1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
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);
        }
    }
}