rust/alloc/vec/drain.rs

   1 // SPDX-License-Identifier: Apache-2.0 OR MIT
   2
   3 use crate::alloc::{Allocator, Global};
   4 use core::fmt;
   5 use core::iter::{FusedIterator, TrustedLen};
   6 use core::mem;
   7 use core::ptr::{self, NonNull};
   8 use core::slice::{self};
   9
  10 use super::Vec;
  11
  12 /// A draining iterator for `Vec<T>`.
  13 ///
  14 /// This `struct` is created by [`Vec::drain`].
  15 /// See its documentation for more.
  16 ///
  17 /// # Example
  18 ///
  19 /// ```
  20 /// let mut v = vec![0, 1, 2];
  21 /// let iter: std::vec::Drain<_> = v.drain(..);
  22 /// ```
  23 #[stable(feature = "drain", since = "1.6.0")]
  24 pub struct Drain<
  25     'a,
  26     T: 'a,
  27     #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global,
  28 > {
  29     /// Index of tail to preserve
  30     pub(super) tail_start: usize,
  31     /// Length of tail
  32     pub(super) tail_len: usize,
  33     /// Current remaining range to remove
  34     pub(super) iter: slice::Iter<'a, T>,
  35     pub(super) vec: NonNull<Vec<T, A>>,
  36 }
  37
  38 #[stable(feature = "collection_debug", since = "1.17.0")]
  39 impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> {
  40     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  41         f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
  42     }
  43 }
  44
  45 impl<'a, T, A: Allocator> Drain<'a, T, A> {
  46     /// Returns the remaining items of this iterator as a slice.
  47     ///
  48     /// # Examples
  49     ///
  50     /// ```
  51     /// let mut vec = vec!['a', 'b', 'c'];
  52     /// let mut drain = vec.drain(..);
  53     /// assert_eq!(drain.as_slice(), &['a', 'b', 'c']);
  54     /// let _ = drain.next().unwrap();
  55     /// assert_eq!(drain.as_slice(), &['b', 'c']);
  56     /// ```
  57     #[must_use]
  58     #[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
  59     pub fn as_slice(&self) -> &[T] {
  60         self.iter.as_slice()
  61     }
  62
  63     /// Returns a reference to the underlying allocator.
  64     #[unstable(feature = "allocator_api", issue = "32838")]
  65     #[must_use]
  66     #[inline]
  67     pub fn allocator(&self) -> &A {
  68         unsafe { self.vec.as_ref().allocator() }
  69     }
  70 }
  71
  72 #[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
  73 impl<'a, T, A: Allocator> AsRef<[T]> for Drain<'a, T, A> {
  74     fn as_ref(&self) -> &[T] {
  75         self.as_slice()
  76     }
  77 }
  78
  79 #[stable(feature = "drain", since = "1.6.0")]
  80 unsafe impl<T: Sync, A: Sync + Allocator> Sync for Drain<'_, T, A> {}
  81 #[stable(feature = "drain", since = "1.6.0")]
  82 unsafe impl<T: Send, A: Send + Allocator> Send for Drain<'_, T, A> {}
  83
  84 #[stable(feature = "drain", since = "1.6.0")]
  85 impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
  86     type Item = T;
  87
  88     #[inline]
  89     fn next(&mut self) -> Option<T> {
  90         self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
  91     }
  92
  93     fn size_hint(&self) -> (usize, Option<usize>) {
  94         self.iter.size_hint()
  95     }
  96 }
  97
  98 #[stable(feature = "drain", since = "1.6.0")]
  99 impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> {
 100     #[inline]
 101     fn next_back(&mut self) -> Option<T> {
 102         self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
 103     }
 104 }
 105
 106 #[stable(feature = "drain", since = "1.6.0")]
 107 impl<T, A: Allocator> Drop for Drain<'_, T, A> {
 108     fn drop(&mut self) {
 109         /// Moves back the un-`Drain`ed elements to restore the original `Vec`.
 110         struct DropGuard<'r, 'a, T, A: Allocator>(&'r mut Drain<'a, T, A>);
 111
 112         impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
 113             fn drop(&mut self) {
 114                 if self.0.tail_len > 0 {
 115                     unsafe {
 116                         let source_vec = self.0.vec.as_mut();
 117                         // memmove back untouched tail, update to new length
 118                         let start = source_vec.len();
 119                         let tail = self.0.tail_start;
 120                         if tail != start {
 121                             let src = source_vec.as_ptr().add(tail);
 122                             let dst = source_vec.as_mut_ptr().add(start);
 123                             ptr::copy(src, dst, self.0.tail_len);
 124                         }
 125                         source_vec.set_len(start + self.0.tail_len);
 126                     }
 127                 }
 128             }
 129         }
 130
 131         let iter = mem::replace(&mut self.iter, (&mut []).iter());
 132         let drop_len = iter.len();
 133
 134         let mut vec = self.vec;
 135
 136         if mem::size_of::<T>() == 0 {
 137             // ZSTs have no identity, so we don't need to move them around, we only need to drop the correct amount.
 138             // this can be achieved by manipulating the Vec length instead of moving values out from `iter`.
 139             unsafe {
 140                 let vec = vec.as_mut();
 141                 let old_len = vec.len();
 142                 vec.set_len(old_len + drop_len + self.tail_len);
 143                 vec.truncate(old_len + self.tail_len);
 144             }
 145
 146             return;
 147         }
 148
 149         // ensure elements are moved back into their appropriate places, even when drop_in_place panics
 150         let _guard = DropGuard(self);
 151
 152         if drop_len == 0 {
 153             return;
 154         }
 155
 156         // as_slice() must only be called when iter.len() is > 0 because
 157         // vec::Splice modifies vec::Drain fields and may grow the vec which would invalidate
 158         // the iterator's internal pointers. Creating a reference to deallocated memory
 159         // is invalid even when it is zero-length
 160         let drop_ptr = iter.as_slice().as_ptr();
 161
 162         unsafe {
 163             // drop_ptr comes from a slice::Iter which only gives us a &[T] but for drop_in_place
 164             // a pointer with mutable provenance is necessary. Therefore we must reconstruct
 165             // it from the original vec but also avoid creating a &mut to the front since that could
 166             // invalidate raw pointers to it which some unsafe code might rely on.
 167             let vec_ptr = vec.as_mut().as_mut_ptr();
 168             let drop_offset = drop_ptr.sub_ptr(vec_ptr);
 169             let to_drop = ptr::slice_from_raw_parts_mut(vec_ptr.add(drop_offset), drop_len);
 170             ptr::drop_in_place(to_drop);
 171         }
 172     }
 173 }
 174
 175 #[stable(feature = "drain", since = "1.6.0")]
 176 impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {
 177     fn is_empty(&self) -> bool {
 178         self.iter.is_empty()
 179     }
 180 }
 181
 182 #[unstable(feature = "trusted_len", issue = "37572")]
 183 unsafe impl<T, A: Allocator> TrustedLen for Drain<'_, T, A> {}
 184
 185 #[stable(feature = "fused", since = "1.26.0")]
 186 impl<T, A: Allocator> FusedIterator for Drain<'_, T, A> {}