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