library/core/src/slice/iter.rs

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