1 // SPDX-License-Identifier: Apache-2.0 OR MIT
2 
3 #[cfg(not(no_global_oom_handling))]
4 use super::AsVecIntoIter;
5 use crate::alloc::{Allocator, Global};
6 #[cfg(not(no_global_oom_handling))]
7 use crate::collections::VecDeque;
8 use crate::raw_vec::RawVec;
9 use core::array;
10 use core::fmt;
11 use core::iter::{
12     FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccessNoCoerce,
13 };
14 use core::marker::PhantomData;
15 use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties};
16 use core::num::NonZeroUsize;
17 #[cfg(not(no_global_oom_handling))]
18 use core::ops::Deref;
19 use core::ptr::{self, NonNull};
20 use 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]
35 pub 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")]
52 impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result53     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
54         f.debug_tuple("IntoIter").field(&self.as_slice()).finish()
55     }
56 }
57 
58 impl<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")]
as_slice(&self) -> &[T]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")]
as_mut_slice(&mut self) -> &mut [T]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]
allocator(&self) -> &A96     pub fn allocator(&self) -> &A {
97         &self.alloc
98     }
99 
as_raw_mut_slice(&mut self) -> *mut [T]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))]
forget_allocation_drop_remaining(&mut self)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.
forget_remaining_elements(&mut self)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]
into_vecdeque(self) -> VecDeque<T, A>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")]
174 impl<T, A: Allocator> AsRef<[T]> for IntoIter<T, A> {
as_ref(&self) -> &[T]175     fn as_ref(&self) -> &[T] {
176         self.as_slice()
177     }
178 }
179 
180 #[stable(feature = "rust1", since = "1.0.0")]
181 unsafe impl<T: Send, A: Allocator + Send> Send for IntoIter<T, A> {}
182 #[stable(feature = "rust1", since = "1.0.0")]
183 unsafe impl<T: Sync, A: Allocator + Sync> Sync for IntoIter<T, A> {}
184 
185 #[stable(feature = "rust1", since = "1.0.0")]
186 impl<T, A: Allocator> Iterator for IntoIter<T, A> {
187     type Item = T;
188 
189     #[inline]
next(&mut self) -> Option<T>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]
size_hint(&self) -> (usize, Option<usize>)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]
advance_by(&mut self, n: usize) -> Result<(), NonZeroUsize>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]
count(self) -> usize237     fn count(self) -> usize {
238         self.len()
239     }
240 
241     #[inline]
next_chunk<const N: usize>(&mut self) -> Result<[T; N], core::array::IntoIter<T, N>>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 
__iterator_get_unchecked(&mut self, i: usize) -> Self::Item where Self: TrustedRandomAccessNoCoerce,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")]
297 impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
298     #[inline]
next_back(&mut self) -> Option<T>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]
advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize>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")]
335 impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {
is_empty(&self) -> bool336     fn is_empty(&self) -> bool {
337         self.ptr == self.end
338     }
339 }
340 
341 #[stable(feature = "fused", since = "1.26.0")]
342 impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}
343 
344 #[unstable(feature = "trusted_len", issue = "37572")]
345 unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {}
346 
347 #[stable(feature = "default_iters", since = "1.70.0")]
348 impl<T, A> Default for IntoIter<T, A>
349 where
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     /// ```
default() -> Self360     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]
368 pub 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")]
373 impl<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`
379 unsafe impl<T, A: Allocator> TrustedRandomAccessNoCoerce for IntoIter<T, A>
380 where
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")]
388 impl<T: Clone, A: Allocator + Clone> Clone for IntoIter<T, A> {
389     #[cfg(not(test))]
clone(&self) -> Self390     fn clone(&self) -> Self {
391         self.as_slice().to_vec_in(self.alloc.deref().clone()).into_iter()
392     }
393     #[cfg(test)]
clone(&self) -> Self394     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")]
400 unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter<T, A> {
drop(&mut self)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)]
428 unsafe impl<T, A: Allocator> InPlaceIterable for IntoIter<T, A> {}
429 
430 #[unstable(issue = "none", feature = "inplace_iteration")]
431 #[doc(hidden)]
432 unsafe impl<T, A: Allocator> SourceIter for IntoIter<T, A> {
433     type Source = Self;
434 
435     #[inline]
as_inner(&mut self) -> &mut Self::Source436     unsafe fn as_inner(&mut self) -> &mut Self::Source {
437         self
438     }
439 }
440 
441 #[cfg(not(no_global_oom_handling))]
442 unsafe impl<T> AsVecIntoIter for IntoIter<T> {
443     type Item = T;
444 
as_into_iter(&mut self) -> &mut IntoIter<Self::Item>445     fn as_into_iter(&mut self) -> &mut IntoIter<Self::Item> {
446         self
447     }
448 }
449