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
8pub use error::CapacityExceededError;
9pub use safety_boundary::ArrayVec;
10#[cfg(creusot)]
11use creusot_std::prelude::*;
12
13/// Limits the scope of `unsafe` auditing.
14// New trait impls and fns that don't need to access internals should go below the module, not
15// inside it!
16mod safety_boundary {
17    #[cfg(creusot)]
18    use creusot_std::prelude::*;
19
20    use core::mem::MaybeUninit;
21
22    /// A growable contiguous collection backed by array.
23    #[derive(Copy)]
24    pub struct ArrayVec<T: Copy, const CAP: usize> {
25        len: usize,
26        data: [MaybeUninit<T>; CAP],
27    }
28
29    impl<T: Copy, const CAP: usize> ArrayVec<T, CAP> {
30        /// Constructs an empty `ArrayVec`.
31        #[must_use]
32        pub const fn new() -> Self { Self { len: 0, data: [MaybeUninit::uninit(); CAP] } }
33
34        /// Constructs a new `ArrayVec` initialized with the contents of `slice`.
35        ///
36        /// # Panics
37        ///
38        /// If the slice is longer than `CAP`.
39        #[cfg_attr(creusot, check(ghost))]
40        #[cfg_attr(creusot, requires(slice@.len() <= CAP@))]
41        #[cfg_attr(creusot, ensures(result@ == slice@))]
42        pub const fn from_slice(slice: &[T]) -> Self {
43            assert!(slice.len() <= CAP);
44            let mut data = [MaybeUninit::uninit(); CAP];
45            let mut i = 0;
46            // can't use mutable references and operators in const
47            #[cfg_attr(creusot, invariant(forall<j> j >= 0 && j < i@ ==> data@[j]@ == Some(slice@[j])))]
48            #[cfg_attr(creusot, variant(slice@.len() - i@))]
49            while i < slice.len() {
50                data[i] = MaybeUninit::new(slice[i]);
51                i += 1;
52            }
53
54            Self { len: slice.len(), data }
55        }
56
57        /// Returns a reference to the underlying data.
58        #[cfg_attr(creusot, check(ghost))]
59        #[cfg_attr(creusot, ensures(self@ == result@))]
60        #[cfg_attr(creusot, ensures(result@.len() == self.len_view()))]
61        #[cfg_attr(creusot, ensures(forall<i> i >= 0 && i < self.len_view() ==> self.buf_view()[i]@ == Some((*result)@[i])))]
62        pub const fn as_slice(&self) -> &[T] {
63            // SAFETY: self.len is chosen such that everything is initialized up to len
64            unsafe {
65                if self.len > CAP { core::hint::unreachable_unchecked() }
66                super::slice_assume_init_ref(self.data.split_at(self.len).0)
67            }
68        }
69
70        /// Returns a mutable reference to the underlying data.
71        #[cfg_attr(creusot, check(ghost))]
72        #[cfg_attr(creusot, ensures(result@.len() == self.len_view()))]
73        #[cfg_attr(creusot, ensures((*self)@.len() == (^self)@.len()))]
74        #[cfg_attr(creusot, ensures((*result)@.len() == (^result)@.len()))]
75        #[cfg_attr(creusot, ensures(self@ == result@))]
76        #[cfg_attr(creusot, ensures((^self)@ == (^result)@))]
77        #[cfg_attr(creusot, ensures(forall<i> i >= 0 && i < self.len_view() ==> (*self).buf_view()[i]@ == Some((*result)@[i]) && (^self).buf_view()[i]@ == Some((^result)@[i])))]
78        #[cfg_attr(creusot, ensures(forall<i> i >= self@.len() && i < CAP@ ==> (^self).buf_view()[i] == (*self).buf_view()[i]))]
79        pub fn as_mut_slice(&mut self) -> &mut [T] {
80            // SAFETY: self.len is chosen such that everything is initialized up to len
81            unsafe {
82                if self.len > CAP { core::hint::unreachable_unchecked() }
83                super::slice_assume_init_mut(self.data.split_at_mut(self.len).0)
84            }
85        }
86
87        /// Returns remaining spare capacity of the vector as a slice of `MaybeUninit<T>`.
88        #[cfg_attr(creusot, ensures((^self)@ == (*self)@))]
89        #[cfg_attr(creusot, ensures((*result)@.len() == CAP@ - self@.len()))]
90        #[cfg_attr(creusot, ensures((^result)@.len() == CAP@ - self@.len()))]
91        #[cfg_attr(creusot, ensures(forall<i> i >= 0 && i < CAP@ - self@.len() ==> (*result)[i] == (*self).buf_view()[self@.len() + i]))]
92        #[cfg_attr(creusot, ensures(forall<i> i >= 0 && i < CAP@ - self@.len() ==> (^result)[i] == (^self).buf_view()[self@.len() + i]))]
93        pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
94            // SOUNDNESS: self.len <= CAP is the invariant on the type
95            unsafe { self.data.get_unchecked_mut(self.len..) }
96        }
97
98        /// Forces the length to `new_len`.
99        ///
100        /// # Safety
101        ///
102        /// * `new_len` must be less than or equal to `CAP`.
103        /// * All elements up to `new_len` must be initialized.
104        #[cfg_attr(creusot, requires(new_len <= CAP))]
105        #[cfg_attr(creusot, requires(forall<i> i >= 0 && i < new_len@ ==> match (*self).buf_view()[i]@ { Some(x) => inv(x), None => false }))]
106        #[cfg_attr(creusot, ensures((^self)@.len() == new_len@))]
107        #[cfg_attr(creusot, ensures((^self).buf_view() == (*self).buf_view()))]
108        #[cfg_attr(creusot, ensures((^self).len_view() == new_len@))]
109        pub unsafe fn set_len(&mut self, new_len: usize) {
110            debug_assert!(new_len <= CAP);
111            self.len = new_len;
112        }
113
114        #[cfg(creusot)]
115        #[logic(inline)]
116        #[ensures(inv(self) ==> result.len() == CAP@)]
117        pub fn buf_view(self) -> Seq<MaybeUninit<T>> {
118            self.data.view()
119        }
120
121        #[cfg(creusot)]
122        #[logic]
123        #[ensures(inv(self) ==> result <= CAP@)]
124        pub fn len_view(self) -> Int {
125            self.len.view()
126        }
127    }
128
129    #[cfg(creusot)]
130    impl<T: Copy, const CAP: usize> Invariant for ArrayVec<T, CAP> {
131        #[logic(prophetic, inline)]
132        fn invariant(self) -> bool {
133            pearlite! {
134                self.len <= CAP && forall<i: Int> 0 <= i && i < self.len@ ==> match self.data@[i]@ { Some(x) => inv(x), None => false }
135            }
136        }
137    }
138
139    #[cfg(creusot)]
140    impl<T: Copy, const CAP: usize> View for ArrayVec<T, CAP> {
141        type ViewTy = Seq<T>;
142
143        #[logic(inline)]
144        #[ensures(inv(self) ==> result.len() <= CAP@)]
145        #[ensures(inv(self) ==> forall<i> i >= 0 && i < result.len() ==> self.buf_view()[i]@ == Some(result[i]))]
146        #[ensures(inv(self) ==> result.len() == self.len_view())]
147        fn view(self) -> Self::ViewTy {
148            pearlite! {
149                self.buf_view()
150                    .subsequence(0, self.len@)
151                    .map(|x: MaybeUninit<T>| {
152                        match x@ {
153                            Some(x) => x,
154                            None => creusot_std::logic::any(),
155                        }
156                    })
157            }
158        }
159    }
160
161    #[cfg(creusot)]
162    impl<T: Copy + DeepModel, const CAP: usize> DeepModel for ArrayVec<T, CAP> {
163        type DeepModelTy = Seq<T::DeepModelTy>;
164
165        #[logic(open, inline)]
166        #[ensures(self@.len() == result.len())]
167        #[ensures(forall<i> 0 <= i && i < self@.len() ==> result[i] == self@[i].deep_model())]
168        fn deep_model(self) -> Self::DeepModelTy {
169            pearlite! {
170                self@.map(|x: T| x.deep_model())
171            }
172        }
173    }
174}
175
176// Polyfill because creusot doesn't support pointer casting and we need const, pre-1.93 MSRV, and
177// check(ghost)
178#[cfg_attr(creusot, check(ghost))]
179#[cfg_attr(creusot, requires(forall<i> i >= 0 && i < slice@.len() ==> match slice[i]@ { Some(_) => true, None => false }))]
180#[cfg_attr(creusot, ensures(slice@.len() == result@.len()))]
181#[cfg_attr(creusot, ensures(forall<i> i >= 0 && i < slice@.len() ==> slice@[i]@ == Some(result@[i])))]
182const unsafe fn slice_assume_init_ref<T>(slice: &[MaybeUninit<T>]) -> &[T] {
183    #[cfg(creusot)]
184    {
185        // SAFETY: the caller must guarantee correctness
186        unsafe { slice.assume_init_ref() }
187    }
188    #[cfg(not(creusot))]
189    {
190        // SAFETY: the caller must guarantee correctness and the code is literally the copy of
191        // `assume_init_ref` from std.
192        unsafe { &*(slice as *const [MaybeUninit<T>] as *const [T]) }
193    }
194}
195
196// Same reason as above except here we don't have `const` as it's currently not needed even though
197// we could theoretically have it conditional on sufficiently recent Rust version.
198#[cfg_attr(creusot, check(ghost))]
199#[cfg_attr(creusot, requires(forall<i> 0 <= i && i < slice@.len() ==> (*slice)[i]@ != None))]
200#[cfg_attr(creusot, ensures((*slice)@.len() == (*result)@.len()))]
201#[cfg_attr(creusot, ensures((^slice)@.len() == (^result)@.len()))]
202#[cfg_attr(creusot, ensures((*result)@.len() == (^result)@.len()))]
203#[cfg_attr(creusot, ensures(forall<i> 0 <= i && i < slice@.len() ==> (*slice)[i]@ == Some((*result)[i])))]
204#[cfg_attr(creusot, ensures(forall<i> 0 <= i && i < slice@.len() ==> (^slice)[i]@ == Some((^result)[i])))]
205unsafe fn slice_assume_init_mut<T>(slice: &mut [MaybeUninit<T>]) -> &mut [T] {
206    #[cfg(creusot)]
207    {
208        // SAFETY: the caller must guarantee correctness
209        unsafe { slice.assume_init_mut() }
210    }
211    #[cfg(not(creusot))]
212    {
213        // SAFETY: the caller must guarantee correctness and the code is literally the copy of
214        // `assume_init_mut` from std.
215        unsafe { &mut *(slice as *mut [MaybeUninit<T>] as *mut [T]) }
216    }
217}
218
219// Same reason as above
220#[cfg_attr(creusot, check(ghost))]
221#[cfg_attr(creusot, requires(dest@.len() == src@.len()))]
222#[cfg_attr(creusot, ensures((^dest)@.len() == (*dest)@.len()))]
223#[cfg_attr(creusot, ensures(forall<i> i >= 0 && i < dest@.len() ==> (^dest)@[i]@ == Some(src[i])))]
224fn write_copy_of_slice<T: Copy>(dest: &mut [MaybeUninit<T>], src: &[T]) {
225    #[cfg(creusot)]
226    {
227        dest.write_copy_of_slice(src);
228    }
229    #[cfg(not(creusot))]
230    // We want to use std's code verbatim
231    #[allow(clippy::transmute_ptr_to_ptr)]
232    {
233        // SAFETY: &[T] and &[MaybeUninit<T>] have the same layout
234        let uninit_src: &[MaybeUninit<T>] = unsafe { core::mem::transmute(src) };
235        dest.copy_from_slice(uninit_src);
236    }
237}
238
239impl<T: Copy, const CAP: usize> ArrayVec<T, CAP> {
240    /// Adds an element into `self`.
241    ///
242    /// # Panics
243    ///
244    /// If the length would increase past CAP.
245    #[track_caller]
246    #[cfg_attr(creusot, requires(self@.len() < CAP@))]
247    #[cfg_attr(creusot, ensures((^self)@ == self@.push_back(element)))]
248    pub fn push(&mut self, element: T) {
249        self.try_push(element).expect("push past the capacity of the array");
250    }
251
252    /// Adds an element into `self`.
253    ///
254    /// # Errors
255    ///
256    /// Returns error if the `ArrayVec` is full.
257    #[cfg_attr(creusot, ensures(self@.len() < CAP@ ==> (^self)@ == self@.push_back(element) && result == Ok(())))]
258    #[cfg_attr(creusot, ensures(self@.len() == CAP@ ==> (^self)@ == (*self)@ && match result { Ok(()) => false, Err(_) => true }))]
259    pub fn try_push(&mut self, element: T) -> Result<(), CapacityExceededError> {
260        let first =
261            self.spare_capacity_mut().first_mut().ok_or(CapacityExceededError { capacity: CAP })?;
262        *first = MaybeUninit::new(element);
263        let old_len = self.len();
264        // SOUNDNESS:
265        // * first being non-None implies the element exists therefore one-past the length <=
266        //   CAP
267        // * all elements up to old_len were already filled and we just added one
268        unsafe {
269            self.set_len(old_len + 1);
270        }
271        Ok(())
272    }
273
274    /// Removes the last element, returning it.
275    ///
276    /// # Returns
277    ///
278    /// None if the `ArrayVec` is empty.
279    #[cfg_attr(creusot, ensures(self@.len() == 0 ==> result == None))]
280    #[cfg_attr(creusot, ensures(self@.len() == 0 ==> (^self) == (*self)))]
281    #[cfg_attr(creusot, ensures(self@.len() > 0 ==> result == Some(self@[self@.len() - 1])))]
282    #[cfg_attr(creusot, ensures(self@.len() > 0 ==> (^self)@ == (*self)@.subsequence(0, (*self)@.len() - 1)))]
283    pub fn pop(&mut self) -> Option<T> {
284        let slice = self.as_slice();
285        let res = *slice.last()?;
286        let old_len = slice.len();
287        // SOUNDNESS:
288        // * decreasing the already-valid len keeps the len <= CAP invariant
289        // * decreasing the already-valid len does not mark any new elements as initialized
290        unsafe { self.set_len(old_len - 1) }
291        Some(res)
292    }
293
294    /// Copies and appends all elements from `slice` into `self`.
295    ///
296    /// # Panics
297    ///
298    /// If the length would increase past CAP.
299    #[cfg_attr(creusot, requires(slice@.len() <= CAP@ - self@.len()))]
300    #[cfg_attr(creusot, ensures((^self)@ == (*self)@.concat(slice@)))]
301    pub fn extend_from_slice(&mut self, slice: &[T]) {
302        let dst = self.spare_capacity_mut()
303            .get_mut(..slice.len())
304            .expect("buffer overflow");
305        write_copy_of_slice(dst, slice);
306        let old_len = self.len();
307        unsafe { self.set_len(old_len + slice.len()) }
308    }
309}
310
311impl<T: Copy, const CAP: usize> Default for ArrayVec<T, CAP> {
312    fn default() -> Self { Self::new() }
313}
314
315/// Clones the value *faster* than using `Copy`.
316///
317/// Because we avoid copying the uninitialized part of the array this copies the value faster than
318/// memcpy.
319#[allow(clippy::non_canonical_clone_impl)]
320#[allow(clippy::expl_impl_clone_on_copy)]
321impl<T: Copy, const CAP: usize> Clone for ArrayVec<T, CAP> {
322    #[cfg_attr(creusot, ensures(result@ == self@))]
323    fn clone(&self) -> Self { Self::from_slice(self) }
324}
325
326impl<T: Copy, const CAP: usize> core::ops::Deref for ArrayVec<T, CAP> {
327    type Target = [T];
328
329    #[cfg_attr(creusot, check(ghost))]
330    #[cfg_attr(creusot, ensures(self@ == result@))]
331    #[cfg_attr(creusot, ensures(result@.len() == self.len_view()))]
332    #[cfg_attr(creusot, ensures(forall<i> i >= 0 && i < self.len_view() ==> self.buf_view()[i]@ == Some((*result)@[i])))]
333    fn deref(&self) -> &Self::Target { self.as_slice() }
334}
335
336impl<T: Copy, const CAP: usize> core::ops::DerefMut for ArrayVec<T, CAP> {
337    #[cfg_attr(creusot, check(ghost))]
338    #[cfg_attr(creusot, ensures(result@.len() == self.len_view()))]
339    #[cfg_attr(creusot, ensures((*self)@.len() == (^self)@.len()))]
340    #[cfg_attr(creusot, ensures((*result)@.len() == (^result)@.len()))]
341    #[cfg_attr(creusot, ensures(self@ == result@))]
342    #[cfg_attr(creusot, ensures((^self)@ == (^result)@))]
343    #[cfg_attr(creusot, ensures(forall<i> i >= 0 && i < self.len_view() ==> (*self).buf_view()[i]@ == Some((*result)@[i]) && (^self).buf_view()[i]@ == Some((^result)@[i])))]
344    #[cfg_attr(creusot, ensures(forall<i> i >= self@.len() && i < CAP@ ==> (^self).buf_view()[i] == (*self).buf_view()[i]))]
345    fn deref_mut(&mut self) -> &mut Self::Target { self.as_mut_slice() }
346}
347
348macro_rules! with_deep_model {
349    ($(impl<$param:ident: $bound:ident $(+ $bounds:ident)*, const $cap:ident: usize $(, const $cap2:ident: usize)?> $tr:ident$(<$trait_ty:ty>)? for $ty:ty $(where $wherety:ty: $wheretr:path)? { $($imp:tt)* })*) => {
350        $(
351        #[cfg(creusot)]
352        impl<$param: $bound $(+ $bounds)* + DeepModel, const $cap: usize $(, const $cap2: usize)?> $tr $(<$trait_ty>)? for $ty $(where $wherety: $wheretr)? {
353            $($imp)*
354        }
355
356        #[cfg(not(creusot))]
357        impl<$param: $bound $(+ $bounds)*, const $cap: usize $(, const $cap2: usize)?> $tr$(<$trait_ty>)? for $ty {
358            $($imp)*
359        }
360        )*
361    }
362}
363
364with_deep_model! {
365impl<T: Copy + PartialEq, const CAP: usize> Eq for ArrayVec<T, CAP> {}
366
367impl<T: Copy + PartialEq, const CAP1: usize, const CAP2: usize> PartialEq<ArrayVec<T, CAP2>>
368    for ArrayVec<T, CAP1>
369{
370    #[cfg_attr(creusot, ensures(result == (self.deep_model() == other.deep_model())))]
371    fn eq(&self, other: &ArrayVec<T, CAP2>) -> bool {
372        **self == **other
373    }
374}
375
376impl<T: Copy + PartialEq, const CAP: usize> PartialEq<[T]> for ArrayVec<T, CAP> {
377    #[cfg_attr(creusot, ensures(result == (self.deep_model() == other.deep_model())))]
378    fn eq(&self, other: &[T]) -> bool { **self == *other }
379}
380
381impl<T: Copy + PartialEq, const CAP: usize> PartialEq<ArrayVec<T, CAP>> for [T] {
382    #[cfg_attr(creusot, ensures(result == (self.deep_model() == other.deep_model())))]
383    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
384}
385
386impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<[T; LEN]>
387    for ArrayVec<T, CAP>
388{
389    #[cfg_attr(creusot, ensures(result == (self.deep_model() == other.deep_model())))]
390    fn eq(&self, other: &[T; LEN]) -> bool { other == self }
391}
392
393impl<T: Copy + PartialEq, const CAP: usize, const LEN: usize> PartialEq<ArrayVec<T, CAP>>
394    for [T; LEN]
395{
396    #[cfg_attr(creusot, ensures(result == (self.deep_model() == other.deep_model())))]
397    fn eq(&self, other: &ArrayVec<T, CAP>) -> bool { *self == **other }
398}
399
400impl<T: Copy + Ord, const CAP: usize> Ord for ArrayVec<T, CAP> where T::DeepModelTy: OrdLogic {
401    #[cfg_attr(creusot, ensures(result == (*self).deep_model().cmp_log((*other).deep_model())))]
402    fn cmp(&self, other: &Self) -> core::cmp::Ordering { (**self).cmp(&**other) }
403}
404
405impl<T: Copy + PartialOrd, const CAP1: usize, const CAP2: usize> PartialOrd<ArrayVec<T, CAP2>>
406    for ArrayVec<T, CAP1> where T::DeepModelTy: PartialOrdLogic {
407    #[cfg_attr(creusot, ensures(result == (*self).deep_model().partial_cmp_log((*other).deep_model())))]
408    fn partial_cmp(&self, other: &ArrayVec<T, CAP2>) -> Option<core::cmp::Ordering> {
409        let left = &**self;
410        let right = &**other;
411        #[cfg(creusot)]
412        {
413            // The verifiers struggle to find this on their own.
414            proof_assert!(left.deep_model() == self.deep_model());
415            proof_assert!(other.deep_model() == right.deep_model());
416        }
417        left.partial_cmp(right)
418    }
419}
420}
421
422impl<T: Copy + fmt::Debug, const CAP: usize> fmt::Debug for ArrayVec<T, CAP> {
423    #[cfg_attr(creusot, requires(false))]
424    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { fmt::Debug::fmt(&**self, f) }
425}
426
427impl<T: Copy + core::hash::Hash, const CAP: usize> core::hash::Hash for ArrayVec<T, CAP> {
428    #[cfg_attr(creusot, requires(false))]
429    fn hash<H: core::hash::Hasher>(&self, state: &mut H) { core::hash::Hash::hash(&**self, state); }
430}
431
432/// Error types for `ArrayVec`.
433pub mod error {
434    use core::fmt;
435    #[cfg(creusot)]
436    use creusot_std::prelude::*;
437    #[cfg(creusot)]
438    use creusot_std::prelude::{Clone, PartialEq};
439
440    /// Errors encountered when inserting or removing elements from an `ArrayVec`.
441    #[derive(Copy, Clone, Debug, PartialEq, Eq)]
442    pub struct CapacityExceededError {
443        /// The capacity that was exceeded.
444        pub(super) capacity: usize,
445    }
446
447    impl fmt::Display for CapacityExceededError {
448        #[cfg_attr(creusot, requires(false))]
449        fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
450            write!(f, "Capacity exceeded: {}", self.capacity)
451        }
452    }
453
454    #[cfg(feature = "std")]
455    impl std::error::Error for CapacityExceededError {
456        fn source(&self) -> Option<&(dyn std::error::Error + 'static)> {
457            let Self { capacity: _ } = self;
458            None
459        }
460    }
461
462    #[cfg(creusot)]
463    impl DeepModel for CapacityExceededError {
464        type DeepModelTy = Self;
465
466        #[logic]
467        fn deep_model(self) -> Self::DeepModelTy {
468            self
469        }
470    }
471}
472
473#[cfg(feature = "serde")]
474impl<T: Copy + crate::serde::Serialize, const CAP: usize> crate::serde::Serialize
475    for ArrayVec<T, CAP>
476{
477    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
478    where
479        S: crate::serde::Serializer,
480    {
481        serializer.collect_seq(self.iter())
482    }
483}
484
485#[cfg(feature = "serde")]
486impl<'de, T, const CAP: usize> crate::serde::Deserialize<'de> for ArrayVec<T, CAP>
487where
488    T: Copy + crate::serde::Deserialize<'de>,
489{
490    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
491    where
492        D: serde::Deserializer<'de>,
493    {
494        use core::marker::PhantomData;
495
496        use crate::serde::de;
497
498        struct Visitor<T, const CAP: usize>(PhantomData<T>);
499
500        impl<'de, T, const CAP: usize> de::Visitor<'de> for Visitor<T, CAP>
501        where
502            T: Copy + crate::serde::Deserialize<'de>,
503        {
504            type Value = ArrayVec<T, CAP>;
505
506            fn expecting(&self, f: &mut fmt::Formatter) -> fmt::Result {
507                write!(f, "a sequence of at most {} elements", CAP)
508            }
509
510            fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
511            where
512                A: de::SeqAccess<'de>,
513            {
514                use de::Error;
515
516                if let Some(hint) = seq.size_hint() {
517                    if hint > CAP {
518                        return Err(Error::invalid_length(hint, &self));
519                    }
520                }
521
522                let mut out = ArrayVec::<T, CAP>::new();
523                while let Some(elem) = seq.next_element::<T>()? {
524                    out.try_push(elem).map_err(|_| Error::invalid_length(out.len() + 1, &self))?;
525                }
526                Ok(out)
527            }
528        }
529        deserializer.deserialize_seq(Visitor::<T, CAP>(PhantomData))
530    }
531}
532
533#[cfg(test)]
534mod tests {
535    use super::ArrayVec;
536
537    #[test]
538    fn arrayvec_ops() {
539        let mut av = ArrayVec::<_, 1>::new();
540        assert!(av.is_empty());
541        av.push(42);
542        assert_eq!(av.len(), 1);
543        assert_eq!(av, [42]);
544    }
545
546    #[test]
547    #[should_panic(expected = "push past the capacity of the array")]
548    fn overflow_push() {
549        let mut av = ArrayVec::<_, 0>::new();
550        av.push(42);
551    }
552
553    #[test]
554    #[should_panic(expected = "buffer overflow")]
555    fn overflow_extend() {
556        let mut av = ArrayVec::<_, 0>::new();
557        av.extend_from_slice(&[42]);
558    }
559
560    #[test]
561    fn extend_from_slice() {
562        let mut av = ArrayVec::<u8, 8>::new();
563        av.extend_from_slice(b"abc");
564    }
565
566    #[cfg(feature = "serde")]
567    #[test]
568    fn serde_round_trip_u8() {
569        let mut want = ArrayVec::<u8, 8>::new();
570        want.extend_from_slice(b"abc");
571
572        let json = serde_json::to_string(&want).expect("serde_json failed to encode");
573        let got: ArrayVec<u8, 8> =
574            serde_json::from_str(&json).expect("serde_json failed to decode");
575        assert_eq!(got, want);
576
577        let bin = bincode::serialize(&want).expect("bincode failed to encode");
578        let got: ArrayVec<u8, 8> = bincode::deserialize(&bin).expect("bincode failed to decode");
579        assert_eq!(got, want);
580    }
581
582    #[cfg(feature = "serde")]
583    #[test]
584    fn serde_round_trip_u32() {
585        let mut want = ArrayVec::<u32, 4>::new();
586        (1..=3).for_each(|i| want.push(i));
587
588        let json = serde_json::to_string(&want).expect("serde_json failed to encode");
589        let got: ArrayVec<u32, 4> =
590            serde_json::from_str(&json).expect("serde_json failed to decode");
591        assert_eq!(got, want);
592
593        let bin = bincode::serialize(&want).expect("bincode failed to encode");
594        let got: ArrayVec<u32, 4> = bincode::deserialize(&bin).expect("bincode failed to decode");
595        assert_eq!(got, want);
596    }
597
598    #[cfg(feature = "serde")]
599    #[test]
600    fn serde_round_trip_empty() {
601        let want = ArrayVec::<u8, 0>::new();
602
603        let json = serde_json::to_string(&want).expect("serde_json failed to encode");
604        assert_eq!(json, "[]");
605        let got: ArrayVec<u8, 0> =
606            serde_json::from_str(&json).expect("serde_json failed to decode");
607        assert_eq!(got, want);
608    }
609
610    #[cfg(feature = "serde")]
611    #[test]
612    fn serde_deserialize_overflow_json_returns_error() {
613        // CAP=2 but JSON contains 3 elements -> must error, not panic.
614        // Excercises the read-until-overflow path (no usable size_hint).
615        let json = "[1,2,3]";
616        let res: Result<ArrayVec<u8, 2>, _> = serde_json::from_str(json);
617        assert!(res.is_err(), "expected an error for over-capacity input");
618    }
619
620    #[cfg(feature = "serde")]
621    #[test]
622    fn serde_deserialize_overflow_bincode_returns_error() {
623        // Exercises the size_hint > CAP fast-reject path; bincode prefixes the
624        // sequence with a length, which becomes the sze_hint on deserialize.
625        let slice: &[u8] = &[1, 2, 3];
626        let bin = bincode::serialize(slice).expect("bincode failed to encode");
627        let res: Result<ArrayVec<u8, 2>, _> = bincode::deserialize(&bin);
628        assert!(res.is_err(), "expected an error for over-capacity input");
629    }
630
631    #[cfg(feature = "serde")]
632    #[test]
633    fn serde_matches_vec_wire_format() {
634        // Verifies the on-the-wire encoding is identical to `Vec<T>`/`&[T]` so
635        // that an `ArrayVec<T, CAP>` is interchangeable with `Vec<T>` in serde.
636        let slice: &[u8] = &[1, 2, 3];
637        let want = ArrayVec::<u8, 8>::from_slice(slice);
638
639        // JSON
640        let av_json = serde_json::to_string(&want).expect("serde_json failed to encode");
641        let slice_json = serde_json::to_string(slice).expect("serde_json failed to encode");
642        assert_eq!(av_json, slice_json);
643
644        // Bincode.
645        let av_bin = bincode::serialize(&want).expect("bincode failed to encode");
646        let slice_bin = bincode::serialize(slice).expect("bincode failed to encode");
647        assert_eq!(av_bin, slice_bin);
648
649        // Deserialize the slice-encoded bytes into ArrayVec.
650        let got: ArrayVec<u8, 8> =
651            serde_json::from_str(&slice_json).expect("serde_json failed to decode");
652        assert_eq!(got, want);
653
654        let got: ArrayVec<u8, 8> =
655            bincode::deserialize(&slice_bin).expect("bincode failed to decode");
656        assert_eq!(got, want);
657    }
658}
659
660#[cfg(kani)]
661mod verification {
662    use super::*;
663
664    #[kani::unwind(16)] // One greater than 15 (max number of elements).
665    #[kani::proof]
666    fn no_out_of_bounds_less_than_cap() {
667        const CAP: usize = 32;
668        let n = kani::any::<u32>();
669        let elements = (n & 0x0F) as usize; // Just use 4 bits.
670
671        let val = kani::any::<u32>();
672
673        let mut v = ArrayVec::<u32, CAP>::new();
674        for _ in 0..elements {
675            v.push(val);
676        }
677
678        for i in 0..elements {
679            assert_eq!(v[i], val);
680        }
681    }
682
683    #[kani::unwind(16)] // One greater than 15.
684    #[kani::proof]
685    fn no_out_of_bounds_upto_cap() {
686        const CAP: usize = 15;
687        let elements = CAP;
688
689        let val = kani::any::<u32>();
690
691        let mut v = ArrayVec::<u32, CAP>::new();
692        for _ in 0..elements {
693            v.push(val);
694        }
695
696        for i in 0..elements {
697            assert_eq!(v[i], val);
698        }
699    }
700}
bitcoin_internals/array_vec.rs

bitcoin_internals/
array_vec.rs
