library/core/src/slice/iter.rs

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