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