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