sharky_arrayvec/

lib.rs

#![cfg_attr(all(not(feature = "std"), not(test)), no_std)]
#![cfg_attr(
    feature = "nightly",
    feature(
        const_clone,
        const_trait_impl,
        const_index,
        const_default,
        const_convert,
        const_destruct,
        const_drop_in_place,
        min_specialization,
        const_cmp,
    )
)]
#![cfg_attr(coverage_nightly, feature(coverage_attribute))]

use core::mem;
use core::mem::MaybeUninit;

mod iter;
pub use iter::ArrayVecIter;

#[cfg(feature = "deku")]
pub mod deku;

#[cfg(feature = "nightly")]
mod nightly;

#[cfg(not(feature = "nightly"))]
mod stable;

fn write_filled<T: Clone>(slice: &mut [MaybeUninit<T>], value: T) {
    if slice.is_empty() {
        return;
    }

    let len = slice.len();
    for elem in &mut slice[..len.saturating_sub(1)] {
        elem.write(value.clone());
    }
    slice[len.saturating_sub(1)].write(value);
}

const fn ptr_cast_array<const N: usize, T>(ptr: *const T) -> *const [T; N] {
    ptr.cast()
}

const fn ptr_cast_array_mut<const N: usize, T>(ptr: *mut T) -> *mut [T; N] {
    ptr.cast()
}

/// # Safety
///
/// - `Src` and `Dest` **must** have the same invariants. That is, any valid
///   `Src` must also be a valid `Dest`.
const unsafe fn reinterpret_array_ref<const N: usize, Src, Dest>(src: &[Src; N]) -> &[Dest; N] {
    #[expect(clippy::manual_assert)]
    if size_of::<Src>() != size_of::<Dest>() {
        panic!("Src and Dest have different sizes");
    }

    let src_ptr: *const Src = src.as_ptr();
    let dest_ptr: *const Dest = src_ptr.cast();
    let dest_array_ptr: *const [Dest; N] = ptr_cast_array(dest_ptr);

    // SAFETY: This is always non-null because it's `src`, but with the reference
    // cast. While Src and Dest might not have the same invariants, they are the
    // same size, so there can't be any out-of-bounds accesses.
    unsafe { dest_array_ptr.as_ref_unchecked() }
}

/// # Safety
///
/// - `Src` and `Dest` **must** have the same invariants. That is, any valid
///   `Src` must also be a valid `Dest`.
const unsafe fn reinterpret_array_mut<const N: usize, Src, Dest>(
    src: &mut [Src; N],
) -> &mut [Dest; N] {
    #[expect(clippy::manual_assert)]
    if size_of::<Src>() != size_of::<Dest>() {
        panic!("Src and Dest have different sizes");
    }

    let src_ptr: *mut Src = src.as_mut_ptr();
    let dest_ptr: *mut Dest = src_ptr.cast();
    let dest_array_ptr: *mut [Dest; N] = ptr_cast_array_mut(dest_ptr);

    // SAFETY: This is always non-null because it's `src`, but with the reference
    // cast. While Src and Dest might not have the same invariants, they are the
    // same size, so there can't be any out-of-bounds accesses.
    unsafe { dest_array_ptr.as_mut_unchecked() }
}

