Node-sharing shortcuts silently corrupt algebraic results for non-idempotent `Lattice` values

[adamv-symbolica]

Summary

join/meet/subtract — at the map level, the write-zipper level, and the experimental zipper_alg level — all contain shortcuts that skip the value-level pjoin/pmeet/psubtract whenever the two operands are (or contain) the same physical node. The shortcut assumes the value operations are idempotent (x ∨ x = x, x ∖ x = ∅). That holds for every built-in impl and for genuine lattices, but nothing in the Lattice/DistributiveLattice docs states it as a contract (ring.rs:531 says only "Implements basic algebraic behavior (union & intersection) for a type"), and the traits are the natural hook for counting/multiset semantics (join = sum of counts, subtract = decrement) — for which the shortcuts produce silently wrong results that depend on physical sharing rather than logical content.

The failure is representation-dependent: the same call is correct when the operand was built fresh and wrong when it shares nodes with the receiver (via clone, CoW edits, grafting, or Identity-reusing results of earlier algebra). With partial sharing, a single join returns correct values on unshared branches and wrong values on shared branches of the same result map.

Verified on pathmap 0.3.0 at 7570be8426fa5c525e69515b088687cf15672345, rustc 1.95.0-nightly, macOS arm64.

Reproduction

Count models multiset semantics: join = sum; subtract = saturating decrement where zero is a meaningful value that must persist (an existence count).

[dependencies]
pathmap = { path = "../PathMap", features = ["zipper_alg"] }

use pathmap::ring::{AlgebraicResult, DistributiveLattice, Lattice};
use pathmap::PathMap;

#[derive(Clone, Debug, PartialEq)]
struct Count(u64);

impl Lattice for Count {
    fn pjoin(&self, other: &Self) -> AlgebraicResult<Self> {
        AlgebraicResult::Element(Count(self.0 + other.0))
    }
    fn pmeet(&self, other: &Self) -> AlgebraicResult<Self> {
        AlgebraicResult::Element(Count(self.0.min(other.0)))
    }
}
impl DistributiveLattice for Count {
    fn psubtract(&self, other: &Self) -> AlgebraicResult<Self> {
        AlgebraicResult::Element(Count(self.0.saturating_sub(other.0)))
    }
}

fn main() {
    // Case A: whole-map sharing via clone
    let mut a = PathMap::<Count>::new();
    a.insert(b"k", Count(1));
    let b = a.clone();
    assert_eq!(a.join(&b).get(b"k"), Some(&Count(2)));   // FAILS: Some(Count(1))

    let mut b2 = PathMap::<Count>::new();                // same logical content,
    b2.insert(b"k", Count(1));                           // no physical sharing
    assert_eq!(a.join(&b2).get(b"k"), Some(&Count(2)));  // passes

    // Case B: partial sharing via clone + CoW edit — one join call,
    // correct on the modified branch, wrong on the shared branch
    let mut a = PathMap::<Count>::new();
    for i in 0..100u32 {
        a.insert(format!("shared/{i:03}").as_bytes(), Count(1));
    }
    a.insert(b"hot", Count(1));
    let mut b = a.clone();
    b.insert(b"hot", Count(5));                          // CoW copies only the "hot" spine
    let j = a.join(&b);
    assert_eq!(j.get(b"hot"), Some(&Count(6)));          // passes
    assert_eq!(j.get(b"shared/050"), Some(&Count(2)));   // FAILS: Some(Count(1))

    // Case C: subtract with keep-zero semantics
    let mut a = PathMap::<Count>::new();
    a.insert(b"k", Count(3));
    let b = a.clone();
    assert_eq!(a.subtract(&b).get(b"k"), Some(&Count(0))); // FAILS: None (entry vanishes)
}

Observed output of the full test matrix (labels: map = PathMap::join/subtract, zipper_* = the zipper_alg free functions writing into a fresh output zipper):

