bitcoin_internals/
array_vec.rs

1// SPDX-License-Identifier: CC0-1.0
2
3//! A simplified `Copy` version of `arrayvec::ArrayVec`.
4
5use core::fmt;
6
7pub use safety_boundary::ArrayVec;
8
9/// Limits the scope of `unsafe` auditing.
10// New trait impls and fns that don't need to access internals should go below the module, not
11// inside it!
12mod safety_boundary {
13    use core::mem::MaybeUninit;
14
15    /// A growable contiguous collection backed by array.
16    #[derive(Copy)]
17    pub struct ArrayVec<T: Copy, const CAP: usize> {
18        len: usize,
19        data: [MaybeUninit<T>; CAP],
20    }
21
22    impl<T: Copy, const CAP: usize> ArrayVec<T, CAP> {
23        /// Constructs an empty `ArrayVec`.
24        pub const fn new() -> Self { Self { len: 0, data: [MaybeUninit::uninit(); CAP] } }
25
26        /// Constructs a new `ArrayVec` initialized with the contents of `slice`.
27        ///
28        /// # Panics
29        ///
30        /// If the slice is longer than `CAP`.
31        pub const fn from_slice(slice: &[T]) -> Self {
32            assert!(slice.len() <= CAP);
33            let mut data = [MaybeUninit::uninit(); CAP];
34            let mut i = 0;
35            // can't use mutable references and operators in const
36            while i < slice.len() {
37                data[i] = MaybeUninit::new(slice[i]);
38                i += 1;
39            }
40
41            Self { len: slice.len(), data }
42        }
43
44        /// Returns a reference to the underlying data.
45        pub const fn as_slice(&self) -> &[T] {
46            // transmute needed; see https://github.com/rust-lang/rust/issues/63569
47            // SAFETY: self.len is chosen such that everything is initialized up to len,
48            //  and MaybeUninit<T> has the same representation as T.
49            let ptr = self.data.as_ptr().cast::<T>();
50            unsafe { core::slice::from_raw_parts(ptr, self.len) }
51        }
52
53        /// Returns a mutable reference to the underlying data.
54        pub fn as_mut_slice(&mut self) -> &mut [T] {
55            // SAFETY: self.len is chosen such that everything is initialized up to len,
56            //  and MaybeUninit<T> has the same representation as T.
57            let ptr = self.data.as_mut_ptr().cast::<T>();
58            unsafe { core::slice::from_raw_parts_mut(ptr, self.len) }
59        }
60
61        /// Adds an element into `self`.
62        ///
63        /// # Panics
64        ///
65        /// If the length would increase past CAP.
66        pub fn push(&mut self, element: T) {
67            assert!(self.len < CAP);
68            self.data[self.len] = MaybeUninit::new(element);
69            self.len += 1;
70        }
71
72        /// Removes the last element, returning it.
73        ///
74        /// # Returns
75        ///
76        /// None if the `ArrayVec` is empty.
77        pub fn pop(&mut self) -> Option<T> {
78            if self.len > 0 {
79                self.len -= 1;
80                // SAFETY: All elements in 0..len are initialized
81                let res = self.data[self.len];
82                self.data[self.len] = MaybeUninit::uninit();
83                Some(unsafe { res.assume_init() })
84            } else {
85                None
86            }
87        }
88
89        /// Copies and appends all elements from `slice` into `self`.
90        ///
91        /// # Panics
92        ///
93        /// If the length would increase past CAP.
94        pub fn extend_from_slice(&mut self, slice: &[T]) {
95            let new_len = self.len.checked_add(slice.len()).expect("integer/buffer overflow");
96            assert!(new_len <= CAP, "buffer overflow");
97            // SAFETY: MaybeUninit<T> has the same layout as T
98            let slice = unsafe {
99                let ptr = slice.as_ptr();
100                core::slice::from_raw_parts(ptr.cast::<MaybeUninit<T>>(), slice.len())
101            };
102            self.data[self.len..new_len].copy_from_slice(slice);
103            self.len = new_len;
104        }
105    }
106}
107
108impl<T: Copy, const CAP: usize> Default for ArrayVec<T, CAP> {
109    fn default() -> Self { Self::new() }
110}
111
112/// Clones the value *faster* than using `Copy`.
113///
114/// Because we avoid copying the uninitialized part of the array this copies the value faster than
115/// memcpy.
116#[allow(clippy::non_canonical_clone_impl)]
117#[allow(clippy::expl_impl_clone_on_copy)]
118impl<T: Copy, const CAP: usize> Clone for ArrayVec<T, CAP> {
119    fn clone(&self) -> Self { Self::from_slice(self) }
120}
121
122impl<T: Copy, const CAP: usize> core::ops::Deref for ArrayVec<T, CAP> {
123    type Target = [T];
124
125    fn deref(&self) -> &Self::Target { self.as_slice() }
126}
127
128impl<T: Copy, const CAP: usize> core::ops::DerefMut for ArrayVec<T, CAP> {
129    fn deref_mut(&mut self) -> &mut Self::Target { self.as_mut_slice() }
130}
131
132impl<T: Copy + Eq, const CAP: usize> Eq for ArrayVec<T, CAP> {}
133
134impl<T: Copy + PartialEq, const CAP1: usize, const CAP2: usize> PartialEq<ArrayVec<T, CAP2>>
135    for ArrayVec<T, CAP1>
136{
137    fn eq(&self, other: &ArrayVec<T, CAP2>) -> bool { **self == **other }
138}
139
140impl<T: Copy + PartialEq, const CAP: usize> PartialEq<[T]> for ArrayVec<T, CAP> {
141    fn eq(&self, other: &[T]) -> bool { **self == *other }
142}
143
144impl<T: Copy + PartialEq, const CAP: usize> PartialEq<ArrayVec<T, CAP>> for [T] {
145    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
146}
147
148impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<[T; LEN]>
149    for ArrayVec<T, CAP>
150{
151    fn eq(&self, other: &[T; LEN]) -> bool { **self == *other }
152}
153
154impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<ArrayVec<T, CAP>>
155    for [T; LEN]
156{
157    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
158}
159
160impl<T: Copy + Ord, const CAP: usize> Ord for ArrayVec<T, CAP> {
161    fn cmp(&self, other: &Self) -> core::cmp::Ordering { (**self).cmp(&**other) }
162}
163
164impl<T: Copy + PartialOrd, const CAP1: usize, const CAP2: usize> PartialOrd<ArrayVec<T, CAP2>>
165    for ArrayVec<T, CAP1>
166{
167    fn partial_cmp(&self, other: &ArrayVec<T, CAP2>) -> Option<core::cmp::Ordering> {
168        (**self).partial_cmp(&**other)
169    }
170}
171
172impl<T: Copy + fmt::Debug, const CAP: usize> fmt::Debug for ArrayVec<T, CAP> {
173    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { fmt::Debug::fmt(&**self, f) }
174}
175
176impl<T: Copy + core::hash::Hash, const CAP: usize> core::hash::Hash for ArrayVec<T, CAP> {
177    fn hash<H: core::hash::Hasher>(&self, state: &mut H) { core::hash::Hash::hash(&**self, state) }
178}
179
180#[cfg(test)]
181mod tests {
182    use super::ArrayVec;
183
184    #[test]
185    fn arrayvec_ops() {
186        let mut av = ArrayVec::<_, 1>::new();
187        assert!(av.is_empty());
188        av.push(42);
189        assert_eq!(av.len(), 1);
190        assert_eq!(av, [42]);
191    }
192
193    #[test]
194    #[should_panic(expected = "assertion failed")]
195    fn overflow_push() {
196        let mut av = ArrayVec::<_, 0>::new();
197        av.push(42);
198    }
199
200    #[test]
201    #[should_panic(expected = "buffer overflow")]
202    fn overflow_extend() {
203        let mut av = ArrayVec::<_, 0>::new();
204        av.extend_from_slice(&[42]);
205    }
206
207    #[test]
208    fn extend_from_slice() {
209        let mut av = ArrayVec::<u8, 8>::new();
210        av.extend_from_slice(b"abc");
211    }
212}
213
214#[cfg(kani)]
215mod verification {
216    use super::*;
217
218    #[kani::unwind(16)] // One greater than 15 (max number of elements).
219    #[kani::proof]
220    fn no_out_of_bounds_less_than_cap() {
221        const CAP: usize = 32;
222        let n = kani::any::<u32>();
223        let elements = (n & 0x0F) as usize; // Just use 4 bits.
224
225        let val = kani::any::<u32>();
226
227        let mut v = ArrayVec::<u32, CAP>::new();
228        for _ in 0..elements {
229            v.push(val);
230        }
231
232        for i in 0..elements {
233            assert_eq!(v[i], val);
234        }
235    }
236
237    #[kani::unwind(16)] // One greater than 15.
238    #[kani::proof]
239    fn no_out_of_bounds_upto_cap() {
240        const CAP: usize = 15;
241        let elements = CAP;
242
243        let val = kani::any::<u32>();
244
245        let mut v = ArrayVec::<u32, CAP>::new();
246        for _ in 0..elements {
247            v.push(val);
248        }
249
250        for i in 0..elements {
251            assert_eq!(v[i], val);
252        }
253    }
254}
bitcoin_internals/array_vec.rs

bitcoin_internals/
array_vec.rs
