Loading...
Note: File does not exist in v5.9.
1// SPDX-License-Identifier: Apache-2.0 OR MIT
2
3#[cfg(not(no_global_oom_handling))]
4use super::AsVecIntoIter;
5use crate::alloc::{Allocator, Global};
6#[cfg(not(no_global_oom_handling))]
7use crate::collections::VecDeque;
8use crate::raw_vec::RawVec;
9use core::array;
10use core::fmt;
11use core::iter::{
12 FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccessNoCoerce,
13};
14use core::marker::PhantomData;
15use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties};
16use core::num::NonZeroUsize;
17#[cfg(not(no_global_oom_handling))]
18use core::ops::Deref;
19use core::ptr::{self, NonNull};
20use core::slice::{self};
21
22/// An iterator that moves out of a vector.
23///
24/// This `struct` is created by the `into_iter` method on [`Vec`](super::Vec)
25/// (provided by the [`IntoIterator`] trait).
26///
27/// # Example
28///
29/// ```
30/// let v = vec![0, 1, 2];
31/// let iter: std::vec::IntoIter<_> = v.into_iter();
32/// ```
33#[stable(feature = "rust1", since = "1.0.0")]
34#[rustc_insignificant_dtor]
35pub struct IntoIter<
36 T,
37 #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global,
38> {
39 pub(super) buf: NonNull<T>,
40 pub(super) phantom: PhantomData<T>,
41 pub(super) cap: usize,
42 // the drop impl reconstructs a RawVec from buf, cap and alloc
43 // to avoid dropping the allocator twice we need to wrap it into ManuallyDrop
44 pub(super) alloc: ManuallyDrop<A>,
45 pub(super) ptr: *const T,
46 pub(super) end: *const T, // If T is a ZST, this is actually ptr+len. This encoding is picked so that
47 // ptr == end is a quick test for the Iterator being empty, that works
48 // for both ZST and non-ZST.
49}
50
51#[stable(feature = "vec_intoiter_debug", since = "1.13.0")]
52impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
53 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
54 f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
55 }
56}
57
58impl<T, A: Allocator> IntoIter<T, A> {
59 /// Returns the remaining items of this iterator as a slice.
60 ///
61 /// # Examples
62 ///
63 /// ```
64 /// let vec = vec!['a', 'b', 'c'];
65 /// let mut into_iter = vec.into_iter();
66 /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
67 /// let _ = into_iter.next().unwrap();
68 /// assert_eq!(into_iter.as_slice(), &['b', 'c']);
69 /// ```
70 #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
71 pub fn as_slice(&self) -> &[T] {
72 unsafe { slice::from_raw_parts(self.ptr, self.len()) }
73 }
74
75 /// Returns the remaining items of this iterator as a mutable slice.
76 ///
77 /// # Examples
78 ///
79 /// ```
80 /// let vec = vec!['a', 'b', 'c'];
81 /// let mut into_iter = vec.into_iter();
82 /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']);
83 /// into_iter.as_mut_slice()[2] = 'z';
84 /// assert_eq!(into_iter.next().unwrap(), 'a');
85 /// assert_eq!(into_iter.next().unwrap(), 'b');
86 /// assert_eq!(into_iter.next().unwrap(), 'z');
87 /// ```
88 #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")]
89 pub fn as_mut_slice(&mut self) -> &mut [T] {
90 unsafe { &mut *self.as_raw_mut_slice() }
91 }
92
93 /// Returns a reference to the underlying allocator.
94 #[unstable(feature = "allocator_api", issue = "32838")]
95 #[inline]
96 pub fn allocator(&self) -> &A {
97 &self.alloc
98 }
99
100 fn as_raw_mut_slice(&mut self) -> *mut [T] {
101 ptr::slice_from_raw_parts_mut(self.ptr as *mut T, self.len())
102 }
103
104 /// Drops remaining elements and relinquishes the backing allocation.
105 /// This method guarantees it won't panic before relinquishing
106 /// the backing allocation.
107 ///
108 /// This is roughly equivalent to the following, but more efficient
109 ///
110 /// ```
111 /// # let mut into_iter = Vec::<u8>::with_capacity(10).into_iter();
112 /// let mut into_iter = std::mem::replace(&mut into_iter, Vec::new().into_iter());
113 /// (&mut into_iter).for_each(drop);
114 /// std::mem::forget(into_iter);
115 /// ```
116 ///
117 /// This method is used by in-place iteration, refer to the vec::in_place_collect
118 /// documentation for an overview.
119 #[cfg(not(no_global_oom_handling))]
120 pub(super) fn forget_allocation_drop_remaining(&mut self) {
121 let remaining = self.as_raw_mut_slice();
122
123 // overwrite the individual fields instead of creating a new
124 // struct and then overwriting &mut self.
125 // this creates less assembly
126 self.cap = 0;
127 self.buf = unsafe { NonNull::new_unchecked(RawVec::NEW.ptr()) };
128 self.ptr = self.buf.as_ptr();
129 self.end = self.buf.as_ptr();
130
131 // Dropping the remaining elements can panic, so this needs to be
132 // done only after updating the other fields.
133 unsafe {
134 ptr::drop_in_place(remaining);
135 }
136 }
137
138 /// Forgets to Drop the remaining elements while still allowing the backing allocation to be freed.
139 pub(crate) fn forget_remaining_elements(&mut self) {
140 // For th ZST case, it is crucial that we mutate `end` here, not `ptr`.
141 // `ptr` must stay aligned, while `end` may be unaligned.
142 self.end = self.ptr;
143 }
144
145 #[cfg(not(no_global_oom_handling))]
146 #[inline]
147 pub(crate) fn into_vecdeque(self) -> VecDeque<T, A> {
148 // Keep our `Drop` impl from dropping the elements and the allocator
149 let mut this = ManuallyDrop::new(self);
150
151 // SAFETY: This allocation originally came from a `Vec`, so it passes
152 // all those checks. We have `this.buf` ≤ `this.ptr` ≤ `this.end`,
153 // so the `sub_ptr`s below cannot wrap, and will produce a well-formed
154 // range. `end` ≤ `buf + cap`, so the range will be in-bounds.
155 // Taking `alloc` is ok because nothing else is going to look at it,
156 // since our `Drop` impl isn't going to run so there's no more code.
157 unsafe {
158 let buf = this.buf.as_ptr();
159 let initialized = if T::IS_ZST {
160 // All the pointers are the same for ZSTs, so it's fine to
161 // say that they're all at the beginning of the "allocation".
162 0..this.len()
163 } else {
164 this.ptr.sub_ptr(buf)..this.end.sub_ptr(buf)
165 };
166 let cap = this.cap;
167 let alloc = ManuallyDrop::take(&mut this.alloc);
168 VecDeque::from_contiguous_raw_parts_in(buf, initialized, cap, alloc)
169 }
170 }
171}
172
173#[stable(feature = "vec_intoiter_as_ref", since = "1.46.0")]
174impl<T, A: Allocator> AsRef<[T]> for IntoIter<T, A> {
175 fn as_ref(&self) -> &[T] {
176 self.as_slice()
177 }
178}
179
180#[stable(feature = "rust1", since = "1.0.0")]
181unsafe impl<T: Send, A: Allocator + Send> Send for IntoIter<T, A> {}
182#[stable(feature = "rust1", since = "1.0.0")]
183unsafe impl<T: Sync, A: Allocator + Sync> Sync for IntoIter<T, A> {}
184
185#[stable(feature = "rust1", since = "1.0.0")]
186impl<T, A: Allocator> Iterator for IntoIter<T, A> {
187 type Item = T;
188
189 #[inline]
190 fn next(&mut self) -> Option<T> {
191 if self.ptr == self.end {
192 None
193 } else if T::IS_ZST {
194 // `ptr` has to stay where it is to remain aligned, so we reduce the length by 1 by
195 // reducing the `end`.
196 self.end = self.end.wrapping_byte_sub(1);
197
198 // Make up a value of this ZST.
199 Some(unsafe { mem::zeroed() })
200 } else {
201 let old = self.ptr;
202 self.ptr = unsafe { self.ptr.add(1) };
203
204 Some(unsafe { ptr::read(old) })
205 }
206 }
207
208 #[inline]
209 fn size_hint(&self) -> (usize, Option<usize>) {
210 let exact = if T::IS_ZST {
211 self.end.addr().wrapping_sub(self.ptr.addr())
212 } else {
213 unsafe { self.end.sub_ptr(self.ptr) }
214 };
215 (exact, Some(exact))
216 }
217
218 #[inline]
219 fn advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
220 let step_size = self.len().min(n);
221 let to_drop = ptr::slice_from_raw_parts_mut(self.ptr as *mut T, step_size);
222 if T::IS_ZST {
223 // See `next` for why we sub `end` here.
224 self.end = self.end.wrapping_byte_sub(step_size);
225 } else {
226 // SAFETY: the min() above ensures that step_size is in bounds
227 self.ptr = unsafe { self.ptr.add(step_size) };
228 }
229 // SAFETY: the min() above ensures that step_size is in bounds
230 unsafe {
231 ptr::drop_in_place(to_drop);
232 }
233 NonZeroUsize::new(n - step_size).map_or(Ok(()), Err)
234 }
235
236 #[inline]
237 fn count(self) -> usize {
238 self.len()
239 }
240
241 #[inline]
242 fn next_chunk<const N: usize>(&mut self) -> Result<[T; N], core::array::IntoIter<T, N>> {
243 let mut raw_ary = MaybeUninit::uninit_array();
244
245 let len = self.len();
246
247 if T::IS_ZST {
248 if len < N {
249 self.forget_remaining_elements();
250 // Safety: ZSTs can be conjured ex nihilo, only the amount has to be correct
251 return Err(unsafe { array::IntoIter::new_unchecked(raw_ary, 0..len) });
252 }
253
254 self.end = self.end.wrapping_byte_sub(N);
255 // Safety: ditto
256 return Ok(unsafe { raw_ary.transpose().assume_init() });
257 }
258
259 if len < N {
260 // Safety: `len` indicates that this many elements are available and we just checked that
261 // it fits into the array.
262 unsafe {
263 ptr::copy_nonoverlapping(self.ptr, raw_ary.as_mut_ptr() as *mut T, len);
264 self.forget_remaining_elements();
265 return Err(array::IntoIter::new_unchecked(raw_ary, 0..len));
266 }
267 }
268
269 // Safety: `len` is larger than the array size. Copy a fixed amount here to fully initialize
270 // the array.
271 return unsafe {
272 ptr::copy_nonoverlapping(self.ptr, raw_ary.as_mut_ptr() as *mut T, N);
273 self.ptr = self.ptr.add(N);
274 Ok(raw_ary.transpose().assume_init())
275 };
276 }
277
278 unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> Self::Item
279 where
280 Self: TrustedRandomAccessNoCoerce,
281 {
282 // SAFETY: the caller must guarantee that `i` is in bounds of the
283 // `Vec<T>`, so `i` cannot overflow an `isize`, and the `self.ptr.add(i)`
284 // is guaranteed to pointer to an element of the `Vec<T>` and
285 // thus guaranteed to be valid to dereference.
286 //
287 // Also note the implementation of `Self: TrustedRandomAccess` requires
288 // that `T: Copy` so reading elements from the buffer doesn't invalidate
289 // them for `Drop`.
290 unsafe {
291 if T::IS_ZST { mem::zeroed() } else { ptr::read(self.ptr.add(i)) }
292 }
293 }
294}
295
296#[stable(feature = "rust1", since = "1.0.0")]
297impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
298 #[inline]
299 fn next_back(&mut self) -> Option<T> {
300 if self.end == self.ptr {
301 None
302 } else if T::IS_ZST {
303 // See above for why 'ptr.offset' isn't used
304 self.end = self.end.wrapping_byte_sub(1);
305
306 // Make up a value of this ZST.
307 Some(unsafe { mem::zeroed() })
308 } else {
309 self.end = unsafe { self.end.sub(1) };
310
311 Some(unsafe { ptr::read(self.end) })
312 }
313 }
314
315 #[inline]
316 fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
317 let step_size = self.len().min(n);
318 if T::IS_ZST {
319 // SAFETY: same as for advance_by()
320 self.end = self.end.wrapping_byte_sub(step_size);
321 } else {
322 // SAFETY: same as for advance_by()
323 self.end = unsafe { self.end.sub(step_size) };
324 }
325 let to_drop = ptr::slice_from_raw_parts_mut(self.end as *mut T, step_size);
326 // SAFETY: same as for advance_by()
327 unsafe {
328 ptr::drop_in_place(to_drop);
329 }
330 NonZeroUsize::new(n - step_size).map_or(Ok(()), Err)
331 }
332}
333
334#[stable(feature = "rust1", since = "1.0.0")]
335impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {
336 fn is_empty(&self) -> bool {
337 self.ptr == self.end
338 }
339}
340
341#[stable(feature = "fused", since = "1.26.0")]
342impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}
343
344#[unstable(feature = "trusted_len", issue = "37572")]
345unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {}
346
347#[stable(feature = "default_iters", since = "1.70.0")]
348impl<T, A> Default for IntoIter<T, A>
349where
350 A: Allocator + Default,
351{
352 /// Creates an empty `vec::IntoIter`.
353 ///
354 /// ```
355 /// # use std::vec;
356 /// let iter: vec::IntoIter<u8> = Default::default();
357 /// assert_eq!(iter.len(), 0);
358 /// assert_eq!(iter.as_slice(), &[]);
359 /// ```
360 fn default() -> Self {
361 super::Vec::new_in(Default::default()).into_iter()
362 }
363}
364
365#[doc(hidden)]
366#[unstable(issue = "none", feature = "std_internals")]
367#[rustc_unsafe_specialization_marker]
368pub trait NonDrop {}
369
370// T: Copy as approximation for !Drop since get_unchecked does not advance self.ptr
371// and thus we can't implement drop-handling
372#[unstable(issue = "none", feature = "std_internals")]
373impl<T: Copy> NonDrop for T {}
374
375#[doc(hidden)]
376#[unstable(issue = "none", feature = "std_internals")]
377// TrustedRandomAccess (without NoCoerce) must not be implemented because
378// subtypes/supertypes of `T` might not be `NonDrop`
379unsafe impl<T, A: Allocator> TrustedRandomAccessNoCoerce for IntoIter<T, A>
380where
381 T: NonDrop,
382{
383 const MAY_HAVE_SIDE_EFFECT: bool = false;
384}
385
386#[cfg(not(no_global_oom_handling))]
387#[stable(feature = "vec_into_iter_clone", since = "1.8.0")]
388impl<T: Clone, A: Allocator + Clone> Clone for IntoIter<T, A> {
389 #[cfg(not(test))]
390 fn clone(&self) -> Self {
391 self.as_slice().to_vec_in(self.alloc.deref().clone()).into_iter()
392 }
393 #[cfg(test)]
394 fn clone(&self) -> Self {
395 crate::slice::to_vec(self.as_slice(), self.alloc.deref().clone()).into_iter()
396 }
397}
398
399#[stable(feature = "rust1", since = "1.0.0")]
400unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter<T, A> {
401 fn drop(&mut self) {
402 struct DropGuard<'a, T, A: Allocator>(&'a mut IntoIter<T, A>);
403
404 impl<T, A: Allocator> Drop for DropGuard<'_, T, A> {
405 fn drop(&mut self) {
406 unsafe {
407 // `IntoIter::alloc` is not used anymore after this and will be dropped by RawVec
408 let alloc = ManuallyDrop::take(&mut self.0.alloc);
409 // RawVec handles deallocation
410 let _ = RawVec::from_raw_parts_in(self.0.buf.as_ptr(), self.0.cap, alloc);
411 }
412 }
413 }
414
415 let guard = DropGuard(self);
416 // destroy the remaining elements
417 unsafe {
418 ptr::drop_in_place(guard.0.as_raw_mut_slice());
419 }
420 // now `guard` will be dropped and do the rest
421 }
422}
423
424// In addition to the SAFETY invariants of the following three unsafe traits
425// also refer to the vec::in_place_collect module documentation to get an overview
426#[unstable(issue = "none", feature = "inplace_iteration")]
427#[doc(hidden)]
428unsafe impl<T, A: Allocator> InPlaceIterable for IntoIter<T, A> {}
429
430#[unstable(issue = "none", feature = "inplace_iteration")]
431#[doc(hidden)]
432unsafe impl<T, A: Allocator> SourceIter for IntoIter<T, A> {
433 type Source = Self;
434
435 #[inline]
436 unsafe fn as_inner(&mut self) -> &mut Self::Source {
437 self
438 }
439}
440
441#[cfg(not(no_global_oom_handling))]
442unsafe impl<T> AsVecIntoIter for IntoIter<T> {
443 type Item = T;
444
445 fn as_into_iter(&mut self) -> &mut IntoIter<Self::Item> {
446 self
447 }
448}