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

mithril_common/entities/
block_range.rs
