1use 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#[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 #[serde(serialize_with = "serialize_elements", deserialize_with = "deserialize_elements")]
53 pub elements: Vec<T>,
54 #[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(); 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 pub fn new() -> Self {
118 Self::default()
119 }
120}
121
122impl<T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static> GSet<T> {
123 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 pub fn contains(&self, element: &T) -> bool {
133 self.elements.binary_search(element).is_ok()
134 }
135
136 pub fn iter(&self) -> impl Iterator<Item = &T> {
138 self.elements.iter()
139 }
140
141 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
173pub 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
237impl<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}