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