1 //! Defines the `IntoIter` owned iterator for arrays.
5 iter::{self, ExactSizeIterator, FusedIterator, TrustedLen},
6 mem::{self, MaybeUninit},
7 ops::{IndexRange, Range},
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.
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!
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],
29 /// The elements in `data` that have not been yielded yet.
32 /// - `alive.end <= N`
34 /// (And the `IndexRange` type requires `alive.start <= alive.end`.)
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] {
44 type IntoIter = IntoIter<T, N>;
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.
50 /// Arrays have special behavior when calling `.into_iter()` prior to the
51 /// 2021 edition -- see the [array] Editions section for more information.
53 /// [array]: prim@array
54 fn into_iter(self) -> Self::IntoIter {
55 // SAFETY: The transmute here is actually safe. The docs of `MaybeUninit`
58 // > `MaybeUninit<T>` is guaranteed to have the same size and alignment
61 // The docs even show a transmute from an array of `MaybeUninit<T>` to
64 // With that, this initialization satisfies the invariants.
66 // FIXME(LukasKalbertodt): actually use `mem::transmute` here, once it
67 // works with const generics:
68 // `mem::transmute::<[T; N], [MaybeUninit<T>; N]>(array)`
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.
73 let iter = IntoIter { data: mem::transmute_copy(&self), alive: IndexRange::zero_to(N) };
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)
88 /// Creates an iterator over the elements in a partially-initialized buffer.
90 /// If you have a fully-initialized array, then use [`IntoIterator`].
91 /// But this is useful for returning partial results from unsafe code.
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.)
100 /// It's sound to have more elements initialized than mentioned, though that
101 /// will most likely result in them being leaked.
106 /// #![feature(array_into_iter_constructors)]
107 /// #![feature(maybe_uninit_uninit_array_transpose)]
108 /// #![feature(maybe_uninit_uninit_array)]
109 /// use std::array::IntoIter;
110 /// use std::mem::MaybeUninit;
112 /// # // Hi! Thanks for reading the code. This is restricted to `Copy` because
113 /// # // otherwise it could leak. A fully-general version this would need a drop
114 /// # // guard to handle panics from the iterator, but this works for an example.
115 /// fn next_chunk<T: Copy, const N: usize>(
116 /// it: &mut impl Iterator<Item = T>,
117 /// ) -> Result<[T; N], IntoIter<T, N>> {
118 /// let mut buffer = MaybeUninit::uninit_array();
121 /// match it.next() {
123 /// buffer[i].write(x);
127 /// // SAFETY: We've initialized the first `i` items
129 /// return Err(IntoIter::new_unchecked(buffer, 0..i));
135 /// // SAFETY: We've initialized all N items
136 /// unsafe { Ok(buffer.transpose().assume_init()) }
139 /// let r: [_; 4] = next_chunk(&mut (10..16)).unwrap();
140 /// assert_eq!(r, [10, 11, 12, 13]);
141 /// let r: IntoIter<_, 40> = next_chunk(&mut (10..16)).unwrap_err();
142 /// assert_eq!(r.collect::<Vec<_>>(), vec![10, 11, 12, 13, 14, 15]);
144 #[unstable(feature = "array_into_iter_constructors", issue = "91583")]
145 #[rustc_const_unstable(feature = "const_array_into_iter_constructors", issue = "91583")]
146 pub const unsafe fn new_unchecked(
147 buffer: [MaybeUninit<T>; N],
148 initialized: Range<usize>,
150 // SAFETY: one of our safety conditions is that the range is canonical.
151 let alive = unsafe { IndexRange::new_unchecked(initialized.start, initialized.end) };
152 Self { data: buffer, alive }
155 /// Creates an iterator over `T` which returns no elements.
157 /// If you just need an empty iterator, then use
158 /// [`iter::empty()`](crate::iter::empty) instead.
159 /// And if you need an empty array, use `[]`.
161 /// But this is useful when you need an `array::IntoIter<T, N>` *specifically*.
166 /// #![feature(array_into_iter_constructors)]
167 /// use std::array::IntoIter;
169 /// let empty = IntoIter::<i32, 3>::empty();
170 /// assert_eq!(empty.len(), 0);
171 /// assert_eq!(empty.as_slice(), &[]);
173 /// let empty = IntoIter::<std::convert::Infallible, 200>::empty();
174 /// assert_eq!(empty.len(), 0);
177 /// `[1, 2].into_iter()` and `[].into_iter()` have different types
178 /// ```should_fail,edition2021
179 /// #![feature(array_into_iter_constructors)]
180 /// use std::array::IntoIter;
182 /// pub fn get_bytes(b: bool) -> IntoIter<i8, 4> {
184 /// [1, 2, 3, 4].into_iter()
186 /// [].into_iter() // error[E0308]: mismatched types
191 /// But using this method you can get an empty iterator of appropriate size:
193 /// #![feature(array_into_iter_constructors)]
194 /// use std::array::IntoIter;
196 /// pub fn get_bytes(b: bool) -> IntoIter<i8, 4> {
198 /// [1, 2, 3, 4].into_iter()
200 /// IntoIter::empty()
204 /// assert_eq!(get_bytes(true).collect::<Vec<_>>(), vec![1, 2, 3, 4]);
205 /// assert_eq!(get_bytes(false).collect::<Vec<_>>(), vec![]);
207 #[unstable(feature = "array_into_iter_constructors", issue = "91583")]
208 #[rustc_const_unstable(feature = "const_array_into_iter_constructors", issue = "91583")]
209 pub const fn empty() -> Self {
210 let buffer = MaybeUninit::uninit_array();
211 let initialized = 0..0;
213 // SAFETY: We're telling it that none of the elements are initialized,
214 // which is trivially true. And ∀N: usize, 0 <= N.
215 unsafe { Self::new_unchecked(buffer, initialized) }
218 /// Returns an immutable slice of all elements that have not been yielded
220 #[stable(feature = "array_value_iter", since = "1.51.0")]
221 pub fn as_slice(&self) -> &[T] {
222 // SAFETY: We know that all elements within `alive` are properly initialized.
224 let slice = self.data.get_unchecked(self.alive.clone());
225 MaybeUninit::slice_assume_init_ref(slice)
229 /// Returns a mutable slice of all elements that have not been yielded yet.
230 #[stable(feature = "array_value_iter", since = "1.51.0")]
231 pub fn as_mut_slice(&mut self) -> &mut [T] {
232 // SAFETY: We know that all elements within `alive` are properly initialized.
234 let slice = self.data.get_unchecked_mut(self.alive.clone());
235 MaybeUninit::slice_assume_init_mut(slice)
240 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
241 impl<T, const N: usize> Iterator for IntoIter<T, N> {
243 fn next(&mut self) -> Option<Self::Item> {
244 // Get the next index from the front.
246 // Increasing `alive.start` by 1 maintains the invariant regarding
247 // `alive`. However, due to this change, for a short time, the alive
248 // zone is not `data[alive]` anymore, but `data[idx..alive.end]`.
249 self.alive.next().map(|idx| {
250 // Read the element from the array.
251 // SAFETY: `idx` is an index into the former "alive" region of the
252 // array. Reading this element means that `data[idx]` is regarded as
253 // dead now (i.e. do not touch). As `idx` was the start of the
254 // alive-zone, the alive zone is now `data[alive]` again, restoring
256 unsafe { self.data.get_unchecked(idx).assume_init_read() }
260 fn size_hint(&self) -> (usize, Option<usize>) {
261 let len = self.len();
266 fn fold<Acc, Fold>(mut self, init: Acc, mut fold: Fold) -> Acc
268 Fold: FnMut(Acc, Self::Item) -> Acc,
270 let data = &mut self.data;
271 iter::ByRefSized(&mut self.alive).fold(init, |acc, idx| {
272 // SAFETY: idx is obtained by folding over the `alive` range, which implies the
273 // value is currently considered alive but as the range is being consumed each value
274 // we read here will only be read once and then considered dead.
275 fold(acc, unsafe { data.get_unchecked(idx).assume_init_read() })
279 fn count(self) -> usize {
283 fn last(mut self) -> Option<Self::Item> {
287 fn advance_by(&mut self, n: usize) -> Result<(), usize> {
288 let original_len = self.len();
290 // This also moves the start, which marks them as conceptually "dropped",
291 // so if anything goes bad then our drop impl won't double-free them.
292 let range_to_drop = self.alive.take_prefix(n);
294 // SAFETY: These elements are currently initialized, so it's fine to drop them.
296 let slice = self.data.get_unchecked_mut(range_to_drop);
297 ptr::drop_in_place(MaybeUninit::slice_assume_init_mut(slice));
300 if n > original_len { Err(original_len) } else { Ok(()) }
304 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
305 impl<T, const N: usize> DoubleEndedIterator for IntoIter<T, N> {
306 fn next_back(&mut self) -> Option<Self::Item> {
307 // Get the next index from the back.
309 // Decreasing `alive.end` by 1 maintains the invariant regarding
310 // `alive`. However, due to this change, for a short time, the alive
311 // zone is not `data[alive]` anymore, but `data[alive.start..=idx]`.
312 self.alive.next_back().map(|idx| {
313 // Read the element from the array.
314 // SAFETY: `idx` is an index into the former "alive" region of the
315 // array. Reading this element means that `data[idx]` is regarded as
316 // dead now (i.e. do not touch). As `idx` was the end of the
317 // alive-zone, the alive zone is now `data[alive]` again, restoring
319 unsafe { self.data.get_unchecked(idx).assume_init_read() }
324 fn rfold<Acc, Fold>(mut self, init: Acc, mut rfold: Fold) -> Acc
326 Fold: FnMut(Acc, Self::Item) -> Acc,
328 let data = &mut self.data;
329 iter::ByRefSized(&mut self.alive).rfold(init, |acc, idx| {
330 // SAFETY: idx is obtained by folding over the `alive` range, which implies the
331 // value is currently considered alive but as the range is being consumed each value
332 // we read here will only be read once and then considered dead.
333 rfold(acc, unsafe { data.get_unchecked(idx).assume_init_read() })
337 fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
338 let original_len = self.len();
340 // This also moves the end, which marks them as conceptually "dropped",
341 // so if anything goes bad then our drop impl won't double-free them.
342 let range_to_drop = self.alive.take_suffix(n);
344 // SAFETY: These elements are currently initialized, so it's fine to drop them.
346 let slice = self.data.get_unchecked_mut(range_to_drop);
347 ptr::drop_in_place(MaybeUninit::slice_assume_init_mut(slice));
350 if n > original_len { Err(original_len) } else { Ok(()) }
354 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
355 impl<T, const N: usize> Drop for IntoIter<T, N> {
357 // SAFETY: This is safe: `as_mut_slice` returns exactly the sub-slice
358 // of elements that have not been moved out yet and that remain
360 unsafe { ptr::drop_in_place(self.as_mut_slice()) }
364 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
365 impl<T, const N: usize> ExactSizeIterator for IntoIter<T, N> {
366 fn len(&self) -> usize {
369 fn is_empty(&self) -> bool {
370 self.alive.is_empty()
374 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
375 impl<T, const N: usize> FusedIterator for IntoIter<T, N> {}
377 // The iterator indeed reports the correct length. The number of "alive"
378 // elements (that will still be yielded) is the length of the range `alive`.
379 // This range is decremented in length in either `next` or `next_back`. It is
380 // always decremented by 1 in those methods, but only if `Some(_)` is returned.
381 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
382 unsafe impl<T, const N: usize> TrustedLen for IntoIter<T, N> {}
384 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
385 impl<T: Clone, const N: usize> Clone for IntoIter<T, N> {
386 fn clone(&self) -> Self {
387 // Note, we don't really need to match the exact same alive range, so
388 // we can just clone into offset 0 regardless of where `self` is.
389 let mut new = Self { data: MaybeUninit::uninit_array(), alive: IndexRange::zero_to(0) };
391 // Clone all alive elements.
392 for (src, dst) in iter::zip(self.as_slice(), &mut new.data) {
393 // Write a clone into the new array, then update its alive range.
394 // If cloning panics, we'll correctly drop the previous items.
395 dst.write(src.clone());
396 // This addition cannot overflow as we're iterating a slice
397 new.alive = IndexRange::zero_to(new.alive.end() + 1);
404 #[stable(feature = "array_value_iter_impls", since = "1.40.0")]
405 impl<T: fmt::Debug, const N: usize> fmt::Debug for IntoIter<T, N> {
406 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
407 // Only print the elements that were not yielded yet: we cannot
408 // access the yielded elements anymore.
409 f.debug_tuple("IntoIter").field(&self.as_slice()).finish()