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