generic-vec 0.1.2

#![cfg_attr(not(any(doc, feature = "std")), no_std)]
#![cfg_attr(
    any(doc, feature = "nightly"),
    feature(min_const_generics, unsafe_block_in_unsafe_fn)
)]
#![cfg_attr(
    any(doc, feature = "nightly"),
    feature(
        trusted_len,
        min_specialization,
        exact_size_is_empty,
        allocator_api,
        alloc_layout_extra,
        const_panic,
        const_fn,
        const_mut_refs,
        const_raw_ptr_deref,
        doc_cfg,
    )
)]
#![cfg_attr(feature = "nightly", forbid(unsafe_op_in_unsafe_fn))]
#![allow(unused_unsafe)]
#![forbid(missing_docs, clippy::missing_safety_doc)]

//! A vector that can store items anywhere: in slices, arrays, or the heap!
//!
//! [`GenericVec`] has complete parity with [`Vec`], and even provides some features
//! that are only in `nightly` on `std` (like [`GenericVec::drain_filter`]), or a more permissive
//! interface like [`GenericVec::retain`]. In fact, you can trivially convert a [`Vec`] to a
//! [`HeapVec`] and back!
//!
//! This crate is `no_std` compatible, just turn off all default features.
//!
//! # Features
//!
//! * `std` (default) - enables you to use an allocator, and
//! * `alloc` - enables you to use an allocator, for heap allocated storages
//!     (like [`Vec`])
//! * `nightly` - enables you to use array (`[T; N]`) based storages
//!
//! # Basic Usage
//!
//! ### [`SliceVec`] and [`InitSliceVec`]
//!
//! [`SliceVec`] and [`InitSliceVec`] are pretty similar, you give them a slice
//! buffer, and they store all of thier values in that buffer. But have three major
//! differences between them.
//!
//! * You can pass an uninitialized buffer to [`SliceVec`]
//! * You can only use [`Copy`] types with [`InitSliceVec`]
//! * You can freely set the length of the [`InitSliceVec`] as long as you stay
//!     within it's capacity (the length of the slice you pass in)
//!
//! ```rust
//! use generic_vec::{SliceVec, InitSliceVec, uninit_array};
//!
//! let mut uninit_buffer = uninit_array!(16);
//! let mut slice_vec = SliceVec::new(&mut uninit_buffer);
//!
//! assert!(slice_vec.is_empty());
//! slice_vec.push(10);
//! assert_eq!(slice_vec, [10]);
//! ```
//!
//! ```rust
//! # use generic_vec::InitSliceVec;
//! let mut init_buffer = [0xae; 16];
//! let mut slice_vec = InitSliceVec::new(&mut init_buffer);
//!
//! assert!(slice_vec.is_full());
//! assert_eq!(slice_vec.pop(), 0xae);
//! slice_vec.set_len(16);
//! assert!(slice_vec.is_full());
//! ```
//!
//! Of course if you try to push past a `*SliceVec`'s capacity
//! (the length of the slice you passed in), then it will panic.
//!
//! ```rust,should_panic
//! # use generic_vec::InitSliceVec;
//! let mut init_buffer = [0xae; 16];
//! let mut slice_vec = InitSliceVec::new(&mut init_buffer);
//! slice_vec.push(0);
//! ```
//!
//! ### [`TypeVec`]
//!
//! [`TypeVec`] is an owned buffer. You can use like so:
//!
//! ```rust
//! use generic_vec::{TypeVec, gvec};
//! let mut vec: TypeVec<u32, [u32; 4]> = gvec![1, 2, 3, 4];
//!
//! assert_eq!(vec, [1, 2, 3, 4]);
//!
//! vec.try_push(5).expect_err("Tried to push past capacity!");
//! ```
//!
//! The second parameter specifies the buffer type, this can be any type
//! you want. Only the size of the type matters. There is also a defaulted
//! third parameter, but you should only use that if you know what you are
//! doing, and after reading the docs for [`UninitBuffer`](raw::UninitBuffer).
//!
//! As a neat side-effect of this framework, you can also get an efficient
//! [`GenericVec`] for zero-sized types, just a `usize` in size! This feature
//! can be on stable `no_std`.
//!
//! ### [`ArrayVec`](type@ArrayVec) and [`InitArrayVec`](type@InitArrayVec)
//!
//! [`ArrayVec`](type@ArrayVec) and [`InitArrayVec`](type@InitArrayVec)
//! are just like the slice versions, but since they own their data,
//! they can be freely moved around, unconstrained. You can also create
//! a new [`ArrayVec`](type@ArrayVec) without passing in an existing buffer,
//! unlike the slice versions.
//!
//! On stable, you can use the [`ArrayVec`](macro@ArrayVec) or
//! [`InitArrayVec`](macro@InitArrayVec) to construct the type. On `nightly`,
//! you can use the type aliases [`ArrayVec`](type@ArrayVec) and
//! [`InitArrayVec`](type@InitArrayVec). The macros will be deprecated once
//! `min_const_generics` hits stable.
//!
//! The only limitation on stable is that you can only use [`InitArrayVec`](type@InitArrayVec)
//! capacity up to 32. i.e. `InitArrayVec![i32; 33]` doesn't work. `ArrayVec` does not suffer
//! from this limitation because it is built atop [`TypeVec`].
//!
//! ```rust
//! use generic_vec::ArrayVec;
//!
//! let mut array_vec = ArrayVec::<i32, 16>::new();
//!
//! array_vec.push(10);
//! array_vec.push(20);
//! array_vec.push(30);
//!
//! assert_eq!(array_vec, [10, 20, 30]);
//! ```
//!
//! The distinction between [`ArrayVec`](type@ArrayVec) and [`InitArrayVec`](type@InitArrayVec)
//! is identical to their slice counterparts.
//!
//! ### [`ZSVec`]
//!
//! ```rust
//! use generic_vec::ZSVec;
//!
//! struct MyType;
//!
//! let mut vec = ZSVec::new();
//!
//! vec.push(MyType);
//! vec.push(MyType);
//! vec.push(MyType);
//!
//! assert_eq!(vec.len(), 3);
//! assert_eq!(std::mem::size_of_val(&vec), std::mem::size_of::<usize>());
//! ```
//!
//! ## `alloc`
//!
//! A [`HeapVec`] is just [`Vec`], but built atop [`GenericVec`],
//! meaning you get all the features of [`GenericVec`] for free! But this
//! requries either the `alloc` or `std` feature to be enabled.
//!
//! ```rust
//! use generic_vec::{HeapVec, gvec};
//! let mut vec: HeapVec<u32> = gvec![1, 2, 3, 4];
//! assert_eq!(vec.capacity(), 4);
//! vec.extend(&[5, 6, 7, 8]);
//!
//! assert_eq!(vec, [1, 2, 3, 4, 5, 6, 7, 8]);
//!
//! vec.try_push(5).expect_err("Tried to push past capacity!");
//! ```
//!
//! ## `nightly`
//!
//! On `nightly`
//! * the restriction on [`InitArrayVec`](type@InitArrayVec)'s length goes away.
//! * many functions/methods become `const fn`s
//! * a number of optimizations are enabled
//! * some diagnostics become better
//!
//! Note on the documentation: if the feature exists on [`Vec`], then the documentation
//! is either exactly the same as [`Vec`] or slightly adapted to better fit [`GenericVec`]
//!
//! Note on implementation: large parts of the implementation came straight from [`Vec`]
//! so thanks for the amazing reference `std`!

#[cfg(all(feature = "alloc", not(feature = "std")))]
extern crate alloc as std;

use core::{
    marker::PhantomData,
    mem::MaybeUninit,
    ops::{Deref, DerefMut, RangeBounds},
    ptr,
};

mod extension;
mod impls;
mod slice;

pub mod iter;
pub mod raw;

use raw::Storage;

#[doc(hidden)]
pub use core;

/// A heap backed vector with a growable capacity
#[cfg(any(doc, all(feature = "alloc", feature = "nightly")))]
#[cfg_attr(doc, doc(cfg(all(feature = "alloc", feature = "nightly"))))]
pub type HeapVec<T, A = std::alloc::Global> = GenericVec<T, raw::Heap<T, A>>;

