1353942Sdim//===-- SemaConcept.cpp - Semantic Analysis for Constraints and Concepts --===// 2353942Sdim// 3353942Sdim// The LLVM Compiler Infrastructure 4353942Sdim// 5353942Sdim// This file is distributed under the University of Illinois Open Source 6353942Sdim// License. See LICENSE.TXT for details. 7353942Sdim// 8353942Sdim//===----------------------------------------------------------------------===// 9353942Sdim// 10353942Sdim// This file implements semantic analysis for C++ constraints and concepts. 11353942Sdim// 12353942Sdim//===----------------------------------------------------------------------===// 13353942Sdim 14357095Sdim#include "clang/Sema/SemaConcept.h" 15353942Sdim#include "clang/Sema/Sema.h" 16357095Sdim#include "clang/Sema/SemaInternal.h" 17353942Sdim#include "clang/Sema/SemaDiagnostic.h" 18353942Sdim#include "clang/Sema/TemplateDeduction.h" 19353942Sdim#include "clang/Sema/Template.h" 20357099Sdim#include "clang/Sema/Overload.h" 21357099Sdim#include "clang/Sema/Initialization.h" 22357099Sdim#include "clang/Sema/SemaInternal.h" 23357099Sdim#include "clang/AST/ExprConcepts.h" 24357095Sdim#include "clang/AST/RecursiveASTVisitor.h" 25357095Sdim#include "clang/Basic/OperatorPrecedence.h" 26357095Sdim#include "llvm/ADT/DenseMap.h" 27357095Sdim#include "llvm/ADT/PointerUnion.h" 28353942Sdimusing namespace clang; 29353942Sdimusing namespace sema; 30353942Sdim 31357095Sdimbool 32357095SdimSema::CheckConstraintExpression(Expr *ConstraintExpression, Token NextToken, 33357095Sdim bool *PossibleNonPrimary, 34357095Sdim bool IsTrailingRequiresClause) { 35353942Sdim // C++2a [temp.constr.atomic]p1 36353942Sdim // ..E shall be a constant expression of type bool. 37353942Sdim 38353942Sdim ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts(); 39353942Sdim 40353942Sdim if (auto *BinOp = dyn_cast<BinaryOperator>(ConstraintExpression)) { 41353942Sdim if (BinOp->getOpcode() == BO_LAnd || BinOp->getOpcode() == BO_LOr) 42357095Sdim return CheckConstraintExpression(BinOp->getLHS(), NextToken, 43357095Sdim PossibleNonPrimary) && 44357095Sdim CheckConstraintExpression(BinOp->getRHS(), NextToken, 45357095Sdim PossibleNonPrimary); 46353942Sdim } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression)) 47357095Sdim return CheckConstraintExpression(C->getSubExpr(), NextToken, 48357095Sdim PossibleNonPrimary); 49353942Sdim 50357095Sdim QualType Type = ConstraintExpression->getType(); 51357095Sdim 52357095Sdim auto CheckForNonPrimary = [&] { 53357095Sdim if (PossibleNonPrimary) 54357095Sdim *PossibleNonPrimary = 55357095Sdim // We have the following case: 56357095Sdim // template<typename> requires func(0) struct S { }; 57357095Sdim // The user probably isn't aware of the parentheses required around 58357095Sdim // the function call, and we're only going to parse 'func' as the 59357095Sdim // primary-expression, and complain that it is of non-bool type. 60357095Sdim (NextToken.is(tok::l_paren) && 61357095Sdim (IsTrailingRequiresClause || 62357095Sdim (Type->isDependentType() && 63357095Sdim IsDependentFunctionNameExpr(ConstraintExpression)) || 64357095Sdim Type->isFunctionType() || 65357095Sdim Type->isSpecificBuiltinType(BuiltinType::Overload))) || 66357095Sdim // We have the following case: 67357095Sdim // template<typename T> requires size_<T> == 0 struct S { }; 68357095Sdim // The user probably isn't aware of the parentheses required around 69357095Sdim // the binary operator, and we're only going to parse 'func' as the 70357095Sdim // first operand, and complain that it is of non-bool type. 71357095Sdim getBinOpPrecedence(NextToken.getKind(), 72357095Sdim /*GreaterThanIsOperator=*/true, 73357095Sdim getLangOpts().CPlusPlus11) > prec::LogicalAnd; 74357095Sdim }; 75357095Sdim 76353942Sdim // An atomic constraint! 77357095Sdim if (ConstraintExpression->isTypeDependent()) { 78357095Sdim CheckForNonPrimary(); 79353942Sdim return true; 80357095Sdim } 81353942Sdim 82353942Sdim if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) { 83353942Sdim Diag(ConstraintExpression->getExprLoc(), 84353942Sdim diag::err_non_bool_atomic_constraint) << Type 85353942Sdim << ConstraintExpression->getSourceRange(); 86357095Sdim CheckForNonPrimary(); 87353942Sdim return false; 88353942Sdim } 89357095Sdim 90357095Sdim if (PossibleNonPrimary) 91357095Sdim *PossibleNonPrimary = false; 92353942Sdim return true; 93353942Sdim} 94353942Sdim 95357095Sdimtemplate <typename AtomicEvaluator> 96357095Sdimstatic bool 97357095SdimcalculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr, 98357095Sdim ConstraintSatisfaction &Satisfaction, 99357095Sdim AtomicEvaluator &&Evaluator) { 100353942Sdim ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts(); 101353942Sdim 102353942Sdim if (auto *BO = dyn_cast<BinaryOperator>(ConstraintExpr)) { 103357095Sdim if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) { 104357095Sdim if (calculateConstraintSatisfaction(S, BO->getLHS(), Satisfaction, 105357095Sdim Evaluator)) 106353942Sdim return true; 107357095Sdim 108357095Sdim bool IsLHSSatisfied = Satisfaction.IsSatisfied; 109357095Sdim 110357095Sdim if (BO->getOpcode() == BO_LOr && IsLHSSatisfied) 111357095Sdim // [temp.constr.op] p3 112357095Sdim // A disjunction is a constraint taking two operands. To determine if 113357095Sdim // a disjunction is satisfied, the satisfaction of the first operand 114357095Sdim // is checked. If that is satisfied, the disjunction is satisfied. 115357095Sdim // Otherwise, the disjunction is satisfied if and only if the second 116357095Sdim // operand is satisfied. 117353942Sdim return false; 118357095Sdim 119357095Sdim if (BO->getOpcode() == BO_LAnd && !IsLHSSatisfied) 120357095Sdim // [temp.constr.op] p2 121357095Sdim // A conjunction is a constraint taking two operands. To determine if 122357095Sdim // a conjunction is satisfied, the satisfaction of the first operand 123357095Sdim // is checked. If that is not satisfied, the conjunction is not 124357095Sdim // satisfied. Otherwise, the conjunction is satisfied if and only if 125357095Sdim // the second operand is satisfied. 126353942Sdim return false; 127357095Sdim 128357095Sdim return calculateConstraintSatisfaction(S, BO->getRHS(), Satisfaction, 129357095Sdim std::forward<AtomicEvaluator>(Evaluator)); 130353942Sdim } 131353942Sdim } 132353942Sdim else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) 133357095Sdim return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction, 134357095Sdim std::forward<AtomicEvaluator>(Evaluator)); 135353942Sdim 136357095Sdim // An atomic constraint expression 137357095Sdim ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr); 138357095Sdim 139357095Sdim if (SubstitutedAtomicExpr.isInvalid()) 140357095Sdim return true; 141357095Sdim 142357095Sdim if (!SubstitutedAtomicExpr.isUsable()) 143357095Sdim // Evaluator has decided satisfaction without yielding an expression. 144357095Sdim return false; 145357095Sdim 146353942Sdim EnterExpressionEvaluationContext ConstantEvaluated( 147357095Sdim S, Sema::ExpressionEvaluationContext::ConstantEvaluated); 148357095Sdim SmallVector<PartialDiagnosticAt, 2> EvaluationDiags; 149357095Sdim Expr::EvalResult EvalResult; 150357095Sdim EvalResult.Diag = &EvaluationDiags; 151357095Sdim if (!SubstitutedAtomicExpr.get()->EvaluateAsRValue(EvalResult, S.Context)) { 152357095Sdim // C++2a [temp.constr.atomic]p1 153357095Sdim // ...E shall be a constant expression of type bool. 154357095Sdim S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(), 155357095Sdim diag::err_non_constant_constraint_expression) 156357095Sdim << SubstitutedAtomicExpr.get()->getSourceRange(); 157357095Sdim for (const PartialDiagnosticAt &PDiag : EvaluationDiags) 158357095Sdim S.Diag(PDiag.first, PDiag.second); 159357095Sdim return true; 160357095Sdim } 161353942Sdim 162357095Sdim Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue(); 163357095Sdim if (!Satisfaction.IsSatisfied) 164357095Sdim Satisfaction.Details.emplace_back(ConstraintExpr, 165357095Sdim SubstitutedAtomicExpr.get()); 166353942Sdim 167357095Sdim return false; 168357095Sdim} 169357095Sdim 170357095Sdimstatic bool calculateConstraintSatisfaction( 171357964Sdim Sema &S, const NamedDecl *Template, ArrayRef<TemplateArgument> TemplateArgs, 172357095Sdim SourceLocation TemplateNameLoc, MultiLevelTemplateArgumentList &MLTAL, 173357095Sdim const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction) { 174357095Sdim return calculateConstraintSatisfaction( 175357095Sdim S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) { 176357095Sdim EnterExpressionEvaluationContext ConstantEvaluated( 177357095Sdim S, Sema::ExpressionEvaluationContext::ConstantEvaluated); 178357095Sdim 179357095Sdim // Atomic constraint - substitute arguments and check satisfaction. 180357095Sdim ExprResult SubstitutedExpression; 181357095Sdim { 182357095Sdim TemplateDeductionInfo Info(TemplateNameLoc); 183357095Sdim Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(), 184357964Sdim Sema::InstantiatingTemplate::ConstraintSubstitution{}, 185357964Sdim const_cast<NamedDecl *>(Template), Info, 186357964Sdim AtomicExpr->getSourceRange()); 187357095Sdim if (Inst.isInvalid()) 188357095Sdim return ExprError(); 189357095Sdim // We do not want error diagnostics escaping here. 190357095Sdim Sema::SFINAETrap Trap(S); 191357095Sdim SubstitutedExpression = S.SubstExpr(const_cast<Expr *>(AtomicExpr), 192357095Sdim MLTAL); 193357095Sdim if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) { 194357095Sdim // C++2a [temp.constr.atomic]p1 195357095Sdim // ...If substitution results in an invalid type or expression, the 196357095Sdim // constraint is not satisfied. 197357095Sdim if (!Trap.hasErrorOccurred()) 198357095Sdim // A non-SFINAE error has occured as a result of this 199357095Sdim // substitution. 200357095Sdim return ExprError(); 201357095Sdim 202357095Sdim PartialDiagnosticAt SubstDiag{SourceLocation(), 203357095Sdim PartialDiagnostic::NullDiagnostic()}; 204357095Sdim Info.takeSFINAEDiagnostic(SubstDiag); 205357095Sdim // FIXME: Concepts: This is an unfortunate consequence of there 206357095Sdim // being no serialization code for PartialDiagnostics and the fact 207357095Sdim // that serializing them would likely take a lot more storage than 208357095Sdim // just storing them as strings. We would still like, in the 209357095Sdim // future, to serialize the proper PartialDiagnostic as serializing 210357095Sdim // it as a string defeats the purpose of the diagnostic mechanism. 211357095Sdim SmallString<128> DiagString; 212357095Sdim DiagString = ": "; 213357095Sdim SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString); 214357095Sdim unsigned MessageSize = DiagString.size(); 215357095Sdim char *Mem = new (S.Context) char[MessageSize]; 216357095Sdim memcpy(Mem, DiagString.c_str(), MessageSize); 217357095Sdim Satisfaction.Details.emplace_back( 218357095Sdim AtomicExpr, 219357095Sdim new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{ 220357095Sdim SubstDiag.first, StringRef(Mem, MessageSize)}); 221357095Sdim Satisfaction.IsSatisfied = false; 222357095Sdim return ExprEmpty(); 223357095Sdim } 224357095Sdim } 225357095Sdim 226357095Sdim if (!S.CheckConstraintExpression(SubstitutedExpression.get())) 227357095Sdim return ExprError(); 228357095Sdim 229357095Sdim return SubstitutedExpression; 230357095Sdim }); 231357095Sdim} 232357095Sdim 233357964Sdimstatic bool CheckConstraintSatisfaction(Sema &S, const NamedDecl *Template, 234357095Sdim ArrayRef<const Expr *> ConstraintExprs, 235357095Sdim ArrayRef<TemplateArgument> TemplateArgs, 236357095Sdim SourceRange TemplateIDRange, 237357095Sdim ConstraintSatisfaction &Satisfaction) { 238357095Sdim if (ConstraintExprs.empty()) { 239357095Sdim Satisfaction.IsSatisfied = true; 240357095Sdim return false; 241357095Sdim } 242357095Sdim 243357095Sdim for (auto& Arg : TemplateArgs) 244357095Sdim if (Arg.isInstantiationDependent()) { 245357095Sdim // No need to check satisfaction for dependent constraint expressions. 246357095Sdim Satisfaction.IsSatisfied = true; 247353942Sdim return false; 248353942Sdim } 249357095Sdim 250357095Sdim Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(), 251357964Sdim Sema::InstantiatingTemplate::ConstraintsCheck{}, 252357964Sdim const_cast<NamedDecl *>(Template), TemplateArgs, TemplateIDRange); 253357095Sdim if (Inst.isInvalid()) 254357095Sdim return true; 255357095Sdim 256357095Sdim MultiLevelTemplateArgumentList MLTAL; 257357095Sdim MLTAL.addOuterTemplateArguments(TemplateArgs); 258357095Sdim 259357095Sdim for (const Expr *ConstraintExpr : ConstraintExprs) { 260357095Sdim if (calculateConstraintSatisfaction(S, Template, TemplateArgs, 261357095Sdim TemplateIDRange.getBegin(), MLTAL, 262357095Sdim ConstraintExpr, Satisfaction)) 263357095Sdim return true; 264357095Sdim if (!Satisfaction.IsSatisfied) 265357095Sdim // [temp.constr.op] p2 266357095Sdim // [...] To determine if a conjunction is satisfied, the satisfaction 267357095Sdim // of the first operand is checked. If that is not satisfied, the 268357095Sdim // conjunction is not satisfied. [...] 269357095Sdim return false; 270353942Sdim } 271357095Sdim return false; 272357095Sdim} 273353942Sdim 274357099Sdimbool Sema::CheckConstraintSatisfaction( 275357964Sdim const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs, 276357099Sdim ArrayRef<TemplateArgument> TemplateArgs, SourceRange TemplateIDRange, 277357099Sdim ConstraintSatisfaction &OutSatisfaction) { 278357099Sdim if (ConstraintExprs.empty()) { 279357099Sdim OutSatisfaction.IsSatisfied = true; 280357099Sdim return false; 281357099Sdim } 282357095Sdim 283357099Sdim llvm::FoldingSetNodeID ID; 284357099Sdim void *InsertPos; 285357099Sdim ConstraintSatisfaction *Satisfaction = nullptr; 286357964Sdim bool ShouldCache = LangOpts.ConceptSatisfactionCaching && Template; 287357964Sdim if (ShouldCache) { 288357099Sdim ConstraintSatisfaction::Profile(ID, Context, Template, TemplateArgs); 289357099Sdim Satisfaction = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos); 290357099Sdim if (Satisfaction) { 291357099Sdim OutSatisfaction = *Satisfaction; 292357099Sdim return false; 293357099Sdim } 294357099Sdim Satisfaction = new ConstraintSatisfaction(Template, TemplateArgs); 295357099Sdim } else { 296357099Sdim Satisfaction = &OutSatisfaction; 297357099Sdim } 298357964Sdim if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs, 299357964Sdim TemplateArgs, TemplateIDRange, 300357964Sdim *Satisfaction)) { 301357964Sdim if (ShouldCache) 302357099Sdim delete Satisfaction; 303357099Sdim return true; 304357099Sdim } 305357095Sdim 306357964Sdim if (ShouldCache) { 307357099Sdim // We cannot use InsertNode here because CheckConstraintSatisfaction might 308357099Sdim // have invalidated it. 309357099Sdim SatisfactionCache.InsertNode(Satisfaction); 310357099Sdim OutSatisfaction = *Satisfaction; 311357099Sdim } 312357099Sdim return false; 313357095Sdim} 314357095Sdim 315357095Sdimbool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr, 316357095Sdim ConstraintSatisfaction &Satisfaction) { 317357095Sdim return calculateConstraintSatisfaction( 318357095Sdim *this, ConstraintExpr, Satisfaction, 319357095Sdim [](const Expr *AtomicExpr) -> ExprResult { 320357095Sdim return ExprResult(const_cast<Expr *>(AtomicExpr)); 321357095Sdim }); 322357095Sdim} 323357095Sdim 324357964Sdimbool Sema::CheckFunctionConstraints(const FunctionDecl *FD, 325357964Sdim ConstraintSatisfaction &Satisfaction, 326357964Sdim SourceLocation UsageLoc) { 327357964Sdim const Expr *RC = FD->getTrailingRequiresClause(); 328357964Sdim if (RC->isInstantiationDependent()) { 329357964Sdim Satisfaction.IsSatisfied = true; 330357964Sdim return false; 331357964Sdim } 332357964Sdim Qualifiers ThisQuals; 333357964Sdim CXXRecordDecl *Record = nullptr; 334357964Sdim if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) { 335357964Sdim ThisQuals = Method->getMethodQualifiers(); 336357964Sdim Record = const_cast<CXXRecordDecl *>(Method->getParent()); 337357964Sdim } 338357964Sdim CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr); 339357964Sdim // We substitute with empty arguments in order to rebuild the atomic 340357964Sdim // constraint in a constant-evaluated context. 341357964Sdim // FIXME: Should this be a dedicated TreeTransform? 342357964Sdim return CheckConstraintSatisfaction( 343357964Sdim FD, {RC}, /*TemplateArgs=*/{}, 344357964Sdim SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()), 345357964Sdim Satisfaction); 346357964Sdim} 347357964Sdim 348357095Sdimbool Sema::EnsureTemplateArgumentListConstraints( 349357095Sdim TemplateDecl *TD, ArrayRef<TemplateArgument> TemplateArgs, 350357095Sdim SourceRange TemplateIDRange) { 351357095Sdim ConstraintSatisfaction Satisfaction; 352357095Sdim llvm::SmallVector<const Expr *, 3> AssociatedConstraints; 353357095Sdim TD->getAssociatedConstraints(AssociatedConstraints); 354357095Sdim if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgs, 355357095Sdim TemplateIDRange, Satisfaction)) 356353942Sdim return true; 357353942Sdim 358357095Sdim if (!Satisfaction.IsSatisfied) { 359357095Sdim SmallString<128> TemplateArgString; 360357095Sdim TemplateArgString = " "; 361357095Sdim TemplateArgString += getTemplateArgumentBindingsText( 362357095Sdim TD->getTemplateParameters(), TemplateArgs.data(), TemplateArgs.size()); 363357095Sdim 364357095Sdim Diag(TemplateIDRange.getBegin(), 365357095Sdim diag::err_template_arg_list_constraints_not_satisfied) 366357095Sdim << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD 367357095Sdim << TemplateArgString << TemplateIDRange; 368357095Sdim DiagnoseUnsatisfiedConstraint(Satisfaction); 369353942Sdim return true; 370353942Sdim } 371357095Sdim return false; 372357095Sdim} 373353942Sdim 374357099Sdimstatic void diagnoseUnsatisfiedRequirement(Sema &S, 375357099Sdim concepts::ExprRequirement *Req, 376357099Sdim bool First) { 377357099Sdim assert(!Req->isSatisfied() 378357099Sdim && "Diagnose() can only be used on an unsatisfied requirement"); 379357099Sdim switch (Req->getSatisfactionStatus()) { 380357099Sdim case concepts::ExprRequirement::SS_Dependent: 381357099Sdim llvm_unreachable("Diagnosing a dependent requirement"); 382357099Sdim break; 383357099Sdim case concepts::ExprRequirement::SS_ExprSubstitutionFailure: { 384357099Sdim auto *SubstDiag = Req->getExprSubstitutionDiagnostic(); 385357099Sdim if (!SubstDiag->DiagMessage.empty()) 386357099Sdim S.Diag(SubstDiag->DiagLoc, 387357099Sdim diag::note_expr_requirement_expr_substitution_error) 388357099Sdim << (int)First << SubstDiag->SubstitutedEntity 389357099Sdim << SubstDiag->DiagMessage; 390357099Sdim else 391357099Sdim S.Diag(SubstDiag->DiagLoc, 392357099Sdim diag::note_expr_requirement_expr_unknown_substitution_error) 393357099Sdim << (int)First << SubstDiag->SubstitutedEntity; 394357099Sdim break; 395357099Sdim } 396357099Sdim case concepts::ExprRequirement::SS_NoexceptNotMet: 397357099Sdim S.Diag(Req->getNoexceptLoc(), 398357099Sdim diag::note_expr_requirement_noexcept_not_met) 399357099Sdim << (int)First << Req->getExpr(); 400357099Sdim break; 401357099Sdim case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: { 402357099Sdim auto *SubstDiag = 403357099Sdim Req->getReturnTypeRequirement().getSubstitutionDiagnostic(); 404357099Sdim if (!SubstDiag->DiagMessage.empty()) 405357099Sdim S.Diag(SubstDiag->DiagLoc, 406357099Sdim diag::note_expr_requirement_type_requirement_substitution_error) 407357099Sdim << (int)First << SubstDiag->SubstitutedEntity 408357099Sdim << SubstDiag->DiagMessage; 409357099Sdim else 410357099Sdim S.Diag(SubstDiag->DiagLoc, 411357099Sdim diag::note_expr_requirement_type_requirement_unknown_substitution_error) 412357099Sdim << (int)First << SubstDiag->SubstitutedEntity; 413357099Sdim break; 414357099Sdim } 415357099Sdim case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: { 416357099Sdim ConceptSpecializationExpr *ConstraintExpr = 417357099Sdim Req->getReturnTypeRequirementSubstitutedConstraintExpr(); 418357099Sdim if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1) 419357099Sdim // A simple case - expr type is the type being constrained and the concept 420357099Sdim // was not provided arguments. 421357099Sdim S.Diag(ConstraintExpr->getBeginLoc(), 422357099Sdim diag::note_expr_requirement_constraints_not_satisfied_simple) 423357099Sdim << (int)First << S.BuildDecltypeType(Req->getExpr(), 424357099Sdim Req->getExpr()->getBeginLoc()) 425357099Sdim << ConstraintExpr->getNamedConcept(); 426357099Sdim else 427357099Sdim S.Diag(ConstraintExpr->getBeginLoc(), 428357099Sdim diag::note_expr_requirement_constraints_not_satisfied) 429357099Sdim << (int)First << ConstraintExpr; 430357099Sdim S.DiagnoseUnsatisfiedConstraint(ConstraintExpr->getSatisfaction()); 431357099Sdim break; 432357099Sdim } 433357099Sdim case concepts::ExprRequirement::SS_Satisfied: 434357099Sdim llvm_unreachable("We checked this above"); 435357099Sdim } 436357099Sdim} 437357099Sdim 438357099Sdimstatic void diagnoseUnsatisfiedRequirement(Sema &S, 439357099Sdim concepts::TypeRequirement *Req, 440357099Sdim bool First) { 441357099Sdim assert(!Req->isSatisfied() 442357099Sdim && "Diagnose() can only be used on an unsatisfied requirement"); 443357099Sdim switch (Req->getSatisfactionStatus()) { 444357099Sdim case concepts::TypeRequirement::SS_Dependent: 445357099Sdim llvm_unreachable("Diagnosing a dependent requirement"); 446357099Sdim return; 447357099Sdim case concepts::TypeRequirement::SS_SubstitutionFailure: { 448357099Sdim auto *SubstDiag = Req->getSubstitutionDiagnostic(); 449357099Sdim if (!SubstDiag->DiagMessage.empty()) 450357099Sdim S.Diag(SubstDiag->DiagLoc, 451357099Sdim diag::note_type_requirement_substitution_error) << (int)First 452357099Sdim << SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage; 453357099Sdim else 454357099Sdim S.Diag(SubstDiag->DiagLoc, 455357099Sdim diag::note_type_requirement_unknown_substitution_error) 456357099Sdim << (int)First << SubstDiag->SubstitutedEntity; 457357099Sdim return; 458357099Sdim } 459357099Sdim default: 460357099Sdim llvm_unreachable("Unknown satisfaction status"); 461357099Sdim return; 462357099Sdim } 463357099Sdim} 464357099Sdim 465357099Sdimstatic void diagnoseUnsatisfiedRequirement(Sema &S, 466357099Sdim concepts::NestedRequirement *Req, 467357099Sdim bool First) { 468357099Sdim if (Req->isSubstitutionFailure()) { 469357099Sdim concepts::Requirement::SubstitutionDiagnostic *SubstDiag = 470357099Sdim Req->getSubstitutionDiagnostic(); 471357099Sdim if (!SubstDiag->DiagMessage.empty()) 472357099Sdim S.Diag(SubstDiag->DiagLoc, 473357099Sdim diag::note_nested_requirement_substitution_error) 474357099Sdim << (int)First << SubstDiag->SubstitutedEntity 475357099Sdim << SubstDiag->DiagMessage; 476357099Sdim else 477357099Sdim S.Diag(SubstDiag->DiagLoc, 478357099Sdim diag::note_nested_requirement_unknown_substitution_error) 479357099Sdim << (int)First << SubstDiag->SubstitutedEntity; 480357099Sdim return; 481357099Sdim } 482357099Sdim S.DiagnoseUnsatisfiedConstraint(Req->getConstraintSatisfaction(), First); 483357099Sdim} 484357099Sdim 485357099Sdim 486357095Sdimstatic void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S, 487357095Sdim Expr *SubstExpr, 488357095Sdim bool First = true) { 489357095Sdim SubstExpr = SubstExpr->IgnoreParenImpCasts(); 490357095Sdim if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) { 491357095Sdim switch (BO->getOpcode()) { 492357095Sdim // These two cases will in practice only be reached when using fold 493357095Sdim // expressions with || and &&, since otherwise the || and && will have been 494357095Sdim // broken down into atomic constraints during satisfaction checking. 495357095Sdim case BO_LOr: 496357095Sdim // Or evaluated to false - meaning both RHS and LHS evaluated to false. 497357095Sdim diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First); 498357095Sdim diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), 499357095Sdim /*First=*/false); 500357095Sdim return; 501357095Sdim case BO_LAnd: 502357095Sdim bool LHSSatisfied; 503357095Sdim BO->getLHS()->EvaluateAsBooleanCondition(LHSSatisfied, S.Context); 504357095Sdim if (LHSSatisfied) { 505357095Sdim // LHS is true, so RHS must be false. 506357095Sdim diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First); 507357095Sdim return; 508357095Sdim } 509357095Sdim // LHS is false 510357095Sdim diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First); 511353942Sdim 512357095Sdim // RHS might also be false 513357095Sdim bool RHSSatisfied; 514357095Sdim BO->getRHS()->EvaluateAsBooleanCondition(RHSSatisfied, S.Context); 515357095Sdim if (!RHSSatisfied) 516357095Sdim diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), 517357095Sdim /*First=*/false); 518357095Sdim return; 519357095Sdim case BO_GE: 520357095Sdim case BO_LE: 521357095Sdim case BO_GT: 522357095Sdim case BO_LT: 523357095Sdim case BO_EQ: 524357095Sdim case BO_NE: 525357095Sdim if (BO->getLHS()->getType()->isIntegerType() && 526357095Sdim BO->getRHS()->getType()->isIntegerType()) { 527357095Sdim Expr::EvalResult SimplifiedLHS; 528357095Sdim Expr::EvalResult SimplifiedRHS; 529357095Sdim BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context); 530357095Sdim BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context); 531357095Sdim if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) { 532357095Sdim S.Diag(SubstExpr->getBeginLoc(), 533357095Sdim diag::note_atomic_constraint_evaluated_to_false_elaborated) 534357095Sdim << (int)First << SubstExpr 535357095Sdim << SimplifiedLHS.Val.getInt().toString(10) 536357095Sdim << BinaryOperator::getOpcodeStr(BO->getOpcode()) 537357095Sdim << SimplifiedRHS.Val.getInt().toString(10); 538357095Sdim return; 539357095Sdim } 540357095Sdim } 541357095Sdim break; 542357095Sdim 543357095Sdim default: 544357095Sdim break; 545357095Sdim } 546357095Sdim } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) { 547357095Sdim if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) { 548357095Sdim S.Diag( 549357095Sdim CSE->getSourceRange().getBegin(), 550357095Sdim diag:: 551357095Sdim note_single_arg_concept_specialization_constraint_evaluated_to_false) 552357095Sdim << (int)First 553357095Sdim << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument() 554357095Sdim << CSE->getNamedConcept(); 555357095Sdim } else { 556357095Sdim S.Diag(SubstExpr->getSourceRange().getBegin(), 557357095Sdim diag::note_concept_specialization_constraint_evaluated_to_false) 558357095Sdim << (int)First << CSE; 559357095Sdim } 560357095Sdim S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction()); 561357095Sdim return; 562357099Sdim } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) { 563357099Sdim for (concepts::Requirement *Req : RE->getRequirements()) 564357099Sdim if (!Req->isDependent() && !Req->isSatisfied()) { 565357099Sdim if (auto *E = dyn_cast<concepts::ExprRequirement>(Req)) 566357099Sdim diagnoseUnsatisfiedRequirement(S, E, First); 567357099Sdim else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req)) 568357099Sdim diagnoseUnsatisfiedRequirement(S, T, First); 569357099Sdim else 570357099Sdim diagnoseUnsatisfiedRequirement( 571357099Sdim S, cast<concepts::NestedRequirement>(Req), First); 572357099Sdim break; 573357099Sdim } 574357099Sdim return; 575357095Sdim } 576357095Sdim 577357095Sdim S.Diag(SubstExpr->getSourceRange().getBegin(), 578357095Sdim diag::note_atomic_constraint_evaluated_to_false) 579357095Sdim << (int)First << SubstExpr; 580357095Sdim} 581357095Sdim 582357095Sdimtemplate<typename SubstitutionDiagnostic> 583357095Sdimstatic void diagnoseUnsatisfiedConstraintExpr( 584357095Sdim Sema &S, const Expr *E, 585357095Sdim const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record, 586357095Sdim bool First = true) { 587357095Sdim if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){ 588357095Sdim S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed) 589357095Sdim << Diag->second; 590357095Sdim return; 591357095Sdim } 592357095Sdim 593357095Sdim diagnoseWellFormedUnsatisfiedConstraintExpr(S, 594357095Sdim Record.template get<Expr *>(), First); 595357095Sdim} 596357095Sdim 597357099Sdimvoid 598357099SdimSema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction, 599357099Sdim bool First) { 600357095Sdim assert(!Satisfaction.IsSatisfied && 601357095Sdim "Attempted to diagnose a satisfied constraint"); 602357095Sdim for (auto &Pair : Satisfaction.Details) { 603357095Sdim diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First); 604357095Sdim First = false; 605357095Sdim } 606357095Sdim} 607357095Sdim 608357095Sdimvoid Sema::DiagnoseUnsatisfiedConstraint( 609357099Sdim const ASTConstraintSatisfaction &Satisfaction, 610357099Sdim bool First) { 611357095Sdim assert(!Satisfaction.IsSatisfied && 612357095Sdim "Attempted to diagnose a satisfied constraint"); 613357095Sdim for (auto &Pair : Satisfaction) { 614357095Sdim diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First); 615357095Sdim First = false; 616357095Sdim } 617357095Sdim} 618357095Sdim 619357095Sdimconst NormalizedConstraint * 620357095SdimSema::getNormalizedAssociatedConstraints( 621357095Sdim NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) { 622357095Sdim auto CacheEntry = NormalizationCache.find(ConstrainedDecl); 623357095Sdim if (CacheEntry == NormalizationCache.end()) { 624357095Sdim auto Normalized = 625357095Sdim NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl, 626357095Sdim AssociatedConstraints); 627357095Sdim CacheEntry = 628357095Sdim NormalizationCache 629357095Sdim .try_emplace(ConstrainedDecl, 630357095Sdim Normalized 631357095Sdim ? new (Context) NormalizedConstraint( 632357095Sdim std::move(*Normalized)) 633357095Sdim : nullptr) 634357095Sdim .first; 635357095Sdim } 636357095Sdim return CacheEntry->second; 637357095Sdim} 638357095Sdim 639357095Sdimstatic bool substituteParameterMappings(Sema &S, NormalizedConstraint &N, 640357095Sdim ConceptDecl *Concept, ArrayRef<TemplateArgument> TemplateArgs, 641357095Sdim const ASTTemplateArgumentListInfo *ArgsAsWritten) { 642357095Sdim if (!N.isAtomic()) { 643357095Sdim if (substituteParameterMappings(S, N.getLHS(), Concept, TemplateArgs, 644357095Sdim ArgsAsWritten)) 645357095Sdim return true; 646357095Sdim return substituteParameterMappings(S, N.getRHS(), Concept, TemplateArgs, 647357095Sdim ArgsAsWritten); 648357095Sdim } 649357095Sdim TemplateParameterList *TemplateParams = Concept->getTemplateParameters(); 650357095Sdim 651357095Sdim AtomicConstraint &Atomic = *N.getAtomicConstraint(); 652357095Sdim TemplateArgumentListInfo SubstArgs; 653357095Sdim MultiLevelTemplateArgumentList MLTAL; 654357095Sdim MLTAL.addOuterTemplateArguments(TemplateArgs); 655357095Sdim if (!Atomic.ParameterMapping) { 656357095Sdim llvm::SmallBitVector OccurringIndices(TemplateParams->size()); 657357095Sdim S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false, 658357095Sdim /*Depth=*/0, OccurringIndices); 659357095Sdim Atomic.ParameterMapping.emplace( 660357095Sdim MutableArrayRef<TemplateArgumentLoc>( 661357095Sdim new (S.Context) TemplateArgumentLoc[OccurringIndices.count()], 662357095Sdim OccurringIndices.count())); 663357095Sdim for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I) 664357095Sdim if (OccurringIndices[I]) 665357095Sdim new (&(*Atomic.ParameterMapping)[J++]) TemplateArgumentLoc( 666357095Sdim S.getIdentityTemplateArgumentLoc(TemplateParams->begin()[I], 667357095Sdim // Here we assume we do not support things like 668357095Sdim // template<typename A, typename B> 669357095Sdim // concept C = ...; 670357095Sdim // 671357095Sdim // template<typename... Ts> requires C<Ts...> 672357095Sdim // struct S { }; 673357095Sdim // The above currently yields a diagnostic. 674357095Sdim // We still might have default arguments for concept parameters. 675357095Sdim ArgsAsWritten->NumTemplateArgs > I ? 676357095Sdim ArgsAsWritten->arguments()[I].getLocation() : 677357095Sdim SourceLocation())); 678357095Sdim } 679357095Sdim Sema::InstantiatingTemplate Inst( 680357095Sdim S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(), 681357095Sdim Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept, 682357095Sdim SourceRange(ArgsAsWritten->arguments()[0].getSourceRange().getBegin(), 683357095Sdim ArgsAsWritten->arguments().back().getSourceRange().getEnd())); 684357095Sdim if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs)) 685357095Sdim return true; 686357964Sdim Atomic.ParameterMapping.emplace( 687357964Sdim MutableArrayRef<TemplateArgumentLoc>( 688357964Sdim new (S.Context) TemplateArgumentLoc[SubstArgs.size()], 689357964Sdim SubstArgs.size())); 690357095Sdim std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(), 691357095Sdim N.getAtomicConstraint()->ParameterMapping->begin()); 692353942Sdim return false; 693357095Sdim} 694357095Sdim 695357095SdimOptional<NormalizedConstraint> 696357095SdimNormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D, 697357095Sdim ArrayRef<const Expr *> E) { 698357095Sdim assert(E.size() != 0); 699357095Sdim auto First = fromConstraintExpr(S, D, E[0]); 700357095Sdim if (E.size() == 1) 701357095Sdim return First; 702357095Sdim auto Second = fromConstraintExpr(S, D, E[1]); 703357095Sdim if (!Second) 704357095Sdim return None; 705357095Sdim llvm::Optional<NormalizedConstraint> Conjunction; 706357095Sdim Conjunction.emplace(S.Context, std::move(*First), std::move(*Second), 707357095Sdim CCK_Conjunction); 708357095Sdim for (unsigned I = 2; I < E.size(); ++I) { 709357095Sdim auto Next = fromConstraintExpr(S, D, E[I]); 710357095Sdim if (!Next) 711357095Sdim return llvm::Optional<NormalizedConstraint>{}; 712357095Sdim NormalizedConstraint NewConjunction(S.Context, std::move(*Conjunction), 713357095Sdim std::move(*Next), CCK_Conjunction); 714357095Sdim *Conjunction = std::move(NewConjunction); 715357095Sdim } 716357095Sdim return Conjunction; 717357095Sdim} 718357095Sdim 719357095Sdimllvm::Optional<NormalizedConstraint> 720357095SdimNormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) { 721357095Sdim assert(E != nullptr); 722357095Sdim 723357095Sdim // C++ [temp.constr.normal]p1.1 724357095Sdim // [...] 725357095Sdim // - The normal form of an expression (E) is the normal form of E. 726357095Sdim // [...] 727357095Sdim E = E->IgnoreParenImpCasts(); 728357095Sdim if (auto *BO = dyn_cast<const BinaryOperator>(E)) { 729357095Sdim if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) { 730357095Sdim auto LHS = fromConstraintExpr(S, D, BO->getLHS()); 731357095Sdim if (!LHS) 732357095Sdim return None; 733357095Sdim auto RHS = fromConstraintExpr(S, D, BO->getRHS()); 734357095Sdim if (!RHS) 735357095Sdim return None; 736357095Sdim 737357095Sdim return NormalizedConstraint( 738357095Sdim S.Context, std::move(*LHS), std::move(*RHS), 739357095Sdim BO->getOpcode() == BO_LAnd ? CCK_Conjunction : CCK_Disjunction); 740357095Sdim } 741357095Sdim } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) { 742357095Sdim const NormalizedConstraint *SubNF; 743357095Sdim { 744357095Sdim Sema::InstantiatingTemplate Inst( 745357095Sdim S, CSE->getExprLoc(), 746357095Sdim Sema::InstantiatingTemplate::ConstraintNormalization{}, D, 747357095Sdim CSE->getSourceRange()); 748357095Sdim // C++ [temp.constr.normal]p1.1 749357095Sdim // [...] 750357095Sdim // The normal form of an id-expression of the form C<A1, A2, ..., AN>, 751357095Sdim // where C names a concept, is the normal form of the 752357095Sdim // constraint-expression of C, after substituting A1, A2, ..., AN for C���s 753357095Sdim // respective template parameters in the parameter mappings in each atomic 754357095Sdim // constraint. If any such substitution results in an invalid type or 755357095Sdim // expression, the program is ill-formed; no diagnostic is required. 756357095Sdim // [...] 757357095Sdim ConceptDecl *CD = CSE->getNamedConcept(); 758357095Sdim SubNF = S.getNormalizedAssociatedConstraints(CD, 759357095Sdim {CD->getConstraintExpr()}); 760357095Sdim if (!SubNF) 761357095Sdim return None; 762357095Sdim } 763357095Sdim 764357095Sdim Optional<NormalizedConstraint> New; 765357095Sdim New.emplace(S.Context, *SubNF); 766357095Sdim 767357095Sdim if (substituteParameterMappings( 768357095Sdim S, *New, CSE->getNamedConcept(), 769357095Sdim CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten())) 770357095Sdim return None; 771357095Sdim 772357095Sdim return New; 773357095Sdim } 774357095Sdim return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)}; 775357095Sdim} 776357095Sdim 777357095Sdimusing NormalForm = 778357095Sdim llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>; 779357095Sdim 780357095Sdimstatic NormalForm makeCNF(const NormalizedConstraint &Normalized) { 781357095Sdim if (Normalized.isAtomic()) 782357095Sdim return {{Normalized.getAtomicConstraint()}}; 783357095Sdim 784357095Sdim NormalForm LCNF = makeCNF(Normalized.getLHS()); 785357095Sdim NormalForm RCNF = makeCNF(Normalized.getRHS()); 786357095Sdim if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) { 787357095Sdim LCNF.reserve(LCNF.size() + RCNF.size()); 788357095Sdim while (!RCNF.empty()) 789357095Sdim LCNF.push_back(RCNF.pop_back_val()); 790357095Sdim return LCNF; 791357095Sdim } 792357095Sdim 793357095Sdim // Disjunction 794357095Sdim NormalForm Res; 795357095Sdim Res.reserve(LCNF.size() * RCNF.size()); 796357095Sdim for (auto &LDisjunction : LCNF) 797357095Sdim for (auto &RDisjunction : RCNF) { 798357095Sdim NormalForm::value_type Combined; 799357095Sdim Combined.reserve(LDisjunction.size() + RDisjunction.size()); 800357095Sdim std::copy(LDisjunction.begin(), LDisjunction.end(), 801357095Sdim std::back_inserter(Combined)); 802357095Sdim std::copy(RDisjunction.begin(), RDisjunction.end(), 803357095Sdim std::back_inserter(Combined)); 804357095Sdim Res.emplace_back(Combined); 805357095Sdim } 806357095Sdim return Res; 807357095Sdim} 808357095Sdim 809357095Sdimstatic NormalForm makeDNF(const NormalizedConstraint &Normalized) { 810357095Sdim if (Normalized.isAtomic()) 811357095Sdim return {{Normalized.getAtomicConstraint()}}; 812357095Sdim 813357095Sdim NormalForm LDNF = makeDNF(Normalized.getLHS()); 814357095Sdim NormalForm RDNF = makeDNF(Normalized.getRHS()); 815357095Sdim if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) { 816357095Sdim LDNF.reserve(LDNF.size() + RDNF.size()); 817357095Sdim while (!RDNF.empty()) 818357095Sdim LDNF.push_back(RDNF.pop_back_val()); 819357095Sdim return LDNF; 820357095Sdim } 821357095Sdim 822357095Sdim // Conjunction 823357095Sdim NormalForm Res; 824357095Sdim Res.reserve(LDNF.size() * RDNF.size()); 825357095Sdim for (auto &LConjunction : LDNF) { 826357095Sdim for (auto &RConjunction : RDNF) { 827357095Sdim NormalForm::value_type Combined; 828357095Sdim Combined.reserve(LConjunction.size() + RConjunction.size()); 829357095Sdim std::copy(LConjunction.begin(), LConjunction.end(), 830357095Sdim std::back_inserter(Combined)); 831357095Sdim std::copy(RConjunction.begin(), RConjunction.end(), 832357095Sdim std::back_inserter(Combined)); 833357095Sdim Res.emplace_back(Combined); 834357095Sdim } 835357095Sdim } 836357095Sdim return Res; 837357095Sdim} 838357095Sdim 839357095Sdimtemplate<typename AtomicSubsumptionEvaluator> 840357095Sdimstatic bool subsumes(NormalForm PDNF, NormalForm QCNF, 841357095Sdim AtomicSubsumptionEvaluator E) { 842357095Sdim // C++ [temp.constr.order] p2 843357095Sdim // Then, P subsumes Q if and only if, for every disjunctive clause Pi in the 844357095Sdim // disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in 845357095Sdim // the conjuctive normal form of Q, where [...] 846357095Sdim for (const auto &Pi : PDNF) { 847357095Sdim for (const auto &Qj : QCNF) { 848357095Sdim // C++ [temp.constr.order] p2 849357095Sdim // - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if 850357095Sdim // and only if there exists an atomic constraint Pia in Pi for which 851357095Sdim // there exists an atomic constraint, Qjb, in Qj such that Pia 852357095Sdim // subsumes Qjb. 853357095Sdim bool Found = false; 854357095Sdim for (const AtomicConstraint *Pia : Pi) { 855357095Sdim for (const AtomicConstraint *Qjb : Qj) { 856357095Sdim if (E(*Pia, *Qjb)) { 857357095Sdim Found = true; 858357095Sdim break; 859357095Sdim } 860357095Sdim } 861357095Sdim if (Found) 862357095Sdim break; 863357095Sdim } 864357095Sdim if (!Found) 865357095Sdim return false; 866357095Sdim } 867357095Sdim } 868357095Sdim return true; 869357095Sdim} 870357095Sdim 871357095Sdimtemplate<typename AtomicSubsumptionEvaluator> 872357095Sdimstatic bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P, 873357095Sdim NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes, 874357095Sdim AtomicSubsumptionEvaluator E) { 875357095Sdim // C++ [temp.constr.order] p2 876357095Sdim // In order to determine if a constraint P subsumes a constraint Q, P is 877357095Sdim // transformed into disjunctive normal form, and Q is transformed into 878357095Sdim // conjunctive normal form. [...] 879357095Sdim auto *PNormalized = S.getNormalizedAssociatedConstraints(DP, P); 880357095Sdim if (!PNormalized) 881357095Sdim return true; 882357095Sdim const NormalForm PDNF = makeDNF(*PNormalized); 883357095Sdim 884357095Sdim auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q); 885357095Sdim if (!QNormalized) 886357095Sdim return true; 887357095Sdim const NormalForm QCNF = makeCNF(*QNormalized); 888357095Sdim 889357095Sdim Subsumes = subsumes(PDNF, QCNF, E); 890357095Sdim return false; 891357095Sdim} 892357095Sdim 893357095Sdimbool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef<const Expr *> AC1, 894357095Sdim NamedDecl *D2, ArrayRef<const Expr *> AC2, 895357095Sdim bool &Result) { 896357095Sdim if (AC1.empty()) { 897357095Sdim Result = AC2.empty(); 898357095Sdim return false; 899357095Sdim } 900357095Sdim if (AC2.empty()) { 901357095Sdim // TD1 has associated constraints and TD2 does not. 902357095Sdim Result = true; 903357095Sdim return false; 904357095Sdim } 905357095Sdim 906357095Sdim std::pair<NamedDecl *, NamedDecl *> Key{D1, D2}; 907357095Sdim auto CacheEntry = SubsumptionCache.find(Key); 908357095Sdim if (CacheEntry != SubsumptionCache.end()) { 909357095Sdim Result = CacheEntry->second; 910357095Sdim return false; 911357095Sdim } 912357095Sdim 913357095Sdim if (subsumes(*this, D1, AC1, D2, AC2, Result, 914357095Sdim [this] (const AtomicConstraint &A, const AtomicConstraint &B) { 915357095Sdim return A.subsumes(Context, B); 916357095Sdim })) 917357095Sdim return true; 918357095Sdim SubsumptionCache.try_emplace(Key, Result); 919357095Sdim return false; 920357095Sdim} 921357095Sdim 922357095Sdimbool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1, 923357095Sdim ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) { 924357095Sdim if (isSFINAEContext()) 925357095Sdim // No need to work here because our notes would be discarded. 926357095Sdim return false; 927357095Sdim 928357095Sdim if (AC1.empty() || AC2.empty()) 929357095Sdim return false; 930357095Sdim 931357095Sdim auto NormalExprEvaluator = 932357095Sdim [this] (const AtomicConstraint &A, const AtomicConstraint &B) { 933357095Sdim return A.subsumes(Context, B); 934357095Sdim }; 935357095Sdim 936357095Sdim const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr; 937357095Sdim auto IdenticalExprEvaluator = 938357095Sdim [&] (const AtomicConstraint &A, const AtomicConstraint &B) { 939357095Sdim if (!A.hasMatchingParameterMapping(Context, B)) 940357095Sdim return false; 941357095Sdim const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr; 942357095Sdim if (EA == EB) 943357095Sdim return true; 944357095Sdim 945357095Sdim // Not the same source level expression - are the expressions 946357095Sdim // identical? 947357095Sdim llvm::FoldingSetNodeID IDA, IDB; 948357095Sdim EA->Profile(IDA, Context, /*Cannonical=*/true); 949357095Sdim EB->Profile(IDB, Context, /*Cannonical=*/true); 950357095Sdim if (IDA != IDB) 951357095Sdim return false; 952357095Sdim 953357095Sdim AmbiguousAtomic1 = EA; 954357095Sdim AmbiguousAtomic2 = EB; 955357095Sdim return true; 956357095Sdim }; 957357095Sdim 958357095Sdim { 959357095Sdim // The subsumption checks might cause diagnostics 960357095Sdim SFINAETrap Trap(*this); 961357095Sdim auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1); 962357095Sdim if (!Normalized1) 963357095Sdim return false; 964357095Sdim const NormalForm DNF1 = makeDNF(*Normalized1); 965357095Sdim const NormalForm CNF1 = makeCNF(*Normalized1); 966357095Sdim 967357095Sdim auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2); 968357095Sdim if (!Normalized2) 969357095Sdim return false; 970357095Sdim const NormalForm DNF2 = makeDNF(*Normalized2); 971357095Sdim const NormalForm CNF2 = makeCNF(*Normalized2); 972357095Sdim 973357095Sdim bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator); 974357095Sdim bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator); 975357095Sdim bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator); 976357095Sdim bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator); 977357095Sdim if (Is1AtLeastAs2 == Is1AtLeastAs2Normally && 978357095Sdim Is2AtLeastAs1 == Is2AtLeastAs1Normally) 979357095Sdim // Same result - no ambiguity was caused by identical atomic expressions. 980357095Sdim return false; 981357095Sdim } 982357095Sdim 983357095Sdim // A different result! Some ambiguous atomic constraint(s) caused a difference 984357095Sdim assert(AmbiguousAtomic1 && AmbiguousAtomic2); 985357095Sdim 986357095Sdim Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints) 987357095Sdim << AmbiguousAtomic1->getSourceRange(); 988357095Sdim Diag(AmbiguousAtomic2->getBeginLoc(), 989357095Sdim diag::note_ambiguous_atomic_constraints_similar_expression) 990357095Sdim << AmbiguousAtomic2->getSourceRange(); 991357095Sdim return true; 992357095Sdim} 993357099Sdim 994357099Sdimconcepts::ExprRequirement::ExprRequirement( 995357099Sdim Expr *E, bool IsSimple, SourceLocation NoexceptLoc, 996357099Sdim ReturnTypeRequirement Req, SatisfactionStatus Status, 997357099Sdim ConceptSpecializationExpr *SubstitutedConstraintExpr) : 998357099Sdim Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent, 999357099Sdim Status == SS_Dependent && 1000357099Sdim (E->containsUnexpandedParameterPack() || 1001357099Sdim Req.containsUnexpandedParameterPack()), 1002357099Sdim Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc), 1003357099Sdim TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr), 1004357099Sdim Status(Status) { 1005357099Sdim assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) && 1006357099Sdim "Simple requirement must not have a return type requirement or a " 1007357099Sdim "noexcept specification"); 1008357099Sdim assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) == 1009357099Sdim (SubstitutedConstraintExpr != nullptr)); 1010357099Sdim} 1011357099Sdim 1012357099Sdimconcepts::ExprRequirement::ExprRequirement( 1013357099Sdim SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple, 1014357099Sdim SourceLocation NoexceptLoc, ReturnTypeRequirement Req) : 1015357099Sdim Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(), 1016357099Sdim Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false), 1017357099Sdim Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req), 1018357099Sdim Status(SS_ExprSubstitutionFailure) { 1019357099Sdim assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) && 1020357099Sdim "Simple requirement must not have a return type requirement or a " 1021357099Sdim "noexcept specification"); 1022357099Sdim} 1023357099Sdim 1024357099Sdimconcepts::ExprRequirement::ReturnTypeRequirement:: 1025357099SdimReturnTypeRequirement(TemplateParameterList *TPL) : 1026357099Sdim TypeConstraintInfo(TPL, 0) { 1027357099Sdim assert(TPL->size() == 1); 1028357099Sdim const TypeConstraint *TC = 1029357099Sdim cast<TemplateTypeParmDecl>(TPL->getParam(0))->getTypeConstraint(); 1030357099Sdim assert(TC && 1031357099Sdim "TPL must have a template type parameter with a type constraint"); 1032357099Sdim auto *Constraint = 1033357099Sdim cast_or_null<ConceptSpecializationExpr>( 1034357099Sdim TC->getImmediatelyDeclaredConstraint()); 1035357099Sdim bool Dependent = false; 1036357099Sdim if (Constraint->getTemplateArgsAsWritten()) { 1037357099Sdim for (auto &ArgLoc : 1038357099Sdim Constraint->getTemplateArgsAsWritten()->arguments().drop_front(1)) { 1039357099Sdim if (ArgLoc.getArgument().isDependent()) { 1040357099Sdim Dependent = true; 1041357099Sdim break; 1042357099Sdim } 1043357099Sdim } 1044357099Sdim } 1045357099Sdim TypeConstraintInfo.setInt(Dependent ? 1 : 0); 1046357099Sdim} 1047357099Sdim 1048357099Sdimconcepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) : 1049357099Sdim Requirement(RK_Type, T->getType()->isDependentType(), 1050357099Sdim T->getType()->containsUnexpandedParameterPack(), 1051357099Sdim // We reach this ctor with either dependent types (in which 1052357099Sdim // IsSatisfied doesn't matter) or with non-dependent type in 1053357099Sdim // which the existence of the type indicates satisfaction. 1054357099Sdim /*IsSatisfied=*/true 1055357099Sdim ), Value(T), 1056357099Sdim Status(T->getType()->isDependentType() ? SS_Dependent : SS_Satisfied) {} 1057