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     ///
1838     /// # Example
1839     ///
1840     /// ```
1841     /// let slice = ['l', 'o', 'r', 'e', 'm'];
1842     /// let mut iter = slice.chunks_exact(2);
1843     /// assert_eq!(iter.remainder(), &['m'][..]);
1844     /// assert_eq!(iter.next(), Some(&['l', 'o'][..]));
1845     /// assert_eq!(iter.remainder(), &['m'][..]);
1846     /// assert_eq!(iter.next(), Some(&['r', 'e'][..]));
1847     /// assert_eq!(iter.remainder(), &['m'][..]);
1848     /// assert_eq!(iter.next(), None);
1849     /// assert_eq!(iter.remainder(), &['m'][..]);
1850     /// ```
1851     #[must_use]
1852     #[stable(feature = "chunks_exact", since = "1.31.0")]
1853     pub fn remainder(&self) -> &'a [T] {
1854         self.rem
1855     }
1856 }
1857
1858 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
1859 #[stable(feature = "chunks_exact", since = "1.31.0")]
1860 impl<T> Clone for ChunksExact<'_, T> {
1861     fn clone(&self) -> Self {
1862         ChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size }
1863     }
1864 }
1865
1866 #[stable(feature = "chunks_exact", since = "1.31.0")]
1867 impl<'a, T> Iterator for ChunksExact<'a, T> {
1868     type Item = &'a [T];
1869
1870     #[inline]
1871     fn next(&mut self) -> Option<&'a [T]> {
1872         if self.v.len() < self.chunk_size {
1873             None
1874         } else {
1875             let (fst, snd) = self.v.split_at(self.chunk_size);
1876             self.v = snd;
1877             Some(fst)
1878         }
1879     }
1880
1881     #[inline]
1882     fn size_hint(&self) -> (usize, Option<usize>) {
1883         let n = self.v.len() / self.chunk_size;
1884         (n, Some(n))
1885     }
1886
1887     #[inline]
1888     fn count(self) -> usize {
1889         self.len()
1890     }
1891
1892     #[inline]
1893     fn nth(&mut self, n: usize) -> Option<Self::Item> {
1894         let (start, overflow) = n.overflowing_mul(self.chunk_size);
1895         if start >= self.v.len() || overflow {
1896             self.v = &[];
1897             None
1898         } else {
1899             let (_, snd) = self.v.split_at(start);
1900             self.v = snd;
1901             self.next()
1902         }
1903     }
1904
1905     #[inline]
1906     fn last(mut self) -> Option<Self::Item> {
1907         self.next_back()
1908     }
1909
1910     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
1911         let start = idx * self.chunk_size;
1912         // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
1913         unsafe { from_raw_parts(self.v.as_ptr().add(start), self.chunk_size) }
1914     }
1915 }
1916
1917 #[stable(feature = "chunks_exact", since = "1.31.0")]
1918 impl<'a, T> DoubleEndedIterator for ChunksExact<'a, T> {
1919     #[inline]
1920     fn next_back(&mut self) -> Option<&'a [T]> {
1921         if self.v.len() < self.chunk_size {
1922             None
1923         } else {
1924             let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
1925             self.v = fst;
1926             Some(snd)
1927         }
1928     }
1929
1930     #[inline]
1931     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1932         let len = self.len();
1933         if n >= len {
1934             self.v = &[];
1935             None
1936         } else {
1937             let start = (len - 1 - n) * self.chunk_size;
1938             let end = start + self.chunk_size;
1939             let nth_back = &self.v[start..end];
1940             self.v = &self.v[..start];
1941             Some(nth_back)
1942         }
1943     }
1944 }
1945
1946 #[stable(feature = "chunks_exact", since = "1.31.0")]
1947 impl<T> ExactSizeIterator for ChunksExact<'_, T> {
1948     fn is_empty(&self) -> bool {
1949         self.v.is_empty()
1950     }
1951 }
1952
1953 #[unstable(feature = "trusted_len", issue = "37572")]
1954 unsafe impl<T> TrustedLen for ChunksExact<'_, T> {}
1955
1956 #[stable(feature = "chunks_exact", since = "1.31.0")]
1957 impl<T> FusedIterator for ChunksExact<'_, T> {}
1958
1959 #[doc(hidden)]
1960 #[unstable(feature = "trusted_random_access", issue = "none")]
1961 unsafe impl<'a, T> TrustedRandomAccess for ChunksExact<'a, T> {}
1962
1963 #[doc(hidden)]
1964 #[unstable(feature = "trusted_random_access", issue = "none")]
1965 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksExact<'a, T> {
1966     const MAY_HAVE_SIDE_EFFECT: bool = false;
1967 }
1968
1969 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
1970 /// elements at a time), starting at the beginning of the slice.
1971 ///
1972 /// When the slice len is not evenly divided by the chunk size, the last up to
1973 /// `chunk_size-1` elements will be omitted but can be retrieved from the
1974 /// [`into_remainder`] function from the iterator.
1975 ///
1976 /// This struct is created by the [`chunks_exact_mut`] method on [slices].
1977 ///
1978 /// # Example
1979 ///
1980 /// ```
1981 /// let mut slice = ['l', 'o', 'r', 'e', 'm'];
1982 /// let iter = slice.chunks_exact_mut(2);
1983 /// ```
1984 ///
1985 /// [`chunks_exact_mut`]: slice::chunks_exact_mut
1986 /// [`into_remainder`]: ChunksExactMut::into_remainder
1987 /// [slices]: slice
1988 #[derive(Debug)]
1989 #[stable(feature = "chunks_exact", since = "1.31.0")]
1990 #[must_use = "iterators are lazy and do nothing unless consumed"]
1991 pub struct ChunksExactMut<'a, T: 'a> {
1992     /// # Safety
1993     /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
1994     /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
1995     /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
1996     /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
1997     /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
1998     v: *mut [T],
1999     rem: &'a mut [T], // The iterator never yields from here, so this can be unique
2000     chunk_size: usize,
2001     _marker: PhantomData<&'a mut T>,
2002 }
2003
2004 impl<'a, T> ChunksExactMut<'a, T> {
2005     #[inline]
2006     pub(super) fn new(slice: &'a mut [T], chunk_size: usize) -> Self {
2007         let rem = slice.len() % chunk_size;
2008         let fst_len = slice.len() - rem;
2009         // SAFETY: 0 <= fst_len <= slice.len() by construction above
2010         let (fst, snd) = unsafe { slice.split_at_mut_unchecked(fst_len) };
2011         Self { v: fst, rem: snd, chunk_size, _marker: PhantomData }
2012     }
2013
2014     /// Returns the remainder of the original slice that is not going to be
2015     /// returned by the iterator. The returned slice has at most `chunk_size-1`
2016     /// elements.
2017     #[must_use = "`self` will be dropped if the result is not used"]
2018     #[stable(feature = "chunks_exact", since = "1.31.0")]
2019     pub fn into_remainder(self) -> &'a mut [T] {
2020         self.rem
2021     }
2022 }
2023
2024 #[stable(feature = "chunks_exact", since = "1.31.0")]
2025 impl<'a, T> Iterator for ChunksExactMut<'a, T> {
2026     type Item = &'a mut [T];
2027
2028     #[inline]
2029     fn next(&mut self) -> Option<&'a mut [T]> {
2030         if self.v.len() < self.chunk_size {
2031             None
2032         } else {
2033             // SAFETY: self.chunk_size is inbounds because we compared above against self.v.len()
2034             let (head, tail) = unsafe { self.v.split_at_mut(self.chunk_size) };
2035             self.v = tail;
2036             // SAFETY: Nothing else points to or will point to the contents of this slice.
2037             Some(unsafe { &mut *head })
2038         }
2039     }
2040
2041     #[inline]
2042     fn size_hint(&self) -> (usize, Option<usize>) {
2043         let n = self.v.len() / self.chunk_size;
2044         (n, Some(n))
2045     }
2046
2047     #[inline]
2048     fn count(self) -> usize {
2049         self.len()
2050     }
2051
2052     #[inline]
2053     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
2054         let (start, overflow) = n.overflowing_mul(self.chunk_size);
2055         if start >= self.v.len() || overflow {
2056             self.v = &mut [];
2057             None
2058         } else {
2059             // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2060             let (_, snd) = unsafe { self.v.split_at_mut(start) };
2061             self.v = snd;
2062             self.next()
2063         }
2064     }
2065
2066     #[inline]
2067     fn last(mut self) -> Option<Self::Item> {
2068         self.next_back()
2069     }
2070
2071     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2072         let start = idx * self.chunk_size;
2073         // SAFETY: see comments for `Chunks::__iterator_get_unchecked` and `self.v`.
2074         unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size) }
2075     }
2076 }
2077
2078 #[stable(feature = "chunks_exact", since = "1.31.0")]
2079 impl<'a, T> DoubleEndedIterator for ChunksExactMut<'a, T> {
2080     #[inline]
2081     fn next_back(&mut self) -> Option<&'a mut [T]> {
2082         if self.v.len() < self.chunk_size {
2083             None
2084         } else {
2085             // SAFETY: This subtraction is inbounds because of the check above
2086             let (head, tail) = unsafe { self.v.split_at_mut(self.v.len() - self.chunk_size) };
2087             self.v = head;
2088             // SAFETY: Nothing else points to or will point to the contents of this slice.
2089             Some(unsafe { &mut *tail })
2090         }
2091     }
2092
2093     #[inline]
2094     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2095         let len = self.len();
2096         if n >= len {
2097             self.v = &mut [];
2098             None
2099         } else {
2100             let start = (len - 1 - n) * self.chunk_size;
2101             let end = start + self.chunk_size;
2102             // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2103             let (temp, _tail) = unsafe { mem::replace(&mut self.v, &mut []).split_at_mut(end) };
2104             // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2105             let (head, nth_back) = unsafe { temp.split_at_mut(start) };
2106             self.v = head;
2107             // SAFETY: Nothing else points to or will point to the contents of this slice.
2108             Some(unsafe { &mut *nth_back })
2109         }
2110     }
2111 }
2112
2113 #[stable(feature = "chunks_exact", since = "1.31.0")]
2114 impl<T> ExactSizeIterator for ChunksExactMut<'_, T> {
2115     fn is_empty(&self) -> bool {
2116         self.v.is_empty()
2117     }
2118 }
2119
2120 #[unstable(feature = "trusted_len", issue = "37572")]
2121 unsafe impl<T> TrustedLen for ChunksExactMut<'_, T> {}
2122
2123 #[stable(feature = "chunks_exact", since = "1.31.0")]
2124 impl<T> FusedIterator for ChunksExactMut<'_, T> {}
2125
2126 #[doc(hidden)]
2127 #[unstable(feature = "trusted_random_access", issue = "none")]
2128 unsafe impl<'a, T> TrustedRandomAccess for ChunksExactMut<'a, T> {}
2129
2130 #[doc(hidden)]
2131 #[unstable(feature = "trusted_random_access", issue = "none")]
2132 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for ChunksExactMut<'a, T> {
2133     const MAY_HAVE_SIDE_EFFECT: bool = false;
2134 }
2135
2136 #[stable(feature = "chunks_exact", since = "1.31.0")]
2137 unsafe impl<T> Send for ChunksExactMut<'_, T> where T: Send {}
2138
2139 #[stable(feature = "chunks_exact", since = "1.31.0")]
2140 unsafe impl<T> Sync for ChunksExactMut<'_, T> where T: Sync {}
2141
2142 /// A windowed iterator over a slice in overlapping chunks (`N` elements at a
2143 /// time), starting at the beginning of the slice
2144 ///
2145 /// This struct is created by the [`array_windows`] method on [slices].
2146 ///
2147 /// # Example
2148 ///
2149 /// ```
2150 /// #![feature(array_windows)]
2151 ///
2152 /// let slice = [0, 1, 2, 3];
2153 /// let iter = slice.array_windows::<2>();
2154 /// ```
2155 ///
2156 /// [`array_windows`]: slice::array_windows
2157 /// [slices]: slice
2158 #[derive(Debug, Clone, Copy)]
2159 #[unstable(feature = "array_windows", issue = "75027")]
2160 #[must_use = "iterators are lazy and do nothing unless consumed"]
2161 pub struct ArrayWindows<'a, T: 'a, const N: usize> {
2162     slice_head: *const T,
2163     num: usize,
2164     marker: PhantomData<&'a [T; N]>,
2165 }
2166
2167 impl<'a, T: 'a, const N: usize> ArrayWindows<'a, T, N> {
2168     #[inline]
2169     pub(super) fn new(slice: &'a [T]) -> Self {
2170         let num_windows = slice.len().saturating_sub(N - 1);
2171         Self { slice_head: slice.as_ptr(), num: num_windows, marker: PhantomData }
2172     }
2173 }
2174
2175 #[unstable(feature = "array_windows", issue = "75027")]
2176 impl<'a, T, const N: usize> Iterator for ArrayWindows<'a, T, N> {
2177     type Item = &'a [T; N];
2178
2179     #[inline]
2180     fn next(&mut self) -> Option<Self::Item> {
2181         if self.num == 0 {
2182             return None;
2183         }
2184         // SAFETY:
2185         // This is safe because it's indexing into a slice guaranteed to be length > N.
2186         let ret = unsafe { &*self.slice_head.cast::<[T; N]>() };
2187         // SAFETY: Guaranteed that there are at least 1 item remaining otherwise
2188         // earlier branch would've been hit
2189         self.slice_head = unsafe { self.slice_head.add(1) };
2190
2191         self.num -= 1;
2192         Some(ret)
2193     }
2194
2195     #[inline]
2196     fn size_hint(&self) -> (usize, Option<usize>) {
2197         (self.num, Some(self.num))
2198     }
2199
2200     #[inline]
2201     fn count(self) -> usize {
2202         self.num
2203     }
2204
2205     #[inline]
2206     fn nth(&mut self, n: usize) -> Option<Self::Item> {
2207         if self.num <= n {
2208             self.num = 0;
2209             return None;
2210         }
2211         // SAFETY:
2212         // This is safe because it's indexing into a slice guaranteed to be length > N.
2213         let ret = unsafe { &*self.slice_head.add(n).cast::<[T; N]>() };
2214         // SAFETY: Guaranteed that there are at least n items remaining
2215         self.slice_head = unsafe { self.slice_head.add(n + 1) };
2216
2217         self.num -= n + 1;
2218         Some(ret)
2219     }
2220
2221     #[inline]
2222     fn last(mut self) -> Option<Self::Item> {
2223         self.nth(self.num.checked_sub(1)?)
2224     }
2225 }
2226
2227 #[unstable(feature = "array_windows", issue = "75027")]
2228 impl<'a, T, const N: usize> DoubleEndedIterator for ArrayWindows<'a, T, N> {
2229     #[inline]
2230     fn next_back(&mut self) -> Option<&'a [T; N]> {
2231         if self.num == 0 {
2232             return None;
2233         }
2234         // SAFETY: Guaranteed that there are n items remaining, n-1 for 0-indexing.
2235         let ret = unsafe { &*self.slice_head.add(self.num - 1).cast::<[T; N]>() };
2236         self.num -= 1;
2237         Some(ret)
2238     }
2239
2240     #[inline]
2241     fn nth_back(&mut self, n: usize) -> Option<&'a [T; N]> {
2242         if self.num <= n {
2243             self.num = 0;
2244             return None;
2245         }
2246         // SAFETY: Guaranteed that there are n items remaining, n-1 for 0-indexing.
2247         let ret = unsafe { &*self.slice_head.add(self.num - (n + 1)).cast::<[T; N]>() };
2248         self.num -= n + 1;
2249         Some(ret)
2250     }
2251 }
2252
2253 #[unstable(feature = "array_windows", issue = "75027")]
2254 impl<T, const N: usize> ExactSizeIterator for ArrayWindows<'_, T, N> {
2255     fn is_empty(&self) -> bool {
2256         self.num == 0
2257     }
2258 }
2259
2260 /// An iterator over a slice in (non-overlapping) chunks (`N` elements at a
2261 /// time), starting at the beginning of the slice.
2262 ///
2263 /// When the slice len is not evenly divided by the chunk size, the last
2264 /// up to `N-1` elements will be omitted but can be retrieved from
2265 /// the [`remainder`] function from the iterator.
2266 ///
2267 /// This struct is created by the [`array_chunks`] method on [slices].
2268 ///
2269 /// # Example
2270 ///
2271 /// ```
2272 /// #![feature(array_chunks)]
2273 ///
2274 /// let slice = ['l', 'o', 'r', 'e', 'm'];
2275 /// let iter = slice.array_chunks::<2>();
2276 /// ```
2277 ///
2278 /// [`array_chunks`]: slice::array_chunks
2279 /// [`remainder`]: ArrayChunks::remainder
2280 /// [slices]: slice
2281 #[derive(Debug)]
2282 #[unstable(feature = "array_chunks", issue = "74985")]
2283 #[must_use = "iterators are lazy and do nothing unless consumed"]
2284 pub struct ArrayChunks<'a, T: 'a, const N: usize> {
2285     iter: Iter<'a, [T; N]>,
2286     rem: &'a [T],
2287 }
2288
2289 impl<'a, T, const N: usize> ArrayChunks<'a, T, N> {
2290     #[inline]
2291     pub(super) fn new(slice: &'a [T]) -> Self {
2292         let (array_slice, rem) = slice.as_chunks();
2293         Self { iter: array_slice.iter(), rem }
2294     }
2295
2296     /// Returns the remainder of the original slice that is not going to be
2297     /// returned by the iterator. The returned slice has at most `N-1`
2298     /// elements.
2299     #[must_use]
2300     #[unstable(feature = "array_chunks", issue = "74985")]
2301     pub fn remainder(&self) -> &'a [T] {
2302         self.rem
2303     }
2304 }
2305
2306 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2307 #[unstable(feature = "array_chunks", issue = "74985")]
2308 impl<T, const N: usize> Clone for ArrayChunks<'_, T, N> {
2309     fn clone(&self) -> Self {
2310         ArrayChunks { iter: self.iter.clone(), rem: self.rem }
2311     }
2312 }
2313
2314 #[unstable(feature = "array_chunks", issue = "74985")]
2315 impl<'a, T, const N: usize> Iterator for ArrayChunks<'a, T, N> {
2316     type Item = &'a [T; N];
2317
2318     #[inline]
2319     fn next(&mut self) -> Option<&'a [T; N]> {
2320         self.iter.next()
2321     }
2322
2323     #[inline]
2324     fn size_hint(&self) -> (usize, Option<usize>) {
2325         self.iter.size_hint()
2326     }
2327
2328     #[inline]
2329     fn count(self) -> usize {
2330         self.iter.count()
2331     }
2332
2333     #[inline]
2334     fn nth(&mut self, n: usize) -> Option<Self::Item> {
2335         self.iter.nth(n)
2336     }
2337
2338     #[inline]
2339     fn last(self) -> Option<Self::Item> {
2340         self.iter.last()
2341     }
2342
2343     unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> &'a [T; N] {
2344         // SAFETY: The safety guarantees of `__iterator_get_unchecked` are
2345         // transferred to the caller.
2346         unsafe { self.iter.__iterator_get_unchecked(i) }
2347     }
2348 }
2349
2350 #[unstable(feature = "array_chunks", issue = "74985")]
2351 impl<'a, T, const N: usize> DoubleEndedIterator for ArrayChunks<'a, T, N> {
2352     #[inline]
2353     fn next_back(&mut self) -> Option<&'a [T; N]> {
2354         self.iter.next_back()
2355     }
2356
2357     #[inline]
2358     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2359         self.iter.nth_back(n)
2360     }
2361 }
2362
2363 #[unstable(feature = "array_chunks", issue = "74985")]
2364 impl<T, const N: usize> ExactSizeIterator for ArrayChunks<'_, T, N> {
2365     fn is_empty(&self) -> bool {
2366         self.iter.is_empty()
2367     }
2368 }
2369
2370 #[unstable(feature = "trusted_len", issue = "37572")]
2371 unsafe impl<T, const N: usize> TrustedLen for ArrayChunks<'_, T, N> {}
2372
2373 #[unstable(feature = "array_chunks", issue = "74985")]
2374 impl<T, const N: usize> FusedIterator for ArrayChunks<'_, T, N> {}
2375
2376 #[doc(hidden)]
2377 #[unstable(feature = "array_chunks", issue = "74985")]
2378 unsafe impl<'a, T, const N: usize> TrustedRandomAccess for ArrayChunks<'a, T, N> {}
2379
2380 #[doc(hidden)]
2381 #[unstable(feature = "array_chunks", issue = "74985")]
2382 unsafe impl<'a, T, const N: usize> TrustedRandomAccessNoCoerce for ArrayChunks<'a, T, N> {
2383     const MAY_HAVE_SIDE_EFFECT: bool = false;
2384 }
2385
2386 /// An iterator over a slice in (non-overlapping) mutable chunks (`N` elements
2387 /// at a time), starting at the beginning of the slice.
2388 ///
2389 /// When the slice len is not evenly divided by the chunk size, the last
2390 /// up to `N-1` elements will be omitted but can be retrieved from
2391 /// the [`into_remainder`] function from the iterator.
2392 ///
2393 /// This struct is created by the [`array_chunks_mut`] method on [slices].
2394 ///
2395 /// # Example
2396 ///
2397 /// ```
2398 /// #![feature(array_chunks)]
2399 ///
2400 /// let mut slice = ['l', 'o', 'r', 'e', 'm'];
2401 /// let iter = slice.array_chunks_mut::<2>();
2402 /// ```
2403 ///
2404 /// [`array_chunks_mut`]: slice::array_chunks_mut
2405 /// [`into_remainder`]: ../../std/slice/struct.ArrayChunksMut.html#method.into_remainder
2406 /// [slices]: slice
2407 #[derive(Debug)]
2408 #[unstable(feature = "array_chunks", issue = "74985")]
2409 #[must_use = "iterators are lazy and do nothing unless consumed"]
2410 pub struct ArrayChunksMut<'a, T: 'a, const N: usize> {
2411     iter: IterMut<'a, [T; N]>,
2412     rem: &'a mut [T],
2413 }
2414
2415 impl<'a, T, const N: usize> ArrayChunksMut<'a, T, N> {
2416     #[inline]
2417     pub(super) fn new(slice: &'a mut [T]) -> Self {
2418         let (array_slice, rem) = slice.as_chunks_mut();
2419         Self { iter: array_slice.iter_mut(), rem }
2420     }
2421
2422     /// Returns the remainder of the original slice that is not going to be
2423     /// returned by the iterator. The returned slice has at most `N-1`
2424     /// elements.
2425     #[must_use = "`self` will be dropped if the result is not used"]
2426     #[unstable(feature = "array_chunks", issue = "74985")]
2427     pub fn into_remainder(self) -> &'a mut [T] {
2428         self.rem
2429     }
2430 }
2431
2432 #[unstable(feature = "array_chunks", issue = "74985")]
2433 impl<'a, T, const N: usize> Iterator for ArrayChunksMut<'a, T, N> {
2434     type Item = &'a mut [T; N];
2435
2436     #[inline]
2437     fn next(&mut self) -> Option<&'a mut [T; N]> {
2438         self.iter.next()
2439     }
2440
2441     #[inline]
2442     fn size_hint(&self) -> (usize, Option<usize>) {
2443         self.iter.size_hint()
2444     }
2445
2446     #[inline]
2447     fn count(self) -> usize {
2448         self.iter.count()
2449     }
2450
2451     #[inline]
2452     fn nth(&mut self, n: usize) -> Option<Self::Item> {
2453         self.iter.nth(n)
2454     }
2455
2456     #[inline]
2457     fn last(self) -> Option<Self::Item> {
2458         self.iter.last()
2459     }
2460
2461     unsafe fn __iterator_get_unchecked(&mut self, i: usize) -> &'a mut [T; N] {
2462         // SAFETY: The safety guarantees of `__iterator_get_unchecked` are transferred to
2463         // the caller.
2464         unsafe { self.iter.__iterator_get_unchecked(i) }
2465     }
2466 }
2467
2468 #[unstable(feature = "array_chunks", issue = "74985")]
2469 impl<'a, T, const N: usize> DoubleEndedIterator for ArrayChunksMut<'a, T, N> {
2470     #[inline]
2471     fn next_back(&mut self) -> Option<&'a mut [T; N]> {
2472         self.iter.next_back()
2473     }
2474
2475     #[inline]
2476     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2477         self.iter.nth_back(n)
2478     }
2479 }
2480
2481 #[unstable(feature = "array_chunks", issue = "74985")]
2482 impl<T, const N: usize> ExactSizeIterator for ArrayChunksMut<'_, T, N> {
2483     fn is_empty(&self) -> bool {
2484         self.iter.is_empty()
2485     }
2486 }
2487
2488 #[unstable(feature = "trusted_len", issue = "37572")]
2489 unsafe impl<T, const N: usize> TrustedLen for ArrayChunksMut<'_, T, N> {}
2490
2491 #[unstable(feature = "array_chunks", issue = "74985")]
2492 impl<T, const N: usize> FusedIterator for ArrayChunksMut<'_, T, N> {}
2493
2494 #[doc(hidden)]
2495 #[unstable(feature = "array_chunks", issue = "74985")]
2496 unsafe impl<'a, T, const N: usize> TrustedRandomAccess for ArrayChunksMut<'a, T, N> {}
2497
2498 #[doc(hidden)]
2499 #[unstable(feature = "array_chunks", issue = "74985")]
2500 unsafe impl<'a, T, const N: usize> TrustedRandomAccessNoCoerce for ArrayChunksMut<'a, T, N> {
2501     const MAY_HAVE_SIDE_EFFECT: bool = false;
2502 }
2503
2504 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
2505 /// time), starting at the end of the slice.
2506 ///
2507 /// When the slice len is not evenly divided by the chunk size, the last slice
2508 /// of the iteration will be the remainder.
2509 ///
2510 /// This struct is created by the [`rchunks`] method on [slices].
2511 ///
2512 /// # Example
2513 ///
2514 /// ```
2515 /// let slice = ['l', 'o', 'r', 'e', 'm'];
2516 /// let iter = slice.rchunks(2);
2517 /// ```
2518 ///
2519 /// [`rchunks`]: slice::rchunks
2520 /// [slices]: slice
2521 #[derive(Debug)]
2522 #[stable(feature = "rchunks", since = "1.31.0")]
2523 #[must_use = "iterators are lazy and do nothing unless consumed"]
2524 pub struct RChunks<'a, T: 'a> {
2525     v: &'a [T],
2526     chunk_size: usize,
2527 }
2528
2529 impl<'a, T: 'a> RChunks<'a, T> {
2530     #[inline]
2531     pub(super) fn new(slice: &'a [T], size: usize) -> Self {
2532         Self { v: slice, chunk_size: size }
2533     }
2534 }
2535
2536 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2537 #[stable(feature = "rchunks", since = "1.31.0")]
2538 impl<T> Clone for RChunks<'_, T> {
2539     fn clone(&self) -> Self {
2540         RChunks { v: self.v, chunk_size: self.chunk_size }
2541     }
2542 }
2543
2544 #[stable(feature = "rchunks", since = "1.31.0")]
2545 impl<'a, T> Iterator for RChunks<'a, T> {
2546     type Item = &'a [T];
2547
2548     #[inline]
2549     fn next(&mut self) -> Option<&'a [T]> {
2550         if self.v.is_empty() {
2551             None
2552         } else {
2553             let len = self.v.len();
2554             let chunksz = cmp::min(len, self.chunk_size);
2555             // SAFETY: split_at_unchecked just requires the argument be less
2556             // than the length. This could only happen if the expression `len -
2557             // chunksz` overflows. This could only happen if `chunksz > len`,
2558             // which is impossible as we initialize it as the `min` of `len` and
2559             // `self.chunk_size`.
2560             let (fst, snd) = unsafe { self.v.split_at_unchecked(len - chunksz) };
2561             self.v = fst;
2562             Some(snd)
2563         }
2564     }
2565
2566     #[inline]
2567     fn size_hint(&self) -> (usize, Option<usize>) {
2568         if self.v.is_empty() {
2569             (0, Some(0))
2570         } else {
2571             let n = self.v.len() / self.chunk_size;
2572             let rem = self.v.len() % self.chunk_size;
2573             let n = if rem > 0 { n + 1 } else { n };
2574             (n, Some(n))
2575         }
2576     }
2577
2578     #[inline]
2579     fn count(self) -> usize {
2580         self.len()
2581     }
2582
2583     #[inline]
2584     fn nth(&mut self, n: usize) -> Option<Self::Item> {
2585         let (end, overflow) = n.overflowing_mul(self.chunk_size);
2586         if end >= self.v.len() || overflow {
2587             self.v = &[];
2588             None
2589         } else {
2590             // Can't underflow because of the check above
2591             let end = self.v.len() - end;
2592             let start = match end.checked_sub(self.chunk_size) {
2593                 Some(sum) => sum,
2594                 None => 0,
2595             };
2596             let nth = &self.v[start..end];
2597             self.v = &self.v[0..start];
2598             Some(nth)
2599         }
2600     }
2601
2602     #[inline]
2603     fn last(self) -> Option<Self::Item> {
2604         if self.v.is_empty() {
2605             None
2606         } else {
2607             let rem = self.v.len() % self.chunk_size;
2608             let end = if rem == 0 { self.chunk_size } else { rem };
2609             Some(&self.v[0..end])
2610         }
2611     }
2612
2613     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2614         let end = self.v.len() - idx * self.chunk_size;
2615         let start = match end.checked_sub(self.chunk_size) {
2616             None => 0,
2617             Some(start) => start,
2618         };
2619         // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
2620         unsafe { from_raw_parts(self.v.as_ptr().add(start), end - start) }
2621     }
2622 }
2623
2624 #[stable(feature = "rchunks", since = "1.31.0")]
2625 impl<'a, T> DoubleEndedIterator for RChunks<'a, T> {
2626     #[inline]
2627     fn next_back(&mut self) -> Option<&'a [T]> {
2628         if self.v.is_empty() {
2629             None
2630         } else {
2631             let remainder = self.v.len() % self.chunk_size;
2632             let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
2633             // SAFETY: similar to Chunks::next_back
2634             let (fst, snd) = unsafe { self.v.split_at_unchecked(chunksz) };
2635             self.v = snd;
2636             Some(fst)
2637         }
2638     }
2639
2640     #[inline]
2641     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2642         let len = self.len();
2643         if n >= len {
2644             self.v = &[];
2645             None
2646         } else {
2647             // can't underflow because `n < len`
2648             let offset_from_end = (len - 1 - n) * self.chunk_size;
2649             let end = self.v.len() - offset_from_end;
2650             let start = end.saturating_sub(self.chunk_size);
2651             let nth_back = &self.v[start..end];
2652             self.v = &self.v[end..];
2653             Some(nth_back)
2654         }
2655     }
2656 }
2657
2658 #[stable(feature = "rchunks", since = "1.31.0")]
2659 impl<T> ExactSizeIterator for RChunks<'_, T> {}
2660
2661 #[unstable(feature = "trusted_len", issue = "37572")]
2662 unsafe impl<T> TrustedLen for RChunks<'_, T> {}
2663
2664 #[stable(feature = "rchunks", since = "1.31.0")]
2665 impl<T> FusedIterator for RChunks<'_, T> {}
2666
2667 #[doc(hidden)]
2668 #[unstable(feature = "trusted_random_access", issue = "none")]
2669 unsafe impl<'a, T> TrustedRandomAccess for RChunks<'a, T> {}
2670
2671 #[doc(hidden)]
2672 #[unstable(feature = "trusted_random_access", issue = "none")]
2673 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunks<'a, T> {
2674     const MAY_HAVE_SIDE_EFFECT: bool = false;
2675 }
2676
2677 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
2678 /// elements at a time), starting at the end of the slice.
2679 ///
2680 /// When the slice len is not evenly divided by the chunk size, the last slice
2681 /// of the iteration will be the remainder.
2682 ///
2683 /// This struct is created by the [`rchunks_mut`] method on [slices].
2684 ///
2685 /// # Example
2686 ///
2687 /// ```
2688 /// let mut slice = ['l', 'o', 'r', 'e', 'm'];
2689 /// let iter = slice.rchunks_mut(2);
2690 /// ```
2691 ///
2692 /// [`rchunks_mut`]: slice::rchunks_mut
2693 /// [slices]: slice
2694 #[derive(Debug)]
2695 #[stable(feature = "rchunks", since = "1.31.0")]
2696 #[must_use = "iterators are lazy and do nothing unless consumed"]
2697 pub struct RChunksMut<'a, T: 'a> {
2698     /// # Safety
2699     /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
2700     /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
2701     /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
2702     /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
2703     /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
2704     v: *mut [T],
2705     chunk_size: usize,
2706     _marker: PhantomData<&'a mut T>,
2707 }
2708
2709 impl<'a, T: 'a> RChunksMut<'a, T> {
2710     #[inline]
2711     pub(super) fn new(slice: &'a mut [T], size: usize) -> Self {
2712         Self { v: slice, chunk_size: size, _marker: PhantomData }
2713     }
2714 }
2715
2716 #[stable(feature = "rchunks", since = "1.31.0")]
2717 impl<'a, T> Iterator for RChunksMut<'a, T> {
2718     type Item = &'a mut [T];
2719
2720     #[inline]
2721     fn next(&mut self) -> Option<&'a mut [T]> {
2722         if self.v.is_empty() {
2723             None
2724         } else {
2725             let sz = cmp::min(self.v.len(), self.chunk_size);
2726             let len = self.v.len();
2727             // SAFETY: split_at_mut_unchecked just requires the argument be less
2728             // than the length. This could only happen if the expression
2729             // `len - sz` overflows. This could only happen if `sz >
2730             // len`, which is impossible as we initialize it as the `min` of
2731             // `self.v.len()` (e.g. `len`) and `self.chunk_size`.
2732             let (head, tail) = unsafe { self.v.split_at_mut_unchecked(len - sz) };
2733             self.v = head;
2734             // SAFETY: Nothing else points to or will point to the contents of this slice.
2735             Some(unsafe { &mut *tail })
2736         }
2737     }
2738
2739     #[inline]
2740     fn size_hint(&self) -> (usize, Option<usize>) {
2741         if self.v.is_empty() {
2742             (0, Some(0))
2743         } else {
2744             let n = self.v.len() / self.chunk_size;
2745             let rem = self.v.len() % self.chunk_size;
2746             let n = if rem > 0 { n + 1 } else { n };
2747             (n, Some(n))
2748         }
2749     }
2750
2751     #[inline]
2752     fn count(self) -> usize {
2753         self.len()
2754     }
2755
2756     #[inline]
2757     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
2758         let (end, overflow) = n.overflowing_mul(self.chunk_size);
2759         if end >= self.v.len() || overflow {
2760             self.v = &mut [];
2761             None
2762         } else {
2763             // Can't underflow because of the check above
2764             let end = self.v.len() - end;
2765             let start = match end.checked_sub(self.chunk_size) {
2766                 Some(sum) => sum,
2767                 None => 0,
2768             };
2769             // SAFETY: This type ensures that self.v is a valid pointer with a correct len.
2770             // Therefore the bounds check in split_at_mut guarantees the split point is inbounds.
2771             let (head, tail) = unsafe { self.v.split_at_mut(start) };
2772             // SAFETY: This type ensures that self.v is a valid pointer with a correct len.
2773             // Therefore the bounds check in split_at_mut guarantees the split point is inbounds.
2774             let (nth, _) = unsafe { tail.split_at_mut(end - start) };
2775             self.v = head;
2776             // SAFETY: Nothing else points to or will point to the contents of this slice.
2777             Some(unsafe { &mut *nth })
2778         }
2779     }
2780
2781     #[inline]
2782     fn last(self) -> Option<Self::Item> {
2783         if self.v.is_empty() {
2784             None
2785         } else {
2786             let rem = self.v.len() % self.chunk_size;
2787             let end = if rem == 0 { self.chunk_size } else { rem };
2788             // SAFETY: Nothing else points to or will point to the contents of this slice.
2789             Some(unsafe { &mut *self.v.get_unchecked_mut(0..end) })
2790         }
2791     }
2792
2793     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2794         let end = self.v.len() - idx * self.chunk_size;
2795         let start = match end.checked_sub(self.chunk_size) {
2796             None => 0,
2797             Some(start) => start,
2798         };
2799         // SAFETY: see comments for `RChunks::__iterator_get_unchecked` and
2800         // `ChunksMut::__iterator_get_unchecked`, `self.v`.
2801         unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), end - start) }
2802     }
2803 }
2804
2805 #[stable(feature = "rchunks", since = "1.31.0")]
2806 impl<'a, T> DoubleEndedIterator for RChunksMut<'a, T> {
2807     #[inline]
2808     fn next_back(&mut self) -> Option<&'a mut [T]> {
2809         if self.v.is_empty() {
2810             None
2811         } else {
2812             let remainder = self.v.len() % self.chunk_size;
2813             let sz = if remainder != 0 { remainder } else { self.chunk_size };
2814             // SAFETY: Similar to `Chunks::next_back`
2815             let (head, tail) = unsafe { self.v.split_at_mut_unchecked(sz) };
2816             self.v = tail;
2817             // SAFETY: Nothing else points to or will point to the contents of this slice.
2818             Some(unsafe { &mut *head })
2819         }
2820     }
2821
2822     #[inline]
2823     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
2824         let len = self.len();
2825         if n >= len {
2826             self.v = &mut [];
2827             None
2828         } else {
2829             // can't underflow because `n < len`
2830             let offset_from_end = (len - 1 - n) * self.chunk_size;
2831             let end = self.v.len() - offset_from_end;
2832             let start = end.saturating_sub(self.chunk_size);
2833             // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2834             let (tmp, tail) = unsafe { self.v.split_at_mut(end) };
2835             // SAFETY: The self.v contract ensures that any split_at_mut is valid.
2836             let (_, nth_back) = unsafe { tmp.split_at_mut(start) };
2837             self.v = tail;
2838             // SAFETY: Nothing else points to or will point to the contents of this slice.
2839             Some(unsafe { &mut *nth_back })
2840         }
2841     }
2842 }
2843
2844 #[stable(feature = "rchunks", since = "1.31.0")]
2845 impl<T> ExactSizeIterator for RChunksMut<'_, T> {}
2846
2847 #[unstable(feature = "trusted_len", issue = "37572")]
2848 unsafe impl<T> TrustedLen for RChunksMut<'_, T> {}
2849
2850 #[stable(feature = "rchunks", since = "1.31.0")]
2851 impl<T> FusedIterator for RChunksMut<'_, T> {}
2852
2853 #[doc(hidden)]
2854 #[unstable(feature = "trusted_random_access", issue = "none")]
2855 unsafe impl<'a, T> TrustedRandomAccess for RChunksMut<'a, T> {}
2856
2857 #[doc(hidden)]
2858 #[unstable(feature = "trusted_random_access", issue = "none")]
2859 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksMut<'a, T> {
2860     const MAY_HAVE_SIDE_EFFECT: bool = false;
2861 }
2862
2863 #[stable(feature = "rchunks", since = "1.31.0")]
2864 unsafe impl<T> Send for RChunksMut<'_, T> where T: Send {}
2865
2866 #[stable(feature = "rchunks", since = "1.31.0")]
2867 unsafe impl<T> Sync for RChunksMut<'_, T> where T: Sync {}
2868
2869 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
2870 /// time), starting at the end of the slice.
2871 ///
2872 /// When the slice len is not evenly divided by the chunk size, the last
2873 /// up to `chunk_size-1` elements will be omitted but can be retrieved from
2874 /// the [`remainder`] function from the iterator.
2875 ///
2876 /// This struct is created by the [`rchunks_exact`] method on [slices].
2877 ///
2878 /// # Example
2879 ///
2880 /// ```
2881 /// let slice = ['l', 'o', 'r', 'e', 'm'];
2882 /// let iter = slice.rchunks_exact(2);
2883 /// ```
2884 ///
2885 /// [`rchunks_exact`]: slice::rchunks_exact
2886 /// [`remainder`]: RChunksExact::remainder
2887 /// [slices]: slice
2888 #[derive(Debug)]
2889 #[stable(feature = "rchunks", since = "1.31.0")]
2890 #[must_use = "iterators are lazy and do nothing unless consumed"]
2891 pub struct RChunksExact<'a, T: 'a> {
2892     v: &'a [T],
2893     rem: &'a [T],
2894     chunk_size: usize,
2895 }
2896
2897 impl<'a, T> RChunksExact<'a, T> {
2898     #[inline]
2899     pub(super) fn new(slice: &'a [T], chunk_size: usize) -> Self {
2900         let rem = slice.len() % chunk_size;
2901         // SAFETY: 0 <= rem <= slice.len() by construction above
2902         let (fst, snd) = unsafe { slice.split_at_unchecked(rem) };
2903         Self { v: snd, rem: fst, chunk_size }
2904     }
2905
2906     /// Returns the remainder of the original slice that is not going to be
2907     /// returned by the iterator. The returned slice has at most `chunk_size-1`
2908     /// elements.
2909     ///
2910     /// # Example
2911     ///
2912     /// ```
2913     /// let slice = ['l', 'o', 'r', 'e', 'm'];
2914     /// let mut iter = slice.rchunks_exact(2);
2915     /// assert_eq!(iter.remainder(), &['l'][..]);
2916     /// assert_eq!(iter.next(), Some(&['e', 'm'][..]));
2917     /// assert_eq!(iter.remainder(), &['l'][..]);
2918     /// assert_eq!(iter.next(), Some(&['o', 'r'][..]));
2919     /// assert_eq!(iter.remainder(), &['l'][..]);
2920     /// assert_eq!(iter.next(), None);
2921     /// assert_eq!(iter.remainder(), &['l'][..]);
2922     /// ```
2923     #[must_use]
2924     #[stable(feature = "rchunks", since = "1.31.0")]
2925     pub fn remainder(&self) -> &'a [T] {
2926         self.rem
2927     }
2928 }
2929
2930 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2931 #[stable(feature = "rchunks", since = "1.31.0")]
2932 impl<'a, T> Clone for RChunksExact<'a, T> {
2933     fn clone(&self) -> RChunksExact<'a, T> {
2934         RChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size }
2935     }
2936 }
2937
2938 #[stable(feature = "rchunks", since = "1.31.0")]
2939 impl<'a, T> Iterator for RChunksExact<'a, T> {
2940     type Item = &'a [T];
2941
2942     #[inline]
2943     fn next(&mut self) -> Option<&'a [T]> {
2944         if self.v.len() < self.chunk_size {
2945             None
2946         } else {
2947             let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
2948             self.v = fst;
2949             Some(snd)
2950         }
2951     }
2952
2953     #[inline]
2954     fn size_hint(&self) -> (usize, Option<usize>) {
2955         let n = self.v.len() / self.chunk_size;
2956         (n, Some(n))
2957     }
2958
2959     #[inline]
2960     fn count(self) -> usize {
2961         self.len()
2962     }
2963
2964     #[inline]
2965     fn nth(&mut self, n: usize) -> Option<Self::Item> {
2966         let (end, overflow) = n.overflowing_mul(self.chunk_size);
2967         if end >= self.v.len() || overflow {
2968             self.v = &[];
2969             None
2970         } else {
2971             let (fst, _) = self.v.split_at(self.v.len() - end);
2972             self.v = fst;
2973             self.next()
2974         }
2975     }
2976
2977     #[inline]
2978     fn last(mut self) -> Option<Self::Item> {
2979         self.next_back()
2980     }
2981
2982     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
2983         let end = self.v.len() - idx * self.chunk_size;
2984         let start = end - self.chunk_size;
2985         // SAFETY: mostly identical to `Chunks::__iterator_get_unchecked`.
2986         unsafe { from_raw_parts(self.v.as_ptr().add(start), self.chunk_size) }
2987     }
2988 }
2989
2990 #[stable(feature = "rchunks", since = "1.31.0")]
2991 impl<'a, T> DoubleEndedIterator for RChunksExact<'a, T> {
2992     #[inline]
2993     fn next_back(&mut self) -> Option<&'a [T]> {
2994         if self.v.len() < self.chunk_size {
2995             None
2996         } else {
2997             let (fst, snd) = self.v.split_at(self.chunk_size);
2998             self.v = snd;
2999             Some(fst)
3000         }
3001     }
3002
3003     #[inline]
3004     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
3005         let len = self.len();
3006         if n >= len {
3007             self.v = &[];
3008             None
3009         } else {
3010             // now that we know that `n` corresponds to a chunk,
3011             // none of these operations can underflow/overflow
3012             let offset = (len - n) * self.chunk_size;
3013             let start = self.v.len() - offset;
3014             let end = start + self.chunk_size;
3015             let nth_back = &self.v[start..end];
3016             self.v = &self.v[end..];
3017             Some(nth_back)
3018         }
3019     }
3020 }
3021
3022 #[stable(feature = "rchunks", since = "1.31.0")]
3023 impl<'a, T> ExactSizeIterator for RChunksExact<'a, T> {
3024     fn is_empty(&self) -> bool {
3025         self.v.is_empty()
3026     }
3027 }
3028
3029 #[unstable(feature = "trusted_len", issue = "37572")]
3030 unsafe impl<T> TrustedLen for RChunksExact<'_, T> {}
3031
3032 #[stable(feature = "rchunks", since = "1.31.0")]
3033 impl<T> FusedIterator for RChunksExact<'_, T> {}
3034
3035 #[doc(hidden)]
3036 #[unstable(feature = "trusted_random_access", issue = "none")]
3037 unsafe impl<'a, T> TrustedRandomAccess for RChunksExact<'a, T> {}
3038
3039 #[doc(hidden)]
3040 #[unstable(feature = "trusted_random_access", issue = "none")]
3041 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksExact<'a, T> {
3042     const MAY_HAVE_SIDE_EFFECT: bool = false;
3043 }
3044
3045 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
3046 /// elements at a time), starting at the end of the slice.
3047 ///
3048 /// When the slice len is not evenly divided by the chunk size, the last up to
3049 /// `chunk_size-1` elements will be omitted but can be retrieved from the
3050 /// [`into_remainder`] function from the iterator.
3051 ///
3052 /// This struct is created by the [`rchunks_exact_mut`] method on [slices].
3053 ///
3054 /// # Example
3055 ///
3056 /// ```
3057 /// let mut slice = ['l', 'o', 'r', 'e', 'm'];
3058 /// let iter = slice.rchunks_exact_mut(2);
3059 /// ```
3060 ///
3061 /// [`rchunks_exact_mut`]: slice::rchunks_exact_mut
3062 /// [`into_remainder`]: RChunksExactMut::into_remainder
3063 /// [slices]: slice
3064 #[derive(Debug)]
3065 #[stable(feature = "rchunks", since = "1.31.0")]
3066 #[must_use = "iterators are lazy and do nothing unless consumed"]
3067 pub struct RChunksExactMut<'a, T: 'a> {
3068     /// # Safety
3069     /// This slice pointer must point at a valid region of `T` with at least length `v.len()`. Normally,
3070     /// those requirements would mean that we could instead use a `&mut [T]` here, but we cannot
3071     /// because `__iterator_get_unchecked` needs to return `&mut [T]`, which guarantees certain aliasing
3072     /// properties that we cannot uphold if we hold on to the full original `&mut [T]`. Wrapping a raw
3073     /// slice instead lets us hand out non-overlapping `&mut [T]` subslices of the slice we wrap.
3074     v: *mut [T],
3075     rem: &'a mut [T],
3076     chunk_size: usize,
3077 }
3078
3079 impl<'a, T> RChunksExactMut<'a, T> {
3080     #[inline]
3081     pub(super) fn new(slice: &'a mut [T], chunk_size: usize) -> Self {
3082         let rem = slice.len() % chunk_size;
3083         // SAFETY: 0 <= rem <= slice.len() by construction above
3084         let (fst, snd) = unsafe { slice.split_at_mut_unchecked(rem) };
3085         Self { v: snd, rem: fst, chunk_size }
3086     }
3087
3088     /// Returns the remainder of the original slice that is not going to be
3089     /// returned by the iterator. The returned slice has at most `chunk_size-1`
3090     /// elements.
3091     #[must_use = "`self` will be dropped if the result is not used"]
3092     #[stable(feature = "rchunks", since = "1.31.0")]
3093     pub fn into_remainder(self) -> &'a mut [T] {
3094         self.rem
3095     }
3096 }
3097
3098 #[stable(feature = "rchunks", since = "1.31.0")]
3099 impl<'a, T> Iterator for RChunksExactMut<'a, T> {
3100     type Item = &'a mut [T];
3101
3102     #[inline]
3103     fn next(&mut self) -> Option<&'a mut [T]> {
3104         if self.v.len() < self.chunk_size {
3105             None
3106         } else {
3107             let len = self.v.len();
3108             // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3109             let (head, tail) = unsafe { self.v.split_at_mut(len - self.chunk_size) };
3110             self.v = head;
3111             // SAFETY: Nothing else points to or will point to the contents of this slice.
3112             Some(unsafe { &mut *tail })
3113         }
3114     }
3115
3116     #[inline]
3117     fn size_hint(&self) -> (usize, Option<usize>) {
3118         let n = self.v.len() / self.chunk_size;
3119         (n, Some(n))
3120     }
3121
3122     #[inline]
3123     fn count(self) -> usize {
3124         self.len()
3125     }
3126
3127     #[inline]
3128     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
3129         let (end, overflow) = n.overflowing_mul(self.chunk_size);
3130         if end >= self.v.len() || overflow {
3131             self.v = &mut [];
3132             None
3133         } else {
3134             let len = self.v.len();
3135             // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3136             let (fst, _) = unsafe { self.v.split_at_mut(len - end) };
3137             self.v = fst;
3138             self.next()
3139         }
3140     }
3141
3142     #[inline]
3143     fn last(mut self) -> Option<Self::Item> {
3144         self.next_back()
3145     }
3146
3147     unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item {
3148         let end = self.v.len() - idx * self.chunk_size;
3149         let start = end - self.chunk_size;
3150         // SAFETY: see comments for `RChunksMut::__iterator_get_unchecked` and `self.v`.
3151         unsafe { from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size) }
3152     }
3153 }
3154
3155 #[stable(feature = "rchunks", since = "1.31.0")]
3156 impl<'a, T> DoubleEndedIterator for RChunksExactMut<'a, T> {
3157     #[inline]
3158     fn next_back(&mut self) -> Option<&'a mut [T]> {
3159         if self.v.len() < self.chunk_size {
3160             None
3161         } else {
3162             // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3163             let (head, tail) = unsafe { self.v.split_at_mut(self.chunk_size) };
3164             self.v = tail;
3165             // SAFETY: Nothing else points to or will point to the contents of this slice.
3166             Some(unsafe { &mut *head })
3167         }
3168     }
3169
3170     #[inline]
3171     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
3172         let len = self.len();
3173         if n >= len {
3174             self.v = &mut [];
3175             None
3176         } else {
3177             // now that we know that `n` corresponds to a chunk,
3178             // none of these operations can underflow/overflow
3179             let offset = (len - n) * self.chunk_size;
3180             let start = self.v.len() - offset;
3181             let end = start + self.chunk_size;
3182             // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3183             let (tmp, tail) = unsafe { self.v.split_at_mut(end) };
3184             // SAFETY: The self.v contract ensures that any split_at_mut is valid.
3185             let (_, nth_back) = unsafe { tmp.split_at_mut(start) };
3186             self.v = tail;
3187             // SAFETY: Nothing else points to or will point to the contents of this slice.
3188             Some(unsafe { &mut *nth_back })
3189         }
3190     }
3191 }
3192
3193 #[stable(feature = "rchunks", since = "1.31.0")]
3194 impl<T> ExactSizeIterator for RChunksExactMut<'_, T> {
3195     fn is_empty(&self) -> bool {
3196         self.v.is_empty()
3197     }
3198 }
3199
3200 #[unstable(feature = "trusted_len", issue = "37572")]
3201 unsafe impl<T> TrustedLen for RChunksExactMut<'_, T> {}
3202
3203 #[stable(feature = "rchunks", since = "1.31.0")]
3204 impl<T> FusedIterator for RChunksExactMut<'_, T> {}
3205
3206 #[doc(hidden)]
3207 #[unstable(feature = "trusted_random_access", issue = "none")]
3208 unsafe impl<'a, T> TrustedRandomAccess for RChunksExactMut<'a, T> {}
3209
3210 #[doc(hidden)]
3211 #[unstable(feature = "trusted_random_access", issue = "none")]
3212 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for RChunksExactMut<'a, T> {
3213     const MAY_HAVE_SIDE_EFFECT: bool = false;
3214 }
3215
3216 #[stable(feature = "rchunks", since = "1.31.0")]
3217 unsafe impl<T> Send for RChunksExactMut<'_, T> where T: Send {}
3218
3219 #[stable(feature = "rchunks", since = "1.31.0")]
3220 unsafe impl<T> Sync for RChunksExactMut<'_, T> where T: Sync {}
3221
3222 #[doc(hidden)]
3223 #[unstable(feature = "trusted_random_access", issue = "none")]
3224 unsafe impl<'a, T> TrustedRandomAccess for Iter<'a, T> {}
3225
3226 #[doc(hidden)]
3227 #[unstable(feature = "trusted_random_access", issue = "none")]
3228 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for Iter<'a, T> {
3229     const MAY_HAVE_SIDE_EFFECT: bool = false;
3230 }
3231
3232 #[doc(hidden)]
3233 #[unstable(feature = "trusted_random_access", issue = "none")]
3234 unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> {}
3235
3236 #[doc(hidden)]
3237 #[unstable(feature = "trusted_random_access", issue = "none")]
3238 unsafe impl<'a, T> TrustedRandomAccessNoCoerce for IterMut<'a, T> {
3239     const MAY_HAVE_SIDE_EFFECT: bool = false;
3240 }
3241
3242 /// An iterator over slice in (non-overlapping) chunks separated by a predicate.
3243 ///
3244 /// This struct is created by the [`group_by`] method on [slices].
3245 ///
3246 /// [`group_by`]: slice::group_by
3247 /// [slices]: slice
3248 #[unstable(feature = "slice_group_by", issue = "80552")]
3249 #[must_use = "iterators are lazy and do nothing unless consumed"]
3250 pub struct GroupBy<'a, T: 'a, P> {
3251     slice: &'a [T],
3252     predicate: P,
3253 }
3254
3255 #[unstable(feature = "slice_group_by", issue = "80552")]
3256 impl<'a, T: 'a, P> GroupBy<'a, T, P> {
3257     pub(super) fn new(slice: &'a [T], predicate: P) -> Self {
3258         GroupBy { slice, predicate }
3259     }
3260 }
3261
3262 #[unstable(feature = "slice_group_by", issue = "80552")]
3263 impl<'a, T: 'a, P> Iterator for GroupBy<'a, T, P>
3264 where
3265     P: FnMut(&T, &T) -> bool,
3266 {
3267     type Item = &'a [T];
3268
3269     #[inline]
3270     fn next(&mut self) -> Option<Self::Item> {
3271         if self.slice.is_empty() {
3272             None
3273         } else {
3274             let mut len = 1;
3275             let mut iter = self.slice.windows(2);
3276             while let Some([l, r]) = iter.next() {
3277                 if (self.predicate)(l, r) { len += 1 } else { break }
3278             }
3279             let (head, tail) = self.slice.split_at(len);
3280             self.slice = tail;
3281             Some(head)
3282         }
3283     }
3284
3285     #[inline]
3286     fn size_hint(&self) -> (usize, Option<usize>) {
3287         if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) }
3288     }
3289
3290     #[inline]
3291     fn last(mut self) -> Option<Self::Item> {
3292         self.next_back()
3293     }
3294 }
3295
3296 #[unstable(feature = "slice_group_by", issue = "80552")]
3297 impl<'a, T: 'a, P> DoubleEndedIterator for GroupBy<'a, T, P>
3298 where
3299     P: FnMut(&T, &T) -> bool,
3300 {
3301     #[inline]
3302     fn next_back(&mut self) -> Option<Self::Item> {
3303         if self.slice.is_empty() {
3304             None
3305         } else {
3306             let mut len = 1;
3307             let mut iter = self.slice.windows(2);
3308             while let Some([l, r]) = iter.next_back() {
3309                 if (self.predicate)(l, r) { len += 1 } else { break }
3310             }
3311             let (head, tail) = self.slice.split_at(self.slice.len() - len);
3312             self.slice = head;
3313             Some(tail)
3314         }
3315     }
3316 }
3317
3318 #[unstable(feature = "slice_group_by", issue = "80552")]
3319 impl<'a, T: 'a, P> FusedIterator for GroupBy<'a, T, P> where P: FnMut(&T, &T) -> bool {}
3320
3321 #[unstable(feature = "slice_group_by", issue = "80552")]
3322 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for GroupBy<'a, T, P> {
3323     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3324         f.debug_struct("GroupBy").field("slice", &self.slice).finish()
3325     }
3326 }
3327
3328 /// An iterator over slice in (non-overlapping) mutable chunks separated
3329 /// by a predicate.
3330 ///
3331 /// This struct is created by the [`group_by_mut`] method on [slices].
3332 ///
3333 /// [`group_by_mut`]: slice::group_by_mut
3334 /// [slices]: slice
3335 #[unstable(feature = "slice_group_by", issue = "80552")]
3336 #[must_use = "iterators are lazy and do nothing unless consumed"]
3337 pub struct GroupByMut<'a, T: 'a, P> {
3338     slice: &'a mut [T],
3339     predicate: P,
3340 }
3341
3342 #[unstable(feature = "slice_group_by", issue = "80552")]
3343 impl<'a, T: 'a, P> GroupByMut<'a, T, P> {
3344     pub(super) fn new(slice: &'a mut [T], predicate: P) -> Self {
3345         GroupByMut { slice, predicate }
3346     }
3347 }
3348
3349 #[unstable(feature = "slice_group_by", issue = "80552")]
3350 impl<'a, T: 'a, P> Iterator for GroupByMut<'a, T, P>
3351 where
3352     P: FnMut(&T, &T) -> bool,
3353 {
3354     type Item = &'a mut [T];
3355
3356     #[inline]
3357     fn next(&mut self) -> Option<Self::Item> {
3358         if self.slice.is_empty() {
3359             None
3360         } else {
3361             let mut len = 1;
3362             let mut iter = self.slice.windows(2);
3363             while let Some([l, r]) = iter.next() {
3364                 if (self.predicate)(l, r) { len += 1 } else { break }
3365             }
3366             let slice = mem::take(&mut self.slice);
3367             let (head, tail) = slice.split_at_mut(len);
3368             self.slice = tail;
3369             Some(head)
3370         }
3371     }
3372
3373     #[inline]
3374     fn size_hint(&self) -> (usize, Option<usize>) {
3375         if self.slice.is_empty() { (0, Some(0)) } else { (1, Some(self.slice.len())) }
3376     }
3377
3378     #[inline]
3379     fn last(mut self) -> Option<Self::Item> {
3380         self.next_back()
3381     }
3382 }
3383
3384 #[unstable(feature = "slice_group_by", issue = "80552")]
3385 impl<'a, T: 'a, P> DoubleEndedIterator for GroupByMut<'a, T, P>
3386 where
3387     P: FnMut(&T, &T) -> bool,
3388 {
3389     #[inline]
3390     fn next_back(&mut self) -> Option<Self::Item> {
3391         if self.slice.is_empty() {
3392             None
3393         } else {
3394             let mut len = 1;
3395             let mut iter = self.slice.windows(2);
3396             while let Some([l, r]) = iter.next_back() {
3397                 if (self.predicate)(l, r) { len += 1 } else { break }
3398             }
3399             let slice = mem::take(&mut self.slice);
3400             let (head, tail) = slice.split_at_mut(slice.len() - len);
3401             self.slice = head;
3402             Some(tail)
3403         }
3404     }
3405 }
3406
3407 #[unstable(feature = "slice_group_by", issue = "80552")]
3408 impl<'a, T: 'a, P> FusedIterator for GroupByMut<'a, T, P> where P: FnMut(&T, &T) -> bool {}
3409
3410 #[unstable(feature = "slice_group_by", issue = "80552")]
3411 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for GroupByMut<'a, T, P> {
3412     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3413         f.debug_struct("GroupByMut").field("slice", &self.slice).finish()
3414     }
3415 }