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},
   6     mem::{self, MaybeUninit},
   7     ops::{IndexRange, Range},
   8     ptr,
   9 };
  10
  11 /// A by-value [array] iterator.
  12 #[stable(feature = "array_value_iter", since = "1.51.0")]
  13 #[rustc_insignificant_dtor]
  14 pub struct IntoIter<T, const N: usize> {
  15     /// This is the array we are iterating over.
  16     ///
  17     /// Elements with index `i` where `alive.start <= i < alive.end` have not
  18     /// been yielded yet and are valid array entries. Elements with indices `i
  19     /// < alive.start` or `i >= alive.end` have been yielded already and must
  20     /// not be accessed anymore! Those dead elements might even be in a
  21     /// completely uninitialized state!
  22     ///
  23     /// So the invariants are:
  24     /// - `data[alive]` is alive (i.e. contains valid elements)
  25     /// - `data[..alive.start]` and `data[alive.end..]` are dead (i.e. the
  26     ///   elements were already read and must not be touched anymore!)
  27     data: [MaybeUninit<T>; N],
  28
  29     /// The elements in `data` that have not been yielded yet.
  30     ///
  31     /// Invariants:
  32     /// - `alive.end <= N`
  33     ///
  34     /// (And the `IndexRange` type requires `alive.start <= alive.end`.)
  35     alive: IndexRange,
  36 }
  37
  38 // Note: the `#[rustc_skip_array_during_method_dispatch]` on `trait IntoIterator`
  39 // hides this implementation from explicit `.into_iter()` calls on editions < 2021,
  40 // so those calls will still resolve to the slice implementation, by reference.
  41 #[stable(feature = "array_into_iter_impl", since = "1.53.0")]
  42 impl<T, const N: usize> IntoIterator for [T; N] {
  43     type Item = T;
  44     type IntoIter = IntoIter<T, N>;
  45
  46     /// Creates a consuming iterator, that is, one that moves each value out of
  47     /// the array (from start to end). The array cannot be used after calling
  48     /// this unless `T` implements `Copy`, so the whole array is copied.
  49     ///
  50     /// Arrays have special behavior when calling `.into_iter()` prior to the
  51     /// 2021 edition -- see the [array] Editions section for more information.
  52     ///
  53     /// [array]: prim@array
  54     fn into_iter(self) -> Self::IntoIter {
  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 = IntoIter { data: mem::transmute_copy(&self), alive: IndexRange::zero_to(N) };
  74             mem::forget(self);
  75             iter
  76         }
  77     }
  78 }
  79
  80 impl<T, const N: usize> IntoIter<T, N> {
  81     /// Creates a new iterator over the given `array`.
  82     #[stable(feature = "array_value_iter", since = "1.51.0")]
  83     #[deprecated(since = "1.59.0", note = "use `IntoIterator::into_iter` instead")]
  84     pub fn new(array: [T; N]) -> Self {
  85         IntoIterator::into_iter(array)
  86     }
  87
  88     /// Creates an iterator over the elements in a partially-initialized buffer.
  89     ///
  90     /// If you have a fully-initialized array, then use [`IntoIterator`].
  91     /// But this is useful for returning partial results from unsafe code.
  92     ///
  93     /// # Safety
  94     ///
  95     /// - The `buffer[initialized]` elements must all be initialized.
  96     /// - The range must be canonical, with `initialized.start <= initialized.end`.
  97     /// - The range must be in-bounds for the buffer, with `initialized.end <= N`.
  98     ///   (Like how indexing `[0][100..100]` fails despite the range being empty.)
  99     ///
 100     /// It's sound to have more elements initialized than mentioned, though that
 101     /// will most likely result in them being leaked.
 102     ///
 103     /// # Examples
 104     ///
 105     /// ```
 106     /// #![feature(array_into_iter_constructors)]
 107     ///
 108     /// #![feature(maybe_uninit_array_assume_init)]
 109     /// #![feature(maybe_uninit_uninit_array)]
 110     /// use std::array::IntoIter;
 111     /// use std::mem::MaybeUninit;
 112     ///
 113     /// # // Hi!  Thanks for reading the code.  This is restricted to `Copy` because
 114     /// # // otherwise it could leak.  A fully-general version this would need a drop
 115     /// # // guard to handle panics from the iterator, but this works for an example.
 116     /// fn next_chunk<T: Copy, const N: usize>(
 117     ///     it: &mut impl Iterator<Item = T>,
 118     /// ) -> Result<[T; N], IntoIter<T, N>> {
 119     ///     let mut buffer = MaybeUninit::uninit_array();
 120     ///     let mut i = 0;
 121     ///     while i < N {
 122     ///         match it.next() {
 123     ///             Some(x) => {
 124     ///                 buffer[i].write(x);
 125     ///                 i += 1;
 126     ///             }
 127     ///             None => {
 128     ///                 // SAFETY: We've initialized the first `i` items
 129     ///                 unsafe {
 130     ///                     return Err(IntoIter::new_unchecked(buffer, 0..i));
 131     ///                 }
 132     ///             }
 133     ///         }
 134     ///     }
 135     ///
 136     ///     // SAFETY: We've initialized all N items
 137     ///     unsafe { Ok(MaybeUninit::array_assume_init(buffer)) }
 138     /// }
 139     ///
 140     /// let r: [_; 4] = next_chunk(&mut (10..16)).unwrap();
 141     /// assert_eq!(r, [10, 11, 12, 13]);
 142     /// let r: IntoIter<_, 40> = next_chunk(&mut (10..16)).unwrap_err();
 143     /// assert_eq!(r.collect::<Vec<_>>(), vec![10, 11, 12, 13, 14, 15]);
 144     /// ```
 145     #[unstable(feature = "array_into_iter_constructors", issue = "91583")]
 146     #[rustc_const_unstable(feature = "const_array_into_iter_constructors", issue = "91583")]
 147     pub const unsafe fn new_unchecked(
 148         buffer: [MaybeUninit<T>; N],
 149         initialized: Range<usize>,
 150     ) -> Self {
 151         // SAFETY: one of our safety conditions is that the range is canonical.
 152         let alive = unsafe { IndexRange::new_unchecked(initialized.start, initialized.end) };
 153         Self { data: buffer, alive }
 154     }
 155
 156     /// Creates an iterator over `T` which returns no elements.
 157     ///
 158     /// If you just need an empty iterator, then use
 159     /// [`iter::empty()`](crate::iter::empty) instead.
 160     /// And if you need an empty array, use `[]`.
 161     ///
 162     /// But this is useful when you need an `array::IntoIter<T, N>` *specifically*.
 163     ///
 164     /// # Examples
 165     ///
 166     /// ```
 167     /// #![feature(array_into_iter_constructors)]
 168     /// use std::array::IntoIter;
 169     ///
 170     /// let empty = IntoIter::<i32, 3>::empty();
 171     /// assert_eq!(empty.len(), 0);
 172     /// assert_eq!(empty.as_slice(), &[]);
 173     ///
 174     /// let empty = IntoIter::<std::convert::Infallible, 200>::empty();
 175     /// assert_eq!(empty.len(), 0);
 176     /// ```
 177     ///
 178     /// `[1, 2].into_iter()` and `[].into_iter()` have different types
 179     /// ```should_fail,edition2021
 180     /// #![feature(array_into_iter_constructors)]
 181     /// use std::array::IntoIter;
 182     ///
 183     /// pub fn get_bytes(b: bool) -> IntoIter<i8, 4> {
 184     ///     if b {
 185     ///         [1, 2, 3, 4].into_iter()
 186     ///     } else {
 187     ///         [].into_iter() // error[E0308]: mismatched types
 188     ///     }
 189     /// }
 190     /// ```
 191     ///
 192     /// But using this method you can get an empty iterator of appropriate size:
 193     /// ```edition2021
 194     /// #![feature(array_into_iter_constructors)]
 195     /// use std::array::IntoIter;
 196     ///
 197     /// pub fn get_bytes(b: bool) -> IntoIter<i8, 4> {
 198     ///     if b {
 199     ///         [1, 2, 3, 4].into_iter()
 200     ///     } else {
 201     ///         IntoIter::empty()
 202     ///     }
 203     /// }
 204     ///
 205     /// assert_eq!(get_bytes(true).collect::<Vec<_>>(), vec![1, 2, 3, 4]);
 206     /// assert_eq!(get_bytes(false).collect::<Vec<_>>(), vec![]);
 207     /// ```
 208     #[unstable(feature = "array_into_iter_constructors", issue = "91583")]
 209     #[rustc_const_unstable(feature = "const_array_into_iter_constructors", issue = "91583")]
 210     pub const fn empty() -> Self {
 211         let buffer = MaybeUninit::uninit_array();
 212         let initialized = 0..0;
 213
 214         // SAFETY: We're telling it that none of the elements are initialized,
 215         // which is trivially true.  And ∀N: usize, 0 <= N.
 216         unsafe { Self::new_unchecked(buffer, initialized) }
 217     }
 218
 219     /// Returns an immutable slice of all elements that have not been yielded
 220     /// yet.
 221     #[stable(feature = "array_value_iter", since = "1.51.0")]
 222     pub fn as_slice(&self) -> &[T] {
 223         // SAFETY: We know that all elements within `alive` are properly initialized.
 224         unsafe {
 225             let slice = self.data.get_unchecked(self.alive.clone());
 226             MaybeUninit::slice_assume_init_ref(slice)
 227         }
 228     }
 229
 230     /// Returns a mutable slice of all elements that have not been yielded yet.
 231     #[stable(feature = "array_value_iter", since = "1.51.0")]
 232     pub fn as_mut_slice(&mut self) -> &mut [T] {
 233         // SAFETY: We know that all elements within `alive` are properly initialized.
 234         unsafe {
 235             let slice = self.data.get_unchecked_mut(self.alive.clone());
 236             MaybeUninit::slice_assume_init_mut(slice)
 237         }
 238     }
 239 }
 240
 241 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 242 impl<T, const N: usize> Iterator for IntoIter<T, N> {
 243     type Item = T;
 244     fn next(&mut self) -> Option<Self::Item> {
 245         // Get the next index from the front.
 246         //
 247         // Increasing `alive.start` by 1 maintains the invariant regarding
 248         // `alive`. However, due to this change, for a short time, the alive
 249         // zone is not `data[alive]` anymore, but `data[idx..alive.end]`.
 250         self.alive.next().map(|idx| {
 251             // Read the element from the array.
 252             // SAFETY: `idx` is an index into the former "alive" region of the
 253             // array. Reading this element means that `data[idx]` is regarded as
 254             // dead now (i.e. do not touch). As `idx` was the start of the
 255             // alive-zone, the alive zone is now `data[alive]` again, restoring
 256             // all invariants.
 257             unsafe { self.data.get_unchecked(idx).assume_init_read() }
 258         })
 259     }
 260
 261     fn size_hint(&self) -> (usize, Option<usize>) {
 262         let len = self.len();
 263         (len, Some(len))
 264     }
 265
 266     #[inline]
 267     fn fold<Acc, Fold>(mut self, init: Acc, mut fold: Fold) -> Acc
 268     where
 269         Fold: FnMut(Acc, Self::Item) -> Acc,
 270     {
 271         let data = &mut self.data;
 272         iter::ByRefSized(&mut self.alive).fold(init, |acc, idx| {
 273             // SAFETY: idx is obtained by folding over the `alive` range, which implies the
 274             // value is currently considered alive but as the range is being consumed each value
 275             // we read here will only be read once and then considered dead.
 276             fold(acc, unsafe { data.get_unchecked(idx).assume_init_read() })
 277         })
 278     }
 279
 280     fn count(self) -> usize {
 281         self.len()
 282     }
 283
 284     fn last(mut self) -> Option<Self::Item> {
 285         self.next_back()
 286     }
 287
 288     fn advance_by(&mut self, n: usize) -> Result<(), usize> {
 289         let original_len = self.len();
 290
 291         // This also moves the start, which marks them as conceptually "dropped",
 292         // so if anything goes bad then our drop impl won't double-free them.
 293         let range_to_drop = self.alive.take_prefix(n);
 294
 295         // SAFETY: These elements are currently initialized, so it's fine to drop them.
 296         unsafe {
 297             let slice = self.data.get_unchecked_mut(range_to_drop);
 298             ptr::drop_in_place(MaybeUninit::slice_assume_init_mut(slice));
 299         }
 300
 301         if n > original_len { Err(original_len) } else { Ok(()) }
 302     }
 303 }
 304
 305 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 306 impl<T, const N: usize> DoubleEndedIterator for IntoIter<T, N> {
 307     fn next_back(&mut self) -> Option<Self::Item> {
 308         // Get the next index from the back.
 309         //
 310         // Decreasing `alive.end` by 1 maintains the invariant regarding
 311         // `alive`. However, due to this change, for a short time, the alive
 312         // zone is not `data[alive]` anymore, but `data[alive.start..=idx]`.
 313         self.alive.next_back().map(|idx| {
 314             // Read the element from the array.
 315             // SAFETY: `idx` is an index into the former "alive" region of the
 316             // array. Reading this element means that `data[idx]` is regarded as
 317             // dead now (i.e. do not touch). As `idx` was the end of the
 318             // alive-zone, the alive zone is now `data[alive]` again, restoring
 319             // all invariants.
 320             unsafe { self.data.get_unchecked(idx).assume_init_read() }
 321         })
 322     }
 323
 324     #[inline]
 325     fn rfold<Acc, Fold>(mut self, init: Acc, mut rfold: Fold) -> Acc
 326     where
 327         Fold: FnMut(Acc, Self::Item) -> Acc,
 328     {
 329         let data = &mut self.data;
 330         iter::ByRefSized(&mut self.alive).rfold(init, |acc, idx| {
 331             // SAFETY: idx is obtained by folding over the `alive` range, which implies the
 332             // value is currently considered alive but as the range is being consumed each value
 333             // we read here will only be read once and then considered dead.
 334             rfold(acc, unsafe { data.get_unchecked(idx).assume_init_read() })
 335         })
 336     }
 337
 338     fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
 339         let original_len = self.len();
 340
 341         // This also moves the end, which marks them as conceptually "dropped",
 342         // so if anything goes bad then our drop impl won't double-free them.
 343         let range_to_drop = self.alive.take_suffix(n);
 344
 345         // SAFETY: These elements are currently initialized, so it's fine to drop them.
 346         unsafe {
 347             let slice = self.data.get_unchecked_mut(range_to_drop);
 348             ptr::drop_in_place(MaybeUninit::slice_assume_init_mut(slice));
 349         }
 350
 351         if n > original_len { Err(original_len) } else { Ok(()) }
 352     }
 353 }
 354
 355 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 356 impl<T, const N: usize> Drop for IntoIter<T, N> {
 357     fn drop(&mut self) {
 358         // SAFETY: This is safe: `as_mut_slice` returns exactly the sub-slice
 359         // of elements that have not been moved out yet and that remain
 360         // to be dropped.
 361         unsafe { ptr::drop_in_place(self.as_mut_slice()) }
 362     }
 363 }
 364
 365 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 366 impl<T, const N: usize> ExactSizeIterator for IntoIter<T, N> {
 367     fn len(&self) -> usize {
 368         self.alive.len()
 369     }
 370     fn is_empty(&self) -> bool {
 371         self.alive.is_empty()
 372     }
 373 }
 374
 375 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 376 impl<T, const N: usize> FusedIterator for IntoIter<T, N> {}
 377
 378 // The iterator indeed reports the correct length. The number of "alive"
 379 // elements (that will still be yielded) is the length of the range `alive`.
 380 // This range is decremented in length in either `next` or `next_back`. It is
 381 // always decremented by 1 in those methods, but only if `Some(_)` is returned.
 382 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 383 unsafe impl<T, const N: usize> TrustedLen for IntoIter<T, N> {}
 384
 385 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 386 impl<T: Clone, const N: usize> Clone for IntoIter<T, N> {
 387     fn clone(&self) -> Self {
 388         // Note, we don't really need to match the exact same alive range, so
 389         // we can just clone into offset 0 regardless of where `self` is.
 390         let mut new = Self { data: MaybeUninit::uninit_array(), alive: IndexRange::zero_to(0) };
 391
 392         // Clone all alive elements.
 393         for (src, dst) in iter::zip(self.as_slice(), &mut new.data) {
 394             // Write a clone into the new array, then update its alive range.
 395             // If cloning panics, we'll correctly drop the previous items.
 396             dst.write(src.clone());
 397             // This addition cannot overflow as we're iterating a slice
 398             new.alive = IndexRange::zero_to(new.alive.end() + 1);
 399         }
 400
 401         new
 402     }
 403 }
 404
 405 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
 406 impl<T: fmt::Debug, const N: usize> fmt::Debug for IntoIter<T, N> {
 407     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 408         // Only print the elements that were not yielded yet: we cannot
 409         // access the yielded elements anymore.
 410         f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
 411     }
 412 }