vendor/llvm-project/llvmorg-16-init-18548-gb0daacf58f41

1 files changed, 555 insertions, 137 deletions

diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index 239e5dc4394c..4d4b2482d046 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -10,6 +10,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "TreeTransform.h"
 #include "clang/Sema/SemaConcept.h"
 #include "clang/Sema/Sema.h"
 #include "clang/Sema/SemaInternal.h"
@@ -18,18 +19,21 @@
 #include "clang/Sema/Template.h"
 #include "clang/Sema/Overload.h"
 #include "clang/Sema/Initialization.h"
+#include "clang/AST/ASTLambda.h"
 #include "clang/AST/ExprConcepts.h"
 #include "clang/AST/RecursiveASTVisitor.h"
 #include "clang/Basic/OperatorPrecedence.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/StringExtras.h"
+#include <optional>
 
 using namespace clang;
 using namespace sema;
 
 namespace {
 class LogicalBinOp {
+  SourceLocation Loc;
   OverloadedOperatorKind Op = OO_None;
   const Expr *LHS = nullptr;
   const Expr *RHS = nullptr;
@@ -40,12 +44,14 @@ public:
       Op = BinaryOperator::getOverloadedOperator(BO->getOpcode());
       LHS = BO->getLHS();
       RHS = BO->getRHS();
+      Loc = BO->getExprLoc();
     } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(E)) {
       // If OO is not || or && it might not have exactly 2 arguments.
       if (OO->getNumArgs() == 2) {
         Op = OO->getOperator();
         LHS = OO->getArg(0);
         RHS = OO->getArg(1);
+        Loc = OO->getOperatorLoc();
       }
     }
   }
@@ -56,6 +62,26 @@ public:
 
   const Expr *getLHS() const { return LHS; }
   const Expr *getRHS() const { return RHS; }
+
+  ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS) const {
+    return recreateBinOp(SemaRef, LHS, const_cast<Expr *>(getRHS()));
+  }
+
+  ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS,
+                           ExprResult RHS) const {
+    assert((isAnd() || isOr()) && "Not the right kind of op?");
+    assert((!LHS.isInvalid() && !RHS.isInvalid()) && "not good expressions?");
+
+    if (!LHS.isUsable() || !RHS.isUsable())
+      return ExprEmpty();
+
+    // We should just be able to 'normalize' these to the builtin Binary
+    // Operator, since that is how they are evaluated in constriant checks.
+    return BinaryOperator::Create(SemaRef.Context, LHS.get(), RHS.get(),
+                                  BinaryOperator::getOverloadedOpcode(Op),
+                                  SemaRef.Context.BoolTy, VK_PRValue,
+                                  OK_Ordinary, Loc, FPOptionsOverride{});
+  }
 };
 }
 
@@ -121,17 +147,30 @@ bool Sema::CheckConstraintExpression(const Expr *ConstraintExpression,
   return true;
 }
 
+namespace {
+struct SatisfactionStackRAII {
+  Sema &SemaRef;
+  SatisfactionStackRAII(Sema &SemaRef, llvm::FoldingSetNodeID FSNID)
+      : SemaRef(SemaRef) {
+      SemaRef.PushSatisfactionStackEntry(FSNID);
+  }
+  ~SatisfactionStackRAII() { SemaRef.PopSatisfactionStackEntry(); }
+};
+} // namespace
+
 template <typename AtomicEvaluator>
-static bool
+static ExprResult
 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
                                 ConstraintSatisfaction &Satisfaction,
                                 AtomicEvaluator &&Evaluator) {
   ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
 
   if (LogicalBinOp BO = ConstraintExpr) {
-    if (calculateConstraintSatisfaction(S, BO.getLHS(), Satisfaction,
-                                        Evaluator))
-      return true;
+    ExprResult LHSRes = calculateConstraintSatisfaction(
+        S, BO.getLHS(), Satisfaction, Evaluator);
+
+    if (LHSRes.isInvalid())
+      return ExprError();
 
     bool IsLHSSatisfied = Satisfaction.IsSatisfied;
 
@@ -142,7 +181,8 @@ calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
       //    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;
+      // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
+      return LHSRes;
 
     if (BO.isAnd() && !IsLHSSatisfied)
       // [temp.constr.op] p2
@@ -151,12 +191,22 @@ calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
       //    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;
+      // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
+      return LHSRes;
 
-    return calculateConstraintSatisfaction(
+    ExprResult RHSRes = calculateConstraintSatisfaction(
         S, BO.getRHS(), Satisfaction, std::forward<AtomicEvaluator>(Evaluator));
-  } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) {
-    return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction,
+    if (RHSRes.isInvalid())
+      return ExprError();
+
+    return BO.recreateBinOp(S, LHSRes, RHSRes);
+  }
+
+  if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) {
+    // These aren't evaluated, so we don't care about cleanups, so we can just
+    // evaluate these as if the cleanups didn't exist.
+    return calculateConstraintSatisfaction(
+        S, C->getSubExpr(), Satisfaction,
         std::forward<AtomicEvaluator>(Evaluator));
   }
 
