loro_internal/version/
frontiers.rs

1use super::*;
2use either::Either;
3
4/// Frontiers representation.
5//
6// Internal Invariance:
7// - Frontiers::Map(map) always have at least 2 elements.
8#[derive(Clone, Default)]
9pub enum Frontiers {
10    #[default]
11    None,
12    ID(ID),
13    // We use internal map to avoid the module outside accidentally create or modify the map
14    // to make it empty or only contain 1 element
15    Map(InternalMap),
16}
17
18use std::{fmt, sync::Arc};
19
20impl fmt::Debug for Frontiers {
21    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
22        f.debug_tuple("Frontiers")
23            .field(&FrontiersDebugHelper(self))
24            .finish()
25    }
26}
27
28struct FrontiersDebugHelper<'a>(&'a Frontiers);
29
30impl fmt::Debug for FrontiersDebugHelper<'_> {
31    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
32        let mut list = f.debug_list();
33        match self.0 {
34            Frontiers::None => {}
35            Frontiers::ID(id) => {
36                list.entry(id);
37            }
38            Frontiers::Map(map) => {
39                for id in map.iter() {
40                    list.entry(&id);
41                }
42            }
43        }
44        list.finish()
45    }
46}
47
48#[derive(Debug, Clone, PartialEq, Eq)]
49pub struct InternalMap(Arc<FxHashMap<PeerID, Counter>>);
50
51impl InternalMap {
52    fn new() -> Self {
53        Self(Arc::new(FxHashMap::default()))
54    }
55
56    fn len(&self) -> usize {
57        self.0.len()
58    }
59
60    fn iter(&self) -> impl Iterator<Item = ID> + '_ {
61        self.0
62            .iter()
63            .map(|(&peer, &counter)| ID::new(peer, counter))
64    }
65
66    fn contains(&self, id: &ID) -> bool {
67        self.0
68            .get(&id.peer)
69            .is_some_and(|&counter| counter == id.counter)
70    }
71
72    fn insert(&mut self, id: ID) {
73        Arc::make_mut(&mut self.0)
74            .entry(id.peer)
75            .and_modify(|e| *e = (*e).max(id.counter))
76            .or_insert(id.counter);
77    }
78
79    fn remove(&mut self, id: &ID) -> bool {
80        let map = Arc::make_mut(&mut self.0);
81        if let Some(counter) = map.get_mut(&id.peer) {
82            if *counter == id.counter {
83                map.remove(&id.peer);
84                return true;
85            }
86        }
87        false
88    }
89
90    fn retain<F>(&mut self, mut f: F)
91    where
92        F: FnMut(&ID) -> bool,
93    {
94        let map = Arc::make_mut(&mut self.0);
95        map.retain(|&peer, &mut counter| f(&ID::new(peer, counter)));
96    }
97}
98
99impl Frontiers {
100    pub fn len(&self) -> usize {
101        match self {
102            Frontiers::None => 0,
103            Frontiers::ID(_) => 1,
104            Frontiers::Map(map) => map.len(),
105        }
106    }
107
108    pub fn iter(&self) -> impl Iterator<Item = ID> + '_ {
109        match self {
110            Frontiers::None => Either::Left(Either::Left(std::iter::empty())),
111            Frontiers::ID(id) => Either::Left(Either::Right(std::iter::once(*id))),
112            Frontiers::Map(map) => Either::Right(map.iter()),
113        }
114    }
115
116    pub fn contains(&self, id: &ID) -> bool {
117        match self {
118            Frontiers::None => false,
119            Frontiers::ID(inner_id) => inner_id == id,
120            Frontiers::Map(map) => map.contains(id),
121        }
122    }
123
124    pub fn push(&mut self, id: ID) {
125        match self {
126            Frontiers::None => *self = Frontiers::ID(id),
127            Frontiers::ID(existing_id) => {
128                if existing_id.peer != id.peer {
129                    let mut map = InternalMap::new();
130                    map.insert(*existing_id);
131                    map.insert(id);
132                    *self = Frontiers::Map(map);
133                } else if existing_id.counter < id.counter {
134                    *existing_id = id;
135                }
136            }
137            Frontiers::Map(map) => map.insert(id),
138        }
139    }
140
141    pub fn retain<F>(&mut self, mut f: F)
142    where
143        F: FnMut(&ID) -> bool,
144    {
145        match self {
146            Frontiers::None => {}
147            Frontiers::ID(id) => {
148                if !f(id) {
149                    *self = Frontiers::None;
150                }
151            }
152            Frontiers::Map(map) => {
153                map.retain(|id| f(id));
154                match map.len() {
155                    0 => *self = Frontiers::None,
156                    1 => {
157                        let id = map.iter().next().unwrap();
158                        *self = Frontiers::ID(id);
159                    }
160                    _ => {}
161                }
162            }
163        }
164    }
165
166    pub fn remove(&mut self, id: &ID) {
167        match self {
168            Frontiers::None => {}
169            Frontiers::ID(existing_id) => {
170                if existing_id == id {
171                    *self = Frontiers::None;
172                }
173            }
174            Frontiers::Map(map) => {
175                if map.remove(id) {
176                    match map.len() {
177                        0 => *self = Frontiers::None,
178                        1 => {
179                            let id = map.iter().next().unwrap();
180                            *self = Frontiers::ID(id);
181                        }
182                        _ => {}
183                    }
184                }
185            }
186        }
187    }
188}
189
190impl PartialEq for Frontiers {
191    fn eq(&self, other: &Self) -> bool {
192        let len = self.len();
193        if len != other.len() {
194            return false;
195        }
196
197        match (self, other) {
198            (Frontiers::None, Frontiers::None) => true,
199            (Frontiers::ID(id1), Frontiers::ID(id2)) => id1 == id2,
200            (Frontiers::Map(map1), Frontiers::Map(map2)) => map1 == map2,
201            _ => unreachable!(),
202        }
203    }
204}
205
206impl Eq for Frontiers {}
207
208impl Frontiers {
209    pub fn new() -> Self {
210        Self::None
211    }
212
213    #[inline]
214    pub fn from_id(id: ID) -> Self {
215        Self::ID(id)
216    }
217
218    #[inline]
219    pub fn encode(&self) -> Vec<u8> {
220        let mut vec: Vec<ID> = self.iter().collect();
221        vec.sort();
222        postcard::to_allocvec(&vec).unwrap()
223    }
224
225    #[inline]
226    pub fn decode(bytes: &[u8]) -> Result<Self, LoroError> {
227        let vec: Vec<ID> = postcard::from_bytes(bytes).map_err(|_| {
228            LoroError::DecodeError("Decode Frontiers error".to_string().into_boxed_str())
229        })?;
230        Ok(Self::from(vec))
231    }
232
233    pub fn update_frontiers_on_new_change(&mut self, id: ID, deps: &Frontiers) {
234        if self.len() <= 8 && self == deps {
235            *self = Frontiers::from_id(id);
236            return;
237        }
238
239        // Remove all IDs in deps from self
240        for dep in deps.iter() {
241            self.remove(&dep);
242        }
243
244        // Add the new ID
245        self.push(id);
246    }
247
248    pub fn is_empty(&self) -> bool {
249        self.len() == 0
250    }
251
252    /// Returns the single ID if the Frontiers contains exactly one ID, otherwise returns None.
253    pub fn as_single(&self) -> Option<ID> {
254        match self {
255            Frontiers::ID(id) => Some(*id),
256            _ => None,
257        }
258    }
259
260    /// Returns a reference to the internal map if the Frontiers contains multiple IDs,
261    /// otherwise returns None.
262    pub fn as_map(&self) -> Option<&InternalMap> {
263        match self {
264            Frontiers::Map(map) => Some(map),
265            _ => None,
266        }
267    }
268
269    /// Merges another Frontiers into this one.
270    ///
271    /// Id from other will override the id with the same peer from self.
272    pub fn merge_with_greater(&mut self, other: &Frontiers) {
273        if self.is_empty() {
274            *self = other.clone();
275            return;
276        }
277
278        if let Some(id) = self.as_single() {
279            match other {
280                Frontiers::None => {}
281                Frontiers::ID(other_id) => {
282                    if id.peer == other_id.peer {
283                        *self = Frontiers::ID(ID::new(id.peer, id.counter.max(other_id.counter)));
284                    } else {
285                        self.push(*other_id);
286                    }
287                    return;
288                }
289                Frontiers::Map(internal_map) => {
290                    let mut map = internal_map.clone();
291                    Arc::make_mut(&mut map.0)
292                        .entry(id.peer)
293                        .and_modify(|c| *c = (*c).max(id.counter))
294                        .or_insert(id.counter);
295                    *self = Frontiers::Map(map);
296                }
297            }
298
299            return;
300        }
301
302        let Frontiers::Map(map) = self else {
303            unreachable!()
304        };
305        let map = Arc::make_mut(&mut map.0);
306        for id in other.iter() {
307            map.entry(id.peer)
308                .and_modify(|c| *c = (*c).max(id.counter))
309                .or_insert(id.counter);
310        }
311    }
312
313    pub fn to_vec(&self) -> Vec<ID> {
314        match self {
315            Frontiers::None => Vec::new(),
316            Frontiers::ID(id) => vec![*id],
317            Frontiers::Map(map) => map.iter().collect(),
318        }
319    }
320
321    /// Keeps only one element in the Frontiers, deleting all others.
322    /// If the Frontiers is empty, it remains empty.
323    /// If it contains multiple elements, it keeps the first one encountered.
324    pub fn keep_one(&mut self) {
325        match self {
326            Frontiers::None => {}
327            Frontiers::ID(_) => {}
328            Frontiers::Map(map) => {
329                if let Some((&peer, &counter)) = map.0.iter().next() {
330                    *self = Frontiers::ID(ID::new(peer, counter));
331                }
332            }
333        }
334    }
335}
336impl From<&[ID]> for Frontiers {
337    fn from(ids: &[ID]) -> Self {
338        match ids.len() {
339            0 => Frontiers::None,
340            1 => Frontiers::ID(ids[0]),
341            _ => {
342                let mut map = InternalMap::new();
343                for &id in ids {
344                    map.insert(id);
345                }
346                Frontiers::Map(map)
347            }
348        }
349    }
350}
351
352impl From<Vec<ID>> for Frontiers {
353    fn from(ids: Vec<ID>) -> Self {
354        match ids.len() {
355            0 => Frontiers::None,
356            1 => Frontiers::ID(ids[0]),
357            _ => {
358                let mut map = InternalMap::new();
359                for id in ids {
360                    map.insert(id);
361                }
362                Frontiers::Map(map)
363            }
364        }
365    }
366}
367
368impl From<ID> for Frontiers {
369    fn from(value: ID) -> Self {
370        Self::ID(value)
371    }
372}
373
374impl FromIterator<ID> for Frontiers {
375    fn from_iter<I: IntoIterator<Item = ID>>(iter: I) -> Self {
376        let mut new = Self::new();
377        for id in iter {
378            new.push(id);
379        }
380        new
381    }
382}
383
384impl From<Option<ID>> for Frontiers {
385    fn from(value: Option<ID>) -> Self {
386        match value {
387            Some(id) => Frontiers::ID(id),
388            None => Frontiers::None,
389        }
390    }
391}
392
393impl<const N: usize> From<[ID; N]> for Frontiers {
394    fn from(value: [ID; N]) -> Self {
395        match N {
396            0 => Frontiers::None,
397            1 => Frontiers::ID(value[0]),
398            _ => {
399                let mut map = InternalMap::new();
400                for id in value {
401                    map.insert(id);
402                }
403                Frontiers::Map(map)
404            }
405        }
406    }
407}
408
409impl From<&Vec<ID>> for Frontiers {
410    fn from(ids: &Vec<ID>) -> Self {
411        match ids.len() {
412            0 => Frontiers::None,
413            1 => Frontiers::ID(ids[0]),
414            _ => {
415                let mut map = InternalMap::new();
416                for id in ids {
417                    map.insert(*id);
418                }
419                Frontiers::Map(map)
420            }
421        }
422    }
423}
424
425#[cfg(test)]
426mod tests {
427    use super::*;
428
429    #[test]
430    fn test_frontiers_push_insert_remove() {
431        let mut frontiers = Frontiers::None;
432
433        // Test push
434        frontiers.push(ID::new(1, 1));
435        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 1)));
436
437        frontiers.push(ID::new(2, 1));
438        assert!(matches!(frontiers, Frontiers::Map(_)));
439        assert_eq!(frontiers.len(), 2);
440
441        frontiers.push(ID::new(1, 2));
442        assert_eq!(frontiers.len(), 2);
443        assert!(frontiers.contains(&ID::new(1, 2)));
444        assert!(!frontiers.contains(&ID::new(1, 1)));
445
446        // Test insert (via InternalMap)
447        if let Frontiers::Map(ref mut map) = frontiers {
448            map.insert(ID::new(3, 1));
449        }
450        assert_eq!(frontiers.len(), 3);
451        assert!(frontiers.contains(&ID::new(3, 1)));
452
453        // Test remove
454        frontiers.remove(&ID::new(2, 1));
455        assert_eq!(frontiers.len(), 2);
456        assert!(!frontiers.contains(&ID::new(2, 1)));
457
458        frontiers.remove(&ID::new(1, 2));
459        assert_eq!(frontiers, Frontiers::ID(ID::new(3, 1)));
460
461        frontiers.remove(&ID::new(3, 1));
462        assert_eq!(frontiers, Frontiers::None);
463    }
464
465    #[test]
466    fn test_frontiers_edge_cases() {
467        let mut frontiers = Frontiers::None;
468
469        // Push to empty
470        frontiers.push(ID::new(1, 1));
471        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 1)));
472
473        // Push same peer, higher counter
474        frontiers.push(ID::new(1, 2));
475        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 2)));
476
477        // Push same peer, lower counter (should not change)
478        frontiers.push(ID::new(1, 1));
479        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 2)));
480
481        // Push different peer
482        frontiers.push(ID::new(2, 1));
483        assert!(matches!(frontiers, Frontiers::Map(_)));
484        assert_eq!(frontiers.len(), 2);
485
486        // Remove non-existent
487        frontiers.remove(&ID::new(3, 1));
488        assert_eq!(frontiers.len(), 2);
489
490        // Remove until only one left
491        frontiers.remove(&ID::new(2, 1));
492        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 2)));
493
494        // Remove last
495        frontiers.remove(&ID::new(1, 2));
496        assert_eq!(frontiers, Frontiers::None);
497    }
498
499    #[test]
500    fn test_frontiers_retain() {
501        let mut frontiers = Frontiers::None;
502
503        // Test retain on empty frontiers
504        frontiers.retain(|_| true);
505        assert_eq!(frontiers, Frontiers::None);
506
507        // Test retain on single ID
508        frontiers.push(ID::new(1, 1));
509        frontiers.retain(|id| id.peer == 1);
510        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 1)));
511
512        frontiers.retain(|id| id.peer == 2);
513        assert_eq!(frontiers, Frontiers::None);
514
515        // Test retain on multiple IDs
516        frontiers.push(ID::new(1, 1));
517        frontiers.push(ID::new(2, 2));
518        frontiers.push(ID::new(3, 3));
519
520        // Retain only even peer IDs
521        frontiers.retain(|id| id.peer % 2 == 0);
522        assert_eq!(frontiers, Frontiers::ID(ID::new(2, 2)));
523
524        // Add more IDs and test retaining multiple
525        frontiers.push(ID::new(1, 1));
526        frontiers.push(ID::new(3, 3));
527        frontiers.push(ID::new(4, 4));
528
529        frontiers.retain(|id| id.peer > 2);
530        assert!(matches!(frontiers, Frontiers::Map(_)));
531        assert_eq!(frontiers.len(), 2);
532        assert!(frontiers.contains(&ID::new(3, 3)));
533        assert!(frontiers.contains(&ID::new(4, 4)));
534
535        // Retain none
536        frontiers.retain(|_| false);
537        assert_eq!(frontiers, Frontiers::None);
538    }
539
540    #[test]
541    fn test_frontiers_encode_decode() {
542        let mut frontiers = Frontiers::None;
543
544        // Test encode/decode for empty frontiers
545        let encoded = frontiers.encode();
546        let decoded = Frontiers::decode(&encoded).unwrap();
547        assert_eq!(frontiers, decoded);
548
549        // Test encode/decode for single ID
550        frontiers.push(ID::new(1, 100));
551        let encoded = frontiers.encode();
552        let decoded = Frontiers::decode(&encoded).unwrap();
553        assert_eq!(frontiers, decoded);
554
555        // Test encode/decode for multiple IDs
556        frontiers.push(ID::new(2, 200));
557        frontiers.push(ID::new(3, 300));
558        let encoded = frontiers.encode();
559        let decoded = Frontiers::decode(&encoded).unwrap();
560        assert_eq!(frontiers, decoded);
561
562        // Test encode/decode for many IDs
563        for i in 4..20 {
564            frontiers.push(ID::new(i, i as Counter * 100));
565        }
566        let encoded = frontiers.encode();
567        let decoded = Frontiers::decode(&encoded).unwrap();
568        assert_eq!(frontiers, decoded);
569
570        // Test decode with invalid input
571        assert!(Frontiers::decode(&[0xFF]).is_err());
572        assert!(Frontiers::decode(&[]).is_err());
573    }
574}
loro_internal/version/frontiers.rs

loro_internal/version/
frontiers.rs
