len: LenUint,

// the `len` first elements of the array are initialized

xs: [MaybeUninit<T>; CAP],

fn drop(&mut self) {

self.clear();

// MaybeUninit inhibits array's drop

}

($method_name:expr, $index:expr, $len:expr) => {

panic!(concat!("ArrayVec::", $method_name, ": index {} is out of bounds in vector of length {}"),

$index, $len)

}

/// Capacity

const CAPACITY: usize = CAP;

/// Create a new empty `ArrayVec`.

///

/// The maximum capacity is given by the generic parameter `CAP`.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::<_, 16>::new();

/// array.push(1);

/// array.push(2);

/// assert_eq!(&array[..], &[1, 2]);

/// assert_eq!(array.capacity(), 16);

/// ```

#[inline]

#[track_caller]

pub fn new() -> ArrayVec<T, CAP> {

assert_capacity_limit!(CAP);

unsafe {

ArrayVec { xs: MaybeUninit::uninit().assume_init(), len: 0 }

}

}

/// Create a new empty `ArrayVec` (const fn).

///

/// The maximum capacity is given by the generic parameter `CAP`.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// static ARRAY: ArrayVec<u8, 1024> = ArrayVec::new_const();

/// ```

pub const fn new_const() -> ArrayVec<T, CAP> {

assert_capacity_limit_const!(CAP);

ArrayVec { xs: MakeMaybeUninit::ARRAY, len: 0 }

}

/// Return the number of elements in the `ArrayVec`.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::from([1, 2, 3]);

/// array.pop();

/// assert_eq!(array.len(), 2);

/// ```

#[inline(always)]

pub const fn len(&self) -> usize { self.len as usize }

/// Returns whether the `ArrayVec` is empty.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::from([1]);

/// array.pop();

/// assert_eq!(array.is_empty(), true);

/// ```

#[inline]

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

/// Return the capacity of the `ArrayVec`.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let array = ArrayVec::from([1, 2, 3]);

/// assert_eq!(array.capacity(), 3);

/// ```

#[inline(always)]

pub const fn capacity(&self) -> usize { CAP }

/// Return true if the `ArrayVec` is completely filled to its capacity, false otherwise.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::<_, 1>::new();

/// assert!(!array.is_full());

/// array.push(1);

/// assert!(array.is_full());

/// ```

pub const fn is_full(&self) -> bool { self.len() == self.capacity() }

/// Returns the capacity left in the `ArrayVec`.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::from([1, 2, 3]);

/// array.pop();

/// assert_eq!(array.remaining_capacity(), 1);

/// ```

pub const fn remaining_capacity(&self) -> usize {

self.capacity() - self.len()

}

/// Push `element` to the end of the vector.

///

/// ***Panics*** if the vector is already full.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::<_, 2>::new();

///

/// array.push(1);

/// array.push(2);

///

/// assert_eq!(&array[..], &[1, 2]);

/// ```

#[track_caller]

pub fn push(&mut self, element: T) {

ArrayVecImpl::push(self, element)

}

/// Push `element` to the end of the vector.

///

/// Return `Ok` if the push succeeds, or return an error if the vector

/// is already full.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::<_, 2>::new();

///

/// let push1 = array.try_push(1);

/// let push2 = array.try_push(2);

///

/// assert!(push1.is_ok());

/// assert!(push2.is_ok());

///

/// assert_eq!(&array[..], &[1, 2]);

///

/// let overflow = array.try_push(3);

///

/// assert!(overflow.is_err());

/// ```

pub fn try_push(&mut self, element: T) -> Result<(), CapacityError<T>> {

ArrayVecImpl::try_push(self, element)

}

/// Push `element` to the end of the vector without checking the capacity.

///

/// It is up to the caller to ensure the capacity of the vector is

/// sufficiently large.

///

/// This method uses *debug assertions* to check that the arrayvec is not full.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::<_, 2>::new();

///

/// if array.len() + 2 <= array.capacity() {

/// unsafe {

/// array.push_unchecked(1);

/// array.push_unchecked(2);

/// }

/// }

///

/// assert_eq!(&array[..], &[1, 2]);

/// ```

pub unsafe fn push_unchecked(&mut self, element: T) {

ArrayVecImpl::push_unchecked(self, element)

}

/// 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.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::from([1, 2, 3, 4, 5]);

/// array.truncate(3);

/// assert_eq!(&array[..], &[1, 2, 3]);

