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/ASTConcept.h"
16#include "clang/AST/ASTLambda.h"
17#include "clang/AST/DeclCXX.h"
18#include "clang/AST/ExprConcepts.h"
19#include "clang/AST/RecursiveASTVisitor.h"
20#include "clang/Basic/OperatorPrecedence.h"
21#include "clang/Sema/EnterExpressionEvaluationContext.h"
22#include "clang/Sema/Initialization.h"
23#include "clang/Sema/Overload.h"
24#include "clang/Sema/ScopeInfo.h"
25#include "clang/Sema/Sema.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 "llvm/Support/SaveAndRestore.h"
33#include "llvm/Support/TimeProfiler.h"
34
35using namespace clang;
36using namespace sema;
37
38namespace {
39class LogicalBinOp {
40 SourceLocation Loc;
41 OverloadedOperatorKind Op = OO_None;
42 const Expr *LHS = nullptr;
43 const Expr *RHS = nullptr;
44
45public:
46 LogicalBinOp(const Expr *E) {
47 if (auto *BO = dyn_cast<BinaryOperator>(Val: E)) {
48 Op = BinaryOperator::getOverloadedOperator(Opc: BO->getOpcode());
49 LHS = BO->getLHS();
50 RHS = BO->getRHS();
51 Loc = BO->getExprLoc();
52 } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(Val: E)) {
53 // If OO is not || or && it might not have exactly 2 arguments.
54 if (OO->getNumArgs() == 2) {
55 Op = OO->getOperator();
56 LHS = OO->getArg(Arg: 0);
57 RHS = OO->getArg(Arg: 1);
58 Loc = OO->getOperatorLoc();
59 }
60 }
61 }
62
63 bool isAnd() const { return Op == OO_AmpAmp; }
64 bool isOr() const { return Op == OO_PipePipe; }
65 explicit operator bool() const { return isAnd() || isOr(); }
66
67 const Expr *getLHS() const { return LHS; }
68 const Expr *getRHS() const { return RHS; }
69 OverloadedOperatorKind getOp() const { return Op; }
70
71 ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS) const {
72 return recreateBinOp(SemaRef, LHS, RHS: const_cast<Expr *>(getRHS()));
73 }
74
75 ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS,
76 ExprResult RHS) const {
77 assert((isAnd() || isOr()) && "Not the right kind of op?");
78 assert((!LHS.isInvalid() && !RHS.isInvalid()) && "not good expressions?");
79
80 if (!LHS.isUsable() || !RHS.isUsable())
81 return ExprEmpty();
82
83 // We should just be able to 'normalize' these to the builtin Binary
84 // Operator, since that is how they are evaluated in constriant checks.
85 return BinaryOperator::Create(C: SemaRef.Context, lhs: LHS.get(), rhs: RHS.get(),
86 opc: BinaryOperator::getOverloadedOpcode(OO: Op),
87 ResTy: SemaRef.Context.BoolTy, VK: VK_PRValue,
88 OK: OK_Ordinary, opLoc: Loc, FPFeatures: FPOptionsOverride{});
89 }
90};
91} // namespace
92
93bool Sema::CheckConstraintExpression(const Expr *ConstraintExpression,
94 Token NextToken, bool *PossibleNonPrimary,
95 bool IsTrailingRequiresClause) {
96 // C++2a [temp.constr.atomic]p1
97 // ..E shall be a constant expression of type bool.
98
99 ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts();
100
101 if (LogicalBinOp BO = ConstraintExpression) {
102 return CheckConstraintExpression(ConstraintExpression: BO.getLHS(), NextToken,
103 PossibleNonPrimary) &&
104 CheckConstraintExpression(ConstraintExpression: BO.getRHS(), NextToken,
105 PossibleNonPrimary);
106 } else if (auto *C = dyn_cast<ExprWithCleanups>(Val: ConstraintExpression))
107 return CheckConstraintExpression(ConstraintExpression: C->getSubExpr(), NextToken,
108 PossibleNonPrimary);
109
110 QualType Type = ConstraintExpression->getType();
111
112 auto CheckForNonPrimary = [&] {
113 if (!PossibleNonPrimary)
114 return;
115
116 *PossibleNonPrimary =
117 // We have the following case:
118 // template<typename> requires func(0) struct S { };
119 // The user probably isn't aware of the parentheses required around
120 // the function call, and we're only going to parse 'func' as the
121 // primary-expression, and complain that it is of non-bool type.
122 //
123 // However, if we're in a lambda, this might also be:
124 // []<typename> requires var () {};
125 // Which also looks like a function call due to the lambda parentheses,
126 // but unlike the first case, isn't an error, so this check is skipped.
127 (NextToken.is(K: tok::l_paren) &&
128 (IsTrailingRequiresClause ||
129 (Type->isDependentType() &&
130 isa<UnresolvedLookupExpr>(Val: ConstraintExpression) &&
131 !dyn_cast_if_present<LambdaScopeInfo>(Val: getCurFunction())) ||
132 Type->isFunctionType() ||
133 Type->isSpecificBuiltinType(K: BuiltinType::Overload))) ||
134 // We have the following case:
135 // template<typename T> requires size_<T> == 0 struct S { };
136 // The user probably isn't aware of the parentheses required around
137 // the binary operator, and we're only going to parse 'func' as the
138 // first operand, and complain that it is of non-bool type.
139 getBinOpPrecedence(Kind: NextToken.getKind(),
140 /*GreaterThanIsOperator=*/true,
141 CPlusPlus11: getLangOpts().CPlusPlus11) > prec::LogicalAnd;
142 };
143
144 // An atomic constraint!
145 if (ConstraintExpression->isTypeDependent()) {
146 CheckForNonPrimary();
147 return true;
148 }
149
150 if (!Context.hasSameUnqualifiedType(T1: Type, T2: Context.BoolTy)) {
151 Diag(Loc: ConstraintExpression->getExprLoc(),
152 DiagID: diag::err_non_bool_atomic_constraint)
153 << Type << ConstraintExpression->getSourceRange();
154 CheckForNonPrimary();
155 return false;
156 }
157
158 if (PossibleNonPrimary)
159 *PossibleNonPrimary = false;
160 return true;
161}
162
163namespace {
164struct SatisfactionStackRAII {
165 Sema &SemaRef;
166 bool Inserted = false;
167 SatisfactionStackRAII(Sema &SemaRef, const NamedDecl *ND,
168 const llvm::FoldingSetNodeID &FSNID)
169 : SemaRef(SemaRef) {
170 if (ND) {
171 SemaRef.PushSatisfactionStackEntry(D: ND, ID: FSNID);
172 Inserted = true;
173 }
174 }
175 ~SatisfactionStackRAII() {
176 if (Inserted)
177 SemaRef.PopSatisfactionStackEntry();
178 }
179};
180} // namespace
181
182static bool DiagRecursiveConstraintEval(
183 Sema &S, llvm::FoldingSetNodeID &ID, const NamedDecl *Templ, const Expr *E,
184 const MultiLevelTemplateArgumentList *MLTAL = nullptr) {
185 E->Profile(ID, Context: S.Context, /*Canonical=*/true);
186 if (MLTAL) {
187 for (const auto &List : *MLTAL)
188 for (const auto &TemplateArg : List.Args)
189 S.Context.getCanonicalTemplateArgument(Arg: TemplateArg)
190 .Profile(ID, Context: S.Context);
191 }
192 if (S.SatisfactionStackContains(D: Templ, ID)) {
193 S.Diag(Loc: E->getExprLoc(), DiagID: diag::err_constraint_depends_on_self)
194 << E << E->getSourceRange();
195 return true;
196 }
197 return false;
198}
199
200// Figure out the to-translation-unit depth for this function declaration for
201// the purpose of seeing if they differ by constraints. This isn't the same as
202// getTemplateDepth, because it includes already instantiated parents.
203static unsigned
204CalculateTemplateDepthForConstraints(Sema &S, const NamedDecl *ND,
205 bool SkipForSpecialization = false) {
206 MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
207 D: ND, DC: ND->getLexicalDeclContext(), /*Final=*/false,
208 /*Innermost=*/std::nullopt,
209 /*RelativeToPrimary=*/true,
210 /*Pattern=*/nullptr,
211 /*ForConstraintInstantiation=*/true, SkipForSpecialization);
212 return MLTAL.getNumLevels();
213}
214
215namespace {
216class AdjustConstraints : public TreeTransform<AdjustConstraints> {
217 unsigned TemplateDepth = 0;
218
219 bool RemoveNonPackExpansionPacks = false;
220
221public:
222 using inherited = TreeTransform<AdjustConstraints>;
223 AdjustConstraints(Sema &SemaRef, unsigned TemplateDepth,
224 bool RemoveNonPackExpansionPacks = false)
225 : inherited(SemaRef), TemplateDepth(TemplateDepth),
226 RemoveNonPackExpansionPacks(RemoveNonPackExpansionPacks) {}
227
228 ExprResult RebuildPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc,
229 UnsignedOrNone NumExpansions) {
230 return inherited::RebuildPackExpansion(Pattern, EllipsisLoc, NumExpansions);
231 }
232
233 TemplateArgumentLoc RebuildPackExpansion(TemplateArgumentLoc Pattern,
234 SourceLocation EllipsisLoc,
235 UnsignedOrNone NumExpansions) {
236 if (!RemoveNonPackExpansionPacks)
237 return inherited::RebuildPackExpansion(Pattern, EllipsisLoc,
238 NumExpansions);
239 return Pattern;
240 }
241
242 bool PreparePackForExpansion(TemplateArgumentLoc In, bool Uneval,
243 TemplateArgumentLoc &Out, UnexpandedInfo &Info) {
244 if (!RemoveNonPackExpansionPacks)
245 return inherited::PreparePackForExpansion(In, Uneval, Out, Info);
246 assert(In.getArgument().isPackExpansion());
247 Out = In;
248 Info.Expand = false;
249 return false;
250 }
251
252 using inherited::TransformTemplateTypeParmType;
253 QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
254 TemplateTypeParmTypeLoc TL, bool) {
255 const TemplateTypeParmType *T = TL.getTypePtr();
256
257 TemplateTypeParmDecl *NewTTPDecl = nullptr;
258 if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())
259 NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(
260 Val: TransformDecl(Loc: TL.getNameLoc(), D: OldTTPDecl));
261
262 QualType Result = getSema().Context.getTemplateTypeParmType(
263 Depth: T->getDepth() + TemplateDepth, Index: T->getIndex(),
264 ParameterPack: RemoveNonPackExpansionPacks ? false : T->isParameterPack(), ParmDecl: NewTTPDecl);
265 TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(T: Result);
266 NewTL.setNameLoc(TL.getNameLoc());
267 return Result;
268 }
269
270 bool AlreadyTransformed(QualType T) {
271 if (T.isNull())
272 return true;
273
274 if (T->isInstantiationDependentType() || T->isVariablyModifiedType() ||
275 T->containsUnexpandedParameterPack())
276 return false;
277 return true;
278 }
279};
280} // namespace
281
282namespace {
283
284// FIXME: Convert it to DynamicRecursiveASTVisitor
285class HashParameterMapping : public RecursiveASTVisitor<HashParameterMapping> {
286 using inherited = RecursiveASTVisitor<HashParameterMapping>;
287 friend inherited;
288
289 Sema &SemaRef;
290 const MultiLevelTemplateArgumentList &TemplateArgs;
291 llvm::FoldingSetNodeID &ID;
292 llvm::SmallVector<TemplateArgument, 10> UsedTemplateArgs;
293
294 UnsignedOrNone OuterPackSubstIndex;
295
296 bool shouldVisitTemplateInstantiations() const { return true; }
297
298public:
299 HashParameterMapping(Sema &SemaRef,
300 const MultiLevelTemplateArgumentList &TemplateArgs,
301 llvm::FoldingSetNodeID &ID,
302 UnsignedOrNone OuterPackSubstIndex)
303 : SemaRef(SemaRef), TemplateArgs(TemplateArgs), ID(ID),
304 OuterPackSubstIndex(OuterPackSubstIndex) {}
305
306 bool VisitTemplateTypeParmType(TemplateTypeParmType *T) {
307 // A lambda expression can introduce template parameters that don't have
308 // corresponding template arguments yet.
309 if (T->getDepth() >= TemplateArgs.getNumLevels())
310 return true;
311
312 // There might not be a corresponding template argument before substituting
313 // into the parameter mapping, e.g. a sizeof... expression.
314 if (!TemplateArgs.hasTemplateArgument(Depth: T->getDepth(), Index: T->getIndex()))
315 return true;
316
317 TemplateArgument Arg = TemplateArgs(T->getDepth(), T->getIndex());
318
319 // In concept parameter mapping for fold expressions, packs that aren't
320 // expanded in place are treated as having non-pack dependency, so that
321 // a PackExpansionType won't prevent expanding the packs outside the
322 // TreeTransform. However we still need to check the pack at this point.
323 if ((T->isParameterPack() ||
324 (T->getDecl() && T->getDecl()->isTemplateParameterPack())) &&
325 SemaRef.ArgPackSubstIndex) {
326 assert(Arg.getKind() == TemplateArgument::Pack &&
327 "Missing argument pack");
328
329 Arg = SemaRef.getPackSubstitutedTemplateArgument(Arg);
330 }
331
332 UsedTemplateArgs.push_back(
333 Elt: SemaRef.Context.getCanonicalTemplateArgument(Arg));
334 return true;
335 }
336
337 bool VisitDeclRefExpr(DeclRefExpr *E) {
338 NamedDecl *D = E->getDecl();
339 NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(Val: D);
340 if (!NTTP)
341 return TraverseDecl(D);
342
343 if (NTTP->getDepth() >= TemplateArgs.getNumLevels())
344 return true;
345
346 if (!TemplateArgs.hasTemplateArgument(Depth: NTTP->getDepth(), Index: NTTP->getIndex()))
347 return true;
348
349 TemplateArgument Arg = TemplateArgs(NTTP->getDepth(), NTTP->getPosition());
350 if (NTTP->isParameterPack() && SemaRef.ArgPackSubstIndex) {
351 assert(Arg.getKind() == TemplateArgument::Pack &&
352 "Missing argument pack");
353 Arg = SemaRef.getPackSubstitutedTemplateArgument(Arg);
354 }
355
356 UsedTemplateArgs.push_back(
357 Elt: SemaRef.Context.getCanonicalTemplateArgument(Arg));
358 return true;
359 }
360
361 bool VisitTypedefType(TypedefType *TT) {
362 return inherited::TraverseType(T: TT->desugar());
363 }
364
365 bool TraverseDecl(Decl *D) {
366 if (auto *VD = dyn_cast<ValueDecl>(Val: D)) {
367 if (auto *Var = dyn_cast<VarDecl>(Val: VD))
368 TraverseStmt(S: Var->getInit());
369 return TraverseType(T: VD->getType());
370 }
371
372 return inherited::TraverseDecl(D);
373 }
374
375 bool TraverseCallExpr(CallExpr *CE) {
376 inherited::TraverseStmt(S: CE->getCallee());
377
378 for (Expr *Arg : CE->arguments())
379 inherited::TraverseStmt(S: Arg);
380
381 return true;
382 }
383
384 bool TraverseTypeLoc(TypeLoc TL, bool TraverseQualifier = true) {
385 // We don't care about TypeLocs. So traverse Types instead.
386 return TraverseType(T: TL.getType().getCanonicalType(), TraverseQualifier);
387 }
388
389 bool TraverseDependentNameType(const DependentNameType *T,
390 bool /*TraverseQualifier*/) {
391 return TraverseNestedNameSpecifier(NNS: T->getQualifier());
392 }
393
394 bool TraverseTagType(const TagType *T, bool TraverseQualifier) {
395 // T's parent can be dependent while T doesn't have any template arguments.
396 // We should have already traversed its qualifier.
397 // FIXME: Add an assert to catch cases where we failed to profile the
398 // concept.
399 return true;
400 }
401
402 bool TraverseInjectedClassNameType(InjectedClassNameType *T,
403 bool TraverseQualifier) {
404 return TraverseTemplateArguments(Args: T->getTemplateArgs(Ctx: SemaRef.Context));
405 }
406
407 bool TraverseTemplateArgument(const TemplateArgument &Arg) {
408 if (!Arg.containsUnexpandedParameterPack() || Arg.isPackExpansion()) {
409 // Act as if we are fully expanding this pack, if it is a PackExpansion.
410 Sema::ArgPackSubstIndexRAII _1(SemaRef, std::nullopt);
411 llvm::SaveAndRestore<UnsignedOrNone> _2(OuterPackSubstIndex,
412 std::nullopt);
413 return inherited::TraverseTemplateArgument(Arg);
414 }
415
416 Sema::ArgPackSubstIndexRAII _1(SemaRef, OuterPackSubstIndex);
417 return inherited::TraverseTemplateArgument(Arg);
418 }
419
420 bool TraverseSizeOfPackExpr(SizeOfPackExpr *SOPE) {
421 return TraverseDecl(D: SOPE->getPack());
422 }
423
424 bool VisitSubstNonTypeTemplateParmExpr(SubstNonTypeTemplateParmExpr *E) {
425 return inherited::TraverseStmt(S: E->getReplacement());
426 }
427
428 bool TraverseTemplateName(TemplateName Template) {
429 if (auto *TTP = dyn_cast_if_present<TemplateTemplateParmDecl>(
430 Val: Template.getAsTemplateDecl());
431 TTP && TTP->getDepth() < TemplateArgs.getNumLevels()) {
432 if (!TemplateArgs.hasTemplateArgument(Depth: TTP->getDepth(),
433 Index: TTP->getPosition()))
434 return true;
435
436 TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getPosition());
437 if (TTP->isParameterPack() && SemaRef.ArgPackSubstIndex) {
438 assert(Arg.getKind() == TemplateArgument::Pack &&
439 "Missing argument pack");
440 Arg = SemaRef.getPackSubstitutedTemplateArgument(Arg);
441 }
442 assert(!Arg.getAsTemplate().isNull() &&
443 "Null template template argument");
444 UsedTemplateArgs.push_back(
445 Elt: SemaRef.Context.getCanonicalTemplateArgument(Arg));
446 }
447 return inherited::TraverseTemplateName(Template);
448 }
449
450 void VisitConstraint(const NormalizedConstraintWithParamMapping &Constraint) {
451 if (!Constraint.hasParameterMapping()) {
452 for (const auto &List : TemplateArgs)
453 for (const TemplateArgument &Arg : List.Args)
454 SemaRef.Context.getCanonicalTemplateArgument(Arg).Profile(
455 ID, Context: SemaRef.Context);
456 return;
457 }
458
459 llvm::ArrayRef<TemplateArgumentLoc> Mapping =
460 Constraint.getParameterMapping();
461 for (auto &ArgLoc : Mapping) {
462 TemplateArgument Canonical =
463 SemaRef.Context.getCanonicalTemplateArgument(Arg: ArgLoc.getArgument());
464 // We don't want sugars to impede the profile of cache.
465 UsedTemplateArgs.push_back(Elt: Canonical);
466 TraverseTemplateArgument(Arg: Canonical);
467 }
468
469 for (auto &Used : UsedTemplateArgs) {
470 llvm::FoldingSetNodeID R;
471 Used.Profile(ID&: R, Context: SemaRef.Context);
472 ID.AddNodeID(ID: R);
473 }
474 }
475};
476
477class ConstraintSatisfactionChecker {
478 Sema &S;
479 const NamedDecl *Template;
480 SourceLocation TemplateNameLoc;
481 UnsignedOrNone PackSubstitutionIndex;
482 ConstraintSatisfaction &Satisfaction;
483 bool BuildExpression;
484
485 // The most closest concept declaration when evaluating atomic constriants.
486 // This is to make sure that lambdas in the atomic expression live in the
487 // right context.
488 ConceptDecl *ParentConcept = nullptr;
489
490private:
491 template <class Constraint>
492 UnsignedOrNone getOuterPackIndex(const Constraint &C) const {
493 return C.getPackSubstitutionIndex() ? C.getPackSubstitutionIndex()
494 : PackSubstitutionIndex;
495 }
496
497 ExprResult
498 EvaluateAtomicConstraint(const Expr *AtomicExpr,
499 const MultiLevelTemplateArgumentList &MLTAL);
500
501 UnsignedOrNone EvaluateFoldExpandedConstraintSize(
502 const FoldExpandedConstraint &FE,
503 const MultiLevelTemplateArgumentList &MLTAL);
504
505 // XXX: It is SLOW! Use it very carefully.
506 std::optional<MultiLevelTemplateArgumentList> SubstitutionInTemplateArguments(
507 const NormalizedConstraintWithParamMapping &Constraint,
508 const MultiLevelTemplateArgumentList &MLTAL,
509 llvm::SmallVector<TemplateArgument> &SubstitutedOuterMost);
510
511 ExprResult EvaluateSlow(const AtomicConstraint &Constraint,
512 const MultiLevelTemplateArgumentList &MLTAL);
513
514 ExprResult Evaluate(const AtomicConstraint &Constraint,
515 const MultiLevelTemplateArgumentList &MLTAL);
516
517 ExprResult EvaluateSlow(const FoldExpandedConstraint &Constraint,
518 const MultiLevelTemplateArgumentList &MLTAL);
519
520 ExprResult Evaluate(const FoldExpandedConstraint &Constraint,
521 const MultiLevelTemplateArgumentList &MLTAL);
522
523 ExprResult EvaluateSlow(const ConceptIdConstraint &Constraint,
524 const MultiLevelTemplateArgumentList &MLTAL,
525 unsigned int Size);
526
527 ExprResult Evaluate(const ConceptIdConstraint &Constraint,
528 const MultiLevelTemplateArgumentList &MLTAL);
529
530 ExprResult Evaluate(const CompoundConstraint &Constraint,
531 const MultiLevelTemplateArgumentList &MLTAL);
532
533public:
534 ConstraintSatisfactionChecker(Sema &SemaRef, const NamedDecl *Template,
535 SourceLocation TemplateNameLoc,
536 UnsignedOrNone PackSubstitutionIndex,
537 ConstraintSatisfaction &Satisfaction,
538 bool BuildExpression)
539 : S(SemaRef), Template(Template), TemplateNameLoc(TemplateNameLoc),
540 PackSubstitutionIndex(PackSubstitutionIndex),
541 Satisfaction(Satisfaction), BuildExpression(BuildExpression) {}
542
543 ExprResult Evaluate(const NormalizedConstraint &Constraint,
544 const MultiLevelTemplateArgumentList &MLTAL);
545};
546
547StringRef allocateStringFromConceptDiagnostic(const Sema &S,
548 const PartialDiagnostic Diag) {
549 SmallString<128> DiagString;
550 DiagString = ": ";
551 Diag.EmitToString(Diags&: S.getDiagnostics(), Buf&: DiagString);
552 return S.getASTContext().backupStr(S: DiagString);
553}
554
555} // namespace
556
557ExprResult ConstraintSatisfactionChecker::EvaluateAtomicConstraint(
558 const Expr *AtomicExpr, const MultiLevelTemplateArgumentList &MLTAL) {
559 llvm::FoldingSetNodeID ID;
560 if (Template &&
561 DiagRecursiveConstraintEval(S, ID, Templ: Template, E: AtomicExpr, MLTAL: &MLTAL)) {
562 Satisfaction.IsSatisfied = false;
563 Satisfaction.ContainsErrors = true;
564 return ExprEmpty();
565 }
566 SatisfactionStackRAII StackRAII(S, Template, ID);
567
568 // Atomic constraint - substitute arguments and check satisfaction.
569 ExprResult SubstitutedExpression = const_cast<Expr *>(AtomicExpr);
570 {
571 TemplateDeductionInfo Info(TemplateNameLoc);
572 Sema::InstantiatingTemplate Inst(
573 S, AtomicExpr->getBeginLoc(),
574 Sema::InstantiatingTemplate::ConstraintSubstitution{},
575 // FIXME: improve const-correctness of InstantiatingTemplate
576 const_cast<NamedDecl *>(Template), AtomicExpr->getSourceRange());
577 if (Inst.isInvalid())
578 return ExprError();
579
580 // We do not want error diagnostics escaping here.
581 Sema::SFINAETrap Trap(S, Info);
582 SubstitutedExpression =
583 S.SubstConstraintExpr(E: const_cast<Expr *>(AtomicExpr), TemplateArgs: MLTAL);
584
585 if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
586 // C++2a [temp.constr.atomic]p1
587 // ...If substitution results in an invalid type or expression, the
588 // constraint is not satisfied.
589 if (!Trap.hasErrorOccurred())
590 // A non-SFINAE error has occurred as a result of this
591 // substitution.
592 return ExprError();
593
594 PartialDiagnosticAt SubstDiag{SourceLocation(),
595 PartialDiagnostic::NullDiagnostic()};
596 Info.takeSFINAEDiagnostic(PD&: SubstDiag);
597 // FIXME: This is an unfortunate consequence of there
598 // being no serialization code for PartialDiagnostics and the fact
599 // that serializing them would likely take a lot more storage than
600 // just storing them as strings. We would still like, in the
601 // future, to serialize the proper PartialDiagnostic as serializing
602 // it as a string defeats the purpose of the diagnostic mechanism.
603 Satisfaction.Details.emplace_back(
604 Args: new (S.Context) ConstraintSubstitutionDiagnostic{
605 SubstDiag.first,
606 allocateStringFromConceptDiagnostic(S, Diag: SubstDiag.second)});
607 Satisfaction.IsSatisfied = false;
608 return ExprEmpty();
609 }
610 }
611
612 if (!S.CheckConstraintExpression(ConstraintExpression: SubstitutedExpression.get()))
613 return ExprError();
614
615 // [temp.constr.atomic]p3: To determine if an atomic constraint is
616 // satisfied, the parameter mapping and template arguments are first
617 // substituted into its expression. If substitution results in an
618 // invalid type or expression, the constraint is not satisfied.
619 // Otherwise, the lvalue-to-rvalue conversion is performed if necessary,
620 // and E shall be a constant expression of type bool.
621 //
622 // Perform the L to R Value conversion if necessary. We do so for all
623 // non-PRValue categories, else we fail to extend the lifetime of
624 // temporaries, and that fails the constant expression check.
625 if (!SubstitutedExpression.get()->isPRValue())
626 SubstitutedExpression = ImplicitCastExpr::Create(
627 Context: S.Context, T: SubstitutedExpression.get()->getType(), Kind: CK_LValueToRValue,
628 Operand: SubstitutedExpression.get(),
629 /*BasePath=*/nullptr, Cat: VK_PRValue, FPO: FPOptionsOverride());
630
631 return SubstitutedExpression;
632}
633
634std::optional<MultiLevelTemplateArgumentList>
635ConstraintSatisfactionChecker::SubstitutionInTemplateArguments(
636 const NormalizedConstraintWithParamMapping &Constraint,
637 const MultiLevelTemplateArgumentList &MLTAL,
638 llvm::SmallVector<TemplateArgument> &SubstitutedOutermost) {
639
640 if (!Constraint.hasParameterMapping()) {
641 if (MLTAL.getNumSubstitutedLevels())
642 SubstitutedOutermost.assign(AR: MLTAL.getOutermost());
643 return MLTAL;
644 }
645
646 // The mapping is empty, meaning no template arguments are needed for
647 // evaluation.
648 if (Constraint.getParameterMapping().empty())
649 return MultiLevelTemplateArgumentList();
650
651 TemplateDeductionInfo Info(Constraint.getBeginLoc());
652 Sema::SFINAETrap Trap(S, Info);
653 Sema::InstantiatingTemplate Inst(
654 S, Constraint.getBeginLoc(),
655 Sema::InstantiatingTemplate::ConstraintSubstitution{},
656 // FIXME: improve const-correctness of InstantiatingTemplate
657 const_cast<NamedDecl *>(Template), Constraint.getSourceRange());
658 if (Inst.isInvalid())
659 return std::nullopt;
660
661 TemplateArgumentListInfo SubstArgs;
662 Sema::ArgPackSubstIndexRAII SubstIndex(
663 S, Constraint.getPackSubstitutionIndex()
664 ? Constraint.getPackSubstitutionIndex()
665 : PackSubstitutionIndex);
666
667 if (S.SubstTemplateArgumentsInParameterMapping(
668 Args: Constraint.getParameterMapping(), BaseLoc: Constraint.getBeginLoc(), TemplateArgs: MLTAL,
669 Out&: SubstArgs)) {
670 Satisfaction.IsSatisfied = false;
671 return std::nullopt;
672 }
673
674 Sema::CheckTemplateArgumentInfo CTAI;
675 auto *TD = const_cast<TemplateDecl *>(
676 cast<TemplateDecl>(Val: Constraint.getConstraintDecl()));
677 if (S.CheckTemplateArgumentList(Template: TD, Params: Constraint.getUsedTemplateParamList(),
678 TemplateLoc: TD->getLocation(), TemplateArgs&: SubstArgs,
679 /*DefaultArguments=*/DefaultArgs: {},
680 /*PartialTemplateArgs=*/false, CTAI))
681 return std::nullopt;
682 const NormalizedConstraint::OccurenceList &Used =
683 Constraint.mappingOccurenceList();
684 // The empty MLTAL situation should only occur when evaluating non-dependent
685 // constraints.
686 if (MLTAL.getNumSubstitutedLevels())
687 SubstitutedOutermost =
688 llvm::to_vector_of<TemplateArgument>(Range: MLTAL.getOutermost());
689 unsigned Offset = 0;
690 for (unsigned I = 0, MappedIndex = 0; I < Used.size(); I++) {
691 TemplateArgument Arg;
692 if (Used[I])
693 Arg = S.Context.getCanonicalTemplateArgument(
694 Arg: CTAI.SugaredConverted[MappedIndex++]);
695 if (I < SubstitutedOutermost.size()) {
696 SubstitutedOutermost[I] = Arg;
697 Offset = I + 1;
698 } else {
699 SubstitutedOutermost.push_back(Elt: Arg);
700 Offset = SubstitutedOutermost.size();
701 }
702 }
703 if (Offset < SubstitutedOutermost.size())
704 SubstitutedOutermost.erase(CI: SubstitutedOutermost.begin() + Offset);
705
706 MultiLevelTemplateArgumentList SubstitutedTemplateArgs;
707 SubstitutedTemplateArgs.addOuterTemplateArguments(AssociatedDecl: TD, Args: SubstitutedOutermost,
708 /*Final=*/false);
709 return std::move(SubstitutedTemplateArgs);
710}
711
712ExprResult ConstraintSatisfactionChecker::EvaluateSlow(
713 const AtomicConstraint &Constraint,
714 const MultiLevelTemplateArgumentList &MLTAL) {
715 std::optional<EnterExpressionEvaluationContext> EvaluationContext;
716 EvaluationContext.emplace(
717 args&: S, args: Sema::ExpressionEvaluationContext::ConstantEvaluated,
718 args: Sema::ReuseLambdaContextDecl);
719
720 llvm::SmallVector<TemplateArgument> SubstitutedOutermost;
721 std::optional<MultiLevelTemplateArgumentList> SubstitutedArgs =
722 SubstitutionInTemplateArguments(Constraint, MLTAL, SubstitutedOutermost);
723 if (!SubstitutedArgs) {
724 Satisfaction.IsSatisfied = false;
725 return ExprEmpty();
726 }
727
728 // Note that generic lambdas inside requires body require a lambda context
729 // decl from which to fetch correct template arguments. But we don't have any
730 // proper decls because the constraints are already normalized.
731 if (ParentConcept) {
732 // FIXME: the evaluation context should learn to track template arguments
733 // separately from a Decl.
734 EvaluationContext.emplace(
735 args&: S, args: Sema::ExpressionEvaluationContext::ConstantEvaluated,
736 /*LambdaContextDecl=*/
737 args: ImplicitConceptSpecializationDecl::Create(
738 C: S.Context, DC: ParentConcept->getDeclContext(),
739 SL: ParentConcept->getBeginLoc(), ConvertedArgs: SubstitutedOutermost));
740 }
741
742 Sema::ArgPackSubstIndexRAII SubstIndex(S, PackSubstitutionIndex);
743 ExprResult SubstitutedAtomicExpr = EvaluateAtomicConstraint(
744 AtomicExpr: Constraint.getConstraintExpr(), MLTAL: *SubstitutedArgs);
745
746 if (SubstitutedAtomicExpr.isInvalid())
747 return ExprError();
748
749 if (SubstitutedAtomicExpr.isUnset())
750 // Evaluator has decided satisfaction without yielding an expression.
751 return ExprEmpty();
752
753 // We don't have the ability to evaluate this, since it contains a
754 // RecoveryExpr, so we want to fail overload resolution. Otherwise,
755 // we'd potentially pick up a different overload, and cause confusing
756 // diagnostics. SO, add a failure detail that will cause us to make this
757 // overload set not viable.
758 if (SubstitutedAtomicExpr.get()->containsErrors()) {
759 Satisfaction.IsSatisfied = false;
760 Satisfaction.ContainsErrors = true;
761
762 PartialDiagnostic Msg = S.PDiag(DiagID: diag::note_constraint_references_error);
763 Satisfaction.Details.emplace_back(
764 Args: new (S.Context) ConstraintSubstitutionDiagnostic{
765 SubstitutedAtomicExpr.get()->getBeginLoc(),
766 allocateStringFromConceptDiagnostic(S, Diag: Msg)});
767 return SubstitutedAtomicExpr;
768 }
769
770 if (SubstitutedAtomicExpr.get()->isValueDependent()) {
771 Satisfaction.IsSatisfied = true;
772 Satisfaction.ContainsErrors = false;
773 return SubstitutedAtomicExpr;
774 }
775
776 SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;
777 Expr::EvalResult EvalResult;
778 EvalResult.Diag = &EvaluationDiags;
779 if (!SubstitutedAtomicExpr.get()->EvaluateAsConstantExpr(Result&: EvalResult,
780 Ctx: S.Context) ||
781 !EvaluationDiags.empty()) {
782 // C++2a [temp.constr.atomic]p1
783 // ...E shall be a constant expression of type bool.
784 S.Diag(Loc: SubstitutedAtomicExpr.get()->getBeginLoc(),
785 DiagID: diag::err_non_constant_constraint_expression)
786 << SubstitutedAtomicExpr.get()->getSourceRange();
787 for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
788 S.Diag(Loc: PDiag.first, PD: PDiag.second);
789 return ExprError();
790 }
791
792 assert(EvalResult.Val.isInt() &&
793 "evaluating bool expression didn't produce int");
794 Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
795 if (!Satisfaction.IsSatisfied)
796 Satisfaction.Details.emplace_back(Args: SubstitutedAtomicExpr.get());
797
798 return SubstitutedAtomicExpr;
799}
800
801ExprResult ConstraintSatisfactionChecker::Evaluate(
802 const AtomicConstraint &Constraint,
803 const MultiLevelTemplateArgumentList &MLTAL) {
804
805 unsigned Size = Satisfaction.Details.size();
806 llvm::FoldingSetNodeID ID;
807 ID.AddPointer(Ptr: Constraint.getConstraintExpr());
808 ID.AddInteger(
809 I: Constraint.getPackSubstitutionIndex().toInternalRepresentation());
810 ID.AddInteger(I: PackSubstitutionIndex.toInternalRepresentation());
811 HashParameterMapping(S, MLTAL, ID, getOuterPackIndex(C: Constraint))
812 .VisitConstraint(Constraint);
813
814 if (auto Iter = S.UnsubstitutedConstraintSatisfactionCache.find(Val: ID);
815 Iter != S.UnsubstitutedConstraintSatisfactionCache.end()) {
816 auto &Cached = Iter->second.Satisfaction;
817 Satisfaction.ContainsErrors = Cached.ContainsErrors;
818 Satisfaction.IsSatisfied = Cached.IsSatisfied;
819 Satisfaction.Details.insert(I: Satisfaction.Details.begin() + Size,
820 From: Cached.Details.begin(), To: Cached.Details.end());
821 return Iter->second.SubstExpr;
822 }
823
824 ExprResult E = EvaluateSlow(Constraint, MLTAL);
825
826 UnsubstitutedConstraintSatisfactionCacheResult Cache;
827 Cache.Satisfaction.ContainsErrors = Satisfaction.ContainsErrors;
828 Cache.Satisfaction.IsSatisfied = Satisfaction.IsSatisfied;
829 Cache.Satisfaction.Details.insert(I: Cache.Satisfaction.Details.end(),
830 From: Satisfaction.Details.begin() + Size,
831 To: Satisfaction.Details.end());
832 Cache.SubstExpr = E;
833 S.UnsubstitutedConstraintSatisfactionCache.insert(KV: {ID, std::move(Cache)});
834
835 return E;
836}
837
838UnsignedOrNone
839ConstraintSatisfactionChecker::EvaluateFoldExpandedConstraintSize(
840 const FoldExpandedConstraint &FE,
841 const MultiLevelTemplateArgumentList &MLTAL) {
842
843 Expr *Pattern = const_cast<Expr *>(FE.getPattern());
844
845 SmallVector<UnexpandedParameterPack, 2> Unexpanded;
846 S.collectUnexpandedParameterPacks(E: Pattern, Unexpanded);
847 assert(!Unexpanded.empty() && "Pack expansion without parameter packs?");
848 bool Expand = true;
849 bool RetainExpansion = false;
850 UnsignedOrNone NumExpansions(std::nullopt);
851 if (S.CheckParameterPacksForExpansion(
852 EllipsisLoc: Pattern->getExprLoc(), PatternRange: Pattern->getSourceRange(), Unexpanded, TemplateArgs: MLTAL,
853 /*FailOnPackProducingTemplates=*/false, ShouldExpand&: Expand, RetainExpansion,
854 NumExpansions, /*Diagnose=*/false) ||
855 !Expand || RetainExpansion)
856 return std::nullopt;
857
858 if (NumExpansions && S.getLangOpts().BracketDepth < *NumExpansions)
859 return std::nullopt;
860 return NumExpansions;
861}
862
863ExprResult ConstraintSatisfactionChecker::EvaluateSlow(
864 const FoldExpandedConstraint &Constraint,
865 const MultiLevelTemplateArgumentList &MLTAL) {
866
867 bool Conjunction = Constraint.getFoldOperator() ==
868 FoldExpandedConstraint::FoldOperatorKind::And;
869 unsigned EffectiveDetailEndIndex = Satisfaction.Details.size();
870
871 llvm::SmallVector<TemplateArgument> SubstitutedOutermost;
872 // FIXME: Is PackSubstitutionIndex correct?
873 llvm::SaveAndRestore _(PackSubstitutionIndex, S.ArgPackSubstIndex);
874 std::optional<MultiLevelTemplateArgumentList> SubstitutedArgs =
875 SubstitutionInTemplateArguments(
876 Constraint: static_cast<const NormalizedConstraintWithParamMapping &>(Constraint),
877 MLTAL, SubstitutedOutermost);
878 if (!SubstitutedArgs) {
879 Satisfaction.IsSatisfied = false;
880 return ExprError();
881 }
882
883 ExprResult Out;
884 UnsignedOrNone NumExpansions =
885 EvaluateFoldExpandedConstraintSize(FE: Constraint, MLTAL: *SubstitutedArgs);
886 if (!NumExpansions)
887 return ExprEmpty();
888
889 if (*NumExpansions == 0) {
890 Satisfaction.IsSatisfied = Conjunction;
891 return ExprEmpty();
892 }
893
894 for (unsigned I = 0; I < *NumExpansions; I++) {
895 Sema::ArgPackSubstIndexRAII SubstIndex(S, I);
896 Satisfaction.IsSatisfied = false;
897 Satisfaction.ContainsErrors = false;
898 ExprResult Expr =
899 ConstraintSatisfactionChecker(S, Template, TemplateNameLoc,
900 UnsignedOrNone(I), Satisfaction,
901 /*BuildExpression=*/false)
902 .Evaluate(Constraint: Constraint.getNormalizedPattern(), MLTAL: *SubstitutedArgs);
903 if (BuildExpression && Expr.isUsable()) {
904 if (Out.isUnset())
905 Out = Expr;
906 else
907 Out = BinaryOperator::Create(C: S.Context, lhs: Out.get(), rhs: Expr.get(),
908 opc: Conjunction ? BinaryOperatorKind::BO_LAnd
909 : BinaryOperatorKind::BO_LOr,
910 ResTy: S.Context.BoolTy, VK: VK_PRValue, OK: OK_Ordinary,
911 opLoc: Constraint.getBeginLoc(),
912 FPFeatures: FPOptionsOverride{});
913 } else {
914 assert(!BuildExpression || !Satisfaction.IsSatisfied);
915 }
916 if (!Conjunction && Satisfaction.IsSatisfied) {
917 Satisfaction.Details.erase(CS: Satisfaction.Details.begin() +
918 EffectiveDetailEndIndex,
919 CE: Satisfaction.Details.end());
920 break;
921 }
922 if (Satisfaction.IsSatisfied != Conjunction)
923 return Out;
924 }
925
926 return Out;
927}
928
929ExprResult ConstraintSatisfactionChecker::Evaluate(
930 const FoldExpandedConstraint &Constraint,
931 const MultiLevelTemplateArgumentList &MLTAL) {
932
933 llvm::FoldingSetNodeID ID;
934 ID.AddPointer(Ptr: Constraint.getPattern());
935 HashParameterMapping(S, MLTAL, ID, std::nullopt).VisitConstraint(Constraint);
936
937 if (auto Iter = S.UnsubstitutedConstraintSatisfactionCache.find(Val: ID);
938 Iter != S.UnsubstitutedConstraintSatisfactionCache.end()) {
939
940 auto &Cached = Iter->second.Satisfaction;
941 Satisfaction.ContainsErrors = Cached.ContainsErrors;
942 Satisfaction.IsSatisfied = Cached.IsSatisfied;
943 Satisfaction.Details.insert(I: Satisfaction.Details.end(),
944 From: Cached.Details.begin(), To: Cached.Details.end());
945 return Iter->second.SubstExpr;
946 }
947
948 unsigned Size = Satisfaction.Details.size();
949
950 ExprResult E = EvaluateSlow(Constraint, MLTAL);
951 UnsubstitutedConstraintSatisfactionCacheResult Cache;
952 Cache.Satisfaction.ContainsErrors = Satisfaction.ContainsErrors;
953 Cache.Satisfaction.IsSatisfied = Satisfaction.IsSatisfied;
954 Cache.Satisfaction.Details.insert(I: Cache.Satisfaction.Details.end(),
955 From: Satisfaction.Details.begin() + Size,
956 To: Satisfaction.Details.end());
957 Cache.SubstExpr = E;
958 S.UnsubstitutedConstraintSatisfactionCache.insert(KV: {ID, std::move(Cache)});
959 return E;
960}
961
962ExprResult ConstraintSatisfactionChecker::EvaluateSlow(
963 const ConceptIdConstraint &Constraint,
964 const MultiLevelTemplateArgumentList &MLTAL, unsigned Size) {
965 const ConceptReference *ConceptId = Constraint.getConceptId();
966
967 llvm::SmallVector<TemplateArgument> SubstitutedOutermost;
968 std::optional<MultiLevelTemplateArgumentList> SubstitutedArgs =
969 SubstitutionInTemplateArguments(Constraint, MLTAL, SubstitutedOutermost);
970
971 if (!SubstitutedArgs) {
972 Satisfaction.IsSatisfied = false;
973 // FIXME: diagnostics?
974 return ExprError();
975 }
976
977 Sema::ArgPackSubstIndexRAII SubstIndex(
978 S, Constraint.getPackSubstitutionIndex()
979 ? Constraint.getPackSubstitutionIndex()
980 : PackSubstitutionIndex);
981
982 const ASTTemplateArgumentListInfo *Ori =
983 ConceptId->getTemplateArgsAsWritten();
984 TemplateDeductionInfo Info(TemplateNameLoc);
985 Sema::SFINAETrap Trap(S, Info);
986 Sema::InstantiatingTemplate _2(
987 S, TemplateNameLoc, Sema::InstantiatingTemplate::ConstraintSubstitution{},
988 const_cast<NamedDecl *>(Template), Constraint.getSourceRange());
989
990 TemplateArgumentListInfo OutArgs(Ori->LAngleLoc, Ori->RAngleLoc);
991 if (S.SubstTemplateArguments(Args: Ori->arguments(), TemplateArgs: *SubstitutedArgs, Outputs&: OutArgs) ||
992 Trap.hasErrorOccurred()) {
993 Satisfaction.IsSatisfied = false;
994 if (!Trap.hasErrorOccurred())
995 return ExprError();
996
997 PartialDiagnosticAt SubstDiag{SourceLocation(),
998 PartialDiagnostic::NullDiagnostic()};
999 Info.takeSFINAEDiagnostic(PD&: SubstDiag);
1000 // FIXME: This is an unfortunate consequence of there
1001 // being no serialization code for PartialDiagnostics and the fact
1002 // that serializing them would likely take a lot more storage than
1003 // just storing them as strings. We would still like, in the
1004 // future, to serialize the proper PartialDiagnostic as serializing
1005 // it as a string defeats the purpose of the diagnostic mechanism.
1006 Satisfaction.Details.insert(
1007 I: Satisfaction.Details.begin() + Size,
1008 Elt: new (S.Context) ConstraintSubstitutionDiagnostic{
1009 SubstDiag.first,
1010 allocateStringFromConceptDiagnostic(S, Diag: SubstDiag.second)});
1011 return ExprError();
1012 }
1013
1014 CXXScopeSpec SS;
1015 SS.Adopt(Other: ConceptId->getNestedNameSpecifierLoc());
1016
1017 ExprResult SubstitutedConceptId = S.CheckConceptTemplateId(
1018 SS, TemplateKWLoc: ConceptId->getTemplateKWLoc(), ConceptNameInfo: ConceptId->getConceptNameInfo(),
1019 FoundDecl: ConceptId->getFoundDecl(), NamedConcept: ConceptId->getNamedConcept(), TemplateArgs: &OutArgs,
1020 /*DoCheckConstraintSatisfaction=*/false);
1021
1022 if (SubstitutedConceptId.isInvalid() || Trap.hasErrorOccurred())
1023 return ExprError();
1024
1025 if (Size != Satisfaction.Details.size()) {
1026 Satisfaction.Details.insert(
1027 I: Satisfaction.Details.begin() + Size,
1028 Elt: UnsatisfiedConstraintRecord(
1029 SubstitutedConceptId.getAs<ConceptSpecializationExpr>()
1030 ->getConceptReference()));
1031 }
1032 return SubstitutedConceptId;
1033}
1034
1035ExprResult ConstraintSatisfactionChecker::Evaluate(
1036 const ConceptIdConstraint &Constraint,
1037 const MultiLevelTemplateArgumentList &MLTAL) {
1038
1039 const ConceptReference *ConceptId = Constraint.getConceptId();
1040 Sema::InstantiatingTemplate InstTemplate(
1041 S, ConceptId->getBeginLoc(),
1042 Sema::InstantiatingTemplate::ConstraintsCheck{},
1043 ConceptId->getNamedConcept(),
1044 // We may have empty template arguments when checking non-dependent
1045 // nested constraint expressions.
1046 // In such cases, non-SFINAE errors would have already been diagnosed
1047 // during parameter mapping substitution, so the instantiating template
1048 // arguments are less useful here.
1049 MLTAL.getNumSubstitutedLevels() ? MLTAL.getInnermost()
1050 : ArrayRef<TemplateArgument>{},
1051 Constraint.getSourceRange());
1052 if (InstTemplate.isInvalid())
1053 return ExprError();
1054
1055 llvm::SaveAndRestore PushConceptDecl(
1056 ParentConcept, cast<ConceptDecl>(Val: ConceptId->getNamedConcept()));
1057
1058 unsigned Size = Satisfaction.Details.size();
1059
1060 ExprResult E = Evaluate(Constraint: Constraint.getNormalizedConstraint(), MLTAL);
1061
1062 if (E.isInvalid()) {
1063 Satisfaction.Details.insert(I: Satisfaction.Details.begin() + Size, Elt: ConceptId);
1064 return E;
1065 }
1066
1067 // ConceptIdConstraint is only relevant for diagnostics,
1068 // so if the normalized constraint is satisfied, we should not
1069 // substitute into the constraint.
1070 if (Satisfaction.IsSatisfied)
1071 return E;
1072
1073 llvm::FoldingSetNodeID ID;
1074 ID.AddPointer(Ptr: Constraint.getConceptId());
1075 ID.AddInteger(
1076 I: Constraint.getPackSubstitutionIndex().toInternalRepresentation());
1077 ID.AddInteger(I: PackSubstitutionIndex.toInternalRepresentation());
1078 HashParameterMapping(S, MLTAL, ID, getOuterPackIndex(C: Constraint))
1079 .VisitConstraint(Constraint);
1080
1081 if (auto Iter = S.UnsubstitutedConstraintSatisfactionCache.find(Val: ID);
1082 Iter != S.UnsubstitutedConstraintSatisfactionCache.end()) {
1083
1084 auto &Cached = Iter->second.Satisfaction;
1085 Satisfaction.ContainsErrors = Cached.ContainsErrors;
1086 Satisfaction.IsSatisfied = Cached.IsSatisfied;
1087 Satisfaction.Details.insert(I: Satisfaction.Details.begin() + Size,
1088 From: Cached.Details.begin(), To: Cached.Details.end());
1089 return Iter->second.SubstExpr;
1090 }
1091
1092 ExprResult CE = EvaluateSlow(Constraint, MLTAL, Size);
1093 if (CE.isInvalid())
1094 return E;
1095 UnsubstitutedConstraintSatisfactionCacheResult Cache;
1096 Cache.Satisfaction.ContainsErrors = Satisfaction.ContainsErrors;
1097 Cache.Satisfaction.IsSatisfied = Satisfaction.IsSatisfied;
1098 Cache.Satisfaction.Details.insert(I: Cache.Satisfaction.Details.end(),
1099 From: Satisfaction.Details.begin() + Size,
1100 To: Satisfaction.Details.end());
1101 Cache.SubstExpr = CE;
1102 S.UnsubstitutedConstraintSatisfactionCache.insert(KV: {ID, std::move(Cache)});
1103 return CE;
1104}
1105
1106ExprResult ConstraintSatisfactionChecker::Evaluate(
1107 const CompoundConstraint &Constraint,
1108 const MultiLevelTemplateArgumentList &MLTAL) {
1109
1110 unsigned EffectiveDetailEndIndex = Satisfaction.Details.size();
1111
1112 bool Conjunction =
1113 Constraint.getCompoundKind() == NormalizedConstraint::CCK_Conjunction;
1114
1115 ExprResult LHS = Evaluate(Constraint: Constraint.getLHS(), MLTAL);
1116
1117 if (Conjunction && (!Satisfaction.IsSatisfied || Satisfaction.ContainsErrors))
1118 return LHS;
1119
1120 if (!Conjunction && !LHS.isInvalid() && Satisfaction.IsSatisfied &&
1121 !Satisfaction.ContainsErrors)
1122 return LHS;
1123
1124 Satisfaction.ContainsErrors = false;
1125 Satisfaction.IsSatisfied = false;
1126
1127 ExprResult RHS = Evaluate(Constraint: Constraint.getRHS(), MLTAL);
1128
1129 if (!Conjunction && !RHS.isInvalid() && Satisfaction.IsSatisfied &&
1130 !Satisfaction.ContainsErrors)
1131 Satisfaction.Details.erase(CS: Satisfaction.Details.begin() +
1132 EffectiveDetailEndIndex,
1133 CE: Satisfaction.Details.end());
1134
1135 if (!BuildExpression)
1136 return Satisfaction.ContainsErrors ? ExprError() : ExprEmpty();
1137
1138 if (!LHS.isUsable())
1139 return RHS;
1140
1141 if (!RHS.isUsable())
1142 return LHS;
1143
1144 return BinaryOperator::Create(C: S.Context, lhs: LHS.get(), rhs: RHS.get(),
1145 opc: Conjunction ? BinaryOperatorKind::BO_LAnd
1146 : BinaryOperatorKind::BO_LOr,
1147 ResTy: S.Context.BoolTy, VK: VK_PRValue, OK: OK_Ordinary,
1148 opLoc: Constraint.getBeginLoc(), FPFeatures: FPOptionsOverride{});
1149}
1150
1151ExprResult ConstraintSatisfactionChecker::Evaluate(
1152 const NormalizedConstraint &Constraint,
1153 const MultiLevelTemplateArgumentList &MLTAL) {
1154 switch (Constraint.getKind()) {
1155 case NormalizedConstraint::ConstraintKind::Atomic:
1156 return Evaluate(Constraint: static_cast<const AtomicConstraint &>(Constraint), MLTAL);
1157
1158 case NormalizedConstraint::ConstraintKind::FoldExpanded:
1159 return Evaluate(Constraint: static_cast<const FoldExpandedConstraint &>(Constraint),
1160 MLTAL);
1161
1162 case NormalizedConstraint::ConstraintKind::ConceptId:
1163 return Evaluate(Constraint: static_cast<const ConceptIdConstraint &>(Constraint),
1164 MLTAL);
1165
1166 case NormalizedConstraint::ConstraintKind::Compound:
1167 return Evaluate(Constraint: static_cast<const CompoundConstraint &>(Constraint), MLTAL);
1168 }
1169 llvm_unreachable("Unknown ConstraintKind enum");
1170}
1171
1172static bool CheckConstraintSatisfaction(
1173 Sema &S, const NamedDecl *Template,
1174 ArrayRef<AssociatedConstraint> AssociatedConstraints,
1175 const MultiLevelTemplateArgumentList &TemplateArgsLists,
1176 SourceRange TemplateIDRange, ConstraintSatisfaction &Satisfaction,
1177 Expr **ConvertedExpr, const ConceptReference *TopLevelConceptId = nullptr) {
1178
1179 if (ConvertedExpr)
1180 *ConvertedExpr = nullptr;
1181
1182 if (AssociatedConstraints.empty()) {
1183 Satisfaction.IsSatisfied = true;
1184 return false;
1185 }
1186
1187 // In the general case, we can't check satisfaction if the arguments contain
1188 // unsubstituted template parameters, even if they are purely syntactic,
1189 // because they may still turn out to be invalid after substitution.
1190 // This could be permitted in cases where this substitution will still be
1191 // attempted later and diagnosed, such as function template specializations,
1192 // but that's not the case for concept specializations.
1193 if (TemplateArgsLists.isAnyArgInstantiationDependent()) {
1194 Satisfaction.IsSatisfied = true;
1195 return false;
1196 }
1197
1198 llvm::ArrayRef<TemplateArgument> Args;
1199 if (TemplateArgsLists.getNumLevels() != 0)
1200 Args = TemplateArgsLists.getInnermost();
1201
1202 struct SynthesisContextPair {
1203 Sema::InstantiatingTemplate Inst;
1204 Sema::NonSFINAEContext NSC;
1205 SynthesisContextPair(Sema &S, NamedDecl *Template,
1206 ArrayRef<TemplateArgument> TemplateArgs,
1207 SourceRange InstantiationRange)
1208 : Inst(S, InstantiationRange.getBegin(),
1209 Sema::InstantiatingTemplate::ConstraintsCheck{}, Template,
1210 TemplateArgs, InstantiationRange),
1211 NSC(S) {}
1212 };
1213 std::optional<SynthesisContextPair> SynthesisContext;
1214 if (!TopLevelConceptId)
1215 SynthesisContext.emplace(args&: S, args: const_cast<NamedDecl *>(Template), args&: Args,
1216 args&: TemplateIDRange);
1217
1218 const NormalizedConstraint *C =
1219 S.getNormalizedAssociatedConstraints(Entity: Template, AssociatedConstraints);
1220 if (!C) {
1221 Satisfaction.IsSatisfied = false;
1222 return true;
1223 }
1224
1225 if (TopLevelConceptId)
1226 C = ConceptIdConstraint::Create(Ctx&: S.getASTContext(), ConceptId: TopLevelConceptId,
1227 SubConstraint: const_cast<NormalizedConstraint *>(C),
1228 ConstraintDecl: Template, /*CSE=*/nullptr,
1229 PackIndex: S.ArgPackSubstIndex);
1230
1231 ExprResult Res = ConstraintSatisfactionChecker(
1232 S, Template, TemplateIDRange.getBegin(),
1233 S.ArgPackSubstIndex, Satisfaction,
1234 /*BuildExpression=*/ConvertedExpr != nullptr)
1235 .Evaluate(Constraint: *C, MLTAL: TemplateArgsLists);
1236
1237 if (Res.isInvalid())
1238 return true;
1239
1240 if (Res.isUsable() && ConvertedExpr)
1241 *ConvertedExpr = Res.get();
1242
1243 return false;
1244}
1245
1246bool Sema::CheckConstraintSatisfaction(
1247 ConstrainedDeclOrNestedRequirement Entity,
1248 ArrayRef<AssociatedConstraint> AssociatedConstraints,
1249 const MultiLevelTemplateArgumentList &TemplateArgsLists,
1250 SourceRange TemplateIDRange, ConstraintSatisfaction &OutSatisfaction,
1251 const ConceptReference *TopLevelConceptId, Expr **ConvertedExpr) {
1252 llvm::TimeTraceScope TimeScope(
1253 "CheckConstraintSatisfaction", [TemplateIDRange, this] {
1254 return TemplateIDRange.printToString(SM: getSourceManager());
1255 });
1256 if (AssociatedConstraints.empty()) {
1257 OutSatisfaction.IsSatisfied = true;
1258 return false;
1259 }
1260 const auto *Template = Entity.dyn_cast<const NamedDecl *>();
1261 if (!Template) {
1262 return ::CheckConstraintSatisfaction(
1263 S&: *this, Template: nullptr, AssociatedConstraints, TemplateArgsLists,
1264 TemplateIDRange, Satisfaction&: OutSatisfaction, ConvertedExpr, TopLevelConceptId);
1265 }
1266 // Invalid templates could make their way here. Substituting them could result
1267 // in dependent expressions.
1268 if (Template->isInvalidDecl()) {
1269 OutSatisfaction.IsSatisfied = false;
1270 return true;
1271 }
1272
1273 // A list of the template argument list flattened in a predictible manner for
1274 // the purposes of caching. The ConstraintSatisfaction type is in AST so it
1275 // has no access to the MultiLevelTemplateArgumentList, so this has to happen
1276 // here.
1277 llvm::SmallVector<TemplateArgument, 4> FlattenedArgs;
1278 for (auto List : TemplateArgsLists)
1279 for (const TemplateArgument &Arg : List.Args)
1280 FlattenedArgs.emplace_back(Args: Context.getCanonicalTemplateArgument(Arg));
1281
1282 const NamedDecl *Owner = Template;
1283 if (TopLevelConceptId)
1284 Owner = TopLevelConceptId->getNamedConcept();
1285
1286 llvm::FoldingSetNodeID ID;
1287 ConstraintSatisfaction::Profile(ID, C: Context, ConstraintOwner: Owner, TemplateArgs: FlattenedArgs);
1288 void *InsertPos;
1289 if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
1290 OutSatisfaction = *Cached;
1291 return false;
1292 }
1293
1294 auto Satisfaction =
1295 std::make_unique<ConstraintSatisfaction>(args&: Owner, args&: FlattenedArgs);
1296 if (::CheckConstraintSatisfaction(
1297 S&: *this, Template, AssociatedConstraints, TemplateArgsLists,
1298 TemplateIDRange, Satisfaction&: *Satisfaction, ConvertedExpr, TopLevelConceptId)) {
1299 OutSatisfaction = std::move(*Satisfaction);
1300 return true;
1301 }
1302
1303 if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
1304 // The evaluation of this constraint resulted in us trying to re-evaluate it
1305 // recursively. This isn't really possible, except we try to form a
1306 // RecoveryExpr as a part of the evaluation. If this is the case, just
1307 // return the 'cached' version (which will have the same result), and save
1308 // ourselves the extra-insert. If it ever becomes possible to legitimately
1309 // recursively check a constraint, we should skip checking the 'inner' one
1310 // above, and replace the cached version with this one, as it would be more
1311 // specific.
1312 OutSatisfaction = *Cached;
1313 return false;
1314 }
1315
1316 // Else we can simply add this satisfaction to the list.
1317 OutSatisfaction = *Satisfaction;
1318 // We cannot use InsertPos here because CheckConstraintSatisfaction might have
1319 // invalidated it.
1320 // Note that entries of SatisfactionCache are deleted in Sema's destructor.
1321 SatisfactionCache.InsertNode(N: Satisfaction.release());
1322 return false;
1323}
1324
1325static ExprResult
1326SubstituteConceptsInConstraintExpression(Sema &S, const NamedDecl *D,
1327 const ConceptSpecializationExpr *CSE,
1328 UnsignedOrNone SubstIndex) {
1329
1330 // [C++2c] [temp.constr.normal]
1331 // Otherwise, to form CE, any non-dependent concept template argument Ai
1332 // is substituted into the constraint-expression of C.
1333 // If any such substitution results in an invalid concept-id,
1334 // the program is ill-formed; no diagnostic is required.
1335
1336 ConceptDecl *Concept = CSE->getNamedConcept()->getCanonicalDecl();
1337 Sema::ArgPackSubstIndexRAII _(S, SubstIndex);
1338
1339 const ASTTemplateArgumentListInfo *ArgsAsWritten =
1340 CSE->getTemplateArgsAsWritten();
1341 if (llvm::none_of(
1342 Range: ArgsAsWritten->arguments(), P: [&](const TemplateArgumentLoc &ArgLoc) {
1343 return !ArgLoc.getArgument().isDependent() &&
1344 ArgLoc.getArgument().isConceptOrConceptTemplateParameter();
1345 })) {
1346 return Concept->getConstraintExpr();
1347 }
1348
1349 MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
1350 D: Concept, DC: Concept->getLexicalDeclContext(),
1351 /*Final=*/false, Innermost: CSE->getTemplateArguments(),
1352 /*RelativeToPrimary=*/true,
1353 /*Pattern=*/nullptr,
1354 /*ForConstraintInstantiation=*/true);
1355 return S.SubstConceptTemplateArguments(CSE, ConstraintExpr: Concept->getConstraintExpr(),
1356 MLTAL);
1357}
1358
1359bool Sema::SetupConstraintScope(
1360 FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
1361 const MultiLevelTemplateArgumentList &MLTAL,
1362 LocalInstantiationScope &Scope) {
1363 assert(!isLambdaCallOperator(FD) &&
1364 "Use LambdaScopeForCallOperatorInstantiationRAII to handle lambda "
1365 "instantiations");
1366 if (FD->isTemplateInstantiation() && FD->getPrimaryTemplate()) {
1367 FunctionTemplateDecl *PrimaryTemplate = FD->getPrimaryTemplate();
1368 InstantiatingTemplate Inst(
1369 *this, FD->getPointOfInstantiation(),
1370 Sema::InstantiatingTemplate::ConstraintsCheck{}, PrimaryTemplate,
1371 TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
1372 SourceRange());
1373 if (Inst.isInvalid())
1374 return true;
1375
1376 // addInstantiatedParametersToScope creates a map of 'uninstantiated' to
1377 // 'instantiated' parameters and adds it to the context. For the case where
1378 // this function is a template being instantiated NOW, we also need to add
1379 // the list of current template arguments to the list so that they also can
1380 // be picked out of the map.
1381 if (auto *SpecArgs = FD->getTemplateSpecializationArgs()) {
1382 MultiLevelTemplateArgumentList JustTemplArgs(FD, SpecArgs->asArray(),
1383 /*Final=*/false);
1384 if (addInstantiatedParametersToScope(
1385 Function: FD, PatternDecl: PrimaryTemplate->getTemplatedDecl(), Scope, TemplateArgs: JustTemplArgs))
1386 return true;
1387 }
1388
1389 // If this is a member function, make sure we get the parameters that
1390 // reference the original primary template.
1391 if (FunctionTemplateDecl *FromMemTempl =
1392 PrimaryTemplate->getInstantiatedFromMemberTemplate()) {
1393 if (addInstantiatedParametersToScope(Function: FD, PatternDecl: FromMemTempl->getTemplatedDecl(),
1394 Scope, TemplateArgs: MLTAL))
1395 return true;
1396 }
1397
1398 return false;
1399 }
1400
1401 if (FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization ||
1402 FD->getTemplatedKind() == FunctionDecl::TK_DependentNonTemplate) {
1403 FunctionDecl *InstantiatedFrom =
1404 FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization
1405 ? FD->getInstantiatedFromMemberFunction()
1406 : FD->getInstantiatedFromDecl();
1407
1408 InstantiatingTemplate Inst(
1409 *this, FD->getPointOfInstantiation(),
1410 Sema::InstantiatingTemplate::ConstraintsCheck{}, InstantiatedFrom,
1411 TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
1412 SourceRange());
1413 if (Inst.isInvalid())
1414 return true;
1415
1416 // Case where this was not a template, but instantiated as a
1417 // child-function.
1418 if (addInstantiatedParametersToScope(Function: FD, PatternDecl: InstantiatedFrom, Scope, TemplateArgs: MLTAL))
1419 return true;
1420 }
1421
1422 return false;
1423}
1424
1425// This function collects all of the template arguments for the purposes of
1426// constraint-instantiation and checking.
1427std::optional<MultiLevelTemplateArgumentList>
1428Sema::SetupConstraintCheckingTemplateArgumentsAndScope(
1429 FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
1430 LocalInstantiationScope &Scope) {
1431 MultiLevelTemplateArgumentList MLTAL;
1432
1433 // Collect the list of template arguments relative to the 'primary' template.
1434 // We need the entire list, since the constraint is completely uninstantiated
1435 // at this point.
1436 MLTAL =
1437 getTemplateInstantiationArgs(D: FD, DC: FD->getLexicalDeclContext(),
1438 /*Final=*/false, /*Innermost=*/std::nullopt,
1439 /*RelativeToPrimary=*/true,
1440 /*Pattern=*/nullptr,
1441 /*ForConstraintInstantiation=*/true);
1442 // Lambdas are handled by LambdaScopeForCallOperatorInstantiationRAII.
1443 if (isLambdaCallOperator(DC: FD))
1444 return MLTAL;
1445 if (SetupConstraintScope(FD, TemplateArgs, MLTAL, Scope))
1446 return std::nullopt;
1447
1448 return MLTAL;
1449}
1450
1451bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
1452 ConstraintSatisfaction &Satisfaction,
1453 SourceLocation UsageLoc,
1454 bool ForOverloadResolution) {
1455 // Don't check constraints if the function is dependent. Also don't check if
1456 // this is a function template specialization, as the call to
1457 // CheckFunctionTemplateConstraints after this will check it
1458 // better.
1459 if (FD->isDependentContext() ||
1460 FD->getTemplatedKind() ==
1461 FunctionDecl::TK_FunctionTemplateSpecialization) {
1462 Satisfaction.IsSatisfied = true;
1463 return false;
1464 }
1465
1466 // A lambda conversion operator has the same constraints as the call operator
1467 // and constraints checking relies on whether we are in a lambda call operator
1468 // (and may refer to its parameters), so check the call operator instead.
1469 // Note that the declarations outside of the lambda should also be
1470 // considered. Turning on the 'ForOverloadResolution' flag results in the
1471 // LocalInstantiationScope not looking into its parents, but we can still
1472 // access Decls from the parents while building a lambda RAII scope later.
1473 if (const auto *MD = dyn_cast<CXXConversionDecl>(Val: FD);
1474 MD && isLambdaConversionOperator(C: const_cast<CXXConversionDecl *>(MD)))
1475 return CheckFunctionConstraints(FD: MD->getParent()->getLambdaCallOperator(),
1476 Satisfaction, UsageLoc,
1477 /*ShouldAddDeclsFromParentScope=*/ForOverloadResolution: true);
1478
1479 DeclContext *CtxToSave = const_cast<FunctionDecl *>(FD);
1480
1481 while (isLambdaCallOperator(DC: CtxToSave) || FD->isTransparentContext()) {
1482 if (isLambdaCallOperator(DC: CtxToSave))
1483 CtxToSave = CtxToSave->getParent()->getParent();
1484 else
1485 CtxToSave = CtxToSave->getNonTransparentContext();
1486 }
1487
1488 ContextRAII SavedContext{*this, CtxToSave};
1489 LocalInstantiationScope Scope(*this, !ForOverloadResolution);
1490 std::optional<MultiLevelTemplateArgumentList> MLTAL =
1491 SetupConstraintCheckingTemplateArgumentsAndScope(
1492 FD: const_cast<FunctionDecl *>(FD), TemplateArgs: {}, Scope);
1493
1494 if (!MLTAL)
1495 return true;
1496
1497 Qualifiers ThisQuals;
1498 CXXRecordDecl *Record = nullptr;
1499 if (auto *Method = dyn_cast<CXXMethodDecl>(Val: FD)) {
1500 ThisQuals = Method->getMethodQualifiers();
1501 Record = const_cast<CXXRecordDecl *>(Method->getParent());
1502 }
1503 CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
1504
1505 LambdaScopeForCallOperatorInstantiationRAII LambdaScope(
1506 *this, const_cast<FunctionDecl *>(FD), *MLTAL, Scope,
1507 ForOverloadResolution);
1508
1509 return CheckConstraintSatisfaction(
1510 Entity: FD, AssociatedConstraints: FD->getTrailingRequiresClause(), TemplateArgsLists: *MLTAL,
1511 TemplateIDRange: SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
1512 OutSatisfaction&: Satisfaction);
1513}
1514
1515static const Expr *SubstituteConstraintExpressionWithoutSatisfaction(
1516 Sema &S, const Sema::TemplateCompareNewDeclInfo &DeclInfo,
1517 const Expr *ConstrExpr) {
1518 MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
1519 D: DeclInfo.getDecl(), DC: DeclInfo.getDeclContext(), /*Final=*/false,
1520 /*Innermost=*/std::nullopt,
1521 /*RelativeToPrimary=*/true,
1522 /*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true,
1523 /*SkipForSpecialization*/ false);
1524
1525 if (MLTAL.getNumSubstitutedLevels() == 0)
1526 return ConstrExpr;
1527
1528 Sema::NonSFINAEContext _(S);
1529 Sema::InstantiatingTemplate Inst(
1530 S, DeclInfo.getLocation(),
1531 Sema::InstantiatingTemplate::ConstraintNormalization{},
1532 const_cast<NamedDecl *>(DeclInfo.getDecl()), SourceRange{});
1533 if (Inst.isInvalid())
1534 return nullptr;
1535
1536 // Set up a dummy 'instantiation' scope in the case of reference to function
1537 // parameters that the surrounding function hasn't been instantiated yet. Note
1538 // this may happen while we're comparing two templates' constraint
1539 // equivalence.
1540 std::optional<LocalInstantiationScope> ScopeForParameters;
1541 if (const NamedDecl *ND = DeclInfo.getDecl();
1542 ND && ND->isFunctionOrFunctionTemplate()) {
1543 ScopeForParameters.emplace(args&: S, /*CombineWithOuterScope=*/args: true);
1544 const FunctionDecl *FD = ND->getAsFunction();
1545 if (FunctionTemplateDecl *Template = FD->getDescribedFunctionTemplate();
1546 Template && Template->getInstantiatedFromMemberTemplate())
1547 FD = Template->getInstantiatedFromMemberTemplate()->getTemplatedDecl();
1548 for (auto *PVD : FD->parameters()) {
1549 if (ScopeForParameters->getInstantiationOfIfExists(D: PVD))
1550 continue;
1551 if (!PVD->isParameterPack()) {
1552 ScopeForParameters->InstantiatedLocal(D: PVD, Inst: PVD);
1553 continue;
1554 }
1555 // This is hacky: we're mapping the parameter pack to a size-of-1 argument
1556 // to avoid building SubstTemplateTypeParmPackTypes for
1557 // PackExpansionTypes. The SubstTemplateTypeParmPackType node would
1558 // otherwise reference the AssociatedDecl of the template arguments, which
1559 // is, in this case, the template declaration.
1560 //
1561 // However, as we are in the process of comparing potential
1562 // re-declarations, the canonical declaration is the declaration itself at
1563 // this point. So if we didn't expand these packs, we would end up with an
1564 // incorrect profile difference because we will be profiling the
1565 // canonical types!
1566 //
1567 // FIXME: Improve the "no-transform" machinery in FindInstantiatedDecl so
1568 // that we can eliminate the Scope in the cases where the declarations are
1569 // not necessarily instantiated. It would also benefit the noexcept
1570 // specifier comparison.
1571 ScopeForParameters->MakeInstantiatedLocalArgPack(D: PVD);
1572 ScopeForParameters->InstantiatedLocalPackArg(D: PVD, Inst: PVD);
1573 }
1574 }
1575
1576 std::optional<Sema::CXXThisScopeRAII> ThisScope;
1577
1578 // See TreeTransform::RebuildTemplateSpecializationType. A context scope is
1579 // essential for having an injected class as the canonical type for a template
1580 // specialization type at the rebuilding stage. This guarantees that, for
1581 // out-of-line definitions, injected class name types and their equivalent
1582 // template specializations can be profiled to the same value, which makes it
1583 // possible that e.g. constraints involving C<Class<T>> and C<Class> are
1584 // perceived identical.
1585 std::optional<Sema::ContextRAII> ContextScope;
1586 const DeclContext *DC = [&] {
1587 if (!DeclInfo.getDecl())
1588 return DeclInfo.getDeclContext();
1589 return DeclInfo.getDecl()->getFriendObjectKind()
1590 ? DeclInfo.getLexicalDeclContext()
1591 : DeclInfo.getDeclContext();
1592 }();
1593 if (auto *RD = dyn_cast<CXXRecordDecl>(Val: DC)) {
1594 ThisScope.emplace(args&: S, args: const_cast<CXXRecordDecl *>(RD), args: Qualifiers());
1595 ContextScope.emplace(args&: S, args: const_cast<DeclContext *>(cast<DeclContext>(Val: RD)),
1596 /*NewThisContext=*/args: false);
1597 }
1598 EnterExpressionEvaluationContext UnevaluatedContext(
1599 S, Sema::ExpressionEvaluationContext::Unevaluated,
1600 Sema::ReuseLambdaContextDecl);
1601 ExprResult SubstConstr = S.SubstConstraintExprWithoutSatisfaction(
1602 E: const_cast<clang::Expr *>(ConstrExpr), TemplateArgs: MLTAL);
1603 if (!SubstConstr.isUsable())
1604 return nullptr;
1605 return SubstConstr.get();
1606}
1607
1608bool Sema::AreConstraintExpressionsEqual(const NamedDecl *Old,
1609 const Expr *OldConstr,
1610 const TemplateCompareNewDeclInfo &New,
1611 const Expr *NewConstr) {
1612 if (OldConstr == NewConstr)
1613 return true;
1614 // C++ [temp.constr.decl]p4
1615 if (Old && !New.isInvalid() && !New.ContainsDecl(ND: Old) &&
1616 Old->getLexicalDeclContext() != New.getLexicalDeclContext()) {
1617 if (const Expr *SubstConstr =
1618 SubstituteConstraintExpressionWithoutSatisfaction(S&: *this, DeclInfo: Old,
1619 ConstrExpr: OldConstr))
1620 OldConstr = SubstConstr;
1621 else
1622 return false;
1623 if (const Expr *SubstConstr =
1624 SubstituteConstraintExpressionWithoutSatisfaction(S&: *this, DeclInfo: New,
1625 ConstrExpr: NewConstr))
1626 NewConstr = SubstConstr;
1627 else
1628 return false;
1629 }
1630
1631 llvm::FoldingSetNodeID ID1, ID2;
1632 OldConstr->Profile(ID&: ID1, Context, /*Canonical=*/true);
1633 NewConstr->Profile(ID&: ID2, Context, /*Canonical=*/true);
1634 return ID1 == ID2;
1635}
1636
1637bool Sema::FriendConstraintsDependOnEnclosingTemplate(const FunctionDecl *FD) {
1638 assert(FD->getFriendObjectKind() && "Must be a friend!");
1639
1640 // The logic for non-templates is handled in ASTContext::isSameEntity, so we
1641 // don't have to bother checking 'DependsOnEnclosingTemplate' for a
1642 // non-function-template.
1643 assert(FD->getDescribedFunctionTemplate() &&
1644 "Non-function templates don't need to be checked");
1645
1646 SmallVector<AssociatedConstraint, 3> ACs;
1647 FD->getDescribedFunctionTemplate()->getAssociatedConstraints(AC&: ACs);
1648
1649 unsigned OldTemplateDepth = CalculateTemplateDepthForConstraints(S&: *this, ND: FD);
1650 for (const AssociatedConstraint &AC : ACs)
1651 if (ConstraintExpressionDependsOnEnclosingTemplate(Friend: FD, TemplateDepth: OldTemplateDepth,
1652 Constraint: AC.ConstraintExpr))
1653 return true;
1654
1655 return false;
1656}
1657
1658bool Sema::EnsureTemplateArgumentListConstraints(
1659 TemplateDecl *TD, const MultiLevelTemplateArgumentList &TemplateArgsLists,
1660 SourceRange TemplateIDRange) {
1661 ConstraintSatisfaction Satisfaction;
1662 llvm::SmallVector<AssociatedConstraint, 3> AssociatedConstraints;
1663 TD->getAssociatedConstraints(AC&: AssociatedConstraints);
1664 if (CheckConstraintSatisfaction(Entity: TD, AssociatedConstraints, TemplateArgsLists,
1665 TemplateIDRange, OutSatisfaction&: Satisfaction))
1666 return true;
1667
1668 if (!Satisfaction.IsSatisfied) {
1669 SmallString<128> TemplateArgString;
1670 TemplateArgString = " ";
1671 TemplateArgString += getTemplateArgumentBindingsText(
1672 Params: TD->getTemplateParameters(), Args: TemplateArgsLists.getInnermost().data(),
1673 NumArgs: TemplateArgsLists.getInnermost().size());
1674
1675 Diag(Loc: TemplateIDRange.getBegin(),
1676 DiagID: diag::err_template_arg_list_constraints_not_satisfied)
1677 << (int)getTemplateNameKindForDiagnostics(Name: TemplateName(TD)) << TD
1678 << TemplateArgString << TemplateIDRange;
1679 DiagnoseUnsatisfiedConstraint(Satisfaction);
1680 return true;
1681 }
1682 return false;
1683}
1684
1685static bool CheckFunctionConstraintsWithoutInstantiation(
1686 Sema &SemaRef, SourceLocation PointOfInstantiation,
1687 FunctionTemplateDecl *Template, ArrayRef<TemplateArgument> TemplateArgs,
1688 ConstraintSatisfaction &Satisfaction) {
1689 SmallVector<AssociatedConstraint, 3> TemplateAC;
1690 Template->getAssociatedConstraints(AC&: TemplateAC);
1691 if (TemplateAC.empty()) {
1692 Satisfaction.IsSatisfied = true;
1693 return false;
1694 }
1695
1696 LocalInstantiationScope Scope(SemaRef);
1697
1698 FunctionDecl *FD = Template->getTemplatedDecl();
1699 // Collect the list of template arguments relative to the 'primary'
1700 // template. We need the entire list, since the constraint is completely
1701 // uninstantiated at this point.
1702
1703 MultiLevelTemplateArgumentList MLTAL;
1704 {
1705 // getTemplateInstantiationArgs uses this instantiation context to find out
1706 // template arguments for uninstantiated functions.
1707 // We don't want this RAII object to persist, because there would be
1708 // otherwise duplicate diagnostic notes.
1709 Sema::InstantiatingTemplate Inst(
1710 SemaRef, PointOfInstantiation,
1711 Sema::InstantiatingTemplate::ConstraintsCheck{}, Template, TemplateArgs,
1712 PointOfInstantiation);
1713 if (Inst.isInvalid())
1714 return true;
1715 MLTAL = SemaRef.getTemplateInstantiationArgs(
1716 /*D=*/FD, DC: FD,
1717 /*Final=*/false, /*Innermost=*/{}, /*RelativeToPrimary=*/true,
1718 /*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true);
1719 }
1720
1721 Sema::ContextRAII SavedContext(SemaRef, FD);
1722 return SemaRef.CheckConstraintSatisfaction(
1723 Entity: Template, AssociatedConstraints: TemplateAC, TemplateArgsLists: MLTAL, TemplateIDRange: PointOfInstantiation, OutSatisfaction&: Satisfaction);
1724}
1725
1726bool Sema::CheckFunctionTemplateConstraints(
1727 SourceLocation PointOfInstantiation, FunctionDecl *Decl,
1728 ArrayRef<TemplateArgument> TemplateArgs,
1729 ConstraintSatisfaction &Satisfaction) {
1730 // In most cases we're not going to have constraints, so check for that first.
1731 FunctionTemplateDecl *Template = Decl->getPrimaryTemplate();
1732
1733 if (!Template)
1734 return ::CheckFunctionConstraintsWithoutInstantiation(
1735 SemaRef&: *this, PointOfInstantiation, Template: Decl->getDescribedFunctionTemplate(),
1736 TemplateArgs, Satisfaction);
1737
1738 // Note - code synthesis context for the constraints check is created
1739 // inside CheckConstraintsSatisfaction.
1740 SmallVector<AssociatedConstraint, 3> TemplateAC;
1741 Template->getAssociatedConstraints(AC&: TemplateAC);
1742 if (TemplateAC.empty()) {
1743 Satisfaction.IsSatisfied = true;
1744 return false;
1745 }
1746
1747 // Enter the scope of this instantiation. We don't use
1748 // PushDeclContext because we don't have a scope.
1749 Sema::ContextRAII savedContext(*this, Decl);
1750 LocalInstantiationScope Scope(*this);
1751
1752 std::optional<MultiLevelTemplateArgumentList> MLTAL =
1753 SetupConstraintCheckingTemplateArgumentsAndScope(FD: Decl, TemplateArgs,
1754 Scope);
1755
1756 if (!MLTAL)
1757 return true;
1758
1759 Qualifiers ThisQuals;
1760 CXXRecordDecl *Record = nullptr;
1761 if (auto *Method = dyn_cast<CXXMethodDecl>(Val: Decl)) {
1762 ThisQuals = Method->getMethodQualifiers();
1763 Record = Method->getParent();
1764 }
1765
1766 CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
1767 LambdaScopeForCallOperatorInstantiationRAII LambdaScope(*this, Decl, *MLTAL,
1768 Scope);
1769
1770 return CheckConstraintSatisfaction(Entity: Template, AssociatedConstraints: TemplateAC, TemplateArgsLists: *MLTAL,
1771 TemplateIDRange: PointOfInstantiation, OutSatisfaction&: Satisfaction);
1772}
1773
1774static void diagnoseUnsatisfiedRequirement(Sema &S,
1775 concepts::ExprRequirement *Req,
1776 bool First) {
1777 assert(!Req->isSatisfied() &&
1778 "Diagnose() can only be used on an unsatisfied requirement");
1779 switch (Req->getSatisfactionStatus()) {
1780 case concepts::ExprRequirement::SS_Dependent:
1781 llvm_unreachable("Diagnosing a dependent requirement");
1782 break;
1783 case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {
1784 auto *SubstDiag = Req->getExprSubstitutionDiagnostic();
1785 if (!SubstDiag->DiagMessage.empty())
1786 S.Diag(Loc: SubstDiag->DiagLoc,
1787 DiagID: diag::note_expr_requirement_expr_substitution_error)
1788 << (int)First << SubstDiag->SubstitutedEntity
1789 << SubstDiag->DiagMessage;
1790 else
1791 S.Diag(Loc: SubstDiag->DiagLoc,
1792 DiagID: diag::note_expr_requirement_expr_unknown_substitution_error)
1793 << (int)First << SubstDiag->SubstitutedEntity;
1794 break;
1795 }
1796 case concepts::ExprRequirement::SS_NoexceptNotMet:
1797 S.Diag(Loc: Req->getNoexceptLoc(), DiagID: diag::note_expr_requirement_noexcept_not_met)
1798 << (int)First << Req->getExpr();
1799 break;
1800 case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
1801 auto *SubstDiag =
1802 Req->getReturnTypeRequirement().getSubstitutionDiagnostic();
1803 if (!SubstDiag->DiagMessage.empty())
1804 S.Diag(Loc: SubstDiag->DiagLoc,
1805 DiagID: diag::note_expr_requirement_type_requirement_substitution_error)
1806 << (int)First << SubstDiag->SubstitutedEntity
1807 << SubstDiag->DiagMessage;
1808 else
1809 S.Diag(
1810 Loc: SubstDiag->DiagLoc,
1811 DiagID: diag::
1812 note_expr_requirement_type_requirement_unknown_substitution_error)
1813 << (int)First << SubstDiag->SubstitutedEntity;
1814 break;
1815 }
1816 case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {
1817 ConceptSpecializationExpr *ConstraintExpr =
1818 Req->getReturnTypeRequirementSubstitutedConstraintExpr();
1819 S.DiagnoseUnsatisfiedConstraint(ConstraintExpr);
1820 break;
1821 }
1822 case concepts::ExprRequirement::SS_Satisfied:
1823 llvm_unreachable("We checked this above");
1824 }
1825}
1826
1827static void diagnoseUnsatisfiedRequirement(Sema &S,
1828 concepts::TypeRequirement *Req,
1829 bool First) {
1830 assert(!Req->isSatisfied() &&
1831 "Diagnose() can only be used on an unsatisfied requirement");
1832 switch (Req->getSatisfactionStatus()) {
1833 case concepts::TypeRequirement::SS_Dependent:
1834 llvm_unreachable("Diagnosing a dependent requirement");
1835 return;
1836 case concepts::TypeRequirement::SS_SubstitutionFailure: {
1837 auto *SubstDiag = Req->getSubstitutionDiagnostic();
1838 if (!SubstDiag->DiagMessage.empty())
1839 S.Diag(Loc: SubstDiag->DiagLoc, DiagID: diag::note_type_requirement_substitution_error)
1840 << (int)First << SubstDiag->SubstitutedEntity
1841 << SubstDiag->DiagMessage;
1842 else
1843 S.Diag(Loc: SubstDiag->DiagLoc,
1844 DiagID: diag::note_type_requirement_unknown_substitution_error)
1845 << (int)First << SubstDiag->SubstitutedEntity;
1846 return;
1847 }
1848 default:
1849 llvm_unreachable("Unknown satisfaction status");
1850 return;
1851 }
1852}
1853
1854static void diagnoseUnsatisfiedConceptIdExpr(Sema &S,
1855 const ConceptReference *Concept,
1856 SourceLocation Loc, bool First) {
1857 if (Concept->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
1858 S.Diag(
1859 Loc,
1860 DiagID: diag::
1861 note_single_arg_concept_specialization_constraint_evaluated_to_false)
1862 << (int)First
1863 << Concept->getTemplateArgsAsWritten()->arguments()[0].getArgument()
1864 << Concept->getNamedConcept();
1865 } else {
1866 S.Diag(Loc, DiagID: diag::note_concept_specialization_constraint_evaluated_to_false)
1867 << (int)First << Concept;
1868 }
1869}
1870
1871static void diagnoseUnsatisfiedConstraintExpr(
1872 Sema &S, const UnsatisfiedConstraintRecord &Record, SourceLocation Loc,
1873 bool First, concepts::NestedRequirement *Req = nullptr);
1874
1875static void DiagnoseUnsatisfiedConstraint(
1876 Sema &S, ArrayRef<UnsatisfiedConstraintRecord> Records, SourceLocation Loc,
1877 bool First = true, concepts::NestedRequirement *Req = nullptr) {
1878 for (auto &Record : Records) {
1879 diagnoseUnsatisfiedConstraintExpr(S, Record, Loc, First, Req);
1880 Loc = {};
1881 First = isa<const ConceptReference *>(Val: Record);
1882 }
1883}
1884
1885static void diagnoseUnsatisfiedRequirement(Sema &S,
1886 concepts::NestedRequirement *Req,
1887 bool First) {
1888 DiagnoseUnsatisfiedConstraint(S, Records: Req->getConstraintSatisfaction().records(),
1889 Loc: Req->hasInvalidConstraint()
1890 ? SourceLocation()
1891 : Req->getConstraintExpr()->getExprLoc(),
1892 First, Req);
1893}
1894
1895static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
1896 const Expr *SubstExpr,
1897 bool First) {
1898 SubstExpr = SubstExpr->IgnoreParenImpCasts();
1899 if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: SubstExpr)) {
1900 switch (BO->getOpcode()) {
1901 // These two cases will in practice only be reached when using fold
1902 // expressions with || and &&, since otherwise the || and && will have been
1903 // broken down into atomic constraints during satisfaction checking.
1904 case BO_LOr:
1905 // Or evaluated to false - meaning both RHS and LHS evaluated to false.
1906 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getLHS(), First);
1907 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getRHS(),
1908 /*First=*/false);
1909 return;
1910 case BO_LAnd: {
1911 bool LHSSatisfied =
1912 BO->getLHS()->EvaluateKnownConstInt(Ctx: S.Context).getBoolValue();
1913 if (LHSSatisfied) {
1914 // LHS is true, so RHS must be false.
1915 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getRHS(), First);
1916 return;
1917 }
1918 // LHS is false
1919 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getLHS(), First);
1920
1921 // RHS might also be false
1922 bool RHSSatisfied =
1923 BO->getRHS()->EvaluateKnownConstInt(Ctx: S.Context).getBoolValue();
1924 if (!RHSSatisfied)
1925 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getRHS(),
1926 /*First=*/false);
1927 return;
1928 }
1929 case BO_GE:
1930 case BO_LE:
1931 case BO_GT:
1932 case BO_LT:
1933 case BO_EQ:
1934 case BO_NE:
1935 if (BO->getLHS()->getType()->isIntegerType() &&
1936 BO->getRHS()->getType()->isIntegerType()) {
1937 Expr::EvalResult SimplifiedLHS;
1938 Expr::EvalResult SimplifiedRHS;
1939 BO->getLHS()->EvaluateAsInt(Result&: SimplifiedLHS, Ctx: S.Context,
1940 AllowSideEffects: Expr::SE_NoSideEffects,
1941 /*InConstantContext=*/true);
1942 BO->getRHS()->EvaluateAsInt(Result&: SimplifiedRHS, Ctx: S.Context,
1943 AllowSideEffects: Expr::SE_NoSideEffects,
1944 /*InConstantContext=*/true);
1945 if (!SimplifiedLHS.Diag && !SimplifiedRHS.Diag) {
1946 S.Diag(Loc: SubstExpr->getBeginLoc(),
1947 DiagID: diag::note_atomic_constraint_evaluated_to_false_elaborated)
1948 << (int)First << SubstExpr
1949 << toString(I: SimplifiedLHS.Val.getInt(), Radix: 10)
1950 << BinaryOperator::getOpcodeStr(Op: BO->getOpcode())
1951 << toString(I: SimplifiedRHS.Val.getInt(), Radix: 10);
1952 return;
1953 }
1954 }
1955 break;
1956
1957 default:
1958 break;
1959 }
1960 } else if (auto *RE = dyn_cast<RequiresExpr>(Val: SubstExpr)) {
1961 // FIXME: RequiresExpr should store dependent diagnostics.
1962 for (concepts::Requirement *Req : RE->getRequirements())
1963 if (!Req->isDependent() && !Req->isSatisfied()) {
1964 if (auto *E = dyn_cast<concepts::ExprRequirement>(Val: Req))
1965 diagnoseUnsatisfiedRequirement(S, Req: E, First);
1966 else if (auto *T = dyn_cast<concepts::TypeRequirement>(Val: Req))
1967 diagnoseUnsatisfiedRequirement(S, Req: T, First);
1968 else
1969 diagnoseUnsatisfiedRequirement(
1970 S, Req: cast<concepts::NestedRequirement>(Val: Req), First);
1971 break;
1972 }
1973 return;
1974 } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(Val: SubstExpr)) {
1975 // Drill down concept ids treated as atomic constraints
1976 S.DiagnoseUnsatisfiedConstraint(ConstraintExpr: CSE, First);
1977 return;
1978 } else if (auto *TTE = dyn_cast<TypeTraitExpr>(Val: SubstExpr);
1979 TTE && TTE->getTrait() == clang::TypeTrait::BTT_IsDeducible) {
1980 assert(TTE->getNumArgs() == 2);
1981 S.Diag(Loc: SubstExpr->getSourceRange().getBegin(),
1982 DiagID: diag::note_is_deducible_constraint_evaluated_to_false)
1983 << TTE->getArg(I: 0)->getType() << TTE->getArg(I: 1)->getType();
1984 return;
1985 }
1986
1987 S.Diag(Loc: SubstExpr->getSourceRange().getBegin(),
1988 DiagID: diag::note_atomic_constraint_evaluated_to_false)
1989 << (int)First << SubstExpr;
1990 S.DiagnoseTypeTraitDetails(E: SubstExpr);
1991}
1992
1993static void diagnoseUnsatisfiedConstraintExpr(
1994 Sema &S, const UnsatisfiedConstraintRecord &Record, SourceLocation Loc,
1995 bool First, concepts::NestedRequirement *Req) {
1996 if (auto *Diag =
1997 Record
1998 .template dyn_cast<const ConstraintSubstitutionDiagnostic *>()) {
1999 if (Req)
2000 S.Diag(Loc: Diag->first, DiagID: diag::note_nested_requirement_substitution_error)
2001 << (int)First << Req->getInvalidConstraintEntity() << Diag->second;
2002 else
2003 S.Diag(Loc: Diag->first, DiagID: diag::note_substituted_constraint_expr_is_ill_formed)
2004 << Diag->second;
2005 return;
2006 }
2007 if (const auto *Concept = dyn_cast<const ConceptReference *>(Val: Record)) {
2008 if (Loc.isInvalid())
2009 Loc = Concept->getBeginLoc();
2010 diagnoseUnsatisfiedConceptIdExpr(S, Concept, Loc, First);
2011 return;
2012 }
2013 diagnoseWellFormedUnsatisfiedConstraintExpr(
2014 S, SubstExpr: cast<const class Expr *>(Val: Record), First);
2015}
2016
2017void Sema::DiagnoseUnsatisfiedConstraint(
2018 const ConstraintSatisfaction &Satisfaction, SourceLocation Loc,
2019 bool First) {
2020
2021 assert(!Satisfaction.IsSatisfied &&
2022 "Attempted to diagnose a satisfied constraint");
2023 ::DiagnoseUnsatisfiedConstraint(S&: *this, Records: Satisfaction.Details, Loc, First);
2024}
2025
2026void Sema::DiagnoseUnsatisfiedConstraint(
2027 const ConceptSpecializationExpr *ConstraintExpr, bool First) {
2028
2029 const ASTConstraintSatisfaction &Satisfaction =
2030 ConstraintExpr->getSatisfaction();
2031
2032 assert(!Satisfaction.IsSatisfied &&
2033 "Attempted to diagnose a satisfied constraint");
2034
2035 ::DiagnoseUnsatisfiedConstraint(S&: *this, Records: Satisfaction.records(),
2036 Loc: ConstraintExpr->getBeginLoc(), First);
2037}
2038
2039namespace {
2040
2041class SubstituteParameterMappings {
2042 Sema &SemaRef;
2043
2044 const MultiLevelTemplateArgumentList *MLTAL;
2045 const ASTTemplateArgumentListInfo *ArgsAsWritten;
2046
2047 // When normalizing a fold constraint, e.g.
2048 // C<Pack1, Pack2...> && ...
2049 // we want the TreeTransform to expand only Pack2 but not Pack1,
2050 // since Pack1 will be expanded during the evaluation of the fold expression.
2051 // This flag helps rewrite any non-PackExpansion packs into "expanded"
2052 // parameters.
2053 bool RemovePacksForFoldExpr;
2054
2055 SubstituteParameterMappings(Sema &SemaRef,
2056 const MultiLevelTemplateArgumentList *MLTAL,
2057 const ASTTemplateArgumentListInfo *ArgsAsWritten,
2058 bool RemovePacksForFoldExpr)
2059 : SemaRef(SemaRef), MLTAL(MLTAL), ArgsAsWritten(ArgsAsWritten),
2060 RemovePacksForFoldExpr(RemovePacksForFoldExpr) {}
2061
2062 void buildParameterMapping(NormalizedConstraintWithParamMapping &N);
2063
2064 bool substitute(NormalizedConstraintWithParamMapping &N);
2065
2066 bool substitute(ConceptIdConstraint &CC);
2067
2068public:
2069 SubstituteParameterMappings(Sema &SemaRef,
2070 bool RemovePacksForFoldExpr = false)
2071 : SemaRef(SemaRef), MLTAL(nullptr), ArgsAsWritten(nullptr),
2072 RemovePacksForFoldExpr(RemovePacksForFoldExpr) {}
2073
2074 bool substitute(NormalizedConstraint &N);
2075};
2076
2077void SubstituteParameterMappings::buildParameterMapping(
2078 NormalizedConstraintWithParamMapping &N) {
2079 TemplateParameterList *TemplateParams =
2080 cast<TemplateDecl>(Val: N.getConstraintDecl())->getTemplateParameters();
2081
2082 llvm::SmallBitVector OccurringIndices(TemplateParams->size());
2083 llvm::SmallBitVector OccurringIndicesForSubsumption(TemplateParams->size());
2084
2085 if (N.getKind() == NormalizedConstraint::ConstraintKind::Atomic) {
2086 SemaRef.MarkUsedTemplateParameters(
2087 E: static_cast<AtomicConstraint &>(N).getConstraintExpr(),
2088 /*OnlyDeduced=*/false,
2089 /*Depth=*/0, Used&: OccurringIndices);
2090
2091 SemaRef.MarkUsedTemplateParametersForSubsumptionParameterMapping(
2092 E: static_cast<AtomicConstraint &>(N).getConstraintExpr(),
2093 /*Depth=*/0, Used&: OccurringIndicesForSubsumption);
2094
2095 } else if (N.getKind() ==
2096 NormalizedConstraint::ConstraintKind::FoldExpanded) {
2097 SemaRef.MarkUsedTemplateParameters(
2098 E: static_cast<FoldExpandedConstraint &>(N).getPattern(),
2099 /*OnlyDeduced=*/false,
2100 /*Depth=*/0, Used&: OccurringIndices);
2101 } else if (N.getKind() == NormalizedConstraint::ConstraintKind::ConceptId) {
2102 auto *Args = static_cast<ConceptIdConstraint &>(N)
2103 .getConceptId()
2104 ->getTemplateArgsAsWritten();
2105 if (Args)
2106 SemaRef.MarkUsedTemplateParameters(TemplateArgs: Args->arguments(),
2107 /*Depth=*/0, Used&: OccurringIndices);
2108 }
2109 unsigned Size = OccurringIndices.count();
2110 // When the constraint is independent of any template parameters,
2111 // we build an empty mapping so that we can distinguish these cases
2112 // from cases where no mapping exists at all, e.g. when there are only atomic
2113 // constraints.
2114 TemplateArgumentLoc *TempArgs =
2115 new (SemaRef.Context) TemplateArgumentLoc[Size];
2116 llvm::SmallVector<NamedDecl *> UsedParams;
2117 for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I) {
2118 SourceLocation Loc = ArgsAsWritten->NumTemplateArgs > I
2119 ? ArgsAsWritten->arguments()[I].getLocation()
2120 : SourceLocation();
2121 // FIXME: Investigate why we couldn't always preserve the SourceLoc. We
2122 // can't assert Loc.isValid() now.
2123 if (OccurringIndices[I]) {
2124 NamedDecl *Param = TemplateParams->begin()[I];
2125 new (&(TempArgs)[J]) TemplateArgumentLoc(
2126 SemaRef.getIdentityTemplateArgumentLoc(Param, Location: Loc));
2127 UsedParams.push_back(Elt: Param);
2128 J++;
2129 }
2130 }
2131 auto *UsedList = TemplateParameterList::Create(
2132 C: SemaRef.Context, TemplateLoc: TemplateParams->getTemplateLoc(),
2133 LAngleLoc: TemplateParams->getLAngleLoc(), Params: UsedParams,
2134 /*RAngleLoc=*/SourceLocation(),
2135 /*RequiresClause=*/nullptr);
2136 N.updateParameterMapping(
2137 Indexes: std::move(OccurringIndices), IndexesForSubsumption: std::move(OccurringIndicesForSubsumption),
2138 Args: MutableArrayRef<TemplateArgumentLoc>{TempArgs, Size}, ParamList: UsedList);
2139}
2140
2141bool SubstituteParameterMappings::substitute(
2142 NormalizedConstraintWithParamMapping &N) {
2143 if (!N.hasParameterMapping())
2144 buildParameterMapping(N);
2145
2146 // If the parameter mapping is empty, there is nothing to substitute.
2147 if (N.getParameterMapping().empty())
2148 return false;
2149
2150 SourceLocation InstLocBegin, InstLocEnd;
2151 llvm::ArrayRef Arguments = ArgsAsWritten->arguments();
2152 if (Arguments.empty()) {
2153 InstLocBegin = ArgsAsWritten->getLAngleLoc();
2154 InstLocEnd = ArgsAsWritten->getRAngleLoc();
2155 } else {
2156 auto SR = Arguments[0].getSourceRange();
2157 InstLocBegin = SR.getBegin();
2158 InstLocEnd = SR.getEnd();
2159 }
2160 Sema::NonSFINAEContext _(SemaRef);
2161 Sema::InstantiatingTemplate Inst(
2162 SemaRef, InstLocBegin,
2163 Sema::InstantiatingTemplate::ParameterMappingSubstitution{},
2164 const_cast<NamedDecl *>(N.getConstraintDecl()),
2165 {InstLocBegin, InstLocEnd});
2166 if (Inst.isInvalid())
2167 return true;
2168
2169 // TransformTemplateArguments is unable to preserve the source location of a
2170 // pack. The SourceLocation is necessary for the instantiation location.
2171 // FIXME: The BaseLoc will be used as the location of the pack expansion,
2172 // which is wrong.
2173 TemplateArgumentListInfo SubstArgs;
2174 if (SemaRef.SubstTemplateArgumentsInParameterMapping(
2175 Args: N.getParameterMapping(), BaseLoc: N.getBeginLoc(), TemplateArgs: *MLTAL, Out&: SubstArgs))
2176 return true;
2177 Sema::CheckTemplateArgumentInfo CTAI;
2178 auto *TD =
2179 const_cast<TemplateDecl *>(cast<TemplateDecl>(Val: N.getConstraintDecl()));
2180 if (SemaRef.CheckTemplateArgumentList(Template: TD, Params: N.getUsedTemplateParamList(),
2181 TemplateLoc: TD->getLocation(), TemplateArgs&: SubstArgs,
2182 /*DefaultArguments=*/DefaultArgs: {},
2183 /*PartialTemplateArgs=*/false, CTAI))
2184 return true;
2185
2186 TemplateArgumentLoc *TempArgs =
2187 new (SemaRef.Context) TemplateArgumentLoc[CTAI.SugaredConverted.size()];
2188
2189 for (unsigned I = 0; I < CTAI.SugaredConverted.size(); ++I) {
2190 SourceLocation Loc;
2191 // If this is an empty pack, we have no corresponding SubstArgs.
2192 if (I < SubstArgs.size())
2193 Loc = SubstArgs.arguments()[I].getLocation();
2194
2195 TempArgs[I] = SemaRef.getTrivialTemplateArgumentLoc(
2196 Arg: CTAI.SugaredConverted[I], NTTPType: QualType(), Loc);
2197 }
2198
2199 MutableArrayRef<TemplateArgumentLoc> Mapping(TempArgs,
2200 CTAI.SugaredConverted.size());
2201 N.updateParameterMapping(Indexes: N.mappingOccurenceList(),
2202 IndexesForSubsumption: N.mappingOccurenceListForSubsumption(), Args: Mapping,
2203 ParamList: N.getUsedTemplateParamList());
2204 return false;
2205}
2206
2207bool SubstituteParameterMappings::substitute(ConceptIdConstraint &CC) {
2208 assert(CC.getConstraintDecl() && MLTAL && ArgsAsWritten);
2209
2210 if (substitute(N&: static_cast<NormalizedConstraintWithParamMapping &>(CC)))
2211 return true;
2212
2213 auto *CSE = CC.getConceptSpecializationExpr();
2214 assert(CSE);
2215 assert(!CC.getBeginLoc().isInvalid());
2216
2217 SourceLocation InstLocBegin, InstLocEnd;
2218 if (llvm::ArrayRef Arguments = ArgsAsWritten->arguments();
2219 Arguments.empty()) {
2220 InstLocBegin = ArgsAsWritten->getLAngleLoc();
2221 InstLocEnd = ArgsAsWritten->getRAngleLoc();
2222 } else {
2223 auto SR = Arguments[0].getSourceRange();
2224 InstLocBegin = SR.getBegin();
2225 InstLocEnd = SR.getEnd();
2226 }
2227 Sema::NonSFINAEContext _(SemaRef);
2228 // This is useful for name lookup across modules; see Sema::getLookupModules.
2229 Sema::InstantiatingTemplate Inst(
2230 SemaRef, InstLocBegin,
2231 Sema::InstantiatingTemplate::ParameterMappingSubstitution{},
2232 const_cast<NamedDecl *>(CC.getConstraintDecl()),
2233 {InstLocBegin, InstLocEnd});
2234 if (Inst.isInvalid())
2235 return true;
2236
2237 TemplateArgumentListInfo Out;
2238 // TransformTemplateArguments is unable to preserve the source location of a
2239 // pack. The SourceLocation is necessary for the instantiation location.
2240 // FIXME: The BaseLoc will be used as the location of the pack expansion,
2241 // which is wrong.
2242 const ASTTemplateArgumentListInfo *ArgsAsWritten =
2243 CSE->getTemplateArgsAsWritten();
2244 if (SemaRef.SubstTemplateArgumentsInParameterMapping(
2245 Args: ArgsAsWritten->arguments(), BaseLoc: CC.getBeginLoc(), TemplateArgs: *MLTAL, Out))
2246 return true;
2247 Sema::CheckTemplateArgumentInfo CTAI;
2248 if (SemaRef.CheckTemplateArgumentList(Template: CSE->getNamedConcept(),
2249 TemplateLoc: CSE->getConceptNameInfo().getLoc(), TemplateArgs&: Out,
2250 /*DefaultArgs=*/{},
2251 /*PartialTemplateArgs=*/false, CTAI,
2252 /*UpdateArgsWithConversions=*/false))
2253 return true;
2254 auto TemplateArgs = *MLTAL;
2255 TemplateArgs.replaceOutermostTemplateArguments(AssociatedDecl: CSE->getNamedConcept(),
2256 Args: CTAI.SugaredConverted);
2257 return SubstituteParameterMappings(SemaRef, &TemplateArgs, ArgsAsWritten,
2258 RemovePacksForFoldExpr)
2259 .substitute(N&: CC.getNormalizedConstraint());
2260}
2261
2262bool SubstituteParameterMappings::substitute(NormalizedConstraint &N) {
2263 switch (N.getKind()) {
2264 case NormalizedConstraint::ConstraintKind::Atomic: {
2265 if (!MLTAL) {
2266 assert(!ArgsAsWritten);
2267 return false;
2268 }
2269 return substitute(N&: static_cast<NormalizedConstraintWithParamMapping &>(N));
2270 }
2271 case NormalizedConstraint::ConstraintKind::FoldExpanded: {
2272 auto &FE = static_cast<FoldExpandedConstraint &>(N);
2273 if (!MLTAL) {
2274 llvm::SaveAndRestore _1(RemovePacksForFoldExpr, true);
2275 assert(!ArgsAsWritten);
2276 return substitute(N&: FE.getNormalizedPattern());
2277 }
2278 Sema::ArgPackSubstIndexRAII _(SemaRef, std::nullopt);
2279 substitute(N&: static_cast<NormalizedConstraintWithParamMapping &>(FE));
2280 return SubstituteParameterMappings(SemaRef, /*RemovePacksForFoldExpr=*/true)
2281 .substitute(N&: FE.getNormalizedPattern());
2282 }
2283 case NormalizedConstraint::ConstraintKind::ConceptId: {
2284 auto &CC = static_cast<ConceptIdConstraint &>(N);
2285 if (MLTAL) {
2286 assert(ArgsAsWritten);
2287 return substitute(CC);
2288 }
2289 assert(!ArgsAsWritten);
2290 const ConceptSpecializationExpr *CSE = CC.getConceptSpecializationExpr();
2291 SmallVector<TemplateArgument> InnerArgs(CSE->getTemplateArguments());
2292 ConceptDecl *Concept = CSE->getNamedConcept();
2293 if (RemovePacksForFoldExpr) {
2294 TemplateArgumentListInfo OutArgs;
2295 ArrayRef<TemplateArgumentLoc> InputArgLoc =
2296 CSE->getConceptReference()->getTemplateArgsAsWritten()->arguments();
2297 if (AdjustConstraints(SemaRef, /*TemplateDepth=*/0,
2298 /*RemoveNonPackExpansionPacks=*/true)
2299 .TransformTemplateArguments(First: InputArgLoc.begin(),
2300 Last: InputArgLoc.end(), Outputs&: OutArgs))
2301 return true;
2302 Sema::CheckTemplateArgumentInfo CTAI;
2303 // Repack the packs.
2304 if (SemaRef.CheckTemplateArgumentList(
2305 Template: Concept, Params: Concept->getTemplateParameters(), TemplateLoc: Concept->getBeginLoc(),
2306 TemplateArgs&: OutArgs,
2307 /*DefaultArguments=*/DefaultArgs: {},
2308 /*PartialTemplateArgs=*/false, CTAI))
2309 return true;
2310 InnerArgs = std::move(CTAI.SugaredConverted);
2311 }
2312
2313 MultiLevelTemplateArgumentList MLTAL = SemaRef.getTemplateInstantiationArgs(
2314 D: Concept, DC: Concept->getLexicalDeclContext(),
2315 /*Final=*/true, Innermost: InnerArgs,
2316 /*RelativeToPrimary=*/true,
2317 /*Pattern=*/nullptr,
2318 /*ForConstraintInstantiation=*/true);
2319
2320 return SubstituteParameterMappings(SemaRef, &MLTAL,
2321 CSE->getTemplateArgsAsWritten(),
2322 RemovePacksForFoldExpr)
2323 .substitute(N&: CC.getNormalizedConstraint());
2324 }
2325 case NormalizedConstraint::ConstraintKind::Compound: {
2326 auto &Compound = static_cast<CompoundConstraint &>(N);
2327 if (substitute(N&: Compound.getLHS()))
2328 return true;
2329 return substitute(N&: Compound.getRHS());
2330 }
2331 }
2332 llvm_unreachable("Unknown ConstraintKind enum");
2333}
2334
2335} // namespace
2336
2337NormalizedConstraint *NormalizedConstraint::fromAssociatedConstraints(
2338 Sema &S, const NamedDecl *D, ArrayRef<AssociatedConstraint> ACs) {
2339 assert(ACs.size() != 0);
2340 auto *Conjunction =
2341 fromConstraintExpr(S, D, E: ACs[0].ConstraintExpr, SubstIndex: ACs[0].ArgPackSubstIndex);
2342 if (!Conjunction)
2343 return nullptr;
2344 for (unsigned I = 1; I < ACs.size(); ++I) {
2345 auto *Next = fromConstraintExpr(S, D, E: ACs[I].ConstraintExpr,
2346 SubstIndex: ACs[I].ArgPackSubstIndex);
2347 if (!Next)
2348 return nullptr;
2349 Conjunction = CompoundConstraint::CreateConjunction(Ctx&: S.getASTContext(),
2350 LHS: Conjunction, RHS: Next);
2351 }
2352 return Conjunction;
2353}
2354
2355NormalizedConstraint *NormalizedConstraint::fromConstraintExpr(
2356 Sema &S, const NamedDecl *D, const Expr *E, UnsignedOrNone SubstIndex) {
2357 assert(E != nullptr);
2358
2359 // C++ [temp.constr.normal]p1.1
2360 // [...]
2361 // - The normal form of an expression (E) is the normal form of E.
2362 // [...]
2363 E = E->IgnoreParenImpCasts();
2364
2365 llvm::FoldingSetNodeID ID;
2366 if (D && DiagRecursiveConstraintEval(S, ID, Templ: D, E)) {
2367 return nullptr;
2368 }
2369 SatisfactionStackRAII StackRAII(S, D, ID);
2370
2371 // C++2a [temp.param]p4:
2372 // [...] If T is not a pack, then E is E', otherwise E is (E' && ...).
2373 // Fold expression is considered atomic constraints per current wording.
2374 // See http://cplusplus.github.io/concepts-ts/ts-active.html#28
2375
2376 if (LogicalBinOp BO = E) {
2377 auto *LHS = fromConstraintExpr(S, D, E: BO.getLHS(), SubstIndex);
2378 if (!LHS)
2379 return nullptr;
2380 auto *RHS = fromConstraintExpr(S, D, E: BO.getRHS(), SubstIndex);
2381 if (!RHS)
2382 return nullptr;
2383
2384 return CompoundConstraint::Create(
2385 Ctx&: S.Context, LHS, CCK: BO.isAnd() ? CCK_Conjunction : CCK_Disjunction, RHS);
2386 } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(Val: E)) {
2387 NormalizedConstraint *SubNF;
2388 {
2389 Sema::NonSFINAEContext _(S);
2390 Sema::InstantiatingTemplate Inst(
2391 S, CSE->getExprLoc(),
2392 Sema::InstantiatingTemplate::ConstraintNormalization{},
2393 // FIXME: improve const-correctness of InstantiatingTemplate
2394 const_cast<NamedDecl *>(D), CSE->getSourceRange());
2395 if (Inst.isInvalid())
2396 return nullptr;
2397 // C++ [temp.constr.normal]p1.1
2398 // [...]
2399 // The normal form of an id-expression of the form C<A1, A2, ..., AN>,
2400 // where C names a concept, is the normal form of the
2401 // constraint-expression of C, after substituting A1, A2, ..., AN for C’s
2402 // respective template parameters in the parameter mappings in each atomic
2403 // constraint. If any such substitution results in an invalid type or
2404 // expression, the program is ill-formed; no diagnostic is required.
2405 // [...]
2406
2407 // Use canonical declarations to merge ConceptDecls across
2408 // different modules.
2409 ConceptDecl *CD = CSE->getNamedConcept()->getCanonicalDecl();
2410
2411 ExprResult Res =
2412 SubstituteConceptsInConstraintExpression(S, D, CSE, SubstIndex);
2413 if (!Res.isUsable())
2414 return nullptr;
2415
2416 SubNF = NormalizedConstraint::fromAssociatedConstraints(
2417 S, D: CD, ACs: AssociatedConstraint(Res.get(), SubstIndex));
2418
2419 if (!SubNF)
2420 return nullptr;
2421 }
2422
2423 return ConceptIdConstraint::Create(Ctx&: S.getASTContext(),
2424 ConceptId: CSE->getConceptReference(), SubConstraint: SubNF, ConstraintDecl: D,
2425 CSE, PackIndex: SubstIndex);
2426
2427 } else if (auto *FE = dyn_cast<const CXXFoldExpr>(Val: E);
2428 FE && S.getLangOpts().CPlusPlus26 &&
2429 (FE->getOperator() == BinaryOperatorKind::BO_LAnd ||
2430 FE->getOperator() == BinaryOperatorKind::BO_LOr)) {
2431
2432 // Normalize fold expressions in C++26.
2433
2434 FoldExpandedConstraint::FoldOperatorKind Kind =
2435 FE->getOperator() == BinaryOperatorKind::BO_LAnd
2436 ? FoldExpandedConstraint::FoldOperatorKind::And
2437 : FoldExpandedConstraint::FoldOperatorKind::Or;
2438
2439 if (FE->getInit()) {
2440 auto *LHS = fromConstraintExpr(S, D, E: FE->getLHS(), SubstIndex);
2441 auto *RHS = fromConstraintExpr(S, D, E: FE->getRHS(), SubstIndex);
2442 if (!LHS || !RHS)
2443 return nullptr;
2444
2445 if (FE->isRightFold())
2446 LHS = FoldExpandedConstraint::Create(Ctx&: S.getASTContext(),
2447 Pattern: FE->getPattern(), ConstraintDecl: D, OpKind: Kind, Constraint: LHS);
2448 else
2449 RHS = FoldExpandedConstraint::Create(Ctx&: S.getASTContext(),
2450 Pattern: FE->getPattern(), ConstraintDecl: D, OpKind: Kind, Constraint: RHS);
2451
2452 return CompoundConstraint::Create(
2453 Ctx&: S.getASTContext(), LHS,
2454 CCK: (FE->getOperator() == BinaryOperatorKind::BO_LAnd ? CCK_Conjunction
2455 : CCK_Disjunction),
2456 RHS);
2457 }
2458 auto *Sub = fromConstraintExpr(S, D, E: FE->getPattern(), SubstIndex);
2459 if (!Sub)
2460 return nullptr;
2461 return FoldExpandedConstraint::Create(Ctx&: S.getASTContext(), Pattern: FE->getPattern(),
2462 ConstraintDecl: D, OpKind: Kind, Constraint: Sub);
2463 }
2464 return AtomicConstraint::Create(Ctx&: S.getASTContext(), ConstraintExpr: E, ConstraintDecl: D, PackIndex: SubstIndex);
2465}
2466
2467const NormalizedConstraint *Sema::getNormalizedAssociatedConstraints(
2468 ConstrainedDeclOrNestedRequirement ConstrainedDeclOrNestedReq,
2469 ArrayRef<AssociatedConstraint> AssociatedConstraints) {
2470 if (!ConstrainedDeclOrNestedReq) {
2471 auto *Normalized = NormalizedConstraint::fromAssociatedConstraints(
2472 S&: *this, D: nullptr, ACs: AssociatedConstraints);
2473 if (!Normalized ||
2474 SubstituteParameterMappings(*this).substitute(N&: *Normalized))
2475 return nullptr;
2476
2477 return Normalized;
2478 }
2479
2480 // FIXME: ConstrainedDeclOrNestedReq is never a NestedRequirement!
2481 const NamedDecl *ND =
2482 ConstrainedDeclOrNestedReq.dyn_cast<const NamedDecl *>();
2483 auto CacheEntry = NormalizationCache.find(Val: ConstrainedDeclOrNestedReq);
2484 if (CacheEntry == NormalizationCache.end()) {
2485 auto *Normalized = NormalizedConstraint::fromAssociatedConstraints(
2486 S&: *this, D: ND, ACs: AssociatedConstraints);
2487 if (!Normalized) {
2488 NormalizationCache.try_emplace(Key: ConstrainedDeclOrNestedReq, Args: nullptr);
2489 return nullptr;
2490 }
2491 // substitute() can invalidate iterators of NormalizationCache.
2492 bool Failed = SubstituteParameterMappings(*this).substitute(N&: *Normalized);
2493 CacheEntry =
2494 NormalizationCache.try_emplace(Key: ConstrainedDeclOrNestedReq, Args&: Normalized)
2495 .first;
2496 if (Failed)
2497 return nullptr;
2498 }
2499 return CacheEntry->second;
2500}
2501
2502bool FoldExpandedConstraint::AreCompatibleForSubsumption(
2503 const FoldExpandedConstraint &A, const FoldExpandedConstraint &B) {
2504
2505 // [C++26] [temp.constr.fold]
2506 // Two fold expanded constraints are compatible for subsumption
2507 // if their respective constraints both contain an equivalent unexpanded pack.
2508
2509 llvm::SmallVector<UnexpandedParameterPack> APacks, BPacks;
2510 Sema::collectUnexpandedParameterPacks(E: const_cast<Expr *>(A.getPattern()),
2511 Unexpanded&: APacks);
2512 Sema::collectUnexpandedParameterPacks(E: const_cast<Expr *>(B.getPattern()),
2513 Unexpanded&: BPacks);
2514
2515 for (const UnexpandedParameterPack &APack : APacks) {
2516 auto ADI = getDepthAndIndex(UPP: APack);
2517 if (!ADI)
2518 continue;
2519 auto It = llvm::find_if(Range&: BPacks, P: [&](const UnexpandedParameterPack &BPack) {
2520 return getDepthAndIndex(UPP: BPack) == ADI;
2521 });
2522 if (It != BPacks.end())
2523 return true;
2524 }
2525 return false;
2526}
2527
2528bool Sema::IsAtLeastAsConstrained(const NamedDecl *D1,
2529 MutableArrayRef<AssociatedConstraint> AC1,
2530 const NamedDecl *D2,
2531 MutableArrayRef<AssociatedConstraint> AC2,
2532 bool &Result) {
2533#ifndef NDEBUG
2534 if (const auto *FD1 = dyn_cast<FunctionDecl>(D1)) {
2535 auto IsExpectedEntity = [](const FunctionDecl *FD) {
2536 FunctionDecl::TemplatedKind Kind = FD->getTemplatedKind();
2537 return Kind == FunctionDecl::TK_NonTemplate ||
2538 Kind == FunctionDecl::TK_FunctionTemplate;
2539 };
2540 const auto *FD2 = dyn_cast<FunctionDecl>(D2);
2541 assert(IsExpectedEntity(FD1) && FD2 && IsExpectedEntity(FD2) &&
2542 "use non-instantiated function declaration for constraints partial "
2543 "ordering");
2544 }
2545#endif
2546
2547 if (AC1.empty()) {
2548 Result = AC2.empty();
2549 return false;
2550 }
2551 if (AC2.empty()) {
2552 // TD1 has associated constraints and TD2 does not.
2553 Result = true;
2554 return false;
2555 }
2556
2557 std::pair<const NamedDecl *, const NamedDecl *> Key{D1, D2};
2558 auto CacheEntry = SubsumptionCache.find(Val: Key);
2559 if (CacheEntry != SubsumptionCache.end()) {
2560 Result = CacheEntry->second;
2561 return false;
2562 }
2563
2564 unsigned Depth1 = CalculateTemplateDepthForConstraints(S&: *this, ND: D1, SkipForSpecialization: true);
2565 unsigned Depth2 = CalculateTemplateDepthForConstraints(S&: *this, ND: D2, SkipForSpecialization: true);
2566
2567 for (size_t I = 0; I != AC1.size() && I != AC2.size(); ++I) {
2568 if (Depth2 > Depth1) {
2569 AC1[I].ConstraintExpr =
2570 AdjustConstraints(*this, Depth2 - Depth1)
2571 .TransformExpr(E: const_cast<Expr *>(AC1[I].ConstraintExpr))
2572 .get();
2573 } else if (Depth1 > Depth2) {
2574 AC2[I].ConstraintExpr =
2575 AdjustConstraints(*this, Depth1 - Depth2)
2576 .TransformExpr(E: const_cast<Expr *>(AC2[I].ConstraintExpr))
2577 .get();
2578 }
2579 }
2580
2581 SubsumptionChecker SC(*this);
2582 // Associated declarations are used as a cache key in the event they were
2583 // normalized earlier during concept checking. However we cannot reuse these
2584 // cached results if any of the template depths have been adjusted.
2585 const NamedDecl *DeclAC1 = D1, *DeclAC2 = D2;
2586 if (Depth2 > Depth1)
2587 DeclAC1 = nullptr;
2588 else if (Depth1 > Depth2)
2589 DeclAC2 = nullptr;
2590 std::optional<bool> Subsumes = SC.Subsumes(DP: DeclAC1, P: AC1, DQ: DeclAC2, Q: AC2);
2591 if (!Subsumes) {
2592 // Normalization failed
2593 return true;
2594 }
2595 Result = *Subsumes;
2596 SubsumptionCache.try_emplace(Key, Args&: *Subsumes);
2597 return false;
2598}
2599
2600bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(
2601 const NamedDecl *D1, ArrayRef<AssociatedConstraint> AC1,
2602 const NamedDecl *D2, ArrayRef<AssociatedConstraint> AC2) {
2603 if (isSFINAEContext())
2604 // No need to work here because our notes would be discarded.
2605 return false;
2606
2607 if (AC1.empty() || AC2.empty())
2608 return false;
2609
2610 const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
2611 auto IdenticalExprEvaluator = [&](const AtomicConstraint &A,
2612 const AtomicConstraint &B) {
2613 if (!A.hasMatchingParameterMapping(C&: Context, Other: B))
2614 return false;
2615 const Expr *EA = A.getConstraintExpr(), *EB = B.getConstraintExpr();
2616 if (EA == EB)
2617 return true;
2618
2619 // Not the same source level expression - are the expressions
2620 // identical?
2621 llvm::FoldingSetNodeID IDA, IDB;
2622 EA->Profile(ID&: IDA, Context, /*Canonical=*/true);
2623 EB->Profile(ID&: IDB, Context, /*Canonical=*/true);
2624 if (IDA != IDB)
2625 return false;
2626
2627 AmbiguousAtomic1 = EA;
2628 AmbiguousAtomic2 = EB;
2629 return true;
2630 };
2631
2632 {
2633 auto *Normalized1 = getNormalizedAssociatedConstraints(ConstrainedDeclOrNestedReq: D1, AssociatedConstraints: AC1);
2634 if (!Normalized1)
2635 return false;
2636
2637 auto *Normalized2 = getNormalizedAssociatedConstraints(ConstrainedDeclOrNestedReq: D2, AssociatedConstraints: AC2);
2638 if (!Normalized2)
2639 return false;
2640
2641 SubsumptionChecker SC(*this);
2642
2643 bool Is1AtLeastAs2Normally = SC.Subsumes(P: Normalized1, Q: Normalized2);
2644 bool Is2AtLeastAs1Normally = SC.Subsumes(P: Normalized2, Q: Normalized1);
2645
2646 SubsumptionChecker SC2(*this, IdenticalExprEvaluator);
2647 bool Is1AtLeastAs2 = SC2.Subsumes(P: Normalized1, Q: Normalized2);
2648 bool Is2AtLeastAs1 = SC2.Subsumes(P: Normalized2, Q: Normalized1);
2649
2650 if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
2651 Is2AtLeastAs1 == Is2AtLeastAs1Normally)
2652 // Same result - no ambiguity was caused by identical atomic expressions.
2653 return false;
2654 }
2655 // A different result! Some ambiguous atomic constraint(s) caused a difference
2656 assert(AmbiguousAtomic1 && AmbiguousAtomic2);
2657
2658 Diag(Loc: AmbiguousAtomic1->getBeginLoc(), DiagID: diag::note_ambiguous_atomic_constraints)
2659 << AmbiguousAtomic1->getSourceRange();
2660 Diag(Loc: AmbiguousAtomic2->getBeginLoc(),
2661 DiagID: diag::note_ambiguous_atomic_constraints_similar_expression)
2662 << AmbiguousAtomic2->getSourceRange();
2663 return true;
2664}
2665
2666//
2667//
2668// ------------------------ Subsumption -----------------------------------
2669//
2670//
2671SubsumptionChecker::SubsumptionChecker(Sema &SemaRef,
2672 SubsumptionCallable Callable)
2673 : SemaRef(SemaRef), Callable(Callable), NextID(1) {}
2674
2675uint16_t SubsumptionChecker::getNewLiteralId() {
2676 assert((unsigned(NextID) + 1 < std::numeric_limits<uint16_t>::max()) &&
2677 "too many constraints!");
2678 return NextID++;
2679}
2680
2681auto SubsumptionChecker::find(const AtomicConstraint *Ori) -> Literal {
2682 auto &Elems = AtomicMap[Ori->getConstraintExpr()];
2683 // C++ [temp.constr.order] p2
2684 // - an atomic constraint A subsumes another atomic constraint B
2685 // if and only if the A and B are identical [...]
2686 //
2687 // C++ [temp.constr.atomic] p2
2688 // Two atomic constraints are identical if they are formed from the
2689 // same expression and the targets of the parameter mappings are
2690 // equivalent according to the rules for expressions [...]
2691
2692 // Because subsumption of atomic constraints is an identity
2693 // relationship that does not require further analysis
2694 // We cache the results such that if an atomic constraint literal
2695 // subsumes another, their literal will be the same
2696
2697 llvm::FoldingSetNodeID ID;
2698 ID.AddBoolean(B: Ori->hasParameterMapping());
2699 if (Ori->hasParameterMapping()) {
2700 const auto &Mapping = Ori->getParameterMapping();
2701 const NormalizedConstraint::OccurenceList &Indexes =
2702 Ori->mappingOccurenceListForSubsumption();
2703 for (auto [Idx, TAL] : llvm::enumerate(First: Mapping)) {
2704 if (Indexes[Idx])
2705 SemaRef.getASTContext()
2706 .getCanonicalTemplateArgument(Arg: TAL.getArgument())
2707 .Profile(ID, Context: SemaRef.getASTContext());
2708 }
2709 }
2710 auto It = Elems.find(Val: ID);
2711 if (It == Elems.end()) {
2712 It = Elems
2713 .insert(KV: {ID,
2714 MappedAtomicConstraint{
2715 .Constraint: Ori, .ID: {.Value: getNewLiteralId(), .Kind: Literal::Atomic}}})
2716 .first;
2717 ReverseMap[It->second.ID.Value] = Ori;
2718 }
2719 return It->getSecond().ID;
2720}
2721
2722auto SubsumptionChecker::find(const FoldExpandedConstraint *Ori) -> Literal {
2723 auto &Elems = FoldMap[Ori->getPattern()];
2724
2725 FoldExpendedConstraintKey K;
2726 K.Kind = Ori->getFoldOperator();
2727
2728 auto It = llvm::find_if(Range&: Elems, P: [&K](const FoldExpendedConstraintKey &Other) {
2729 return K.Kind == Other.Kind;
2730 });
2731 if (It == Elems.end()) {
2732 K.ID = {.Value: getNewLiteralId(), .Kind: Literal::FoldExpanded};
2733 It = Elems.insert(position: Elems.end(), x: std::move(K));
2734 ReverseMap[It->ID.Value] = Ori;
2735 }
2736 return It->ID;
2737}
2738
2739auto SubsumptionChecker::CNF(const NormalizedConstraint &C) -> CNFFormula {
2740 return SubsumptionChecker::Normalize<CNFFormula>(NC: C);
2741}
2742auto SubsumptionChecker::DNF(const NormalizedConstraint &C) -> DNFFormula {
2743 return SubsumptionChecker::Normalize<DNFFormula>(NC: C);
2744}
2745
2746///
2747/// \brief SubsumptionChecker::Normalize
2748///
2749/// Normalize a formula to Conjunctive Normal Form or
2750/// Disjunctive normal form.
2751///
2752/// Each Atomic (and Fold Expanded) constraint gets represented by
2753/// a single id to reduce space.
2754///
2755/// To minimize risks of exponential blow up, if two atomic
2756/// constraints subsumes each other (same constraint and mapping),
2757/// they are represented by the same literal.
2758///
2759template <typename FormulaType>
2760FormulaType SubsumptionChecker::Normalize(const NormalizedConstraint &NC) {
2761 FormulaType Res;
2762
2763 auto Add = [&, this](Clause C) {
2764 // Sort each clause and remove duplicates for faster comparisons.
2765 llvm::sort(C);
2766 C.erase(CS: llvm::unique(R&: C), CE: C.end());
2767 AddUniqueClauseToFormula(F&: Res, C: std::move(C));
2768 };
2769
2770 switch (NC.getKind()) {
2771 case NormalizedConstraint::ConstraintKind::Atomic:
2772 return {{find(Ori: &static_cast<const AtomicConstraint &>(NC))}};
2773
2774 case NormalizedConstraint::ConstraintKind::FoldExpanded:
2775 return {{find(Ori: &static_cast<const FoldExpandedConstraint &>(NC))}};
2776
2777 case NormalizedConstraint::ConstraintKind::ConceptId:
2778 return Normalize<FormulaType>(
2779 static_cast<const ConceptIdConstraint &>(NC).getNormalizedConstraint());
2780
2781 case NormalizedConstraint::ConstraintKind::Compound: {
2782 const auto &Compound = static_cast<const CompoundConstraint &>(NC);
2783 FormulaType Left, Right;
2784 SemaRef.runWithSufficientStackSpace(Loc: SourceLocation(), Fn: [&] {
2785 Left = Normalize<FormulaType>(Compound.getLHS());
2786 Right = Normalize<FormulaType>(Compound.getRHS());
2787 });
2788
2789 if (Compound.getCompoundKind() == FormulaType::Kind) {
2790 unsigned SizeLeft = Left.size();
2791 Res = std::move(Left);
2792 Res.reserve(SizeLeft + Right.size());
2793 std::for_each(std::make_move_iterator(Right.begin()),
2794 std::make_move_iterator(Right.end()), Add);
2795 return Res;
2796 }
2797
2798 Res.reserve(Left.size() * Right.size());
2799 for (const auto &LTransform : Left) {
2800 for (const auto &RTransform : Right) {
2801 Clause Combined;
2802 Combined.reserve(N: LTransform.size() + RTransform.size());
2803 llvm::copy(LTransform, std::back_inserter(x&: Combined));
2804 llvm::copy(RTransform, std::back_inserter(x&: Combined));
2805 Add(std::move(Combined));
2806 }
2807 }
2808 return Res;
2809 }
2810 }
2811 llvm_unreachable("Unknown ConstraintKind enum");
2812}
2813
2814void SubsumptionChecker::AddUniqueClauseToFormula(Formula &F, Clause C) {
2815 for (auto &Other : F) {
2816 if (llvm::equal(LRange&: C, RRange&: Other))
2817 return;
2818 }
2819 F.push_back(Elt: C);
2820}
2821
2822std::optional<bool> SubsumptionChecker::Subsumes(
2823 const NamedDecl *DP, ArrayRef<AssociatedConstraint> P, const NamedDecl *DQ,
2824 ArrayRef<AssociatedConstraint> Q) {
2825 const NormalizedConstraint *PNormalized =
2826 SemaRef.getNormalizedAssociatedConstraints(ConstrainedDeclOrNestedReq: DP, AssociatedConstraints: P);
2827 if (!PNormalized)
2828 return std::nullopt;
2829
2830 const NormalizedConstraint *QNormalized =
2831 SemaRef.getNormalizedAssociatedConstraints(ConstrainedDeclOrNestedReq: DQ, AssociatedConstraints: Q);
2832 if (!QNormalized)
2833 return std::nullopt;
2834
2835 return Subsumes(P: PNormalized, Q: QNormalized);
2836}
2837
2838bool SubsumptionChecker::Subsumes(const NormalizedConstraint *P,
2839 const NormalizedConstraint *Q) {
2840
2841 DNFFormula DNFP = DNF(C: *P);
2842 CNFFormula CNFQ = CNF(C: *Q);
2843 return Subsumes(P: DNFP, Q: CNFQ);
2844}
2845
2846bool SubsumptionChecker::Subsumes(const DNFFormula &PDNF,
2847 const CNFFormula &QCNF) {
2848 for (const auto &Pi : PDNF) {
2849 for (const auto &Qj : QCNF) {
2850 // C++ [temp.constr.order] p2
2851 // - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
2852 // and only if there exists an atomic constraint Pia in Pi for which
2853 // there exists an atomic constraint, Qjb, in Qj such that Pia
2854 // subsumes Qjb.
2855 if (!DNFSubsumes(P: Pi, Q: Qj))
2856 return false;
2857 }
2858 }
2859 return true;
2860}
2861
2862bool SubsumptionChecker::DNFSubsumes(const Clause &P, const Clause &Q) {
2863
2864 return llvm::any_of(Range: P, P: [&](Literal LP) {
2865 return llvm::any_of(Range: Q, P: [this, LP](Literal LQ) { return Subsumes(A: LP, B: LQ); });
2866 });
2867}
2868
2869bool SubsumptionChecker::Subsumes(const FoldExpandedConstraint *A,
2870 const FoldExpandedConstraint *B) {
2871 std::pair<const FoldExpandedConstraint *, const FoldExpandedConstraint *> Key{
2872 A, B};
2873
2874 auto It = FoldSubsumptionCache.find(Val: Key);
2875 if (It == FoldSubsumptionCache.end()) {
2876 // C++ [temp.constr.order]
2877 // a fold expanded constraint A subsumes another fold expanded
2878 // constraint B if they are compatible for subsumption, have the same
2879 // fold-operator, and the constraint of A subsumes that of B.
2880 bool DoesSubsume =
2881 A->getFoldOperator() == B->getFoldOperator() &&
2882 FoldExpandedConstraint::AreCompatibleForSubsumption(A: *A, B: *B) &&
2883 Subsumes(P: &A->getNormalizedPattern(), Q: &B->getNormalizedPattern());
2884 It = FoldSubsumptionCache.try_emplace(Key: std::move(Key), Args&: DoesSubsume).first;
2885 }
2886 return It->second;
2887}
2888
2889bool SubsumptionChecker::Subsumes(Literal A, Literal B) {
2890 if (A.Kind != B.Kind)
2891 return false;
2892 switch (A.Kind) {
2893 case Literal::Atomic:
2894 if (!Callable)
2895 return A.Value == B.Value;
2896 return Callable(
2897 *static_cast<const AtomicConstraint *>(ReverseMap[A.Value]),
2898 *static_cast<const AtomicConstraint *>(ReverseMap[B.Value]));
2899 case Literal::FoldExpanded:
2900 return Subsumes(
2901 A: static_cast<const FoldExpandedConstraint *>(ReverseMap[A.Value]),
2902 B: static_cast<const FoldExpandedConstraint *>(ReverseMap[B.Value]));
2903 }
2904 llvm_unreachable("unknown literal kind");
2905}
2906