1use core::ptr::{self};
2use core::slice::{self};
34use super::{Drain, Vec};
5use crate::alloc::{Allocator, Global};
67/// A splicing iterator for `Vec`.
8///
9/// This struct is created by [`Vec::splice()`].
10/// See its documentation for more.
11///
12/// # Example
13///
14/// ```
15/// let mut v = vec![0, 1, 2];
16/// let new = [7, 8];
17/// let iter: std::vec::Splice<'_, _> = v.splice(1.., new);
18/// ```
19#[derive(Debug)]
20#[stable(feature = "vec_splice", since = "1.21.0")]
21pub struct Splice<
22'a,
23 I: Iterator + 'a,
24#[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global,
25> {
26pub(super) drain: Drain<'a, I::Item, A>,
27pub(super) replace_with: I,
28}
2930#[stable(feature = "vec_splice", since = "1.21.0")]
31impl<I: Iterator, A: Allocator> Iterator for Splice<'_, I, A> {
32type Item = I::Item;
3334fn next(&mut self) -> Option<Self::Item> {
35self.drain.next()
36 }
3738fn size_hint(&self) -> (usize, Option<usize>) {
39self.drain.size_hint()
40 }
41}
4243#[stable(feature = "vec_splice", since = "1.21.0")]
44impl<I: Iterator, A: Allocator> DoubleEndedIterator for Splice<'_, I, A> {
45fn next_back(&mut self) -> Option<Self::Item> {
46self.drain.next_back()
47 }
48}
4950#[stable(feature = "vec_splice", since = "1.21.0")]
51impl<I: Iterator, A: Allocator> ExactSizeIterator for Splice<'_, I, A> {}
5253#[stable(feature = "vec_splice", since = "1.21.0")]
54impl<I: Iterator, A: Allocator> Drop for Splice<'_, I, A> {
55#[track_caller]
56fn drop(&mut self) {
57self.drain.by_ref().for_each(drop);
58// At this point draining is done and the only remaining tasks are splicing
59 // and moving things into the final place.
60 // Which means we can replace the slice::Iter with pointers that won't point to deallocated
61 // memory, so that Drain::drop is still allowed to call iter.len(), otherwise it would break
62 // the ptr.sub_ptr contract.
63self.drain.iter = (&[]).iter();
6465unsafe {
66if self.drain.tail_len == 0 {
67self.drain.vec.as_mut().extend(self.replace_with.by_ref());
68return;
69 }
7071// First fill the range left by drain().
72if !self.drain.fill(&mut self.replace_with) {
73return;
74 }
7576// There may be more elements. Use the lower bound as an estimate.
77 // FIXME: Is the upper bound a better guess? Or something else?
78let (lower_bound, _upper_bound) = self.replace_with.size_hint();
79if lower_bound > 0 {
80self.drain.move_tail(lower_bound);
81if !self.drain.fill(&mut self.replace_with) {
82return;
83 }
84 }
8586// Collect any remaining elements.
87 // This is a zero-length vector which does not allocate if `lower_bound` was exact.
88let mut collected = self.replace_with.by_ref().collect::<Vec<I::Item>>().into_iter();
89// Now we have an exact count.
90if collected.len() > 0 {
91self.drain.move_tail(collected.len());
92let filled = self.drain.fill(&mut collected);
93debug_assert!(filled);
94debug_assert_eq!(collected.len(), 0);
95 }
96 }
97// Let `Drain::drop` move the tail back if necessary and restore `vec.len`.
98}
99}
100101/// Private helper methods for `Splice::drop`
102impl<T, A: Allocator> Drain<'_, T, A> {
103/// The range from `self.vec.len` to `self.tail_start` contains elements
104 /// that have been moved out.
105 /// Fill that range as much as possible with new elements from the `replace_with` iterator.
106 /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.)
107unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool {
108let vec = unsafe { self.vec.as_mut() };
109let range_start = vec.len;
110let range_end = self.tail_start;
111let range_slice = unsafe {
112 slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start)
113 };
114115for place in range_slice {
116if let Some(new_item) = replace_with.next() {
117unsafe { ptr::write(place, new_item) };
118 vec.len += 1;
119 } else {
120return false;
121 }
122 }
123true
124}
125126/// Makes room for inserting more elements before the tail.
127#[track_caller]
128unsafe fn move_tail(&mut self, additional: usize) {
129let vec = unsafe { self.vec.as_mut() };
130let len = self.tail_start + self.tail_len;
131 vec.buf.reserve(len, additional);
132133let new_tail_start = self.tail_start + additional;
134unsafe {
135let src = vec.as_ptr().add(self.tail_start);
136let dst = vec.as_mut_ptr().add(new_tail_start);
137 ptr::copy(src, dst, self.tail_len);
138 }
139self.tail_start = new_tail_start;
140 }
141}