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
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
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> {}