src/libcore/slice/mod.rs

   1 // Copyright 2012-2017 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Slice management and manipulation
  12 //!
  13 //! For more details see [`std::slice`].
  14 //!
  15 //! [`std::slice`]: ../../std/slice/index.html
  16
  17 #![stable(feature = "rust1", since = "1.0.0")]
  18
  19 // How this module is organized.
  20 //
  21 // The library infrastructure for slices is fairly messy. There's
  22 // a lot of stuff defined here. Let's keep it clean.
  23 //
  24 // Since slices don't support inherent methods; all operations
  25 // on them are defined on traits, which are then re-exported from
  26 // the prelude for convenience. So there are a lot of traits here.
  27 //
  28 // The layout of this file is thus:
  29 //
  30 // * Slice-specific 'extension' traits and their implementations. This
  31 //   is where most of the slice API resides.
  32 // * Implementations of a few common traits with important slice ops.
  33 // * Definitions of a bunch of iterators.
  34 // * Free functions.
  35 // * The `raw` and `bytes` submodules.
  36 // * Boilerplate trait implementations.
  37
  38 use cmp::Ordering::{self, Less, Equal, Greater};
  39 use cmp;
  40 use fmt;
  41 use intrinsics::assume;
  42 use iter::*;
  43 use ops::{FnMut, Try, self};
  44 use option::Option;
  45 use option::Option::{None, Some};
  46 use result::Result;
  47 use result::Result::{Ok, Err};
  48 use ptr;
  49 use mem;
  50 use marker::{Copy, Send, Sync, Sized, self};
  51 use iter_private::TrustedRandomAccess;
  52
  53 #[unstable(feature = "slice_internals", issue = "0",
  54            reason = "exposed from core to be reused in std; use the memchr crate")]
  55 /// Pure rust memchr implementation, taken from rust-memchr
  56 pub mod memchr;
  57
  58 mod rotate;
  59 mod sort;
  60
  61 #[repr(C)]
  62 union Repr<'a, T: 'a> {
  63     rust: &'a [T],
  64     rust_mut: &'a mut [T],
  65     raw: FatPtr<T>,
  66 }
  67
  68 #[repr(C)]
  69 struct FatPtr<T> {
  70     data: *const T,
  71     len: usize,
  72 }
  73
  74 //
  75 // Extension traits
  76 //
  77
  78 // Use macros to be generic over const/mut
  79 macro_rules! slice_offset {
  80     ($ptr:expr, $by:expr) => {{
  81         let ptr = $ptr;
  82         if size_from_ptr(ptr) == 0 {
  83             (ptr as *mut i8).wrapping_offset($by) as _
  84         } else {
  85             ptr.offset($by)
  86         }
  87     }};
  88 }
  89
  90 // make a &T from a *const T
  91 macro_rules! make_ref {
  92     ($ptr:expr) => {{
  93         let ptr = $ptr;
  94         if size_from_ptr(ptr) == 0 {
  95             // Use a non-null pointer value
  96             &*(1 as *mut _)
  97         } else {
  98             &*ptr
  99         }
 100     }};
 101 }
 102
 103 // make a &mut T from a *mut T
 104 macro_rules! make_ref_mut {
 105     ($ptr:expr) => {{
 106         let ptr = $ptr;
 107         if size_from_ptr(ptr) == 0 {
 108             // Use a non-null pointer value
 109             &mut *(1 as *mut _)
 110         } else {
 111             &mut *ptr
 112         }
 113     }};
 114 }
 115
 116 #[lang = "slice"]
 117 #[cfg(not(test))]
 118 impl<T> [T] {
 119     /// Returns the number of elements in the slice.
 120     ///
 121     /// # Examples
 122     ///
 123     /// ```
 124     /// let a = [1, 2, 3];
 125     /// assert_eq!(a.len(), 3);
 126     /// ```
 127     #[stable(feature = "rust1", since = "1.0.0")]
 128     #[inline]
 129     #[rustc_const_unstable(feature = "const_slice_len")]
 130     pub const fn len(&self) -> usize {
 131         unsafe {
 132             Repr { rust: self }.raw.len
 133         }
 134     }
 135
 136     /// Returns `true` if the slice has a length of 0.
 137     ///
 138     /// # Examples
 139     ///
 140     /// ```
 141     /// let a = [1, 2, 3];
 142     /// assert!(!a.is_empty());
 143     /// ```
 144     #[stable(feature = "rust1", since = "1.0.0")]
 145     #[inline]
 146     #[rustc_const_unstable(feature = "const_slice_len")]
 147     pub const fn is_empty(&self) -> bool {
 148         self.len() == 0
 149     }
 150
 151     /// Returns the first element of the slice, or `None` if it is empty.
 152     ///
 153     /// # Examples
 154     ///
 155     /// ```
 156     /// let v = [10, 40, 30];
 157     /// assert_eq!(Some(&10), v.first());
 158     ///
 159     /// let w: &[i32] = &[];
 160     /// assert_eq!(None, w.first());
 161     /// ```
 162     #[stable(feature = "rust1", since = "1.0.0")]
 163     #[inline]
 164     pub fn first(&self) -> Option<&T> {
 165         if self.is_empty() { None } else { Some(&self[0]) }
 166     }
 167
 168     /// Returns a mutable pointer to the first element of the slice, or `None` if it is empty.
 169     ///
 170     /// # Examples
 171     ///
 172     /// ```
 173     /// let x = &mut [0, 1, 2];
 174     ///
 175     /// if let Some(first) = x.first_mut() {
 176     ///     *first = 5;
 177     /// }
 178     /// assert_eq!(x, &[5, 1, 2]);
 179     /// ```
 180     #[stable(feature = "rust1", since = "1.0.0")]
 181     #[inline]
 182     pub fn first_mut(&mut self) -> Option<&mut T> {
 183         if self.is_empty() { None } else { Some(&mut self[0]) }
 184     }
 185
 186     /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
 187     ///
 188     /// # Examples
 189     ///
 190     /// ```
 191     /// let x = &[0, 1, 2];
 192     ///
 193     /// if let Some((first, elements)) = x.split_first() {
 194     ///     assert_eq!(first, &0);
 195     ///     assert_eq!(elements, &[1, 2]);
 196     /// }
 197     /// ```
 198     #[stable(feature = "slice_splits", since = "1.5.0")]
 199     #[inline]
 200     pub fn split_first(&self) -> Option<(&T, &[T])> {
 201         if self.is_empty() { None } else { Some((&self[0], &self[1..])) }
 202     }
 203
 204     /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
 205     ///
 206     /// # Examples
 207     ///
 208     /// ```
 209     /// let x = &mut [0, 1, 2];
 210     ///
 211     /// if let Some((first, elements)) = x.split_first_mut() {
 212     ///     *first = 3;
 213     ///     elements[0] = 4;
 214     ///     elements[1] = 5;
 215     /// }
 216     /// assert_eq!(x, &[3, 4, 5]);
 217     /// ```
 218     #[stable(feature = "slice_splits", since = "1.5.0")]
 219     #[inline]
 220     pub fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
 221         if self.is_empty() { None } else {
 222             let split = self.split_at_mut(1);
 223             Some((&mut split.0[0], split.1))
 224         }
 225     }
 226
 227     /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
 228     ///
 229     /// # Examples
 230     ///
 231     /// ```
 232     /// let x = &[0, 1, 2];
 233     ///
 234     /// if let Some((last, elements)) = x.split_last() {
 235     ///     assert_eq!(last, &2);
 236     ///     assert_eq!(elements, &[0, 1]);
 237     /// }
 238     /// ```
 239     #[stable(feature = "slice_splits", since = "1.5.0")]
 240     #[inline]
 241     pub fn split_last(&self) -> Option<(&T, &[T])> {
 242         let len = self.len();
 243         if len == 0 { None } else { Some((&self[len - 1], &self[..(len - 1)])) }
 244     }
 245
 246     /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
 247     ///
 248     /// # Examples
 249     ///
 250     /// ```
 251     /// let x = &mut [0, 1, 2];
 252     ///
 253     /// if let Some((last, elements)) = x.split_last_mut() {
 254     ///     *last = 3;
 255     ///     elements[0] = 4;
 256     ///     elements[1] = 5;
 257     /// }
 258     /// assert_eq!(x, &[4, 5, 3]);
 259     /// ```
 260     #[stable(feature = "slice_splits", since = "1.5.0")]
 261     #[inline]
 262     pub fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
 263         let len = self.len();
 264         if len == 0 { None } else {
 265             let split = self.split_at_mut(len - 1);
 266             Some((&mut split.1[0], split.0))
 267         }
 268
 269     }
 270
 271     /// Returns the last element of the slice, or `None` if it is empty.
 272     ///
 273     /// # Examples
 274     ///
 275     /// ```
 276     /// let v = [10, 40, 30];
 277     /// assert_eq!(Some(&30), v.last());
 278     ///
 279     /// let w: &[i32] = &[];
 280     /// assert_eq!(None, w.last());
 281     /// ```
 282     #[stable(feature = "rust1", since = "1.0.0")]
 283     #[inline]
 284     pub fn last(&self) -> Option<&T> {
 285         if self.is_empty() { None } else { Some(&self[self.len() - 1]) }
 286     }
 287
 288     /// Returns a mutable pointer to the last item in the slice.
 289     ///
 290     /// # Examples
 291     ///
 292     /// ```
 293     /// let x = &mut [0, 1, 2];
 294     ///
 295     /// if let Some(last) = x.last_mut() {
 296     ///     *last = 10;
 297     /// }
 298     /// assert_eq!(x, &[0, 1, 10]);
 299     /// ```
 300     #[stable(feature = "rust1", since = "1.0.0")]
 301     #[inline]
 302     pub fn last_mut(&mut self) -> Option<&mut T> {
 303         let len = self.len();
 304         if len == 0 { return None; }
 305         Some(&mut self[len - 1])
 306     }
 307
 308     /// Returns a reference to an element or subslice depending on the type of
 309     /// index.
 310     ///
 311     /// - If given a position, returns a reference to the element at that
 312     ///   position or `None` if out of bounds.
 313     /// - If given a range, returns the subslice corresponding to that range,
 314     ///   or `None` if out of bounds.
 315     ///
 316     /// # Examples
 317     ///
 318     /// ```
 319     /// let v = [10, 40, 30];
 320     /// assert_eq!(Some(&40), v.get(1));
 321     /// assert_eq!(Some(&[10, 40][..]), v.get(0..2));
 322     /// assert_eq!(None, v.get(3));
 323     /// assert_eq!(None, v.get(0..4));
 324     /// ```
 325     #[stable(feature = "rust1", since = "1.0.0")]
 326     #[inline]
 327     pub fn get<I>(&self, index: I) -> Option<&I::Output>
 328         where I: SliceIndex<Self>
 329     {
 330         index.get(self)
 331     }
 332
 333     /// Returns a mutable reference to an element or subslice depending on the
 334     /// type of index (see [`get`]) or `None` if the index is out of bounds.
 335     ///
 336     /// [`get`]: #method.get
 337     ///
 338     /// # Examples
 339     ///
 340     /// ```
 341     /// let x = &mut [0, 1, 2];
 342     ///
 343     /// if let Some(elem) = x.get_mut(1) {
 344     ///     *elem = 42;
 345     /// }
 346     /// assert_eq!(x, &[0, 42, 2]);
 347     /// ```
 348     #[stable(feature = "rust1", since = "1.0.0")]
 349     #[inline]
 350     pub fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
 351         where I: SliceIndex<Self>
 352     {
 353         index.get_mut(self)
 354     }
 355
 356     /// Returns a reference to an element or subslice, without doing bounds
 357     /// checking.
 358     ///
 359     /// This is generally not recommended, use with caution! For a safe
 360     /// alternative see [`get`].
 361     ///
 362     /// [`get`]: #method.get
 363     ///
 364     /// # Examples
 365     ///
 366     /// ```
 367     /// let x = &[1, 2, 4];
 368     ///
 369     /// unsafe {
 370     ///     assert_eq!(x.get_unchecked(1), &2);
 371     /// }
 372     /// ```
 373     #[stable(feature = "rust1", since = "1.0.0")]
 374     #[inline]
 375     pub unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
 376         where I: SliceIndex<Self>
 377     {
 378         index.get_unchecked(self)
 379     }
 380
 381     /// Returns a mutable reference to an element or subslice, without doing
 382     /// bounds checking.
 383     ///
 384     /// This is generally not recommended, use with caution! For a safe
 385     /// alternative see [`get_mut`].
 386     ///
 387     /// [`get_mut`]: #method.get_mut
 388     ///
 389     /// # Examples
 390     ///
 391     /// ```
 392     /// let x = &mut [1, 2, 4];
 393     ///
 394     /// unsafe {
 395     ///     let elem = x.get_unchecked_mut(1);
 396     ///     *elem = 13;
 397     /// }
 398     /// assert_eq!(x, &[1, 13, 4]);
 399     /// ```
 400     #[stable(feature = "rust1", since = "1.0.0")]
 401     #[inline]
 402     pub unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
 403         where I: SliceIndex<Self>
 404     {
 405         index.get_unchecked_mut(self)
 406     }
 407
 408     /// Returns a raw pointer to the slice's buffer.
 409     ///
 410     /// The caller must ensure that the slice outlives the pointer this
 411     /// function returns, or else it will end up pointing to garbage.
 412     ///
 413     /// Modifying the container referenced by this slice may cause its buffer
 414     /// to be reallocated, which would also make any pointers to it invalid.
 415     ///
 416     /// # Examples
 417     ///
 418     /// ```
 419     /// let x = &[1, 2, 4];
 420     /// let x_ptr = x.as_ptr();
 421     ///
 422     /// unsafe {
 423     ///     for i in 0..x.len() {
 424     ///         assert_eq!(x.get_unchecked(i), &*x_ptr.offset(i as isize));
 425     ///     }
 426     /// }
 427     /// ```
 428     #[stable(feature = "rust1", since = "1.0.0")]
 429     #[inline]
 430     #[rustc_const_unstable(feature = "const_slice_as_ptr")]
 431     pub const fn as_ptr(&self) -> *const T {
 432         self as *const [T] as *const T
 433     }
 434
 435     /// Returns an unsafe mutable pointer to the slice's buffer.
 436     ///
 437     /// The caller must ensure that the slice outlives the pointer this
 438     /// function returns, or else it will end up pointing to garbage.
 439     ///
 440     /// Modifying the container referenced by this slice may cause its buffer
 441     /// to be reallocated, which would also make any pointers to it invalid.
 442     ///
 443     /// # Examples
 444     ///
 445     /// ```
 446     /// let x = &mut [1, 2, 4];
 447     /// let x_ptr = x.as_mut_ptr();
 448     ///
 449     /// unsafe {
 450     ///     for i in 0..x.len() {
 451     ///         *x_ptr.offset(i as isize) += 2;
 452     ///     }
 453     /// }
 454     /// assert_eq!(x, &[3, 4, 6]);
 455     /// ```
 456     #[stable(feature = "rust1", since = "1.0.0")]
 457     #[inline]
 458     pub fn as_mut_ptr(&mut self) -> *mut T {
 459         self as *mut [T] as *mut T
 460     }
 461
 462     /// Swaps two elements in the slice.
 463     ///
 464     /// # Arguments
 465     ///
 466     /// * a - The index of the first element
 467     /// * b - The index of the second element
 468     ///
 469     /// # Panics
 470     ///
 471     /// Panics if `a` or `b` are out of bounds.
 472     ///
 473     /// # Examples
 474     ///
 475     /// ```
 476     /// let mut v = ["a", "b", "c", "d"];
 477     /// v.swap(1, 3);
 478     /// assert!(v == ["a", "d", "c", "b"]);
 479     /// ```
 480     #[stable(feature = "rust1", since = "1.0.0")]
 481     #[inline]
 482     pub fn swap(&mut self, a: usize, b: usize) {
 483         unsafe {
 484             // Can't take two mutable loans from one vector, so instead just cast
 485             // them to their raw pointers to do the swap
 486             let pa: *mut T = &mut self[a];
 487             let pb: *mut T = &mut self[b];
 488             ptr::swap(pa, pb);
 489         }
 490     }
 491
 492     /// Reverses the order of elements in the slice, in place.
 493     ///
 494     /// # Examples
 495     ///
 496     /// ```
 497     /// let mut v = [1, 2, 3];
 498     /// v.reverse();
 499     /// assert!(v == [3, 2, 1]);
 500     /// ```
 501     #[stable(feature = "rust1", since = "1.0.0")]
 502     #[inline]
 503     pub fn reverse(&mut self) {
 504         let mut i: usize = 0;
 505         let ln = self.len();
 506
 507         // For very small types, all the individual reads in the normal
 508         // path perform poorly.  We can do better, given efficient unaligned
 509         // load/store, by loading a larger chunk and reversing a register.
 510
 511         // Ideally LLVM would do this for us, as it knows better than we do
 512         // whether unaligned reads are efficient (since that changes between
 513         // different ARM versions, for example) and what the best chunk size
 514         // would be.  Unfortunately, as of LLVM 4.0 (2017-05) it only unrolls
 515         // the loop, so we need to do this ourselves.  (Hypothesis: reverse
 516         // is troublesome because the sides can be aligned differently --
 517         // will be, when the length is odd -- so there's no way of emitting
 518         // pre- and postludes to use fully-aligned SIMD in the middle.)
 519
 520         let fast_unaligned =
 521             cfg!(any(target_arch = "x86", target_arch = "x86_64"));
 522
 523         if fast_unaligned && mem::size_of::<T>() == 1 {
 524             // Use the llvm.bswap intrinsic to reverse u8s in a usize
 525             let chunk = mem::size_of::<usize>();
 526             while i + chunk - 1 < ln / 2 {
 527                 unsafe {
 528                     let pa: *mut T = self.get_unchecked_mut(i);
 529                     let pb: *mut T = self.get_unchecked_mut(ln - i - chunk);
 530                     let va = ptr::read_unaligned(pa as *mut usize);
 531                     let vb = ptr::read_unaligned(pb as *mut usize);
 532                     ptr::write_unaligned(pa as *mut usize, vb.swap_bytes());
 533                     ptr::write_unaligned(pb as *mut usize, va.swap_bytes());
 534                 }
 535                 i += chunk;
 536             }
 537         }
 538
 539         if fast_unaligned && mem::size_of::<T>() == 2 {
 540             // Use rotate-by-16 to reverse u16s in a u32
 541             let chunk = mem::size_of::<u32>() / 2;
 542             while i + chunk - 1 < ln / 2 {
 543                 unsafe {
 544                     let pa: *mut T = self.get_unchecked_mut(i);
 545                     let pb: *mut T = self.get_unchecked_mut(ln - i - chunk);
 546                     let va = ptr::read_unaligned(pa as *mut u32);
 547                     let vb = ptr::read_unaligned(pb as *mut u32);
 548                     ptr::write_unaligned(pa as *mut u32, vb.rotate_left(16));
 549                     ptr::write_unaligned(pb as *mut u32, va.rotate_left(16));
 550                 }
 551                 i += chunk;
 552             }
 553         }
 554
 555         while i < ln / 2 {
 556             // Unsafe swap to avoid the bounds check in safe swap.
 557             unsafe {
 558                 let pa: *mut T = self.get_unchecked_mut(i);
 559                 let pb: *mut T = self.get_unchecked_mut(ln - i - 1);
 560                 ptr::swap(pa, pb);
 561             }
 562             i += 1;
 563         }
 564     }
 565
 566     /// Returns an iterator over the slice.
 567     ///
 568     /// # Examples
 569     ///
 570     /// ```
 571     /// let x = &[1, 2, 4];
 572     /// let mut iterator = x.iter();
 573     ///
 574     /// assert_eq!(iterator.next(), Some(&1));
 575     /// assert_eq!(iterator.next(), Some(&2));
 576     /// assert_eq!(iterator.next(), Some(&4));
 577     /// assert_eq!(iterator.next(), None);
 578     /// ```
 579     #[stable(feature = "rust1", since = "1.0.0")]
 580     #[inline]
 581     pub fn iter(&self) -> Iter<T> {
 582         unsafe {
 583             let p = if mem::size_of::<T>() == 0 {
 584                 1 as *const _
 585             } else {
 586                 let p = self.as_ptr();
 587                 assume(!p.is_null());
 588                 p
 589             };
 590
 591             Iter {
 592                 ptr: p,
 593                 end: slice_offset!(p, self.len() as isize),
 594                 _marker: marker::PhantomData
 595             }
 596         }
 597     }
 598
 599     /// Returns an iterator that allows modifying each value.
 600     ///
 601     /// # Examples
 602     ///
 603     /// ```
 604     /// let x = &mut [1, 2, 4];
 605     /// for elem in x.iter_mut() {
 606     ///     *elem += 2;
 607     /// }
 608     /// assert_eq!(x, &[3, 4, 6]);
 609     /// ```
 610     #[stable(feature = "rust1", since = "1.0.0")]
 611     #[inline]
 612     pub fn iter_mut(&mut self) -> IterMut<T> {
 613         unsafe {
 614             let p = if mem::size_of::<T>() == 0 {
 615                 1 as *mut _
 616             } else {
 617                 let p = self.as_mut_ptr();
 618                 assume(!p.is_null());
 619                 p
 620             };
 621
 622             IterMut {
 623                 ptr: p,
 624                 end: slice_offset!(p, self.len() as isize),
 625                 _marker: marker::PhantomData
 626             }
 627         }
 628     }
 629
 630     /// Returns an iterator over all contiguous windows of length
 631     /// `size`. The windows overlap. If the slice is shorter than
 632     /// `size`, the iterator returns no values.
 633     ///
 634     /// # Panics
 635     ///
 636     /// Panics if `size` is 0.
 637     ///
 638     /// # Examples
 639     ///
 640     /// ```
 641     /// let slice = ['r', 'u', 's', 't'];
 642     /// let mut iter = slice.windows(2);
 643     /// assert_eq!(iter.next().unwrap(), &['r', 'u']);
 644     /// assert_eq!(iter.next().unwrap(), &['u', 's']);
 645     /// assert_eq!(iter.next().unwrap(), &['s', 't']);
 646     /// assert!(iter.next().is_none());
 647     /// ```
 648     ///
 649     /// If the slice is shorter than `size`:
 650     ///
 651     /// ```
 652     /// let slice = ['f', 'o', 'o'];
 653     /// let mut iter = slice.windows(4);
 654     /// assert!(iter.next().is_none());
 655     /// ```
 656     #[stable(feature = "rust1", since = "1.0.0")]
 657     #[inline]
 658     pub fn windows(&self, size: usize) -> Windows<T> {
 659         assert!(size != 0);
 660         Windows { v: self, size: size }
 661     }
 662
 663     /// Returns an iterator over `chunk_size` elements of the slice at a
 664     /// time. The chunks are slices and do not overlap. If `chunk_size` does
 665     /// not divide the length of the slice, then the last chunk will
 666     /// not have length `chunk_size`.
 667     ///
 668     /// See [`exact_chunks`] for a variant of this iterator that returns chunks
 669     /// of always exactly `chunk_size` elements.
 670     ///
 671     /// # Panics
 672     ///
 673     /// Panics if `chunk_size` is 0.
 674     ///
 675     /// # Examples
 676     ///
 677     /// ```
 678     /// let slice = ['l', 'o', 'r', 'e', 'm'];
 679     /// let mut iter = slice.chunks(2);
 680     /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
 681     /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
 682     /// assert_eq!(iter.next().unwrap(), &['m']);
 683     /// assert!(iter.next().is_none());
 684     /// ```
 685     ///
 686     /// [`exact_chunks`]: #method.exact_chunks
 687     #[stable(feature = "rust1", since = "1.0.0")]
 688     #[inline]
 689     pub fn chunks(&self, chunk_size: usize) -> Chunks<T> {
 690         assert!(chunk_size != 0);
 691         Chunks { v: self, chunk_size: chunk_size }
 692     }
 693
 694     /// Returns an iterator over `chunk_size` elements of the slice at a time.
 695     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does
 696     /// not divide the length of the slice, then the last chunk will not
 697     /// have length `chunk_size`.
 698     ///
 699     /// See [`exact_chunks_mut`] for a variant of this iterator that returns chunks
 700     /// of always exactly `chunk_size` elements.
 701     ///
 702     /// # Panics
 703     ///
 704     /// Panics if `chunk_size` is 0.
 705     ///
 706     /// # Examples
 707     ///
 708     /// ```
 709     /// let v = &mut [0, 0, 0, 0, 0];
 710     /// let mut count = 1;
 711     ///
 712     /// for chunk in v.chunks_mut(2) {
 713     ///     for elem in chunk.iter_mut() {
 714     ///         *elem += count;
 715     ///     }
 716     ///     count += 1;
 717     /// }
 718     /// assert_eq!(v, &[1, 1, 2, 2, 3]);
 719     /// ```
 720     ///
 721     /// [`exact_chunks_mut`]: #method.exact_chunks_mut
 722     #[stable(feature = "rust1", since = "1.0.0")]
 723     #[inline]
 724     pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> {
 725         assert!(chunk_size != 0);
 726         ChunksMut { v: self, chunk_size: chunk_size }
 727     }
 728
 729     /// Returns an iterator over `chunk_size` elements of the slice at a
 730     /// time. The chunks are slices and do not overlap. If `chunk_size` does
 731     /// not divide the length of the slice, then the last up to `chunk_size-1`
 732     /// elements will be omitted.
 733     ///
 734     /// Due to each chunk having exactly `chunk_size` elements, the compiler
 735     /// can often optimize the resulting code better than in the case of
 736     /// [`chunks`].
 737     ///
 738     /// # Panics
 739     ///
 740     /// Panics if `chunk_size` is 0.
 741     ///
 742     /// # Examples
 743     ///
 744     /// ```
 745     /// #![feature(exact_chunks)]
 746     ///
 747     /// let slice = ['l', 'o', 'r', 'e', 'm'];
 748     /// let mut iter = slice.exact_chunks(2);
 749     /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
 750     /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
 751     /// assert!(iter.next().is_none());
 752     /// ```
 753     ///
 754     /// [`chunks`]: #method.chunks
 755     #[unstable(feature = "exact_chunks", issue = "47115")]
 756     #[inline]
 757     pub fn exact_chunks(&self, chunk_size: usize) -> ExactChunks<T> {
 758         assert!(chunk_size != 0);
 759         let rem = self.len() % chunk_size;
 760         let len = self.len() - rem;
 761         ExactChunks { v: &self[..len], chunk_size: chunk_size}
 762     }
 763
 764     /// Returns an iterator over `chunk_size` elements of the slice at a time.
 765     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does
 766     /// not divide the length of the slice, then the last up to `chunk_size-1`
 767     /// elements will be omitted.
 768     ///
 769     ///
 770     /// Due to each chunk having exactly `chunk_size` elements, the compiler
 771     /// can often optimize the resulting code better than in the case of
 772     /// [`chunks_mut`].
 773     ///
 774     /// # Panics
 775     ///
 776     /// Panics if `chunk_size` is 0.
 777     ///
 778     /// # Examples
 779     ///
 780     /// ```
 781     /// #![feature(exact_chunks)]
 782     ///
 783     /// let v = &mut [0, 0, 0, 0, 0];
 784     /// let mut count = 1;
 785     ///
 786     /// for chunk in v.exact_chunks_mut(2) {
 787     ///     for elem in chunk.iter_mut() {
 788     ///         *elem += count;
 789     ///     }
 790     ///     count += 1;
 791     /// }
 792     /// assert_eq!(v, &[1, 1, 2, 2, 0]);
 793     /// ```
 794     ///
 795     /// [`chunks_mut`]: #method.chunks_mut
 796     #[unstable(feature = "exact_chunks", issue = "47115")]
 797     #[inline]
 798     pub fn exact_chunks_mut(&mut self, chunk_size: usize) -> ExactChunksMut<T> {
 799         assert!(chunk_size != 0);
 800         let rem = self.len() % chunk_size;
 801         let len = self.len() - rem;
 802         ExactChunksMut { v: &mut self[..len], chunk_size: chunk_size}
 803     }
 804
 805     /// Divides one slice into two at an index.
 806     ///
 807     /// The first will contain all indices from `[0, mid)` (excluding
 808     /// the index `mid` itself) and the second will contain all
 809     /// indices from `[mid, len)` (excluding the index `len` itself).
 810     ///
 811     /// # Panics
 812     ///
 813     /// Panics if `mid > len`.
 814     ///
 815     /// # Examples
 816     ///
 817     /// ```
 818     /// let v = [1, 2, 3, 4, 5, 6];
 819     ///
 820     /// {
 821     ///    let (left, right) = v.split_at(0);
 822     ///    assert!(left == []);
 823     ///    assert!(right == [1, 2, 3, 4, 5, 6]);
 824     /// }
 825     ///
 826     /// {
 827     ///     let (left, right) = v.split_at(2);
 828     ///     assert!(left == [1, 2]);
 829     ///     assert!(right == [3, 4, 5, 6]);
 830     /// }
 831     ///
 832     /// {
 833     ///     let (left, right) = v.split_at(6);
 834     ///     assert!(left == [1, 2, 3, 4, 5, 6]);
 835     ///     assert!(right == []);
 836     /// }
 837     /// ```
 838     #[stable(feature = "rust1", since = "1.0.0")]
 839     #[inline]
 840     pub fn split_at(&self, mid: usize) -> (&[T], &[T]) {
 841         (&self[..mid], &self[mid..])
 842     }
 843
 844     /// Divides one mutable slice into two at an index.
 845     ///
 846     /// The first will contain all indices from `[0, mid)` (excluding
 847     /// the index `mid` itself) and the second will contain all
 848     /// indices from `[mid, len)` (excluding the index `len` itself).
 849     ///
 850     /// # Panics
 851     ///
 852     /// Panics if `mid > len`.
 853     ///
 854     /// # Examples
 855     ///
 856     /// ```
 857     /// let mut v = [1, 0, 3, 0, 5, 6];
 858     /// // scoped to restrict the lifetime of the borrows
 859     /// {
 860     ///     let (left, right) = v.split_at_mut(2);
 861     ///     assert!(left == [1, 0]);
 862     ///     assert!(right == [3, 0, 5, 6]);
 863     ///     left[1] = 2;
 864     ///     right[1] = 4;
 865     /// }
 866     /// assert!(v == [1, 2, 3, 4, 5, 6]);
 867     /// ```
 868     #[stable(feature = "rust1", since = "1.0.0")]
 869     #[inline]
 870     pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
 871         let len = self.len();
 872         let ptr = self.as_mut_ptr();
 873
 874         unsafe {
 875             assert!(mid <= len);
 876
 877             (from_raw_parts_mut(ptr, mid),
 878              from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
 879         }
 880     }
 881
 882     /// Returns an iterator over subslices separated by elements that match
 883     /// `pred`. The matched element is not contained in the subslices.
 884     ///
 885     /// # Examples
 886     ///
 887     /// ```
 888     /// let slice = [10, 40, 33, 20];
 889     /// let mut iter = slice.split(|num| num % 3 == 0);
 890     ///
 891     /// assert_eq!(iter.next().unwrap(), &[10, 40]);
 892     /// assert_eq!(iter.next().unwrap(), &[20]);
 893     /// assert!(iter.next().is_none());
 894     /// ```
 895     ///
 896     /// If the first element is matched, an empty slice will be the first item
 897     /// returned by the iterator. Similarly, if the last element in the slice
 898     /// is matched, an empty slice will be the last item returned by the
 899     /// iterator:
 900     ///
 901     /// ```
 902     /// let slice = [10, 40, 33];
 903     /// let mut iter = slice.split(|num| num % 3 == 0);
 904     ///
 905     /// assert_eq!(iter.next().unwrap(), &[10, 40]);
 906     /// assert_eq!(iter.next().unwrap(), &[]);
 907     /// assert!(iter.next().is_none());
 908     /// ```
 909     ///
 910     /// If two matched elements are directly adjacent, an empty slice will be
 911     /// present between them:
 912     ///
 913     /// ```
 914     /// let slice = [10, 6, 33, 20];
 915     /// let mut iter = slice.split(|num| num % 3 == 0);
 916     ///
 917     /// assert_eq!(iter.next().unwrap(), &[10]);
 918     /// assert_eq!(iter.next().unwrap(), &[]);
 919     /// assert_eq!(iter.next().unwrap(), &[20]);
 920     /// assert!(iter.next().is_none());
 921     /// ```
 922     #[stable(feature = "rust1", since = "1.0.0")]
 923     #[inline]
 924     pub fn split<F>(&self, pred: F) -> Split<T, F>
 925         where F: FnMut(&T) -> bool
 926     {
 927         Split {
 928             v: self,
 929             pred,
 930             finished: false
 931         }
 932     }
 933
 934     /// Returns an iterator over mutable subslices separated by elements that
 935     /// match `pred`. The matched element is not contained in the subslices.
 936     ///
 937     /// # Examples
 938     ///
 939     /// ```
 940     /// let mut v = [10, 40, 30, 20, 60, 50];
 941     ///
 942     /// for group in v.split_mut(|num| *num % 3 == 0) {
 943     ///     group[0] = 1;
 944     /// }
 945     /// assert_eq!(v, [1, 40, 30, 1, 60, 1]);
 946     /// ```
 947     #[stable(feature = "rust1", since = "1.0.0")]
 948     #[inline]
 949     pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F>
 950         where F: FnMut(&T) -> bool
 951     {
 952         SplitMut { v: self, pred: pred, finished: false }
 953     }
 954
 955     /// Returns an iterator over subslices separated by elements that match
 956     /// `pred`, starting at the end of the slice and working backwards.
 957     /// The matched element is not contained in the subslices.
 958     ///
 959     /// # Examples
 960     ///
 961     /// ```
 962     /// let slice = [11, 22, 33, 0, 44, 55];
 963     /// let mut iter = slice.rsplit(|num| *num == 0);
 964     ///
 965     /// assert_eq!(iter.next().unwrap(), &[44, 55]);
 966     /// assert_eq!(iter.next().unwrap(), &[11, 22, 33]);
 967     /// assert_eq!(iter.next(), None);
 968     /// ```
 969     ///
 970     /// As with `split()`, if the first or last element is matched, an empty
 971     /// slice will be the first (or last) item returned by the iterator.
 972     ///
 973     /// ```
 974     /// let v = &[0, 1, 1, 2, 3, 5, 8];
 975     /// let mut it = v.rsplit(|n| *n % 2 == 0);
 976     /// assert_eq!(it.next().unwrap(), &[]);
 977     /// assert_eq!(it.next().unwrap(), &[3, 5]);
 978     /// assert_eq!(it.next().unwrap(), &[1, 1]);
 979     /// assert_eq!(it.next().unwrap(), &[]);
 980     /// assert_eq!(it.next(), None);
 981     /// ```
 982     #[stable(feature = "slice_rsplit", since = "1.27.0")]
 983     #[inline]
 984     pub fn rsplit<F>(&self, pred: F) -> RSplit<T, F>
 985         where F: FnMut(&T) -> bool
 986     {
 987         RSplit { inner: self.split(pred) }
 988     }
 989
 990     /// Returns an iterator over mutable subslices separated by elements that
 991     /// match `pred`, starting at the end of the slice and working
 992     /// backwards. The matched element is not contained in the subslices.
 993     ///
 994     /// # Examples
 995     ///
 996     /// ```
 997     /// let mut v = [100, 400, 300, 200, 600, 500];
 998     ///
 999     /// let mut count = 0;
