library/core/src/array/iter.rs

   1 //! Defines the `IntoIter` owned iterator for arrays.
   2
   3 use crate::{
   4     fmt,
   5     iter::{self, ExactSizeIterator, FusedIterator, TrustedLen, TrustedRandomAccess},
   6     mem::{self, MaybeUninit},
   7     ops::Range,
   8     ptr,
   9 };
  10
  11 /// A by-value [array] iterator.
  12 #[stable(feature = "array_value_iter", since = "1.51.0")]
  13 pub struct IntoIter<T, const N: usize> {
  14     /// This is the array we are iterating over.
  15     ///
  16     /// Elements with index `i` where `alive.start <= i < alive.end` have not
  17     /// been yielded yet and are valid array entries. Elements with indices `i
  18     /// < alive.start` or `i >= alive.end` have been yielded already and must
  19     /// not be accessed anymore! Those dead elements might even be in a
  20     /// completely uninitialized state!
  21     ///
  22     /// So the invariants are:
  23     /// - `data[alive]` is alive (i.e. contains valid elements)
  24     /// - `data[..alive.start]` and `data[alive.end..]` are dead (i.e. the
  25     ///   elements were already read and must not be touched anymore!)
  26     data: [MaybeUninit<T>; N],
  27
  28     /// The elements in `data` that have not been yielded yet.
  29     ///
  30     /// Invariants:
  31     /// - `alive.start <= alive.end`
  32     /// - `alive.end <= N`
  33     alive: Range<usize>,
  34 }
  35
  36 impl<T, const N: usize> IntoIter<T, N> {
  37     /// Creates a new iterator over the given `array`.
  38     ///
  39     /// *Note*: this method might be deprecated in the future,
  40     /// after [`IntoIterator` is implemented for arrays][array-into-iter].
  41     ///
  42     /// # Examples
  43     ///
  44     /// ```
  45     /// use std::array;
  46     ///
  47     /// for value in array::IntoIter::new([1, 2, 3, 4, 5]) {
  48     ///     // The type of `value` is a `i32` here, instead of `&i32`
  49     ///     let _: i32 = value;
  50     /// }
  51     /// ```
  52     /// [array-into-iter]: https://github.com/rust-lang/rust/pull/65819
  53     #[stable(feature = "array_value_iter", since = "1.51.0")]
  54     pub fn new(array: [T; N]) -> Self {
  55         // SAFETY: The transmute here is actually safe. The docs of `MaybeUninit`
  56         // promise:
  57         //
  58         // > `MaybeUninit<T>` is guaranteed to have the same size and alignment
  59         // > as `T`.
  60         //
  61         // The docs even show a transmute from an array of `MaybeUninit<T>` to
  62         // an array of `T`.
  63         //
  64         // With that, this initialization satisfies the invariants.
  65
  66         // FIXME(LukasKalbertodt): actually use `mem::transmute` here, once it
  67         // works with const generics:
  68         //     `mem::transmute::<[T; N], [MaybeUninit<T>; N]>(array)`
  69         //
  70         // Until then, we can use `mem::transmute_copy` to create a bitwise copy
  71         // as a different type, then forget `array` so that it is not dropped.
  72         unsafe {
  73             let iter = Self { data: mem::transmute_copy(&array), alive: 0..N };
  74             mem::forget(array);
  75             iter
  76         }
  77     }
  78
  79     /// Returns an immutable slice of all elements that have not been yielded
  80     /// yet.
  81     #[stable(feature = "array_value_iter", since = "1.51.0")]
  82     pub fn as_slice(&self) -> &[T] {
  83         // SAFETY: We know that all elements within `alive` are properly initialized.
  84         unsafe {
  85             let slice = self.data.get_unchecked(self.alive.clone());
  86             MaybeUninit::slice_assume_init_ref(slice)
  87         }
  88     }
  89
  90     /// Returns a mutable slice of all elements that have not been yielded yet.
  91     #[stable(feature = "array_value_iter", since = "1.51.0")]
  92     pub fn as_mut_slice(&mut self) -> &mut [T] {
  93         // SAFETY: We know that all elements within `alive` are properly initialized.
  94         unsafe {
  95             let slice = self.data.get_unchecked_mut(self.alive.clone());
  96             MaybeUninit::slice_assume_init_mut(slice)
  97         }
  98     }
  99 }
 100
 101 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 102 impl<T, const N: usize> Iterator for IntoIter<T, N> {
 103     type Item = T;
 104     fn next(&mut self) -> Option<Self::Item> {
 105         // Get the next index from the front.
 106         //
 107         // Increasing `alive.start` by 1 maintains the invariant regarding
 108         // `alive`. However, due to this change, for a short time, the alive
 109         // zone is not `data[alive]` anymore, but `data[idx..alive.end]`.
 110         self.alive.next().map(|idx| {
 111             // Read the element from the array.
 112             // SAFETY: `idx` is an index into the former "alive" region of the
 113             // array. Reading this element means that `data[idx]` is regarded as
 114             // dead now (i.e. do not touch). As `idx` was the start of the
 115             // alive-zone, the alive zone is now `data[alive]` again, restoring
 116             // all invariants.
 117             unsafe { self.data.get_unchecked(idx).assume_init_read() }
 118         })
 119     }
 120
 121     fn size_hint(&self) -> (usize, Option<usize>) {
 122         let len = self.len();
 123         (len, Some(len))
 124     }
 125
 126     fn count(self) -> usize {
 127         self.len()
 128     }
 129
 130     fn last(mut self) -> Option<Self::Item> {
 131         self.next_back()
 132     }
 133
 134     #[inline]
 135     #[doc(hidden)]
 136     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item
 137     where
 138         Self: TrustedRandomAccess,
 139     {
 140         // SAFETY: Callers are only allowed to pass an index that is in bounds
 141         // Additionally Self: TrustedRandomAccess is only implemented for T: Copy which means even
 142         // multiple repeated reads of the same index would be safe and the
 143         // values are !Drop, thus won't suffer from double drops.
 144         unsafe { self.data.get_unchecked(self.alive.start + idx).assume_init_read() }
 145     }
 146 }
 147
 148 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 149 impl<T, const N: usize> DoubleEndedIterator for IntoIter<T, N> {
 150     fn next_back(&mut self) -> Option<Self::Item> {
 151         // Get the next index from the back.
 152         //
 153         // Decreasing `alive.end` by 1 maintains the invariant regarding
 154         // `alive`. However, due to this change, for a short time, the alive
 155         // zone is not `data[alive]` anymore, but `data[alive.start..=idx]`.
 156         self.alive.next_back().map(|idx| {
 157             // Read the element from the array.
 158             // SAFETY: `idx` is an index into the former "alive" region of the
 159             // array. Reading this element means that `data[idx]` is regarded as
 160             // dead now (i.e. do not touch). As `idx` was the end of the
 161             // alive-zone, the alive zone is now `data[alive]` again, restoring
 162             // all invariants.
 163             unsafe { self.data.get_unchecked(idx).assume_init_read() }
 164         })
 165     }
 166 }
 167
 168 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 169 impl<T, const N: usize> Drop for IntoIter<T, N> {
 170     fn drop(&mut self) {
 171         // SAFETY: This is safe: `as_mut_slice` returns exactly the sub-slice
 172         // of elements that have not been moved out yet and that remain
 173         // to be dropped.
 174         unsafe { ptr::drop_in_place(self.as_mut_slice()) }
 175     }
 176 }
 177
 178 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 179 impl<T, const N: usize> ExactSizeIterator for IntoIter<T, N> {
 180     fn len(&self) -> usize {
 181         // Will never underflow due to the invariant `alive.start <=
 182         // alive.end`.
 183         self.alive.end - self.alive.start
 184     }
 185     fn is_empty(&self) -> bool {
 186         self.alive.is_empty()
 187     }
 188 }
 189
 190 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 191 impl<T, const N: usize> FusedIterator for IntoIter<T, N> {}
 192
 193 // The iterator indeed reports the correct length. The number of "alive"
 194 // elements (that will still be yielded) is the length of the range `alive`.
 195 // This range is decremented in length in either `next` or `next_back`. It is
 196 // always decremented by 1 in those methods, but only if `Some(_)` is returned.
 197 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 198 unsafe impl<T, const N: usize> TrustedLen for IntoIter<T, N> {}
 199
 200 #[doc(hidden)]
 201 #[unstable(feature = "trusted_random_access", issue = "none")]
 202 // T: Copy as approximation for !Drop since get_unchecked does not update the pointers
 203 // and thus we can't implement drop-handling
 204 unsafe impl<T, const N: usize> TrustedRandomAccess for IntoIter<T, N>
 205 where
 206     T: Copy,
 207 {
 208     const MAY_HAVE_SIDE_EFFECT: bool = false;
 209 }
 210
 211 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 212 impl<T: Clone, const N: usize> Clone for IntoIter<T, N> {
 213     fn clone(&self) -> Self {
 214         // Note, we don't really need to match the exact same alive range, so
 215         // we can just clone into offset 0 regardless of where `self` is.
 216         let mut new = Self { data: MaybeUninit::uninit_array(), alive: 0..0 };
 217
 218         // Clone all alive elements.
 219         for (src, dst) in iter::zip(self.as_slice(), &mut new.data) {
 220             // Write a clone into the new array, then update its alive range.
 221             // If cloning panics, we'll correctly drop the previous items.
 222             dst.write(src.clone());
 223             new.alive.end += 1;
 224         }
 225
 226         new
 227     }
 228 }
 229
 230 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 231 impl<T: fmt::Debug, const N: usize> fmt::Debug for IntoIter<T, N> {
 232     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 233         // Only print the elements that were not yielded yet: we cannot
 234         // access the yielded elements anymore.
 235         f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
 236     }
 237 }