iter.rs - source
Description: Source of the Rust file `library/core/src/slice/iter.rs`.

#
core/slice/
iter.rs

    1//! Definitions of a bunch of iterators for `[T]`.
    2
    3#[macro_use] // import iterator! and forward_iterator!
    4mod macros;
    5
    6use super::{from_raw_parts, from_raw_parts_mut};
    7use crate::hint::assert_unchecked;
    8use crate::iter::{
    9    FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce, UncheckedIterator,
    10};
    11use crate::marker::PhantomData;
    12use crate::mem::{self, SizedTypeProperties};
    13use crate::num::NonZero;
    14use crate::ptr::{NonNull, without_provenance, without_provenance_mut};
    15use crate::{cmp, fmt};
    16
    17#[stable(feature = "boxed_slice_into_iter", since = "1.80.0")]
    18impl<T> !Iterator for [T] {}
    19
    20#[stable(feature = "rust1", since = "1.0.0")]
    21impl<'a, T> IntoIterator for &'a [T] {
    22    type Item = &'a T;
    23    type IntoIter = Iter<'a, T>;
    24
    25    fn into_iter(self) -> Iter<'a, T> {
    26        self.iter()
    27    }
    28}
    29
    30#[stable(feature = "rust1", since = "1.0.0")]
    31impl<'a, T> IntoIterator for &'a mut [T] {
    32    type Item = &'a mut T;
    33    type IntoIter = IterMut<'a, T>;
    34
    35    fn into_iter(self) -> IterMut<'a, T> {
    36        self.iter_mut()
    37    }
    38}
    39
    40/// Immutable slice iterator
    41///
    42/// This struct is created by the [`iter`] method on [slices].
    43///
    44/// # Examples
    45///
    46/// Basic usage:
    47///
    48/// ```
    49/// // First, we need a slice to call the `iter` method on:
    50/// let slice = &[1, 2, 3];
    51///
    52/// // Then we call `iter` on the slice to get the `Iter` iterator,
    53/// // and iterate over it:
    54/// for element in slice.iter() {
    55///     println!("{element}");
    56/// }
    57///
    58/// // This for loop actually already works without calling `iter`:
    59/// for element in slice {
    60///     println!("{element}");
    61/// }
    62/// ```
    63///
    64/// [`iter`]: slice::iter
    65/// [slices]: slice
    66#[stable(feature = "rust1", since = "1.0.0")]
    67#[must_use = "iterators are lazy and do nothing unless consumed"]
    68#[rustc_diagnostic_item = "SliceIter"]
    69pub struct Iter<'a, T: 'a> {
    70    /// The pointer to the next element to return, or the past-the-end location
    71    /// if the iterator is empty.
    72    ///
    73    /// This address will be used for all ZST elements, never changed.
    74    ptr: NonNull<T>,
    75    /// For non-ZSTs, the non-null pointer to the past-the-end element.
    76    ///
    77    /// For ZSTs, this is `ptr::without_provenance_mut(len)`.
    78    end_or_len: *const T,
    79    _marker: PhantomData<&'a T>,
    80}
    81
    82#[stable(feature = "core_impl_debug", since = "1.9.0")]
    83impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
    84    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    85        f.debug_tuple("Iter").field(&self.as_slice()).finish()
    86    }
    87}
    88
    89#[stable(feature = "rust1", since = "1.0.0")]
    90unsafe impl<T: Sync> Sync for Iter<'_, T> {}
    91#[stable(feature = "rust1", since = "1.0.0")]
    92unsafe impl<T: Sync> Send for Iter<'_, T> {}
    93
    94impl<'a, T> Iter<'a, T> {
    95    #[inline]
    96    pub(super) const fn new(slice: &'a [T]) -> Self {
    97        let len = slice.len();
    98        let ptr: NonNull<T> = NonNull::from_ref(slice).cast();
    99        // SAFETY: Similar to `IterMut::new`.
    100        unsafe {
    101            let end_or_len =
    102                if T::IS_ZST { without_provenance(len) } else { ptr.as_ptr().add(len) };
    103
    104            Self { ptr, end_or_len, _marker: PhantomData }
    105        }
    106    }
    107
    108    /// Views the underlying data as a subslice of the original data.
    109    ///
    110    /// # Examples
    111    ///
    112    /// Basic usage:
    113    ///
    114    /// ```
    115    /// // First, we need a slice to call the `iter` method on:
    116    /// let slice = &[1, 2, 3];
    117    ///
    118    /// // Then we call `iter` on the slice to get the `Iter` iterator:
    119    /// let mut iter = slice.iter();
    120    /// // Here `as_slice` still returns the whole slice, so this prints "[1, 2, 3]":
    121    /// println!("{:?}", iter.as_slice());
    122    ///
    123    /// // Now, we call the `next` method to remove the first element from the iterator:
    124    /// iter.next();
    125    /// // Here the iterator does not contain the first element of the slice any more,
    126    /// // so `as_slice` only returns the last two elements of the slice,
    127    /// // and so this prints "[2, 3]":
    128    /// println!("{:?}", iter.as_slice());
    129    ///
    130    /// // The underlying slice has not been modified and still contains three elements,
    131    /// // so this prints "[1, 2, 3]":
    132    /// println!("{:?}", slice);
    133    /// ```
    134    #[must_use]
    135    #[stable(feature = "iter_to_slice", since = "1.4.0")]
    136    #[inline]
    137    pub fn as_slice(&self) -> &'a [T] {
    138        self.make_slice()
    139    }
    140}
    141
    142iterator! {struct Iter -> *const T, &'a T, const, {/* no mut */}, as_ref, each_ref, {
    143    fn is_sorted_by<F>(self, mut compare: F) -> bool
    144    where
    145        Self: Sized,
    146        F: FnMut(&Self::Item, &Self::Item) -> bool,
    147    {
    148        self.as_slice().is_sorted_by(|a, b| compare(&a, &b))
    149    }
    150}}
    151
    152#[stable(feature = "rust1", since = "1.0.0")]
    153impl<T> Clone for Iter<'_, T> {
    154    #[inline]
    155    fn clone(&self) -> Self {
    156        Iter { ptr: self.ptr, end_or_len: self.end_or_len, _marker: self._marker }
    157    }
    158}
    159
    160#[stable(feature = "slice_iter_as_ref", since = "1.13.0")]
    161impl<T> AsRef<[T]> for Iter<'_, T> {
    162    #[inline]
    163    fn as_ref(&self) -> &[T] {
    164        self.as_slice()
    165    }
    166}
    167
    168/// Mutable slice iterator.
    169///
    170/// This struct is created by the [`iter_mut`] method on [slices].
    171///
    172/// # Examples
    173///
    174/// Basic usage:
    175///
    176/// ```
    177/// // First, we need a slice to call the `iter_mut` method on:
    178/// let slice = &mut [1, 2, 3];
    179///
    180/// // Then we call `iter_mut` on the slice to get the `IterMut` iterator,
    181/// // iterate over it and increment each element value:
    182/// for element in slice.iter_mut() {
    183///     *element += 1;
    184/// }
    185///
    186/// // We now have "[2, 3, 4]":
    187/// println!("{slice:?}");
    188/// ```
    189///
    190/// [`iter_mut`]: slice::iter_mut
    191/// [slices]: slice
    192#[stable(feature = "rust1", since = "1.0.0")]
    193#[must_use = "iterators are lazy and do nothing unless consumed"]
    194pub struct IterMut<'a, T: 'a> {
    195    /// The pointer to the next element to return, or the past-the-end location
    196    /// if the iterator is empty.
    197    ///
    198    /// This address will be used for all ZST elements, never changed.
    199    ptr: NonNull<T>,
    200    /// For non-ZSTs, the non-null pointer to the past-the-end element.
    201    ///
    202    /// For ZSTs, this is `ptr::without_provenance_mut(len)`.
    203    end_or_len: *mut T,
    204    _marker: PhantomData<&'a mut T>,
    205}
    206
    207#[stable(feature = "core_impl_debug", since = "1.9.0")]
    208impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
    209    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    210        f.debug_tuple("IterMut").field(&self.make_slice()).finish()
    211    }
    212}
    213
    214#[stable(feature = "rust1", since = "1.0.0")]
    215unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
    216#[stable(feature = "rust1", since = "1.0.0")]
    217unsafe impl<T: Send> Send for IterMut<'_, T> {}
    218
    219impl<'a, T> IterMut<'a, T> {
    220    #[inline]
    221    pub(super) const fn new(slice: &'a mut [T]) -> Self {
    222        let len = slice.len();
    223        let ptr: NonNull<T> = NonNull::from_mut(slice).cast();
    224        // SAFETY: There are several things here:
    225        //
    226        // `ptr` has been obtained by `slice.as_ptr()` where `slice` is a valid
    227        // reference thus it is non-NUL and safe to use and pass to
    228        // `NonNull::new_unchecked` .
    229        //
    230        // Adding `slice.len()` to the starting pointer gives a pointer
    231        // at the end of `slice`. `end` will never be dereferenced, only checked
    232        // for direct pointer equality with `ptr` to check if the iterator is
    233        // done.
    234        //
    235        // In the case of a ZST, the end pointer is just the length.  It's never
    236        // used as a pointer at all, and thus it's fine to have no provenance.
    237        //
    238        // See the `next_unchecked!` and `is_empty!` macros as well as the
    239        // `post_inc_start` method for more information.
    240        unsafe {
    241            let end_or_len =
    242                if T::IS_ZST { without_provenance_mut(len) } else { ptr.as_ptr().add(len) };
    243
    244            Self { ptr, end_or_len, _marker: PhantomData }
    245        }
    246    }
    247
    248    /// Views the underlying data as a subslice of the original data.
    249    ///
    250    /// To avoid creating `&mut` references that alias, this is forced
    251    /// to consume the iterator.
    252    ///
    253    /// # Examples
    254    ///
    255    /// Basic usage:
    256    ///
    257    /// ```
    258    /// // First, we need a slice to call the `iter_mut` method on:
    259    /// let mut slice = &mut [1, 2, 3];
    260    ///
    261    /// // Then we call `iter_mut` on the slice to get the `IterMut` struct:
    262    /// let mut iter = slice.iter_mut();
    263    /// // Now, we call the `next` method to remove the first element of the iterator,
    264    /// // unwrap and dereference what we get from `next` and increase its value by 1:
    265    /// *iter.next().unwrap() += 1;
    266    /// // Here the iterator does not contain the first element of the slice any more,
    267    /// // so `into_slice` only returns the last two elements of the slice,
    268    /// // and so this prints "[2, 3]":
    269    /// println!("{:?}", iter.into_slice());
    270    /// // The underlying slice still contains three elements, but its first element
    271    /// // was increased by 1, so this prints "[2, 2, 3]":
    272    /// println!("{:?}", slice);
    273    /// ```
    274    #[must_use = "`self` will be dropped if the result is not used"]
    275    #[stable(feature = "iter_to_slice", since = "1.4.0")]
    276    pub fn into_slice(self) -> &'a mut [T] {
    277        // SAFETY: the iterator was created from a mutable slice with pointer
    278        // `self.ptr` and length `len!(self)`. This guarantees that all the prerequisites
    279        // for `from_raw_parts_mut` are fulfilled.
    280        unsafe { from_raw_parts_mut(self.ptr.as_ptr(), len!(self)) }
    281    }
    282
    283    /// Views the underlying data as a subslice of the original data.
    284    ///
    285    /// # Examples
    286    ///
    287    /// Basic usage:
    288    ///
    289    /// ```
    290    /// // First, we need a slice to call the `iter_mut` method on:
    291    /// let slice = &mut [1, 2, 3];
    292    ///
    293    /// // Then we call `iter_mut` on the slice to get the `IterMut` iterator:
    294    /// let mut iter = slice.iter_mut();
    295    /// // Here `as_slice` still returns the whole slice, so this prints "[1, 2, 3]":
    296    /// println!("{:?}", iter.as_slice());
    297    ///
    298    /// // Now, we call the `next` method to remove the first element from the iterator
    299    /// // and increment its value:
    300    /// *iter.next().unwrap() += 1;
    301    /// // Here the iterator does not contain the first element of the slice any more,
    302    /// // so `as_slice` only returns the last two elements of the slice,
    303    /// // and so this prints "[2, 3]":
    304    /// println!("{:?}", iter.as_slice());
    305    ///
    306    /// // The underlying slice still contains three elements, but its first element
    307    /// // was increased by 1, so this prints "[2, 2, 3]":
    308    /// println!("{:?}", slice);
    309    /// ```
    310    #[must_use]
    311    #[stable(feature = "slice_iter_mut_as_slice", since = "1.53.0")]
    312    #[inline]
    313    pub fn as_slice(&self) -> &[T] {
    314        self.make_slice()
    315    }
    316
    317    /// Views the underlying data as a mutable subslice of the original data.
    318    ///
    319    /// # Examples
    320    ///
    321    /// Basic usage:
    322    ///
    323    /// ```
    324    /// #![feature(slice_iter_mut_as_mut_slice)]
    325    ///
    326    /// let mut slice: &mut [usize] = &mut [1, 2, 3];
    327    ///
    328    /// // First, we get the iterator:
    329    /// let mut iter = slice.iter_mut();
    330    /// // Then, we get a mutable slice from it:
    331    /// let mut_slice = iter.as_mut_slice();
    332    /// // So if we check what the `as_mut_slice` method returned, we have "[1, 2, 3]":
    333    /// assert_eq!(mut_slice, &mut [1, 2, 3]);
    334    ///
    335    /// // We can use it to mutate the slice:
    336    /// mut_slice[0] = 4;
    337    /// mut_slice[2] = 5;
    338    ///
    339    /// // Next, we can move to the second element of the slice, checking that
    340    /// // it yields the value we just wrote:
    341    /// assert_eq!(iter.next(), Some(&mut 4));
    342    /// // Now `as_mut_slice` returns "[2, 5]":
    343    /// assert_eq!(iter.as_mut_slice(), &mut [2, 5]);
    344    /// ```
    345    #[must_use]
    346    // FIXME: Uncomment the `AsMut<[T]>` impl when this gets stabilized.
    347    #[unstable(feature = "slice_iter_mut_as_mut_slice", issue = "93079")]
    348    pub fn as_mut_slice(&mut self) -> &mut [T] {
    349        // SAFETY: the iterator was created from a mutable slice with pointer
    350        // `self.ptr` and length `len!(self)`. This guarantees that all the prerequisites
    351        // for `from_raw_parts_mut` are fulfilled.
    352        unsafe { from_raw_parts_mut(self.ptr.as_ptr(), len!(self)) }
    353    }
    354}
    355
    356#[stable(feature = "slice_iter_mut_as_slice", since = "1.53.0")]
    357impl<T> AsRef<[T]> for IterMut<'_, T> {
    358    #[inline]
    359    fn as_ref(&self) -> &[T] {
    360        self.as_slice()
    361    }
    362}
    363
    364// #[stable(feature = "slice_iter_mut_as_mut_slice", since = "FIXME")]
    365// impl<T> AsMut<[T]> for IterMut<'_, T> {
    366//     fn as_mut(&mut self) -> &mut [T] {
    367//         self.as_mut_slice()
    368//     }
    369// }
    370
    371iterator! {struct IterMut -> *mut T, &'a mut T, mut, {mut}, as_mut, each_mut, {}}
    372
    373/// An internal abstraction over the splitting iterators, so that
    374/// splitn, splitn_mut etc can be implemented once.
    375#[doc(hidden)]
    376pub(super) trait SplitIter: DoubleEndedIterator {
    377    /// Marks the underlying iterator as complete, extracting the remaining
    378    /// portion of the slice.
    379    fn finish(&mut self) -> Option<Self::Item>;
    380}
    381
    382/// An iterator over subslices separated by elements that match a predicate
    383/// function.
    384///
    385/// This struct is created by the [`split`] method on [slices].
    386///
    387/// # Example
    388///
    389/// ```
    390/// let slice = [10, 40, 33, 20];
    391/// let mut iter = slice.split(|num| num % 3 == 0);
    392/// assert_eq!(iter.next(), Some(&[10, 40][..]));
    393/// assert_eq!(iter.next(), Some(&[20][..]));
    394/// assert_eq!(iter.next(), None);
    395/// ```
    396///
    397/// [`split`]: slice::split
    398/// [slices]: slice
    399#[stable(feature = "rust1", since = "1.0.0")]
    400#[must_use = "iterators are lazy and do nothing unless consumed"]
    401pub struct Split<'a, T: 'a, P>
    402where
    403    P: FnMut(&T) -> bool,
    404{
    405    // Used for `SplitWhitespace` and `SplitAsciiWhitespace` `as_str` methods
    406    pub(crate) v: &'a [T],
    407    pred: P,
    408    // Used for `SplitAsciiWhitespace` `as_str` method
    409    pub(crate) finished: bool,
    410}
    411
    412impl<'a, T: 'a, P: FnMut(&T) -> bool> Split<'a, T, P> {
    413    #[inline]
    414    pub(super) fn new(slice: &'a [T], pred: P) -> Self {
    415        Self { v: slice, pred, finished: false }
    416    }
    417    /// Returns a slice which contains items not yet handled by split.
    418    /// # Example
    419    ///
    420    /// ```
    421    /// #![feature(split_as_slice)]
    422    /// let slice = [1,2,3,4,5];
    423    /// let mut split = slice.split(|v| v % 2 == 0);
    424    /// assert!(split.next().is_some());
    425    /// assert_eq!(split.as_slice(), &[3,4,5]);
    426    /// ```
    427    #[unstable(feature = "split_as_slice", issue = "96137")]
    428    pub fn as_slice(&self) -> &'a [T] {
    429        if self.finished { &[] } else { &self.v }
    430    }
    431}
    432
    433#[stable(feature = "core_impl_debug", since = "1.9.0")]
    434impl<T: fmt::Debug, P> fmt::Debug for Split<'_, T, P>
    435where
    436    P: FnMut(&T) -> bool,
    437{
    438    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    439        f.debug_struct("Split").field("v", &self.v).field("finished", &self.finished).finish()
    440    }
    441}
    442
    443// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
    444#[stable(feature = "rust1", since = "1.0.0")]
    445impl<T, P> Clone for Split<'_, T, P>
    446where
    447    P: Clone + FnMut(&T) -> bool,
    448{
    449    fn clone(&self) -> Self {
    450        Split { v: self.v, pred: self.pred.clone(), finished: self.finished }
    451    }
    452}
    453
    454#[stable(feature = "rust1", since = "1.0.0")]
    455impl<'a, T, P> Iterator for Split<'a, T, P>
    456where
    457    P: FnMut(&T) -> bool,
    458{
    459    type Item = &'a [T];
    460
    461    #[inline]
    462    fn next(&mut self) -> Option<&'a [T]> {
    463        if self.finished {
    464            return None;
    465        }
    466
    467        match self.v.iter().position(|x| (self.pred)(x)) {
    468            None => self.finish(),
    469            Some(idx) => {
    470                let (left, right) =
    471                    // SAFETY: if v.iter().position returns Some(idx), that
    472                    // idx is definitely a valid index for v
    473                    unsafe { (self.v.get_unchecked(..idx), self.v.get_unchecked(idx + 1..)) };
    474                let ret = Some(left);
    475                self.v = right;
    476                ret
    477            }
    478        }
    479    }
    480
    481    #[inline]
    482    fn size_hint(&self) -> (usize, Option<usize>) {
    483        if self.finished {
    484            (0, Some(0))
    485        } else {
    486            // If the predicate doesn't match anything, we yield one slice.
    487            // If it matches every element, we yield `len() + 1` empty slices.
    488            (1, Some(self.v.len() + 1))
    489        }
    490    }
    491}
    492
    493#[stable(feature = "rust1", since = "1.0.0")]
    494impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P>
    495where
    496    P: FnMut(&T) -> bool,
    497{
    498    #[inline]
    499    fn next_back(&mut self) -> Option<&'a [T]> {
    500        if self.finished {
    501            return None;
    502        }
    503
    504        match self.v.iter().rposition(|x| (self.pred)(x)) {
    505            None => self.finish(),
    506            Some(idx) => {
    507                let (left, right) =
    508                    // SAFETY: if v.iter().rposition returns Some(idx), then
    509                    // idx is definitely a valid index for v
    510                    unsafe { (self.v.get_unchecked(..idx), self.v.get_unchecked(idx + 1..)) };
    511                let ret = Some(right);
    512                self.v = left;
    513                ret
    514            }
    515        }
    516    }
    517}
    518
    519impl<'a, T, P> SplitIter for Split<'a, T, P>
    520where
    521    P: FnMut(&T) -> bool,
    522{
    523    #[inline]
    524    fn finish(&mut self) -> Option<&'a [T]> {
    525        if self.finished {
    526            None
    527        } else {
    528            self.finished = true;
    529            Some(self.v)
    530        }
    531    }
    532}
    533
    534#[stable(feature = "fused", since = "1.26.0")]
    535impl<T, P> FusedIterator for Split<'_, T, P> where P: FnMut(&T) -> bool {}
    536
    537/// An iterator over subslices separated by elements that match a predicate
    538/// function. Unlike `Split`, it contains the matched part as a terminator
    539/// of the subslice.
    540///
    541/// This struct is created by the [`split_inclusive`] method on [slices].
    542///
    543/// # Example
    544///
    545/// ```
    546/// let slice = [10, 40, 33, 20];
    547/// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
    548/// assert_eq!(iter.next(), Some(&[10, 40, 33][..]));
    549/// assert_eq!(iter.next(), Some(&[20][..]));
    550/// assert_eq!(iter.next(), None);
    551/// ```
    552///
    553/// [`split_inclusive`]: slice::split_inclusive
    554/// [slices]: slice
    555#[stable(feature = "split_inclusive", since = "1.51.0")]
    556#[must_use = "iterators are lazy and do nothing unless consumed"]
    557pub struct SplitInclusive<'a, T: 'a, P>
    558where
    559    P: FnMut(&T) -> bool,
    560{
    561    v: &'a [T],
    562    pred: P,
    563    finished: bool,
    564}
    565
    566impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitInclusive<'a, T, P> {
    567    #[inline]
    568    pub(super) fn new(slice: &'a [T], pred: P) -> Self {
    569        let finished = slice.is_empty();
    570        Self { v: slice, pred, finished }
    571    }
    572}
    573
    574#[stable(feature = "split_inclusive", since = "1.51.0")]
    575impl<T: fmt::Debug, P> fmt::Debug for SplitInclusive<'_, T, P>
    576where
    577    P: FnMut(&T) -> bool,
    578{
    579    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    580        f.debug_struct("SplitInclusive")
    581            .field("v", &self.v)
    582            .field("finished", &self.finished)
    583            .finish()
    584    }
    585}
    586
    587// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
    588#[stable(feature = "split_inclusive", since = "1.51.0")]
    589impl<T, P> Clone for SplitInclusive<'_, T, P>
    590where
    591    P: Clone + FnMut(&T) -> bool,
    592{
    593    fn clone(&self) -> Self {
    594        SplitInclusive { v: self.v, pred: self.pred.clone(), finished: self.finished }
    595    }
    596}
    597
    598#[stable(feature = "split_inclusive", since = "1.51.0")]
    599impl<'a, T, P> Iterator for SplitInclusive<'a, T, P>
    600where
    601    P: FnMut(&T) -> bool,
    602{
    603    type Item = &'a [T];
    604
    605    #[inline]
    606    fn next(&mut self) -> Option<&'a [T]> {
    607        if self.finished {
    608            return None;
    609        }
    610
    611        let idx =
    612            self.v.iter().position(|x| (self.pred)(x)).map(|idx| idx + 1).unwrap_or(self.v.len());
    613        if idx == self.v.len() {
    614            self.finished = true;
    615        }
    616        let ret = Some(&self.v[..idx]);
    617        self.v = &self.v[idx..];
    618        ret
    619    }
    620
    621    #[inline]
    622    fn size_hint(&self) -> (usize, Option<usize>) {
    623        if self.finished {
    624            (0, Some(0))
    625        } else {
    626            // If the predicate doesn't match anything, we yield one slice.
    627            // If it matches every element, we yield `len()` one-element slices,
    628            // or a single empty slice.
    629            (1, Some(cmp::max(1, self.v.len())))
    630        }
    631    }
    632}
    633
    634#[stable(feature = "split_inclusive", since = "1.51.0")]
    635impl<'a, T, P> DoubleEndedIterator for SplitInclusive<'a, T, P>
    636where
    637    P: FnMut(&T) -> bool,
    638{
    639    #[inline]
    640    fn next_back(&mut self) -> Option<&'a [T]> {
    641        if self.finished {
    642            return None;
    643        }
    644
    645        // The last index of self.v is already checked and found to match
    646        // by the last iteration, so we start searching a new match
    647        // one index to the left.
    648        let remainder = if self.v.is_empty() { &[] } else { &self.v[..(self.v.len() - 1)] };
    649        let idx = remainder.iter().rposition(|x| (self.pred)(x)).map(|idx| idx + 1).unwrap_or(0);
    650        if idx == 0 {
    651            self.finished = true;
    652        }
    653        let ret = Some(&self.v[idx..]);
    654        self.v = &self.v[..idx];
    655        ret
    656    }
    657}
    658
    659#[stable(feature = "split_inclusive", since = "1.51.0")]
    660impl<T, P> FusedIterator for SplitInclusive<'_, T, P> where P: FnMut(&T) -> bool {}
    661
    662/// An iterator over the mutable subslices of the vector which are separated
    663/// by elements that match `pred`.
    664///
    665/// This struct is created by the [`split_mut`] method on [slices].
    666///
    667/// # Example
    668///
    669/// ```
    670/// let mut v = [10, 40, 30, 20, 60, 50];
    671/// let iter = v.split_mut(|num| *num % 3 == 0);
    672/// ```
    673///
    674/// [`split_mut`]: slice::split_mut
    675/// [slices]: slice
    676#[stable(feature = "rust1", since = "1.0.0")]
    677#[must_use = "iterators are lazy and do nothing unless consumed"]
    678pub struct SplitMut<'a, T: 'a, P>
    679where
    680    P: FnMut(&T) -> bool,
    681{
    682    v: &'a mut [T],
    683    pred: P,
    684    finished: bool,
    685}
    686
    687impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitMut<'a, T, P> {
    688    #[inline]
    689    pub(super) fn new(slice: &'a mut [T], pred: P) -> Self {
    690        Self { v: slice, pred, finished: false }
    691    }
    692}
    693
    694#[stable(feature = "core_impl_debug", since = "1.9.0")]
    695impl<T: fmt::Debug, P> fmt::Debug for SplitMut<'_, T, P>
    696where
    697    P: FnMut(&T) -> bool,
    698{
    699    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    700        f.debug_struct("SplitMut").field("v", &self.v).field("finished", &self.finished).finish()
    701    }
    702}
    703
    704impl<'a, T, P> SplitIter for SplitMut<'a, T, P>
    705where
    706    P: FnMut(&T) -> bool,
    707{
    708    #[inline]
    709    fn finish(&mut self) -> Option<&'a mut [T]> {
    710        if self.finished {
    711            None
    712        } else {
    713            self.finished = true;
    714            Some(mem::take(&mut self.v))
    715        }
    716    }
    717}
    718
    719#[stable(feature = "rust1", since = "1.0.0")]
    720impl<'a, T, P> Iterator for SplitMut<'a, T, P>
    721where
    722    P: FnMut(&T) -> bool,
    723{
    724    type Item = &'a mut [T];
    725
    726    #[inline]
    727    fn next(&mut self) -> Option<&'a mut [T]> {
    728        if self.finished {
    729            return None;
    730        }
    731
    732        match self.v.iter().position(|x| (self.pred)(x)) {
    733            None => self.finish(),
    734            Some(idx) => {
    735                let tmp = mem::take(&mut self.v);
    736                // idx is the index of the element we are splitting on. We want to set self to the
    737                // region after idx, and return the subslice before and not including idx.
    738                // So first we split after idx
    739                let (head, tail) = tmp.split_at_mut(idx + 1);
    740                self.v = tail;
    741                // Then return the subslice up to but not including the found element
    742                Some(&mut head[..idx])
    743            }
    744        }
    745    }
    746
    747    #[inline]
    748    fn size_hint(&self) -> (usize, Option<usize>) {
    749        if self.finished {
    750            (0, Some(0))
    751        } else {
    752            // If the predicate doesn't match anything, we yield one slice.
    753            // If it matches every element, we yield `len() + 1` empty slices.
    754            (1, Some(self.v.len() + 1))
    755        }
    756    }
    757}
    758
    759#[stable(feature = "rust1", since = "1.0.0")]
    760impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P>
    761where
    762    P: FnMut(&T) -> bool,
    763{
    764    #[inline]
    765    fn next_back(&mut self) -> Option<&'a mut [T]> {
    766        if self.finished {
    767            return None;
    768        }
    769
    770        let idx_opt = {
    771            // work around borrowck limitations
    772            let pred = &mut self.pred;
    773            self.v.iter().rposition(|x| (*pred)(x))
    774        };
    775        match idx_opt {
    776            None => self.finish(),
    777            Some(idx) => {
    778                let tmp = mem::take(&mut self.v);
    779                let (head, tail) = tmp.split_at_mut(idx);
    780                self.v = head;
    781                Some(&mut tail[1..])
    782            }
    783        }
    784    }
    785}
    786
    787#[stable(feature = "fused", since = "1.26.0")]
    788impl<T, P> FusedIterator for SplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
    789
    790/// An iterator over the mutable subslices of the vector which are separated
    791/// by elements that match `pred`. Unlike `SplitMut`, it contains the matched
    792/// parts in the ends of the subslices.
    793///
    794/// This struct is created by the [`split_inclusive_mut`] method on [slices].
    795///
    796/// # Example
    797///
    798/// ```
    799/// let mut v = [10, 40, 30, 20, 60, 50];
    800/// let iter = v.split_inclusive_mut(|num| *num % 3 == 0);
    801/// ```
    802///
    803/// [`split_inclusive_mut`]: slice::split_inclusive_mut
    804/// [slices]: slice
    805#[stable(feature = "split_inclusive", since = "1.51.0")]
    806#[must_use = "iterators are lazy and do nothing unless consumed"]
    807pub struct SplitInclusiveMut<'a, T: 'a, P>
    808where
    809    P: FnMut(&T) -> bool,
    810{
    811    v: &'a mut [T],
    812    pred: P,
    813    finished: bool,
    814}
    815
    816impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitInclusiveMut<'a, T, P> {
    817    #[inline]
    818    pub(super) fn new(slice: &'a mut [T], pred: P) -> Self {
    819        let finished = slice.is_empty();
    820        Self { v: slice, pred, finished }
    821    }
    822}
    823
    824#[stable(feature = "split_inclusive", since = "1.51.0")]
    825impl<T: fmt::Debug, P> fmt::Debug for SplitInclusiveMut<'_, T, P>
    826where
    827    P: FnMut(&T) -> bool,
    828{
    829    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    830        f.debug_struct("SplitInclusiveMut")
    831            .field("v", &self.v)
    832            .field("finished", &self.finished)
    833            .finish()
    834    }
    835}
    836
    837#[stable(feature = "split_inclusive", since = "1.51.0")]
    838impl<'a, T, P> Iterator for SplitInclusiveMut<'a, T, P>
    839where
    840    P: FnMut(&T) -> bool,
    841{
    842    type Item = &'a mut [T];
    843
    844    #[inline]
    845    fn next(&mut self) -> Option<&'a mut [T]> {
    846        if self.finished {
    847            return None;
    848        }
    849
    850        let idx_opt = {
    851            // work around borrowck limitations
    852            let pred = &mut self.pred;
    853            self.v.iter().position(|x| (*pred)(x))
    854        };
    855        let idx = idx_opt.map(|idx| idx + 1).unwrap_or(self.v.len());
    856        if idx == self.v.len() {
    857            self.finished = true;
    858        }
    859        let tmp = mem::take(&mut self.v);
    860        let (head, tail) = tmp.split_at_mut(idx);
    861        self.v = tail;
    862        Some(head)
    863    }
    864
    865    #[inline]
    866    fn size_hint(&self) -> (usize, Option<usize>) {
    867        if self.finished {
    868            (0, Some(0))
    869        } else {
    870            // If the predicate doesn't match anything, we yield one slice.
    871            // If it matches every element, we yield `len()` one-element slices,
    872            // or a single empty slice.
    873            (1, Some(cmp::max(1, self.v.len())))
    874        }
    875    }
    876}
    877
    878#[stable(feature = "split_inclusive", since = "1.51.0")]
    879impl<'a, T, P> DoubleEndedIterator for SplitInclusiveMut<'a, T, P>
    880where
    881    P: FnMut(&T) -> bool,
    882{
    883    #[inline]
    884    fn next_back(&mut self) -> Option<&'a mut [T]> {
    885        if self.finished {
    886            return None;
    887        }
    888
    889        let idx_opt = if self.v.is_empty() {
    890            None
    891        } else {
    892            // work around borrowck limitations
    893            let pred = &mut self.pred;
    894
    895            // The last index of self.v is already checked and found to match
    896            // by the last iteration, so we start searching a new match
    897            // one index to the left.
    898            let remainder = &self.v[..(self.v.len() - 1)];
    899            remainder.iter().rposition(|x| (*pred)(x))
    900        };
    901        let idx = idx_opt.map(|idx| idx + 1).unwrap_or(0);
    902        if idx == 0 {
    903            self.finished = true;
    904        }
    905        let tmp = mem::take(&mut self.v);
    906        let (head, tail) = tmp.split_at_mut(idx);
    907        self.v = head;
    908        Some(tail)
    909    }
    910}
    911
    912#[stable(feature = "split_inclusive", since = "1.51.0")]
    913impl<T, P> FusedIterator for SplitInclusiveMut<'_, T, P> where P: FnMut(&T) -> bool {}
    914
    915/// An iterator over subslices separated by elements that match a predicate
    916/// function, starting from the end of the slice.
    917///
    918/// This struct is created by the [`rsplit`] method on [slices].
    919///
    920/// # Example
    921///
    922/// ```
    923/// let slice = [11, 22, 33, 0, 44, 55];
    924/// let mut iter = slice.rsplit(|num| *num == 0);
    925/// assert_eq!(iter.next(), Some(&[44, 55][..]));
    926/// assert_eq!(iter.next(), Some(&[11, 22, 33][..]));
    927/// assert_eq!(iter.next(), None);
    928/// ```
    929///
    930/// [`rsplit`]: slice::rsplit
    931/// [slices]: slice
    932#[stable(feature = "slice_rsplit", since = "1.27.0")]
    933#[must_use = "iterators are lazy and do nothing unless consumed"]
    934pub struct RSplit<'a, T: 'a, P>
    935where
    936    P: FnMut(&T) -> bool,
    937{
    938    inner: Split<'a, T, P>,
    939}
    940
    941impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplit<'a, T, P> {
    942    #[inline]
    943    pub(super) fn new(slice: &'a [T], pred: P) -> Self {
    944        Self { inner: Split::new(slice, pred) }
    945    }
    946}
    947
    948#[stable(feature = "slice_rsplit", since = "1.27.0")]
    949impl<T: fmt::Debug, P> fmt::Debug for RSplit<'_, T, P>
    950where
    951    P: FnMut(&T) -> bool,
    952{
    953    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    954        f.debug_struct("RSplit")
    955            .field("v", &self.inner.v)
    956            .field("finished", &self.inner.finished)
    957            .finish()
    958    }
    959}
    960
    961// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
    962#[stable(feature = "slice_rsplit", since = "1.27.0")]
    963impl<T, P> Clone for RSplit<'_, T, P>
    964where
    965    P: Clone + FnMut(&T) -> bool,
    966{
    967    fn clone(&self) -> Self {
    968        RSplit { inner: self.inner.clone() }
    969    }
    970}
    971
    972#[stable(feature = "slice_rsplit", since = "1.27.0")]
    973impl<'a, T, P> Iterator for RSplit<'a, T, P>
    974where
    975    P: FnMut(&T) -> bool,
    976{
    977    type Item = &'a [T];
    978
    979    #[inline]
    980    fn next(&mut self) -> Option<&'a [T]> {
    981        self.inner.next_back()
    982    }
    983
    984    #[inline]
    985    fn size_hint(&self) -> (usize, Option<usize>) {
    986        self.inner.size_hint()
    987    }
    988}
    989
    990#[stable(feature = "slice_rsplit", since = "1.27.0")]
    991impl<'a, T, P> DoubleEndedIterator for RSplit<'a, T, P>
    992where
    993    P: FnMut(&T) -> bool,
    994{
    995    #[inline]
    996    fn next_back(&mut self) -> Option<&'a [T]> {
    997        self.inner.next()
    998    }
    999}
    1000
    1001#[stable(feature = "slice_rsplit", since = "1.27.0")]
    1002impl<'a, T, P> SplitIter for RSplit<'a, T, P>
    1003where
    1004    P: FnMut(&T) -> bool,
    1005{
    1006    #[inline]
    1007    fn finish(&mut self) -> Option<&'a [T]> {
    1008        self.inner.finish()
    1009    }
    1010}
    1011
    1012#[stable(feature = "slice_rsplit", since = "1.27.0")]
    1013impl<T, P> FusedIterator for RSplit<'_, T, P> where P: FnMut(&T) -> bool {}
    1014
    1015/// An iterator over the subslices of the vector which are separated
    1016/// by elements that match `pred`, starting from the end of the slice.
    1017///
    1018/// This struct is created by the [`rsplit_mut`] method on [slices].
    1019///
    1020/// # Example
    1021///
    1022/// ```
    1023/// let mut slice = [11, 22, 33, 0, 44, 55];
    1024/// let iter = slice.rsplit_mut(|num| *num == 0);
    1025/// ```
    1026///
    1027/// [`rsplit_mut`]: slice::rsplit_mut
    1028/// [slices]: slice
    1029#[stable(feature = "slice_rsplit", since = "1.27.0")]
    1030#[must_use = "iterators are lazy and do nothing unless consumed"]
    1031pub struct RSplitMut<'a, T: 'a, P>
    1032where
    1033    P: FnMut(&T) -> bool,
    1034{
    1035    inner: SplitMut<'a, T, P>,
    1036}
    1037
    1038impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplitMut<'a, T, P> {
    1039    #[inline]
    1040    pub(super) fn new(slice: &'a mut [T], pred: P) -> Self {
    1041        Self { inner: SplitMut::new(slice, pred) }
    1042    }
    1043}
    1044
    1045#[stable(feature = "slice_rsplit", since = "1.27.0")]
    1046impl<T: fmt::Debug, P> fmt::Debug for RSplitMut<'_, T, P>
    1047where
    1048    P: FnMut(&T) -> bool,
    1049{
    1050    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    1051        f.debug_struct("RSplitMut")
    1052            .field("v", &self.inner.v)
    1053            .field("finished", &self.inner.finished)
    1054            .finish()
    1055    }
    1056}
    1057
    1058#[stable(feature = "slice_rsplit", since = "1.27.0")]
    1059impl<'a, T, P> SplitIter for RSplitMut<'a, T, P>
    1060where
    1061    P: FnMut(&T) -> bool,
    1062{
    1063    #[inline]
    1064    fn finish(&mut self) -> Option<&'a mut [T]> {
    1065        self.inner.finish()
    1066    }
    1067}
    1068
    1069#[stable(feature = "slice_rsplit", since = "1.27.0")]
    1070impl<'a, T, P> Iterator for RSplitMut<'a, T, P>
    1071where
    1072    P: FnMut(&T) -> bool,
    1073{
    1074    type Item = &'a mut [T];
    1075
    1076    #[inline]
    1077    fn next(&mut self) -> Option<&'a mut [T]> {
    1078        self.inner.next_back()
    1079    }
    1080
    1081    #[inline]
    1082    fn size_hint(&self) -> (usize, Option<usize>) {
    1083        self.inner.size_hint()
    1084    }
    1085}
    1086
    1087#[stable(feature = "slice_rsplit", since = "1.27.0")]
    1088impl<'a, T, P> DoubleEndedIterator for RSplitMut<'a, T, P>
    1089where
    1090    P: FnMut(&T) -> bool,
    1091{
    1092    #[inline]
    1093    fn next_back(&mut self) -> Option<&'a mut [T]> {
    1094        self.inner.next()
    1095    }
    1096}
    1097
    1098#[stable(feature = "slice_rsplit", since = "1.27.0")]
    1099impl<T, P> FusedIterator for RSplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
    1100
    1101/// An private iterator over subslices separated by elements that
    1102/// match a predicate function, splitting at most a fixed number of
    1103/// times.
    1104#[derive(Debug)]
    1105struct GenericSplitN<I> {
    1106    iter: I,
    1107    count: usize,
    1108}
    1109
    1110impl<T, I: SplitIter<Item = T>> Iterator for GenericSplitN<I> {
    1111    type Item = T;
    1112
    1113    #[inline]
    1114    fn next(&mut self) -> Option<T> {
    1115        match self.count {
    1116            0 => None,
    1117            1 => {
    1118                self.count -= 1;
    1119                self.iter.finish()
    1120            }
    1121            _ => {
    1122                self.count -= 1;
    1123                self.iter.next()
    1124            }
    1125        }
    1126    }
    1127
    1128    #[inline]
    1129    fn size_hint(&self) -> (usize, Option<usize>) {
    1130        let (lower, upper_opt) = self.iter.size_hint();
    1131        (
    1132            cmp::min(self.count, lower),
    1133            Some(upper_opt.map_or(self.count, |upper| cmp::min(self.count, upper))),
    1134        )
    1135    }
    1136}
    1137
    1138/// An iterator over subslices separated by elements that match a predicate
    1139/// function, limited to a given number of splits.
    1140///
    1141/// This struct is created by the [`splitn`] method on [slices].
    1142///
    1143/// # Example
    1144///
    1145/// ```
    1146/// let slice = [10, 40, 30, 20, 60, 50];
    1147/// let mut iter = slice.splitn(2, |num| *num % 3 == 0);
    1148/// assert_eq!(iter.next(), Some(&[10, 40][..]));
    1149/// assert_eq!(iter.next(), Some(&[20, 60, 50][..]));
    1150/// assert_eq!(iter.next(), None);
    1151/// ```
    1152///
    1153/// [`splitn`]: slice::splitn
    1154/// [slices]: slice
    1155#[stable(feature = "rust1", since = "1.0.0")]
    1156#[must_use = "iterators are lazy and do nothing unless consumed"]
    1157pub struct SplitN<'a, T: 'a, P>
    1158where
    1159    P: FnMut(&T) -> bool,
    1160{
    1161    inner: GenericSplitN<Split<'a, T, P>>,
    1162}
    1163
    1164impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitN<'a, T, P> {
    1165    #[inline]
    1166    pub(super) fn new(s: Split<'a, T, P>, n: usize) -> Self {
    1167        Self { inner: GenericSplitN { iter: s, count: n } }
    1168    }
    1169}
    1170
    1171#[stable(feature = "core_impl_debug", since = "1.9.0")]
    1172impl<T: fmt::Debug, P> fmt::Debug for SplitN<'_, T, P>
    1173where
    1174    P: FnMut(&T) -> bool,
    1175{
    1176    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    1177        f.debug_struct("SplitN").field("inner", &self.inner).finish()
    1178    }
    1179}
    1180
    1181/// An iterator over subslices separated by elements that match a
    1182/// predicate function, limited to a given number of splits, starting
    1183/// from the end of the slice.
    1184///
    1185/// This struct is created by the [`rsplitn`] method on [slices].
    1186///
    1187/// # Example
    1188///
    1189/// ```
    1190/// let slice = [10, 40, 30, 20, 60, 50];
    1191/// let mut iter = slice.rsplitn(2, |num| *num % 3 == 0);
    1192/// assert_eq!(iter.next(), Some(&[50][..]));
    1193/// assert_eq!(iter.next(), Some(&[10, 40, 30, 20][..]));
    1194/// assert_eq!(iter.next(), None);
    1195/// ```
    1196///
    1197/// [`rsplitn`]: slice::rsplitn
    1198/// [slices]: slice
    1199#[stable(feature = "rust1", since = "1.0.0")]
    1200#[must_use = "iterators are lazy and do nothing unless consumed"]
    1201pub struct RSplitN<'a, T: 'a, P>
    1202where
    1203    P: FnMut(&T) -> bool,
    1204{
    1205    inner: GenericSplitN<RSplit<'a, T, P>>,
    1206}
    1207
    1208impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplitN<'a, T, P> {
    1209    #[inline]
    1210    pub(super) fn new(s: RSplit<'a, T, P>, n: usize) -> Self {
    1211        Self { inner: GenericSplitN { iter: s, count: n } }
    1212    }
    1213}
    1214
    1215#[stable(feature = "core_impl_debug", since = "1.9.0")]
    1216impl<T: fmt::Debug, P> fmt::Debug for RSplitN<'_, T, P>
    1217where
    1218    P: FnMut(&T) -> bool,
    1219{
    1220    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    1221        f.debug_struct("RSplitN").field("inner", &self.inner).finish()
    1222    }
    1223}
    1224
    1225/// An iterator over subslices separated by elements that match a predicate
    1226/// function, limited to a given number of splits.
    1227///
    1228/// This struct is created by the [`splitn_mut`] method on [slices].
    1229///
    1230/// # Example
    1231///
    1232/// ```
    1233/// let mut slice = [10, 40, 30, 20, 60, 50];
    1234/// let iter = slice.splitn_mut(2, |num| *num % 3 == 0);
    1235/// ```
    1236///
    1237/// [`splitn_mut`]: slice::splitn_mut
    1238/// [slices]: slice
    1239#[stable(feature = "rust1", since = "1.0.0")]
    1240#[must_use = "iterators are lazy and do nothing unless consumed"]
    1241pub struct SplitNMut<'a, T: 'a, P>
    1242where
    1243    P: FnMut(&T) -> bool,
    1244{
    1245    inner: GenericSplitN<SplitMut<'a, T, P>>,
    1246}
    1247
    1248impl<'a, T: 'a, P: FnMut(&T) -> bool> SplitNMut<'a, T, P> {
    1249    #[inline]
    1250    pub(super) fn new(s: SplitMut<'a, T, P>, n: usize) -> Self {
    1251        Self { inner: GenericSplitN { iter: s, count: n } }
    1252    }
    1253}
    1254
    1255#[stable(feature = "core_impl_debug", since = "1.9.0")]
    1256impl<T: fmt::Debug, P> fmt::Debug for SplitNMut<'_, T, P>
    1257where
    1258    P: FnMut(&T) -> bool,
    1259{
    1260    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    1261        f.debug_struct("SplitNMut").field("inner", &self.inner).finish()
    1262    }
    1263}
    1264
    1265/// An iterator over subslices separated by elements that match a
    1266/// predicate function, limited to a given number of splits, starting
    1267/// from the end of the slice.
    1268///
    1269/// This struct is created by the [`rsplitn_mut`] method on [slices].
    1270///
    1271/// # Example
    1272///
    1273/// ```
    1274/// let mut slice = [10, 40, 30, 20, 60, 50];
    1275/// let iter = slice.rsplitn_mut(2, |num| *num % 3 == 0);
    1276/// ```
    1277///
    1278/// [`rsplitn_mut`]: slice::rsplitn_mut
    1279/// [slices]: slice
    1280#[stable(feature = "rust1", since = "1.0.0")]
    1281#[must_use = "iterators are lazy and do nothing unless consumed"]
    1282pub struct RSplitNMut<'a, T: 'a, P>
    1283where
    1284    P: FnMut(&T) -> bool,
    1285{
    1286    inner: GenericSplitN<RSplitMut<'a, T, P>>,
    1287}
    1288
    1289impl<'a, T: 'a, P: FnMut(&T) -> bool> RSplitNMut<'a, T, P> {
    1290    #[inline]
    1291    pub(super) fn new(s: RSplitMut<'a, T, P>, n: usize) -> Self {
    1292        Self { inner: GenericSplitN { iter: s, count: n } }
    1293    }
    1294}
    1295
    1296#[stable(feature = "core_impl_debug", since = "1.9.0")]
    1297impl<T: fmt::Debug, P> fmt::Debug for RSplitNMut<'_, T, P>
    1298where
    1299    P: FnMut(&T) -> bool,
    1300{
    1301    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    1302        f.debug_struct("RSplitNMut").field("inner", &self.inner).finish()
    1303    }
    1304}
    1305
    1306forward_iterator! { SplitN: T, &'a [T] }
    1307forward_iterator! { RSplitN: T, &'a [T] }
    1308forward_iterator! { SplitNMut: T, &'a mut [T] }
    1309forward_iterator! { RSplitNMut: T, &'a mut [T] }
    1310
    1311/// An iterator over overlapping subslices of length `size`.
    1312///
    1313/// This struct is created by the [`windows`] method on [slices].
    1314///
    1315/// # Example
    1316///
    1317/// ```
    1318/// let slice = ['r', 'u', 's', 't'];
    1319/// let mut iter = slice.windows(2);
    1320/// assert_eq!(iter.next(), Some(&['r', 'u'][..]));
    1321/// assert_eq!(iter.next(), Some(&['u', 's'][..]));
    1322/// assert_eq!(iter.next(), Some(&['s', 't'][..]));
    1323/// assert_eq!(iter.next(), None);
    1324/// ```
    1325///
    1326/// [`windows`]: slice::windows
    1327/// [slices]: slice
    1328#[derive(Debug)]
    1329#[stable(feature = "rust1", since = "1.0.0")]
    1330#[must_use = "iterators are lazy and do nothing unless consumed"]
    1331pub struct Windows<'a, T: 'a> {
    1332    v: &'a [T],
    1333    size: NonZero<usize>,
    1334}
    1335
    1336impl<'a, T: 'a> Windows<'a, T> {
    1337    #[inline]
    1338    pub(super) const fn new(slice: &'a [T], size: NonZero<usize>) -> Self {
    1339        Self { v: slice, size }
    1340    }
    1341}
    1342
    1343// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
    1344#[stable(feature = "rust1", since = "1.0.0")]
    1345impl<T> Clone for Windows<'_, T> {
    1346    fn clone(&self) -> Self {
    1347        Windows { v: self.v, size: self.size }
    1348    }
    1349}
    1350
    1351#[stable(feature = "rust1", since = "1.0.0")]
    1352impl<'a, T> Iterator for Windows<'a, T> {
    1353    type Item = &'a [T];
    1354
    1355    #[inline]
    1356    fn next(&mut self) -> Option<&'a [T]> {
    1357        if self.size.get() > self.v.len() {
    1358            None
    1359        } else {
    1360            let ret = Some(&self.v[..self.size.get()]);
    1361            self.v = &self.v[1..];
    1362            ret
    1363        }
    1364    }
    1365
    1366    #[inline]
    1367    fn size_hint(&self) -> (usize, Option<usize>) {
    1368        if self.size.get() > self.v.len() {
    1369            (0, Some(0))
    1370        } else {
    1371            let size = self.v.len() - self.size.get() + 1;
    1372            (size, Some(size))
    1373        }
    1374    }
    1375
    1376    #[inline]
    1377    fn count(self) -> usize {
    1378        self.len()
    1379    }
    1380
    1381    #[inline]
    1382    fn nth(&mut self, n: usize) -> Option<Self::Item> {
    1383        let size = self.size.get();
    1384        if let Some(rest) = self.v.get(n..)
    1385            && let Some(nth) = rest.get(..size)
    1386        {
    1387            self.v = &rest[1..];
    1388            Some(nth)
    1389        } else {
    1390            // setting length to 0 is cheaper than overwriting the pointer when assigning &[]
    1391            self.v = &self.v[..0]; // cheaper than &[]
    1392            None
    1393        }
    1394    }
    1395
    1396    #[inline]
    1397    fn last(self) -> Option<Self::Item> {
    1398        if self.size.get() > self.v.len() {
    1399            None
    1400        } else {
    1401            let start = self.v.len() - self.size.get();
    1402            Some(&self.v[start..])
    1403        }
    1404    }
    1405
    1406    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
    1407        // SAFETY: since the caller guarantees that `i` is in bounds,
    1408        // which means that `i` cannot overflow an `isize`, and the
    1409        // slice created by `from_raw_parts` is a subslice of `self.v`
    1410        // thus is guaranteed to be valid for the lifetime `'a` of `self.v`.
    1411        unsafe { from_raw_parts(self.v.as_ptr().add(idx), self.size.get()) }
    1412    }
    1413}
    1414
    1415#[stable(feature = "rust1", since = "1.0.0")]
    1416impl<'a, T> DoubleEndedIterator for Windows<'a, T> {
    1417    #[inline]
    1418    fn next_back(&mut self) -> Option<Self::Item> {
    1419        self.nth_back(0)
    1420    }
    1421
    1422    #[inline]
    1423    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
    1424        if let Some(end) = self.v.len().checked_sub(n)
    1425            && let Some(start) = end.checked_sub(self.size.get())
    1426        {
    1427            let res = &self.v[start..end];
    1428            self.v = &self.v[..end - 1];
    1429            Some(res)
    1430        } else {
    1431            self.v = &self.v[..0]; // cheaper than &[]
    1432            None
    1433        }
    1434    }
    1435}
    1436
    1437#[stable(feature = "rust1", since = "1.0.0")]
    1438impl<T> ExactSizeIterator for Windows<'_, T> {}
    1439
    1440#[unstable(feature = "trusted_len", issue = "37572")]
    1441unsafe impl<T> TrustedLen for Windows<'_, T> {}
    1442
    1443#[stable(feature = "fused", since = "1.26.0")]
    1444impl<T> FusedIterator for Windows<'_, T> {}
    1445
    1446#[doc(hidden)]
    1447#[unstable(feature = "trusted_random_access", issue = "none")]
    1448unsafe impl<'a, T> TrustedRandomAccess for Windows<'a, T> {}
    1449
    1450#[doc(hidden)]
    1451#[unstable(feature = "trusted_random_access", issue = "none")]
    1452unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Windows<'a, T> {
    1453    const MAY_HAVE_SIDE_EFFECT: bool = false;
    1454}
    1455
    1456/// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
    1457/// time), starting at the beginning of the slice.
    1458///
    1459/// When the slice len is not evenly divided by the chunk size, the last slice
    1460/// of the iteration will be the remainder.
    1461///
    1462/// This struct is created by the [`chunks`] method on [slices].
    1463///
    1464/// # Example
    1465///
    1466/// ```
    1467/// let slice = ['l', 'o', 'r', 'e', 'm'];
    1468/// let mut iter = slice.chunks(2);
    1469/// assert_eq!(iter.next(), Some(&['l', 'o'][..]));
    1470/// assert_eq!(iter.next(), Some(&['r', 'e'][..]));
    1471/// assert_eq!(iter.next(), Some(&['m'][..]));
    1472/// assert_eq!(iter.next(), None);
    1473/// ```
    1474///
    1475/// [`chunks`]: slice::chunks
    1476/// [slices]: slice
    1477#[derive(Debug)]
    1478#[stable(feature = "rust1", since = "1.0.0")]
    1479#[must_use = "iterators are lazy and do nothing unless consumed"]
    1480pub struct Chunks<'a, T: 'a> {
    1481    v: &'a [T],
    1482    chunk_size: usize,
    1483}
    1484
    1485impl<'a, T: 'a> Chunks<'a, T> {
    1486    #[inline]
    1487    pub(super) const fn new(slice: &'a [T], size: usize) -> Self {
    1488        Self { v: slice, chunk_size: size }
    1489    }
    1490}
    1491
    1492// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
    1493#[stable(feature = "rust1", since = "1.0.0")]
    1494impl<T> Clone for Chunks<'_, T> {
    1495    fn clone(&self) -> Self {
    1496        Chunks { v: self.v, chunk_size: self.chunk_size }
    1497    }
    1498}
    1499
    1500#[stable(feature = "rust1", since = "1.0.0")]
    1501impl<'a, T> Iterator for Chunks<'a, T> {
    1502    type Item = &'a [T];
    1503
    1504    #[inline]
    1505    fn next(&mut self) -> Option<&'a [T]> {
    1506        if self.v.is_empty() {
    1507            None
    1508        } else {
    1509            let chunksz = cmp::min(self.v.len(), self.chunk_size);
    1510            let (fst, snd) = self.v.split_at(chunksz);
    1511            self.v = snd;
    1512            Some(fst)
    1513        }
    1514    }
    1515
    1516    #[inline]
    1517    fn size_hint(&self) -> (usize, Option<usize>) {
    1518        if self.v.is_empty() {
    1519            (0, Some(0))
    1520        } else {
    1521            let n = self.v.len().div_ceil(self.chunk_size);
    1522            (n, Some(n))
    1523        }
    1524    }
    1525
    1526    #[inline]
    1527    fn count(self) -> usize {
    1528        self.len()
    1529    }
    1530
    1531    #[inline]
    1532    fn nth(&mut self, n: usize) -> Option<Self::Item> {
    1533        if let Some(start) = n.checked_mul(self.chunk_size)
    1534            && start < self.v.len()
    1535        {
    1536            let rest = &self.v[start..];
    1537            let (chunk, rest) = rest.split_at(self.chunk_size.min(rest.len()));
    1538            self.v = rest;
    1539            Some(chunk)
    1540        } else {
    1541            self.v = &self.v[..0]; // cheaper than &[]
    1542            None
    1543        }
    1544    }
    1545
    1546    #[inline]
    1547    fn last(self) -> Option<Self::Item> {
    1548        if self.v.is_empty() {
    1549            None
    1550        } else {
    1551            let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
    1552            Some(&self.v[start..])
    1553        }
    1554    }
    1555
    1556    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
    1557        let start = idx * self.chunk_size;
    1558        // SAFETY: the caller guarantees that `i` is in bounds,
    1559        // which means that `start` must be in bounds of the
    1560        // underlying `self.v` slice, and we made sure that `len`
    1561        // is also in bounds of `self.v`. Thus, `start` cannot overflow
    1562        // an `isize`, and the slice constructed by `from_raw_parts`
    1563        // is a subslice of `self.v` which is guaranteed to be valid
    1564        // for the lifetime `'a` of `self.v`.
    1565        unsafe {
    1566            let len = cmp::min(self.v.len().unchecked_sub(start), self.chunk_size);
    1567            from_raw_parts(self.v.as_ptr().add(start), len)
    1568        }
    1569    }
    1570}
    1571
    1572#[stable(feature = "rust1", since = "1.0.0")]
    1573impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
    1574    #[inline]
    1575    fn next_back(&mut self) -> Option<&'a [T]> {
    1576        if self.v.is_empty() {
    1577            None
    1578        } else {
    1579            let remainder = self.v.len() % self.chunk_size;
    1580            let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
    1581            // SAFETY: split_at_unchecked requires the argument be less than or
    1582            // equal to the length. This is guaranteed, but subtle: `chunksz`
    1583            // will always either be `self.v.len() % self.chunk_size`, which
    1584            // will always evaluate to strictly less than `self.v.len()` (or
    1585            // panic, in the case that `self.chunk_size` is zero), or it can be
    1586            // `self.chunk_size`, in the case that the length is exactly
    1587            // divisible by the chunk size.
    1588            //
    1589            // While it seems like using `self.chunk_size` in this case could
    1590            // lead to a value greater than `self.v.len()`, it cannot: if
    1591            // `self.chunk_size` were greater than `self.v.len()`, then
    1592            // `self.v.len() % self.chunk_size` would return nonzero (note that
    1593            // in this branch of the `if`, we already know that `self.v` is
    1594            // non-empty).
    1595            let (fst, snd) = unsafe { self.v.split_at_unchecked(self.v.len() - chunksz) };
    1596            self.v = fst;
    1597            Some(snd)
    1598        }
    1599    }
    1600
    1601    #[inline]
    1602    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
    1603        let len = self.len();
    1604        if n < len {
    1605            let start = (len - 1 - n) * self.chunk_size;
    1606            let end = start + (self.v.len() - start).min(self.chunk_size);
    1607            let nth_back = &self.v[start..end];
    1608            self.v = &self.v[..start];
    1609            Some(nth_back)
    1610        } else {
    1611            self.v = &self.v[..0]; // cheaper than &[]
    1612            None
    1613        }
    1614    }
    1615}
    1616
    1617#[stable(feature = "rust1", since = "1.0.0")]
    1618impl<T> ExactSizeIterator for Chunks<'_, T> {}
    1619
    1620#[unstable(feature = "trusted_len", issue = "37572")]
    1621unsafe impl<T> TrustedLen for Chunks<'_, T> {}
    1622
    1623#[stable(feature = "fused", since = "1.26.0")]
    1624impl<T> FusedIterator for Chunks<'_, T> {}
    1625
    1626#[doc(hidden)]
    1627#[unstable(feature = "trusted_random_access", issue = "none")]
    1628unsafe impl<'a, T> TrustedRandomAccess for Chunks<'a, T> {}
    1629
    1630#[doc(hidden)]
    1631#[unstable(feature = "trusted_random_access", issue = "none")]
    1632unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Chunks<'a, T> {
    1633    const MAY_HAVE_SIDE_EFFECT: bool = false;
    1634}
    1635
    1636/// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
    1637/// elements at a time), starting at the beginning of the slice.
    1638///
    1639/// When the slice len is not evenly divided by the chunk size, the last slice
    1640/// of the iteration will be the remainder.
    1641///
    1642/// This struct is created by the [`chunks_mut`] method on [slices].
    1643///
    1644/// # Example
    1645///
    1646/// ```
    1647/// let mut slice = ['l', 'o', 'r', 'e', 'm'];
    1648/// let iter = slice.chunks_mut(2);
    1649/// ```
    1650///
    1651/// [`chunks_mut`]: slice::chunks_mut
    1652/// [slices]: slice
    1653#[derive(Debug)]
    1654#[stable(feature = "rust1", since = "1.0.0")]
    1655#[must_use = "iterators are lazy and do nothing unless consumed"]
    1656pub struct ChunksMut<'a, T: 'a> {
    1657    /// # Safety
    1658    /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
    1659    /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
    1660    /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
    1661    /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
    1662    /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
    1663    v: *mut [T],
    1664    chunk_size: usize,
    1665    _marker: PhantomData<&'a mut T>,
    1666}
    1667
    1668impl<'a, T: 'a> ChunksMut<'a, T> {
    1669    #[inline]
    1670    pub(super) const fn new(slice: &'a mut [T], size: usize) -> Self {
    1671        Self { v: slice, chunk_size: size, _marker: PhantomData }
    1672    }
    1673}
    1674
    1675#[stable(feature = "rust1", since = "1.0.0")]
    1676impl<'a, T> Iterator for ChunksMut<'a, T> {
    1677    type Item = &'a mut [T];
    1678
    1679    #[inline]
    1680    fn next(&mut self) -> Option<&'a mut [T]> {
    1681        if self.v.is_empty() {
    1682            None
    1683        } else {
    1684            let sz = cmp::min(self.v.len(), self.chunk_size);
    1685            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    1686            let (head, tail) = unsafe { self.v.split_at_mut(sz) };
    1687            self.v = tail;
    1688            // SAFETY: Nothing else points to or will point to the contents of this slice.
    1689            Some(unsafe { &mut *head })
    1690        }
    1691    }
    1692
    1693    #[inline]
    1694    fn size_hint(&self) -> (usize, Option<usize>) {
    1695        if self.v.is_empty() {
    1696            (0, Some(0))
    1697        } else {
    1698            let n = self.v.len().div_ceil(self.chunk_size);
    1699            (n, Some(n))
    1700        }
    1701    }
    1702
    1703    #[inline]
    1704    fn count(self) -> usize {
    1705        self.len()
    1706    }
    1707
    1708    #[inline]
    1709    fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
    1710        if let Some(start) = n.checked_mul(self.chunk_size)
    1711            && start < self.v.len()
    1712        {
    1713            // SAFETY: `start < self.v.len()` ensures this is in bounds
    1714            let (_, rest) = unsafe { self.v.split_at_mut(start) };
    1715            // SAFETY: `.min(rest.len()` ensures this is in bounds
    1716            let (chunk, rest) = unsafe { rest.split_at_mut(self.chunk_size.min(rest.len())) };
    1717            self.v = rest;
    1718            // SAFETY: Nothing else points to or will point to the contents of this slice.
    1719            Some(unsafe { &mut *chunk })
    1720        } else {
    1721            self.v = &mut [];
    1722            None
    1723        }
    1724    }
    1725
    1726    #[inline]
    1727    fn last(self) -> Option<Self::Item> {
    1728        if self.v.is_empty() {
    1729            None
    1730        } else {
    1731            let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
    1732            // SAFETY: Nothing else points to or will point to the contents of this slice.
    1733            Some(unsafe { &mut *self.v.get_unchecked_mut(start..) })
    1734        }
    1735    }
    1736
    1737    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
    1738        let start = idx * self.chunk_size;
    1739        // SAFETY: see comments for `Chunks::__iterator_get_unchecked` and `self.v`.
    1740        //
    1741        // Also note that the caller also guarantees that we're never called
    1742        // with the same index again, and that no other methods that will
    1743        // access this subslice are called, so it is valid for the returned
    1744        // slice to be mutable.
    1745        unsafe {
    1746            let len = cmp::min(self.v.len().unchecked_sub(start), self.chunk_size);
    1747            from_raw_parts_mut(self.v.as_mut_ptr().add(start), len)
    1748        }
    1749    }
    1750}
    1751
    1752#[stable(feature = "rust1", since = "1.0.0")]
    1753impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
    1754    #[inline]
    1755    fn next_back(&mut self) -> Option<&'a mut [T]> {
    1756        if self.v.is_empty() {
    1757            None
    1758        } else {
    1759            let remainder = self.v.len() % self.chunk_size;
    1760            let sz = if remainder != 0 { remainder } else { self.chunk_size };
    1761            let len = self.v.len();
    1762            // SAFETY: Similar to `Chunks::next_back`
    1763            let (head, tail) = unsafe { self.v.split_at_mut_unchecked(len - sz) };
    1764            self.v = head;
    1765            // SAFETY: Nothing else points to or will point to the contents of this slice.
    1766            Some(unsafe { &mut *tail })
    1767        }
    1768    }
    1769
    1770    #[inline]
    1771    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
    1772        let len = self.len();
    1773        if n < len {
    1774            let start = (len - 1 - n) * self.chunk_size;
    1775            let end = match start.checked_add(self.chunk_size) {
    1776                Some(res) => cmp::min(self.v.len(), res),
    1777                None => self.v.len(),
    1778            };
    1779            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    1780            let (temp, _tail) = unsafe { self.v.split_at_mut(end) };
    1781            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    1782            let (head, nth_back) = unsafe { temp.split_at_mut(start) };
    1783            self.v = head;
    1784            // SAFETY: Nothing else points to or will point to the contents of this slice.
    1785            Some(unsafe { &mut *nth_back })
    1786        } else {
    1787            self.v = &mut [];
    1788            None
    1789        }
    1790    }
    1791}
    1792
    1793#[stable(feature = "rust1", since = "1.0.0")]
    1794impl<T> ExactSizeIterator for ChunksMut<'_, T> {}
    1795
    1796#[unstable(feature = "trusted_len", issue = "37572")]
    1797unsafe impl<T> TrustedLen for ChunksMut<'_, T> {}
    1798
    1799#[stable(feature = "fused", since = "1.26.0")]
    1800impl<T> FusedIterator for ChunksMut<'_, T> {}
    1801
    1802#[doc(hidden)]
    1803#[unstable(feature = "trusted_random_access", issue = "none")]
    1804unsafe impl<'a, T> TrustedRandomAccess for ChunksMut<'a, T> {}
    1805
    1806#[doc(hidden)]
    1807#[unstable(feature = "trusted_random_access", issue = "none")]
    1808unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksMut<'a, T> {
    1809    const MAY_HAVE_SIDE_EFFECT: bool = false;
    1810}
    1811
    1812#[stable(feature = "rust1", since = "1.0.0")]
    1813unsafe impl<T> Send for ChunksMut<'_, T> where T: Send {}
    1814
    1815#[stable(feature = "rust1", since = "1.0.0")]
    1816unsafe impl<T> Sync for ChunksMut<'_, T> where T: Sync {}
    1817
    1818/// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
    1819/// time), starting at the beginning of the slice.
    1820///
    1821/// When the slice len is not evenly divided by the chunk size, the last
    1822/// up to `chunk_size-1` elements will be omitted but can be retrieved from
    1823/// the [`remainder`] function from the iterator.
    1824///
    1825/// This struct is created by the [`chunks_exact`] method on [slices].
    1826///
    1827/// # Example
    1828///
    1829/// ```
    1830/// let slice = ['l', 'o', 'r', 'e', 'm'];
    1831/// let mut iter = slice.chunks_exact(2);
    1832/// assert_eq!(iter.next(), Some(&['l', 'o'][..]));
    1833/// assert_eq!(iter.next(), Some(&['r', 'e'][..]));
    1834/// assert_eq!(iter.next(), None);
    1835/// ```
    1836///
    1837/// [`chunks_exact`]: slice::chunks_exact
    1838/// [`remainder`]: ChunksExact::remainder
    1839/// [slices]: slice
    1840#[derive(Debug)]
    1841#[stable(feature = "chunks_exact", since = "1.31.0")]
    1842#[must_use = "iterators are lazy and do nothing unless consumed"]
    1843pub struct ChunksExact<'a, T: 'a> {
    1844    v: &'a [T],
    1845    rem: &'a [T],
    1846    chunk_size: usize,
    1847}
    1848
    1849impl<'a, T> ChunksExact<'a, T> {
    1850    #[inline]
    1851    pub(super) const fn new(slice: &'a [T], chunk_size: usize) -> Self {
    1852        let rem = slice.len() % chunk_size;
    1853        let fst_len = slice.len() - rem;
    1854        // SAFETY: 0 <= fst_len <= slice.len() by construction above
    1855        let (fst, snd) = unsafe { slice.split_at_unchecked(fst_len) };
    1856        Self { v: fst, rem: snd, chunk_size }
    1857    }
    1858
    1859    /// Returns the remainder of the original slice that is not going to be
    1860    /// returned by the iterator. The returned slice has at most `chunk_size-1`
    1861    /// elements.
    1862    ///
    1863    /// # Example
    1864    ///
    1865    /// ```
    1866    /// let slice = ['l', 'o', 'r', 'e', 'm'];
    1867    /// let mut iter = slice.chunks_exact(2);
    1868    /// assert_eq!(iter.remainder(), &['m'][..]);
    1869    /// assert_eq!(iter.next(), Some(&['l', 'o'][..]));
    1870    /// assert_eq!(iter.remainder(), &['m'][..]);
    1871    /// assert_eq!(iter.next(), Some(&['r', 'e'][..]));
    1872    /// assert_eq!(iter.remainder(), &['m'][..]);
    1873    /// assert_eq!(iter.next(), None);
    1874    /// assert_eq!(iter.remainder(), &['m'][..]);
    1875    /// ```
    1876    #[must_use]
    1877    #[stable(feature = "chunks_exact", since = "1.31.0")]
    1878    pub fn remainder(&self) -> &'a [T] {
    1879        self.rem
    1880    }
    1881}
    1882
    1883// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
    1884#[stable(feature = "chunks_exact", since = "1.31.0")]
    1885impl<T> Clone for ChunksExact<'_, T> {
    1886    fn clone(&self) -> Self {
    1887        ChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size }
    1888    }
    1889}
    1890
    1891#[stable(feature = "chunks_exact", since = "1.31.0")]
    1892impl<'a, T> Iterator for ChunksExact<'a, T> {
    1893    type Item = &'a [T];
    1894
    1895    #[inline]
    1896    fn next(&mut self) -> Option<&'a [T]> {
    1897        self.v.split_at_checked(self.chunk_size).and_then(|(chunk, rest)| {
    1898            self.v = rest;
    1899            Some(chunk)
    1900        })
    1901    }
    1902
    1903    #[inline]
    1904    fn size_hint(&self) -> (usize, Option<usize>) {
    1905        let n = self.v.len() / self.chunk_size;
    1906        (n, Some(n))
    1907    }
    1908
    1909    #[inline]
    1910    fn count(self) -> usize {
    1911        self.len()
    1912    }
    1913
    1914    #[inline]
    1915    fn nth(&mut self, n: usize) -> Option<Self::Item> {
    1916        if let Some(start) = n.checked_mul(self.chunk_size)
    1917            && start < self.v.len()
    1918        {
    1919            self.v = &self.v[start..];
    1920            self.next()
    1921        } else {
    1922            self.v = &self.v[..0]; // cheaper than &[]
    1923            None
    1924        }
    1925    }
    1926
    1927    #[inline]
    1928    fn last(mut self) -> Option<Self::Item> {
    1929        self.next_back()
    1930    }
    1931
    1932    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
    1933        let start = idx * self.chunk_size;
    1934        // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
    1935        unsafe { from_raw_parts(self.v.as_ptr().add(start), self.chunk_size) }
    1936    }
    1937}
    1938
    1939#[stable(feature = "chunks_exact", since = "1.31.0")]
    1940impl<'a, T> DoubleEndedIterator for ChunksExact<'a, T> {
    1941    #[inline]
    1942    fn next_back(&mut self) -> Option<&'a [T]> {
    1943        if self.v.len() < self.chunk_size {
    1944            None
    1945        } else {
    1946            let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
    1947            self.v = fst;
    1948            Some(snd)
    1949        }
    1950    }
    1951
    1952    #[inline]
    1953    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
    1954        let len = self.len();
    1955        if n < len {
    1956            let start = (len - 1 - n) * self.chunk_size;
    1957            let end = start + self.chunk_size;
    1958            let nth_back = &self.v[start..end];
    1959            self.v = &self.v[..start];
    1960            Some(nth_back)
    1961        } else {
    1962            self.v = &self.v[..0]; // cheaper than &[]
    1963            None
    1964        }
    1965    }
    1966}
    1967
    1968#[stable(feature = "chunks_exact", since = "1.31.0")]
    1969impl<T> ExactSizeIterator for ChunksExact<'_, T> {
    1970    fn is_empty(&self) -> bool {
    1971        self.v.is_empty()
    1972    }
    1973}
    1974
    1975#[unstable(feature = "trusted_len", issue = "37572")]
    1976unsafe impl<T> TrustedLen for ChunksExact<'_, T> {}
    1977
    1978#[stable(feature = "chunks_exact", since = "1.31.0")]
    1979impl<T> FusedIterator for ChunksExact<'_, T> {}
    1980
    1981#[doc(hidden)]
    1982#[unstable(feature = "trusted_random_access", issue = "none")]
    1983unsafe impl<'a, T> TrustedRandomAccess for ChunksExact<'a, T> {}
    1984
    1985#[doc(hidden)]
    1986#[unstable(feature = "trusted_random_access", issue = "none")]
    1987unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksExact<'a, T> {
    1988    const MAY_HAVE_SIDE_EFFECT: bool = false;
    1989}
    1990
    1991/// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
    1992/// elements at a time), starting at the beginning of the slice.
    1993///
    1994/// When the slice len is not evenly divided by the chunk size, the last up to
    1995/// `chunk_size-1` elements will be omitted but can be retrieved from the
    1996/// [`into_remainder`] function from the iterator.
    1997///
    1998/// This struct is created by the [`chunks_exact_mut`] method on [slices].
    1999///
    2000/// # Example
    2001///
    2002/// ```
    2003/// let mut slice = ['l', 'o', 'r', 'e', 'm'];
    2004/// let iter = slice.chunks_exact_mut(2);
    2005/// ```
    2006///
    2007/// [`chunks_exact_mut`]: slice::chunks_exact_mut
    2008/// [`into_remainder`]: ChunksExactMut::into_remainder
    2009/// [slices]: slice
    2010#[derive(Debug)]
    2011#[stable(feature = "chunks_exact", since = "1.31.0")]
    2012#[must_use = "iterators are lazy and do nothing unless consumed"]
    2013pub struct ChunksExactMut<'a, T: 'a> {
    2014    /// # Safety
    2015    /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
    2016    /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
    2017    /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
    2018    /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
    2019    /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
    2020    v: *mut [T],
    2021    rem: &'a mut [T], // The iterator never yields from here, so this can be unique
    2022    chunk_size: usize,
    2023    _marker: PhantomData<&'a mut T>,
    2024}
    2025
    2026impl<'a, T> ChunksExactMut<'a, T> {
    2027    #[inline]
    2028    pub(super) const fn new(slice: &'a mut [T], chunk_size: usize) -> Self {
    2029        let rem = slice.len() % chunk_size;
    2030        let fst_len = slice.len() - rem;
    2031        // SAFETY: 0 <= fst_len <= slice.len() by construction above
    2032        let (fst, snd) = unsafe { slice.split_at_mut_unchecked(fst_len) };
    2033        Self { v: fst, rem: snd, chunk_size, _marker: PhantomData }
    2034    }
    2035
    2036    /// Returns the remainder of the original slice that is not going to be
    2037    /// returned by the iterator. The returned slice has at most `chunk_size-1`
    2038    /// elements.
    2039    #[must_use = "`self` will be dropped if the result is not used"]
    2040    #[stable(feature = "chunks_exact", since = "1.31.0")]
    2041    pub fn into_remainder(self) -> &'a mut [T] {
    2042        self.rem
    2043    }
    2044}
    2045
    2046#[stable(feature = "chunks_exact", since = "1.31.0")]
    2047impl<'a, T> Iterator for ChunksExactMut<'a, T> {
    2048    type Item = &'a mut [T];
    2049
    2050    #[inline]
    2051    fn next(&mut self) -> Option<&'a mut [T]> {
    2052        // SAFETY: we have `&mut self`, so are allowed to temporarily materialize a mut slice
    2053        unsafe { &mut *self.v }.split_at_mut_checked(self.chunk_size).and_then(|(chunk, rest)| {
    2054            self.v = rest;
    2055            Some(chunk)
    2056        })
    2057    }
    2058
    2059    #[inline]
    2060    fn size_hint(&self) -> (usize, Option<usize>) {
    2061        let n = self.v.len() / self.chunk_size;
    2062        (n, Some(n))
    2063    }
    2064
    2065    #[inline]
    2066    fn count(self) -> usize {
    2067        self.len()
    2068    }
    2069
    2070    #[inline]
    2071    fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
    2072        if let Some(start) = n.checked_mul(self.chunk_size)
    2073            && start < self.v.len()
    2074        {
    2075            // SAFETY: `start < self.v.len()`
    2076            self.v = unsafe { self.v.split_at_mut(start).1 };
    2077            self.next()
    2078        } else {
    2079            self.v = &mut [];
    2080            None
    2081        }
    2082    }
    2083
    2084    #[inline]
    2085    fn last(mut self) -> Option<Self::Item> {
    2086        self.next_back()
    2087    }
    2088
    2089    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
    2090        let start = idx * self.chunk_size;
    2091        // SAFETY: see comments for `Chunks::__iterator_get_unchecked` and `self.v`.
    2092        unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size) }
    2093    }
    2094}
    2095
    2096#[stable(feature = "chunks_exact", since = "1.31.0")]
    2097impl<'a, T> DoubleEndedIterator for ChunksExactMut<'a, T> {
    2098    #[inline]
    2099    fn next_back(&mut self) -> Option<&'a mut [T]> {
    2100        if self.v.len() < self.chunk_size {
    2101            None
    2102        } else {
    2103            // SAFETY: This subtraction is inbounds because of the check above
    2104            let (head, tail) = unsafe { self.v.split_at_mut(self.v.len() - self.chunk_size) };
    2105            self.v = head;
    2106            // SAFETY: Nothing else points to or will point to the contents of this slice.
    2107            Some(unsafe { &mut *tail })
    2108        }
    2109    }
    2110
    2111    #[inline]
    2112    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
    2113        let len = self.len();
    2114        if n < len {
    2115            let start = (len - 1 - n) * self.chunk_size;
    2116            let end = start + self.chunk_size;
    2117            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2118            let (temp, _tail) = unsafe { mem::replace(&mut self.v, &mut []).split_at_mut(end) };
    2119            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2120            let (head, nth_back) = unsafe { temp.split_at_mut(start) };
    2121            self.v = head;
    2122            // SAFETY: Nothing else points to or will point to the contents of this slice.
    2123            Some(unsafe { &mut *nth_back })
    2124        } else {
    2125            self.v = &mut [];
    2126            None
    2127        }
    2128    }
    2129}
    2130
    2131#[stable(feature = "chunks_exact", since = "1.31.0")]
    2132impl<T> ExactSizeIterator for ChunksExactMut<'_, T> {
    2133    fn is_empty(&self) -> bool {
    2134        self.v.is_empty()
    2135    }
    2136}
    2137
    2138#[unstable(feature = "trusted_len", issue = "37572")]
    2139unsafe impl<T> TrustedLen for ChunksExactMut<'_, T> {}
    2140
    2141#[stable(feature = "chunks_exact", since = "1.31.0")]
    2142impl<T> FusedIterator for ChunksExactMut<'_, T> {}
    2143
    2144#[doc(hidden)]
    2145#[unstable(feature = "trusted_random_access", issue = "none")]
    2146unsafe impl<'a, T> TrustedRandomAccess for ChunksExactMut<'a, T> {}
    2147
    2148#[doc(hidden)]
    2149#[unstable(feature = "trusted_random_access", issue = "none")]
    2150unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksExactMut<'a, T> {
    2151    const MAY_HAVE_SIDE_EFFECT: bool = false;
    2152}
    2153
    2154#[stable(feature = "chunks_exact", since = "1.31.0")]
    2155unsafe impl<T> Send for ChunksExactMut<'_, T> where T: Send {}
    2156
    2157#[stable(feature = "chunks_exact", since = "1.31.0")]
    2158unsafe impl<T> Sync for ChunksExactMut<'_, T> where T: Sync {}
    2159
    2160/// A windowed iterator over a slice in overlapping chunks (`N` elements at a
    2161/// time), starting at the beginning of the slice
    2162///
    2163/// This struct is created by the [`array_windows`] method on [slices].
    2164///
    2165/// # Example
    2166///
    2167/// ```
    2168/// let slice = [0, 1, 2, 3];
    2169/// let mut iter = slice.array_windows::<2>();
    2170/// assert_eq!(iter.next(), Some(&[0, 1]));
    2171/// assert_eq!(iter.next(), Some(&[1, 2]));
    2172/// assert_eq!(iter.next(), Some(&[2, 3]));
    2173/// assert_eq!(iter.next(), None);
    2174/// ```
    2175///
    2176/// [`array_windows`]: slice::array_windows
    2177/// [slices]: slice
    2178#[derive(Debug)]
    2179#[stable(feature = "array_windows", since = "1.94.0")]
    2180#[must_use = "iterators are lazy and do nothing unless consumed"]
    2181pub struct ArrayWindows<'a, T: 'a, const N: usize> {
    2182    v: &'a [T],
    2183}
    2184
    2185impl<'a, T: 'a, const N: usize> ArrayWindows<'a, T, N> {
    2186    #[inline]
    2187    pub(super) const fn new(slice: &'a [T]) -> Self {
    2188        Self { v: slice }
    2189    }
    2190}
    2191
    2192// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
    2193#[stable(feature = "array_windows", since = "1.94.0")]
    2194impl<T, const N: usize> Clone for ArrayWindows<'_, T, N> {
    2195    fn clone(&self) -> Self {
    2196        Self { v: self.v }
    2197    }
    2198}
    2199
    2200#[stable(feature = "array_windows", since = "1.94.0")]
    2201impl<'a, T, const N: usize> Iterator for ArrayWindows<'a, T, N> {
    2202    type Item = &'a [T; N];
    2203
    2204    #[inline]
    2205    fn next(&mut self) -> Option<Self::Item> {
    2206        let ret = self.v.first_chunk();
    2207        if ret.is_some() {
    2208            self.v = &self.v[1..];
    2209        }
    2210        ret
    2211    }
    2212
    2213    #[inline]
    2214    fn size_hint(&self) -> (usize, Option<usize>) {
    2215        let size = self.v.len().saturating_sub(N - 1);
    2216        (size, Some(size))
    2217    }
    2218
    2219    #[inline]
    2220    fn count(self) -> usize {
    2221        self.len()
    2222    }
    2223
    2224    #[inline]
    2225    fn nth(&mut self, n: usize) -> Option<Self::Item> {
    2226        let idx = n.min(self.v.len());
    2227        self.v = &self.v[idx..];
    2228        self.next()
    2229    }
    2230
    2231    #[inline]
    2232    fn last(self) -> Option<Self::Item> {
    2233        self.v.last_chunk()
    2234    }
    2235
    2236    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
    2237        // SAFETY: since the caller guarantees that `idx` is in bounds,
    2238        // which means that `idx` cannot overflow an `isize`, and the
    2239        // "slice" created by `cast_array` is a subslice of `self.v`
    2240        // thus is guaranteed to be valid for the lifetime `'a` of `self.v`.
    2241        unsafe { &*self.v.as_ptr().add(idx).cast_array() }
    2242    }
    2243}
    2244
    2245#[stable(feature = "array_windows", since = "1.94.0")]
    2246impl<'a, T, const N: usize> DoubleEndedIterator for ArrayWindows<'a, T, N> {
    2247    #[inline]
    2248    fn next_back(&mut self) -> Option<&'a [T; N]> {
    2249        let ret = self.v.last_chunk();
    2250        if ret.is_some() {
    2251            self.v = &self.v[..self.v.len() - 1];
    2252        }
    2253        ret
    2254    }
    2255
    2256    #[inline]
    2257    fn nth_back(&mut self, n: usize) -> Option<&'a [T; N]> {
    2258        let idx = self.v.len().saturating_sub(n);
    2259        self.v = &self.v[..idx];
    2260        self.next_back()
    2261    }
    2262}
    2263
    2264#[stable(feature = "array_windows", since = "1.94.0")]
    2265impl<T, const N: usize> ExactSizeIterator for ArrayWindows<'_, T, N> {
    2266    fn is_empty(&self) -> bool {
    2267        self.v.len() < N
    2268    }
    2269}
    2270
    2271#[unstable(feature = "trusted_len", issue = "37572")]
    2272unsafe impl<T, const N: usize> TrustedLen for ArrayWindows<'_, T, N> {}
    2273
    2274#[stable(feature = "array_windows", since = "1.94.0")]
    2275impl<T, const N: usize> FusedIterator for ArrayWindows<'_, T, N> {}
    2276
    2277#[doc(hidden)]
    2278#[unstable(feature = "trusted_random_access", issue = "none")]
    2279unsafe impl<T, const N: usize> TrustedRandomAccess for ArrayWindows<'_, T, N> {}
    2280
    2281#[doc(hidden)]
    2282#[unstable(feature = "trusted_random_access", issue = "none")]
    2283unsafe impl<T, const N: usize> TrustedRandomAccessNoCoerce for ArrayWindows<'_, T, N> {
    2284    const MAY_HAVE_SIDE_EFFECT: bool = false;
    2285}
    2286
    2287/// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
    2288/// time), starting at the end of the slice.
    2289///
    2290/// When the slice len is not evenly divided by the chunk size, the last slice
    2291/// of the iteration will be the remainder.
    2292///
    2293/// This struct is created by the [`rchunks`] method on [slices].
    2294///
    2295/// # Example
    2296///
    2297/// ```
    2298/// let slice = ['l', 'o', 'r', 'e', 'm'];
    2299/// let mut iter = slice.rchunks(2);
    2300/// assert_eq!(iter.next(), Some(&['e', 'm'][..]));
    2301/// assert_eq!(iter.next(), Some(&['o', 'r'][..]));
    2302/// assert_eq!(iter.next(), Some(&['l'][..]));
    2303/// assert_eq!(iter.next(), None);
    2304/// ```
    2305///
    2306/// [`rchunks`]: slice::rchunks
    2307/// [slices]: slice
    2308#[derive(Debug)]
    2309#[stable(feature = "rchunks", since = "1.31.0")]
    2310#[must_use = "iterators are lazy and do nothing unless consumed"]
    2311pub struct RChunks<'a, T: 'a> {
    2312    v: &'a [T],
    2313    chunk_size: usize,
    2314}
    2315
    2316impl<'a, T: 'a> RChunks<'a, T> {
    2317    #[inline]
    2318    pub(super) const fn new(slice: &'a [T], size: usize) -> Self {
    2319        Self { v: slice, chunk_size: size }
    2320    }
    2321}
    2322
    2323// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
    2324#[stable(feature = "rchunks", since = "1.31.0")]
    2325impl<T> Clone for RChunks<'_, T> {
    2326    fn clone(&self) -> Self {
    2327        RChunks { v: self.v, chunk_size: self.chunk_size }
    2328    }
    2329}
    2330
    2331#[stable(feature = "rchunks", since = "1.31.0")]
    2332impl<'a, T> Iterator for RChunks<'a, T> {
    2333    type Item = &'a [T];
    2334
    2335    #[inline]
    2336    fn next(&mut self) -> Option<&'a [T]> {
    2337        if self.v.is_empty() {
    2338            None
    2339        } else {
    2340            let idx = self.v.len().saturating_sub(self.chunk_size);
    2341            // SAFETY: self.chunk_size() > 0, so 0 <= idx < self.v.len().
    2342            // Thus `idx` is in-bounds for `self.v` and can be used as a valid argument for `split_at_mut_unchecked`.
    2343            let (rest, chunk) = unsafe { self.v.split_at_unchecked(idx) };
    2344            self.v = rest;
    2345            Some(chunk)
    2346        }
    2347    }
    2348
    2349    #[inline]
    2350    fn size_hint(&self) -> (usize, Option<usize>) {
    2351        if self.v.is_empty() {
    2352            (0, Some(0))
    2353        } else {
    2354            let n = self.v.len().div_ceil(self.chunk_size);
    2355            (n, Some(n))
    2356        }
    2357    }
    2358
    2359    #[inline]
    2360    fn count(self) -> usize {
    2361        self.len()
    2362    }
    2363
    2364    #[inline]
    2365    fn nth(&mut self, n: usize) -> Option<Self::Item> {
    2366        if let Some(end) = n.checked_mul(self.chunk_size)
    2367            && end < self.v.len()
    2368        {
    2369            let end = self.v.len() - end;
    2370            let rest = &self.v[..end];
    2371            let (rest, chunk) = rest.split_at(end.saturating_sub(self.chunk_size));
    2372            self.v = rest;
    2373            Some(chunk)
    2374        } else {
    2375            self.v = &self.v[..0]; // cheaper than &[]
    2376            None
    2377        }
    2378    }
    2379
    2380    #[inline]
    2381    fn last(self) -> Option<Self::Item> {
    2382        if self.v.is_empty() {
    2383            None
    2384        } else {
    2385            let rem = self.v.len() % self.chunk_size;
    2386            let end = if rem == 0 { self.chunk_size } else { rem };
    2387            Some(&self.v[0..end])
    2388        }
    2389    }
    2390
    2391    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
    2392        let end = self.v.len() - idx * self.chunk_size;
    2393        let start = end.saturating_sub(self.chunk_size);
    2394        // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
    2395        unsafe { from_raw_parts(self.v.as_ptr().add(start), end - start) }
    2396    }
    2397}
    2398
    2399#[stable(feature = "rchunks", since = "1.31.0")]
    2400impl<'a, T> DoubleEndedIterator for RChunks<'a, T> {
    2401    #[inline]
    2402    fn next_back(&mut self) -> Option<&'a [T]> {
    2403        if self.v.is_empty() {
    2404            None
    2405        } else {
    2406            let remainder = self.v.len() % self.chunk_size;
    2407            let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
    2408            // SAFETY: similar to Chunks::next_back
    2409            let (fst, snd) = unsafe { self.v.split_at_unchecked(chunksz) };
    2410            self.v = snd;
    2411            Some(fst)
    2412        }
    2413    }
    2414
    2415    #[inline]
    2416    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
    2417        let len = self.len();
    2418        if n < len {
    2419            let offset_from_end = (len - 1 - n) * self.chunk_size;
    2420            let end = self.v.len() - offset_from_end;
    2421            let start = end.saturating_sub(self.chunk_size);
    2422            let nth_back = &self.v[start..end];
    2423            self.v = &self.v[end..];
    2424            Some(nth_back)
    2425        } else {
    2426            self.v = &self.v[..0]; // cheaper than &[]
    2427            None
    2428        }
    2429    }
    2430}
    2431
    2432#[stable(feature = "rchunks", since = "1.31.0")]
    2433impl<T> ExactSizeIterator for RChunks<'_, T> {}
    2434
    2435#[unstable(feature = "trusted_len", issue = "37572")]
    2436unsafe impl<T> TrustedLen for RChunks<'_, T> {}
    2437
    2438#[stable(feature = "rchunks", since = "1.31.0")]
    2439impl<T> FusedIterator for RChunks<'_, T> {}
    2440
    2441#[doc(hidden)]
    2442#[unstable(feature = "trusted_random_access", issue = "none")]
    2443unsafe impl<'a, T> TrustedRandomAccess for RChunks<'a, T> {}
    2444
    2445#[doc(hidden)]
    2446#[unstable(feature = "trusted_random_access", issue = "none")]
    2447unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunks<'a, T> {
    2448    const MAY_HAVE_SIDE_EFFECT: bool = false;
    2449}
    2450
    2451/// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
    2452/// elements at a time), starting at the end of the slice.
    2453///
    2454/// When the slice len is not evenly divided by the chunk size, the last slice
    2455/// of the iteration will be the remainder.
    2456///
    2457/// This struct is created by the [`rchunks_mut`] method on [slices].
    2458///
    2459/// # Example
    2460///
    2461/// ```
    2462/// let mut slice = ['l', 'o', 'r', 'e', 'm'];
    2463/// let iter = slice.rchunks_mut(2);
    2464/// ```
    2465///
    2466/// [`rchunks_mut`]: slice::rchunks_mut
    2467/// [slices]: slice
    2468#[derive(Debug)]
    2469#[stable(feature = "rchunks", since = "1.31.0")]
    2470#[must_use = "iterators are lazy and do nothing unless consumed"]
    2471pub struct RChunksMut<'a, T: 'a> {
    2472    /// # Safety
    2473    /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
    2474    /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
    2475    /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
    2476    /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
    2477    /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
    2478    v: *mut [T],
    2479    chunk_size: usize,
    2480    _marker: PhantomData<&'a mut T>,
    2481}
    2482
    2483impl<'a, T: 'a> RChunksMut<'a, T> {
    2484    #[inline]
    2485    pub(super) const fn new(slice: &'a mut [T], size: usize) -> Self {
    2486        Self { v: slice, chunk_size: size, _marker: PhantomData }
    2487    }
    2488}
    2489
    2490#[stable(feature = "rchunks", since = "1.31.0")]
    2491impl<'a, T> Iterator for RChunksMut<'a, T> {
    2492    type Item = &'a mut [T];
    2493
    2494    #[inline]
    2495    fn next(&mut self) -> Option<&'a mut [T]> {
    2496        if self.v.is_empty() {
    2497            None
    2498        } else {
    2499            let idx = self.v.len().saturating_sub(self.chunk_size);
    2500            // SAFETY: self.chunk_size() > 0, so 0 <= idx < self.v.len().
    2501            // Thus `idx` is in-bounds for `self.v` and can be used as a valid argument for `split_at_mut_unchecked`.
    2502            let (rest, chunk) = unsafe { self.v.split_at_mut_unchecked(idx) };
    2503            self.v = rest;
    2504            // SAFETY: Nothing else points to or will point to the contents of this slice.
    2505            Some(unsafe { &mut *chunk })
    2506        }
    2507    }
    2508
    2509    #[inline]
    2510    fn size_hint(&self) -> (usize, Option<usize>) {
    2511        if self.v.is_empty() {
    2512            (0, Some(0))
    2513        } else {
    2514            let n = self.v.len().div_ceil(self.chunk_size);
    2515            (n, Some(n))
    2516        }
    2517    }
    2518
    2519    #[inline]
    2520    fn count(self) -> usize {
    2521        self.len()
    2522    }
    2523
    2524    #[inline]
    2525    fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
    2526        if let Some(end) = n.checked_mul(self.chunk_size)
    2527            && end < self.v.len()
    2528        {
    2529            let end = self.v.len() - end;
    2530            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2531            let (rest, _) = unsafe { self.v.split_at_mut(end) };
    2532            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2533            let (rest, chunk) = unsafe { rest.split_at_mut(end.saturating_sub(self.chunk_size)) };
    2534            self.v = rest;
    2535            // SAFETY: Nothing else points to or will point to the contents of this slice.
    2536            Some(unsafe { &mut *chunk })
    2537        } else {
    2538            self.v = &mut [];
    2539            None
    2540        }
    2541    }
    2542
    2543    #[inline]
    2544    fn last(self) -> Option<Self::Item> {
    2545        if self.v.is_empty() {
    2546            None
    2547        } else {
    2548            let rem = self.v.len() % self.chunk_size;
    2549            let end = if rem == 0 { self.chunk_size } else { rem };
    2550            // SAFETY: Nothing else points to or will point to the contents of this slice.
    2551            Some(unsafe { &mut *self.v.get_unchecked_mut(0..end) })
    2552        }
    2553    }
    2554
    2555    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
    2556        let end = self.v.len() - idx * self.chunk_size;
    2557        let start = end.saturating_sub(self.chunk_size);
    2558        // SAFETY: see comments for `RChunks::__iterator_get_unchecked` and
    2559        // `ChunksMut::__iterator_get_unchecked`, `self.v`.
    2560        unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), end - start) }
    2561    }
    2562}
    2563
    2564#[stable(feature = "rchunks", since = "1.31.0")]
    2565impl<'a, T> DoubleEndedIterator for RChunksMut<'a, T> {
    2566    #[inline]
    2567    fn next_back(&mut self) -> Option<&'a mut [T]> {
    2568        if self.v.is_empty() {
    2569            None
    2570        } else {
    2571            let remainder = self.v.len() % self.chunk_size;
    2572            let sz = if remainder != 0 { remainder } else { self.chunk_size };
    2573            // SAFETY: Similar to `Chunks::next_back`
    2574            let (head, tail) = unsafe { self.v.split_at_mut_unchecked(sz) };
    2575            self.v = tail;
    2576            // SAFETY: Nothing else points to or will point to the contents of this slice.
    2577            Some(unsafe { &mut *head })
    2578        }
    2579    }
    2580
    2581    #[inline]
    2582    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
    2583        let len = self.len();
    2584        if n < len {
    2585            // can't underflow because `n < len`
    2586            let offset_from_end = (len - 1 - n) * self.chunk_size;
    2587            let end = self.v.len() - offset_from_end;
    2588            let start = end.saturating_sub(self.chunk_size);
    2589            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2590            let (tmp, tail) = unsafe { self.v.split_at_mut(end) };
    2591            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2592            let (_, nth_back) = unsafe { tmp.split_at_mut(start) };
    2593            self.v = tail;
    2594            // SAFETY: Nothing else points to or will point to the contents of this slice.
    2595            Some(unsafe { &mut *nth_back })
    2596        } else {
    2597            self.v = &mut [];
    2598            None
    2599        }
    2600    }
    2601}
    2602
    2603#[stable(feature = "rchunks", since = "1.31.0")]
    2604impl<T> ExactSizeIterator for RChunksMut<'_, T> {}
    2605
    2606#[unstable(feature = "trusted_len", issue = "37572")]
    2607unsafe impl<T> TrustedLen for RChunksMut<'_, T> {}
    2608
    2609#[stable(feature = "rchunks", since = "1.31.0")]
    2610impl<T> FusedIterator for RChunksMut<'_, T> {}
    2611
    2612#[doc(hidden)]
    2613#[unstable(feature = "trusted_random_access", issue = "none")]
    2614unsafe impl<'a, T> TrustedRandomAccess for RChunksMut<'a, T> {}
    2615
    2616#[doc(hidden)]
    2617#[unstable(feature = "trusted_random_access", issue = "none")]
    2618unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksMut<'a, T> {
    2619    const MAY_HAVE_SIDE_EFFECT: bool = false;
    2620}
    2621
    2622#[stable(feature = "rchunks", since = "1.31.0")]
    2623unsafe impl<T> Send for RChunksMut<'_, T> where T: Send {}
    2624
    2625#[stable(feature = "rchunks", since = "1.31.0")]
    2626unsafe impl<T> Sync for RChunksMut<'_, T> where T: Sync {}
    2627
    2628/// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
    2629/// time), starting at the end of the slice.
    2630///
    2631/// When the slice len is not evenly divided by the chunk size, the last
    2632/// up to `chunk_size-1` elements will be omitted but can be retrieved from
    2633/// the [`remainder`] function from the iterator.
    2634///
    2635/// This struct is created by the [`rchunks_exact`] method on [slices].
    2636///
    2637/// # Example
    2638///
    2639/// ```
    2640/// let slice = ['l', 'o', 'r', 'e', 'm'];
    2641/// let mut iter = slice.rchunks_exact(2);
    2642/// assert_eq!(iter.next(), Some(&['e', 'm'][..]));
    2643/// assert_eq!(iter.next(), Some(&['o', 'r'][..]));
    2644/// assert_eq!(iter.next(), None);
    2645/// ```
    2646///
    2647/// [`rchunks_exact`]: slice::rchunks_exact
    2648/// [`remainder`]: RChunksExact::remainder
    2649/// [slices]: slice
    2650#[derive(Debug)]
    2651#[stable(feature = "rchunks", since = "1.31.0")]
    2652#[must_use = "iterators are lazy and do nothing unless consumed"]
    2653pub struct RChunksExact<'a, T: 'a> {
    2654    v: &'a [T],
    2655    rem: &'a [T],
    2656    chunk_size: usize,
    2657}
    2658
    2659impl<'a, T> RChunksExact<'a, T> {
    2660    #[inline]
    2661    pub(super) const fn new(slice: &'a [T], chunk_size: usize) -> Self {
    2662        let rem = slice.len() % chunk_size;
    2663        // SAFETY: 0 <= rem <= slice.len() by construction above
    2664        let (fst, snd) = unsafe { slice.split_at_unchecked(rem) };
    2665        Self { v: snd, rem: fst, chunk_size }
    2666    }
    2667
    2668    /// Returns the remainder of the original slice that is not going to be
    2669    /// returned by the iterator. The returned slice has at most `chunk_size-1`
    2670    /// elements.
    2671    ///
    2672    /// # Example
    2673    ///
    2674    /// ```
    2675    /// let slice = ['l', 'o', 'r', 'e', 'm'];
    2676    /// let mut iter = slice.rchunks_exact(2);
    2677    /// assert_eq!(iter.remainder(), &['l'][..]);
    2678    /// assert_eq!(iter.next(), Some(&['e', 'm'][..]));
    2679    /// assert_eq!(iter.remainder(), &['l'][..]);
    2680    /// assert_eq!(iter.next(), Some(&['o', 'r'][..]));
    2681    /// assert_eq!(iter.remainder(), &['l'][..]);
    2682    /// assert_eq!(iter.next(), None);
    2683    /// assert_eq!(iter.remainder(), &['l'][..]);
    2684    /// ```
    2685    #[must_use]
    2686    #[stable(feature = "rchunks", since = "1.31.0")]
    2687    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
    2688    pub const fn remainder(&self) -> &'a [T] {
    2689        self.rem
    2690    }
    2691}
    2692
    2693// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
    2694#[stable(feature = "rchunks", since = "1.31.0")]
    2695impl<'a, T> Clone for RChunksExact<'a, T> {
    2696    fn clone(&self) -> RChunksExact<'a, T> {
    2697        RChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size }
    2698    }
    2699}
    2700
    2701#[stable(feature = "rchunks", since = "1.31.0")]
    2702impl<'a, T> Iterator for RChunksExact<'a, T> {
    2703    type Item = &'a [T];
    2704
    2705    #[inline]
    2706    fn next(&mut self) -> Option<&'a [T]> {
    2707        if self.v.len() < self.chunk_size {
    2708            None
    2709        } else {
    2710            let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
    2711            self.v = fst;
    2712            Some(snd)
    2713        }
    2714    }
    2715
    2716    #[inline]
    2717    fn size_hint(&self) -> (usize, Option<usize>) {
    2718        let n = self.v.len() / self.chunk_size;
    2719        (n, Some(n))
    2720    }
    2721
    2722    #[inline]
    2723    fn count(self) -> usize {
    2724        self.len()
    2725    }
    2726
    2727    #[inline]
    2728    fn nth(&mut self, n: usize) -> Option<Self::Item> {
    2729        if let Some(end) = n.checked_mul(self.chunk_size)
    2730            && end < self.v.len()
    2731        {
    2732            self.v = &self.v[..self.v.len() - end];
    2733            self.next()
    2734        } else {
    2735            self.v = &self.v[..0]; // cheaper than &[]
    2736            None
    2737        }
    2738    }
    2739
    2740    #[inline]
    2741    fn last(mut self) -> Option<Self::Item> {
    2742        self.next_back()
    2743    }
    2744
    2745    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
    2746        let end = self.v.len() - idx * self.chunk_size;
    2747        let start = end - self.chunk_size;
    2748        // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
    2749        unsafe { from_raw_parts(self.v.as_ptr().add(start), self.chunk_size) }
    2750    }
    2751}
    2752
    2753#[stable(feature = "rchunks", since = "1.31.0")]
    2754impl<'a, T> DoubleEndedIterator for RChunksExact<'a, T> {
    2755    #[inline]
    2756    fn next_back(&mut self) -> Option<&'a [T]> {
    2757        if self.v.len() < self.chunk_size {
    2758            None
    2759        } else {
    2760            let (fst, snd) = self.v.split_at(self.chunk_size);
    2761            self.v = snd;
    2762            Some(fst)
    2763        }
    2764    }
    2765
    2766    #[inline]
    2767    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
    2768        let len = self.len();
    2769        if n < len {
    2770            // now that we know that `n` corresponds to a chunk,
    2771            // none of these operations can underflow/overflow
    2772            let offset = (len - n) * self.chunk_size;
    2773            let start = self.v.len() - offset;
    2774            let end = start + self.chunk_size;
    2775            let nth_back = &self.v[start..end];
    2776            self.v = &self.v[end..];
    2777            Some(nth_back)
    2778        } else {
    2779            self.v = &self.v[..0]; // cheaper than &[]
    2780            None
    2781        }
    2782    }
    2783}
    2784
    2785#[stable(feature = "rchunks", since = "1.31.0")]
    2786impl<'a, T> ExactSizeIterator for RChunksExact<'a, T> {
    2787    fn is_empty(&self) -> bool {
    2788        self.v.is_empty()
    2789    }
    2790}
    2791
    2792#[unstable(feature = "trusted_len", issue = "37572")]
    2793unsafe impl<T> TrustedLen for RChunksExact<'_, T> {}
    2794
    2795#[stable(feature = "rchunks", since = "1.31.0")]
    2796impl<T> FusedIterator for RChunksExact<'_, T> {}
    2797
    2798#[doc(hidden)]
    2799#[unstable(feature = "trusted_random_access", issue = "none")]
    2800unsafe impl<'a, T> TrustedRandomAccess for RChunksExact<'a, T> {}
    2801
    2802#[doc(hidden)]
    2803#[unstable(feature = "trusted_random_access", issue = "none")]
    2804unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksExact<'a, T> {
    2805    const MAY_HAVE_SIDE_EFFECT: bool = false;
    2806}
    2807
    2808/// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
    2809/// elements at a time), starting at the end of the slice.
    2810///
    2811/// When the slice len is not evenly divided by the chunk size, the last up to
    2812/// `chunk_size-1` elements will be omitted but can be retrieved from the
    2813/// [`into_remainder`] function from the iterator.
    2814///
    2815/// This struct is created by the [`rchunks_exact_mut`] method on [slices].
    2816///
    2817/// # Example
    2818///
    2819/// ```
    2820/// let mut slice = ['l', 'o', 'r', 'e', 'm'];
    2821/// let iter = slice.rchunks_exact_mut(2);
    2822/// ```
    2823///
    2824/// [`rchunks_exact_mut`]: slice::rchunks_exact_mut
    2825/// [`into_remainder`]: RChunksExactMut::into_remainder
    2826/// [slices]: slice
    2827#[derive(Debug)]
    2828#[stable(feature = "rchunks", since = "1.31.0")]
    2829#[must_use = "iterators are lazy and do nothing unless consumed"]
    2830pub struct RChunksExactMut<'a, T: 'a> {
    2831    /// # Safety
    2832    /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
    2833    /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
    2834    /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
    2835    /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
    2836    /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
    2837    v: *mut [T],
    2838    rem: &'a mut [T],
    2839    chunk_size: usize,
    2840}
    2841
    2842impl<'a, T> RChunksExactMut<'a, T> {
    2843    #[inline]
    2844    pub(super) const fn new(slice: &'a mut [T], chunk_size: usize) -> Self {
    2845        let rem = slice.len() % chunk_size;
    2846        // SAFETY: 0 <= rem <= slice.len() by construction above
    2847        let (fst, snd) = unsafe { slice.split_at_mut_unchecked(rem) };
    2848        Self { v: snd, rem: fst, chunk_size }
    2849    }
    2850
    2851    /// Returns the remainder of the original slice that is not going to be
    2852    /// returned by the iterator. The returned slice has at most `chunk_size-1`
    2853    /// elements.
    2854    #[must_use = "`self` will be dropped if the result is not used"]
    2855    #[stable(feature = "rchunks", since = "1.31.0")]
    2856    #[rustc_const_unstable(feature = "const_slice_make_iter", issue = "137737")]
    2857    pub const fn into_remainder(self) -> &'a mut [T] {
    2858        self.rem
    2859    }
    2860}
    2861
    2862#[stable(feature = "rchunks", since = "1.31.0")]
    2863impl<'a, T> Iterator for RChunksExactMut<'a, T> {
    2864    type Item = &'a mut [T];
    2865
    2866    #[inline]
    2867    fn next(&mut self) -> Option<&'a mut [T]> {
    2868        if self.v.len() < self.chunk_size {
    2869            None
    2870        } else {
    2871            let len = self.v.len();
    2872            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2873            let (head, tail) = unsafe { self.v.split_at_mut(len - self.chunk_size) };
    2874            self.v = head;
    2875            // SAFETY: Nothing else points to or will point to the contents of this slice.
    2876            Some(unsafe { &mut *tail })
    2877        }
    2878    }
    2879
    2880    #[inline]
    2881    fn size_hint(&self) -> (usize, Option<usize>) {
    2882        let n = self.v.len() / self.chunk_size;
    2883        (n, Some(n))
    2884    }
    2885
    2886    #[inline]
    2887    fn count(self) -> usize {
    2888        self.len()
    2889    }
    2890
    2891    #[inline]
    2892    fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
    2893        if let Some(end) = n.checked_mul(self.chunk_size)
    2894            && end < self.v.len()
    2895        {
    2896            let idx = self.v.len() - end;
    2897            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2898            let (fst, _) = unsafe { self.v.split_at_mut(idx) };
    2899            self.v = fst;
    2900            self.next()
    2901        } else {
    2902            self.v = &mut [];
    2903            None
    2904        }
    2905    }
    2906
    2907    #[inline]
    2908    fn last(mut self) -> Option<Self::Item> {
    2909        self.next_back()
    2910    }
    2911
    2912    unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
    2913        let end = self.v.len() - idx * self.chunk_size;
    2914        let start = end - self.chunk_size;
    2915        // SAFETY: see comments for `RChunksMut::__iterator_get_unchecked` and `self.v`.
    2916        unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size) }
    2917    }
    2918}
    2919
    2920#[stable(feature = "rchunks", since = "1.31.0")]
    2921impl<'a, T> DoubleEndedIterator for RChunksExactMut<'a, T> {
    2922    #[inline]
    2923    fn next_back(&mut self) -> Option<&'a mut [T]> {
    2924        if self.v.len() < self.chunk_size {
    2925            None
    2926        } else {
    2927            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2928            let (head, tail) = unsafe { self.v.split_at_mut(self.chunk_size) };
    2929            self.v = tail;
    2930            // SAFETY: Nothing else points to or will point to the contents of this slice.
    2931            Some(unsafe { &mut *head })
    2932        }
    2933    }
    2934
    2935    #[inline]
    2936    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
    2937        let len = self.len();
    2938        if n < len {
    2939            // now that we know that `n` corresponds to a chunk,
    2940            // none of these operations can underflow/overflow
    2941            let offset = (len - n) * self.chunk_size;
    2942            let start = self.v.len() - offset;
    2943            let end = start + self.chunk_size;
    2944            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2945            let (tmp, tail) = unsafe { self.v.split_at_mut(end) };
    2946            // SAFETY: The self.v contract ensures that any split_at_mut is valid.
    2947            let (_, nth_back) = unsafe { tmp.split_at_mut(start) };
    2948            self.v = tail;
    2949            // SAFETY: Nothing else points to or will point to the contents of this slice.
    2950            Some(unsafe { &mut *nth_back })
    2951        } else {
    2952            self.v = &mut [];
    2953            None
    2954        }
    2955    }
    2956}
    2957
    2958#[stable(feature = "rchunks", since = "1.31.0")]
    2959impl<T> ExactSizeIterator for RChunksExactMut<'_, T> {
    2960    fn is_empty(&self) -> bool {
    2961        self.v.is_empty()
    2962    }
    2963}
    2964
    2965#[unstable(feature = "trusted_len", issue = "37572")]
    2966unsafe impl<T> TrustedLen for RChunksExactMut<'_, T> {}
    2967
    2968#[stable(feature = "rchunks", since = "1.31.0")]
    2969impl<T> FusedIterator for RChunksExactMut<'_, T> {}
    2970
    2971#[doc(hidden)]
    2972#[unstable(feature = "trusted_random_access", issue = "none")]
    2973unsafe impl<'a, T> TrustedRandomAccess for RChunksExactMut<'a, T> {}
    2974
    2975#[doc(hidden)]
    2976#[unstable(feature = "trusted_random_access", issue = "none")]
    2977unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksExactMut<'a, T> {
    2978    const MAY_HAVE_SIDE_EFFECT: bool = false;
    2979}
    2980
    2981#[stable(feature = "rchunks", since = "1.31.0")]
    2982unsafe impl<T> Send for RChunksExactMut<'_, T> where T: Send {}
    2983
    2984#[stable(feature = "rchunks", since = "1.31.0")]
    2985unsafe impl<T> Sync for RChunksExactMut<'_, T> where T: Sync {}
    2986
    2987#[doc(hidden)]
    2988#[unstable(feature = "trusted_random_access", issue = "none")]
    2989unsafe impl<'a, T> TrustedRandomAccess for Iter<'a, T> {}
    2990
    2991#[doc(hidden)]
    2992#[unstable(feature = "trusted_random_access", issue = "none")]
    2993unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Iter<'a, T> {
    2994    const MAY_HAVE_SIDE_EFFECT: bool = false;
    2995}
    2996
    2997#[doc(hidden)]
    2998#[unstable(feature = "trusted_random_access", issue = "none")]
    2999unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> {}
    3000
    3001#[doc(hidden)]
    3002#[unstable(feature = "trusted_random_access", issue = "none")]
    3003unsafe impl<'a, T> TrustedRandomAccessNoCoerce for IterMut<'a, T> {
    3004    const MAY_HAVE_SIDE_EFFECT: bool = false;
    3005}
    3006
    3007/// An iterator over slice in (non-overlapping) chunks separated by a predicate.
    3008///
    3009/// This struct is created by the [`chunk_by`] method on [slices].
    3010///
    3011/// [`chunk_by`]: slice::chunk_by
    3012/// [slices]: slice
    3013#[stable(feature = "slice_group_by", since = "1.77.0")]
    3014#[must_use = "iterators are lazy and do nothing unless consumed"]
    3015pub struct ChunkBy<'a, T: 'a, P> {
    3016    slice: &'a [T],
    3017    predicate: P,
    3018}
    3019
    3020#[stable(feature = "slice_group_by", since = "1.77.0")]
    3021impl<'a, T: 'a, P> ChunkBy<'a, T, P> {
    3022    pub(super) const fn new(slice: &'a [T], predicate: P) -> Self {
    3023        ChunkBy { slice, predicate }
    3024    }
    3025}
    3026
    3027#[stable(feature = "slice_group_by", since = "1.77.0")]
    3028impl<'a, T: 'a, P> Iterator for ChunkBy<'a, T, P>
    3029where
    3030    P: FnMut(&T, &T) -> bool,
    3031{
    3032    type Item = &'a [T];
    3033
    3034    #[inline]
    3035    fn next(&mut self) -> Option<Self::Item> {
    3036        if self.slice.is_empty() {
    3037            None
    3038        } else {
    3039            let mut len = 1;
    3040            let mut iter = self.slice.windows(2);
    3041            while let Some([l, r]) = iter.next() {
    3042                if (self.predicate)(l, r) { len += 1 } else { break }
    3043            }
    3044            let (head, tail) = self.slice.split_at(len);
    3045            self.slice = tail;
    3046            Some(head)
    3047        }
    3048    }
    3049
    3050    #[inline]
    3051    fn size_hint(&self) -> (usize, Option<usize>) {
    3052        if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) }
    3053    }
    3054
    3055    #[inline]
    3056    fn last(mut self) -> Option<Self::Item> {
    3057        self.next_back()
    3058    }
    3059}
    3060
    3061#[stable(feature = "slice_group_by", since = "1.77.0")]
    3062impl<'a, T: 'a, P> DoubleEndedIterator for ChunkBy<'a, T, P>
    3063where
    3064    P: FnMut(&T, &T) -> bool,
    3065{
    3066    #[inline]
    3067    fn next_back(&mut self) -> Option<Self::Item> {
    3068        if self.slice.is_empty() {
    3069            None
    3070        } else {
    3071            let mut len = 1;
    3072            let mut iter = self.slice.windows(2);
    3073            while let Some([l, r]) = iter.next_back() {
    3074                if (self.predicate)(l, r) { len += 1 } else { break }
    3075            }
    3076            let (head, tail) = self.slice.split_at(self.slice.len() - len);
    3077            self.slice = head;
    3078            Some(tail)
    3079        }
    3080    }
    3081}
    3082
    3083#[stable(feature = "slice_group_by", since = "1.77.0")]
    3084impl<'a, T: 'a, P> FusedIterator for ChunkBy<'a, T, P> where P: FnMut(&T, &T) -> bool {}
    3085
    3086#[stable(feature = "slice_group_by_clone", since = "1.89.0")]
    3087impl<'a, T: 'a, P: Clone> Clone for ChunkBy<'a, T, P> {
    3088    fn clone(&self) -> Self {
    3089        Self { slice: self.slice, predicate: self.predicate.clone() }
    3090    }
    3091}
    3092
    3093#[stable(feature = "slice_group_by", since = "1.77.0")]
    3094impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for ChunkBy<'a, T, P> {
    3095    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    3096        f.debug_struct("ChunkBy").field("slice", &self.slice).finish()
    3097    }
    3098}
    3099
    3100/// An iterator over slice in (non-overlapping) mutable chunks separated
    3101/// by a predicate.
    3102///
    3103/// This struct is created by the [`chunk_by_mut`] method on [slices].
    3104///
    3105/// [`chunk_by_mut`]: slice::chunk_by_mut
    3106/// [slices]: slice
    3107#[stable(feature = "slice_group_by", since = "1.77.0")]
    3108#[must_use = "iterators are lazy and do nothing unless consumed"]
    3109pub struct ChunkByMut<'a, T: 'a, P> {
    3110    slice: &'a mut [T],
    3111    predicate: P,
    3112}
    3113
    3114#[stable(feature = "slice_group_by", since = "1.77.0")]
    3115impl<'a, T: 'a, P> ChunkByMut<'a, T, P> {
    3116    pub(super) const fn new(slice: &'a mut [T], predicate: P) -> Self {
    3117        ChunkByMut { slice, predicate }
    3118    }
    3119}
    3120
    3121#[stable(feature = "slice_group_by", since = "1.77.0")]
    3122impl<'a, T: 'a, P> Iterator for ChunkByMut<'a, T, P>
    3123where
    3124    P: FnMut(&T, &T) -> bool,
    3125{
    3126    type Item = &'a mut [T];
    3127
    3128    #[inline]
    3129    fn next(&mut self) -> Option<Self::Item> {
    3130        if self.slice.is_empty() {
    3131            None
    3132        } else {
    3133            let mut len = 1;
    3134            let mut iter = self.slice.windows(2);
    3135            while let Some([l, r]) = iter.next() {
    3136                if (self.predicate)(l, r) { len += 1 } else { break }
    3137            }
    3138            let slice = mem::take(&mut self.slice);
    3139            let (head, tail) = slice.split_at_mut(len);
    3140            self.slice = tail;
    3141            Some(head)
    3142        }
    3143    }
    3144
    3145    #[inline]
    3146    fn size_hint(&self) -> (usize, Option<usize>) {
    3147        if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) }
    3148    }
    3149
    3150    #[inline]
    3151    fn last(mut self) -> Option<Self::Item> {
    3152        self.next_back()
    3153    }
    3154}
    3155
    3156#[stable(feature = "slice_group_by", since = "1.77.0")]
    3157impl<'a, T: 'a, P> DoubleEndedIterator for ChunkByMut<'a, T, P>
    3158where
    3159    P: FnMut(&T, &T) -> bool,
    3160{
    3161    #[inline]
    3162    fn next_back(&mut self) -> Option<Self::Item> {
    3163        if self.slice.is_empty() {
    3164            None
    3165        } else {
    3166            let mut len = 1;
    3167            let mut iter = self.slice.windows(2);
    3168            while let Some([l, r]) = iter.next_back() {
    3169                if (self.predicate)(l, r) { len += 1 } else { break }
    3170            }
    3171            let slice = mem::take(&mut self.slice);
    3172            let (head, tail) = slice.split_at_mut(slice.len() - len);
    3173            self.slice = head;
    3174            Some(tail)
    3175        }
    3176    }
    3177}
    3178
    3179#[stable(feature = "slice_group_by", since = "1.77.0")]
    3180impl<'a, T: 'a, P> FusedIterator for ChunkByMut<'a, T, P> where P: FnMut(&T, &T) -> bool {}
    3181
    3182#[stable(feature = "slice_group_by", since = "1.77.0")]
    3183impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for ChunkByMut<'a, T, P> {
    3184    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    3185        f.debug_struct("ChunkByMut").field("slice", &self.slice).finish()
    3186    }
    3187}