https://github.com/cor3ntin updated
https://github.com/llvm/llvm-project/pull/132849
>From b5b5275093f6942238536834c6508551f7ceffd8 Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Sun, 16 Mar 2025 23:34:19 +0100
Subject: [PATCH 1/2] [Clang] Improve subsumption.
The main goal of this patch is to improve the
performance of concept subsumption by
- Making sure literal (atomic) clauses are de-duplicated
(Whether 2 atomic constraint is established during the
initial normal form production).
- Eagerly removing redundant clauses.
This should minimize the risks of exponentially-large
that can be produced by a naive {C,D}NF transformation.
While at it, I restructured that part of the code to be a bit
clearer.
Subsumption of fold expanded constraint is also cached.
---
Note that removing redundant clauses (even naively)
seems to be necessary and sufficient to have acceptable performance
on anything that could be construed as reasonable code.
Ultimately, the number of clauses is always going to be fairly
small (but $2^{fairly\ small}$ is quickly fairly large..).
I went too far in the rabbit hole of Tseitin transformations etc,
which was much faster but would then require to check satisfiabiliy
to establish subsumption between some constraints (although it was
good enough to pass all but ones of our tests...).
It doesn't help that the C++ standard has a very specific
definition of subsumption that is really more of an implication...
While that sort of musing is fascinating, it was ultimately a fool's
errand, at least until such time that there is more motivation for
a SAT solver in clang (clang-tidy can after all use z3!).
Here be dragons.
Fixes #122581
---
clang/docs/ReleaseNotes.rst | 1 +
clang/include/clang/Sema/SemaConcept.h | 225 +++++-----
clang/lib/Sema/SemaConcept.cpp | 452 +++++++++++++++-----
clang/test/SemaCXX/concepts-subsumption.cpp | 194 +++++++++
4 files changed, 636 insertions(+), 236 deletions(-)
create mode 100644 clang/test/SemaCXX/concepts-subsumption.cpp
diff --git a/clang/docs/ReleaseNotes.rst b/clang/docs/ReleaseNotes.rst
index 2f15c90ab1583..05bde5c9cc1d1 100644
--- a/clang/docs/ReleaseNotes.rst
+++ b/clang/docs/ReleaseNotes.rst
@@ -358,6 +358,7 @@ Bug Fixes to C++ Support
- Fixed a Clang regression in C++20 mode where unresolved dependent call
expressions were created inside non-dependent contexts (#GH122892)
- Clang now emits the ``-Wunused-variable`` warning when some structured
bindings are unused
and the ``[[maybe_unused]]`` attribute is not applied. (#GH125810)
+- Clang no longer crash when establishing subsumption between some constraint
expressions. (#GH122581)
Bug Fixes to AST Handling
^^^^^^^^^^^^^^^^^^^^^^^^^
diff --git a/clang/include/clang/Sema/SemaConcept.h
b/clang/include/clang/Sema/SemaConcept.h
index 5c599a70532f6..87fee1678fb05 100644
--- a/clang/include/clang/Sema/SemaConcept.h
+++ b/clang/include/clang/Sema/SemaConcept.h
@@ -14,13 +14,14 @@
#define LLVM_CLANG_SEMA_SEMACONCEPT_H
#include "clang/AST/ASTConcept.h"
#include "clang/AST/ASTContext.h"
-#include "clang/AST/Expr.h"
#include "clang/AST/DeclTemplate.h"
+#include "clang/AST/Expr.h"
#include "clang/Basic/SourceLocation.h"
+#include "llvm/ADT/FoldingSet.h"
#include "llvm/ADT/PointerUnion.h"
+#include "llvm/ADT/STLFunctionalExtras.h"
#include "llvm/ADT/SmallVector.h"
#include <optional>
-#include <string>
#include <utility>
namespace clang {
@@ -56,49 +57,10 @@ struct alignas(ConstraintAlignment) AtomicConstraint {
}
return true;
}
-
- bool subsumes(ASTContext &C, const AtomicConstraint &Other) const {
- // 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 [...]
-
- // We do not actually substitute the parameter mappings into the
- // constraint expressions, therefore the constraint expressions are
- // the originals, and comparing them will suffice.
- if (ConstraintExpr != Other.ConstraintExpr)
- return false;
-
- // Check that the parameter lists are identical
- return hasMatchingParameterMapping(C, Other);
- }
};
-struct alignas(ConstraintAlignment) FoldExpandedConstraint;
-
-using NormalFormConstraint =
- llvm::PointerUnion<AtomicConstraint *, FoldExpandedConstraint *>;
-struct NormalizedConstraint;
-using NormalForm =
- llvm::SmallVector<llvm::SmallVector<NormalFormConstraint, 2>, 4>;
-
-// A constraint is in conjunctive normal form when it is a conjunction of
-// clauses where each clause is a disjunction of atomic constraints. For atomic
-// constraints A, B, and C, the constraint A ∧ (B ∨ C) is in conjunctive
-// normal form.
-NormalForm makeCNF(const NormalizedConstraint &Normalized);
-
-// A constraint is in disjunctive normal form when it is a disjunction of
-// clauses where each clause is a conjunction of atomic constraints. For atomic
-// constraints A, B, and C, the disjunctive normal form of the constraint A
-// ∧ (B ∨ C) is (A ∧ B) ∨ (A ∧ C).
-NormalForm makeDNF(const NormalizedConstraint &Normalized);
-
struct alignas(ConstraintAlignment) NormalizedConstraintPair;
+struct alignas(ConstraintAlignment) FoldExpandedConstraint;
/// \brief A normalized constraint, as defined in C++ [temp.constr.normal], is
/// either an atomic constraint, a conjunction of normalized constraints or a
@@ -170,102 +132,113 @@ struct alignas(ConstraintAlignment)
FoldExpandedConstraint {
const Expr *Pattern)
: Kind(K), Constraint(std::move(C)), Pattern(Pattern) {};
- template <typename AtomicSubsumptionEvaluator>
- bool subsumes(const FoldExpandedConstraint &Other,
- const AtomicSubsumptionEvaluator &E) const;
-
static bool AreCompatibleForSubsumption(const FoldExpandedConstraint &A,
const FoldExpandedConstraint &B);
+
+ llvm::FoldingSetNodeID ProfileForSubsumption() const;
};
const NormalizedConstraint *getNormalizedAssociatedConstraints(
Sema &S, NamedDecl *ConstrainedDecl,
ArrayRef<const Expr *> AssociatedConstraints);
-template <typename AtomicSubsumptionEvaluator>
-bool subsumes(const NormalForm &PDNF, const NormalForm &QCNF,
- const 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 (isa<FoldExpandedConstraint *>(Pia) &&
- isa<FoldExpandedConstraint *>(Qjb)) {
- if (cast<FoldExpandedConstraint *>(Pia)->subsumes(
- *cast<FoldExpandedConstraint *>(Qjb), E)) {
- Found = true;
- break;
- }
- } else if (isa<AtomicConstraint *>(Pia) &&
- isa<AtomicConstraint *>(Qjb)) {
- if (E(*cast<AtomicConstraint *>(Pia),
- *cast<AtomicConstraint *>(Qjb))) {
- 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,
- const 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. [...]
- const NormalizedConstraint *PNormalized =
- getNormalizedAssociatedConstraints(S, DP, P);
- if (!PNormalized)
- return true;
- NormalForm PDNF = makeDNF(*PNormalized);
+/// \brief SubsumptionChecker establishes subsumption
+/// between two set of constraints.
+class SubsumptionChecker {
+public:
+ using SubsumptionCallable = llvm::function_ref<bool(
+ const AtomicConstraint &, const AtomicConstraint &)>;
- const NormalizedConstraint *QNormalized =
- getNormalizedAssociatedConstraints(S, DQ, Q);
- if (!QNormalized)
- return true;
- NormalForm QCNF = makeCNF(*QNormalized);
-
- Subsumes = subsumes(PDNF, QCNF, E);
- return false;
-}
-
-template <typename AtomicSubsumptionEvaluator>
-bool FoldExpandedConstraint::subsumes(
- const FoldExpandedConstraint &Other,
- const AtomicSubsumptionEvaluator &E) const {
+ SubsumptionChecker(Sema &SemaRef, SubsumptionCallable Callable = {});
- // [C++26] [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
+ std::optional<bool> Subsumes(NamedDecl *DP, ArrayRef<const Expr *> P,
+ NamedDecl *DQ, ArrayRef<const Expr *> Q);
- if (Kind != Other.Kind || !AreCompatibleForSubsumption(*this, Other))
- return false;
+ bool Subsumes(const NormalizedConstraint *P, const NormalizedConstraint *Q);
- NormalForm PDNF = makeDNF(this->Constraint);
- NormalForm QCNF = makeCNF(Other.Constraint);
- return clang::subsumes(PDNF, QCNF, E);
-}
+private:
+ Sema &SemaRef;
+ SubsumptionCallable Callable;
+
+ // Each Literal has a unique value that is enough to establish
+ // its identity.
+ // Some constraints (fold expended) requires special subsumption
+ // handling logic beyond comparing values, so we store a flag
+ // to let us quickly dispatch to each kind of variable.
+ struct Literal {
+ enum Kind { Atomic, FoldExpanded };
+
+ unsigned Value : 16;
+ LLVM_PREFERRED_TYPE(Kind)
+ unsigned Kind : 1;
+
+ bool operator==(const Literal &Other) const { return Value == Other.Value;
}
+ bool operator<(const Literal &Other) const { return Value < Other.Value; }
+ };
+ using Clause = llvm::SmallVector<Literal>;
+ using Formula = llvm::SmallVector<Clause, 5>;
+
+ struct CNFFormula : Formula {
+ static constexpr auto Kind = NormalizedConstraint::CCK_Conjunction;
+ using Formula::Formula;
+ };
+ struct DNFFormula : Formula {
+ static constexpr auto Kind = NormalizedConstraint::CCK_Disjunction;
+ using Formula::Formula;
+ };
+
+ struct MappedAtomicConstraint {
+ AtomicConstraint *Constraint;
+ Literal ID;
+ };
+
+ struct FoldExpendedConstraintKey {
+ FoldExpandedConstraint::FoldOperatorKind Kind;
+ AtomicConstraint *Constraint;
+ Literal ID;
+ };
+
+ llvm::DenseMap<const Expr *, llvm::SmallDenseMap<llvm::FoldingSetNodeID,
+ MappedAtomicConstraint>>
+ AtomicMap;
+
+ llvm::DenseMap<const Expr *, std::vector<FoldExpendedConstraintKey>> FoldMap;
+
+ // A map from a literal to a corresponding associated constraint.
+ // We do not have enough bits left for a pointer union here :(
+ llvm::DenseMap<uint16_t, void *> ReverseMap;
+
+ // Fold expanded constraints ask us to recursively establish subsumption.
+ // This caches the result.
+ llvm::SmallDenseMap<
+ std::pair<const FoldExpandedConstraint *, const FoldExpandedConstraint
*>,
+ bool>
+ FoldSubsumptionCache;
+
+ // Each <atomic, fold expanded constraint> is represented as a single ID.
+ // This is intentionally kept small we can't handle a large number of
+ // constraints anyway.
+ uint16_t NextID;
+
+ bool Subsumes(const DNFFormula &P, const CNFFormula &Q);
+ bool Subsumes(Literal A, Literal B);
+ bool Subsumes(const FoldExpandedConstraint *A,
+ const FoldExpandedConstraint *B);
+ bool DNFSubsumes(const Clause &P, const Clause &Q);
+
+ CNFFormula CNF(const NormalizedConstraint &C);
+ DNFFormula DNF(const NormalizedConstraint &C);
+
+ template <typename FormulaType>
+ FormulaType Normalize(const NormalizedConstraint &C);
+ void AddClauseToFormula(Formula &F, Clause C);
+ bool IsSuperSet(const Clause &A, const Clause &B);
+
+ Literal find(AtomicConstraint *);
+ Literal find(FoldExpandedConstraint *);
+
+ uint16_t getNewId();
+};
} // clang
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index 57dc4154a537f..b16dac9c08dec 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -1726,71 +1726,6 @@ bool FoldExpandedConstraint::AreCompatibleForSubsumption(
return false;
}
-NormalForm clang::makeCNF(const NormalizedConstraint &Normalized) {
- if (Normalized.isAtomic())
- return {{Normalized.getAtomicConstraint()}};
-
- else if (Normalized.isFoldExpanded())
- return {{Normalized.getFoldExpandedConstraint()}};
-
- NormalForm LCNF = makeCNF(Normalized.getLHS());
- NormalForm RCNF = makeCNF(Normalized.getRHS());
- if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
- LCNF.reserve(LCNF.size() + RCNF.size());
- while (!RCNF.empty())
- LCNF.push_back(RCNF.pop_back_val());
- return LCNF;
- }
-
- // Disjunction
- NormalForm Res;
- Res.reserve(LCNF.size() * RCNF.size());
- for (auto &LDisjunction : LCNF)
- for (auto &RDisjunction : RCNF) {
- NormalForm::value_type Combined;
- Combined.reserve(LDisjunction.size() + RDisjunction.size());
- std::copy(LDisjunction.begin(), LDisjunction.end(),
- std::back_inserter(Combined));
- std::copy(RDisjunction.begin(), RDisjunction.end(),
- std::back_inserter(Combined));
- Res.emplace_back(Combined);
- }
- return Res;
-}
-
-NormalForm clang::makeDNF(const NormalizedConstraint &Normalized) {
- if (Normalized.isAtomic())
- return {{Normalized.getAtomicConstraint()}};
-
- else if (Normalized.isFoldExpanded())
- return {{Normalized.getFoldExpandedConstraint()}};
-
- NormalForm LDNF = makeDNF(Normalized.getLHS());
- NormalForm RDNF = makeDNF(Normalized.getRHS());
- if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
- LDNF.reserve(LDNF.size() + RDNF.size());
- while (!RDNF.empty())
- LDNF.push_back(RDNF.pop_back_val());
- return LDNF;
- }
-
- // Conjunction
- NormalForm Res;
- Res.reserve(LDNF.size() * RDNF.size());
- for (auto &LConjunction : LDNF) {
- for (auto &RConjunction : RDNF) {
- NormalForm::value_type Combined;
- Combined.reserve(LConjunction.size() + RConjunction.size());
- std::copy(LConjunction.begin(), LConjunction.end(),
- std::back_inserter(Combined));
- std::copy(RConjunction.begin(), RConjunction.end(),
- std::back_inserter(Combined));
- Res.emplace_back(Combined);
- }
- }
- return Res;
-}
-
bool Sema::IsAtLeastAsConstrained(NamedDecl *D1,
MutableArrayRef<const Expr *> AC1,
NamedDecl *D2,
@@ -1842,18 +1777,21 @@ bool Sema::IsAtLeastAsConstrained(NamedDecl *D1,
}
}
- if (clang::subsumes(
- *this, D1, AC1, D2, AC2, Result,
- [this](const AtomicConstraint &A, const AtomicConstraint &B) {
- return A.subsumes(Context, B);
- }))
+ SubsumptionChecker SC(*this);
+ std::optional<bool> Subsumes = SC.Subsumes(D1, AC1, D2, AC2);
+ if (!Subsumes) {
+ // Normalization failed
return true;
- SubsumptionCache.try_emplace(Key, Result);
+ }
+ Result = *Subsumes;
+ SubsumptionCache.try_emplace(Key, *Subsumes);
return false;
}
-bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
- ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) {
+bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(
+ NamedDecl *D1, ArrayRef<const Expr *> AC1, NamedDecl *D2,
+ ArrayRef<const Expr *> AC2) {
+
if (isSFINAEContext())
// No need to work here because our notes would be discarded.
return false;
@@ -1861,32 +1799,27 @@ bool
Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
if (AC1.empty() || AC2.empty())
return false;
- auto NormalExprEvaluator =
- [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
- return A.subsumes(Context, B);
- };
-
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.ConstraintExpr, *EB = B.ConstraintExpr;
- 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 IdenticalExprEvaluator = [&](const AtomicConstraint &A,
+ const AtomicConstraint &B) {
+ if (!A.hasMatchingParameterMapping(Context, B))
+ return false;
+ const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
+ 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;
+ };
{
// The subsumption checks might cause diagnostics
@@ -1894,27 +1827,25 @@ bool
Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1);
if (!Normalized1)
return false;
- const NormalForm DNF1 = makeDNF(*Normalized1);
- const NormalForm CNF1 = makeCNF(*Normalized1);
auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2);
if (!Normalized2)
return false;
- const NormalForm DNF2 = makeDNF(*Normalized2);
- const NormalForm CNF2 = makeCNF(*Normalized2);
-
- bool Is1AtLeastAs2Normally =
- clang::subsumes(DNF1, CNF2, NormalExprEvaluator);
- bool Is2AtLeastAs1Normally =
- clang::subsumes(DNF2, CNF1, NormalExprEvaluator);
- bool Is1AtLeastAs2 = clang::subsumes(DNF1, CNF2, IdenticalExprEvaluator);
- bool Is2AtLeastAs1 = clang::subsumes(DNF2, CNF1, IdenticalExprEvaluator);
+
+ 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);
@@ -2001,3 +1932,304 @@ NormalizedConstraint::getFoldExpandedConstraint() const
{
"getFoldExpandedConstraint called on non-fold-expanded constraint.");
return cast<FoldExpandedConstraint *>(Constraint);
}
+
+//
+//
+// -------------------------------------------------------------------------
+//
+//
+
+/// \name Subsumption
+
+template <> struct llvm::DenseMapInfo<llvm::FoldingSetNodeID> {
+
+ static FoldingSetNodeID getEmptyKey() {
+ FoldingSetNodeID id;
+ id.AddInteger(std::numeric_limits<unsigned>::max());
+ return id;
+ }
+
+ static FoldingSetNodeID getTombstoneKey() {
+ FoldingSetNodeID id;
+ for (size_t i = 0; i < sizeof(id) / sizeof(unsigned); ++i) {
+ id.AddInteger(std::numeric_limits<unsigned>::max());
+ }
+ return id;
+ }
+
+ static unsigned getHashValue(const FoldingSetNodeID &Val) {
+ return Val.ComputeHash();
+ }
+
+ static bool isEqual(const FoldingSetNodeID &LHS,
+ const FoldingSetNodeID &RHS) {
+ return LHS == RHS;
+ }
+};
+
+SubsumptionChecker::SubsumptionChecker(Sema &SemaRef,
+ SubsumptionCallable Callable)
+ : SemaRef(SemaRef), Callable(Callable), NextID(1) {}
+
+auto SubsumptionChecker::getNewId() -> uint16_t {
+ assert((unsigned(NextID) + 1 < std::numeric_limits<uint16_t>::max()) &&
+ "too many constraints!");
+ return NextID++;
+}
+
+auto SubsumptionChecker::find(AtomicConstraint *Ori) -> Literal {
+ auto &Elems = AtomicMap[Ori->ConstraintExpr];
+ // 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;
+ const auto &Mapping = Ori->ParameterMapping;
+ ID.AddBoolean(Mapping.has_value());
+ if (Mapping) {
+ for (unsigned I = 0, S = Mapping->size(); I < S; ++I) {
+ SemaRef.getASTContext()
+ .getCanonicalTemplateArgument((*Mapping)[I].getArgument())
+ .Profile(ID, SemaRef.getASTContext());
+ }
+ }
+ auto It = Elems.find(ID);
+ if (It == Elems.end()) {
+ It =
+ Elems
+ .insert({ID, MappedAtomicConstraint{Ori, Literal{getNewId(),
+
Literal::Atomic}}})
+ .first;
+ ReverseMap[It->second.ID.Value] = Ori;
+ }
+ return It->getSecond().ID;
+}
+
+auto SubsumptionChecker::find(FoldExpandedConstraint *Ori) -> Literal {
+ auto &Elems = FoldMap[Ori->Pattern];
+
+ FoldExpendedConstraintKey K;
+ K.Kind = Ori->Kind;
+
+ auto It = llvm::find_if(Elems, [&K](const FoldExpendedConstraintKey &Other) {
+ return K.Kind == Other.Kind;
+ });
+ if (It == Elems.end()) {
+ K.ID = {getNewId(), 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.
+///
+/// Redundant clauses (ie clauses that are fully subsumed) by other
+/// clauses in the same formula are removed.
+template <typename FormulaType>
+FormulaType SubsumptionChecker::Normalize(const NormalizedConstraint &NC) {
+ FormulaType Res;
+
+ auto Add = [&Res, this](Clause C, bool RemoveRedundantClause) {
+ // Sort each clause and remove duplicates for faster comparision
+ // Both AddClauseToFormula and IsSuperSet require sorted, uniqued literals.
+ std::sort(C.begin(), C.end());
+ C.erase(std::unique(C.begin(), C.end()), C.end());
+
+ if (RemoveRedundantClause)
+ AddClauseToFormula(Res, std::move(C));
+ else
+ Res.push_back(std::move(C));
+ };
+
+ if (NC.isAtomic())
+ return {{find(NC.getAtomicConstraint())}};
+
+ if (NC.isFoldExpanded())
+ return {{find(NC.getFoldExpandedConstraint())}};
+
+ FormulaType Left, Right;
+ SemaRef.runWithSufficientStackSpace(SourceLocation(), [&] {
+ Left = Normalize<FormulaType>(NC.getLHS());
+ Right = Normalize<FormulaType>(NC.getRHS());
+ });
+
+ if (NC.getCompoundKind() == FormulaType::Kind) {
+ Res = std::move(Left);
+ Res.reserve(Left.size() + Right.size());
+ std::for_each(std::make_move_iterator(Right.begin()),
+ std::make_move_iterator(Right.end()), [&](Clause C) {
+ Add(std::move(C),
+ FormulaType::Kind ==
+ NormalizedConstraint::CCK_Disjunction);
+ });
+ 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());
+ std::copy(LTransform.begin(), LTransform.end(),
+ std::back_inserter(Combined));
+ std::copy(RTransform.begin(), RTransform.end(),
+ std::back_inserter(Combined));
+ Add(std::move(Combined),
+ FormulaType::Kind == NormalizedConstraint::CCK_Conjunction);
+ }
+ }
+ return Res;
+}
+
+// Remove redundant clauses.
+// This is fairly crude, but we expect the number of clauses to be
+// small-ish and the number of literals to be small
+void SubsumptionChecker::AddClauseToFormula(Formula &F, Clause C) {
+ bool Added = false;
+ for (auto &Other : F) {
+ // Forward subsume: nothing to do
+ if (IsSuperSet(Other, C))
+ return;
+ // Backward subsume: replace other clauses
+ if (IsSuperSet(C, Other)) {
+ Other = C;
+ Added = true;
+ }
+ }
+ if (!Added)
+ F.push_back(C);
+}
+
+bool SubsumptionChecker::IsSuperSet(const Clause &A, const Clause &B) {
+ if (B.size() > A.size())
+ return false;
+ Clause::const_iterator At = A.begin();
+ Clause::const_iterator Bt = B.begin();
+ for (; At != A.end() && Bt != B.end();) {
+ if (At->Value == Bt->Value) {
+ At++;
+ Bt++;
+ continue;
+ }
+ if (At->Value < Bt->Value) {
+ At++;
+ continue;
+ }
+ return false;
+ }
+ return Bt == B.end();
+}
+
+std::optional<bool> SubsumptionChecker::Subsumes(NamedDecl *DP,
+ ArrayRef<const Expr *> P,
+ NamedDecl *DQ,
+ ArrayRef<const Expr *> Q) {
+ const NormalizedConstraint *PNormalized =
+ getNormalizedAssociatedConstraints(SemaRef, DP, P);
+ if (!PNormalized)
+ return std::nullopt;
+
+ const NormalizedConstraint *QNormalized =
+ getNormalizedAssociatedConstraints(SemaRef, 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 Bif they are compatible for subsumption, have the same
+ // fold-operator, and the constraint of A subsumes that of B.
+ bool DoesSubsumes =
+ A->Kind == B->Kind &&
+ FoldExpandedConstraint::AreCompatibleForSubsumption(*A, *B) &&
+ Subsumes(&A->Constraint, &B->Constraint);
+ It = FoldSubsumptionCache.try_emplace(std::move(Key), DoesSubsumes).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");
+}
diff --git a/clang/test/SemaCXX/concepts-subsumption.cpp
b/clang/test/SemaCXX/concepts-subsumption.cpp
new file mode 100644
index 0000000000000..1732c4c946446
--- /dev/null
+++ b/clang/test/SemaCXX/concepts-subsumption.cpp
@@ -0,0 +1,194 @@
+// RUN: %clang_cc1 -fsyntax-only -verify -std=c++20 %s
+
+namespace A {
+template <typename T>
+concept C = true;
+
+template <typename T>
+requires C<T> && C<T>
+void f() {}
+
+template <typename T>
+requires C<T> && true
+void f() {}
+
+template <>
+void f<int>();
+}
+
+namespace B {
+template <typename T>
+concept A = true;
+template <typename T>
+concept B = true;
+
+template <typename T>
+requires (A<T> && B<T>)
+constexpr int f() { return 0; }
+
+template <typename T>
+requires (A<T> || B<T>)
+constexpr int f() { return 1; }
+
+static_assert(f<int>() == 0);
+}
+
+namespace GH122581 {
+// Test that producing a Conjunctive Normal Form
+// does not blow up exponentially.
+// i.e, this should terminate reasonably quickly
+// within a small memory footprint
+template <typename T> concept C0 = true;
+template <typename T> concept C1 = true;
+template <typename T> concept C2 = true;
+template <typename T> concept C3 = true;
+template <typename T> concept C4 = true;
+
+template <typename T>
+concept majority5 =
+ (C0<T> && C1<T> && C2<T>) ||
+ (C0<T> && C1<T> && C3<T>) ||
+ (C0<T> && C1<T> && C4<T>) ||
+ (C0<T> && C2<T> && C3<T>) ||
+ (C0<T> && C2<T> && C4<T>) ||
+ (C0<T> && C3<T> && C4<T>) ||
+ (C1<T> && C2<T> && C3<T>) ||
+ (C1<T> && C2<T> && C4<T>) ||
+ (C1<T> && C3<T> && C4<T>) ||
+ (C2<T> && C3<T> && C4<T>);
+
+template <typename T>concept Y = C0<T> && majority5<T>;
+template <typename T>concept Z = Y<T> && C1<T>;
+
+constexpr int foo(majority5 auto x) { return 10; }
+constexpr int foo(Y auto y) { return 20; }
+constexpr int foo(Z auto y) { return 30; }
+static_assert(foo(0) == 30);
+}
+
+namespace WhateverThisIs {
+template <typename T> concept C0 = true;
+template <typename T> concept C1 = true;
+template <typename T> concept C2 = true;
+template <typename T> concept C3 = true;
+template <typename T> concept C4 = true;
+
+template <typename T>
+concept X =
+ (C0<T> || C1<T> || C2<T>) &&
+ (C0<T> || C1<T> || C3<T>) &&
+ (C0<T> || C1<T> || C4<T>) &&
+ (C0<T> || C2<T> || C3<T>) &&
+ (C0<T> || C2<T> || C4<T>) &&
+ (C0<T> || C3<T> || C4<T>) &&
+ (C1<T> || C2<T> || C3<T>) &&
+ (C1<T> || C2<T> || C4<T>) &&
+ (C1<T> || C3<T> || C4<T>) &&
+ (C2<T> || C3<T> || C4<T>);
+
+template <typename T>concept Y = C0<T> && X<T>;
+
+template <typename T>concept Z = Y<T> && C1<T>;
+
+constexpr int foo(X auto x) { return 10; }
+constexpr int foo(Y auto y) { return 20; }
+constexpr int foo(Z auto y) { return 30; }
+
+static_assert(foo(0) == 30);
+}
+
+namespace WAT{
+template<typename T>
+concept Z0 = true;
+
+template<typename T>
+concept Z1 = true;
+
+template<typename T>
+concept Z2 = true;
+
+template<typename T>
+concept Z3 = true;
+
+template<typename T>
+concept Z4 = true;
+
+template<typename T>
+concept Z5 = true;
+
+template<typename T>
+concept Z6 = true;
+
+template<typename T>
+concept Z7 = true;
+
+template<typename T>
+concept Z8 = true;
+
+template<typename T>
+concept Z9 = true;
+
+template <typename T>
+concept X =
+ ((((((Z6<T> || Z2<T>)&&Z3<T>)&&(Z2<T> || ((Z2<T> || Z3<T>)&&Z8<T>))) ||
+ ((Z0<T> || Z9<T>) ||
+ (Z7<T> || ((Z3<T> || (Z9<T> && Z4<T>)) || Z2<T>)))) ||
+ ((Z9<T> && (Z7<T> && (Z3<T> || Z2<T>))) ||
+ (((Z7<T> || (Z3<T> || Z2<T>)) && ((Z0<T> && Z9<T>)&&(Z1<T> || Z0<T>)))
||
+ (Z5<T> || (Z1<T> && Z8<T>))))) &&
+ (((((((Z8<T> || (((Z5<T> && Z6<T>)&&(Z4<T> || Z2<T>)) ||
+ (Z8<T> && (Z8<T> && Z7<T>)))) ||
+ ((Z1<T> && (Z2<T> || Z6<T>)) || Z4<T>)) &&
+ Z8<T>)&&((((((Z6<T> && (Z4<T> || Z3<T>)) ||
+ Z1<T>)&&(Z0<T> && ((Z9<T> && Z6<T>) || Z4<T>))) &&
+ Z0<T>) ||
+ ((Z5<T> || Z8<T>)&&((Z7<T> || (Z6<T> && Z5<T>)) ||
+ (Z2<T> || (Z3<T> && Z9<T>))))) &&
+ ((((Z2<T> || (Z7<T> || (Z4<T> || Z3<T>))) ||
+ (Z0<T> && Z3<T>)) ||
+ (Z7<T> ||
+ ((Z3<T> || (Z3<T> && (Z3<T> || Z0<T>))) && Z6<T>))) &&
+ ((Z9<T> && Z7<T>) ||
+ (Z4<T> && (((Z7<T> || Z1<T>) || Z4<T>) || Z3<T>))))))
&&
+ (((Z1<T> || (((Z0<T> && (Z1<T> || Z5<T>)) && (Z2<T> || Z1<T>)) ||
+ (Z0<T> && ((Z0<T> && Z7<T>)&&Z5<T>)))) &&
+ (Z3<T> && (Z1<T> && (Z9<T> && Z1<T>)))) &&
+ (((((Z4<T> && Z3<T>) ||
+ Z0<T>)&&((Z3<T> || (Z4<T> || Z1<T>)) && Z6<T>)) &&
+ Z4<T>)&&((((Z6<T> || ((Z3<T> || Z4<T>) || Z7<T>)) ||
+ Z0<T>)&&Z2<T>) ||
+ Z0<T>)))) ||
+ (((Z5<T> && ((Z0<T> || Z5<T>)&&(Z3<T> && ((Z1<T> && Z9<T>)&&Z4<T>))))
||
+ (Z2<T> || Z8<T>)) ||
+ (((Z6<T> || Z1<T>) || ((Z6<T> && ((Z6<T> || Z9<T>) || Z8<T>)) ||
+ ((Z7<T> || Z6<T>)&&(Z7<T> || Z4<T>)))) &&
+ ((((((Z4<T> && Z8<T>) || Z1<T>) ||
+ (((Z6<T> || Z3<T>)&&(Z9<T> || Z1<T>)) ||
+ (Z1<T> && (Z0<T> || Z4<T>)))) ||
+ (((Z8<T> && (Z1<T> && Z0<T>)) || Z3<T>) ||
+ (((((Z5<T> && Z1<T>)&&((Z6<T> && Z7<T>)&&(Z0<T> || Z5<T>))) ||
+ (Z0<T> && ((Z2<T> || Z1<T>)&&Z3<T>))) ||
+ (Z6<T> && (Z2<T> || Z4<T>))) ||
+ Z5<T>))) ||
+ (((Z9<T> && Z1<T>) || (Z4<T> && Z6<T>)) &&
+ (((Z6<T> || Z1<T>) || ((Z4<T> && Z2<T>) || Z5<T>)) ||
+ ((Z5<T> && Z9<T>)&&Z3<T>)))) &&
+ (((Z5<T> && (Z7<T> || Z3<T>)) && Z9<T>) || (Z0<T> || Z4<T>)))))) ||
+ ((((Z8<T> && (Z1<T> || Z9<T>)) &&
+ ((Z4<T> && Z2<T>) ||
+ ((Z2<T> || ((Z9<T> && Z7<T>) || Z0<T>)) && Z2<T>))) &&
+ (((Z0<T> && Z9<T>)&&Z9<T>)&&(Z6<T> && Z5<T>))) &&
+ (((((Z7<T> || Z5<T>) || Z6<T>) ||
+ ((Z7<T> || (Z0<T> && Z8<T>)) ||
+ ((Z5<T> && (Z3<T> && Z1<T>)) && Z5<T>))) ||
+ Z0<T>)&&((Z9<T> && Z7<T>)&&Z4<T>)))));
+
+template<typename T>
+concept Y = Z0<T> && X<T>;
+
+constexpr int foo(X auto x) { return 1; } // expected-note{{candidate
function}}
+
+constexpr int foo(Y auto y) { return 2; } // expected-note{{candidate
function}}
+
+static_assert(foo(0) == 3); // expected-error {{call to 'foo' is ambiguous}}
+}
>From 4fd7da811706ea6617e23a799f91ab9b0228b55e Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Tue, 25 Mar 2025 12:02:02 +0100
Subject: [PATCH 2/2] apply feedback, fix a test case
---
clang/docs/ReleaseNotes.rst | 2 +-
clang/include/clang/Sema/SemaConcept.h | 11 ++--
clang/lib/Sema/SemaConcept.cpp | 66 +++++++++++++--------
clang/test/SemaCXX/concepts-subsumption.cpp | 14 +++--
4 files changed, 56 insertions(+), 37 deletions(-)
diff --git a/clang/docs/ReleaseNotes.rst b/clang/docs/ReleaseNotes.rst
index 05bde5c9cc1d1..53f5d11583916 100644
--- a/clang/docs/ReleaseNotes.rst
+++ b/clang/docs/ReleaseNotes.rst
@@ -358,7 +358,7 @@ Bug Fixes to C++ Support
- Fixed a Clang regression in C++20 mode where unresolved dependent call
expressions were created inside non-dependent contexts (#GH122892)
- Clang now emits the ``-Wunused-variable`` warning when some structured
bindings are unused
and the ``[[maybe_unused]]`` attribute is not applied. (#GH125810)
-- Clang no longer crash when establishing subsumption between some constraint
expressions. (#GH122581)
+- Clang no longer crashes when establishing subsumption between some
constraint expressions. (#GH122581)
Bug Fixes to AST Handling
^^^^^^^^^^^^^^^^^^^^^^^^^
diff --git a/clang/include/clang/Sema/SemaConcept.h
b/clang/include/clang/Sema/SemaConcept.h
index 87fee1678fb05..af6672c1719df 100644
--- a/clang/include/clang/Sema/SemaConcept.h
+++ b/clang/include/clang/Sema/SemaConcept.h
@@ -162,7 +162,7 @@ class SubsumptionChecker {
// Each Literal has a unique value that is enough to establish
// its identity.
- // Some constraints (fold expended) requires special subsumption
+ // Some constraints (fold expended) require special subsumption
// handling logic beyond comparing values, so we store a flag
// to let us quickly dispatch to each kind of variable.
struct Literal {
@@ -230,14 +230,17 @@ class SubsumptionChecker {
DNFFormula DNF(const NormalizedConstraint &C);
template <typename FormulaType>
- FormulaType Normalize(const NormalizedConstraint &C);
- void AddClauseToFormula(Formula &F, Clause C);
+ FormulaType
+ Normalize(const NormalizedConstraint &C,
+ NormalizedConstraint::CompoundConstraintKind ParentKind);
+ void AddNonRedundantClauseToFormula(Formula &F, Clause C);
+ void AddUniqueClauseToFormula(Formula &F, Clause C);
bool IsSuperSet(const Clause &A, const Clause &B);
Literal find(AtomicConstraint *);
Literal find(FoldExpandedConstraint *);
- uint16_t getNewId();
+ uint16_t getNewLiteralId();
};
} // clang
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index b16dac9c08dec..dc6c2b336a3d6 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -1935,26 +1935,24 @@ NormalizedConstraint::getFoldExpandedConstraint() const
{
//
//
-// -------------------------------------------------------------------------
+// ------------------------ Subsumption -----------------------------------
//
//
-/// \name Subsumption
-
template <> struct llvm::DenseMapInfo<llvm::FoldingSetNodeID> {
static FoldingSetNodeID getEmptyKey() {
- FoldingSetNodeID id;
- id.AddInteger(std::numeric_limits<unsigned>::max());
- return id;
+ FoldingSetNodeID ID;
+ ID.AddInteger(std::numeric_limits<unsigned>::max());
+ return ID;
}
static FoldingSetNodeID getTombstoneKey() {
- FoldingSetNodeID id;
- for (size_t i = 0; i < sizeof(id) / sizeof(unsigned); ++i) {
- id.AddInteger(std::numeric_limits<unsigned>::max());
+ FoldingSetNodeID ID;
+ for (unsigned I = 0; I < sizeof(ID) / sizeof(unsigned); ++I) {
+ ID.AddInteger(std::numeric_limits<unsigned>::max());
}
- return id;
+ return ID;
}
static unsigned getHashValue(const FoldingSetNodeID &Val) {
@@ -1971,7 +1969,7 @@ SubsumptionChecker::SubsumptionChecker(Sema &SemaRef,
SubsumptionCallable Callable)
: SemaRef(SemaRef), Callable(Callable), NextID(1) {}
-auto SubsumptionChecker::getNewId() -> uint16_t {
+uint16_t SubsumptionChecker::getNewLiteralId() {
assert((unsigned(NextID) + 1 < std::numeric_limits<uint16_t>::max()) &&
"too many constraints!");
return NextID++;
@@ -2007,7 +2005,7 @@ auto SubsumptionChecker::find(AtomicConstraint *Ori) ->
Literal {
if (It == Elems.end()) {
It =
Elems
- .insert({ID, MappedAtomicConstraint{Ori, Literal{getNewId(),
+ .insert({ID, MappedAtomicConstraint{Ori, Literal{getNewLiteralId(),
Literal::Atomic}}})
.first;
ReverseMap[It->second.ID.Value] = Ori;
@@ -2025,7 +2023,7 @@ auto SubsumptionChecker::find(FoldExpandedConstraint
*Ori) -> Literal {
return K.Kind == Other.Kind;
});
if (It == Elems.end()) {
- K.ID = {getNewId(), Literal::FoldExpanded};
+ K.ID = {getNewLiteralId(), Literal::FoldExpanded};
It = Elems.insert(Elems.end(), std::move(K));
ReverseMap[It->ID.Value] = Ori;
}
@@ -2033,10 +2031,10 @@ auto SubsumptionChecker::find(FoldExpandedConstraint
*Ori) -> Literal {
}
auto SubsumptionChecker::CNF(const NormalizedConstraint &C) -> CNFFormula {
- return SubsumptionChecker::Normalize<CNFFormula>(C);
+ return SubsumptionChecker::Normalize<CNFFormula>(C, DNFFormula::Kind);
}
auto SubsumptionChecker::DNF(const NormalizedConstraint &C) -> DNFFormula {
- return SubsumptionChecker::Normalize<DNFFormula>(C);
+ return SubsumptionChecker::Normalize<DNFFormula>(C, DNFFormula::Kind);
}
///
@@ -2055,19 +2053,26 @@ auto SubsumptionChecker::DNF(const NormalizedConstraint
&C) -> DNFFormula {
/// Redundant clauses (ie clauses that are fully subsumed) by other
/// clauses in the same formula are removed.
template <typename FormulaType>
-FormulaType SubsumptionChecker::Normalize(const NormalizedConstraint &NC) {
+FormulaType SubsumptionChecker::Normalize(
+ const NormalizedConstraint &NC,
+ NormalizedConstraint::CompoundConstraintKind ParentKind) {
FormulaType Res;
- auto Add = [&Res, this](Clause C, bool RemoveRedundantClause) {
+ bool ParentWillDoCrossProduct = ParentKind != FormulaType::Kind;
+
+ auto Add = [&, this](Clause C, bool RemoveRedundantClause) {
// Sort each clause and remove duplicates for faster comparision
// Both AddClauseToFormula and IsSuperSet require sorted, uniqued literals.
std::sort(C.begin(), C.end());
C.erase(std::unique(C.begin(), C.end()), C.end());
- if (RemoveRedundantClause)
- AddClauseToFormula(Res, std::move(C));
+ // Because the caller may produce the cross product of the clauses
+ // we need to be careful not to remove clauses that could be
+ // combined by the parent.
+ if (!ParentWillDoCrossProduct && RemoveRedundantClause)
+ AddNonRedundantClauseToFormula(Res, std::move(C));
else
- Res.push_back(std::move(C));
+ AddUniqueClauseToFormula(Res, std::move(C));
};
if (NC.isAtomic())
@@ -2078,8 +2083,8 @@ FormulaType SubsumptionChecker::Normalize(const
NormalizedConstraint &NC) {
FormulaType Left, Right;
SemaRef.runWithSufficientStackSpace(SourceLocation(), [&] {
- Left = Normalize<FormulaType>(NC.getLHS());
- Right = Normalize<FormulaType>(NC.getRHS());
+ Left = Normalize<FormulaType>(NC.getLHS(), NC.getCompoundKind());
+ Right = Normalize<FormulaType>(NC.getRHS(), NC.getCompoundKind());
});
if (NC.getCompoundKind() == FormulaType::Kind) {
@@ -2113,7 +2118,7 @@ FormulaType SubsumptionChecker::Normalize(const
NormalizedConstraint &NC) {
// Remove redundant clauses.
// This is fairly crude, but we expect the number of clauses to be
// small-ish and the number of literals to be small
-void SubsumptionChecker::AddClauseToFormula(Formula &F, Clause C) {
+void SubsumptionChecker::AddNonRedundantClauseToFormula(Formula &F, Clause C) {
bool Added = false;
for (auto &Other : F) {
// Forward subsume: nothing to do
@@ -2129,6 +2134,14 @@ void SubsumptionChecker::AddClauseToFormula(Formula &F,
Clause C) {
F.push_back(C);
}
+void SubsumptionChecker::AddUniqueClauseToFormula(Formula &F, Clause C) {
+ for (auto &Other : F) {
+ if (llvm::equal(C, Other))
+ return;
+ }
+ F.push_back(C);
+}
+
bool SubsumptionChecker::IsSuperSet(const Clause &A, const Clause &B) {
if (B.size() > A.size())
return false;
@@ -2201,17 +2214,18 @@ 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 Bif they are compatible for subsumption, have the same
+ // constraint B if they are compatible for subsumption, have the same
// fold-operator, and the constraint of A subsumes that of B.
- bool DoesSubsumes =
+ bool DoesSubsume =
A->Kind == B->Kind &&
FoldExpandedConstraint::AreCompatibleForSubsumption(*A, *B) &&
Subsumes(&A->Constraint, &B->Constraint);
- It = FoldSubsumptionCache.try_emplace(std::move(Key), DoesSubsumes).first;
+ It = FoldSubsumptionCache.try_emplace(std::move(Key), DoesSubsume).first;
}
return It->second;
}
diff --git a/clang/test/SemaCXX/concepts-subsumption.cpp
b/clang/test/SemaCXX/concepts-subsumption.cpp
index 1732c4c946446..9fce374221d6f 100644
--- a/clang/test/SemaCXX/concepts-subsumption.cpp
+++ b/clang/test/SemaCXX/concepts-subsumption.cpp
@@ -1,5 +1,5 @@
// RUN: %clang_cc1 -fsyntax-only -verify -std=c++20 %s
-
+// expected-no-diagnostics
namespace A {
template <typename T>
concept C = true;
@@ -98,6 +98,10 @@ static_assert(foo(0) == 30);
}
namespace WAT{
+// user-provided formula that is misshandled by clang 20,
+// and some other compilers. There is no particular meaning
+// to it except to stress-test the compiler.
+
template<typename T>
concept Z0 = true;
@@ -186,9 +190,7 @@ concept X =
template<typename T>
concept Y = Z0<T> && X<T>;
-constexpr int foo(X auto x) { return 1; } // expected-note{{candidate
function}}
-
-constexpr int foo(Y auto y) { return 2; } // expected-note{{candidate
function}}
-
-static_assert(foo(0) == 3); // expected-error {{call to 'foo' is ambiguous}}
+constexpr int foo(X auto x) { return 1; }
+constexpr int foo(Y auto y) { return 2; }
+static_assert(foo(0) == 2);
}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
