vendor/llvm-project/llvmorg-10-init-17466-ge26a78e7085

1 files changed, 762 insertions, 59 deletions

diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index 848ccf543445..018ac2d7dc9d 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -11,15 +11,24 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "clang/Sema/SemaConcept.h"
 #include "clang/Sema/Sema.h"
+#include "clang/Sema/SemaInternal.h"
 #include "clang/Sema/SemaDiagnostic.h"
 #include "clang/Sema/TemplateDeduction.h"
 #include "clang/Sema/Template.h"
 #include "clang/AST/ExprCXX.h"
+#include "clang/AST/RecursiveASTVisitor.h"
+#include "clang/Basic/OperatorPrecedence.h"
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/PointerUnion.h"
 using namespace clang;
 using namespace sema;
 
-bool Sema::CheckConstraintExpression(Expr *ConstraintExpression) {
+bool
+Sema::CheckConstraintExpression(Expr *ConstraintExpression, Token NextToken,
+                                bool *PossibleNonPrimary,
+                                bool IsTrailingRequiresClause) {
   // C++2a [temp.constr.atomic]p1
   // ..E shall be a constant expression of type bool.
 
@@ -27,99 +36,793 @@ bool Sema::CheckConstraintExpression(Expr *ConstraintExpression) {
 
   if (auto *BinOp = dyn_cast<BinaryOperator>(ConstraintExpression)) {
     if (BinOp->getOpcode() == BO_LAnd || BinOp->getOpcode() == BO_LOr)
-      return CheckConstraintExpression(BinOp->getLHS()) &&
-             CheckConstraintExpression(BinOp->getRHS());
+      return CheckConstraintExpression(BinOp->getLHS(), NextToken,
+                                       PossibleNonPrimary) &&
+             CheckConstraintExpression(BinOp->getRHS(), NextToken,
+                                       PossibleNonPrimary);
   } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression))
-    return CheckConstraintExpression(C->getSubExpr());
+    return CheckConstraintExpression(C->getSubExpr(), NextToken,
+                                     PossibleNonPrimary);
+
+  QualType Type = ConstraintExpression->getType();
+
+  auto CheckForNonPrimary = [&] {
+    if (PossibleNonPrimary)
+      *PossibleNonPrimary =
+          // We have the following case:
+          // template<typename> requires func(0) struct S { };
+          // The user probably isn't aware of the parentheses required around
+          // the function call, and we're only going to parse 'func' as the
+          // primary-expression, and complain that it is of non-bool type.
+          (NextToken.is(tok::l_paren) &&
+           (IsTrailingRequiresClause ||
+            (Type->isDependentType() &&
+             IsDependentFunctionNameExpr(ConstraintExpression)) ||
+            Type->isFunctionType() ||
+            Type->isSpecificBuiltinType(BuiltinType::Overload))) ||
+          // We have the following case:
+          // template<typename T> requires size_<T> == 0 struct S { };
+          // The user probably isn't aware of the parentheses required around
+          // the binary operator, and we're only going to parse 'func' as the
+          // first operand, and complain that it is of non-bool type.
+          getBinOpPrecedence(NextToken.getKind(),
+                             /*GreaterThanIsOperator=*/true,
+                             getLangOpts().CPlusPlus11) > prec::LogicalAnd;
+  };
 
   // An atomic constraint!
-  if (ConstraintExpression->isTypeDependent())
+  if (ConstraintExpression->isTypeDependent()) {
+    CheckForNonPrimary();
     return true;
+  }
 
-  QualType Type = ConstraintExpression->getType();
   if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) {
     Diag(ConstraintExpression->getExprLoc(),
          diag::err_non_bool_atomic_constraint) << Type
         << ConstraintExpression->getSourceRange();
+    CheckForNonPrimary();
     return false;
   }
+
+  if (PossibleNonPrimary)
+      *PossibleNonPrimary = false;
   return true;
 }
 
