library/alloc/src/vec/into_iter.rs

   1 #[cfg(not(no_global_oom_handling))]
   2 use super::AsVecIntoIter;
   3 use crate::alloc::{Allocator, Global};
   4 #[cfg(not(no_global_oom_handling))]
   5 use crate::collections::VecDeque;
   6 use crate::raw_vec::RawVec;
   7 use core::array;
   8 use core::fmt;
   9 use core::iter::{
  10     FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccessNoCoerce,
  11 };
  12 use core::marker::PhantomData;
  13 use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties};
  14 #[cfg(not(no_global_oom_handling))]
  15 use core::ops::Deref;
  16 use core::ptr::{self, NonNull};
  17 use core::slice::{self};
  18
  19 /// An iterator that moves out of a vector.
  20 ///
  21 /// This `struct` is created by the `into_iter` method on [`Vec`](super::Vec)
  22 /// (provided by the [`IntoIterator`] trait).
  23 ///
  24 /// # Example
  25 ///
  26 /// ```
  27 /// let v = vec![0, 1, 2];
  28 /// let iter: std::vec::IntoIter<_> = v.into_iter();
  29 /// ```
  30 #[stable(feature = "rust1", since = "1.0.0")]
  31 #[rustc_insignificant_dtor]
  32 pub struct IntoIter<
  33     T,
  34     #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
  35 > {
  36     pub(super) buf: NonNull<T>,
  37     pub(super) phantom: PhantomData<T>,
  38     pub(super) cap: usize,
  39     // the drop impl reconstructs a RawVec from buf, cap and alloc
  40     // to avoid dropping the allocator twice we need to wrap it into ManuallyDrop
  41     pub(super) alloc: ManuallyDrop<A>,
  42     pub(super) ptr: *const T,
  43     pub(super) end: *const T, // If T is a ZST, this is actually ptr+len.  This encoding is picked so that
  44                               // ptr == end is a quick test for the Iterator being empty, that works
  45                               // for both ZST and non-ZST.
  46 }
  47
  48 #[stable(feature = "vec_intoiter_debug", since = "1.13.0")]
  49 impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
  50     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
  51         f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
  52     }
  53 }
  54
  55 impl<T, A: Allocator> IntoIter<T, A> {
  56     /// Returns the remaining items of this iterator as a slice.
  57     ///
  58     /// # Examples
  59     ///
  60     /// ```
  61     /// let vec = vec!['a', 'b', 'c'];
  62     /// let mut into_iter = vec.into_iter();
  63     /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
  64     /// let _ = into_iter.next().unwrap();
  65     /// assert_eq!(into_iter.as_slice(), &['b', 'c']);
  66     /// ```
  67     #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
  68     pub fn as_slice(&self) -> &[T] {
  69         unsafe { slice::from_raw_parts(self.ptr, self.len()) }
  70     }
  71
  72     /// Returns the remaining items of this iterator as a mutable slice.
  73     ///
  74     /// # Examples
  75     ///
  76     /// ```
  77     /// let vec = vec!['a', 'b', 'c'];
  78     /// let mut into_iter = vec.into_iter();
  79     /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
  80     /// into_iter.as_mut_slice()[2] = 'z';
  81     /// assert_eq!(into_iter.next().unwrap(), 'a');
  82     /// assert_eq!(into_iter.next().unwrap(), 'b');
  83     /// assert_eq!(into_iter.next().unwrap(), 'z');
  84     /// ```
  85     #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
  86     pub fn as_mut_slice(&mut self) -> &mut [T] {
  87         unsafe { &mut *self.as_raw_mut_slice() }
  88     }
  89
  90     /// Returns a reference to the underlying allocator.
  91     #[unstable(feature = "allocator_api", issue = "32838")]
  92     #[inline]
  93     pub fn allocator(&self) -> &A {
  94         &self.alloc
  95     }
  96
  97     fn as_raw_mut_slice(&mut self) -> *mut [T] {
  98         ptr::slice_from_raw_parts_mut(self.ptr as *mut T, self.len())
  99     }
 100
 101     /// Drops remaining elements and relinquishes the backing allocation.
 102     /// This method guarantees it won't panic before relinquishing
 103     /// the backing allocation.
 104     ///
 105     /// This is roughly equivalent to the following, but more efficient
 106     ///
 107     /// ```
 108     /// # let mut into_iter = Vec::<u8>::with_capacity(10).into_iter();
 109     /// let mut into_iter = std::mem::replace(&mut into_iter, Vec::new().into_iter());
 110     /// (&mut into_iter).for_each(core::mem::drop);
 111     /// std::mem::forget(into_iter);
 112     /// ```
 113     ///
 114     /// This method is used by in-place iteration, refer to the vec::in_place_collect
 115     /// documentation for an overview.
 116     #[cfg(not(no_global_oom_handling))]
 117     pub(super) fn forget_allocation_drop_remaining(&mut self) {
 118         let remaining = self.as_raw_mut_slice();
 119
 120         // overwrite the individual fields instead of creating a new
 121         // struct and then overwriting &mut self.
 122         // this creates less assembly
 123         self.cap = 0;
 124         self.buf = unsafe { NonNull::new_unchecked(RawVec::NEW.ptr()) };
 125         self.ptr = self.buf.as_ptr();
 126         self.end = self.buf.as_ptr();
 127
 128         // Dropping the remaining elements can panic, so this needs to be
 129         // done only after updating the other fields.
 130         unsafe {
 131             ptr::drop_in_place(remaining);
 132         }
 133     }
 134
 135     /// Forgets to Drop the remaining elements while still allowing the backing allocation to be freed.
 136     pub(crate) fn forget_remaining_elements(&mut self) {
 137         // For th ZST case, it is crucial that we mutate `end` here, not `ptr`.
 138         // `ptr` must stay aligned, while `end` may be unaligned.
 139         self.end = self.ptr;
 140     }
 141
 142     #[cfg(not(no_global_oom_handling))]
 143     #[inline]
 144     pub(crate) fn into_vecdeque(self) -> VecDeque<T, A> {
 145         // Keep our `Drop` impl from dropping the elements and the allocator
 146         let mut this = ManuallyDrop::new(self);
 147
 148         // SAFETY: This allocation originally came from a `Vec`, so it passes
 149         // all those checks.  We have `this.buf` ≤ `this.ptr` ≤ `this.end`,
 150         // so the `sub_ptr`s below cannot wrap, and will produce a well-formed
 151         // range.  `end` ≤ `buf + cap`, so the range will be in-bounds.
 152         // Taking `alloc` is ok because nothing else is going to look at it,
 153         // since our `Drop` impl isn't going to run so there's no more code.
 154         unsafe {
 155             let buf = this.buf.as_ptr();
 156             let initialized = if T::IS_ZST {
 157                 // All the pointers are the same for ZSTs, so it's fine to
 158                 // say that they're all at the beginning of the "allocation".
 159                 0..this.len()
 160             } else {
 161                 this.ptr.sub_ptr(buf)..this.end.sub_ptr(buf)
 162             };
 163             let cap = this.cap;
 164             let alloc = ManuallyDrop::take(&mut this.alloc);
 165             VecDeque::from_contiguous_raw_parts_in(buf, initialized, cap, alloc)
 166         }
 167     }
 168 }
 169
 170 #[stable(feature = "vec_intoiter_as_ref", since = "1.46.0")]
 171 impl<T, A: Allocator> AsRef<[T]> for IntoIter<T, A> {
 172     fn as_ref(&self) -> &[T] {
 173         self.as_slice()
 174     }
 175 }
 176
 177 #[stable(feature = "rust1", since = "1.0.0")]
 178 unsafe impl<T: Send, A: Allocator + Send> Send for IntoIter<T, A> {}
 179 #[stable(feature = "rust1", since = "1.0.0")]
 180 unsafe impl<T: Sync, A: Allocator + Sync> Sync for IntoIter<T, A> {}
 181
 182 #[stable(feature = "rust1", since = "1.0.0")]
 183 impl<T, A: Allocator> Iterator for IntoIter<T, A> {
 184     type Item = T;
 185
 186     #[inline]
 187     fn next(&mut self) -> Option<T> {
 188         if self.ptr == self.end {
 189             None
 190         } else if T::IS_ZST {
 191             // `ptr` has to stay where it is to remain aligned, so we reduce the length by 1 by
 192             // reducing the `end`.
 193             self.end = self.end.wrapping_byte_sub(1);
 194
 195             // Make up a value of this ZST.
 196             Some(unsafe { mem::zeroed() })
 197         } else {
 198             let old = self.ptr;
 199             self.ptr = unsafe { self.ptr.add(1) };
 200
 201             Some(unsafe { ptr::read(old) })
 202         }
 203     }
 204
 205     #[inline]
 206     fn size_hint(&self) -> (usize, Option<usize>) {
 207         let exact = if T::IS_ZST {
 208             self.end.addr().wrapping_sub(self.ptr.addr())
 209         } else {
 210             unsafe { self.end.sub_ptr(self.ptr) }
 211         };
 212         (exact, Some(exact))
 213     }
 214
 215     #[inline]
 216     fn advance_by(&mut self, n: usize) -> Result<(), usize> {
 217         let step_size = self.len().min(n);
 218         let to_drop = ptr::slice_from_raw_parts_mut(self.ptr as *mut T, step_size);
 219         if T::IS_ZST {
 220             // See `next` for why we sub `end` here.
 221             self.end = self.end.wrapping_byte_sub(step_size);
 222         } else {
 223             // SAFETY: the min() above ensures that step_size is in bounds
 224             self.ptr = unsafe { self.ptr.add(step_size) };
 225         }
 226         // SAFETY: the min() above ensures that step_size is in bounds
 227         unsafe {
 228             ptr::drop_in_place(to_drop);
 229         }
 230         if step_size < n {
 231             return Err(step_size);
 232         }
 233         Ok(())
 234     }
 235
 236     #[inline]
 237     fn count(self) -> usize {
 238         self.len()
 239     }
 240
 241     #[inline]
 242     fn next_chunk<const N: usize>(&mut self) -> Result<[T; N], core::array::IntoIter<T, N>> {
 243         let mut raw_ary = MaybeUninit::uninit_array();
 244
 245         let len = self.len();
 246
 247         if T::IS_ZST {
 248             if len < N {
 249                 self.forget_remaining_elements();
 250                 // Safety: ZSTs can be conjured ex nihilo, only the amount has to be correct
 251                 return Err(unsafe { array::IntoIter::new_unchecked(raw_ary, 0..len) });
 252             }
 253
 254             self.end = self.end.wrapping_byte_sub(N);
 255             // Safety: ditto
 256             return Ok(unsafe { raw_ary.transpose().assume_init() });
 257         }
 258
 259         if len < N {
 260             // Safety: `len` indicates that this many elements are available and we just checked that
 261             // it fits into the array.
 262             unsafe {
 263                 ptr::copy_nonoverlapping(self.ptr, raw_ary.as_mut_ptr() as *mut T, len);
 264                 self.forget_remaining_elements();
 265                 return Err(array::IntoIter::new_unchecked(raw_ary, 0..len));
 266             }
 267         }
 268
 269         // Safety: `len` is larger than the array size. Copy a fixed amount here to fully initialize
 270         // the array.
 271         return unsafe {
 272             ptr::copy_nonoverlapping(self.ptr, raw_ary.as_mut_ptr() as *mut T, N);
 273             self.ptr = self.ptr.add(N);
 274             Ok(raw_ary.transpose().assume_init())
 275         };
 276     }
 277
 278     unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> Self::Item
 279     where
 280         Self: TrustedRandomAccessNoCoerce,
 281     {
 282         // SAFETY: the caller must guarantee that `i` is in bounds of the
 283         // `Vec<T>`, so `i` cannot overflow an `isize`, and the `self.ptr.add(i)`
 284         // is guaranteed to pointer to an element of the `Vec<T>` and
 285         // thus guaranteed to be valid to dereference.
 286         //
 287         // Also note the implementation of `Self: TrustedRandomAccess` requires
 288         // that `T: Copy` so reading elements from the buffer doesn't invalidate
 289         // them for `Drop`.
 290         unsafe {
 291             if T::IS_ZST { mem::zeroed() } else { ptr::read(self.ptr.add(i)) }
 292         }
 293     }
 294 }
 295
 296 #[stable(feature = "rust1", since = "1.0.0")]
 297 impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
 298     #[inline]
 299     fn next_back(&mut self) -> Option<T> {
 300         if self.end == self.ptr {
 301             None
 302         } else if T::IS_ZST {
 303             // See above for why 'ptr.offset' isn't used
 304             self.end = self.end.wrapping_byte_sub(1);
 305
 306             // Make up a value of this ZST.
 307             Some(unsafe { mem::zeroed() })
 308         } else {
 309             self.end = unsafe { self.end.sub(1) };
 310
 311             Some(unsafe { ptr::read(self.end) })
 312         }
 313     }
 314
 315     #[inline]
 316     fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
 317         let step_size = self.len().min(n);
 318         if T::IS_ZST {
 319             // SAFETY: same as for advance_by()
 320             self.end = self.end.wrapping_byte_sub(step_size);
 321         } else {
 322             // SAFETY: same as for advance_by()
 323             self.end = unsafe { self.end.sub(step_size) };
 324         }
 325         let to_drop = ptr::slice_from_raw_parts_mut(self.end as *mut T, step_size);
 326         // SAFETY: same as for advance_by()
 327         unsafe {
 328             ptr::drop_in_place(to_drop);
 329         }
 330         if step_size < n {
 331             return Err(step_size);
 332         }
 333         Ok(())
 334     }
 335 }
 336
 337 #[stable(feature = "rust1", since = "1.0.0")]
 338 impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {
 339     fn is_empty(&self) -> bool {
 340         self.ptr == self.end
 341     }
 342 }
 343
 344 #[stable(feature = "fused", since = "1.26.0")]
 345 impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}
 346
 347 #[unstable(feature = "trusted_len", issue = "37572")]
 348 unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {}
 349
 350 #[doc(hidden)]
 351 #[unstable(issue = "none", feature = "std_internals")]
 352 #[rustc_unsafe_specialization_marker]
 353 pub trait NonDrop {}
 354
 355 // T: Copy as approximation for !Drop since get_unchecked does not advance self.ptr
 356 // and thus we can't implement drop-handling
 357 #[unstable(issue = "none", feature = "std_internals")]
 358 impl<T: Copy> NonDrop for T {}
 359
 360 #[doc(hidden)]
 361 #[unstable(issue = "none", feature = "std_internals")]
 362 // TrustedRandomAccess (without NoCoerce) must not be implemented because
 363 // subtypes/supertypes of `T` might not be `NonDrop`
 364 unsafe impl<T, A: Allocator> TrustedRandomAccessNoCoerce for IntoIter<T, A>
 365 where
 366     T: NonDrop,
 367 {
 368     const MAY_HAVE_SIDE_EFFECT: bool = false;
 369 }
 370
 371 #[cfg(not(no_global_oom_handling))]
 372 #[stable(feature = "vec_into_iter_clone", since = "1.8.0")]
 373 impl<T: Clone, A: Allocator + Clone> Clone for IntoIter<T, A> {
 374     #[cfg(not(test))]
 375     fn clone(&self) -> Self {
 376         self.as_slice().to_vec_in(self.alloc.deref().clone()).into_iter()
 377     }
 378     #[cfg(test)]
 379     fn clone(&self) -> Self {
 380         crate::slice::to_vec(self.as_slice(), self.alloc.deref().clone()).into_iter()
 381     }
 382 }
 383
 384 #[stable(feature = "rust1", since = "1.0.0")]
 385 unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter<T, A> {
 386     fn drop(&mut self) {
 387         struct DropGuard<'a, T, A: Allocator>(&'a mut IntoIter<T, A>);
 388
 389         impl<T, A: Allocator> Drop for DropGuard<'_, T, A> {
 390             fn drop(&mut self) {
 391                 unsafe {
 392                     // `IntoIter::alloc` is not used anymore after this and will be dropped by RawVec
 393                     let alloc = ManuallyDrop::take(&mut self.0.alloc);
 394                     // RawVec handles deallocation
 395                     let _ = RawVec::from_raw_parts_in(self.0.buf.as_ptr(), self.0.cap, alloc);
 396                 }
 397             }
 398         }
 399
 400         let guard = DropGuard(self);
 401         // destroy the remaining elements
 402         unsafe {
 403             ptr::drop_in_place(guard.0.as_raw_mut_slice());
 404         }
 405         // now `guard` will be dropped and do the rest
 406     }
 407 }
 408
 409 // In addition to the SAFETY invariants of the following three unsafe traits
 410 // also refer to the vec::in_place_collect module documentation to get an overview
 411 #[unstable(issue = "none", feature = "inplace_iteration")]
 412 #[doc(hidden)]
 413 unsafe impl<T, A: Allocator> InPlaceIterable for IntoIter<T, A> {}
 414
 415 #[unstable(issue = "none", feature = "inplace_iteration")]
 416 #[doc(hidden)]
 417 unsafe impl<T, A: Allocator> SourceIter for IntoIter<T, A> {
 418     type Source = Self;
 419
 420     #[inline]
 421     unsafe fn as_inner(&mut self) -> &mut Self::Source {
 422         self
 423     }
 424 }
 425
 426 #[cfg(not(no_global_oom_handling))]
 427 unsafe impl<T> AsVecIntoIter for IntoIter<T> {
 428     type Item = T;
 429
 430     fn as_into_iter(&mut self) -> &mut IntoIter<Self::Item> {
 431         self
 432     }
 433 }