/// array.truncate(4);

/// assert_eq!(&array[..], &[1, 2, 3]);

/// ```

pub fn truncate(&mut self, new_len: usize) {

ArrayVecImpl::truncate(self, new_len)

}

/// Remove all elements in the vector.

pub fn clear(&mut self) {

ArrayVecImpl::clear(self)

}

/// Get pointer to where element at `index` would be

unsafe fn get_unchecked_ptr(&mut self, index: usize) -> *mut T {

self.as_mut_ptr().add(index)

}

/// Insert `element` at position `index`.

///

/// Shift up all elements after `index`.

///

/// It is an error if the index is greater than the length or if the

/// arrayvec is full.

///

/// ***Panics*** if the array is full or the `index` is out of bounds. See

/// `try_insert` for fallible version.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::<_, 2>::new();

///

/// array.insert(0, "x");

/// array.insert(0, "y");

/// assert_eq!(&array[..], &["y", "x"]);

///

/// ```

#[track_caller]

pub fn insert(&mut self, index: usize, element: T) {

self.try_insert(index, element).unwrap()

}

/// Insert `element` at position `index`.

///

/// Shift up all elements after `index`; the `index` must be less than

/// or equal to the length.

///

/// Returns an error if vector is already at full capacity.

///

/// ***Panics*** `index` is out of bounds.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::<_, 2>::new();

///

/// assert!(array.try_insert(0, "x").is_ok());

/// assert!(array.try_insert(0, "y").is_ok());

/// assert!(array.try_insert(0, "z").is_err());

/// assert_eq!(&array[..], &["y", "x"]);

///

/// ```

pub fn try_insert(&mut self, index: usize, element: T) -> Result<(), CapacityError<T>> {

if index > self.len() {

panic_oob!("try_insert", index, self.len())

}

if self.len() == self.capacity() {

return Err(CapacityError::new(element));

}

let len = self.len();

// follows is just like Vec<T>

unsafe { // infallible

// The spot to put the new value

{

let p: *mut _ = self.get_unchecked_ptr(index);

// Shift everything over to make space. (Duplicating the

// `index`th element into two consecutive places.)

ptr::copy(p, p.offset(1), len - index);

// Write it in, overwriting the first copy of the `index`th

// element.

ptr::write(p, element);

}

self.set_len(len + 1);

}

Ok(())

}

/// Remove the last element in the vector and return it.

///

/// Return `Some(` *element* `)` if the vector is non-empty, else `None`.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::<_, 2>::new();

///

/// array.push(1);

///

/// assert_eq!(array.pop(), Some(1));

/// assert_eq!(array.pop(), None);

/// ```

pub fn pop(&mut self) -> Option<T> {

ArrayVecImpl::pop(self)

}

/// Remove the element at `index` and swap the last element into its place.

///

/// This operation is O(1).

///

/// Return the *element* if the index is in bounds, else panic.

///

/// ***Panics*** if the `index` is out of bounds.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::from([1, 2, 3]);

///

/// assert_eq!(array.swap_remove(0), 1);

/// assert_eq!(&array[..], &[3, 2]);

///

/// assert_eq!(array.swap_remove(1), 2);

/// assert_eq!(&array[..], &[3]);

/// ```

pub fn swap_remove(&mut self, index: usize) -> T {

self.swap_pop(index)

.unwrap_or_else(|| {

panic_oob!("swap_remove", index, self.len())

})

}

/// Remove the element at `index` and swap the last element into its place.

///

/// This is a checked version of `.swap_remove`.

/// This operation is O(1).

///

/// Return `Some(` *element* `)` if the index is in bounds, else `None`.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::from([1, 2, 3]);

///

/// assert_eq!(array.swap_pop(0), Some(1));

/// assert_eq!(&array[..], &[3, 2]);

///

/// assert_eq!(array.swap_pop(10), None);

/// ```

pub fn swap_pop(&mut self, index: usize) -> Option<T> {

let len = self.len();

if index >= len {

return None;

}

self.swap(index, len - 1);

self.pop()

}

/// Remove the element at `index` and shift down the following elements.

///

/// The `index` must be strictly less than the length of the vector.

///

/// ***Panics*** if the `index` is out of bounds.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::from([1, 2, 3]);

///

/// let removed_elt = array.remove(0);

/// assert_eq!(removed_elt, 1);

/// assert_eq!(&array[..], &[2, 3]);