[ BUG ] map join, rhs = lhs.clone()                             expected Some(2)      got Some(1)
[  ok ] map join, rhs = fresh map, same logical content         expected Some(2)      got Some(2)
[  ok ] partial sharing: join at key on modified branch         expected Some(6)      got Some(6)
[ BUG ] partial sharing: join at key on shared branch           expected Some(2)      got Some(1)
[ BUG ] map subtract, rhs = lhs.clone()                         expected Some(0)      got None
[  ok ] map subtract, rhs = fresh map, same logical content     expected Some(0)      got Some(0)
[  ok ] zipper_join (zipper_alg), rhs = lhs.clone()             expected Some(2)      got Some(2)
[  ok ] zipper_join (zipper_alg), rhs = fresh map               expected Some(2)      got Some(2)
[  ok ] zipper_subtract (zipper_alg), rhs = lhs.clone()         expected Some(0)      got Some(0)
[  ok ] zipper_subtract (zipper_alg), rhs = fresh map           expected Some(0)      got Some(0)
[  ok ] zipper_join wide map, rhs = lhs.clone()                 expected Some(2)      got Some(2)
[  ok ] zipper_join partial sharing: key on modified branch     expected Some(6)      got Some(6)
[ BUG ] zipper_join partial sharing: key on shared branch       expected Some(2)      got Some(1)
[ BUG ] zipper_subtract partial sharing: key on shared branch   expected Some(0)      got None

