loro_common/
span.rs

1use std::fmt::Debug;
2
3use crate::{Counter, IdLp, IdSpanVector, Lamport, PeerID, ID};
4use rle::{HasLength, Mergable, Slice, Sliceable};
5
6/// This struct supports reverse repr: `from` can be less than `to`.
7/// We need this because it'll make merging deletions easier.
8///
9/// But we should use it behavior conservatively.
10/// If it is not necessary to be reverse, it should not.
11#[derive(Clone, Copy, PartialEq, Eq)]
12pub struct CounterSpan {
13    // TODO: should be private. user should not be able to change start from smaller than end to be greater than end
14    pub start: Counter,
15    // TODO: should be private
16    pub end: Counter,
17}
18
19pub trait HasLamport {
20    fn lamport(&self) -> Lamport;
21}
22
23pub trait HasLamportSpan: HasLamport + rle::HasLength {
24    /// end is the exclusive end, last the inclusive end.
25    fn lamport_end(&self) -> Lamport {
26        self.lamport() + self.content_len() as Lamport
27    }
28
29    /// end is the exclusive end, last the inclusive end.
30    fn lamport_last(&self) -> Lamport {
31        self.lamport() + self.content_len() as Lamport - 1
32    }
33}
34
35impl Debug for CounterSpan {
36    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
37        f.write_str(format!("{}~{}", self.start, self.end).as_str())
38    }
39}
40
41impl CounterSpan {
42    #[inline]
43    pub fn new(from: Counter, to: Counter) -> Self {
44        CounterSpan {
45            start: from,
46            end: to,
47        }
48    }
49
50    #[inline]
51    pub fn reverse(&mut self) {
52        if self.start == self.end {
53            return;
54        }
55
56        if self.start < self.end {
57            (self.start, self.end) = (self.end - 1, self.start - 1);
58        } else {
59            (self.start, self.end) = (self.end + 1, self.start + 1);
60        }
61    }
62
63    /// Make end greater than start
64    pub fn normalize_(&mut self) {
65        if self.end < self.start {
66            self.reverse();
67        }
68    }
69
70    #[inline(always)]
71    pub fn bidirectional(&self) -> bool {
72        (self.end - self.start).abs() == 1
73    }
74
75    #[inline(always)]
76    pub fn direction(&self) -> i32 {
77        if self.start < self.end {
78            1
79        } else {
80            -1
81        }
82    }
83
84    #[inline(always)]
85    pub fn is_reversed(&self) -> bool {
86        self.end < self.start
87    }
88
89    #[inline]
90    pub fn min(&self) -> Counter {
91        if self.start < self.end {
92            self.start
93        } else {
94            self.end + 1
95        }
96    }
97
98    pub fn set_min(&mut self, min: Counter) {
99        if self.start < self.end {
100            self.start = min;
101        } else {
102            self.end = min - 1;
103        }
104    }
105
106    #[inline(always)]
107    pub fn max(&self) -> Counter {
108        if self.start > self.end {
109            self.start
110        } else {
111            self.end - 1
112        }
113    }
114
115    #[inline(always)]
116    /// Normalized end value.
117    ///
118    /// This is different from end. start may be greater than end. This is the max of start+1 and end
119    pub fn norm_end(&self) -> i32 {
120        if self.start < self.end {
121            self.end
122        } else {
123            self.start + 1
124        }
125    }
126
127    #[inline]
128    pub fn contains(&self, v: Counter) -> bool {
129        if self.start < self.end {
130            self.start <= v && v < self.end
131        } else {
132            self.start >= v && v > self.end
133        }
134    }
135
136    pub fn set_start(&mut self, new_start: Counter) {
137        if self.start < self.end {
138            self.start = new_start.min(self.end);
139        } else {
140            self.start = new_start.max(self.end);
141        }
142    }
143
144    pub fn set_end(&mut self, new_end: Counter) {
145        if self.start < self.end {
146            self.end = new_end.max(self.start);
147        } else {
148            self.end = new_end.min(self.start);
149        }
150    }
151
152    pub fn extend_include(&mut self, new_start: Counter, new_end: Counter) {
153        self.set_start(new_start);
154        self.set_end(new_end);
155    }
156
157    /// if we can merge element on the left, this method return the last atom of it
158    fn prev_pos(&self) -> i32 {
159        if self.start < self.end {
160            self.start - 1
161        } else {
162            self.start + 1
163        }
164    }
165
166    /// if we can merge element on the right, this method return the first atom of it
167    fn next_pos(&self) -> i32 {
168        self.end
169    }
170
171    fn get_intersection(&self, counter: &CounterSpan) -> Option<Self> {
172        let start = self.start.max(counter.start);
173        let end = self.end.min(counter.end);
174        if start < end {
175            Some(CounterSpan { start, end })
176        } else {
177            None
178        }
179    }
180}
181
182impl HasLength for CounterSpan {
183    #[inline]
184    fn content_len(&self) -> usize {
185        if self.start < self.end {
186            (self.end - self.start) as usize
187        } else {
188            (self.start - self.end) as usize
189        }
190    }
191}
192
193impl Sliceable for CounterSpan {
194    fn slice(&self, from: usize, to: usize) -> Self {
195        assert!(from <= to);
196        let len = to - from;
197        assert!(len <= self.content_len());
198        if self.start < self.end {
199            CounterSpan {
200                start: self.start + from as Counter,
201                end: self.start + to as Counter,
202            }
203        } else {
204            CounterSpan {
205                start: self.start - from as Counter,
206                end: self.start - to as Counter,
207            }
208        }
209    }
210}
211
212impl Mergable for CounterSpan {
213    #[inline]
214    fn is_mergable(&self, other: &Self, _: &()) -> bool {
215        match (self.bidirectional(), other.bidirectional()) {
216            (true, true) => self.start + 1 == other.start || self.start == other.start + 1,
217            (true, false) => self.start == other.prev_pos(),
218            (false, true) => self.next_pos() == other.start,
219            (false, false) => {
220                self.next_pos() == other.start && self.direction() == other.direction()
221            }
222        }
223    }
224
225    #[inline]
226    fn merge(&mut self, other: &Self, _: &()) {
227        match (self.bidirectional(), other.bidirectional()) {
228            (true, true) => {
229                if self.start + 1 == other.start {
230                    self.end = self.start + 2;
231                } else if self.start - 1 == other.start {
232                    self.end = self.start - 2;
233                }
234            }
235            (true, false) => self.end = other.end,
236            (false, true) => self.end += self.direction(),
237            (false, false) => {
238                self.end = other.end;
239            }
240        }
241    }
242}
243
244#[derive(Debug, Clone, Copy, PartialEq, Eq)]
245pub struct LamportSpan {
246    pub start: Lamport,
247    pub end: Lamport,
248}
249
250#[derive(Clone, Copy, PartialEq, Eq, Debug)]
251pub struct IdLpSpan {
252    pub peer: PeerID,
253    pub lamport: LamportSpan,
254}
255
256impl HasLength for IdLpSpan {
257    fn content_len(&self) -> usize {
258        (self.lamport.end - self.lamport.start) as usize
259    }
260}
261
262impl IdLpSpan {
263    pub fn new(peer: PeerID, from: Lamport, to: Lamport) -> Self {
264        Self {
265            peer,
266            lamport: LamportSpan {
267                start: from,
268                end: to,
269            },
270        }
271    }
272
273    pub fn contains(&self, id: IdLp) -> bool {
274        self.peer == id.peer && self.lamport.start <= id.lamport && id.lamport < self.lamport.end
275    }
276}
277
278/// This struct supports reverse repr: [CounterSpan]'s from can be less than to. But we should use it conservatively.
279/// We need this because it'll make merging deletions easier.
280#[derive(Clone, Copy, PartialEq, Eq, Debug)]
281pub struct IdSpan {
282    pub peer: PeerID,
283    pub counter: CounterSpan,
284}
285
286impl IdSpan {
287    #[inline]
288    pub fn new(peer: PeerID, from: Counter, to: Counter) -> Self {
289        Self {
290            peer,
291            counter: CounterSpan {
292                start: from,
293                end: to,
294            },
295        }
296    }
297
298    #[inline]
299    pub fn contains(&self, id: ID) -> bool {
300        self.peer == id.peer && self.counter.contains(id.counter)
301    }
302
303    #[inline(always)]
304    pub fn is_reversed(&self) -> bool {
305        self.counter.end < self.counter.start
306    }
307
308    #[inline(always)]
309    pub fn reverse(&mut self) {
310        self.counter.reverse();
311    }
312
313    #[inline(always)]
314    pub fn normalize_(&mut self) {
315        self.counter.normalize_();
316    }
317
318    /// This is different from id_start. id_start may be greater than id_end, but this is the min of id_start and id_end-1
319    #[inline]
320    pub fn norm_id_start(&self) -> ID {
321        ID::new(self.peer, self.counter.min())
322    }
323
324    /// This is different from id_end. id_start may be greater than id_end. This is the max of id_start+1 and id_end
325    #[inline]
326    pub fn norm_id_end(&self) -> ID {
327        ID::new(self.peer, self.counter.norm_end())
328    }
329
330    pub fn to_id_span_vec(self) -> IdSpanVector {
331        let mut out = IdSpanVector::default();
332        out.insert(self.peer, self.counter);
333        out
334    }
335
336    pub fn get_intersection(&self, other: &Self) -> Option<Self> {
337        if self.peer != other.peer {
338            return None;
339        }
340
341        let counter = self.counter.get_intersection(&other.counter)?;
342        Some(Self {
343            peer: self.peer,
344            counter,
345        })
346    }
347
348    pub fn get_slice_range_on(&self, other: &Self) -> Option<(usize, usize)> {
349        if self.peer != other.peer {
350            return None;
351        }
352
353        let self_start = self.counter.start.min(self.counter.end);
354        let self_end = self.counter.start.max(self.counter.end);
355        let other_start = other.counter.start.min(other.counter.end);
356        let other_end = other.counter.start.max(other.counter.end);
357
358        if self_start >= other_end || self_end <= other_start {
359            return None;
360        }
361
362        let start = (self_start.max(other_start) - other_start) as usize;
363        let end = (self_end.min(other_end) - other_start) as usize;
364
365        Some((start, end))
366    }
367}
368
369impl HasLength for IdSpan {
370    #[inline]
371    fn content_len(&self) -> usize {
372        self.counter.content_len()
373    }
374}
375
376impl Sliceable for IdSpan {
377    #[inline]
378    fn slice(&self, from: usize, to: usize) -> Self {
379        IdSpan {
380            peer: self.peer,
381            counter: self.counter.slice(from, to),
382        }
383    }
384}
385
386impl Mergable for IdSpan {
387    fn is_mergable(&self, other: &Self, _: &()) -> bool {
388        self.peer == other.peer && self.counter.is_mergable(&other.counter, &())
389    }
390
391    fn merge(&mut self, other: &Self, _: &()) {
392        self.counter.merge(&other.counter, &())
393    }
394}
395
396pub trait HasId {
397    fn id_start(&self) -> ID;
398}
399
400pub trait HasCounter {
401    fn ctr_start(&self) -> Counter;
402}
403
404pub trait HasCounterSpan: HasCounter + HasLength {
405    /// end is the exclusive end, last the inclusive end.
406    fn ctr_end(&self) -> Counter {
407        self.ctr_start() + self.atom_len() as Counter
408    }
409
410    /// end is the exclusive end, last the inclusive end.
411    fn ctr_last(&self) -> Counter {
412        self.ctr_start() + self.atom_len() as Counter - 1
413    }
414
415    fn ctr_span(&self) -> CounterSpan {
416        CounterSpan {
417            start: self.ctr_start(),
418            end: self.ctr_end(),
419        }
420    }
421}
422
423impl<T: HasCounter + HasLength> HasCounterSpan for T {}
424
425pub trait HasIdSpan: HasId + HasLength {
426    fn intersect<T: HasIdSpan>(&self, other: &T) -> bool {
427        let self_start = self.id_start();
428        let other_start = self.id_start();
429        if self_start.peer != other_start.peer {
430            false
431        } else {
432            let self_start = self_start.counter;
433            let other_start = other_start.counter;
434            let self_end = self.id_end().counter;
435            let other_end = other.id_end().counter;
436            self_start < other_end && other_start < self_end
437        }
438    }
439
440    fn id_span(&self) -> IdSpan {
441        let id = self.id_start();
442        IdSpan::new(
443            id.peer,
444            id.counter,
445            id.counter + self.content_len() as Counter,
446        )
447    }
448
449    /// end is the exclusive end, last the inclusive end.
450    fn id_end(&self) -> ID {
451        self.id_start().inc(self.content_len() as i32)
452    }
453
454    /// end is the exclusive end, last the inclusive end.
455    fn id_last(&self) -> ID {
456        self.id_start().inc(self.content_len() as i32 - 1)
457    }
458
459    fn contains_id(&self, id: ID) -> bool {
460        let id_start = self.id_start();
461        if id.peer != id_start.peer {
462            return false;
463        }
464
465        id_start.counter <= id.counter
466            && id.counter < id_start.counter + self.content_len() as Counter
467    }
468}
469impl<T: HasId + HasLength> HasIdSpan for T {}
470
471impl<T: HasLamport + HasLength> HasLamportSpan for T {}
472
473impl HasId for IdSpan {
474    #[inline]
475    fn id_start(&self) -> ID {
476        self.norm_id_start()
477    }
478}
479
480impl HasCounter for IdSpan {
481    #[inline]
482    fn ctr_start(&self) -> Counter {
483        self.counter.min()
484    }
485}
486
487impl<'a> From<Slice<'a, IdSpan>> for IdSpan {
488    fn from(slice: Slice<'a, IdSpan>) -> Self {
489        slice.value.slice(slice.start, slice.end)
490    }
491}
492
493impl HasId for (&PeerID, &CounterSpan) {
494    fn id_start(&self) -> ID {
495        ID {
496            peer: *self.0,
497            counter: self.1.min(),
498        }
499    }
500}
501
502impl HasId for (PeerID, CounterSpan) {
503    fn id_start(&self) -> ID {
504        ID {
505            peer: self.0,
506            counter: self.1.min(),
507        }
508    }
509}
510
511impl From<ID> for IdSpan {
512    fn from(value: ID) -> Self {
513        Self::new(value.peer, value.counter, value.counter + 1)
514    }
515}
516
517#[cfg(feature = "wasm")]
518mod wasm {
519    use js_sys::Object;
520    use wasm_bindgen::JsValue;
521
522    use super::CounterSpan;
523
524    impl From<CounterSpan> for JsValue {
525        fn from(value: CounterSpan) -> Self {
526            let obj = Object::new();
527            js_sys::Reflect::set(
528                &obj,
529                &JsValue::from_str("start"),
530                &JsValue::from(value.start),
531            )
532            .unwrap();
533            js_sys::Reflect::set(&obj, &JsValue::from_str("end"), &JsValue::from(value.end))
534                .unwrap();
535            obj.into()
536        }
537    }
538}
539
540#[cfg(test)]
541mod test_id_span {
542    use super::*;
543
544    #[test]
545    fn merge() {
546        let mut a = CounterSpan::new(0, 2);
547        let b = CounterSpan::new(2, 1);
548        assert!(a.is_mergable(&b, &()));
549        a.merge(&b, &());
550        assert_eq!(a, CounterSpan::new(0, 3));
551
552        let mut a = CounterSpan::new(3, 2);
553        let b = CounterSpan::new(2, 1);
554        assert!(a.is_mergable(&b, &()));
555        a.merge(&b, &());
556        assert_eq!(a, CounterSpan::new(3, 1));
557
558        let mut a = CounterSpan::new(4, 2);
559        let b = CounterSpan::new(2, 3);
560        assert!(a.is_mergable(&b, &()));
561        a.merge(&b, &());
562        assert_eq!(a, CounterSpan::new(4, 1));
563
564        let mut a = CounterSpan::new(8, 9);
565        let b = CounterSpan::new(9, 8);
566        assert!(a.is_mergable(&b, &()));
567        a.merge(&b, &());
568        assert_eq!(a, CounterSpan::new(8, 10));
569
570        let a = CounterSpan::new(8, 9);
571        let b = CounterSpan::new(10, 11);
572        assert!(!a.is_mergable(&b, &()));
573
574        let mut a = CounterSpan::new(0, 2);
575        let b = CounterSpan::new(2, 4);
576        assert!(a.is_mergable(&b, &()));
577        a.merge(&b, &());
578        assert_eq!(a, CounterSpan::new(0, 4));
579
580        let mut a = CounterSpan::new(4, 2);
581        let b = CounterSpan::new(2, 0);
582        assert!(a.is_mergable(&b, &()));
583        a.merge(&b, &());
584        assert_eq!(a, CounterSpan::new(4, 0));
585    }
586}
loro_common/span.rs

loro_common/
span.rs
