use crate::alloc::{Allocator, Global};
use core::mem::{ManuallyDrop, SizedTypeProperties};
use core::ptr;
use core::slice;

use super::Vec;

/// 使用闭包确定是否应删除元素的迭代器。
///
/// 该结构体由 [`Vec::drain_filter`] 创建。
/// 有关更多信息，请参见其文档。
///
/// # Example
///
/// ```
/// #![feature(drain_filter)]
///
/// let mut v = vec![0, 1, 2];
/// let iter: std::vec::DrainFilter<'_, _, _> = v.drain_filter(|x| *x % 2 == 0);
/// ```
#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
#[derive(Debug)]
pub struct DrainFilter<
    'a,
    T,
    F,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
> where
    F: FnMut(&mut T) -> bool,
{
    pub(super) vec: &'a mut Vec<T, A>,
    /// `next` 的下一次调用将检查的项的索引。
    pub(super) idx: usize,
    /// 到目前为止已耗尽 (removed) 的项数。
    pub(super) del: usize,
    /// draining 之前 `vec` 的原始长度。
    pub(super) old_len: usize,
    /// 过滤器测试谓词。
    pub(super) pred: F,
    /// 指示 panic 的标志已出现在过滤器测试谓词中。
    /// 这在丢弃实现中用作一个提示，以防止消耗 `DrainFilter` 的其余部分。
    /// 任何未处理的项目将在 `vec` 中后移，但过滤谓词不会丢弃或测试其他任何项目。
    ///
    ///
    pub(super) panic_flag: bool,
}

impl<T, F, A: Allocator> DrainFilter<'_, T, F, A>
where
    F: FnMut(&mut T) -> bool,
{
    /// 返回底层分配器的引用。
    #[unstable(feature = "allocator_api", issue = "32838")]
    #[inline]
    pub fn allocator(&self) -> &A {
        self.vec.allocator()
    }

    /// 在源 `Vec` 中保留未屈服的元素。
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(drain_filter)]
    /// #![feature(drain_keep_rest)]
    ///
    /// let mut vec = vec!['a', 'b', 'c'];
    /// let mut drain = vec.drain_filter(|_| true);
    ///
    /// 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) {
        // 此时布局如下所示:
        //
        //  _____________________/-- old_len
        // /                     \
        // [kept] [yielded] [tail] \_______/ ^-- idx \-- del
        //
        // 通常 `Drop` impl 会丢弃 [tail] (通过 .for_each(drop), ie still calling `pred`)
        //
        // 1. 在 [kept] 之后移动 [tail]
        // 2. 将原始 vec 的长度更新为 `old_len - del` a.
        // 对于 ZST，这是我们唯一想做的事情
        // 3.
        // 不要*不要*丢弃自己，因为一切都已经处于一致状态，没有什么可做的
        //
        let mut this = ManuallyDrop::new(self);

        unsafe {
            // ZST 没有身份，所以我们不需要移动它们。
            if !T::IS_ZST && this.idx < this.old_len && this.del > 0 {
                let ptr = this.vec.as_mut_ptr();
                let src = ptr.add(this.idx);
                let dst = src.sub(this.del);
                let tail_len = this.old_len - this.idx;
                src.copy_to(dst, tail_len);
            }

            let new_len = this.old_len - this.del;
            this.vec.set_len(new_len);
        }
    }
}

#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
impl<T, F, A: Allocator> Iterator for DrainFilter<'_, T, F, A>
where
    F: FnMut(&mut T) -> bool,
{
    type Item = T;

    fn next(&mut self) -> Option<T> {
        unsafe {
            while self.idx < self.old_len {
                let i = self.idx;
                let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len);
                self.panic_flag = true;
                let drained = (self.pred)(&mut v[i]);
                self.panic_flag = false;
                // 在谓词被调用之后更新索引。
                // 如果索引先于谓词 panics 进行更新，则该索引处的元素将被泄漏。
                //
                self.idx += 1;
                if drained {
                    self.del += 1;
                    return Some(ptr::read(&v[i]));
                } else if self.del > 0 {
                    let del = self.del;
                    let src: *const T = &v[i];
                    let dst: *mut T = &mut v[i - del];
                    ptr::copy_nonoverlapping(src, dst, 1);
                }
            }
            None
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.old_len - self.idx))
    }
}

#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")]
impl<T, F, A: Allocator> Drop for DrainFilter<'_, T, F, A>
where
    F: FnMut(&mut T) -> bool,
{
    fn drop(&mut self) {
        struct BackshiftOnDrop<'a, 'b, T, F, A: Allocator>
        where
            F: FnMut(&mut T) -> bool,
        {
            drain: &'b mut DrainFilter<'a, T, F, A>,
        }

        impl<'a, 'b, T, F, A: Allocator> Drop for BackshiftOnDrop<'a, 'b, T, F, A>
        where
            F: FnMut(&mut T) -> bool,
        {
            fn drop(&mut self) {
                unsafe {
                    if self.drain.idx < self.drain.old_len && self.drain.del > 0 {
                        // 这是一个非常混乱的状态，实际上并没有一件明显正确的事情要做。
                        // 我们不想继续尝试执行 `pred`，因此我们只回移了所有未处理的元素，并告诉 vec 它们仍然存在。
                        //
                        // 需要回退以防止在谓词发生 panic 之前对最后一个成功排出的项进行双重丢弃。
                        //
                        //
                        let ptr = self.drain.vec.as_mut_ptr();
                        let src = ptr.add(self.drain.idx);
                        let dst = src.sub(self.drain.del);
                        let tail_len = self.drain.old_len - self.drain.idx;
                        src.copy_to(dst, tail_len);
                    }
                    self.drain.vec.set_len(self.drain.old_len - self.drain.del);
                }
            }
        }

        let backshift = BackshiftOnDrop { drain: self };

        // 如果过滤谓词尚未 panic，请尝试消耗所有剩余的元素。
        // 无论是否已经 panic 或这里的消耗量 panics，我们都会回退所有剩余的元素。
        //
        if !backshift.drain.panic_flag {
            backshift.drain.for_each(drop);
        }
    }
}