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 01/12] [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 02/12] 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);
}
>From a8b171879a5891729a466444014a8e2feb21b369 Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Tue, 25 Mar 2025 12:26:58 +0100
Subject: [PATCH 03/12] Do not remove redundant clauses if we could produce
their cross product
---
clang/include/clang/Sema/SemaConcept.h | 2 +-
clang/lib/Sema/SemaConcept.cpp | 15 ++++++---------
2 files changed, 7 insertions(+), 10 deletions(-)
diff --git a/clang/include/clang/Sema/SemaConcept.h
b/clang/include/clang/Sema/SemaConcept.h
index af6672c1719df..696fc4b97a1be 100644
--- a/clang/include/clang/Sema/SemaConcept.h
+++ b/clang/include/clang/Sema/SemaConcept.h
@@ -232,7 +232,7 @@ class SubsumptionChecker {
template <typename FormulaType>
FormulaType
Normalize(const NormalizedConstraint &C,
- NormalizedConstraint::CompoundConstraintKind ParentKind);
+ bool ParentWillDoCrossProduct);
void AddNonRedundantClauseToFormula(Formula &F, Clause C);
void AddUniqueClauseToFormula(Formula &F, Clause C);
bool IsSuperSet(const Clause &A, const Clause &B);
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index dc6c2b336a3d6..d89b778817785 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -2031,10 +2031,10 @@ auto SubsumptionChecker::find(FoldExpandedConstraint
*Ori) -> Literal {
}
auto SubsumptionChecker::CNF(const NormalizedConstraint &C) -> CNFFormula {
- return SubsumptionChecker::Normalize<CNFFormula>(C, DNFFormula::Kind);
+ return SubsumptionChecker::Normalize<CNFFormula>(C,
/*ParentWillDoCrossProduct=*/false);
}
auto SubsumptionChecker::DNF(const NormalizedConstraint &C) -> DNFFormula {
- return SubsumptionChecker::Normalize<DNFFormula>(C, DNFFormula::Kind);
+ return SubsumptionChecker::Normalize<DNFFormula>(C,
/*ParentWillDoCrossProduct=*/false);
}
///
@@ -2053,13 +2053,10 @@ 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,
- NormalizedConstraint::CompoundConstraintKind ParentKind) {
+FormulaType SubsumptionChecker::Normalize(const NormalizedConstraint &NC,
+ bool ParentWillDoCrossProduct) {
FormulaType Res;
- 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.
@@ -2083,8 +2080,8 @@ FormulaType SubsumptionChecker::Normalize(
FormulaType Left, Right;
SemaRef.runWithSufficientStackSpace(SourceLocation(), [&] {
- Left = Normalize<FormulaType>(NC.getLHS(), NC.getCompoundKind());
- Right = Normalize<FormulaType>(NC.getRHS(), NC.getCompoundKind());
+ Left = Normalize<FormulaType>(NC.getLHS(), ParentWillDoCrossProduct ||
NC.getCompoundKind() != FormulaType::Kind);
+ Right = Normalize<FormulaType>(NC.getRHS(), ParentWillDoCrossProduct ||
NC.getCompoundKind() != FormulaType::Kind);
});
if (NC.getCompoundKind() == FormulaType::Kind) {
>From 89d4851dc81ed27706e1c7fd7522c4d5fd4c1074 Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Tue, 25 Mar 2025 12:45:54 +0100
Subject: [PATCH 04/12] Apply feedback
---
clang/lib/Sema/SemaConcept.cpp | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index d89b778817785..54974156809e7 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -2144,7 +2144,7 @@ bool SubsumptionChecker::IsSuperSet(const Clause &A,
const Clause &B) {
return false;
Clause::const_iterator At = A.begin();
Clause::const_iterator Bt = B.begin();
- for (; At != A.end() && Bt != B.end();) {
+ while (At != A.end() && Bt != B.end()) {
if (At->Value == Bt->Value) {
At++;
Bt++;
>From 85bc6c94d60d9532e573f39bc876a281bbdb7411 Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Tue, 25 Mar 2025 13:09:43 +0100
Subject: [PATCH 05/12] Cleanup tests
---
clang/test/SemaCXX/concepts-subsumption.cpp | 237 ++++++++++++++------
1 file changed, 167 insertions(+), 70 deletions(-)
diff --git a/clang/test/SemaCXX/concepts-subsumption.cpp
b/clang/test/SemaCXX/concepts-subsumption.cpp
index 9fce374221d6f..a5d813f8a9b05 100644
--- a/clang/test/SemaCXX/concepts-subsumption.cpp
+++ b/clang/test/SemaCXX/concepts-subsumption.cpp
@@ -43,24 +43,89 @@ 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 C5 = true;
+template <typename T> concept C6 = true;
+template <typename T> concept C7 = true;
+template <typename T> concept C8 = true;
+template <typename T> concept C9 = 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>;
+concept Majority8 =
+ (C0<T> && C1<T> && C2<T> && C3<T>) ||
+ (C0<T> && C1<T> && C2<T> && C4<T>) ||
+ (C0<T> && C1<T> && C2<T> && C5<T>) ||
+ (C0<T> && C1<T> && C2<T> && C6<T>) ||
+ (C0<T> && C1<T> && C2<T> && C7<T>) ||
+ (C0<T> && C1<T> && C3<T> && C4<T>) ||
+ (C0<T> && C1<T> && C3<T> && C5<T>) ||
+ (C0<T> && C1<T> && C3<T> && C6<T>) ||
+ (C0<T> && C1<T> && C3<T> && C7<T>) ||
+ (C0<T> && C1<T> && C4<T> && C5<T>) ||
+ (C0<T> && C1<T> && C4<T> && C6<T>) ||
+ (C0<T> && C1<T> && C4<T> && C7<T>) ||
+ (C0<T> && C1<T> && C5<T> && C6<T>) ||
+ (C0<T> && C1<T> && C5<T> && C7<T>) ||
+ (C0<T> && C1<T> && C6<T> && C7<T>) ||
+ (C0<T> && C2<T> && C3<T> && C4<T>) ||
+ (C0<T> && C2<T> && C3<T> && C5<T>) ||
+ (C0<T> && C2<T> && C3<T> && C6<T>) ||
+ (C0<T> && C2<T> && C3<T> && C7<T>) ||
+ (C0<T> && C2<T> && C4<T> && C5<T>) ||
+ (C0<T> && C2<T> && C4<T> && C6<T>) ||
+ (C0<T> && C2<T> && C4<T> && C7<T>) ||
+ (C0<T> && C2<T> && C5<T> && C6<T>) ||
+ (C0<T> && C2<T> && C5<T> && C7<T>) ||
+ (C0<T> && C2<T> && C6<T> && C7<T>) ||
+ (C0<T> && C3<T> && C4<T> && C5<T>) ||
+ (C0<T> && C3<T> && C4<T> && C6<T>) ||
+ (C0<T> && C3<T> && C4<T> && C7<T>) ||
+ (C0<T> && C3<T> && C5<T> && C6<T>) ||
+ (C0<T> && C3<T> && C5<T> && C7<T>) ||
+ (C0<T> && C3<T> && C6<T> && C7<T>) ||
+ (C0<T> && C4<T> && C5<T> && C6<T>) ||
+ (C0<T> && C4<T> && C5<T> && C7<T>) ||
+ (C0<T> && C4<T> && C6<T> && C7<T>) ||
+ (C0<T> && C5<T> && C6<T> && C7<T>) ||
+ (C1<T> && C2<T> && C3<T> && C4<T>) ||
+ (C1<T> && C2<T> && C3<T> && C5<T>) ||
+ (C1<T> && C2<T> && C3<T> && C6<T>) ||
+ (C1<T> && C2<T> && C3<T> && C7<T>) ||
+ (C1<T> && C2<T> && C4<T> && C5<T>) ||
+ (C1<T> && C2<T> && C4<T> && C6<T>) ||
+ (C1<T> && C2<T> && C4<T> && C7<T>) ||
+ (C1<T> && C2<T> && C5<T> && C6<T>) ||
+ (C1<T> && C2<T> && C5<T> && C7<T>) ||
+ (C1<T> && C2<T> && C6<T> && C7<T>) ||
+ (C1<T> && C3<T> && C4<T> && C5<T>) ||
+ (C1<T> && C3<T> && C4<T> && C6<T>) ||
+ (C1<T> && C3<T> && C4<T> && C7<T>) ||
+ (C1<T> && C3<T> && C5<T> && C6<T>) ||
+ (C1<T> && C3<T> && C5<T> && C7<T>) ||
+ (C1<T> && C3<T> && C6<T> && C7<T>) ||
+ (C1<T> && C4<T> && C5<T> && C6<T>) ||
+ (C1<T> && C4<T> && C5<T> && C7<T>) ||
+ (C1<T> && C4<T> && C6<T> && C7<T>) ||
+ (C1<T> && C5<T> && C6<T> && C7<T>) ||
+ (C2<T> && C3<T> && C4<T> && C5<T>) ||
+ (C2<T> && C3<T> && C4<T> && C6<T>) ||
+ (C2<T> && C3<T> && C4<T> && C7<T>) ||
+ (C2<T> && C3<T> && C5<T> && C6<T>) ||
+ (C2<T> && C3<T> && C5<T> && C7<T>) ||
+ (C2<T> && C3<T> && C6<T> && C7<T>) ||
+ (C2<T> && C4<T> && C5<T> && C6<T>) ||
+ (C2<T> && C4<T> && C5<T> && C7<T>) ||
+ (C2<T> && C4<T> && C6<T> && C7<T>) ||
+ (C2<T> && C5<T> && C6<T> && C7<T>) ||
+ (C3<T> && C4<T> && C5<T> && C6<T>) ||
+ (C3<T> && C4<T> && C5<T> && C7<T>) ||
+ (C3<T> && C4<T> && C6<T> && C7<T>) ||
+ (C3<T> && C5<T> && C6<T> && C7<T>) ||
+ (C4<T> && C5<T> && C6<T> && C7<T>);
+
+template <typename T>concept Y = C0<T> || Majority8<T>;
+template <typename T>concept Z = Majority8<T> && C1<T>;
-constexpr int foo(majority5 auto x) { return 10; }
+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);
@@ -98,7 +163,7 @@ static_assert(foo(0) == 30);
}
namespace WAT{
-// user-provided formula that is misshandled by clang 20,
+// randomly generated formulas misshandled by clang 20,
// and some other compilers. There is no particular meaning
// to it except to stress-test the compiler.
@@ -132,60 +197,58 @@ 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 Z10 = true;
+
+template<typename T>
+concept Z11 = true;
+
+template<typename T>
+concept Z12 = true;
+
+template<typename T>
+concept Z13 = true;
+
+template<typename T>
+concept Z14 = true;
+
+template<typename T>
+concept Z15 = true;
+
+template<typename T>
+concept Z16 = true;
+
+template<typename T>
+concept Z17 = true;
+
+template<typename T>
+concept Z18 = true;
+
+template<typename T>
+concept Z19 = true;
+
+namespace T1 {
+template<typename T>
+concept X = ((((((((Z13<T> || (Z2<T> || Z10<T>)) && (Z2<T> && (Z6<T> &&
((Z7<T> && Z13<T>) && Z0<T>)))) && (Z13<T> ||
+(Z12<T> && Z8<T>))) && (Z9<T> || (Z2<T> && Z17<T>))) || Z2<T>) && ((((Z17<T>
|| Z6<T>) && (((Z6<T> || Z4<T>) || Z9<T>)
+&& Z13<T>)) || ((Z14<T> || Z10<T>) || Z3<T>)) || (Z8<T> || ((Z19<T> && (Z3<T>
&& Z14<T>)) && ((Z5<T> || (Z3<T> &&
+Z5<T>)) || (Z7<T> && Z13<T>)))))) || ((((Z14<T> && (Z2<T> && Z1<T>)) ||
((Z17<T> && Z12<T>) && (Z0<T> || ((((Z9<T> ||
+(Z6<T> && Z16<T>)) && Z19<T>) && (Z6<T> && (Z12<T> && Z17<T>))) && (Z19<T> &&
Z8<T>))))) || (((Z10<T> || Z17<T>) &&
+Z1<T>) && ((Z16<T> && (Z15<T> || Z5<T>)) || ((Z4<T> && Z5<T>) || ((Z1<T> ||
Z4<T>) || Z2<T>))))) && (((Z12<T> && (Z5<T>
+&& Z10<T>)) || ((Z4<T> && Z18<T>) && Z0<T>)) || ((((Z10<T> || Z0<T>) &&
Z18<T>) || (Z15<T> && ((Z11<T> && Z5<T>) &&
+Z6<T>))) && Z2<T>)))) && ((((((((((Z8<T> && Z13<T>) && Z7<T>) && Z18<T>) &&
((((Z7<T> && Z11<T>) || (Z19<T> && Z6<T>))
+|| Z13<T>) && Z15<T>)) || (Z1<T> || Z15<T>)) || (Z9<T> && (Z6<T> || Z10<T>)))
|| Z0<T>) && (((Z14<T> || Z4<T>) &&
+(Z4<T> || ((Z4<T> && Z10<T>) && Z11<T>))) || Z4<T>)) && ((((((Z8<T> && ((Z1<T>
&& (Z16<T> && (Z0<T> && Z6<T>))) &&
+(Z1<T> && Z10<T>))) && ((Z18<T> && Z3<T>) || ((Z14<T> && Z1<T>) || Z15<T>)))
&& (((Z19<T> || Z17<T>) || ((Z17<T> &&
+(Z9<T> && Z19<T>)) || Z6<T>)) || (((Z4<T> || (((Z4<T> || Z9<T>) && Z6<T>) &&
Z2<T>)) || ((Z17<T> && (Z16<T> && ((Z14<T>
+&& Z10<T>) && Z17<T>))) || Z9<T>)) && (Z5<T> && Z6<T>)))) && (((Z3<T> &&
Z14<T>) || Z5<T>) && Z8<T>)) && ((((Z10<T> ||
+(Z17<T> && Z8<T>)) || ((Z16<T> && (((Z12<T> && Z16<T>) || Z18<T>) || (Z4<T> &&
Z13<T>))) || (Z17<T> && Z10<T>))) ||
+((((Z9<T> && ((Z7<T> || Z2<T>) && Z15<T>)) || ((Z18<T> && Z13<T>) || (Z4<T> ||
Z14<T>))) || (((Z7<T> || (Z10<T> &&
+(Z14<T> && Z18<T>))) && (Z9<T> || Z5<T>)) || (Z8<T> && ((Z14<T> || Z11<T>) ||
((Z4<T> || Z2<T>) && (Z7<T> &&
+Z5<T>)))))) && (((Z14<T> && (Z13<T> && Z10<T>)) || Z8<T>) && (((((Z7<T> ||
(Z8<T> && Z14<T>)) || Z0<T>) && Z0<T>) ||
+Z17<T>) || Z5<T>)))) && (Z16<T> && Z4<T>))) && (((Z1<T> && Z12<T>) || ((Z17<T>
|| Z4<T>) || (Z15<T> || (Z6<T> ||
+Z8<T>)))) || (((Z2<T> || Z19<T>) && Z5<T>) && Z1<T>)))) || ((((Z9<T> ||
(Z12<T> || Z6<T>)) && (Z5<T> || Z12<T>)) &&
+((Z1<T> || Z8<T>) || (Z18<T> && Z19<T>))) || ((Z11<T> && Z17<T>) || (Z5<T> &&
Z12<T>)))));
template<typename T>
concept Y = Z0<T> && X<T>;
@@ -194,3 +257,37 @@ constexpr int foo(X auto x) { return 1; }
constexpr int foo(Y auto y) { return 2; }
static_assert(foo(0) == 2);
}
+
+namespace T3 {
+
+template<typename T>
+concept X = (((Z2<T> && ((Z7<T> || (Z8<T> && (Z6<T> && Z4<T>))) && ((Z1<T> &&
Z3<T>) || ((Z1<T> && (Z7<T> && Z2<T>)) &&
+Z1<T>)))) && ((Z7<T> || (((Z6<T> || Z0<T>) || (Z5<T> || Z3<T>)) && Z3<T>)) &&
((Z6<T> || ((((Z6<T> && Z8<T>) && (Z8<T>
+&& Z3<T>)) || (Z6<T> && Z5<T>)) && (Z6<T> || (Z3<T> && (Z3<T> || Z8<T>))))) &&
((((Z3<T> || (Z3<T> && (Z6<T> ||
+Z8<T>))) && Z3<T>) && Z9<T>) || ((Z7<T> || Z6<T>) || ((Z3<T> && (Z4<T> &&
(Z0<T> && Z3<T>))) && (((Z5<T> && (Z1<T> ||
+Z5<T>)) || Z3<T>) && (((Z7<T> || Z5<T>) || ((Z9<T> || Z1<T>) && ((Z9<T> &&
Z0<T>) || Z0<T>))) && (Z5<T> &&
+Z7<T>))))))))) || (((((Z5<T> || Z0<T>) || (Z7<T> && (Z8<T> && (Z9<T> || (Z6<T>
&& Z1<T>))))) || (((Z6<T> || Z3<T>) ||
+Z1<T>) && Z3<T>)) || (((Z9<T> && ((((Z9<T> || (Z9<T> && (((Z7<T> || ((Z4<T> ||
Z3<T>) || Z8<T>)) && Z3<T>) && (Z1<T> &&
+Z3<T>)))) || ((Z1<T> && ((Z8<T> && (Z9<T> && Z6<T>)) && (Z1<T> || Z5<T>))) ||
Z0<T>)) && Z2<T>) && ((Z1<T> || (Z0<T> ||
+Z7<T>)) || (Z9<T> && Z4<T>)))) || (Z4<T> || Z3<T>)) && ((Z3<T> && Z9<T>) ||
((Z6<T> || Z8<T>) && (Z7<T> && (Z9<T> ||
+(Z3<T> || Z7<T>))))))) && (Z2<T> && (Z7<T> || Z3<T>))));
+
+template<typename T>
+concept Y = X<T> && ((Z2<T> && (((Z6<T> || Z5<T>) || Z1<T>) && (Z4<T> ||
((Z9<T> || (Z2<T> || Z5<T>)) || Z7<T>)))) ||
+((((((Z9<T> || (Z1<T> || Z3<T>)) && Z5<T>) || ((Z5<T> || Z0<T>) || (Z2<T> &&
Z1<T>))) || Z3<T>) || (((Z0<T> && ((Z4<T>
+&& (((Z3<T> && Z0<T>) || (Z1<T> || Z5<T>)) || Z6<T>)) || ((Z7<T> || (Z1<T> ||
Z8<T>)) || Z8<T>))) && ((Z6<T> || (Z6<T>
+|| Z9<T>)) && (Z1<T> || Z0<T>))) || (Z5<T> || (((Z8<T> || Z5<T>) &&
(((((((Z3<T> || Z2<T>) || Z6<T>) || ((Z6<T> ||
+Z4<T>) || ((Z1<T> && Z9<T>) || Z8<T>))) || (Z3<T> && (Z9<T> && (Z6<T> ||
(Z1<T> || Z0<T>))))) && (((Z3<T> && Z5<T>) ||
+(Z4<T> || Z2<T>)) && (Z5<T> && (Z6<T> || (Z0<T> || Z1<T>))))) || Z1<T>) ||
(Z4<T> || (Z1<T> || Z4<T>)))) && Z9<T>))))
+&& ((((Z6<T> || (((Z6<T> && (Z3<T> || Z9<T>)) && Z6<T>) && (Z1<T> && Z9<T>)))
&& ((Z4<T> && (Z4<T> && Z3<T>)) &&
+Z4<T>)) && (((((Z1<T> && Z3<T>) && (Z5<T> && Z2<T>)) || (Z1<T> || (Z9<T> ||
Z1<T>))) && (Z8<T> || Z1<T>)) || ((Z4<T> ||
+Z5<T>) && Z3<T>))) && ((((((Z8<T> || Z4<T>) || (Z6<T> && Z3<T>)) || (Z4<T> ||
Z0<T>)) || Z4<T>) && (Z7<T> || Z5<T>)) &&
+((Z8<T> || (Z2<T> && Z1<T>)) && (Z8<T> || Z1<T>))))));
+
+constexpr int foo(X auto x) { return 1; }
+constexpr int foo(Y auto y) { return 2; }
+static_assert(foo(0) == 2);
+
+}
+
+}
>From 09e9453af87d56219bdd5c1b5a647321cbe75589 Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Tue, 25 Mar 2025 13:11:04 +0100
Subject: [PATCH 06/12] format
---
clang/include/clang/Sema/SemaConcept.h | 5 ++---
clang/lib/Sema/SemaConcept.cpp | 14 ++++++++++----
2 files changed, 12 insertions(+), 7 deletions(-)
diff --git a/clang/include/clang/Sema/SemaConcept.h
b/clang/include/clang/Sema/SemaConcept.h
index 696fc4b97a1be..9e61773ea599a 100644
--- a/clang/include/clang/Sema/SemaConcept.h
+++ b/clang/include/clang/Sema/SemaConcept.h
@@ -230,9 +230,8 @@ class SubsumptionChecker {
DNFFormula DNF(const NormalizedConstraint &C);
template <typename FormulaType>
- FormulaType
- Normalize(const NormalizedConstraint &C,
- bool ParentWillDoCrossProduct);
+ FormulaType Normalize(const NormalizedConstraint &C,
+ bool ParentWillDoCrossProduct);
void AddNonRedundantClauseToFormula(Formula &F, Clause C);
void AddUniqueClauseToFormula(Formula &F, Clause C);
bool IsSuperSet(const Clause &A, const Clause &B);
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index 54974156809e7..6acb950d03dba 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -2031,10 +2031,12 @@ auto SubsumptionChecker::find(FoldExpandedConstraint
*Ori) -> Literal {
}
auto SubsumptionChecker::CNF(const NormalizedConstraint &C) -> CNFFormula {
- return SubsumptionChecker::Normalize<CNFFormula>(C,
/*ParentWillDoCrossProduct=*/false);
+ return SubsumptionChecker::Normalize<CNFFormula>(
+ C, /*ParentWillDoCrossProduct=*/false);
}
auto SubsumptionChecker::DNF(const NormalizedConstraint &C) -> DNFFormula {
- return SubsumptionChecker::Normalize<DNFFormula>(C,
/*ParentWillDoCrossProduct=*/false);
+ return SubsumptionChecker::Normalize<DNFFormula>(
+ C, /*ParentWillDoCrossProduct=*/false);
}
///
@@ -2080,8 +2082,12 @@ FormulaType SubsumptionChecker::Normalize(const
NormalizedConstraint &NC,
FormulaType Left, Right;
SemaRef.runWithSufficientStackSpace(SourceLocation(), [&] {
- Left = Normalize<FormulaType>(NC.getLHS(), ParentWillDoCrossProduct ||
NC.getCompoundKind() != FormulaType::Kind);
- Right = Normalize<FormulaType>(NC.getRHS(), ParentWillDoCrossProduct ||
NC.getCompoundKind() != FormulaType::Kind);
+ Left = Normalize<FormulaType>(NC.getLHS(), ParentWillDoCrossProduct ||
+ NC.getCompoundKind() !=
+ FormulaType::Kind);
+ Right = Normalize<FormulaType>(NC.getRHS(), ParentWillDoCrossProduct ||
+ NC.getCompoundKind() !=
+ FormulaType::Kind);
});
if (NC.getCompoundKind() == FormulaType::Kind) {
>From 03628427aa317ea2728f4eeae4dd987a5ee5e677 Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Tue, 25 Mar 2025 13:22:56 +0100
Subject: [PATCH 07/12] tests fix
---
clang/test/SemaCXX/concepts-subsumption.cpp | 5 ++---
1 file changed, 2 insertions(+), 3 deletions(-)
diff --git a/clang/test/SemaCXX/concepts-subsumption.cpp
b/clang/test/SemaCXX/concepts-subsumption.cpp
index a5d813f8a9b05..d9d5535e532f4 100644
--- a/clang/test/SemaCXX/concepts-subsumption.cpp
+++ b/clang/test/SemaCXX/concepts-subsumption.cpp
@@ -12,8 +12,7 @@ template <typename T>
requires C<T> && true
void f() {}
-template <>
-void f<int>();
+void test() { f<int>(); };
}
namespace B {
@@ -125,7 +124,7 @@ concept Majority8 =
template <typename T>concept Y = C0<T> || Majority8<T>;
template <typename T>concept Z = Majority8<T> && C1<T>;
-constexpr int foo(X auto x) { return 10; }
+constexpr int foo(Majority8 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);
>From 692c6f58f5e7d05e3c5eeb6a4c03c7dea225416f Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Tue, 25 Mar 2025 13:31:17 +0100
Subject: [PATCH 08/12] Only remove non-unique (rather than redundant) clauses.
Removing redundant clauses while producing a cross products was
unsound.
---
clang/include/clang/Sema/SemaConcept.h | 6 +-
clang/lib/Sema/SemaConcept.cpp | 81 ++++----------------------
2 files changed, 12 insertions(+), 75 deletions(-)
diff --git a/clang/include/clang/Sema/SemaConcept.h
b/clang/include/clang/Sema/SemaConcept.h
index 9e61773ea599a..b4b879c515047 100644
--- a/clang/include/clang/Sema/SemaConcept.h
+++ b/clang/include/clang/Sema/SemaConcept.h
@@ -230,11 +230,9 @@ class SubsumptionChecker {
DNFFormula DNF(const NormalizedConstraint &C);
template <typename FormulaType>
- FormulaType Normalize(const NormalizedConstraint &C,
- bool ParentWillDoCrossProduct);
- void AddNonRedundantClauseToFormula(Formula &F, Clause C);
+ FormulaType
+ Normalize(const NormalizedConstraint &C);
void AddUniqueClauseToFormula(Formula &F, Clause C);
- bool IsSuperSet(const Clause &A, const Clause &B);
Literal find(AtomicConstraint *);
Literal find(FoldExpandedConstraint *);
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index 6acb950d03dba..f231ed9cd0f6a 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -2031,12 +2031,10 @@ auto SubsumptionChecker::find(FoldExpandedConstraint
*Ori) -> Literal {
}
auto SubsumptionChecker::CNF(const NormalizedConstraint &C) -> CNFFormula {
- return SubsumptionChecker::Normalize<CNFFormula>(
- C, /*ParentWillDoCrossProduct=*/false);
+ return SubsumptionChecker::Normalize<CNFFormula>(C);
}
auto SubsumptionChecker::DNF(const NormalizedConstraint &C) -> DNFFormula {
- return SubsumptionChecker::Normalize<DNFFormula>(
- C, /*ParentWillDoCrossProduct=*/false);
+ return SubsumptionChecker::Normalize<DNFFormula>(C);
}
///
@@ -2052,26 +2050,15 @@ auto SubsumptionChecker::DNF(const NormalizedConstraint
&C) -> DNFFormula {
/// 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,
- bool ParentWillDoCrossProduct) {
+FormulaType SubsumptionChecker::Normalize(const NormalizedConstraint &NC) {
FormulaType Res;
- auto Add = [&, this](Clause C, bool RemoveRedundantClause) {
- // Sort each clause and remove duplicates for faster comparision
- // Both AddClauseToFormula and IsSuperSet require sorted, uniqued literals.
+ auto Add = [&, this](Clause C) {
+ // Sort each clause and remove duplicates for faster comparisons
std::sort(C.begin(), C.end());
C.erase(std::unique(C.begin(), C.end()), C.end());
-
- // 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
- AddUniqueClauseToFormula(Res, std::move(C));
+ AddUniqueClauseToFormula(Res, std::move(C));
};
if (NC.isAtomic())
@@ -2082,23 +2069,15 @@ FormulaType SubsumptionChecker::Normalize(const
NormalizedConstraint &NC,
FormulaType Left, Right;
SemaRef.runWithSufficientStackSpace(SourceLocation(), [&] {
- Left = Normalize<FormulaType>(NC.getLHS(), ParentWillDoCrossProduct ||
- NC.getCompoundKind() !=
- FormulaType::Kind);
- Right = Normalize<FormulaType>(NC.getRHS(), ParentWillDoCrossProduct ||
- NC.getCompoundKind() !=
- FormulaType::Kind);
+ 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);
- });
+ std::make_move_iterator(Right.end()), Add);
return Res;
}
@@ -2111,32 +2090,12 @@ FormulaType SubsumptionChecker::Normalize(const
NormalizedConstraint &NC,
std::back_inserter(Combined));
std::copy(RTransform.begin(), RTransform.end(),
std::back_inserter(Combined));
- Add(std::move(Combined),
- FormulaType::Kind == NormalizedConstraint::CCK_Conjunction);
+ Add(std::move(Combined));
}
}
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::AddNonRedundantClauseToFormula(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);
-}
-
void SubsumptionChecker::AddUniqueClauseToFormula(Formula &F, Clause C) {
for (auto &Other : F) {
if (llvm::equal(C, Other))
@@ -2145,26 +2104,6 @@ void
SubsumptionChecker::AddUniqueClauseToFormula(Formula &F, Clause C) {
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();
- while (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,
>From e63d32de636bcc8a3438d786343b09ba54ed0e4d Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Tue, 25 Mar 2025 13:50:59 +0100
Subject: [PATCH 09/12] format
---
clang/include/clang/Sema/SemaConcept.h | 3 +--
clang/lib/Sema/SemaConcept.cpp | 2 +-
2 files changed, 2 insertions(+), 3 deletions(-)
diff --git a/clang/include/clang/Sema/SemaConcept.h
b/clang/include/clang/Sema/SemaConcept.h
index b4b879c515047..f523e518733ce 100644
--- a/clang/include/clang/Sema/SemaConcept.h
+++ b/clang/include/clang/Sema/SemaConcept.h
@@ -230,8 +230,7 @@ class SubsumptionChecker {
DNFFormula DNF(const NormalizedConstraint &C);
template <typename FormulaType>
- FormulaType
- Normalize(const NormalizedConstraint &C);
+ FormulaType Normalize(const NormalizedConstraint &C);
void AddUniqueClauseToFormula(Formula &F, Clause C);
Literal find(AtomicConstraint *);
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index f231ed9cd0f6a..0b6d122ad5411 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -2069,7 +2069,7 @@ FormulaType SubsumptionChecker::Normalize(const
NormalizedConstraint &NC) {
FormulaType Left, Right;
SemaRef.runWithSufficientStackSpace(SourceLocation(), [&] {
- Left = Normalize<FormulaType>(NC.getLHS());
+ Left = Normalize<FormulaType>(NC.getLHS());
Right = Normalize<FormulaType>(NC.getRHS());
});
>From 3a412aba5bd62a5324850d8366027dda036e7001 Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Wed, 26 Mar 2025 11:43:19 +0100
Subject: [PATCH 10/12] Apply review feedback
---
clang/lib/Sema/SemaConcept.cpp | 14 ++++++--------
1 file changed, 6 insertions(+), 8 deletions(-)
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index 0b6d122ad5411..bfd08fe07d160 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -1995,9 +1995,9 @@ auto SubsumptionChecker::find(AtomicConstraint *Ori) ->
Literal {
const auto &Mapping = Ori->ParameterMapping;
ID.AddBoolean(Mapping.has_value());
if (Mapping) {
- for (unsigned I = 0, S = Mapping->size(); I < S; ++I) {
+ for (const TemplateArgumentLoc & TAL : *Mapping) {
SemaRef.getASTContext()
- .getCanonicalTemplateArgument((*Mapping)[I].getArgument())
+ .getCanonicalTemplateArgument(TAL.getArgument())
.Profile(ID, SemaRef.getASTContext());
}
}
@@ -2056,8 +2056,8 @@ FormulaType SubsumptionChecker::Normalize(const
NormalizedConstraint &NC) {
auto Add = [&, this](Clause C) {
// Sort each clause and remove duplicates for faster comparisons
- std::sort(C.begin(), C.end());
- C.erase(std::unique(C.begin(), C.end()), C.end());
+ llvm::sort(C);
+ C.erase(llvm::unique(C), C.end());
AddUniqueClauseToFormula(Res, std::move(C));
};
@@ -2086,10 +2086,8 @@ FormulaType SubsumptionChecker::Normalize(const
NormalizedConstraint &NC) {
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));
+ llvm::copy(LTransform, std::back_inserter(Combined));
+ llvm::copy(RTransform, std::back_inserter(Combined));
Add(std::move(Combined));
}
}
>From 552b3d35df39a7266e0600c7197d481e78cab173 Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Thu, 27 Mar 2025 16:31:31 +0100
Subject: [PATCH 11/12] remove unused function
---
clang/include/clang/Sema/SemaConcept.h | 2 --
1 file changed, 2 deletions(-)
diff --git a/clang/include/clang/Sema/SemaConcept.h
b/clang/include/clang/Sema/SemaConcept.h
index f523e518733ce..fda22b779c636 100644
--- a/clang/include/clang/Sema/SemaConcept.h
+++ b/clang/include/clang/Sema/SemaConcept.h
@@ -134,8 +134,6 @@ struct alignas(ConstraintAlignment) FoldExpandedConstraint {
static bool AreCompatibleForSubsumption(const FoldExpandedConstraint &A,
const FoldExpandedConstraint &B);
-
- llvm::FoldingSetNodeID ProfileForSubsumption() const;
};
const NormalizedConstraint *getNormalizedAssociatedConstraints(
>From a3d3cd488e018a4dcf190978b12787b4acb7b787 Mon Sep 17 00:00:00 2001
From: Corentin Jabot <corentinja...@gmail.com>
Date: Thu, 27 Mar 2025 16:45:39 +0100
Subject: [PATCH 12/12] format
---
clang/lib/Sema/SemaConcept.cpp | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp
index bfd08fe07d160..e7e0b4cfb72a7 100644
--- a/clang/lib/Sema/SemaConcept.cpp
+++ b/clang/lib/Sema/SemaConcept.cpp
@@ -1995,7 +1995,7 @@ auto SubsumptionChecker::find(AtomicConstraint *Ori) ->
Literal {
const auto &Mapping = Ori->ParameterMapping;
ID.AddBoolean(Mapping.has_value());
if (Mapping) {
- for (const TemplateArgumentLoc & TAL : *Mapping) {
+ for (const TemplateArgumentLoc &TAL : *Mapping) {
SemaRef.getASTContext()
.getCanonicalTemplateArgument(TAL.getArgument())
.Profile(ID, SemaRef.getASTContext());
_______________________________________________
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits
