ternary_version/
lib.rs

1//! # ternary-version
2//!
3//! Version vectors with ternary comparison for distributed GPU state.
4
5use std::collections::HashMap;
6
7#[derive(Debug, Clone, Copy, PartialEq, Eq)]
8pub enum VersionOrder { Newer = 1, Concurrent = 0, Older = -1 }
9
10#[derive(Debug, Clone)]
11pub struct VersionVector {
12    entries: HashMap<String, u64>,
13}
14
15impl VersionVector {
16    pub fn new() -> Self { Self { entries: HashMap::new() } }
17
18    pub fn increment(&mut self, node: &str) -> u64 {
19        let v = self.entries.entry(node.into()).or_insert(0);
20        *v += 1;
21        *v
22    }
23
24    pub fn get(&self, node: &str) -> u64 { self.entries.get(node).copied().unwrap_or(0) }
25
26    pub fn set(&mut self, node: &str, version: u64) {
27        self.entries.insert(node.into(), version);
28    }
29
30    /// Compare two version vectors: +1 if self dominates, -1 if other dominates, 0 if concurrent.
31    pub fn compare(&self, other: &VersionVector) -> VersionOrder {
32        let all_keys: std::collections::HashSet<&String> =
33            self.entries.keys().chain(other.entries.keys()).collect();
34
35        let mut self_greater = false;
36        let mut other_greater = false;
37
38        for key in &all_keys {
39            let a = self.entries.get(*key).copied().unwrap_or(0);
40            let b = other.entries.get(*key).copied().unwrap_or(0);
41            if a > b { self_greater = true; }
42            if b > a { other_greater = true; }
43        }
44
45        if self_greater && !other_greater { VersionOrder::Newer }
46        else if other_greater && !self_greater { VersionOrder::Older }
47        else { VersionOrder::Concurrent }
48    }
49
50    /// Merge: take component-wise max.
51    pub fn merge(&mut self, other: &VersionVector) {
52        for (key, &val) in &other.entries {
53            let current = self.entries.entry(key.clone()).or_insert(0);
54            *current = (*current).max(val);
55        }
56    }
57
58    pub fn is_empty(&self) -> bool { self.entries.is_empty() }
59    pub fn node_count(&self) -> usize { self.entries.len() }
60}
61
62impl Default for VersionVector { fn default() -> Self { Self::new() } }
63
64pub struct ConflictResolver {
65    resolver_id: String,
66    clock: VersionVector,
67    resolved: u64,
68}
69
70impl ConflictResolver {
71    pub fn new(id: &str) -> Self {
72        Self { resolver_id: id.into(), clock: VersionVector::new(), resolved: 0 }
73    }
74
75    /// Resolve conflict between two versions. Returns merged vector.
76    pub fn resolve(&mut self, a: &VersionVector, b: &VersionVector) -> VersionVector {
77        let mut merged = a.clone();
78        merged.merge(b);
79        merged.increment(&self.resolver_id);
80        self.clock.merge(&merged);
81        self.resolved += 1;
82        merged
83    }
84
85    pub fn resolved_count(&self) -> u64 { self.resolved }
86}
87
88#[cfg(test)]
89mod tests {
90    use super::*;
91
92    #[test]
93    fn test_increment() {
94        let mut vv = VersionVector::new();
95        vv.increment("node_a");
96        vv.increment("node_a");
97        assert_eq!(vv.get("node_a"), 2);
98    }
99
100    #[test]
101    fn test_newer() {
102        let mut a = VersionVector::new();
103        let b = VersionVector::new();
104        a.set("x", 2);
105        a.set("y", 1);
106        assert_eq!(a.compare(&b), VersionOrder::Newer);
107    }
108
109    #[test]
110    fn test_older() {
111        let a = VersionVector::new();
112        let mut b = VersionVector::new();
113        b.set("x", 5);
114        assert_eq!(a.compare(&b), VersionOrder::Older);
115    }
116
117    #[test]
118    fn test_concurrent() {
119        let mut a = VersionVector::new();
120        let mut b = VersionVector::new();
121        a.set("x", 2);
122        b.set("y", 2);
123        assert_eq!(a.compare(&b), VersionOrder::Concurrent);
124    }
125
126    #[test]
127    fn test_merge() {
128        let mut a = VersionVector::new();
129        let mut b = VersionVector::new();
130        a.set("x", 3);
131        b.set("x", 5);
132        b.set("y", 2);
133        a.merge(&b);
134        assert_eq!(a.get("x"), 5);
135        assert_eq!(a.get("y"), 2);
136    }
137
138    #[test]
139    fn test_equal() {
140        let mut a = VersionVector::new();
141        let mut b = VersionVector::new();
142        a.set("x", 3);
143        b.set("x", 3);
144        assert_eq!(a.compare(&b), VersionOrder::Concurrent); // equal is concurrent
145    }
146
147    #[test]
148    fn test_resolver() {
149        let mut cr = ConflictResolver::new("resolver1");
150        let mut a = VersionVector::new();
151        let mut b = VersionVector::new();
152        a.set("x", 2);
153        b.set("x", 3);
154        let merged = cr.resolve(&a, &b);
155        assert_eq!(merged.get("x"), 3);
156        assert_eq!(cr.resolved_count(), 1);
157    }
158
159    #[test]
160    fn test_empty_compare() {
161        let a = VersionVector::new();
162        let b = VersionVector::new();
163        assert_eq!(a.compare(&b), VersionOrder::Concurrent);
164    }
165}
ternary_version/lib.rs

ternary_version/
lib.rs
