//! 为数组定义 `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()
    }
}