[Concepts] Constrained partial specializations and function overloads.

Added support for constraint satisfaction checking and partial ordering of constraints in constrained partial specialization and function template overloads.

Phabricator: D41910

1 files changed, 360 insertions, 0 deletions

diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index f917d9c7e5a..cd41000fa02 100644..100755
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -17,6 +17,7 @@
 #include "clang/Sema/TemplateDeduction.h"
 #include "clang/Sema/Template.h"
 #include "clang/AST/ExprCXX.h"
+#include "clang/AST/RecursiveASTVisitor.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PointerUnion.h"
 using namespace clang;
@@ -414,4 +415,363 @@ void Sema::DiagnoseUnsatisfiedConstraint(
     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
     First = false;
   }
+}
+
+namespace {
+struct AtomicConstraint {
+  const Expr *ConstraintExpr;
+  llvm::Optional<llvm::SmallVector<TemplateArgumentLoc, 3>> ParameterMapping;
+
+  AtomicConstraint(Sema &S, const Expr *ConstraintExpr) :
+      ConstraintExpr(ConstraintExpr) { };
+
+  bool hasMatchingParameterMapping(ASTContext &C,
+                                   const AtomicConstraint &Other) const {
+    if (!ParameterMapping != !Other.ParameterMapping)
+      return false;
+    if (!ParameterMapping)
+      return true;
+    if (ParameterMapping->size() != Other.ParameterMapping->size())
+      return false;
+
+    for (unsigned I = 0, S = ParameterMapping->size(); I < S; ++I)
+      if (!C.getCanonicalTemplateArgument((*ParameterMapping)[I].getArgument())
+               .structurallyEquals(C.getCanonicalTemplateArgument(
+                  (*Other.ParameterMapping)[I].getArgument())))
+        return false;
+    return true;
+  }
+
+  bool subsumes(ASTContext &C, const AtomicConstraint &Other) const {
+    // C++ [temp.constr.order] p2
+    //   - an atomic constraint A subsumes another atomic constraint B
+    //     if and only if the A and B are identical [...]
+    //
+    // C++ [temp.constr.atomic] p2
+    //   Two atomic constraints are identical if they are formed from the
+    //   same expression and the targets of the parameter mappings are
+    //   equivalent according to the rules for expressions [...]
+
+    // We do not actually substitute the parameter mappings into the
+    // constraint expressions, therefore the constraint expressions are
+    // the originals, and comparing them will suffice.
+    if (ConstraintExpr != Other.ConstraintExpr)
+      return false;
+
+    // Check that the parameter lists are identical
+    return hasMatchingParameterMapping(C, Other);
+  }
+};
+
+/// \brief A normalized constraint, as defined in C++ [temp.constr.normal], is
+/// either an atomic constraint, a conjunction of normalized constraints or a
+/// disjunction of normalized constraints.
+struct NormalizedConstraint {
+  enum CompoundConstraintKind { CCK_Conjunction, CCK_Disjunction };
+
+  using CompoundConstraint = llvm::PointerIntPair<
+      std::pair<NormalizedConstraint, NormalizedConstraint> *, 1,
+      CompoundConstraintKind>;
+
+  llvm::PointerUnion<AtomicConstraint *, CompoundConstraint> Constraint;
+
+  NormalizedConstraint(AtomicConstraint *C): Constraint{C} { };
+  NormalizedConstraint(ASTContext &C, NormalizedConstraint LHS,
+                       NormalizedConstraint RHS, CompoundConstraintKind Kind)
+      : Constraint{CompoundConstraint{
+            new (C) std::pair<NormalizedConstraint, NormalizedConstraint>{LHS,
+                                                                          RHS},
+            Kind}} { };
+
+  CompoundConstraintKind getCompoundKind() const {
+    assert(!isAtomic() && "getCompoundKind called on atomic constraint.");
+    return Constraint.get<CompoundConstraint>().getInt();
+  }
+
+  bool isAtomic() const { return Constraint.is<AtomicConstraint *>(); }
+
+  NormalizedConstraint &getLHS() const {
+    assert(!isAtomic() && "getLHS called on atomic constraint.");
+    return Constraint.get<CompoundConstraint>().getPointer()->first;
+  }
+
+  NormalizedConstraint &getRHS() const {
+    assert(!isAtomic() && "getRHS called on atomic constraint.");
+    return Constraint.get<CompoundConstraint>().getPointer()->second;
+  }
+
+  AtomicConstraint *getAtomicConstraint() const {
+    assert(isAtomic() &&
+           "getAtomicConstraint called on non-atomic constraint.");
+    return Constraint.get<AtomicConstraint *>();
+  }
+
+  static llvm::Optional<NormalizedConstraint>
+  fromConstraintExprs(Sema &S, NamedDecl *D, ArrayRef<const Expr *> E) {
+    assert(E.size() != 0);
+    auto First = fromConstraintExpr(S, D, E[0]);
+    if (E.size() == 1)
+      return First;
+    auto Second = fromConstraintExpr(S, D, E[1]);
+    if (!Second)
+      return llvm::Optional<NormalizedConstraint>{};
+    llvm::Optional<NormalizedConstraint> Conjunction;
+    Conjunction.emplace(S.Context, std::move(*First), std::move(*Second),
+                        CCK_Conjunction);
+    for (unsigned I = 2; I < E.size(); ++I) {
+      auto Next = fromConstraintExpr(S, D, E[I]);
+      if (!Next)
+        return llvm::Optional<NormalizedConstraint>{};
+      NormalizedConstraint NewConjunction(S.Context, std::move(*Conjunction),
+                                          std::move(*Next), CCK_Conjunction);
+      *Conjunction = std::move(NewConjunction);
+    }
+    return Conjunction;
+  }
+
+private:
+  static llvm::Optional<NormalizedConstraint> fromConstraintExpr(Sema &S,
+                                                                 NamedDecl *D,
+                                                                 const Expr *E);
+};
+
+static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
+    ConceptDecl *Concept, ArrayRef<TemplateArgument> TemplateArgs,
+    const ASTTemplateArgumentListInfo *ArgsAsWritten) {
+  if (!N.isAtomic()) {
+    if (substituteParameterMappings(S, N.getLHS(), Concept, TemplateArgs,
+                                    ArgsAsWritten))
+      return true;
+    return substituteParameterMappings(S, N.getRHS(), Concept, TemplateArgs,
+                                       ArgsAsWritten);
+  }
+  TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
+
+  AtomicConstraint &Atomic = *N.getAtomicConstraint();
+  TemplateArgumentListInfo SubstArgs;
+  MultiLevelTemplateArgumentList MLTAL;
+  MLTAL.addOuterTemplateArguments(TemplateArgs);
+  if (!Atomic.ParameterMapping) {
+    llvm::SmallBitVector OccurringIndices;
+    S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
+                                 /*Depth=*/0, OccurringIndices);
+    Atomic.ParameterMapping.emplace();
+    Atomic.ParameterMapping->reserve(OccurringIndices.size());
+    for (unsigned I = 0, C = TemplateParams->size(); I != C; ++I)
+      if (OccurringIndices[I])
+        Atomic.ParameterMapping->push_back(
+            S.getIdentityTemplateArgumentLoc(TemplateParams->begin()[I],
+                // Here we assume we do not support things like
+                // template<typename A, typename B>
+                // concept C = ...;
+                //
+                // template<typename... Ts> requires C<Ts...>
+                // struct S { };
+                // The above currently yields a diagnostic.
+                // We still might have default arguments for concept parameters.
+                ArgsAsWritten->NumTemplateArgs > I ?
+                ArgsAsWritten->arguments()[I].getLocation() :
+                SourceLocation()));
+  }
+  Sema::InstantiatingTemplate Inst(
+      S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(),
+      Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept,
+      SourceRange(ArgsAsWritten->arguments()[0].getSourceRange().getBegin(),
+                  ArgsAsWritten->arguments().back().getSourceRange().getEnd()));
+  if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs))
+    return true;
+  std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(),
+            N.getAtomicConstraint()->ParameterMapping->begin());
+  return false;
+}
+
+llvm::Optional<NormalizedConstraint>
+NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
+  assert(E != nullptr);
+
+  // C++ [temp.constr.normal]p1.1
+  // [...]
+  // - The normal form of an expression (E) is the normal form of E.
+  // [...]
+  E = E->IgnoreParenImpCasts();
+  if (auto *BO = dyn_cast<const BinaryOperator>(E)) {
+    if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) {
+      auto LHS = fromConstraintExpr(S, D, BO->getLHS());
+      if (!LHS)
+        return None;
+      auto RHS = fromConstraintExpr(S, D, BO->getRHS());
+      if (!RHS)
+        return None;
+
+      return NormalizedConstraint(
+          S.Context, *LHS, *RHS,
+          BO->getOpcode() == BO_LAnd ? CCK_Conjunction : CCK_Disjunction);
+    }
+  } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) {
+    Optional<NormalizedConstraint> SubNF;
+    {
+      Sema::InstantiatingTemplate Inst(
+          S, CSE->getExprLoc(),
+          Sema::InstantiatingTemplate::ConstraintNormalization{}, D,
+          CSE->getSourceRange());
+      // C++ [temp.constr.normal]p1.1
+      // [...]
+      // The normal form of an id-expression of the form C<A1, A2, ..., AN>,
+      // where C names a concept, is the normal form of the
+      // constraint-expression of C, after substituting A1, A2, ..., AN for C’s
+      // respective template parameters in the parameter mappings in each atomic
+      // constraint. If any such substitution results in an invalid type or
+      // expression, the program is ill-formed; no diagnostic is required.
+      // [...]
+      SubNF = fromConstraintExpr(S, CSE->getNamedConcept(),
+                                 CSE->getNamedConcept()->getConstraintExpr());
+      if (!SubNF)
+        return None;
+    }
+
+    if (substituteParameterMappings(
+            S, *SubNF, CSE->getNamedConcept(),
+            CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten()))
+      return None;
+
+    return SubNF;
+  }
+  return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)};
+}
+
+} // namespace
+
+using NormalForm =
+    llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>;
+
+static NormalForm makeCNF(const NormalizedConstraint &Normalized) {
+  if (Normalized.isAtomic())
+    return {{Normalized.getAtomicConstraint()}};
+
+  NormalForm LCNF = makeCNF(Normalized.getLHS());
+  NormalForm RCNF = makeCNF(Normalized.getRHS());
+  if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
+    LCNF.reserve(LCNF.size() + RCNF.size());
+    while (!RCNF.empty())
+      LCNF.push_back(std::move(RCNF.pop_back_val()));
+    return LCNF;
+  }
+
+  // Disjunction
+  NormalForm Res;
+  Res.reserve(LCNF.size() * RCNF.size());
+  for (auto &LDisjunction : LCNF)
+    for (auto &RDisjunction : RCNF) {
+      NormalForm::value_type Combined;
+      Combined.reserve(LDisjunction.size() + RDisjunction.size());
+      std::copy(LDisjunction.begin(), LDisjunction.end(),
+                std::back_inserter(Combined));
+      std::copy(RDisjunction.begin(), RDisjunction.end(),
+                std::back_inserter(Combined));
+      Res.emplace_back(Combined);
+    }
+  return Res;
+}
+
+static NormalForm makeDNF(const NormalizedConstraint &Normalized) {
+  if (Normalized.isAtomic())
+    return {{Normalized.getAtomicConstraint()}};
+
+  NormalForm LDNF = makeDNF(Normalized.getLHS());
+  NormalForm RDNF = makeDNF(Normalized.getRHS());
+  if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
+    LDNF.reserve(LDNF.size() + RDNF.size());
+    while (!RDNF.empty())
+      LDNF.push_back(std::move(RDNF.pop_back_val()));
+    return LDNF;
+  }
+
+  // Conjunction
+  NormalForm Res;
+  Res.reserve(LDNF.size() * RDNF.size());
+  for (auto &LConjunction : LDNF) {
+    for (auto &RConjunction : RDNF) {
+      NormalForm::value_type Combined;
+      Combined.reserve(LConjunction.size() + RConjunction.size());
+      std::copy(LConjunction.begin(), LConjunction.end(),
+                std::back_inserter(Combined));
+      std::copy(RConjunction.begin(), RConjunction.end(),
+                std::back_inserter(Combined));
+      Res.emplace_back(Combined);
+    }
+  }
+  return Res;
+}
+
+static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
+                     NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes) {
+  // C++ [temp.constr.order] p2
+  //   In order to determine if a constraint P subsumes a constraint Q, P is
+  //   transformed into disjunctive normal form, and Q is transformed into
+  //   conjunctive normal form. [...]
+  auto PNormalized = NormalizedConstraint::fromConstraintExprs(S, DP, P);
+  if (!PNormalized)
+    return true;
+  const NormalForm PDNF = makeDNF(*PNormalized);
+
+  auto QNormalized = NormalizedConstraint::fromConstraintExprs(S, DQ, Q);
+  if (!QNormalized)
+    return true;
+  const NormalForm QCNF = makeCNF(*QNormalized);
+
+  // C++ [temp.constr.order] p2
+  //   Then, P subsumes Q if and only if, for every disjunctive clause Pi in the
+  //   disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in
+  //   the conjuctive normal form of Q, where [...]
+  for (const auto &Pi : PDNF) {
+    for (const auto &Qj : QCNF) {
+      // C++ [temp.constr.order] p2
+      //   - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
+      //     and only if there exists an atomic constraint Pia in Pi for which
+      //     there exists an atomic constraint, Qjb, in Qj such that Pia
+      //     subsumes Qjb.
+      bool Found = false;
+      for (const AtomicConstraint *Pia : Pi) {
+        for (const AtomicConstraint *Qjb : Qj) {
+          if (Pia->subsumes(S.Context, *Qjb)) {
+            Found = true;
+            break;
+          }
+        }
+        if (Found)
+          break;
+      }
+      if (!Found) {
+        Subsumes = false;
+        return false;
+      }
+    }
+  }
+  Subsumes = true;
+  return false;
+}
+
+bool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef<const Expr *> AC1,
+                                  NamedDecl *D2, ArrayRef<const Expr *> AC2,
+                                  bool &Result) {
+  if (AC1.empty()) {
+    Result = AC2.empty();
+    return false;
+  }
+  if (AC2.empty()) {
+    // TD1 has associated constraints and TD2 does not.
+    Result = true;
+    return false;
+  }
+
+  std::pair<NamedDecl *, NamedDecl *> Key{D1, D2};
+  auto CacheEntry = SubsumptionCache.find(Key);
+  if (CacheEntry != SubsumptionCache.end()) {
+    Result = CacheEntry->second;
+    return false;
+  }
+  if (subsumes(*this, D1, AC1, D2, AC2, Result))
+    return true;
+  SubsumptionCache.try_emplace(Key, Result);
+  return false;
 }
\ No newline at end of file