// NOTE: This is the stalib's implementation
const fn slice_shift_right<const N: usize, T>(slice: &mut [T], inserted: [T; N]) -> [T; N] {
    if let Some(shift) = slice.len().checked_sub(N) {
        // SAFETY: Having just checked that the inserted/returned arrays are
        // shorter than (or the same length as) the slice:
        // 1. The read for the items to return is in-bounds
        // 2. We can `memmove` the slice over to cover the items we're returning to
        //    ensure those aren't double-dropped
        // 3. Then we write (in-bounds for the same reason as the read) the inserted
        //    items atop the items of the slice that we just duplicated
        //
        // And none of this can panic, so there's no risk of intermediate unwinds.
        unsafe {
            let ptr = slice.as_mut_ptr();
            let returned = ptr_cast_array_mut::<N, _>(ptr.add(shift)).read();
            ptr.add(N).copy_from(ptr, shift);
            ptr_cast_array_mut::<N, _>(ptr).write(inserted);
            returned
        }
    } else {
        // SAFETY: Having checked that the slice is strictly shorter than the
        // inserted/returned arrays, it means we'll be copying the whole slice
        // into the returned array, but that's not enough on its own.  We also
        // need to copy some of the inserted array into the returned array,
        // with the rest going into the slice.  Because `&mut` is exclusive
        // and we own both `inserted` and `returned`, they're all disjoint
        // allocations from each other as we can use `nonoverlapping` copies.
        //
        // We avoid double-frees by `ManuallyDrop`ing the inserted items,
        // since we always copy them to other locations that will drop them
        // instead.  Plus nothing in here can panic -- it's just memcpy three
        // times -- so there's no intermediate unwinds to worry about.
        unsafe {
            let len = slice.len();
            let slice = slice.as_mut_ptr();
            let inserted = mem::ManuallyDrop::new(inserted);
            let inserted = (&raw const inserted).cast::<T>();

            let mut returned = MaybeUninit::<[T; N]>::uninit();
            let ptr = returned.as_mut_ptr().cast::<T>();
            ptr.add(N.wrapping_sub(len))
                .copy_from_nonoverlapping(slice, len);
            ptr.copy_from_nonoverlapping(inserted.add(len), N.wrapping_sub(len));
            slice.copy_from_nonoverlapping(inserted, len);
            returned.assume_init()
        }
    }
}

#[must_use]
pub struct ArrayVec<const C: usize, T> {
    array: [MaybeUninit<T>; C],
    len:   usize,
}

// NOTE: `BoundedVec` must implement `Drop` because "...dropping a
// `MaybeUninit<T>` will never call `T`’s drop code. It is your responsibility
// to make sure `T` gets dropped if it got initialized."
// See <https://doc.rust-lang.org/std/mem/union.MaybeUninit.html#method.new>
impl<const C: usize, T> Drop for ArrayVec<C, T> {
    #[inline]
    fn drop(&mut self) {
        for i in 0..self.len {
            // SAFETY: This is okay because `self.len` tracks the number of initialized
            // values
            unsafe { self.array[i].assume_init_drop() };
        }
    }
}

impl<const C: usize, T: Clone> Clone for ArrayVec<C, T> {
    #[inline]
    fn clone(&self) -> Self {
        let mut array = konst::maybe_uninit::UNINIT_ARRAY::<T, C>::V;
        array[..self.len()].write_clone_of_slice(self.as_slice());

        Self {
            array,
            len: self.len,
        }
    }
}

impl<const C: usize, T: core::fmt::Debug> core::fmt::Debug for ArrayVec<C, T> {
    #[inline]
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        f.debug_list().entries(self.ref_vec().as_slice()).finish()
    }
}

impl<const C: usize, T> ArrayVec<C, T> {
    pub const CAPACITY: usize = C;

    #[inline]
    pub const fn new() -> Self {
        Self {
            array: konst::array::from_fn!(|_| MaybeUninit::uninit()),
            len:   0,
        }
    }

    #[inline]
    pub const fn len(&self) -> usize {
        self.len
    }

    #[inline]
    pub const fn is_empty(&self) -> bool {
        self.len() == 0
    }

    #[inline]
    pub const fn is_full(&self) -> bool {
        self.len() == C
    }

    #[inline]
    pub fn fill_rest(&mut self, item: &T)
    where
        T: Clone, {
        for _ in self.len..C {
            self.push(item.clone());
        }
    }

    #[inline]
    pub fn fill_rest_with(&mut self, mut pred: impl FnMut() -> T)
    where
        T: Clone, {
        for _ in self.len..C {
            self.push(pred());
        }
    }

