like_a_clockwork/
causality.rs

1use serde::{Deserialize, Serialize};
2use std::collections::HashSet;
3use std::fmt;
4
5use crate::vector::VectorTimestamp;
6
7#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
8pub enum CausalityRelation {
9    /// a → b — event A caused event B
10    HappensBefore,
11    /// b → a — event B caused event A
12    HappensAfter,
13    /// a ∥ b — events are concurrent
14    Concurrent,
15    /// a = b — same causal state
16    Equal,
17}
18
19impl CausalityRelation {
20    pub fn inverse(&self) -> Self {
21        match self {
22            Self::HappensBefore => Self::HappensAfter,
23            Self::HappensAfter => Self::HappensBefore,
24            Self::Concurrent => Self::Concurrent,
25            Self::Equal => Self::Equal,
26        }
27    }
28
29    pub fn is_causal(&self) -> bool {
30        matches!(self, Self::HappensBefore | Self::HappensAfter)
31    }
32
33    pub fn is_concurrent(&self) -> bool {
34        matches!(self, Self::Concurrent)
35    }
36}
37
38impl fmt::Display for CausalityRelation {
39    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
40        match self {
41            Self::HappensBefore => write!(f, "→"),
42            Self::HappensAfter => write!(f, "←"),
43            Self::Concurrent => write!(f, "∥"),
44            Self::Equal => write!(f, "="),
45        }
46    }
47}
48
49pub fn compare(a: &VectorTimestamp, b: &VectorTimestamp) -> CausalityRelation {
50    let keys: HashSet<&String> = a.clocks().keys().chain(b.clocks().keys()).collect();
51
52    let mut a_leq_b = true;
53    let mut b_leq_a = true;
54
55    for key in &keys {
56        let va = a.get(key);
57        let vb = b.get(key);
58        if va > vb {
59            a_leq_b = false;
60        }
61        if vb > va {
62            b_leq_a = false;
63        }
64    }
65
66    match (a_leq_b, b_leq_a) {
67        (true, true) => CausalityRelation::Equal,
68        (true, false) => CausalityRelation::HappensBefore,
69        (false, true) => CausalityRelation::HappensAfter,
70        (false, false) => CausalityRelation::Concurrent,
71    }
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn inverse_happens_before_returns_happens_after() {
80        assert_eq!(CausalityRelation::HappensBefore.inverse(), CausalityRelation::HappensAfter);
81    }
82
83    #[test]
84    fn inverse_happens_after_returns_happens_before() {
85        assert_eq!(CausalityRelation::HappensAfter.inverse(), CausalityRelation::HappensBefore);
86    }
87
88    #[test]
89    fn inverse_concurrent_returns_concurrent() {
90        assert_eq!(CausalityRelation::Concurrent.inverse(), CausalityRelation::Concurrent);
91    }
92
93    #[test]
94    fn inverse_equal_returns_equal() {
95        assert_eq!(CausalityRelation::Equal.inverse(), CausalityRelation::Equal);
96    }
97
98    #[test]
99    fn double_inverse_is_identity() {
100        for variant in [
101            CausalityRelation::HappensBefore,
102            CausalityRelation::HappensAfter,
103            CausalityRelation::Concurrent,
104            CausalityRelation::Equal,
105        ] {
106            assert_eq!(variant.inverse().inverse(), variant);
107        }
108    }
109
110    #[test]
111    fn is_causal_true_for_happens_before() {
112        assert!(CausalityRelation::HappensBefore.is_causal());
113    }
114
115    #[test]
116    fn is_causal_true_for_happens_after() {
117        assert!(CausalityRelation::HappensAfter.is_causal());
118    }
119
120    #[test]
121    fn is_causal_false_for_concurrent() {
122        assert!(!CausalityRelation::Concurrent.is_causal());
123    }
124
125    #[test]
126    fn is_causal_false_for_equal() {
127        assert!(!CausalityRelation::Equal.is_causal());
128    }
129
130    #[test]
131    fn is_concurrent_true_for_concurrent() {
132        assert!(CausalityRelation::Concurrent.is_concurrent());
133    }
134
135    #[test]
136    fn is_concurrent_false_for_others() {
137        assert!(!CausalityRelation::HappensBefore.is_concurrent());
138        assert!(!CausalityRelation::HappensAfter.is_concurrent());
139        assert!(!CausalityRelation::Equal.is_concurrent());
140    }
141
142    #[test]
143    fn display_happens_before() {
144        assert_eq!(format!("{}", CausalityRelation::HappensBefore), "→");
145    }
146
147    #[test]
148    fn display_happens_after() {
149        assert_eq!(format!("{}", CausalityRelation::HappensAfter), "←");
150    }
151
152    #[test]
153    fn display_concurrent() {
154        assert_eq!(format!("{}", CausalityRelation::Concurrent), "∥");
155    }
156
157    #[test]
158    fn display_equal() {
159        assert_eq!(format!("{}", CausalityRelation::Equal), "=");
160    }
161
162    #[test]
163    fn serde_json_roundtrip_all_variants() {
164        for variant in [
165            CausalityRelation::HappensBefore,
166            CausalityRelation::HappensAfter,
167            CausalityRelation::Concurrent,
168            CausalityRelation::Equal,
169        ] {
170            let json = serde_json::to_string(&variant).unwrap();
171            let deserialized: CausalityRelation = serde_json::from_str(&json).unwrap();
172            assert_eq!(variant, deserialized);
173        }
174    }
175
176    #[test]
177    fn compare_equal_vectors() {
178        use std::collections::HashMap;
179        let mut m = HashMap::new();
180        m.insert("a".to_string(), 1u64);
181        m.insert("b".to_string(), 2u64);
182        let ts_a = VectorTimestamp::from(m.clone());
183        let ts_b = VectorTimestamp::from(m);
184        assert_eq!(compare(&ts_a, &ts_b), CausalityRelation::Equal);
185    }
186
187    #[test]
188    fn compare_strictly_less() {
189        use std::collections::HashMap;
190        let mut ma = HashMap::new();
191        ma.insert("a".to_string(), 1u64);
192        ma.insert("b".to_string(), 1u64);
193        let mut mb = HashMap::new();
194        mb.insert("a".to_string(), 2u64);
195        mb.insert("b".to_string(), 2u64);
196        let ts_a = VectorTimestamp::from(ma);
197        let ts_b = VectorTimestamp::from(mb);
198        assert_eq!(compare(&ts_a, &ts_b), CausalityRelation::HappensBefore);
199    }
200
201    #[test]
202    fn compare_less_or_equal_with_one_strict() {
203        use std::collections::HashMap;
204        let mut ma = HashMap::new();
205        ma.insert("a".to_string(), 1u64);
206        ma.insert("b".to_string(), 2u64);
207        let mut mb = HashMap::new();
208        mb.insert("a".to_string(), 2u64);
209        mb.insert("b".to_string(), 2u64);
210        let ts_a = VectorTimestamp::from(ma);
211        let ts_b = VectorTimestamp::from(mb);
212        assert_eq!(compare(&ts_a, &ts_b), CausalityRelation::HappensBefore);
213    }
214
215    #[test]
216    fn compare_strictly_greater() {
217        use std::collections::HashMap;
218        let mut ma = HashMap::new();
219        ma.insert("a".to_string(), 3u64);
220        ma.insert("b".to_string(), 3u64);
221        let mut mb = HashMap::new();
222        mb.insert("a".to_string(), 1u64);
223        mb.insert("b".to_string(), 1u64);
224        let ts_a = VectorTimestamp::from(ma);
225        let ts_b = VectorTimestamp::from(mb);
226        assert_eq!(compare(&ts_a, &ts_b), CausalityRelation::HappensAfter);
227    }
228
229    #[test]
230    fn compare_concurrent() {
231        use std::collections::HashMap;
232        let mut ma = HashMap::new();
233        ma.insert("a".to_string(), 2u64);
234        ma.insert("b".to_string(), 1u64);
235        let mut mb = HashMap::new();
236        mb.insert("a".to_string(), 1u64);
237        mb.insert("b".to_string(), 2u64);
238        let ts_a = VectorTimestamp::from(ma);
239        let ts_b = VectorTimestamp::from(mb);
240        assert_eq!(compare(&ts_a, &ts_b), CausalityRelation::Concurrent);
241    }
242
243    #[test]
244    fn compare_with_different_sized_vectors() {
245        use std::collections::HashMap;
246        let mut ma = HashMap::new();
247        ma.insert("a".to_string(), 1u64);
248        let mut mb = HashMap::new();
249        mb.insert("a".to_string(), 1u64);
250        mb.insert("b".to_string(), 1u64);
251        let ts_a = VectorTimestamp::from(ma);
252        let ts_b = VectorTimestamp::from(mb);
253        // a has a=1, b=0(missing); b has a=1, b=1 → a <= b, so HappensBefore
254        assert_eq!(compare(&ts_a, &ts_b), CausalityRelation::HappensBefore);
255    }
256
257    #[test]
258    fn compare_inverse_symmetry() {
259        use std::collections::HashMap;
260        let mut ma = HashMap::new();
261        ma.insert("a".to_string(), 1u64);
262        ma.insert("b".to_string(), 0u64);
263        let mut mb = HashMap::new();
264        mb.insert("a".to_string(), 0u64);
265        mb.insert("b".to_string(), 1u64);
266        let ts_a = VectorTimestamp::from(ma);
267        let ts_b = VectorTimestamp::from(mb);
268        assert_eq!(compare(&ts_a, &ts_b), compare(&ts_b, &ts_a).inverse());
269    }
270}
like_a_clockwork/causality.rs

like_a_clockwork/
causality.rs