/// A heap backed vector with a growable capacity
#[cfg(all(not(doc), feature = "alloc", not(feature = "nightly")))]
#[cfg_attr(doc, doc(cfg(feature = "alloc")))]
pub type HeapVec<T> = GenericVec<T, raw::Heap<T>>;

/// An array backed vector backed by potentially uninitialized memory
#[cfg(any(doc, feature = "nightly"))]
#[cfg_attr(doc, doc(cfg(feature = "nightly")))]
pub type ArrayVec<T, const N: usize> = TypeVec<T, [T; N]>;
/// An slice backed vector backed by potentially uninitialized memory
pub type SliceVec<'a, T> = GenericVec<T, &'a mut raw::UninitSlice<T>>;

/// An array backed vector backed by initialized memory
#[cfg(any(doc, feature = "nightly"))]
#[cfg_attr(doc, doc(cfg(feature = "nightly")))]
pub type InitArrayVec<T, const N: usize> = GenericVec<T, [T; N]>;
/// An slice backed vector backed by initialized memory
pub type InitSliceVec<'a, T> = GenericVec<T, &'a mut [T]>;
/// A counter vector that can only store zero-sized types
pub type ZSVec<T> = GenericVec<T, raw::ZeroSized<T>>;
/// An type based vector backed by uninitialized memory with the same layout as `B`
///
/// see: [`UninitBuffer`](raw::UninitBuffer) for details
pub type TypeVec<T, B, A = T> = GenericVec<T, raw::UninitBuffer<B, A>>;

#[doc(hidden)]
pub mod macros {
    pub use core::mem::MaybeUninit;
    impl<T> Uninit for T {}
    pub trait Uninit: Sized {
        const UNINIT: MaybeUninit<Self> = MaybeUninit::uninit();
    }
}

/// Create a new generic vector
///
/// Because this can create any generic vector, you will likely
/// need to add some type annotations when you use it,
///
/// ```rust
/// # use generic_vec::{gvec, ArrayVec};
/// let x: ArrayVec<i32, 2> = gvec![0, 1];
/// assert_eq!(x, [0, 1]);
/// ```
#[macro_export]
#[cfg(feature = "nightly")]
macro_rules! gvec {
    ($expr:expr; $n:expr) => {{
        let len = $n;
        let mut vec = $crate::GenericVec::with_capacity(len);
        vec.grow(len, $expr);
        vec
    }};
    ($($expr:expr),*) => {{
        let expr = [$($expr),*];
        let mut vec = $crate::GenericVec::with_capacity(expr.len());
        unsafe { vec.push_array_unchecked(expr); }
        vec
    }};
}

#[doc(hidden)]
#[macro_export]
macro_rules! count {
    () => { 0 };
    ($($a:tt $b:tt)*) => { $crate::count!($($a)*) << 1 };
    ($c:tt $($a:tt $b:tt)*) => { ($crate::count!($($a)*) << 1) | 1 };
}

/// Create a new generic vector
///
/// Because this can create any generic vector, you will likely
/// need to add some type annotations when you use it,
///
/// ```rust
/// # use generic_vec::{gvec, TypeVec};
/// let x: TypeVec<i32, [i32; 4]> = gvec![1, 2, 3, 4];
/// assert_eq!(x, [1, 2, 3, 4]);
/// ```
#[macro_export]
#[cfg(not(feature = "nightly"))]
macro_rules! gvec {
    ($expr:expr; $n:expr) => {{
        let len = $n;
        let mut vec = $crate::GenericVec::with_capacity(len);
        vec.grow(len, $expr);
        vec
    }};
    ($($expr:expr),*) => {{
        let mut vec = $crate::GenericVec::with_capacity($crate::count!($(($expr))*));
        unsafe {
            $(vec.push_unchecked($expr);)*
        }
        vec
    }};
}

/// a helper macro to safely create an array of uninitialized memory of any size
///
///  use the const prefix if you need to initialize a `const` or `static`,
/// otherwise don't use the const modifier
#[macro_export]
macro_rules! uninit_array {
    (const $n:expr) => {
        [$crate::macros::Uninit::UNINIT; $n]
    };

    ($n:expr) => {
        // Safety
        //
        // `MaybeUninit` can represent any bit-pattern, including uninitialized memory
        // so it's fine to cast uninitialized memory to `[MaybeUninit; N]`
        unsafe { $crate::macros::MaybeUninit::<[$crate::macros::MaybeUninit<_>; $n]>::uninit().assume_init() }
    };
}

/// Save the changes to [`GenericVec::spare_capacity_mut`]
///
/// $orig - a mutable reference to a [`GenericVec`]
/// $spare - the [`SliceVec`] that was obtained from [`$orig.spare_capacity_mut()`]
///
/// # Safety
///
/// `$spare` should be the [`SliceVec`] returned by `$orig.spare_capacity_mut()`
#[macro_export]
macro_rules! save_spare {
    ($spare:expr, $orig:expr) => {{
        let spare: $crate::SliceVec<_> = $spare;
        let spare = $crate::core::mem::ManuallyDrop::new(spare);
        let len = spare.len();
        let ptr = spare.as_ptr();
        let orig: &mut $crate::GenericVec<_, _> = $orig;
        $crate::validate_spare(ptr, orig);
        let len = len + orig.len();
        $orig.set_len_unchecked(len);
    }};
}

#[doc(hidden)]
pub fn validate_spare<T>(spare_ptr: *const T, orig: &[T]) {
    debug_assert!(
        unsafe { orig.as_ptr().add(orig.len()) == spare_ptr },
        "Tried to use `save_spare!` with a `SliceVec` that was not obtained from `GenricVec::spare_capacity_mut`. \
         This is undefined behavior on release mode!"
    )
}

/// An array backed vector backed by potentially uninitialized memory
///
/// On `nightly`, it's prefered to use the [`ArrayVec`](type@ArrayVec) type alias
#[macro_export]
macro_rules! ArrayVec {
    ($type:ty; $len:expr) => {
        $crate::GenericVec<$type, $crate::raw::UninitBuffer<[$type; $len]>>
    };
}

/// An array backed vector backed by initialized memory
///
/// On `nightly`, it's prefered to use the [`InitArrayVec`](type@InitArrayVec) type alias
#[macro_export]
macro_rules! InitArrayVec {
    ($type:ty; $len:expr) => {
        $crate::GenericVec<$type, [$type; $len]>
    };
}

/// A vector type that can be backed up by a variety of different backends
/// including slices, arrays, and the heap.
#[repr(C)]
pub struct GenericVec<T, S: ?Sized + Storage<T>> {
    mark: PhantomData<T>,
    len: usize,
    storage: S,
}

impl<T, S: ?Sized + Storage<T>> Deref for GenericVec<T, S> {
    type Target = [T];

    fn deref(&self) -> &Self::Target {
        let len = self.len();
        // The first `len` elements are guaranteed to be initialized
        // as part of the guarantee on `self.set_len_unchecked`
        unsafe { core::slice::from_raw_parts(self.as_ptr(), len) }
    }
}

impl<T, S: ?Sized + Storage<T>> DerefMut for GenericVec<T, S> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        let len = self.len();
        // The first `len` elements are guaranteed to be initialized
        // as part of the guarantee on `self.set_len_unchecked`
        unsafe { core::slice::from_raw_parts_mut(self.as_mut_ptr(), len) }
    }
}

impl<T, S: ?Sized + Storage<T>> Drop for GenericVec<T, S> {
    fn drop(&mut self) {
        // The first `len` elements are guaranteed to be initialized
        // as part of the guarantee on `self.set_len_unchecked`
        // These elements should be dropped when the `GenericVec` gets dropped/
        // The storage will clean it's self up on drop
        unsafe { ptr::drop_in_place(self.as_mut_slice()) }
    }
}

#[cfg(not(feature = "nightly"))]
impl<T, S: Storage<T>> GenericVec<T, S> {
    /// Create a new empty `GenericVec` with the given backend
    ///
    /// ```rust
    /// use generic_vec::{GenericVec, raw::ZeroSized};
    /// let vec = GenericVec::with_storage(ZeroSized::<[i32; 0]>::NEW);
    /// ```
    pub fn with_storage(storage: S) -> Self {
        assert!(S::IS_ALIGNED, "The storage must be aligned to `T`");
        Self {
            storage,
            len: 0,
            mark: PhantomData,
        }
    }
}

