diff options
Diffstat (limited to 'rust/alloc/vec/mod.rs')
| -rw-r--r-- | rust/alloc/vec/mod.rs | 464 |
1 files changed, 355 insertions, 109 deletions
diff --git a/rust/alloc/vec/mod.rs b/rust/alloc/vec/mod.rs index fe4fff5064bc..94995913566b 100644 --- a/rust/alloc/vec/mod.rs +++ b/rust/alloc/vec/mod.rs @@ -61,12 +61,12 @@ use core::cmp::Ordering; use core::convert::TryFrom; use core::fmt; use core::hash::{Hash, Hasher}; -use core::intrinsics::{arith_offset, assume}; +use core::intrinsics::assume; use core::iter; #[cfg(not(no_global_oom_handling))] use core::iter::FromIterator; use core::marker::PhantomData; -use core::mem::{self, ManuallyDrop, MaybeUninit}; +use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties}; use core::ops::{self, Index, IndexMut, Range, RangeBounds}; use core::ptr::{self, NonNull}; use core::slice::{self, SliceIndex}; @@ -75,7 +75,7 @@ use crate::alloc::{Allocator, Global}; #[cfg(not(no_borrow))] use crate::borrow::{Cow, ToOwned}; use crate::boxed::Box; -use crate::collections::TryReserveError; +use crate::collections::{TryReserveError, TryReserveErrorKind}; use crate::raw_vec::RawVec; #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] @@ -127,7 +127,7 @@ use self::set_len_on_drop::SetLenOnDrop; mod set_len_on_drop; #[cfg(not(no_global_oom_handling))] -use self::in_place_drop::InPlaceDrop; +use self::in_place_drop::{InPlaceDrop, InPlaceDstBufDrop}; #[cfg(not(no_global_oom_handling))] mod in_place_drop; @@ -169,7 +169,7 @@ mod spec_extend; /// vec[0] = 7; /// assert_eq!(vec[0], 7); /// -/// vec.extend([1, 2, 3].iter().copied()); +/// vec.extend([1, 2, 3]); /// /// for x in &vec { /// println!("{x}"); @@ -428,17 +428,25 @@ impl<T> Vec<T> { Vec { buf: RawVec::NEW, len: 0 } } - /// Constructs a new, empty `Vec<T>` with the specified capacity. + /// Constructs a new, empty `Vec<T>` with at least the specified capacity. /// - /// The vector will be able to hold exactly `capacity` elements without - /// reallocating. If `capacity` is 0, the vector will not allocate. + /// The vector will be able to hold at least `capacity` elements without + /// reallocating. This method is allowed to allocate for more elements than + /// `capacity`. 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 + /// minimum *capacity* specified, the vector will have a zero *length*. For + /// an explanation of the difference between length and capacity, see /// *[Capacity and reallocation]*. /// + /// If it is important to know the exact allocated capacity of a `Vec`, + /// always use the [`capacity`] method after construction. + /// + /// For `Vec<T>` where `T` is a zero-sized type, there will be no allocation + /// and the capacity will always be `usize::MAX`. + /// /// [Capacity and reallocation]: #capacity-and-reallocation + /// [`capacity`]: Vec::capacity /// /// # Panics /// @@ -451,19 +459,24 @@ impl<T> Vec<T> { /// /// // The vector contains no items, even though it has capacity for more /// assert_eq!(vec.len(), 0); - /// assert_eq!(vec.capacity(), 10); + /// assert!(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); + /// assert!(vec.capacity() >= 10); /// /// // ...but this may make the vector reallocate /// vec.push(11); /// assert_eq!(vec.len(), 11); /// assert!(vec.capacity() >= 11); + /// + /// // A vector of a zero-sized type will always over-allocate, since no + /// // allocation is necessary + /// let vec_units = Vec::<()>::with_capacity(10); + /// assert_eq!(vec_units.capacity(), usize::MAX); /// ``` #[cfg(not(no_global_oom_handling))] #[inline] @@ -473,17 +486,25 @@ impl<T> Vec<T> { Self::with_capacity_in(capacity, Global) } - /// Tries to construct a new, empty `Vec<T>` with the specified capacity. + /// Tries to construct a new, empty `Vec<T>` with at least the specified capacity. /// - /// The vector will be able to hold exactly `capacity` elements without - /// reallocating. If `capacity` is 0, the vector will not allocate. + /// The vector will be able to hold at least `capacity` elements without + /// reallocating. This method is allowed to allocate for more elements than + /// `capacity`. 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 + /// minimum *capacity* specified, the vector will have a zero *length*. For + /// an explanation of the difference between length and capacity, see /// *[Capacity and reallocation]*. /// + /// If it is important to know the exact allocated capacity of a `Vec`, + /// always use the [`capacity`] method after construction. + /// + /// For `Vec<T>` where `T` is a zero-sized type, there will be no allocation + /// and the capacity will always be `usize::MAX`. + /// /// [Capacity and reallocation]: #capacity-and-reallocation + /// [`capacity`]: Vec::capacity /// /// # Examples /// @@ -492,14 +513,14 @@ impl<T> Vec<T> { /// /// // The vector contains no items, even though it has capacity for more /// assert_eq!(vec.len(), 0); - /// assert_eq!(vec.capacity(), 10); + /// assert!(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); + /// assert!(vec.capacity() >= 10); /// /// // ...but this may make the vector reallocate /// vec.push(11); @@ -508,6 +529,11 @@ impl<T> Vec<T> { /// /// let mut result = Vec::try_with_capacity(usize::MAX); /// assert!(result.is_err()); + /// + /// // A vector of a zero-sized type will always over-allocate, since no + /// // allocation is necessary + /// let vec_units = Vec::<()>::try_with_capacity(10).unwrap(); + /// assert_eq!(vec_units.capacity(), usize::MAX); /// ``` #[inline] #[stable(feature = "kernel", since = "1.0.0")] @@ -515,15 +541,15 @@ impl<T> Vec<T> { Self::try_with_capacity_in(capacity, Global) } - /// Creates a `Vec<T>` directly from the raw components of another vector. + /// Creates a `Vec<T>` directly from a pointer, a capacity, and a length. /// /// # 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<T>` - /// (at least, it's highly likely to be incorrect if it wasn't). + /// * `ptr` must have been allocated using the global allocator, such as via + /// the [`alloc::alloc`] function. /// * `T` needs to have the same 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 @@ -532,6 +558,14 @@ impl<T> Vec<T> { /// to be the same size as the pointer was allocated with. (Because similar to /// alignment, [`dealloc`] must be called with the same layout `size`.) /// * `length` needs to be less than or equal to `capacity`. + /// * The first `length` values must be properly initialized values of type `T`. + /// * `capacity` needs to be the capacity that the pointer was allocated with. + /// * The allocated size in bytes must be no larger than `isize::MAX`. + /// See the safety documentation of [`pointer::offset`]. + /// + /// These requirements are always upheld by any `ptr` that has been allocated + /// via `Vec<T>`. Other allocation sources are allowed if the invariants are + /// upheld. /// /// Violating these may cause problems like corrupting the allocator's /// internal data structures. For example it is normally **not** safe @@ -552,6 +586,7 @@ impl<T> Vec<T> { /// function. /// /// [`String`]: crate::string::String + /// [`alloc::alloc`]: crate::alloc::alloc /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc /// /// # Examples @@ -574,8 +609,8 @@ impl<T> Vec<T> { /// /// unsafe { /// // Overwrite memory with 4, 5, 6 - /// for i in 0..len as isize { - /// ptr::write(p.offset(i), 4 + i); + /// for i in 0..len { + /// ptr::write(p.add(i), 4 + i); /// } /// /// // Put everything back together into a Vec @@ -583,6 +618,32 @@ impl<T> Vec<T> { /// assert_eq!(rebuilt, [4, 5, 6]); /// } /// ``` + /// + /// Using memory that was allocated elsewhere: + /// + /// ```rust + /// #![feature(allocator_api)] + /// + /// use std::alloc::{AllocError, Allocator, Global, Layout}; + /// + /// fn main() { + /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen"); + /// + /// let vec = unsafe { + /// let mem = match Global.allocate(layout) { + /// Ok(mem) => mem.cast::<u32>().as_ptr(), + /// Err(AllocError) => return, + /// }; + /// + /// mem.write(1_000_000); + /// + /// Vec::from_raw_parts_in(mem, 1, 16, Global) + /// }; + /// + /// assert_eq!(vec, &[1_000_000]); + /// assert_eq!(vec.capacity(), 16); + /// } + /// ``` #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self { @@ -611,18 +672,26 @@ impl<T, A: Allocator> Vec<T, A> { Vec { buf: RawVec::new_in(alloc), len: 0 } } - /// Constructs a new, empty `Vec<T, A>` with the specified capacity with the provided - /// allocator. + /// Constructs a new, empty `Vec<T, A>` with at least 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. + /// The vector will be able to hold at least `capacity` elements without + /// reallocating. This method is allowed to allocate for more elements than + /// `capacity`. 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 + /// minimum *capacity* specified, the vector will have a zero *length*. For + /// an explanation of the difference between length and capacity, see /// *[Capacity and reallocation]*. /// + /// If it is important to know the exact allocated capacity of a `Vec`, + /// always use the [`capacity`] method after construction. + /// + /// For `Vec<T, A>` where `T` is a zero-sized type, there will be no allocation + /// and the capacity will always be `usize::MAX`. + /// /// [Capacity and reallocation]: #capacity-and-reallocation + /// [`capacity`]: Vec::capacity /// /// # Panics /// @@ -652,6 +721,11 @@ impl<T, A: Allocator> Vec<T, A> { /// vec.push(11); /// assert_eq!(vec.len(), 11); /// assert!(vec.capacity() >= 11); + /// + /// // A vector of a zero-sized type will always over-allocate, since no + /// // allocation is necessary + /// let vec_units = Vec::<(), System>::with_capacity_in(10, System); + /// assert_eq!(vec_units.capacity(), usize::MAX); /// ``` #[cfg(not(no_global_oom_handling))] #[inline] @@ -660,18 +734,26 @@ impl<T, A: Allocator> Vec<T, A> { Vec { buf: RawVec::with_capacity_in(capacity, alloc), len: 0 } } - /// Tries to construct a new, empty `Vec<T, A>` with the specified capacity + /// Tries to construct a new, empty `Vec<T, A>` with at least 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. + /// The vector will be able to hold at least `capacity` elements without + /// reallocating. This method is allowed to allocate for more elements than + /// `capacity`. 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 + /// minimum *capacity* specified, the vector will have a zero *length*. For + /// an explanation of the difference between length and capacity, see /// *[Capacity and reallocation]*. /// + /// If it is important to know the exact allocated capacity of a `Vec`, + /// always use the [`capacity`] method after construction. + /// + /// For `Vec<T, A>` where `T` is a zero-sized type, there will be no allocation + /// and the capacity will always be `usize::MAX`. + /// /// [Capacity and reallocation]: #capacity-and-reallocation + /// [`capacity`]: Vec::capacity /// /// # Examples /// @@ -700,6 +782,11 @@ impl<T, A: Allocator> Vec<T, A> { /// /// let mut result = Vec::try_with_capacity_in(usize::MAX, System); /// assert!(result.is_err()); + /// + /// // A vector of a zero-sized type will always over-allocate, since no + /// // allocation is necessary + /// let vec_units = Vec::<(), System>::try_with_capacity_in(10, System).unwrap(); + /// assert_eq!(vec_units.capacity(), usize::MAX); /// ``` #[inline] #[stable(feature = "kernel", since = "1.0.0")] @@ -707,21 +794,31 @@ impl<T, A: Allocator> Vec<T, A> { Ok(Vec { buf: RawVec::try_with_capacity_in(capacity, alloc)?, len: 0 }) } - /// Creates a `Vec<T, A>` directly from the raw components of another vector. + /// Creates a `Vec<T, A>` directly from a pointer, a capacity, a length, + /// and an allocator. /// /// # 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<T>` - /// (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. + /// * `ptr` must be [*currently allocated*] via the given allocator `alloc`. + /// * `T` needs to have the same 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.) + /// * The size of `T` times the `capacity` (ie. the allocated size in bytes) needs + /// to be the same size as the pointer was allocated with. (Because similar to + /// alignment, [`dealloc`] must be called with the same layout `size`.) /// * `length` needs to be less than or equal to `capacity`. - /// * `capacity` needs to be the capacity that the pointer was allocated with. + /// * The first `length` values must be properly initialized values of type `T`. + /// * `capacity` needs to [*fit*] the layout size that the pointer was allocated with. + /// * The allocated size in bytes must be no larger than `isize::MAX`. + /// See the safety documentation of [`pointer::offset`]. + /// + /// These requirements are always upheld by any `ptr` that has been allocated + /// via `Vec<T, A>`. Other allocation sources are allowed if the invariants are + /// upheld. /// /// Violating these may cause problems like corrupting the allocator's /// internal data structures. For example it is **not** safe @@ -739,6 +836,8 @@ impl<T, A: Allocator> Vec<T, A> { /// /// [`String`]: crate::string::String /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc + /// [*currently allocated*]: crate::alloc::Allocator#currently-allocated-memory + /// [*fit*]: crate::alloc::Allocator#memory-fitting /// /// # Examples /// @@ -768,8 +867,8 @@ impl<T, A: Allocator> Vec<T, A> { /// /// unsafe { /// // Overwrite memory with 4, 5, 6 - /// for i in 0..len as isize { - /// ptr::write(p.offset(i), 4 + i); + /// for i in 0..len { + /// ptr::write(p.add(i), 4 + i); /// } /// /// // Put everything back together into a Vec @@ -777,6 +876,29 @@ impl<T, A: Allocator> Vec<T, A> { /// assert_eq!(rebuilt, [4, 5, 6]); /// } /// ``` + /// + /// Using memory that was allocated elsewhere: + /// + /// ```rust + /// use std::alloc::{alloc, Layout}; + /// + /// fn main() { + /// let layout = Layout::array::<u32>(16).expect("overflow cannot happen"); + /// let vec = unsafe { + /// let mem = alloc(layout).cast::<u32>(); + /// if mem.is_null() { + /// return; + /// } + /// + /// mem.write(1_000_000); + /// + /// Vec::from_raw_parts(mem, 1, 16) + /// }; + /// + /// assert_eq!(vec, &[1_000_000]); + /// assert_eq!(vec.capacity(), 16); + /// } + /// ``` #[inline] #[unstable(feature = "allocator_api", issue = "32838")] pub unsafe fn from_raw_parts_in(ptr: *mut T, length: usize, capacity: usize, alloc: A) -> Self { @@ -869,13 +991,14 @@ impl<T, A: Allocator> Vec<T, A> { (ptr, len, capacity, alloc) } - /// Returns the number of elements the vector can hold without + /// Returns the total number of elements the vector can hold without /// reallocating. /// /// # Examples /// /// ``` - /// let vec: Vec<i32> = Vec::with_capacity(10); + /// let mut vec: Vec<i32> = Vec::with_capacity(10); + /// vec.push(42); /// assert_eq!(vec.capacity(), 10); /// ``` #[inline] @@ -885,10 +1008,10 @@ impl<T, A: Allocator> Vec<T, A> { } /// Reserves capacity for at least `additional` more elements to be inserted - /// in the given `Vec<T>`. 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. + /// in the given `Vec<T>`. The collection may reserve more space to + /// speculatively 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 /// @@ -907,10 +1030,12 @@ impl<T, A: Allocator> Vec<T, A> { self.buf.reserve(self.len, additional); } - /// Reserves the minimum capacity for exactly `additional` more elements to - /// be inserted in the given `Vec<T>`. After calling `reserve_exact`, - /// capacity will be greater than or equal to `self.len() + additional`. - /// Does nothing if the capacity is already sufficient. + /// Reserves the minimum capacity for at least `additional` more elements to + /// be inserted in the given `Vec<T>`. Unlike [`reserve`], this will not + /// deliberately over-allocate to speculatively avoid frequent allocations. + /// 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 @@ -936,10 +1061,11 @@ impl<T, A: Allocator> Vec<T, A> { } /// Tries to reserve capacity for at least `additional` more elements to be inserted - /// in the given `Vec<T>`. The collection may reserve more space to avoid + /// in the given `Vec<T>`. The collection may reserve more space to speculatively 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. + /// greater than or equal to `self.len() + additional` if it returns + /// `Ok(())`. Does nothing if capacity is already sufficient. This method + /// preserves the contents even if an error occurs. /// /// # Errors /// @@ -971,10 +1097,11 @@ impl<T, A: Allocator> Vec<T, A> { self.buf.try_reserve(self.len, additional) } - /// Tries to reserve the minimum capacity for exactly `additional` - /// elements to be inserted in the given `Vec<T>`. After calling - /// `try_reserve_exact`, capacity will be greater than or equal to - /// `self.len() + additional` if it returns `Ok(())`. + /// Tries to reserve the minimum capacity for at least `additional` + /// elements to be inserted in the given `Vec<T>`. Unlike [`try_reserve`], + /// this will not deliberately over-allocate to speculatively avoid frequent + /// allocations. 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 @@ -1066,7 +1193,8 @@ impl<T, A: Allocator> Vec<T, A> { /// Converts the vector into [`Box<[T]>`][owned slice]. /// - /// Note that this will drop any excess capacity. + /// If the vector has excess capacity, its items will be moved into a + /// newly-allocated buffer with exactly the right capacity. /// /// [owned slice]: Box /// @@ -1199,7 +1327,8 @@ impl<T, A: Allocator> Vec<T, A> { self } - /// Returns a raw pointer to the vector's buffer. + /// Returns a raw pointer to the vector's buffer, or a dangling raw pointer + /// valid for zero sized reads if the vector didn't allocate. /// /// The caller must ensure that the vector outlives the pointer this /// function returns, or else it will end up pointing to garbage. @@ -1236,7 +1365,8 @@ impl<T, A: Allocator> Vec<T, A> { ptr } - /// Returns an unsafe mutable pointer to the vector's buffer. + /// Returns an unsafe mutable pointer to the vector's buffer, or a dangling + /// raw pointer valid for zero sized reads if the vector didn't allocate. /// /// The caller must ensure that the vector outlives the pointer this /// function returns, or else it will end up pointing to garbage. @@ -1440,9 +1570,6 @@ impl<T, A: Allocator> Vec<T, A> { } let len = self.len(); - if index > len { - assert_failed(index, len); - } // space for the new element if len == self.buf.capacity() { @@ -1454,9 +1581,15 @@ impl<T, A: Allocator> Vec<T, A> { // 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); + if index < len { + // Shift everything over to make space. (Duplicating the + // `index`th element into two consecutive places.) + ptr::copy(p, p.add(1), len - index); + } else if index == len { + // No elements need shifting. + } else { + assert_failed(index, len); + } // Write it in, overwriting the first copy of the `index`th // element. ptr::write(p, element); @@ -1513,7 +1646,7 @@ impl<T, A: Allocator> Vec<T, A> { ret = ptr::read(ptr); // Shift everything down to fill in that spot. - ptr::copy(ptr.offset(1), ptr, len - index - 1); + ptr::copy(ptr.add(1), ptr, len - index - 1); } self.set_len(len - 1); ret @@ -1562,11 +1695,11 @@ impl<T, A: Allocator> Vec<T, A> { /// /// ``` /// let mut vec = vec![1, 2, 3, 4]; - /// vec.retain_mut(|x| if *x > 3 { - /// false - /// } else { + /// vec.retain_mut(|x| if *x <= 3 { /// *x += 1; /// true + /// } else { + /// false /// }); /// assert_eq!(vec, [2, 3, 4]); /// ``` @@ -1854,6 +1987,51 @@ impl<T, A: Allocator> Vec<T, A> { Ok(()) } + /// Appends an element if there is sufficient spare capacity, otherwise an error is returned + /// with the element. + /// + /// Unlike [`push`] this method will not reallocate when there's insufficient capacity. + /// The caller should use [`reserve`] or [`try_reserve`] to ensure that there is enough capacity. + /// + /// [`push`]: Vec::push + /// [`reserve`]: Vec::reserve + /// [`try_reserve`]: Vec::try_reserve + /// + /// # Examples + /// + /// A manual, panic-free alternative to [`FromIterator`]: + /// + /// ``` + /// #![feature(vec_push_within_capacity)] + /// + /// use std::collections::TryReserveError; + /// fn from_iter_fallible<T>(iter: impl Iterator<Item=T>) -> Result<Vec<T>, TryReserveError> { + /// let mut vec = Vec::new(); + /// for value in iter { + /// if let Err(value) = vec.push_within_capacity(value) { + /// vec.try_reserve(1)?; + /// // this cannot fail, the previous line either returned or added at least 1 free slot + /// let _ = vec.push_within_capacity(value); + /// } + /// } + /// Ok(vec) + /// } + /// assert_eq!(from_iter_fallible(0..100), Ok(Vec::from_iter(0..100))); + /// ``` + #[inline] + #[unstable(feature = "vec_push_within_capacity", issue = "100486")] + pub fn push_within_capacity(&mut self, value: T) -> Result<(), T> { + if self.len == self.buf.capacity() { + return Err(value); + } + unsafe { + let end = self.as_mut_ptr().add(self.len); + ptr::write(end, value); + self.len += 1; + } + Ok(()) + } + /// Removes the last element from a vector and returns it, or [`None`] if it /// is empty. /// @@ -1886,7 +2064,7 @@ impl<T, A: Allocator> Vec<T, A> { /// /// # Panics /// - /// Panics if the number of elements in the vector overflows a `usize`. + /// Panics if the new capacity exceeds `isize::MAX` bytes. /// /// # Examples /// @@ -1980,9 +2158,7 @@ impl<T, A: Allocator> Vec<T, A> { 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); + let range_slice = slice::from_raw_parts(self.as_ptr().add(start), end - start); Drain { tail_start: end, tail_len: len - end, @@ -2145,7 +2321,7 @@ impl<T, A: Allocator> Vec<T, A> { { let len = self.len(); if new_len > len { - self.extend_with(new_len - len, ExtendFunc(f)); + self.extend_trusted(iter::repeat_with(f).take(new_len - len)); } else { self.truncate(new_len); } @@ -2174,7 +2350,6 @@ impl<T, A: Allocator> Vec<T, A> { /// static_ref[0] += 1; /// assert_eq!(static_ref, &[2, 2, 3]); /// ``` - #[cfg(not(no_global_oom_handling))] #[stable(feature = "vec_leak", since = "1.47.0")] #[inline] pub fn leak<'a>(self) -> &'a mut [T] @@ -2469,7 +2644,7 @@ impl<T: Clone, A: Allocator> Vec<T, A> { self.reserve(range.len()); // SAFETY: - // - `slice::range` guarantees that the given range is valid for indexing self + // - `slice::range` guarantees that the given range is valid for indexing self unsafe { self.spec_extend_from_within(range); } @@ -2501,7 +2676,7 @@ impl<T, A: Allocator, const N: usize> Vec<[T; N], A> { #[unstable(feature = "slice_flatten", issue = "95629")] pub fn into_flattened(self) -> Vec<T, A> { let (ptr, len, cap, alloc) = self.into_raw_parts_with_alloc(); - let (new_len, new_cap) = if mem::size_of::<T>() == 0 { + let (new_len, new_cap) = if T::IS_ZST { (len.checked_mul(N).expect("vec len overflow"), usize::MAX) } else { // SAFETY: @@ -2537,16 +2712,6 @@ impl<T: Clone> ExtendWith<T> for ExtendElement<T> { } } -struct ExtendFunc<F>(F); -impl<T, F: FnMut() -> T> ExtendWith<T> for ExtendFunc<F> { - fn next(&mut self) -> T { - (self.0)() - } - fn last(mut self) -> T { - (self.0)() - } -} - impl<T, A: Allocator> Vec<T, A> { #[cfg(not(no_global_oom_handling))] /// Extend the vector by `n` values, using the given generator. @@ -2563,7 +2728,7 @@ impl<T, A: Allocator> Vec<T, A> { // Write all elements except the last one for _ in 1..n { ptr::write(ptr, value.next()); - ptr = ptr.offset(1); + ptr = ptr.add(1); // Increment the length in every step in case next() panics local_len.increment_len(1); } @@ -2592,7 +2757,7 @@ impl<T, A: Allocator> Vec<T, A> { // Write all elements except the last one for _ in 1..n { ptr::write(ptr, value.next()); - ptr = ptr.offset(1); + ptr = ptr.add(1); // Increment the length in every step in case next() panics local_len.increment_len(1); } @@ -2664,7 +2829,7 @@ impl<T: Clone, A: Allocator> ExtendFromWithinSpec for Vec<T, A> { let (this, spare, len) = unsafe { self.split_at_spare_mut_with_len() }; // SAFETY: - // - caller guaratees that src is a valid index + // - caller guarantees that src is a valid index let to_clone = unsafe { this.get_unchecked(src) }; iter::zip(to_clone, spare) @@ -2683,13 +2848,13 @@ impl<T: Copy, A: Allocator> ExtendFromWithinSpec for Vec<T, A> { let (init, spare) = self.split_at_spare_mut(); // SAFETY: - // - caller guaratees that `src` is a valid index + // - caller guarantees that `src` is a valid index let source = unsafe { init.get_unchecked(src) }; // SAFETY: // - Both pointers are created from unique slice references (`&mut [_]`) // so they are valid and do not overlap. - // - Elements are :Copy so it's OK to to copy them, without doing + // - Elements are :Copy so it's OK to copy them, without doing // anything with the original values // - `count` is equal to the len of `source`, so source is valid for // `count` reads @@ -2712,6 +2877,7 @@ impl<T: Copy, A: Allocator> ExtendFromWithinSpec for Vec<T, A> { impl<T, A: Allocator> ops::Deref for Vec<T, A> { type Target = [T]; + #[inline] fn deref(&self) -> &[T] { unsafe { slice::from_raw_parts(self.as_ptr(), self.len) } } @@ -2719,6 +2885,7 @@ impl<T, A: Allocator> ops::Deref for Vec<T, A> { #[stable(feature = "rust1", since = "1.0.0")] impl<T, A: Allocator> ops::DerefMut for Vec<T, A> { + #[inline] fn deref_mut(&mut self) -> &mut [T] { unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) } } @@ -2764,7 +2931,7 @@ impl<T: Clone, A: Allocator + Clone> Clone for Vec<T, A> { // 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) + // `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 { @@ -2845,19 +3012,22 @@ impl<T, A: Allocator> IntoIterator for Vec<T, A> { /// /// ``` /// let v = vec!["a".to_string(), "b".to_string()]; - /// for s in v.into_iter() { - /// // s has type String, not &String - /// println!("{s}"); - /// } + /// let mut v_iter = v.into_iter(); + /// + /// let first_element: Option<String> = v_iter.next(); + /// + /// assert_eq!(first_element, Some("a".to_string())); + /// assert_eq!(v_iter.next(), Some("b".to_string())); + /// assert_eq!(v_iter.next(), None); /// ``` #[inline] - fn into_iter(self) -> IntoIter<T, A> { + fn into_iter(self) -> Self::IntoIter { unsafe { let mut me = ManuallyDrop::new(self); let alloc = ManuallyDrop::new(ptr::read(me.allocator())); let begin = me.as_mut_ptr(); - let end = if mem::size_of::<T>() == 0 { - arith_offset(begin as *const i8, me.len() as isize) as *const T + let end = if T::IS_ZST { + begin.wrapping_byte_add(me.len()) } else { begin.add(me.len()) as *const T }; @@ -2879,7 +3049,7 @@ impl<'a, T, A: Allocator> IntoIterator for &'a Vec<T, A> { type Item = &'a T; type IntoIter = slice::Iter<'a, T>; - fn into_iter(self) -> slice::Iter<'a, T> { + fn into_iter(self) -> Self::IntoIter { self.iter() } } @@ -2889,7 +3059,7 @@ impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> { type Item = &'a mut T; type IntoIter = slice::IterMut<'a, T>; - fn into_iter(self) -> slice::IterMut<'a, T> { + fn into_iter(self) -> Self::IntoIter { self.iter_mut() } } @@ -2969,6 +3139,69 @@ impl<T, A: Allocator> Vec<T, A> { Ok(()) } + // specific extend for `TrustedLen` iterators, called both by the specializations + // and internal places where resolving specialization makes compilation slower + #[cfg(not(no_global_oom_handling))] + fn extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) { + let (low, high) = iterator.size_hint(); + if let Some(additional) = high { + debug_assert_eq!( + low, + additional, + "TrustedLen iterator's size hint is not exact: {:?}", + (low, high) + ); + self.reserve(additional); + unsafe { + let ptr = self.as_mut_ptr(); + let mut local_len = SetLenOnDrop::new(&mut self.len); + iterator.for_each(move |element| { + ptr::write(ptr.add(local_len.current_len()), element); + // Since the loop executes user code which can panic we have to update + // the length every step to correctly drop what we've written. + // NB can't overflow since we would have had to alloc the address space + local_len.increment_len(1); + }); + } + } else { + // Per TrustedLen contract a `None` upper bound means that the iterator length + // truly exceeds usize::MAX, which would eventually lead to a capacity overflow anyway. + // Since the other branch already panics eagerly (via `reserve()`) we do the same here. + // This avoids additional codegen for a fallback code path which would eventually + // panic anyway. + panic!("capacity overflow"); + } + } + + // specific extend for `TrustedLen` iterators, called both by the specializations + // and internal places where resolving specialization makes compilation slower + fn try_extend_trusted(&mut self, iterator: impl iter::TrustedLen<Item = T>) -> Result<(), TryReserveError> { + let (low, high) = iterator.size_hint(); + if let Some(additional) = high { + debug_assert_eq!( + low, + additional, + "TrustedLen iterator's size hint is not exact: {:?}", + (low, high) + ); + self.try_reserve(additional)?; + unsafe { + let ptr = self.as_mut_ptr(); + let mut local_len = SetLenOnDrop::new(&mut self.len); + iterator.for_each(move |element| { + ptr::write(ptr.add(local_len.current_len()), element); + // Since the loop executes user code which can panic we have to update + // the length every step to correctly drop what we've written. + // NB can't overflow since we would have had to alloc the address space + local_len.increment_len(1); + }); + } + Ok(()) + } else { + Err(TryReserveErrorKind::CapacityOverflow.into()) + } + } + /// 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`. @@ -3135,6 +3368,8 @@ unsafe impl<#[may_dangle] T, A: Allocator> Drop for Vec<T, A> { #[rustc_const_unstable(feature = "const_default_impls", issue = "87864")] impl<T> const Default for Vec<T> { /// Creates an empty `Vec<T>`. + /// + /// The vector will not allocate until elements are pushed onto it. fn default() -> Vec<T> { Vec::new() } @@ -3227,12 +3462,15 @@ impl<T, const N: usize> From<[T; N]> for Vec<T> { /// ``` #[cfg(not(test))] fn from(s: [T; N]) -> Vec<T> { - <[T]>::into_vec(box s) + <[T]>::into_vec( + #[rustc_box] + Box::new(s), + ) } #[cfg(test)] fn from(s: [T; N]) -> Vec<T> { - crate::slice::into_vec(box s) + crate::slice::into_vec(Box::new(s)) } } @@ -3261,7 +3499,7 @@ where } } -// note: test pulls in libstd, which causes errors here +// note: test pulls in std, which causes errors here #[cfg(not(test))] #[stable(feature = "vec_from_box", since = "1.18.0")] impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> { @@ -3279,7 +3517,7 @@ impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> { } } -// note: test pulls in libstd, which causes errors here +// note: test pulls in std, which causes errors here #[cfg(not(no_global_oom_handling))] #[cfg(not(test))] #[stable(feature = "box_from_vec", since = "1.20.0")] @@ -3294,6 +3532,14 @@ impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> { /// ``` /// assert_eq!(Box::from(vec![1, 2, 3]), vec![1, 2, 3].into_boxed_slice()); /// ``` + /// + /// Any excess capacity is removed: + /// ``` + /// let mut vec = Vec::with_capacity(10); + /// vec.extend([1, 2, 3]); + /// + /// assert_eq!(Box::from(vec), vec![1, 2, 3].into_boxed_slice()); + /// ``` fn from(v: Vec<T, A>) -> Self { v.into_boxed_slice() } |