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

loro_internal/version/
frontiers.rs