    #[inline]
    pub const fn as_slice(&self) -> &[T] {
        // SAFETY: every item 0..self.len is initialized.
        unsafe { konst::slice::slice_up_to(&self.array, self.len).assume_init_ref() }
    }

    #[inline]
    pub const fn as_slice_mut(&mut self) -> &mut [T] {
        // SAFETY: every item 0..self.len is initialized.
        unsafe { konst::slice::slice_up_to_mut(&mut self.array, self.len).assume_init_mut() }
    }

    #[inline]
    pub const fn from_array(array: [T; C]) -> Self {
        let array = konst::array::map!(array, MaybeUninit::new);
        Self { array, len: C }
    }

    #[inline]
    pub const fn as_array(&self) -> Option<&[T; C]> {
        if self.is_full() {
            // SAFETY: The array is full (len == capacity); therefore, all the values are
            // initialized and valid.
            Some(unsafe { reinterpret_array_ref(&self.array) })
        } else {
            None
        }
    }

    #[inline]
    pub const fn as_array_mut(&mut self) -> Option<&mut [T; C]> {
        if self.is_full() {
            // SAFETY: The array is full (len == capacity); therefore, all the values are
            // initialized and valid.
            Some(unsafe { reinterpret_array_mut(&mut self.array) })
        } else {
            None
        }
    }

    /// Copy all elements from `slice` into a new [`ArrayVec`].
    ///
    /// Returns [`None`] if `slice` is larger than the capacity.
    #[inline]
    pub fn from_slice(slice: &[T]) -> Option<Self>
    where
        T: Clone, {
        if slice.len() > C {
            return None;
        }

        let mut array = konst::maybe_uninit::UNINIT_ARRAY::<T, C>::V;
        array[..slice.len()].write_clone_of_slice(slice);

        Some(Self {
            array,
            len: slice.len(),
        })
    }

    /// Create a new [`ArrayVec`] containing references to all the values in
    /// this one.
    #[inline]
    pub const fn ref_vec(&self) -> ArrayVec<C, &T> {
        let mut array = konst::maybe_uninit::UNINIT_ARRAY::<&T, C>::V;
        konst::iter::for_each! { (i, elem) in konst::slice::iter(self.as_slice()),enumerate() =>
        // pub const fn iter(&self) -> ArrayVecIter<C, &T> {

        // }

                array[i].write(elem);
            }

        ArrayVec {
            array,
            len: self.len,
        }
    }

    /// Create a new [`ArrayVec`] containing mutable references to all the
    /// values in this one.
    #[inline]
    pub const fn mut_vec(&mut self) -> ArrayVec<C, &mut T> {
        let len = self.len;
        let mut array = konst::maybe_uninit::UNINIT_ARRAY::<&mut T, C>::V;
        konst::iter::for_each! { (i, elem) in konst::slice::iter_mut(self.as_slice_mut()),enumerate() =>
            array[i].write(elem);
        }
        ArrayVec { array, len }
    }

