1use crate::crypto::{Digest, Hashable, sign::PublicKey};
2use serde::{Deserialize, Serialize};
3use sqlx::{
4 Decode, Encode, Sqlite, Type,
5 encode::IsNull,
6 error::BoxDynError,
7 sqlite::{SqliteArgumentValue, SqliteTypeInfo, SqliteValueRef},
8};
9use std::{
10 cmp::Ordering,
11 collections::BTreeMap,
12 fmt,
13 iter::Sum,
14 ops::{Add, AddAssign},
15};
16
17#[derive(Default, Clone, Serialize, Deserialize)]
26pub struct VersionVector(BTreeMap<PublicKey, u64>);
27
28impl VersionVector {
29 pub const fn new() -> Self {
31 Self(BTreeMap::new())
32 }
33
34 pub fn first(writer_id: PublicKey) -> Self {
35 let mut vv = Self::new();
36 vv.increment(writer_id);
37 vv
38 }
39
40 pub fn insert(&mut self, writer_id: PublicKey, version: u64) {
43 let old = self.0.entry(writer_id).or_insert(0);
44 *old = (*old).max(version);
45 }
46
47 pub fn get(&self, writer_id: &PublicKey) -> u64 {
49 self.0.get(writer_id).copied().unwrap_or(0)
50 }
51
52 pub fn increment(&mut self, writer_id: PublicKey) {
54 let version = self.0.entry(writer_id).or_insert(0);
55 *version += 1;
56 }
57
58 pub fn incremented(mut self, writer_id: PublicKey) -> Self {
60 self.increment(writer_id);
61 self
62 }
63
64 pub fn merge(&mut self, other: &Self) {
69 for (writer_id, version) in &other.0 {
70 self.insert(*writer_id, *version);
71 }
72 }
73
74 pub fn merged(mut self, other: &Self) -> Self {
76 self.merge(other);
77 self
78 }
79
80 pub fn saturating_sub(&self, rhs: &Self) -> Self {
82 self.0
83 .iter()
84 .filter_map(|(id, version)| Some((*id, version.checked_sub(rhs.get(id))?)))
85 .collect()
86 }
87
88 pub fn is_empty(&self) -> bool {
89 self.0.values().all(|version| *version == 0)
90 }
91
92 pub fn entries(&self) -> impl Iterator<Item = (&PublicKey, u64)> {
93 self.0
94 .iter()
95 .map(|(writer_id, version)| (writer_id, *version))
96 }
97
98 pub fn len(&self) -> usize {
99 self.0.values().filter(|version| **version > 0).count()
100 }
101}
102
103impl fmt::Debug for VersionVector {
108 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
109 write!(f, "{:?}", self.0)
110 }
111}
112
113impl PartialOrd for VersionVector {
114 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
115 use Ordering::*;
116
117 self.0
118 .iter()
119 .map(|(lhs_key, &lhs_version)| (lhs_version, other.get(lhs_key)))
120 .chain(
121 other
122 .0
123 .iter()
124 .filter(|(rhs_key, _)| !self.0.contains_key(rhs_key))
125 .map(|(_, &rhs_version)| (0, rhs_version)),
126 )
127 .try_fold(Equal, |ordering, (lhs_version, rhs_version)| {
128 match (ordering, lhs_version.cmp(&rhs_version)) {
129 (Equal, Equal) => Some(Equal),
130 (Equal, Less) | (Less, Equal) | (Less, Less) => Some(Less),
131 (Equal, Greater) | (Greater, Equal) | (Greater, Greater) => Some(Greater),
132 (Less, Greater) | (Greater, Less) => None,
133 }
134 })
135 }
136}
137
138impl PartialEq for VersionVector {
139 fn eq(&self, other: &Self) -> bool {
140 self.partial_cmp(other) == Some(Ordering::Equal)
141 }
142}
143
144impl Eq for VersionVector {}
145
146impl FromIterator<(PublicKey, u64)> for VersionVector {
147 fn from_iter<T>(iter: T) -> Self
148 where
149 T: IntoIterator<Item = (PublicKey, u64)>,
150 {
151 iter.into_iter()
152 .fold(Self::new(), |mut vv, (key, version)| {
153 vv.insert(key, version);
154 vv
155 })
156 }
157}
158
159impl Add for &'_ VersionVector {
160 type Output = VersionVector;
161
162 fn add(self, other: Self) -> Self::Output {
163 let mut output = self.clone();
164 output += other;
165 output
166 }
167}
168
169impl<'a> AddAssign<&'a VersionVector> for VersionVector {
170 fn add_assign(&mut self, rhs: &'a VersionVector) {
171 for (id, version) in &rhs.0 {
172 *self.0.entry(*id).or_default() += version;
173 }
174 }
175}
176
177impl AddAssign for VersionVector {
178 fn add_assign(&mut self, rhs: VersionVector) {
179 *self += &rhs
180 }
181}
182
183impl<'a> Sum<&'a VersionVector> for VersionVector {
184 fn sum<I>(iter: I) -> Self
185 where
186 I: Iterator<Item = &'a VersionVector>,
187 {
188 iter.fold(Self::new(), |mut sum, v| {
189 sum += v;
190 sum
191 })
192 }
193}
194
195impl Type<Sqlite> for VersionVector {
198 fn type_info() -> SqliteTypeInfo {
199 <Vec<u8> as Type<Sqlite>>::type_info()
200 }
201}
202
203impl<'q> Encode<'q, Sqlite> for VersionVector {
204 fn encode_by_ref(
205 &self,
206 args: &mut Vec<SqliteArgumentValue<'q>>,
207 ) -> Result<IsNull, BoxDynError> {
208 Encode::<Sqlite>::encode_by_ref(
209 &bincode::serialize(self).expect("failed to serialize VersionVector for db"),
210 args,
211 )
212 }
213}
214
215impl<'r> Decode<'r, Sqlite> for VersionVector {
216 fn decode(value: SqliteValueRef<'r>) -> Result<Self, BoxDynError> {
217 let slice = <&[u8] as Decode<Sqlite>>::decode(value)?;
218 Ok(bincode::deserialize(slice)?)
219 }
220}
221
222impl Hashable for VersionVector {
223 fn update_hash<S: Digest>(&self, state: &mut S) {
224 self.0.update_hash(state)
225 }
226}
227
228#[cfg(test)]
229mod tests {
230 use super::*;
231
232 #[test]
233 fn eq() {
234 let id0 = PublicKey::random();
235 let id1 = PublicKey::random();
236
237 assert_eq!(vv![], vv![]);
238 assert_eq!(vv![id0 => 0], vv![id0 => 0]);
239 assert_eq!(vv![id0 => 1], vv![id0 => 1]);
240 assert_eq!(vv![id0 => 0, id1 => 1], vv![id0 => 0, id1 => 1]);
241 assert_eq!(vv![id0 => 0, id1 => 1], vv![id1 => 1]);
242 }
243
244 #[test]
245 fn cmp_equal() {
246 let id0 = PublicKey::random();
247 let id1 = PublicKey::random();
248
249 assert_eq!(vv![].partial_cmp(&vv![]), Some(Ordering::Equal));
250 assert_eq!(
251 vv![id0 => 0].partial_cmp(&vv![id0 => 0]),
252 Some(Ordering::Equal)
253 );
254 assert_eq!(
255 vv![id0 => 1].partial_cmp(&vv![id0 => 1]),
256 Some(Ordering::Equal)
257 );
258 assert_eq!(
259 vv![id0 => 0, id1 => 1].partial_cmp(&vv![id0 => 0, id1 => 1]),
260 Some(Ordering::Equal)
261 );
262 assert_eq!(
263 vv![id0 => 0, id1 => 1].partial_cmp(&vv![id1 => 1]),
264 Some(Ordering::Equal)
265 );
266 }
267
268 #[test]
269 fn cmp_less() {
270 let id0 = PublicKey::random();
271 let id1 = PublicKey::random();
272
273 assert_eq!(vv![].partial_cmp(&vv![id0 => 1]), Some(Ordering::Less));
274
275 assert_eq!(
276 vv![id0 => 0].partial_cmp(&vv![id0 => 1]),
277 Some(Ordering::Less)
278 );
279
280 assert_eq!(
281 vv![id0 => 0].partial_cmp(&vv![id0 => 1, id1 => 1]),
282 Some(Ordering::Less)
283 );
284
285 assert_eq!(
286 vv![id0 => 0, id1 => 0].partial_cmp(&vv![id0 => 1, id1 => 1]),
287 Some(Ordering::Less)
288 );
289
290 assert_eq!(
291 vv![id0 => 0, id1 => 0].partial_cmp(&vv![id0 => 0, id1 => 1]),
292 Some(Ordering::Less)
293 );
294 }
295
296 #[test]
297 fn cmp_greater() {
298 let id0 = PublicKey::random();
299 let id1 = PublicKey::random();
300
301 assert_eq!(vv![id0 => 1].partial_cmp(&vv![]), Some(Ordering::Greater));
302
303 assert_eq!(
304 vv![id0 => 1].partial_cmp(&vv![id0 => 0]),
305 Some(Ordering::Greater)
306 );
307
308 assert_eq!(
309 vv![
310 id0 => 1, id1 => 1]
311 .partial_cmp(&vv![id0 => 0]),
312 Some(Ordering::Greater)
313 );
314
315 assert_eq!(
316 vv![id0 => 1, id1 => 1].partial_cmp(&vv![id0 => 0, id1 => 0]),
317 Some(Ordering::Greater)
318 );
319
320 assert_eq!(
321 vv![id0 => 1, id1 => 1].partial_cmp(&vv![id0 => 1, id1 => 0]),
322 Some(Ordering::Greater)
323 );
324 }
325
326 #[test]
327 fn cmp_concurrent() {
328 let id0 = PublicKey::random();
329 let id1 = PublicKey::random();
330
331 assert_eq!(
332 vv![id0 => 0, id1 => 1].partial_cmp(&vv![id0 => 1, id1 => 0]),
333 None
334 );
335
336 assert_eq!(vv![id1 => 1].partial_cmp(&vv![id0 => 1]), None);
337 }
338
339 #[test]
340 fn insert() {
341 let id = PublicKey::random();
342
343 let mut vv = vv![];
344 assert_eq!(vv.get(&id), 0);
345
346 vv.insert(id, 1);
347 assert_eq!(vv.get(&id), 1);
348
349 vv.insert(id, 2);
350 assert_eq!(vv.get(&id), 2);
351
352 vv.insert(id, 1);
353 assert_eq!(vv.get(&id), 2);
354 }
355
356 #[test]
357 fn increment_in_place() {
358 let id = PublicKey::random();
359
360 let mut vv = vv![];
361 assert_eq!(vv.get(&id), 0);
362
363 vv.increment(id);
364 assert_eq!(vv.get(&id), 1);
365 }
366
367 #[test]
368 fn merge() {
369 let id0 = PublicKey::random();
370 let id1 = PublicKey::random();
371
372 let mut vv = vv![];
373 vv.merge(&vv![]);
374 assert_eq!(vv, vv![]);
375
376 let mut vv = vv![];
377 vv.merge(&vv![id0 => 1]);
378 assert_eq!(vv, vv![id0 => 1]);
379
380 let mut vv = vv![id0 => 1];
381 vv.merge(&vv![]);
382 assert_eq!(vv, vv![id0 => 1]);
383
384 let mut vv = vv![id0 => 1];
385 vv.merge(&vv![id0 => 2]);
386 assert_eq!(vv, vv![id0 => 2]);
387
388 let mut vv = vv![id0 => 2];
389 vv.merge(&vv![id0 => 1]);
390 assert_eq!(vv, vv![id0 => 2]);
391
392 let mut vv = vv![id0 => 1];
393 vv.merge(&vv![id1 => 2]);
394 assert_eq!(vv, vv![id0 => 1, id1 => 2]);
395
396 let mut vv = vv![id0 => 1, id1 => 2];
397 vv.merge(&vv![id0 => 2, id1 => 1]);
398 assert_eq!(vv, vv![id0 => 2, id1 => 2]);
399 }
400
401 #[test]
402 fn add() {
403 let id0 = PublicKey::random();
404 let id1 = PublicKey::random();
405
406 let mut vv = vv![];
407 vv += vv![];
408 assert_eq!(vv, vv![]);
409
410 let mut vv = vv![id0 => 1];
411 vv += vv![id1 => 1];
412 assert_eq!(vv, vv![id0 =>1, id1 => 1]);
413
414 let mut vv = vv![id0 => 1, id1 => 2];
415 vv += vv![id0 => 3];
416 assert_eq!(vv, vv![id0 => 4, id1 => 2]);
417
418 let mut vv = vv![id0 => 3];
419 vv += vv![id0 => 1, id1 => 2];
420 assert_eq!(vv, vv![id0 => 4, id1 => 2]);
421 }
422
423 #[test]
424 fn saturating_sub() {
425 let id0 = PublicKey::random();
426
427 assert_eq!(vv![].saturating_sub(&vv![]), vv![]);
428 assert_eq!(vv![id0 => 1].saturating_sub(&vv![id0 => 1]), vv![]);
429 assert_eq!(vv![id0 => 2].saturating_sub(&vv![id0 => 1]), vv![id0 => 1]);
430 assert_eq!(vv![].saturating_sub(&vv![id0 => 1]), vv![]);
431 assert_eq!(vv![id0 => 1].saturating_sub(&vv![id0 => 2]), vv![]);
432 }
433}