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