/// ```

pub fn remove(&mut self, index: usize) -> T {

self.pop_at(index)

.unwrap_or_else(|| {

panic_oob!("remove", index, self.len())

})

}

/// Remove the element at `index` and shift down the following elements.

///

/// This is a checked version of `.remove(index)`. Returns `None` if there

/// is no element at `index`. Otherwise, return the element inside `Some`.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::from([1, 2, 3]);

///

/// assert!(array.pop_at(0).is_some());

/// assert_eq!(&array[..], &[2, 3]);

///

/// assert!(array.pop_at(2).is_none());

/// assert!(array.pop_at(10).is_none());

/// ```

pub fn pop_at(&mut self, index: usize) -> Option<T> {

if index >= self.len() {

None

} else {

self.drain(index..index + 1).next()

}

}

/// Retains only the elements specified by the predicate.

///

/// In other words, remove all elements `e` such that `f(&mut e)` returns false.

/// This method operates in place and preserves the order of the retained

/// elements.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut array = ArrayVec::from([1, 2, 3, 4]);

/// array.retain(|x| *x & 1 != 0 );

/// assert_eq!(&array[..], &[1, 3]);

/// ```

pub fn retain<F>(&mut self, mut f: F)

where F: FnMut(&mut T) -> bool

{

// Check the implementation of

// https://doc.rust-lang.org/std/vec/struct.Vec.html#method.retain

// for safety arguments (especially regarding panics in f and when

// dropping elements). Implementation closely mirrored here.

let original_len = self.len();

unsafe { self.set_len(0) };

struct BackshiftOnDrop<'a, T, const CAP: usize> {

v: &'a mut ArrayVec<T, CAP>,

processed_len: usize,

deleted_cnt: usize,

original_len: usize,

}

impl<T, const CAP: usize> Drop for BackshiftOnDrop<'_, T, CAP> {

fn drop(&mut self) {

if self.deleted_cnt > 0 {

unsafe {

ptr::copy(

self.v.as_ptr().add(self.processed_len),

self.v.as_mut_ptr().add(self.processed_len - self.deleted_cnt),

self.original_len - self.processed_len

);

}

}

unsafe {

self.v.set_len(self.original_len - self.deleted_cnt);

}

}

}

let mut g = BackshiftOnDrop { v: self, processed_len: 0, deleted_cnt: 0, original_len };

#[inline(always)]

fn process_one<F: FnMut(&mut T) -> bool, T, const CAP: usize, const DELETED: bool>(

f: &mut F,

g: &mut BackshiftOnDrop<'_, T, CAP>

) -> bool {

let cur = unsafe { g.v.as_mut_ptr().add(g.processed_len) };

if !f(unsafe { &mut *cur }) {

g.processed_len += 1;

g.deleted_cnt += 1;

unsafe { ptr::drop_in_place(cur) };

return false;

}

if DELETED {

unsafe {

let hole_slot = cur.sub(g.deleted_cnt);

ptr::copy_nonoverlapping(cur, hole_slot, 1);

}

}

g.processed_len += 1;

true

}

// Stage 1: Nothing was deleted.

while g.processed_len != original_len {

if !process_one::<F, T, CAP, false>(&mut f, &mut g) {

break;

}

}

// Stage 2: Some elements were deleted.

while g.processed_len != original_len {

process_one::<F, T, CAP, true>(&mut f, &mut g);

}

drop(g);

}

/// Returns the remaining spare capacity of the vector as a slice of

/// `MaybeUninit<T>`.

///

/// The returned slice can be used to fill the vector with data (e.g. by

/// reading from a file) before marking the data as initialized using the

/// [`set_len`] method.

///

/// [`set_len`]: ArrayVec::set_len

///

/// # Examples

///

/// ```

/// use arrayvec::ArrayVec;

///

/// // Allocate vector big enough for 10 elements.

/// let mut v: ArrayVec<i32, 10> = ArrayVec::new();

///

/// // Fill in the first 3 elements.

/// let uninit = v.spare_capacity_mut();

/// uninit[0].write(0);

/// uninit[1].write(1);

/// uninit[2].write(2);

///

/// // Mark the first 3 elements of the vector as being initialized.

/// unsafe {

/// v.set_len(3);

/// }

///

/// assert_eq!(&v[..], &[0, 1, 2]);

/// ```

pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {

let len = self.len();

&mut self.xs[len..]

}

