ouisync/
version_vector.rs

1use crate::crypto::{sign::PublicKey, Digest, Hashable};
2use serde::{Deserialize, Serialize};
3use sqlx::{
4    encode::IsNull,
5    error::BoxDynError,
6    sqlite::{SqliteArgumentValue, SqliteTypeInfo, SqliteValueRef},
7    Decode, Encode, Sqlite, Type,
8};
9use std::{
10    cmp::Ordering,
11    collections::BTreeMap,
12    fmt,
13    iter::Sum,
14    ops::{Add, AddAssign},
15};
16
17/// [Version vector](https://en.wikipedia.org/wiki/Version_vector).
18///
19/// The `PartialOrd` impl provides the "happened-before" relation like follows:
20///
21/// - `Some(Ordering::Equal)`   -> the vectors are exactly equal
22/// - `Some(Ordering::Less)`    -> the lhs vector happened-before the rhs vector
23/// - `Some(Ordering::Greater)` -> the rhs vector happened-before the lhs vector
24/// - `None`                    -> the version vectors are concurrent
25#[derive(Default, Clone, Serialize, Deserialize)]
26pub struct VersionVector(BTreeMap<PublicKey, u64>);
27
28impl VersionVector {
29    /// Creates an empty version vector.
30    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    /// Inserts an entry into this version vector. If the entry already exists, it's overwritten
41    /// only if the new version is higher than the existing version. This operation is idempotent.
42    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    /// Retrieves the version corresponding to the given replica id.
48    pub fn get(&self, writer_id: &PublicKey) -> u64 {
49        self.0.get(writer_id).copied().unwrap_or(0)
50    }
51
52    /// Increments the version corresponding to the given replica id.
53    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    /// Returns `self` with the version corresponding to `writer_id` incremented.
59    pub fn incremented(mut self, writer_id: PublicKey) -> Self {
60        self.increment(writer_id);
61        self
62    }
63
64    /// Merge two version vectors into one. The version of each entry in the resulting vector is
65    /// the maximum of the corresponding entries of the input vectors.
66    ///
67    /// This operation is commutative, associative and idempotent.
68    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    /// Returns `self` merged with `other`.
75    pub fn merged(mut self, other: &Self) -> Self {
76        self.merge(other);
77        self
78    }
79
80    /// Saturating subtraction.
81    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
93// Less clutter in the debug output this way (as opposed to deriving).
94// e.g.:
95//   with deriving: Foo { version_vector: VersionVector({...}) }
96//   without:       Foo { version_vector: {...} }
97impl fmt::Debug for VersionVector {
98    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
99        write!(f, "{:?}", self.0)
100    }
101}
102
103impl PartialOrd for VersionVector {
104    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
105        use Ordering::*;
106
107        self.0
108            .iter()
109            .map(|(lhs_key, &lhs_version)| (lhs_version, other.get(lhs_key)))
110            .chain(
111                other
112                    .0
113                    .iter()
114                    .filter(|(rhs_key, _)| !self.0.contains_key(rhs_key))
115                    .map(|(_, &rhs_version)| (0, rhs_version)),
116            )
117            .try_fold(Equal, |ordering, (lhs_version, rhs_version)| {
118                match (ordering, lhs_version.cmp(&rhs_version)) {
119                    (Equal, Equal) => Some(Equal),
120                    (Equal, Less) | (Less, Equal) | (Less, Less) => Some(Less),
121                    (Equal, Greater) | (Greater, Equal) | (Greater, Greater) => Some(Greater),
122                    (Less, Greater) | (Greater, Less) => None,
123                }
124            })
125    }
126}
127
128impl PartialEq for VersionVector {
129    fn eq(&self, other: &Self) -> bool {
130        self.partial_cmp(other) == Some(Ordering::Equal)
131    }
132}
133
134impl Eq for VersionVector {}
135
136impl FromIterator<(PublicKey, u64)> for VersionVector {
137    fn from_iter<T>(iter: T) -> Self
138    where
139        T: IntoIterator<Item = (PublicKey, u64)>,
140    {
141        iter.into_iter()
142            .fold(Self::new(), |mut vv, (key, version)| {
143                vv.insert(key, version);
144                vv
145            })
146    }
147}
148
149impl Add for &'_ VersionVector {
150    type Output = VersionVector;
151
152    fn add(self, other: Self) -> Self::Output {
153        let mut output = self.clone();
154        output += other;
155        output
156    }
157}
158
159impl<'a> AddAssign<&'a VersionVector> for VersionVector {
160    fn add_assign(&mut self, rhs: &'a VersionVector) {
161        for (id, version) in &rhs.0 {
162            *self.0.entry(*id).or_default() += version;
163        }
164    }
165}
166
167impl AddAssign for VersionVector {
168    fn add_assign(&mut self, rhs: VersionVector) {
169        *self += &rhs
170    }
171}
172
173impl<'a> Sum<&'a VersionVector> for VersionVector {
174    fn sum<I>(iter: I) -> Self
175    where
176        I: Iterator<Item = &'a VersionVector>,
177    {
178        iter.fold(Self::new(), |mut sum, v| {
179            sum += v;
180            sum
181        })
182    }
183}
184
185// Support reading/writing `VersionVector` directly from/to the db:
186
187impl Type<Sqlite> for VersionVector {
188    fn type_info() -> SqliteTypeInfo {
189        <Vec<u8> as Type<Sqlite>>::type_info()
190    }
191}
192
193impl<'q> Encode<'q, Sqlite> for VersionVector {
194    fn encode_by_ref(
195        &self,
196        args: &mut Vec<SqliteArgumentValue<'q>>,
197    ) -> Result<IsNull, BoxDynError> {
198        Encode::<Sqlite>::encode_by_ref(
199            &bincode::serialize(self).expect("failed to serialize VersionVector for db"),
200            args,
201        )
202    }
203}
204
205impl<'r> Decode<'r, Sqlite> for VersionVector {
206    fn decode(value: SqliteValueRef<'r>) -> Result<Self, BoxDynError> {
207        let slice = <&[u8] as Decode<Sqlite>>::decode(value)?;
208        Ok(bincode::deserialize(slice)?)
209    }
210}
211
212impl Hashable for VersionVector {
213    fn update_hash<S: Digest>(&self, state: &mut S) {
214        self.0.update_hash(state)
215    }
216}
217
218#[cfg(test)]
219mod tests {
220    use super::*;
221
222    #[test]
223    fn eq() {
224        let id0 = PublicKey::random();
225        let id1 = PublicKey::random();
226
227        assert_eq!(vv![], vv![]);
228        assert_eq!(vv![id0 => 0], vv![id0 => 0]);
229        assert_eq!(vv![id0 => 1], vv![id0 => 1]);
230        assert_eq!(vv![id0 => 0, id1 => 1], vv![id0 => 0, id1 => 1]);
231        assert_eq!(vv![id0 => 0, id1 => 1], vv![id1 => 1]);
232    }
233
234    #[test]
235    fn cmp_equal() {
236        let id0 = PublicKey::random();
237        let id1 = PublicKey::random();
238
239        assert_eq!(vv![].partial_cmp(&vv![]), Some(Ordering::Equal));
240        assert_eq!(
241            vv![id0 => 0].partial_cmp(&vv![id0 => 0]),
242            Some(Ordering::Equal)
243        );
244        assert_eq!(
245            vv![id0 => 1].partial_cmp(&vv![id0 => 1]),
246            Some(Ordering::Equal)
247        );
248        assert_eq!(
249            vv![id0 => 0, id1 => 1].partial_cmp(&vv![id0 => 0, id1 => 1]),
250            Some(Ordering::Equal)
251        );
252        assert_eq!(
253            vv![id0 => 0, id1 => 1].partial_cmp(&vv![id1 => 1]),
254            Some(Ordering::Equal)
255        );
256    }
257
258    #[test]
259    fn cmp_less() {
260        let id0 = PublicKey::random();
261        let id1 = PublicKey::random();
262
263        assert_eq!(vv![].partial_cmp(&vv![id0 => 1]), Some(Ordering::Less));
264
265        assert_eq!(
266            vv![id0 => 0].partial_cmp(&vv![id0 => 1]),
267            Some(Ordering::Less)
268        );
269
270        assert_eq!(
271            vv![id0 => 0].partial_cmp(&vv![id0 => 1, id1 => 1]),
272            Some(Ordering::Less)
273        );
274
275        assert_eq!(
276            vv![id0 => 0, id1 => 0].partial_cmp(&vv![id0 => 1, id1 => 1]),
277            Some(Ordering::Less)
278        );
279
280        assert_eq!(
281            vv![id0 => 0, id1 => 0].partial_cmp(&vv![id0 => 0, id1 => 1]),
282            Some(Ordering::Less)
283        );
284    }
285
286    #[test]
287    fn cmp_greater() {
288        let id0 = PublicKey::random();
289        let id1 = PublicKey::random();
290
291        assert_eq!(vv![id0 => 1].partial_cmp(&vv![]), Some(Ordering::Greater));
292
293        assert_eq!(
294            vv![id0 => 1].partial_cmp(&vv![id0 => 0]),
295            Some(Ordering::Greater)
296        );
297
298        assert_eq!(
299            vv![
300                id0 => 1, id1 => 1]
301            .partial_cmp(&vv![id0 => 0]),
302            Some(Ordering::Greater)
303        );
304
305        assert_eq!(
306            vv![id0 => 1, id1 => 1].partial_cmp(&vv![id0 => 0, id1 => 0]),
307            Some(Ordering::Greater)
308        );
309
310        assert_eq!(
311            vv![id0 => 1, id1 => 1].partial_cmp(&vv![id0 => 1, id1 => 0]),
312            Some(Ordering::Greater)
313        );
314    }
315
316    #[test]
317    fn cmp_concurrent() {
318        let id0 = PublicKey::random();
319        let id1 = PublicKey::random();
320
321        assert_eq!(
322            vv![id0 => 0, id1 => 1].partial_cmp(&vv![id0 => 1, id1 => 0]),
323            None
324        );
325
326        assert_eq!(vv![id1 => 1].partial_cmp(&vv![id0 => 1]), None);
327    }
328
329    #[test]
330    fn insert() {
331        let id = PublicKey::random();
332
333        let mut vv = vv![];
334        assert_eq!(vv.get(&id), 0);
335
336        vv.insert(id, 1);
337        assert_eq!(vv.get(&id), 1);
338
339        vv.insert(id, 2);
340        assert_eq!(vv.get(&id), 2);
341
342        vv.insert(id, 1);
343        assert_eq!(vv.get(&id), 2);
344    }
345
346    #[test]
347    fn increment_in_place() {
348        let id = PublicKey::random();
349
350        let mut vv = vv![];
351        assert_eq!(vv.get(&id), 0);
352
353        vv.increment(id);
354        assert_eq!(vv.get(&id), 1);
355    }
356
357    #[test]
358    fn merge() {
359        let id0 = PublicKey::random();
360        let id1 = PublicKey::random();
361
362        let mut vv = vv![];
363        vv.merge(&vv![]);
364        assert_eq!(vv, vv![]);
365
366        let mut vv = vv![];
367        vv.merge(&vv![id0 => 1]);
368        assert_eq!(vv, vv![id0 => 1]);
369
370        let mut vv = vv![id0 => 1];
371        vv.merge(&vv![]);
372        assert_eq!(vv, vv![id0 => 1]);
373
374        let mut vv = vv![id0 => 1];
375        vv.merge(&vv![id0 => 2]);
376        assert_eq!(vv, vv![id0 => 2]);
377
378        let mut vv = vv![id0 => 2];
379        vv.merge(&vv![id0 => 1]);
380        assert_eq!(vv, vv![id0 => 2]);
381
382        let mut vv = vv![id0 => 1];
383        vv.merge(&vv![id1 => 2]);
384        assert_eq!(vv, vv![id0 => 1, id1 => 2]);
385
386        let mut vv = vv![id0 => 1, id1 => 2];
387        vv.merge(&vv![id0 => 2, id1 => 1]);
388        assert_eq!(vv, vv![id0 => 2, id1 => 2]);
389    }
390
391    #[test]
392    fn add() {
393        let id0 = PublicKey::random();
394        let id1 = PublicKey::random();
395
396        let mut vv = vv![];
397        vv += vv![];
398        assert_eq!(vv, vv![]);
399
400        let mut vv = vv![id0 => 1];
401        vv += vv![id1 => 1];
402        assert_eq!(vv, vv![id0 =>1, id1 => 1]);
403
404        let mut vv = vv![id0 => 1, id1 => 2];
405        vv += vv![id0 => 3];
406        assert_eq!(vv, vv![id0 => 4, id1 => 2]);
407
408        let mut vv = vv![id0 => 3];
409        vv += vv![id0 => 1, id1 => 2];
410        assert_eq!(vv, vv![id0 => 4, id1 => 2]);
411    }
412
413    #[test]
414    fn saturating_sub() {
415        let id0 = PublicKey::random();
416
417        assert_eq!(vv![].saturating_sub(&vv![]), vv![]);
418        assert_eq!(vv![id0 => 1].saturating_sub(&vv![id0 => 1]), vv![]);
419        assert_eq!(vv![id0 => 2].saturating_sub(&vv![id0 => 1]), vv![id0 => 1]);
420        assert_eq!(vv![].saturating_sub(&vv![id0 => 1]), vv![]);
421        assert_eq!(vv![id0 => 1].saturating_sub(&vv![id0 => 2]), vv![]);
422    }
423}
ouisync/version_vector.rs

ouisync/
version_vector.rs