-bool
-Sema::CalculateConstraintSatisfaction(ConceptDecl *NamedConcept,
-                                      MultiLevelTemplateArgumentList &MLTAL,
-                                      Expr *ConstraintExpr,
-                                      bool &IsSatisfied) {
+template <typename AtomicEvaluator>
+static bool
+calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
+                                ConstraintSatisfaction &Satisfaction,
+                                AtomicEvaluator &&Evaluator) {
   ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
 
   if (auto *BO = dyn_cast<BinaryOperator>(ConstraintExpr)) {
-    if (BO->getOpcode() == BO_LAnd) {
-      if (CalculateConstraintSatisfaction(NamedConcept, MLTAL, BO->getLHS(),
-                                          IsSatisfied))
+    if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) {
+      if (calculateConstraintSatisfaction(S, BO->getLHS(), Satisfaction,
+                                          Evaluator))
         return true;
-      if (!IsSatisfied)
+
+      bool IsLHSSatisfied = Satisfaction.IsSatisfied;
+
+      if (BO->getOpcode() == BO_LOr && IsLHSSatisfied)
+        // [temp.constr.op] p3
+        //    A disjunction is a constraint taking two operands. To determine if
+        //    a disjunction is satisfied, the satisfaction of the first operand
+        //    is checked. If that is satisfied, the disjunction is satisfied.
+        //    Otherwise, the disjunction is satisfied if and only if the second
+        //    operand is satisfied.
         return false;
-      return CalculateConstraintSatisfaction(NamedConcept, MLTAL, BO->getRHS(),
-                                             IsSatisfied);
-    } else if (BO->getOpcode() == BO_LOr) {
-      if (CalculateConstraintSatisfaction(NamedConcept, MLTAL, BO->getLHS(),
-                                          IsSatisfied))
-        return true;
-      if (IsSatisfied)
+
+      if (BO->getOpcode() == BO_LAnd && !IsLHSSatisfied)
+        // [temp.constr.op] p2
+        //    A conjunction is a constraint taking two operands. To determine if
+        //    a conjunction is satisfied, the satisfaction of the first operand
+        //    is checked. If that is not satisfied, the conjunction is not
+        //    satisfied. Otherwise, the conjunction is satisfied if and only if
+        //    the second operand is satisfied.
         return false;
-      return CalculateConstraintSatisfaction(NamedConcept, MLTAL, BO->getRHS(),
-                                             IsSatisfied);
+
+      return calculateConstraintSatisfaction(S, BO->getRHS(), Satisfaction,
+          std::forward<AtomicEvaluator>(Evaluator));
     }
   }
   else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr))
-    return CalculateConstraintSatisfaction(NamedConcept, MLTAL, C->getSubExpr(),
-                                           IsSatisfied);
+    return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction,
+        std::forward<AtomicEvaluator>(Evaluator));
 
-  EnterExpressionEvaluationContext ConstantEvaluated(
-      *this, Sema::ExpressionEvaluationContext::ConstantEvaluated);
+  // An atomic constraint expression
+  ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr);
 