@@ -164,11 +214,35 @@ calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
   ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr);
 
   if (SubstitutedAtomicExpr.isInvalid())
-    return true;
+    return ExprError();
 
   if (!SubstitutedAtomicExpr.isUsable())
     // Evaluator has decided satisfaction without yielding an expression.
-    return false;
+    return ExprEmpty();
+
+  // We don't have the ability to evaluate this, since it contains a
+  // RecoveryExpr, so we want to fail overload resolution.  Otherwise,
+  // we'd potentially pick up a different overload, and cause confusing
+  // diagnostics. SO, add a failure detail that will cause us to make this
+  // overload set not viable.
+  if (SubstitutedAtomicExpr.get()->containsErrors()) {
+    Satisfaction.IsSatisfied = false;
+    Satisfaction.ContainsErrors = true;
+
+    PartialDiagnostic Msg = S.PDiag(diag::note_constraint_references_error);
+    SmallString<128> DiagString;
+    DiagString = ": ";
+    Msg.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(
+        ConstraintExpr,
+        new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
+            SubstitutedAtomicExpr.get()->getBeginLoc(),
+            StringRef(Mem, MessageSize)});
+    return SubstitutedAtomicExpr;
+  }
 
   EnterExpressionEvaluationContext ConstantEvaluated(
       S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
@@ -185,7 +259,7 @@ calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
         << SubstitutedAtomicExpr.get()->getSourceRange();
     for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
       S.Diag(PDiag.first, PDiag.second);
-    return true;
+    return ExprError();
   }
 
   assert(EvalResult.Val.isInt() &&
@@ -195,17 +269,41 @@ calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
     Satisfaction.Details.emplace_back(ConstraintExpr,
                                       SubstitutedAtomicExpr.get());
 
+  return SubstitutedAtomicExpr;
+}
+
+static bool
+DiagRecursiveConstraintEval(Sema &S, llvm::FoldingSetNodeID &ID, const Expr *E,
+                            const MultiLevelTemplateArgumentList &MLTAL) {
+  E->Profile(ID, S.Context, /*Canonical=*/true);
+  for (const auto &List : MLTAL)
+    for (const auto &TemplateArg : List.Args)
+      TemplateArg.Profile(ID, S.Context);
+
+  // Note that we have to do this with our own collection, because there are
+  // times where a constraint-expression check can cause us to need to evaluate
+  // other constriants that are unrelated, such as when evaluating a recovery
+  // expression, or when trying to determine the constexpr-ness of special
+  // members. Otherwise we could just use the
+  // Sema::InstantiatingTemplate::isAlreadyBeingInstantiated function.
+  if (S.SatisfactionStackContains(ID)) {
+    S.Diag(E->getExprLoc(), diag::err_constraint_depends_on_self)
+        << const_cast<Expr *>(E) << E->getSourceRange();
+    return true;
+  }
+
   return false;
 }
 
