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