-  // Atomic constraint - substitute arguments and check satisfaction.
-  ExprResult E;
-  {
-    TemplateDeductionInfo Info(ConstraintExpr->getBeginLoc());
-    InstantiatingTemplate Inst(*this, ConstraintExpr->getBeginLoc(),
-                               InstantiatingTemplate::ConstraintSubstitution{},
-                               NamedConcept, Info,
-                               ConstraintExpr->getSourceRange());
-    if (Inst.isInvalid())
-      return true;
-    // We do not want error diagnostics escaping here.
-    Sema::SFINAETrap Trap(*this);
+  if (SubstitutedAtomicExpr.isInvalid())
+    return true;
+
+  if (!SubstitutedAtomicExpr.isUsable())
+    // Evaluator has decided satisfaction without yielding an expression.
+    return false;
 
-    E = SubstExpr(ConstraintExpr, MLTAL);
-    if (E.isInvalid() || Trap.hasErrorOccurred()) {
+  EnterExpressionEvaluationContext ConstantEvaluated(
+      S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
+  SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;
+  Expr::EvalResult EvalResult;
+  EvalResult.Diag = &EvaluationDiags;
+  if (!SubstitutedAtomicExpr.get()->EvaluateAsRValue(EvalResult, S.Context)) {
       // C++2a [temp.constr.atomic]p1
-      //   ...If substitution results in an invalid type or expression, the
-      //   constraint is not satisfied.
-      IsSatisfied = false;
+      //   ...E shall be a constant expression of type bool.
+    S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(),
+           diag::err_non_constant_constraint_expression)
+        << SubstitutedAtomicExpr.get()->getSourceRange();
+    for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
+      S.Diag(PDiag.first, PDiag.second);
+    return true;
+  }
+
+  Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
+  if (!Satisfaction.IsSatisfied)
+    Satisfaction.Details.emplace_back(ConstraintExpr,
+                                      SubstitutedAtomicExpr.get());
+
+  return false;
+}
+
+template <typename TemplateDeclT>
+static bool calculateConstraintSatisfaction(
+    Sema &S, TemplateDeclT *Template, ArrayRef<TemplateArgument> TemplateArgs,
+    SourceLocation TemplateNameLoc, MultiLevelTemplateArgumentList &MLTAL,
+    const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction) {
+  return calculateConstraintSatisfaction(
+      S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) {
+        EnterExpressionEvaluationContext ConstantEvaluated(
+            S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
+
+        // Atomic constraint - substitute arguments and check satisfaction.
+        ExprResult SubstitutedExpression;
+        {
+          TemplateDeductionInfo Info(TemplateNameLoc);
+          Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(),
+              Sema::InstantiatingTemplate::ConstraintSubstitution{}, Template,
+              Info, AtomicExpr->getSourceRange());
+          if (Inst.isInvalid())
+            return ExprError();
+          // We do not want error diagnostics escaping here.
+          Sema::SFINAETrap Trap(S);
+          SubstitutedExpression = S.SubstExpr(const_cast<Expr *>(AtomicExpr),
+                                              MLTAL);
+          if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
+            // C++2a [temp.constr.atomic]p1
+            //   ...If substitution results in an invalid type or expression, the
+            //   constraint is not satisfied.
+            if (!Trap.hasErrorOccurred())
+              // A non-SFINAE error has occured as a result of this
+              // substitution.
+              return ExprError();
+
+            PartialDiagnosticAt SubstDiag{SourceLocation(),
+                                          PartialDiagnostic::NullDiagnostic()};
+            Info.takeSFINAEDiagnostic(SubstDiag);
+            // FIXME: Concepts: This is an unfortunate consequence of there
+            //  being no serialization code for PartialDiagnostics and the fact
+            //  that serializing them would likely take a lot more storage than
+            //  just storing them as strings. We would still like, in the
+            //  future, to serialize the proper PartialDiagnostic as serializing
+            //  it as a string defeats the purpose of the diagnostic mechanism.
+            SmallString<128> DiagString;
+            DiagString = ": ";
+            SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString);
+            unsigned MessageSize = DiagString.size();
+            char *Mem = new (S.Context) char[MessageSize];
+            memcpy(Mem, DiagString.c_str(), MessageSize);
+            Satisfaction.Details.emplace_back(
+                AtomicExpr,
+                new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
+                        SubstDiag.first, StringRef(Mem, MessageSize)});
+            Satisfaction.IsSatisfied = false;
+            return ExprEmpty();
+          }
+        }
+
+        if (!S.CheckConstraintExpression(SubstitutedExpression.get()))
+          return ExprError();
+
+        return SubstitutedExpression;
+      });
+}
+
+template<typename TemplateDeclT>
+static bool CheckConstraintSatisfaction(Sema &S, TemplateDeclT *Template,
+                                        ArrayRef<const Expr *> ConstraintExprs,
+                                        ArrayRef<TemplateArgument> TemplateArgs,
+                                        SourceRange TemplateIDRange,
+                                        ConstraintSatisfaction &Satisfaction) {
+  if (ConstraintExprs.empty()) {
+    Satisfaction.IsSatisfied = true;
+    return false;
+  }
+
+  for (auto& Arg : TemplateArgs)
+    if (Arg.isInstantiationDependent()) {
+      // No need to check satisfaction for dependent constraint expressions.
+      Satisfaction.IsSatisfied = true;
       return false;
     }
+
+  Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
+      Sema::InstantiatingTemplate::ConstraintsCheck{}, Template, TemplateArgs,
+      TemplateIDRange);
+  if (Inst.isInvalid())
+    return true;
+
+  MultiLevelTemplateArgumentList MLTAL;
+  MLTAL.addOuterTemplateArguments(TemplateArgs);
+
+  for (const Expr *ConstraintExpr : ConstraintExprs) {
+    if (calculateConstraintSatisfaction(S, Template, TemplateArgs,
+                                        TemplateIDRange.getBegin(), MLTAL,
+                                        ConstraintExpr, Satisfaction))
+      return true;
+    if (!Satisfaction.IsSatisfied)
+      // [temp.constr.op] p2
+      //   [...] To determine if a conjunction is satisfied, the satisfaction
+      //   of the first operand is checked. If that is not satisfied, the
+      //   conjunction is not satisfied. [...]
+      return false;
   }
