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