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

source code of clang/lib/Sema/SemaConcept.cpp