core/slice/
mod.rs

1//! Slice management and manipulation.
2//!
3//! For more details see [`std::slice`].
4//!
5//! [`std::slice`]: ../../std/slice/index.html
6
7#![stable(feature = "rust1", since = "1.0.0")]
8
9use crate::cmp::Ordering::{self, Equal, Greater, Less};
10use crate::intrinsics::{exact_div, unchecked_sub};
11use crate::mem::{self, MaybeUninit, SizedTypeProperties};
12use crate::num::NonZero;
13use crate::ops::{OneSidedRange, OneSidedRangeBound, Range, RangeBounds, RangeInclusive};
14use crate::panic::const_panic;
15use crate::simd::{self, Simd};
16use crate::ub_checks::assert_unsafe_precondition;
17use crate::{fmt, hint, ptr, range, slice};
18
19#[unstable(
20    feature = "slice_internals",
21    issue = "none",
22    reason = "exposed from core to be reused in std; use the memchr crate"
23)]
24#[doc(hidden)]
25/// Pure Rust memchr implementation, taken from rust-memchr
26pub mod memchr;
27
28#[unstable(
29    feature = "slice_internals",
30    issue = "none",
31    reason = "exposed from core to be reused in std;"
32)]
33#[doc(hidden)]
34pub mod sort;
35
36mod ascii;
37mod cmp;
38pub(crate) mod index;
39mod iter;
40mod raw;
41mod rotate;
42mod specialize;
43
44#[stable(feature = "inherent_ascii_escape", since = "1.60.0")]
45pub use ascii::EscapeAscii;
46#[unstable(feature = "str_internals", issue = "none")]
47#[doc(hidden)]
48pub use ascii::is_ascii_simple;
49#[stable(feature = "slice_get_slice", since = "1.28.0")]
50pub use index::SliceIndex;
51#[unstable(feature = "slice_range", issue = "76393")]
52pub use index::{range, try_range};
53#[unstable(feature = "array_windows", issue = "75027")]
54pub use iter::ArrayWindows;
55#[unstable(feature = "array_chunks", issue = "74985")]
56pub use iter::{ArrayChunks, ArrayChunksMut};
57#[stable(feature = "slice_group_by", since = "1.77.0")]
58pub use iter::{ChunkBy, ChunkByMut};
59#[stable(feature = "rust1", since = "1.0.0")]
60pub use iter::{Chunks, ChunksMut, Windows};
61#[stable(feature = "chunks_exact", since = "1.31.0")]
62pub use iter::{ChunksExact, ChunksExactMut};
63#[stable(feature = "rust1", since = "1.0.0")]
64pub use iter::{Iter, IterMut};
65#[stable(feature = "rchunks", since = "1.31.0")]
66pub use iter::{RChunks, RChunksExact, RChunksExactMut, RChunksMut};
67#[stable(feature = "slice_rsplit", since = "1.27.0")]
68pub use iter::{RSplit, RSplitMut};
69#[stable(feature = "rust1", since = "1.0.0")]
70pub use iter::{RSplitN, RSplitNMut, Split, SplitMut, SplitN, SplitNMut};
71#[stable(feature = "split_inclusive", since = "1.51.0")]
72pub use iter::{SplitInclusive, SplitInclusiveMut};
73#[stable(feature = "from_ref", since = "1.28.0")]
74pub use raw::{from_mut, from_ref};
75#[unstable(feature = "slice_from_ptr_range", issue = "89792")]
76pub use raw::{from_mut_ptr_range, from_ptr_range};
77#[stable(feature = "rust1", since = "1.0.0")]
78pub use raw::{from_raw_parts, from_raw_parts_mut};
79
80/// Calculates the direction and split point of a one-sided range.
81///
82/// This is a helper function for `split_off` and `split_off_mut` that returns
83/// the direction of the split (front or back) as well as the index at
84/// which to split. Returns `None` if the split index would overflow.
85#[inline]
86fn split_point_of(range: impl OneSidedRange<usize>) -> Option<(Direction, usize)> {
87    use OneSidedRangeBound::{End, EndInclusive, StartInclusive};
88
89    Some(match range.bound() {
90        (StartInclusive, i) => (Direction::Back, i),
91        (End, i) => (Direction::Front, i),
92        (EndInclusive, i) => (Direction::Front, i.checked_add(1)?),
93    })
94}
95
96enum Direction {
97    Front,
98    Back,
99}
100
101impl<T> [T] {
102    /// Returns the number of elements in the slice.
103    ///
104    /// # Examples
105    ///
106    /// ```
107    /// let a = [1, 2, 3];
108    /// assert_eq!(a.len(), 3);
109    /// ```
110    #[lang = "slice_len_fn"]
111    #[stable(feature = "rust1", since = "1.0.0")]
112    #[rustc_const_stable(feature = "const_slice_len", since = "1.39.0")]
113    #[rustc_no_implicit_autorefs]
114    #[inline]
115    #[must_use]
116    pub const fn len(&self) -> usize {
117        ptr::metadata(self)
118    }
119
120    /// Returns `true` if the slice has a length of 0.
121    ///
122    /// # Examples
123    ///
124    /// ```
125    /// let a = [1, 2, 3];
126    /// assert!(!a.is_empty());
127    ///
128    /// let b: &[i32] = &[];
129    /// assert!(b.is_empty());
130    /// ```
131    #[stable(feature = "rust1", since = "1.0.0")]
132    #[rustc_const_stable(feature = "const_slice_is_empty", since = "1.39.0")]
133    #[rustc_no_implicit_autorefs]
134    #[inline]
135    #[must_use]
136    pub const fn is_empty(&self) -> bool {
137        self.len() == 0
138    }
139
140    /// Returns the first element of the slice, or `None` if it is empty.
141    ///
142    /// # Examples
143    ///
144    /// ```
145    /// let v = [10, 40, 30];
146    /// assert_eq!(Some(&10), v.first());
147    ///
148    /// let w: &[i32] = &[];
149    /// assert_eq!(None, w.first());
150    /// ```
151    #[stable(feature = "rust1", since = "1.0.0")]
152    #[rustc_const_stable(feature = "const_slice_first_last_not_mut", since = "1.56.0")]
153    #[inline]
154    #[must_use]
155    pub const fn first(&self) -> Option<&T> {
156        if let [first, ..] = self { Some(first) } else { None }
157    }
158
159    /// Returns a mutable reference to the first element of the slice, or `None` if it is empty.
160    ///
161    /// # Examples
162    ///
163    /// ```
164    /// let x = &mut [0, 1, 2];
165    ///
166    /// if let Some(first) = x.first_mut() {
167    ///     *first = 5;
168    /// }
169    /// assert_eq!(x, &[5, 1, 2]);
170    ///
171    /// let y: &mut [i32] = &mut [];
172    /// assert_eq!(None, y.first_mut());
173    /// ```
174    #[stable(feature = "rust1", since = "1.0.0")]
175    #[rustc_const_stable(feature = "const_slice_first_last", since = "1.83.0")]
176    #[inline]
177    #[must_use]
178    pub const fn first_mut(&mut self) -> Option<&mut T> {
179        if let [first, ..] = self { Some(first) } else { None }
180    }
181
182    /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
183    ///
184    /// # Examples
185    ///
186    /// ```
187    /// let x = &[0, 1, 2];
188    ///
189    /// if let Some((first, elements)) = x.split_first() {
190    ///     assert_eq!(first, &0);
191    ///     assert_eq!(elements, &[1, 2]);
192    /// }
193    /// ```
194    #[stable(feature = "slice_splits", since = "1.5.0")]
195    #[rustc_const_stable(feature = "const_slice_first_last_not_mut", since = "1.56.0")]
196    #[inline]
197    #[must_use]
198    pub const fn split_first(&self) -> Option<(&T, &[T])> {
199        if let [first, tail @ ..] = self { Some((first, tail)) } else { None }
200    }
201
202    /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
203    ///
204    /// # Examples
205    ///
206    /// ```
207    /// let x = &mut [0, 1, 2];
208    ///
209    /// if let Some((first, elements)) = x.split_first_mut() {
210    ///     *first = 3;
211    ///     elements[0] = 4;
212    ///     elements[1] = 5;
213    /// }
214    /// assert_eq!(x, &[3, 4, 5]);
215    /// ```
216    #[stable(feature = "slice_splits", since = "1.5.0")]
217    #[rustc_const_stable(feature = "const_slice_first_last", since = "1.83.0")]
218    #[inline]
219    #[must_use]
220    pub const fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
221        if let [first, tail @ ..] = self { Some((first, tail)) } else { None }
222    }
223
224    /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
225    ///
226    /// # Examples
227    ///
228    /// ```
229    /// let x = &[0, 1, 2];
230    ///
231    /// if let Some((last, elements)) = x.split_last() {
232    ///     assert_eq!(last, &2);
233    ///     assert_eq!(elements, &[0, 1]);
234    /// }
235    /// ```
236    #[stable(feature = "slice_splits", since = "1.5.0")]
237    #[rustc_const_stable(feature = "const_slice_first_last_not_mut", since = "1.56.0")]
238    #[inline]
239    #[must_use]
240    pub const fn split_last(&self) -> Option<(&T, &[T])> {
241        if let [init @ .., last] = self { Some((last, init)) } else { None }
242    }
243
244    /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
245    ///
246    /// # Examples
247    ///
248    /// ```
249    /// let x = &mut [0, 1, 2];
250    ///
251    /// if let Some((last, elements)) = x.split_last_mut() {
252    ///     *last = 3;
253    ///     elements[0] = 4;
254    ///     elements[1] = 5;
255    /// }
256    /// assert_eq!(x, &[4, 5, 3]);
257    /// ```
258    #[stable(feature = "slice_splits", since = "1.5.0")]
259    #[rustc_const_stable(feature = "const_slice_first_last", since = "1.83.0")]
260    #[inline]
261    #[must_use]
262    pub const fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
263        if let [init @ .., last] = self { Some((last, init)) } else { None }
264    }
265
266    /// Returns the last element of the slice, or `None` if it is empty.
267    ///
268    /// # Examples
269    ///
270    /// ```
271    /// let v = [10, 40, 30];
272    /// assert_eq!(Some(&30), v.last());
273    ///
274    /// let w: &[i32] = &[];
275    /// assert_eq!(None, w.last());
276    /// ```
277    #[stable(feature = "rust1", since = "1.0.0")]
278    #[rustc_const_stable(feature = "const_slice_first_last_not_mut", since = "1.56.0")]
279    #[inline]
280    #[must_use]
281    pub const fn last(&self) -> Option<&T> {
282        if let [.., last] = self { Some(last) } else { None }
283    }
284
285    /// Returns a mutable reference to the last item in the slice, or `None` if it is empty.
286    ///
287    /// # Examples
288    ///
289    /// ```
290    /// let x = &mut [0, 1, 2];
291    ///
292    /// if let Some(last) = x.last_mut() {
293    ///     *last = 10;
294    /// }
295    /// assert_eq!(x, &[0, 1, 10]);
296    ///
297    /// let y: &mut [i32] = &mut [];
298    /// assert_eq!(None, y.last_mut());
299    /// ```
300    #[stable(feature = "rust1", since = "1.0.0")]
301    #[rustc_const_stable(feature = "const_slice_first_last", since = "1.83.0")]
302    #[inline]
303    #[must_use]
304    pub const fn last_mut(&mut self) -> Option<&mut T> {
305        if let [.., last] = self { Some(last) } else { None }
306    }
307
308    /// Returns an array reference to the first `N` items in the slice.
309    ///
310    /// If the slice is not at least `N` in length, this will return `None`.
311    ///
312    /// # Examples
313    ///
314    /// ```
315    /// let u = [10, 40, 30];
316    /// assert_eq!(Some(&[10, 40]), u.first_chunk::<2>());
317    ///
318    /// let v: &[i32] = &[10];
319    /// assert_eq!(None, v.first_chunk::<2>());
320    ///
321    /// let w: &[i32] = &[];
322    /// assert_eq!(Some(&[]), w.first_chunk::<0>());
323    /// ```
324    #[inline]
325    #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
326    #[rustc_const_stable(feature = "slice_first_last_chunk", since = "1.77.0")]
327    pub const fn first_chunk<const N: usize>(&self) -> Option<&[T; N]> {
328        if self.len() < N {
329            None
330        } else {
331            // SAFETY: We explicitly check for the correct number of elements,
332            //   and do not let the reference outlive the slice.
333            Some(unsafe { &*(self.as_ptr().cast::<[T; N]>()) })
334        }
335    }
336
337    /// Returns a mutable array reference to the first `N` items in the slice.
338    ///
339    /// If the slice is not at least `N` in length, this will return `None`.
340    ///
341    /// # Examples
342    ///
343    /// ```
344    /// let x = &mut [0, 1, 2];
345    ///
346    /// if let Some(first) = x.first_chunk_mut::<2>() {
347    ///     first[0] = 5;
348    ///     first[1] = 4;
349    /// }
350    /// assert_eq!(x, &[5, 4, 2]);
351    ///
352    /// assert_eq!(None, x.first_chunk_mut::<4>());
353    /// ```
354    #[inline]
355    #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
356    #[rustc_const_stable(feature = "const_slice_first_last_chunk", since = "1.83.0")]
357    pub const fn first_chunk_mut<const N: usize>(&mut self) -> Option<&mut [T; N]> {
358        if self.len() < N {
359            None
360        } else {
361            // SAFETY: We explicitly check for the correct number of elements,
362            //   do not let the reference outlive the slice,
363            //   and require exclusive access to the entire slice to mutate the chunk.
364            Some(unsafe { &mut *(self.as_mut_ptr().cast::<[T; N]>()) })
365        }
366    }
367
368    /// Returns an array reference to the first `N` items in the slice and the remaining slice.
369    ///
370    /// If the slice is not at least `N` in length, this will return `None`.
371    ///
372    /// # Examples
373    ///
374    /// ```
375    /// let x = &[0, 1, 2];
376    ///
377    /// if let Some((first, elements)) = x.split_first_chunk::<2>() {
378    ///     assert_eq!(first, &[0, 1]);
379    ///     assert_eq!(elements, &[2]);
380    /// }
381    ///
382    /// assert_eq!(None, x.split_first_chunk::<4>());
383    /// ```
384    #[inline]
385    #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
386    #[rustc_const_stable(feature = "slice_first_last_chunk", since = "1.77.0")]
387    pub const fn split_first_chunk<const N: usize>(&self) -> Option<(&[T; N], &[T])> {
388        let Some((first, tail)) = self.split_at_checked(N) else { return None };
389
390        // SAFETY: We explicitly check for the correct number of elements,
391        //   and do not let the references outlive the slice.
392        Some((unsafe { &*(first.as_ptr().cast::<[T; N]>()) }, tail))
393    }
394
395    /// Returns a mutable array reference to the first `N` items in the slice and the remaining
396    /// slice.
397    ///
398    /// If the slice is not at least `N` in length, this will return `None`.
399    ///
400    /// # Examples
401    ///
402    /// ```
403    /// let x = &mut [0, 1, 2];
404    ///
405    /// if let Some((first, elements)) = x.split_first_chunk_mut::<2>() {
406    ///     first[0] = 3;
407    ///     first[1] = 4;
408    ///     elements[0] = 5;
409    /// }
410    /// assert_eq!(x, &[3, 4, 5]);
411    ///
412    /// assert_eq!(None, x.split_first_chunk_mut::<4>());
413    /// ```
414    #[inline]
415    #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
416    #[rustc_const_stable(feature = "const_slice_first_last_chunk", since = "1.83.0")]
417    pub const fn split_first_chunk_mut<const N: usize>(
418        &mut self,
419    ) -> Option<(&mut [T; N], &mut [T])> {
420        let Some((first, tail)) = self.split_at_mut_checked(N) else { return None };
421
422        // SAFETY: We explicitly check for the correct number of elements,
423        //   do not let the reference outlive the slice,
424        //   and enforce exclusive mutability of the chunk by the split.
425        Some((unsafe { &mut *(first.as_mut_ptr().cast::<[T; N]>()) }, tail))
426    }
427
428    /// Returns an array reference to the last `N` items in the slice and the remaining slice.
429    ///
430    /// If the slice is not at least `N` in length, this will return `None`.
431    ///
432    /// # Examples
433    ///
434    /// ```
435    /// let x = &[0, 1, 2];
436    ///
437    /// if let Some((elements, last)) = x.split_last_chunk::<2>() {
438    ///     assert_eq!(elements, &[0]);
439    ///     assert_eq!(last, &[1, 2]);
440    /// }
441    ///
442    /// assert_eq!(None, x.split_last_chunk::<4>());
443    /// ```
444    #[inline]
445    #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
446    #[rustc_const_stable(feature = "slice_first_last_chunk", since = "1.77.0")]
447    pub const fn split_last_chunk<const N: usize>(&self) -> Option<(&[T], &[T; N])> {
448        let Some(index) = self.len().checked_sub(N) else { return None };
449        let (init, last) = self.split_at(index);
450
451        // SAFETY: We explicitly check for the correct number of elements,
452        //   and do not let the references outlive the slice.
453        Some((init, unsafe { &*(last.as_ptr().cast::<[T; N]>()) }))
454    }
455
456    /// Returns a mutable array reference to the last `N` items in the slice and the remaining
457    /// slice.
458    ///
459    /// If the slice is not at least `N` in length, this will return `None`.
460    ///
461    /// # Examples
462    ///
463    /// ```
464    /// let x = &mut [0, 1, 2];
465    ///
466    /// if let Some((elements, last)) = x.split_last_chunk_mut::<2>() {
467    ///     last[0] = 3;
468    ///     last[1] = 4;
469    ///     elements[0] = 5;
470    /// }
471    /// assert_eq!(x, &[5, 3, 4]);
472    ///
473    /// assert_eq!(None, x.split_last_chunk_mut::<4>());
474    /// ```
475    #[inline]
476    #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
477    #[rustc_const_stable(feature = "const_slice_first_last_chunk", since = "1.83.0")]
478    pub const fn split_last_chunk_mut<const N: usize>(
479        &mut self,
480    ) -> Option<(&mut [T], &mut [T; N])> {
481        let Some(index) = self.len().checked_sub(N) else { return None };
482        let (init, last) = self.split_at_mut(index);
483
484        // SAFETY: We explicitly check for the correct number of elements,
485        //   do not let the reference outlive the slice,
486        //   and enforce exclusive mutability of the chunk by the split.
487        Some((init, unsafe { &mut *(last.as_mut_ptr().cast::<[T; N]>()) }))
488    }
489
490    /// Returns an array reference to the last `N` items in the slice.
491    ///
492    /// If the slice is not at least `N` in length, this will return `None`.
493    ///
494    /// # Examples
495    ///
496    /// ```
497    /// let u = [10, 40, 30];
498    /// assert_eq!(Some(&[40, 30]), u.last_chunk::<2>());
499    ///
500    /// let v: &[i32] = &[10];
501    /// assert_eq!(None, v.last_chunk::<2>());
502    ///
503    /// let w: &[i32] = &[];
504    /// assert_eq!(Some(&[]), w.last_chunk::<0>());
505    /// ```
506    #[inline]
507    #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
508    #[rustc_const_stable(feature = "const_slice_last_chunk", since = "1.80.0")]
509    pub const fn last_chunk<const N: usize>(&self) -> Option<&[T; N]> {
510        // FIXME(const-hack): Without const traits, we need this instead of `get`.
511        let Some(index) = self.len().checked_sub(N) else { return None };
512        let (_, last) = self.split_at(index);
513
514        // SAFETY: We explicitly check for the correct number of elements,
515        //   and do not let the references outlive the slice.
516        Some(unsafe { &*(last.as_ptr().cast::<[T; N]>()) })
517    }
518
519    /// Returns a mutable array reference to the last `N` items in the slice.
520    ///
521    /// If the slice is not at least `N` in length, this will return `None`.
522    ///
523    /// # Examples
524    ///
525    /// ```
526    /// let x = &mut [0, 1, 2];
527    ///
528    /// if let Some(last) = x.last_chunk_mut::<2>() {
529    ///     last[0] = 10;
530    ///     last[1] = 20;
531    /// }
532    /// assert_eq!(x, &[0, 10, 20]);
533    ///
534    /// assert_eq!(None, x.last_chunk_mut::<4>());
535    /// ```
536    #[inline]
537    #[stable(feature = "slice_first_last_chunk", since = "1.77.0")]
538    #[rustc_const_stable(feature = "const_slice_first_last_chunk", since = "1.83.0")]
539    pub const fn last_chunk_mut<const N: usize>(&mut self) -> Option<&mut [T; N]> {
540        // FIXME(const-hack): Without const traits, we need this instead of `get`.
541        let Some(index) = self.len().checked_sub(N) else { return None };
542        let (_, last) = self.split_at_mut(index);
543
544        // SAFETY: We explicitly check for the correct number of elements,
545        //   do not let the reference outlive the slice,
546        //   and require exclusive access to the entire slice to mutate the chunk.
547        Some(unsafe { &mut *(last.as_mut_ptr().cast::<[T; N]>()) })
548    }
549
550    /// Returns a reference to an element or subslice depending on the type of
551    /// index.
552    ///
553    /// - If given a position, returns a reference to the element at that
554    ///   position or `None` if out of bounds.
555    /// - If given a range, returns the subslice corresponding to that range,
556    ///   or `None` if out of bounds.
557    ///
558    /// # Examples
559    ///
560    /// ```
561    /// let v = [10, 40, 30];
562    /// assert_eq!(Some(&40), v.get(1));
563    /// assert_eq!(Some(&[10, 40][..]), v.get(0..2));
564    /// assert_eq!(None, v.get(3));
565    /// assert_eq!(None, v.get(0..4));
566    /// ```
567    #[stable(feature = "rust1", since = "1.0.0")]
568    #[rustc_no_implicit_autorefs]
569    #[inline]
570    #[must_use]
571    pub fn get<I>(&self, index: I) -> Option<&I::Output>
572    where
573        I: SliceIndex<Self>,
574    {
575        index.get(self)
576    }
577
578    /// Returns a mutable reference to an element or subslice depending on the
579    /// type of index (see [`get`]) or `None` if the index is out of bounds.
580    ///
581    /// [`get`]: slice::get
582    ///
583    /// # Examples
584    ///
585    /// ```
586    /// let x = &mut [0, 1, 2];
587    ///
588    /// if let Some(elem) = x.get_mut(1) {
589    ///     *elem = 42;
590    /// }
591    /// assert_eq!(x, &[0, 42, 2]);
592    /// ```
593    #[stable(feature = "rust1", since = "1.0.0")]
594    #[rustc_no_implicit_autorefs]
595    #[inline]
596    #[must_use]
597    pub fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
598    where
599        I: SliceIndex<Self>,
600    {
601        index.get_mut(self)
602    }
603
604    /// Returns a reference to an element or subslice, without doing bounds
605    /// checking.
606    ///
607    /// For a safe alternative see [`get`].
608    ///
609    /// # Safety
610    ///
611    /// Calling this method with an out-of-bounds index is *[undefined behavior]*
612    /// even if the resulting reference is not used.
613    ///
614    /// You can think of this like `.get(index).unwrap_unchecked()`.  It's UB
615    /// to call `.get_unchecked(len)`, even if you immediately convert to a
616    /// pointer.  And it's UB to call `.get_unchecked(..len + 1)`,
617    /// `.get_unchecked(..=len)`, or similar.
618    ///
619    /// [`get`]: slice::get
620    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
621    ///
622    /// # Examples
623    ///
624    /// ```
625    /// let x = &[1, 2, 4];
626    ///
627    /// unsafe {
628    ///     assert_eq!(x.get_unchecked(1), &2);
629    /// }
630    /// ```
631    #[stable(feature = "rust1", since = "1.0.0")]
632    #[rustc_no_implicit_autorefs]
633    #[inline]
634    #[must_use]
635    #[track_caller]
636    pub unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
637    where
638        I: SliceIndex<Self>,
639    {
640        // SAFETY: the caller must uphold most of the safety requirements for `get_unchecked`;
641        // the slice is dereferenceable because `self` is a safe reference.
642        // The returned pointer is safe because impls of `SliceIndex` have to guarantee that it is.
643        unsafe { &*index.get_unchecked(self) }
644    }
645
646    /// Returns a mutable reference to an element or subslice, without doing
647    /// bounds checking.
648    ///
649    /// For a safe alternative see [`get_mut`].
650    ///
651    /// # Safety
652    ///
653    /// Calling this method with an out-of-bounds index is *[undefined behavior]*
654    /// even if the resulting reference is not used.
655    ///
656    /// You can think of this like `.get_mut(index).unwrap_unchecked()`.  It's
657    /// UB to call `.get_unchecked_mut(len)`, even if you immediately convert
658    /// to a pointer.  And it's UB to call `.get_unchecked_mut(..len + 1)`,
659    /// `.get_unchecked_mut(..=len)`, or similar.
660    ///
661    /// [`get_mut`]: slice::get_mut
662    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
663    ///
664    /// # Examples
665    ///
666    /// ```
667    /// let x = &mut [1, 2, 4];
668    ///
669    /// unsafe {
670    ///     let elem = x.get_unchecked_mut(1);
671    ///     *elem = 13;
672    /// }
673    /// assert_eq!(x, &[1, 13, 4]);
674    /// ```
675    #[stable(feature = "rust1", since = "1.0.0")]
676    #[rustc_no_implicit_autorefs]
677    #[inline]
678    #[must_use]
679    #[track_caller]
680    pub unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
681    where
682        I: SliceIndex<Self>,
683    {
684        // SAFETY: the caller must uphold the safety requirements for `get_unchecked_mut`;
685        // the slice is dereferenceable because `self` is a safe reference.
686        // The returned pointer is safe because impls of `SliceIndex` have to guarantee that it is.
687        unsafe { &mut *index.get_unchecked_mut(self) }
688    }
689
690    /// Returns a raw pointer to the slice's buffer.
691    ///
692    /// The caller must ensure that the slice outlives the pointer this
693    /// function returns, or else it will end up dangling.
694    ///
695    /// The caller must also ensure that the memory the pointer (non-transitively) points to
696    /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
697    /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
698    ///
699    /// Modifying the container referenced by this slice may cause its buffer
700    /// to be reallocated, which would also make any pointers to it invalid.
701    ///
702    /// # Examples
703    ///
704    /// ```
705    /// let x = &[1, 2, 4];
706    /// let x_ptr = x.as_ptr();
707    ///
708    /// unsafe {
709    ///     for i in 0..x.len() {
710    ///         assert_eq!(x.get_unchecked(i), &*x_ptr.add(i));
711    ///     }
712    /// }
713    /// ```
714    ///
715    /// [`as_mut_ptr`]: slice::as_mut_ptr
716    #[stable(feature = "rust1", since = "1.0.0")]
717    #[rustc_const_stable(feature = "const_slice_as_ptr", since = "1.32.0")]
718    #[rustc_never_returns_null_ptr]
719    #[rustc_as_ptr]
720    #[inline(always)]
721    #[must_use]
722    pub const fn as_ptr(&self) -> *const T {
723        self as *const [T] as *const T
724    }
725
726    /// Returns an unsafe mutable pointer to the slice's buffer.
727    ///
728    /// The caller must ensure that the slice outlives the pointer this
729    /// function returns, or else it will end up dangling.
730    ///
731    /// Modifying the container referenced by this slice may cause its buffer
732    /// to be reallocated, which would also make any pointers to it invalid.
733    ///
734    /// # Examples
735    ///
736    /// ```
737    /// let x = &mut [1, 2, 4];
738    /// let x_ptr = x.as_mut_ptr();
739    ///
740    /// unsafe {
741    ///     for i in 0..x.len() {
742    ///         *x_ptr.add(i) += 2;
743    ///     }
744    /// }
745    /// assert_eq!(x, &[3, 4, 6]);
746    /// ```
747    #[stable(feature = "rust1", since = "1.0.0")]
748    #[rustc_const_stable(feature = "const_ptr_offset", since = "1.61.0")]
749    #[rustc_never_returns_null_ptr]
750    #[rustc_as_ptr]
751    #[inline(always)]
752    #[must_use]
753    pub const fn as_mut_ptr(&mut self) -> *mut T {
754        self as *mut [T] as *mut T
755    }
756
757    /// Returns the two raw pointers spanning the slice.
758    ///
759    /// The returned range is half-open, which means that the end pointer
760    /// points *one past* the last element of the slice. This way, an empty
761    /// slice is represented by two equal pointers, and the difference between
762    /// the two pointers represents the size of the slice.
763    ///
764    /// See [`as_ptr`] for warnings on using these pointers. The end pointer
765    /// requires extra caution, as it does not point to a valid element in the
766    /// slice.
767    ///
768    /// This function is useful for interacting with foreign interfaces which
769    /// use two pointers to refer to a range of elements in memory, as is
770    /// common in C++.
771    ///
772    /// It can also be useful to check if a pointer to an element refers to an
773    /// element of this slice:
774    ///
775    /// ```
776    /// let a = [1, 2, 3];
777    /// let x = &a[1] as *const _;
778    /// let y = &5 as *const _;
779    ///
780    /// assert!(a.as_ptr_range().contains(&x));
781    /// assert!(!a.as_ptr_range().contains(&y));
782    /// ```
783    ///
784    /// [`as_ptr`]: slice::as_ptr
785    #[stable(feature = "slice_ptr_range", since = "1.48.0")]
786    #[rustc_const_stable(feature = "const_ptr_offset", since = "1.61.0")]
787    #[inline]
788    #[must_use]
789    pub const fn as_ptr_range(&self) -> Range<*const T> {
790        let start = self.as_ptr();
791        // SAFETY: The `add` here is safe, because:
792        //
793        //   - Both pointers are part of the same object, as pointing directly
794        //     past the object also counts.
795        //
796        //   - The size of the slice is never larger than `isize::MAX` bytes, as
797        //     noted here:
798        //       - https://github.com/rust-lang/unsafe-code-guidelines/issues/102#issuecomment-473340447
799        //       - https://doc.rust-lang.org/reference/behavior-considered-undefined.html
800        //       - https://doc.rust-lang.org/core/slice/fn.from_raw_parts.html#safety
801        //     (This doesn't seem normative yet, but the very same assumption is
802        //     made in many places, including the Index implementation of slices.)
803        //
804        //   - There is no wrapping around involved, as slices do not wrap past
805        //     the end of the address space.
806        //
807        // See the documentation of [`pointer::add`].
808        let end = unsafe { start.add(self.len()) };
809        start..end
810    }
811
812    /// Returns the two unsafe mutable pointers spanning the slice.
813    ///
814    /// The returned range is half-open, which means that the end pointer
815    /// points *one past* the last element of the slice. This way, an empty
816    /// slice is represented by two equal pointers, and the difference between
817    /// the two pointers represents the size of the slice.
818    ///
819    /// See [`as_mut_ptr`] for warnings on using these pointers. The end
820    /// pointer requires extra caution, as it does not point to a valid element
821    /// in the slice.
822    ///
823    /// This function is useful for interacting with foreign interfaces which
824    /// use two pointers to refer to a range of elements in memory, as is
825    /// common in C++.
826    ///
827    /// [`as_mut_ptr`]: slice::as_mut_ptr
828    #[stable(feature = "slice_ptr_range", since = "1.48.0")]
829    #[rustc_const_stable(feature = "const_ptr_offset", since = "1.61.0")]
830    #[inline]
831    #[must_use]
832    pub const fn as_mut_ptr_range(&mut self) -> Range<*mut T> {
833        let start = self.as_mut_ptr();
834        // SAFETY: See as_ptr_range() above for why `add` here is safe.
835        let end = unsafe { start.add(self.len()) };
836        start..end
837    }
838
839    /// Gets a reference to the underlying array.
840    ///
841    /// If `N` is not exactly equal to the length of `self`, then this method returns `None`.
842    #[unstable(feature = "slice_as_array", issue = "133508")]
843    #[inline]
844    #[must_use]
845    pub const fn as_array<const N: usize>(&self) -> Option<&[T; N]> {
846        if self.len() == N {
847            let ptr = self.as_ptr() as *const [T; N];
848
849            // SAFETY: The underlying array of a slice can be reinterpreted as an actual array `[T; N]` if `N` is not greater than the slice's length.
850            let me = unsafe { &*ptr };
851            Some(me)
852        } else {
853            None
854        }
855    }
856
857    /// Gets a mutable reference to the slice's underlying array.
858    ///
859    /// If `N` is not exactly equal to the length of `self`, then this method returns `None`.
860    #[unstable(feature = "slice_as_array", issue = "133508")]
861    #[inline]
862    #[must_use]
863    pub const fn as_mut_array<const N: usize>(&mut self) -> Option<&mut [T; N]> {
864        if self.len() == N {
865            let ptr = self.as_mut_ptr() as *mut [T; N];
866
867            // SAFETY: The underlying array of a slice can be reinterpreted as an actual array `[T; N]` if `N` is not greater than the slice's length.
868            let me = unsafe { &mut *ptr };
869            Some(me)
870        } else {
871            None
872        }
873    }
874
875    /// Swaps two elements in the slice.
876    ///
877    /// If `a` equals to `b`, it's guaranteed that elements won't change value.
878    ///
879    /// # Arguments
880    ///
881    /// * a - The index of the first element
882    /// * b - The index of the second element
883    ///
884    /// # Panics
885    ///
886    /// Panics if `a` or `b` are out of bounds.
887    ///
888    /// # Examples
889    ///
890    /// ```
891    /// let mut v = ["a", "b", "c", "d", "e"];
892    /// v.swap(2, 4);
893    /// assert!(v == ["a", "b", "e", "d", "c"]);
894    /// ```
895    #[stable(feature = "rust1", since = "1.0.0")]
896    #[rustc_const_stable(feature = "const_swap", since = "1.85.0")]
897    #[inline]
898    #[track_caller]
899    pub const fn swap(&mut self, a: usize, b: usize) {
900        // FIXME: use swap_unchecked here (https://github.com/rust-lang/rust/pull/88540#issuecomment-944344343)
901        // Can't take two mutable loans from one vector, so instead use raw pointers.
902        let pa = &raw mut self[a];
903        let pb = &raw mut self[b];
904        // SAFETY: `pa` and `pb` have been created from safe mutable references and refer
905        // to elements in the slice and therefore are guaranteed to be valid and aligned.
906        // Note that accessing the elements behind `a` and `b` is checked and will
907        // panic when out of bounds.
908        unsafe {
909            ptr::swap(pa, pb);
910        }
911    }
912
913    /// Swaps two elements in the slice, without doing bounds checking.
914    ///
915    /// For a safe alternative see [`swap`].
916    ///
917    /// # Arguments
918    ///
919    /// * a - The index of the first element
920    /// * b - The index of the second element
921    ///
922    /// # Safety
923    ///
924    /// Calling this method with an out-of-bounds index is *[undefined behavior]*.
925    /// The caller has to ensure that `a < self.len()` and `b < self.len()`.
926    ///
927    /// # Examples
928    ///
929    /// ```
930    /// #![feature(slice_swap_unchecked)]
931    ///
932    /// let mut v = ["a", "b", "c", "d"];
933    /// // SAFETY: we know that 1 and 3 are both indices of the slice
934    /// unsafe { v.swap_unchecked(1, 3) };
935    /// assert!(v == ["a", "d", "c", "b"]);
936    /// ```
937    ///
938    /// [`swap`]: slice::swap
939    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
940    #[unstable(feature = "slice_swap_unchecked", issue = "88539")]
941    #[track_caller]
942    pub const unsafe fn swap_unchecked(&mut self, a: usize, b: usize) {
943        assert_unsafe_precondition!(
944            check_library_ub,
945            "slice::swap_unchecked requires that the indices are within the slice",
946            (
947                len: usize = self.len(),
948                a: usize = a,
949                b: usize = b,
950            ) => a < len && b < len,
951        );
952
953        let ptr = self.as_mut_ptr();
954        // SAFETY: caller has to guarantee that `a < self.len()` and `b < self.len()`
955        unsafe {
956            ptr::swap(ptr.add(a), ptr.add(b));
957        }
958    }
959
960    /// Reverses the order of elements in the slice, in place.
961    ///
962    /// # Examples
963    ///
964    /// ```
965    /// let mut v = [1, 2, 3];
966    /// v.reverse();
967    /// assert!(v == [3, 2, 1]);
968    /// ```
969    #[stable(feature = "rust1", since = "1.0.0")]
970    #[rustc_const_unstable(feature = "const_slice_reverse", issue = "135120")]
971    #[inline]
972    pub const fn reverse(&mut self) {
973        let half_len = self.len() / 2;
974        let Range { start, end } = self.as_mut_ptr_range();
975
976        // These slices will skip the middle item for an odd length,
977        // since that one doesn't need to move.
978        let (front_half, back_half) =
979            // SAFETY: Both are subparts of the original slice, so the memory
980            // range is valid, and they don't overlap because they're each only
981            // half (or less) of the original slice.
982            unsafe {
983                (
984                    slice::from_raw_parts_mut(start, half_len),
985                    slice::from_raw_parts_mut(end.sub(half_len), half_len),
986                )
987            };
988
989        // Introducing a function boundary here means that the two halves
990        // get `noalias` markers, allowing better optimization as LLVM
991        // knows that they're disjoint, unlike in the original slice.
992        revswap(front_half, back_half, half_len);
993
994        #[inline]
995        const fn revswap<T>(a: &mut [T], b: &mut [T], n: usize) {
996            debug_assert!(a.len() == n);
997            debug_assert!(b.len() == n);
998
999            // Because this function is first compiled in isolation,
1000            // this check tells LLVM that the indexing below is
1001            // in-bounds. Then after inlining -- once the actual
1002            // lengths of the slices are known -- it's removed.
1003            let (a, _) = a.split_at_mut(n);
1004            let (b, _) = b.split_at_mut(n);
1005
1006            let mut i = 0;
1007            while i < n {
1008                mem::swap(&mut a[i], &mut b[n - 1 - i]);
1009                i += 1;
1010            }
1011        }
1012    }
1013
1014    /// Returns an iterator over the slice.
1015    ///
1016    /// The iterator yields all items from start to end.
1017    ///
1018    /// # Examples
1019    ///
1020    /// ```
1021    /// let x = &[1, 2, 4];
1022    /// let mut iterator = x.iter();
1023    ///
1024    /// assert_eq!(iterator.next(), Some(&1));
1025    /// assert_eq!(iterator.next(), Some(&2));
1026    /// assert_eq!(iterator.next(), Some(&4));
1027    /// assert_eq!(iterator.next(), None);
1028    /// ```
1029    #[stable(feature = "rust1", since = "1.0.0")]
1030    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1031    #[inline]
1032    #[rustc_diagnostic_item = "slice_iter"]
1033    pub const fn iter(&self) -> Iter<'_, T> {
1034        Iter::new(self)
1035    }
1036
1037    /// Returns an iterator that allows modifying each value.
1038    ///
1039    /// The iterator yields all items from start to end.
1040    ///
1041    /// # Examples
1042    ///
1043    /// ```
1044    /// let x = &mut [1, 2, 4];
1045    /// for elem in x.iter_mut() {
1046    ///     *elem += 2;
1047    /// }
1048    /// assert_eq!(x, &[3, 4, 6]);
1049    /// ```
1050    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1051    #[stable(feature = "rust1", since = "1.0.0")]
1052    #[inline]
1053    pub const fn iter_mut(&mut self) -> IterMut<'_, T> {
1054        IterMut::new(self)
1055    }
1056
1057    /// Returns an iterator over all contiguous windows of length
1058    /// `size`. The windows overlap. If the slice is shorter than
1059    /// `size`, the iterator returns no values.
1060    ///
1061    /// # Panics
1062    ///
1063    /// Panics if `size` is zero.
1064    ///
1065    /// # Examples
1066    ///
1067    /// ```
1068    /// let slice = ['l', 'o', 'r', 'e', 'm'];
1069    /// let mut iter = slice.windows(3);
1070    /// assert_eq!(iter.next().unwrap(), &['l', 'o', 'r']);
1071    /// assert_eq!(iter.next().unwrap(), &['o', 'r', 'e']);
1072    /// assert_eq!(iter.next().unwrap(), &['r', 'e', 'm']);
1073    /// assert!(iter.next().is_none());
1074    /// ```
1075    ///
1076    /// If the slice is shorter than `size`:
1077    ///
1078    /// ```
1079    /// let slice = ['f', 'o', 'o'];
1080    /// let mut iter = slice.windows(4);
1081    /// assert!(iter.next().is_none());
1082    /// ```
1083    ///
1084    /// Because the [Iterator] trait cannot represent the required lifetimes,
1085    /// there is no `windows_mut` analog to `windows`;
1086    /// `[0,1,2].windows_mut(2).collect()` would violate [the rules of references]
1087    /// (though a [LendingIterator] analog is possible). You can sometimes use
1088    /// [`Cell::as_slice_of_cells`](crate::cell::Cell::as_slice_of_cells) in
1089    /// conjunction with `windows` instead:
1090    ///
1091    /// [the rules of references]: https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html#the-rules-of-references
1092    /// [LendingIterator]: https://blog.rust-lang.org/2022/10/28/gats-stabilization.html
1093    /// ```
1094    /// use std::cell::Cell;
1095    ///
1096    /// let mut array = ['R', 'u', 's', 't', ' ', '2', '0', '1', '5'];
1097    /// let slice = &mut array[..];
1098    /// let slice_of_cells: &[Cell<char>] = Cell::from_mut(slice).as_slice_of_cells();
1099    /// for w in slice_of_cells.windows(3) {
1100    ///     Cell::swap(&w[0], &w[2]);
1101    /// }
1102    /// assert_eq!(array, ['s', 't', ' ', '2', '0', '1', '5', 'u', 'R']);
1103    /// ```
1104    #[stable(feature = "rust1", since = "1.0.0")]
1105    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1106    #[inline]
1107    #[track_caller]
1108    pub const fn windows(&self, size: usize) -> Windows<'_, T> {
1109        let size = NonZero::new(size).expect("window size must be non-zero");
1110        Windows::new(self, size)
1111    }
1112
1113    /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1114    /// beginning of the slice.
1115    ///
1116    /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
1117    /// slice, then the last chunk will not have length `chunk_size`.
1118    ///
1119    /// See [`chunks_exact`] for a variant of this iterator that returns chunks of always exactly
1120    /// `chunk_size` elements, and [`rchunks`] for the same iterator but starting at the end of the
1121    /// slice.
1122    ///
1123    /// # Panics
1124    ///
1125    /// Panics if `chunk_size` is zero.
1126    ///
1127    /// # Examples
1128    ///
1129    /// ```
1130    /// let slice = ['l', 'o', 'r', 'e', 'm'];
1131    /// let mut iter = slice.chunks(2);
1132    /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
1133    /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
1134    /// assert_eq!(iter.next().unwrap(), &['m']);
1135    /// assert!(iter.next().is_none());
1136    /// ```
1137    ///
1138    /// [`chunks_exact`]: slice::chunks_exact
1139    /// [`rchunks`]: slice::rchunks
1140    #[stable(feature = "rust1", since = "1.0.0")]
1141    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1142    #[inline]
1143    #[track_caller]
1144    pub const fn chunks(&self, chunk_size: usize) -> Chunks<'_, T> {
1145        assert!(chunk_size != 0, "chunk size must be non-zero");
1146        Chunks::new(self, chunk_size)
1147    }
1148
1149    /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1150    /// beginning of the slice.
1151    ///
1152    /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
1153    /// length of the slice, then the last chunk will not have length `chunk_size`.
1154    ///
1155    /// See [`chunks_exact_mut`] for a variant of this iterator that returns chunks of always
1156    /// exactly `chunk_size` elements, and [`rchunks_mut`] for the same iterator but starting at
1157    /// the end of the slice.
1158    ///
1159    /// # Panics
1160    ///
1161    /// Panics if `chunk_size` is zero.
1162    ///
1163    /// # Examples
1164    ///
1165    /// ```
1166    /// let v = &mut [0, 0, 0, 0, 0];
1167    /// let mut count = 1;
1168    ///
1169    /// for chunk in v.chunks_mut(2) {
1170    ///     for elem in chunk.iter_mut() {
1171    ///         *elem += count;
1172    ///     }
1173    ///     count += 1;
1174    /// }
1175    /// assert_eq!(v, &[1, 1, 2, 2, 3]);
1176    /// ```
1177    ///
1178    /// [`chunks_exact_mut`]: slice::chunks_exact_mut
1179    /// [`rchunks_mut`]: slice::rchunks_mut
1180    #[stable(feature = "rust1", since = "1.0.0")]
1181    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1182    #[inline]
1183    #[track_caller]
1184    pub const fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<'_, T> {
1185        assert!(chunk_size != 0, "chunk size must be non-zero");
1186        ChunksMut::new(self, chunk_size)
1187    }
1188
1189    /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1190    /// beginning of the slice.
1191    ///
1192    /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
1193    /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved
1194    /// from the `remainder` function of the iterator.
1195    ///
1196    /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
1197    /// resulting code better than in the case of [`chunks`].
1198    ///
1199    /// See [`chunks`] for a variant of this iterator that also returns the remainder as a smaller
1200    /// chunk, and [`rchunks_exact`] for the same iterator but starting at the end of the slice.
1201    ///
1202    /// # Panics
1203    ///
1204    /// Panics if `chunk_size` is zero.
1205    ///
1206    /// # Examples
1207    ///
1208    /// ```
1209    /// let slice = ['l', 'o', 'r', 'e', 'm'];
1210    /// let mut iter = slice.chunks_exact(2);
1211    /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
1212    /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
1213    /// assert!(iter.next().is_none());
1214    /// assert_eq!(iter.remainder(), &['m']);
1215    /// ```
1216    ///
1217    /// [`chunks`]: slice::chunks
1218    /// [`rchunks_exact`]: slice::rchunks_exact
1219    #[stable(feature = "chunks_exact", since = "1.31.0")]
1220    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1221    #[inline]
1222    #[track_caller]
1223    pub const fn chunks_exact(&self, chunk_size: usize) -> ChunksExact<'_, T> {
1224        assert!(chunk_size != 0, "chunk size must be non-zero");
1225        ChunksExact::new(self, chunk_size)
1226    }
1227
1228    /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1229    /// beginning of the slice.
1230    ///
1231    /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
1232    /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be
1233    /// retrieved from the `into_remainder` function of the iterator.
1234    ///
1235    /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
1236    /// resulting code better than in the case of [`chunks_mut`].
1237    ///
1238    /// See [`chunks_mut`] for a variant of this iterator that also returns the remainder as a
1239    /// smaller chunk, and [`rchunks_exact_mut`] for the same iterator but starting at the end of
1240    /// the slice.
1241    ///
1242    /// # Panics
1243    ///
1244    /// Panics if `chunk_size` is zero.
1245    ///
1246    /// # Examples
1247    ///
1248    /// ```
1249    /// let v = &mut [0, 0, 0, 0, 0];
1250    /// let mut count = 1;
1251    ///
1252    /// for chunk in v.chunks_exact_mut(2) {
1253    ///     for elem in chunk.iter_mut() {
1254    ///         *elem += count;
1255    ///     }
1256    ///     count += 1;
1257    /// }
1258    /// assert_eq!(v, &[1, 1, 2, 2, 0]);
1259    /// ```
1260    ///
1261    /// [`chunks_mut`]: slice::chunks_mut
1262    /// [`rchunks_exact_mut`]: slice::rchunks_exact_mut
1263    #[stable(feature = "chunks_exact", since = "1.31.0")]
1264    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1265    #[inline]
1266    #[track_caller]
1267    pub const fn chunks_exact_mut(&mut self, chunk_size: usize) -> ChunksExactMut<'_, T> {
1268        assert!(chunk_size != 0, "chunk size must be non-zero");
1269        ChunksExactMut::new(self, chunk_size)
1270    }
1271
1272    /// Splits the slice into a slice of `N`-element arrays,
1273    /// assuming that there's no remainder.
1274    ///
1275    /// This is the inverse operation to [`as_flattened`].
1276    ///
1277    /// [`as_flattened`]: slice::as_flattened
1278    ///
1279    /// As this is `unsafe`, consider whether you could use [`as_chunks`] or
1280    /// [`as_rchunks`] instead, perhaps via something like
1281    /// `if let (chunks, []) = slice.as_chunks()` or
1282    /// `let (chunks, []) = slice.as_chunks() else { unreachable!() };`.
1283    ///
1284    /// [`as_chunks`]: slice::as_chunks
1285    /// [`as_rchunks`]: slice::as_rchunks
1286    ///
1287    /// # Safety
1288    ///
1289    /// This may only be called when
1290    /// - The slice splits exactly into `N`-element chunks (aka `self.len() % N == 0`).
1291    /// - `N != 0`.
1292    ///
1293    /// # Examples
1294    ///
1295    /// ```
1296    /// let slice: &[char] = &['l', 'o', 'r', 'e', 'm', '!'];
1297    /// let chunks: &[[char; 1]] =
1298    ///     // SAFETY: 1-element chunks never have remainder
1299    ///     unsafe { slice.as_chunks_unchecked() };
1300    /// assert_eq!(chunks, &[['l'], ['o'], ['r'], ['e'], ['m'], ['!']]);
1301    /// let chunks: &[[char; 3]] =
1302    ///     // SAFETY: The slice length (6) is a multiple of 3
1303    ///     unsafe { slice.as_chunks_unchecked() };
1304    /// assert_eq!(chunks, &[['l', 'o', 'r'], ['e', 'm', '!']]);
1305    ///
1306    /// // These would be unsound:
1307    /// // let chunks: &[[_; 5]] = slice.as_chunks_unchecked() // The slice length is not a multiple of 5
1308    /// // let chunks: &[[_; 0]] = slice.as_chunks_unchecked() // Zero-length chunks are never allowed
1309    /// ```
1310    #[stable(feature = "slice_as_chunks", since = "1.88.0")]
1311    #[rustc_const_stable(feature = "slice_as_chunks", since = "1.88.0")]
1312    #[inline]
1313    #[must_use]
1314    #[track_caller]
1315    pub const unsafe fn as_chunks_unchecked<const N: usize>(&self) -> &[[T; N]] {
1316        assert_unsafe_precondition!(
1317            check_language_ub,
1318            "slice::as_chunks_unchecked requires `N != 0` and the slice to split exactly into `N`-element chunks",
1319            (n: usize = N, len: usize = self.len()) => n != 0 && len.is_multiple_of(n),
1320        );
1321        // SAFETY: Caller must guarantee that `N` is nonzero and exactly divides the slice length
1322        let new_len = unsafe { exact_div(self.len(), N) };
1323        // SAFETY: We cast a slice of `new_len * N` elements into
1324        // a slice of `new_len` many `N` elements chunks.
1325        unsafe { from_raw_parts(self.as_ptr().cast(), new_len) }
1326    }
1327
1328    /// Splits the slice into a slice of `N`-element arrays,
1329    /// starting at the beginning of the slice,
1330    /// and a remainder slice with length strictly less than `N`.
1331    ///
1332    /// The remainder is meaningful in the division sense.  Given
1333    /// `let (chunks, remainder) = slice.as_chunks()`, then:
1334    /// - `chunks.len()` equals `slice.len() / N`,
1335    /// - `remainder.len()` equals `slice.len() % N`, and
1336    /// - `slice.len()` equals `chunks.len() * N + remainder.len()`.
1337    ///
1338    /// You can flatten the chunks back into a slice-of-`T` with [`as_flattened`].
1339    ///
1340    /// [`as_flattened`]: slice::as_flattened
1341    ///
1342    /// # Panics
1343    ///
1344    /// Panics if `N` is zero.
1345    ///
1346    /// Note that this check is against a const generic parameter, not a runtime
1347    /// value, and thus a particular monomorphization will either always panic
1348    /// or it will never panic.
1349    ///
1350    /// # Examples
1351    ///
1352    /// ```
1353    /// let slice = ['l', 'o', 'r', 'e', 'm'];
1354    /// let (chunks, remainder) = slice.as_chunks();
1355    /// assert_eq!(chunks, &[['l', 'o'], ['r', 'e']]);
1356    /// assert_eq!(remainder, &['m']);
1357    /// ```
1358    ///
1359    /// If you expect the slice to be an exact multiple, you can combine
1360    /// `let`-`else` with an empty slice pattern:
1361    /// ```
1362    /// let slice = ['R', 'u', 's', 't'];
1363    /// let (chunks, []) = slice.as_chunks::<2>() else {
1364    ///     panic!("slice didn't have even length")
1365    /// };
1366    /// assert_eq!(chunks, &[['R', 'u'], ['s', 't']]);
1367    /// ```
1368    #[stable(feature = "slice_as_chunks", since = "1.88.0")]
1369    #[rustc_const_stable(feature = "slice_as_chunks", since = "1.88.0")]
1370    #[inline]
1371    #[track_caller]
1372    #[must_use]
1373    pub const fn as_chunks<const N: usize>(&self) -> (&[[T; N]], &[T]) {
1374        assert!(N != 0, "chunk size must be non-zero");
1375        let len_rounded_down = self.len() / N * N;
1376        // SAFETY: The rounded-down value is always the same or smaller than the
1377        // original length, and thus must be in-bounds of the slice.
1378        let (multiple_of_n, remainder) = unsafe { self.split_at_unchecked(len_rounded_down) };
1379        // SAFETY: We already panicked for zero, and ensured by construction
1380        // that the length of the subslice is a multiple of N.
1381        let array_slice = unsafe { multiple_of_n.as_chunks_unchecked() };
1382        (array_slice, remainder)
1383    }
1384
1385    /// Splits the slice into a slice of `N`-element arrays,
1386    /// starting at the end of the slice,
1387    /// and a remainder slice with length strictly less than `N`.
1388    ///
1389    /// The remainder is meaningful in the division sense.  Given
1390    /// `let (remainder, chunks) = slice.as_rchunks()`, then:
1391    /// - `remainder.len()` equals `slice.len() % N`,
1392    /// - `chunks.len()` equals `slice.len() / N`, and
1393    /// - `slice.len()` equals `chunks.len() * N + remainder.len()`.
1394    ///
1395    /// You can flatten the chunks back into a slice-of-`T` with [`as_flattened`].
1396    ///
1397    /// [`as_flattened`]: slice::as_flattened
1398    ///
1399    /// # Panics
1400    ///
1401    /// Panics if `N` is zero.
1402    ///
1403    /// Note that this check is against a const generic parameter, not a runtime
1404    /// value, and thus a particular monomorphization will either always panic
1405    /// or it will never panic.
1406    ///
1407    /// # Examples
1408    ///
1409    /// ```
1410    /// let slice = ['l', 'o', 'r', 'e', 'm'];
1411    /// let (remainder, chunks) = slice.as_rchunks();
1412    /// assert_eq!(remainder, &['l']);
1413    /// assert_eq!(chunks, &[['o', 'r'], ['e', 'm']]);
1414    /// ```
1415    #[stable(feature = "slice_as_chunks", since = "1.88.0")]
1416    #[rustc_const_stable(feature = "slice_as_chunks", since = "1.88.0")]
1417    #[inline]
1418    #[track_caller]
1419    #[must_use]
1420    pub const fn as_rchunks<const N: usize>(&self) -> (&[T], &[[T; N]]) {
1421        assert!(N != 0, "chunk size must be non-zero");
1422        let len = self.len() / N;
1423        let (remainder, multiple_of_n) = self.split_at(self.len() - len * N);
1424        // SAFETY: We already panicked for zero, and ensured by construction
1425        // that the length of the subslice is a multiple of N.
1426        let array_slice = unsafe { multiple_of_n.as_chunks_unchecked() };
1427        (remainder, array_slice)
1428    }
1429
1430    /// Returns an iterator over `N` elements of the slice at a time, starting at the
1431    /// beginning of the slice.
1432    ///
1433    /// The chunks are array references and do not overlap. If `N` does not divide the
1434    /// length of the slice, then the last up to `N-1` elements will be omitted and can be
1435    /// retrieved from the `remainder` function of the iterator.
1436    ///
1437    /// This method is the const generic equivalent of [`chunks_exact`].
1438    ///
1439    /// # Panics
1440    ///
1441    /// Panics if `N` is zero. This check will most probably get changed to a compile time
1442    /// error before this method gets stabilized.
1443    ///
1444    /// # Examples
1445    ///
1446    /// ```
1447    /// #![feature(array_chunks)]
1448    /// let slice = ['l', 'o', 'r', 'e', 'm'];
1449    /// let mut iter = slice.array_chunks();
1450    /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
1451    /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
1452    /// assert!(iter.next().is_none());
1453    /// assert_eq!(iter.remainder(), &['m']);
1454    /// ```
1455    ///
1456    /// [`chunks_exact`]: slice::chunks_exact
1457    #[unstable(feature = "array_chunks", issue = "74985")]
1458    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1459    #[inline]
1460    #[track_caller]
1461    pub const fn array_chunks<const N: usize>(&self) -> ArrayChunks<'_, T, N> {
1462        assert!(N != 0, "chunk size must be non-zero");
1463        ArrayChunks::new(self)
1464    }
1465
1466    /// Splits the slice into a slice of `N`-element arrays,
1467    /// assuming that there's no remainder.
1468    ///
1469    /// This is the inverse operation to [`as_flattened_mut`].
1470    ///
1471    /// [`as_flattened_mut`]: slice::as_flattened_mut
1472    ///
1473    /// As this is `unsafe`, consider whether you could use [`as_chunks_mut`] or
1474    /// [`as_rchunks_mut`] instead, perhaps via something like
1475    /// `if let (chunks, []) = slice.as_chunks_mut()` or
1476    /// `let (chunks, []) = slice.as_chunks_mut() else { unreachable!() };`.
1477    ///
1478    /// [`as_chunks_mut`]: slice::as_chunks_mut
1479    /// [`as_rchunks_mut`]: slice::as_rchunks_mut
1480    ///
1481    /// # Safety
1482    ///
1483    /// This may only be called when
1484    /// - The slice splits exactly into `N`-element chunks (aka `self.len() % N == 0`).
1485    /// - `N != 0`.
1486    ///
1487    /// # Examples
1488    ///
1489    /// ```
1490    /// let slice: &mut [char] = &mut ['l', 'o', 'r', 'e', 'm', '!'];
1491    /// let chunks: &mut [[char; 1]] =
1492    ///     // SAFETY: 1-element chunks never have remainder
1493    ///     unsafe { slice.as_chunks_unchecked_mut() };
1494    /// chunks[0] = ['L'];
1495    /// assert_eq!(chunks, &[['L'], ['o'], ['r'], ['e'], ['m'], ['!']]);
1496    /// let chunks: &mut [[char; 3]] =
1497    ///     // SAFETY: The slice length (6) is a multiple of 3
1498    ///     unsafe { slice.as_chunks_unchecked_mut() };
1499    /// chunks[1] = ['a', 'x', '?'];
1500    /// assert_eq!(slice, &['L', 'o', 'r', 'a', 'x', '?']);
1501    ///
1502    /// // These would be unsound:
1503    /// // let chunks: &[[_; 5]] = slice.as_chunks_unchecked_mut() // The slice length is not a multiple of 5
1504    /// // let chunks: &[[_; 0]] = slice.as_chunks_unchecked_mut() // Zero-length chunks are never allowed
1505    /// ```
1506    #[stable(feature = "slice_as_chunks", since = "1.88.0")]
1507    #[rustc_const_stable(feature = "slice_as_chunks", since = "1.88.0")]
1508    #[inline]
1509    #[must_use]
1510    #[track_caller]
1511    pub const unsafe fn as_chunks_unchecked_mut<const N: usize>(&mut self) -> &mut [[T; N]] {
1512        assert_unsafe_precondition!(
1513            check_language_ub,
1514            "slice::as_chunks_unchecked requires `N != 0` and the slice to split exactly into `N`-element chunks",
1515            (n: usize = N, len: usize = self.len()) => n != 0 && len.is_multiple_of(n)
1516        );
1517        // SAFETY: Caller must guarantee that `N` is nonzero and exactly divides the slice length
1518        let new_len = unsafe { exact_div(self.len(), N) };
1519        // SAFETY: We cast a slice of `new_len * N` elements into
1520        // a slice of `new_len` many `N` elements chunks.
1521        unsafe { from_raw_parts_mut(self.as_mut_ptr().cast(), new_len) }
1522    }
1523
1524    /// Splits the slice into a slice of `N`-element arrays,
1525    /// starting at the beginning of the slice,
1526    /// and a remainder slice with length strictly less than `N`.
1527    ///
1528    /// The remainder is meaningful in the division sense.  Given
1529    /// `let (chunks, remainder) = slice.as_chunks_mut()`, then:
1530    /// - `chunks.len()` equals `slice.len() / N`,
1531    /// - `remainder.len()` equals `slice.len() % N`, and
1532    /// - `slice.len()` equals `chunks.len() * N + remainder.len()`.
1533    ///
1534    /// You can flatten the chunks back into a slice-of-`T` with [`as_flattened_mut`].
1535    ///
1536    /// [`as_flattened_mut`]: slice::as_flattened_mut
1537    ///
1538    /// # Panics
1539    ///
1540    /// Panics if `N` is zero.
1541    ///
1542    /// Note that this check is against a const generic parameter, not a runtime
1543    /// value, and thus a particular monomorphization will either always panic
1544    /// or it will never panic.
1545    ///
1546    /// # Examples
1547    ///
1548    /// ```
1549    /// let v = &mut [0, 0, 0, 0, 0];
1550    /// let mut count = 1;
1551    ///
1552    /// let (chunks, remainder) = v.as_chunks_mut();
1553    /// remainder[0] = 9;
1554    /// for chunk in chunks {
1555    ///     *chunk = [count; 2];
1556    ///     count += 1;
1557    /// }
1558    /// assert_eq!(v, &[1, 1, 2, 2, 9]);
1559    /// ```
1560    #[stable(feature = "slice_as_chunks", since = "1.88.0")]
1561    #[rustc_const_stable(feature = "slice_as_chunks", since = "1.88.0")]
1562    #[inline]
1563    #[track_caller]
1564    #[must_use]
1565    pub const fn as_chunks_mut<const N: usize>(&mut self) -> (&mut [[T; N]], &mut [T]) {
1566        assert!(N != 0, "chunk size must be non-zero");
1567        let len_rounded_down = self.len() / N * N;
1568        // SAFETY: The rounded-down value is always the same or smaller than the
1569        // original length, and thus must be in-bounds of the slice.
1570        let (multiple_of_n, remainder) = unsafe { self.split_at_mut_unchecked(len_rounded_down) };
1571        // SAFETY: We already panicked for zero, and ensured by construction
1572        // that the length of the subslice is a multiple of N.
1573        let array_slice = unsafe { multiple_of_n.as_chunks_unchecked_mut() };
1574        (array_slice, remainder)
1575    }
1576
1577    /// Splits the slice into a slice of `N`-element arrays,
1578    /// starting at the end of the slice,
1579    /// and a remainder slice with length strictly less than `N`.
1580    ///
1581    /// The remainder is meaningful in the division sense.  Given
1582    /// `let (remainder, chunks) = slice.as_rchunks_mut()`, then:
1583    /// - `remainder.len()` equals `slice.len() % N`,
1584    /// - `chunks.len()` equals `slice.len() / N`, and
1585    /// - `slice.len()` equals `chunks.len() * N + remainder.len()`.
1586    ///
1587    /// You can flatten the chunks back into a slice-of-`T` with [`as_flattened_mut`].
1588    ///
1589    /// [`as_flattened_mut`]: slice::as_flattened_mut
1590    ///
1591    /// # Panics
1592    ///
1593    /// Panics if `N` is zero.
1594    ///
1595    /// Note that this check is against a const generic parameter, not a runtime
1596    /// value, and thus a particular monomorphization will either always panic
1597    /// or it will never panic.
1598    ///
1599    /// # Examples
1600    ///
1601    /// ```
1602    /// let v = &mut [0, 0, 0, 0, 0];
1603    /// let mut count = 1;
1604    ///
1605    /// let (remainder, chunks) = v.as_rchunks_mut();
1606    /// remainder[0] = 9;
1607    /// for chunk in chunks {
1608    ///     *chunk = [count; 2];
1609    ///     count += 1;
1610    /// }
1611    /// assert_eq!(v, &[9, 1, 1, 2, 2]);
1612    /// ```
1613    #[stable(feature = "slice_as_chunks", since = "1.88.0")]
1614    #[rustc_const_stable(feature = "slice_as_chunks", since = "1.88.0")]
1615    #[inline]
1616    #[track_caller]
1617    #[must_use]
1618    pub const fn as_rchunks_mut<const N: usize>(&mut self) -> (&mut [T], &mut [[T; N]]) {
1619        assert!(N != 0, "chunk size must be non-zero");
1620        let len = self.len() / N;
1621        let (remainder, multiple_of_n) = self.split_at_mut(self.len() - len * N);
1622        // SAFETY: We already panicked for zero, and ensured by construction
1623        // that the length of the subslice is a multiple of N.
1624        let array_slice = unsafe { multiple_of_n.as_chunks_unchecked_mut() };
1625        (remainder, array_slice)
1626    }
1627
1628    /// Returns an iterator over `N` elements of the slice at a time, starting at the
1629    /// beginning of the slice.
1630    ///
1631    /// The chunks are mutable array references and do not overlap. If `N` does not divide
1632    /// the length of the slice, then the last up to `N-1` elements will be omitted and
1633    /// can be retrieved from the `into_remainder` function of the iterator.
1634    ///
1635    /// This method is the const generic equivalent of [`chunks_exact_mut`].
1636    ///
1637    /// # Panics
1638    ///
1639    /// Panics if `N` is zero. This check will most probably get changed to a compile time
1640    /// error before this method gets stabilized.
1641    ///
1642    /// # Examples
1643    ///
1644    /// ```
1645    /// #![feature(array_chunks)]
1646    /// let v = &mut [0, 0, 0, 0, 0];
1647    /// let mut count = 1;
1648    ///
1649    /// for chunk in v.array_chunks_mut() {
1650    ///     *chunk = [count; 2];
1651    ///     count += 1;
1652    /// }
1653    /// assert_eq!(v, &[1, 1, 2, 2, 0]);
1654    /// ```
1655    ///
1656    /// [`chunks_exact_mut`]: slice::chunks_exact_mut
1657    #[unstable(feature = "array_chunks", issue = "74985")]
1658    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1659    #[inline]
1660    #[track_caller]
1661    pub const fn array_chunks_mut<const N: usize>(&mut self) -> ArrayChunksMut<'_, T, N> {
1662        assert!(N != 0, "chunk size must be non-zero");
1663        ArrayChunksMut::new(self)
1664    }
1665
1666    /// Returns an iterator over overlapping windows of `N` elements of a slice,
1667    /// starting at the beginning of the slice.
1668    ///
1669    /// This is the const generic equivalent of [`windows`].
1670    ///
1671    /// If `N` is greater than the size of the slice, it will return no windows.
1672    ///
1673    /// # Panics
1674    ///
1675    /// Panics if `N` is zero. This check will most probably get changed to a compile time
1676    /// error before this method gets stabilized.
1677    ///
1678    /// # Examples
1679    ///
1680    /// ```
1681    /// #![feature(array_windows)]
1682    /// let slice = [0, 1, 2, 3];
1683    /// let mut iter = slice.array_windows();
1684    /// assert_eq!(iter.next().unwrap(), &[0, 1]);
1685    /// assert_eq!(iter.next().unwrap(), &[1, 2]);
1686    /// assert_eq!(iter.next().unwrap(), &[2, 3]);
1687    /// assert!(iter.next().is_none());
1688    /// ```
1689    ///
1690    /// [`windows`]: slice::windows
1691    #[unstable(feature = "array_windows", issue = "75027")]
1692    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1693    #[inline]
1694    #[track_caller]
1695    pub const fn array_windows<const N: usize>(&self) -> ArrayWindows<'_, T, N> {
1696        assert!(N != 0, "window size must be non-zero");
1697        ArrayWindows::new(self)
1698    }
1699
1700    /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
1701    /// of the slice.
1702    ///
1703    /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
1704    /// slice, then the last chunk will not have length `chunk_size`.
1705    ///
1706    /// See [`rchunks_exact`] for a variant of this iterator that returns chunks of always exactly
1707    /// `chunk_size` elements, and [`chunks`] for the same iterator but starting at the beginning
1708    /// of the slice.
1709    ///
1710    /// # Panics
1711    ///
1712    /// Panics if `chunk_size` is zero.
1713    ///
1714    /// # Examples
1715    ///
1716    /// ```
1717    /// let slice = ['l', 'o', 'r', 'e', 'm'];
1718    /// let mut iter = slice.rchunks(2);
1719    /// assert_eq!(iter.next().unwrap(), &['e', 'm']);
1720    /// assert_eq!(iter.next().unwrap(), &['o', 'r']);
1721    /// assert_eq!(iter.next().unwrap(), &['l']);
1722    /// assert!(iter.next().is_none());
1723    /// ```
1724    ///
1725    /// [`rchunks_exact`]: slice::rchunks_exact
1726    /// [`chunks`]: slice::chunks
1727    #[stable(feature = "rchunks", since = "1.31.0")]
1728    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1729    #[inline]
1730    #[track_caller]
1731    pub const fn rchunks(&self, chunk_size: usize) -> RChunks<'_, T> {
1732        assert!(chunk_size != 0, "chunk size must be non-zero");
1733        RChunks::new(self, chunk_size)
1734    }
1735
1736    /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
1737    /// of the slice.
1738    ///
1739    /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
1740    /// length of the slice, then the last chunk will not have length `chunk_size`.
1741    ///
1742    /// See [`rchunks_exact_mut`] for a variant of this iterator that returns chunks of always
1743    /// exactly `chunk_size` elements, and [`chunks_mut`] for the same iterator but starting at the
1744    /// beginning of the slice.
1745    ///
1746    /// # Panics
1747    ///
1748    /// Panics if `chunk_size` is zero.
1749    ///
1750    /// # Examples
1751    ///
1752    /// ```
1753    /// let v = &mut [0, 0, 0, 0, 0];
1754    /// let mut count = 1;
1755    ///
1756    /// for chunk in v.rchunks_mut(2) {
1757    ///     for elem in chunk.iter_mut() {
1758    ///         *elem += count;
1759    ///     }
1760    ///     count += 1;
1761    /// }
1762    /// assert_eq!(v, &[3, 2, 2, 1, 1]);
1763    /// ```
1764    ///
1765    /// [`rchunks_exact_mut`]: slice::rchunks_exact_mut
1766    /// [`chunks_mut`]: slice::chunks_mut
1767    #[stable(feature = "rchunks", since = "1.31.0")]
1768    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1769    #[inline]
1770    #[track_caller]
1771    pub const fn rchunks_mut(&mut self, chunk_size: usize) -> RChunksMut<'_, T> {
1772        assert!(chunk_size != 0, "chunk size must be non-zero");
1773        RChunksMut::new(self, chunk_size)
1774    }
1775
1776    /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
1777    /// end of the slice.
1778    ///
1779    /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
1780    /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved
1781    /// from the `remainder` function of the iterator.
1782    ///
1783    /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
1784    /// resulting code better than in the case of [`rchunks`].
1785    ///
1786    /// See [`rchunks`] for a variant of this iterator that also returns the remainder as a smaller
1787    /// chunk, and [`chunks_exact`] for the same iterator but starting at the beginning of the
1788    /// slice.
1789    ///
1790    /// # Panics
1791    ///
1792    /// Panics if `chunk_size` is zero.
1793    ///
1794    /// # Examples
1795    ///
1796    /// ```
1797    /// let slice = ['l', 'o', 'r', 'e', 'm'];
1798    /// let mut iter = slice.rchunks_exact(2);
1799    /// assert_eq!(iter.next().unwrap(), &['e', 'm']);
1800    /// assert_eq!(iter.next().unwrap(), &['o', 'r']);
1801    /// assert!(iter.next().is_none());
1802    /// assert_eq!(iter.remainder(), &['l']);
1803    /// ```
1804    ///
1805    /// [`chunks`]: slice::chunks
1806    /// [`rchunks`]: slice::rchunks
1807    /// [`chunks_exact`]: slice::chunks_exact
1808    #[stable(feature = "rchunks", since = "1.31.0")]
1809    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1810    #[inline]
1811    #[track_caller]
1812    pub const fn rchunks_exact(&self, chunk_size: usize) -> RChunksExact<'_, T> {
1813        assert!(chunk_size != 0, "chunk size must be non-zero");
1814        RChunksExact::new(self, chunk_size)
1815    }
1816
1817    /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
1818    /// of the slice.
1819    ///
1820    /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
1821    /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be
1822    /// retrieved from the `into_remainder` function of the iterator.
1823    ///
1824    /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
1825    /// resulting code better than in the case of [`chunks_mut`].
1826    ///
1827    /// See [`rchunks_mut`] for a variant of this iterator that also returns the remainder as a
1828    /// smaller chunk, and [`chunks_exact_mut`] for the same iterator but starting at the beginning
1829    /// of the slice.
1830    ///
1831    /// # Panics
1832    ///
1833    /// Panics if `chunk_size` is zero.
1834    ///
1835    /// # Examples
1836    ///
1837    /// ```
1838    /// let v = &mut [0, 0, 0, 0, 0];
1839    /// let mut count = 1;
1840    ///
1841    /// for chunk in v.rchunks_exact_mut(2) {
1842    ///     for elem in chunk.iter_mut() {
1843    ///         *elem += count;
1844    ///     }
1845    ///     count += 1;
1846    /// }
1847    /// assert_eq!(v, &[0, 2, 2, 1, 1]);
1848    /// ```
1849    ///
1850    /// [`chunks_mut`]: slice::chunks_mut
1851    /// [`rchunks_mut`]: slice::rchunks_mut
1852    /// [`chunks_exact_mut`]: slice::chunks_exact_mut
1853    #[stable(feature = "rchunks", since = "1.31.0")]
1854    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1855    #[inline]
1856    #[track_caller]
1857    pub const fn rchunks_exact_mut(&mut self, chunk_size: usize) -> RChunksExactMut<'_, T> {
1858        assert!(chunk_size != 0, "chunk size must be non-zero");
1859        RChunksExactMut::new(self, chunk_size)
1860    }
1861
1862    /// Returns an iterator over the slice producing non-overlapping runs
1863    /// of elements using the predicate to separate them.
1864    ///
1865    /// The predicate is called for every pair of consecutive elements,
1866    /// meaning that it is called on `slice[0]` and `slice[1]`,
1867    /// followed by `slice[1]` and `slice[2]`, and so on.
1868    ///
1869    /// # Examples
1870    ///
1871    /// ```
1872    /// let slice = &[1, 1, 1, 3, 3, 2, 2, 2];
1873    ///
1874    /// let mut iter = slice.chunk_by(|a, b| a == b);
1875    ///
1876    /// assert_eq!(iter.next(), Some(&[1, 1, 1][..]));
1877    /// assert_eq!(iter.next(), Some(&[3, 3][..]));
1878    /// assert_eq!(iter.next(), Some(&[2, 2, 2][..]));
1879    /// assert_eq!(iter.next(), None);
1880    /// ```
1881    ///
1882    /// This method can be used to extract the sorted subslices:
1883    ///
1884    /// ```
1885    /// let slice = &[1, 1, 2, 3, 2, 3, 2, 3, 4];
1886    ///
1887    /// let mut iter = slice.chunk_by(|a, b| a <= b);
1888    ///
1889    /// assert_eq!(iter.next(), Some(&[1, 1, 2, 3][..]));
1890    /// assert_eq!(iter.next(), Some(&[2, 3][..]));
1891    /// assert_eq!(iter.next(), Some(&[2, 3, 4][..]));
1892    /// assert_eq!(iter.next(), None);
1893    /// ```
1894    #[stable(feature = "slice_group_by", since = "1.77.0")]
1895    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1896    #[inline]
1897    pub const fn chunk_by<F>(&self, pred: F) -> ChunkBy<'_, T, F>
1898    where
1899        F: FnMut(&T, &T) -> bool,
1900    {
1901        ChunkBy::new(self, pred)
1902    }
1903
1904    /// Returns an iterator over the slice producing non-overlapping mutable
1905    /// runs of elements using the predicate to separate them.
1906    ///
1907    /// The predicate is called for every pair of consecutive elements,
1908    /// meaning that it is called on `slice[0]` and `slice[1]`,
1909    /// followed by `slice[1]` and `slice[2]`, and so on.
1910    ///
1911    /// # Examples
1912    ///
1913    /// ```
1914    /// let slice = &mut [1, 1, 1, 3, 3, 2, 2, 2];
1915    ///
1916    /// let mut iter = slice.chunk_by_mut(|a, b| a == b);
1917    ///
1918    /// assert_eq!(iter.next(), Some(&mut [1, 1, 1][..]));
1919    /// assert_eq!(iter.next(), Some(&mut [3, 3][..]));
1920    /// assert_eq!(iter.next(), Some(&mut [2, 2, 2][..]));
1921    /// assert_eq!(iter.next(), None);
1922    /// ```
1923    ///
1924    /// This method can be used to extract the sorted subslices:
1925    ///
1926    /// ```
1927    /// let slice = &mut [1, 1, 2, 3, 2, 3, 2, 3, 4];
1928    ///
1929    /// let mut iter = slice.chunk_by_mut(|a, b| a <= b);
1930    ///
1931    /// assert_eq!(iter.next(), Some(&mut [1, 1, 2, 3][..]));
1932    /// assert_eq!(iter.next(), Some(&mut [2, 3][..]));
1933    /// assert_eq!(iter.next(), Some(&mut [2, 3, 4][..]));
1934    /// assert_eq!(iter.next(), None);
1935    /// ```
1936    #[stable(feature = "slice_group_by", since = "1.77.0")]
1937    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
1938    #[inline]
1939    pub const fn chunk_by_mut<F>(&mut self, pred: F) -> ChunkByMut<'_, T, F>
1940    where
1941        F: FnMut(&T, &T) -> bool,
1942    {
1943        ChunkByMut::new(self, pred)
1944    }
1945
1946    /// Divides one slice into two at an index.
1947    ///
1948    /// The first will contain all indices from `[0, mid)` (excluding
1949    /// the index `mid` itself) and the second will contain all
1950    /// indices from `[mid, len)` (excluding the index `len` itself).
1951    ///
1952    /// # Panics
1953    ///
1954    /// Panics if `mid > len`.  For a non-panicking alternative see
1955    /// [`split_at_checked`](slice::split_at_checked).
1956    ///
1957    /// # Examples
1958    ///
1959    /// ```
1960    /// let v = ['a', 'b', 'c'];
1961    ///
1962    /// {
1963    ///    let (left, right) = v.split_at(0);
1964    ///    assert_eq!(left, []);
1965    ///    assert_eq!(right, ['a', 'b', 'c']);
1966    /// }
1967    ///
1968    /// {
1969    ///     let (left, right) = v.split_at(2);
1970    ///     assert_eq!(left, ['a', 'b']);
1971    ///     assert_eq!(right, ['c']);
1972    /// }
1973    ///
1974    /// {
1975    ///     let (left, right) = v.split_at(3);
1976    ///     assert_eq!(left, ['a', 'b', 'c']);
1977    ///     assert_eq!(right, []);
1978    /// }
1979    /// ```
1980    #[stable(feature = "rust1", since = "1.0.0")]
1981    #[rustc_const_stable(feature = "const_slice_split_at_not_mut", since = "1.71.0")]
1982    #[inline]
1983    #[track_caller]
1984    #[must_use]
1985    pub const fn split_at(&self, mid: usize) -> (&[T], &[T]) {
1986        match self.split_at_checked(mid) {
1987            Some(pair) => pair,
1988            None => panic!("mid > len"),
1989        }
1990    }
1991
1992    /// Divides one mutable slice into two at an index.
1993    ///
1994    /// The first will contain all indices from `[0, mid)` (excluding
1995    /// the index `mid` itself) and the second will contain all
1996    /// indices from `[mid, len)` (excluding the index `len` itself).
1997    ///
1998    /// # Panics
1999    ///
2000    /// Panics if `mid > len`.  For a non-panicking alternative see
2001    /// [`split_at_mut_checked`](slice::split_at_mut_checked).
2002    ///
2003    /// # Examples
2004    ///
2005    /// ```
2006    /// let mut v = [1, 0, 3, 0, 5, 6];
2007    /// let (left, right) = v.split_at_mut(2);
2008    /// assert_eq!(left, [1, 0]);
2009    /// assert_eq!(right, [3, 0, 5, 6]);
2010    /// left[1] = 2;
2011    /// right[1] = 4;
2012    /// assert_eq!(v, [1, 2, 3, 4, 5, 6]);
2013    /// ```
2014    #[stable(feature = "rust1", since = "1.0.0")]
2015    #[inline]
2016    #[track_caller]
2017    #[must_use]
2018    #[rustc_const_stable(feature = "const_slice_split_at_mut", since = "1.83.0")]
2019    pub const fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
2020        match self.split_at_mut_checked(mid) {
2021            Some(pair) => pair,
2022            None => panic!("mid > len"),
2023        }
2024    }
2025
2026    /// Divides one slice into two at an index, without doing bounds checking.
2027    ///
2028    /// The first will contain all indices from `[0, mid)` (excluding
2029    /// the index `mid` itself) and the second will contain all
2030    /// indices from `[mid, len)` (excluding the index `len` itself).
2031    ///
2032    /// For a safe alternative see [`split_at`].
2033    ///
2034    /// # Safety
2035    ///
2036    /// Calling this method with an out-of-bounds index is *[undefined behavior]*
2037    /// even if the resulting reference is not used. The caller has to ensure that
2038    /// `0 <= mid <= self.len()`.
2039    ///
2040    /// [`split_at`]: slice::split_at
2041    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2042    ///
2043    /// # Examples
2044    ///
2045    /// ```
2046    /// let v = ['a', 'b', 'c'];
2047    ///
2048    /// unsafe {
2049    ///    let (left, right) = v.split_at_unchecked(0);
2050    ///    assert_eq!(left, []);
2051    ///    assert_eq!(right, ['a', 'b', 'c']);
2052    /// }
2053    ///
2054    /// unsafe {
2055    ///     let (left, right) = v.split_at_unchecked(2);
2056    ///     assert_eq!(left, ['a', 'b']);
2057    ///     assert_eq!(right, ['c']);
2058    /// }
2059    ///
2060    /// unsafe {
2061    ///     let (left, right) = v.split_at_unchecked(3);
2062    ///     assert_eq!(left, ['a', 'b', 'c']);
2063    ///     assert_eq!(right, []);
2064    /// }
2065    /// ```
2066    #[stable(feature = "slice_split_at_unchecked", since = "1.79.0")]
2067    #[rustc_const_stable(feature = "const_slice_split_at_unchecked", since = "1.77.0")]
2068    #[inline]
2069    #[must_use]
2070    #[track_caller]
2071    pub const unsafe fn split_at_unchecked(&self, mid: usize) -> (&[T], &[T]) {
2072        // FIXME(const-hack): the const function `from_raw_parts` is used to make this
2073        // function const; previously the implementation used
2074        // `(self.get_unchecked(..mid), self.get_unchecked(mid..))`
2075
2076        let len = self.len();
2077        let ptr = self.as_ptr();
2078
2079        assert_unsafe_precondition!(
2080            check_library_ub,
2081            "slice::split_at_unchecked requires the index to be within the slice",
2082            (mid: usize = mid, len: usize = len) => mid <= len,
2083        );
2084
2085        // SAFETY: Caller has to check that `0 <= mid <= self.len()`
2086        unsafe { (from_raw_parts(ptr, mid), from_raw_parts(ptr.add(mid), unchecked_sub(len, mid))) }
2087    }
2088
2089    /// Divides one mutable slice into two at an index, without doing bounds checking.
2090    ///
2091    /// The first will contain all indices from `[0, mid)` (excluding
2092    /// the index `mid` itself) and the second will contain all
2093    /// indices from `[mid, len)` (excluding the index `len` itself).
2094    ///
2095    /// For a safe alternative see [`split_at_mut`].
2096    ///
2097    /// # Safety
2098    ///
2099    /// Calling this method with an out-of-bounds index is *[undefined behavior]*
2100    /// even if the resulting reference is not used. The caller has to ensure that
2101    /// `0 <= mid <= self.len()`.
2102    ///
2103    /// [`split_at_mut`]: slice::split_at_mut
2104    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
2105    ///
2106    /// # Examples
2107    ///
2108    /// ```
2109    /// let mut v = [1, 0, 3, 0, 5, 6];
2110    /// // scoped to restrict the lifetime of the borrows
2111    /// unsafe {
2112    ///     let (left, right) = v.split_at_mut_unchecked(2);
2113    ///     assert_eq!(left, [1, 0]);
2114    ///     assert_eq!(right, [3, 0, 5, 6]);
2115    ///     left[1] = 2;
2116    ///     right[1] = 4;
2117    /// }
2118    /// assert_eq!(v, [1, 2, 3, 4, 5, 6]);
2119    /// ```
2120    #[stable(feature = "slice_split_at_unchecked", since = "1.79.0")]
2121    #[rustc_const_stable(feature = "const_slice_split_at_mut", since = "1.83.0")]
2122    #[inline]
2123    #[must_use]
2124    #[track_caller]
2125    pub const unsafe fn split_at_mut_unchecked(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
2126        let len = self.len();
2127        let ptr = self.as_mut_ptr();
2128
2129        assert_unsafe_precondition!(
2130            check_library_ub,
2131            "slice::split_at_mut_unchecked requires the index to be within the slice",
2132            (mid: usize = mid, len: usize = len) => mid <= len,
2133        );
2134
2135        // SAFETY: Caller has to check that `0 <= mid <= self.len()`.
2136        //
2137        // `[ptr; mid]` and `[mid; len]` are not overlapping, so returning a mutable reference
2138        // is fine.
2139        unsafe {
2140            (
2141                from_raw_parts_mut(ptr, mid),
2142                from_raw_parts_mut(ptr.add(mid), unchecked_sub(len, mid)),
2143            )
2144        }
2145    }
2146
2147    /// Divides one slice into two at an index, returning `None` if the slice is
2148    /// too short.
2149    ///
2150    /// If `mid ≤ len` returns a pair of slices where the first will contain all
2151    /// indices from `[0, mid)` (excluding the index `mid` itself) and the
2152    /// second will contain all indices from `[mid, len)` (excluding the index
2153    /// `len` itself).
2154    ///
2155    /// Otherwise, if `mid > len`, returns `None`.
2156    ///
2157    /// # Examples
2158    ///
2159    /// ```
2160    /// let v = [1, -2, 3, -4, 5, -6];
2161    ///
2162    /// {
2163    ///    let (left, right) = v.split_at_checked(0).unwrap();
2164    ///    assert_eq!(left, []);
2165    ///    assert_eq!(right, [1, -2, 3, -4, 5, -6]);
2166    /// }
2167    ///
2168    /// {
2169    ///     let (left, right) = v.split_at_checked(2).unwrap();
2170    ///     assert_eq!(left, [1, -2]);
2171    ///     assert_eq!(right, [3, -4, 5, -6]);
2172    /// }
2173    ///
2174    /// {
2175    ///     let (left, right) = v.split_at_checked(6).unwrap();
2176    ///     assert_eq!(left, [1, -2, 3, -4, 5, -6]);
2177    ///     assert_eq!(right, []);
2178    /// }
2179    ///
2180    /// assert_eq!(None, v.split_at_checked(7));
2181    /// ```
2182    #[stable(feature = "split_at_checked", since = "1.80.0")]
2183    #[rustc_const_stable(feature = "split_at_checked", since = "1.80.0")]
2184    #[inline]
2185    #[must_use]
2186    pub const fn split_at_checked(&self, mid: usize) -> Option<(&[T], &[T])> {
2187        if mid <= self.len() {
2188            // SAFETY: `[ptr; mid]` and `[mid; len]` are inside `self`, which
2189            // fulfills the requirements of `split_at_unchecked`.
2190            Some(unsafe { self.split_at_unchecked(mid) })
2191        } else {
2192            None
2193        }
2194    }
2195
2196    /// Divides one mutable slice into two at an index, returning `None` if the
2197    /// slice is too short.
2198    ///
2199    /// If `mid ≤ len` returns a pair of slices where the first will contain all
2200    /// indices from `[0, mid)` (excluding the index `mid` itself) and the
2201    /// second will contain all indices from `[mid, len)` (excluding the index
2202    /// `len` itself).
2203    ///
2204    /// Otherwise, if `mid > len`, returns `None`.
2205    ///
2206    /// # Examples
2207    ///
2208    /// ```
2209    /// let mut v = [1, 0, 3, 0, 5, 6];
2210    ///
2211    /// if let Some((left, right)) = v.split_at_mut_checked(2) {
2212    ///     assert_eq!(left, [1, 0]);
2213    ///     assert_eq!(right, [3, 0, 5, 6]);
2214    ///     left[1] = 2;
2215    ///     right[1] = 4;
2216    /// }
2217    /// assert_eq!(v, [1, 2, 3, 4, 5, 6]);
2218    ///
2219    /// assert_eq!(None, v.split_at_mut_checked(7));
2220    /// ```
2221    #[stable(feature = "split_at_checked", since = "1.80.0")]
2222    #[rustc_const_stable(feature = "const_slice_split_at_mut", since = "1.83.0")]
2223    #[inline]
2224    #[must_use]
2225    pub const fn split_at_mut_checked(&mut self, mid: usize) -> Option<(&mut [T], &mut [T])> {
2226        if mid <= self.len() {
2227            // SAFETY: `[ptr; mid]` and `[mid; len]` are inside `self`, which
2228            // fulfills the requirements of `split_at_unchecked`.
2229            Some(unsafe { self.split_at_mut_unchecked(mid) })
2230        } else {
2231            None
2232        }
2233    }
2234
2235    /// Returns an iterator over subslices separated by elements that match
2236    /// `pred`. The matched element is not contained in the subslices.
2237    ///
2238    /// # Examples
2239    ///
2240    /// ```
2241    /// let slice = [10, 40, 33, 20];
2242    /// let mut iter = slice.split(|num| num % 3 == 0);
2243    ///
2244    /// assert_eq!(iter.next().unwrap(), &[10, 40]);
2245    /// assert_eq!(iter.next().unwrap(), &[20]);
2246    /// assert!(iter.next().is_none());
2247    /// ```
2248    ///
2249    /// If the first element is matched, an empty slice will be the first item
2250    /// returned by the iterator. Similarly, if the last element in the slice
2251    /// is matched, an empty slice will be the last item returned by the
2252    /// iterator:
2253    ///
2254    /// ```
2255    /// let slice = [10, 40, 33];
2256    /// let mut iter = slice.split(|num| num % 3 == 0);
2257    ///
2258    /// assert_eq!(iter.next().unwrap(), &[10, 40]);
2259    /// assert_eq!(iter.next().unwrap(), &[]);
2260    /// assert!(iter.next().is_none());
2261    /// ```
2262    ///
2263    /// If two matched elements are directly adjacent, an empty slice will be
2264    /// present between them:
2265    ///
2266    /// ```
2267    /// let slice = [10, 6, 33, 20];
2268    /// let mut iter = slice.split(|num| num % 3 == 0);
2269    ///
2270    /// assert_eq!(iter.next().unwrap(), &[10]);
2271    /// assert_eq!(iter.next().unwrap(), &[]);
2272    /// assert_eq!(iter.next().unwrap(), &[20]);
2273    /// assert!(iter.next().is_none());
2274    /// ```
2275    #[stable(feature = "rust1", since = "1.0.0")]
2276    #[inline]
2277    pub fn split<F>(&self, pred: F) -> Split<'_, T, F>
2278    where
2279        F: FnMut(&T) -> bool,
2280    {
2281        Split::new(self, pred)
2282    }
2283
2284    /// Returns an iterator over mutable subslices separated by elements that
2285    /// match `pred`. The matched element is not contained in the subslices.
2286    ///
2287    /// # Examples
2288    ///
2289    /// ```
2290    /// let mut v = [10, 40, 30, 20, 60, 50];
2291    ///
2292    /// for group in v.split_mut(|num| *num % 3 == 0) {
2293    ///     group[0] = 1;
2294    /// }
2295    /// assert_eq!(v, [1, 40, 30, 1, 60, 1]);
2296    /// ```
2297    #[stable(feature = "rust1", since = "1.0.0")]
2298    #[inline]
2299    pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<'_, T, F>
2300    where
2301        F: FnMut(&T) -> bool,
2302    {
2303        SplitMut::new(self, pred)
2304    }
2305
2306    /// Returns an iterator over subslices separated by elements that match
2307    /// `pred`. The matched element is contained in the end of the previous
2308    /// subslice as a terminator.
2309    ///
2310    /// # Examples
2311    ///
2312    /// ```
2313    /// let slice = [10, 40, 33, 20];
2314    /// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
2315    ///
2316    /// assert_eq!(iter.next().unwrap(), &[10, 40, 33]);
2317    /// assert_eq!(iter.next().unwrap(), &[20]);
2318    /// assert!(iter.next().is_none());
2319    /// ```
2320    ///
2321    /// If the last element of the slice is matched,
2322    /// that element will be considered the terminator of the preceding slice.
2323    /// That slice will be the last item returned by the iterator.
2324    ///
2325    /// ```
2326    /// let slice = [3, 10, 40, 33];
2327    /// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
2328    ///
2329    /// assert_eq!(iter.next().unwrap(), &[3]);
2330    /// assert_eq!(iter.next().unwrap(), &[10, 40, 33]);
2331    /// assert!(iter.next().is_none());
2332    /// ```
2333    #[stable(feature = "split_inclusive", since = "1.51.0")]
2334    #[inline]
2335    pub fn split_inclusive<F>(&self, pred: F) -> SplitInclusive<'_, T, F>
2336    where
2337        F: FnMut(&T) -> bool,
2338    {
2339        SplitInclusive::new(self, pred)
2340    }
2341
2342    /// Returns an iterator over mutable subslices separated by elements that
2343    /// match `pred`. The matched element is contained in the previous
2344    /// subslice as a terminator.
2345    ///
2346    /// # Examples
2347    ///
2348    /// ```
2349    /// let mut v = [10, 40, 30, 20, 60, 50];
2350    ///
2351    /// for group in v.split_inclusive_mut(|num| *num % 3 == 0) {
2352    ///     let terminator_idx = group.len()-1;
2353    ///     group[terminator_idx] = 1;
2354    /// }
2355    /// assert_eq!(v, [10, 40, 1, 20, 1, 1]);
2356    /// ```
2357    #[stable(feature = "split_inclusive", since = "1.51.0")]
2358    #[inline]
2359    pub fn split_inclusive_mut<F>(&mut self, pred: F) -> SplitInclusiveMut<'_, T, F>
2360    where
2361        F: FnMut(&T) -> bool,
2362    {
2363        SplitInclusiveMut::new(self, pred)
2364    }
2365
2366    /// Returns an iterator over subslices separated by elements that match
2367    /// `pred`, starting at the end of the slice and working backwards.
2368    /// The matched element is not contained in the subslices.
2369    ///
2370    /// # Examples
2371    ///
2372    /// ```
2373    /// let slice = [11, 22, 33, 0, 44, 55];
2374    /// let mut iter = slice.rsplit(|num| *num == 0);
2375    ///
2376    /// assert_eq!(iter.next().unwrap(), &[44, 55]);
2377    /// assert_eq!(iter.next().unwrap(), &[11, 22, 33]);
2378    /// assert_eq!(iter.next(), None);
2379    /// ```
2380    ///
2381    /// As with `split()`, if the first or last element is matched, an empty
2382    /// slice will be the first (or last) item returned by the iterator.
2383    ///
2384    /// ```
2385    /// let v = &[0, 1, 1, 2, 3, 5, 8];
2386    /// let mut it = v.rsplit(|n| *n % 2 == 0);
2387    /// assert_eq!(it.next().unwrap(), &[]);
2388    /// assert_eq!(it.next().unwrap(), &[3, 5]);
2389    /// assert_eq!(it.next().unwrap(), &[1, 1]);
2390    /// assert_eq!(it.next().unwrap(), &[]);
2391    /// assert_eq!(it.next(), None);
2392    /// ```
2393    #[stable(feature = "slice_rsplit", since = "1.27.0")]
2394    #[inline]
2395    pub fn rsplit<F>(&self, pred: F) -> RSplit<'_, T, F>
2396    where
2397        F: FnMut(&T) -> bool,
2398    {
2399        RSplit::new(self, pred)
2400    }
2401
2402    /// Returns an iterator over mutable subslices separated by elements that
2403    /// match `pred`, starting at the end of the slice and working
2404    /// backwards. The matched element is not contained in the subslices.
2405    ///
2406    /// # Examples
2407    ///
2408    /// ```
2409    /// let mut v = [100, 400, 300, 200, 600, 500];
2410    ///
2411    /// let mut count = 0;
2412    /// for group in v.rsplit_mut(|num| *num % 3 == 0) {
2413    ///     count += 1;
2414    ///     group[0] = count;
2415    /// }
2416    /// assert_eq!(v, [3, 400, 300, 2, 600, 1]);
2417    /// ```
2418    ///
2419    #[stable(feature = "slice_rsplit", since = "1.27.0")]
2420    #[inline]
2421    pub fn rsplit_mut<F>(&mut self, pred: F) -> RSplitMut<'_, T, F>
2422    where
2423        F: FnMut(&T) -> bool,
2424    {
2425        RSplitMut::new(self, pred)
2426    }
2427
2428    /// Returns an iterator over subslices separated by elements that match
2429    /// `pred`, limited to returning at most `n` items. The matched element is
2430    /// not contained in the subslices.
2431    ///
2432    /// The last element returned, if any, will contain the remainder of the
2433    /// slice.
2434    ///
2435    /// # Examples
2436    ///
2437    /// Print the slice split once by numbers divisible by 3 (i.e., `[10, 40]`,
2438    /// `[20, 60, 50]`):
2439    ///
2440    /// ```
2441    /// let v = [10, 40, 30, 20, 60, 50];
2442    ///
2443    /// for group in v.splitn(2, |num| *num % 3 == 0) {
2444    ///     println!("{group:?}");
2445    /// }
2446    /// ```
2447    #[stable(feature = "rust1", since = "1.0.0")]
2448    #[inline]
2449    pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<'_, T, F>
2450    where
2451        F: FnMut(&T) -> bool,
2452    {
2453        SplitN::new(self.split(pred), n)
2454    }
2455
2456    /// Returns an iterator over mutable subslices separated by elements that match
2457    /// `pred`, limited to returning at most `n` items. The matched element is
2458    /// not contained in the subslices.
2459    ///
2460    /// The last element returned, if any, will contain the remainder of the
2461    /// slice.
2462    ///
2463    /// # Examples
2464    ///
2465    /// ```
2466    /// let mut v = [10, 40, 30, 20, 60, 50];
2467    ///
2468    /// for group in v.splitn_mut(2, |num| *num % 3 == 0) {
2469    ///     group[0] = 1;
2470    /// }
2471    /// assert_eq!(v, [1, 40, 30, 1, 60, 50]);
2472    /// ```
2473    #[stable(feature = "rust1", since = "1.0.0")]
2474    #[inline]
2475    pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<'_, T, F>
2476    where
2477        F: FnMut(&T) -> bool,
2478    {
2479        SplitNMut::new(self.split_mut(pred), n)
2480    }
2481
2482    /// Returns an iterator over subslices separated by elements that match
2483    /// `pred` limited to returning at most `n` items. This starts at the end of
2484    /// the slice and works backwards. The matched element is not contained in
2485    /// the subslices.
2486    ///
2487    /// The last element returned, if any, will contain the remainder of the
2488    /// slice.
2489    ///
2490    /// # Examples
2491    ///
2492    /// Print the slice split once, starting from the end, by numbers divisible
2493    /// by 3 (i.e., `[50]`, `[10, 40, 30, 20]`):
2494    ///
2495    /// ```
2496    /// let v = [10, 40, 30, 20, 60, 50];
2497    ///
2498    /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
2499    ///     println!("{group:?}");
2500    /// }
2501    /// ```
2502    #[stable(feature = "rust1", since = "1.0.0")]
2503    #[inline]
2504    pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<'_, T, F>
2505    where
2506        F: FnMut(&T) -> bool,
2507    {
2508        RSplitN::new(self.rsplit(pred), n)
2509    }
2510
2511    /// Returns an iterator over subslices separated by elements that match
2512    /// `pred` limited to returning at most `n` items. This starts at the end of
2513    /// the slice and works backwards. The matched element is not contained in
2514    /// the subslices.
2515    ///
2516    /// The last element returned, if any, will contain the remainder of the
2517    /// slice.
2518    ///
2519    /// # Examples
2520    ///
2521    /// ```
2522    /// let mut s = [10, 40, 30, 20, 60, 50];
2523    ///
2524    /// for group in s.rsplitn_mut(2, |num| *num % 3 == 0) {
2525    ///     group[0] = 1;
2526    /// }
2527    /// assert_eq!(s, [1, 40, 30, 20, 60, 1]);
2528    /// ```
2529    #[stable(feature = "rust1", since = "1.0.0")]
2530    #[inline]
2531    pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<'_, T, F>
2532    where
2533        F: FnMut(&T) -> bool,
2534    {
2535        RSplitNMut::new(self.rsplit_mut(pred), n)
2536    }
2537
2538    /// Splits the slice on the first element that matches the specified
2539    /// predicate.
2540    ///
2541    /// If any matching elements are present in the slice, returns the prefix
2542    /// before the match and suffix after. The matching element itself is not
2543    /// included. If no elements match, returns `None`.
2544    ///
2545    /// # Examples
2546    ///
2547    /// ```
2548    /// #![feature(slice_split_once)]
2549    /// let s = [1, 2, 3, 2, 4];
2550    /// assert_eq!(s.split_once(|&x| x == 2), Some((
2551    ///     &[1][..],
2552    ///     &[3, 2, 4][..]
2553    /// )));
2554    /// assert_eq!(s.split_once(|&x| x == 0), None);
2555    /// ```
2556    #[unstable(feature = "slice_split_once", reason = "newly added", issue = "112811")]
2557    #[inline]
2558    pub fn split_once<F>(&self, pred: F) -> Option<(&[T], &[T])>
2559    where
2560        F: FnMut(&T) -> bool,
2561    {
2562        let index = self.iter().position(pred)?;
2563        Some((&self[..index], &self[index + 1..]))
2564    }
2565
2566    /// Splits the slice on the last element that matches the specified
2567    /// predicate.
2568    ///
2569    /// If any matching elements are present in the slice, returns the prefix
2570    /// before the match and suffix after. The matching element itself is not
2571    /// included. If no elements match, returns `None`.
2572    ///
2573    /// # Examples
2574    ///
2575    /// ```
2576    /// #![feature(slice_split_once)]
2577    /// let s = [1, 2, 3, 2, 4];
2578    /// assert_eq!(s.rsplit_once(|&x| x == 2), Some((
2579    ///     &[1, 2, 3][..],
2580    ///     &[4][..]
2581    /// )));
2582    /// assert_eq!(s.rsplit_once(|&x| x == 0), None);
2583    /// ```
2584    #[unstable(feature = "slice_split_once", reason = "newly added", issue = "112811")]
2585    #[inline]
2586    pub fn rsplit_once<F>(&self, pred: F) -> Option<(&[T], &[T])>
2587    where
2588        F: FnMut(&T) -> bool,
2589    {
2590        let index = self.iter().rposition(pred)?;
2591        Some((&self[..index], &self[index + 1..]))
2592    }
2593
2594    /// Returns `true` if the slice contains an element with the given value.
2595    ///
2596    /// This operation is *O*(*n*).
2597    ///
2598    /// Note that if you have a sorted slice, [`binary_search`] may be faster.
2599    ///
2600    /// [`binary_search`]: slice::binary_search
2601    ///
2602    /// # Examples
2603    ///
2604    /// ```
2605    /// let v = [10, 40, 30];
2606    /// assert!(v.contains(&30));
2607    /// assert!(!v.contains(&50));
2608    /// ```
2609    ///
2610    /// If you do not have a `&T`, but some other value that you can compare
2611    /// with one (for example, `String` implements `PartialEq<str>`), you can
2612    /// use `iter().any`:
2613    ///
2614    /// ```
2615    /// let v = [String::from("hello"), String::from("world")]; // slice of `String`
2616    /// assert!(v.iter().any(|e| e == "hello")); // search with `&str`
2617    /// assert!(!v.iter().any(|e| e == "hi"));
2618    /// ```
2619    #[stable(feature = "rust1", since = "1.0.0")]
2620    #[inline]
2621    #[must_use]
2622    pub fn contains(&self, x: &T) -> bool
2623    where
2624        T: PartialEq,
2625    {
2626        cmp::SliceContains::slice_contains(x, self)
2627    }
2628
2629    /// Returns `true` if `needle` is a prefix of the slice or equal to the slice.
2630    ///
2631    /// # Examples
2632    ///
2633    /// ```
2634    /// let v = [10, 40, 30];
2635    /// assert!(v.starts_with(&[10]));
2636    /// assert!(v.starts_with(&[10, 40]));
2637    /// assert!(v.starts_with(&v));
2638    /// assert!(!v.starts_with(&[50]));
2639    /// assert!(!v.starts_with(&[10, 50]));
2640    /// ```
2641    ///
2642    /// Always returns `true` if `needle` is an empty slice:
2643    ///
2644    /// ```
2645    /// let v = &[10, 40, 30];
2646    /// assert!(v.starts_with(&[]));
2647    /// let v: &[u8] = &[];
2648    /// assert!(v.starts_with(&[]));
2649    /// ```
2650    #[stable(feature = "rust1", since = "1.0.0")]
2651    #[must_use]
2652    pub fn starts_with(&self, needle: &[T]) -> bool
2653    where
2654        T: PartialEq,
2655    {
2656        let n = needle.len();
2657        self.len() >= n && needle == &self[..n]
2658    }
2659
2660    /// Returns `true` if `needle` is a suffix of the slice or equal to the slice.
2661    ///
2662    /// # Examples
2663    ///
2664    /// ```
2665    /// let v = [10, 40, 30];
2666    /// assert!(v.ends_with(&[30]));
2667    /// assert!(v.ends_with(&[40, 30]));
2668    /// assert!(v.ends_with(&v));
2669    /// assert!(!v.ends_with(&[50]));
2670    /// assert!(!v.ends_with(&[50, 30]));
2671    /// ```
2672    ///
2673    /// Always returns `true` if `needle` is an empty slice:
2674    ///
2675    /// ```
2676    /// let v = &[10, 40, 30];
2677    /// assert!(v.ends_with(&[]));
2678    /// let v: &[u8] = &[];
2679    /// assert!(v.ends_with(&[]));
2680    /// ```
2681    #[stable(feature = "rust1", since = "1.0.0")]
2682    #[must_use]
2683    pub fn ends_with(&self, needle: &[T]) -> bool
2684    where
2685        T: PartialEq,
2686    {
2687        let (m, n) = (self.len(), needle.len());
2688        m >= n && needle == &self[m - n..]
2689    }
2690
2691    /// Returns a subslice with the prefix removed.
2692    ///
2693    /// If the slice starts with `prefix`, returns the subslice after the prefix, wrapped in `Some`.
2694    /// If `prefix` is empty, simply returns the original slice. If `prefix` is equal to the
2695    /// original slice, returns an empty slice.
2696    ///
2697    /// If the slice does not start with `prefix`, returns `None`.
2698    ///
2699    /// # Examples
2700    ///
2701    /// ```
2702    /// let v = &[10, 40, 30];
2703    /// assert_eq!(v.strip_prefix(&[10]), Some(&[40, 30][..]));
2704    /// assert_eq!(v.strip_prefix(&[10, 40]), Some(&[30][..]));
2705    /// assert_eq!(v.strip_prefix(&[10, 40, 30]), Some(&[][..]));
2706    /// assert_eq!(v.strip_prefix(&[50]), None);
2707    /// assert_eq!(v.strip_prefix(&[10, 50]), None);
2708    ///
2709    /// let prefix : &str = "he";
2710    /// assert_eq!(b"hello".strip_prefix(prefix.as_bytes()),
2711    ///            Some(b"llo".as_ref()));
2712    /// ```
2713    #[must_use = "returns the subslice without modifying the original"]
2714    #[stable(feature = "slice_strip", since = "1.51.0")]
2715    pub fn strip_prefix<P: SlicePattern<Item = T> + ?Sized>(&self, prefix: &P) -> Option<&[T]>
2716    where
2717        T: PartialEq,
2718    {
2719        // This function will need rewriting if and when SlicePattern becomes more sophisticated.
2720        let prefix = prefix.as_slice();
2721        let n = prefix.len();
2722        if n <= self.len() {
2723            let (head, tail) = self.split_at(n);
2724            if head == prefix {
2725                return Some(tail);
2726            }
2727        }
2728        None
2729    }
2730
2731    /// Returns a subslice with the suffix removed.
2732    ///
2733    /// If the slice ends with `suffix`, returns the subslice before the suffix, wrapped in `Some`.
2734    /// If `suffix` is empty, simply returns the original slice. If `suffix` is equal to the
2735    /// original slice, returns an empty slice.
2736    ///
2737    /// If the slice does not end with `suffix`, returns `None`.
2738    ///
2739    /// # Examples
2740    ///
2741    /// ```
2742    /// let v = &[10, 40, 30];
2743    /// assert_eq!(v.strip_suffix(&[30]), Some(&[10, 40][..]));
2744    /// assert_eq!(v.strip_suffix(&[40, 30]), Some(&[10][..]));
2745    /// assert_eq!(v.strip_suffix(&[10, 40, 30]), Some(&[][..]));
2746    /// assert_eq!(v.strip_suffix(&[50]), None);
2747    /// assert_eq!(v.strip_suffix(&[50, 30]), None);
2748    /// ```
2749    #[must_use = "returns the subslice without modifying the original"]
2750    #[stable(feature = "slice_strip", since = "1.51.0")]
2751    pub fn strip_suffix<P: SlicePattern<Item = T> + ?Sized>(&self, suffix: &P) -> Option<&[T]>
2752    where
2753        T: PartialEq,
2754    {
2755        // This function will need rewriting if and when SlicePattern becomes more sophisticated.
2756        let suffix = suffix.as_slice();
2757        let (len, n) = (self.len(), suffix.len());
2758        if n <= len {
2759            let (head, tail) = self.split_at(len - n);
2760            if tail == suffix {
2761                return Some(head);
2762            }
2763        }
2764        None
2765    }
2766
2767    /// Returns a subslice with the optional prefix removed.
2768    ///
2769    /// If the slice starts with `prefix`, returns the subslice after the prefix.  If `prefix`
2770    /// is empty or the slice does not start with `prefix`, simply returns the original slice.
2771    /// If `prefix` is equal to the original slice, returns an empty slice.
2772    ///
2773    /// # Examples
2774    ///
2775    /// ```
2776    /// #![feature(trim_prefix_suffix)]
2777    ///
2778    /// let v = &[10, 40, 30];
2779    ///
2780    /// // Prefix present - removes it
2781    /// assert_eq!(v.trim_prefix(&[10]), &[40, 30][..]);
2782    /// assert_eq!(v.trim_prefix(&[10, 40]), &[30][..]);
2783    /// assert_eq!(v.trim_prefix(&[10, 40, 30]), &[][..]);
2784    ///
2785    /// // Prefix absent - returns original slice
2786    /// assert_eq!(v.trim_prefix(&[50]), &[10, 40, 30][..]);
2787    /// assert_eq!(v.trim_prefix(&[10, 50]), &[10, 40, 30][..]);
2788    ///
2789    /// let prefix : &str = "he";
2790    /// assert_eq!(b"hello".trim_prefix(prefix.as_bytes()), b"llo".as_ref());
2791    /// ```
2792    #[must_use = "returns the subslice without modifying the original"]
2793    #[unstable(feature = "trim_prefix_suffix", issue = "142312")]
2794    pub fn trim_prefix<P: SlicePattern<Item = T> + ?Sized>(&self, prefix: &P) -> &[T]
2795    where
2796        T: PartialEq,
2797    {
2798        // This function will need rewriting if and when SlicePattern becomes more sophisticated.
2799        let prefix = prefix.as_slice();
2800        let n = prefix.len();
2801        if n <= self.len() {
2802            let (head, tail) = self.split_at(n);
2803            if head == prefix {
2804                return tail;
2805            }
2806        }
2807        self
2808    }
2809
2810    /// Returns a subslice with the optional suffix removed.
2811    ///
2812    /// If the slice ends with `suffix`, returns the subslice before the suffix.  If `suffix`
2813    /// is empty or the slice does not end with `suffix`, simply returns the original slice.
2814    /// If `suffix` is equal to the original slice, returns an empty slice.
2815    ///
2816    /// # Examples
2817    ///
2818    /// ```
2819    /// #![feature(trim_prefix_suffix)]
2820    ///
2821    /// let v = &[10, 40, 30];
2822    ///
2823    /// // Suffix present - removes it
2824    /// assert_eq!(v.trim_suffix(&[30]), &[10, 40][..]);
2825    /// assert_eq!(v.trim_suffix(&[40, 30]), &[10][..]);
2826    /// assert_eq!(v.trim_suffix(&[10, 40, 30]), &[][..]);
2827    ///
2828    /// // Suffix absent - returns original slice
2829    /// assert_eq!(v.trim_suffix(&[50]), &[10, 40, 30][..]);
2830    /// assert_eq!(v.trim_suffix(&[50, 30]), &[10, 40, 30][..]);
2831    /// ```
2832    #[must_use = "returns the subslice without modifying the original"]
2833    #[unstable(feature = "trim_prefix_suffix", issue = "142312")]
2834    pub fn trim_suffix<P: SlicePattern<Item = T> + ?Sized>(&self, suffix: &P) -> &[T]
2835    where
2836        T: PartialEq,
2837    {
2838        // This function will need rewriting if and when SlicePattern becomes more sophisticated.
2839        let suffix = suffix.as_slice();
2840        let (len, n) = (self.len(), suffix.len());
2841        if n <= len {
2842            let (head, tail) = self.split_at(len - n);
2843            if tail == suffix {
2844                return head;
2845            }
2846        }
2847        self
2848    }
2849
2850    /// Binary searches this slice for a given element.
2851    /// If the slice is not sorted, the returned result is unspecified and
2852    /// meaningless.
2853    ///
2854    /// If the value is found then [`Result::Ok`] is returned, containing the
2855    /// index of the matching element. If there are multiple matches, then any
2856    /// one of the matches could be returned. The index is chosen
2857    /// deterministically, but is subject to change in future versions of Rust.
2858    /// If the value is not found then [`Result::Err`] is returned, containing
2859    /// the index where a matching element could be inserted while maintaining
2860    /// sorted order.
2861    ///
2862    /// See also [`binary_search_by`], [`binary_search_by_key`], and [`partition_point`].
2863    ///
2864    /// [`binary_search_by`]: slice::binary_search_by
2865    /// [`binary_search_by_key`]: slice::binary_search_by_key
2866    /// [`partition_point`]: slice::partition_point
2867    ///
2868    /// # Examples
2869    ///
2870    /// Looks up a series of four elements. The first is found, with a
2871    /// uniquely determined position; the second and third are not
2872    /// found; the fourth could match any position in `[1, 4]`.
2873    ///
2874    /// ```
2875    /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
2876    ///
2877    /// assert_eq!(s.binary_search(&13),  Ok(9));
2878    /// assert_eq!(s.binary_search(&4),   Err(7));
2879    /// assert_eq!(s.binary_search(&100), Err(13));
2880    /// let r = s.binary_search(&1);
2881    /// assert!(match r { Ok(1..=4) => true, _ => false, });
2882    /// ```
2883    ///
2884    /// If you want to find that whole *range* of matching items, rather than
2885    /// an arbitrary matching one, that can be done using [`partition_point`]:
2886    /// ```
2887    /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
2888    ///
2889    /// let low = s.partition_point(|x| x < &1);
2890    /// assert_eq!(low, 1);
2891    /// let high = s.partition_point(|x| x <= &1);
2892    /// assert_eq!(high, 5);
2893    /// let r = s.binary_search(&1);
2894    /// assert!((low..high).contains(&r.unwrap()));
2895    ///
2896    /// assert!(s[..low].iter().all(|&x| x < 1));
2897    /// assert!(s[low..high].iter().all(|&x| x == 1));
2898    /// assert!(s[high..].iter().all(|&x| x > 1));
2899    ///
2900    /// // For something not found, the "range" of equal items is empty
2901    /// assert_eq!(s.partition_point(|x| x < &11), 9);
2902    /// assert_eq!(s.partition_point(|x| x <= &11), 9);
2903    /// assert_eq!(s.binary_search(&11), Err(9));
2904    /// ```
2905    ///
2906    /// If you want to insert an item to a sorted vector, while maintaining
2907    /// sort order, consider using [`partition_point`]:
2908    ///
2909    /// ```
2910    /// let mut s = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
2911    /// let num = 42;
2912    /// let idx = s.partition_point(|&x| x <= num);
2913    /// // If `num` is unique, `s.partition_point(|&x| x < num)` (with `<`) is equivalent to
2914    /// // `s.binary_search(&num).unwrap_or_else(|x| x)`, but using `<=` will allow `insert`
2915    /// // to shift less elements.
2916    /// s.insert(idx, num);
2917    /// assert_eq!(s, [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
2918    /// ```
2919    #[stable(feature = "rust1", since = "1.0.0")]
2920    pub fn binary_search(&self, x: &T) -> Result<usize, usize>
2921    where
2922        T: Ord,
2923    {
2924        self.binary_search_by(|p| p.cmp(x))
2925    }
2926
2927    /// Binary searches this slice with a comparator function.
2928    ///
2929    /// The comparator function should return an order code that indicates
2930    /// whether its argument is `Less`, `Equal` or `Greater` the desired
2931    /// target.
2932    /// If the slice is not sorted or if the comparator function does not
2933    /// implement an order consistent with the sort order of the underlying
2934    /// slice, the returned result is unspecified and meaningless.
2935    ///
2936    /// If the value is found then [`Result::Ok`] is returned, containing the
2937    /// index of the matching element. If there are multiple matches, then any
2938    /// one of the matches could be returned. The index is chosen
2939    /// deterministically, but is subject to change in future versions of Rust.
2940    /// If the value is not found then [`Result::Err`] is returned, containing
2941    /// the index where a matching element could be inserted while maintaining
2942    /// sorted order.
2943    ///
2944    /// See also [`binary_search`], [`binary_search_by_key`], and [`partition_point`].
2945    ///
2946    /// [`binary_search`]: slice::binary_search
2947    /// [`binary_search_by_key`]: slice::binary_search_by_key
2948    /// [`partition_point`]: slice::partition_point
2949    ///
2950    /// # Examples
2951    ///
2952    /// Looks up a series of four elements. The first is found, with a
2953    /// uniquely determined position; the second and third are not
2954    /// found; the fourth could match any position in `[1, 4]`.
2955    ///
2956    /// ```
2957    /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
2958    ///
2959    /// let seek = 13;
2960    /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
2961    /// let seek = 4;
2962    /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
2963    /// let seek = 100;
2964    /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
2965    /// let seek = 1;
2966    /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
2967    /// assert!(match r { Ok(1..=4) => true, _ => false, });
2968    /// ```
2969    #[stable(feature = "rust1", since = "1.0.0")]
2970    #[inline]
2971    pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
2972    where
2973        F: FnMut(&'a T) -> Ordering,
2974    {
2975        let mut size = self.len();
2976        if size == 0 {
2977            return Err(0);
2978        }
2979        let mut base = 0usize;
2980
2981        // This loop intentionally doesn't have an early exit if the comparison
2982        // returns Equal. We want the number of loop iterations to depend *only*
2983        // on the size of the input slice so that the CPU can reliably predict
2984        // the loop count.
2985        while size > 1 {
2986            let half = size / 2;
2987            let mid = base + half;
2988
2989            // SAFETY: the call is made safe by the following invariants:
2990            // - `mid >= 0`: by definition
2991            // - `mid < size`: `mid = size / 2 + size / 4 + size / 8 ...`
2992            let cmp = f(unsafe { self.get_unchecked(mid) });
2993
2994            // Binary search interacts poorly with branch prediction, so force
2995            // the compiler to use conditional moves if supported by the target
2996            // architecture.
2997            base = hint::select_unpredictable(cmp == Greater, base, mid);
2998
2999            // This is imprecise in the case where `size` is odd and the
3000            // comparison returns Greater: the mid element still gets included
3001            // by `size` even though it's known to be larger than the element
3002            // being searched for.
3003            //
3004            // This is fine though: we gain more performance by keeping the
3005            // loop iteration count invariant (and thus predictable) than we
3006            // lose from considering one additional element.
3007            size -= half;
3008        }
3009
3010        // SAFETY: base is always in [0, size) because base <= mid.
3011        let cmp = f(unsafe { self.get_unchecked(base) });
3012        if cmp == Equal {
3013            // SAFETY: same as the `get_unchecked` above.
3014            unsafe { hint::assert_unchecked(base < self.len()) };
3015            Ok(base)
3016        } else {
3017            let result = base + (cmp == Less) as usize;
3018            // SAFETY: same as the `get_unchecked` above.
3019            // Note that this is `<=`, unlike the assume in the `Ok` path.
3020            unsafe { hint::assert_unchecked(result <= self.len()) };
3021            Err(result)
3022        }
3023    }
3024
3025    /// Binary searches this slice with a key extraction function.
3026    ///
3027    /// Assumes that the slice is sorted by the key, for instance with
3028    /// [`sort_by_key`] using the same key extraction function.
3029    /// If the slice is not sorted by the key, the returned result is
3030    /// unspecified and meaningless.
3031    ///
3032    /// If the value is found then [`Result::Ok`] is returned, containing the
3033    /// index of the matching element. If there are multiple matches, then any
3034    /// one of the matches could be returned. The index is chosen
3035    /// deterministically, but is subject to change in future versions of Rust.
3036    /// If the value is not found then [`Result::Err`] is returned, containing
3037    /// the index where a matching element could be inserted while maintaining
3038    /// sorted order.
3039    ///
3040    /// See also [`binary_search`], [`binary_search_by`], and [`partition_point`].
3041    ///
3042    /// [`sort_by_key`]: slice::sort_by_key
3043    /// [`binary_search`]: slice::binary_search
3044    /// [`binary_search_by`]: slice::binary_search_by
3045    /// [`partition_point`]: slice::partition_point
3046    ///
3047    /// # Examples
3048    ///
3049    /// Looks up a series of four elements in a slice of pairs sorted by
3050    /// their second elements. The first is found, with a uniquely
3051    /// determined position; the second and third are not found; the
3052    /// fourth could match any position in `[1, 4]`.
3053    ///
3054    /// ```
3055    /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1),
3056    ///          (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
3057    ///          (1, 21), (2, 34), (4, 55)];
3058    ///
3059    /// assert_eq!(s.binary_search_by_key(&13, |&(a, b)| b),  Ok(9));
3060    /// assert_eq!(s.binary_search_by_key(&4, |&(a, b)| b),   Err(7));
3061    /// assert_eq!(s.binary_search_by_key(&100, |&(a, b)| b), Err(13));
3062    /// let r = s.binary_search_by_key(&1, |&(a, b)| b);
3063    /// assert!(match r { Ok(1..=4) => true, _ => false, });
3064    /// ```
3065    // Lint rustdoc::broken_intra_doc_links is allowed as `slice::sort_by_key` is
3066    // in crate `alloc`, and as such doesn't exists yet when building `core`: #74481.
3067    // This breaks links when slice is displayed in core, but changing it to use relative links
3068    // would break when the item is re-exported. So allow the core links to be broken for now.
3069    #[allow(rustdoc::broken_intra_doc_links)]
3070    #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
3071    #[inline]
3072    pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
3073    where
3074        F: FnMut(&'a T) -> B,
3075        B: Ord,
3076    {
3077        self.binary_search_by(|k| f(k).cmp(b))
3078    }
3079
3080    /// Sorts the slice in ascending order **without** preserving the initial order of equal elements.
3081    ///
3082    /// This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does not
3083    /// allocate), and *O*(*n* \* log(*n*)) worst-case.
3084    ///
3085    /// If the implementation of [`Ord`] for `T` does not implement a [total order], the function
3086    /// may panic; even if the function exits normally, the resulting order of elements in the slice
3087    /// is unspecified. See also the note on panicking below.
3088    ///
3089    /// For example `|a, b| (a - b).cmp(a)` is a comparison function that is neither transitive nor
3090    /// reflexive nor total, `a < b < c < a` with `a = 1, b = 2, c = 3`. For more information and
3091    /// examples see the [`Ord`] documentation.
3092    ///
3093    ///
3094    /// All original elements will remain in the slice and any possible modifications via interior
3095    /// mutability are observed in the input. Same is true if the implementation of [`Ord`] for `T` panics.
3096    ///
3097    /// Sorting types that only implement [`PartialOrd`] such as [`f32`] and [`f64`] require
3098    /// additional precautions. For example, `f32::NAN != f32::NAN`, which doesn't fulfill the
3099    /// reflexivity requirement of [`Ord`]. By using an alternative comparison function with
3100    /// `slice::sort_unstable_by` such as [`f32::total_cmp`] or [`f64::total_cmp`] that defines a
3101    /// [total order] users can sort slices containing floating-point values. Alternatively, if all
3102    /// values in the slice are guaranteed to be in a subset for which [`PartialOrd::partial_cmp`]
3103    /// forms a [total order], it's possible to sort the slice with `sort_unstable_by(|a, b|
3104    /// a.partial_cmp(b).unwrap())`.
3105    ///
3106    /// # Current implementation
3107    ///
3108    /// The current implementation is based on [ipnsort] by Lukas Bergdoll and Orson Peters, which
3109    /// combines the fast average case of quicksort with the fast worst case of heapsort, achieving
3110    /// linear time on fully sorted and reversed inputs. On inputs with k distinct elements, the
3111    /// expected time to sort the data is *O*(*n* \* log(*k*)).
3112    ///
3113    /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
3114    /// slice is partially sorted.
3115    ///
3116    /// # Panics
3117    ///
3118    /// May panic if the implementation of [`Ord`] for `T` does not implement a [total order], or if
3119    /// the [`Ord`] implementation panics.
3120    ///
3121    /// # Examples
3122    ///
3123    /// ```
3124    /// let mut v = [4, -5, 1, -3, 2];
3125    ///
3126    /// v.sort_unstable();
3127    /// assert_eq!(v, [-5, -3, 1, 2, 4]);
3128    /// ```
3129    ///
3130    /// [ipnsort]: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort
3131    /// [total order]: https://en.wikipedia.org/wiki/Total_order
3132    #[stable(feature = "sort_unstable", since = "1.20.0")]
3133    #[inline]
3134    pub fn sort_unstable(&mut self)
3135    where
3136        T: Ord,
3137    {
3138        sort::unstable::sort(self, &mut T::lt);
3139    }
3140
3141    /// Sorts the slice in ascending order with a comparison function, **without** preserving the
3142    /// initial order of equal elements.
3143    ///
3144    /// This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does not
3145    /// allocate), and *O*(*n* \* log(*n*)) worst-case.
3146    ///
3147    /// If the comparison function `compare` does not implement a [total order], the function
3148    /// may panic; even if the function exits normally, the resulting order of elements in the slice
3149    /// is unspecified. See also the note on panicking below.
3150    ///
3151    /// For example `|a, b| (a - b).cmp(a)` is a comparison function that is neither transitive nor
3152    /// reflexive nor total, `a < b < c < a` with `a = 1, b = 2, c = 3`. For more information and
3153    /// examples see the [`Ord`] documentation.
3154    ///
3155    /// All original elements will remain in the slice and any possible modifications via interior
3156    /// mutability are observed in the input. Same is true if `compare` panics.
3157    ///
3158    /// # Current implementation
3159    ///
3160    /// The current implementation is based on [ipnsort] by Lukas Bergdoll and Orson Peters, which
3161    /// combines the fast average case of quicksort with the fast worst case of heapsort, achieving
3162    /// linear time on fully sorted and reversed inputs. On inputs with k distinct elements, the
3163    /// expected time to sort the data is *O*(*n* \* log(*k*)).
3164    ///
3165    /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
3166    /// slice is partially sorted.
3167    ///
3168    /// # Panics
3169    ///
3170    /// May panic if the `compare` does not implement a [total order], or if
3171    /// the `compare` itself panics.
3172    ///
3173    /// # Examples
3174    ///
3175    /// ```
3176    /// let mut v = [4, -5, 1, -3, 2];
3177    /// v.sort_unstable_by(|a, b| a.cmp(b));
3178    /// assert_eq!(v, [-5, -3, 1, 2, 4]);
3179    ///
3180    /// // reverse sorting
3181    /// v.sort_unstable_by(|a, b| b.cmp(a));
3182    /// assert_eq!(v, [4, 2, 1, -3, -5]);
3183    /// ```
3184    ///
3185    /// [ipnsort]: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort
3186    /// [total order]: https://en.wikipedia.org/wiki/Total_order
3187    #[stable(feature = "sort_unstable", since = "1.20.0")]
3188    #[inline]
3189    pub fn sort_unstable_by<F>(&mut self, mut compare: F)
3190    where
3191        F: FnMut(&T, &T) -> Ordering,
3192    {
3193        sort::unstable::sort(self, &mut |a, b| compare(a, b) == Ordering::Less);
3194    }
3195
3196    /// Sorts the slice in ascending order with a key extraction function, **without** preserving
3197    /// the initial order of equal elements.
3198    ///
3199    /// This sort is unstable (i.e., may reorder equal elements), in-place (i.e., does not
3200    /// allocate), and *O*(*n* \* log(*n*)) worst-case.
3201    ///
3202    /// If the implementation of [`Ord`] for `K` does not implement a [total order], the function
3203    /// may panic; even if the function exits normally, the resulting order of elements in the slice
3204    /// is unspecified. See also the note on panicking below.
3205    ///
3206    /// For example `|a, b| (a - b).cmp(a)` is a comparison function that is neither transitive nor
3207    /// reflexive nor total, `a < b < c < a` with `a = 1, b = 2, c = 3`. For more information and
3208    /// examples see the [`Ord`] documentation.
3209    ///
3210    /// All original elements will remain in the slice and any possible modifications via interior
3211    /// mutability are observed in the input. Same is true if the implementation of [`Ord`] for `K` panics.
3212    ///
3213    /// # Current implementation
3214    ///
3215    /// The current implementation is based on [ipnsort] by Lukas Bergdoll and Orson Peters, which
3216    /// combines the fast average case of quicksort with the fast worst case of heapsort, achieving
3217    /// linear time on fully sorted and reversed inputs. On inputs with k distinct elements, the
3218    /// expected time to sort the data is *O*(*n* \* log(*k*)).
3219    ///
3220    /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
3221    /// slice is partially sorted.
3222    ///
3223    /// # Panics
3224    ///
3225    /// May panic if the implementation of [`Ord`] for `K` does not implement a [total order], or if
3226    /// the [`Ord`] implementation panics.
3227    ///
3228    /// # Examples
3229    ///
3230    /// ```
3231    /// let mut v = [4i32, -5, 1, -3, 2];
3232    ///
3233    /// v.sort_unstable_by_key(|k| k.abs());
3234    /// assert_eq!(v, [1, 2, -3, 4, -5]);
3235    /// ```
3236    ///
3237    /// [ipnsort]: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort
3238    /// [total order]: https://en.wikipedia.org/wiki/Total_order
3239    #[stable(feature = "sort_unstable", since = "1.20.0")]
3240    #[inline]
3241    pub fn sort_unstable_by_key<K, F>(&mut self, mut f: F)
3242    where
3243        F: FnMut(&T) -> K,
3244        K: Ord,
3245    {
3246        sort::unstable::sort(self, &mut |a, b| f(a).lt(&f(b)));
3247    }
3248
3249    /// Reorders the slice such that the element at `index` is at a sort-order position. All
3250    /// elements before `index` will be `<=` to this value, and all elements after will be `>=` to
3251    /// it.
3252    ///
3253    /// This reordering is unstable (i.e. any element that compares equal to the nth element may end
3254    /// up at that position), in-place (i.e.  does not allocate), and runs in *O*(*n*) time. This
3255    /// function is also known as "kth element" in other libraries.
3256    ///
3257    /// Returns a triple that partitions the reordered slice:
3258    ///
3259    /// * The unsorted subslice before `index`, whose elements all satisfy `x <= self[index]`.
3260    ///
3261    /// * The element at `index`.
3262    ///
3263    /// * The unsorted subslice after `index`, whose elements all satisfy `x >= self[index]`.
3264    ///
3265    /// # Current implementation
3266    ///
3267    /// The current algorithm is an introselect implementation based on [ipnsort] by Lukas Bergdoll
3268    /// and Orson Peters, which is also the basis for [`sort_unstable`]. The fallback algorithm is
3269    /// Median of Medians using Tukey's Ninther for pivot selection, which guarantees linear runtime
3270    /// for all inputs.
3271    ///
3272    /// [`sort_unstable`]: slice::sort_unstable
3273    ///
3274    /// # Panics
3275    ///
3276    /// Panics when `index >= len()`, and so always panics on empty slices.
3277    ///
3278    /// May panic if the implementation of [`Ord`] for `T` does not implement a [total order].
3279    ///
3280    /// # Examples
3281    ///
3282    /// ```
3283    /// let mut v = [-5i32, 4, 2, -3, 1];
3284    ///
3285    /// // Find the items `<=` to the median, the median itself, and the items `>=` to it.
3286    /// let (lesser, median, greater) = v.select_nth_unstable(2);
3287    ///
3288    /// assert!(lesser == [-3, -5] || lesser == [-5, -3]);
3289    /// assert_eq!(median, &mut 1);
3290    /// assert!(greater == [4, 2] || greater == [2, 4]);
3291    ///
3292    /// // We are only guaranteed the slice will be one of the following, based on the way we sort
3293    /// // about the specified index.
3294    /// assert!(v == [-3, -5, 1, 2, 4] ||
3295    ///         v == [-5, -3, 1, 2, 4] ||
3296    ///         v == [-3, -5, 1, 4, 2] ||
3297    ///         v == [-5, -3, 1, 4, 2]);
3298    /// ```
3299    ///
3300    /// [ipnsort]: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort
3301    /// [total order]: https://en.wikipedia.org/wiki/Total_order
3302    #[stable(feature = "slice_select_nth_unstable", since = "1.49.0")]
3303    #[inline]
3304    pub fn select_nth_unstable(&mut self, index: usize) -> (&mut [T], &mut T, &mut [T])
3305    where
3306        T: Ord,
3307    {
3308        sort::select::partition_at_index(self, index, T::lt)
3309    }
3310
3311    /// Reorders the slice with a comparator function such that the element at `index` is at a
3312    /// sort-order position. All elements before `index` will be `<=` to this value, and all
3313    /// elements after will be `>=` to it, according to the comparator function.
3314    ///
3315    /// This reordering is unstable (i.e. any element that compares equal to the nth element may end
3316    /// up at that position), in-place (i.e.  does not allocate), and runs in *O*(*n*) time. This
3317    /// function is also known as "kth element" in other libraries.
3318    ///
3319    /// Returns a triple partitioning the reordered slice:
3320    ///
3321    /// * The unsorted subslice before `index`, whose elements all satisfy
3322    ///   `compare(x, self[index]).is_le()`.
3323    ///
3324    /// * The element at `index`.
3325    ///
3326    /// * The unsorted subslice after `index`, whose elements all satisfy
3327    ///   `compare(x, self[index]).is_ge()`.
3328    ///
3329    /// # Current implementation
3330    ///
3331    /// The current algorithm is an introselect implementation based on [ipnsort] by Lukas Bergdoll
3332    /// and Orson Peters, which is also the basis for [`sort_unstable`]. The fallback algorithm is
3333    /// Median of Medians using Tukey's Ninther for pivot selection, which guarantees linear runtime
3334    /// for all inputs.
3335    ///
3336    /// [`sort_unstable`]: slice::sort_unstable
3337    ///
3338    /// # Panics
3339    ///
3340    /// Panics when `index >= len()`, and so always panics on empty slices.
3341    ///
3342    /// May panic if `compare` does not implement a [total order].
3343    ///
3344    /// # Examples
3345    ///
3346    /// ```
3347    /// let mut v = [-5i32, 4, 2, -3, 1];
3348    ///
3349    /// // Find the items `>=` to the median, the median itself, and the items `<=` to it, by using
3350    /// // a reversed comparator.
3351    /// let (before, median, after) = v.select_nth_unstable_by(2, |a, b| b.cmp(a));
3352    ///
3353    /// assert!(before == [4, 2] || before == [2, 4]);
3354    /// assert_eq!(median, &mut 1);
3355    /// assert!(after == [-3, -5] || after == [-5, -3]);
3356    ///
3357    /// // We are only guaranteed the slice will be one of the following, based on the way we sort
3358    /// // about the specified index.
3359    /// assert!(v == [2, 4, 1, -5, -3] ||
3360    ///         v == [2, 4, 1, -3, -5] ||
3361    ///         v == [4, 2, 1, -5, -3] ||
3362    ///         v == [4, 2, 1, -3, -5]);
3363    /// ```
3364    ///
3365    /// [ipnsort]: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort
3366    /// [total order]: https://en.wikipedia.org/wiki/Total_order
3367    #[stable(feature = "slice_select_nth_unstable", since = "1.49.0")]
3368    #[inline]
3369    pub fn select_nth_unstable_by<F>(
3370        &mut self,
3371        index: usize,
3372        mut compare: F,
3373    ) -> (&mut [T], &mut T, &mut [T])
3374    where
3375        F: FnMut(&T, &T) -> Ordering,
3376    {
3377        sort::select::partition_at_index(self, index, |a: &T, b: &T| compare(a, b) == Less)
3378    }
3379
3380    /// Reorders the slice with a key extraction function such that the element at `index` is at a
3381    /// sort-order position. All elements before `index` will have keys `<=` to the key at `index`,
3382    /// and all elements after will have keys `>=` to it.
3383    ///
3384    /// This reordering is unstable (i.e. any element that compares equal to the nth element may end
3385    /// up at that position), in-place (i.e.  does not allocate), and runs in *O*(*n*) time. This
3386    /// function is also known as "kth element" in other libraries.
3387    ///
3388    /// Returns a triple partitioning the reordered slice:
3389    ///
3390    /// * The unsorted subslice before `index`, whose elements all satisfy `f(x) <= f(self[index])`.
3391    ///
3392    /// * The element at `index`.
3393    ///
3394    /// * The unsorted subslice after `index`, whose elements all satisfy `f(x) >= f(self[index])`.
3395    ///
3396    /// # Current implementation
3397    ///
3398    /// The current algorithm is an introselect implementation based on [ipnsort] by Lukas Bergdoll
3399    /// and Orson Peters, which is also the basis for [`sort_unstable`]. The fallback algorithm is
3400    /// Median of Medians using Tukey's Ninther for pivot selection, which guarantees linear runtime
3401    /// for all inputs.
3402    ///
3403    /// [`sort_unstable`]: slice::sort_unstable
3404    ///
3405    /// # Panics
3406    ///
3407    /// Panics when `index >= len()`, meaning it always panics on empty slices.
3408    ///
3409    /// May panic if `K: Ord` does not implement a total order.
3410    ///
3411    /// # Examples
3412    ///
3413    /// ```
3414    /// let mut v = [-5i32, 4, 1, -3, 2];
3415    ///
3416    /// // Find the items `<=` to the absolute median, the absolute median itself, and the items
3417    /// // `>=` to it.
3418    /// let (lesser, median, greater) = v.select_nth_unstable_by_key(2, |a| a.abs());
3419    ///
3420    /// assert!(lesser == [1, 2] || lesser == [2, 1]);
3421    /// assert_eq!(median, &mut -3);
3422    /// assert!(greater == [4, -5] || greater == [-5, 4]);
3423    ///
3424    /// // We are only guaranteed the slice will be one of the following, based on the way we sort
3425    /// // about the specified index.
3426    /// assert!(v == [1, 2, -3, 4, -5] ||
3427    ///         v == [1, 2, -3, -5, 4] ||
3428    ///         v == [2, 1, -3, 4, -5] ||
3429    ///         v == [2, 1, -3, -5, 4]);
3430    /// ```
3431    ///
3432    /// [ipnsort]: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort
3433    /// [total order]: https://en.wikipedia.org/wiki/Total_order
3434    #[stable(feature = "slice_select_nth_unstable", since = "1.49.0")]
3435    #[inline]
3436    pub fn select_nth_unstable_by_key<K, F>(
3437        &mut self,
3438        index: usize,
3439        mut f: F,
3440    ) -> (&mut [T], &mut T, &mut [T])
3441    where
3442        F: FnMut(&T) -> K,
3443        K: Ord,
3444    {
3445        sort::select::partition_at_index(self, index, |a: &T, b: &T| f(a).lt(&f(b)))
3446    }
3447
3448    /// Moves all consecutive repeated elements to the end of the slice according to the
3449    /// [`PartialEq`] trait implementation.
3450    ///
3451    /// Returns two slices. The first contains no consecutive repeated elements.
3452    /// The second contains all the duplicates in no specified order.
3453    ///
3454    /// If the slice is sorted, the first returned slice contains no duplicates.
3455    ///
3456    /// # Examples
3457    ///
3458    /// ```
3459    /// #![feature(slice_partition_dedup)]
3460    ///
3461    /// let mut slice = [1, 2, 2, 3, 3, 2, 1, 1];
3462    ///
3463    /// let (dedup, duplicates) = slice.partition_dedup();
3464    ///
3465    /// assert_eq!(dedup, [1, 2, 3, 2, 1]);
3466    /// assert_eq!(duplicates, [2, 3, 1]);
3467    /// ```
3468    #[unstable(feature = "slice_partition_dedup", issue = "54279")]
3469    #[inline]
3470    pub fn partition_dedup(&mut self) -> (&mut [T], &mut [T])
3471    where
3472        T: PartialEq,
3473    {
3474        self.partition_dedup_by(|a, b| a == b)
3475    }
3476
3477    /// Moves all but the first of consecutive elements to the end of the slice satisfying
3478    /// a given equality relation.
3479    ///
3480    /// Returns two slices. The first contains no consecutive repeated elements.
3481    /// The second contains all the duplicates in no specified order.
3482    ///
3483    /// The `same_bucket` function is passed references to two elements from the slice and
3484    /// must determine if the elements compare equal. The elements are passed in opposite order
3485    /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is moved
3486    /// at the end of the slice.
3487    ///
3488    /// If the slice is sorted, the first returned slice contains no duplicates.
3489    ///
3490    /// # Examples
3491    ///
3492    /// ```
3493    /// #![feature(slice_partition_dedup)]
3494    ///
3495    /// let mut slice = ["foo", "Foo", "BAZ", "Bar", "bar", "baz", "BAZ"];
3496    ///
3497    /// let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.eq_ignore_ascii_case(b));
3498    ///
3499    /// assert_eq!(dedup, ["foo", "BAZ", "Bar", "baz"]);
3500    /// assert_eq!(duplicates, ["bar", "Foo", "BAZ"]);
3501    /// ```
3502    #[unstable(feature = "slice_partition_dedup", issue = "54279")]
3503    #[inline]
3504    pub fn partition_dedup_by<F>(&mut self, mut same_bucket: F) -> (&mut [T], &mut [T])
3505    where
3506        F: FnMut(&mut T, &mut T) -> bool,
3507    {
3508        // Although we have a mutable reference to `self`, we cannot make
3509        // *arbitrary* changes. The `same_bucket` calls could panic, so we
3510        // must ensure that the slice is in a valid state at all times.
3511        //
3512        // The way that we handle this is by using swaps; we iterate
3513        // over all the elements, swapping as we go so that at the end
3514        // the elements we wish to keep are in the front, and those we
3515        // wish to reject are at the back. We can then split the slice.
3516        // This operation is still `O(n)`.
3517        //
3518        // Example: We start in this state, where `r` represents "next
3519        // read" and `w` represents "next_write".
3520        //
3521        //           r
3522        //     +---+---+---+---+---+---+
3523        //     | 0 | 1 | 1 | 2 | 3 | 3 |
3524        //     +---+---+---+---+---+---+
3525        //           w
3526        //
3527        // Comparing self[r] against self[w-1], this is not a duplicate, so
3528        // we swap self[r] and self[w] (no effect as r==w) and then increment both
3529        // r and w, leaving us with:
3530        //
3531        //               r
3532        //     +---+---+---+---+---+---+
3533        //     | 0 | 1 | 1 | 2 | 3 | 3 |
3534        //     +---+---+---+---+---+---+
3535        //               w
3536        //
3537        // Comparing self[r] against self[w-1], this value is a duplicate,
3538        // so we increment `r` but leave everything else unchanged:
3539        //
3540        //                   r
3541        //     +---+---+---+---+---+---+
3542        //     | 0 | 1 | 1 | 2 | 3 | 3 |
3543        //     +---+---+---+---+---+---+
3544        //               w
3545        //
3546        // Comparing self[r] against self[w-1], this is not a duplicate,
3547        // so swap self[r] and self[w] and advance r and w:
3548        //
3549        //                       r
3550        //     +---+---+---+---+---+---+
3551        //     | 0 | 1 | 2 | 1 | 3 | 3 |
3552        //     +---+---+---+---+---+---+
3553        //                   w
3554        //
3555        // Not a duplicate, repeat:
3556        //
3557        //                           r
3558        //     +---+---+---+---+---+---+
3559        //     | 0 | 1 | 2 | 3 | 1 | 3 |
3560        //     +---+---+---+---+---+---+
3561        //                       w
3562        //
3563        // Duplicate, advance r. End of slice. Split at w.
3564
3565        let len = self.len();
3566        if len <= 1 {
3567            return (self, &mut []);
3568        }
3569
3570        let ptr = self.as_mut_ptr();
3571        let mut next_read: usize = 1;
3572        let mut next_write: usize = 1;
3573
3574        // SAFETY: the `while` condition guarantees `next_read` and `next_write`
3575        // are less than `len`, thus are inside `self`. `prev_ptr_write` points to
3576        // one element before `ptr_write`, but `next_write` starts at 1, so
3577        // `prev_ptr_write` is never less than 0 and is inside the slice.
3578        // This fulfils the requirements for dereferencing `ptr_read`, `prev_ptr_write`
3579        // and `ptr_write`, and for using `ptr.add(next_read)`, `ptr.add(next_write - 1)`
3580        // and `prev_ptr_write.offset(1)`.
3581        //
3582        // `next_write` is also incremented at most once per loop at most meaning
3583        // no element is skipped when it may need to be swapped.
3584        //
3585        // `ptr_read` and `prev_ptr_write` never point to the same element. This
3586        // is required for `&mut *ptr_read`, `&mut *prev_ptr_write` to be safe.
3587        // The explanation is simply that `next_read >= next_write` is always true,
3588        // thus `next_read > next_write - 1` is too.
3589        unsafe {
3590            // Avoid bounds checks by using raw pointers.
3591            while next_read < len {
3592                let ptr_read = ptr.add(next_read);
3593                let prev_ptr_write = ptr.add(next_write - 1);
3594                if !same_bucket(&mut *ptr_read, &mut *prev_ptr_write) {
3595                    if next_read != next_write {
3596                        let ptr_write = prev_ptr_write.add(1);
3597                        mem::swap(&mut *ptr_read, &mut *ptr_write);
3598                    }
3599                    next_write += 1;
3600                }
3601                next_read += 1;
3602            }
3603        }
3604
3605        self.split_at_mut(next_write)
3606    }
3607
3608    /// Moves all but the first of consecutive elements to the end of the slice that resolve
3609    /// to the same key.
3610    ///
3611    /// Returns two slices. The first contains no consecutive repeated elements.
3612    /// The second contains all the duplicates in no specified order.
3613    ///
3614    /// If the slice is sorted, the first returned slice contains no duplicates.
3615    ///
3616    /// # Examples
3617    ///
3618    /// ```
3619    /// #![feature(slice_partition_dedup)]
3620    ///
3621    /// let mut slice = [10, 20, 21, 30, 30, 20, 11, 13];
3622    ///
3623    /// let (dedup, duplicates) = slice.partition_dedup_by_key(|i| *i / 10);
3624    ///
3625    /// assert_eq!(dedup, [10, 20, 30, 20, 11]);
3626    /// assert_eq!(duplicates, [21, 30, 13]);
3627    /// ```
3628    #[unstable(feature = "slice_partition_dedup", issue = "54279")]
3629    #[inline]
3630    pub fn partition_dedup_by_key<K, F>(&mut self, mut key: F) -> (&mut [T], &mut [T])
3631    where
3632        F: FnMut(&mut T) -> K,
3633        K: PartialEq,
3634    {
3635        self.partition_dedup_by(|a, b| key(a) == key(b))
3636    }
3637
3638    /// Rotates the slice in-place such that the first `mid` elements of the
3639    /// slice move to the end while the last `self.len() - mid` elements move to
3640    /// the front.
3641    ///
3642    /// After calling `rotate_left`, the element previously at index `mid` will
3643    /// become the first element in the slice.
3644    ///
3645    /// # Panics
3646    ///
3647    /// This function will panic if `mid` is greater than the length of the
3648    /// slice. Note that `mid == self.len()` does _not_ panic and is a no-op
3649    /// rotation.
3650    ///
3651    /// # Complexity
3652    ///
3653    /// Takes linear (in `self.len()`) time.
3654    ///
3655    /// # Examples
3656    ///
3657    /// ```
3658    /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
3659    /// a.rotate_left(2);
3660    /// assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
3661    /// ```
3662    ///
3663    /// Rotating a subslice:
3664    ///
3665    /// ```
3666    /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
3667    /// a[1..5].rotate_left(1);
3668    /// assert_eq!(a, ['a', 'c', 'd', 'e', 'b', 'f']);
3669    /// ```
3670    #[stable(feature = "slice_rotate", since = "1.26.0")]
3671    pub fn rotate_left(&mut self, mid: usize) {
3672        assert!(mid <= self.len());
3673        let k = self.len() - mid;
3674        let p = self.as_mut_ptr();
3675
3676        // SAFETY: The range `[p.add(mid) - mid, p.add(mid) + k)` is trivially
3677        // valid for reading and writing, as required by `ptr_rotate`.
3678        unsafe {
3679            rotate::ptr_rotate(mid, p.add(mid), k);
3680        }
3681    }
3682
3683    /// Rotates the slice in-place such that the first `self.len() - k`
3684    /// elements of the slice move to the end while the last `k` elements move
3685    /// to the front.
3686    ///
3687    /// After calling `rotate_right`, the element previously at index
3688    /// `self.len() - k` will become the first element in the slice.
3689    ///
3690    /// # Panics
3691    ///
3692    /// This function will panic if `k` is greater than the length of the
3693    /// slice. Note that `k == self.len()` does _not_ panic and is a no-op
3694    /// rotation.
3695    ///
3696    /// # Complexity
3697    ///
3698    /// Takes linear (in `self.len()`) time.
3699    ///
3700    /// # Examples
3701    ///
3702    /// ```
3703    /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
3704    /// a.rotate_right(2);
3705    /// assert_eq!(a, ['e', 'f', 'a', 'b', 'c', 'd']);
3706    /// ```
3707    ///
3708    /// Rotating a subslice:
3709    ///
3710    /// ```
3711    /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
3712    /// a[1..5].rotate_right(1);
3713    /// assert_eq!(a, ['a', 'e', 'b', 'c', 'd', 'f']);
3714    /// ```
3715    #[stable(feature = "slice_rotate", since = "1.26.0")]
3716    pub fn rotate_right(&mut self, k: usize) {
3717        assert!(k <= self.len());
3718        let mid = self.len() - k;
3719        let p = self.as_mut_ptr();
3720
3721        // SAFETY: The range `[p.add(mid) - mid, p.add(mid) + k)` is trivially
3722        // valid for reading and writing, as required by `ptr_rotate`.
3723        unsafe {
3724            rotate::ptr_rotate(mid, p.add(mid), k);
3725        }
3726    }
3727
3728    /// Fills `self` with elements by cloning `value`.
3729    ///
3730    /// # Examples
3731    ///
3732    /// ```
3733    /// let mut buf = vec![0; 10];
3734    /// buf.fill(1);
3735    /// assert_eq!(buf, vec![1; 10]);
3736    /// ```
3737    #[doc(alias = "memset")]
3738    #[stable(feature = "slice_fill", since = "1.50.0")]
3739    pub fn fill(&mut self, value: T)
3740    where
3741        T: Clone,
3742    {
3743        specialize::SpecFill::spec_fill(self, value);
3744    }
3745
3746    /// Fills `self` with elements returned by calling a closure repeatedly.
3747    ///
3748    /// This method uses a closure to create new values. If you'd rather
3749    /// [`Clone`] a given value, use [`fill`]. If you want to use the [`Default`]
3750    /// trait to generate values, you can pass [`Default::default`] as the
3751    /// argument.
3752    ///
3753    /// [`fill`]: slice::fill
3754    ///
3755    /// # Examples
3756    ///
3757    /// ```
3758    /// let mut buf = vec![1; 10];
3759    /// buf.fill_with(Default::default);
3760    /// assert_eq!(buf, vec![0; 10]);
3761    /// ```
3762    #[stable(feature = "slice_fill_with", since = "1.51.0")]
3763    pub fn fill_with<F>(&mut self, mut f: F)
3764    where
3765        F: FnMut() -> T,
3766    {
3767        for el in self {
3768            *el = f();
3769        }
3770    }
3771
3772    /// Copies the elements from `src` into `self`.
3773    ///
3774    /// The length of `src` must be the same as `self`.
3775    ///
3776    /// # Panics
3777    ///
3778    /// This function will panic if the two slices have different lengths.
3779    ///
3780    /// # Examples
3781    ///
3782    /// Cloning two elements from a slice into another:
3783    ///
3784    /// ```
3785    /// let src = [1, 2, 3, 4];
3786    /// let mut dst = [0, 0];
3787    ///
3788    /// // Because the slices have to be the same length,
3789    /// // we slice the source slice from four elements
3790    /// // to two. It will panic if we don't do this.
3791    /// dst.clone_from_slice(&src[2..]);
3792    ///
3793    /// assert_eq!(src, [1, 2, 3, 4]);
3794    /// assert_eq!(dst, [3, 4]);
3795    /// ```
3796    ///
3797    /// Rust enforces that there can only be one mutable reference with no
3798    /// immutable references to a particular piece of data in a particular
3799    /// scope. Because of this, attempting to use `clone_from_slice` on a
3800    /// single slice will result in a compile failure:
3801    ///
3802    /// ```compile_fail
3803    /// let mut slice = [1, 2, 3, 4, 5];
3804    ///
3805    /// slice[..2].clone_from_slice(&slice[3..]); // compile fail!
3806    /// ```
3807    ///
3808    /// To work around this, we can use [`split_at_mut`] to create two distinct
3809    /// sub-slices from a slice:
3810    ///
3811    /// ```
3812    /// let mut slice = [1, 2, 3, 4, 5];
3813    ///
3814    /// {
3815    ///     let (left, right) = slice.split_at_mut(2);
3816    ///     left.clone_from_slice(&right[1..]);
3817    /// }
3818    ///
3819    /// assert_eq!(slice, [4, 5, 3, 4, 5]);
3820    /// ```
3821    ///
3822    /// [`copy_from_slice`]: slice::copy_from_slice
3823    /// [`split_at_mut`]: slice::split_at_mut
3824    #[stable(feature = "clone_from_slice", since = "1.7.0")]
3825    #[track_caller]
3826    pub fn clone_from_slice(&mut self, src: &[T])
3827    where
3828        T: Clone,
3829    {
3830        self.spec_clone_from(src);
3831    }
3832
3833    /// Copies all elements from `src` into `self`, using a memcpy.
3834    ///
3835    /// The length of `src` must be the same as `self`.
3836    ///
3837    /// If `T` does not implement `Copy`, use [`clone_from_slice`].
3838    ///
3839    /// # Panics
3840    ///
3841    /// This function will panic if the two slices have different lengths.
3842    ///
3843    /// # Examples
3844    ///
3845    /// Copying two elements from a slice into another:
3846    ///
3847    /// ```
3848    /// let src = [1, 2, 3, 4];
3849    /// let mut dst = [0, 0];
3850    ///
3851    /// // Because the slices have to be the same length,
3852    /// // we slice the source slice from four elements
3853    /// // to two. It will panic if we don't do this.
3854    /// dst.copy_from_slice(&src[2..]);
3855    ///
3856    /// assert_eq!(src, [1, 2, 3, 4]);
3857    /// assert_eq!(dst, [3, 4]);
3858    /// ```
3859    ///
3860    /// Rust enforces that there can only be one mutable reference with no
3861    /// immutable references to a particular piece of data in a particular
3862    /// scope. Because of this, attempting to use `copy_from_slice` on a
3863    /// single slice will result in a compile failure:
3864    ///
3865    /// ```compile_fail
3866    /// let mut slice = [1, 2, 3, 4, 5];
3867    ///
3868    /// slice[..2].copy_from_slice(&slice[3..]); // compile fail!
3869    /// ```
3870    ///
3871    /// To work around this, we can use [`split_at_mut`] to create two distinct
3872    /// sub-slices from a slice:
3873    ///
3874    /// ```
3875    /// let mut slice = [1, 2, 3, 4, 5];
3876    ///
3877    /// {
3878    ///     let (left, right) = slice.split_at_mut(2);
3879    ///     left.copy_from_slice(&right[1..]);
3880    /// }
3881    ///
3882    /// assert_eq!(slice, [4, 5, 3, 4, 5]);
3883    /// ```
3884    ///
3885    /// [`clone_from_slice`]: slice::clone_from_slice
3886    /// [`split_at_mut`]: slice::split_at_mut
3887    #[doc(alias = "memcpy")]
3888    #[inline]
3889    #[stable(feature = "copy_from_slice", since = "1.9.0")]
3890    #[rustc_const_stable(feature = "const_copy_from_slice", since = "1.87.0")]
3891    #[track_caller]
3892    pub const fn copy_from_slice(&mut self, src: &[T])
3893    where
3894        T: Copy,
3895    {
3896        // The panic code path was put into a cold function to not bloat the
3897        // call site.
3898        #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never), cold)]
3899        #[cfg_attr(feature = "panic_immediate_abort", inline)]
3900        #[track_caller]
3901        const fn len_mismatch_fail(dst_len: usize, src_len: usize) -> ! {
3902            const_panic!(
3903                "copy_from_slice: source slice length does not match destination slice length",
3904                "copy_from_slice: source slice length ({src_len}) does not match destination slice length ({dst_len})",
3905                src_len: usize,
3906                dst_len: usize,
3907            )
3908        }
3909
3910        if self.len() != src.len() {
3911            len_mismatch_fail(self.len(), src.len());
3912        }
3913
3914        // SAFETY: `self` is valid for `self.len()` elements by definition, and `src` was
3915        // checked to have the same length. The slices cannot overlap because
3916        // mutable references are exclusive.
3917        unsafe {
3918            ptr::copy_nonoverlapping(src.as_ptr(), self.as_mut_ptr(), self.len());
3919        }
3920    }
3921
3922    /// Copies elements from one part of the slice to another part of itself,
3923    /// using a memmove.
3924    ///
3925    /// `src` is the range within `self` to copy from. `dest` is the starting
3926    /// index of the range within `self` to copy to, which will have the same
3927    /// length as `src`. The two ranges may overlap. The ends of the two ranges
3928    /// must be less than or equal to `self.len()`.
3929    ///
3930    /// # Panics
3931    ///
3932    /// This function will panic if either range exceeds the end of the slice,
3933    /// or if the end of `src` is before the start.
3934    ///
3935    /// # Examples
3936    ///
3937    /// Copying four bytes within a slice:
3938    ///
3939    /// ```
3940    /// let mut bytes = *b"Hello, World!";
3941    ///
3942    /// bytes.copy_within(1..5, 8);
3943    ///
3944    /// assert_eq!(&bytes, b"Hello, Wello!");
3945    /// ```
3946    #[stable(feature = "copy_within", since = "1.37.0")]
3947    #[track_caller]
3948    pub fn copy_within<R: RangeBounds<usize>>(&mut self, src: R, dest: usize)
3949    where
3950        T: Copy,
3951    {
3952        let Range { start: src_start, end: src_end } = slice::range(src, ..self.len());
3953        let count = src_end - src_start;
3954        assert!(dest <= self.len() - count, "dest is out of bounds");
3955        // SAFETY: the conditions for `ptr::copy` have all been checked above,
3956        // as have those for `ptr::add`.
3957        unsafe {
3958            // Derive both `src_ptr` and `dest_ptr` from the same loan
3959            let ptr = self.as_mut_ptr();
3960            let src_ptr = ptr.add(src_start);
3961            let dest_ptr = ptr.add(dest);
3962            ptr::copy(src_ptr, dest_ptr, count);
3963        }
3964    }
3965
3966    /// Swaps all elements in `self` with those in `other`.
3967    ///
3968    /// The length of `other` must be the same as `self`.
3969    ///
3970    /// # Panics
3971    ///
3972    /// This function will panic if the two slices have different lengths.
3973    ///
3974    /// # Example
3975    ///
3976    /// Swapping two elements across slices:
3977    ///
3978    /// ```
3979    /// let mut slice1 = [0, 0];
3980    /// let mut slice2 = [1, 2, 3, 4];
3981    ///
3982    /// slice1.swap_with_slice(&mut slice2[2..]);
3983    ///
3984    /// assert_eq!(slice1, [3, 4]);
3985    /// assert_eq!(slice2, [1, 2, 0, 0]);
3986    /// ```
3987    ///
3988    /// Rust enforces that there can only be one mutable reference to a
3989    /// particular piece of data in a particular scope. Because of this,
3990    /// attempting to use `swap_with_slice` on a single slice will result in
3991    /// a compile failure:
3992    ///
3993    /// ```compile_fail
3994    /// let mut slice = [1, 2, 3, 4, 5];
3995    /// slice[..2].swap_with_slice(&mut slice[3..]); // compile fail!
3996    /// ```
3997    ///
3998    /// To work around this, we can use [`split_at_mut`] to create two distinct
3999    /// mutable sub-slices from a slice:
4000    ///
4001    /// ```
4002    /// let mut slice = [1, 2, 3, 4, 5];
4003    ///
4004    /// {
4005    ///     let (left, right) = slice.split_at_mut(2);
4006    ///     left.swap_with_slice(&mut right[1..]);
4007    /// }
4008    ///
4009    /// assert_eq!(slice, [4, 5, 3, 1, 2]);
4010    /// ```
4011    ///
4012    /// [`split_at_mut`]: slice::split_at_mut
4013    #[stable(feature = "swap_with_slice", since = "1.27.0")]
4014    #[track_caller]
4015    pub fn swap_with_slice(&mut self, other: &mut [T]) {
4016        assert!(self.len() == other.len(), "destination and source slices have different lengths");
4017        // SAFETY: `self` is valid for `self.len()` elements by definition, and `src` was
4018        // checked to have the same length. The slices cannot overlap because
4019        // mutable references are exclusive.
4020        unsafe {
4021            ptr::swap_nonoverlapping(self.as_mut_ptr(), other.as_mut_ptr(), self.len());
4022        }
4023    }
4024
4025    /// Function to calculate lengths of the middle and trailing slice for `align_to{,_mut}`.
4026    fn align_to_offsets<U>(&self) -> (usize, usize) {
4027        // What we gonna do about `rest` is figure out what multiple of `U`s we can put in a
4028        // lowest number of `T`s. And how many `T`s we need for each such "multiple".
4029        //
4030        // Consider for example T=u8 U=u16. Then we can put 1 U in 2 Ts. Simple. Now, consider
4031        // for example a case where size_of::<T> = 16, size_of::<U> = 24. We can put 2 Us in
4032        // place of every 3 Ts in the `rest` slice. A bit more complicated.
4033        //
4034        // Formula to calculate this is:
4035        //
4036        // Us = lcm(size_of::<T>, size_of::<U>) / size_of::<U>
4037        // Ts = lcm(size_of::<T>, size_of::<U>) / size_of::<T>
4038        //
4039        // Expanded and simplified:
4040        //
4041        // Us = size_of::<T> / gcd(size_of::<T>, size_of::<U>)
4042        // Ts = size_of::<U> / gcd(size_of::<T>, size_of::<U>)
4043        //
4044        // Luckily since all this is constant-evaluated... performance here matters not!
4045        const fn gcd(a: usize, b: usize) -> usize {
4046            if b == 0 { a } else { gcd(b, a % b) }
4047        }
4048
4049        // Explicitly wrap the function call in a const block so it gets
4050        // constant-evaluated even in debug mode.
4051        let gcd: usize = const { gcd(size_of::<T>(), size_of::<U>()) };
4052        let ts: usize = size_of::<U>() / gcd;
4053        let us: usize = size_of::<T>() / gcd;
4054
4055        // Armed with this knowledge, we can find how many `U`s we can fit!
4056        let us_len = self.len() / ts * us;
4057        // And how many `T`s will be in the trailing slice!
4058        let ts_len = self.len() % ts;
4059        (us_len, ts_len)
4060    }
4061
4062    /// Transmutes the slice to a slice of another type, ensuring alignment of the types is
4063    /// maintained.
4064    ///
4065    /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
4066    /// slice of a new type, and the suffix slice. The middle part will be as big as possible under
4067    /// the given alignment constraint and element size.
4068    ///
4069    /// This method has no purpose when either input element `T` or output element `U` are
4070    /// zero-sized and will return the original slice without splitting anything.
4071    ///
4072    /// # Safety
4073    ///
4074    /// This method is essentially a `transmute` with respect to the elements in the returned
4075    /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
4076    ///
4077    /// # Examples
4078    ///
4079    /// Basic usage:
4080    ///
4081    /// ```
4082    /// unsafe {
4083    ///     let bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
4084    ///     let (prefix, shorts, suffix) = bytes.align_to::<u16>();
4085    ///     // less_efficient_algorithm_for_bytes(prefix);
4086    ///     // more_efficient_algorithm_for_aligned_shorts(shorts);
4087    ///     // less_efficient_algorithm_for_bytes(suffix);
4088    /// }
4089    /// ```
4090    #[stable(feature = "slice_align_to", since = "1.30.0")]
4091    #[must_use]
4092    pub unsafe fn align_to<U>(&self) -> (&[T], &[U], &[T]) {
4093        // Note that most of this function will be constant-evaluated,
4094        if U::IS_ZST || T::IS_ZST {
4095            // handle ZSTs specially, which is – don't handle them at all.
4096            return (self, &[], &[]);
4097        }
4098
4099        // First, find at what point do we split between the first and 2nd slice. Easy with
4100        // ptr.align_offset.
4101        let ptr = self.as_ptr();
4102        // SAFETY: See the `align_to_mut` method for the detailed safety comment.
4103        let offset = unsafe { crate::ptr::align_offset(ptr, align_of::<U>()) };
4104        if offset > self.len() {
4105            (self, &[], &[])
4106        } else {
4107            let (left, rest) = self.split_at(offset);
4108            let (us_len, ts_len) = rest.align_to_offsets::<U>();
4109            // Inform Miri that we want to consider the "middle" pointer to be suitably aligned.
4110            #[cfg(miri)]
4111            crate::intrinsics::miri_promise_symbolic_alignment(
4112                rest.as_ptr().cast(),
4113                align_of::<U>(),
4114            );
4115            // SAFETY: now `rest` is definitely aligned, so `from_raw_parts` below is okay,
4116            // since the caller guarantees that we can transmute `T` to `U` safely.
4117            unsafe {
4118                (
4119                    left,
4120                    from_raw_parts(rest.as_ptr() as *const U, us_len),
4121                    from_raw_parts(rest.as_ptr().add(rest.len() - ts_len), ts_len),
4122                )
4123            }
4124        }
4125    }
4126
4127    /// Transmutes the mutable slice to a mutable slice of another type, ensuring alignment of the
4128    /// types is maintained.
4129    ///
4130    /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
4131    /// slice of a new type, and the suffix slice. The middle part will be as big as possible under
4132    /// the given alignment constraint and element size.
4133    ///
4134    /// This method has no purpose when either input element `T` or output element `U` are
4135    /// zero-sized and will return the original slice without splitting anything.
4136    ///
4137    /// # Safety
4138    ///
4139    /// This method is essentially a `transmute` with respect to the elements in the returned
4140    /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
4141    ///
4142    /// # Examples
4143    ///
4144    /// Basic usage:
4145    ///
4146    /// ```
4147    /// unsafe {
4148    ///     let mut bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
4149    ///     let (prefix, shorts, suffix) = bytes.align_to_mut::<u16>();
4150    ///     // less_efficient_algorithm_for_bytes(prefix);
4151    ///     // more_efficient_algorithm_for_aligned_shorts(shorts);
4152    ///     // less_efficient_algorithm_for_bytes(suffix);
4153    /// }
4154    /// ```
4155    #[stable(feature = "slice_align_to", since = "1.30.0")]
4156    #[must_use]
4157    pub unsafe fn align_to_mut<U>(&mut self) -> (&mut [T], &mut [U], &mut [T]) {
4158        // Note that most of this function will be constant-evaluated,
4159        if U::IS_ZST || T::IS_ZST {
4160            // handle ZSTs specially, which is – don't handle them at all.
4161            return (self, &mut [], &mut []);
4162        }
4163
4164        // First, find at what point do we split between the first and 2nd slice. Easy with
4165        // ptr.align_offset.
4166        let ptr = self.as_ptr();
4167        // SAFETY: Here we are ensuring we will use aligned pointers for U for the
4168        // rest of the method. This is done by passing a pointer to &[T] with an
4169        // alignment targeted for U.
4170        // `crate::ptr::align_offset` is called with a correctly aligned and
4171        // valid pointer `ptr` (it comes from a reference to `self`) and with
4172        // a size that is a power of two (since it comes from the alignment for U),
4173        // satisfying its safety constraints.
4174        let offset = unsafe { crate::ptr::align_offset(ptr, align_of::<U>()) };
4175        if offset > self.len() {
4176            (self, &mut [], &mut [])
4177        } else {
4178            let (left, rest) = self.split_at_mut(offset);
4179            let (us_len, ts_len) = rest.align_to_offsets::<U>();
4180            let rest_len = rest.len();
4181            let mut_ptr = rest.as_mut_ptr();
4182            // Inform Miri that we want to consider the "middle" pointer to be suitably aligned.
4183            #[cfg(miri)]
4184            crate::intrinsics::miri_promise_symbolic_alignment(
4185                mut_ptr.cast() as *const (),
4186                align_of::<U>(),
4187            );
4188            // We can't use `rest` again after this, that would invalidate its alias `mut_ptr`!
4189            // SAFETY: see comments for `align_to`.
4190            unsafe {
4191                (
4192                    left,
4193                    from_raw_parts_mut(mut_ptr as *mut U, us_len),
4194                    from_raw_parts_mut(mut_ptr.add(rest_len - ts_len), ts_len),
4195                )
4196            }
4197        }
4198    }
4199
4200    /// Splits a slice into a prefix, a middle of aligned SIMD types, and a suffix.
4201    ///
4202    /// This is a safe wrapper around [`slice::align_to`], so inherits the same
4203    /// guarantees as that method.
4204    ///
4205    /// # Panics
4206    ///
4207    /// This will panic if the size of the SIMD type is different from
4208    /// `LANES` times that of the scalar.
4209    ///
4210    /// At the time of writing, the trait restrictions on `Simd<T, LANES>` keeps
4211    /// that from ever happening, as only power-of-two numbers of lanes are
4212    /// supported.  It's possible that, in the future, those restrictions might
4213    /// be lifted in a way that would make it possible to see panics from this
4214    /// method for something like `LANES == 3`.
4215    ///
4216    /// # Examples
4217    ///
4218    /// ```
4219    /// #![feature(portable_simd)]
4220    /// use core::simd::prelude::*;
4221    ///
4222    /// let short = &[1, 2, 3];
4223    /// let (prefix, middle, suffix) = short.as_simd::<4>();
4224    /// assert_eq!(middle, []); // Not enough elements for anything in the middle
4225    ///
4226    /// // They might be split in any possible way between prefix and suffix
4227    /// let it = prefix.iter().chain(suffix).copied();
4228    /// assert_eq!(it.collect::<Vec<_>>(), vec![1, 2, 3]);
4229    ///
4230    /// fn basic_simd_sum(x: &[f32]) -> f32 {
4231    ///     use std::ops::Add;
4232    ///     let (prefix, middle, suffix) = x.as_simd();
4233    ///     let sums = f32x4::from_array([
4234    ///         prefix.iter().copied().sum(),
4235    ///         0.0,
4236    ///         0.0,
4237    ///         suffix.iter().copied().sum(),
4238    ///     ]);
4239    ///     let sums = middle.iter().copied().fold(sums, f32x4::add);
4240    ///     sums.reduce_sum()
4241    /// }
4242    ///
4243    /// let numbers: Vec<f32> = (1..101).map(|x| x as _).collect();
4244    /// assert_eq!(basic_simd_sum(&numbers[1..99]), 4949.0);
4245    /// ```
4246    #[unstable(feature = "portable_simd", issue = "86656")]
4247    #[must_use]
4248    pub fn as_simd<const LANES: usize>(&self) -> (&[T], &[Simd<T, LANES>], &[T])
4249    where
4250        Simd<T, LANES>: AsRef<[T; LANES]>,
4251        T: simd::SimdElement,
4252        simd::LaneCount<LANES>: simd::SupportedLaneCount,
4253    {
4254        // These are expected to always match, as vector types are laid out like
4255        // arrays per <https://llvm.org/docs/LangRef.html#vector-type>, but we
4256        // might as well double-check since it'll optimize away anyhow.
4257        assert_eq!(size_of::<Simd<T, LANES>>(), size_of::<[T; LANES]>());
4258
4259        // SAFETY: The simd types have the same layout as arrays, just with
4260        // potentially-higher alignment, so the de-facto transmutes are sound.
4261        unsafe { self.align_to() }
4262    }
4263
4264    /// Splits a mutable slice into a mutable prefix, a middle of aligned SIMD types,
4265    /// and a mutable suffix.
4266    ///
4267    /// This is a safe wrapper around [`slice::align_to_mut`], so inherits the same
4268    /// guarantees as that method.
4269    ///
4270    /// This is the mutable version of [`slice::as_simd`]; see that for examples.
4271    ///
4272    /// # Panics
4273    ///
4274    /// This will panic if the size of the SIMD type is different from
4275    /// `LANES` times that of the scalar.
4276    ///
4277    /// At the time of writing, the trait restrictions on `Simd<T, LANES>` keeps
4278    /// that from ever happening, as only power-of-two numbers of lanes are
4279    /// supported.  It's possible that, in the future, those restrictions might
4280    /// be lifted in a way that would make it possible to see panics from this
4281    /// method for something like `LANES == 3`.
4282    #[unstable(feature = "portable_simd", issue = "86656")]
4283    #[must_use]
4284    pub fn as_simd_mut<const LANES: usize>(&mut self) -> (&mut [T], &mut [Simd<T, LANES>], &mut [T])
4285    where
4286        Simd<T, LANES>: AsMut<[T; LANES]>,
4287        T: simd::SimdElement,
4288        simd::LaneCount<LANES>: simd::SupportedLaneCount,
4289    {
4290        // These are expected to always match, as vector types are laid out like
4291        // arrays per <https://llvm.org/docs/LangRef.html#vector-type>, but we
4292        // might as well double-check since it'll optimize away anyhow.
4293        assert_eq!(size_of::<Simd<T, LANES>>(), size_of::<[T; LANES]>());
4294
4295        // SAFETY: The simd types have the same layout as arrays, just with
4296        // potentially-higher alignment, so the de-facto transmutes are sound.
4297        unsafe { self.align_to_mut() }
4298    }
4299
4300    /// Checks if the elements of this slice are sorted.
4301    ///
4302    /// That is, for each element `a` and its following element `b`, `a <= b` must hold. If the
4303    /// slice yields exactly zero or one element, `true` is returned.
4304    ///
4305    /// Note that if `Self::Item` is only `PartialOrd`, but not `Ord`, the above definition
4306    /// implies that this function returns `false` if any two consecutive items are not
4307    /// comparable.
4308    ///
4309    /// # Examples
4310    ///
4311    /// ```
4312    /// let empty: [i32; 0] = [];
4313    ///
4314    /// assert!([1, 2, 2, 9].is_sorted());
4315    /// assert!(![1, 3, 2, 4].is_sorted());
4316    /// assert!([0].is_sorted());
4317    /// assert!(empty.is_sorted());
4318    /// assert!(![0.0, 1.0, f32::NAN].is_sorted());
4319    /// ```
4320    #[inline]
4321    #[stable(feature = "is_sorted", since = "1.82.0")]
4322    #[must_use]
4323    pub fn is_sorted(&self) -> bool
4324    where
4325        T: PartialOrd,
4326    {
4327        // This odd number works the best. 32 + 1 extra due to overlapping chunk boundaries.
4328        const CHUNK_SIZE: usize = 33;
4329        if self.len() < CHUNK_SIZE {
4330            return self.windows(2).all(|w| w[0] <= w[1]);
4331        }
4332        let mut i = 0;
4333        // Check in chunks for autovectorization.
4334        while i < self.len() - CHUNK_SIZE {
4335            let chunk = &self[i..i + CHUNK_SIZE];
4336            if !chunk.windows(2).fold(true, |acc, w| acc & (w[0] <= w[1])) {
4337                return false;
4338            }
4339            // We need to ensure that chunk boundaries are also sorted.
4340            // Overlap the next chunk with the last element of our last chunk.
4341            i += CHUNK_SIZE - 1;
4342        }
4343        self[i..].windows(2).all(|w| w[0] <= w[1])
4344    }
4345
4346    /// Checks if the elements of this slice are sorted using the given comparator function.
4347    ///
4348    /// Instead of using `PartialOrd::partial_cmp`, this function uses the given `compare`
4349    /// function to determine whether two elements are to be considered in sorted order.
4350    ///
4351    /// # Examples
4352    ///
4353    /// ```
4354    /// assert!([1, 2, 2, 9].is_sorted_by(|a, b| a <= b));
4355    /// assert!(![1, 2, 2, 9].is_sorted_by(|a, b| a < b));
4356    ///
4357    /// assert!([0].is_sorted_by(|a, b| true));
4358    /// assert!([0].is_sorted_by(|a, b| false));
4359    ///
4360    /// let empty: [i32; 0] = [];
4361    /// assert!(empty.is_sorted_by(|a, b| false));
4362    /// assert!(empty.is_sorted_by(|a, b| true));
4363    /// ```
4364    #[stable(feature = "is_sorted", since = "1.82.0")]
4365    #[must_use]
4366    pub fn is_sorted_by<'a, F>(&'a self, mut compare: F) -> bool
4367    where
4368        F: FnMut(&'a T, &'a T) -> bool,
4369    {
4370        self.array_windows().all(|[a, b]| compare(a, b))
4371    }
4372
4373    /// Checks if the elements of this slice are sorted using the given key extraction function.
4374    ///
4375    /// Instead of comparing the slice's elements directly, this function compares the keys of the
4376    /// elements, as determined by `f`. Apart from that, it's equivalent to [`is_sorted`]; see its
4377    /// documentation for more information.
4378    ///
4379    /// [`is_sorted`]: slice::is_sorted
4380    ///
4381    /// # Examples
4382    ///
4383    /// ```
4384    /// assert!(["c", "bb", "aaa"].is_sorted_by_key(|s| s.len()));
4385    /// assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
4386    /// ```
4387    #[inline]
4388    #[stable(feature = "is_sorted", since = "1.82.0")]
4389    #[must_use]
4390    pub fn is_sorted_by_key<'a, F, K>(&'a self, f: F) -> bool
4391    where
4392        F: FnMut(&'a T) -> K,
4393        K: PartialOrd,
4394    {
4395        self.iter().is_sorted_by_key(f)
4396    }
4397
4398    /// Returns the index of the partition point according to the given predicate
4399    /// (the index of the first element of the second partition).
4400    ///
4401    /// The slice is assumed to be partitioned according to the given predicate.
4402    /// This means that all elements for which the predicate returns true are at the start of the slice
4403    /// and all elements for which the predicate returns false are at the end.
4404    /// For example, `[7, 15, 3, 5, 4, 12, 6]` is partitioned under the predicate `x % 2 != 0`
4405    /// (all odd numbers are at the start, all even at the end).
4406    ///
4407    /// If this slice is not partitioned, the returned result is unspecified and meaningless,
4408    /// as this method performs a kind of binary search.
4409    ///
4410    /// See also [`binary_search`], [`binary_search_by`], and [`binary_search_by_key`].
4411    ///
4412    /// [`binary_search`]: slice::binary_search
4413    /// [`binary_search_by`]: slice::binary_search_by
4414    /// [`binary_search_by_key`]: slice::binary_search_by_key
4415    ///
4416    /// # Examples
4417    ///
4418    /// ```
4419    /// let v = [1, 2, 3, 3, 5, 6, 7];
4420    /// let i = v.partition_point(|&x| x < 5);
4421    ///
4422    /// assert_eq!(i, 4);
4423    /// assert!(v[..i].iter().all(|&x| x < 5));
4424    /// assert!(v[i..].iter().all(|&x| !(x < 5)));
4425    /// ```
4426    ///
4427    /// If all elements of the slice match the predicate, including if the slice
4428    /// is empty, then the length of the slice will be returned:
4429    ///
4430    /// ```
4431    /// let a = [2, 4, 8];
4432    /// assert_eq!(a.partition_point(|x| x < &100), a.len());
4433    /// let a: [i32; 0] = [];
4434    /// assert_eq!(a.partition_point(|x| x < &100), 0);
4435    /// ```
4436    ///
4437    /// If you want to insert an item to a sorted vector, while maintaining
4438    /// sort order:
4439    ///
4440    /// ```
4441    /// let mut s = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
4442    /// let num = 42;
4443    /// let idx = s.partition_point(|&x| x <= num);
4444    /// s.insert(idx, num);
4445    /// assert_eq!(s, [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
4446    /// ```
4447    #[stable(feature = "partition_point", since = "1.52.0")]
4448    #[must_use]
4449    pub fn partition_point<P>(&self, mut pred: P) -> usize
4450    where
4451        P: FnMut(&T) -> bool,
4452    {
4453        self.binary_search_by(|x| if pred(x) { Less } else { Greater }).unwrap_or_else(|i| i)
4454    }
4455
4456    /// Removes the subslice corresponding to the given range
4457    /// and returns a reference to it.
4458    ///
4459    /// Returns `None` and does not modify the slice if the given
4460    /// range is out of bounds.
4461    ///
4462    /// Note that this method only accepts one-sided ranges such as
4463    /// `2..` or `..6`, but not `2..6`.
4464    ///
4465    /// # Examples
4466    ///
4467    /// Splitting off the first three elements of a slice:
4468    ///
4469    /// ```
4470    /// let mut slice: &[_] = &['a', 'b', 'c', 'd'];
4471    /// let mut first_three = slice.split_off(..3).unwrap();
4472    ///
4473    /// assert_eq!(slice, &['d']);
4474    /// assert_eq!(first_three, &['a', 'b', 'c']);
4475    /// ```
4476    ///
4477    /// Splitting off a slice starting with the third element:
4478    ///
4479    /// ```
4480    /// let mut slice: &[_] = &['a', 'b', 'c', 'd'];
4481    /// let mut tail = slice.split_off(2..).unwrap();
4482    ///
4483    /// assert_eq!(slice, &['a', 'b']);
4484    /// assert_eq!(tail, &['c', 'd']);
4485    /// ```
4486    ///
4487    /// Getting `None` when `range` is out of bounds:
4488    ///
4489    /// ```
4490    /// let mut slice: &[_] = &['a', 'b', 'c', 'd'];
4491    ///
4492    /// assert_eq!(None, slice.split_off(5..));
4493    /// assert_eq!(None, slice.split_off(..5));
4494    /// assert_eq!(None, slice.split_off(..=4));
4495    /// let expected: &[char] = &['a', 'b', 'c', 'd'];
4496    /// assert_eq!(Some(expected), slice.split_off(..4));
4497    /// ```
4498    #[inline]
4499    #[must_use = "method does not modify the slice if the range is out of bounds"]
4500    #[stable(feature = "slice_take", since = "1.87.0")]
4501    pub fn split_off<'a, R: OneSidedRange<usize>>(
4502        self: &mut &'a Self,
4503        range: R,
4504    ) -> Option<&'a Self> {
4505        let (direction, split_index) = split_point_of(range)?;
4506        if split_index > self.len() {
4507            return None;
4508        }
4509        let (front, back) = self.split_at(split_index);
4510        match direction {
4511            Direction::Front => {
4512                *self = back;
4513                Some(front)
4514            }
4515            Direction::Back => {
4516                *self = front;
4517                Some(back)
4518            }
4519        }
4520    }
4521
4522    /// Removes the subslice corresponding to the given range
4523    /// and returns a mutable reference to it.
4524    ///
4525    /// Returns `None` and does not modify the slice if the given
4526    /// range is out of bounds.
4527    ///
4528    /// Note that this method only accepts one-sided ranges such as
4529    /// `2..` or `..6`, but not `2..6`.
4530    ///
4531    /// # Examples
4532    ///
4533    /// Splitting off the first three elements of a slice:
4534    ///
4535    /// ```
4536    /// let mut slice: &mut [_] = &mut ['a', 'b', 'c', 'd'];
4537    /// let mut first_three = slice.split_off_mut(..3).unwrap();
4538    ///
4539    /// assert_eq!(slice, &mut ['d']);
4540    /// assert_eq!(first_three, &mut ['a', 'b', 'c']);
4541    /// ```
4542    ///
4543    /// Splitting off a slice starting with the third element:
4544    ///
4545    /// ```
4546    /// let mut slice: &mut [_] = &mut ['a', 'b', 'c', 'd'];
4547    /// let mut tail = slice.split_off_mut(2..).unwrap();
4548    ///
4549    /// assert_eq!(slice, &mut ['a', 'b']);
4550    /// assert_eq!(tail, &mut ['c', 'd']);
4551    /// ```
4552    ///
4553    /// Getting `None` when `range` is out of bounds:
4554    ///
4555    /// ```
4556    /// let mut slice: &mut [_] = &mut ['a', 'b', 'c', 'd'];
4557    ///
4558    /// assert_eq!(None, slice.split_off_mut(5..));
4559    /// assert_eq!(None, slice.split_off_mut(..5));
4560    /// assert_eq!(None, slice.split_off_mut(..=4));
4561    /// let expected: &mut [_] = &mut ['a', 'b', 'c', 'd'];
4562    /// assert_eq!(Some(expected), slice.split_off_mut(..4));
4563    /// ```
4564    #[inline]
4565    #[must_use = "method does not modify the slice if the range is out of bounds"]
4566    #[stable(feature = "slice_take", since = "1.87.0")]
4567    pub fn split_off_mut<'a, R: OneSidedRange<usize>>(
4568        self: &mut &'a mut Self,
4569        range: R,
4570    ) -> Option<&'a mut Self> {
4571        let (direction, split_index) = split_point_of(range)?;
4572        if split_index > self.len() {
4573            return None;
4574        }
4575        let (front, back) = mem::take(self).split_at_mut(split_index);
4576        match direction {
4577            Direction::Front => {
4578                *self = back;
4579                Some(front)
4580            }
4581            Direction::Back => {
4582                *self = front;
4583                Some(back)
4584            }
4585        }
4586    }
4587
4588    /// Removes the first element of the slice and returns a reference
4589    /// to it.
4590    ///
4591    /// Returns `None` if the slice is empty.
4592    ///
4593    /// # Examples
4594    ///
4595    /// ```
4596    /// let mut slice: &[_] = &['a', 'b', 'c'];
4597    /// let first = slice.split_off_first().unwrap();
4598    ///
4599    /// assert_eq!(slice, &['b', 'c']);
4600    /// assert_eq!(first, &'a');
4601    /// ```
4602    #[inline]
4603    #[stable(feature = "slice_take", since = "1.87.0")]
4604    #[rustc_const_unstable(feature = "const_split_off_first_last", issue = "138539")]
4605    pub const fn split_off_first<'a>(self: &mut &'a Self) -> Option<&'a T> {
4606        // FIXME(const-hack): Use `?` when available in const instead of `let-else`.
4607        let Some((first, rem)) = self.split_first() else { return None };
4608        *self = rem;
4609        Some(first)
4610    }
4611
4612    /// Removes the first element of the slice and returns a mutable
4613    /// reference to it.
4614    ///
4615    /// Returns `None` if the slice is empty.
4616    ///
4617    /// # Examples
4618    ///
4619    /// ```
4620    /// let mut slice: &mut [_] = &mut ['a', 'b', 'c'];
4621    /// let first = slice.split_off_first_mut().unwrap();
4622    /// *first = 'd';
4623    ///
4624    /// assert_eq!(slice, &['b', 'c']);
4625    /// assert_eq!(first, &'d');
4626    /// ```
4627    #[inline]
4628    #[stable(feature = "slice_take", since = "1.87.0")]
4629    #[rustc_const_unstable(feature = "const_split_off_first_last", issue = "138539")]
4630    pub const fn split_off_first_mut<'a>(self: &mut &'a mut Self) -> Option<&'a mut T> {
4631        // FIXME(const-hack): Use `mem::take` and `?` when available in const.
4632        // Original: `mem::take(self).split_first_mut()?`
4633        let Some((first, rem)) = mem::replace(self, &mut []).split_first_mut() else { return None };
4634        *self = rem;
4635        Some(first)
4636    }
4637
4638    /// Removes the last element of the slice and returns a reference
4639    /// to it.
4640    ///
4641    /// Returns `None` if the slice is empty.
4642    ///
4643    /// # Examples
4644    ///
4645    /// ```
4646    /// let mut slice: &[_] = &['a', 'b', 'c'];
4647    /// let last = slice.split_off_last().unwrap();
4648    ///
4649    /// assert_eq!(slice, &['a', 'b']);
4650    /// assert_eq!(last, &'c');
4651    /// ```
4652    #[inline]
4653    #[stable(feature = "slice_take", since = "1.87.0")]
4654    #[rustc_const_unstable(feature = "const_split_off_first_last", issue = "138539")]
4655    pub const fn split_off_last<'a>(self: &mut &'a Self) -> Option<&'a T> {
4656        // FIXME(const-hack): Use `?` when available in const instead of `let-else`.
4657        let Some((last, rem)) = self.split_last() else { return None };
4658        *self = rem;
4659        Some(last)
4660    }
4661
4662    /// Removes the last element of the slice and returns a mutable
4663    /// reference to it.
4664    ///
4665    /// Returns `None` if the slice is empty.
4666    ///
4667    /// # Examples
4668    ///
4669    /// ```
4670    /// let mut slice: &mut [_] = &mut ['a', 'b', 'c'];
4671    /// let last = slice.split_off_last_mut().unwrap();
4672    /// *last = 'd';
4673    ///
4674    /// assert_eq!(slice, &['a', 'b']);
4675    /// assert_eq!(last, &'d');
4676    /// ```
4677    #[inline]
4678    #[stable(feature = "slice_take", since = "1.87.0")]
4679    #[rustc_const_unstable(feature = "const_split_off_first_last", issue = "138539")]
4680    pub const fn split_off_last_mut<'a>(self: &mut &'a mut Self) -> Option<&'a mut T> {
4681        // FIXME(const-hack): Use `mem::take` and `?` when available in const.
4682        // Original: `mem::take(self).split_last_mut()?`
4683        let Some((last, rem)) = mem::replace(self, &mut []).split_last_mut() else { return None };
4684        *self = rem;
4685        Some(last)
4686    }
4687
4688    /// Returns mutable references to many indices at once, without doing any checks.
4689    ///
4690    /// An index can be either a `usize`, a [`Range`] or a [`RangeInclusive`]. Note
4691    /// that this method takes an array, so all indices must be of the same type.
4692    /// If passed an array of `usize`s this method gives back an array of mutable references
4693    /// to single elements, while if passed an array of ranges it gives back an array of
4694    /// mutable references to slices.
4695    ///
4696    /// For a safe alternative see [`get_disjoint_mut`].
4697    ///
4698    /// # Safety
4699    ///
4700    /// Calling this method with overlapping or out-of-bounds indices is *[undefined behavior]*
4701    /// even if the resulting references are not used.
4702    ///
4703    /// # Examples
4704    ///
4705    /// ```
4706    /// let x = &mut [1, 2, 4];
4707    ///
4708    /// unsafe {
4709    ///     let [a, b] = x.get_disjoint_unchecked_mut([0, 2]);
4710    ///     *a *= 10;
4711    ///     *b *= 100;
4712    /// }
4713    /// assert_eq!(x, &[10, 2, 400]);
4714    ///
4715    /// unsafe {
4716    ///     let [a, b] = x.get_disjoint_unchecked_mut([0..1, 1..3]);
4717    ///     a[0] = 8;
4718    ///     b[0] = 88;
4719    ///     b[1] = 888;
4720    /// }
4721    /// assert_eq!(x, &[8, 88, 888]);
4722    ///
4723    /// unsafe {
4724    ///     let [a, b] = x.get_disjoint_unchecked_mut([1..=2, 0..=0]);
4725    ///     a[0] = 11;
4726    ///     a[1] = 111;
4727    ///     b[0] = 1;
4728    /// }
4729    /// assert_eq!(x, &[1, 11, 111]);
4730    /// ```
4731    ///
4732    /// [`get_disjoint_mut`]: slice::get_disjoint_mut
4733    /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
4734    #[stable(feature = "get_many_mut", since = "1.86.0")]
4735    #[inline]
4736    #[track_caller]
4737    pub unsafe fn get_disjoint_unchecked_mut<I, const N: usize>(
4738        &mut self,
4739        indices: [I; N],
4740    ) -> [&mut I::Output; N]
4741    where
4742        I: GetDisjointMutIndex + SliceIndex<Self>,
4743    {
4744        // NB: This implementation is written as it is because any variation of
4745        // `indices.map(|i| self.get_unchecked_mut(i))` would make miri unhappy,
4746        // or generate worse code otherwise. This is also why we need to go
4747        // through a raw pointer here.
4748        let slice: *mut [T] = self;
4749        let mut arr: MaybeUninit<[&mut I::Output; N]> = MaybeUninit::uninit();
4750        let arr_ptr = arr.as_mut_ptr();
4751
4752        // SAFETY: We expect `indices` to contain disjunct values that are
4753        // in bounds of `self`.
4754        unsafe {
4755            for i in 0..N {
4756                let idx = indices.get_unchecked(i).clone();
4757                arr_ptr.cast::<&mut I::Output>().add(i).write(&mut *slice.get_unchecked_mut(idx));
4758            }
4759            arr.assume_init()
4760        }
4761    }
4762
4763    /// Returns mutable references to many indices at once.
4764    ///
4765    /// An index can be either a `usize`, a [`Range`] or a [`RangeInclusive`]. Note
4766    /// that this method takes an array, so all indices must be of the same type.
4767    /// If passed an array of `usize`s this method gives back an array of mutable references
4768    /// to single elements, while if passed an array of ranges it gives back an array of
4769    /// mutable references to slices.
4770    ///
4771    /// Returns an error if any index is out-of-bounds, or if there are overlapping indices.
4772    /// An empty range is not considered to overlap if it is located at the beginning or at
4773    /// the end of another range, but is considered to overlap if it is located in the middle.
4774    ///
4775    /// This method does a O(n^2) check to check that there are no overlapping indices, so be careful
4776    /// when passing many indices.
4777    ///
4778    /// # Examples
4779    ///
4780    /// ```
4781    /// let v = &mut [1, 2, 3];
4782    /// if let Ok([a, b]) = v.get_disjoint_mut([0, 2]) {
4783    ///     *a = 413;
4784    ///     *b = 612;
4785    /// }
4786    /// assert_eq!(v, &[413, 2, 612]);
4787    ///
4788    /// if let Ok([a, b]) = v.get_disjoint_mut([0..1, 1..3]) {
4789    ///     a[0] = 8;
4790    ///     b[0] = 88;
4791    ///     b[1] = 888;
4792    /// }
4793    /// assert_eq!(v, &[8, 88, 888]);
4794    ///
4795    /// if let Ok([a, b]) = v.get_disjoint_mut([1..=2, 0..=0]) {
4796    ///     a[0] = 11;
4797    ///     a[1] = 111;
4798    ///     b[0] = 1;
4799    /// }
4800    /// assert_eq!(v, &[1, 11, 111]);
4801    /// ```
4802    #[stable(feature = "get_many_mut", since = "1.86.0")]
4803    #[inline]
4804    pub fn get_disjoint_mut<I, const N: usize>(
4805        &mut self,
4806        indices: [I; N],
4807    ) -> Result<[&mut I::Output; N], GetDisjointMutError>
4808    where
4809        I: GetDisjointMutIndex + SliceIndex<Self>,
4810    {
4811        get_disjoint_check_valid(&indices, self.len())?;
4812        // SAFETY: The `get_disjoint_check_valid()` call checked that all indices
4813        // are disjunct and in bounds.
4814        unsafe { Ok(self.get_disjoint_unchecked_mut(indices)) }
4815    }
4816
4817    /// Returns the index that an element reference points to.
4818    ///
4819    /// Returns `None` if `element` does not point to the start of an element within the slice.
4820    ///
4821    /// This method is useful for extending slice iterators like [`slice::split`].
4822    ///
4823    /// Note that this uses pointer arithmetic and **does not compare elements**.
4824    /// To find the index of an element via comparison, use
4825    /// [`.iter().position()`](crate::iter::Iterator::position) instead.
4826    ///
4827    /// # Panics
4828    /// Panics if `T` is zero-sized.
4829    ///
4830    /// # Examples
4831    /// Basic usage:
4832    /// ```
4833    /// #![feature(substr_range)]
4834    ///
4835    /// let nums: &[u32] = &[1, 7, 1, 1];
4836    /// let num = &nums[2];
4837    ///
4838    /// assert_eq!(num, &1);
4839    /// assert_eq!(nums.element_offset(num), Some(2));
4840    /// ```
4841    /// Returning `None` with an unaligned element:
4842    /// ```
4843    /// #![feature(substr_range)]
4844    ///
4845    /// let arr: &[[u32; 2]] = &[[0, 1], [2, 3]];
4846    /// let flat_arr: &[u32] = arr.as_flattened();
4847    ///
4848    /// let ok_elm: &[u32; 2] = flat_arr[0..2].try_into().unwrap();
4849    /// let weird_elm: &[u32; 2] = flat_arr[1..3].try_into().unwrap();
4850    ///
4851    /// assert_eq!(ok_elm, &[0, 1]);
4852    /// assert_eq!(weird_elm, &[1, 2]);
4853    ///
4854    /// assert_eq!(arr.element_offset(ok_elm), Some(0)); // Points to element 0
4855    /// assert_eq!(arr.element_offset(weird_elm), None); // Points between element 0 and 1
4856    /// ```
4857    #[must_use]
4858    #[unstable(feature = "substr_range", issue = "126769")]
4859    pub fn element_offset(&self, element: &T) -> Option<usize> {
4860        if T::IS_ZST {
4861            panic!("elements are zero-sized");
4862        }
4863
4864        let self_start = self.as_ptr().addr();
4865        let elem_start = ptr::from_ref(element).addr();
4866
4867        let byte_offset = elem_start.wrapping_sub(self_start);
4868
4869        if !byte_offset.is_multiple_of(size_of::<T>()) {
4870            return None;
4871        }
4872
4873        let offset = byte_offset / size_of::<T>();
4874
4875        if offset < self.len() { Some(offset) } else { None }
4876    }
4877
4878    /// Returns the range of indices that a subslice points to.
4879    ///
4880    /// Returns `None` if `subslice` does not point within the slice or if it is not aligned with the
4881    /// elements in the slice.
4882    ///
4883    /// This method **does not compare elements**. Instead, this method finds the location in the slice that
4884    /// `subslice` was obtained from. To find the index of a subslice via comparison, instead use
4885    /// [`.windows()`](slice::windows)[`.position()`](crate::iter::Iterator::position).
4886    ///
4887    /// This method is useful for extending slice iterators like [`slice::split`].
4888    ///
4889    /// Note that this may return a false positive (either `Some(0..0)` or `Some(self.len()..self.len())`)
4890    /// if `subslice` has a length of zero and points to the beginning or end of another, separate, slice.
4891    ///
4892    /// # Panics
4893    /// Panics if `T` is zero-sized.
4894    ///
4895    /// # Examples
4896    /// Basic usage:
4897    /// ```
4898    /// #![feature(substr_range)]
4899    ///
4900    /// let nums = &[0, 5, 10, 0, 0, 5];
4901    ///
4902    /// let mut iter = nums
4903    ///     .split(|t| *t == 0)
4904    ///     .map(|n| nums.subslice_range(n).unwrap());
4905    ///
4906    /// assert_eq!(iter.next(), Some(0..0));
4907    /// assert_eq!(iter.next(), Some(1..3));
4908    /// assert_eq!(iter.next(), Some(4..4));
4909    /// assert_eq!(iter.next(), Some(5..6));
4910    /// ```
4911    #[must_use]
4912    #[unstable(feature = "substr_range", issue = "126769")]
4913    pub fn subslice_range(&self, subslice: &[T]) -> Option<Range<usize>> {
4914        if T::IS_ZST {
4915            panic!("elements are zero-sized");
4916        }
4917
4918        let self_start = self.as_ptr().addr();
4919        let subslice_start = subslice.as_ptr().addr();
4920
4921        let byte_start = subslice_start.wrapping_sub(self_start);
4922
4923        if !byte_start.is_multiple_of(size_of::<T>()) {
4924            return None;
4925        }
4926
4927        let start = byte_start / size_of::<T>();
4928        let end = start.wrapping_add(subslice.len());
4929
4930        if start <= self.len() && end <= self.len() { Some(start..end) } else { None }
4931    }
4932}
4933
4934impl<T> [MaybeUninit<T>] {
4935    /// Transmutes the mutable uninitialized slice to a mutable uninitialized slice of
4936    /// another type, ensuring alignment of the types is maintained.
4937    ///
4938    /// This is a safe wrapper around [`slice::align_to_mut`], so inherits the same
4939    /// guarantees as that method.
4940    ///
4941    /// # Examples
4942    ///
4943    /// ```
4944    /// #![feature(align_to_uninit_mut)]
4945    /// use std::mem::MaybeUninit;
4946    ///
4947    /// pub struct BumpAllocator<'scope> {
4948    ///     memory: &'scope mut [MaybeUninit<u8>],
4949    /// }
4950    ///
4951    /// impl<'scope> BumpAllocator<'scope> {
4952    ///     pub fn new(memory: &'scope mut [MaybeUninit<u8>]) -> Self {
4953    ///         Self { memory }
4954    ///     }
4955    ///     pub fn try_alloc_uninit<T>(&mut self) -> Option<&'scope mut MaybeUninit<T>> {
4956    ///         let first_end = self.memory.as_ptr().align_offset(align_of::<T>()) + size_of::<T>();
4957    ///         let prefix = self.memory.split_off_mut(..first_end)?;
4958    ///         Some(&mut prefix.align_to_uninit_mut::<T>().1[0])
4959    ///     }
4960    ///     pub fn try_alloc_u32(&mut self, value: u32) -> Option<&'scope mut u32> {
4961    ///         let uninit = self.try_alloc_uninit()?;
4962    ///         Some(uninit.write(value))
4963    ///     }
4964    /// }
4965    ///
4966    /// let mut memory = [MaybeUninit::<u8>::uninit(); 10];
4967    /// let mut allocator = BumpAllocator::new(&mut memory);
4968    /// let v = allocator.try_alloc_u32(42);
4969    /// assert_eq!(v, Some(&mut 42));
4970    /// ```
4971    #[unstable(feature = "align_to_uninit_mut", issue = "139062")]
4972    #[inline]
4973    #[must_use]
4974    pub fn align_to_uninit_mut<U>(&mut self) -> (&mut Self, &mut [MaybeUninit<U>], &mut Self) {
4975        // SAFETY: `MaybeUninit` is transparent. Correct size and alignment are guaranteed by
4976        // `align_to_mut` itself. Therefore the only thing that we have to ensure for a safe
4977        // `transmute` is that the values are valid for the types involved. But for `MaybeUninit`
4978        // any values are valid, so this operation is safe.
4979        unsafe { self.align_to_mut() }
4980    }
4981}
4982
4983impl<T, const N: usize> [[T; N]] {
4984    /// Takes a `&[[T; N]]`, and flattens it to a `&[T]`.
4985    ///
4986    /// For the opposite operation, see [`as_chunks`] and [`as_rchunks`].
4987    ///
4988    /// [`as_chunks`]: slice::as_chunks
4989    /// [`as_rchunks`]: slice::as_rchunks
4990    ///
4991    /// # Panics
4992    ///
4993    /// This panics if the length of the resulting slice would overflow a `usize`.
4994    ///
4995    /// This is only possible when flattening a slice of arrays of zero-sized
4996    /// types, and thus tends to be irrelevant in practice. If
4997    /// `size_of::<T>() > 0`, this will never panic.
4998    ///
4999    /// # Examples
5000    ///
5001    /// ```
5002    /// assert_eq!([[1, 2, 3], [4, 5, 6]].as_flattened(), &[1, 2, 3, 4, 5, 6]);
5003    ///
5004    /// assert_eq!(
5005    ///     [[1, 2, 3], [4, 5, 6]].as_flattened(),
5006    ///     [[1, 2], [3, 4], [5, 6]].as_flattened(),
5007    /// );
5008    ///
5009    /// let slice_of_empty_arrays: &[[i32; 0]] = &[[], [], [], [], []];
5010    /// assert!(slice_of_empty_arrays.as_flattened().is_empty());
5011    ///
5012    /// let empty_slice_of_arrays: &[[u32; 10]] = &[];
5013    /// assert!(empty_slice_of_arrays.as_flattened().is_empty());
5014    /// ```
5015    #[stable(feature = "slice_flatten", since = "1.80.0")]
5016    #[rustc_const_stable(feature = "const_slice_flatten", since = "1.87.0")]
5017    pub const fn as_flattened(&self) -> &[T] {
5018        let len = if T::IS_ZST {
5019            self.len().checked_mul(N).expect("slice len overflow")
5020        } else {
5021            // SAFETY: `self.len() * N` cannot overflow because `self` is
5022            // already in the address space.
5023            unsafe { self.len().unchecked_mul(N) }
5024        };
5025        // SAFETY: `[T]` is layout-identical to `[T; N]`
5026        unsafe { from_raw_parts(self.as_ptr().cast(), len) }
5027    }
5028
5029    /// Takes a `&mut [[T; N]]`, and flattens it to a `&mut [T]`.
5030    ///
5031    /// For the opposite operation, see [`as_chunks_mut`] and [`as_rchunks_mut`].
5032    ///
5033    /// [`as_chunks_mut`]: slice::as_chunks_mut
5034    /// [`as_rchunks_mut`]: slice::as_rchunks_mut
5035    ///
5036    /// # Panics
5037    ///
5038    /// This panics if the length of the resulting slice would overflow a `usize`.
5039    ///
5040    /// This is only possible when flattening a slice of arrays of zero-sized
5041    /// types, and thus tends to be irrelevant in practice. If
5042    /// `size_of::<T>() > 0`, this will never panic.
5043    ///
5044    /// # Examples
5045    ///
5046    /// ```
5047    /// fn add_5_to_all(slice: &mut [i32]) {
5048    ///     for i in slice {
5049    ///         *i += 5;
5050    ///     }
5051    /// }
5052    ///
5053    /// let mut array = [[1, 2, 3], [4, 5, 6], [7, 8, 9]];
5054    /// add_5_to_all(array.as_flattened_mut());
5055    /// assert_eq!(array, [[6, 7, 8], [9, 10, 11], [12, 13, 14]]);
5056    /// ```
5057    #[stable(feature = "slice_flatten", since = "1.80.0")]
5058    #[rustc_const_stable(feature = "const_slice_flatten", since = "1.87.0")]
5059    pub const fn as_flattened_mut(&mut self) -> &mut [T] {
5060        let len = if T::IS_ZST {
5061            self.len().checked_mul(N).expect("slice len overflow")
5062        } else {
5063            // SAFETY: `self.len() * N` cannot overflow because `self` is
5064            // already in the address space.
5065            unsafe { self.len().unchecked_mul(N) }
5066        };
5067        // SAFETY: `[T]` is layout-identical to `[T; N]`
5068        unsafe { from_raw_parts_mut(self.as_mut_ptr().cast(), len) }
5069    }
5070}
5071
5072impl [f32] {
5073    /// Sorts the slice of floats.
5074    ///
5075    /// This sort is in-place (i.e. does not allocate), *O*(*n* \* log(*n*)) worst-case, and uses
5076    /// the ordering defined by [`f32::total_cmp`].
5077    ///
5078    /// # Current implementation
5079    ///
5080    /// This uses the same sorting algorithm as [`sort_unstable_by`](slice::sort_unstable_by).
5081    ///
5082    /// # Examples
5083    ///
5084    /// ```
5085    /// #![feature(sort_floats)]
5086    /// let mut v = [2.6, -5e-8, f32::NAN, 8.29, f32::INFINITY, -1.0, 0.0, -f32::INFINITY, -0.0];
5087    ///
5088    /// v.sort_floats();
5089    /// let sorted = [-f32::INFINITY, -1.0, -5e-8, -0.0, 0.0, 2.6, 8.29, f32::INFINITY, f32::NAN];
5090    /// assert_eq!(&v[..8], &sorted[..8]);
5091    /// assert!(v[8].is_nan());
5092    /// ```
5093    #[unstable(feature = "sort_floats", issue = "93396")]
5094    #[inline]
5095    pub fn sort_floats(&mut self) {
5096        self.sort_unstable_by(f32::total_cmp);
5097    }
5098}
5099
5100impl [f64] {
5101    /// Sorts the slice of floats.
5102    ///
5103    /// This sort is in-place (i.e. does not allocate), *O*(*n* \* log(*n*)) worst-case, and uses
5104    /// the ordering defined by [`f64::total_cmp`].
5105    ///
5106    /// # Current implementation
5107    ///
5108    /// This uses the same sorting algorithm as [`sort_unstable_by`](slice::sort_unstable_by).
5109    ///
5110    /// # Examples
5111    ///
5112    /// ```
5113    /// #![feature(sort_floats)]
5114    /// let mut v = [2.6, -5e-8, f64::NAN, 8.29, f64::INFINITY, -1.0, 0.0, -f64::INFINITY, -0.0];
5115    ///
5116    /// v.sort_floats();
5117    /// let sorted = [-f64::INFINITY, -1.0, -5e-8, -0.0, 0.0, 2.6, 8.29, f64::INFINITY, f64::NAN];
5118    /// assert_eq!(&v[..8], &sorted[..8]);
5119    /// assert!(v[8].is_nan());
5120    /// ```
5121    #[unstable(feature = "sort_floats", issue = "93396")]
5122    #[inline]
5123    pub fn sort_floats(&mut self) {
5124        self.sort_unstable_by(f64::total_cmp);
5125    }
5126}
5127
5128trait CloneFromSpec<T> {
5129    fn spec_clone_from(&mut self, src: &[T]);
5130}
5131
5132impl<T> CloneFromSpec<T> for [T]
5133where
5134    T: Clone,
5135{
5136    #[track_caller]
5137    default fn spec_clone_from(&mut self, src: &[T]) {
5138        assert!(self.len() == src.len(), "destination and source slices have different lengths");
5139        // NOTE: We need to explicitly slice them to the same length
5140        // to make it easier for the optimizer to elide bounds checking.
5141        // But since it can't be relied on we also have an explicit specialization for T: Copy.
5142        let len = self.len();
5143        let src = &src[..len];
5144        for i in 0..len {
5145            self[i].clone_from(&src[i]);
5146        }
5147    }
5148}
5149
5150impl<T> CloneFromSpec<T> for [T]
5151where
5152    T: Copy,
5153{
5154    #[track_caller]
5155    fn spec_clone_from(&mut self, src: &[T]) {
5156        self.copy_from_slice(src);
5157    }
5158}
5159
5160#[stable(feature = "rust1", since = "1.0.0")]
5161impl<T> Default for &[T] {
5162    /// Creates an empty slice.
5163    fn default() -> Self {
5164        &[]
5165    }
5166}
5167
5168#[stable(feature = "mut_slice_default", since = "1.5.0")]
5169impl<T> Default for &mut [T] {
5170    /// Creates a mutable empty slice.
5171    fn default() -> Self {
5172        &mut []
5173    }
5174}
5175
5176#[unstable(feature = "slice_pattern", reason = "stopgap trait for slice patterns", issue = "56345")]
5177/// Patterns in slices - currently, only used by `strip_prefix` and `strip_suffix`.  At a future
5178/// point, we hope to generalise `core::str::Pattern` (which at the time of writing is limited to
5179/// `str`) to slices, and then this trait will be replaced or abolished.
5180pub trait SlicePattern {
5181    /// The element type of the slice being matched on.
5182    type Item;
5183
5184    /// Currently, the consumers of `SlicePattern` need a slice.
5185    fn as_slice(&self) -> &[Self::Item];
5186}
5187
5188#[stable(feature = "slice_strip", since = "1.51.0")]
5189impl<T> SlicePattern for [T] {
5190    type Item = T;
5191
5192    #[inline]
5193    fn as_slice(&self) -> &[Self::Item] {
5194        self
5195    }
5196}
5197
5198#[stable(feature = "slice_strip", since = "1.51.0")]
5199impl<T, const N: usize> SlicePattern for [T; N] {
5200    type Item = T;
5201
5202    #[inline]
5203    fn as_slice(&self) -> &[Self::Item] {
5204        self
5205    }
5206}
5207
5208/// This checks every index against each other, and against `len`.
5209///
5210/// This will do `binomial(N + 1, 2) = N * (N + 1) / 2 = 0, 1, 3, 6, 10, ..`
5211/// comparison operations.
5212#[inline]
5213fn get_disjoint_check_valid<I: GetDisjointMutIndex, const N: usize>(
5214    indices: &[I; N],
5215    len: usize,
5216) -> Result<(), GetDisjointMutError> {
5217    // NB: The optimizer should inline the loops into a sequence
5218    // of instructions without additional branching.
5219    for (i, idx) in indices.iter().enumerate() {
5220        if !idx.is_in_bounds(len) {
5221            return Err(GetDisjointMutError::IndexOutOfBounds);
5222        }
5223        for idx2 in &indices[..i] {
5224            if idx.is_overlapping(idx2) {
5225                return Err(GetDisjointMutError::OverlappingIndices);
5226            }
5227        }
5228    }
5229    Ok(())
5230}
5231
5232/// The error type returned by [`get_disjoint_mut`][`slice::get_disjoint_mut`].
5233///
5234/// It indicates one of two possible errors:
5235/// - An index is out-of-bounds.
5236/// - The same index appeared multiple times in the array
5237///   (or different but overlapping indices when ranges are provided).
5238///
5239/// # Examples
5240///
5241/// ```
5242/// use std::slice::GetDisjointMutError;
5243///
5244/// let v = &mut [1, 2, 3];
5245/// assert_eq!(v.get_disjoint_mut([0, 999]), Err(GetDisjointMutError::IndexOutOfBounds));
5246/// assert_eq!(v.get_disjoint_mut([1, 1]), Err(GetDisjointMutError::OverlappingIndices));
5247/// ```
5248#[stable(feature = "get_many_mut", since = "1.86.0")]
5249#[derive(Debug, Clone, PartialEq, Eq)]
5250pub enum GetDisjointMutError {
5251    /// An index provided was out-of-bounds for the slice.
5252    IndexOutOfBounds,
5253    /// Two indices provided were overlapping.
5254    OverlappingIndices,
5255}
5256
5257#[stable(feature = "get_many_mut", since = "1.86.0")]
5258impl fmt::Display for GetDisjointMutError {
5259    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
5260        let msg = match self {
5261            GetDisjointMutError::IndexOutOfBounds => "an index is out of bounds",
5262            GetDisjointMutError::OverlappingIndices => "there were overlapping indices",
5263        };
5264        fmt::Display::fmt(msg, f)
5265    }
5266}
5267
5268mod private_get_disjoint_mut_index {
5269    use super::{Range, RangeInclusive, range};
5270
5271    #[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5272    pub trait Sealed {}
5273
5274    #[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5275    impl Sealed for usize {}
5276    #[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5277    impl Sealed for Range<usize> {}
5278    #[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5279    impl Sealed for RangeInclusive<usize> {}
5280    #[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5281    impl Sealed for range::Range<usize> {}
5282    #[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5283    impl Sealed for range::RangeInclusive<usize> {}
5284}
5285
5286/// A helper trait for `<[T]>::get_disjoint_mut()`.
5287///
5288/// # Safety
5289///
5290/// If `is_in_bounds()` returns `true` and `is_overlapping()` returns `false`,
5291/// it must be safe to index the slice with the indices.
5292#[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5293pub unsafe trait GetDisjointMutIndex:
5294    Clone + private_get_disjoint_mut_index::Sealed
5295{
5296    /// Returns `true` if `self` is in bounds for `len` slice elements.
5297    #[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5298    fn is_in_bounds(&self, len: usize) -> bool;
5299
5300    /// Returns `true` if `self` overlaps with `other`.
5301    ///
5302    /// Note that we don't consider zero-length ranges to overlap at the beginning or the end,
5303    /// but do consider them to overlap in the middle.
5304    #[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5305    fn is_overlapping(&self, other: &Self) -> bool;
5306}
5307
5308#[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5309// SAFETY: We implement `is_in_bounds()` and `is_overlapping()` correctly.
5310unsafe impl GetDisjointMutIndex for usize {
5311    #[inline]
5312    fn is_in_bounds(&self, len: usize) -> bool {
5313        *self < len
5314    }
5315
5316    #[inline]
5317    fn is_overlapping(&self, other: &Self) -> bool {
5318        *self == *other
5319    }
5320}
5321
5322#[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5323// SAFETY: We implement `is_in_bounds()` and `is_overlapping()` correctly.
5324unsafe impl GetDisjointMutIndex for Range<usize> {
5325    #[inline]
5326    fn is_in_bounds(&self, len: usize) -> bool {
5327        (self.start <= self.end) & (self.end <= len)
5328    }
5329
5330    #[inline]
5331    fn is_overlapping(&self, other: &Self) -> bool {
5332        (self.start < other.end) & (other.start < self.end)
5333    }
5334}
5335
5336#[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5337// SAFETY: We implement `is_in_bounds()` and `is_overlapping()` correctly.
5338unsafe impl GetDisjointMutIndex for RangeInclusive<usize> {
5339    #[inline]
5340    fn is_in_bounds(&self, len: usize) -> bool {
5341        (self.start <= self.end) & (self.end < len)
5342    }
5343
5344    #[inline]
5345    fn is_overlapping(&self, other: &Self) -> bool {
5346        (self.start <= other.end) & (other.start <= self.end)
5347    }
5348}
5349
5350#[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5351// SAFETY: We implement `is_in_bounds()` and `is_overlapping()` correctly.
5352unsafe impl GetDisjointMutIndex for range::Range<usize> {
5353    #[inline]
5354    fn is_in_bounds(&self, len: usize) -> bool {
5355        Range::from(*self).is_in_bounds(len)
5356    }
5357
5358    #[inline]
5359    fn is_overlapping(&self, other: &Self) -> bool {
5360        Range::from(*self).is_overlapping(&Range::from(*other))
5361    }
5362}
5363
5364#[unstable(feature = "get_disjoint_mut_helpers", issue = "none")]
5365// SAFETY: We implement `is_in_bounds()` and `is_overlapping()` correctly.
5366unsafe impl GetDisjointMutIndex for range::RangeInclusive<usize> {
5367    #[inline]
5368    fn is_in_bounds(&self, len: usize) -> bool {
5369        RangeInclusive::from(*self).is_in_bounds(len)
5370    }
5371
5372    #[inline]
5373    fn is_overlapping(&self, other: &Self) -> bool {
5374        RangeInclusive::from(*self).is_overlapping(&RangeInclusive::from(*other))
5375    }
5376}