1use crate::lww_map_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 = "K: Serialize, V: Serialize",
48 deserialize = "K: DeserializeOwned + Eq + Hash + Ord, V: DeserializeOwned"
49))]
50pub struct LWWMap<K: Eq + Hash + Ord, V> {
51 #[serde(serialize_with = "serialize_entries", deserialize_with = "deserialize_entries")]
53 pub entries: Vec<(K, (V, u64, String))>,
54 #[serde(default)]
56 pub vclock: VectorClock,
57}
58
59fn serialize_entries<S, K, V>(
60 entries: &Vec<(K, (V, u64, String))>,
61 serializer: S,
62) -> Result<S::Ok, S::Error>
63where
64 S: serde::Serializer,
65 K: Serialize,
66 V: Serialize,
67{
68 use serde::ser::SerializeMap;
69 let mut map = serializer.serialize_map(Some(entries.len()))?;
70 for (k, v) in entries {
71 map.serialize_entry(k, v)?;
72 }
73 map.end()
74}
75
76type LWWMapEntry<K, V> = (K, (V, u64, String));
77
78fn deserialize_entries<'de, D, K, V>(deserializer: D) -> Result<Vec<LWWMapEntry<K, V>>, D::Error>
79where
80 D: serde::Deserializer<'de>,
81 K: DeserializeOwned + Eq + Hash + Ord,
82 V: DeserializeOwned,
83{
84 struct EntriesVisitor<K, V>(std::marker::PhantomData<(K, V)>);
85
86 impl<'de, K, V> serde::de::Visitor<'de> for EntriesVisitor<K, V>
87 where
88 K: DeserializeOwned + Eq + Hash + Ord,
89 V: DeserializeOwned,
90 {
91 type Value = Vec<LWWMapEntry<K, V>>;
92
93 fn expecting(&self, formatter: &mut std::fmt::Formatter) -> std::fmt::Result {
94 formatter.write_str("a map of entries")
95 }
96
97 fn visit_map<M>(self, mut access: M) -> Result<Self::Value, M::Error>
98 where
99 M: serde::de::MapAccess<'de>,
100 {
101 let mut entries: Vec<LWWMapEntry<K, V>> =
102 Vec::with_capacity(access.size_hint().unwrap_or(0));
103 while let Some((key, value)) = access.next_entry()? {
104 entries.push((key, value));
105 }
106 entries.sort_by(|a, b| a.0.cmp(&b.0));
108 Ok(entries)
109 }
110 }
111
112 deserializer.deserialize_map(EntriesVisitor(std::marker::PhantomData))
113}
114
115impl<K: Eq + Hash + Ord, V> Default for LWWMap<K, V> {
116 fn default() -> Self {
117 Self {
118 entries: Vec::new(),
119 vclock: VectorClock::new(),
120 }
121 }
122}
123
124impl<K: Eq + Hash + Ord, V> LWWMap<K, V> {
125 pub fn new() -> Self {
127 Self::default()
128 }
129}
130
131impl<K, V> LWWMap<K, V>
132where
133 K: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
134 V: Clone + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
135{
136 pub fn insert(&mut self, node_id: &str, key: K, value: V, timestamp: u64) {
141 let node_id_str = node_id.to_string();
142
143 match self.entries.binary_search_by(|(k, _)| k.cmp(&key)) {
144 Ok(idx) => {
145 let (_, (val, ts, nid)) = &self.entries[idx];
146 let update = timestamp > *ts
147 || (timestamp == *ts && node_id_str > *nid)
148 || (timestamp == *ts
149 && node_id_str == *nid
150 && value > *val);
151
152 if update {
153 self.entries[idx] = (key, (value, timestamp, node_id_str));
154 self.vclock.increment(node_id);
155 }
156 }
157 Err(idx) => {
158 self.entries.insert(idx, (key, (value, timestamp, node_id_str)));
159 self.vclock.increment(node_id);
160 }
161 }
162 }
163
164 pub fn remove(&mut self, key: &K) {
170 if let Ok(idx) = self.entries.binary_search_by(|(k, _)| k.cmp(key)) {
171 self.entries.remove(idx);
172 }
173 }
174
175 pub fn get(&self, key: &K) -> Option<&V> {
177 self.entries
178 .binary_search_by(|(k, _)| k.cmp(key))
179 .ok()
180 .map(|idx| &self.entries[idx].1.0)
181 }
182
183 pub fn merge(&mut self, other: &Self) {
185 let mut result = Vec::with_capacity(self.entries.len() + other.entries.len());
186 let mut i = 0;
187 let mut j = 0;
188
189 while i < self.entries.len() && j < other.entries.len() {
190 let (k1, (v1, ts1, nid1)) = &self.entries[i];
191 let (k2, (v2, ts2, nid2)) = &other.entries[j];
192
193 match k1.cmp(k2) {
194 Ordering::Less => {
195 result.push(self.entries[i].clone());
196 i += 1;
197 }
198 Ordering::Greater => {
199 result.push(other.entries[j].clone());
200 j += 1;
201 }
202 Ordering::Equal => {
203 let update = *ts2 > *ts1
205 || (*ts2 == *ts1 && nid2 > nid1)
206 || (*ts2 == *ts1
207 && nid2 == nid1
208 && v2 > v1);
209
210 if update {
211 result.push(other.entries[j].clone());
212 } else {
213 result.push(self.entries[i].clone());
214 }
215 i += 1;
216 j += 1;
217 }
218 }
219 }
220
221 while i < self.entries.len() {
222 result.push(self.entries[i].clone());
223 i += 1;
224 }
225 while j < other.entries.len() {
226 result.push(other.entries[j].clone());
227 j += 1;
228 }
229
230 self.entries = result;
231 self.vclock.merge(&other.vclock);
232 }
233}
234
235pub struct LWWMapReader<'a, K: Eq + Hash + Ord, V> {
240 bytes: &'a [u8],
241 _phantom: std::marker::PhantomData<(K, V)>,
242}
243
244impl<'a, K, V> LWWMapReader<'a, K, V>
245where
246 K: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
247 V: Clone + Serialize + DeserializeOwned + Send + Sync + 'static,
248{
249 pub fn new(bytes: &'a [u8]) -> Self {
250 Self {
251 bytes,
252 _phantom: std::marker::PhantomData,
253 }
254 }
255
256 fn to_map(&self) -> Result<LWWMap<K, V>, CrdtError> {
257 let reader = serialize::read_message(self.bytes, ReaderOptions::new())
258 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
259 let lww_map = reader
260 .get_root::<lww_map_capnp::lww_map::Reader>()
261 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
262
263 let mut entries = Vec::new();
264 let entries_list = lww_map
265 .get_entries()
266 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
267
268 for entry in entries_list {
269 let key_bytes = entry
270 .get_key()
271 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
272 let key: K = bincode::deserialize(key_bytes)
273 .map_err(|e: bincode::Error| CrdtError::Deserialization(e.to_string()))?;
274
275 let value_bytes = entry
276 .get_value()
277 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
278 let value: V = bincode::deserialize(value_bytes)
279 .map_err(|e: bincode::Error| CrdtError::Deserialization(e.to_string()))?;
280
281 let timestamp = entry.get_timestamp();
282 let node_id = entry
283 .get_node_id()
284 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?
285 .to_string()
286 .map_err(|e: std::str::Utf8Error| CrdtError::Deserialization(e.to_string()))?;
287
288 entries.push((key, (value, timestamp, node_id)));
289 }
290 entries.sort_by(|a, b| a.0.cmp(&b.0));
292
293 let vclock = if lww_map.has_vclock() {
294 let vc_bytes = lww_map
295 .get_vclock()
296 .map_err(|e: capnp::Error| CrdtError::Deserialization(e.to_string()))?;
297 VectorClock::merge_from_readers(&[crate::vector_clock::VectorClockReader::new(
298 vc_bytes,
299 )])?
300 } else {
301 VectorClock::new()
302 };
303
304 Ok(LWWMap { entries, vclock })
305 }
306}
307
308impl<'a, K, V> CrdtReader<'a> for LWWMapReader<'a, K, V>
309where
310 K: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
311 V: Clone + Serialize + DeserializeOwned + Send + Sync + 'static,
312{
313 fn is_empty(&self) -> Result<bool, CrdtError> {
314 Ok(self.to_map()?.entries.is_empty())
315 }
316}
317
318impl<K, V> Crdt for LWWMap<K, V>
323where
324 K: Clone + Eq + Hash + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
325 V: Clone + Ord + Serialize + DeserializeOwned + Send + Sync + 'static,
326{
327 type Reader<'a> = LWWMapReader<'a, K, V>;
328
329 fn merge_from_readers(readers: &[Self::Reader<'_>]) -> Result<Self, CrdtError> {
330 let mut result = LWWMap::new();
331 for reader in readers {
332 result.merge(&reader.to_map()?);
333 }
334 Ok(result)
335 }
336
337 fn to_capnp_bytes(&self) -> Vec<u8> {
338 let mut message = Builder::new(HeapAllocator::new());
339 {
340 let mut lww_map = message.init_root::<lww_map_capnp::lww_map::Builder>();
341 let mut entries = lww_map.reborrow().init_entries(self.entries.len() as u32);
342 for (idx, (key, (value, timestamp, node_id))) in self.entries.iter().enumerate() {
343 let mut entry = entries.reborrow().get(idx as u32);
344 let key_bytes = bincode::serialize(key).expect("LWWMap key serialization fail");
345 let value_bytes =
346 bincode::serialize(value).expect("LWWMap value serialization fail");
347 entry.set_key(&key_bytes);
348 entry.set_value(&value_bytes);
349 entry.set_timestamp(*timestamp);
350 entry.set_node_id(node_id.as_str().into());
351 }
352 let vclock_bytes = self.vclock.to_capnp_bytes();
353 lww_map.set_vclock(&vclock_bytes);
354 }
355 let mut buf = Vec::new();
356 serialize::write_message(&mut buf, &message).expect("LWWMap serialization fail");
357 buf
358 }
359
360 fn is_empty(&self) -> bool {
361 self.entries.is_empty()
362 }
363
364 fn validate(&self) -> Result<(), CrdtError> {
365 Ok(())
366 }
367}