library/core/src/array/iter.rs

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