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