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