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

tidecoin_internals/
array_vec.rs
