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#[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 #[serde(serialize_with = "serialize_elements", deserialize_with = "deserialize_elements")]
50 pub elements: Vec<T>,
51 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(); 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 pub fn new() -> Self {
114 Self::default()
115 }
116}
117
118impl<T: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static> GSet<T> {
119 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 pub fn contains(&self, element: &T) -> bool {
129 self.elements.binary_search(element).is_ok()
130 }
131
132 pub fn iter(&self) -> impl Iterator<Item = &T> {
134 self.elements.iter()
135 }
136
137 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
169pub 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
233impl<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}