diff options
Diffstat (limited to 'library/alloc/src')
58 files changed, 1356 insertions, 505 deletions
diff --git a/library/alloc/src/alloc.rs b/library/alloc/src/alloc.rs index 1833a7f477f..db2d752cfde 100644 --- a/library/alloc/src/alloc.rs +++ b/library/alloc/src/alloc.rs @@ -2,16 +2,14 @@ #![stable(feature = "alloc_module", since = "1.28.0")] +#[stable(feature = "alloc_module", since = "1.28.0")] +#[doc(inline)] +pub use core::alloc::*; #[cfg(not(test))] use core::hint; - #[cfg(not(test))] use core::ptr::{self, NonNull}; -#[stable(feature = "alloc_module", since = "1.28.0")] -#[doc(inline)] -pub use core::alloc::*; - #[cfg(test)] mod tests; @@ -57,7 +55,7 @@ pub struct Global; #[cfg(test)] pub use std::alloc::Global; -/// Allocate memory with the global allocator. +/// Allocates memory with the global allocator. /// /// This function forwards calls to the [`GlobalAlloc::alloc`] method /// of the allocator registered with the `#[global_allocator]` attribute @@ -101,7 +99,7 @@ pub unsafe fn alloc(layout: Layout) -> *mut u8 { } } -/// Deallocate memory with the global allocator. +/// Deallocates memory with the global allocator. /// /// This function forwards calls to the [`GlobalAlloc::dealloc`] method /// of the allocator registered with the `#[global_allocator]` attribute @@ -119,7 +117,7 @@ pub unsafe fn dealloc(ptr: *mut u8, layout: Layout) { unsafe { __rust_dealloc(ptr, layout.size(), layout.align()) } } -/// Reallocate memory with the global allocator. +/// Reallocates memory with the global allocator. /// /// This function forwards calls to the [`GlobalAlloc::realloc`] method /// of the allocator registered with the `#[global_allocator]` attribute @@ -138,7 +136,7 @@ pub unsafe fn realloc(ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 unsafe { __rust_realloc(ptr, layout.size(), layout.align(), new_size) } } -/// Allocate zero-initialized memory with the global allocator. +/// Allocates zero-initialized memory with the global allocator. /// /// This function forwards calls to the [`GlobalAlloc::alloc_zeroed`] method /// of the allocator registered with the `#[global_allocator]` attribute @@ -345,7 +343,7 @@ extern "Rust" { fn __rust_alloc_error_handler(size: usize, align: usize) -> !; } -/// Signal a memory allocation error. +/// Signals a memory allocation error. /// /// Callers of memory allocation APIs wishing to cease execution /// in response to an allocation error are encouraged to call this function, diff --git a/library/alloc/src/alloc/tests.rs b/library/alloc/src/alloc/tests.rs index 1a5938fd34c..5d6077f057a 100644 --- a/library/alloc/src/alloc/tests.rs +++ b/library/alloc/src/alloc/tests.rs @@ -1,9 +1,10 @@ use super::*; extern crate test; -use crate::boxed::Box; use test::Bencher; +use crate::boxed::Box; + #[test] fn allocate_zeroed() { unsafe { diff --git a/library/alloc/src/borrow.rs b/library/alloc/src/borrow.rs index 42f8a08a9e4..f86face3f90 100644 --- a/library/alloc/src/borrow.rs +++ b/library/alloc/src/borrow.rs @@ -2,21 +2,20 @@ #![stable(feature = "rust1", since = "1.0.0")] +#[stable(feature = "rust1", since = "1.0.0")] +pub use core::borrow::{Borrow, BorrowMut}; use core::cmp::Ordering; use core::hash::{Hash, Hasher}; #[cfg(not(no_global_oom_handling))] use core::ops::{Add, AddAssign}; use core::ops::{Deref, DerefPure}; -#[stable(feature = "rust1", since = "1.0.0")] -pub use core::borrow::{Borrow, BorrowMut}; +use Cow::*; use crate::fmt; #[cfg(not(no_global_oom_handling))] use crate::string::String; -use Cow::*; - #[stable(feature = "rust1", since = "1.0.0")] impl<'a, B: ?Sized> Borrow<B> for Cow<'a, B> where diff --git a/library/alloc/src/boxed.rs b/library/alloc/src/boxed.rs index 405430377e5..7de41259599 100644 --- a/library/alloc/src/boxed.rs +++ b/library/alloc/src/boxed.rs @@ -187,26 +187,26 @@ use core::any::Any; use core::async_iter::AsyncIterator; -use core::borrow; #[cfg(not(no_global_oom_handling))] use core::clone::CloneToUninit; use core::cmp::Ordering; use core::error::Error; -use core::fmt; use core::future::Future; use core::hash::{Hash, Hasher}; use core::iter::FusedIterator; -use core::marker::Tuple; -use core::marker::Unsize; +use core::marker::{Tuple, Unsize}; use core::mem::{self, SizedTypeProperties}; -use core::ops::{AsyncFn, AsyncFnMut, AsyncFnOnce}; use core::ops::{ - CoerceUnsized, Coroutine, CoroutineState, Deref, DerefMut, DerefPure, DispatchFromDyn, Receiver, + AsyncFn, AsyncFnMut, AsyncFnOnce, CoerceUnsized, Coroutine, CoroutineState, Deref, DerefMut, + DerefPure, DispatchFromDyn, Receiver, }; -use core::pin::Pin; +use core::pin::{Pin, PinCoerceUnsized}; use core::ptr::{self, addr_of_mut, NonNull, Unique}; -use core::slice; use core::task::{Context, Poll}; +use core::{borrow, fmt, slice}; + +#[unstable(feature = "thin_box", issue = "92791")] +pub use thin::ThinBox; #[cfg(not(no_global_oom_handling))] use crate::alloc::handle_alloc_error; @@ -222,9 +222,6 @@ use crate::vec; #[cfg(not(no_global_oom_handling))] use crate::vec::Vec; -#[unstable(feature = "thin_box", issue = "92791")] -pub use thin::ThinBox; - mod thin; /// A pointer type that uniquely owns a heap allocation of type `T`. @@ -1176,6 +1173,7 @@ impl<T: ?Sized, A: Allocator> Box<T, A> { /// ``` /// /// [memory layout]: self#memory-layout + #[must_use = "losing the pointer will leak memory"] #[stable(feature = "box_raw", since = "1.4.0")] #[inline] pub fn into_raw(b: Self) -> *mut T { @@ -1229,6 +1227,7 @@ impl<T: ?Sized, A: Allocator> Box<T, A> { /// ``` /// /// [memory layout]: self#memory-layout + #[must_use = "losing the pointer will leak memory"] #[unstable(feature = "allocator_api", issue = "32838")] #[inline] pub fn into_raw_with_allocator(b: Self) -> (*mut T, A) { @@ -1268,9 +1267,11 @@ impl<T: ?Sized, A: Allocator> Box<T, A> { } /// Consumes and leaks the `Box`, returning a mutable reference, - /// `&'a mut T`. Note that the type `T` must outlive the chosen lifetime - /// `'a`. If the type has only static references, or none at all, then this - /// may be chosen to be `'static`. + /// `&'a mut T`. + /// + /// Note that the type `T` must outlive the chosen lifetime `'a`. If the type + /// has only static references, or none at all, then this may be chosen to be + /// `'static`. /// /// This function is mainly useful for data that lives for the remainder of /// the program's life. Dropping the returned reference will cause a memory @@ -1853,7 +1854,7 @@ impl<T, const N: usize> TryFrom<Vec<T>> for Box<[T; N]> { } impl<A: Allocator> Box<dyn Any, A> { - /// Attempt to downcast the box to a concrete type. + /// Attempts to downcast the box to a concrete type. /// /// # Examples /// @@ -1912,7 +1913,7 @@ impl<A: Allocator> Box<dyn Any, A> { } impl<A: Allocator> Box<dyn Any + Send, A> { - /// Attempt to downcast the box to a concrete type. + /// Attempts to downcast the box to a concrete type. /// /// # Examples /// @@ -1971,7 +1972,7 @@ impl<A: Allocator> Box<dyn Any + Send, A> { } impl<A: Allocator> Box<dyn Any + Send + Sync, A> { - /// Attempt to downcast the box to a concrete type. + /// Attempts to downcast the box to a concrete type. /// /// # Examples /// @@ -2725,3 +2726,6 @@ impl<T: core::error::Error> core::error::Error for Box<T> { core::error::Error::provide(&**self, request); } } + +#[unstable(feature = "pin_coerce_unsized_trait", issue = "123430")] +unsafe impl<T: ?Sized, A: Allocator> PinCoerceUnsized for Box<T, A> {} diff --git a/library/alloc/src/boxed/thin.rs b/library/alloc/src/boxed/thin.rs index e9bfecba160..9baded3a521 100644 --- a/library/alloc/src/boxed/thin.rs +++ b/library/alloc/src/boxed/thin.rs @@ -2,7 +2,6 @@ //! <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}; #[cfg(not(no_global_oom_handling))] @@ -14,8 +13,9 @@ use core::mem; #[cfg(not(no_global_oom_handling))] use core::mem::SizedTypeProperties; use core::ops::{Deref, DerefMut}; -use core::ptr::Pointee; -use core::ptr::{self, NonNull}; +use core::ptr::{self, NonNull, Pointee}; + +use crate::alloc::{self, Layout, LayoutError}; /// ThinBox. /// diff --git a/library/alloc/src/collections/binary_heap/mod.rs b/library/alloc/src/collections/binary_heap/mod.rs index fe1ff241395..88701370c10 100644 --- a/library/alloc/src/collections/binary_heap/mod.rs +++ b/library/alloc/src/collections/binary_heap/mod.rs @@ -144,12 +144,11 @@ #![stable(feature = "rust1", since = "1.0.0")] use core::alloc::Allocator; -use core::fmt; use core::iter::{FusedIterator, InPlaceIterable, SourceIter, TrustedFused, TrustedLen}; use core::mem::{self, swap, ManuallyDrop}; use core::num::NonZero; use core::ops::{Deref, DerefMut}; -use core::ptr; +use core::{fmt, ptr}; use crate::alloc::Global; use crate::collections::TryReserveError; @@ -965,6 +964,7 @@ impl<T, A: Allocator> BinaryHeap<T, A> { } /// Returns an iterator which retrieves elements in heap order. + /// /// This method consumes the original heap. /// /// # Examples @@ -1361,7 +1361,7 @@ struct Hole<'a, T: 'a> { } impl<'a, T> Hole<'a, T> { - /// Create a new `Hole` at index `pos`. + /// Creates a new `Hole` at index `pos`. /// /// Unsafe because pos must be within the data slice. #[inline] @@ -1433,6 +1433,20 @@ pub struct Iter<'a, T: 'a> { iter: slice::Iter<'a, T>, } +#[stable(feature = "default_iters_sequel", since = "CURRENT_RUSTC_VERSION")] +impl<T> Default for Iter<'_, T> { + /// Creates an empty `binary_heap::Iter`. + /// + /// ``` + /// # use std::collections::binary_heap; + /// let iter: binary_heap::Iter<'_, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Iter { iter: Default::default() } + } +} + #[stable(feature = "collection_debug", since = "1.17.0")] impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { diff --git a/library/alloc/src/collections/binary_heap/tests.rs b/library/alloc/src/collections/binary_heap/tests.rs index d4bc6226a14..1cb07c62149 100644 --- a/library/alloc/src/collections/binary_heap/tests.rs +++ b/library/alloc/src/collections/binary_heap/tests.rs @@ -1,7 +1,8 @@ +use std::panic::{catch_unwind, AssertUnwindSafe}; + use super::*; use crate::boxed::Box; use crate::testing::crash_test::{CrashTestDummy, Panic}; -use std::panic::{catch_unwind, AssertUnwindSafe}; #[test] fn test_iterator() { @@ -504,11 +505,12 @@ fn test_retain_catch_unwind() { #[cfg(not(target_os = "emscripten"))] #[cfg_attr(not(panic = "unwind"), ignore = "test requires unwinding support")] fn panic_safe() { - use rand::seq::SliceRandom; use std::cmp; use std::panic::{self, AssertUnwindSafe}; use std::sync::atomic::{AtomicUsize, Ordering}; + use rand::seq::SliceRandom; + static DROP_COUNTER: AtomicUsize = AtomicUsize::new(0); #[derive(Eq, PartialEq, Ord, Clone, Debug)] diff --git a/library/alloc/src/collections/btree/append.rs b/library/alloc/src/collections/btree/append.rs index b6989afb625..47372938fbe 100644 --- a/library/alloc/src/collections/btree/append.rs +++ b/library/alloc/src/collections/btree/append.rs @@ -1,8 +1,9 @@ -use super::merge_iter::MergeIterInner; -use super::node::{self, Root}; use core::alloc::Allocator; use core::iter::FusedIterator; +use super::merge_iter::MergeIterInner; +use super::node::{self, Root}; + impl<K, V> Root<K, V> { /// Appends all key-value pairs from the union of two ascending iterators, /// incrementing a `length` variable along the way. The latter makes it diff --git a/library/alloc/src/collections/btree/fix.rs b/library/alloc/src/collections/btree/fix.rs index 91b61218005..4c1e19ead40 100644 --- a/library/alloc/src/collections/btree/fix.rs +++ b/library/alloc/src/collections/btree/fix.rs @@ -1,7 +1,10 @@ -use super::map::MIN_LEN; -use super::node::{marker, ForceResult::*, Handle, LeftOrRight::*, NodeRef, Root}; use core::alloc::Allocator; +use super::map::MIN_LEN; +use super::node::ForceResult::*; +use super::node::LeftOrRight::*; +use super::node::{marker, Handle, NodeRef, Root}; + impl<'a, K: 'a, V: 'a> NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal> { /// Stocks up a possibly underfull node by merging with or stealing from a /// sibling. If successful but at the cost of shrinking the parent node, diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index 3875f61efaf..f6f773cc42a 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -1,4 +1,3 @@ -use crate::vec::Vec; use core::borrow::Borrow; use core::cmp::Ordering; use core::error::Error; @@ -10,20 +9,21 @@ use core::mem::{self, ManuallyDrop}; use core::ops::{Bound, Index, RangeBounds}; use core::ptr; -use crate::alloc::{Allocator, Global}; - use super::borrow::DormantMutRef; use super::dedup_sorted_iter::DedupSortedIter; use super::navigate::{LazyLeafRange, LeafRange}; -use super::node::{self, marker, ForceResult::*, Handle, NodeRef, Root}; -use super::search::{SearchBound, SearchResult::*}; +use super::node::ForceResult::*; +use super::node::{self, marker, Handle, NodeRef, Root}; +use super::search::SearchBound; +use super::search::SearchResult::*; use super::set_val::SetValZST; +use crate::alloc::{Allocator, Global}; +use crate::vec::Vec; mod entry; #[stable(feature = "rust1", since = "1.0.0")] pub use entry::{Entry, OccupiedEntry, OccupiedError, VacantEntry}; - use Entry::*; /// Minimum number of elements in a node that is not a root. @@ -2016,6 +2016,20 @@ impl<K, V> Default for Range<'_, K, V> { } } +#[stable(feature = "default_iters_sequel", since = "CURRENT_RUSTC_VERSION")] +impl<K, V> Default for RangeMut<'_, K, V> { + /// Creates an empty `btree_map::RangeMut`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::RangeMut<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.count(), 0); + /// ``` + fn default() -> Self { + RangeMut { inner: Default::default(), _marker: PhantomData } + } +} + #[stable(feature = "map_values_mut", since = "1.10.0")] impl<'a, K, V> Iterator for ValuesMut<'a, K, V> { type Item = &'a mut V; @@ -2050,6 +2064,20 @@ impl<K, V> ExactSizeIterator for ValuesMut<'_, K, V> { #[stable(feature = "fused", since = "1.26.0")] impl<K, V> FusedIterator for ValuesMut<'_, K, V> {} +#[stable(feature = "default_iters_sequel", since = "CURRENT_RUSTC_VERSION")] +impl<K, V> Default for ValuesMut<'_, K, V> { + /// Creates an empty `btree_map::ValuesMut`. + /// + /// ``` + /// # use std::collections::btree_map; + /// let iter: btree_map::ValuesMut<'_, u8, u8> = Default::default(); + /// assert_eq!(iter.count(), 0); + /// ``` + fn default() -> Self { + ValuesMut { inner: Default::default() } + } +} + #[stable(feature = "map_into_keys_values", since = "1.54.0")] impl<K, V, A: Allocator + Clone> Iterator for IntoKeys<K, V, A> { type Item = K; @@ -2921,7 +2949,7 @@ impl<'a, K, V> Cursor<'a, K, V> { /// Returns a reference to the key and value of the next element without /// moving the cursor. /// - /// If the cursor is at the end of the map then `None` is returned + /// If the cursor is at the end of the map then `None` is returned. #[unstable(feature = "btree_cursors", issue = "107540")] pub fn peek_next(&self) -> Option<(&'a K, &'a V)> { self.clone().next() @@ -2963,7 +2991,7 @@ impl<'a, K, V, A> CursorMut<'a, K, V, A> { /// Returns a reference to the key and value of the next element without /// moving the cursor. /// - /// If the cursor is at the end of the map then `None` is returned + /// If the cursor is at the end of the map then `None` is returned. #[unstable(feature = "btree_cursors", issue = "107540")] pub fn peek_next(&mut self) -> Option<(&K, &mut V)> { let (k, v) = self.inner.peek_next()?; @@ -3061,7 +3089,7 @@ impl<'a, K, V, A> CursorMutKey<'a, K, V, A> { /// Returns a reference to the key and value of the next element without /// moving the cursor. /// - /// If the cursor is at the end of the map then `None` is returned + /// If the cursor is at the end of the map then `None` is returned. #[unstable(feature = "btree_cursors", issue = "107540")] pub fn peek_next(&mut self) -> Option<(&mut K, &mut V)> { let current = self.current.as_mut()?; diff --git a/library/alloc/src/collections/btree/map/entry.rs b/library/alloc/src/collections/btree/map/entry.rs index 66eb991c6d4..d128ad8ee5f 100644 --- a/library/alloc/src/collections/btree/map/entry.rs +++ b/library/alloc/src/collections/btree/map/entry.rs @@ -2,13 +2,12 @@ use core::fmt::{self, Debug}; use core::marker::PhantomData; use core::mem; -use crate::alloc::{Allocator, Global}; +use Entry::*; use super::super::borrow::DormantMutRef; use super::super::node::{marker, Handle, NodeRef}; use super::BTreeMap; - -use Entry::*; +use crate::alloc::{Allocator, Global}; /// A view into a single entry in a map, which may either be vacant or occupied. /// @@ -189,6 +188,7 @@ impl<'a, K: Ord, V, A: Allocator + Clone> Entry<'a, K, V, A> { } /// Ensures a value is in the entry by inserting, if empty, the result of the default function. + /// /// This method allows for generating key-derived values for insertion by providing the default /// function a reference to the key that was moved during the `.entry(key)` method call. /// diff --git a/library/alloc/src/collections/btree/map/tests.rs b/library/alloc/src/collections/btree/map/tests.rs index ba1f38dcc3e..ff1254a5a0c 100644 --- a/library/alloc/src/collections/btree/map/tests.rs +++ b/library/alloc/src/collections/btree/map/tests.rs @@ -1,3 +1,10 @@ +use core::assert_matches::assert_matches; +use std::iter; +use std::ops::Bound::{Excluded, Included, Unbounded}; +use std::panic::{catch_unwind, AssertUnwindSafe}; +use std::sync::atomic::AtomicUsize; +use std::sync::atomic::Ordering::SeqCst; + use super::*; use crate::boxed::Box; use crate::fmt::Debug; @@ -6,11 +13,6 @@ use crate::string::{String, ToString}; use crate::testing::crash_test::{CrashTestDummy, Panic}; use crate::testing::ord_chaos::{Cyclic3, Governed, Governor}; use crate::testing::rng::DeterministicRng; -use core::assert_matches::assert_matches; -use std::iter; -use std::ops::Bound::{Excluded, Included, Unbounded}; -use std::panic::{catch_unwind, AssertUnwindSafe}; -use std::sync::atomic::{AtomicUsize, Ordering::SeqCst}; // Minimum number of elements to insert, to guarantee a tree with 2 levels, // i.e., a tree who's root is an internal node at height 1, with edges to leaf nodes. diff --git a/library/alloc/src/collections/btree/mem.rs b/library/alloc/src/collections/btree/mem.rs index e1363d1ae1f..d738c5c47b4 100644 --- a/library/alloc/src/collections/btree/mem.rs +++ b/library/alloc/src/collections/btree/mem.rs @@ -1,6 +1,4 @@ -use core::intrinsics; -use core::mem; -use core::ptr; +use core::{intrinsics, mem, ptr}; /// This replaces the value behind the `v` unique reference by calling the /// relevant function. diff --git a/library/alloc/src/collections/btree/navigate.rs b/library/alloc/src/collections/btree/navigate.rs index 5e6a26f65c4..f5c621e2c17 100644 --- a/library/alloc/src/collections/btree/navigate.rs +++ b/library/alloc/src/collections/btree/navigate.rs @@ -1,11 +1,10 @@ use core::borrow::Borrow; -use core::hint; use core::ops::RangeBounds; -use core::ptr; +use core::{hint, ptr}; -use super::node::{marker, ForceResult::*, Handle, NodeRef}; +use super::node::ForceResult::*; +use super::node::{marker, Handle, NodeRef}; use super::search::SearchBound; - use crate::alloc::Allocator; // `front` and `back` are always both `None` or both `Some`. pub struct LeafRange<BorrowType, K, V> { diff --git a/library/alloc/src/collections/btree/remove.rs b/library/alloc/src/collections/btree/remove.rs index 0904299254f..c46422c2f1d 100644 --- a/library/alloc/src/collections/btree/remove.rs +++ b/library/alloc/src/collections/btree/remove.rs @@ -1,7 +1,10 @@ -use super::map::MIN_LEN; -use super::node::{marker, ForceResult::*, Handle, LeftOrRight::*, NodeRef}; use core::alloc::Allocator; +use super::map::MIN_LEN; +use super::node::ForceResult::*; +use super::node::LeftOrRight::*; +use super::node::{marker, Handle, NodeRef}; + impl<'a, K: 'a, V: 'a> Handle<NodeRef<marker::Mut<'a>, K, V, marker::LeafOrInternal>, marker::KV> { /// Removes a key-value pair from the tree, and returns that pair, as well as /// the leaf edge corresponding to that former pair. It's possible this empties diff --git a/library/alloc/src/collections/btree/search.rs b/library/alloc/src/collections/btree/search.rs index ad3522b4e04..1d5c927175e 100644 --- a/library/alloc/src/collections/btree/search.rs +++ b/library/alloc/src/collections/btree/search.rs @@ -2,11 +2,12 @@ use core::borrow::Borrow; use core::cmp::Ordering; use core::ops::{Bound, RangeBounds}; -use super::node::{marker, ForceResult::*, Handle, NodeRef}; - use SearchBound::*; use SearchResult::*; +use super::node::ForceResult::*; +use super::node::{marker, Handle, NodeRef}; + pub enum SearchBound<T> { /// An inclusive bound to look for, just like `Bound::Included(T)`. Included(T), diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs index b0bd6ef2d3c..973e7c66067 100644 --- a/library/alloc/src/collections/btree/set.rs +++ b/library/alloc/src/collections/btree/set.rs @@ -1,4 +1,3 @@ -use crate::vec::Vec; use core::borrow::Borrow; use core::cmp::Ordering::{self, Equal, Greater, Less}; use core::cmp::{max, min}; @@ -6,14 +5,14 @@ use core::fmt::{self, Debug}; use core::hash::{Hash, Hasher}; use core::iter::{FusedIterator, Peekable}; use core::mem::ManuallyDrop; -use core::ops::{BitAnd, BitOr, BitXor, RangeBounds, Sub}; +use core::ops::{BitAnd, BitOr, BitXor, Bound, RangeBounds, Sub}; use super::map::{BTreeMap, Keys}; use super::merge_iter::MergeIterInner; use super::set_val::SetValZST; use super::Recover; - use crate::alloc::{Allocator, Global}; +use crate::vec::Vec; /// An ordered set based on a B-Tree. /// @@ -1183,6 +1182,178 @@ impl<T, A: Allocator + Clone> BTreeSet<T, A> { pub const fn is_empty(&self) -> bool { self.len() == 0 } + + /// Returns a [`Cursor`] pointing at the gap before the smallest element + /// greater than the given bound. + /// + /// Passing `Bound::Included(x)` will return a cursor pointing to the + /// gap before the smallest element greater than or equal to `x`. + /// + /// Passing `Bound::Excluded(x)` will return a cursor pointing to the + /// gap before the smallest element greater than `x`. + /// + /// Passing `Bound::Unbounded` will return a cursor pointing to the + /// gap before the smallest element in the set. + /// + /// # Examples + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeSet; + /// use std::ops::Bound; + /// + /// let set = BTreeSet::from([1, 2, 3, 4]); + /// + /// let cursor = set.lower_bound(Bound::Included(&2)); + /// assert_eq!(cursor.peek_prev(), Some(&1)); + /// assert_eq!(cursor.peek_next(), Some(&2)); + /// + /// let cursor = set.lower_bound(Bound::Excluded(&2)); + /// assert_eq!(cursor.peek_prev(), Some(&2)); + /// assert_eq!(cursor.peek_next(), Some(&3)); + /// + /// let cursor = set.lower_bound(Bound::Unbounded); + /// assert_eq!(cursor.peek_prev(), None); + /// assert_eq!(cursor.peek_next(), Some(&1)); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn lower_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, T> + where + T: Borrow<Q> + Ord, + Q: Ord, + { + Cursor { inner: self.map.lower_bound(bound) } + } + + /// Returns a [`CursorMut`] pointing at the gap before the smallest element + /// greater than the given bound. + /// + /// Passing `Bound::Included(x)` will return a cursor pointing to the + /// gap before the smallest element greater than or equal to `x`. + /// + /// Passing `Bound::Excluded(x)` will return a cursor pointing to the + /// gap before the smallest element greater than `x`. + /// + /// Passing `Bound::Unbounded` will return a cursor pointing to the + /// gap before the smallest element in the set. + /// + /// # Examples + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeSet; + /// use std::ops::Bound; + /// + /// let mut set = BTreeSet::from([1, 2, 3, 4]); + /// + /// let mut cursor = set.lower_bound_mut(Bound::Included(&2)); + /// assert_eq!(cursor.peek_prev(), Some(&1)); + /// assert_eq!(cursor.peek_next(), Some(&2)); + /// + /// let mut cursor = set.lower_bound_mut(Bound::Excluded(&2)); + /// assert_eq!(cursor.peek_prev(), Some(&2)); + /// assert_eq!(cursor.peek_next(), Some(&3)); + /// + /// let mut cursor = set.lower_bound_mut(Bound::Unbounded); + /// assert_eq!(cursor.peek_prev(), None); + /// assert_eq!(cursor.peek_next(), Some(&1)); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn lower_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, T, A> + where + T: Borrow<Q> + Ord, + Q: Ord, + { + CursorMut { inner: self.map.lower_bound_mut(bound) } + } + + /// Returns a [`Cursor`] pointing at the gap after the greatest element + /// smaller than the given bound. + /// + /// Passing `Bound::Included(x)` will return a cursor pointing to the + /// gap after the greatest element smaller than or equal to `x`. + /// + /// Passing `Bound::Excluded(x)` will return a cursor pointing to the + /// gap after the greatest element smaller than `x`. + /// + /// Passing `Bound::Unbounded` will return a cursor pointing to the + /// gap after the greatest element in the set. + /// + /// # Examples + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeSet; + /// use std::ops::Bound; + /// + /// let set = BTreeSet::from([1, 2, 3, 4]); + /// + /// let cursor = set.upper_bound(Bound::Included(&3)); + /// assert_eq!(cursor.peek_prev(), Some(&3)); + /// assert_eq!(cursor.peek_next(), Some(&4)); + /// + /// let cursor = set.upper_bound(Bound::Excluded(&3)); + /// assert_eq!(cursor.peek_prev(), Some(&2)); + /// assert_eq!(cursor.peek_next(), Some(&3)); + /// + /// let cursor = set.upper_bound(Bound::Unbounded); + /// assert_eq!(cursor.peek_prev(), Some(&4)); + /// assert_eq!(cursor.peek_next(), None); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn upper_bound<Q: ?Sized>(&self, bound: Bound<&Q>) -> Cursor<'_, T> + where + T: Borrow<Q> + Ord, + Q: Ord, + { + Cursor { inner: self.map.upper_bound(bound) } + } + + /// Returns a [`CursorMut`] pointing at the gap after the greatest element + /// smaller than the given bound. + /// + /// Passing `Bound::Included(x)` will return a cursor pointing to the + /// gap after the greatest element smaller than or equal to `x`. + /// + /// Passing `Bound::Excluded(x)` will return a cursor pointing to the + /// gap after the greatest element smaller than `x`. + /// + /// Passing `Bound::Unbounded` will return a cursor pointing to the + /// gap after the greatest element in the set. + /// + /// # Examples + /// + /// ``` + /// #![feature(btree_cursors)] + /// + /// use std::collections::BTreeSet; + /// use std::ops::Bound; + /// + /// let mut set = BTreeSet::from([1, 2, 3, 4]); + /// + /// let mut cursor = unsafe { set.upper_bound_mut(Bound::Included(&3)) }; + /// assert_eq!(cursor.peek_prev(), Some(&3)); + /// assert_eq!(cursor.peek_next(), Some(&4)); + /// + /// let mut cursor = unsafe { set.upper_bound_mut(Bound::Excluded(&3)) }; + /// assert_eq!(cursor.peek_prev(), Some(&2)); + /// assert_eq!(cursor.peek_next(), Some(&3)); + /// + /// let mut cursor = unsafe { set.upper_bound_mut(Bound::Unbounded) }; + /// assert_eq!(cursor.peek_prev(), Some(&4)); + /// assert_eq!(cursor.peek_next(), None); + /// ``` + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn upper_bound_mut<Q: ?Sized>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, T, A> + where + T: Borrow<Q> + Ord, + Q: Ord, + { + CursorMut { inner: self.map.upper_bound_mut(bound) } + } } #[stable(feature = "rust1", since = "1.0.0")] @@ -1817,5 +1988,414 @@ impl<'a, T: Ord> Iterator for Union<'a, T> { #[stable(feature = "fused", since = "1.26.0")] impl<T: Ord> FusedIterator for Union<'_, T> {} +/// A cursor over a `BTreeSet`. +/// +/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth. +/// +/// Cursors always point to a gap between two elements in the set, and can +/// operate on the two immediately adjacent elements. +/// +/// A `Cursor` is created with the [`BTreeSet::lower_bound`] and [`BTreeSet::upper_bound`] methods. +#[derive(Clone)] +#[unstable(feature = "btree_cursors", issue = "107540")] +pub struct Cursor<'a, K: 'a> { + inner: super::map::Cursor<'a, K, SetValZST>, +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl<K: Debug> Debug for Cursor<'_, K> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str("Cursor") + } +} + +/// A cursor over a `BTreeSet` with editing operations. +/// +/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can +/// safely mutate the set during iteration. This is because the lifetime of its yielded +/// references is tied to its own lifetime, instead of just the underlying map. This means +/// cursors cannot yield multiple elements at once. +/// +/// Cursors always point to a gap between two elements in the set, and can +/// operate on the two immediately adjacent elements. +/// +/// A `CursorMut` is created with the [`BTreeSet::lower_bound_mut`] and [`BTreeSet::upper_bound_mut`] +/// methods. +#[unstable(feature = "btree_cursors", issue = "107540")] +pub struct CursorMut<'a, K: 'a, #[unstable(feature = "allocator_api", issue = "32838")] A = Global> +{ + inner: super::map::CursorMut<'a, K, SetValZST, A>, +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl<K: Debug, A> Debug for CursorMut<'_, K, A> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str("CursorMut") + } +} + +/// A cursor over a `BTreeSet` with editing operations, and which allows +/// mutating elements. +/// +/// A `Cursor` is like an iterator, except that it can freely seek back-and-forth, and can +/// safely mutate the set during iteration. This is because the lifetime of its yielded +/// references is tied to its own lifetime, instead of just the underlying set. This means +/// cursors cannot yield multiple elements at once. +/// +/// Cursors always point to a gap between two elements in the set, and can +/// operate on the two immediately adjacent elements. +/// +/// A `CursorMutKey` is created from a [`CursorMut`] with the +/// [`CursorMut::with_mutable_key`] method. +/// +/// # Safety +/// +/// Since this cursor allows mutating elements, you must ensure that the +/// `BTreeSet` invariants are maintained. Specifically: +/// +/// * The newly inserted element must be unique in the tree. +/// * All elements in the tree must remain in sorted order. +#[unstable(feature = "btree_cursors", issue = "107540")] +pub struct CursorMutKey< + 'a, + K: 'a, + #[unstable(feature = "allocator_api", issue = "32838")] A = Global, +> { + inner: super::map::CursorMutKey<'a, K, SetValZST, A>, +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +impl<K: Debug, A> Debug for CursorMutKey<'_, K, A> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + f.write_str("CursorMutKey") + } +} + +impl<'a, K> Cursor<'a, K> { + /// Advances the cursor to the next gap, returning the element that it + /// moved over. + /// + /// If the cursor is already at the end of the set then `None` is returned + /// and the cursor is not moved. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn next(&mut self) -> Option<&'a K> { + self.inner.next().map(|(k, _)| k) + } + + /// Advances the cursor to the previous gap, returning the element that it + /// moved over. + /// + /// If the cursor is already at the start of the set then `None` is returned + /// and the cursor is not moved. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn prev(&mut self) -> Option<&'a K> { + self.inner.prev().map(|(k, _)| k) + } + + /// Returns a reference to next element without moving the cursor. + /// + /// If the cursor is at the end of the set then `None` is returned + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_next(&self) -> Option<&'a K> { + self.inner.peek_next().map(|(k, _)| k) + } + + /// Returns a reference to the previous element without moving the cursor. + /// + /// If the cursor is at the start of the set then `None` is returned. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_prev(&self) -> Option<&'a K> { + self.inner.peek_prev().map(|(k, _)| k) + } +} + +impl<'a, T, A> CursorMut<'a, T, A> { + /// Advances the cursor to the next gap, returning the element that it + /// moved over. + /// + /// If the cursor is already at the end of the set then `None` is returned + /// and the cursor is not moved. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn next(&mut self) -> Option<&T> { + self.inner.next().map(|(k, _)| k) + } + + /// Advances the cursor to the previous gap, returning the element that it + /// moved over. + /// + /// If the cursor is already at the start of the set then `None` is returned + /// and the cursor is not moved. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn prev(&mut self) -> Option<&T> { + self.inner.prev().map(|(k, _)| k) + } + + /// Returns a reference to the next element without moving the cursor. + /// + /// If the cursor is at the end of the set then `None` is returned. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_next(&mut self) -> Option<&T> { + self.inner.peek_next().map(|(k, _)| k) + } + + /// Returns a reference to the previous element without moving the cursor. + /// + /// If the cursor is at the start of the set then `None` is returned. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_prev(&mut self) -> Option<&T> { + self.inner.peek_prev().map(|(k, _)| k) + } + + /// Returns a read-only cursor pointing to the same location as the + /// `CursorMut`. + /// + /// The lifetime of the returned `Cursor` is bound to that of the + /// `CursorMut`, which means it cannot outlive the `CursorMut` and that the + /// `CursorMut` is frozen for the lifetime of the `Cursor`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn as_cursor(&self) -> Cursor<'_, T> { + Cursor { inner: self.inner.as_cursor() } + } + + /// Converts the cursor into a [`CursorMutKey`], which allows mutating + /// elements in the tree. + /// + /// # Safety + /// + /// Since this cursor allows mutating elements, you must ensure that the + /// `BTreeSet` invariants are maintained. Specifically: + /// + /// * The newly inserted element must be unique in the tree. + /// * All elements in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn with_mutable_key(self) -> CursorMutKey<'a, T, A> { + CursorMutKey { inner: unsafe { self.inner.with_mutable_key() } } + } +} + +impl<'a, T, A> CursorMutKey<'a, T, A> { + /// Advances the cursor to the next gap, returning the element that it + /// moved over. + /// + /// If the cursor is already at the end of the set then `None` is returned + /// and the cursor is not moved. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn next(&mut self) -> Option<&mut T> { + self.inner.next().map(|(k, _)| k) + } + + /// Advances the cursor to the previous gap, returning the element that it + /// moved over. + /// + /// If the cursor is already at the start of the set then `None` is returned + /// and the cursor is not moved. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn prev(&mut self) -> Option<&mut T> { + self.inner.prev().map(|(k, _)| k) + } + + /// Returns a reference to the next element without moving the cursor. + /// + /// If the cursor is at the end of the set then `None` is returned + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_next(&mut self) -> Option<&mut T> { + self.inner.peek_next().map(|(k, _)| k) + } + + /// Returns a reference to the previous element without moving the cursor. + /// + /// If the cursor is at the start of the set then `None` is returned. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn peek_prev(&mut self) -> Option<&mut T> { + self.inner.peek_prev().map(|(k, _)| k) + } + + /// Returns a read-only cursor pointing to the same location as the + /// `CursorMutKey`. + /// + /// The lifetime of the returned `Cursor` is bound to that of the + /// `CursorMutKey`, which means it cannot outlive the `CursorMutKey` and that the + /// `CursorMutKey` is frozen for the lifetime of the `Cursor`. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn as_cursor(&self) -> Cursor<'_, T> { + Cursor { inner: self.inner.as_cursor() } + } +} + +impl<'a, T: Ord, A: Allocator + Clone> CursorMut<'a, T, A> { + /// Inserts a new element into the set in the gap that the + /// cursor is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap before the + /// newly inserted element. + /// + /// # Safety + /// + /// You must ensure that the `BTreeSet` invariants are maintained. + /// Specifically: + /// + /// * The newly inserted element must be unique in the tree. + /// * All elements in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn insert_after_unchecked(&mut self, value: T) { + unsafe { self.inner.insert_after_unchecked(value, SetValZST) } + } + + /// Inserts a new element into the set in the gap that the + /// cursor is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap after the + /// newly inserted element. + /// + /// # Safety + /// + /// You must ensure that the `BTreeSet` invariants are maintained. + /// Specifically: + /// + /// * The newly inserted element must be unique in the tree. + /// * All elements in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn insert_before_unchecked(&mut self, value: T) { + unsafe { self.inner.insert_before_unchecked(value, SetValZST) } + } + + /// Inserts a new element into the set in the gap that the + /// cursor is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap before the + /// newly inserted element. + /// + /// If the inserted element is not greater than the element before the + /// cursor (if any), or if it not less than the element after the cursor (if + /// any), then an [`UnorderedKeyError`] is returned since this would + /// invalidate the [`Ord`] invariant between the elements of the set. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> { + self.inner.insert_after(value, SetValZST) + } + + /// Inserts a new element into the set in the gap that the + /// cursor is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap after the + /// newly inserted element. + /// + /// If the inserted element is not greater than the element before the + /// cursor (if any), or if it not less than the element after the cursor (if + /// any), then an [`UnorderedKeyError`] is returned since this would + /// invalidate the [`Ord`] invariant between the elements of the set. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn insert_before(&mut self, value: T) -> Result<(), UnorderedKeyError> { + self.inner.insert_before(value, SetValZST) + } + + /// Removes the next element from the `BTreeSet`. + /// + /// The element that was removed is returned. The cursor position is + /// unchanged (before the removed element). + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn remove_next(&mut self) -> Option<T> { + self.inner.remove_next().map(|(k, _)| k) + } + + /// Removes the precending element from the `BTreeSet`. + /// + /// The element that was removed is returned. The cursor position is + /// unchanged (after the removed element). + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn remove_prev(&mut self) -> Option<T> { + self.inner.remove_prev().map(|(k, _)| k) + } +} + +impl<'a, T: Ord, A: Allocator + Clone> CursorMutKey<'a, T, A> { + /// Inserts a new element into the set in the gap that the + /// cursor is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap before the + /// newly inserted element. + /// + /// # Safety + /// + /// You must ensure that the `BTreeSet` invariants are maintained. + /// Specifically: + /// + /// * The key of the newly inserted element must be unique in the tree. + /// * All elements in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn insert_after_unchecked(&mut self, value: T) { + unsafe { self.inner.insert_after_unchecked(value, SetValZST) } + } + + /// Inserts a new element into the set in the gap that the + /// cursor is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap after the + /// newly inserted element. + /// + /// # Safety + /// + /// You must ensure that the `BTreeSet` invariants are maintained. + /// Specifically: + /// + /// * The newly inserted element must be unique in the tree. + /// * All elements in the tree must remain in sorted order. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub unsafe fn insert_before_unchecked(&mut self, value: T) { + unsafe { self.inner.insert_before_unchecked(value, SetValZST) } + } + + /// Inserts a new element into the set in the gap that the + /// cursor is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap before the + /// newly inserted element. + /// + /// If the inserted element is not greater than the element before the + /// cursor (if any), or if it not less than the element after the cursor (if + /// any), then an [`UnorderedKeyError`] is returned since this would + /// invalidate the [`Ord`] invariant between the elements of the set. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn insert_after(&mut self, value: T) -> Result<(), UnorderedKeyError> { + self.inner.insert_after(value, SetValZST) + } + + /// Inserts a new element into the set in the gap that the + /// cursor is currently pointing to. + /// + /// After the insertion the cursor will be pointing at the gap after the + /// newly inserted element. + /// + /// If the inserted element is not greater than the element before the + /// cursor (if any), or if it not less than the element after the cursor (if + /// any), then an [`UnorderedKeyError`] is returned since this would + /// invalidate the [`Ord`] invariant between the elements of the set. + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn insert_before(&mut self, value: T) -> Result<(), UnorderedKeyError> { + self.inner.insert_before(value, SetValZST) + } + + /// Removes the next element from the `BTreeSet`. + /// + /// The element that was removed is returned. The cursor position is + /// unchanged (before the removed element). + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn remove_next(&mut self) -> Option<T> { + self.inner.remove_next().map(|(k, _)| k) + } + + /// Removes the precending element from the `BTreeSet`. + /// + /// The element that was removed is returned. The cursor position is + /// unchanged (after the removed element). + #[unstable(feature = "btree_cursors", issue = "107540")] + pub fn remove_prev(&mut self) -> Option<T> { + self.inner.remove_prev().map(|(k, _)| k) + } +} + +#[unstable(feature = "btree_cursors", issue = "107540")] +pub use super::map::UnorderedKeyError; + #[cfg(test)] mod tests; diff --git a/library/alloc/src/collections/btree/set/tests.rs b/library/alloc/src/collections/btree/set/tests.rs index 48bf7674138..f947b6108c9 100644 --- a/library/alloc/src/collections/btree/set/tests.rs +++ b/library/alloc/src/collections/btree/set/tests.rs @@ -1,8 +1,9 @@ +use std::ops::Bound::{Excluded, Included}; +use std::panic::{catch_unwind, AssertUnwindSafe}; + use super::*; use crate::testing::crash_test::{CrashTestDummy, Panic}; use crate::testing::rng::DeterministicRng; -use std::ops::Bound::{Excluded, Included}; -use std::panic::{catch_unwind, AssertUnwindSafe}; #[test] fn test_clone_eq() { diff --git a/library/alloc/src/collections/btree/split.rs b/library/alloc/src/collections/btree/split.rs index 638dc98fc3e..c188ed1da61 100644 --- a/library/alloc/src/collections/btree/split.rs +++ b/library/alloc/src/collections/btree/split.rs @@ -1,8 +1,10 @@ -use super::node::{ForceResult::*, Root}; -use super::search::SearchResult::*; use core::alloc::Allocator; use core::borrow::Borrow; +use super::node::ForceResult::*; +use super::node::Root; +use super::search::SearchResult::*; + impl<K, V> Root<K, V> { /// Calculates the length of both trees that result from splitting up /// a given number of distinct key-value pairs. diff --git a/library/alloc/src/collections/linked_list.rs b/library/alloc/src/collections/linked_list.rs index 077483a174b..0cd410c0fb7 100644 --- a/library/alloc/src/collections/linked_list.rs +++ b/library/alloc/src/collections/linked_list.rs @@ -13,12 +13,11 @@ #![stable(feature = "rust1", since = "1.0.0")] use core::cmp::Ordering; -use core::fmt; use core::hash::{Hash, Hasher}; use core::iter::FusedIterator; use core::marker::PhantomData; -use core::mem; use core::ptr::NonNull; +use core::{fmt, mem}; use super::SpecExtend; use crate::alloc::{Allocator, Global}; diff --git a/library/alloc/src/collections/linked_list/tests.rs b/library/alloc/src/collections/linked_list/tests.rs index d3744c5a9d0..9b3c9ac5ce5 100644 --- a/library/alloc/src/collections/linked_list/tests.rs +++ b/library/alloc/src/collections/linked_list/tests.rs @@ -1,12 +1,12 @@ -use super::*; -use crate::testing::crash_test::{CrashTestDummy, Panic}; -use crate::vec::Vec; - use std::panic::{catch_unwind, AssertUnwindSafe}; use std::thread; use rand::RngCore; +use super::*; +use crate::testing::crash_test::{CrashTestDummy, Panic}; +use crate::vec::Vec; + #[test] fn test_basic() { let mut m = LinkedList::<Box<_>>::new(); @@ -1167,9 +1167,7 @@ fn test_drop_panic() { #[test] fn test_allocator() { - use core::alloc::AllocError; - use core::alloc::Allocator; - use core::alloc::Layout; + use core::alloc::{AllocError, Allocator, Layout}; use core::cell::Cell; struct A { diff --git a/library/alloc/src/collections/mod.rs b/library/alloc/src/collections/mod.rs index 705b81535c2..020cf4d7365 100644 --- a/library/alloc/src/collections/mod.rs +++ b/library/alloc/src/collections/mod.rs @@ -27,33 +27,30 @@ pub mod btree_set { pub use super::btree::set::*; } +use core::fmt::Display; + #[cfg(not(no_global_oom_handling))] #[stable(feature = "rust1", since = "1.0.0")] #[doc(no_inline)] pub use binary_heap::BinaryHeap; - #[cfg(not(no_global_oom_handling))] #[stable(feature = "rust1", since = "1.0.0")] #[doc(no_inline)] pub use btree_map::BTreeMap; - #[cfg(not(no_global_oom_handling))] #[stable(feature = "rust1", since = "1.0.0")] #[doc(no_inline)] pub use btree_set::BTreeSet; - #[cfg(not(no_global_oom_handling))] #[stable(feature = "rust1", since = "1.0.0")] #[doc(no_inline)] pub use linked_list::LinkedList; - #[cfg(not(no_global_oom_handling))] #[stable(feature = "rust1", since = "1.0.0")] #[doc(no_inline)] pub use vec_deque::VecDeque; use crate::alloc::{Layout, LayoutError}; -use core::fmt::Display; /// The error type for `try_reserve` methods. #[derive(Clone, PartialEq, Eq, Debug)] diff --git a/library/alloc/src/collections/vec_deque/drain.rs b/library/alloc/src/collections/vec_deque/drain.rs index 1373e601492..44fcef4ed7d 100644 --- a/library/alloc/src/collections/vec_deque/drain.rs +++ b/library/alloc/src/collections/vec_deque/drain.rs @@ -4,9 +4,8 @@ use core::mem::{self, SizedTypeProperties}; use core::ptr::NonNull; use core::{fmt, ptr}; -use crate::alloc::{Allocator, Global}; - use super::VecDeque; +use crate::alloc::{Allocator, Global}; /// A draining iterator over the elements of a `VecDeque`. /// diff --git a/library/alloc/src/collections/vec_deque/into_iter.rs b/library/alloc/src/collections/vec_deque/into_iter.rs index 4747517393c..7be3de16b2d 100644 --- a/library/alloc/src/collections/vec_deque/into_iter.rs +++ b/library/alloc/src/collections/vec_deque/into_iter.rs @@ -1,10 +1,11 @@ use core::iter::{FusedIterator, TrustedLen}; +use core::mem::MaybeUninit; use core::num::NonZero; -use core::{array, fmt, mem::MaybeUninit, ops::Try, ptr}; - -use crate::alloc::{Allocator, Global}; +use core::ops::Try; +use core::{array, fmt, ptr}; use super::VecDeque; +use crate::alloc::{Allocator, Global}; /// An owning iterator over the elements of a `VecDeque`. /// @@ -120,6 +121,7 @@ impl<T, A: Allocator> Iterator for IntoIter<T, A> { { match self.try_fold(init, |b, item| Ok::<B, !>(f(b, item))) { Ok(b) => b, + #[cfg(bootstrap)] Err(e) => match e {}, } } @@ -241,6 +243,7 @@ impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> { { match self.try_rfold(init, |b, item| Ok::<B, !>(f(b, item))) { Ok(b) => b, + #[cfg(bootstrap)] Err(e) => match e {}, } } diff --git a/library/alloc/src/collections/vec_deque/iter.rs b/library/alloc/src/collections/vec_deque/iter.rs index 5a5e7f70854..67b5b91c4d4 100644 --- a/library/alloc/src/collections/vec_deque/iter.rs +++ b/library/alloc/src/collections/vec_deque/iter.rs @@ -28,6 +28,20 @@ impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { } } +#[stable(feature = "default_iters_sequel", since = "CURRENT_RUSTC_VERSION")] +impl<T> Default for Iter<'_, T> { + /// Creates an empty `vec_deque::Iter`. + /// + /// ``` + /// # use std::collections::vec_deque; + /// let iter: vec_deque::Iter<'_, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + Iter { i1: Default::default(), i2: Default::default() } + } +} + // FIXME(#26925) Remove in favor of `#[derive(Clone)]` #[stable(feature = "rust1", since = "1.0.0")] impl<T> Clone for Iter<'_, T> { diff --git a/library/alloc/src/collections/vec_deque/iter_mut.rs b/library/alloc/src/collections/vec_deque/iter_mut.rs index 5061931afb7..2726e3e4252 100644 --- a/library/alloc/src/collections/vec_deque/iter_mut.rs +++ b/library/alloc/src/collections/vec_deque/iter_mut.rs @@ -28,6 +28,20 @@ impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> { } } +#[stable(feature = "default_iters_sequel", since = "CURRENT_RUSTC_VERSION")] +impl<T> Default for IterMut<'_, T> { + /// Creates an empty `vec_deque::IterMut`. + /// + /// ``` + /// # use std::collections::vec_deque; + /// let iter: vec_deque::IterMut<'_, u8> = Default::default(); + /// assert_eq!(iter.len(), 0); + /// ``` + fn default() -> Self { + IterMut { i1: Default::default(), i2: Default::default() } + } +} + #[stable(feature = "rust1", since = "1.0.0")] impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; diff --git a/library/alloc/src/collections/vec_deque/mod.rs b/library/alloc/src/collections/vec_deque/mod.rs index a07f250d7d8..dc725ec0f56 100644 --- a/library/alloc/src/collections/vec_deque/mod.rs +++ b/library/alloc/src/collections/vec_deque/mod.rs @@ -8,23 +8,19 @@ #![stable(feature = "rust1", since = "1.0.0")] use core::cmp::{self, Ordering}; -use core::fmt; use core::hash::{Hash, Hasher}; use core::iter::{repeat_n, repeat_with, ByRefSized}; -use core::mem::{ManuallyDrop, SizedTypeProperties}; -use core::ops::{Index, IndexMut, Range, RangeBounds}; -use core::ptr; -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 core::mem::{ManuallyDrop, SizedTypeProperties}; +use core::ops::{Index, IndexMut, Range, RangeBounds}; +use core::{fmt, ptr, slice}; use crate::alloc::{Allocator, Global}; -use crate::collections::TryReserveError; -use crate::collections::TryReserveErrorKind; +use crate::collections::{TryReserveError, TryReserveErrorKind}; use crate::raw_vec::RawVec; use crate::vec::Vec; diff --git a/library/alloc/src/collections/vec_deque/spec_extend.rs b/library/alloc/src/collections/vec_deque/spec_extend.rs index 6a89abc3ef9..a9b0fd073b5 100644 --- a/library/alloc/src/collections/vec_deque/spec_extend.rs +++ b/library/alloc/src/collections/vec_deque/spec_extend.rs @@ -1,9 +1,9 @@ -use crate::alloc::Allocator; -use crate::vec; use core::iter::TrustedLen; use core::slice; use super::VecDeque; +use crate::alloc::Allocator; +use crate::vec; // Specialization trait used for VecDeque::extend pub(super) trait SpecExtend<T, I> { diff --git a/library/alloc/src/ffi/c_str.rs b/library/alloc/src/ffi/c_str.rs index f1eb195b884..e32676a6543 100644 --- a/library/alloc/src/ffi/c_str.rs +++ b/library/alloc/src/ffi/c_str.rs @@ -3,25 +3,21 @@ #[cfg(test)] mod tests; -use crate::borrow::{Cow, ToOwned}; -use crate::boxed::Box; -use crate::rc::Rc; -use crate::slice::hack::into_vec; -use crate::string::String; -use crate::vec::Vec; use core::borrow::Borrow; use core::ffi::{c_char, CStr}; -use core::fmt; -use core::mem; use core::num::NonZero; -use core::ops; -use core::ptr; -use core::slice; use core::slice::memchr; use core::str::{self, Utf8Error}; +use core::{fmt, mem, ops, ptr, slice}; +use crate::borrow::{Cow, ToOwned}; +use crate::boxed::Box; +use crate::rc::Rc; +use crate::slice::hack::into_vec; +use crate::string::String; #[cfg(target_has_atomic = "ptr")] use crate::sync::Arc; +use crate::vec::Vec; /// A type representing an owned, C-compatible, nul-terminated string with no nul bytes in the /// middle. diff --git a/library/alloc/src/ffi/c_str/tests.rs b/library/alloc/src/ffi/c_str/tests.rs index 9f51e17a427..8b7172b3f20 100644 --- a/library/alloc/src/ffi/c_str/tests.rs +++ b/library/alloc/src/ffi/c_str/tests.rs @@ -1,10 +1,10 @@ -use super::*; use core::assert_matches::assert_matches; use core::ffi::FromBytesUntilNulError; -use core::hash::{Hash, Hasher}; - #[allow(deprecated)] use core::hash::SipHasher13 as DefaultHasher; +use core::hash::{Hash, Hasher}; + +use super::*; #[test] fn c_to_rust() { diff --git a/library/alloc/src/ffi/mod.rs b/library/alloc/src/ffi/mod.rs index 9fc1acc231b..4f9dc40a3cf 100644 --- a/library/alloc/src/ffi/mod.rs +++ b/library/alloc/src/ffi/mod.rs @@ -80,13 +80,12 @@ #![stable(feature = "alloc_ffi", since = "1.64.0")] -#[doc(no_inline)] -#[stable(feature = "alloc_c_string", since = "1.64.0")] -pub use self::c_str::{FromVecWithNulError, IntoStringError, NulError}; - #[doc(inline)] #[stable(feature = "alloc_c_string", since = "1.64.0")] pub use self::c_str::CString; +#[doc(no_inline)] +#[stable(feature = "alloc_c_string", since = "1.64.0")] +pub use self::c_str::{FromVecWithNulError, IntoStringError, NulError}; #[unstable(feature = "c_str_module", issue = "112134")] pub mod c_str; diff --git a/library/alloc/src/fmt.rs b/library/alloc/src/fmt.rs index c6bba619ae6..571fcd177aa 100644 --- a/library/alloc/src/fmt.rs +++ b/library/alloc/src/fmt.rs @@ -581,7 +581,7 @@ pub use core::fmt::Alignment; #[stable(feature = "rust1", since = "1.0.0")] pub use core::fmt::Error; #[unstable(feature = "debug_closure_helpers", issue = "117729")] -pub use core::fmt::FormatterFn; +pub use core::fmt::{from_fn, FromFn}; #[stable(feature = "rust1", since = "1.0.0")] pub use core::fmt::{write, Arguments}; #[stable(feature = "rust1", since = "1.0.0")] @@ -600,8 +600,7 @@ pub use core::fmt::{LowerHex, Pointer, UpperHex}; #[cfg(not(no_global_oom_handling))] use crate::string; -/// The `format` function takes an [`Arguments`] struct and returns the resulting -/// formatted string. +/// Takes an [`Arguments`] struct and returns the resulting formatted string. /// /// The [`Arguments`] instance can be created with the [`format_args!`] macro. /// diff --git a/library/alloc/src/lib.rs b/library/alloc/src/lib.rs index 49036077e2e..3e44adf73f0 100644 --- a/library/alloc/src/lib.rs +++ b/library/alloc/src/lib.rs @@ -86,6 +86,7 @@ #![warn(multiple_supertrait_upcastable)] #![allow(internal_features)] #![allow(rustdoc::redundant_explicit_links)] +#![warn(rustdoc::unescaped_backticks)] #![deny(ffi_unwind_calls)] // // Library features: @@ -116,7 +117,6 @@ #![feature(const_pin)] #![feature(const_refs_to_cell)] #![feature(const_size_of_val)] -#![feature(const_waker)] #![feature(core_intrinsics)] #![feature(deprecated_suggestion)] #![feature(deref_pure_trait)] @@ -138,6 +138,7 @@ #![feature(maybe_uninit_uninit_array_transpose)] #![feature(panic_internals)] #![feature(pattern)] +#![feature(pin_coerce_unsized_trait)] #![feature(ptr_internals)] #![feature(ptr_metadata)] #![feature(ptr_sub_ptr)] @@ -165,7 +166,6 @@ // // Language features: // tidy-alphabetical-start -#![cfg_attr(bootstrap, feature(c_unwind))] #![cfg_attr(not(test), feature(coroutine_trait))] #![cfg_attr(test, feature(panic_update_hook))] #![cfg_attr(test, feature(test))] diff --git a/library/alloc/src/raw_vec.rs b/library/alloc/src/raw_vec.rs index 7b7dae5a057..9c8fa7ceff4 100644 --- a/library/alloc/src/raw_vec.rs +++ b/library/alloc/src/raw_vec.rs @@ -1,10 +1,9 @@ #![unstable(feature = "raw_vec_internals", reason = "unstable const warnings", issue = "none")] -use core::alloc::LayoutError; -use core::cmp; -use core::hint; -use core::mem::{self, ManuallyDrop, MaybeUninit, SizedTypeProperties}; +use core::marker::PhantomData; +use core::mem::{ManuallyDrop, MaybeUninit, SizedTypeProperties}; use core::ptr::{self, NonNull, Unique}; +use core::{cmp, hint}; #[cfg(not(no_global_oom_handling))] use crate::alloc::handle_alloc_error; @@ -41,6 +40,13 @@ struct Cap(usize); impl Cap { const ZERO: Cap = unsafe { Cap(0) }; + + /// `Cap(cap)`, except if `T` is a ZST then `Cap::ZERO`. + /// + /// # Safety: cap must be <= `isize::MAX`. + unsafe fn new<T>(cap: usize) -> Self { + if T::IS_ZST { Cap::ZERO } else { unsafe { Self(cap) } } + } } /// A low-level utility for more ergonomically allocating, reallocating, and deallocating @@ -52,7 +58,7 @@ impl Cap { /// * Produces `Unique::dangling()` on zero-length allocations. /// * Avoids freeing `Unique::dangling()`. /// * Catches all overflows in capacity computations (promotes them to "capacity overflow" panics). -/// * Guards against 32-bit systems allocating more than isize::MAX bytes. +/// * Guards against 32-bit systems allocating more than `isize::MAX` bytes. /// * Guards against overflowing your length. /// * Calls `handle_alloc_error` for fallible allocations. /// * Contains a `ptr::Unique` and thus endows the user with all related benefits. @@ -67,7 +73,19 @@ impl Cap { /// `Box<[T]>`, since `capacity()` won't yield the length. #[allow(missing_debug_implementations)] pub(crate) struct RawVec<T, A: Allocator = Global> { - ptr: Unique<T>, + inner: RawVecInner<A>, + _marker: PhantomData<T>, +} + +/// Like a `RawVec`, but only generic over the allocator, not the type. +/// +/// As such, all the methods need the layout passed-in as a parameter. +/// +/// Having this separation reduces the amount of code we need to monomorphize, +/// as most operations don't need the actual type, just its layout. +#[allow(missing_debug_implementations)] +struct RawVecInner<A: Allocator = Global> { + ptr: Unique<u8>, /// Never used for ZSTs; it's `capacity()`'s responsibility to return usize::MAX in that case. /// /// # Safety @@ -91,8 +109,9 @@ impl<T> RawVec<T, Global> { /// `RawVec` with capacity `usize::MAX`. Useful for implementing /// delayed allocation. #[must_use] + #[rustc_const_stable(feature = "raw_vec_internals_const", since = "1.81")] pub const fn new() -> Self { - Self::new_in(Global) + Self { inner: RawVecInner::new::<T>(), _marker: PhantomData } } /// Creates a `RawVec` (on the system heap) with exactly the @@ -114,10 +133,7 @@ impl<T> RawVec<T, Global> { #[must_use] #[inline] pub fn with_capacity(capacity: usize) -> Self { - match Self::try_allocate_in(capacity, AllocInit::Uninitialized, Global) { - Ok(res) => res, - Err(err) => handle_error(err), - } + Self { inner: RawVecInner::with_capacity(capacity, T::LAYOUT), _marker: PhantomData } } /// Like `with_capacity`, but guarantees the buffer is zeroed. @@ -125,29 +141,56 @@ impl<T> RawVec<T, Global> { #[must_use] #[inline] pub fn with_capacity_zeroed(capacity: usize) -> Self { - Self::with_capacity_zeroed_in(capacity, Global) + Self { + inner: RawVecInner::with_capacity_zeroed_in(capacity, Global, T::LAYOUT), + _marker: PhantomData, + } } } -impl<T, A: Allocator> RawVec<T, A> { - // Tiny Vecs are dumb. Skip to: - // - 8 if the element size is 1, because any heap allocators is likely - // to round up a request of less than 8 bytes to at least 8 bytes. - // - 4 if elements are moderate-sized (<= 1 KiB). - // - 1 otherwise, to avoid wasting too much space for very short Vecs. - pub(crate) const MIN_NON_ZERO_CAP: usize = if mem::size_of::<T>() == 1 { +impl RawVecInner<Global> { + #[must_use] + #[rustc_const_stable(feature = "raw_vec_internals_const", since = "1.81")] + const fn new<T>() -> Self { + Self::new_in(Global, core::mem::align_of::<T>()) + } + + #[cfg(not(any(no_global_oom_handling, test)))] + #[must_use] + #[inline] + fn with_capacity(capacity: usize, elem_layout: Layout) -> Self { + match Self::try_allocate_in(capacity, AllocInit::Uninitialized, Global, elem_layout) { + Ok(res) => res, + Err(err) => handle_error(err), + } + } +} + +// Tiny Vecs are dumb. Skip to: +// - 8 if the element size is 1, because any heap allocators is likely +// to round up a request of less than 8 bytes to at least 8 bytes. +// - 4 if elements are moderate-sized (<= 1 KiB). +// - 1 otherwise, to avoid wasting too much space for very short Vecs. +const fn min_non_zero_cap(size: usize) -> usize { + if size == 1 { 8 - } else if mem::size_of::<T>() <= 1024 { + } else if size <= 1024 { 4 } else { 1 - }; + } +} + +impl<T, A: Allocator> RawVec<T, A> { + #[cfg(not(no_global_oom_handling))] + pub(crate) const MIN_NON_ZERO_CAP: usize = min_non_zero_cap(size_of::<T>()); /// Like `new`, but parameterized over the choice of allocator for /// the returned `RawVec`. + #[inline] + #[rustc_const_stable(feature = "raw_vec_internals_const", since = "1.81")] pub const fn new_in(alloc: A) -> Self { - // `cap: 0` means "unallocated". zero-sized types are ignored. - Self { ptr: Unique::dangling(), cap: Cap::ZERO, alloc } + Self { inner: RawVecInner::new_in(alloc, align_of::<T>()), _marker: PhantomData } } /// Like `with_capacity`, but parameterized over the choice of @@ -155,9 +198,9 @@ impl<T, A: Allocator> RawVec<T, A> { #[cfg(not(no_global_oom_handling))] #[inline] pub fn with_capacity_in(capacity: usize, alloc: A) -> Self { - match Self::try_allocate_in(capacity, AllocInit::Uninitialized, alloc) { - Ok(res) => res, - Err(err) => handle_error(err), + Self { + inner: RawVecInner::with_capacity_in(capacity, alloc, T::LAYOUT), + _marker: PhantomData, } } @@ -165,7 +208,10 @@ impl<T, A: Allocator> RawVec<T, A> { /// allocator for the returned `RawVec`. #[inline] pub fn try_with_capacity_in(capacity: usize, alloc: A) -> Result<Self, TryReserveError> { - Self::try_allocate_in(capacity, AllocInit::Uninitialized, alloc) + match RawVecInner::try_with_capacity_in(capacity, alloc, T::LAYOUT) { + Ok(inner) => Ok(Self { inner, _marker: PhantomData }), + Err(e) => Err(e), + } } /// Like `with_capacity_zeroed`, but parameterized over the choice @@ -173,9 +219,9 @@ impl<T, A: Allocator> RawVec<T, A> { #[cfg(not(no_global_oom_handling))] #[inline] pub fn with_capacity_zeroed_in(capacity: usize, alloc: A) -> Self { - match Self::try_allocate_in(capacity, AllocInit::Zeroed, alloc) { - Ok(res) => res, - Err(err) => handle_error(err), + Self { + inner: RawVecInner::with_capacity_zeroed_in(capacity, alloc, T::LAYOUT), + _marker: PhantomData, } } @@ -201,45 +247,7 @@ impl<T, A: Allocator> RawVec<T, A> { let me = ManuallyDrop::new(self); unsafe { let slice = ptr::slice_from_raw_parts_mut(me.ptr() as *mut MaybeUninit<T>, len); - Box::from_raw_in(slice, ptr::read(&me.alloc)) - } - } - - fn try_allocate_in( - capacity: usize, - init: AllocInit, - alloc: A, - ) -> Result<Self, TryReserveError> { - // Don't allocate here because `Drop` will not deallocate when `capacity` is 0. - - if T::IS_ZST || capacity == 0 { - Ok(Self::new_in(alloc)) - } else { - // We avoid `unwrap_or_else` here because it bloats the amount of - // LLVM IR generated. - let layout = match Layout::array::<T>(capacity) { - Ok(layout) => layout, - Err(_) => return Err(CapacityOverflow.into()), - }; - - if let Err(err) = alloc_guard(layout.size()) { - return Err(err); - } - - let result = match init { - AllocInit::Uninitialized => alloc.allocate(layout), - #[cfg(not(no_global_oom_handling))] - AllocInit::Zeroed => alloc.allocate_zeroed(layout), - }; - let ptr = match result { - Ok(ptr) => ptr, - Err(_) => return Err(AllocError { layout, non_exhaustive: () }.into()), - }; - - // Allocators currently return a `NonNull<[u8]>` whose length - // matches the size requested. If that ever changes, the capacity - // here should change to `ptr.len() / mem::size_of::<T>()`. - Ok(Self { ptr: Unique::from(ptr.cast()), cap: unsafe { Cap(capacity) }, alloc }) + Box::from_raw_in(slice, ptr::read(&me.inner.alloc)) } } @@ -255,8 +263,15 @@ impl<T, A: Allocator> RawVec<T, A> { /// guaranteed. #[inline] pub unsafe fn from_raw_parts_in(ptr: *mut T, capacity: usize, alloc: A) -> Self { - let cap = if T::IS_ZST { Cap::ZERO } else { unsafe { Cap(capacity) } }; - Self { ptr: unsafe { Unique::new_unchecked(ptr) }, cap, alloc } + // SAFETY: Precondition passed to the caller + unsafe { + let ptr = ptr.cast(); + let capacity = Cap::new::<T>(capacity); + Self { + inner: RawVecInner::from_raw_parts_in(ptr, capacity, alloc), + _marker: PhantomData, + } + } } /// A convenience method for hoisting the non-null precondition out of [`RawVec::from_raw_parts_in`]. @@ -265,9 +280,13 @@ impl<T, A: Allocator> RawVec<T, A> { /// /// See [`RawVec::from_raw_parts_in`]. #[inline] - pub(crate) unsafe fn from_nonnull_in(ptr: NonNull<T>, capacity: usize, alloc: A) -> Self { - let cap = if T::IS_ZST { Cap::ZERO } else { unsafe { Cap(capacity) } }; - Self { ptr: Unique::from(ptr), cap, alloc } + pub unsafe fn from_nonnull_in(ptr: NonNull<T>, capacity: usize, alloc: A) -> Self { + // SAFETY: Precondition passed to the caller + unsafe { + let ptr = ptr.cast(); + let capacity = Cap::new::<T>(capacity); + Self { inner: RawVecInner::from_nonnull_in(ptr, capacity, alloc), _marker: PhantomData } + } } /// Gets a raw pointer to the start of the allocation. Note that this is @@ -275,43 +294,26 @@ impl<T, A: Allocator> RawVec<T, A> { /// be careful. #[inline] pub fn ptr(&self) -> *mut T { - self.ptr.as_ptr() + self.inner.ptr() } #[inline] pub fn non_null(&self) -> NonNull<T> { - NonNull::from(self.ptr) + self.inner.non_null() } /// Gets the capacity of the allocation. /// /// This will always be `usize::MAX` if `T` is zero-sized. - #[inline(always)] + #[inline] pub fn capacity(&self) -> usize { - if T::IS_ZST { usize::MAX } else { self.cap.0 } + self.inner.capacity(size_of::<T>()) } /// Returns a shared reference to the allocator backing this `RawVec`. + #[inline] pub fn allocator(&self) -> &A { - &self.alloc - } - - fn current_memory(&self) -> Option<(NonNull<u8>, Layout)> { - if T::IS_ZST || self.cap.0 == 0 { - None - } else { - // We could use Layout::array here which ensures the absence of isize and usize overflows - // and could hypothetically handle differences between stride and size, but this memory - // has already been allocated so we know it can't overflow and currently Rust does not - // support such types. So we can do better by skipping some checks and avoid an unwrap. - const { assert!(mem::size_of::<T>() % mem::align_of::<T>() == 0) }; - unsafe { - let align = mem::align_of::<T>(); - let size = mem::size_of::<T>().unchecked_mul(self.cap.0); - let layout = Layout::from_size_align_unchecked(size, align); - Some((self.ptr.cast().into(), layout)) - } - } + self.inner.allocator() } /// Ensures that the buffer contains at least enough space to hold `len + @@ -336,24 +338,7 @@ impl<T, A: Allocator> RawVec<T, A> { #[cfg(not(no_global_oom_handling))] #[inline] pub fn reserve(&mut self, len: usize, additional: usize) { - // Callers expect this function to be very cheap when there is already sufficient capacity. - // Therefore, we move all the resizing and error-handling logic from grow_amortized and - // handle_reserve behind a call, while making sure that this function is likely to be - // inlined as just a comparison and a call if the comparison fails. - #[cold] - fn do_reserve_and_handle<T, A: Allocator>( - slf: &mut RawVec<T, A>, - len: usize, - additional: usize, - ) { - if let Err(err) = slf.grow_amortized(len, additional) { - handle_error(err); - } - } - - if self.needs_to_grow(len, additional) { - do_reserve_and_handle(self, len, additional); - } + self.inner.reserve(len, additional, T::LAYOUT) } /// A specialized version of `self.reserve(len, 1)` which requires the @@ -361,21 +346,12 @@ impl<T, A: Allocator> RawVec<T, A> { #[cfg(not(no_global_oom_handling))] #[inline(never)] pub fn grow_one(&mut self) { - if let Err(err) = self.grow_amortized(self.cap.0, 1) { - handle_error(err); - } + self.inner.grow_one(T::LAYOUT) } /// The same as `reserve`, but returns on errors instead of panicking or aborting. pub fn try_reserve(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> { - if self.needs_to_grow(len, additional) { - self.grow_amortized(len, additional)?; - } - unsafe { - // Inform the optimizer that the reservation has succeeded or wasn't needed - hint::assert_unchecked(!self.needs_to_grow(len, additional)); - } - Ok(()) + self.inner.try_reserve(len, additional, T::LAYOUT) } /// Ensures that the buffer contains at least enough space to hold `len + @@ -397,9 +373,7 @@ impl<T, A: Allocator> RawVec<T, A> { /// Aborts on OOM. #[cfg(not(no_global_oom_handling))] pub fn reserve_exact(&mut self, len: usize, additional: usize) { - if let Err(err) = self.try_reserve_exact(len, additional) { - handle_error(err); - } + self.inner.reserve_exact(len, additional, T::LAYOUT) } /// The same as `reserve_exact`, but returns on errors instead of panicking or aborting. @@ -408,14 +382,7 @@ impl<T, A: Allocator> RawVec<T, A> { len: usize, additional: usize, ) -> Result<(), TryReserveError> { - if self.needs_to_grow(len, additional) { - self.grow_exact(len, additional)?; - } - unsafe { - // Inform the optimizer that the reservation has succeeded or wasn't needed - hint::assert_unchecked(!self.needs_to_grow(len, additional)); - } - Ok(()) + self.inner.try_reserve_exact(len, additional, T::LAYOUT) } /// Shrinks the buffer down to the specified capacity. If the given amount @@ -431,22 +398,230 @@ impl<T, A: Allocator> RawVec<T, A> { #[cfg(not(no_global_oom_handling))] #[inline] pub fn shrink_to_fit(&mut self, cap: usize) { - if let Err(err) = self.shrink(cap) { + self.inner.shrink_to_fit(cap, T::LAYOUT) + } +} + +unsafe impl<#[may_dangle] T, A: Allocator> Drop for RawVec<T, A> { + /// Frees the memory owned by the `RawVec` *without* trying to drop its contents. + fn drop(&mut self) { + // SAFETY: We are in a Drop impl, self.inner will not be used again. + unsafe { self.inner.deallocate(T::LAYOUT) } + } +} + +impl<A: Allocator> RawVecInner<A> { + #[inline] + #[rustc_const_stable(feature = "raw_vec_internals_const", since = "1.81")] + const fn new_in(alloc: A, align: usize) -> Self { + let ptr = unsafe { core::mem::transmute(align) }; + // `cap: 0` means "unallocated". zero-sized types are ignored. + Self { ptr, cap: Cap::ZERO, alloc } + } + + #[cfg(not(no_global_oom_handling))] + #[inline] + fn with_capacity_in(capacity: usize, alloc: A, elem_layout: Layout) -> Self { + match Self::try_allocate_in(capacity, AllocInit::Uninitialized, alloc, elem_layout) { + Ok(this) => { + unsafe { + // Make it more obvious that a subsquent Vec::reserve(capacity) will not allocate. + hint::assert_unchecked(!this.needs_to_grow(0, capacity, elem_layout)); + } + this + } + Err(err) => handle_error(err), + } + } + + #[inline] + fn try_with_capacity_in( + capacity: usize, + alloc: A, + elem_layout: Layout, + ) -> Result<Self, TryReserveError> { + Self::try_allocate_in(capacity, AllocInit::Uninitialized, alloc, elem_layout) + } + + #[cfg(not(no_global_oom_handling))] + #[inline] + fn with_capacity_zeroed_in(capacity: usize, alloc: A, elem_layout: Layout) -> Self { + match Self::try_allocate_in(capacity, AllocInit::Zeroed, alloc, elem_layout) { + Ok(res) => res, + Err(err) => handle_error(err), + } + } + + fn try_allocate_in( + capacity: usize, + init: AllocInit, + alloc: A, + elem_layout: Layout, + ) -> Result<Self, TryReserveError> { + // We avoid `unwrap_or_else` here because it bloats the amount of + // LLVM IR generated. + let layout = match layout_array(capacity, elem_layout) { + Ok(layout) => layout, + Err(_) => return Err(CapacityOverflow.into()), + }; + + // Don't allocate here because `Drop` will not deallocate when `capacity` is 0. + if layout.size() == 0 { + return Ok(Self::new_in(alloc, elem_layout.align())); + } + + if let Err(err) = alloc_guard(layout.size()) { + return Err(err); + } + + let result = match init { + AllocInit::Uninitialized => alloc.allocate(layout), + #[cfg(not(no_global_oom_handling))] + AllocInit::Zeroed => alloc.allocate_zeroed(layout), + }; + let ptr = match result { + Ok(ptr) => ptr, + Err(_) => return Err(AllocError { layout, non_exhaustive: () }.into()), + }; + + // Allocators currently return a `NonNull<[u8]>` whose length + // matches the size requested. If that ever changes, the capacity + // here should change to `ptr.len() / mem::size_of::<T>()`. + Ok(Self { ptr: Unique::from(ptr.cast()), cap: unsafe { Cap(capacity) }, alloc }) + } + + #[inline] + unsafe fn from_raw_parts_in(ptr: *mut u8, cap: Cap, alloc: A) -> Self { + Self { ptr: unsafe { Unique::new_unchecked(ptr) }, cap, alloc } + } + + #[inline] + unsafe fn from_nonnull_in(ptr: NonNull<u8>, cap: Cap, alloc: A) -> Self { + Self { ptr: Unique::from(ptr), cap, alloc } + } + + #[inline] + fn ptr<T>(&self) -> *mut T { + self.non_null::<T>().as_ptr() + } + + #[inline] + fn non_null<T>(&self) -> NonNull<T> { + self.ptr.cast().into() + } + + #[inline] + fn capacity(&self, elem_size: usize) -> usize { + if elem_size == 0 { usize::MAX } else { self.cap.0 } + } + + #[inline] + fn allocator(&self) -> &A { + &self.alloc + } + + #[inline] + fn current_memory(&self, elem_layout: Layout) -> Option<(NonNull<u8>, Layout)> { + if elem_layout.size() == 0 || self.cap.0 == 0 { + None + } else { + // We could use Layout::array here which ensures the absence of isize and usize overflows + // and could hypothetically handle differences between stride and size, but this memory + // has already been allocated so we know it can't overflow and currently Rust does not + // support such types. So we can do better by skipping some checks and avoid an unwrap. + unsafe { + let alloc_size = elem_layout.size().unchecked_mul(self.cap.0); + let layout = Layout::from_size_align_unchecked(alloc_size, elem_layout.align()); + Some((self.ptr.into(), layout)) + } + } + } + + #[cfg(not(no_global_oom_handling))] + #[inline] + fn reserve(&mut self, len: usize, additional: usize, elem_layout: Layout) { + // Callers expect this function to be very cheap when there is already sufficient capacity. + // Therefore, we move all the resizing and error-handling logic from grow_amortized and + // handle_reserve behind a call, while making sure that this function is likely to be + // inlined as just a comparison and a call if the comparison fails. + #[cold] + fn do_reserve_and_handle<A: Allocator>( + slf: &mut RawVecInner<A>, + len: usize, + additional: usize, + elem_layout: Layout, + ) { + if let Err(err) = slf.grow_amortized(len, additional, elem_layout) { + handle_error(err); + } + } + + if self.needs_to_grow(len, additional, elem_layout) { + do_reserve_and_handle(self, len, additional, elem_layout); + } + } + + #[cfg(not(no_global_oom_handling))] + #[inline] + fn grow_one(&mut self, elem_layout: Layout) { + if let Err(err) = self.grow_amortized(self.cap.0, 1, elem_layout) { handle_error(err); } } -} -impl<T, A: Allocator> RawVec<T, A> { - /// Returns if the buffer needs to grow to fulfill the needed extra capacity. - /// Mainly used to make inlining reserve-calls possible without inlining `grow`. - fn needs_to_grow(&self, len: usize, additional: usize) -> bool { - additional > self.capacity().wrapping_sub(len) + fn try_reserve( + &mut self, + len: usize, + additional: usize, + elem_layout: Layout, + ) -> Result<(), TryReserveError> { + if self.needs_to_grow(len, additional, elem_layout) { + self.grow_amortized(len, additional, elem_layout)?; + } + unsafe { + // Inform the optimizer that the reservation has succeeded or wasn't needed + hint::assert_unchecked(!self.needs_to_grow(len, additional, elem_layout)); + } + Ok(()) } - /// # Safety: - /// - /// `cap` must not exceed `isize::MAX`. + #[cfg(not(no_global_oom_handling))] + fn reserve_exact(&mut self, len: usize, additional: usize, elem_layout: Layout) { + if let Err(err) = self.try_reserve_exact(len, additional, elem_layout) { + handle_error(err); + } + } + + fn try_reserve_exact( + &mut self, + len: usize, + additional: usize, + elem_layout: Layout, + ) -> Result<(), TryReserveError> { + if self.needs_to_grow(len, additional, elem_layout) { + self.grow_exact(len, additional, elem_layout)?; + } + unsafe { + // Inform the optimizer that the reservation has succeeded or wasn't needed + hint::assert_unchecked(!self.needs_to_grow(len, additional, elem_layout)); + } + Ok(()) + } + + #[cfg(not(no_global_oom_handling))] + #[inline] + fn shrink_to_fit(&mut self, cap: usize, elem_layout: Layout) { + if let Err(err) = self.shrink(cap, elem_layout) { + handle_error(err); + } + } + + #[inline] + fn needs_to_grow(&self, len: usize, additional: usize, elem_layout: Layout) -> bool { + additional > self.capacity(elem_layout.size()).wrapping_sub(len) + } + + #[inline] unsafe fn set_ptr_and_cap(&mut self, ptr: NonNull<[u8]>, cap: usize) { // Allocators currently return a `NonNull<[u8]>` whose length matches // the size requested. If that ever changes, the capacity here should @@ -455,18 +630,16 @@ impl<T, A: Allocator> RawVec<T, A> { self.cap = unsafe { Cap(cap) }; } - // This method is usually instantiated many times. So we want it to be as - // small as possible, to improve compile times. But we also want as much of - // its contents to be statically computable as possible, to make the - // generated code run faster. Therefore, this method is carefully written - // so that all of the code that depends on `T` is within it, while as much - // of the code that doesn't depend on `T` as possible is in functions that - // are non-generic over `T`. - fn grow_amortized(&mut self, len: usize, additional: usize) -> Result<(), TryReserveError> { + fn grow_amortized( + &mut self, + len: usize, + additional: usize, + elem_layout: Layout, + ) -> Result<(), TryReserveError> { // This is ensured by the calling contexts. debug_assert!(additional > 0); - if T::IS_ZST { + if elem_layout.size() == 0 { // 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()); @@ -478,33 +651,34 @@ impl<T, A: Allocator> RawVec<T, A> { // This guarantees exponential growth. The doubling cannot overflow // because `cap <= isize::MAX` and the type of `cap` is `usize`. let cap = cmp::max(self.cap.0 * 2, required_cap); - let cap = cmp::max(Self::MIN_NON_ZERO_CAP, cap); + let cap = cmp::max(min_non_zero_cap(elem_layout.size()), cap); + + let new_layout = layout_array(cap, elem_layout)?; - let new_layout = Layout::array::<T>(cap); + let ptr = finish_grow(new_layout, self.current_memory(elem_layout), &mut self.alloc)?; + // SAFETY: finish_grow would have resulted in a capacity overflow if we tried to allocate more than `isize::MAX` items - // `finish_grow` is non-generic over `T`. - let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?; - // SAFETY: finish_grow would have resulted in a capacity overflow if we tried to allocate more than isize::MAX items unsafe { self.set_ptr_and_cap(ptr, cap) }; Ok(()) } - // The constraints on this method are much the same as those on - // `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 T::IS_ZST { + fn grow_exact( + &mut self, + len: usize, + additional: usize, + elem_layout: Layout, + ) -> Result<(), TryReserveError> { + if elem_layout.size() == 0 { // 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()); } let cap = len.checked_add(additional).ok_or(CapacityOverflow)?; - let new_layout = Layout::array::<T>(cap); + let new_layout = layout_array(cap, elem_layout)?; - // `finish_grow` is non-generic over `T`. - let ptr = finish_grow(new_layout, self.current_memory(), &mut self.alloc)?; - // SAFETY: finish_grow would have resulted in a capacity overflow if we tried to allocate more than isize::MAX items + let ptr = finish_grow(new_layout, self.current_memory(elem_layout), &mut self.alloc)?; + // SAFETY: finish_grow would have resulted in a capacity overflow if we tried to allocate more than `isize::MAX` items unsafe { self.set_ptr_and_cap(ptr, cap); } @@ -513,10 +687,10 @@ impl<T, A: Allocator> RawVec<T, A> { #[cfg(not(no_global_oom_handling))] #[inline] - fn shrink(&mut self, cap: usize) -> Result<(), TryReserveError> { - assert!(cap <= self.capacity(), "Tried to shrink to a larger capacity"); + fn shrink(&mut self, cap: usize, elem_layout: Layout) -> Result<(), TryReserveError> { + assert!(cap <= self.capacity(elem_layout.size()), "Tried to shrink to a larger capacity"); // SAFETY: Just checked this isn't trying to grow - unsafe { self.shrink_unchecked(cap) } + unsafe { self.shrink_unchecked(cap, elem_layout) } } /// `shrink`, but without the capacity check. @@ -530,23 +704,27 @@ impl<T, A: Allocator> RawVec<T, A> { /// # Safety /// `cap <= self.capacity()` #[cfg(not(no_global_oom_handling))] - unsafe fn shrink_unchecked(&mut self, cap: usize) -> Result<(), TryReserveError> { - let (ptr, layout) = if let Some(mem) = self.current_memory() { mem } else { return Ok(()) }; - // See current_memory() why this assert is here - const { assert!(mem::size_of::<T>() % mem::align_of::<T>() == 0) }; + unsafe fn shrink_unchecked( + &mut self, + cap: usize, + elem_layout: Layout, + ) -> Result<(), TryReserveError> { + let (ptr, layout) = + if let Some(mem) = self.current_memory(elem_layout) { mem } else { return Ok(()) }; // If shrinking to 0, deallocate the buffer. We don't reach this point // for the T::IS_ZST case since current_memory() will have returned // None. if cap == 0 { unsafe { self.alloc.deallocate(ptr, layout) }; - self.ptr = Unique::dangling(); + self.ptr = + unsafe { Unique::new_unchecked(ptr::without_provenance_mut(elem_layout.align())) }; self.cap = Cap::ZERO; } else { let ptr = unsafe { - // `Layout::array` cannot overflow here because it would have + // Layout cannot overflow here because it would have // overflowed earlier when capacity was larger. - let new_size = mem::size_of::<T>().unchecked_mul(cap); + let new_size = elem_layout.size().unchecked_mul(cap); let new_layout = Layout::from_size_align_unchecked(new_size, layout.align()); self.alloc .shrink(ptr, layout, new_layout) @@ -559,24 +737,32 @@ impl<T, A: Allocator> RawVec<T, A> { } Ok(()) } + + /// # Safety + /// + /// This function deallocates the owned allocation, but does not update `ptr` or `cap` to + /// prevent double-free or use-after-free. Essentially, do not do anything with the caller + /// after this function returns. + /// Ideally this function would take `self` by move, but it cannot because it exists to be + /// called from a `Drop` impl. + unsafe fn deallocate(&mut self, elem_layout: Layout) { + if let Some((ptr, layout)) = self.current_memory(elem_layout) { + unsafe { + self.alloc.deallocate(ptr, layout); + } + } + } } -// This function is outside `RawVec` to minimize compile times. See the comment -// above `RawVec::grow_amortized` for details. (The `A` parameter isn't -// significant, because the number of different `A` types seen in practice is -// much smaller than the number of `T` types.) #[inline(never)] fn finish_grow<A>( - new_layout: Result<Layout, LayoutError>, + new_layout: Layout, current_memory: Option<(NonNull<u8>, Layout)>, alloc: &mut A, ) -> Result<NonNull<[u8]>, TryReserveError> where A: Allocator, { - // Check for the error here to minimize the size of `RawVec::grow_*`. - let new_layout = new_layout.map_err(|_| CapacityOverflow)?; - alloc_guard(new_layout.size())?; let memory = if let Some((ptr, old_layout)) = current_memory { @@ -593,15 +779,6 @@ where memory.map_err(|_| AllocError { layout: new_layout, non_exhaustive: () }.into()) } -unsafe impl<#[may_dangle] T, A: Allocator> Drop for RawVec<T, A> { - /// Frees the memory owned by the `RawVec` *without* trying to drop its contents. - fn drop(&mut self) { - if let Some((ptr, layout)) = self.current_memory() { - unsafe { self.alloc.deallocate(ptr, layout) } - } - } -} - // Central function for reserve error handling. #[cfg(not(no_global_oom_handling))] #[cold] @@ -628,3 +805,8 @@ fn alloc_guard(alloc_size: usize) -> Result<(), TryReserveError> { Ok(()) } } + +#[inline] +fn layout_array(cap: usize, elem_layout: Layout) -> Result<Layout, TryReserveError> { + elem_layout.repeat(cap).map(|(layout, _pad)| layout).map_err(|_| CapacityOverflow.into()) +} diff --git a/library/alloc/src/raw_vec/tests.rs b/library/alloc/src/raw_vec/tests.rs index 4194be53061..d78ded104fb 100644 --- a/library/alloc/src/raw_vec/tests.rs +++ b/library/alloc/src/raw_vec/tests.rs @@ -1,7 +1,8 @@ -use super::*; use core::mem::size_of; use std::cell::Cell; +use super::*; + #[test] fn allocator_param() { use crate::alloc::AllocError; @@ -42,9 +43,9 @@ fn allocator_param() { let a = BoundedAlloc { fuel: Cell::new(500) }; let mut v: RawVec<u8, _> = RawVec::with_capacity_in(50, a); - assert_eq!(v.alloc.fuel.get(), 450); + assert_eq!(v.inner.alloc.fuel.get(), 450); v.reserve(50, 150); // (causes a realloc, thus using 50 + 150 = 200 units of fuel) - assert_eq!(v.alloc.fuel.get(), 250); + assert_eq!(v.inner.alloc.fuel.get(), 250); } #[test] @@ -85,7 +86,7 @@ struct ZST; fn zst_sanity<T>(v: &RawVec<T>) { assert_eq!(v.capacity(), usize::MAX); assert_eq!(v.ptr(), core::ptr::Unique::<T>::dangling().as_ptr()); - assert_eq!(v.current_memory(), None); + assert_eq!(v.inner.current_memory(T::LAYOUT), None); } #[test] @@ -105,22 +106,11 @@ fn zst() { let v: RawVec<ZST> = RawVec::with_capacity_in(100, Global); zst_sanity(&v); - let v: RawVec<ZST> = RawVec::try_allocate_in(0, AllocInit::Uninitialized, Global).unwrap(); - zst_sanity(&v); - - let v: RawVec<ZST> = RawVec::try_allocate_in(100, AllocInit::Uninitialized, Global).unwrap(); - zst_sanity(&v); - - let mut v: RawVec<ZST> = - RawVec::try_allocate_in(usize::MAX, AllocInit::Uninitialized, Global).unwrap(); + let mut v: RawVec<ZST> = RawVec::with_capacity_in(usize::MAX, Global); zst_sanity(&v); // Check all these operations work as expected with zero-sized elements. - assert!(!v.needs_to_grow(100, usize::MAX - 100)); - assert!(v.needs_to_grow(101, usize::MAX - 100)); - zst_sanity(&v); - v.reserve(100, usize::MAX - 100); //v.reserve(101, usize::MAX - 100); // panics, in `zst_reserve_panic` below zst_sanity(&v); @@ -137,12 +127,12 @@ fn zst() { assert_eq!(v.try_reserve_exact(101, usize::MAX - 100), cap_err); zst_sanity(&v); - assert_eq!(v.grow_amortized(100, usize::MAX - 100), cap_err); - assert_eq!(v.grow_amortized(101, usize::MAX - 100), cap_err); + assert_eq!(v.inner.grow_amortized(100, usize::MAX - 100, ZST::LAYOUT), cap_err); + assert_eq!(v.inner.grow_amortized(101, usize::MAX - 100, ZST::LAYOUT), cap_err); zst_sanity(&v); - assert_eq!(v.grow_exact(100, usize::MAX - 100), cap_err); - assert_eq!(v.grow_exact(101, usize::MAX - 100), cap_err); + assert_eq!(v.inner.grow_exact(100, usize::MAX - 100, ZST::LAYOUT), cap_err); + assert_eq!(v.inner.grow_exact(101, usize::MAX - 100, ZST::LAYOUT), cap_err); zst_sanity(&v); } diff --git a/library/alloc/src/rc.rs b/library/alloc/src/rc.rs index bfe3ea20800..bdee06154fa 100644 --- a/library/alloc/src/rc.rs +++ b/library/alloc/src/rc.rs @@ -241,20 +241,12 @@ #![stable(feature = "rust1", since = "1.0.0")] -#[cfg(not(test))] -use crate::boxed::Box; -#[cfg(test)] -use std::boxed::Box; - use core::any::Any; -use core::borrow; use core::cell::Cell; #[cfg(not(no_global_oom_handling))] use core::clone::CloneToUninit; use core::cmp::Ordering; -use core::fmt; use core::hash::{Hash, Hasher}; -use core::hint; use core::intrinsics::abort; #[cfg(not(no_global_oom_handling))] use core::iter; @@ -264,14 +256,20 @@ use core::ops::{CoerceUnsized, Deref, DerefMut, DerefPure, DispatchFromDyn, Rece use core::panic::{RefUnwindSafe, UnwindSafe}; #[cfg(not(no_global_oom_handling))] use core::pin::Pin; +use core::pin::PinCoerceUnsized; use core::ptr::{self, drop_in_place, NonNull}; #[cfg(not(no_global_oom_handling))] use core::slice::from_raw_parts_mut; +use core::{borrow, fmt, hint}; +#[cfg(test)] +use std::boxed::Box; #[cfg(not(no_global_oom_handling))] use crate::alloc::handle_alloc_error; use crate::alloc::{AllocError, Allocator, Global, Layout}; use crate::borrow::{Cow, ToOwned}; +#[cfg(not(test))] +use crate::boxed::Box; #[cfg(not(no_global_oom_handling))] use crate::string::String; #[cfg(not(no_global_oom_handling))] @@ -439,7 +437,7 @@ impl<T> Rc<T> { /// } /// /// impl Gadget { - /// /// Construct a reference counted Gadget. + /// /// Constructs a reference counted Gadget. /// fn new() -> Rc<Self> { /// // `me` is a `Weak<Gadget>` pointing at the new allocation of the /// // `Rc` we're constructing. @@ -449,7 +447,7 @@ impl<T> Rc<T> { /// }) /// } /// - /// /// Return a reference counted pointer to Self. + /// /// Returns a reference counted pointer to Self. /// fn me(&self) -> Rc<Self> { /// self.me.upgrade().unwrap() /// } @@ -1375,6 +1373,7 @@ impl<T: ?Sized, A: Allocator> Rc<T, A> { /// let x = unsafe { Rc::from_raw_in(ptr, alloc) }; /// assert_eq!(&*x, "hello"); /// ``` + #[must_use = "losing the pointer will leak memory"] #[unstable(feature = "allocator_api", issue = "32838")] pub fn into_raw_with_allocator(this: Self) -> (*const T, A) { let this = mem::ManuallyDrop::new(this); @@ -1900,7 +1899,7 @@ impl<T: Clone, A: Allocator> Rc<T, A> { } impl<A: Allocator> Rc<dyn Any, A> { - /// Attempt to downcast the `Rc<dyn Any>` to a concrete type. + /// Attempts to downcast the `Rc<dyn Any>` to a concrete type. /// /// # Examples /// @@ -2179,6 +2178,12 @@ impl<T: ?Sized, A: Allocator> Deref for Rc<T, A> { } } +#[unstable(feature = "pin_coerce_unsized_trait", issue = "123430")] +unsafe impl<T: ?Sized, A: Allocator> PinCoerceUnsized for Rc<T, A> {} + +#[unstable(feature = "pin_coerce_unsized_trait", issue = "123430")] +unsafe impl<T: ?Sized, A: Allocator> PinCoerceUnsized for Weak<T, A> {} + #[unstable(feature = "deref_pure_trait", issue = "87121")] unsafe impl<T: ?Sized, A: Allocator> DerefPure for Rc<T, A> {} @@ -2586,7 +2591,7 @@ impl<T, const N: usize> From<[T; N]> for Rc<[T]> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "shared_from_slice", since = "1.21.0")] impl<T: Clone> From<&[T]> for Rc<[T]> { - /// Allocate a reference-counted slice and fill it by cloning `v`'s items. + /// Allocates a reference-counted slice and fills it by cloning `v`'s items. /// /// # Example /// @@ -2605,7 +2610,7 @@ impl<T: Clone> From<&[T]> for Rc<[T]> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "shared_from_slice", since = "1.21.0")] impl From<&str> for Rc<str> { - /// Allocate a reference-counted string slice and copy `v` into it. + /// Allocates a reference-counted string slice and copies `v` into it. /// /// # Example /// @@ -2624,7 +2629,7 @@ impl From<&str> for Rc<str> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "shared_from_slice", since = "1.21.0")] impl From<String> for Rc<str> { - /// Allocate a reference-counted string slice and copy `v` into it. + /// Allocates a reference-counted string slice and copies `v` into it. /// /// # Example /// @@ -2662,7 +2667,7 @@ impl<T: ?Sized, A: Allocator> From<Box<T, A>> for Rc<T, A> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "shared_from_slice", since = "1.21.0")] impl<T, A: Allocator> From<Vec<T, A>> for Rc<[T], A> { - /// Allocate a reference-counted slice and move `v`'s items into it. + /// Allocates a reference-counted slice and moves `v`'s items into it. /// /// # Example /// @@ -2695,8 +2700,8 @@ where B: ToOwned + ?Sized, Rc<B>: From<&'a B> + From<B::Owned>, { - /// Create a reference-counted pointer from - /// a clone-on-write pointer by copying its content. + /// Creates a reference-counted pointer from a clone-on-write pointer by + /// copying its content. /// /// # Example /// @@ -3110,6 +3115,7 @@ impl<T: ?Sized, A: Allocator> Weak<T, A> { /// /// [`from_raw_in`]: Weak::from_raw_in /// [`as_ptr`]: Weak::as_ptr + #[must_use = "losing the pointer will leak memory"] #[inline] #[unstable(feature = "allocator_api", issue = "32838")] pub fn into_raw_with_allocator(self) -> (*const T, A) { @@ -3526,7 +3532,7 @@ impl<T: ?Sized, A: Allocator> AsRef<T> for Rc<T, A> { #[stable(feature = "pin", since = "1.33.0")] impl<T: ?Sized, A: Allocator> Unpin for Rc<T, A> {} -/// Get the offset within an `RcBox` for the payload behind a pointer. +/// Gets the offset within an `RcBox` for the payload behind a pointer. /// /// # Safety /// @@ -3692,6 +3698,9 @@ impl<T: ?Sized, A: Allocator> Deref for UniqueRc<T, A> { } } +#[unstable(feature = "pin_coerce_unsized_trait", issue = "123430")] +unsafe impl<T: ?Sized> PinCoerceUnsized for UniqueRc<T> {} + #[unstable(feature = "unique_rc_arc", issue = "112566")] impl<T: ?Sized, A: Allocator> DerefMut for UniqueRc<T, A> { fn deref_mut(&mut self) -> &mut T { @@ -3734,7 +3743,7 @@ struct UniqueRcUninit<T: ?Sized, A: Allocator> { #[cfg(not(no_global_oom_handling))] impl<T: ?Sized, A: Allocator> UniqueRcUninit<T, A> { - /// Allocate a RcBox with layout suitable to contain `for_value` or a clone of it. + /// Allocates a RcBox with layout suitable to contain `for_value` or a clone of it. fn new(for_value: &T, alloc: A) -> UniqueRcUninit<T, A> { let layout = Layout::for_value(for_value); let ptr = unsafe { diff --git a/library/alloc/src/rc/tests.rs b/library/alloc/src/rc/tests.rs index 5e2e4beb94a..84e8b325f71 100644 --- a/library/alloc/src/rc/tests.rs +++ b/library/alloc/src/rc/tests.rs @@ -1,8 +1,8 @@ -use super::*; - use std::cell::RefCell; use std::clone::Clone; +use super::*; + #[test] fn test_clone() { let x = Rc::new(RefCell::new(5)); diff --git a/library/alloc/src/slice.rs b/library/alloc/src/slice.rs index c7960b3fb49..9d704870326 100644 --- a/library/alloc/src/slice.rs +++ b/library/alloc/src/slice.rs @@ -78,7 +78,6 @@ pub use core::slice::{SplitInclusive, SplitInclusiveMut}; // N.B., see the `hack` module in this file for more details. #[cfg(test)] pub use hack::into_vec; - // HACK(japaric) needed for the implementation of `Vec::clone` during testing // N.B., see the `hack` module in this file for more details. #[cfg(test)] @@ -179,15 +178,25 @@ impl<T> [T] { /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) /// worst-case. /// - /// If `T: Ord` does not implement a total order the resulting order is unspecified. All - /// original elements will remain in the slice and any possible modifications via interior - /// mutability are observed in the input. Same is true if `T: Ord` panics. + /// If the implementation of [`Ord`] for `T` does not implement a [total order] the resulting + /// order of elements in the slice is unspecified. All original elements will remain in the + /// slice and any possible modifications via interior mutability are observed in the input. Same + /// is true if the implementation of [`Ord`] for `T` panics. /// /// When applicable, unstable sorting is preferred because it is generally faster than stable /// sorting and it doesn't allocate auxiliary memory. See /// [`sort_unstable`](slice::sort_unstable). The exception are partially sorted slices, which /// may be better served with `slice::sort`. /// + /// Sorting types that only implement [`PartialOrd`] such as [`f32`] and [`f64`] require + /// additional precautions. For example, `f32::NAN != f32::NAN`, which doesn't fulfill the + /// reflexivity requirement of [`Ord`]. By using an alternative comparison function with + /// `slice::sort_by` such as [`f32::total_cmp`] or [`f64::total_cmp`] that defines a [total + /// order] users can sort slices containing floating-point values. Alternatively, if all values + /// in the slice are guaranteed to be in a subset for which [`PartialOrd::partial_cmp`] forms a + /// [total order], it's possible to sort the slice with `sort_by(|a, b| + /// a.partial_cmp(b).unwrap())`. + /// /// # Current implementation /// /// The current implementation is based on [driftsort] by Orson Peters and Lukas Bergdoll, which @@ -199,18 +208,21 @@ impl<T> [T] { /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it /// clamps at `self.len() / 2`. /// - /// If `T: Ord` does not implement a total order, the implementation may panic. + /// # Panics + /// + /// May panic if the implementation of [`Ord`] for `T` does not implement a [total order]. /// /// # Examples /// /// ``` - /// let mut v = [-5, 4, 1, -3, 2]; + /// let mut v = [4, -5, 1, -3, 2]; /// /// v.sort(); - /// assert!(v == [-5, -3, 1, 2, 4]); + /// assert_eq!(v, [-5, -3, 1, 2, 4]); /// ``` /// /// [driftsort]: https://github.com/Voultapher/driftsort + /// [total order]: https://en.wikipedia.org/wiki/Total_order #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "rust1", since = "1.0.0")] @@ -222,30 +234,19 @@ impl<T> [T] { stable_sort(self, T::lt); } - /// Sorts the slice with a comparator function, preserving initial order of equal elements. + /// Sorts the slice with a comparison function, preserving initial order of equal elements. /// /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) /// worst-case. /// - /// The comparator function should define a total ordering for the elements in the slice. If the - /// ordering is not total, the order of the elements is unspecified. + /// If the comparison function `compare` does not implement a [total order] the resulting order + /// of elements in the slice is unspecified. All original elements will remain in the slice and + /// any possible modifications via interior mutability are observed in the input. Same is true + /// if `compare` panics. /// - /// If the comparator function does not implement a total order the resulting order is - /// unspecified. All original elements will remain in the slice and any possible modifications - /// via interior mutability are observed in the input. Same is true if the comparator function - /// panics. A total order (for all `a`, `b` and `c`): - /// - /// * total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true, and - /// * transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`. - /// - /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use - /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`. - /// - /// ``` - /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0]; - /// floats.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap()); - /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]); - /// ``` + /// For example `|a, b| (a - b).cmp(a)` is a comparison function that is neither transitive nor + /// reflexive nor total, `a < b < c < a` with `a = 1, b = 2, c = 3`. For more information and + /// examples see the [`Ord`] documentation. /// /// # Current implementation /// @@ -258,21 +259,24 @@ impl<T> [T] { /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it /// clamps at `self.len() / 2`. /// - /// If `T: Ord` does not implement a total order, the implementation may panic. + /// # Panics + /// + /// May panic if `compare` does not implement a [total order]. /// /// # Examples /// /// ``` - /// let mut v = [5, 4, 1, 3, 2]; + /// let mut v = [4, -5, 1, -3, 2]; /// v.sort_by(|a, b| a.cmp(b)); - /// assert!(v == [1, 2, 3, 4, 5]); + /// assert_eq!(v, [-5, -3, 1, 2, 4]); /// /// // reverse sorting /// v.sort_by(|a, b| b.cmp(a)); - /// assert!(v == [5, 4, 3, 2, 1]); + /// assert_eq!(v, [4, 2, 1, -3, -5]); /// ``` /// /// [driftsort]: https://github.com/Voultapher/driftsort + /// [total order]: https://en.wikipedia.org/wiki/Total_order #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "rust1", since = "1.0.0")] @@ -289,9 +293,10 @@ impl<T> [T] { /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* \* log(*n*)) /// worst-case, where the key function is *O*(*m*). /// - /// If `K: Ord` does not implement a total order the resulting order is unspecified. - /// All original elements will remain in the slice and any possible modifications via interior - /// mutability are observed in the input. Same is true if `K: Ord` panics. + /// If the implementation of [`Ord`] for `K` does not implement a [total order] the resulting + /// order of elements in the slice is unspecified. All original elements will remain in the + /// slice and any possible modifications via interior mutability are observed in the input. Same + /// is true if the implementation of [`Ord`] for `K` panics. /// /// # Current implementation /// @@ -304,18 +309,21 @@ impl<T> [T] { /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it /// clamps at `self.len() / 2`. /// - /// If `K: Ord` does not implement a total order, the implementation may panic. + /// # Panics + /// + /// May panic if the implementation of [`Ord`] for `K` does not implement a [total order]. /// /// # Examples /// /// ``` - /// let mut v = [-5i32, 4, 1, -3, 2]; + /// let mut v = [4i32, -5, 1, -3, 2]; /// /// v.sort_by_key(|k| k.abs()); - /// assert!(v == [1, 2, -3, 4, -5]); + /// assert_eq!(v, [1, 2, -3, 4, -5]); /// ``` /// /// [driftsort]: https://github.com/Voultapher/driftsort + /// [total order]: https://en.wikipedia.org/wiki/Total_order #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "slice_sort_by_key", since = "1.7.0")] @@ -337,9 +345,10 @@ impl<T> [T] { /// storage to remember the results of key evaluation. The order of calls to the key function is /// unspecified and may change in future versions of the standard library. /// - /// If `K: Ord` does not implement a total order the resulting order is unspecified. - /// All original elements will remain in the slice and any possible modifications via interior - /// mutability are observed in the input. Same is true if `K: Ord` panics. + /// If the implementation of [`Ord`] for `K` does not implement a [total order] the resulting + /// order of elements in the slice is unspecified. All original elements will remain in the + /// slice and any possible modifications via interior mutability are observed in the input. Same + /// is true if the implementation of [`Ord`] for `K` panics. /// /// For simple key functions (e.g., functions that are property accesses or basic operations), /// [`sort_by_key`](slice::sort_by_key) is likely to be faster. @@ -356,16 +365,22 @@ impl<T> [T] { /// In the worst case, the algorithm allocates temporary storage in a `Vec<(K, usize)>` the /// length of the slice. /// + /// # Panics + /// + /// May panic if the implementation of [`Ord`] for `K` does not implement a [total order]. + /// /// # Examples /// /// ``` - /// let mut v = [-5i32, 4, 32, -3, 2]; + /// let mut v = [4i32, -5, 1, -3, 2, 10]; /// + /// // Strings are sorted by lexicographical order. /// v.sort_by_cached_key(|k| k.to_string()); - /// assert!(v == [-3, -5, 2, 32, 4]); + /// assert_eq!(v, [-3, -5, 1, 10, 2, 4]); /// ``` /// /// [ipnsort]: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort + /// [total order]: https://en.wikipedia.org/wiki/Total_order #[cfg(not(no_global_oom_handling))] #[rustc_allow_incoherent_impl] #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")] diff --git a/library/alloc/src/slice/tests.rs b/library/alloc/src/slice/tests.rs index 0b972a13898..786704caeb0 100644 --- a/library/alloc/src/slice/tests.rs +++ b/library/alloc/src/slice/tests.rs @@ -1,18 +1,21 @@ +use core::cell::Cell; +use core::cmp::Ordering::{self, Equal, Greater, Less}; +use core::convert::identity; +use core::sync::atomic::AtomicUsize; +use core::sync::atomic::Ordering::Relaxed; +use core::{fmt, mem}; +use std::panic; + +use rand::distributions::Standard; +use rand::prelude::*; +use rand::{Rng, RngCore}; + use crate::borrow::ToOwned; use crate::rc::Rc; use crate::string::ToString; use crate::test_helpers::test_rng; use crate::vec::Vec; -use core::cell::Cell; -use core::cmp::Ordering::{self, Equal, Greater, Less}; -use core::convert::identity; -use core::fmt; -use core::mem; -use core::sync::atomic::{AtomicUsize, Ordering::Relaxed}; -use rand::{distributions::Standard, prelude::*, Rng, RngCore}; -use std::panic; - macro_rules! do_test { ($input:ident, $func:ident) => { let len = $input.len(); diff --git a/library/alloc/src/str.rs b/library/alloc/src/str.rs index 94053ef83a0..d7fba3ae159 100644 --- a/library/alloc/src/str.rs +++ b/library/alloc/src/str.rs @@ -9,19 +9,9 @@ use core::borrow::{Borrow, BorrowMut}; use core::iter::FusedIterator; -use core::mem; -use core::ptr; -use core::str::pattern::{DoubleEndedSearcher, Pattern, ReverseSearcher, Searcher}; -use core::unicode::conversions; - -use crate::borrow::ToOwned; -use crate::boxed::Box; -use crate::slice::{Concat, Join, SliceIndex}; -use crate::string::String; -use crate::vec::Vec; - #[stable(feature = "rust1", since = "1.0.0")] pub use core::str::pattern; +use core::str::pattern::{DoubleEndedSearcher, Pattern, ReverseSearcher, Searcher}; #[stable(feature = "encode_utf16", since = "1.8.0")] pub use core::str::EncodeUtf16; #[stable(feature = "split_ascii_whitespace", since = "1.34.0")] @@ -55,6 +45,14 @@ pub use core::str::{RSplitN, SplitN}; pub use core::str::{RSplitTerminator, SplitTerminator}; #[stable(feature = "utf8_chunks", since = "1.79.0")] pub use core::str::{Utf8Chunk, Utf8Chunks}; +use core::unicode::conversions; +use core::{mem, ptr}; + +use crate::borrow::ToOwned; +use crate::boxed::Box; +use crate::slice::{Concat, Join, SliceIndex}; +use crate::string::String; +use crate::vec::Vec; /// 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 0ff66167a46..124230812df 100644 --- a/library/alloc/src/string.rs +++ b/library/alloc/src/string.rs @@ -43,8 +43,6 @@ #![stable(feature = "rust1", since = "1.0.0")] use core::error::Error; -use core::fmt; -use core::hash; #[cfg(not(no_global_oom_handling))] use core::iter::from_fn; use core::iter::FusedIterator; @@ -55,9 +53,8 @@ use core::ops::AddAssign; #[cfg(not(no_global_oom_handling))] use core::ops::Bound::{Excluded, Included, Unbounded}; use core::ops::{self, Range, RangeBounds}; -use core::ptr; -use core::slice; use core::str::pattern::Pattern; +use core::{fmt, hash, ptr, slice}; #[cfg(not(no_global_oom_handling))] use crate::alloc::Allocator; @@ -903,7 +900,7 @@ impl String { /// let rebuilt = unsafe { String::from_raw_parts(ptr, len, cap) }; /// assert_eq!(rebuilt, "hello"); /// ``` - #[must_use = "`self` will be dropped if the result is not used"] + #[must_use = "losing the pointer will leak memory"] #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")] pub fn into_raw_parts(self) -> (*mut u8, usize, usize) { self.vec.into_raw_parts() diff --git a/library/alloc/src/sync.rs b/library/alloc/src/sync.rs index c36b8f6a1ac..2c0d19b0ada 100644 --- a/library/alloc/src/sync.rs +++ b/library/alloc/src/sync.rs @@ -9,13 +9,10 @@ //! `#[cfg(target_has_atomic = "ptr")]`. use core::any::Any; -use core::borrow; #[cfg(not(no_global_oom_handling))] use core::clone::CloneToUninit; use core::cmp::Ordering; -use core::fmt; use core::hash::{Hash, Hasher}; -use core::hint; use core::intrinsics::abort; #[cfg(not(no_global_oom_handling))] use core::iter; @@ -23,12 +20,13 @@ use core::marker::{PhantomData, Unsize}; use core::mem::{self, align_of_val_raw, ManuallyDrop}; use core::ops::{CoerceUnsized, Deref, DerefPure, DispatchFromDyn, Receiver}; use core::panic::{RefUnwindSafe, UnwindSafe}; -use core::pin::Pin; +use core::pin::{Pin, PinCoerceUnsized}; use core::ptr::{self, NonNull}; #[cfg(not(no_global_oom_handling))] use core::slice::from_raw_parts_mut; use core::sync::atomic; use core::sync::atomic::Ordering::{Acquire, Relaxed, Release}; +use core::{borrow, fmt, hint}; #[cfg(not(no_global_oom_handling))] use crate::alloc::handle_alloc_error; @@ -428,7 +426,7 @@ impl<T> Arc<T> { /// } /// /// impl Gadget { - /// /// Construct a reference counted Gadget. + /// /// Constructs a reference counted Gadget. /// fn new() -> Arc<Self> { /// // `me` is a `Weak<Gadget>` pointing at the new allocation of the /// // `Arc` we're constructing. @@ -438,7 +436,7 @@ impl<T> Arc<T> { /// }) /// } /// - /// /// Return a reference counted pointer to Self. + /// /// Returns a reference counted pointer to Self. /// fn me(&self) -> Arc<Self> { /// self.me.upgrade().unwrap() /// } @@ -2144,6 +2142,12 @@ impl<T: ?Sized, A: Allocator> Deref for Arc<T, A> { } } +#[unstable(feature = "pin_coerce_unsized_trait", issue = "123430")] +unsafe impl<T: ?Sized, A: Allocator> PinCoerceUnsized for Arc<T, A> {} + +#[unstable(feature = "pin_coerce_unsized_trait", issue = "123430")] +unsafe impl<T: ?Sized, A: Allocator> PinCoerceUnsized for Weak<T, A> {} + #[unstable(feature = "deref_pure_trait", issue = "87121")] unsafe impl<T: ?Sized, A: Allocator> DerefPure for Arc<T, A> {} @@ -2531,7 +2535,7 @@ unsafe impl<#[may_dangle] T: ?Sized, A: Allocator> Drop for Arc<T, A> { } impl<A: Allocator> Arc<dyn Any + Send + Sync, A> { - /// Attempt to downcast the `Arc<dyn Any + Send + Sync>` to a concrete type. + /// Attempts to downcast the `Arc<dyn Any + Send + Sync>` to a concrete type. /// /// # Examples /// @@ -3545,7 +3549,7 @@ impl<T, const N: usize> From<[T; N]> for Arc<[T]> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "shared_from_slice", since = "1.21.0")] impl<T: Clone> From<&[T]> for Arc<[T]> { - /// Allocate a reference-counted slice and fill it by cloning `v`'s items. + /// Allocates a reference-counted slice and fills it by cloning `v`'s items. /// /// # Example /// @@ -3564,7 +3568,7 @@ impl<T: Clone> From<&[T]> for Arc<[T]> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "shared_from_slice", since = "1.21.0")] impl From<&str> for Arc<str> { - /// Allocate a reference-counted `str` and copy `v` into it. + /// Allocates a reference-counted `str` and copies `v` into it. /// /// # Example /// @@ -3583,7 +3587,7 @@ impl From<&str> for Arc<str> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "shared_from_slice", since = "1.21.0")] impl From<String> for Arc<str> { - /// Allocate a reference-counted `str` and copy `v` into it. + /// Allocates a reference-counted `str` and copies `v` into it. /// /// # Example /// @@ -3621,7 +3625,7 @@ impl<T: ?Sized, A: Allocator> From<Box<T, A>> for Arc<T, A> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "shared_from_slice", since = "1.21.0")] impl<T, A: Allocator + Clone> From<Vec<T, A>> for Arc<[T], A> { - /// Allocate a reference-counted slice and move `v`'s items into it. + /// Allocates a reference-counted slice and moves `v`'s items into it. /// /// # Example /// @@ -3654,8 +3658,8 @@ where B: ToOwned + ?Sized, Arc<B>: From<&'a B> + From<B::Owned>, { - /// Create an atomically reference-counted pointer from - /// a clone-on-write pointer by copying its content. + /// Creates an atomically reference-counted pointer from a clone-on-write + /// pointer by copying its content. /// /// # Example /// @@ -3811,7 +3815,7 @@ impl<T: ?Sized, A: Allocator> AsRef<T> for Arc<T, A> { #[stable(feature = "pin", since = "1.33.0")] impl<T: ?Sized, A: Allocator> Unpin for Arc<T, A> {} -/// Get the offset within an `ArcInner` for the payload behind a pointer. +/// Gets the offset within an `ArcInner` for the payload behind a pointer. /// /// # Safety /// @@ -3833,7 +3837,7 @@ fn data_offset_align(align: usize) -> usize { layout.size() + layout.padding_needed_for(align) } -/// A unique owning pointer to a [`ArcInner`] **that does not imply the contents are initialized,** +/// A unique owning pointer to an [`ArcInner`] **that does not imply the contents are initialized,** /// but will deallocate it (without dropping the value) when dropped. /// /// This is a helper for [`Arc::make_mut()`] to ensure correct cleanup on panic. @@ -3846,7 +3850,7 @@ struct UniqueArcUninit<T: ?Sized, A: Allocator> { #[cfg(not(no_global_oom_handling))] impl<T: ?Sized, A: Allocator> UniqueArcUninit<T, A> { - /// Allocate a ArcInner with layout suitable to contain `for_value` or a clone of it. + /// Allocates an ArcInner with layout suitable to contain `for_value` or a clone of it. fn new(for_value: &T, alloc: A) -> UniqueArcUninit<T, A> { let layout = Layout::for_value(for_value); let ptr = unsafe { diff --git a/library/alloc/src/sync/tests.rs b/library/alloc/src/sync/tests.rs index 1b123aa58f2..d6b3de87577 100644 --- a/library/alloc/src/sync/tests.rs +++ b/library/alloc/src/sync/tests.rs @@ -1,5 +1,3 @@ -use super::*; - use std::clone::Clone; use std::mem::MaybeUninit; use std::option::Option::None; @@ -9,6 +7,8 @@ use std::sync::mpsc::channel; use std::sync::Mutex; use std::thread; +use super::*; + struct Canary(*mut AtomicUsize); impl Drop for Canary { diff --git a/library/alloc/src/task.rs b/library/alloc/src/task.rs index a3fa6585a37..27589aed2f9 100644 --- a/library/alloc/src/task.rs +++ b/library/alloc/src/task.rs @@ -7,14 +7,14 @@ //! This may be detected at compile time using //! `#[cfg(target_has_atomic = "ptr")]`. -use crate::rc::Rc; use core::mem::ManuallyDrop; +#[cfg(target_has_atomic = "ptr")] +use core::task::Waker; use core::task::{LocalWaker, RawWaker, RawWakerVTable}; +use crate::rc::Rc; #[cfg(target_has_atomic = "ptr")] use crate::sync::Arc; -#[cfg(target_has_atomic = "ptr")] -use core::task::Waker; /// The implementation of waking a task on an executor. /// diff --git a/library/alloc/src/testing/crash_test.rs b/library/alloc/src/testing/crash_test.rs index ff72f99b2cb..684bac60d9a 100644 --- a/library/alloc/src/testing/crash_test.rs +++ b/library/alloc/src/testing/crash_test.rs @@ -1,6 +1,8 @@ -use crate::fmt::Debug; // the `Debug` trait is the only thing we use from `crate::fmt` use std::cmp::Ordering; -use std::sync::atomic::{AtomicUsize, Ordering::SeqCst}; +use std::sync::atomic::AtomicUsize; +use std::sync::atomic::Ordering::SeqCst; + +use crate::fmt::Debug; // the `Debug` trait is the only thing we use from `crate::fmt` /// A blueprint for crash test dummy instances that monitor particular events. /// Some instances may be configured to panic at some point. diff --git a/library/alloc/src/tests.rs b/library/alloc/src/tests.rs index ab256ceaec3..b95d11cb07e 100644 --- a/library/alloc/src/tests.rs +++ b/library/alloc/src/tests.rs @@ -2,7 +2,6 @@ use core::any::Any; use core::ops::Deref; - use std::boxed::Box; #[test] diff --git a/library/alloc/src/vec/cow.rs b/library/alloc/src/vec/cow.rs index 3fe83242a30..c18091705a6 100644 --- a/library/alloc/src/vec/cow.rs +++ b/library/alloc/src/vec/cow.rs @@ -1,6 +1,5 @@ -use crate::borrow::Cow; - use super::Vec; +use crate::borrow::Cow; #[stable(feature = "cow_from_vec", since = "1.8.0")] impl<'a, T: Clone> From<&'a [T]> for Cow<'a, [T]> { diff --git a/library/alloc/src/vec/drain.rs b/library/alloc/src/vec/drain.rs index f0b63759ac7..9362cef2a1b 100644 --- a/library/alloc/src/vec/drain.rs +++ b/library/alloc/src/vec/drain.rs @@ -1,4 +1,3 @@ -use crate::alloc::{Allocator, Global}; use core::fmt; use core::iter::{FusedIterator, TrustedLen}; use core::mem::{self, ManuallyDrop, SizedTypeProperties}; @@ -6,6 +5,7 @@ use core::ptr::{self, NonNull}; use core::slice::{self}; use super::Vec; +use crate::alloc::{Allocator, Global}; /// A draining iterator for `Vec<T>`. /// diff --git a/library/alloc/src/vec/extract_if.rs b/library/alloc/src/vec/extract_if.rs index 118cfdb36b9..72d51e89044 100644 --- a/library/alloc/src/vec/extract_if.rs +++ b/library/alloc/src/vec/extract_if.rs @@ -1,8 +1,7 @@ -use crate::alloc::{Allocator, Global}; -use core::ptr; -use core::slice; +use core::{ptr, slice}; use super::Vec; +use crate::alloc::{Allocator, Global}; /// An iterator which uses a closure to determine if an element should be removed. /// diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index 0dc193d82c5..d119e6ca397 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -155,9 +155,7 @@ //! vec.truncate(write_idx); //! ``` -use crate::alloc::{handle_alloc_error, Global}; -use core::alloc::Allocator; -use core::alloc::Layout; +use core::alloc::{Allocator, Layout}; use core::iter::{InPlaceIterable, SourceIter, TrustedRandomAccessNoCoerce}; use core::marker::PhantomData; use core::mem::{self, ManuallyDrop, SizedTypeProperties}; @@ -165,6 +163,7 @@ use core::num::NonZero; use core::ptr; use super::{InPlaceDrop, InPlaceDstDataSrcBufDrop, SpecFromIter, SpecFromIterNested, Vec}; +use crate::alloc::{handle_alloc_error, Global}; const fn in_place_collectible<DEST, SRC>( step_merge: Option<NonZero<usize>>, diff --git a/library/alloc/src/vec/in_place_drop.rs b/library/alloc/src/vec/in_place_drop.rs index 4050c250130..27f75979310 100644 --- a/library/alloc/src/vec/in_place_drop.rs +++ b/library/alloc/src/vec/in_place_drop.rs @@ -1,6 +1,5 @@ use core::marker::PhantomData; -use core::ptr::NonNull; -use core::ptr::{self, drop_in_place}; +use core::ptr::{self, drop_in_place, NonNull}; use core::slice::{self}; use crate::alloc::Global; diff --git a/library/alloc/src/vec/into_iter.rs b/library/alloc/src/vec/into_iter.rs index 10f62e4bb62..fad8abad493 100644 --- a/library/alloc/src/vec/into_iter.rs +++ b/library/alloc/src/vec/into_iter.rs @@ -1,11 +1,3 @@ -#[cfg(not(no_global_oom_handling))] -use super::AsVecIntoIter; -use crate::alloc::{Allocator, Global}; -#[cfg(not(no_global_oom_handling))] -use crate::collections::VecDeque; -use crate::raw_vec::RawVec; -use core::array; -use core::fmt; use core::iter::{ FusedIterator, InPlaceIterable, SourceIter, TrustedFused, TrustedLen, TrustedRandomAccessNoCoerce, @@ -17,6 +9,14 @@ use core::num::NonZero; use core::ops::Deref; use core::ptr::{self, NonNull}; use core::slice::{self}; +use core::{array, fmt}; + +#[cfg(not(no_global_oom_handling))] +use super::AsVecIntoIter; +use crate::alloc::{Allocator, Global}; +#[cfg(not(no_global_oom_handling))] +use crate::collections::VecDeque; +use crate::raw_vec::RawVec; macro non_null { (mut $place:expr, $t:ident) => {{ @@ -114,8 +114,9 @@ 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 method guarantees it won't panic before relinquishing the backing + /// allocation. /// /// This is roughly equivalent to the following, but more efficient /// diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index f63a6dd6749..b4e0bc5fcbe 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -66,15 +66,14 @@ use core::ops::{self, Index, IndexMut, Range, RangeBounds}; use core::ptr::{self, NonNull}; use core::slice::{self, SliceIndex}; +#[unstable(feature = "extract_if", reason = "recently added", issue = "43244")] +pub use self::extract_if::ExtractIf; use crate::alloc::{Allocator, Global}; use crate::borrow::{Cow, ToOwned}; use crate::boxed::Box; use crate::collections::TryReserveError; use crate::raw_vec::RawVec; -#[unstable(feature = "extract_if", reason = "recently added", issue = "43244")] -pub use self::extract_if::ExtractIf; - mod extract_if; #[cfg(not(no_global_oom_handling))] @@ -879,6 +878,7 @@ impl<T, A: Allocator> Vec<T, A> { /// }; /// assert_eq!(rebuilt, [4294967295, 0, 1]); /// ``` + #[must_use = "losing the pointer will leak memory"] #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")] pub fn into_raw_parts(self) -> (*mut T, usize, usize) { let mut me = ManuallyDrop::new(self); @@ -922,6 +922,7 @@ impl<T, A: Allocator> Vec<T, A> { /// }; /// assert_eq!(rebuilt, [4294967295, 0, 1]); /// ``` + #[must_use = "losing the pointer will leak memory"] #[unstable(feature = "allocator_api", issue = "32838")] // #[unstable(feature = "vec_into_raw_parts", reason = "new API", issue = "65816")] pub fn into_raw_parts_with_alloc(self) -> (*mut T, usize, usize, A) { @@ -1711,6 +1712,12 @@ impl<T, A: Allocator> Vec<T, A> { F: FnMut(&mut T) -> bool, { let original_len = self.len(); + + if original_len == 0 { + // Empty case: explicit return allows better optimization, vs letting compiler infer it + return; + } + // Avoid double drop if the drop guard is not executed, // since we may make some holes during the process. unsafe { self.set_len(0) }; @@ -2373,9 +2380,11 @@ impl<T, A: Allocator> Vec<T, A> { } /// Consumes and leaks the `Vec`, returning a mutable reference to the contents, - /// `&'a mut [T]`. Note that the type `T` must outlive the chosen lifetime - /// `'a`. If the type has only static references, or none at all, then this - /// may be chosen to be `'static`. + /// `&'a mut [T]`. + /// + /// Note that the type `T` must outlive the chosen lifetime `'a`. If the type + /// has only static references, or none at all, then this may be chosen to be + /// `'static`. /// /// As of Rust 1.57, this method does not reallocate or shrink the `Vec`, /// so the leaked allocation may include unused capacity that is not part @@ -3359,7 +3368,7 @@ impl<T, A: Allocator> AsMut<[T]> for Vec<T, A> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "rust1", since = "1.0.0")] impl<T: Clone> From<&[T]> for Vec<T> { - /// Allocate a `Vec<T>` and fill it by cloning `s`'s items. + /// Allocates a `Vec<T>` and fills it by cloning `s`'s items. /// /// # Examples /// @@ -3379,7 +3388,7 @@ impl<T: Clone> From<&[T]> for Vec<T> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "vec_from_mut", since = "1.19.0")] impl<T: Clone> From<&mut [T]> for Vec<T> { - /// Allocate a `Vec<T>` and fill it by cloning `s`'s items. + /// Allocates a `Vec<T>` and fills it by cloning `s`'s items. /// /// # Examples /// @@ -3399,7 +3408,7 @@ impl<T: Clone> From<&mut [T]> for Vec<T> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "vec_from_array_ref", since = "1.74.0")] impl<T: Clone, const N: usize> From<&[T; N]> for Vec<T> { - /// Allocate a `Vec<T>` and fill it by cloning `s`'s items. + /// Allocates a `Vec<T>` and fills it by cloning `s`'s items. /// /// # Examples /// @@ -3414,7 +3423,7 @@ impl<T: Clone, const N: usize> From<&[T; N]> for Vec<T> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "vec_from_array_ref", since = "1.74.0")] impl<T: Clone, const N: usize> From<&mut [T; N]> for Vec<T> { - /// Allocate a `Vec<T>` and fill it by cloning `s`'s items. + /// Allocates a `Vec<T>` and fills it by cloning `s`'s items. /// /// # Examples /// @@ -3429,7 +3438,7 @@ impl<T: Clone, const N: usize> From<&mut [T; N]> for Vec<T> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "vec_from_array", since = "1.44.0")] impl<T, const N: usize> From<[T; N]> for Vec<T> { - /// Allocate a `Vec<T>` and move `s`'s items into it. + /// Allocates a `Vec<T>` and moves `s`'s items into it. /// /// # Examples /// @@ -3452,7 +3461,7 @@ impl<'a, T> From<Cow<'a, [T]>> for Vec<T> where [T]: ToOwned<Owned = Vec<T>>, { - /// Convert a clone-on-write slice into a vector. + /// Converts a clone-on-write slice into a vector. /// /// If `s` already owns a `Vec<T>`, it will be returned directly. /// If `s` is borrowing a slice, a new `Vec<T>` will be allocated and @@ -3475,7 +3484,7 @@ where #[cfg(not(test))] #[stable(feature = "vec_from_box", since = "1.18.0")] impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> { - /// Convert a boxed slice into a vector by transferring ownership of + /// Converts a boxed slice into a vector by transferring ownership of /// the existing heap allocation. /// /// # Examples @@ -3494,7 +3503,7 @@ impl<T, A: Allocator> From<Box<[T], A>> for Vec<T, A> { #[cfg(not(test))] #[stable(feature = "box_from_vec", since = "1.20.0")] impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> { - /// Convert a vector into a boxed slice. + /// Converts a vector into a boxed slice. /// /// Before doing the conversion, this method discards excess capacity like [`Vec::shrink_to_fit`]. /// @@ -3522,7 +3531,7 @@ impl<T, A: Allocator> From<Vec<T, A>> for Box<[T], A> { #[cfg(not(no_global_oom_handling))] #[stable(feature = "rust1", since = "1.0.0")] impl From<&str> for Vec<u8> { - /// Allocate a `Vec<u8>` and fill it with a UTF-8 string. + /// Allocates a `Vec<u8>` and fills it with a UTF-8 string. /// /// # Examples /// diff --git a/library/alloc/src/vec/partial_eq.rs b/library/alloc/src/vec/partial_eq.rs index b0cf72577a1..5e620c4b2ef 100644 --- a/library/alloc/src/vec/partial_eq.rs +++ b/library/alloc/src/vec/partial_eq.rs @@ -1,9 +1,8 @@ +use super::Vec; use crate::alloc::Allocator; #[cfg(not(no_global_oom_handling))] use crate::borrow::Cow; -use super::Vec; - macro_rules! __impl_slice_eq1 { ([$($vars:tt)*] $lhs:ty, $rhs:ty $(where $ty:ty: $bound:ident)?, #[$stability:meta]) => { #[$stability] diff --git a/library/alloc/src/vec/spec_extend.rs b/library/alloc/src/vec/spec_extend.rs index e2f865d0f71..7085bceef5b 100644 --- a/library/alloc/src/vec/spec_extend.rs +++ b/library/alloc/src/vec/spec_extend.rs @@ -1,8 +1,8 @@ -use crate::alloc::Allocator; use core::iter::TrustedLen; use core::slice::{self}; use super::{IntoIter, Vec}; +use crate::alloc::Allocator; // Specialization trait used for Vec::extend pub(super) trait SpecExtend<T, I> { diff --git a/library/alloc/src/vec/spec_from_elem.rs b/library/alloc/src/vec/spec_from_elem.rs index 01a6db14474..96d701e15d4 100644 --- a/library/alloc/src/vec/spec_from_elem.rs +++ b/library/alloc/src/vec/spec_from_elem.rs @@ -1,10 +1,9 @@ use core::ptr; +use super::{IsZero, Vec}; use crate::alloc::Allocator; use crate::raw_vec::RawVec; -use super::{IsZero, Vec}; - // Specialization trait used for Vec::from_elem pub(super) trait SpecFromElem: Sized { fn from_elem<A: Allocator>(elem: Self, n: usize, alloc: A) -> Vec<Self, A>; diff --git a/library/alloc/src/vec/spec_from_iter_nested.rs b/library/alloc/src/vec/spec_from_iter_nested.rs index f915ebb86e5..77f7761d22f 100644 --- a/library/alloc/src/vec/spec_from_iter_nested.rs +++ b/library/alloc/src/vec/spec_from_iter_nested.rs @@ -1,10 +1,8 @@ -use core::cmp; use core::iter::TrustedLen; -use core::ptr; - -use crate::raw_vec::RawVec; +use core::{cmp, ptr}; use super::{SpecExtend, Vec}; +use crate::raw_vec::RawVec; /// Another specialization trait for Vec::from_iter /// necessary to manually prioritize overlapping specializations diff --git a/library/alloc/src/vec/splice.rs b/library/alloc/src/vec/splice.rs index 852fdcc3f5c..9e36377c148 100644 --- a/library/alloc/src/vec/splice.rs +++ b/library/alloc/src/vec/splice.rs @@ -1,8 +1,8 @@ -use crate::alloc::{Allocator, Global}; use core::ptr::{self}; use core::slice::{self}; use super::{Drain, Vec}; +use crate::alloc::{Allocator, Global}; /// A splicing iterator for `Vec`. /// |