Skip to main content

ouisync/
version_vector.rs

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/// [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    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
103// Less clutter in the debug output this way (as opposed to deriving).
104// e.g.:
105//   with deriving: Foo { version_vector: VersionVector({...}) }
106//   without:       Foo { version_vector: {...} }
107impl 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
195// Support reading/writing `VersionVector` directly from/to the db:
196
197impl 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}