safemesh_crdt/crdt/
lww_map.rs

1// SafeMesh — delta-state CRDT convergence, built on crdt-lean.
2// Copyright (C) 2026 Ben Cassie
3// SPDX-License-Identifier: Apache-2.0
4
5use crate::{Crdt, LwwDot, LwwEntry, MergeError, Mergeable, RecordId, WireError};
6use alloc::collections::BTreeMap;
7
8/// Delta for a last-writer-wins map.
9#[derive(Clone, Debug, PartialEq, Eq)]
10pub enum LwwMapDelta<K: Ord, V: Ord> {
11    Set {
12        key: K,
13        timestamp: u64,
14        replica: u64,
15        value: V,
16    },
17    Remove {
18        key: K,
19        timestamp: u64,
20        replica: u64,
21    },
22}
23
24/// Last-writer-wins map.
25///
26/// This is a flat tested-not-proven type. Each key has an optional max-dot value
27/// entry and an optional max-dot remove tombstone. A key is visible when its
28/// value dot is greater than its remove dot.
29#[derive(Clone, Debug, PartialEq, Eq)]
30pub struct LwwMap<K: Ord, V: Ord> {
31    pub(super) entries: BTreeMap<K, LwwEntry<V>>,
32    pub(super) removals: BTreeMap<K, LwwDot>,
33}
34
35impl<K: Ord, V: Ord> LwwMap<K, V> {
36    pub fn new() -> Self {
37        LwwMap {
38            entries: BTreeMap::new(),
39            removals: BTreeMap::new(),
40        }
41    }
42
43    pub fn set(&mut self, key: K, timestamp: u64, replica: u64, value: V) {
44        self.apply_entry(
45            key,
46            LwwEntry {
47                dot: LwwDot { timestamp, replica },
48                value,
49            },
50        );
51    }
52
53    pub fn remove(&mut self, key: K, timestamp: u64, replica: u64) {
54        self.apply_removal(key, LwwDot { timestamp, replica });
55    }
56
57    pub fn get(&self, key: &K) -> Option<&V> {
58        self.visible_entry(key).map(|entry| &entry.value)
59    }
60
61    pub fn visible_entry(&self, key: &K) -> Option<&LwwEntry<V>> {
62        let entry = self.entries.get(key)?;
63        match self.removals.get(key) {
64            Some(removal) if entry.dot <= *removal => None,
65            _ => Some(entry),
66        }
67    }
68
69    pub fn entries(&self) -> &BTreeMap<K, LwwEntry<V>> {
70        &self.entries
71    }
72
73    pub fn removals(&self) -> &BTreeMap<K, LwwDot> {
74        &self.removals
75    }
76
77    fn apply_entry(&mut self, key: K, entry: LwwEntry<V>) {
78        match self.entries.get(&key) {
79            Some(current) if current >= &entry => {}
80            _ => {
81                self.entries.insert(key, entry);
82            }
83        }
84    }
85
86    fn apply_removal(&mut self, key: K, dot: LwwDot) {
87        match self.removals.get(&key) {
88            Some(current) if *current >= dot => {}
89            _ => {
90                self.removals.insert(key, dot);
91            }
92        }
93    }
94}
95
96impl<K: Ord + Clone, V: Ord + Clone> LwwMap<K, V> {
97    pub fn merge(&mut self, other: &Self) {
98        for (key, entry) in other.entries.iter() {
99            self.apply_entry(key.clone(), entry.clone());
100        }
101        for (key, dot) in other.removals.iter() {
102            self.apply_removal(key.clone(), *dot);
103        }
104    }
105
106    pub fn value(&self) -> BTreeMap<K, V> {
107        self.entries
108            .iter()
109            .filter_map(|(key, entry)| {
110                if self.visible_entry(key).is_some() {
111                    Some((key.clone(), entry.value.clone()))
112                } else {
113                    None
114                }
115            })
116            .collect()
117    }
118}
119
120impl<K: Ord, V: Ord> Default for LwwMap<K, V> {
121    fn default() -> Self {
122        Self::new()
123    }
124}
125
126impl<K: Ord + Clone, V: Ord + Clone> Mergeable for LwwMap<K, V> {
127    fn merge(&mut self, other: &Self) -> Result<(), MergeError> {
128        LwwMap::merge(self, other);
129        Ok(())
130    }
131}
132
133impl<K: Ord + Clone, V: Ord + Clone> Crdt for LwwMap<K, V> {
134    type Delta = LwwMapDelta<K, V>;
135
136    /// Sets and removes may only assign their author's dot. Losing operations
137    /// with a matching author remain valid and are subsumed by the max-dot rule.
138    fn validate_record(&self, id: RecordId, delta: &Self::Delta) -> Result<(), WireError> {
139        id.require_positive_sequence("LWW map")?;
140        let replica = match delta {
141            LwwMapDelta::Set { replica, .. } | LwwMapDelta::Remove { replica, .. } => *replica,
142        };
143        if replica != id.replica {
144            return Err(WireError::OwnershipViolation);
145        }
146        Ok(())
147    }
148
149    fn apply_delta(&mut self, delta: Self::Delta) {
150        match delta {
151            LwwMapDelta::Set {
152                key,
153                timestamp,
154                replica,
155                value,
156            } => self.set(key, timestamp, replica, value),
157            LwwMapDelta::Remove {
158                key,
159                timestamp,
160                replica,
161            } => self.remove(key, timestamp, replica),
162        }
163    }
164}
safemesh_crdt/crdt/lww_map.rs

safemesh_crdt/crdt/
lww_map.rs