-static bool calculateConstraintSatisfaction(
-    Sema &S, const NamedDecl *Template, ArrayRef<TemplateArgument> TemplateArgs,
-    SourceLocation TemplateNameLoc, MultiLevelTemplateArgumentList &MLTAL,
-    const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction) {
+static ExprResult calculateConstraintSatisfaction(
+    Sema &S, const NamedDecl *Template, SourceLocation TemplateNameLoc,
+    const MultiLevelTemplateArgumentList &MLTAL, const Expr *ConstraintExpr,
+    ConstraintSatisfaction &Satisfaction) {
   return calculateConstraintSatisfaction(
       S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) {
         EnterExpressionEvaluationContext ConstantEvaluated(
-            S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
+            S, Sema::ExpressionEvaluationContext::ConstantEvaluated,
+            Sema::ReuseLambdaContextDecl);
 
         // Atomic constraint - substitute arguments and check satisfaction.
         ExprResult SubstitutedExpression;
@@ -217,17 +315,21 @@ static bool calculateConstraintSatisfaction(
               AtomicExpr->getSourceRange());
           if (Inst.isInvalid())
             return ExprError();
+
+          llvm::FoldingSetNodeID ID;
+          if (DiagRecursiveConstraintEval(S, ID, AtomicExpr, MLTAL)) {
+            Satisfaction.IsSatisfied = false;
+            Satisfaction.ContainsErrors = true;
+            return ExprEmpty();
+          }
+
+          SatisfactionStackRAII StackRAII(S, ID);
+
           // We do not want error diagnostics escaping here.
           Sema::SFINAETrap Trap(S);
-          SubstitutedExpression = S.SubstExpr(const_cast<Expr *>(AtomicExpr),
-                                              MLTAL);
-          // Substitution might have stripped off a contextual conversion to
-          // bool if this is the operand of an '&&' or '||'. For example, we
-          // might lose an lvalue-to-rvalue conversion here. If so, put it back
-          // before we try to evaluate.
-          if (!SubstitutedExpression.isInvalid())
-            SubstitutedExpression =
-                S.PerformContextuallyConvertToBool(SubstitutedExpression.get());
+          SubstitutedExpression =
+              S.SubstConstraintExpr(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
@@ -264,78 +366,129 @@ static bool calculateConstraintSatisfaction(
         if (!S.CheckConstraintExpression(SubstitutedExpression.get()))
           return ExprError();
 
+        // [temp.constr.atomic]p3: To determine if an atomic constraint is
+        // satisfied, the parameter mapping and template arguments are first
+        // substituted into its expression.  If substitution results in an
+        // invalid type or expression, the constraint is not satisfied.
+        // Otherwise, the lvalue-to-rvalue conversion is performed if necessary,
+        // and E shall be a constant expression of type bool.
+        //
+        // Perform the L to R Value conversion if necessary. We do so for all
+        // non-PRValue categories, else we fail to extend the lifetime of
+        // temporaries, and that fails the constant expression check.
+        if (!SubstitutedExpression.get()->isPRValue())
+          SubstitutedExpression = ImplicitCastExpr::Create(
+              S.Context, SubstitutedExpression.get()->getType(),
+              CK_LValueToRValue, SubstitutedExpression.get(),
+              /*BasePath=*/nullptr, VK_PRValue, FPOptionsOverride());
+
         return SubstitutedExpression;
       });
 }
 
-static bool CheckConstraintSatisfaction(Sema &S, const NamedDecl *Template,
-                                        ArrayRef<const Expr *> ConstraintExprs,
-                                        ArrayRef<TemplateArgument> TemplateArgs,
-                                        SourceRange TemplateIDRange,
-                                        ConstraintSatisfaction &Satisfaction) {
+static bool CheckConstraintSatisfaction(
+    Sema &S, const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
+    llvm::SmallVectorImpl<Expr *> &Converted,
+    const MultiLevelTemplateArgumentList &TemplateArgsLists,
+    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;
-    }
+  if (TemplateArgsLists.isAnyArgInstantiationDependent()) {
+    // No need to check satisfaction for dependent constraint expressions.
+    Satisfaction.IsSatisfied = true;
+    return false;
+  }
 
+  ArrayRef<TemplateArgument> TemplateArgs =
+      TemplateArgsLists.getNumSubstitutedLevels() > 0
+          ? TemplateArgsLists.getOutermost()
+          : ArrayRef<TemplateArgument> {};
   Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
       Sema::InstantiatingTemplate::ConstraintsCheck{},
       const_cast<NamedDecl *>(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))
+    ExprResult Res = calculateConstraintSatisfaction(
+        S, Template, TemplateIDRange.getBegin(), TemplateArgsLists,
+        ConstraintExpr, Satisfaction);
+    if (Res.isInvalid())
       return true;
-    if (!Satisfaction.IsSatisfied)
+
+    Converted.push_back(Res.get());
+    if (!Satisfaction.IsSatisfied) {
+      // Backfill the 'converted' list with nulls so we can keep the Converted
+      // and unconverted lists in sync.
+      Converted.append(ConstraintExprs.size() - Converted.size(), nullptr);
       // [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. [...]
+      // [...] 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(
     const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
-    ArrayRef<TemplateArgument> TemplateArgs, SourceRange TemplateIDRange,
-    ConstraintSatisfaction &OutSatisfaction) {
+    llvm::SmallVectorImpl<Expr *> &ConvertedConstraints,
+    const MultiLevelTemplateArgumentList &TemplateArgsLists,
+    SourceRange TemplateIDRange, ConstraintSatisfaction &OutSatisfaction) {
   if (ConstraintExprs.empty()) {
     OutSatisfaction.IsSatisfied = true;
     return false;
   }
   if (!Template) {
-    return ::CheckConstraintSatisfaction(*this, nullptr, ConstraintExprs,
-                                         TemplateArgs, TemplateIDRange,
-                                         OutSatisfaction);
+    return ::CheckConstraintSatisfaction(
+        *this, nullptr, ConstraintExprs, ConvertedConstraints,
+        TemplateArgsLists, TemplateIDRange, OutSatisfaction);
   }
+
+  // A list of the template argument list flattened in a predictible manner for
+  // the purposes of caching. The ConstraintSatisfaction type is in AST so it
+  // has no access to the MultiLevelTemplateArgumentList, so this has to happen
+  // here.
+  llvm::SmallVector<TemplateArgument, 4> FlattenedArgs;
+  for (auto List : TemplateArgsLists)
+    FlattenedArgs.insert(FlattenedArgs.end(), List.Args.begin(),
+                         List.Args.end());
+
   llvm::FoldingSetNodeID ID;
-  ConstraintSatisfaction::Profile(ID, Context, Template, TemplateArgs);
+  ConstraintSatisfaction::Profile(ID, Context, Template, FlattenedArgs);
   void *InsertPos;
   if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
     OutSatisfaction = *Cached;
     return false;
   }
+
   auto Satisfaction =
-      std::make_unique<ConstraintSatisfaction>(Template, TemplateArgs);
+      std::make_unique<ConstraintSatisfaction>(Template, FlattenedArgs);
   if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
-                                    TemplateArgs, TemplateIDRange,
-                                    *Satisfaction)) {
+                                    ConvertedConstraints, TemplateArgsLists,
+                                    TemplateIDRange, *Satisfaction)) {
+    OutSatisfaction = *Satisfaction;
     return true;
   }
