You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
[epic] Canonical form + hash-consing: make expression identity structural, not conventional
Problem
Expression identity is currently decided ad hoc at every call site: deep operator== here, raw hash_value() there, pointer comparison elsewhere. The July 2026 review showed this is the library's worst bug class — #339, #340, #341, #342, #343, #347, #371 are all instances of "two places disagree about when expressions are the same". Fixing those issues repairs the sites we found; it does not prevent the next one, because the architecture allows every new dispatcher to re-decide identity.
There is also no defined canonical form and no user-callable simplify(): normalization happens implicitly at construction, differently per operator, so the same mathematical expression can exist in several structural shapes (#184 was an instance; the ((x+y)+x)+x → {x, y, 2*x} state behind #347 is another).
Goal
One authoritative answer to "are these expressions identical?", O(1), impossible to bypass.
Proposal: hash-consed unique table
A per-process (later: per-context) intern table maps structural key → shared_ptr<node>. All node construction goes through make_expression<T>(...), which canonicalizes children order (existing operator<), then interns.
The coefficient-blind hash design stays as the bucket key for like-term merging; it no longer doubles as identity anywhere.
Prerequisite: nodes must be immutable after construction (see the thread-safety epic — annotations are the hard part; either fold annotations into the intern key or move them to a side table keyed by node).
Algebra-equivalence fuzzer (eval-before vs eval-after simplification at random points) as the standing guard — extends the existing FuzzyDiff harness, runs in CI.
Design note: intern-key definition (node id + children identities + payload: coefficients, index sequences, names, constants), annotation policy, lifetime policy (weak_ptr table vs generation GC).
Implement intern table behind make_expression; convert operator==/< to pointer identity + stable total order.
Sweep: delete per-node operator== overrides and hash-equality shortcuts made redundant.
Define + document the canonical form (child ordering, coefficient placement, pow/mul normalization) and expose explicit simplify(expr) as the re-canonicalization entry point.
Phase 0 — tactical ground truth. Land #339–#343, #347, #371 with their lock-in tables. These tests define the identity contract the intern table must reproduce.
Phase 1 — immutability prerequisite. Hashes computed eagerly in node constructors (children are already constructed); annotations frozen at construction or moved to a side table (shared work with the thread-safety epic).
Phase 2 — intern table. In make_expression<T>(args...): build the node, derive the intern key = (domain tag, node type id, ordered child node pointers, payload: coefficient scalar_number, index sequences, symbol name, constant value bits). Look up in a std::unordered_map<key, std::weak_ptr<node>> guarded by a mutex (sharded if contended); return the existing node or insert. Expired entries cleaned lazily on collision/insert.
Phase 3 — identity switch.expression::operator== → pointer equality; operator< → stable total order on (hash, pointer) for map determinism, keeping the existing hash-based print order. Delete per-node operator== overrides.
Phase 4 — sweep + guard. Remove now-redundant hash-equality shortcuts; add a clang-tidy/grep CI check that hash_value() == appears only inside the intern implementation.
Interning: EXPECT_EQ((x+y).data(), (y+x).data()) — same canonical node pointer; EXPECT_NE((x+2.0).data(), (x+5.0).data()).
Algebra-equivalence fuzzer: random expression trees per domain, evaluate the unsimplified operand recipe vs the constructed/simplified expression at ≥3 random points, EXPECT_NEAR within tolerance; run N=5000 seeds in CI (reuses FuzzyDiff generators).
Lifetime: build expressions in a scope, drop them, assert the intern table empties (weak_ptr expiry) — no leak of interned nodes.
Determinism: to_string of a fixed expression identical across two process runs (guards accidental pointer-order dependence).
[epic] Canonical form + hash-consing: make expression identity structural, not conventional
Problem
Expression identity is currently decided ad hoc at every call site: deep
operator==here, rawhash_value()there, pointer comparison elsewhere. The July 2026 review showed this is the library's worst bug class — #339, #340, #341, #342, #343, #347, #371 are all instances of "two places disagree about when expressions are the same". Fixing those issues repairs the sites we found; it does not prevent the next one, because the architecture allows every new dispatcher to re-decide identity.There is also no defined canonical form and no user-callable
simplify(): normalization happens implicitly at construction, differently per operator, so the same mathematical expression can exist in several structural shapes (#184 was an instance; the((x+y)+x)+x → {x, y, 2*x}state behind #347 is another).Goal
One authoritative answer to "are these expressions identical?", O(1), impossible to bypass.
Proposal: hash-consed unique table
shared_ptr<node>. All node construction goes throughmake_expression<T>(...), which canonicalizes children order (existingoperator<), then interns.expression::operator==becomesthis == &other; the entire hash-as-identity class (Raw hash_value() equality used as identity in simplifiers — X+pow(X,2)→2*pow(X,2), X+2*X→4*X, X*(2*X) drops the 2, sin(a)−sin(b)→0 #340) becomes unrepresentable.Scope / tasks
make_expression; convertoperator==/<to pointer identity + stable total order.operator==overrides and hash-equality shortcuts made redundant.simplify(expr)as the re-canonicalization entry point.Acceptance criteria
a == b⇔ same pointer; all existing tests green; n_ary_tree operator== ignores the coefficient — x+2 == x+5 and 2*x == 3*x compare equal, corrupting simplify/compare/substitute #339/Raw hash_value() equality used as identity in simplifiers — X+pow(X,2)→2*pow(X,2), X+2*X→4*X, X*(2*X) drops the 2, sin(a)−sin(b)→0 #340 lock-in tables pass unchanged.hash_value() ==left outside the intern table implementation (grep-clean, enforced by clang-tidy check or review checklist).Related
#339, #340, #341, #342, #343, #347, #371, #184 (closed), #95, #104, #262.
How to fix (implementation sketch)
Phase 0 — tactical ground truth. Land #339–#343, #347, #371 with their lock-in tables. These tests define the identity contract the intern table must reproduce.
Phase 1 — immutability prerequisite. Hashes computed eagerly in node constructors (children are already constructed); annotations frozen at construction or moved to a side table (shared work with the thread-safety epic).
Phase 2 — intern table. In
make_expression<T>(args...): build the node, derive the intern key = (domain tag, node type id, ordered child node pointers, payload: coefficientscalar_number, indexsequences, symbol name, constant value bits). Look up in astd::unordered_map<key, std::weak_ptr<node>>guarded by a mutex (sharded if contended); return the existing node or insert. Expired entries cleaned lazily on collision/insert.Phase 3 — identity switch.
expression::operator==→ pointer equality;operator<→ stable total order on (hash, pointer) for map determinism, keeping the existing hash-based print order. Delete per-nodeoperator==overrides.Phase 4 — sweep + guard. Remove now-redundant hash-equality shortcuts; add a clang-tidy/grep CI check that
hash_value() ==appears only inside the intern implementation.Tests
EXPECT_EQ((x+y).data(), (y+x).data())— same canonical node pointer;EXPECT_NE((x+2.0).data(), (x+5.0).data()).EXPECT_NEARwithin tolerance; run N=5000 seeds in CI (reuses FuzzyDiff generators).to_stringof a fixed expression identical across two process runs (guards accidental pointer-order dependence).