use crate::alloc::{Allocator, Global};
use core::ptr::{self};
use core::slice::{self};

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()
    }
}

#[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 或这里的消耗量 panics，我们都会回退所有剩余的元素。
        //
        if !backshift.drain.panic_flag {
            backshift.drain.for_each(drop);
        }
    }
}