diff options
Diffstat (limited to 'library/alloc/src')
35 files changed, 1059 insertions, 310 deletions
diff --git a/library/alloc/src/alloc.rs b/library/alloc/src/alloc.rs index cc8da7bcc..8187517cc 100644 --- a/library/alloc/src/alloc.rs +++ b/library/alloc/src/alloc.rs @@ -28,16 +28,20 @@ extern "Rust" { // The rustc fork of LLVM 14 and earlier also special-cases these function names to be able to optimize them // like `malloc`, `realloc`, and `free`, respectively. #[rustc_allocator] - #[rustc_allocator_nounwind] + #[cfg_attr(not(bootstrap), rustc_nounwind)] + #[cfg_attr(bootstrap, rustc_allocator_nounwind)] fn __rust_alloc(size: usize, align: usize) -> *mut u8; - #[cfg_attr(not(bootstrap), rustc_deallocator)] - #[rustc_allocator_nounwind] + #[rustc_deallocator] + #[cfg_attr(not(bootstrap), rustc_nounwind)] + #[cfg_attr(bootstrap, rustc_allocator_nounwind)] fn __rust_dealloc(ptr: *mut u8, size: usize, align: usize); - #[cfg_attr(not(bootstrap), rustc_reallocator)] - #[rustc_allocator_nounwind] + #[rustc_reallocator] + #[cfg_attr(not(bootstrap), rustc_nounwind)] + #[cfg_attr(bootstrap, rustc_allocator_nounwind)] fn __rust_realloc(ptr: *mut u8, old_size: usize, align: usize, new_size: usize) -> *mut u8; - #[cfg_attr(not(bootstrap), rustc_allocator_zeroed)] - #[rustc_allocator_nounwind] + #[rustc_allocator_zeroed] + #[cfg_attr(not(bootstrap), rustc_nounwind)] + #[cfg_attr(bootstrap, rustc_allocator_nounwind)] fn __rust_alloc_zeroed(size: usize, align: usize) -> *mut u8; } diff --git a/library/alloc/src/alloc/tests.rs b/library/alloc/src/alloc/tests.rs index 7d560964d..b2f019459 100644 --- a/library/alloc/src/alloc/tests.rs +++ b/library/alloc/src/alloc/tests.rs @@ -15,7 +15,7 @@ fn allocate_zeroed() { let end = i.add(layout.size()); while i < end { assert_eq!(*i, 0); - i = i.offset(1); + i = i.add(1); } Global.deallocate(ptr.as_non_null_ptr(), layout); } diff --git a/library/alloc/src/borrow.rs b/library/alloc/src/borrow.rs index 904a53bb4..83a138559 100644 --- a/library/alloc/src/borrow.rs +++ b/library/alloc/src/borrow.rs @@ -21,7 +21,6 @@ use Cow::*; impl<'a, B: ?Sized> Borrow<B> for Cow<'a, B> where B: ToOwned, - <B as ToOwned>::Owned: 'a, { fn borrow(&self) -> &B { &**self diff --git a/library/alloc/src/boxed.rs b/library/alloc/src/boxed.rs index c1ceeb0de..d6681a317 100644 --- a/library/alloc/src/boxed.rs +++ b/library/alloc/src/boxed.rs @@ -1,4 +1,4 @@ -//! A pointer type for heap allocation. +//! The `Box<T>` type for heap allocation. //! //! [`Box<T>`], casually referred to as a 'box', provides the simplest form of //! heap allocation in Rust. Boxes provide ownership for this allocation, and @@ -151,6 +151,7 @@ use core::async_iter::AsyncIterator; use core::borrow; use core::cmp::Ordering; use core::convert::{From, TryFrom}; +use core::error::Error; use core::fmt; use core::future::Future; use core::hash::{Hash, Hasher}; @@ -175,6 +176,8 @@ use crate::raw_vec::RawVec; #[cfg(not(no_global_oom_handling))] use crate::str::from_boxed_utf8_unchecked; #[cfg(not(no_global_oom_handling))] +use crate::string::String; +#[cfg(not(no_global_oom_handling))] use crate::vec::Vec; #[unstable(feature = "thin_box", issue = "92791")] @@ -1480,7 +1483,7 @@ impl<T: Copy> From<&[T]> for Box<[T]> { /// Converts a `&[T]` into a `Box<[T]>` /// /// This conversion allocates on the heap - /// and performs a copy of `slice`. + /// and performs a copy of `slice` and its contents. /// /// # Examples /// ```rust @@ -1617,6 +1620,22 @@ impl<T, const N: usize> From<[T; N]> for Box<[T]> { } } +/// Casts a boxed slice to a boxed array. +/// +/// # Safety +/// +/// `boxed_slice.len()` must be exactly `N`. +unsafe fn boxed_slice_as_array_unchecked<T, A: Allocator, const N: usize>( + boxed_slice: Box<[T], A>, +) -> Box<[T; N], A> { + debug_assert_eq!(boxed_slice.len(), N); + + let (ptr, alloc) = Box::into_raw_with_allocator(boxed_slice); + // SAFETY: Pointer and allocator came from an existing box, + // and our safety condition requires that the length is exactly `N` + unsafe { Box::from_raw_in(ptr as *mut [T; N], alloc) } +} + #[stable(feature = "boxed_slice_try_from", since = "1.43.0")] impl<T, const N: usize> TryFrom<Box<[T]>> for Box<[T; N]> { type Error = Box<[T]>; @@ -1632,13 +1651,46 @@ impl<T, const N: usize> TryFrom<Box<[T]>> for Box<[T; N]> { /// `boxed_slice.len()` does not equal `N`. fn try_from(boxed_slice: Box<[T]>) -> Result<Self, Self::Error> { if boxed_slice.len() == N { - Ok(unsafe { Box::from_raw(Box::into_raw(boxed_slice) as *mut [T; N]) }) + Ok(unsafe { boxed_slice_as_array_unchecked(boxed_slice) }) } else { Err(boxed_slice) } } } +#[cfg(not(no_global_oom_handling))] +#[stable(feature = "boxed_array_try_from_vec", since = "1.66.0")] +impl<T, const N: usize> TryFrom<Vec<T>> for Box<[T; N]> { + type Error = Vec<T>; + + /// Attempts to convert a `Vec<T>` into a `Box<[T; N]>`. + /// + /// Like [`Vec::into_boxed_slice`], this is in-place if `vec.capacity() == N`, + /// but will require a reallocation otherwise. + /// + /// # Errors + /// + /// Returns the original `Vec<T>` in the `Err` variant if + /// `boxed_slice.len()` does not equal `N`. + /// + /// # Examples + /// + /// This can be used with [`vec!`] to create an array on the heap: + /// + /// ``` + /// let state: Box<[f32; 100]> = vec![1.0; 100].try_into().unwrap(); + /// assert_eq!(state.len(), 100); + /// ``` + fn try_from(vec: Vec<T>) -> Result<Self, Self::Error> { + if vec.len() == N { + let boxed_slice = vec.into_boxed_slice(); + Ok(unsafe { boxed_slice_as_array_unchecked(boxed_slice) }) + } else { + Err(vec) + } + } +} + impl<A: Allocator> Box<dyn Any, A> { /// Attempt to downcast the box to a concrete type. /// @@ -2032,8 +2084,7 @@ impl<T: ?Sized, A: Allocator> AsMut<T> for Box<T, A> { * could have a method to project a Pin<T> from it. */ #[stable(feature = "pin", since = "1.33.0")] -#[rustc_const_unstable(feature = "const_box", issue = "92521")] -impl<T: ?Sized, A: Allocator> const Unpin for Box<T, A> where A: 'static {} +impl<T: ?Sized, A: Allocator> Unpin for Box<T, A> where A: 'static {} #[unstable(feature = "generator_trait", issue = "43122")] impl<G: ?Sized + Generator<R> + Unpin, R, A: Allocator> Generator<R> for Box<G, A> @@ -2085,3 +2136,292 @@ impl<S: ?Sized + AsyncIterator + Unpin> AsyncIterator for Box<S> { (**self).size_hint() } } + +impl dyn Error { + #[inline] + #[stable(feature = "error_downcast", since = "1.3.0")] + #[rustc_allow_incoherent_impl] + /// Attempts to downcast the box to a concrete type. + pub fn downcast<T: Error + 'static>(self: Box<Self>) -> Result<Box<T>, Box<dyn Error>> { + if self.is::<T>() { + unsafe { + let raw: *mut dyn Error = Box::into_raw(self); + Ok(Box::from_raw(raw as *mut T)) + } + } else { + Err(self) + } + } +} + +impl dyn Error + Send { + #[inline] + #[stable(feature = "error_downcast", since = "1.3.0")] + #[rustc_allow_incoherent_impl] + /// Attempts to downcast the box to a concrete type. + pub fn downcast<T: Error + 'static>(self: Box<Self>) -> Result<Box<T>, Box<dyn Error + Send>> { + let err: Box<dyn Error> = self; + <dyn Error>::downcast(err).map_err(|s| unsafe { + // Reapply the `Send` marker. + mem::transmute::<Box<dyn Error>, Box<dyn Error + Send>>(s) + }) + } +} + +impl dyn Error + Send + Sync { + #[inline] + #[stable(feature = "error_downcast", since = "1.3.0")] + #[rustc_allow_incoherent_impl] + /// Attempts to downcast the box to a concrete type. + pub fn downcast<T: Error + 'static>(self: Box<Self>) -> Result<Box<T>, Box<Self>> { + let err: Box<dyn Error> = self; + <dyn Error>::downcast(err).map_err(|s| unsafe { + // Reapply the `Send + Sync` marker. + mem::transmute::<Box<dyn Error>, Box<dyn Error + Send + Sync>>(s) + }) + } +} + +#[cfg(not(no_global_oom_handling))] +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, E: Error + 'a> From<E> for Box<dyn Error + 'a> { + /// Converts a type of [`Error`] into a box of dyn [`Error`]. + /// + /// # Examples + /// + /// ``` + /// use std::error::Error; + /// use std::fmt; + /// use std::mem; + /// + /// #[derive(Debug)] + /// struct AnError; + /// + /// impl fmt::Display for AnError { + /// fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + /// write!(f, "An error") + /// } + /// } + /// + /// impl Error for AnError {} + /// + /// let an_error = AnError; + /// assert!(0 == mem::size_of_val(&an_error)); + /// let a_boxed_error = Box::<dyn Error>::from(an_error); + /// assert!(mem::size_of::<Box<dyn Error>>() == mem::size_of_val(&a_boxed_error)) + /// ``` + fn from(err: E) -> Box<dyn Error + 'a> { + Box::new(err) + } +} + +#[cfg(not(no_global_oom_handling))] +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a, E: Error + Send + Sync + 'a> From<E> for Box<dyn Error + Send + Sync + 'a> { + /// Converts a type of [`Error`] + [`Send`] + [`Sync`] into a box of + /// dyn [`Error`] + [`Send`] + [`Sync`]. + /// + /// # Examples + /// + /// ``` + /// use std::error::Error; + /// use std::fmt; + /// use std::mem; + /// + /// #[derive(Debug)] + /// struct AnError; + /// + /// impl fmt::Display for AnError { + /// fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + /// write!(f, "An error") + /// } + /// } + /// + /// impl Error for AnError {} + /// + /// unsafe impl Send for AnError {} + /// + /// unsafe impl Sync for AnError {} + /// + /// let an_error = AnError; + /// assert!(0 == mem::size_of_val(&an_error)); + /// let a_boxed_error = Box::<dyn Error + Send + Sync>::from(an_error); + /// assert!( + /// mem::size_of::<Box<dyn Error + Send + Sync>>() == mem::size_of_val(&a_boxed_error)) + /// ``` + fn from(err: E) -> Box<dyn Error + Send + Sync + 'a> { + Box::new(err) + } +} + +#[cfg(not(no_global_oom_handling))] +#[stable(feature = "rust1", since = "1.0.0")] +impl From<String> for Box<dyn Error + Send + Sync> { + /// Converts a [`String`] into a box of dyn [`Error`] + [`Send`] + [`Sync`]. + /// + /// # Examples + /// + /// ``` + /// use std::error::Error; + /// use std::mem; + /// + /// let a_string_error = "a string error".to_string(); + /// let a_boxed_error = Box::<dyn Error + Send + Sync>::from(a_string_error); + /// assert!( + /// mem::size_of::<Box<dyn Error + Send + Sync>>() == mem::size_of_val(&a_boxed_error)) + /// ``` + #[inline] + fn from(err: String) -> Box<dyn Error + Send + Sync> { + struct StringError(String); + + impl Error for StringError { + #[allow(deprecated)] + fn description(&self) -> &str { + &self.0 + } + } + + impl fmt::Display for StringError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(&self.0, f) + } + } + + // Purposefully skip printing "StringError(..)" + impl fmt::Debug for StringError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&self.0, f) + } + } + + Box::new(StringError(err)) + } +} + +#[cfg(not(no_global_oom_handling))] +#[stable(feature = "string_box_error", since = "1.6.0")] +impl From<String> for Box<dyn Error> { + /// Converts a [`String`] into a box of dyn [`Error`]. + /// + /// # Examples + /// + /// ``` + /// use std::error::Error; + /// use std::mem; + /// + /// let a_string_error = "a string error".to_string(); + /// let a_boxed_error = Box::<dyn Error>::from(a_string_error); + /// assert!(mem::size_of::<Box<dyn Error>>() == mem::size_of_val(&a_boxed_error)) + /// ``` + fn from(str_err: String) -> Box<dyn Error> { + let err1: Box<dyn Error + Send + Sync> = From::from(str_err); + let err2: Box<dyn Error> = err1; + err2 + } +} + +#[cfg(not(no_global_oom_handling))] +#[stable(feature = "rust1", since = "1.0.0")] +impl<'a> From<&str> for Box<dyn Error + Send + Sync + 'a> { + /// Converts a [`str`] into a box of dyn [`Error`] + [`Send`] + [`Sync`]. + /// + /// [`str`]: prim@str + /// + /// # Examples + /// + /// ``` + /// use std::error::Error; + /// use std::mem; + /// + /// let a_str_error = "a str error"; + /// let a_boxed_error = Box::<dyn Error + Send + Sync>::from(a_str_error); + /// assert!( + /// mem::size_of::<Box<dyn Error + Send + Sync>>() == mem::size_of_val(&a_boxed_error)) + /// ``` + #[inline] + fn from(err: &str) -> Box<dyn Error + Send + Sync + 'a> { + From::from(String::from(err)) + } +} + +#[cfg(not(no_global_oom_handling))] +#[stable(feature = "string_box_error", since = "1.6.0")] +impl From<&str> for Box<dyn Error> { + /// Converts a [`str`] into a box of dyn [`Error`]. + /// + /// [`str`]: prim@str + /// + /// # Examples + /// + /// ``` + /// use std::error::Error; + /// use std::mem; + /// + /// let a_str_error = "a str error"; + /// let a_boxed_error = Box::<dyn Error>::from(a_str_error); + /// assert!(mem::size_of::<Box<dyn Error>>() == mem::size_of_val(&a_boxed_error)) + /// ``` + fn from(err: &str) -> Box<dyn Error> { + From::from(String::from(err)) + } +} + +#[cfg(not(no_global_oom_handling))] +#[stable(feature = "cow_box_error", since = "1.22.0")] +impl<'a, 'b> From<Cow<'b, str>> for Box<dyn Error + Send + Sync + 'a> { + /// Converts a [`Cow`] into a box of dyn [`Error`] + [`Send`] + [`Sync`]. + /// + /// # Examples + /// + /// ``` + /// use std::error::Error; + /// use std::mem; + /// use std::borrow::Cow; + /// + /// let a_cow_str_error = Cow::from("a str error"); + /// let a_boxed_error = Box::<dyn Error + Send + Sync>::from(a_cow_str_error); + /// assert!( + /// mem::size_of::<Box<dyn Error + Send + Sync>>() == mem::size_of_val(&a_boxed_error)) + /// ``` + fn from(err: Cow<'b, str>) -> Box<dyn Error + Send + Sync + 'a> { + From::from(String::from(err)) + } +} + +#[cfg(not(no_global_oom_handling))] +#[stable(feature = "cow_box_error", since = "1.22.0")] +impl<'a> From<Cow<'a, str>> for Box<dyn Error> { + /// Converts a [`Cow`] into a box of dyn [`Error`]. + /// + /// # Examples + /// + /// ``` + /// use std::error::Error; + /// use std::mem; + /// use std::borrow::Cow; + /// + /// let a_cow_str_error = Cow::from("a str error"); + /// let a_boxed_error = Box::<dyn Error>::from(a_cow_str_error); + /// assert!(mem::size_of::<Box<dyn Error>>() == mem::size_of_val(&a_boxed_error)) + /// ``` + fn from(err: Cow<'a, str>) -> Box<dyn Error> { + From::from(String::from(err)) + } +} + +#[stable(feature = "box_error", since = "1.8.0")] +impl<T: core::error::Error> core::error::Error for Box<T> { + #[allow(deprecated, deprecated_in_future)] + fn description(&self) -> &str { + core::error::Error::description(&**self) + } + + #[allow(deprecated)] + fn cause(&self) -> Option<&dyn core::error::Error> { + core::error::Error::cause(&**self) + } + + fn source(&self) -> Option<&(dyn core::error::Error + 'static)> { + core::error::Error::source(&**self) + } +} diff --git a/library/alloc/src/boxed/thin.rs b/library/alloc/src/boxed/thin.rs index 649ccfcaa..c477c4490 100644 --- a/library/alloc/src/boxed/thin.rs +++ b/library/alloc/src/boxed/thin.rs @@ -2,6 +2,7 @@ // https://github.com/matthieu-m/rfc2580/blob/b58d1d3cba0d4b5e859d3617ea2d0943aaa31329/examples/thin.rs // by matthieu-m use crate::alloc::{self, Layout, LayoutError}; +use core::error::Error; use core::fmt::{self, Debug, Display, Formatter}; use core::marker::PhantomData; #[cfg(not(no_global_oom_handling))] @@ -271,3 +272,10 @@ impl<H> WithHeader<H> { Layout::new::<H>().extend(value_layout) } } + +#[unstable(feature = "thin_box", issue = "92791")] +impl<T: ?Sized + Error> Error for ThinBox<T> { + fn source(&self) -> Option<&(dyn Error + 'static)> { + self.deref().source() + } +} diff --git a/library/alloc/src/collections/binary_heap.rs b/library/alloc/src/collections/binary_heap.rs index 197e7aaac..4583bc9a1 100644 --- a/library/alloc/src/collections/binary_heap.rs +++ b/library/alloc/src/collections/binary_heap.rs @@ -1010,7 +1010,8 @@ impl<T> BinaryHeap<T> { /// current length. The allocator may reserve more space to speculatively /// avoid frequent allocations. After calling `try_reserve`, capacity will be /// greater than or equal to `self.len() + additional` if it returns - /// `Ok(())`. Does nothing if capacity is already sufficient. + /// `Ok(())`. Does nothing if capacity is already sufficient. This method + /// preserves the contents even if an error occurs. /// /// # Errors /// diff --git a/library/alloc/src/collections/btree/dedup_sorted_iter.rs b/library/alloc/src/collections/btree/dedup_sorted_iter.rs index 60bf83b83..17ee78045 100644 --- a/library/alloc/src/collections/btree/dedup_sorted_iter.rs +++ b/library/alloc/src/collections/btree/dedup_sorted_iter.rs @@ -3,7 +3,9 @@ use core::iter::Peekable; /// A iterator for deduping the key of a sorted iterator. /// When encountering the duplicated key, only the last key-value pair is yielded. /// -/// Used by [`BTreeMap::bulk_build_from_sorted_iter`]. +/// Used by [`BTreeMap::bulk_build_from_sorted_iter`][1]. +/// +/// [1]: crate::collections::BTreeMap::bulk_build_from_sorted_iter pub struct DedupSortedIter<K, V, I> where I: Iterator<Item = (K, V)>, diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index cacbd54b6..8a7719347 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -580,7 +580,7 @@ impl<K, V> BTreeMap<K, V> { /// map.insert(1, "a"); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")] #[must_use] pub const fn new() -> BTreeMap<K, V> { BTreeMap { root: None, length: 0, alloc: ManuallyDrop::new(Global), _marker: PhantomData } @@ -703,7 +703,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// Basic usage: /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -712,7 +711,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// map.insert(2, "a"); /// assert_eq!(map.first_key_value(), Some((&1, &"b"))); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn first_key_value(&self) -> Option<(&K, &V)> where K: Ord, @@ -727,7 +726,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// # Examples /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -741,7 +739,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// assert_eq!(*map.get(&1).unwrap(), "first"); /// assert_eq!(*map.get(&2).unwrap(), "b"); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>> where K: Ord, @@ -765,7 +763,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// Draining elements in ascending order, while keeping a usable map each iteration. /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -776,7 +773,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// } /// assert!(map.is_empty()); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn pop_first(&mut self) -> Option<(K, V)> where K: Ord, @@ -792,7 +789,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// Basic usage: /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -800,7 +796,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// map.insert(2, "a"); /// assert_eq!(map.last_key_value(), Some((&2, &"a"))); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn last_key_value(&self) -> Option<(&K, &V)> where K: Ord, @@ -815,7 +811,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// # Examples /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -829,7 +824,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// assert_eq!(*map.get(&1).unwrap(), "a"); /// assert_eq!(*map.get(&2).unwrap(), "last"); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>> where K: Ord, @@ -853,7 +848,6 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// Draining elements in descending order, while keeping a usable map each iteration. /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeMap; /// /// let mut map = BTreeMap::new(); @@ -864,7 +858,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// } /// assert!(map.is_empty()); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn pop_last(&mut self) -> Option<(K, V)> where K: Ord, @@ -1099,6 +1093,9 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// Moves all elements from `other` into `self`, leaving `other` empty. /// + /// If a key from `other` is already present in `self`, the respective + /// value from `self` will be overwritten with the respective value from `other`. + /// /// # Examples /// /// ``` @@ -1107,10 +1104,10 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// let mut a = BTreeMap::new(); /// a.insert(1, "a"); /// a.insert(2, "b"); - /// a.insert(3, "c"); + /// a.insert(3, "c"); // Note: Key (3) also present in b. /// /// let mut b = BTreeMap::new(); - /// b.insert(3, "d"); + /// b.insert(3, "d"); // Note: Key (3) also present in a. /// b.insert(4, "e"); /// b.insert(5, "f"); /// @@ -1121,7 +1118,7 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// /// assert_eq!(a[&1], "a"); /// assert_eq!(a[&2], "b"); - /// assert_eq!(a[&3], "d"); + /// assert_eq!(a[&3], "d"); // Note: "c" has been overwritten. /// assert_eq!(a[&4], "e"); /// assert_eq!(a[&5], "f"); /// ``` @@ -2392,7 +2389,11 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// ``` #[must_use] #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_unstable( + feature = "const_btree_len", + issue = "71835", + implied_by = "const_btree_new" + )] pub const fn len(&self) -> usize { self.length } @@ -2413,7 +2414,11 @@ impl<K, V, A: Allocator + Clone> BTreeMap<K, V, A> { /// ``` #[must_use] #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_unstable( + feature = "const_btree_len", + issue = "71835", + implied_by = "const_btree_new" + )] pub const fn is_empty(&self) -> bool { self.len() == 0 } diff --git a/library/alloc/src/collections/btree/map/entry.rs b/library/alloc/src/collections/btree/map/entry.rs index b6eecf9b0..370b58864 100644 --- a/library/alloc/src/collections/btree/map/entry.rs +++ b/library/alloc/src/collections/btree/map/entry.rs @@ -133,6 +133,16 @@ impl<'a, K: Debug + Ord, V: Debug, A: Allocator + Clone> fmt::Display } } +#[unstable(feature = "map_try_insert", issue = "82766")] +impl<'a, K: core::fmt::Debug + Ord, V: core::fmt::Debug> core::error::Error + for crate::collections::btree_map::OccupiedError<'a, K, V> +{ + #[allow(deprecated)] + fn description(&self) -> &str { + "key already exists" + } +} + impl<'a, K: Ord, V, A: Allocator + Clone> Entry<'a, K, V, A> { /// Ensures a value is in the entry by inserting the default if empty, and returns /// a mutable reference to the value in the entry. diff --git a/library/alloc/src/collections/btree/node.rs b/library/alloc/src/collections/btree/node.rs index d831161bc..da766b67a 100644 --- a/library/alloc/src/collections/btree/node.rs +++ b/library/alloc/src/collections/btree/node.rs @@ -206,9 +206,9 @@ impl<'a, K: 'a, V: 'a, Type> Clone for NodeRef<marker::Immut<'a>, K, V, Type> { unsafe impl<BorrowType, K: Sync, V: Sync, Type> Sync for NodeRef<BorrowType, K, V, Type> {} -unsafe impl<'a, K: Sync + 'a, V: Sync + 'a, Type> Send for NodeRef<marker::Immut<'a>, K, V, Type> {} -unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::Mut<'a>, K, V, Type> {} -unsafe impl<'a, K: Send + 'a, V: Send + 'a, Type> Send for NodeRef<marker::ValMut<'a>, K, V, Type> {} +unsafe impl<K: Sync, V: Sync, Type> Send for NodeRef<marker::Immut<'_>, K, V, Type> {} +unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Mut<'_>, K, V, Type> {} +unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::ValMut<'_>, K, V, Type> {} unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Owned, K, V, Type> {} unsafe impl<K: Send, V: Send, Type> Send for NodeRef<marker::Dying, K, V, Type> {} @@ -318,7 +318,7 @@ impl<BorrowType: marker::BorrowType, K, V, Type> NodeRef<BorrowType, K, V, Type> pub fn ascend( self, ) -> Result<Handle<NodeRef<BorrowType, K, V, marker::Internal>, marker::Edge>, Self> { - assert!(BorrowType::PERMITS_TRAVERSAL); + let _ = BorrowType::TRAVERSAL_PERMIT; // We need to use raw pointers to nodes because, if BorrowType is marker::ValMut, // there might be outstanding mutable references to values that we must not invalidate. let leaf_ptr: *const _ = Self::as_leaf_ptr(&self); @@ -1003,7 +1003,7 @@ impl<BorrowType: marker::BorrowType, K, V> /// `edge.descend().ascend().unwrap()` and `node.ascend().unwrap().descend()` should /// both, upon success, do nothing. pub fn descend(self) -> NodeRef<BorrowType, K, V, marker::LeafOrInternal> { - assert!(BorrowType::PERMITS_TRAVERSAL); + let _ = BorrowType::TRAVERSAL_PERMIT; // We need to use raw pointers to nodes because, if BorrowType is // marker::ValMut, there might be outstanding mutable references to // values that we must not invalidate. There's no worry accessing the @@ -1666,15 +1666,17 @@ pub mod marker { pub struct ValMut<'a>(PhantomData<&'a mut ()>); pub trait BorrowType { - // Whether node references of this borrow type allow traversing - // to other nodes in the tree. - const PERMITS_TRAVERSAL: bool = true; + // If node references of this borrow type allow traversing to other + // nodes in the tree, this constant can be evaluated. Thus reading it + // serves as a compile-time assertion. + const TRAVERSAL_PERMIT: () = (); } impl BorrowType for Owned { - // Traversal isn't needed, it happens using the result of `borrow_mut`. + // Reject evaluation, because traversal isn't needed. Instead traversal + // happens using the result of `borrow_mut`. // By disabling traversal, and only creating new references to roots, // we know that every reference of the `Owned` type is to a root node. - const PERMITS_TRAVERSAL: bool = false; + const TRAVERSAL_PERMIT: () = panic!(); } impl BorrowType for Dying {} impl<'a> BorrowType for Immut<'a> {} diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs index 2cfc08074..4ddb21192 100644 --- a/library/alloc/src/collections/btree/set.rs +++ b/library/alloc/src/collections/btree/set.rs @@ -343,7 +343,7 @@ impl<T> BTreeSet<T> { /// let mut set: BTreeSet<i32> = BTreeSet::new(); /// ``` #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_stable(feature = "const_btree_new", since = "1.66.0")] #[must_use] pub const fn new() -> BTreeSet<T> { BTreeSet { map: BTreeMap::new() } @@ -786,7 +786,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// Basic usage: /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeSet; /// /// let mut set = BTreeSet::new(); @@ -797,7 +796,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// assert_eq!(set.first(), Some(&1)); /// ``` #[must_use] - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn first(&self) -> Option<&T> where T: Ord, @@ -813,7 +812,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// Basic usage: /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeSet; /// /// let mut set = BTreeSet::new(); @@ -824,7 +822,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// assert_eq!(set.last(), Some(&2)); /// ``` #[must_use] - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn last(&self) -> Option<&T> where T: Ord, @@ -838,7 +836,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// # Examples /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeSet; /// /// let mut set = BTreeSet::new(); @@ -849,7 +846,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// } /// assert!(set.is_empty()); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn pop_first(&mut self) -> Option<T> where T: Ord, @@ -863,7 +860,6 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// # Examples /// /// ``` - /// #![feature(map_first_last)] /// use std::collections::BTreeSet; /// /// let mut set = BTreeSet::new(); @@ -874,7 +870,7 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// } /// assert!(set.is_empty()); /// ``` - #[unstable(feature = "map_first_last", issue = "62924")] + #[stable(feature = "map_first_last", since = "1.66.0")] pub fn pop_last(&mut self) -> Option<T> where T: Ord, @@ -1174,7 +1170,11 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// ``` #[must_use] #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_unstable( + feature = "const_btree_len", + issue = "71835", + implied_by = "const_btree_new" + )] pub const fn len(&self) -> usize { self.map.len() } @@ -1193,7 +1193,11 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { /// ``` #[must_use] #[stable(feature = "rust1", since = "1.0.0")] - #[rustc_const_unstable(feature = "const_btree_new", issue = "71835")] + #[rustc_const_unstable( + feature = "const_btree_len", + issue = "71835", + implied_by = "const_btree_new" + )] pub const fn is_empty(&self) -> bool { self.len() == 0 } diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs index e21c8aa3b..f2f5dffc2 100644 --- a/library/alloc/src/collections/linked_list.rs +++ b/library/alloc/src/collections/linked_list.rs @@ -1570,7 +1570,7 @@ impl<'a, T> CursorMut<'a, T> { /// that the cursor points to is unchanged, even if it is the "ghost" node. /// /// This operation should compute in *O*(1) time. - // `push_front` continues to point to "ghost" when it addes a node to mimic + // `push_front` continues to point to "ghost" when it adds a node to mimic // the behavior of `insert_before` on an empty list. #[unstable(feature = "linked_list_cursors", issue = "58533")] pub fn push_front(&mut self, elt: T) { @@ -1613,7 +1613,7 @@ impl<'a, T> CursorMut<'a, T> { None } else { // We can't point to the node that we pop. Copying the behavior of - // `remove_current`, we move on the the next node in the sequence. + // `remove_current`, we move on to the next node in the sequence. // If the list is of length 1 then we end pointing to the "ghost" // node at index 0, which is expected. if self.list.head == self.current { diff --git a/library/alloc/src/collections/mod.rs b/library/alloc/src/collections/mod.rs index 628a5b155..161a37573 100644 --- a/library/alloc/src/collections/mod.rs +++ b/library/alloc/src/collections/mod.rs @@ -152,3 +152,6 @@ trait SpecExtend<I: IntoIterator> { /// Extends `self` with the contents of the given iterator. fn spec_extend(&mut self, iter: I); } + +#[stable(feature = "try_reserve", since = "1.57.0")] +impl core::error::Error for TryReserveError {} diff --git a/library/alloc/src/collections/vec_deque/drain.rs b/library/alloc/src/collections/vec_deque/drain.rs index 05f94da6d..41baa7102 100644 --- a/library/alloc/src/collections/vec_deque/drain.rs +++ b/library/alloc/src/collections/vec_deque/drain.rs @@ -1,10 +1,12 @@ +use core::fmt; use core::iter::FusedIterator; +use core::marker::PhantomData; +use core::mem::{self, MaybeUninit}; use core::ptr::{self, NonNull}; -use core::{fmt, mem}; use crate::alloc::{Allocator, Global}; -use super::{count, Iter, VecDeque}; +use super::{count, wrap_index, VecDeque}; /// A draining iterator over the elements of a `VecDeque`. /// @@ -20,18 +22,24 @@ pub struct Drain< > { after_tail: usize, after_head: usize, - iter: Iter<'a, T>, + ring: NonNull<[T]>, + tail: usize, + head: usize, deque: NonNull<VecDeque<T, A>>, + _phantom: PhantomData<&'a T>, } impl<'a, T, A: Allocator> Drain<'a, T, A> { pub(super) unsafe fn new( after_tail: usize, after_head: usize, - iter: Iter<'a, T>, + ring: &'a [MaybeUninit<T>], + tail: usize, + head: usize, deque: NonNull<VecDeque<T, A>>, ) -> Self { - Drain { after_tail, after_head, iter, deque } + let ring = unsafe { NonNull::new_unchecked(ring as *const [MaybeUninit<T>] as *mut _) }; + Drain { after_tail, after_head, ring, tail, head, deque, _phantom: PhantomData } } } @@ -41,7 +49,9 @@ impl<T: fmt::Debug, A: Allocator> fmt::Debug for Drain<'_, T, A> { f.debug_tuple("Drain") .field(&self.after_tail) .field(&self.after_head) - .field(&self.iter) + .field(&self.ring) + .field(&self.tail) + .field(&self.head) .finish() } } @@ -118,12 +128,21 @@ impl<T, A: Allocator> Iterator for Drain<'_, T, A> { #[inline] fn next(&mut self) -> Option<T> { - self.iter.next().map(|elt| unsafe { ptr::read(elt) }) + if self.tail == self.head { + return None; + } + let tail = self.tail; + self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len()); + // Safety: + // - `self.tail` in a ring buffer is always a valid index. + // - `self.head` and `self.tail` equality is checked above. + unsafe { Some(ptr::read(self.ring.as_ptr().get_unchecked_mut(tail))) } } #[inline] fn size_hint(&self) -> (usize, Option<usize>) { - self.iter.size_hint() + let len = count(self.tail, self.head, self.ring.len()); + (len, Some(len)) } } @@ -131,7 +150,14 @@ impl<T, A: Allocator> Iterator for Drain<'_, T, A> { impl<T, A: Allocator> DoubleEndedIterator for Drain<'_, T, A> { #[inline] fn next_back(&mut self) -> Option<T> { - self.iter.next_back().map(|elt| unsafe { ptr::read(elt) }) + if self.tail == self.head { + return None; + } + self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len()); + // Safety: + // - `self.head` in a ring buffer is always a valid index. + // - `self.head` and `self.tail` equality is checked above. + unsafe { Some(ptr::read(self.ring.as_ptr().get_unchecked_mut(self.head))) } } } diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs index 4d895d837..2a57dad89 100644 --- a/library/alloc/src/collections/vec_deque/mod.rs +++ b/library/alloc/src/collections/vec_deque/mod.rs @@ -12,11 +12,17 @@ use core::fmt; use core::hash::{Hash, Hasher}; use core::iter::{repeat_with, FromIterator}; use core::marker::PhantomData; -use core::mem::{self, ManuallyDrop, MaybeUninit}; +use core::mem::{ManuallyDrop, MaybeUninit, SizedTypeProperties}; use core::ops::{Index, IndexMut, Range, RangeBounds}; use core::ptr::{self, NonNull}; use core::slice; +// This is used in a bunch of intra-doc links. +// FIXME: For some reason, `#[cfg(doc)]` wasn't sufficient, resulting in +// failures in linkchecker even though rustdoc built the docs just fine. +#[allow(unused_imports)] +use core::mem; + use crate::alloc::{Allocator, Global}; use crate::collections::TryReserveError; use crate::collections::TryReserveErrorKind; @@ -177,7 +183,7 @@ impl<T, A: Allocator> VecDeque<T, A> { /// Marginally more convenient #[inline] fn cap(&self) -> usize { - if mem::size_of::<T>() == 0 { + if T::IS_ZST { // For zero sized types, we are always at maximum capacity MAXIMUM_ZST_CAPACITY } else { @@ -794,7 +800,8 @@ impl<T, A: Allocator> VecDeque<T, A> { /// in the given deque. 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` if it returns - /// `Ok(())`. Does nothing if capacity is already sufficient. + /// `Ok(())`. Does nothing if capacity is already sufficient. This method + /// preserves the contents even if an error occurs. /// /// # Errors /// @@ -1333,9 +1340,8 @@ impl<T, A: Allocator> VecDeque<T, A> { // it. We do not write to `self` nor reborrow to a mutable reference. // Hence the raw pointer we created above, for `deque`, remains valid. let ring = self.buffer_as_slice(); - let iter = Iter::new(ring, drain_tail, drain_head); - Drain::new(drain_head, head, iter, deque) + Drain::new(drain_head, head, ring, drain_tail, drain_head, deque) } } @@ -2447,8 +2453,8 @@ impl<T, A: Allocator> VecDeque<T, A> { let mut right_offset = 0; for i in left_edge..right_edge { right_offset = (i - left_edge) % (cap - right_edge); - let src: isize = (right_edge + right_offset) as isize; - ptr::swap(buf.add(i), buf.offset(src)); + let src = right_edge + right_offset; + ptr::swap(buf.add(i), buf.add(src)); } let n_ops = right_edge - left_edge; left_edge += n_ops; @@ -3038,7 +3044,7 @@ impl<T, A: Allocator> From<Vec<T, A>> for VecDeque<T, A> { /// `Vec<T>` came from `From<VecDeque<T>>` and hasn't been reallocated. fn from(mut other: Vec<T, A>) -> Self { let len = other.len(); - if mem::size_of::<T>() == 0 { + if T::IS_ZST { // There's no actual allocation for ZSTs to worry about capacity, // but `VecDeque` can't handle as much length as `Vec`. assert!(len < MAXIMUM_ZST_CAPACITY, "capacity overflow"); @@ -3124,7 +3130,7 @@ impl<T, const N: usize> From<[T; N]> for VecDeque<T> { fn from(arr: [T; N]) -> Self { let mut deq = VecDeque::with_capacity(N); let arr = ManuallyDrop::new(arr); - if mem::size_of::<T>() != 0 { + if !<T>::IS_ZST { // SAFETY: VecDeque::with_capacity ensures that there is enough capacity. unsafe { ptr::copy_nonoverlapping(arr.as_ptr(), deq.ptr(), N); diff --git a/library/alloc/src/ffi/c_str.rs b/library/alloc/src/ffi/c_str.rs index ae61b1f1e..11bd4c4dc 100644 --- a/library/alloc/src/ffi/c_str.rs +++ b/library/alloc/src/ffi/c_str.rs @@ -436,9 +436,9 @@ impl CString { /// /// unsafe { /// assert_eq!(b'f', *ptr as u8); - /// assert_eq!(b'o', *ptr.offset(1) as u8); - /// assert_eq!(b'o', *ptr.offset(2) as u8); - /// assert_eq!(b'\0', *ptr.offset(3) as u8); + /// assert_eq!(b'o', *ptr.add(1) as u8); + /// assert_eq!(b'o', *ptr.add(2) as u8); + /// assert_eq!(b'\0', *ptr.add(3) as u8); /// /// // retake pointer to free memory /// let _ = CString::from_raw(ptr); @@ -1121,3 +1121,26 @@ impl CStr { CString::from(self) } } + +#[stable(feature = "rust1", since = "1.0.0")] +impl core::error::Error for NulError { + #[allow(deprecated)] + fn description(&self) -> &str { + "nul byte found in data" + } +} + +#[stable(feature = "cstring_from_vec_with_nul", since = "1.58.0")] +impl core::error::Error for FromVecWithNulError {} + +#[stable(feature = "cstring_into", since = "1.7.0")] +impl core::error::Error for IntoStringError { + #[allow(deprecated)] + fn description(&self) -> &str { + "C string contained non-utf8 bytes" + } + + fn source(&self) -> Option<&(dyn core::error::Error + 'static)> { + Some(self.__source()) + } +} diff --git a/library/alloc/src/fmt.rs b/library/alloc/src/fmt.rs index ed398b566..799ce9d5d 100644 --- a/library/alloc/src/fmt.rs +++ b/library/alloc/src/fmt.rs @@ -327,7 +327,7 @@ //! - `text` must not contain any `'{'` or `'}'` characters, //! - `ws` is any character for which [`char::is_whitespace`] returns `true`, has no semantic //! meaning and is completely optional, -//! - `integer` is a decimal integer that may contain leading zeroes and +//! - `integer` is a decimal integer that may contain leading zeroes and must fit into an `usize` and //! - `identifier` is an `IDENTIFIER_OR_KEYWORD` (not an `IDENTIFIER`) as defined by the [Rust language reference](https://doc.rust-lang.org/reference/identifiers.html). //! //! # Formatting traits diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs index 8b6f40548..ce36b116f 100644 --- a/library/alloc/src/lib.rs +++ b/library/alloc/src/lib.rs @@ -56,10 +56,6 @@ //! [`Rc`]: rc //! [`RefCell`]: core::cell -// To run liballoc tests without x.py without ending up with two copies of liballoc, Miri needs to be -// able to "empty" this crate. See <https://github.com/rust-lang/miri-test-libstd/issues/4>. -// rustc itself never sets the feature, so this line has no affect there. -#![cfg(any(not(feature = "miri-test-libstd"), test, doctest))] #![allow(unused_attributes)] #![stable(feature = "alloc", since = "1.36.0")] #![doc( @@ -73,10 +69,16 @@ any(not(feature = "miri-test-libstd"), test, doctest), no_global_oom_handling, not(no_global_oom_handling), + not(no_rc), + not(no_sync), target_has_atomic = "ptr" ))] #![no_std] #![needs_allocator] +// To run liballoc tests without x.py without ending up with two copies of liballoc, Miri needs to be +// able to "empty" this crate. See <https://github.com/rust-lang/miri-test-libstd/issues/4>. +// rustc itself never sets the feature, so this line has no affect there. +#![cfg(any(not(feature = "miri-test-libstd"), test, doctest))] // // Lints: #![deny(unsafe_op_in_unsafe_fn)] @@ -97,7 +99,7 @@ #![feature(coerce_unsized)] #![cfg_attr(not(no_global_oom_handling), feature(const_alloc_error))] #![feature(const_box)] -#![cfg_attr(not(no_global_oom_handling), feature(const_btree_new))] +#![cfg_attr(not(no_global_oom_handling), feature(const_btree_len))] #![feature(const_cow_is_borrowed)] #![feature(const_convert)] #![feature(const_size_of_val)] @@ -109,8 +111,11 @@ #![feature(core_intrinsics)] #![feature(const_eval_select)] #![feature(const_pin)] +#![feature(const_waker)] #![feature(cstr_from_bytes_until_nul)] #![feature(dispatch_from_dyn)] +#![feature(error_generic_member_access)] +#![feature(error_in_core)] #![feature(exact_size_is_empty)] #![feature(extend_one)] #![feature(fmt_internals)] @@ -120,18 +125,21 @@ #![feature(iter_advance_by)] #![feature(iter_next_chunk)] #![feature(layout_for_ptr)] -#![feature(maybe_uninit_array_assume_init)] #![feature(maybe_uninit_slice)] #![feature(maybe_uninit_uninit_array)] +#![feature(maybe_uninit_uninit_array_transpose)] #![cfg_attr(test, feature(new_uninit))] #![feature(nonnull_slice_from_raw_parts)] #![feature(pattern)] #![feature(pointer_byte_offsets)] +#![feature(provide_any)] #![feature(ptr_internals)] #![feature(ptr_metadata)] #![feature(ptr_sub_ptr)] #![feature(receiver_trait)] +#![feature(saturating_int_impl)] #![feature(set_ptr_value)] +#![feature(sized_type_properties)] #![feature(slice_from_ptr_range)] #![feature(slice_group_by)] #![feature(slice_ptr_get)] @@ -145,6 +153,7 @@ #![feature(unchecked_math)] #![feature(unicode_internals)] #![feature(unsize)] +#![feature(utf8_chunks)] #![feature(std_internals)] // // Language features: @@ -164,7 +173,6 @@ #![cfg_attr(not(test), feature(generator_trait))] #![feature(hashmap_internals)] #![feature(lang_items)] -#![feature(let_else)] #![feature(min_specialization)] #![feature(negative_impls)] #![feature(never_type)] @@ -178,6 +186,7 @@ #![feature(unboxed_closures)] #![feature(unsized_fn_params)] #![feature(c_unwind)] +#![feature(with_negative_coherence)] // // Rustdoc features: #![feature(doc_cfg)] @@ -218,16 +227,17 @@ mod boxed { } pub mod borrow; pub mod collections; -#[cfg(not(no_global_oom_handling))] +#[cfg(all(not(no_rc), not(no_sync), not(no_global_oom_handling)))] pub mod ffi; pub mod fmt; +#[cfg(not(no_rc))] pub mod rc; pub mod slice; pub mod str; pub mod string; -#[cfg(target_has_atomic = "ptr")] +#[cfg(all(not(no_rc), not(no_sync), target_has_atomic = "ptr"))] pub mod sync; -#[cfg(all(not(no_global_oom_handling), target_has_atomic = "ptr"))] +#[cfg(all(not(no_global_oom_handling), not(no_rc), not(no_sync), target_has_atomic = "ptr"))] pub mod task; #[cfg(test)] mod tests; diff --git a/library/alloc/src/macros.rs b/library/alloc/src/macros.rs index 88eb6aa7a..5198bf297 100644 --- a/library/alloc/src/macros.rs +++ b/library/alloc/src/macros.rs @@ -107,6 +107,8 @@ macro_rules! vec { /// format!("test"); /// format!("hello {}", "world!"); /// format!("x = {}, y = {y}", 10, y = 30); +/// let (x, y) = (1, 2); +/// format!("{x} + {y} = 3"); /// ``` #[macro_export] #[stable(feature = "rust1", since = "1.0.0")] diff --git a/library/alloc/src/raw_vec.rs b/library/alloc/src/raw_vec.rs index b0f4529ab..5a10121bb 100644 --- a/library/alloc/src/raw_vec.rs +++ b/library/alloc/src/raw_vec.rs @@ -3,7 +3,7 @@ use core::alloc::LayoutError; use core::cmp; use core::intrinsics; -use core::mem::{self, ManuallyDrop, MaybeUninit}; +use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties}; use core::ops::Drop; use core::ptr::{self, NonNull, Unique}; use core::slice; @@ -168,7 +168,7 @@ impl<T, A: Allocator> RawVec<T, A> { #[cfg(not(no_global_oom_handling))] fn allocate_in(capacity: usize, init: AllocInit, alloc: A) -> Self { // Don't allocate here because `Drop` will not deallocate when `capacity` is 0. - if mem::size_of::<T>() == 0 || capacity == 0 { + if T::IS_ZST || capacity == 0 { Self::new_in(alloc) } else { // We avoid `unwrap_or_else` here because it bloats the amount of @@ -229,7 +229,7 @@ impl<T, A: Allocator> RawVec<T, A> { /// This will always be `usize::MAX` if `T` is zero-sized. #[inline(always)] pub fn capacity(&self) -> usize { - if mem::size_of::<T>() == 0 { usize::MAX } else { self.cap } + if T::IS_ZST { usize::MAX } else { self.cap } } /// Returns a shared reference to the allocator backing this `RawVec`. @@ -238,7 +238,7 @@ impl<T, A: Allocator> RawVec<T, A> { } fn current_memory(&self) -> Option<(NonNull<u8>, Layout)> { - if mem::size_of::<T>() == 0 || self.cap == 0 { + if T::IS_ZST || self.cap == 0 { None } else { // We have an allocated chunk of memory, so we can bypass runtime @@ -380,7 +380,7 @@ impl<T, A: Allocator> RawVec<T, A> { // This is ensured by the calling contexts. debug_assert!(additional > 0); - if mem::size_of::<T>() == 0 { + if T::IS_ZST { // Since we return a capacity of `usize::MAX` when `elem_size` is // 0, getting to here necessarily means the `RawVec` is overfull. return Err(CapacityOverflow.into()); @@ -406,7 +406,7 @@ impl<T, A: Allocator> RawVec<T, A> { // `grow_amortized`, but this method is usually instantiated less often so // it's less critical. fn grow_exact(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> { - if mem::size_of::<T>() == 0 { + if T::IS_ZST { // Since we return a capacity of `usize::MAX` when the type size is // 0, getting to here necessarily means the `RawVec` is overfull. return Err(CapacityOverflow.into()); diff --git a/library/alloc/src/rc.rs b/library/alloc/src/rc.rs index b89b03683..006d813e5 100644 --- a/library/alloc/src/rc.rs +++ b/library/alloc/src/rc.rs @@ -1110,8 +1110,8 @@ impl<T: ?Sized> Rc<T> { #[inline] #[stable(feature = "ptr_eq", since = "1.17.0")] - /// Returns `true` if the two `Rc`s point to the same allocation - /// (in a vein similar to [`ptr::eq`]). + /// Returns `true` if the two `Rc`s point to the same allocation in a vein similar to + /// [`ptr::eq`]. See [that function][`ptr::eq`] for caveats when comparing `dyn Trait` pointers. /// /// # Examples /// @@ -1142,7 +1142,7 @@ impl<T: Clone> Rc<T> { /// be cloned. /// /// See also [`get_mut`], which will fail rather than cloning the inner value - /// or diassociating [`Weak`] pointers. + /// or disassociating [`Weak`] pointers. /// /// [`clone`]: Clone::clone /// [`get_mut`]: Rc::get_mut @@ -1386,7 +1386,7 @@ impl<T: ?Sized> Rc<T> { Self::allocate_for_layout( Layout::for_value(&*ptr), |layout| Global.allocate(layout), - |mem| mem.with_metadata_of(ptr as *mut RcBox<T>), + |mem| mem.with_metadata_of(ptr as *const RcBox<T>), ) } } @@ -2419,9 +2419,9 @@ impl<T: ?Sized> Weak<T> { } } - /// Returns `true` if the two `Weak`s point to the same allocation (similar to - /// [`ptr::eq`]), or if both don't point to any allocation - /// (because they were created with `Weak::new()`). + /// Returns `true` if the two `Weak`s point to the same allocation similar to [`ptr::eq`], or if + /// both don't point to any allocation (because they were created with `Weak::new()`). See [that + /// function][`ptr::eq`] for caveats when comparing `dyn Trait` pointers. /// /// # Notes /// diff --git a/library/alloc/src/slice.rs b/library/alloc/src/slice.rs index 63d4d9452..a5e7bf2a1 100644 --- a/library/alloc/src/slice.rs +++ b/library/alloc/src/slice.rs @@ -1,82 +1,12 @@ -//! A dynamically-sized view into a contiguous sequence, `[T]`. +//! Utilities for the slice primitive type. //! //! *[See also the slice primitive type](slice).* //! -//! Slices are a view into a block of memory represented as a pointer and a -//! length. +//! Most of the structs in this module are iterator types which can only be created +//! using a certain function. For example, `slice.iter()` yields an [`Iter`]. //! -//! ``` -//! // slicing a Vec -//! let vec = vec![1, 2, 3]; -//! let int_slice = &vec[..]; -//! // coercing an array to a slice -//! let str_slice: &[&str] = &["one", "two", "three"]; -//! ``` -//! -//! Slices are either mutable or shared. The shared slice type is `&[T]`, -//! while the mutable slice type is `&mut [T]`, where `T` represents the element -//! type. For example, you can mutate the block of memory that a mutable slice -//! points to: -//! -//! ``` -//! let x = &mut [1, 2, 3]; -//! x[1] = 7; -//! assert_eq!(x, &[1, 7, 3]); -//! ``` -//! -//! Here are some of the things this module contains: -//! -//! ## Structs -//! -//! There are several structs that are useful for slices, such as [`Iter`], which -//! represents iteration over a slice. -//! -//! ## Trait Implementations -//! -//! There are several implementations of common traits for slices. Some examples -//! include: -//! -//! * [`Clone`] -//! * [`Eq`], [`Ord`] - for slices whose element type are [`Eq`] or [`Ord`]. -//! * [`Hash`] - for slices whose element type is [`Hash`]. -//! -//! ## Iteration -//! -//! The slices implement `IntoIterator`. The iterator yields references to the -//! slice elements. -//! -//! ``` -//! let numbers = &[0, 1, 2]; -//! for n in numbers { -//! println!("{n} is a number!"); -//! } -//! ``` -//! -//! The mutable slice yields mutable references to the elements: -//! -//! ``` -//! let mut scores = [7, 8, 9]; -//! for score in &mut scores[..] { -//! *score += 1; -//! } -//! ``` -//! -//! This iterator yields mutable references to the slice's elements, so while -//! the element type of the slice is `i32`, the element type of the iterator is -//! `&mut i32`. -//! -//! * [`.iter`] and [`.iter_mut`] are the explicit methods to return the default -//! iterators. -//! * Further methods that return iterators are [`.split`], [`.splitn`], -//! [`.chunks`], [`.windows`] and more. -//! -//! [`Hash`]: core::hash::Hash -//! [`.iter`]: slice::iter -//! [`.iter_mut`]: slice::iter_mut -//! [`.split`]: slice::split -//! [`.splitn`]: slice::splitn -//! [`.chunks`]: slice::chunks -//! [`.windows`]: slice::windows +//! A few functions are provided to create a slice from a value reference +//! or from a raw pointer. #![stable(feature = "rust1", since = "1.0.0")] // Many of the usings in this module are only used in the test configuration. // It's cleaner to just turn off the unused_imports warning than to fix them. @@ -86,9 +16,7 @@ use core::borrow::{Borrow, BorrowMut}; #[cfg(not(no_global_oom_handling))] use core::cmp::Ordering::{self, Less}; #[cfg(not(no_global_oom_handling))] -use core::mem; -#[cfg(not(no_global_oom_handling))] -use core::mem::size_of; +use core::mem::{self, SizedTypeProperties}; #[cfg(not(no_global_oom_handling))] use core::ptr; @@ -275,7 +203,7 @@ impl<T> [T] { where T: Ord, { - merge_sort(self, |a, b| a.lt(b)); + merge_sort(self, T::lt); } /// Sorts the slice with a comparator function. @@ -1024,7 +952,7 @@ where // Consume the greater side. // If equal, prefer the right run to maintain stability. unsafe { - let to_copy = if is_less(&*right.offset(-1), &*left.offset(-1)) { + let to_copy = if is_less(&*right.sub(1), &*left.sub(1)) { decrement_and_get(left) } else { decrement_and_get(right) @@ -1038,12 +966,12 @@ where unsafe fn get_and_increment<T>(ptr: &mut *mut T) -> *mut T { let old = *ptr; - *ptr = unsafe { ptr.offset(1) }; + *ptr = unsafe { ptr.add(1) }; old } unsafe fn decrement_and_get<T>(ptr: &mut *mut T) -> *mut T { - *ptr = unsafe { ptr.offset(-1) }; + *ptr = unsafe { ptr.sub(1) }; *ptr } @@ -1088,7 +1016,7 @@ where const MIN_RUN: usize = 10; // Sorting has no meaningful behavior on zero-sized types. - if size_of::<T>() == 0 { + if T::IS_ZST { return; } diff --git a/library/alloc/src/str.rs b/library/alloc/src/str.rs index d5ed2c4ad..b28d20cda 100644 --- a/library/alloc/src/str.rs +++ b/library/alloc/src/str.rs @@ -1,26 +1,6 @@ -//! Unicode string slices. +//! Utilities for the `str` primitive type. //! //! *[See also the `str` primitive type](str).* -//! -//! The `&str` type is one of the two main string types, the other being `String`. -//! Unlike its `String` counterpart, its contents are borrowed. -//! -//! # Basic Usage -//! -//! A basic string declaration of `&str` type: -//! -//! ``` -//! let hello_world = "Hello, World!"; -//! ``` -//! -//! Here we have declared a string literal, also known as a string slice. -//! String literals have a static lifetime, which means the string `hello_world` -//! is guaranteed to be valid for the duration of the entire program. -//! We can explicitly specify `hello_world`'s lifetime as well: -//! -//! ``` -//! let hello_world: &'static str = "Hello, world!"; -//! ``` #![stable(feature = "rust1", since = "1.0.0")] // Many of the usings in this module are only used in the test configuration. @@ -71,6 +51,8 @@ pub use core::str::{RSplit, Split}; pub use core::str::{RSplitN, SplitN}; #[stable(feature = "rust1", since = "1.0.0")] pub use core::str::{RSplitTerminator, SplitTerminator}; +#[unstable(feature = "utf8_chunks", issue = "99543")] +pub use core::str::{Utf8Chunk, Utf8Chunks}; /// Note: `str` in `Concat<str>` is not meaningful here. /// This type parameter of the trait only exists to enable another impl. diff --git a/library/alloc/src/string.rs b/library/alloc/src/string.rs index a5118e533..c436adf70 100644 --- a/library/alloc/src/string.rs +++ b/library/alloc/src/string.rs @@ -44,6 +44,7 @@ #[cfg(not(no_global_oom_handling))] use core::char::{decode_utf16, REPLACEMENT_CHARACTER}; +use core::error::Error; use core::fmt; use core::hash; use core::iter::FusedIterator; @@ -58,15 +59,15 @@ use core::ops::Bound::{Excluded, Included, Unbounded}; use core::ops::{self, Index, IndexMut, Range, RangeBounds}; use core::ptr; use core::slice; -#[cfg(not(no_global_oom_handling))] -use core::str::lossy; use core::str::pattern::Pattern; +#[cfg(not(no_global_oom_handling))] +use core::str::Utf8Chunks; #[cfg(not(no_global_oom_handling))] use crate::borrow::{Cow, ToOwned}; use crate::boxed::Box; use crate::collections::TryReserveError; -use crate::str::{self, Chars, Utf8Error}; +use crate::str::{self, from_utf8_unchecked_mut, Chars, Utf8Error}; #[cfg(not(no_global_oom_handling))] use crate::str::{from_boxed_utf8_unchecked, FromStr}; use crate::vec::Vec; @@ -628,11 +629,11 @@ impl String { #[cfg(not(no_global_oom_handling))] #[stable(feature = "rust1", since = "1.0.0")] pub fn from_utf8_lossy(v: &[u8]) -> Cow<'_, str> { - let mut iter = lossy::Utf8Lossy::from_bytes(v).chunks(); + let mut iter = Utf8Chunks::new(v); let first_valid = if let Some(chunk) = iter.next() { - let lossy::Utf8LossyChunk { valid, broken } = chunk; - if broken.is_empty() { + let valid = chunk.valid(); + if chunk.invalid().is_empty() { debug_assert_eq!(valid.len(), v.len()); return Cow::Borrowed(valid); } @@ -647,9 +648,9 @@ impl String { res.push_str(first_valid); res.push_str(REPLACEMENT); - for lossy::Utf8LossyChunk { valid, broken } in iter { - res.push_str(valid); - if !broken.is_empty() { + for chunk in iter { + res.push_str(chunk.valid()); + if !chunk.invalid().is_empty() { res.push_str(REPLACEMENT); } } @@ -1080,7 +1081,8 @@ impl String { /// current length. The allocator may reserve more space to speculatively /// avoid frequent allocations. After calling `try_reserve`, capacity will be /// greater than or equal to `self.len() + additional` if it returns - /// `Ok(())`. Does nothing if capacity is already sufficient. + /// `Ok(())`. Does nothing if capacity is already sufficient. This method + /// preserves the contents even if an error occurs. /// /// # Errors /// @@ -1847,6 +1849,35 @@ impl String { let slice = self.vec.into_boxed_slice(); unsafe { from_boxed_utf8_unchecked(slice) } } + + /// Consumes and leaks the `String`, returning a mutable reference to the contents, + /// `&'static mut str`. + /// + /// This is mainly useful for data that lives for the remainder of + /// the program's life. Dropping the returned reference will cause a memory + /// leak. + /// + /// It does not reallocate or shrink the `String`, + /// so the leaked allocation may include unused capacity that is not part + /// of the returned slice. + /// + /// # Examples + /// + /// Simple usage: + /// + /// ``` + /// #![feature(string_leak)] + /// + /// let x = String::from("bucket"); + /// let static_ref: &'static mut str = x.leak(); + /// assert_eq!(static_ref, "bucket"); + /// ``` + #[unstable(feature = "string_leak", issue = "102929")] + #[inline] + pub fn leak(self) -> &'static mut str { + let slice = self.vec.leak(); + unsafe { from_utf8_unchecked_mut(slice) } + } } impl FromUtf8Error { @@ -1938,6 +1969,22 @@ impl fmt::Display for FromUtf16Error { } } +#[stable(feature = "rust1", since = "1.0.0")] +impl Error for FromUtf8Error { + #[allow(deprecated)] + fn description(&self) -> &str { + "invalid utf-8" + } +} + +#[stable(feature = "rust1", since = "1.0.0")] +impl Error for FromUtf16Error { + #[allow(deprecated)] + fn description(&self) -> &str { + "invalid utf-16" + } +} + #[cfg(not(no_global_oom_handling))] #[stable(feature = "rust1", since = "1.0.0")] impl Clone for String { diff --git a/library/alloc/src/sync.rs b/library/alloc/src/sync.rs index 4c03cc3ed..81cd77074 100644 --- a/library/alloc/src/sync.rs +++ b/library/alloc/src/sync.rs @@ -3,6 +3,10 @@ //! Thread-safe reference-counting pointers. //! //! See the [`Arc<T>`][Arc] documentation for more details. +//! +//! **Note**: This module is only available on platforms that support atomic +//! loads and stores of pointers. This may be detected at compile time using +//! `#[cfg(target_has_atomic = "ptr")]`. use core::any::Any; use core::borrow; @@ -82,6 +86,11 @@ macro_rules! acquire { /// [`Mutex`][mutex], [`RwLock`][rwlock], or one of the [`Atomic`][atomic] /// types. /// +/// **Note**: This type is only available on platforms that support atomic +/// loads and stores of pointers, which includes all platforms that support +/// the `std` crate but not all those which only support [`alloc`](crate). +/// This may be detected at compile time using `#[cfg(target_has_atomic = "ptr")]`. +/// /// ## Thread Safety /// /// Unlike [`Rc<T>`], `Arc<T>` uses atomic operations for its reference @@ -1108,8 +1117,8 @@ impl<T: ?Sized> Arc<T> { drop(Weak { ptr: self.ptr }); } - /// Returns `true` if the two `Arc`s point to the same allocation - /// (in a vein similar to [`ptr::eq`]). + /// Returns `true` if the two `Arc`s point to the same allocation in a vein similar to + /// [`ptr::eq`]. See [that function][`ptr::eq`] for caveats when comparing `dyn Trait` pointers. /// /// # Examples /// @@ -1195,7 +1204,7 @@ impl<T: ?Sized> Arc<T> { Self::allocate_for_layout( Layout::for_value(&*ptr), |layout| Global.allocate(layout), - |mem| mem.with_metadata_of(ptr as *mut ArcInner<T>), + |mem| mem.with_metadata_of(ptr as *const ArcInner<T>), ) } } @@ -1980,33 +1989,26 @@ impl<T: ?Sized> Weak<T> { // We use a CAS loop to increment the strong count instead of a // fetch_add as this function should never take the reference count // from zero to one. - let inner = self.inner()?; - - // Relaxed load because any write of 0 that we can observe - // leaves the field in a permanently zero state (so a - // "stale" read of 0 is fine), and any other value is - // confirmed via the CAS below. - let mut n = inner.strong.load(Relaxed); - - loop { - if n == 0 { - return None; - } - - // See comments in `Arc::clone` for why we do this (for `mem::forget`). - if n > MAX_REFCOUNT { - abort(); - } - + self.inner()? + .strong // Relaxed is fine for the failure case because we don't have any expectations about the new state. // Acquire is necessary for the success case to synchronise with `Arc::new_cyclic`, when the inner // value can be initialized after `Weak` references have already been created. In that case, we // expect to observe the fully initialized value. - match inner.strong.compare_exchange_weak(n, n + 1, Acquire, Relaxed) { - Ok(_) => return Some(unsafe { Arc::from_inner(self.ptr) }), // null checked above - Err(old) => n = old, - } - } + .fetch_update(Acquire, Relaxed, |n| { + // Any write of 0 we can observe leaves the field in permanently zero state. + if n == 0 { + return None; + } + // See comments in `Arc::clone` for why we do this (for `mem::forget`). + if n > MAX_REFCOUNT { + abort(); + } + Some(n + 1) + }) + .ok() + // null checked above + .map(|_| unsafe { Arc::from_inner(self.ptr) }) } /// Gets the number of strong (`Arc`) pointers pointing to this allocation. @@ -2067,9 +2069,9 @@ impl<T: ?Sized> Weak<T> { } } - /// Returns `true` if the two `Weak`s point to the same allocation (similar to - /// [`ptr::eq`]), or if both don't point to any allocation - /// (because they were created with `Weak::new()`). + /// Returns `true` if the two `Weak`s point to the same allocation similar to [`ptr::eq`], or if + /// both don't point to any allocation (because they were created with `Weak::new()`). See [that + /// function][`ptr::eq`] for caveats when comparing `dyn Trait` pointers. /// /// # Notes /// @@ -2763,3 +2765,24 @@ fn data_offset_align(align: usize) -> usize { let layout = Layout::new::<ArcInner<()>>(); layout.size() + layout.padding_needed_for(align) } + +#[stable(feature = "arc_error", since = "1.52.0")] +impl<T: core::error::Error + ?Sized> core::error::Error for Arc<T> { + #[allow(deprecated, deprecated_in_future)] + fn description(&self) -> &str { + core::error::Error::description(&**self) + } + + #[allow(deprecated)] + fn cause(&self) -> Option<&dyn core::error::Error> { + core::error::Error::cause(&**self) + } + + fn source(&self) -> Option<&(dyn core::error::Error + 'static)> { + core::error::Error::source(&**self) + } + + fn provide<'a>(&'a self, req: &mut core::any::Demand<'a>) { + core::error::Error::provide(&**self, req); + } +} diff --git a/library/alloc/src/sync/tests.rs b/library/alloc/src/sync/tests.rs index 202d0e7f0..0fae8953a 100644 --- a/library/alloc/src/sync/tests.rs +++ b/library/alloc/src/sync/tests.rs @@ -618,3 +618,22 @@ fn test_arc_cyclic_two_refs() { assert_eq!(Arc::strong_count(&two_refs), 3); assert_eq!(Arc::weak_count(&two_refs), 2); } + +/// Test for Arc::drop bug (https://github.com/rust-lang/rust/issues/55005) +#[test] +#[cfg(miri)] // relies on Stacked Borrows in Miri +fn arc_drop_dereferenceable_race() { + // The bug seems to take up to 700 iterations to reproduce with most seeds (tested 0-9). + for _ in 0..750 { + let arc_1 = Arc::new(()); + let arc_2 = arc_1.clone(); + let thread = thread::spawn(|| drop(arc_2)); + // Spin a bit; makes the race more likely to appear + let mut i = 0; + while i < 256 { + i += 1; + } + drop(arc_1); + thread.join().unwrap(); + } +} diff --git a/library/alloc/src/task.rs b/library/alloc/src/task.rs index 528ee4ff1..9d8e309a9 100644 --- a/library/alloc/src/task.rs +++ b/library/alloc/src/task.rs @@ -1,5 +1,11 @@ #![stable(feature = "wake_trait", since = "1.51.0")] + //! Types and Traits for working with asynchronous tasks. +//! +//! **Note**: This module is only available on platforms that support atomic +//! loads and stores of pointers. This may be detected at compile time using +//! `#[cfg(target_has_atomic = "ptr")]`. + use core::mem::ManuallyDrop; use core::task::{RawWaker, RawWakerVTable, Waker}; diff --git a/library/alloc/src/vec/drain.rs b/library/alloc/src/vec/drain.rs index 5cdee0bd4..541f99bcf 100644 --- a/library/alloc/src/vec/drain.rs +++ b/library/alloc/src/vec/drain.rs @@ -1,7 +1,7 @@ use crate::alloc::{Allocator, Global}; use core::fmt; use core::iter::{FusedIterator, TrustedLen}; -use core::mem; +use core::mem::{self, ManuallyDrop, SizedTypeProperties}; use core::ptr::{self, NonNull}; use core::slice::{self}; @@ -65,6 +65,77 @@ impl<'a, T, A: Allocator> Drain<'a, T, A> { pub fn allocator(&self) -> &A { unsafe { self.vec.as_ref().allocator() } } + + /// Keep unyielded elements in the source `Vec`. + /// + /// # Examples + /// + /// ``` + /// #![feature(drain_keep_rest)] + /// + /// let mut vec = vec!['a', 'b', 'c']; + /// let mut drain = vec.drain(..); + /// + /// assert_eq!(drain.next().unwrap(), 'a'); + /// + /// // This call keeps 'b' and 'c' in the vec. + /// drain.keep_rest(); + /// + /// // If we wouldn't call `keep_rest()`, + /// // `vec` would be empty. + /// assert_eq!(vec, ['b', 'c']); + /// ``` + #[unstable(feature = "drain_keep_rest", issue = "101122")] + pub fn keep_rest(self) { + // At this moment layout looks like this: + // + // [head] [yielded by next] [unyielded] [yielded by next_back] [tail] + // ^-- start \_________/-- unyielded_len \____/-- self.tail_len + // ^-- unyielded_ptr ^-- tail + // + // Normally `Drop` impl would drop [unyielded] and then move [tail] to the `start`. + // Here we want to + // 1. Move [unyielded] to `start` + // 2. Move [tail] to a new start at `start + len(unyielded)` + // 3. Update length of the original vec to `len(head) + len(unyielded) + len(tail)` + // a. In case of ZST, this is the only thing we want to do + // 4. Do *not* drop self, as everything is put in a consistent state already, there is nothing to do + let mut this = ManuallyDrop::new(self); + + unsafe { + let source_vec = this.vec.as_mut(); + + let start = source_vec.len(); + let tail = this.tail_start; + + let unyielded_len = this.iter.len(); + let unyielded_ptr = this.iter.as_slice().as_ptr(); + + // ZSTs have no identity, so we don't need to move them around. + let needs_move = mem::size_of::<T>() != 0; + + if needs_move { + let start_ptr = source_vec.as_mut_ptr().add(start); + + // memmove back unyielded elements + if unyielded_ptr != start_ptr { + let src = unyielded_ptr; + let dst = start_ptr; + + ptr::copy(src, dst, unyielded_len); + } + + // memmove back untouched tail + if tail != (start + unyielded_len) { + let src = source_vec.as_ptr().add(tail); + let dst = start_ptr.add(unyielded_len); + ptr::copy(src, dst, this.tail_len); + } + } + + source_vec.set_len(start + unyielded_len + this.tail_len); + } + } } #[stable(feature = "vec_drain_as_slice", since = "1.46.0")] @@ -131,7 +202,7 @@ impl<T, A: Allocator> Drop for Drain<'_, T, A> { let mut vec = self.vec; - if mem::size_of::<T>() == 0 { + if T::IS_ZST { // ZSTs have no identity, so we don't need to move them around, we only need to drop the correct amount. // this can be achieved by manipulating the Vec length instead of moving values out from `iter`. unsafe { diff --git a/library/alloc/src/vec/drain_filter.rs b/library/alloc/src/vec/drain_filter.rs index 3c37c92ae..8c03f1692 100644 --- a/library/alloc/src/vec/drain_filter.rs +++ b/library/alloc/src/vec/drain_filter.rs @@ -1,6 +1,7 @@ use crate::alloc::{Allocator, Global}; -use core::ptr::{self}; -use core::slice::{self}; +use core::mem::{self, ManuallyDrop}; +use core::ptr; +use core::slice; use super::Vec; @@ -54,6 +55,61 @@ where pub fn allocator(&self) -> &A { self.vec.allocator() } + + /// Keep unyielded elements in the source `Vec`. + /// + /// # Examples + /// + /// ``` + /// #![feature(drain_filter)] + /// #![feature(drain_keep_rest)] + /// + /// let mut vec = vec!['a', 'b', 'c']; + /// let mut drain = vec.drain_filter(|_| true); + /// + /// assert_eq!(drain.next().unwrap(), 'a'); + /// + /// // This call keeps 'b' and 'c' in the vec. + /// drain.keep_rest(); + /// + /// // If we wouldn't call `keep_rest()`, + /// // `vec` would be empty. + /// assert_eq!(vec, ['b', 'c']); + /// ``` + #[unstable(feature = "drain_keep_rest", issue = "101122")] + pub fn keep_rest(self) { + // At this moment layout looks like this: + // + // _____________________/-- old_len + // / \ + // [kept] [yielded] [tail] + // \_______/ ^-- idx + // \-- del + // + // Normally `Drop` impl would drop [tail] (via .for_each(drop), ie still calling `pred`) + // + // 1. Move [tail] after [kept] + // 2. Update length of the original vec to `old_len - del` + // a. In case of ZST, this is the only thing we want to do + // 3. Do *not* drop self, as everything is put in a consistent state already, there is nothing to do + let mut this = ManuallyDrop::new(self); + + unsafe { + // ZSTs have no identity, so we don't need to move them around. + let needs_move = mem::size_of::<T>() != 0; + + if needs_move && this.idx < this.old_len && this.del > 0 { + let ptr = this.vec.as_mut_ptr(); + let src = ptr.add(this.idx); + let dst = src.sub(this.del); + let tail_len = this.old_len - this.idx; + src.copy_to(dst, tail_len); + } + + let new_len = this.old_len - this.del; + this.vec.set_len(new_len); + } + } } #[unstable(feature = "drain_filter", reason = "recently added", issue = "43244")] diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index 55dcb84ad..87d61deb1 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -55,6 +55,9 @@ //! This is handled by the [`InPlaceDrop`] guard for sink items (`U`) and by //! [`vec::IntoIter::forget_allocation_drop_remaining()`] for remaining source items (`T`). //! +//! If dropping any remaining source item (`T`) panics then [`InPlaceDstBufDrop`] will handle dropping +//! the already collected sink items (`U`) and freeing the allocation. +//! //! [`vec::IntoIter::forget_allocation_drop_remaining()`]: super::IntoIter::forget_allocation_drop_remaining() //! //! # O(1) collect @@ -135,10 +138,10 @@ //! vec.truncate(write_idx); //! ``` use core::iter::{InPlaceIterable, SourceIter, TrustedRandomAccessNoCoerce}; -use core::mem::{self, ManuallyDrop}; +use core::mem::{self, ManuallyDrop, SizedTypeProperties}; use core::ptr::{self}; -use super::{InPlaceDrop, SpecFromIter, SpecFromIterNested, Vec}; +use super::{InPlaceDrop, InPlaceDstBufDrop, 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. @@ -154,7 +157,7 @@ where default fn from_iter(mut iterator: I) -> Self { // See "Layout constraints" section in the module documentation. We rely on const // optimization here since these conditions currently cannot be expressed as trait bounds - if mem::size_of::<T>() == 0 + if T::IS_ZST || mem::size_of::<T>() != mem::size_of::<<<I as SourceIter>::Source as AsVecIntoIter>::Item>() || mem::align_of::<T>() @@ -191,14 +194,17 @@ where ); } - // Drop any remaining values at the tail of the source but prevent drop of the allocation - // itself once IntoIter goes out of scope. - // If the drop panics then we also leak any elements collected into dst_buf. + // The ownership of the allocation and the new `T` values is temporarily moved into `dst_guard`. + // This is safe because `forget_allocation_drop_remaining` immediately forgets the allocation + // before any panic can occur in order to avoid any double free, and then proceeds to drop + // any remaining values at the tail of the source. // // Note: This access to the source wouldn't be allowed by the TrustedRandomIteratorNoCoerce // contract (used by SpecInPlaceCollect below). But see the "O(1) collect" section in the // module documenttation why this is ok anyway. + let dst_guard = InPlaceDstBufDrop { ptr: dst_buf, len, cap }; src.forget_allocation_drop_remaining(); + mem::forget(dst_guard); let vec = unsafe { Vec::from_raw_parts(dst_buf, len, cap) }; @@ -267,7 +273,7 @@ where // one slot in the underlying storage will have been freed up and we can immediately // write back the result. unsafe { - let dst = dst_buf.offset(i as isize); + let dst = dst_buf.add(i); debug_assert!(dst as *const _ <= end, "InPlaceIterable contract violation"); ptr::write(dst, self.__iterator_get_unchecked(i)); // Since this executes user code which can panic we have to bump the pointer diff --git a/library/alloc/src/vec/in_place_drop.rs b/library/alloc/src/vec/in_place_drop.rs index 1b1ef9130..25ca33c6a 100644 --- a/library/alloc/src/vec/in_place_drop.rs +++ b/library/alloc/src/vec/in_place_drop.rs @@ -22,3 +22,18 @@ impl<T> Drop for InPlaceDrop<T> { } } } + +// A helper struct for in-place collection that drops the destination allocation and elements, +// to avoid leaking them if some other destructor panics. +pub(super) struct InPlaceDstBufDrop<T> { + pub(super) ptr: *mut T, + pub(super) len: usize, + pub(super) cap: usize, +} + +impl<T> Drop for InPlaceDstBufDrop<T> { + #[inline] + fn drop(&mut self) { + unsafe { super::Vec::from_raw_parts(self.ptr, self.len, self.cap) }; + } +} diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index 1b483e3fc..02cc7691a 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -4,12 +4,11 @@ use crate::alloc::{Allocator, Global}; use crate::raw_vec::RawVec; use core::array; use core::fmt; -use core::intrinsics::arith_offset; use core::iter::{ FusedIterator, InPlaceIterable, SourceIter, TrustedLen, TrustedRandomAccessNoCoerce, }; use core::marker::PhantomData; -use core::mem::{self, ManuallyDrop, MaybeUninit}; +use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties}; #[cfg(not(no_global_oom_handling))] use core::ops::Deref; use core::ptr::{self, NonNull}; @@ -96,13 +95,16 @@ impl<T, A: Allocator> IntoIter<T, A> { } /// Drops remaining elements and relinquishes the backing allocation. + /// This method guarantees it won't panic before relinquishing + /// the backing allocation. /// /// This is roughly equivalent to the following, but more efficient /// /// ``` /// # let mut into_iter = Vec::<u8>::with_capacity(10).into_iter(); + /// let mut into_iter = std::mem::replace(&mut into_iter, Vec::new().into_iter()); /// (&mut into_iter).for_each(core::mem::drop); - /// unsafe { core::ptr::write(&mut into_iter, Vec::new().into_iter()); } + /// std::mem::forget(into_iter); /// ``` /// /// This method is used by in-place iteration, refer to the vec::in_place_collect @@ -119,6 +121,8 @@ impl<T, A: Allocator> IntoIter<T, A> { self.ptr = self.buf.as_ptr(); self.end = self.buf.as_ptr(); + // Dropping the remaining elements can panic, so this needs to be + // done only after updating the other fields. unsafe { ptr::drop_in_place(remaining); } @@ -148,19 +152,19 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { #[inline] fn next(&mut self) -> Option<T> { - if self.ptr as *const _ == self.end { + if self.ptr == self.end { None - } else if mem::size_of::<T>() == 0 { + } else if T::IS_ZST { // 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 }; + self.ptr = self.ptr.wrapping_byte_add(1); // Make up a value of this ZST. Some(unsafe { mem::zeroed() }) } else { let old = self.ptr; - self.ptr = unsafe { self.ptr.offset(1) }; + self.ptr = unsafe { self.ptr.add(1) }; Some(unsafe { ptr::read(old) }) } @@ -168,7 +172,7 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { #[inline] fn size_hint(&self) -> (usize, Option<usize>) { - let exact = if mem::size_of::<T>() == 0 { + let exact = if T::IS_ZST { self.end.addr().wrapping_sub(self.ptr.addr()) } else { unsafe { self.end.sub_ptr(self.ptr) } @@ -180,11 +184,11 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { fn advance_by(&mut self, n: usize) -> Result<(), usize> { let step_size = self.len().min(n); let to_drop = ptr::slice_from_raw_parts_mut(self.ptr as *mut T, step_size); - if mem::size_of::<T>() == 0 { + if T::IS_ZST { // SAFETY: due to unchecked casts of unsigned amounts to signed offsets the wraparound // effectively results in unsigned pointers representing positions 0..usize::MAX, // which is valid for ZSTs. - self.ptr = unsafe { arith_offset(self.ptr as *const i8, step_size as isize) as *mut T } + self.ptr = self.ptr.wrapping_byte_add(step_size); } else { // SAFETY: the min() above ensures that step_size is in bounds self.ptr = unsafe { self.ptr.add(step_size) }; @@ -210,16 +214,16 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { let len = self.len(); - if mem::size_of::<T>() == 0 { + if T::IS_ZST { if len < N { self.forget_remaining_elements(); // Safety: ZSTs can be conjured ex nihilo, only the amount has to be correct return Err(unsafe { array::IntoIter::new_unchecked(raw_ary, 0..len) }); } - self.ptr = unsafe { arith_offset(self.ptr as *const i8, N as isize) as *mut T }; + self.ptr = self.ptr.wrapping_byte_add(N); // Safety: ditto - return Ok(unsafe { MaybeUninit::array_assume_init(raw_ary) }); + return Ok(unsafe { raw_ary.transpose().assume_init() }); } if len < N { @@ -237,7 +241,7 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { return unsafe { ptr::copy_nonoverlapping(self.ptr, raw_ary.as_mut_ptr() as *mut T, N); self.ptr = self.ptr.add(N); - Ok(MaybeUninit::array_assume_init(raw_ary)) + Ok(raw_ary.transpose().assume_init()) }; } @@ -254,7 +258,7 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { // that `T: Copy` so reading elements from the buffer doesn't invalidate // them for `Drop`. unsafe { - if mem::size_of::<T>() == 0 { mem::zeroed() } else { ptr::read(self.ptr.add(i)) } + if T::IS_ZST { mem::zeroed() } else { ptr::read(self.ptr.add(i)) } } } } @@ -265,14 +269,14 @@ impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> { fn next_back(&mut self) -> Option<T> { if self.end == self.ptr { None - } else if mem::size_of::<T>() == 0 { + } else if T::IS_ZST { // See above for why 'ptr.offset' isn't used - self.end = unsafe { arith_offset(self.end as *const i8, -1) as *mut T }; + self.end = self.end.wrapping_byte_sub(1); // Make up a value of this ZST. Some(unsafe { mem::zeroed() }) } else { - self.end = unsafe { self.end.offset(-1) }; + self.end = unsafe { self.end.sub(1) }; Some(unsafe { ptr::read(self.end) }) } @@ -281,14 +285,12 @@ impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> { #[inline] fn advance_back_by(&mut self, n: usize) -> Result<(), usize> { let step_size = self.len().min(n); - if mem::size_of::<T>() == 0 { + if T::IS_ZST { // SAFETY: same as for advance_by() - self.end = unsafe { - arith_offset(self.end as *const i8, step_size.wrapping_neg() as isize) as *mut T - } + self.end = self.end.wrapping_byte_sub(step_size); } else { // SAFETY: same as for advance_by() - self.end = unsafe { self.end.offset(step_size.wrapping_neg() as isize) }; + self.end = unsafe { self.end.sub(step_size) }; } let to_drop = ptr::slice_from_raw_parts_mut(self.end as *mut T, step_size); // SAFETY: same as for advance_by() diff --git a/library/alloc/src/vec/is_zero.rs b/library/alloc/src/vec/is_zero.rs index 92a32779b..8e652d676 100644 --- a/library/alloc/src/vec/is_zero.rs +++ b/library/alloc/src/vec/is_zero.rs @@ -1,3 +1,5 @@ +use core::num::{Saturating, Wrapping}; + use crate::boxed::Box; #[rustc_specialization_trait] @@ -144,3 +146,39 @@ impl_is_zero_option_of_nonzero!( NonZeroUsize, NonZeroIsize, ); + +unsafe impl<T: IsZero> IsZero for Wrapping<T> { + #[inline] + fn is_zero(&self) -> bool { + self.0.is_zero() + } +} + +unsafe impl<T: IsZero> IsZero for Saturating<T> { + #[inline] + fn is_zero(&self) -> bool { + self.0.is_zero() + } +} + +macro_rules! impl_for_optional_bool { + ($($t:ty,)+) => {$( + unsafe impl IsZero for $t { + #[inline] + fn is_zero(&self) -> bool { + // SAFETY: This is *not* a stable layout guarantee, but + // inside `core` we're allowed to rely on the current rustc + // behaviour that options of bools will be one byte with + // no padding, so long as they're nested less than 254 deep. + let raw: u8 = unsafe { core::mem::transmute(*self) }; + raw == 0 + } + } + )+}; +} +impl_for_optional_bool! { + Option<bool>, + Option<Option<bool>>, + Option<Option<Option<bool>>>, + // Could go further, but not worth the metadata overhead +} diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index fa9f2131c..bbbdc3aa2 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -59,12 +59,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}; @@ -125,7 +125,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; @@ -436,7 +436,7 @@ impl<T> Vec<T> { /// an explanation of the difference between length and capacity, see /// *[Capacity and reallocation]*. /// - /// If it is imporant to know the exact allocated capacity of a `Vec`, + /// 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 @@ -483,15 +483,13 @@ impl<T> Vec<T> { Self::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). /// * `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 @@ -500,6 +498,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 @@ -542,8 +548,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 @@ -551,6 +557,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 { @@ -591,7 +623,7 @@ impl<T, A: Allocator> Vec<T, A> { /// an explanation of the difference between length and capacity, see /// *[Capacity and reallocation]*. /// - /// If it is imporant to know the exact allocated capacity of a `Vec`, + /// 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 @@ -641,21 +673,30 @@ impl<T, A: Allocator> Vec<T, A> { Vec { buf: RawVec::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. + /// * `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 @@ -673,6 +714,7 @@ impl<T, A: Allocator> Vec<T, A> { /// /// [`String`]: crate::string::String /// [`dealloc`]: crate::alloc::GlobalAlloc::dealloc + /// [*fit*]: crate::alloc::Allocator#memory-fitting /// /// # Examples /// @@ -702,8 +744,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 @@ -711,6 +753,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 { @@ -803,13 +868,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] @@ -875,7 +941,8 @@ impl<T, A: Allocator> Vec<T, A> { /// 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` if it returns - /// `Ok(())`. Does nothing if capacity is already sufficient. + /// `Ok(())`. Does nothing if capacity is already sufficient. This method + /// preserves the contents even if an error occurs. /// /// # Errors /// @@ -1393,7 +1460,7 @@ impl<T, A: Allocator> Vec<T, A> { if index < len { // Shift everything over to make space. (Duplicating the // `index`th element into two consecutive places.) - ptr::copy(p, p.offset(1), len - index); + ptr::copy(p, p.add(1), len - index); } else if index == len { // No elements need shifting. } else { @@ -1455,7 +1522,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 @@ -1773,6 +1840,51 @@ impl<T, A: Allocator> Vec<T, A> { } } + /// 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. /// @@ -1888,9 +2000,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, @@ -2082,7 +2192,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] @@ -2346,7 +2455,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: @@ -2408,7 +2517,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); } @@ -2676,8 +2785,8 @@ impl<T, A: Allocator> IntoIterator for Vec<T, A> { 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 }; @@ -2927,6 +3036,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() } diff --git a/library/alloc/src/vec/spec_extend.rs b/library/alloc/src/vec/spec_extend.rs index 506ee0ecf..1ea9c827a 100644 --- a/library/alloc/src/vec/spec_extend.rs +++ b/library/alloc/src/vec/spec_extend.rs @@ -39,7 +39,7 @@ where let mut local_len = SetLenOnDrop::new(&mut self.len); iterator.for_each(move |element| { ptr::write(ptr, element); - ptr = ptr.offset(1); + ptr = ptr.add(1); // Since the loop executes user code which can panic we have to bump the pointer // after each step. // NB can't overflow since we would have had to alloc the address space |