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