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