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
use crate::alloc::{Allocator, Global};
use core::ptr::{self};
use core::slice::{self};

use super::{Drain, Vec};

/// `Vec` 的拼接迭代器。
///
/// 这个结构体是由 [`Vec::splice ()`] 创建的。
/// 有关更多信息,请参见其文档。
///
/// # Example
///
/// ```
/// let mut v = vec![0, 1, 2];
/// let new = [7, 8];
/// let iter: std::vec::Splice<'_, _> = v.splice(1.., new);
/// ```
#[derive(Debug)]
#[stable(feature = "vec_splice", since = "1.21.0")]
pub struct Splice<
    'a,
    I: Iterator + 'a,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global,
> {
    pub(super) drain: Drain<'a, I::Item, A>,
    pub(super) replace_with: I,
}

#[stable(feature = "vec_splice", since = "1.21.0")]
impl<I: Iterator, A: Allocator> Iterator for Splice<'_, I, A> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        self.drain.next()
    }

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

#[stable(feature = "vec_splice", since = "1.21.0")]
impl<I: Iterator, A: Allocator> DoubleEndedIterator for Splice<'_, I, A> {
    fn next_back(&mut self) -> Option<Self::Item> {
        self.drain.next_back()
    }
}

#[stable(feature = "vec_splice", since = "1.21.0")]
impl<I: Iterator, A: Allocator> ExactSizeIterator for Splice<'_, I, A> {}

#[stable(feature = "vec_splice", since = "1.21.0")]
impl<I: Iterator, A: Allocator> Drop for Splice<'_, I, A> {
    fn drop(&mut self) {
        self.drain.by_ref().for_each(drop);
        // 此时 draining 已经完成,唯一剩下的任务就是拼接和移动东西到最后的地方。
        // 这意味着我们可以用不会指向释放内存的指针替换 slice::Iter,这样 Drain::drop 仍然可以调用 iter.len(),否则会破坏 ptr.sub_ptr 契约。
        //
        //
        //
        self.drain.iter = (&[]).iter();

        unsafe {
            if self.drain.tail_len == 0 {
                self.drain.vec.as_mut().extend(self.replace_with.by_ref());
                return;
            }

            // 首先填充 drain() 剩余的范围。
            if !self.drain.fill(&mut self.replace_with) {
                return;
            }

            // 可能还有更多元素。使用下限作为估计值。
            // FIXME: 上限是更好的猜测吗? 或者是其他东西?
            let (lower_bound, _upper_bound) = self.replace_with.size_hint();
            if lower_bound > 0 {
                self.drain.move_tail(lower_bound);
                if !self.drain.fill(&mut self.replace_with) {
                    return;
                }
            }

            // 收集所有剩余的元素。
            // 这是一个零长度的 vector,如果 `lower_bound` 是精确的,则不分配。
            let mut collected = self.replace_with.by_ref().collect::<Vec<I::Item>>().into_iter();
            // 现在我们有了一个准确的计数。
            if collected.len() > 0 {
                self.drain.move_tail(collected.len());
                let filled = self.drain.fill(&mut collected);
                debug_assert!(filled);
                debug_assert_eq!(collected.len(), 0);
            }
        }
        // 如有必要,让 `Drain::drop` 将尾巴向后移,并恢复 `vec.len`。
    }
}

/// `Splice::drop` 的 private 帮助器方法
impl<T, A: Allocator> Drain<'_, T, A> {
    /// 从 `self.vec.len` 到 `self.tail_start` 的范围包含已移出的元素。
    ///
    /// 尽可能用 `replace_with` 迭代器中的新元素填充该范围。
    /// 如果我们填满整个范围,则返回 `true`。(`replace_with.next()` 没有返回 `None`。)
    unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool {
        let vec = unsafe { self.vec.as_mut() };
        let range_start = vec.len;
        let range_end = self.tail_start;
        let range_slice = unsafe {
            slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start)
        };

        for place in range_slice {
            if let Some(new_item) = replace_with.next() {
                unsafe { ptr::write(place, new_item) };
                vec.len += 1;
            } else {
                return false;
            }
        }
        true
    }

    /// 为在尾部之前插入更多元素留出空间。
    unsafe fn move_tail(&mut self, additional: usize) {
        let vec = unsafe { self.vec.as_mut() };
        let len = self.tail_start + self.tail_len;
        vec.buf.reserve(len, additional);

        let new_tail_start = self.tail_start + additional;
        unsafe {
            let src = vec.as_ptr().add(self.tail_start);
            let dst = vec.as_mut_ptr().add(new_tail_start);
            ptr::copy(src, dst, self.tail_len);
        }
        self.tail_start = new_tail_start;
    }
}