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;
6use core::mem::MaybeUninit;
7
8use error::Error;
9pub use safety_boundary::ArrayVec;
10
11/// Limits the scope of `unsafe` auditing.
12// New trait impls and fns that don't need to access internals should go below the module, not
13// inside it!
14mod safety_boundary {
15    use core::mem::MaybeUninit;
16
17    /// A growable contiguous collection backed by array.
18    #[derive(Copy)]
19    pub struct ArrayVec<T: Copy, const CAP: usize> {
20        len: usize,
21        data: [MaybeUninit<T>; CAP],
22    }
23
24    impl<T: Copy, const CAP: usize> ArrayVec<T, CAP> {
25        /// Constructs an empty `ArrayVec`.
26        #[must_use]
27        pub const fn new() -> Self { Self { len: 0, data: [MaybeUninit::uninit(); CAP] } }
28
29        /// Constructs a new `ArrayVec` initialized with the contents of `slice`.
30        ///
31        /// # Panics
32        ///
33        /// If the slice is longer than `CAP`.
34        pub const fn from_slice(slice: &[T]) -> Self {
35            assert!(slice.len() <= CAP);
36            let mut data = [MaybeUninit::uninit(); CAP];
37            let mut i = 0;
38            // can't use mutable references and operators in const
39            while i < slice.len() {
40                data[i] = MaybeUninit::new(slice[i]);
41                i += 1;
42            }
43
44            Self { len: slice.len(), data }
45        }
46
47        /// Returns a reference to the underlying data.
48        pub const fn as_slice(&self) -> &[T] {
49            // transmute needed; see https://github.com/rust-lang/rust/issues/63569
50            // SAFETY: self.len is chosen such that everything is initialized up to len,
51            //  and MaybeUninit<T> has the same representation as T.
52            let ptr = self.data.as_ptr().cast::<T>();
53            unsafe { core::slice::from_raw_parts(ptr, self.len) }
54        }
55
56        /// Returns a mutable reference to the underlying data.
57        pub fn as_mut_slice(&mut self) -> &mut [T] {
58            // SAFETY: self.len is chosen such that everything is initialized up to len,
59            //  and MaybeUninit<T> has the same representation as T.
60            let ptr = self.data.as_mut_ptr().cast::<T>();
61            unsafe { core::slice::from_raw_parts_mut(ptr, self.len) }
62        }
63
64        /// Returns remaining spare capacity of the vector as a slice of `MaybeUninit<T>`.
65        pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
66            // SOUNDNESS: self.len <= CAP is the invariant on the type
67            unsafe { self.data.get_unchecked_mut(self.len..) }
68        }
69
70        /// Forces the length to `new_len`.
71        ///
72        /// # Safety
73        ///
74        /// * `new_len` must be less than or equal to `CAP`.
75        /// * All elements up to `new_len` must be initialized.
76        pub unsafe fn set_len(&mut self, new_len: usize) {
77            debug_assert!(new_len <= CAP);
78            self.len = new_len;
79        }
80    }
81}
82
83impl<T: Copy, const CAP: usize> ArrayVec<T, CAP> {
84    /// Adds an element into `self`.
85    ///
86    /// # Panics
87    ///
88    /// If the length would increase past CAP.
89    #[track_caller]
90    pub fn push(&mut self, element: T) {
91        self.try_push(element).expect("push past the capacity of the array");
92    }
93
94    /// Adds an element into `self`.
95    ///
96    /// # Errors
97    ///
98    /// Returns `CapacityExceeded` if the `ArrayVec` is full.
99    pub fn try_push(&mut self, element: T) -> Result<(), Error> {
100        let first = self.spare_capacity_mut().first_mut().ok_or(Error::CapacityExceeded(CAP))?;
101        *first = MaybeUninit::new(element);
102        let old_len = self.len();
103        // SOUNDNESS:
104        // * first being non-None implies the element exists therefore one-past the length <=
105        //   CAP
106        // * all elements up to old_len were already filled and we just added one
107        unsafe {
108            self.set_len(old_len + 1);
109        }
110        Ok(())
111    }
112
113    /// Removes the last element, returning it.
114    ///
115    /// # Returns
116    ///
117    /// None if the `ArrayVec` is empty.
118    pub fn pop(&mut self) -> Option<T> {
119        let res = *self.last()?;
120        let old_len = self.len();
121        // SOUNDNESS:
122        // * decreasing the already-valid len keeps the len <= CAP invariant
123        // * decreasing the already-valid len does not mark any new elements as initialized
124        unsafe { self.set_len(old_len - 1) }
125        Some(res)
126    }
127
128    /// Copies and appends all elements from `slice` into `self`.
129    ///
130    /// # Panics
131    ///
132    /// If the length would increase past CAP.
133    pub fn extend_from_slice(&mut self, slice: &[T]) {
134        // SAFETY: MaybeUninit<T> has the same layout as T
135        let slice = unsafe {
136            let ptr = slice.as_ptr();
137            core::slice::from_raw_parts(ptr.cast::<MaybeUninit<T>>(), slice.len())
138        };
139        self.spare_capacity_mut()
140            .get_mut(..slice.len())
141            .expect("buffer overflow")
142            .copy_from_slice(slice);
143        let old_len = self.len();
144        unsafe { self.set_len(old_len + slice.len()) }
145    }
146}
147
148impl<T: Copy, const CAP: usize> Default for ArrayVec<T, CAP> {
149    fn default() -> Self { Self::new() }
150}
151
152/// Clones the value *faster* than using `Copy`.
153///
154/// Because we avoid copying the uninitialized part of the array this copies the value faster than
155/// memcpy.
156#[allow(clippy::non_canonical_clone_impl)]
157#[allow(clippy::expl_impl_clone_on_copy)]
158impl<T: Copy, const CAP: usize> Clone for ArrayVec<T, CAP> {
159    fn clone(&self) -> Self { Self::from_slice(self) }
160}
161
162impl<T: Copy, const CAP: usize> core::ops::Deref for ArrayVec<T, CAP> {
163    type Target = [T];
164
165    fn deref(&self) -> &Self::Target { self.as_slice() }
166}
167
168impl<T: Copy, const CAP: usize> core::ops::DerefMut for ArrayVec<T, CAP> {
169    fn deref_mut(&mut self) -> &mut Self::Target { self.as_mut_slice() }
170}
171
172impl<T: Copy + Eq, const CAP: usize> Eq for ArrayVec<T, CAP> {}
173
174impl<T: Copy + PartialEq, const CAP1: usize, const CAP2: usize> PartialEq<ArrayVec<T, CAP2>>
175    for ArrayVec<T, CAP1>
176{
177    fn eq(&self, other: &ArrayVec<T, CAP2>) -> bool { **self == **other }
178}
179
180impl<T: Copy + PartialEq, const CAP: usize> PartialEq<[T]> for ArrayVec<T, CAP> {
181    fn eq(&self, other: &[T]) -> bool { **self == *other }
182}
183
184impl<T: Copy + PartialEq, const CAP: usize> PartialEq<ArrayVec<T, CAP>> for [T] {
185    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
186}
187
188impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<[T; LEN]>
189    for ArrayVec<T, CAP>
190{
191    fn eq(&self, other: &[T; LEN]) -> bool { **self == *other }
192}
193
194impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<ArrayVec<T, CAP>>
195    for [T; LEN]
196{
197    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
198}
199
200impl<T: Copy + Ord, const CAP: usize> Ord for ArrayVec<T, CAP> {
201    fn cmp(&self, other: &Self) -> core::cmp::Ordering { (**self).cmp(&**other) }
202}
203
204impl<T: Copy + PartialOrd, const CAP1: usize, const CAP2: usize> PartialOrd<ArrayVec<T, CAP2>>
205    for ArrayVec<T, CAP1>
206{
207    fn partial_cmp(&self, other: &ArrayVec<T, CAP2>) -> Option<core::cmp::Ordering> {
208        (**self).partial_cmp(&**other)
209    }
210}
211
212impl<T: Copy + fmt::Debug, const CAP: usize> fmt::Debug for ArrayVec<T, CAP> {
213    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { fmt::Debug::fmt(&**self, f) }
214}
215
216impl<T: Copy + core::hash::Hash, const CAP: usize> core::hash::Hash for ArrayVec<T, CAP> {
217    fn hash<H: core::hash::Hasher>(&self, state: &mut H) { core::hash::Hash::hash(&**self, state); }
218}
219
220/// Error types for `ArrayVec`.
221pub mod error {
222    use core::fmt;
223
224    /// Errors encountered when inserting or removing elements from an `ArrayVec`.
225    #[derive(Copy, Clone, Debug, PartialEq, Eq)]
226    pub enum Error {
227        /// Attempting to push additional element beyond the `ArrayVec`'s capacity.
228        CapacityExceeded(usize),
229    }
230
231    impl fmt::Display for Error {
232        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
233            match self {
234                Self::CapacityExceeded(cap) => write!(f, "Capacity exceeded: {}", cap),
235            }
236        }
237    }
238
239    #[cfg(feature = "std")]
240    impl std::error::Error for Error {
241        fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
242            match self {
243                Self::CapacityExceeded(_) => None,
244            }
245        }
246    }
247}
248
249#[cfg(feature = "serde")]
250impl<T: Copy + crate::serde::Serialize, const CAP: usize> crate::serde::Serialize
251    for ArrayVec<T, CAP>
252{
253    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
254    where
255        S: crate::serde::Serializer,
256    {
257        serializer.collect_seq(self.iter())
258    }
259}
260
261#[cfg(feature = "serde")]
262impl<'de, T, const CAP: usize> crate::serde::Deserialize<'de> for ArrayVec<T, CAP>
263where
264    T: Copy + crate::serde::Deserialize<'de>,
265{
266    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
267    where
268        D: serde::Deserializer<'de>,
269    {
270        use core::marker::PhantomData;
271
272        use crate::serde::de;
273
274        struct Visitor<T, const CAP: usize>(PhantomData<T>);
275
276        impl<'de, T, const CAP: usize> de::Visitor<'de> for Visitor<T, CAP>
277        where
278            T: Copy + crate::serde::Deserialize<'de>,
279        {
280            type Value = ArrayVec<T, CAP>;
281
282            fn expecting(&self, f: &mut fmt::Formatter) -> fmt::Result {
283                write!(f, "a sequence of at most {} elements", CAP)
284            }
285
286            fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
287            where
288                A: de::SeqAccess<'de>,
289            {
290                use de::Error;
291
292                if let Some(hint) = seq.size_hint() {
293                    if hint > CAP {
294                        return Err(Error::invalid_length(hint, &self));
295                    }
296                }
297
298                let mut out = ArrayVec::<T, CAP>::new();
299                while let Some(elem) = seq.next_element::<T>()? {
300                    out.try_push(elem).map_err(|_| Error::invalid_length(out.len() + 1, &self))?;
301                }
302                Ok(out)
303            }
304        }
305        deserializer.deserialize_seq(Visitor::<T, CAP>(PhantomData))
306    }
307}
308
309#[cfg(test)]
310mod tests {
311    use super::ArrayVec;
312
313    #[test]
314    fn arrayvec_ops() {
315        let mut av = ArrayVec::<_, 1>::new();
316        assert!(av.is_empty());
317        av.push(42);
318        assert_eq!(av.len(), 1);
319        assert_eq!(av, [42]);
320    }
321
322    #[test]
323    #[should_panic(expected = "push past the capacity of the array")]
324    fn overflow_push() {
325        let mut av = ArrayVec::<_, 0>::new();
326        av.push(42);
327    }
328
329    #[test]
330    #[should_panic(expected = "buffer overflow")]
331    fn overflow_extend() {
332        let mut av = ArrayVec::<_, 0>::new();
333        av.extend_from_slice(&[42]);
334    }
335
336    #[test]
337    fn extend_from_slice() {
338        let mut av = ArrayVec::<u8, 8>::new();
339        av.extend_from_slice(b"abc");
340    }
341
342    #[cfg(feature = "serde")]
343    #[test]
344    fn serde_round_trip_u8() {
345        let mut want = ArrayVec::<u8, 8>::new();
346        want.extend_from_slice(b"abc");
347
348        let json = serde_json::to_string(&want).expect("serde_json failed to encode");
349        let got: ArrayVec<u8, 8> =
350            serde_json::from_str(&json).expect("serde_json failed to decode");
351        assert_eq!(got, want);
352
353        let bin = bincode::serialize(&want).expect("bincode failed to encode");
354        let got: ArrayVec<u8, 8> = bincode::deserialize(&bin).expect("bincode failed to decode");
355        assert_eq!(got, want);
356    }
357
358    #[cfg(feature = "serde")]
359    #[test]
360    fn serde_round_trip_u32() {
361        let mut want = ArrayVec::<u32, 4>::new();
362        (1..=3).for_each(|i| want.push(i));
363
364        let json = serde_json::to_string(&want).expect("serde_json failed to encode");
365        let got: ArrayVec<u32, 4> =
366            serde_json::from_str(&json).expect("serde_json failed to decode");
367        assert_eq!(got, want);
368
369        let bin = bincode::serialize(&want).expect("bincode failed to encode");
370        let got: ArrayVec<u32, 4> = bincode::deserialize(&bin).expect("bincode failed to decode");
371        assert_eq!(got, want);
372    }
373
374    #[cfg(feature = "serde")]
375    #[test]
376    fn serde_round_trip_empty() {
377        let want = ArrayVec::<u8, 0>::new();
378
379        let json = serde_json::to_string(&want).expect("serde_json failed to encode");
380        assert_eq!(json, "[]");
381        let got: ArrayVec<u8, 0> =
382            serde_json::from_str(&json).expect("serde_json failed to decode");
383        assert_eq!(got, want);
384    }
385
386    #[cfg(feature = "serde")]
387    #[test]
388    fn serde_deserialize_overflow_json_returns_error() {
389        // CAP=2 but JSON contains 3 elements -> must error, not panic.
390        // Excercises the read-until-overflow path (no usable size_hint).
391        let json = "[1,2,3]";
392        let res: Result<ArrayVec<u8, 2>, _> = serde_json::from_str(json);
393        assert!(res.is_err(), "expected an error for over-capacity input");
394    }
395
396    #[cfg(feature = "serde")]
397    #[test]
398    fn serde_deserialize_overflow_bincode_returns_error() {
399        // Exercises the size_hint > CAP fast-reject path; bincode prefixes the
400        // sequence with a length, which becomes the sze_hint on deserialize.
401        let slice: &[u8] = &[1, 2, 3];
402        let bin = bincode::serialize(slice).expect("bincode failed to encode");
403        let res: Result<ArrayVec<u8, 2>, _> = bincode::deserialize(&bin);
404        assert!(res.is_err(), "expected an error for over-capacity input");
405    }
406
407    #[cfg(feature = "serde")]
408    #[test]
409    fn serde_matches_vec_wire_format() {
410        // Verifies the on-the-wire encoding is identical to `Vec<T>`/`&[T]` so
411        // that an `ArrayVec<T, CAP>` is interchangeable with `Vec<T>` in serde.
412        let slice: &[u8] = &[1, 2, 3];
413        let want = ArrayVec::<u8, 8>::from_slice(slice);
414
415        // JSON
416        let av_json = serde_json::to_string(&want).expect("serde_json failed to encode");
417        let slice_json = serde_json::to_string(slice).expect("serde_json failed to encode");
418        assert_eq!(av_json, slice_json);
419
420        // Bincode.
421        let av_bin = bincode::serialize(&want).expect("bincode failed to encode");
422        let slice_bin = bincode::serialize(slice).expect("bincode failed to encode");
423        assert_eq!(av_bin, slice_bin);
424
425        // Deserialize the slice-encoded bytes into ArrayVec.
426        let got: ArrayVec<u8, 8> =
427            serde_json::from_str(&slice_json).expect("serde_json failed to decode");
428        assert_eq!(got, want);
429
430        let got: ArrayVec<u8, 8> =
431            bincode::deserialize(&slice_bin).expect("bincode failed to decode");
432        assert_eq!(got, want);
433    }
434}
435
436#[cfg(kani)]
437mod verification {
438    use super::*;
439
440    #[kani::unwind(16)] // One greater than 15 (max number of elements).
441    #[kani::proof]
442    fn no_out_of_bounds_less_than_cap() {
443        const CAP: usize = 32;
444        let n = kani::any::<u32>();
445        let elements = (n & 0x0F) as usize; // Just use 4 bits.
446
447        let val = kani::any::<u32>();
448
449        let mut v = ArrayVec::<u32, CAP>::new();
450        for _ in 0..elements {
451            v.push(val);
452        }
453
454        for i in 0..elements {
455            assert_eq!(v[i], val);
456        }
457    }
458
459    #[kani::unwind(16)] // One greater than 15.
460    #[kani::proof]
461    fn no_out_of_bounds_upto_cap() {
462        const CAP: usize = 15;
463        let elements = CAP;
464
465        let val = kani::any::<u32>();
466
467        let mut v = ArrayVec::<u32, CAP>::new();
468        for _ in 0..elements {
469            v.push(val);
470        }
471
472        for i in 0..elements {
473            assert_eq!(v[i], val);
474        }
475    }
476}
bitcoin_internals/array_vec.rs

bitcoin_internals/
array_vec.rs
