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