bump_scope/bump_vec/
splice.rs

1#![cfg(feature = "panic-on-alloc")]
2
3use core::{ptr, slice};
4
5use crate::{BumpAllocatorExt, BumpVec, destructure::destructure};
6
7use super::Drain;
8
9/// A splicing iterator for `BumpVec`.
10///
11/// This struct is created by [`BumpVec::splice()`].
12/// See its documentation for more.
13///
14/// # Example
15///
16/// ```
17/// # use bump_scope::{Bump, bump_vec};
18/// # let bump: Bump = Bump::new();
19/// let mut v = bump_vec![in &bump; 0, 1, 2];
20/// let new = [7, 8];
21/// let old = bump.alloc_iter_exact(v.splice(1.., new));
22/// assert_eq!(old, [1, 2]);
23/// assert_eq!(v, [0, 7, 8]);
24/// ```
25///
26/// [`BumpVec::splice()`]: crate::BumpVec::splice
27#[derive(Debug)]
28pub struct Splice<'a, I: Iterator + 'a, A: BumpAllocatorExt> {
29    pub(super) drain: Drain<'a, I::Item, A>,
30    pub(super) replace_with: I,
31}
32
33impl<I: Iterator, A: BumpAllocatorExt> Iterator for Splice<'_, I, A> {
34    type Item = I::Item;
35
36    #[inline]
37    fn next(&mut self) -> Option<Self::Item> {
38        self.drain.next()
39    }
40
41    #[inline]
42    fn size_hint(&self) -> (usize, Option<usize>) {
43        self.drain.size_hint()
44    }
45}
46
47impl<I: Iterator, A: BumpAllocatorExt> DoubleEndedIterator for Splice<'_, I, A> {
48    #[inline]
49    fn next_back(&mut self) -> Option<Self::Item> {
50        self.drain.next_back()
51    }
52}
53
54impl<I: Iterator, A: BumpAllocatorExt> ExactSizeIterator for Splice<'_, I, A> {}
55
56impl<I: Iterator, A: BumpAllocatorExt> Drop for Splice<'_, I, A> {
57    fn drop(&mut self) {
58        self.drain.by_ref().for_each(drop);
59        // At this point draining is done and the only remaining tasks are splicing
60        // and moving things into the final place.
61        // Which means we can replace the slice::Iter with pointers that won't point to deallocated
62        // memory, so that Drain::drop is still allowed to call iter.len(), otherwise it would break
63        // the ptr.sub_ptr contract.
64        self.drain.iter = <[I::Item]>::iter(&[]);
65
66        unsafe {
67            if self.drain.tail_len == 0 {
68                self.drain.vec.as_mut().extend(self.replace_with.by_ref());
69                return;
70            }
71
72            // First fill the range left by drain().
73            if !self.drain.fill(&mut self.replace_with) {
74                return;
75            }
76
77            // There may be more elements. Use the lower bound as an estimate.
78            // STD-FIXME: Is the upper bound a better guess? Or something else?
79            let (lower_bound, _upper_bound) = self.replace_with.size_hint();
80            if lower_bound > 0 {
81                self.drain.move_tail(lower_bound);
82                if !self.drain.fill(&mut self.replace_with) {
83                    return;
84                }
85            }
86
87            // Collect any remaining elements.
88            // This is a zero-length vector which does not allocate if `lower_bound` was exact.
89            let collected = BumpVec::from_iter_in(&mut self.replace_with, self.drain.vec.as_ref().allocator());
90
91            // We can't use `into_fixed_vec` here because that would require a
92            // `BumpAllocatorScope<'a>` instead of just a `BumpAllocator`.
93            destructure!(let BumpVec::<I::Item, &A> { fixed: collected } = collected);
94            let mut collected = collected.cook().into_iter();
95
96            // Now we have an exact count.
97            #[expect(clippy::len_zero)]
98            if collected.len() > 0 {
99                self.drain.move_tail(collected.len());
100                let filled = self.drain.fill(&mut collected);
101                debug_assert!(filled);
102                debug_assert_eq!(collected.len(), 0);
103            }
104        }
105        // Let `Drain::drop` move the tail back if necessary and restore `vec.len`.
106    }
107}
108
109/// Private helper methods for `Splice::drop`
110impl<T, A: BumpAllocatorExt> Drain<'_, T, A> {
111    /// The range from `self.vec.len` to `self.tail_start` contains elements
112    /// that have been moved out.
113    /// Fill that range as much as possible with new elements from the `replace_with` iterator.
114    /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.)
115    unsafe fn fill<I: Iterator<Item = T>>(&mut self, replace_with: &mut I) -> bool {
116        unsafe {
117            let vec = self.vec.as_mut();
118            let range_start = vec.len();
119            let range_end = self.tail_start;
120            let range_slice = slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start);
121
122            for place in range_slice {
123                match replace_with.next() {
124                    Some(new_item) => {
125                        ptr::write(place, new_item);
126                        vec.inc_len(1);
127                    }
128                    _ => {
129                        return false;
130                    }
131                }
132            }
133            true
134        }
135    }
136
137    /// Makes room for inserting more elements before the tail.
138    unsafe fn move_tail(&mut self, additional: usize) {
139        unsafe {
140            let vec = self.vec.as_mut();
141            let len = self.tail_start + self.tail_len;
142            vec.buf_reserve(len, additional);
143
144            let new_tail_start = self.tail_start + additional;
145
146            let src = vec.as_ptr().add(self.tail_start);
147            let dst = vec.as_mut_ptr().add(new_tail_start);
148            ptr::copy(src, dst, self.tail_len);
149
150            self.tail_start = new_tail_start;
151        }
152    }
153}
bump_scope/bump_vec/splice.rs

bump_scope/bump_vec/
splice.rs
