1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
use std::{
cmp::Ordering,
collections::{HashMap, HashSet},
};
use uuid::Uuid;
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct VectorClock(HashMap<Uuid, u64>);
impl VectorClock {
pub fn new() -> Self {
Self(HashMap::new())
}
pub fn get(&self, actor_id: &Uuid) -> u64 {
self.0.get(actor_id).unwrap_or(&0).clone()
}
pub fn inc(&self, actor_id: &Uuid) -> Self {
let mut m = self.0.clone();
m.insert(actor_id.clone(), self.get(actor_id) + 1);
VectorClock(m)
}
/// Returns true if this clock is concurrent with another (neither happens before the other)
pub fn is_concurrent_with(&self, other: &VectorClock) -> bool {
self.partial_cmp(other).is_none()
}
}
impl PartialOrd for VectorClock {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
let orderings: HashSet<_> = self
.0
.keys()
.chain(other.0.keys())
.collect::<HashSet<_>>()
.into_iter()
.map(|actor_id| self.get(actor_id).cmp(&other.get(actor_id)))
.collect();
let less = orderings.contains(&Ordering::Less);
let greater = orderings.contains(&Ordering::Greater);
match (less, greater) {
(true, true) => None,
(true, false) => Some(Ordering::Less),
(false, true) => Some(Ordering::Greater),
(false, false) => Some(Ordering::Equal),
}
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn vector_clock_compare() {
let alice_id = Uuid::now_v7();
let bob_id = Uuid::now_v7();
let carol_id = Uuid::now_v7();
assert!(alice_id < bob_id);
assert!(bob_id < carol_id);
let mut alice = VectorClock::new();
let mut bob = VectorClock::new();
assert!(alice == bob);
assert!(bob == alice);
bob = bob.inc(&bob_id);
assert!(alice < bob);
assert!(bob > alice);
alice = alice.inc(&alice_id);
assert!(!(alice < bob));
assert!(!(alice > bob));
alice = alice.inc(&bob_id);
bob = bob.inc(&alice_id);
assert!(alice == bob);
alice = alice.inc(&alice_id);
assert!(alice > bob);
assert!(bob < alice);
bob = bob.inc(&alice_id);
assert!(alice == bob);
alice = alice.inc(&carol_id);
assert!(alice > bob);
assert!(bob < alice);
bob = bob.inc(&bob_id);
assert!(!(alice > bob));
assert!(!(alice < bob));
let clock_a = VectorClock::new().inc(&alice_id).inc(&carol_id);
let clock_b = VectorClock::new().inc(&bob_id).inc(&carol_id);
assert!(!(clock_a > clock_b));
assert!(!(clock_a < clock_b));
}
#[test]
fn concurrent_clocks() {
let alice_id = Uuid::now_v7();
let bob_id = Uuid::now_v7();
let carol_id = Uuid::now_v7();
// Equal clocks are not concurrent
let clock1 = VectorClock::new();
let clock2 = VectorClock::new();
assert!(!clock1.is_concurrent_with(&clock2));
// Causally ordered clocks are not concurrent
let clock_before = VectorClock::new().inc(&alice_id);
let clock_after = VectorClock::new().inc(&alice_id).inc(&bob_id);
assert!(!clock_before.is_concurrent_with(&clock_after));
assert!(!clock_after.is_concurrent_with(&clock_before));
// Clocks from different actors are concurrent
let alice_clock = VectorClock::new().inc(&alice_id);
let bob_clock = VectorClock::new().inc(&bob_id);
assert!(alice_clock.is_concurrent_with(&bob_clock));
assert!(bob_clock.is_concurrent_with(&alice_clock));
// Complex concurrent case: diverged branches
let clock_a = VectorClock::new()
.inc(&alice_id)
.inc(&alice_id)
.inc(&bob_id)
.inc(&carol_id);
let clock_b = VectorClock::new()
.inc(&alice_id)
.inc(&alice_id)
.inc(&bob_id)
.inc(&bob_id);
// clock_a: {alice: 2, bob: 1, carol: 1}
// clock_b: {alice: 2, bob: 2}
// carol: 1 > 0, but bob: 1 < 2 → concurrent
assert!(clock_a.is_concurrent_with(&clock_b));
}
}
|