1000     /// for group in v.rsplit_mut(|num| *num % 3 == 0) {
1001     ///     count += 1;
1002     ///     group[0] = count;
1003     /// }
1004     /// assert_eq!(v, [3, 400, 300, 2, 600, 1]);
1005     /// ```
1006     ///
1007     #[stable(feature = "slice_rsplit", since = "1.27.0")]
1008     #[inline]
1009     pub fn rsplit_mut<F>(&mut self, pred: F) -> RSplitMut<T, F>
1010         where F: FnMut(&T) -> bool
1011     {
1012         RSplitMut { inner: self.split_mut(pred) }
1013     }
1014
1015     /// Returns an iterator over subslices separated by elements that match
1016     /// `pred`, limited to returning at most `n` items. The matched element is
1017     /// not contained in the subslices.
1018     ///
1019     /// The last element returned, if any, will contain the remainder of the
1020     /// slice.
1021     ///
1022     /// # Examples
1023     ///
1024     /// Print the slice split once by numbers divisible by 3 (i.e. `[10, 40]`,
1025     /// `[20, 60, 50]`):
1026     ///
1027     /// ```
1028     /// let v = [10, 40, 30, 20, 60, 50];
1029     ///
1030     /// for group in v.splitn(2, |num| *num % 3 == 0) {
1031     ///     println!("{:?}", group);
1032     /// }
1033     /// ```
1034     #[stable(feature = "rust1", since = "1.0.0")]
1035     #[inline]
1036     pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<T, F>
1037         where F: FnMut(&T) -> bool
1038     {
1039         SplitN {
1040             inner: GenericSplitN {
1041                 iter: self.split(pred),
1042                 count: n
1043             }
1044         }
1045     }
1046
1047     /// Returns an iterator over subslices separated by elements that match
1048     /// `pred`, limited to returning at most `n` items. The matched element is
1049     /// not contained in the subslices.
1050     ///
1051     /// The last element returned, if any, will contain the remainder of the
1052     /// slice.
1053     ///
1054     /// # Examples
1055     ///
1056     /// ```
1057     /// let mut v = [10, 40, 30, 20, 60, 50];
1058     ///
1059     /// for group in v.splitn_mut(2, |num| *num % 3 == 0) {
1060     ///     group[0] = 1;
1061     /// }
1062     /// assert_eq!(v, [1, 40, 30, 1, 60, 50]);
1063     /// ```
1064     #[stable(feature = "rust1", since = "1.0.0")]
1065     #[inline]
1066     pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<T, F>
1067         where F: FnMut(&T) -> bool
1068     {
1069         SplitNMut {
1070             inner: GenericSplitN {
1071                 iter: self.split_mut(pred),
1072                 count: n
1073             }
1074         }
1075     }
1076
1077     /// Returns an iterator over subslices separated by elements that match
1078     /// `pred` limited to returning at most `n` items. This starts at the end of
1079     /// the slice and works backwards.  The matched element is not contained in
1080     /// the subslices.
1081     ///
1082     /// The last element returned, if any, will contain the remainder of the
1083     /// slice.
1084     ///
1085     /// # Examples
1086     ///
1087     /// Print the slice split once, starting from the end, by numbers divisible
1088     /// by 3 (i.e. `[50]`, `[10, 40, 30, 20]`):
1089     ///
1090     /// ```
1091     /// let v = [10, 40, 30, 20, 60, 50];
1092     ///
1093     /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
1094     ///     println!("{:?}", group);
1095     /// }
1096     /// ```
1097     #[stable(feature = "rust1", since = "1.0.0")]
1098     #[inline]
1099     pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<T, F>
1100         where F: FnMut(&T) -> bool
1101     {
1102         RSplitN {
1103             inner: GenericSplitN {
1104                 iter: self.rsplit(pred),
1105                 count: n
1106             }
1107         }
1108     }
1109
1110     /// Returns an iterator over subslices separated by elements that match
1111     /// `pred` limited to returning at most `n` items. This starts at the end of
1112     /// the slice and works backwards. The matched element is not contained in
1113     /// the subslices.
1114     ///
1115     /// The last element returned, if any, will contain the remainder of the
1116     /// slice.
1117     ///
1118     /// # Examples
1119     ///
1120     /// ```
1121     /// let mut s = [10, 40, 30, 20, 60, 50];
1122     ///
1123     /// for group in s.rsplitn_mut(2, |num| *num % 3 == 0) {
1124     ///     group[0] = 1;
1125     /// }
1126     /// assert_eq!(s, [1, 40, 30, 20, 60, 1]);
1127     /// ```
1128     #[stable(feature = "rust1", since = "1.0.0")]
1129     #[inline]
1130     pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<T, F>
1131         where F: FnMut(&T) -> bool
1132     {
1133         RSplitNMut {
1134             inner: GenericSplitN {
1135                 iter: self.rsplit_mut(pred),
1136                 count: n
1137             }
1138         }
1139     }
1140
1141     /// Returns `true` if the slice contains an element with the given value.
1142     ///
1143     /// # Examples
1144     ///
1145     /// ```
1146     /// let v = [10, 40, 30];
1147     /// assert!(v.contains(&30));
1148     /// assert!(!v.contains(&50));
1149     /// ```
1150     #[stable(feature = "rust1", since = "1.0.0")]
1151     pub fn contains(&self, x: &T) -> bool
1152         where T: PartialEq
1153     {
1154         x.slice_contains(self)
1155     }
1156
1157     /// Returns `true` if `needle` is a prefix of the slice.
1158     ///
1159     /// # Examples
1160     ///
1161     /// ```
1162     /// let v = [10, 40, 30];
1163     /// assert!(v.starts_with(&[10]));
1164     /// assert!(v.starts_with(&[10, 40]));
1165     /// assert!(!v.starts_with(&[50]));
1166     /// assert!(!v.starts_with(&[10, 50]));
1167     /// ```
1168     ///
1169     /// Always returns `true` if `needle` is an empty slice:
1170     ///
1171     /// ```
1172     /// let v = &[10, 40, 30];
1173     /// assert!(v.starts_with(&[]));
1174     /// let v: &[u8] = &[];
1175     /// assert!(v.starts_with(&[]));
1176     /// ```
1177     #[stable(feature = "rust1", since = "1.0.0")]
1178     pub fn starts_with(&self, needle: &[T]) -> bool
1179         where T: PartialEq
1180     {
1181         let n = needle.len();
1182         self.len() >= n && needle == &self[..n]
1183     }
1184
1185     /// Returns `true` if `needle` is a suffix of the slice.
1186     ///
1187     /// # Examples
1188     ///
1189     /// ```
1190     /// let v = [10, 40, 30];
1191     /// assert!(v.ends_with(&[30]));
1192     /// assert!(v.ends_with(&[40, 30]));
1193     /// assert!(!v.ends_with(&[50]));
1194     /// assert!(!v.ends_with(&[50, 30]));
1195     /// ```
1196     ///
1197     /// Always returns `true` if `needle` is an empty slice:
1198     ///
1199     /// ```
1200     /// let v = &[10, 40, 30];
1201     /// assert!(v.ends_with(&[]));
1202     /// let v: &[u8] = &[];
1203     /// assert!(v.ends_with(&[]));
1204     /// ```
1205     #[stable(feature = "rust1", since = "1.0.0")]
1206     pub fn ends_with(&self, needle: &[T]) -> bool
1207         where T: PartialEq
1208     {
1209         let (m, n) = (self.len(), needle.len());
1210         m >= n && needle == &self[m-n..]
1211     }
1212
1213     /// Binary searches this sorted slice for a given element.
1214     ///
1215     /// If the value is found then `Ok` is returned, containing the
1216     /// index of the matching element; if the value is not found then
1217     /// `Err` is returned, containing the index where a matching
1218     /// element could be inserted while maintaining sorted order.
1219     ///
1220     /// # Examples
1221     ///
1222     /// Looks up a series of four elements. The first is found, with a
1223     /// uniquely determined position; the second and third are not
1224     /// found; the fourth could match any position in `[1, 4]`.
1225     ///
1226     /// ```
1227     /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1228     ///
1229     /// assert_eq!(s.binary_search(&13),  Ok(9));
1230     /// assert_eq!(s.binary_search(&4),   Err(7));
1231     /// assert_eq!(s.binary_search(&100), Err(13));
1232     /// let r = s.binary_search(&1);
1233     /// assert!(match r { Ok(1..=4) => true, _ => false, });
1234     /// ```
1235     #[stable(feature = "rust1", since = "1.0.0")]
1236     pub fn binary_search(&self, x: &T) -> Result<usize, usize>
1237         where T: Ord
1238     {
1239         self.binary_search_by(|p| p.cmp(x))
1240     }
1241
1242     /// Binary searches this sorted slice with a comparator function.
1243     ///
1244     /// The comparator function should implement an order consistent
1245     /// with the sort order of the underlying slice, returning an
1246     /// order code that indicates whether its argument is `Less`,
1247     /// `Equal` or `Greater` the desired target.
1248     ///
1249     /// If a matching value is found then returns `Ok`, containing
1250     /// the index for the matched element; if no match is found then
1251     /// `Err` is returned, containing the index where a matching
1252     /// element could be inserted while maintaining sorted order.
1253     ///
1254     /// # Examples
1255     ///
1256     /// Looks up a series of four elements. The first is found, with a
1257     /// uniquely determined position; the second and third are not
1258     /// found; the fourth could match any position in `[1, 4]`.
1259     ///
1260     /// ```
1261     /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1262     ///
1263     /// let seek = 13;
1264     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
1265     /// let seek = 4;
1266     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
1267     /// let seek = 100;
1268     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
1269     /// let seek = 1;
1270     /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
1271     /// assert!(match r { Ok(1..=4) => true, _ => false, });
1272     /// ```
1273     #[stable(feature = "rust1", since = "1.0.0")]
1274     #[inline]
1275     pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
1276         where F: FnMut(&'a T) -> Ordering
1277     {
1278         let s = self;
1279         let mut size = s.len();
1280         if size == 0 {
1281             return Err(0);
1282         }
1283         let mut base = 0usize;
1284         while size > 1 {
1285             let half = size / 2;
1286             let mid = base + half;
1287             // mid is always in [0, size), that means mid is >= 0 and < size.
1288             // mid >= 0: by definition
1289             // mid < size: mid = size / 2 + size / 4 + size / 8 ...
1290             let cmp = f(unsafe { s.get_unchecked(mid) });
1291             base = if cmp == Greater { base } else { mid };
1292             size -= half;
1293         }
1294         // base is always in [0, size) because base <= mid.
1295         let cmp = f(unsafe { s.get_unchecked(base) });
1296         if cmp == Equal { Ok(base) } else { Err(base + (cmp == Less) as usize) }
1297
1298     }
1299
1300     /// Binary searches this sorted slice with a key extraction function.
1301     ///
1302     /// Assumes that the slice is sorted by the key, for instance with
1303     /// [`sort_by_key`] using the same key extraction function.
1304     ///
1305     /// If a matching value is found then returns `Ok`, containing the
1306     /// index for the matched element; if no match is found then `Err`
1307     /// is returned, containing the index where a matching element could
1308     /// be inserted while maintaining sorted order.
1309     ///
1310     /// [`sort_by_key`]: #method.sort_by_key
1311     ///
1312     /// # Examples
1313     ///
1314     /// Looks up a series of four elements in a slice of pairs sorted by
1315     /// their second elements. The first is found, with a uniquely
1316     /// determined position; the second and third are not found; the
1317     /// fourth could match any position in `[1, 4]`.
1318     ///
1319     /// ```
1320     /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1),
1321     ///          (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
1322     ///          (1, 21), (2, 34), (4, 55)];
1323     ///
1324     /// assert_eq!(s.binary_search_by_key(&13, |&(a,b)| b),  Ok(9));
1325     /// assert_eq!(s.binary_search_by_key(&4, |&(a,b)| b),   Err(7));
1326     /// assert_eq!(s.binary_search_by_key(&100, |&(a,b)| b), Err(13));
1327     /// let r = s.binary_search_by_key(&1, |&(a,b)| b);
1328     /// assert!(match r { Ok(1..=4) => true, _ => false, });
1329     /// ```
1330     #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
1331     #[inline]
1332     pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
1333         where F: FnMut(&'a T) -> B,
1334               B: Ord
1335     {
1336         self.binary_search_by(|k| f(k).cmp(b))
1337     }
1338
1339     /// Sorts the slice, but may not preserve the order of equal elements.
1340     ///
1341     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1342     /// and `O(n log n)` worst-case.
1343     ///
1344     /// # Current implementation
1345     ///
1346     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1347     /// which combines the fast average case of randomized quicksort with the fast worst case of
1348     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1349     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1350     /// deterministic behavior.
1351     ///
1352     /// It is typically faster than stable sorting, except in a few special cases, e.g. when the
1353     /// slice consists of several concatenated sorted sequences.
1354     ///
1355     /// # Examples
1356     ///
1357     /// ```
1358     /// let mut v = [-5, 4, 1, -3, 2];
1359     ///
1360     /// v.sort_unstable();
1361     /// assert!(v == [-5, -3, 1, 2, 4]);
1362     /// ```
1363     ///
1364     /// [pdqsort]: https://github.com/orlp/pdqsort
1365     #[stable(feature = "sort_unstable", since = "1.20.0")]
1366     #[inline]
1367     pub fn sort_unstable(&mut self)
1368         where T: Ord
1369     {
1370         sort::quicksort(self, |a, b| a.lt(b));
1371     }
1372
1373     /// Sorts the slice with a comparator function, but may not preserve the order of equal
1374     /// elements.
1375     ///
1376     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1377     /// and `O(n log n)` worst-case.
1378     ///
1379     /// # Current implementation
1380     ///
1381     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1382     /// which combines the fast average case of randomized quicksort with the fast worst case of
1383     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1384     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1385     /// deterministic behavior.
1386     ///
1387     /// It is typically faster than stable sorting, except in a few special cases, e.g. when the
1388     /// slice consists of several concatenated sorted sequences.
1389     ///
1390     /// # Examples
1391     ///
1392     /// ```
1393     /// let mut v = [5, 4, 1, 3, 2];
1394     /// v.sort_unstable_by(|a, b| a.cmp(b));
1395     /// assert!(v == [1, 2, 3, 4, 5]);
1396     ///
1397     /// // reverse sorting
1398     /// v.sort_unstable_by(|a, b| b.cmp(a));
1399     /// assert!(v == [5, 4, 3, 2, 1]);
1400     /// ```
1401     ///
1402     /// [pdqsort]: https://github.com/orlp/pdqsort
1403     #[stable(feature = "sort_unstable", since = "1.20.0")]
1404     #[inline]
1405     pub fn sort_unstable_by<F>(&mut self, mut compare: F)
1406         where F: FnMut(&T, &T) -> Ordering
1407     {
1408         sort::quicksort(self, |a, b| compare(a, b) == Ordering::Less);
1409     }
1410
1411     /// Sorts the slice with a key extraction function, but may not preserve the order of equal
1412     /// elements.
1413     ///
1414     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1415     /// and `O(m n log(m n))` worst-case, where the key function is `O(m)`.
1416     ///
1417     /// # Current implementation
1418     ///
1419     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1420     /// which combines the fast average case of randomized quicksort with the fast worst case of
1421     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1422     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1423     /// deterministic behavior.
1424     ///
1425     /// # Examples
1426     ///
1427     /// ```
1428     /// let mut v = [-5i32, 4, 1, -3, 2];
1429     ///
1430     /// v.sort_unstable_by_key(|k| k.abs());
1431     /// assert!(v == [1, 2, -3, 4, -5]);
1432     /// ```
1433     ///
1434     /// [pdqsort]: https://github.com/orlp/pdqsort
1435     #[stable(feature = "sort_unstable", since = "1.20.0")]
1436     #[inline]
1437     pub fn sort_unstable_by_key<K, F>(&mut self, mut f: F)
1438         where F: FnMut(&T) -> K, K: Ord
1439     {
1440         sort::quicksort(self, |a, b| f(a).lt(&f(b)));
1441     }
1442
1443     /// Rotates the slice in-place such that the first `mid` elements of the
1444     /// slice move to the end while the last `self.len() - mid` elements move to
1445     /// the front. After calling `rotate_left`, the element previously at index
1446     /// `mid` will become the first element in the slice.
1447     ///
1448     /// # Panics
1449     ///
1450     /// This function will panic if `mid` is greater than the length of the
1451     /// slice. Note that `mid == self.len()` does _not_ panic and is a no-op
1452     /// rotation.
1453     ///
1454     /// # Complexity
1455     ///
1456     /// Takes linear (in `self.len()`) time.
1457     ///
1458     /// # Examples
1459     ///
1460     /// ```
1461     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1462     /// a.rotate_left(2);
1463     /// assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
1464     /// ```
1465     ///
1466     /// Rotating a subslice:
1467     ///
1468     /// ```
1469     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1470     /// a[1..5].rotate_left(1);
1471     /// assert_eq!(a, ['a', 'c', 'd', 'e', 'b', 'f']);
1472    /// ```
1473     #[stable(feature = "slice_rotate", since = "1.26.0")]
1474     pub fn rotate_left(&mut self, mid: usize) {
1475         assert!(mid <= self.len());
1476         let k = self.len() - mid;
1477
1478         unsafe {
1479             let p = self.as_mut_ptr();
1480             rotate::ptr_rotate(mid, p.offset(mid as isize), k);
1481         }
1482     }
1483
1484     /// Rotates the slice in-place such that the first `self.len() - k`
1485     /// elements of the slice move to the end while the last `k` elements move
1486     /// to the front. After calling `rotate_right`, the element previously at
1487     /// index `self.len() - k` will become the first element in the slice.
1488     ///
1489     /// # Panics
1490     ///
1491     /// This function will panic if `k` is greater than the length of the
1492     /// slice. Note that `k == self.len()` does _not_ panic and is a no-op
1493     /// rotation.
1494     ///
1495     /// # Complexity
1496     ///
1497     /// Takes linear (in `self.len()`) time.
1498     ///
1499     /// # Examples
1500     ///
1501     /// ```
1502     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1503     /// a.rotate_right(2);
1504     /// assert_eq!(a, ['e', 'f', 'a', 'b', 'c', 'd']);
1505     /// ```
1506     ///
1507     /// Rotate a subslice:
1508     ///
1509     /// ```
1510     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
1511     /// a[1..5].rotate_right(1);
1512     /// assert_eq!(a, ['a', 'e', 'b', 'c', 'd', 'f']);
1513     /// ```
1514     #[stable(feature = "slice_rotate", since = "1.26.0")]
1515     pub fn rotate_right(&mut self, k: usize) {
1516         assert!(k <= self.len());
1517         let mid = self.len() - k;
1518
1519         unsafe {
1520             let p = self.as_mut_ptr();
1521             rotate::ptr_rotate(mid, p.offset(mid as isize), k);
1522         }
1523     }
1524
1525     /// Copies the elements from `src` into `self`.
1526     ///
1527     /// The length of `src` must be the same as `self`.
1528     ///
1529     /// If `src` implements `Copy`, it can be more performant to use
1530     /// [`copy_from_slice`].
1531     ///
1532     /// # Panics
1533     ///
1534     /// This function will panic if the two slices have different lengths.
1535     ///
1536     /// # Examples
1537     ///
1538     /// Cloning two elements from a slice into another:
1539     ///
1540     /// ```
1541     /// let src = [1, 2, 3, 4];
1542     /// let mut dst = [0, 0];
1543     ///
1544     /// dst.clone_from_slice(&src[2..]);
1545     ///
1546     /// assert_eq!(src, [1, 2, 3, 4]);
1547     /// assert_eq!(dst, [3, 4]);
1548     /// ```
1549     ///
1550     /// Rust enforces that there can only be one mutable reference with no
1551     /// immutable references to a particular piece of data in a particular
1552     /// scope. Because of this, attempting to use `clone_from_slice` on a
1553     /// single slice will result in a compile failure:
1554     ///
1555     /// ```compile_fail
1556     /// let mut slice = [1, 2, 3, 4, 5];
1557     ///
1558     /// slice[..2].clone_from_slice(&slice[3..]); // compile fail!
1559     /// ```
1560     ///
1561     /// To work around this, we can use [`split_at_mut`] to create two distinct
1562     /// sub-slices from a slice:
1563     ///
1564     /// ```
1565     /// let mut slice = [1, 2, 3, 4, 5];
1566     ///
1567     /// {
1568     ///     let (left, right) = slice.split_at_mut(2);
1569     ///     left.clone_from_slice(&right[1..]);
1570     /// }
1571     ///
1572     /// assert_eq!(slice, [4, 5, 3, 4, 5]);
1573     /// ```
1574     ///
1575     /// [`copy_from_slice`]: #method.copy_from_slice
1576     /// [`split_at_mut`]: #method.split_at_mut
1577     #[stable(feature = "clone_from_slice", since = "1.7.0")]
1578     pub fn clone_from_slice(&mut self, src: &[T]) where T: Clone {
1579         assert!(self.len() == src.len(),
1580                 "destination and source slices have different lengths");
1581         // NOTE: We need to explicitly slice them to the same length
1582         // for bounds checking to be elided, and the optimizer will
1583         // generate memcpy for simple cases (for example T = u8).
1584         let len = self.len();
1585         let src = &src[..len];
1586         for i in 0..len {
1587             self[i].clone_from(&src[i]);
1588         }
1589
1590     }
1591
1592     /// Copies all elements from `src` into `self`, using a memcpy.
1593     ///
1594     /// The length of `src` must be the same as `self`.
1595     ///
1596     /// If `src` does not implement `Copy`, use [`clone_from_slice`].
1597     ///
1598     /// # Panics
1599     ///
1600     /// This function will panic if the two slices have different lengths.
1601     ///
1602     /// # Examples
1603     ///
1604     /// Copying two elements from a slice into another:
1605     ///
1606     /// ```
1607     /// let src = [1, 2, 3, 4];
1608     /// let mut dst = [0, 0];
1609     ///
1610     /// dst.copy_from_slice(&src[2..]);
1611     ///
1612     /// assert_eq!(src, [1, 2, 3, 4]);
1613     /// assert_eq!(dst, [3, 4]);
1614     /// ```
1615     ///
1616     /// Rust enforces that there can only be one mutable reference with no
1617     /// immutable references to a particular piece of data in a particular
1618     /// scope. Because of this, attempting to use `copy_from_slice` on a
1619     /// single slice will result in a compile failure:
1620     ///
1621     /// ```compile_fail
1622     /// let mut slice = [1, 2, 3, 4, 5];
1623     ///
1624     /// slice[..2].copy_from_slice(&slice[3..]); // compile fail!
1625     /// ```
1626     ///
1627     /// To work around this, we can use [`split_at_mut`] to create two distinct
1628     /// sub-slices from a slice:
1629     ///
1630     /// ```
1631     /// let mut slice = [1, 2, 3, 4, 5];
1632     ///
1633     /// {
1634     ///     let (left, right) = slice.split_at_mut(2);
1635     ///     left.copy_from_slice(&right[1..]);
1636     /// }
1637     ///
1638     /// assert_eq!(slice, [4, 5, 3, 4, 5]);
1639     /// ```
1640     ///
1641     /// [`clone_from_slice`]: #method.clone_from_slice
1642     /// [`split_at_mut`]: #method.split_at_mut
1643     #[stable(feature = "copy_from_slice", since = "1.9.0")]
1644     pub fn copy_from_slice(&mut self, src: &[T]) where T: Copy {
1645         assert_eq!(self.len(), src.len(),
1646                    "destination and source slices have different lengths");
1647         unsafe {
1648             ptr::copy_nonoverlapping(
1649                 src.as_ptr(), self.as_mut_ptr(), self.len());
1650         }
1651     }
1652
1653     /// Swaps all elements in `self` with those in `other`.
1654     ///
1655     /// The length of `other` must be the same as `self`.
1656     ///
1657     /// # Panics
1658     ///
1659     /// This function will panic if the two slices have different lengths.
1660     ///
1661     /// # Example
1662     ///
1663     /// Swapping two elements across slices:
1664     ///
1665     /// ```
1666     /// let mut slice1 = [0, 0];
1667     /// let mut slice2 = [1, 2, 3, 4];
1668     ///
1669     /// slice1.swap_with_slice(&mut slice2[2..]);
1670     ///
1671     /// assert_eq!(slice1, [3, 4]);
1672     /// assert_eq!(slice2, [1, 2, 0, 0]);
1673     /// ```
1674     ///
1675     /// Rust enforces that there can only be one mutable reference to a
1676     /// particular piece of data in a particular scope. Because of this,
1677     /// attempting to use `swap_with_slice` on a single slice will result in
1678     /// a compile failure:
1679     ///
1680     /// ```compile_fail
1681     /// let mut slice = [1, 2, 3, 4, 5];
1682     /// slice[..2].swap_with_slice(&mut slice[3..]); // compile fail!
1683     /// ```
1684     ///
1685     /// To work around this, we can use [`split_at_mut`] to create two distinct
1686     /// mutable sub-slices from a slice:
1687     ///
1688     /// ```
1689     /// let mut slice = [1, 2, 3, 4, 5];
1690     ///
1691     /// {
1692     ///     let (left, right) = slice.split_at_mut(2);
1693     ///     left.swap_with_slice(&mut right[1..]);
1694     /// }
1695     ///
1696     /// assert_eq!(slice, [4, 5, 3, 1, 2]);
1697     /// ```
1698     ///
1699     /// [`split_at_mut`]: #method.split_at_mut
1700     #[stable(feature = "swap_with_slice", since = "1.27.0")]
1701     pub fn swap_with_slice(&mut self, other: &mut [T]) {
1702         assert!(self.len() == other.len(),
1703                 "destination and source slices have different lengths");
1704         unsafe {
1705             ptr::swap_nonoverlapping(
1706                 self.as_mut_ptr(), other.as_mut_ptr(), self.len());
1707         }
1708     }
1709
1710     /// Function to calculate lenghts of the middle and trailing slice for `align_to{,_mut}`.
1711     fn align_to_offsets<U>(&self) -> (usize, usize) {
1712         // What we gonna do about `rest` is figure out what multiple of `U`s we can put in a
1713         // lowest number of `T`s. And how many `T`s we need for each such "multiple".
1714         //
1715         // Consider for example T=u8 U=u16. Then we can put 1 U in 2 Ts. Simple. Now, consider
1716         // for example a case where size_of::<T> = 16, size_of::<U> = 24. We can put 2 Us in
1717         // place of every 3 Ts in the `rest` slice. A bit more complicated.
1718         //
1719         // Formula to calculate this is:
1720         //
1721         // Us = lcm(size_of::<T>, size_of::<U>) / size_of::<U>
1722         // Ts = lcm(size_of::<T>, size_of::<U>) / size_of::<T>
1723         //
1724         // Expanded and simplified:
1725         //
1726         // Us = size_of::<T> / gcd(size_of::<T>, size_of::<U>)
1727         // Ts = size_of::<U> / gcd(size_of::<T>, size_of::<U>)
1728         //
1729         // Luckily since all this is constant-evaluated... performance here matters not!
1730         #[inline]
1731         fn gcd(a: usize, b: usize) -> usize {
1732             // iterative stein’s algorithm
1733             // We should still make this `const fn` (and revert to recursive algorithm if we do)
1734             // because relying on llvm to consteval all this is… well, it makes me
1735             let (ctz_a, mut ctz_b) = unsafe {
1736                 if a == 0 { return b; }
1737                 if b == 0 { return a; }
1738                 (::intrinsics::cttz_nonzero(a), ::intrinsics::cttz_nonzero(b))
1739             };
1740             let k = ctz_a.min(ctz_b);
1741             let mut a = a >> ctz_a;
1742             let mut b = b;
1743             loop {
1744                 // remove all factors of 2 from b
1745                 b >>= ctz_b;
1746                 if a > b {
1747                     ::mem::swap(&mut a, &mut b);
1748                 }
1749                 b = b - a;
1750                 unsafe {
1751                     if b == 0 {
1752                         break;
1753                     }
1754                     ctz_b = ::intrinsics::cttz_nonzero(b);
1755                 }
1756             }
1757             return a << k;
1758         }
1759         let gcd: usize = gcd(::mem::size_of::<T>(), ::mem::size_of::<U>());
1760         let ts: usize = ::mem::size_of::<U>() / gcd;
1761         let us: usize = ::mem::size_of::<T>() / gcd;
1762
1763         // Armed with this knowledge, we can find how many `U`s we can fit!
1764         let us_len = self.len() / ts * us;
1765         // And how many `T`s will be in the trailing slice!
1766         let ts_len = self.len() % ts;
1767         return (us_len, ts_len);
1768     }
1769
1770     /// Transmute the slice to a slice of another type, ensuring aligment of the types is
1771     /// maintained.
1772     ///
1773     /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
1774     /// slice of a new type, and the suffix slice. The middle slice will have the greatest length
1775     /// possible for a given type and input slice.
1776     ///
1777     /// This method has no purpose when either input element `T` or output element `U` are
1778     /// zero-sized and will return the original slice without splitting anything.
1779     ///
1780     /// # Unsafety
1781     ///
1782     /// This method is essentially a `transmute` with respect to the elements in the returned
1783     /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
1784     ///
1785     /// # Examples
1786     ///
1787     /// Basic usage:
1788     ///
1789     /// ```
1790     /// # #![feature(slice_align_to)]
1791     /// unsafe {
1792     ///     let bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
1793     ///     let (prefix, shorts, suffix) = bytes.align_to::<u16>();
1794     ///     // less_efficient_algorithm_for_bytes(prefix);
1795     ///     // more_efficient_algorithm_for_aligned_shorts(shorts);
1796     ///     // less_efficient_algorithm_for_bytes(suffix);
1797     /// }
1798     /// ```
1799     #[unstable(feature = "slice_align_to", issue = "44488")]
1800     pub unsafe fn align_to<U>(&self) -> (&[T], &[U], &[T]) {
1801         // Note that most of this function will be constant-evaluated,
1802         if ::mem::size_of::<U>() == 0 || ::mem::size_of::<T>() == 0 {
1803             // handle ZSTs specially, which is – don't handle them at all.
1804             return (self, &[], &[]);
1805         }
1806
1807         // First, find at what point do we split between the first and 2nd slice. Easy with
1808         // ptr.align_offset.
1809         let ptr = self.as_ptr();
1810         let offset = ::ptr::align_offset(ptr, ::mem::align_of::<U>());
1811         if offset > self.len() {
1812             return (self, &[], &[]);
1813         } else {
1814             let (left, rest) = self.split_at(offset);
1815             let (us_len, ts_len) = rest.align_to_offsets::<U>();
1816             return (left,
1817                     from_raw_parts(rest.as_ptr() as *const U, us_len),
1818                     from_raw_parts(rest.as_ptr().offset((rest.len() - ts_len) as isize), ts_len))
1819         }
1820     }
1821
1822     /// Transmute the slice to a slice of another type, ensuring aligment of the types is
1823     /// maintained.
1824     ///
1825     /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
1826     /// slice of a new type, and the suffix slice. The middle slice will have the greatest length
1827     /// possible for a given type and input slice.
1828     ///
1829     /// This method has no purpose when either input element `T` or output element `U` are
1830     /// zero-sized and will return the original slice without splitting anything.
1831     ///
1832     /// # Unsafety
1833     ///
1834     /// This method is essentially a `transmute` with respect to the elements in the returned
1835     /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
1836     ///
1837     /// # Examples
1838     ///
1839     /// Basic usage:
1840     ///
1841     /// ```
1842     /// # #![feature(slice_align_to)]
1843     /// unsafe {
1844     ///     let mut bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
1845     ///     let (prefix, shorts, suffix) = bytes.align_to_mut::<u16>();
1846     ///     // less_efficient_algorithm_for_bytes(prefix);
1847     ///     // more_efficient_algorithm_for_aligned_shorts(shorts);
1848     ///     // less_efficient_algorithm_for_bytes(suffix);
1849     /// }
1850     /// ```
1851     #[unstable(feature = "slice_align_to", issue = "44488")]
1852     pub unsafe fn align_to_mut<U>(&mut self) -> (&mut [T], &mut [U], &mut [T]) {
1853         // Note that most of this function will be constant-evaluated,
1854         if ::mem::size_of::<U>() == 0 || ::mem::size_of::<T>() == 0 {
1855             // handle ZSTs specially, which is – don't handle them at all.
1856             return (self, &mut [], &mut []);
1857         }
1858
1859         // First, find at what point do we split between the first and 2nd slice. Easy with
1860         // ptr.align_offset.
1861         let ptr = self.as_ptr();
1862         let offset = ::ptr::align_offset(ptr, ::mem::align_of::<U>());
1863         if offset > self.len() {
1864             return (self, &mut [], &mut []);
1865         } else {
1866             let (left, rest) = self.split_at_mut(offset);
1867             let (us_len, ts_len) = rest.align_to_offsets::<U>();
1868             let mut_ptr = rest.as_mut_ptr();
1869             return (left,
1870                     from_raw_parts_mut(mut_ptr as *mut U, us_len),
1871                     from_raw_parts_mut(mut_ptr.offset((rest.len() - ts_len) as isize), ts_len))
1872         }
1873     }
1874 }
1875
1876 #[lang = "slice_u8"]
1877 #[cfg(not(test))]
1878 impl [u8] {
1879     /// Checks if all bytes in this slice are within the ASCII range.
1880     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1881     #[inline]
1882     pub fn is_ascii(&self) -> bool {
1883         self.iter().all(|b| b.is_ascii())
1884     }
1885
1886     /// Checks that two slices are an ASCII case-insensitive match.
1887     ///
1888     /// Same as `to_ascii_lowercase(a) == to_ascii_lowercase(b)`,
1889     /// but without allocating and copying temporaries.
1890     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1891     #[inline]
1892     pub fn eq_ignore_ascii_case(&self, other: &[u8]) -> bool {
1893         self.len() == other.len() &&
1894             self.iter().zip(other).all(|(a, b)| {
1895                 a.eq_ignore_ascii_case(b)
1896             })
1897     }
1898
1899     /// Converts this slice to its ASCII upper case equivalent in-place.
1900     ///
1901     /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
1902     /// but non-ASCII letters are unchanged.
1903     ///
1904     /// To return a new uppercased value without modifying the existing one, use
1905     /// [`to_ascii_uppercase`].
1906     ///
1907     /// [`to_ascii_uppercase`]: #method.to_ascii_uppercase
1908     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1909     #[inline]
1910     pub fn make_ascii_uppercase(&mut self) {
1911         for byte in self {
1912             byte.make_ascii_uppercase();
1913         }
1914     }
1915
1916     /// Converts this slice to its ASCII lower case equivalent in-place.
1917     ///
1918     /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
1919     /// but non-ASCII letters are unchanged.
1920     ///
1921     /// To return a new lowercased value without modifying the existing one, use
1922     /// [`to_ascii_lowercase`].
1923     ///
1924     /// [`to_ascii_lowercase`]: #method.to_ascii_lowercase
1925     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1926     #[inline]
1927     pub fn make_ascii_lowercase(&mut self) {
1928         for byte in self {
1929             byte.make_ascii_lowercase();
1930         }
1931     }
1932
1933 }
1934
1935 #[stable(feature = "rust1", since = "1.0.0")]
1936 #[rustc_on_unimplemented = "slice indices are of type `usize` or ranges of `usize`"]
1937 impl<T, I> ops::Index<I> for [T]
1938     where I: SliceIndex<[T]>
1939 {
1940     type Output = I::Output;
1941
1942     #[inline]
1943     fn index(&self, index: I) -> &I::Output {
1944         index.index(self)
1945     }
1946 }
1947
1948 #[stable(feature = "rust1", since = "1.0.0")]
1949 #[rustc_on_unimplemented = "slice indices are of type `usize` or ranges of `usize`"]
1950 impl<T, I> ops::IndexMut<I> for [T]
1951     where I: SliceIndex<[T]>
1952 {
1953     #[inline]
1954     fn index_mut(&mut self, index: I) -> &mut I::Output {
1955         index.index_mut(self)
1956     }
1957 }
1958
1959 #[inline(never)]
1960 #[cold]
1961 fn slice_index_len_fail(index: usize, len: usize) -> ! {
1962     panic!("index {} out of range for slice of length {}", index, len);
1963 }
1964
1965 #[inline(never)]
1966 #[cold]
1967 fn slice_index_order_fail(index: usize, end: usize) -> ! {
1968     panic!("slice index starts at {} but ends at {}", index, end);
1969 }
1970
1971 #[inline(never)]
1972 #[cold]
1973 fn slice_index_overflow_fail() -> ! {
1974     panic!("attempted to index slice up to maximum usize");
1975 }
1976
1977 mod private_slice_index {
1978     use super::ops;
1979     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1980     pub trait Sealed {}
1981
1982     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1983     impl Sealed for usize {}
1984     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1985     impl Sealed for ops::Range<usize> {}
1986     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1987     impl Sealed for ops::RangeTo<usize> {}
1988     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1989     impl Sealed for ops::RangeFrom<usize> {}
1990     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1991     impl Sealed for ops::RangeFull {}
1992     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1993     impl Sealed for ops::RangeInclusive<usize> {}
1994     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1995     impl Sealed for ops::RangeToInclusive<usize> {}
1996 }
1997
1998 /// A helper trait used for indexing operations.
1999 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2000 #[rustc_on_unimplemented = "slice indices are of type `usize` or ranges of `usize`"]
2001 pub trait SliceIndex<T: ?Sized>: private_slice_index::Sealed {
2002     /// The output type returned by methods.
2003     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2004     type Output: ?Sized;
2005
2006     /// Returns a shared reference to the output at this location, if in
2007     /// bounds.
2008     #[unstable(feature = "slice_index_methods", issue = "0")]
2009     fn get(self, slice: &T) -> Option<&Self::Output>;
2010
2011     /// Returns a mutable reference to the output at this location, if in
2012     /// bounds.
2013     #[unstable(feature = "slice_index_methods", issue = "0")]
2014     fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
2015
2016     /// Returns a shared reference to the output at this location, without
2017     /// performing any bounds checking.
2018     #[unstable(feature = "slice_index_methods", issue = "0")]
2019     unsafe fn get_unchecked(self, slice: &T) -> &Self::Output;
2020
2021     /// Returns a mutable reference to the output at this location, without
2022     /// performing any bounds checking.
2023     #[unstable(feature = "slice_index_methods", issue = "0")]
2024     unsafe fn get_unchecked_mut(self, slice: &mut T) -> &mut Self::Output;
2025
2026     /// Returns a shared reference to the output at this location, panicking
2027     /// if out of bounds.
2028     #[unstable(feature = "slice_index_methods", issue = "0")]
2029     fn index(self, slice: &T) -> &Self::Output;
2030
2031     /// Returns a mutable reference to the output at this location, panicking
2032     /// if out of bounds.
2033     #[unstable(feature = "slice_index_methods", issue = "0")]
2034     fn index_mut(self, slice: &mut T) -> &mut Self::Output;
2035 }
2036
2037 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
2038 impl<T> SliceIndex<[T]> for usize {
2039     type Output = T;
2040
2041     #[inline]
2042     fn get(self, slice: &[T]) -> Option<&T> {
2043         if self < slice.len() {
2044             unsafe {
2045                 Some(self.get_unchecked(slice))
2046             }
2047         } else {
2048             None
2049         }
2050     }
2051
2052     #[inline]
2053     fn get_mut(self, slice: &mut [T]) -> Option<&mut T> {
2054         if self < slice.len() {
2055             unsafe {
2056                 Some(self.get_unchecked_mut(slice))
2057             }
2058         } else {
2059             None
2060         }
2061     }
2062
2063     #[inline]
2064     unsafe fn get_unchecked(self, slice: &[T]) -> &T {
2065         &*slice.as_ptr().offset(self as isize)
2066     }
2067
2068     #[inline]
2069     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut T {
2070         &mut *slice.as_mut_ptr().offset(self as isize)
2071     }
2072
2073     #[inline]
2074     fn index(self, slice: &[T]) -> &T {
2075         // NB: use intrinsic indexing
2076         &(*slice)[self]
2077     }
2078
2079     #[inline]
2080     fn index_mut(self, slice: &mut [T]) -> &mut T {
2081         // NB: use intrinsic indexing
2082         &mut (*slice)[self]
2083     }
2084 }
2085
2086 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
2087 impl<T> SliceIndex<[T]> for  ops::Range<usize> {
2088     type Output = [T];
2089
2090     #[inline]
2091     fn get(self, slice: &[T]) -> Option<&[T]> {
2092         if self.start > self.end || self.end > slice.len() {
2093             None
2094         } else {
2095             unsafe {
2096                 Some(self.get_unchecked(slice))
2097             }
2098         }
2099     }
2100
2101     #[inline]
2102     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2103         if self.start > self.end || self.end > slice.len() {
2104             None
2105         } else {
2106             unsafe {
2107                 Some(self.get_unchecked_mut(slice))
2108             }
2109         }
2110     }
2111
2112     #[inline]
2113     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2114         from_raw_parts(slice.as_ptr().offset(self.start as isize), self.end - self.start)
2115     }
2116
2117     #[inline]
2118     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2119         from_raw_parts_mut(slice.as_mut_ptr().offset(self.start as isize), self.end - self.start)
2120     }
2121
2122     #[inline]
2123     fn index(self, slice: &[T]) -> &[T] {
2124         if self.start > self.end {
2125             slice_index_order_fail(self.start, self.end);
2126         } else if self.end > slice.len() {
2127             slice_index_len_fail(self.end, slice.len());
2128         }
2129         unsafe {
2130             self.get_unchecked(slice)
2131         }
2132     }
2133
2134     #[inline]
2135     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2136         if self.start > self.end {
2137             slice_index_order_fail(self.start, self.end);
2138         } else if self.end > slice.len() {
2139             slice_index_len_fail(self.end, slice.len());
2140         }
2141         unsafe {
2142             self.get_unchecked_mut(slice)
2143         }
2144     }
2145 }
2146
2147 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
2148 impl<T> SliceIndex<[T]> for ops::RangeTo<usize> {
2149     type Output = [T];
2150
2151     #[inline]
2152     fn get(self, slice: &[T]) -> Option<&[T]> {
2153         (0..self.end).get(slice)
2154     }
2155
2156     #[inline]
2157     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2158         (0..self.end).get_mut(slice)
2159     }
2160
2161     #[inline]
2162     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2163         (0..self.end).get_unchecked(slice)
2164     }
2165
2166     #[inline]
2167     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2168         (0..self.end).get_unchecked_mut(slice)
2169     }
2170
2171     #[inline]
2172     fn index(self, slice: &[T]) -> &[T] {
2173         (0..self.end).index(slice)
2174     }
2175
2176     #[inline]
2177     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2178         (0..self.end).index_mut(slice)
2179     }
2180 }
2181
2182 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
2183 impl<T> SliceIndex<[T]> for ops::RangeFrom<usize> {
2184     type Output = [T];
2185
2186     #[inline]
2187     fn get(self, slice: &[T]) -> Option<&[T]> {
2188         (self.start..slice.len()).get(slice)
2189     }
2190
2191     #[inline]
2192     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2193         (self.start..slice.len()).get_mut(slice)
2194     }
2195
2196     #[inline]
2197     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2198         (self.start..slice.len()).get_unchecked(slice)
2199     }
2200
2201     #[inline]
2202     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2203         (self.start..slice.len()).get_unchecked_mut(slice)
2204     }
2205
2206     #[inline]
2207     fn index(self, slice: &[T]) -> &[T] {
2208         (self.start..slice.len()).index(slice)
2209     }
2210
2211     #[inline]
2212     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2213         (self.start..slice.len()).index_mut(slice)
2214     }
2215 }
2216
2217 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
2218 impl<T> SliceIndex<[T]> for ops::RangeFull {
2219     type Output = [T];
2220
2221     #[inline]
2222     fn get(self, slice: &[T]) -> Option<&[T]> {
2223         Some(slice)
2224     }
2225
2226     #[inline]
2227     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2228         Some(slice)
2229     }
2230
2231     #[inline]
2232     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2233         slice
2234     }
2235
2236     #[inline]
2237     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2238         slice
2239     }
2240
2241     #[inline]
2242     fn index(self, slice: &[T]) -> &[T] {
2243         slice
2244     }
2245
2246     #[inline]
2247     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2248         slice
2249     }
2250 }
2251
2252
2253 #[stable(feature = "inclusive_range", since = "1.26.0")]
2254 impl<T> SliceIndex<[T]> for ops::RangeInclusive<usize> {
2255     type Output = [T];
2256
2257     #[inline]
2258     fn get(self, slice: &[T]) -> Option<&[T]> {
2259         if self.end == usize::max_value() { None }
2260         else { (self.start..self.end + 1).get(slice) }
2261     }
2262
2263     #[inline]
2264     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2265         if self.end == usize::max_value() { None }
2266         else { (self.start..self.end + 1).get_mut(slice) }
2267     }
2268
2269     #[inline]
2270     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2271         (self.start..self.end + 1).get_unchecked(slice)
2272     }
2273
2274     #[inline]
2275     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2276         (self.start..self.end + 1).get_unchecked_mut(slice)
2277     }
2278
2279     #[inline]
2280     fn index(self, slice: &[T]) -> &[T] {
2281         if self.end == usize::max_value() { slice_index_overflow_fail(); }
2282         (self.start..self.end + 1).index(slice)
2283     }
2284
2285     #[inline]
2286     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2287         if self.end == usize::max_value() { slice_index_overflow_fail(); }
2288         (self.start..self.end + 1).index_mut(slice)
2289     }
2290 }
2291
2292 #[stable(feature = "inclusive_range", since = "1.26.0")]
2293 impl<T> SliceIndex<[T]> for ops::RangeToInclusive<usize> {
2294     type Output = [T];
2295
2296     #[inline]
2297     fn get(self, slice: &[T]) -> Option<&[T]> {
2298         (0..=self.end).get(slice)
2299     }
2300
2301     #[inline]
2302     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2303         (0..=self.end).get_mut(slice)
2304     }
2305
2306     #[inline]
2307     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2308         (0..=self.end).get_unchecked(slice)
2309     }
2310
2311     #[inline]
2312     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2313         (0..=self.end).get_unchecked_mut(slice)
2314     }
2315
2316     #[inline]
2317     fn index(self, slice: &[T]) -> &[T] {
2318         (0..=self.end).index(slice)
2319     }
2320
2321     #[inline]
2322     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2323         (0..=self.end).index_mut(slice)
2324     }
2325 }
2326
2327 ////////////////////////////////////////////////////////////////////////////////
2328 // Common traits
2329 ////////////////////////////////////////////////////////////////////////////////
2330
2331 #[stable(feature = "rust1", since = "1.0.0")]
2332 impl<'a, T> Default for &'a [T] {
2333     /// Creates an empty slice.
2334     fn default() -> &'a [T] { &[] }
2335 }
2336
2337 #[stable(feature = "mut_slice_default", since = "1.5.0")]
2338 impl<'a, T> Default for &'a mut [T] {
2339     /// Creates a mutable empty slice.
2340     fn default() -> &'a mut [T] { &mut [] }
2341 }
2342
2343 //
2344 // Iterators
2345 //
2346
2347 #[stable(feature = "rust1", since = "1.0.0")]
2348 impl<'a, T> IntoIterator for &'a [T] {
2349     type Item = &'a T;
2350     type IntoIter = Iter<'a, T>;
2351
2352     fn into_iter(self) -> Iter<'a, T> {
2353         self.iter()
2354     }
2355 }
2356
2357 #[stable(feature = "rust1", since = "1.0.0")]
2358 impl<'a, T> IntoIterator for &'a mut [T] {
2359     type Item = &'a mut T;
2360     type IntoIter = IterMut<'a, T>;
2361
2362     fn into_iter(self) -> IterMut<'a, T> {
2363         self.iter_mut()
2364     }
2365 }
2366
2367 #[inline]
2368 fn size_from_ptr<T>(_: *const T) -> usize {
2369     mem::size_of::<T>()
2370 }
2371
2372 // The shared definition of the `Iter` and `IterMut` iterators
2373 macro_rules! iterator {
2374     (struct $name:ident -> $ptr:ty, $elem:ty, $mkref:ident) => {
2375         #[stable(feature = "rust1", since = "1.0.0")]
2376         impl<'a, T> Iterator for $name<'a, T> {
2377             type Item = $elem;
2378
2379             #[inline]
2380             fn next(&mut self) -> Option<$elem> {
2381                 // could be implemented with slices, but this avoids bounds checks
2382                 unsafe {
2383                     if mem::size_of::<T>() != 0 {
2384                         assume(!self.ptr.is_null());
2385                         assume(!self.end.is_null());
2386                     }
2387                     if self.ptr == self.end {
2388                         None
2389                     } else {
2390                         Some($mkref!(self.ptr.post_inc()))
2391                     }
2392                 }
2393             }
2394
2395             #[inline]
2396             fn size_hint(&self) -> (usize, Option<usize>) {
2397                 let exact = unsafe { ptrdistance(self.ptr, self.end) };
2398                 (exact, Some(exact))
2399             }
2400
2401             #[inline]
2402             fn count(self) -> usize {
2403                 self.len()
2404             }
2405
2406             #[inline]
2407             fn nth(&mut self, n: usize) -> Option<$elem> {
2408                 // Call helper method. Can't put the definition here because mut versus const.
2409                 self.iter_nth(n)
2410             }
2411
2412             #[inline]
2413             fn last(mut self) -> Option<$elem> {
2414                 self.next_back()
2415             }
2416
2417             #[inline]
2418             fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
2419                 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
2420             {
2421                 // manual unrolling is needed when there are conditional exits from the loop
2422                 let mut accum = init;
2423                 unsafe {
2424                     while ptrdistance(self.ptr, self.end) >= 4 {
2425                         accum = f(accum, $mkref!(self.ptr.post_inc()))?;
2426                         accum = f(accum, $mkref!(self.ptr.post_inc()))?;
2427                         accum = f(accum, $mkref!(self.ptr.post_inc()))?;
2428                         accum = f(accum, $mkref!(self.ptr.post_inc()))?;
2429                     }
2430                     while self.ptr != self.end {
2431                         accum = f(accum, $mkref!(self.ptr.post_inc()))?;
2432                     }
2433                 }
2434                 Try::from_ok(accum)
2435             }
2436
2437             #[inline]
2438             fn fold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc
2439                 where Fold: FnMut(Acc, Self::Item) -> Acc,
2440             {
2441                 // Let LLVM unroll this, rather than using the default
2442                 // impl that would force the manual unrolling above
2443                 let mut accum = init;
2444                 while let Some(x) = self.next() {
2445                     accum = f(accum, x);
2446                 }
2447                 accum
2448             }
2449
2450             #[inline]
2451             #[rustc_inherit_overflow_checks]
2452             fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
2453                 Self: Sized,
2454                 P: FnMut(Self::Item) -> bool,
2455             {
2456                 // The addition might panic on overflow
2457                 // Use the len of the slice to hint optimizer to remove result index bounds check.
2458                 let n = make_slice!(self.ptr, self.end).len();
2459                 self.try_fold(0, move |i, x| {
2460                     if predicate(x) { Err(i) }
2461                     else { Ok(i + 1) }
2462                 }).err()
2463                     .map(|i| {
2464                         unsafe { assume(i < n) };
2465                         i
2466                     })
2467             }
2468
2469             #[inline]
2470             fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
2471                 P: FnMut(Self::Item) -> bool,
2472                 Self: Sized + ExactSizeIterator + DoubleEndedIterator
2473             {
2474                 // No need for an overflow check here, because `ExactSizeIterator`
2475                 // implies that the number of elements fits into a `usize`.
2476                 // Use the len of the slice to hint optimizer to remove result index bounds check.
2477                 let n = make_slice!(self.ptr, self.end).len();
2478                 self.try_rfold(n, move |i, x| {
2479                     let i = i - 1;
2480                     if predicate(x) { Err(i) }
2481                     else { Ok(i) }
2482                 }).err()
2483                     .map(|i| {
2484                         unsafe { assume(i < n) };
2485                         i
2486                     })
2487             }
2488         }
2489
2490         #[stable(feature = "rust1", since = "1.0.0")]
2491         impl<'a, T> DoubleEndedIterator for $name<'a, T> {
2492             #[inline]
2493             fn next_back(&mut self) -> Option<$elem> {
2494                 // could be implemented with slices, but this avoids bounds checks
2495                 unsafe {
2496                     if mem::size_of::<T>() != 0 {
2497                         assume(!self.ptr.is_null());
2498                         assume(!self.end.is_null());
2499                     }
2500                     if self.end == self.ptr {
2501                         None
2502                     } else {
2503                         Some($mkref!(self.end.pre_dec()))
2504                     }
2505                 }
2506             }
2507
2508             #[inline]
2509             fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
2510                 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
2511             {
2512                 // manual unrolling is needed when there are conditional exits from the loop
2513                 let mut accum = init;
2514                 unsafe {
2515                     while ptrdistance(self.ptr, self.end) >= 4 {
2516                         accum = f(accum, $mkref!(self.end.pre_dec()))?;
2517                         accum = f(accum, $mkref!(self.end.pre_dec()))?;
2518                         accum = f(accum, $mkref!(self.end.pre_dec()))?;
2519                         accum = f(accum, $mkref!(self.end.pre_dec()))?;
2520                     }
2521                     while self.ptr != self.end {
2522                         accum = f(accum, $mkref!(self.end.pre_dec()))?;
2523                     }
2524                 }
2525                 Try::from_ok(accum)
2526             }
2527
2528             #[inline]
2529             fn rfold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc
2530                 where Fold: FnMut(Acc, Self::Item) -> Acc,
2531             {
2532                 // Let LLVM unroll this, rather than using the default
2533                 // impl that would force the manual unrolling above
2534                 let mut accum = init;
2535                 while let Some(x) = self.next_back() {
2536                     accum = f(accum, x);
2537                 }
2538                 accum
2539             }
2540         }
2541
2542         #[stable(feature = "fused", since = "1.26.0")]
2543         impl<'a, T> FusedIterator for $name<'a, T> {}
2544
2545         #[unstable(feature = "trusted_len", issue = "37572")]
2546         unsafe impl<'a, T> TrustedLen for $name<'a, T> {}
2547     }
2548 }
2549
2550 macro_rules! make_slice {
2551     ($start: expr, $end: expr) => {{
2552         let start = $start;
2553         let diff = ($end as usize).wrapping_sub(start as usize);
2554         if size_from_ptr(start) == 0 {
2555             // use a non-null pointer value
2556             unsafe { from_raw_parts(1 as *const _, diff) }
2557         } else {
2558             let len = diff / size_from_ptr(start);
2559             unsafe { from_raw_parts(start, len) }
2560         }
2561     }}
2562 }
2563
2564 macro_rules! make_mut_slice {
2565     ($start: expr, $end: expr) => {{
2566         let start = $start;
2567         let diff = ($end as usize).wrapping_sub(start as usize);
2568         if size_from_ptr(start) == 0 {
2569             // use a non-null pointer value
2570             unsafe { from_raw_parts_mut(1 as *mut _, diff) }
2571         } else {
2572             let len = diff / size_from_ptr(start);
2573             unsafe { from_raw_parts_mut(start, len) }
2574         }
2575     }}
2576 }
2577
2578 /// Immutable slice iterator
2579 ///
2580 /// This struct is created by the [`iter`] method on [slices].
2581 ///
2582 /// # Examples
2583 ///
2584 /// Basic usage:
2585 ///
2586 /// ```
2587 /// // First, we declare a type which has `iter` method to get the `Iter` struct (&[usize here]):
2588 /// let slice = &[1, 2, 3];
2589 ///
2590 /// // Then, we iterate over it:
2591 /// for element in slice.iter() {
2592 ///     println!("{}", element);
2593 /// }
2594 /// ```
2595 ///
2596 /// [`iter`]: ../../std/primitive.slice.html#method.iter
2597 /// [slices]: ../../std/primitive.slice.html
2598 #[stable(feature = "rust1", since = "1.0.0")]
2599 pub struct Iter<'a, T: 'a> {
2600     ptr: *const T,
2601     end: *const T,
2602     _marker: marker::PhantomData<&'a T>,
2603 }
2604
2605 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2606 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Iter<'a, T> {
2607     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2608         f.debug_tuple("Iter")
2609             .field(&self.as_slice())
2610             .finish()
2611     }
2612 }
2613
2614 #[stable(feature = "rust1", since = "1.0.0")]
2615 unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}
2616 #[stable(feature = "rust1", since = "1.0.0")]
2617 unsafe impl<'a, T: Sync> Send for Iter<'a, T> {}
2618
2619 impl<'a, T> Iter<'a, T> {
2620     /// View the underlying data as a subslice of the original data.
2621     ///
2622     /// This has the same lifetime as the original slice, and so the
2623     /// iterator can continue to be used while this exists.
2624     ///
2625     /// # Examples
2626     ///
2627     /// Basic usage:
2628     ///
2629     /// ```
2630     /// // First, we declare a type which has the `iter` method to get the `Iter`
2631     /// // struct (&[usize here]):
2632     /// let slice = &[1, 2, 3];
2633     ///
2634     /// // Then, we get the iterator:
2635     /// let mut iter = slice.iter();
2636     /// // So if we print what `as_slice` method returns here, we have "[1, 2, 3]":
2637     /// println!("{:?}", iter.as_slice());
2638     ///
2639     /// // Next, we move to the second element of the slice:
2640     /// iter.next();
2641     /// // Now `as_slice` returns "[2, 3]":
2642     /// println!("{:?}", iter.as_slice());
2643     /// ```
2644     #[stable(feature = "iter_to_slice", since = "1.4.0")]
2645     pub fn as_slice(&self) -> &'a [T] {
2646         make_slice!(self.ptr, self.end)
2647     }
2648
2649     // Helper function for Iter::nth
2650     fn iter_nth(&mut self, n: usize) -> Option<&'a T> {
2651         match self.as_slice().get(n) {
2652             Some(elem_ref) => unsafe {
2653                 self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
2654                 Some(elem_ref)
2655             },
2656             None => {
2657                 self.ptr = self.end;
2658                 None
2659             }
2660         }
2661     }
2662 }
2663
2664 iterator!{struct Iter -> *const T, &'a T, make_ref}
2665
2666 #[stable(feature = "rust1", since = "1.0.0")]
2667 impl<'a, T> ExactSizeIterator for Iter<'a, T> {
2668     fn is_empty(&self) -> bool {
2669         self.ptr == self.end
2670     }
2671 }
2672
2673 #[stable(feature = "rust1", since = "1.0.0")]
2674 impl<'a, T> Clone for Iter<'a, T> {
2675     fn clone(&self) -> Iter<'a, T> { Iter { ptr: self.ptr, end: self.end, _marker: self._marker } }
2676 }
2677
2678 #[stable(feature = "slice_iter_as_ref", since = "1.13.0")]
2679 impl<'a, T> AsRef<[T]> for Iter<'a, T> {
2680     fn as_ref(&self) -> &[T] {
2681         self.as_slice()
2682     }
2683 }
2684
2685 /// Mutable slice iterator.
2686 ///
2687 /// This struct is created by the [`iter_mut`] method on [slices].
2688 ///
2689 /// # Examples
2690 ///
2691 /// Basic usage:
2692 ///
2693 /// ```
2694 /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
2695 /// // struct (&[usize here]):
2696 /// let mut slice = &mut [1, 2, 3];
2697 ///
2698 /// // Then, we iterate over it and increment each element value:
2699 /// for element in slice.iter_mut() {
2700 ///     *element += 1;
2701 /// }
2702 ///
2703 /// // We now have "[2, 3, 4]":
2704 /// println!("{:?}", slice);
2705 /// ```
2706 ///
2707 /// [`iter_mut`]: ../../std/primitive.slice.html#method.iter_mut
2708 /// [slices]: ../../std/primitive.slice.html
2709 #[stable(feature = "rust1", since = "1.0.0")]
2710 pub struct IterMut<'a, T: 'a> {
2711     ptr: *mut T,
2712     end: *mut T,
2713     _marker: marker::PhantomData<&'a mut T>,
2714 }
2715
2716 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2717 impl<'a, T: 'a + fmt::Debug> fmt::Debug for IterMut<'a, T> {
2718     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2719         f.debug_tuple("IterMut")
2720             .field(&make_slice!(self.ptr, self.end))
2721             .finish()
2722     }
2723 }
2724
2725 #[stable(feature = "rust1", since = "1.0.0")]
2726 unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
2727 #[stable(feature = "rust1", since = "1.0.0")]
2728 unsafe impl<'a, T: Send> Send for IterMut<'a, T> {}
2729
2730 impl<'a, T> IterMut<'a, T> {
2731     /// View the underlying data as a subslice of the original data.
2732     ///
2733     /// To avoid creating `&mut` references that alias, this is forced
2734     /// to consume the iterator.
2735     ///
2736     /// # Examples
2737     ///
2738     /// Basic usage:
2739     ///
2740     /// ```
2741     /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
2742     /// // struct (&[usize here]):
2743     /// let mut slice = &mut [1, 2, 3];
2744     ///
2745     /// {
2746     ///     // Then, we get the iterator:
2747     ///     let mut iter = slice.iter_mut();
2748     ///     // We move to next element:
2749     ///     iter.next();
2750     ///     // So if we print what `into_slice` method returns here, we have "[2, 3]":
2751     ///     println!("{:?}", iter.into_slice());
2752     /// }
2753     ///
2754     /// // Now let's modify a value of the slice:
2755     /// {
2756     ///     // First we get back the iterator:
2757     ///     let mut iter = slice.iter_mut();
2758     ///     // We change the value of the first element of the slice returned by the `next` method:
2759     ///     *iter.next().unwrap() += 1;
2760     /// }
2761     /// // Now slice is "[2, 2, 3]":
2762     /// println!("{:?}", slice);
2763     /// ```
2764     #[stable(feature = "iter_to_slice", since = "1.4.0")]
2765     pub fn into_slice(self) -> &'a mut [T] {
2766         make_mut_slice!(self.ptr, self.end)
2767     }
2768
2769     // Helper function for IterMut::nth
2770     fn iter_nth(&mut self, n: usize) -> Option<&'a mut T> {
2771         match make_mut_slice!(self.ptr, self.end).get_mut(n) {
2772             Some(elem_ref) => unsafe {
2773                 self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
2774                 Some(elem_ref)
2775             },
2776             None => {
2777                 self.ptr = self.end;
2778                 None
2779             }
2780         }
2781     }
2782 }
2783
2784 iterator!{struct IterMut -> *mut T, &'a mut T, make_ref_mut}
2785
2786 #[stable(feature = "rust1", since = "1.0.0")]
2787 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {
2788     fn is_empty(&self) -> bool {
2789         self.ptr == self.end
2790     }
2791 }
2792
2793 // Return the number of elements of `T` from `start` to `end`.
2794 // Return the arithmetic difference if `T` is zero size.
2795 #[inline(always)]
2796 unsafe fn ptrdistance<T>(start: *const T, end: *const T) -> usize {
2797     if mem::size_of::<T>() == 0 {
2798         (end as usize).wrapping_sub(start as usize)
2799     } else {
2800         end.offset_from(start) as usize
2801     }
2802 }
2803
2804 // Extension methods for raw pointers, used by the iterators
2805 trait PointerExt : Copy {
2806     unsafe fn slice_offset(self, i: isize) -> Self;
2807
2808     /// Increments `self` by 1, but returns the old value.
2809     #[inline(always)]
2810     unsafe fn post_inc(&mut self) -> Self {
2811         let current = *self;
2812         *self = self.slice_offset(1);
2813         current
2814     }
2815
2816     /// Decrements `self` by 1, and returns the new value.
2817     #[inline(always)]
2818     unsafe fn pre_dec(&mut self) -> Self {
2819         *self = self.slice_offset(-1);
2820         *self
2821     }
2822 }
2823
2824 impl<T> PointerExt for *const T {
2825     #[inline(always)]
2826     unsafe fn slice_offset(self, i: isize) -> Self {
2827         slice_offset!(self, i)
2828     }
2829 }
2830
2831 impl<T> PointerExt for *mut T {
2832     #[inline(always)]
2833     unsafe fn slice_offset(self, i: isize) -> Self {
2834         slice_offset!(self, i)
2835     }
2836 }
2837
2838 /// An internal abstraction over the splitting iterators, so that
2839 /// splitn, splitn_mut etc can be implemented once.
2840 #[doc(hidden)]
2841 trait SplitIter: DoubleEndedIterator {
2842     /// Marks the underlying iterator as complete, extracting the remaining
2843     /// portion of the slice.
2844     fn finish(&mut self) -> Option<Self::Item>;
2845 }
2846
2847 /// An iterator over subslices separated by elements that match a predicate
2848 /// function.
2849 ///
2850 /// This struct is created by the [`split`] method on [slices].
2851 ///
2852 /// [`split`]: ../../std/primitive.slice.html#method.split
2853 /// [slices]: ../../std/primitive.slice.html
2854 #[stable(feature = "rust1", since = "1.0.0")]
2855 pub struct Split<'a, T:'a, P> where P: FnMut(&T) -> bool {
2856     v: &'a [T],
2857     pred: P,
2858     finished: bool
2859 }
2860
2861 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2862 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for Split<'a, T, P> where P: FnMut(&T) -> bool {
2863     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2864         f.debug_struct("Split")
2865             .field("v", &self.v)
2866             .field("finished", &self.finished)
2867             .finish()
2868     }
2869 }
2870
2871 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2872 #[stable(feature = "rust1", since = "1.0.0")]
2873 impl<'a, T, P> Clone for Split<'a, T, P> where P: Clone + FnMut(&T) -> bool {
2874     fn clone(&self) -> Split<'a, T, P> {
2875         Split {
2876             v: self.v,
2877             pred: self.pred.clone(),
2878             finished: self.finished,
2879         }
2880     }
2881 }
2882
2883 #[stable(feature = "rust1", since = "1.0.0")]
2884 impl<'a, T, P> Iterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
2885     type Item = &'a [T];
2886
2887     #[inline]
2888     fn next(&mut self) -> Option<&'a [T]> {
2889         if self.finished { return None; }
2890
2891         match self.v.iter().position(|x| (self.pred)(x)) {
2892             None => self.finish(),
2893             Some(idx) => {
2894                 let ret = Some(&self.v[..idx]);
2895                 self.v = &self.v[idx + 1..];
2896                 ret
2897             }
2898         }
2899     }
2900
2901     #[inline]
2902     fn size_hint(&self) -> (usize, Option<usize>) {
2903         if self.finished {
2904             (0, Some(0))
2905         } else {
2906             (1, Some(self.v.len() + 1))
2907         }
2908     }
2909 }
2910
2911 #[stable(feature = "rust1", since = "1.0.0")]
2912 impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
2913     #[inline]
2914     fn next_back(&mut self) -> Option<&'a [T]> {
2915         if self.finished { return None; }
2916
2917         match self.v.iter().rposition(|x| (self.pred)(x)) {
2918             None => self.finish(),
2919             Some(idx) => {
2920                 let ret = Some(&self.v[idx + 1..]);
2921                 self.v = &self.v[..idx];
2922                 ret
2923             }
2924         }
2925     }
2926 }
2927
2928 impl<'a, T, P> SplitIter for Split<'a, T, P> where P: FnMut(&T) -> bool {
2929     #[inline]
2930     fn finish(&mut self) -> Option<&'a [T]> {
2931         if self.finished { None } else { self.finished = true; Some(self.v) }
2932     }
2933 }
2934
2935 #[stable(feature = "fused", since = "1.26.0")]
2936 impl<'a, T, P> FusedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool {}
2937
2938 /// An iterator over the subslices of the vector which are separated
2939 /// by elements that match `pred`.
2940 ///
2941 /// This struct is created by the [`split_mut`] method on [slices].
2942 ///
2943 /// [`split_mut`]: ../../std/primitive.slice.html#method.split_mut
2944 /// [slices]: ../../std/primitive.slice.html
2945 #[stable(feature = "rust1", since = "1.0.0")]
2946 pub struct SplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
2947     v: &'a mut [T],
2948     pred: P,
2949     finished: bool
2950 }
2951
2952 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2953 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
2954     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2955         f.debug_struct("SplitMut")
2956             .field("v", &self.v)
2957             .field("finished", &self.finished)
2958             .finish()
2959     }
2960 }
2961
2962 impl<'a, T, P> SplitIter for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
2963     #[inline]
2964     fn finish(&mut self) -> Option<&'a mut [T]> {
2965         if self.finished {
2966             None
2967         } else {
2968             self.finished = true;
2969             Some(mem::replace(&mut self.v, &mut []))
2970         }
2971     }
2972 }
2973
2974 #[stable(feature = "rust1", since = "1.0.0")]
2975 impl<'a, T, P> Iterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
2976     type Item = &'a mut [T];
2977
2978     #[inline]
2979     fn next(&mut self) -> Option<&'a mut [T]> {
2980         if self.finished { return None; }
2981
2982         let idx_opt = { // work around borrowck limitations
2983             let pred = &mut self.pred;
2984             self.v.iter().position(|x| (*pred)(x))
2985         };
2986         match idx_opt {
2987             None => self.finish(),
2988             Some(idx) => {
2989                 let tmp = mem::replace(&mut self.v, &mut []);
2990                 let (head, tail) = tmp.split_at_mut(idx);
2991                 self.v = &mut tail[1..];
2992                 Some(head)
2993             }
2994         }
2995     }
2996
2997     #[inline]
2998     fn size_hint(&self) -> (usize, Option<usize>) {
2999         if self.finished {
3000             (0, Some(0))
3001         } else {
3002             // if the predicate doesn't match anything, we yield one slice
3003             // if it matches every element, we yield len+1 empty slices.
3004             (1, Some(self.v.len() + 1))
3005         }
3006     }
3007 }
3008
3009 #[stable(feature = "rust1", since = "1.0.0")]
3010 impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P> where
3011     P: FnMut(&T) -> bool,
3012 {
3013     #[inline]
3014     fn next_back(&mut self) -> Option<&'a mut [T]> {
3015         if self.finished { return None; }
3016
3017         let idx_opt = { // work around borrowck limitations
3018             let pred = &mut self.pred;
3019             self.v.iter().rposition(|x| (*pred)(x))
3020         };
3021         match idx_opt {
3022             None => self.finish(),
3023             Some(idx) => {
3024                 let tmp = mem::replace(&mut self.v, &mut []);
3025                 let (head, tail) = tmp.split_at_mut(idx);
3026                 self.v = head;
3027                 Some(&mut tail[1..])
3028             }
3029         }
3030     }
3031 }
3032
3033 #[stable(feature = "fused", since = "1.26.0")]
3034 impl<'a, T, P> FusedIterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {}
3035
3036 /// An iterator over subslices separated by elements that match a predicate
3037 /// function, starting from the end of the slice.
3038 ///
3039 /// This struct is created by the [`rsplit`] method on [slices].
3040 ///
3041 /// [`rsplit`]: ../../std/primitive.slice.html#method.rsplit
3042 /// [slices]: ../../std/primitive.slice.html
3043 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3044 #[derive(Clone)] // Is this correct, or does it incorrectly require `T: Clone`?
3045 pub struct RSplit<'a, T:'a, P> where P: FnMut(&T) -> bool {
3046     inner: Split<'a, T, P>
3047 }
3048
3049 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3050 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3051     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3052         f.debug_struct("RSplit")
3053             .field("v", &self.inner.v)
3054             .field("finished", &self.inner.finished)
3055             .finish()
3056     }
3057 }
3058
3059 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3060 impl<'a, T, P> Iterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3061     type Item = &'a [T];
3062
3063     #[inline]
3064     fn next(&mut self) -> Option<&'a [T]> {
3065         self.inner.next_back()
3066     }
3067
3068     #[inline]
3069     fn size_hint(&self) -> (usize, Option<usize>) {
3070         self.inner.size_hint()
3071     }
3072 }
3073
3074 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3075 impl<'a, T, P> DoubleEndedIterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3076     #[inline]
3077     fn next_back(&mut self) -> Option<&'a [T]> {
3078         self.inner.next()
3079     }
3080 }
3081
3082 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3083 impl<'a, T, P> SplitIter for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3084     #[inline]
3085     fn finish(&mut self) -> Option<&'a [T]> {
3086         self.inner.finish()
3087     }
3088 }
3089
3090 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3091 impl<'a, T, P> FusedIterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {}
3092
3093 /// An iterator over the subslices of the vector which are separated
3094 /// by elements that match `pred`, starting from the end of the slice.
3095 ///
3096 /// This struct is created by the [`rsplit_mut`] method on [slices].
3097 ///
3098 /// [`rsplit_mut`]: ../../std/primitive.slice.html#method.rsplit_mut
3099 /// [slices]: ../../std/primitive.slice.html
3100 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3101 pub struct RSplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
3102     inner: SplitMut<'a, T, P>
3103 }
3104
3105 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3106 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
3107     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3108         f.debug_struct("RSplitMut")
3109             .field("v", &self.inner.v)
3110             .field("finished", &self.inner.finished)
3111             .finish()
3112     }
3113 }
3114
3115 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3116 impl<'a, T, P> SplitIter for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
3117     #[inline]
3118     fn finish(&mut self) -> Option<&'a mut [T]> {
3119         self.inner.finish()
3120     }
3121 }
3122
3123 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3124 impl<'a, T, P> Iterator for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
3125     type Item = &'a mut [T];
3126
3127     #[inline]
3128     fn next(&mut self) -> Option<&'a mut [T]> {
3129         self.inner.next_back()
3130     }
3131
3132     #[inline]
3133     fn size_hint(&self) -> (usize, Option<usize>) {
3134         self.inner.size_hint()
3135     }
3136 }
3137
3138 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3139 impl<'a, T, P> DoubleEndedIterator for RSplitMut<'a, T, P> where
3140     P: FnMut(&T) -> bool,
3141 {
3142     #[inline]
3143     fn next_back(&mut self) -> Option<&'a mut [T]> {
3144         self.inner.next()
3145     }
3146 }
3147
3148 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3149 impl<'a, T, P> FusedIterator for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {}
3150
3151 /// An private iterator over subslices separated by elements that
3152 /// match a predicate function, splitting at most a fixed number of
3153 /// times.
3154 #[derive(Debug)]
3155 struct GenericSplitN<I> {
3156     iter: I,
3157     count: usize,
3158 }
3159
3160 impl<T, I: SplitIter<Item=T>> Iterator for GenericSplitN<I> {
3161     type Item = T;
3162
3163     #[inline]
3164     fn next(&mut self) -> Option<T> {
3165         match self.count {
3166             0 => None,
3167             1 => { self.count -= 1; self.iter.finish() }
3168             _ => { self.count -= 1; self.iter.next() }
3169         }
3170     }
3171
3172     #[inline]
3173     fn size_hint(&self) -> (usize, Option<usize>) {
3174         let (lower, upper_opt) = self.iter.size_hint();
3175         (lower, upper_opt.map(|upper| cmp::min(self.count, upper)))
3176     }
3177 }
3178
3179 /// An iterator over subslices separated by elements that match a predicate
3180 /// function, limited to a given number of splits.
3181 ///
3182 /// This struct is created by the [`splitn`] method on [slices].
3183 ///
3184 /// [`splitn`]: ../../std/primitive.slice.html#method.splitn
3185 /// [slices]: ../../std/primitive.slice.html
3186 #[stable(feature = "rust1", since = "1.0.0")]
3187 pub struct SplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3188     inner: GenericSplitN<Split<'a, T, P>>
3189 }
3190
3191 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3192 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitN<'a, T, P> where P: FnMut(&T) -> bool {
3193     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3194         f.debug_struct("SplitN")
3195             .field("inner", &self.inner)
3196             .finish()
3197     }
3198 }
3199
3200 /// An iterator over subslices separated by elements that match a
3201 /// predicate function, limited to a given number of splits, starting
3202 /// from the end of the slice.
3203 ///
3204 /// This struct is created by the [`rsplitn`] method on [slices].
3205 ///
3206 /// [`rsplitn`]: ../../std/primitive.slice.html#method.rsplitn
3207 /// [slices]: ../../std/primitive.slice.html
3208 #[stable(feature = "rust1", since = "1.0.0")]
3209 pub struct RSplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3210     inner: GenericSplitN<RSplit<'a, T, P>>
3211 }
3212
3213 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3214 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitN<'a, T, P> where P: FnMut(&T) -> bool {
3215     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3216         f.debug_struct("RSplitN")
3217             .field("inner", &self.inner)
3218             .finish()
3219     }
3220 }
3221
3222 /// An iterator over subslices separated by elements that match a predicate
3223 /// function, limited to a given number of splits.
3224 ///
3225 /// This struct is created by the [`splitn_mut`] method on [slices].
3226 ///
3227 /// [`splitn_mut`]: ../../std/primitive.slice.html#method.splitn_mut
3228 /// [slices]: ../../std/primitive.slice.html
3229 #[stable(feature = "rust1", since = "1.0.0")]
3230 pub struct SplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3231     inner: GenericSplitN<SplitMut<'a, T, P>>
3232 }
3233
3234 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3235 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitNMut<'a, T, P> where P: FnMut(&T) -> bool {
3236     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3237         f.debug_struct("SplitNMut")
3238             .field("inner", &self.inner)
3239             .finish()
3240     }
3241 }
3242
3243 /// An iterator over subslices separated by elements that match a
3244 /// predicate function, limited to a given number of splits, starting
3245 /// from the end of the slice.
3246 ///
3247 /// This struct is created by the [`rsplitn_mut`] method on [slices].
3248 ///
3249 /// [`rsplitn_mut`]: ../../std/primitive.slice.html#method.rsplitn_mut
3250 /// [slices]: ../../std/primitive.slice.html
3251 #[stable(feature = "rust1", since = "1.0.0")]
3252 pub struct RSplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3253     inner: GenericSplitN<RSplitMut<'a, T, P>>
3254 }
3255
3256 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3257 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitNMut<'a, T, P> where P: FnMut(&T) -> bool {
3258     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3259         f.debug_struct("RSplitNMut")
3260             .field("inner", &self.inner)
3261             .finish()
3262     }
3263 }
3264
3265 macro_rules! forward_iterator {
3266     ($name:ident: $elem:ident, $iter_of:ty) => {
3267         #[stable(feature = "rust1", since = "1.0.0")]
3268         impl<'a, $elem, P> Iterator for $name<'a, $elem, P> where
3269             P: FnMut(&T) -> bool
3270         {
3271             type Item = $iter_of;
3272
3273             #[inline]
3274             fn next(&mut self) -> Option<$iter_of> {
3275                 self.inner.next()
3276             }
3277
3278             #[inline]
3279             fn size_hint(&self) -> (usize, Option<usize>) {
3280                 self.inner.size_hint()
3281             }
3282         }
3283
3284         #[stable(feature = "fused", since = "1.26.0")]
3285         impl<'a, $elem, P> FusedIterator for $name<'a, $elem, P>
3286             where P: FnMut(&T) -> bool {}
3287     }
3288 }
3289
3290 forward_iterator! { SplitN: T, &'a [T] }
3291 forward_iterator! { RSplitN: T, &'a [T] }
3292 forward_iterator! { SplitNMut: T, &'a mut [T] }
3293 forward_iterator! { RSplitNMut: T, &'a mut [T] }
3294
3295 /// An iterator over overlapping subslices of length `size`.
3296 ///
3297 /// This struct is created by the [`windows`] method on [slices].
3298 ///
3299 /// [`windows`]: ../../std/primitive.slice.html#method.windows
3300 /// [slices]: ../../std/primitive.slice.html
3301 #[derive(Debug)]
3302 #[stable(feature = "rust1", since = "1.0.0")]
3303 pub struct Windows<'a, T:'a> {
3304     v: &'a [T],
3305     size: usize
3306 }
3307
3308 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
3309 #[stable(feature = "rust1", since = "1.0.0")]
3310 impl<'a, T> Clone for Windows<'a, T> {
3311     fn clone(&self) -> Windows<'a, T> {
3312         Windows {
3313             v: self.v,
3314             size: self.size,
3315         }
3316     }
3317 }
3318
3319 #[stable(feature = "rust1", since = "1.0.0")]
3320 impl<'a, T> Iterator for Windows<'a, T> {
3321     type Item = &'a [T];
3322
3323     #[inline]
3324     fn next(&mut self) -> Option<&'a [T]> {
3325         if self.size > self.v.len() {
3326             None
3327         } else {
3328             let ret = Some(&self.v[..self.size]);
3329             self.v = &self.v[1..];
3330             ret
3331         }
3332     }
3333
3334     #[inline]
3335     fn size_hint(&self) -> (usize, Option<usize>) {
3336         if self.size > self.v.len() {
3337             (0, Some(0))
3338         } else {
3339             let size = self.v.len() - self.size + 1;
3340             (size, Some(size))
3341         }
3342     }
3343
3344     #[inline]
3345     fn count(self) -> usize {
3346         self.len()
3347     }
3348
3349     #[inline]
3350     fn nth(&mut self, n: usize) -> Option<Self::Item> {
3351         let (end, overflow) = self.size.overflowing_add(n);
3352         if end > self.v.len() || overflow {
3353             self.v = &[];
3354             None
3355         } else {
3356             let nth = &self.v[n..end];
3357             self.v = &self.v[n+1..];
3358             Some(nth)
3359         }
3360     }
3361
3362     #[inline]
3363     fn last(self) -> Option<Self::Item> {
3364         if self.size > self.v.len() {
3365             None
3366         } else {
3367             let start = self.v.len() - self.size;
3368             Some(&self.v[start..])
3369         }
3370     }
3371 }
3372
3373 #[stable(feature = "rust1", since = "1.0.0")]
3374 impl<'a, T> DoubleEndedIterator for Windows<'a, T> {
3375     #[inline]
3376     fn next_back(&mut self) -> Option<&'a [T]> {
3377         if self.size > self.v.len() {
3378             None
3379         } else {
3380             let ret = Some(&self.v[self.v.len()-self.size..]);
3381             self.v = &self.v[..self.v.len()-1];
3382             ret
3383         }
3384     }
3385 }
3386
3387 #[stable(feature = "rust1", since = "1.0.0")]
3388 impl<'a, T> ExactSizeIterator for Windows<'a, T> {}
3389
3390 #[unstable(feature = "trusted_len", issue = "37572")]
3391 unsafe impl<'a, T> TrustedLen for Windows<'a, T> {}
3392
3393 #[stable(feature = "fused", since = "1.26.0")]
3394 impl<'a, T> FusedIterator for Windows<'a, T> {}
3395
3396 #[doc(hidden)]
3397 unsafe impl<'a, T> TrustedRandomAccess for Windows<'a, T> {
3398     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
3399         from_raw_parts(self.v.as_ptr().offset(i as isize), self.size)
3400     }
3401     fn may_have_side_effect() -> bool { false }
3402 }
3403
3404 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
3405 /// time).
3406 ///
3407 /// When the slice len is not evenly divided by the chunk size, the last slice
3408 /// of the iteration will be the remainder.
3409 ///
3410 /// This struct is created by the [`chunks`] method on [slices].
3411 ///
3412 /// [`chunks`]: ../../std/primitive.slice.html#method.chunks
3413 /// [slices]: ../../std/primitive.slice.html
3414 #[derive(Debug)]
3415 #[stable(feature = "rust1", since = "1.0.0")]
3416 pub struct Chunks<'a, T:'a> {
3417     v: &'a [T],
3418     chunk_size: usize
3419 }
3420
3421 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
3422 #[stable(feature = "rust1", since = "1.0.0")]
3423 impl<'a, T> Clone for Chunks<'a, T> {
3424     fn clone(&self) -> Chunks<'a, T> {
3425         Chunks {
3426             v: self.v,
3427             chunk_size: self.chunk_size,
3428         }
3429     }
3430 }
3431
3432 #[stable(feature = "rust1", since = "1.0.0")]
3433 impl<'a, T> Iterator for Chunks<'a, T> {
3434     type Item = &'a [T];
3435
3436     #[inline]
3437     fn next(&mut self) -> Option<&'a [T]> {
3438         if self.v.is_empty() {
3439             None
3440         } else {
3441             let chunksz = cmp::min(self.v.len(), self.chunk_size);
3442             let (fst, snd) = self.v.split_at(chunksz);
3443             self.v = snd;
3444             Some(fst)
3445         }
3446     }
3447
3448     #[inline]
3449     fn size_hint(&self) -> (usize, Option<usize>) {
3450         if self.v.is_empty() {
3451             (0, Some(0))
3452         } else {
3453             let n = self.v.len() / self.chunk_size;
3454             let rem = self.v.len() % self.chunk_size;
3455             let n = if rem > 0 { n+1 } else { n };
3456             (n, Some(n))
3457         }
3458     }
3459
3460     #[inline]
3461     fn count(self) -> usize {
3462         self.len()
3463     }
3464
3465     #[inline]
3466     fn nth(&mut self, n: usize) -> Option<Self::Item> {
3467         let (start, overflow) = n.overflowing_mul(self.chunk_size);
3468         if start >= self.v.len() || overflow {
3469             self.v = &[];
3470             None
3471         } else {
3472             let end = match start.checked_add(self.chunk_size) {
3473                 Some(sum) => cmp::min(self.v.len(), sum),
3474                 None => self.v.len(),
3475             };
3476             let nth = &self.v[start..end];
3477             self.v = &self.v[end..];
3478             Some(nth)
3479         }
3480     }
3481
3482     #[inline]
3483     fn last(self) -> Option<Self::Item> {
3484         if self.v.is_empty() {
3485             None
3486         } else {
3487             let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
3488             Some(&self.v[start..])
3489         }
3490     }
3491 }
3492
3493 #[stable(feature = "rust1", since = "1.0.0")]
3494 impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
3495     #[inline]
3496     fn next_back(&mut self) -> Option<&'a [T]> {
3497         if self.v.is_empty() {
3498             None
3499         } else {
3500             let remainder = self.v.len() % self.chunk_size;
3501             let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
3502             let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
3503             self.v = fst;
3504             Some(snd)
3505         }
3506     }
3507 }
3508
3509 #[stable(feature = "rust1", since = "1.0.0")]
3510 impl<'a, T> ExactSizeIterator for Chunks<'a, T> {}
3511
3512 #[unstable(feature = "trusted_len", issue = "37572")]
3513 unsafe impl<'a, T> TrustedLen for Chunks<'a, T> {}
3514
3515 #[stable(feature = "fused", since = "1.26.0")]
3516 impl<'a, T> FusedIterator for Chunks<'a, T> {}
3517
3518 #[doc(hidden)]
3519 unsafe impl<'a, T> TrustedRandomAccess for Chunks<'a, T> {
3520     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
3521         let start = i * self.chunk_size;
3522         let end = match start.checked_add(self.chunk_size) {
3523             None => self.v.len(),
3524             Some(end) => cmp::min(end, self.v.len()),
3525         };
3526         from_raw_parts(self.v.as_ptr().offset(start as isize), end - start)
3527     }
3528     fn may_have_side_effect() -> bool { false }
3529 }
3530
3531 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
3532 /// elements at a time). When the slice len is not evenly divided by the chunk
3533 /// size, the last slice of the iteration will be the remainder.
3534 ///
3535 /// This struct is created by the [`chunks_mut`] method on [slices].
3536 ///
3537 /// [`chunks_mut`]: ../../std/primitive.slice.html#method.chunks_mut
3538 /// [slices]: ../../std/primitive.slice.html
3539 #[derive(Debug)]
3540 #[stable(feature = "rust1", since = "1.0.0")]
3541 pub struct ChunksMut<'a, T:'a> {
3542     v: &'a mut [T],
3543     chunk_size: usize
3544 }
3545
3546 #[stable(feature = "rust1", since = "1.0.0")]
3547 impl<'a, T> Iterator for ChunksMut<'a, T> {
3548     type Item = &'a mut [T];
3549
3550     #[inline]
3551     fn next(&mut self) -> Option<&'a mut [T]> {
3552         if self.v.is_empty() {
3553             None
3554         } else {
3555             let sz = cmp::min(self.v.len(), self.chunk_size);
3556             let tmp = mem::replace(&mut self.v, &mut []);
3557             let (head, tail) = tmp.split_at_mut(sz);
3558             self.v = tail;
3559             Some(head)
3560         }
3561     }
3562
3563     #[inline]
3564     fn size_hint(&self) -> (usize, Option<usize>) {
3565         if self.v.is_empty() {
3566             (0, Some(0))
3567         } else {
3568             let n = self.v.len() / self.chunk_size;
3569             let rem = self.v.len() % self.chunk_size;
3570             let n = if rem > 0 { n + 1 } else { n };
3571             (n, Some(n))
3572         }
3573     }
3574
3575     #[inline]
3576     fn count(self) -> usize {
3577         self.len()
3578     }
3579
3580     #[inline]
3581     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
3582         let (start, overflow) = n.overflowing_mul(self.chunk_size);
3583         if start >= self.v.len() || overflow {
3584             self.v = &mut [];
3585             None
3586         } else {
3587             let end = match start.checked_add(self.chunk_size) {
3588                 Some(sum) => cmp::min(self.v.len(), sum),
3589                 None => self.v.len(),
3590             };
3591             let tmp = mem::replace(&mut self.v, &mut []);
3592             let (head, tail) = tmp.split_at_mut(end);
3593             let (_, nth) =  head.split_at_mut(start);
3594             self.v = tail;
3595             Some(nth)
3596         }
3597     }
3598
3599     #[inline]
3600     fn last(self) -> Option<Self::Item> {
3601         if self.v.is_empty() {
3602             None
3603         } else {
3604             let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
3605             Some(&mut self.v[start..])
3606         }
3607     }
3608 }
3609
3610 #[stable(feature = "rust1", since = "1.0.0")]
3611 impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
3612     #[inline]
3613     fn next_back(&mut self) -> Option<&'a mut [T]> {
3614         if self.v.is_empty() {
3615             None
3616         } else {
3617             let remainder = self.v.len() % self.chunk_size;
3618             let sz = if remainder != 0 { remainder } else { self.chunk_size };
3619             let tmp = mem::replace(&mut self.v, &mut []);
3620             let tmp_len = tmp.len();
3621             let (head, tail) = tmp.split_at_mut(tmp_len - sz);
3622             self.v = head;
3623             Some(tail)
3624         }
3625     }
3626 }
3627
3628 #[stable(feature = "rust1", since = "1.0.0")]
3629 impl<'a, T> ExactSizeIterator for ChunksMut<'a, T> {}
3630
3631 #[unstable(feature = "trusted_len", issue = "37572")]
3632 unsafe impl<'a, T> TrustedLen for ChunksMut<'a, T> {}
3633
3634 #[stable(feature = "fused", since = "1.26.0")]
3635 impl<'a, T> FusedIterator for ChunksMut<'a, T> {}
3636
3637 #[doc(hidden)]
3638 unsafe impl<'a, T> TrustedRandomAccess for ChunksMut<'a, T> {
3639     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
3640         let start = i * self.chunk_size;
3641         let end = match start.checked_add(self.chunk_size) {
3642             None => self.v.len(),
3643             Some(end) => cmp::min(end, self.v.len()),
3644         };
3645         from_raw_parts_mut(self.v.as_mut_ptr().offset(start as isize), end - start)
3646     }
3647     fn may_have_side_effect() -> bool { false }
3648 }
3649
3650 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
3651 /// time).
3652 ///
3653 /// When the slice len is not evenly divided by the chunk size, the last
3654 /// up to `chunk_size-1` elements will be omitted.
3655 ///
3656 /// This struct is created by the [`exact_chunks`] method on [slices].
3657 ///
3658 /// [`exact_chunks`]: ../../std/primitive.slice.html#method.exact_chunks
3659 /// [slices]: ../../std/primitive.slice.html
3660 #[derive(Debug)]
3661 #[unstable(feature = "exact_chunks", issue = "47115")]
3662 pub struct ExactChunks<'a, T:'a> {
3663     v: &'a [T],
3664     chunk_size: usize
3665 }
3666
3667 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
3668 #[unstable(feature = "exact_chunks", issue = "47115")]
3669 impl<'a, T> Clone for ExactChunks<'a, T> {
3670     fn clone(&self) -> ExactChunks<'a, T> {
3671         ExactChunks {
3672             v: self.v,
3673             chunk_size: self.chunk_size,
3674         }
3675     }
3676 }
3677
3678 #[unstable(feature = "exact_chunks", issue = "47115")]
3679 impl<'a, T> Iterator for ExactChunks<'a, T> {
3680     type Item = &'a [T];
3681
3682     #[inline]
3683     fn next(&mut self) -> Option<&'a [T]> {
3684         if self.v.len() < self.chunk_size {
3685             None
3686         } else {
3687             let (fst, snd) = self.v.split_at(self.chunk_size);
3688             self.v = snd;
3689             Some(fst)
3690         }
3691     }
3692
3693     #[inline]
3694     fn size_hint(&self) -> (usize, Option<usize>) {
3695         let n = self.v.len() / self.chunk_size;
3696         (n, Some(n))
3697     }
3698
3699     #[inline]
3700     fn count(self) -> usize {
3701         self.len()
3702     }
3703
3704     #[inline]
3705     fn nth(&mut self, n: usize) -> Option<Self::Item> {
3706         let (start, overflow) = n.overflowing_mul(self.chunk_size);
3707         if start >= self.v.len() || overflow {
3708             self.v = &[];
3709             None
3710         } else {
3711             let (_, snd) = self.v.split_at(start);
3712             self.v = snd;
3713             self.next()
3714         }
3715     }
3716
3717     #[inline]
3718     fn last(mut self) -> Option<Self::Item> {
3719         self.next_back()
3720     }
3721 }
3722
3723 #[unstable(feature = "exact_chunks", issue = "47115")]
3724 impl<'a, T> DoubleEndedIterator for ExactChunks<'a, T> {
3725     #[inline]
3726     fn next_back(&mut self) -> Option<&'a [T]> {
3727         if self.v.len() < self.chunk_size {
3728             None
3729         } else {
3730             let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
3731             self.v = fst;
3732             Some(snd)
3733         }
3734     }
3735 }
3736
3737 #[unstable(feature = "exact_chunks", issue = "47115")]
3738 impl<'a, T> ExactSizeIterator for ExactChunks<'a, T> {
3739     fn is_empty(&self) -> bool {
3740         self.v.is_empty()
3741     }
3742 }
3743
3744 #[unstable(feature = "trusted_len", issue = "37572")]
3745 unsafe impl<'a, T> TrustedLen for ExactChunks<'a, T> {}
3746
3747 #[unstable(feature = "exact_chunks", issue = "47115")]
3748 impl<'a, T> FusedIterator for ExactChunks<'a, T> {}
3749
3750 #[doc(hidden)]
3751 unsafe impl<'a, T> TrustedRandomAccess for ExactChunks<'a, T> {
3752     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
3753         let start = i * self.chunk_size;
3754         from_raw_parts(self.v.as_ptr().offset(start as isize), self.chunk_size)
3755     }
3756     fn may_have_side_effect() -> bool { false }
3757 }
3758
3759 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
3760 /// elements at a time). When the slice len is not evenly divided by the chunk
3761 /// size, the last up to `chunk_size-1` elements will be omitted.
3762 ///
3763 /// This struct is created by the [`exact_chunks_mut`] method on [slices].
3764 ///
3765 /// [`exact_chunks_mut`]: ../../std/primitive.slice.html#method.exact_chunks_mut
3766 /// [slices]: ../../std/primitive.slice.html
3767 #[derive(Debug)]
3768 #[unstable(feature = "exact_chunks", issue = "47115")]
3769 pub struct ExactChunksMut<'a, T:'a> {
3770     v: &'a mut [T],
3771     chunk_size: usize
3772 }
3773
3774 #[unstable(feature = "exact_chunks", issue = "47115")]
3775 impl<'a, T> Iterator for ExactChunksMut<'a, T> {
3776     type Item = &'a mut [T];
3777
3778     #[inline]
3779     fn next(&mut self) -> Option<&'a mut [T]> {
3780         if self.v.len() < self.chunk_size {
3781             None
3782         } else {
3783             let tmp = mem::replace(&mut self.v, &mut []);
3784             let (head, tail) = tmp.split_at_mut(self.chunk_size);
3785             self.v = tail;
3786             Some(head)
3787         }
3788     }
3789
3790     #[inline]
3791     fn size_hint(&self) -> (usize, Option<usize>) {
3792         let n = self.v.len() / self.chunk_size;
3793         (n, Some(n))
3794     }
3795
3796     #[inline]
3797     fn count(self) -> usize {
3798         self.len()
3799     }
3800
3801     #[inline]
3802     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
3803         let (start, overflow) = n.overflowing_mul(self.chunk_size);
3804         if start >= self.v.len() || overflow {
3805             self.v = &mut [];
3806             None
3807         } else {
3808             let tmp = mem::replace(&mut self.v, &mut []);
3809             let (_, snd) = tmp.split_at_mut(start);
3810             self.v = snd;
3811             self.next()
3812         }
3813     }
3814
3815     #[inline]
3816     fn last(mut self) -> Option<Self::Item> {
3817         self.next_back()
3818     }
3819 }
3820
3821 #[unstable(feature = "exact_chunks", issue = "47115")]
3822 impl<'a, T> DoubleEndedIterator for ExactChunksMut<'a, T> {
3823     #[inline]
3824     fn next_back(&mut self) -> Option<&'a mut [T]> {
3825         if self.v.len() < self.chunk_size {
3826             None
3827         } else {
3828             let tmp = mem::replace(&mut self.v, &mut []);
3829             let tmp_len = tmp.len();
3830             let (head, tail) = tmp.split_at_mut(tmp_len - self.chunk_size);
3831             self.v = head;
3832             Some(tail)
3833         }
3834     }
3835 }
3836
3837 #[unstable(feature = "exact_chunks", issue = "47115")]
3838 impl<'a, T> ExactSizeIterator for ExactChunksMut<'a, T> {
3839     fn is_empty(&self) -> bool {
3840         self.v.is_empty()
3841     }
3842 }
3843
3844 #[unstable(feature = "trusted_len", issue = "37572")]
3845 unsafe impl<'a, T> TrustedLen for ExactChunksMut<'a, T> {}
3846
3847 #[unstable(feature = "exact_chunks", issue = "47115")]
3848 impl<'a, T> FusedIterator for ExactChunksMut<'a, T> {}
3849
3850 #[doc(hidden)]
3851 unsafe impl<'a, T> TrustedRandomAccess for ExactChunksMut<'a, T> {
3852     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
3853         let start = i * self.chunk_size;
3854         from_raw_parts_mut(self.v.as_mut_ptr().offset(start as isize), self.chunk_size)
3855     }
3856     fn may_have_side_effect() -> bool { false }
3857 }
3858
3859 //
3860 // Free functions
3861 //
3862
3863 /// Forms a slice from a pointer and a length.
3864 ///
3865 /// The `len` argument is the number of **elements**, not the number of bytes.
3866 ///
3867 /// # Safety
3868 ///
3869 /// This function is unsafe as there is no guarantee that the given pointer is
3870 /// valid for `len` elements, nor whether the lifetime inferred is a suitable
3871 /// lifetime for the returned slice.
3872 ///
3873 /// `data` must be non-null and aligned, even for zero-length slices. One
3874 /// reason for this is that enum layout optimizations may rely on references
3875 /// (including slices of any length) being aligned and non-null to distinguish
3876 /// them from other data. You can obtain a pointer that is usable as `data`
3877 /// for zero-length slices using [`NonNull::dangling()`].
3878 ///
3879 /// # Caveat
3880 ///
3881 /// The lifetime for the returned slice is inferred from its usage. To
3882 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
3883 /// source lifetime is safe in the context, such as by providing a helper
3884 /// function taking the lifetime of a host value for the slice, or by explicit
3885 /// annotation.
3886 ///
3887 /// # Examples
3888 ///
3889 /// ```
3890 /// use std::slice;
3891 ///
3892 /// // manifest a slice out of thin air!
3893 /// let ptr = 0x1234 as *const usize;
3894 /// let amt = 10;
3895 /// unsafe {
3896 ///     let slice = slice::from_raw_parts(ptr, amt);
3897 /// }
3898 /// ```
3899 ///
3900 /// [`NonNull::dangling()`]: ../../std/ptr/struct.NonNull.html#method.dangling
3901 #[inline]
3902 #[stable(feature = "rust1", since = "1.0.0")]
3903 pub unsafe fn from_raw_parts<'a, T>(data: *const T, len: usize) -> &'a [T] {
3904     Repr { raw: FatPtr { data, len } }.rust
3905 }
3906
3907 /// Performs the same functionality as `from_raw_parts`, except that a mutable
3908 /// slice is returned.
3909 ///
3910 /// This function is unsafe for the same reasons as `from_raw_parts`, as well
3911 /// as not being able to provide a non-aliasing guarantee of the returned
3912 /// mutable slice. `data` must be non-null and aligned even for zero-length
3913 /// slices as with `from_raw_parts`.
3914 #[inline]
3915 #[stable(feature = "rust1", since = "1.0.0")]
3916 pub unsafe fn from_raw_parts_mut<'a, T>(data: *mut T, len: usize) -> &'a mut [T] {
3917     Repr { raw: FatPtr { data, len} }.rust_mut
3918 }
3919
3920 /// Converts a reference to T into a slice of length 1 (without copying).
3921 #[stable(feature = "from_ref", since = "1.28.0")]
3922 pub fn from_ref<T>(s: &T) -> &[T] {
3923     unsafe {
3924         from_raw_parts(s, 1)
3925     }
3926 }
3927
3928 /// Converts a reference to T into a slice of length 1 (without copying).
3929 #[stable(feature = "from_ref", since = "1.28.0")]
3930 pub fn from_mut<T>(s: &mut T) -> &mut [T] {
3931     unsafe {
3932         from_raw_parts_mut(s, 1)
3933     }
3934 }
3935
3936 // This function is public only because there is no other way to unit test heapsort.
3937 #[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "0")]
3938 #[doc(hidden)]
3939 pub fn heapsort<T, F>(v: &mut [T], mut is_less: F)
3940     where F: FnMut(&T, &T) -> bool
3941 {
3942     sort::heapsort(v, &mut is_less);
3943 }
3944
3945 //
3946 // Comparison traits
3947 //
3948
3949 extern {
3950     /// Calls implementation provided memcmp.
3951     ///
3952     /// Interprets the data as u8.
3953     ///
3954     /// Returns 0 for equal, < 0 for less than and > 0 for greater
3955     /// than.
3956     // FIXME(#32610): Return type should be c_int
3957     fn memcmp(s1: *const u8, s2: *const u8, n: usize) -> i32;
3958 }
3959
3960 #[stable(feature = "rust1", since = "1.0.0")]
3961 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
3962     fn eq(&self, other: &[B]) -> bool {
3963         SlicePartialEq::equal(self, other)
3964     }
3965
3966     fn ne(&self, other: &[B]) -> bool {
3967         SlicePartialEq::not_equal(self, other)
3968     }
3969 }
3970
3971 #[stable(feature = "rust1", since = "1.0.0")]
3972 impl<T: Eq> Eq for [T] {}
3973
3974 /// Implements comparison of vectors lexicographically.
3975 #[stable(feature = "rust1", since = "1.0.0")]
3976 impl<T: Ord> Ord for [T] {
3977     fn cmp(&self, other: &[T]) -> Ordering {
3978         SliceOrd::compare(self, other)
3979     }
3980 }
3981
3982 /// Implements comparison of vectors lexicographically.
3983 #[stable(feature = "rust1", since = "1.0.0")]
3984 impl<T: PartialOrd> PartialOrd for [T] {
3985     fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
3986         SlicePartialOrd::partial_compare(self, other)
3987     }
3988 }
3989
3990 #[doc(hidden)]
3991 // intermediate trait for specialization of slice's PartialEq
3992 trait SlicePartialEq<B> {
3993     fn equal(&self, other: &[B]) -> bool;
3994
3995     fn not_equal(&self, other: &[B]) -> bool { !self.equal(other) }
3996 }
3997
3998 // Generic slice equality
3999 impl<A, B> SlicePartialEq<B> for [A]
4000     where A: PartialEq<B>
4001 {
4002     default fn equal(&self, other: &[B]) -> bool {
4003         if self.len() != other.len() {
4004             return false;
4005         }
4006
4007         for i in 0..self.len() {
4008             if !self[i].eq(&other[i]) {
4009                 return false;
4010             }
4011         }
4012
4013         true
4014     }
4015 }
4016
4017 // Use memcmp for bytewise equality when the types allow
4018 impl<A> SlicePartialEq<A> for [A]
4019     where A: PartialEq<A> + BytewiseEquality
4020 {
4021     fn equal(&self, other: &[A]) -> bool {
4022         if self.len() != other.len() {
4023             return false;
4024         }
4025         if self.as_ptr() == other.as_ptr() {
4026             return true;
4027         }
4028         unsafe {
4029             let size = mem::size_of_val(self);
4030             memcmp(self.as_ptr() as *const u8,
4031                    other.as_ptr() as *const u8, size) == 0
4032         }
4033     }
4034 }
4035
4036 #[doc(hidden)]
4037 // intermediate trait for specialization of slice's PartialOrd
4038 trait SlicePartialOrd<B> {
4039     fn partial_compare(&self, other: &[B]) -> Option<Ordering>;
4040 }
4041
4042 impl<A> SlicePartialOrd<A> for [A]
4043     where A: PartialOrd
4044 {
4045     default fn partial_compare(&self, other: &[A]) -> Option<Ordering> {
4046         let l = cmp::min(self.len(), other.len());
4047
4048         // Slice to the loop iteration range to enable bound check
4049         // elimination in the compiler
4050         let lhs = &self[..l];
4051         let rhs = &other[..l];
4052
4053         for i in 0..l {
4054             match lhs[i].partial_cmp(&rhs[i]) {
4055                 Some(Ordering::Equal) => (),
4056                 non_eq => return non_eq,
4057             }
4058         }
4059
4060         self.len().partial_cmp(&other.len())
4061     }
4062 }
4063
4064 impl<A> SlicePartialOrd<A> for [A]
4065     where A: Ord
4066 {
4067     default fn partial_compare(&self, other: &[A]) -> Option<Ordering> {
4068         Some(SliceOrd::compare(self, other))
4069     }
4070 }
4071
4072 #[doc(hidden)]
4073 // intermediate trait for specialization of slice's Ord
4074 trait SliceOrd<B> {
4075     fn compare(&self, other: &[B]) -> Ordering;
4076 }
4077
4078 impl<A> SliceOrd<A> for [A]
4079     where A: Ord
4080 {
4081     default fn compare(&self, other: &[A]) -> Ordering {
4082         let l = cmp::min(self.len(), other.len());
4083
4084         // Slice to the loop iteration range to enable bound check
4085         // elimination in the compiler
4086         let lhs = &self[..l];
4087         let rhs = &other[..l];
4088
4089         for i in 0..l {
4090             match lhs[i].cmp(&rhs[i]) {
4091                 Ordering::Equal => (),
4092                 non_eq => return non_eq,
4093             }
4094         }
4095
4096         self.len().cmp(&other.len())
4097     }
4098 }
4099
4100 // memcmp compares a sequence of unsigned bytes lexicographically.
4101 // this matches the order we want for [u8], but no others (not even [i8]).
4102 impl SliceOrd<u8> for [u8] {
4103     #[inline]
4104     fn compare(&self, other: &[u8]) -> Ordering {
4105         let order = unsafe {
4106             memcmp(self.as_ptr(), other.as_ptr(),
4107                    cmp::min(self.len(), other.len()))
4108         };
4109         if order == 0 {
4110             self.len().cmp(&other.len())
4111         } else if order < 0 {
4112             Less
4113         } else {
4114             Greater
4115         }
4116     }
4117 }
4118
4119 #[doc(hidden)]
4120 /// Trait implemented for types that can be compared for equality using
4121 /// their bytewise representation
4122 trait BytewiseEquality { }
4123
4124 macro_rules! impl_marker_for {
4125     ($traitname:ident, $($ty:ty)*) => {
4126         $(
4127             impl $traitname for $ty { }
4128         )*
4129     }
4130 }
4131
4132 impl_marker_for!(BytewiseEquality,
4133                  u8 i8 u16 i16 u32 i32 u64 i64 usize isize char bool);
4134
4135 #[doc(hidden)]
4136 unsafe impl<'a, T> TrustedRandomAccess for Iter<'a, T> {
4137     unsafe fn get_unchecked(&mut self, i: usize) -> &'a T {
4138         &*self.ptr.offset(i as isize)
4139     }
4140     fn may_have_side_effect() -> bool { false }
4141 }
4142
4143 #[doc(hidden)]
4144 unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> {
4145     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut T {
4146         &mut *self.ptr.offset(i as isize)
4147     }
4148     fn may_have_side_effect() -> bool { false }
4149 }
4150
4151 trait SliceContains: Sized {
4152     fn slice_contains(&self, x: &[Self]) -> bool;
4153 }
4154
4155 impl<T> SliceContains for T where T: PartialEq {
4156     default fn slice_contains(&self, x: &[Self]) -> bool {
4157         x.iter().any(|y| *y == *self)
4158     }
4159 }
4160
4161 impl SliceContains for u8 {
4162     fn slice_contains(&self, x: &[Self]) -> bool {
4163         memchr::memchr(*self, x).is_some()
4164     }
4165 }
4166
4167 impl SliceContains for i8 {
4168     fn slice_contains(&self, x: &[Self]) -> bool {
4169         let byte = *self as u8;
4170         let bytes: &[u8] = unsafe { from_raw_parts(x.as_ptr() as *const u8, x.len()) };
4171         memchr::memchr(byte, bytes).is_some()
4172     }
4173 }