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