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