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