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 vec: Vec<ID> = self.iter().collect();
221        postcard::to_allocvec(&vec).unwrap()
222    }
223
224    #[inline]
225    pub fn decode(bytes: &[u8]) -> Result<Self, LoroError> {
226        let vec: Vec<ID> = postcard::from_bytes(bytes).map_err(|_| {
227            LoroError::DecodeError("Decode Frontiers error".to_string().into_boxed_str())
228        })?;
229        Ok(Self::from(vec))
230    }
231
232    pub fn update_frontiers_on_new_change(&mut self, id: ID, deps: &Frontiers) {
233        if self.len() <= 8 && self == deps {
234            *self = Frontiers::from_id(id);
235            return;
236        }
237
238        // Remove all IDs in deps from self
239        for dep in deps.iter() {
240            self.remove(&dep);
241        }
242
243        // Add the new ID
244        self.push(id);
245    }
246
247    #[inline]
248    pub(crate) fn with_capacity(_cap: usize) -> Frontiers {
249        // TODO
250        Self::None
251    }
252
253    pub fn is_empty(&self) -> bool {
254        self.len() == 0
255    }
256
257    /// Returns the single ID if the Frontiers contains exactly one ID, otherwise returns None.
258    pub fn as_single(&self) -> Option<ID> {
259        match self {
260            Frontiers::ID(id) => Some(*id),
261            _ => None,
262        }
263    }
264
265    /// Returns a reference to the internal map if the Frontiers contains multiple IDs,
266    /// otherwise returns None.
267    pub fn as_map(&self) -> Option<&InternalMap> {
268        match self {
269            Frontiers::Map(map) => Some(map),
270            _ => None,
271        }
272    }
273
274    /// Merges another Frontiers into this one.
275    ///
276    /// Id from other will override the id with the same peer from self.
277    pub fn merge_with_greater(&mut self, other: &Frontiers) {
278        if self.is_empty() {
279            *self = other.clone();
280            return;
281        }
282
283        if let Some(id) = self.as_single() {
284            match other {
285                Frontiers::None => {}
286                Frontiers::ID(other_id) => {
287                    if id.peer == other_id.peer {
288                        *self = Frontiers::ID(ID::new(id.peer, id.counter.max(other_id.counter)));
289                    } else {
290                        self.push(*other_id);
291                    }
292                    return;
293                }
294                Frontiers::Map(internal_map) => {
295                    let mut map = internal_map.clone();
296                    Arc::make_mut(&mut map.0)
297                        .entry(id.peer)
298                        .and_modify(|c| *c = (*c).max(id.counter))
299                        .or_insert(id.counter);
300                    *self = Frontiers::Map(map);
301                }
302            }
303
304            return;
305        }
306
307        let Frontiers::Map(map) = self else {
308            unreachable!()
309        };
310        let map = Arc::make_mut(&mut map.0);
311        for id in other.iter() {
312            map.entry(id.peer)
313                .and_modify(|c| *c = (*c).max(id.counter))
314                .or_insert(id.counter);
315        }
316    }
317
318    pub fn to_vec(&self) -> Vec<ID> {
319        match self {
320            Frontiers::None => Vec::new(),
321            Frontiers::ID(id) => vec![*id],
322            Frontiers::Map(map) => map.iter().collect(),
323        }
324    }
325
326    /// Keeps only one element in the Frontiers, deleting all others.
327    /// If the Frontiers is empty, it remains empty.
328    /// If it contains multiple elements, it keeps the first one encountered.
329    pub fn keep_one(&mut self) {
330        match self {
331            Frontiers::None => {}
332            Frontiers::ID(_) => {}
333            Frontiers::Map(map) => {
334                if let Some((&peer, &counter)) = map.0.iter().next() {
335                    *self = Frontiers::ID(ID::new(peer, counter));
336                }
337            }
338        }
339    }
340}
341impl From<&[ID]> for Frontiers {
342    fn from(ids: &[ID]) -> Self {
343        match ids.len() {
344            0 => Frontiers::None,
345            1 => Frontiers::ID(ids[0]),
346            _ => {
347                let mut map = InternalMap::new();
348                for &id in ids {
349                    map.insert(id);
350                }
351                Frontiers::Map(map)
352            }
353        }
354    }
355}
356
357impl From<Vec<ID>> for Frontiers {
358    fn from(ids: Vec<ID>) -> Self {
359        match ids.len() {
360            0 => Frontiers::None,
361            1 => Frontiers::ID(ids[0]),
362            _ => {
363                let mut map = InternalMap::new();
364                for id in ids {
365                    map.insert(id);
366                }
367                Frontiers::Map(map)
368            }
369        }
370    }
371}
372
373impl From<ID> for Frontiers {
374    fn from(value: ID) -> Self {
375        Self::ID(value)
376    }
377}
378
379impl FromIterator<ID> for Frontiers {
380    fn from_iter<I: IntoIterator<Item = ID>>(iter: I) -> Self {
381        let mut new = Self::new();
382        for id in iter {
383            new.push(id);
384        }
385        new
386    }
387}
388
389impl From<Option<ID>> for Frontiers {
390    fn from(value: Option<ID>) -> Self {
391        match value {
392            Some(id) => Frontiers::ID(id),
393            None => Frontiers::None,
394        }
395    }
396}
397
398impl<const N: usize> From<[ID; N]> for Frontiers {
399    fn from(value: [ID; N]) -> Self {
400        match N {
401            0 => Frontiers::None,
402            1 => Frontiers::ID(value[0]),
403            _ => {
404                let mut map = InternalMap::new();
405                for id in value {
406                    map.insert(id);
407                }
408                Frontiers::Map(map)
409            }
410        }
411    }
412}
413
414impl From<&Vec<ID>> for Frontiers {
415    fn from(ids: &Vec<ID>) -> Self {
416        match ids.len() {
417            0 => Frontiers::None,
418            1 => Frontiers::ID(ids[0]),
419            _ => {
420                let mut map = InternalMap::new();
421                for id in ids {
422                    map.insert(*id);
423                }
424                Frontiers::Map(map)
425            }
426        }
427    }
428}
429
430#[cfg(test)]
431mod tests {
432    use super::*;
433
434    #[test]
435    fn test_frontiers_push_insert_remove() {
436        let mut frontiers = Frontiers::None;
437
438        // Test push
439        frontiers.push(ID::new(1, 1));
440        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 1)));
441
442        frontiers.push(ID::new(2, 1));
443        assert!(matches!(frontiers, Frontiers::Map(_)));
444        assert_eq!(frontiers.len(), 2);
445
446        frontiers.push(ID::new(1, 2));
447        assert_eq!(frontiers.len(), 2);
448        assert!(frontiers.contains(&ID::new(1, 2)));
449        assert!(!frontiers.contains(&ID::new(1, 1)));
450
451        // Test insert (via InternalMap)
452        if let Frontiers::Map(ref mut map) = frontiers {
453            map.insert(ID::new(3, 1));
454        }
455        assert_eq!(frontiers.len(), 3);
456        assert!(frontiers.contains(&ID::new(3, 1)));
457
458        // Test remove
459        frontiers.remove(&ID::new(2, 1));
460        assert_eq!(frontiers.len(), 2);
461        assert!(!frontiers.contains(&ID::new(2, 1)));
462
463        frontiers.remove(&ID::new(1, 2));
464        assert_eq!(frontiers, Frontiers::ID(ID::new(3, 1)));
465
466        frontiers.remove(&ID::new(3, 1));
467        assert_eq!(frontiers, Frontiers::None);
468    }
469
470    #[test]
471    fn test_frontiers_edge_cases() {
472        let mut frontiers = Frontiers::None;
473
474        // Push to empty
475        frontiers.push(ID::new(1, 1));
476        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 1)));
477
478        // Push same peer, higher counter
479        frontiers.push(ID::new(1, 2));
480        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 2)));
481
482        // Push same peer, lower counter (should not change)
483        frontiers.push(ID::new(1, 1));
484        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 2)));
485
486        // Push different peer
487        frontiers.push(ID::new(2, 1));
488        assert!(matches!(frontiers, Frontiers::Map(_)));
489        assert_eq!(frontiers.len(), 2);
490
491        // Remove non-existent
492        frontiers.remove(&ID::new(3, 1));
493        assert_eq!(frontiers.len(), 2);
494
495        // Remove until only one left
496        frontiers.remove(&ID::new(2, 1));
497        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 2)));
498
499        // Remove last
500        frontiers.remove(&ID::new(1, 2));
501        assert_eq!(frontiers, Frontiers::None);
502    }
503
504    #[test]
505    fn test_frontiers_retain() {
506        let mut frontiers = Frontiers::None;
507
508        // Test retain on empty frontiers
509        frontiers.retain(|_| true);
510        assert_eq!(frontiers, Frontiers::None);
511
512        // Test retain on single ID
513        frontiers.push(ID::new(1, 1));
514        frontiers.retain(|id| id.peer == 1);
515        assert_eq!(frontiers, Frontiers::ID(ID::new(1, 1)));
516
517        frontiers.retain(|id| id.peer == 2);
518        assert_eq!(frontiers, Frontiers::None);
519
520        // Test retain on multiple IDs
521        frontiers.push(ID::new(1, 1));
522        frontiers.push(ID::new(2, 2));
523        frontiers.push(ID::new(3, 3));
524
525        // Retain only even peer IDs
526        frontiers.retain(|id| id.peer % 2 == 0);
527        assert_eq!(frontiers, Frontiers::ID(ID::new(2, 2)));
528
529        // Add more IDs and test retaining multiple
530        frontiers.push(ID::new(1, 1));
531        frontiers.push(ID::new(3, 3));
532        frontiers.push(ID::new(4, 4));
533
534        frontiers.retain(|id| id.peer > 2);
535        assert!(matches!(frontiers, Frontiers::Map(_)));
536        assert_eq!(frontiers.len(), 2);
537        assert!(frontiers.contains(&ID::new(3, 3)));
538        assert!(frontiers.contains(&ID::new(4, 4)));
539
540        // Retain none
541        frontiers.retain(|_| false);
542        assert_eq!(frontiers, Frontiers::None);
543    }
544
545    #[test]
546    fn test_frontiers_encode_decode() {
547        let mut frontiers = Frontiers::None;
548
549        // Test encode/decode for empty frontiers
550        let encoded = frontiers.encode();
551        let decoded = Frontiers::decode(&encoded).unwrap();
552        assert_eq!(frontiers, decoded);
553
554        // Test encode/decode for single ID
555        frontiers.push(ID::new(1, 100));
556        let encoded = frontiers.encode();
557        let decoded = Frontiers::decode(&encoded).unwrap();
558        assert_eq!(frontiers, decoded);
559
560        // Test encode/decode for multiple IDs
561        frontiers.push(ID::new(2, 200));
562        frontiers.push(ID::new(3, 300));
563        let encoded = frontiers.encode();
564        let decoded = Frontiers::decode(&encoded).unwrap();
565        assert_eq!(frontiers, decoded);
566
567        // Test encode/decode for many IDs
568        for i in 4..20 {
569            frontiers.push(ID::new(i, i as Counter * 100));
570        }
571        let encoded = frontiers.encode();
572        let decoded = Frontiers::decode(&encoded).unwrap();
573        assert_eq!(frontiers, decoded);
574
575        // Test decode with invalid input
576        assert!(Frontiers::decode(&[0xFF]).is_err());
577        assert!(Frontiers::decode(&[]).is_err());
578    }
579}
loro_internal/version/frontiers.rs

loro_internal/version/
frontiers.rs
