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