/// Set the vector’s length without dropping or moving out elements

///

/// This method is `unsafe` because it changes the notion of the

/// number of “valid” elements in the vector. Use with care.

///

/// This method uses *debug assertions* to check that `length` is

/// not greater than the capacity.

pub unsafe fn set_len(&mut self, length: usize) {

// type invariant that capacity always fits in LenUint

debug_assert!(length <= self.capacity());

self.len = length as LenUint;

}

/// Copy all elements from the slice and append to the `ArrayVec`.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut vec: ArrayVec<usize, 10> = ArrayVec::new();

/// vec.push(1);

/// vec.try_extend_from_slice(&[2, 3]).unwrap();

/// assert_eq!(&vec[..], &[1, 2, 3]);

/// ```

///

/// # Errors

///

/// This method will return an error if the capacity left (see

/// [`remaining_capacity`]) is smaller then the length of the provided

/// slice.

///

/// [`remaining_capacity`]: #method.remaining_capacity

pub fn try_extend_from_slice(&mut self, other: &[T]) -> Result<(), CapacityError>

where T: Copy,

{

if self.remaining_capacity() < other.len() {

return Err(CapacityError::new(()));

}

let self_len = self.len();

let other_len = other.len();

unsafe {

let dst = self.get_unchecked_ptr(self_len);

ptr::copy_nonoverlapping(other.as_ptr(), dst, other_len);

self.set_len(self_len + other_len);

}

Ok(())

}

/// Create a draining iterator that removes the specified range in the vector

/// and yields the removed items from start to end. The element range is

/// removed even if the iterator is not consumed until the end.

///

/// Note: It is unspecified how many elements are removed from the vector,

/// if the `Drain` value is leaked.

///

/// **Panics** if the starting point is greater than the end point or if

/// the end point is greater than the length of the vector.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut v1 = ArrayVec::from([1, 2, 3]);

/// let v2: ArrayVec<_, 3> = v1.drain(0..2).collect();

/// assert_eq!(&v1[..], &[3]);

/// assert_eq!(&v2[..], &[1, 2]);

/// ```

pub fn drain<R>(&mut self, range: R) -> Drain<'_, T, CAP>

where R: RangeBounds<usize>

{

// Memory safety

//

// When the Drain is first created, it shortens the length of

// the source vector to make sure no uninitialized or moved-from elements

// are accessible at all if the Drain's destructor never gets to run.

//

// Drain will ptr::read out the values to remove.

// When finished, remaining tail of the vec is copied back to cover

// the hole, and the vector length is restored to the new length.

//

let len = self.len();

let start = match range.start_bound() {

Bound::Unbounded => 0,

Bound::Included(&i) => i,

Bound::Excluded(&i) => i.saturating_add(1),

};

let end = match range.end_bound() {

Bound::Excluded(&j) => j,

Bound::Included(&j) => j.saturating_add(1),

Bound::Unbounded => len,

};

self.drain_range(start, end)

}

fn drain_range(&mut self, start: usize, end: usize) -> Drain<'_, T, CAP>

{

let len = self.len();

// bounds check happens here (before length is changed!)

let range_slice: *const _ = &self[start..end];

// Calling `set_len` creates a fresh and thus unique mutable references, making all

// older aliases we created invalid. So we cannot call that function.

self.len = start as LenUint;

unsafe {

Drain {

tail_start: end,

tail_len: len - end,

iter: (*range_slice).iter(),

vec: self as *mut _,

}

}

}

/// Return the inner fixed size array, if it is full to its capacity.

///

/// Return an `Ok` value with the array if length equals capacity,

/// return an `Err` with self otherwise.

pub fn into_inner(self) -> Result<[T; CAP], Self> {

if self.len() < self.capacity() {

Err(self)

} else {

unsafe { Ok(self.into_inner_unchecked()) }

}

}

/// Return the inner fixed size array.

///

/// Safety:

/// This operation is safe if and only if length equals capacity.

pub unsafe fn into_inner_unchecked(self) -> [T; CAP] {

debug_assert_eq!(self.len(), self.capacity());

let self_ = ManuallyDrop::new(self);

let array = ptr::read(self_.as_ptr() as *const [T; CAP]);

array

}

/// Returns the ArrayVec, replacing the original with a new empty ArrayVec.

///

/// ```

/// use arrayvec::ArrayVec;

///

