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