logicaffeine_data/crdt/causal/
vclock.rs

1//! Vector Clock for causal ordering.
2//!
3//! VClock tracks causality between distributed events.
4
5use super::super::replica::ReplicaId;
6use super::super::Merge;
7use serde::{Deserialize, Serialize};
8use std::collections::HashMap;
9
10/// A vector clock for tracking causal relationships between events.
11///
12/// Each replica has a logical clock counter. The vector clock captures
13/// which events have been "seen" by tracking the maximum counter for each replica.
14#[derive(Debug, Clone, Default, Serialize, Deserialize, PartialEq, Eq)]
15pub struct VClock {
16    entries: HashMap<ReplicaId, u64>,
17}
18
19impl VClock {
20    /// Create a new empty vector clock.
21    pub fn new() -> Self {
22        Self::default()
23    }
24
25    /// Increment the clock for a replica and return the new counter value.
26    pub fn increment(&mut self, replica: ReplicaId) -> u64 {
27        let entry = self.entries.entry(replica).or_insert(0);
28        *entry += 1;
29        *entry
30    }
31
32    /// Get the current counter for a replica (0 if not seen).
33    pub fn get(&self, replica: ReplicaId) -> u64 {
34        *self.entries.get(&replica).unwrap_or(&0)
35    }
36
37    /// Check if self dominates other (self >= other for all replicas).
38    ///
39    /// Returns true if for every replica in `other`, self has an equal or greater counter.
40    pub fn dominates(&self, other: &Self) -> bool {
41        for (&replica, &count) in &other.entries {
42            if self.get(replica) < count {
43                return false;
44            }
45        }
46        true
47    }
48
49    /// Check if self and other are concurrent (neither dominates the other).
50    pub fn concurrent(&self, other: &Self) -> bool {
51        !self.dominates(other) && !other.dominates(self)
52    }
53
54    /// Merge another vector clock into this one (pointwise max).
55    pub fn merge_vclock(&mut self, other: &Self) {
56        for (&replica, &count) in &other.entries {
57            let entry = self.entries.entry(replica).or_insert(0);
58            *entry = (*entry).max(count);
59        }
60    }
61
62    /// Get all replicas in this clock.
63    pub fn replicas(&self) -> impl Iterator<Item = &ReplicaId> {
64        self.entries.keys()
65    }
66}
67
68impl Merge for VClock {
69    fn merge(&mut self, other: &Self) {
70        self.merge_vclock(other);
71    }
72}
73
74#[cfg(test)]
75mod tests {
76    use super::*;
77
78    #[test]
79    fn test_vclock_new() {
80        let clock = VClock::new();
81        assert_eq!(clock.get(42), 0);
82    }
83
84    #[test]
85    fn test_vclock_increment() {
86        let mut clock = VClock::new();
87        assert_eq!(clock.increment(42), 1);
88        assert_eq!(clock.increment(42), 2);
89        assert_eq!(clock.get(42), 2);
90    }
91
92    #[test]
93    fn test_vclock_merge() {
94        let mut a = VClock::new();
95        let mut b = VClock::new();
96
97        a.increment(1);
98        a.increment(1);
99        b.increment(2);
100
101        a.merge(&b);
102
103        assert_eq!(a.get(1), 2);
104        assert_eq!(a.get(2), 1);
105    }
106
107    #[test]
108    fn test_vclock_dominates() {
109        let mut a = VClock::new();
110        let mut b = VClock::new();
111
112        a.increment(1);
113        a.increment(1);
114        b.increment(1);
115
116        assert!(a.dominates(&b));
117        assert!(!b.dominates(&a));
118    }
119
120    #[test]
121    fn test_vclock_concurrent() {
122        let mut a = VClock::new();
123        let mut b = VClock::new();
124
125        a.increment(1);
126        b.increment(2);
127
128        assert!(a.concurrent(&b));
129    }
130}
logicaffeine_data/crdt/causal/vclock.rs

logicaffeine_data/crdt/causal/
vclock.rs
