diff options
Diffstat (limited to 'library/alloc/src')
| -rw-r--r-- | library/alloc/src/alloc.rs | 5 | ||||
| -rw-r--r-- | library/alloc/src/boxed.rs | 8 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/map.rs | 5 | ||||
| -rw-r--r-- | library/alloc/src/collections/btree/set.rs | 6 | ||||
| -rw-r--r-- | library/alloc/src/sync.rs | 2 | ||||
| -rw-r--r-- | library/alloc/src/vec/in_place_collect.rs | 168 | ||||
| -rw-r--r-- | library/alloc/src/vec/mod.rs | 7 |
7 files changed, 104 insertions, 97 deletions
diff --git a/library/alloc/src/alloc.rs b/library/alloc/src/alloc.rs index a5d28aa5252..6677534eafc 100644 --- a/library/alloc/src/alloc.rs +++ b/library/alloc/src/alloc.rs @@ -51,7 +51,7 @@ extern "Rust" { #[derive(Copy, Clone, Default, Debug)] #[cfg(not(test))] // the compiler needs to know when a Box uses the global allocator vs a custom one -#[cfg_attr(not(bootstrap), lang = "global_alloc_ty")] +#[lang = "global_alloc_ty"] pub struct Global; #[cfg(test)] @@ -387,8 +387,7 @@ pub const fn handle_alloc_error(layout: Layout) -> ! { } #[cfg(not(feature = "panic_immediate_abort"))] - #[cfg_attr(not(bootstrap), allow(unused_unsafe))] // on bootstrap bump, remove unsafe block - unsafe { + { core::intrinsics::const_eval_select((layout,), ct_error, rt_error) } diff --git a/library/alloc/src/boxed.rs b/library/alloc/src/boxed.rs index f47fe560b07..cfaf533088a 100644 --- a/library/alloc/src/boxed.rs +++ b/library/alloc/src/boxed.rs @@ -2042,18 +2042,16 @@ impl<Args: Tuple, F: AsyncFnOnce<Args> + ?Sized, A: Allocator> AsyncFnOnce<Args> #[unstable(feature = "async_fn_traits", issue = "none")] impl<Args: Tuple, F: AsyncFnMut<Args> + ?Sized, A: Allocator> AsyncFnMut<Args> for Box<F, A> { - type CallMutFuture<'a> = F::CallMutFuture<'a> where Self: 'a; + type CallRefFuture<'a> = F::CallRefFuture<'a> where Self: 'a; - extern "rust-call" fn async_call_mut(&mut self, args: Args) -> Self::CallMutFuture<'_> { + extern "rust-call" fn async_call_mut(&mut self, args: Args) -> Self::CallRefFuture<'_> { F::async_call_mut(self, args) } } #[unstable(feature = "async_fn_traits", issue = "none")] impl<Args: Tuple, F: AsyncFn<Args> + ?Sized, A: Allocator> AsyncFn<Args> for Box<F, A> { - type CallFuture<'a> = F::CallFuture<'a> where Self: 'a; - - extern "rust-call" fn async_call(&self, args: Args) -> Self::CallFuture<'_> { + extern "rust-call" fn async_call(&self, args: Args) -> Self::CallRefFuture<'_> { F::async_call(self, args) } } diff --git a/library/alloc/src/collections/btree/map.rs b/library/alloc/src/collections/btree/map.rs index e99c6220e20..3875f61efaf 100644 --- a/library/alloc/src/collections/btree/map.rs +++ b/library/alloc/src/collections/btree/map.rs @@ -72,7 +72,7 @@ pub(super) const MIN_LEN: usize = node::MIN_LEN_AFTER_SPLIT; /// `BTreeMap` that observed the logic error and not result in undefined behavior. This could /// include panics, incorrect results, aborts, memory leaks, and non-termination. /// -/// Iterators obtained from functions such as [`BTreeMap::iter`], [`BTreeMap::values`], or +/// Iterators obtained from functions such as [`BTreeMap::iter`], [`BTreeMap::into_iter`], [`BTreeMap::values`], or /// [`BTreeMap::keys`] produce their items in order by key, and take worst-case logarithmic and /// amortized constant time per item returned. /// @@ -415,7 +415,7 @@ impl<'a, K: 'a, V: 'a> Default for IterMut<'a, K, V> { } } -/// An owning iterator over the entries of a `BTreeMap`. +/// An owning iterator over the entries of a `BTreeMap`, sorted by key. /// /// This `struct` is created by the [`into_iter`] method on [`BTreeMap`] /// (provided by the [`IntoIterator`] trait). See its documentation for more. @@ -1637,6 +1637,7 @@ impl<K, V, A: Allocator + Clone> IntoIterator for BTreeMap<K, V, A> { type Item = (K, V); type IntoIter = IntoIter<K, V, A>; + /// Gets an owning iterator over the entries of the map, sorted by key. fn into_iter(self) -> IntoIter<K, V, A> { let mut me = ManuallyDrop::new(self); if let Some(root) = me.root.take() { diff --git a/library/alloc/src/collections/btree/set.rs b/library/alloc/src/collections/btree/set.rs index ed91ae1a66e..7508ae468ae 100644 --- a/library/alloc/src/collections/btree/set.rs +++ b/library/alloc/src/collections/btree/set.rs @@ -27,7 +27,7 @@ use crate::alloc::{Allocator, Global}; /// `BTreeSet` that observed the logic error and not result in undefined behavior. This could /// include panics, incorrect results, aborts, memory leaks, and non-termination. /// -/// Iterators returned by [`BTreeSet::iter`] produce their items in order, and take worst-case +/// Iterators returned by [`BTreeSet::iter`] and [`BTreeSet::into_iter`] produce their items in order, and take worst-case /// logarithmic and amortized constant time per item returned. /// /// [`Cell`]: core::cell::Cell @@ -140,7 +140,7 @@ impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { } } -/// An owning iterator over the items of a `BTreeSet`. +/// An owning iterator over the items of a `BTreeSet` in ascending order. /// /// This `struct` is created by the [`into_iter`] method on [`BTreeSet`] /// (provided by the [`IntoIterator`] trait). See its documentation for more. @@ -1237,7 +1237,7 @@ impl<T, A: Allocator + Clone> IntoIterator for BTreeSet<T, A> { type Item = T; type IntoIter = IntoIter<T, A>; - /// Gets an iterator for moving out the `BTreeSet`'s contents. + /// Gets an iterator for moving out the `BTreeSet`'s contents in ascending order. /// /// # Examples /// diff --git a/library/alloc/src/sync.rs b/library/alloc/src/sync.rs index 80f0f2acc99..7e3e2fb38b1 100644 --- a/library/alloc/src/sync.rs +++ b/library/alloc/src/sync.rs @@ -233,7 +233,7 @@ macro_rules! acquire { /// let val = Arc::clone(&val); /// /// thread::spawn(move || { -/// let v = val.fetch_add(1, Ordering::SeqCst); +/// let v = val.fetch_add(1, Ordering::Relaxed); /// println!("{v:?}"); /// }); /// } diff --git a/library/alloc/src/vec/in_place_collect.rs b/library/alloc/src/vec/in_place_collect.rs index 07eb91c9005..4907a45e881 100644 --- a/library/alloc/src/vec/in_place_collect.rs +++ b/library/alloc/src/vec/in_place_collect.rs @@ -229,96 +229,106 @@ where I: Iterator<Item = T> + InPlaceCollect, <I as SourceIter>::Source: AsVecIntoIter, { - default fn from_iter(mut iterator: I) -> Self { - // See "Layout constraints" section in the module documentation. We rely on const - // optimization here since these conditions currently cannot be expressed as trait bounds - if const { !in_place_collectible::<T, I::Src>(I::MERGE_BY, I::EXPAND_BY) } { - // fallback to more generic implementations - return SpecFromIterNested::from_iter(iterator); - } - - let (src_buf, src_ptr, src_cap, mut dst_buf, dst_end, dst_cap) = unsafe { - let inner = iterator.as_inner().as_into_iter(); - ( - inner.buf.as_ptr(), - inner.ptr, - inner.cap, - inner.buf.as_ptr() as *mut T, - inner.end as *const T, - inner.cap * mem::size_of::<I::Src>() / mem::size_of::<T>(), - ) + default fn from_iter(iterator: I) -> Self { + // Select the implementation in const eval to avoid codegen of the dead branch to improve compile times. + let fun: fn(I) -> Vec<T> = const { + // See "Layout constraints" section in the module documentation. We use const conditions here + // since these conditions currently cannot be expressed as trait bounds + if in_place_collectible::<T, I::Src>(I::MERGE_BY, I::EXPAND_BY) { + from_iter_in_place + } else { + // fallback + SpecFromIterNested::<T, I>::from_iter + } }; - // SAFETY: `dst_buf` and `dst_end` are the start and end of the buffer. - let len = unsafe { SpecInPlaceCollect::collect_in_place(&mut iterator, dst_buf, dst_end) }; + fun(iterator) + } +} - let src = unsafe { iterator.as_inner().as_into_iter() }; - // check if SourceIter contract was upheld - // caveat: if they weren't we might not even make it to this point - debug_assert_eq!(src_buf, src.buf.as_ptr()); - // check InPlaceIterable contract. This is only possible if the iterator advanced the - // source pointer at all. If it uses unchecked access via TrustedRandomAccess - // then the source pointer will stay in its initial position and we can't use it as reference - if src.ptr != src_ptr { - debug_assert!( - unsafe { dst_buf.add(len) as *const _ } <= src.ptr.as_ptr(), - "InPlaceIterable contract violation, write pointer advanced beyond read pointer" - ); - } +fn from_iter_in_place<I, T>(mut iterator: I) -> Vec<T> +where + I: Iterator<Item = T> + InPlaceCollect, + <I as SourceIter>::Source: AsVecIntoIter, +{ + let (src_buf, src_ptr, src_cap, mut dst_buf, dst_end, dst_cap) = unsafe { + let inner = iterator.as_inner().as_into_iter(); + ( + inner.buf.as_ptr(), + inner.ptr, + inner.cap, + inner.buf.as_ptr() as *mut T, + inner.end as *const T, + inner.cap * mem::size_of::<I::Src>() / mem::size_of::<T>(), + ) + }; - // The ownership of the source allocation and the new `T` values is temporarily moved into `dst_guard`. - // This is safe because - // * `forget_allocation_drop_remaining` immediately forgets the allocation - // before any panic can occur in order to avoid any double free, and then proceeds to drop - // any remaining values at the tail of the source. - // * the shrink either panics without invalidating the allocation, aborts or - // succeeds. In the last case we disarm the guard. - // - // Note: This access to the source wouldn't be allowed by the TrustedRandomIteratorNoCoerce - // contract (used by SpecInPlaceCollect below). But see the "O(1) collect" section in the - // module documentation why this is ok anyway. - let dst_guard = - InPlaceDstDataSrcBufDrop { ptr: dst_buf, len, src_cap, src: PhantomData::<I::Src> }; - src.forget_allocation_drop_remaining(); + // SAFETY: `dst_buf` and `dst_end` are the start and end of the buffer. + let len = unsafe { SpecInPlaceCollect::collect_in_place(&mut iterator, dst_buf, dst_end) }; - // Adjust the allocation if the source had a capacity in bytes that wasn't a multiple - // of the destination type size. - // Since the discrepancy should generally be small this should only result in some - // bookkeeping updates and no memmove. - if needs_realloc::<I::Src, T>(src_cap, dst_cap) { - let alloc = Global; - debug_assert_ne!(src_cap, 0); - debug_assert_ne!(dst_cap, 0); - unsafe { - // The old allocation exists, therefore it must have a valid layout. - let src_align = mem::align_of::<I::Src>(); - let src_size = mem::size_of::<I::Src>().unchecked_mul(src_cap); - let old_layout = Layout::from_size_align_unchecked(src_size, src_align); + let src = unsafe { iterator.as_inner().as_into_iter() }; + // check if SourceIter contract was upheld + // caveat: if they weren't we might not even make it to this point + debug_assert_eq!(src_buf, src.buf.as_ptr()); + // check InPlaceIterable contract. This is only possible if the iterator advanced the + // source pointer at all. If it uses unchecked access via TrustedRandomAccess + // then the source pointer will stay in its initial position and we can't use it as reference + if src.ptr != src_ptr { + debug_assert!( + unsafe { dst_buf.add(len) as *const _ } <= src.ptr.as_ptr(), + "InPlaceIterable contract violation, write pointer advanced beyond read pointer" + ); + } - // The allocation must be equal or smaller for in-place iteration to be possible - // therefore the new layout must be ≤ the old one and therefore valid. - let dst_align = mem::align_of::<T>(); - let dst_size = mem::size_of::<T>().unchecked_mul(dst_cap); - let new_layout = Layout::from_size_align_unchecked(dst_size, dst_align); + // The ownership of the source allocation and the new `T` values is temporarily moved into `dst_guard`. + // This is safe because + // * `forget_allocation_drop_remaining` immediately forgets the allocation + // before any panic can occur in order to avoid any double free, and then proceeds to drop + // any remaining values at the tail of the source. + // * the shrink either panics without invalidating the allocation, aborts or + // succeeds. In the last case we disarm the guard. + // + // Note: This access to the source wouldn't be allowed by the TrustedRandomIteratorNoCoerce + // contract (used by SpecInPlaceCollect below). But see the "O(1) collect" section in the + // module documentation why this is ok anyway. + let dst_guard = + InPlaceDstDataSrcBufDrop { ptr: dst_buf, len, src_cap, src: PhantomData::<I::Src> }; + src.forget_allocation_drop_remaining(); - let result = alloc.shrink( - NonNull::new_unchecked(dst_buf as *mut u8), - old_layout, - new_layout, - ); - let Ok(reallocated) = result else { handle_alloc_error(new_layout) }; - dst_buf = reallocated.as_ptr() as *mut T; - } - } else { - debug_assert_eq!(src_cap * mem::size_of::<I::Src>(), dst_cap * mem::size_of::<T>()); + // Adjust the allocation if the source had a capacity in bytes that wasn't a multiple + // of the destination type size. + // Since the discrepancy should generally be small this should only result in some + // bookkeeping updates and no memmove. + if needs_realloc::<I::Src, T>(src_cap, dst_cap) { + let alloc = Global; + debug_assert_ne!(src_cap, 0); + debug_assert_ne!(dst_cap, 0); + unsafe { + // The old allocation exists, therefore it must have a valid layout. + let src_align = mem::align_of::<I::Src>(); + let src_size = mem::size_of::<I::Src>().unchecked_mul(src_cap); + let old_layout = Layout::from_size_align_unchecked(src_size, src_align); + + // The allocation must be equal or smaller for in-place iteration to be possible + // therefore the new layout must be ≤ the old one and therefore valid. + let dst_align = mem::align_of::<T>(); + let dst_size = mem::size_of::<T>().unchecked_mul(dst_cap); + let new_layout = Layout::from_size_align_unchecked(dst_size, dst_align); + + let result = + alloc.shrink(NonNull::new_unchecked(dst_buf as *mut u8), old_layout, new_layout); + let Ok(reallocated) = result else { handle_alloc_error(new_layout) }; + dst_buf = reallocated.as_ptr() as *mut T; } + } else { + debug_assert_eq!(src_cap * mem::size_of::<I::Src>(), dst_cap * mem::size_of::<T>()); + } - mem::forget(dst_guard); + mem::forget(dst_guard); - let vec = unsafe { Vec::from_raw_parts(dst_buf, len, dst_cap) }; + let vec = unsafe { Vec::from_raw_parts(dst_buf, len, dst_cap) }; - vec - } + vec } fn write_in_place_with_drop<T>( diff --git a/library/alloc/src/vec/mod.rs b/library/alloc/src/vec/mod.rs index db56b8d07c7..94bed825bb2 100644 --- a/library/alloc/src/vec/mod.rs +++ b/library/alloc/src/vec/mod.rs @@ -1541,6 +1541,9 @@ impl<T, A: Allocator> Vec<T, A> { } let len = self.len(); + if index > len { + assert_failed(index, len); + } // space for the new element if len == self.buf.capacity() { @@ -1556,10 +1559,6 @@ impl<T, A: Allocator> Vec<T, A> { // Shift everything over to make space. (Duplicating the // `index`th element into two consecutive places.) ptr::copy(p, p.add(1), len - index); - } else if index == len { - // No elements need shifting. - } else { - assert_failed(index, len); } // Write it in, overwriting the first copy of the `index`th // element. |