into_iter.rs - source
Description: Source of the Rust file `library/alloc/src/vec/into_iter.rs`.

#
alloc/vec/
into_iter.rs

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