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