+
+  if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
+    // The evaluation of this constraint resulted in us trying to re-evaluate it
+    // recursively. This isn't really possible, except we try to form a
+    // RecoveryExpr as a part of the evaluation.  If this is the case, just
+    // return the 'cached' version (which will have the same result), and save
+    // ourselves the extra-insert. If it ever becomes possible to legitimately
+    // recursively check a constraint, we should skip checking the 'inner' one
+    // above, and replace the cached version with this one, as it would be more
+    // specific.
+    OutSatisfaction = *Cached;
+    return false;
+  }
+
+  // Else we can simply add this satisfaction to the list.
   OutSatisfaction = *Satisfaction;
   // We cannot use InsertPos here because CheckConstraintSatisfaction might have
   // invalidated it.
@@ -347,21 +500,133 @@ bool Sema::CheckConstraintSatisfaction(
 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
                                        ConstraintSatisfaction &Satisfaction) {
   return calculateConstraintSatisfaction(
-      *this, ConstraintExpr, Satisfaction,
-      [this](const Expr *AtomicExpr) -> ExprResult {
-        // We only do this to immitate lvalue-to-rvalue conversion.
-        return PerformContextuallyConvertToBool(const_cast<Expr *>(AtomicExpr));
-      });
+             *this, ConstraintExpr, Satisfaction,
+             [this](const Expr *AtomicExpr) -> ExprResult {
+               // We only do this to immitate lvalue-to-rvalue conversion.
+               return PerformContextuallyConvertToBool(
+                   const_cast<Expr *>(AtomicExpr));
+             })
+      .isInvalid();
+}
+
+bool Sema::SetupConstraintScope(
+    FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
+    MultiLevelTemplateArgumentList MLTAL, LocalInstantiationScope &Scope) {
+  if (FD->isTemplateInstantiation() && FD->getPrimaryTemplate()) {
+    FunctionTemplateDecl *PrimaryTemplate = FD->getPrimaryTemplate();
+    InstantiatingTemplate Inst(
+        *this, FD->getPointOfInstantiation(),
+        Sema::InstantiatingTemplate::ConstraintsCheck{}, PrimaryTemplate,
+        TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
+        SourceRange());
+    if (Inst.isInvalid())
+      return true;
+
+    // addInstantiatedParametersToScope creates a map of 'uninstantiated' to
+    // 'instantiated' parameters and adds it to the context. For the case where
+    // this function is a template being instantiated NOW, we also need to add
+    // the list of current template arguments to the list so that they also can
+    // be picked out of the map.
+    if (auto *SpecArgs = FD->getTemplateSpecializationArgs()) {
+      MultiLevelTemplateArgumentList JustTemplArgs(FD, SpecArgs->asArray(),
+                                                   /*Final=*/false);
+      if (addInstantiatedParametersToScope(
+              FD, PrimaryTemplate->getTemplatedDecl(), Scope, JustTemplArgs))
+        return true;
+    }
+
+    // If this is a member function, make sure we get the parameters that
+    // reference the original primary template.
+    if (const auto *FromMemTempl =
+            PrimaryTemplate->getInstantiatedFromMemberTemplate()) {
+      if (addInstantiatedParametersToScope(FD, FromMemTempl->getTemplatedDecl(),
+                                           Scope, MLTAL))
+        return true;
+    }
+
+    return false;
+  }
+
+  if (FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization ||
+      FD->getTemplatedKind() == FunctionDecl::TK_DependentNonTemplate) {
+    FunctionDecl *InstantiatedFrom =
+        FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization
+            ? FD->getInstantiatedFromMemberFunction()
+            : FD->getInstantiatedFromDecl();
+
+    InstantiatingTemplate Inst(
+        *this, FD->getPointOfInstantiation(),
+        Sema::InstantiatingTemplate::ConstraintsCheck{}, InstantiatedFrom,
+        TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
+        SourceRange());
+    if (Inst.isInvalid())
+      return true;
+
+    // Case where this was not a template, but instantiated as a
+    // child-function.
+    if (addInstantiatedParametersToScope(FD, InstantiatedFrom, Scope, MLTAL))
+      return true;
+  }
+
+  return false;
+}
+
+// This function collects all of the template arguments for the purposes of
+// constraint-instantiation and checking.
+std::optional<MultiLevelTemplateArgumentList>
+Sema::SetupConstraintCheckingTemplateArgumentsAndScope(
+    FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
+    LocalInstantiationScope &Scope) {
+  MultiLevelTemplateArgumentList MLTAL;
+
+  // Collect the list of template arguments relative to the 'primary' template.
+  // We need the entire list, since the constraint is completely uninstantiated
+  // at this point.
+  MLTAL =
+      getTemplateInstantiationArgs(FD, /*Final=*/false, /*Innermost=*/nullptr,
+                                   /*RelativeToPrimary=*/true,
+                                   /*Pattern=*/nullptr,
+                                   /*ForConstraintInstantiation=*/true);
+  if (SetupConstraintScope(FD, TemplateArgs, MLTAL, Scope))
+    return std::nullopt;
+
+  return MLTAL;
 }
 
 bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
                                     ConstraintSatisfaction &Satisfaction,