    /// Remove an the final element from the the vector.
    ///
    /// `None` is returned when the vector is empty.
    #[inline]
    pub const fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            return None;
        }

        self.len = self.len.strict_sub(1);

        // SAFETY:
        // - `self.len > 0`; therefore `self.len - 1` is a valid index.
        // - `0..self.len` is initialized
        // - `self.len` is decremented to prevent any reads of the duplicated element.
        let item = unsafe { self.array[self.len].assume_init_read() };
        Some(item)
    }

    /// Add an item to the back of the vector.
    ///
    /// # Panics
    ///
    /// This function panics when:
    ///
    /// 1. The array is full.
    #[inline]
    pub const fn push(&mut self, item: T) {
        assert!(
            self.len < C,
            "Tried to push to a vector without enough capacity."
        );

        // SAFETY:
        // - `self.len < C`; therefore, `self.len` is a valid index.
        // - `0..self.len` are valid elements; therefore, writing to `self.len` doesn't
        //   overwrite any valid and non-dropped elements.
        // - `self.len` is incremented afterwards to prevent double-invocations that
        //   cause missed `Drop`s.
        self.array[self.len].write(item);
        self.len = self.len.strict_add(1);
    }

    /// Add an item to the back of the vector.
    ///
    /// # Returns
    ///
    /// This function returns the provided item as the error variant when:
    ///
    /// - `index` is out of bounds.
    #[inline]
    pub const fn try_push(&mut self, item: T) -> Result<(), T> {
        if self.len >= C {
            return Err(item);
        }

        self.push(item);
        Ok(())
    }

    /// Insert `item` at `index` shifting all the elements on the right by one,
    /// and extend the length to acommodate.
    ///
    /// # Panics
    ///
    /// This function panics when:
    ///
    /// - The array is at it's maximum length.
    #[inline]
    pub const fn insert(&mut self, item: T, index: usize) {
        assert!(self.len < C, "Tried to insert to a full vector.");
        assert!(index <= self.len, "Index out of bounds.");

        // NOTE: it's okay to ignore the result of this because we checked above that
        // there is at least one invalid (thus removable) element at the end
        // (`self.len < C`).
        let _ = slice_shift_right(
            konst::slice::slice_from_mut(&mut self.array, index),
            [MaybeUninit::new(item)],
        );
        self.len = self.len.strict_add(1);
    }

    /// Attempt to insert `item` at `index` shifting all the elements on the
    /// right by one, and extend the length to acommodate.
    ///
    /// # Returns
    ///
    /// This function returns the provided item as the error variant when:
    ///
    /// - The array is full.
    /// - `index` is out of bounds.
    #[inline]
    pub const fn try_insert(&mut self, item: T, index: usize) -> Result<(), T> {
        if self.len >= C || index > self.len {
            return Err(item);
        }
        self.insert(item, index);
        Ok(())
    }

    #[inline]
    pub fn truncate(&mut self, len: usize) {
        if len >= self.len {
            return;
        }

        // SAFETY: These elements can be dropped because everything from `0..self.len`
        // is initialized. The dropped elements will not be accessed again because
        // `self.len` is set to `len`
        unsafe { self.array[len..self.len].assume_init_drop() };
        self.len = len;
    }

    /// Resize so that `len` is equal to `new_len`.
    ///
    /// If `new_len` is greater than `len`, the vec is extended by the
    /// difference with each additional slot filled with `value`. If `new_len`
    /// is less than `len`, the vec is truncated.
    ///
    /// # Panics
    ///
    /// This function panics when:
    ///
    /// 1. `new_len > C`
    #[inline]
    pub fn resize(&mut self, new_len: usize, value: T)
    where
        T: Clone, {
        assert!(new_len <= C, "Tried to resize beyond capacity.");

        if new_len < self.len {
            self.truncate(new_len);
        } else if new_len > self.len {
            write_filled(&mut self.array[self.len..new_len], value);
            self.len = new_len;
        }
    }
}
#[cfg(test)]
#[cfg_attr(coverage_nightly, coverage(off))]
mod tests {
    use super::*;
    use proptest::prelude::*;

    fn proptest_config() -> ProptestConfig {
        ProptestConfig {
            #[cfg(miri)]
            failure_persistence: None,
            #[cfg(miri)]
            cases: 32,
            ..ProptestConfig::default()
        }
    }

    #[test]
    #[expect(clippy::undocumented_unsafe_blocks)]
    fn ptr_cast_array_eq() {
        let x = &[0u8; 4];
        let x_ptr: *const u8 = x.as_ptr();

        let y_ptr: *const [u8; 4] = ptr_cast_array(x_ptr);
        let y = unsafe { y_ptr.as_ref().unwrap() };
        assert_eq!(x, y);
    }

    #[test]
    fn test_ptr_cast_array_mut() {
        let x = &mut [0u8; 4];
        let y_ptr: *mut [u8; 4] = ptr_cast_array_mut(x.as_mut_ptr());

        assert_eq!(x.as_mut_ptr() as usize, y_ptr as usize);
    }

