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
 695     /// time. The chunks are slices and do not overlap. If `chunk_size` does
 696     /// not divide the length of the slice, then the last up to `chunk_size-1`
 697     /// elements will be omitted.
 698     ///
 699     /// Due to each chunk having exactly `chunk_size` elements, the compiler
 700     /// can often optimize the resulting code better than in the case of
 701     /// [`chunks`].
 702     ///
 703     /// # Panics
 704     ///
 705     /// Panics if `chunk_size` is 0.
 706     ///
 707     /// # Examples
 708     ///
 709     /// ```
 710     /// #![feature(exact_chunks)]
 711     ///
 712     /// let slice = ['l', 'o', 'r', 'e', 'm'];
 713     /// let mut iter = slice.exact_chunks(2);
 714     /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
 715     /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
 716     /// assert!(iter.next().is_none());
 717     /// ```
 718     ///
 719     /// [`chunks`]: #method.chunks
 720     #[unstable(feature = "exact_chunks", issue = "47115")]
 721     #[inline]
 722     pub fn exact_chunks(&self, chunk_size: usize) -> ExactChunks<T> {
 723         assert!(chunk_size != 0);
 724         let rem = self.len() % chunk_size;
 725         let len = self.len() - rem;
 726         ExactChunks { v: &self[..len], chunk_size: chunk_size}
 727     }
 728
 729     /// Returns an iterator over `chunk_size` elements of the slice at a time.
 730     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does
 731     /// not divide the length of the slice, then the last chunk will not
 732     /// have length `chunk_size`.
 733     ///
 734     /// See [`exact_chunks_mut`] for a variant of this iterator that returns chunks
 735     /// of always exactly `chunk_size` elements.
 736     ///
 737     /// # Panics
 738     ///
 739     /// Panics if `chunk_size` is 0.
 740     ///
 741     /// # Examples
 742     ///
 743     /// ```
 744     /// let v = &mut [0, 0, 0, 0, 0];
 745     /// let mut count = 1;
 746     ///
 747     /// for chunk in v.chunks_mut(2) {
 748     ///     for elem in chunk.iter_mut() {
 749     ///         *elem += count;
 750     ///     }
 751     ///     count += 1;
 752     /// }
 753     /// assert_eq!(v, &[1, 1, 2, 2, 3]);
 754     /// ```
 755     ///
 756     /// [`exact_chunks_mut`]: #method.exact_chunks_mut
 757     #[stable(feature = "rust1", since = "1.0.0")]
 758     #[inline]
 759     pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> {
 760         assert!(chunk_size != 0);
 761         ChunksMut { v: self, 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!(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     #[cfg(not(stage0))]
1712     fn align_to_offsets<U>(&self) -> (usize, usize) {
1713         // What we gonna do about `rest` is figure out what multiple of `U`s we can put in a
1714         // lowest number of `T`s. And how many `T`s we need for each such "multiple".
1715         //
1716         // Consider for example T=u8 U=u16. Then we can put 1 U in 2 Ts. Simple. Now, consider
1717         // for example a case where size_of::<T> = 16, size_of::<U> = 24. We can put 2 Us in
1718         // place of every 3 Ts in the `rest` slice. A bit more complicated.
1719         //
1720         // Formula to calculate this is:
1721         //
1722         // Us = lcm(size_of::<T>, size_of::<U>) / size_of::<U>
1723         // Ts = lcm(size_of::<T>, size_of::<U>) / size_of::<T>
1724         //
1725         // Expanded and simplified:
1726         //
1727         // Us = size_of::<T> / gcd(size_of::<T>, size_of::<U>)
1728         // Ts = size_of::<U> / gcd(size_of::<T>, size_of::<U>)
1729         //
1730         // Luckily since all this is constant-evaluated... performance here matters not!
1731         #[inline]
1732         fn gcd(a: usize, b: usize) -> usize {
1733             // iterative stein’s algorithm
1734             // We should still make this `const fn` (and revert to recursive algorithm if we do)
1735             // because relying on llvm to consteval all this is… well, it makes me
1736             let (ctz_a, mut ctz_b) = unsafe {
1737                 if a == 0 { return b; }
1738                 if b == 0 { return a; }
1739                 (::intrinsics::cttz_nonzero(a), ::intrinsics::cttz_nonzero(b))
1740             };
1741             let k = ctz_a.min(ctz_b);
1742             let mut a = a >> ctz_a;
1743             let mut b = b;
1744             loop {
1745                 // remove all factors of 2 from b
1746                 b >>= ctz_b;
1747                 if a > b {
1748                     ::mem::swap(&mut a, &mut b);
1749                 }
1750                 b = b - a;
1751                 unsafe {
1752                     if b == 0 {
1753                         break;
1754                     }
1755                     ctz_b = ::intrinsics::cttz_nonzero(b);
1756                 }
1757             }
1758             return a << k;
1759         }
1760         let gcd: usize = gcd(::mem::size_of::<T>(), ::mem::size_of::<U>());
1761         let ts: usize = ::mem::size_of::<U>() / gcd;
1762         let us: usize = ::mem::size_of::<T>() / gcd;
1763
1764         // Armed with this knowledge, we can find how many `U`s we can fit!
1765         let us_len = self.len() / ts * us;
1766         // And how many `T`s will be in the trailing slice!
1767         let ts_len = self.len() % ts;
1768         return (us_len, ts_len);
1769     }
1770
1771     /// Transmute the slice to a slice of another type, ensuring aligment of the types is
1772     /// maintained.
1773     ///
1774     /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
1775     /// slice of a new type, and the suffix slice. The middle slice will have the greatest length
1776     /// possible for a given type and input slice.
1777     ///
1778     /// This method has no purpose when either input element `T` or output element `U` are
1779     /// zero-sized and will return the original slice without splitting anything.
1780     ///
1781     /// # Unsafety
1782     ///
1783     /// This method is essentially a `transmute` with respect to the elements in the returned
1784     /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
1785     ///
1786     /// # Examples
1787     ///
1788     /// Basic usage:
1789     ///
1790     /// ```
1791     /// # #![feature(slice_align_to)]
1792     /// unsafe {
1793     ///     let bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
1794     ///     let (prefix, shorts, suffix) = bytes.align_to::<u16>();
1795     ///     // less_efficient_algorithm_for_bytes(prefix);
1796     ///     // more_efficient_algorithm_for_aligned_shorts(shorts);
1797     ///     // less_efficient_algorithm_for_bytes(suffix);
1798     /// }
1799     /// ```
1800     #[unstable(feature = "slice_align_to", issue = "44488")]
1801     #[cfg(not(stage0))]
1802     pub unsafe fn align_to<U>(&self) -> (&[T], &[U], &[T]) {
1803         // Note that most of this function will be constant-evaluated,
1804         if ::mem::size_of::<U>() == 0 || ::mem::size_of::<T>() == 0 {
1805             // handle ZSTs specially, which is – don't handle them at all.
1806             return (self, &[], &[]);
1807         }
1808
1809         // First, find at what point do we split between the first and 2nd slice. Easy with
1810         // ptr.align_offset.
1811         let ptr = self.as_ptr();
1812         let offset = ::ptr::align_offset(ptr, ::mem::align_of::<U>());
1813         if offset > self.len() {
1814             return (self, &[], &[]);
1815         } else {
1816             let (left, rest) = self.split_at(offset);
1817             let (us_len, ts_len) = rest.align_to_offsets::<U>();
1818             return (left,
1819                     from_raw_parts(rest.as_ptr() as *const U, us_len),
1820                     from_raw_parts(rest.as_ptr().offset((rest.len() - ts_len) as isize), ts_len))
1821         }
1822     }
1823
1824     /// Transmute the slice to a slice of another type, ensuring aligment of the types is
1825     /// maintained.
1826     ///
1827     /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
1828     /// slice of a new type, and the suffix slice. The middle slice will have the greatest length
1829     /// possible for a given type and input slice.
1830     ///
1831     /// This method has no purpose when either input element `T` or output element `U` are
1832     /// zero-sized and will return the original slice without splitting anything.
1833     ///
1834     /// # Unsafety
1835     ///
1836     /// This method is essentially a `transmute` with respect to the elements in the returned
1837     /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
1838     ///
1839     /// # Examples
1840     ///
1841     /// Basic usage:
1842     ///
1843     /// ```
1844     /// # #![feature(slice_align_to)]
1845     /// unsafe {
1846     ///     let mut bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
1847     ///     let (prefix, shorts, suffix) = bytes.align_to_mut::<u16>();
1848     ///     // less_efficient_algorithm_for_bytes(prefix);
1849     ///     // more_efficient_algorithm_for_aligned_shorts(shorts);
1850     ///     // less_efficient_algorithm_for_bytes(suffix);
1851     /// }
1852     /// ```
1853     #[unstable(feature = "slice_align_to", issue = "44488")]
1854     #[cfg(not(stage0))]
1855     pub unsafe fn align_to_mut<U>(&mut self) -> (&mut [T], &mut [U], &mut [T]) {
1856         // Note that most of this function will be constant-evaluated,
1857         if ::mem::size_of::<U>() == 0 || ::mem::size_of::<T>() == 0 {
1858             // handle ZSTs specially, which is – don't handle them at all.
1859             return (self, &mut [], &mut []);
1860         }
1861
1862         // First, find at what point do we split between the first and 2nd slice. Easy with
1863         // ptr.align_offset.
1864         let ptr = self.as_ptr();
1865         let offset = ::ptr::align_offset(ptr, ::mem::align_of::<U>());
1866         if offset > self.len() {
1867             return (self, &mut [], &mut []);
1868         } else {
1869             let (left, rest) = self.split_at_mut(offset);
1870             let (us_len, ts_len) = rest.align_to_offsets::<U>();
1871             let mut_ptr = rest.as_mut_ptr();
1872             return (left,
1873                     from_raw_parts_mut(mut_ptr as *mut U, us_len),
1874                     from_raw_parts_mut(mut_ptr.offset((rest.len() - ts_len) as isize), ts_len))
1875         }
1876     }
1877 }
1878
1879 #[lang = "slice_u8"]
1880 #[cfg(not(test))]
1881 impl [u8] {
1882     /// Checks if all bytes in this slice are within the ASCII range.
1883     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1884     #[inline]
1885     pub fn is_ascii(&self) -> bool {
1886         self.iter().all(|b| b.is_ascii())
1887     }
1888
1889     /// Checks that two slices are an ASCII case-insensitive match.
1890     ///
1891     /// Same as `to_ascii_lowercase(a) == to_ascii_lowercase(b)`,
1892     /// but without allocating and copying temporaries.
1893     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1894     #[inline]
1895     pub fn eq_ignore_ascii_case(&self, other: &[u8]) -> bool {
1896         self.len() == other.len() &&
1897             self.iter().zip(other).all(|(a, b)| {
1898                 a.eq_ignore_ascii_case(b)
1899             })
1900     }
1901
1902     /// Converts this slice to its ASCII upper case equivalent in-place.
1903     ///
1904     /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
1905     /// but non-ASCII letters are unchanged.
1906     ///
1907     /// To return a new uppercased value without modifying the existing one, use
1908     /// [`to_ascii_uppercase`].
1909     ///
1910     /// [`to_ascii_uppercase`]: #method.to_ascii_uppercase
1911     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1912     #[inline]
1913     pub fn make_ascii_uppercase(&mut self) {
1914         for byte in self {
1915             byte.make_ascii_uppercase();
1916         }
1917     }
1918
1919     /// Converts this slice to its ASCII lower case equivalent in-place.
1920     ///
1921     /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
1922     /// but non-ASCII letters are unchanged.
1923     ///
1924     /// To return a new lowercased value without modifying the existing one, use
1925     /// [`to_ascii_lowercase`].
1926     ///
1927     /// [`to_ascii_lowercase`]: #method.to_ascii_lowercase
1928     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
1929     #[inline]
1930     pub fn make_ascii_lowercase(&mut self) {
1931         for byte in self {
1932             byte.make_ascii_lowercase();
1933         }
1934     }
1935
1936 }
1937
1938 #[stable(feature = "rust1", since = "1.0.0")]
1939 #[rustc_on_unimplemented = "slice indices are of type `usize` or ranges of `usize`"]
1940 impl<T, I> ops::Index<I> for [T]
1941     where I: SliceIndex<[T]>
1942 {
1943     type Output = I::Output;
1944
1945     #[inline]
1946     fn index(&self, index: I) -> &I::Output {
1947         index.index(self)
1948     }
1949 }
1950
1951 #[stable(feature = "rust1", since = "1.0.0")]
1952 #[rustc_on_unimplemented = "slice indices are of type `usize` or ranges of `usize`"]
1953 impl<T, I> ops::IndexMut<I> for [T]
1954     where I: SliceIndex<[T]>
1955 {
1956     #[inline]
1957     fn index_mut(&mut self, index: I) -> &mut I::Output {
1958         index.index_mut(self)
1959     }
1960 }
1961
1962 #[inline(never)]
1963 #[cold]
1964 fn slice_index_len_fail(index: usize, len: usize) -> ! {
1965     panic!("index {} out of range for slice of length {}", index, len);
1966 }
1967
1968 #[inline(never)]
1969 #[cold]
1970 fn slice_index_order_fail(index: usize, end: usize) -> ! {
1971     panic!("slice index starts at {} but ends at {}", index, end);
1972 }
1973
1974 #[inline(never)]
1975 #[cold]
1976 fn slice_index_overflow_fail() -> ! {
1977     panic!("attempted to index slice up to maximum usize");
1978 }
1979
1980 mod private_slice_index {
1981     use super::ops;
1982     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1983     pub trait Sealed {}
1984
1985     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1986     impl Sealed for usize {}
1987     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1988     impl Sealed for ops::Range<usize> {}
1989     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1990     impl Sealed for ops::RangeTo<usize> {}
1991     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1992     impl Sealed for ops::RangeFrom<usize> {}
1993     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1994     impl Sealed for ops::RangeFull {}
1995     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1996     impl Sealed for ops::RangeInclusive<usize> {}
1997     #[stable(feature = "slice_get_slice", since = "1.28.0")]
1998     impl Sealed for ops::RangeToInclusive<usize> {}
1999 }
2000
2001 /// A helper trait used for indexing operations.
2002 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2003 #[rustc_on_unimplemented = "slice indices are of type `usize` or ranges of `usize`"]
2004 pub trait SliceIndex<T: ?Sized>: private_slice_index::Sealed {
2005     /// The output type returned by methods.
2006     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2007     type Output: ?Sized;
2008
2009     /// Returns a shared reference to the output at this location, if in
2010     /// bounds.
2011     #[unstable(feature = "slice_index_methods", issue = "0")]
2012     fn get(self, slice: &T) -> Option<&Self::Output>;
2013
2014     /// Returns a mutable reference to the output at this location, if in
2015     /// bounds.
2016     #[unstable(feature = "slice_index_methods", issue = "0")]
2017     fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
2018
2019     /// Returns a shared reference to the output at this location, without
2020     /// performing any bounds checking.
2021     #[unstable(feature = "slice_index_methods", issue = "0")]
2022     unsafe fn get_unchecked(self, slice: &T) -> &Self::Output;
2023
2024     /// Returns a mutable reference to the output at this location, without
2025     /// performing any bounds checking.
2026     #[unstable(feature = "slice_index_methods", issue = "0")]
2027     unsafe fn get_unchecked_mut(self, slice: &mut T) -> &mut Self::Output;
2028
2029     /// Returns a shared reference to the output at this location, panicking
2030     /// if out of bounds.
2031     #[unstable(feature = "slice_index_methods", issue = "0")]
2032     fn index(self, slice: &T) -> &Self::Output;
2033
2034     /// Returns a mutable reference to the output at this location, panicking
2035     /// if out of bounds.
2036     #[unstable(feature = "slice_index_methods", issue = "0")]
2037     fn index_mut(self, slice: &mut T) -> &mut Self::Output;
2038 }
2039
2040 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
2041 impl<T> SliceIndex<[T]> for usize {
2042     type Output = T;
2043
2044     #[inline]
2045     fn get(self, slice: &[T]) -> Option<&T> {
2046         if self < slice.len() {
2047             unsafe {
2048                 Some(self.get_unchecked(slice))
2049             }
2050         } else {
2051             None
2052         }
2053     }
2054
2055     #[inline]
2056     fn get_mut(self, slice: &mut [T]) -> Option<&mut T> {
2057         if self < slice.len() {
2058             unsafe {
2059                 Some(self.get_unchecked_mut(slice))
2060             }
2061         } else {
2062             None
2063         }
2064     }
2065
2066     #[inline]
2067     unsafe fn get_unchecked(self, slice: &[T]) -> &T {
2068         &*slice.as_ptr().offset(self as isize)
2069     }
2070
2071     #[inline]
2072     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut T {
2073         &mut *slice.as_mut_ptr().offset(self as isize)
2074     }
2075
2076     #[inline]
2077     fn index(self, slice: &[T]) -> &T {
2078         // NB: use intrinsic indexing
2079         &(*slice)[self]
2080     }
2081
2082     #[inline]
2083     fn index_mut(self, slice: &mut [T]) -> &mut T {
2084         // NB: use intrinsic indexing
2085         &mut (*slice)[self]
2086     }
2087 }
2088
2089 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
2090 impl<T> SliceIndex<[T]> for  ops::Range<usize> {
2091     type Output = [T];
2092
2093     #[inline]
2094     fn get(self, slice: &[T]) -> Option<&[T]> {
2095         if self.start > self.end || self.end > slice.len() {
2096             None
2097         } else {
2098             unsafe {
2099                 Some(self.get_unchecked(slice))
2100             }
2101         }
2102     }
2103
2104     #[inline]
2105     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2106         if self.start > self.end || self.end > slice.len() {
2107             None
2108         } else {
2109             unsafe {
2110                 Some(self.get_unchecked_mut(slice))
2111             }
2112         }
2113     }
2114
2115     #[inline]
2116     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2117         from_raw_parts(slice.as_ptr().offset(self.start as isize), self.end - self.start)
2118     }
2119
2120     #[inline]
2121     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2122         from_raw_parts_mut(slice.as_mut_ptr().offset(self.start as isize), self.end - self.start)
2123     }
2124
2125     #[inline]
2126     fn index(self, slice: &[T]) -> &[T] {
2127         if self.start > self.end {
2128             slice_index_order_fail(self.start, self.end);
2129         } else if self.end > slice.len() {
2130             slice_index_len_fail(self.end, slice.len());
2131         }
2132         unsafe {
2133             self.get_unchecked(slice)
2134         }
2135     }
2136
2137     #[inline]
2138     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2139         if self.start > self.end {
2140             slice_index_order_fail(self.start, self.end);
2141         } else if self.end > slice.len() {
2142             slice_index_len_fail(self.end, slice.len());
2143         }
2144         unsafe {
2145             self.get_unchecked_mut(slice)
2146         }
2147     }
2148 }
2149
2150 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
2151 impl<T> SliceIndex<[T]> for ops::RangeTo<usize> {
2152     type Output = [T];
2153
2154     #[inline]
2155     fn get(self, slice: &[T]) -> Option<&[T]> {
2156         (0..self.end).get(slice)
2157     }
2158
2159     #[inline]
2160     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2161         (0..self.end).get_mut(slice)
2162     }
2163
2164     #[inline]
2165     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2166         (0..self.end).get_unchecked(slice)
2167     }
2168
2169     #[inline]
2170     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2171         (0..self.end).get_unchecked_mut(slice)
2172     }
2173
2174     #[inline]
2175     fn index(self, slice: &[T]) -> &[T] {
2176         (0..self.end).index(slice)
2177     }
2178
2179     #[inline]
2180     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2181         (0..self.end).index_mut(slice)
2182     }
2183 }
2184
2185 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
2186 impl<T> SliceIndex<[T]> for ops::RangeFrom<usize> {
2187     type Output = [T];
2188
2189     #[inline]
2190     fn get(self, slice: &[T]) -> Option<&[T]> {
2191         (self.start..slice.len()).get(slice)
2192     }
2193
2194     #[inline]
2195     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2196         (self.start..slice.len()).get_mut(slice)
2197     }
2198
2199     #[inline]
2200     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2201         (self.start..slice.len()).get_unchecked(slice)
2202     }
2203
2204     #[inline]
2205     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2206         (self.start..slice.len()).get_unchecked_mut(slice)
2207     }
2208
2209     #[inline]
2210     fn index(self, slice: &[T]) -> &[T] {
2211         (self.start..slice.len()).index(slice)
2212     }
2213
2214     #[inline]
2215     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2216         (self.start..slice.len()).index_mut(slice)
2217     }
2218 }
2219
2220 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
2221 impl<T> SliceIndex<[T]> for ops::RangeFull {
2222     type Output = [T];
2223
2224     #[inline]
2225     fn get(self, slice: &[T]) -> Option<&[T]> {
2226         Some(slice)
2227     }
2228
2229     #[inline]
2230     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2231         Some(slice)
2232     }
2233
2234     #[inline]
2235     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2236         slice
2237     }
2238
2239     #[inline]
2240     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2241         slice
2242     }
2243
2244     #[inline]
2245     fn index(self, slice: &[T]) -> &[T] {
2246         slice
2247     }
2248
2249     #[inline]
2250     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2251         slice
2252     }
2253 }
2254
2255
2256 #[stable(feature = "inclusive_range", since = "1.26.0")]
2257 impl<T> SliceIndex<[T]> for ops::RangeInclusive<usize> {
2258     type Output = [T];
2259
2260     #[inline]
2261     fn get(self, slice: &[T]) -> Option<&[T]> {
2262         if self.end == usize::max_value() { None }
2263         else { (self.start..self.end + 1).get(slice) }
2264     }
2265
2266     #[inline]
2267     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2268         if self.end == usize::max_value() { None }
2269         else { (self.start..self.end + 1).get_mut(slice) }
2270     }
2271
2272     #[inline]
2273     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2274         (self.start..self.end + 1).get_unchecked(slice)
2275     }
2276
2277     #[inline]
2278     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2279         (self.start..self.end + 1).get_unchecked_mut(slice)
2280     }
2281
2282     #[inline]
2283     fn index(self, slice: &[T]) -> &[T] {
2284         if self.end == usize::max_value() { slice_index_overflow_fail(); }
2285         (self.start..self.end + 1).index(slice)
2286     }
2287
2288     #[inline]
2289     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2290         if self.end == usize::max_value() { slice_index_overflow_fail(); }
2291         (self.start..self.end + 1).index_mut(slice)
2292     }
2293 }
2294
2295 #[stable(feature = "inclusive_range", since = "1.26.0")]
2296 impl<T> SliceIndex<[T]> for ops::RangeToInclusive<usize> {
2297     type Output = [T];
2298
2299     #[inline]
2300     fn get(self, slice: &[T]) -> Option<&[T]> {
2301         (0..=self.end).get(slice)
2302     }
2303
2304     #[inline]
2305     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2306         (0..=self.end).get_mut(slice)
2307     }
2308
2309     #[inline]
2310     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2311         (0..=self.end).get_unchecked(slice)
2312     }
2313
2314     #[inline]
2315     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2316         (0..=self.end).get_unchecked_mut(slice)
2317     }
2318
2319     #[inline]
2320     fn index(self, slice: &[T]) -> &[T] {
2321         (0..=self.end).index(slice)
2322     }
2323
2324     #[inline]
2325     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2326         (0..=self.end).index_mut(slice)
2327     }
2328 }
2329
2330 ////////////////////////////////////////////////////////////////////////////////
2331 // Common traits
2332 ////////////////////////////////////////////////////////////////////////////////
2333
2334 #[stable(feature = "rust1", since = "1.0.0")]
2335 impl<'a, T> Default for &'a [T] {
2336     /// Creates an empty slice.
2337     fn default() -> &'a [T] { &[] }
2338 }
2339
2340 #[stable(feature = "mut_slice_default", since = "1.5.0")]
2341 impl<'a, T> Default for &'a mut [T] {
2342     /// Creates a mutable empty slice.
2343     fn default() -> &'a mut [T] { &mut [] }
2344 }
2345
2346 //
2347 // Iterators
2348 //
2349
2350 #[stable(feature = "rust1", since = "1.0.0")]
2351 impl<'a, T> IntoIterator for &'a [T] {
2352     type Item = &'a T;
2353     type IntoIter = Iter<'a, T>;
2354
2355     fn into_iter(self) -> Iter<'a, T> {
2356         self.iter()
2357     }
2358 }
2359
2360 #[stable(feature = "rust1", since = "1.0.0")]
2361 impl<'a, T> IntoIterator for &'a mut [T] {
2362     type Item = &'a mut T;
2363     type IntoIter = IterMut<'a, T>;
2364
2365     fn into_iter(self) -> IterMut<'a, T> {
2366         self.iter_mut()
2367     }
2368 }
2369
2370 #[inline]
2371 fn size_from_ptr<T>(_: *const T) -> usize {
2372     mem::size_of::<T>()
2373 }
2374
2375 // The shared definition of the `Iter` and `IterMut` iterators
2376 macro_rules! iterator {
2377     (struct $name:ident -> $ptr:ty, $elem:ty, $mkref:ident) => {
2378         #[stable(feature = "rust1", since = "1.0.0")]
2379         impl<'a, T> Iterator for $name<'a, T> {
2380             type Item = $elem;
2381
2382             #[inline]
2383             fn next(&mut self) -> Option<$elem> {
2384                 // could be implemented with slices, but this avoids bounds checks
2385                 unsafe {
2386                     if mem::size_of::<T>() != 0 {
2387                         assume(!self.ptr.is_null());
2388                         assume(!self.end.is_null());
2389                     }
2390                     if self.ptr == self.end {
2391                         None
2392                     } else {
2393                         Some($mkref!(self.ptr.post_inc()))
2394                     }
2395                 }
2396             }
2397
2398             #[inline]
2399             fn size_hint(&self) -> (usize, Option<usize>) {
2400                 let exact = unsafe { ptrdistance(self.ptr, self.end) };
2401                 (exact, Some(exact))
2402             }
2403
2404             #[inline]
2405             fn count(self) -> usize {
2406                 self.len()
2407             }
2408
2409             #[inline]
2410             fn nth(&mut self, n: usize) -> Option<$elem> {
2411                 // Call helper method. Can't put the definition here because mut versus const.
2412                 self.iter_nth(n)
2413             }
2414
2415             #[inline]
2416             fn last(mut self) -> Option<$elem> {
2417                 self.next_back()
2418             }
2419
2420             #[inline]
2421             fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R where
2422                 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
2423             {
2424                 // manual unrolling is needed when there are conditional exits from the loop
2425                 let mut accum = init;
2426                 unsafe {
2427                     while ptrdistance(self.ptr, self.end) >= 4 {
2428                         accum = f(accum, $mkref!(self.ptr.post_inc()))?;
2429                         accum = f(accum, $mkref!(self.ptr.post_inc()))?;
2430                         accum = f(accum, $mkref!(self.ptr.post_inc()))?;
2431                         accum = f(accum, $mkref!(self.ptr.post_inc()))?;
2432                     }
2433                     while self.ptr != self.end {
2434                         accum = f(accum, $mkref!(self.ptr.post_inc()))?;
2435                     }
2436                 }
2437                 Try::from_ok(accum)
2438             }
2439
2440             #[inline]
2441             fn fold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc
2442                 where Fold: FnMut(Acc, Self::Item) -> Acc,
2443             {
2444                 // Let LLVM unroll this, rather than using the default
2445                 // impl that would force the manual unrolling above
2446                 let mut accum = init;
2447                 while let Some(x) = self.next() {
2448                     accum = f(accum, x);
2449                 }
2450                 accum
2451             }
2452
2453             #[inline]
2454             #[rustc_inherit_overflow_checks]
2455             fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
2456                 Self: Sized,
2457                 P: FnMut(Self::Item) -> bool,
2458             {
2459                 // The addition might panic on overflow
2460                 // Use the len of the slice to hint optimizer to remove result index bounds check.
2461                 let n = make_slice!(self.ptr, self.end).len();
2462                 self.try_fold(0, move |i, x| {
2463                     if predicate(x) { Err(i) }
2464                     else { Ok(i + 1) }
2465                 }).err()
2466                     .map(|i| {
2467                         unsafe { assume(i < n) };
2468                         i
2469                     })
2470             }
2471
2472             #[inline]
2473             fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
2474                 P: FnMut(Self::Item) -> bool,
2475                 Self: Sized + ExactSizeIterator + DoubleEndedIterator
2476             {
2477                 // No need for an overflow check here, because `ExactSizeIterator`
2478                 // implies that the number of elements fits into a `usize`.
2479                 // Use the len of the slice to hint optimizer to remove result index bounds check.
2480                 let n = make_slice!(self.ptr, self.end).len();
2481                 self.try_rfold(n, move |i, x| {
2482                     let i = i - 1;
2483                     if predicate(x) { Err(i) }
2484                     else { Ok(i) }
2485                 }).err()
2486                     .map(|i| {
2487                         unsafe { assume(i < n) };
2488                         i
2489                     })
2490             }
2491         }
2492
2493         #[stable(feature = "rust1", since = "1.0.0")]
2494         impl<'a, T> DoubleEndedIterator for $name<'a, T> {
2495             #[inline]
2496             fn next_back(&mut self) -> Option<$elem> {
2497                 // could be implemented with slices, but this avoids bounds checks
2498                 unsafe {
2499                     if mem::size_of::<T>() != 0 {
2500                         assume(!self.ptr.is_null());
2501                         assume(!self.end.is_null());
2502                     }
2503                     if self.end == self.ptr {
2504                         None
2505                     } else {
2506                         Some($mkref!(self.end.pre_dec()))
2507                     }
2508                 }
2509             }
2510
2511             #[inline]
2512             fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R where
2513                 Self: Sized, F: FnMut(B, Self::Item) -> R, R: Try<Ok=B>
2514             {
2515                 // manual unrolling is needed when there are conditional exits from the loop
2516                 let mut accum = init;
2517                 unsafe {
2518                     while ptrdistance(self.ptr, self.end) >= 4 {
2519                         accum = f(accum, $mkref!(self.end.pre_dec()))?;
2520                         accum = f(accum, $mkref!(self.end.pre_dec()))?;
2521                         accum = f(accum, $mkref!(self.end.pre_dec()))?;
2522                         accum = f(accum, $mkref!(self.end.pre_dec()))?;
2523                     }
2524                     while self.ptr != self.end {
2525                         accum = f(accum, $mkref!(self.end.pre_dec()))?;
2526                     }
2527                 }
2528                 Try::from_ok(accum)
2529             }
2530
2531             #[inline]
2532             fn rfold<Acc, Fold>(mut self, init: Acc, mut f: Fold) -> Acc
2533                 where Fold: FnMut(Acc, Self::Item) -> Acc,
2534             {
2535                 // Let LLVM unroll this, rather than using the default
2536                 // impl that would force the manual unrolling above
2537                 let mut accum = init;
2538                 while let Some(x) = self.next_back() {
2539                     accum = f(accum, x);
2540                 }
2541                 accum
2542             }
2543         }
2544
2545         #[stable(feature = "fused", since = "1.26.0")]
2546         impl<'a, T> FusedIterator for $name<'a, T> {}
2547
2548         #[unstable(feature = "trusted_len", issue = "37572")]
2549         unsafe impl<'a, T> TrustedLen for $name<'a, T> {}
2550     }
2551 }
2552
2553 macro_rules! make_slice {
2554     ($start: expr, $end: expr) => {{
2555         let start = $start;
2556         let diff = ($end as usize).wrapping_sub(start as usize);
2557         if size_from_ptr(start) == 0 {
2558             // use a non-null pointer value
2559             unsafe { from_raw_parts(1 as *const _, diff) }
2560         } else {
2561             let len = diff / size_from_ptr(start);
2562             unsafe { from_raw_parts(start, len) }
2563         }
2564     }}
2565 }
2566
2567 macro_rules! make_mut_slice {
2568     ($start: expr, $end: expr) => {{
2569         let start = $start;
2570         let diff = ($end as usize).wrapping_sub(start as usize);
2571         if size_from_ptr(start) == 0 {
2572             // use a non-null pointer value
2573             unsafe { from_raw_parts_mut(1 as *mut _, diff) }
2574         } else {
2575             let len = diff / size_from_ptr(start);
2576             unsafe { from_raw_parts_mut(start, len) }
2577         }
2578     }}
2579 }
2580
2581 /// Immutable slice iterator
2582 ///
2583 /// This struct is created by the [`iter`] method on [slices].
2584 ///
2585 /// # Examples
2586 ///
2587 /// Basic usage:
2588 ///
2589 /// ```
2590 /// // First, we declare a type which has `iter` method to get the `Iter` struct (&[usize here]):
2591 /// let slice = &[1, 2, 3];
2592 ///
2593 /// // Then, we iterate over it:
2594 /// for element in slice.iter() {
2595 ///     println!("{}", element);
2596 /// }
2597 /// ```
2598 ///
2599 /// [`iter`]: ../../std/primitive.slice.html#method.iter
2600 /// [slices]: ../../std/primitive.slice.html
2601 #[stable(feature = "rust1", since = "1.0.0")]
2602 pub struct Iter<'a, T: 'a> {
2603     ptr: *const T,
2604     end: *const T,
2605     _marker: marker::PhantomData<&'a T>,
2606 }
2607
2608 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2609 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Iter<'a, T> {
2610     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2611         f.debug_tuple("Iter")
2612             .field(&self.as_slice())
2613             .finish()
2614     }
2615 }
2616
2617 #[stable(feature = "rust1", since = "1.0.0")]
2618 unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}
2619 #[stable(feature = "rust1", since = "1.0.0")]
2620 unsafe impl<'a, T: Sync> Send for Iter<'a, T> {}
2621
2622 impl<'a, T> Iter<'a, T> {
2623     /// View the underlying data as a subslice of the original data.
2624     ///
2625     /// This has the same lifetime as the original slice, and so the
2626     /// iterator can continue to be used while this exists.
2627     ///
2628     /// # Examples
2629     ///
2630     /// Basic usage:
2631     ///
2632     /// ```
2633     /// // First, we declare a type which has the `iter` method to get the `Iter`
2634     /// // struct (&[usize here]):
2635     /// let slice = &[1, 2, 3];
2636     ///
2637     /// // Then, we get the iterator:
2638     /// let mut iter = slice.iter();
2639     /// // So if we print what `as_slice` method returns here, we have "[1, 2, 3]":
2640     /// println!("{:?}", iter.as_slice());
2641     ///
2642     /// // Next, we move to the second element of the slice:
2643     /// iter.next();
2644     /// // Now `as_slice` returns "[2, 3]":
2645     /// println!("{:?}", iter.as_slice());
2646     /// ```
2647     #[stable(feature = "iter_to_slice", since = "1.4.0")]
2648     pub fn as_slice(&self) -> &'a [T] {
2649         make_slice!(self.ptr, self.end)
2650     }
2651
2652     // Helper function for Iter::nth
2653     fn iter_nth(&mut self, n: usize) -> Option<&'a T> {
2654         match self.as_slice().get(n) {
2655             Some(elem_ref) => unsafe {
2656                 self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
2657                 Some(elem_ref)
2658             },
2659             None => {
2660                 self.ptr = self.end;
2661                 None
2662             }
2663         }
2664     }
2665 }
2666
2667 iterator!{struct Iter -> *const T, &'a T, make_ref}
2668
2669 #[stable(feature = "rust1", since = "1.0.0")]
2670 impl<'a, T> ExactSizeIterator for Iter<'a, T> {
2671     fn is_empty(&self) -> bool {
2672         self.ptr == self.end
2673     }
2674 }
2675
2676 #[stable(feature = "rust1", since = "1.0.0")]
2677 impl<'a, T> Clone for Iter<'a, T> {
2678     fn clone(&self) -> Iter<'a, T> { Iter { ptr: self.ptr, end: self.end, _marker: self._marker } }
2679 }
2680
2681 #[stable(feature = "slice_iter_as_ref", since = "1.13.0")]
2682 impl<'a, T> AsRef<[T]> for Iter<'a, T> {
2683     fn as_ref(&self) -> &[T] {
2684         self.as_slice()
2685     }
2686 }
2687
2688 /// Mutable slice iterator.
2689 ///
2690 /// This struct is created by the [`iter_mut`] method on [slices].
2691 ///
2692 /// # Examples
2693 ///
2694 /// Basic usage:
2695 ///
2696 /// ```
2697 /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
2698 /// // struct (&[usize here]):
2699 /// let mut slice = &mut [1, 2, 3];
2700 ///
2701 /// // Then, we iterate over it and increment each element value:
2702 /// for element in slice.iter_mut() {
2703 ///     *element += 1;
2704 /// }
2705 ///
2706 /// // We now have "[2, 3, 4]":
2707 /// println!("{:?}", slice);
2708 /// ```
2709 ///
2710 /// [`iter_mut`]: ../../std/primitive.slice.html#method.iter_mut
2711 /// [slices]: ../../std/primitive.slice.html
2712 #[stable(feature = "rust1", since = "1.0.0")]
2713 pub struct IterMut<'a, T: 'a> {
2714     ptr: *mut T,
2715     end: *mut T,
2716     _marker: marker::PhantomData<&'a mut T>,
2717 }
2718
2719 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2720 impl<'a, T: 'a + fmt::Debug> fmt::Debug for IterMut<'a, T> {
2721     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2722         f.debug_tuple("IterMut")
2723             .field(&make_slice!(self.ptr, self.end))
2724             .finish()
2725     }
2726 }
2727
2728 #[stable(feature = "rust1", since = "1.0.0")]
2729 unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
2730 #[stable(feature = "rust1", since = "1.0.0")]
2731 unsafe impl<'a, T: Send> Send for IterMut<'a, T> {}
2732
2733 impl<'a, T> IterMut<'a, T> {
2734     /// View the underlying data as a subslice of the original data.
2735     ///
2736     /// To avoid creating `&mut` references that alias, this is forced
2737     /// to consume the iterator.
2738     ///
2739     /// # Examples
2740     ///
2741     /// Basic usage:
2742     ///
2743     /// ```
2744     /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
2745     /// // struct (&[usize here]):
2746     /// let mut slice = &mut [1, 2, 3];
2747     ///
2748     /// {
2749     ///     // Then, we get the iterator:
2750     ///     let mut iter = slice.iter_mut();
2751     ///     // We move to next element:
2752     ///     iter.next();
2753     ///     // So if we print what `into_slice` method returns here, we have "[2, 3]":
2754     ///     println!("{:?}", iter.into_slice());
2755     /// }
2756     ///
2757     /// // Now let's modify a value of the slice:
2758     /// {
2759     ///     // First we get back the iterator:
2760     ///     let mut iter = slice.iter_mut();
2761     ///     // We change the value of the first element of the slice returned by the `next` method:
2762     ///     *iter.next().unwrap() += 1;
2763     /// }
2764     /// // Now slice is "[2, 2, 3]":
2765     /// println!("{:?}", slice);
2766     /// ```
2767     #[stable(feature = "iter_to_slice", since = "1.4.0")]
2768     pub fn into_slice(self) -> &'a mut [T] {
2769         make_mut_slice!(self.ptr, self.end)
2770     }
2771
2772     // Helper function for IterMut::nth
2773     fn iter_nth(&mut self, n: usize) -> Option<&'a mut T> {
2774         match make_mut_slice!(self.ptr, self.end).get_mut(n) {
2775             Some(elem_ref) => unsafe {
2776                 self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
2777                 Some(elem_ref)
2778             },
2779             None => {
2780                 self.ptr = self.end;
2781                 None
2782             }
2783         }
2784     }
2785 }
2786
2787 iterator!{struct IterMut -> *mut T, &'a mut T, make_ref_mut}
2788
2789 #[stable(feature = "rust1", since = "1.0.0")]
2790 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {
2791     fn is_empty(&self) -> bool {
2792         self.ptr == self.end
2793     }
2794 }
2795
2796 // Return the number of elements of `T` from `start` to `end`.
2797 // Return the arithmetic difference if `T` is zero size.
2798 #[inline(always)]
2799 unsafe fn ptrdistance<T>(start: *const T, end: *const T) -> usize {
2800     if mem::size_of::<T>() == 0 {
2801         (end as usize).wrapping_sub(start as usize)
2802     } else {
2803         end.offset_from(start) as usize
2804     }
2805 }
2806
2807 // Extension methods for raw pointers, used by the iterators
2808 trait PointerExt : Copy {
2809     unsafe fn slice_offset(self, i: isize) -> Self;
2810
2811     /// Increments `self` by 1, but returns the old value.
2812     #[inline(always)]
2813     unsafe fn post_inc(&mut self) -> Self {
2814         let current = *self;
2815         *self = self.slice_offset(1);
2816         current
2817     }
2818
2819     /// Decrements `self` by 1, and returns the new value.
2820     #[inline(always)]
2821     unsafe fn pre_dec(&mut self) -> Self {
2822         *self = self.slice_offset(-1);
2823         *self
2824     }
2825 }
2826
2827 impl<T> PointerExt for *const T {
2828     #[inline(always)]
2829     unsafe fn slice_offset(self, i: isize) -> Self {
2830         slice_offset!(self, i)
2831     }
2832 }
2833
2834 impl<T> PointerExt for *mut T {
2835     #[inline(always)]
2836     unsafe fn slice_offset(self, i: isize) -> Self {
2837         slice_offset!(self, i)
2838     }
2839 }
2840
2841 /// An internal abstraction over the splitting iterators, so that
2842 /// splitn, splitn_mut etc can be implemented once.
2843 #[doc(hidden)]
2844 trait SplitIter: DoubleEndedIterator {
2845     /// Marks the underlying iterator as complete, extracting the remaining
2846     /// portion of the slice.
2847     fn finish(&mut self) -> Option<Self::Item>;
2848 }
2849
2850 /// An iterator over subslices separated by elements that match a predicate
2851 /// function.
2852 ///
2853 /// This struct is created by the [`split`] method on [slices].
2854 ///
2855 /// [`split`]: ../../std/primitive.slice.html#method.split
2856 /// [slices]: ../../std/primitive.slice.html
2857 #[stable(feature = "rust1", since = "1.0.0")]
2858 pub struct Split<'a, T:'a, P> where P: FnMut(&T) -> bool {
2859     v: &'a [T],
2860     pred: P,
2861     finished: bool
2862 }
2863
2864 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2865 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for Split<'a, T, P> where P: FnMut(&T) -> bool {
2866     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2867         f.debug_struct("Split")
2868             .field("v", &self.v)
2869             .field("finished", &self.finished)
2870             .finish()
2871     }
2872 }
2873
2874 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
2875 #[stable(feature = "rust1", since = "1.0.0")]
2876 impl<'a, T, P> Clone for Split<'a, T, P> where P: Clone + FnMut(&T) -> bool {
2877     fn clone(&self) -> Split<'a, T, P> {
2878         Split {
2879             v: self.v,
2880             pred: self.pred.clone(),
2881             finished: self.finished,
2882         }
2883     }
2884 }
2885
2886 #[stable(feature = "rust1", since = "1.0.0")]
2887 impl<'a, T, P> Iterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
2888     type Item = &'a [T];
2889
2890     #[inline]
2891     fn next(&mut self) -> Option<&'a [T]> {
2892         if self.finished { return None; }
2893
2894         match self.v.iter().position(|x| (self.pred)(x)) {
2895             None => self.finish(),
2896             Some(idx) => {
2897                 let ret = Some(&self.v[..idx]);
2898                 self.v = &self.v[idx + 1..];
2899                 ret
2900             }
2901         }
2902     }
2903
2904     #[inline]
2905     fn size_hint(&self) -> (usize, Option<usize>) {
2906         if self.finished {
2907             (0, Some(0))
2908         } else {
2909             (1, Some(self.v.len() + 1))
2910         }
2911     }
2912 }
2913
2914 #[stable(feature = "rust1", since = "1.0.0")]
2915 impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
2916     #[inline]
2917     fn next_back(&mut self) -> Option<&'a [T]> {
2918         if self.finished { return None; }
2919
2920         match self.v.iter().rposition(|x| (self.pred)(x)) {
2921             None => self.finish(),
2922             Some(idx) => {
2923                 let ret = Some(&self.v[idx + 1..]);
2924                 self.v = &self.v[..idx];
2925                 ret
2926             }
2927         }
2928     }
2929 }
2930
2931 impl<'a, T, P> SplitIter for Split<'a, T, P> where P: FnMut(&T) -> bool {
2932     #[inline]
2933     fn finish(&mut self) -> Option<&'a [T]> {
2934         if self.finished { None } else { self.finished = true; Some(self.v) }
2935     }
2936 }
2937
2938 #[stable(feature = "fused", since = "1.26.0")]
2939 impl<'a, T, P> FusedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool {}
2940
2941 /// An iterator over the subslices of the vector which are separated
2942 /// by elements that match `pred`.
2943 ///
2944 /// This struct is created by the [`split_mut`] method on [slices].
2945 ///
2946 /// [`split_mut`]: ../../std/primitive.slice.html#method.split_mut
2947 /// [slices]: ../../std/primitive.slice.html
2948 #[stable(feature = "rust1", since = "1.0.0")]
2949 pub struct SplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
2950     v: &'a mut [T],
2951     pred: P,
2952     finished: bool
2953 }
2954
2955 #[stable(feature = "core_impl_debug", since = "1.9.0")]
2956 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
2957     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2958         f.debug_struct("SplitMut")
2959             .field("v", &self.v)
2960             .field("finished", &self.finished)
2961             .finish()
2962     }
2963 }
2964
2965 impl<'a, T, P> SplitIter for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
2966     #[inline]
2967     fn finish(&mut self) -> Option<&'a mut [T]> {
2968         if self.finished {
2969             None
2970         } else {
2971             self.finished = true;
2972             Some(mem::replace(&mut self.v, &mut []))
2973         }
2974     }
2975 }
2976
2977 #[stable(feature = "rust1", since = "1.0.0")]
2978 impl<'a, T, P> Iterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
2979     type Item = &'a mut [T];
2980
2981     #[inline]
2982     fn next(&mut self) -> Option<&'a mut [T]> {
2983         if self.finished { return None; }
2984
2985         let idx_opt = { // work around borrowck limitations
2986             let pred = &mut self.pred;
2987             self.v.iter().position(|x| (*pred)(x))
2988         };
2989         match idx_opt {
2990             None => self.finish(),
2991             Some(idx) => {
2992                 let tmp = mem::replace(&mut self.v, &mut []);
2993                 let (head, tail) = tmp.split_at_mut(idx);
2994                 self.v = &mut tail[1..];
2995                 Some(head)
2996             }
2997         }
2998     }
2999
3000     #[inline]
3001     fn size_hint(&self) -> (usize, Option<usize>) {
3002         if self.finished {
3003             (0, Some(0))
3004         } else {
3005             // if the predicate doesn't match anything, we yield one slice
3006             // if it matches every element, we yield len+1 empty slices.
3007             (1, Some(self.v.len() + 1))
3008         }
3009     }
3010 }
3011
3012 #[stable(feature = "rust1", since = "1.0.0")]
3013 impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P> where
3014     P: FnMut(&T) -> bool,
3015 {
3016     #[inline]
3017     fn next_back(&mut self) -> Option<&'a mut [T]> {
3018         if self.finished { return None; }
3019
3020         let idx_opt = { // work around borrowck limitations
3021             let pred = &mut self.pred;
3022             self.v.iter().rposition(|x| (*pred)(x))
3023         };
3024         match idx_opt {
3025             None => self.finish(),
3026             Some(idx) => {
3027                 let tmp = mem::replace(&mut self.v, &mut []);
3028                 let (head, tail) = tmp.split_at_mut(idx);
3029                 self.v = head;
3030                 Some(&mut tail[1..])
3031             }
3032         }
3033     }
3034 }
3035
3036 #[stable(feature = "fused", since = "1.26.0")]
3037 impl<'a, T, P> FusedIterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {}
3038
3039 /// An iterator over subslices separated by elements that match a predicate
3040 /// function, starting from the end of the slice.
3041 ///
3042 /// This struct is created by the [`rsplit`] method on [slices].
3043 ///
3044 /// [`rsplit`]: ../../std/primitive.slice.html#method.rsplit
3045 /// [slices]: ../../std/primitive.slice.html
3046 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3047 #[derive(Clone)] // Is this correct, or does it incorrectly require `T: Clone`?
3048 pub struct RSplit<'a, T:'a, P> where P: FnMut(&T) -> bool {
3049     inner: Split<'a, T, P>
3050 }
3051
3052 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3053 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3054     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3055         f.debug_struct("RSplit")
3056             .field("v", &self.inner.v)
3057             .field("finished", &self.inner.finished)
3058             .finish()
3059     }
3060 }
3061
3062 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3063 impl<'a, T, P> Iterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3064     type Item = &'a [T];
3065
3066     #[inline]
3067     fn next(&mut self) -> Option<&'a [T]> {
3068         self.inner.next_back()
3069     }
3070
3071     #[inline]
3072     fn size_hint(&self) -> (usize, Option<usize>) {
3073         self.inner.size_hint()
3074     }
3075 }
3076
3077 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3078 impl<'a, T, P> DoubleEndedIterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3079     #[inline]
3080     fn next_back(&mut self) -> Option<&'a [T]> {
3081         self.inner.next()
3082     }
3083 }
3084
3085 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3086 impl<'a, T, P> SplitIter for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
3087     #[inline]
3088     fn finish(&mut self) -> Option<&'a [T]> {
3089         self.inner.finish()
3090     }
3091 }
3092
3093 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3094 impl<'a, T, P> FusedIterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {}
3095
3096 /// An iterator over the subslices of the vector which are separated
3097 /// by elements that match `pred`, starting from the end of the slice.
3098 ///
3099 /// This struct is created by the [`rsplit_mut`] method on [slices].
3100 ///
3101 /// [`rsplit_mut`]: ../../std/primitive.slice.html#method.rsplit_mut
3102 /// [slices]: ../../std/primitive.slice.html
3103 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3104 pub struct RSplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
3105     inner: SplitMut<'a, T, P>
3106 }
3107
3108 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3109 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
3110     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3111         f.debug_struct("RSplitMut")
3112             .field("v", &self.inner.v)
3113             .field("finished", &self.inner.finished)
3114             .finish()
3115     }
3116 }
3117
3118 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3119 impl<'a, T, P> SplitIter for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
3120     #[inline]
3121     fn finish(&mut self) -> Option<&'a mut [T]> {
3122         self.inner.finish()
3123     }
3124 }
3125
3126 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3127 impl<'a, T, P> Iterator for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
3128     type Item = &'a mut [T];
3129
3130     #[inline]
3131     fn next(&mut self) -> Option<&'a mut [T]> {
3132         self.inner.next_back()
3133     }
3134
3135     #[inline]
3136     fn size_hint(&self) -> (usize, Option<usize>) {
3137         self.inner.size_hint()
3138     }
3139 }
3140
3141 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3142 impl<'a, T, P> DoubleEndedIterator for RSplitMut<'a, T, P> where
3143     P: FnMut(&T) -> bool,
3144 {
3145     #[inline]
3146     fn next_back(&mut self) -> Option<&'a mut [T]> {
3147         self.inner.next()
3148     }
3149 }
3150
3151 #[stable(feature = "slice_rsplit", since = "1.27.0")]
3152 impl<'a, T, P> FusedIterator for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {}
3153
3154 /// An private iterator over subslices separated by elements that
3155 /// match a predicate function, splitting at most a fixed number of
3156 /// times.
3157 #[derive(Debug)]
3158 struct GenericSplitN<I> {
3159     iter: I,
3160     count: usize,
3161 }
3162
3163 impl<T, I: SplitIter<Item=T>> Iterator for GenericSplitN<I> {
3164     type Item = T;
3165
3166     #[inline]
3167     fn next(&mut self) -> Option<T> {
3168         match self.count {
3169             0 => None,
3170             1 => { self.count -= 1; self.iter.finish() }
3171             _ => { self.count -= 1; self.iter.next() }
3172         }
3173     }
3174
3175     #[inline]
3176     fn size_hint(&self) -> (usize, Option<usize>) {
3177         let (lower, upper_opt) = self.iter.size_hint();
3178         (lower, upper_opt.map(|upper| cmp::min(self.count, upper)))
3179     }
3180 }
3181
3182 /// An iterator over subslices separated by elements that match a predicate
3183 /// function, limited to a given number of splits.
3184 ///
3185 /// This struct is created by the [`splitn`] method on [slices].
3186 ///
3187 /// [`splitn`]: ../../std/primitive.slice.html#method.splitn
3188 /// [slices]: ../../std/primitive.slice.html
3189 #[stable(feature = "rust1", since = "1.0.0")]
3190 pub struct SplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3191     inner: GenericSplitN<Split<'a, T, P>>
3192 }
3193
3194 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3195 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitN<'a, T, P> where P: FnMut(&T) -> bool {
3196     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3197         f.debug_struct("SplitN")
3198             .field("inner", &self.inner)
3199             .finish()
3200     }
3201 }
3202
3203 /// An iterator over subslices separated by elements that match a
3204 /// predicate function, limited to a given number of splits, starting
3205 /// from the end of the slice.
3206 ///
3207 /// This struct is created by the [`rsplitn`] method on [slices].
3208 ///
3209 /// [`rsplitn`]: ../../std/primitive.slice.html#method.rsplitn
3210 /// [slices]: ../../std/primitive.slice.html
3211 #[stable(feature = "rust1", since = "1.0.0")]
3212 pub struct RSplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3213     inner: GenericSplitN<RSplit<'a, T, P>>
3214 }
3215
3216 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3217 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitN<'a, T, P> where P: FnMut(&T) -> bool {
3218     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3219         f.debug_struct("RSplitN")
3220             .field("inner", &self.inner)
3221             .finish()
3222     }
3223 }
3224
3225 /// An iterator over subslices separated by elements that match a predicate
3226 /// function, limited to a given number of splits.
3227 ///
3228 /// This struct is created by the [`splitn_mut`] method on [slices].
3229 ///
3230 /// [`splitn_mut`]: ../../std/primitive.slice.html#method.splitn_mut
3231 /// [slices]: ../../std/primitive.slice.html
3232 #[stable(feature = "rust1", since = "1.0.0")]
3233 pub struct SplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3234     inner: GenericSplitN<SplitMut<'a, T, P>>
3235 }
3236
3237 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3238 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitNMut<'a, T, P> where P: FnMut(&T) -> bool {
3239     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3240         f.debug_struct("SplitNMut")
3241             .field("inner", &self.inner)
3242             .finish()
3243     }
3244 }
3245
3246 /// An iterator over subslices separated by elements that match a
3247 /// predicate function, limited to a given number of splits, starting
3248 /// from the end of the slice.
3249 ///
3250 /// This struct is created by the [`rsplitn_mut`] method on [slices].
3251 ///
3252 /// [`rsplitn_mut`]: ../../std/primitive.slice.html#method.rsplitn_mut
3253 /// [slices]: ../../std/primitive.slice.html
3254 #[stable(feature = "rust1", since = "1.0.0")]
3255 pub struct RSplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
3256     inner: GenericSplitN<RSplitMut<'a, T, P>>
3257 }
3258
3259 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3260 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitNMut<'a, T, P> where P: FnMut(&T) -> bool {
3261     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
3262         f.debug_struct("RSplitNMut")
3263             .field("inner", &self.inner)
3264             .finish()
3265     }
3266 }
3267
3268 macro_rules! forward_iterator {
3269     ($name:ident: $elem:ident, $iter_of:ty) => {
3270         #[stable(feature = "rust1", since = "1.0.0")]
3271         impl<'a, $elem, P> Iterator for $name<'a, $elem, P> where
3272             P: FnMut(&T) -> bool
3273         {
3274             type Item = $iter_of;
3275
3276             #[inline]
3277             fn next(&mut self) -> Option<$iter_of> {
3278                 self.inner.next()
3279             }
3280
3281             #[inline]
3282             fn size_hint(&self) -> (usize, Option<usize>) {
3283                 self.inner.size_hint()
3284             }
3285         }
3286
3287         #[stable(feature = "fused", since = "1.26.0")]
3288         impl<'a, $elem, P> FusedIterator for $name<'a, $elem, P>
3289             where P: FnMut(&T) -> bool {}
3290     }
3291 }
3292
3293 forward_iterator! { SplitN: T, &'a [T] }
3294 forward_iterator! { RSplitN: T, &'a [T] }
3295 forward_iterator! { SplitNMut: T, &'a mut [T] }
3296 forward_iterator! { RSplitNMut: T, &'a mut [T] }
3297
3298 /// An iterator over overlapping subslices of length `size`.
3299 ///
3300 /// This struct is created by the [`windows`] method on [slices].
3301 ///
3302 /// [`windows`]: ../../std/primitive.slice.html#method.windows
3303 /// [slices]: ../../std/primitive.slice.html
3304 #[derive(Debug)]
3305 #[stable(feature = "rust1", since = "1.0.0")]
3306 pub struct Windows<'a, T:'a> {
3307     v: &'a [T],
3308     size: usize
3309 }
3310
3311 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
3312 #[stable(feature = "rust1", since = "1.0.0")]
3313 impl<'a, T> Clone for Windows<'a, T> {
3314     fn clone(&self) -> Windows<'a, T> {
3315         Windows {
3316             v: self.v,
3317             size: self.size,
3318         }
3319     }
3320 }
3321
3322 #[stable(feature = "rust1", since = "1.0.0")]
3323 impl<'a, T> Iterator for Windows<'a, T> {
3324     type Item = &'a [T];
3325
3326     #[inline]
3327     fn next(&mut self) -> Option<&'a [T]> {
3328         if self.size > self.v.len() {
3329             None
3330         } else {
3331             let ret = Some(&self.v[..self.size]);
3332             self.v = &self.v[1..];
3333             ret
3334         }
3335     }
3336
3337     #[inline]
3338     fn size_hint(&self) -> (usize, Option<usize>) {
3339         if self.size > self.v.len() {
3340             (0, Some(0))
3341         } else {
3342             let size = self.v.len() - self.size + 1;
3343             (size, Some(size))
3344         }
3345     }
3346
3347     #[inline]
3348     fn count(self) -> usize {
3349         self.len()
3350     }
3351
3352     #[inline]
3353     fn nth(&mut self, n: usize) -> Option<Self::Item> {
3354         let (end, overflow) = self.size.overflowing_add(n);
3355         if end > self.v.len() || overflow {
3356             self.v = &[];
3357             None
3358         } else {
3359             let nth = &self.v[n..end];
3360             self.v = &self.v[n+1..];
3361             Some(nth)
3362         }
3363     }
3364
3365     #[inline]
3366     fn last(self) -> Option<Self::Item> {
3367         if self.size > self.v.len() {
3368             None
3369         } else {
3370             let start = self.v.len() - self.size;
3371             Some(&self.v[start..])
3372         }
3373     }
3374 }
3375
3376 #[stable(feature = "rust1", since = "1.0.0")]
3377 impl<'a, T> DoubleEndedIterator for Windows<'a, T> {
3378     #[inline]
3379     fn next_back(&mut self) -> Option<&'a [T]> {
3380         if self.size > self.v.len() {
3381             None
3382         } else {
3383             let ret = Some(&self.v[self.v.len()-self.size..]);
3384             self.v = &self.v[..self.v.len()-1];
3385             ret
3386         }
3387     }
3388 }
3389
3390 #[stable(feature = "rust1", since = "1.0.0")]
3391 impl<'a, T> ExactSizeIterator for Windows<'a, T> {}
3392
3393 #[unstable(feature = "trusted_len", issue = "37572")]
3394 unsafe impl<'a, T> TrustedLen for Windows<'a, T> {}
3395
3396 #[stable(feature = "fused", since = "1.26.0")]
3397 impl<'a, T> FusedIterator for Windows<'a, T> {}
3398
3399 #[doc(hidden)]
3400 unsafe impl<'a, T> TrustedRandomAccess for Windows<'a, T> {
3401     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
3402         from_raw_parts(self.v.as_ptr().offset(i as isize), self.size)
3403     }
3404     fn may_have_side_effect() -> bool { false }
3405 }
3406
3407 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
3408 /// time).
3409 ///
3410 /// When the slice len is not evenly divided by the chunk size, the last slice
3411 /// of the iteration will be the remainder.
3412 ///
3413 /// This struct is created by the [`chunks`] method on [slices].
3414 ///
3415 /// [`chunks`]: ../../std/primitive.slice.html#method.chunks
3416 /// [slices]: ../../std/primitive.slice.html
3417 #[derive(Debug)]
3418 #[stable(feature = "rust1", since = "1.0.0")]
3419 pub struct Chunks<'a, T:'a> {
3420     v: &'a [T],
3421     chunk_size: usize
3422 }
3423
3424 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
3425 #[stable(feature = "rust1", since = "1.0.0")]
3426 impl<'a, T> Clone for Chunks<'a, T> {
3427     fn clone(&self) -> Chunks<'a, T> {
3428         Chunks {
3429             v: self.v,
3430             chunk_size: self.chunk_size,
3431         }
3432     }
3433 }
3434
3435 #[stable(feature = "rust1", since = "1.0.0")]
3436 impl<'a, T> Iterator for Chunks<'a, T> {
3437     type Item = &'a [T];
3438
3439     #[inline]
3440     fn next(&mut self) -> Option<&'a [T]> {
3441         if self.v.is_empty() {
3442             None
3443         } else {
3444             let chunksz = cmp::min(self.v.len(), self.chunk_size);
3445             let (fst, snd) = self.v.split_at(chunksz);
3446             self.v = snd;
3447             Some(fst)
3448         }
3449     }
3450
3451     #[inline]
3452     fn size_hint(&self) -> (usize, Option<usize>) {
3453         if self.v.is_empty() {
3454             (0, Some(0))
3455         } else {
3456             let n = self.v.len() / self.chunk_size;
3457             let rem = self.v.len() % self.chunk_size;
3458             let n = if rem > 0 { n+1 } else { n };
3459             (n, Some(n))
3460         }
3461     }
3462
3463     #[inline]
3464     fn count(self) -> usize {
3465         self.len()
3466     }
3467
3468     #[inline]
3469     fn nth(&mut self, n: usize) -> Option<Self::Item> {
3470         let (start, overflow) = n.overflowing_mul(self.chunk_size);
3471         if start >= self.v.len() || overflow {
3472             self.v = &[];
3473             None
3474         } else {
3475             let end = match start.checked_add(self.chunk_size) {
3476                 Some(sum) => cmp::min(self.v.len(), sum),
3477                 None => self.v.len(),
3478             };
3479             let nth = &self.v[start..end];
3480             self.v = &self.v[end..];
3481             Some(nth)
3482         }
3483     }
3484
3485     #[inline]
3486     fn last(self) -> Option<Self::Item> {
3487         if self.v.is_empty() {
3488             None
3489         } else {
3490             let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
3491             Some(&self.v[start..])
3492         }
3493     }
3494 }
3495
3496 #[stable(feature = "rust1", since = "1.0.0")]
3497 impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
3498     #[inline]
3499     fn next_back(&mut self) -> Option<&'a [T]> {
3500         if self.v.is_empty() {
3501             None
3502         } else {
3503             let remainder = self.v.len() % self.chunk_size;
3504             let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
3505             let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
3506             self.v = fst;
3507             Some(snd)
3508         }
3509     }
3510 }
3511
3512 #[stable(feature = "rust1", since = "1.0.0")]
3513 impl<'a, T> ExactSizeIterator for Chunks<'a, T> {}
3514
3515 #[unstable(feature = "trusted_len", issue = "37572")]
3516 unsafe impl<'a, T> TrustedLen for Chunks<'a, T> {}
3517
3518 #[stable(feature = "fused", since = "1.26.0")]
3519 impl<'a, T> FusedIterator for Chunks<'a, T> {}
3520
3521 #[doc(hidden)]
3522 unsafe impl<'a, T> TrustedRandomAccess for Chunks<'a, T> {
3523     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
3524         let start = i * self.chunk_size;
3525         let end = match start.checked_add(self.chunk_size) {
3526             None => self.v.len(),
3527             Some(end) => cmp::min(end, self.v.len()),
3528         };
3529         from_raw_parts(self.v.as_ptr().offset(start as isize), end - start)
3530     }
3531     fn may_have_side_effect() -> bool { false }
3532 }
3533
3534 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
3535 /// elements at a time). When the slice len is not evenly divided by the chunk
3536 /// size, the last slice of the iteration will be the remainder.
3537 ///
3538 /// This struct is created by the [`chunks_mut`] method on [slices].
3539 ///
3540 /// [`chunks_mut`]: ../../std/primitive.slice.html#method.chunks_mut
3541 /// [slices]: ../../std/primitive.slice.html
3542 #[derive(Debug)]
3543 #[stable(feature = "rust1", since = "1.0.0")]
3544 pub struct ChunksMut<'a, T:'a> {
3545     v: &'a mut [T],
3546     chunk_size: usize
3547 }
3548
3549 #[stable(feature = "rust1", since = "1.0.0")]
3550 impl<'a, T> Iterator for ChunksMut<'a, T> {
3551     type Item = &'a mut [T];
3552
3553     #[inline]
3554     fn next(&mut self) -> Option<&'a mut [T]> {
3555         if self.v.is_empty() {
3556             None
3557         } else {
3558             let sz = cmp::min(self.v.len(), self.chunk_size);
3559             let tmp = mem::replace(&mut self.v, &mut []);
3560             let (head, tail) = tmp.split_at_mut(sz);
3561             self.v = tail;
3562             Some(head)
3563         }
3564     }
3565
3566     #[inline]
3567     fn size_hint(&self) -> (usize, Option<usize>) {
3568         if self.v.is_empty() {
3569             (0, Some(0))
3570         } else {
3571             let n = self.v.len() / self.chunk_size;
3572             let rem = self.v.len() % self.chunk_size;
3573             let n = if rem > 0 { n + 1 } else { n };
3574             (n, Some(n))
3575         }
3576     }
3577
3578     #[inline]
3579     fn count(self) -> usize {
3580         self.len()
3581     }
3582
3583     #[inline]
3584     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
3585         let (start, overflow) = n.overflowing_mul(self.chunk_size);
3586         if start >= self.v.len() || overflow {
3587             self.v = &mut [];
3588             None
3589         } else {
3590             let end = match start.checked_add(self.chunk_size) {
3591                 Some(sum) => cmp::min(self.v.len(), sum),
3592                 None => self.v.len(),
3593             };
3594             let tmp = mem::replace(&mut self.v, &mut []);
3595             let (head, tail) = tmp.split_at_mut(end);
3596             let (_, nth) =  head.split_at_mut(start);
3597             self.v = tail;
3598             Some(nth)
3599         }
3600     }
3601
3602     #[inline]
3603     fn last(self) -> Option<Self::Item> {
3604         if self.v.is_empty() {
3605             None
3606         } else {
3607             let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
3608             Some(&mut self.v[start..])
3609         }
3610     }
3611 }
3612
3613 #[stable(feature = "rust1", since = "1.0.0")]
3614 impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
3615     #[inline]
3616     fn next_back(&mut self) -> Option<&'a mut [T]> {
3617         if self.v.is_empty() {
3618             None
3619         } else {
3620             let remainder = self.v.len() % self.chunk_size;
3621             let sz = if remainder != 0 { remainder } else { self.chunk_size };
3622             let tmp = mem::replace(&mut self.v, &mut []);
3623             let tmp_len = tmp.len();
3624             let (head, tail) = tmp.split_at_mut(tmp_len - sz);
3625             self.v = head;
3626             Some(tail)
3627         }
3628     }
3629 }
3630
3631 #[stable(feature = "rust1", since = "1.0.0")]
3632 impl<'a, T> ExactSizeIterator for ChunksMut<'a, T> {}
3633
3634 #[unstable(feature = "trusted_len", issue = "37572")]
3635 unsafe impl<'a, T> TrustedLen for ChunksMut<'a, T> {}
3636
3637 #[stable(feature = "fused", since = "1.26.0")]
3638 impl<'a, T> FusedIterator for ChunksMut<'a, T> {}
3639
3640 #[doc(hidden)]
3641 unsafe impl<'a, T> TrustedRandomAccess for ChunksMut<'a, T> {
3642     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
3643         let start = i * self.chunk_size;
3644         let end = match start.checked_add(self.chunk_size) {
3645             None => self.v.len(),
3646             Some(end) => cmp::min(end, self.v.len()),
3647         };
3648         from_raw_parts_mut(self.v.as_mut_ptr().offset(start as isize), end - start)
3649     }
3650     fn may_have_side_effect() -> bool { false }
3651 }
3652
3653 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
3654 /// time).
3655 ///
3656 /// When the slice len is not evenly divided by the chunk size, the last
3657 /// up to `chunk_size-1` elements will be omitted.
3658 ///
3659 /// This struct is created by the [`exact_chunks`] method on [slices].
3660 ///
3661 /// [`exact_chunks`]: ../../std/primitive.slice.html#method.exact_chunks
3662 /// [slices]: ../../std/primitive.slice.html
3663 #[derive(Debug)]
3664 #[unstable(feature = "exact_chunks", issue = "47115")]
3665 pub struct ExactChunks<'a, T:'a> {
3666     v: &'a [T],
3667     chunk_size: usize
3668 }
3669
3670 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
3671 #[unstable(feature = "exact_chunks", issue = "47115")]
3672 impl<'a, T> Clone for ExactChunks<'a, T> {
3673     fn clone(&self) -> ExactChunks<'a, T> {
3674         ExactChunks {
3675             v: self.v,
3676             chunk_size: self.chunk_size,
3677         }
3678     }
3679 }
3680
3681 #[unstable(feature = "exact_chunks", issue = "47115")]
3682 impl<'a, T> Iterator for ExactChunks<'a, T> {
3683     type Item = &'a [T];
3684
3685     #[inline]
3686     fn next(&mut self) -> Option<&'a [T]> {
3687         if self.v.len() < self.chunk_size {
3688             None
3689         } else {
3690             let (fst, snd) = self.v.split_at(self.chunk_size);
3691             self.v = snd;
3692             Some(fst)
3693         }
3694     }
3695
3696     #[inline]
3697     fn size_hint(&self) -> (usize, Option<usize>) {
3698         let n = self.v.len() / self.chunk_size;
3699         (n, Some(n))
3700     }
3701
3702     #[inline]
3703     fn count(self) -> usize {
3704         self.len()
3705     }
3706
3707     #[inline]
3708     fn nth(&mut self, n: usize) -> Option<Self::Item> {
3709         let (start, overflow) = n.overflowing_mul(self.chunk_size);
3710         if start >= self.v.len() || overflow {
3711             self.v = &[];
3712             None
3713         } else {
3714             let (_, snd) = self.v.split_at(start);
3715             self.v = snd;
3716             self.next()
3717         }
3718     }
3719
3720     #[inline]
3721     fn last(mut self) -> Option<Self::Item> {
3722         self.next_back()
3723     }
3724 }
3725
3726 #[unstable(feature = "exact_chunks", issue = "47115")]
3727 impl<'a, T> DoubleEndedIterator for ExactChunks<'a, T> {
3728     #[inline]
3729     fn next_back(&mut self) -> Option<&'a [T]> {
3730         if self.v.len() < self.chunk_size {
3731             None
3732         } else {
3733             let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
3734             self.v = fst;
3735             Some(snd)
3736         }
3737     }
3738 }
3739
3740 #[unstable(feature = "exact_chunks", issue = "47115")]
3741 impl<'a, T> ExactSizeIterator for ExactChunks<'a, T> {
3742     fn is_empty(&self) -> bool {
3743         self.v.is_empty()
3744     }
3745 }
3746
3747 #[unstable(feature = "trusted_len", issue = "37572")]
3748 unsafe impl<'a, T> TrustedLen for ExactChunks<'a, T> {}
3749
3750 #[unstable(feature = "exact_chunks", issue = "47115")]
3751 impl<'a, T> FusedIterator for ExactChunks<'a, T> {}
3752
3753 #[doc(hidden)]
3754 unsafe impl<'a, T> TrustedRandomAccess for ExactChunks<'a, T> {
3755     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
3756         let start = i * self.chunk_size;
3757         from_raw_parts(self.v.as_ptr().offset(start as isize), self.chunk_size)
3758     }
3759     fn may_have_side_effect() -> bool { false }
3760 }
3761
3762 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
3763 /// elements at a time). When the slice len is not evenly divided by the chunk
3764 /// size, the last up to `chunk_size-1` elements will be omitted.
3765 ///
3766 /// This struct is created by the [`exact_chunks_mut`] method on [slices].
3767 ///
3768 /// [`exact_chunks_mut`]: ../../std/primitive.slice.html#method.exact_chunks_mut
3769 /// [slices]: ../../std/primitive.slice.html
3770 #[derive(Debug)]
3771 #[unstable(feature = "exact_chunks", issue = "47115")]
3772 pub struct ExactChunksMut<'a, T:'a> {
3773     v: &'a mut [T],
3774     chunk_size: usize
3775 }
3776
3777 #[unstable(feature = "exact_chunks", issue = "47115")]
3778 impl<'a, T> Iterator for ExactChunksMut<'a, T> {
3779     type Item = &'a mut [T];
3780
3781     #[inline]
3782     fn next(&mut self) -> Option<&'a mut [T]> {
3783         if self.v.len() < self.chunk_size {
3784             None
3785         } else {
3786             let tmp = mem::replace(&mut self.v, &mut []);
3787             let (head, tail) = tmp.split_at_mut(self.chunk_size);
3788             self.v = tail;
3789             Some(head)
3790         }
3791     }
3792
3793     #[inline]
3794     fn size_hint(&self) -> (usize, Option<usize>) {
3795         let n = self.v.len() / self.chunk_size;
3796         (n, Some(n))
3797     }
3798
3799     #[inline]
3800     fn count(self) -> usize {
3801         self.len()
3802     }
3803
3804     #[inline]
3805     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
3806         let (start, overflow) = n.overflowing_mul(self.chunk_size);
3807         if start >= self.v.len() || overflow {
3808             self.v = &mut [];
3809             None
3810         } else {
3811             let tmp = mem::replace(&mut self.v, &mut []);
3812             let (_, snd) = tmp.split_at_mut(start);
3813             self.v = snd;
3814             self.next()
3815         }
3816     }
3817
3818     #[inline]
3819     fn last(mut self) -> Option<Self::Item> {
3820         self.next_back()
3821     }
3822 }
3823
3824 #[unstable(feature = "exact_chunks", issue = "47115")]
3825 impl<'a, T> DoubleEndedIterator for ExactChunksMut<'a, T> {
3826     #[inline]
3827     fn next_back(&mut self) -> Option<&'a mut [T]> {
3828         if self.v.len() < self.chunk_size {
3829             None
3830         } else {
3831             let tmp = mem::replace(&mut self.v, &mut []);
3832             let tmp_len = tmp.len();
3833             let (head, tail) = tmp.split_at_mut(tmp_len - self.chunk_size);
3834             self.v = head;
3835             Some(tail)
3836         }
3837     }
3838 }
3839
3840 #[unstable(feature = "exact_chunks", issue = "47115")]
3841 impl<'a, T> ExactSizeIterator for ExactChunksMut<'a, T> {
3842     fn is_empty(&self) -> bool {
3843         self.v.is_empty()
3844     }
3845 }
3846
3847 #[unstable(feature = "trusted_len", issue = "37572")]
3848 unsafe impl<'a, T> TrustedLen for ExactChunksMut<'a, T> {}
3849
3850 #[unstable(feature = "exact_chunks", issue = "47115")]
3851 impl<'a, T> FusedIterator for ExactChunksMut<'a, T> {}
3852
3853 #[doc(hidden)]
3854 unsafe impl<'a, T> TrustedRandomAccess for ExactChunksMut<'a, T> {
3855     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
3856         let start = i * self.chunk_size;
3857         from_raw_parts_mut(self.v.as_mut_ptr().offset(start as isize), self.chunk_size)
3858     }
3859     fn may_have_side_effect() -> bool { false }
3860 }
3861
3862 //
3863 // Free functions
3864 //
3865
3866 /// Forms a slice from a pointer and a length.
3867 ///
3868 /// The `len` argument is the number of **elements**, not the number of bytes.
3869 ///
3870 /// # Safety
3871 ///
3872 /// This function is unsafe as there is no guarantee that the given pointer is
3873 /// valid for `len` elements, nor whether the lifetime inferred is a suitable
3874 /// lifetime for the returned slice.
3875 ///
3876 /// `p` must be non-null and aligned, even for zero-length slices, as is
3877 /// required for all references. However, for zero-length slices, `p` can be
3878 /// a bogus non-dereferencable pointer such as [`NonNull::dangling()`].
3879 ///
3880 /// # Caveat
3881 ///
3882 /// The lifetime for the returned slice is inferred from its usage. To
3883 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
3884 /// source lifetime is safe in the context, such as by providing a helper
3885 /// function taking the lifetime of a host value for the slice, or by explicit
3886 /// annotation.
3887 ///
3888 /// # Examples
3889 ///
3890 /// ```
3891 /// use std::slice;
3892 ///
3893 /// // manifest a slice out of thin air!
3894 /// let ptr = 0x1234 as *const usize;
3895 /// let amt = 10;
3896 /// unsafe {
3897 ///     let slice = slice::from_raw_parts(ptr, amt);
3898 /// }
3899 /// ```
3900 ///
3901 /// [`NonNull::dangling()`]: ../../std/ptr/struct.NonNull.html#method.dangling
3902 #[inline]
3903 #[stable(feature = "rust1", since = "1.0.0")]
3904 pub unsafe fn from_raw_parts<'a, T>(data: *const T, len: usize) -> &'a [T] {
3905     Repr { raw: FatPtr { data, len } }.rust
3906 }
3907
3908 /// Performs the same functionality as `from_raw_parts`, except that a mutable
3909 /// slice is returned.
3910 ///
3911 /// This function is unsafe for the same reasons as `from_raw_parts`, as well
3912 /// as not being able to provide a non-aliasing guarantee of the returned
3913 /// mutable slice. `p` must be non-null and aligned even for zero-length slices as with
3914 /// `from_raw_parts`.
3915 #[inline]
3916 #[stable(feature = "rust1", since = "1.0.0")]
3917 pub unsafe fn from_raw_parts_mut<'a, T>(data: *mut T, len: usize) -> &'a mut [T] {
3918     Repr { raw: FatPtr { data, len} }.rust_mut
3919 }
3920
3921 /// Converts a reference to T into a slice of length 1 (without copying).
3922 #[stable(feature = "from_ref", since = "1.28.0")]
3923 pub fn from_ref<T>(s: &T) -> &[T] {
3924     unsafe {
3925         from_raw_parts(s, 1)
3926     }
3927 }
3928
3929 /// Converts a reference to T into a slice of length 1 (without copying).
3930 #[stable(feature = "from_ref", since = "1.28.0")]
3931 pub fn from_mut<T>(s: &mut T) -> &mut [T] {
3932     unsafe {
3933         from_raw_parts_mut(s, 1)
3934     }
3935 }
3936
3937 // This function is public only because there is no other way to unit test heapsort.
3938 #[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "0")]
3939 #[doc(hidden)]
3940 pub fn heapsort<T, F>(v: &mut [T], mut is_less: F)
3941     where F: FnMut(&T, &T) -> bool
3942 {
3943     sort::heapsort(v, &mut is_less);
3944 }
3945
3946 //
3947 // Comparison traits
3948 //
3949
3950 extern {
3951     /// Calls implementation provided memcmp.
3952     ///
3953     /// Interprets the data as u8.
3954     ///
3955     /// Returns 0 for equal, < 0 for less than and > 0 for greater
3956     /// than.
3957     // FIXME(#32610): Return type should be c_int
3958     fn memcmp(s1: *const u8, s2: *const u8, n: usize) -> i32;
3959 }
3960
3961 #[stable(feature = "rust1", since = "1.0.0")]
3962 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
3963     fn eq(&self, other: &[B]) -> bool {
3964         SlicePartialEq::equal(self, other)
3965     }
3966
3967     fn ne(&self, other: &[B]) -> bool {
3968         SlicePartialEq::not_equal(self, other)
3969     }
3970 }
3971
3972 #[stable(feature = "rust1", since = "1.0.0")]
3973 impl<T: Eq> Eq for [T] {}
3974
3975 /// Implements comparison of vectors lexicographically.
3976 #[stable(feature = "rust1", since = "1.0.0")]
3977 impl<T: Ord> Ord for [T] {
3978     fn cmp(&self, other: &[T]) -> Ordering {
3979         SliceOrd::compare(self, other)
3980     }
3981 }
3982
3983 /// Implements comparison of vectors lexicographically.
3984 #[stable(feature = "rust1", since = "1.0.0")]
3985 impl<T: PartialOrd> PartialOrd for [T] {
3986     fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
3987         SlicePartialOrd::partial_compare(self, other)
3988     }
3989 }
3990
3991 #[doc(hidden)]
3992 // intermediate trait for specialization of slice's PartialEq
3993 trait SlicePartialEq<B> {
3994     fn equal(&self, other: &[B]) -> bool;
3995
3996     fn not_equal(&self, other: &[B]) -> bool { !self.equal(other) }
3997 }
3998
3999 // Generic slice equality
4000 impl<A, B> SlicePartialEq<B> for [A]
4001     where A: PartialEq<B>
4002 {
4003     default fn equal(&self, other: &[B]) -> bool {
4004         if self.len() != other.len() {
4005             return false;
4006         }
4007
4008         for i in 0..self.len() {
4009             if !self[i].eq(&other[i]) {
4010                 return false;
4011             }
4012         }
4013
4014         true
4015     }
4016 }
4017
4018 // Use memcmp for bytewise equality when the types allow
4019 impl<A> SlicePartialEq<A> for [A]
4020     where A: PartialEq<A> + BytewiseEquality
4021 {
4022     fn equal(&self, other: &[A]) -> bool {
4023         if self.len() != other.len() {
4024             return false;
4025         }
4026         if self.as_ptr() == other.as_ptr() {
4027             return true;
4028         }
4029         unsafe {
4030             let size = mem::size_of_val(self);
4031             memcmp(self.as_ptr() as *const u8,
4032                    other.as_ptr() as *const u8, size) == 0
4033         }
4034     }
4035 }
4036
4037 #[doc(hidden)]
4038 // intermediate trait for specialization of slice's PartialOrd
4039 trait SlicePartialOrd<B> {
4040     fn partial_compare(&self, other: &[B]) -> Option<Ordering>;
4041 }
4042
4043 impl<A> SlicePartialOrd<A> for [A]
4044     where A: PartialOrd
4045 {
4046     default fn partial_compare(&self, other: &[A]) -> Option<Ordering> {
4047         let l = cmp::min(self.len(), other.len());
4048
4049         // Slice to the loop iteration range to enable bound check
4050         // elimination in the compiler
4051         let lhs = &self[..l];
4052         let rhs = &other[..l];
4053
4054         for i in 0..l {
4055             match lhs[i].partial_cmp(&rhs[i]) {
4056                 Some(Ordering::Equal) => (),
4057                 non_eq => return non_eq,
4058             }
4059         }
4060
4061         self.len().partial_cmp(&other.len())
4062     }
4063 }
4064
4065 impl<A> SlicePartialOrd<A> for [A]
4066     where A: Ord
4067 {
4068     default fn partial_compare(&self, other: &[A]) -> Option<Ordering> {
4069         Some(SliceOrd::compare(self, other))
4070     }
4071 }
4072
4073 #[doc(hidden)]
4074 // intermediate trait for specialization of slice's Ord
4075 trait SliceOrd<B> {
4076     fn compare(&self, other: &[B]) -> Ordering;
4077 }
4078
4079 impl<A> SliceOrd<A> for [A]
4080     where A: Ord
4081 {
4082     default fn compare(&self, other: &[A]) -> Ordering {
4083         let l = cmp::min(self.len(), other.len());
4084
4085         // Slice to the loop iteration range to enable bound check
4086         // elimination in the compiler
4087         let lhs = &self[..l];
4088         let rhs = &other[..l];
4089
4090         for i in 0..l {
4091             match lhs[i].cmp(&rhs[i]) {
4092                 Ordering::Equal => (),
4093                 non_eq => return non_eq,
4094             }
4095         }
4096
4097         self.len().cmp(&other.len())
4098     }
4099 }
4100
4101 // memcmp compares a sequence of unsigned bytes lexicographically.
4102 // this matches the order we want for [u8], but no others (not even [i8]).
4103 impl SliceOrd<u8> for [u8] {
4104     #[inline]
4105     fn compare(&self, other: &[u8]) -> Ordering {
4106         let order = unsafe {
4107             memcmp(self.as_ptr(), other.as_ptr(),
4108                    cmp::min(self.len(), other.len()))
4109         };
4110         if order == 0 {
4111             self.len().cmp(&other.len())
4112         } else if order < 0 {
4113             Less
4114         } else {
4115             Greater
4116         }
4117     }
4118 }
4119
4120 #[doc(hidden)]
4121 /// Trait implemented for types that can be compared for equality using
4122 /// their bytewise representation
4123 trait BytewiseEquality { }
4124
4125 macro_rules! impl_marker_for {
4126     ($traitname:ident, $($ty:ty)*) => {
4127         $(
4128             impl $traitname for $ty { }
4129         )*
4130     }
4131 }
4132
4133 impl_marker_for!(BytewiseEquality,
4134                  u8 i8 u16 i16 u32 i32 u64 i64 usize isize char bool);
4135
4136 #[doc(hidden)]
4137 unsafe impl<'a, T> TrustedRandomAccess for Iter<'a, T> {
4138     unsafe fn get_unchecked(&mut self, i: usize) -> &'a T {
4139         &*self.ptr.offset(i as isize)
4140     }
4141     fn may_have_side_effect() -> bool { false }
4142 }
4143
4144 #[doc(hidden)]
4145 unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> {
4146     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut T {
4147         &mut *self.ptr.offset(i as isize)
4148     }
4149     fn may_have_side_effect() -> bool { false }
4150 }
4151
4152 trait SliceContains: Sized {
4153     fn slice_contains(&self, x: &[Self]) -> bool;
4154 }
4155
4156 impl<T> SliceContains for T where T: PartialEq {
4157     default fn slice_contains(&self, x: &[Self]) -> bool {
4158         x.iter().any(|y| *y == *self)
4159     }
4160 }
4161
4162 impl SliceContains for u8 {
4163     fn slice_contains(&self, x: &[Self]) -> bool {
4164         memchr::memchr(*self, x).is_some()
4165     }
4166 }
4167
4168 impl SliceContains for i8 {
4169     fn slice_contains(&self, x: &[Self]) -> bool {
4170         let byte = *self as u8;
4171         let bytes: &[u8] = unsafe { from_raw_parts(x.as_ptr() as *const u8, x.len()) };
4172         memchr::memchr(byte, bytes).is_some()
4173     }
4174 }