summaryrefslogtreecommitdiffstats
path: root/library/core/src/slice/mod.rs
diff options
context:
space:
mode:
Diffstat (limited to 'library/core/src/slice/mod.rs')
-rw-r--r--library/core/src/slice/mod.rs372
1 files changed, 300 insertions, 72 deletions
diff --git a/library/core/src/slice/mod.rs b/library/core/src/slice/mod.rs
index f541808a6..ea0181e35 100644
--- a/library/core/src/slice/mod.rs
+++ b/library/core/src/slice/mod.rs
@@ -42,8 +42,13 @@ mod index;
mod iter;
mod raw;
mod rotate;
+mod select;
mod specialize;
+#[unstable(feature = "str_internals", issue = "none")]
+#[doc(hidden)]
+pub use ascii::is_ascii_simple;
+
#[stable(feature = "rust1", since = "1.0.0")]
pub use iter::{Chunks, ChunksMut, Windows};
#[stable(feature = "rust1", since = "1.0.0")]
@@ -315,6 +320,264 @@ impl<T> [T] {
if let [.., last] = self { Some(last) } else { None }
}
+ /// Returns the first `N` elements of the slice, or `None` if it has fewer than `N` elements.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(slice_first_last_chunk)]
+ ///
+ /// let u = [10, 40, 30];
+ /// assert_eq!(Some(&[10, 40]), u.first_chunk::<2>());
+ ///
+ /// let v: &[i32] = &[10];
+ /// assert_eq!(None, v.first_chunk::<2>());
+ ///
+ /// let w: &[i32] = &[];
+ /// assert_eq!(Some(&[]), w.first_chunk::<0>());
+ /// ```
+ #[unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[rustc_const_unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[inline]
+ pub const fn first_chunk<const N: usize>(&self) -> Option<&[T; N]> {
+ if self.len() < N {
+ None
+ } else {
+ // SAFETY: We explicitly check for the correct number of elements,
+ // and do not let the reference outlive the slice.
+ Some(unsafe { &*(self.as_ptr() as *const [T; N]) })
+ }
+ }
+
+ /// Returns a mutable reference to the first `N` elements of the slice,
+ /// or `None` if it has fewer than `N` elements.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(slice_first_last_chunk)]
+ ///
+ /// let x = &mut [0, 1, 2];
+ ///
+ /// if let Some(first) = x.first_chunk_mut::<2>() {
+ /// first[0] = 5;
+ /// first[1] = 4;
+ /// }
+ /// assert_eq!(x, &[5, 4, 2]);
+ /// ```
+ #[unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[rustc_const_unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[inline]
+ pub const fn first_chunk_mut<const N: usize>(&mut self) -> Option<&mut [T; N]> {
+ if self.len() < N {
+ None
+ } else {
+ // SAFETY: We explicitly check for the correct number of elements,
+ // do not let the reference outlive the slice,
+ // and require exclusive access to the entire slice to mutate the chunk.
+ Some(unsafe { &mut *(self.as_mut_ptr() as *mut [T; N]) })
+ }
+ }
+
+ /// Returns the first `N` elements of the slice and the remainder,
+ /// or `None` if it has fewer than `N` elements.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(slice_first_last_chunk)]
+ ///
+ /// let x = &[0, 1, 2];
+ ///
+ /// if let Some((first, elements)) = x.split_first_chunk::<2>() {
+ /// assert_eq!(first, &[0, 1]);
+ /// assert_eq!(elements, &[2]);
+ /// }
+ /// ```
+ #[unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[rustc_const_unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[inline]
+ pub const fn split_first_chunk<const N: usize>(&self) -> Option<(&[T; N], &[T])> {
+ if self.len() < N {
+ None
+ } else {
+ // SAFETY: We manually verified the bounds of the split.
+ let (first, tail) = unsafe { self.split_at_unchecked(N) };
+
+ // SAFETY: We explicitly check for the correct number of elements,
+ // and do not let the references outlive the slice.
+ Some((unsafe { &*(first.as_ptr() as *const [T; N]) }, tail))
+ }
+ }
+
+ /// Returns a mutable reference to the first `N` elements of the slice and the remainder,
+ /// or `None` if it has fewer than `N` elements.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(slice_first_last_chunk)]
+ ///
+ /// let x = &mut [0, 1, 2];
+ ///
+ /// if let Some((first, elements)) = x.split_first_chunk_mut::<2>() {
+ /// first[0] = 3;
+ /// first[1] = 4;
+ /// elements[0] = 5;
+ /// }
+ /// assert_eq!(x, &[3, 4, 5]);
+ /// ```
+ #[unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[rustc_const_unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[inline]
+ pub const fn split_first_chunk_mut<const N: usize>(
+ &mut self,
+ ) -> Option<(&mut [T; N], &mut [T])> {
+ if self.len() < N {
+ None
+ } else {
+ // SAFETY: We manually verified the bounds of the split.
+ let (first, tail) = unsafe { self.split_at_mut_unchecked(N) };
+
+ // SAFETY: We explicitly check for the correct number of elements,
+ // do not let the reference outlive the slice,
+ // and enforce exclusive mutability of the chunk by the split.
+ Some((unsafe { &mut *(first.as_mut_ptr() as *mut [T; N]) }, tail))
+ }
+ }
+
+ /// Returns the last `N` elements of the slice and the remainder,
+ /// or `None` if it has fewer than `N` elements.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(slice_first_last_chunk)]
+ ///
+ /// let x = &[0, 1, 2];
+ ///
+ /// if let Some((last, elements)) = x.split_last_chunk::<2>() {
+ /// assert_eq!(last, &[1, 2]);
+ /// assert_eq!(elements, &[0]);
+ /// }
+ /// ```
+ #[unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[rustc_const_unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[inline]
+ pub const fn split_last_chunk<const N: usize>(&self) -> Option<(&[T; N], &[T])> {
+ if self.len() < N {
+ None
+ } else {
+ // SAFETY: We manually verified the bounds of the split.
+ let (init, last) = unsafe { self.split_at_unchecked(self.len() - N) };
+
+ // SAFETY: We explicitly check for the correct number of elements,
+ // and do not let the references outlive the slice.
+ Some((unsafe { &*(last.as_ptr() as *const [T; N]) }, init))
+ }
+ }
+
+ /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(slice_first_last_chunk)]
+ ///
+ /// let x = &mut [0, 1, 2];
+ ///
+ /// if let Some((last, elements)) = x.split_last_chunk_mut::<2>() {
+ /// last[0] = 3;
+ /// last[1] = 4;
+ /// elements[0] = 5;
+ /// }
+ /// assert_eq!(x, &[5, 3, 4]);
+ /// ```
+ #[unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[rustc_const_unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[inline]
+ pub const fn split_last_chunk_mut<const N: usize>(
+ &mut self,
+ ) -> Option<(&mut [T; N], &mut [T])> {
+ if self.len() < N {
+ None
+ } else {
+ // SAFETY: We manually verified the bounds of the split.
+ let (init, last) = unsafe { self.split_at_mut_unchecked(self.len() - N) };
+
+ // SAFETY: We explicitly check for the correct number of elements,
+ // do not let the reference outlive the slice,
+ // and enforce exclusive mutability of the chunk by the split.
+ Some((unsafe { &mut *(last.as_mut_ptr() as *mut [T; N]) }, init))
+ }
+ }
+
+ /// Returns the last element of the slice, or `None` if it is empty.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(slice_first_last_chunk)]
+ ///
+ /// let u = [10, 40, 30];
+ /// assert_eq!(Some(&[40, 30]), u.last_chunk::<2>());
+ ///
+ /// let v: &[i32] = &[10];
+ /// assert_eq!(None, v.last_chunk::<2>());
+ ///
+ /// let w: &[i32] = &[];
+ /// assert_eq!(Some(&[]), w.last_chunk::<0>());
+ /// ```
+ #[unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[rustc_const_unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[inline]
+ pub const fn last_chunk<const N: usize>(&self) -> Option<&[T; N]> {
+ if self.len() < N {
+ None
+ } else {
+ // SAFETY: We manually verified the bounds of the slice.
+ // FIXME: Without const traits, we need this instead of `get_unchecked`.
+ let last = unsafe { self.split_at_unchecked(self.len() - N).1 };
+
+ // SAFETY: We explicitly check for the correct number of elements,
+ // and do not let the references outlive the slice.
+ Some(unsafe { &*(last.as_ptr() as *const [T; N]) })
+ }
+ }
+
+ /// Returns a mutable pointer to the last item in the slice.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// #![feature(slice_first_last_chunk)]
+ ///
+ /// let x = &mut [0, 1, 2];
+ ///
+ /// if let Some(last) = x.last_chunk_mut::<2>() {
+ /// last[0] = 10;
+ /// last[1] = 20;
+ /// }
+ /// assert_eq!(x, &[0, 10, 20]);
+ /// ```
+ #[unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[rustc_const_unstable(feature = "slice_first_last_chunk", issue = "111774")]
+ #[inline]
+ pub const fn last_chunk_mut<const N: usize>(&mut self) -> Option<&mut [T; N]> {
+ if self.len() < N {
+ None
+ } else {
+ // SAFETY: We manually verified the bounds of the slice.
+ // FIXME: Without const traits, we need this instead of `get_unchecked`.
+ let last = unsafe { self.split_at_mut_unchecked(self.len() - N).1 };
+
+ // SAFETY: We explicitly check for the correct number of elements,
+ // do not let the reference outlive the slice,
+ // and require exclusive access to the entire slice to mutate the chunk.
+ Some(unsafe { &mut *(last.as_mut_ptr() as *mut [T; N]) })
+ }
+ }
+
/// Returns a reference to an element or subslice depending on the type of
/// index.
///
@@ -333,12 +596,11 @@ impl<T> [T] {
/// assert_eq!(None, v.get(0..4));
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
#[inline]
#[must_use]
- pub const fn get<I>(&self, index: I) -> Option<&I::Output>
+ pub fn get<I>(&self, index: I) -> Option<&I::Output>
where
- I: ~const SliceIndex<Self>,
+ I: SliceIndex<Self>,
{
index.get(self)
}
@@ -359,12 +621,11 @@ impl<T> [T] {
/// assert_eq!(x, &[0, 42, 2]);
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
#[inline]
#[must_use]
- pub const fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
+ pub fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
where
- I: ~const SliceIndex<Self>,
+ I: SliceIndex<Self>,
{
index.get_mut(self)
}
@@ -392,12 +653,11 @@ impl<T> [T] {
/// }
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
#[inline]
#[must_use]
- pub const unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
+ pub unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
where
- I: ~const SliceIndex<Self>,
+ I: SliceIndex<Self>,
{
// SAFETY: the caller must uphold most of the safety requirements for `get_unchecked`;
// the slice is dereferenceable because `self` is a safe reference.
@@ -430,12 +690,11 @@ impl<T> [T] {
/// assert_eq!(x, &[1, 13, 4]);
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
#[inline]
#[must_use]
- pub const unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
+ pub unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
where
- I: ~const SliceIndex<Self>,
+ I: SliceIndex<Self>,
{
// SAFETY: the caller must uphold the safety requirements for `get_unchecked_mut`;
// the slice is dereferenceable because `self` is a safe reference.
@@ -678,9 +937,8 @@ impl<T> [T] {
/// assert!(v == [3, 2, 1]);
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_reverse", issue = "100784")]
#[inline]
- pub const fn reverse(&mut self) {
+ pub fn reverse(&mut self) {
let half_len = self.len() / 2;
let Range { start, end } = self.as_mut_ptr_range();
@@ -703,7 +961,7 @@ impl<T> [T] {
revswap(front_half, back_half, half_len);
#[inline]
- const fn revswap<T>(a: &mut [T], b: &mut [T], n: usize) {
+ fn revswap<T>(a: &mut [T], b: &mut [T], n: usize) {
debug_assert!(a.len() == n);
debug_assert!(b.len() == n);
@@ -996,7 +1254,7 @@ impl<T> [T] {
#[unstable(feature = "slice_as_chunks", issue = "74985")]
#[inline]
#[must_use]
- pub unsafe fn as_chunks_unchecked<const N: usize>(&self) -> &[[T; N]] {
+ pub const unsafe fn as_chunks_unchecked<const N: usize>(&self) -> &[[T; N]] {
let this = self;
// SAFETY: Caller must guarantee that `N` is nonzero and exactly divides the slice length
let new_len = unsafe {
@@ -1044,7 +1302,7 @@ impl<T> [T] {
#[inline]
#[track_caller]
#[must_use]
- pub fn as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T]) {
+ pub const fn as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T]) {
assert!(N != 0, "chunk size must be non-zero");
let len = self.len() / N;
let (multiple_of_n, remainder) = self.split_at(len * N);
@@ -1076,7 +1334,7 @@ impl<T> [T] {
#[inline]
#[track_caller]
#[must_use]
- pub fn as_rchunks<const N: usize>(&self) -> (&[T], &[[T; N]]) {
+ pub const fn as_rchunks<const N: usize>(&self) -> (&[T], &[[T; N]]) {
assert!(N != 0, "chunk size must be non-zero");
let len = self.len() / N;
let (remainder, multiple_of_n) = self.split_at(self.len() - len * N);
@@ -1153,7 +1411,7 @@ impl<T> [T] {
#[unstable(feature = "slice_as_chunks", issue = "74985")]
#[inline]
#[must_use]
- pub unsafe fn as_chunks_unchecked_mut<const N: usize>(&mut self) -> &mut [[T; N]] {
+ pub const unsafe fn as_chunks_unchecked_mut<const N: usize>(&mut self) -> &mut [[T; N]] {
let this = &*self;
// SAFETY: Caller must guarantee that `N` is nonzero and exactly divides the slice length
let new_len = unsafe {
@@ -1196,7 +1454,7 @@ impl<T> [T] {
#[inline]
#[track_caller]
#[must_use]
- pub fn as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T]) {
+ pub const fn as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T]) {
assert!(N != 0, "chunk size must be non-zero");
let len = self.len() / N;
let (multiple_of_n, remainder) = self.split_at_mut(len * N);
@@ -1234,7 +1492,7 @@ impl<T> [T] {
#[inline]
#[track_caller]
#[must_use]
- pub fn as_rchunks_mut<const N: usize>(&mut self) -> (&mut [T], &mut [[T; N]]) {
+ pub const fn as_rchunks_mut<const N: usize>(&mut self) -> (&mut [T], &mut [[T; N]]) {
assert!(N != 0, "chunk size must be non-zero");
let len = self.len() / N;
let (remainder, multiple_of_n) = self.split_at_mut(self.len() - len * N);
@@ -1596,7 +1854,8 @@ impl<T> [T] {
/// }
/// ```
#[stable(feature = "rust1", since = "1.0.0")]
- #[rustc_const_unstable(feature = "const_slice_split_at_not_mut", issue = "101158")]
+ #[rustc_const_stable(feature = "const_slice_split_at_not_mut", since = "1.71.0")]
+ #[rustc_allow_const_fn_unstable(slice_split_at_unchecked)]
#[inline]
#[track_caller]
#[must_use]
@@ -2746,8 +3005,9 @@ impl<T> [T] {
///
/// # Current implementation
///
- /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
- /// used for [`sort_unstable`].
+ /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also
+ /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for
+ /// pivot selection, which guarantees linear runtime for all inputs.
///
/// [`sort_unstable`]: slice::sort_unstable
///
@@ -2776,7 +3036,7 @@ impl<T> [T] {
where
T: Ord,
{
- sort::partition_at_index(self, index, T::lt)
+ select::partition_at_index(self, index, T::lt)
}
/// Reorder the slice with a comparator function such that the element at `index` is at its
@@ -2797,8 +3057,9 @@ impl<T> [T] {
///
/// # Current implementation
///
- /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
- /// used for [`sort_unstable`].
+ /// The current algorithm is an introselect implementation based on Pattern Defeating Quicksort, which is also
+ /// the basis for [`sort_unstable`]. The fallback algorithm is Median of Medians using Tukey's Ninther for
+ /// pivot selection, which guarantees linear runtime for all inputs.
///
/// [`sort_unstable`]: slice::sort_unstable
///
@@ -2831,7 +3092,7 @@ impl<T> [T] {
where
F: FnMut(&T, &T) -> Ordering,
{
- sort::partition_at_index(self, index, |a: &T, b: &T| compare(a, b) == Less)
+ select::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
@@ -2887,7 +3148,7 @@ impl<T> [T] {
F: FnMut(&T) -> K,
K: Ord,
{
- sort::partition_at_index(self, index, |a: &T, b: &T| f(a).lt(&f(b)))
+ select::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
@@ -3479,44 +3740,13 @@ impl<T> [T] {
// Ts = size_of::<U> / gcd(size_of::<T>, size_of::<U>)
//
// Luckily since all this is constant-evaluated... performance here matters not!
- #[inline]
- fn gcd(a: usize, b: usize) -> usize {
- use crate::intrinsics;
- // iterative stein’s algorithm
- // We should still make this `const fn` (and revert to recursive algorithm if we do)
- // because relying on llvm to consteval all this is… well, it makes me uncomfortable.
-
- // SAFETY: `a` and `b` are checked to be non-zero values.
- let (ctz_a, mut ctz_b) = unsafe {
- if a == 0 {
- return b;
- }
- if b == 0 {
- return a;
- }
- (intrinsics::cttz_nonzero(a), intrinsics::cttz_nonzero(b))
- };
- let k = ctz_a.min(ctz_b);
- let mut a = a >> ctz_a;
- let mut b = b;
- loop {
- // remove all factors of 2 from b
- b >>= ctz_b;
- if a > b {
- mem::swap(&mut a, &mut b);
- }
- b = b - a;
- // SAFETY: `b` is checked to be non-zero.
- unsafe {
- if b == 0 {
- break;
- }
- ctz_b = intrinsics::cttz_nonzero(b);
- }
- }
- a << k
+ const fn gcd(a: usize, b: usize) -> usize {
+ if b == 0 { a } else { gcd(b, a % b) }
}
- let gcd: usize = gcd(mem::size_of::<T>(), mem::size_of::<U>());
+
+ // Explicitly wrap the function call in a const block so it gets
+ // constant-evaluated even in debug mode.
+ let gcd: usize = const { gcd(mem::size_of::<T>(), mem::size_of::<U>()) };
let ts: usize = mem::size_of::<U>() / gcd;
let us: usize = mem::size_of::<T>() / gcd;
@@ -4262,7 +4492,7 @@ impl<T, const N: usize> [[T; N]] {
/// assert!(empty_slice_of_arrays.flatten().is_empty());
/// ```
#[unstable(feature = "slice_flatten", issue = "95629")]
- pub fn flatten(&self) -> &[T] {
+ pub const fn flatten(&self) -> &[T] {
let len = if T::IS_ZST {
self.len().checked_mul(N).expect("slice len overflow")
} else {
@@ -4404,8 +4634,7 @@ where
}
#[stable(feature = "rust1", since = "1.0.0")]
-#[rustc_const_unstable(feature = "const_default_impls", issue = "87864")]
-impl<T> const Default for &[T] {
+impl<T> Default for &[T] {
/// Creates an empty slice.
fn default() -> Self {
&[]
@@ -4413,8 +4642,7 @@ impl<T> const Default for &[T] {
}
#[stable(feature = "mut_slice_default", since = "1.5.0")]
-#[rustc_const_unstable(feature = "const_default_impls", issue = "87864")]
-impl<T> const Default for &mut [T] {
+impl<T> Default for &mut [T] {
/// Creates a mutable empty slice.
fn default() -> Self {
&mut []
@@ -4458,7 +4686,7 @@ impl<T, const N: usize> SlicePattern for [T; N] {
/// This will do `binomial(N + 1, 2) = N * (N + 1) / 2 = 0, 1, 3, 6, 10, ..`
/// comparison operations.
fn get_many_check_valid<const N: usize>(indices: &[usize; N], len: usize) -> bool {
- // NB: The optimzer should inline the loops into a sequence
+ // NB: The optimizer should inline the loops into a sequence
// of instructions without additional branching.
let mut valid = true;
for (i, &idx) in indices.iter().enumerate() {
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-29 12:00:02 +0000