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