-                                    SourceLocation UsageLoc) {
-  const Expr *RC = FD->getTrailingRequiresClause();
-  if (RC->isInstantiationDependent()) {
+                                    SourceLocation UsageLoc,
+                                    bool ForOverloadResolution) {
+  // Don't check constraints if the function is dependent. Also don't check if
+  // this is a function template specialization, as the call to
+  // CheckinstantiatedFunctionTemplateConstraints after this will check it
+  // better.
+  if (FD->isDependentContext() ||
+      FD->getTemplatedKind() ==
+          FunctionDecl::TK_FunctionTemplateSpecialization) {
     Satisfaction.IsSatisfied = true;
     return false;
   }
+
+  DeclContext *CtxToSave = const_cast<FunctionDecl *>(FD);
+
+  while (isLambdaCallOperator(CtxToSave) || FD->isTransparentContext()) {
+    if (isLambdaCallOperator(CtxToSave))
+      CtxToSave = CtxToSave->getParent()->getParent();
+    else
+      CtxToSave = CtxToSave->getNonTransparentContext();
+  }
+
+  ContextRAII SavedContext{*this, CtxToSave};
+  LocalInstantiationScope Scope(*this, !ForOverloadResolution ||
+                                           isLambdaCallOperator(FD));
+  std::optional<MultiLevelTemplateArgumentList> MLTAL =
+      SetupConstraintCheckingTemplateArgumentsAndScope(
+          const_cast<FunctionDecl *>(FD), {}, Scope);
+
+  if (!MLTAL)
+    return true;
+
   Qualifiers ThisQuals;
   CXXRecordDecl *Record = nullptr;
   if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) {
@@ -372,19 +637,124 @@ bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
   // We substitute with empty arguments in order to rebuild the atomic
   // constraint in a constant-evaluated context.
   // FIXME: Should this be a dedicated TreeTransform?
-  return CheckConstraintSatisfaction(
-      FD, {RC}, /*TemplateArgs=*/{},
-      SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
-      Satisfaction);
+  const Expr *RC = FD->getTrailingRequiresClause();
+  llvm::SmallVector<Expr *, 1> Converted;
+
+  if (CheckConstraintSatisfaction(
+          FD, {RC}, Converted, *MLTAL,
+          SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
+          Satisfaction))
+    return true;
+
+  // FIXME: we need to do this for the function constraints for
+  // comparison of constraints to work, but do we also need to do it for
+  // CheckInstantiatedFunctionConstraints?  That one is more difficult, but we
+  // seem to always just pick up the constraints from the primary template.
+  assert(Converted.size() <= 1 && "Got more expressions converted?");
+  if (!Converted.empty() && Converted[0] != nullptr)
+    const_cast<FunctionDecl *>(FD)->setTrailingRequiresClause(Converted[0]);
+  return false;
+}
+
+
+// Figure out the to-translation-unit depth for this function declaration for
+// the purpose of seeing if they differ by constraints. This isn't the same as
+// getTemplateDepth, because it includes already instantiated parents.
+static unsigned
+CalculateTemplateDepthForConstraints(Sema &S, const NamedDecl *ND,
+                                     bool SkipForSpecialization = false) {
+  MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
+      ND, /*Final=*/false, /*Innermost=*/nullptr, /*RelativeToPrimary=*/true,
+      /*Pattern=*/nullptr,
+      /*ForConstraintInstantiation=*/true, SkipForSpecialization);
+  return MLTAL.getNumSubstitutedLevels();
+}
+
+namespace {
+  class AdjustConstraintDepth : public TreeTransform<AdjustConstraintDepth> {
+  unsigned TemplateDepth = 0;
+  public:
+  using inherited = TreeTransform<AdjustConstraintDepth>;
+  AdjustConstraintDepth(Sema &SemaRef, unsigned TemplateDepth)
+      : inherited(SemaRef), TemplateDepth(TemplateDepth) {}
+
+  using inherited::TransformTemplateTypeParmType;
+  QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
+                                         TemplateTypeParmTypeLoc TL, bool) {
+    const TemplateTypeParmType *T = TL.getTypePtr();
+
+    TemplateTypeParmDecl *NewTTPDecl = nullptr;
+    if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())
+      NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(
+          TransformDecl(TL.getNameLoc(), OldTTPDecl));
+
+    QualType Result = getSema().Context.getTemplateTypeParmType(
+        T->getDepth() + TemplateDepth, T->getIndex(), T->isParameterPack(),
+        NewTTPDecl);
+    TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
+    NewTL.setNameLoc(TL.getNameLoc());
+    return Result;
+  }
+  };
+} // namespace
+
+bool Sema::AreConstraintExpressionsEqual(const NamedDecl *Old,
+                                         const Expr *OldConstr,
+                                         const NamedDecl *New,
+                                         const Expr *NewConstr) {
+  if (Old && New && Old != New) {
+    unsigned Depth1 = CalculateTemplateDepthForConstraints(
+        *this, Old);
+    unsigned Depth2 = CalculateTemplateDepthForConstraints(
+        *this, New);
+
+    // Adjust the 'shallowest' verison of this to increase the depth to match
+    // the 'other'.
+    if (Depth2 > Depth1) {
+      OldConstr = AdjustConstraintDepth(*this, Depth2 - Depth1)
+                      .TransformExpr(const_cast<Expr *>(OldConstr))
+                      .get();
+    } else if (Depth1 > Depth2) {
+      NewConstr = AdjustConstraintDepth(*this, Depth1 - Depth2)
+                      .TransformExpr(const_cast<Expr *>(NewConstr))
+                      .get();
+    }
+  }
+
+  llvm::FoldingSetNodeID ID1, ID2;
+  OldConstr->Profile(ID1, Context, /*Canonical=*/true);
+  NewConstr->Profile(ID2, Context, /*Canonical=*/true);
+  return ID1 == ID2;
+}
+
+bool Sema::FriendConstraintsDependOnEnclosingTemplate(const FunctionDecl *FD) {
+  assert(FD->getFriendObjectKind() && "Must be a friend!");
+
+  // The logic for non-templates is handled in ASTContext::isSameEntity, so we
+  // don't have to bother checking 'DependsOnEnclosingTemplate' for a
+  // non-function-template.
+  assert(FD->getDescribedFunctionTemplate() &&
+         "Non-function templates don't need to be checked");
+
+  SmallVector<const Expr *, 3> ACs;
+  FD->getDescribedFunctionTemplate()->getAssociatedConstraints(ACs);
+
+  unsigned OldTemplateDepth = CalculateTemplateDepthForConstraints(*this, FD);
+  for (const Expr *Constraint : ACs)
+    if (ConstraintExpressionDependsOnEnclosingTemplate(FD, OldTemplateDepth,
+                                                       Constraint))
+      return true;
+
+  return false;
 }
 
 bool Sema::EnsureTemplateArgumentListConstraints(
-    TemplateDecl *TD, ArrayRef<TemplateArgument> TemplateArgs,
+    TemplateDecl *TD, const MultiLevelTemplateArgumentList &TemplateArgsLists,
     SourceRange TemplateIDRange) {
   ConstraintSatisfaction Satisfaction;
   llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
   TD->getAssociatedConstraints(AssociatedConstraints);
-  if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgs,
+  if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgsLists,
                                   TemplateIDRange, Satisfaction))
     return true;
 