#[cfg(feature = "nightly")]
impl<T, S: Storage<T>> GenericVec<T, S> {
    /// Create a new empty `GenericVec` with the given backend
    ///
    /// Note: this is only const with the `nightly` feature enabled
    pub const fn with_storage(storage: S) -> Self {
        assert!(S::IS_ALIGNED, "The storage must be aligned to `T`");
        Self {
            storage,
            len: 0,
            mark: PhantomData,
        }
    }
}

impl<T, S: raw::StorageWithCapacity<T>> GenericVec<T, S> {
    /// Create a new empty `GenericVec` with the backend with at least the given capacity
    pub fn with_capacity(capacity: usize) -> Self { Self::with_storage(S::with_capacity(capacity)) }

    #[inline]
    #[allow(non_snake_case)]
    fn __with_capacity__const_capacity_checked(capacity: usize, old_capacity: Option<usize>) -> Self {
        Self::with_storage(S::__with_capacity__const_capacity_checked(capacity, old_capacity))
    }
}

impl<T, B> TypeVec<T, B, T> {
    /// Create a new [`TypeVec`]
    pub const fn new() -> Self { Self::with_align() }
}

impl<T, B, A> TypeVec<T, B, A> {
    /// Create a new [`TypeVec`] with the given alignment type
    pub const fn with_align() -> Self {
        #[cfg(not(feature = "nightly"))]
        #[allow(clippy::no_effect)]
        {
            [()][(!<raw::UninitBuffer<B, A> as raw::Storage<T>>::IS_ALIGNED) as usize];
        }
        #[cfg(feature = "nightly")]
        {
            assert!(
                <raw::UninitBuffer<B, A> as raw::Storage<T>>::IS_ALIGNED,
                "Your buffer is not sufficiently aligned"
            )
        }

        Self {
            len: 0,
            storage: raw::UninitBuffer::uninit(),
            mark: PhantomData,
        }
    }
}

#[cfg(any(doc, feature = "nightly"))]
#[cfg_attr(doc, doc(cfg(feature = "nightly")))]
impl<T, const N: usize> ArrayVec<T, N> {
    /// Create a new full `ArrayVec`
    pub const fn from_array(array: [T; N]) -> Self {
        Self {
            len: 0,
            mark: PhantomData,
            storage: raw::UninitBuffer::new(array),
        }
    }

    /// Convert this `ArrayVec` into an array
    ///
    /// # Panic
    ///
    /// Panics if the the collection is not full
    pub fn into_array(self) -> [T; N] {
        assert!(self.is_full());
        let this = core::mem::ManuallyDrop::new(self);
        unsafe { Storage::<[T; N]>::as_ptr(&this.storage).read() }
    }
}

#[cfg(feature = "nightly")]
#[cfg_attr(doc, doc(cfg(feature = "nightly")))]
impl<T: Copy, const N: usize> InitArrayVec<T, N> {
    /// Create a new full `InitArrayVec`
    pub fn new(storage: [T; N]) -> Self {
        Self {
            len: N,
            mark: PhantomData,
            storage,
        }
    }
}

#[cfg(feature = "alloc")]
#[cfg_attr(doc, doc(cfg(feature = "alloc")))]
impl<T> HeapVec<T> {
    /// Create a new empty `HeapVec`
    pub const fn new() -> Self {
        Self {
            len: 0,
            mark: PhantomData,
            storage: raw::Heap::new(),
        }
    }
}

#[cfg(any(doc, all(feature = "nightly", feature = "alloc")))]
#[cfg_attr(doc, doc(cfg(all(feature = "nightly", feature = "alloc"))))]
impl<T, A: std::alloc::AllocRef> HeapVec<T, A> {
    /// Create a new empty `HeapVec` with the given allocator
    pub fn with_alloc(alloc: A) -> Self { Self::with_storage(raw::Heap::with_alloc(alloc)) }
}

#[cfg(any(doc, not(feature = "nightly")))]
impl<'a, T> SliceVec<'a, T> {
    /// Create a new empty `SliceVec`
    pub fn new(slice: &'a mut [MaybeUninit<T>]) -> Self { Self::with_storage(raw::UninitSlice::from_mut(slice)) }
}

#[cfg(any(doc, feature = "nightly"))]
impl<'a, T> SliceVec<'a, T> {
    /// Create a new empty `SliceVec`
    ///
    /// Note: this is only const with the `nightly` feature enabled
    pub const fn new(slice: &'a mut [MaybeUninit<T>]) -> Self { Self::with_storage(raw::UninitSlice::from_mut(slice)) }
}

#[cfg(any(doc, not(feature = "nightly")))]
impl<'a, T: Copy> InitSliceVec<'a, T> {
    /// Create a new full `InitSliceVec`
    pub fn new(storage: &'a mut [T]) -> Self {
        Self {
            len: storage.len(),
            storage,
            mark: PhantomData,
        }
    }
}

#[cfg(feature = "nightly")]
impl<'a, T: Copy> InitSliceVec<'a, T> {
    /// Create a new full `InitSliceVec`
    ///
    /// Note: this is only const with the `nightly` feature enabled
    pub const fn new(storage: &'a mut [T]) -> Self {
        Self {
            len: storage.len(),
            storage,
            mark: PhantomData,
        }
    }
}

impl<T, S: Storage<T>> GenericVec<T, S> {
    /// Convert a `GenericVec` into a length-storage pair
    pub fn into_raw_parts(self) -> (usize, S) {
        let this = core::mem::ManuallyDrop::new(self);
        unsafe { (this.len, core::ptr::read(&this.storage)) }
    }

    /// Create a `GenericVec` from a length-storage pair
    ///
    /// # Safety
    ///
    /// the length must be less than `raw.capacity()` and
    /// all elements in the range `0..length`, must be initialized
    ///
    /// # Panic
    ///
    /// If the given storage cannot hold type `T`, then this method will panic
    #[cfg(not(feature = "nightly"))]
    pub unsafe fn from_raw_parts(len: usize, storage: S) -> Self {
        Self {
            storage,
            len,
            mark: PhantomData,
        }
    }
}

#[cfg(feature = "nightly")]
impl<T, S: Storage<T>> GenericVec<T, S> {
    /// Create a `GenericVec` from a length-storage pair
    ///
    /// Note: this is only const with the `nightly` feature enabled
    ///
    /// # Safety
    ///
    /// the length must be less than `raw.capacity()` and
    /// all elements in the range `0..length`, must be initialized
    ///
    /// # Panic
    ///
    /// If the given storage cannot hold type `T`, then this method will panic
    pub const unsafe fn from_raw_parts(len: usize, storage: S) -> Self {
        Self {
            storage,
            len,
            mark: PhantomData,
        }
    }
}

impl<T> ZSVec<T> {
    /// Create a new counter vector
    pub const NEW: Self = Self {
        len: 0,
        storage: raw::ZeroSized::NEW,
        mark: PhantomData,
    };

    /// Create a new counter vector
    pub const fn new() -> Self { Self::NEW }
}

impl<T, S: ?Sized + Storage<T>> GenericVec<T, S> {
    /// Returns a shared raw pointer to the vector's buffer.
    ///
    /// It's not safe to write to this pointer except for values
    /// inside of an `UnsafeCell`
    pub fn as_ptr(&self) -> *const T { self.storage.as_ptr() }

    /// Returns a unique raw pointer to the vector's buffer.
    pub fn as_mut_ptr(&mut self) -> *mut T { self.storage.as_mut_ptr() }

    /// Returns the number of elements in the vector
    pub fn len(&self) -> usize { self.len }

    /// Returns the number of elements the vector can hold without reallocating or panicing.
    pub fn capacity(&self) -> usize {
        if core::mem::size_of::<T>() == 0 {
            isize::MAX as usize
        } else {
            self.storage.capacity()
        }
    }

    /// Returns true if and only if the vector contains no elements.
    pub fn is_empty(&self) -> bool { self.len() == 0 }

    /// Returns true if and only if the vector's length is equal to it's capacity.
    pub fn is_full(&self) -> bool { self.len() == self.capacity() }

    /// Returns the length of the spare capacity of the `GenericVec`
    pub fn remaining_capacity(&self) -> usize { self.capacity().wrapping_sub(self.len()) }

    /// Set the length of a vector
    ///
    /// # Safety
    ///
    /// * new_len must be less than or equal to `capacity()`.
    /// * The elements at `old_len..new_len` must be initialized.
    pub unsafe fn set_len_unchecked(&mut self, len: usize) { self.len = len; }

