uni_crdt/
vector_clock.rs

1// SPDX-License-Identifier: Apache-2.0
2// Copyright 2024-2026 Dragonscale Team
3
4use crate::CrdtMerge;
5use fxhash::FxHashMap;
6use serde::{Deserialize, Serialize};
7use std::cmp::Ordering;
8
9/// Vector clock for causal ordering in distributed systems.
10///
11/// Maps actor IDs to logical counters.
12#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, Default)]
13pub struct VectorClock {
14    pub clocks: FxHashMap<String, u64>,
15}
16
17impl VectorClock {
18    pub fn new() -> Self {
19        Self::default()
20    }
21
22    /// Increment the clock for an actor.
23    pub fn increment(&mut self, actor: &str) {
24        *self.clocks.entry(actor.to_string()).or_insert(0) += 1;
25    }
26
27    /// Get the clock value for an actor.
28    pub fn get(&self, actor: &str) -> u64 {
29        *self.clocks.get(actor).unwrap_or(&0)
30    }
31
32    /// Merge another vector clock into this one (point-wise maximum).
33    pub fn merge_clock(&mut self, other: &VectorClock) {
34        for (actor, &count) in &other.clocks {
35            let entry = self.clocks.entry(actor.clone()).or_insert(0);
36            *entry = std::cmp::max(*entry, count);
37        }
38    }
39
40    /// Returns true if self causally happened before other.
41    /// A < B iff for all k: A\[k\] <= B\[k\] AND exists k: A\[k\] < B\[k\].
42    pub fn happened_before(&self, other: &VectorClock) -> bool {
43        let mut strictly_less = false;
44
45        // Check if all our entries are <= other's
46        for (actor, &count) in &self.clocks {
47            let other_count = other.get(actor);
48            if count > other_count {
49                return false;
50            }
51            if count < other_count {
52                strictly_less = true;
53            }
54        }
55
56        // Also check if other has keys we don't (implicitly our 0 < their count)
57        if !strictly_less {
58            for (actor, &count) in &other.clocks {
59                if !self.clocks.contains_key(actor) && count > 0 {
60                    strictly_less = true;
61                    break;
62                }
63            }
64        }
65
66        strictly_less
67    }
68
69    /// Returns true if neither clock happened before the other (concurrent).
70    pub fn is_concurrent(&self, other: &VectorClock) -> bool {
71        !self.happened_before(other) && !other.happened_before(self) && self != other
72    }
73
74    /// Compare two clocks for causal ordering.
75    ///
76    /// Returns `Less`/`Greater` when one clock causally happened before the
77    /// other, `Equal` when they match, and `None` when they are concurrent.
78    /// Named `causal_cmp` rather than implementing `PartialOrd` to keep the
79    /// concurrent-as-`None` semantics explicit at call sites.
80    pub fn causal_cmp(&self, other: &VectorClock) -> Option<Ordering> {
81        if self == other {
82            Some(Ordering::Equal)
83        } else if self.happened_before(other) {
84            Some(Ordering::Less)
85        } else if other.happened_before(self) {
86            Some(Ordering::Greater)
87        } else {
88            None // Concurrent
89        }
90    }
91}
92
93impl CrdtMerge for VectorClock {
94    fn merge(&mut self, other: &Self) {
95        self.merge_clock(other);
96    }
97}
98
99#[cfg(test)]
100mod tests {
101    use super::*;
102
103    #[test]
104    fn test_vector_clock_ordering() {
105        let mut a = VectorClock::new();
106        a.increment("node1"); // {node1: 1}
107
108        let mut b = a.clone();
109        b.increment("node1"); // {node1: 2}
110
111        // a < b
112        assert!(a.happened_before(&b));
113        assert!(!b.happened_before(&a));
114        assert_eq!(a.causal_cmp(&b), Some(Ordering::Less));
115
116        let mut c = a.clone();
117        c.increment("node2"); // {node1: 1, node2: 1}
118
119        // b {node1: 2} vs c {node1: 1, node2: 1} -> Concurrent
120        // b has node1: 2 > 1
121        // c has node2: 1 > 0
122        assert!(!b.happened_before(&c));
123        assert!(!c.happened_before(&b));
124        assert!(b.is_concurrent(&c));
125        assert_eq!(b.causal_cmp(&c), None);
126    }
127
128    #[test]
129    fn test_merge() {
130        let mut a = VectorClock::new();
131        a.increment("node1"); // {node1: 1}
132
133        let mut b = VectorClock::new();
134        b.increment("node2"); // {node2: 1}
135
136        a.merge(&b); // {node1: 1, node2: 1}
137        assert_eq!(a.get("node1"), 1);
138        assert_eq!(a.get("node2"), 1);
139    }
140}
uni_crdt/vector_clock.rs

uni_crdt/
vector_clock.rs