/// let mut v = ArrayVec::from([0, 1, 2, 3]);

/// assert_eq!([0, 1, 2, 3], v.take().into_inner().unwrap());

/// assert!(v.is_empty());

/// ```

pub fn take(&mut self) -> Self {

mem::replace(self, Self::new())

}

/// Return a slice containing all elements of the vector.

pub fn as_slice(&self) -> &[T] {

ArrayVecImpl::as_slice(self)

}

/// Return a mutable slice containing all elements of the vector.

pub fn as_mut_slice(&mut self) -> &mut [T] {

ArrayVecImpl::as_mut_slice(self)

}

/// Return a raw pointer to the vector's buffer.

pub fn as_ptr(&self) -> *const T {

ArrayVecImpl::as_ptr(self)

}

/// Return a raw mutable pointer to the vector's buffer.

pub fn as_mut_ptr(&mut self) -> *mut T {

ArrayVecImpl::as_mut_ptr(self)

}

type Item = T;

const CAPACITY: usize = CAP;

fn len(&self) -> usize { self.len() }

unsafe fn set_len(&mut self, length: usize) {

debug_assert!(length <= CAP);

self.len = length as LenUint;

}

fn as_ptr(&self) -> *const Self::Item {

self.xs.as_ptr() as _

}

fn as_mut_ptr(&mut self) -> *mut Self::Item {

self.xs.as_mut_ptr() as _

}

type Target = [T];

#[inline]

fn deref(&self) -> &Self::Target {

self.as_slice()

}

#[inline]

fn deref_mut(&mut self) -> &mut Self::Target {

self.as_mut_slice()

}

#[track_caller]

fn from(array: [T; CAP]) -> Self {

let array = ManuallyDrop::new(array);

let mut vec = <ArrayVec<T, CAP>>::new();

unsafe {

(&*array as *const [T; CAP] as *const [MaybeUninit<T>; CAP])

.copy_to_nonoverlapping(&mut vec.xs as *mut [MaybeUninit<T>; CAP], 1);

vec.set_len(CAP);

}

vec

}

where T: Clone,

type Error = CapacityError;

fn try_from(slice: &[T]) -> Result<Self, Self::Error> {

if Self::CAPACITY < slice.len() {

Err(CapacityError::new(()))

} else {

let mut array = Self::new();

array.extend_from_slice(slice);

Ok(array)

}

}

type Item = T;

type IntoIter = IntoIter<T, CAP>;

fn into_iter(self) -> IntoIter<T, CAP> {

IntoIter { index: 0, v: self, }

}

fn zeroize(&mut self) {

// Zeroize all the contained elements.

self.iter_mut().zeroize();

// Drop all the elements and set the length to 0.

self.clear();

// Zeroize the backing array.

self.xs.zeroize();

}

/// Returns the remaining items of this iterator as a slice.

pub fn as_slice(&self) -> &[T] {

&self.v[self.index..]

}

/// Returns the remaining items of this iterator as a mutable slice.

pub fn as_mut_slice(&mut self) -> &mut [T] {

&mut self.v[self.index..]

}

type Item = T;

fn next(&mut self) -> Option<Self::Item> {

if self.index == self.v.len() {

None

} else {

unsafe {

let index = self.index;

self.index = index + 1;

Some(ptr::read(self.v.get_unchecked_ptr(index)))

}

}

}

fn size_hint(&self) -> (usize, Option<usize>) {

let len = self.v.len() - self.index;

(len, Some(len))

}

fn next_back(&mut self) -> Option<Self::Item> {

if self.index == self.v.len() {

None

} else {

unsafe {

let new_len = self.v.len() - 1;

self.v.set_len(new_len);

Some(ptr::read(self.v.get_unchecked_ptr(new_len)))

}

}

}

fn drop(&mut self) {

// panic safety: Set length to 0 before dropping elements.

let index = self.index;

let len = self.v.len();

unsafe {

self.v.set_len(0);

let elements = slice::from_raw_parts_mut(

self.v.get_unchecked_ptr(index),

len - index);

ptr::drop_in_place(elements);

}

}

where T: Clone,

fn clone(&self) -> IntoIter<T, CAP> {

let mut v = ArrayVec::new();

v.extend_from_slice(&self.v[self.index..]);

v.into_iter()

}

T: fmt::Debug,

fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {

f.debug_list()

.entries(&self.v[self.index..])

.finish()

}