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