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

mithril_common/entities/
block_range.rs
