https://github.com/cor3ntin created
https://github.com/llvm/llvm-project/pull/132849
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 formulas 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
>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] [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}}
+}
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
