oxihuman_core/
version_vector.rs

1// Copyright (C) 2026 COOLJAPAN OU (Team KitaSan)
2// SPDX-License-Identifier: Apache-2.0
3
4//! Vector clock for distributed state tracking.
5
6#![allow(dead_code)]
7
8use std::collections::HashMap;
9
10/// A vector clock mapping node ID to logical timestamp.
11#[allow(dead_code)]
12#[derive(Debug, Clone, PartialEq)]
13pub struct VersionVector {
14    pub clocks: HashMap<String, u64>,
15}
16
17/// Create an empty version vector.
18#[allow(dead_code)]
19pub fn new_version_vector() -> VersionVector {
20    VersionVector {
21        clocks: HashMap::new(),
22    }
23}
24
25/// Increment the clock for a given node.
26#[allow(dead_code)]
27pub fn vv_increment(vv: &mut VersionVector, node: &str) {
28    let entry = vv.clocks.entry(node.to_string()).or_insert(0);
29    *entry += 1;
30}
31
32/// Get the clock value for a node (0 if not present).
33#[allow(dead_code)]
34pub fn vv_get(vv: &VersionVector, node: &str) -> u64 {
35    *vv.clocks.get(node).unwrap_or(&0)
36}
37
38/// Merge two version vectors, taking the max of each component.
39#[allow(dead_code)]
40pub fn vv_merge(a: &VersionVector, b: &VersionVector) -> VersionVector {
41    let mut result = a.clone();
42    for (node, &val) in &b.clocks {
43        let entry = result.clocks.entry(node.clone()).or_insert(0);
44        if val > *entry {
45            *entry = val;
46        }
47    }
48    result
49}
50
51/// Check if `a` happens-before `b` (all a's components <= b's, and at least one is strictly less).
52#[allow(dead_code)]
53pub fn vv_happens_before(a: &VersionVector, b: &VersionVector) -> bool {
54    // Every component of a must be <= corresponding component in b
55    let all_le = a.clocks.iter().all(|(k, &v)| vv_get(b, k) >= v);
56    // At least one component of a must be strictly less, OR b has extra keys
57    let any_lt = a.clocks.iter().any(|(k, &v)| vv_get(b, k) > v)
58        || b.clocks.keys().any(|k| !a.clocks.contains_key(k.as_str()));
59    all_le && any_lt
60}
61
62/// Check if two version vectors are concurrent (neither happens-before the other).
63#[allow(dead_code)]
64pub fn vv_concurrent(a: &VersionVector, b: &VersionVector) -> bool {
65    !vv_happens_before(a, b) && !vv_happens_before(b, a) && a != b
66}
67
68/// Compare two version vectors: -1 (a<b), 0 (equal), 1 (a>b), 2 (concurrent).
69#[allow(dead_code)]
70pub fn vv_compare(a: &VersionVector, b: &VersionVector) -> i32 {
71    if a == b {
72        0
73    } else if vv_happens_before(a, b) {
74        -1
75    } else if vv_happens_before(b, a) {
76        1
77    } else {
78        2
79    }
80}
81
82/// Number of nodes in the vector.
83#[allow(dead_code)]
84pub fn vv_node_count(vv: &VersionVector) -> usize {
85    vv.clocks.len()
86}
87
88/// Reset a node's clock to zero.
89#[allow(dead_code)]
90pub fn vv_reset_node(vv: &mut VersionVector, node: &str) {
91    vv.clocks.insert(node.to_string(), 0);
92}
93
94/// Return all node names.
95#[allow(dead_code)]
96pub fn vv_nodes(vv: &VersionVector) -> Vec<&str> {
97    vv.clocks.keys().map(|s| s.as_str()).collect()
98}
99
100#[cfg(test)]
101mod tests {
102    use super::*;
103
104    #[test]
105    fn new_is_empty() {
106        let vv = new_version_vector();
107        assert_eq!(vv_node_count(&vv), 0);
108    }
109
110    #[test]
111    fn increment_and_get() {
112        let mut vv = new_version_vector();
113        vv_increment(&mut vv, "A");
114        vv_increment(&mut vv, "A");
115        assert_eq!(vv_get(&vv, "A"), 2);
116    }
117
118    #[test]
119    fn get_missing_returns_zero() {
120        let vv = new_version_vector();
121        assert_eq!(vv_get(&vv, "X"), 0);
122    }
123
124    #[test]
125    fn merge_takes_max() {
126        let mut a = new_version_vector();
127        let mut b = new_version_vector();
128        vv_increment(&mut a, "A");
129        vv_increment(&mut b, "A");
130        vv_increment(&mut b, "A");
131        vv_increment(&mut b, "B");
132        let merged = vv_merge(&a, &b);
133        assert_eq!(vv_get(&merged, "A"), 2);
134        assert_eq!(vv_get(&merged, "B"), 1);
135    }
136
137    #[test]
138    fn happens_before_basic() {
139        let mut a = new_version_vector();
140        let mut b = new_version_vector();
141        vv_increment(&mut a, "A");
142        vv_increment(&mut b, "A");
143        vv_increment(&mut b, "A");
144        assert!(vv_happens_before(&a, &b));
145        assert!(!vv_happens_before(&b, &a));
146    }
147
148    #[test]
149    fn equal_vectors_not_happens_before() {
150        let mut a = new_version_vector();
151        let mut b = new_version_vector();
152        vv_increment(&mut a, "A");
153        vv_increment(&mut b, "A");
154        assert!(!vv_happens_before(&a, &b));
155    }
156
157    #[test]
158    fn concurrent_vectors() {
159        let mut a = new_version_vector();
160        let mut b = new_version_vector();
161        vv_increment(&mut a, "A");
162        vv_increment(&mut b, "B");
163        assert!(vv_concurrent(&a, &b));
164    }
165
166    #[test]
167    fn compare_equal() {
168        let mut a = new_version_vector();
169        let mut b = new_version_vector();
170        vv_increment(&mut a, "X");
171        vv_increment(&mut b, "X");
172        assert_eq!(vv_compare(&a, &b), 0);
173    }
174
175    #[test]
176    fn reset_node() {
177        let mut vv = new_version_vector();
178        vv_increment(&mut vv, "N");
179        vv_increment(&mut vv, "N");
180        vv_reset_node(&mut vv, "N");
181        assert_eq!(vv_get(&vv, "N"), 0);
182    }
183
184    #[test]
185    fn node_count_grows() {
186        let mut vv = new_version_vector();
187        vv_increment(&mut vv, "A");
188        vv_increment(&mut vv, "B");
189        assert_eq!(vv_node_count(&vv), 2);
190    }
191}
oxihuman_core/version_vector.rs

oxihuman_core/
version_vector.rs
