tinyvec/
arrayvec.rs

1use super::*;
2use core::convert::{TryFrom, TryInto};
3
4#[cfg(feature = "serde")]
5use core::marker::PhantomData;
6#[cfg(feature = "serde")]
7use serde::de::{
8  Deserialize, Deserializer, Error as DeserializeError, SeqAccess, Visitor,
9};
10#[cfg(feature = "serde")]
11use serde::ser::{Serialize, SerializeSeq, Serializer};
12
13/// Helper to make an `ArrayVec`.
14///
15/// You specify the backing array type, and optionally give all the elements you
16/// want to initially place into the array.
17///
18/// ```rust
19/// use tinyvec::*;
20///
21/// // The backing array type can be specified in the macro call
22/// let empty_av = array_vec!([u8; 16]);
23/// let some_ints = array_vec!([i32; 4] => 1, 2, 3);
24///
25/// // Or left to inference
26/// let empty_av: ArrayVec<[u8; 10]> = array_vec!();
27/// let some_ints: ArrayVec<[u8; 10]> = array_vec!(5, 6, 7, 8);
28/// ```
29#[macro_export]
30macro_rules! array_vec {
31  ($array_type:ty => $($elem:expr),* $(,)?) => {
32    {
33      let mut av: $crate::ArrayVec<$array_type> = Default::default();
34      $( av.push($elem); )*
35      av
36    }
37  };
38  ($array_type:ty) => {
39    $crate::ArrayVec::<$array_type>::default()
40  };
41  ($($elem:expr),*) => {
42    $crate::array_vec!(_ => $($elem),*)
43  };
44  ($elem:expr; $n:expr) => {
45    $crate::ArrayVec::from([$elem; $n])
46  };
47  () => {
48    $crate::array_vec!(_)
49  };
50}
51
52/// An array-backed, vector-like data structure.
53///
54/// * `ArrayVec` has a fixed capacity, equal to the minimum of the array size
55///   and `u16::MAX`. Note that not all capacities are necessarily supported by
56///   default. See comments in [`Array`].
57/// * `ArrayVec` has a variable length, as you add and remove elements. Attempts
58///   to fill the vec beyond its capacity will cause a panic.
59/// * All of the vec's array slots are always initialized in terms of Rust's
60///   memory model. When you remove a element from a location, the old value at
61///   that location is replaced with the type's default value.
62///
63/// The overall API of this type is intended to, as much as possible, emulate
64/// the API of the [`Vec`](https://doc.rust-lang.org/alloc/vec/struct.Vec.html)
65/// type.
66///
67/// ## Construction
68///
69/// You can use the `array_vec!` macro similarly to how you might use the `vec!`
70/// macro. Specify the array type, then optionally give all the initial values
71/// you want to have.
72/// ```rust
73/// # use tinyvec::*;
74/// let some_ints = array_vec!([i32; 4] => 1, 2, 3);
75/// assert_eq!(some_ints.len(), 3);
76/// ```
77///
78/// The [`default`](ArrayVec::new) for an `ArrayVec` is to have a default
79/// array with length 0. The [`new`](ArrayVec::new) method is the same as
80/// calling `default`
81/// ```rust
82/// # use tinyvec::*;
83/// let some_ints = ArrayVec::<[i32; 7]>::default();
84/// assert_eq!(some_ints.len(), 0);
85///
86/// let more_ints = ArrayVec::<[i32; 7]>::new();
87/// assert_eq!(some_ints, more_ints);
88/// ```
89///
90/// If you have an array and want the _whole thing_ so count as being "in" the
91/// new `ArrayVec` you can use one of the `from` implementations. If you want
92/// _part of_ the array then you can use
93/// [`from_array_len`](ArrayVec::from_array_len):
94/// ```rust
95/// # use tinyvec::*;
96/// let some_ints = ArrayVec::from([5, 6, 7, 8]);
97/// assert_eq!(some_ints.len(), 4);
98///
99/// let more_ints = ArrayVec::from_array_len([5, 6, 7, 8], 2);
100/// assert_eq!(more_ints.len(), 2);
101///
102/// let no_ints: ArrayVec<[u8; 5]> = ArrayVec::from_array_empty([1, 2, 3, 4, 5]);
103/// assert_eq!(no_ints.len(), 0);
104/// ```
105#[repr(C)]
106pub struct ArrayVec<A> {
107  len: u16,
108  pub(crate) data: A,
109}
110
111impl<A> Clone for ArrayVec<A>
112where
113  A: Array + Clone,
114  A::Item: Clone,
115{
116  #[inline]
117  fn clone(&self) -> Self {
118    Self { data: self.data.clone(), len: self.len }
119  }
120
121  #[inline]
122  fn clone_from(&mut self, o: &Self) {
123    let iter = self
124      .data
125      .as_slice_mut()
126      .iter_mut()
127      .zip(o.data.as_slice())
128      .take(self.len.max(o.len) as usize);
129    for (dst, src) in iter {
130      dst.clone_from(src)
131    }
132    if let Some(to_drop) =
133      self.data.as_slice_mut().get_mut((o.len as usize)..(self.len as usize))
134    {
135      to_drop.iter_mut().for_each(|x| drop(core::mem::take(x)));
136    }
137    self.len = o.len;
138  }
139}
140
141impl<A> Copy for ArrayVec<A>
142where
143  A: Array + Copy,
144  A::Item: Copy,
145{
146}
147
148impl<A: Array> Default for ArrayVec<A> {
149  #[inline]
150  fn default() -> Self {
151    Self { len: 0, data: A::default() }
152  }
153}
154
155impl<A: Array> Deref for ArrayVec<A> {
156  type Target = [A::Item];
157  #[inline(always)]
158  #[must_use]
159  fn deref(&self) -> &Self::Target {
160    &self.data.as_slice()[..self.len as usize]
161  }
162}
163
164impl<A: Array> DerefMut for ArrayVec<A> {
165  #[inline(always)]
166  #[must_use]
167  fn deref_mut(&mut self) -> &mut Self::Target {
168    &mut self.data.as_slice_mut()[..self.len as usize]
169  }
170}
171
172impl<A: Array, I: SliceIndex<[A::Item]>> Index<I> for ArrayVec<A> {
173  type Output = <I as SliceIndex<[A::Item]>>::Output;
174  #[inline(always)]
175  #[must_use]
176  fn index(&self, index: I) -> &Self::Output {
177    &self.deref()[index]
178  }
179}
180
181impl<A: Array, I: SliceIndex<[A::Item]>> IndexMut<I> for ArrayVec<A> {
182  #[inline(always)]
183  #[must_use]
184  fn index_mut(&mut self, index: I) -> &mut Self::Output {
185    &mut self.deref_mut()[index]
186  }
187}
188
189#[cfg(feature = "serde")]
190#[cfg_attr(docs_rs, doc(cfg(feature = "serde")))]
191impl<A: Array> Serialize for ArrayVec<A>
192where
193  A::Item: Serialize,
194{
195  #[must_use]
196  fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
197  where
198    S: Serializer,
199  {
200    let mut seq = serializer.serialize_seq(Some(self.len()))?;
201    for element in self.iter() {
202      seq.serialize_element(element)?;
203    }
204    seq.end()
205  }
206}
207
208#[cfg(feature = "serde")]
209#[cfg_attr(docs_rs, doc(cfg(feature = "serde")))]
210impl<'de, A: Array> Deserialize<'de> for ArrayVec<A>
211where
212  A::Item: Deserialize<'de>,
213{
214  fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
215  where
216    D: Deserializer<'de>,
217  {
218    deserializer.deserialize_seq(ArrayVecVisitor(PhantomData))
219  }
220}
221
222#[cfg(feature = "borsh")]
223#[cfg_attr(docs_rs, doc(cfg(feature = "borsh")))]
224impl<A: Array> borsh::BorshSerialize for ArrayVec<A>
225where
226  <A as Array>::Item: borsh::BorshSerialize,
227{
228  fn serialize<W: borsh::io::Write>(
229    &self, writer: &mut W,
230  ) -> borsh::io::Result<()> {
231    <usize as borsh::BorshSerialize>::serialize(&self.len(), writer)?;
232    for elem in self.iter() {
233      <<A as Array>::Item as borsh::BorshSerialize>::serialize(elem, writer)?;
234    }
235    Ok(())
236  }
237}
238
239#[cfg(feature = "borsh")]
240#[cfg_attr(docs_rs, doc(cfg(feature = "borsh")))]
241impl<A: Array> borsh::BorshDeserialize for ArrayVec<A>
242where
243  <A as Array>::Item: borsh::BorshDeserialize,
244{
245  fn deserialize_reader<R: borsh::io::Read>(
246    reader: &mut R,
247  ) -> borsh::io::Result<Self> {
248    let len = <usize as borsh::BorshDeserialize>::deserialize_reader(reader)?;
249    let mut new_arrayvec = Self::default();
250
251    for idx in 0..len {
252      let value =
253        <<A as Array>::Item as borsh::BorshDeserialize>::deserialize_reader(
254          reader,
255        )?;
256      if idx >= new_arrayvec.capacity() {
257        return Err(borsh::io::Error::new(
258          borsh::io::ErrorKind::InvalidData,
259          "invalid ArrayVec length",
260        ));
261      }
262      new_arrayvec.push(value)
263    }
264
265    Ok(new_arrayvec)
266  }
267}
268
269#[cfg(feature = "arbitrary")]
270#[cfg_attr(docs_rs, doc(cfg(feature = "arbitrary")))]
271impl<'a, A> arbitrary::Arbitrary<'a> for ArrayVec<A>
272where
273  A: Array,
274  A::Item: arbitrary::Arbitrary<'a>,
275{
276  fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
277    let max_len = A::CAPACITY.min(u16::MAX as usize) as u16;
278    let len = u.int_in_range::<u16>(0..=max_len)?;
279    let mut self_: Self = Default::default();
280    for _ in 0..len {
281      self_.push(u.arbitrary()?);
282    }
283    Ok(self_)
284  }
285
286  fn size_hint(depth: usize) -> (usize, Option<usize>) {
287    arbitrary::size_hint::recursion_guard(depth, |depth| {
288      let max_len = A::CAPACITY.min(u16::MAX as usize);
289      let inner = A::Item::size_hint(depth).1;
290      (0, inner.map(|inner| 2 + max_len * inner))
291    })
292  }
293}
294
295impl<A: Array> ArrayVec<A> {
296  /// Move all values from `other` into this vec.
297  ///
298  /// ## Panics
299  /// * If the vec overflows its capacity
300  ///
301  /// ## Example
302  /// ```rust
303  /// # use tinyvec::*;
304  /// let mut av = array_vec!([i32; 10] => 1, 2, 3);
305  /// let mut av2 = array_vec!([i32; 10] => 4, 5, 6);
306  /// av.append(&mut av2);
307  /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]);
308  /// assert_eq!(av2, &[][..]);
309  /// ```
310  #[inline]
311  pub fn append(&mut self, other: &mut Self) {
312    assert!(
313      self.try_append(other).is_none(),
314      "ArrayVec::append> total length {} exceeds capacity {}!",
315      self.len() + other.len(),
316      A::CAPACITY
317    );
318  }
319
320  /// Move all values from `other` into this vec.
321  /// If appending would overflow the capacity, Some(other) is returned.
322  /// ## Example
323  /// ```rust
324  /// # use tinyvec::*;
325  /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
326  /// let mut av2 = array_vec!([i32; 7] => 4, 5, 6);
327  /// av.append(&mut av2);
328  /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]);
329  /// assert_eq!(av2, &[][..]);
330  ///
331  /// let mut av3 = array_vec!([i32; 7] => 7, 8, 9);
332  /// assert!(av.try_append(&mut av3).is_some());
333  /// assert_eq!(av, &[1, 2, 3, 4, 5, 6][..]);
334  /// assert_eq!(av3, &[7, 8, 9][..]);
335  /// ```
336  #[inline]
337  pub fn try_append<'other>(
338    &mut self, other: &'other mut Self,
339  ) -> Option<&'other mut Self> {
340    let new_len = self.len() + other.len();
341    if new_len > A::CAPACITY {
342      return Some(other);
343    }
344
345    let iter = other.iter_mut().map(core::mem::take);
346    for item in iter {
347      self.push(item);
348    }
349
350    other.set_len(0);
351
352    return None;
353  }
354
355  /// A `*mut` pointer to the backing array.
356  ///
357  /// ## Safety
358  ///
359  /// This pointer has provenance over the _entire_ backing array.
360  #[inline(always)]
361  #[must_use]
362  pub fn as_mut_ptr(&mut self) -> *mut A::Item {
363    self.data.as_slice_mut().as_mut_ptr()
364  }
365
366  /// Performs a `deref_mut`, into unique slice form.
367  #[inline(always)]
368  #[must_use]
369  pub fn as_mut_slice(&mut self) -> &mut [A::Item] {
370    self.deref_mut()
371  }
372
373  /// A `*const` pointer to the backing array.
374  ///
375  /// ## Safety
376  ///
377  /// This pointer has provenance over the _entire_ backing array.
378  #[inline(always)]
379  #[must_use]
380  pub fn as_ptr(&self) -> *const A::Item {
381    self.data.as_slice().as_ptr()
382  }
383
384  /// Performs a `deref`, into shared slice form.
385  #[inline(always)]
386  #[must_use]
387  pub fn as_slice(&self) -> &[A::Item] {
388    self.deref()
389  }
390
391  /// The capacity of the `ArrayVec`.
392  ///
393  /// This is fixed based on the array type, but can't yet be made a `const fn`
394  /// on Stable Rust.
395  #[inline(always)]
396  #[must_use]
397  pub fn capacity(&self) -> usize {
398    // Note: This shouldn't use A::CAPACITY, because unsafe code can't rely on
399    // any Array invariants. This ensures that at the very least, the returned
400    // value is a valid length for a subslice of the backing array.
401    self.data.as_slice().len().min(u16::MAX as usize)
402  }
403
404  /// Truncates the `ArrayVec` down to length 0.
405  #[inline(always)]
406  pub fn clear(&mut self) {
407    self.truncate(0)
408  }
409
410  /// Creates a draining iterator that removes the specified range in the vector
411  /// and yields the removed items.
412  ///
413  /// ## Panics
414  /// * If the start is greater than the end
415  /// * If the end is past the edge of the vec.
416  ///
417  /// ## Example
418  /// ```rust
419  /// # use tinyvec::*;
420  /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
421  /// let av2: ArrayVec<[i32; 4]> = av.drain(1..).collect();
422  /// assert_eq!(av.as_slice(), &[1][..]);
423  /// assert_eq!(av2.as_slice(), &[2, 3][..]);
424  ///
425  /// av.drain(..);
426  /// assert_eq!(av.as_slice(), &[]);
427  /// ```
428  #[inline]
429  pub fn drain<R>(&mut self, range: R) -> ArrayVecDrain<'_, A::Item>
430  where
431    R: RangeBounds<usize>,
432  {
433    ArrayVecDrain::new(self, range)
434  }
435
436  /// Returns the inner array of the `ArrayVec`.
437  ///
438  /// This returns the full array, even if the `ArrayVec` length is currently
439  /// less than that.
440  ///
441  /// ## Example
442  ///
443  /// ```rust
444  /// # use tinyvec::{array_vec, ArrayVec};
445  /// let mut favorite_numbers = array_vec!([i32; 5] => 87, 48, 33, 9, 26);
446  /// assert_eq!(favorite_numbers.clone().into_inner(), [87, 48, 33, 9, 26]);
447  ///
448  /// favorite_numbers.pop();
449  /// assert_eq!(favorite_numbers.into_inner(), [87, 48, 33, 9, 0]);
450  /// ```
451  ///
452  /// A use for this function is to build an array from an iterator by first
453  /// collecting it into an `ArrayVec`.
454  ///
455  /// ```rust
456  /// # use tinyvec::ArrayVec;
457  /// let arr_vec: ArrayVec<[i32; 10]> = (1..=3).cycle().take(10).collect();
458  /// let inner = arr_vec.into_inner();
459  /// assert_eq!(inner, [1, 2, 3, 1, 2, 3, 1, 2, 3, 1]);
460  /// ```
461  #[inline]
462  pub fn into_inner(self) -> A {
463    self.data
464  }
465
466  /// Clone each element of the slice into this `ArrayVec`.
467  ///
468  /// ## Panics
469  /// * If the `ArrayVec` would overflow, this will panic.
470  #[inline]
471  pub fn extend_from_slice(&mut self, sli: &[A::Item])
472  where
473    A::Item: Clone,
474  {
475    if sli.is_empty() {
476      return;
477    }
478
479    let new_len = self.len as usize + sli.len();
480    assert!(
481      new_len <= A::CAPACITY,
482      "ArrayVec::extend_from_slice> total length {} exceeds capacity {}!",
483      new_len,
484      A::CAPACITY
485    );
486
487    let target = &mut self.data.as_slice_mut()[self.len as usize..new_len];
488    target.clone_from_slice(sli);
489    self.set_len(new_len);
490  }
491
492  /// Fill the vector until its capacity has been reached.
493  ///
494  /// Successively fills unused space in the spare slice of the vector with
495  /// elements from the iterator. It then returns the remaining iterator
496  /// without exhausting it. This also allows appending the head of an
497  /// infinite iterator.
498  ///
499  /// This is an alternative to `Extend::extend` method for cases where the
500  /// length of the iterator can not be checked. Since this vector can not
501  /// reallocate to increase its capacity, it is unclear what to do with
502  /// remaining elements in the iterator and the iterator itself. The
503  /// interface also provides no way to communicate this to the caller.
504  ///
505  /// ## Panics
506  /// * If the `next` method of the provided iterator panics.
507  ///
508  /// ## Example
509  ///
510  /// ```rust
511  /// # use tinyvec::*;
512  /// let mut av = array_vec!([i32; 4]);
513  /// let mut to_inf = av.fill(0..);
514  /// assert_eq!(&av[..], [0, 1, 2, 3]);
515  /// assert_eq!(to_inf.next(), Some(4));
516  /// ```
517  #[inline]
518  pub fn fill<I: IntoIterator<Item = A::Item>>(
519    &mut self, iter: I,
520  ) -> I::IntoIter {
521    // If this is written as a call to push for each element in iter, the
522    // compiler emits code that updates the length for every element. The
523    // additional complexity from that length update is worth nearly 2x in
524    // the runtime of this function.
525    let mut iter = iter.into_iter();
526    let mut pushed = 0;
527    let to_take = self.capacity() - self.len();
528    let target = &mut self.data.as_slice_mut()[self.len as usize..];
529    for element in iter.by_ref().take(to_take) {
530      target[pushed] = element;
531      pushed += 1;
532    }
533    self.len += pushed as u16;
534    iter
535  }
536
537  /// Wraps up an array and uses the given length as the initial length.
538  ///
539  /// If you want to simply use the full array, use `from` instead.
540  ///
541  /// ## Panics
542  ///
543  /// * The length specified must be less than or equal to the capacity of the
544  ///   array.
545  #[inline]
546  #[must_use]
547  #[allow(clippy::match_wild_err_arm)]
548  pub fn from_array_len(data: A, len: usize) -> Self {
549    match Self::try_from_array_len(data, len) {
550      Ok(out) => out,
551      Err(_) => panic!(
552        "ArrayVec::from_array_len> length {} exceeds capacity {}!",
553        len,
554        A::CAPACITY
555      ),
556    }
557  }
558
559  /// Inserts an item at the position given, moving all following elements +1
560  /// index.
561  ///
562  /// ## Panics
563  /// * If `index` > `len`
564  /// * If the capacity is exhausted
565  ///
566  /// ## Example
567  /// ```rust
568  /// use tinyvec::*;
569  /// let mut av = array_vec!([i32; 10] => 1, 2, 3);
570  /// av.insert(1, 4);
571  /// assert_eq!(av.as_slice(), &[1, 4, 2, 3]);
572  /// av.insert(4, 5);
573  /// assert_eq!(av.as_slice(), &[1, 4, 2, 3, 5]);
574  /// ```
575  #[inline]
576  pub fn insert(&mut self, index: usize, item: A::Item) {
577    let x = self.try_insert(index, item);
578    assert!(x.is_none(), "ArrayVec::insert> capacity overflow!");
579  }
580
581  /// Tries to insert an item at the position given, moving all following
582  /// elements +1 index.
583  /// Returns back the element if the capacity is exhausted,
584  /// otherwise returns None.
585  ///
586  /// ## Panics
587  /// * If `index` > `len`
588  ///
589  /// ## Example
590  /// ```rust
591  /// use tinyvec::*;
592  /// let mut av = array_vec!([&'static str; 4] => "one", "two", "three");
593  /// av.insert(1, "four");
594  /// assert_eq!(av.as_slice(), &["one", "four", "two", "three"]);
595  /// assert_eq!(av.try_insert(4, "five"), Some("five"));
596  /// ```
597  #[inline]
598  pub fn try_insert(
599    &mut self, index: usize, mut item: A::Item,
600  ) -> Option<A::Item> {
601    assert!(
602      index <= self.len as usize,
603      "ArrayVec::try_insert> index {} is out of bounds {}",
604      index,
605      self.len
606    );
607
608    // A previous implementation used self.try_push and slice::rotate_right
609    // rotate_right and rotate_left generate a huge amount of code and fail to
610    // inline; calling them here incurs the cost of all the cases they
611    // handle even though we're rotating a usually-small array by a constant
612    // 1 offset. This swap-based implementation benchmarks much better for
613    // small array lengths in particular.
614
615    if (self.len as usize) < A::CAPACITY {
616      self.len += 1;
617    } else {
618      return Some(item);
619    }
620
621    let target = &mut self.as_mut_slice()[index..];
622    #[allow(clippy::needless_range_loop)]
623    for i in 0..target.len() {
624      core::mem::swap(&mut item, &mut target[i]);
625    }
626    return None;
627  }
628
629  /// Checks if the length is 0.
630  #[inline(always)]
631  #[must_use]
632  pub fn is_empty(&self) -> bool {
633    self.len == 0
634  }
635
636  /// The length of the `ArrayVec` (in elements).
637  #[inline(always)]
638  #[must_use]
639  pub fn len(&self) -> usize {
640    self.len as usize
641  }
642
643  /// Makes a new, empty `ArrayVec`.
644  #[inline(always)]
645  #[must_use]
646  pub fn new() -> Self {
647    Self::default()
648  }
649
650  /// Remove and return the last element of the vec, if there is one.
651  ///
652  /// ## Failure
653  /// * If the vec is empty you get `None`.
654  ///
655  /// ## Example
656  /// ```rust
657  /// # use tinyvec::*;
658  /// let mut av = array_vec!([i32; 10] => 1, 2);
659  /// assert_eq!(av.pop(), Some(2));
660  /// assert_eq!(av.pop(), Some(1));
661  /// assert_eq!(av.pop(), None);
662  /// ```
663  #[inline]
664  pub fn pop(&mut self) -> Option<A::Item> {
665    if self.len > 0 {
666      self.len -= 1;
667      let out =
668        core::mem::take(&mut self.data.as_slice_mut()[self.len as usize]);
669      Some(out)
670    } else {
671      None
672    }
673  }
674
675  /// Place an element onto the end of the vec.
676  ///
677  /// ## Panics
678  /// * If the length of the vec would overflow the capacity.
679  ///
680  /// ## Example
681  /// ```rust
682  /// # use tinyvec::*;
683  /// let mut av = array_vec!([i32; 2]);
684  /// assert_eq!(&av[..], []);
685  /// av.push(1);
686  /// assert_eq!(&av[..], [1]);
687  /// av.push(2);
688  /// assert_eq!(&av[..], [1, 2]);
689  /// // av.push(3); this would overflow the ArrayVec and panic!
690  /// ```
691  #[inline(always)]
692  pub fn push(&mut self, val: A::Item) {
693    let x = self.try_push(val);
694    assert!(x.is_none(), "ArrayVec::push> capacity overflow!");
695  }
696
697  /// Tries to place an element onto the end of the vec.\
698  /// Returns back the element if the capacity is exhausted,
699  /// otherwise returns None.
700  /// ```rust
701  /// # use tinyvec::*;
702  /// let mut av = array_vec!([i32; 2]);
703  /// assert_eq!(av.as_slice(), []);
704  /// assert_eq!(av.try_push(1), None);
705  /// assert_eq!(&av[..], [1]);
706  /// assert_eq!(av.try_push(2), None);
707  /// assert_eq!(&av[..], [1, 2]);
708  /// assert_eq!(av.try_push(3), Some(3));
709  /// ```
710  #[inline(always)]
711  pub fn try_push(&mut self, val: A::Item) -> Option<A::Item> {
712    debug_assert!(self.len as usize <= A::CAPACITY);
713
714    let itemref = match self.data.as_slice_mut().get_mut(self.len as usize) {
715      None => return Some(val),
716      Some(x) => x,
717    };
718
719    *itemref = val;
720    self.len += 1;
721    return None;
722  }
723
724  /// Removes the item at `index`, shifting all others down by one index.
725  ///
726  /// Returns the removed element.
727  ///
728  /// ## Panics
729  ///
730  /// * If the index is out of bounds.
731  ///
732  /// ## Example
733  ///
734  /// ```rust
735  /// # use tinyvec::*;
736  /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
737  /// assert_eq!(av.remove(1), 2);
738  /// assert_eq!(&av[..], [1, 3]);
739  /// ```
740  #[inline]
741  pub fn remove(&mut self, index: usize) -> A::Item {
742    let targets: &mut [A::Item] = &mut self.deref_mut()[index..];
743    let item = core::mem::take(&mut targets[0]);
744
745    // A previous implementation used rotate_left
746    // rotate_right and rotate_left generate a huge amount of code and fail to
747    // inline; calling them here incurs the cost of all the cases they
748    // handle even though we're rotating a usually-small array by a constant
749    // 1 offset. This swap-based implementation benchmarks much better for
750    // small array lengths in particular.
751
752    for i in 0..targets.len() - 1 {
753      targets.swap(i, i + 1);
754    }
755    self.len -= 1;
756    item
757  }
758
759  /// As [`resize_with`](ArrayVec::resize_with)
760  /// and it clones the value as the closure.
761  ///
762  /// ## Example
763  ///
764  /// ```rust
765  /// # use tinyvec::*;
766  ///
767  /// let mut av = array_vec!([&str; 10] => "hello");
768  /// av.resize(3, "world");
769  /// assert_eq!(&av[..], ["hello", "world", "world"]);
770  ///
771  /// let mut av = array_vec!([i32; 10] => 1, 2, 3, 4);
772  /// av.resize(2, 0);
773  /// assert_eq!(&av[..], [1, 2]);
774  /// ```
775  #[inline]
776  pub fn resize(&mut self, new_len: usize, new_val: A::Item)
777  where
778    A::Item: Clone,
779  {
780    self.resize_with(new_len, || new_val.clone())
781  }
782
783  /// Resize the vec to the new length.
784  ///
785  /// If it needs to be longer, it's filled with repeated calls to the provided
786  /// function. If it needs to be shorter, it's truncated.
787  ///
788  /// ## Example
789  ///
790  /// ```rust
791  /// # use tinyvec::*;
792  ///
793  /// let mut av = array_vec!([i32; 10] => 1, 2, 3);
794  /// av.resize_with(5, Default::default);
795  /// assert_eq!(&av[..], [1, 2, 3, 0, 0]);
796  ///
797  /// let mut av = array_vec!([i32; 10]);
798  /// let mut p = 1;
799  /// av.resize_with(4, || {
800  ///   p *= 2;
801  ///   p
802  /// });
803  /// assert_eq!(&av[..], [2, 4, 8, 16]);
804  /// ```
805  #[inline]
806  pub fn resize_with<F: FnMut() -> A::Item>(
807    &mut self, new_len: usize, mut f: F,
808  ) {
809    match new_len.checked_sub(self.len as usize) {
810      None => self.truncate(new_len),
811      Some(new_elements) => {
812        for _ in 0..new_elements {
813          self.push(f());
814        }
815      }
816    }
817  }
818
819  /// Walk the vec and keep only the elements that pass the predicate given.
820  ///
821  /// ## Example
822  ///
823  /// ```rust
824  /// # use tinyvec::*;
825  ///
826  /// let mut av = array_vec!([i32; 10] => 1, 1, 2, 3, 3, 4);
827  /// av.retain(|&x| x % 2 == 0);
828  /// assert_eq!(&av[..], [2, 4]);
829  /// ```
830  #[inline]
831  pub fn retain<F: FnMut(&A::Item) -> bool>(&mut self, mut acceptable: F) {
832    // Drop guard to contain exactly the remaining elements when the test
833    // panics.
834    struct JoinOnDrop<'vec, Item> {
835      items: &'vec mut [Item],
836      done_end: usize,
837      // Start of tail relative to `done_end`.
838      tail_start: usize,
839    }
840
841    impl<Item> Drop for JoinOnDrop<'_, Item> {
842      fn drop(&mut self) {
843        self.items[self.done_end..].rotate_left(self.tail_start);
844      }
845    }
846
847    let mut rest = JoinOnDrop {
848      items: &mut self.data.as_slice_mut()[..self.len as usize],
849      done_end: 0,
850      tail_start: 0,
851    };
852
853    let len = self.len as usize;
854    for idx in 0..len {
855      // Loop start invariant: idx = rest.done_end + rest.tail_start
856      if !acceptable(&rest.items[idx]) {
857        let _ = core::mem::take(&mut rest.items[idx]);
858        self.len -= 1;
859        rest.tail_start += 1;
860      } else {
861        rest.items.swap(rest.done_end, idx);
862        rest.done_end += 1;
863      }
864    }
865  }
866
867  /// Retains only the elements specified by the predicate, passing a mutable
868  /// reference to it.
869  ///
870  /// In other words, remove all elements e such that f(&mut e) returns false.
871  /// This method operates in place, visiting each element exactly once in the
872  /// original order, and preserves the order of the retained elements.
873  ///
874  ///
875  /// ## Example
876  ///
877  /// ```rust
878  /// # use tinyvec::*;
879  ///
880  /// let mut av = array_vec!([i32; 10] => 1, 1, 2, 3, 3, 4);
881  /// av.retain_mut(|x| if *x % 2 == 0 { *x *= 2; true } else { false });
882  /// assert_eq!(&av[..], [4, 8]);
883  /// ```
884  #[inline]
885  pub fn retain_mut<F>(&mut self, mut acceptable: F)
886  where
887    F: FnMut(&mut A::Item) -> bool,
888  {
889    // Drop guard to contain exactly the remaining elements when the test
890    // panics.
891    struct JoinOnDrop<'vec, Item> {
892      items: &'vec mut [Item],
893      done_end: usize,
894      // Start of tail relative to `done_end`.
895      tail_start: usize,
896    }
897
898    impl<Item> Drop for JoinOnDrop<'_, Item> {
899      fn drop(&mut self) {
900        self.items[self.done_end..].rotate_left(self.tail_start);
901      }
902    }
903
904    let mut rest = JoinOnDrop {
905      items: &mut self.data.as_slice_mut()[..self.len as usize],
906      done_end: 0,
907      tail_start: 0,
908    };
909
910    let len = self.len as usize;
911    for idx in 0..len {
912      // Loop start invariant: idx = rest.done_end + rest.tail_start
913      if !acceptable(&mut rest.items[idx]) {
914        let _ = core::mem::take(&mut rest.items[idx]);
915        self.len -= 1;
916        rest.tail_start += 1;
917      } else {
918        rest.items.swap(rest.done_end, idx);
919        rest.done_end += 1;
920      }
921    }
922  }
923
924  /// Forces the length of the vector to `new_len`.
925  ///
926  /// ## Panics
927  /// * If `new_len` is greater than the vec's capacity.
928  ///
929  /// ## Safety
930  /// * This is a fully safe operation! The inactive memory already counts as
931  ///   "initialized" by Rust's rules.
932  /// * Other than "the memory is initialized" there are no other guarantees
933  ///   regarding what you find in the inactive portion of the vec.
934  #[inline(always)]
935  pub fn set_len(&mut self, new_len: usize) {
936    if new_len > A::CAPACITY {
937      // Note(Lokathor): Technically we don't have to panic here, and we could
938      // just let some other call later on trigger a panic on accident when the
939      // length is wrong. However, it's a lot easier to catch bugs when things
940      // are more "fail-fast".
941      panic!(
942        "ArrayVec::set_len> new length {} exceeds capacity {}",
943        new_len,
944        A::CAPACITY
945      )
946    }
947
948    let new_len: u16 = new_len
949      .try_into()
950      .expect("ArrayVec::set_len> new length is not in range 0..=u16::MAX");
951    self.len = new_len;
952  }
953
954  /// Splits the collection at the point given.
955  ///
956  /// * `[0, at)` stays in this vec
957  /// * `[at, len)` ends up in the new vec.
958  ///
959  /// ## Panics
960  /// * if at > len
961  ///
962  /// ## Example
963  ///
964  /// ```rust
965  /// # use tinyvec::*;
966  /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
967  /// let av2 = av.split_off(1);
968  /// assert_eq!(&av[..], [1]);
969  /// assert_eq!(&av2[..], [2, 3]);
970  /// ```
971  #[inline]
972  pub fn split_off(&mut self, at: usize) -> Self {
973    // FIXME: should this just use drain into the output?
974    if at > self.len() {
975      panic!(
976        "ArrayVec::split_off> at value {} exceeds length of {}",
977        at, self.len
978      );
979    }
980    let mut new = Self::default();
981    let moves = &mut self.as_mut_slice()[at..];
982    let split_len = moves.len();
983    let targets = &mut new.data.as_slice_mut()[..split_len];
984    moves.swap_with_slice(targets);
985
986    /* moves.len() <= u16::MAX, so these are surely in u16 range */
987    new.len = split_len as u16;
988    self.len = at as u16;
989    new
990  }
991
992  /// Creates a splicing iterator that removes the specified range in the
993  /// vector, yields the removed items, and replaces them with elements from
994  /// the provided iterator.
995  ///
996  /// `splice` fuses the provided iterator, so elements after the first `None`
997  /// are ignored.
998  ///
999  /// ## Panics
1000  /// * If the start is greater than the end.
1001  /// * If the end is past the edge of the vec.
1002  /// * If the provided iterator panics.
1003  /// * If the new length would overflow the capacity of the array. Because
1004  ///   `ArrayVecSplice` adds elements to this vec in its destructor when
1005  ///   necessary, this panic would occur when it is dropped.
1006  ///
1007  /// ## Example
1008  /// ```rust
1009  /// use tinyvec::*;
1010  /// let mut av = array_vec!([i32; 4] => 1, 2, 3);
1011  /// let av2: ArrayVec<[i32; 4]> = av.splice(1.., 4..=6).collect();
1012  /// assert_eq!(av.as_slice(), &[1, 4, 5, 6][..]);
1013  /// assert_eq!(av2.as_slice(), &[2, 3][..]);
1014  ///
1015  /// av.splice(.., None);
1016  /// assert_eq!(av.as_slice(), &[]);
1017  /// ```
1018  #[inline]
1019  pub fn splice<R, I>(
1020    &mut self, range: R, replacement: I,
1021  ) -> ArrayVecSplice<'_, A, core::iter::Fuse<I::IntoIter>>
1022  where
1023    R: RangeBounds<usize>,
1024    I: IntoIterator<Item = A::Item>,
1025  {
1026    use core::ops::Bound;
1027    let start = match range.start_bound() {
1028      Bound::Included(x) => *x,
1029      Bound::Excluded(x) => x.saturating_add(1),
1030      Bound::Unbounded => 0,
1031    };
1032    let end = match range.end_bound() {
1033      Bound::Included(x) => x.saturating_add(1),
1034      Bound::Excluded(x) => *x,
1035      Bound::Unbounded => self.len(),
1036    };
1037    assert!(
1038      start <= end,
1039      "ArrayVec::splice> Illegal range, {} to {}",
1040      start,
1041      end
1042    );
1043    assert!(
1044      end <= self.len(),
1045      "ArrayVec::splice> Range ends at {} but length is only {}!",
1046      end,
1047      self.len()
1048    );
1049
1050    ArrayVecSplice {
1051      removal_start: start,
1052      removal_end: end,
1053      parent: self,
1054      replacement: replacement.into_iter().fuse(),
1055    }
1056  }
1057
1058  /// Remove an element, swapping the end of the vec into its place.
1059  ///
1060  /// ## Panics
1061  /// * If the index is out of bounds.
1062  ///
1063  /// ## Example
1064  /// ```rust
1065  /// # use tinyvec::*;
1066  /// let mut av = array_vec!([&str; 4] => "foo", "bar", "quack", "zap");
1067  ///
1068  /// assert_eq!(av.swap_remove(1), "bar");
1069  /// assert_eq!(&av[..], ["foo", "zap", "quack"]);
1070  ///
1071  /// assert_eq!(av.swap_remove(0), "foo");
1072  /// assert_eq!(&av[..], ["quack", "zap"]);
1073  /// ```
1074  #[inline]
1075  pub fn swap_remove(&mut self, index: usize) -> A::Item {
1076    assert!(
1077      index < self.len(),
1078      "ArrayVec::swap_remove> index {} is out of bounds {}",
1079      index,
1080      self.len
1081    );
1082    if index == self.len() - 1 {
1083      self.pop().unwrap()
1084    } else {
1085      let i = self.pop().unwrap();
1086      replace(&mut self[index], i)
1087    }
1088  }
1089
1090  /// Reduces the vec's length to the given value.
1091  ///
1092  /// If the vec is already shorter than the input, nothing happens.
1093  #[inline]
1094  pub fn truncate(&mut self, new_len: usize) {
1095    if new_len >= self.len as usize {
1096      return;
1097    }
1098
1099    if needs_drop::<A::Item>() {
1100      let len = self.len as usize;
1101      self.data.as_slice_mut()[new_len..len]
1102        .iter_mut()
1103        .map(core::mem::take)
1104        .for_each(drop);
1105    }
1106
1107    /* new_len is less than self.len */
1108    self.len = new_len as u16;
1109  }
1110
1111  /// Wraps an array, using the given length as the starting length.
1112  ///
1113  /// If you want to use the whole length of the array, you can just use the
1114  /// `From` impl.
1115  ///
1116  /// ## Failure
1117  ///
1118  /// If the given length is greater than the capacity of the array this will
1119  /// error, and you'll get the array back in the `Err`.
1120  #[inline]
1121  #[cfg(not(feature = "latest_stable_rust"))]
1122  pub fn try_from_array_len(data: A, len: usize) -> Result<Self, A> {
1123    /* Note(Soveu): Should we allow A::CAPACITY > u16::MAX for now? */
1124    if len <= A::CAPACITY {
1125      Ok(Self { data, len: len as u16 })
1126    } else {
1127      Err(data)
1128    }
1129  }
1130
1131  /// Wraps an array, using the given length as the starting length.
1132  ///
1133  /// If you want to use the whole length of the array, you can just use the
1134  /// `From` impl.
1135  ///
1136  /// ## Failure
1137  ///
1138  /// If the given length is greater than the capacity of the array this will
1139  /// error, and you'll get the array back in the `Err`.
1140  #[inline]
1141  #[cfg(feature = "latest_stable_rust")]
1142  pub const fn try_from_array_len(data: A, len: usize) -> Result<Self, A> {
1143    /* Note(Soveu): Should we allow A::CAPACITY > u16::MAX for now? */
1144    if len <= A::CAPACITY {
1145      Ok(Self { data, len: len as u16 })
1146    } else {
1147      Err(data)
1148    }
1149  }
1150}
1151
1152impl<A> ArrayVec<A> {
1153  /// Wraps up an array as a new empty `ArrayVec`.
1154  ///
1155  /// If you want to simply use the full array, use `from` instead.
1156  ///
1157  /// ## Examples
1158  ///
1159  /// This method in particular allows to create values for statics:
1160  ///
1161  /// ```rust
1162  /// # use tinyvec::ArrayVec;
1163  /// static DATA: ArrayVec<[u8; 5]> = ArrayVec::from_array_empty([0; 5]);
1164  /// assert_eq!(DATA.len(), 0);
1165  /// ```
1166  ///
1167  /// But of course it is just an normal empty `ArrayVec`:
1168  ///
1169  /// ```rust
1170  /// # use tinyvec::ArrayVec;
1171  /// let mut data = ArrayVec::from_array_empty([1, 2, 3, 4]);
1172  /// assert_eq!(&data[..], &[]);
1173  /// data.push(42);
1174  /// assert_eq!(&data[..], &[42]);
1175  /// ```
1176  #[inline]
1177  #[must_use]
1178  pub const fn from_array_empty(data: A) -> Self {
1179    Self { data, len: 0 }
1180  }
1181}
1182
1183#[cfg(feature = "grab_spare_slice")]
1184impl<A: Array> ArrayVec<A> {
1185  /// Obtain the shared slice of the array _after_ the active memory.
1186  ///
1187  /// ## Example
1188  /// ```rust
1189  /// # use tinyvec::*;
1190  /// let mut av = array_vec!([i32; 4]);
1191  /// assert_eq!(av.grab_spare_slice().len(), 4);
1192  /// av.push(10);
1193  /// av.push(11);
1194  /// av.push(12);
1195  /// av.push(13);
1196  /// assert_eq!(av.grab_spare_slice().len(), 0);
1197  /// ```
1198  #[inline(always)]
1199  pub fn grab_spare_slice(&self) -> &[A::Item] {
1200    &self.data.as_slice()[self.len as usize..]
1201  }
1202
1203  /// Obtain the mutable slice of the array _after_ the active memory.
1204  ///
1205  /// ## Example
1206  /// ```rust
1207  /// # use tinyvec::*;
1208  /// let mut av = array_vec!([i32; 4]);
1209  /// assert_eq!(av.grab_spare_slice_mut().len(), 4);
1210  /// av.push(10);
1211  /// av.push(11);
1212  /// assert_eq!(av.grab_spare_slice_mut().len(), 2);
1213  /// ```
1214  #[inline(always)]
1215  pub fn grab_spare_slice_mut(&mut self) -> &mut [A::Item] {
1216    &mut self.data.as_slice_mut()[self.len as usize..]
1217  }
1218}
1219
1220#[cfg(feature = "nightly_slice_partition_dedup")]
1221impl<A: Array> ArrayVec<A> {
1222  /// De-duplicates the vec contents.
1223  #[inline(always)]
1224  pub fn dedup(&mut self)
1225  where
1226    A::Item: PartialEq,
1227  {
1228    self.dedup_by(|a, b| a == b)
1229  }
1230
1231  /// De-duplicates the vec according to the predicate given.
1232  #[inline(always)]
1233  pub fn dedup_by<F>(&mut self, same_bucket: F)
1234  where
1235    F: FnMut(&mut A::Item, &mut A::Item) -> bool,
1236  {
1237    let len = {
1238      let (dedup, _) = self.as_mut_slice().partition_dedup_by(same_bucket);
1239      dedup.len()
1240    };
1241    self.truncate(len);
1242  }
1243
1244  /// De-duplicates the vec according to the key selector given.
1245  #[inline(always)]
1246  pub fn dedup_by_key<F, K>(&mut self, mut key: F)
1247  where
1248    F: FnMut(&mut A::Item) -> K,
1249    K: PartialEq,
1250  {
1251    self.dedup_by(|a, b| key(a) == key(b))
1252  }
1253}
1254
1255impl<A> ArrayVec<A> {
1256  /// Returns the reference to the inner array of the `ArrayVec`.
1257  ///
1258  /// This returns the full array, even if the `ArrayVec` length is currently
1259  /// less than that.
1260  #[inline(always)]
1261  #[must_use]
1262  pub const fn as_inner(&self) -> &A {
1263    &self.data
1264  }
1265}
1266
1267/// Splicing iterator for `ArrayVec`
1268/// See [`ArrayVec::splice`](ArrayVec::<A>::splice)
1269pub struct ArrayVecSplice<'p, A: Array, I: Iterator<Item = A::Item>> {
1270  parent: &'p mut ArrayVec<A>,
1271  removal_start: usize,
1272  removal_end: usize,
1273  replacement: I,
1274}
1275
1276impl<'p, A: Array, I: Iterator<Item = A::Item>> Iterator
1277  for ArrayVecSplice<'p, A, I>
1278{
1279  type Item = A::Item;
1280
1281  #[inline]
1282  fn next(&mut self) -> Option<A::Item> {
1283    if self.removal_start < self.removal_end {
1284      match self.replacement.next() {
1285        Some(replacement) => {
1286          let removed = core::mem::replace(
1287            &mut self.parent[self.removal_start],
1288            replacement,
1289          );
1290          self.removal_start += 1;
1291          Some(removed)
1292        }
1293        None => {
1294          let removed = self.parent.remove(self.removal_start);
1295          self.removal_end -= 1;
1296          Some(removed)
1297        }
1298      }
1299    } else {
1300      None
1301    }
1302  }
1303
1304  #[inline]
1305  fn size_hint(&self) -> (usize, Option<usize>) {
1306    let len = self.len();
1307    (len, Some(len))
1308  }
1309}
1310
1311impl<'p, A, I> ExactSizeIterator for ArrayVecSplice<'p, A, I>
1312where
1313  A: Array,
1314  I: Iterator<Item = A::Item>,
1315{
1316  #[inline]
1317  fn len(&self) -> usize {
1318    self.removal_end - self.removal_start
1319  }
1320}
1321
1322impl<'p, A, I> FusedIterator for ArrayVecSplice<'p, A, I>
1323where
1324  A: Array,
1325  I: Iterator<Item = A::Item>,
1326{
1327}
1328
1329impl<'p, A, I> DoubleEndedIterator for ArrayVecSplice<'p, A, I>
1330where
1331  A: Array,
1332  I: Iterator<Item = A::Item> + DoubleEndedIterator,
1333{
1334  #[inline]
1335  fn next_back(&mut self) -> Option<A::Item> {
1336    if self.removal_start < self.removal_end {
1337      match self.replacement.next_back() {
1338        Some(replacement) => {
1339          let removed = core::mem::replace(
1340            &mut self.parent[self.removal_end - 1],
1341            replacement,
1342          );
1343          self.removal_end -= 1;
1344          Some(removed)
1345        }
1346        None => {
1347          let removed = self.parent.remove(self.removal_end - 1);
1348          self.removal_end -= 1;
1349          Some(removed)
1350        }
1351      }
1352    } else {
1353      None
1354    }
1355  }
1356}
1357
1358impl<'p, A: Array, I: Iterator<Item = A::Item>> Drop
1359  for ArrayVecSplice<'p, A, I>
1360{
1361  #[inline]
1362  fn drop(&mut self) {
1363    for _ in self.by_ref() {}
1364
1365    // FIXME: reserve lower bound of size_hint
1366
1367    for replacement in self.replacement.by_ref() {
1368      self.parent.insert(self.removal_end, replacement);
1369      self.removal_end += 1;
1370    }
1371  }
1372}
1373
1374impl<A: Array> AsMut<[A::Item]> for ArrayVec<A> {
1375  #[inline(always)]
1376  #[must_use]
1377  fn as_mut(&mut self) -> &mut [A::Item] {
1378    &mut *self
1379  }
1380}
1381
1382impl<A: Array> AsRef<[A::Item]> for ArrayVec<A> {
1383  #[inline(always)]
1384  #[must_use]
1385  fn as_ref(&self) -> &[A::Item] {
1386    &*self
1387  }
1388}
1389
1390impl<A: Array> Borrow<[A::Item]> for ArrayVec<A> {
1391  #[inline(always)]
1392  #[must_use]
1393  fn borrow(&self) -> &[A::Item] {
1394    &*self
1395  }
1396}
1397
1398impl<A: Array> BorrowMut<[A::Item]> for ArrayVec<A> {
1399  #[inline(always)]
1400  #[must_use]
1401  fn borrow_mut(&mut self) -> &mut [A::Item] {
1402    &mut *self
1403  }
1404}
1405
1406impl<A: Array> Extend<A::Item> for ArrayVec<A> {
1407  #[inline]
1408  fn extend<T: IntoIterator<Item = A::Item>>(&mut self, iter: T) {
1409    for t in iter {
1410      self.push(t)
1411    }
1412  }
1413}
1414
1415impl<A: Array> From<A> for ArrayVec<A> {
1416  #[inline(always)]
1417  #[must_use]
1418  /// The output has a length equal to the full array.
1419  ///
1420  /// If you want to select a length, use
1421  /// [`from_array_len`](ArrayVec::from_array_len)
1422  fn from(data: A) -> Self {
1423    let len: u16 = data
1424      .as_slice()
1425      .len()
1426      .try_into()
1427      .expect("ArrayVec::from> length must be in range 0..=u16::MAX");
1428    Self { len, data }
1429  }
1430}
1431
1432/// The error type returned when a conversion from a slice to an [`ArrayVec`]
1433/// fails.
1434#[derive(Debug, Copy, Clone)]
1435pub struct TryFromSliceError(());
1436
1437impl core::fmt::Display for TryFromSliceError {
1438  #[inline]
1439  fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
1440    f.write_str("could not convert slice to ArrayVec")
1441  }
1442}
1443
1444#[cfg(feature = "std")]
1445impl std::error::Error for TryFromSliceError {}
1446
1447impl<T, A> TryFrom<&'_ [T]> for ArrayVec<A>
1448where
1449  T: Clone + Default,
1450  A: Array<Item = T>,
1451{
1452  type Error = TryFromSliceError;
1453
1454  #[inline]
1455  /// The output has a length equal to that of the slice, with the same capacity
1456  /// as `A`.
1457  fn try_from(slice: &[T]) -> Result<Self, Self::Error> {
1458    if slice.len() > A::CAPACITY {
1459      Err(TryFromSliceError(()))
1460    } else {
1461      let mut arr = ArrayVec::new();
1462      // We do not use ArrayVec::extend_from_slice, because it looks like LLVM
1463      // fails to deduplicate all the length-checking logic between the
1464      // above if and the contents of that method, thus producing much
1465      // slower code. Unlike many of the other optimizations in this
1466      // crate, this one is worth keeping an eye on. I see no reason, for
1467      // any element type, that these should produce different code. But
1468      // they do. (rustc 1.51.0)
1469      arr.set_len(slice.len());
1470      arr.as_mut_slice().clone_from_slice(slice);
1471      Ok(arr)
1472    }
1473  }
1474}
1475
1476impl<A: Array> FromIterator<A::Item> for ArrayVec<A> {
1477  #[inline]
1478  #[must_use]
1479  fn from_iter<T: IntoIterator<Item = A::Item>>(iter: T) -> Self {
1480    let mut av = Self::default();
1481    for i in iter {
1482      av.push(i)
1483    }
1484    av
1485  }
1486}
1487
1488/// Iterator for consuming an `ArrayVec` and returning owned elements.
1489pub struct ArrayVecIterator<A: Array> {
1490  base: u16,
1491  tail: u16,
1492  data: A,
1493}
1494
1495impl<A: Array> ArrayVecIterator<A> {
1496  /// Returns the remaining items of this iterator as a slice.
1497  #[inline]
1498  #[must_use]
1499  pub fn as_slice(&self) -> &[A::Item] {
1500    &self.data.as_slice()[self.base as usize..self.tail as usize]
1501  }
1502}
1503impl<A: Array> FusedIterator for ArrayVecIterator<A> {}
1504impl<A: Array> Iterator for ArrayVecIterator<A> {
1505  type Item = A::Item;
1506  #[inline]
1507  fn next(&mut self) -> Option<Self::Item> {
1508    let slice =
1509      &mut self.data.as_slice_mut()[self.base as usize..self.tail as usize];
1510    let itemref = slice.first_mut()?;
1511    self.base += 1;
1512    return Some(core::mem::take(itemref));
1513  }
1514  #[inline(always)]
1515  #[must_use]
1516  fn size_hint(&self) -> (usize, Option<usize>) {
1517    let s = self.tail - self.base;
1518    let s = s as usize;
1519    (s, Some(s))
1520  }
1521  #[inline(always)]
1522  fn count(self) -> usize {
1523    self.size_hint().0
1524  }
1525  #[inline]
1526  fn last(mut self) -> Option<Self::Item> {
1527    self.next_back()
1528  }
1529  #[inline]
1530  fn nth(&mut self, n: usize) -> Option<A::Item> {
1531    let slice = &mut self.data.as_slice_mut();
1532    let slice = &mut slice[self.base as usize..self.tail as usize];
1533
1534    if let Some(x) = slice.get_mut(n) {
1535      /* n is in range [0 .. self.tail - self.base) so in u16 range */
1536      self.base += n as u16 + 1;
1537      return Some(core::mem::take(x));
1538    }
1539
1540    self.base = self.tail;
1541    return None;
1542  }
1543}
1544
1545impl<A: Array> DoubleEndedIterator for ArrayVecIterator<A> {
1546  #[inline]
1547  fn next_back(&mut self) -> Option<Self::Item> {
1548    let slice =
1549      &mut self.data.as_slice_mut()[self.base as usize..self.tail as usize];
1550    let item = slice.last_mut()?;
1551    self.tail -= 1;
1552    return Some(core::mem::take(item));
1553  }
1554
1555  #[inline]
1556  fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1557    let base = self.base as usize;
1558    let tail = self.tail as usize;
1559    let slice = &mut self.data.as_slice_mut()[base..tail];
1560    let n = n.saturating_add(1);
1561
1562    if let Some(n) = slice.len().checked_sub(n) {
1563      let item = &mut slice[n];
1564      /* n is in [0..self.tail - self.base] range, so in u16 range */
1565      self.tail = self.base + n as u16;
1566      return Some(core::mem::take(item));
1567    }
1568
1569    self.tail = self.base;
1570    return None;
1571  }
1572}
1573
1574impl<A: Array> ExactSizeIterator for ArrayVecIterator<A> {
1575  #[inline]
1576  fn len(&self) -> usize {
1577    self.size_hint().0
1578  }
1579}
1580
1581impl<A: Array> Debug for ArrayVecIterator<A>
1582where
1583  A::Item: Debug,
1584{
1585  #[allow(clippy::missing_inline_in_public_items)]
1586  fn fmt(&self, f: &mut Formatter<'_>) -> core::fmt::Result {
1587    f.debug_tuple("ArrayVecIterator").field(&self.as_slice()).finish()
1588  }
1589}
1590
1591impl<A: Array> IntoIterator for ArrayVec<A> {
1592  type Item = A::Item;
1593  type IntoIter = ArrayVecIterator<A>;
1594  #[inline(always)]
1595  #[must_use]
1596  fn into_iter(self) -> Self::IntoIter {
1597    ArrayVecIterator { base: 0, tail: self.len, data: self.data }
1598  }
1599}
1600
1601impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
1602  type Item = &'a mut A::Item;
1603  type IntoIter = core::slice::IterMut<'a, A::Item>;
1604  #[inline(always)]
1605  #[must_use]
1606  fn into_iter(self) -> Self::IntoIter {
1607    self.iter_mut()
1608  }
1609}
1610
1611impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
1612  type Item = &'a A::Item;
1613  type IntoIter = core::slice::Iter<'a, A::Item>;
1614  #[inline(always)]
1615  #[must_use]
1616  fn into_iter(self) -> Self::IntoIter {
1617    self.iter()
1618  }
1619}
1620
1621impl<A: Array> PartialEq for ArrayVec<A>
1622where
1623  A::Item: PartialEq,
1624{
1625  #[inline]
1626  #[must_use]
1627  fn eq(&self, other: &Self) -> bool {
1628    self.as_slice().eq(other.as_slice())
1629  }
1630}
1631impl<A: Array> Eq for ArrayVec<A> where A::Item: Eq {}
1632
1633impl<A: Array> PartialOrd for ArrayVec<A>
1634where
1635  A::Item: PartialOrd,
1636{
1637  #[inline]
1638  #[must_use]
1639  fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
1640    self.as_slice().partial_cmp(other.as_slice())
1641  }
1642}
1643impl<A: Array> Ord for ArrayVec<A>
1644where
1645  A::Item: Ord,
1646{
1647  #[inline]
1648  #[must_use]
1649  fn cmp(&self, other: &Self) -> core::cmp::Ordering {
1650    self.as_slice().cmp(other.as_slice())
1651  }
1652}
1653
1654impl<A: Array> PartialEq<&A> for ArrayVec<A>
1655where
1656  A::Item: PartialEq,
1657{
1658  #[inline]
1659  #[must_use]
1660  fn eq(&self, other: &&A) -> bool {
1661    self.as_slice().eq(other.as_slice())
1662  }
1663}
1664
1665impl<A: Array> PartialEq<&[A::Item]> for ArrayVec<A>
1666where
1667  A::Item: PartialEq,
1668{
1669  #[inline]
1670  #[must_use]
1671  fn eq(&self, other: &&[A::Item]) -> bool {
1672    self.as_slice().eq(*other)
1673  }
1674}
1675
1676impl<A: Array> Hash for ArrayVec<A>
1677where
1678  A::Item: Hash,
1679{
1680  #[inline]
1681  fn hash<H: Hasher>(&self, state: &mut H) {
1682    self.as_slice().hash(state)
1683  }
1684}
1685
1686#[cfg(feature = "experimental_write_impl")]
1687impl<A: Array<Item = u8>> core::fmt::Write for ArrayVec<A> {
1688  fn write_str(&mut self, s: &str) -> core::fmt::Result {
1689    let my_len = self.len();
1690    let str_len = s.as_bytes().len();
1691    if my_len + str_len <= A::CAPACITY {
1692      let remainder = &mut self.data.as_slice_mut()[my_len..];
1693      let target = &mut remainder[..str_len];
1694      target.copy_from_slice(s.as_bytes());
1695      Ok(())
1696    } else {
1697      Err(core::fmt::Error)
1698    }
1699  }
1700}
1701
1702// // // // // // // //
1703// Formatting impls
1704// // // // // // // //
1705
1706impl<A: Array> Binary for ArrayVec<A>
1707where
1708  A::Item: Binary,
1709{
1710  #[allow(clippy::missing_inline_in_public_items)]
1711  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1712    write!(f, "[")?;
1713    if f.alternate() {
1714      write!(f, "\n    ")?;
1715    }
1716    for (i, elem) in self.iter().enumerate() {
1717      if i > 0 {
1718        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1719      }
1720      Binary::fmt(elem, f)?;
1721    }
1722    if f.alternate() {
1723      write!(f, ",\n")?;
1724    }
1725    write!(f, "]")
1726  }
1727}
1728
1729impl<A: Array> Debug for ArrayVec<A>
1730where
1731  A::Item: Debug,
1732{
1733  #[allow(clippy::missing_inline_in_public_items)]
1734  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1735    write!(f, "[")?;
1736    if f.alternate() && !self.is_empty() {
1737      write!(f, "\n    ")?;
1738    }
1739    for (i, elem) in self.iter().enumerate() {
1740      if i > 0 {
1741        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1742      }
1743      Debug::fmt(elem, f)?;
1744    }
1745    if f.alternate() && !self.is_empty() {
1746      write!(f, ",\n")?;
1747    }
1748    write!(f, "]")
1749  }
1750}
1751
1752impl<A: Array> Display for ArrayVec<A>
1753where
1754  A::Item: Display,
1755{
1756  #[allow(clippy::missing_inline_in_public_items)]
1757  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1758    write!(f, "[")?;
1759    if f.alternate() {
1760      write!(f, "\n    ")?;
1761    }
1762    for (i, elem) in self.iter().enumerate() {
1763      if i > 0 {
1764        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1765      }
1766      Display::fmt(elem, f)?;
1767    }
1768    if f.alternate() {
1769      write!(f, ",\n")?;
1770    }
1771    write!(f, "]")
1772  }
1773}
1774
1775impl<A: Array> LowerExp for ArrayVec<A>
1776where
1777  A::Item: LowerExp,
1778{
1779  #[allow(clippy::missing_inline_in_public_items)]
1780  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1781    write!(f, "[")?;
1782    if f.alternate() {
1783      write!(f, "\n    ")?;
1784    }
1785    for (i, elem) in self.iter().enumerate() {
1786      if i > 0 {
1787        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1788      }
1789      LowerExp::fmt(elem, f)?;
1790    }
1791    if f.alternate() {
1792      write!(f, ",\n")?;
1793    }
1794    write!(f, "]")
1795  }
1796}
1797
1798impl<A: Array> LowerHex for ArrayVec<A>
1799where
1800  A::Item: LowerHex,
1801{
1802  #[allow(clippy::missing_inline_in_public_items)]
1803  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1804    write!(f, "[")?;
1805    if f.alternate() {
1806      write!(f, "\n    ")?;
1807    }
1808    for (i, elem) in self.iter().enumerate() {
1809      if i > 0 {
1810        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1811      }
1812      LowerHex::fmt(elem, f)?;
1813    }
1814    if f.alternate() {
1815      write!(f, ",\n")?;
1816    }
1817    write!(f, "]")
1818  }
1819}
1820
1821impl<A: Array> Octal for ArrayVec<A>
1822where
1823  A::Item: Octal,
1824{
1825  #[allow(clippy::missing_inline_in_public_items)]
1826  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1827    write!(f, "[")?;
1828    if f.alternate() {
1829      write!(f, "\n    ")?;
1830    }
1831    for (i, elem) in self.iter().enumerate() {
1832      if i > 0 {
1833        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1834      }
1835      Octal::fmt(elem, f)?;
1836    }
1837    if f.alternate() {
1838      write!(f, ",\n")?;
1839    }
1840    write!(f, "]")
1841  }
1842}
1843
1844impl<A: Array> Pointer for ArrayVec<A>
1845where
1846  A::Item: Pointer,
1847{
1848  #[allow(clippy::missing_inline_in_public_items)]
1849  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1850    write!(f, "[")?;
1851    if f.alternate() {
1852      write!(f, "\n    ")?;
1853    }
1854    for (i, elem) in self.iter().enumerate() {
1855      if i > 0 {
1856        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1857      }
1858      Pointer::fmt(elem, f)?;
1859    }
1860    if f.alternate() {
1861      write!(f, ",\n")?;
1862    }
1863    write!(f, "]")
1864  }
1865}
1866
1867impl<A: Array> UpperExp for ArrayVec<A>
1868where
1869  A::Item: UpperExp,
1870{
1871  #[allow(clippy::missing_inline_in_public_items)]
1872  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1873    write!(f, "[")?;
1874    if f.alternate() {
1875      write!(f, "\n    ")?;
1876    }
1877    for (i, elem) in self.iter().enumerate() {
1878      if i > 0 {
1879        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1880      }
1881      UpperExp::fmt(elem, f)?;
1882    }
1883    if f.alternate() {
1884      write!(f, ",\n")?;
1885    }
1886    write!(f, "]")
1887  }
1888}
1889
1890impl<A: Array> UpperHex for ArrayVec<A>
1891where
1892  A::Item: UpperHex,
1893{
1894  #[allow(clippy::missing_inline_in_public_items)]
1895  fn fmt(&self, f: &mut Formatter) -> core::fmt::Result {
1896    write!(f, "[")?;
1897    if f.alternate() {
1898      write!(f, "\n    ")?;
1899    }
1900    for (i, elem) in self.iter().enumerate() {
1901      if i > 0 {
1902        write!(f, ",{}", if f.alternate() { "\n    " } else { " " })?;
1903      }
1904      UpperHex::fmt(elem, f)?;
1905    }
1906    if f.alternate() {
1907      write!(f, ",\n")?;
1908    }
1909    write!(f, "]")
1910  }
1911}
1912
1913#[cfg(feature = "alloc")]
1914use alloc::vec::Vec;
1915
1916#[cfg(all(feature = "alloc", feature = "rustc_1_57"))]
1917use alloc::collections::TryReserveError;
1918
1919#[cfg(feature = "alloc")]
1920impl<A: Array> ArrayVec<A> {
1921  /// Drains all elements to a Vec, but reserves additional space
1922  /// ```
1923  /// # use tinyvec::*;
1924  /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1925  /// let v = av.drain_to_vec_and_reserve(10);
1926  /// assert_eq!(v, &[1, 2, 3]);
1927  /// assert_eq!(v.capacity(), 13);
1928  /// ```
1929  #[inline]
1930  pub fn drain_to_vec_and_reserve(&mut self, n: usize) -> Vec<A::Item> {
1931    let cap = n + self.len();
1932    let mut v = Vec::with_capacity(cap);
1933    let iter = self.iter_mut().map(core::mem::take);
1934    v.extend(iter);
1935    self.set_len(0);
1936    return v;
1937  }
1938
1939  /// Tries to drain all elements to a Vec, but reserves additional space.
1940  ///
1941  /// # Errors
1942  ///
1943  /// If the allocator reports a failure, then an error is returned.
1944  ///
1945  /// ```
1946  /// # use tinyvec::*;
1947  /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1948  /// let v = av.try_drain_to_vec_and_reserve(10);
1949  /// assert!(matches!(v, Ok(_)));
1950  /// let v = v.unwrap();
1951  /// assert_eq!(v, &[1, 2, 3]);
1952  /// assert_eq!(v.capacity(), 13);
1953  /// ```
1954  #[inline]
1955  #[cfg(feature = "rustc_1_57")]
1956  pub fn try_drain_to_vec_and_reserve(
1957    &mut self, n: usize,
1958  ) -> Result<Vec<A::Item>, TryReserveError> {
1959    let cap = n + self.len();
1960    let mut v = Vec::new();
1961    v.try_reserve(cap)?;
1962    let iter = self.iter_mut().map(core::mem::take);
1963    v.extend(iter);
1964    self.set_len(0);
1965    return Ok(v);
1966  }
1967
1968  /// Drains all elements to a Vec
1969  /// ```
1970  /// # use tinyvec::*;
1971  /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1972  /// let v = av.drain_to_vec();
1973  /// assert_eq!(v, &[1, 2, 3]);
1974  /// assert_eq!(v.capacity(), 3);
1975  /// ```
1976  #[inline]
1977  pub fn drain_to_vec(&mut self) -> Vec<A::Item> {
1978    self.drain_to_vec_and_reserve(0)
1979  }
1980
1981  /// Tries to drain all elements to a Vec.
1982  ///
1983  /// # Errors
1984  ///
1985  /// If the allocator reports a failure, then an error is returned.
1986  ///
1987  /// ```
1988  /// # use tinyvec::*;
1989  /// let mut av = array_vec!([i32; 7] => 1, 2, 3);
1990  /// let v = av.try_drain_to_vec();
1991  /// assert!(matches!(v, Ok(_)));
1992  /// let v = v.unwrap();
1993  /// assert_eq!(v, &[1, 2, 3]);
1994  /// // Vec may reserve more than necessary in order to prevent more future allocations.
1995  /// assert!(v.capacity() >= 3);
1996  /// ```
1997  #[inline]
1998  #[cfg(feature = "rustc_1_57")]
1999  pub fn try_drain_to_vec(&mut self) -> Result<Vec<A::Item>, TryReserveError> {
2000    self.try_drain_to_vec_and_reserve(0)
2001  }
2002}
2003
2004#[cfg(feature = "serde")]
2005struct ArrayVecVisitor<A: Array>(PhantomData<A>);
2006
2007#[cfg(feature = "serde")]
2008impl<'de, A: Array> Visitor<'de> for ArrayVecVisitor<A>
2009where
2010  A::Item: Deserialize<'de>,
2011{
2012  type Value = ArrayVec<A>;
2013
2014  fn expecting(
2015    &self, formatter: &mut core::fmt::Formatter,
2016  ) -> core::fmt::Result {
2017    formatter.write_str("a sequence")
2018  }
2019
2020  fn visit_seq<S>(self, mut seq: S) -> Result<Self::Value, S::Error>
2021  where
2022    S: SeqAccess<'de>,
2023  {
2024    let mut new_arrayvec: ArrayVec<A> = Default::default();
2025
2026    let mut idx = 0usize;
2027    while let Some(value) = seq.next_element()? {
2028      if new_arrayvec.len() >= new_arrayvec.capacity() {
2029        return Err(DeserializeError::invalid_length(idx, &self));
2030      }
2031      new_arrayvec.push(value);
2032      idx = idx + 1;
2033    }
2034
2035    Ok(new_arrayvec)
2036  }
2037}
2038
2039#[cfg(test)]
2040mod test {
2041  use super::*;
2042
2043  #[test]
2044  fn retain_mut_empty_vec() {
2045    let mut av: ArrayVec<[i32; 4]> = ArrayVec::new();
2046    av.retain_mut(|&mut x| x % 2 == 0);
2047    assert_eq!(av.len(), 0);
2048  }
2049
2050  #[test]
2051  fn retain_mut_all_elements() {
2052    let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 2, 4, 6, 8);
2053    av.retain_mut(|&mut x| x % 2 == 0);
2054    assert_eq!(av.len(), 4);
2055    assert_eq!(av.as_slice(), &[2, 4, 6, 8]);
2056  }
2057
2058  #[test]
2059  fn retain_mut_some_elements() {
2060    let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 1, 2, 3, 4);
2061    av.retain_mut(|&mut x| x % 2 == 0);
2062    assert_eq!(av.len(), 2);
2063    assert_eq!(av.as_slice(), &[2, 4]);
2064  }
2065
2066  #[test]
2067  fn retain_mut_no_elements() {
2068    let mut av: ArrayVec<[i32; 4]> = array_vec!([i32; 4] => 1, 3, 5, 7);
2069    av.retain_mut(|&mut x| x % 2 == 0);
2070    assert_eq!(av.len(), 0);
2071  }
2072
2073  #[test]
2074  fn retain_mut_zero_capacity() {
2075    let mut av: ArrayVec<[i32; 0]> = ArrayVec::new();
2076    av.retain_mut(|&mut x| x % 2 == 0);
2077    assert_eq!(av.len(), 0);
2078  }
2079}
tinyvec/arrayvec.rs

tinyvec/
arrayvec.rs