Note the zipper_alg rows: the whole-map-clone cases pass (the shared-node check apparently doesn't engage at the root focus in this construction) while the partial-sharing cases fail — the trigger conditions differ from the map-level ops, which makes the behavior even harder to catch in tests: a test suite exercising clones would conclude zipper_join is safe for counting, and production data with CoW-edited maps would still be corrupted.

Root cause

1. Node-level ops — TrieNodeODRc::{pjoin, pmeet, psubtract} short-circuit on pointer identity without consulting V's ops, src/trie_node.rs:3075-3123:

pub fn pjoin(&self, other: &Self) -> AlgebraicResult<Self> {
    if self.ptr_eq(other) {
        AlgebraicResult::Identity(SELF_IDENT | COUNTER_IDENT)   // asserts x ∨ x = x
    } else { ... }
}
...
pub fn psubtract(&self, other: &Self) -> AlgebraicResult<Self> {
    if self.ptr_eq(other) {
        AlgebraicResult::None                                   // asserts x ∖ x = ∅
    } else { ... }
}

These serve PathMap::join/meet/subtract (src/trie_map.rs:523/528/559) and ZipperWriting::join_into/meet_into/subtract_into (src/write_zipper.rs:139/215/228). Because the node ops recurse per child, the shortcut also fires at any shared subtree inside otherwise-distinct maps — which is what corrupts only the shared branch in Case B. (The //GOAT, question: Is there any point to this pre-check... comment at trie_node.rs:3082 already questions the pre-check; the answer is that it is not merely a perf question — it encodes a semantic assumption.)

2. Experimental zipper algebra — zipper_merge skips whole subtrees when both zippers stand on the same shared node, src/experimental/zipper_algebra.rs:385-397 (entry) and :438-450 (mid-descent):

fn check_sharing<ZL, ZR>(lhs: &ZL, rhs: &ZR) -> bool { 
    lhs.shared_node_id()
        .is_some_and(|lsnid| rhs.shared_node_id().is_some_and(|rsnid| lsnid == rsnid))
}
if check_sharing(lhs, rhs) { P::on_id(lhs, out); return; }

where the policies bake in idempotence: Join::on_id grafts one side verbatim (:1487-1494), Meet::on_id likewise (:1562-1569), and Subtract::on_id emits nothing (:1673-1680).

3. Contract gap — Lattice (src/ring.rs:531-536) and DistributiveLattice document no algebraic laws; the built-in impls are all idempotent-shaped (e.g. impl Lattice for u64 returns Identity(SELF_IDENT) unconditionally, src/ring.rs:837-840), so the assumption is never exercised by the crate's own types or tests.

Why this deserves fixing (or at least loud documentation)

• The result of a public operation depends on physical representation, not logical content. Sharing arises invisibly: clone, CoW edits, graft, and even Identity-reusing results of earlier algebraic ops. Two logically identical programs differ in output depending on how their maps were constructed.
• The corruption is silent and partial — no panic, no wrong-looking structure, just undercounted values on whichever branches happened to be shared.
• Counting/multiset semantics are arguably the most common non-trivial use of a "join values on key collision" hook in a key-value store, and nothing warns against them.

Suggested directions

Any of these would resolve the surprise; (2) preserves both use cases:

1. Document the laws as a hard contract: pjoin must satisfy x.pjoin(x) ≡ Identity(SELF_IDENT|COUNTER_IDENT), pmeet likewise, psubtract must satisfy x.psubtract(x) ≡ None — stating that results are unspecified otherwise. Cheapest, but leaves counting users without a supported path.
2. Gate the shortcuts on an associated const: trait Lattice { const IDEMPOTENT: bool = true; ... } (and the same on DistributiveLattice). Non-idempotent impls set it to false; every shortcut site (trie_node.rs:3078/3106/3117, zipper_algebra.rs check_sharing call sites, and any per-node-type *_dyn shortcuts) checks V::IDEMPOTENT first. Const-folded, so zero cost for all existing impls; shared-subtree traversal cost returns only for types that actually need it.
3. Debug assertions: when a shortcut is taken and the shared focus carries a value v, debug_assert!(v.pjoin(&v).is_identity()) (resp. is_none() for subtract) — catches out-of-contract impls in tests instead of production.

Context

Found while designing an incrementally-maintained statistics index (PathMap<Stats> with sum-on-merge counts) for [hgxz]: an adversarial review flagged that join_into-based delta maintenance would silently undercount whenever operand tries share nodes, which forced the integration down to per-key point updates. The zipper_alg operations were proposed as the workaround, and the reproduction above shows they carry the same assumption with different trigger conditions.

[luketpeterson]

Yes. I remember this conversation with @Adam-Vandervorst now. We didn't have the "idempotent" framing then, but this is pretty much exactly what we went over almost 2 years ago. Idempotency is a good way to talk about the limitation.

I agree with the clanker that not documenting the limitation is not an option.

The deeper fix is down to a judgement call on API aesthetics. My fear is that the IDEMPOTENT flag has the potential to turn a call that completes in a reasonable amount of time into a call that effectively runs forever. But I'm not too bothered about that because it is set by the trait implementor. So it won't be tweaked often and it won't be exposed to people who aren't willing to invest a bit of thought. Bonus that it's a constant folded in at compile-time.

The alternative to the flag is a separate set of entry points. The flag feels nicer to me.

One of the roadmap items is to change the shape of the Lattice trait from being implemented on value types to something that gets implemented on a policy object. Primarily so no sketchy unsafe casting is needed to perform different policy operations on the same map / trie.

I was waiting for the implications of @marcin-rzeznicki 's work to be fully realized before deciding how the main-line would intercept the zipper_algebra. Whether we'd want to promote certain operations from zipper_algbra to fast-paths that operate at the node level, etc. and how to incorporate the current traits, along-side zipper_algebra, into a coherent API with a single best way to do every operation.

[luketpeterson]

@marcin-rzeznicki zipper_algebra also takes the same shortcuts based on sharing. So whatever we come up with needs to be handled by zipper_algebra too.

[marcin-rzeznicki]

Yes, agreed @luketpeterson . What is a bit baffling here, is that [ ok ] zipper_join (zipper_alg), rhs = lhs.clone() comes with the explanation: the shared-node check apparently doesn't engage at the root focus in this construction - on the contrary, it does, it's the first check when we enter the function 🤔