[rustc.git] / library / alloc / src / vec / drain.rs

use crate::alloc::{Allocator, Global};
use core::fmt;
use core::iter::{FusedIterator, TrustedLen};
use core::mem::{self, ManuallyDrop, SizedTypeProperties};
use core::ptr::{self, NonNull};
use core::slice::{self};

use super::Vec;

/// A draining iterator for `Vec<T>`.
///
/// This `struct` is created by [`Vec::drain`].
/// See its documentation for more.
///
/// # Example
///
/// ```
/// let mut v = vec![0, 1, 2];
/// let iter: std::vec::Drain<_> = v.drain(..);
/// ```
#[stable(feature = "drain", since = "1.6.0")]
pub struct Drain<
    'a,
    T: 'a,
    #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global,
> {
    /// Index of tail to preserve
    pub(super) tail_start: usize,
    /// Length of tail
    pub(super) tail_len: usize,
    /// Current remaining range to remove
    pub(super) iter: slice::Iter<'a, T>,
    pub(super) vec: NonNull<Vec<T, A>>,
}

#[stable(feature = "collection_debug", since = "1.17.0")]
impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
    }
}

impl<'a, T, A: Allocator> Drain<'a, T, A> {
    /// Returns the remaining items of this iterator as a slice.
    ///
    /// # Examples
    ///
    /// ```
    /// let mut vec = vec!['a', 'b', 'c'];
    /// let mut drain = vec.drain(..);
    /// assert_eq!(drain.as_slice(), &['a', 'b', 'c']);
    /// let _ = drain.next().unwrap();
    /// assert_eq!(drain.as_slice(), &['b', 'c']);
    /// ```
    #[must_use]
    #[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
    pub fn as_slice(&self) -> &[T] {
        self.iter.as_slice()
    }

    /// Returns a reference to the underlying allocator.
    #[unstable(feature = "allocator_api", issue = "32838")]
    #[must_use]
    #[inline]
    pub fn allocator(&self) -> &A {
        unsafe { self.vec.as_ref().allocator() }
    }

    /// Keep unyielded elements in the source `Vec`.
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(drain_keep_rest)]
    ///
    /// let mut vec = vec!['a', 'b', 'c'];
    /// let mut drain = vec.drain(..);
    ///
    /// assert_eq!(drain.next().unwrap(), 'a');
    ///
    /// // This call keeps 'b' and 'c' in the vec.
    /// drain.keep_rest();
    ///
    /// // If we wouldn't call `keep_rest()`,
    /// // `vec` would be empty.
    /// assert_eq!(vec, ['b', 'c']);
    /// ```
    #[unstable(feature = "drain_keep_rest", issue = "101122")]
    pub fn keep_rest(self) {
        // At this moment layout looks like this:
        //
        // [head] [yielded by next] [unyielded] [yielded by next_back] [tail]
        //        ^-- start         \_________/-- unyielded_len        \____/-- self.tail_len
        //                          ^-- unyielded_ptr                  ^-- tail
        //
        // Normally `Drop` impl would drop [unyielded] and then move [tail] to the `start`.
        // Here we want to
        // 1. Move [unyielded] to `start`
        // 2. Move [tail] to a new start at `start + len(unyielded)`
        // 3. Update length of the original vec to `len(head) + len(unyielded) + len(tail)`
        //    a. In case of ZST, this is the only thing we want to do
        // 4. Do *not* drop self, as everything is put in a consistent state already, there is nothing to do
        let mut this = ManuallyDrop::new(self);

        unsafe {
            let source_vec = this.vec.as_mut();

            let start = source_vec.len();
            let tail = this.tail_start;

            let unyielded_len = this.iter.len();
            let unyielded_ptr = this.iter.as_slice().as_ptr();

            // ZSTs have no identity, so we don't need to move them around.
            let needs_move = mem::size_of::<T>() != 0;

            if needs_move {
                let start_ptr = source_vec.as_mut_ptr().add(start);

                // memmove back unyielded elements
                if unyielded_ptr != start_ptr {
                    let src = unyielded_ptr;
                    let dst = start_ptr;

                    ptr::copy(src, dst, unyielded_len);
                }

                // memmove back untouched tail
                if tail != (start + unyielded_len) {
                    let src = source_vec.as_ptr().add(tail);
                    let dst = start_ptr.add(unyielded_len);
                    ptr::copy(src, dst, this.tail_len);
                }
            }

            source_vec.set_len(start + unyielded_len + this.tail_len);
        }
    }
}

#[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
impl<'a, T, A: Allocator> AsRef<[T]> for Drain<'a, T, A> {
    fn as_ref(&self) -> &[T] {
        self.as_slice()
    }
}