+  return false;
+}
+
+bool Sema::CheckConstraintSatisfaction(TemplateDecl *Template,
+                                       ArrayRef<const Expr *> ConstraintExprs,
+                                       ArrayRef<TemplateArgument> TemplateArgs,
+                                       SourceRange TemplateIDRange,
+                                       ConstraintSatisfaction &Satisfaction) {
+  return ::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
+                                       TemplateArgs, TemplateIDRange,
+                                       Satisfaction);
+}
 
-  if (!CheckConstraintExpression(E.get()))
+bool
+Sema::CheckConstraintSatisfaction(ClassTemplatePartialSpecializationDecl* Part,
+                                  ArrayRef<const Expr *> ConstraintExprs,
+                                  ArrayRef<TemplateArgument> TemplateArgs,
+                                  SourceRange TemplateIDRange,
+                                  ConstraintSatisfaction &Satisfaction) {
+  return ::CheckConstraintSatisfaction(*this, Part, ConstraintExprs,
+                                       TemplateArgs, TemplateIDRange,
+                                       Satisfaction);
+}
+
+bool
+Sema::CheckConstraintSatisfaction(VarTemplatePartialSpecializationDecl* Partial,
+                                  ArrayRef<const Expr *> ConstraintExprs,
+                                  ArrayRef<TemplateArgument> TemplateArgs,
+                                  SourceRange TemplateIDRange,
+                                  ConstraintSatisfaction &Satisfaction) {
+  return ::CheckConstraintSatisfaction(*this, Partial, ConstraintExprs,
+                                       TemplateArgs, TemplateIDRange,
+                                       Satisfaction);
+}
+
+bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
+                                       ConstraintSatisfaction &Satisfaction) {
+  return calculateConstraintSatisfaction(
+      *this, ConstraintExpr, Satisfaction,
+      [](const Expr *AtomicExpr) -> ExprResult {
+        return ExprResult(const_cast<Expr *>(AtomicExpr));
+      });
+}
+
+bool Sema::EnsureTemplateArgumentListConstraints(
+    TemplateDecl *TD, ArrayRef<TemplateArgument> TemplateArgs,
+    SourceRange TemplateIDRange) {
+  ConstraintSatisfaction Satisfaction;
+  llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
+  TD->getAssociatedConstraints(AssociatedConstraints);
+  if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgs,
+                                  TemplateIDRange, Satisfaction))
     return true;
 
