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

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);

        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;
    }
}