Loading...
Note: File does not exist in v3.1.
1// SPDX-License-Identifier: Apache-2.0 OR MIT
2
3use crate::alloc::{Allocator, Global};
4use core::fmt;
5use core::iter::{FusedIterator, TrustedLen};
6use core::mem;
7use core::ptr::{self, NonNull};
8use core::slice::{self};
9
10use 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")]
24pub 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")]
39impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> {
40 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
41 f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
42 }
43}
44
45impl<'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")]
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]
67 pub fn allocator(&self) -> &A {
68 unsafe { self.vec.as_ref().allocator() }
69 }
70}
71
72#[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
73impl<'a, T, A: Allocator> AsRef<[T]> for Drain<'a, T, A> {
74 fn as_ref(&self) -> &[T] {
75 self.as_slice()
76 }
77}
78
79#[stable(feature = "drain", since = "1.6.0")]
80unsafe impl<T: Sync, A: Sync + Allocator> Sync for Drain<'_, T, A> {}
81#[stable(feature = "drain", since = "1.6.0")]
82unsafe impl<T: Send, A: Send + Allocator> Send for Drain<'_, T, A> {}
83
84#[stable(feature = "drain", since = "1.6.0")]
85impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
86 type Item = T;
87
88 #[inline]
89 fn next(&mut self) -> Option<T> {
90 self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
91 }
92
93 fn size_hint(&self) -> (usize, Option<usize>) {
94 self.iter.size_hint()
95 }
96}
97
98#[stable(feature = "drain", since = "1.6.0")]
99impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> {
100 #[inline]
101 fn next_back(&mut self) -> Option<T> {
102 self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
103 }
104}
105
106#[stable(feature = "drain", since = "1.6.0")]
107impl<T, A: Allocator> Drop for Drain<'_, T, A> {
108 fn drop(&mut self) {
109 /// Moves back the un-`Drain`ed elements to restore the original `Vec`.
110 struct DropGuard<'r, 'a, T, A: Allocator>(&'r mut Drain<'a, T, A>);
111
112 impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
113 fn drop(&mut self) {
114 if self.0.tail_len > 0 {
115 unsafe {
116 let source_vec = self.0.vec.as_mut();
117 // memmove back untouched tail, update to new length
118 let start = source_vec.len();
119 let tail = self.0.tail_start;
120 if tail != start {
121 let src = source_vec.as_ptr().add(tail);
122 let dst = source_vec.as_mut_ptr().add(start);
123 ptr::copy(src, dst, self.0.tail_len);
124 }
125 source_vec.set_len(start + self.0.tail_len);
126 }
127 }
128 }
129 }
130
131 let iter = mem::replace(&mut self.iter, (&mut []).iter());
132 let drop_len = iter.len();
133
134 let mut vec = self.vec;
135
136 if mem::size_of::<T>() == 0 {
137 // ZSTs have no identity, so we don't need to move them around, we only need to drop the correct amount.
138 // this can be achieved by manipulating the Vec length instead of moving values out from `iter`.
139 unsafe {
140 let vec = vec.as_mut();
141 let old_len = vec.len();
142 vec.set_len(old_len + drop_len + self.tail_len);
143 vec.truncate(old_len + self.tail_len);
144 }
145
146 return;
147 }
148
149 // ensure elements are moved back into their appropriate places, even when drop_in_place panics
150 let _guard = DropGuard(self);
151
152 if drop_len == 0 {
153 return;
154 }
155
156 // as_slice() must only be called when iter.len() is > 0 because
157 // vec::Splice modifies vec::Drain fields and may grow the vec which would invalidate
158 // the iterator's internal pointers. Creating a reference to deallocated memory
159 // is invalid even when it is zero-length
160 let drop_ptr = iter.as_slice().as_ptr();
161
162 unsafe {
163 // drop_ptr comes from a slice::Iter which only gives us a &[T] but for drop_in_place
164 // a pointer with mutable provenance is necessary. Therefore we must reconstruct
165 // it from the original vec but also avoid creating a &mut to the front since that could
166 // invalidate raw pointers to it which some unsafe code might rely on.
167 let vec_ptr = vec.as_mut().as_mut_ptr();
168 let drop_offset = drop_ptr.sub_ptr(vec_ptr);
169 let to_drop = ptr::slice_from_raw_parts_mut(vec_ptr.add(drop_offset), drop_len);
170 ptr::drop_in_place(to_drop);
171 }
172 }
173}
174
175#[stable(feature = "drain", since = "1.6.0")]
176impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {
177 fn is_empty(&self) -> bool {
178 self.iter.is_empty()
179 }
180}
181
182#[unstable(feature = "trusted_len", issue = "37572")]
183unsafe impl<T, A: Allocator> TrustedLen for Drain<'_, T, A> {}
184
185#[stable(feature = "fused", since = "1.26.0")]
186impl<T, A: Allocator> FusedIterator for Drain<'_, T, A> {}