diff options
Diffstat (limited to 'library')
58 files changed, 818 insertions, 628 deletions
diff --git a/library/alloc/src/raw_vec.rs b/library/alloc/src/raw_vec.rs index 5a10121bbbe..3751f2a2454 100644 --- a/library/alloc/src/raw_vec.rs +++ b/library/alloc/src/raw_vec.rs @@ -241,10 +241,15 @@ impl<T, A: Allocator> RawVec<T, A> { if T::IS_ZST || self.cap == 0 { None } else { - // We have an allocated chunk of memory, so we can bypass runtime - // checks to get our current layout. + // 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. + let _: () = const { assert!(mem::size_of::<T>() % mem::align_of::<T>() == 0) }; unsafe { - let layout = Layout::array::<T>(self.cap).unwrap_unchecked(); + let align = mem::align_of::<T>(); + let size = mem::size_of::<T>().unchecked_mul(self.cap); + let layout = Layout::from_size_align_unchecked(size, align); Some((self.ptr.cast().into(), layout)) } } @@ -426,11 +431,13 @@ impl<T, A: Allocator> RawVec<T, A> { assert!(cap <= self.capacity(), "Tried to shrink to a larger capacity"); let (ptr, layout) = if let Some(mem) = self.current_memory() { mem } else { return Ok(()) }; - + // See current_memory() why this assert is here + let _: () = const { assert!(mem::size_of::<T>() % mem::align_of::<T>() == 0) }; let ptr = unsafe { // `Layout::array` cannot overflow here because it would have // overflowed earlier when capacity was larger. - let new_layout = Layout::array::<T>(cap).unwrap_unchecked(); + let new_size = mem::size_of::<T>().unchecked_mul(cap); + let new_layout = Layout::from_size_align_unchecked(new_size, layout.align()); self.alloc .shrink(ptr, layout, new_layout) .map_err(|_| AllocError { layout: new_layout, non_exhaustive: () })? diff --git a/library/alloc/src/string.rs b/library/alloc/src/string.rs index 75659188515..2b843647dd5 100644 --- a/library/alloc/src/string.rs +++ b/library/alloc/src/string.rs @@ -42,8 +42,6 @@ #![stable(feature = "rust1", since = "1.0.0")] -#[cfg(not(no_global_oom_handling))] -use core::char::{decode_utf16, REPLACEMENT_CHARACTER}; use core::error::Error; use core::fmt; use core::hash; @@ -683,7 +681,7 @@ impl String { // This isn't done via collect::<Result<_, _>>() for performance reasons. // FIXME: the function can be simplified again when #48994 is closed. let mut ret = String::with_capacity(v.len()); - for c in decode_utf16(v.iter().cloned()) { + for c in char::decode_utf16(v.iter().cloned()) { if let Ok(c) = c { ret.push(c); } else { @@ -722,7 +720,9 @@ impl String { #[inline] #[stable(feature = "rust1", since = "1.0.0")] pub fn from_utf16_lossy(v: &[u16]) -> String { - decode_utf16(v.iter().cloned()).map(|r| r.unwrap_or(REPLACEMENT_CHARACTER)).collect() + char::decode_utf16(v.iter().cloned()) + .map(|r| r.unwrap_or(char::REPLACEMENT_CHARACTER)) + .collect() } /// Decomposes a `String` into its raw components. diff --git a/library/core/benches/array.rs b/library/core/benches/array.rs new file mode 100644 index 00000000000..d8cc44d05c4 --- /dev/null +++ b/library/core/benches/array.rs @@ -0,0 +1,19 @@ +use test::black_box; +use test::Bencher; + +macro_rules! map_array { + ($func_name:ident, $start_item: expr, $map_item: expr, $arr_size: expr) => { + #[bench] + fn $func_name(b: &mut Bencher) { + let arr = [$start_item; $arr_size]; + b.iter(|| black_box(arr).map(|_| black_box($map_item))); + } + }; +} + +map_array!(map_8byte_8byte_8, 0u64, 1u64, 80); +map_array!(map_8byte_8byte_64, 0u64, 1u64, 640); +map_array!(map_8byte_8byte_256, 0u64, 1u64, 2560); + +map_array!(map_8byte_256byte_256, 0u64, [0u64; 4], 2560); +map_array!(map_256byte_8byte_256, [0u64; 4], 0u64, 2560); diff --git a/library/core/benches/lib.rs b/library/core/benches/lib.rs index f1244d93285..e4100120d82 100644 --- a/library/core/benches/lib.rs +++ b/library/core/benches/lib.rs @@ -9,6 +9,7 @@ extern crate test; mod any; +mod array; mod ascii; mod char; mod fmt; diff --git a/library/core/src/alloc/global.rs b/library/core/src/alloc/global.rs index 1d80b8bf9ec..18da70451f2 100644 --- a/library/core/src/alloc/global.rs +++ b/library/core/src/alloc/global.rs @@ -203,7 +203,7 @@ pub unsafe trait GlobalAlloc { ptr } - /// Shrink or grow a block of memory to the given `new_size`. + /// Shrink or grow a block of memory to the given `new_size` in bytes. /// The block is described by the given `ptr` pointer and `layout`. /// /// If this returns a non-null pointer, then ownership of the memory block @@ -211,10 +211,11 @@ pub unsafe trait GlobalAlloc { /// Any access to the old `ptr` is Undefined Behavior, even if the /// allocation remained in-place. The newly returned pointer is the only valid pointer /// for accessing this memory now. + /// /// The new memory block is allocated with `layout`, - /// but with the `size` updated to `new_size`. This new layout must be - /// used when deallocating the new memory block with `dealloc`. The range - /// `0..min(layout.size(), new_size)` of the new memory block is + /// but with the `size` updated to `new_size` in bytes. + /// This new layout must be used when deallocating the new memory block with `dealloc`. + /// The range `0..min(layout.size(), new_size)` of the new memory block is /// guaranteed to have the same values as the original block. /// /// If this method returns null, then ownership of the memory diff --git a/library/core/src/array/drain.rs b/library/core/src/array/drain.rs new file mode 100644 index 00000000000..5fadf907b62 --- /dev/null +++ b/library/core/src/array/drain.rs @@ -0,0 +1,76 @@ +use crate::iter::{TrustedLen, UncheckedIterator}; +use crate::mem::ManuallyDrop; +use crate::ptr::drop_in_place; +use crate::slice; + +/// A situationally-optimized version of `array.into_iter().for_each(func)`. +/// +/// [`crate::array::IntoIter`]s are great when you need an owned iterator, but +/// storing the entire array *inside* the iterator like that can sometimes +/// pessimize code. Notable, it can be more bytes than you really want to move +/// around, and because the array accesses index into it SRoA has a harder time +/// optimizing away the type than it does iterators that just hold a couple pointers. +/// +/// Thus this function exists, which gives a way to get *moved* access to the +/// elements of an array using a small iterator -- no bigger than a slice iterator. +/// +/// The function-taking-a-closure structure makes it safe, as it keeps callers +/// from looking at already-dropped elements. +pub(crate) fn drain_array_with<T, R, const N: usize>( + array: [T; N], + func: impl for<'a> FnOnce(Drain<'a, T>) -> R, +) -> R { + let mut array = ManuallyDrop::new(array); + // SAFETY: Now that the local won't drop it, it's ok to construct the `Drain` which will. + let drain = Drain(array.iter_mut()); + func(drain) +} + +/// See [`drain_array_with`] -- this is `pub(crate)` only so it's allowed to be +/// mentioned in the signature of that method. (Otherwise it hits `E0446`.) +// INVARIANT: It's ok to drop the remainder of the inner iterator. +pub(crate) struct Drain<'a, T>(slice::IterMut<'a, T>); + +impl<T> Drop for Drain<'_, T> { + fn drop(&mut self) { + // SAFETY: By the type invariant, we're allowed to drop all these. + unsafe { drop_in_place(self.0.as_mut_slice()) } + } +} + +impl<T> Iterator for Drain<'_, T> { + type Item = T; + + #[inline] + fn next(&mut self) -> Option<T> { + let p: *const T = self.0.next()?; + // SAFETY: The iterator was already advanced, so we won't drop this later. + Some(unsafe { p.read() }) + } + + #[inline] + fn size_hint(&self) -> (usize, Option<usize>) { + let n = self.len(); + (n, Some(n)) + } +} + +impl<T> ExactSizeIterator for Drain<'_, T> { + #[inline] + fn len(&self) -> usize { + self.0.len() + } +} + +// SAFETY: This is a 1:1 wrapper for a slice iterator, which is also `TrustedLen`. +unsafe impl<T> TrustedLen for Drain<'_, T> {} + +impl<T> UncheckedIterator for Drain<'_, T> { + unsafe fn next_unchecked(&mut self) -> T { + // SAFETY: `Drain` is 1:1 with the inner iterator, so if the caller promised + // that there's an element left, the inner iterator has one too. + let p: *const T = unsafe { self.0.next_unchecked() }; + // SAFETY: The iterator was already advanced, so we won't drop this later. + unsafe { p.read() } + } +} diff --git a/library/core/src/array/mod.rs b/library/core/src/array/mod.rs index 5decd7d5a65..1643842d607 100644 --- a/library/core/src/array/mod.rs +++ b/library/core/src/array/mod.rs @@ -10,16 +10,19 @@ use crate::convert::{Infallible, TryFrom}; use crate::error::Error; use crate::fmt; use crate::hash::{self, Hash}; -use crate::iter::TrustedLen; +use crate::iter::UncheckedIterator; use crate::mem::{self, MaybeUninit}; use crate::ops::{ ChangeOutputType, ControlFlow, FromResidual, Index, IndexMut, NeverShortCircuit, Residual, Try, }; use crate::slice::{Iter, IterMut}; +mod drain; mod equality; mod iter; +pub(crate) use drain::drain_array_with; + #[stable(feature = "array_value_iter", since = "1.51.0")] pub use iter::IntoIter; @@ -52,16 +55,11 @@ pub use iter::IntoIter; /// ``` #[inline] #[stable(feature = "array_from_fn", since = "1.63.0")] -pub fn from_fn<T, const N: usize, F>(mut cb: F) -> [T; N] +pub fn from_fn<T, const N: usize, F>(cb: F) -> [T; N] where F: FnMut(usize) -> T, { - let mut idx = 0; - [(); N].map(|_| { - let res = cb(idx); - idx += 1; - res - }) + try_from_fn(NeverShortCircuit::wrap_mut_1(cb)).0 } /// Creates an array `[T; N]` where each fallible array element `T` is returned by the `cb` call. @@ -101,9 +99,14 @@ where R: Try, R::Residual: Residual<[R::Output; N]>, { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { try_collect_into_array_unchecked(&mut (0..N).map(cb)) } + let mut array = MaybeUninit::uninit_array::<N>(); + match try_from_fn_erased(&mut array, cb) { + ControlFlow::Break(r) => FromResidual::from_residual(r), + ControlFlow::Continue(()) => { + // SAFETY: All elements of the array were populated. + try { unsafe { MaybeUninit::array_assume_init(array) } } + } + } } /// Converts a reference to `T` into a reference to an array of length 1 (without copying). @@ -414,9 +417,7 @@ trait SpecArrayClone: Clone { impl<T: Clone> SpecArrayClone for T { #[inline] default fn clone<const N: usize>(array: &[T; N]) -> [T; N] { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut array.iter().cloned()) } + from_trusted_iterator(array.iter().cloned()) } } @@ -500,9 +501,7 @@ impl<T, const N: usize> [T; N] { where F: FnMut(T) -> U, { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut IntoIterator::into_iter(self).map(f)) } + self.try_map(NeverShortCircuit::wrap_mut_1(f)).0 } /// A fallible function `f` applied to each element on array `self` in order to @@ -539,9 +538,7 @@ impl<T, const N: usize> [T; N] { R: Try, R::Residual: Residual<[R::Output; N]>, { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { try_collect_into_array_unchecked(&mut IntoIterator::into_iter(self).map(f)) } + drain_array_with(self, |iter| try_from_trusted_iterator(iter.map(f))) } /// 'Zips up' two arrays into a single array of pairs. @@ -562,11 +559,9 @@ impl<T, const N: usize> [T; N] { /// ``` #[unstable(feature = "array_zip", issue = "80094")] pub fn zip<U>(self, rhs: [U; N]) -> [(T, U); N] { - let mut iter = IntoIterator::into_iter(self).zip(rhs); - - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut iter) } + drain_array_with(self, |lhs| { + drain_array_with(rhs, |rhs| from_trusted_iterator(crate::iter::zip(lhs, rhs))) + }) } /// Returns a slice containing the entire array. Equivalent to `&s[..]`. @@ -613,9 +608,7 @@ impl<T, const N: usize> [T; N] { /// ``` #[unstable(feature = "array_methods", issue = "76118")] pub fn each_ref(&self) -> [&T; N] { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut self.iter()) } + from_trusted_iterator(self.iter()) } /// Borrows each element mutably and returns an array of mutable references @@ -635,9 +628,7 @@ impl<T, const N: usize> [T; N] { /// ``` #[unstable(feature = "array_methods", issue = "76118")] pub fn each_mut(&mut self) -> [&mut T; N] { - // SAFETY: we know for certain that this iterator will yield exactly `N` - // items. - unsafe { collect_into_array_unchecked(&mut self.iter_mut()) } + from_trusted_iterator(self.iter_mut()) } /// Divides one array reference into two at an index. @@ -797,105 +788,71 @@ impl<T, const N: usize> [T; N] { } } -/// Pulls `N` items from `iter` and returns them as an array. If the iterator -/// yields fewer than `N` items, this function exhibits undefined behavior. -/// -/// See [`try_collect_into_array`] for more information. +/// Populate an array from the first `N` elements of `iter` /// +/// # Panics /// -/// # Safety +/// If the iterator doesn't actually have enough items. /// -/// It is up to the caller to guarantee that `iter` yields at least `N` items. -/// Violating this condition causes undefined behavior. -unsafe fn try_collect_into_array_unchecked<I, T, R, const N: usize>(iter: &mut I) -> R::TryType -where - // Note: `TrustedLen` here is somewhat of an experiment. This is just an - // internal function, so feel free to remove if this bound turns out to be a - // bad idea. In that case, remember to also remove the lower bound - // `debug_assert!` below! - I: Iterator + TrustedLen, - I::Item: Try<Output = T, Residual = R>, - R: Residual<[T; N]>, -{ - debug_assert!(N <= iter.size_hint().1.unwrap_or(usize::MAX)); - debug_assert!(N <= iter.size_hint().0); - - // SAFETY: covered by the function contract. - unsafe { try_collect_into_array(iter).unwrap_unchecked() } +/// By depending on `TrustedLen`, however, we can do that check up-front (where +/// it easily optimizes away) so it doesn't impact the loop that fills the array. +#[inline] +fn from_trusted_iterator<T, const N: usize>(iter: impl UncheckedIterator<Item = T>) -> [T; N] { + try_from_trusted_iterator(iter.map(NeverShortCircuit)).0 } -// Infallible version of `try_collect_into_array_unchecked`. -unsafe fn collect_into_array_unchecked<I, const N: usize>(iter: &mut I) -> [I::Item; N] +#[inline] +fn try_from_trusted_iterator<T, R, const N: usize>( + iter: impl UncheckedIterator<Item = R>, +) -> ChangeOutputType<R, [T; N]> where - I: Iterator + TrustedLen, + R: Try<Output = T>, + R::Residual: Residual<[T; N]>, { - let mut map = iter.map(NeverShortCircuit); - - // SAFETY: The same safety considerations w.r.t. the iterator length - // apply for `try_collect_into_array_unchecked` as for - // `collect_into_array_unchecked` - match unsafe { try_collect_into_array_unchecked(&mut map) } { - NeverShortCircuit(array) => array, + assert!(iter.size_hint().0 >= N); + fn next<T>(mut iter: impl UncheckedIterator<Item = T>) -> impl FnMut(usize) -> T { + move |_| { + // SAFETY: We know that `from_fn` will call this at most N times, + // and we checked to ensure that we have at least that many items. + unsafe { iter.next_unchecked() } + } } + + try_from_fn(next(iter)) } -/// Pulls `N` items from `iter` and returns them as an array. If the iterator -/// yields fewer than `N` items, `Err` is returned containing an iterator over -/// the already yielded items. +/// Version of [`try_from_fn`] using a passed-in slice in order to avoid +/// needing to monomorphize for every array length. /// -/// Since the iterator is passed as a mutable reference and this function calls -/// `next` at most `N` times, the iterator can still be used afterwards to -/// retrieve the remaining items. +/// This takes a generator rather than an iterator so that *at the type level* +/// it never needs to worry about running out of items. When combined with +/// an infallible `Try` type, that means the loop canonicalizes easily, allowing +/// it to optimize well. /// -/// If `iter.next()` panicks, all items already yielded by the iterator are -/// dropped. +/// It would be *possible* to unify this and [`iter_next_chunk_erased`] into one +/// function that does the union of both things, but last time it was that way +/// it resulted in poor codegen from the "are there enough source items?" checks +/// not optimizing away. So if you give it a shot, make sure to watch what +/// happens in the codegen tests. #[inline] -fn try_collect_into_array<I, T, R, const N: usize>( - iter: &mut I, -) -> Result<R::TryType, IntoIter<T, N>> +fn try_from_fn_erased<T, R>( + buffer: &mut [MaybeUninit<T>], + mut generator: impl FnMut(usize) -> R, +) -> ControlFlow<R::Residual> where - I: Iterator, - I::Item: Try<Output = T, Residual = R>, - R: Residual<[T; N]>, + R: Try<Output = T>, { - if N == 0 { - // SAFETY: An empty array is always inhabited and has no validity invariants. - return Ok(Try::from_output(unsafe { mem::zeroed() })); - } + let mut guard = Guard { array_mut: buffer, initialized: 0 }; - let mut array = MaybeUninit::uninit_array::<N>(); - let mut guard = Guard { array_mut: &mut array, initialized: 0 }; - - for _ in 0..N { - match iter.next() { - Some(item_rslt) => { - let item = match item_rslt.branch() { - ControlFlow::Break(r) => { - return Ok(FromResidual::from_residual(r)); - } - ControlFlow::Continue(elem) => elem, - }; - - // SAFETY: `guard.initialized` starts at 0, which means push can be called - // at most N times, which this loop does. - unsafe { - guard.push_unchecked(item); - } - } - None => { - let alive = 0..guard.initialized; - mem::forget(guard); - // SAFETY: `array` was initialized with exactly `initialized` - // number of elements. - return Err(unsafe { IntoIter::new_unchecked(array, alive) }); - } - } + while guard.initialized < guard.array_mut.len() { + let item = generator(guard.initialized).branch()?; + + // SAFETY: The loop condition ensures we have space to push the item + unsafe { guard.push_unchecked(item) }; } mem::forget(guard); - // SAFETY: All elements of the array were populated in the loop above. - let output = unsafe { array.transpose().assume_init() }; - Ok(Try::from_output(output)) + ControlFlow::Continue(()) } /// Panic guard for incremental initialization of arrays. @@ -909,14 +866,14 @@ where /// /// To minimize indirection fields are still pub but callers should at least use /// `push_unchecked` to signal that something unsafe is going on. -pub(crate) struct Guard<'a, T, const N: usize> { +struct Guard<'a, T> { /// The array to be initialized. - pub array_mut: &'a mut [MaybeUninit<T>; N], + pub array_mut: &'a mut [MaybeUninit<T>], /// The number of items that have been initialized so far. pub initialized: usize, } -impl<T, const N: usize> Guard<'_, T, N> { +impl<T> Guard<'_, T> { /// Adds an item to the array and updates the initialized item counter. /// /// # Safety @@ -934,28 +891,73 @@ impl<T, const N: usize> Guard<'_, T, N> { } } -impl<T, const N: usize> Drop for Guard<'_, T, N> { +impl<T> Drop for Guard<'_, T> { fn drop(&mut self) { - debug_assert!(self.initialized <= N); + debug_assert!(self.initialized <= self.array_mut.len()); // SAFETY: this slice will contain only initialized objects. unsafe { crate::ptr::drop_in_place(MaybeUninit::slice_assume_init_mut( - &mut self.array_mut.get_unchecked_mut(..self.initialized), + self.array_mut.get_unchecked_mut(..self.initialized), )); } } } -/// Returns the next chunk of `N` items from the iterator or errors with an -/// iterator over the remainder. Used for `Iterator::next_chunk`. +/// Pulls `N` items from `iter` and returns them as an array. If the iterator +/// yields fewer than `N` items, `Err` is returned containing an iterator over +/// the already yielded items. +/// +/// Since the iterator is passed as a mutable reference and this function calls +/// `next` at most `N` times, the iterator can still be used afterwards to +/// retrieve the remaining items. +/// +/// If `iter.next()` panicks, all items already yielded by the iterator are +/// dropped. +/// +/// Used for [`Iterator::next_chunk`]. #[inline] -pub(crate) fn iter_next_chunk<I, const N: usize>( - iter: &mut I, -) -> Result<[I::Item; N], IntoIter<I::Item, N>> -where - I: Iterator, -{ - let mut map = iter.map(NeverShortCircuit); - try_collect_into_array(&mut map).map(|NeverShortCircuit(arr)| arr) +pub(crate) fn iter_next_chunk<T, const N: usize>( + iter: &mut impl Iterator<Item = T>, +) -> Result<[T; N], IntoIter<T, N>> { + let mut array = MaybeUninit::uninit_array::<N>(); + let r = iter_next_chunk_erased(&mut array, iter); + match r { + Ok(()) => { + // SAFETY: All elements of `array` were populated. + Ok(unsafe { MaybeUninit::array_assume_init(array) }) + } + Err(initialized) => { + // SAFETY: Only the first `initialized` elements were populated + Err(unsafe { IntoIter::new_unchecked(array, 0..initialized) }) + } + } +} + +/// Version of [`iter_next_chunk`] using a passed-in slice in order to avoid +/// needing to monomorphize for every array length. +/// +/// Unfortunately this loop has two exit conditions, the buffer filling up +/// or the iterator running out of items, making it tend to optimize poorly. +#[inline] +fn iter_next_chunk_erased<T>( + buffer: &mut [MaybeUninit<T>], + iter: &mut impl Iterator<Item = T>, +) -> Result<(), usize> { + let mut guard = Guard { array_mut: buffer, initialized: 0 }; + while guard.initialized < guard.array_mut.len() { + let Some(item) = iter.next() else { + // Unlike `try_from_fn_erased`, we want to keep the partial results, + // so we need to defuse the guard instead of using `?`. + let initialized = guard.initialized; + mem::forget(guard); + return Err(initialized) + }; + + // SAFETY: The loop condition ensures we have space to push the item + unsafe { guard.push_unchecked(item) }; + } + + mem::forget(guard); + Ok(()) } diff --git a/library/core/src/char/decode.rs b/library/core/src/char/decode.rs index eeb08803040..dbfe251f2bb 100644 --- a/library/core/src/char/decode.rs +++ b/library/core/src/char/decode.rs @@ -3,8 +3,6 @@ use crate::error::Error; use crate::fmt; -use super::from_u32_unchecked; - /// An iterator that decodes UTF-16 encoded code points from an iterator of `u16`s. /// /// This `struct` is created by the [`decode_utf16`] method on [`char`]. See its @@ -49,7 +47,7 @@ impl<I: Iterator<Item = u16>> Iterator for DecodeUtf16<I> { if !u.is_utf16_surrogate() { // SAFETY: not a surrogate - Some(Ok(unsafe { from_u32_unchecked(u as u32) })) + Some(Ok(unsafe { char::from_u32_unchecked(u as u32) })) } else if u >= 0xDC00 { // a trailing surrogate Some(Err(DecodeUtf16Error { code: u })) @@ -69,7 +67,7 @@ impl<I: Iterator<Item = u16>> Iterator for DecodeUtf16<I> { // all ok, so lets decode it. let c = (((u & 0x3ff) as u32) << 10 | (u2 & 0x3ff) as u32) + 0x1_0000; // SAFETY: we checked that it's a legal unicode value - Some(Ok(unsafe { from_u32_unchecked(c) })) + Some(Ok(unsafe { char::from_u32_unchecked(c) })) } } diff --git a/library/core/src/char/methods.rs b/library/core/src/char/methods.rs index 3e7383b4cd1..9bc97ea0bff 100644 --- a/library/core/src/char/methods.rs +++ b/library/core/src/char/methods.rs @@ -53,15 +53,13 @@ impl char { /// Basic usage: /// /// ``` - /// use std::char::decode_utf16; - /// /// // 𝄞mus<invalid>ic<invalid> /// let v = [ /// 0xD834, 0xDD1E, 0x006d, 0x0075, 0x0073, 0xDD1E, 0x0069, 0x0063, 0xD834, /// ]; /// /// assert_eq!( - /// decode_utf16(v) + /// char::decode_utf16(v) /// .map(|r| r.map_err(|e| e.unpaired_surrogate())) /// .collect::<Vec<_>>(), /// vec![ @@ -77,16 +75,14 @@ impl char { /// A lossy decoder can be obtained by replacing `Err` results with the replacement character: /// /// ``` - /// use std::char::{decode_utf16, REPLACEMENT_CHARACTER}; - /// /// // 𝄞mus<invalid>ic<invalid> /// let v = [ /// 0xD834, 0xDD1E, 0x006d, 0x0075, 0x0073, 0xDD1E, 0x0069, 0x0063, 0xD834, /// ]; /// /// assert_eq!( - /// decode_utf16(v) - /// .map(|r| r.unwrap_or(REPLACEMENT_CHARACTER)) + /// char::decode_utf16(v) + /// .map(|r| r.unwrap_or(char::REPLACEMENT_CHARACTER)) /// .collect::<String>(), /// "𝄞mus�ic�" /// ); @@ -123,8 +119,6 @@ impl char { /// Basic usage: /// /// ``` - /// use std::char; - /// /// let c = char::from_u32(0x2764); /// /// assert_eq!(Some('❤'), c); @@ -133,8 +127,6 @@ impl char { /// Returning `None` when the input is not a valid `char`: /// /// ``` - /// use std::char; - /// /// let c = char::from_u32(0x110000); /// /// assert_eq!(None, c); @@ -176,8 +168,6 @@ impl char { /// Basic usage: /// /// ``` - /// use std::char; - /// /// let c = unsafe { char::from_u32_unchecked(0x2764) }; /// /// assert_eq!('❤', c); @@ -210,8 +200,6 @@ impl char { /// Basic usage: /// /// ``` - /// use std::char; - /// /// let c = char::from_digit(4, 10); /// /// assert_eq!(Some('4'), c); @@ -225,8 +213,6 @@ impl char { /// Returning `None` when the input is not a digit: /// /// ``` - /// use std::char; - /// /// let c = char::from_digit(20, 10); /// /// assert_eq!(None, c); @@ -235,8 +221,6 @@ impl char { /// Passing a large radix, causing a panic: /// /// ```should_panic - /// use std::char; - /// /// // this panics /// let _c = char::from_digit(1, 37); /// ``` @@ -1786,7 +1770,7 @@ pub fn encode_utf16_raw(mut code: u32, dst: &mut [u16]) -> &mut [u16] { } else { panic!( "encode_utf16: need {} units to encode U+{:X}, but the buffer has {}", - from_u32_unchecked(code).len_utf16(), + char::from_u32_unchecked(code).len_utf16(), code, dst.len(), ) diff --git a/library/core/src/char/mod.rs b/library/core/src/char/mod.rs index af98059cf42..8ec78e88733 100644 --- a/library/core/src/char/mod.rs +++ b/library/core/src/char/mod.rs @@ -189,7 +189,7 @@ impl Iterator for EscapeUnicode { } EscapeUnicodeState::Value => { let hex_digit = ((self.c as u32) >> (self.hex_digit_idx * 4)) & 0xf; - let c = from_digit(hex_digit, 16).unwrap(); + let c = char::from_digit(hex_digit, 16).unwrap(); if self.hex_digit_idx == 0 { self.state = EscapeUnicodeState::RightBrace; } else { diff --git a/library/core/src/iter/adapters/array_chunks.rs b/library/core/src/iter/adapters/array_chunks.rs index af786609757..13719c727e9 100644 --- a/library/core/src/iter/adapters/array_chunks.rs +++ b/library/core/src/iter/adapters/array_chunks.rs @@ -1,6 +1,5 @@ use crate::array; use crate::iter::{ByRefSized, FusedIterator, Iterator, TrustedRandomAccessNoCoerce}; -use crate::mem::{self, MaybeUninit}; use crate::ops::{ControlFlow, NeverShortCircuit, Try}; /// An iterator over `N` elements of the iterator at a time. @@ -212,19 +211,14 @@ where let mut i = 0; // Use a while loop because (0..len).step_by(N) doesn't optimize well. while inner_len - i >= N { - let mut chunk = MaybeUninit::uninit_array(); - let mut guard = array::Guard { array_mut: &mut chunk, initialized: 0 }; - while guard.initialized < N { + let chunk = crate::array::from_fn(|local| { // SAFETY: The method consumes the iterator and the loop condition ensures that // all accesses are in bounds and only happen once. unsafe { - let idx = i + guard.initialized; - guard.push_unchecked(self.iter.__iterator_get_unchecked(idx)); + let idx = i + local; + self.iter.__iterator_get_unchecked(idx) } - } - mem::forget(guard); - // SAFETY: The loop above initialized all elements - let chunk = unsafe { MaybeUninit::array_assume_init(chunk) }; + }); accum = f(accum, chunk); i += N; } diff --git a/library/core/src/iter/adapters/cloned.rs b/library/core/src/iter/adapters/cloned.rs index aba24a79dcf..914ff86c1a9 100644 --- a/library/core/src/iter/adapters/cloned.rs +++ b/library/core/src/iter/adapters/cloned.rs @@ -1,7 +1,7 @@ use crate::iter::adapters::{ zip::try_get_unchecked, TrustedRandomAccess, TrustedRandomAccessNoCoerce, }; -use crate::iter::{FusedIterator, TrustedLen}; +use crate::iter::{FusedIterator, TrustedLen, UncheckedIterator}; use crate::ops::Try; /// An iterator that clones the elements of an underlying iterator. @@ -140,3 +140,16 @@ where T: Clone, { } + +impl<'a, I, T: 'a> UncheckedIterator for Cloned<I> +where + I: UncheckedIterator<Item = &'a T>, + T: Clone, +{ + unsafe fn next_unchecked(&mut self) -> T { + // SAFETY: `Cloned` is 1:1 with the inner iterator, so if the caller promised + // that there's an element left, the inner iterator has one too. + let item = unsafe { self.it.next_unchecked() }; + item.clone() + } +} diff --git a/library/core/src/iter/adapters/map.rs b/library/core/src/iter/adapters/map.rs index 9e25dbe462c..31d02a4da6e 100644 --- a/library/core/src/iter/adapters/map.rs +++ b/library/core/src/iter/adapters/map.rs @@ -2,7 +2,7 @@ use crate::fmt; use crate::iter::adapters::{ zip::try_get_unchecked, SourceIter, TrustedRandomAccess, TrustedRandomAccessNoCoerce, }; -use crate::iter::{FusedIterator, InPlaceIterable, TrustedLen}; +use crate::iter::{FusedIterator, InPlaceIterable, TrustedLen, UncheckedIterator}; use crate::ops::Try; /// An iterator that maps the values of `iter` with `f`. @@ -187,6 +187,19 @@ where { } +impl<B, I, F> UncheckedIterator for Map<I, F> +where + I: UncheckedIterator, + F: FnMut(I::Item) -> B, +{ + unsafe fn next_unchecked(&mut self) -> B { + // SAFETY: `Map` is 1:1 with the inner iterator, so if the caller promised + // that there's an element left, the inner iterator has one too. + let item = unsafe { self.iter.next_unchecked() }; + (self.f)(item) + } +} + #[doc(hidden)] #[unstable(feature = "trusted_random_access", issue = "none")] unsafe impl<I, F> TrustedRandomAccess for Map<I, F> where I: TrustedRandomAccess {} diff --git a/library/core/src/iter/adapters/zip.rs b/library/core/src/iter/adapters/zip.rs index 8153c8cfef1..b6b0c90cb7d 100644 --- a/library/core/src/iter/adapters/zip.rs +++ b/library/core/src/iter/adapters/zip.rs @@ -1,7 +1,7 @@ use crate::cmp; use crate::fmt::{self, Debug}; use crate::iter::{DoubleEndedIterator, ExactSizeIterator, FusedIterator, Iterator}; -use crate::iter::{InPlaceIterable, SourceIter, TrustedLen}; +use crate::iter::{InPlaceIterable, SourceIter, TrustedLen, UncheckedIterator}; /// An iterator that iterates two other iterators simultaneously. /// @@ -417,6 +417,13 @@ where { } +impl<A, B> UncheckedIterator for Zip<A, B> +where + A: UncheckedIterator, + B: UncheckedIterator, +{ +} + // Arbitrarily selects the left side of the zip iteration as extractable "source" // it would require negative trait bounds to be able to try both #[unstable(issue = "none", feature = "inplace_iteration")] diff --git a/library/core/src/iter/mod.rs b/library/core/src/iter/mod.rs index 00f57fbcc61..156b925de77 100644 --- a/library/core/src/iter/mod.rs +++ b/library/core/src/iter/mod.rs @@ -450,6 +450,7 @@ pub use self::adapters::{ pub use self::adapters::{Intersperse, IntersperseWith}; pub(crate) use self::adapters::try_process; +pub(crate) use self::traits::UncheckedIterator; mod adapters; mod range; diff --git a/library/core/src/iter/range.rs b/library/core/src/iter/range.rs index b5739f2f3c0..78e27d73065 100644 --- a/library/core/src/iter/range.rs +++ b/library/core/src/iter/range.rs @@ -1,4 +1,3 @@ -use crate::char; use crate::convert::TryFrom; use crate::mem; use crate::ops::{self, Try}; diff --git a/library/core/src/iter/traits/exact_size.rs b/library/core/src/iter/traits/exact_size.rs index 1757e37ec0e..908830d8a95 100644 --- a/library/core/src/iter/traits/exact_size.rs +++ b/library/core/src/iter/traits/exact_size.rs @@ -21,6 +21,16 @@ /// /// [`len`]: ExactSizeIterator::len /// +/// # When *shouldn't* an adapter be `ExactSizeIterator`? +/// +/// If an adapter makes an iterator *longer*, then it's usually incorrect for +/// that adapter to implement `ExactSizeIterator`. The inner exact-sized +/// iterator might already be `usize::MAX`-long, and thus the length of the +/// longer adapted iterator would no longer be exactly representable in `usize`. +/// +/// This is why [`Chain<A, B>`](crate::iter::Chain) isn't `ExactSizeIterator`, +/// even when `A` and `B` are both `ExactSizeIterator`. +/// /// # Examples /// /// Basic usage: diff --git a/library/core/src/iter/traits/marker.rs b/library/core/src/iter/traits/marker.rs index da753745740..af02848233d 100644 --- a/library/core/src/iter/traits/marker.rs +++ b/library/core/src/iter/traits/marker.rs @@ -31,6 +31,17 @@ impl<I: FusedIterator + ?Sized> FusedIterator for &mut I {} /// The iterator must produce exactly the number of elements it reported /// or diverge before reaching the end. /// +/// # When *shouldn't* an adapter be `TrustedLen`? +/// +/// If an adapter makes an iterator *shorter* by a given amount, then it's +/// usually incorrect for that adapter to implement `TrustedLen`. The inner +/// iterator might return more than `usize::MAX` items, but there's no way to +/// know what `k` elements less than that will be, since the `size_hint` from +/// the inner iterator has already saturated and lost that information. +/// +/// This is why [`Skip<I>`](crate::iter::Skip) isn't `TrustedLen`, even when +/// `I` implements `TrustedLen`. +/// /// # Safety /// /// This trait must only be implemented when the contract is upheld. Consumers diff --git a/library/core/src/iter/traits/mod.rs b/library/core/src/iter/traits/mod.rs index ed0fb634dbf..41ea29e6a84 100644 --- a/library/core/src/iter/traits/mod.rs +++ b/library/core/src/iter/traits/mod.rs @@ -4,6 +4,7 @@ mod double_ended; mod exact_size; mod iterator; mod marker; +mod unchecked_iterator; #[stable(feature = "rust1", since = "1.0.0")] pub use self::{ @@ -19,3 +20,5 @@ pub use self::{ pub use self::marker::InPlaceIterable; #[unstable(feature = "trusted_step", issue = "85731")] pub use self::marker::TrustedStep; + +pub(crate) use self::unchecked_iterator::UncheckedIterator; diff --git a/library/core/src/iter/traits/unchecked_iterator.rs b/library/core/src/iter/traits/unchecked_iterator.rs new file mode 100644 index 00000000000..ae4bfcad4e6 --- /dev/null +++ b/library/core/src/iter/traits/unchecked_iterator.rs @@ -0,0 +1,36 @@ +use crate::iter::TrustedLen; + +/// [`TrustedLen`] cannot have methods, so this allows augmenting it. +/// +/// It currently requires `TrustedLen` because it's unclear whether it's +/// reasonably possible to depend on the `size_hint` of anything else. +pub(crate) trait UncheckedIterator: TrustedLen { + /// Gets the next item from a non-empty iterator. + /// + /// Because there's always a value to return, that means it can return + /// the `Item` type directly, without wrapping it in an `Option`. + /// + /// # Safety + /// + /// This can only be called if `size_hint().0 != 0`, guaranteeing that + /// there's at least one item available. + /// + /// Otherwise (aka when `size_hint().1 == Some(0)`), this is UB. + /// + /// # Note to Implementers + /// + /// This has a default implementation using [`Option::unwrap_unchecked`]. + /// That's probably sufficient if your `next` *always* returns `Some`, + /// such as for infinite iterators. In more complicated situations, however, + /// sometimes there can still be `insertvalue`/`assume`/`extractvalue` + /// instructions remaining in the IR from the `Option` handling, at which + /// point you might want to implement this manually instead. + #[unstable(feature = "trusted_len_next_unchecked", issue = "37572")] + #[inline] + unsafe fn next_unchecked(&mut self) -> Self::Item { + let opt = self.next(); + // SAFETY: The caller promised that we're not empty, and + // `Self: TrustedLen` so we can actually trust the `size_hint`. + unsafe { opt.unwrap_unchecked() } + } +} diff --git a/library/core/src/marker.rs b/library/core/src/marker.rs index e11bca5962a..520ae0edb09 100644 --- a/library/core/src/marker.rs +++ b/library/core/src/marker.rs @@ -97,6 +97,7 @@ unsafe impl<T: Sync + ?Sized> Send for &T {} #[fundamental] // for Default, for example, which requires that `[T]: !Default` be evaluatable #[rustc_specialization_trait] #[rustc_deny_explicit_impl] +#[cfg_attr(not(bootstrap), rustc_coinductive)] pub trait Sized { // Empty. } @@ -871,7 +872,10 @@ pub trait Destruct {} #[rustc_deny_explicit_impl] pub trait Tuple {} -/// A marker for things +/// A marker for pointer-like types. +/// +/// All types that have the same size and alignment as a `usize` or +/// `*const ()` automatically implement this trait. #[unstable(feature = "pointer_like_trait", issue = "none")] #[cfg_attr(bootstrap, lang = "pointer_sized")] #[cfg_attr(not(bootstrap), lang = "pointer_like")] diff --git a/library/core/src/num/int_log10.rs b/library/core/src/num/int_log10.rs index 80472528f6c..0ce31b40a38 100644 --- a/library/core/src/num/int_log10.rs +++ b/library/core/src/num/int_log10.rs @@ -138,3 +138,11 @@ pub const fn i64(val: i64) -> u32 { pub const fn i128(val: i128) -> u32 { u128(val as u128) } + +/// Instantiate this panic logic once, rather than for all the ilog methods +/// on every single primitive type. +#[cold] +#[track_caller] +pub const fn panic_for_nonpositive_argument() -> ! { + panic!("argument of integer logarithm must be positive") +} diff --git a/library/core/src/num/int_macros.rs b/library/core/src/num/int_macros.rs index b59f28193e2..479f8ffb78d 100644 --- a/library/core/src/num/int_macros.rs +++ b/library/core/src/num/int_macros.rs @@ -2331,14 +2331,17 @@ macro_rules! int_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog(self, base: Self) -> u32 { assert!(base >= 2, "base of integer logarithm must be at least 2"); - self.checked_ilog(base).expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog(base) { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the base 2 logarithm of the number, rounded down. @@ -2354,13 +2357,16 @@ macro_rules! int_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog2(self) -> u32 { - self.checked_ilog2().expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog2() { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the base 10 logarithm of the number, rounded down. @@ -2376,13 +2382,16 @@ macro_rules! int_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog10(self) -> u32 { - self.checked_ilog10().expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog10() { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the logarithm of the number with respect to an arbitrary base, diff --git a/library/core/src/num/shells/i128.rs b/library/core/src/num/shells/i128.rs index 7b048dc5206..b3b3d3b4875 100644 --- a/library/core/src/num/shells/i128.rs +++ b/library/core/src/num/shells/i128.rs @@ -1,6 +1,4 @@ -//! Constants for the 128-bit signed integer type. -//! -//! *[See also the `i128` primitive type][i128].* +//! Redundant constants module for the [`i128` primitive type][i128]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/i16.rs b/library/core/src/num/shells/i16.rs index 5c5812d5c5e..70a452e1939 100644 --- a/library/core/src/num/shells/i16.rs +++ b/library/core/src/num/shells/i16.rs @@ -1,6 +1,4 @@ -//! Constants for the 16-bit signed integer type. -//! -//! *[See also the `i16` primitive type][i16].* +//! Redundant constants module for the [`i16` primitive type][i16]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/i32.rs b/library/core/src/num/shells/i32.rs index b283ac64415..c30849e2591 100644 --- a/library/core/src/num/shells/i32.rs +++ b/library/core/src/num/shells/i32.rs @@ -1,6 +1,4 @@ -//! Constants for the 32-bit signed integer type. -//! -//! *[See also the `i32` primitive type][i32].* +//! Redundant constants module for the [`i32` primitive type][i32]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/i64.rs b/library/core/src/num/shells/i64.rs index a416fa7e936..77d95d71250 100644 --- a/library/core/src/num/shells/i64.rs +++ b/library/core/src/num/shells/i64.rs @@ -1,6 +1,4 @@ -//! Constants for the 64-bit signed integer type. -//! -//! *[See also the `i64` primitive type][i64].* +//! Redundant constants module for the [`i64` primitive type][i64]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/i8.rs b/library/core/src/num/shells/i8.rs index 02465013a4a..516ba8cdef3 100644 --- a/library/core/src/num/shells/i8.rs +++ b/library/core/src/num/shells/i8.rs @@ -1,6 +1,4 @@ -//! Constants for the 8-bit signed integer type. -//! -//! *[See also the `i8` primitive type][i8].* +//! Redundant constants module for the [`i8` primitive type][i8]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/isize.rs b/library/core/src/num/shells/isize.rs index 1579fbab6d4..828f7345baf 100644 --- a/library/core/src/num/shells/isize.rs +++ b/library/core/src/num/shells/isize.rs @@ -1,6 +1,4 @@ -//! Constants for the pointer-sized signed integer type. -//! -//! *[See also the `isize` primitive type][isize].* +//! Redundant constants module for the [`isize` primitive type][isize]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/u128.rs b/library/core/src/num/shells/u128.rs index fe08cee586c..b1e30e38435 100644 --- a/library/core/src/num/shells/u128.rs +++ b/library/core/src/num/shells/u128.rs @@ -1,6 +1,4 @@ -//! Constants for the 128-bit unsigned integer type. -//! -//! *[See also the `u128` primitive type][u128].* +//! Redundant constants module for the [`u128` primitive type][u128]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/u16.rs b/library/core/src/num/shells/u16.rs index 36f8c697878..b203806f460 100644 --- a/library/core/src/num/shells/u16.rs +++ b/library/core/src/num/shells/u16.rs @@ -1,6 +1,4 @@ -//! Constants for the 16-bit unsigned integer type. -//! -//! *[See also the `u16` primitive type][u16].* +//! Redundant constants module for the [`i16` primitive type][i16]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/u32.rs b/library/core/src/num/shells/u32.rs index 1c369097dcd..4c84274e752 100644 --- a/library/core/src/num/shells/u32.rs +++ b/library/core/src/num/shells/u32.rs @@ -1,6 +1,4 @@ -//! Constants for the 32-bit unsigned integer type. -//! -//! *[See also the `u32` primitive type][u32].* +//! Redundant constants module for the [`u32` primitive type][u32]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/u64.rs b/library/core/src/num/shells/u64.rs index e8b691d1555..47a95c6820f 100644 --- a/library/core/src/num/shells/u64.rs +++ b/library/core/src/num/shells/u64.rs @@ -1,6 +1,4 @@ -//! Constants for the 64-bit unsigned integer type. -//! -//! *[See also the `u64` primitive type][u64].* +//! Redundant constants module for the [`u64` primitive type][u64]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/u8.rs b/library/core/src/num/shells/u8.rs index 817c6a18aaa..360baef7228 100644 --- a/library/core/src/num/shells/u8.rs +++ b/library/core/src/num/shells/u8.rs @@ -1,6 +1,4 @@ -//! Constants for the 8-bit unsigned integer type. -//! -//! *[See also the `u8` primitive type][u8].* +//! Redundant constants module for the [`u8` primitive type][u8]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/shells/usize.rs b/library/core/src/num/shells/usize.rs index 3e1bec5ec48..44c24dfc2cf 100644 --- a/library/core/src/num/shells/usize.rs +++ b/library/core/src/num/shells/usize.rs @@ -1,6 +1,4 @@ -//! Constants for the pointer-sized unsigned integer type. -//! -//! *[See also the `usize` primitive type][usize].* +//! Redundant constants module for the [`usize` primitive type][usize]. //! //! New code should use the associated constants directly on the primitive type. diff --git a/library/core/src/num/uint_macros.rs b/library/core/src/num/uint_macros.rs index dcc0835ecd6..495c44bd859 100644 --- a/library/core/src/num/uint_macros.rs +++ b/library/core/src/num/uint_macros.rs @@ -705,14 +705,17 @@ macro_rules! uint_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog(self, base: Self) -> u32 { assert!(base >= 2, "base of integer logarithm must be at least 2"); - self.checked_ilog(base).expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog(base) { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the base 2 logarithm of the number, rounded down. @@ -728,13 +731,16 @@ macro_rules! uint_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog2(self) -> u32 { - self.checked_ilog2().expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog2() { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the base 10 logarithm of the number, rounded down. @@ -750,13 +756,16 @@ macro_rules! uint_impl { /// ``` #[stable(feature = "int_log", since = "1.67.0")] #[rustc_const_stable(feature = "int_log", since = "1.67.0")] - #[rustc_allow_const_fn_unstable(const_option)] #[must_use = "this returns the result of the operation, \ without modifying the original"] #[inline] #[track_caller] pub const fn ilog10(self) -> u32 { - self.checked_ilog10().expect("argument of integer logarithm must be positive") + if let Some(log) = self.checked_ilog10() { + log + } else { + int_log10::panic_for_nonpositive_argument() + } } /// Returns the logarithm of the number with respect to an arbitrary base, diff --git a/library/core/src/ops/try_trait.rs b/library/core/src/ops/try_trait.rs index 9108fc63045..86aa1e4fd20 100644 --- a/library/core/src/ops/try_trait.rs +++ b/library/core/src/ops/try_trait.rs @@ -379,6 +379,15 @@ pub(crate) type ChangeOutputType<T, V> = <<T as Try>::Residual as Residual<V>>:: pub(crate) struct NeverShortCircuit<T>(pub T); impl<T> NeverShortCircuit<T> { + /// Wraps a unary function to produce one that wraps the output into a `NeverShortCircuit`. + /// + /// This is useful for implementing infallible functions in terms of the `try_` ones, + /// without accidentally capturing extra generic parameters in a closure. + #[inline] + pub fn wrap_mut_1<A>(mut f: impl FnMut(A) -> T) -> impl FnMut(A) -> NeverShortCircuit<T> { + move |a| NeverShortCircuit(f(a)) + } + #[inline] pub fn wrap_mut_2<A, B>( mut f: impl ~const FnMut(A, B) -> T, diff --git a/library/core/src/ptr/const_ptr.rs b/library/core/src/ptr/const_ptr.rs index 16eb726f6f6..57e2ffe5d20 100644 --- a/library/core/src/ptr/const_ptr.rs +++ b/library/core/src/ptr/const_ptr.rs @@ -23,8 +23,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "Follow the rabbit"; /// let ptr: *const u8 = s.as_ptr(); @@ -323,8 +321,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let ptr: *const u8 = &10u8 as *const u8; /// @@ -384,8 +380,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// #![feature(ptr_as_uninit)] /// @@ -449,8 +443,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "123"; /// let ptr: *const u8 = s.as_ptr(); @@ -526,8 +518,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements /// let data = [1u8, 2, 3, 4, 5]; @@ -908,8 +898,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "123"; /// let ptr: *const u8 = s.as_ptr(); @@ -993,8 +981,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "123"; /// @@ -1072,8 +1058,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements /// let data = [1u8, 2, 3, 4, 5]; @@ -1152,8 +1136,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements (backwards) /// let data = [1u8, 2, 3, 4, 5]; @@ -1359,7 +1341,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: /// ``` /// #![feature(pointer_is_aligned)] /// #![feature(pointer_byte_offsets)] @@ -1482,7 +1463,6 @@ impl<T: ?Sized> *const T { /// /// # Examples /// - /// Basic usage: /// ``` /// #![feature(pointer_is_aligned)] /// #![feature(pointer_byte_offsets)] diff --git a/library/core/src/ptr/mut_ptr.rs b/library/core/src/ptr/mut_ptr.rs index 0a2f63e3ec6..422d0f2b8f0 100644 --- a/library/core/src/ptr/mut_ptr.rs +++ b/library/core/src/ptr/mut_ptr.rs @@ -22,8 +22,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let mut s = [1, 2, 3]; /// let ptr: *mut u32 = s.as_mut_ptr(); @@ -332,8 +330,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let ptr: *mut u8 = &mut 10u8 as *mut u8; /// @@ -396,8 +392,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// #![feature(ptr_as_uninit)] /// @@ -461,8 +455,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let mut s = [1, 2, 3]; /// let ptr: *mut u32 = s.as_mut_ptr(); @@ -539,8 +531,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements /// let mut data = [1u8, 2, 3, 4, 5]; @@ -660,8 +650,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let mut s = [1, 2, 3]; /// let ptr: *mut u32 = s.as_mut_ptr(); @@ -1010,8 +998,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "123"; /// let ptr: *const u8 = s.as_ptr(); @@ -1095,8 +1081,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// let s: &str = "123"; /// @@ -1174,8 +1158,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements /// let data = [1u8, 2, 3, 4, 5]; @@ -1254,8 +1236,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: - /// /// ``` /// // Iterate using a raw pointer in increments of two elements (backwards) /// let data = [1u8, 2, 3, 4, 5]; @@ -1627,7 +1607,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: /// ``` /// #![feature(pointer_is_aligned)] /// #![feature(pointer_byte_offsets)] @@ -1752,7 +1731,6 @@ impl<T: ?Sized> *mut T { /// /// # Examples /// - /// Basic usage: /// ``` /// #![feature(pointer_is_aligned)] /// #![feature(pointer_byte_offsets)] diff --git a/library/core/src/result.rs b/library/core/src/result.rs index f00c40f35d5..7596e9cc005 100644 --- a/library/core/src/result.rs +++ b/library/core/src/result.rs @@ -458,7 +458,7 @@ //! [`Result`] of a collection of each contained value of the original //! [`Result`] values, or [`Err`] if any of the elements was [`Err`]. //! -//! [impl-FromIterator]: Result#impl-FromIterator%3CResult%3CA%2C%20E%3E%3E-for-Result%3CV%2C%20E%3E +//! [impl-FromIterator]: Result#impl-FromIterator%3CResult%3CA,+E%3E%3E-for-Result%3CV,+E%3E //! //! ``` //! let v = [Ok(2), Ok(4), Err("err!"), Ok(8)]; @@ -474,8 +474,8 @@ //! to provide the [`product`][Iterator::product] and //! [`sum`][Iterator::sum] methods. //! -//! [impl-Product]: Result#impl-Product%3CResult%3CU%2C%20E%3E%3E-for-Result%3CT%2C%20E%3E -//! [impl-Sum]: Result#impl-Sum%3CResult%3CU%2C%20E%3E%3E-for-Result%3CT%2C%20E%3E +//! [impl-Product]: Result#impl-Product%3CResult%3CU,+E%3E%3E-for-Result%3CT,+E%3E +//! [impl-Sum]: Result#impl-Sum%3CResult%3CU,+E%3E%3E-for-Result%3CT,+E%3E //! //! ``` //! let v = [Err("error!"), Ok(1), Ok(2), Ok(3), Err("foo")]; diff --git a/library/core/src/slice/iter.rs b/library/core/src/slice/iter.rs index 90ab43d1289..c4317799bcc 100644 --- a/library/core/src/slice/iter.rs +++ b/library/core/src/slice/iter.rs @@ -7,7 +7,9 @@ use crate::cmp; use crate::cmp::Ordering; use crate::fmt; use crate::intrinsics::assume; -use crate::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce}; +use crate::iter::{ + FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, UncheckedIterator, +}; use crate::marker::{PhantomData, Send, Sized, Sync}; use crate::mem::{self, SizedTypeProperties}; use crate::num::NonZeroUsize; diff --git a/library/core/src/slice/iter/macros.rs b/library/core/src/slice/iter/macros.rs index 0fd57b197aa..89b92a7d597 100644 --- a/library/core/src/slice/iter/macros.rs +++ b/library/core/src/slice/iter/macros.rs @@ -384,6 +384,15 @@ macro_rules! iterator { #[unstable(feature = "trusted_len", issue = "37572")] unsafe impl<T> TrustedLen for $name<'_, T> {} + + impl<'a, T> UncheckedIterator for $name<'a, T> { + unsafe fn next_unchecked(&mut self) -> $elem { + // SAFETY: The caller promised there's at least one more item. + unsafe { + next_unchecked!(self) + } + } + } } } diff --git a/library/core/src/slice/sort.rs b/library/core/src/slice/sort.rs index 2181f9a8118..4ca4eb86bde 100644 --- a/library/core/src/slice/sort.rs +++ b/library/core/src/slice/sort.rs @@ -13,115 +13,184 @@ use crate::cmp; use crate::mem::{self, MaybeUninit, SizedTypeProperties}; use crate::ptr; -/// When dropped, copies from `src` into `dest`. -struct CopyOnDrop<T> { +// When dropped, copies from `src` into `dest`. +struct InsertionHole<T> { src: *const T, dest: *mut T, } -impl<T> Drop for CopyOnDrop<T> { +impl<T> Drop for InsertionHole<T> { fn drop(&mut self) { - // SAFETY: This is a helper class. - // Please refer to its usage for correctness. - // Namely, one must be sure that `src` and `dst` does not overlap as required by `ptr::copy_nonoverlapping`. + // SAFETY: This is a helper class. Please refer to its usage for correctness. Namely, one + // must be sure that `src` and `dst` does not overlap as required by + // `ptr::copy_nonoverlapping` and are both valid for writes. unsafe { ptr::copy_nonoverlapping(self.src, self.dest, 1); } } } -/// Shifts the first element to the right until it encounters a greater or equal element. -fn shift_head<T, F>(v: &mut [T], is_less: &mut F) +/// Inserts `v[v.len() - 1]` into pre-sorted sequence `v[..v.len() - 1]` so that whole `v[..]` +/// becomes sorted. +unsafe fn insert_tail<T, F>(v: &mut [T], is_less: &mut F) where F: FnMut(&T, &T) -> bool, { - let len = v.len(); - // SAFETY: The unsafe operations below involves indexing without a bounds check (by offsetting a - // pointer) and copying memory (`ptr::copy_nonoverlapping`). - // - // a. Indexing: - // 1. We checked the size of the array to >=2. - // 2. All the indexing that we will do is always between {0 <= index < len} at most. - // - // b. Memory copying - // 1. We are obtaining pointers to references which are guaranteed to be valid. - // 2. They cannot overlap because we obtain pointers to difference indices of the slice. - // Namely, `i` and `i-1`. - // 3. If the slice is properly aligned, the elements are properly aligned. - // It is the caller's responsibility to make sure the slice is properly aligned. - // - // See comments below for further detail. + debug_assert!(v.len() >= 2); + + let arr_ptr = v.as_mut_ptr(); + let i = v.len() - 1; + + // SAFETY: caller must ensure v is at least len 2. unsafe { - // If the first two elements are out-of-order... - if len >= 2 && is_less(v.get_unchecked(1), v.get_unchecked(0)) { - // Read the first element into a stack-allocated variable. If a following comparison - // operation panics, `hole` will get dropped and automatically write the element back - // into the slice. - let tmp = mem::ManuallyDrop::new(ptr::read(v.get_unchecked(0))); - let v = v.as_mut_ptr(); - let mut hole = CopyOnDrop { src: &*tmp, dest: v.add(1) }; - ptr::copy_nonoverlapping(v.add(1), v.add(0), 1); - - for i in 2..len { - if !is_less(&*v.add(i), &*tmp) { + // See insert_head which talks about why this approach is beneficial. + let i_ptr = arr_ptr.add(i); + + // It's important that we use i_ptr here. If this check is positive and we continue, + // We want to make sure that no other copy of the value was seen by is_less. + // Otherwise we would have to copy it back. + if is_less(&*i_ptr, &*i_ptr.sub(1)) { + // It's important, that we use tmp for comparison from now on. As it is the value that + // will be copied back. And notionally we could have created a divergence if we copy + // back the wrong value. + let tmp = mem::ManuallyDrop::new(ptr::read(i_ptr)); + // Intermediate state of the insertion process is always tracked by `hole`, which + // serves two purposes: + // 1. Protects integrity of `v` from panics in `is_less`. + // 2. Fills the remaining hole in `v` in the end. + // + // Panic safety: + // + // If `is_less` panics at any point during the process, `hole` will get dropped and + // fill the hole in `v` with `tmp`, thus ensuring that `v` still holds every object it + // initially held exactly once. + let mut hole = InsertionHole { src: &*tmp, dest: i_ptr.sub(1) }; + ptr::copy_nonoverlapping(hole.dest, i_ptr, 1); + + // SAFETY: We know i is at least 1. + for j in (0..(i - 1)).rev() { + let j_ptr = arr_ptr.add(j); + if !is_less(&*tmp, &*j_ptr) { break; } - // Move `i`-th element one place to the left, thus shifting the hole to the right. - ptr::copy_nonoverlapping(v.add(i), v.add(i - 1), 1); - hole.dest = v.add(i); + ptr::copy_nonoverlapping(j_ptr, hole.dest, 1); + hole.dest = j_ptr; } // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`. } } } -/// Shifts the last element to the left until it encounters a smaller or equal element. -fn shift_tail<T, F>(v: &mut [T], is_less: &mut F) +/// Inserts `v[0]` into pre-sorted sequence `v[1..]` so that whole `v[..]` becomes sorted. +/// +/// This is the integral subroutine of insertion sort. +unsafe fn insert_head<T, F>(v: &mut [T], is_less: &mut F) where F: FnMut(&T, &T) -> bool, { - let len = v.len(); - // SAFETY: The unsafe operations below involves indexing without a bound check (by offsetting a - // pointer) and copying memory (`ptr::copy_nonoverlapping`). - // - // a. Indexing: - // 1. We checked the size of the array to >= 2. - // 2. All the indexing that we will do is always between `0 <= index < len-1` at most. - // - // b. Memory copying - // 1. We are obtaining pointers to references which are guaranteed to be valid. - // 2. They cannot overlap because we obtain pointers to difference indices of the slice. - // Namely, `i` and `i+1`. - // 3. If the slice is properly aligned, the elements are properly aligned. - // It is the caller's responsibility to make sure the slice is properly aligned. - // - // See comments below for further detail. + debug_assert!(v.len() >= 2); + + // SAFETY: caller must ensure v is at least len 2. unsafe { - // If the last two elements are out-of-order... - if len >= 2 && is_less(v.get_unchecked(len - 1), v.get_unchecked(len - 2)) { - // Read the last element into a stack-allocated variable. If a following comparison - // operation panics, `hole` will get dropped and automatically write the element back - // into the slice. - let tmp = mem::ManuallyDrop::new(ptr::read(v.get_unchecked(len - 1))); - let v = v.as_mut_ptr(); - let mut hole = CopyOnDrop { src: &*tmp, dest: v.add(len - 2) }; - ptr::copy_nonoverlapping(v.add(len - 2), v.add(len - 1), 1); - - for i in (0..len - 2).rev() { - if !is_less(&*tmp, &*v.add(i)) { + if is_less(v.get_unchecked(1), v.get_unchecked(0)) { + let arr_ptr = v.as_mut_ptr(); + + // There are three ways to implement insertion here: + // + // 1. Swap adjacent elements until the first one gets to its final destination. + // However, this way we copy data around more than is necessary. If elements are big + // structures (costly to copy), this method will be slow. + // + // 2. Iterate until the right place for the first element is found. Then shift the + // elements succeeding it to make room for it and finally place it into the + // remaining hole. This is a good method. + // + // 3. Copy the first element into a temporary variable. Iterate until the right place + // for it is found. As we go along, copy every traversed element into the slot + // preceding it. Finally, copy data from the temporary variable into the remaining + // hole. This method is very good. Benchmarks demonstrated slightly better + // performance than with the 2nd method. + // + // All methods were benchmarked, and the 3rd showed best results. So we chose that one. + let tmp = mem::ManuallyDrop::new(ptr::read(arr_ptr)); + + // Intermediate state of the insertion process is always tracked by `hole`, which + // serves two purposes: + // 1. Protects integrity of `v` from panics in `is_less`. + // 2. Fills the remaining hole in `v` in the end. + // + // Panic safety: + // + // If `is_less` panics at any point during the process, `hole` will get dropped and + // fill the hole in `v` with `tmp`, thus ensuring that `v` still holds every object it + // initially held exactly once. + let mut hole = InsertionHole { src: &*tmp, dest: arr_ptr.add(1) }; + ptr::copy_nonoverlapping(arr_ptr.add(1), arr_ptr.add(0), 1); + + for i in 2..v.len() { + if !is_less(&v.get_unchecked(i), &*tmp) { break; } - - // Move `i`-th element one place to the right, thus shifting the hole to the left. - ptr::copy_nonoverlapping(v.add(i), v.add(i + 1), 1); - hole.dest = v.add(i); + ptr::copy_nonoverlapping(arr_ptr.add(i), arr_ptr.add(i - 1), 1); + hole.dest = arr_ptr.add(i); } // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`. } } } +/// Sort `v` assuming `v[..offset]` is already sorted. +/// +/// Never inline this function to avoid code bloat. It still optimizes nicely and has practically no +/// performance impact. Even improving performance in some cases. +#[inline(never)] +fn insertion_sort_shift_left<T, F>(v: &mut [T], offset: usize, is_less: &mut F) +where + F: FnMut(&T, &T) -> bool, +{ + let len = v.len(); + + // Using assert here improves performance. + assert!(offset != 0 && offset <= len); + + // Shift each element of the unsorted region v[i..] as far left as is needed to make v sorted. + for i in offset..len { + // SAFETY: we tested that `offset` must be at least 1, so this loop is only entered if len + // >= 2. The range is exclusive and we know `i` must be at least 1 so this slice has at + // >least len 2. + unsafe { + insert_tail(&mut v[..=i], is_less); + } + } +} + +/// Sort `v` assuming `v[offset..]` is already sorted. +/// +/// Never inline this function to avoid code bloat. It still optimizes nicely and has practically no +/// performance impact. Even improving performance in some cases. +#[inline(never)] +fn insertion_sort_shift_right<T, F>(v: &mut [T], offset: usize, is_less: &mut F) +where + F: FnMut(&T, &T) -> bool, +{ + let len = v.len(); + + // Using assert here improves performance. + assert!(offset != 0 && offset <= len && len >= 2); + + // Shift each element of the unsorted region v[..i] as far left as is needed to make v sorted. + for i in (0..offset).rev() { + // SAFETY: we tested that `offset` must be at least 1, so this loop is only entered if len + // >= 2.We ensured that the slice length is always at least 2 long. We know that start_found + // will be at least one less than end, and the range is exclusive. Which gives us i always + // <= (end - 2). + unsafe { + insert_head(&mut v[i..len], is_less); + } + } +} + /// Partially sorts a slice by shifting several out-of-order elements around. /// /// Returns `true` if the slice is sorted at the end. This function is *O*(*n*) worst-case. @@ -161,26 +230,19 @@ where // Swap the found pair of elements. This puts them in correct order. v.swap(i - 1, i); - // Shift the smaller element to the left. - shift_tail(&mut v[..i], is_less); - // Shift the greater element to the right. - shift_head(&mut v[i..], is_less); + if i >= 2 { + // Shift the smaller element to the left. + insertion_sort_shift_left(&mut v[..i], i - 1, is_less); + + // Shift the greater element to the right. + insertion_sort_shift_right(&mut v[..i], 1, is_less); + } } // Didn't manage to sort the slice in the limited number of steps. false } -/// Sorts a slice using insertion sort, which is *O*(*n*^2) worst-case. -fn insertion_sort<T, F>(v: &mut [T], is_less: &mut F) -where - F: FnMut(&T, &T) -> bool, -{ - for i in 1..v.len() { - shift_tail(&mut v[..i + 1], is_less); - } -} - /// Sorts `v` using heapsort, which guarantees *O*(*n* \* log(*n*)) worst-case. #[cold] #[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "none")] @@ -198,8 +260,11 @@ where } // Choose the greater child. - if child + 1 < v.len() && is_less(&v[child], &v[child + 1]) { - child += 1; + if child + 1 < v.len() { + // We need a branch to be sure not to out-of-bounds index, + // but it's highly predictable. The comparison, however, + // is better done branchless, especially for primitives. + child += is_less(&v[child], &v[child + 1]) as usize; } // Stop if the invariant holds at `node`. @@ -507,7 +572,7 @@ where // SAFETY: `pivot` is a reference to the first element of `v`, so `ptr::read` is safe. let tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) }); - let _pivot_guard = CopyOnDrop { src: &*tmp, dest: pivot }; + let _pivot_guard = InsertionHole { src: &*tmp, dest: pivot }; let pivot = &*tmp; // Find the first pair of out-of-order elements. @@ -560,7 +625,7 @@ where // operation panics, the pivot will be automatically written back into the slice. // SAFETY: The pointer here is valid because it is obtained from a reference to a slice. let tmp = mem::ManuallyDrop::new(unsafe { ptr::read(pivot) }); - let _pivot_guard = CopyOnDrop { src: &*tmp, dest: pivot }; + let _pivot_guard = InsertionHole { src: &*tmp, dest: pivot }; let pivot = &*tmp; // Now partition the slice. @@ -742,7 +807,9 @@ where // Very short slices get sorted using insertion sort. if len <= MAX_INSERTION { - insertion_sort(v, is_less); + if len >= 2 { + insertion_sort_shift_left(v, 1, is_less); + } return; } @@ -844,10 +911,14 @@ fn partition_at_index_loop<'a, T, F>( let mut was_balanced = true; loop { + let len = v.len(); + // For slices of up to this length it's probably faster to simply sort them. const MAX_INSERTION: usize = 10; - if v.len() <= MAX_INSERTION { - insertion_sort(v, is_less); + if len <= MAX_INSERTION { + if len >= 2 { + insertion_sort_shift_left(v, 1, is_less); + } return; } @@ -887,7 +958,7 @@ fn partition_at_index_loop<'a, T, F>( } let (mid, _) = partition(v, pivot, is_less); - was_balanced = cmp::min(mid, v.len() - mid) >= v.len() / 8; + was_balanced = cmp::min(mid, len - mid) >= len / 8; // Split the slice into `left`, `pivot`, and `right`. let (left, right) = v.split_at_mut(mid); @@ -954,75 +1025,6 @@ where (left, pivot, right) } -/// Inserts `v[0]` into pre-sorted sequence `v[1..]` so that whole `v[..]` becomes sorted. -/// -/// This is the integral subroutine of insertion sort. -fn insert_head<T, F>(v: &mut [T], is_less: &mut F) -where - F: FnMut(&T, &T) -> bool, -{ - if v.len() >= 2 && is_less(&v[1], &v[0]) { - // SAFETY: Copy tmp back even if panic, and ensure unique observation. - unsafe { - // There are three ways to implement insertion here: - // - // 1. Swap adjacent elements until the first one gets to its final destination. - // However, this way we copy data around more than is necessary. If elements are big - // structures (costly to copy), this method will be slow. - // - // 2. Iterate until the right place for the first element is found. Then shift the - // elements succeeding it to make room for it and finally place it into the - // remaining hole. This is a good method. - // - // 3. Copy the first element into a temporary variable. Iterate until the right place - // for it is found. As we go along, copy every traversed element into the slot - // preceding it. Finally, copy data from the temporary variable into the remaining - // hole. This method is very good. Benchmarks demonstrated slightly better - // performance than with the 2nd method. - // - // All methods were benchmarked, and the 3rd showed best results. So we chose that one. - let tmp = mem::ManuallyDrop::new(ptr::read(&v[0])); - - // Intermediate state of the insertion process is always tracked by `hole`, which - // serves two purposes: - // 1. Protects integrity of `v` from panics in `is_less`. - // 2. Fills the remaining hole in `v` in the end. - // - // Panic safety: - // - // If `is_less` panics at any point during the process, `hole` will get dropped and - // fill the hole in `v` with `tmp`, thus ensuring that `v` still holds every object it - // initially held exactly once. - let mut hole = InsertionHole { src: &*tmp, dest: &mut v[1] }; - ptr::copy_nonoverlapping(&v[1], &mut v[0], 1); - - for i in 2..v.len() { - if !is_less(&v[i], &*tmp) { - break; - } - ptr::copy_nonoverlapping(&v[i], &mut v[i - 1], 1); - hole.dest = &mut v[i]; - } - // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`. - } - } - - // When dropped, copies from `src` into `dest`. - struct InsertionHole<T> { - src: *const T, - dest: *mut T, - } - - impl<T> Drop for InsertionHole<T> { - fn drop(&mut self) { - // SAFETY: The caller must ensure that src and dest are correctly set. - unsafe { - ptr::copy_nonoverlapping(self.src, self.dest, 1); - } - } - } -} - /// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `buf` as temporary storage, and /// stores the result into `v[..]`. /// @@ -1180,8 +1182,6 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( { // Slices of up to this length get sorted using insertion sort. const MAX_INSERTION: usize = 20; - // Very short runs are extended using insertion sort to span at least this many elements. - const MIN_RUN: usize = 10; // The caller should have already checked that. debug_assert!(!T::IS_ZST); @@ -1191,9 +1191,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( // Short arrays get sorted in-place via insertion sort to avoid allocations. if len <= MAX_INSERTION { if len >= 2 { - for i in (0..len - 1).rev() { - insert_head(&mut v[i..], is_less); - } + insertion_sort_shift_left(v, 1, is_less); } return; } @@ -1203,59 +1201,43 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( // `is_less` panics. When merging two sorted runs, this buffer holds a copy of the shorter run, // which will always have length at most `len / 2`. let buf = BufGuard::new(len / 2, elem_alloc_fn, elem_dealloc_fn); - let buf_ptr = buf.buf_ptr; + let buf_ptr = buf.buf_ptr.as_ptr(); let mut runs = RunVec::new(run_alloc_fn, run_dealloc_fn); - // In order to identify natural runs in `v`, we traverse it backwards. That might seem like a - // strange decision, but consider the fact that merges more often go in the opposite direction - // (forwards). According to benchmarks, merging forwards is slightly faster than merging - // backwards. To conclude, identifying runs by traversing backwards improves performance. - let mut end = len; - while end > 0 { - // Find the next natural run, and reverse it if it's strictly descending. - let mut start = end - 1; - if start > 0 { - start -= 1; - - // SAFETY: The v.get_unchecked must be fed with correct inbound indicies. - unsafe { - if is_less(v.get_unchecked(start + 1), v.get_unchecked(start)) { - while start > 0 && is_less(v.get_unchecked(start), v.get_unchecked(start - 1)) { - start -= 1; - } - v[start..end].reverse(); - } else { - while start > 0 && !is_less(v.get_unchecked(start), v.get_unchecked(start - 1)) - { - start -= 1; - } - } - } + let mut end = 0; + let mut start = 0; + + // Scan forward. Memory pre-fetching prefers forward scanning vs backwards scanning, and the + // code-gen is usually better. For the most sensitive types such as integers, these are merged + // bidirectionally at once. So there is no benefit in scanning backwards. + while end < len { + let (streak_end, was_reversed) = find_streak(&v[start..], is_less); + end += streak_end; + if was_reversed { + v[start..end].reverse(); } // Insert some more elements into the run if it's too short. Insertion sort is faster than // merge sort on short sequences, so this significantly improves performance. - while start > 0 && end - start < MIN_RUN { - start -= 1; - insert_head(&mut v[start..end], is_less); - } + end = provide_sorted_batch(v, start, end, is_less); // Push this run onto the stack. runs.push(TimSortRun { start, len: end - start }); - end = start; + start = end; // Merge some pairs of adjacent runs to satisfy the invariants. - while let Some(r) = collapse(runs.as_slice()) { - let left = runs[r + 1]; - let right = runs[r]; + while let Some(r) = collapse(runs.as_slice(), len) { + let left = runs[r]; + let right = runs[r + 1]; + let merge_slice = &mut v[left.start..right.start + right.len]; // SAFETY: `buf_ptr` must hold enough capacity for the shorter of the two sides, and // neither side may be on length 0. unsafe { - merge(&mut v[left.start..right.start + right.len], left.len, buf_ptr, is_less); + merge(merge_slice, left.len, buf_ptr, is_less); } - runs[r] = TimSortRun { start: left.start, len: left.len + right.len }; - runs.remove(r + 1); + runs[r + 1] = TimSortRun { start: left.start, len: left.len + right.len }; + runs.remove(r); } } @@ -1277,10 +1259,10 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( // run starts at index 0, it will always demand a merge operation until the stack is fully // collapsed, in order to complete the sort. #[inline] - fn collapse(runs: &[TimSortRun]) -> Option<usize> { + fn collapse(runs: &[TimSortRun], stop: usize) -> Option<usize> { let n = runs.len(); if n >= 2 - && (runs[n - 1].start == 0 + && (runs[n - 1].start + runs[n - 1].len == stop || runs[n - 2].len <= runs[n - 1].len || (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len) || (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len)) @@ -1298,7 +1280,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( where ElemDeallocF: Fn(*mut T, usize), { - buf_ptr: *mut T, + buf_ptr: ptr::NonNull<T>, capacity: usize, elem_dealloc_fn: ElemDeallocF, } @@ -1315,7 +1297,11 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( where ElemAllocF: Fn(usize) -> *mut T, { - Self { buf_ptr: elem_alloc_fn(len), capacity: len, elem_dealloc_fn } + Self { + buf_ptr: ptr::NonNull::new(elem_alloc_fn(len)).unwrap(), + capacity: len, + elem_dealloc_fn, + } } } @@ -1324,7 +1310,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( ElemDeallocF: Fn(*mut T, usize), { fn drop(&mut self) { - (self.elem_dealloc_fn)(self.buf_ptr, self.capacity); + (self.elem_dealloc_fn)(self.buf_ptr.as_ptr(), self.capacity); } } @@ -1333,7 +1319,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( RunAllocF: Fn(usize) -> *mut TimSortRun, RunDeallocF: Fn(*mut TimSortRun, usize), { - buf_ptr: *mut TimSortRun, + buf_ptr: ptr::NonNull<TimSortRun>, capacity: usize, len: usize, run_alloc_fn: RunAllocF, @@ -1350,7 +1336,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( const START_RUN_CAPACITY: usize = 16; Self { - buf_ptr: run_alloc_fn(START_RUN_CAPACITY), + buf_ptr: ptr::NonNull::new(run_alloc_fn(START_RUN_CAPACITY)).unwrap(), capacity: START_RUN_CAPACITY, len: 0, run_alloc_fn, @@ -1361,15 +1347,15 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( fn push(&mut self, val: TimSortRun) { if self.len == self.capacity { let old_capacity = self.capacity; - let old_buf_ptr = self.buf_ptr; + let old_buf_ptr = self.buf_ptr.as_ptr(); self.capacity = self.capacity * 2; - self.buf_ptr = (self.run_alloc_fn)(self.capacity); + self.buf_ptr = ptr::NonNull::new((self.run_alloc_fn)(self.capacity)).unwrap(); // SAFETY: buf_ptr new and old were correctly allocated and old_buf_ptr has // old_capacity valid elements. unsafe { - ptr::copy_nonoverlapping(old_buf_ptr, self.buf_ptr, old_capacity); + ptr::copy_nonoverlapping(old_buf_ptr, self.buf_ptr.as_ptr(), old_capacity); } (self.run_dealloc_fn)(old_buf_ptr, old_capacity); @@ -1377,7 +1363,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( // SAFETY: The invariant was just checked. unsafe { - self.buf_ptr.add(self.len).write(val); + self.buf_ptr.as_ptr().add(self.len).write(val); } self.len += 1; } @@ -1390,7 +1376,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( // SAFETY: buf_ptr needs to be valid and len invariant upheld. unsafe { // the place we are taking from. - let ptr = self.buf_ptr.add(index); + let ptr = self.buf_ptr.as_ptr().add(index); // Shift everything down to fill in that spot. ptr::copy(ptr.add(1), ptr, self.len - index - 1); @@ -1400,7 +1386,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( fn as_slice(&self) -> &[TimSortRun] { // SAFETY: Safe as long as buf_ptr is valid and len invariant was upheld. - unsafe { &*ptr::slice_from_raw_parts(self.buf_ptr, self.len) } + unsafe { &*ptr::slice_from_raw_parts(self.buf_ptr.as_ptr(), self.len) } } fn len(&self) -> usize { @@ -1419,7 +1405,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( if index < self.len { // SAFETY: buf_ptr and len invariant must be upheld. unsafe { - return &*(self.buf_ptr.add(index)); + return &*(self.buf_ptr.as_ptr().add(index)); } } @@ -1436,7 +1422,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( if index < self.len { // SAFETY: buf_ptr and len invariant must be upheld. unsafe { - return &mut *(self.buf_ptr.add(index)); + return &mut *(self.buf_ptr.as_ptr().add(index)); } } @@ -1452,7 +1438,7 @@ pub fn merge_sort<T, CmpF, ElemAllocF, ElemDeallocF, RunAllocF, RunDeallocF>( fn drop(&mut self) { // As long as TimSortRun is Copy we don't need to drop them individually but just the // whole allocation. - (self.run_dealloc_fn)(self.buf_ptr, self.capacity); + (self.run_dealloc_fn)(self.buf_ptr.as_ptr(), self.capacity); } } } @@ -1463,3 +1449,71 @@ pub struct TimSortRun { len: usize, start: usize, } + +/// Takes a range as denoted by start and end, that is already sorted and extends it to the right if +/// necessary with sorts optimized for smaller ranges such as insertion sort. +#[cfg(not(no_global_oom_handling))] +fn provide_sorted_batch<T, F>(v: &mut [T], start: usize, mut end: usize, is_less: &mut F) -> usize +where + F: FnMut(&T, &T) -> bool, +{ + let len = v.len(); + assert!(end >= start && end <= len); + + // This value is a balance between least comparisons and best performance, as + // influenced by for example cache locality. + const MIN_INSERTION_RUN: usize = 10; + + // Insert some more elements into the run if it's too short. Insertion sort is faster than + // merge sort on short sequences, so this significantly improves performance. + let start_end_diff = end - start; + + if start_end_diff < MIN_INSERTION_RUN && end < len { + // v[start_found..end] are elements that are already sorted in the input. We want to extend + // the sorted region to the left, so we push up MIN_INSERTION_RUN - 1 to the right. Which is + // more efficient that trying to push those already sorted elements to the left. + end = cmp::min(start + MIN_INSERTION_RUN, len); + let presorted_start = cmp::max(start_end_diff, 1); + + insertion_sort_shift_left(&mut v[start..end], presorted_start, is_less); + } + + end +} + +/// Finds a streak of presorted elements starting at the beginning of the slice. Returns the first +/// value that is not part of said streak, and a bool denoting wether the streak was reversed. +/// Streaks can be increasing or decreasing. +fn find_streak<T, F>(v: &[T], is_less: &mut F) -> (usize, bool) +where + F: FnMut(&T, &T) -> bool, +{ + let len = v.len(); + + if len < 2 { + return (len, false); + } + + let mut end = 2; + + // SAFETY: See below specific. + unsafe { + // SAFETY: We checked that len >= 2, so 0 and 1 are valid indices. + let assume_reverse = is_less(v.get_unchecked(1), v.get_unchecked(0)); + + // SAFETY: We know end >= 2 and check end < len. + // From that follows that accessing v at end and end - 1 is safe. + if assume_reverse { + while end < len && is_less(v.get_unchecked(end), v.get_unchecked(end - 1)) { + end += 1; + } + + (end, true) + } else { + while end < len && !is_less(v.get_unchecked(end), v.get_unchecked(end - 1)) { + end += 1; + } + (end, false) + } + } +} diff --git a/library/core/src/str/iter.rs b/library/core/src/str/iter.rs index d969475aa48..95c682f42d0 100644 --- a/library/core/src/str/iter.rs +++ b/library/core/src/str/iter.rs @@ -1,6 +1,6 @@ //! Iterators for `str` methods. -use crate::char; +use crate::char as char_mod; use crate::fmt::{self, Write}; use crate::iter::{Chain, FlatMap, Flatten}; use crate::iter::{Copied, Filter, FusedIterator, Map, TrustedLen}; @@ -1455,8 +1455,8 @@ impl FusedIterator for EncodeUtf16<'_> {} #[derive(Clone, Debug)] pub struct EscapeDebug<'a> { pub(super) inner: Chain< - Flatten<option::IntoIter<char::EscapeDebug>>, - FlatMap<Chars<'a>, char::EscapeDebug, CharEscapeDebugContinue>, + Flatten<option::IntoIter<char_mod::EscapeDebug>>, + FlatMap<Chars<'a>, char_mod::EscapeDebug, CharEscapeDebugContinue>, >, } @@ -1464,14 +1464,14 @@ pub struct EscapeDebug<'a> { #[stable(feature = "str_escape", since = "1.34.0")] #[derive(Clone, Debug)] pub struct EscapeDefault<'a> { - pub(super) inner: FlatMap<Chars<'a>, char::EscapeDefault, CharEscapeDefault>, + pub(super) inner: FlatMap<Chars<'a>, char_mod::EscapeDefault, CharEscapeDefault>, } /// The return type of [`str::escape_unicode`]. #[stable(feature = "str_escape", since = "1.34.0")] #[derive(Clone, Debug)] pub struct EscapeUnicode<'a> { - pub(super) inner: FlatMap<Chars<'a>, char::EscapeUnicode, CharEscapeUnicode>, + pub(super) inner: FlatMap<Chars<'a>, char_mod::EscapeUnicode, CharEscapeUnicode>, } macro_rules! escape_types_impls { diff --git a/library/core/tests/array.rs b/library/core/tests/array.rs index f268fe3ae7b..5327e4f8139 100644 --- a/library/core/tests/array.rs +++ b/library/core/tests/array.rs @@ -700,3 +700,28 @@ fn array_into_iter_rfold() { let s = it.rfold(10, |a, b| 10 * a + b); assert_eq!(s, 10432); } + +#[cfg(not(panic = "abort"))] +#[test] +fn array_map_drops_unmapped_elements_on_panic() { + struct DropCounter<'a>(usize, &'a AtomicUsize); + impl Drop for DropCounter<'_> { + fn drop(&mut self) { + self.1.fetch_add(1, Ordering::SeqCst); + } + } + + const MAX: usize = 11; + for panic_after in 0..MAX { + let counter = AtomicUsize::new(0); + let a = array::from_fn::<_, 11, _>(|i| DropCounter(i, &counter)); + let success = std::panic::catch_unwind(|| { + let _ = a.map(|x| { + assert!(x.0 < panic_after); + assert_eq!(counter.load(Ordering::SeqCst), x.0); + }); + }); + assert!(success.is_err()); + assert_eq!(counter.load(Ordering::SeqCst), MAX); + } +} diff --git a/library/core/tests/iter/range.rs b/library/core/tests/iter/range.rs index 84498a8eae5..0f91ffe2dfc 100644 --- a/library/core/tests/iter/range.rs +++ b/library/core/tests/iter/range.rs @@ -26,7 +26,6 @@ fn test_range() { #[test] fn test_char_range() { - use std::char; // Miri is too slow let from = if cfg!(miri) { char::from_u32(0xD800 - 10).unwrap() } else { '\0' }; let to = if cfg!(miri) { char::from_u32(0xDFFF + 10).unwrap() } else { char::MAX }; diff --git a/library/core/tests/iter/traits/iterator.rs b/library/core/tests/iter/traits/iterator.rs index 37345c1d381..62566a9502d 100644 --- a/library/core/tests/iter/traits/iterator.rs +++ b/library/core/tests/iter/traits/iterator.rs @@ -582,6 +582,9 @@ fn test_next_chunk() { assert_eq!(it.next_chunk().unwrap(), []); assert_eq!(it.next_chunk().unwrap(), [4, 5, 6, 7, 8, 9]); assert_eq!(it.next_chunk::<4>().unwrap_err().as_slice(), &[10, 11]); + + let mut it = std::iter::repeat_with(|| panic!()); + assert_eq!(it.next_chunk::<0>().unwrap(), []); } // just tests by whether or not this compiles diff --git a/library/core/tests/ptr.rs b/library/core/tests/ptr.rs index 80d30f14c66..c02cd99cc44 100644 --- a/library/core/tests/ptr.rs +++ b/library/core/tests/ptr.rs @@ -25,7 +25,7 @@ fn test() { snd: isize, } let mut p = Pair { fst: 10, snd: 20 }; - let pptr: *mut Pair = &mut p; + let pptr: *mut Pair = addr_of_mut!(p); let iptr: *mut isize = pptr as *mut isize; assert_eq!(*iptr, 10); *iptr = 30; @@ -1070,8 +1070,8 @@ fn swap_copy_untyped() { let mut x = 5u8; let mut y = 6u8; - let ptr1 = &mut x as *mut u8 as *mut bool; - let ptr2 = &mut y as *mut u8 as *mut bool; + let ptr1 = addr_of_mut!(x).cast::<bool>(); + let ptr2 = addr_of_mut!(y).cast::<bool>(); unsafe { ptr::swap(ptr1, ptr2); diff --git a/library/proc_macro/src/bridge/rpc.rs b/library/proc_macro/src/bridge/rpc.rs index e9d7a46c06f..5b1bfb30983 100644 --- a/library/proc_macro/src/bridge/rpc.rs +++ b/library/proc_macro/src/bridge/rpc.rs @@ -1,7 +1,6 @@ //! Serialization for client-server communication. use std::any::Any; -use std::char; use std::io::Write; use std::num::NonZeroU32; use std::str; diff --git a/library/std/Cargo.toml b/library/std/Cargo.toml index adf521d9b94..349cd91c89e 100644 --- a/library/std/Cargo.toml +++ b/library/std/Cargo.toml @@ -16,7 +16,7 @@ panic_unwind = { path = "../panic_unwind", optional = true } panic_abort = { path = "../panic_abort" } core = { path = "../core" } libc = { version = "0.2.138", default-features = false, features = ['rustc-dep-of-std'] } -compiler_builtins = { version = "0.1.85" } +compiler_builtins = { version = "0.1.87" } profiler_builtins = { path = "../profiler_builtins", optional = true } unwind = { path = "../unwind" } hashbrown = { version = "0.12", default-features = false, features = ['rustc-dep-of-std'] } diff --git a/library/std/src/sys/hermit/mod.rs b/library/std/src/sys/hermit/mod.rs index 6811fadb018..20fd3dd8f09 100644 --- a/library/std/src/sys/hermit/mod.rs +++ b/library/std/src/sys/hermit/mod.rs @@ -72,11 +72,6 @@ pub fn unsupported_err() -> crate::io::Error { ) } -#[no_mangle] -pub extern "C" fn floor(x: f64) -> f64 { - unsafe { intrinsics::floorf64(x) } -} - pub fn abort_internal() -> ! { unsafe { abi::abort(); diff --git a/library/std/src/sys/unix/args.rs b/library/std/src/sys/unix/args.rs index a342f0f5e85..a5ce6d5120d 100644 --- a/library/std/src/sys/unix/args.rs +++ b/library/std/src/sys/unix/args.rs @@ -141,12 +141,28 @@ mod imp { // list. let argv = ARGV.load(Ordering::Relaxed); let argc = if argv.is_null() { 0 } else { ARGC.load(Ordering::Relaxed) }; - (0..argc) - .map(|i| { - let cstr = CStr::from_ptr(*argv.offset(i) as *const libc::c_char); - OsStringExt::from_vec(cstr.to_bytes().to_vec()) - }) - .collect() + let mut args = Vec::with_capacity(argc as usize); + for i in 0..argc { + let ptr = *argv.offset(i) as *const libc::c_char; + + // Some C commandline parsers (e.g. GLib and Qt) are replacing already + // handled arguments in `argv` with `NULL` and move them to the end. That + // means that `argc` might be bigger than the actual number of non-`NULL` + // pointers in `argv` at this point. + // + // To handle this we simply stop iterating at the first `NULL` argument. + // + // `argv` is also guaranteed to be `NULL`-terminated so any non-`NULL` arguments + // after the first `NULL` can safely be ignored. + if ptr.is_null() { + break; + } + + let cstr = CStr::from_ptr(ptr); + args.push(OsStringExt::from_vec(cstr.to_bytes().to_vec())); + } + + args } } } diff --git a/library/std/src/sys/wasi/os.rs b/library/std/src/sys/wasi/os.rs index f5513e9996d..9919dc7087e 100644 --- a/library/std/src/sys/wasi/os.rs +++ b/library/std/src/sys/wasi/os.rs @@ -21,6 +21,7 @@ mod libc { extern "C" { pub fn getcwd(buf: *mut c_char, size: size_t) -> *mut c_char; pub fn chdir(dir: *const c_char) -> c_int; + pub fn __wasilibc_get_environ() -> *mut *mut c_char; } } @@ -161,7 +162,12 @@ impl Iterator for Env { pub fn env() -> Env { unsafe { let _guard = env_read_lock(); - let mut environ = libc::environ; + + // Use `__wasilibc_get_environ` instead of `environ` here so that we + // don't require wasi-libc to eagerly initialize the environment + // variables. + let mut environ = libc::__wasilibc_get_environ(); + let mut result = Vec::new(); if !environ.is_null() { while !(*environ).is_null() { diff --git a/library/std/src/sys/windows/c.rs b/library/std/src/sys/windows/c.rs index 81461de4f72..f58dcf1287b 100644 --- a/library/std/src/sys/windows/c.rs +++ b/library/std/src/sys/windows/c.rs @@ -295,8 +295,6 @@ pub fn nt_success(status: NTSTATUS) -> bool { status >= 0 } -// "RNG\0" -pub const BCRYPT_RNG_ALGORITHM: &[u16] = &[b'R' as u16, b'N' as u16, b'G' as u16, 0]; pub const BCRYPT_USE_SYSTEM_PREFERRED_RNG: DWORD = 0x00000002; #[repr(C)] @@ -834,6 +832,10 @@ if #[cfg(not(target_vendor = "uwp"))] { #[link(name = "advapi32")] extern "system" { + // Forbidden when targeting UWP + #[link_name = "SystemFunction036"] + pub fn RtlGenRandom(RandomBuffer: *mut u8, RandomBufferLength: ULONG) -> BOOLEAN; + // Allowed but unused by UWP pub fn OpenProcessToken( ProcessHandle: HANDLE, @@ -1258,13 +1260,6 @@ extern "system" { cbBuffer: ULONG, dwFlags: ULONG, ) -> NTSTATUS; - pub fn BCryptOpenAlgorithmProvider( - phalgorithm: *mut BCRYPT_ALG_HANDLE, - pszAlgId: LPCWSTR, - pszimplementation: LPCWSTR, - dwflags: ULONG, - ) -> NTSTATUS; - pub fn BCryptCloseAlgorithmProvider(hAlgorithm: BCRYPT_ALG_HANDLE, dwFlags: ULONG) -> NTSTATUS; } // Functions that aren't available on every version of Windows that we support, diff --git a/library/std/src/sys/windows/fs.rs b/library/std/src/sys/windows/fs.rs index 37809803828..d2c597664fa 100644 --- a/library/std/src/sys/windows/fs.rs +++ b/library/std/src/sys/windows/fs.rs @@ -1266,7 +1266,12 @@ fn metadata(path: &Path, reparse: ReparsePoint) -> io::Result<FileAttr> { // If the fallback fails for any reason we return the original error. match File::open(path, &opts) { Ok(file) => file.file_attr(), - Err(e) if e.raw_os_error() == Some(c::ERROR_SHARING_VIOLATION as _) => { + Err(e) + if [Some(c::ERROR_SHARING_VIOLATION as _), Some(c::ERROR_ACCESS_DENIED as _)] + .contains(&e.raw_os_error()) => + { + // `ERROR_ACCESS_DENIED` is returned when the user doesn't have permission for the resource. + // One such example is `System Volume Information` as default but can be created as well // `ERROR_SHARING_VIOLATION` will almost never be returned. // Usually if a file is locked you can still read some metadata. // However, there are special system files, such as @@ -1393,6 +1398,8 @@ fn symlink_junction_inner(original: &Path, junction: &Path) -> io::Result<()> { let mut data = Align8([MaybeUninit::<u8>::uninit(); c::MAXIMUM_REPARSE_DATA_BUFFER_SIZE]); let data_ptr = data.0.as_mut_ptr(); let db = data_ptr.cast::<c::REPARSE_MOUNTPOINT_DATA_BUFFER>(); + // Zero the header to ensure it's fully initialized, including reserved parameters. + *db = mem::zeroed(); let buf = ptr::addr_of_mut!((*db).ReparseTarget).cast::<c::WCHAR>(); let mut i = 0; // FIXME: this conversion is very hacky diff --git a/library/std/src/sys/windows/rand.rs b/library/std/src/sys/windows/rand.rs index b5a49489d3f..cdf37cfe911 100644 --- a/library/std/src/sys/windows/rand.rs +++ b/library/std/src/sys/windows/rand.rs @@ -1,106 +1,39 @@ -//! # Random key generation -//! -//! This module wraps the RNG provided by the OS. There are a few different -//! ways to interface with the OS RNG so it's worth exploring each of the options. -//! Note that at the time of writing these all go through the (undocumented) -//! `bcryptPrimitives.dll` but they use different route to get there. -//! -//! Originally we were using [`RtlGenRandom`], however that function is -//! deprecated and warns it "may be altered or unavailable in subsequent versions". -//! -//! So we switched to [`BCryptGenRandom`] with the `BCRYPT_USE_SYSTEM_PREFERRED_RNG` -//! flag to query and find the system configured RNG. However, this change caused a small -//! but significant number of users to experience panics caused by a failure of -//! this function. See [#94098]. -//! -//! The current version falls back to using `BCryptOpenAlgorithmProvider` if -//! `BCRYPT_USE_SYSTEM_PREFERRED_RNG` fails for any reason. -//! -//! [#94098]: https://github.com/rust-lang/rust/issues/94098 -//! [`RtlGenRandom`]: https://docs.microsoft.com/en-us/windows/win32/api/ntsecapi/nf-ntsecapi-rtlgenrandom -//! [`BCryptGenRandom`]: https://docs.microsoft.com/en-us/windows/win32/api/bcrypt/nf-bcrypt-bcryptgenrandom +use crate::io; use crate::mem; use crate::ptr; use crate::sys::c; -/// Generates high quality secure random keys for use by [`HashMap`]. -/// -/// This is used to seed the default [`RandomState`]. -/// -/// [`HashMap`]: crate::collections::HashMap -/// [`RandomState`]: crate::collections::hash_map::RandomState pub fn hashmap_random_keys() -> (u64, u64) { - Rng::SYSTEM.gen_random_keys().unwrap_or_else(fallback_rng) + let mut v = (0, 0); + let ret = unsafe { + c::BCryptGenRandom( + ptr::null_mut(), + &mut v as *mut _ as *mut u8, + mem::size_of_val(&v) as c::ULONG, + c::BCRYPT_USE_SYSTEM_PREFERRED_RNG, + ) + }; + if c::nt_success(ret) { v } else { fallback_rng() } } -struct Rng { - algorithm: c::BCRYPT_ALG_HANDLE, - flags: u32, -} -impl Rng { - const SYSTEM: Self = unsafe { Self::new(ptr::null_mut(), c::BCRYPT_USE_SYSTEM_PREFERRED_RNG) }; - - /// Create the RNG from an existing algorithm handle. - /// - /// # Safety - /// - /// The handle must either be null or a valid algorithm handle. - const unsafe fn new(algorithm: c::BCRYPT_ALG_HANDLE, flags: u32) -> Self { - Self { algorithm, flags } - } - - /// Open a handle to the RNG algorithm. - fn open() -> Result<Self, c::NTSTATUS> { - use crate::sync::atomic::AtomicPtr; - use crate::sync::atomic::Ordering::{Acquire, Release}; - - // An atomic is used so we don't need to reopen the handle every time. - static HANDLE: AtomicPtr<crate::ffi::c_void> = AtomicPtr::new(ptr::null_mut()); - - let mut handle = HANDLE.load(Acquire); - if handle.is_null() { - let status = unsafe { - c::BCryptOpenAlgorithmProvider( - &mut handle, - c::BCRYPT_RNG_ALGORITHM.as_ptr(), - ptr::null(), - 0, - ) - }; - if c::nt_success(status) { - // If another thread opens a handle first then use that handle instead. - let result = HANDLE.compare_exchange(ptr::null_mut(), handle, Release, Acquire); - if let Err(previous_handle) = result { - // Close our handle and return the previous one. - unsafe { c::BCryptCloseAlgorithmProvider(handle, 0) }; - handle = previous_handle; - } - Ok(unsafe { Self::new(handle, 0) }) - } else { - Err(status) - } - } else { - Ok(unsafe { Self::new(handle, 0) }) - } - } +/// Generate random numbers using the fallback RNG function (RtlGenRandom) +/// +/// This is necessary because of a failure to load the SysWOW64 variant of the +/// bcryptprimitives.dll library from code that lives in bcrypt.dll +/// See <https://bugzilla.mozilla.org/show_bug.cgi?id=1788004#c9> +#[cfg(not(target_vendor = "uwp"))] +#[inline(never)] +fn fallback_rng() -> (u64, u64) { + let mut v = (0, 0); + let ret = + unsafe { c::RtlGenRandom(&mut v as *mut _ as *mut u8, mem::size_of_val(&v) as c::ULONG) }; - fn gen_random_keys(self) -> Result<(u64, u64), c::NTSTATUS> { - let mut v = (0, 0); - let status = unsafe { - let size = mem::size_of_val(&v).try_into().unwrap(); - c::BCryptGenRandom(self.algorithm, ptr::addr_of_mut!(v).cast(), size, self.flags) - }; - if c::nt_success(status) { Ok(v) } else { Err(status) } - } + if ret != 0 { v } else { panic!("fallback RNG broken: {}", io::Error::last_os_error()) } } -/// Generate random numbers using the fallback RNG function +/// We can't use RtlGenRandom with UWP, so there is no fallback +#[cfg(target_vendor = "uwp")] #[inline(never)] -fn fallback_rng(rng_status: c::NTSTATUS) -> (u64, u64) { - match Rng::open().and_then(|rng| rng.gen_random_keys()) { - Ok(keys) => keys, - Err(status) => { - panic!("RNG broken: {rng_status:#x}, fallback RNG broken: {status:#x}") - } - } +fn fallback_rng() -> (u64, u64) { + panic!("fallback RNG broken: RtlGenRandom() not supported on UWP"); } diff --git a/library/std/src/sys/windows/stdio.rs b/library/std/src/sys/windows/stdio.rs index 70c9b14a08f..c2cd48470bd 100644 --- a/library/std/src/sys/windows/stdio.rs +++ b/library/std/src/sys/windows/stdio.rs @@ -1,6 +1,5 @@ #![unstable(issue = "none", feature = "windows_stdio")] -use crate::char::decode_utf16; use crate::cmp; use crate::io; use crate::mem::MaybeUninit; @@ -369,7 +368,7 @@ fn read_u16s(handle: c::HANDLE, buf: &mut [MaybeUninit<u16>]) -> io::Result<usiz #[allow(unused)] fn utf16_to_utf8(utf16: &[u16], utf8: &mut [u8]) -> io::Result<usize> { let mut written = 0; - for chr in decode_utf16(utf16.iter().cloned()) { + for chr in char::decode_utf16(utf16.iter().cloned()) { match chr { Ok(chr) => { chr.encode_utf8(&mut utf8[written..]); diff --git a/library/std/src/sys_common/wtf8.rs b/library/std/src/sys_common/wtf8.rs index dd53767d452..e202d17e1c2 100644 --- a/library/std/src/sys_common/wtf8.rs +++ b/library/std/src/sys_common/wtf8.rs @@ -18,10 +18,10 @@ #[cfg(test)] mod tests; +use core::char::{encode_utf16_raw, encode_utf8_raw}; use core::str::next_code_point; use crate::borrow::Cow; -use crate::char; use crate::collections::TryReserveError; use crate::fmt; use crate::hash::{Hash, Hasher}; @@ -235,7 +235,7 @@ impl Wtf8Buf { /// This does **not** include the WTF-8 concatenation check or `is_known_utf8` check. fn push_code_point_unchecked(&mut self, code_point: CodePoint) { let mut bytes = [0; 4]; - let bytes = char::encode_utf8_raw(code_point.value, &mut bytes); + let bytes = encode_utf8_raw(code_point.value, &mut bytes); self.bytes.extend_from_slice(bytes) } @@ -939,7 +939,7 @@ impl<'a> Iterator for EncodeWide<'a> { let mut buf = [0; 2]; self.code_points.next().map(|code_point| { - let n = char::encode_utf16_raw(code_point.value, &mut buf).len(); + let n = encode_utf16_raw(code_point.value, &mut buf).len(); if n == 2 { self.extra = buf[1]; } |