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