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