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