library/core/src/slice/iter.rs

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