    #[test]
    #[expect(clippy::undocumented_unsafe_blocks)]
    fn test_reinterpret_array_ref() {
        let x = &[0i32];
        let y: &[u32; 1] = unsafe { reinterpret_array_ref(x) };
        assert_eq!(x[0] as u32, y[0]);
    }

    #[test]
    #[should_panic]
    #[expect(clippy::undocumented_unsafe_blocks)]
    fn test_reinterpret_array_ref_unequal_sizes() {
        let x = &[0i32];
        let _y: &[u128; 1] = unsafe { reinterpret_array_ref(x) };
    }

    #[test]
    #[expect(clippy::undocumented_unsafe_blocks)]
    fn test_reinterpret_array_mut() {
        let mut x = [0x1i32];
        let y: &mut [u32; 1] = unsafe { reinterpret_array_mut(&mut x) };
        assert_eq!(0x1, y[0]);
    }

    #[test]
    #[should_panic]
    #[expect(clippy::undocumented_unsafe_blocks)]
    fn test_reinterpret_array_mut_unequal_sizes() {
        let mut x = [0x1i32];
        let _y: &mut [u8; 1] = unsafe { reinterpret_array_mut(&mut x) };
    }

    #[test]
    fn test_write_filled_empty() {
        let mut vec: ArrayVec<0, ()> = ArrayVec::default();
        write_filled(&mut vec.array, ());
        assert!(vec.is_empty());
    }

    #[test]
    fn default() {
        let vec: ArrayVec<4, ()> = ArrayVec::default();
        assert!(vec.is_empty());
    }

    #[test]
    fn drop_empy() {
        let x: ArrayVec<0, ()> = ArrayVec::new();
        core::mem::drop(x);
    }

    #[test]
    fn drop_heap_types() {
        let x = ArrayVec::from_array([Box::new(0)]);
        core::mem::drop(x);
        let x = ArrayVec::from_array([String::from("I ♥ cum")]);
        core::mem::drop(x);
        let x = ArrayVec::from_array([vec![String::from("I ♥ you")]]);
        core::mem::drop(x);
    }

    #[test]
    fn clone() {
        let vec = ArrayVec::from_array([1, 2, 3, 4]);
        let mut vec2 = vec.clone();
        assert_eq!(vec.as_slice(), vec2.as_slice());

        vec2[1] = 69;
        assert_eq!(vec[1], 2);
    }

    #[test]
    fn len() {
        const EXPECTED: [u32; 4] = [67, 69, 420, 80085];
        let vec = ArrayVec::from_array(EXPECTED);
        assert_eq!(vec.len(), EXPECTED.len());
    }

    #[test]
    fn is_empty() {
        let vec: ArrayVec<4, u8> = ArrayVec::new();
        assert!(vec.is_empty());
    }

    #[test]
    fn is_full() {
        let vec: ArrayVec<4, u8> = ArrayVec::from_array([0; 4]);
        assert!(vec.is_full());
    }

    #[test]
    fn from_array() {
        const EXPECTED: [u32; 4] = [67, 69, 420, 80085];
        let vec = ArrayVec::from_array(EXPECTED);
        assert_eq!(vec.as_slice(), EXPECTED);
    }

    #[test]
    fn deref() {
        let vec: ArrayVec<4, u8> = ArrayVec::from_array([0; 4]);
        assert_eq!(&*vec, [0; 4]);
    }

    #[test]
    fn deref_mut() {
        let mut vec: ArrayVec<4, u8> = ArrayVec::from_array([0; 4]);
        assert_eq!(&*vec, [0; 4]);

        for item in &mut *vec {
            *item = 10;
        }
        assert_eq!(&*vec, [10; 4]);
    }

    #[test]
    fn from_slice() {
        const EXPECTED: [u32; 4] = [67, 69, 420, 80085];
        let vec = ArrayVec::<4, _>::from_slice(&EXPECTED).unwrap();
        assert_eq!(vec.as_slice(), EXPECTED);
    }