    /// Set the length of a vector
    pub fn set_len(&mut self, len: usize)
    where
        S: raw::StorageInit<T>,
    {
        // Safety
        //
        // The storage only contains initialized data, and we check that
        // the given length is smaller than the capacity
        unsafe {
            assert!(
                len <= self.capacity(),
                "Tried to set the length to larger than the capacity"
            );
            self.set_len_unchecked(len);
        }
    }

    /// Extracts a slice containing the entire vector.
    ///
    /// Equivalent to &s[..].
    pub fn as_slice(&self) -> &[T] { self }

    /// Extracts a mutable slice containing the entire vector.
    ///
    /// Equivalent to &mut s[..].
    pub fn as_mut_slice(&mut self) -> &mut [T] { self }

    /// Returns the underlying storage
    pub fn storage(&self) -> &S { &self.storage }

    /// Returns the underlying storage
    ///
    /// # Safety
    ///
    /// You must not replace the storage
    pub unsafe fn storage_mut(&mut self) -> &mut S { &mut self.storage }

    /// Returns the remaining spare capacity of the vector as
    /// a [`SliceVec<'_, T>`](SliceVec).
    ///
    /// Keep in mind that the [`SliceVec<'_, T>`](SliceVec) will drop all elements
    /// that you push into it when it goes out of scope! If you want
    /// these modifications to persist then you should use [`save_spare`]
    /// to persist these writes.
    ///
    /// ```
    /// let mut vec = generic_vec::TypeVec::<i32, [i32; 16]>::new();
    ///
    /// let mut spare = vec.spare_capacity_mut();
    /// spare.push(0);
    /// spare.push(2);
    /// drop(spare);
    /// assert_eq!(vec, []);
    ///
    /// let mut spare = vec.spare_capacity_mut();
    /// spare.push(0);
    /// spare.push(2);
    /// unsafe { generic_vec::save_spare!(spare, &mut vec) }
    /// assert_eq!(vec, [0, 2]);
    /// ```
    pub fn spare_capacity_mut(&mut self) -> SliceVec<'_, T> {
        // Safety
        //
        // The elements from `len..capacity` are guaranteed to be contain
        // `A::BufferItem`s, as per `Storage`'s safety requirements
        unsafe {
            let len = self.len();
            let cap = self.capacity();
            SliceVec::new(core::slice::from_raw_parts_mut(
                self.storage.as_mut_ptr().add(len).cast(),
                cap.wrapping_sub(len),
            ))
        }
    }

    /// Reserve enough space for at least `additional` elements
    ///
    /// # Panics
    ///
    /// May panic or abort if it isn't possible to allocate enough space for
    /// `additional` more elements
    #[inline]
    pub fn reserve(&mut self, additional: usize) {
        #[cold]
        #[inline(never)]
        fn allocation_failure(additional: usize) -> ! {
            panic!("Tried to allocate: {} more space and failed", additional)
        }

        if self.remaining_capacity() < additional {
            self.storage.reserve(match self.len().checked_add(additional) {
                Some(new_capacity) => new_capacity,
                None => allocation_failure(additional),
            })
        }
    }

    /// Try to reserve enough space for at least `additional` elements, and returns `Err(_)`
    /// if it's not possible to reserve enough space
    #[inline]
    pub fn try_reserve(&mut self, additional: usize) -> bool {
        if self.remaining_capacity() < additional {
            match self.len().checked_add(additional) {
                Some(new_capacity) => self.storage.try_reserve(new_capacity),
                None => false,
            }
        } else {
            true
        }
    }

    /// Shortens the vector, keeping the first len elements and dropping the rest.
    ///
    /// If len is greater than the vector's current length, this has no effect.
    ///
    /// Note that this method has no effect on the allocated capacity of the vector.
    pub fn truncate(&mut self, len: usize) {
        if let Some(diff) = self.len().checked_sub(len) {
            // # Safety
            //
            // * the given length is smaller than the current length, so
            //   all the elements must be initialized
            // * the elements from `len..self.len()` are valid,
            //   and should be dropped
            unsafe {
                self.set_len_unchecked(len);
                let ptr = self.as_mut_ptr().add(len);
                let len = diff;
                core::ptr::drop_in_place(core::slice::from_raw_parts_mut(ptr, len));
            }
        }
    }

    /// Grows the `GenericVec` in-place by additional elements.
    ///
    /// This method requires `T` to implement `Clone`, in order to be able to clone
    /// the passed value. If you need more flexibility (or want to rely on Default instead of `Clone`),
    /// use [`GenericVec::grow_with`].
    ///
    /// # Panic
    ///
    /// May panic or reallocate if the collection is full
    ///
    /// # Panic behavor
    ///
    /// If `T::clone` panics, then all added items will be dropped. This is different
    /// from `std`, where on panic, items will stay in the `Vec`. This behavior
    /// is unstable, and may change in the future.
    pub fn grow(&mut self, additional: usize, value: T)
    where
        T: Clone,
    {
        self.reserve(additional);
        // # Safety
        //
        // * we reserved enough space
        unsafe { extension::Extension::grow(self, additional, value) }
    }

    /// Grows the `GenericVec` in-place by additional elements.
    ///
    /// This method uses a closure to create new values on every push.
    /// If you'd rather `Clone` a given value, use `GenericVec::resize`.
    /// If you want to use the `Default` trait to generate values, you
    /// can pass `Default::default` as the second argument.
    ///
    /// # Panic
    ///
    /// May panic or reallocate if the collection is full
    ///
    /// # Panic behavor
    ///
    /// If `F` panics, then all added items will be dropped. This is different
    /// from `std`, where on panic, items will stay in the `Vec`. This behavior
    /// is unstable, and may change in the future.
    pub fn grow_with<F>(&mut self, additional: usize, mut value: F)
    where
        F: FnMut() -> T,
    {
        // Safety
        //
        // * we reserve enough space for `additional` elements
        // * we use `spare_capacity_mut` to ensure that the items are dropped,
        //   even on panic
        // * the `ptr` always stays in bounds

        self.reserve(additional);
        let mut writer = self.spare_capacity_mut();

        for _ in 0..additional {
            unsafe {
                writer.push_unchecked(value());
            }
        }

        unsafe {
            save_spare!(writer, self);
        }
    }

    /// Resizes the [`GenericVec`] in-place so that `len` is equal to `new_len`.
    ///
    /// If `new_len` is greater than `len`, the [`GenericVec`] is extended by the difference,
    /// with each additional slot filled with value. If `new_len` is less than `len`,
    /// the [`GenericVec`] is simply truncated.
    ///
    /// If you know that `new_len` is larger than `len`, then use [`GenericVec::grow`]
    ///
    /// If you know that `new_len` is less than `len`, then use [`GenericVec::truncate`]
    ///
    /// This method requires `T` to implement `Clone`, in order to be able to clone
    /// the passed value. If you need more flexibility (or want to rely on Default
    /// instead of `Clone`), use [`GenericVec::resize_with`].
    ///
    /// # Panic
    ///
    /// May panic or reallocate if the collection is full
    ///
    /// # Panic behavor
    ///
    /// If `F` panics, then all added items will be dropped. This is different
    /// from `std`, where on panic, items will stay in the `Vec`. This behavior
    /// is unstable, and may change in the future.
    pub fn resize(&mut self, new_len: usize, value: T)
    where
        T: Clone,
    {
        match new_len.checked_sub(self.len()) {
            Some(0) => (),
            Some(additional) => self.grow(additional, value),
            None => self.truncate(new_len),
        }
    }