-  SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;
-  Expr::EvalResult EvalResult;
-  EvalResult.Diag = &EvaluationDiags;
-  if (!E.get()->EvaluateAsRValue(EvalResult, Context)) {
-    // C++2a [temp.constr.atomic]p1
-    //   ...E shall be a constant expression of type bool.
-    Diag(E.get()->getBeginLoc(),
-         diag::err_non_constant_constraint_expression)
-        << E.get()->getSourceRange();
-    for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
-      Diag(PDiag.first, PDiag.second);
+  if (!Satisfaction.IsSatisfied) {
+    SmallString<128> TemplateArgString;
+    TemplateArgString = " ";
+    TemplateArgString += getTemplateArgumentBindingsText(
+        TD->getTemplateParameters(), TemplateArgs.data(), TemplateArgs.size());
+
+    Diag(TemplateIDRange.getBegin(),
+         diag::err_template_arg_list_constraints_not_satisfied)
+        << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD
+        << TemplateArgString << TemplateIDRange;
+    DiagnoseUnsatisfiedConstraint(Satisfaction);
+    return true;
+  }
+  return false;
+}
+
+static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
+                                                        Expr *SubstExpr,
+                                                        bool First = true) {
+  SubstExpr = SubstExpr->IgnoreParenImpCasts();
+  if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {
+    switch (BO->getOpcode()) {
+    // These two cases will in practice only be reached when using fold
+    // expressions with || and &&, since otherwise the || and && will have been
+    // broken down into atomic constraints during satisfaction checking.
+    case BO_LOr:
+      // Or evaluated to false - meaning both RHS and LHS evaluated to false.
+      diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
+      diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
+                                                  /*First=*/false);
+      return;
+    case BO_LAnd:
+      bool LHSSatisfied;
+      BO->getLHS()->EvaluateAsBooleanCondition(LHSSatisfied, S.Context);
+      if (LHSSatisfied) {
+        // LHS is true, so RHS must be false.
+        diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First);
+        return;
+      }
+      // LHS is false
+      diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
+
+      // RHS might also be false
+      bool RHSSatisfied;
+      BO->getRHS()->EvaluateAsBooleanCondition(RHSSatisfied, S.Context);
+      if (!RHSSatisfied)
+        diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
+                                                    /*First=*/false);
+      return;
+    case BO_GE:
+    case BO_LE:
+    case BO_GT:
+    case BO_LT:
+    case BO_EQ:
+    case BO_NE:
+      if (BO->getLHS()->getType()->isIntegerType() &&
+          BO->getRHS()->getType()->isIntegerType()) {
+        Expr::EvalResult SimplifiedLHS;
+        Expr::EvalResult SimplifiedRHS;
+        BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context);
+        BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context);
+        if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
+          S.Diag(SubstExpr->getBeginLoc(),
+                 diag::note_atomic_constraint_evaluated_to_false_elaborated)
+              << (int)First << SubstExpr
+              << SimplifiedLHS.Val.getInt().toString(10)
+              << BinaryOperator::getOpcodeStr(BO->getOpcode())
+              << SimplifiedRHS.Val.getInt().toString(10);
+          return;
+        }
+      }
+      break;
+
+    default:
+      break;
+    }
+  } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) {
+    if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
+      S.Diag(
+          CSE->getSourceRange().getBegin(),
+          diag::
+          note_single_arg_concept_specialization_constraint_evaluated_to_false)
+          << (int)First
+          << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
+          << CSE->getNamedConcept();
+    } else {
+      S.Diag(SubstExpr->getSourceRange().getBegin(),
+             diag::note_concept_specialization_constraint_evaluated_to_false)
+          << (int)First << CSE;
+    }
+    S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction());
+    return;
+  }
+
+  S.Diag(SubstExpr->getSourceRange().getBegin(),
+         diag::note_atomic_constraint_evaluated_to_false)
+      << (int)First << SubstExpr;
+}
+
+template<typename SubstitutionDiagnostic>
+static void diagnoseUnsatisfiedConstraintExpr(
+    Sema &S, const Expr *E,
+    const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
+    bool First = true) {
+  if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){
+    S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
+        << Diag->second;
+    return;
+  }
+
+  diagnoseWellFormedUnsatisfiedConstraintExpr(S,
+      Record.template get<Expr *>(), First);
+}
+
+void Sema::DiagnoseUnsatisfiedConstraint(
+    const ConstraintSatisfaction& Satisfaction) {
+  assert(!Satisfaction.IsSatisfied &&
+         "Attempted to diagnose a satisfied constraint");
+  bool First = true;
+  for (auto &Pair : Satisfaction.Details) {
+    diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
+    First = false;
+  }
+}
+
+void Sema::DiagnoseUnsatisfiedConstraint(
+    const ASTConstraintSatisfaction &Satisfaction) {
+  assert(!Satisfaction.IsSatisfied &&
+         "Attempted to diagnose a satisfied constraint");
+  bool First = true;
+  for (auto &Pair : Satisfaction) {
+    diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
+    First = false;
+  }
+}
+
+const NormalizedConstraint *
+Sema::getNormalizedAssociatedConstraints(
+    NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) {
+  auto CacheEntry = NormalizationCache.find(ConstrainedDecl);
+  if (CacheEntry == NormalizationCache.end()) {
+    auto Normalized =
+        NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl,
+                                                  AssociatedConstraints);
+    CacheEntry =
+        NormalizationCache
+            .try_emplace(ConstrainedDecl,
+                         Normalized
+                             ? new (Context) NormalizedConstraint(
+                                 std::move(*Normalized))
+                             : nullptr)
+            .first;
+  }
+  return CacheEntry->second;
+}
+
+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(
+        MutableArrayRef<TemplateArgumentLoc>(
+            new (S.Context) TemplateArgumentLoc[OccurringIndices.count()],
+            OccurringIndices.count()));
+    for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I)
+      if (OccurringIndices[I])
+        new (&(*Atomic.ParameterMapping)[J++]) TemplateArgumentLoc(
+            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;
+}
+
+Optional<NormalizedConstraint>
+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 None;
+  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;
+}
+
+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, std::move(*LHS), std::move(*RHS),
+          BO->getOpcode() == BO_LAnd ? CCK_Conjunction : CCK_Disjunction);
+    }
+  } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) {
+    const 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.
+      // [...]
+      ConceptDecl *CD = CSE->getNamedConcept();
+      SubNF = S.getNormalizedAssociatedConstraints(CD,
+                                                   {CD->getConstraintExpr()});
+      if (!SubNF)
+        return None;
+    }
+
+    Optional<NormalizedConstraint> New;
+    New.emplace(S.Context, *SubNF);
+
+    if (substituteParameterMappings(
+            S, *New, CSE->getNamedConcept(),
+            CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten()))
+      return None;
+
+    return New;
+  }
+  return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)};
+}
+
+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;
+}
+
+template<typename AtomicSubsumptionEvaluator>
+static bool subsumes(NormalForm PDNF, NormalForm QCNF,
+                     AtomicSubsumptionEvaluator E) {
+  // 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 (E(*Pia, *Qjb)) {
+            Found = true;
+            break;
+          }
+        }
+        if (Found)
+          break;
+      }
+      if (!Found)
+        return false;
+    }
+  }
+  return true;
+}
+
+template<typename AtomicSubsumptionEvaluator>
+static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
+                     NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes,
+                     AtomicSubsumptionEvaluator E) {
+  // 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 = S.getNormalizedAssociatedConstraints(DP, P);
+  if (!PNormalized)
+    return true;
+  const NormalForm PDNF = makeDNF(*PNormalized);
+
+  auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q);
+  if (!QNormalized)
     return true;
