1 | //! Defines the `IntoIter` owned iterator for arrays. |
2 | |
3 | use crate::num::NonZero; |
4 | use 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" ] |
17 | pub 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" )] |
45 | impl<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 | |
76 | impl<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" )] |
237 | impl<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<(), NonZero<usize>> { |
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 | NonZero::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" )] |
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<(), NonZero<usize>> { |
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 | NonZero::new(remaining).map_or(Ok(()), Err) |
351 | } |
352 | } |
353 | |
354 | #[stable (feature = "array_value_iter_impls" , since = "1.40.0" )] |
355 | impl<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" )] |
365 | impl<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" )] |
375 | impl<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" )] |
382 | unsafe 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 ] |
387 | pub 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" )] |
392 | impl<T: Copy> NonDrop for T {} |
393 | |
394 | #[doc (hidden)] |
395 | #[unstable (issue = "none" , feature = "std_internals" )] |
396 | unsafe impl<T, const N: usize> TrustedRandomAccessNoCoerce for IntoIter<T, N> |
397 | where |
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" )] |
404 | impl<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" )] |
424 | impl<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 | |