    /// Resizes the [`GenericVec`] in-place so that len is equal to new_len.
    ///
    /// If `new_len` is greater than `len`, the [`GenericVec`] is extended by the
    /// difference, with each additional slot filled with the result of calling
    /// the closure `f`. The return values from `f` will end up in the [`GenericVec`]
    /// in the order they have been generated.
    ///
    /// If `new_len` is less than `len`, the [`GenericVec`] is simply truncated.
    ///
    /// If you know that `new_len` is larger than `len`, then use [`GenericVec::grow_with`]
    ///
    /// If you know that `new_len` is less than `len`, then use [`GenericVec::truncate`]
    ///
    /// This method uses a closure to create new values on every push. If you'd
    /// rather [`Clone`] a given value, use [`GenericVec::resize`]. If you want to
    /// use the [`Default`] trait to generate values, you can pass [`Default::default`]
    /// as the second argument.
    ///
    /// # Panic
    ///
    /// May panic or reallocate if the collection is full
    ///
    /// # Panic behavor
    ///
    /// If `F` panics, then all added items will be dropped. This is different
    /// from `std`, where on panic, items will stay in the `Vec`. This behavior
    /// is unstable, and may change in the future.
    pub fn resize_with<F: FnMut() -> T>(&mut self, new_len: usize, value: F) {
        match new_len.checked_sub(self.len()) {
            Some(0) => (),
            Some(additional) => self.grow_with(additional, value),
            None => self.truncate(new_len),
        }
    }

    /// Clears the vector, removing all values.
    ///
    /// Note that this method has no effect on the allocated capacity of the vector.
    pub fn clear(&mut self) { self.truncate(0); }

    /// Appends an element to the back of a collection.
    ///
    /// # Panic
    ///
    /// May panic or reallocate if the collection is full
    pub fn push(&mut self, value: T) -> &mut T {
        if self.len() == self.capacity() {
            self.reserve(1);
        }

        // Safety
        //
        // * we reserve enough space for 1 more element
        unsafe { self.push_unchecked(value) }
    }

    /// Appends the array to the back of a collection.
    ///
    /// # Panic
    ///
    /// May panic or reallocate if the collection has less than N elements remaining
    #[cfg(any(doc, feature = "nightly"))]
    pub fn push_array<const N: usize>(&mut self, value: [T; N]) -> &mut [T; N] {
        self.reserve(N);

        // Safety
        //
        // * we reserve enough space for N more elements
        unsafe { self.push_array_unchecked(value) }
    }

    /// Inserts an element at position index within the vector,
    /// shifting all elements after it to the right.
    ///
    /// # Panics
    ///
    /// * May panic or reallocate if the collection is full
    /// * Panics if index > len.
    pub fn insert(&mut self, index: usize, value: T) -> &mut T {
        #[cold]
        #[inline(never)]
        fn insert_fail(index: usize, len: usize) -> ! {
            panic!("Tried to insert at {}, but length is {}", index, len);
        }

        if index > self.len() {
            insert_fail(index, self.len())
        }

        if self.is_full() {
            self.reserve(1);
        }

        // Safety
        //
        // * we reserve enough space for 1 more element
        // * we verify that index is in bounds
        unsafe { self.insert_unchecked(index, value) }
    }

    /// Inserts the array at position index within the vector,
    /// shifting all elements after it to the right.
    ///
    /// # Panics
    ///
    /// * May panic or reallocate if the collection has less than N elements remaining
    /// * Panics if index > len.
    #[cfg(any(doc, feature = "nightly"))]
    pub fn insert_array<const N: usize>(&mut self, index: usize, value: [T; N]) -> &mut [T; N] {
        #[cold]
        #[inline(never)]
        fn insert_array_fail(index: usize, size: usize, len: usize) -> ! {
            panic!(
                "Tried to insert array of length {} at {}, but length is {}",
                size, index, len
            );
        }

        if index > self.len() {
            insert_array_fail(index, N, self.len())
        }

        self.reserve(N);

        // Safety
        //
        // * we reserve enough space for N more elements
        // * we verify that index is in bounds
        unsafe { self.insert_array_unchecked(index, value) }
    }

    /// Removes the last element from a vector and returns it
    ///
    /// # Panics
    ///
    /// Panics if the collection is empty
    pub fn pop(&mut self) -> T {
        #[cold]
        #[inline(never)]
        fn pop_fail() -> ! {
            panic!("Tried to pop an element from an empty vector",);
        }

        if self.is_empty() {
            pop_fail()
        }

        // Safety
        //
        // * we verify we are not empty
        unsafe { self.pop_unchecked() }
    }

    /// Removes the last `N` elements from a vector and returns it
    ///
    /// # Panics
    ///
    /// Panics if the collection contains less than `N` elements in it
    #[cfg(any(doc, feature = "nightly"))]
    pub fn pop_array<const N: usize>(&mut self) -> [T; N] {
        #[cold]
        #[inline(never)]
        fn pop_array_fail(size: usize, len: usize) -> ! {
            panic!("Tried to pop an array of size {}, a vector of length {}", size, len);
        }

        if self.len() < N {
            pop_array_fail(N, self.len())
        }

        // Safety
        //
        // * we verify we have at least N elements
        unsafe { self.pop_array_unchecked() }
    }

    /// Removes and returns the element at position index within the vector,
    /// shifting all elements after it to the left.
    ///
    /// # Panics
    ///
    /// Panics if `index` is out of bounds.
    pub fn remove(&mut self, index: usize) -> T {
        #[cold]
        #[inline(never)]
        fn remove_fail(index: usize, len: usize) -> ! {
            panic!("Tried to remove an element at {}, but length is {}", index, len);
        }

        if index > self.len() {
            remove_fail(index, self.len())
        }

        // Safety
        //
        // * we verify that the index is in bounds
        unsafe { self.remove_unchecked(index) }
    }

    /// Removes and returns `N` elements at position index within the vector,
    /// shifting all elements after it to the left.
    ///
    /// # Panics
    ///
    /// Panics if `index` is out of bounds or if `index + N > len()`
    #[cfg(any(doc, feature = "nightly"))]
    pub fn remove_array<const N: usize>(&mut self, index: usize) -> [T; N] {
        #[cold]
        #[inline(never)]
        fn remove_array_fail(index: usize, size: usize, len: usize) -> ! {
            panic!(
                "Tried to remove an array length {} at {}, but length is {}",
                size, index, len
            );
        }

        if self.len() < index || self.len().wrapping_sub(index) < N {
            remove_array_fail(index, N, self.len())
        }

        // Safety
        //
        // * we verify that the index is in bounds
        // * we verify that there are at least `N` elements
        //   after the index
        unsafe { self.remove_array_unchecked(index) }
    }

    /// Removes an element from the vector and returns it.
    ///
    /// The removed element is replaced by the last element of the vector.
    ///
    /// This does not preserve ordering, but is O(1).
    ///
    /// # Panics
    ///
    /// Panics if `index` is out of bounds.
    pub fn swap_remove(&mut self, index: usize) -> T {
        #[cold]
        #[inline(never)]
        fn swap_remove_fail(index: usize, len: usize) -> ! {
            panic!("Tried to remove an element at {}, but length is {}", index, len);
        }

        if index > self.len() {
            swap_remove_fail(index, self.len())
        }

        // Safety
        //
        // * we verify that the index is in bounds
        unsafe { self.swap_remove_unchecked(index) }
    }

    /// Tries to append an element to the back of a collection.
    /// Returns the `Err(value)` if the collection is full
    ///
    /// Guaranteed to not panic/abort/allocate
    pub fn try_push(&mut self, value: T) -> Result<&mut T, T> {
        if self.is_full() {
            Err(value)
        } else {
            // Safety
            //
            // * we reserve enough space for 1 more element
            unsafe { Ok(self.push_unchecked(value)) }
        }
    }

    /// Tries to append an array to the back of a collection.
    /// Returns the `Err(value)` if the collection doesn't have enough remaining capacity
    /// to hold `N` elements.
    ///
    /// Guaranteed to not panic/abort/allocate
    #[cfg(any(doc, feature = "nightly"))]
    pub fn try_push_array<const N: usize>(&mut self, value: [T; N]) -> Result<&mut [T; N], [T; N]> {
        if self.remaining_capacity() < N {
            Err(value)
        } else {
            // Safety
            //
            // * we reserve enough space for N more elements
            unsafe { Ok(self.push_array_unchecked(value)) }
        }
    }

    /// Inserts an element at position index within the vector,
    /// shifting all elements after it to the right.
    /// Returns the `Err(value)` if the collection is full or index is out of bounds
    ///
    /// Guaranteed to not panic/abort/allocate
    pub fn try_insert(&mut self, index: usize, value: T) -> Result<&mut T, T> {
        if self.is_full() || index > self.len() {
            Err(value)
        } else {
            // Safety
            //
            // * we reserve enough space for 1 more element
            // * we verify that index is in bounds
            unsafe { Ok(self.insert_unchecked(index, value)) }
        }
    }

