synckit_core/sync/
lww.rs

1//! Last-Write-Wins (LWW) merge algorithm
2//!
3//! Implements the TLA+ verified LWW merge algorithm from protocol/tla/lww_merge.tla
4
5use crate::sync::Timestamp;
6use serde::{Deserialize, Serialize};
7use serde_json::Value as JsonValue;
8
9/// A field value with LWW metadata
10#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
11pub struct LWWField {
12    /// The actual field value (JSON-like)
13    pub value: JsonValue,
14
15    /// Timestamp for conflict resolution
16    pub timestamp: Timestamp,
17}
18
19impl LWWField {
20    /// Create a new LWW field with a value and timestamp
21    pub fn new(value: JsonValue, timestamp: Timestamp) -> Self {
22        Self { value, timestamp }
23    }
24
25    /// Merge two LWW fields using Last-Write-Wins semantics
26    ///
27    /// This follows the TLA+ verified algorithm:
28    /// - If remote is newer (higher timestamp), use remote
29    /// - If local is newer, keep local
30    /// - If equal timestamps, use deterministic tie-breaking via client_id
31    pub fn merge(&self, other: &LWWField) -> LWWField {
32        match self.timestamp.compare_lww(&other.timestamp) {
33            std::cmp::Ordering::Less => {
34                // Remote is newer - use it
35                other.clone()
36            }
37            std::cmp::Ordering::Greater => {
38                // Local is newer - keep it
39                self.clone()
40            }
41            std::cmp::Ordering::Equal => {
42                // Equal timestamps - already handled by compare_lww via client_id
43                self.clone()
44            }
45        }
46    }
47
48    /// Check if this field is newer than another
49    pub fn is_newer_than(&self, other: &LWWField) -> bool {
50        self.timestamp.is_newer_than(&other.timestamp)
51    }
52}
53
54#[cfg(test)]
55mod tests {
56    use super::*;
57    use serde_json::json;
58
59    #[test]
60    fn test_merge_remote_newer() {
61        let local = LWWField::new(json!("old"), Timestamp::new(1, "client1".into()));
62        let remote = LWWField::new(json!("new"), Timestamp::new(2, "client2".into()));
63
64        let result = local.merge(&remote);
65        assert_eq!(result.value, json!("new"));
66        assert_eq!(result.timestamp.clock, 2);
67    }
68
69    #[test]
70    fn test_merge_local_newer() {
71        let local = LWWField::new(json!("new"), Timestamp::new(2, "client1".into()));
72        let remote = LWWField::new(json!("old"), Timestamp::new(1, "client2".into()));
73
74        let result = local.merge(&remote);
75        assert_eq!(result.value, json!("new"));
76        assert_eq!(result.timestamp.clock, 2);
77    }
78
79    #[test]
80    fn test_merge_same_timestamp_same_client() {
81        let local = LWWField::new(json!("value"), Timestamp::new(1, "client1".into()));
82        let remote = LWWField::new(json!("value"), Timestamp::new(1, "client1".into()));
83
84        let result = local.merge(&remote);
85        assert_eq!(result.value, json!("value"));
86    }
87
88    #[test]
89    fn test_merge_same_timestamp_different_clients() {
90        let local = LWWField::new(json!("alpha"), Timestamp::new(1, "client_a".into()));
91        let remote = LWWField::new(json!("beta"), Timestamp::new(1, "client_b".into()));
92
93        // client_b > client_a lexicographically, so remote should win
94        let result = local.merge(&remote);
95        assert_eq!(result.value, json!("beta"));
96
97        // Verify commutativity
98        let result2 = remote.merge(&local);
99        assert_eq!(result.value, result2.value);
100    }
101
102    #[test]
103    fn test_idempotence() {
104        let field = LWWField::new(json!("value"), Timestamp::new(1, "client1".into()));
105
106        let result = field.merge(&field);
107        assert_eq!(result.value, field.value);
108        assert_eq!(result.timestamp, field.timestamp);
109    }
110}
synckit_core/sync/lww.rs

synckit_core/sync/
lww.rs
