llvmbot wrote:
<!--LLVM PR SUMMARY COMMENT--> @llvm/pr-subscribers-clang Author: cor3ntin (cor3ntin) <details> <summary>Changes</summary> Implement https://isocpp.org/files/papers/P2963R3.pdf --- Patch is 50.57 KiB, truncated to 20.00 KiB below, full version: https://github.com/llvm/llvm-project/pull/98160.diff 7 Files Affected: - (modified) clang/docs/ReleaseNotes.rst (+3) - (modified) clang/include/clang/Sema/Sema.h (+5) - (modified) clang/include/clang/Sema/SemaConcept.h (+125-17) - (modified) clang/lib/Sema/SemaConcept.cpp (+404-200) - (modified) clang/lib/Sema/SemaTemplateVariadic.cpp (+4) - (added) clang/test/SemaCXX/cxx2c-fold-exprs.cpp (+239) - (modified) clang/www/cxx_status.html (+1-1) ``````````diff diff --git a/clang/docs/ReleaseNotes.rst b/clang/docs/ReleaseNotes.rst index 838cb69f647ee..7d0b2115f8e53 100644 --- a/clang/docs/ReleaseNotes.rst +++ b/clang/docs/ReleaseNotes.rst @@ -271,6 +271,9 @@ C++2c Feature Support - Implemented `P3144R2 Deleting a Pointer to an Incomplete Type Should be Ill-formed <https://wg21.link/P3144R2>`_. +- Implemented `P2963R3 Ordering of constraints involving fold expressions <https://wg21.link/P2963R3>`_. + + Resolutions to C++ Defect Reports ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ - Substitute template parameter pack, when it is not explicitly specified diff --git a/clang/include/clang/Sema/Sema.h b/clang/include/clang/Sema/Sema.h index 75a80540dbcbf..4a07da6b7bfd9 100644 --- a/clang/include/clang/Sema/Sema.h +++ b/clang/include/clang/Sema/Sema.h @@ -14062,6 +14062,11 @@ class Sema final : public SemaBase { const DeclarationNameInfo &NameInfo, SmallVectorImpl<UnexpandedParameterPack> &Unexpanded); + /// Collect the set of unexpanded parameter packs within the given + /// expression. + static void collectUnexpandedParameterPacks( + Expr *E, SmallVectorImpl<UnexpandedParameterPack> &Unexpanded); + /// Invoked when parsing a template argument followed by an /// ellipsis, which creates a pack expansion. /// diff --git a/clang/include/clang/Sema/SemaConcept.h b/clang/include/clang/Sema/SemaConcept.h index 711443505174f..b6327e729768b 100644 --- a/clang/include/clang/Sema/SemaConcept.h +++ b/clang/include/clang/Sema/SemaConcept.h @@ -75,6 +75,17 @@ struct AtomicConstraint { } }; +struct FoldExpandedConstraint; + +using NormalFormConstraint = + llvm::PointerUnion<AtomicConstraint *, FoldExpandedConstraint *>; +struct NormalizedConstraint; +using NormalForm = + llvm::SmallVector<llvm::SmallVector<NormalFormConstraint, 2>, 4>; + +NormalForm makeCNF(const NormalizedConstraint &Normalized); +NormalForm makeDNF(const NormalizedConstraint &Normalized); + /// \brief A normalized constraint, as defined in C++ [temp.constr.normal], is /// either an atomic constraint, a conjunction of normalized constraints or a /// disjunction of normalized constraints. @@ -87,26 +98,17 @@ struct NormalizedConstraint { std::pair<NormalizedConstraint, NormalizedConstraint> *, 1, CompoundConstraintKind>; - llvm::PointerUnion<AtomicConstraint *, CompoundConstraint> Constraint; + llvm::PointerUnion<AtomicConstraint *, FoldExpandedConstraint *, + CompoundConstraint> + Constraint; NormalizedConstraint(AtomicConstraint *C): Constraint{C} { }; + NormalizedConstraint(FoldExpandedConstraint *C) : Constraint{C} {}; + NormalizedConstraint(ASTContext &C, NormalizedConstraint LHS, - NormalizedConstraint RHS, CompoundConstraintKind Kind) - : Constraint{CompoundConstraint{ - new (C) std::pair<NormalizedConstraint, NormalizedConstraint>{ - std::move(LHS), std::move(RHS)}, Kind}} { }; - - NormalizedConstraint(ASTContext &C, const NormalizedConstraint &Other) { - if (Other.isAtomic()) { - Constraint = new (C) AtomicConstraint(*Other.getAtomicConstraint()); - } else { - Constraint = CompoundConstraint( - new (C) std::pair<NormalizedConstraint, NormalizedConstraint>{ - NormalizedConstraint(C, Other.getLHS()), - NormalizedConstraint(C, Other.getRHS())}, - Other.getCompoundKind()); - } - } + NormalizedConstraint RHS, CompoundConstraintKind Kind); + + NormalizedConstraint(ASTContext &C, const NormalizedConstraint &Other); NormalizedConstraint(NormalizedConstraint &&Other): Constraint(Other.Constraint) { Other.Constraint = nullptr; @@ -126,6 +128,9 @@ struct NormalizedConstraint { } bool isAtomic() const { return Constraint.is<AtomicConstraint *>(); } + bool isFoldExpanded() const { + return Constraint.is<FoldExpandedConstraint *>(); + } NormalizedConstraint &getLHS() const { assert(!isAtomic() && "getLHS called on atomic constraint."); @@ -143,6 +148,12 @@ struct NormalizedConstraint { return Constraint.get<AtomicConstraint *>(); } + FoldExpandedConstraint *getFoldExpandedConstraint() const { + assert(isFoldExpanded() && + "getFoldExpandedConstraint called on non-fold-expanded constraint."); + return Constraint.get<FoldExpandedConstraint *>(); + } + private: static std::optional<NormalizedConstraint> fromConstraintExprs(Sema &S, NamedDecl *D, ArrayRef<const Expr *> E); @@ -150,6 +161,103 @@ struct NormalizedConstraint { fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E); }; +struct FoldExpandedConstraint { + enum class FoldOperatorKind { FoAnd, FoOr } Kind; + NormalizedConstraint Constraint; + const Expr *Pattern; + + FoldExpandedConstraint(FoldOperatorKind K, NormalizedConstraint C, + const Expr *Pattern) + : Kind(K), Constraint(std::move(C)), Pattern(Pattern) {}; + + template <typename AtomicSubsumptionEvaluator> + bool subsumes(const FoldExpandedConstraint &Other, + AtomicSubsumptionEvaluator E) const; + + static bool AreSubsumptionElligible(const FoldExpandedConstraint &A, + const FoldExpandedConstraint &B); +}; + +const NormalizedConstraint *getNormalizedAssociatedConstraints( + Sema &S, NamedDecl *ConstrainedDecl, + ArrayRef<const Expr *> AssociatedConstraints); + +template <typename AtomicSubsumptionEvaluator> +bool subsumes(const NormalForm &PDNF, const NormalForm &QCNF, + AtomicSubsumptionEvaluator E) { + // C++ [temp.constr.order] p2 + // Then, P subsumes Q if and only if, for every disjunctive clause Pi in the + // disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in + // the conjuctive normal form of Q, where [...] + 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. + bool Found = false; + for (NormalFormConstraint Pia : Pi) { + for (NormalFormConstraint Qjb : Qj) { + if (Pia.is<FoldExpandedConstraint *>() && + Qjb.is<FoldExpandedConstraint *>()) { + if (Pia.get<FoldExpandedConstraint *>()->subsumes( + *Qjb.get<FoldExpandedConstraint *>(), E)) { + Found = true; + break; + } + } else if (Pia.is<AtomicConstraint *>() && + Qjb.is<AtomicConstraint *>()) { + if (E(*Pia.get<AtomicConstraint *>(), + *Qjb.get<AtomicConstraint *>())) { + Found = true; + break; + } + } + } + if (Found) + break; + } + if (!Found) + return false; + } + } + return true; +} + +template <typename AtomicSubsumptionEvaluator> +bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P, NamedDecl *DQ, + ArrayRef<const Expr *> Q, bool &Subsumes, + AtomicSubsumptionEvaluator E) { + // C++ [temp.constr.order] p2 + // In order to determine if a constraint P subsumes a constraint Q, P is + // transformed into disjunctive normal form, and Q is transformed into + // conjunctive normal form. [...] + auto *PNormalized = getNormalizedAssociatedConstraints(S, DP, P); + if (!PNormalized) + return true; + const NormalForm PDNF = makeDNF(*PNormalized); + + auto *QNormalized = getNormalizedAssociatedConstraints(S, DQ, Q); + if (!QNormalized) + return true; + const NormalForm QCNF = makeCNF(*QNormalized); + + Subsumes = subsumes(PDNF, QCNF, E); + return false; +} + +template <typename AtomicSubsumptionEvaluator> +bool FoldExpandedConstraint::subsumes(const FoldExpandedConstraint &Other, + AtomicSubsumptionEvaluator E) const { + if (Kind != Other.Kind || !AreSubsumptionElligible(*this, Other)) + return false; + + const NormalForm PDNF = makeDNF(this->Constraint); + const NormalForm QCNF = makeCNF(Other.Constraint); + return clang::subsumes(PDNF, QCNF, E); +} + } // clang #endif // LLVM_CLANG_SEMA_SEMACONCEPT_H diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp index 202dd86c67f62..b86e2d51e380b 100644 --- a/clang/lib/Sema/SemaConcept.cpp +++ b/clang/lib/Sema/SemaConcept.cpp @@ -65,6 +65,7 @@ class LogicalBinOp { 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())); @@ -177,65 +178,160 @@ struct SatisfactionStackRAII { }; } // namespace -template <typename AtomicEvaluator> +template <typename ConstraintEvaluator> static ExprResult calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction, - AtomicEvaluator &&Evaluator) { - ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts(); + ConstraintEvaluator &&Evaluator); - if (LogicalBinOp BO = ConstraintExpr) { - size_t EffectiveDetailEndIndex = Satisfaction.Details.size(); - ExprResult LHSRes = calculateConstraintSatisfaction( - S, BO.getLHS(), Satisfaction, Evaluator); +template <typename ConstraintEvaluator> +static ExprResult calculateConstraintSatisfaction( + Sema &S, const Expr *LHS, OverloadedOperatorKind Op, const Expr *RHS, + ConstraintSatisfaction &Satisfaction, ConstraintEvaluator &Evaluator) { + size_t EffectiveDetailEndIndex = Satisfaction.Details.size(); - if (LHSRes.isInvalid()) - return ExprError(); + ExprResult LHSRes = + calculateConstraintSatisfaction(S, LHS, Satisfaction, Evaluator); - bool IsLHSSatisfied = Satisfaction.IsSatisfied; + if (LHSRes.isInvalid()) + return ExprError(); - if (BO.isOr() && IsLHSSatisfied) - // [temp.constr.op] p3 - // A disjunction is a constraint taking two operands. To determine if - // a disjunction is satisfied, the satisfaction of the first operand - // is checked. If that is satisfied, the disjunction is satisfied. - // Otherwise, the disjunction is satisfied if and only if the second - // operand is satisfied. - // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp. - return LHSRes; - - if (BO.isAnd() && !IsLHSSatisfied) - // [temp.constr.op] p2 - // A conjunction is a constraint taking two operands. To determine if - // a conjunction is satisfied, the satisfaction of the first operand - // is checked. If that is not satisfied, the conjunction is not - // satisfied. Otherwise, the conjunction is satisfied if and only if - // the second operand is satisfied. - // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp. - return LHSRes; - - ExprResult RHSRes = calculateConstraintSatisfaction( - S, BO.getRHS(), Satisfaction, std::forward<AtomicEvaluator>(Evaluator)); - if (RHSRes.isInvalid()) - return ExprError(); + bool IsLHSSatisfied = Satisfaction.IsSatisfied; + + if (Op == clang::OO_PipePipe && IsLHSSatisfied) + // [temp.constr.op] p3 + // A disjunction is a constraint taking two operands. To determine if + // a disjunction is satisfied, the satisfaction of the first operand + // is checked. If that is satisfied, the disjunction is satisfied. + // Otherwise, the disjunction is satisfied if and only if the second + // operand is satisfied. + // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp. + return LHSRes; + + if (Op == clang::OO_AmpAmp && !IsLHSSatisfied) + // [temp.constr.op] p2 + // A conjunction is a constraint taking two operands. To determine if + // a conjunction is satisfied, the satisfaction of the first operand + // is checked. If that is not satisfied, the conjunction is not + // satisfied. Otherwise, the conjunction is satisfied if and only if + // the second operand is satisfied. + // LHS is instantiated while RHS is not. Skip creating invalid BinaryOp. + return LHSRes; + + ExprResult RHSRes = calculateConstraintSatisfaction( + S, RHS, Satisfaction, std::forward<ConstraintEvaluator>(Evaluator)); + if (RHSRes.isInvalid()) + return ExprError(); + + bool IsRHSSatisfied = Satisfaction.IsSatisfied; + // Current implementation adds diagnostic information about the falsity + // of each false atomic constraint expression when it evaluates them. + // When the evaluation results to `false || true`, the information + // generated during the evaluation of left-hand side is meaningless + // because the whole expression evaluates to true. + // The following code removes the irrelevant diagnostic information. + // FIXME: We should probably delay the addition of diagnostic information + // until we know the entire expression is false. + if (Op == clang::OO_PipePipe && IsRHSSatisfied) { + auto EffectiveDetailEnd = Satisfaction.Details.begin(); + std::advance(EffectiveDetailEnd, EffectiveDetailEndIndex); + Satisfaction.Details.erase(EffectiveDetailEnd, Satisfaction.Details.end()); + } + if (!LHSRes.isUsable() || !RHSRes.isUsable()) + return ExprEmpty(); + + return BinaryOperator::Create(S.Context, LHSRes.get(), RHSRes.get(), + BinaryOperator::getOverloadedOpcode(Op), + S.Context.BoolTy, VK_PRValue, OK_Ordinary, + LHS->getBeginLoc(), FPOptionsOverride{}); +} + +template <typename ConstraintEvaluator> +static ExprResult +calculateConstraintSatisfaction(Sema &S, const CXXFoldExpr *FE, + ConstraintSatisfaction &Satisfaction, + ConstraintEvaluator &&Evaluator) { + bool Conjunction = FE->getOperator() == BinaryOperatorKind::BO_LAnd; + size_t EffectiveDetailEndIndex = Satisfaction.Details.size(); + + ExprResult Out; + if (FE->isLeftFold() && FE->getInit()) { + Out = calculateConstraintSatisfaction(S, FE->getInit(), Satisfaction, + Evaluator); + if (Out.isInvalid()) + return ExprError(); + bool IsLHSSatisfied = Satisfaction.IsSatisfied; + if (Conjunction && !IsLHSSatisfied) { + return Out; + } + if (!Conjunction && IsLHSSatisfied) { + return Out; + } + } + std::optional<unsigned> NumExpansions = + Evaluator.EvaluateFoldExpandedConstraintSize(FE); + if (!NumExpansions) + return ExprError(); + for (unsigned I = 0; I < *NumExpansions; I++) { + Sema::ArgumentPackSubstitutionIndexRAII SubstIndex(S, I); + ExprResult Res = calculateConstraintSatisfaction(S, FE->getPattern(), + Satisfaction, Evaluator); + if (Res.isInvalid()) + return ExprError(); bool IsRHSSatisfied = Satisfaction.IsSatisfied; - // Current implementation adds diagnostic information about the falsity - // of each false atomic constraint expression when it evaluates them. - // When the evaluation results to `false || true`, the information - // generated during the evaluation of left-hand side is meaningless - // because the whole expression evaluates to true. - // The following code removes the irrelevant diagnostic information. - // FIXME: We should probably delay the addition of diagnostic information - // until we know the entire expression is false. - if (BO.isOr() && IsRHSSatisfied) { + if (!Conjunction && IsRHSSatisfied) { auto EffectiveDetailEnd = Satisfaction.Details.begin(); std::advance(EffectiveDetailEnd, EffectiveDetailEndIndex); Satisfaction.Details.erase(EffectiveDetailEnd, Satisfaction.Details.end()); } + if (Out.isUnset()) + Out = Res; + else if (!Res.isUnset()) { + Out = BinaryOperator::Create( + S.Context, Out.get(), Res.get(), FE->getOperator(), S.Context.BoolTy, + VK_PRValue, OK_Ordinary, FE->getBeginLoc(), FPOptionsOverride{}); + } + if (Conjunction && !IsRHSSatisfied) + return Out; + if (!Conjunction && IsRHSSatisfied) + return Out; + } + + if (FE->isRightFold() && FE->getInit()) { + ExprResult Res = calculateConstraintSatisfaction(S, FE->getInit(), + Satisfaction, Evaluator); + if (Out.isInvalid()) + return ExprError(); + + if (Out.isUnset()) + Out = Res; + else if (!Res.isUnset()) { + Out = BinaryOperator::Create( + S.Context, Out.get(), Res.get(), FE->getOperator(), S.Context.BoolTy, + VK_PRValue, OK_Ordinary, FE->getBeginLoc(), FPOptionsOverride{}); + } + } - return BO.recreateBinOp(S, LHSRes, RHSRes); + if (Out.isUnset()) { + Satisfaction.IsSatisfied = Conjunction; + Out = S.BuildEmptyCXXFoldExpr(FE->getBeginLoc(), FE->getOperator()); + } + return Out; +} + +template <typename ConstraintEvaluator> +static ExprResult +calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr, + ConstraintSatisfaction &Satisfaction, + ConstraintEvaluator &&Evaluator) { + ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts(); + + if (LogicalBinOp BO = ConstraintExpr) { + + return calculateConstraintSatisfaction( + S, BO.getLHS(), BO.getOp(), BO.getRHS(), Satisfaction, Evaluator); } if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) { @@ -243,11 +339,19 @@ calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr, // evaluate these as if the cleanups didn't exist. return calculateConstraintSatisfaction( S, C->getSubExpr(), Satisfaction, - std::forward<AtomicEvaluator>(Evaluator)); + std::forward<ConstraintEvaluator>(Evaluator)); + } + + if (auto *FE = dyn_cast<CXXFoldExpr>(ConstraintExpr); + FE && S.getLangOpts().CPlusPlus26 && + (FE->getOperator() == BinaryOperatorKind::BO_LAnd || + FE->getOperator() == BinaryOperatorKind::BO_LOr)) { + return calculateConstraintSatisfaction(S, FE, Satisfaction, Evaluator); } // An atomic constraint expression - ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr); + ExprResult SubstitutedAtomicExpr = + Evaluator.EvaluateAtomicConstraint(ConstraintExpr); if (SubstitutedAtomicExpr.isInvalid()) return ExprError(); @@ -336,92 +440,133 @@ static ExprResult calculateConstraintSatisfaction( Sema &S, const NamedDecl *Template, SourceLocation TemplateNameLoc, const MultiLevelTemplateArgumentList &MLTAL, const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction) { - return calculateConstraintSatisfaction( - S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) { - EnterExpressionEvaluationContext ConstantEvaluated( - S, Sema::ExpressionEvaluationContext::ConstantEvaluated, - Sema::ReuseLambdaContextDecl); - - // Atomic constraint - substitute arguments and check satisfaction. - ExprResult SubstitutedExpression; - { - TemplateDeductionInfo Info(TemplateNameLoc); - Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(), - Sema::InstantiatingTemplate::ConstraintSubstitution{}, - const_cast<NamedDecl *>(Template), Info, - AtomicExpr->getSourceRange()); - if (Inst.isInvalid()) + + struct ConstraintEvaluator { + Sema &S; + const NamedDecl *Template; + SourceLocation TemplateNameLoc; + const MultiLevelTemplateArgumentList &MLTAL; + ConstraintSatisfaction &Satisfaction; + + ExprResult EvaluateAtomicConstraint(const Expr *AtomicExpr) { + EnterExpressionEvaluationContext ConstantEvaluated( + S, Sema::ExpressionEvaluationContext::ConstantEvaluated, + Sema::ReuseLambdaContextDecl); + + // Atomic constraint - substitute arguments and check satisfaction... [truncated] `````````` </details> https://github.com/llvm/llvm-project/pull/98160 _______________________________________________ cfe-commits mailing list cfe-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
