loro_internal/delta/
map_delta.rs

1use std::{hash::Hash, sync::Weak};
2
3use loro_common::IdLp;
4use rustc_hash::FxHashMap;
5use serde::{ser::SerializeStruct, Serialize};
6
7use crate::{
8    change::Lamport, handler::ValueOrHandler, id::PeerID, span::HasLamport, InternalString,
9    LoroDocInner, LoroValue,
10};
11
12#[derive(Default, Debug, Clone, Serialize)]
13pub struct MapDelta {
14    /// If the value is none, it's a uncreate op that should remove the entry from the
15    /// map container.
16    pub updated: FxHashMap<InternalString, Option<MapValue>>,
17}
18
19#[derive(Debug, Clone)]
20pub struct MapValue {
21    pub value: Option<LoroValue>,
22    pub lamp: Lamport,
23    pub peer: PeerID,
24}
25
26impl Ord for MapValue {
27    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
28        self.lamp
29            .cmp(&other.lamp)
30            .then_with(|| self.peer.cmp(&other.peer))
31    }
32}
33
34impl PartialOrd for MapValue {
35    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
36        Some(self.cmp(other))
37    }
38}
39
40impl PartialEq for MapValue {
41    fn eq(&self, other: &Self) -> bool {
42        self.lamp == other.lamp && self.peer == other.peer
43    }
44}
45
46impl Eq for MapValue {}
47
48impl MapValue {
49    pub fn idlp(&self) -> IdLp {
50        IdLp::new(self.peer, self.lamp)
51    }
52}
53
54#[derive(Default, Debug, Clone)]
55pub struct ResolvedMapDelta {
56    pub updated: FxHashMap<InternalString, ResolvedMapValue>,
57}
58
59#[derive(Debug, Clone)]
60pub struct ResolvedMapValue {
61    pub value: Option<ValueOrHandler>,
62    pub idlp: IdLp,
63}
64
65impl ResolvedMapValue {
66    pub(crate) fn from_map_value(v: MapValue, doc: &Weak<LoroDocInner>) -> Self {
67        let doc = &doc.upgrade().unwrap();
68        ResolvedMapValue {
69            idlp: IdLp::new(v.peer, v.lamp),
70            value: v.value.map(|v| ValueOrHandler::from_value(v, doc)),
71        }
72    }
73
74    /// This is used to indicate that the entry is unset. (caused by checkout to before the entry is created)
75    pub fn new_unset() -> Self {
76        ResolvedMapValue {
77            idlp: IdLp::new(PeerID::default(), Lamport::MAX),
78            value: None,
79        }
80    }
81}
82
83impl MapDelta {
84    pub(crate) fn compose(mut self, x: MapDelta) -> MapDelta {
85        for (k, v) in x.updated.into_iter() {
86            if let Some(old) = self.updated.get_mut(&k) {
87                if &v > old {
88                    *old = v;
89                }
90            } else {
91                self.updated.insert(k, v);
92            }
93        }
94        self
95    }
96
97    #[inline]
98    pub fn new() -> Self {
99        MapDelta {
100            updated: FxHashMap::default(),
101        }
102    }
103
104    #[inline]
105    pub fn with_entry(mut self, key: InternalString, map_value: MapValue) -> Self {
106        self.updated.insert(key, Some(map_value));
107        self
108    }
109}
110
111impl ResolvedMapDelta {
112    pub(crate) fn compose(&self, x: ResolvedMapDelta) -> ResolvedMapDelta {
113        let mut updated = self.updated.clone();
114        for (k, v) in x.updated.into_iter() {
115            if let Some(old) = updated.get_mut(&k) {
116                if v.idlp > old.idlp {
117                    *old = v;
118                }
119            } else {
120                updated.insert(k, v);
121            }
122        }
123        ResolvedMapDelta { updated }
124    }
125
126    #[inline]
127    pub fn new() -> Self {
128        ResolvedMapDelta {
129            updated: FxHashMap::default(),
130        }
131    }
132
133    #[inline]
134    pub fn with_entry(mut self, key: InternalString, map_value: ResolvedMapValue) -> Self {
135        self.updated.insert(key, map_value);
136        self
137    }
138
139    pub(crate) fn transform(&mut self, b: &ResolvedMapDelta, left_prior: bool) {
140        for (k, _) in b.updated.iter() {
141            if !left_prior {
142                self.updated.remove(k);
143            }
144        }
145    }
146}
147
148impl Hash for MapValue {
149    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
150        // value is not being hashed
151        self.peer.hash(state);
152        self.lamp.hash(state);
153    }
154}
155
156impl HasLamport for MapValue {
157    fn lamport(&self) -> Lamport {
158        self.lamp
159    }
160}
161
162impl Serialize for MapValue {
163    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
164    where
165        S: serde::Serializer,
166    {
167        let mut s = serializer.serialize_struct("MapValue", 2)?;
168        s.serialize_field("value", &self.value)?;
169        s.serialize_field("lamport", &self.lamp)?;
170        s.serialize_field("id", &self.idlp())?;
171        s.end()
172    }
173}
174
175#[cfg(test)]
176mod tests {
177    use std::hash::{Hash, Hasher};
178
179    use rustc_hash::FxHasher;
180
181    use crate::{handler::ValueOrHandler, LoroValue};
182
183    use super::*;
184
185    fn key(value: &str) -> InternalString {
186        value.into()
187    }
188
189    fn map_value(lamp: Lamport, peer: PeerID, value: i64) -> MapValue {
190        MapValue {
191            value: Some(LoroValue::I64(value)),
192            lamp,
193            peer,
194        }
195    }
196
197    fn resolved_value(lamp: Lamport, peer: PeerID, value: i64) -> ResolvedMapValue {
198        ResolvedMapValue {
199            value: Some(ValueOrHandler::Value(LoroValue::I64(value))),
200            idlp: IdLp::new(peer, lamp),
201        }
202    }
203
204    fn hash_map_value(value: &MapValue) -> u64 {
205        let mut hasher = FxHasher::default();
206        value.hash(&mut hasher);
207        hasher.finish()
208    }
209
210    #[test]
211    fn map_value_ordering_identity_and_hash_are_timestamp_based() {
212        let lower_lamport = map_value(1, 9, 10);
213        let higher_lamport = map_value(2, 1, 20);
214        let lower_peer = map_value(2, 1, 30);
215        let higher_peer = map_value(2, 2, 40);
216
217        assert!(higher_lamport > lower_lamport);
218        assert!(higher_peer > lower_peer);
219        assert_eq!(higher_peer.idlp(), IdLp::new(2, 2));
220        assert_eq!(higher_peer.lamport(), 2);
221
222        let same_id_different_value = MapValue {
223            value: Some(LoroValue::I64(999)),
224            ..higher_peer.clone()
225        };
226        assert_eq!(higher_peer, same_id_different_value);
227        assert_eq!(
228            hash_map_value(&higher_peer),
229            hash_map_value(&same_id_different_value)
230        );
231    }
232
233    #[test]
234    fn map_delta_compose_keeps_latest_timestamp_per_key() {
235        let initial = MapDelta::new()
236            .with_entry(key("same"), map_value(2, 1, 10))
237            .with_entry(key("left-only"), map_value(1, 1, 11));
238
239        let mut incoming = MapDelta::new()
240            .with_entry(key("same"), map_value(2, 2, 20))
241            .with_entry(key("right-only"), map_value(1, 1, 21));
242        incoming.updated.insert(key("unset"), None);
243
244        let composed = initial.compose(incoming);
245        assert_eq!(
246            composed
247                .updated
248                .get(&key("same"))
249                .and_then(|value| value.as_ref())
250                .and_then(|value| value.value.as_ref()),
251            Some(&LoroValue::I64(20))
252        );
253        assert!(composed.updated.contains_key(&key("left-only")));
254        assert!(composed.updated.contains_key(&key("right-only")));
255        assert_eq!(composed.updated.get(&key("unset")), Some(&None));
256    }
257
258    #[test]
259    fn map_delta_compose_does_not_let_older_entries_overwrite_newer_ones() {
260        let initial = MapDelta::new().with_entry(key("same"), map_value(5, 1, 50));
261        let incoming = MapDelta::new().with_entry(key("same"), map_value(4, 9, 40));
262
263        let composed = initial.compose(incoming);
264        let value = composed
265            .updated
266            .get(&key("same"))
267            .and_then(|value| value.as_ref())
268            .and_then(|value| value.value.as_ref());
269        assert_eq!(value, Some(&LoroValue::I64(50)));
270    }
271
272    #[test]
273    fn resolved_map_delta_compose_and_transform_apply_the_same_conflict_contract() {
274        let left = ResolvedMapDelta::new()
275            .with_entry(key("same"), resolved_value(1, 1, 10))
276            .with_entry(key("left-only"), resolved_value(1, 1, 11));
277        let right = ResolvedMapDelta::new()
278            .with_entry(key("same"), resolved_value(1, 2, 20))
279            .with_entry(key("right-only"), resolved_value(1, 1, 21));
280
281        let composed = left.compose(right.clone());
282        let value = composed.updated.get(&key("same")).unwrap();
283        assert_eq!(value.idlp, IdLp::new(2, 1));
284        assert_eq!(value.value.as_ref().unwrap().to_value(), LoroValue::I64(20));
285        assert!(composed.updated.contains_key(&key("left-only")));
286        assert!(composed.updated.contains_key(&key("right-only")));
287
288        let mut left_prior = composed.clone();
289        left_prior.transform(&right, true);
290        assert!(left_prior.updated.contains_key(&key("same")));
291
292        let mut right_prior = composed;
293        right_prior.transform(&right, false);
294        assert!(!right_prior.updated.contains_key(&key("same")));
295        assert!(!right_prior.updated.contains_key(&key("right-only")));
296        assert!(right_prior.updated.contains_key(&key("left-only")));
297    }
298
299    #[test]
300    fn resolved_unset_uses_max_lamport_to_win_against_material_values() {
301        let unset = ResolvedMapValue::new_unset();
302        let value = resolved_value(Lamport::MAX - 1, PeerID::MAX, 1);
303
304        let composed = ResolvedMapDelta::new()
305            .with_entry(key("field"), value)
306            .compose(ResolvedMapDelta::new().with_entry(key("field"), unset));
307        let entry = composed.updated.get(&key("field")).unwrap();
308        assert_eq!(entry.idlp, IdLp::new(PeerID::default(), Lamport::MAX));
309        assert!(entry.value.is_none());
310    }
311
312    #[test]
313    fn map_value_serialization_exposes_value_lamport_and_id() {
314        let serialized = serde_json::to_value(map_value(7, 8, 42)).unwrap();
315        assert_eq!(serialized["value"], serde_json::json!(42));
316        assert_eq!(serialized["lamport"], serde_json::json!(7));
317        assert_eq!(
318            serialized["id"],
319            serde_json::json!({ "peer": 8, "lamport": 7 })
320        );
321    }
322}
loro_internal/delta/map_delta.rs

loro_internal/delta/
map_delta.rs