    #[test]
    #[should_panic]
    fn from_slice_too_large() {
        const EXPECTED: [u32; 4] = [67, 69, 420, 80085];
        let _ = ArrayVec::<1, _>::from_slice(&EXPECTED).unwrap();
    }

    #[test]
    fn as_array() {
        let vec: ArrayVec<4, u8> = ArrayVec::from_array([69; 4]);
        assert_eq!(&*vec, vec.as_array().unwrap());
    }

    #[test]
    fn as_array_mut() {
        let mut vec: ArrayVec<4, u8> = ArrayVec::from_array([69; 4]);
        vec.as_array_mut().unwrap()[2] = 3;
        assert_eq!(&*vec, [69, 69, 3, 69]);
    }

    #[test]
    fn as_array_not_full() {
        let vec: ArrayVec<4, u8> = ArrayVec::new();
        assert_eq!(vec.as_array(), None);
    }

    #[test]
    fn as_array_mut_not_full() {
        let mut vec: ArrayVec<4, u8> = ArrayVec::new();
        assert_eq!(vec.as_array_mut(), None);
    }

    #[test]
    fn push() {
        let mut vec: ArrayVec<5, u8> = ArrayVec::new();
        vec.push(230);
        assert_eq!(vec.as_slice(), &[230]);
        vec.push(69);
        assert_eq!(vec.as_slice(), &[230, 69]);
        vec.push(101);
        assert_eq!(vec.as_slice(), &[230, 69, 101]);
    }

    #[test]
    #[should_panic]
    fn push_beyond_capacity() {
        let mut vec: ArrayVec<0, u8> = ArrayVec::new();
        vec.push(69);
    }

    #[test]
    fn pop_removes_values() {
        let mut vec = ArrayVec::from_array([2, 3, 4]);
        assert_eq!(vec.pop(), Some(4));
        assert_eq!(&*vec, &[2, 3]);

        assert_eq!(vec.pop(), Some(3));
        assert_eq!(&*vec, &[2]);

        assert_eq!(vec.pop(), Some(2));
        assert_eq!(&*vec, &[]);

        assert_eq!(vec.pop(), None);
        assert_eq!(&*vec, &[]);
    }

    #[test]
    fn pop_heap_types() {
        let mut vec = ArrayVec::from_array([String::from("hey"), String::from("boy")]);
        assert_eq!(vec.pop(), Some(String::from("boy")));
        core::mem::drop(vec);
    }

    #[test]
    fn push_pop() {
        let mut vec = ArrayVec::<2, u8>::new();

        vec.push(1);
        assert_eq!(vec.pop(), Some(1));
        assert_eq!(&*vec, &[]);

        vec.push(8);
        assert_eq!(vec.pop(), Some(8));
        assert_eq!(&*vec, &[]);
    }

    #[test]
    fn try_push_ok() {
        let mut vec: ArrayVec<2, u8> = ArrayVec::new();
        assert_eq!(vec.try_push(1), Ok(()));
        assert_eq!(vec.try_push(2), Ok(()));
    }

    #[test]
    fn try_push_full() {
        let mut vec: ArrayVec<1, u8> = ArrayVec::new();
        vec.push(1);
        assert_eq!(vec.try_push(99), Err(99));
        assert_eq!(vec.as_slice(), &[1]);
    }

    #[test]
    fn try_insert() {
        let mut vec: ArrayVec<4, u8> = ArrayVec::from_slice(&[1, 3]).unwrap();
        assert_eq!(vec.try_insert(2, 1), Ok(()));
        assert_eq!(vec.as_slice(), &[1, 2, 3]);
    }

    #[test]
    fn try_insert_out_of_bounds() {
        let mut vec: ArrayVec<4, u8> = ArrayVec::new();
        assert!(vec.try_insert(0, 1).is_err());
    }

