sapphire_framework_sync/
vv.rs

1//! Dots and version vectors.
2
3use std::collections::BTreeMap;
4
5use serde::{Deserialize, Serialize};
6
7use crate::id::ReplicaId;
8
9/// One event: the `counter`-th write recorded by `replica`.
10#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, Serialize, Deserialize)]
11pub struct Dot {
12    pub replica: ReplicaId,
13    pub counter: u64,
14}
15
16/// For each replica, the highest counter covered.
17#[derive(Clone, Debug, Default, PartialEq, Eq, Serialize, Deserialize)]
18pub struct VersionVector(pub BTreeMap<ReplicaId, u64>);
19
20impl VersionVector {
21    pub fn new() -> Self {
22        Self::default()
23    }
24
25    pub fn get(&self, replica: &ReplicaId) -> u64 {
26        self.0.get(replica).copied().unwrap_or(0)
27    }
28
29    pub fn covers_dot(&self, dot: &Dot) -> bool {
30        self.get(&dot.replica) >= dot.counter
31    }
32
33    pub fn covers(&self, other: &VersionVector) -> bool {
34        other.0.iter().all(|(r, c)| self.get(r) >= *c)
35    }
36
37    pub fn add_dot(&mut self, dot: &Dot) {
38        let slot = self.0.entry(dot.replica).or_insert(0);
39        *slot = (*slot).max(dot.counter);
40    }
41
42    pub fn merge(&mut self, other: &VersionVector) {
43        for (r, c) in &other.0 {
44            let slot = self.0.entry(*r).or_insert(0);
45            *slot = (*slot).max(*c);
46        }
47    }
48}
49
50#[cfg(test)]
51mod tests {
52    use super::*;
53    use uuid::Uuid;
54
55    fn r(n: u128) -> ReplicaId {
56        ReplicaId(Uuid::from_u128(n))
57    }
58
59    #[test]
60    fn cover_and_merge() {
61        let mut a = VersionVector::new();
62        a.add_dot(&Dot {
63            replica: r(1),
64            counter: 3,
65        });
66        let mut b = VersionVector::new();
67        b.add_dot(&Dot {
68            replica: r(2),
69            counter: 1,
70        });
71        assert!(a.covers_dot(&Dot {
72            replica: r(1),
73            counter: 2
74        }));
75        assert!(!a.covers_dot(&Dot {
76            replica: r(2),
77            counter: 1
78        }));
79        assert!(!a.covers(&b));
80        a.merge(&b);
81        assert!(a.covers(&b));
82        a.add_dot(&Dot {
83            replica: r(1),
84            counter: 1,
85        });
86        assert_eq!(a.get(&r(1)), 3, "add_dot never lowers a counter");
87    }
88
89    #[test]
90    fn serializes_as_a_json_object_keyed_by_uuid() {
91        let mut v = VersionVector::new();
92        v.add_dot(&Dot {
93            replica: r(1),
94            counter: 2,
95        });
96        let json = serde_json::to_string(&v).unwrap();
97        assert_eq!(json, r#"{"00000000-0000-0000-0000-000000000001":2}"#);
98        assert_eq!(serde_json::from_str::<VersionVector>(&json).unwrap(), v);
99    }
100}
sapphire_framework_sync/vv.rs

sapphire_framework_sync/
vv.rs
