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