    /// Inserts an array at position index within the vector,
    /// shifting all elements after it to the right.
    /// Returns the `Err(value)` if the collection doesn't have enough remaining capacity
    /// to hold `N` elements or index is out of bounds
    ///
    /// Guaranteed to not panic/abort/allocate
    #[cfg(any(doc, feature = "nightly"))]
    pub fn try_insert_array<const N: usize>(&mut self, index: usize, value: [T; N]) -> Result<&mut [T; N], [T; N]> {
        if self.capacity().wrapping_sub(self.len()) < N || index > self.len() {
            Err(value)
        } else {
            // Safety
            //
            // * we reserve enough space for N more elements
            // * we verify that index is in bounds
            unsafe { Ok(self.insert_array_unchecked(index, value)) }
        }
    }

    /// Removes the last element from a vector and returns it,
    /// Returns `None` if the collection is empty
    ///
    /// Guaranteed to not panic/abort/allocate
    pub fn try_pop(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            // Safety
            //
            // * we verify we are not empty
            unsafe { Some(self.pop_unchecked()) }
        }
    }

    /// Removes the last `N` elements from a vector and returns it,
    /// Returns `None` if the collection is has less than N elements
    ///
    /// Guaranteed to not panic/abort/allocate
    #[cfg(any(doc, feature = "nightly"))]
    pub fn try_pop_array<const N: usize>(&mut self) -> Option<[T; N]> {
        if self.is_empty() {
            None
        } else {
            // Safety
            //
            // * we verify we have at least N elements
            unsafe { Some(self.pop_array_unchecked()) }
        }
    }

    /// Removes and returns the element at position index within the vector,
    /// shifting all elements after it to the left.
    /// Returns `None` if collection is empty or `index` is out of bounds.
    ///
    /// Guaranteed to not panic/abort/allocate
    pub fn try_remove(&mut self, index: usize) -> Option<T> {
        if self.len() < index {
            None
        } else {
            // Safety
            //
            // * we verify that the index is in bounds
            unsafe { Some(self.remove_unchecked(index)) }
        }
    }

    /// Removes and returns the element at position index within the vector,
    /// shifting all elements after it to the left.
    /// Returns `None` if the collection is has less than N elements
    /// or `index` is out of bounds.
    ///
    /// Guaranteed to not panic/abort/allocate
    #[cfg(any(doc, feature = "nightly"))]
    pub fn try_remove_array<const N: usize>(&mut self, index: usize) -> Option<[T; N]> {
        if self.len() < index || self.len().wrapping_sub(index) < N {
            None
        } else {
            // Safety
            //
            // * we verify that the index is in bounds
            // * we verify that there are at least `N` elements
            //   after the index
            unsafe { Some(self.remove_array_unchecked(index)) }
        }
    }

    /// Removes an element from the vector and returns it.
    /// Returns `None` if collection is empty or `index` is out of bounds.
    ///
    /// The removed element is replaced by the last element of the vector.
    ///
    /// This does not preserve ordering, but is O(1).
    ///
    /// Guaranteed to not panic/abort/allocate
    pub fn try_swap_remove(&mut self, index: usize) -> Option<T> {
        if index < self.len() {
            // Safety
            //
            // * we verify that the index is in bounds
            unsafe { Some(self.swap_remove_unchecked(index)) }
        } else {
            None
        }
    }

    /// Appends an element to the back of a collection.
    ///
    /// # Safety
    ///
    /// the collection must not be full
    pub unsafe fn push_unchecked(&mut self, value: T) -> &mut T {
        if Some(0) == S::CONST_CAPACITY {
            panic!("Tried to push an element into a zero-capacity vector!")
        }

        debug_assert_ne!(
            self.len(),
            self.capacity(),
            "Tried to `push_unchecked` past capacity! This is UB in release mode"
        );

        // Safety
        //
        // the collection isn't full, so `ptr.add(len)` is valid to write
        unsafe {
            let len = self.len();
            self.set_len_unchecked(len.wrapping_add(1));
            let ptr = self.as_mut_ptr().add(len);
            ptr.write(value);
            &mut *ptr
        }
    }

    /// Appends the array to the back of a collection.
    ///
    /// # Safety
    ///
    /// the collection's remaining capacity must be at least N
    #[cfg(any(doc, feature = "nightly"))]
    pub unsafe fn push_array_unchecked<const N: usize>(&mut self, value: [T; N]) -> &mut [T; N] {
        match S::CONST_CAPACITY {
            Some(n) if n < N => {
                panic!("Tried to push an array larger than the maximum capacity of the vector!")
            }
            _ => (),
        }

        // Safety
        //
        // the collection has at least N remaining elements of capacity left,
        // so `ptr.add(len)` is valid to write `N` elements
        unsafe {
            let len = self.len();
            self.set_len_unchecked(len.wrapping_add(N));
            let ptr = self.as_mut_ptr();
            let out = ptr.add(len) as *mut [T; N];
            out.write(value);
            &mut *out
        }
    }

    /// Inserts an element at position index within the vector,
    /// shifting all elements after it to the right.
    ///
    /// # Safety
    ///
    /// * the collection is must not be full
    /// * hte index must be in bounds
    pub unsafe fn insert_unchecked(&mut self, index: usize, value: T) -> &mut T {
        unsafe {
            if Some(0) == S::CONST_CAPACITY {
                panic!("Tried to insert an element into a zero-capacity vector!")
            }

            // Safety
            //
            // * the index is in bounds
            // * the collection is't full so `ptr.add(len)` is valid to write 1 element
            let len = self.len();
            self.set_len_unchecked(len.wrapping_add(1));
            let ptr = self.storage.as_mut_ptr().add(index);
            ptr.add(1).copy_from(ptr, len.wrapping_sub(index));
            ptr.write(value);
            &mut *ptr
        }
    }

    /// Inserts an array at position index within the vector,
    /// shifting all elements after it to the right.
    ///
    /// # Safety
    ///
    /// * the collection's remaining capacity must be at least N
    /// * hte index must be in bounds
    #[cfg(any(doc, feature = "nightly"))]
    pub unsafe fn insert_array_unchecked<const N: usize>(&mut self, index: usize, value: [T; N]) -> &mut [T; N] {
        match S::CONST_CAPACITY {
            Some(n) if n < N => {
                panic!("Tried to push an array larger than the maximum capacity of the vector!")
            }
            _ => (),
        }

        // Safety
        //
        // * the index is in bounds
        // * the collection has at least N remaining elements of capacity left,
        //   so `ptr.add(len)` is valid to write `N` elements
        unsafe {
            let len = self.len();
            self.set_len_unchecked(len.wrapping_add(N));
            let ptr = self.as_mut_ptr();
            let dist = len.wrapping_sub(index);

            let out = ptr.add(index);
            out.add(N).copy_from(out, dist);
            let out = out as *mut [T; N];
            out.write(value);
            &mut *out
        }
    }

    /// Removes the last element from a vector and returns it
    ///
    /// # Safety
    ///
    /// the collection must not be empty
    pub unsafe fn pop_unchecked(&mut self) -> T {
        if Some(0) == S::CONST_CAPACITY {
            panic!("Tried to remove an element from a zero-capacity vector!")
        }

        let len = self.len();
        debug_assert_ne!(
            len, 0,
            "Tried to `pop_unchecked` an empty array vec! This is UB in release mode"
        );

        // Safety
        //
        // * the collection isn't empty, so `ptr.add(len - 1)` is valid to read
        unsafe {
            let len = len.wrapping_sub(1);
            self.set_len_unchecked(len);
            self.as_mut_ptr().add(len).read()
        }
    }

    /// Removes the last `N` elements from a vector and returns it
    ///
    /// # Safety
    ///
    /// The collection must contain at least `N` elements in it
    #[cfg(any(doc, feature = "nightly"))]
    pub unsafe fn pop_array_unchecked<const N: usize>(&mut self) -> [T; N] {
        match S::CONST_CAPACITY {
            Some(n) if n < N => panic!("Tried to remove {} elements from a {} capacity vector!", N, n),
            _ => (),
        }

        let len = self.len();
        debug_assert!(
            len > N,
            "Tried to remove {} elements from a {} length vector! This is UB in release mode",
            N,
            len,
        );
        // Safety
        //
        // * the collection has at least `N` elements, so `ptr.add(len - N)` is valid to read `N` elements
        unsafe {
            let len = len.wrapping_sub(N);
            self.set_len_unchecked(len);
            self.as_mut_ptr().add(len).cast::<[T; N]>().read()
        }
    }

