clang/lib/Sema/SemaConcept.cpp

   1 //===-- SemaConcept.cpp - Semantic Analysis for Constraints and Concepts --===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file implements semantic analysis for C++ constraints and concepts.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/Sema/SemaConcept.h"
  14 #include "TreeTransform.h"
  15 #include "clang/AST/ASTLambda.h"
  16 #include "clang/AST/DeclCXX.h"
  17 #include "clang/AST/ExprConcepts.h"
  18 #include "clang/Basic/OperatorPrecedence.h"
  19 #include "clang/Sema/EnterExpressionEvaluationContext.h"
  20 #include "clang/Sema/Initialization.h"
  21 #include "clang/Sema/Overload.h"
  22 #include "clang/Sema/ScopeInfo.h"
  23 #include "clang/Sema/Sema.h"
  24 #include "clang/Sema/SemaInternal.h"
  25 #include "clang/Sema/Template.h"
  26 #include "clang/Sema/TemplateDeduction.h"
  27 #include "llvm/ADT/DenseMap.h"
  28 #include "llvm/ADT/PointerUnion.h"
  29 #include "llvm/ADT/StringExtras.h"
  30 #include <optional>
  31
  32 using namespace clang;
  33 using namespace sema;
  34
  35 namespace {
  36 class LogicalBinOp {
  37   SourceLocation Loc;
  38   OverloadedOperatorKind Op = OO_None;
  39   const Expr *LHS = nullptr;
  40   const Expr *RHS = nullptr;
  41
  42 public:
  43   LogicalBinOp(const Expr *E) {
  44     if (auto *BO = dyn_cast<BinaryOperator>(E)) {
  45       Op = BinaryOperator::getOverloadedOperator(BO->getOpcode());
  46       LHS = BO->getLHS();
  47       RHS = BO->getRHS();
  48       Loc = BO->getExprLoc();
  49     } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(E)) {
  50       // If OO is not || or && it might not have exactly 2 arguments.
  51       if (OO->getNumArgs() == 2) {
  52         Op = OO->getOperator();
  53         LHS = OO->getArg(0);
  54         RHS = OO->getArg(1);
  55         Loc = OO->getOperatorLoc();
  56       }
  57     }
  58   }
  59
  60   bool isAnd() const { return Op == OO_AmpAmp; }
  61   bool isOr() const { return Op == OO_PipePipe; }
  62   explicit operator bool() const { return isAnd() || isOr(); }
  63
  64   const Expr *getLHS() const { return LHS; }
  65   const Expr *getRHS() const { return RHS; }
  66   OverloadedOperatorKind getOp() const { return Op; }
  67
  68   ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS) const {
  69     return recreateBinOp(SemaRef, LHS, const_cast<Expr *>(getRHS()));
  70   }
  71
  72   ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS,
  73                            ExprResult RHS) const {
  74     assert((isAnd() || isOr()) && "Not the right kind of op?");
  75     assert((!LHS.isInvalid() && !RHS.isInvalid()) && "not good expressions?");
  76
  77     if (!LHS.isUsable() || !RHS.isUsable())
  78       return ExprEmpty();
  79
  80     // We should just be able to 'normalize' these to the builtin Binary
  81     // Operator, since that is how they are evaluated in constriant checks.
  82     return BinaryOperator::Create(SemaRef.Context, LHS.get(), RHS.get(),
  83                                   BinaryOperator::getOverloadedOpcode(Op),
  84                                   SemaRef.Context.BoolTy, VK_PRValue,
  85                                   OK_Ordinary, Loc, FPOptionsOverride{});
  86   }
  87 };
  88 }
  89
  90 bool Sema::CheckConstraintExpression(const Expr *ConstraintExpression,
  91                                      Token NextToken, bool *PossibleNonPrimary,
  92                                      bool IsTrailingRequiresClause) {
  93   // C++2a [temp.constr.atomic]p1
  94   // ..E shall be a constant expression of type bool.
  95
  96   ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts();
  97
  98   if (LogicalBinOp BO = ConstraintExpression) {
  99     return CheckConstraintExpression(BO.getLHS(), NextToken,
 100                                      PossibleNonPrimary) &&
 101            CheckConstraintExpression(BO.getRHS(), NextToken,
 102                                      PossibleNonPrimary);
 103   } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression))
 104     return CheckConstraintExpression(C->getSubExpr(), NextToken,
 105                                      PossibleNonPrimary);
 106
 107   QualType Type = ConstraintExpression->getType();
 108
 109   auto CheckForNonPrimary = [&] {
 110     if (!PossibleNonPrimary)
 111       return;
 112
 113     *PossibleNonPrimary =
 114         // We have the following case:
 115         // template<typename> requires func(0) struct S { };
 116         // The user probably isn't aware of the parentheses required around
 117         // the function call, and we're only going to parse 'func' as the
 118         // primary-expression, and complain that it is of non-bool type.
 119         //
 120         // However, if we're in a lambda, this might also be:
 121         // []<typename> requires var () {};
 122         // Which also looks like a function call due to the lambda parentheses,
 123         // but unlike the first case, isn't an error, so this check is skipped.
 124         (NextToken.is(tok::l_paren) &&
 125          (IsTrailingRequiresClause ||
 126           (Type->isDependentType() &&
 127            isa<UnresolvedLookupExpr>(ConstraintExpression) &&
 128            !dyn_cast_if_present<LambdaScopeInfo>(getCurFunction())) ||
 129           Type->isFunctionType() ||
 130           Type->isSpecificBuiltinType(BuiltinType::Overload))) ||
 131         // We have the following case:
 132         // template<typename T> requires size_<T> == 0 struct S { };
 133         // The user probably isn't aware of the parentheses required around
 134         // the binary operator, and we're only going to parse 'func' as the
 135         // first operand, and complain that it is of non-bool type.
 136         getBinOpPrecedence(NextToken.getKind(),
 137                            /*GreaterThanIsOperator=*/true,
 138                            getLangOpts().CPlusPlus11) > prec::LogicalAnd;
 139   };
 140
 141   // An atomic constraint!
 142   if (ConstraintExpression->isTypeDependent()) {
 143     CheckForNonPrimary();
 144     return true;
 145   }
 146
 147   if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) {
 148     Diag(ConstraintExpression->getExprLoc(),
 149          diag::err_non_bool_atomic_constraint) << Type
 150         << ConstraintExpression->getSourceRange();
 151     CheckForNonPrimary();
 152     return false;
 153   }
 154
 155   if (PossibleNonPrimary)
 156       *PossibleNonPrimary = false;
 157   return true;
 158 }
 159
 160 namespace {
 161 struct SatisfactionStackRAII {
 162   Sema &SemaRef;
 163   bool Inserted = false;
 164   SatisfactionStackRAII(Sema &SemaRef, const NamedDecl *ND,
 165                         const llvm::FoldingSetNodeID &FSNID)
 166       : SemaRef(SemaRef) {
 167       if (ND) {
 168       SemaRef.PushSatisfactionStackEntry(ND, FSNID);
 169       Inserted = true;
 170       }
 171   }
 172   ~SatisfactionStackRAII() {
 173         if (Inserted)
 174           SemaRef.PopSatisfactionStackEntry();
 175   }
 176 };
 177 } // namespace
 178
 179 template <typename ConstraintEvaluator>
 180 static ExprResult
 181 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
 182                                 ConstraintSatisfaction &Satisfaction,
 183                                 const ConstraintEvaluator &Evaluator);
 184
 185 template <typename ConstraintEvaluator>
 186 static ExprResult
 187 calculateConstraintSatisfaction(Sema &S, const Expr *LHS,
 188                                 OverloadedOperatorKind Op, const Expr *RHS,
 189                                 ConstraintSatisfaction &Satisfaction,
 190                                 const ConstraintEvaluator &Evaluator) {
 191   size_t EffectiveDetailEndIndex = Satisfaction.Details.size();
 192
 193   ExprResult LHSRes =
 194       calculateConstraintSatisfaction(S, LHS, Satisfaction, Evaluator);
 195
 196   if (LHSRes.isInvalid())
 197     return ExprError();
 198
 199   bool IsLHSSatisfied = Satisfaction.IsSatisfied;
 200
 201   if (Op == clang::OO_PipePipe && IsLHSSatisfied)
 202     // [temp.constr.op] p3
 203     //    A disjunction is a constraint taking two operands. To determine if
 204     //    a disjunction is satisfied, the satisfaction of the first operand
 205     //    is checked. If that is satisfied, the disjunction is satisfied.
 206     //    Otherwise, the disjunction is satisfied if and only if the second
 207     //    operand is satisfied.
 208     // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
 209     return LHSRes;
 210
 211   if (Op == clang::OO_AmpAmp && !IsLHSSatisfied)
 212     // [temp.constr.op] p2
 213     //    A conjunction is a constraint taking two operands. To determine if
 214     //    a conjunction is satisfied, the satisfaction of the first operand
 215     //    is checked. If that is not satisfied, the conjunction is not
 216     //    satisfied. Otherwise, the conjunction is satisfied if and only if
 217     //    the second operand is satisfied.
 218     // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
 219     return LHSRes;
 220
 221   ExprResult RHSRes =
 222       calculateConstraintSatisfaction(S, RHS, Satisfaction, Evaluator);
 223   if (RHSRes.isInvalid())
 224     return ExprError();
 225
 226   bool IsRHSSatisfied = Satisfaction.IsSatisfied;
 227   // Current implementation adds diagnostic information about the falsity
 228   // of each false atomic constraint expression when it evaluates them.
 229   // When the evaluation results to `false || true`, the information
 230   // generated during the evaluation of left-hand side is meaningless
 231   // because the whole expression evaluates to true.
 232   // The following code removes the irrelevant diagnostic information.
 233   // FIXME: We should probably delay the addition of diagnostic information
 234   // until we know the entire expression is false.
 235   if (Op == clang::OO_PipePipe && IsRHSSatisfied) {
 236     auto EffectiveDetailEnd = Satisfaction.Details.begin();
 237     std::advance(EffectiveDetailEnd, EffectiveDetailEndIndex);
 238     Satisfaction.Details.erase(EffectiveDetailEnd, Satisfaction.Details.end());
 239   }
 240
 241   if (!LHSRes.isUsable() || !RHSRes.isUsable())
 242     return ExprEmpty();
 243
 244   return BinaryOperator::Create(S.Context, LHSRes.get(), RHSRes.get(),
 245                                 BinaryOperator::getOverloadedOpcode(Op),
 246                                 S.Context.BoolTy, VK_PRValue, OK_Ordinary,
 247                                 LHS->getBeginLoc(), FPOptionsOverride{});
 248 }
 249
 250 template <typename ConstraintEvaluator>
 251 static ExprResult
 252 calculateConstraintSatisfaction(Sema &S, const CXXFoldExpr *FE,
 253                                 ConstraintSatisfaction &Satisfaction,
 254                                 const ConstraintEvaluator &Evaluator) {
 255   bool Conjunction = FE->getOperator() == BinaryOperatorKind::BO_LAnd;
 256   size_t EffectiveDetailEndIndex = Satisfaction.Details.size();
 257
 258   ExprResult Out;
 259   if (FE->isLeftFold() && FE->getInit()) {
 260     Out = calculateConstraintSatisfaction(S, FE->getInit(), Satisfaction,
 261                                           Evaluator);
 262     if (Out.isInvalid())
 263       return ExprError();
 264
 265     // If the first clause of a conjunction is not satisfied,
 266     // or if the first clause of a disjection is satisfied,
 267     // we have established satisfaction of the whole constraint
 268     // and we should not continue further.
 269     if (Conjunction != Satisfaction.IsSatisfied)
 270       return Out;
 271   }
 272   std::optional<unsigned> NumExpansions =
 273       Evaluator.EvaluateFoldExpandedConstraintSize(FE);
 274   if (!NumExpansions)
 275     return ExprError();
 276   for (unsigned I = 0; I < *NumExpansions; I++) {
 277     Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(S, I);
 278     ExprResult Res = calculateConstraintSatisfaction(S, FE->getPattern(),
 279                                                      Satisfaction, Evaluator);
 280     if (Res.isInvalid())
 281       return ExprError();
 282     bool IsRHSSatisfied = Satisfaction.IsSatisfied;
 283     if (!Conjunction && IsRHSSatisfied) {
 284       auto EffectiveDetailEnd = Satisfaction.Details.begin();
 285       std::advance(EffectiveDetailEnd, EffectiveDetailEndIndex);
 286       Satisfaction.Details.erase(EffectiveDetailEnd,
 287                                  Satisfaction.Details.end());
 288     }
 289     if (Out.isUnset())
 290       Out = Res;
 291     else if (!Res.isUnset()) {
 292       Out = BinaryOperator::Create(
 293           S.Context, Out.get(), Res.get(), FE->getOperator(), S.Context.BoolTy,
 294           VK_PRValue, OK_Ordinary, FE->getBeginLoc(), FPOptionsOverride{});
 295     }
 296     if (Conjunction != IsRHSSatisfied)
 297       return Out;
 298   }
 299
 300   if (FE->isRightFold() && FE->getInit()) {
 301     ExprResult Res = calculateConstraintSatisfaction(S, FE->getInit(),
 302                                                      Satisfaction, Evaluator);
 303     if (Out.isInvalid())
 304       return ExprError();
 305
 306     if (Out.isUnset())
 307       Out = Res;
 308     else if (!Res.isUnset()) {
 309       Out = BinaryOperator::Create(
 310           S.Context, Out.get(), Res.get(), FE->getOperator(), S.Context.BoolTy,
 311           VK_PRValue, OK_Ordinary, FE->getBeginLoc(), FPOptionsOverride{});
 312     }
 313   }
 314
 315   if (Out.isUnset()) {
 316     Satisfaction.IsSatisfied = Conjunction;
 317     Out = S.BuildEmptyCXXFoldExpr(FE->getBeginLoc(), FE->getOperator());
 318   }
 319   return Out;
 320 }
 321
 322 template <typename ConstraintEvaluator>
 323 static ExprResult
 324 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
 325                                 ConstraintSatisfaction &Satisfaction,
 326                                 const ConstraintEvaluator &Evaluator) {
 327   ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
 328
 329   if (LogicalBinOp BO = ConstraintExpr)
 330     return calculateConstraintSatisfaction(
 331         S, BO.getLHS(), BO.getOp(), BO.getRHS(), Satisfaction, Evaluator);
 332
 333   if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) {
 334     // These aren't evaluated, so we don't care about cleanups, so we can just
 335     // evaluate these as if the cleanups didn't exist.
 336     return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction,
 337                                            Evaluator);
 338   }
 339
 340   if (auto *FE = dyn_cast<CXXFoldExpr>(ConstraintExpr);
 341       FE && S.getLangOpts().CPlusPlus26 &&
 342       (FE->getOperator() == BinaryOperatorKind::BO_LAnd ||
 343        FE->getOperator() == BinaryOperatorKind::BO_LOr)) {
 344     return calculateConstraintSatisfaction(S, FE, Satisfaction, Evaluator);
 345   }
 346
 347   // An atomic constraint expression
 348   ExprResult SubstitutedAtomicExpr =
 349       Evaluator.EvaluateAtomicConstraint(ConstraintExpr);
 350
 351   if (SubstitutedAtomicExpr.isInvalid())
 352     return ExprError();
 353
 354   if (!SubstitutedAtomicExpr.isUsable())
 355     // Evaluator has decided satisfaction without yielding an expression.
 356     return ExprEmpty();
 357
 358   // We don't have the ability to evaluate this, since it contains a
 359   // RecoveryExpr, so we want to fail overload resolution.  Otherwise,
 360   // we'd potentially pick up a different overload, and cause confusing
 361   // diagnostics. SO, add a failure detail that will cause us to make this
 362   // overload set not viable.
 363   if (SubstitutedAtomicExpr.get()->containsErrors()) {
 364     Satisfaction.IsSatisfied = false;
 365     Satisfaction.ContainsErrors = true;
 366
 367     PartialDiagnostic Msg = S.PDiag(diag::note_constraint_references_error);
 368     SmallString<128> DiagString;
 369     DiagString = ": ";
 370     Msg.EmitToString(S.getDiagnostics(), DiagString);
 371     unsigned MessageSize = DiagString.size();
 372     char *Mem = new (S.Context) char[MessageSize];
 373     memcpy(Mem, DiagString.c_str(), MessageSize);
 374     Satisfaction.Details.emplace_back(
 375         new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
 376             SubstitutedAtomicExpr.get()->getBeginLoc(),
 377             StringRef(Mem, MessageSize)});
 378     return SubstitutedAtomicExpr;
 379   }
 380
 381   EnterExpressionEvaluationContext ConstantEvaluated(
 382       S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
 383   SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;
 384   Expr::EvalResult EvalResult;
 385   EvalResult.Diag = &EvaluationDiags;
 386   if (!SubstitutedAtomicExpr.get()->EvaluateAsConstantExpr(EvalResult,
 387                                                            S.Context) ||
 388       !EvaluationDiags.empty()) {
 389     // C++2a [temp.constr.atomic]p1
 390     //   ...E shall be a constant expression of type bool.
 391     S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(),
 392            diag::err_non_constant_constraint_expression)
 393         << SubstitutedAtomicExpr.get()->getSourceRange();
 394     for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
 395       S.Diag(PDiag.first, PDiag.second);
 396     return ExprError();
 397   }
 398
 399   assert(EvalResult.Val.isInt() &&
 400          "evaluating bool expression didn't produce int");
 401   Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
 402   if (!Satisfaction.IsSatisfied)
 403     Satisfaction.Details.emplace_back(SubstitutedAtomicExpr.get());
 404
 405   return SubstitutedAtomicExpr;
 406 }
 407
 408 static bool
 409 DiagRecursiveConstraintEval(Sema &S, llvm::FoldingSetNodeID &ID,
 410                             const NamedDecl *Templ, const Expr *E,
 411                             const MultiLevelTemplateArgumentList &MLTAL) {
 412   E->Profile(ID, S.Context, /*Canonical=*/true);
 413   for (const auto &List : MLTAL)
 414     for (const auto &TemplateArg : List.Args)
 415       TemplateArg.Profile(ID, S.Context);
 416
 417   // Note that we have to do this with our own collection, because there are
 418   // times where a constraint-expression check can cause us to need to evaluate
 419   // other constriants that are unrelated, such as when evaluating a recovery
 420   // expression, or when trying to determine the constexpr-ness of special
 421   // members. Otherwise we could just use the
 422   // Sema::InstantiatingTemplate::isAlreadyBeingInstantiated function.
 423   if (S.SatisfactionStackContains(Templ, ID)) {
 424     S.Diag(E->getExprLoc(), diag::err_constraint_depends_on_self)
 425         << const_cast<Expr *>(E) << E->getSourceRange();
 426     return true;
 427   }
 428
 429   return false;
 430 }
 431
 432 static ExprResult calculateConstraintSatisfaction(
 433     Sema &S, const NamedDecl *Template, SourceLocation TemplateNameLoc,
 434     const MultiLevelTemplateArgumentList &MLTAL, const Expr *ConstraintExpr,
 435     ConstraintSatisfaction &Satisfaction) {
 436
 437   struct ConstraintEvaluator {
 438     Sema &S;
 439     const NamedDecl *Template;
 440     SourceLocation TemplateNameLoc;
 441     const MultiLevelTemplateArgumentList &MLTAL;
 442     ConstraintSatisfaction &Satisfaction;
 443
 444     ExprResult EvaluateAtomicConstraint(const Expr *AtomicExpr) const {
 445       EnterExpressionEvaluationContext ConstantEvaluated(
 446           S, Sema::ExpressionEvaluationContext::ConstantEvaluated,
 447           Sema::ReuseLambdaContextDecl);
 448
 449       // Atomic constraint - substitute arguments and check satisfaction.
 450       ExprResult SubstitutedExpression;
 451       {
 452         TemplateDeductionInfo Info(TemplateNameLoc);
 453         Sema::InstantiatingTemplate Inst(
 454             S, AtomicExpr->getBeginLoc(),
 455             Sema::InstantiatingTemplate::ConstraintSubstitution{},
 456             const_cast<NamedDecl *>(Template), Info,
 457             AtomicExpr->getSourceRange());
 458         if (Inst.isInvalid())
 459           return ExprError();
 460
 461         llvm::FoldingSetNodeID ID;
 462         if (Template &&
 463             DiagRecursiveConstraintEval(S, ID, Template, AtomicExpr, MLTAL)) {
 464           Satisfaction.IsSatisfied = false;
 465           Satisfaction.ContainsErrors = true;
 466           return ExprEmpty();
 467         }
 468
 469         SatisfactionStackRAII StackRAII(S, Template, ID);
 470
 471         // We do not want error diagnostics escaping here.
 472         Sema::SFINAETrap Trap(S);
 473         SubstitutedExpression =
 474             S.SubstConstraintExpr(const_cast<Expr *>(AtomicExpr), MLTAL);
 475
 476         if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
 477           // C++2a [temp.constr.atomic]p1
 478           //   ...If substitution results in an invalid type or expression, the
 479           //   constraint is not satisfied.
 480           if (!Trap.hasErrorOccurred())
 481             // A non-SFINAE error has occurred as a result of this
 482             // substitution.
 483             return ExprError();
 484
 485           PartialDiagnosticAt SubstDiag{SourceLocation(),
 486                                         PartialDiagnostic::NullDiagnostic()};
 487           Info.takeSFINAEDiagnostic(SubstDiag);
 488           // FIXME: Concepts: This is an unfortunate consequence of there
 489           //  being no serialization code for PartialDiagnostics and the fact
 490           //  that serializing them would likely take a lot more storage than
 491           //  just storing them as strings. We would still like, in the
 492           //  future, to serialize the proper PartialDiagnostic as serializing
 493           //  it as a string defeats the purpose of the diagnostic mechanism.
 494           SmallString<128> DiagString;
 495           DiagString = ": ";
 496           SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString);
 497           unsigned MessageSize = DiagString.size();
 498           char *Mem = new (S.Context) char[MessageSize];
 499           memcpy(Mem, DiagString.c_str(), MessageSize);
 500           Satisfaction.Details.emplace_back(
 501               new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
 502                   SubstDiag.first, StringRef(Mem, MessageSize)});
 503           Satisfaction.IsSatisfied = false;
 504           return ExprEmpty();
 505         }
 506       }
 507
 508       if (!S.CheckConstraintExpression(SubstitutedExpression.get()))
 509         return ExprError();
 510
 511       // [temp.constr.atomic]p3: To determine if an atomic constraint is
 512       // satisfied, the parameter mapping and template arguments are first
 513       // substituted into its expression.  If substitution results in an
 514       // invalid type or expression, the constraint is not satisfied.
 515       // Otherwise, the lvalue-to-rvalue conversion is performed if necessary,
 516       // and E shall be a constant expression of type bool.
 517       //
 518       // Perform the L to R Value conversion if necessary. We do so for all
 519       // non-PRValue categories, else we fail to extend the lifetime of
 520       // temporaries, and that fails the constant expression check.
 521       if (!SubstitutedExpression.get()->isPRValue())
 522         SubstitutedExpression = ImplicitCastExpr::Create(
 523             S.Context, SubstitutedExpression.get()->getType(),
 524             CK_LValueToRValue, SubstitutedExpression.get(),
 525             /*BasePath=*/nullptr, VK_PRValue, FPOptionsOverride());
 526
 527       return SubstitutedExpression;
 528     }
 529
 530     std::optional<unsigned>
 531     EvaluateFoldExpandedConstraintSize(const CXXFoldExpr *FE) const {
 532
 533       // We should ignore errors in the presence of packs of different size.
 534       Sema::SFINAETrap Trap(S);
 535
 536       Expr *Pattern = FE->getPattern();
 537
 538       SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 539       S.collectUnexpandedParameterPacks(Pattern, Unexpanded);
 540       assert(!Unexpanded.empty() && "Pack expansion without parameter packs?");
 541       bool Expand = true;
 542       bool RetainExpansion = false;
 543       std::optional<unsigned> OrigNumExpansions = FE->getNumExpansions(),
 544                               NumExpansions = OrigNumExpansions;
 545       if (S.CheckParameterPacksForExpansion(
 546               FE->getEllipsisLoc(), Pattern->getSourceRange(), Unexpanded,
 547               MLTAL, Expand, RetainExpansion, NumExpansions) ||
 548           !Expand || RetainExpansion)
 549         return std::nullopt;
 550
 551       if (NumExpansions && S.getLangOpts().BracketDepth < NumExpansions) {
 552         S.Diag(FE->getEllipsisLoc(),
 553                clang::diag::err_fold_expression_limit_exceeded)
 554             << *NumExpansions << S.getLangOpts().BracketDepth
 555             << FE->getSourceRange();
 556         S.Diag(FE->getEllipsisLoc(), diag::note_bracket_depth);
 557         return std::nullopt;
 558       }
 559       return NumExpansions;
 560     }
 561   };
 562
 563   return calculateConstraintSatisfaction(
 564       S, ConstraintExpr, Satisfaction,
 565       ConstraintEvaluator{S, Template, TemplateNameLoc, MLTAL, Satisfaction});
 566 }
 567
 568 static bool CheckConstraintSatisfaction(
 569     Sema &S, const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
 570     llvm::SmallVectorImpl<Expr *> &Converted,
 571     const MultiLevelTemplateArgumentList &TemplateArgsLists,
 572     SourceRange TemplateIDRange, ConstraintSatisfaction &Satisfaction) {
 573   if (ConstraintExprs.empty()) {
 574     Satisfaction.IsSatisfied = true;
 575     return false;
 576   }
 577
 578   if (TemplateArgsLists.isAnyArgInstantiationDependent()) {
 579     // No need to check satisfaction for dependent constraint expressions.
 580     Satisfaction.IsSatisfied = true;
 581     return false;
 582   }
 583
 584   ArrayRef<TemplateArgument> TemplateArgs =
 585       TemplateArgsLists.getNumSubstitutedLevels() > 0
 586           ? TemplateArgsLists.getOutermost()
 587           : ArrayRef<TemplateArgument>{};
 588   Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
 589       Sema::InstantiatingTemplate::ConstraintsCheck{},
 590       const_cast<NamedDecl *>(Template), TemplateArgs, TemplateIDRange);
 591   if (Inst.isInvalid())
 592     return true;
 593
 594   for (const Expr *ConstraintExpr : ConstraintExprs) {
 595     ExprResult Res = calculateConstraintSatisfaction(
 596         S, Template, TemplateIDRange.getBegin(), TemplateArgsLists,
 597         ConstraintExpr, Satisfaction);
 598     if (Res.isInvalid())
 599       return true;
 600
 601     Converted.push_back(Res.get());
 602     if (!Satisfaction.IsSatisfied) {
 603       // Backfill the 'converted' list with nulls so we can keep the Converted
 604       // and unconverted lists in sync.
 605       Converted.append(ConstraintExprs.size() - Converted.size(), nullptr);
 606       // [temp.constr.op] p2
 607       // [...] To determine if a conjunction is satisfied, the satisfaction
 608       // of the first operand is checked. If that is not satisfied, the
 609       // conjunction is not satisfied. [...]
 610       return false;
 611     }
 612   }
 613   return false;
 614 }
 615
 616 bool Sema::CheckConstraintSatisfaction(
 617     const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
 618     llvm::SmallVectorImpl<Expr *> &ConvertedConstraints,
 619     const MultiLevelTemplateArgumentList &TemplateArgsLists,
 620     SourceRange TemplateIDRange, ConstraintSatisfaction &OutSatisfaction) {
 621   if (ConstraintExprs.empty()) {
 622     OutSatisfaction.IsSatisfied = true;
 623     return false;
 624   }
 625   if (!Template) {
 626     return ::CheckConstraintSatisfaction(
 627         *this, nullptr, ConstraintExprs, ConvertedConstraints,
 628         TemplateArgsLists, TemplateIDRange, OutSatisfaction);
 629   }
 630   // Invalid templates could make their way here. Substituting them could result
 631   // in dependent expressions.
 632   if (Template->isInvalidDecl()) {
 633     OutSatisfaction.IsSatisfied = false;
 634     return true;
 635   }
 636
 637   // A list of the template argument list flattened in a predictible manner for
 638   // the purposes of caching. The ConstraintSatisfaction type is in AST so it
 639   // has no access to the MultiLevelTemplateArgumentList, so this has to happen
 640   // here.
 641   llvm::SmallVector<TemplateArgument, 4> FlattenedArgs;
 642   for (auto List : TemplateArgsLists)
 643     FlattenedArgs.insert(FlattenedArgs.end(), List.Args.begin(),
 644                          List.Args.end());
 645
 646   llvm::FoldingSetNodeID ID;
 647   ConstraintSatisfaction::Profile(ID, Context, Template, FlattenedArgs);
 648   void *InsertPos;
 649   if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
 650     OutSatisfaction = *Cached;
 651     return false;
 652   }
 653
 654   auto Satisfaction =
 655       std::make_unique<ConstraintSatisfaction>(Template, FlattenedArgs);
 656   if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
 657                                     ConvertedConstraints, TemplateArgsLists,
 658                                     TemplateIDRange, *Satisfaction)) {
 659     OutSatisfaction = *Satisfaction;
 660     return true;
 661   }
 662
 663   if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
 664     // The evaluation of this constraint resulted in us trying to re-evaluate it
 665     // recursively. This isn't really possible, except we try to form a
 666     // RecoveryExpr as a part of the evaluation.  If this is the case, just
 667     // return the 'cached' version (which will have the same result), and save
 668     // ourselves the extra-insert. If it ever becomes possible to legitimately
 669     // recursively check a constraint, we should skip checking the 'inner' one
 670     // above, and replace the cached version with this one, as it would be more
 671     // specific.
 672     OutSatisfaction = *Cached;
 673     return false;
 674   }
 675
 676   // Else we can simply add this satisfaction to the list.
 677   OutSatisfaction = *Satisfaction;
 678   // We cannot use InsertPos here because CheckConstraintSatisfaction might have
 679   // invalidated it.
 680   // Note that entries of SatisfactionCache are deleted in Sema's destructor.
 681   SatisfactionCache.InsertNode(Satisfaction.release());
 682   return false;
 683 }
 684
 685 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
 686                                        ConstraintSatisfaction &Satisfaction) {
 687
 688   struct ConstraintEvaluator {
 689     Sema &S;
 690     ExprResult EvaluateAtomicConstraint(const Expr *AtomicExpr) const {
 691       return S.PerformContextuallyConvertToBool(const_cast<Expr *>(AtomicExpr));
 692     }
 693
 694     std::optional<unsigned>
 695     EvaluateFoldExpandedConstraintSize(const CXXFoldExpr *FE) const {
 696       return 0;
 697     }
 698   };
 699
 700   return calculateConstraintSatisfaction(*this, ConstraintExpr, Satisfaction,
 701                                          ConstraintEvaluator{*this})
 702       .isInvalid();
 703 }
 704
 705 bool Sema::addInstantiatedCapturesToScope(
 706     FunctionDecl *Function, const FunctionDecl *PatternDecl,
 707     LocalInstantiationScope &Scope,
 708     const MultiLevelTemplateArgumentList &TemplateArgs) {
 709   const auto *LambdaClass = cast<CXXMethodDecl>(Function)->getParent();
 710   const auto *LambdaPattern = cast<CXXMethodDecl>(PatternDecl)->getParent();
 711
 712   unsigned Instantiated = 0;
 713
 714   auto AddSingleCapture = [&](const ValueDecl *CapturedPattern,
 715                               unsigned Index) {
 716     ValueDecl *CapturedVar = LambdaClass->getCapture(Index)->getCapturedVar();
 717     assert(CapturedVar->isInitCapture());
 718     Scope.InstantiatedLocal(CapturedPattern, CapturedVar);
 719   };
 720
 721   for (const LambdaCapture &CapturePattern : LambdaPattern->captures()) {
 722     if (!CapturePattern.capturesVariable()) {
 723       Instantiated++;
 724       continue;
 725     }
 726     ValueDecl *CapturedPattern = CapturePattern.getCapturedVar();
 727
 728     if (!CapturedPattern->isInitCapture()) {
 729       Instantiated++;
 730       continue;
 731     }
 732
 733     if (!CapturedPattern->isParameterPack()) {
 734       AddSingleCapture(CapturedPattern, Instantiated++);
 735     } else {
 736       Scope.MakeInstantiatedLocalArgPack(CapturedPattern);
 737       SmallVector<UnexpandedParameterPack, 2> Unexpanded;
 738       SemaRef.collectUnexpandedParameterPacks(
 739           dyn_cast<VarDecl>(CapturedPattern)->getInit(), Unexpanded);
 740       auto NumArgumentsInExpansion =
 741           getNumArgumentsInExpansionFromUnexpanded(Unexpanded, TemplateArgs);
 742       if (!NumArgumentsInExpansion)
 743         continue;
 744       for (unsigned Arg = 0; Arg < *NumArgumentsInExpansion; ++Arg)
 745         AddSingleCapture(CapturedPattern, Instantiated++);
 746     }
 747   }
 748   return false;
 749 }
 750
 751 bool Sema::SetupConstraintScope(
 752     FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
 753     const MultiLevelTemplateArgumentList &MLTAL,
 754     LocalInstantiationScope &Scope) {
 755   if (FD->isTemplateInstantiation() && FD->getPrimaryTemplate()) {
 756     FunctionTemplateDecl *PrimaryTemplate = FD->getPrimaryTemplate();
 757     InstantiatingTemplate Inst(
 758         *this, FD->getPointOfInstantiation(),
 759         Sema::InstantiatingTemplate::ConstraintsCheck{}, PrimaryTemplate,
 760         TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
 761         SourceRange());
 762     if (Inst.isInvalid())
 763       return true;
 764
 765     // addInstantiatedParametersToScope creates a map of 'uninstantiated' to
 766     // 'instantiated' parameters and adds it to the context. For the case where
 767     // this function is a template being instantiated NOW, we also need to add
 768     // the list of current template arguments to the list so that they also can
 769     // be picked out of the map.
 770     if (auto *SpecArgs = FD->getTemplateSpecializationArgs()) {
 771       MultiLevelTemplateArgumentList JustTemplArgs(FD, SpecArgs->asArray(),
 772                                                    /*Final=*/false);
 773       if (addInstantiatedParametersToScope(
 774               FD, PrimaryTemplate->getTemplatedDecl(), Scope, JustTemplArgs))
 775         return true;
 776     }
 777
 778     // If this is a member function, make sure we get the parameters that
 779     // reference the original primary template.
 780     // We walk up the instantiated template chain so that nested lambdas get
 781     // handled properly.
 782     // We should only collect instantiated parameters from the primary template.
 783     // Otherwise, we may have mismatched template parameter depth!
 784     if (FunctionTemplateDecl *FromMemTempl =
 785             PrimaryTemplate->getInstantiatedFromMemberTemplate()) {
 786       while (FromMemTempl->getInstantiatedFromMemberTemplate())
 787         FromMemTempl = FromMemTempl->getInstantiatedFromMemberTemplate();
 788       if (addInstantiatedParametersToScope(FD, FromMemTempl->getTemplatedDecl(),
 789                                            Scope, MLTAL))
 790         return true;
 791     }
 792
 793     return false;
 794   }
 795
 796   if (FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization ||
 797       FD->getTemplatedKind() == FunctionDecl::TK_DependentNonTemplate) {
 798     FunctionDecl *InstantiatedFrom =
 799         FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization
 800             ? FD->getInstantiatedFromMemberFunction()
 801             : FD->getInstantiatedFromDecl();
 802
 803     InstantiatingTemplate Inst(
 804         *this, FD->getPointOfInstantiation(),
 805         Sema::InstantiatingTemplate::ConstraintsCheck{}, InstantiatedFrom,
 806         TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
 807         SourceRange());
 808     if (Inst.isInvalid())
 809       return true;
 810
 811     // Case where this was not a template, but instantiated as a
 812     // child-function.
 813     if (addInstantiatedParametersToScope(FD, InstantiatedFrom, Scope, MLTAL))
 814       return true;
 815   }
 816
 817   return false;
 818 }
 819
 820 // This function collects all of the template arguments for the purposes of
 821 // constraint-instantiation and checking.
 822 std::optional<MultiLevelTemplateArgumentList>
 823 Sema::SetupConstraintCheckingTemplateArgumentsAndScope(
 824     FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
 825     LocalInstantiationScope &Scope) {
 826   MultiLevelTemplateArgumentList MLTAL;
 827
 828   // Collect the list of template arguments relative to the 'primary' template.
 829   // We need the entire list, since the constraint is completely uninstantiated
 830   // at this point.
 831   MLTAL =
 832       getTemplateInstantiationArgs(FD, FD->getLexicalDeclContext(),
 833                                    /*Final=*/false, /*Innermost=*/std::nullopt,
 834                                    /*RelativeToPrimary=*/true,
 835                                    /*Pattern=*/nullptr,
 836                                    /*ForConstraintInstantiation=*/true);
 837   if (SetupConstraintScope(FD, TemplateArgs, MLTAL, Scope))
 838     return std::nullopt;
 839
 840   return MLTAL;
 841 }
 842
 843 bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
 844                                     ConstraintSatisfaction &Satisfaction,
 845                                     SourceLocation UsageLoc,
 846                                     bool ForOverloadResolution) {
 847   // Don't check constraints if the function is dependent. Also don't check if
 848   // this is a function template specialization, as the call to
 849   // CheckinstantiatedFunctionTemplateConstraints after this will check it
 850   // better.
 851   if (FD->isDependentContext() ||
 852       FD->getTemplatedKind() ==
 853           FunctionDecl::TK_FunctionTemplateSpecialization) {
 854     Satisfaction.IsSatisfied = true;
 855     return false;
 856   }
 857
 858   // A lambda conversion operator has the same constraints as the call operator
 859   // and constraints checking relies on whether we are in a lambda call operator
 860   // (and may refer to its parameters), so check the call operator instead.
 861   // Note that the declarations outside of the lambda should also be
 862   // considered. Turning on the 'ForOverloadResolution' flag results in the
 863   // LocalInstantiationScope not looking into its parents, but we can still
 864   // access Decls from the parents while building a lambda RAII scope later.
 865   if (const auto *MD = dyn_cast<CXXConversionDecl>(FD);
 866       MD && isLambdaConversionOperator(const_cast<CXXConversionDecl *>(MD)))
 867     return CheckFunctionConstraints(MD->getParent()->getLambdaCallOperator(),
 868                                     Satisfaction, UsageLoc,
 869                                     /*ShouldAddDeclsFromParentScope=*/true);
 870
 871   DeclContext *CtxToSave = const_cast<FunctionDecl *>(FD);
 872
 873   while (isLambdaCallOperator(CtxToSave) || FD->isTransparentContext()) {
 874     if (isLambdaCallOperator(CtxToSave))
 875       CtxToSave = CtxToSave->getParent()->getParent();
 876     else
 877       CtxToSave = CtxToSave->getNonTransparentContext();
 878   }
 879
 880   ContextRAII SavedContext{*this, CtxToSave};
 881   LocalInstantiationScope Scope(*this, !ForOverloadResolution);
 882   std::optional<MultiLevelTemplateArgumentList> MLTAL =
 883       SetupConstraintCheckingTemplateArgumentsAndScope(
 884           const_cast<FunctionDecl *>(FD), {}, Scope);
 885
 886   if (!MLTAL)
 887     return true;
 888
 889   Qualifiers ThisQuals;
 890   CXXRecordDecl *Record = nullptr;
 891   if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) {
 892     ThisQuals = Method->getMethodQualifiers();
 893     Record = const_cast<CXXRecordDecl *>(Method->getParent());
 894   }
 895   CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
 896
 897   LambdaScopeForCallOperatorInstantiationRAII LambdaScope(
 898       *this, const_cast<FunctionDecl *>(FD), *MLTAL, Scope,
 899       ForOverloadResolution);
 900
 901   return CheckConstraintSatisfaction(
 902       FD, {FD->getTrailingRequiresClause()}, *MLTAL,
 903       SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
 904       Satisfaction);
 905 }
 906
 907
 908 // Figure out the to-translation-unit depth for this function declaration for
 909 // the purpose of seeing if they differ by constraints. This isn't the same as
 910 // getTemplateDepth, because it includes already instantiated parents.
 911 static unsigned
 912 CalculateTemplateDepthForConstraints(Sema &S, const NamedDecl *ND,
 913                                      bool SkipForSpecialization = false) {
 914   MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
 915       ND, ND->getLexicalDeclContext(), /*Final=*/false,
 916       /*Innermost=*/std::nullopt,
 917       /*RelativeToPrimary=*/true,
 918       /*Pattern=*/nullptr,
 919       /*ForConstraintInstantiation=*/true, SkipForSpecialization);
 920   return MLTAL.getNumLevels();
 921 }
 922
 923 namespace {
 924   class AdjustConstraintDepth : public TreeTransform<AdjustConstraintDepth> {
 925   unsigned TemplateDepth = 0;
 926   public:
 927   using inherited = TreeTransform<AdjustConstraintDepth>;
 928   AdjustConstraintDepth(Sema &SemaRef, unsigned TemplateDepth)
 929       : inherited(SemaRef), TemplateDepth(TemplateDepth) {}
 930
 931   using inherited::TransformTemplateTypeParmType;
 932   QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
 933                                          TemplateTypeParmTypeLoc TL, bool) {
 934     const TemplateTypeParmType *T = TL.getTypePtr();
 935
 936     TemplateTypeParmDecl *NewTTPDecl = nullptr;
 937     if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())
 938       NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(
 939           TransformDecl(TL.getNameLoc(), OldTTPDecl));
 940
 941     QualType Result = getSema().Context.getTemplateTypeParmType(
 942         T->getDepth() + TemplateDepth, T->getIndex(), T->isParameterPack(),
 943         NewTTPDecl);
 944     TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
 945     NewTL.setNameLoc(TL.getNameLoc());
 946     return Result;
 947   }
 948   };
 949 } // namespace
 950
 951 static const Expr *SubstituteConstraintExpressionWithoutSatisfaction(
 952     Sema &S, const Sema::TemplateCompareNewDeclInfo &DeclInfo,
 953     const Expr *ConstrExpr) {
 954   MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
 955       DeclInfo.getDecl(), DeclInfo.getLexicalDeclContext(), /*Final=*/false,
 956       /*Innermost=*/std::nullopt,
 957       /*RelativeToPrimary=*/true,
 958       /*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true,
 959       /*SkipForSpecialization*/ false);
 960
 961   if (MLTAL.getNumSubstitutedLevels() == 0)
 962     return ConstrExpr;
 963
 964   Sema::SFINAETrap SFINAE(S, /*AccessCheckingSFINAE=*/false);
 965
 966   Sema::InstantiatingTemplate Inst(
 967       S, DeclInfo.getLocation(),
 968       Sema::InstantiatingTemplate::ConstraintNormalization{},
 969       const_cast<NamedDecl *>(DeclInfo.getDecl()), SourceRange{});
 970   if (Inst.isInvalid())
 971     return nullptr;
 972
 973   // Set up a dummy 'instantiation' scope in the case of reference to function
 974   // parameters that the surrounding function hasn't been instantiated yet. Note
 975   // this may happen while we're comparing two templates' constraint
 976   // equivalence.
 977   std::optional<LocalInstantiationScope> ScopeForParameters;
 978   if (const NamedDecl *ND = DeclInfo.getDecl();
 979       ND && ND->isFunctionOrFunctionTemplate()) {
 980     ScopeForParameters.emplace(S, /*CombineWithOuterScope=*/true);
 981     const FunctionDecl *FD = ND->getAsFunction();
 982     for (auto *PVD : FD->parameters()) {
 983       if (!PVD->isParameterPack()) {
 984         ScopeForParameters->InstantiatedLocal(PVD, PVD);
 985         continue;
 986       }
 987       // This is hacky: we're mapping the parameter pack to a size-of-1 argument
 988       // to avoid building SubstTemplateTypeParmPackTypes for
 989       // PackExpansionTypes. The SubstTemplateTypeParmPackType node would
 990       // otherwise reference the AssociatedDecl of the template arguments, which
 991       // is, in this case, the template declaration.
 992       //
 993       // However, as we are in the process of comparing potential
 994       // re-declarations, the canonical declaration is the declaration itself at
 995       // this point. So if we didn't expand these packs, we would end up with an
 996       // incorrect profile difference because we will be profiling the
 997       // canonical types!
 998       //
 999       // FIXME: Improve the "no-transform" machinery in FindInstantiatedDecl so
1000       // that we can eliminate the Scope in the cases where the declarations are
1001       // not necessarily instantiated. It would also benefit the noexcept
1002       // specifier comparison.
1003       ScopeForParameters->MakeInstantiatedLocalArgPack(PVD);
1004       ScopeForParameters->InstantiatedLocalPackArg(PVD, PVD);
1005     }
1006   }
1007
1008   std::optional<Sema::CXXThisScopeRAII> ThisScope;
1009
1010   // See TreeTransform::RebuildTemplateSpecializationType. A context scope is
1011   // essential for having an injected class as the canonical type for a template
1012   // specialization type at the rebuilding stage. This guarantees that, for
1013   // out-of-line definitions, injected class name types and their equivalent
1014   // template specializations can be profiled to the same value, which makes it
1015   // possible that e.g. constraints involving C<Class<T>> and C<Class> are
1016   // perceived identical.
1017   std::optional<Sema::ContextRAII> ContextScope;
1018   const DeclContext *DC = [&] {
1019     if (!DeclInfo.getDecl())
1020       return DeclInfo.getDeclContext();
1021     return DeclInfo.getDecl()->getFriendObjectKind()
1022                ? DeclInfo.getLexicalDeclContext()
1023                : DeclInfo.getDeclContext();
1024   }();
1025   if (auto *RD = dyn_cast<CXXRecordDecl>(DC)) {
1026     ThisScope.emplace(S, const_cast<CXXRecordDecl *>(RD), Qualifiers());
1027     ContextScope.emplace(S, const_cast<DeclContext *>(cast<DeclContext>(RD)),
1028                          /*NewThisContext=*/false);
1029   }
1030   ExprResult SubstConstr = S.SubstConstraintExprWithoutSatisfaction(
1031       const_cast<clang::Expr *>(ConstrExpr), MLTAL);
1032   if (SFINAE.hasErrorOccurred() || !SubstConstr.isUsable())
1033     return nullptr;
1034   return SubstConstr.get();
1035 }
1036
1037 bool Sema::AreConstraintExpressionsEqual(const NamedDecl *Old,
1038                                          const Expr *OldConstr,
1039                                          const TemplateCompareNewDeclInfo &New,
1040                                          const Expr *NewConstr) {
1041   if (OldConstr == NewConstr)
1042     return true;
1043   // C++ [temp.constr.decl]p4
1044   if (Old && !New.isInvalid() && !New.ContainsDecl(Old) &&
1045       Old->getLexicalDeclContext() != New.getLexicalDeclContext()) {
1046     if (const Expr *SubstConstr =
1047             SubstituteConstraintExpressionWithoutSatisfaction(*this, Old,
1048                                                               OldConstr))
1049       OldConstr = SubstConstr;
1050     else
1051       return false;
1052     if (const Expr *SubstConstr =
1053             SubstituteConstraintExpressionWithoutSatisfaction(*this, New,
1054                                                               NewConstr))
1055       NewConstr = SubstConstr;
1056     else
1057       return false;
1058   }
1059
1060   llvm::FoldingSetNodeID ID1, ID2;
1061   OldConstr->Profile(ID1, Context, /*Canonical=*/true);
1062   NewConstr->Profile(ID2, Context, /*Canonical=*/true);
1063   return ID1 == ID2;
1064 }
1065
1066 bool Sema::FriendConstraintsDependOnEnclosingTemplate(const FunctionDecl *FD) {
1067   assert(FD->getFriendObjectKind() && "Must be a friend!");
1068
1069   // The logic for non-templates is handled in ASTContext::isSameEntity, so we
1070   // don't have to bother checking 'DependsOnEnclosingTemplate' for a
1071   // non-function-template.
1072   assert(FD->getDescribedFunctionTemplate() &&
1073          "Non-function templates don't need to be checked");
1074
1075   SmallVector<const Expr *, 3> ACs;
1076   FD->getDescribedFunctionTemplate()->getAssociatedConstraints(ACs);
1077
1078   unsigned OldTemplateDepth = CalculateTemplateDepthForConstraints(*this, FD);
1079   for (const Expr *Constraint : ACs)
1080     if (ConstraintExpressionDependsOnEnclosingTemplate(FD, OldTemplateDepth,
1081                                                        Constraint))
1082       return true;
1083
1084   return false;
1085 }
1086
1087 bool Sema::EnsureTemplateArgumentListConstraints(
1088     TemplateDecl *TD, const MultiLevelTemplateArgumentList &TemplateArgsLists,
1089     SourceRange TemplateIDRange) {
1090   ConstraintSatisfaction Satisfaction;
1091   llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
1092   TD->getAssociatedConstraints(AssociatedConstraints);
1093   if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgsLists,
1094                                   TemplateIDRange, Satisfaction))
1095     return true;
1096
1097   if (!Satisfaction.IsSatisfied) {
1098     SmallString<128> TemplateArgString;
1099     TemplateArgString = " ";
1100     TemplateArgString += getTemplateArgumentBindingsText(
1101         TD->getTemplateParameters(), TemplateArgsLists.getInnermost().data(),
1102         TemplateArgsLists.getInnermost().size());
1103
1104     Diag(TemplateIDRange.getBegin(),
1105          diag::err_template_arg_list_constraints_not_satisfied)
1106         << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD
1107         << TemplateArgString << TemplateIDRange;
1108     DiagnoseUnsatisfiedConstraint(Satisfaction);
1109     return true;
1110   }
1111   return false;
1112 }
1113
1114 bool Sema::CheckInstantiatedFunctionTemplateConstraints(
1115     SourceLocation PointOfInstantiation, FunctionDecl *Decl,
1116     ArrayRef<TemplateArgument> TemplateArgs,
1117     ConstraintSatisfaction &Satisfaction) {
1118   // In most cases we're not going to have constraints, so check for that first.
1119   FunctionTemplateDecl *Template = Decl->getPrimaryTemplate();
1120   // Note - code synthesis context for the constraints check is created
1121   // inside CheckConstraintsSatisfaction.
1122   SmallVector<const Expr *, 3> TemplateAC;
1123   Template->getAssociatedConstraints(TemplateAC);
1124   if (TemplateAC.empty()) {
1125     Satisfaction.IsSatisfied = true;
1126     return false;
1127   }
1128
1129   // Enter the scope of this instantiation. We don't use
1130   // PushDeclContext because we don't have a scope.
1131   Sema::ContextRAII savedContext(*this, Decl);
1132   LocalInstantiationScope Scope(*this);
1133
1134   std::optional<MultiLevelTemplateArgumentList> MLTAL =
1135       SetupConstraintCheckingTemplateArgumentsAndScope(Decl, TemplateArgs,
1136                                                        Scope);
1137
1138   if (!MLTAL)
1139     return true;
1140
1141   Qualifiers ThisQuals;
1142   CXXRecordDecl *Record = nullptr;
1143   if (auto *Method = dyn_cast<CXXMethodDecl>(Decl)) {
1144     ThisQuals = Method->getMethodQualifiers();
1145     Record = Method->getParent();
1146   }
1147
1148   CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
1149   LambdaScopeForCallOperatorInstantiationRAII LambdaScope(
1150       *this, const_cast<FunctionDecl *>(Decl), *MLTAL, Scope);
1151
1152   llvm::SmallVector<Expr *, 1> Converted;
1153   return CheckConstraintSatisfaction(Template, TemplateAC, Converted, *MLTAL,
1154                                      PointOfInstantiation, Satisfaction);
1155 }
1156
1157 static void diagnoseUnsatisfiedRequirement(Sema &S,
1158                                            concepts::ExprRequirement *Req,
1159                                            bool First) {
1160   assert(!Req->isSatisfied()
1161          && "Diagnose() can only be used on an unsatisfied requirement");
1162   switch (Req->getSatisfactionStatus()) {
1163     case concepts::ExprRequirement::SS_Dependent:
1164       llvm_unreachable("Diagnosing a dependent requirement");
1165       break;
1166     case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {
1167       auto *SubstDiag = Req->getExprSubstitutionDiagnostic();
1168       if (!SubstDiag->DiagMessage.empty())
1169         S.Diag(SubstDiag->DiagLoc,
1170                diag::note_expr_requirement_expr_substitution_error)
1171                << (int)First << SubstDiag->SubstitutedEntity
1172                << SubstDiag->DiagMessage;
1173       else
1174         S.Diag(SubstDiag->DiagLoc,
1175                diag::note_expr_requirement_expr_unknown_substitution_error)
1176             << (int)First << SubstDiag->SubstitutedEntity;
1177       break;
1178     }
1179     case concepts::ExprRequirement::SS_NoexceptNotMet:
1180       S.Diag(Req->getNoexceptLoc(),
1181              diag::note_expr_requirement_noexcept_not_met)
1182           << (int)First << Req->getExpr();
1183       break;
1184     case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
1185       auto *SubstDiag =
1186           Req->getReturnTypeRequirement().getSubstitutionDiagnostic();
1187       if (!SubstDiag->DiagMessage.empty())
1188         S.Diag(SubstDiag->DiagLoc,
1189                diag::note_expr_requirement_type_requirement_substitution_error)
1190             << (int)First << SubstDiag->SubstitutedEntity
1191             << SubstDiag->DiagMessage;
1192       else
1193         S.Diag(SubstDiag->DiagLoc,
1194                diag::note_expr_requirement_type_requirement_unknown_substitution_error)
1195             << (int)First << SubstDiag->SubstitutedEntity;
1196       break;
1197     }
1198     case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {
1199       ConceptSpecializationExpr *ConstraintExpr =
1200           Req->getReturnTypeRequirementSubstitutedConstraintExpr();
1201       if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
1202         // A simple case - expr type is the type being constrained and the concept
1203         // was not provided arguments.
1204         Expr *e = Req->getExpr();
1205         S.Diag(e->getBeginLoc(),
1206                diag::note_expr_requirement_constraints_not_satisfied_simple)
1207             << (int)First << S.Context.getReferenceQualifiedType(e)
1208             << ConstraintExpr->getNamedConcept();
1209       } else {
1210         S.Diag(ConstraintExpr->getBeginLoc(),
1211                diag::note_expr_requirement_constraints_not_satisfied)
1212             << (int)First << ConstraintExpr;
1213       }
1214       S.DiagnoseUnsatisfiedConstraint(ConstraintExpr->getSatisfaction());
1215       break;
1216     }
1217     case concepts::ExprRequirement::SS_Satisfied:
1218       llvm_unreachable("We checked this above");
1219   }
1220 }
1221
1222 static void diagnoseUnsatisfiedRequirement(Sema &S,
1223                                            concepts::TypeRequirement *Req,
1224                                            bool First) {
1225   assert(!Req->isSatisfied()
1226          && "Diagnose() can only be used on an unsatisfied requirement");
1227   switch (Req->getSatisfactionStatus()) {
1228   case concepts::TypeRequirement::SS_Dependent:
1229     llvm_unreachable("Diagnosing a dependent requirement");
1230     return;
1231   case concepts::TypeRequirement::SS_SubstitutionFailure: {
1232     auto *SubstDiag = Req->getSubstitutionDiagnostic();
1233     if (!SubstDiag->DiagMessage.empty())
1234       S.Diag(SubstDiag->DiagLoc,
1235              diag::note_type_requirement_substitution_error) << (int)First
1236           << SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage;
1237     else
1238       S.Diag(SubstDiag->DiagLoc,
1239              diag::note_type_requirement_unknown_substitution_error)
1240           << (int)First << SubstDiag->SubstitutedEntity;
1241     return;
1242   }
1243   default:
1244     llvm_unreachable("Unknown satisfaction status");
1245     return;
1246   }
1247 }
1248 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
1249                                                         Expr *SubstExpr,
1250                                                         bool First = true);
1251
1252 static void diagnoseUnsatisfiedRequirement(Sema &S,
1253                                            concepts::NestedRequirement *Req,
1254                                            bool First) {
1255   using SubstitutionDiagnostic = std::pair<SourceLocation, StringRef>;
1256   for (auto &Record : Req->getConstraintSatisfaction()) {
1257     if (auto *SubstDiag = Record.dyn_cast<SubstitutionDiagnostic *>())
1258       S.Diag(SubstDiag->first, diag::note_nested_requirement_substitution_error)
1259           << (int)First << Req->getInvalidConstraintEntity()
1260           << SubstDiag->second;
1261     else
1262       diagnoseWellFormedUnsatisfiedConstraintExpr(S, Record.dyn_cast<Expr *>(),
1263                                                   First);
1264     First = false;
1265   }
1266 }
1267
1268 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
1269                                                         Expr *SubstExpr,
1270                                                         bool First) {
1271   SubstExpr = SubstExpr->IgnoreParenImpCasts();
1272   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {
1273     switch (BO->getOpcode()) {
1274     // These two cases will in practice only be reached when using fold
1275     // expressions with || and &&, since otherwise the || and && will have been
1276     // broken down into atomic constraints during satisfaction checking.
1277     case BO_LOr:
1278       // Or evaluated to false - meaning both RHS and LHS evaluated to false.
1279       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
1280       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
1281                                                   /*First=*/false);
1282       return;
1283     case BO_LAnd: {
1284       bool LHSSatisfied =
1285           BO->getLHS()->EvaluateKnownConstInt(S.Context).getBoolValue();
1286       if (LHSSatisfied) {
1287         // LHS is true, so RHS must be false.
1288         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First);
1289         return;
1290       }
1291       // LHS is false
1292       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
1293
1294       // RHS might also be false
1295       bool RHSSatisfied =
1296           BO->getRHS()->EvaluateKnownConstInt(S.Context).getBoolValue();
1297       if (!RHSSatisfied)
1298         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
1299                                                     /*First=*/false);
1300       return;
1301     }
1302     case BO_GE:
1303     case BO_LE:
1304     case BO_GT:
1305     case BO_LT:
1306     case BO_EQ:
1307     case BO_NE:
1308       if (BO->getLHS()->getType()->isIntegerType() &&
1309           BO->getRHS()->getType()->isIntegerType()) {
1310         Expr::EvalResult SimplifiedLHS;
1311         Expr::EvalResult SimplifiedRHS;
1312         BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context,
1313                                     Expr::SE_NoSideEffects,
1314                                     /*InConstantContext=*/true);
1315         BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context,
1316                                     Expr::SE_NoSideEffects,
1317                                     /*InConstantContext=*/true);
1318         if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
1319           S.Diag(SubstExpr->getBeginLoc(),
1320                  diag::note_atomic_constraint_evaluated_to_false_elaborated)
1321               << (int)First << SubstExpr
1322               << toString(SimplifiedLHS.Val.getInt(), 10)
1323               << BinaryOperator::getOpcodeStr(BO->getOpcode())
1324               << toString(SimplifiedRHS.Val.getInt(), 10);
1325           return;
1326         }
1327       }
1328       break;
1329
1330     default:
1331       break;
1332     }
1333   } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) {
1334     if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
1335       S.Diag(
1336           CSE->getSourceRange().getBegin(),
1337           diag::
1338           note_single_arg_concept_specialization_constraint_evaluated_to_false)
1339           << (int)First
1340           << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
1341           << CSE->getNamedConcept();
1342     } else {
1343       S.Diag(SubstExpr->getSourceRange().getBegin(),
1344              diag::note_concept_specialization_constraint_evaluated_to_false)
1345           << (int)First << CSE;
1346     }
1347     S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction());
1348     return;
1349   } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) {
1350     // FIXME: RequiresExpr should store dependent diagnostics.
1351     for (concepts::Requirement *Req : RE->getRequirements())
1352       if (!Req->isDependent() && !Req->isSatisfied()) {
1353         if (auto *E = dyn_cast<concepts::ExprRequirement>(Req))
1354           diagnoseUnsatisfiedRequirement(S, E, First);
1355         else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req))
1356           diagnoseUnsatisfiedRequirement(S, T, First);
1357         else
1358           diagnoseUnsatisfiedRequirement(
1359               S, cast<concepts::NestedRequirement>(Req), First);
1360         break;
1361       }
1362     return;
1363   } else if (auto *TTE = dyn_cast<TypeTraitExpr>(SubstExpr);
1364              TTE && TTE->getTrait() == clang::TypeTrait::BTT_IsDeducible) {
1365     assert(TTE->getNumArgs() == 2);
1366     S.Diag(SubstExpr->getSourceRange().getBegin(),
1367            diag::note_is_deducible_constraint_evaluated_to_false)
1368         << TTE->getArg(0)->getType() << TTE->getArg(1)->getType();
1369     return;
1370   }
1371
1372   S.Diag(SubstExpr->getSourceRange().getBegin(),
1373          diag::note_atomic_constraint_evaluated_to_false)
1374       << (int)First << SubstExpr;
1375 }
1376
1377 template <typename SubstitutionDiagnostic>
1378 static void diagnoseUnsatisfiedConstraintExpr(
1379     Sema &S, const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
1380     bool First = true) {
1381   if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()) {
1382     S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
1383         << Diag->second;
1384     return;
1385   }
1386
1387   diagnoseWellFormedUnsatisfiedConstraintExpr(S, cast<Expr *>(Record), First);
1388 }
1389
1390 void
1391 Sema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction,
1392                                     bool First) {
1393   assert(!Satisfaction.IsSatisfied &&
1394          "Attempted to diagnose a satisfied constraint");
1395   for (auto &Record : Satisfaction.Details) {
1396     diagnoseUnsatisfiedConstraintExpr(*this, Record, First);
1397     First = false;
1398   }
1399 }
1400
1401 void Sema::DiagnoseUnsatisfiedConstraint(
1402     const ASTConstraintSatisfaction &Satisfaction,
1403     bool First) {
1404   assert(!Satisfaction.IsSatisfied &&
1405          "Attempted to diagnose a satisfied constraint");
1406   for (auto &Record : Satisfaction) {
1407     diagnoseUnsatisfiedConstraintExpr(*this, Record, First);
1408     First = false;
1409   }
1410 }
1411
1412 const NormalizedConstraint *
1413 Sema::getNormalizedAssociatedConstraints(
1414     NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) {
1415   // In case the ConstrainedDecl comes from modules, it is necessary to use
1416   // the canonical decl to avoid different atomic constraints with the 'same'
1417   // declarations.
1418   ConstrainedDecl = cast<NamedDecl>(ConstrainedDecl->getCanonicalDecl());
1419
1420   auto CacheEntry = NormalizationCache.find(ConstrainedDecl);
1421   if (CacheEntry == NormalizationCache.end()) {
1422     auto Normalized =
1423         NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl,
1424                                                   AssociatedConstraints);
1425     CacheEntry =
1426         NormalizationCache
1427             .try_emplace(ConstrainedDecl,
1428                          Normalized
1429                              ? new (Context) NormalizedConstraint(
1430                                  std::move(*Normalized))
1431                              : nullptr)
1432             .first;
1433   }
1434   return CacheEntry->second;
1435 }
1436
1437 const NormalizedConstraint *clang::getNormalizedAssociatedConstraints(
1438     Sema &S, NamedDecl *ConstrainedDecl,
1439     ArrayRef<const Expr *> AssociatedConstraints) {
1440   return S.getNormalizedAssociatedConstraints(ConstrainedDecl,
1441                                               AssociatedConstraints);
1442 }
1443
1444 static bool
1445 substituteParameterMappings(Sema &S, NormalizedConstraint &N,
1446                             ConceptDecl *Concept,
1447                             const MultiLevelTemplateArgumentList &MLTAL,
1448                             const ASTTemplateArgumentListInfo *ArgsAsWritten) {
1449
1450   if (N.isCompound()) {
1451     if (substituteParameterMappings(S, N.getLHS(), Concept, MLTAL,
1452                                     ArgsAsWritten))
1453       return true;
1454     return substituteParameterMappings(S, N.getRHS(), Concept, MLTAL,
1455                                        ArgsAsWritten);
1456   }
1457
1458   if (N.isFoldExpanded()) {
1459     Sema::ArgumentPackSubstitutionIndexRAII _(S, -1);
1460     return substituteParameterMappings(
1461         S, N.getFoldExpandedConstraint()->Constraint, Concept, MLTAL,
1462         ArgsAsWritten);
1463   }
1464
1465   TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
1466
1467   AtomicConstraint &Atomic = *N.getAtomicConstraint();
1468   TemplateArgumentListInfo SubstArgs;
1469   if (!Atomic.ParameterMapping) {
1470     llvm::SmallBitVector OccurringIndices(TemplateParams->size());
1471     S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
1472                                  /*Depth=*/0, OccurringIndices);
1473     TemplateArgumentLoc *TempArgs =
1474         new (S.Context) TemplateArgumentLoc[OccurringIndices.count()];
1475     for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I)
1476       if (OccurringIndices[I])
1477         new (&(TempArgs)[J++])
1478             TemplateArgumentLoc(S.getIdentityTemplateArgumentLoc(
1479                 TemplateParams->begin()[I],
1480                 // Here we assume we do not support things like
1481                 // template<typename A, typename B>
1482                 // concept C = ...;
1483                 //
1484                 // template<typename... Ts> requires C<Ts...>
1485                 // struct S { };
1486                 // The above currently yields a diagnostic.
1487                 // We still might have default arguments for concept parameters.
1488                 ArgsAsWritten->NumTemplateArgs > I
1489                     ? ArgsAsWritten->arguments()[I].getLocation()
1490                     : SourceLocation()));
1491     Atomic.ParameterMapping.emplace(TempArgs,  OccurringIndices.count());
1492   }
1493   SourceLocation InstLocBegin =
1494       ArgsAsWritten->arguments().empty()
1495           ? ArgsAsWritten->getLAngleLoc()
1496           : ArgsAsWritten->arguments().front().getSourceRange().getBegin();
1497   SourceLocation InstLocEnd =
1498       ArgsAsWritten->arguments().empty()
1499           ? ArgsAsWritten->getRAngleLoc()
1500           : ArgsAsWritten->arguments().front().getSourceRange().getEnd();
1501   Sema::InstantiatingTemplate Inst(
1502       S, InstLocBegin,
1503       Sema::InstantiatingTemplate::ParameterMappingSubstitution{},
1504       Atomic.ConstraintDecl, {InstLocBegin, InstLocEnd});
1505   if (Inst.isInvalid())
1506     return true;
1507   if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs))
1508     return true;
1509
1510   TemplateArgumentLoc *TempArgs =
1511       new (S.Context) TemplateArgumentLoc[SubstArgs.size()];
1512   std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(),
1513             TempArgs);
1514   Atomic.ParameterMapping.emplace(TempArgs, SubstArgs.size());
1515   return false;
1516 }
1517
1518 static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
1519                                         const ConceptSpecializationExpr *CSE) {
1520   MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
1521       CSE->getNamedConcept(), CSE->getNamedConcept()->getLexicalDeclContext(),
1522       /*Final=*/false, CSE->getTemplateArguments(),
1523       /*RelativeToPrimary=*/true,
1524       /*Pattern=*/nullptr,
1525       /*ForConstraintInstantiation=*/true);
1526
1527   return substituteParameterMappings(S, N, CSE->getNamedConcept(), MLTAL,
1528                                      CSE->getTemplateArgsAsWritten());
1529 }
1530
1531 NormalizedConstraint::NormalizedConstraint(ASTContext &C,
1532                                            NormalizedConstraint LHS,
1533                                            NormalizedConstraint RHS,
1534                                            CompoundConstraintKind Kind)
1535     : Constraint{CompoundConstraint{
1536           new(C) NormalizedConstraintPair{std::move(LHS), std::move(RHS)},
1537           Kind}} {}
1538
1539 NormalizedConstraint::NormalizedConstraint(ASTContext &C,
1540                                            const NormalizedConstraint &Other) {
1541   if (Other.isAtomic()) {
1542     Constraint = new (C) AtomicConstraint(*Other.getAtomicConstraint());
1543   } else if (Other.isFoldExpanded()) {
1544     Constraint = new (C) FoldExpandedConstraint(
1545         Other.getFoldExpandedConstraint()->Kind,
1546         NormalizedConstraint(C, Other.getFoldExpandedConstraint()->Constraint),
1547         Other.getFoldExpandedConstraint()->Pattern);
1548   } else {
1549     Constraint = CompoundConstraint(
1550         new (C)
1551             NormalizedConstraintPair{NormalizedConstraint(C, Other.getLHS()),
1552                                      NormalizedConstraint(C, Other.getRHS())},
1553         Other.getCompoundKind());
1554   }
1555 }
1556
1557 NormalizedConstraint &NormalizedConstraint::getLHS() const {
1558   assert(isCompound() && "getLHS called on a non-compound constraint.");
1559   return cast<CompoundConstraint>(Constraint).getPointer()->LHS;
1560 }
1561
1562 NormalizedConstraint &NormalizedConstraint::getRHS() const {
1563   assert(isCompound() && "getRHS called on a non-compound constraint.");
1564   return cast<CompoundConstraint>(Constraint).getPointer()->RHS;
1565 }
1566
1567 std::optional<NormalizedConstraint>
1568 NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D,
1569                                           ArrayRef<const Expr *> E) {
1570   assert(E.size() != 0);
1571   auto Conjunction = fromConstraintExpr(S, D, E[0]);
1572   if (!Conjunction)
1573     return std::nullopt;
1574   for (unsigned I = 1; I < E.size(); ++I) {
1575     auto Next = fromConstraintExpr(S, D, E[I]);
1576     if (!Next)
1577       return std::nullopt;
1578     *Conjunction = NormalizedConstraint(S.Context, std::move(*Conjunction),
1579                                         std::move(*Next), CCK_Conjunction);
1580   }
1581   return Conjunction;
1582 }
1583
1584 std::optional<NormalizedConstraint>
1585 NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
1586   assert(E != nullptr);
1587
1588   // C++ [temp.constr.normal]p1.1
1589   // [...]
1590   // - The normal form of an expression (E) is the normal form of E.
1591   // [...]
1592   E = E->IgnoreParenImpCasts();
1593
1594   // C++2a [temp.param]p4:
1595   //     [...] If T is not a pack, then E is E', otherwise E is (E' && ...).
1596   // Fold expression is considered atomic constraints per current wording.
1597   // See http://cplusplus.github.io/concepts-ts/ts-active.html#28
1598
1599   if (LogicalBinOp BO = E) {
1600     auto LHS = fromConstraintExpr(S, D, BO.getLHS());
1601     if (!LHS)
1602       return std::nullopt;
1603     auto RHS = fromConstraintExpr(S, D, BO.getRHS());
1604     if (!RHS)
1605       return std::nullopt;
1606
1607     return NormalizedConstraint(S.Context, std::move(*LHS), std::move(*RHS),
1608                                 BO.isAnd() ? CCK_Conjunction : CCK_Disjunction);
1609   } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) {
1610     const NormalizedConstraint *SubNF;
1611     {
1612       Sema::InstantiatingTemplate Inst(
1613           S, CSE->getExprLoc(),
1614           Sema::InstantiatingTemplate::ConstraintNormalization{}, D,
1615           CSE->getSourceRange());
1616       if (Inst.isInvalid())
1617         return std::nullopt;
1618       // C++ [temp.constr.normal]p1.1
1619       // [...]
1620       // The normal form of an id-expression of the form C<A1, A2, ..., AN>,
1621       // where C names a concept, is the normal form of the
1622       // constraint-expression of C, after substituting A1, A2, ..., AN for C’s
1623       // respective template parameters in the parameter mappings in each atomic
1624       // constraint. If any such substitution results in an invalid type or
1625       // expression, the program is ill-formed; no diagnostic is required.
1626       // [...]
1627       ConceptDecl *CD = CSE->getNamedConcept();
1628       SubNF = S.getNormalizedAssociatedConstraints(CD,
1629                                                    {CD->getConstraintExpr()});
1630       if (!SubNF)
1631         return std::nullopt;
1632     }
1633
1634     std::optional<NormalizedConstraint> New;
1635     New.emplace(S.Context, *SubNF);
1636
1637     if (substituteParameterMappings(S, *New, CSE))
1638       return std::nullopt;
1639
1640     return New;
1641   } else if (auto *FE = dyn_cast<const CXXFoldExpr>(E);
1642              FE && S.getLangOpts().CPlusPlus26 &&
1643              (FE->getOperator() == BinaryOperatorKind::BO_LAnd ||
1644               FE->getOperator() == BinaryOperatorKind::BO_LOr)) {
1645
1646     // Normalize fold expressions in C++26.
1647
1648     FoldExpandedConstraint::FoldOperatorKind Kind =
1649         FE->getOperator() == BinaryOperatorKind::BO_LAnd
1650             ? FoldExpandedConstraint::FoldOperatorKind::And
1651             : FoldExpandedConstraint::FoldOperatorKind::Or;
1652
1653     if (FE->getInit()) {
1654       auto LHS = fromConstraintExpr(S, D, FE->getLHS());
1655       auto RHS = fromConstraintExpr(S, D, FE->getRHS());
1656       if (!LHS || !RHS)
1657         return std::nullopt;
1658
1659       if (FE->isRightFold())
1660         RHS = NormalizedConstraint{new (S.Context) FoldExpandedConstraint{
1661             Kind, std::move(*RHS), FE->getPattern()}};
1662       else
1663         LHS = NormalizedConstraint{new (S.Context) FoldExpandedConstraint{
1664             Kind, std::move(*LHS), FE->getPattern()}};
1665
1666       return NormalizedConstraint(
1667           S.Context, std::move(*LHS), std::move(*RHS),
1668           FE->getOperator() == BinaryOperatorKind::BO_LAnd ? CCK_Conjunction
1669                                                            : CCK_Disjunction);
1670     }
1671     auto Sub = fromConstraintExpr(S, D, FE->getPattern());
1672     if (!Sub)
1673       return std::nullopt;
1674     return NormalizedConstraint{new (S.Context) FoldExpandedConstraint{
1675         Kind, std::move(*Sub), FE->getPattern()}};
1676   }
1677
1678   return NormalizedConstraint{new (S.Context) AtomicConstraint(E, D)};
1679 }
1680
1681 bool FoldExpandedConstraint::AreCompatibleForSubsumption(
1682     const FoldExpandedConstraint &A, const FoldExpandedConstraint &B) {
1683
1684   // [C++26] [temp.constr.fold]
1685   // Two fold expanded constraints are compatible for subsumption
1686   // if their respective constraints both contain an equivalent unexpanded pack.
1687
1688   llvm::SmallVector<UnexpandedParameterPack> APacks, BPacks;
1689   Sema::collectUnexpandedParameterPacks(const_cast<Expr *>(A.Pattern), APacks);
1690   Sema::collectUnexpandedParameterPacks(const_cast<Expr *>(B.Pattern), BPacks);
1691
1692   for (const UnexpandedParameterPack &APack : APacks) {
1693     std::pair<unsigned, unsigned> DepthAndIndex = getDepthAndIndex(APack);
1694     auto it = llvm::find_if(BPacks, [&](const UnexpandedParameterPack &BPack) {
1695       return getDepthAndIndex(BPack) == DepthAndIndex;
1696     });
1697     if (it != BPacks.end())
1698       return true;
1699   }
1700   return false;
1701 }
1702
1703 NormalForm clang::makeCNF(const NormalizedConstraint &Normalized) {
1704   if (Normalized.isAtomic())
1705     return {{Normalized.getAtomicConstraint()}};
1706
1707   else if (Normalized.isFoldExpanded())
1708     return {{Normalized.getFoldExpandedConstraint()}};
1709
1710   NormalForm LCNF = makeCNF(Normalized.getLHS());
1711   NormalForm RCNF = makeCNF(Normalized.getRHS());
1712   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
1713     LCNF.reserve(LCNF.size() + RCNF.size());
1714     while (!RCNF.empty())
1715       LCNF.push_back(RCNF.pop_back_val());
1716     return LCNF;
1717   }
1718
1719   // Disjunction
1720   NormalForm Res;
1721   Res.reserve(LCNF.size() * RCNF.size());
1722   for (auto &LDisjunction : LCNF)
1723     for (auto &RDisjunction : RCNF) {
1724       NormalForm::value_type Combined;
1725       Combined.reserve(LDisjunction.size() + RDisjunction.size());
1726       std::copy(LDisjunction.begin(), LDisjunction.end(),
1727                 std::back_inserter(Combined));
1728       std::copy(RDisjunction.begin(), RDisjunction.end(),
1729                 std::back_inserter(Combined));
1730       Res.emplace_back(Combined);
1731     }
1732   return Res;
1733 }
1734
1735 NormalForm clang::makeDNF(const NormalizedConstraint &Normalized) {
1736   if (Normalized.isAtomic())
1737     return {{Normalized.getAtomicConstraint()}};
1738
1739   else if (Normalized.isFoldExpanded())
1740     return {{Normalized.getFoldExpandedConstraint()}};
1741
1742   NormalForm LDNF = makeDNF(Normalized.getLHS());
1743   NormalForm RDNF = makeDNF(Normalized.getRHS());
1744   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
1745     LDNF.reserve(LDNF.size() + RDNF.size());
1746     while (!RDNF.empty())
1747       LDNF.push_back(RDNF.pop_back_val());
1748     return LDNF;
1749   }
1750
1751   // Conjunction
1752   NormalForm Res;
1753   Res.reserve(LDNF.size() * RDNF.size());
1754   for (auto &LConjunction : LDNF) {
1755     for (auto &RConjunction : RDNF) {
1756       NormalForm::value_type Combined;
1757       Combined.reserve(LConjunction.size() + RConjunction.size());
1758       std::copy(LConjunction.begin(), LConjunction.end(),
1759                 std::back_inserter(Combined));
1760       std::copy(RConjunction.begin(), RConjunction.end(),
1761                 std::back_inserter(Combined));
1762       Res.emplace_back(Combined);
1763     }
1764   }
1765   return Res;
1766 }
1767
1768 bool Sema::IsAtLeastAsConstrained(NamedDecl *D1,
1769                                   MutableArrayRef<const Expr *> AC1,
1770                                   NamedDecl *D2,
1771                                   MutableArrayRef<const Expr *> AC2,
1772                                   bool &Result) {
1773   if (const auto *FD1 = dyn_cast<FunctionDecl>(D1)) {
1774     auto IsExpectedEntity = [](const FunctionDecl *FD) {
1775       FunctionDecl::TemplatedKind Kind = FD->getTemplatedKind();
1776       return Kind == FunctionDecl::TK_NonTemplate ||
1777              Kind == FunctionDecl::TK_FunctionTemplate;
1778     };
1779     const auto *FD2 = dyn_cast<FunctionDecl>(D2);
1780     (void)IsExpectedEntity;
1781     (void)FD1;
1782     (void)FD2;
1783     assert(IsExpectedEntity(FD1) && FD2 && IsExpectedEntity(FD2) &&
1784            "use non-instantiated function declaration for constraints partial "
1785            "ordering");
1786   }
1787
1788   if (AC1.empty()) {
1789     Result = AC2.empty();
1790     return false;
1791   }
1792   if (AC2.empty()) {
1793     // TD1 has associated constraints and TD2 does not.
1794     Result = true;
1795     return false;
1796   }
1797
1798   std::pair<NamedDecl *, NamedDecl *> Key{D1, D2};
1799   auto CacheEntry = SubsumptionCache.find(Key);
1800   if (CacheEntry != SubsumptionCache.end()) {
1801     Result = CacheEntry->second;
1802     return false;
1803   }
1804
1805   unsigned Depth1 = CalculateTemplateDepthForConstraints(*this, D1, true);
1806   unsigned Depth2 = CalculateTemplateDepthForConstraints(*this, D2, true);
1807
1808   for (size_t I = 0; I != AC1.size() && I != AC2.size(); ++I) {
1809     if (Depth2 > Depth1) {
1810       AC1[I] = AdjustConstraintDepth(*this, Depth2 - Depth1)
1811                    .TransformExpr(const_cast<Expr *>(AC1[I]))
1812                    .get();
1813     } else if (Depth1 > Depth2) {
1814       AC2[I] = AdjustConstraintDepth(*this, Depth1 - Depth2)
1815                    .TransformExpr(const_cast<Expr *>(AC2[I]))
1816                    .get();
1817     }
1818   }
1819
1820   if (clang::subsumes(
1821           *this, D1, AC1, D2, AC2, Result,
1822           [this](const AtomicConstraint &A, const AtomicConstraint &B) {
1823             return A.subsumes(Context, B);
1824           }))
1825     return true;
1826   SubsumptionCache.try_emplace(Key, Result);
1827   return false;
1828 }
1829
1830 bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
1831     ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) {
1832   if (isSFINAEContext())
1833     // No need to work here because our notes would be discarded.
1834     return false;
1835
1836   if (AC1.empty() || AC2.empty())
1837     return false;
1838
1839   auto NormalExprEvaluator =
1840       [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
1841         return A.subsumes(Context, B);
1842       };
1843
1844   const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
1845   auto IdenticalExprEvaluator =
1846       [&] (const AtomicConstraint &A, const AtomicConstraint &B) {
1847         if (!A.hasMatchingParameterMapping(Context, B))
1848           return false;
1849         const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
1850         if (EA == EB)
1851           return true;
1852
1853         // Not the same source level expression - are the expressions
1854         // identical?
1855         llvm::FoldingSetNodeID IDA, IDB;
1856         EA->Profile(IDA, Context, /*Canonical=*/true);
1857         EB->Profile(IDB, Context, /*Canonical=*/true);
1858         if (IDA != IDB)
1859           return false;
1860
1861         AmbiguousAtomic1 = EA;
1862         AmbiguousAtomic2 = EB;
1863         return true;
1864       };
1865
1866   {
1867     // The subsumption checks might cause diagnostics
1868     SFINAETrap Trap(*this);
1869     auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1);
1870     if (!Normalized1)
1871       return false;
1872     const NormalForm DNF1 = makeDNF(*Normalized1);
1873     const NormalForm CNF1 = makeCNF(*Normalized1);
1874
1875     auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2);
1876     if (!Normalized2)
1877       return false;
1878     const NormalForm DNF2 = makeDNF(*Normalized2);
1879     const NormalForm CNF2 = makeCNF(*Normalized2);
1880
1881     bool Is1AtLeastAs2Normally =
1882         clang::subsumes(DNF1, CNF2, NormalExprEvaluator);
1883     bool Is2AtLeastAs1Normally =
1884         clang::subsumes(DNF2, CNF1, NormalExprEvaluator);
1885     bool Is1AtLeastAs2 = clang::subsumes(DNF1, CNF2, IdenticalExprEvaluator);
1886     bool Is2AtLeastAs1 = clang::subsumes(DNF2, CNF1, IdenticalExprEvaluator);
1887     if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
1888         Is2AtLeastAs1 == Is2AtLeastAs1Normally)
1889       // Same result - no ambiguity was caused by identical atomic expressions.
1890       return false;
1891   }
1892
1893   // A different result! Some ambiguous atomic constraint(s) caused a difference
1894   assert(AmbiguousAtomic1 && AmbiguousAtomic2);
1895
1896   Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints)
1897       << AmbiguousAtomic1->getSourceRange();
1898   Diag(AmbiguousAtomic2->getBeginLoc(),
1899        diag::note_ambiguous_atomic_constraints_similar_expression)
1900       << AmbiguousAtomic2->getSourceRange();
1901   return true;
1902 }
1903
1904 concepts::ExprRequirement::ExprRequirement(
1905     Expr *E, bool IsSimple, SourceLocation NoexceptLoc,
1906     ReturnTypeRequirement Req, SatisfactionStatus Status,
1907     ConceptSpecializationExpr *SubstitutedConstraintExpr) :
1908     Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent,
1909                 Status == SS_Dependent &&
1910                 (E->containsUnexpandedParameterPack() ||
1911                  Req.containsUnexpandedParameterPack()),
1912                 Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc),
1913     TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr),
1914     Status(Status) {
1915   assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1916          "Simple requirement must not have a return type requirement or a "
1917          "noexcept specification");
1918   assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) ==
1919          (SubstitutedConstraintExpr != nullptr));
1920 }
1921
1922 concepts::ExprRequirement::ExprRequirement(
1923     SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple,
1924     SourceLocation NoexceptLoc, ReturnTypeRequirement Req) :
1925     Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(),
1926                 Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false),
1927     Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req),
1928     Status(SS_ExprSubstitutionFailure) {
1929   assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1930          "Simple requirement must not have a return type requirement or a "
1931          "noexcept specification");
1932 }
1933
1934 concepts::ExprRequirement::ReturnTypeRequirement::
1935 ReturnTypeRequirement(TemplateParameterList *TPL) :
1936     TypeConstraintInfo(TPL, false) {
1937   assert(TPL->size() == 1);
1938   const TypeConstraint *TC =
1939       cast<TemplateTypeParmDecl>(TPL->getParam(0))->getTypeConstraint();
1940   assert(TC &&
1941          "TPL must have a template type parameter with a type constraint");
1942   auto *Constraint =
1943       cast<ConceptSpecializationExpr>(TC->getImmediatelyDeclaredConstraint());
1944   bool Dependent =
1945       Constraint->getTemplateArgsAsWritten() &&
1946       TemplateSpecializationType::anyInstantiationDependentTemplateArguments(
1947           Constraint->getTemplateArgsAsWritten()->arguments().drop_front(1));
1948   TypeConstraintInfo.setInt(Dependent ? true : false);
1949 }
1950
1951 concepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) :
1952     Requirement(RK_Type, T->getType()->isInstantiationDependentType(),
1953                 T->getType()->containsUnexpandedParameterPack(),
1954                 // We reach this ctor with either dependent types (in which
1955                 // IsSatisfied doesn't matter) or with non-dependent type in
1956                 // which the existence of the type indicates satisfaction.
1957                 /*IsSatisfied=*/true),
1958     Value(T),
1959     Status(T->getType()->isInstantiationDependentType() ? SS_Dependent
1960                                                         : SS_Satisfied) {}