@@ -392,7 +762,8 @@ bool Sema::EnsureTemplateArgumentListConstraints(
     SmallString<128> TemplateArgString;
     TemplateArgString = " ";
     TemplateArgString += getTemplateArgumentBindingsText(
-        TD->getTemplateParameters(), TemplateArgs.data(), TemplateArgs.size());
+        TD->getTemplateParameters(), TemplateArgsLists.getInnermost().data(),
+        TemplateArgsLists.getInnermost().size());
 
     Diag(TemplateIDRange.getBegin(),
          diag::err_template_arg_list_constraints_not_satisfied)
@@ -424,21 +795,13 @@ bool Sema::CheckInstantiatedFunctionTemplateConstraints(
   Sema::ContextRAII savedContext(*this, Decl);
   LocalInstantiationScope Scope(*this);
 
-  // If this is not an explicit specialization - we need to get the instantiated
-  // version of the template arguments and add them to scope for the
-  // substitution.
-  if (Decl->isTemplateInstantiation()) {
-    InstantiatingTemplate Inst(*this, Decl->getPointOfInstantiation(),
-        InstantiatingTemplate::ConstraintsCheck{}, Decl->getPrimaryTemplate(),
-        TemplateArgs, SourceRange());
-    if (Inst.isInvalid())
-      return true;
-    MultiLevelTemplateArgumentList MLTAL(
-        *Decl->getTemplateSpecializationArgs());
-    if (addInstantiatedParametersToScope(
-            Decl, Decl->getPrimaryTemplate()->getTemplatedDecl(), Scope, MLTAL))
-      return true;
-  }
+  std::optional<MultiLevelTemplateArgumentList> MLTAL =
+      SetupConstraintCheckingTemplateArgumentsAndScope(Decl, TemplateArgs,
+                                                       Scope);
+
+  if (!MLTAL)
+    return true;
+
   Qualifiers ThisQuals;
   CXXRecordDecl *Record = nullptr;
   if (auto *Method = dyn_cast<CXXMethodDecl>(Decl)) {
@@ -446,7 +809,14 @@ bool Sema::CheckInstantiatedFunctionTemplateConstraints(
     Record = Method->getParent();
   }
   CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
-  return CheckConstraintSatisfaction(Template, TemplateAC, TemplateArgs,
+  FunctionScopeRAII FuncScope(*this);
+  if (isLambdaCallOperator(Decl))
+    PushLambdaScope();
+  else
+    FuncScope.disable();
+
+  llvm::SmallVector<Expr *, 1> Converted;
+  return CheckConstraintSatisfaction(Template, TemplateAC, Converted, *MLTAL,
                                      PointOfInstantiation, Satisfaction);
 }
 
@@ -541,31 +911,28 @@ static void diagnoseUnsatisfiedRequirement(Sema &S,
     return;
   }
 }
+static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
+                                                        Expr *SubstExpr,
+                                                        bool First = true);
 
 static void diagnoseUnsatisfiedRequirement(Sema &S,
                                            concepts::NestedRequirement *Req,
                                            bool First) {
-  if (Req->isSubstitutionFailure()) {
-    concepts::Requirement::SubstitutionDiagnostic *SubstDiag =
-        Req->getSubstitutionDiagnostic();
-    if (!SubstDiag->DiagMessage.empty())
-      S.Diag(SubstDiag->DiagLoc,
-             diag::note_nested_requirement_substitution_error)
-             << (int)First << SubstDiag->SubstitutedEntity
-             << SubstDiag->DiagMessage;
+  using SubstitutionDiagnostic = std::pair<SourceLocation, StringRef>;
+  for (auto &Pair : Req->getConstraintSatisfaction()) {
+    if (auto *SubstDiag = Pair.second.dyn_cast<SubstitutionDiagnostic *>())
+      S.Diag(SubstDiag->first, diag::note_nested_requirement_substitution_error)
+          << (int)First << Req->getInvalidConstraintEntity() << SubstDiag->second;
     else
-      S.Diag(SubstDiag->DiagLoc,
-             diag::note_nested_requirement_unknown_substitution_error)
-          << (int)First << SubstDiag->SubstitutedEntity;
-    return;
+      diagnoseWellFormedUnsatisfiedConstraintExpr(
+          S, Pair.second.dyn_cast<Expr *>(), First);
+    First = false;
   }
-  S.DiagnoseUnsatisfiedConstraint(Req->getConstraintSatisfaction(), First);
 }
 
-
 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
                                                         Expr *SubstExpr,
-                                                        bool First = true) {
+                                                        bool First) {
   SubstExpr = SubstExpr->IgnoreParenImpCasts();
   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {
     switch (BO->getOpcode()) {
@@ -645,6 +1012,7 @@ static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
     S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction());
     return;
   } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) {
+    // FIXME: RequiresExpr should store dependent diagnostics.
     for (concepts::Requirement *Req : RE->getRequirements())
       if (!Req->isDependent() && !Req->isSatisfied()) {
         if (auto *E = dyn_cast<concepts::ExprRequirement>(Req))
@@ -721,34 +1089,33 @@ Sema::getNormalizedAssociatedConstraints(
   return CacheEntry->second;
 }
 
-static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
-    ConceptDecl *Concept, ArrayRef<TemplateArgument> TemplateArgs,
-    const ASTTemplateArgumentListInfo *ArgsAsWritten) {
+static bool
+substituteParameterMappings(Sema &S, NormalizedConstraint &N,
+                            ConceptDecl *Concept,
+                            const MultiLevelTemplateArgumentList &MLTAL,
+                            const ASTTemplateArgumentListInfo *ArgsAsWritten) {
   if (!N.isAtomic()) {
-    if (substituteParameterMappings(S, N.getLHS(), Concept, TemplateArgs,
+    if (substituteParameterMappings(S, N.getLHS(), Concept, MLTAL,
                                     ArgsAsWritten))
       return true;
-    return substituteParameterMappings(S, N.getRHS(), Concept, TemplateArgs,
+    return substituteParameterMappings(S, N.getRHS(), Concept, MLTAL,
                                        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()));
+    TemplateArgumentLoc *TempArgs =
+        new (S.Context) TemplateArgumentLoc[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],
+        new (&(TempArgs)[J++])
+            TemplateArgumentLoc(S.getIdentityTemplateArgumentLoc(
+                TemplateParams->begin()[I],
                 // Here we assume we do not support things like
                 // template<typename A, typename B>
                 // concept C = ...;
@@ -757,9 +1124,10 @@ static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
                 // 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()));
+                ArgsAsWritten->NumTemplateArgs > I
+                    ? ArgsAsWritten->arguments()[I].getLocation()
+                    : SourceLocation()));
+    Atomic.ParameterMapping.emplace(TempArgs,  OccurringIndices.count());
   }
   Sema::InstantiatingTemplate Inst(
       S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(),
@@ -768,33 +1136,47 @@ static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
                   ArgsAsWritten->arguments().back().getSourceRange().getEnd()));
   if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs))
     return true;
-  Atomic.ParameterMapping.emplace(
-        MutableArrayRef<TemplateArgumentLoc>(
-            new (S.Context) TemplateArgumentLoc[SubstArgs.size()],
-            SubstArgs.size()));
+
+  TemplateArgumentLoc *TempArgs =
+      new (S.Context) TemplateArgumentLoc[SubstArgs.size()];
   std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(),
-            N.getAtomicConstraint()->ParameterMapping->begin());
+            TempArgs);
+  Atomic.ParameterMapping.emplace(TempArgs, SubstArgs.size());
   return false;
 }
 
