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