Skip to main content

alloc/vec/
drain.rs

1use core::iter::{FusedIterator, TrustedLen};
2use core::mem::{self, ManuallyDrop, SizedTypeProperties};
3use core::ptr::{self, NonNull};
4use core::{fmt, slice};
5
6use super::Vec;
7use crate::alloc::{Allocator, Global};
8
9/// A draining iterator for `Vec<T>`.
10///
11/// This `struct` is created by [`Vec::drain`].
12/// See its documentation for more.
13///
14/// # Example
15///
16/// ```
17/// let mut v = vec![0, 1, 2];
18/// let iter: std::vec::Drain<'_, _> = v.drain(..);
19/// ```
20#[stable(feature = "drain", since = "1.6.0")]
21pub struct Drain<
22    'a,
23    T: 'a,
24    #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: Allocator + 'a = Global,
25> {
26    /// Index of tail to preserve
27    pub(super) tail_start: usize,
28    /// Length of tail
29    pub(super) tail_len: usize,
30    /// Current remaining range to remove
31    pub(super) iter: slice::Iter<'a, T>,
32    pub(super) vec: NonNull<Vec<T, A>>,
33}
34
35#[stable(feature = "collection_debug", since = "1.17.0")]
36impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> {
37    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
38        f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
39    }
40}
41
42impl<'a, T, A: Allocator> Drain<'a, T, A> {
43    /// Returns the remaining items of this iterator as a slice.
44    ///
45    /// # Examples
46    ///
47    /// ```
48    /// let mut vec = vec!['a', 'b', 'c'];
49    /// let mut drain = vec.drain(..);
50    /// assert_eq!(drain.as_slice(), &['a', 'b', 'c']);
51    /// let _ = drain.next().unwrap();
52    /// assert_eq!(drain.as_slice(), &['b', 'c']);
53    /// ```
54    #[must_use]
55    #[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
56    pub fn as_slice(&self) -> &[T] {
57        self.iter.as_slice()
58    }
59
60    /// Returns a reference to the underlying allocator.
61    #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")]
62    #[inline]
63    pub fn allocator(&self) -> &A {
64        // SAFETY: `vec` is valid for reads.
65        unsafe { self.vec.as_ref().allocator() }
66    }
67
68    /// Keep unyielded elements in the source `Vec`.
69    ///
70    /// # Examples
71    ///
72    /// ```
73    /// #![feature(drain_keep_rest)]
74    ///
75    /// let mut vec = vec!['a', 'b', 'c'];
76    /// let mut drain = vec.drain(..);
77    ///
78    /// assert_eq!(drain.next().unwrap(), 'a');
79    ///
80    /// // This call keeps 'b' and 'c' in the vec.
81    /// drain.keep_rest();
82    ///
83    /// // If we wouldn't call `keep_rest()`,
84    /// // `vec` would be empty.
85    /// assert_eq!(vec, ['b', 'c']);
86    /// ```
87    #[unstable(feature = "drain_keep_rest", issue = "101122")]
88    pub fn keep_rest(self) {
89        // At this moment layout looks like this:
90        //
91        // [head] [yielded by next] [unyielded] [yielded by next_back] [tail]
92        //        ^-- start         \_________/-- unyielded_len        \____/-- self.tail_len
93        //                          ^-- unyielded_ptr                  ^-- tail
94        //
95        // Normally `Drop` impl would drop [unyielded] and then move [tail] to the `start`.
96        // Here we want to
97        // 1. Move [unyielded] to `start`
98        // 2. Move [tail] to a new start at `start + len(unyielded)`
99        // 3. Update length of the original vec to `len(head) + len(unyielded) + len(tail)`
100        //    a. In case of ZST, this is the only thing we want to do
101        // 4. Do *not* drop self, as everything is put in a consistent state already, there is nothing to do
102        let mut this = ManuallyDrop::new(self);
103
104        // ignore-tidy-undocumented-unsafe
105        unsafe {
106            let source_vec = this.vec.as_mut();
107
108            let start = source_vec.len();
109            let tail = this.tail_start;
110
111            let unyielded_len = this.iter.len();
112            let unyielded_ptr = this.iter.as_slice().as_ptr();
113
114            // ZSTs have no identity, so we don't need to move them around.
115            if !T::IS_ZST {
116                let start_ptr = source_vec.as_mut_ptr().add(start);
117
118                // memmove back unyielded elements
119                if unyielded_ptr != start_ptr {
120                    let src = unyielded_ptr;
121                    let dst = start_ptr;
122
123                    ptr::copy(src, dst, unyielded_len);
124                }
125
126                // memmove back untouched tail
127                if tail != (start + unyielded_len) {
128                    let src = source_vec.as_ptr().add(tail);
129                    let dst = start_ptr.add(unyielded_len);
130                    ptr::copy(src, dst, this.tail_len);
131                }
132            }
133
134            source_vec.set_len(start + unyielded_len + this.tail_len);
135        }
136    }
137}
138
139#[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
140impl<'a, T, A: Allocator> AsRef<[T]> for Drain<'a, T, A> {
141    fn as_ref(&self) -> &[T] {
142        self.as_slice()
143    }
144}
145
146#[stable(feature = "drain", since = "1.6.0")]
147unsafe impl<T: Sync, A: Sync + Allocator> Sync for Drain<'_, T, A> {}
148#[stable(feature = "drain", since = "1.6.0")]
149unsafe impl<T: Send, A: Send + Allocator> Send for Drain<'_, T, A> {}
150
151#[stable(feature = "drain", since = "1.6.0")]
152impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
153    type Item = T;
154
155    #[inline]
156    fn next(&mut self) -> Option<T> {
157        // ignore-tidy-undocumented-unsafe
158        self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
159    }
160
161    fn size_hint(&self) -> (usize, Option<usize>) {
162        self.iter.size_hint()
163    }
164}
165
166#[stable(feature = "drain", since = "1.6.0")]
167impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> {
168    #[inline]
169    fn next_back(&mut self) -> Option<T> {
170        // ignore-tidy-undocumented-unsafe
171        self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
172    }
173}
174
175#[stable(feature = "drain", since = "1.6.0")]
176impl<T, A: Allocator> Drop for Drain<'_, T, A> {
177    fn drop(&mut self) {
178        /// Moves back the un-`Drain`ed elements to restore the original `Vec`.
179        struct DropGuard<'r, 'a, T, A: Allocator>(&'r mut Drain<'a, T, A>);
180
181        impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
182            fn drop(&mut self) {
183                if self.0.tail_len > 0 {
184                    // ignore-tidy-undocumented-unsafe
185                    unsafe {
186                        let source_vec = self.0.vec.as_mut();
187                        // memmove back untouched tail, update to new length
188                        let start = source_vec.len();
189                        let tail = self.0.tail_start;
190                        if tail != start {
191                            let src = source_vec.as_ptr().add(tail);
192                            let dst = source_vec.as_mut_ptr().add(start);
193                            ptr::copy(src, dst, self.0.tail_len);
194                        }
195                        source_vec.set_len(start + self.0.tail_len);
196                    }
197                }
198            }
199        }
200
201        let iter = mem::take(&mut self.iter);
202        let drop_len = iter.len();
203
204        let mut vec = self.vec;
205
206        if T::IS_ZST {
207            // ZSTs have no identity, so we don't need to move them around, we only need to drop the correct amount.
208            // this can be achieved by manipulating the Vec length instead of moving values out from `iter`.
209            // ignore-tidy-undocumented-unsafe
210            unsafe {
211                let vec = vec.as_mut();
212                let old_len = vec.len();
213                vec.set_len(old_len + drop_len + self.tail_len);
214                vec.truncate(old_len + self.tail_len);
215            }
216
217            return;
218        }
219
220        // ensure elements are moved back into their appropriate places, even when drop_in_place panics
221        let _guard = DropGuard(self);
222
223        if drop_len == 0 {
224            return;
225        }
226
227        // as_slice() must only be called when iter.len() is > 0 because
228        // it also gets touched by vec::Splice which may turn it into a dangling pointer
229        // which would make it and the vec pointer point to different allocations which would
230        // lead to invalid pointer arithmetic below.
231        let drop_ptr = iter.as_slice().as_ptr();
232
233        // ignore-tidy-undocumented-unsafe
234        unsafe {
235            // drop_ptr comes from a slice::Iter which only gives us a &[T] but for drop_in_place
236            // a pointer with mutable provenance is necessary. Therefore we must reconstruct
237            // it from the original vec but also avoid creating a &mut to the front since that could
238            // invalidate raw pointers to it which some unsafe code might rely on.
239            let vec_ptr = vec.as_mut().as_mut_ptr();
240            let drop_offset = drop_ptr.offset_from_unsigned(vec_ptr);
241            let to_drop = vec_ptr.add(drop_offset).cast_slice(drop_len);
242            ptr::drop_in_place(to_drop);
243        }
244    }
245}
246
247#[stable(feature = "drain", since = "1.6.0")]
248impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {
249    fn is_empty(&self) -> bool {
250        self.iter.is_empty()
251    }
252}
253
254#[unstable(feature = "trusted_len", issue = "37572")]
255unsafe impl<T, A: Allocator> TrustedLen for Drain<'_, T, A> {}
256
257#[stable(feature = "fused", since = "1.26.0")]
258impl<T, A: Allocator> FusedIterator for Drain<'_, T, A> {}