src/libcore/array/iter.rs

   1 //! Defines the `IntoIter` owned iterator for arrays.
   2
   3 use super::LengthAtMost32;
   4 use crate::{
   5     fmt,
   6     iter::{ExactSizeIterator, FusedIterator, TrustedLen},
   7     mem::{self, MaybeUninit},
   8     ops::Range,
   9     ptr,
  10 };
  11
  12 /// A by-value [array] iterator.
  13 ///
  14 /// [array]: ../../std/primitive.array.html
  15 #[unstable(feature = "array_value_iter", issue = "65798")]
  16 pub struct IntoIter<T, const N: usize>
  17 where
  18     [T; N]: LengthAtMost32,
  19 {
  20     /// This is the array we are iterating over.
  21     ///
  22     /// Elements with index `i` where `alive.start <= i < alive.end` have not
  23     /// been yielded yet and are valid array entries. Elements with indices `i
  24     /// < alive.start` or `i >= alive.end` have been yielded already and must
  25     /// not be accessed anymore! Those dead elements might even be in a
  26     /// completely uninitialized state!
  27     ///
  28     /// So the invariants are:
  29     /// - `data[alive]` is alive (i.e. contains valid elements)
  30     /// - `data[..alive.start]` and `data[alive.end..]` are dead (i.e. the
  31     ///   elements were already read and must not be touched anymore!)
  32     data: [MaybeUninit<T>; N],
  33
  34     /// The elements in `data` that have not been yielded yet.
  35     ///
  36     /// Invariants:
  37     /// - `alive.start <= alive.end`
  38     /// - `alive.end <= N`
  39     alive: Range<usize>,
  40 }
  41
  42 impl<T, const N: usize> IntoIter<T, N>
  43 where
  44     [T; N]: LengthAtMost32,
  45 {
  46     /// Creates a new iterator over the given `array`.
  47     ///
  48     /// *Note*: this method might never get stabilized and/or removed in the
  49     /// future as there will likely be another, preferred way of obtaining this
  50     /// iterator (either via `IntoIterator` for arrays or via another way).
  51     #[unstable(feature = "array_value_iter", issue = "65798")]
  52     pub fn new(array: [T; N]) -> Self {
  53         // SAFETY: The transmute here is actually safe. The docs of `MaybeUninit`
  54         // promise:
  55         //
  56         // > `MaybeUninit<T>` is guaranteed to have the same size and alignment
  57         // > as `T`.
  58         //
  59         // The docs even show a transmute from an array of `MaybeUninit<T>` to
  60         // an array of `T`.
  61         //
  62         // With that, this initialization satisfies the invariants.
  63
  64         // FIXME(LukasKalbertodt): actually use `mem::transmute` here, once it
  65         // works with const generics:
  66         //     `mem::transmute::<[T; {N}], [MaybeUninit<T>; {N}]>(array)`
  67         //
  68         // Until then, we do it manually here. We first create a bitwise copy
  69         // but cast the pointer so that it is treated as a different type. Then
  70         // we forget `array` so that it is not dropped.
  71         let data = unsafe {
  72             let data = ptr::read(&array as *const [T; N] as *const [MaybeUninit<T>; N]);
  73             mem::forget(array);
  74             data
  75         };
  76
  77         Self { data, alive: 0..N }
  78     }
  79
  80     /// Returns an immutable slice of all elements that have not been yielded
  81     /// yet.
  82     fn as_slice(&self) -> &[T] {
  83         let slice = &self.data[self.alive.clone()];
  84         // SAFETY: This transmute is safe. As mentioned in `new`, `MaybeUninit` retains
  85         // the size and alignment of `T`. Furthermore, we know that all
  86         // elements within `alive` are properly initialized.
  87         unsafe { mem::transmute::<&[MaybeUninit<T>], &[T]>(slice) }
  88     }
  89
  90     /// Returns a mutable slice of all elements that have not been yielded yet.
  91     fn as_mut_slice(&mut self) -> &mut [T] {
  92         // This transmute is safe, same as in `as_slice` above.
  93         let slice = &mut self.data[self.alive.clone()];
  94         // SAFETY: This transmute is safe. As mentioned in `new`, `MaybeUninit` retains
  95         // the size and alignment of `T`. Furthermore, we know that all
  96         // elements within `alive` are properly initialized.
  97         unsafe { mem::transmute::<&mut [MaybeUninit<T>], &mut [T]>(slice) }
  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 where
 104     [T; N]: LengthAtMost32,
 105 {
 106     type Item = T;
 107     fn next(&mut self) -> Option<Self::Item> {
 108         if self.alive.start == self.alive.end {
 109             return None;
 110         }
 111
 112         // Bump start index.
 113         //
 114         // From the check above we know that `alive.start != alive.end`.
 115         // Combine this with the invariant `alive.start <= alive.end`, we know
 116         // that `alive.start < alive.end`. Increasing `alive.start` by 1
 117         // maintains the invariant regarding `alive`. However, due to this
 118         // change, for a short time, the alive zone is not `data[alive]`
 119         // anymore, but `data[idx..alive.end]`.
 120         let idx = self.alive.start;
 121         self.alive.start += 1;
 122
 123         // Read the element from the array.
 124         // SAFETY: This is safe: `idx` is an index
 125         // into the "alive" region of the array. Reading this element means
 126         // that `data[idx]` is regarded as dead now (i.e. do not touch). As
 127         // `idx` was the start of the alive-zone, the alive zone is now
 128         // `data[alive]` again, restoring all invariants.
 129         let out = unsafe { self.data.get_unchecked(idx).read() };
 130
 131         Some(out)
 132     }
 133
 134     fn size_hint(&self) -> (usize, Option<usize>) {
 135         let len = self.len();
 136         (len, Some(len))
 137     }
 138
 139     fn count(self) -> usize {
 140         self.len()
 141     }
 142
 143     fn last(mut self) -> Option<Self::Item> {
 144         self.next_back()
 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 where
 151     [T; N]: LengthAtMost32,
 152 {
 153     fn next_back(&mut self) -> Option<Self::Item> {
 154         if self.alive.start == self.alive.end {
 155             return None;
 156         }
 157
 158         // Decrease end index.
 159         //
 160         // From the check above we know that `alive.start != alive.end`.
 161         // Combine this with the invariant `alive.start <= alive.end`, we know
 162         // that `alive.start < alive.end`. As `alive.start` cannot be negative,
 163         // `alive.end` is at least 1, meaning that we can safely decrement it
 164         // by one. This also maintains the invariant `alive.start <=
 165         // alive.end`. However, due to this change, for a short time, the alive
 166         // zone is not `data[alive]` anymore, but `data[alive.start..alive.end
 167         // + 1]`.
 168         self.alive.end -= 1;
 169
 170         // Read the element from the array.
 171         // SAFETY: This is safe: `alive.end` is an
 172         // index into the "alive" region of the array. Compare the previous
 173         // comment that states that the alive region is
 174         // `data[alive.start..alive.end + 1]`. Reading this element means that
 175         // `data[alive.end]` is regarded as dead now (i.e. do not touch). As
 176         // `alive.end` was the end of the alive-zone, the alive zone is now
 177         // `data[alive]` again, restoring all invariants.
 178         let out = unsafe { self.data.get_unchecked(self.alive.end).read() };
 179
 180         Some(out)
 181     }
 182 }
 183
 184 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 185 impl<T, const N: usize> Drop for IntoIter<T, N>
 186 where
 187     [T; N]: LengthAtMost32,
 188 {
 189     fn drop(&mut self) {
 190         // SAFETY: This is safe: `as_mut_slice` returns exactly the sub-slice
 191         // of elements that have not been moved out yet and that remain
 192         // to be dropped.
 193         unsafe { ptr::drop_in_place(self.as_mut_slice()) }
 194     }
 195 }
 196
 197 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 198 impl<T, const N: usize> ExactSizeIterator for IntoIter<T, N>
 199 where
 200     [T; N]: LengthAtMost32,
 201 {
 202     fn len(&self) -> usize {
 203         // Will never underflow due to the invariant `alive.start <=
 204         // alive.end`.
 205         self.alive.end - self.alive.start
 206     }
 207     fn is_empty(&self) -> bool {
 208         self.alive.is_empty()
 209     }
 210 }
 211
 212 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 213 impl<T, const N: usize> FusedIterator for IntoIter<T, N> where [T; N]: LengthAtMost32 {}
 214
 215 // The iterator indeed reports the correct length. The number of "alive"
 216 // elements (that will still be yielded) is the length of the range `alive`.
 217 // This range is decremented in length in either `next` or `next_back`. It is
 218 // always decremented by 1 in those methods, but only if `Some(_)` is returned.
 219 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 220 unsafe impl<T, const N: usize> TrustedLen for IntoIter<T, N> where [T; N]: LengthAtMost32 {}
 221
 222 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 223 impl<T: Clone, const N: usize> Clone for IntoIter<T, N>
 224 where
 225     [T; N]: LengthAtMost32,
 226 {
 227     fn clone(&self) -> Self {
 228         // SAFETY: each point of unsafety is documented inside the unsafe block
 229         unsafe {
 230             // This creates a new uninitialized array. Note that the `assume_init`
 231             // refers to the array, not the individual elements. And it is Ok if
 232             // the array is in an uninitialized state as all elements may be
 233             // uninitialized (all bit patterns are valid). Compare the
 234             // `MaybeUninit` docs for more information.
 235             let mut new_data: [MaybeUninit<T>; N] = MaybeUninit::uninit().assume_init();
 236
 237             // Clone all alive elements.
 238             for idx in self.alive.clone() {
 239                 // The element at `idx` in the old array is alive, so we can
 240                 // safely call `get_ref()`. We then clone it, and write the
 241                 // clone into the new array.
 242                 let clone = self.data.get_unchecked(idx).get_ref().clone();
 243                 new_data.get_unchecked_mut(idx).write(clone);
 244             }
 245
 246             Self { data: new_data, alive: self.alive.clone() }
 247         }
 248     }
 249 }
 250
 251 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 252 impl<T: fmt::Debug, const N: usize> fmt::Debug for IntoIter<T, N>
 253 where
 254     [T; N]: LengthAtMost32,
 255 {
 256     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 257         // Only print the elements that were not yielded yet: we cannot
 258         // access the yielded elements anymore.
 259         f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
 260     }
 261 }