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