From 20431706a863f92cb37dc512fef6e48d192aaf2c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Wed, 17 Apr 2024 14:11:38 +0200 Subject: Merging upstream version 1.66.0+dfsg1. Signed-off-by: Daniel Baumann --- library/core/src/slice/index.rs | 104 +++++++++++++++++++++++++-- library/core/src/slice/iter.rs | 21 +++--- library/core/src/slice/iter/macros.rs | 8 +-- library/core/src/slice/memchr.rs | 4 +- library/core/src/slice/mod.rs | 132 +++++++++++++++++++++++----------- library/core/src/slice/raw.rs | 42 ++++++++--- library/core/src/slice/rotate.rs | 4 +- library/core/src/slice/sort.rs | 6 +- 8 files changed, 243 insertions(+), 78 deletions(-) (limited to 'library/core/src/slice') diff --git a/library/core/src/slice/index.rs b/library/core/src/slice/index.rs index 3403a5a86..6d2f7330d 100644 --- a/library/core/src/slice/index.rs +++ b/library/core/src/slice/index.rs @@ -139,6 +139,8 @@ mod private_slice_index { impl Sealed for ops::RangeToInclusive {} #[stable(feature = "slice_index_with_ops_bound_pair", since = "1.53.0")] impl Sealed for (ops::Bound, ops::Bound) {} + + impl Sealed for ops::IndexRange {} } /// A helper trait used for indexing operations. @@ -158,6 +160,7 @@ mod private_slice_index { message = "the type `{T}` cannot be indexed by `{Self}`", label = "slice indices are of type `usize` or ranges of `usize`" )] +#[const_trait] pub unsafe trait SliceIndex: private_slice_index::Sealed { /// The output type returned by methods. #[stable(feature = "slice_get_slice", since = "1.28.0")] @@ -229,7 +232,10 @@ unsafe impl const SliceIndex<[T]> for usize { // `self` is in bounds of `slice` so `self` cannot overflow an `isize`, // so the call to `add` is safe. unsafe { - assert_unsafe_precondition!([T](this: usize, slice: *const [T]) => this < slice.len()); + assert_unsafe_precondition!( + "slice::get_unchecked requires that the index is within the slice", + [T](this: usize, slice: *const [T]) => this < slice.len() + ); slice.as_ptr().add(self) } } @@ -239,7 +245,10 @@ unsafe impl const SliceIndex<[T]> for usize { let this = self; // SAFETY: see comments for `get_unchecked` above. unsafe { - assert_unsafe_precondition!([T](this: usize, slice: *mut [T]) => this < slice.len()); + assert_unsafe_precondition!( + "slice::get_unchecked_mut requires that the index is within the slice", + [T](this: usize, slice: *mut [T]) => this < slice.len() + ); slice.as_mut_ptr().add(self) } } @@ -257,6 +266,83 @@ unsafe impl const SliceIndex<[T]> for usize { } } +/// Because `IndexRange` guarantees `start <= end`, fewer checks are needed here +/// than there are for a general `Range` (which might be `100..3`). +#[rustc_const_unstable(feature = "const_index_range_slice_index", issue = "none")] +unsafe impl const SliceIndex<[T]> for ops::IndexRange { + type Output = [T]; + + #[inline] + fn get(self, slice: &[T]) -> Option<&[T]> { + if self.end() <= slice.len() { + // SAFETY: `self` is checked to be valid and in bounds above. + unsafe { Some(&*self.get_unchecked(slice)) } + } else { + None + } + } + + #[inline] + fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> { + if self.end() <= slice.len() { + // SAFETY: `self` is checked to be valid and in bounds above. + unsafe { Some(&mut *self.get_unchecked_mut(slice)) } + } else { + None + } + } + + #[inline] + unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] { + let end = self.end(); + // SAFETY: the caller guarantees that `slice` is not dangling, so it + // cannot be longer than `isize::MAX`. They also guarantee that + // `self` is in bounds of `slice` so `self` cannot overflow an `isize`, + // so the call to `add` is safe. + + unsafe { + assert_unsafe_precondition!( + "slice::get_unchecked requires that the index is within the slice", + [T](end: usize, slice: *const [T]) => end <= slice.len() + ); + ptr::slice_from_raw_parts(slice.as_ptr().add(self.start()), self.len()) + } + } + + #[inline] + unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] { + let end = self.end(); + // SAFETY: see comments for `get_unchecked` above. + unsafe { + assert_unsafe_precondition!( + "slice::get_unchecked_mut requires that the index is within the slice", + [T](end: usize, slice: *mut [T]) => end <= slice.len() + ); + ptr::slice_from_raw_parts_mut(slice.as_mut_ptr().add(self.start()), self.len()) + } + } + + #[inline] + fn index(self, slice: &[T]) -> &[T] { + if self.end() <= slice.len() { + // SAFETY: `self` is checked to be valid and in bounds above. + unsafe { &*self.get_unchecked(slice) } + } else { + slice_end_index_len_fail(self.end(), slice.len()) + } + } + + #[inline] + fn index_mut(self, slice: &mut [T]) -> &mut [T] { + if self.end() <= slice.len() { + // SAFETY: `self` is checked to be valid and in bounds above. + unsafe { &mut *self.get_unchecked_mut(slice) } + } else { + slice_end_index_len_fail(self.end(), slice.len()) + } + } +} + #[stable(feature = "slice_get_slice_impls", since = "1.15.0")] #[rustc_const_unstable(feature = "const_slice_index", issue = "none")] unsafe impl const SliceIndex<[T]> for ops::Range { @@ -291,8 +377,11 @@ unsafe impl const SliceIndex<[T]> for ops::Range { // so the call to `add` is safe. unsafe { - assert_unsafe_precondition!([T](this: ops::Range, slice: *const [T]) => - this.end >= this.start && this.end <= slice.len()); + assert_unsafe_precondition!( + "slice::get_unchecked requires that the range is within the slice", + [T](this: ops::Range, slice: *const [T]) => + this.end >= this.start && this.end <= slice.len() + ); ptr::slice_from_raw_parts(slice.as_ptr().add(self.start), self.end - self.start) } } @@ -302,8 +391,11 @@ unsafe impl const SliceIndex<[T]> for ops::Range { let this = ops::Range { start: self.start, end: self.end }; // SAFETY: see comments for `get_unchecked` above. unsafe { - assert_unsafe_precondition!([T](this: ops::Range, slice: *mut [T]) => - this.end >= this.start && this.end <= slice.len()); + assert_unsafe_precondition!( + "slice::get_unchecked_mut requires that the range is within the slice", + [T](this: ops::Range, slice: *mut [T]) => + this.end >= this.start && this.end <= slice.len() + ); ptr::slice_from_raw_parts_mut(slice.as_mut_ptr().add(self.start), self.end - self.start) } } diff --git a/library/core/src/slice/iter.rs b/library/core/src/slice/iter.rs index 395c56784..8a8962828 100644 --- a/library/core/src/slice/iter.rs +++ b/library/core/src/slice/iter.rs @@ -9,7 +9,7 @@ use crate::fmt; use crate::intrinsics::{assume, exact_div, unchecked_sub}; use crate::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce}; use crate::marker::{PhantomData, Send, Sized, Sync}; -use crate::mem; +use crate::mem::{self, SizedTypeProperties}; use crate::num::NonZeroUsize; use crate::ptr::NonNull; @@ -91,11 +91,8 @@ impl<'a, T> Iter<'a, T> { unsafe { assume(!ptr.is_null()); - let end = if mem::size_of::() == 0 { - ptr.wrapping_byte_add(slice.len()) - } else { - ptr.add(slice.len()) - }; + let end = + if T::IS_ZST { ptr.wrapping_byte_add(slice.len()) } else { ptr.add(slice.len()) }; Self { ptr: NonNull::new_unchecked(ptr as *mut T), end, _marker: PhantomData } } @@ -127,6 +124,7 @@ impl<'a, T> Iter<'a, T> { /// ``` #[must_use] #[stable(feature = "iter_to_slice", since = "1.4.0")] + #[inline] pub fn as_slice(&self) -> &'a [T] { self.make_slice() } @@ -146,6 +144,7 @@ iterator! {struct Iter -> *const T, &'a T, const, {/* no mut */}, { #[stable(feature = "rust1", since = "1.0.0")] impl Clone for Iter<'_, T> { + #[inline] fn clone(&self) -> Self { Iter { ptr: self.ptr, end: self.end, _marker: self._marker } } @@ -153,6 +152,7 @@ impl Clone for Iter<'_, T> { #[stable(feature = "slice_iter_as_ref", since = "1.13.0")] impl AsRef<[T]> for Iter<'_, T> { + #[inline] fn as_ref(&self) -> &[T] { self.as_slice() } @@ -227,11 +227,8 @@ impl<'a, T> IterMut<'a, T> { unsafe { assume(!ptr.is_null()); - let end = if mem::size_of::() == 0 { - ptr.wrapping_byte_add(slice.len()) - } else { - ptr.add(slice.len()) - }; + let end = + if T::IS_ZST { ptr.wrapping_byte_add(slice.len()) } else { ptr.add(slice.len()) }; Self { ptr: NonNull::new_unchecked(ptr), end, _marker: PhantomData } } @@ -303,6 +300,7 @@ impl<'a, T> IterMut<'a, T> { /// ``` #[must_use] #[stable(feature = "slice_iter_mut_as_slice", since = "1.53.0")] + #[inline] pub fn as_slice(&self) -> &[T] { self.make_slice() } @@ -351,6 +349,7 @@ impl<'a, T> IterMut<'a, T> { #[stable(feature = "slice_iter_mut_as_slice", since = "1.53.0")] impl AsRef<[T]> for IterMut<'_, T> { + #[inline] fn as_ref(&self) -> &[T] { self.as_slice() } diff --git a/library/core/src/slice/iter/macros.rs b/library/core/src/slice/iter/macros.rs index 6c9e7574e..ce51d48e3 100644 --- a/library/core/src/slice/iter/macros.rs +++ b/library/core/src/slice/iter/macros.rs @@ -100,7 +100,7 @@ macro_rules! iterator { // Unsafe because the offset must not exceed `self.len()`. #[inline(always)] unsafe fn pre_dec_end(&mut self, offset: usize) -> * $raw_mut T { - if mem::size_of::() == 0 { + if T::IS_ZST { zst_shrink!(self, offset); self.ptr.as_ptr() } else { @@ -140,7 +140,7 @@ macro_rules! iterator { // since we check if the iterator is empty first. unsafe { assume(!self.ptr.as_ptr().is_null()); - if mem::size_of::() != 0 { + if !::IS_ZST { assume(!self.end.is_null()); } if is_empty!(self) { @@ -166,7 +166,7 @@ macro_rules! iterator { fn nth(&mut self, n: usize) -> Option<$elem> { if n >= len!(self) { // This iterator is now empty. - if mem::size_of::() == 0 { + if T::IS_ZST { // We have to do it this way as `ptr` may never be 0, but `end` // could be (due to wrapping). self.end = self.ptr.as_ptr(); @@ -355,7 +355,7 @@ macro_rules! iterator { // empty first. unsafe { assume(!self.ptr.as_ptr().is_null()); - if mem::size_of::() != 0 { + if !::IS_ZST { assume(!self.end.is_null()); } if is_empty!(self) { diff --git a/library/core/src/slice/memchr.rs b/library/core/src/slice/memchr.rs index 7de1f48e6..c848c2e18 100644 --- a/library/core/src/slice/memchr.rs +++ b/library/core/src/slice/memchr.rs @@ -141,8 +141,8 @@ pub fn memrchr(x: u8, text: &[u8]) -> Option { // SAFETY: offset starts at len - suffix.len(), as long as it is greater than // min_aligned_offset (prefix.len()) the remaining distance is at least 2 * chunk_bytes. unsafe { - let u = *(ptr.offset(offset as isize - 2 * chunk_bytes as isize) as *const Chunk); - let v = *(ptr.offset(offset as isize - chunk_bytes as isize) as *const Chunk); + let u = *(ptr.add(offset - 2 * chunk_bytes) as *const Chunk); + let v = *(ptr.add(offset - chunk_bytes) as *const Chunk); // Break if there is a matching byte. let zu = contains_zero_byte(u ^ repeated_x); diff --git a/library/core/src/slice/mod.rs b/library/core/src/slice/mod.rs index 6a7150d29..4f1bb1734 100644 --- a/library/core/src/slice/mod.rs +++ b/library/core/src/slice/mod.rs @@ -9,7 +9,7 @@ use crate::cmp::Ordering::{self, Greater, Less}; use crate::intrinsics::{assert_unsafe_precondition, exact_div}; use crate::marker::Copy; -use crate::mem; +use crate::mem::{self, SizedTypeProperties}; use crate::num::NonZeroUsize; use crate::ops::{Bound, FnMut, OneSidedRange, Range, RangeBounds}; use crate::option::Option; @@ -123,18 +123,11 @@ impl [T] { #[lang = "slice_len_fn"] #[stable(feature = "rust1", since = "1.0.0")] #[rustc_const_stable(feature = "const_slice_len", since = "1.39.0")] + #[rustc_allow_const_fn_unstable(ptr_metadata)] #[inline] #[must_use] - // SAFETY: const sound because we transmute out the length field as a usize (which it must be) pub const fn len(&self) -> usize { - // FIXME: Replace with `crate::ptr::metadata(self)` when that is const-stable. - // As of this writing this causes a "Const-stable functions can only call other - // const-stable functions" error. - - // SAFETY: Accessing the value from the `PtrRepr` union is safe since *const T - // and PtrComponents have the same memory layouts. Only std can make this - // guarantee. - unsafe { crate::ptr::PtrRepr { const_ptr: self }.components.metadata } + ptr::metadata(self) } /// Returns `true` if the slice has a length of 0. @@ -660,7 +653,10 @@ impl [T] { let ptr = this.as_mut_ptr(); // SAFETY: caller has to guarantee that `a < self.len()` and `b < self.len()` unsafe { - assert_unsafe_precondition!([T](a: usize, b: usize, this: &mut [T]) => a < this.len() && b < this.len()); + assert_unsafe_precondition!( + "slice::swap_unchecked requires that the indices are within the slice", + [T](a: usize, b: usize, this: &mut [T]) => a < this.len() && b < this.len() + ); ptr::swap(ptr.add(a), ptr.add(b)); } } @@ -976,7 +972,10 @@ impl [T] { let this = self; // SAFETY: Caller must guarantee that `N` is nonzero and exactly divides the slice length let new_len = unsafe { - assert_unsafe_precondition!([T](this: &[T], N: usize) => N != 0 && this.len() % N == 0); + assert_unsafe_precondition!( + "slice::as_chunks_unchecked requires `N != 0` and the slice to split exactly into `N`-element chunks", + [T](this: &[T], N: usize) => N != 0 && this.len() % N == 0 + ); exact_div(self.len(), N) }; // SAFETY: We cast a slice of `new_len * N` elements into @@ -1116,7 +1115,10 @@ impl [T] { let this = &*self; // SAFETY: Caller must guarantee that `N` is nonzero and exactly divides the slice length let new_len = unsafe { - assert_unsafe_precondition!([T](this: &[T], N: usize) => N != 0 && this.len() % N == 0); + assert_unsafe_precondition!( + "slice::as_chunks_unchecked_mut requires `N != 0` and the slice to split exactly into `N`-element chunks", + [T](this: &[T], N: usize) => N != 0 && this.len() % N == 0 + ); exact_div(this.len(), N) }; // SAFETY: We cast a slice of `new_len * N` elements into @@ -1580,7 +1582,8 @@ impl [T] { #[inline] #[track_caller] #[must_use] - pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) { + #[rustc_const_unstable(feature = "const_slice_split_at_mut", issue = "101804")] + pub const fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) { assert!(mid <= self.len()); // SAFETY: `[ptr; mid]` and `[mid; len]` are inside `self`, which // fulfills the requirements of `from_raw_parts_mut`. @@ -1679,9 +1682,10 @@ impl [T] { /// assert_eq!(v, [1, 2, 3, 4, 5, 6]); /// ``` #[unstable(feature = "slice_split_at_unchecked", reason = "new API", issue = "76014")] + #[rustc_const_unstable(feature = "const_slice_split_at_mut", issue = "101804")] #[inline] #[must_use] - pub unsafe fn split_at_mut_unchecked(&mut self, mid: usize) -> (&mut [T], &mut [T]) { + pub const unsafe fn split_at_mut_unchecked(&mut self, mid: usize) -> (&mut [T], &mut [T]) { let len = self.len(); let ptr = self.as_mut_ptr(); @@ -1690,7 +1694,10 @@ impl [T] { // `[ptr; mid]` and `[mid; len]` are not overlapping, so returning a mutable reference // is fine. unsafe { - assert_unsafe_precondition!((mid: usize, len: usize) => mid <= len); + assert_unsafe_precondition!( + "slice::split_at_mut_unchecked requires the index to be within the slice", + (mid: usize, len: usize) => mid <= len + ); (from_raw_parts_mut(ptr, mid), from_raw_parts_mut(ptr.add(mid), len - mid)) } } @@ -2074,7 +2081,7 @@ impl [T] { SplitN::new(self.split(pred), n) } - /// Returns an iterator over subslices separated by elements that match + /// Returns an iterator over mutable subslices separated by elements that match /// `pred`, limited to returning at most `n` items. The matched element is /// not contained in the subslices. /// @@ -2357,6 +2364,28 @@ impl [T] { /// assert!(match r { Ok(1..=4) => true, _ => false, }); /// ``` /// + /// If you want to find that whole *range* of matching items, rather than + /// an arbitrary matching one, that can be done using [`partition_point`]: + /// ``` + /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]; + /// + /// let low = s.partition_point(|x| x < &1); + /// assert_eq!(low, 1); + /// let high = s.partition_point(|x| x <= &1); + /// assert_eq!(high, 5); + /// let r = s.binary_search(&1); + /// assert!((low..high).contains(&r.unwrap())); + /// + /// assert!(s[..low].iter().all(|&x| x < 1)); + /// assert!(s[low..high].iter().all(|&x| x == 1)); + /// assert!(s[high..].iter().all(|&x| x > 1)); + /// + /// // For something not found, the "range" of equal items is empty + /// assert_eq!(s.partition_point(|x| x < &11), 9); + /// assert_eq!(s.partition_point(|x| x <= &11), 9); + /// assert_eq!(s.binary_search(&11), Err(9)); + /// ``` + /// /// If you want to insert an item to a sorted vector, while maintaining /// sort order, consider using [`partition_point`]: /// @@ -2424,15 +2453,20 @@ impl [T] { where F: FnMut(&'a T) -> Ordering, { + // INVARIANTS: + // - 0 <= left <= left + size = right <= self.len() + // - f returns Less for everything in self[..left] + // - f returns Greater for everything in self[right..] let mut size = self.len(); let mut left = 0; let mut right = size; while left < right { let mid = left + size / 2; - // SAFETY: the call is made safe by the following invariants: - // - `mid >= 0` - // - `mid < size`: `mid` is limited by `[left; right)` bound. + // SAFETY: the while condition means `size` is strictly positive, so + // `size/2 < size`. Thus `left + size/2 < left + size`, which + // coupled with the `left + size <= self.len()` invariant means + // we have `left + size/2 < self.len()`, and this is in-bounds. let cmp = f(unsafe { self.get_unchecked(mid) }); // The reason why we use if/else control flow rather than match @@ -2450,6 +2484,10 @@ impl [T] { size = right - left; } + + // SAFETY: directly true from the overall invariant. + // Note that this is `<=`, unlike the assume in the `Ok` path. + unsafe { crate::intrinsics::assume(left <= self.len()) }; Err(left) } @@ -2540,7 +2578,7 @@ impl [T] { where T: Ord, { - sort::quicksort(self, |a, b| a.lt(b)); + sort::quicksort(self, T::lt); } /// Sorts the slice with a comparator function, but might not preserve the order of equal @@ -2643,9 +2681,10 @@ impl [T] { /// less than or equal to any value at a position `j > index`. Additionally, this reordering is /// unstable (i.e. any number of equal elements may end up at position `index`), in-place /// (i.e. does not allocate), and *O*(*n*) worst-case. This function is also/ known as "kth - /// element" in other libraries. It returns a triplet of the following values: all elements less - /// than the one at the given index, the value at the given index, and all elements greater than - /// the one at the given index. + /// element" in other libraries. It returns a triplet of the following from the reordered slice: + /// the subslice prior to `index`, the element at `index`, and the subslice after `index`; + /// accordingly, the values in those two subslices will respectively all be less-than-or-equal-to + /// and greater-than-or-equal-to the value of the element at `index`. /// /// # Current implementation /// @@ -2679,8 +2718,7 @@ impl [T] { where T: Ord, { - let mut f = |a: &T, b: &T| a.lt(b); - sort::partition_at_index(self, index, &mut f) + sort::partition_at_index(self, index, T::lt) } /// Reorder the slice with a comparator function such that the element at `index` is at its @@ -2690,10 +2728,11 @@ impl [T] { /// less than or equal to any value at a position `j > index` using the comparator function. /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at /// position `index`), in-place (i.e. does not allocate), and *O*(*n*) worst-case. This function - /// is also known as "kth element" in other libraries. It returns a triplet of the following - /// values: all elements less than the one at the given index, the value at the given index, - /// and all elements greater than the one at the given index, using the provided comparator - /// function. + /// is also known as "kth element" in other libraries. It returns a triplet of the following from + /// the slice reordered according to the provided comparator function: the subslice prior to + /// `index`, the element at `index`, and the subslice after `index`; accordingly, the values in + /// those two subslices will respectively all be less-than-or-equal-to and greater-than-or-equal-to + /// the value of the element at `index`. /// /// # Current implementation /// @@ -2731,8 +2770,7 @@ impl [T] { where F: FnMut(&T, &T) -> Ordering, { - let mut f = |a: &T, b: &T| compare(a, b) == Less; - sort::partition_at_index(self, index, &mut f) + sort::partition_at_index(self, index, |a: &T, b: &T| compare(a, b) == Less) } /// Reorder the slice with a key extraction function such that the element at `index` is at its @@ -2742,10 +2780,11 @@ impl [T] { /// less than or equal to any value at a position `j > index` using the key extraction function. /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at /// position `index`), in-place (i.e. does not allocate), and *O*(*n*) worst-case. This function - /// is also known as "kth element" in other libraries. It returns a triplet of the following - /// values: all elements less than the one at the given index, the value at the given index, and - /// all elements greater than the one at the given index, using the provided key extraction - /// function. + /// is also known as "kth element" in other libraries. It returns a triplet of the following from + /// the slice reordered according to the provided key extraction function: the subslice prior to + /// `index`, the element at `index`, and the subslice after `index`; accordingly, the values in + /// those two subslices will respectively all be less-than-or-equal-to and greater-than-or-equal-to + /// the value of the element at `index`. /// /// # Current implementation /// @@ -2784,8 +2823,7 @@ impl [T] { F: FnMut(&T) -> K, K: Ord, { - let mut g = |a: &T, b: &T| f(a).lt(&f(b)); - sort::partition_at_index(self, index, &mut g) + sort::partition_at_index(self, index, |a: &T, b: &T| f(a).lt(&f(b))) } /// Moves all consecutive repeated elements to the end of the slice according to the @@ -3459,7 +3497,7 @@ impl [T] { #[must_use] pub unsafe fn align_to(&self) -> (&[T], &[U], &[T]) { // Note that most of this function will be constant-evaluated, - if mem::size_of::() == 0 || mem::size_of::() == 0 { + if U::IS_ZST || T::IS_ZST { // handle ZSTs specially, which is – don't handle them at all. return (self, &[], &[]); } @@ -3520,7 +3558,7 @@ impl [T] { #[must_use] pub unsafe fn align_to_mut(&mut self) -> (&mut [T], &mut [U], &mut [T]) { // Note that most of this function will be constant-evaluated, - if mem::size_of::() == 0 || mem::size_of::() == 0 { + if U::IS_ZST || T::IS_ZST { // handle ZSTs specially, which is – don't handle them at all. return (self, &mut [], &mut []); } @@ -3776,6 +3814,16 @@ impl [T] { /// assert!(v[i..].iter().all(|&x| !(x < 5))); /// ``` /// + /// If all elements of the slice match the predicate, including if the slice + /// is empty, then the length of the slice will be returned: + /// + /// ``` + /// let a = [2, 4, 8]; + /// assert_eq!(a.partition_point(|x| x < &100), a.len()); + /// let a: [i32; 0] = []; + /// assert_eq!(a.partition_point(|x| x < &100), 0); + /// ``` + /// /// If you want to insert an item to a sorted vector, while maintaining /// sort order: /// @@ -4066,7 +4114,7 @@ impl [[T; N]] { /// ``` #[unstable(feature = "slice_flatten", issue = "95629")] pub fn flatten(&self) -> &[T] { - let len = if crate::mem::size_of::() == 0 { + let len = if T::IS_ZST { self.len().checked_mul(N).expect("slice len overflow") } else { // SAFETY: `self.len() * N` cannot overflow because `self` is @@ -4104,7 +4152,7 @@ impl [[T; N]] { /// ``` #[unstable(feature = "slice_flatten", issue = "95629")] pub fn flatten_mut(&mut self) -> &mut [T] { - let len = if crate::mem::size_of::() == 0 { + let len = if T::IS_ZST { self.len().checked_mul(N).expect("slice len overflow") } else { // SAFETY: `self.len() * N` cannot overflow because `self` is diff --git a/library/core/src/slice/raw.rs b/library/core/src/slice/raw.rs index f1e8bc79b..052fd34d0 100644 --- a/library/core/src/slice/raw.rs +++ b/library/core/src/slice/raw.rs @@ -1,7 +1,9 @@ //! Free functions to create `&[T]` and `&mut [T]`. use crate::array; -use crate::intrinsics::{assert_unsafe_precondition, is_aligned_and_not_null}; +use crate::intrinsics::{ + assert_unsafe_precondition, is_aligned_and_not_null, is_valid_allocation_size, +}; use crate::ops::Range; use crate::ptr; @@ -90,9 +92,10 @@ use crate::ptr; pub const unsafe fn from_raw_parts<'a, T>(data: *const T, len: usize) -> &'a [T] { // SAFETY: the caller must uphold the safety contract for `from_raw_parts`. unsafe { - assert_unsafe_precondition!([T](data: *const T, len: usize) => - is_aligned_and_not_null(data) - && crate::mem::size_of::().saturating_mul(len) <= isize::MAX as usize + assert_unsafe_precondition!( + "slice::from_raw_parts requires the pointer to be aligned and non-null, and the total size of the slice not to exceed `isize::MAX`", + [T](data: *const T, len: usize) => is_aligned_and_not_null(data) + && is_valid_allocation_size::(len) ); &*ptr::slice_from_raw_parts(data, len) } @@ -134,9 +137,10 @@ pub const unsafe fn from_raw_parts<'a, T>(data: *const T, len: usize) -> &'a [T] pub const unsafe fn from_raw_parts_mut<'a, T>(data: *mut T, len: usize) -> &'a mut [T] { // SAFETY: the caller must uphold the safety contract for `from_raw_parts_mut`. unsafe { - assert_unsafe_precondition!([T](data: *mut T, len: usize) => - is_aligned_and_not_null(data) - && crate::mem::size_of::().saturating_mul(len) <= isize::MAX as usize + assert_unsafe_precondition!( + "slice::from_raw_parts_mut requires the pointer to be aligned and non-null, and the total size of the slice not to exceed `isize::MAX`", + [T](data: *mut T, len: usize) => is_aligned_and_not_null(data) + && is_valid_allocation_size::(len) ); &mut *ptr::slice_from_raw_parts_mut(data, len) } @@ -188,6 +192,10 @@ pub const fn from_mut(s: &mut T) -> &mut [T] { /// /// Note that a range created from [`slice::as_ptr_range`] fulfills these requirements. /// +/// # Panics +/// +/// This function panics if `T` is a Zero-Sized Type (“ZST”). +/// /// # Caveat /// /// The lifetime for the returned slice is inferred from its usage. To @@ -219,9 +227,15 @@ pub const unsafe fn from_ptr_range<'a, T>(range: Range<*const T>) -> &'a [T] { unsafe { from_raw_parts(range.start, range.end.sub_ptr(range.start)) } } -/// Performs the same functionality as [`from_ptr_range`], except that a +/// Forms a mutable slice from a pointer range. +/// +/// This is the same functionality as [`from_ptr_range`], except that a /// mutable slice is returned. /// +/// This function is useful for interacting with foreign interfaces which +/// use two pointers to refer to a range of elements in memory, as is +/// common in C++. +/// /// # Safety /// /// Behavior is undefined if any of the following conditions are violated: @@ -247,6 +261,18 @@ pub const unsafe fn from_ptr_range<'a, T>(range: Range<*const T>) -> &'a [T] { /// /// Note that a range created from [`slice::as_mut_ptr_range`] fulfills these requirements. /// +/// # Panics +/// +/// This function panics if `T` is a Zero-Sized Type (“ZST”). +/// +/// # Caveat +/// +/// The lifetime for the returned slice is inferred from its usage. To +/// prevent accidental misuse, it's suggested to tie the lifetime to whichever +/// source lifetime is safe in the context, such as by providing a helper +/// function taking the lifetime of a host value for the slice, or by explicit +/// annotation. +/// /// # Examples /// /// ``` diff --git a/library/core/src/slice/rotate.rs b/library/core/src/slice/rotate.rs index 4589c6c0f..fa8c238f8 100644 --- a/library/core/src/slice/rotate.rs +++ b/library/core/src/slice/rotate.rs @@ -1,5 +1,5 @@ use crate::cmp; -use crate::mem::{self, MaybeUninit}; +use crate::mem::{self, MaybeUninit, SizedTypeProperties}; use crate::ptr; /// Rotates the range `[mid-left, mid+right)` such that the element at `mid` becomes the first @@ -63,7 +63,7 @@ use crate::ptr; /// when `left < right` the swapping happens from the left instead. pub unsafe fn ptr_rotate(mut left: usize, mut mid: *mut T, mut right: usize) { type BufType = [usize; 32]; - if mem::size_of::() == 0 { + if T::IS_ZST { return; } loop { diff --git a/library/core/src/slice/sort.rs b/library/core/src/slice/sort.rs index c6c03c0b0..87f77b7f2 100644 --- a/library/core/src/slice/sort.rs +++ b/library/core/src/slice/sort.rs @@ -7,7 +7,7 @@ //! stable sorting implementation. use crate::cmp; -use crate::mem::{self, MaybeUninit}; +use crate::mem::{self, MaybeUninit, SizedTypeProperties}; use crate::ptr; /// When dropped, copies from `src` into `dest`. @@ -813,7 +813,7 @@ where F: FnMut(&T, &T) -> bool, { // Sorting has no meaningful behavior on zero-sized types. - if mem::size_of::() == 0 { + if T::IS_ZST { return; } @@ -898,7 +898,7 @@ where panic!("partition_at_index index {} greater than length of slice {}", index, v.len()); } - if mem::size_of::() == 0 { + if T::IS_ZST { // Sorting has no meaningful behavior on zero-sized types. Do nothing. } else if index == v.len() - 1 { // Find max element and place it in the last position of the array. We're free to use -- cgit v1.2.3