]>
Commit | Line | Data |
---|---|---|
3dfed10e XL |
1 | //! Defines the `IntoIter` owned iterator for arrays. |
2 | ||
3 | use crate::{ | |
4 | fmt, | |
5 | iter::{ExactSizeIterator, FusedIterator, TrustedLen}, | |
6 | mem::{self, MaybeUninit}, | |
7 | ops::Range, | |
8 | ptr, | |
9 | }; | |
10 | ||
11 | /// A by-value [array] iterator. | |
5869c6ff | 12 | #[stable(feature = "array_value_iter", since = "1.51.0")] |
3dfed10e XL |
13 | pub struct IntoIter<T, const N: usize> { |
14 | /// This is the array we are iterating over. | |
15 | /// | |
16 | /// Elements with index `i` where `alive.start <= i < alive.end` have not | |
17 | /// been yielded yet and are valid array entries. Elements with indices `i | |
18 | /// < alive.start` or `i >= alive.end` have been yielded already and must | |
19 | /// not be accessed anymore! Those dead elements might even be in a | |
20 | /// completely uninitialized state! | |
21 | /// | |
22 | /// So the invariants are: | |
23 | /// - `data[alive]` is alive (i.e. contains valid elements) | |
24 | /// - `data[..alive.start]` and `data[alive.end..]` are dead (i.e. the | |
25 | /// elements were already read and must not be touched anymore!) | |
26 | data: [MaybeUninit<T>; N], | |
27 | ||
28 | /// The elements in `data` that have not been yielded yet. | |
29 | /// | |
30 | /// Invariants: | |
31 | /// - `alive.start <= alive.end` | |
32 | /// - `alive.end <= N` | |
33 | alive: Range<usize>, | |
34 | } | |
35 | ||
36 | impl<T, const N: usize> IntoIter<T, N> { | |
37 | /// Creates a new iterator over the given `array`. | |
38 | /// | |
5869c6ff XL |
39 | /// *Note*: this method might be deprecated in the future, |
40 | /// after [`IntoIterator` is implemented for arrays][array-into-iter]. | |
41 | /// | |
42 | /// # Examples | |
43 | /// | |
44 | /// ``` | |
45 | /// use std::array; | |
46 | /// | |
47 | /// for value in array::IntoIter::new([1, 2, 3, 4, 5]) { | |
48 | /// // The type of `value` is a `i32` here, instead of `&i32` | |
49 | /// let _: i32 = value; | |
50 | /// } | |
51 | /// ``` | |
52 | /// [array-into-iter]: https://github.com/rust-lang/rust/pull/65819 | |
53 | #[stable(feature = "array_value_iter", since = "1.51.0")] | |
3dfed10e XL |
54 | pub fn new(array: [T; N]) -> Self { |
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 = Self { data: mem::transmute_copy(&array), alive: 0..N }; | |
74 | mem::forget(array); | |
75 | iter | |
76 | } | |
77 | } | |
78 | ||
79 | /// Returns an immutable slice of all elements that have not been yielded | |
80 | /// yet. | |
5869c6ff | 81 | #[stable(feature = "array_value_iter", since = "1.51.0")] |
fc512014 | 82 | pub fn as_slice(&self) -> &[T] { |
3dfed10e XL |
83 | // SAFETY: We know that all elements within `alive` are properly initialized. |
84 | unsafe { | |
85 | let slice = self.data.get_unchecked(self.alive.clone()); | |
1b1a35ee | 86 | MaybeUninit::slice_assume_init_ref(slice) |
3dfed10e XL |
87 | } |
88 | } | |
89 | ||
90 | /// Returns a mutable slice of all elements that have not been yielded yet. | |
5869c6ff | 91 | #[stable(feature = "array_value_iter", since = "1.51.0")] |
fc512014 | 92 | pub fn as_mut_slice(&mut self) -> &mut [T] { |
3dfed10e XL |
93 | // SAFETY: We know that all elements within `alive` are properly initialized. |
94 | unsafe { | |
95 | let slice = self.data.get_unchecked_mut(self.alive.clone()); | |
1b1a35ee | 96 | MaybeUninit::slice_assume_init_mut(slice) |
3dfed10e XL |
97 | } |
98 | } | |
99 | } | |
100 | ||
101 | #[stable(feature = "array_value_iter_impls", since = "1.40.0")] | |
102 | impl<T, const N: usize> Iterator for IntoIter<T, N> { | |
103 | type Item = T; | |
104 | fn next(&mut self) -> Option<Self::Item> { | |
105 | // Get the next index from the front. | |
106 | // | |
107 | // Increasing `alive.start` by 1 maintains the invariant regarding | |
108 | // `alive`. However, due to this change, for a short time, the alive | |
109 | // zone is not `data[alive]` anymore, but `data[idx..alive.end]`. | |
110 | self.alive.next().map(|idx| { | |
111 | // Read the element from the array. | |
112 | // SAFETY: `idx` is an index into the former "alive" region of the | |
113 | // array. Reading this element means that `data[idx]` is regarded as | |
114 | // dead now (i.e. do not touch). As `idx` was the start of the | |
115 | // alive-zone, the alive zone is now `data[alive]` again, restoring | |
116 | // all invariants. | |
1b1a35ee | 117 | unsafe { self.data.get_unchecked(idx).assume_init_read() } |
3dfed10e XL |
118 | }) |
119 | } | |
120 | ||
121 | fn size_hint(&self) -> (usize, Option<usize>) { | |
122 | let len = self.len(); | |
123 | (len, Some(len)) | |
124 | } | |
125 | ||
126 | fn count(self) -> usize { | |
127 | self.len() | |
128 | } | |
129 | ||
130 | fn last(mut self) -> Option<Self::Item> { | |
131 | self.next_back() | |
132 | } | |
133 | } | |
134 | ||
135 | #[stable(feature = "array_value_iter_impls", since = "1.40.0")] | |
136 | impl<T, const N: usize> DoubleEndedIterator for IntoIter<T, N> { | |
137 | fn next_back(&mut self) -> Option<Self::Item> { | |
138 | // Get the next index from the back. | |
139 | // | |
140 | // Decreasing `alive.end` by 1 maintains the invariant regarding | |
141 | // `alive`. However, due to this change, for a short time, the alive | |
142 | // zone is not `data[alive]` anymore, but `data[alive.start..=idx]`. | |
143 | self.alive.next_back().map(|idx| { | |
144 | // Read the element from the array. | |
145 | // SAFETY: `idx` is an index into the former "alive" region of the | |
146 | // array. Reading this element means that `data[idx]` is regarded as | |
147 | // dead now (i.e. do not touch). As `idx` was the end of the | |
148 | // alive-zone, the alive zone is now `data[alive]` again, restoring | |
149 | // all invariants. | |
1b1a35ee | 150 | unsafe { self.data.get_unchecked(idx).assume_init_read() } |
3dfed10e XL |
151 | }) |
152 | } | |
153 | } | |
154 | ||
155 | #[stable(feature = "array_value_iter_impls", since = "1.40.0")] | |
156 | impl<T, const N: usize> Drop for IntoIter<T, N> { | |
157 | fn drop(&mut self) { | |
158 | // SAFETY: This is safe: `as_mut_slice` returns exactly the sub-slice | |
159 | // of elements that have not been moved out yet and that remain | |
160 | // to be dropped. | |
161 | unsafe { ptr::drop_in_place(self.as_mut_slice()) } | |
162 | } | |
163 | } | |
164 | ||
165 | #[stable(feature = "array_value_iter_impls", since = "1.40.0")] | |
166 | impl<T, const N: usize> ExactSizeIterator for IntoIter<T, N> { | |
167 | fn len(&self) -> usize { | |
168 | // Will never underflow due to the invariant `alive.start <= | |
169 | // alive.end`. | |
170 | self.alive.end - self.alive.start | |
171 | } | |
172 | fn is_empty(&self) -> bool { | |
173 | self.alive.is_empty() | |
174 | } | |
175 | } | |
176 | ||
177 | #[stable(feature = "array_value_iter_impls", since = "1.40.0")] | |
178 | impl<T, const N: usize> FusedIterator for IntoIter<T, N> {} | |
179 | ||
180 | // The iterator indeed reports the correct length. The number of "alive" | |
181 | // elements (that will still be yielded) is the length of the range `alive`. | |
182 | // This range is decremented in length in either `next` or `next_back`. It is | |
183 | // always decremented by 1 in those methods, but only if `Some(_)` is returned. | |
184 | #[stable(feature = "array_value_iter_impls", since = "1.40.0")] | |
185 | unsafe impl<T, const N: usize> TrustedLen for IntoIter<T, N> {} | |
186 | ||
187 | #[stable(feature = "array_value_iter_impls", since = "1.40.0")] | |
188 | impl<T: Clone, const N: usize> Clone for IntoIter<T, N> { | |
189 | fn clone(&self) -> Self { | |
190 | // Note, we don't really need to match the exact same alive range, so | |
191 | // we can just clone into offset 0 regardless of where `self` is. | |
192 | let mut new = Self { data: MaybeUninit::uninit_array(), alive: 0..0 }; | |
193 | ||
194 | // Clone all alive elements. | |
195 | for (src, dst) in self.as_slice().iter().zip(&mut new.data) { | |
196 | // Write a clone into the new array, then update its alive range. | |
197 | // If cloning panics, we'll correctly drop the previous items. | |
198 | dst.write(src.clone()); | |
199 | new.alive.end += 1; | |
200 | } | |
201 | ||
202 | new | |
203 | } | |
204 | } | |
205 | ||
206 | #[stable(feature = "array_value_iter_impls", since = "1.40.0")] | |
207 | impl<T: fmt::Debug, const N: usize> fmt::Debug for IntoIter<T, N> { | |
208 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { | |
209 | // Only print the elements that were not yielded yet: we cannot | |
210 | // access the yielded elements anymore. | |
211 | f.debug_tuple("IntoIter").field(&self.as_slice()).finish() | |
212 | } | |
213 | } |