    #[test]
    fn truncate() {
        let mut vec = ArrayVec::from_array([1, 2, 3, 4]);

        vec.truncate(2);
        assert_eq!(vec.as_slice(), [1, 2]);
        vec.push(0);
        assert_eq!(vec.as_slice(), [1, 2, 0]);
        vec.truncate(0);
        assert_eq!(vec.as_slice(), []);
        vec.truncate(0xcafebabe);
        assert!(vec.is_empty());
    }

    #[test]
    fn truncate_heap_types() {
        let mut vec = ArrayVec::from_array([String::from("hey"), String::from("boy")]);

        vec.truncate(1);
        assert_eq!(vec.as_slice(), [String::from("hey")]);
        core::mem::drop(vec);
    }

    #[test]
    fn truncate_noop() {
        let mut vec = ArrayVec::from_array([1, 2, 3, 4]);

        // Anything >= len is a no-op
        vec.truncate(4);
        assert_eq!(vec.len(), 4);
        vec.truncate(10);
        assert_eq!(vec.len(), 4);
    }

    #[test]
    fn resize_truncate() {
        let mut vec = ArrayVec::from_array([1, 2, 3, 4]);

        vec.resize(2, 0);
        assert_eq!(vec.len(), 2);
    }

    #[test]
    #[should_panic]
    fn resize_beyond_capacity() {
        let mut vec = ArrayVec::<1, _>::from_slice(&[1]).unwrap();

        vec.resize(2, 0);
    }

    #[test]
    fn resize_extend_heap_types() {
        let mut vec = ArrayVec::<1, _>::from_slice(&[]).unwrap();

        vec.resize(1, String::from("girls rule"));
        assert_eq!(vec.len(), 1);
        assert_eq!(vec.as_slice(), [String::from("girls rule")]);
    }

    #[test]
    fn insert() {
        const EXPECTED: [u32; 4] = [67, 69, 420, 80085];
        let vec: ArrayVec<4, u32> = {
            let mut vec = ArrayVec::<4, _>::from_slice(&[67, 420, 80085]).unwrap();
            vec.insert(69, 1);
            vec
        };
        assert_eq!(vec.as_slice(), EXPECTED);
    }

    #[test]
    #[should_panic]
    fn insert_full() {
        let mut vec = ArrayVec::<0, u64>::from_array([]);
        vec.insert(0xcafebabe, 0);
    }

    proptest! {
        #![proptest_config(proptest_config())]
        #[test]
        fn resize_extend(
            initial in prop::collection::vec(0u8..=255, 0..4usize),
            fill: u8,
            extra in 0..5usize,
        ) {
            let new_len = initial.len() + extra;
            let mut vec = ArrayVec::<8, u8>::from_slice(&initial).unwrap();
            vec.resize(new_len, fill);

            assert_eq!(&vec.as_slice()[..initial.len()], initial.as_slice());
            assert!(vec.as_slice()[initial.len()..].iter().all(|&x| x == fill));
            assert_eq!(vec.len(), new_len);
        }
    }

    #[test]
    fn ref_vec() {
        let vec = ArrayVec::from_array([7; 4]);
        let slice: ArrayVec<4, &i32> = vec.ref_vec();
        assert!(vec.iter().zip(slice.iter().copied()).all(|(&l, r)| l.eq(r)));
    }

    #[test]
    fn mut_vec() {
        let mut vec = ArrayVec::from_array([7; 4]);
        let slice: ArrayVec<4, &mut i32> = vec.mut_vec();

        for x in slice {
            *x = 69; // I'm so horny
        }

        assert_eq!(&*vec, [69; 4]);
    }

    #[test]
    fn debug_noop() {
        let vec = ArrayVec::from_array([1u8, 2, 3, 4]);
        eprintln!("{vec:?}");
    }

    #[test]
    fn partial_eq() {
        let a = ArrayVec::from_array([1u8, 2, 3]);
        let b = ArrayVec::from_array([1u8, 2, 3]);
        let c = ArrayVec::from_array([1u8, 2, 4]);
        assert_eq!(a, b);
        assert_ne!(a, c);
    }

