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