-Optional<NormalizedConstraint>
+static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
+                                        const ConceptSpecializationExpr *CSE) {
+  TemplateArgumentList TAL{TemplateArgumentList::OnStack,
+                           CSE->getTemplateArguments()};
+  MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
+      CSE->getNamedConcept(), /*Final=*/false, &TAL,
+      /*RelativeToPrimary=*/true,
+      /*Pattern=*/nullptr,
+      /*ForConstraintInstantiation=*/true);
+
+  return substituteParameterMappings(S, N, CSE->getNamedConcept(), MLTAL,
+                                     CSE->getTemplateArgsAsWritten());
+}
+
+std::optional<NormalizedConstraint>
 NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D,
                                           ArrayRef<const Expr *> E) {
   assert(E.size() != 0);
   auto Conjunction = fromConstraintExpr(S, D, E[0]);
   if (!Conjunction)
-    return None;
+    return std::nullopt;
   for (unsigned I = 1; I < E.size(); ++I) {
     auto Next = fromConstraintExpr(S, D, E[I]);
     if (!Next)
-      return None;
+      return std::nullopt;
     *Conjunction = NormalizedConstraint(S.Context, std::move(*Conjunction),
                                         std::move(*Next), CCK_Conjunction);
   }
   return Conjunction;
 }
 
