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)]
117impl<T: Copy, const CAP: usize> Clone for ArrayVec<T, CAP> {
118    fn clone(&self) -> Self { Self::from_slice(self) }
119}
120
121impl<T: Copy, const CAP: usize> core::ops::Deref for ArrayVec<T, CAP> {
122    type Target = [T];
123
124    fn deref(&self) -> &Self::Target { self.as_slice() }
125}
126
127impl<T: Copy, const CAP: usize> core::ops::DerefMut for ArrayVec<T, CAP> {
128    fn deref_mut(&mut self) -> &mut Self::Target { self.as_mut_slice() }
129}
130
131impl<T: Copy + Eq, const CAP: usize> Eq for ArrayVec<T, CAP> {}
132
133impl<T: Copy + PartialEq, const CAP1: usize, const CAP2: usize> PartialEq<ArrayVec<T, CAP2>>
134    for ArrayVec<T, CAP1>
135{
136    fn eq(&self, other: &ArrayVec<T, CAP2>) -> bool { **self == **other }
137}
138
139impl<T: Copy + PartialEq, const CAP: usize> PartialEq<[T]> for ArrayVec<T, CAP> {
140    fn eq(&self, other: &[T]) -> bool { **self == *other }
141}
142
143impl<T: Copy + PartialEq, const CAP: usize> PartialEq<ArrayVec<T, CAP>> for [T] {
144    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
145}
146
147impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<[T; LEN]>
148    for ArrayVec<T, CAP>
149{
150    fn eq(&self, other: &[T; LEN]) -> bool { **self == *other }
151}
152
153impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<ArrayVec<T, CAP>>
154    for [T; LEN]
155{
156    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
157}
158
159impl<T: Copy + Ord, const CAP: usize> Ord for ArrayVec<T, CAP> {
160    fn cmp(&self, other: &Self) -> core::cmp::Ordering { (**self).cmp(&**other) }
161}
162
163impl<T: Copy + PartialOrd, const CAP1: usize, const CAP2: usize> PartialOrd<ArrayVec<T, CAP2>>
164    for ArrayVec<T, CAP1>
165{
166    fn partial_cmp(&self, other: &ArrayVec<T, CAP2>) -> Option<core::cmp::Ordering> {
167        (**self).partial_cmp(&**other)
168    }
169}
170
171impl<T: Copy + fmt::Debug, const CAP: usize> fmt::Debug for ArrayVec<T, CAP> {
172    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { fmt::Debug::fmt(&**self, f) }
173}
174
175impl<T: Copy + core::hash::Hash, const CAP: usize> core::hash::Hash for ArrayVec<T, CAP> {
176    fn hash<H: core::hash::Hasher>(&self, state: &mut H) { core::hash::Hash::hash(&**self, state) }
177}
178
179#[cfg(test)]
180mod tests {
181    use super::ArrayVec;
182
183    #[test]
184    fn arrayvec_ops() {
185        let mut av = ArrayVec::<_, 1>::new();
186        assert!(av.is_empty());
187        av.push(42);
188        assert_eq!(av.len(), 1);
189        assert_eq!(av, [42]);
190    }
191
192    #[test]
193    #[should_panic]
194    fn overflow_push() {
195        let mut av = ArrayVec::<_, 0>::new();
196        av.push(42);
197    }
198
199    #[test]
200    #[should_panic]
201    fn overflow_extend() {
202        let mut av = ArrayVec::<_, 0>::new();
203        av.extend_from_slice(&[42]);
204    }
205
206    #[test]
207    fn extend_from_slice() {
208        let mut av = ArrayVec::<u8, 8>::new();
209        av.extend_from_slice(b"abc");
210    }
211}
212
213#[cfg(kani)]
214mod verification {
215    use super::*;
216
217    #[kani::unwind(16)] // One greater than 15 (max number of elements).
218    #[kani::proof]
219    fn no_out_of_bounds_less_than_cap() {
220        const CAP: usize = 32;
221        let n = kani::any::<u32>();
222        let elements = (n & 0x0F) as usize; // Just use 4 bits.
223
224        let val = kani::any::<u32>();
225
226        let mut v = ArrayVec::<u32, CAP>::new();
227        for _ in 0..elements {
228            v.push(val);
229        }
230
231        for i in 0..elements {
232            assert_eq!(v[i], val);
233        }
234    }
235
236    #[kani::unwind(16)] // One greater than 15.
237    #[kani::proof]
238    fn no_out_of_bounds_upto_cap() {
239        const CAP: usize = 15;
240        let elements = CAP;
241
242        let val = kani::any::<u32>();
243
244        let mut v = ArrayVec::<u32, CAP>::new();
245        for _ in 0..elements {
246            v.push(val);
247        }
248
249        for i in 0..elements {
250            assert_eq!(v[i], val);
251        }
252    }
253}
bitcoin_internals/array_vec.rs

bitcoin_internals/
array_vec.rs
