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 "clang/Sema/Sema.h" 15 #include "clang/Sema/SemaInternal.h" 16 #include "clang/Sema/SemaDiagnostic.h" 17 #include "clang/Sema/TemplateDeduction.h" 18 #include "clang/Sema/Template.h" 19 #include "clang/Sema/Overload.h" 20 #include "clang/Sema/Initialization.h" 21 #include "clang/Sema/SemaInternal.h" 22 #include "clang/AST/ExprConcepts.h" 23 #include "clang/AST/RecursiveASTVisitor.h" 24 #include "clang/Basic/OperatorPrecedence.h" 25 #include "llvm/ADT/DenseMap.h" 26 #include "llvm/ADT/PointerUnion.h" 27 #include "llvm/ADT/StringExtras.h" 28 29 using namespace clang; 30 using namespace sema; 31 32 namespace { 33 class LogicalBinOp { 34 OverloadedOperatorKind Op = OO_None; 35 const Expr *LHS = nullptr; 36 const Expr *RHS = nullptr; 37 38 public: 39 LogicalBinOp(const Expr *E) { 40 if (auto *BO = dyn_cast<BinaryOperator>(E)) { 41 Op = BinaryOperator::getOverloadedOperator(BO->getOpcode()); 42 LHS = BO->getLHS(); 43 RHS = BO->getRHS(); 44 } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(E)) { 45 // If OO is not || or && it might not have exactly 2 arguments. 46 if (OO->getNumArgs() == 2) { 47 Op = OO->getOperator(); 48 LHS = OO->getArg(0); 49 RHS = OO->getArg(1); 50 } 51 } 52 } 53 54 bool isAnd() const { return Op == OO_AmpAmp; } 55 bool isOr() const { return Op == OO_PipePipe; } 56 explicit operator bool() const { return isAnd() || isOr(); } 57 58 const Expr *getLHS() const { return LHS; } 59 const Expr *getRHS() const { return RHS; } 60 }; 61 } 62 63 bool Sema::CheckConstraintExpression(const Expr *ConstraintExpression, 64 Token NextToken, bool *PossibleNonPrimary, 65 bool IsTrailingRequiresClause) { 66 // C++2a [temp.constr.atomic]p1 67 // ..E shall be a constant expression of type bool. 68 69 ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts(); 70 71 if (LogicalBinOp BO = ConstraintExpression) { 72 return CheckConstraintExpression(BO.getLHS(), NextToken, 73 PossibleNonPrimary) && 74 CheckConstraintExpression(BO.getRHS(), NextToken, 75 PossibleNonPrimary); 76 } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression)) 77 return CheckConstraintExpression(C->getSubExpr(), NextToken, 78 PossibleNonPrimary); 79 80 QualType Type = ConstraintExpression->getType(); 81 82 auto CheckForNonPrimary = [&] { 83 if (PossibleNonPrimary) 84 *PossibleNonPrimary = 85 // We have the following case: 86 // template<typename> requires func(0) struct S { }; 87 // The user probably isn't aware of the parentheses required around 88 // the function call, and we're only going to parse 'func' as the 89 // primary-expression, and complain that it is of non-bool type. 90 (NextToken.is(tok::l_paren) && 91 (IsTrailingRequiresClause || 92 (Type->isDependentType() && 93 isa<UnresolvedLookupExpr>(ConstraintExpression)) || 94 Type->isFunctionType() || 95 Type->isSpecificBuiltinType(BuiltinType::Overload))) || 96 // We have the following case: 97 // template<typename T> requires size_<T> == 0 struct S { }; 98 // The user probably isn't aware of the parentheses required around 99 // the binary operator, and we're only going to parse 'func' as the 100 // first operand, and complain that it is of non-bool type. 101 getBinOpPrecedence(NextToken.getKind(), 102 /*GreaterThanIsOperator=*/true, 103 getLangOpts().CPlusPlus11) > prec::LogicalAnd; 104 }; 105 106 // An atomic constraint! 107 if (ConstraintExpression->isTypeDependent()) { 108 CheckForNonPrimary(); 109 return true; 110 } 111 112 if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) { 113 Diag(ConstraintExpression->getExprLoc(), 114 diag::err_non_bool_atomic_constraint) << Type 115 << ConstraintExpression->getSourceRange(); 116 CheckForNonPrimary(); 117 return false; 118 } 119 120 if (PossibleNonPrimary) 121 *PossibleNonPrimary = false; 122 return true; 123 } 124 125 template <typename AtomicEvaluator> 126 static bool 127 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr, 128 ConstraintSatisfaction &Satisfaction, 129 AtomicEvaluator &&Evaluator) { 130 ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts(); 131 132 if (LogicalBinOp BO = ConstraintExpr) { 133 if (calculateConstraintSatisfaction(S, BO.getLHS(), Satisfaction, 134 Evaluator)) 135 return true; 136 137 bool IsLHSSatisfied = Satisfaction.IsSatisfied; 138 139 if (BO.isOr() && IsLHSSatisfied) 140 // [temp.constr.op] p3 141 // A disjunction is a constraint taking two operands. To determine if 142 // a disjunction is satisfied, the satisfaction of the first operand 143 // is checked. If that is satisfied, the disjunction is satisfied. 144 // Otherwise, the disjunction is satisfied if and only if the second 145 // operand is satisfied. 146 return false; 147 148 if (BO.isAnd() && !IsLHSSatisfied) 149 // [temp.constr.op] p2 150 // A conjunction is a constraint taking two operands. To determine if 151 // a conjunction is satisfied, the satisfaction of the first operand 152 // is checked. If that is not satisfied, the conjunction is not 153 // satisfied. Otherwise, the conjunction is satisfied if and only if 154 // the second operand is satisfied. 155 return false; 156 157 return calculateConstraintSatisfaction( 158 S, BO.getRHS(), Satisfaction, std::forward<AtomicEvaluator>(Evaluator)); 159 } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) { 160 return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction, 161 std::forward<AtomicEvaluator>(Evaluator)); 162 } 163 164 // An atomic constraint expression 165 ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr); 166 167 if (SubstitutedAtomicExpr.isInvalid()) 168 return true; 169 170 if (!SubstitutedAtomicExpr.isUsable()) 171 // Evaluator has decided satisfaction without yielding an expression. 172 return false; 173 174 EnterExpressionEvaluationContext ConstantEvaluated( 175 S, Sema::ExpressionEvaluationContext::ConstantEvaluated); 176 SmallVector<PartialDiagnosticAt, 2> EvaluationDiags; 177 Expr::EvalResult EvalResult; 178 EvalResult.Diag = &EvaluationDiags; 179 if (!SubstitutedAtomicExpr.get()->EvaluateAsConstantExpr(EvalResult, 180 S.Context) || 181 !EvaluationDiags.empty()) { 182 // C++2a [temp.constr.atomic]p1 183 // ...E shall be a constant expression of type bool. 184 S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(), 185 diag::err_non_constant_constraint_expression) 186 << SubstitutedAtomicExpr.get()->getSourceRange(); 187 for (const PartialDiagnosticAt &PDiag : EvaluationDiags) 188 S.Diag(PDiag.first, PDiag.second); 189 return true; 190 } 191 192 assert(EvalResult.Val.isInt() && 193 "evaluating bool expression didn't produce int"); 194 Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue(); 195 if (!Satisfaction.IsSatisfied) 196 Satisfaction.Details.emplace_back(ConstraintExpr, 197 SubstitutedAtomicExpr.get()); 198 199 return false; 200 } 201 202 static bool calculateConstraintSatisfaction( 203 Sema &S, const NamedDecl *Template, ArrayRef<TemplateArgument> TemplateArgs, 204 SourceLocation TemplateNameLoc, MultiLevelTemplateArgumentList &MLTAL, 205 const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction) { 206 return calculateConstraintSatisfaction( 207 S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) { 208 EnterExpressionEvaluationContext ConstantEvaluated( 209 S, Sema::ExpressionEvaluationContext::ConstantEvaluated); 210 211 // Atomic constraint - substitute arguments and check satisfaction. 212 ExprResult SubstitutedExpression; 213 { 214 TemplateDeductionInfo Info(TemplateNameLoc); 215 Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(), 216 Sema::InstantiatingTemplate::ConstraintSubstitution{}, 217 const_cast<NamedDecl *>(Template), Info, 218 AtomicExpr->getSourceRange()); 219 if (Inst.isInvalid()) 220 return ExprError(); 221 // We do not want error diagnostics escaping here. 222 Sema::SFINAETrap Trap(S); 223 SubstitutedExpression = S.SubstExpr(const_cast<Expr *>(AtomicExpr), 224 MLTAL); 225 // Substitution might have stripped off a contextual conversion to 226 // bool if this is the operand of an '&&' or '||'. For example, we 227 // might lose an lvalue-to-rvalue conversion here. If so, put it back 228 // before we try to evaluate. 229 if (!SubstitutedExpression.isInvalid()) 230 SubstitutedExpression = 231 S.PerformContextuallyConvertToBool(SubstitutedExpression.get()); 232 if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) { 233 // C++2a [temp.constr.atomic]p1 234 // ...If substitution results in an invalid type or expression, the 235 // constraint is not satisfied. 236 if (!Trap.hasErrorOccurred()) 237 // A non-SFINAE error has occurred as a result of this 238 // substitution. 239 return ExprError(); 240 241 PartialDiagnosticAt SubstDiag{SourceLocation(), 242 PartialDiagnostic::NullDiagnostic()}; 243 Info.takeSFINAEDiagnostic(SubstDiag); 244 // FIXME: Concepts: This is an unfortunate consequence of there 245 // being no serialization code for PartialDiagnostics and the fact 246 // that serializing them would likely take a lot more storage than 247 // just storing them as strings. We would still like, in the 248 // future, to serialize the proper PartialDiagnostic as serializing 249 // it as a string defeats the purpose of the diagnostic mechanism. 250 SmallString<128> DiagString; 251 DiagString = ": "; 252 SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString); 253 unsigned MessageSize = DiagString.size(); 254 char *Mem = new (S.Context) char[MessageSize]; 255 memcpy(Mem, DiagString.c_str(), MessageSize); 256 Satisfaction.Details.emplace_back( 257 AtomicExpr, 258 new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{ 259 SubstDiag.first, StringRef(Mem, MessageSize)}); 260 Satisfaction.IsSatisfied = false; 261 return ExprEmpty(); 262 } 263 } 264 265 if (!S.CheckConstraintExpression(SubstitutedExpression.get())) 266 return ExprError(); 267 268 return SubstitutedExpression; 269 }); 270 } 271 272 static bool CheckConstraintSatisfaction(Sema &S, const NamedDecl *Template, 273 ArrayRef<const Expr *> ConstraintExprs, 274 ArrayRef<TemplateArgument> TemplateArgs, 275 SourceRange TemplateIDRange, 276 ConstraintSatisfaction &Satisfaction) { 277 if (ConstraintExprs.empty()) { 278 Satisfaction.IsSatisfied = true; 279 return false; 280 } 281 282 for (auto& Arg : TemplateArgs) 283 if (Arg.isInstantiationDependent()) { 284 // No need to check satisfaction for dependent constraint expressions. 285 Satisfaction.IsSatisfied = true; 286 return false; 287 } 288 289 Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(), 290 Sema::InstantiatingTemplate::ConstraintsCheck{}, 291 const_cast<NamedDecl *>(Template), TemplateArgs, TemplateIDRange); 292 if (Inst.isInvalid()) 293 return true; 294 295 MultiLevelTemplateArgumentList MLTAL; 296 MLTAL.addOuterTemplateArguments(TemplateArgs); 297 298 for (const Expr *ConstraintExpr : ConstraintExprs) { 299 if (calculateConstraintSatisfaction(S, Template, TemplateArgs, 300 TemplateIDRange.getBegin(), MLTAL, 301 ConstraintExpr, Satisfaction)) 302 return true; 303 if (!Satisfaction.IsSatisfied) 304 // [temp.constr.op] p2 305 // [...] To determine if a conjunction is satisfied, the satisfaction 306 // of the first operand is checked. If that is not satisfied, the 307 // conjunction is not satisfied. [...] 308 return false; 309 } 310 return false; 311 } 312 313 bool Sema::CheckConstraintSatisfaction( 314 const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs, 315 ArrayRef<TemplateArgument> TemplateArgs, SourceRange TemplateIDRange, 316 ConstraintSatisfaction &OutSatisfaction) { 317 if (ConstraintExprs.empty()) { 318 OutSatisfaction.IsSatisfied = true; 319 return false; 320 } 321 322 llvm::FoldingSetNodeID ID; 323 void *InsertPos; 324 ConstraintSatisfaction *Satisfaction = nullptr; 325 bool ShouldCache = LangOpts.ConceptSatisfactionCaching && Template; 326 if (ShouldCache) { 327 ConstraintSatisfaction::Profile(ID, Context, Template, TemplateArgs); 328 Satisfaction = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos); 329 if (Satisfaction) { 330 OutSatisfaction = *Satisfaction; 331 return false; 332 } 333 Satisfaction = new ConstraintSatisfaction(Template, TemplateArgs); 334 } else { 335 Satisfaction = &OutSatisfaction; 336 } 337 if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs, 338 TemplateArgs, TemplateIDRange, 339 *Satisfaction)) { 340 if (ShouldCache) 341 delete Satisfaction; 342 return true; 343 } 344 345 if (ShouldCache) { 346 // We cannot use InsertNode here because CheckConstraintSatisfaction might 347 // have invalidated it. 348 SatisfactionCache.InsertNode(Satisfaction); 349 OutSatisfaction = *Satisfaction; 350 } 351 return false; 352 } 353 354 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr, 355 ConstraintSatisfaction &Satisfaction) { 356 return calculateConstraintSatisfaction( 357 *this, ConstraintExpr, Satisfaction, 358 [](const Expr *AtomicExpr) -> ExprResult { 359 return ExprResult(const_cast<Expr *>(AtomicExpr)); 360 }); 361 } 362 363 bool Sema::CheckFunctionConstraints(const FunctionDecl *FD, 364 ConstraintSatisfaction &Satisfaction, 365 SourceLocation UsageLoc) { 366 const Expr *RC = FD->getTrailingRequiresClause(); 367 if (RC->isInstantiationDependent()) { 368 Satisfaction.IsSatisfied = true; 369 return false; 370 } 371 Qualifiers ThisQuals; 372 CXXRecordDecl *Record = nullptr; 373 if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) { 374 ThisQuals = Method->getMethodQualifiers(); 375 Record = const_cast<CXXRecordDecl *>(Method->getParent()); 376 } 377 CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr); 378 // We substitute with empty arguments in order to rebuild the atomic 379 // constraint in a constant-evaluated context. 380 // FIXME: Should this be a dedicated TreeTransform? 381 return CheckConstraintSatisfaction( 382 FD, {RC}, /*TemplateArgs=*/{}, 383 SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()), 384 Satisfaction); 385 } 386 387 bool Sema::EnsureTemplateArgumentListConstraints( 388 TemplateDecl *TD, ArrayRef<TemplateArgument> TemplateArgs, 389 SourceRange TemplateIDRange) { 390 ConstraintSatisfaction Satisfaction; 391 llvm::SmallVector<const Expr *, 3> AssociatedConstraints; 392 TD->getAssociatedConstraints(AssociatedConstraints); 393 if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgs, 394 TemplateIDRange, Satisfaction)) 395 return true; 396 397 if (!Satisfaction.IsSatisfied) { 398 SmallString<128> TemplateArgString; 399 TemplateArgString = " "; 400 TemplateArgString += getTemplateArgumentBindingsText( 401 TD->getTemplateParameters(), TemplateArgs.data(), TemplateArgs.size()); 402 403 Diag(TemplateIDRange.getBegin(), 404 diag::err_template_arg_list_constraints_not_satisfied) 405 << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD 406 << TemplateArgString << TemplateIDRange; 407 DiagnoseUnsatisfiedConstraint(Satisfaction); 408 return true; 409 } 410 return false; 411 } 412 413 static void diagnoseUnsatisfiedRequirement(Sema &S, 414 concepts::ExprRequirement *Req, 415 bool First) { 416 assert(!Req->isSatisfied() 417 && "Diagnose() can only be used on an unsatisfied requirement"); 418 switch (Req->getSatisfactionStatus()) { 419 case concepts::ExprRequirement::SS_Dependent: 420 llvm_unreachable("Diagnosing a dependent requirement"); 421 break; 422 case concepts::ExprRequirement::SS_ExprSubstitutionFailure: { 423 auto *SubstDiag = Req->getExprSubstitutionDiagnostic(); 424 if (!SubstDiag->DiagMessage.empty()) 425 S.Diag(SubstDiag->DiagLoc, 426 diag::note_expr_requirement_expr_substitution_error) 427 << (int)First << SubstDiag->SubstitutedEntity 428 << SubstDiag->DiagMessage; 429 else 430 S.Diag(SubstDiag->DiagLoc, 431 diag::note_expr_requirement_expr_unknown_substitution_error) 432 << (int)First << SubstDiag->SubstitutedEntity; 433 break; 434 } 435 case concepts::ExprRequirement::SS_NoexceptNotMet: 436 S.Diag(Req->getNoexceptLoc(), 437 diag::note_expr_requirement_noexcept_not_met) 438 << (int)First << Req->getExpr(); 439 break; 440 case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: { 441 auto *SubstDiag = 442 Req->getReturnTypeRequirement().getSubstitutionDiagnostic(); 443 if (!SubstDiag->DiagMessage.empty()) 444 S.Diag(SubstDiag->DiagLoc, 445 diag::note_expr_requirement_type_requirement_substitution_error) 446 << (int)First << SubstDiag->SubstitutedEntity 447 << SubstDiag->DiagMessage; 448 else 449 S.Diag(SubstDiag->DiagLoc, 450 diag::note_expr_requirement_type_requirement_unknown_substitution_error) 451 << (int)First << SubstDiag->SubstitutedEntity; 452 break; 453 } 454 case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: { 455 ConceptSpecializationExpr *ConstraintExpr = 456 Req->getReturnTypeRequirementSubstitutedConstraintExpr(); 457 if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1) { 458 // A simple case - expr type is the type being constrained and the concept 459 // was not provided arguments. 460 Expr *e = Req->getExpr(); 461 S.Diag(e->getBeginLoc(), 462 diag::note_expr_requirement_constraints_not_satisfied_simple) 463 << (int)First << S.Context.getReferenceQualifiedType(e) 464 << ConstraintExpr->getNamedConcept(); 465 } else { 466 S.Diag(ConstraintExpr->getBeginLoc(), 467 diag::note_expr_requirement_constraints_not_satisfied) 468 << (int)First << ConstraintExpr; 469 } 470 S.DiagnoseUnsatisfiedConstraint(ConstraintExpr->getSatisfaction()); 471 break; 472 } 473 case concepts::ExprRequirement::SS_Satisfied: 474 llvm_unreachable("We checked this above"); 475 } 476 } 477 478 static void diagnoseUnsatisfiedRequirement(Sema &S, 479 concepts::TypeRequirement *Req, 480 bool First) { 481 assert(!Req->isSatisfied() 482 && "Diagnose() can only be used on an unsatisfied requirement"); 483 switch (Req->getSatisfactionStatus()) { 484 case concepts::TypeRequirement::SS_Dependent: 485 llvm_unreachable("Diagnosing a dependent requirement"); 486 return; 487 case concepts::TypeRequirement::SS_SubstitutionFailure: { 488 auto *SubstDiag = Req->getSubstitutionDiagnostic(); 489 if (!SubstDiag->DiagMessage.empty()) 490 S.Diag(SubstDiag->DiagLoc, 491 diag::note_type_requirement_substitution_error) << (int)First 492 << SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage; 493 else 494 S.Diag(SubstDiag->DiagLoc, 495 diag::note_type_requirement_unknown_substitution_error) 496 << (int)First << SubstDiag->SubstitutedEntity; 497 return; 498 } 499 default: 500 llvm_unreachable("Unknown satisfaction status"); 501 return; 502 } 503 } 504 505 static void diagnoseUnsatisfiedRequirement(Sema &S, 506 concepts::NestedRequirement *Req, 507 bool First) { 508 if (Req->isSubstitutionFailure()) { 509 concepts::Requirement::SubstitutionDiagnostic *SubstDiag = 510 Req->getSubstitutionDiagnostic(); 511 if (!SubstDiag->DiagMessage.empty()) 512 S.Diag(SubstDiag->DiagLoc, 513 diag::note_nested_requirement_substitution_error) 514 << (int)First << SubstDiag->SubstitutedEntity 515 << SubstDiag->DiagMessage; 516 else 517 S.Diag(SubstDiag->DiagLoc, 518 diag::note_nested_requirement_unknown_substitution_error) 519 << (int)First << SubstDiag->SubstitutedEntity; 520 return; 521 } 522 S.DiagnoseUnsatisfiedConstraint(Req->getConstraintSatisfaction(), First); 523 } 524 525 526 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S, 527 Expr *SubstExpr, 528 bool First = true) { 529 SubstExpr = SubstExpr->IgnoreParenImpCasts(); 530 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) { 531 switch (BO->getOpcode()) { 532 // These two cases will in practice only be reached when using fold 533 // expressions with || and &&, since otherwise the || and && will have been 534 // broken down into atomic constraints during satisfaction checking. 535 case BO_LOr: 536 // Or evaluated to false - meaning both RHS and LHS evaluated to false. 537 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First); 538 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), 539 /*First=*/false); 540 return; 541 case BO_LAnd: { 542 bool LHSSatisfied = 543 BO->getLHS()->EvaluateKnownConstInt(S.Context).getBoolValue(); 544 if (LHSSatisfied) { 545 // LHS is true, so RHS must be false. 546 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First); 547 return; 548 } 549 // LHS is false 550 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First); 551 552 // RHS might also be false 553 bool RHSSatisfied = 554 BO->getRHS()->EvaluateKnownConstInt(S.Context).getBoolValue(); 555 if (!RHSSatisfied) 556 diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), 557 /*First=*/false); 558 return; 559 } 560 case BO_GE: 561 case BO_LE: 562 case BO_GT: 563 case BO_LT: 564 case BO_EQ: 565 case BO_NE: 566 if (BO->getLHS()->getType()->isIntegerType() && 567 BO->getRHS()->getType()->isIntegerType()) { 568 Expr::EvalResult SimplifiedLHS; 569 Expr::EvalResult SimplifiedRHS; 570 BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context, 571 Expr::SE_NoSideEffects, 572 /*InConstantContext=*/true); 573 BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context, 574 Expr::SE_NoSideEffects, 575 /*InConstantContext=*/true); 576 if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) { 577 S.Diag(SubstExpr->getBeginLoc(), 578 diag::note_atomic_constraint_evaluated_to_false_elaborated) 579 << (int)First << SubstExpr 580 << toString(SimplifiedLHS.Val.getInt(), 10) 581 << BinaryOperator::getOpcodeStr(BO->getOpcode()) 582 << toString(SimplifiedRHS.Val.getInt(), 10); 583 return; 584 } 585 } 586 break; 587 588 default: 589 break; 590 } 591 } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) { 592 if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) { 593 S.Diag( 594 CSE->getSourceRange().getBegin(), 595 diag:: 596 note_single_arg_concept_specialization_constraint_evaluated_to_false) 597 << (int)First 598 << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument() 599 << CSE->getNamedConcept(); 600 } else { 601 S.Diag(SubstExpr->getSourceRange().getBegin(), 602 diag::note_concept_specialization_constraint_evaluated_to_false) 603 << (int)First << CSE; 604 } 605 S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction()); 606 return; 607 } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) { 608 for (concepts::Requirement *Req : RE->getRequirements()) 609 if (!Req->isDependent() && !Req->isSatisfied()) { 610 if (auto *E = dyn_cast<concepts::ExprRequirement>(Req)) 611 diagnoseUnsatisfiedRequirement(S, E, First); 612 else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req)) 613 diagnoseUnsatisfiedRequirement(S, T, First); 614 else 615 diagnoseUnsatisfiedRequirement( 616 S, cast<concepts::NestedRequirement>(Req), First); 617 break; 618 } 619 return; 620 } 621 622 S.Diag(SubstExpr->getSourceRange().getBegin(), 623 diag::note_atomic_constraint_evaluated_to_false) 624 << (int)First << SubstExpr; 625 } 626 627 template<typename SubstitutionDiagnostic> 628 static void diagnoseUnsatisfiedConstraintExpr( 629 Sema &S, const Expr *E, 630 const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record, 631 bool First = true) { 632 if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){ 633 S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed) 634 << Diag->second; 635 return; 636 } 637 638 diagnoseWellFormedUnsatisfiedConstraintExpr(S, 639 Record.template get<Expr *>(), First); 640 } 641 642 void 643 Sema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction, 644 bool First) { 645 assert(!Satisfaction.IsSatisfied && 646 "Attempted to diagnose a satisfied constraint"); 647 for (auto &Pair : Satisfaction.Details) { 648 diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First); 649 First = false; 650 } 651 } 652 653 void Sema::DiagnoseUnsatisfiedConstraint( 654 const ASTConstraintSatisfaction &Satisfaction, 655 bool First) { 656 assert(!Satisfaction.IsSatisfied && 657 "Attempted to diagnose a satisfied constraint"); 658 for (auto &Pair : Satisfaction) { 659 diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First); 660 First = false; 661 } 662 } 663 664 const NormalizedConstraint * 665 Sema::getNormalizedAssociatedConstraints( 666 NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) { 667 auto CacheEntry = NormalizationCache.find(ConstrainedDecl); 668 if (CacheEntry == NormalizationCache.end()) { 669 auto Normalized = 670 NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl, 671 AssociatedConstraints); 672 CacheEntry = 673 NormalizationCache 674 .try_emplace(ConstrainedDecl, 675 Normalized 676 ? new (Context) NormalizedConstraint( 677 std::move(*Normalized)) 678 : nullptr) 679 .first; 680 } 681 return CacheEntry->second; 682 } 683 684 static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N, 685 ConceptDecl *Concept, ArrayRef<TemplateArgument> TemplateArgs, 686 const ASTTemplateArgumentListInfo *ArgsAsWritten) { 687 if (!N.isAtomic()) { 688 if (substituteParameterMappings(S, N.getLHS(), Concept, TemplateArgs, 689 ArgsAsWritten)) 690 return true; 691 return substituteParameterMappings(S, N.getRHS(), Concept, TemplateArgs, 692 ArgsAsWritten); 693 } 694 TemplateParameterList *TemplateParams = Concept->getTemplateParameters(); 695 696 AtomicConstraint &Atomic = *N.getAtomicConstraint(); 697 TemplateArgumentListInfo SubstArgs; 698 MultiLevelTemplateArgumentList MLTAL; 699 MLTAL.addOuterTemplateArguments(TemplateArgs); 700 if (!Atomic.ParameterMapping) { 701 llvm::SmallBitVector OccurringIndices(TemplateParams->size()); 702 S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false, 703 /*Depth=*/0, OccurringIndices); 704 Atomic.ParameterMapping.emplace( 705 MutableArrayRef<TemplateArgumentLoc>( 706 new (S.Context) TemplateArgumentLoc[OccurringIndices.count()], 707 OccurringIndices.count())); 708 for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I) 709 if (OccurringIndices[I]) 710 new (&(*Atomic.ParameterMapping)[J++]) TemplateArgumentLoc( 711 S.getIdentityTemplateArgumentLoc(TemplateParams->begin()[I], 712 // Here we assume we do not support things like 713 // template<typename A, typename B> 714 // concept C = ...; 715 // 716 // template<typename... Ts> requires C<Ts...> 717 // struct S { }; 718 // The above currently yields a diagnostic. 719 // We still might have default arguments for concept parameters. 720 ArgsAsWritten->NumTemplateArgs > I ? 721 ArgsAsWritten->arguments()[I].getLocation() : 722 SourceLocation())); 723 } 724 Sema::InstantiatingTemplate Inst( 725 S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(), 726 Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept, 727 SourceRange(ArgsAsWritten->arguments()[0].getSourceRange().getBegin(), 728 ArgsAsWritten->arguments().back().getSourceRange().getEnd())); 729 if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs)) 730 return true; 731 Atomic.ParameterMapping.emplace( 732 MutableArrayRef<TemplateArgumentLoc>( 733 new (S.Context) TemplateArgumentLoc[SubstArgs.size()], 734 SubstArgs.size())); 735 std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(), 736 N.getAtomicConstraint()->ParameterMapping->begin()); 737 return false; 738 } 739 740 Optional<NormalizedConstraint> 741 NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D, 742 ArrayRef<const Expr *> E) { 743 assert(E.size() != 0); 744 auto Conjunction = fromConstraintExpr(S, D, E[0]); 745 if (!Conjunction) 746 return None; 747 for (unsigned I = 1; I < E.size(); ++I) { 748 auto Next = fromConstraintExpr(S, D, E[I]); 749 if (!Next) 750 return None; 751 *Conjunction = NormalizedConstraint(S.Context, std::move(*Conjunction), 752 std::move(*Next), CCK_Conjunction); 753 } 754 return Conjunction; 755 } 756 757 llvm::Optional<NormalizedConstraint> 758 NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) { 759 assert(E != nullptr); 760 761 // C++ [temp.constr.normal]p1.1 762 // [...] 763 // - The normal form of an expression (E) is the normal form of E. 764 // [...] 765 E = E->IgnoreParenImpCasts(); 766 if (LogicalBinOp BO = E) { 767 auto LHS = fromConstraintExpr(S, D, BO.getLHS()); 768 if (!LHS) 769 return None; 770 auto RHS = fromConstraintExpr(S, D, BO.getRHS()); 771 if (!RHS) 772 return None; 773 774 return NormalizedConstraint(S.Context, std::move(*LHS), std::move(*RHS), 775 BO.isAnd() ? CCK_Conjunction : CCK_Disjunction); 776 } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) { 777 const NormalizedConstraint *SubNF; 778 { 779 Sema::InstantiatingTemplate Inst( 780 S, CSE->getExprLoc(), 781 Sema::InstantiatingTemplate::ConstraintNormalization{}, D, 782 CSE->getSourceRange()); 783 // C++ [temp.constr.normal]p1.1 784 // [...] 785 // The normal form of an id-expression of the form C<A1, A2, ..., AN>, 786 // where C names a concept, is the normal form of the 787 // constraint-expression of C, after substituting A1, A2, ..., AN for C’s 788 // respective template parameters in the parameter mappings in each atomic 789 // constraint. If any such substitution results in an invalid type or 790 // expression, the program is ill-formed; no diagnostic is required. 791 // [...] 792 ConceptDecl *CD = CSE->getNamedConcept(); 793 SubNF = S.getNormalizedAssociatedConstraints(CD, 794 {CD->getConstraintExpr()}); 795 if (!SubNF) 796 return None; 797 } 798 799 Optional<NormalizedConstraint> New; 800 New.emplace(S.Context, *SubNF); 801 802 if (substituteParameterMappings( 803 S, *New, CSE->getNamedConcept(), 804 CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten())) 805 return None; 806 807 return New; 808 } 809 return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)}; 810 } 811 812 using NormalForm = 813 llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>; 814 815 static NormalForm makeCNF(const NormalizedConstraint &Normalized) { 816 if (Normalized.isAtomic()) 817 return {{Normalized.getAtomicConstraint()}}; 818 819 NormalForm LCNF = makeCNF(Normalized.getLHS()); 820 NormalForm RCNF = makeCNF(Normalized.getRHS()); 821 if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) { 822 LCNF.reserve(LCNF.size() + RCNF.size()); 823 while (!RCNF.empty()) 824 LCNF.push_back(RCNF.pop_back_val()); 825 return LCNF; 826 } 827 828 // Disjunction 829 NormalForm Res; 830 Res.reserve(LCNF.size() * RCNF.size()); 831 for (auto &LDisjunction : LCNF) 832 for (auto &RDisjunction : RCNF) { 833 NormalForm::value_type Combined; 834 Combined.reserve(LDisjunction.size() + RDisjunction.size()); 835 std::copy(LDisjunction.begin(), LDisjunction.end(), 836 std::back_inserter(Combined)); 837 std::copy(RDisjunction.begin(), RDisjunction.end(), 838 std::back_inserter(Combined)); 839 Res.emplace_back(Combined); 840 } 841 return Res; 842 } 843 844 static NormalForm makeDNF(const NormalizedConstraint &Normalized) { 845 if (Normalized.isAtomic()) 846 return {{Normalized.getAtomicConstraint()}}; 847 848 NormalForm LDNF = makeDNF(Normalized.getLHS()); 849 NormalForm RDNF = makeDNF(Normalized.getRHS()); 850 if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) { 851 LDNF.reserve(LDNF.size() + RDNF.size()); 852 while (!RDNF.empty()) 853 LDNF.push_back(RDNF.pop_back_val()); 854 return LDNF; 855 } 856 857 // Conjunction 858 NormalForm Res; 859 Res.reserve(LDNF.size() * RDNF.size()); 860 for (auto &LConjunction : LDNF) { 861 for (auto &RConjunction : RDNF) { 862 NormalForm::value_type Combined; 863 Combined.reserve(LConjunction.size() + RConjunction.size()); 864 std::copy(LConjunction.begin(), LConjunction.end(), 865 std::back_inserter(Combined)); 866 std::copy(RConjunction.begin(), RConjunction.end(), 867 std::back_inserter(Combined)); 868 Res.emplace_back(Combined); 869 } 870 } 871 return Res; 872 } 873 874 template<typename AtomicSubsumptionEvaluator> 875 static bool subsumes(NormalForm PDNF, NormalForm QCNF, 876 AtomicSubsumptionEvaluator E) { 877 // C++ [temp.constr.order] p2 878 // Then, P subsumes Q if and only if, for every disjunctive clause Pi in the 879 // disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in 880 // the conjuctive normal form of Q, where [...] 881 for (const auto &Pi : PDNF) { 882 for (const auto &Qj : QCNF) { 883 // C++ [temp.constr.order] p2 884 // - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if 885 // and only if there exists an atomic constraint Pia in Pi for which 886 // there exists an atomic constraint, Qjb, in Qj such that Pia 887 // subsumes Qjb. 888 bool Found = false; 889 for (const AtomicConstraint *Pia : Pi) { 890 for (const AtomicConstraint *Qjb : Qj) { 891 if (E(*Pia, *Qjb)) { 892 Found = true; 893 break; 894 } 895 } 896 if (Found) 897 break; 898 } 899 if (!Found) 900 return false; 901 } 902 } 903 return true; 904 } 905 906 template<typename AtomicSubsumptionEvaluator> 907 static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P, 908 NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes, 909 AtomicSubsumptionEvaluator E) { 910 // C++ [temp.constr.order] p2 911 // In order to determine if a constraint P subsumes a constraint Q, P is 912 // transformed into disjunctive normal form, and Q is transformed into 913 // conjunctive normal form. [...] 914 auto *PNormalized = S.getNormalizedAssociatedConstraints(DP, P); 915 if (!PNormalized) 916 return true; 917 const NormalForm PDNF = makeDNF(*PNormalized); 918 919 auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q); 920 if (!QNormalized) 921 return true; 922 const NormalForm QCNF = makeCNF(*QNormalized); 923 924 Subsumes = subsumes(PDNF, QCNF, E); 925 return false; 926 } 927 928 bool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef<const Expr *> AC1, 929 NamedDecl *D2, ArrayRef<const Expr *> AC2, 930 bool &Result) { 931 if (AC1.empty()) { 932 Result = AC2.empty(); 933 return false; 934 } 935 if (AC2.empty()) { 936 // TD1 has associated constraints and TD2 does not. 937 Result = true; 938 return false; 939 } 940 941 std::pair<NamedDecl *, NamedDecl *> Key{D1, D2}; 942 auto CacheEntry = SubsumptionCache.find(Key); 943 if (CacheEntry != SubsumptionCache.end()) { 944 Result = CacheEntry->second; 945 return false; 946 } 947 948 if (subsumes(*this, D1, AC1, D2, AC2, Result, 949 [this] (const AtomicConstraint &A, const AtomicConstraint &B) { 950 return A.subsumes(Context, B); 951 })) 952 return true; 953 SubsumptionCache.try_emplace(Key, Result); 954 return false; 955 } 956 957 bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1, 958 ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) { 959 if (isSFINAEContext()) 960 // No need to work here because our notes would be discarded. 961 return false; 962 963 if (AC1.empty() || AC2.empty()) 964 return false; 965 966 auto NormalExprEvaluator = 967 [this] (const AtomicConstraint &A, const AtomicConstraint &B) { 968 return A.subsumes(Context, B); 969 }; 970 971 const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr; 972 auto IdenticalExprEvaluator = 973 [&] (const AtomicConstraint &A, const AtomicConstraint &B) { 974 if (!A.hasMatchingParameterMapping(Context, B)) 975 return false; 976 const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr; 977 if (EA == EB) 978 return true; 979 980 // Not the same source level expression - are the expressions 981 // identical? 982 llvm::FoldingSetNodeID IDA, IDB; 983 EA->Profile(IDA, Context, /*Canonical=*/true); 984 EB->Profile(IDB, Context, /*Canonical=*/true); 985 if (IDA != IDB) 986 return false; 987 988 AmbiguousAtomic1 = EA; 989 AmbiguousAtomic2 = EB; 990 return true; 991 }; 992 993 { 994 // The subsumption checks might cause diagnostics 995 SFINAETrap Trap(*this); 996 auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1); 997 if (!Normalized1) 998 return false; 999 const NormalForm DNF1 = makeDNF(*Normalized1); 1000 const NormalForm CNF1 = makeCNF(*Normalized1); 1001 1002 auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2); 1003 if (!Normalized2) 1004 return false; 1005 const NormalForm DNF2 = makeDNF(*Normalized2); 1006 const NormalForm CNF2 = makeCNF(*Normalized2); 1007 1008 bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator); 1009 bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator); 1010 bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator); 1011 bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator); 1012 if (Is1AtLeastAs2 == Is1AtLeastAs2Normally && 1013 Is2AtLeastAs1 == Is2AtLeastAs1Normally) 1014 // Same result - no ambiguity was caused by identical atomic expressions. 1015 return false; 1016 } 1017 1018 // A different result! Some ambiguous atomic constraint(s) caused a difference 1019 assert(AmbiguousAtomic1 && AmbiguousAtomic2); 1020 1021 Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints) 1022 << AmbiguousAtomic1->getSourceRange(); 1023 Diag(AmbiguousAtomic2->getBeginLoc(), 1024 diag::note_ambiguous_atomic_constraints_similar_expression) 1025 << AmbiguousAtomic2->getSourceRange(); 1026 return true; 1027 } 1028 1029 concepts::ExprRequirement::ExprRequirement( 1030 Expr *E, bool IsSimple, SourceLocation NoexceptLoc, 1031 ReturnTypeRequirement Req, SatisfactionStatus Status, 1032 ConceptSpecializationExpr *SubstitutedConstraintExpr) : 1033 Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent, 1034 Status == SS_Dependent && 1035 (E->containsUnexpandedParameterPack() || 1036 Req.containsUnexpandedParameterPack()), 1037 Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc), 1038 TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr), 1039 Status(Status) { 1040 assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) && 1041 "Simple requirement must not have a return type requirement or a " 1042 "noexcept specification"); 1043 assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) == 1044 (SubstitutedConstraintExpr != nullptr)); 1045 } 1046 1047 concepts::ExprRequirement::ExprRequirement( 1048 SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple, 1049 SourceLocation NoexceptLoc, ReturnTypeRequirement Req) : 1050 Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(), 1051 Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false), 1052 Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req), 1053 Status(SS_ExprSubstitutionFailure) { 1054 assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) && 1055 "Simple requirement must not have a return type requirement or a " 1056 "noexcept specification"); 1057 } 1058 1059 concepts::ExprRequirement::ReturnTypeRequirement:: 1060 ReturnTypeRequirement(TemplateParameterList *TPL) : 1061 TypeConstraintInfo(TPL, 0) { 1062 assert(TPL->size() == 1); 1063 const TypeConstraint *TC = 1064 cast<TemplateTypeParmDecl>(TPL->getParam(0))->getTypeConstraint(); 1065 assert(TC && 1066 "TPL must have a template type parameter with a type constraint"); 1067 auto *Constraint = 1068 cast<ConceptSpecializationExpr>(TC->getImmediatelyDeclaredConstraint()); 1069 bool Dependent = 1070 Constraint->getTemplateArgsAsWritten() && 1071 TemplateSpecializationType::anyInstantiationDependentTemplateArguments( 1072 Constraint->getTemplateArgsAsWritten()->arguments().drop_front(1)); 1073 TypeConstraintInfo.setInt(Dependent ? 1 : 0); 1074 } 1075 1076 concepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) : 1077 Requirement(RK_Type, T->getType()->isInstantiationDependentType(), 1078 T->getType()->containsUnexpandedParameterPack(), 1079 // We reach this ctor with either dependent types (in which 1080 // IsSatisfied doesn't matter) or with non-dependent type in 1081 // which the existence of the type indicates satisfaction. 1082 /*IsSatisfied=*/true), 1083 Value(T), 1084 Status(T->getType()->isInstantiationDependentType() ? SS_Dependent 1085 : SS_Satisfied) {} 1086