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

mithril_common/entities/
block_range.rs
