mithril_common/entities/
block_range.rs

1use std::{
2    cmp::Ordering,
3    fmt::{Display, Formatter, Result},
4    ops::{Deref, Range, RangeInclusive},
5};
6
7use anyhow::anyhow;
8use serde::{Deserialize, Serialize};
9
10use crate::{
11    StdResult,
12    crypto_helper::{MKMapKey, MKTreeNode},
13    entities::BlockNumber,
14};
15
16/// BlockRangeLength is the length of a block range.
17pub type BlockRangeLength = BlockNumber;
18
19/// BlockRange for the Cardano chain
20#[derive(Serialize, Deserialize, Clone, Eq, PartialEq, Debug, Hash)]
21pub struct BlockRange {
22    inner_range: Range<BlockNumber>,
23}
24
25impl BlockRange {
26    /// The length of the block range
27    /// Important: this value should be updated with extreme care (probably with an era change) in order to avoid signing disruptions.
28    pub const LENGTH: BlockRangeLength = BlockNumber(15);
29
30    /// Get the start of the block range that contains the given block number
31    pub fn start(number: BlockNumber) -> BlockNumber {
32        Self::start_with_length(number, Self::LENGTH)
33    }
34
35    /// Get all [BlockRange] strictly contained in the given interval
36    pub fn all_block_ranges_in(interval: RangeInclusive<BlockNumber>) -> BlockRangesSequence {
37        BlockRangesSequence::new(interval)
38    }
39
40    /// Returns `true` if the given block number is included in, or beyond, this block range.
41    ///
42    /// In other words, the range `[start, end[` is fully covered when `block_number >= end - 1`.
43    ///
44    /// # Examples
45    ///
46    /// ```rust
47    /// # use mithril_common::entities::{BlockNumber, BlockRange};
48    /// let range = BlockRange::from_block_number(BlockNumber(15));
49    ///
50    /// assert!(range.is_fully_covered_at(BlockNumber(29)));
51    /// assert!(range.is_fully_covered_at(BlockNumber(30)));
52    /// assert!(!range.is_fully_covered_at(BlockNumber(28)));
53    /// ```
54    pub fn is_fully_covered_at(&self, block_number: BlockNumber) -> bool {
55        block_number >= self.end - 1
56    }
57
58    /// Create a BlockRange from a block number
59    pub fn from_block_number(number: BlockNumber) -> Self {
60        // Unwrap is safe as the length is always strictly greater than 0
61        Self::from_block_number_and_length(number, Self::LENGTH).unwrap()
62    }
63
64    /// Create a BlockRange from a block number and a range length
65    pub(crate) fn from_block_number_and_length(
66        number: BlockNumber,
67        length: BlockRangeLength,
68    ) -> StdResult<Self> {
69        if length == 0 {
70            return Err(anyhow!(
71                "BlockRange cannot be be computed with a length of 0"
72            ));
73        }
74        let block_range_start = Self::start_with_length(number, length);
75        let block_range_end = block_range_start + length;
76        Ok(Self::from(*block_range_start..*block_range_end))
77    }
78
79    /// Get the start of the block range of given length that contains the given block number
80    fn start_with_length(number: BlockNumber, length: BlockRangeLength) -> BlockNumber {
81        // the formula used to compute the lower bound of the block range is `⌊number / length⌋ * length`
82        // the computation of the floor is done with the integer division `/` of rust
83        (number / length) * length
84    }
85}
86
87impl Display for BlockRange {
88    fn fmt(&self, f: &mut Formatter) -> Result {
89        write!(f, "[{},{}[", self.inner_range.start, self.inner_range.end)
90    }
91}
92
93impl Deref for BlockRange {
94    type Target = Range<BlockNumber>;
95
96    fn deref(&self) -> &Self::Target {
97        &self.inner_range
98    }
99}
100
101impl PartialOrd for BlockRange {
102    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
103        Some(std::cmp::Ord::cmp(self, other))
104    }
105}
106
107impl Ord for BlockRange {
108    fn cmp(&self, other: &Self) -> Ordering {
109        // Order by range start, then by range end
110        match self.inner_range.start.cmp(&other.inner_range.start) {
111            Ordering::Equal => self.inner_range.end.cmp(&other.inner_range.end),
112            order => order,
113        }
114    }
115}
116
117impl From<BlockRange> for Range<BlockNumber> {
118    fn from(value: BlockRange) -> Self {
119        value.inner_range
120    }
121}
122
123impl From<BlockRange> for Range<u64> {
124    fn from(value: BlockRange) -> Self {
125        *value.inner_range.start..*value.inner_range.end
126    }
127}
128
129impl From<Range<u64>> for BlockRange {
130    fn from(other: Range<u64>) -> Self {
131        BlockRange {
132            inner_range: BlockNumber(other.start)..BlockNumber(other.end),
133        }
134    }
135}
136
137impl From<BlockRange> for MKTreeNode {
138    fn from(other: BlockRange) -> Self {
139        let start = other.start.to_string();
140        let end = other.end.to_string();
141        let mut bytes = vec![];
142        bytes.extend_from_slice(start.as_bytes());
143        bytes.extend_from_slice("-".as_bytes());
144        bytes.extend_from_slice(end.as_bytes());
145        MKTreeNode::new(bytes)
146    }
147}
148
149impl MKMapKey for BlockRange {}
150
151/// A continuous iterable sequence of [block ranges][BlockRange].
152///
153/// Yielded block ranges are sized by [BlockRange::LENGTH], and always have
154/// bounds that are multiples of [BlockRange::LENGTH].
155#[derive(Debug, Clone, Eq, PartialEq)]
156pub struct BlockRangesSequence {
157    start: BlockNumber,
158    end: BlockNumber,
159}
160
161impl BlockRangesSequence {
162    /// Build the [BlockRangesSequence] strictly contained in the given interval.
163    ///
164    /// The interval bounds will be corrected to be multiples of [BlockRange::LENGTH].
165    pub fn new(interval: RangeInclusive<BlockNumber>) -> Self {
166        let start = if (*interval.start() % BlockRange::LENGTH) == 0 {
167            *interval.start()
168        } else {
169            BlockRange::start(*interval.start()) + BlockRange::LENGTH
170        };
171        // End is inclusive, so we need to add 1
172        let end = BlockRange::start(*interval.end() + 1);
173
174        if start >= end {
175            Self {
176                start: BlockNumber(0),
177                end: BlockNumber(0),
178            }
179        } else {
180            Self { start, end }
181        }
182    }
183
184    /// Returns the start of the block ranges sequence.
185    pub fn start(&self) -> BlockNumber {
186        self.start
187    }
188
189    /// Returns the end of the block ranges sequence.
190    pub fn end(&self) -> BlockNumber {
191        self.end
192    }
193
194    /// Returns `true` if range is contained in the sequence.
195    pub fn contains(&self, range: &Range<BlockNumber>) -> bool {
196        self.start <= range.start && range.end <= self.end
197    }
198
199    /// Returns `true` if the block ranges sequence contains no elements.
200    pub fn is_empty(&self) -> bool {
201        self.start >= self.end
202    }
203
204    /// Consume `self` into a new Vec
205    pub fn into_vec(self) -> Vec<BlockRange> {
206        self.into_iter().collect()
207    }
208}
209
210impl Iterator for BlockRangesSequence {
211    type Item = BlockRange;
212
213    fn next(&mut self) -> Option<Self::Item> {
214        if BlockRangesSequence::is_empty(self) {
215            return None;
216        }
217
218        let block_range = BlockRange::from_block_number(self.start);
219        self.start = block_range.end;
220        Some(block_range)
221    }
222
223    fn size_hint(&self) -> (usize, Option<usize>) {
224        (*self.start as usize, Some(*self.end as usize))
225    }
226}
227
228impl ExactSizeIterator for BlockRangesSequence {
229    fn len(&self) -> usize {
230        *((self.end - self.start) / BlockRange::LENGTH) as usize
231    }
232}
233
234mod test_extensions {
235    use crate::test::entities_extensions::BlockRangeTestExtension;
236
237    use super::*;
238
239    impl BlockRangeTestExtension for BlockRange {
240        fn new(start: u64, end: u64) -> Self {
241            Self {
242                inner_range: BlockNumber(start)..BlockNumber(end),
243            }
244        }
245
246        fn try_add(&self, other: &BlockRange) -> StdResult<BlockRange> {
247            if self.inner_range.end.max(other.inner_range.end)
248                < self.inner_range.start.min(other.inner_range.start)
249            {
250                return Err(anyhow!(
251                    "BlockRange cannot be added as they don't strictly overlap"
252                ));
253            }
254
255            Ok(Self {
256                inner_range: Range {
257                    start: self.inner_range.start.min(other.inner_range.start),
258                    end: self.inner_range.end.max(other.inner_range.end),
259                },
260            })
261        }
262    }
263}
264
265#[cfg(test)]
266mod tests {
267    use std::ops::Not;
268
269    use crate::test::entities_extensions::BlockRangeTestExtension;
270
271    use super::*;
272
273    #[test]
274    fn test_block_range_contains() {
275        let block_range = BlockRange::new(1, 10);
276
277        assert!(block_range.contains(&BlockNumber(1)));
278        assert!(block_range.contains(&BlockNumber(6)));
279        assert!(block_range.contains(&BlockNumber(9)));
280
281        assert!(block_range.contains(&BlockNumber(0)).not());
282        // The end of the range is exclusive
283        assert!(block_range.contains(&BlockNumber(10)).not());
284    }
285
286    #[test]
287    fn test_block_range_cmp() {
288        assert_eq!(BlockRange::new(1, 10), BlockRange::new(1, 10));
289        assert_ne!(BlockRange::new(1, 10), BlockRange::new(1, 11));
290        assert_ne!(BlockRange::new(1, 10), BlockRange::new(2, 10));
291        assert_ne!(BlockRange::new(1, 11), BlockRange::new(2, 10));
292
293        assert!(BlockRange::new(1, 10) < BlockRange::new(1, 11));
294        assert!(BlockRange::new(1, 10) < BlockRange::new(2, 10));
295        assert!(BlockRange::new(1, 11) < BlockRange::new(2, 10));
296    }
297
298    #[test]
299    fn test_block_range_try_add() {
300        assert_eq!(
301            BlockRange::new(1, 10).try_add(&BlockRange::new(1, 10)).unwrap(),
302            BlockRange::new(1, 10)
303        );
304        assert_eq!(
305            BlockRange::new(1, 10).try_add(&BlockRange::new(1, 11)).unwrap(),
306            BlockRange::new(1, 11)
307        );
308        assert_eq!(
309            BlockRange::new(1, 10).try_add(&BlockRange::new(2, 10)).unwrap(),
310            BlockRange::new(1, 10)
311        );
312    }
313
314    #[test]
315    fn test_block_range_start() {
316        assert_eq!(BlockRange::start(BlockNumber(0)), 0);
317        assert_eq!(BlockRange::start(BlockNumber(1)), 0);
318        assert_eq!(BlockRange::start(BlockNumber(14)), 0);
319        assert_eq!(BlockRange::start(BlockNumber(15)), 15);
320        assert_eq!(BlockRange::start(BlockNumber(16)), 15);
321        assert_eq!(BlockRange::start(BlockNumber(29)), 15);
322    }
323
324    #[test]
325    fn test_block_range_all_block_ranges_in() {
326        assert_eq!(
327            BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(0)).into_vec(),
328            vec![]
329        );
330        assert_eq!(
331            BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(1)).into_vec(),
332            vec![]
333        );
334        assert_eq!(
335            BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(13)).into_vec(),
336            vec![]
337        );
338        assert_eq!(
339            BlockRange::all_block_ranges_in(BlockNumber(1)..=BlockNumber(14)).into_vec(),
340            vec![]
341        );
342        assert_eq!(
343            BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(14)).into_vec(),
344            vec![BlockRange::new(0, 15)]
345        );
346        assert_eq!(
347            BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(15)).into_vec(),
348            vec![BlockRange::new(0, 15)]
349        );
350        assert_eq!(
351            BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(29)).into_vec(),
352            vec![BlockRange::new(15, 30)]
353        );
354        assert_eq!(
355            BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(30)).into_vec(),
356            vec![BlockRange::new(15, 30)]
357        );
358        assert_eq!(
359            BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(60)).into_vec(),
360            vec![
361                BlockRange::new(15, 30),
362                BlockRange::new(30, 45),
363                BlockRange::new(45, 60)
364            ]
365        );
366    }
367
368    #[test]
369    fn test_block_ranges_sequence_is_empty() {
370        assert!(BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(0)).is_empty());
371        assert!(BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(1)).is_empty());
372        assert!(BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(13)).is_empty());
373        assert!(BlockRange::all_block_ranges_in(BlockNumber(1)..=BlockNumber(14)).is_empty());
374        assert!(
375            BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(14))
376                .is_empty()
377                .not()
378        );
379        assert!(
380            BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(15))
381                .is_empty()
382                .not()
383        );
384        assert!(
385            BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(29))
386                .is_empty()
387                .not()
388        );
389        assert!(
390            BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(30))
391                .is_empty()
392                .not()
393        );
394        assert!(
395            BlockRange::all_block_ranges_in(BlockNumber(14)..=BlockNumber(60))
396                .is_empty()
397                .not()
398        );
399    }
400
401    #[test]
402    fn test_block_ranges_sequence_len() {
403        assert_eq!(
404            BlockRange::all_block_ranges_in(BlockNumber(0)..=(BlockRange::LENGTH - 2)).len(),
405            0
406        );
407        assert_eq!(
408            BlockRange::all_block_ranges_in(BlockNumber(0)..=(BlockRange::LENGTH - 1)).len(),
409            1
410        );
411        assert_eq!(
412            BlockRange::all_block_ranges_in(BlockNumber(0)..=(BlockRange::LENGTH * 15)).len(),
413            15
414        );
415    }
416
417    #[test]
418    fn test_block_ranges_sequence_contains() {
419        let block_range = BlockRange::new(15, 30);
420        assert!(
421            BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(14))
422                .contains(&block_range)
423                .not()
424        );
425        assert!(
426            BlockRange::all_block_ranges_in(BlockNumber(30)..=BlockNumber(59))
427                .contains(&block_range)
428                .not()
429        );
430        assert!(
431            BlockRange::all_block_ranges_in(BlockNumber(0)..=BlockNumber(29))
432                .contains(&block_range)
433        );
434        assert!(
435            BlockRange::all_block_ranges_in(BlockNumber(15)..=BlockNumber(29))
436                .contains(&block_range)
437        );
438        assert!(
439            BlockRange::all_block_ranges_in(BlockNumber(15)..=BlockNumber(44))
440                .contains(&block_range)
441        );
442    }
443
444    #[test]
445    fn test_block_range_from_number() {
446        assert_eq!(
447            BlockRange::from_block_number(BlockNumber(0)),
448            BlockRange::new(0, 15)
449        );
450        assert_eq!(
451            BlockRange::from_block_number(BlockNumber(1)),
452            BlockRange::new(0, 15)
453        );
454        assert_eq!(
455            BlockRange::from_block_number(BlockNumber(14)),
456            BlockRange::new(0, 15)
457        );
458        assert_eq!(
459            BlockRange::from_block_number(BlockNumber(15)),
460            BlockRange::new(15, 30)
461        );
462        assert_eq!(
463            BlockRange::from_block_number(BlockNumber(16)),
464            BlockRange::new(15, 30)
465        );
466        assert_eq!(
467            BlockRange::from_block_number(BlockNumber(29)),
468            BlockRange::new(15, 30)
469        );
470    }
471
472    #[test]
473    fn test_block_range_from_number_and_length_with_valid_input() {
474        assert_eq!(
475            BlockRange::from_block_number_and_length(BlockNumber(0), BlockNumber(10)).unwrap(),
476            BlockRange::new(0, 10)
477        );
478        assert_eq!(
479            BlockRange::from_block_number_and_length(BlockNumber(1), BlockNumber(10)).unwrap(),
480            BlockRange::new(0, 10)
481        );
482        assert_eq!(
483            BlockRange::from_block_number_and_length(BlockNumber(9), BlockNumber(10)).unwrap(),
484            BlockRange::new(0, 10)
485        );
486        assert_eq!(
487            BlockRange::from_block_number_and_length(BlockNumber(10), BlockNumber(10)).unwrap(),
488            BlockRange::new(10, 20)
489        );
490        assert_eq!(
491            BlockRange::from_block_number_and_length(BlockNumber(11), BlockNumber(10)).unwrap(),
492            BlockRange::new(10, 20)
493        );
494        assert_eq!(
495            BlockRange::from_block_number_and_length(BlockNumber(19), BlockNumber(10)).unwrap(),
496            BlockRange::new(10, 20)
497        );
498    }
499
500    #[test]
501    fn test_block_range_from_number_and_length_with_invalid_input() {
502        BlockRange::from_block_number_and_length(BlockNumber(10), BlockNumber(0))
503            .expect_err("BlockRange should not be computed with a length of 0");
504    }
505
506    #[test]
507    // allow to specify a range with start > end
508    #[allow(clippy::reversed_empty_ranges)]
509    fn test_building_sequence_with_start_greater_than_end_yield_empty_iterator() {
510        let sequence = BlockRange::all_block_ranges_in(BlockNumber(30)..=BlockNumber(15));
511        assert_eq!(sequence.clone().into_vec(), vec![]);
512        assert!(sequence.is_empty());
513    }
514
515    mod is_fully_covered_at {
516        use super::*;
517
518        #[test]
519        fn returns_false_when_block_number_is_below_range_start() {
520            let block_range = BlockRange::new(15, 30);
521
522            assert!(!block_range.is_fully_covered_at(BlockNumber(0)));
523            assert!(!block_range.is_fully_covered_at(BlockNumber(14)));
524        }
525
526        #[test]
527        fn returns_false_when_block_number_is_inside_the_range_but_before_last_block() {
528            let block_range = BlockRange::new(15, 30);
529
530            assert!(!block_range.is_fully_covered_at(BlockNumber(15)));
531            assert!(!block_range.is_fully_covered_at(BlockNumber(28)));
532        }
533
534        #[test]
535        fn returns_true_when_block_number_reaches_the_last_block_of_the_range() {
536            let block_range = BlockRange::new(15, 30);
537
538            assert!(block_range.is_fully_covered_at(BlockNumber(29)));
539        }
540
541        #[test]
542        fn returns_true_when_block_number_is_after_the_range() {
543            let block_range = BlockRange::new(15, 30);
544
545            assert!(block_range.is_fully_covered_at(BlockNumber(30)));
546            assert!(block_range.is_fully_covered_at(BlockNumber(31)));
547        }
548    }
549}
mithril_common/entities/block_range.rs

mithril_common/entities/
block_range.rs
