1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404
//! 为数组定义 `IntoIter` 拥有的迭代器。
use crate::num::NonZeroUsize;
use crate::{
fmt,
intrinsics::transmute_unchecked,
iter::{self, ExactSizeIterator, FusedIterator, TrustedLen},
mem::MaybeUninit,
ops::{IndexRange, Range},
ptr,
};
/// 一个按值的 [array] 迭代器。
#[stable(feature = "array_value_iter", since = "1.51.0")]
#[rustc_insignificant_dtor]
pub struct IntoIter<T, const N: usize> {
/// 这是我们要遍历的数组。
///
/// 索引为 `i` 的元素 (尚未生成 `alive.start <= i < alive.end`) 是有效的数组条目。
/// 索引为 `i < alive.start` 或 `i >= alive.end` 的元素已经产生,不能再访问了! 那些死元素甚至可能处于完全未初始化的状态!
///
///
/// 因此,不变量是:
/// - `data[alive]` 是活动的 (即包含有效元素)
/// - `data[..alive.start]` 和 `data[alive.end..]` 已经失效 (即元素已被读取,不能再被触碰!)
///
///
///
data: [MaybeUninit<T>; N],
/// `data` 中尚未产生的元素。
///
/// Invariants:
/// - `alive.end <= N`
///
/// (并且 `IndexRange` 类型需要 `alive.start <= alive.end`。)
alive: IndexRange,
}
// Note: `trait IntoIterator` 上的 `#[rustc_skip_array_during_method_dispatch]` 对小于 2021 的版本显式 `.into_iter()` 调用隐藏了此实现,因此这些调用仍将通过引用解析为 slice 实现。
//
//
#[stable(feature = "array_into_iter_impl", since = "1.53.0")]
impl<T, const N: usize> IntoIterator for [T; N] {
type Item = T;
type IntoIter = IntoIter<T, N>;
/// 创建一个消费迭代器,即将每个值移出数组 (从开始到结束)。
/// 除非 `T` 实现了 `Copy`,否则调用此数组后不能使用数组,因此整个数组都会被复制。
///
///
/// 在调用 `.into_iter()` 之前,数组具有特殊行为
/// 2021 版 -- 有关更多信息,请参见 [array] 版本部分。
///
/// [array]: prim@array
fn into_iter(self) -> Self::IntoIter {
// SAFETY: 此处的转换实际上是安全的。`MaybeUninit` promise 的文档:
//
// > `MaybeUninit<T>` 保证具有相同的大小和对齐方式
// > 作为 `T`。
//
// 该文档甚至显示了从 `MaybeUninit<T>` 数组到 `T` 数组的转换。
//
// 这样,该初始化就满足了不变性。
//
// FIXME: 如果普通 `transmute` 变得足够聪明,可以直接允许这样做,请使用它而不是 `transmute_unchecked`。
//
//
//
let data: [MaybeUninit<T>; N] = unsafe { transmute_unchecked(self) };
IntoIter { data, alive: IndexRange::zero_to(N) }
}
}
impl<T, const N: usize> IntoIter<T, N> {
/// 在给定的 `array` 上创建一个新的迭代器。
#[stable(feature = "array_value_iter", since = "1.51.0")]
#[deprecated(since = "1.59.0", note = "use `IntoIterator::into_iter` instead")]
pub fn new(array: [T; N]) -> Self {
IntoIterator::into_iter(array)
}
/// 在部分初始化的缓冲区中的元素上创建迭代器。
///
/// 如果您有一个完全初始化的数组,则使用 [`IntoIterator`]。
/// 但这对于从不安全代码中返回部分结果很有用。
///
/// # Safety
///
/// - `buffer[initialized]` 元素必须全部初始化。
/// - 范围必须是规范的,并带有 `initialized.start <= initialized.end`。
/// - 该范围必须在缓冲区的界限内,同时 `initialized.end <= N`。
/// (就像索引 `[0][100..100]` 失败一样,尽管范围为空。)
///
/// 初始化的元素比提到的多是合理的,尽管这很可能会导致它们被泄露。
///
///
/// # Examples
///
/// ```
/// #![feature(array_into_iter_constructors)]
/// #![feature(maybe_uninit_uninit_array_transpose)]
/// #![feature(maybe_uninit_uninit_array)]
/// use std::array::IntoIter;
/// use std::mem::MaybeUninit;
///
/// # // 您好!感谢您阅读代码。这仅限于 `Copy`,因为
/// # // 否则可能会泄漏。一个完全通用的版本,这需要一个丢弃
/// # // 守卫处理来自迭代器的 panics,但这仅适用于示例。
/// fn next_chunk<T: Copy, const N: usize>(
/// it: &mut impl Iterator<Item = T>,
/// ) -> Result<[T; N], IntoIter<T, N>> {
/// let mut buffer = MaybeUninit::uninit_array();
/// let mut i = 0;
/// while i < N {
/// match it.next() {
/// Some(x) => {
/// buffer[i].write(x);
/// i += 1;
/// }
/// None => {
/// // SAFETY: 我们已经初始化了第一个 `i` 项
/// unsafe {
/// return Err(IntoIter::new_unchecked(buffer, 0..i));
/// }
/// }
/// }
/// }
///
/// // SAFETY: 我们已经初始化了所有 N 项
/// unsafe { Ok(buffer.transpose().assume_init()) }
/// }
///
/// let r: [_; 4] = next_chunk(&mut (10..16)).unwrap();
/// assert_eq!(r, [10, 11, 12, 13]);
/// let r: IntoIter<_, 40> = next_chunk(&mut (10..16)).unwrap_err();
/// assert_eq!(r.collect::<Vec<_>>(), vec![10, 11, 12, 13, 14, 15]);
/// ```
#[unstable(feature = "array_into_iter_constructors", issue = "91583")]
#[rustc_const_unstable(feature = "const_array_into_iter_constructors", issue = "91583")]
pub const unsafe fn new_unchecked(
buffer: [MaybeUninit<T>; N],
initialized: Range<usize>,
) -> Self {
// SAFETY: 我们的安全条件之一是范围是规范的。
let alive = unsafe { IndexRange::new_unchecked(initialized.start, initialized.end) };
Self { data: buffer, alive }
}
/// 在 `T` 上创建一个迭代器,该迭代器不返回任何元素。
/// 如果您只需要一个空的迭代器,请使用 [`iter::empty()`](crate::iter::empty)。
/// 如果您需要一个空数组,请使用 `[]`。
///
/// 但是当您需要 `array::IntoIter<T, N>` 时,这非常有用。
///
/// # Examples
///
/// ```
/// #![feature(array_into_iter_constructors)]
/// use std::array::IntoIter;
///
/// let empty = IntoIter::<i32, 3>::empty();
/// assert_eq!(empty.len(), 0);
/// assert_eq!(empty.as_slice(), &[]);
///
/// let empty = IntoIter::<std::convert::Infallible, 200>::empty();
/// assert_eq!(empty.len(), 0);
/// ```
///
/// `[1, 2].into_iter()` 和 `[].into_iter()` 有不同的类型
///
/// ```should_fail,edition2021
/// #![feature(array_into_iter_constructors)]
/// use std::array::IntoIter;
///
/// pub fn get_bytes(b: bool) -> IntoIter<i8, 4> {
/// if b {
/// [1, 2, 3, 4].into_iter()
/// } else {
/// [].into_iter() // error[E0308]: 类型不匹配
/// }
/// }
/// ```
///
/// 但是,使用此方法您可以得到一个适当大小的空迭代器:
///
/// ```edition2021
/// #![feature(array_into_iter_constructors)]
/// use std::array::IntoIter;
///
/// pub fn get_bytes(b: bool) -> IntoIter<i8, 4> {
/// if b {
/// [1, 2, 3, 4].into_iter()
/// } else {
/// IntoIter::empty()
/// }
/// }
///
/// assert_eq!(get_bytes(true).collect::<Vec<_>>(), vec![1, 2, 3, 4]);
/// assert_eq!(get_bytes(false).collect::<Vec<_>>(), vec![]);
/// ```
#[unstable(feature = "array_into_iter_constructors", issue = "91583")]
#[rustc_const_unstable(feature = "const_array_into_iter_constructors", issue = "91583")]
pub const fn empty() -> Self {
let buffer = MaybeUninit::uninit_array();
let initialized = 0..0;
// SAFETY: 我们告诉它,没有任何一个元素被初始化,这是非常正确的。
// And ∀N: usize, 0 <= N。
unsafe { Self::new_unchecked(buffer, initialized) }
}
/// 返回尚未产生的所有元素的不可变切片。
///
#[stable(feature = "array_value_iter", since = "1.51.0")]
pub fn as_slice(&self) -> &[T] {
// SAFETY: 我们知道 `alive` 中的所有元素都已正确初始化。
unsafe {
let slice = self.data.get_unchecked(self.alive.clone());
MaybeUninit::slice_assume_init_ref(slice)
}
}
/// 返回尚未生成的所有元素的可变切片。
#[stable(feature = "array_value_iter", since = "1.51.0")]
pub fn as_mut_slice(&mut self) -> &mut [T] {
// SAFETY: 我们知道 `alive` 中的所有元素都已正确初始化。
unsafe {
let slice = self.data.get_unchecked_mut(self.alive.clone());
MaybeUninit::slice_assume_init_mut(slice)
}
}
}
#[stable(feature = "array_value_iter_impls", since = "1.40.0")]
impl<T, const N: usize> Iterator for IntoIter<T, N> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
// 从前面获取下一个索引。
//
// `alive.start` 增加 1 将保持 `alive` 的不变性。
// 但是,由于此更改,在短时间内,活动区域不再是 `data[alive]`,而是 `data[idx..alive.end]`。
//
self.alive.next().map(|idx| {
// 从数组中读取元素。
// SAFETY: `idx` 是数组前 "alive" 区域的索引。
// 读取此元素意味着 `data[idx]` 现在被视为已失效 (即
// 请勿触摸)。
// 由于 `idx` 是活动区域的开始,因此活动区域现在又是 `data[alive]`,恢复了所有不变量。
//
unsafe { self.data.get_unchecked(idx).assume_init_read() }
})
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.len();
(len, Some(len))
}
#[inline]
fn fold<Acc, Fold>(mut self, init: Acc, mut fold: Fold) -> Acc
where
Fold: FnMut(Acc, Self::Item) -> Acc,
{
let data = &mut self.data;
iter::ByRefSized(&mut self.alive).fold(init, |acc, idx| {
// SAFETY: idx 是通过折叠 `alive` 范围获得的,这意味着该值当前被认为是活动的,但是随着范围被消耗,我们在这里读取的每个值只会被读取一次,然后被认为是死的。
//
//
fold(acc, unsafe { data.get_unchecked(idx).assume_init_read() })
})
}
fn count(self) -> usize {
self.len()
}
fn last(mut self) -> Option<Self::Item> {
self.next_back()
}
fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
// 这也移动了开始,将它们标记为 "dropped",因此如果出现任何问题,那么我们的丢弃 impl 不会过多释放它们。
//
let range_to_drop = self.alive.take_prefix(n);
let remaining = n - range_to_drop.len();
// SAFETY: 这些元素当前已初始化,因此可以将它们丢弃。
unsafe {
let slice = self.data.get_unchecked_mut(range_to_drop);
ptr::drop_in_place(MaybeUninit::slice_assume_init_mut(slice));
}
NonZeroUsize::new(remaining).map_or(Ok(()), Err)
}
}
#[stable(feature = "array_value_iter_impls", since = "1.40.0")]
impl<T, const N: usize> DoubleEndedIterator for IntoIter<T, N> {
fn next_back(&mut self) -> Option<Self::Item> {
// 从后面获取下一个索引。
//
// `alive.end` 减 1 保持 `alive` 不变。
// 但是,由于此更改,在短时间内,活动区域不再是 `data[alive]`,而是 `data[alive.start..=idx]`。
//
self.alive.next_back().map(|idx| {
// 从数组中读取元素。
// SAFETY: `idx` 是数组前 "alive" 区域的索引。
// 读取此元素意味着 `data[idx]` 现在被视为已失效 (即
// 请勿触摸)。
// 由于 `idx` 是活动区域的结尾,因此活动区域现在又是 `data[alive]`,还原了所有不变量。
//
unsafe { self.data.get_unchecked(idx).assume_init_read() }
})
}
#[inline]
fn rfold<Acc, Fold>(mut self, init: Acc, mut rfold: Fold) -> Acc
where
Fold: FnMut(Acc, Self::Item) -> Acc,
{
let data = &mut self.data;
iter::ByRefSized(&mut self.alive).rfold(init, |acc, idx| {
// SAFETY: idx 是通过折叠 `alive` 范围获得的,这意味着该值当前被认为是活动的,但是随着范围被消耗,我们在这里读取的每个值只会被读取一次,然后被认为是死的。
//
//
rfold(acc, unsafe { data.get_unchecked(idx).assume_init_read() })
})
}
fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
// 这也移动了结尾,这将它们标记为 "dropped",所以如果有任何事情变坏,那么我们的丢弃 impl 不会过度释放它们。
//
let range_to_drop = self.alive.take_suffix(n);
let remaining = n - range_to_drop.len();
// SAFETY: 这些元素当前已初始化,因此可以将它们丢弃。
unsafe {
let slice = self.data.get_unchecked_mut(range_to_drop);
ptr::drop_in_place(MaybeUninit::slice_assume_init_mut(slice));
}
NonZeroUsize::new(remaining).map_or(Ok(()), Err)
}
}
#[stable(feature = "array_value_iter_impls", since = "1.40.0")]
impl<T, const N: usize> Drop for IntoIter<T, N> {
fn drop(&mut self) {
// SAFETY: 这是安全的: `as_mut_slice` 精确地返回尚未移出但仍要丢弃的元素的子切片。
//
//
unsafe { ptr::drop_in_place(self.as_mut_slice()) }
}
}
#[stable(feature = "array_value_iter_impls", since = "1.40.0")]
impl<T, const N: usize> ExactSizeIterator for IntoIter<T, N> {
fn len(&self) -> usize {
self.alive.len()
}
fn is_empty(&self) -> bool {
self.alive.is_empty()
}
}
#[stable(feature = "array_value_iter_impls", since = "1.40.0")]
impl<T, const N: usize> FusedIterator for IntoIter<T, N> {}
// 迭代器确实报告了正确的长度。
// "alive" 元素的数量 (仍将产生) 是 `alive` 范围的长度。
// 在 `next` 或 `next_back` 中,此范围的长度减小。
// 在这些方法中,它总是减 1,但前提是要返回 `Some(_)`。
#[stable(feature = "array_value_iter_impls", since = "1.40.0")]
unsafe impl<T, const N: usize> TrustedLen for IntoIter<T, N> {}
#[stable(feature = "array_value_iter_impls", since = "1.40.0")]
impl<T: Clone, const N: usize> Clone for IntoIter<T, N> {
fn clone(&self) -> Self {
// 注意,我们实际上并不需要完全匹配相同的有效范围,因此无论 `self` 在哪里,我们都可以克隆到偏移量 0 中。
//
let mut new = Self { data: MaybeUninit::uninit_array(), alive: IndexRange::zero_to(0) };
// 克隆所有活动元素。
for (src, dst) in iter::zip(self.as_slice(), &mut new.data) {
// 将克隆写入新阵列,然后更新其有效范围。
// 如果克隆发生 panics,我们将正确丢弃前一个项。
dst.write(src.clone());
// 这个添加不会溢出,因为我们正在迭代一个切片
new.alive = IndexRange::zero_to(new.alive.end() + 1);
}
new
}
}
#[stable(feature = "array_value_iter_impls", since = "1.40.0")]
impl<T: fmt::Debug, const N: usize> fmt::Debug for IntoIter<T, N> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
// 只打印尚未产生的元素:我们不能再访问产生的元素。
//
f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
}
}