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