| //===-- SemaConcept.cpp - Semantic Analysis for Constraints and Concepts --===// | |
| // | |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |
| // See https://llvm.org/LICENSE.txt for license information. | |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |
| // | |
| //===----------------------------------------------------------------------===// | |
| // | |
| // This file implements semantic analysis for C++ constraints and concepts. | |
| // | |
| //===----------------------------------------------------------------------===// | |
| #include "clang/Sema/SemaConcept.h" | |
| #include "TreeTransform.h" | |
| #include "clang/AST/ASTConcept.h" | |
| #include "clang/AST/ASTLambda.h" | |
| #include "clang/AST/DeclCXX.h" | |
| #include "clang/AST/ExprConcepts.h" | |
| #include "clang/AST/RecursiveASTVisitor.h" | |
| #include "clang/AST/TextNodeDumper.h" | |
| #include "clang/Basic/OperatorPrecedence.h" | |
| #include "clang/Sema/EnterExpressionEvaluationContext.h" | |
| #include "clang/Sema/Initialization.h" | |
| #include "clang/Sema/Overload.h" | |
| #include "clang/Sema/ScopeInfo.h" | |
| #include "clang/Sema/Sema.h" | |
| #include "clang/Sema/SemaInternal.h" | |
| #include "clang/Sema/Template.h" | |
| #include "clang/Sema/TemplateDeduction.h" | |
| #include "llvm/ADT/DenseMap.h" | |
| #include "llvm/ADT/PointerUnion.h" | |
| #include "llvm/ADT/StringExtras.h" | |
| #include "llvm/Support/SaveAndRestore.h" | |
| #include "llvm/Support/ScopedPrinter.h" | |
| #include "llvm/Support/TimeProfiler.h" | |
| using namespace clang; | |
| using namespace sema; | |
| namespace { | |
| class LogicalBinOp { | |
| SourceLocation Loc; | |
| OverloadedOperatorKind Op = OO_None; | |
| const Expr *LHS = nullptr; | |
| const Expr *RHS = nullptr; | |
| public: | |
| LogicalBinOp(const Expr *E) { | |
| if (auto *BO = dyn_cast<BinaryOperator>(E)) { | |
| Op = BinaryOperator::getOverloadedOperator(BO->getOpcode()); | |
| LHS = BO->getLHS(); | |
| RHS = BO->getRHS(); | |
| Loc = BO->getExprLoc(); | |
| } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(E)) { | |
| // If OO is not || or && it might not have exactly 2 arguments. | |
| if (OO->getNumArgs() == 2) { | |
| Op = OO->getOperator(); | |
| LHS = OO->getArg(0); | |
| RHS = OO->getArg(1); | |
| Loc = OO->getOperatorLoc(); | |
| } | |
| } | |
| } | |
| bool isAnd() const { return Op == OO_AmpAmp; } | |
| bool isOr() const { return Op == OO_PipePipe; } | |
| explicit operator bool() const { return isAnd() || isOr(); } | |
| const Expr *getLHS() const { return LHS; } | |
| const Expr *getRHS() const { return RHS; } | |
| OverloadedOperatorKind getOp() const { return Op; } | |
| ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS) const { | |
| return recreateBinOp(SemaRef, LHS, const_cast<Expr *>(getRHS())); | |
| } | |
| ExprResult recreateBinOp(Sema &SemaRef, ExprResult LHS, | |
| ExprResult RHS) const { | |
| assert((isAnd() || isOr()) && "Not the right kind of op?"); | |
| assert((!LHS.isInvalid() && !RHS.isInvalid()) && "not good expressions?"); | |
| if (!LHS.isUsable() || !RHS.isUsable()) | |
| return ExprEmpty(); | |
| // We should just be able to 'normalize' these to the builtin Binary | |
| // Operator, since that is how they are evaluated in constriant checks. | |
| return BinaryOperator::Create(SemaRef.Context, LHS.get(), RHS.get(), | |
| BinaryOperator::getOverloadedOpcode(Op), | |
| SemaRef.Context.BoolTy, VK_PRValue, | |
| OK_Ordinary, Loc, FPOptionsOverride{}); | |
| } | |
| }; | |
| } // namespace | |
| bool Sema::CheckConstraintExpression(const Expr *ConstraintExpression, | |
| Token NextToken, bool *PossibleNonPrimary, | |
| bool IsTrailingRequiresClause) { | |
| // C++2a [temp.constr.atomic]p1 | |
| // ..E shall be a constant expression of type bool. | |
| ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts(); | |
| if (LogicalBinOp BO = ConstraintExpression) { | |
| return CheckConstraintExpression(BO.getLHS(), NextToken, | |
| PossibleNonPrimary) && | |
| CheckConstraintExpression(BO.getRHS(), NextToken, | |
| PossibleNonPrimary); | |
| } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression)) | |
| return CheckConstraintExpression(C->getSubExpr(), NextToken, | |
| PossibleNonPrimary); | |
| QualType Type = ConstraintExpression->getType(); | |
| auto CheckForNonPrimary = [&] { | |
| if (!PossibleNonPrimary) | |
| return; | |
| *PossibleNonPrimary = | |
| // We have the following case: | |
| // template<typename> requires func(0) struct S { }; | |
| // The user probably isn't aware of the parentheses required around | |
| // the function call, and we're only going to parse 'func' as the | |
| // primary-expression, and complain that it is of non-bool type. | |
| // | |
| // However, if we're in a lambda, this might also be: | |
| // []<typename> requires var () {}; | |
| // Which also looks like a function call due to the lambda parentheses, | |
| // but unlike the first case, isn't an error, so this check is skipped. | |
| (NextToken.is(tok::l_paren) && | |
| (IsTrailingRequiresClause || | |
| (Type->isDependentType() && | |
| isa<UnresolvedLookupExpr>(ConstraintExpression) && | |
| !dyn_cast_if_present<LambdaScopeInfo>(getCurFunction())) || | |
| Type->isFunctionType() || | |
| Type->isSpecificBuiltinType(BuiltinType::Overload))) || | |
| // We have the following case: | |
| // template<typename T> requires size_<T> == 0 struct S { }; | |
| // The user probably isn't aware of the parentheses required around | |
| // the binary operator, and we're only going to parse 'func' as the | |
| // first operand, and complain that it is of non-bool type. | |
| getBinOpPrecedence(NextToken.getKind(), | |
| /*GreaterThanIsOperator=*/true, | |
| getLangOpts().CPlusPlus11) > prec::LogicalAnd; | |
| }; | |
| // An atomic constraint! | |
| if (ConstraintExpression->isTypeDependent()) { | |
| CheckForNonPrimary(); | |
| return true; | |
| } | |
| if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) { | |
| Diag(ConstraintExpression->getExprLoc(), | |
| diag::err_non_bool_atomic_constraint) | |
| << Type << ConstraintExpression->getSourceRange(); | |
| CheckForNonPrimary(); | |
| return false; | |
| } | |
| if (PossibleNonPrimary) | |
| *PossibleNonPrimary = false; | |
| return true; | |
| } | |
| namespace { | |
| struct SatisfactionStackRAII { | |
| Sema &SemaRef; | |
| bool Inserted = false; | |
| SatisfactionStackRAII(Sema &SemaRef, const NamedDecl *ND, | |
| const llvm::FoldingSetNodeID &FSNID) | |
| : SemaRef(SemaRef) { | |
| if (ND) { | |
| SemaRef.PushSatisfactionStackEntry(ND, FSNID); | |
| Inserted = true; | |
| } | |
| } | |
| ~SatisfactionStackRAII() { | |
| if (Inserted) | |
| SemaRef.PopSatisfactionStackEntry(); | |
| } | |
| }; | |
| } // namespace | |
| static bool DiagRecursiveConstraintEval( | |
| Sema &S, llvm::FoldingSetNodeID &ID, const NamedDecl *Templ, const Expr *E, | |
| const MultiLevelTemplateArgumentList *MLTAL = nullptr) { | |
| E->Profile(ID, S.Context, /*Canonical=*/true); | |
| if (MLTAL) { | |
| for (const auto &List : *MLTAL) | |
| for (const auto &TemplateArg : List.Args) | |
| S.Context.getCanonicalTemplateArgument(TemplateArg) | |
| .Profile(ID, S.Context); | |
| } | |
| if (S.SatisfactionStackContains(Templ, ID)) { | |
| S.Diag(E->getExprLoc(), diag::err_constraint_depends_on_self) | |
| << E << E->getSourceRange(); | |
| return true; | |
| } | |
| return false; | |
| } | |
| // Figure out the to-translation-unit depth for this function declaration for | |
| // the purpose of seeing if they differ by constraints. This isn't the same as | |
| // getTemplateDepth, because it includes already instantiated parents. | |
| static unsigned | |
| CalculateTemplateDepthForConstraints(Sema &S, const NamedDecl *ND, | |
| bool SkipForSpecialization = false) { | |
| MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs( | |
| ND, ND->getLexicalDeclContext(), /*Final=*/false, | |
| /*Innermost=*/std::nullopt, | |
| /*RelativeToPrimary=*/true, | |
| /*Pattern=*/nullptr, | |
| /*ForConstraintInstantiation=*/true, SkipForSpecialization); | |
| return MLTAL.getNumLevels(); | |
| } | |
| namespace { | |
| class AdjustConstraints : public TreeTransform<AdjustConstraints> { | |
| unsigned TemplateDepth = 0; | |
| bool RemoveNonPackExpansionPacks = false; | |
| public: | |
| using inherited = TreeTransform<AdjustConstraints>; | |
| AdjustConstraints(Sema &SemaRef, unsigned TemplateDepth, | |
| bool RemoveNonPackExpansionPacks = false) | |
| : inherited(SemaRef), TemplateDepth(TemplateDepth), | |
| RemoveNonPackExpansionPacks(RemoveNonPackExpansionPacks) {} | |
| ExprResult RebuildPackExpansion(Expr *Pattern, SourceLocation EllipsisLoc, | |
| UnsignedOrNone NumExpansions) { | |
| return inherited::RebuildPackExpansion(Pattern, EllipsisLoc, NumExpansions); | |
| } | |
| TemplateArgumentLoc RebuildPackExpansion(TemplateArgumentLoc Pattern, | |
| SourceLocation EllipsisLoc, | |
| UnsignedOrNone NumExpansions) { | |
| if (!RemoveNonPackExpansionPacks) | |
| return inherited::RebuildPackExpansion(Pattern, EllipsisLoc, | |
| NumExpansions); | |
| return Pattern; | |
| } | |
| bool PreparePackForExpansion(TemplateArgumentLoc In, bool Uneval, | |
| TemplateArgumentLoc &Out, UnexpandedInfo &Info) { | |
| if (!RemoveNonPackExpansionPacks) | |
| return inherited::PreparePackForExpansion(In, Uneval, Out, Info); | |
| assert(In.getArgument().isPackExpansion()); | |
| Out = In; | |
| Info.Expand = false; | |
| return false; | |
| } | |
| using inherited::TransformTemplateTypeParmType; | |
| QualType TransformTemplateTypeParmType(TypeLocBuilder &TLB, | |
| TemplateTypeParmTypeLoc TL, bool) { | |
| const TemplateTypeParmType *T = TL.getTypePtr(); | |
| TemplateTypeParmDecl *NewTTPDecl = nullptr; | |
| if (TemplateTypeParmDecl *OldTTPDecl = T->getDecl()) | |
| NewTTPDecl = cast_or_null<TemplateTypeParmDecl>( | |
| TransformDecl(TL.getNameLoc(), OldTTPDecl)); | |
| QualType Result = getSema().Context.getTemplateTypeParmType( | |
| T->getDepth() + TemplateDepth, T->getIndex(), | |
| RemoveNonPackExpansionPacks ? false : T->isParameterPack(), NewTTPDecl); | |
| TemplateTypeParmTypeLoc NewTL = TLB.push<TemplateTypeParmTypeLoc>(Result); | |
| NewTL.setNameLoc(TL.getNameLoc()); | |
| return Result; | |
| } | |
| QualType TransformPackIndexingType(TypeLocBuilder &TLB, | |
| PackIndexingTypeLoc TL) { | |
| llvm::SaveAndRestore _1(RemoveNonPackExpansionPacks, false); | |
| return inherited::TransformPackIndexingType(TLB, TL); | |
| } | |
| bool AlreadyTransformed(QualType T) { | |
| if (T.isNull()) | |
| return true; | |
| if (T->isInstantiationDependentType() || T->isVariablyModifiedType() || | |
| T->containsUnexpandedParameterPack()) | |
| return false; | |
| return true; | |
| } | |
| ExprResult TransformDeclRefExpr(DeclRefExpr *E) { | |
| NonTypeTemplateParmDecl *NTTP = | |
| dyn_cast<NonTypeTemplateParmDecl>(E->getDecl()); | |
| if (!NTTP) | |
| return inherited::TransformDeclRefExpr(E); | |
| assert(E->getTemplateArgs() == nullptr && | |
| "Template arguments for NTTP decl?"); | |
| auto *TSI = inherited::TransformType(NTTP->getTypeSourceInfo()); | |
| if (!TSI) | |
| return ExprError(); | |
| auto *D = NonTypeTemplateParmDecl::Create( | |
| SemaRef.getASTContext(), NTTP->getDeclContext(), | |
| NTTP->getInnerLocStart(), NTTP->getLocation(), | |
| NTTP->getDepth() + TemplateDepth, NTTP->getPosition(), | |
| NTTP->getIdentifier(), TSI->getType(), | |
| RemoveNonPackExpansionPacks ? false : NTTP->isParameterPack(), TSI); | |
| return DeclRefExpr::Create( | |
| SemaRef.getASTContext(), E->getQualifierLoc(), | |
| E->getTemplateKeywordLoc(), D, E->refersToEnclosingVariableOrCapture(), | |
| E->getNameInfo(), TSI->getType(), E->getValueKind(), | |
| RemoveNonPackExpansionPacks ? NTTP : D, | |
| /*TemplateArgs=*/nullptr, E->isNonOdrUse()); | |
| } | |
| }; | |
| } // namespace | |
| namespace { | |
| // FIXME: Convert it to DynamicRecursiveASTVisitor | |
| class HashParameterMapping : public RecursiveASTVisitor<HashParameterMapping> { | |
| using inherited = RecursiveASTVisitor<HashParameterMapping>; | |
| friend inherited; | |
| Sema &SemaRef; | |
| const MultiLevelTemplateArgumentList &TemplateArgs; | |
| llvm::FoldingSetNodeID &ID; | |
| llvm::SmallVector<TemplateArgument, 10> UsedTemplateArgs; | |
| UnsignedOrNone OuterPackSubstIndex; | |
| bool shouldVisitTemplateInstantiations() const { return true; } | |
| public: | |
| HashParameterMapping(Sema &SemaRef, | |
| const MultiLevelTemplateArgumentList &TemplateArgs, | |
| llvm::FoldingSetNodeID &ID, | |
| UnsignedOrNone OuterPackSubstIndex) | |
| : SemaRef(SemaRef), TemplateArgs(TemplateArgs), ID(ID), | |
| OuterPackSubstIndex(OuterPackSubstIndex) {} | |
| bool VisitTemplateTypeParmType(TemplateTypeParmType *T) { | |
| // A lambda expression can introduce template parameters that don't have | |
| // corresponding template arguments yet. | |
| if (T->getDepth() >= TemplateArgs.getNumLevels()) | |
| return true; | |
| // There might not be a corresponding template argument before substituting | |
| // into the parameter mapping, e.g. a sizeof... expression. | |
| if (!TemplateArgs.hasTemplateArgument(T->getDepth(), T->getIndex())) | |
| return true; | |
| TemplateArgument Arg = TemplateArgs(T->getDepth(), T->getIndex()); | |
| // In concept parameter mapping for fold expressions, packs that aren't | |
| // expanded in place are treated as having non-pack dependency, so that | |
| // a PackExpansionType won't prevent expanding the packs outside the | |
| // TreeTransform. However we still need to check the pack at this point. | |
| if ((T->isParameterPack() || | |
| (T->getDecl() && T->getDecl()->isTemplateParameterPack())) && | |
| SemaRef.ArgPackSubstIndex) { | |
| assert(Arg.getKind() == TemplateArgument::Pack && | |
| "Missing argument pack"); | |
| Arg = SemaRef.getPackSubstitutedTemplateArgument(Arg); | |
| } | |
| UsedTemplateArgs.push_back( | |
| SemaRef.Context.getCanonicalTemplateArgument(Arg)); | |
| return true; | |
| } | |
| bool VisitDeclRefExpr(DeclRefExpr *E) { | |
| NamedDecl *D = E->getDecl(); | |
| NonTypeTemplateParmDecl *NTTP = dyn_cast<NonTypeTemplateParmDecl>(D); | |
| if (!NTTP) | |
| return TraverseDecl(D); | |
| if (NTTP->getDepth() >= TemplateArgs.getNumLevels()) | |
| return true; | |
| if (!TemplateArgs.hasTemplateArgument(NTTP->getDepth(), NTTP->getIndex())) | |
| return true; | |
| TemplateArgument Arg = TemplateArgs(NTTP->getDepth(), NTTP->getPosition()); | |
| // In concept parameter mapping for fold expressions, packs that aren't | |
| // expanded in place are treated as having non-pack dependency, so that | |
| // a PackExpansionType won't prevent expanding the packs outside the | |
| // TreeTransform. However we still need to check the pack at this point. | |
| if ((NTTP->isParameterPack() || | |
| (E->getFoundDecl() && E->getFoundDecl() != E->getDecl() && | |
| E->getFoundDecl()->isParameterPack())) && | |
| SemaRef.ArgPackSubstIndex) { | |
| assert(Arg.getKind() == TemplateArgument::Pack && | |
| "Missing argument pack"); | |
| Arg = SemaRef.getPackSubstitutedTemplateArgument(Arg); | |
| } | |
| UsedTemplateArgs.push_back( | |
| SemaRef.Context.getCanonicalTemplateArgument(Arg)); | |
| return true; | |
| } | |
| bool VisitTypedefType(TypedefType *TT) { | |
| return inherited::TraverseType(TT->desugar()); | |
| } | |
| bool TraversePackIndexingType(PackIndexingType *T, bool TraverseQualifier) { | |
| { | |
| Sema::ArgPackSubstIndexRAII _(SemaRef, std::nullopt); | |
| if (!TraverseType(T->getPattern())) | |
| return false; | |
| } | |
| return TraverseStmt(T->getIndexExpr()); | |
| } | |
| bool TraverseDecl(Decl *D) { | |
| if (auto *VD = dyn_cast<ValueDecl>(D)) { | |
| if (auto *Var = dyn_cast<VarDecl>(VD)) | |
| TraverseStmt(Var->getInit()); | |
| return TraverseType(VD->getType()); | |
| } | |
| return inherited::TraverseDecl(D); | |
| } | |
| bool TraverseCallExpr(CallExpr *CE) { | |
| inherited::TraverseStmt(CE->getCallee()); | |
| for (Expr *Arg : CE->arguments()) | |
| inherited::TraverseStmt(Arg); | |
| return true; | |
| } | |
| bool TraverseCXXThisExpr(CXXThisExpr *E) { | |
| return inherited::TraverseType(E->getType()); | |
| } | |
| bool TraverseTypeLoc(TypeLoc TL, bool TraverseQualifier = true) { | |
| // We don't care about TypeLocs. So traverse Types instead. | |
| return TraverseType(TL.getType().getCanonicalType(), TraverseQualifier); | |
| } | |
| bool TraverseDependentNameType(const DependentNameType *T, | |
| bool /*TraverseQualifier*/) { | |
| return TraverseNestedNameSpecifier(T->getQualifier()); | |
| } | |
| bool TraverseTagType(const TagType *T, bool TraverseQualifier) { | |
| // T's parent can be dependent while T doesn't have any template arguments. | |
| // We should have already traversed its qualifier. | |
| // FIXME: Add an assert to catch cases where we failed to profile the | |
| // concept. | |
| return true; | |
| } | |
| bool TraverseUnresolvedUsingType(UnresolvedUsingType *T, | |
| bool TraverseQualifier) { | |
| // Sometimes the written type doesn't contain a qualifier which contains | |
| // necessary template arguments, whereas the declaration does. | |
| if (NestedNameSpecifier NNS = T->getDecl()->getQualifier(); | |
| TraverseQualifier && NNS) | |
| return inherited::TraverseNestedNameSpecifier(NNS); | |
| return inherited::TraverseUnresolvedUsingType(T, TraverseQualifier); | |
| } | |
| bool TraverseInjectedClassNameType(InjectedClassNameType *T, | |
| bool TraverseQualifier) { | |
| return TraverseTemplateArguments(T->getTemplateArgs(SemaRef.Context)); | |
| } | |
| bool TraverseTemplateArgument(const TemplateArgument &Arg) { | |
| if (!Arg.containsUnexpandedParameterPack() || Arg.isPackExpansion()) { | |
| // Act as if we are fully expanding this pack, if it is a PackExpansion. | |
| Sema::ArgPackSubstIndexRAII _1(SemaRef, std::nullopt); | |
| llvm::SaveAndRestore<UnsignedOrNone> _2(OuterPackSubstIndex, | |
| std::nullopt); | |
| return inherited::TraverseTemplateArgument(Arg); | |
| } | |
| Sema::ArgPackSubstIndexRAII _1(SemaRef, OuterPackSubstIndex); | |
| return inherited::TraverseTemplateArgument(Arg); | |
| } | |
| bool TraverseSizeOfPackExpr(SizeOfPackExpr *SOPE) { | |
| return TraverseDecl(SOPE->getPack()); | |
| } | |
| bool VisitSubstNonTypeTemplateParmExpr(SubstNonTypeTemplateParmExpr *E) { | |
| return inherited::TraverseStmt(E->getReplacement()); | |
| } | |
| bool TraverseTemplateName(TemplateName Template, | |
| bool TraverseQualifier = true) { | |
| if (auto *TTP = dyn_cast_if_present<TemplateTemplateParmDecl>( | |
| Template.getAsTemplateDecl()); | |
| TTP && TTP->getDepth() < TemplateArgs.getNumLevels()) { | |
| if (!TemplateArgs.hasTemplateArgument(TTP->getDepth(), | |
| TTP->getPosition())) | |
| return true; | |
| TemplateArgument Arg = TemplateArgs(TTP->getDepth(), TTP->getPosition()); | |
| if (TTP->isParameterPack() && SemaRef.ArgPackSubstIndex) { | |
| assert(Arg.getKind() == TemplateArgument::Pack && | |
| "Missing argument pack"); | |
| Arg = SemaRef.getPackSubstitutedTemplateArgument(Arg); | |
| } | |
| assert(!Arg.getAsTemplate().isNull() && | |
| "Null template template argument"); | |
| UsedTemplateArgs.push_back( | |
| SemaRef.Context.getCanonicalTemplateArgument(Arg)); | |
| } | |
| return inherited::TraverseTemplateName(Template, TraverseQualifier); | |
| } | |
| void VisitConstraint(const NormalizedConstraintWithParamMapping &Constraint) { | |
| switch (Constraint.getKind()) { | |
| case NormalizedConstraint::ConstraintKind::Atomic: | |
| ID.AddPointer(static_cast<const AtomicConstraint &>(Constraint) | |
| .getConstraintExpr()); | |
| ID.AddInteger(OuterPackSubstIndex.toInternalRepresentation()); | |
| break; | |
| case NormalizedConstraint::ConstraintKind::ConceptId: | |
| ID.AddPointer( | |
| static_cast<const ConceptIdConstraint &>(Constraint).getConceptId()); | |
| ID.AddInteger(OuterPackSubstIndex.toInternalRepresentation()); | |
| break; | |
| case NormalizedConstraint::ConstraintKind::FoldExpanded: | |
| ID.AddPointer( | |
| static_cast<const FoldExpandedConstraint &>(Constraint).getPattern()); | |
| break; | |
| case NormalizedConstraint::ConstraintKind::Compound: | |
| llvm_unreachable("Cannot hash a compound constraint"); | |
| } | |
| if (!Constraint.hasParameterMapping()) { | |
| for (const auto &List : TemplateArgs) | |
| for (const TemplateArgument &Arg : List.Args) | |
| SemaRef.Context.getCanonicalTemplateArgument(Arg).Profile( | |
| ID, SemaRef.Context); | |
| return; | |
| } | |
| llvm::ArrayRef<TemplateArgumentLoc> Mapping = | |
| Constraint.getParameterMapping(); | |
| for (auto &ArgLoc : Mapping) { | |
| TemplateArgument Canonical = | |
| SemaRef.Context.getCanonicalTemplateArgument(ArgLoc.getArgument()); | |
| // We don't want sugars to impede the profile of cache. | |
| UsedTemplateArgs.push_back(Canonical); | |
| TraverseTemplateArgument(Canonical); | |
| } | |
| for (auto &Used : UsedTemplateArgs) { | |
| llvm::FoldingSetNodeID R; | |
| Used.Profile(R, SemaRef.Context); | |
| ID.AddNodeID(R); | |
| } | |
| } | |
| }; | |
| } // namespace | |
| namespace clang { | |
| class ConstraintSatisfactionChecker { | |
| Sema &S; | |
| const NamedDecl *Template; | |
| const ConceptReference *TopLevelConceptId; | |
| SourceLocation TemplateNameLoc; | |
| UnsignedOrNone PackSubstitutionIndex; | |
| ConstraintSatisfaction &Satisfaction; | |
| bool BuildExpression; | |
| // The closest concept declaration when evaluating atomic constraints. | |
| ConceptDecl *ParentConcept = nullptr; | |
| // This is for TemplateInstantiator to not instantiate the same template | |
| // parameter mapping many times, in order to improve substitution performance. | |
| llvm::DenseMap<llvm::FoldingSetNodeID, TemplateArgumentLoc> | |
| CachedTemplateArgs; | |
| private: | |
| struct ParameterMappingInstantiationCache { | |
| llvm::FoldingSetNodeID ID; | |
| ConstraintSatisfactionChecker &Checker; | |
| HashParameterMapping H; | |
| unsigned PreviousDetailsSize; | |
| ParameterMappingInstantiationCache( | |
| ConstraintSatisfactionChecker &Checker, | |
| const NormalizedConstraintWithParamMapping &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL, UnsignedOrNone PackIndex, | |
| UnsignedOrNone PreviousDetailsSize = std::nullopt) | |
| : Checker(Checker), H(Checker.S, MLTAL, ID, PackIndex), | |
| PreviousDetailsSize(PreviousDetailsSize | |
| ? *PreviousDetailsSize | |
| : Checker.Satisfaction.Details.size()) { | |
| H.VisitConstraint(Constraint); | |
| } | |
| const UnsubstitutedConstraintSatisfactionCacheResult *available() { | |
| auto &Cache = Checker.S.UnsubstitutedConstraintSatisfactionCache; | |
| auto Iter = Cache.find(ID); | |
| if (Iter == Cache.end()) | |
| return nullptr; | |
| auto &Satisfaction = Checker.Satisfaction; | |
| auto &Cached = Iter->second.Satisfaction; | |
| Satisfaction.ContainsErrors = Cached.ContainsErrors; | |
| Satisfaction.IsSatisfied = Cached.IsSatisfied; | |
| Satisfaction.Details.insert(Satisfaction.Details.begin() + | |
| PreviousDetailsSize, | |
| Cached.Details.begin(), Cached.Details.end()); | |
| return &Iter->second; | |
| } | |
| ExprResult cache(ExprResult E) { | |
| UnsubstitutedConstraintSatisfactionCacheResult Cache; | |
| auto &Satisfaction = Checker.Satisfaction; | |
| Cache.Satisfaction.ContainsErrors = Satisfaction.ContainsErrors; | |
| Cache.Satisfaction.IsSatisfied = Satisfaction.IsSatisfied; | |
| Cache.Satisfaction.Details.insert(Cache.Satisfaction.Details.end(), | |
| Satisfaction.Details.begin() + | |
| PreviousDetailsSize, | |
| Satisfaction.Details.end()); | |
| Cache.SubstExpr = E; | |
| Checker.S.UnsubstitutedConstraintSatisfactionCache.insert( | |
| {ID, std::move(Cache)}); | |
| return E; | |
| } | |
| }; | |
| private: | |
| template <class Constraint> | |
| UnsignedOrNone getOuterPackIndex(const Constraint &C) const { | |
| return C.getPackSubstitutionIndex() ? C.getPackSubstitutionIndex() | |
| : PackSubstitutionIndex; | |
| } | |
| StringRef allocateStringFromConceptDiagnostic(const PartialDiagnostic &Diag) { | |
| SmallString<128> DiagString; | |
| DiagString = ": "; | |
| Diag.EmitToString(S.getDiagnostics(), DiagString); | |
| return S.getASTContext().backupStr(DiagString); | |
| } | |
| void consumeSFINAEFailure(TemplateDeductionInfo &Info, | |
| ConstraintSatisfaction &Satisfaction) { | |
| PartialDiagnosticAt SubstDiag{SourceLocation(), | |
| PartialDiagnostic::NullDiagnostic()}; | |
| Info.takeSFINAEDiagnostic(SubstDiag); | |
| // FIXME: This is an unfortunate consequence of there | |
| // being no serialization code for PartialDiagnostics and the fact | |
| // that serializing them would likely take a lot more storage than | |
| // just storing them as strings. We would still like, in the | |
| // future, to serialize the proper PartialDiagnostic as serializing | |
| // it as a string defeats the purpose of the diagnostic mechanism. | |
| Satisfaction.Details.emplace_back( | |
| new (S.Context) ConstraintSubstitutionDiagnostic{ | |
| SubstDiag.first, | |
| allocateStringFromConceptDiagnostic(SubstDiag.second)}); | |
| } | |
| ExprResult | |
| EvaluateAtomicConstraint(const Expr *AtomicExpr, | |
| const MultiLevelTemplateArgumentList &MLTAL); | |
| // XXX: It is SLOW! Use it very carefully. | |
| std::optional<MultiLevelTemplateArgumentList> SubstitutionInTemplateArguments( | |
| const NormalizedConstraintWithParamMapping &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL, | |
| llvm::SmallVector<TemplateArgument> &SubstitutedOuterMost); | |
| ExprResult EvaluateSlow(const AtomicConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL); | |
| ExprResult Evaluate(const AtomicConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL); | |
| ExprResult EvaluateSlow(const FoldExpandedConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL); | |
| ExprResult Evaluate(const FoldExpandedConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL); | |
| ExprResult EvaluateSlow(const ConceptIdConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL, | |
| unsigned int Size); | |
| ExprResult Evaluate(const ConceptIdConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL); | |
| ExprResult Evaluate(const CompoundConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL); | |
| public: | |
| ConstraintSatisfactionChecker(Sema &SemaRef, const NamedDecl *Template, | |
| const ConceptReference *TopLevelConceptId, | |
| SourceLocation TemplateNameLoc, | |
| UnsignedOrNone PackSubstitutionIndex, | |
| ConstraintSatisfaction &Satisfaction, | |
| bool BuildExpression) | |
| : S(SemaRef), Template(Template), TopLevelConceptId(TopLevelConceptId), | |
| TemplateNameLoc(TemplateNameLoc), | |
| PackSubstitutionIndex(PackSubstitutionIndex), | |
| Satisfaction(Satisfaction), BuildExpression(BuildExpression) {} | |
| ExprResult Evaluate(const NormalizedConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL); | |
| }; | |
| } // namespace clang | |
| ExprResult ConstraintSatisfactionChecker::EvaluateAtomicConstraint( | |
| const Expr *AtomicExpr, const MultiLevelTemplateArgumentList &MLTAL) { | |
| llvm::FoldingSetNodeID ID; | |
| if (Template && | |
| DiagRecursiveConstraintEval(S, ID, Template, AtomicExpr, &MLTAL)) { | |
| Satisfaction.IsSatisfied = false; | |
| Satisfaction.ContainsErrors = true; | |
| return ExprEmpty(); | |
| } | |
| SatisfactionStackRAII StackRAII(S, Template, ID); | |
| // Atomic constraint - substitute arguments and check satisfaction. | |
| ExprResult SubstitutedExpression = const_cast<Expr *>(AtomicExpr); | |
| { | |
| TemplateDeductionInfo Info(TemplateNameLoc); | |
| Sema::InstantiatingTemplate Inst( | |
| S, AtomicExpr->getBeginLoc(), | |
| Sema::InstantiatingTemplate::ConstraintSubstitution{}, | |
| // FIXME: improve const-correctness of InstantiatingTemplate | |
| const_cast<NamedDecl *>(Template), AtomicExpr->getSourceRange()); | |
| if (Inst.isInvalid()) | |
| return ExprError(); | |
| // We do not want error diagnostics escaping here. | |
| Sema::SFINAETrap Trap(S, Info); | |
| SubstitutedExpression = | |
| S.SubstConstraintExpr(const_cast<Expr *>(AtomicExpr), MLTAL); | |
| if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) { | |
| // C++2a [temp.constr.atomic]p1 | |
| // ...If substitution results in an invalid type or expression, the | |
| // constraint is not satisfied. | |
| if (!Trap.hasErrorOccurred()) | |
| // A non-SFINAE error has occurred as a result of this | |
| // substitution. | |
| return ExprError(); | |
| consumeSFINAEFailure(Info, Satisfaction); | |
| return ExprEmpty(); | |
| } | |
| } | |
| if (!S.CheckConstraintExpression(SubstitutedExpression.get())) | |
| return ExprError(); | |
| // [temp.constr.atomic]p3: To determine if an atomic constraint is | |
| // satisfied, the parameter mapping and template arguments are first | |
| // substituted into its expression. If substitution results in an | |
| // invalid type or expression, the constraint is not satisfied. | |
| // Otherwise, the lvalue-to-rvalue conversion is performed if necessary, | |
| // and E shall be a constant expression of type bool. | |
| // | |
| // Perform the L to R Value conversion if necessary. We do so for all | |
| // non-PRValue categories, else we fail to extend the lifetime of | |
| // temporaries, and that fails the constant expression check. | |
| if (!SubstitutedExpression.get()->isPRValue()) | |
| SubstitutedExpression = ImplicitCastExpr::Create( | |
| S.Context, SubstitutedExpression.get()->getType(), CK_LValueToRValue, | |
| SubstitutedExpression.get(), | |
| /*BasePath=*/nullptr, VK_PRValue, FPOptionsOverride()); | |
| return SubstitutedExpression; | |
| } | |
| std::optional<MultiLevelTemplateArgumentList> | |
| ConstraintSatisfactionChecker::SubstitutionInTemplateArguments( | |
| const NormalizedConstraintWithParamMapping &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL, | |
| llvm::SmallVector<TemplateArgument> &SubstitutedOutermost) { | |
| if (!Constraint.hasParameterMapping()) { | |
| if (MLTAL.getNumSubstitutedLevels()) | |
| SubstitutedOutermost.assign(MLTAL.getOutermost()); | |
| return MLTAL; | |
| } | |
| // The mapping is empty, meaning no template arguments are needed for | |
| // evaluation. | |
| if (Constraint.getParameterMapping().empty()) | |
| return MultiLevelTemplateArgumentList(); | |
| TemplateDeductionInfo Info(Constraint.getBeginLoc()); | |
| Sema::SFINAETrap Trap(S, Info); | |
| Sema::InstantiatingTemplate Inst( | |
| S, Constraint.getBeginLoc(), | |
| Sema::InstantiatingTemplate::ConstraintSubstitution{}, | |
| // FIXME: improve const-correctness of InstantiatingTemplate | |
| const_cast<NamedDecl *>(Template), Constraint.getSourceRange()); | |
| if (Inst.isInvalid()) | |
| return std::nullopt; | |
| TemplateArgumentListInfo SubstArgs; | |
| Sema::ArgPackSubstIndexRAII SubstIndex(S, getOuterPackIndex(Constraint)); | |
| llvm::SaveAndRestore PushTemplateArgsCache(S.CurrentCachedTemplateArgs, | |
| &CachedTemplateArgs); | |
| // We don't want the template argument substitution into parameter | |
| // mappings to preserve the outer depths. | |
| if (S.SubstTemplateArgumentsInParameterMapping( | |
| Constraint.getParameterMapping(), Constraint.getBeginLoc(), MLTAL, | |
| SubstArgs)) { | |
| Satisfaction.IsSatisfied = false; | |
| if (Trap.hasErrorOccurred()) | |
| consumeSFINAEFailure(Info, Satisfaction); | |
| return std::nullopt; | |
| } | |
| Sema::CheckTemplateArgumentInfo CTAI; | |
| auto *TD = const_cast<TemplateDecl *>( | |
| cast<TemplateDecl>(Constraint.getConstraintDecl())); | |
| if (S.CheckTemplateArgumentList(TD, Constraint.getUsedTemplateParamList(), | |
| TD->getLocation(), SubstArgs, | |
| /*DefaultArguments=*/{}, | |
| /*PartialTemplateArgs=*/false, CTAI)) | |
| return std::nullopt; | |
| const NormalizedConstraint::OccurenceList &Used = | |
| Constraint.mappingOccurenceList(); | |
| // The empty MLTAL situation should only occur when evaluating non-dependent | |
| // constraints. | |
| if (MLTAL.getNumSubstitutedLevels()) | |
| SubstitutedOutermost = | |
| llvm::to_vector_of<TemplateArgument>(MLTAL.getOutermost()); | |
| unsigned Offset = 0; | |
| for (unsigned I = 0, MappedIndex = 0; I < Used.size(); I++) { | |
| TemplateArgument Arg; | |
| if (Used[I]) | |
| Arg = S.Context.getCanonicalTemplateArgument( | |
| CTAI.SugaredConverted[MappedIndex++]); | |
| if (I < SubstitutedOutermost.size()) { | |
| SubstitutedOutermost[I] = Arg; | |
| Offset = I + 1; | |
| } else { | |
| SubstitutedOutermost.push_back(Arg); | |
| Offset = SubstitutedOutermost.size(); | |
| } | |
| } | |
| if (Offset < SubstitutedOutermost.size()) | |
| SubstitutedOutermost.erase(SubstitutedOutermost.begin() + Offset); | |
| MultiLevelTemplateArgumentList SubstitutedTemplateArgs; | |
| SubstitutedTemplateArgs.addOuterTemplateArguments(TD, SubstitutedOutermost, | |
| /*Final=*/false); | |
| return std::move(SubstitutedTemplateArgs); | |
| } | |
| ExprResult ConstraintSatisfactionChecker::EvaluateSlow( | |
| const AtomicConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL) { | |
| std::optional<EnterExpressionEvaluationContext> EvaluationContext; | |
| // The ConceptDecl as a ContextDecl ensures that, when evaluating constraints | |
| // on transformed lambdas, we don't have extra outer template arguments. | |
| if (ParentConcept) | |
| EvaluationContext.emplace( | |
| S, Sema::ExpressionEvaluationContext::ConstantEvaluated, ParentConcept); | |
| else | |
| EvaluationContext.emplace( | |
| S, Sema::ExpressionEvaluationContext::ConstantEvaluated, | |
| Sema::ReuseLambdaContextDecl); | |
| llvm::SmallVector<TemplateArgument> SubstitutedOutermost; | |
| std::optional<MultiLevelTemplateArgumentList> SubstitutedArgs = | |
| SubstitutionInTemplateArguments(Constraint, MLTAL, SubstitutedOutermost); | |
| if (!SubstitutedArgs) { | |
| Satisfaction.IsSatisfied = false; | |
| return ExprError(); | |
| } | |
| // Make sure that concepts are not evaluated in the context they are used, | |
| // i.e they should not have access to the current class object or its | |
| // non-public members. | |
| std::optional<Sema::ContextRAII> ConceptContext; | |
| if (ParentConcept) | |
| ConceptContext.emplace(S, ParentConcept->getDeclContext()); | |
| Sema::ArgPackSubstIndexRAII SubstIndex(S, PackSubstitutionIndex); | |
| ExprResult SubstitutedAtomicExpr = EvaluateAtomicConstraint( | |
| Constraint.getConstraintExpr(), *SubstitutedArgs); | |
| if (SubstitutedAtomicExpr.isInvalid()) | |
| return ExprError(); | |
| if (SubstitutedAtomicExpr.isUnset()) | |
| // Evaluator has decided satisfaction without yielding an expression. | |
| return ExprEmpty(); | |
| // We don't have the ability to evaluate this, since it contains a | |
| // RecoveryExpr, so we want to fail overload resolution. Otherwise, | |
| // we'd potentially pick up a different overload, and cause confusing | |
| // diagnostics. SO, add a failure detail that will cause us to make this | |
| // overload set not viable. | |
| if (SubstitutedAtomicExpr.get()->containsErrors()) { | |
| Satisfaction.IsSatisfied = false; | |
| Satisfaction.ContainsErrors = true; | |
| PartialDiagnostic Msg = S.PDiag(diag::note_constraint_references_error); | |
| Satisfaction.Details.emplace_back( | |
| new (S.Context) ConstraintSubstitutionDiagnostic{ | |
| SubstitutedAtomicExpr.get()->getBeginLoc(), | |
| allocateStringFromConceptDiagnostic(Msg)}); | |
| return SubstitutedAtomicExpr; | |
| } | |
| if (SubstitutedAtomicExpr.get()->isValueDependent()) { | |
| Satisfaction.IsSatisfied = true; | |
| Satisfaction.ContainsErrors = false; | |
| return SubstitutedAtomicExpr; | |
| } | |
| SmallVector<PartialDiagnosticAt, 2> EvaluationDiags; | |
| Expr::EvalResult EvalResult; | |
| EvalResult.Diag = &EvaluationDiags; | |
| if (!SubstitutedAtomicExpr.get()->EvaluateAsConstantExpr(EvalResult, | |
| S.Context) || | |
| !EvaluationDiags.empty()) { | |
| // C++2a [temp.constr.atomic]p1 | |
| // ...E shall be a constant expression of type bool. | |
| S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(), | |
| diag::err_non_constant_constraint_expression) | |
| << SubstitutedAtomicExpr.get()->getSourceRange(); | |
| for (const PartialDiagnosticAt &PDiag : EvaluationDiags) | |
| S.Diag(PDiag.first, PDiag.second); | |
| return ExprError(); | |
| } | |
| assert(EvalResult.Val.isInt() && | |
| "evaluating bool expression didn't produce int"); | |
| Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue(); | |
| if (!Satisfaction.IsSatisfied) | |
| Satisfaction.Details.emplace_back(SubstitutedAtomicExpr.get()); | |
| return SubstitutedAtomicExpr; | |
| } | |
| ExprResult ConstraintSatisfactionChecker::Evaluate( | |
| const AtomicConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL) { | |
| ParameterMappingInstantiationCache PMCache(*this, Constraint, MLTAL, | |
| getOuterPackIndex(Constraint)); | |
| if (auto *V = PMCache.available()) | |
| return V->SubstExpr; | |
| return PMCache.cache(EvaluateSlow(Constraint, MLTAL)); | |
| } | |
| ExprResult ConstraintSatisfactionChecker::EvaluateSlow( | |
| const FoldExpandedConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL) { | |
| bool Conjunction = Constraint.getFoldOperator() == | |
| FoldExpandedConstraint::FoldOperatorKind::And; | |
| unsigned EffectiveDetailEndIndex = Satisfaction.Details.size(); | |
| llvm::SmallVector<TemplateArgument> SubstitutedOutermost; | |
| // FIXME: Is PackSubstitutionIndex correct? | |
| llvm::SaveAndRestore _(PackSubstitutionIndex, S.ArgPackSubstIndex); | |
| std::optional<MultiLevelTemplateArgumentList> SubstitutedArgs = | |
| SubstitutionInTemplateArguments( | |
| static_cast<const NormalizedConstraintWithParamMapping &>(Constraint), | |
| MLTAL, SubstitutedOutermost); | |
| if (!SubstitutedArgs) { | |
| Satisfaction.IsSatisfied = false; | |
| return ExprError(); | |
| } | |
| UnsignedOrNone NumExpansions(std::nullopt); | |
| { | |
| Sema::InstantiatingTemplate InstTemplate( | |
| S, TemplateNameLoc, | |
| Sema::InstantiatingTemplate::ConstraintSubstitution{}, | |
| const_cast<NamedDecl *>(Template), Constraint.getSourceRange()); | |
| NumExpansions = S.EvaluateFoldExpandedConstraintSize( | |
| Constraint.getPattern(), *SubstitutedArgs); | |
| } | |
| if (!NumExpansions) | |
| return ExprEmpty(); | |
| if (*NumExpansions == 0) { | |
| Satisfaction.IsSatisfied = Conjunction; | |
| return ExprEmpty(); | |
| } | |
| ExprResult Out; | |
| for (unsigned I = 0; I < *NumExpansions; I++) { | |
| Sema::ArgPackSubstIndexRAII SubstIndex(S, I); | |
| Satisfaction.IsSatisfied = false; | |
| Satisfaction.ContainsErrors = false; | |
| ExprResult Expr = | |
| ConstraintSatisfactionChecker(S, Template, TopLevelConceptId, | |
| TemplateNameLoc, UnsignedOrNone(I), | |
| Satisfaction, | |
| /*BuildExpression=*/false) | |
| .Evaluate(Constraint.getNormalizedPattern(), *SubstitutedArgs); | |
| if (BuildExpression) { | |
| if (Out.isUnset() || !Expr.isUsable()) | |
| Out = Expr; | |
| else | |
| Out = BinaryOperator::Create(S.Context, Out.get(), Expr.get(), | |
| Conjunction ? BinaryOperatorKind::BO_LAnd | |
| : BinaryOperatorKind::BO_LOr, | |
| S.Context.BoolTy, VK_PRValue, OK_Ordinary, | |
| Constraint.getBeginLoc(), | |
| FPOptionsOverride{}); | |
| } | |
| if (!Conjunction && Satisfaction.IsSatisfied) { | |
| Satisfaction.Details.erase(Satisfaction.Details.begin() + | |
| EffectiveDetailEndIndex, | |
| Satisfaction.Details.end()); | |
| break; | |
| } | |
| if (Satisfaction.IsSatisfied != Conjunction) | |
| return Out; | |
| } | |
| return Out; | |
| } | |
| ExprResult ConstraintSatisfactionChecker::Evaluate( | |
| const FoldExpandedConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL) { | |
| ParameterMappingInstantiationCache PMCache(*this, Constraint, MLTAL, | |
| /*PackIndex=*/std::nullopt); | |
| if (auto *V = PMCache.available()) | |
| return V->SubstExpr; | |
| return PMCache.cache(EvaluateSlow(Constraint, MLTAL)); | |
| } | |
| ExprResult ConstraintSatisfactionChecker::EvaluateSlow( | |
| const ConceptIdConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL, unsigned Size) { | |
| const ConceptReference *ConceptId = Constraint.getConceptId(); | |
| llvm::SmallVector<TemplateArgument> SubstitutedOutermost; | |
| std::optional<MultiLevelTemplateArgumentList> SubstitutedArgs = | |
| SubstitutionInTemplateArguments(Constraint, MLTAL, SubstitutedOutermost); | |
| if (!SubstitutedArgs) { | |
| Satisfaction.IsSatisfied = false; | |
| return ExprError(); | |
| } | |
| Sema::ArgPackSubstIndexRAII SubstIndex(S, getOuterPackIndex(Constraint)); | |
| const ASTTemplateArgumentListInfo *Ori = | |
| ConceptId->getTemplateArgsAsWritten(); | |
| TemplateDeductionInfo Info(TemplateNameLoc); | |
| Sema::SFINAETrap Trap(S, Info); | |
| Sema::InstantiatingTemplate _2( | |
| S, TemplateNameLoc, Sema::InstantiatingTemplate::ConstraintSubstitution{}, | |
| const_cast<NamedDecl *>(Template), Constraint.getSourceRange()); | |
| TemplateArgumentListInfo OutArgs(Ori->LAngleLoc, Ori->RAngleLoc); | |
| // There's a concern that even with the same concept, they may not have the | |
| // same ConceptReference, if they come from modules. | |
| if (TopLevelConceptId && | |
| ConceptId->getNamedConcept().getAsTemplateDecl() == | |
| TopLevelConceptId->getNamedConcept().getAsTemplateDecl()) { | |
| for (auto &A : Ori->arguments()) | |
| OutArgs.addArgument(A); | |
| } else if (S.SubstTemplateArguments(Ori->arguments(), *SubstitutedArgs, | |
| OutArgs) || | |
| Trap.hasErrorOccurred()) { | |
| Satisfaction.IsSatisfied = false; | |
| if (Trap.hasErrorOccurred()) | |
| consumeSFINAEFailure(Info, Satisfaction); | |
| return ExprError(); | |
| } | |
| CXXScopeSpec SS; | |
| SS.Adopt(ConceptId->getNestedNameSpecifierLoc()); | |
| ExprResult SubstitutedConceptId = S.CheckConceptTemplateId( | |
| SS, ConceptId->getTemplateKWLoc(), ConceptId->getConceptNameInfo(), | |
| ConceptId->getFoundDecl(), | |
| ConceptId->getNamedConcept().getAsTemplateDecl(), &OutArgs, | |
| /*DoCheckConstraintSatisfaction=*/false); | |
| if (SubstitutedConceptId.isInvalid() || Trap.hasErrorOccurred()) | |
| return ExprError(); | |
| if (Size != Satisfaction.Details.size()) { | |
| Satisfaction.Details.insert( | |
| Satisfaction.Details.begin() + Size, | |
| UnsatisfiedConstraintRecord( | |
| SubstitutedConceptId.getAs<ConceptSpecializationExpr>() | |
| ->getConceptReference())); | |
| } | |
| return SubstitutedConceptId; | |
| } | |
| ExprResult ConstraintSatisfactionChecker::Evaluate( | |
| const ConceptIdConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL) { | |
| const ConceptReference *ConceptId = Constraint.getConceptId(); | |
| Sema::InstantiatingTemplate InstTemplate( | |
| S, ConceptId->getBeginLoc(), | |
| Sema::InstantiatingTemplate::ConstraintsCheck{}, | |
| ConceptId->getNamedConcept().getAsTemplateDecl(), | |
| // We may have empty template arguments when checking non-dependent | |
| // nested constraint expressions. | |
| // In such cases, non-SFINAE errors would have already been diagnosed | |
| // during parameter mapping substitution, so the instantiating template | |
| // arguments are less useful here. | |
| MLTAL.getNumSubstitutedLevels() ? MLTAL.getInnermost() | |
| : ArrayRef<TemplateArgument>{}, | |
| Constraint.getSourceRange()); | |
| if (InstTemplate.isInvalid()) | |
| return ExprError(); | |
| unsigned Size = Satisfaction.Details.size(); | |
| llvm::SaveAndRestore PushConceptDecl( | |
| ParentConcept, | |
| cast<ConceptDecl>(ConceptId->getNamedConcept().getAsTemplateDecl())); | |
| ExprResult E = Evaluate(Constraint.getNormalizedConstraint(), MLTAL); | |
| if (E.isInvalid()) { | |
| Satisfaction.Details.insert(Satisfaction.Details.begin() + Size, ConceptId); | |
| return E; | |
| } | |
| // ConceptIdConstraint is only relevant for diagnostics, | |
| // so if the normalized constraint is satisfied, we should not | |
| // substitute into the constraint. | |
| if (Satisfaction.IsSatisfied) | |
| return E; | |
| ParameterMappingInstantiationCache PMCache( | |
| *this, Constraint, MLTAL, getOuterPackIndex(Constraint), Size); | |
| if (auto *V = PMCache.available()) | |
| return V->SubstExpr; | |
| return PMCache.cache(EvaluateSlow(Constraint, MLTAL, Size)); | |
| } | |
| ExprResult ConstraintSatisfactionChecker::Evaluate( | |
| const CompoundConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL) { | |
| unsigned EffectiveDetailEndIndex = Satisfaction.Details.size(); | |
| bool Conjunction = | |
| Constraint.getCompoundKind() == NormalizedConstraint::CCK_Conjunction; | |
| ExprResult LHS = Evaluate(Constraint.getLHS(), MLTAL); | |
| if (Conjunction && (!Satisfaction.IsSatisfied || Satisfaction.ContainsErrors)) | |
| return LHS; | |
| if (!Conjunction && !LHS.isInvalid() && Satisfaction.IsSatisfied && | |
| !Satisfaction.ContainsErrors) | |
| return LHS; | |
| Satisfaction.ContainsErrors = false; | |
| Satisfaction.IsSatisfied = false; | |
| ExprResult RHS = Evaluate(Constraint.getRHS(), MLTAL); | |
| if (!Conjunction && !RHS.isInvalid() && Satisfaction.IsSatisfied && | |
| !Satisfaction.ContainsErrors) | |
| Satisfaction.Details.erase(Satisfaction.Details.begin() + | |
| EffectiveDetailEndIndex, | |
| Satisfaction.Details.end()); | |
| if (!BuildExpression) | |
| return Satisfaction.ContainsErrors ? ExprError() : ExprEmpty(); | |
| if (!LHS.isUsable()) | |
| return RHS; | |
| if (!RHS.isUsable()) | |
| return LHS; | |
| return BinaryOperator::Create(S.Context, LHS.get(), RHS.get(), | |
| Conjunction ? BinaryOperatorKind::BO_LAnd | |
| : BinaryOperatorKind::BO_LOr, | |
| S.Context.BoolTy, VK_PRValue, OK_Ordinary, | |
| Constraint.getBeginLoc(), FPOptionsOverride{}); | |
| } | |
| ExprResult ConstraintSatisfactionChecker::Evaluate( | |
| const NormalizedConstraint &Constraint, | |
| const MultiLevelTemplateArgumentList &MLTAL) { | |
| switch (Constraint.getKind()) { | |
| case NormalizedConstraint::ConstraintKind::Atomic: | |
| return Evaluate(static_cast<const AtomicConstraint &>(Constraint), MLTAL); | |
| case NormalizedConstraint::ConstraintKind::FoldExpanded: | |
| return Evaluate(static_cast<const FoldExpandedConstraint &>(Constraint), | |
| MLTAL); | |
| case NormalizedConstraint::ConstraintKind::ConceptId: | |
| return Evaluate(static_cast<const ConceptIdConstraint &>(Constraint), | |
| MLTAL); | |
| case NormalizedConstraint::ConstraintKind::Compound: | |
| return Evaluate(static_cast<const CompoundConstraint &>(Constraint), MLTAL); | |
| } | |
| llvm_unreachable("Unknown ConstraintKind enum"); | |
| } | |
| static bool CheckConstraintSatisfaction( | |
| Sema &S, const NamedDecl *Template, | |
| ArrayRef<AssociatedConstraint> AssociatedConstraints, | |
| const MultiLevelTemplateArgumentList &TemplateArgsLists, | |
| SourceRange TemplateIDRange, ConstraintSatisfaction &Satisfaction, | |
| Expr **ConvertedExpr, const ConceptReference *TopLevelConceptId = nullptr) { | |
| if (ConvertedExpr) | |
| *ConvertedExpr = nullptr; | |
| if (AssociatedConstraints.empty()) { | |
| Satisfaction.IsSatisfied = true; | |
| return false; | |
| } | |
| // In the general case, we can't check satisfaction if the arguments contain | |
| // unsubstituted template parameters, even if they are purely syntactic, | |
| // because they may still turn out to be invalid after substitution. | |
| // This could be permitted in cases where this substitution will still be | |
| // attempted later and diagnosed, such as function template specializations, | |
| // but that's not the case for concept specializations. | |
| if (TemplateArgsLists.isAnyArgInstantiationDependent()) { | |
| Satisfaction.IsSatisfied = true; | |
| return false; | |
| } | |
| llvm::ArrayRef<TemplateArgument> Args; | |
| if (TemplateArgsLists.getNumLevels() != 0) | |
| Args = TemplateArgsLists.getInnermost(); | |
| struct SynthesisContextPair { | |
| Sema::InstantiatingTemplate Inst; | |
| Sema::NonSFINAEContext NSC; | |
| SynthesisContextPair(Sema &S, NamedDecl *Template, | |
| ArrayRef<TemplateArgument> TemplateArgs, | |
| SourceRange InstantiationRange) | |
| : Inst(S, InstantiationRange.getBegin(), | |
| Sema::InstantiatingTemplate::ConstraintsCheck{}, Template, | |
| TemplateArgs, InstantiationRange), | |
| NSC(S) {} | |
| }; | |
| std::optional<SynthesisContextPair> SynthesisContext; | |
| if (!TopLevelConceptId) | |
| SynthesisContext.emplace(S, const_cast<NamedDecl *>(Template), Args, | |
| TemplateIDRange); | |
| const NormalizedConstraint *C = | |
| S.getNormalizedAssociatedConstraints(Template, AssociatedConstraints); | |
| if (!C) { | |
| Satisfaction.IsSatisfied = false; | |
| return true; | |
| } | |
| if (TopLevelConceptId) | |
| C = ConceptIdConstraint::Create(S.getASTContext(), TopLevelConceptId, | |
| const_cast<NormalizedConstraint *>(C), | |
| Template, /*CSE=*/nullptr, | |
| S.ArgPackSubstIndex); | |
| ExprResult Res = | |
| ConstraintSatisfactionChecker( | |
| S, Template, TopLevelConceptId, TemplateIDRange.getBegin(), | |
| S.ArgPackSubstIndex, Satisfaction, | |
| /*BuildExpression=*/ConvertedExpr != nullptr) | |
| .Evaluate(*C, TemplateArgsLists); | |
| if (Res.isUsable() && ConvertedExpr) | |
| *ConvertedExpr = Res.get(); | |
| return false; | |
| } | |
| bool Sema::CheckConstraintSatisfaction( | |
| ConstrainedDeclOrNestedRequirement Entity, | |
| ArrayRef<AssociatedConstraint> AssociatedConstraints, | |
| const MultiLevelTemplateArgumentList &TemplateArgsLists, | |
| SourceRange TemplateIDRange, ConstraintSatisfaction &OutSatisfaction, | |
| const ConceptReference *TopLevelConceptId, Expr **ConvertedExpr) { | |
| llvm::TimeTraceScope TimeScope( | |
| "CheckConstraintSatisfaction", [TemplateIDRange, this] { | |
| return TemplateIDRange.printToString(getSourceManager()); | |
| }); | |
| if (AssociatedConstraints.empty()) { | |
| OutSatisfaction.IsSatisfied = true; | |
| return false; | |
| } | |
| const auto *Template = dyn_cast_if_present<const NamedDecl *>(Entity); | |
| if (!Template) { | |
| return ::CheckConstraintSatisfaction( | |
| *this, nullptr, AssociatedConstraints, TemplateArgsLists, | |
| TemplateIDRange, OutSatisfaction, ConvertedExpr, TopLevelConceptId); | |
| } | |
| // Invalid templates could make their way here. Substituting them could result | |
| // in dependent expressions. | |
| if (Template->isInvalidDecl()) { | |
| OutSatisfaction.IsSatisfied = false; | |
| return true; | |
| } | |
| // A list of the template argument list flattened in a predictible manner for | |
| // the purposes of caching. The ConstraintSatisfaction type is in AST so it | |
| // has no access to the MultiLevelTemplateArgumentList, so this has to happen | |
| // here. | |
| llvm::SmallVector<TemplateArgument, 4> FlattenedArgs; | |
| for (auto List : TemplateArgsLists) | |
| for (const TemplateArgument &Arg : List.Args) | |
| FlattenedArgs.emplace_back(Context.getCanonicalTemplateArgument(Arg)); | |
| const NamedDecl *Owner = Template; | |
| if (TopLevelConceptId) | |
| Owner = TopLevelConceptId->getNamedConcept().getAsTemplateDecl(); | |
| llvm::FoldingSetNodeID ID; | |
| ConstraintSatisfaction::Profile(ID, Context, Owner, FlattenedArgs); | |
| llvm::FoldingSetInsertToken Token; | |
| if (auto *Cached = SatisfactionCache.lookup(ID, Token)) { | |
| OutSatisfaction = *Cached; | |
| return false; | |
| } | |
| auto Satisfaction = | |
| std::make_unique<ConstraintSatisfaction>(Owner, FlattenedArgs); | |
| if (::CheckConstraintSatisfaction( | |
| *this, Template, AssociatedConstraints, TemplateArgsLists, | |
| TemplateIDRange, *Satisfaction, ConvertedExpr, TopLevelConceptId)) { | |
| OutSatisfaction = std::move(*Satisfaction); | |
| return true; | |
| } | |
| if (auto *Cached = SatisfactionCache.lookup(ID, Token)) { | |
| // The evaluation of this constraint resulted in us trying to re-evaluate it | |
| // recursively. This isn't really possible, except we try to form a | |
| // RecoveryExpr as a part of the evaluation. If this is the case, just | |
| // return the 'cached' version (which will have the same result), and save | |
| // ourselves the extra-insert. If it ever becomes possible to legitimately | |
| // recursively check a constraint, we should skip checking the 'inner' one | |
| // above, and replace the cached version with this one, as it would be more | |
| // specific. | |
| OutSatisfaction = *Cached; | |
| return false; | |
| } | |
| // Else we can simply add this satisfaction to the list. | |
| OutSatisfaction = *Satisfaction; | |
| // Note that entries of SatisfactionCache are deleted in Sema's destructor. | |
| SatisfactionCache.insert(Satisfaction.release()); | |
| return false; | |
| } | |
| static ExprResult | |
| SubstituteConceptsInConstraintExpression(Sema &S, const NamedDecl *D, | |
| const ConceptSpecializationExpr *CSE, | |
| UnsignedOrNone SubstIndex) { | |
| Sema::SFINAETrap Trap(S); | |
| // [C++2c] [temp.constr.normal] | |
| // Otherwise, to form CE, any non-dependent concept template argument Ai | |
| // is substituted into the constraint-expression of C. | |
| // If any such substitution results in an invalid concept-id, | |
| // the program is ill-formed; no diagnostic is required. | |
| ConceptDecl *Concept = CSE->getConceptDecl()->getCanonicalDecl(); | |
| Sema::ArgPackSubstIndexRAII _(S, SubstIndex); | |
| const ASTTemplateArgumentListInfo *ArgsAsWritten = | |
| CSE->getTemplateArgsAsWritten(); | |
| if (llvm::none_of( | |
| ArgsAsWritten->arguments(), [&](const TemplateArgumentLoc &ArgLoc) { | |
| return !ArgLoc.getArgument().isDependent() && | |
| ArgLoc.getArgument().isConceptOrConceptTemplateParameter(); | |
| })) { | |
| return Concept->getConstraintExpr(); | |
| } | |
| MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs( | |
| Concept, Concept->getLexicalDeclContext(), | |
| /*Final=*/false, CSE->getTemplateArguments(), | |
| /*RelativeToPrimary=*/true, | |
| /*Pattern=*/nullptr, | |
| /*ForConstraintInstantiation=*/true); | |
| return S.SubstConceptTemplateArguments(CSE, Concept->getConstraintExpr(), | |
| MLTAL); | |
| } | |
| bool Sema::SetupConstraintScope( | |
| FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs, | |
| const MultiLevelTemplateArgumentList &MLTAL, | |
| LocalInstantiationScope &Scope) { | |
| assert(!isLambdaCallOperator(FD) && | |
| "Use LambdaScopeForCallOperatorInstantiationRAII to handle lambda " | |
| "instantiations"); | |
| if (FD->isTemplateInstantiation() && FD->getPrimaryTemplate()) { | |
| FunctionTemplateDecl *PrimaryTemplate = FD->getPrimaryTemplate(); | |
| InstantiatingTemplate Inst( | |
| *this, FD->getPointOfInstantiation(), | |
| Sema::InstantiatingTemplate::ConstraintsCheck{}, PrimaryTemplate, | |
| TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{}, | |
| SourceRange()); | |
| if (Inst.isInvalid()) | |
| return true; | |
| // addInstantiatedParametersToScope creates a map of 'uninstantiated' to | |
| // 'instantiated' parameters and adds it to the context. For the case where | |
| // this function is a template being instantiated NOW, we also need to add | |
| // the list of current template arguments to the list so that they also can | |
| // be picked out of the map. | |
| if (auto *SpecArgs = FD->getTemplateSpecializationArgs()) { | |
| MultiLevelTemplateArgumentList JustTemplArgs(FD, SpecArgs->asArray(), | |
| /*Final=*/false); | |
| if (addInstantiatedParametersToScope( | |
| FD, PrimaryTemplate->getTemplatedDecl(), Scope, JustTemplArgs)) | |
| return true; | |
| } | |
| // If this is a member function, make sure we get the parameters that | |
| // reference the original primary template. | |
| if (FunctionTemplateDecl *FromMemTempl = | |
| PrimaryTemplate->getInstantiatedFromMemberTemplate()) { | |
| if (addInstantiatedParametersToScope(FD, FromMemTempl->getTemplatedDecl(), | |
| Scope, MLTAL)) | |
| return true; | |
| } | |
| return false; | |
| } | |
| if (FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization || | |
| FD->getTemplatedKind() == FunctionDecl::TK_DependentNonTemplate) { | |
| FunctionDecl *InstantiatedFrom = | |
| FD->getTemplatedKind() == FunctionDecl::TK_MemberSpecialization | |
| ? FD->getInstantiatedFromMemberFunction() | |
| : FD->getInstantiatedFromDecl(); | |
| InstantiatingTemplate Inst( | |
| *this, FD->getPointOfInstantiation(), | |
| Sema::InstantiatingTemplate::ConstraintsCheck{}, InstantiatedFrom, | |
| TemplateArgs ? *TemplateArgs : ArrayRef<TemplateArgument>{}, | |
| SourceRange()); | |
| if (Inst.isInvalid()) | |
| return true; | |
| // Case where this was not a template, but instantiated as a | |
| // child-function. | |
| if (addInstantiatedParametersToScope(FD, InstantiatedFrom, Scope, MLTAL)) | |
| return true; | |
| } | |
| return false; | |
| } | |
| // This function collects all of the template arguments for the purposes of | |
| // constraint-instantiation and checking. | |
| std::optional<MultiLevelTemplateArgumentList> | |
| Sema::SetupConstraintCheckingTemplateArgumentsAndScope( | |
| FunctionDecl *FD, std::optional<ArrayRef<TemplateArgument>> TemplateArgs, | |
| LocalInstantiationScope &Scope) { | |
| MultiLevelTemplateArgumentList MLTAL; | |
| // Collect the list of template arguments relative to the 'primary' template. | |
| // We need the entire list, since the constraint is completely uninstantiated | |
| // at this point. | |
| MLTAL = | |
| getTemplateInstantiationArgs(FD, FD->getLexicalDeclContext(), | |
| /*Final=*/false, /*Innermost=*/std::nullopt, | |
| /*RelativeToPrimary=*/true, | |
| /*Pattern=*/nullptr, | |
| /*ForConstraintInstantiation=*/true); | |
| // Lambdas are handled by LambdaScopeForCallOperatorInstantiationRAII. | |
| if (isLambdaCallOperator(FD)) | |
| return MLTAL; | |
| if (SetupConstraintScope(FD, TemplateArgs, MLTAL, Scope)) | |
| return std::nullopt; | |
| return MLTAL; | |
| } | |
| bool Sema::CheckFunctionConstraints(const FunctionDecl *FD, | |
| ConstraintSatisfaction &Satisfaction, | |
| SourceLocation UsageLoc, | |
| bool ForOverloadResolution) { | |
| // Don't check constraints if the function is dependent. Also don't check if | |
| // this is a function template specialization, as the call to | |
| // CheckFunctionTemplateConstraints after this will check it | |
| // better. | |
| if (FD->isDependentContext() || | |
| FD->getTemplatedKind() == | |
| FunctionDecl::TK_FunctionTemplateSpecialization) { | |
| Satisfaction.IsSatisfied = true; | |
| return false; | |
| } | |
| // A lambda conversion operator has the same constraints as the call operator | |
| // and constraints checking relies on whether we are in a lambda call operator | |
| // (and may refer to its parameters), so check the call operator instead. | |
| // Note that the declarations outside of the lambda should also be | |
| // considered. Turning on the 'ForOverloadResolution' flag results in the | |
| // LocalInstantiationScope not looking into its parents, but we can still | |
| // access Decls from the parents while building a lambda RAII scope later. | |
| if (const auto *MD = dyn_cast<CXXConversionDecl>(FD); | |
| MD && isLambdaConversionOperator(const_cast<CXXConversionDecl *>(MD))) | |
| return CheckFunctionConstraints(MD->getParent()->getLambdaCallOperator(), | |
| Satisfaction, UsageLoc, | |
| /*ShouldAddDeclsFromParentScope=*/true); | |
| DeclContext *CtxToSave = const_cast<FunctionDecl *>(FD); | |
| while (isLambdaCallOperator(CtxToSave) || FD->isTransparentContext()) { | |
| if (isLambdaCallOperator(CtxToSave)) | |
| CtxToSave = CtxToSave->getParent()->getParent(); | |
| else | |
| CtxToSave = CtxToSave->getNonTransparentContext(); | |
| } | |
| ContextRAII SavedContext{*this, CtxToSave}; | |
| LocalInstantiationScope Scope(*this, !ForOverloadResolution); | |
| std::optional<MultiLevelTemplateArgumentList> MLTAL = | |
| SetupConstraintCheckingTemplateArgumentsAndScope( | |
| const_cast<FunctionDecl *>(FD), {}, Scope); | |
| if (!MLTAL) | |
| return true; | |
| Qualifiers ThisQuals; | |
| CXXRecordDecl *Record = nullptr; | |
| if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) { | |
| ThisQuals = Method->getMethodQualifiers(); | |
| Record = const_cast<CXXRecordDecl *>(Method->getParent()); | |
| } | |
| CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr); | |
| LambdaScopeForCallOperatorInstantiationRAII LambdaScope( | |
| *this, const_cast<FunctionDecl *>(FD), *MLTAL, Scope, | |
| ForOverloadResolution); | |
| return CheckConstraintSatisfaction( | |
| FD, FD->getTrailingRequiresClause(), *MLTAL, | |
| SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()), | |
| Satisfaction); | |
| } | |
| static const Expr *SubstituteConstraintExpressionWithoutSatisfaction( | |
| Sema &S, const Sema::TemplateCompareNewDeclInfo &DeclInfo, | |
| const Expr *ConstrExpr) { | |
| MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs( | |
| DeclInfo.getDecl(), DeclInfo.getDeclContext(), /*Final=*/false, | |
| /*Innermost=*/std::nullopt, | |
| /*RelativeToPrimary=*/true, | |
| /*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true, | |
| /*SkipForSpecialization*/ false); | |
| if (MLTAL.getNumSubstitutedLevels() == 0) | |
| return ConstrExpr; | |
| // Set up a dummy 'instantiation' scope in the case of reference to function | |
| // parameters that the surrounding function hasn't been instantiated yet. Note | |
| // this may happen while we're comparing two templates' constraint | |
| // equivalence. | |
| std::optional<LocalInstantiationScope> ScopeForParameters; | |
| if (const NamedDecl *ND = DeclInfo.getDecl(); | |
| ND && ND->isFunctionOrFunctionTemplate()) { | |
| ScopeForParameters.emplace(S, /*CombineWithOuterScope=*/true); | |
| const FunctionDecl *FD = ND->getAsFunction(); | |
| if (FunctionTemplateDecl *Template = FD->getDescribedFunctionTemplate(); | |
| Template && Template->getInstantiatedFromMemberTemplate()) | |
| FD = Template->getInstantiatedFromMemberTemplate()->getTemplatedDecl(); | |
| for (auto *PVD : FD->parameters()) { | |
| if (ScopeForParameters->getInstantiationOfIfExists(PVD)) | |
| continue; | |
| if (!PVD->isParameterPack()) { | |
| ScopeForParameters->InstantiatedLocal(PVD, PVD); | |
| continue; | |
| } | |
| // This is hacky: we're mapping the parameter pack to a size-of-1 argument | |
| // to avoid building SubstTemplateTypeParmPackTypes for | |
| // PackExpansionTypes. The SubstTemplateTypeParmPackType node would | |
| // otherwise reference the AssociatedDecl of the template arguments, which | |
| // is, in this case, the template declaration. | |
| // | |
| // However, as we are in the process of comparing potential | |
| // re-declarations, the canonical declaration is the declaration itself at | |
| // this point. So if we didn't expand these packs, we would end up with an | |
| // incorrect profile difference because we will be profiling the | |
| // canonical types! | |
| // | |
| // FIXME: Improve the "no-transform" machinery in FindInstantiatedDecl so | |
| // that we can eliminate the Scope in the cases where the declarations are | |
| // not necessarily instantiated. It would also benefit the noexcept | |
| // specifier comparison. | |
| ScopeForParameters->MakeInstantiatedLocalArgPack(PVD); | |
| ScopeForParameters->InstantiatedLocalPackArg(PVD, PVD); | |
| } | |
| } | |
| std::optional<Sema::CXXThisScopeRAII> ThisScope; | |
| // See TreeTransform::RebuildTemplateSpecializationType. A context scope is | |
| // essential for having an injected class as the canonical type for a template | |
| // specialization type at the rebuilding stage. This guarantees that, for | |
| // out-of-line definitions, injected class name types and their equivalent | |
| // template specializations can be profiled to the same value, which makes it | |
| // possible that e.g. constraints involving C<Class<T>> and C<Class> are | |
| // perceived identical. | |
| std::optional<Sema::ContextRAII> ContextScope; | |
| const DeclContext *DC = [&] { | |
| if (!DeclInfo.getDecl()) | |
| return DeclInfo.getDeclContext(); | |
| return DeclInfo.getDecl()->getFriendObjectKind() | |
| ? DeclInfo.getLexicalDeclContext() | |
| : DeclInfo.getDeclContext(); | |
| }(); | |
| if (auto *RD = dyn_cast<CXXRecordDecl>(DC)) { | |
| ThisScope.emplace(S, const_cast<CXXRecordDecl *>(RD), Qualifiers()); | |
| ContextScope.emplace(S, const_cast<DeclContext *>(cast<DeclContext>(RD)), | |
| /*NewThisContext=*/false); | |
| } | |
| EnterExpressionEvaluationContext UnevaluatedContext( | |
| S, Sema::ExpressionEvaluationContext::Unevaluated, | |
| Sema::ReuseLambdaContextDecl); | |
| ExprResult SubstConstr = S.SubstConstraintExprWithoutSatisfaction( | |
| const_cast<clang::Expr *>(ConstrExpr), MLTAL); | |
| if (!SubstConstr.isUsable()) | |
| return nullptr; | |
| return SubstConstr.get(); | |
| } | |
| bool Sema::AreConstraintExpressionsEqual(const NamedDecl *Old, | |
| const Expr *OldConstr, | |
| const TemplateCompareNewDeclInfo &New, | |
| const Expr *NewConstr) { | |
| if (OldConstr == NewConstr) | |
| return true; | |
| // C++ [temp.constr.decl]p4 | |
| if (Old && !New.isInvalid() && !New.ContainsDecl(Old) && | |
| Old->getLexicalDeclContext() != New.getLexicalDeclContext()) { | |
| Sema::SFINAETrap _(*this); | |
| if (const Expr *SubstConstr = | |
| SubstituteConstraintExpressionWithoutSatisfaction(*this, Old, | |
| OldConstr)) | |
| OldConstr = SubstConstr; | |
| else | |
| return false; | |
| if (const Expr *SubstConstr = | |
| SubstituteConstraintExpressionWithoutSatisfaction(*this, New, | |
| NewConstr)) | |
| NewConstr = SubstConstr; | |
| else | |
| return false; | |
| } | |
| llvm::FoldingSetNodeID ID1, ID2; | |
| OldConstr->Profile(ID1, Context, /*Canonical=*/true); | |
| NewConstr->Profile(ID2, Context, /*Canonical=*/true); | |
| return ID1 == ID2; | |
| } | |
| bool Sema::FriendConstraintsDependOnEnclosingTemplate(const FunctionDecl *FD) { | |
| assert(FD->getFriendObjectKind() && "Must be a friend!"); | |
| // The logic for non-templates is handled in ASTContext::isSameEntity, so we | |
| // don't have to bother checking 'DependsOnEnclosingTemplate' for a | |
| // non-function-template. | |
| assert(FD->getDescribedFunctionTemplate() && | |
| "Non-function templates don't need to be checked"); | |
| SmallVector<AssociatedConstraint, 3> ACs; | |
| FD->getDescribedFunctionTemplate()->getAssociatedConstraints(ACs); | |
| unsigned OldTemplateDepth = CalculateTemplateDepthForConstraints(*this, FD); | |
| for (const AssociatedConstraint &AC : ACs) | |
| if (ConstraintExpressionDependsOnEnclosingTemplate(FD, OldTemplateDepth, | |
| AC.ConstraintExpr)) | |
| return true; | |
| return false; | |
| } | |
| bool Sema::EnsureTemplateArgumentListConstraints( | |
| TemplateDecl *TD, const MultiLevelTemplateArgumentList &TemplateArgsLists, | |
| SourceRange TemplateIDRange) { | |
| ConstraintSatisfaction Satisfaction; | |
| llvm::SmallVector<AssociatedConstraint, 3> AssociatedConstraints; | |
| TD->getAssociatedConstraints(AssociatedConstraints); | |
| if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgsLists, | |
| TemplateIDRange, Satisfaction) || | |
| !Satisfaction.IsSatisfied) { | |
| SmallString<128> TemplateArgString; | |
| TemplateArgString = " "; | |
| TemplateArgString += getTemplateArgumentBindingsText( | |
| TD->getTemplateParameters(), TemplateArgsLists.getInnermost().data(), | |
| TemplateArgsLists.getInnermost().size()); | |
| Diag(TemplateIDRange.getBegin(), | |
| diag::err_template_arg_list_constraints_not_satisfied) | |
| << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD | |
| << TemplateArgString << TemplateIDRange; | |
| DiagnoseUnsatisfiedConstraint(Satisfaction); | |
| return true; | |
| } | |
| return false; | |
| } | |
| static bool CheckFunctionConstraintsWithoutInstantiation( | |
| Sema &SemaRef, SourceLocation PointOfInstantiation, | |
| FunctionTemplateDecl *Template, ArrayRef<TemplateArgument> TemplateArgs, | |
| ConstraintSatisfaction &Satisfaction) { | |
| SmallVector<AssociatedConstraint, 3> TemplateAC; | |
| Template->getAssociatedConstraints(TemplateAC); | |
| if (TemplateAC.empty()) { | |
| Satisfaction.IsSatisfied = true; | |
| return false; | |
| } | |
| LocalInstantiationScope Scope(SemaRef); | |
| FunctionDecl *FD = Template->getTemplatedDecl(); | |
| // Collect the list of template arguments relative to the 'primary' | |
| // template. We need the entire list, since the constraint is completely | |
| // uninstantiated at this point. | |
| MultiLevelTemplateArgumentList MLTAL; | |
| { | |
| // getTemplateInstantiationArgs uses this instantiation context to find out | |
| // template arguments for uninstantiated functions. | |
| // We don't want this RAII object to persist, because there would be | |
| // otherwise duplicate diagnostic notes. | |
| Sema::InstantiatingTemplate Inst( | |
| SemaRef, PointOfInstantiation, | |
| Sema::InstantiatingTemplate::ConstraintsCheck{}, Template, TemplateArgs, | |
| PointOfInstantiation); | |
| if (Inst.isInvalid()) | |
| return true; | |
| MLTAL = SemaRef.getTemplateInstantiationArgs( | |
| /*D=*/FD, FD, | |
| /*Final=*/false, /*Innermost=*/{}, /*RelativeToPrimary=*/true, | |
| /*Pattern=*/nullptr, /*ForConstraintInstantiation=*/true); | |
| } | |
| Sema::ContextRAII SavedContext(SemaRef, FD); | |
| return SemaRef.CheckConstraintSatisfaction( | |
| Template, TemplateAC, MLTAL, PointOfInstantiation, Satisfaction); | |
| } | |
| bool Sema::CheckFunctionTemplateConstraints( | |
| SourceLocation PointOfInstantiation, FunctionDecl *Decl, | |
| ArrayRef<TemplateArgument> TemplateArgs, | |
| ConstraintSatisfaction &Satisfaction) { | |
| // In most cases we're not going to have constraints, so check for that first. | |
| FunctionTemplateDecl *Template = Decl->getPrimaryTemplate(); | |
| if (!Template) | |
| return ::CheckFunctionConstraintsWithoutInstantiation( | |
| *this, PointOfInstantiation, Decl->getDescribedFunctionTemplate(), | |
| TemplateArgs, Satisfaction); | |
| // Note - code synthesis context for the constraints check is created | |
| // inside CheckConstraintsSatisfaction. | |
| SmallVector<AssociatedConstraint, 3> TemplateAC; | |
| Template->getAssociatedConstraints(TemplateAC); | |
| if (TemplateAC.empty()) { | |
| Satisfaction.IsSatisfied = true; | |
| return false; | |
| } | |
| // Enter the scope of this instantiation. We don't use | |
| // PushDeclContext because we don't have a scope. | |
| Sema::ContextRAII savedContext(*this, Decl); | |
| LocalInstantiationScope Scope(*this); | |
| std::optional<MultiLevelTemplateArgumentList> MLTAL = | |
| SetupConstraintCheckingTemplateArgumentsAndScope(Decl, TemplateArgs, | |
| Scope); | |
| if (!MLTAL) | |
| return true; | |
| Qualifiers ThisQuals; | |
| CXXRecordDecl *Record = nullptr; | |
| if (auto *Method = dyn_cast<CXXMethodDecl>(Decl)) { | |
| ThisQuals = Method->getMethodQualifiers(); | |
| Record = Method->getParent(); | |
| } | |
| CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr); | |
| LambdaScopeForCallOperatorInstantiationRAII LambdaScope(*this, Decl, *MLTAL, | |
| Scope); | |
| return CheckConstraintSatisfaction(Template, TemplateAC, *MLTAL, | |
| PointOfInstantiation, Satisfaction); | |
| } | |
| static void diagnoseUnsatisfiedRequirement(Sema &S, | |
| concepts::ExprRequirement *Req, | |
| bool First) { | |
| assert(!Req->isSatisfied() && | |
| "Diagnose() can only be used on an unsatisfied requirement"); | |
| switch (Req->getSatisfactionStatus()) { | |
| case concepts::ExprRequirement::SS_Dependent: | |
| llvm_unreachable("Diagnosing a dependent requirement"); | |
| break; | |
| case concepts::ExprRequirement::SS_ExprSubstitutionFailure: { | |
| auto *SubstDiag = Req->getExprSubstitutionDiagnostic(); | |
| if (!SubstDiag->DiagMessage.empty()) | |
| S.Diag(SubstDiag->DiagLoc, | |
| diag::note_expr_requirement_expr_substitution_error) | |
| << (int)First << SubstDiag->SubstitutedEntity | |
| << SubstDiag->DiagMessage; | |
| else | |
| S.Diag(SubstDiag->DiagLoc, | |
| diag::note_expr_requirement_expr_unknown_substitution_error) | |
| << (int)First << SubstDiag->SubstitutedEntity; | |
| break; | |
| } | |
| case concepts::ExprRequirement::SS_NoexceptNotMet: | |
| S.Diag(Req->getNoexceptLoc(), diag::note_expr_requirement_noexcept_not_met) | |
| << (int)First << Req->getExpr(); | |
| break; | |
| case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: { | |
| auto *SubstDiag = | |
| Req->getReturnTypeRequirement().getSubstitutionDiagnostic(); | |
| if (!SubstDiag->DiagMessage.empty()) | |
| S.Diag(SubstDiag->DiagLoc, | |
| diag::note_expr_requirement_type_requirement_substitution_error) | |
| << (int)First << SubstDiag->SubstitutedEntity | |
| << SubstDiag->DiagMessage; | |
| else | |
| S.Diag( | |
| SubstDiag->DiagLoc, | |
| diag:: | |
| note_expr_requirement_type_requirement_unknown_substitution_error) | |
| << (int)First << SubstDiag->SubstitutedEntity; | |
| break; | |
| } | |
| case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: { | |
| ConceptSpecializationExpr *ConstraintExpr = | |
| Req->getReturnTypeRequirementSubstitutedConstraintExpr(); | |
| S.DiagnoseUnsatisfiedConstraint(ConstraintExpr); | |
| break; | |
| } | |
| case concepts::ExprRequirement::SS_Satisfied: | |
| llvm_unreachable("We checked this above"); | |
| } | |
| } | |
| static void diagnoseUnsatisfiedRequirement(Sema &S, | |
| concepts::TypeRequirement *Req, | |
| bool First) { | |
| assert(!Req->isSatisfied() && | |
| "Diagnose() can only be used on an unsatisfied requirement"); | |
| switch (Req->getSatisfactionStatus()) { | |
| case concepts::TypeRequirement::SS_Dependent: | |
| llvm_unreachable("Diagnosing a dependent requirement"); | |
| return; | |
| case concepts::TypeRequirement::SS_SubstitutionFailure: { | |
| auto *SubstDiag = Req->getSubstitutionDiagnostic(); | |
| if (!SubstDiag->DiagMessage.empty()) | |
| S.Diag(SubstDiag->DiagLoc, diag::note_type_requirement_substitution_error) | |
| << (int)First << SubstDiag->SubstitutedEntity | |
| << SubstDiag->DiagMessage; | |
| else | |
| S.Diag(SubstDiag->DiagLoc, | |
| diag::note_type_requirement_unknown_substitution_error) | |
| << (int)First << SubstDiag->SubstitutedEntity; | |
| return; | |
| } | |
| default: | |
| llvm_unreachable("Unknown satisfaction status"); | |
| return; | |
| } | |
| } | |
| static void diagnoseUnsatisfiedConceptIdExpr(Sema &S, | |
| const ConceptReference *Concept, | |
| SourceLocation Loc, bool First) { | |
| if (Concept->getTemplateArgsAsWritten()->NumTemplateArgs == 1) { | |
| S.Diag( | |
| Loc, | |
| diag:: | |
| note_single_arg_concept_specialization_constraint_evaluated_to_false) | |
| << (int)First | |
| << Concept->getTemplateArgsAsWritten()->arguments()[0].getArgument() | |
| << Concept->getNamedConcept().getAsTemplateDecl(); | |
| } else { | |
| S.Diag(Loc, diag::note_concept_specialization_constraint_evaluated_to_false) | |
| << (int)First << Concept; | |
| } | |
| } | |
| static void diagnoseUnsatisfiedConstraintExpr( | |
| Sema &S, const UnsatisfiedConstraintRecord &Record, SourceLocation Loc, | |
| bool First, concepts::NestedRequirement *Req = nullptr); | |
| static void DiagnoseUnsatisfiedConstraint( | |
| Sema &S, ArrayRef<UnsatisfiedConstraintRecord> Records, SourceLocation Loc, | |
| bool First = true, concepts::NestedRequirement *Req = nullptr) { | |
| for (auto &Record : Records) { | |
| diagnoseUnsatisfiedConstraintExpr(S, Record, Loc, First, Req); | |
| Loc = {}; | |
| First = isa<const ConceptReference *>(Record); | |
| } | |
| } | |
| static void diagnoseUnsatisfiedRequirement(Sema &S, | |
| concepts::NestedRequirement *Req, | |
| bool First) { | |
| DiagnoseUnsatisfiedConstraint(S, Req->getConstraintSatisfaction().records(), | |
| Req->hasInvalidConstraint() | |
| ? SourceLocation() | |
| : Req->getConstraintExpr()->getExprLoc(), | |
| First, Req); | |
| } | |
| static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S, | |
| const Expr *SubstExpr, | |
| bool First) { | |
| SubstExpr = SubstExpr->IgnoreParenImpCasts(); | |
| if (const BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) { | |
| switch (BO->getOpcode()) { | |
| // These two cases will in practice only be reached when using fold | |
| // expressions with || and &&, since otherwise the || and && will have been | |
| // broken down into atomic constraints during satisfaction checking. | |
| case BO_LOr: | |
| // Or evaluated to false - meaning both RHS and LHS evaluated to false. | |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First); | |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), | |
| /*First=*/false); | |
| return; | |
| case BO_LAnd: { | |
| bool LHSSatisfied = | |
| BO->getLHS()->EvaluateKnownConstInt(S.Context).getBoolValue(); | |
| if (LHSSatisfied) { | |
| // LHS is true, so RHS must be false. | |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First); | |
| return; | |
| } | |
| // LHS is false | |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First); | |
| // RHS might also be false | |
| bool RHSSatisfied = | |
| BO->getRHS()->EvaluateKnownConstInt(S.Context).getBoolValue(); | |
| if (!RHSSatisfied) | |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), | |
| /*First=*/false); | |
| return; | |
| } | |
| case BO_GE: | |
| case BO_LE: | |
| case BO_GT: | |
| case BO_LT: | |
| case BO_EQ: | |
| case BO_NE: | |
| if (BO->getLHS()->getType()->isIntegerType() && | |
| BO->getRHS()->getType()->isIntegerType()) { | |
| Expr::EvalResult SimplifiedLHS; | |
| Expr::EvalResult SimplifiedRHS; | |
| BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context, | |
| Expr::SE_NoSideEffects, | |
| /*InConstantContext=*/true); | |
| BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context, | |
| Expr::SE_NoSideEffects, | |
| /*InConstantContext=*/true); | |
| if (!SimplifiedLHS.Diag && !SimplifiedRHS.Diag) { | |
| S.Diag(SubstExpr->getBeginLoc(), | |
| diag::note_atomic_constraint_evaluated_to_false_elaborated) | |
| << (int)First << SubstExpr | |
| << toString(SimplifiedLHS.Val.getInt(), 10) | |
| << BinaryOperator::getOpcodeStr(BO->getOpcode()) | |
| << toString(SimplifiedRHS.Val.getInt(), 10); | |
| return; | |
| } | |
| } | |
| break; | |
| default: | |
| break; | |
| } | |
| } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) { | |
| S.DiagnoseUnsatisfiedRequiresExpr(RE, First); | |
| return; | |
| } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) { | |
| // Drill down concept ids treated as atomic constraints | |
| S.DiagnoseUnsatisfiedConstraint(CSE, First); | |
| return; | |
| } else if (auto *TTE = dyn_cast<TypeTraitExpr>(SubstExpr); | |
| TTE && TTE->getTrait() == clang::TypeTrait::BTT_IsDeducible) { | |
| assert(TTE->getNumArgs() == 2); | |
| S.Diag(SubstExpr->getSourceRange().getBegin(), | |
| diag::note_is_deducible_constraint_evaluated_to_false) | |
| << TTE->getArg(0)->getType() << TTE->getArg(1)->getType(); | |
| return; | |
| } | |
| S.Diag(SubstExpr->getSourceRange().getBegin(), | |
| diag::note_atomic_constraint_evaluated_to_false) | |
| << (int)First << SubstExpr; | |
| S.DiagnoseTypeTraitDetails(SubstExpr); | |
| } | |
| static void diagnoseUnsatisfiedConstraintExpr( | |
| Sema &S, const UnsatisfiedConstraintRecord &Record, SourceLocation Loc, | |
| bool First, concepts::NestedRequirement *Req) { | |
| if (auto *Diag = dyn_cast<const ConstraintSubstitutionDiagnostic *>(Record)) { | |
| if (Req) | |
| S.Diag(Diag->first, diag::note_nested_requirement_substitution_error) | |
| << (int)First << Req->getInvalidConstraintEntity() << Diag->second; | |
| else | |
| S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed) | |
| << Diag->second; | |
| return; | |
| } | |
| if (const auto *Concept = dyn_cast<const ConceptReference *>(Record)) { | |
| if (Loc.isInvalid()) | |
| Loc = Concept->getBeginLoc(); | |
| diagnoseUnsatisfiedConceptIdExpr(S, Concept, Loc, First); | |
| return; | |
| } | |
| diagnoseWellFormedUnsatisfiedConstraintExpr( | |
| S, cast<const class Expr *>(Record), First); | |
| } | |
| void Sema::DiagnoseUnsatisfiedRequiresExpr(const RequiresExpr *RE, bool First) { | |
| // FIXME: RequiresExpr should store dependent diagnostics. | |
| for (concepts::Requirement *Req : RE->getRequirements()) | |
| if (!Req->isDependent() && !Req->isSatisfied()) { | |
| if (auto *E = dyn_cast<concepts::ExprRequirement>(Req)) | |
| diagnoseUnsatisfiedRequirement(*this, E, First); | |
| else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req)) | |
| diagnoseUnsatisfiedRequirement(*this, T, First); | |
| else | |
| diagnoseUnsatisfiedRequirement( | |
| *this, cast<concepts::NestedRequirement>(Req), First); | |
| break; | |
| } | |
| } | |
| void Sema::DiagnoseUnsatisfiedConstraint( | |
| const ConstraintSatisfaction &Satisfaction, SourceLocation Loc, | |
| bool First) { | |
| assert(!Satisfaction.IsSatisfied && | |
| "Attempted to diagnose a satisfied constraint"); | |
| ::DiagnoseUnsatisfiedConstraint(*this, Satisfaction.Details, Loc, First); | |
| } | |
| void Sema::DiagnoseUnsatisfiedConstraint( | |
| const ConceptSpecializationExpr *ConstraintExpr, bool First) { | |
| const ASTConstraintSatisfaction &Satisfaction = | |
| ConstraintExpr->getSatisfaction(); | |
| assert(!Satisfaction.IsSatisfied && | |
| "Attempted to diagnose a satisfied constraint"); | |
| ::DiagnoseUnsatisfiedConstraint(*this, Satisfaction.records(), | |
| ConstraintExpr->getBeginLoc(), First); | |
| } | |
| namespace clang { | |
| class SubstituteParameterMappings { | |
| Sema &SemaRef; | |
| const MultiLevelTemplateArgumentList *MLTAL; | |
| const ASTTemplateArgumentListInfo *ArgsAsWritten; | |
| // When normalizing a fold constraint, e.g. | |
| // C<Pack1, Pack2...> && ... | |
| // we want the TreeTransform to expand only Pack2 but not Pack1, | |
| // since Pack1 will be expanded during the evaluation of the fold expression. | |
| // This flag helps rewrite any non-PackExpansion packs into "expanded" | |
| // parameters. | |
| bool RemovePacksForFoldExpr; | |
| SubstituteParameterMappings(Sema &SemaRef, | |
| const MultiLevelTemplateArgumentList *MLTAL, | |
| const ASTTemplateArgumentListInfo *ArgsAsWritten, | |
| bool RemovePacksForFoldExpr) | |
| : SemaRef(SemaRef), MLTAL(MLTAL), ArgsAsWritten(ArgsAsWritten), | |
| RemovePacksForFoldExpr(RemovePacksForFoldExpr) {} | |
| void buildParameterMapping(NormalizedConstraintWithParamMapping &N); | |
| bool substitute(NormalizedConstraintWithParamMapping &N); | |
| bool substitute(ConceptIdConstraint &CC); | |
| public: | |
| SubstituteParameterMappings(Sema &SemaRef, | |
| bool RemovePacksForFoldExpr = false) | |
| : SemaRef(SemaRef), MLTAL(nullptr), ArgsAsWritten(nullptr), | |
| RemovePacksForFoldExpr(RemovePacksForFoldExpr) {} | |
| bool substitute(NormalizedConstraint &N); | |
| }; | |
| } // namespace clang | |
| void SubstituteParameterMappings::buildParameterMapping( | |
| NormalizedConstraintWithParamMapping &N) { | |
| TemplateParameterList *TemplateParams = | |
| cast<TemplateDecl>(N.getConstraintDecl())->getTemplateParameters(); | |
| llvm::SmallBitVector OccurringIndices(TemplateParams->size()); | |
| llvm::SmallBitVector OccurringIndicesForSubsumption(TemplateParams->size()); | |
| if (N.getKind() == NormalizedConstraint::ConstraintKind::Atomic) { | |
| SemaRef.MarkUsedTemplateParameters( | |
| static_cast<AtomicConstraint &>(N).getConstraintExpr(), | |
| /*OnlyDeduced=*/false, | |
| /*Depth=*/0, OccurringIndices); | |
| SemaRef.MarkUsedTemplateParametersForSubsumptionParameterMapping( | |
| static_cast<AtomicConstraint &>(N).getConstraintExpr(), | |
| /*Depth=*/0, OccurringIndicesForSubsumption); | |
| } else if (N.getKind() == | |
| NormalizedConstraint::ConstraintKind::FoldExpanded) { | |
| SemaRef.MarkUsedTemplateParameters( | |
| static_cast<FoldExpandedConstraint &>(N).getPattern(), | |
| /*OnlyDeduced=*/false, | |
| /*Depth=*/0, OccurringIndices); | |
| } else if (N.getKind() == NormalizedConstraint::ConstraintKind::ConceptId) { | |
| auto *Args = static_cast<ConceptIdConstraint &>(N) | |
| .getConceptId() | |
| ->getTemplateArgsAsWritten(); | |
| if (Args) | |
| SemaRef.MarkUsedTemplateParameters(Args->arguments(), | |
| /*Depth=*/0, OccurringIndices); | |
| } | |
| // If a parameter is only referenced in a default template argument, | |
| // we need to add it to the mapping explicitly. | |
| { | |
| llvm::SmallVector<TemplateArgument> DefaultArgs; | |
| for (unsigned I = TemplateParams->getMinRequiredArguments(); | |
| I < TemplateParams->size(); ++I) { | |
| const NamedDecl *Param = TemplateParams->getParam(I); | |
| if (Param->isParameterPack()) | |
| break; | |
| const TemplateArgument *Arg = | |
| SemaRef.getASTContext().getDefaultTemplateArgumentOrNone(Param); | |
| assert(Arg && "expected a default argument"); | |
| DefaultArgs.emplace_back(std::move(*Arg)); | |
| } | |
| SemaRef.MarkUsedTemplateParameters(DefaultArgs, /*OnlyDeduced=*/false, | |
| /*Depth=*/0, OccurringIndices); | |
| SemaRef.MarkUsedTemplateParameters(DefaultArgs, /*OnlyDeduced=*/false, | |
| /*Depth=*/0, | |
| OccurringIndicesForSubsumption); | |
| } | |
| unsigned Size = OccurringIndices.count(); | |
| // When the constraint is independent of any template parameters, | |
| // we build an empty mapping so that we can distinguish these cases | |
| // from cases where no mapping exists at all, e.g. when there are only atomic | |
| // constraints. | |
| TemplateArgumentLoc *TempArgs = | |
| new (SemaRef.Context) TemplateArgumentLoc[Size]; | |
| llvm::SmallVector<NamedDecl *> UsedParams; | |
| for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I) { | |
| SourceLocation Loc = ArgsAsWritten->NumTemplateArgs > I | |
| ? ArgsAsWritten->arguments()[I].getLocation() | |
| : SourceLocation(); | |
| // FIXME: Investigate why we couldn't always preserve the SourceLoc. We | |
| // can't assert Loc.isValid() now. | |
| if (OccurringIndices[I]) { | |
| NamedDecl *Param = TemplateParams->begin()[I]; | |
| new (&(TempArgs)[J]) TemplateArgumentLoc( | |
| SemaRef.getIdentityTemplateArgumentLoc(Param, Loc)); | |
| UsedParams.push_back(Param); | |
| J++; | |
| } | |
| } | |
| auto *UsedList = TemplateParameterList::Create( | |
| SemaRef.Context, TemplateParams->getTemplateLoc(), | |
| TemplateParams->getLAngleLoc(), UsedParams, | |
| /*RAngleLoc=*/SourceLocation(), | |
| /*RequiresClause=*/nullptr); | |
| N.updateParameterMapping( | |
| std::move(OccurringIndices), std::move(OccurringIndicesForSubsumption), | |
| MutableArrayRef<TemplateArgumentLoc>{TempArgs, Size}, UsedList); | |
| } | |
| bool SubstituteParameterMappings::substitute( | |
| NormalizedConstraintWithParamMapping &N) { | |
| if (!N.hasParameterMapping()) | |
| buildParameterMapping(N); | |
| // If the parameter mapping is empty, there is nothing to substitute. | |
| if (N.getParameterMapping().empty()) | |
| return false; | |
| SourceLocation InstLocBegin, InstLocEnd; | |
| llvm::ArrayRef Arguments = ArgsAsWritten->arguments(); | |
| if (Arguments.empty()) { | |
| InstLocBegin = ArgsAsWritten->getLAngleLoc(); | |
| InstLocEnd = ArgsAsWritten->getRAngleLoc(); | |
| } else { | |
| auto SR = Arguments[0].getSourceRange(); | |
| InstLocBegin = SR.getBegin(); | |
| InstLocEnd = SR.getEnd(); | |
| } | |
| Sema::NonSFINAEContext _(SemaRef); | |
| Sema::InstantiatingTemplate Inst( | |
| SemaRef, InstLocBegin, | |
| Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, | |
| const_cast<NamedDecl *>(N.getConstraintDecl()), | |
| {InstLocBegin, InstLocEnd}); | |
| if (Inst.isInvalid()) | |
| return true; | |
| // TransformTemplateArguments is unable to preserve the source location of a | |
| // pack. The SourceLocation is necessary for the instantiation location. | |
| // FIXME: The BaseLoc will be used as the location of the pack expansion, | |
| // which is wrong. | |
| TemplateArgumentListInfo SubstArgs; | |
| llvm::SaveAndRestore<decltype(SemaRef.CurrentCachedTemplateArgs)> | |
| DoNotCacheDependentArgs(SemaRef.CurrentCachedTemplateArgs, nullptr); | |
| if (SemaRef.SubstTemplateArgumentsInParameterMapping( | |
| N.getParameterMapping(), N.getBeginLoc(), *MLTAL, SubstArgs)) | |
| return true; | |
| Sema::CheckTemplateArgumentInfo CTAI; | |
| auto *TD = | |
| const_cast<TemplateDecl *>(cast<TemplateDecl>(N.getConstraintDecl())); | |
| if (SemaRef.CheckTemplateArgumentList(TD, N.getUsedTemplateParamList(), | |
| TD->getLocation(), SubstArgs, | |
| /*DefaultArguments=*/{}, | |
| /*PartialTemplateArgs=*/false, CTAI)) | |
| return true; | |
| TemplateArgumentLoc *TempArgs = | |
| new (SemaRef.Context) TemplateArgumentLoc[CTAI.SugaredConverted.size()]; | |
| for (unsigned I = 0; I < CTAI.SugaredConverted.size(); ++I) { | |
| SourceLocation Loc; | |
| // If this is an empty pack, we have no corresponding SubstArgs. | |
| if (I < SubstArgs.size()) | |
| Loc = SubstArgs.arguments()[I].getLocation(); | |
| TempArgs[I] = SemaRef.getTrivialTemplateArgumentLoc( | |
| CTAI.SugaredConverted[I], QualType(), Loc); | |
| } | |
| MutableArrayRef<TemplateArgumentLoc> Mapping(TempArgs, | |
| CTAI.SugaredConverted.size()); | |
| N.updateParameterMapping(N.mappingOccurenceList(), | |
| N.mappingOccurenceListForSubsumption(), Mapping, | |
| N.getUsedTemplateParamList()); | |
| return false; | |
| } | |
| bool SubstituteParameterMappings::substitute(ConceptIdConstraint &CC) { | |
| assert(CC.getConstraintDecl() && MLTAL && ArgsAsWritten); | |
| if (substitute(static_cast<NormalizedConstraintWithParamMapping &>(CC))) | |
| return true; | |
| auto *CSE = CC.getConceptSpecializationExpr(); | |
| assert(CSE); | |
| assert(!CC.getBeginLoc().isInvalid()); | |
| SourceLocation InstLocBegin, InstLocEnd; | |
| if (llvm::ArrayRef Arguments = ArgsAsWritten->arguments(); | |
| Arguments.empty()) { | |
| InstLocBegin = ArgsAsWritten->getLAngleLoc(); | |
| InstLocEnd = ArgsAsWritten->getRAngleLoc(); | |
| } else { | |
| auto SR = Arguments[0].getSourceRange(); | |
| InstLocBegin = SR.getBegin(); | |
| InstLocEnd = SR.getEnd(); | |
| } | |
| Sema::NonSFINAEContext _(SemaRef); | |
| // This is useful for name lookup across modules; see Sema::getLookupModules. | |
| Sema::InstantiatingTemplate Inst( | |
| SemaRef, InstLocBegin, | |
| Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, | |
| const_cast<NamedDecl *>(CC.getConstraintDecl()), | |
| {InstLocBegin, InstLocEnd}); | |
| if (Inst.isInvalid()) | |
| return true; | |
| TemplateArgumentListInfo Out; | |
| // TransformTemplateArguments is unable to preserve the source location of a | |
| // pack. The SourceLocation is necessary for the instantiation location. | |
| // FIXME: The BaseLoc will be used as the location of the pack expansion, | |
| // which is wrong. | |
| llvm::SaveAndRestore<decltype(SemaRef.CurrentCachedTemplateArgs)> | |
| DoNotCacheDependentArgs(SemaRef.CurrentCachedTemplateArgs, nullptr); | |
| const ASTTemplateArgumentListInfo *ArgsAsWritten = | |
| CSE->getTemplateArgsAsWritten(); | |
| if (SemaRef.SubstTemplateArgumentsInParameterMapping( | |
| ArgsAsWritten->arguments(), CC.getBeginLoc(), *MLTAL, Out)) | |
| return true; | |
| Sema::CheckTemplateArgumentInfo CTAI; | |
| if (SemaRef.CheckTemplateArgumentList(CSE->getConceptDecl(), | |
| CSE->getConceptNameInfo().getLoc(), Out, | |
| /*DefaultArgs=*/{}, | |
| /*PartialTemplateArgs=*/false, CTAI, | |
| /*UpdateArgsWithConversions=*/false)) | |
| return true; | |
| auto TemplateArgs = *MLTAL; | |
| TemplateArgs.replaceOutermostTemplateArguments(CSE->getConceptDecl(), | |
| CTAI.SugaredConverted); | |
| return SubstituteParameterMappings(SemaRef, &TemplateArgs, ArgsAsWritten, | |
| RemovePacksForFoldExpr) | |
| .substitute(CC.getNormalizedConstraint()); | |
| } | |
| bool SubstituteParameterMappings::substitute(NormalizedConstraint &N) { | |
| switch (N.getKind()) { | |
| case NormalizedConstraint::ConstraintKind::Atomic: { | |
| if (!MLTAL) { | |
| assert(!ArgsAsWritten); | |
| return false; | |
| } | |
| return substitute(static_cast<NormalizedConstraintWithParamMapping &>(N)); | |
| } | |
| case NormalizedConstraint::ConstraintKind::FoldExpanded: { | |
| auto &FE = static_cast<FoldExpandedConstraint &>(N); | |
| if (!MLTAL) { | |
| llvm::SaveAndRestore _1(RemovePacksForFoldExpr, true); | |
| assert(!ArgsAsWritten); | |
| return substitute(FE.getNormalizedPattern()); | |
| } | |
| Sema::ArgPackSubstIndexRAII _(SemaRef, std::nullopt); | |
| substitute(static_cast<NormalizedConstraintWithParamMapping &>(FE)); | |
| return SubstituteParameterMappings(SemaRef, /*RemovePacksForFoldExpr=*/true) | |
| .substitute(FE.getNormalizedPattern()); | |
| } | |
| case NormalizedConstraint::ConstraintKind::ConceptId: { | |
| auto &CC = static_cast<ConceptIdConstraint &>(N); | |
| if (MLTAL) { | |
| assert(ArgsAsWritten); | |
| return substitute(CC); | |
| } | |
| assert(!ArgsAsWritten); | |
| const ConceptSpecializationExpr *CSE = CC.getConceptSpecializationExpr(); | |
| // Make sure that lambdas within template arguments live in a | |
| // dependent context such that they are assured to be transformed during | |
| // constraint evaluation. | |
| EnterExpressionEvaluationContext EECtx( | |
| SemaRef, Sema::ExpressionEvaluationContext::ConstantEvaluated, | |
| /*LambdaContextDecl=*/ | |
| const_cast<ImplicitConceptSpecializationDecl *>( | |
| CSE->getSpecializationDecl())); | |
| SmallVector<TemplateArgument> InnerArgs(CSE->getTemplateArguments()); | |
| ConceptDecl *Concept = CSE->getConceptDecl(); | |
| if (RemovePacksForFoldExpr) { | |
| TemplateArgumentListInfo OutArgs; | |
| ArrayRef<TemplateArgumentLoc> InputArgLoc = | |
| CSE->getConceptReference()->getTemplateArgsAsWritten()->arguments(); | |
| if (AdjustConstraints(SemaRef, /*TemplateDepth=*/0, | |
| /*RemoveNonPackExpansionPacks=*/true) | |
| .TransformTemplateArguments(InputArgLoc.begin(), | |
| InputArgLoc.end(), OutArgs)) | |
| return true; | |
| Sema::CheckTemplateArgumentInfo CTAI; | |
| // Repack the packs. | |
| if (SemaRef.CheckTemplateArgumentList( | |
| Concept, Concept->getTemplateParameters(), Concept->getBeginLoc(), | |
| OutArgs, | |
| /*DefaultArguments=*/{}, | |
| /*PartialTemplateArgs=*/false, CTAI)) | |
| return true; | |
| InnerArgs = std::move(CTAI.SugaredConverted); | |
| } | |
| MultiLevelTemplateArgumentList MLTAL = SemaRef.getTemplateInstantiationArgs( | |
| Concept, Concept->getLexicalDeclContext(), | |
| /*Final=*/true, InnerArgs, | |
| /*RelativeToPrimary=*/true, | |
| /*Pattern=*/nullptr, | |
| /*ForConstraintInstantiation=*/true); | |
| MLTAL.setRetainInnerDepths(); | |
| return SubstituteParameterMappings(SemaRef, &MLTAL, | |
| CSE->getTemplateArgsAsWritten(), | |
| RemovePacksForFoldExpr) | |
| .substitute(CC.getNormalizedConstraint()); | |
| } | |
| case NormalizedConstraint::ConstraintKind::Compound: { | |
| auto &Compound = static_cast<CompoundConstraint &>(N); | |
| if (substitute(Compound.getLHS())) | |
| return true; | |
| return substitute(Compound.getRHS()); | |
| } | |
| } | |
| llvm_unreachable("Unknown ConstraintKind enum"); | |
| } | |
| NormalizedConstraint *NormalizedConstraint::fromAssociatedConstraints( | |
| Sema &S, const NamedDecl *D, ArrayRef<AssociatedConstraint> ACs) { | |
| assert(ACs.size() != 0); | |
| auto *Conjunction = | |
| fromConstraintExpr(S, D, ACs[0].ConstraintExpr, ACs[0].ArgPackSubstIndex); | |
| if (!Conjunction) | |
| return nullptr; | |
| for (unsigned I = 1; I < ACs.size(); ++I) { | |
| auto *Next = fromConstraintExpr(S, D, ACs[I].ConstraintExpr, | |
| ACs[I].ArgPackSubstIndex); | |
| if (!Next) | |
| return nullptr; | |
| Conjunction = CompoundConstraint::CreateConjunction(S.getASTContext(), | |
| Conjunction, Next); | |
| } | |
| return Conjunction; | |
| } | |
| NormalizedConstraint *NormalizedConstraint::fromConstraintExpr( | |
| Sema &S, const NamedDecl *D, const Expr *E, UnsignedOrNone SubstIndex) { | |
| assert(E != nullptr); | |
| // C++ [temp.constr.normal]p1.1 | |
| // [...] | |
| // - The normal form of an expression (E) is the normal form of E. | |
| // [...] | |
| E = E->IgnoreParenImpCasts(); | |
| llvm::FoldingSetNodeID ID; | |
| if (D && DiagRecursiveConstraintEval(S, ID, D, E)) { | |
| return nullptr; | |
| } | |
| SatisfactionStackRAII StackRAII(S, D, ID); | |
| // C++2a [temp.param]p4: | |
| // [...] If T is not a pack, then E is E', otherwise E is (E' && ...). | |
| // Fold expression is considered atomic constraints per current wording. | |
| // See http://cplusplus.github.io/concepts-ts/ts-active.html#28 | |
| if (LogicalBinOp BO = E) { | |
| auto *LHS = fromConstraintExpr(S, D, BO.getLHS(), SubstIndex); | |
| if (!LHS) | |
| return nullptr; | |
| auto *RHS = fromConstraintExpr(S, D, BO.getRHS(), SubstIndex); | |
| if (!RHS) | |
| return nullptr; | |
| return CompoundConstraint::Create( | |
| S.Context, LHS, BO.isAnd() ? CCK_Conjunction : CCK_Disjunction, RHS); | |
| } | |
| if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) { | |
| // C++ [temp.constr.normal]p1.1 | |
| // [...] | |
| // The normal form of an id-expression of the form C<A1, A2, ..., AN>, | |
| // where C names a concept, is the normal form of the | |
| // constraint-expression of C, after substituting A1, A2, ..., AN for C’s | |
| // respective template parameters in the parameter mappings in each atomic | |
| // constraint. If any such substitution results in an invalid type or | |
| // expression, the program is ill-formed; no diagnostic is required. | |
| // [...] | |
| NormalizedConstraint *SubNF; | |
| if (ExprResult Res = | |
| SubstituteConceptsInConstraintExpression(S, D, CSE, SubstIndex); | |
| Res.isUsable()) | |
| // Use canonical declarations to merge ConceptDecls across different | |
| // modules. | |
| SubNF = NormalizedConstraint::fromAssociatedConstraints( | |
| S, CSE->getConceptDecl()->getCanonicalDecl(), | |
| AssociatedConstraint(Res.get(), SubstIndex)); | |
| else | |
| return nullptr; | |
| return ConceptIdConstraint::Create(S.getASTContext(), | |
| CSE->getConceptReference(), SubNF, D, | |
| CSE, SubstIndex); | |
| } | |
| if (auto *FE = dyn_cast<const CXXFoldExpr>(E); | |
| FE && S.getLangOpts().CPlusPlus26 && | |
| (FE->getOperator() == BinaryOperatorKind::BO_LAnd || | |
| FE->getOperator() == BinaryOperatorKind::BO_LOr)) { | |
| // Normalize fold expressions in C++26. | |
| FoldExpandedConstraint::FoldOperatorKind Kind = | |
| FE->getOperator() == BinaryOperatorKind::BO_LAnd | |
| ? FoldExpandedConstraint::FoldOperatorKind::And | |
| : FoldExpandedConstraint::FoldOperatorKind::Or; | |
| if (FE->getInit()) { | |
| auto *LHS = fromConstraintExpr(S, D, FE->getLHS(), SubstIndex); | |
| auto *RHS = fromConstraintExpr(S, D, FE->getRHS(), SubstIndex); | |
| if (!LHS || !RHS) | |
| return nullptr; | |
| if (FE->isRightFold()) | |
| LHS = FoldExpandedConstraint::Create(S.getASTContext(), | |
| FE->getPattern(), D, Kind, LHS); | |
| else | |
| RHS = FoldExpandedConstraint::Create(S.getASTContext(), | |
| FE->getPattern(), D, Kind, RHS); | |
| return CompoundConstraint::Create( | |
| S.getASTContext(), LHS, | |
| (FE->getOperator() == BinaryOperatorKind::BO_LAnd ? CCK_Conjunction | |
| : CCK_Disjunction), | |
| RHS); | |
| } | |
| auto *Sub = fromConstraintExpr(S, D, FE->getPattern(), SubstIndex); | |
| if (!Sub) | |
| return nullptr; | |
| return FoldExpandedConstraint::Create(S.getASTContext(), FE->getPattern(), | |
| D, Kind, Sub); | |
| } | |
| return AtomicConstraint::Create(S.getASTContext(), E, D, SubstIndex); | |
| } | |
| const NormalizedConstraint *Sema::getNormalizedAssociatedConstraints( | |
| ConstrainedDeclOrNestedRequirement ConstrainedDeclOrNestedReq, | |
| ArrayRef<AssociatedConstraint> AssociatedConstraints) { | |
| if (!ConstrainedDeclOrNestedReq) { | |
| auto *Normalized = NormalizedConstraint::fromAssociatedConstraints( | |
| *this, nullptr, AssociatedConstraints); | |
| if (!Normalized || | |
| SubstituteParameterMappings(*this).substitute(*Normalized)) | |
| return nullptr; | |
| return Normalized; | |
| } | |
| // FIXME: ConstrainedDeclOrNestedReq is never a NestedRequirement! | |
| const NamedDecl *ND = dyn_cast<const NamedDecl *>(ConstrainedDeclOrNestedReq); | |
| // The normal form only depends on the constraint expressions, and the | |
| // members of all specializations of a class template share the | |
| // (uninstantiated) constraint expressions of the member they were | |
| // instantiated from. Cache the normal form of each expression to not | |
| // normalize the same expression once per class template specialization. | |
| NormalizedConstraint *Normalized = nullptr; | |
| for (const AssociatedConstraint &AC : AssociatedConstraints) { | |
| std::pair<const Expr *, unsigned> Key( | |
| AC.ConstraintExpr, AC.ArgPackSubstIndex.toInternalRepresentation()); | |
| NormalizedConstraint *Next; | |
| if (auto It = NormalizedConstraintExprCache.find(Key); | |
| It != NormalizedConstraintExprCache.end()) { | |
| Next = It->second; | |
| } else { | |
| Next = NormalizedConstraint::fromAssociatedConstraints(*this, ND, AC); | |
| // substitute() can invalidate iterators of NormalizedConstraintExprCache. | |
| if (Next && SubstituteParameterMappings(*this).substitute(*Next)) | |
| Next = nullptr; | |
| NormalizedConstraintExprCache.try_emplace(Key, Next); | |
| } | |
| if (!Next) | |
| return nullptr; | |
| Normalized = | |
| Normalized | |
| ? CompoundConstraint::CreateConjunction(Context, Normalized, Next) | |
| : Next; | |
| } | |
| return Normalized; | |
| } | |
| bool FoldExpandedConstraint::AreCompatibleForSubsumption( | |
| const FoldExpandedConstraint &A, const FoldExpandedConstraint &B) { | |
| // [C++26] [temp.constr.fold] | |
| // Two fold expanded constraints are compatible for subsumption | |
| // if their respective constraints both contain an equivalent unexpanded pack. | |
| llvm::SmallVector<UnexpandedParameterPack> APacks, BPacks; | |
| Sema::collectUnexpandedParameterPacks(const_cast<Expr *>(A.getPattern()), | |
| APacks); | |
| Sema::collectUnexpandedParameterPacks(const_cast<Expr *>(B.getPattern()), | |
| BPacks); | |
| for (const UnexpandedParameterPack &APack : APacks) { | |
| auto ADI = getDepthAndIndex(APack); | |
| if (!ADI) | |
| continue; | |
| auto It = llvm::find_if(BPacks, [&](const UnexpandedParameterPack &BPack) { | |
| return getDepthAndIndex(BPack) == ADI; | |
| }); | |
| if (It != BPacks.end()) | |
| return true; | |
| } | |
| return false; | |
| } | |
| bool Sema::IsAtLeastAsConstrained(const NamedDecl *D1, | |
| MutableArrayRef<AssociatedConstraint> AC1, | |
| const NamedDecl *D2, | |
| MutableArrayRef<AssociatedConstraint> AC2, | |
| bool &Result) { | |
| #ifndef NDEBUG | |
| if (const auto *FD1 = dyn_cast<FunctionDecl>(D1)) { | |
| auto IsExpectedEntity = [](const FunctionDecl *FD) { | |
| FunctionDecl::TemplatedKind Kind = FD->getTemplatedKind(); | |
| return Kind == FunctionDecl::TK_NonTemplate || | |
| Kind == FunctionDecl::TK_FunctionTemplate || | |
| (Kind == FunctionDecl::TK_MemberSpecialization && | |
| FD->getInstantiatedFromMemberFunction() | |
| ->getOverloadedOperator() == OO_Spaceship); | |
| }; | |
| const auto *FD2 = dyn_cast<FunctionDecl>(D2); | |
| assert(IsExpectedEntity(FD1) && FD2 && IsExpectedEntity(FD2) && | |
| "use non-instantiated function declaration for constraints partial " | |
| "ordering"); | |
| } | |
| #endif | |
| if (AC1.empty()) { | |
| Result = AC2.empty(); | |
| return false; | |
| } | |
| if (AC2.empty()) { | |
| // TD1 has associated constraints and TD2 does not. | |
| Result = true; | |
| return false; | |
| } | |
| std::pair<const NamedDecl *, const NamedDecl *> Key{D1, D2}; | |
| auto CacheEntry = SubsumptionCache.find(Key); | |
| if (CacheEntry != SubsumptionCache.end()) { | |
| Result = CacheEntry->second; | |
| return false; | |
| } | |
| unsigned Depth1 = CalculateTemplateDepthForConstraints(*this, D1, true); | |
| unsigned Depth2 = CalculateTemplateDepthForConstraints(*this, D2, true); | |
| for (size_t I = 0; I != AC1.size() && I != AC2.size(); ++I) { | |
| if (Depth2 > Depth1) { | |
| AC1[I].ConstraintExpr = | |
| AdjustConstraints(*this, Depth2 - Depth1) | |
| .TransformExpr(const_cast<Expr *>(AC1[I].ConstraintExpr)) | |
| .get(); | |
| } else if (Depth1 > Depth2) { | |
| AC2[I].ConstraintExpr = | |
| AdjustConstraints(*this, Depth1 - Depth2) | |
| .TransformExpr(const_cast<Expr *>(AC2[I].ConstraintExpr)) | |
| .get(); | |
| } | |
| } | |
| SubsumptionChecker SC(*this); | |
| // Associated declarations are used as a cache key in the event they were | |
| // normalized earlier during concept checking. However we cannot reuse these | |
| // cached results if any of the template depths have been adjusted. | |
| const NamedDecl *DeclAC1 = D1, *DeclAC2 = D2; | |
| if (Depth2 > Depth1) | |
| DeclAC1 = nullptr; | |
| else if (Depth1 > Depth2) | |
| DeclAC2 = nullptr; | |
| std::optional<bool> Subsumes = SC.Subsumes(DeclAC1, AC1, DeclAC2, AC2); | |
| if (!Subsumes) { | |
| // Normalization failed | |
| return true; | |
| } | |
| Result = *Subsumes; | |
| SubsumptionCache.try_emplace(Key, *Subsumes); | |
| return false; | |
| } | |
| bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic( | |
| const NamedDecl *D1, ArrayRef<AssociatedConstraint> AC1, | |
| const NamedDecl *D2, ArrayRef<AssociatedConstraint> AC2) { | |
| if (isSFINAEContext()) | |
| // No need to work here because our notes would be discarded. | |
| return false; | |
| if (AC1.empty() || AC2.empty()) | |
| return false; | |
| const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr; | |
| auto IdenticalExprEvaluator = [&](const AtomicConstraint &A, | |
| const AtomicConstraint &B) { | |
| if (!A.hasMatchingParameterMapping(Context, B)) | |
| return false; | |
| const Expr *EA = A.getConstraintExpr(), *EB = B.getConstraintExpr(); | |
| if (EA == EB) | |
| return true; | |
| // Not the same source level expression - are the expressions | |
| // identical? | |
| llvm::FoldingSetNodeID IDA, IDB; | |
| EA->Profile(IDA, Context, /*Canonical=*/true); | |
| EB->Profile(IDB, Context, /*Canonical=*/true); | |
| if (IDA != IDB) | |
| return false; | |
| AmbiguousAtomic1 = EA; | |
| AmbiguousAtomic2 = EB; | |
| return true; | |
| }; | |
| { | |
| auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1); | |
| if (!Normalized1) | |
| return false; | |
| auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2); | |
| if (!Normalized2) | |
| return false; | |
| SubsumptionChecker SC(*this); | |
| bool Is1AtLeastAs2Normally = SC.Subsumes(Normalized1, Normalized2); | |
| bool Is2AtLeastAs1Normally = SC.Subsumes(Normalized2, Normalized1); | |
| SubsumptionChecker SC2(*this, IdenticalExprEvaluator); | |
| bool Is1AtLeastAs2 = SC2.Subsumes(Normalized1, Normalized2); | |
| bool Is2AtLeastAs1 = SC2.Subsumes(Normalized2, Normalized1); | |
| if (Is1AtLeastAs2 == Is1AtLeastAs2Normally && | |
| Is2AtLeastAs1 == Is2AtLeastAs1Normally) | |
| // Same result - no ambiguity was caused by identical atomic expressions. | |
| return false; | |
| } | |
| // A different result! Some ambiguous atomic constraint(s) caused a difference | |
| assert(AmbiguousAtomic1 && AmbiguousAtomic2); | |
| Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints) | |
| << AmbiguousAtomic1->getSourceRange(); | |
| Diag(AmbiguousAtomic2->getBeginLoc(), | |
| diag::note_ambiguous_atomic_constraints_similar_expression) | |
| << AmbiguousAtomic2->getSourceRange(); | |
| return true; | |
| } | |
| // | |
| // | |
| // ------------------------ Subsumption ----------------------------------- | |
| // | |
| // | |
| SubsumptionChecker::SubsumptionChecker(Sema &SemaRef, | |
| SubsumptionCallable Callable) | |
| : SemaRef(SemaRef), Callable(Callable), NextID(1) {} | |
| uint16_t SubsumptionChecker::getNewLiteralId() { | |
| assert((unsigned(NextID) + 1 < std::numeric_limits<uint16_t>::max()) && | |
| "too many constraints!"); | |
| return NextID++; | |
| } | |
| auto SubsumptionChecker::find(const AtomicConstraint *Ori) -> Literal { | |
| auto &Elems = AtomicMap[Ori->getConstraintExpr()]; | |
| // C++ [temp.constr.order] p2 | |
| // - an atomic constraint A subsumes another atomic constraint B | |
| // if and only if the A and B are identical [...] | |
| // | |
| // C++ [temp.constr.atomic] p2 | |
| // Two atomic constraints are identical if they are formed from the | |
| // same expression and the targets of the parameter mappings are | |
| // equivalent according to the rules for expressions [...] | |
| // Because subsumption of atomic constraints is an identity | |
| // relationship that does not require further analysis | |
| // We cache the results such that if an atomic constraint literal | |
| // subsumes another, their literal will be the same | |
| llvm::FoldingSetNodeID ID; | |
| ID.AddBoolean(Ori->hasParameterMapping()); | |
| if (Ori->hasParameterMapping()) { | |
| const auto &Mapping = Ori->getParameterMapping(); | |
| const NormalizedConstraint::OccurenceList &Indexes = | |
| Ori->mappingOccurenceListForSubsumption(); | |
| for (auto [Idx, TAL] : llvm::enumerate(Mapping)) { | |
| if (Indexes[Idx]) | |
| SemaRef.getASTContext() | |
| .getCanonicalTemplateArgument(TAL.getArgument()) | |
| .Profile(ID, SemaRef.getASTContext()); | |
| } | |
| } | |
| auto It = Elems.find(ID); | |
| if (It == Elems.end()) { | |
| It = Elems | |
| .insert({ID, | |
| MappedAtomicConstraint{ | |
| Ori, {getNewLiteralId(), Literal::Atomic}}}) | |
| .first; | |
| ReverseMap[It->second.ID.Value] = Ori; | |
| } | |
| return It->getSecond().ID; | |
| } | |
| auto SubsumptionChecker::find(const FoldExpandedConstraint *Ori) -> Literal { | |
| auto &Elems = FoldMap[Ori->getPattern()]; | |
| FoldExpendedConstraintKey K; | |
| K.Kind = Ori->getFoldOperator(); | |
| auto It = llvm::find_if(Elems, [&K](const FoldExpendedConstraintKey &Other) { | |
| return K.Kind == Other.Kind; | |
| }); | |
| if (It == Elems.end()) { | |
| K.ID = {getNewLiteralId(), Literal::FoldExpanded}; | |
| It = Elems.insert(Elems.end(), std::move(K)); | |
| ReverseMap[It->ID.Value] = Ori; | |
| } | |
| return It->ID; | |
| } | |
| auto SubsumptionChecker::CNF(const NormalizedConstraint &C) -> CNFFormula { | |
| return SubsumptionChecker::Normalize<CNFFormula>(C); | |
| } | |
| auto SubsumptionChecker::DNF(const NormalizedConstraint &C) -> DNFFormula { | |
| return SubsumptionChecker::Normalize<DNFFormula>(C); | |
| } | |
| /// | |
| /// \brief SubsumptionChecker::Normalize | |
| /// | |
| /// Normalize a formula to Conjunctive Normal Form or | |
| /// Disjunctive normal form. | |
| /// | |
| /// Each Atomic (and Fold Expanded) constraint gets represented by | |
| /// a single id to reduce space. | |
| /// | |
| /// To minimize risks of exponential blow up, if two atomic | |
| /// constraints subsumes each other (same constraint and mapping), | |
| /// they are represented by the same literal. | |
| /// | |
| template <typename FormulaType> | |
| FormulaType SubsumptionChecker::Normalize(const NormalizedConstraint &NC) { | |
| FormulaType Res; | |
| auto Add = [&, this](Clause C) { | |
| // Sort each clause and remove duplicates for faster comparisons. | |
| llvm::sort(C); | |
| C.erase(llvm::unique(C), C.end()); | |
| AddUniqueClauseToFormula(Res, std::move(C)); | |
| }; | |
| switch (NC.getKind()) { | |
| case NormalizedConstraint::ConstraintKind::Atomic: | |
| return {{find(&static_cast<const AtomicConstraint &>(NC))}}; | |
| case NormalizedConstraint::ConstraintKind::FoldExpanded: | |
| return {{find(&static_cast<const FoldExpandedConstraint &>(NC))}}; | |
| case NormalizedConstraint::ConstraintKind::ConceptId: | |
| return Normalize<FormulaType>( | |
| static_cast<const ConceptIdConstraint &>(NC).getNormalizedConstraint()); | |
| case NormalizedConstraint::ConstraintKind::Compound: { | |
| const auto &Compound = static_cast<const CompoundConstraint &>(NC); | |
| FormulaType Left, Right; | |
| SemaRef.runWithSufficientStackSpace(SourceLocation(), [&] { | |
| Left = Normalize<FormulaType>(Compound.getLHS()); | |
| Right = Normalize<FormulaType>(Compound.getRHS()); | |
| }); | |
| if (Compound.getCompoundKind() == FormulaType::Kind) { | |
| unsigned SizeLeft = Left.size(); | |
| Res = std::move(Left); | |
| Res.reserve(SizeLeft + Right.size()); | |
| std::for_each(std::make_move_iterator(Right.begin()), | |
| std::make_move_iterator(Right.end()), Add); | |
| return Res; | |
| } | |
| Res.reserve(Left.size() * Right.size()); | |
| for (const auto <ransform : Left) { | |
| for (const auto &RTransform : Right) { | |
| Clause Combined; | |
| Combined.reserve(LTransform.size() + RTransform.size()); | |
| llvm::copy(LTransform, std::back_inserter(Combined)); | |
| llvm::copy(RTransform, std::back_inserter(Combined)); | |
| Add(std::move(Combined)); | |
| } | |
| } | |
| return Res; | |
| } | |
| } | |
| llvm_unreachable("Unknown ConstraintKind enum"); | |
| } | |
| void SubsumptionChecker::AddUniqueClauseToFormula(Formula &F, Clause C) { | |
| for (auto &Other : F) { | |
| if (llvm::equal(C, Other)) | |
| return; | |
| } | |
| F.push_back(C); | |
| } | |
| std::optional<bool> SubsumptionChecker::Subsumes( | |
| const NamedDecl *DP, ArrayRef<AssociatedConstraint> P, const NamedDecl *DQ, | |
| ArrayRef<AssociatedConstraint> Q) { | |
| const NormalizedConstraint *PNormalized = | |
| SemaRef.getNormalizedAssociatedConstraints(DP, P); | |
| if (!PNormalized) | |
| return std::nullopt; | |
| const NormalizedConstraint *QNormalized = | |
| SemaRef.getNormalizedAssociatedConstraints(DQ, Q); | |
| if (!QNormalized) | |
| return std::nullopt; | |
| return Subsumes(PNormalized, QNormalized); | |
| } | |
| bool SubsumptionChecker::Subsumes(const NormalizedConstraint *P, | |
| const NormalizedConstraint *Q) { | |
| DNFFormula DNFP = DNF(*P); | |
| CNFFormula CNFQ = CNF(*Q); | |
| return Subsumes(DNFP, CNFQ); | |
| } | |
| bool SubsumptionChecker::Subsumes(const DNFFormula &PDNF, | |
| const CNFFormula &QCNF) { | |
| for (const auto &Pi : PDNF) { | |
| for (const auto &Qj : QCNF) { | |
| // C++ [temp.constr.order] p2 | |
| // - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if | |
| // and only if there exists an atomic constraint Pia in Pi for which | |
| // there exists an atomic constraint, Qjb, in Qj such that Pia | |
| // subsumes Qjb. | |
| if (!DNFSubsumes(Pi, Qj)) | |
| return false; | |
| } | |
| } | |
| return true; | |
| } | |
| bool SubsumptionChecker::DNFSubsumes(const Clause &P, const Clause &Q) { | |
| return llvm::any_of(P, [&](Literal LP) { | |
| return llvm::any_of(Q, [this, LP](Literal LQ) { return Subsumes(LP, LQ); }); | |
| }); | |
| } | |
| bool SubsumptionChecker::Subsumes(const FoldExpandedConstraint *A, | |
| const FoldExpandedConstraint *B) { | |
| std::pair<const FoldExpandedConstraint *, const FoldExpandedConstraint *> Key{ | |
| A, B}; | |
| auto It = FoldSubsumptionCache.find(Key); | |
| if (It == FoldSubsumptionCache.end()) { | |
| // C++ [temp.constr.order] | |
| // a fold expanded constraint A subsumes another fold expanded | |
| // constraint B if they are compatible for subsumption, have the same | |
| // fold-operator, and the constraint of A subsumes that of B. | |
| bool DoesSubsume = | |
| A->getFoldOperator() == B->getFoldOperator() && | |
| FoldExpandedConstraint::AreCompatibleForSubsumption(*A, *B) && | |
| Subsumes(&A->getNormalizedPattern(), &B->getNormalizedPattern()); | |
| It = FoldSubsumptionCache.try_emplace(std::move(Key), DoesSubsume).first; | |
| } | |
| return It->second; | |
| } | |
| bool SubsumptionChecker::Subsumes(Literal A, Literal B) { | |
| if (A.Kind != B.Kind) | |
| return false; | |
| switch (A.Kind) { | |
| case Literal::Atomic: | |
| if (!Callable) | |
| return A.Value == B.Value; | |
| return Callable( | |
| *static_cast<const AtomicConstraint *>(ReverseMap[A.Value]), | |
| *static_cast<const AtomicConstraint *>(ReverseMap[B.Value])); | |
| case Literal::FoldExpanded: | |
| return Subsumes( | |
| static_cast<const FoldExpandedConstraint *>(ReverseMap[A.Value]), | |
| static_cast<const FoldExpandedConstraint *>(ReverseMap[B.Value])); | |
| } | |
| llvm_unreachable("unknown literal kind"); | |
| } | |
| namespace { | |
| class DumpNormalizedConstraint { | |
| raw_ostream &OS; | |
| const PrintingPolicy &PP; | |
| TextNodeDumper TD; | |
| public: | |
| DumpNormalizedConstraint(raw_ostream &OS, ASTContext &Context) | |
| : OS(OS), PP(Context.getPrintingPolicy()), | |
| TD(OS, Context, /*ShowColors=*/false) {} | |
| void dump(const NormalizedConstraint &N) { | |
| TD.AddChild([&] { Traverse(N); }); | |
| } | |
| private: | |
| void Traverse(const NormalizedConstraint &N) { | |
| switch (N.getKind()) { | |
| case NormalizedConstraint::ConstraintKind::Compound: | |
| VisitCompound(static_cast<const CompoundConstraint &>(N)); | |
| break; | |
| case NormalizedConstraint::ConstraintKind::Atomic: | |
| VisitAtomic(static_cast<const AtomicConstraint &>(N)); | |
| break; | |
| case NormalizedConstraint::ConstraintKind::ConceptId: | |
| VisitConceptId(static_cast<const ConceptIdConstraint &>(N)); | |
| break; | |
| case NormalizedConstraint::ConstraintKind::FoldExpanded: | |
| VisitFoldExpanded(static_cast<const FoldExpandedConstraint &>(N)); | |
| break; | |
| } | |
| } | |
| void WriteNodeHeader(const NormalizedConstraint &N, StringRef Kind) { | |
| OS << Kind; | |
| TD.dumpPointer(&N); | |
| TD.dumpSourceRange(N.getSourceRange()); | |
| } | |
| void WritePackIndex(const NormalizedConstraintWithParamMapping &N) { | |
| if (auto Idx = N.getPackSubstitutionIndex()) | |
| OS << " SubstIndex=" << *Idx; | |
| } | |
| void VisitCompound(const CompoundConstraint &C) { | |
| WriteNodeHeader(C, "CompoundConstraint"); | |
| OS << " " | |
| << (C.getCompoundKind() == NormalizedConstraint::CCK_Conjunction | |
| ? "Conjunction" | |
| : "Disjunction"); | |
| TD.AddChild([&] { Traverse(C.getLHS()); }); | |
| TD.AddChild([&] { Traverse(C.getRHS()); }); | |
| } | |
| void VisitAtomic(const AtomicConstraint &A) { | |
| WriteNodeHeader(A, "AtomicConstraint"); | |
| WritePackIndex(A); | |
| OS << " "; | |
| A.getConstraintExpr()->printPretty(OS, /*Helper=*/nullptr, PP); | |
| WriteParameterMapping(A); | |
| } | |
| void VisitConceptId(const ConceptIdConstraint &C) { | |
| WriteNodeHeader(C, "ConceptIdConstraint"); | |
| WritePackIndex(C); | |
| OS << " "; | |
| if (auto *CSE = C.getConceptSpecializationExpr()) { | |
| CSE->printPretty(OS, /*Helper=*/nullptr, PP); | |
| } else { | |
| C.getConceptId()->print(OS, PP); | |
| } | |
| WriteParameterMapping(C); | |
| TD.AddChild([&] { Traverse(C.getNormalizedConstraint()); }); | |
| } | |
| void VisitFoldExpanded(const FoldExpandedConstraint &F) { | |
| WriteNodeHeader(F, "FoldExpandedConstraint"); | |
| OS << " " | |
| << (F.getFoldOperator() == FoldExpandedConstraint::FoldOperatorKind::And | |
| ? "And" | |
| : "Or"); | |
| WritePackIndex(F); | |
| OS << " "; | |
| F.getPattern()->printPretty(OS, /*Helper=*/nullptr, PP); | |
| WriteParameterMapping(F); | |
| TD.AddChild([&] { Traverse(F.getNormalizedPattern()); }); | |
| } | |
| void WriteParameterMapping(const NormalizedConstraintWithParamMapping &N) { | |
| if (!N.hasParameterMapping() || N.mappingOccurenceList().none()) | |
| return; | |
| TD.AddChild([this, Indexes(N.mappingOccurenceList()), | |
| IndexesForSub(N.mappingOccurenceListForSubsumption()), | |
| Mapping(N.getParameterMapping()), | |
| TPL(N.getUsedTemplateParamList())] { | |
| OS << "ParameterMapping"; | |
| WriteOccurenceList("Indexes", Indexes); | |
| WriteOccurenceList("IndexesForSubsumption", IndexesForSub); | |
| unsigned Slot = 0; | |
| for (unsigned ParamIndex : Indexes.set_bits()) { | |
| TD.AddChild([this, Slot, ParamIndex, Mapping, TPL] { | |
| assert(TPL && Slot < TPL->size()); | |
| const NamedDecl *Param = TPL->getParam(Slot); | |
| OS << "#" << ParamIndex << ": <"; | |
| Param->print(OS, PP); | |
| OS << "> -> "; | |
| Mapping[Slot].getArgument().print(PP, OS, | |
| /*IncludeType=*/false); | |
| TD.AddChild([this, Slot, Mapping] { | |
| const TemplateArgument &TA = Mapping[Slot].getArgument(); | |
| OS << "TemplateArgument " << TA.getKindName(); | |
| TD.dumpPointer(&TA); | |
| }); | |
| }); | |
| ++Slot; | |
| } | |
| }); | |
| } | |
| void WriteOccurenceList(StringRef Label, | |
| const NormalizedConstraint::OccurenceList &BV) { | |
| if (BV.none()) | |
| return; | |
| OS << " " << Label << "={" | |
| << llvm::join( | |
| llvm::map_range( | |
| llvm::make_range(BV.set_bits_begin(), BV.set_bits_end()), | |
| [](unsigned I) { return llvm::to_string(I); }), | |
| ", ") | |
| << '}'; | |
| } | |
| }; | |
| } // namespace | |
| LLVM_DUMP_METHOD void NormalizedConstraint::dump(ASTContext &Context) const { | |
| dump(llvm::errs(), Context); | |
| } | |
| LLVM_DUMP_METHOD void NormalizedConstraint::dump(llvm::raw_ostream &OS, | |
| ASTContext &Context) const { | |
| return DumpNormalizedConstraint(OS, Context).dump(*this); | |
| } |