    /// Removes and returns the element at position index within the vector,
    /// shifting all elements after it to the left.
    ///
    /// # Safety
    ///
    /// the collection must not be empty, and
    /// index must be in bounds
    pub unsafe fn remove_unchecked(&mut self, index: usize) -> T {
        if Some(0) == S::CONST_CAPACITY {
            panic!("Tried to remove an element from a zero-capacity vector!")
        }

        let len = self.len();

        debug_assert!(
            index <= len,
            "Tried to remove an element at index {} from a {} length vector! This is UB in release mode",
            index,
            len,
        );

        // Safety
        //
        // * the index is in bounds
        // * the collection isn't empty, so `ptr.add(len - index - 1)` is valid to read
        unsafe {
            self.set_len_unchecked(len.wrapping_sub(1));
            let ptr = self.storage.as_mut_ptr().add(index);
            let value = ptr.read();
            ptr.copy_from(ptr.add(1), len.wrapping_sub(index).wrapping_sub(1));
            value
        }
    }

    /// Removes and returns the element at position index within the vector,
    /// shifting all elements after it to the left.
    ///
    /// # Safety
    ///
    /// the collection must contain at least N elements, and
    /// index must be in bounds
    #[cfg(any(doc, feature = "nightly"))]
    pub unsafe fn remove_array_unchecked<const N: usize>(&mut self, index: usize) -> [T; N] {
        match S::CONST_CAPACITY {
            Some(n) if n < N => panic!("Tried to remove {} elements from a {} capacity vector!", N, n),
            _ => (),
        }

        let len = self.len();
        debug_assert!(
            index <= len,
            "Tried to remove elements at index {} from a {} length vector! This is UB in release mode",
            index,
            len,
        );
        debug_assert!(
            len.wrapping_sub(index) > N,
            "Tried to remove {} elements from a {} length vector! This is UB in release mode",
            N,
            len,
        );

        // Safety
        //
        // * the index is in bounds
        // * the collection isn't empty, so `ptr.add(len - index - N)` is valid to read `N` elements
        unsafe {
            self.set_len_unchecked(len.wrapping_sub(N));
            let ptr = self.as_mut_ptr().add(index);
            let value = ptr.cast::<[T; N]>().read();
            if N != 0 {
                ptr.copy_from(ptr.add(N), len.wrapping_sub(index).wrapping_sub(N));
            }
            value
        }
    }

    /// Removes an element from the vector and returns it.
    ///
    /// The removed element is replaced by the last element of the vector.
    ///
    /// This does not preserve ordering, but is O(1).
    ///
    /// # Safety
    ///
    /// the `index` must be in bounds
    pub unsafe fn swap_remove_unchecked(&mut self, index: usize) -> T {
        if Some(0) == S::CONST_CAPACITY {
            panic!("Tried to remove an element from a zero-capacity vector!")
        }

        // Safety
        //
        // * the index is in bounds
        // * the collection isn't empty
        unsafe {
            let len = self.len();
            self.set_len_unchecked(len.wrapping_sub(1));
            let ptr = self.storage.as_mut_ptr();
            let at = ptr.add(index);
            let end = ptr.add(len.wrapping_sub(1));
            let value = at.read();
            at.copy_from(end, 1);
            value
        }
    }

    /// Splits the collection into two at the given index.
    ///
    /// Returns a newly allocated vector containing the elements in the range `[at, len)`.
    /// After the call, the original vector will be left containing the elements `[0, at)`
    /// with its previous capacity unchanged.
    ///
    /// ```rust
    /// # use generic_vec::{gvec, SliceVec, uninit_array};
    /// # let mut vec_buf = uninit_array!(3);
    /// # let mut vec2_buf = uninit_array!(5);
    /// # let mut vec: SliceVec<_> = SliceVec::new(&mut vec_buf); vec.extend([1, 2, 3].iter().copied());
    /// # let mut vec2: SliceVec<_> = SliceVec::new(&mut vec2_buf); vec2.extend([4, 5, 6].iter().copied());
    /// assert_eq!(vec, [1, 2, 3]);
    /// assert_eq!(vec2, [4, 5, 6]);
    /// vec.split_off_into(1, &mut vec2);
    /// assert_eq!(vec, [1]);
    /// assert_eq!(vec2, [4, 5, 6, 2, 3]);
    /// ```
    pub fn split_off<B>(&mut self, index: usize) -> GenericVec<T, B>
    where
        B: raw::StorageWithCapacity<T>,
    {
        assert!(
            index <= self.len(),
            "Tried to split at index {}, but length is {}",
            index,
            self.len()
        );

        let mut vec = GenericVec::<T, B>::__with_capacity__const_capacity_checked(
            self.len().wrapping_sub(index),
            S::CONST_CAPACITY,
        );

        self.split_off_into(index, &mut vec);

        vec
    }

    /// Splits the collection into two at the given index.
    ///
    /// Appends the elements from the range `[at, len)` to `other`.
    /// After the call, the original vector will be left containing the elements `[0, at)`
    /// with its previous capacity unchanged.
    ///
    /// ```rust
    /// # use generic_vec::{gvec, SliceVec, uninit_array};
    /// # let mut vec_buf = uninit_array!(3);
    /// # let mut vec2_buf = uninit_array!(5);
    /// # let mut vec: SliceVec<_> = SliceVec::new(&mut vec_buf); vec.extend([1, 2, 3].iter().copied());
    /// # let mut vec2: SliceVec<_> = SliceVec::new(&mut vec2_buf); vec2.extend([4, 5, 6].iter().copied());
    /// assert_eq!(vec, [1, 2, 3]);
    /// assert_eq!(vec2, [4, 5, 6]);
    /// vec.split_off_into(1, &mut vec2);
    /// assert_eq!(vec, [1]);
    /// assert_eq!(vec2, [4, 5, 6, 2, 3]);
    /// ```
    pub fn split_off_into<B>(&mut self, index: usize, other: &mut GenericVec<T, B>)
    where
        B: raw::Storage<T> + ?Sized,
    {
        assert!(
            index <= self.len(),
            "Tried to split at index {}, but length is {}",
            index,
            self.len()
        );

        unsafe {
            // Safety
            //
            // * the index is in bounds
            // * other has reserved enough space
            // * we ignore all elements after index
            let slice = self.get_unchecked(index..);
            other.reserve(slice.len());
            other.extend_from_slice_unchecked(slice);
            self.set_len_unchecked(index);
        }
    }