    #[test]
    fn ord() {
        let a = ArrayVec::from_array([1u8, 2, 3]);
        let b = ArrayVec::from_array([1u8, 2, 4]);
        assert!(a < b);
    }

    proptest! {
        #![proptest_config(proptest_config())]
        #[test]
        fn shift_right_semantics(
            original in prop::collection::vec(0u8..=255, 0..16),
            item: u8,
        ) {
            // Build conceptual [item, original...], then split
            let mut expected_slice = vec![item];
            expected_slice.extend_from_slice(&original);
            expected_slice.truncate(original.len()); // first `len` stay
            let expected_returned = {
                let mut full = vec![item];
                full.extend_from_slice(&original);
                full[original.len()..].to_vec()        // last 1 is returned
            };

            let mut buf = original.clone();
            let returned = slice_shift_right(&mut buf, [item]);

            assert_eq!(buf, expected_slice);
            assert_eq!(returned, expected_returned.as_slice());
        }
    }

    #[derive(Debug, Clone)]
    enum Op {
        Push(u8),
        TryPush(u8),
        Pop,
        Insert(u8, usize),
        TryInsert(u8, usize),
        Truncate(usize),
        Resize(usize, u8),
    }

    fn arbatrary_op() -> impl Strategy<Value = Op> {
        prop_oneof![
            any::<u8>().prop_map(Op::Push),
            any::<u8>().prop_map(Op::TryPush),
            Just(Op::Pop),
            (any::<u8>(), any::<usize>()).prop_map(|(v, i)| Op::Insert(v, i)),
            (any::<u8>(), any::<usize>()).prop_map(|(v, i)| Op::TryInsert(v, i)),
            any::<usize>().prop_map(Op::Truncate),
            (any::<u8>(), any::<usize>()).prop_map(|(v, i)| Op::Resize(i, v)),
        ]
    }

    fn model_try_push(v: &mut Vec<u8>, value: u8) -> Result<(), u8> {
        if v.len() >= v.capacity() {
            return Err(value);
        }

        v.push(value);
        Ok(())
    }

    fn model_try_insert(v: &mut Vec<u8>, value: u8, idx: usize) -> Result<(), u8> {
        if v.len() >= v.capacity() || idx > v.len() {
            return Err(value);
        }

        v.insert(idx, value);
        Ok(())
    }

    proptest! {
        #![proptest_config(proptest_config())]
        #[test]
        fn model_based(ops in prop::collection::vec(arbatrary_op(), 0..50)) {
            const C: usize = 8;
            let mut vec: ArrayVec<C, u8> = ArrayVec::new();
            let mut model: Vec<u8> = Vec::with_capacity(C);

            for op in ops {
                match op {
                    Op::Push(v) => {
                        if model.len() < C {
                            vec.push(v);
                            model.push(v);
                        }
                    }
                    Op::TryPush(x) => {
                        assert_eq!(vec.try_push(x), model_try_push(&mut model, x));
                    }
                    Op::Pop => {
                        assert_eq!(vec.pop(), model.pop());
                    }
                    Op::Insert(v, i) => {
                        if model.len() < C {
                            let idx = i % (model.len() + 1);
                            vec.insert(v, idx);
                            model.insert(idx, v);
                        }
                    }
                    Op::TryInsert(val, idx) => {
                        assert_eq!(
                            vec.try_insert(val, idx),
                            model_try_insert(&mut model, val, idx)
                        );
                    }
                    Op::Truncate(n) => {
                        let n = n % (C + 1);
                        vec.truncate(n);
                        model.truncate(n);
                    }
                    Op::Resize(n, x) => {
                        let n = n % (C + 1);
                        vec.resize(n, x);
                        model.resize(n,x);
                    }
                }
                assert_eq!(vec.as_slice(), model.as_slice());
                assert!(vec.len() <= C);
            }
        }
    }
}