constraint_crdt/
merge.rs

1//! # CRDT Merge Trait
2//!
3//! The fundamental algebraic structure underlying both CRDTs and constraint lattices:
4//! a **semilattice**. Every CRDT merge must be:
5//! - **Commutative**: a.merge(b) == b.merge(a)
6//! - **Associative**: a.merge(b).merge(c) == a.merge(b.merge(c))
7//! - **Idempotent**: a.merge(a) == a
8//!
9//! These are EXACTLY the properties needed for distributed constraint satisfaction.
10
11use std::fmt::Debug;
12
13/// The fundamental merge operation — a bounded semilattice join.
14///
15/// This trait unifies CRDT merges, constraint lattice joins,
16/// and PLATO tile reconciliation under one algebraic structure.
17pub trait Merge: Clone + Debug {
18    /// Merge another state into this one (in-place).
19    ///
20    /// Postconditions:
21    /// - `a.merge(b)` ≡ `b.merge(a)` (commutative)
22    /// - `a.merge(b).merge(c)` ≡ `a.merge(b.merge(c))` (associative)
23    /// - `a.merge(a)` ≡ `a` (idempotent)
24    fn merge(&mut self, other: &Self);
25
26    /// Create a merged copy without modifying self.
27    fn merged(&self, other: &Self) -> Self
28    where
29        Self: Sized,
30    {
31        let mut copy = self.clone();
32        copy.merge(other);
33        copy
34    }
35
36    /// Check if this state subsumes (is greater than or equal to) another.
37    /// In lattice terms: self ≥ other.
38    fn subsumes(&self, other: &Self) -> bool
39    where
40        Self: PartialEq,
41    {
42        self.merged(other) == *self
43    }
44}
45
46#[cfg(test)]
47pub mod laws {
48    use super::*;
49
50    /// Verify commutativity: a ∘ b == b ∘ a
51    pub fn check_commutative<T: Merge + PartialEq>(a: &T, b: &T) -> bool {
52        a.merged(b) == b.merged(a)
53    }
54
55    /// Verify associativity: (a ∘ b) ∘ c == a ∘ (b ∘ c)
56    pub fn check_associative<T: Merge + PartialEq>(a: &T, b: &T, c: &T) -> bool {
57        a.merged(b).merged(c) == a.merged(&b.merged(c))
58    }
59
60    /// Verify idempotence: a ∘ a == a
61    pub fn check_idempotent<T: Merge + PartialEq>(a: &T) -> bool {
62        a.merged(a) == *a
63    }
64}
constraint_crdt/merge.rs

constraint_crdt/
merge.rs
