library/alloc/src/vec/drain.rs

   1 use crate::alloc::{Allocator, Global};
   2 use core::fmt;
   3 use core::iter::{FusedIterator, TrustedLen};
   4 use core::mem::{self, ManuallyDrop};
   5 use core::ptr::{self, NonNull};
   6 use core::slice::{self};
   7
   8 use super::Vec;
   9
  10 /// A draining iterator for `Vec<T>`.
  11 ///
  12 /// This `struct` is created by [`Vec::drain`].
  13 /// See its documentation for more.
  14 ///
  15 /// # Example
  16 ///
  17 /// ```
  18 /// let mut v = vec![0, 1, 2];
  19 /// let iter: std::vec::Drain<_> = v.drain(..);
  20 /// ```
  21 #[stable(feature = "drain", since = "1.6.0")]
  22 pub struct Drain<
  23     'a,
  24     T: 'a,
  25     #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global,
  26 > {
  27     /// Index of tail to preserve
  28     pub(super) tail_start: usize,
  29     /// Length of tail
  30     pub(super) tail_len: usize,
  31     /// Current remaining range to remove
  32     pub(super) iter: slice::Iter<'a, T>,
  33     pub(super) vec: NonNull<Vec<T, A>>,
  34 }
  35
  36 #[stable(feature = "collection_debug", since = "1.17.0")]
  37 impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> {
  38     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  39         f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
  40     }
  41 }
  42
  43 impl<'a, T, A: Allocator> Drain<'a, T, A> {
  44     /// Returns the remaining items of this iterator as a slice.
  45     ///
  46     /// # Examples
  47     ///
  48     /// ```
  49     /// let mut vec = vec!['a', 'b', 'c'];
  50     /// let mut drain = vec.drain(..);
  51     /// assert_eq!(drain.as_slice(), &['a', 'b', 'c']);
  52     /// let _ = drain.next().unwrap();
  53     /// assert_eq!(drain.as_slice(), &['b', 'c']);
  54     /// ```
  55     #[must_use]
  56     #[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
  57     pub fn as_slice(&self) -> &[T] {
  58         self.iter.as_slice()
  59     }
  60
  61     /// Returns a reference to the underlying allocator.
  62     #[unstable(feature = "allocator_api", issue = "32838")]
  63     #[must_use]
  64     #[inline]
  65     pub fn allocator(&self) -> &A {
  66         unsafe { self.vec.as_ref().allocator() }
  67     }
  68
  69     /// Keep unyielded elements in the source `Vec`.
  70     ///
  71     /// # Examples
  72     ///
  73     /// ```
  74     /// #![feature(drain_keep_rest)]
  75     ///
  76     /// let mut vec = vec!['a', 'b', 'c'];
  77     /// let mut drain = vec.drain(..);
  78     ///
  79     /// assert_eq!(drain.next().unwrap(), 'a');
  80     ///
  81     /// // This call keeps 'b' and 'c' in the vec.
  82     /// drain.keep_rest();
  83     ///
  84     /// // If we wouldn't call `keep_rest()`,
  85     /// // `vec` would be empty.
  86     /// assert_eq!(vec, ['b', 'c']);
  87     /// ```
  88     #[unstable(feature = "drain_keep_rest", issue = "101122")]
  89     pub fn keep_rest(self) {
  90         // At this moment layout looks like this:
  91         //
  92         // [head] [yielded by next] [unyielded] [yielded by next_back] [tail]
  93         //        ^-- start         \_________/-- unyielded_len        \____/-- self.tail_len
  94         //                          ^-- unyielded_ptr                  ^-- tail
  95         //
  96         // Normally `Drop` impl would drop [unyielded] and then move [tail] to the `start`.
  97         // Here we want to
  98         // 1. Move [unyielded] to `start`
  99         // 2. Move [tail] to a new start at `start + len(unyielded)`
 100         // 3. Update length of the original vec to `len(head) + len(unyielded) + len(tail)`
 101         //    a. In case of ZST, this is the only thing we want to do
 102         // 4. Do *not* drop self, as everything is put in a consistent state already, there is nothing to do
 103         let mut this = ManuallyDrop::new(self);
 104
 105         unsafe {
 106             let source_vec = this.vec.as_mut();
 107
 108             let start = source_vec.len();
 109             let tail = this.tail_start;
 110
 111             let unyielded_len = this.iter.len();
 112             let unyielded_ptr = this.iter.as_slice().as_ptr();
 113
 114             // ZSTs have no identity, so we don't need to move them around.
 115             let needs_move = mem::size_of::<T>() != 0;
 116
 117             if needs_move {
 118                 let start_ptr = source_vec.as_mut_ptr().add(start);
 119
 120                 // memmove back unyielded elements
 121                 if unyielded_ptr != start_ptr {
 122                     let src = unyielded_ptr;
 123                     let dst = start_ptr;
 124
 125                     ptr::copy(src, dst, unyielded_len);
 126                 }
 127
 128                 // memmove back untouched tail
 129                 if tail != (start + unyielded_len) {
 130                     let src = source_vec.as_ptr().add(tail);
 131                     let dst = start_ptr.add(unyielded_len);
 132                     ptr::copy(src, dst, this.tail_len);
 133                 }
 134             }
 135
 136             source_vec.set_len(start + unyielded_len + this.tail_len);
 137         }
 138     }
 139 }
 140
 141 #[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
 142 impl<'a, T, A: Allocator> AsRef<[T]> for Drain<'a, T, A> {
 143     fn as_ref(&self) -> &[T] {
 144         self.as_slice()
 145     }
 146 }
 147
 148 #[stable(feature = "drain", since = "1.6.0")]
 149 unsafe impl<T: Sync, A: Sync + Allocator> Sync for Drain<'_, T, A> {}
 150 #[stable(feature = "drain", since = "1.6.0")]
 151 unsafe impl<T: Send, A: Send + Allocator> Send for Drain<'_, T, A> {}
 152
 153 #[stable(feature = "drain", since = "1.6.0")]
 154 impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
 155     type Item = T;
 156
 157     #[inline]
 158     fn next(&mut self) -> Option<T> {
 159         self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
 160     }
 161
 162     fn size_hint(&self) -> (usize, Option<usize>) {
 163         self.iter.size_hint()
 164     }
 165 }
 166
 167 #[stable(feature = "drain", since = "1.6.0")]
 168 impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> {
 169     #[inline]
 170     fn next_back(&mut self) -> Option<T> {
 171         self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
 172     }
 173 }
 174
 175 #[stable(feature = "drain", since = "1.6.0")]
 176 impl<T, A: Allocator> Drop for Drain<'_, T, A> {
 177     fn drop(&mut self) {
 178         /// Moves back the un-`Drain`ed elements to restore the original `Vec`.
 179         struct DropGuard<'r, 'a, T, A: Allocator>(&'r mut Drain<'a, T, A>);
 180
 181         impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
 182             fn drop(&mut self) {
 183                 if self.0.tail_len > 0 {
 184                     unsafe {
 185                         let source_vec = self.0.vec.as_mut();
 186                         // memmove back untouched tail, update to new length
 187                         let start = source_vec.len();
 188                         let tail = self.0.tail_start;
 189                         if tail != start {
 190                             let src = source_vec.as_ptr().add(tail);
 191                             let dst = source_vec.as_mut_ptr().add(start);
 192                             ptr::copy(src, dst, self.0.tail_len);
 193                         }
 194                         source_vec.set_len(start + self.0.tail_len);
 195                     }
 196                 }
 197             }
 198         }
 199
 200         let iter = mem::replace(&mut self.iter, (&mut []).iter());
 201         let drop_len = iter.len();
 202
 203         let mut vec = self.vec;
 204
 205         if mem::size_of::<T>() == 0 {
 206             // ZSTs have no identity, so we don't need to move them around, we only need to drop the correct amount.
 207             // this can be achieved by manipulating the Vec length instead of moving values out from `iter`.
 208             unsafe {
 209                 let vec = vec.as_mut();
 210                 let old_len = vec.len();
 211                 vec.set_len(old_len + drop_len + self.tail_len);
 212                 vec.truncate(old_len + self.tail_len);
 213             }
 214
 215             return;
 216         }
 217
 218         // ensure elements are moved back into their appropriate places, even when drop_in_place panics
 219         let _guard = DropGuard(self);
 220
 221         if drop_len == 0 {
 222             return;
 223         }
 224
 225         // as_slice() must only be called when iter.len() is > 0 because
 226         // vec::Splice modifies vec::Drain fields and may grow the vec which would invalidate
 227         // the iterator's internal pointers. Creating a reference to deallocated memory
 228         // is invalid even when it is zero-length
 229         let drop_ptr = iter.as_slice().as_ptr();
 230
 231         unsafe {
 232             // drop_ptr comes from a slice::Iter which only gives us a &[T] but for drop_in_place
 233             // a pointer with mutable provenance is necessary. Therefore we must reconstruct
 234             // it from the original vec but also avoid creating a &mut to the front since that could
 235             // invalidate raw pointers to it which some unsafe code might rely on.
 236             let vec_ptr = vec.as_mut().as_mut_ptr();
 237             let drop_offset = drop_ptr.sub_ptr(vec_ptr);
 238             let to_drop = ptr::slice_from_raw_parts_mut(vec_ptr.add(drop_offset), drop_len);
 239             ptr::drop_in_place(to_drop);
 240         }
 241     }
 242 }
 243
 244 #[stable(feature = "drain", since = "1.6.0")]
 245 impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {
 246     fn is_empty(&self) -> bool {
 247         self.iter.is_empty()
 248     }
 249 }
 250
 251 #[unstable(feature = "trusted_len", issue = "37572")]
 252 unsafe impl<T, A: Allocator> TrustedLen for Drain<'_, T, A> {}
 253
 254 #[stable(feature = "fused", since = "1.26.0")]
 255 impl<T, A: Allocator> FusedIterator for Drain<'_, T, A> {}