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

bitcoin_internals/
array_vec.rs