#[stable(feature = "drain", since = "1.6.0")]
unsafe impl<T: Sync, A: Sync + Allocator> Sync for Drain<'_, T, A> {}
#[stable(feature = "drain", since = "1.6.0")]
unsafe impl<T: Send, A: Send + Allocator> Send for Drain<'_, T, A> {}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> Iterator for Drain<'_, T, A> {
    type Item = T;

    #[inline]
    fn next(&mut self) -> Option<T> {
        self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) })
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> {
    #[inline]
    fn next_back(&mut self) -> Option<T> {
        self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) })
    }
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> Drop for Drain<'_, T, A> {
    fn drop(&mut self) {
        /// Moves back the un-`Drain`ed elements to restore the original `Vec`.
        struct DropGuard<'r, 'a, T, A: Allocator>(&'r mut Drain<'a, T, A>);

        impl<'r, 'a, T, A: Allocator> Drop for DropGuard<'r, 'a, T, A> {
            fn drop(&mut self) {
                if self.0.tail_len > 0 {
                    unsafe {
                        let source_vec = self.0.vec.as_mut();
                        // memmove back untouched tail, update to new length
                        let start = source_vec.len();
                        let tail = self.0.tail_start;
                        if tail != start {
                            let src = source_vec.as_ptr().add(tail);
                            let dst = source_vec.as_mut_ptr().add(start);
                            ptr::copy(src, dst, self.0.tail_len);
                        }
                        source_vec.set_len(start + self.0.tail_len);
                    }
                }
            }
        }

        let iter = mem::replace(&mut self.iter, (&mut []).iter());
        let drop_len = iter.len();

        let mut vec = self.vec;

        if T::IS_ZST {
            // ZSTs have no identity, so we don't need to move them around, we only need to drop the correct amount.
            // this can be achieved by manipulating the Vec length instead of moving values out from `iter`.
            unsafe {
                let vec = vec.as_mut();
                let old_len = vec.len();
                vec.set_len(old_len + drop_len + self.tail_len);
                vec.truncate(old_len + self.tail_len);
            }

            return;
        }

        // ensure elements are moved back into their appropriate places, even when drop_in_place panics
        let _guard = DropGuard(self);

        if drop_len == 0 {
            return;
        }

        // as_slice() must only be called when iter.len() is > 0 because
        // it also gets touched by vec::Splice which may turn it into a dangling pointer
        // which would make it and the vec pointer point to different allocations which would
        // lead to invalid pointer arithmetic below.
        let drop_ptr = iter.as_slice().as_ptr();

        unsafe {
            // drop_ptr comes from a slice::Iter which only gives us a &[T] but for drop_in_place
            // a pointer with mutable provenance is necessary. Therefore we must reconstruct
            // it from the original vec but also avoid creating a &mut to the front since that could
            // invalidate raw pointers to it which some unsafe code might rely on.
            let vec_ptr = vec.as_mut().as_mut_ptr();
            let drop_offset = drop_ptr.sub_ptr(vec_ptr);
            let to_drop = ptr::slice_from_raw_parts_mut(vec_ptr.add(drop_offset), drop_len);
            ptr::drop_in_place(to_drop);
        }
    }
}

#[stable(feature = "drain", since = "1.6.0")]
impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {
    fn is_empty(&self) -> bool {
        self.iter.is_empty()
    }
}

#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<T, A: Allocator> TrustedLen for Drain<'_, T, A> {}

#[stable(feature = "fused", since = "1.26.0")]
impl<T, A: Allocator> FusedIterator for Drain<'_, T, A> {}
Commit	Line	Data
5869c6ff XL	1	use crate::alloc::{Allocator, Global};
	2	use core::fmt;
	3	use core::iter::{FusedIterator, TrustedLen};
