From 5182776c6ceded22b79adc43e275b6b02111fe5b Mon Sep 17 00:00:00 2001 From: C Date: Fri, 4 Dec 2020 23:50:05 +0000 Subject: refactor: moving vec.rs to vec/mod.rs --- library/alloc/src/vec/mod.rs | 3725 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 3725 insertions(+) create mode 100644 library/alloc/src/vec/mod.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs new file mode 100644 index 00000000000..c9fa41138cd --- /dev/null +++ b/library/alloc/src/vec/mod.rs @@ -0,0 +1,3725 @@ +// ignore-tidy-filelength +//! A contiguous growable array type with heap-allocated contents, written +//! `Vec`. +//! +//! Vectors have `O(1)` indexing, amortized `O(1)` push (to the end) and +//! `O(1)` pop (from the end). +//! +//! Vectors ensure they never allocate more than `isize::MAX` bytes. +//! +//! # Examples +//! +//! You can explicitly create a [`Vec`] with [`Vec::new`]: +//! +//! ``` +//! let v: Vec = Vec::new(); +//! ``` +//! +//! ...or by using the [`vec!`] macro: +//! +//! ``` +//! let v: Vec = vec![]; +//! +//! let v = vec![1, 2, 3, 4, 5]; +//! +//! let v = vec![0; 10]; // ten zeroes +//! ``` +//! +//! You can [`push`] values onto the end of a vector (which will grow the vector +//! as needed): +//! +//! ``` +//! let mut v = vec![1, 2]; +//! +//! v.push(3); +//! ``` +//! +//! Popping values works in much the same way: +//! +//! ``` +//! let mut v = vec![1, 2]; +//! +//! let two = v.pop(); +//! ``` +//! +//! Vectors also support indexing (through the [`Index`] and [`IndexMut`] traits): +//! +//! ``` +//! let mut v = vec![1, 2, 3]; +//! let three = v[2]; +//! v[1] = v[1] + 5; +//! ``` +//! +//! [`push`]: Vec::push + +#![stable(feature = "rust1", since = "1.0.0")] + +use core::cmp::{self, Ordering}; +use core::convert::TryFrom; +use core::fmt; +use core::hash::{Hash, Hasher}; +use core::intrinsics::{arith_offset, assume}; +use core::iter::{ + FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccess, +}; +use core::marker::PhantomData; +use core::mem::{self, ManuallyDrop, MaybeUninit}; +use core::ops::{self, Index, IndexMut, Range, RangeBounds}; +use core::ptr::{self, NonNull}; +use core::slice::{self, SliceIndex}; + +use crate::alloc::{Allocator, Global}; +use crate::borrow::{Cow, ToOwned}; +use crate::boxed::Box; +use crate::collections::TryReserveError; +use crate::raw_vec::RawVec; + +/// A contiguous growable array type, written `Vec` but pronounced 'vector'. +/// +/// # Examples +/// +/// ``` +/// let mut vec = Vec::new(); +/// vec.push(1); +/// vec.push(2); +/// +/// assert_eq!(vec.len(), 2); +/// assert_eq!(vec[0], 1); +/// +/// assert_eq!(vec.pop(), Some(2)); +/// assert_eq!(vec.len(), 1); +/// +/// vec[0] = 7; +/// assert_eq!(vec[0], 7); +/// +/// vec.extend([1, 2, 3].iter().copied()); +/// +/// for x in &vec { +/// println!("{}", x); +/// } +/// assert_eq!(vec, [7, 1, 2, 3]); +/// ``` +/// +/// The [`vec!`] macro is provided to make initialization more convenient: +/// +/// ``` +/// let mut vec = vec![1, 2, 3]; +/// vec.push(4); +/// assert_eq!(vec, [1, 2, 3, 4]); +/// ``` +/// +/// It can also initialize each element of a `Vec` with a given value. +/// This may be more efficient than performing allocation and initialization +/// in separate steps, especially when initializing a vector of zeros: +/// +/// ``` +/// let vec = vec![0; 5]; +/// assert_eq!(vec, [0, 0, 0, 0, 0]); +/// +/// // The following is equivalent, but potentially slower: +/// let mut vec = Vec::with_capacity(5); +/// vec.resize(5, 0); +/// assert_eq!(vec, [0, 0, 0, 0, 0]); +/// ``` +/// +/// For more information, see +/// [Capacity and Reallocation](#capacity-and-reallocation). +/// +/// Use a `Vec` as an efficient stack: +/// +/// ``` +/// let mut stack = Vec::new(); +/// +/// stack.push(1); +/// stack.push(2); +/// stack.push(3); +/// +/// while let Some(top) = stack.pop() { +/// // Prints 3, 2, 1 +/// println!("{}", top); +/// } +/// ``` +/// +/// # Indexing +/// +/// The `Vec` type allows to access values by index, because it implements the +/// [`Index`] trait. An example will be more explicit: +/// +/// ``` +/// let v = vec![0, 2, 4, 6]; +/// println!("{}", v[1]); // it will display '2' +/// ``` +/// +/// However be careful: if you try to access an index which isn't in the `Vec`, +/// your software will panic! You cannot do this: +/// +/// ```should_panic +/// let v = vec![0, 2, 4, 6]; +/// println!("{}", v[6]); // it will panic! +/// ``` +/// +/// Use [`get`] and [`get_mut`] if you want to check whether the index is in +/// the `Vec`. +/// +/// # Slicing +/// +/// A `Vec` can be mutable. Slices, on the other hand, are read-only objects. +/// To get a [slice], use [`&`]. Example: +/// +/// ``` +/// fn read_slice(slice: &[usize]) { +/// // ... +/// } +/// +/// let v = vec![0, 1]; +/// read_slice(&v); +/// +/// // ... and that's all! +/// // you can also do it like this: +/// let u: &[usize] = &v; +/// // or like this: +/// let u: &[_] = &v; +/// ``` +/// +/// In Rust, it's more common to pass slices as arguments rather than vectors +/// when you just want to provide read access. The same goes for [`String`] and +/// [`&str`]. +/// +/// # Capacity and reallocation +/// +/// The capacity of a vector is the amount of space allocated for any future +/// elements that will be added onto the vector. This is not to be confused with +/// the *length* of a vector, which specifies the number of actual elements +/// within the vector. If a vector's length exceeds its capacity, its capacity +/// will automatically be increased, but its elements will have to be +/// reallocated. +/// +/// For example, a vector with capacity 10 and length 0 would be an empty vector +/// with space for 10 more elements. Pushing 10 or fewer elements onto the +/// vector will not change its capacity or cause reallocation to occur. However, +/// if the vector's length is increased to 11, it will have to reallocate, which +/// can be slow. For this reason, it is recommended to use [`Vec::with_capacity`] +/// whenever possible to specify how big the vector is expected to get. +/// +/// # Guarantees +/// +/// Due to its incredibly fundamental nature, `Vec` makes a lot of guarantees +/// about its design. This ensures that it's as low-overhead as possible in +/// the general case, and can be correctly manipulated in primitive ways +/// by unsafe code. Note that these guarantees refer to an unqualified `Vec`. +/// If additional type parameters are added (e.g., to support custom allocators), +/// overriding their defaults may change the behavior. +/// +/// Most fundamentally, `Vec` is and always will be a (pointer, capacity, length) +/// triplet. No more, no less. The order of these fields is completely +/// unspecified, and you should use the appropriate methods to modify these. +/// The pointer will never be null, so this type is null-pointer-optimized. +/// +/// However, the pointer may not actually point to allocated memory. In particular, +/// if you construct a `Vec` with capacity 0 via [`Vec::new`], [`vec![]`][`vec!`], +/// [`Vec::with_capacity(0)`][`Vec::with_capacity`], or by calling [`shrink_to_fit`] +/// on an empty Vec, it will not allocate memory. Similarly, if you store zero-sized +/// types inside a `Vec`, it will not allocate space for them. *Note that in this case +/// the `Vec` may not report a [`capacity`] of 0*. `Vec` will allocate if and only +/// if [`mem::size_of::`]`() * capacity() > 0`. In general, `Vec`'s allocation +/// details are very subtle — if you intend to allocate memory using a `Vec` +/// and use it for something else (either to pass to unsafe code, or to build your +/// own memory-backed collection), be sure to deallocate this memory by using +/// `from_raw_parts` to recover the `Vec` and then dropping it. +/// +/// If a `Vec` *has* allocated memory, then the memory it points to is on the heap +/// (as defined by the allocator Rust is configured to use by default), and its +/// pointer points to [`len`] initialized, contiguous elements in order (what +/// you would see if you coerced it to a slice), followed by [`capacity`]` - +/// `[`len`] logically uninitialized, contiguous elements. +/// +/// `Vec` will never perform a "small optimization" where elements are actually +/// stored on the stack for two reasons: +/// +/// * It would make it more difficult for unsafe code to correctly manipulate +/// a `Vec`. The contents of a `Vec` wouldn't have a stable address if it were +/// only moved, and it would be more difficult to determine if a `Vec` had +/// actually allocated memory. +/// +/// * It would penalize the general case, incurring an additional branch +/// on every access. +/// +/// `Vec` will never automatically shrink itself, even if completely empty. This +/// ensures no unnecessary allocations or deallocations occur. Emptying a `Vec` +/// and then filling it back up to the same [`len`] should incur no calls to +/// the allocator. If you wish to free up unused memory, use +/// [`shrink_to_fit`]. +/// +/// [`push`] and [`insert`] will never (re)allocate if the reported capacity is +/// sufficient. [`push`] and [`insert`] *will* (re)allocate if +/// [`len`]` == `[`capacity`]. That is, the reported capacity is completely +/// accurate, and can be relied on. It can even be used to manually free the memory +/// allocated by a `Vec` if desired. Bulk insertion methods *may* reallocate, even +/// when not necessary. +/// +/// `Vec` does not guarantee any particular growth strategy when reallocating +/// when full, nor when [`reserve`] is called. The current strategy is basic +/// and it may prove desirable to use a non-constant growth factor. Whatever +/// strategy is used will of course guarantee *O*(1) amortized [`push`]. +/// +/// `vec![x; n]`, `vec![a, b, c, d]`, and +/// [`Vec::with_capacity(n)`][`Vec::with_capacity`], will all produce a `Vec` +/// with exactly the requested capacity. If [`len`]` == `[`capacity`], +/// (as is the case for the [`vec!`] macro), then a `Vec` can be converted to +/// and from a [`Box<[T]>`][owned slice] without reallocating or moving the elements. +/// +/// `Vec` will not specifically overwrite any data that is removed from it, +/// but also won't specifically preserve it. Its uninitialized memory is +/// scratch space that it may use however it wants. It will generally just do +/// whatever is most efficient or otherwise easy to implement. Do not rely on +/// removed data to be erased for security purposes. Even if you drop a `Vec`, its +/// buffer may simply be reused by another `Vec`. Even if you zero a `Vec`'s memory +/// first, that may not actually happen because the optimizer does not consider +/// this a side-effect that must be preserved. There is one case which we will +/// not break, however: using `unsafe` code to write to the excess capacity, +/// and then increasing the length to match, is always valid. +/// +/// `Vec` does not currently guarantee the order in which elements are dropped. +/// The order has changed in the past and may change again. +/// +/// [`get`]: ../../std/vec/struct.Vec.html#method.get +/// [`get_mut`]: ../../std/vec/struct.Vec.html#method.get_mut +/// [`String`]: crate::string::String +/// [`&str`]: type@str +/// [`shrink_to_fit`]: Vec::shrink_to_fit +/// [`capacity`]: Vec::capacity +/// [`mem::size_of::`]: core::mem::size_of +/// [`len`]: Vec::len +/// [`push`]: Vec::push +/// [`insert`]: Vec::insert +/// [`reserve`]: Vec::reserve +/// [owned slice]: Box +/// [slice]: ../../std/primitive.slice.html +/// [`&`]: ../../std/primitive.reference.html +#[stable(feature = "rust1", since = "1.0.0")] +#[cfg_attr(not(test), rustc_diagnostic_item = "vec_type")] +pub struct Vec { + buf: RawVec, + len: usize, +} + +//////////////////////////////////////////////////////////////////////////////// +// Inherent methods +//////////////////////////////////////////////////////////////////////////////// + +impl Vec { + /// Constructs a new, empty `Vec`. + /// + /// The vector will not allocate until elements are pushed onto it. + /// + /// # Examples + /// + /// ``` + /// # #![allow(unused_mut)] + /// let mut vec: Vec = Vec::new(); + /// ``` + #[inline] + #[rustc_const_stable(feature = "const_vec_new", since = "1.39.0")] + #[stable(feature = "rust1", since = "1.0.0")] + pub const fn new() -> Self { + Vec { buf: RawVec::NEW, len: 0 } + } + + /// Constructs a new, empty `Vec` with the specified capacity. + /// + /// The vector will be able to hold exactly `capacity` elements without + /// reallocating. If `capacity` is 0, the vector will not allocate. + /// + /// It is important to note that although the returned vector has the + /// *capacity* specified, the vector will have a zero *length*. For an + /// explanation of the difference between length and capacity, see + /// *[Capacity and reallocation]*. + /// + /// [Capacity and reallocation]: #capacity-and-reallocation + /// + /// # Examples + /// + /// ``` + /// let mut vec = Vec::with_capacity(10); + /// + /// // The vector contains no items, even though it has capacity for more + /// assert_eq!(vec.len(), 0); + /// assert_eq!(vec.capacity(), 10); + /// + /// // These are all done without reallocating... + /// for i in 0..10 { + /// vec.push(i); + /// } + /// assert_eq!(vec.len(), 10); + /// assert_eq!(vec.capacity(), 10); + /// + /// // ...but this may make the vector reallocate + /// vec.push(11); + /// assert_eq!(vec.len(), 11); + /// assert!(vec.capacity() >= 11); + /// ``` + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn with_capacity(capacity: usize) -> Self { + Self::with_capacity_in(capacity, Global) + } + + /// Creates a `Vec` directly from the raw components of another vector. + /// + /// # Safety + /// + /// This is highly unsafe, due to the number of invariants that aren't + /// checked: + /// + /// * `ptr` needs to have been previously allocated via [`String`]/`Vec` + /// (at least, it's highly likely to be incorrect if it wasn't). + /// * `T` needs to have the same size and alignment as what `ptr` was allocated with. + /// (`T` having a less strict alignment is not sufficient, the alignment really + /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be + /// allocated and deallocated with the same layout.) + /// * `length` needs to be less than or equal to `capacity`. + /// * `capacity` needs to be the capacity that the pointer was allocated with. + /// + /// Violating these may cause problems like corrupting the allocator's + /// internal data structures. For example it is **not** safe + /// to build a `Vec` from a pointer to a C `char` array with length `size_t`. + /// It's also not safe to build one from a `Vec` and its length, because + /// the allocator cares about the alignment, and these two types have different + /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after + /// turning it into a `Vec` it'll be deallocated with alignment 1. + /// + /// The ownership of `ptr` is effectively transferred to the + /// `Vec` which may then deallocate, reallocate or change the + /// contents of memory pointed to by the pointer at will. Ensure + /// that nothing else uses the pointer after calling this + /// function. + /// + /// [`String`]: crate::string::String + /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc + /// + /// # Examples + /// + /// ``` + /// use std::ptr; + /// use std::mem; + /// + /// let v = vec![1, 2, 3]; + /// + // FIXME Update this when vec_into_raw_parts is stabilized + /// // Prevent running `v`'s destructor so we are in complete control + /// // of the allocation. + /// let mut v = mem::ManuallyDrop::new(v); + /// + /// // Pull out the various important pieces of information about `v` + /// let p = v.as_mut_ptr(); + /// let len = v.len(); + /// let cap = v.capacity(); + /// + /// unsafe { + /// // Overwrite memory with 4, 5, 6 + /// for i in 0..len as isize { + /// ptr::write(p.offset(i), 4 + i); + /// } + /// + /// // Put everything back together into a Vec + /// let rebuilt = Vec::from_raw_parts(p, len, cap); + /// assert_eq!(rebuilt, [4, 5, 6]); + /// } + /// ``` + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self { + unsafe { Self::from_raw_parts_in(ptr, length, capacity, Global) } + } +} + +impl Vec { + /// Constructs a new, empty `Vec`. + /// + /// The vector will not allocate until elements are pushed onto it. + /// + /// # Examples + /// + /// ``` + /// #![feature(allocator_api)] + /// + /// use std::alloc::System; + /// + /// # #[allow(unused_mut)] + /// let mut vec: Vec = Vec::new_in(System); + /// ``` + #[inline] + #[unstable(feature = "allocator_api", issue = "32838")] + pub const fn new_in(alloc: A) -> Self { + Vec { buf: RawVec::new_in(alloc), len: 0 } + } + + /// Constructs a new, empty `Vec` with the specified capacity with the provided + /// allocator. + /// + /// The vector will be able to hold exactly `capacity` elements without + /// reallocating. If `capacity` is 0, the vector will not allocate. + /// + /// It is important to note that although the returned vector has the + /// *capacity* specified, the vector will have a zero *length*. For an + /// explanation of the difference between length and capacity, see + /// *[Capacity and reallocation]*. + /// + /// [Capacity and reallocation]: #capacity-and-reallocation + /// + /// # Examples + /// + /// ``` + /// #![feature(allocator_api)] + /// + /// use std::alloc::System; + /// + /// let mut vec = Vec::with_capacity_in(10, System); + /// + /// // The vector contains no items, even though it has capacity for more + /// assert_eq!(vec.len(), 0); + /// assert_eq!(vec.capacity(), 10); + /// + /// // These are all done without reallocating... + /// for i in 0..10 { + /// vec.push(i); + /// } + /// assert_eq!(vec.len(), 10); + /// assert_eq!(vec.capacity(), 10); + /// + /// // ...but this may make the vector reallocate + /// vec.push(11); + /// assert_eq!(vec.len(), 11); + /// assert!(vec.capacity() >= 11); + /// ``` + #[inline] + #[unstable(feature = "allocator_api", issue = "32838")] + pub fn with_capacity_in(capacity: usize, alloc: A) -> Self { + Vec { buf: RawVec::with_capacity_in(capacity, alloc), len: 0 } + } + + /// Creates a `Vec` directly from the raw components of another vector. + /// + /// # Safety + /// + /// This is highly unsafe, due to the number of invariants that aren't + /// checked: + /// + /// * `ptr` needs to have been previously allocated via [`String`]/`Vec` + /// (at least, it's highly likely to be incorrect if it wasn't). + /// * `T` needs to have the same size and alignment as what `ptr` was allocated with. + /// (`T` having a less strict alignment is not sufficient, the alignment really + /// needs to be equal to satisfy the [`dealloc`] requirement that memory must be + /// allocated and deallocated with the same layout.) + /// * `length` needs to be less than or equal to `capacity`. + /// * `capacity` needs to be the capacity that the pointer was allocated with. + /// + /// Violating these may cause problems like corrupting the allocator's + /// internal data structures. For example it is **not** safe + /// to build a `Vec` from a pointer to a C `char` array with length `size_t`. + /// It's also not safe to build one from a `Vec` and its length, because + /// the allocator cares about the alignment, and these two types have different + /// alignments. The buffer was allocated with alignment 2 (for `u16`), but after + /// turning it into a `Vec` it'll be deallocated with alignment 1. + /// + /// The ownership of `ptr` is effectively transferred to the + /// `Vec` which may then deallocate, reallocate or change the + /// contents of memory pointed to by the pointer at will. Ensure + /// that nothing else uses the pointer after calling this + /// function. + /// + /// [`String`]: crate::string::String + /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc + /// + /// # Examples + /// + /// ``` + /// #![feature(allocator_api)] + /// + /// use std::alloc::System; + /// + /// use std::ptr; + /// use std::mem; + /// + /// let mut v = Vec::with_capacity_in(3, System); + /// v.push(1); + /// v.push(2); + /// v.push(3); + /// + // FIXME Update this when vec_into_raw_parts is stabilized + /// // Prevent running `v`'s destructor so we are in complete control + /// // of the allocation. + /// let mut v = mem::ManuallyDrop::new(v); + /// + /// // Pull out the various important pieces of information about `v` + /// let p = v.as_mut_ptr(); + /// let len = v.len(); + /// let cap = v.capacity(); + /// let alloc = v.allocator(); + /// + /// unsafe { + /// // Overwrite memory with 4, 5, 6 + /// for i in 0..len as isize { + /// ptr::write(p.offset(i), 4 + i); + /// } + /// + /// // Put everything back together into a Vec + /// let rebuilt = Vec::from_raw_parts_in(p, len, cap, alloc.clone()); + /// assert_eq!(rebuilt, [4, 5, 6]); + /// } + /// ``` + #[inline] + #[unstable(feature = "allocator_api", issue = "32838")] + pub unsafe fn from_raw_parts_in(ptr: *mut T, length: usize, capacity: usize, alloc: A) -> Self { + unsafe { Vec { buf: RawVec::from_raw_parts_in(ptr, capacity, alloc), len: length } } + } + + /// Decomposes a `Vec` into its raw components. + /// + /// Returns the raw pointer to the underlying data, the length of + /// the vector (in elements), and the allocated capacity of the + /// data (in elements). These are the same arguments in the same + /// order as the arguments to [`from_raw_parts`]. + /// + /// After calling this function, the caller is responsible for the + /// memory previously managed by the `Vec`. The only way to do + /// this is to convert the raw pointer, length, and capacity back + /// into a `Vec` with the [`from_raw_parts`] function, allowing + /// the destructor to perform the cleanup. + /// + /// [`from_raw_parts`]: Vec::from_raw_parts + /// + /// # Examples + /// + /// ``` + /// #![feature(vec_into_raw_parts)] + /// let v: Vec = vec![-1, 0, 1]; + /// + /// let (ptr, len, cap) = v.into_raw_parts(); + /// + /// let rebuilt = unsafe { + /// // We can now make changes to the components, such as + /// // transmuting the raw pointer to a compatible type. + /// let ptr = ptr as *mut u32; + /// + /// Vec::from_raw_parts(ptr, len, cap) + /// }; + /// assert_eq!(rebuilt, [4294967295, 0, 1]); + /// ``` + #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")] + pub fn into_raw_parts(self) -> (*mut T, usize, usize) { + let mut me = ManuallyDrop::new(self); + (me.as_mut_ptr(), me.len(), me.capacity()) + } + + /// Decomposes a `Vec` into its raw components. + /// + /// Returns the raw pointer to the underlying data, the length of the vector (in elements), + /// the allocated capacity of the data (in elements), and the allocator. These are the same + /// arguments in the same order as the arguments to [`from_raw_parts_in`]. + /// + /// After calling this function, the caller is responsible for the + /// memory previously managed by the `Vec`. The only way to do + /// this is to convert the raw pointer, length, and capacity back + /// into a `Vec` with the [`from_raw_parts_in`] function, allowing + /// the destructor to perform the cleanup. + /// + /// [`from_raw_parts_in`]: Vec::from_raw_parts_in + /// + /// # Examples + /// + /// ``` + /// #![feature(allocator_api, vec_into_raw_parts)] + /// + /// use std::alloc::System; + /// + /// let mut v: Vec = Vec::new_in(System); + /// v.push(-1); + /// v.push(0); + /// v.push(1); + /// + /// let (ptr, len, cap, alloc) = v.into_raw_parts_with_alloc(); + /// + /// let rebuilt = unsafe { + /// // We can now make changes to the components, such as + /// // transmuting the raw pointer to a compatible type. + /// let ptr = ptr as *mut u32; + /// + /// Vec::from_raw_parts_in(ptr, len, cap, alloc) + /// }; + /// assert_eq!(rebuilt, [4294967295, 0, 1]); + /// ``` + #[unstable(feature = "allocator_api", issue = "32838")] + // #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")] + pub fn into_raw_parts_with_alloc(self) -> (*mut T, usize, usize, A) { + let mut me = ManuallyDrop::new(self); + let len = me.len(); + let capacity = me.capacity(); + let ptr = me.as_mut_ptr(); + let alloc = unsafe { ptr::read(me.allocator()) }; + (ptr, len, capacity, alloc) + } + + /// Returns the number of elements the vector can hold without + /// reallocating. + /// + /// # Examples + /// + /// ``` + /// let vec: Vec = Vec::with_capacity(10); + /// assert_eq!(vec.capacity(), 10); + /// ``` + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn capacity(&self) -> usize { + self.buf.capacity() + } + + /// Reserves capacity for at least `additional` more elements to be inserted + /// in the given `Vec`. The collection may reserve more space to avoid + /// frequent reallocations. After calling `reserve`, capacity will be + /// greater than or equal to `self.len() + additional`. Does nothing if + /// capacity is already sufficient. + /// + /// # Panics + /// + /// Panics if the new capacity exceeds `isize::MAX` bytes. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1]; + /// vec.reserve(10); + /// assert!(vec.capacity() >= 11); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn reserve(&mut self, additional: usize) { + self.buf.reserve(self.len, additional); + } + + /// Reserves the minimum capacity for exactly `additional` more elements to + /// be inserted in the given `Vec`. After calling `reserve_exact`, + /// capacity will be greater than or equal to `self.len() + additional`. + /// Does nothing if the capacity is already sufficient. + /// + /// Note that the allocator may give the collection more space than it + /// requests. Therefore, capacity can not be relied upon to be precisely + /// minimal. Prefer `reserve` if future insertions are expected. + /// + /// # Panics + /// + /// Panics if the new capacity overflows `usize`. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1]; + /// vec.reserve_exact(10); + /// assert!(vec.capacity() >= 11); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn reserve_exact(&mut self, additional: usize) { + self.buf.reserve_exact(self.len, additional); + } + + /// Tries to reserve capacity for at least `additional` more elements to be inserted + /// in the given `Vec`. The collection may reserve more space to avoid + /// frequent reallocations. After calling `try_reserve`, capacity will be + /// greater than or equal to `self.len() + additional`. Does nothing if + /// capacity is already sufficient. + /// + /// # Errors + /// + /// If the capacity overflows, or the allocator reports a failure, then an error + /// is returned. + /// + /// # Examples + /// + /// ``` + /// #![feature(try_reserve)] + /// use std::collections::TryReserveError; + /// + /// fn process_data(data: &[u32]) -> Result, TryReserveError> { + /// let mut output = Vec::new(); + /// + /// // Pre-reserve the memory, exiting if we can't + /// output.try_reserve(data.len())?; + /// + /// // Now we know this can't OOM in the middle of our complex work + /// output.extend(data.iter().map(|&val| { + /// val * 2 + 5 // very complicated + /// })); + /// + /// Ok(output) + /// } + /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?"); + /// ``` + #[unstable(feature = "try_reserve", reason = "new API", issue = "48043")] + pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.buf.try_reserve(self.len, additional) + } + + /// Tries to reserve the minimum capacity for exactly `additional` + /// elements to be inserted in the given `Vec`. After calling + /// `try_reserve_exact`, capacity will be greater than or equal to + /// `self.len() + additional` if it returns `Ok(())`. + /// Does nothing if the capacity is already sufficient. + /// + /// Note that the allocator may give the collection more space than it + /// requests. Therefore, capacity can not be relied upon to be precisely + /// minimal. Prefer `reserve` if future insertions are expected. + /// + /// # Errors + /// + /// If the capacity overflows, or the allocator reports a failure, then an error + /// is returned. + /// + /// # Examples + /// + /// ``` + /// #![feature(try_reserve)] + /// use std::collections::TryReserveError; + /// + /// fn process_data(data: &[u32]) -> Result, TryReserveError> { + /// let mut output = Vec::new(); + /// + /// // Pre-reserve the memory, exiting if we can't + /// output.try_reserve_exact(data.len())?; + /// + /// // Now we know this can't OOM in the middle of our complex work + /// output.extend(data.iter().map(|&val| { + /// val * 2 + 5 // very complicated + /// })); + /// + /// Ok(output) + /// } + /// # process_data(&[1, 2, 3]).expect("why is the test harness OOMing on 12 bytes?"); + /// ``` + #[unstable(feature = "try_reserve", reason = "new API", issue = "48043")] + pub fn try_reserve_exact(&mut self, additional: usize) -> Result<(), TryReserveError> { + self.buf.try_reserve_exact(self.len, additional) + } + + /// Shrinks the capacity of the vector as much as possible. + /// + /// It will drop down as close as possible to the length but the allocator + /// may still inform the vector that there is space for a few more elements. + /// + /// # Examples + /// + /// ``` + /// let mut vec = Vec::with_capacity(10); + /// vec.extend([1, 2, 3].iter().cloned()); + /// assert_eq!(vec.capacity(), 10); + /// vec.shrink_to_fit(); + /// assert!(vec.capacity() >= 3); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn shrink_to_fit(&mut self) { + // The capacity is never less than the length, and there's nothing to do when + // they are equal, so we can avoid the panic case in `RawVec::shrink_to_fit` + // by only calling it with a greater capacity. + if self.capacity() > self.len { + self.buf.shrink_to_fit(self.len); + } + } + + /// Shrinks the capacity of the vector with a lower bound. + /// + /// The capacity will remain at least as large as both the length + /// and the supplied value. + /// + /// # Panics + /// + /// Panics if the current capacity is smaller than the supplied + /// minimum capacity. + /// + /// # Examples + /// + /// ``` + /// #![feature(shrink_to)] + /// let mut vec = Vec::with_capacity(10); + /// vec.extend([1, 2, 3].iter().cloned()); + /// assert_eq!(vec.capacity(), 10); + /// vec.shrink_to(4); + /// assert!(vec.capacity() >= 4); + /// vec.shrink_to(0); + /// assert!(vec.capacity() >= 3); + /// ``` + #[unstable(feature = "shrink_to", reason = "new API", issue = "56431")] + pub fn shrink_to(&mut self, min_capacity: usize) { + self.buf.shrink_to_fit(cmp::max(self.len, min_capacity)); + } + + /// Converts the vector into [`Box<[T]>`][owned slice]. + /// + /// Note that this will drop any excess capacity. + /// + /// [owned slice]: Box + /// + /// # Examples + /// + /// ``` + /// let v = vec![1, 2, 3]; + /// + /// let slice = v.into_boxed_slice(); + /// ``` + /// + /// Any excess capacity is removed: + /// + /// ``` + /// let mut vec = Vec::with_capacity(10); + /// vec.extend([1, 2, 3].iter().cloned()); + /// + /// assert_eq!(vec.capacity(), 10); + /// let slice = vec.into_boxed_slice(); + /// assert_eq!(slice.into_vec().capacity(), 3); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn into_boxed_slice(mut self) -> Box<[T], A> { + unsafe { + self.shrink_to_fit(); + let me = ManuallyDrop::new(self); + let buf = ptr::read(&me.buf); + let len = me.len(); + buf.into_box(len).assume_init() + } + } + + /// Shortens the vector, keeping the first `len` elements and dropping + /// the rest. + /// + /// If `len` is greater than the vector's current length, this has no + /// effect. + /// + /// The [`drain`] method can emulate `truncate`, but causes the excess + /// elements to be returned instead of dropped. + /// + /// Note that this method has no effect on the allocated capacity + /// of the vector. + /// + /// # Examples + /// + /// Truncating a five element vector to two elements: + /// + /// ``` + /// let mut vec = vec![1, 2, 3, 4, 5]; + /// vec.truncate(2); + /// assert_eq!(vec, [1, 2]); + /// ``` + /// + /// No truncation occurs when `len` is greater than the vector's current + /// length: + /// + /// ``` + /// let mut vec = vec![1, 2, 3]; + /// vec.truncate(8); + /// assert_eq!(vec, [1, 2, 3]); + /// ``` + /// + /// Truncating when `len == 0` is equivalent to calling the [`clear`] + /// method. + /// + /// ``` + /// let mut vec = vec![1, 2, 3]; + /// vec.truncate(0); + /// assert_eq!(vec, []); + /// ``` + /// + /// [`clear`]: Vec::clear + /// [`drain`]: Vec::drain + #[stable(feature = "rust1", since = "1.0.0")] + pub fn truncate(&mut self, len: usize) { + // This is safe because: + // + // * the slice passed to `drop_in_place` is valid; the `len > self.len` + // case avoids creating an invalid slice, and + // * the `len` of the vector is shrunk before calling `drop_in_place`, + // such that no value will be dropped twice in case `drop_in_place` + // were to panic once (if it panics twice, the program aborts). + unsafe { + if len > self.len { + return; + } + let remaining_len = self.len - len; + let s = ptr::slice_from_raw_parts_mut(self.as_mut_ptr().add(len), remaining_len); + self.len = len; + ptr::drop_in_place(s); + } + } + + /// Extracts a slice containing the entire vector. + /// + /// Equivalent to `&s[..]`. + /// + /// # Examples + /// + /// ``` + /// use std::io::{self, Write}; + /// let buffer = vec![1, 2, 3, 5, 8]; + /// io::sink().write(buffer.as_slice()).unwrap(); + /// ``` + #[inline] + #[stable(feature = "vec_as_slice", since = "1.7.0")] + pub fn as_slice(&self) -> &[T] { + self + } + + /// Extracts a mutable slice of the entire vector. + /// + /// Equivalent to `&mut s[..]`. + /// + /// # Examples + /// + /// ``` + /// use std::io::{self, Read}; + /// let mut buffer = vec![0; 3]; + /// io::repeat(0b101).read_exact(buffer.as_mut_slice()).unwrap(); + /// ``` + #[inline] + #[stable(feature = "vec_as_slice", since = "1.7.0")] + pub fn as_mut_slice(&mut self) -> &mut [T] { + self + } + + /// Returns a raw pointer to the vector's buffer. + /// + /// The caller must ensure that the vector outlives the pointer this + /// function returns, or else it will end up pointing to garbage. + /// Modifying the vector may cause its buffer to be reallocated, + /// which would also make any pointers to it invalid. + /// + /// The caller must also ensure that the memory the pointer (non-transitively) points to + /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer + /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`]. + /// + /// # Examples + /// + /// ``` + /// let x = vec![1, 2, 4]; + /// let x_ptr = x.as_ptr(); + /// + /// unsafe { + /// for i in 0..x.len() { + /// assert_eq!(*x_ptr.add(i), 1 << i); + /// } + /// } + /// ``` + /// + /// [`as_mut_ptr`]: Vec::as_mut_ptr + #[stable(feature = "vec_as_ptr", since = "1.37.0")] + #[inline] + pub fn as_ptr(&self) -> *const T { + // We shadow the slice method of the same name to avoid going through + // `deref`, which creates an intermediate reference. + let ptr = self.buf.ptr(); + unsafe { + assume(!ptr.is_null()); + } + ptr + } + + /// Returns an unsafe mutable pointer to the vector's buffer. + /// + /// The caller must ensure that the vector outlives the pointer this + /// function returns, or else it will end up pointing to garbage. + /// Modifying the vector may cause its buffer to be reallocated, + /// which would also make any pointers to it invalid. + /// + /// # Examples + /// + /// ``` + /// // Allocate vector big enough for 4 elements. + /// let size = 4; + /// let mut x: Vec = Vec::with_capacity(size); + /// let x_ptr = x.as_mut_ptr(); + /// + /// // Initialize elements via raw pointer writes, then set length. + /// unsafe { + /// for i in 0..size { + /// *x_ptr.add(i) = i as i32; + /// } + /// x.set_len(size); + /// } + /// assert_eq!(&*x, &[0, 1, 2, 3]); + /// ``` + #[stable(feature = "vec_as_ptr", since = "1.37.0")] + #[inline] + pub fn as_mut_ptr(&mut self) -> *mut T { + // We shadow the slice method of the same name to avoid going through + // `deref_mut`, which creates an intermediate reference. + let ptr = self.buf.ptr(); + unsafe { + assume(!ptr.is_null()); + } + ptr + } + + /// Returns a reference to the underlying allocator. + #[unstable(feature = "allocator_api", issue = "32838")] + #[inline] + pub fn allocator(&self) -> &A { + self.buf.allocator() + } + + /// Forces the length of the vector to `new_len`. + /// + /// This is a low-level operation that maintains none of the normal + /// invariants of the type. Normally changing the length of a vector + /// is done using one of the safe operations instead, such as + /// [`truncate`], [`resize`], [`extend`], or [`clear`]. + /// + /// [`truncate`]: Vec::truncate + /// [`resize`]: Vec::resize + /// [`extend`]: Extend::extend + /// [`clear`]: Vec::clear + /// + /// # Safety + /// + /// - `new_len` must be less than or equal to [`capacity()`]. + /// - The elements at `old_len..new_len` must be initialized. + /// + /// [`capacity()`]: Vec::capacity + /// + /// # Examples + /// + /// This method can be useful for situations in which the vector + /// is serving as a buffer for other code, particularly over FFI: + /// + /// ```no_run + /// # #![allow(dead_code)] + /// # // This is just a minimal skeleton for the doc example; + /// # // don't use this as a starting point for a real library. + /// # pub struct StreamWrapper { strm: *mut std::ffi::c_void } + /// # const Z_OK: i32 = 0; + /// # extern "C" { + /// # fn deflateGetDictionary( + /// # strm: *mut std::ffi::c_void, + /// # dictionary: *mut u8, + /// # dictLength: *mut usize, + /// # ) -> i32; + /// # } + /// # impl StreamWrapper { + /// pub fn get_dictionary(&self) -> Option> { + /// // Per the FFI method's docs, "32768 bytes is always enough". + /// let mut dict = Vec::with_capacity(32_768); + /// let mut dict_length = 0; + /// // SAFETY: When `deflateGetDictionary` returns `Z_OK`, it holds that: + /// // 1. `dict_length` elements were initialized. + /// // 2. `dict_length` <= the capacity (32_768) + /// // which makes `set_len` safe to call. + /// unsafe { + /// // Make the FFI call... + /// let r = deflateGetDictionary(self.strm, dict.as_mut_ptr(), &mut dict_length); + /// if r == Z_OK { + /// // ...and update the length to what was initialized. + /// dict.set_len(dict_length); + /// Some(dict) + /// } else { + /// None + /// } + /// } + /// } + /// # } + /// ``` + /// + /// While the following example is sound, there is a memory leak since + /// the inner vectors were not freed prior to the `set_len` call: + /// + /// ``` + /// let mut vec = vec![vec![1, 0, 0], + /// vec![0, 1, 0], + /// vec![0, 0, 1]]; + /// // SAFETY: + /// // 1. `old_len..0` is empty so no elements need to be initialized. + /// // 2. `0 <= capacity` always holds whatever `capacity` is. + /// unsafe { + /// vec.set_len(0); + /// } + /// ``` + /// + /// Normally, here, one would use [`clear`] instead to correctly drop + /// the contents and thus not leak memory. + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub unsafe fn set_len(&mut self, new_len: usize) { + debug_assert!(new_len <= self.capacity()); + + self.len = new_len; + } + + /// Removes an element from the vector and returns it. + /// + /// The removed element is replaced by the last element of the vector. + /// + /// This does not preserve ordering, but is O(1). + /// + /// # Panics + /// + /// Panics if `index` is out of bounds. + /// + /// # Examples + /// + /// ``` + /// let mut v = vec!["foo", "bar", "baz", "qux"]; + /// + /// assert_eq!(v.swap_remove(1), "bar"); + /// assert_eq!(v, ["foo", "qux", "baz"]); + /// + /// assert_eq!(v.swap_remove(0), "foo"); + /// assert_eq!(v, ["baz", "qux"]); + /// ``` + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn swap_remove(&mut self, index: usize) -> T { + #[cold] + #[inline(never)] + fn assert_failed(index: usize, len: usize) -> ! { + panic!("swap_remove index (is {}) should be < len (is {})", index, len); + } + + let len = self.len(); + if index >= len { + assert_failed(index, len); + } + unsafe { + // We replace self[index] with the last element. Note that if the + // bounds check above succeeds there must be a last element (which + // can be self[index] itself). + let last = ptr::read(self.as_ptr().add(len - 1)); + let hole = self.as_mut_ptr().add(index); + self.set_len(len - 1); + ptr::replace(hole, last) + } + } + + /// Inserts an element at position `index` within the vector, shifting all + /// elements after it to the right. + /// + /// # Panics + /// + /// Panics if `index > len`. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1, 2, 3]; + /// vec.insert(1, 4); + /// assert_eq!(vec, [1, 4, 2, 3]); + /// vec.insert(4, 5); + /// assert_eq!(vec, [1, 4, 2, 3, 5]); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn insert(&mut self, index: usize, element: T) { + #[cold] + #[inline(never)] + fn assert_failed(index: usize, len: usize) -> ! { + panic!("insertion index (is {}) should be <= len (is {})", index, len); + } + + let len = self.len(); + if index > len { + assert_failed(index, len); + } + + // space for the new element + if len == self.buf.capacity() { + self.reserve(1); + } + + unsafe { + // infallible + // The spot to put the new value + { + let p = self.as_mut_ptr().add(index); + // Shift everything over to make space. (Duplicating the + // `index`th element into two consecutive places.) + ptr::copy(p, p.offset(1), len - index); + // Write it in, overwriting the first copy of the `index`th + // element. + ptr::write(p, element); + } + self.set_len(len + 1); + } + } + + /// Removes and returns the element at position `index` within the vector, + /// shifting all elements after it to the left. + /// + /// # Panics + /// + /// Panics if `index` is out of bounds. + /// + /// # Examples + /// + /// ``` + /// let mut v = vec![1, 2, 3]; + /// assert_eq!(v.remove(1), 2); + /// assert_eq!(v, [1, 3]); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn remove(&mut self, index: usize) -> T { + #[cold] + #[inline(never)] + fn assert_failed(index: usize, len: usize) -> ! { + panic!("removal index (is {}) should be < len (is {})", index, len); + } + + let len = self.len(); + if index >= len { + assert_failed(index, len); + } + unsafe { + // infallible + let ret; + { + // the place we are taking from. + let ptr = self.as_mut_ptr().add(index); + // copy it out, unsafely having a copy of the value on + // the stack and in the vector at the same time. + ret = ptr::read(ptr); + + // Shift everything down to fill in that spot. + ptr::copy(ptr.offset(1), ptr, len - index - 1); + } + self.set_len(len - 1); + ret + } + } + + /// Retains only the elements specified by the predicate. + /// + /// In other words, remove all elements `e` such that `f(&e)` returns `false`. + /// This method operates in place, visiting each element exactly once in the + /// original order, and preserves the order of the retained elements. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1, 2, 3, 4]; + /// vec.retain(|&x| x % 2 == 0); + /// assert_eq!(vec, [2, 4]); + /// ``` + /// + /// The exact order may be useful for tracking external state, like an index. + /// + /// ``` + /// let mut vec = vec![1, 2, 3, 4, 5]; + /// let keep = [false, true, true, false, true]; + /// let mut i = 0; + /// vec.retain(|_| (keep[i], i += 1).0); + /// assert_eq!(vec, [2, 3, 5]); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn retain(&mut self, mut f: F) + where + F: FnMut(&T) -> bool, + { + let len = self.len(); + let mut del = 0; + { + let v = &mut **self; + + for i in 0..len { + if !f(&v[i]) { + del += 1; + } else if del > 0 { + v.swap(i - del, i); + } + } + } + if del > 0 { + self.truncate(len - del); + } + } + + /// Removes all but the first of consecutive elements in the vector that resolve to the same + /// key. + /// + /// If the vector is sorted, this removes all duplicates. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![10, 20, 21, 30, 20]; + /// + /// vec.dedup_by_key(|i| *i / 10); + /// + /// assert_eq!(vec, [10, 20, 30, 20]); + /// ``` + #[stable(feature = "dedup_by", since = "1.16.0")] + #[inline] + pub fn dedup_by_key(&mut self, mut key: F) + where + F: FnMut(&mut T) -> K, + K: PartialEq, + { + self.dedup_by(|a, b| key(a) == key(b)) + } + + /// Removes all but the first of consecutive elements in the vector satisfying a given equality + /// relation. + /// + /// The `same_bucket` function is passed references to two elements from the vector and + /// must determine if the elements compare equal. The elements are passed in opposite order + /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is removed. + /// + /// If the vector is sorted, this removes all duplicates. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec!["foo", "bar", "Bar", "baz", "bar"]; + /// + /// vec.dedup_by(|a, b| a.eq_ignore_ascii_case(b)); + /// + /// assert_eq!(vec, ["foo", "bar", "baz", "bar"]); + /// ``` + #[stable(feature = "dedup_by", since = "1.16.0")] + pub fn dedup_by(&mut self, same_bucket: F) + where + F: FnMut(&mut T, &mut T) -> bool, + { + let len = { + let (dedup, _) = self.as_mut_slice().partition_dedup_by(same_bucket); + dedup.len() + }; + self.truncate(len); + } + + /// Appends an element to the back of a collection. + /// + /// # Panics + /// + /// Panics if the new capacity exceeds `isize::MAX` bytes. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1, 2]; + /// vec.push(3); + /// assert_eq!(vec, [1, 2, 3]); + /// ``` + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn push(&mut self, value: T) { + // This will panic or abort if we would allocate > isize::MAX bytes + // or if the length increment would overflow for zero-sized types. + if self.len == self.buf.capacity() { + self.reserve(1); + } + unsafe { + let end = self.as_mut_ptr().add(self.len); + ptr::write(end, value); + self.len += 1; + } + } + + /// Removes the last element from a vector and returns it, or [`None`] if it + /// is empty. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1, 2, 3]; + /// assert_eq!(vec.pop(), Some(3)); + /// assert_eq!(vec, [1, 2]); + /// ``` + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn pop(&mut self) -> Option { + if self.len == 0 { + None + } else { + unsafe { + self.len -= 1; + Some(ptr::read(self.as_ptr().add(self.len()))) + } + } + } + + /// Moves all the elements of `other` into `Self`, leaving `other` empty. + /// + /// # Panics + /// + /// Panics if the number of elements in the vector overflows a `usize`. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1, 2, 3]; + /// let mut vec2 = vec![4, 5, 6]; + /// vec.append(&mut vec2); + /// assert_eq!(vec, [1, 2, 3, 4, 5, 6]); + /// assert_eq!(vec2, []); + /// ``` + #[inline] + #[stable(feature = "append", since = "1.4.0")] + pub fn append(&mut self, other: &mut Self) { + unsafe { + self.append_elements(other.as_slice() as _); + other.set_len(0); + } + } + + /// Appends elements to `Self` from other buffer. + #[inline] + unsafe fn append_elements(&mut self, other: *const [T]) { + let count = unsafe { (*other).len() }; + self.reserve(count); + let len = self.len(); + unsafe { ptr::copy_nonoverlapping(other as *const T, self.as_mut_ptr().add(len), count) }; + self.len += count; + } + + /// Creates a draining iterator that removes the specified range in the vector + /// and yields the removed items. + /// + /// When the iterator **is** dropped, all elements in the range are removed + /// from the vector, even if the iterator was not fully consumed. If the + /// iterator **is not** dropped (with [`mem::forget`] for example), it is + /// unspecified how many elements are removed. + /// + /// # Panics + /// + /// Panics if the starting point is greater than the end point or if + /// the end point is greater than the length of the vector. + /// + /// # Examples + /// + /// ``` + /// let mut v = vec![1, 2, 3]; + /// let u: Vec<_> = v.drain(1..).collect(); + /// assert_eq!(v, &[1]); + /// assert_eq!(u, &[2, 3]); + /// + /// // A full range clears the vector + /// v.drain(..); + /// assert_eq!(v, &[]); + /// ``` + #[stable(feature = "drain", since = "1.6.0")] + pub fn drain(&mut self, range: R) -> Drain<'_, T, A> + where + R: RangeBounds, + { + // Memory safety + // + // When the Drain is first created, it shortens the length of + // the source vector to make sure no uninitialized or moved-from elements + // are accessible at all if the Drain's destructor never gets to run. + // + // Drain will ptr::read out the values to remove. + // When finished, remaining tail of the vec is copied back to cover + // the hole, and the vector length is restored to the new length. + // + let len = self.len(); + let Range { start, end } = range.assert_len(len); + + unsafe { + // set self.vec length's to start, to be safe in case Drain is leaked + self.set_len(start); + // Use the borrow in the IterMut to indicate borrowing behavior of the + // whole Drain iterator (like &mut T). + let range_slice = slice::from_raw_parts_mut(self.as_mut_ptr().add(start), end - start); + Drain { + tail_start: end, + tail_len: len - end, + iter: range_slice.iter(), + vec: NonNull::from(self), + } + } + } + + /// Clears the vector, removing all values. + /// + /// Note that this method has no effect on the allocated capacity + /// of the vector. + /// + /// # Examples + /// + /// ``` + /// let mut v = vec![1, 2, 3]; + /// + /// v.clear(); + /// + /// assert!(v.is_empty()); + /// ``` + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn clear(&mut self) { + self.truncate(0) + } + + /// Returns the number of elements in the vector, also referred to + /// as its 'length'. + /// + /// # Examples + /// + /// ``` + /// let a = vec![1, 2, 3]; + /// assert_eq!(a.len(), 3); + /// ``` + #[doc(alias = "length")] + #[inline] + #[stable(feature = "rust1", since = "1.0.0")] + pub fn len(&self) -> usize { + self.len + } + + /// Returns `true` if the vector contains no elements. + /// + /// # Examples + /// + /// ``` + /// let mut v = Vec::new(); + /// assert!(v.is_empty()); + /// + /// v.push(1); + /// assert!(!v.is_empty()); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + pub fn is_empty(&self) -> bool { + self.len() == 0 + } + + /// Splits the collection into two at the given index. + /// + /// Returns a newly allocated vector containing the elements in the range + /// `[at, len)`. After the call, the original vector will be left containing + /// the elements `[0, at)` with its previous capacity unchanged. + /// + /// # Panics + /// + /// Panics if `at > len`. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1, 2, 3]; + /// let vec2 = vec.split_off(1); + /// assert_eq!(vec, [1]); + /// assert_eq!(vec2, [2, 3]); + /// ``` + #[inline] + #[must_use = "use `.truncate()` if you don't need the other half"] + #[stable(feature = "split_off", since = "1.4.0")] + pub fn split_off(&mut self, at: usize) -> Self + where + A: Clone, + { + #[cold] + #[inline(never)] + fn assert_failed(at: usize, len: usize) -> ! { + panic!("`at` split index (is {}) should be <= len (is {})", at, len); + } + + if at > self.len() { + assert_failed(at, self.len()); + } + + if at == 0 { + // the new vector can take over the original buffer and avoid the copy + return mem::replace( + self, + Vec::with_capacity_in(self.capacity(), self.allocator().clone()), + ); + } + + let other_len = self.len - at; + let mut other = Vec::with_capacity_in(other_len, self.allocator().clone()); + + // Unsafely `set_len` and copy items to `other`. + unsafe { + self.set_len(at); + other.set_len(other_len); + + ptr::copy_nonoverlapping(self.as_ptr().add(at), other.as_mut_ptr(), other.len()); + } + other + } + + /// Resizes the `Vec` in-place so that `len` is equal to `new_len`. + /// + /// If `new_len` is greater than `len`, the `Vec` is extended by the + /// difference, with each additional slot filled with the result of + /// calling the closure `f`. The return values from `f` will end up + /// in the `Vec` in the order they have been generated. + /// + /// If `new_len` is less than `len`, the `Vec` is simply truncated. + /// + /// This method uses a closure to create new values on every push. If + /// you'd rather [`Clone`] a given value, use [`Vec::resize`]. If you + /// want to use the [`Default`] trait to generate values, you can + /// pass [`Default::default`] as the second argument. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1, 2, 3]; + /// vec.resize_with(5, Default::default); + /// assert_eq!(vec, [1, 2, 3, 0, 0]); + /// + /// let mut vec = vec![]; + /// let mut p = 1; + /// vec.resize_with(4, || { p *= 2; p }); + /// assert_eq!(vec, [2, 4, 8, 16]); + /// ``` + #[stable(feature = "vec_resize_with", since = "1.33.0")] + pub fn resize_with(&mut self, new_len: usize, f: F) + where + F: FnMut() -> T, + { + let len = self.len(); + if new_len > len { + self.extend_with(new_len - len, ExtendFunc(f)); + } else { + self.truncate(new_len); + } + } + + /// Consumes and leaks the `Vec`, returning a mutable reference to the contents, + /// `&'a mut [T]`. Note that the type `T` must outlive the chosen lifetime + /// `'a`. If the type has only static references, or none at all, then this + /// may be chosen to be `'static`. + /// + /// This function is similar to the [`leak`][Box::leak] function on [`Box`] + /// except that there is no way to recover the leaked memory. + /// + /// This function is mainly useful for data that lives for the remainder of + /// the program's life. Dropping the returned reference will cause a memory + /// leak. + /// + /// # Examples + /// + /// Simple usage: + /// + /// ``` + /// let x = vec![1, 2, 3]; + /// let static_ref: &'static mut [usize] = x.leak(); + /// static_ref[0] += 1; + /// assert_eq!(static_ref, &[2, 2, 3]); + /// ``` + #[stable(feature = "vec_leak", since = "1.47.0")] + #[inline] + pub fn leak<'a>(self) -> &'a mut [T] + where + A: 'a, + { + Box::leak(self.into_boxed_slice()) + } + + /// Returns the remaining spare capacity of the vector as a slice of + /// `MaybeUninit`. + /// + /// The returned slice can be used to fill the vector with data (e.g. by + /// reading from a file) before marking the data as initialized using the + /// [`set_len`] method. + /// + /// [`set_len`]: Vec::set_len + /// + /// # Examples + /// + /// ``` + /// #![feature(vec_spare_capacity, maybe_uninit_extra)] + /// + /// // Allocate vector big enough for 10 elements. + /// let mut v = Vec::with_capacity(10); + /// + /// // Fill in the first 3 elements. + /// let uninit = v.spare_capacity_mut(); + /// uninit[0].write(0); + /// uninit[1].write(1); + /// uninit[2].write(2); + /// + /// // Mark the first 3 elements of the vector as being initialized. + /// unsafe { + /// v.set_len(3); + /// } + /// + /// assert_eq!(&v, &[0, 1, 2]); + /// ``` + #[unstable(feature = "vec_spare_capacity", issue = "75017")] + #[inline] + pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit] { + unsafe { + slice::from_raw_parts_mut( + self.as_mut_ptr().add(self.len) as *mut MaybeUninit, + self.buf.capacity() - self.len, + ) + } + } +} + +impl Vec { + /// Resizes the `Vec` in-place so that `len` is equal to `new_len`. + /// + /// If `new_len` is greater than `len`, the `Vec` is extended by the + /// difference, with each additional slot filled with `value`. + /// If `new_len` is less than `len`, the `Vec` is simply truncated. + /// + /// This method requires `T` to implement [`Clone`], + /// in order to be able to clone the passed value. + /// If you need more flexibility (or want to rely on [`Default`] instead of + /// [`Clone`]), use [`Vec::resize_with`]. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec!["hello"]; + /// vec.resize(3, "world"); + /// assert_eq!(vec, ["hello", "world", "world"]); + /// + /// let mut vec = vec![1, 2, 3, 4]; + /// vec.resize(2, 0); + /// assert_eq!(vec, [1, 2]); + /// ``` + #[stable(feature = "vec_resize", since = "1.5.0")] + pub fn resize(&mut self, new_len: usize, value: T) { + let len = self.len(); + + if new_len > len { + self.extend_with(new_len - len, ExtendElement(value)) + } else { + self.truncate(new_len); + } + } + + /// Clones and appends all elements in a slice to the `Vec`. + /// + /// Iterates over the slice `other`, clones each element, and then appends + /// it to this `Vec`. The `other` vector is traversed in-order. + /// + /// Note that this function is same as [`extend`] except that it is + /// specialized to work with slices instead. If and when Rust gets + /// specialization this function will likely be deprecated (but still + /// available). + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1]; + /// vec.extend_from_slice(&[2, 3, 4]); + /// assert_eq!(vec, [1, 2, 3, 4]); + /// ``` + /// + /// [`extend`]: Vec::extend + #[stable(feature = "vec_extend_from_slice", since = "1.6.0")] + pub fn extend_from_slice(&mut self, other: &[T]) { + self.spec_extend(other.iter()) + } +} + +// This code generalizes `extend_with_{element,default}`. +trait ExtendWith { + fn next(&mut self) -> T; + fn last(self) -> T; +} + +struct ExtendElement(T); +impl ExtendWith for ExtendElement { + fn next(&mut self) -> T { + self.0.clone() + } + fn last(self) -> T { + self.0 + } +} + +struct ExtendDefault; +impl ExtendWith for ExtendDefault { + fn next(&mut self) -> T { + Default::default() + } + fn last(self) -> T { + Default::default() + } +} + +struct ExtendFunc(F); +impl T> ExtendWith for ExtendFunc { + fn next(&mut self) -> T { + (self.0)() + } + fn last(mut self) -> T { + (self.0)() + } +} + +impl Vec { + /// Extend the vector by `n` values, using the given generator. + fn extend_with>(&mut self, n: usize, mut value: E) { + self.reserve(n); + + unsafe { + let mut ptr = self.as_mut_ptr().add(self.len()); + // Use SetLenOnDrop to work around bug where compiler + // may not realize the store through `ptr` through self.set_len() + // don't alias. + let mut local_len = SetLenOnDrop::new(&mut self.len); + + // Write all elements except the last one + for _ in 1..n { + ptr::write(ptr, value.next()); + ptr = ptr.offset(1); + // Increment the length in every step in case next() panics + local_len.increment_len(1); + } + + if n > 0 { + // We can write the last element directly without cloning needlessly + ptr::write(ptr, value.last()); + local_len.increment_len(1); + } + + // len set by scope guard + } + } +} + +// Set the length of the vec when the `SetLenOnDrop` value goes out of scope. +// +// The idea is: The length field in SetLenOnDrop is a local variable +// that the optimizer will see does not alias with any stores through the Vec's data +// pointer. This is a workaround for alias analysis issue #32155 +struct SetLenOnDrop<'a> { + len: &'a mut usize, + local_len: usize, +} + +impl<'a> SetLenOnDrop<'a> { + #[inline] + fn new(len: &'a mut usize) -> Self { + SetLenOnDrop { local_len: *len, len } + } + + #[inline] + fn increment_len(&mut self, increment: usize) { + self.local_len += increment; + } +} + +impl Drop for SetLenOnDrop<'_> { + #[inline] + fn drop(&mut self) { + *self.len = self.local_len; + } +} + +impl Vec { + /// Removes consecutive repeated elements in the vector according to the + /// [`PartialEq`] trait implementation. + /// + /// If the vector is sorted, this removes all duplicates. + /// + /// # Examples + /// + /// ``` + /// let mut vec = vec![1, 2, 2, 3, 2]; + /// + /// vec.dedup(); + /// + /// assert_eq!(vec, [1, 2, 3, 2]); + /// ``` + #[stable(feature = "rust1", since = "1.0.0")] + #[inline] + pub fn dedup(&mut self) { + self.dedup_by(|a, b| a == b) + } +} + +impl Vec { + /// Removes the first instance of `item` from the vector if the item exists. + /// + /// This method will be removed soon. + #[unstable(feature = "vec_remove_item", reason = "recently added", issue = "40062")] + #[rustc_deprecated( + reason = "Removing the first item equal to a needle is already easily possible \ + with iterators and the current Vec methods. Furthermore, having a method for \ + one particular case of removal (linear search, only the first item, no swap remove) \ + but not for others is inconsistent. This method will be removed soon.", + since = "1.46.0" + )] + pub fn remove_item(&mut self, item: &V) -> Option + where + T: PartialEq, + { + let pos = self.iter().position(|x| *x == *item)?; + Some(self.remove(pos)) + } +} + +//////////////////////////////////////////////////////////////////////////////// +// Internal methods and functions +//////////////////////////////////////////////////////////////////////////////// + +#[doc(hidden)] +#[stable(feature = "rust1", since = "1.0.0")] +pub fn from_elem(elem: T, n: usize) -> Vec { + ::from_elem(elem, n, Global) +} + +#[doc(hidden)] +#[unstable(feature = "allocator_api", issue = "32838")] +pub fn from_elem_in(elem: T, n: usize, alloc: A) -> Vec { + ::from_elem(elem, n, alloc) +} + +// Specialization trait used for Vec::from_elem +trait SpecFromElem: Sized { + fn from_elem(elem: Self, n: usize, alloc: A) -> Vec; +} + +impl SpecFromElem for T { + default fn from_elem(elem: Self, n: usize, alloc: A) -> Vec { + let mut v = Vec::with_capacity_in(n, alloc); + v.extend_with(n, ExtendElement(elem)); + v + } +} + +impl SpecFromElem for i8 { + #[inline] + fn from_elem(elem: i8, n: usize, alloc: A) -> Vec { + if elem == 0 { + return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; + } + unsafe { + let mut v = Vec::with_capacity_in(n, alloc); + ptr::write_bytes(v.as_mut_ptr(), elem as u8, n); + v.set_len(n); + v + } + } +} + +impl SpecFromElem for u8 { + #[inline] + fn from_elem(elem: u8, n: usize, alloc: A) -> Vec { + if elem == 0 { + return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; + } + unsafe { + let mut v = Vec::with_capacity_in(n, alloc); + ptr::write_bytes(v.as_mut_ptr(), elem, n); + v.set_len(n); + v + } + } +} + +impl SpecFromElem for T { + #[inline] + fn from_elem(elem: T, n: usize, alloc: A) -> Vec { + if elem.is_zero() { + return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; + } + let mut v = Vec::with_capacity_in(n, alloc); + v.extend_with(n, ExtendElement(elem)); + v + } +} + +#[rustc_specialization_trait] +unsafe trait IsZero { + /// Whether this value is zero + fn is_zero(&self) -> bool; +} + +macro_rules! impl_is_zero { + ($t:ty, $is_zero:expr) => { + unsafe impl IsZero for $t { + #[inline] + fn is_zero(&self) -> bool { + $is_zero(*self) + } + } + }; +} + +impl_is_zero!(i16, |x| x == 0); +impl_is_zero!(i32, |x| x == 0); +impl_is_zero!(i64, |x| x == 0); +impl_is_zero!(i128, |x| x == 0); +impl_is_zero!(isize, |x| x == 0); + +impl_is_zero!(u16, |x| x == 0); +impl_is_zero!(u32, |x| x == 0); +impl_is_zero!(u64, |x| x == 0); +impl_is_zero!(u128, |x| x == 0); +impl_is_zero!(usize, |x| x == 0); + +impl_is_zero!(bool, |x| x == false); +impl_is_zero!(char, |x| x == '\0'); + +impl_is_zero!(f32, |x: f32| x.to_bits() == 0); +impl_is_zero!(f64, |x: f64| x.to_bits() == 0); + +unsafe impl IsZero for *const T { + #[inline] + fn is_zero(&self) -> bool { + (*self).is_null() + } +} + +unsafe impl IsZero for *mut T { + #[inline] + fn is_zero(&self) -> bool { + (*self).is_null() + } +} + +// `Option<&T>` and `Option>` are guaranteed to represent `None` as null. +// For fat pointers, the bytes that would be the pointer metadata in the `Some` +// variant are padding in the `None` variant, so ignoring them and +// zero-initializing instead is ok. +// `Option<&mut T>` never implements `Clone`, so there's no need for an impl of +// `SpecFromElem`. + +unsafe impl IsZero for Option<&T> { + #[inline] + fn is_zero(&self) -> bool { + self.is_none() + } +} + +unsafe impl IsZero for Option> { + #[inline] + fn is_zero(&self) -> bool { + self.is_none() + } +} + +//////////////////////////////////////////////////////////////////////////////// +// Common trait implementations for Vec +//////////////////////////////////////////////////////////////////////////////// + +#[stable(feature = "rust1", since = "1.0.0")] +impl ops::Deref for Vec { + type Target = [T]; + + fn deref(&self) -> &[T] { + unsafe { slice::from_raw_parts(self.as_ptr(), self.len) } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ops::DerefMut for Vec { + fn deref_mut(&mut self) -> &mut [T] { + unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Clone for Vec { + #[cfg(not(test))] + fn clone(&self) -> Self { + let alloc = self.allocator().clone(); + <[T]>::to_vec_in(&**self, alloc) + } + + // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is + // required for this method definition, is not available. Instead use the + // `slice::to_vec` function which is only available with cfg(test) + // NB see the slice::hack module in slice.rs for more information + #[cfg(test)] + fn clone(&self) -> Self { + let alloc = self.allocator().clone(); + crate::slice::to_vec(&**self, alloc) + } + + fn clone_from(&mut self, other: &Self) { + // drop anything that will not be overwritten + self.truncate(other.len()); + + // self.len <= other.len due to the truncate above, so the + // slices here are always in-bounds. + let (init, tail) = other.split_at(self.len()); + + // reuse the contained values' allocations/resources. + self.clone_from_slice(init); + self.extend_from_slice(tail); + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Hash for Vec { + #[inline] + fn hash(&self, state: &mut H) { + Hash::hash(&**self, state) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +#[rustc_on_unimplemented( + message = "vector indices are of type `usize` or ranges of `usize`", + label = "vector indices are of type `usize` or ranges of `usize`" +)] +impl, A: Allocator> Index for Vec { + type Output = I::Output; + + #[inline] + fn index(&self, index: I) -> &Self::Output { + Index::index(&**self, index) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +#[rustc_on_unimplemented( + message = "vector indices are of type `usize` or ranges of `usize`", + label = "vector indices are of type `usize` or ranges of `usize`" +)] +impl, A: Allocator> IndexMut for Vec { + #[inline] + fn index_mut(&mut self, index: I) -> &mut Self::Output { + IndexMut::index_mut(&mut **self, index) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl FromIterator for Vec { + #[inline] + fn from_iter>(iter: I) -> Vec { + >::from_iter(iter.into_iter()) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl IntoIterator for Vec { + type Item = T; + type IntoIter = IntoIter; + + /// Creates a consuming iterator, that is, one that moves each value out of + /// the vector (from start to end). The vector cannot be used after calling + /// this. + /// + /// # Examples + /// + /// ``` + /// let v = vec!["a".to_string(), "b".to_string()]; + /// for s in v.into_iter() { + /// // s has type String, not &String + /// println!("{}", s); + /// } + /// ``` + #[inline] + fn into_iter(self) -> IntoIter { + unsafe { + let mut me = ManuallyDrop::new(self); + let alloc = ptr::read(me.allocator()); + let begin = me.as_mut_ptr(); + let end = if mem::size_of::() == 0 { + arith_offset(begin as *const i8, me.len() as isize) as *const T + } else { + begin.add(me.len()) as *const T + }; + let cap = me.buf.capacity(); + IntoIter { + buf: NonNull::new_unchecked(begin), + phantom: PhantomData, + cap, + alloc, + ptr: begin, + end, + } + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T, A: Allocator> IntoIterator for &'a Vec { + type Item = &'a T; + type IntoIter = slice::Iter<'a, T>; + + fn into_iter(self) -> slice::Iter<'a, T> { + self.iter() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec { + type Item = &'a mut T; + type IntoIter = slice::IterMut<'a, T>; + + fn into_iter(self) -> slice::IterMut<'a, T> { + self.iter_mut() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Extend for Vec { + #[inline] + fn extend>(&mut self, iter: I) { + >::spec_extend(self, iter.into_iter()) + } + + #[inline] + fn extend_one(&mut self, item: T) { + self.push(item); + } + + #[inline] + fn extend_reserve(&mut self, additional: usize) { + self.reserve(additional); + } +} + +/// Specialization trait used for Vec::from_iter +/// +/// ## The delegation graph: +/// +/// ```text +/// +-------------+ +/// |FromIterator | +/// +-+-----------+ +/// | +/// v +/// +-+-------------------------------+ +---------------------+ +/// |SpecFromIter +---->+SpecFromIterNested | +/// |where I: | | |where I: | +/// | Iterator (default)----------+ | | Iterator (default) | +/// | vec::IntoIter | | | TrustedLen | +/// | SourceIterMarker---fallback-+ | | | +/// | slice::Iter | | | +/// | Iterator | +---------------------+ +/// +---------------------------------+ +/// ``` +trait SpecFromIter { + fn from_iter(iter: I) -> Self; +} + +/// Another specialization trait for Vec::from_iter +/// necessary to manually prioritize overlapping specializations +/// see [`SpecFromIter`] for details. +trait SpecFromIterNested { + fn from_iter(iter: I) -> Self; +} + +impl SpecFromIterNested for Vec +where + I: Iterator, +{ + default fn from_iter(mut iterator: I) -> Self { + // Unroll the first iteration, as the vector is going to be + // expanded on this iteration in every case when the iterable is not + // empty, but the loop in extend_desugared() is not going to see the + // vector being full in the few subsequent loop iterations. + // So we get better branch prediction. + let mut vector = match iterator.next() { + None => return Vec::new(), + Some(element) => { + let (lower, _) = iterator.size_hint(); + let mut vector = Vec::with_capacity(lower.saturating_add(1)); + unsafe { + ptr::write(vector.as_mut_ptr(), element); + vector.set_len(1); + } + vector + } + }; + // must delegate to spec_extend() since extend() itself delegates + // to spec_from for empty Vecs + as SpecExtend>::spec_extend(&mut vector, iterator); + vector + } +} + +impl SpecFromIterNested for Vec +where + I: TrustedLen, +{ + fn from_iter(iterator: I) -> Self { + let mut vector = match iterator.size_hint() { + (_, Some(upper)) => Vec::with_capacity(upper), + _ => Vec::new(), + }; + // must delegate to spec_extend() since extend() itself delegates + // to spec_from for empty Vecs + vector.spec_extend(iterator); + vector + } +} + +impl SpecFromIter for Vec +where + I: Iterator, +{ + default fn from_iter(iterator: I) -> Self { + SpecFromIterNested::from_iter(iterator) + } +} + +// A helper struct for in-place iteration that drops the destination slice of iteration, +// i.e. the head. The source slice (the tail) is dropped by IntoIter. +struct InPlaceDrop { + inner: *mut T, + dst: *mut T, +} + +impl InPlaceDrop { + fn len(&self) -> usize { + unsafe { self.dst.offset_from(self.inner) as usize } + } +} + +impl Drop for InPlaceDrop { + #[inline] + fn drop(&mut self) { + unsafe { + ptr::drop_in_place(slice::from_raw_parts_mut(self.inner, self.len())); + } + } +} + +impl SpecFromIter> for Vec { + fn from_iter(iterator: IntoIter) -> Self { + // A common case is passing a vector into a function which immediately + // re-collects into a vector. We can short circuit this if the IntoIter + // has not been advanced at all. + // When it has been advanced We can also reuse the memory and move the data to the front. + // But we only do so when the resulting Vec wouldn't have more unused capacity + // than creating it through the generic FromIterator implementation would. That limitation + // is not strictly necessary as Vec's allocation behavior is intentionally unspecified. + // But it is a conservative choice. + let has_advanced = iterator.buf.as_ptr() as *const _ != iterator.ptr; + if !has_advanced || iterator.len() >= iterator.cap / 2 { + unsafe { + let it = ManuallyDrop::new(iterator); + if has_advanced { + ptr::copy(it.ptr, it.buf.as_ptr(), it.len()); + } + return Vec::from_raw_parts(it.buf.as_ptr(), it.len(), it.cap); + } + } + + let mut vec = Vec::new(); + // must delegate to spec_extend() since extend() itself delegates + // to spec_from for empty Vecs + vec.spec_extend(iterator); + vec + } +} + +fn write_in_place_with_drop( + src_end: *const T, +) -> impl FnMut(InPlaceDrop, T) -> Result, !> { + move |mut sink, item| { + unsafe { + // the InPlaceIterable contract cannot be verified precisely here since + // try_fold has an exclusive reference to the source pointer + // all we can do is check if it's still in range + debug_assert!(sink.dst as *const _ <= src_end, "InPlaceIterable contract violation"); + ptr::write(sink.dst, item); + sink.dst = sink.dst.add(1); + } + Ok(sink) + } +} + +/// Specialization marker for collecting an iterator pipeline into a Vec while reusing the +/// source allocation, i.e. executing the pipeline in place. +/// +/// The SourceIter parent trait is necessary for the specializing function to access the allocation +/// which is to be reused. But it is not sufficient for the specialization to be valid. See +/// additional bounds on the impl. +#[rustc_unsafe_specialization_marker] +trait SourceIterMarker: SourceIter {} + +// The std-internal SourceIter/InPlaceIterable traits are only implemented by chains of +// Adapter>> (all owned by core/std). Additional bounds +// on the adapter implementations (beyond `impl Trait for Adapter`) only depend on other +// traits already marked as specialization traits (Copy, TrustedRandomAccess, FusedIterator). +// I.e. the marker does not depend on lifetimes of user-supplied types. Modulo the Copy hole, which +// several other specializations already depend on. +impl SourceIterMarker for T where T: SourceIter + InPlaceIterable {} + +impl SpecFromIter for Vec +where + I: Iterator + SourceIterMarker, +{ + default fn from_iter(mut iterator: I) -> Self { + // Additional requirements which cannot expressed via trait bounds. We rely on const eval + // instead: + // a) no ZSTs as there would be no allocation to reuse and pointer arithmetic would panic + // b) size match as required by Alloc contract + // c) alignments match as required by Alloc contract + if mem::size_of::() == 0 + || mem::size_of::() + != mem::size_of::<<::Source as AsIntoIter>::Item>() + || mem::align_of::() + != mem::align_of::<<::Source as AsIntoIter>::Item>() + { + // fallback to more generic implementations + return SpecFromIterNested::from_iter(iterator); + } + + let (src_buf, src_ptr, dst_buf, dst_end, cap) = unsafe { + let inner = iterator.as_inner().as_into_iter(); + ( + inner.buf.as_ptr(), + inner.ptr, + inner.buf.as_ptr() as *mut T, + inner.end as *const T, + inner.cap, + ) + }; + + // use try-fold since + // - it vectorizes better for some iterator adapters + // - unlike most internal iteration methods, it only takes a &mut self + // - it lets us thread the write pointer through its innards and get it back in the end + let sink = InPlaceDrop { inner: dst_buf, dst: dst_buf }; + let sink = iterator + .try_fold::<_, _, Result<_, !>>(sink, write_in_place_with_drop(dst_end)) + .unwrap(); + // iteration succeeded, don't drop head + let dst = ManuallyDrop::new(sink).dst; + + let src = unsafe { iterator.as_inner().as_into_iter() }; + // check if SourceIter contract was upheld + // caveat: if they weren't we may not even make it to this point + debug_assert_eq!(src_buf, src.buf.as_ptr()); + // check InPlaceIterable contract. This is only possible if the iterator advanced the + // source pointer at all. If it uses unchecked access via TrustedRandomAccess + // then the source pointer will stay in its initial position and we can't use it as reference + if src.ptr != src_ptr { + debug_assert!( + dst as *const _ <= src.ptr, + "InPlaceIterable contract violation, write pointer advanced beyond read pointer" + ); + } + + // drop any remaining values at the tail of the source + src.drop_remaining(); + // but prevent drop of the allocation itself once IntoIter goes out of scope + src.forget_allocation(); + + let vec = unsafe { + let len = dst.offset_from(dst_buf) as usize; + Vec::from_raw_parts(dst_buf, len, cap) + }; + + vec + } +} + +impl<'a, T: 'a, I> SpecFromIter<&'a T, I> for Vec +where + I: Iterator, + T: Clone, +{ + default fn from_iter(iterator: I) -> Self { + SpecFromIter::from_iter(iterator.cloned()) + } +} + +// This utilizes `iterator.as_slice().to_vec()` since spec_extend +// must take more steps to reason about the final capacity + length +// and thus do more work. `to_vec()` directly allocates the correct amount +// and fills it exactly. +impl<'a, T: 'a + Clone> SpecFromIter<&'a T, slice::Iter<'a, T>> for Vec { + #[cfg(not(test))] + fn from_iter(iterator: slice::Iter<'a, T>) -> Self { + iterator.as_slice().to_vec() + } + + // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is + // required for this method definition, is not available. Instead use the + // `slice::to_vec` function which is only available with cfg(test) + // NB see the slice::hack module in slice.rs for more information + #[cfg(test)] + fn from_iter(iterator: slice::Iter<'a, T>) -> Self { + crate::slice::to_vec(iterator.as_slice(), Global) + } +} + +// Specialization trait used for Vec::extend +trait SpecExtend { + fn spec_extend(&mut self, iter: I); +} + +impl SpecExtend for Vec +where + I: Iterator, +{ + default fn spec_extend(&mut self, iter: I) { + self.extend_desugared(iter) + } +} + +impl SpecExtend for Vec +where + I: TrustedLen, +{ + default fn spec_extend(&mut self, iterator: I) { + // This is the case for a TrustedLen iterator. + let (low, high) = iterator.size_hint(); + if let Some(high_value) = high { + debug_assert_eq!( + low, + high_value, + "TrustedLen iterator's size hint is not exact: {:?}", + (low, high) + ); + } + if let Some(additional) = high { + self.reserve(additional); + unsafe { + let mut ptr = self.as_mut_ptr().add(self.len()); + let mut local_len = SetLenOnDrop::new(&mut self.len); + iterator.for_each(move |element| { + ptr::write(ptr, element); + ptr = ptr.offset(1); + // NB can't overflow since we would have had to alloc the address space + local_len.increment_len(1); + }); + } + } else { + self.extend_desugared(iterator) + } + } +} + +impl SpecExtend> for Vec { + fn spec_extend(&mut self, mut iterator: IntoIter) { + unsafe { + self.append_elements(iterator.as_slice() as _); + } + iterator.ptr = iterator.end; + } +} + +impl<'a, T: 'a, I, A: Allocator + 'a> SpecExtend<&'a T, I> for Vec +where + I: Iterator, + T: Clone, +{ + default fn spec_extend(&mut self, iterator: I) { + self.spec_extend(iterator.cloned()) + } +} + +impl<'a, T: 'a, A: Allocator + 'a> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec +where + T: Copy, +{ + fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) { + let slice = iterator.as_slice(); + unsafe { self.append_elements(slice) }; + } +} + +impl Vec { + // leaf method to which various SpecFrom/SpecExtend implementations delegate when + // they have no further optimizations to apply + fn extend_desugared>(&mut self, mut iterator: I) { + // This is the case for a general iterator. + // + // This function should be the moral equivalent of: + // + // for item in iterator { + // self.push(item); + // } + while let Some(element) = iterator.next() { + let len = self.len(); + if len == self.capacity() { + let (lower, _) = iterator.size_hint(); + self.reserve(lower.saturating_add(1)); + } + unsafe { + ptr::write(self.as_mut_ptr().add(len), element); + // NB can't overflow since we would have had to alloc the address space + self.set_len(len + 1); + } + } + } + + /// Creates a splicing iterator that replaces the specified range in the vector + /// with the given `replace_with` iterator and yields the removed items. + /// `replace_with` does not need to be the same length as `range`. + /// + /// `range` is removed even if the iterator is not consumed until the end. + /// + /// It is unspecified how many elements are removed from the vector + /// if the `Splice` value is leaked. + /// + /// The input iterator `replace_with` is only consumed when the `Splice` value is dropped. + /// + /// This is optimal if: + /// + /// * The tail (elements in the vector after `range`) is empty, + /// * or `replace_with` yields fewer elements than `range`’s length + /// * or the lower bound of its `size_hint()` is exact. + /// + /// Otherwise, a temporary vector is allocated and the tail is moved twice. + /// + /// # Panics + /// + /// Panics if the starting point is greater than the end point or if + /// the end point is greater than the length of the vector. + /// + /// # Examples + /// + /// ``` + /// let mut v = vec![1, 2, 3]; + /// let new = [7, 8]; + /// let u: Vec<_> = v.splice(..2, new.iter().cloned()).collect(); + /// assert_eq!(v, &[7, 8, 3]); + /// assert_eq!(u, &[1, 2]); + /// ``` + #[inline] + #[stable(feature = "vec_splice", since = "1.21.0")] + pub fn splice(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter, A> + where + R: RangeBounds, + I: IntoIterator, + { + Splice { drain: self.drain(range), replace_with: replace_with.into_iter() } + } + + /// Creates an iterator which uses a closure to determine if an element should be removed. + /// + /// If the closure returns true, then the element is removed and yielded. + /// If the closure returns false, the element will remain in the vector and will not be yielded + /// by the iterator. + /// + /// Using this method is equivalent to the following code: + /// + /// ``` + /// # let some_predicate = |x: &mut i32| { *x == 2 || *x == 3 || *x == 6 }; + /// # let mut vec = vec![1, 2, 3, 4, 5, 6]; + /// let mut i = 0; + /// while i != vec.len() { + /// if some_predicate(&mut vec[i]) { + /// let val = vec.remove(i); + /// // your code here + /// } else { + /// i += 1; + /// } + /// } + /// + /// # assert_eq!(vec, vec![1, 4, 5]); + /// ``` + /// + /// But `drain_filter` is easier to use. `drain_filter` is also more efficient, + /// because it can backshift the elements of the array in bulk. + /// + /// Note that `drain_filter` also lets you mutate every element in the filter closure, + /// regardless of whether you choose to keep or remove it. + /// + /// # Examples + /// + /// Splitting an array into evens and odds, reusing the original allocation: + /// + /// ``` + /// #![feature(drain_filter)] + /// let mut numbers = vec![1, 2, 3, 4, 5, 6, 8, 9, 11, 13, 14, 15]; + /// + /// let evens = numbers.drain_filter(|x| *x % 2 == 0).collect::>(); + /// let odds = numbers; + /// + /// assert_eq!(evens, vec![2, 4, 6, 8, 14]); + /// assert_eq!(odds, vec![1, 3, 5, 9, 11, 13, 15]); + /// ``` + #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] + pub fn drain_filter(&mut self, filter: F) -> DrainFilter<'_, T, F, A> + where + F: FnMut(&mut T) -> bool, + { + let old_len = self.len(); + + // Guard against us getting leaked (leak amplification) + unsafe { + self.set_len(0); + } + + DrainFilter { vec: self, idx: 0, del: 0, old_len, pred: filter, panic_flag: false } + } +} + +/// Extend implementation that copies elements out of references before pushing them onto the Vec. +/// +/// This implementation is specialized for slice iterators, where it uses [`copy_from_slice`] to +/// append the entire slice at once. +/// +/// [`copy_from_slice`]: ../../std/primitive.slice.html#method.copy_from_slice +#[stable(feature = "extend_ref", since = "1.2.0")] +impl<'a, T: Copy + 'a, A: Allocator + 'a> Extend<&'a T> for Vec { + fn extend>(&mut self, iter: I) { + self.spec_extend(iter.into_iter()) + } + + #[inline] + fn extend_one(&mut self, &item: &'a T) { + self.push(item); + } + + #[inline] + fn extend_reserve(&mut self, additional: usize) { + self.reserve(additional); + } +} + +macro_rules! __impl_slice_eq1 { + ([$($vars:tt)*] $lhs:ty, $rhs:ty $(where $ty:ty: $bound:ident)?, #[$stability:meta]) => { + #[$stability] + impl PartialEq<$rhs> for $lhs + where + T: PartialEq, + $($ty: $bound)? + { + #[inline] + fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } + #[inline] + fn ne(&self, other: &$rhs) -> bool { self[..] != other[..] } + } + } +} + +__impl_slice_eq1! { [A: Allocator] Vec, Vec, #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [A: Allocator] Vec, &[U], #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [A: Allocator] Vec, &mut [U], #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [A: Allocator] &[T], Vec, #[stable(feature = "partialeq_vec_for_ref_slice", since = "1.46.0")] } +__impl_slice_eq1! { [A: Allocator] &mut [T], Vec, #[stable(feature = "partialeq_vec_for_ref_slice", since = "1.46.0")] } +__impl_slice_eq1! { [A: Allocator] Vec, [U], #[stable(feature = "partialeq_vec_for_slice", since = "1.48.0")] } +__impl_slice_eq1! { [A: Allocator] [T], Vec, #[stable(feature = "partialeq_vec_for_slice", since = "1.48.0")] } +__impl_slice_eq1! { [A: Allocator] Cow<'_, [T]>, Vec where T: Clone, #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [] Cow<'_, [T]>, &[U] where T: Clone, #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [] Cow<'_, [T]>, &mut [U] where T: Clone, #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [A: Allocator, const N: usize] Vec, [U; N], #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [A: Allocator, const N: usize] Vec, &[U; N], #[stable(feature = "rust1", since = "1.0.0")] } + +// NOTE: some less important impls are omitted to reduce code bloat +// FIXME(Centril): Reconsider this? +//__impl_slice_eq1! { [const N: usize] Vec, &mut [B; N], } +//__impl_slice_eq1! { [const N: usize] [A; N], Vec, } +//__impl_slice_eq1! { [const N: usize] &[A; N], Vec, } +//__impl_slice_eq1! { [const N: usize] &mut [A; N], Vec, } +//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, [B; N], } +//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, &[B; N], } +//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, &mut [B; N], } + +/// Implements comparison of vectors, [lexicographically](core::cmp::Ord#lexicographical-comparison). +#[stable(feature = "rust1", since = "1.0.0")] +impl PartialOrd for Vec { + #[inline] + fn partial_cmp(&self, other: &Self) -> Option { + PartialOrd::partial_cmp(&**self, &**other) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Eq for Vec {} + +/// Implements ordering of vectors, [lexicographically](core::cmp::Ord#lexicographical-comparison). +#[stable(feature = "rust1", since = "1.0.0")] +impl Ord for Vec { + #[inline] + fn cmp(&self, other: &Self) -> Ordering { + Ord::cmp(&**self, &**other) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +unsafe impl<#[may_dangle] T, A: Allocator> Drop for Vec { + fn drop(&mut self) { + unsafe { + // use drop for [T] + // use a raw slice to refer to the elements of the vector as weakest necessary type; + // could avoid questions of validity in certain cases + ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.as_mut_ptr(), self.len)) + } + // RawVec handles deallocation + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Default for Vec { + /// Creates an empty `Vec`. + fn default() -> Vec { + Vec::new() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl fmt::Debug for Vec { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&**self, f) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl AsRef> for Vec { + fn as_ref(&self) -> &Vec { + self + } +} + +#[stable(feature = "vec_as_mut", since = "1.5.0")] +impl AsMut> for Vec { + fn as_mut(&mut self) -> &mut Vec { + self + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl AsRef<[T]> for Vec { + fn as_ref(&self) -> &[T] { + self + } +} + +#[stable(feature = "vec_as_mut", since = "1.5.0")] +impl AsMut<[T]> for Vec { + fn as_mut(&mut self) -> &mut [T] { + self + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl From<&[T]> for Vec { + #[cfg(not(test))] + fn from(s: &[T]) -> Vec { + s.to_vec() + } + #[cfg(test)] + fn from(s: &[T]) -> Vec { + crate::slice::to_vec(s, Global) + } +} + +#[stable(feature = "vec_from_mut", since = "1.19.0")] +impl From<&mut [T]> for Vec { + #[cfg(not(test))] + fn from(s: &mut [T]) -> Vec { + s.to_vec() + } + #[cfg(test)] + fn from(s: &mut [T]) -> Vec { + crate::slice::to_vec(s, Global) + } +} + +#[stable(feature = "vec_from_array", since = "1.44.0")] +impl From<[T; N]> for Vec { + #[cfg(not(test))] + fn from(s: [T; N]) -> Vec { + <[T]>::into_vec(box s) + } + #[cfg(test)] + fn from(s: [T; N]) -> Vec { + crate::slice::into_vec(box s) + } +} + +#[stable(feature = "vec_from_cow_slice", since = "1.14.0")] +impl<'a, T> From> for Vec +where + [T]: ToOwned>, +{ + fn from(s: Cow<'a, [T]>) -> Vec { + s.into_owned() + } +} + +// note: test pulls in libstd, which causes errors here +#[cfg(not(test))] +#[stable(feature = "vec_from_box", since = "1.18.0")] +impl From> for Vec { + fn from(s: Box<[T], A>) -> Self { + let len = s.len(); + Self { buf: RawVec::from_box(s), len } + } +} + +// note: test pulls in libstd, which causes errors here +#[cfg(not(test))] +#[stable(feature = "box_from_vec", since = "1.20.0")] +impl From> for Box<[T], A> { + fn from(v: Vec) -> Self { + v.into_boxed_slice() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl From<&str> for Vec { + fn from(s: &str) -> Vec { + From::from(s.as_bytes()) + } +} + +#[stable(feature = "array_try_from_vec", since = "1.48.0")] +impl TryFrom> for [T; N] { + type Error = Vec; + + /// Gets the entire contents of the `Vec` as an array, + /// if its size exactly matches that of the requested array. + /// + /// # Examples + /// + /// ``` + /// use std::convert::TryInto; + /// assert_eq!(vec![1, 2, 3].try_into(), Ok([1, 2, 3])); + /// assert_eq!(>::new().try_into(), Ok([])); + /// ``` + /// + /// If the length doesn't match, the input comes back in `Err`: + /// ``` + /// use std::convert::TryInto; + /// let r: Result<[i32; 4], _> = (0..10).collect::>().try_into(); + /// assert_eq!(r, Err(vec![0, 1, 2, 3, 4, 5, 6, 7, 8, 9])); + /// ``` + /// + /// If you're fine with just getting a prefix of the `Vec`, + /// you can call [`.truncate(N)`](Vec::truncate) first. + /// ``` + /// use std::convert::TryInto; + /// let mut v = String::from("hello world").into_bytes(); + /// v.sort(); + /// v.truncate(2); + /// let [a, b]: [_; 2] = v.try_into().unwrap(); + /// assert_eq!(a, b' '); + /// assert_eq!(b, b'd'); + /// ``` + fn try_from(mut vec: Vec) -> Result<[T; N], Vec> { + if vec.len() != N { + return Err(vec); + } + + // SAFETY: `.set_len(0)` is always sound. + unsafe { vec.set_len(0) }; + + // SAFETY: A `Vec`'s pointer is always aligned properly, and + // the alignment the array needs is the same as the items. + // We checked earlier that we have sufficient items. + // The items will not double-drop as the `set_len` + // tells the `Vec` not to also drop them. + let array = unsafe { ptr::read(vec.as_ptr() as *const [T; N]) }; + Ok(array) + } +} + +//////////////////////////////////////////////////////////////////////////////// +// Clone-on-write +//////////////////////////////////////////////////////////////////////////////// + +#[stable(feature = "cow_from_vec", since = "1.8.0")] +impl<'a, T: Clone> From<&'a [T]> for Cow<'a, [T]> { + fn from(s: &'a [T]) -> Cow<'a, [T]> { + Cow::Borrowed(s) + } +} + +#[stable(feature = "cow_from_vec", since = "1.8.0")] +impl<'a, T: Clone> From> for Cow<'a, [T]> { + fn from(v: Vec) -> Cow<'a, [T]> { + Cow::Owned(v) + } +} + +#[stable(feature = "cow_from_vec_ref", since = "1.28.0")] +impl<'a, T: Clone> From<&'a Vec> for Cow<'a, [T]> { + fn from(v: &'a Vec) -> Cow<'a, [T]> { + Cow::Borrowed(v.as_slice()) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T> FromIterator for Cow<'a, [T]> +where + T: Clone, +{ + fn from_iter>(it: I) -> Cow<'a, [T]> { + Cow::Owned(FromIterator::from_iter(it)) + } +} + +//////////////////////////////////////////////////////////////////////////////// +// Iterators +//////////////////////////////////////////////////////////////////////////////// + +/// An iterator that moves out of a vector. +/// +/// This `struct` is created by the `into_iter` method on [`Vec`] (provided +/// by the [`IntoIterator`] trait). +/// +/// # Example +/// +/// ``` +/// let v = vec![0, 1, 2]; +/// let iter: std::vec::IntoIter<_> = v.into_iter(); +/// ``` +#[stable(feature = "rust1", since = "1.0.0")] +pub struct IntoIter< + T, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, +> { + buf: NonNull, + phantom: PhantomData, + cap: usize, + alloc: A, + ptr: *const T, + end: *const T, +} + +#[stable(feature = "vec_intoiter_debug", since = "1.13.0")] +impl fmt::Debug for IntoIter { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("IntoIter").field(&self.as_slice()).finish() + } +} + +impl IntoIter { + /// Returns the remaining items of this iterator as a slice. + /// + /// # Examples + /// + /// ``` + /// let vec = vec!['a', 'b', 'c']; + /// let mut into_iter = vec.into_iter(); + /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); + /// let _ = into_iter.next().unwrap(); + /// assert_eq!(into_iter.as_slice(), &['b', 'c']); + /// ``` + #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")] + pub fn as_slice(&self) -> &[T] { + unsafe { slice::from_raw_parts(self.ptr, self.len()) } + } + + /// Returns the remaining items of this iterator as a mutable slice. + /// + /// # Examples + /// + /// ``` + /// let vec = vec!['a', 'b', 'c']; + /// let mut into_iter = vec.into_iter(); + /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); + /// into_iter.as_mut_slice()[2] = 'z'; + /// assert_eq!(into_iter.next().unwrap(), 'a'); + /// assert_eq!(into_iter.next().unwrap(), 'b'); + /// assert_eq!(into_iter.next().unwrap(), 'z'); + /// ``` + #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")] + pub fn as_mut_slice(&mut self) -> &mut [T] { + unsafe { &mut *self.as_raw_mut_slice() } + } + + /// Returns a reference to the underlying allocator. + #[unstable(feature = "allocator_api", issue = "32838")] + #[inline] + pub fn allocator(&self) -> &A { + &self.alloc + } + + fn as_raw_mut_slice(&mut self) -> *mut [T] { + ptr::slice_from_raw_parts_mut(self.ptr as *mut T, self.len()) + } + + fn drop_remaining(&mut self) { + unsafe { + ptr::drop_in_place(self.as_mut_slice()); + } + self.ptr = self.end; + } + + /// Relinquishes the backing allocation, equivalent to + /// `ptr::write(&mut self, Vec::new().into_iter())` + fn forget_allocation(&mut self) { + self.cap = 0; + self.buf = unsafe { NonNull::new_unchecked(RawVec::NEW.ptr()) }; + self.ptr = self.buf.as_ptr(); + self.end = self.buf.as_ptr(); + } +} + +#[stable(feature = "vec_intoiter_as_ref", since = "1.46.0")] +impl AsRef<[T]> for IntoIter { + fn as_ref(&self) -> &[T] { + self.as_slice() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +unsafe impl Send for IntoIter {} +#[stable(feature = "rust1", since = "1.0.0")] +unsafe impl Sync for IntoIter {} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for IntoIter { + type Item = T; + + #[inline] + fn next(&mut self) -> Option { + if self.ptr as *const _ == self.end { + None + } else if mem::size_of::() == 0 { + // purposefully don't use 'ptr.offset' because for + // vectors with 0-size elements this would return the + // same pointer. + self.ptr = unsafe { arith_offset(self.ptr as *const i8, 1) as *mut T }; + + // Make up a value of this ZST. + Some(unsafe { mem::zeroed() }) + } else { + let old = self.ptr; + self.ptr = unsafe { self.ptr.offset(1) }; + + Some(unsafe { ptr::read(old) }) + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let exact = if mem::size_of::() == 0 { + (self.end as usize).wrapping_sub(self.ptr as usize) + } else { + unsafe { self.end.offset_from(self.ptr) as usize } + }; + (exact, Some(exact)) + } + + #[inline] + fn count(self) -> usize { + self.len() + } + + unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> Self::Item + where + Self: TrustedRandomAccess, + { + // SAFETY: the caller must guarantee that `i` is in bounds of the + // `Vec`, so `i` cannot overflow an `isize`, and the `self.ptr.add(i)` + // is guaranteed to pointer to an element of the `Vec` and + // thus guaranteed to be valid to dereference. + // + // Also note the implementation of `Self: TrustedRandomAccess` requires + // that `T: Copy` so reading elements from the buffer doesn't invalidate + // them for `Drop`. + unsafe { + if mem::size_of::() == 0 { mem::zeroed() } else { ptr::read(self.ptr.add(i)) } + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl DoubleEndedIterator for IntoIter { + #[inline] + fn next_back(&mut self) -> Option { + if self.end == self.ptr { + None + } else if mem::size_of::() == 0 { + // See above for why 'ptr.offset' isn't used + self.end = unsafe { arith_offset(self.end as *const i8, -1) as *mut T }; + + // Make up a value of this ZST. + Some(unsafe { mem::zeroed() }) + } else { + self.end = unsafe { self.end.offset(-1) }; + + Some(unsafe { ptr::read(self.end) }) + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ExactSizeIterator for IntoIter { + fn is_empty(&self) -> bool { + self.ptr == self.end + } +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for IntoIter {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for IntoIter {} + +#[doc(hidden)] +#[unstable(issue = "none", feature = "std_internals")] +// T: Copy as approximation for !Drop since get_unchecked does not advance self.ptr +// and thus we can't implement drop-handling +unsafe impl TrustedRandomAccess for IntoIter +where + T: Copy, +{ + fn may_have_side_effect() -> bool { + false + } +} + +#[stable(feature = "vec_into_iter_clone", since = "1.8.0")] +impl Clone for IntoIter { + #[cfg(not(test))] + fn clone(&self) -> Self { + self.as_slice().to_vec_in(self.alloc.clone()).into_iter() + } + #[cfg(test)] + fn clone(&self) -> Self { + crate::slice::to_vec(self.as_slice(), self.alloc.clone()).into_iter() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter { + fn drop(&mut self) { + struct DropGuard<'a, T, A: Allocator>(&'a mut IntoIter); + + impl Drop for DropGuard<'_, T, A> { + fn drop(&mut self) { + unsafe { + // `IntoIter::alloc` is not used anymore after this + let alloc = ptr::read(&self.0.alloc); + // RawVec handles deallocation + let _ = RawVec::from_raw_parts_in(self.0.buf.as_ptr(), self.0.cap, alloc); + } + } + } + + let guard = DropGuard(self); + // destroy the remaining elements + unsafe { + ptr::drop_in_place(guard.0.as_raw_mut_slice()); + } + // now `guard` will be dropped and do the rest + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for IntoIter {} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for IntoIter { + type Source = Self; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut Self::Source { + self + } +} + +// internal helper trait for in-place iteration specialization. +#[rustc_specialization_trait] +pub(crate) trait AsIntoIter { + type Item; + fn as_into_iter(&mut self) -> &mut IntoIter; +} + +impl AsIntoIter for IntoIter { + type Item = T; + + fn as_into_iter(&mut self) -> &mut IntoIter { + self + } +} + +/// A draining iterator for `Vec`. +/// +/// 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 + tail_start: usize, + /// Length of tail + tail_len: usize, + /// Current remaining range to remove + iter: slice::Iter<'a, T>, + vec: NonNull>, +} + +#[stable(feature = "collection_debug", since = "1.17.0")] +impl 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']); + /// ``` + #[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")] + #[inline] + pub fn allocator(&self) -> &A { + unsafe { self.vec.as_ref().allocator() } + } +} + +#[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 Sync for Drain<'_, T, A> {} +#[stable(feature = "drain", since = "1.6.0")] +unsafe impl Send for Drain<'_, T, A> {} + +#[stable(feature = "drain", since = "1.6.0")] +impl Iterator for Drain<'_, T, A> { + type Item = T; + + #[inline] + fn next(&mut self) -> Option { + self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) }) + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +#[stable(feature = "drain", since = "1.6.0")] +impl DoubleEndedIterator for Drain<'_, T, A> { + #[inline] + fn next_back(&mut self) -> Option { + self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) }) + } +} + +#[stable(feature = "drain", since = "1.6.0")] +impl Drop for Drain<'_, T, A> { + fn drop(&mut self) { + /// Continues dropping the remaining elements in the `Drain`, then 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) { + // Continue the same loop we have below. If the loop already finished, this does + // nothing. + self.0.for_each(drop); + + 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); + } + } + } + } + + // exhaust self first + while let Some(item) = self.next() { + let guard = DropGuard(self); + drop(item); + mem::forget(guard); + } + + // Drop a `DropGuard` to move back the non-drained tail of `self`. + DropGuard(self); + } +} + +#[stable(feature = "drain", since = "1.6.0")] +impl ExactSizeIterator for Drain<'_, T, A> { + fn is_empty(&self) -> bool { + self.iter.is_empty() + } +} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for Drain<'_, T, A> {} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for Drain<'_, T, A> {} + +/// A splicing iterator for `Vec`. +/// +/// This struct is created by [`Vec::splice()`]. +/// See its documentation for more. +/// +/// # Example +/// +/// ``` +/// let mut v = vec![0, 1, 2]; +/// let new = [7, 8]; +/// let iter: std::vec::Splice<_> = v.splice(1.., new.iter().cloned()); +/// ``` +#[derive(Debug)] +#[stable(feature = "vec_splice", since = "1.21.0")] +pub struct Splice< + 'a, + I: Iterator + 'a, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global, +> { + drain: Drain<'a, I::Item, A>, + replace_with: I, +} + +#[stable(feature = "vec_splice", since = "1.21.0")] +impl Iterator for Splice<'_, I, A> { + type Item = I::Item; + + fn next(&mut self) -> Option { + self.drain.next() + } + + fn size_hint(&self) -> (usize, Option) { + self.drain.size_hint() + } +} + +#[stable(feature = "vec_splice", since = "1.21.0")] +impl DoubleEndedIterator for Splice<'_, I, A> { + fn next_back(&mut self) -> Option { + self.drain.next_back() + } +} + +#[stable(feature = "vec_splice", since = "1.21.0")] +impl ExactSizeIterator for Splice<'_, I, A> {} + +#[stable(feature = "vec_splice", since = "1.21.0")] +impl Drop for Splice<'_, I, A> { + fn drop(&mut self) { + self.drain.by_ref().for_each(drop); + + unsafe { + if self.drain.tail_len == 0 { + self.drain.vec.as_mut().extend(self.replace_with.by_ref()); + return; + } + + // First fill the range left by drain(). + if !self.drain.fill(&mut self.replace_with) { + return; + } + + // There may be more elements. Use the lower bound as an estimate. + // FIXME: Is the upper bound a better guess? Or something else? + let (lower_bound, _upper_bound) = self.replace_with.size_hint(); + if lower_bound > 0 { + self.drain.move_tail(lower_bound); + if !self.drain.fill(&mut self.replace_with) { + return; + } + } + + // Collect any remaining elements. + // This is a zero-length vector which does not allocate if `lower_bound` was exact. + let mut collected = self.replace_with.by_ref().collect::>().into_iter(); + // Now we have an exact count. + if collected.len() > 0 { + self.drain.move_tail(collected.len()); + let filled = self.drain.fill(&mut collected); + debug_assert!(filled); + debug_assert_eq!(collected.len(), 0); + } + } + // Let `Drain::drop` move the tail back if necessary and restore `vec.len`. + } +} + +/// Private helper methods for `Splice::drop` +impl Drain<'_, T, A> { + /// The range from `self.vec.len` to `self.tail_start` contains elements + /// that have been moved out. + /// Fill that range as much as possible with new elements from the `replace_with` iterator. + /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.) + unsafe fn fill>(&mut self, replace_with: &mut I) -> bool { + let vec = unsafe { self.vec.as_mut() }; + let range_start = vec.len; + let range_end = self.tail_start; + let range_slice = unsafe { + slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start) + }; + + for place in range_slice { + if let Some(new_item) = replace_with.next() { + unsafe { ptr::write(place, new_item) }; + vec.len += 1; + } else { + return false; + } + } + true + } + + /// Makes room for inserting more elements before the tail. + unsafe fn move_tail(&mut self, additional: usize) { + let vec = unsafe { self.vec.as_mut() }; + let len = self.tail_start + self.tail_len; + vec.buf.reserve(len, additional); + + let new_tail_start = self.tail_start + additional; + unsafe { + let src = vec.as_ptr().add(self.tail_start); + let dst = vec.as_mut_ptr().add(new_tail_start); + ptr::copy(src, dst, self.tail_len); + } + self.tail_start = new_tail_start; + } +} + +/// An iterator which uses a closure to determine if an element should be removed. +/// +/// This struct is created by [`Vec::drain_filter`]. +/// See its documentation for more. +/// +/// # Example +/// +/// ``` +/// #![feature(drain_filter)] +/// +/// let mut v = vec![0, 1, 2]; +/// let iter: std::vec::DrainFilter<_, _> = v.drain_filter(|x| *x % 2 == 0); +/// ``` +#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] +#[derive(Debug)] +pub struct DrainFilter< + 'a, + T, + F, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, +> where + F: FnMut(&mut T) -> bool, +{ + vec: &'a mut Vec, + /// The index of the item that will be inspected by the next call to `next`. + idx: usize, + /// The number of items that have been drained (removed) thus far. + del: usize, + /// The original length of `vec` prior to draining. + old_len: usize, + /// The filter test predicate. + pred: F, + /// A flag that indicates a panic has occurred in the filter test predicate. + /// This is used as a hint in the drop implementation to prevent consumption + /// of the remainder of the `DrainFilter`. Any unprocessed items will be + /// backshifted in the `vec`, but no further items will be dropped or + /// tested by the filter predicate. + panic_flag: bool, +} + +impl DrainFilter<'_, T, F, A> +where + F: FnMut(&mut T) -> bool, +{ + /// Returns a reference to the underlying allocator. + #[unstable(feature = "allocator_api", issue = "32838")] + #[inline] + pub fn allocator(&self) -> &A { + self.vec.allocator() + } +} + +#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] +impl Iterator for DrainFilter<'_, T, F, A> +where + F: FnMut(&mut T) -> bool, +{ + type Item = T; + + fn next(&mut self) -> Option { + unsafe { + while self.idx < self.old_len { + let i = self.idx; + let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len); + self.panic_flag = true; + let drained = (self.pred)(&mut v[i]); + self.panic_flag = false; + // Update the index *after* the predicate is called. If the index + // is updated prior and the predicate panics, the element at this + // index would be leaked. + self.idx += 1; + if drained { + self.del += 1; + return Some(ptr::read(&v[i])); + } else if self.del > 0 { + let del = self.del; + let src: *const T = &v[i]; + let dst: *mut T = &mut v[i - del]; + ptr::copy_nonoverlapping(src, dst, 1); + } + } + None + } + } + + fn size_hint(&self) -> (usize, Option) { + (0, Some(self.old_len - self.idx)) + } +} + +#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] +impl Drop for DrainFilter<'_, T, F, A> +where + F: FnMut(&mut T) -> bool, +{ + fn drop(&mut self) { + struct BackshiftOnDrop<'a, 'b, T, F, A: Allocator> + where + F: FnMut(&mut T) -> bool, + { + drain: &'b mut DrainFilter<'a, T, F, A>, + } + + impl<'a, 'b, T, F, A: Allocator> Drop for BackshiftOnDrop<'a, 'b, T, F, A> + where + F: FnMut(&mut T) -> bool, + { + fn drop(&mut self) { + unsafe { + if self.drain.idx < self.drain.old_len && self.drain.del > 0 { + // This is a pretty messed up state, and there isn't really an + // obviously right thing to do. We don't want to keep trying + // to execute `pred`, so we just backshift all the unprocessed + // elements and tell the vec that they still exist. The backshift + // is required to prevent a double-drop of the last successfully + // drained item prior to a panic in the predicate. + let ptr = self.drain.vec.as_mut_ptr(); + let src = ptr.add(self.drain.idx); + let dst = src.sub(self.drain.del); + let tail_len = self.drain.old_len - self.drain.idx; + src.copy_to(dst, tail_len); + } + self.drain.vec.set_len(self.drain.old_len - self.drain.del); + } + } + } + + let backshift = BackshiftOnDrop { drain: self }; + + // Attempt to consume any remaining elements if the filter predicate + // has not yet panicked. We'll backshift any remaining elements + // whether we've already panicked or if the consumption here panics. + if !backshift.drain.panic_flag { + backshift.drain.for_each(drop); + } + } +} -- cgit 1.4.1-3-g733a5 From 434e5d142204d9b3019cfedc049d39b0affd08e7 Mon Sep 17 00:00:00 2001 From: C Date: Fri, 4 Dec 2020 23:58:11 +0000 Subject: refactor: moving DrainFilter into drain_filter.rs --- library/alloc/src/vec/drain_filter.rs | 143 ++++++++++++++++++++++++++++++++++ library/alloc/src/vec/mod.rs | 143 ++-------------------------------- 2 files changed, 148 insertions(+), 138 deletions(-) create mode 100644 library/alloc/src/vec/drain_filter.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/drain_filter.rs b/library/alloc/src/vec/drain_filter.rs new file mode 100644 index 00000000000..9d898c7c756 --- /dev/null +++ b/library/alloc/src/vec/drain_filter.rs @@ -0,0 +1,143 @@ +use core::ptr::{self}; +use core::slice::{self}; +use crate::alloc::{Allocator, Global}; + +use super::{Vec}; + +/// An iterator which uses a closure to determine if an element should be removed. +/// +/// This struct is created by [`Vec::drain_filter`]. +/// See its documentation for more. +/// +/// # Example +/// +/// ``` +/// #![feature(drain_filter)] +/// +/// let mut v = vec![0, 1, 2]; +/// let iter: std::vec::DrainFilter<_, _> = v.drain_filter(|x| *x % 2 == 0); +/// ``` +#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] +#[derive(Debug)] +pub struct DrainFilter< + 'a, + T, + F, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, +> where + F: FnMut(&mut T) -> bool, +{ + pub(super) vec: &'a mut Vec, + /// The index of the item that will be inspected by the next call to `next`. + pub(super) idx: usize, + /// The number of items that have been drained (removed) thus far. + pub(super) del: usize, + /// The original length of `vec` prior to draining. + pub(super) old_len: usize, + /// The filter test predicate. + pub(super) pred: F, + /// A flag that indicates a panic has occurred in the filter test predicate. + /// This is used as a hint in the drop implementation to prevent consumption + /// of the remainder of the `DrainFilter`. Any unprocessed items will be + /// backshifted in the `vec`, but no further items will be dropped or + /// tested by the filter predicate. + pub(super) panic_flag: bool, +} + +impl DrainFilter<'_, T, F, A> + where + F: FnMut(&mut T) -> bool, +{ + /// Returns a reference to the underlying allocator. + #[unstable(feature = "allocator_api", issue = "32838")] + #[inline] + pub fn allocator(&self) -> &A { + self.vec.allocator() + } +} + +#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] +impl Iterator for DrainFilter<'_, T, F, A> + where + F: FnMut(&mut T) -> bool, +{ + type Item = T; + + fn next(&mut self) -> Option { + unsafe { + while self.idx < self.old_len { + let i = self.idx; + let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len); + self.panic_flag = true; + let drained = (self.pred)(&mut v[i]); + self.panic_flag = false; + // Update the index *after* the predicate is called. If the index + // is updated prior and the predicate panics, the element at this + // index would be leaked. + self.idx += 1; + if drained { + self.del += 1; + return Some(ptr::read(&v[i])); + } else if self.del > 0 { + let del = self.del; + let src: *const T = &v[i]; + let dst: *mut T = &mut v[i - del]; + ptr::copy_nonoverlapping(src, dst, 1); + } + } + None + } + } + + fn size_hint(&self) -> (usize, Option) { + (0, Some(self.old_len - self.idx)) + } +} + +#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] +impl Drop for DrainFilter<'_, T, F, A> + where + F: FnMut(&mut T) -> bool, +{ + fn drop(&mut self) { + struct BackshiftOnDrop<'a, 'b, T, F, A: Allocator> + where + F: FnMut(&mut T) -> bool, + { + drain: &'b mut DrainFilter<'a, T, F, A>, + } + + impl<'a, 'b, T, F, A: Allocator> Drop for BackshiftOnDrop<'a, 'b, T, F, A> + where + F: FnMut(&mut T) -> bool, + { + fn drop(&mut self) { + unsafe { + if self.drain.idx < self.drain.old_len && self.drain.del > 0 { + // This is a pretty messed up state, and there isn't really an + // obviously right thing to do. We don't want to keep trying + // to execute `pred`, so we just backshift all the unprocessed + // elements and tell the vec that they still exist. The backshift + // is required to prevent a double-drop of the last successfully + // drained item prior to a panic in the predicate. + let ptr = self.drain.vec.as_mut_ptr(); + let src = ptr.add(self.drain.idx); + let dst = src.sub(self.drain.del); + let tail_len = self.drain.old_len - self.drain.idx; + src.copy_to(dst, tail_len); + } + self.drain.vec.set_len(self.drain.old_len - self.drain.del); + } + } + } + + let backshift = BackshiftOnDrop { drain: self }; + + // Attempt to consume any remaining elements if the filter predicate + // has not yet panicked. We'll backshift any remaining elements + // whether we've already panicked or if the consumption here panics. + if !backshift.drain.panic_flag { + backshift.drain.for_each(drop); + } + } +} \ No newline at end of file diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index c9fa41138cd..2fb1fe0d5cb 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -74,6 +74,11 @@ use crate::boxed::Box; use crate::collections::TryReserveError; use crate::raw_vec::RawVec; +#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] +pub use self::drain_filter::DrainFilter; + +mod drain_filter; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -3585,141 +3590,3 @@ impl Drain<'_, T, A> { self.tail_start = new_tail_start; } } - -/// An iterator which uses a closure to determine if an element should be removed. -/// -/// This struct is created by [`Vec::drain_filter`]. -/// See its documentation for more. -/// -/// # Example -/// -/// ``` -/// #![feature(drain_filter)] -/// -/// let mut v = vec![0, 1, 2]; -/// let iter: std::vec::DrainFilter<_, _> = v.drain_filter(|x| *x % 2 == 0); -/// ``` -#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] -#[derive(Debug)] -pub struct DrainFilter< - 'a, - T, - F, - #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, -> where - F: FnMut(&mut T) -> bool, -{ - vec: &'a mut Vec, - /// The index of the item that will be inspected by the next call to `next`. - idx: usize, - /// The number of items that have been drained (removed) thus far. - del: usize, - /// The original length of `vec` prior to draining. - old_len: usize, - /// The filter test predicate. - pred: F, - /// A flag that indicates a panic has occurred in the filter test predicate. - /// This is used as a hint in the drop implementation to prevent consumption - /// of the remainder of the `DrainFilter`. Any unprocessed items will be - /// backshifted in the `vec`, but no further items will be dropped or - /// tested by the filter predicate. - panic_flag: bool, -} - -impl DrainFilter<'_, T, F, A> -where - F: FnMut(&mut T) -> bool, -{ - /// Returns a reference to the underlying allocator. - #[unstable(feature = "allocator_api", issue = "32838")] - #[inline] - pub fn allocator(&self) -> &A { - self.vec.allocator() - } -} - -#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] -impl Iterator for DrainFilter<'_, T, F, A> -where - F: FnMut(&mut T) -> bool, -{ - type Item = T; - - fn next(&mut self) -> Option { - unsafe { - while self.idx < self.old_len { - let i = self.idx; - let v = slice::from_raw_parts_mut(self.vec.as_mut_ptr(), self.old_len); - self.panic_flag = true; - let drained = (self.pred)(&mut v[i]); - self.panic_flag = false; - // Update the index *after* the predicate is called. If the index - // is updated prior and the predicate panics, the element at this - // index would be leaked. - self.idx += 1; - if drained { - self.del += 1; - return Some(ptr::read(&v[i])); - } else if self.del > 0 { - let del = self.del; - let src: *const T = &v[i]; - let dst: *mut T = &mut v[i - del]; - ptr::copy_nonoverlapping(src, dst, 1); - } - } - None - } - } - - fn size_hint(&self) -> (usize, Option) { - (0, Some(self.old_len - self.idx)) - } -} - -#[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] -impl Drop for DrainFilter<'_, T, F, A> -where - F: FnMut(&mut T) -> bool, -{ - fn drop(&mut self) { - struct BackshiftOnDrop<'a, 'b, T, F, A: Allocator> - where - F: FnMut(&mut T) -> bool, - { - drain: &'b mut DrainFilter<'a, T, F, A>, - } - - impl<'a, 'b, T, F, A: Allocator> Drop for BackshiftOnDrop<'a, 'b, T, F, A> - where - F: FnMut(&mut T) -> bool, - { - fn drop(&mut self) { - unsafe { - if self.drain.idx < self.drain.old_len && self.drain.del > 0 { - // This is a pretty messed up state, and there isn't really an - // obviously right thing to do. We don't want to keep trying - // to execute `pred`, so we just backshift all the unprocessed - // elements and tell the vec that they still exist. The backshift - // is required to prevent a double-drop of the last successfully - // drained item prior to a panic in the predicate. - let ptr = self.drain.vec.as_mut_ptr(); - let src = ptr.add(self.drain.idx); - let dst = src.sub(self.drain.del); - let tail_len = self.drain.old_len - self.drain.idx; - src.copy_to(dst, tail_len); - } - self.drain.vec.set_len(self.drain.old_len - self.drain.del); - } - } - } - - let backshift = BackshiftOnDrop { drain: self }; - - // Attempt to consume any remaining elements if the filter predicate - // has not yet panicked. We'll backshift any remaining elements - // whether we've already panicked or if the consumption here panics. - if !backshift.drain.panic_flag { - backshift.drain.for_each(drop); - } - } -} -- cgit 1.4.1-3-g733a5 From 17593f258b5bc8a4778df35bf9a82950738b70e8 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 00:04:32 +0000 Subject: refactor: moving Splice into splice.rs --- library/alloc/src/vec/mod.rs | 133 ++-------------------------------------- library/alloc/src/vec/splice.rs | 133 ++++++++++++++++++++++++++++++++++++++++ 2 files changed, 138 insertions(+), 128 deletions(-) create mode 100644 library/alloc/src/vec/splice.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 2fb1fe0d5cb..924b04a8fe1 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -79,6 +79,11 @@ pub use self::drain_filter::DrainFilter; mod drain_filter; +#[stable(feature = "vec_splice", since = "1.21.0")] +pub use self::splice::Splice; + +mod splice; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -3462,131 +3467,3 @@ unsafe impl TrustedLen for Drain<'_, T, A> {} #[stable(feature = "fused", since = "1.26.0")] impl FusedIterator for Drain<'_, T, A> {} - -/// A splicing iterator for `Vec`. -/// -/// This struct is created by [`Vec::splice()`]. -/// See its documentation for more. -/// -/// # Example -/// -/// ``` -/// let mut v = vec![0, 1, 2]; -/// let new = [7, 8]; -/// let iter: std::vec::Splice<_> = v.splice(1.., new.iter().cloned()); -/// ``` -#[derive(Debug)] -#[stable(feature = "vec_splice", since = "1.21.0")] -pub struct Splice< - 'a, - I: Iterator + 'a, - #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global, -> { - drain: Drain<'a, I::Item, A>, - replace_with: I, -} - -#[stable(feature = "vec_splice", since = "1.21.0")] -impl Iterator for Splice<'_, I, A> { - type Item = I::Item; - - fn next(&mut self) -> Option { - self.drain.next() - } - - fn size_hint(&self) -> (usize, Option) { - self.drain.size_hint() - } -} - -#[stable(feature = "vec_splice", since = "1.21.0")] -impl DoubleEndedIterator for Splice<'_, I, A> { - fn next_back(&mut self) -> Option { - self.drain.next_back() - } -} - -#[stable(feature = "vec_splice", since = "1.21.0")] -impl ExactSizeIterator for Splice<'_, I, A> {} - -#[stable(feature = "vec_splice", since = "1.21.0")] -impl Drop for Splice<'_, I, A> { - fn drop(&mut self) { - self.drain.by_ref().for_each(drop); - - unsafe { - if self.drain.tail_len == 0 { - self.drain.vec.as_mut().extend(self.replace_with.by_ref()); - return; - } - - // First fill the range left by drain(). - if !self.drain.fill(&mut self.replace_with) { - return; - } - - // There may be more elements. Use the lower bound as an estimate. - // FIXME: Is the upper bound a better guess? Or something else? - let (lower_bound, _upper_bound) = self.replace_with.size_hint(); - if lower_bound > 0 { - self.drain.move_tail(lower_bound); - if !self.drain.fill(&mut self.replace_with) { - return; - } - } - - // Collect any remaining elements. - // This is a zero-length vector which does not allocate if `lower_bound` was exact. - let mut collected = self.replace_with.by_ref().collect::>().into_iter(); - // Now we have an exact count. - if collected.len() > 0 { - self.drain.move_tail(collected.len()); - let filled = self.drain.fill(&mut collected); - debug_assert!(filled); - debug_assert_eq!(collected.len(), 0); - } - } - // Let `Drain::drop` move the tail back if necessary and restore `vec.len`. - } -} - -/// Private helper methods for `Splice::drop` -impl Drain<'_, T, A> { - /// The range from `self.vec.len` to `self.tail_start` contains elements - /// that have been moved out. - /// Fill that range as much as possible with new elements from the `replace_with` iterator. - /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.) - unsafe fn fill>(&mut self, replace_with: &mut I) -> bool { - let vec = unsafe { self.vec.as_mut() }; - let range_start = vec.len; - let range_end = self.tail_start; - let range_slice = unsafe { - slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start) - }; - - for place in range_slice { - if let Some(new_item) = replace_with.next() { - unsafe { ptr::write(place, new_item) }; - vec.len += 1; - } else { - return false; - } - } - true - } - - /// Makes room for inserting more elements before the tail. - unsafe fn move_tail(&mut self, additional: usize) { - let vec = unsafe { self.vec.as_mut() }; - let len = self.tail_start + self.tail_len; - vec.buf.reserve(len, additional); - - let new_tail_start = self.tail_start + additional; - unsafe { - let src = vec.as_ptr().add(self.tail_start); - let dst = vec.as_mut_ptr().add(new_tail_start); - ptr::copy(src, dst, self.tail_len); - } - self.tail_start = new_tail_start; - } -} diff --git a/library/alloc/src/vec/splice.rs b/library/alloc/src/vec/splice.rs new file mode 100644 index 00000000000..86b2fa0968e --- /dev/null +++ b/library/alloc/src/vec/splice.rs @@ -0,0 +1,133 @@ +use crate::alloc::{Allocator, Global}; +use core::ptr::{self}; +use core::slice::{self}; + +use super::{Vec, Drain}; + +/// A splicing iterator for `Vec`. +/// +/// This struct is created by [`Vec::splice()`]. +/// See its documentation for more. +/// +/// # Example +/// +/// ``` +/// let mut v = vec![0, 1, 2]; +/// let new = [7, 8]; +/// let iter: std::vec::Splice<_> = v.splice(1.., new.iter().cloned()); +/// ``` +#[derive(Debug)] +#[stable(feature = "vec_splice", since = "1.21.0")] +pub struct Splice< + 'a, + I: Iterator + 'a, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator + 'a = Global, +> { + pub(super) drain: Drain<'a, I::Item, A>, + pub(super) replace_with: I, +} + +#[stable(feature = "vec_splice", since = "1.21.0")] +impl Iterator for Splice<'_, I, A> { + type Item = I::Item; + + fn next(&mut self) -> Option { + self.drain.next() + } + + fn size_hint(&self) -> (usize, Option) { + self.drain.size_hint() + } +} + +#[stable(feature = "vec_splice", since = "1.21.0")] +impl DoubleEndedIterator for Splice<'_, I, A> { + fn next_back(&mut self) -> Option { + self.drain.next_back() + } +} + +#[stable(feature = "vec_splice", since = "1.21.0")] +impl ExactSizeIterator for Splice<'_, I, A> {} + +#[stable(feature = "vec_splice", since = "1.21.0")] +impl Drop for Splice<'_, I, A> { + fn drop(&mut self) { + self.drain.by_ref().for_each(drop); + + unsafe { + if self.drain.tail_len == 0 { + self.drain.vec.as_mut().extend(self.replace_with.by_ref()); + return; + } + + // First fill the range left by drain(). + if !self.drain.fill(&mut self.replace_with) { + return; + } + + // There may be more elements. Use the lower bound as an estimate. + // FIXME: Is the upper bound a better guess? Or something else? + let (lower_bound, _upper_bound) = self.replace_with.size_hint(); + if lower_bound > 0 { + self.drain.move_tail(lower_bound); + if !self.drain.fill(&mut self.replace_with) { + return; + } + } + + // Collect any remaining elements. + // This is a zero-length vector which does not allocate if `lower_bound` was exact. + let mut collected = self.replace_with.by_ref().collect::>().into_iter(); + // Now we have an exact count. + if collected.len() > 0 { + self.drain.move_tail(collected.len()); + let filled = self.drain.fill(&mut collected); + debug_assert!(filled); + debug_assert_eq!(collected.len(), 0); + } + } + // Let `Drain::drop` move the tail back if necessary and restore `vec.len`. + } +} + +/// Private helper methods for `Splice::drop` +impl Drain<'_, T, A> { + /// The range from `self.vec.len` to `self.tail_start` contains elements + /// that have been moved out. + /// Fill that range as much as possible with new elements from the `replace_with` iterator. + /// Returns `true` if we filled the entire range. (`replace_with.next()` didn’t return `None`.) + unsafe fn fill>(&mut self, replace_with: &mut I) -> bool { + let vec = unsafe { self.vec.as_mut() }; + let range_start = vec.len; + let range_end = self.tail_start; + let range_slice = unsafe { + slice::from_raw_parts_mut(vec.as_mut_ptr().add(range_start), range_end - range_start) + }; + + for place in range_slice { + if let Some(new_item) = replace_with.next() { + unsafe { ptr::write(place, new_item) }; + vec.len += 1; + } else { + return false; + } + } + true + } + + /// Makes room for inserting more elements before the tail. + unsafe fn move_tail(&mut self, additional: usize) { + let vec = unsafe { self.vec.as_mut() }; + let len = self.tail_start + self.tail_len; + vec.buf.reserve(len, additional); + + let new_tail_start = self.tail_start + additional; + unsafe { + let src = vec.as_ptr().add(self.tail_start); + let dst = vec.as_mut_ptr().add(new_tail_start); + ptr::copy(src, dst, self.tail_len); + } + self.tail_start = new_tail_start; + } +} \ No newline at end of file -- cgit 1.4.1-3-g733a5 From 6bf9608f9fd22c10f8ba37b416b6a0d4431ef59a Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 00:12:42 +0000 Subject: refactor: moving Drain into drain.rs --- library/alloc/src/vec/drain.rs | 157 +++++++++++++++++++++++++++++++++++++++++ library/alloc/src/vec/mod.rs | 152 ++------------------------------------- 2 files changed, 162 insertions(+), 147 deletions(-) create mode 100644 library/alloc/src/vec/drain.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/drain.rs b/library/alloc/src/vec/drain.rs new file mode 100644 index 00000000000..e61f17a1c30 --- /dev/null +++ b/library/alloc/src/vec/drain.rs @@ -0,0 +1,157 @@ +use crate::alloc::{Allocator, Global}; +use core::iter::{ + FusedIterator, TrustedLen, +}; +use core::mem::{self}; +use core::ptr::{self, NonNull}; +use core::slice::{self}; +use core::fmt; + +use super::{Vec}; + +/// A draining iterator for `Vec`. +/// +/// 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>, +} + +#[stable(feature = "collection_debug", since = "1.17.0")] +impl 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']); + /// ``` + #[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")] + #[inline] + pub fn allocator(&self) -> &A { + unsafe { self.vec.as_ref().allocator() } + } +} + +#[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 Sync for Drain<'_, T, A> {} +#[stable(feature = "drain", since = "1.6.0")] +unsafe impl Send for Drain<'_, T, A> {} + +#[stable(feature = "drain", since = "1.6.0")] +impl Iterator for Drain<'_, T, A> { + type Item = T; + + #[inline] + fn next(&mut self) -> Option { + self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) }) + } + + fn size_hint(&self) -> (usize, Option) { + self.iter.size_hint() + } +} + +#[stable(feature = "drain", since = "1.6.0")] +impl DoubleEndedIterator for Drain<'_, T, A> { + #[inline] + fn next_back(&mut self) -> Option { + self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) }) + } +} + +#[stable(feature = "drain", since = "1.6.0")] +impl Drop for Drain<'_, T, A> { + fn drop(&mut self) { + /// Continues dropping the remaining elements in the `Drain`, then 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) { + // Continue the same loop we have below. If the loop already finished, this does + // nothing. + self.0.for_each(drop); + + 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); + } + } + } + } + + // exhaust self first + while let Some(item) = self.next() { + let guard = DropGuard(self); + drop(item); + mem::forget(guard); + } + + // Drop a `DropGuard` to move back the non-drained tail of `self`. + DropGuard(self); + } +} + +#[stable(feature = "drain", since = "1.6.0")] +impl ExactSizeIterator for Drain<'_, T, A> { + fn is_empty(&self) -> bool { + self.iter.is_empty() + } +} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for Drain<'_, T, A> {} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for Drain<'_, T, A> {} diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 924b04a8fe1..1553e367c87 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -84,6 +84,11 @@ pub use self::splice::Splice; mod splice; +#[stable(feature = "drain", since = "1.6.0")] +pub use self::drain::Drain; + +mod drain; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -3320,150 +3325,3 @@ impl AsIntoIter for IntoIter { self } } - -/// A draining iterator for `Vec`. -/// -/// 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 - tail_start: usize, - /// Length of tail - tail_len: usize, - /// Current remaining range to remove - iter: slice::Iter<'a, T>, - vec: NonNull>, -} - -#[stable(feature = "collection_debug", since = "1.17.0")] -impl 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']); - /// ``` - #[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")] - #[inline] - pub fn allocator(&self) -> &A { - unsafe { self.vec.as_ref().allocator() } - } -} - -#[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 Sync for Drain<'_, T, A> {} -#[stable(feature = "drain", since = "1.6.0")] -unsafe impl Send for Drain<'_, T, A> {} - -#[stable(feature = "drain", since = "1.6.0")] -impl Iterator for Drain<'_, T, A> { - type Item = T; - - #[inline] - fn next(&mut self) -> Option { - self.iter.next().map(|elt| unsafe { ptr::read(elt as *const _) }) - } - - fn size_hint(&self) -> (usize, Option) { - self.iter.size_hint() - } -} - -#[stable(feature = "drain", since = "1.6.0")] -impl DoubleEndedIterator for Drain<'_, T, A> { - #[inline] - fn next_back(&mut self) -> Option { - self.iter.next_back().map(|elt| unsafe { ptr::read(elt as *const _) }) - } -} - -#[stable(feature = "drain", since = "1.6.0")] -impl Drop for Drain<'_, T, A> { - fn drop(&mut self) { - /// Continues dropping the remaining elements in the `Drain`, then 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) { - // Continue the same loop we have below. If the loop already finished, this does - // nothing. - self.0.for_each(drop); - - 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); - } - } - } - } - - // exhaust self first - while let Some(item) = self.next() { - let guard = DropGuard(self); - drop(item); - mem::forget(guard); - } - - // Drop a `DropGuard` to move back the non-drained tail of `self`. - DropGuard(self); - } -} - -#[stable(feature = "drain", since = "1.6.0")] -impl ExactSizeIterator for Drain<'_, T, A> { - fn is_empty(&self) -> bool { - self.iter.is_empty() - } -} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl TrustedLen for Drain<'_, T, A> {} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for Drain<'_, T, A> {} -- cgit 1.4.1-3-g733a5 From 2580822b919257c8b7c81d3343c43733c216e26c Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 00:17:25 +0000 Subject: refactor: moved Vec impl Cow into cow.rs --- library/alloc/src/vec/cow.rs | 35 +++++++++++++++++++++++++++++++++++ library/alloc/src/vec/mod.rs | 37 ++----------------------------------- 2 files changed, 37 insertions(+), 35 deletions(-) create mode 100644 library/alloc/src/vec/cow.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/cow.rs b/library/alloc/src/vec/cow.rs new file mode 100644 index 00000000000..15942f9892d --- /dev/null +++ b/library/alloc/src/vec/cow.rs @@ -0,0 +1,35 @@ +use crate::borrow::Cow; +use core::iter::{FromIterator}; + +use super::{Vec}; + +#[stable(feature = "cow_from_vec", since = "1.8.0")] +impl<'a, T: Clone> From<&'a [T]> for Cow<'a, [T]> { + fn from(s: &'a [T]) -> Cow<'a, [T]> { + Cow::Borrowed(s) + } +} + +#[stable(feature = "cow_from_vec", since = "1.8.0")] +impl<'a, T: Clone> From> for Cow<'a, [T]> { + fn from(v: Vec) -> Cow<'a, [T]> { + Cow::Owned(v) + } +} + +#[stable(feature = "cow_from_vec_ref", since = "1.28.0")] +impl<'a, T: Clone> From<&'a Vec> for Cow<'a, [T]> { + fn from(v: &'a Vec) -> Cow<'a, [T]> { + Cow::Borrowed(v.as_slice()) + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, T> FromIterator for Cow<'a, [T]> + where + T: Clone, +{ + fn from_iter>(it: I) -> Cow<'a, [T]> { + Cow::Owned(FromIterator::from_iter(it)) + } +} \ No newline at end of file diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 1553e367c87..8d3f8b0bfd8 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -89,6 +89,8 @@ pub use self::drain::Drain; mod drain; +mod cow; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -3013,41 +3015,6 @@ impl TryFrom> for [T; N] { } } -//////////////////////////////////////////////////////////////////////////////// -// Clone-on-write -//////////////////////////////////////////////////////////////////////////////// - -#[stable(feature = "cow_from_vec", since = "1.8.0")] -impl<'a, T: Clone> From<&'a [T]> for Cow<'a, [T]> { - fn from(s: &'a [T]) -> Cow<'a, [T]> { - Cow::Borrowed(s) - } -} - -#[stable(feature = "cow_from_vec", since = "1.8.0")] -impl<'a, T: Clone> From> for Cow<'a, [T]> { - fn from(v: Vec) -> Cow<'a, [T]> { - Cow::Owned(v) - } -} - -#[stable(feature = "cow_from_vec_ref", since = "1.28.0")] -impl<'a, T: Clone> From<&'a Vec> for Cow<'a, [T]> { - fn from(v: &'a Vec) -> Cow<'a, [T]> { - Cow::Borrowed(v.as_slice()) - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl<'a, T> FromIterator for Cow<'a, [T]> -where - T: Clone, -{ - fn from_iter>(it: I) -> Cow<'a, [T]> { - Cow::Owned(FromIterator::from_iter(it)) - } -} - //////////////////////////////////////////////////////////////////////////////// // Iterators //////////////////////////////////////////////////////////////////////////////// -- cgit 1.4.1-3-g733a5 From 93613901d004ccf0b8a240bf328559a4128ac3b2 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 00:45:20 +0000 Subject: refactor: moved IntoIter into into_iter.rs --- library/alloc/src/vec/into_iter.rs | 270 +++++++++++++++++++++++++++++++++++++ library/alloc/src/vec/mod.rs | 270 +------------------------------------ 2 files changed, 276 insertions(+), 264 deletions(-) create mode 100644 library/alloc/src/vec/into_iter.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs new file mode 100644 index 00000000000..623792a6316 --- /dev/null +++ b/library/alloc/src/vec/into_iter.rs @@ -0,0 +1,270 @@ +use crate::alloc::{Allocator, Global}; +use crate::raw_vec::RawVec; +use core::marker::PhantomData; +use core::intrinsics::{arith_offset}; +use core::mem::{self}; +use core::fmt; +use core::ptr::{self, NonNull}; +use core::slice::{self}; +use core::iter::{ + FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccess, +}; + +/// An iterator that moves out of a vector. +/// +/// This `struct` is created by the `into_iter` method on [`Vec`] (provided +/// by the [`IntoIterator`] trait). +/// +/// # Example +/// +/// ``` +/// let v = vec![0, 1, 2]; +/// let iter: std::vec::IntoIter<_> = v.into_iter(); +/// ``` +#[stable(feature = "rust1", since = "1.0.0")] +pub struct IntoIter< + T, + #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, +> { + pub(super) buf: NonNull, + pub(super) phantom: PhantomData, + pub(super) cap: usize, + pub(super) alloc: A, + pub(super) ptr: *const T, + pub(super) end: *const T, +} + +#[stable(feature = "vec_intoiter_debug", since = "1.13.0")] +impl fmt::Debug for IntoIter { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.debug_tuple("IntoIter").field(&self.as_slice()).finish() + } +} + +impl IntoIter { + /// Returns the remaining items of this iterator as a slice. + /// + /// # Examples + /// + /// ``` + /// let vec = vec!['a', 'b', 'c']; + /// let mut into_iter = vec.into_iter(); + /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); + /// let _ = into_iter.next().unwrap(); + /// assert_eq!(into_iter.as_slice(), &['b', 'c']); + /// ``` + #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")] + pub fn as_slice(&self) -> &[T] { + unsafe { slice::from_raw_parts(self.ptr, self.len()) } + } + + /// Returns the remaining items of this iterator as a mutable slice. + /// + /// # Examples + /// + /// ``` + /// let vec = vec!['a', 'b', 'c']; + /// let mut into_iter = vec.into_iter(); + /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); + /// into_iter.as_mut_slice()[2] = 'z'; + /// assert_eq!(into_iter.next().unwrap(), 'a'); + /// assert_eq!(into_iter.next().unwrap(), 'b'); + /// assert_eq!(into_iter.next().unwrap(), 'z'); + /// ``` + #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")] + pub fn as_mut_slice(&mut self) -> &mut [T] { + unsafe { &mut *self.as_raw_mut_slice() } + } + + /// Returns a reference to the underlying allocator. + #[unstable(feature = "allocator_api", issue = "32838")] + #[inline] + pub fn allocator(&self) -> &A { + &self.alloc + } + + fn as_raw_mut_slice(&mut self) -> *mut [T] { + ptr::slice_from_raw_parts_mut(self.ptr as *mut T, self.len()) + } + + pub(super) fn drop_remaining(&mut self) { + unsafe { + ptr::drop_in_place(self.as_mut_slice()); + } + self.ptr = self.end; + } + + /// Relinquishes the backing allocation, equivalent to + /// `ptr::write(&mut self, Vec::new().into_iter())` + pub(super) fn forget_allocation(&mut self) { + self.cap = 0; + self.buf = unsafe { NonNull::new_unchecked(RawVec::NEW.ptr()) }; + self.ptr = self.buf.as_ptr(); + self.end = self.buf.as_ptr(); + } +} + +#[stable(feature = "vec_intoiter_as_ref", since = "1.46.0")] +impl AsRef<[T]> for IntoIter { + fn as_ref(&self) -> &[T] { + self.as_slice() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +unsafe impl Send for IntoIter {} +#[stable(feature = "rust1", since = "1.0.0")] +unsafe impl Sync for IntoIter {} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Iterator for IntoIter { + type Item = T; + + #[inline] + fn next(&mut self) -> Option { + if self.ptr as *const _ == self.end { + None + } else if mem::size_of::() == 0 { + // purposefully don't use 'ptr.offset' because for + // vectors with 0-size elements this would return the + // same pointer. + self.ptr = unsafe { arith_offset(self.ptr as *const i8, 1) as *mut T }; + + // Make up a value of this ZST. + Some(unsafe { mem::zeroed() }) + } else { + let old = self.ptr; + self.ptr = unsafe { self.ptr.offset(1) }; + + Some(unsafe { ptr::read(old) }) + } + } + + #[inline] + fn size_hint(&self) -> (usize, Option) { + let exact = if mem::size_of::() == 0 { + (self.end as usize).wrapping_sub(self.ptr as usize) + } else { + unsafe { self.end.offset_from(self.ptr) as usize } + }; + (exact, Some(exact)) + } + + #[inline] + fn count(self) -> usize { + self.len() + } + + unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> Self::Item + where + Self: TrustedRandomAccess, + { + // SAFETY: the caller must guarantee that `i` is in bounds of the + // `Vec`, so `i` cannot overflow an `isize`, and the `self.ptr.add(i)` + // is guaranteed to pointer to an element of the `Vec` and + // thus guaranteed to be valid to dereference. + // + // Also note the implementation of `Self: TrustedRandomAccess` requires + // that `T: Copy` so reading elements from the buffer doesn't invalidate + // them for `Drop`. + unsafe { + if mem::size_of::() == 0 { mem::zeroed() } else { ptr::read(self.ptr.add(i)) } + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl DoubleEndedIterator for IntoIter { + #[inline] + fn next_back(&mut self) -> Option { + if self.end == self.ptr { + None + } else if mem::size_of::() == 0 { + // See above for why 'ptr.offset' isn't used + self.end = unsafe { arith_offset(self.end as *const i8, -1) as *mut T }; + + // Make up a value of this ZST. + Some(unsafe { mem::zeroed() }) + } else { + self.end = unsafe { self.end.offset(-1) }; + + Some(unsafe { ptr::read(self.end) }) + } + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl ExactSizeIterator for IntoIter { + fn is_empty(&self) -> bool { + self.ptr == self.end + } +} + +#[stable(feature = "fused", since = "1.26.0")] +impl FusedIterator for IntoIter {} + +#[unstable(feature = "trusted_len", issue = "37572")] +unsafe impl TrustedLen for IntoIter {} + +#[doc(hidden)] +#[unstable(issue = "none", feature = "std_internals")] +// T: Copy as approximation for !Drop since get_unchecked does not advance self.ptr +// and thus we can't implement drop-handling +unsafe impl TrustedRandomAccess for IntoIter + where + T: Copy, +{ + fn may_have_side_effect() -> bool { + false + } +} + +#[stable(feature = "vec_into_iter_clone", since = "1.8.0")] +impl Clone for IntoIter { + #[cfg(not(test))] + fn clone(&self) -> Self { + self.as_slice().to_vec_in(self.alloc.clone()).into_iter() + } + #[cfg(test)] + fn clone(&self) -> Self { + crate::slice::to_vec(self.as_slice(), self.alloc.clone()).into_iter() + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter { + fn drop(&mut self) { + struct DropGuard<'a, T, A: Allocator>(&'a mut IntoIter); + + impl Drop for DropGuard<'_, T, A> { + fn drop(&mut self) { + unsafe { + // `IntoIter::alloc` is not used anymore after this + let alloc = ptr::read(&self.0.alloc); + // RawVec handles deallocation + let _ = RawVec::from_raw_parts_in(self.0.buf.as_ptr(), self.0.cap, alloc); + } + } + } + + let guard = DropGuard(self); + // destroy the remaining elements + unsafe { + ptr::drop_in_place(guard.0.as_raw_mut_slice()); + } + // now `guard` will be dropped and do the rest + } +} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl InPlaceIterable for IntoIter {} + +#[unstable(issue = "none", feature = "inplace_iteration")] +unsafe impl SourceIter for IntoIter { + type Source = Self; + + #[inline] + unsafe fn as_inner(&mut self) -> &mut Self::Source { + self + } +} diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 8d3f8b0bfd8..b6508bfea08 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -60,7 +60,7 @@ use core::fmt; use core::hash::{Hash, Hasher}; use core::intrinsics::{arith_offset, assume}; use core::iter::{ - FromIterator, FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccess, + FromIterator, InPlaceIterable, SourceIter, TrustedLen, }; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, MaybeUninit}; @@ -91,6 +91,11 @@ mod drain; mod cow; +#[stable(feature = "rust1", since = "1.0.0")] +pub use self::into_iter::IntoIter; + +mod into_iter; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -3015,269 +3020,6 @@ impl TryFrom> for [T; N] { } } -//////////////////////////////////////////////////////////////////////////////// -// Iterators -//////////////////////////////////////////////////////////////////////////////// - -/// An iterator that moves out of a vector. -/// -/// This `struct` is created by the `into_iter` method on [`Vec`] (provided -/// by the [`IntoIterator`] trait). -/// -/// # Example -/// -/// ``` -/// let v = vec![0, 1, 2]; -/// let iter: std::vec::IntoIter<_> = v.into_iter(); -/// ``` -#[stable(feature = "rust1", since = "1.0.0")] -pub struct IntoIter< - T, - #[unstable(feature = "allocator_api", issue = "32838")] A: Allocator = Global, -> { - buf: NonNull, - phantom: PhantomData, - cap: usize, - alloc: A, - ptr: *const T, - end: *const T, -} - -#[stable(feature = "vec_intoiter_debug", since = "1.13.0")] -impl fmt::Debug for IntoIter { - fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { - f.debug_tuple("IntoIter").field(&self.as_slice()).finish() - } -} - -impl IntoIter { - /// Returns the remaining items of this iterator as a slice. - /// - /// # Examples - /// - /// ``` - /// let vec = vec!['a', 'b', 'c']; - /// let mut into_iter = vec.into_iter(); - /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); - /// let _ = into_iter.next().unwrap(); - /// assert_eq!(into_iter.as_slice(), &['b', 'c']); - /// ``` - #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")] - pub fn as_slice(&self) -> &[T] { - unsafe { slice::from_raw_parts(self.ptr, self.len()) } - } - - /// Returns the remaining items of this iterator as a mutable slice. - /// - /// # Examples - /// - /// ``` - /// let vec = vec!['a', 'b', 'c']; - /// let mut into_iter = vec.into_iter(); - /// assert_eq!(into_iter.as_slice(), &['a', 'b', 'c']); - /// into_iter.as_mut_slice()[2] = 'z'; - /// assert_eq!(into_iter.next().unwrap(), 'a'); - /// assert_eq!(into_iter.next().unwrap(), 'b'); - /// assert_eq!(into_iter.next().unwrap(), 'z'); - /// ``` - #[stable(feature = "vec_into_iter_as_slice", since = "1.15.0")] - pub fn as_mut_slice(&mut self) -> &mut [T] { - unsafe { &mut *self.as_raw_mut_slice() } - } - - /// Returns a reference to the underlying allocator. - #[unstable(feature = "allocator_api", issue = "32838")] - #[inline] - pub fn allocator(&self) -> &A { - &self.alloc - } - - fn as_raw_mut_slice(&mut self) -> *mut [T] { - ptr::slice_from_raw_parts_mut(self.ptr as *mut T, self.len()) - } - - fn drop_remaining(&mut self) { - unsafe { - ptr::drop_in_place(self.as_mut_slice()); - } - self.ptr = self.end; - } - - /// Relinquishes the backing allocation, equivalent to - /// `ptr::write(&mut self, Vec::new().into_iter())` - fn forget_allocation(&mut self) { - self.cap = 0; - self.buf = unsafe { NonNull::new_unchecked(RawVec::NEW.ptr()) }; - self.ptr = self.buf.as_ptr(); - self.end = self.buf.as_ptr(); - } -} - -#[stable(feature = "vec_intoiter_as_ref", since = "1.46.0")] -impl AsRef<[T]> for IntoIter { - fn as_ref(&self) -> &[T] { - self.as_slice() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -unsafe impl Send for IntoIter {} -#[stable(feature = "rust1", since = "1.0.0")] -unsafe impl Sync for IntoIter {} - -#[stable(feature = "rust1", since = "1.0.0")] -impl Iterator for IntoIter { - type Item = T; - - #[inline] - fn next(&mut self) -> Option { - if self.ptr as *const _ == self.end { - None - } else if mem::size_of::() == 0 { - // purposefully don't use 'ptr.offset' because for - // vectors with 0-size elements this would return the - // same pointer. - self.ptr = unsafe { arith_offset(self.ptr as *const i8, 1) as *mut T }; - - // Make up a value of this ZST. - Some(unsafe { mem::zeroed() }) - } else { - let old = self.ptr; - self.ptr = unsafe { self.ptr.offset(1) }; - - Some(unsafe { ptr::read(old) }) - } - } - - #[inline] - fn size_hint(&self) -> (usize, Option) { - let exact = if mem::size_of::() == 0 { - (self.end as usize).wrapping_sub(self.ptr as usize) - } else { - unsafe { self.end.offset_from(self.ptr) as usize } - }; - (exact, Some(exact)) - } - - #[inline] - fn count(self) -> usize { - self.len() - } - - unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> Self::Item - where - Self: TrustedRandomAccess, - { - // SAFETY: the caller must guarantee that `i` is in bounds of the - // `Vec`, so `i` cannot overflow an `isize`, and the `self.ptr.add(i)` - // is guaranteed to pointer to an element of the `Vec` and - // thus guaranteed to be valid to dereference. - // - // Also note the implementation of `Self: TrustedRandomAccess` requires - // that `T: Copy` so reading elements from the buffer doesn't invalidate - // them for `Drop`. - unsafe { - if mem::size_of::() == 0 { mem::zeroed() } else { ptr::read(self.ptr.add(i)) } - } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl DoubleEndedIterator for IntoIter { - #[inline] - fn next_back(&mut self) -> Option { - if self.end == self.ptr { - None - } else if mem::size_of::() == 0 { - // See above for why 'ptr.offset' isn't used - self.end = unsafe { arith_offset(self.end as *const i8, -1) as *mut T }; - - // Make up a value of this ZST. - Some(unsafe { mem::zeroed() }) - } else { - self.end = unsafe { self.end.offset(-1) }; - - Some(unsafe { ptr::read(self.end) }) - } - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -impl ExactSizeIterator for IntoIter { - fn is_empty(&self) -> bool { - self.ptr == self.end - } -} - -#[stable(feature = "fused", since = "1.26.0")] -impl FusedIterator for IntoIter {} - -#[unstable(feature = "trusted_len", issue = "37572")] -unsafe impl TrustedLen for IntoIter {} - -#[doc(hidden)] -#[unstable(issue = "none", feature = "std_internals")] -// T: Copy as approximation for !Drop since get_unchecked does not advance self.ptr -// and thus we can't implement drop-handling -unsafe impl TrustedRandomAccess for IntoIter -where - T: Copy, -{ - fn may_have_side_effect() -> bool { - false - } -} - -#[stable(feature = "vec_into_iter_clone", since = "1.8.0")] -impl Clone for IntoIter { - #[cfg(not(test))] - fn clone(&self) -> Self { - self.as_slice().to_vec_in(self.alloc.clone()).into_iter() - } - #[cfg(test)] - fn clone(&self) -> Self { - crate::slice::to_vec(self.as_slice(), self.alloc.clone()).into_iter() - } -} - -#[stable(feature = "rust1", since = "1.0.0")] -unsafe impl<#[may_dangle] T, A: Allocator> Drop for IntoIter { - fn drop(&mut self) { - struct DropGuard<'a, T, A: Allocator>(&'a mut IntoIter); - - impl Drop for DropGuard<'_, T, A> { - fn drop(&mut self) { - unsafe { - // `IntoIter::alloc` is not used anymore after this - let alloc = ptr::read(&self.0.alloc); - // RawVec handles deallocation - let _ = RawVec::from_raw_parts_in(self.0.buf.as_ptr(), self.0.cap, alloc); - } - } - } - - let guard = DropGuard(self); - // destroy the remaining elements - unsafe { - ptr::drop_in_place(guard.0.as_raw_mut_slice()); - } - // now `guard` will be dropped and do the rest - } -} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl InPlaceIterable for IntoIter {} - -#[unstable(issue = "none", feature = "inplace_iteration")] -unsafe impl SourceIter for IntoIter { - type Source = Self; - - #[inline] - unsafe fn as_inner(&mut self) -> &mut Self::Source { - self - } -} - // internal helper trait for in-place iteration specialization. #[rustc_specialization_trait] pub(crate) trait AsIntoIter { -- cgit 1.4.1-3-g733a5 From 2a1248976a00429994d5965bb31d6dcc1b7dcd68 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 00:47:54 +0000 Subject: refactor: moving AsIntoIter into into_iter.rs --- library/alloc/src/vec/into_iter.rs | 15 +++++++++++++++ library/alloc/src/vec/mod.rs | 16 +--------------- 2 files changed, 16 insertions(+), 15 deletions(-) (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index 623792a6316..c4330df4ad9 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -268,3 +268,18 @@ unsafe impl SourceIter for IntoIter { self } } + +// internal helper trait for in-place iteration specialization. +#[rustc_specialization_trait] +pub(crate) trait AsIntoIter { + type Item; + fn as_into_iter(&mut self) -> &mut IntoIter; +} + +impl AsIntoIter for IntoIter { + type Item = T; + + fn as_into_iter(&mut self) -> &mut IntoIter { + self + } +} diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index b6508bfea08..1f410e3c028 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -93,6 +93,7 @@ mod cow; #[stable(feature = "rust1", since = "1.0.0")] pub use self::into_iter::IntoIter; +pub (crate) use self::into_iter::AsIntoIter; mod into_iter; @@ -3019,18 +3020,3 @@ impl TryFrom> for [T; N] { Ok(array) } } - -// internal helper trait for in-place iteration specialization. -#[rustc_specialization_trait] -pub(crate) trait AsIntoIter { - type Item; - fn as_into_iter(&mut self) -> &mut IntoIter; -} - -impl AsIntoIter for IntoIter { - type Item = T; - - fn as_into_iter(&mut self) -> &mut IntoIter { - self - } -} -- cgit 1.4.1-3-g733a5 From 840c4e2873476a7d6101f71e4f63b3024245ccd1 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 00:52:48 +0000 Subject: refactor: moved IsZero into is_zero.rs --- library/alloc/src/vec/is_zero.rs | 71 ++++++++++++++++++++++++++++++++++++++ library/alloc/src/vec/mod.rs | 74 +++------------------------------------- 2 files changed, 75 insertions(+), 70 deletions(-) create mode 100644 library/alloc/src/vec/is_zero.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/is_zero.rs b/library/alloc/src/vec/is_zero.rs new file mode 100644 index 00000000000..961f6ca171b --- /dev/null +++ b/library/alloc/src/vec/is_zero.rs @@ -0,0 +1,71 @@ +use crate::boxed::Box; + +#[rustc_specialization_trait] +pub(super) unsafe trait IsZero { + /// Whether this value is zero + fn is_zero(&self) -> bool; +} + +macro_rules! impl_is_zero { + ($t:ty, $is_zero:expr) => { + unsafe impl IsZero for $t { + #[inline] + fn is_zero(&self) -> bool { + $is_zero(*self) + } + } + }; +} + +impl_is_zero!(i16, |x| x == 0); +impl_is_zero!(i32, |x| x == 0); +impl_is_zero!(i64, |x| x == 0); +impl_is_zero!(i128, |x| x == 0); +impl_is_zero!(isize, |x| x == 0); + +impl_is_zero!(u16, |x| x == 0); +impl_is_zero!(u32, |x| x == 0); +impl_is_zero!(u64, |x| x == 0); +impl_is_zero!(u128, |x| x == 0); +impl_is_zero!(usize, |x| x == 0); + +impl_is_zero!(bool, |x| x == false); +impl_is_zero!(char, |x| x == '\0'); + +impl_is_zero!(f32, |x: f32| x.to_bits() == 0); +impl_is_zero!(f64, |x: f64| x.to_bits() == 0); + +unsafe impl IsZero for *const T { + #[inline] + fn is_zero(&self) -> bool { + (*self).is_null() + } +} + +unsafe impl IsZero for *mut T { + #[inline] + fn is_zero(&self) -> bool { + (*self).is_null() + } +} + +// `Option<&T>` and `Option>` are guaranteed to represent `None` as null. +// For fat pointers, the bytes that would be the pointer metadata in the `Some` +// variant are padding in the `None` variant, so ignoring them and +// zero-initializing instead is ok. +// `Option<&mut T>` never implements `Clone`, so there's no need for an impl of +// `SpecFromElem`. + +unsafe impl IsZero for Option<&T> { + #[inline] + fn is_zero(&self) -> bool { + self.is_none() + } +} + +unsafe impl IsZero for Option> { + #[inline] + fn is_zero(&self) -> bool { + self.is_none() + } +} \ No newline at end of file diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 1f410e3c028..69fcfaa6a7e 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -97,6 +97,10 @@ pub (crate) use self::into_iter::AsIntoIter; mod into_iter; +use self::is_zero::IsZero; + +mod is_zero; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -2042,76 +2046,6 @@ impl SpecFromElem for T { } } -#[rustc_specialization_trait] -unsafe trait IsZero { - /// Whether this value is zero - fn is_zero(&self) -> bool; -} - -macro_rules! impl_is_zero { - ($t:ty, $is_zero:expr) => { - unsafe impl IsZero for $t { - #[inline] - fn is_zero(&self) -> bool { - $is_zero(*self) - } - } - }; -} - -impl_is_zero!(i16, |x| x == 0); -impl_is_zero!(i32, |x| x == 0); -impl_is_zero!(i64, |x| x == 0); -impl_is_zero!(i128, |x| x == 0); -impl_is_zero!(isize, |x| x == 0); - -impl_is_zero!(u16, |x| x == 0); -impl_is_zero!(u32, |x| x == 0); -impl_is_zero!(u64, |x| x == 0); -impl_is_zero!(u128, |x| x == 0); -impl_is_zero!(usize, |x| x == 0); - -impl_is_zero!(bool, |x| x == false); -impl_is_zero!(char, |x| x == '\0'); - -impl_is_zero!(f32, |x: f32| x.to_bits() == 0); -impl_is_zero!(f64, |x: f64| x.to_bits() == 0); - -unsafe impl IsZero for *const T { - #[inline] - fn is_zero(&self) -> bool { - (*self).is_null() - } -} - -unsafe impl IsZero for *mut T { - #[inline] - fn is_zero(&self) -> bool { - (*self).is_null() - } -} - -// `Option<&T>` and `Option>` are guaranteed to represent `None` as null. -// For fat pointers, the bytes that would be the pointer metadata in the `Some` -// variant are padding in the `None` variant, so ignoring them and -// zero-initializing instead is ok. -// `Option<&mut T>` never implements `Clone`, so there's no need for an impl of -// `SpecFromElem`. - -unsafe impl IsZero for Option<&T> { - #[inline] - fn is_zero(&self) -> bool { - self.is_none() - } -} - -unsafe impl IsZero for Option> { - #[inline] - fn is_zero(&self) -> bool { - self.is_none() - } -} - //////////////////////////////////////////////////////////////////////////////// // Common trait implementations for Vec //////////////////////////////////////////////////////////////////////////////// -- cgit 1.4.1-3-g733a5 From 5ac6709b95bb0cce4cffa9bd87d241928bc7f3f6 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 01:04:06 +0000 Subject: refactor: moving SourceIterMarker into source_iter_marker.rs --- library/alloc/src/vec/mod.rs | 107 +-------------------------- library/alloc/src/vec/source_iter_marker.rs | 110 ++++++++++++++++++++++++++++ 2 files changed, 113 insertions(+), 104 deletions(-) create mode 100644 library/alloc/src/vec/source_iter_marker.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 69fcfaa6a7e..bd71d7004b9 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -60,7 +60,7 @@ use core::fmt; use core::hash::{Hash, Hasher}; use core::intrinsics::{arith_offset, assume}; use core::iter::{ - FromIterator, InPlaceIterable, SourceIter, TrustedLen, + FromIterator, TrustedLen, }; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, MaybeUninit}; @@ -101,6 +101,8 @@ use self::is_zero::IsZero; mod is_zero; +mod source_iter_marker; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -2356,109 +2358,6 @@ impl SpecFromIter> for Vec { } } -fn write_in_place_with_drop( - src_end: *const T, -) -> impl FnMut(InPlaceDrop, T) -> Result, !> { - move |mut sink, item| { - unsafe { - // the InPlaceIterable contract cannot be verified precisely here since - // try_fold has an exclusive reference to the source pointer - // all we can do is check if it's still in range - debug_assert!(sink.dst as *const _ <= src_end, "InPlaceIterable contract violation"); - ptr::write(sink.dst, item); - sink.dst = sink.dst.add(1); - } - Ok(sink) - } -} - -/// Specialization marker for collecting an iterator pipeline into a Vec while reusing the -/// source allocation, i.e. executing the pipeline in place. -/// -/// The SourceIter parent trait is necessary for the specializing function to access the allocation -/// which is to be reused. But it is not sufficient for the specialization to be valid. See -/// additional bounds on the impl. -#[rustc_unsafe_specialization_marker] -trait SourceIterMarker: SourceIter {} - -// The std-internal SourceIter/InPlaceIterable traits are only implemented by chains of -// Adapter>> (all owned by core/std). Additional bounds -// on the adapter implementations (beyond `impl Trait for Adapter`) only depend on other -// traits already marked as specialization traits (Copy, TrustedRandomAccess, FusedIterator). -// I.e. the marker does not depend on lifetimes of user-supplied types. Modulo the Copy hole, which -// several other specializations already depend on. -impl SourceIterMarker for T where T: SourceIter + InPlaceIterable {} - -impl SpecFromIter for Vec -where - I: Iterator + SourceIterMarker, -{ - default fn from_iter(mut iterator: I) -> Self { - // Additional requirements which cannot expressed via trait bounds. We rely on const eval - // instead: - // a) no ZSTs as there would be no allocation to reuse and pointer arithmetic would panic - // b) size match as required by Alloc contract - // c) alignments match as required by Alloc contract - if mem::size_of::() == 0 - || mem::size_of::() - != mem::size_of::<<::Source as AsIntoIter>::Item>() - || mem::align_of::() - != mem::align_of::<<::Source as AsIntoIter>::Item>() - { - // fallback to more generic implementations - return SpecFromIterNested::from_iter(iterator); - } - - let (src_buf, src_ptr, dst_buf, dst_end, cap) = unsafe { - let inner = iterator.as_inner().as_into_iter(); - ( - inner.buf.as_ptr(), - inner.ptr, - inner.buf.as_ptr() as *mut T, - inner.end as *const T, - inner.cap, - ) - }; - - // use try-fold since - // - it vectorizes better for some iterator adapters - // - unlike most internal iteration methods, it only takes a &mut self - // - it lets us thread the write pointer through its innards and get it back in the end - let sink = InPlaceDrop { inner: dst_buf, dst: dst_buf }; - let sink = iterator - .try_fold::<_, _, Result<_, !>>(sink, write_in_place_with_drop(dst_end)) - .unwrap(); - // iteration succeeded, don't drop head - let dst = ManuallyDrop::new(sink).dst; - - let src = unsafe { iterator.as_inner().as_into_iter() }; - // check if SourceIter contract was upheld - // caveat: if they weren't we may not even make it to this point - debug_assert_eq!(src_buf, src.buf.as_ptr()); - // check InPlaceIterable contract. This is only possible if the iterator advanced the - // source pointer at all. If it uses unchecked access via TrustedRandomAccess - // then the source pointer will stay in its initial position and we can't use it as reference - if src.ptr != src_ptr { - debug_assert!( - dst as *const _ <= src.ptr, - "InPlaceIterable contract violation, write pointer advanced beyond read pointer" - ); - } - - // drop any remaining values at the tail of the source - src.drop_remaining(); - // but prevent drop of the allocation itself once IntoIter goes out of scope - src.forget_allocation(); - - let vec = unsafe { - let len = dst.offset_from(dst_buf) as usize; - Vec::from_raw_parts(dst_buf, len, cap) - }; - - vec - } -} - impl<'a, T: 'a, I> SpecFromIter<&'a T, I> for Vec where I: Iterator, diff --git a/library/alloc/src/vec/source_iter_marker.rs b/library/alloc/src/vec/source_iter_marker.rs new file mode 100644 index 00000000000..eb3ae01a47e --- /dev/null +++ b/library/alloc/src/vec/source_iter_marker.rs @@ -0,0 +1,110 @@ +use core::iter::{ + InPlaceIterable, SourceIter, +}; +use core::mem::{self, ManuallyDrop}; +use core::ptr::{self}; + +use super::{Vec, InPlaceDrop, AsIntoIter, SpecFromIter, SpecFromIterNested}; + +/// Specialization marker for collecting an iterator pipeline into a Vec while reusing the +/// source allocation, i.e. executing the pipeline in place. +/// +/// The SourceIter parent trait is necessary for the specializing function to access the allocation +/// which is to be reused. But it is not sufficient for the specialization to be valid. See +/// additional bounds on the impl. +#[rustc_unsafe_specialization_marker] +pub (super) trait SourceIterMarker: SourceIter {} + +// The std-internal SourceIter/InPlaceIterable traits are only implemented by chains of +// Adapter>> (all owned by core/std). Additional bounds +// on the adapter implementations (beyond `impl Trait for Adapter`) only depend on other +// traits already marked as specialization traits (Copy, TrustedRandomAccess, FusedIterator). +// I.e. the marker does not depend on lifetimes of user-supplied types. Modulo the Copy hole, which +// several other specializations already depend on. +impl SourceIterMarker for T where T: SourceIter + InPlaceIterable {} + +impl SpecFromIter for Vec + where + I: Iterator + SourceIterMarker, +{ + default fn from_iter(mut iterator: I) -> Self { + // Additional requirements which cannot expressed via trait bounds. We rely on const eval + // instead: + // a) no ZSTs as there would be no allocation to reuse and pointer arithmetic would panic + // b) size match as required by Alloc contract + // c) alignments match as required by Alloc contract + if mem::size_of::() == 0 + || mem::size_of::() + != mem::size_of::<<::Source as AsIntoIter>::Item>() + || mem::align_of::() + != mem::align_of::<<::Source as AsIntoIter>::Item>() + { + // fallback to more generic implementations + return SpecFromIterNested::from_iter(iterator); + } + + let (src_buf, src_ptr, dst_buf, dst_end, cap) = unsafe { + let inner = iterator.as_inner().as_into_iter(); + ( + inner.buf.as_ptr(), + inner.ptr, + inner.buf.as_ptr() as *mut T, + inner.end as *const T, + inner.cap, + ) + }; + + // use try-fold since + // - it vectorizes better for some iterator adapters + // - unlike most internal iteration methods, it only takes a &mut self + // - it lets us thread the write pointer through its innards and get it back in the end + let sink = InPlaceDrop { inner: dst_buf, dst: dst_buf }; + let sink = iterator + .try_fold::<_, _, Result<_, !>>(sink, write_in_place_with_drop(dst_end)) + .unwrap(); + // iteration succeeded, don't drop head + let dst = ManuallyDrop::new(sink).dst; + + let src = unsafe { iterator.as_inner().as_into_iter() }; + // check if SourceIter contract was upheld + // caveat: if they weren't we may not even make it to this point + debug_assert_eq!(src_buf, src.buf.as_ptr()); + // check InPlaceIterable contract. This is only possible if the iterator advanced the + // source pointer at all. If it uses unchecked access via TrustedRandomAccess + // then the source pointer will stay in its initial position and we can't use it as reference + if src.ptr != src_ptr { + debug_assert!( + dst as *const _ <= src.ptr, + "InPlaceIterable contract violation, write pointer advanced beyond read pointer" + ); + } + + // drop any remaining values at the tail of the source + src.drop_remaining(); + // but prevent drop of the allocation itself once IntoIter goes out of scope + src.forget_allocation(); + + let vec = unsafe { + let len = dst.offset_from(dst_buf) as usize; + Vec::from_raw_parts(dst_buf, len, cap) + }; + + vec + } +} + +fn write_in_place_with_drop( + src_end: *const T, +) -> impl FnMut(InPlaceDrop, T) -> Result, !> { + move |mut sink, item| { + unsafe { + // the InPlaceIterable contract cannot be verified precisely here since + // try_fold has an exclusive reference to the source pointer + // all we can do is check if it's still in range + debug_assert!(sink.dst as *const _ <= src_end, "InPlaceIterable contract violation"); + ptr::write(sink.dst, item); + sink.dst = sink.dst.add(1); + } + Ok(sink) + } +} -- cgit 1.4.1-3-g733a5 From dc46013248ecb8b0d3d29581c1734dd2ecd42b0d Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 01:07:34 +0000 Subject: refactor: moved PartialEq into partial_eq --- library/alloc/src/vec/mod.rs | 41 ++--------------------------------- library/alloc/src/vec/partial_eq.rs | 43 +++++++++++++++++++++++++++++++++++++ 2 files changed, 45 insertions(+), 39 deletions(-) create mode 100644 library/alloc/src/vec/partial_eq.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index bd71d7004b9..a862a979d3b 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -103,6 +103,8 @@ mod is_zero; mod source_iter_marker; +mod partial_eq; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -2615,45 +2617,6 @@ impl<'a, T: Copy + 'a, A: Allocator + 'a> Extend<&'a T> for Vec { } } -macro_rules! __impl_slice_eq1 { - ([$($vars:tt)*] $lhs:ty, $rhs:ty $(where $ty:ty: $bound:ident)?, #[$stability:meta]) => { - #[$stability] - impl PartialEq<$rhs> for $lhs - where - T: PartialEq, - $($ty: $bound)? - { - #[inline] - fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } - #[inline] - fn ne(&self, other: &$rhs) -> bool { self[..] != other[..] } - } - } -} - -__impl_slice_eq1! { [A: Allocator] Vec, Vec, #[stable(feature = "rust1", since = "1.0.0")] } -__impl_slice_eq1! { [A: Allocator] Vec, &[U], #[stable(feature = "rust1", since = "1.0.0")] } -__impl_slice_eq1! { [A: Allocator] Vec, &mut [U], #[stable(feature = "rust1", since = "1.0.0")] } -__impl_slice_eq1! { [A: Allocator] &[T], Vec, #[stable(feature = "partialeq_vec_for_ref_slice", since = "1.46.0")] } -__impl_slice_eq1! { [A: Allocator] &mut [T], Vec, #[stable(feature = "partialeq_vec_for_ref_slice", since = "1.46.0")] } -__impl_slice_eq1! { [A: Allocator] Vec, [U], #[stable(feature = "partialeq_vec_for_slice", since = "1.48.0")] } -__impl_slice_eq1! { [A: Allocator] [T], Vec, #[stable(feature = "partialeq_vec_for_slice", since = "1.48.0")] } -__impl_slice_eq1! { [A: Allocator] Cow<'_, [T]>, Vec where T: Clone, #[stable(feature = "rust1", since = "1.0.0")] } -__impl_slice_eq1! { [] Cow<'_, [T]>, &[U] where T: Clone, #[stable(feature = "rust1", since = "1.0.0")] } -__impl_slice_eq1! { [] Cow<'_, [T]>, &mut [U] where T: Clone, #[stable(feature = "rust1", since = "1.0.0")] } -__impl_slice_eq1! { [A: Allocator, const N: usize] Vec, [U; N], #[stable(feature = "rust1", since = "1.0.0")] } -__impl_slice_eq1! { [A: Allocator, const N: usize] Vec, &[U; N], #[stable(feature = "rust1", since = "1.0.0")] } - -// NOTE: some less important impls are omitted to reduce code bloat -// FIXME(Centril): Reconsider this? -//__impl_slice_eq1! { [const N: usize] Vec, &mut [B; N], } -//__impl_slice_eq1! { [const N: usize] [A; N], Vec, } -//__impl_slice_eq1! { [const N: usize] &[A; N], Vec, } -//__impl_slice_eq1! { [const N: usize] &mut [A; N], Vec, } -//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, [B; N], } -//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, &[B; N], } -//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, &mut [B; N], } - /// Implements comparison of vectors, [lexicographically](core::cmp::Ord#lexicographical-comparison). #[stable(feature = "rust1", since = "1.0.0")] impl PartialOrd for Vec { diff --git a/library/alloc/src/vec/partial_eq.rs b/library/alloc/src/vec/partial_eq.rs new file mode 100644 index 00000000000..617f0404439 --- /dev/null +++ b/library/alloc/src/vec/partial_eq.rs @@ -0,0 +1,43 @@ +use crate::alloc::{Allocator}; +use crate::borrow::Cow; + +use super::{Vec}; + +macro_rules! __impl_slice_eq1 { + ([$($vars:tt)*] $lhs:ty, $rhs:ty $(where $ty:ty: $bound:ident)?, #[$stability:meta]) => { + #[$stability] + impl PartialEq<$rhs> for $lhs + where + T: PartialEq, + $($ty: $bound)? + { + #[inline] + fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } + #[inline] + fn ne(&self, other: &$rhs) -> bool { self[..] != other[..] } + } + } +} + +__impl_slice_eq1! { [A: Allocator] Vec, Vec, #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [A: Allocator] Vec, &[U], #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [A: Allocator] Vec, &mut [U], #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [A: Allocator] &[T], Vec, #[stable(feature = "partialeq_vec_for_ref_slice", since = "1.46.0")] } +__impl_slice_eq1! { [A: Allocator] &mut [T], Vec, #[stable(feature = "partialeq_vec_for_ref_slice", since = "1.46.0")] } +__impl_slice_eq1! { [A: Allocator] Vec, [U], #[stable(feature = "partialeq_vec_for_slice", since = "1.48.0")] } +__impl_slice_eq1! { [A: Allocator] [T], Vec, #[stable(feature = "partialeq_vec_for_slice", since = "1.48.0")] } +__impl_slice_eq1! { [A: Allocator] Cow<'_, [T]>, Vec where T: Clone, #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [] Cow<'_, [T]>, &[U] where T: Clone, #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [] Cow<'_, [T]>, &mut [U] where T: Clone, #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [A: Allocator, const N: usize] Vec, [U; N], #[stable(feature = "rust1", since = "1.0.0")] } +__impl_slice_eq1! { [A: Allocator, const N: usize] Vec, &[U; N], #[stable(feature = "rust1", since = "1.0.0")] } + +// NOTE: some less important impls are omitted to reduce code bloat +// FIXME(Centril): Reconsider this? +//__impl_slice_eq1! { [const N: usize] Vec, &mut [B; N], } +//__impl_slice_eq1! { [const N: usize] [A; N], Vec, } +//__impl_slice_eq1! { [const N: usize] &[A; N], Vec, } +//__impl_slice_eq1! { [const N: usize] &mut [A; N], Vec, } +//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, [B; N], } +//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, &[B; N], } +//__impl_slice_eq1! { [const N: usize] Cow<'a, [A]>, &mut [B; N], } -- cgit 1.4.1-3-g733a5 From a2f4bc0d181f6aaee7b43fc37e7f16bd400d6b2c Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 01:14:31 +0000 Subject: refactor: moved SpecFromElem to spec_from_elem.rs --- library/alloc/src/vec/mod.rs | 59 +++----------------------------- library/alloc/src/vec/spec_from_elem.rs | 60 +++++++++++++++++++++++++++++++++ 2 files changed, 64 insertions(+), 55 deletions(-) create mode 100644 library/alloc/src/vec/spec_from_elem.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index a862a979d3b..ae1736d8d3c 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -105,6 +105,10 @@ mod source_iter_marker; mod partial_eq; +use self::spec_from_elem::SpecFromElem; + +mod spec_from_elem; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -1995,61 +1999,6 @@ pub fn from_elem_in(elem: T, n: usize, alloc: A) -> Vec< ::from_elem(elem, n, alloc) } -// Specialization trait used for Vec::from_elem -trait SpecFromElem: Sized { - fn from_elem(elem: Self, n: usize, alloc: A) -> Vec; -} - -impl SpecFromElem for T { - default fn from_elem(elem: Self, n: usize, alloc: A) -> Vec { - let mut v = Vec::with_capacity_in(n, alloc); - v.extend_with(n, ExtendElement(elem)); - v - } -} - -impl SpecFromElem for i8 { - #[inline] - fn from_elem(elem: i8, n: usize, alloc: A) -> Vec { - if elem == 0 { - return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; - } - unsafe { - let mut v = Vec::with_capacity_in(n, alloc); - ptr::write_bytes(v.as_mut_ptr(), elem as u8, n); - v.set_len(n); - v - } - } -} - -impl SpecFromElem for u8 { - #[inline] - fn from_elem(elem: u8, n: usize, alloc: A) -> Vec { - if elem == 0 { - return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; - } - unsafe { - let mut v = Vec::with_capacity_in(n, alloc); - ptr::write_bytes(v.as_mut_ptr(), elem, n); - v.set_len(n); - v - } - } -} - -impl SpecFromElem for T { - #[inline] - fn from_elem(elem: T, n: usize, alloc: A) -> Vec { - if elem.is_zero() { - return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; - } - let mut v = Vec::with_capacity_in(n, alloc); - v.extend_with(n, ExtendElement(elem)); - v - } -} - //////////////////////////////////////////////////////////////////////////////// // Common trait implementations for Vec //////////////////////////////////////////////////////////////////////////////// diff --git a/library/alloc/src/vec/spec_from_elem.rs b/library/alloc/src/vec/spec_from_elem.rs new file mode 100644 index 00000000000..ef89054ea13 --- /dev/null +++ b/library/alloc/src/vec/spec_from_elem.rs @@ -0,0 +1,60 @@ +use crate::alloc::{Allocator}; +use crate::raw_vec::RawVec; +use core::ptr::{self}; + +use super::{Vec, IsZero, ExtendElement}; + +// Specialization trait used for Vec::from_elem +pub(super) trait SpecFromElem: Sized { + fn from_elem(elem: Self, n: usize, alloc: A) -> Vec; +} + +impl SpecFromElem for T { + default fn from_elem(elem: Self, n: usize, alloc: A) -> Vec { + let mut v = Vec::with_capacity_in(n, alloc); + v.extend_with(n, ExtendElement(elem)); + v + } +} + +impl SpecFromElem for i8 { + #[inline] + fn from_elem(elem: i8, n: usize, alloc: A) -> Vec { + if elem == 0 { + return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; + } + unsafe { + let mut v = Vec::with_capacity_in(n, alloc); + ptr::write_bytes(v.as_mut_ptr(), elem as u8, n); + v.set_len(n); + v + } + } +} + +impl SpecFromElem for u8 { + #[inline] + fn from_elem(elem: u8, n: usize, alloc: A) -> Vec { + if elem == 0 { + return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; + } + unsafe { + let mut v = Vec::with_capacity_in(n, alloc); + ptr::write_bytes(v.as_mut_ptr(), elem, n); + v.set_len(n); + v + } + } +} + +impl SpecFromElem for T { + #[inline] + fn from_elem(elem: T, n: usize, alloc: A) -> Vec { + if elem.is_zero() { + return Vec { buf: RawVec::with_capacity_zeroed_in(n, alloc), len: n }; + } + let mut v = Vec::with_capacity_in(n, alloc); + v.extend_with(n, ExtendElement(elem)); + v + } +} \ No newline at end of file -- cgit 1.4.1-3-g733a5 From a3f3fc5aedc9636ea580d8241746e06db6031270 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 01:21:51 +0000 Subject: refactor: moved SetLenOnDrop to set_len_on_drop --- library/alloc/src/vec/mod.rs | 33 ++++---------------------------- library/alloc/src/vec/set_len_on_drop.rs | 28 +++++++++++++++++++++++++++ 2 files changed, 32 insertions(+), 29 deletions(-) create mode 100644 library/alloc/src/vec/set_len_on_drop.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index ae1736d8d3c..62ca5b950ce 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -109,6 +109,10 @@ use self::spec_from_elem::SpecFromElem; mod spec_from_elem; +use self::set_len_on_drop::SetLenOnDrop; + +mod set_len_on_drop; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -1911,35 +1915,6 @@ impl Vec { } } -// Set the length of the vec when the `SetLenOnDrop` value goes out of scope. -// -// The idea is: The length field in SetLenOnDrop is a local variable -// that the optimizer will see does not alias with any stores through the Vec's data -// pointer. This is a workaround for alias analysis issue #32155 -struct SetLenOnDrop<'a> { - len: &'a mut usize, - local_len: usize, -} - -impl<'a> SetLenOnDrop<'a> { - #[inline] - fn new(len: &'a mut usize) -> Self { - SetLenOnDrop { local_len: *len, len } - } - - #[inline] - fn increment_len(&mut self, increment: usize) { - self.local_len += increment; - } -} - -impl Drop for SetLenOnDrop<'_> { - #[inline] - fn drop(&mut self) { - *self.len = self.local_len; - } -} - impl Vec { /// Removes consecutive repeated elements in the vector according to the /// [`PartialEq`] trait implementation. diff --git a/library/alloc/src/vec/set_len_on_drop.rs b/library/alloc/src/vec/set_len_on_drop.rs new file mode 100644 index 00000000000..8b66bc81212 --- /dev/null +++ b/library/alloc/src/vec/set_len_on_drop.rs @@ -0,0 +1,28 @@ +// Set the length of the vec when the `SetLenOnDrop` value goes out of scope. +// +// The idea is: The length field in SetLenOnDrop is a local variable +// that the optimizer will see does not alias with any stores through the Vec's data +// pointer. This is a workaround for alias analysis issue #32155 +pub(super) struct SetLenOnDrop<'a> { + len: &'a mut usize, + local_len: usize, +} + +impl<'a> SetLenOnDrop<'a> { + #[inline] + pub(super) fn new(len: &'a mut usize) -> Self { + SetLenOnDrop { local_len: *len, len } + } + + #[inline] + pub(super) fn increment_len(&mut self, increment: usize) { + self.local_len += increment; + } +} + +impl Drop for SetLenOnDrop<'_> { + #[inline] + fn drop(&mut self) { + *self.len = self.local_len; + } +} -- cgit 1.4.1-3-g733a5 From 9e08ce7190dd63afc3e5a12f89134c760566513a Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 01:26:52 +0000 Subject: refactor: moved InPlaceDrop into in_place_drop.rs --- library/alloc/src/vec/in_place_drop.rs | 24 ++++++++++++++++++++++++ library/alloc/src/vec/mod.rs | 26 ++++---------------------- 2 files changed, 28 insertions(+), 22 deletions(-) create mode 100644 library/alloc/src/vec/in_place_drop.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/in_place_drop.rs b/library/alloc/src/vec/in_place_drop.rs new file mode 100644 index 00000000000..3a0ecc529c0 --- /dev/null +++ b/library/alloc/src/vec/in_place_drop.rs @@ -0,0 +1,24 @@ +use core::ptr::{self}; +use core::slice::{self}; + +// A helper struct for in-place iteration that drops the destination slice of iteration, +// i.e. the head. The source slice (the tail) is dropped by IntoIter. +pub (super) struct InPlaceDrop { + pub (super) inner: *mut T, + pub (super) dst: *mut T, +} + +impl InPlaceDrop { + fn len(&self) -> usize { + unsafe { self.dst.offset_from(self.inner) as usize } + } +} + +impl Drop for InPlaceDrop { + #[inline] + fn drop(&mut self) { + unsafe { + ptr::drop_in_place(slice::from_raw_parts_mut(self.inner, self.len())); + } + } +} diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 62ca5b950ce..08a920a9c60 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -113,6 +113,10 @@ use self::set_len_on_drop::SetLenOnDrop; mod set_len_on_drop; +use self::in_place_drop::InPlaceDrop; + +mod in_place_drop; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -2233,28 +2237,6 @@ where } } -// A helper struct for in-place iteration that drops the destination slice of iteration, -// i.e. the head. The source slice (the tail) is dropped by IntoIter. -struct InPlaceDrop { - inner: *mut T, - dst: *mut T, -} - -impl InPlaceDrop { - fn len(&self) -> usize { - unsafe { self.dst.offset_from(self.inner) as usize } - } -} - -impl Drop for InPlaceDrop { - #[inline] - fn drop(&mut self) { - unsafe { - ptr::drop_in_place(slice::from_raw_parts_mut(self.inner, self.len())); - } - } -} - impl SpecFromIter> for Vec { fn from_iter(iterator: IntoIter) -> Self { // A common case is passing a vector into a function which immediately -- cgit 1.4.1-3-g733a5 From 56d82b3dcc73e227dd2fa4dd4a8ef8d96ce75805 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 01:30:20 +0000 Subject: refactor: moved SpecFromIterNested to spec_from_iter_nested.rs --- library/alloc/src/vec/mod.rs | 56 ++------------------------ library/alloc/src/vec/spec_from_iter_nested.rs | 56 ++++++++++++++++++++++++++ 2 files changed, 60 insertions(+), 52 deletions(-) create mode 100644 library/alloc/src/vec/spec_from_iter_nested.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 08a920a9c60..438246ab4cb 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -117,6 +117,10 @@ use self::in_place_drop::InPlaceDrop; mod in_place_drop; +use self::spec_from_iter_nested::SpecFromIterNested; + +mod spec_from_iter_nested; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -2176,58 +2180,6 @@ trait SpecFromIter { fn from_iter(iter: I) -> Self; } -/// Another specialization trait for Vec::from_iter -/// necessary to manually prioritize overlapping specializations -/// see [`SpecFromIter`] for details. -trait SpecFromIterNested { - fn from_iter(iter: I) -> Self; -} - -impl SpecFromIterNested for Vec -where - I: Iterator, -{ - default fn from_iter(mut iterator: I) -> Self { - // Unroll the first iteration, as the vector is going to be - // expanded on this iteration in every case when the iterable is not - // empty, but the loop in extend_desugared() is not going to see the - // vector being full in the few subsequent loop iterations. - // So we get better branch prediction. - let mut vector = match iterator.next() { - None => return Vec::new(), - Some(element) => { - let (lower, _) = iterator.size_hint(); - let mut vector = Vec::with_capacity(lower.saturating_add(1)); - unsafe { - ptr::write(vector.as_mut_ptr(), element); - vector.set_len(1); - } - vector - } - }; - // must delegate to spec_extend() since extend() itself delegates - // to spec_from for empty Vecs - as SpecExtend>::spec_extend(&mut vector, iterator); - vector - } -} - -impl SpecFromIterNested for Vec -where - I: TrustedLen, -{ - fn from_iter(iterator: I) -> Self { - let mut vector = match iterator.size_hint() { - (_, Some(upper)) => Vec::with_capacity(upper), - _ => Vec::new(), - }; - // must delegate to spec_extend() since extend() itself delegates - // to spec_from for empty Vecs - vector.spec_extend(iterator); - vector - } -} - impl SpecFromIter for Vec where I: Iterator, diff --git a/library/alloc/src/vec/spec_from_iter_nested.rs b/library/alloc/src/vec/spec_from_iter_nested.rs new file mode 100644 index 00000000000..0da42844c96 --- /dev/null +++ b/library/alloc/src/vec/spec_from_iter_nested.rs @@ -0,0 +1,56 @@ +use core::ptr::{self}; +use core::iter::{TrustedLen}; + +use super::{Vec, SpecExtend}; + +/// Another specialization trait for Vec::from_iter +/// necessary to manually prioritize overlapping specializations +/// see [`SpecFromIter`] for details. +pub(super) trait SpecFromIterNested { + fn from_iter(iter: I) -> Self; +} + +impl SpecFromIterNested for Vec + where + I: Iterator, +{ + default fn from_iter(mut iterator: I) -> Self { + // Unroll the first iteration, as the vector is going to be + // expanded on this iteration in every case when the iterable is not + // empty, but the loop in extend_desugared() is not going to see the + // vector being full in the few subsequent loop iterations. + // So we get better branch prediction. + let mut vector = match iterator.next() { + None => return Vec::new(), + Some(element) => { + let (lower, _) = iterator.size_hint(); + let mut vector = Vec::with_capacity(lower.saturating_add(1)); + unsafe { + ptr::write(vector.as_mut_ptr(), element); + vector.set_len(1); + } + vector + } + }; + // must delegate to spec_extend() since extend() itself delegates + // to spec_from for empty Vecs + as SpecExtend>::spec_extend(&mut vector, iterator); + vector + } +} + +impl SpecFromIterNested for Vec + where + I: TrustedLen, +{ + fn from_iter(iterator: I) -> Self { + let mut vector = match iterator.size_hint() { + (_, Some(upper)) => Vec::with_capacity(upper), + _ => Vec::new(), + }; + // must delegate to spec_extend() since extend() itself delegates + // to spec_from for empty Vecs + vector.spec_extend(iterator); + vector + } +} -- cgit 1.4.1-3-g733a5 From d24a27797df96bb1dbc886f0997138965c5d7b50 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 01:37:10 +0000 Subject: refactor: moving SpecFromIter into spec_from_iter.rs --- library/alloc/src/vec/mod.rs | 96 ++------------------------------ library/alloc/src/vec/spec_from_iter.rs | 98 +++++++++++++++++++++++++++++++++ 2 files changed, 102 insertions(+), 92 deletions(-) create mode 100644 library/alloc/src/vec/spec_from_iter.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 438246ab4cb..dfb837d54f5 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -121,6 +121,10 @@ use self::spec_from_iter_nested::SpecFromIterNested; mod spec_from_iter_nested; +use self::spec_from_iter::SpecFromIter; + +mod spec_from_iter; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -2156,98 +2160,6 @@ impl Extend for Vec { } } -/// Specialization trait used for Vec::from_iter -/// -/// ## The delegation graph: -/// -/// ```text -/// +-------------+ -/// |FromIterator | -/// +-+-----------+ -/// | -/// v -/// +-+-------------------------------+ +---------------------+ -/// |SpecFromIter +---->+SpecFromIterNested | -/// |where I: | | |where I: | -/// | Iterator (default)----------+ | | Iterator (default) | -/// | vec::IntoIter | | | TrustedLen | -/// | SourceIterMarker---fallback-+ | | | -/// | slice::Iter | | | -/// | Iterator | +---------------------+ -/// +---------------------------------+ -/// ``` -trait SpecFromIter { - fn from_iter(iter: I) -> Self; -} - -impl SpecFromIter for Vec -where - I: Iterator, -{ - default fn from_iter(iterator: I) -> Self { - SpecFromIterNested::from_iter(iterator) - } -} - -impl SpecFromIter> for Vec { - fn from_iter(iterator: IntoIter) -> Self { - // A common case is passing a vector into a function which immediately - // re-collects into a vector. We can short circuit this if the IntoIter - // has not been advanced at all. - // When it has been advanced We can also reuse the memory and move the data to the front. - // But we only do so when the resulting Vec wouldn't have more unused capacity - // than creating it through the generic FromIterator implementation would. That limitation - // is not strictly necessary as Vec's allocation behavior is intentionally unspecified. - // But it is a conservative choice. - let has_advanced = iterator.buf.as_ptr() as *const _ != iterator.ptr; - if !has_advanced || iterator.len() >= iterator.cap / 2 { - unsafe { - let it = ManuallyDrop::new(iterator); - if has_advanced { - ptr::copy(it.ptr, it.buf.as_ptr(), it.len()); - } - return Vec::from_raw_parts(it.buf.as_ptr(), it.len(), it.cap); - } - } - - let mut vec = Vec::new(); - // must delegate to spec_extend() since extend() itself delegates - // to spec_from for empty Vecs - vec.spec_extend(iterator); - vec - } -} - -impl<'a, T: 'a, I> SpecFromIter<&'a T, I> for Vec -where - I: Iterator, - T: Clone, -{ - default fn from_iter(iterator: I) -> Self { - SpecFromIter::from_iter(iterator.cloned()) - } -} - -// This utilizes `iterator.as_slice().to_vec()` since spec_extend -// must take more steps to reason about the final capacity + length -// and thus do more work. `to_vec()` directly allocates the correct amount -// and fills it exactly. -impl<'a, T: 'a + Clone> SpecFromIter<&'a T, slice::Iter<'a, T>> for Vec { - #[cfg(not(test))] - fn from_iter(iterator: slice::Iter<'a, T>) -> Self { - iterator.as_slice().to_vec() - } - - // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is - // required for this method definition, is not available. Instead use the - // `slice::to_vec` function which is only available with cfg(test) - // NB see the slice::hack module in slice.rs for more information - #[cfg(test)] - fn from_iter(iterator: slice::Iter<'a, T>) -> Self { - crate::slice::to_vec(iterator.as_slice(), Global) - } -} - // Specialization trait used for Vec::extend trait SpecExtend { fn spec_extend(&mut self, iter: I); diff --git a/library/alloc/src/vec/spec_from_iter.rs b/library/alloc/src/vec/spec_from_iter.rs new file mode 100644 index 00000000000..bf07fc97f89 --- /dev/null +++ b/library/alloc/src/vec/spec_from_iter.rs @@ -0,0 +1,98 @@ +use crate::alloc::Global; +use core::mem::{ManuallyDrop}; +use core::ptr::{self}; +use core::slice::{self}; + +use super::{Vec, IntoIter, SpecFromIterNested, SpecExtend}; + +/// Specialization trait used for Vec::from_iter +/// +/// ## The delegation graph: +/// +/// ```text +/// +-------------+ +/// |FromIterator | +/// +-+-----------+ +/// | +/// v +/// +-+-------------------------------+ +---------------------+ +/// |SpecFromIter +---->+SpecFromIterNested | +/// |where I: | | |where I: | +/// | Iterator (default)----------+ | | Iterator (default) | +/// | vec::IntoIter | | | TrustedLen | +/// | SourceIterMarker---fallback-+ | | | +/// | slice::Iter | | | +/// | Iterator | +---------------------+ +/// +---------------------------------+ +/// ``` +pub(super) trait SpecFromIter { + fn from_iter(iter: I) -> Self; +} + +impl SpecFromIter for Vec + where + I: Iterator, +{ + default fn from_iter(iterator: I) -> Self { + SpecFromIterNested::from_iter(iterator) + } +} + +impl SpecFromIter> for Vec { + fn from_iter(iterator: IntoIter) -> Self { + // A common case is passing a vector into a function which immediately + // re-collects into a vector. We can short circuit this if the IntoIter + // has not been advanced at all. + // When it has been advanced We can also reuse the memory and move the data to the front. + // But we only do so when the resulting Vec wouldn't have more unused capacity + // than creating it through the generic FromIterator implementation would. That limitation + // is not strictly necessary as Vec's allocation behavior is intentionally unspecified. + // But it is a conservative choice. + let has_advanced = iterator.buf.as_ptr() as *const _ != iterator.ptr; + if !has_advanced || iterator.len() >= iterator.cap / 2 { + unsafe { + let it = ManuallyDrop::new(iterator); + if has_advanced { + ptr::copy(it.ptr, it.buf.as_ptr(), it.len()); + } + return Vec::from_raw_parts(it.buf.as_ptr(), it.len(), it.cap); + } + } + + let mut vec = Vec::new(); + // must delegate to spec_extend() since extend() itself delegates + // to spec_from for empty Vecs + vec.spec_extend(iterator); + vec + } +} + +impl<'a, T: 'a, I> SpecFromIter<&'a T, I> for Vec + where + I: Iterator, + T: Clone, +{ + default fn from_iter(iterator: I) -> Self { + SpecFromIter::from_iter(iterator.cloned()) + } +} + +// This utilizes `iterator.as_slice().to_vec()` since spec_extend +// must take more steps to reason about the final capacity + length +// and thus do more work. `to_vec()` directly allocates the correct amount +// and fills it exactly. +impl<'a, T: 'a + Clone> SpecFromIter<&'a T, slice::Iter<'a, T>> for Vec { + #[cfg(not(test))] + fn from_iter(iterator: slice::Iter<'a, T>) -> Self { + iterator.as_slice().to_vec() + } + + // HACK(japaric): with cfg(test) the inherent `[T]::to_vec` method, which is + // required for this method definition, is not available. Instead use the + // `slice::to_vec` function which is only available with cfg(test) + // NB see the slice::hack module in slice.rs for more information + #[cfg(test)] + fn from_iter(iterator: slice::Iter<'a, T>) -> Self { + crate::slice::to_vec(iterator.as_slice(), Global) + } +} -- cgit 1.4.1-3-g733a5 From bd49a60f2943c313adae8582f266b875c9b7eaa9 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 01:41:44 +0000 Subject: refactor: moved SpecExtend into spec_extend.rs --- library/alloc/src/vec/mod.rs | 84 +++--------------------------------- library/alloc/src/vec/spec_extend.rs | 82 +++++++++++++++++++++++++++++++++++ 2 files changed, 87 insertions(+), 79 deletions(-) create mode 100644 library/alloc/src/vec/spec_extend.rs (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index dfb837d54f5..32470941755 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -59,9 +59,7 @@ use core::convert::TryFrom; use core::fmt; use core::hash::{Hash, Hasher}; use core::intrinsics::{arith_offset, assume}; -use core::iter::{ - FromIterator, TrustedLen, -}; +use core::iter::{FromIterator}; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, MaybeUninit}; use core::ops::{self, Index, IndexMut, Range, RangeBounds}; @@ -125,6 +123,10 @@ use self::spec_from_iter::SpecFromIter; mod spec_from_iter; +use self::spec_extend::SpecExtend; + +mod spec_extend; + /// A contiguous growable array type, written `Vec` but pronounced 'vector'. /// /// # Examples @@ -2160,82 +2162,6 @@ impl Extend for Vec { } } -// Specialization trait used for Vec::extend -trait SpecExtend { - fn spec_extend(&mut self, iter: I); -} - -impl SpecExtend for Vec -where - I: Iterator, -{ - default fn spec_extend(&mut self, iter: I) { - self.extend_desugared(iter) - } -} - -impl SpecExtend for Vec -where - I: TrustedLen, -{ - default fn spec_extend(&mut self, iterator: I) { - // This is the case for a TrustedLen iterator. - let (low, high) = iterator.size_hint(); - if let Some(high_value) = high { - debug_assert_eq!( - low, - high_value, - "TrustedLen iterator's size hint is not exact: {:?}", - (low, high) - ); - } - if let Some(additional) = high { - self.reserve(additional); - unsafe { - let mut ptr = self.as_mut_ptr().add(self.len()); - let mut local_len = SetLenOnDrop::new(&mut self.len); - iterator.for_each(move |element| { - ptr::write(ptr, element); - ptr = ptr.offset(1); - // NB can't overflow since we would have had to alloc the address space - local_len.increment_len(1); - }); - } - } else { - self.extend_desugared(iterator) - } - } -} - -impl SpecExtend> for Vec { - fn spec_extend(&mut self, mut iterator: IntoIter) { - unsafe { - self.append_elements(iterator.as_slice() as _); - } - iterator.ptr = iterator.end; - } -} - -impl<'a, T: 'a, I, A: Allocator + 'a> SpecExtend<&'a T, I> for Vec -where - I: Iterator, - T: Clone, -{ - default fn spec_extend(&mut self, iterator: I) { - self.spec_extend(iterator.cloned()) - } -} - -impl<'a, T: 'a, A: Allocator + 'a> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec -where - T: Copy, -{ - fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) { - let slice = iterator.as_slice(); - unsafe { self.append_elements(slice) }; - } -} - impl Vec { // leaf method to which various SpecFrom/SpecExtend implementations delegate when // they have no further optimizations to apply diff --git a/library/alloc/src/vec/spec_extend.rs b/library/alloc/src/vec/spec_extend.rs new file mode 100644 index 00000000000..6959733d074 --- /dev/null +++ b/library/alloc/src/vec/spec_extend.rs @@ -0,0 +1,82 @@ +use crate::alloc::{Allocator}; +use core::iter::{TrustedLen}; +use core::slice::{self}; +use core::ptr::{self}; + +use super::{Vec, IntoIter, SetLenOnDrop}; + +// Specialization trait used for Vec::extend +pub(super) trait SpecExtend { + fn spec_extend(&mut self, iter: I); +} + +impl SpecExtend for Vec + where + I: Iterator, +{ + default fn spec_extend(&mut self, iter: I) { + self.extend_desugared(iter) + } +} + +impl SpecExtend for Vec + where + I: TrustedLen, +{ + default fn spec_extend(&mut self, iterator: I) { + // This is the case for a TrustedLen iterator. + let (low, high) = iterator.size_hint(); + if let Some(high_value) = high { + debug_assert_eq!( + low, + high_value, + "TrustedLen iterator's size hint is not exact: {:?}", + (low, high) + ); + } + if let Some(additional) = high { + self.reserve(additional); + unsafe { + let mut ptr = self.as_mut_ptr().add(self.len()); + let mut local_len = SetLenOnDrop::new(&mut self.len); + iterator.for_each(move |element| { + ptr::write(ptr, element); + ptr = ptr.offset(1); + // NB can't overflow since we would have had to alloc the address space + local_len.increment_len(1); + }); + } + } else { + self.extend_desugared(iterator) + } + } +} + +impl SpecExtend> for Vec { + fn spec_extend(&mut self, mut iterator: IntoIter) { + unsafe { + self.append_elements(iterator.as_slice() as _); + } + iterator.ptr = iterator.end; + } +} + +impl<'a, T: 'a, I, A: Allocator + 'a> SpecExtend<&'a T, I> for Vec + where + I: Iterator, + T: Clone, +{ + default fn spec_extend(&mut self, iterator: I) { + self.spec_extend(iterator.cloned()) + } +} + +impl<'a, T: 'a, A: Allocator + 'a> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec + where + T: Copy, +{ + fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) { + let slice = iterator.as_slice(); + unsafe { self.append_elements(slice) }; + } +} -- cgit 1.4.1-3-g733a5 From 6002b280f119a12631da0d1bb7e6adad53cefc95 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 01:42:29 +0000 Subject: refactor: removing // ignore-tidy-filelength --- library/alloc/src/vec/mod.rs | 1 - 1 file changed, 1 deletion(-) (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 32470941755..2947c6a299f 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -1,4 +1,3 @@ -// ignore-tidy-filelength //! A contiguous growable array type with heap-allocated contents, written //! `Vec`. //! -- cgit 1.4.1-3-g733a5 From 2de8356f60a7a9800809ab60e813fcfd4a7accf2 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 01:44:07 +0000 Subject: style: applying Rust style --- library/alloc/src/vec/cow.rs | 10 +++++----- library/alloc/src/vec/drain.rs | 8 +++----- library/alloc/src/vec/drain_filter.rs | 26 +++++++++++++------------- library/alloc/src/vec/in_place_drop.rs | 6 +++--- library/alloc/src/vec/into_iter.rs | 16 +++++++--------- library/alloc/src/vec/is_zero.rs | 2 +- library/alloc/src/vec/mod.rs | 4 ++-- library/alloc/src/vec/partial_eq.rs | 4 ++-- library/alloc/src/vec/source_iter_marker.rs | 16 +++++++--------- library/alloc/src/vec/spec_extend.rs | 26 +++++++++++++------------- library/alloc/src/vec/spec_from_elem.rs | 6 +++--- library/alloc/src/vec/spec_from_iter.rs | 14 +++++++------- library/alloc/src/vec/spec_from_iter_nested.rs | 12 ++++++------ library/alloc/src/vec/splice.rs | 4 ++-- 14 files changed, 74 insertions(+), 80 deletions(-) (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/cow.rs b/library/alloc/src/vec/cow.rs index 15942f9892d..73d15d30647 100644 --- a/library/alloc/src/vec/cow.rs +++ b/library/alloc/src/vec/cow.rs @@ -1,7 +1,7 @@ use crate::borrow::Cow; -use core::iter::{FromIterator}; +use core::iter::FromIterator; -use super::{Vec}; +use super::Vec; #[stable(feature = "cow_from_vec", since = "1.8.0")] impl<'a, T: Clone> From<&'a [T]> for Cow<'a, [T]> { @@ -26,10 +26,10 @@ impl<'a, T: Clone> From<&'a Vec> for Cow<'a, [T]> { #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T> FromIterator for Cow<'a, [T]> - where - T: Clone, +where + T: Clone, { fn from_iter>(it: I) -> Cow<'a, [T]> { Cow::Owned(FromIterator::from_iter(it)) } -} \ No newline at end of file +} diff --git a/library/alloc/src/vec/drain.rs b/library/alloc/src/vec/drain.rs index e61f17a1c30..fb32d144f87 100644 --- a/library/alloc/src/vec/drain.rs +++ b/library/alloc/src/vec/drain.rs @@ -1,13 +1,11 @@ use crate::alloc::{Allocator, Global}; -use core::iter::{ - FusedIterator, TrustedLen, -}; +use core::fmt; +use core::iter::{FusedIterator, TrustedLen}; use core::mem::{self}; use core::ptr::{self, NonNull}; use core::slice::{self}; -use core::fmt; -use super::{Vec}; +use super::Vec; /// A draining iterator for `Vec`. /// diff --git a/library/alloc/src/vec/drain_filter.rs b/library/alloc/src/vec/drain_filter.rs index 9d898c7c756..3c37c92ae44 100644 --- a/library/alloc/src/vec/drain_filter.rs +++ b/library/alloc/src/vec/drain_filter.rs @@ -1,8 +1,8 @@ +use crate::alloc::{Allocator, Global}; use core::ptr::{self}; use core::slice::{self}; -use crate::alloc::{Allocator, Global}; -use super::{Vec}; +use super::Vec; /// An iterator which uses a closure to determine if an element should be removed. /// @@ -45,8 +45,8 @@ pub struct DrainFilter< } impl DrainFilter<'_, T, F, A> - where - F: FnMut(&mut T) -> bool, +where + F: FnMut(&mut T) -> bool, { /// Returns a reference to the underlying allocator. #[unstable(feature = "allocator_api", issue = "32838")] @@ -58,8 +58,8 @@ impl DrainFilter<'_, T, F, A> #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] impl Iterator for DrainFilter<'_, T, F, A> - where - F: FnMut(&mut T) -> bool, +where + F: FnMut(&mut T) -> bool, { type Item = T; @@ -96,20 +96,20 @@ impl Iterator for DrainFilter<'_, T, F, A> #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] impl Drop for DrainFilter<'_, T, F, A> - where - F: FnMut(&mut T) -> bool, +where + F: FnMut(&mut T) -> bool, { fn drop(&mut self) { struct BackshiftOnDrop<'a, 'b, T, F, A: Allocator> - where - F: FnMut(&mut T) -> bool, + where + F: FnMut(&mut T) -> bool, { drain: &'b mut DrainFilter<'a, T, F, A>, } impl<'a, 'b, T, F, A: Allocator> Drop for BackshiftOnDrop<'a, 'b, T, F, A> - where - F: FnMut(&mut T) -> bool, + where + F: FnMut(&mut T) -> bool, { fn drop(&mut self) { unsafe { @@ -140,4 +140,4 @@ impl Drop for DrainFilter<'_, T, F, A> backshift.drain.for_each(drop); } } -} \ No newline at end of file +} diff --git a/library/alloc/src/vec/in_place_drop.rs b/library/alloc/src/vec/in_place_drop.rs index 3a0ecc529c0..354d25c2389 100644 --- a/library/alloc/src/vec/in_place_drop.rs +++ b/library/alloc/src/vec/in_place_drop.rs @@ -3,9 +3,9 @@ use core::slice::{self}; // A helper struct for in-place iteration that drops the destination slice of iteration, // i.e. the head. The source slice (the tail) is dropped by IntoIter. -pub (super) struct InPlaceDrop { - pub (super) inner: *mut T, - pub (super) dst: *mut T, +pub(super) struct InPlaceDrop { + pub(super) inner: *mut T, + pub(super) dst: *mut T, } impl InPlaceDrop { diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index c4330df4ad9..1788690d96b 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -1,14 +1,12 @@ use crate::alloc::{Allocator, Global}; use crate::raw_vec::RawVec; +use core::fmt; +use core::intrinsics::arith_offset; +use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccess}; use core::marker::PhantomData; -use core::intrinsics::{arith_offset}; use core::mem::{self}; -use core::fmt; use core::ptr::{self, NonNull}; use core::slice::{self}; -use core::iter::{ - FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccess, -}; /// An iterator that moves out of a vector. /// @@ -156,8 +154,8 @@ impl Iterator for IntoIter { } unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> Self::Item - where - Self: TrustedRandomAccess, + where + Self: TrustedRandomAccess, { // SAFETY: the caller must guarantee that `i` is in bounds of the // `Vec`, so `i` cannot overflow an `isize`, and the `self.ptr.add(i)` @@ -211,8 +209,8 @@ unsafe impl TrustedLen for IntoIter {} // T: Copy as approximation for !Drop since get_unchecked does not advance self.ptr // and thus we can't implement drop-handling unsafe impl TrustedRandomAccess for IntoIter - where - T: Copy, +where + T: Copy, { fn may_have_side_effect() -> bool { false diff --git a/library/alloc/src/vec/is_zero.rs b/library/alloc/src/vec/is_zero.rs index 961f6ca171b..b5739970b6e 100644 --- a/library/alloc/src/vec/is_zero.rs +++ b/library/alloc/src/vec/is_zero.rs @@ -68,4 +68,4 @@ unsafe impl IsZero for Option> { fn is_zero(&self) -> bool { self.is_none() } -} \ No newline at end of file +} diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index 2947c6a299f..2a83eb33fe3 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -58,7 +58,7 @@ use core::convert::TryFrom; use core::fmt; use core::hash::{Hash, Hasher}; use core::intrinsics::{arith_offset, assume}; -use core::iter::{FromIterator}; +use core::iter::FromIterator; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, MaybeUninit}; use core::ops::{self, Index, IndexMut, Range, RangeBounds}; @@ -88,9 +88,9 @@ mod drain; mod cow; +pub(crate) use self::into_iter::AsIntoIter; #[stable(feature = "rust1", since = "1.0.0")] pub use self::into_iter::IntoIter; -pub (crate) use self::into_iter::AsIntoIter; mod into_iter; diff --git a/library/alloc/src/vec/partial_eq.rs b/library/alloc/src/vec/partial_eq.rs index 617f0404439..ff90b6caf46 100644 --- a/library/alloc/src/vec/partial_eq.rs +++ b/library/alloc/src/vec/partial_eq.rs @@ -1,7 +1,7 @@ -use crate::alloc::{Allocator}; +use crate::alloc::Allocator; use crate::borrow::Cow; -use super::{Vec}; +use super::Vec; macro_rules! __impl_slice_eq1 { ([$($vars:tt)*] $lhs:ty, $rhs:ty $(where $ty:ty: $bound:ident)?, #[$stability:meta]) => { diff --git a/library/alloc/src/vec/source_iter_marker.rs b/library/alloc/src/vec/source_iter_marker.rs index eb3ae01a47e..8c0e95559fa 100644 --- a/library/alloc/src/vec/source_iter_marker.rs +++ b/library/alloc/src/vec/source_iter_marker.rs @@ -1,10 +1,8 @@ -use core::iter::{ - InPlaceIterable, SourceIter, -}; +use core::iter::{InPlaceIterable, SourceIter}; use core::mem::{self, ManuallyDrop}; use core::ptr::{self}; -use super::{Vec, InPlaceDrop, AsIntoIter, SpecFromIter, SpecFromIterNested}; +use super::{AsIntoIter, InPlaceDrop, SpecFromIter, SpecFromIterNested, Vec}; /// Specialization marker for collecting an iterator pipeline into a Vec while reusing the /// source allocation, i.e. executing the pipeline in place. @@ -13,7 +11,7 @@ use super::{Vec, InPlaceDrop, AsIntoIter, SpecFromIter, SpecFromIterNested}; /// which is to be reused. But it is not sufficient for the specialization to be valid. See /// additional bounds on the impl. #[rustc_unsafe_specialization_marker] -pub (super) trait SourceIterMarker: SourceIter {} +pub(super) trait SourceIterMarker: SourceIter {} // The std-internal SourceIter/InPlaceIterable traits are only implemented by chains of // Adapter>> (all owned by core/std). Additional bounds @@ -24,8 +22,8 @@ pub (super) trait SourceIterMarker: SourceIter {} impl SourceIterMarker for T where T: SourceIter + InPlaceIterable {} impl SpecFromIter for Vec - where - I: Iterator + SourceIterMarker, +where + I: Iterator + SourceIterMarker, { default fn from_iter(mut iterator: I) -> Self { // Additional requirements which cannot expressed via trait bounds. We rely on const eval @@ -35,9 +33,9 @@ impl SpecFromIter for Vec // c) alignments match as required by Alloc contract if mem::size_of::() == 0 || mem::size_of::() - != mem::size_of::<<::Source as AsIntoIter>::Item>() + != mem::size_of::<<::Source as AsIntoIter>::Item>() || mem::align_of::() - != mem::align_of::<<::Source as AsIntoIter>::Item>() + != mem::align_of::<<::Source as AsIntoIter>::Item>() { // fallback to more generic implementations return SpecFromIterNested::from_iter(iterator); diff --git a/library/alloc/src/vec/spec_extend.rs b/library/alloc/src/vec/spec_extend.rs index 6959733d074..b6186a7ebaf 100644 --- a/library/alloc/src/vec/spec_extend.rs +++ b/library/alloc/src/vec/spec_extend.rs @@ -1,9 +1,9 @@ -use crate::alloc::{Allocator}; -use core::iter::{TrustedLen}; -use core::slice::{self}; +use crate::alloc::Allocator; +use core::iter::TrustedLen; use core::ptr::{self}; +use core::slice::{self}; -use super::{Vec, IntoIter, SetLenOnDrop}; +use super::{IntoIter, SetLenOnDrop, Vec}; // Specialization trait used for Vec::extend pub(super) trait SpecExtend { @@ -11,8 +11,8 @@ pub(super) trait SpecExtend { } impl SpecExtend for Vec - where - I: Iterator, +where + I: Iterator, { default fn spec_extend(&mut self, iter: I) { self.extend_desugared(iter) @@ -20,8 +20,8 @@ impl SpecExtend for Vec } impl SpecExtend for Vec - where - I: TrustedLen, +where + I: TrustedLen, { default fn spec_extend(&mut self, iterator: I) { // This is the case for a TrustedLen iterator. @@ -62,9 +62,9 @@ impl SpecExtend> for Vec { } impl<'a, T: 'a, I, A: Allocator + 'a> SpecExtend<&'a T, I> for Vec - where - I: Iterator, - T: Clone, +where + I: Iterator, + T: Clone, { default fn spec_extend(&mut self, iterator: I) { self.spec_extend(iterator.cloned()) @@ -72,8 +72,8 @@ impl<'a, T: 'a, I, A: Allocator + 'a> SpecExtend<&'a T, I> for Vec } impl<'a, T: 'a, A: Allocator + 'a> SpecExtend<&'a T, slice::Iter<'a, T>> for Vec - where - T: Copy, +where + T: Copy, { fn spec_extend(&mut self, iterator: slice::Iter<'a, T>) { let slice = iterator.as_slice(); diff --git a/library/alloc/src/vec/spec_from_elem.rs b/library/alloc/src/vec/spec_from_elem.rs index ef89054ea13..de610174783 100644 --- a/library/alloc/src/vec/spec_from_elem.rs +++ b/library/alloc/src/vec/spec_from_elem.rs @@ -1,8 +1,8 @@ -use crate::alloc::{Allocator}; +use crate::alloc::Allocator; use crate::raw_vec::RawVec; use core::ptr::{self}; -use super::{Vec, IsZero, ExtendElement}; +use super::{ExtendElement, IsZero, Vec}; // Specialization trait used for Vec::from_elem pub(super) trait SpecFromElem: Sized { @@ -57,4 +57,4 @@ impl SpecFromElem for T { v.extend_with(n, ExtendElement(elem)); v } -} \ No newline at end of file +} diff --git a/library/alloc/src/vec/spec_from_iter.rs b/library/alloc/src/vec/spec_from_iter.rs index bf07fc97f89..4349d158210 100644 --- a/library/alloc/src/vec/spec_from_iter.rs +++ b/library/alloc/src/vec/spec_from_iter.rs @@ -1,9 +1,9 @@ use crate::alloc::Global; -use core::mem::{ManuallyDrop}; +use core::mem::ManuallyDrop; use core::ptr::{self}; use core::slice::{self}; -use super::{Vec, IntoIter, SpecFromIterNested, SpecExtend}; +use super::{IntoIter, SpecExtend, SpecFromIterNested, Vec}; /// Specialization trait used for Vec::from_iter /// @@ -30,8 +30,8 @@ pub(super) trait SpecFromIter { } impl SpecFromIter for Vec - where - I: Iterator, +where + I: Iterator, { default fn from_iter(iterator: I) -> Self { SpecFromIterNested::from_iter(iterator) @@ -68,9 +68,9 @@ impl SpecFromIter> for Vec { } impl<'a, T: 'a, I> SpecFromIter<&'a T, I> for Vec - where - I: Iterator, - T: Clone, +where + I: Iterator, + T: Clone, { default fn from_iter(iterator: I) -> Self { SpecFromIter::from_iter(iterator.cloned()) diff --git a/library/alloc/src/vec/spec_from_iter_nested.rs b/library/alloc/src/vec/spec_from_iter_nested.rs index 0da42844c96..6abd4ff2a3f 100644 --- a/library/alloc/src/vec/spec_from_iter_nested.rs +++ b/library/alloc/src/vec/spec_from_iter_nested.rs @@ -1,7 +1,7 @@ +use core::iter::TrustedLen; use core::ptr::{self}; -use core::iter::{TrustedLen}; -use super::{Vec, SpecExtend}; +use super::{SpecExtend, Vec}; /// Another specialization trait for Vec::from_iter /// necessary to manually prioritize overlapping specializations @@ -11,8 +11,8 @@ pub(super) trait SpecFromIterNested { } impl SpecFromIterNested for Vec - where - I: Iterator, +where + I: Iterator, { default fn from_iter(mut iterator: I) -> Self { // Unroll the first iteration, as the vector is going to be @@ -40,8 +40,8 @@ impl SpecFromIterNested for Vec } impl SpecFromIterNested for Vec - where - I: TrustedLen, +where + I: TrustedLen, { fn from_iter(iterator: I) -> Self { let mut vector = match iterator.size_hint() { diff --git a/library/alloc/src/vec/splice.rs b/library/alloc/src/vec/splice.rs index 86b2fa0968e..0a27b5b62ec 100644 --- a/library/alloc/src/vec/splice.rs +++ b/library/alloc/src/vec/splice.rs @@ -2,7 +2,7 @@ use crate::alloc::{Allocator, Global}; use core::ptr::{self}; use core::slice::{self}; -use super::{Vec, Drain}; +use super::{Drain, Vec}; /// A splicing iterator for `Vec`. /// @@ -130,4 +130,4 @@ impl Drain<'_, T, A> { } self.tail_start = new_tail_start; } -} \ No newline at end of file +} -- cgit 1.4.1-3-g733a5 From 80f10d7aa7b3e3bf9a47de6ef2a9f4439d993c48 Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 13:27:03 +0000 Subject: fix: moved import into #[cfg(test)] --- library/alloc/src/vec/spec_from_iter.rs | 3 +-- 1 file changed, 1 insertion(+), 2 deletions(-) (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/spec_from_iter.rs b/library/alloc/src/vec/spec_from_iter.rs index 4349d158210..bbfcc68daef 100644 --- a/library/alloc/src/vec/spec_from_iter.rs +++ b/library/alloc/src/vec/spec_from_iter.rs @@ -1,4 +1,3 @@ -use crate::alloc::Global; use core::mem::ManuallyDrop; use core::ptr::{self}; use core::slice::{self}; @@ -93,6 +92,6 @@ impl<'a, T: 'a + Clone> SpecFromIter<&'a T, slice::Iter<'a, T>> for Vec { // NB see the slice::hack module in slice.rs for more information #[cfg(test)] fn from_iter(iterator: slice::Iter<'a, T>) -> Self { - crate::slice::to_vec(iterator.as_slice(), Global) + crate::slice::to_vec(iterator.as_slice(), crate::alloc::Global) } } -- cgit 1.4.1-3-g733a5 From f7a6f0cae3f6850ad84b8fa6ba6b9f06ae94c27d Mon Sep 17 00:00:00 2001 From: C Date: Sat, 5 Dec 2020 13:47:27 +0000 Subject: docs: fixing references --- library/alloc/src/vec/into_iter.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index 1788690d96b..99ecec648ad 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -10,7 +10,7 @@ use core::slice::{self}; /// An iterator that moves out of a vector. /// -/// This `struct` is created by the `into_iter` method on [`Vec`] (provided +/// This `struct` is created by the `into_iter` method on [`super::Vec`] (provided /// by the [`IntoIterator`] trait). /// /// # Example -- cgit 1.4.1-3-g733a5 From 16834a8f52853be76cf4a96de120042f2a4a96a2 Mon Sep 17 00:00:00 2001 From: Mara Bos Date: Wed, 30 Dec 2020 15:35:02 +0000 Subject: Fix rustdoc link in vec/into_iter.rs. --- library/alloc/src/vec/into_iter.rs | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'library/alloc/src/vec') diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index 99ecec648ad..f131d06bb18 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -10,8 +10,8 @@ use core::slice::{self}; /// An iterator that moves out of a vector. /// -/// This `struct` is created by the `into_iter` method on [`super::Vec`] (provided -/// by the [`IntoIterator`] trait). +/// This `struct` is created by the `into_iter` method on [`Vec`](super::Vec) +/// (provided by the [`IntoIterator`] trait). /// /// # Example /// -- cgit 1.4.1-3-g733a5