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