-llvm::Optional<NormalizedConstraint>
+std::optional<NormalizedConstraint>
 NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
   assert(E != nullptr);
 
@@ -803,13 +1185,19 @@ NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
   // - The normal form of an expression (E) is the normal form of E.
   // [...]
   E = E->IgnoreParenImpCasts();
+
+  // C++2a [temp.param]p4:
+  //     [...] If T is not a pack, then E is E', otherwise E is (E' && ...).
+  // Fold expression is considered atomic constraints per current wording.
+  // See http://cplusplus.github.io/concepts-ts/ts-active.html#28
+
   if (LogicalBinOp BO = E) {
     auto LHS = fromConstraintExpr(S, D, BO.getLHS());
     if (!LHS)
-      return None;
+      return std::nullopt;
     auto RHS = fromConstraintExpr(S, D, BO.getRHS());
     if (!RHS)
-      return None;
+      return std::nullopt;
 
     return NormalizedConstraint(S.Context, std::move(*LHS), std::move(*RHS),
                                 BO.isAnd() ? CCK_Conjunction : CCK_Disjunction);
@@ -833,16 +1221,14 @@ NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
       SubNF = S.getNormalizedAssociatedConstraints(CD,
                                                    {CD->getConstraintExpr()});
       if (!SubNF)
-        return None;
+        return std::nullopt;
     }
 
-    Optional<NormalizedConstraint> New;
+    std::optional<NormalizedConstraint> New;
     New.emplace(S.Context, *SubNF);
 
-    if (substituteParameterMappings(
-            S, *New, CSE->getNamedConcept(),
-            CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten()))
-      return None;
+    if (substituteParameterMappings(S, *New, CSE))
+      return std::nullopt;
 
     return New;
   }
@@ -965,9 +1351,26 @@ static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
   return false;
 }
 
-bool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef<const Expr *> AC1,
-                                  NamedDecl *D2, ArrayRef<const Expr *> AC2,
+bool Sema::IsAtLeastAsConstrained(NamedDecl *D1,
+                                  MutableArrayRef<const Expr *> AC1,
+                                  NamedDecl *D2,
+                                  MutableArrayRef<const Expr *> AC2,
                                   bool &Result) {
+  if (const auto *FD1 = dyn_cast<FunctionDecl>(D1)) {
+    auto IsExpectedEntity = [](const FunctionDecl *FD) {
+      FunctionDecl::TemplatedKind Kind = FD->getTemplatedKind();
+      return Kind == FunctionDecl::TK_NonTemplate ||
+             Kind == FunctionDecl::TK_FunctionTemplate;
+    };
+    const auto *FD2 = dyn_cast<FunctionDecl>(D2);
+    (void)IsExpectedEntity;
+    (void)FD1;
+    (void)FD2;
+    assert(IsExpectedEntity(FD1) && FD2 && IsExpectedEntity(FD2) &&
+           "use non-instantiated function declaration for constraints partial "
+           "ordering");
+  }
+
   if (AC1.empty()) {
     Result = AC2.empty();
     return false;
@@ -985,6 +1388,21 @@ bool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef<const Expr *> AC1,
     return false;
   }
 
+  unsigned Depth1 = CalculateTemplateDepthForConstraints(*this, D1, true);
+  unsigned Depth2 = CalculateTemplateDepthForConstraints(*this, D2, true);
+
+  for (size_t I = 0; I != AC1.size() && I != AC2.size(); ++I) {
+    if (Depth2 > Depth1) {
+      AC1[I] = AdjustConstraintDepth(*this, Depth2 - Depth1)
+                   .TransformExpr(const_cast<Expr *>(AC1[I]))
+                   .get();
+    } else if (Depth1 > Depth2) {
+      AC2[I] = AdjustConstraintDepth(*this, Depth1 - Depth2)
+                   .TransformExpr(const_cast<Expr *>(AC2[I]))
+                   .get();
+    }
+  }
+
   if (subsumes(*this, D1, AC1, D2, AC2, Result,
         [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
           return A.subsumes(Context, B);