2b03887a	4	use core::mem::{self, ManuallyDrop, SizedTypeProperties};
5869c6ff XL	5	use core::ptr::{self, NonNull};
	6	use core::slice::{self};
	7
	8	use super::Vec;
	9
	10	/// A draining iterator for `Vec<T>`.
	11	///
	12	/// This `struct` is created by [`Vec::drain`].
	13	/// See its documentation for more.
	14	///
	15	/// # Example
	16	///
	17	/// ```
	18	/// let mut v = vec![0, 1, 2];
	19	/// let iter: std::vec::Drain<_> = v.drain(..);
	20	/// ```
	21	#[stable(feature = "drain", since = "1.6.0")]
	22	pub struct Drain<
	23	'a,
	24	T: 'a,
	25	#[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global,
	26	> {
	27	/// Index of tail to preserve
	28	pub(super) tail_start: usize,
	29	/// Length of tail
	30	pub(super) tail_len: usize,
	31	/// Current remaining range to remove
	32	pub(super) iter: slice::Iter<'a, T>,
	33	pub(super) vec: NonNull<Vec<T, A>>,
	34	}
	35
	36	#[stable(feature = "collection_debug", since = "1.17.0")]
	37	impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> {
	38	fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
	39	f.debug_tuple("Drain").field(&self.iter.as_slice()).finish()
	40	}
	41	}
	42
	43	impl<'a, T, A: Allocator> Drain<'a, T, A> {
	44	/// Returns the remaining items of this iterator as a slice.
	45	///
	46	/// # Examples
	47	///
	48	/// ```
	49	/// let mut vec = vec!['a', 'b', 'c'];
	50	/// let mut drain = vec.drain(..);
	51	/// assert_eq!(drain.as_slice(), &['a', 'b', 'c']);
	52	/// let _ = drain.next().unwrap();
	53	/// assert_eq!(drain.as_slice(), &['b', 'c']);
	54	/// ```
c295e0f8	55	#[must_use]
5869c6ff XL	56	#[stable(feature = "vec_drain_as_slice", since = "1.46.0")]
	57	pub fn as_slice(&self) -> &[T] {
	58	self.iter.as_slice()
	59	}
	60
	61	/// Returns a reference to the underlying allocator.
	62	#[unstable(feature = "allocator_api", issue = "32838")]
3c0e092e	63	#[must_use]
5869c6ff XL	64	#[inline]
	65	pub fn allocator(&self) -> &A {
	66	unsafe { self.vec.as_ref().allocator() }
	67	}
f2b60f7d FG	68
	69	/// Keep unyielded elements in the source `Vec`.
	70	///
	71	/// # Examples
	72	///
	73	/// ```
	74	/// #![feature(drain_keep_rest)]
	75	///
	76	/// let mut vec = vec!['a', 'b', 'c'];
	77	/// let mut drain = vec.drain(..);
	78	///
	79	/// assert_eq!(drain.next().unwrap(), 'a');
	80	///
	81	/// // This call keeps 'b' and 'c' in the vec.
	82	/// drain.keep_rest();
	83	///
	84	/// // If we wouldn't call `keep_rest()`,
	85	/// // `vec` would be empty.
	86	/// assert_eq!(vec, ['b', 'c']);
	87	/// ```
	88	#[unstable(feature = "drain_keep_rest", issue = "101122")]
	89	pub fn keep_rest(self) {
	90	// At this moment layout looks like this:
	91	//
	92	// [head] [yielded by next] [unyielded] [yielded by next_back] [tail]
	93	// ^-- start \_________/-- unyielded_len \____/-- self.tail_len
	94	// ^-- unyielded_ptr ^-- tail
	95	//
	96	// Normally `Drop` impl would drop [unyielded] and then move [tail] to the `start`.
	97	// Here we want to
	98	// 1. Move [unyielded] to `start`
	99	// 2. Move [tail] to a new start at `start + len(unyielded)`
	100	// 3. Update length of the original vec to `len(head) + len(unyielded) + len(tail)`
	101	// a. In case of ZST, this is the only thing we want to do
	102	// 4. Do not drop self, as everything is put in a consistent state already, there is nothing to do
	103	let mut this = ManuallyDrop::new(self);
	104
	105	unsafe {
	106	let source_vec = this.vec.as_mut();
	107
	108	let start = source_vec.len();
	109	let tail = this.tail_start;
	110
	111	let unyielded_len = this.iter.len();
	112	let unyielded_ptr = this.iter.as_slice().as_ptr();
	113
	114	// ZSTs have no identity, so we don't need to move them around.
	115	let needs_move = mem::size_of::<T>() != 0;
	116
	117	if needs_move {
	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	}
5869c6ff XL	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> {
	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]
	158	fn next(&mut self) -> Option<T> {
	159	self.iter.next().map(\|elt\| unsafe { ptr::read(elt as *const _) })
	160	}
	161
	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]
	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> {
	177	fn drop(&mut self) {
a2a8927a	178	/// Moves back the un-`Drain`ed elements to restore the original `Vec`.
5869c6ff XL	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) {
5869c6ff XL	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
a2a8927a XL	200	let iter = mem::replace(&mut self.iter, (&mut []).iter());
	201	let drop_len = iter.len();
	202
	203	let mut vec = self.vec;
	204
2b03887a	205	if T::IS_ZST {
a2a8927a XL	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;
5869c6ff XL	216	}
5869c6ff XL	217
a2a8927a XL	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
f25598a0 FG	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.
a2a8927a XL	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();
04454e1e	237	let drop_offset = drop_ptr.sub_ptr(vec_ptr);
a2a8927a XL	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	}
5869c6ff XL	241	}
	242	}
	243
	244	#[stable(feature = "drain", since = "1.6.0")]
	245	impl<T, A: Allocator> ExactSizeIterator for Drain<'_, T, A> {
	246	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> {}