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