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