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