#[cfg(not(no_global_oom_handling))]
use super::AsVecIntoIter;
use crate::alloc::{Allocator, Global};
#[cfg(not(no_global_oom_handling))]
use crate::collections::VecDeque;
use crate::raw_vec::RawVec;
use core::array;
use core::fmt;
use core::iter::{
    FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccessNoCoerce,
};
use core::marker::PhantomData;
use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties};
use core::num::NonZeroUsize;
#[cfg(not(no_global_oom_handling))]
use core::ops::Deref;
use core::ptr::{self, NonNull};
use core::slice::{self};

/// 从 vector 移出的迭代器。
///
/// 该 `struct` 是通过 [`Vec`](super::Vec) (由 [`IntoIterator`] trait 提供) 上的 `into_iter` 方法创建的。
///
///
/// # Example
///
/// ```
/// let v = vec![0, 1, 2];
/// let iter: std::vec::IntoIter<_> = v.into_iter();
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
#[rustc_insignificant_dtor]
pub struct IntoIter<
    T,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> {
    pub(super) buf: NonNull<T>,
    pub(super) phantom: PhantomData<T>,
    pub(super) cap: usize,
    // drop impl 从 buf，cap 和 alloc 重建一个 RawVec，以避免两次丢弃分配器，我们需要将其包装到 ManuallyDrop 中
    //
    pub(super) alloc: ManuallyDrop<A>,
    pub(super) ptr: *const T,
    pub(super) end: *const T, // 如果 T 是 ZST，则实际上是 ptr + len。选择此编码，以便
                              // ptr == end 是对 Iterator 为空的快速测试，适用于 ZST 和非 ZST。
                              //
}

#[stable(feature = "vec_intoiter_debug", since = "1.13.0")]
impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
    }
}

impl<T, A: Allocator> IntoIter<T, A> {
    /// 返回此迭代器的其余项作为切片。
    ///
    /// # Examples
    ///
    /// ```
    /// let vec = vec!['a', 'b', 'c'];
    /// let mut into_iter = vec.into_iter();
    /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
    /// let _ = into_iter.next().unwrap();
    /// assert_eq!(into_iter.as_slice(), &['b', 'c']);
    /// ```
    #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
    pub fn as_slice(&self) -> &[T] {
        unsafe { slice::from_raw_parts(self.ptr, self.len()) }
    }

    /// 以可变切片的形式返回此迭代器的其余项。
    ///
    /// # Examples
    ///
    /// ```
    /// let vec = vec!['a', 'b', 'c'];
    /// let mut into_iter = vec.into_iter();
    /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
    /// into_iter.as_mut_slice()[2] = 'z';
    /// assert_eq!(into_iter.next().unwrap(), 'a');
    /// assert_eq!(into_iter.next().unwrap(), 'b');
    /// assert_eq!(into_iter.next().unwrap(), 'z');
    /// ```
    #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
    pub fn as_mut_slice(&mut self) -> &mut [T] {
        unsafe { &mut *self.as_raw_mut_slice() }
    }

    /// 返回底层分配器的引用。
    #[unstable(feature = "allocator_api", issue = "32838")]
    #[inline]
    pub fn allocator(&self) -> &A {
        &self.alloc
    }

    fn as_raw_mut_slice(&mut self) -> *mut [T] {
        ptr::slice_from_raw_parts_mut(self.ptr as *mut T, self.len())
    }

    /// 丢弃剩余的元素并放弃支持分配。
    /// 这种方法保证它在放弃支持分配之前不会 panic。
    ///
    /// 这大致等效于以下内容，但效率更高
    ///
    /// ```
    /// # let mut into_iter = Vec::<u8>::with_capacity(10).into_iter();
    /// let mut into_iter = std::mem::replace(&mut into_iter, Vec::new().into_iter());
    /// (&mut into_iter).for_each(drop);
    /// std::mem::forget(into_iter);
    /// ```
    ///
    /// 在就地迭代的时候会使用这个方法，请参见 vec::in_place_collect 文档以获取概述。
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    pub(super) fn forget_allocation_drop_remaining(&mut self) {
        let remaining = self.as_raw_mut_slice();

        // 覆盖各个字段，而不是创建一个新的结构体，然后覆盖 &mut self。
        //
        // 这将创建更少的部件
        self.cap = 0;
        self.buf = unsafe { NonNull::new_unchecked(RawVec::NEW.ptr()) };
        self.ptr = self.buf.as_ptr();
        self.end = self.buf.as_ptr();

        // 丢弃剩余的元素可能会发生 panic，因此仅在更新其他字段后才需要这样做。
        //
        unsafe {
            ptr::drop_in_place(remaining);
        }
    }

    /// 忘记丢弃剩余元素，同时仍然允许释放后备分配。
    pub(crate) fn forget_remaining_elements(&mut self) {
        // 对于 ZST 案例，至关重要的是我们在这里改变 `end`，而不是 `ptr`。
        // `ptr` 必须保持对齐，而 `end` 可能未对齐。
        self.end = self.ptr;
    }

