Skip to main content

crdt_data_types/
g_set.rs

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