library/core/src/slice/iter.rs

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