rust/alloc/vec/into_iter.rs

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