tirea_state/lattice/
mod.rs

1//! Lattice trait and CRDT primitive types for conflict-free parallel state merging.
2//!
3//! A lattice is a partially ordered set where every pair of elements has a least upper bound
4//! (join/merge). The [`Lattice`] trait captures this via the [`merge`](Lattice::merge) method,
5//! which must satisfy commutativity, associativity, and idempotency.
6//!
7//! # Primitive Types
8//!
9//! | Type | Merge semantics |
10//! |------|----------------|
11//! | [`Flag`] | Boolean OR (monotonic enable) |
12//! | [`MaxReg<T>`] | Maximum value |
13//! | [`MinReg<T>`] | Minimum value |
14//! | [`GCounter`] | Grow-only counter (per-node max, sum for value) |
15//! | [`GSet<T>`] | Grow-only set (union) |
16//! | [`ORSet<T>`] | Observed-remove set (add-wins) |
17//! | [`ORMap<K, V>`] | Observed-remove map with recursive value merge (put-wins) |
18
19mod flag;
20mod g_counter;
21mod g_set;
22mod max_reg;
23mod min_reg;
24mod or_map;
25mod or_set;
26mod registry;
27
28pub use flag::Flag;
29pub use g_counter::GCounter;
30pub use g_set::GSet;
31pub use max_reg::MaxReg;
32pub use min_reg::MinReg;
33pub use or_map::ORMap;
34pub use or_set::ORSet;
35pub use registry::{LatticeMerger, LatticeRegistry};
36
37/// A join-semilattice: a set equipped with a commutative, associative, idempotent merge.
38///
39/// Implementors must guarantee the following laws for all values `a`, `b`, `c`:
40///
41/// - **Commutativity**: `a.merge(&b) == b.merge(&a)`
42/// - **Associativity**: `a.merge(&b).merge(&c) == a.merge(&b.merge(&c))`
43/// - **Idempotency**: `a.merge(&a) == a`
44pub trait Lattice: Clone + PartialEq {
45    /// Compute the least upper bound of `self` and `other`.
46    fn merge(&self, other: &Self) -> Self;
47}
48
49/// Assert the three lattice laws (commutativity, associativity, idempotency) for a triple of values.
50///
51/// Intended for use in `#[cfg(test)]` modules.
52///
53/// # Panics
54///
55/// Panics with a descriptive message if any law is violated.
56#[cfg(test)]
57pub(crate) fn assert_lattice_laws<T: Lattice + std::fmt::Debug>(a: &T, b: &T, c: &T) {
58    // Commutativity: a ∨ b == b ∨ a
59    assert_eq!(
60        a.merge(b),
61        b.merge(a),
62        "commutativity violated: a.merge(b) != b.merge(a)\n  a = {a:?}\n  b = {b:?}"
63    );
64
65    // Associativity: (a ∨ b) ∨ c == a ∨ (b ∨ c)
66    assert_eq!(
67        a.merge(b).merge(c),
68        a.merge(&b.merge(c)),
69        "associativity violated: (a∨b)∨c != a∨(b∨c)\n  a = {a:?}\n  b = {b:?}\n  c = {c:?}"
70    );
71
72    // Idempotency: a ∨ a == a
73    assert_eq!(
74        a.merge(a),
75        a.clone(),
76        "idempotency violated for a: a.merge(a) != a\n  a = {a:?}"
77    );
78    assert_eq!(
79        b.merge(b),
80        b.clone(),
81        "idempotency violated for b: b.merge(b) != b\n  b = {b:?}"
82    );
83    assert_eq!(
84        c.merge(c),
85        c.clone(),
86        "idempotency violated for c: c.merge(c) != c\n  c = {c:?}"
87    );
88}
tirea_state/lattice/mod.rs

tirea_state/lattice/
mod.rs