    #[cfg(not(no_global_oom_handling))]
    #[inline]
    pub(crate) fn into_vecdeque(self) -> VecDeque<T, A> {
        // 保持我们的 `Drop` impl 丢弃元素和分配器
        let mut this = ManuallyDrop::new(self);

        // SAFETY: 此分配最初来自 `Vec`，因此它通过了所有这些检查。
        // 我们有 `this.buf` ≤ `this.ptr` ≤ `this.end`，所以下面的 sub_ptr 不能换行，并且会产生一个格式正确的范围。
        // `end` ≤ `buf + cap`，因此范围在边界内。
        // 采用 `alloc` 是可以的，因为没有其他东西会查看它，因为我们的 `Drop` impl 不会运行，所以没有更多的代码。
        //
        //
        unsafe {
            let buf = this.buf.as_ptr();
            let initialized = if T::IS_ZST {
                // ZST 的所有指针都是相同的，所以可以说它们都在 "allocation" 的开头。
                //
                0..this.len()
            } else {
                this.ptr.sub_ptr(buf)..this.end.sub_ptr(buf)
            };
            let cap = this.cap;
            let alloc = ManuallyDrop::take(&mut this.alloc);
            VecDeque::from_contiguous_raw_parts_in(buf, initialized, cap, alloc)
        }
    }
}

#[stable(feature = "vec_intoiter_as_ref", since = "1.46.0")]
impl<T, A: Allocator> AsRef<[T]> for IntoIter<T, A> {
    fn as_ref(&self) -> &[T] {
        self.as_slice()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<T: Send, A: Allocator + Send> Send for IntoIter<T, A> {}
#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<T: Sync, A: Allocator + Sync> Sync for IntoIter<T, A> {}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> Iterator for IntoIter<T, A> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        if self.ptr == self.end {
            None
        } else if T::IS_ZST {
            // `ptr` 必须留在原处以保持对齐，因此我们通过减少 `end` 将长度减少 1。
            //
            self.end = self.end.wrapping_byte_sub(1);

            // 组成此 ZST 的值。
            Some(unsafe { mem::zeroed() })
        } else {
            let old = self.ptr;
            self.ptr = unsafe { self.ptr.add(1) };

            Some(unsafe { ptr::read(old) })
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let exact = if T::IS_ZST {
            self.end.addr().wrapping_sub(self.ptr.addr())
        } else {
            unsafe { self.end.sub_ptr(self.ptr) }
        };
        (exact, Some(exact))
    }