    /// Moves all the elements of `other` into `Self`, leaving `other` empty.
    ///
    /// Does not change the capacity of either collection.
    ///
    /// ```rust
    /// # use generic_vec::{gvec, SliceVec, uninit_array};
    /// # let mut vec_buf = uninit_array!(6);
    /// # let mut vec2_buf = uninit_array!(3);
    /// # let mut vec: SliceVec<_> = SliceVec::new(&mut vec_buf); vec.extend([1, 2, 3].iter().copied());
    /// # let mut vec2: SliceVec<_> = SliceVec::new(&mut vec2_buf); vec2.extend([4, 5, 6].iter().copied());
    /// assert_eq!(vec, [1, 2, 3]);
    /// assert_eq!(vec2, [4, 5, 6]);
    /// vec.append(&mut vec2);
    /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]);
    /// assert_eq!(vec2, []);
    /// ```
    ///
    /// # Panic
    ///
    /// May panic or reallocate if the collection is full
    pub fn append<B: Storage<T> + ?Sized>(&mut self, other: &mut GenericVec<T, B>) { other.split_off_into(0, self) }

    /// Convert the backing storage type, and moves all the elements in `self` to the new vector
    pub fn convert<B: raw::StorageWithCapacity<T>>(mut self) -> GenericVec<T, B>
    where
        S: Sized,
    {
        self.split_off(0)
    }

    /// Creates a raw cursor that can be used to remove elements in the specified range.
    /// Usage of [`RawCursor`](iter::RawCursor) is `unsafe` because it doesn't do any checks.
    /// [`RawCursor`](iter::RawCursor) is meant to be a low level tool to implement fancier
    /// iterators, like [`GenericVec::drain`], [`GenericVec::drain_filter`],
    /// or [`GenericVec::splice`].
    ///
    /// # Panic
    ///
    /// Panics if the starting point is greater than the end point or if the end point
    /// is greater than the length of the vector.
    #[inline]
    pub fn raw_cursor<R>(&mut self, range: R) -> iter::RawCursor<'_, T, S>
    where
        R: RangeBounds<usize>,
    {
        let range = slice::check_range(self.len(), range);
        iter::RawCursor::new(self, range)
    }

    /// Creates a cursor that can be used to remove elements in the specified range.
    ///
    /// # Panic
    ///
    /// Panics if the starting point is greater than the end point or if the end point
    /// is greater than the length of the vector.
    #[inline]
    pub fn cursor<R>(&mut self, range: R) -> iter::Cursor<'_, T, S>
    where
        R: RangeBounds<usize>,
    {
        iter::Cursor::new(self.raw_cursor(range))
    }

    /// Creates a draining iterator that removes the specified range in the
    /// vector and yields the removed items.
    ///
    /// When the iterator is dropped, all elements in the range are removed from
    /// the vector, even if the iterator was not fully consumed. If the iterator
    /// is not dropped (with `mem::forget` for example), it is unspecified how many
    /// elements are removed.
    ///
    /// # Panic
    ///
    /// Panics if the starting point is greater than the end point or if the end point
    /// is greater than the length of the vector.
    #[inline]
    pub fn drain<R>(&mut self, range: R) -> iter::Drain<'_, T, S>
    where
        R: RangeBounds<usize>,
    {
        iter::Drain::new(self.raw_cursor(range))
    }

    /// Creates an iterator which uses a closure to determine if an element should be removed.
    ///
    /// If the closure returns true, then the element is removed and yielded.
    /// If the closure returns false, the element will remain in the vector
    /// and will not be yielded by the iterator.
    ///
    /// # Panic
    ///
    /// Panics if the starting point is greater than the end point or if the end point
    /// is greater than the length of the vector.
    #[inline]
    pub fn drain_filter<R, F>(&mut self, range: R, f: F) -> iter::DrainFilter<'_, T, S, F>
    where
        R: RangeBounds<usize>,
        F: FnMut(&mut T) -> bool,
    {
        iter::DrainFilter::new(self.raw_cursor(range), f)
    }

    /// Creates a splicing iterator that replaces the specified range in the vector with
    /// the given replace_with iterator and yields the removed items. replace_with does
    /// not need to be the same length as range.
    ///
    /// range is removed even if the iterator is not consumed until the end.
    ///
    /// It is unspecified how many elements are removed from the vector if the
    /// [`Splice`](iter::Splice) value is leaked.
    ///
    /// The input iterator replace_with is only consumed when the [`Splice`](iter::Splice)
    /// value is dropped
    ///
    /// # Panic
    ///
    /// Panics if the starting point is greater than the end point or if the end point
    /// is greater than the length of the vector.
    #[inline]
    pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> iter::Splice<'_, T, S, I::IntoIter>
    where
        R: RangeBounds<usize>,
        I: IntoIterator<Item = T>,
    {
        iter::Splice::new(self.raw_cursor(range), replace_with.into_iter())
    }

    /// Retains only the elements specified by the predicate.
    ///
    /// In other words, remove all elements `e` such that `f(e)` returns false.
    /// This method operates in place, visiting each element exactly once in
    /// the original order, and preserves the order of the retained elements.
    #[inline]
    pub fn retain<F>(&mut self, f: F)
    where
        F: FnMut(&mut T) -> bool,
    {
        fn not<F: FnMut(&mut T) -> bool, T>(mut f: F) -> impl FnMut(&mut T) -> bool { move |value| !f(value) }
        self.drain_filter(.., not(f));
    }

    /// Shallow copies and appends all elements in a slice to the `GenericVec`.
    ///
    /// # Safety
    ///
    /// * You must not drop any of the elements in `slice`
    /// * There must be at least `slice.len()` remaining capacity in the vector
    pub unsafe fn extend_from_slice_unchecked(&mut self, slice: &[T]) {
        debug_assert!(
            self.remaining_capacity() >= slice.len(),
            "Not enough capacity to hold the slice"
        );

        unsafe {
            let len = self.len();
            self.as_mut_ptr()
                .add(len)
                .copy_from_nonoverlapping(slice.as_ptr(), slice.len());
            self.set_len_unchecked(len.wrapping_add(slice.len()));
        }
    }

    /// Clones and appends all elements in a slice to the `GenericVec`.
    ///
    /// Iterates over the slice other, clones each element, and then appends
    /// it to this `GenericVec`. The other vector is traversed in-order.
    ///
    /// Note that this function is same as extend except that it is specialized
    /// to work with slices instead. If and when Rust gets specialization this
    /// function will likely be deprecated (but still available).
    ///
    /// # Panic behavor
    ///
    /// If `T::clone` panics, then all newly added items will be dropped. This is different
    /// from `std`, where on panic, newly added items will stay in the `Vec`. This behavior
    /// is unstable, and may change in the future.
    pub fn extend_from_slice(&mut self, slice: &[T])
    where
        T: Clone,
    {
        self.reserve(self.len());

        // Safety
        //
        // We reserved enough space
        unsafe { extension::Extension::extend_from_slice(self, slice) }
    }

    /// Replaces all of the current elements with the ones in the slice
    ///
    /// equivalent to the following
    ///
    /// ```rust
    /// # let slice = [];
    /// # let mut buffer = generic_vec::uninit_array!(0);
    /// # let mut vec = generic_vec::SliceVec::<()>::new(&mut buffer);
    /// vec.clear();
    /// vec.extend_from_slice(&slice);
    /// ```
    ///
    /// # Panic
    ///
    /// May try to panic/reallocate if there is not enough capacity for the slice
    pub fn clone_from(&mut self, source: &[T])
    where
        T: Clone,
    {
        // If the `self` is longer than `source`, remove excess
        self.truncate(source.len());

        // `self` is now at most the same length as `source`
        //
        // * `init.len() == self.len()`
        // * tail is the rest of the `source`, in the case
        //     that `self` is smaller than `source`
        let (init, tail) = source.split_at(self.len());

        // Clone in the beginning, using `slice::clone_from_slice`
        self.clone_from_slice(init);

        // Append the remaining elements
        self.extend_from_slice(tail);
    }

    /// Removes all but the first of consecutive elements in the vector satisfying
    /// a given equality relation.
    ///
    /// The same_bucket function is passed references to two elements from the
    /// vector and must determine if the elements compare equal. The elements
    /// are passed in opposite order from their order in the slice, so if
    /// same_bucket(a, b) returns true, a is removed.
    ///
    /// If the vector is sorted, this removes all duplicates.
    pub fn dedup_by<F>(&mut self, same_bucket: F)
    where
        F: FnMut(&mut T, &mut T) -> bool,
    {
        let (a, _) = slice::partition_dedup_by(self.as_mut_slice(), same_bucket);
        let new_len = a.len();
        self.truncate(new_len);
    }

    /// Removes all but the first of consecutive elements in the vector that resolve to the same key.
    ///
    /// If the vector is sorted, this removes all duplicates.
    pub fn dedup_by_key<F, K>(&mut self, key: F)
    where
        F: FnMut(&mut T) -> K,
        K: PartialEq,
    {
        #[inline]
        fn key_to_same_bucket<T, F, K>(mut f: F) -> impl FnMut(&mut T, &mut T) -> bool
        where
            F: FnMut(&mut T) -> K,
            K: PartialEq,
        {
            #[inline]
            move |a, b| {
                let a = f(a);
                let b = f(b);
                a == b
            }
        }

        self.dedup_by(key_to_same_bucket(key))
    }

    /// Removes all but the first of consecutive elements in the vector that resolve to the same key.
    ///
    /// If the vector is sorted, this removes all duplicates.
    pub fn dedup<F, K>(&mut self)
    where
        T: PartialEq,
    {
        #[inline]
        fn eq_to_same_buckets<T, F>(mut f: F) -> impl FnMut(&mut T, &mut T) -> bool
        where
            F: FnMut(&T, &T) -> bool,
        {
            #[inline]
            move |a, b| f(a, b)
        }

        self.dedup_by(eq_to_same_buckets(PartialEq::eq))
    }
}