1use crate::lww_set_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)]
44#[serde(bound(
45 serialize = "T: Serialize",
46 deserialize = "T: DeserializeOwned + Eq + Hash + Ord"
47))]
48pub struct LWWSet<T: Eq + Hash + Ord> {
49 #[serde(serialize_with = "serialize_lww_map", deserialize_with = "deserialize_lww_map")]
51 pub add_set: Vec<(T, (u64, String))>,
52 #[serde(serialize_with = "serialize_lww_map", deserialize_with = "deserialize_lww_map")]
54 pub remove_set: Vec<(T, (u64, String))>,
55 #[serde(default)]
57 pub vclock: VectorClock,
58}
59
60fn serialize_lww_map<S, T>(
61 elements: &Vec<(T, (u64, String))>,
62 serializer: S,
63) -> Result<S::Ok, S::Error>
64where
65 S: serde::Serializer,
66 T: Serialize,
67{
68 use serde::ser::SerializeMap;
69 let mut map = serializer.serialize_map(Some(elements.len()))?;
70 for (k, v) in elements {
71 map.serialize_entry(k, v)?;
72 }
73 map.end()
74}
75
76type LWWSetEntry<T> = (T, (u64, String));
77
78fn deserialize_lww_map<'de, D, T>(deserializer: D) -> Result<Vec<LWWSetEntry<T>>, D::Error>
79where
80 D: serde::Deserializer<'de>,
81 T: DeserializeOwned + Eq + Hash + Ord,
82{
83 struct LWWMapVisitor<T>(std::marker::PhantomData<T>);
84
85 impl<'de, T> serde::de::Visitor<'de> for LWWMapVisitor<T>
86 where
87 T: DeserializeOwned + Eq + Hash + Ord,
88 {
89 type Value = Vec<LWWSetEntry<T>>;
90
91 fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
92 formatter.write_str("a map of elements to timestamps")
93 }
94
95 fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
96 where
97 M: serde::de::MapAccess<'de>,
98 {
99 let mut elements: Vec<LWWSetEntry<T>> =
100 Vec::with_capacity(access.size_hint().unwrap_or(0));
101 while let Some((key, value)) = access.next_entry()? {
102 elements.push((key, value));
103 }
104 elements.sort_by(|a, b| a.0.cmp(&b.0));
106 Ok(elements)
107 }
108 }
109
110 deserializer.deserialize_map(LWWMapVisitor(std::marker::PhantomData))
111}
112
113impl<T: Eq + Hash + Ord> Default for LWWSet<T> {
114 fn default() -> Self {
115 Self {
116 add_set: Vec::new(),
117 remove_set: Vec::new(),
118 vclock: VectorClock::new(),
119 }
120 }
121}
122
123impl<T: Eq + Hash + Ord> LWWSet<T> {
124 pub fn new() -> Self {
126 Self::default()
127 }
128}
129
130impl<T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static> LWWSet<T> {
131 pub fn insert(&mut self, node_id: &str, element: T, timestamp: u64) {
133 let node_id_str = node_id.to_string();
134 match self.add_set.binary_search_by(|(e, _)| e.cmp(&element)) {
135 Ok(idx) => {
136 let (_, (ts, nid)) = &self.add_set[idx];
137 if timestamp > *ts || (timestamp == *ts && node_id_str > *nid) {
138 self.add_set[idx] = (element, (timestamp, node_id_str));
139 self.vclock.increment(node_id);
140 }
141 }
142 Err(idx) => {
143 self.add_set.insert(idx, (element, (timestamp, node_id_str)));
144 self.vclock.increment(node_id);
145 }
146 }
147 }
148
149 pub fn remove(&mut self, node_id: &str, element: T, timestamp: u64) {
151 let node_id_str = node_id.to_string();
152 match self.remove_set.binary_search_by(|(e, _)| e.cmp(&element)) {
153 Ok(idx) => {
154 let (_, (ts, nid)) = &self.remove_set[idx];
155 if timestamp > *ts || (timestamp == *ts && node_id_str > *nid) {
156 self.remove_set[idx] = (element, (timestamp, node_id_str));
157 self.vclock.increment(node_id);
158 }
159 }
160 Err(idx) => {
161 self.remove_set.insert(idx, (element, (timestamp, node_id_str)));
162 self.vclock.increment(node_id);
163 }
164 }
165 }
166
167 pub fn contains(&self, element: &T) -> bool {
172 let add_entry = self
173 .add_set
174 .binary_search_by(|(e, _)| e.cmp(element))
175 .map(|idx| &self.add_set[idx].1)
176 .ok();
177
178 let remove_entry = self
179 .remove_set
180 .binary_search_by(|(e, _)| e.cmp(element))
181 .map(|idx| &self.remove_set[idx].1)
182 .ok();
183
184 match (add_entry, remove_entry) {
185 (Some((a_ts, a_id)), Some((r_ts, r_id))) => {
186 *a_ts > *r_ts || (*a_ts == *r_ts && a_id > r_id)
187 }
188 (Some(_), None) => true,
189 _ => false,
190 }
191 }
192
193 pub fn iter(&self) -> impl Iterator<Item = &T> {
195 self.add_set.iter().filter_map(move |(e, _)| {
196 if self.contains(e) {
197 Some(e)
198 } else {
199 None
200 }
201 })
202 }
203
204 pub fn merge(&mut self, other: &Self) {
206 self.add_set = Self::merge_vecs(&self.add_set, &other.add_set);
207 self.remove_set = Self::merge_vecs(&self.remove_set, &other.remove_set);
208 self.vclock.merge(&other.vclock);
209 }
210
211 fn merge_vecs(
212 left: &[(T, (u64, String))],
213 right: &[(T, (u64, String))],
214 ) -> Vec<(T, (u64, String))> {
215 let mut result = Vec::with_capacity(left.len() + right.len());
216 let mut i = 0;
217 let mut j = 0;
218
219 while i < left.len() && j < right.len() {
220 let (k1, (ts1, id1)) = &left[i];
221 let (k2, (ts2, id2)) = &right[j];
222
223 match k1.cmp(k2) {
224 Ordering::Less => {
225 result.push((k1.clone(), (*ts1, id1.clone())));
226 i += 1;
227 }
228 Ordering::Greater => {
229 result.push((k2.clone(), (*ts2, id2.clone())));
230 j += 1;
231 }
232 Ordering::Equal => {
233 if *ts1 > *ts2 || (*ts1 == *ts2 && id1 > id2) {
235 result.push((k1.clone(), (*ts1, id1.clone())));
236 } else {
237 result.push((k2.clone(), (*ts2, id2.clone())));
238 }
239 i += 1;
240 j += 1;
241 }
242 }
243 }
244
245 while i < left.len() {
246 result.push(left[i].clone());
247 i += 1;
248 }
249 while j < right.len() {
250 result.push(right[j].clone());
251 j += 1;
252 }
253
254 result
255 }
256}
257
258pub struct LWWSetReader<'a, T: Eq + Hash + Ord> {
263 bytes: &'a [u8],
264 _phantom: std::marker::PhantomData<T>,
265}
266
267impl<'a, T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static>
268 LWWSetReader<'a, T>
269{
270 pub fn new(bytes: &'a [u8]) -> Self {
271 Self {
272 bytes,
273 _phantom: std::marker::PhantomData,
274 }
275 }
276
277 fn to_set(&self) -> Result<LWWSet<T>, CrdtError> {
278 let reader = serialize::read_message(self.bytes, ReaderOptions::new())
279 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
280 let lww_set = reader
281 .get_root::<lww_set_capnp::lww_set::Reader>()
282 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
283
284 let mut add_set = Vec::new();
285 let adds = lww_set
286 .get_add_set()
287 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
288 for entry in adds {
289 let entry: lww_set_capnp::lww_set::entry::Reader = entry;
290 let element: T = bincode::deserialize(
291 entry
292 .get_element()
293 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?,
294 )
295 .map_err(|e: bincode::Error| CrdtError::Deserialization(e.to_string()))?;
296 add_set.push((
297 element,
298 (
299 entry.get_timestamp(),
300 entry
301 .get_node_id()
302 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?
303 .to_string()
304 .map_err(|e: std::str::Utf8Error| {
305 CrdtError::Deserialization(e.to_string())
306 })?,
307 ),
308 ));
309 }
310 add_set.sort_by(|a, b| a.0.cmp(&b.0));
312
313 let mut remove_set = Vec::new();
314 let removes = lww_set
315 .get_remove_set()
316 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
317 for entry in removes {
318 let entry: lww_set_capnp::lww_set::entry::Reader = entry;
319 let element: T = bincode::deserialize(
320 entry
321 .get_element()
322 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?,
323 )
324 .map_err(|e: bincode::Error| CrdtError::Deserialization(e.to_string()))?;
325 remove_set.push((
326 element,
327 (
328 entry.get_timestamp(),
329 entry
330 .get_node_id()
331 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?
332 .to_string()
333 .map_err(|e: std::str::Utf8Error| {
334 CrdtError::Deserialization(e.to_string())
335 })?,
336 ),
337 ));
338 }
339 remove_set.sort_by(|a, b| a.0.cmp(&b.0));
341
342 let vclock = if lww_set.has_vclock() {
343 let vc_bytes = lww_set
344 .get_vclock()
345 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
346 VectorClock::merge_from_readers(&[crate::vector_clock::VectorClockReader::new(
347 vc_bytes,
348 )])?
349 } else {
350 VectorClock::new()
351 };
352
353 Ok(LWWSet {
354 add_set,
355 remove_set,
356 vclock,
357 })
358 }
359}
360
361impl<'a, T> CrdtReader<'a> for LWWSetReader<'a, T>
362where
363 T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
364{
365 fn is_empty(&self) -> Result<bool, CrdtError> {
366 Ok(self.to_set()?.add_set.is_empty())
367 }
368}
369
370impl<T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static> Crdt
375 for LWWSet<T>
376{
377 type Reader<'a> = LWWSetReader<'a, T>;
378
379 fn merge_from_readers(readers: &[Self::Reader<'_>]) -> Result<Self, CrdtError> {
380 let mut result = LWWSet::new();
381 for reader in readers {
382 result.merge(&reader.to_set()?);
383 }
384 Ok(result)
385 }
386
387 fn to_capnp_bytes(&self) -> Vec<u8> {
388 let mut message = Builder::new(HeapAllocator::new());
389 {
390 let mut lww_set = message.init_root::<lww_set_capnp::lww_set::Builder>();
391
392 let mut adds = lww_set.reborrow().init_add_set(self.add_set.len() as u32);
393 for (idx, (element, (timestamp, node_id))) in self.add_set.iter().enumerate() {
394 let mut entry = adds.reborrow().get(idx as u32);
395 let bytes = bincode::serialize(element).expect("LWWSet element serialization fail");
396 entry.set_element(&bytes);
397 entry.set_timestamp(*timestamp);
398 entry.set_node_id(node_id.as_str().into());
399 }
400
401 let mut removes = lww_set
402 .reborrow()
403 .init_remove_set(self.remove_set.len() as u32);
404 for (idx, (element, (timestamp, node_id))) in self.remove_set.iter().enumerate() {
405 let mut entry = removes.reborrow().get(idx as u32);
406 let bytes = bincode::serialize(element).expect("LWWSet element serialization fail");
407 entry.set_element(&bytes);
408 entry.set_timestamp(*timestamp);
409 entry.set_node_id(node_id.as_str().into());
410 }
411
412 let vclock_bytes = self.vclock.to_capnp_bytes();
413 lww_set.set_vclock(&vclock_bytes);
414 }
415 let mut buf = Vec::new();
416 serialize::write_message(&mut buf, &message).expect("LWWSet serialization fail");
417 buf
418 }
419
420 fn is_empty(&self) -> bool {
421 self.add_set.is_empty()
422 }
423
424 fn validate(&self) -> Result<(), CrdtError> {
425 Ok(())
426 }
427}