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/ASTLambda.h"
16#include "clang/AST/DeclCXX.h"
17#include "clang/AST/ExprConcepts.h"
18#include "clang/Basic/OperatorPrecedence.h"
19#include "clang/Sema/EnterExpressionEvaluationContext.h"
20#include "clang/Sema/Initialization.h"
21#include "clang/Sema/Overload.h"
22#include "clang/Sema/ScopeInfo.h"
23#include "clang/Sema/Sema.h"
24#include "clang/Sema/SemaInternal.h"
25#include "clang/Sema/Template.h"
26#include "clang/Sema/TemplateDeduction.h"
27#include "llvm/ADT/DenseMap.h"
28#include "llvm/ADT/PointerUnion.h"
29#include "llvm/ADT/StringExtras.h"
30#include <optional>
31
32using namespace clang;
33using namespace sema;
34
35namespace {
36class LogicalBinOp {
37 SourceLocation Loc;
38 OverloadedOperatorKind Op = OO_None;
39 const Expr *LHS = nullptr;
40 const Expr *RHS = nullptr;
41
42public:
43 LogicalBinOp(const Expr *E) {
44 if (auto *BO = dyn_cast<BinaryOperator>(Val: E)) {
45 Op = BinaryOperator::getOverloadedOperator(Opc: BO->getOpcode());
46 LHS = BO->getLHS();
47 RHS = BO->getRHS();
48 Loc = BO->getExprLoc();
49 } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(Val: E)) {
50 // If OO is not || or && it might not have exactly 2 arguments.
51 if (OO->getNumArgs() == 2) {
52 Op = OO->getOperator();
53 LHS = OO->getArg(Arg: 0);
54 RHS = OO->getArg(Arg: 1);
55 Loc = OO->getOperatorLoc();
56 }
57 }
58 }
59
60 bool isAnd() const { return Op == OO_AmpAmp; }
61 bool isOr() const { return Op == OO_PipePipe; }
62 explicit operator bool() const { return isAnd() || isOr(); }
63
64 const Expr *getLHS() const { return LHS; }
65 const Expr *getRHS() const { return RHS; }
66 OverloadedOperatorKind getOp() const { return Op; }
67
68 ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS) const {
69 return recreateBinOp(SemaRef, LHS, RHS: const_cast<Expr *>(getRHS()));
70 }
71
72 ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS,
73 ExprResult RHS) const {
74 assert((isAnd() || isOr()) && "Not the right kind of op?");
75 assert((!LHS.isInvalid() && !RHS.isInvalid()) && "not good expressions?");
76
77 if (!LHS.isUsable() || !RHS.isUsable())
78 return ExprEmpty();
79
80 // We should just be able to 'normalize' these to the builtin Binary
81 // Operator, since that is how they are evaluated in constriant checks.
82 return BinaryOperator::Create(C: SemaRef.Context, lhs: LHS.get(), rhs: RHS.get(),
83 opc: BinaryOperator::getOverloadedOpcode(OO: Op),
84 ResTy: SemaRef.Context.BoolTy, VK: VK_PRValue,
85 OK: OK_Ordinary, opLoc: Loc, FPFeatures: FPOptionsOverride{});
86 }
87};
88}
89
90bool Sema::CheckConstraintExpression(const Expr *ConstraintExpression,
91 Token NextToken, bool *PossibleNonPrimary,
92 bool IsTrailingRequiresClause) {
93 // C++2a [temp.constr.atomic]p1
94 // ..E shall be a constant expression of type bool.
95
96 ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts();
97
98 if (LogicalBinOp BO = ConstraintExpression) {
99 return CheckConstraintExpression(ConstraintExpression: BO.getLHS(), NextToken,
100 PossibleNonPrimary) &&
101 CheckConstraintExpression(ConstraintExpression: BO.getRHS(), NextToken,
102 PossibleNonPrimary);
103 } else if (auto *C = dyn_cast<ExprWithCleanups>(Val: ConstraintExpression))
104 return CheckConstraintExpression(ConstraintExpression: C->getSubExpr(), NextToken,
105 PossibleNonPrimary);
106
107 QualType Type = ConstraintExpression->getType();
108
109 auto CheckForNonPrimary = [&] {
110 if (!PossibleNonPrimary)
111 return;
112
113 *PossibleNonPrimary =
114 // We have the following case:
115 // template<typename> requires func(0) struct S { };
116 // The user probably isn't aware of the parentheses required around
117 // the function call, and we're only going to parse 'func' as the
118 // primary-expression, and complain that it is of non-bool type.
119 //
120 // However, if we're in a lambda, this might also be:
121 // []<typename> requires var () {};
122 // Which also looks like a function call due to the lambda parentheses,
123 // but unlike the first case, isn't an error, so this check is skipped.
124 (NextToken.is(K: tok::l_paren) &&
125 (IsTrailingRequiresClause ||
126 (Type->isDependentType() &&
127 isa<UnresolvedLookupExpr>(Val: ConstraintExpression) &&
128 !dyn_cast_if_present<LambdaScopeInfo>(Val: getCurFunction())) ||
129 Type->isFunctionType() ||
130 Type->isSpecificBuiltinType(K: BuiltinType::Overload))) ||
131 // We have the following case:
132 // template<typename T> requires size_<T> == 0 struct S { };
133 // The user probably isn't aware of the parentheses required around
134 // the binary operator, and we're only going to parse 'func' as the
135 // first operand, and complain that it is of non-bool type.
136 getBinOpPrecedence(Kind: NextToken.getKind(),
137 /*GreaterThanIsOperator=*/true,
138 CPlusPlus11: getLangOpts().CPlusPlus11) > prec::LogicalAnd;
139 };
140
141 // An atomic constraint!
142 if (ConstraintExpression->isTypeDependent()) {
143 CheckForNonPrimary();
144 return true;
145 }
146
147 if (!Context.hasSameUnqualifiedType(T1: Type, T2: Context.BoolTy)) {
148 Diag(Loc: ConstraintExpression->getExprLoc(),
149 DiagID: diag::err_non_bool_atomic_constraint) << Type
150 << ConstraintExpression->getSourceRange();
151 CheckForNonPrimary();
152 return false;
153 }
154
155 if (PossibleNonPrimary)
156 *PossibleNonPrimary = false;
157 return true;
158}
159
160namespace {
161struct SatisfactionStackRAII {
162 Sema &SemaRef;
163 bool Inserted = false;
164 SatisfactionStackRAII(Sema &SemaRef, const NamedDecl *ND,
165 const llvm::FoldingSetNodeID &FSNID)
166 : SemaRef(SemaRef) {
167 if (ND) {
168 SemaRef.PushSatisfactionStackEntry(D: ND, ID: FSNID);
169 Inserted = true;
170 }
171 }
172 ~SatisfactionStackRAII() {
173 if (Inserted)
174 SemaRef.PopSatisfactionStackEntry();
175 }
176};
177} // namespace
178
179static bool
180DiagRecursiveConstraintEval(Sema &S, llvm::FoldingSetNodeID &ID,
181 const NamedDecl *Templ, const Expr *E,
182 const MultiLevelTemplateArgumentList &MLTAL) {
183 E->Profile(ID, Context: S.Context, /*Canonical=*/true);
184 for (const auto &List : MLTAL)
185 for (const auto &TemplateArg : List.Args)
186 TemplateArg.Profile(ID, Context: S.Context);
187
188 // Note that we have to do this with our own collection, because there are
189 // times where a constraint-expression check can cause us to need to evaluate
190 // other constriants that are unrelated, such as when evaluating a recovery
191 // expression, or when trying to determine the constexpr-ness of special
192 // members. Otherwise we could just use the
193 // Sema::InstantiatingTemplate::isAlreadyBeingInstantiated function.
194 if (S.SatisfactionStackContains(D: Templ, ID)) {
195 S.Diag(Loc: E->getExprLoc(), DiagID: diag::err_constraint_depends_on_self)
196 << const_cast<Expr *>(E) << E->getSourceRange();
197 return true;
198 }
199
200 return false;
201}
202
203static ExprResult EvaluateAtomicConstraint(
204 Sema &S, const Expr *AtomicExpr, const NamedDecl *Template,
205 SourceLocation TemplateNameLoc, const MultiLevelTemplateArgumentList &MLTAL,
206 ConstraintSatisfaction &Satisfaction) {
207 EnterExpressionEvaluationContext ConstantEvaluated(
208 S, Sema::ExpressionEvaluationContext::ConstantEvaluated,
209 Sema::ReuseLambdaContextDecl);
210
211 // Atomic constraint - substitute arguments and check satisfaction.
212 ExprResult SubstitutedExpression;
213 {
214 TemplateDeductionInfo Info(TemplateNameLoc);
215 Sema::InstantiatingTemplate Inst(
216 S, AtomicExpr->getBeginLoc(),
217 Sema::InstantiatingTemplate::ConstraintSubstitution{},
218 // FIXME: improve const-correctness of InstantiatingTemplate
219 const_cast<NamedDecl *>(Template), Info, AtomicExpr->getSourceRange());
220 if (Inst.isInvalid())
221 return ExprError();
222
223 llvm::FoldingSetNodeID ID;
224 if (Template &&
225 DiagRecursiveConstraintEval(S, ID, Templ: Template, E: AtomicExpr, MLTAL)) {
226 Satisfaction.IsSatisfied = false;
227 Satisfaction.ContainsErrors = true;
228 return ExprEmpty();
229 }
230
231 SatisfactionStackRAII StackRAII(S, Template, ID);
232
233 // We do not want error diagnostics escaping here.
234 Sema::SFINAETrap Trap(S);
235 SubstitutedExpression =
236 S.SubstConstraintExpr(E: const_cast<Expr *>(AtomicExpr), TemplateArgs: MLTAL);
237
238 if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
239 // C++2a [temp.constr.atomic]p1
240 // ...If substitution results in an invalid type or expression, the
241 // constraint is not satisfied.
242 if (!Trap.hasErrorOccurred())
243 // A non-SFINAE error has occurred as a result of this
244 // substitution.
245 return ExprError();
246
247 PartialDiagnosticAt SubstDiag{SourceLocation(),
248 PartialDiagnostic::NullDiagnostic()};
249 Info.takeSFINAEDiagnostic(PD&: SubstDiag);
250 // FIXME: Concepts: This is an unfortunate consequence of there
251 // being no serialization code for PartialDiagnostics and the fact
252 // that serializing them would likely take a lot more storage than
253 // just storing them as strings. We would still like, in the
254 // future, to serialize the proper PartialDiagnostic as serializing
255 // it as a string defeats the purpose of the diagnostic mechanism.
256 SmallString<128> DiagString;
257 DiagString = ": ";
258 SubstDiag.second.EmitToString(Diags&: S.getDiagnostics(), Buf&: DiagString);
259 unsigned MessageSize = DiagString.size();
260 char *Mem = new (S.Context) char[MessageSize];
261 memcpy(dest: Mem, src: DiagString.c_str(), n: MessageSize);
262 Satisfaction.Details.emplace_back(
263 Args: new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
264 SubstDiag.first, StringRef(Mem, MessageSize)});
265 Satisfaction.IsSatisfied = false;
266 return ExprEmpty();
267 }
268 }
269
270 if (!S.CheckConstraintExpression(ConstraintExpression: SubstitutedExpression.get()))
271 return ExprError();
272
273 // [temp.constr.atomic]p3: To determine if an atomic constraint is
274 // satisfied, the parameter mapping and template arguments are first
275 // substituted into its expression. If substitution results in an
276 // invalid type or expression, the constraint is not satisfied.
277 // Otherwise, the lvalue-to-rvalue conversion is performed if necessary,
278 // and E shall be a constant expression of type bool.
279 //
280 // Perform the L to R Value conversion if necessary. We do so for all
281 // non-PRValue categories, else we fail to extend the lifetime of
282 // temporaries, and that fails the constant expression check.
283 if (!SubstitutedExpression.get()->isPRValue())
284 SubstitutedExpression = ImplicitCastExpr::Create(
285 Context: S.Context, T: SubstitutedExpression.get()->getType(), Kind: CK_LValueToRValue,
286 Operand: SubstitutedExpression.get(),
287 /*BasePath=*/nullptr, Cat: VK_PRValue, FPO: FPOptionsOverride());
288
289 return SubstitutedExpression;
290}
291
292static UnsignedOrNone EvaluateFoldExpandedConstraintSize(
293 Sema &S, const CXXFoldExpr *FE, const NamedDecl *Template,
294 SourceLocation TemplateNameLoc, const MultiLevelTemplateArgumentList &MLTAL,
295 ConstraintSatisfaction &Satisfaction) {
296
297 // We should ignore errors in the presence of packs of different size.
298 Sema::SFINAETrap Trap(S);
299
300 Expr *Pattern = FE->getPattern();
301
302 SmallVector<UnexpandedParameterPack, 2> Unexpanded;
303 S.collectUnexpandedParameterPacks(E: Pattern, Unexpanded);
304 assert(!Unexpanded.empty() && "Pack expansion without parameter packs?");
305 bool Expand = true;
306 bool RetainExpansion = false;
307 UnsignedOrNone NumExpansions = FE->getNumExpansions();
308 if (S.CheckParameterPacksForExpansion(
309 EllipsisLoc: FE->getEllipsisLoc(), PatternRange: Pattern->getSourceRange(), Unexpanded, TemplateArgs: MLTAL,
310 ShouldExpand&: Expand, RetainExpansion, NumExpansions) ||
311 !Expand || RetainExpansion)
312 return std::nullopt;
313
314 if (NumExpansions && S.getLangOpts().BracketDepth < *NumExpansions) {
315 S.Diag(Loc: FE->getEllipsisLoc(),
316 DiagID: clang::diag::err_fold_expression_limit_exceeded)
317 << *NumExpansions << S.getLangOpts().BracketDepth
318 << FE->getSourceRange();
319 S.Diag(Loc: FE->getEllipsisLoc(), DiagID: diag::note_bracket_depth);
320 return std::nullopt;
321 }
322 return NumExpansions;
323}
324
325static ExprResult calculateConstraintSatisfaction(
326 Sema &S, const Expr *ConstraintExpr, const NamedDecl *Template,
327 SourceLocation TemplateNameLoc, const MultiLevelTemplateArgumentList &MLTAL,
328 ConstraintSatisfaction &Satisfaction);
329
330static ExprResult calculateConstraintSatisfaction(
331 Sema &S, const Expr *LHS, OverloadedOperatorKind Op, const Expr *RHS,
332 const NamedDecl *Template, SourceLocation TemplateNameLoc,
333 const MultiLevelTemplateArgumentList &MLTAL,
334 ConstraintSatisfaction &Satisfaction) {
335 size_t EffectiveDetailEndIndex = Satisfaction.Details.size();
336
337 ExprResult LHSRes = calculateConstraintSatisfaction(
338 S, ConstraintExpr: LHS, Template, TemplateNameLoc, MLTAL, Satisfaction);
339
340 if (LHSRes.isInvalid())
341 return ExprError();
342
343 bool IsLHSSatisfied = Satisfaction.IsSatisfied;
344
345 if (Op == clang::OO_PipePipe && IsLHSSatisfied)
346 // [temp.constr.op] p3
347 // A disjunction is a constraint taking two operands. To determine if
348 // a disjunction is satisfied, the satisfaction of the first operand
349 // is checked. If that is satisfied, the disjunction is satisfied.
350 // Otherwise, the disjunction is satisfied if and only if the second
351 // operand is satisfied.
352 // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
353 return LHSRes;
354
355 if (Op == clang::OO_AmpAmp && !IsLHSSatisfied)
356 // [temp.constr.op] p2
357 // A conjunction is a constraint taking two operands. To determine if
358 // a conjunction is satisfied, the satisfaction of the first operand
359 // is checked. If that is not satisfied, the conjunction is not
360 // satisfied. Otherwise, the conjunction is satisfied if and only if
361 // the second operand is satisfied.
362 // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp.
363 return LHSRes;
364
365 ExprResult RHSRes = calculateConstraintSatisfaction(
366 S, ConstraintExpr: RHS, Template, TemplateNameLoc, MLTAL, Satisfaction);
367 if (RHSRes.isInvalid())
368 return ExprError();
369
370 bool IsRHSSatisfied = Satisfaction.IsSatisfied;
371 // Current implementation adds diagnostic information about the falsity
372 // of each false atomic constraint expression when it evaluates them.
373 // When the evaluation results to `false || true`, the information
374 // generated during the evaluation of left-hand side is meaningless
375 // because the whole expression evaluates to true.
376 // The following code removes the irrelevant diagnostic information.
377 // FIXME: We should probably delay the addition of diagnostic information
378 // until we know the entire expression is false.
379 if (Op == clang::OO_PipePipe && IsRHSSatisfied) {
380 auto EffectiveDetailEnd = Satisfaction.Details.begin();
381 std::advance(i&: EffectiveDetailEnd, n: EffectiveDetailEndIndex);
382 Satisfaction.Details.erase(CS: EffectiveDetailEnd, CE: Satisfaction.Details.end());
383 }
384
385 if (!LHSRes.isUsable() || !RHSRes.isUsable())
386 return ExprEmpty();
387
388 return BinaryOperator::Create(C: S.Context, lhs: LHSRes.get(), rhs: RHSRes.get(),
389 opc: BinaryOperator::getOverloadedOpcode(OO: Op),
390 ResTy: S.Context.BoolTy, VK: VK_PRValue, OK: OK_Ordinary,
391 opLoc: LHS->getBeginLoc(), FPFeatures: FPOptionsOverride{});
392}
393
394static ExprResult calculateConstraintSatisfaction(
395 Sema &S, const CXXFoldExpr *FE, const NamedDecl *Template,
396 SourceLocation TemplateNameLoc, const MultiLevelTemplateArgumentList &MLTAL,
397 ConstraintSatisfaction &Satisfaction) {
398 bool Conjunction = FE->getOperator() == BinaryOperatorKind::BO_LAnd;
399 size_t EffectiveDetailEndIndex = Satisfaction.Details.size();
400
401 ExprResult Out;
402 if (FE->isLeftFold() && FE->getInit()) {
403 Out = calculateConstraintSatisfaction(S, ConstraintExpr: FE->getInit(), Template,
404 TemplateNameLoc, MLTAL, Satisfaction);
405 if (Out.isInvalid())
406 return ExprError();
407
408 // If the first clause of a conjunction is not satisfied,
409 // or if the first clause of a disjection is satisfied,
410 // we have established satisfaction of the whole constraint
411 // and we should not continue further.
412 if (Conjunction != Satisfaction.IsSatisfied)
413 return Out;
414 }
415 UnsignedOrNone NumExpansions = EvaluateFoldExpandedConstraintSize(
416 S, FE, Template, TemplateNameLoc, MLTAL, Satisfaction);
417 if (!NumExpansions)
418 return ExprError();
419 for (unsigned I = 0; I < *NumExpansions; I++) {
420 Sema::ArgPackSubstIndexRAII SubstIndex(S, I);
421 ExprResult Res = calculateConstraintSatisfaction(
422 S, ConstraintExpr: FE->getPattern(), Template, TemplateNameLoc, MLTAL, Satisfaction);
423 if (Res.isInvalid())
424 return ExprError();
425 bool IsRHSSatisfied = Satisfaction.IsSatisfied;
426 if (!Conjunction && IsRHSSatisfied) {
427 auto EffectiveDetailEnd = Satisfaction.Details.begin();
428 std::advance(i&: EffectiveDetailEnd, n: EffectiveDetailEndIndex);
429 Satisfaction.Details.erase(CS: EffectiveDetailEnd,
430 CE: Satisfaction.Details.end());
431 }
432 if (Out.isUnset())
433 Out = Res;
434 else if (!Res.isUnset()) {
435 Out = BinaryOperator::Create(
436 C: S.Context, lhs: Out.get(), rhs: Res.get(), opc: FE->getOperator(), ResTy: S.Context.BoolTy,
437 VK: VK_PRValue, OK: OK_Ordinary, opLoc: FE->getBeginLoc(), FPFeatures: FPOptionsOverride{});
438 }
439 if (Conjunction != IsRHSSatisfied)
440 return Out;
441 }
442
443 if (FE->isRightFold() && FE->getInit()) {
444 ExprResult Res = calculateConstraintSatisfaction(
445 S, ConstraintExpr: FE->getInit(), Template, TemplateNameLoc, MLTAL, Satisfaction);
446 if (Out.isInvalid())
447 return ExprError();
448
449 if (Out.isUnset())
450 Out = Res;
451 else if (!Res.isUnset()) {
452 Out = BinaryOperator::Create(
453 C: S.Context, lhs: Out.get(), rhs: Res.get(), opc: FE->getOperator(), ResTy: S.Context.BoolTy,
454 VK: VK_PRValue, OK: OK_Ordinary, opLoc: FE->getBeginLoc(), FPFeatures: FPOptionsOverride{});
455 }
456 }
457
458 if (Out.isUnset()) {
459 Satisfaction.IsSatisfied = Conjunction;
460 Out = S.BuildEmptyCXXFoldExpr(EllipsisLoc: FE->getBeginLoc(), Operator: FE->getOperator());
461 }
462 return Out;
463}
464
465static ExprResult calculateConstraintSatisfaction(
466 Sema &S, const Expr *ConstraintExpr, const NamedDecl *Template,
467 SourceLocation TemplateNameLoc, const MultiLevelTemplateArgumentList &MLTAL,
468 ConstraintSatisfaction &Satisfaction) {
469 ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
470
471 if (LogicalBinOp BO = ConstraintExpr)
472 return calculateConstraintSatisfaction(
473 S, LHS: BO.getLHS(), Op: BO.getOp(), RHS: BO.getRHS(), Template, TemplateNameLoc,
474 MLTAL, Satisfaction);
475
476 if (auto *C = dyn_cast<ExprWithCleanups>(Val: ConstraintExpr)) {
477 // These aren't evaluated, so we don't care about cleanups, so we can just
478 // evaluate these as if the cleanups didn't exist.
479 return calculateConstraintSatisfaction(
480 S, ConstraintExpr: C->getSubExpr(), Template, TemplateNameLoc, MLTAL, Satisfaction);
481 }
482
483 if (auto *FE = dyn_cast<CXXFoldExpr>(Val: ConstraintExpr);
484 FE && S.getLangOpts().CPlusPlus26 &&
485 (FE->getOperator() == BinaryOperatorKind::BO_LAnd ||
486 FE->getOperator() == BinaryOperatorKind::BO_LOr)) {
487 return calculateConstraintSatisfaction(S, FE, Template, TemplateNameLoc,
488 MLTAL, Satisfaction);
489 }
490
491 // FIXME: We should not treat ConceptSpecializationExpr as atomic constraints.
492
493 // An atomic constraint expression
494 ExprResult SubstitutedAtomicExpr = EvaluateAtomicConstraint(
495 S, AtomicExpr: ConstraintExpr, Template, TemplateNameLoc, MLTAL, Satisfaction);
496
497 if (SubstitutedAtomicExpr.isInvalid())
498 return ExprError();
499
500 if (!SubstitutedAtomicExpr.isUsable())
501 // Evaluator has decided satisfaction without yielding an expression.
502 return ExprEmpty();
503
504 // We don't have the ability to evaluate this, since it contains a
505 // RecoveryExpr, so we want to fail overload resolution. Otherwise,
506 // we'd potentially pick up a different overload, and cause confusing
507 // diagnostics. SO, add a failure detail that will cause us to make this
508 // overload set not viable.
509 if (SubstitutedAtomicExpr.get()->containsErrors()) {
510 Satisfaction.IsSatisfied = false;
511 Satisfaction.ContainsErrors = true;
512
513 PartialDiagnostic Msg = S.PDiag(DiagID: diag::note_constraint_references_error);
514 SmallString<128> DiagString;
515 DiagString = ": ";
516 Msg.EmitToString(Diags&: S.getDiagnostics(), Buf&: DiagString);
517 unsigned MessageSize = DiagString.size();
518 char *Mem = new (S.Context) char[MessageSize];
519 memcpy(dest: Mem, src: DiagString.c_str(), n: MessageSize);
520 Satisfaction.Details.emplace_back(
521 Args: new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
522 SubstitutedAtomicExpr.get()->getBeginLoc(),
523 StringRef(Mem, MessageSize)});
524 return SubstitutedAtomicExpr;
525 }
526
527 EnterExpressionEvaluationContext ConstantEvaluated(
528 S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
529 SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;
530 Expr::EvalResult EvalResult;
531 EvalResult.Diag = &EvaluationDiags;
532 if (!SubstitutedAtomicExpr.get()->EvaluateAsConstantExpr(Result&: EvalResult,
533 Ctx: S.Context) ||
534 !EvaluationDiags.empty()) {
535 // C++2a [temp.constr.atomic]p1
536 // ...E shall be a constant expression of type bool.
537 S.Diag(Loc: SubstitutedAtomicExpr.get()->getBeginLoc(),
538 DiagID: diag::err_non_constant_constraint_expression)
539 << SubstitutedAtomicExpr.get()->getSourceRange();
540 for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
541 S.Diag(Loc: PDiag.first, PD: PDiag.second);
542 return ExprError();
543 }
544
545 assert(EvalResult.Val.isInt() &&
546 "evaluating bool expression didn't produce int");
547 Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
548 if (!Satisfaction.IsSatisfied)
549 Satisfaction.Details.emplace_back(Args: SubstitutedAtomicExpr.get());
550
551 return SubstitutedAtomicExpr;
552}
553
554static ExprResult calculateConstraintSatisfaction(
555 Sema &S, const NamedDecl *Template, SourceLocation TemplateNameLoc,
556 const MultiLevelTemplateArgumentList &MLTAL, const Expr *ConstraintExpr,
557 ConstraintSatisfaction &Satisfaction) {
558
559 return calculateConstraintSatisfaction(S, ConstraintExpr, Template,
560 TemplateNameLoc, MLTAL, Satisfaction);
561}
562
563static bool CheckConstraintSatisfaction(
564 Sema &S, const NamedDecl *Template,
565 ArrayRef<AssociatedConstraint> AssociatedConstraints,
566 llvm::SmallVectorImpl<Expr *> &Converted,
567 const MultiLevelTemplateArgumentList &TemplateArgsLists,
568 SourceRange TemplateIDRange, ConstraintSatisfaction &Satisfaction) {
569 if (AssociatedConstraints.empty()) {
570 Satisfaction.IsSatisfied = true;
571 return false;
572 }
573
574 if (TemplateArgsLists.isAnyArgInstantiationDependent()) {
575 // No need to check satisfaction for dependent constraint expressions.
576 Satisfaction.IsSatisfied = true;
577 return false;
578 }
579
580 ArrayRef<TemplateArgument> TemplateArgs =
581 TemplateArgsLists.getNumSubstitutedLevels() > 0
582 ? TemplateArgsLists.getOutermost()
583 : ArrayRef<TemplateArgument>{};
584 Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
585 Sema::InstantiatingTemplate::ConstraintsCheck{},
586 const_cast<NamedDecl *>(Template), TemplateArgs, TemplateIDRange);
587 if (Inst.isInvalid())
588 return true;
589
590 for (const AssociatedConstraint &AC : AssociatedConstraints) {
591 Sema::ArgPackSubstIndexRAII _(S, AC.ArgPackSubstIndex);
592 ExprResult Res = calculateConstraintSatisfaction(
593 S, Template, TemplateNameLoc: TemplateIDRange.getBegin(), MLTAL: TemplateArgsLists,
594 ConstraintExpr: AC.ConstraintExpr, Satisfaction);
595 if (Res.isInvalid())
596 return true;
597
598 Converted.push_back(Elt: Res.get());
599 if (!Satisfaction.IsSatisfied) {
600 // Backfill the 'converted' list with nulls so we can keep the Converted
601 // and unconverted lists in sync.
602 Converted.append(NumInputs: AssociatedConstraints.size() - Converted.size(),
603 Elt: nullptr);
604 // [temp.constr.op] p2
605 // [...] To determine if a conjunction is satisfied, the satisfaction
606 // of the first operand is checked. If that is not satisfied, the
607 // conjunction is not satisfied. [...]
608 return false;
609 }
610 }
611 return false;
612}
613
614bool Sema::CheckConstraintSatisfaction(
615 const NamedDecl *Template,
616 ArrayRef<AssociatedConstraint> AssociatedConstraints,
617 llvm::SmallVectorImpl<Expr *> &ConvertedConstraints,
618 const MultiLevelTemplateArgumentList &TemplateArgsLists,
619 SourceRange TemplateIDRange, ConstraintSatisfaction &OutSatisfaction) {
620 if (AssociatedConstraints.empty()) {
621 OutSatisfaction.IsSatisfied = true;
622 return false;
623 }
624 if (!Template) {
625 return ::CheckConstraintSatisfaction(
626 S&: *this, Template: nullptr, AssociatedConstraints, Converted&: ConvertedConstraints,
627 TemplateArgsLists, TemplateIDRange, Satisfaction&: OutSatisfaction);
628 }
629 // Invalid templates could make their way here. Substituting them could result
630 // in dependent expressions.
631 if (Template->isInvalidDecl()) {
632 OutSatisfaction.IsSatisfied = false;
633 return true;
634 }
635
636 // A list of the template argument list flattened in a predictible manner for
637 // the purposes of caching. The ConstraintSatisfaction type is in AST so it
638 // has no access to the MultiLevelTemplateArgumentList, so this has to happen
639 // here.
640 llvm::SmallVector<TemplateArgument, 4> FlattenedArgs;
641 for (auto List : TemplateArgsLists)
642 llvm::append_range(C&: FlattenedArgs, R&: List.Args);
643
644 llvm::FoldingSetNodeID ID;
645 ConstraintSatisfaction::Profile(ID, C: Context, ConstraintOwner: Template, TemplateArgs: FlattenedArgs);
646 void *InsertPos;
647 if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
648 OutSatisfaction = *Cached;
649 return false;
650 }
651
652 auto Satisfaction =
653 std::make_unique<ConstraintSatisfaction>(args&: Template, args&: FlattenedArgs);
654 if (::CheckConstraintSatisfaction(S&: *this, Template, AssociatedConstraints,
655 Converted&: ConvertedConstraints, TemplateArgsLists,
656 TemplateIDRange, Satisfaction&: *Satisfaction)) {
657 OutSatisfaction = *Satisfaction;
658 return true;
659 }
660
661 if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
662 // The evaluation of this constraint resulted in us trying to re-evaluate it
663 // recursively. This isn't really possible, except we try to form a
664 // RecoveryExpr as a part of the evaluation. If this is the case, just
665 // return the 'cached' version (which will have the same result), and save
666 // ourselves the extra-insert. If it ever becomes possible to legitimately
667 // recursively check a constraint, we should skip checking the 'inner' one
668 // above, and replace the cached version with this one, as it would be more
669 // specific.
670 OutSatisfaction = *Cached;
671 return false;
672 }
673
674 // Else we can simply add this satisfaction to the list.
675 OutSatisfaction = *Satisfaction;
676 // We cannot use InsertPos here because CheckConstraintSatisfaction might have
677 // invalidated it.
678 // Note that entries of SatisfactionCache are deleted in Sema's destructor.
679 SatisfactionCache.InsertNode(N: Satisfaction.release());
680 return false;
681}
682
683bool Sema::CheckConstraintSatisfaction(
684 const ConceptSpecializationExpr *ConstraintExpr,
685 ConstraintSatisfaction &Satisfaction) {
686
687 MultiLevelTemplateArgumentList MLTAL(ConstraintExpr->getNamedConcept(),
688 ConstraintExpr->getTemplateArguments(),
689 true);
690
691 return calculateConstraintSatisfaction(
692 S&: *this, ConstraintExpr, Template: ConstraintExpr->getNamedConcept(),
693 TemplateNameLoc: ConstraintExpr->getConceptNameLoc(), MLTAL, Satisfaction)
694 .isInvalid();
695}
696
697bool Sema::SetupConstraintScope(
698 FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
699 const MultiLevelTemplateArgumentList &MLTAL,
700 LocalInstantiationScope &Scope) {
701 assert(!isLambdaCallOperator(FD) &&
702 "Use LambdaScopeForCallOperatorInstantiationRAII to handle lambda "
703 "instantiations");
704 if (FD->isTemplateInstantiation() && FD->getPrimaryTemplate()) {
705 FunctionTemplateDecl *PrimaryTemplate = FD->getPrimaryTemplate();
706 InstantiatingTemplate Inst(
707 *this, FD->getPointOfInstantiation(),
708 Sema::InstantiatingTemplate::ConstraintsCheck{}, PrimaryTemplate,
709 TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
710 SourceRange());
711 if (Inst.isInvalid())
712 return true;
713
714 // addInstantiatedParametersToScope creates a map of 'uninstantiated' to
715 // 'instantiated' parameters and adds it to the context. For the case where
716 // this function is a template being instantiated NOW, we also need to add
717 // the list of current template arguments to the list so that they also can
718 // be picked out of the map.
719 if (auto *SpecArgs = FD->getTemplateSpecializationArgs()) {
720 MultiLevelTemplateArgumentList JustTemplArgs(FD, SpecArgs->asArray(),
721 /*Final=*/false);
722 if (addInstantiatedParametersToScope(
723 Function: FD, PatternDecl: PrimaryTemplate->getTemplatedDecl(), Scope, TemplateArgs: JustTemplArgs))
724 return true;
725 }
726
727 // If this is a member function, make sure we get the parameters that
728 // reference the original primary template.
729 if (FunctionTemplateDecl *FromMemTempl =
730 PrimaryTemplate->getInstantiatedFromMemberTemplate()) {
731 if (addInstantiatedParametersToScope(Function: FD, PatternDecl: FromMemTempl->getTemplatedDecl(),
732 Scope, TemplateArgs: MLTAL))
733 return true;
734 }
735
736 return false;
737 }
738
739 if (FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization ||
740 FD->getTemplatedKind() == FunctionDecl::TK_DependentNonTemplate) {
741 FunctionDecl *InstantiatedFrom =
742 FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization
743 ? FD->getInstantiatedFromMemberFunction()
744 : FD->getInstantiatedFromDecl();
745
746 InstantiatingTemplate Inst(
747 *this, FD->getPointOfInstantiation(),
748 Sema::InstantiatingTemplate::ConstraintsCheck{}, InstantiatedFrom,
749 TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
750 SourceRange());
751 if (Inst.isInvalid())
752 return true;
753
754 // Case where this was not a template, but instantiated as a
755 // child-function.
756 if (addInstantiatedParametersToScope(Function: FD, PatternDecl: InstantiatedFrom, Scope, TemplateArgs: MLTAL))
757 return true;
758 }
759
760 return false;
761}
762
763// This function collects all of the template arguments for the purposes of
764// constraint-instantiation and checking.
765std::optional<MultiLevelTemplateArgumentList>
766Sema::SetupConstraintCheckingTemplateArgumentsAndScope(
767 FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
768 LocalInstantiationScope &Scope) {
769 MultiLevelTemplateArgumentList MLTAL;
770
771 // Collect the list of template arguments relative to the 'primary' template.
772 // We need the entire list, since the constraint is completely uninstantiated
773 // at this point.
774 MLTAL =
775 getTemplateInstantiationArgs(D: FD, DC: FD->getLexicalDeclContext(),
776 /*Final=*/false, /*Innermost=*/std::nullopt,
777 /*RelativeToPrimary=*/true,
778 /*Pattern=*/nullptr,
779 /*ForConstraintInstantiation=*/true);
780 // Lambdas are handled by LambdaScopeForCallOperatorInstantiationRAII.
781 if (isLambdaCallOperator(DC: FD))
782 return MLTAL;
783 if (SetupConstraintScope(FD, TemplateArgs, MLTAL, Scope))
784 return std::nullopt;
785
786 return MLTAL;
787}
788
789bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
790 ConstraintSatisfaction &Satisfaction,
791 SourceLocation UsageLoc,
792 bool ForOverloadResolution) {
793 // Don't check constraints if the function is dependent. Also don't check if
794 // this is a function template specialization, as the call to
795 // CheckFunctionTemplateConstraints after this will check it
796 // better.
797 if (FD->isDependentContext() ||
798 FD->getTemplatedKind() ==
799 FunctionDecl::TK_FunctionTemplateSpecialization) {
800 Satisfaction.IsSatisfied = true;
801 return false;
802 }
803
804 // A lambda conversion operator has the same constraints as the call operator
805 // and constraints checking relies on whether we are in a lambda call operator
806 // (and may refer to its parameters), so check the call operator instead.
807 // Note that the declarations outside of the lambda should also be
808 // considered. Turning on the 'ForOverloadResolution' flag results in the
809 // LocalInstantiationScope not looking into its parents, but we can still
810 // access Decls from the parents while building a lambda RAII scope later.
811 if (const auto *MD = dyn_cast<CXXConversionDecl>(Val: FD);
812 MD && isLambdaConversionOperator(C: const_cast<CXXConversionDecl *>(MD)))
813 return CheckFunctionConstraints(FD: MD->getParent()->getLambdaCallOperator(),
814 Satisfaction, UsageLoc,
815 /*ShouldAddDeclsFromParentScope=*/ForOverloadResolution: true);
816
817 DeclContext *CtxToSave = const_cast<FunctionDecl *>(FD);
818
819 while (isLambdaCallOperator(DC: CtxToSave) || FD->isTransparentContext()) {
820 if (isLambdaCallOperator(DC: CtxToSave))
821 CtxToSave = CtxToSave->getParent()->getParent();
822 else
823 CtxToSave = CtxToSave->getNonTransparentContext();
824 }
825
826 ContextRAII SavedContext{*this, CtxToSave};
827 LocalInstantiationScope Scope(*this, !ForOverloadResolution);
828 std::optional<MultiLevelTemplateArgumentList> MLTAL =
829 SetupConstraintCheckingTemplateArgumentsAndScope(
830 FD: const_cast<FunctionDecl *>(FD), TemplateArgs: {}, Scope);
831
832 if (!MLTAL)
833 return true;
834
835 Qualifiers ThisQuals;
836 CXXRecordDecl *Record = nullptr;
837 if (auto *Method = dyn_cast<CXXMethodDecl>(Val: FD)) {
838 ThisQuals = Method->getMethodQualifiers();
839 Record = const_cast<CXXRecordDecl *>(Method->getParent());
840 }
841 CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
842
843 LambdaScopeForCallOperatorInstantiationRAII LambdaScope(
844 *this, const_cast<FunctionDecl *>(FD), *MLTAL, Scope,
845 ForOverloadResolution);
846
847 return CheckConstraintSatisfaction(
848 Template: FD, AssociatedConstraints: FD->getTrailingRequiresClause(), TemplateArgLists: *MLTAL,
849 TemplateIDRange: SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
850 Satisfaction);
851}
852
853
854// Figure out the to-translation-unit depth for this function declaration for
855// the purpose of seeing if they differ by constraints. This isn't the same as
856// getTemplateDepth, because it includes already instantiated parents.
857static unsigned
858CalculateTemplateDepthForConstraints(Sema &S, const NamedDecl *ND,
859 bool SkipForSpecialization = false) {
860 MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
861 D: ND, DC: ND->getLexicalDeclContext(), /*Final=*/false,
862 /*Innermost=*/std::nullopt,
863 /*RelativeToPrimary=*/true,
864 /*Pattern=*/nullptr,
865 /*ForConstraintInstantiation=*/true, SkipForSpecialization);
866 return MLTAL.getNumLevels();
867}
868
869namespace {
870 class AdjustConstraintDepth : public TreeTransform<AdjustConstraintDepth> {
871 unsigned TemplateDepth = 0;
872 public:
873 using inherited = TreeTransform<AdjustConstraintDepth>;
874 AdjustConstraintDepth(Sema &SemaRef, unsigned TemplateDepth)
875 : inherited(SemaRef), TemplateDepth(TemplateDepth) {}
876
877 using inherited::TransformTemplateTypeParmType;
878 QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
879 TemplateTypeParmTypeLoc TL, bool) {
880 const TemplateTypeParmType *T = TL.getTypePtr();
881
882 TemplateTypeParmDecl *NewTTPDecl = nullptr;
883 if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())
884 NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(
885 Val: TransformDecl(Loc: TL.getNameLoc(), D: OldTTPDecl));
886
887 QualType Result = getSema().Context.getTemplateTypeParmType(
888 Depth: T->getDepth() + TemplateDepth, Index: T->getIndex(), ParameterPack: T->isParameterPack(),
889 ParmDecl: NewTTPDecl);
890 TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(T: Result);
891 NewTL.setNameLoc(TL.getNameLoc());
892 return Result;
893 }
894 };
895} // namespace
896
897static const Expr *SubstituteConstraintExpressionWithoutSatisfaction(
898 Sema &S, const Sema::TemplateCompareNewDeclInfo &DeclInfo,
899 const Expr *ConstrExpr) {
900 MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
901 D: DeclInfo.getDecl(), DC: DeclInfo.getLexicalDeclContext(), /*Final=*/false,
902 /*Innermost=*/std::nullopt,
903 /*RelativeToPrimary=*/true,
904 /*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true,
905 /*SkipForSpecialization*/ false);
906
907 if (MLTAL.getNumSubstitutedLevels() == 0)
908 return ConstrExpr;
909
910 Sema::SFINAETrap SFINAE(S);
911
912 Sema::InstantiatingTemplate Inst(
913 S, DeclInfo.getLocation(),
914 Sema::InstantiatingTemplate::ConstraintNormalization{},
915 const_cast<NamedDecl *>(DeclInfo.getDecl()), SourceRange{});
916 if (Inst.isInvalid())
917 return nullptr;
918
919 // Set up a dummy 'instantiation' scope in the case of reference to function
920 // parameters that the surrounding function hasn't been instantiated yet. Note
921 // this may happen while we're comparing two templates' constraint
922 // equivalence.
923 std::optional<LocalInstantiationScope> ScopeForParameters;
924 if (const NamedDecl *ND = DeclInfo.getDecl();
925 ND && ND->isFunctionOrFunctionTemplate()) {
926 ScopeForParameters.emplace(args&: S, /*CombineWithOuterScope=*/args: true);
927 const FunctionDecl *FD = ND->getAsFunction();
928 for (auto *PVD : FD->parameters()) {
929 if (!PVD->isParameterPack()) {
930 ScopeForParameters->InstantiatedLocal(D: PVD, Inst: PVD);
931 continue;
932 }
933 // This is hacky: we're mapping the parameter pack to a size-of-1 argument
934 // to avoid building SubstTemplateTypeParmPackTypes for
935 // PackExpansionTypes. The SubstTemplateTypeParmPackType node would
936 // otherwise reference the AssociatedDecl of the template arguments, which
937 // is, in this case, the template declaration.
938 //
939 // However, as we are in the process of comparing potential
940 // re-declarations, the canonical declaration is the declaration itself at
941 // this point. So if we didn't expand these packs, we would end up with an
942 // incorrect profile difference because we will be profiling the
943 // canonical types!
944 //
945 // FIXME: Improve the "no-transform" machinery in FindInstantiatedDecl so
946 // that we can eliminate the Scope in the cases where the declarations are
947 // not necessarily instantiated. It would also benefit the noexcept
948 // specifier comparison.
949 ScopeForParameters->MakeInstantiatedLocalArgPack(D: PVD);
950 ScopeForParameters->InstantiatedLocalPackArg(D: PVD, Inst: PVD);
951 }
952 }
953
954 std::optional<Sema::CXXThisScopeRAII> ThisScope;
955
956 // See TreeTransform::RebuildTemplateSpecializationType. A context scope is
957 // essential for having an injected class as the canonical type for a template
958 // specialization type at the rebuilding stage. This guarantees that, for
959 // out-of-line definitions, injected class name types and their equivalent
960 // template specializations can be profiled to the same value, which makes it
961 // possible that e.g. constraints involving C<Class<T>> and C<Class> are
962 // perceived identical.
963 std::optional<Sema::ContextRAII> ContextScope;
964 const DeclContext *DC = [&] {
965 if (!DeclInfo.getDecl())
966 return DeclInfo.getDeclContext();
967 return DeclInfo.getDecl()->getFriendObjectKind()
968 ? DeclInfo.getLexicalDeclContext()
969 : DeclInfo.getDeclContext();
970 }();
971 if (auto *RD = dyn_cast<CXXRecordDecl>(Val: DC)) {
972 ThisScope.emplace(args&: S, args: const_cast<CXXRecordDecl *>(RD), args: Qualifiers());
973 ContextScope.emplace(args&: S, args: const_cast<DeclContext *>(cast<DeclContext>(Val: RD)),
974 /*NewThisContext=*/args: false);
975 }
976 EnterExpressionEvaluationContext UnevaluatedContext(
977 S, Sema::ExpressionEvaluationContext::Unevaluated,
978 Sema::ReuseLambdaContextDecl);
979 ExprResult SubstConstr = S.SubstConstraintExprWithoutSatisfaction(
980 E: const_cast<clang::Expr *>(ConstrExpr), TemplateArgs: MLTAL);
981 if (SFINAE.hasErrorOccurred() || !SubstConstr.isUsable())
982 return nullptr;
983 return SubstConstr.get();
984}
985
986bool Sema::AreConstraintExpressionsEqual(const NamedDecl *Old,
987 const Expr *OldConstr,
988 const TemplateCompareNewDeclInfo &New,
989 const Expr *NewConstr) {
990 if (OldConstr == NewConstr)
991 return true;
992 // C++ [temp.constr.decl]p4
993 if (Old && !New.isInvalid() && !New.ContainsDecl(ND: Old) &&
994 Old->getLexicalDeclContext() != New.getLexicalDeclContext()) {
995 if (const Expr *SubstConstr =
996 SubstituteConstraintExpressionWithoutSatisfaction(S&: *this, DeclInfo: Old,
997 ConstrExpr: OldConstr))
998 OldConstr = SubstConstr;
999 else
1000 return false;
1001 if (const Expr *SubstConstr =
1002 SubstituteConstraintExpressionWithoutSatisfaction(S&: *this, DeclInfo: New,
1003 ConstrExpr: NewConstr))
1004 NewConstr = SubstConstr;
1005 else
1006 return false;
1007 }
1008
1009 llvm::FoldingSetNodeID ID1, ID2;
1010 OldConstr->Profile(ID&: ID1, Context, /*Canonical=*/true);
1011 NewConstr->Profile(ID&: ID2, Context, /*Canonical=*/true);
1012 return ID1 == ID2;
1013}
1014
1015bool Sema::FriendConstraintsDependOnEnclosingTemplate(const FunctionDecl *FD) {
1016 assert(FD->getFriendObjectKind() && "Must be a friend!");
1017
1018 // The logic for non-templates is handled in ASTContext::isSameEntity, so we
1019 // don't have to bother checking 'DependsOnEnclosingTemplate' for a
1020 // non-function-template.
1021 assert(FD->getDescribedFunctionTemplate() &&
1022 "Non-function templates don't need to be checked");
1023
1024 SmallVector<AssociatedConstraint, 3> ACs;
1025 FD->getDescribedFunctionTemplate()->getAssociatedConstraints(AC&: ACs);
1026
1027 unsigned OldTemplateDepth = CalculateTemplateDepthForConstraints(S&: *this, ND: FD);
1028 for (const AssociatedConstraint &AC : ACs)
1029 if (ConstraintExpressionDependsOnEnclosingTemplate(Friend: FD, TemplateDepth: OldTemplateDepth,
1030 Constraint: AC.ConstraintExpr))
1031 return true;
1032
1033 return false;
1034}
1035
1036bool Sema::EnsureTemplateArgumentListConstraints(
1037 TemplateDecl *TD, const MultiLevelTemplateArgumentList &TemplateArgsLists,
1038 SourceRange TemplateIDRange) {
1039 ConstraintSatisfaction Satisfaction;
1040 llvm::SmallVector<AssociatedConstraint, 3> AssociatedConstraints;
1041 TD->getAssociatedConstraints(AC&: AssociatedConstraints);
1042 if (CheckConstraintSatisfaction(Template: TD, AssociatedConstraints, TemplateArgLists: TemplateArgsLists,
1043 TemplateIDRange, Satisfaction))
1044 return true;
1045
1046 if (!Satisfaction.IsSatisfied) {
1047 SmallString<128> TemplateArgString;
1048 TemplateArgString = " ";
1049 TemplateArgString += getTemplateArgumentBindingsText(
1050 Params: TD->getTemplateParameters(), Args: TemplateArgsLists.getInnermost().data(),
1051 NumArgs: TemplateArgsLists.getInnermost().size());
1052
1053 Diag(Loc: TemplateIDRange.getBegin(),
1054 DiagID: diag::err_template_arg_list_constraints_not_satisfied)
1055 << (int)getTemplateNameKindForDiagnostics(Name: TemplateName(TD)) << TD
1056 << TemplateArgString << TemplateIDRange;
1057 DiagnoseUnsatisfiedConstraint(Satisfaction);
1058 return true;
1059 }
1060 return false;
1061}
1062
1063static bool CheckFunctionConstraintsWithoutInstantiation(
1064 Sema &SemaRef, SourceLocation PointOfInstantiation,
1065 FunctionTemplateDecl *Template, ArrayRef<TemplateArgument> TemplateArgs,
1066 ConstraintSatisfaction &Satisfaction) {
1067 SmallVector<AssociatedConstraint, 3> TemplateAC;
1068 Template->getAssociatedConstraints(AC&: TemplateAC);
1069 if (TemplateAC.empty()) {
1070 Satisfaction.IsSatisfied = true;
1071 return false;
1072 }
1073
1074 LocalInstantiationScope Scope(SemaRef);
1075
1076 FunctionDecl *FD = Template->getTemplatedDecl();
1077 // Collect the list of template arguments relative to the 'primary'
1078 // template. We need the entire list, since the constraint is completely
1079 // uninstantiated at this point.
1080
1081 // FIXME: Add TemplateArgs through the 'Innermost' parameter once
1082 // the refactoring of getTemplateInstantiationArgs() relands.
1083 MultiLevelTemplateArgumentList MLTAL;
1084 MLTAL.addOuterTemplateArguments(AssociatedDecl: Template, Args: {}, /*Final=*/false);
1085 SemaRef.getTemplateInstantiationArgs(
1086 Result&: MLTAL, /*D=*/FD, DC: FD,
1087 /*Final=*/false, /*Innermost=*/{}, /*RelativeToPrimary=*/true,
1088 /*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true);
1089 MLTAL.replaceInnermostTemplateArguments(AssociatedDecl: Template, Args: TemplateArgs);
1090
1091 Sema::ContextRAII SavedContext(SemaRef, FD);
1092 std::optional<Sema::CXXThisScopeRAII> ThisScope;
1093 if (auto *Method = dyn_cast<CXXMethodDecl>(Val: FD))
1094 ThisScope.emplace(args&: SemaRef, /*Record=*/args: Method->getParent(),
1095 /*ThisQuals=*/args: Method->getMethodQualifiers());
1096 return SemaRef.CheckConstraintSatisfaction(
1097 Template, AssociatedConstraints: TemplateAC, TemplateArgLists: MLTAL, TemplateIDRange: PointOfInstantiation, Satisfaction);
1098}
1099
1100bool Sema::CheckFunctionTemplateConstraints(
1101 SourceLocation PointOfInstantiation, FunctionDecl *Decl,
1102 ArrayRef<TemplateArgument> TemplateArgs,
1103 ConstraintSatisfaction &Satisfaction) {
1104 // In most cases we're not going to have constraints, so check for that first.
1105 FunctionTemplateDecl *Template = Decl->getPrimaryTemplate();
1106
1107 if (!Template)
1108 return ::CheckFunctionConstraintsWithoutInstantiation(
1109 SemaRef&: *this, PointOfInstantiation, Template: Decl->getDescribedFunctionTemplate(),
1110 TemplateArgs, Satisfaction);
1111
1112 // Note - code synthesis context for the constraints check is created
1113 // inside CheckConstraintsSatisfaction.
1114 SmallVector<AssociatedConstraint, 3> TemplateAC;
1115 Template->getAssociatedConstraints(AC&: TemplateAC);
1116 if (TemplateAC.empty()) {
1117 Satisfaction.IsSatisfied = true;
1118 return false;
1119 }
1120
1121 // Enter the scope of this instantiation. We don't use
1122 // PushDeclContext because we don't have a scope.
1123 Sema::ContextRAII savedContext(*this, Decl);
1124 LocalInstantiationScope Scope(*this);
1125
1126 std::optional<MultiLevelTemplateArgumentList> MLTAL =
1127 SetupConstraintCheckingTemplateArgumentsAndScope(FD: Decl, TemplateArgs,
1128 Scope);
1129
1130 if (!MLTAL)
1131 return true;
1132
1133 Qualifiers ThisQuals;
1134 CXXRecordDecl *Record = nullptr;
1135 if (auto *Method = dyn_cast<CXXMethodDecl>(Val: Decl)) {
1136 ThisQuals = Method->getMethodQualifiers();
1137 Record = Method->getParent();
1138 }
1139
1140 CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
1141 LambdaScopeForCallOperatorInstantiationRAII LambdaScope(
1142 *this, const_cast<FunctionDecl *>(Decl), *MLTAL, Scope);
1143
1144 return CheckConstraintSatisfaction(Template, AssociatedConstraints: TemplateAC, TemplateArgLists: *MLTAL,
1145 TemplateIDRange: PointOfInstantiation, Satisfaction);
1146}
1147
1148static void diagnoseUnsatisfiedRequirement(Sema &S,
1149 concepts::ExprRequirement *Req,
1150 bool First) {
1151 assert(!Req->isSatisfied()
1152 && "Diagnose() can only be used on an unsatisfied requirement");
1153 switch (Req->getSatisfactionStatus()) {
1154 case concepts::ExprRequirement::SS_Dependent:
1155 llvm_unreachable("Diagnosing a dependent requirement");
1156 break;
1157 case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {
1158 auto *SubstDiag = Req->getExprSubstitutionDiagnostic();
1159 if (!SubstDiag->DiagMessage.empty())
1160 S.Diag(Loc: SubstDiag->DiagLoc,
1161 DiagID: diag::note_expr_requirement_expr_substitution_error)
1162 << (int)First << SubstDiag->SubstitutedEntity
1163 << SubstDiag->DiagMessage;
1164 else
1165 S.Diag(Loc: SubstDiag->DiagLoc,
1166 DiagID: diag::note_expr_requirement_expr_unknown_substitution_error)
1167 << (int)First << SubstDiag->SubstitutedEntity;
1168 break;
1169 }
1170 case concepts::ExprRequirement::SS_NoexceptNotMet:
1171 S.Diag(Loc: Req->getNoexceptLoc(),
1172 DiagID: diag::note_expr_requirement_noexcept_not_met)
1173 << (int)First << Req->getExpr();
1174 break;
1175 case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
1176 auto *SubstDiag =
1177 Req->getReturnTypeRequirement().getSubstitutionDiagnostic();
1178 if (!SubstDiag->DiagMessage.empty())
1179 S.Diag(Loc: SubstDiag->DiagLoc,
1180 DiagID: diag::note_expr_requirement_type_requirement_substitution_error)
1181 << (int)First << SubstDiag->SubstitutedEntity
1182 << SubstDiag->DiagMessage;
1183 else
1184 S.Diag(Loc: SubstDiag->DiagLoc,
1185 DiagID: diag::note_expr_requirement_type_requirement_unknown_substitution_error)
1186 << (int)First << SubstDiag->SubstitutedEntity;
1187 break;
1188 }
1189 case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {
1190 ConceptSpecializationExpr *ConstraintExpr =
1191 Req->getReturnTypeRequirementSubstitutedConstraintExpr();
1192 if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
1193 // A simple case - expr type is the type being constrained and the concept
1194 // was not provided arguments.
1195 Expr *e = Req->getExpr();
1196 S.Diag(Loc: e->getBeginLoc(),
1197 DiagID: diag::note_expr_requirement_constraints_not_satisfied_simple)
1198 << (int)First << S.Context.getReferenceQualifiedType(e)
1199 << ConstraintExpr->getNamedConcept();
1200 } else {
1201 S.Diag(Loc: ConstraintExpr->getBeginLoc(),
1202 DiagID: diag::note_expr_requirement_constraints_not_satisfied)
1203 << (int)First << ConstraintExpr;
1204 }
1205 S.DiagnoseUnsatisfiedConstraint(Satisfaction: ConstraintExpr->getSatisfaction());
1206 break;
1207 }
1208 case concepts::ExprRequirement::SS_Satisfied:
1209 llvm_unreachable("We checked this above");
1210 }
1211}
1212
1213static void diagnoseUnsatisfiedRequirement(Sema &S,
1214 concepts::TypeRequirement *Req,
1215 bool First) {
1216 assert(!Req->isSatisfied()
1217 && "Diagnose() can only be used on an unsatisfied requirement");
1218 switch (Req->getSatisfactionStatus()) {
1219 case concepts::TypeRequirement::SS_Dependent:
1220 llvm_unreachable("Diagnosing a dependent requirement");
1221 return;
1222 case concepts::TypeRequirement::SS_SubstitutionFailure: {
1223 auto *SubstDiag = Req->getSubstitutionDiagnostic();
1224 if (!SubstDiag->DiagMessage.empty())
1225 S.Diag(Loc: SubstDiag->DiagLoc,
1226 DiagID: diag::note_type_requirement_substitution_error) << (int)First
1227 << SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage;
1228 else
1229 S.Diag(Loc: SubstDiag->DiagLoc,
1230 DiagID: diag::note_type_requirement_unknown_substitution_error)
1231 << (int)First << SubstDiag->SubstitutedEntity;
1232 return;
1233 }
1234 default:
1235 llvm_unreachable("Unknown satisfaction status");
1236 return;
1237 }
1238}
1239static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
1240 Expr *SubstExpr,
1241 bool First = true);
1242
1243static void diagnoseUnsatisfiedRequirement(Sema &S,
1244 concepts::NestedRequirement *Req,
1245 bool First) {
1246 using SubstitutionDiagnostic = std::pair<SourceLocation, StringRef>;
1247 for (auto &Record : Req->getConstraintSatisfaction()) {
1248 if (auto *SubstDiag = Record.dyn_cast<SubstitutionDiagnostic *>())
1249 S.Diag(Loc: SubstDiag->first, DiagID: diag::note_nested_requirement_substitution_error)
1250 << (int)First << Req->getInvalidConstraintEntity()
1251 << SubstDiag->second;
1252 else
1253 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: Record.dyn_cast<Expr *>(),
1254 First);
1255 First = false;
1256 }
1257}
1258
1259static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
1260 Expr *SubstExpr,
1261 bool First) {
1262 SubstExpr = SubstExpr->IgnoreParenImpCasts();
1263 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Val: SubstExpr)) {
1264 switch (BO->getOpcode()) {
1265 // These two cases will in practice only be reached when using fold
1266 // expressions with || and &&, since otherwise the || and && will have been
1267 // broken down into atomic constraints during satisfaction checking.
1268 case BO_LOr:
1269 // Or evaluated to false - meaning both RHS and LHS evaluated to false.
1270 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getLHS(), First);
1271 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getRHS(),
1272 /*First=*/false);
1273 return;
1274 case BO_LAnd: {
1275 bool LHSSatisfied =
1276 BO->getLHS()->EvaluateKnownConstInt(Ctx: S.Context).getBoolValue();
1277 if (LHSSatisfied) {
1278 // LHS is true, so RHS must be false.
1279 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getRHS(), First);
1280 return;
1281 }
1282 // LHS is false
1283 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getLHS(), First);
1284
1285 // RHS might also be false
1286 bool RHSSatisfied =
1287 BO->getRHS()->EvaluateKnownConstInt(Ctx: S.Context).getBoolValue();
1288 if (!RHSSatisfied)
1289 diagnoseWellFormedUnsatisfiedConstraintExpr(S, SubstExpr: BO->getRHS(),
1290 /*First=*/false);
1291 return;
1292 }
1293 case BO_GE:
1294 case BO_LE:
1295 case BO_GT:
1296 case BO_LT:
1297 case BO_EQ:
1298 case BO_NE:
1299 if (BO->getLHS()->getType()->isIntegerType() &&
1300 BO->getRHS()->getType()->isIntegerType()) {
1301 Expr::EvalResult SimplifiedLHS;
1302 Expr::EvalResult SimplifiedRHS;
1303 BO->getLHS()->EvaluateAsInt(Result&: SimplifiedLHS, Ctx: S.Context,
1304 AllowSideEffects: Expr::SE_NoSideEffects,
1305 /*InConstantContext=*/true);
1306 BO->getRHS()->EvaluateAsInt(Result&: SimplifiedRHS, Ctx: S.Context,
1307 AllowSideEffects: Expr::SE_NoSideEffects,
1308 /*InConstantContext=*/true);
1309 if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
1310 S.Diag(Loc: SubstExpr->getBeginLoc(),
1311 DiagID: diag::note_atomic_constraint_evaluated_to_false_elaborated)
1312 << (int)First << SubstExpr
1313 << toString(I: SimplifiedLHS.Val.getInt(), Radix: 10)
1314 << BinaryOperator::getOpcodeStr(Op: BO->getOpcode())
1315 << toString(I: SimplifiedRHS.Val.getInt(), Radix: 10);
1316 return;
1317 }
1318 }
1319 break;
1320
1321 default:
1322 break;
1323 }
1324 } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(Val: SubstExpr)) {
1325 if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
1326 S.Diag(
1327 Loc: CSE->getSourceRange().getBegin(),
1328 DiagID: diag::
1329 note_single_arg_concept_specialization_constraint_evaluated_to_false)
1330 << (int)First
1331 << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
1332 << CSE->getNamedConcept();
1333 } else {
1334 S.Diag(Loc: SubstExpr->getSourceRange().getBegin(),
1335 DiagID: diag::note_concept_specialization_constraint_evaluated_to_false)
1336 << (int)First << CSE;
1337 }
1338 S.DiagnoseUnsatisfiedConstraint(Satisfaction: CSE->getSatisfaction());
1339 return;
1340 } else if (auto *RE = dyn_cast<RequiresExpr>(Val: SubstExpr)) {
1341 // FIXME: RequiresExpr should store dependent diagnostics.
1342 for (concepts::Requirement *Req : RE->getRequirements())
1343 if (!Req->isDependent() && !Req->isSatisfied()) {
1344 if (auto *E = dyn_cast<concepts::ExprRequirement>(Val: Req))
1345 diagnoseUnsatisfiedRequirement(S, Req: E, First);
1346 else if (auto *T = dyn_cast<concepts::TypeRequirement>(Val: Req))
1347 diagnoseUnsatisfiedRequirement(S, Req: T, First);
1348 else
1349 diagnoseUnsatisfiedRequirement(
1350 S, Req: cast<concepts::NestedRequirement>(Val: Req), First);
1351 break;
1352 }
1353 return;
1354 } else if (auto *TTE = dyn_cast<TypeTraitExpr>(Val: SubstExpr);
1355 TTE && TTE->getTrait() == clang::TypeTrait::BTT_IsDeducible) {
1356 assert(TTE->getNumArgs() == 2);
1357 S.Diag(Loc: SubstExpr->getSourceRange().getBegin(),
1358 DiagID: diag::note_is_deducible_constraint_evaluated_to_false)
1359 << TTE->getArg(I: 0)->getType() << TTE->getArg(I: 1)->getType();
1360 return;
1361 }
1362
1363 S.Diag(Loc: SubstExpr->getSourceRange().getBegin(),
1364 DiagID: diag::note_atomic_constraint_evaluated_to_false)
1365 << (int)First << SubstExpr;
1366 S.DiagnoseTypeTraitDetails(E: SubstExpr);
1367}
1368
1369template <typename SubstitutionDiagnostic>
1370static void diagnoseUnsatisfiedConstraintExpr(
1371 Sema &S, const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
1372 bool First = true) {
1373 if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()) {
1374 S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
1375 << Diag->second;
1376 return;
1377 }
1378
1379 diagnoseWellFormedUnsatisfiedConstraintExpr(S, cast<Expr *>(Record), First);
1380}
1381
1382void
1383Sema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction,
1384 bool First) {
1385 assert(!Satisfaction.IsSatisfied &&
1386 "Attempted to diagnose a satisfied constraint");
1387 for (auto &Record : Satisfaction.Details) {
1388 diagnoseUnsatisfiedConstraintExpr(S&: *this, Record, First);
1389 First = false;
1390 }
1391}
1392
1393void Sema::DiagnoseUnsatisfiedConstraint(
1394 const ASTConstraintSatisfaction &Satisfaction,
1395 bool First) {
1396 assert(!Satisfaction.IsSatisfied &&
1397 "Attempted to diagnose a satisfied constraint");
1398 for (auto &Record : Satisfaction) {
1399 diagnoseUnsatisfiedConstraintExpr(S&: *this, Record, First);
1400 First = false;
1401 }
1402}
1403
1404const NormalizedConstraint *Sema::getNormalizedAssociatedConstraints(
1405 const NamedDecl *ConstrainedDecl,
1406 ArrayRef<AssociatedConstraint> AssociatedConstraints) {
1407 // In case the ConstrainedDecl comes from modules, it is necessary to use
1408 // the canonical decl to avoid different atomic constraints with the 'same'
1409 // declarations.
1410 ConstrainedDecl = cast<NamedDecl>(Val: ConstrainedDecl->getCanonicalDecl());
1411
1412 auto CacheEntry = NormalizationCache.find(Val: ConstrainedDecl);
1413 if (CacheEntry == NormalizationCache.end()) {
1414 auto Normalized = NormalizedConstraint::fromAssociatedConstraints(
1415 S&: *this, D: ConstrainedDecl, ACs: AssociatedConstraints);
1416 CacheEntry =
1417 NormalizationCache
1418 .try_emplace(Key: ConstrainedDecl,
1419 Args: Normalized
1420 ? new (Context) NormalizedConstraint(
1421 std::move(*Normalized))
1422 : nullptr)
1423 .first;
1424 }
1425 return CacheEntry->second;
1426}
1427
1428const NormalizedConstraint *clang::getNormalizedAssociatedConstraints(
1429 Sema &S, const NamedDecl *ConstrainedDecl,
1430 ArrayRef<AssociatedConstraint> AssociatedConstraints) {
1431 return S.getNormalizedAssociatedConstraints(ConstrainedDecl,
1432 AssociatedConstraints);
1433}
1434
1435static bool
1436substituteParameterMappings(Sema &S, NormalizedConstraint &N,
1437 ConceptDecl *Concept,
1438 const MultiLevelTemplateArgumentList &MLTAL,
1439 const ASTTemplateArgumentListInfo *ArgsAsWritten) {
1440
1441 if (N.isCompound()) {
1442 if (substituteParameterMappings(S, N&: N.getLHS(), Concept, MLTAL,
1443 ArgsAsWritten))
1444 return true;
1445 return substituteParameterMappings(S, N&: N.getRHS(), Concept, MLTAL,
1446 ArgsAsWritten);
1447 }
1448
1449 if (N.isFoldExpanded()) {
1450 Sema::ArgPackSubstIndexRAII _(S, std::nullopt);
1451 return substituteParameterMappings(
1452 S, N&: N.getFoldExpandedConstraint()->Constraint, Concept, MLTAL,
1453 ArgsAsWritten);
1454 }
1455
1456 TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
1457
1458 AtomicConstraint &Atomic = *N.getAtomicConstraint();
1459 TemplateArgumentListInfo SubstArgs;
1460 if (!Atomic.ParameterMapping) {
1461 llvm::SmallBitVector OccurringIndices(TemplateParams->size());
1462 S.MarkUsedTemplateParameters(E: Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
1463 /*Depth=*/0, Used&: OccurringIndices);
1464 TemplateArgumentLoc *TempArgs =
1465 new (S.Context) TemplateArgumentLoc[OccurringIndices.count()];
1466 for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I)
1467 if (OccurringIndices[I])
1468 new (&(TempArgs)[J++])
1469 TemplateArgumentLoc(S.getIdentityTemplateArgumentLoc(
1470 Param: TemplateParams->begin()[I],
1471 // Here we assume we do not support things like
1472 // template<typename A, typename B>
1473 // concept C = ...;
1474 //
1475 // template<typename... Ts> requires C<Ts...>
1476 // struct S { };
1477 // The above currently yields a diagnostic.
1478 // We still might have default arguments for concept parameters.
1479 Location: ArgsAsWritten->NumTemplateArgs > I
1480 ? ArgsAsWritten->arguments()[I].getLocation()
1481 : SourceLocation()));
1482 Atomic.ParameterMapping.emplace(args&: TempArgs, args: OccurringIndices.count());
1483 }
1484 SourceLocation InstLocBegin =
1485 ArgsAsWritten->arguments().empty()
1486 ? ArgsAsWritten->getLAngleLoc()
1487 : ArgsAsWritten->arguments().front().getSourceRange().getBegin();
1488 SourceLocation InstLocEnd =
1489 ArgsAsWritten->arguments().empty()
1490 ? ArgsAsWritten->getRAngleLoc()
1491 : ArgsAsWritten->arguments().front().getSourceRange().getEnd();
1492 Sema::InstantiatingTemplate Inst(
1493 S, InstLocBegin,
1494 Sema::InstantiatingTemplate::ParameterMappingSubstitution{},
1495 const_cast<NamedDecl *>(Atomic.ConstraintDecl),
1496 {InstLocBegin, InstLocEnd});
1497 if (Inst.isInvalid())
1498 return true;
1499 if (S.SubstTemplateArguments(Args: *Atomic.ParameterMapping, TemplateArgs: MLTAL, Outputs&: SubstArgs))
1500 return true;
1501
1502 TemplateArgumentLoc *TempArgs =
1503 new (S.Context) TemplateArgumentLoc[SubstArgs.size()];
1504 std::copy(first: SubstArgs.arguments().begin(), last: SubstArgs.arguments().end(),
1505 result: TempArgs);
1506 Atomic.ParameterMapping.emplace(args&: TempArgs, args: SubstArgs.size());
1507 return false;
1508}
1509
1510static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
1511 const ConceptSpecializationExpr *CSE) {
1512 MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
1513 D: CSE->getNamedConcept(), DC: CSE->getNamedConcept()->getLexicalDeclContext(),
1514 /*Final=*/false, Innermost: CSE->getTemplateArguments(),
1515 /*RelativeToPrimary=*/true,
1516 /*Pattern=*/nullptr,
1517 /*ForConstraintInstantiation=*/true);
1518
1519 return substituteParameterMappings(S, N, Concept: CSE->getNamedConcept(), MLTAL,
1520 ArgsAsWritten: CSE->getTemplateArgsAsWritten());
1521}
1522
1523NormalizedConstraint::NormalizedConstraint(ASTContext &C,
1524 NormalizedConstraint LHS,
1525 NormalizedConstraint RHS,
1526 CompoundConstraintKind Kind)
1527 : Constraint{CompoundConstraint{
1528 new(C) NormalizedConstraintPair{.LHS: std::move(LHS), .RHS: std::move(RHS)},
1529 Kind}} {}
1530
1531NormalizedConstraint::NormalizedConstraint(ASTContext &C,
1532 const NormalizedConstraint &Other) {
1533 if (Other.isAtomic()) {
1534 Constraint = new (C) AtomicConstraint(*Other.getAtomicConstraint());
1535 } else if (Other.isFoldExpanded()) {
1536 Constraint = new (C) FoldExpandedConstraint(
1537 Other.getFoldExpandedConstraint()->Kind,
1538 NormalizedConstraint(C, Other.getFoldExpandedConstraint()->Constraint),
1539 Other.getFoldExpandedConstraint()->Pattern);
1540 } else {
1541 Constraint = CompoundConstraint(
1542 new (C)
1543 NormalizedConstraintPair{.LHS: NormalizedConstraint(C, Other.getLHS()),
1544 .RHS: NormalizedConstraint(C, Other.getRHS())},
1545 Other.getCompoundKind());
1546 }
1547}
1548
1549NormalizedConstraint &NormalizedConstraint::getLHS() const {
1550 assert(isCompound() && "getLHS called on a non-compound constraint.");
1551 return cast<CompoundConstraint>(Val: Constraint).getPointer()->LHS;
1552}
1553
1554NormalizedConstraint &NormalizedConstraint::getRHS() const {
1555 assert(isCompound() && "getRHS called on a non-compound constraint.");
1556 return cast<CompoundConstraint>(Val: Constraint).getPointer()->RHS;
1557}
1558
1559std::optional<NormalizedConstraint>
1560NormalizedConstraint::fromAssociatedConstraints(
1561 Sema &S, const NamedDecl *D, ArrayRef<AssociatedConstraint> ACs) {
1562 assert(ACs.size() != 0);
1563 auto Conjunction = fromConstraintExpr(S, D, E: ACs[0].ConstraintExpr);
1564 if (!Conjunction)
1565 return std::nullopt;
1566 for (unsigned I = 1; I < ACs.size(); ++I) {
1567 auto Next = fromConstraintExpr(S, D, E: ACs[I].ConstraintExpr);
1568 if (!Next)
1569 return std::nullopt;
1570 *Conjunction = NormalizedConstraint(S.Context, std::move(*Conjunction),
1571 std::move(*Next), CCK_Conjunction);
1572 }
1573 return Conjunction;
1574}
1575
1576std::optional<NormalizedConstraint>
1577NormalizedConstraint::fromConstraintExpr(Sema &S, const NamedDecl *D,
1578 const Expr *E) {
1579 assert(E != nullptr);
1580
1581 // C++ [temp.constr.normal]p1.1
1582 // [...]
1583 // - The normal form of an expression (E) is the normal form of E.
1584 // [...]
1585 E = E->IgnoreParenImpCasts();
1586
1587 // C++2a [temp.param]p4:
1588 // [...] If T is not a pack, then E is E', otherwise E is (E' && ...).
1589 // Fold expression is considered atomic constraints per current wording.
1590 // See http://cplusplus.github.io/concepts-ts/ts-active.html#28
1591
1592 if (LogicalBinOp BO = E) {
1593 auto LHS = fromConstraintExpr(S, D, E: BO.getLHS());
1594 if (!LHS)
1595 return std::nullopt;
1596 auto RHS = fromConstraintExpr(S, D, E: BO.getRHS());
1597 if (!RHS)
1598 return std::nullopt;
1599
1600 return NormalizedConstraint(S.Context, std::move(*LHS), std::move(*RHS),
1601 BO.isAnd() ? CCK_Conjunction : CCK_Disjunction);
1602 } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(Val: E)) {
1603 const NormalizedConstraint *SubNF;
1604 {
1605 Sema::InstantiatingTemplate Inst(
1606 S, CSE->getExprLoc(),
1607 Sema::InstantiatingTemplate::ConstraintNormalization{},
1608 // FIXME: improve const-correctness of InstantiatingTemplate
1609 const_cast<NamedDecl *>(D), CSE->getSourceRange());
1610 if (Inst.isInvalid())
1611 return std::nullopt;
1612 // C++ [temp.constr.normal]p1.1
1613 // [...]
1614 // The normal form of an id-expression of the form C<A1, A2, ..., AN>,
1615 // where C names a concept, is the normal form of the
1616 // constraint-expression of C, after substituting A1, A2, ..., AN for C’s
1617 // respective template parameters in the parameter mappings in each atomic
1618 // constraint. If any such substitution results in an invalid type or
1619 // expression, the program is ill-formed; no diagnostic is required.
1620 // [...]
1621 ConceptDecl *CD = CSE->getNamedConcept();
1622 SubNF = S.getNormalizedAssociatedConstraints(
1623 ConstrainedDecl: CD, AssociatedConstraints: AssociatedConstraint(CD->getConstraintExpr()));
1624 if (!SubNF)
1625 return std::nullopt;
1626 }
1627
1628 std::optional<NormalizedConstraint> New;
1629 New.emplace(args&: S.Context, args: *SubNF);
1630
1631 if (substituteParameterMappings(S, N&: *New, CSE))
1632 return std::nullopt;
1633
1634 return New;
1635 } else if (auto *FE = dyn_cast<const CXXFoldExpr>(Val: E);
1636 FE && S.getLangOpts().CPlusPlus26 &&
1637 (FE->getOperator() == BinaryOperatorKind::BO_LAnd ||
1638 FE->getOperator() == BinaryOperatorKind::BO_LOr)) {
1639
1640 // Normalize fold expressions in C++26.
1641
1642 FoldExpandedConstraint::FoldOperatorKind Kind =
1643 FE->getOperator() == BinaryOperatorKind::BO_LAnd
1644 ? FoldExpandedConstraint::FoldOperatorKind::And
1645 : FoldExpandedConstraint::FoldOperatorKind::Or;
1646
1647 if (FE->getInit()) {
1648 auto LHS = fromConstraintExpr(S, D, E: FE->getLHS());
1649 auto RHS = fromConstraintExpr(S, D, E: FE->getRHS());
1650 if (!LHS || !RHS)
1651 return std::nullopt;
1652
1653 if (FE->isRightFold())
1654 RHS = NormalizedConstraint{new (S.Context) FoldExpandedConstraint{
1655 Kind, std::move(*RHS), FE->getPattern()}};
1656 else
1657 LHS = NormalizedConstraint{new (S.Context) FoldExpandedConstraint{
1658 Kind, std::move(*LHS), FE->getPattern()}};
1659
1660 return NormalizedConstraint(
1661 S.Context, std::move(*LHS), std::move(*RHS),
1662 FE->getOperator() == BinaryOperatorKind::BO_LAnd ? CCK_Conjunction
1663 : CCK_Disjunction);
1664 }
1665 auto Sub = fromConstraintExpr(S, D, E: FE->getPattern());
1666 if (!Sub)
1667 return std::nullopt;
1668 return NormalizedConstraint{new (S.Context) FoldExpandedConstraint{
1669 Kind, std::move(*Sub), FE->getPattern()}};
1670 }
1671
1672 return NormalizedConstraint{new (S.Context) AtomicConstraint(E, D)};
1673}
1674
1675bool FoldExpandedConstraint::AreCompatibleForSubsumption(
1676 const FoldExpandedConstraint &A, const FoldExpandedConstraint &B) {
1677
1678 // [C++26] [temp.constr.fold]
1679 // Two fold expanded constraints are compatible for subsumption
1680 // if their respective constraints both contain an equivalent unexpanded pack.
1681
1682 llvm::SmallVector<UnexpandedParameterPack> APacks, BPacks;
1683 Sema::collectUnexpandedParameterPacks(E: const_cast<Expr *>(A.Pattern), Unexpanded&: APacks);
1684 Sema::collectUnexpandedParameterPacks(E: const_cast<Expr *>(B.Pattern), Unexpanded&: BPacks);
1685
1686 for (const UnexpandedParameterPack &APack : APacks) {
1687 std::pair<unsigned, unsigned> DepthAndIndex = getDepthAndIndex(UPP: APack);
1688 auto it = llvm::find_if(Range&: BPacks, P: [&](const UnexpandedParameterPack &BPack) {
1689 return getDepthAndIndex(UPP: BPack) == DepthAndIndex;
1690 });
1691 if (it != BPacks.end())
1692 return true;
1693 }
1694 return false;
1695}
1696
1697bool Sema::IsAtLeastAsConstrained(const NamedDecl *D1,
1698 MutableArrayRef<AssociatedConstraint> AC1,
1699 const NamedDecl *D2,
1700 MutableArrayRef<AssociatedConstraint> AC2,
1701 bool &Result) {
1702#ifndef NDEBUG
1703 if (const auto *FD1 = dyn_cast<FunctionDecl>(D1)) {
1704 auto IsExpectedEntity = [](const FunctionDecl *FD) {
1705 FunctionDecl::TemplatedKind Kind = FD->getTemplatedKind();
1706 return Kind == FunctionDecl::TK_NonTemplate ||
1707 Kind == FunctionDecl::TK_FunctionTemplate;
1708 };
1709 const auto *FD2 = dyn_cast<FunctionDecl>(D2);
1710 assert(IsExpectedEntity(FD1) && FD2 && IsExpectedEntity(FD2) &&
1711 "use non-instantiated function declaration for constraints partial "
1712 "ordering");
1713 }
1714#endif
1715
1716 if (AC1.empty()) {
1717 Result = AC2.empty();
1718 return false;
1719 }
1720 if (AC2.empty()) {
1721 // TD1 has associated constraints and TD2 does not.
1722 Result = true;
1723 return false;
1724 }
1725
1726 std::pair<const NamedDecl *, const NamedDecl *> Key{D1, D2};
1727 auto CacheEntry = SubsumptionCache.find(Val: Key);
1728 if (CacheEntry != SubsumptionCache.end()) {
1729 Result = CacheEntry->second;
1730 return false;
1731 }
1732
1733 unsigned Depth1 = CalculateTemplateDepthForConstraints(S&: *this, ND: D1, SkipForSpecialization: true);
1734 unsigned Depth2 = CalculateTemplateDepthForConstraints(S&: *this, ND: D2, SkipForSpecialization: true);
1735
1736 for (size_t I = 0; I != AC1.size() && I != AC2.size(); ++I) {
1737 if (Depth2 > Depth1) {
1738 AC1[I].ConstraintExpr =
1739 AdjustConstraintDepth(*this, Depth2 - Depth1)
1740 .TransformExpr(E: const_cast<Expr *>(AC1[I].ConstraintExpr))
1741 .get();
1742 } else if (Depth1 > Depth2) {
1743 AC2[I].ConstraintExpr =
1744 AdjustConstraintDepth(*this, Depth1 - Depth2)
1745 .TransformExpr(E: const_cast<Expr *>(AC2[I].ConstraintExpr))
1746 .get();
1747 }
1748 }
1749
1750 SubsumptionChecker SC(*this);
1751 std::optional<bool> Subsumes = SC.Subsumes(DP: D1, P: AC1, DQ: D2, Q: AC2);
1752 if (!Subsumes) {
1753 // Normalization failed
1754 return true;
1755 }
1756 Result = *Subsumes;
1757 SubsumptionCache.try_emplace(Key, Args&: *Subsumes);
1758 return false;
1759}
1760
1761bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(
1762 const NamedDecl *D1, ArrayRef<AssociatedConstraint> AC1,
1763 const NamedDecl *D2, ArrayRef<AssociatedConstraint> AC2) {
1764 if (isSFINAEContext())
1765 // No need to work here because our notes would be discarded.
1766 return false;
1767
1768 if (AC1.empty() || AC2.empty())
1769 return false;
1770
1771 const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
1772 auto IdenticalExprEvaluator = [&](const AtomicConstraint &A,
1773 const AtomicConstraint &B) {
1774 if (!A.hasMatchingParameterMapping(C&: Context, Other: B))
1775 return false;
1776 const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
1777 if (EA == EB)
1778 return true;
1779
1780 // Not the same source level expression - are the expressions
1781 // identical?
1782 llvm::FoldingSetNodeID IDA, IDB;
1783 EA->Profile(ID&: IDA, Context, /*Canonical=*/true);
1784 EB->Profile(ID&: IDB, Context, /*Canonical=*/true);
1785 if (IDA != IDB)
1786 return false;
1787
1788 AmbiguousAtomic1 = EA;
1789 AmbiguousAtomic2 = EB;
1790 return true;
1791 };
1792
1793 {
1794 // The subsumption checks might cause diagnostics
1795 SFINAETrap Trap(*this);
1796 auto *Normalized1 = getNormalizedAssociatedConstraints(ConstrainedDecl: D1, AssociatedConstraints: AC1);
1797 if (!Normalized1)
1798 return false;
1799
1800 auto *Normalized2 = getNormalizedAssociatedConstraints(ConstrainedDecl: D2, AssociatedConstraints: AC2);
1801 if (!Normalized2)
1802 return false;
1803
1804 SubsumptionChecker SC(*this);
1805
1806 bool Is1AtLeastAs2Normally = SC.Subsumes(P: Normalized1, Q: Normalized2);
1807 bool Is2AtLeastAs1Normally = SC.Subsumes(P: Normalized2, Q: Normalized1);
1808
1809 SubsumptionChecker SC2(*this, IdenticalExprEvaluator);
1810 bool Is1AtLeastAs2 = SC2.Subsumes(P: Normalized1, Q: Normalized2);
1811 bool Is2AtLeastAs1 = SC2.Subsumes(P: Normalized2, Q: Normalized1);
1812
1813 if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
1814 Is2AtLeastAs1 == Is2AtLeastAs1Normally)
1815 // Same result - no ambiguity was caused by identical atomic expressions.
1816 return false;
1817 }
1818 // A different result! Some ambiguous atomic constraint(s) caused a difference
1819 assert(AmbiguousAtomic1 && AmbiguousAtomic2);
1820
1821 Diag(Loc: AmbiguousAtomic1->getBeginLoc(), DiagID: diag::note_ambiguous_atomic_constraints)
1822 << AmbiguousAtomic1->getSourceRange();
1823 Diag(Loc: AmbiguousAtomic2->getBeginLoc(),
1824 DiagID: diag::note_ambiguous_atomic_constraints_similar_expression)
1825 << AmbiguousAtomic2->getSourceRange();
1826 return true;
1827}
1828
1829NormalizedConstraint::CompoundConstraintKind
1830NormalizedConstraint::getCompoundKind() const {
1831 assert(isCompound() && "getCompoundKind on a non-compound constraint..");
1832 return cast<CompoundConstraint>(Val: Constraint).getInt();
1833}
1834
1835AtomicConstraint *NormalizedConstraint::getAtomicConstraint() const {
1836 assert(isAtomic() && "getAtomicConstraint called on non-atomic constraint.");
1837 return cast<AtomicConstraint *>(Val: Constraint);
1838}
1839
1840FoldExpandedConstraint *
1841NormalizedConstraint::getFoldExpandedConstraint() const {
1842 assert(isFoldExpanded() &&
1843 "getFoldExpandedConstraint called on non-fold-expanded constraint.");
1844 return cast<FoldExpandedConstraint *>(Val: Constraint);
1845}
1846
1847//
1848//
1849// ------------------------ Subsumption -----------------------------------
1850//
1851//
1852
1853template <> struct llvm::DenseMapInfo<llvm::FoldingSetNodeID> {
1854
1855 static FoldingSetNodeID getEmptyKey() {
1856 FoldingSetNodeID ID;
1857 ID.AddInteger(I: std::numeric_limits<unsigned>::max());
1858 return ID;
1859 }
1860
1861 static FoldingSetNodeID getTombstoneKey() {
1862 FoldingSetNodeID ID;
1863 for (unsigned I = 0; I < sizeof(ID) / sizeof(unsigned); ++I) {
1864 ID.AddInteger(I: std::numeric_limits<unsigned>::max());
1865 }
1866 return ID;
1867 }
1868
1869 static unsigned getHashValue(const FoldingSetNodeID &Val) {
1870 return Val.ComputeHash();
1871 }
1872
1873 static bool isEqual(const FoldingSetNodeID &LHS,
1874 const FoldingSetNodeID &RHS) {
1875 return LHS == RHS;
1876 }
1877};
1878
1879SubsumptionChecker::SubsumptionChecker(Sema &SemaRef,
1880 SubsumptionCallable Callable)
1881 : SemaRef(SemaRef), Callable(Callable), NextID(1) {}
1882
1883uint16_t SubsumptionChecker::getNewLiteralId() {
1884 assert((unsigned(NextID) + 1 < std::numeric_limits<uint16_t>::max()) &&
1885 "too many constraints!");
1886 return NextID++;
1887}
1888
1889auto SubsumptionChecker::find(AtomicConstraint *Ori) -> Literal {
1890 auto &Elems = AtomicMap[Ori->ConstraintExpr];
1891 // C++ [temp.constr.order] p2
1892 // - an atomic constraint A subsumes another atomic constraint B
1893 // if and only if the A and B are identical [...]
1894 //
1895 // C++ [temp.constr.atomic] p2
1896 // Two atomic constraints are identical if they are formed from the
1897 // same expression and the targets of the parameter mappings are
1898 // equivalent according to the rules for expressions [...]
1899
1900 // Because subsumption of atomic constraints is an identity
1901 // relationship that does not require further analysis
1902 // We cache the results such that if an atomic constraint literal
1903 // subsumes another, their literal will be the same
1904
1905 llvm::FoldingSetNodeID ID;
1906 const auto &Mapping = Ori->ParameterMapping;
1907 ID.AddBoolean(B: Mapping.has_value());
1908 if (Mapping) {
1909 for (const TemplateArgumentLoc &TAL : *Mapping) {
1910 SemaRef.getASTContext()
1911 .getCanonicalTemplateArgument(Arg: TAL.getArgument())
1912 .Profile(ID, Context: SemaRef.getASTContext());
1913 }
1914 }
1915 auto It = Elems.find(Val: ID);
1916 if (It == Elems.end()) {
1917 It = Elems
1918 .insert(KV: {ID,
1919 MappedAtomicConstraint{
1920 .Constraint: Ori, .ID: {.Value: getNewLiteralId(), .Kind: Literal::Atomic}}})
1921 .first;
1922 ReverseMap[It->second.ID.Value] = Ori;
1923 }
1924 return It->getSecond().ID;
1925}
1926
1927auto SubsumptionChecker::find(FoldExpandedConstraint *Ori) -> Literal {
1928 auto &Elems = FoldMap[Ori->Pattern];
1929
1930 FoldExpendedConstraintKey K;
1931 K.Kind = Ori->Kind;
1932
1933 auto It = llvm::find_if(Range&: Elems, P: [&K](const FoldExpendedConstraintKey &Other) {
1934 return K.Kind == Other.Kind;
1935 });
1936 if (It == Elems.end()) {
1937 K.ID = {.Value: getNewLiteralId(), .Kind: Literal::FoldExpanded};
1938 It = Elems.insert(position: Elems.end(), x: std::move(K));
1939 ReverseMap[It->ID.Value] = Ori;
1940 }
1941 return It->ID;
1942}
1943
1944auto SubsumptionChecker::CNF(const NormalizedConstraint &C) -> CNFFormula {
1945 return SubsumptionChecker::Normalize<CNFFormula>(NC: C);
1946}
1947auto SubsumptionChecker::DNF(const NormalizedConstraint &C) -> DNFFormula {
1948 return SubsumptionChecker::Normalize<DNFFormula>(NC: C);
1949}
1950
1951///
1952/// \brief SubsumptionChecker::Normalize
1953///
1954/// Normalize a formula to Conjunctive Normal Form or
1955/// Disjunctive normal form.
1956///
1957/// Each Atomic (and Fold Expanded) constraint gets represented by
1958/// a single id to reduce space.
1959///
1960/// To minimize risks of exponential blow up, if two atomic
1961/// constraints subsumes each other (same constraint and mapping),
1962/// they are represented by the same literal.
1963///
1964template <typename FormulaType>
1965FormulaType SubsumptionChecker::Normalize(const NormalizedConstraint &NC) {
1966 FormulaType Res;
1967
1968 auto Add = [&, this](Clause C) {
1969 // Sort each clause and remove duplicates for faster comparisons.
1970 llvm::sort(C);
1971 C.erase(CS: llvm::unique(R&: C), CE: C.end());
1972 AddUniqueClauseToFormula(F&: Res, C: std::move(C));
1973 };
1974
1975 if (NC.isAtomic())
1976 return {{find(Ori: NC.getAtomicConstraint())}};
1977
1978 if (NC.isFoldExpanded())
1979 return {{find(Ori: NC.getFoldExpandedConstraint())}};
1980
1981 FormulaType Left, Right;
1982 SemaRef.runWithSufficientStackSpace(Loc: SourceLocation(), Fn: [&] {
1983 Left = Normalize<FormulaType>(NC.getLHS());
1984 Right = Normalize<FormulaType>(NC.getRHS());
1985 });
1986
1987 if (NC.getCompoundKind() == FormulaType::Kind) {
1988 auto SizeLeft = Left.size();
1989 Res = std::move(Left);
1990 Res.reserve(SizeLeft + Right.size());
1991 std::for_each(std::make_move_iterator(Right.begin()),
1992 std::make_move_iterator(Right.end()), Add);
1993 return Res;
1994 }
1995
1996 Res.reserve(Left.size() * Right.size());
1997 for (const auto &LTransform : Left) {
1998 for (const auto &RTransform : Right) {
1999 Clause Combined;
2000 Combined.reserve(N: LTransform.size() + RTransform.size());
2001 llvm::append_range(Combined, LTransform);
2002 llvm::append_range(Combined, RTransform);
2003 Add(std::move(Combined));
2004 }
2005 }
2006 return Res;
2007}
2008
2009void SubsumptionChecker::AddUniqueClauseToFormula(Formula &F, Clause C) {
2010 for (auto &Other : F) {
2011 if (llvm::equal(LRange&: C, RRange&: Other))
2012 return;
2013 }
2014 F.push_back(Elt: C);
2015}
2016
2017std::optional<bool> SubsumptionChecker::Subsumes(
2018 const NamedDecl *DP, ArrayRef<AssociatedConstraint> P, const NamedDecl *DQ,
2019 ArrayRef<AssociatedConstraint> Q) {
2020 const NormalizedConstraint *PNormalized =
2021 getNormalizedAssociatedConstraints(S&: SemaRef, ConstrainedDecl: DP, AssociatedConstraints: P);
2022 if (!PNormalized)
2023 return std::nullopt;
2024
2025 const NormalizedConstraint *QNormalized =
2026 getNormalizedAssociatedConstraints(S&: SemaRef, ConstrainedDecl: DQ, AssociatedConstraints: Q);
2027 if (!QNormalized)
2028 return std::nullopt;
2029
2030 return Subsumes(P: PNormalized, Q: QNormalized);
2031}
2032
2033bool SubsumptionChecker::Subsumes(const NormalizedConstraint *P,
2034 const NormalizedConstraint *Q) {
2035
2036 DNFFormula DNFP = DNF(C: *P);
2037 CNFFormula CNFQ = CNF(C: *Q);
2038 return Subsumes(P: DNFP, Q: CNFQ);
2039}
2040
2041bool SubsumptionChecker::Subsumes(const DNFFormula &PDNF,
2042 const CNFFormula &QCNF) {
2043 for (const auto &Pi : PDNF) {
2044 for (const auto &Qj : QCNF) {
2045 // C++ [temp.constr.order] p2
2046 // - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
2047 // and only if there exists an atomic constraint Pia in Pi for which
2048 // there exists an atomic constraint, Qjb, in Qj such that Pia
2049 // subsumes Qjb.
2050 if (!DNFSubsumes(P: Pi, Q: Qj))
2051 return false;
2052 }
2053 }
2054 return true;
2055}
2056
2057bool SubsumptionChecker::DNFSubsumes(const Clause &P, const Clause &Q) {
2058
2059 return llvm::any_of(Range: P, P: [&](Literal LP) {
2060 return llvm::any_of(Range: Q, P: [this, LP](Literal LQ) { return Subsumes(A: LP, B: LQ); });
2061 });
2062}
2063
2064bool SubsumptionChecker::Subsumes(const FoldExpandedConstraint *A,
2065 const FoldExpandedConstraint *B) {
2066 std::pair<const FoldExpandedConstraint *, const FoldExpandedConstraint *> Key{
2067 A, B};
2068
2069 auto It = FoldSubsumptionCache.find(Val: Key);
2070 if (It == FoldSubsumptionCache.end()) {
2071 // C++ [temp.constr.order]
2072 // a fold expanded constraint A subsumes another fold expanded
2073 // constraint B if they are compatible for subsumption, have the same
2074 // fold-operator, and the constraint of A subsumes that of B.
2075 bool DoesSubsume =
2076 A->Kind == B->Kind &&
2077 FoldExpandedConstraint::AreCompatibleForSubsumption(A: *A, B: *B) &&
2078 Subsumes(P: &A->Constraint, Q: &B->Constraint);
2079 It = FoldSubsumptionCache.try_emplace(Key: std::move(Key), Args&: DoesSubsume).first;
2080 }
2081 return It->second;
2082}
2083
2084bool SubsumptionChecker::Subsumes(Literal A, Literal B) {
2085 if (A.Kind != B.Kind)
2086 return false;
2087 switch (A.Kind) {
2088 case Literal::Atomic:
2089 if (!Callable)
2090 return A.Value == B.Value;
2091 return Callable(
2092 *static_cast<const AtomicConstraint *>(ReverseMap[A.Value]),
2093 *static_cast<const AtomicConstraint *>(ReverseMap[B.Value]));
2094 case Literal::FoldExpanded:
2095 return Subsumes(
2096 A: static_cast<const FoldExpandedConstraint *>(ReverseMap[A.Value]),
2097 B: static_cast<const FoldExpandedConstraint *>(ReverseMap[B.Value]));
2098 }
2099 llvm_unreachable("unknown literal kind");
2100}
2101