+  const NormalForm QCNF = makeCNF(*QNormalized);
+
+  Subsumes = subsumes(PDNF, QCNF, E);
+  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;
   }
 
-  IsSatisfied = EvalResult.Val.getInt().getBoolValue();
+  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,
+        [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
+          return A.subsumes(Context, B);
+        }))
+    return true;
+  SubsumptionCache.try_emplace(Key, Result);
   return false;
-}
\ No newline at end of file
+}
+
+bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
+    ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) {
+  if (isSFINAEContext())
+    // No need to work here because our notes would be discarded.
+    return false;
+
+  if (AC1.empty() || AC2.empty())
+    return false;
+
+  auto NormalExprEvaluator =
+      [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
+        return A.subsumes(Context, B);
+      };
+
+  const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
+  auto IdenticalExprEvaluator =
+      [&] (const AtomicConstraint &A, const AtomicConstraint &B) {
+        if (!A.hasMatchingParameterMapping(Context, B))
+          return false;
+        const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
+        if (EA == EB)
+          return true;
+
+        // Not the same source level expression - are the expressions
+        // identical?
+        llvm::FoldingSetNodeID IDA, IDB;
+        EA->Profile(IDA, Context, /*Cannonical=*/true);
+        EB->Profile(IDB, Context, /*Cannonical=*/true);
+        if (IDA != IDB)
+          return false;
+
+        AmbiguousAtomic1 = EA;
+        AmbiguousAtomic2 = EB;
+        return true;
+      };
+
+  {
+    // The subsumption checks might cause diagnostics
+    SFINAETrap Trap(*this);
+    auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1);
+    if (!Normalized1)
+      return false;
+    const NormalForm DNF1 = makeDNF(*Normalized1);
+    const NormalForm CNF1 = makeCNF(*Normalized1);
+
+    auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2);
+    if (!Normalized2)
+      return false;
+    const NormalForm DNF2 = makeDNF(*Normalized2);
+    const NormalForm CNF2 = makeCNF(*Normalized2);
+
+    bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator);
+    bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator);
+    bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator);
+    bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator);
+    if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
+        Is2AtLeastAs1 == Is2AtLeastAs1Normally)
+      // Same result - no ambiguity was caused by identical atomic expressions.
+      return false;
+  }
+
+  // A different result! Some ambiguous atomic constraint(s) caused a difference
+  assert(AmbiguousAtomic1 && AmbiguousAtomic2);
+
+  Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints)
+      << AmbiguousAtomic1->getSourceRange();
+  Diag(AmbiguousAtomic2->getBeginLoc(),
+       diag::note_ambiguous_atomic_constraints_similar_expression)
+      << AmbiguousAtomic2->getSourceRange();
+  return true;
+}