use crate::alloc::{Allocator, Global};
use core::fmt;
use core::iter::{FusedIterator, TrustedLen};
use core::mem::{self, ManuallyDrop, SizedTypeProperties};
use core::ptr::{self, NonNull};
use core::slice::{self};

use super::Vec;

/// `Vec<T>` 的 draining 迭代器。
///
/// 该 `struct` 由 [`Vec::drain`] 创建。
/// 有关更多信息，请参见其文档。
///
/// # Example
///
/// ```
/// let mut v = vec![0, 1, 2];
/// let iter: std::vec::Drain<'_, _> = v.drain(..);
/// ```
#[stable(feature = "drain", since = "1.6.0")]
pub struct Drain<
    'a,
    T: 'a,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global,
> {
    /// 要保存的尾巴索引
    pub(super) tail_start: usize,
    /// 尾巴长度
    pub(super) tail_len: usize,
    /// 当前剩余范围要删除
    pub(super) iter: slice::Iter<'a, T>,
    pub(super) vec: NonNull<Vec<T, A>>,
}

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

impl<'a, T, A: Allocator> Drain<'a, T, A> {
    /// 返回此迭代器的其余项作为切片。
    ///
    /// # Examples
    ///
    /// ```
    /// let mut vec = vec!['a', 'b', 'c'];
    /// let mut drain = vec.drain(..);
    /// assert_eq!(drain.as_slice(), &['a', 'b', 'c']);
    /// let _ = drain.next().unwrap();
    /// assert_eq!(drain.as_slice(), &['b', 'c']);
    /// ```
    #[must_use]
    #[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
    pub fn as_slice(&self) -> &[T] {
        self.iter.as_slice()
    }

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

    /// 在源 `Vec` 中保留未屈服的元素。
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(drain_keep_rest)]
    ///
    /// let mut vec = vec!['a', 'b', 'c'];
    /// let mut drain = vec.drain(..);
    ///
    /// assert_eq!(drain.next().unwrap(), 'a');
    ///
    /// // 这个调用将 'b' 和 'c' 保存在 vec 中。
    /// drain.keep_rest();
    ///
    /// // 如果我们不调用 `keep_rest()`，`vec` 将为空。
    /////
    /// assert_eq!(vec, ['b', 'c']);
    /// ```
    #[unstable(feature = "drain_keep_rest", issue = "101122")]
    pub fn keep_rest(self) {
        // 此时布局如下所示:
        //
        // [head] [yielded by next] [unyielded] [yielded by next_back] [tail] ^-- start         \_________/-- unyielded_len        \____/-- self.tail_len ^-- unyielded_ptr                  ^-- tail
        //
        //
        // 通常 `Drop` impl 会丢弃 [unyielded] 然后移动 [tail] 到 `start`。
        // 在这里我们想要
        // 1. 将 [unyielded] 移动到 `start`
        // 2. 将 [tail] 移至 `start + len(unyielded)` 处的新起点
        // 3. 将原始 vec 的长度更新为 `len(head) + len(unyielded) + len(tail)` a. 对于 ZST，这是我们唯一想做的事情
        // 4. 不要*不要*丢弃自己，因为一切都已经处于一致状态，没有什么可做的
        //
        //
        let mut this = ManuallyDrop::new(self);

        unsafe {
            let source_vec = this.vec.as_mut();

            let start = source_vec.len();
            let tail = this.tail_start;

            let unyielded_len = this.iter.len();
            let unyielded_ptr = this.iter.as_slice().as_ptr();

            // ZST 没有身份，所以我们不需要移动它们。
            if !T::IS_ZST {
                let start_ptr = source_vec.as_mut_ptr().add(start);

                // memmove 退回未屈服的元素
                if unyielded_ptr != start_ptr {
                    let src = unyielded_ptr;
                    let dst = start_ptr;

                    ptr::copy(src, dst, unyielded_len);
                }

                // memmove back 未触及的尾巴
                if tail != (start + unyielded_len) {
                    let src = source_vec.as_ptr().add(tail);
                    let dst = start_ptr.add(unyielded_len);
                    ptr::copy(src, dst, this.tail_len);
                }
            }

            source_vec.set_len(start + unyielded_len + this.tail_len);
        }
    }
}

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

#[stable(feature = "drain", since = "1.6.0")]
unsafe impl<T: Sync, A: Sync + Allocator> Sync for Drain<'_, T, A> {}
#[stable(feature = "drain", since = "1.6.0")]
unsafe impl<T: Send, A: Send + Allocator> Send for Drain<'_, T, A> {}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> {
    #[inline]
    fn next_back(&mut self) -> Option<T> {
        self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
    }
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> Drop for Drain<'_, T, A> {
    fn drop(&mut self) {
        /// 移回未 `Drain`ed 元素以恢复原始 `Vec`。
        struct DropGuard<'r, 'a, T, A: Allocator>(&'r mut Drain<'a, T, A>);

        impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
            fn drop(&mut self) {
                if self.0.tail_len > 0 {
                    unsafe {
                        let source_vec = self.0.vec.as_mut();
                        // 记住原封不动的尾巴，更新到新的长度
                        let start = source_vec.len();
                        let tail = self.0.tail_start;
                        if tail != start {
                            let src = source_vec.as_ptr().add(tail);
                            let dst = source_vec.as_mut_ptr().add(start);
                            ptr::copy(src, dst, self.0.tail_len);
                        }
                        source_vec.set_len(start + self.0.tail_len);
                    }
                }
            }
        }

        let iter = mem::take(&mut self.iter);
        let drop_len = iter.len();

        let mut vec = self.vec;

        if T::IS_ZST {
            // ZSTs 没有标记，所以我们不需要移动它们，我们只需要丢弃正确的数量。
            // 这可以通过操纵 Vec 长度来实现，而不是将值从 `iter` 中移出。
            unsafe {
                let vec = vec.as_mut();
                let old_len = vec.len();
                vec.set_len(old_len + drop_len + self.tail_len);
                vec.truncate(old_len + self.tail_len);
            }

            return;
        }

        // 确保元素被移回适当的位置，即使 drop_in_place 发生 panics 时也是如此
        let _guard = DropGuard(self);

        if drop_len == 0 {
            return;
        }

        // as_slice() 只能在 iter.len() > 0 时调用，因为它也会被 vec::Splice 触及，这可能会将它变成悬垂指针，这会使它和 vec 指针指向不同的分配，这会导致下面的无效指针算法。
        //
        //
        //
        let drop_ptr = iter.as_slice().as_ptr();

        unsafe {
            // drop_ptr 来自 slice::Iter，它只给我们一个 &[T]，但对于 drop_in_place，一个具有可变出处的指针是必要的。
            // 因此，我们必须从原始 vec 重建它，但也要避免在前面创建 &mut，因为这可能会使某些不安全的代码可能依赖的裸指针路径无效。
            //
            //
            let vec_ptr = vec.as_mut().as_mut_ptr();
            let drop_offset = drop_ptr.sub_ptr(vec_ptr);
            let to_drop = ptr::slice_from_raw_parts_mut(vec_ptr.add(drop_offset), drop_len);
            ptr::drop_in_place(to_drop);
        }
    }
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {
    fn is_empty(&self) -> bool {
        self.iter.is_empty()
    }
}

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

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