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
34 using namespace clang;
35 using namespace sema;
36
37 namespace {
38 class LogicalBinOp {
39 SourceLocation Loc;
40 OverloadedOperatorKind Op = OO_None;
41 const Expr *LHS = nullptr;
42 const Expr *RHS = nullptr;
43
44 public:
LogicalBinOp(const Expr * E)45 LogicalBinOp(const Expr *E) {
46 if (auto *BO = dyn_cast<BinaryOperator>(E)) {
47 Op = BinaryOperator::getOverloadedOperator(BO->getOpcode());
48 LHS = BO->getLHS();
49 RHS = BO->getRHS();
50 Loc = BO->getExprLoc();
51 } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(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
isAnd() const62 bool isAnd() const { return Op == OO_AmpAmp; }
isOr() const63 bool isOr() const { return Op == OO_PipePipe; }
operator bool() const64 explicit operator bool() const { return isAnd() || isOr(); }
65
getLHS() const66 const Expr *getLHS() const { return LHS; }
getRHS() const67 const Expr *getRHS() const { return RHS; }
68
recreateBinOp(Sema & SemaRef,ExprResult LHS) const69 ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS) const {
70 return recreateBinOp(SemaRef, LHS, const_cast<Expr *>(getRHS()));
71 }
72
recreateBinOp(Sema & SemaRef,ExprResult LHS,ExprResult RHS) const73 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(SemaRef.Context, LHS.get(), RHS.get(),
84 BinaryOperator::getOverloadedOpcode(Op),
85 SemaRef.Context.BoolTy, VK_PRValue,
86 OK_Ordinary, Loc, FPOptionsOverride{});
87 }
88 };
89 }
90
CheckConstraintExpression(const Expr * ConstraintExpression,Token NextToken,bool * PossibleNonPrimary,bool IsTrailingRequiresClause)91 bool 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(BO.getLHS(), NextToken,
101 PossibleNonPrimary) &&
102 CheckConstraintExpression(BO.getRHS(), NextToken,
103 PossibleNonPrimary);
104 } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression))
105 return CheckConstraintExpression(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(tok::l_paren) &&
126 (IsTrailingRequiresClause ||
127 (Type->isDependentType() &&
128 isa<UnresolvedLookupExpr>(ConstraintExpression) &&
129 !dyn_cast_if_present<LambdaScopeInfo>(getCurFunction())) ||
130 Type->isFunctionType() ||
131 Type->isSpecificBuiltinType(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(NextToken.getKind(),
138 /*GreaterThanIsOperator=*/true,
139 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(Type, 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
161 namespace {
162 struct SatisfactionStackRAII {
163 Sema &SemaRef;
164 bool Inserted = false;
SatisfactionStackRAII__anoncfc64a490311::SatisfactionStackRAII165 SatisfactionStackRAII(Sema &SemaRef, const NamedDecl *ND,
166 const llvm::FoldingSetNodeID &FSNID)
167 : SemaRef(SemaRef) {
168 if (ND) {
169 SemaRef.PushSatisfactionStackEntry(ND, FSNID);
170 Inserted = true;
171 }
172 }
~SatisfactionStackRAII__anoncfc64a490311::SatisfactionStackRAII173 ~SatisfactionStackRAII() {
174 if (Inserted)
175 SemaRef.PopSatisfactionStackEntry();
176 }
177 };
178 } // namespace
179
180 template <typename AtomicEvaluator>
181 static ExprResult
calculateConstraintSatisfaction(Sema & S,const Expr * ConstraintExpr,ConstraintSatisfaction & Satisfaction,AtomicEvaluator && Evaluator)182 calculateConstraintSatisfaction(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(EffectiveDetailEnd, EffectiveDetailEndIndex);
234 Satisfaction.Details.erase(EffectiveDetailEnd,
235 Satisfaction.Details.end());
236 }
237
238 return BO.recreateBinOp(S, LHSRes, RHSRes);
239 }
240
241 if (auto *C = dyn_cast<ExprWithCleanups>(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(S.getDiagnostics(), DiagString);
272 unsigned MessageSize = DiagString.size();
273 char *Mem = new (S.Context) char[MessageSize];
274 memcpy(Mem, DiagString.c_str(), MessageSize);
275 Satisfaction.Details.emplace_back(
276 ConstraintExpr,
277 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(EvalResult,
289 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(ConstraintExpr,
306 SubstitutedAtomicExpr.get());
307
308 return SubstitutedAtomicExpr;
309 }
310
311 static bool
DiagRecursiveConstraintEval(Sema & S,llvm::FoldingSetNodeID & ID,const NamedDecl * Templ,const Expr * E,const MultiLevelTemplateArgumentList & MLTAL)312 DiagRecursiveConstraintEval(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, 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(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
calculateConstraintSatisfaction(Sema & S,const NamedDecl * Template,SourceLocation TemplateNameLoc,const MultiLevelTemplateArgumentList & MLTAL,const Expr * ConstraintExpr,ConstraintSatisfaction & Satisfaction)335 static 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, [&](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, Template, 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(const_cast<Expr *>(AtomicExpr), 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(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(S.getDiagnostics(), DiagString);
392 unsigned MessageSize = DiagString.size();
393 char *Mem = new (S.Context) char[MessageSize];
394 memcpy(Mem, DiagString.c_str(), MessageSize);
395 Satisfaction.Details.emplace_back(
396 AtomicExpr,
397 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(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 S.Context, SubstitutedExpression.get()->getType(),
420 CK_LValueToRValue, SubstitutedExpression.get(),
421 /*BasePath=*/nullptr, VK_PRValue, FPOptionsOverride());
422
423 return SubstitutedExpression;
424 });
425 }
426
CheckConstraintSatisfaction(Sema & S,const NamedDecl * Template,ArrayRef<const Expr * > ConstraintExprs,llvm::SmallVectorImpl<Expr * > & Converted,const MultiLevelTemplateArgumentList & TemplateArgsLists,SourceRange TemplateIDRange,ConstraintSatisfaction & Satisfaction)427 static 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, TemplateIDRange.getBegin(), TemplateArgsLists,
456 ConstraintExpr, Satisfaction);
457 if (Res.isInvalid())
458 return true;
459
460 Converted.push_back(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(ConstraintExprs.size() - Converted.size(), 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
CheckConstraintSatisfaction(const NamedDecl * Template,ArrayRef<const Expr * > ConstraintExprs,llvm::SmallVectorImpl<Expr * > & ConvertedConstraints,const MultiLevelTemplateArgumentList & TemplateArgsLists,SourceRange TemplateIDRange,ConstraintSatisfaction & OutSatisfaction)475 bool 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 *this, nullptr, ConstraintExprs, ConvertedConstraints,
487 TemplateArgsLists, TemplateIDRange, 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(FlattenedArgs.end(), List.Args.begin(),
497 List.Args.end());
498
499 llvm::FoldingSetNodeID ID;
500 ConstraintSatisfaction::Profile(ID, Context, Template, 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>(Template, FlattenedArgs);
509 if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
510 ConvertedConstraints, TemplateArgsLists,
511 TemplateIDRange, *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(Satisfaction.release());
535 return false;
536 }
537
CheckConstraintSatisfaction(const Expr * ConstraintExpr,ConstraintSatisfaction & Satisfaction)538 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
539 ConstraintSatisfaction &Satisfaction) {
540 return calculateConstraintSatisfaction(
541 *this, ConstraintExpr, Satisfaction,
542 [this](const Expr *AtomicExpr) -> ExprResult {
543 // We only do this to immitate lvalue-to-rvalue conversion.
544 return PerformContextuallyConvertToBool(
545 const_cast<Expr *>(AtomicExpr));
546 })
547 .isInvalid();
548 }
549
addInstantiatedCapturesToScope(FunctionDecl * Function,const FunctionDecl * PatternDecl,LocalInstantiationScope & Scope,const MultiLevelTemplateArgumentList & TemplateArgs)550 bool Sema::addInstantiatedCapturesToScope(
551 FunctionDecl *Function, const FunctionDecl *PatternDecl,
552 LocalInstantiationScope &Scope,
553 const MultiLevelTemplateArgumentList &TemplateArgs) {
554 const auto *LambdaClass = cast<CXXMethodDecl>(Function)->getParent();
555 const auto *LambdaPattern = cast<CXXMethodDecl>(PatternDecl)->getParent();
556
557 unsigned Instantiated = 0;
558
559 auto AddSingleCapture = [&](const ValueDecl *CapturedPattern,
560 unsigned Index) {
561 ValueDecl *CapturedVar = LambdaClass->getCapture(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(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
SetupConstraintScope(FunctionDecl * FD,std::optional<ArrayRef<TemplateArgument>> TemplateArgs,MultiLevelTemplateArgumentList MLTAL,LocalInstantiationScope & Scope)587 bool Sema::SetupConstraintScope(
588 FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
589 MultiLevelTemplateArgumentList MLTAL, LocalInstantiationScope &Scope) {
590 if (FD->isTemplateInstantiation() && FD->getPrimaryTemplate()) {
591 FunctionTemplateDecl *PrimaryTemplate = FD->getPrimaryTemplate();
592 InstantiatingTemplate Inst(
593 *this, FD->getPointOfInstantiation(),
594 Sema::InstantiatingTemplate::ConstraintsCheck{}, PrimaryTemplate,
595 TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
596 SourceRange());
597 if (Inst.isInvalid())
598 return true;
599
600 // addInstantiatedParametersToScope creates a map of 'uninstantiated' to
601 // 'instantiated' parameters and adds it to the context. For the case where
602 // this function is a template being instantiated NOW, we also need to add
603 // the list of current template arguments to the list so that they also can
604 // be picked out of the map.
605 if (auto *SpecArgs = FD->getTemplateSpecializationArgs()) {
606 MultiLevelTemplateArgumentList JustTemplArgs(FD, SpecArgs->asArray(),
607 /*Final=*/false);
608 if (addInstantiatedParametersToScope(
609 FD, PrimaryTemplate->getTemplatedDecl(), Scope, JustTemplArgs))
610 return true;
611 }
612
613 // If this is a member function, make sure we get the parameters that
614 // reference the original primary template.
615 // We walk up the instantiated template chain so that nested lambdas get
616 // handled properly.
617 for (FunctionTemplateDecl *FromMemTempl =
618 PrimaryTemplate->getInstantiatedFromMemberTemplate();
619 FromMemTempl;
620 FromMemTempl = FromMemTempl->getInstantiatedFromMemberTemplate()) {
621 if (addInstantiatedParametersToScope(FD, FromMemTempl->getTemplatedDecl(),
622 Scope, MLTAL))
623 return true;
624 }
625
626 return false;
627 }
628
629 if (FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization ||
630 FD->getTemplatedKind() == FunctionDecl::TK_DependentNonTemplate) {
631 FunctionDecl *InstantiatedFrom =
632 FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization
633 ? FD->getInstantiatedFromMemberFunction()
634 : FD->getInstantiatedFromDecl();
635
636 InstantiatingTemplate Inst(
637 *this, FD->getPointOfInstantiation(),
638 Sema::InstantiatingTemplate::ConstraintsCheck{}, InstantiatedFrom,
639 TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{},
640 SourceRange());
641 if (Inst.isInvalid())
642 return true;
643
644 // Case where this was not a template, but instantiated as a
645 // child-function.
646 if (addInstantiatedParametersToScope(FD, InstantiatedFrom, Scope, MLTAL))
647 return true;
648 }
649
650 return false;
651 }
652
653 // This function collects all of the template arguments for the purposes of
654 // constraint-instantiation and checking.
655 std::optional<MultiLevelTemplateArgumentList>
SetupConstraintCheckingTemplateArgumentsAndScope(FunctionDecl * FD,std::optional<ArrayRef<TemplateArgument>> TemplateArgs,LocalInstantiationScope & Scope)656 Sema::SetupConstraintCheckingTemplateArgumentsAndScope(
657 FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs,
658 LocalInstantiationScope &Scope) {
659 MultiLevelTemplateArgumentList MLTAL;
660
661 // Collect the list of template arguments relative to the 'primary' template.
662 // We need the entire list, since the constraint is completely uninstantiated
663 // at this point.
664 MLTAL = getTemplateInstantiationArgs(FD, FD->getLexicalDeclContext(),
665 /*Final=*/false, /*Innermost=*/nullptr,
666 /*RelativeToPrimary=*/true,
667 /*Pattern=*/nullptr,
668 /*ForConstraintInstantiation=*/true);
669 if (SetupConstraintScope(FD, TemplateArgs, MLTAL, Scope))
670 return std::nullopt;
671
672 return MLTAL;
673 }
674
CheckFunctionConstraints(const FunctionDecl * FD,ConstraintSatisfaction & Satisfaction,SourceLocation UsageLoc,bool ForOverloadResolution)675 bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
676 ConstraintSatisfaction &Satisfaction,
677 SourceLocation UsageLoc,
678 bool ForOverloadResolution) {
679 // Don't check constraints if the function is dependent. Also don't check if
680 // this is a function template specialization, as the call to
681 // CheckinstantiatedFunctionTemplateConstraints after this will check it
682 // better.
683 if (FD->isDependentContext() ||
684 FD->getTemplatedKind() ==
685 FunctionDecl::TK_FunctionTemplateSpecialization) {
686 Satisfaction.IsSatisfied = true;
687 return false;
688 }
689
690 // A lambda conversion operator has the same constraints as the call operator
691 // and constraints checking relies on whether we are in a lambda call operator
692 // (and may refer to its parameters), so check the call operator instead.
693 if (const auto *MD = dyn_cast<CXXConversionDecl>(FD);
694 MD && isLambdaConversionOperator(const_cast<CXXConversionDecl *>(MD)))
695 return CheckFunctionConstraints(MD->getParent()->getLambdaCallOperator(),
696 Satisfaction, UsageLoc,
697 ForOverloadResolution);
698
699 DeclContext *CtxToSave = const_cast<FunctionDecl *>(FD);
700
701 while (isLambdaCallOperator(CtxToSave) || FD->isTransparentContext()) {
702 if (isLambdaCallOperator(CtxToSave))
703 CtxToSave = CtxToSave->getParent()->getParent();
704 else
705 CtxToSave = CtxToSave->getNonTransparentContext();
706 }
707
708 ContextRAII SavedContext{*this, CtxToSave};
709 LocalInstantiationScope Scope(*this, !ForOverloadResolution);
710 std::optional<MultiLevelTemplateArgumentList> MLTAL =
711 SetupConstraintCheckingTemplateArgumentsAndScope(
712 const_cast<FunctionDecl *>(FD), {}, Scope);
713
714 if (!MLTAL)
715 return true;
716
717 Qualifiers ThisQuals;
718 CXXRecordDecl *Record = nullptr;
719 if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) {
720 ThisQuals = Method->getMethodQualifiers();
721 Record = const_cast<CXXRecordDecl *>(Method->getParent());
722 }
723 CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
724
725 LambdaScopeForCallOperatorInstantiationRAII LambdaScope(
726 *this, const_cast<FunctionDecl *>(FD), *MLTAL, Scope,
727 ForOverloadResolution);
728
729 return CheckConstraintSatisfaction(
730 FD, {FD->getTrailingRequiresClause()}, *MLTAL,
731 SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
732 Satisfaction);
733 }
734
735
736 // Figure out the to-translation-unit depth for this function declaration for
737 // the purpose of seeing if they differ by constraints. This isn't the same as
738 // getTemplateDepth, because it includes already instantiated parents.
739 static unsigned
CalculateTemplateDepthForConstraints(Sema & S,const NamedDecl * ND,bool SkipForSpecialization=false)740 CalculateTemplateDepthForConstraints(Sema &S, const NamedDecl *ND,
741 bool SkipForSpecialization = false) {
742 MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
743 ND, ND->getLexicalDeclContext(), /*Final=*/false, /*Innermost=*/nullptr,
744 /*RelativeToPrimary=*/true,
745 /*Pattern=*/nullptr,
746 /*ForConstraintInstantiation=*/true, SkipForSpecialization);
747 return MLTAL.getNumLevels();
748 }
749
750 namespace {
751 class AdjustConstraintDepth : public TreeTransform<AdjustConstraintDepth> {
752 unsigned TemplateDepth = 0;
753 public:
754 using inherited = TreeTransform<AdjustConstraintDepth>;
AdjustConstraintDepth(Sema & SemaRef,unsigned TemplateDepth)755 AdjustConstraintDepth(Sema &SemaRef, unsigned TemplateDepth)
756 : inherited(SemaRef), TemplateDepth(TemplateDepth) {}
757
758 using inherited::TransformTemplateTypeParmType;
TransformTemplateTypeParmType(TypeLocBuilder & TLB,TemplateTypeParmTypeLoc TL,bool)759 QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB,
760 TemplateTypeParmTypeLoc TL, bool) {
761 const TemplateTypeParmType *T = TL.getTypePtr();
762
763 TemplateTypeParmDecl *NewTTPDecl = nullptr;
764 if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl())
765 NewTTPDecl = cast_or_null<TemplateTypeParmDecl>(
766 TransformDecl(TL.getNameLoc(), OldTTPDecl));
767
768 QualType Result = getSema().Context.getTemplateTypeParmType(
769 T->getDepth() + TemplateDepth, T->getIndex(), T->isParameterPack(),
770 NewTTPDecl);
771 TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result);
772 NewTL.setNameLoc(TL.getNameLoc());
773 return Result;
774 }
775 };
776 } // namespace
777
SubstituteConstraintExpressionWithoutSatisfaction(Sema & S,const Sema::TemplateCompareNewDeclInfo & DeclInfo,const Expr * ConstrExpr)778 static const Expr *SubstituteConstraintExpressionWithoutSatisfaction(
779 Sema &S, const Sema::TemplateCompareNewDeclInfo &DeclInfo,
780 const Expr *ConstrExpr) {
781 MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
782 DeclInfo.getDecl(), DeclInfo.getLexicalDeclContext(), /*Final=*/false,
783 /*Innermost=*/nullptr,
784 /*RelativeToPrimary=*/true,
785 /*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true,
786 /*SkipForSpecialization*/ false);
787
788 if (MLTAL.getNumSubstitutedLevels() == 0)
789 return ConstrExpr;
790
791 Sema::SFINAETrap SFINAE(S, /*AccessCheckingSFINAE=*/false);
792
793 Sema::InstantiatingTemplate Inst(
794 S, DeclInfo.getLocation(),
795 Sema::InstantiatingTemplate::ConstraintNormalization{},
796 const_cast<NamedDecl *>(DeclInfo.getDecl()), SourceRange{});
797 if (Inst.isInvalid())
798 return nullptr;
799
800 std::optional<Sema::CXXThisScopeRAII> ThisScope;
801 if (auto *RD = dyn_cast<CXXRecordDecl>(DeclInfo.getDeclContext()))
802 ThisScope.emplace(S, const_cast<CXXRecordDecl *>(RD), Qualifiers());
803 ExprResult SubstConstr = S.SubstConstraintExprWithoutSatisfaction(
804 const_cast<clang::Expr *>(ConstrExpr), MLTAL);
805 if (SFINAE.hasErrorOccurred() || !SubstConstr.isUsable())
806 return nullptr;
807 return SubstConstr.get();
808 }
809
AreConstraintExpressionsEqual(const NamedDecl * Old,const Expr * OldConstr,const TemplateCompareNewDeclInfo & New,const Expr * NewConstr)810 bool Sema::AreConstraintExpressionsEqual(const NamedDecl *Old,
811 const Expr *OldConstr,
812 const TemplateCompareNewDeclInfo &New,
813 const Expr *NewConstr) {
814 if (OldConstr == NewConstr)
815 return true;
816 // C++ [temp.constr.decl]p4
817 if (Old && !New.isInvalid() && !New.ContainsDecl(Old) &&
818 Old->getLexicalDeclContext() != New.getLexicalDeclContext()) {
819 if (const Expr *SubstConstr =
820 SubstituteConstraintExpressionWithoutSatisfaction(*this, Old,
821 OldConstr))
822 OldConstr = SubstConstr;
823 else
824 return false;
825 if (const Expr *SubstConstr =
826 SubstituteConstraintExpressionWithoutSatisfaction(*this, New,
827 NewConstr))
828 NewConstr = SubstConstr;
829 else
830 return false;
831 }
832
833 llvm::FoldingSetNodeID ID1, ID2;
834 OldConstr->Profile(ID1, Context, /*Canonical=*/true);
835 NewConstr->Profile(ID2, Context, /*Canonical=*/true);
836 return ID1 == ID2;
837 }
838
FriendConstraintsDependOnEnclosingTemplate(const FunctionDecl * FD)839 bool Sema::FriendConstraintsDependOnEnclosingTemplate(const FunctionDecl *FD) {
840 assert(FD->getFriendObjectKind() && "Must be a friend!");
841
842 // The logic for non-templates is handled in ASTContext::isSameEntity, so we
843 // don't have to bother checking 'DependsOnEnclosingTemplate' for a
844 // non-function-template.
845 assert(FD->getDescribedFunctionTemplate() &&
846 "Non-function templates don't need to be checked");
847
848 SmallVector<const Expr *, 3> ACs;
849 FD->getDescribedFunctionTemplate()->getAssociatedConstraints(ACs);
850
851 unsigned OldTemplateDepth = CalculateTemplateDepthForConstraints(*this, FD);
852 for (const Expr *Constraint : ACs)
853 if (ConstraintExpressionDependsOnEnclosingTemplate(FD, OldTemplateDepth,
854 Constraint))
855 return true;
856
857 return false;
858 }
859
EnsureTemplateArgumentListConstraints(TemplateDecl * TD,const MultiLevelTemplateArgumentList & TemplateArgsLists,SourceRange TemplateIDRange)860 bool Sema::EnsureTemplateArgumentListConstraints(
861 TemplateDecl *TD, const MultiLevelTemplateArgumentList &TemplateArgsLists,
862 SourceRange TemplateIDRange) {
863 ConstraintSatisfaction Satisfaction;
864 llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
865 TD->getAssociatedConstraints(AssociatedConstraints);
866 if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgsLists,
867 TemplateIDRange, Satisfaction))
868 return true;
869
870 if (!Satisfaction.IsSatisfied) {
871 SmallString<128> TemplateArgString;
872 TemplateArgString = " ";
873 TemplateArgString += getTemplateArgumentBindingsText(
874 TD->getTemplateParameters(), TemplateArgsLists.getInnermost().data(),
875 TemplateArgsLists.getInnermost().size());
876
877 Diag(TemplateIDRange.getBegin(),
878 diag::err_template_arg_list_constraints_not_satisfied)
879 << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD
880 << TemplateArgString << TemplateIDRange;
881 DiagnoseUnsatisfiedConstraint(Satisfaction);
882 return true;
883 }
884 return false;
885 }
886
CheckInstantiatedFunctionTemplateConstraints(SourceLocation PointOfInstantiation,FunctionDecl * Decl,ArrayRef<TemplateArgument> TemplateArgs,ConstraintSatisfaction & Satisfaction)887 bool Sema::CheckInstantiatedFunctionTemplateConstraints(
888 SourceLocation PointOfInstantiation, FunctionDecl *Decl,
889 ArrayRef<TemplateArgument> TemplateArgs,
890 ConstraintSatisfaction &Satisfaction) {
891 // In most cases we're not going to have constraints, so check for that first.
892 FunctionTemplateDecl *Template = Decl->getPrimaryTemplate();
893 // Note - code synthesis context for the constraints check is created
894 // inside CheckConstraintsSatisfaction.
895 SmallVector<const Expr *, 3> TemplateAC;
896 Template->getAssociatedConstraints(TemplateAC);
897 if (TemplateAC.empty()) {
898 Satisfaction.IsSatisfied = true;
899 return false;
900 }
901
902 // Enter the scope of this instantiation. We don't use
903 // PushDeclContext because we don't have a scope.
904 Sema::ContextRAII savedContext(*this, Decl);
905 LocalInstantiationScope Scope(*this);
906
907 std::optional<MultiLevelTemplateArgumentList> MLTAL =
908 SetupConstraintCheckingTemplateArgumentsAndScope(Decl, TemplateArgs,
909 Scope);
910
911 if (!MLTAL)
912 return true;
913
914 Qualifiers ThisQuals;
915 CXXRecordDecl *Record = nullptr;
916 if (auto *Method = dyn_cast<CXXMethodDecl>(Decl)) {
917 ThisQuals = Method->getMethodQualifiers();
918 Record = Method->getParent();
919 }
920
921 CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
922 LambdaScopeForCallOperatorInstantiationRAII LambdaScope(
923 *this, const_cast<FunctionDecl *>(Decl), *MLTAL, Scope);
924
925 llvm::SmallVector<Expr *, 1> Converted;
926 return CheckConstraintSatisfaction(Template, TemplateAC, Converted, *MLTAL,
927 PointOfInstantiation, Satisfaction);
928 }
929
diagnoseUnsatisfiedRequirement(Sema & S,concepts::ExprRequirement * Req,bool First)930 static void diagnoseUnsatisfiedRequirement(Sema &S,
931 concepts::ExprRequirement *Req,
932 bool First) {
933 assert(!Req->isSatisfied()
934 && "Diagnose() can only be used on an unsatisfied requirement");
935 switch (Req->getSatisfactionStatus()) {
936 case concepts::ExprRequirement::SS_Dependent:
937 llvm_unreachable("Diagnosing a dependent requirement");
938 break;
939 case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {
940 auto *SubstDiag = Req->getExprSubstitutionDiagnostic();
941 if (!SubstDiag->DiagMessage.empty())
942 S.Diag(SubstDiag->DiagLoc,
943 diag::note_expr_requirement_expr_substitution_error)
944 << (int)First << SubstDiag->SubstitutedEntity
945 << SubstDiag->DiagMessage;
946 else
947 S.Diag(SubstDiag->DiagLoc,
948 diag::note_expr_requirement_expr_unknown_substitution_error)
949 << (int)First << SubstDiag->SubstitutedEntity;
950 break;
951 }
952 case concepts::ExprRequirement::SS_NoexceptNotMet:
953 S.Diag(Req->getNoexceptLoc(),
954 diag::note_expr_requirement_noexcept_not_met)
955 << (int)First << Req->getExpr();
956 break;
957 case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
958 auto *SubstDiag =
959 Req->getReturnTypeRequirement().getSubstitutionDiagnostic();
960 if (!SubstDiag->DiagMessage.empty())
961 S.Diag(SubstDiag->DiagLoc,
962 diag::note_expr_requirement_type_requirement_substitution_error)
963 << (int)First << SubstDiag->SubstitutedEntity
964 << SubstDiag->DiagMessage;
965 else
966 S.Diag(SubstDiag->DiagLoc,
967 diag::note_expr_requirement_type_requirement_unknown_substitution_error)
968 << (int)First << SubstDiag->SubstitutedEntity;
969 break;
970 }
971 case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {
972 ConceptSpecializationExpr *ConstraintExpr =
973 Req->getReturnTypeRequirementSubstitutedConstraintExpr();
974 if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
975 // A simple case - expr type is the type being constrained and the concept
976 // was not provided arguments.
977 Expr *e = Req->getExpr();
978 S.Diag(e->getBeginLoc(),
979 diag::note_expr_requirement_constraints_not_satisfied_simple)
980 << (int)First << S.Context.getReferenceQualifiedType(e)
981 << ConstraintExpr->getNamedConcept();
982 } else {
983 S.Diag(ConstraintExpr->getBeginLoc(),
984 diag::note_expr_requirement_constraints_not_satisfied)
985 << (int)First << ConstraintExpr;
986 }
987 S.DiagnoseUnsatisfiedConstraint(ConstraintExpr->getSatisfaction());
988 break;
989 }
990 case concepts::ExprRequirement::SS_Satisfied:
991 llvm_unreachable("We checked this above");
992 }
993 }
994
diagnoseUnsatisfiedRequirement(Sema & S,concepts::TypeRequirement * Req,bool First)995 static void diagnoseUnsatisfiedRequirement(Sema &S,
996 concepts::TypeRequirement *Req,
997 bool First) {
998 assert(!Req->isSatisfied()
999 && "Diagnose() can only be used on an unsatisfied requirement");
1000 switch (Req->getSatisfactionStatus()) {
1001 case concepts::TypeRequirement::SS_Dependent:
1002 llvm_unreachable("Diagnosing a dependent requirement");
1003 return;
1004 case concepts::TypeRequirement::SS_SubstitutionFailure: {
1005 auto *SubstDiag = Req->getSubstitutionDiagnostic();
1006 if (!SubstDiag->DiagMessage.empty())
1007 S.Diag(SubstDiag->DiagLoc,
1008 diag::note_type_requirement_substitution_error) << (int)First
1009 << SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage;
1010 else
1011 S.Diag(SubstDiag->DiagLoc,
1012 diag::note_type_requirement_unknown_substitution_error)
1013 << (int)First << SubstDiag->SubstitutedEntity;
1014 return;
1015 }
1016 default:
1017 llvm_unreachable("Unknown satisfaction status");
1018 return;
1019 }
1020 }
1021 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
1022 Expr *SubstExpr,
1023 bool First = true);
1024
diagnoseUnsatisfiedRequirement(Sema & S,concepts::NestedRequirement * Req,bool First)1025 static void diagnoseUnsatisfiedRequirement(Sema &S,
1026 concepts::NestedRequirement *Req,
1027 bool First) {
1028 using SubstitutionDiagnostic = std::pair<SourceLocation, StringRef>;
1029 for (auto &Pair : Req->getConstraintSatisfaction()) {
1030 if (auto *SubstDiag = Pair.second.dyn_cast<SubstitutionDiagnostic *>())
1031 S.Diag(SubstDiag->first, diag::note_nested_requirement_substitution_error)
1032 << (int)First << Req->getInvalidConstraintEntity() << SubstDiag->second;
1033 else
1034 diagnoseWellFormedUnsatisfiedConstraintExpr(
1035 S, Pair.second.dyn_cast<Expr *>(), First);
1036 First = false;
1037 }
1038 }
1039
diagnoseWellFormedUnsatisfiedConstraintExpr(Sema & S,Expr * SubstExpr,bool First)1040 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
1041 Expr *SubstExpr,
1042 bool First) {
1043 SubstExpr = SubstExpr->IgnoreParenImpCasts();
1044 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {
1045 switch (BO->getOpcode()) {
1046 // These two cases will in practice only be reached when using fold
1047 // expressions with || and &&, since otherwise the || and && will have been
1048 // broken down into atomic constraints during satisfaction checking.
1049 case BO_LOr:
1050 // Or evaluated to false - meaning both RHS and LHS evaluated to false.
1051 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
1052 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
1053 /*First=*/false);
1054 return;
1055 case BO_LAnd: {
1056 bool LHSSatisfied =
1057 BO->getLHS()->EvaluateKnownConstInt(S.Context).getBoolValue();
1058 if (LHSSatisfied) {
1059 // LHS is true, so RHS must be false.
1060 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First);
1061 return;
1062 }
1063 // LHS is false
1064 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
1065
1066 // RHS might also be false
1067 bool RHSSatisfied =
1068 BO->getRHS()->EvaluateKnownConstInt(S.Context).getBoolValue();
1069 if (!RHSSatisfied)
1070 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
1071 /*First=*/false);
1072 return;
1073 }
1074 case BO_GE:
1075 case BO_LE:
1076 case BO_GT:
1077 case BO_LT:
1078 case BO_EQ:
1079 case BO_NE:
1080 if (BO->getLHS()->getType()->isIntegerType() &&
1081 BO->getRHS()->getType()->isIntegerType()) {
1082 Expr::EvalResult SimplifiedLHS;
1083 Expr::EvalResult SimplifiedRHS;
1084 BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context,
1085 Expr::SE_NoSideEffects,
1086 /*InConstantContext=*/true);
1087 BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context,
1088 Expr::SE_NoSideEffects,
1089 /*InConstantContext=*/true);
1090 if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
1091 S.Diag(SubstExpr->getBeginLoc(),
1092 diag::note_atomic_constraint_evaluated_to_false_elaborated)
1093 << (int)First << SubstExpr
1094 << toString(SimplifiedLHS.Val.getInt(), 10)
1095 << BinaryOperator::getOpcodeStr(BO->getOpcode())
1096 << toString(SimplifiedRHS.Val.getInt(), 10);
1097 return;
1098 }
1099 }
1100 break;
1101
1102 default:
1103 break;
1104 }
1105 } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) {
1106 if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
1107 S.Diag(
1108 CSE->getSourceRange().getBegin(),
1109 diag::
1110 note_single_arg_concept_specialization_constraint_evaluated_to_false)
1111 << (int)First
1112 << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
1113 << CSE->getNamedConcept();
1114 } else {
1115 S.Diag(SubstExpr->getSourceRange().getBegin(),
1116 diag::note_concept_specialization_constraint_evaluated_to_false)
1117 << (int)First << CSE;
1118 }
1119 S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction());
1120 return;
1121 } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) {
1122 // FIXME: RequiresExpr should store dependent diagnostics.
1123 for (concepts::Requirement *Req : RE->getRequirements())
1124 if (!Req->isDependent() && !Req->isSatisfied()) {
1125 if (auto *E = dyn_cast<concepts::ExprRequirement>(Req))
1126 diagnoseUnsatisfiedRequirement(S, E, First);
1127 else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req))
1128 diagnoseUnsatisfiedRequirement(S, T, First);
1129 else
1130 diagnoseUnsatisfiedRequirement(
1131 S, cast<concepts::NestedRequirement>(Req), First);
1132 break;
1133 }
1134 return;
1135 }
1136
1137 S.Diag(SubstExpr->getSourceRange().getBegin(),
1138 diag::note_atomic_constraint_evaluated_to_false)
1139 << (int)First << SubstExpr;
1140 }
1141
1142 template<typename SubstitutionDiagnostic>
diagnoseUnsatisfiedConstraintExpr(Sema & S,const Expr * E,const llvm::PointerUnion<Expr *,SubstitutionDiagnostic * > & Record,bool First=true)1143 static void diagnoseUnsatisfiedConstraintExpr(
1144 Sema &S, const Expr *E,
1145 const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
1146 bool First = true) {
1147 if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){
1148 S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
1149 << Diag->second;
1150 return;
1151 }
1152
1153 diagnoseWellFormedUnsatisfiedConstraintExpr(S,
1154 Record.template get<Expr *>(), First);
1155 }
1156
1157 void
DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction & Satisfaction,bool First)1158 Sema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction,
1159 bool First) {
1160 assert(!Satisfaction.IsSatisfied &&
1161 "Attempted to diagnose a satisfied constraint");
1162 for (auto &Pair : Satisfaction.Details) {
1163 diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
1164 First = false;
1165 }
1166 }
1167
DiagnoseUnsatisfiedConstraint(const ASTConstraintSatisfaction & Satisfaction,bool First)1168 void Sema::DiagnoseUnsatisfiedConstraint(
1169 const ASTConstraintSatisfaction &Satisfaction,
1170 bool First) {
1171 assert(!Satisfaction.IsSatisfied &&
1172 "Attempted to diagnose a satisfied constraint");
1173 for (auto &Pair : Satisfaction) {
1174 diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
1175 First = false;
1176 }
1177 }
1178
1179 const NormalizedConstraint *
getNormalizedAssociatedConstraints(NamedDecl * ConstrainedDecl,ArrayRef<const Expr * > AssociatedConstraints)1180 Sema::getNormalizedAssociatedConstraints(
1181 NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) {
1182 // In case the ConstrainedDecl comes from modules, it is necessary to use
1183 // the canonical decl to avoid different atomic constraints with the 'same'
1184 // declarations.
1185 ConstrainedDecl = cast<NamedDecl>(ConstrainedDecl->getCanonicalDecl());
1186
1187 auto CacheEntry = NormalizationCache.find(ConstrainedDecl);
1188 if (CacheEntry == NormalizationCache.end()) {
1189 auto Normalized =
1190 NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl,
1191 AssociatedConstraints);
1192 CacheEntry =
1193 NormalizationCache
1194 .try_emplace(ConstrainedDecl,
1195 Normalized
1196 ? new (Context) NormalizedConstraint(
1197 std::move(*Normalized))
1198 : nullptr)
1199 .first;
1200 }
1201 return CacheEntry->second;
1202 }
1203
1204 static bool
substituteParameterMappings(Sema & S,NormalizedConstraint & N,ConceptDecl * Concept,const MultiLevelTemplateArgumentList & MLTAL,const ASTTemplateArgumentListInfo * ArgsAsWritten)1205 substituteParameterMappings(Sema &S, NormalizedConstraint &N,
1206 ConceptDecl *Concept,
1207 const MultiLevelTemplateArgumentList &MLTAL,
1208 const ASTTemplateArgumentListInfo *ArgsAsWritten) {
1209 if (!N.isAtomic()) {
1210 if (substituteParameterMappings(S, N.getLHS(), Concept, MLTAL,
1211 ArgsAsWritten))
1212 return true;
1213 return substituteParameterMappings(S, N.getRHS(), Concept, MLTAL,
1214 ArgsAsWritten);
1215 }
1216 TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
1217
1218 AtomicConstraint &Atomic = *N.getAtomicConstraint();
1219 TemplateArgumentListInfo SubstArgs;
1220 if (!Atomic.ParameterMapping) {
1221 llvm::SmallBitVector OccurringIndices(TemplateParams->size());
1222 S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
1223 /*Depth=*/0, OccurringIndices);
1224 TemplateArgumentLoc *TempArgs =
1225 new (S.Context) TemplateArgumentLoc[OccurringIndices.count()];
1226 for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I)
1227 if (OccurringIndices[I])
1228 new (&(TempArgs)[J++])
1229 TemplateArgumentLoc(S.getIdentityTemplateArgumentLoc(
1230 TemplateParams->begin()[I],
1231 // Here we assume we do not support things like
1232 // template<typename A, typename B>
1233 // concept C = ...;
1234 //
1235 // template<typename... Ts> requires C<Ts...>
1236 // struct S { };
1237 // The above currently yields a diagnostic.
1238 // We still might have default arguments for concept parameters.
1239 ArgsAsWritten->NumTemplateArgs > I
1240 ? ArgsAsWritten->arguments()[I].getLocation()
1241 : SourceLocation()));
1242 Atomic.ParameterMapping.emplace(TempArgs, OccurringIndices.count());
1243 }
1244 Sema::InstantiatingTemplate Inst(
1245 S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(),
1246 Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept,
1247 ArgsAsWritten->arguments().front().getSourceRange());
1248 if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs))
1249 return true;
1250
1251 TemplateArgumentLoc *TempArgs =
1252 new (S.Context) TemplateArgumentLoc[SubstArgs.size()];
1253 std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(),
1254 TempArgs);
1255 Atomic.ParameterMapping.emplace(TempArgs, SubstArgs.size());
1256 return false;
1257 }
1258
substituteParameterMappings(Sema & S,NormalizedConstraint & N,const ConceptSpecializationExpr * CSE)1259 static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
1260 const ConceptSpecializationExpr *CSE) {
1261 TemplateArgumentList TAL{TemplateArgumentList::OnStack,
1262 CSE->getTemplateArguments()};
1263 MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
1264 CSE->getNamedConcept(), CSE->getNamedConcept()->getLexicalDeclContext(),
1265 /*Final=*/false, &TAL,
1266 /*RelativeToPrimary=*/true,
1267 /*Pattern=*/nullptr,
1268 /*ForConstraintInstantiation=*/true);
1269
1270 return substituteParameterMappings(S, N, CSE->getNamedConcept(), MLTAL,
1271 CSE->getTemplateArgsAsWritten());
1272 }
1273
1274 std::optional<NormalizedConstraint>
fromConstraintExprs(Sema & S,NamedDecl * D,ArrayRef<const Expr * > E)1275 NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D,
1276 ArrayRef<const Expr *> E) {
1277 assert(E.size() != 0);
1278 auto Conjunction = fromConstraintExpr(S, D, E[0]);
1279 if (!Conjunction)
1280 return std::nullopt;
1281 for (unsigned I = 1; I < E.size(); ++I) {
1282 auto Next = fromConstraintExpr(S, D, E[I]);
1283 if (!Next)
1284 return std::nullopt;
1285 *Conjunction = NormalizedConstraint(S.Context, std::move(*Conjunction),
1286 std::move(*Next), CCK_Conjunction);
1287 }
1288 return Conjunction;
1289 }
1290
1291 std::optional<NormalizedConstraint>
fromConstraintExpr(Sema & S,NamedDecl * D,const Expr * E)1292 NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
1293 assert(E != nullptr);
1294
1295 // C++ [temp.constr.normal]p1.1
1296 // [...]
1297 // - The normal form of an expression (E) is the normal form of E.
1298 // [...]
1299 E = E->IgnoreParenImpCasts();
1300
1301 // C++2a [temp.param]p4:
1302 // [...] If T is not a pack, then E is E', otherwise E is (E' && ...).
1303 // Fold expression is considered atomic constraints per current wording.
1304 // See http://cplusplus.github.io/concepts-ts/ts-active.html#28
1305
1306 if (LogicalBinOp BO = E) {
1307 auto LHS = fromConstraintExpr(S, D, BO.getLHS());
1308 if (!LHS)
1309 return std::nullopt;
1310 auto RHS = fromConstraintExpr(S, D, BO.getRHS());
1311 if (!RHS)
1312 return std::nullopt;
1313
1314 return NormalizedConstraint(S.Context, std::move(*LHS), std::move(*RHS),
1315 BO.isAnd() ? CCK_Conjunction : CCK_Disjunction);
1316 } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) {
1317 const NormalizedConstraint *SubNF;
1318 {
1319 Sema::InstantiatingTemplate Inst(
1320 S, CSE->getExprLoc(),
1321 Sema::InstantiatingTemplate::ConstraintNormalization{}, D,
1322 CSE->getSourceRange());
1323 // C++ [temp.constr.normal]p1.1
1324 // [...]
1325 // The normal form of an id-expression of the form C<A1, A2, ..., AN>,
1326 // where C names a concept, is the normal form of the
1327 // constraint-expression of C, after substituting A1, A2, ..., AN for C’s
1328 // respective template parameters in the parameter mappings in each atomic
1329 // constraint. If any such substitution results in an invalid type or
1330 // expression, the program is ill-formed; no diagnostic is required.
1331 // [...]
1332 ConceptDecl *CD = CSE->getNamedConcept();
1333 SubNF = S.getNormalizedAssociatedConstraints(CD,
1334 {CD->getConstraintExpr()});
1335 if (!SubNF)
1336 return std::nullopt;
1337 }
1338
1339 std::optional<NormalizedConstraint> New;
1340 New.emplace(S.Context, *SubNF);
1341
1342 if (substituteParameterMappings(S, *New, CSE))
1343 return std::nullopt;
1344
1345 return New;
1346 }
1347 return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)};
1348 }
1349
1350 using NormalForm =
1351 llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>;
1352
makeCNF(const NormalizedConstraint & Normalized)1353 static NormalForm makeCNF(const NormalizedConstraint &Normalized) {
1354 if (Normalized.isAtomic())
1355 return {{Normalized.getAtomicConstraint()}};
1356
1357 NormalForm LCNF = makeCNF(Normalized.getLHS());
1358 NormalForm RCNF = makeCNF(Normalized.getRHS());
1359 if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
1360 LCNF.reserve(LCNF.size() + RCNF.size());
1361 while (!RCNF.empty())
1362 LCNF.push_back(RCNF.pop_back_val());
1363 return LCNF;
1364 }
1365
1366 // Disjunction
1367 NormalForm Res;
1368 Res.reserve(LCNF.size() * RCNF.size());
1369 for (auto &LDisjunction : LCNF)
1370 for (auto &RDisjunction : RCNF) {
1371 NormalForm::value_type Combined;
1372 Combined.reserve(LDisjunction.size() + RDisjunction.size());
1373 std::copy(LDisjunction.begin(), LDisjunction.end(),
1374 std::back_inserter(Combined));
1375 std::copy(RDisjunction.begin(), RDisjunction.end(),
1376 std::back_inserter(Combined));
1377 Res.emplace_back(Combined);
1378 }
1379 return Res;
1380 }
1381
makeDNF(const NormalizedConstraint & Normalized)1382 static NormalForm makeDNF(const NormalizedConstraint &Normalized) {
1383 if (Normalized.isAtomic())
1384 return {{Normalized.getAtomicConstraint()}};
1385
1386 NormalForm LDNF = makeDNF(Normalized.getLHS());
1387 NormalForm RDNF = makeDNF(Normalized.getRHS());
1388 if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
1389 LDNF.reserve(LDNF.size() + RDNF.size());
1390 while (!RDNF.empty())
1391 LDNF.push_back(RDNF.pop_back_val());
1392 return LDNF;
1393 }
1394
1395 // Conjunction
1396 NormalForm Res;
1397 Res.reserve(LDNF.size() * RDNF.size());
1398 for (auto &LConjunction : LDNF) {
1399 for (auto &RConjunction : RDNF) {
1400 NormalForm::value_type Combined;
1401 Combined.reserve(LConjunction.size() + RConjunction.size());
1402 std::copy(LConjunction.begin(), LConjunction.end(),
1403 std::back_inserter(Combined));
1404 std::copy(RConjunction.begin(), RConjunction.end(),
1405 std::back_inserter(Combined));
1406 Res.emplace_back(Combined);
1407 }
1408 }
1409 return Res;
1410 }
1411
1412 template<typename AtomicSubsumptionEvaluator>
subsumes(const NormalForm & PDNF,const NormalForm & QCNF,AtomicSubsumptionEvaluator E)1413 static bool subsumes(const NormalForm &PDNF, const NormalForm &QCNF,
1414 AtomicSubsumptionEvaluator E) {
1415 // C++ [temp.constr.order] p2
1416 // Then, P subsumes Q if and only if, for every disjunctive clause Pi in the
1417 // disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in
1418 // the conjuctive normal form of Q, where [...]
1419 for (const auto &Pi : PDNF) {
1420 for (const auto &Qj : QCNF) {
1421 // C++ [temp.constr.order] p2
1422 // - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
1423 // and only if there exists an atomic constraint Pia in Pi for which
1424 // there exists an atomic constraint, Qjb, in Qj such that Pia
1425 // subsumes Qjb.
1426 bool Found = false;
1427 for (const AtomicConstraint *Pia : Pi) {
1428 for (const AtomicConstraint *Qjb : Qj) {
1429 if (E(*Pia, *Qjb)) {
1430 Found = true;
1431 break;
1432 }
1433 }
1434 if (Found)
1435 break;
1436 }
1437 if (!Found)
1438 return false;
1439 }
1440 }
1441 return true;
1442 }
1443
1444 template<typename AtomicSubsumptionEvaluator>
subsumes(Sema & S,NamedDecl * DP,ArrayRef<const Expr * > P,NamedDecl * DQ,ArrayRef<const Expr * > Q,bool & Subsumes,AtomicSubsumptionEvaluator E)1445 static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
1446 NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes,
1447 AtomicSubsumptionEvaluator E) {
1448 // C++ [temp.constr.order] p2
1449 // In order to determine if a constraint P subsumes a constraint Q, P is
1450 // transformed into disjunctive normal form, and Q is transformed into
1451 // conjunctive normal form. [...]
1452 auto *PNormalized = S.getNormalizedAssociatedConstraints(DP, P);
1453 if (!PNormalized)
1454 return true;
1455 const NormalForm PDNF = makeDNF(*PNormalized);
1456
1457 auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q);
1458 if (!QNormalized)
1459 return true;
1460 const NormalForm QCNF = makeCNF(*QNormalized);
1461
1462 Subsumes = subsumes(PDNF, QCNF, E);
1463 return false;
1464 }
1465
IsAtLeastAsConstrained(NamedDecl * D1,MutableArrayRef<const Expr * > AC1,NamedDecl * D2,MutableArrayRef<const Expr * > AC2,bool & Result)1466 bool Sema::IsAtLeastAsConstrained(NamedDecl *D1,
1467 MutableArrayRef<const Expr *> AC1,
1468 NamedDecl *D2,
1469 MutableArrayRef<const Expr *> AC2,
1470 bool &Result) {
1471 if (const auto *FD1 = dyn_cast<FunctionDecl>(D1)) {
1472 auto IsExpectedEntity = [](const FunctionDecl *FD) {
1473 FunctionDecl::TemplatedKind Kind = FD->getTemplatedKind();
1474 return Kind == FunctionDecl::TK_NonTemplate ||
1475 Kind == FunctionDecl::TK_FunctionTemplate;
1476 };
1477 const auto *FD2 = dyn_cast<FunctionDecl>(D2);
1478 (void)IsExpectedEntity;
1479 (void)FD1;
1480 (void)FD2;
1481 assert(IsExpectedEntity(FD1) && FD2 && IsExpectedEntity(FD2) &&
1482 "use non-instantiated function declaration for constraints partial "
1483 "ordering");
1484 }
1485
1486 if (AC1.empty()) {
1487 Result = AC2.empty();
1488 return false;
1489 }
1490 if (AC2.empty()) {
1491 // TD1 has associated constraints and TD2 does not.
1492 Result = true;
1493 return false;
1494 }
1495
1496 std::pair<NamedDecl *, NamedDecl *> Key{D1, D2};
1497 auto CacheEntry = SubsumptionCache.find(Key);
1498 if (CacheEntry != SubsumptionCache.end()) {
1499 Result = CacheEntry->second;
1500 return false;
1501 }
1502
1503 unsigned Depth1 = CalculateTemplateDepthForConstraints(*this, D1, true);
1504 unsigned Depth2 = CalculateTemplateDepthForConstraints(*this, D2, true);
1505
1506 for (size_t I = 0; I != AC1.size() && I != AC2.size(); ++I) {
1507 if (Depth2 > Depth1) {
1508 AC1[I] = AdjustConstraintDepth(*this, Depth2 - Depth1)
1509 .TransformExpr(const_cast<Expr *>(AC1[I]))
1510 .get();
1511 } else if (Depth1 > Depth2) {
1512 AC2[I] = AdjustConstraintDepth(*this, Depth1 - Depth2)
1513 .TransformExpr(const_cast<Expr *>(AC2[I]))
1514 .get();
1515 }
1516 }
1517
1518 if (subsumes(*this, D1, AC1, D2, AC2, Result,
1519 [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
1520 return A.subsumes(Context, B);
1521 }))
1522 return true;
1523 SubsumptionCache.try_emplace(Key, Result);
1524 return false;
1525 }
1526
MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl * D1,ArrayRef<const Expr * > AC1,NamedDecl * D2,ArrayRef<const Expr * > AC2)1527 bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
1528 ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) {
1529 if (isSFINAEContext())
1530 // No need to work here because our notes would be discarded.
1531 return false;
1532
1533 if (AC1.empty() || AC2.empty())
1534 return false;
1535
1536 auto NormalExprEvaluator =
1537 [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
1538 return A.subsumes(Context, B);
1539 };
1540
1541 const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
1542 auto IdenticalExprEvaluator =
1543 [&] (const AtomicConstraint &A, const AtomicConstraint &B) {
1544 if (!A.hasMatchingParameterMapping(Context, B))
1545 return false;
1546 const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
1547 if (EA == EB)
1548 return true;
1549
1550 // Not the same source level expression - are the expressions
1551 // identical?
1552 llvm::FoldingSetNodeID IDA, IDB;
1553 EA->Profile(IDA, Context, /*Canonical=*/true);
1554 EB->Profile(IDB, Context, /*Canonical=*/true);
1555 if (IDA != IDB)
1556 return false;
1557
1558 AmbiguousAtomic1 = EA;
1559 AmbiguousAtomic2 = EB;
1560 return true;
1561 };
1562
1563 {
1564 // The subsumption checks might cause diagnostics
1565 SFINAETrap Trap(*this);
1566 auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1);
1567 if (!Normalized1)
1568 return false;
1569 const NormalForm DNF1 = makeDNF(*Normalized1);
1570 const NormalForm CNF1 = makeCNF(*Normalized1);
1571
1572 auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2);
1573 if (!Normalized2)
1574 return false;
1575 const NormalForm DNF2 = makeDNF(*Normalized2);
1576 const NormalForm CNF2 = makeCNF(*Normalized2);
1577
1578 bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator);
1579 bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator);
1580 bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator);
1581 bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator);
1582 if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
1583 Is2AtLeastAs1 == Is2AtLeastAs1Normally)
1584 // Same result - no ambiguity was caused by identical atomic expressions.
1585 return false;
1586 }
1587
1588 // A different result! Some ambiguous atomic constraint(s) caused a difference
1589 assert(AmbiguousAtomic1 && AmbiguousAtomic2);
1590
1591 Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints)
1592 << AmbiguousAtomic1->getSourceRange();
1593 Diag(AmbiguousAtomic2->getBeginLoc(),
1594 diag::note_ambiguous_atomic_constraints_similar_expression)
1595 << AmbiguousAtomic2->getSourceRange();
1596 return true;
1597 }
1598
ExprRequirement(Expr * E,bool IsSimple,SourceLocation NoexceptLoc,ReturnTypeRequirement Req,SatisfactionStatus Status,ConceptSpecializationExpr * SubstitutedConstraintExpr)1599 concepts::ExprRequirement::ExprRequirement(
1600 Expr *E, bool IsSimple, SourceLocation NoexceptLoc,
1601 ReturnTypeRequirement Req, SatisfactionStatus Status,
1602 ConceptSpecializationExpr *SubstitutedConstraintExpr) :
1603 Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent,
1604 Status == SS_Dependent &&
1605 (E->containsUnexpandedParameterPack() ||
1606 Req.containsUnexpandedParameterPack()),
1607 Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc),
1608 TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr),
1609 Status(Status) {
1610 assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1611 "Simple requirement must not have a return type requirement or a "
1612 "noexcept specification");
1613 assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) ==
1614 (SubstitutedConstraintExpr != nullptr));
1615 }
1616
ExprRequirement(SubstitutionDiagnostic * ExprSubstDiag,bool IsSimple,SourceLocation NoexceptLoc,ReturnTypeRequirement Req)1617 concepts::ExprRequirement::ExprRequirement(
1618 SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple,
1619 SourceLocation NoexceptLoc, ReturnTypeRequirement Req) :
1620 Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(),
1621 Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false),
1622 Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req),
1623 Status(SS_ExprSubstitutionFailure) {
1624 assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1625 "Simple requirement must not have a return type requirement or a "
1626 "noexcept specification");
1627 }
1628
1629 concepts::ExprRequirement::ReturnTypeRequirement::
ReturnTypeRequirement(TemplateParameterList * TPL)1630 ReturnTypeRequirement(TemplateParameterList *TPL) :
1631 TypeConstraintInfo(TPL, false) {
1632 assert(TPL->size() == 1);
1633 const TypeConstraint *TC =
1634 cast<TemplateTypeParmDecl>(TPL->getParam(0))->getTypeConstraint();
1635 assert(TC &&
1636 "TPL must have a template type parameter with a type constraint");
1637 auto *Constraint =
1638 cast<ConceptSpecializationExpr>(TC->getImmediatelyDeclaredConstraint());
1639 bool Dependent =
1640 Constraint->getTemplateArgsAsWritten() &&
1641 TemplateSpecializationType::anyInstantiationDependentTemplateArguments(
1642 Constraint->getTemplateArgsAsWritten()->arguments().drop_front(1));
1643 TypeConstraintInfo.setInt(Dependent ? true : false);
1644 }
1645
TypeRequirement(TypeSourceInfo * T)1646 concepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) :
1647 Requirement(RK_Type, T->getType()->isInstantiationDependentType(),
1648 T->getType()->containsUnexpandedParameterPack(),
1649 // We reach this ctor with either dependent types (in which
1650 // IsSatisfied doesn't matter) or with non-dependent type in
1651 // which the existence of the type indicates satisfaction.
1652 /*IsSatisfied=*/true),
1653 Value(T),
1654 Status(T->getType()->isInstantiationDependentType() ? SS_Dependent
1655 : SS_Satisfied) {}
1656