    #[inline]
    fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
        let step_size = self.len().min(n);
        let to_drop = ptr::slice_from_raw_parts_mut(self.ptr as *mut T, step_size);
        if T::IS_ZST {
            // 请参见 `next`，了解我们为何在此处子 `end`。
            self.end = self.end.wrapping_byte_sub(step_size);
        } else {
            // SAFETY: 上面的 min() 确保 step_size 在界限内
            self.ptr = unsafe { self.ptr.add(step_size) };
        }
        // SAFETY: 上面的 min() 确保 step_size 在界限内
        unsafe {
            ptr::drop_in_place(to_drop);
        }
        NonZeroUsize::new(n - step_size).map_or(Ok(()), Err)
    }

    #[inline]
    fn count(self) -> usize {
        self.len()
    }

    #[inline]
    fn next_chunk<const N: usize>(&mut self) -> Result<[T; N], core::array::IntoIter<T, N>> {
        let mut raw_ary = MaybeUninit::uninit_array();

        let len = self.len();

        if T::IS_ZST {
            if len < N {
                self.forget_remaining_elements();
                // 安全性: ZST 可以凭空变出，只有数量必须正确
                return Err(unsafe { array::IntoIter::new_unchecked(raw_ary, 0..len) });
            }

            self.end = self.end.wrapping_byte_sub(N);
            // 安全: 同上
            return Ok(unsafe { raw_ary.transpose().assume_init() });
        }

        if len < N {
            // 安全性: `len` 表示有这么多元素可用，我们刚刚检查了它是否适合数组。
            //
            unsafe {
                ptr::copy_nonoverlapping(self.ptr, raw_ary.as_mut_ptr() as *mut T, len);
                self.forget_remaining_elements();
                return Err(array::IntoIter::new_unchecked(raw_ary, 0..len));
            }
        }

        // 安全性: `len` 大于数组大小。
        // 在此处复制固定数量以完全初始化数组。
        return unsafe {
            ptr::copy_nonoverlapping(self.ptr, raw_ary.as_mut_ptr() as *mut T, N);
            self.ptr = self.ptr.add(N);
            Ok(raw_ary.transpose().assume_init())
        };
    }

    unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> Self::Item
    where
        Self: TrustedRandomAccessNoCoerce,
    {
        // SAFETY: 调用者必须保证 `i` 在 `Vec<T>` 的范围内，因此 `i` 不会溢出 `isize`，并且保证 `self.ptr.add(i)` 指向 `Vec<T>` 的元素，从而保证对解引用有效。
        //
        //
        // 还要注意，`Self: TrustedRandomAccess` 的实现要求 `T: Copy`，因此从缓冲区读取元素不会使它们对于 `Drop` 无效。
        //
        //
        //
        //
        unsafe {
            if T::IS_ZST { mem::zeroed() } else { ptr::read(self.ptr.add(i)) }
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
    #[inline]
    fn next_back(&mut self) -> Option<T> {
        if self.end == self.ptr {
            None
        } else if T::IS_ZST {
            // 有关为何不使用 'ptr.offset' 的信息，请参见上文
            self.end = self.end.wrapping_byte_sub(1);

            // 组成此 ZST 的值。
            Some(unsafe { mem::zeroed() })
        } else {
            self.end = unsafe { self.end.sub(1) };

            Some(unsafe { ptr::read(self.end) })
        }
    }

    #[inline]
    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
        let step_size = self.len().min(n);
        if T::IS_ZST {
            // SAFETY: 与 advance_by() 相同
            self.end = self.end.wrapping_byte_sub(step_size);
        } else {
            // SAFETY: 与 advance_by() 相同
            self.end = unsafe { self.end.sub(step_size) };
        }
        let to_drop = ptr::slice_from_raw_parts_mut(self.end as *mut T, step_size);
        // SAFETY: 与 advance_by() 相同
        unsafe {
            ptr::drop_in_place(to_drop);
        }
        NonZeroUsize::new(n - step_size).map_or(Ok(()), Err)
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {
    fn is_empty(&self) -> bool {
        self.ptr == self.end
    }
}

#[stable(feature = "fused", since = "1.26.0")]
impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}

#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {}

#[stable(feature = "default_iters", since = "1.70.0")]
impl<T, A> Default for IntoIter<T, A>
where
    A: Allocator + Default,
{
    /// 创建一个空的 `vec::IntoIter`。
    ///
    /// ```
    /// # use std::vec;
    /// let iter: vec::IntoIter<u8> = Default::default();
    /// assert_eq!(iter.len(), 0);
    /// assert_eq!(iter.as_slice(), &[]);
    /// ```
    fn default() -> Self {
        super::Vec::new_in(Default::default()).into_iter()
    }
}

#[doc(hidden)]
#[unstable(issue = "none", feature = "std_internals")]
#[rustc_unsafe_specialization_marker]
pub trait NonDrop {}

// T: 复制为 !Drop 的近似值，因为 get_unchecked 不会推进 self.ptr，因此我们无法实现丢弃处理
//
#[unstable(issue = "none", feature = "std_internals")]
impl<T: Copy> NonDrop for T {}

#[doc(hidden)]
#[unstable(issue = "none", feature = "std_internals")]
// 不得实现 TrustedRandomAccess (无 NoCoerce)，因为 `T` 的 subtypes/supertypes 可能不是 `NonDrop`
//
unsafe impl<T, A: Allocator> TrustedRandomAccessNoCoerce for IntoIter<T, A>
where
    T: NonDrop,
{
    const MAY_HAVE_SIDE_EFFECT: bool = false;
}

#[cfg(not(no_global_oom_handling))]
#[stable(feature = "vec_into_iter_clone", since = "1.8.0")]
impl<T: Clone, A: Allocator + Clone> Clone for IntoIter<T, A> {
    #[cfg(not(test))]
    fn clone(&self) -> Self {
        self.as_slice().to_vec_in(self.alloc.deref().clone()).into_iter()
    }
    #[cfg(test)]
    fn clone(&self) -> Self {
        crate::slice::to_vec(self.as_slice(), self.alloc.deref().clone()).into_iter()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter<T, A> {
    fn drop(&mut self) {
        struct DropGuard<'a, T, A: Allocator>(&'a mut IntoIter<T, A>);

        impl<T, A: Allocator> Drop for DropGuard<'_, T, A> {
            fn drop(&mut self) {
                unsafe {
                    // `IntoIter::alloc` 在此之后不再使用，它会被 RawVec 丢弃
                    let alloc = ManuallyDrop::take(&mut self.0.alloc);
                    // RawVec 处理重新分配
                    let _ = RawVec::from_raw_parts_in(self.0.buf.as_ptr(), self.0.cap, alloc);
                }
            }
        }

        let guard = DropGuard(self);
        // 销毁剩余的元素
        unsafe {
            ptr::drop_in_place(guard.0.as_raw_mut_slice());
        }
        // 现在，`guard` 将被丢弃并执行其余的操作
    }
}

// 除了以下三个不安全的 traits 的 SAFETY 不变量之外，还可以参考 vec::in_place_collect 模块文档以获得概述
//
#[unstable(issue = "none", feature = "inplace_iteration")]
#[doc(hidden)]
unsafe impl<T, A: Allocator> InPlaceIterable for IntoIter<T, A> {}

#[unstable(issue = "none", feature = "inplace_iteration")]
#[doc(hidden)]
unsafe impl<T, A: Allocator> SourceIter for IntoIter<T, A> {
    type Source = Self;

    #[inline]
    unsafe fn as_inner(&mut self) -> &mut Self::Source {
        self
    }
}

#[cfg(not(no_global_oom_handling))]
unsafe impl<T> AsVecIntoIter for IntoIter<T> {
    type Item = T;

    fn as_into_iter(&mut self) -> &mut IntoIter<Self::Item> {
        self
    }
}