calimero_primitives/
crdt.rs

1//! CRDT (Conflict-free Replicated Data Type) primitives.
2//!
3//! This module provides the unified `CrdtType` enum used across the codebase
4//! for identifying CRDT semantics during storage and synchronization.
5
6#[cfg(feature = "borsh")]
7use borsh::{BorshDeserialize, BorshSerialize};
8use serde::{Deserialize, Serialize};
9
10/// CRDT type indicator for merge semantics.
11///
12/// Identifies the conflict resolution strategy used when merging replicated data.
13/// This enum is used both by the storage layer (for persistence metadata) and
14/// the sync protocol (for wire-format entity classification).
15///
16/// # Merge Semantics
17///
18/// Each variant defines specific merge behavior:
19/// - **Registers**: LwwRegister (timestamp-based)
20/// - **Counters**: GCounter (grow-only), PnCounter (increment/decrement)
21/// - **Collections**: Rga, UnorderedMap, UnorderedSet, Vector
22/// - **Special**: UserStorage, FrozenStorage, Custom
23#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Serialize, Deserialize)]
24#[cfg_attr(feature = "borsh", derive(BorshSerialize, BorshDeserialize))]
25pub enum CrdtType {
26    // =========================================================================
27    // REGISTERS
28    // =========================================================================
29    /// Last-Writer-Wins Register.
30    ///
31    /// Wraps primitive types with timestamp-based conflict resolution.
32    /// Merge: Higher HLC timestamp wins, with node ID as tie-breaker.
33    ///
34    /// The inner type name enables proper deserialization during merge.
35    LwwRegister {
36        /// Inner type name (e.g., "String", "u64", "MyStruct")
37        inner_type: String,
38    },
39
40    // =========================================================================
41    // COUNTERS
42    // =========================================================================
43    /// Grow-only Counter.
44    ///
45    /// Supports only increment operations; value can never decrease.
46    /// Internally tracks increments per executor.
47    /// Merge: Take maximum of each executor's count.
48    GCounter,
49
50    /// Positive-Negative Counter.
51    ///
52    /// Supports both increment and decrement operations.
53    /// Internally uses two maps: positive and negative counts per executor.
54    /// Merge: Union of positive maps, union of negative maps, then compute difference.
55    PnCounter,
56
57    // =========================================================================
58    // COLLECTIONS
59    // =========================================================================
60    /// Replicated Growable Array.
61    ///
62    /// CRDT for collaborative text editing and ordered sequences.
63    /// Supports concurrent insertions and deletions with causal ordering.
64    /// Merge: Interleave elements by (timestamp, node_id) ordering.
65    Rga,
66
67    /// Unordered Map.
68    ///
69    /// Key-value store with add-wins semantics for keys.
70    /// Keys are never lost once added (tombstoned but retained).
71    /// Values are merged recursively if they implement Mergeable.
72    /// Merge: Union of keys, recursive merge of values.
73    UnorderedMap {
74        /// Key type name
75        key_type: String,
76        /// Value type name (may be a nested CRDT)
77        value_type: String,
78    },
79
80    /// Unordered Set.
81    ///
82    /// Collection of unique values with add-wins semantics.
83    /// Elements are never lost once added.
84    /// Merge: Union of all elements from both sets.
85    UnorderedSet {
86        /// Element type name
87        element_type: String,
88    },
89
90    /// Vector (ordered collection).
91    ///
92    /// Ordered list with append operations.
93    /// Elements are identified by index + timestamp for ordering.
94    /// Merge: Element-wise merge by index with timestamp ordering.
95    Vector {
96        /// Element type name (may be a nested CRDT)
97        element_type: String,
98    },
99
100    // =========================================================================
101    // SPECIAL STORAGE
102    // =========================================================================
103    /// User Storage.
104    ///
105    /// Per-user data storage with signature-based access control.
106    /// Only the owning user (identified by executor ID) can modify their data.
107    /// Merge: Latest update per user based on nonce/timestamp.
108    UserStorage,
109
110    /// Frozen Storage.
111    ///
112    /// Write-once storage for immutable data.
113    /// Data can be written once and never modified or deleted.
114    /// Merge: First-write-wins (subsequent writes are no-ops).
115    FrozenStorage,
116
117    /// Custom CRDT with app-defined merge.
118    ///
119    /// For types annotated with `#[derive(CrdtState)]` that define custom merge logic.
120    /// The string identifies the custom type name within the application.
121    /// Merge: Dispatched to WASM runtime to call the app's merge function.
122    Custom(String),
123}
124
125impl Default for CrdtType {
126    fn default() -> Self {
127        Self::LwwRegister {
128            inner_type: String::new(),
129        }
130    }
131}
132
133impl CrdtType {
134    /// Create an LwwRegister with a known inner type.
135    #[must_use]
136    pub fn lww_register(inner_type: impl Into<String>) -> Self {
137        Self::LwwRegister {
138            inner_type: inner_type.into(),
139        }
140    }
141
142    /// Create an UnorderedMap with known key and value types.
143    #[must_use]
144    pub fn unordered_map(key_type: impl Into<String>, value_type: impl Into<String>) -> Self {
145        Self::UnorderedMap {
146            key_type: key_type.into(),
147            value_type: value_type.into(),
148        }
149    }
150
151    /// Create an UnorderedSet with a known element type.
152    #[must_use]
153    pub fn unordered_set(element_type: impl Into<String>) -> Self {
154        Self::UnorderedSet {
155            element_type: element_type.into(),
156        }
157    }
158
159    /// Create a Vector with a known element type.
160    #[must_use]
161    pub fn vector(element_type: impl Into<String>) -> Self {
162        Self::Vector {
163            element_type: element_type.into(),
164        }
165    }
166
167    /// Returns `true` if this is a counter type (GCounter or PnCounter).
168    #[must_use]
169    pub const fn is_counter(&self) -> bool {
170        matches!(self, Self::GCounter | Self::PnCounter)
171    }
172
173    /// Returns `true` if this is a set type.
174    #[must_use]
175    pub const fn is_set(&self) -> bool {
176        matches!(self, Self::UnorderedSet { .. })
177    }
178
179    /// Returns `true` if this is a collection type (map, set, vector, or array).
180    #[must_use]
181    pub const fn is_collection(&self) -> bool {
182        matches!(
183            self,
184            Self::UnorderedMap { .. } | Self::UnorderedSet { .. } | Self::Vector { .. } | Self::Rga
185        )
186    }
187
188    /// Returns `true` if this is a custom CRDT type.
189    #[must_use]
190    pub const fn is_custom(&self) -> bool {
191        matches!(self, Self::Custom(_))
192    }
193
194    /// Returns `true` if this type requires special storage handling.
195    #[must_use]
196    pub const fn is_special_storage(&self) -> bool {
197        matches!(self, Self::UserStorage | Self::FrozenStorage)
198    }
199}
200
201#[cfg(test)]
202mod tests {
203    use super::*;
204
205    #[test]
206    fn test_default_is_lww_register() {
207        assert!(matches!(CrdtType::default(), CrdtType::LwwRegister { .. }));
208    }
209
210    #[test]
211    fn test_lww_register_constructor() {
212        let lww = CrdtType::lww_register("String");
213        assert_eq!(
214            lww,
215            CrdtType::LwwRegister {
216                inner_type: "String".to_string()
217            }
218        );
219    }
220
221    #[test]
222    fn test_is_counter() {
223        assert!(CrdtType::GCounter.is_counter());
224        assert!(CrdtType::PnCounter.is_counter());
225        assert!(!CrdtType::lww_register("u64").is_counter());
226        assert!(!CrdtType::unordered_map("String", "u64").is_counter());
227    }
228
229    #[test]
230    fn test_is_set() {
231        assert!(CrdtType::unordered_set("String").is_set());
232        assert!(!CrdtType::unordered_map("String", "u64").is_set());
233        assert!(!CrdtType::vector("u64").is_set());
234    }
235
236    #[test]
237    fn test_is_collection() {
238        assert!(CrdtType::unordered_map("String", "u64").is_collection());
239        assert!(CrdtType::unordered_set("String").is_collection());
240        assert!(CrdtType::vector("u64").is_collection());
241        assert!(CrdtType::Rga.is_collection());
242        assert!(!CrdtType::lww_register("u64").is_collection());
243        assert!(!CrdtType::GCounter.is_collection());
244        assert!(!CrdtType::PnCounter.is_collection());
245    }
246
247    #[test]
248    fn test_is_custom() {
249        assert!(CrdtType::Custom("test".to_string()).is_custom());
250        assert!(!CrdtType::lww_register("u64").is_custom());
251    }
252
253    #[test]
254    fn test_is_special_storage() {
255        assert!(CrdtType::UserStorage.is_special_storage());
256        assert!(CrdtType::FrozenStorage.is_special_storage());
257        assert!(!CrdtType::lww_register("u64").is_special_storage());
258        assert!(!CrdtType::GCounter.is_special_storage());
259    }
260
261    #[test]
262    fn test_serde_roundtrip() {
263        let types = [
264            CrdtType::lww_register("String"),
265            CrdtType::lww_register("u64"),
266            CrdtType::GCounter,
267            CrdtType::PnCounter,
268            CrdtType::Rga,
269            CrdtType::unordered_map("String", "u64"),
270            CrdtType::unordered_set("String"),
271            CrdtType::vector("u64"),
272            CrdtType::UserStorage,
273            CrdtType::FrozenStorage,
274            CrdtType::Custom("my_type".to_string()),
275        ];
276
277        for crdt_type in &types {
278            let json = serde_json::to_string(crdt_type).unwrap();
279            let decoded: CrdtType = serde_json::from_str(&json).unwrap();
280            assert_eq!(*crdt_type, decoded);
281        }
282    }
283
284    #[cfg(feature = "borsh")]
285    #[test]
286    fn test_borsh_roundtrip() {
287        let types = [
288            CrdtType::lww_register("String"),
289            CrdtType::lww_register("u64"),
290            CrdtType::GCounter,
291            CrdtType::PnCounter,
292            CrdtType::Rga,
293            CrdtType::unordered_map("String", "u64"),
294            CrdtType::unordered_set("String"),
295            CrdtType::vector("u64"),
296            CrdtType::UserStorage,
297            CrdtType::FrozenStorage,
298            CrdtType::Custom("my_type".to_string()),
299        ];
300
301        for crdt_type in &types {
302            let bytes = borsh::to_vec(crdt_type).unwrap();
303            let decoded: CrdtType = borsh::from_slice(&bytes).unwrap();
304            assert_eq!(*crdt_type, decoded);
305        }
306    }
307}
calimero_primitives/crdt.rs

calimero_primitives/
crdt.rs
