bitcoin_internals/array.rs
1//! Contains extensions related to arrays.
2
3#[cfg(creusot)]
4use creusot_std::prelude::*;
5
6/// Extension trait for arrays.
7pub trait ArrayExt {
8 /// The item type the array is storing.
9 type Item;
10
11 /// How long the array is. Only needed by creusot.
12 #[cfg(creusot)]
13 const ARR_LEN: usize;
14
15 /// Just like the slicing operation, this returns an array `LEN` items long at position
16 /// `OFFSET`.
17 ///
18 /// The correctness of this operation is compile-time checked.
19 ///
20 /// Note that unlike slicing where the second number is the end index, here the second number
21 /// is array length!
22 #[cfg_attr(creusot, requires(OFFSET@ + LEN@ <= Self::ARR_LEN@))]
23 fn sub_array<const OFFSET: usize, const LEN: usize>(&self) -> &[Self::Item; LEN];
24
25 /// Returns an item at given statically-known index.
26 ///
27 /// This is just like normal indexing except the check happens at compile time.
28 #[cfg_attr(creusot, requires(INDEX@ < Self::ARR_LEN@))]
29 fn get_static<const INDEX: usize>(&self) -> &Self::Item { &self.sub_array::<INDEX, 1>()[0] }
30
31 /// Returns the first item in an array.
32 ///
33 /// Fails to compile if the array is empty.
34 ///
35 /// Note that this method's name intentionally shadows the `std`'s `first` method which
36 /// returns `Option`. The rationale is that given the known length of the array, we always know
37 /// that this will not return `None` so trying to keep the `std` method around is pointless.
38 /// Importing the trait will also cause compile failures - that's also intentional to expose
39 /// the places where useless checks are made.
40 #[cfg_attr(creusot, requires(Self::ARR_LEN@ > 0))]
41 fn first(&self) -> &Self::Item { self.get_static::<0>() }
42
43 /// Splits the array into two, non-overlapping smaller arrays covering the entire range.
44 ///
45 /// This is almost equivalent to just calling [`sub_array`](Self::sub_array) twice, except it also
46 /// checks that the arrays don't overlap and that they cover the full range. This is very useful
47 /// for demonstrating correctness, especially when chained. Using this technique even revealed
48 /// a bug in the past. ([#4195](https://github.com/rust-bitcoin/rust-bitcoin/issues/4195))
49 #[cfg_attr(creusot, requires(LEFT@ + RIGHT@ == Self::ARR_LEN@))]
50 fn split_array<const LEFT: usize, const RIGHT: usize>(
51 &self,
52 ) -> (&[Self::Item; LEFT], &[Self::Item; RIGHT]);
53
54 /// Splits the array into the first element and the remaining, one element shorter, array.
55 ///
56 /// Fails to compile if the array is empty.
57 ///
58 /// Note that this method's name intentionally shadows the `std`'s `split_first` method which
59 /// returns `Option`. The rationale is that given the known length of the array, we always know
60 /// that this will not return `None` so trying to keep the `std` method around is pointless.
61 /// Importing the trait will also cause compile failures - that's also intentional to expose
62 /// the places where useless checks are made.
63 #[cfg_attr(creusot, requires(RIGHT@ + 1 == Self::ARR_LEN@))]
64 fn split_first<const RIGHT: usize>(&self) -> (&Self::Item, &[Self::Item; RIGHT]) {
65 let (first, remaining) = self.split_array::<1, RIGHT>();
66 (&first[0], remaining)
67 }
68
69 /// Splits the array into the last element and the remaining, one element shorter, array.
70 ///
71 /// Fails to compile if the array is empty.
72 ///
73 /// Note that this method's name intentionally shadows the `std`'s `split_last` method which
74 /// returns `Option`. The rationale is that given the known length of the array, we always know
75 /// that this will not return `None` so trying to keep the `std` method around is pointless.
76 /// Importing the trait will also cause compile failures - that's also intentional to expose
77 /// the places where useless checks are made.
78 ///
79 /// The returned tuple is also reversed just as `std` for consistency and simpler diffs when
80 /// migrating.
81 #[cfg_attr(creusot, requires(LEFT@ + 1 == Self::ARR_LEN@))]
82 fn split_last<const LEFT: usize>(&self) -> (&Self::Item, &[Self::Item; LEFT]) {
83 let (remaining, last) = self.split_array::<LEFT, 1>();
84 (&last[0], remaining)
85 }
86}
87
88impl<const N: usize, T> ArrayExt for [T; N] {
89 type Item = T;
90
91 #[cfg(creusot)]
92 const ARR_LEN: usize = N;
93
94 #[cfg_attr(creusot, requires(OFFSET@ + LEN@ <= N@))]
95 #[cfg_attr(creusot, ensures(result@ == self@.subsequence(OFFSET@, OFFSET@ + LEN@)))]
96 fn sub_array<const OFFSET: usize, const LEN: usize>(&self) -> &[Self::Item; LEN] {
97 #[allow(clippy::let_unit_value)]
98 let () = Hack::<N, OFFSET, LEN>::IS_VALID_RANGE;
99
100 self.as_slice()[OFFSET..(OFFSET + LEN)]
101 .try_into()
102 .expect("this is also compiler-checked above")
103 }
104
105 #[cfg_attr(creusot, requires(LEFT@ + RIGHT@ == N@))]
106 #[cfg_attr(creusot, ensures(result.0@ == self@.subsequence(0, LEFT@)))]
107 #[cfg_attr(creusot, ensures(result.1@ == self@.subsequence(LEFT@, N@)))]
108 fn split_array<const LEFT: usize, const RIGHT: usize>(
109 &self,
110 ) -> (&[Self::Item; LEFT], &[Self::Item; RIGHT]) {
111 #[allow(clippy::let_unit_value)]
112 let () = Hack2::<N, LEFT, RIGHT>::IS_FULL_RANGE;
113
114 (self.sub_array::<0, LEFT>(), self.sub_array::<LEFT, RIGHT>())
115 }
116}
117
118struct Hack<const N: usize, const OFFSET: usize, const LEN: usize>;
119
120impl<const N: usize, const OFFSET: usize, const LEN: usize> Hack<N, OFFSET, LEN> {
121 const IS_VALID_RANGE: () = assert!(OFFSET + LEN <= N);
122}
123
124struct Hack2<const N: usize, const LEFT: usize, const RIGHT: usize>;
125
126impl<const N: usize, const LEFT: usize, const RIGHT: usize> Hack2<N, LEFT, RIGHT> {
127 const IS_FULL_RANGE: () = assert!(LEFT + RIGHT == N);
128}