lumina_node/
block_ranges.rs

1//! Ranges utilities
2
3use std::borrow::Borrow;
4use std::fmt::{Debug, Display};
5use std::ops::{Add, RangeInclusive, Sub};
6
7use serde::Serialize;
8use smallvec::SmallVec;
9
10/// Type alias of [`RangeInclusive<u64>`].
11///
12/// [`RangeInclusive<u64>`]: std::ops::RangeInclusive
13pub type BlockRange = RangeInclusive<u64>;
14
15/// Errors that can be produced by [`BlockRanges`].
16#[derive(Debug, thiserror::Error, PartialEq, Eq)]
17pub enum BlockRangesError {
18    /// Block ranges must be sorted.
19    #[error("Block ranges are not sorted")]
20    UnsortedBlockRanges,
21
22    /// Not a valid block range.
23    #[error("Invalid block range: {}", .0.display())]
24    InvalidBlockRange(BlockRange),
25
26    /// Provided range overlaps with another one.
27    #[error("Insertion constrain not satisfied: Provided range ({}) overlaps with {}", .0.display(), .1.display())]
28    BlockRangeOverlap(BlockRange, BlockRange),
29
30    /// Provided range do not have any adjacent neightbors.
31    #[error(
32        "Insertion constrain not satified: Provided range ({}) do not have any adjacent neighbors", .0.display()
33    )]
34    NoAdjacentNeighbors(BlockRange),
35}
36
37type Result<T, E = BlockRangesError> = std::result::Result<T, E>;
38
39pub(crate) trait BlockRangeExt {
40    fn display(&self) -> BlockRangeDisplay;
41    fn validate(&self) -> Result<()>;
42    fn len(&self) -> u64;
43    fn is_adjacent(&self, other: &BlockRange) -> bool;
44    fn is_overlapping(&self, other: &BlockRange) -> bool;
45    fn left_of(&self, other: &BlockRange) -> bool;
46    fn truncate_left(&self, limit: u64) -> Self;
47    fn truncate_right(&self, limit: u64) -> Self;
48}
49
50pub(crate) struct BlockRangeDisplay<'a>(&'a RangeInclusive<u64>);
51
52impl Display for BlockRangeDisplay<'_> {
53    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
54        write!(f, "{}-{}", self.0.start(), self.0.end())
55    }
56}
57
58impl BlockRangeExt for BlockRange {
59    fn display(&self) -> BlockRangeDisplay<'_> {
60        BlockRangeDisplay(self)
61    }
62
63    fn validate(&self) -> Result<()> {
64        if *self.start() > 0 && self.start() <= self.end() {
65            Ok(())
66        } else {
67            Err(BlockRangesError::InvalidBlockRange(self.to_owned()))
68        }
69    }
70
71    fn len(&self) -> u64 {
72        match self.end().checked_sub(*self.start()) {
73            Some(difference) => difference + 1,
74            None => 0,
75        }
76    }
77
78    fn is_adjacent(&self, other: &BlockRange) -> bool {
79        debug_assert!(self.validate().is_ok());
80        debug_assert!(other.validate().is_ok());
81
82        // End of `self` touches start of `other`
83        //
84        // self:  |------|
85        // other:         |------|
86        if *self.end() == other.start().saturating_sub(1) {
87            return true;
88        }
89
90        // Start of `self` touches end of `other`
91        //
92        // self:          |------|
93        // other: |------|
94        if self.start().saturating_sub(1) == *other.end() {
95            return true;
96        }
97
98        false
99    }
100
101    fn is_overlapping(&self, other: &BlockRange) -> bool {
102        debug_assert!(self.validate().is_ok());
103        debug_assert!(other.validate().is_ok());
104
105        // `self` overlaps with start of `other`
106        //
107        // self:  |------|
108        // other:     |------|
109        if self.start() < other.start() && other.contains(self.end()) {
110            return true;
111        }
112
113        // `self` overlaps with end of `other`
114        //
115        // self:      |------|
116        // other: |------|
117        if self.end() > other.end() && other.contains(self.start()) {
118            return true;
119        }
120
121        // `self` is subset of `other`
122        //
123        // self:    |--|
124        // other: |------|
125        if self.start() >= other.start() && self.end() <= other.end() {
126            return true;
127        }
128
129        // `self` is superset of `other`
130        //
131        // self:  |------|
132        // other:   |--|
133        if self.start() <= other.start() && self.end() >= other.end() {
134            return true;
135        }
136
137        false
138    }
139
140    /// Returns `true` if the whole range of `self` is on the left of `other`.
141    fn left_of(&self, other: &BlockRange) -> bool {
142        debug_assert!(self.validate().is_ok());
143        debug_assert!(other.validate().is_ok());
144        self.end() < other.start()
145    }
146
147    /// Truncate the range so that it contains at most `limit` elements, removing from the left
148    fn truncate_left(&self, limit: u64) -> Self {
149        if self.is_empty() {
150            return RangeInclusive::new(1, 0);
151        }
152        let start = *self.start();
153        let end = *self.end();
154
155        let Some(adjusted_start) = end.saturating_sub(limit).checked_add(1) else {
156            // overflow can happen only if limit == 0, which is an empty range anyway
157            return RangeInclusive::new(1, 0);
158        };
159
160        u64::max(start, adjusted_start)..=end
161    }
162
163    /// Truncate the range so that it contains at most `limit` elements, removing from the right
164    fn truncate_right(&self, limit: u64) -> Self {
165        if self.is_empty() {
166            return RangeInclusive::new(1, 0);
167        }
168        let start = *self.start();
169        let end = *self.end();
170
171        let Some(adjusted_end) = start.saturating_add(limit).checked_sub(1) else {
172            return RangeInclusive::new(1, 0);
173        };
174
175        start..=u64::min(end, adjusted_end)
176    }
177}
178
179/// Represents possibly multiple non-overlapping, sorted ranges of header heights
180#[derive(Debug, Clone, PartialEq, Default, Serialize)]
181#[serde(transparent)]
182pub struct BlockRanges(SmallVec<[BlockRange; 2]>);
183
184/// Custom `Deserialize` that validates `BlockRanges`.
185impl<'de> serde::Deserialize<'de> for BlockRanges {
186    fn deserialize<D>(deserializer: D) -> Result<BlockRanges, D::Error>
187    where
188        D: serde::de::Deserializer<'de>,
189    {
190        let raw_ranges = SmallVec::<[RangeInclusive<u64>; 2]>::deserialize(deserializer)?;
191        let ranges = BlockRanges::from_vec(raw_ranges)
192            .map_err(|e| serde::de::Error::custom(e.to_string()))?;
193        Ok(ranges)
194    }
195}
196
197impl BlockRanges {
198    /// Create a new, empty `BlockRanges`.
199    pub fn new() -> BlockRanges {
200        BlockRanges(SmallVec::new())
201    }
202
203    /// Create a `BlockRanges` from a [`SmallVec`].
204    pub fn from_vec(ranges: SmallVec<[BlockRange; 2]>) -> Result<Self> {
205        let mut prev: Option<&RangeInclusive<u64>> = None;
206
207        for range in &ranges {
208            range.validate()?;
209
210            if let Some(prev) = prev {
211                if range.start() <= prev.end() {
212                    return Err(BlockRangesError::UnsortedBlockRanges);
213                }
214            }
215
216            prev = Some(range);
217        }
218
219        Ok(BlockRanges(ranges))
220    }
221
222    /// Returns internal representation.
223    pub fn into_inner(self) -> SmallVec<[BlockRange; 2]> {
224        self.0
225    }
226
227    /// Return whether `BlockRanges` contains provided height.
228    pub fn contains(&self, height: u64) -> bool {
229        self.0.iter().any(|r| r.contains(&height))
230    }
231
232    /// Return whether range is empty.
233    pub fn is_empty(&self) -> bool {
234        self.0.iter().all(|r| r.is_empty())
235    }
236
237    /// Return highest height in the range.
238    pub fn head(&self) -> Option<u64> {
239        self.0.last().map(|r| *r.end())
240    }
241
242    /// Return lowest height in the range.
243    pub fn tail(&self) -> Option<u64> {
244        self.0.first().map(|r| *r.start())
245    }
246
247    /// Returns first and last index of ranges overlapping or touching provided `range`.
248    fn find_affected_ranges(&self, range: impl Borrow<BlockRange>) -> Option<(usize, usize)> {
249        let range = range.borrow();
250        debug_assert!(range.validate().is_ok());
251
252        let mut start_idx = None;
253        let mut end_idx = None;
254
255        for (i, r) in self.0.iter().enumerate() {
256            if r.is_overlapping(range) || r.is_adjacent(range) {
257                if start_idx.is_none() {
258                    start_idx = Some(i);
259                }
260
261                end_idx = Some(i);
262            } else if end_idx.is_some() {
263                // Ranges are sorted, we can skip checking the rest.
264                break;
265            }
266        }
267
268        Some((start_idx?, end_idx?))
269    }
270
271    /// Checks if `to_insert` is valid range to be inserted into the header store.
272    ///
273    /// This *must* be used when implementing [`Store::insert`].
274    ///
275    /// The constraints are as follows:
276    ///
277    /// * Insertion range must be valid.
278    /// * Insertion range must not overlap with any of the existing ranges.
279    /// * Insertion range must be appended to the left or to the right of an existing range.
280    /// * Insertion is always allowed on empty `BlockRanges`.
281    /// * New HEAD range can be created at the front if it doesn't overlap with existing one.
282    ///
283    /// Returns:
284    ///
285    /// * `Err(_)` if constraints are not met.
286    /// * `Ok(true, false)` if `to_insert` range is going to be merged with its left neighbor.
287    /// * `Ok(false, true)` if `to_insert` range is going to be merged with the right neighbor.
288    /// * `Ok(true, true)` if `to_insert` range is going to be merged with both neighbors.
289    /// * `Ok(false, false)` if `to_insert` range is going to be inserted as a new HEAD range (without merging).
290    ///
291    /// [`Store::insert`]: crate::store::Store::insert
292    pub fn check_insertion_constraints(
293        &self,
294        to_insert: impl Borrow<BlockRange>,
295    ) -> Result<(bool, bool)> {
296        let to_insert = to_insert.borrow();
297        to_insert.validate()?;
298
299        let Some(head_range) = self.0.last() else {
300            // Allow insersion on empty store.
301            return Ok((false, false));
302        };
303
304        if head_range.left_of(to_insert) {
305            // Allow adding a new HEAD
306            let prev_exists = head_range.is_adjacent(to_insert);
307            return Ok((prev_exists, false));
308        }
309
310        let Some((first_idx, last_idx)) = self.find_affected_ranges(to_insert) else {
311            return Err(BlockRangesError::NoAdjacentNeighbors(to_insert.to_owned()));
312        };
313
314        let first = &self.0[first_idx];
315        let last = &self.0[last_idx];
316        let num_of_ranges = last_idx - first_idx + 1;
317
318        match num_of_ranges {
319            0 => unreachable!(),
320            1 => {
321                if first.is_overlapping(to_insert) {
322                    Err(BlockRangesError::BlockRangeOverlap(
323                        to_insert.to_owned(),
324                        calc_overlap(to_insert, first, last),
325                    ))
326                } else if first.left_of(to_insert) {
327                    Ok((true, false))
328                } else {
329                    Ok((false, true))
330                }
331            }
332            2 => {
333                if first.is_adjacent(to_insert) && last.is_adjacent(to_insert) {
334                    Ok((true, true))
335                } else {
336                    Err(BlockRangesError::BlockRangeOverlap(
337                        to_insert.to_owned(),
338                        calc_overlap(to_insert, first, last),
339                    ))
340                }
341            }
342            _ => Err(BlockRangesError::BlockRangeOverlap(
343                to_insert.to_owned(),
344                calc_overlap(to_insert, first, last),
345            )),
346        }
347    }
348
349    /// Returns the head height and removes it from the ranges.
350    pub fn pop_head(&mut self) -> Option<u64> {
351        let last = self.0.last_mut()?;
352        let head = *last.end();
353
354        if last.len() == 1 {
355            self.0.remove(self.0.len() - 1);
356        } else {
357            *last = *last.start()..=*last.end() - 1;
358        }
359
360        Some(head)
361    }
362
363    /// Returns the tail (lowest) height and removes it from the ranges.
364    pub fn pop_tail(&mut self) -> Option<u64> {
365        let first = self.0.first_mut()?;
366        let tail = *first.start();
367
368        if first.len() == 1 {
369            self.0.remove(0);
370        } else {
371            *first = *first.start() + 1..=*first.end();
372        }
373
374        Some(tail)
375    }
376
377    /// Insert a new range.
378    ///
379    /// This fails only if `range` is not valid. It allows inserting an overlapping range.
380    pub fn insert_relaxed(&mut self, range: impl Borrow<BlockRange>) -> Result<()> {
381        let range = range.borrow();
382        range.validate()?;
383
384        match self.find_affected_ranges(range) {
385            // `range` must be merged with other ranges
386            Some((start_idx, end_idx)) => {
387                let start = *self.0[start_idx].start().min(range.start());
388                let end = *self.0[end_idx].end().max(range.end());
389
390                self.0.drain(start_idx..=end_idx);
391                self.0.insert(start_idx, start..=end);
392            }
393            // `range` can not be merged with other ranges
394            None => {
395                for (i, r) in self.0.iter().enumerate() {
396                    if range.end() < r.start() {
397                        self.0.insert(i, range.to_owned());
398                        return Ok(());
399                    }
400                }
401
402                self.0.push(range.to_owned());
403            }
404        }
405
406        Ok(())
407    }
408
409    /// Remove a range.
410    ///
411    /// This fails only if `range` is not valid. It allows removing non-existing range.
412    pub fn remove_relaxed(&mut self, range: impl Borrow<BlockRange>) -> Result<()> {
413        let range = range.borrow();
414        range.validate()?;
415
416        let Some((start_idx, end_idx)) = self.find_affected_ranges(range) else {
417            // Nothing to remove
418            return Ok(());
419        };
420
421        // Remove old ranges
422        let old_ranges = self
423            .0
424            .drain(start_idx..=end_idx)
425            .collect::<SmallVec<[_; 2]>>();
426
427        // ranges:       |-----|  |----|  |----|
428        // remove:           |--------------|
429        // after remove: |---|              |--|
430        let first_range = old_ranges.first().expect("non empty");
431        let last_range = old_ranges.last().expect("non empty");
432
433        if range.end() < last_range.end() {
434            // Add the right range
435            self.0
436                .insert(start_idx, *range.end() + 1..=*last_range.end());
437        }
438
439        if first_range.start() < range.start() {
440            // Add the left range
441            self.0
442                .insert(start_idx, *first_range.start()..=*range.start() - 1);
443        }
444
445        Ok(())
446    }
447}
448
449impl AsRef<[RangeInclusive<u64>]> for BlockRanges {
450    fn as_ref(&self) -> &[RangeInclusive<u64>] {
451        &self.0
452    }
453}
454
455impl Add for BlockRanges {
456    type Output = Self;
457
458    fn add(self, rhs: Self) -> Self::Output {
459        self.add(&rhs)
460    }
461}
462
463impl Add<&BlockRanges> for BlockRanges {
464    type Output = Self;
465
466    fn add(mut self, rhs: &BlockRanges) -> Self::Output {
467        for range in rhs.0.iter() {
468            self.insert_relaxed(range)
469                .expect("BlockRanges always holds valid ranges");
470        }
471        self
472    }
473}
474
475impl Sub for BlockRanges {
476    type Output = Self;
477
478    fn sub(self, rhs: Self) -> Self::Output {
479        self.sub(&rhs)
480    }
481}
482
483impl Sub<&BlockRanges> for BlockRanges {
484    type Output = Self;
485
486    fn sub(mut self, rhs: &BlockRanges) -> Self::Output {
487        for range in rhs.0.iter() {
488            self.remove_relaxed(range)
489                .expect("BlockRanges always holds valid ranges");
490        }
491        self
492    }
493}
494
495impl Iterator for BlockRanges {
496    type Item = u64;
497
498    fn next(&mut self) -> Option<Self::Item> {
499        self.pop_tail()
500    }
501}
502
503impl DoubleEndedIterator for BlockRanges {
504    fn next_back(&mut self) -> Option<Self::Item> {
505        self.pop_head()
506    }
507}
508
509impl Display for BlockRanges {
510    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
511        write!(f, "[")?;
512        for (idx, range) in self.0.iter().enumerate() {
513            if idx == 0 {
514                write!(f, "{}", range.display())?;
515            } else {
516                write!(f, ", {}", range.display())?;
517            }
518        }
519        write!(f, "]")
520    }
521}
522
523fn calc_overlap(
524    to_insert: &BlockRange,
525    first_range: &BlockRange,
526    last_range: &BlockRange,
527) -> BlockRange {
528    let start = first_range.start().max(to_insert.start());
529    let end = last_range.end().min(to_insert.end());
530    *start..=*end
531}
532
533#[cfg(test)]
534mod tests {
535    use super::*;
536
537    use crate::test_utils::new_block_ranges;
538
539    #[test]
540    fn range_len() {
541        assert_eq!((0u64..=0).len(), 1);
542        assert_eq!((0u64..=5).len(), 6);
543        assert_eq!((1u64..=2).len(), 2);
544        assert_eq!(RangeInclusive::new(2u64, 1).len(), 0);
545        assert_eq!((10001u64..=20000).len(), 10000);
546    }
547
548    #[test]
549    fn block_ranges_empty() {
550        assert!(new_block_ranges([]).is_empty());
551        assert!(!new_block_ranges([1..=3]).is_empty());
552    }
553
554    #[test]
555    fn block_ranges_head() {
556        assert_eq!(new_block_ranges([]).head(), None);
557        assert_eq!(new_block_ranges([1..=3]).head(), Some(3));
558        assert_eq!(new_block_ranges([1..=3, 6..=9]).head(), Some(9));
559        assert_eq!(new_block_ranges([1..=3, 5..=5, 8..=9]).head(), Some(9));
560    }
561
562    #[test]
563    fn block_ranges_tail() {
564        assert_eq!(new_block_ranges([]).tail(), None);
565        assert_eq!(new_block_ranges([1..=3]).tail(), Some(1));
566        assert_eq!(new_block_ranges([1..=3, 6..=9]).tail(), Some(1));
567        assert_eq!(new_block_ranges([1..=3, 5..=5, 8..=9]).tail(), Some(1));
568    }
569
570    #[test]
571    fn check_range_insert_append() {
572        let (prev_exists, next_exists) = new_block_ranges([])
573            .check_insertion_constraints(1..=5)
574            .unwrap();
575        assert!(!prev_exists);
576        assert!(!next_exists);
577
578        let (prev_exists, next_exists) = new_block_ranges([1..=4])
579            .check_insertion_constraints(5..=5)
580            .unwrap();
581        assert!(prev_exists);
582        assert!(!next_exists);
583
584        let (prev_exists, next_exists) = new_block_ranges([1..=5])
585            .check_insertion_constraints(6..=9)
586            .unwrap();
587        assert!(prev_exists);
588        assert!(!next_exists);
589
590        let (prev_exists, next_exists) = new_block_ranges([6..=8])
591            .check_insertion_constraints(2..=5)
592            .unwrap();
593        assert!(!prev_exists);
594        assert!(next_exists);
595
596        // Allow inserting a new HEAD range
597        let (prev_exists, next_exists) = new_block_ranges([1..=5])
598            .check_insertion_constraints(7..=9)
599            .unwrap();
600        assert!(!prev_exists);
601        assert!(!next_exists);
602    }
603
604    #[test]
605    fn check_range_insert_with_consolidation() {
606        let (prev_exists, next_exists) = new_block_ranges([1..=3, 6..=9])
607            .check_insertion_constraints(4..=5)
608            .unwrap();
609        assert!(prev_exists);
610        assert!(next_exists);
611
612        let (prev_exists, next_exists) = new_block_ranges([1..=2, 5..=5, 8..=9])
613            .check_insertion_constraints(3..=4)
614            .unwrap();
615        assert!(prev_exists);
616        assert!(next_exists);
617
618        let (prev_exists, next_exists) = new_block_ranges([1..=2, 4..=4, 8..=9])
619            .check_insertion_constraints(5..=7)
620            .unwrap();
621        assert!(prev_exists);
622        assert!(next_exists);
623    }
624
625    #[test]
626    fn check_range_insert_overlapping() {
627        let result = new_block_ranges([1..=2])
628            .check_insertion_constraints(1..=1)
629            .unwrap_err();
630        assert_eq!(result, BlockRangesError::BlockRangeOverlap(1..=1, 1..=1));
631
632        let result = new_block_ranges([1..=2])
633            .check_insertion_constraints(2..=2)
634            .unwrap_err();
635        assert_eq!(result, BlockRangesError::BlockRangeOverlap(2..=2, 2..=2));
636
637        let result = new_block_ranges([1..=4])
638            .check_insertion_constraints(2..=8)
639            .unwrap_err();
640        assert_eq!(result, BlockRangesError::BlockRangeOverlap(2..=8, 2..=4));
641
642        let result = new_block_ranges([1..=4])
643            .check_insertion_constraints(2..=3)
644            .unwrap_err();
645        assert_eq!(result, BlockRangesError::BlockRangeOverlap(2..=3, 2..=3));
646
647        let result = new_block_ranges([5..=9])
648            .check_insertion_constraints(1..=5)
649            .unwrap_err();
650        assert_eq!(result, BlockRangesError::BlockRangeOverlap(1..=5, 5..=5));
651
652        let result = new_block_ranges([5..=8])
653            .check_insertion_constraints(2..=8)
654            .unwrap_err();
655        assert_eq!(result, BlockRangesError::BlockRangeOverlap(2..=8, 5..=8));
656
657        let result = new_block_ranges([1..=3, 6..=9])
658            .check_insertion_constraints(3..=6)
659            .unwrap_err();
660        assert_eq!(result, BlockRangesError::BlockRangeOverlap(3..=6, 3..=6));
661
662        let result = new_block_ranges([1..=3, 5..=6])
663            .check_insertion_constraints(3..=9)
664            .unwrap_err();
665        assert_eq!(result, BlockRangesError::BlockRangeOverlap(3..=9, 3..=6));
666
667        let result = new_block_ranges([2..=3, 5..=6])
668            .check_insertion_constraints(1..=5)
669            .unwrap_err();
670        assert_eq!(result, BlockRangesError::BlockRangeOverlap(1..=5, 2..=5));
671    }
672
673    #[test]
674    fn check_range_insert_invalid_placement() {
675        let result = new_block_ranges([1..=2, 7..=9])
676            .check_insertion_constraints(4..=4)
677            .unwrap_err();
678        assert_eq!(result, BlockRangesError::NoAdjacentNeighbors(4..=4));
679
680        let result = new_block_ranges([1..=2, 8..=9])
681            .check_insertion_constraints(4..=6)
682            .unwrap_err();
683        assert_eq!(result, BlockRangesError::NoAdjacentNeighbors(4..=6));
684
685        let result = new_block_ranges([4..=5, 7..=8])
686            .check_insertion_constraints(1..=2)
687            .unwrap_err();
688        assert_eq!(result, BlockRangesError::NoAdjacentNeighbors(1..=2));
689    }
690
691    #[test]
692    fn test_header_range_creation_ok() {
693        new_block_ranges([1..=3, 5..=8]);
694        new_block_ranges([]);
695        new_block_ranges([1..=1, 1000000..=2000000]);
696    }
697
698    #[test]
699    #[should_panic]
700    fn test_header_range_creation_overlap() {
701        new_block_ranges([1..=3, 2..=5]);
702    }
703
704    #[test]
705    #[should_panic]
706    fn test_header_range_creation_inverse() {
707        new_block_ranges([1..=3, RangeInclusive::new(9, 5)]);
708    }
709
710    #[test]
711    #[should_panic]
712    fn test_header_range_creation_wrong_order() {
713        new_block_ranges([10..=15, 1..=5]);
714    }
715
716    #[test]
717    fn pop_head() {
718        let mut ranges = new_block_ranges([]);
719        assert_eq!(ranges.pop_head(), None);
720
721        let mut ranges = new_block_ranges([1..=4, 6..=8, 10..=10]);
722        assert_eq!(ranges.pop_head(), Some(10));
723        assert_eq!(ranges.pop_head(), Some(8));
724        assert_eq!(ranges.pop_head(), Some(7));
725        assert_eq!(ranges.pop_head(), Some(6));
726        assert_eq!(ranges.pop_head(), Some(4));
727        assert_eq!(ranges.pop_head(), Some(3));
728        assert_eq!(ranges.pop_head(), Some(2));
729        assert_eq!(ranges.pop_head(), Some(1));
730        assert_eq!(ranges.pop_head(), None);
731    }
732
733    #[test]
734    fn pop_tail() {
735        let mut ranges = new_block_ranges([]);
736        assert_eq!(ranges.pop_tail(), None);
737
738        let mut ranges = new_block_ranges([1..=4, 6..=8, 10..=10]);
739        assert_eq!(ranges.pop_tail(), Some(1));
740        assert_eq!(ranges.pop_tail(), Some(2));
741        assert_eq!(ranges.pop_tail(), Some(3));
742        assert_eq!(ranges.pop_tail(), Some(4));
743        assert_eq!(ranges.pop_tail(), Some(6));
744        assert_eq!(ranges.pop_tail(), Some(7));
745        assert_eq!(ranges.pop_tail(), Some(8));
746        assert_eq!(ranges.pop_tail(), Some(10));
747        assert_eq!(ranges.pop_tail(), None);
748    }
749
750    #[test]
751    fn block_ranges_iterator() {
752        let ranges = new_block_ranges([1..=5, 10..=15]);
753        let heights: Vec<_> = ranges.collect();
754        assert_eq!(heights, vec![1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15]);
755
756        let empty_heights: Vec<u64> = new_block_ranges([]).collect();
757        assert_eq!(empty_heights, Vec::<u64>::new())
758    }
759
760    #[test]
761    fn block_ranges_double_ended_iterator() {
762        let ranges = new_block_ranges([1..=5, 10..=15]);
763        let heights: Vec<_> = ranges.rev().collect();
764        assert_eq!(heights, vec![15, 14, 13, 12, 11, 10, 5, 4, 3, 2, 1]);
765
766        let empty_heights: Vec<u64> = new_block_ranges([]).collect();
767        assert_eq!(empty_heights, Vec::<u64>::new())
768    }
769
770    #[test]
771    fn validate_check() {
772        (1..=1).validate().unwrap();
773        (1..=2).validate().unwrap();
774        (0..=0).validate().unwrap_err();
775        (0..=1).validate().unwrap_err();
776        #[allow(clippy::reversed_empty_ranges)]
777        (2..=1).validate().unwrap_err();
778    }
779
780    #[test]
781    fn adjacent_check() {
782        assert!((3..=5).is_adjacent(&(1..=2)));
783        assert!((3..=5).is_adjacent(&(6..=8)));
784
785        assert!(!(3..=5).is_adjacent(&(1..=1)));
786        assert!(!(3..=5).is_adjacent(&(7..=8)));
787    }
788
789    #[test]
790    fn overlapping_check() {
791        // equal
792        assert!((3..=5).is_overlapping(&(3..=5)));
793
794        // partial set
795        assert!((3..=5).is_overlapping(&(1..=4)));
796        assert!((3..=5).is_overlapping(&(1..=3)));
797        assert!((3..=5).is_overlapping(&(4..=8)));
798        assert!((3..=5).is_overlapping(&(5..=8)));
799
800        // subset
801        assert!((3..=5).is_overlapping(&(4..=4)));
802        assert!((3..=5).is_overlapping(&(3..=4)));
803        assert!((3..=5).is_overlapping(&(4..=5)));
804
805        // superset
806        assert!((3..=5).is_overlapping(&(1..=5)));
807        assert!((3..=5).is_overlapping(&(1..=6)));
808        assert!((3..=5).is_overlapping(&(3..=6)));
809        assert!((3..=5).is_overlapping(&(4..=6)));
810
811        // not overlapping
812        assert!(!(3..=5).is_overlapping(&(1..=1)));
813        assert!(!(3..=5).is_overlapping(&(7..=8)));
814    }
815
816    #[test]
817    fn left_of_check() {
818        // range is on the left of
819        assert!((1..=2).left_of(&(3..=4)));
820        assert!((1..=1).left_of(&(3..=4)));
821
822        // range is on the right of
823        assert!(!(3..=4).left_of(&(1..=2)));
824        assert!(!(3..=4).left_of(&(1..=1)));
825
826        // overlapping is not accepted
827        assert!(!(1..=3).left_of(&(3..=4)));
828        assert!(!(1..=5).left_of(&(3..=4)));
829        assert!(!(3..=4).left_of(&(1..=3)));
830    }
831
832    #[test]
833    fn truncate_left() {
834        assert_eq!((1..=10).truncate_left(u64::MAX), 1..=10);
835        assert_eq!((1..=10).truncate_left(20), 1..=10);
836        assert_eq!((1..=10).truncate_left(10), 1..=10);
837        assert_eq!((1..=10).truncate_left(5), 6..=10);
838        assert_eq!((1..=10).truncate_left(1), 10..=10);
839        assert!((1..=10).truncate_left(0).is_empty());
840
841        assert_eq!((0..=u64::MAX).truncate_left(u64::MAX), 1..=u64::MAX);
842        assert_eq!((0..=u64::MAX).truncate_left(1), u64::MAX..=u64::MAX);
843        assert!((0..=u64::MAX).truncate_left(0).is_empty());
844    }
845
846    #[test]
847    fn truncate_right() {
848        assert_eq!((1..=10).truncate_right(20), 1..=10);
849        assert_eq!((1..=10).truncate_right(10), 1..=10);
850        assert_eq!((1..=10).truncate_right(5), 1..=5);
851        assert_eq!((1..=10).truncate_right(1), 1..=1);
852        assert!((1..=10).truncate_right(0).is_empty());
853
854        assert_eq!((0..=u64::MAX).truncate_right(u64::MAX), 0..=(u64::MAX - 1));
855        assert_eq!((0..=u64::MAX).truncate_right(1), 0..=0);
856        assert!((0..=u64::MAX).truncate_right(0).is_empty());
857    }
858
859    #[test]
860    fn find_affected_ranges() {
861        let ranges = new_block_ranges([30..=50, 80..=100, 130..=150]);
862
863        assert_eq!(ranges.find_affected_ranges(28..=28), None);
864        assert_eq!(ranges.find_affected_ranges(1..=15), None);
865        assert_eq!(ranges.find_affected_ranges(1..=28), None);
866        assert_eq!(ranges.find_affected_ranges(3..=28), None);
867        assert_eq!(ranges.find_affected_ranges(1..=29), Some((0, 0)));
868        assert_eq!(ranges.find_affected_ranges(1..=30), Some((0, 0)));
869        assert_eq!(ranges.find_affected_ranges(1..=49), Some((0, 0)));
870        assert_eq!(ranges.find_affected_ranges(1..=50), Some((0, 0)));
871        assert_eq!(ranges.find_affected_ranges(1..=51), Some((0, 0)));
872
873        assert_eq!(ranges.find_affected_ranges(40..=51), Some((0, 0)));
874        assert_eq!(ranges.find_affected_ranges(50..=51), Some((0, 0)));
875        assert_eq!(ranges.find_affected_ranges(51..=51), Some((0, 0)));
876
877        assert_eq!(ranges.find_affected_ranges(40..=79), Some((0, 1)));
878        assert_eq!(ranges.find_affected_ranges(50..=79), Some((0, 1)));
879        assert_eq!(ranges.find_affected_ranges(51..=79), Some((0, 1)));
880        assert_eq!(ranges.find_affected_ranges(50..=80), Some((0, 1)));
881
882        assert_eq!(ranges.find_affected_ranges(52..=52), None);
883        assert_eq!(ranges.find_affected_ranges(52..=78), None);
884        assert_eq!(ranges.find_affected_ranges(52..=79), Some((1, 1)));
885        assert_eq!(ranges.find_affected_ranges(52..=80), Some((1, 1)));
886        assert_eq!(ranges.find_affected_ranges(52..=129), Some((1, 2)));
887        assert_eq!(ranges.find_affected_ranges(99..=129), Some((1, 2)));
888        assert_eq!(ranges.find_affected_ranges(100..=129), Some((1, 2)));
889        assert_eq!(ranges.find_affected_ranges(101..=129), Some((1, 2)));
890        assert_eq!(ranges.find_affected_ranges(101..=128), Some((1, 1)));
891        assert_eq!(ranges.find_affected_ranges(51..=129), Some((0, 2)));
892
893        assert_eq!(ranges.find_affected_ranges(102..=128), None);
894        assert_eq!(ranges.find_affected_ranges(102..=120), None);
895        assert_eq!(ranges.find_affected_ranges(120..=128), None);
896
897        assert_eq!(ranges.find_affected_ranges(40..=129), Some((0, 2)));
898        assert_eq!(ranges.find_affected_ranges(40..=140), Some((0, 2)));
899        assert_eq!(ranges.find_affected_ranges(20..=140), Some((0, 2)));
900        assert_eq!(ranges.find_affected_ranges(20..=150), Some((0, 2)));
901        assert_eq!(ranges.find_affected_ranges(20..=151), Some((0, 2)));
902        assert_eq!(ranges.find_affected_ranges(20..=160), Some((0, 2)));
903
904        assert_eq!(ranges.find_affected_ranges(120..=129), Some((2, 2)));
905        assert_eq!(ranges.find_affected_ranges(120..=128), None);
906        assert_eq!(ranges.find_affected_ranges(120..=130), Some((2, 2)));
907        assert_eq!(ranges.find_affected_ranges(120..=131), Some((2, 2)));
908        assert_eq!(ranges.find_affected_ranges(140..=145), Some((2, 2)));
909        assert_eq!(ranges.find_affected_ranges(140..=150), Some((2, 2)));
910        assert_eq!(ranges.find_affected_ranges(140..=155), Some((2, 2)));
911        assert_eq!(ranges.find_affected_ranges(152..=155), None);
912        assert_eq!(ranges.find_affected_ranges(152..=178), None);
913        assert_eq!(ranges.find_affected_ranges(152..=152), None);
914
915        assert_eq!(new_block_ranges([]).find_affected_ranges(1..=1), None);
916
917        assert_eq!(new_block_ranges([1..=2]).find_affected_ranges(6..=9), None);
918        assert_eq!(new_block_ranges([4..=8]).find_affected_ranges(1..=2), None);
919        assert_eq!(
920            new_block_ranges([4..=8, 20..=30]).find_affected_ranges(1..=2),
921            None
922        );
923        assert_eq!(
924            new_block_ranges([4..=8, 20..=30]).find_affected_ranges(10..=12),
925            None
926        );
927        assert_eq!(
928            new_block_ranges([4..=8, 20..=30]).find_affected_ranges(32..=32),
929            None
930        );
931    }
932
933    #[test]
934    fn insert_relaxed_disjoined() {
935        let mut r = BlockRanges::default();
936        r.insert_relaxed(10..=10).unwrap();
937        assert_eq!(&r.0[..], &[10..=10][..]);
938
939        let ranges = new_block_ranges([30..=50, 80..=100, 130..=150]);
940
941        let mut r = ranges.clone();
942        r.insert_relaxed(1..=1).unwrap();
943        assert_eq!(&r.0[..], &[1..=1, 30..=50, 80..=100, 130..=150][..]);
944
945        let mut r = ranges.clone();
946        r.insert_relaxed(1..=28).unwrap();
947        assert_eq!(&r.0[..], &[1..=28, 30..=50, 80..=100, 130..=150][..]);
948
949        let mut r = ranges.clone();
950        r.insert_relaxed(10..=28).unwrap();
951        assert_eq!(&r.0[..], &[10..=28, 30..=50, 80..=100, 130..=150][..]);
952
953        let mut r = ranges.clone();
954        r.insert_relaxed(52..=78).unwrap();
955        assert_eq!(&r.0[..], &[30..=50, 52..=78, 80..=100, 130..=150][..]);
956
957        let mut r = ranges.clone();
958        r.insert_relaxed(102..=128).unwrap();
959        assert_eq!(&r.0[..], &[30..=50, 80..=100, 102..=128, 130..=150][..]);
960
961        let mut r = ranges.clone();
962        r.insert_relaxed(152..=152).unwrap();
963        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=150, 152..=152][..]);
964
965        let mut r = ranges.clone();
966        r.insert_relaxed(152..=170).unwrap();
967        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=150, 152..=170][..]);
968
969        let mut r = ranges.clone();
970        r.insert_relaxed(160..=170).unwrap();
971        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=150, 160..=170][..]);
972    }
973
974    #[test]
975    fn insert_relaxed_intersected() {
976        let ranges = new_block_ranges([30..=50, 80..=100, 130..=150]);
977
978        let mut r = ranges.clone();
979        r.insert_relaxed(29..=29).unwrap();
980        assert_eq!(&r.0[..], &[29..=50, 80..=100, 130..=150][..]);
981
982        let mut r = ranges.clone();
983        r.insert_relaxed(1..=29).unwrap();
984        assert_eq!(&r.0[..], &[1..=50, 80..=100, 130..=150][..]);
985
986        let mut r = ranges.clone();
987        r.insert_relaxed(29..=35).unwrap();
988        assert_eq!(&r.0[..], &[29..=50, 80..=100, 130..=150][..]);
989
990        let mut r = ranges.clone();
991        r.insert_relaxed(29..=55).unwrap();
992        assert_eq!(&r.0[..], &[29..=55, 80..=100, 130..=150][..]);
993
994        let mut r = ranges.clone();
995        r.insert_relaxed(29..=78).unwrap();
996        assert_eq!(&r.0[..], &[29..=78, 80..=100, 130..=150][..]);
997
998        let mut r = ranges.clone();
999        r.insert_relaxed(29..=79).unwrap();
1000        assert_eq!(&r.0[..], &[29..=100, 130..=150][..]);
1001
1002        let mut r = ranges.clone();
1003        r.insert_relaxed(30..=79).unwrap();
1004        assert_eq!(&r.0[..], &[30..=100, 130..=150][..]);
1005
1006        let mut r = ranges.clone();
1007        r.insert_relaxed(30..=150).unwrap();
1008        assert_eq!(&r.0[..], &[30..=150][..]);
1009
1010        let mut r = ranges.clone();
1011        r.insert_relaxed(10..=170).unwrap();
1012        assert_eq!(&r.0[..], &[10..=170][..]);
1013
1014        let mut r = ranges.clone();
1015        r.insert_relaxed(85..=129).unwrap();
1016        assert_eq!(&r.0[..], &[30..=50, 80..=150][..]);
1017
1018        let mut r = ranges.clone();
1019        r.insert_relaxed(85..=129).unwrap();
1020        assert_eq!(&r.0[..], &[30..=50, 80..=150][..]);
1021
1022        let mut r = ranges.clone();
1023        r.insert_relaxed(135..=170).unwrap();
1024        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=170][..]);
1025
1026        let mut r = ranges.clone();
1027        r.insert_relaxed(151..=170).unwrap();
1028        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=170][..]);
1029
1030        let mut r = new_block_ranges([1..=2, 4..=6, 8..=10, 15..=20, 80..=100]);
1031        r.insert_relaxed(3..=79).unwrap();
1032        assert_eq!(&r.0[..], &[1..=100][..]);
1033    }
1034
1035    #[test]
1036    fn remove_relaxed() {
1037        let ranges = new_block_ranges([30..=50, 80..=100, 130..=150]);
1038
1039        let mut r = ranges.clone();
1040        r.remove_relaxed(29..=29).unwrap();
1041        assert_eq!(&r.0[..], &[30..=50, 80..=100, 130..=150][..]);
1042
1043        let mut r = ranges.clone();
1044        r.remove_relaxed(30..=30).unwrap();
1045        assert_eq!(&r.0[..], &[31..=50, 80..=100, 130..=150][..]);
1046
1047        let mut r = ranges.clone();
1048        r.remove_relaxed(20..=40).unwrap();
1049        assert_eq!(&r.0[..], &[41..=50, 80..=100, 130..=150][..]);
1050
1051        let mut r = ranges.clone();
1052        r.remove_relaxed(35..=40).unwrap();
1053        assert_eq!(&r.0[..], &[30..=34, 41..=50, 80..=100, 130..=150][..]);
1054
1055        let mut r = ranges.clone();
1056        r.remove_relaxed(51..=129).unwrap();
1057        assert_eq!(&r.0[..], &[30..=50, 130..=150][..]);
1058
1059        let mut r = ranges.clone();
1060        r.remove_relaxed(50..=130).unwrap();
1061        assert_eq!(&r.0[..], &[30..=49, 131..=150][..]);
1062
1063        let mut r = ranges.clone();
1064        r.remove_relaxed(35..=49).unwrap();
1065        assert_eq!(&r.0[..], &[30..=34, 50..=50, 80..=100, 130..=150][..]);
1066
1067        let mut r = ranges.clone();
1068        r.remove_relaxed(35..=50).unwrap();
1069        assert_eq!(&r.0[..], &[30..=34, 80..=100, 130..=150][..]);
1070
1071        let mut r = ranges.clone();
1072        r.remove_relaxed(35..=55).unwrap();
1073        assert_eq!(&r.0[..], &[30..=34, 80..=100, 130..=150][..]);
1074
1075        let mut r = ranges.clone();
1076        r.remove_relaxed(35..=135).unwrap();
1077        assert_eq!(&r.0[..], &[30..=34, 136..=150][..]);
1078
1079        let mut r = ranges.clone();
1080        r.remove_relaxed(35..=170).unwrap();
1081        assert_eq!(&r.0[..], &[30..=34][..]);
1082
1083        let mut r = ranges.clone();
1084        r.remove_relaxed(10..=135).unwrap();
1085        assert_eq!(&r.0[..], &[136..=150][..]);
1086
1087        let mut r = ranges.clone();
1088        r.remove_relaxed(10..=170).unwrap();
1089        assert!(r.0.is_empty());
1090
1091        let mut r = new_block_ranges([1..=10, 12..=12, 14..=14]);
1092        r.remove_relaxed(12..=12).unwrap();
1093        assert_eq!(&r.0[..], &[1..=10, 14..=14][..]);
1094
1095        let mut r = new_block_ranges([1..=u64::MAX]);
1096        r.remove_relaxed(12..=12).unwrap();
1097        assert_eq!(&r.0[..], &[1..=11, 13..=u64::MAX][..]);
1098
1099        let mut r = new_block_ranges([1..=u64::MAX]);
1100        r.remove_relaxed(1..=1).unwrap();
1101        assert_eq!(&r.0[..], &[2..=u64::MAX][..]);
1102
1103        let mut r = new_block_ranges([1..=u64::MAX]);
1104        r.remove_relaxed(u64::MAX..=u64::MAX).unwrap();
1105        assert_eq!(&r.0[..], &[1..=u64::MAX - 1][..]);
1106    }
1107}
lumina_node/block_ranges.rs

lumina_node/
block_ranges.rs
