crdt_data_types/
g_set.rs

1use crate::gset_capnp;
2use crate::traits::{Crdt, CrdtError, CrdtReader};
3use crate::vector_clock::VectorClock;
4use capnp::message::{Builder, HeapAllocator, ReaderOptions};
5use capnp::serialize;
6use serde::{de::DeserializeOwned, Deserialize, Serialize};
7use std::cmp::Ordering;
8use std::hash::Hash;
9
10/// G-Set: A Grow-only Set CRDT.
11///
12/// A G-Set is a set that only supports element addition. Elements cannot be
13/// removed once added. This leads to simple merge semantics (set union).
14///
15/// # Key Properties
16///
17/// - **Grow-only**: Elements can be added but never removed.
18/// - **Merge Strategy**: Set union.
19/// - **Simplicity**: Very low overhead and simple implementation.
20///
21/// # Algebraic Properties
22///
23/// - **Commutativity**: Yes.
24/// - **Associativity**: Yes.
25/// - **Idempotence**: Yes.
26///
27/// # Example
28///
29/// ```
30/// use crdt_data_types::GSet;
31///
32/// let mut set1 = GSet::new();
33/// set1.insert("node_a", "apple".to_string());
34///
35/// let mut set2 = GSet::new();
36/// set2.insert("node_b", "banana".to_string());
37///
38/// set1.merge(&set2);
39/// assert!(set1.contains(&"apple".to_string()));
40/// assert!(set1.contains(&"banana".to_string()));
41/// ```
42#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
43#[serde(bound(
44    serialize = "T: Serialize",
45    deserialize = "T: DeserializeOwned + Eq + Hash + Ord"
46))]
47pub struct GSet<T: Eq + Hash + Ord> {
48    /// Internal storage for set elements.
49    #[serde(serialize_with = "serialize_elements", deserialize_with = "deserialize_elements")]
50    pub elements: Vec<T>,
51    /// Vector clock for tracking causal history.
52    pub vclock: VectorClock,
53}
54
55fn serialize_elements<S, T>(elements: &Vec<T>, serializer: S) -> Result<S::Ok, S::Error>
56where
57    S: serde::Serializer,
58    T: Serialize,
59{
60    use serde::ser::SerializeSeq;
61    let mut seq = serializer.serialize_seq(Some(elements.len()))?;
62    for e in elements {
63        seq.serialize_element(e)?;
64    }
65    seq.end()
66}
67
68fn deserialize_elements<'de, D, T>(deserializer: D) -> Result<Vec<T>, D::Error>
69where
70    D: serde::Deserializer<'de>,
71    T: DeserializeOwned + Eq + Hash + Ord,
72{
73    struct ElementsVisitor<T>(std::marker::PhantomData<T>);
74
75    impl<'de, T> serde::de::Visitor<'de> for ElementsVisitor<T>
76    where
77        T: DeserializeOwned + Eq + Hash + Ord,
78    {
79        type Value = Vec<T>;
80
81        fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
82            formatter.write_str("a sequence of elements")
83        }
84
85        fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
86        where
87            A: serde::de::SeqAccess<'de>,
88        {
89            let mut elements = Vec::with_capacity(seq.size_hint().unwrap_or(0));
90            while let Some(elem) = seq.next_element()? {
91                elements.push(elem);
92            }
93            elements.sort();
94            elements.dedup(); // Ensure uniqueness just in case
95            Ok(elements)
96        }
97    }
98
99    deserializer.deserialize_seq(ElementsVisitor(std::marker::PhantomData))
100}
101
102impl<T: Eq + Hash + Ord> Default for GSet<T> {
103    fn default() -> Self {
104        Self {
105            elements: Vec::new(),
106            vclock: VectorClock::new(),
107        }
108    }
109}
110
111impl<T: Eq + Hash + Ord> GSet<T> {
112    /// Creates a new, empty G-Set.
113    pub fn new() -> Self {
114        Self::default()
115    }
116}
117
118impl<T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static> GSet<T> {
119    /// Adds an element to the set.
120    pub fn insert(&mut self, node_id: &str, element: T) {
121        if let Err(idx) = self.elements.binary_search(&element) {
122            self.elements.insert(idx, element);
123            self.vclock.increment(node_id);
124        }
125    }
126
127    /// Returns true if the set contains the element.
128    pub fn contains(&self, element: &T) -> bool {
129        self.elements.binary_search(element).is_ok()
130    }
131
132    /// Iterator over the elements in the set.
133    pub fn iter(&self) -> impl Iterator<Item = &T> {
134        self.elements.iter()
135    }
136
137    /// Merges another G-Set into this one.
138    pub fn merge(&mut self, other: &Self) {
139        let mut result = Vec::with_capacity(self.elements.len() + other.elements.len());
140        let mut i = 0;
141        let mut j = 0;
142
143        while i < self.elements.len() && j < other.elements.len() {
144            match self.elements[i].cmp(&other.elements[j]) {
145                Ordering::Less => {
146                    result.push(self.elements[i].clone());
147                    i += 1;
148                }
149                Ordering::Greater => {
150                    result.push(other.elements[j].clone());
151                    j += 1;
152                }
153                Ordering::Equal => {
154                    result.push(self.elements[i].clone());
155                    i += 1;
156                    j += 1;
157                }
158            }
159        }
160
161        result.extend_from_slice(&self.elements[i..]);
162        result.extend_from_slice(&other.elements[j..]);
163
164        self.elements = result;
165        self.vclock.merge(&other.vclock);
166    }
167}
168
169// ============================================================================
170// Zero-Copy Reader
171// ============================================================================
172
173pub struct GSetReader<'a, T: Eq + Hash + Ord> {
174    bytes: &'a [u8],
175    _phantom: std::marker::PhantomData<T>,
176}
177
178impl<'a, T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static>
179    GSetReader<'a, T>
180{
181    pub fn new(bytes: &'a [u8]) -> Self {
182        Self {
183            bytes,
184            _phantom: std::marker::PhantomData,
185        }
186    }
187
188    fn to_set(&self) -> Result<GSet<T>, CrdtError> {
189        let reader = serialize::read_message(self.bytes, ReaderOptions::new())
190            .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
191        let gset = reader
192            .get_root::<gset_capnp::g_set::Reader>()
193            .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
194
195        let mut elements = Vec::new();
196        let elements_list = gset
197            .get_elements()
198            .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
199
200        for entry in elements_list {
201            let bytes = entry.map_err(|e| CrdtError::Deserialization(e.to_string()))?;
202            let element: T = bincode::deserialize(bytes)
203                .map_err(|e: bincode::Error| CrdtError::Deserialization(e.to_string()))?;
204            elements.push(element);
205        }
206        elements.sort();
207        elements.dedup();
208
209        let vclock = if gset.has_vclock() {
210            let vc_bytes = gset
211                .get_vclock()
212                .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
213            VectorClock::merge_from_readers(&[crate::vector_clock::VectorClockReader::new(
214                vc_bytes,
215            )])?
216        } else {
217            VectorClock::new()
218        };
219
220        Ok(GSet { elements, vclock })
221    }
222}
223
224impl<'a, T> CrdtReader<'a> for GSetReader<'a, T>
225where
226    T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
227{
228    fn is_empty(&self) -> Result<bool, CrdtError> {
229        Ok(self.to_set()?.elements.is_empty())
230    }
231}
232
233// ============================================================================
234// CRDT Trait Implementation
235// ============================================================================
236
237impl<T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static> Crdt
238    for GSet<T>
239{
240    type Reader<'a> = GSetReader<'a, T>;
241
242    fn merge_from_readers(readers: &[Self::Reader<'_>]) -> Result<Self, CrdtError> {
243        let mut result = GSet::new();
244        for reader in readers {
245            result.merge(&reader.to_set()?);
246        }
247        Ok(result)
248    }
249
250    fn to_capnp_bytes(&self) -> Vec<u8> {
251        let mut message = Builder::new(HeapAllocator::new());
252        {
253            let mut gset = message.init_root::<gset_capnp::g_set::Builder>();
254            let mut elements = gset.reborrow().init_elements(self.elements.len() as u32);
255            for (idx, element) in self.elements.iter().enumerate() {
256                let bytes = bincode::serialize(element).expect("GSet element serialization fail");
257                elements.set(idx as u32, &bytes);
258            }
259            let vclock_bytes = self.vclock.to_capnp_bytes();
260            gset.set_vclock(&vclock_bytes);
261        }
262        let mut buf = Vec::new();
263        serialize::write_message(&mut buf, &message).expect("GSet serialization fail");
264        buf
265    }
266
267    fn is_empty(&self) -> bool {
268        self.elements.is_empty()
269    }
270
271    fn validate(&self) -> Result<(), CrdtError> {
272        Ok(())
273    }
274}