[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.
Re-commit after fixing another crash (added regression test).
Differential Revision: https://reviews.llvm.org/D41910
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
old mode 100644
new mode 100755
index f917d9c..7f0bdc9
--- 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 @@
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(TemplateParams->size());
+ 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(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(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