src/liballoc/slice.rs

   1 // Copyright 2012-2015 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 //! A dynamically-sized view into a contiguous sequence, `[T]`.
  12 //!
  13 //! Slices are a view into a block of memory represented as a pointer and a
  14 //! length.
  15 //!
  16 //! ```
  17 //! // slicing a Vec
  18 //! let vec = vec![1, 2, 3];
  19 //! let int_slice = &vec[..];
  20 //! // coercing an array to a slice
  21 //! let str_slice: &[&str] = &["one", "two", "three"];
  22 //! ```
  23 //!
  24 //! Slices are either mutable or shared. The shared slice type is `&[T]`,
  25 //! while the mutable slice type is `&mut [T]`, where `T` represents the element
  26 //! type. For example, you can mutate the block of memory that a mutable slice
  27 //! points to:
  28 //!
  29 //! ```
  30 //! let x = &mut [1, 2, 3];
  31 //! x[1] = 7;
  32 //! assert_eq!(x, &[1, 7, 3]);
  33 //! ```
  34 //!
  35 //! Here are some of the things this module contains:
  36 //!
  37 //! ## Structs
  38 //!
  39 //! There are several structs that are useful for slices, such as [`Iter`], which
  40 //! represents iteration over a slice.
  41 //!
  42 //! ## Trait Implementations
  43 //!
  44 //! There are several implementations of common traits for slices. Some examples
  45 //! include:
  46 //!
  47 //! * [`Clone`]
  48 //! * [`Eq`], [`Ord`] - for slices whose element type are [`Eq`] or [`Ord`].
  49 //! * [`Hash`] - for slices whose element type is [`Hash`].
  50 //!
  51 //! ## Iteration
  52 //!
  53 //! The slices implement `IntoIterator`. The iterator yields references to the
  54 //! slice elements.
  55 //!
  56 //! ```
  57 //! let numbers = &[0, 1, 2];
  58 //! for n in numbers {
  59 //!     println!("{} is a number!", n);
  60 //! }
  61 //! ```
  62 //!
  63 //! The mutable slice yields mutable references to the elements:
  64 //!
  65 //! ```
  66 //! let mut scores = [7, 8, 9];
  67 //! for score in &mut scores[..] {
  68 //!     *score += 1;
  69 //! }
  70 //! ```
  71 //!
  72 //! This iterator yields mutable references to the slice's elements, so while
  73 //! the element type of the slice is `i32`, the element type of the iterator is
  74 //! `&mut i32`.
  75 //!
  76 //! * [`.iter`] and [`.iter_mut`] are the explicit methods to return the default
  77 //!   iterators.
  78 //! * Further methods that return iterators are [`.split`], [`.splitn`],
  79 //!   [`.chunks`], [`.windows`] and more.
  80 //!
  81 //! *[See also the slice primitive type](../../std/primitive.slice.html).*
  82 //!
  83 //! [`Clone`]: ../../std/clone/trait.Clone.html
  84 //! [`Eq`]: ../../std/cmp/trait.Eq.html
  85 //! [`Ord`]: ../../std/cmp/trait.Ord.html
  86 //! [`Iter`]: struct.Iter.html
  87 //! [`Hash`]: ../../std/hash/trait.Hash.html
  88 //! [`.iter`]: ../../std/primitive.slice.html#method.iter
  89 //! [`.iter_mut`]: ../../std/primitive.slice.html#method.iter_mut
  90 //! [`.split`]: ../../std/primitive.slice.html#method.split
  91 //! [`.splitn`]: ../../std/primitive.slice.html#method.splitn
  92 //! [`.chunks`]: ../../std/primitive.slice.html#method.chunks
  93 //! [`.windows`]: ../../std/primitive.slice.html#method.windows
  94 #![stable(feature = "rust1", since = "1.0.0")]
  95
  96 // Many of the usings in this module are only used in the test configuration.
  97 // It's cleaner to just turn off the unused_imports warning than to fix them.
  98 #![cfg_attr(test, allow(unused_imports, dead_code))]
  99
 100 use core::cmp::Ordering::{self, Less};
 101 use core::mem::size_of;
 102 use core::mem;
 103 use core::ptr;
 104 use core::slice as core_slice;
 105
 106 use borrow::{Borrow, BorrowMut, ToOwned};
 107 use boxed::Box;
 108 use vec::Vec;
 109
 110 #[stable(feature = "rust1", since = "1.0.0")]
 111 pub use core::slice::{Chunks, Windows};
 112 #[stable(feature = "rust1", since = "1.0.0")]
 113 pub use core::slice::{Iter, IterMut};
 114 #[stable(feature = "rust1", since = "1.0.0")]
 115 pub use core::slice::{SplitMut, ChunksMut, Split};
 116 #[stable(feature = "rust1", since = "1.0.0")]
 117 pub use core::slice::{SplitN, RSplitN, SplitNMut, RSplitNMut};
 118 #[unstable(feature = "slice_rsplit", issue = "41020")]
 119 pub use core::slice::{RSplit, RSplitMut};
 120 #[stable(feature = "rust1", since = "1.0.0")]
 121 pub use core::slice::{from_raw_parts, from_raw_parts_mut};
 122 #[unstable(feature = "slice_get_slice", issue = "35729")]
 123 pub use core::slice::SliceIndex;
 124
 125 ////////////////////////////////////////////////////////////////////////////////
 126 // Basic slice extension methods
 127 ////////////////////////////////////////////////////////////////////////////////
 128
 129 // HACK(japaric) needed for the implementation of `vec!` macro during testing
 130 // NB see the hack module in this file for more details
 131 #[cfg(test)]
 132 pub use self::hack::into_vec;
 133
 134 // HACK(japaric) needed for the implementation of `Vec::clone` during testing
 135 // NB see the hack module in this file for more details
 136 #[cfg(test)]
 137 pub use self::hack::to_vec;
 138
 139 // HACK(japaric): With cfg(test) `impl [T]` is not available, these three
 140 // functions are actually methods that are in `impl [T]` but not in
 141 // `core::slice::SliceExt` - we need to supply these functions for the
 142 // `test_permutations` test
 143 mod hack {
 144     use boxed::Box;
 145     use core::mem;
 146
 147     #[cfg(test)]
 148     use string::ToString;
 149     use vec::Vec;
 150
 151     pub fn into_vec<T>(mut b: Box<[T]>) -> Vec<T> {
 152         unsafe {
 153             let xs = Vec::from_raw_parts(b.as_mut_ptr(), b.len(), b.len());
 154             mem::forget(b);
 155             xs
 156         }
 157     }
 158
 159     #[inline]
 160     pub fn to_vec<T>(s: &[T]) -> Vec<T>
 161         where T: Clone
 162     {
 163         let mut vector = Vec::with_capacity(s.len());
 164         vector.extend_from_slice(s);
 165         vector
 166     }
 167 }
 168
 169 #[lang = "slice"]
 170 #[cfg(not(test))]
 171 impl<T> [T] {
 172     /// Returns the number of elements in the slice.
 173     ///
 174     /// # Examples
 175     ///
 176     /// ```
 177     /// let a = [1, 2, 3];
 178     /// assert_eq!(a.len(), 3);
 179     /// ```
 180     #[stable(feature = "rust1", since = "1.0.0")]
 181     #[inline]
 182     pub fn len(&self) -> usize {
 183         core_slice::SliceExt::len(self)
 184     }
 185
 186     /// Returns `true` if the slice has a length of 0.
 187     ///
 188     /// # Examples
 189     ///
 190     /// ```
 191     /// let a = [1, 2, 3];
 192     /// assert!(!a.is_empty());
 193     /// ```
 194     #[stable(feature = "rust1", since = "1.0.0")]
 195     #[inline]
 196     pub fn is_empty(&self) -> bool {
 197         core_slice::SliceExt::is_empty(self)
 198     }
 199
 200     /// Returns the first element of the slice, or `None` if it is empty.
 201     ///
 202     /// # Examples
 203     ///
 204     /// ```
 205     /// let v = [10, 40, 30];
 206     /// assert_eq!(Some(&10), v.first());
 207     ///
 208     /// let w: &[i32] = &[];
 209     /// assert_eq!(None, w.first());
 210     /// ```
 211     #[stable(feature = "rust1", since = "1.0.0")]
 212     #[inline]
 213     pub fn first(&self) -> Option<&T> {
 214         core_slice::SliceExt::first(self)
 215     }
 216
 217     /// Returns a mutable pointer to the first element of the slice, or `None` if it is empty.
 218     ///
 219     /// # Examples
 220     ///
 221     /// ```
 222     /// let x = &mut [0, 1, 2];
 223     ///
 224     /// if let Some(first) = x.first_mut() {
 225     ///     *first = 5;
 226     /// }
 227     /// assert_eq!(x, &[5, 1, 2]);
 228     /// ```
 229     #[stable(feature = "rust1", since = "1.0.0")]
 230     #[inline]
 231     pub fn first_mut(&mut self) -> Option<&mut T> {
 232         core_slice::SliceExt::first_mut(self)
 233     }
 234
 235     /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
 236     ///
 237     /// # Examples
 238     ///
 239     /// ```
 240     /// let x = &[0, 1, 2];
 241     ///
 242     /// if let Some((first, elements)) = x.split_first() {
 243     ///     assert_eq!(first, &0);
 244     ///     assert_eq!(elements, &[1, 2]);
 245     /// }
 246     /// ```
 247     #[stable(feature = "slice_splits", since = "1.5.0")]
 248     #[inline]
 249     pub fn split_first(&self) -> Option<(&T, &[T])> {
 250         core_slice::SliceExt::split_first(self)
 251     }
 252
 253     /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
 254     ///
 255     /// # Examples
 256     ///
 257     /// ```
 258     /// let x = &mut [0, 1, 2];
 259     ///
 260     /// if let Some((first, elements)) = x.split_first_mut() {
 261     ///     *first = 3;
 262     ///     elements[0] = 4;
 263     ///     elements[1] = 5;
 264     /// }
 265     /// assert_eq!(x, &[3, 4, 5]);
 266     /// ```
 267     #[stable(feature = "slice_splits", since = "1.5.0")]
 268     #[inline]
 269     pub fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
 270         core_slice::SliceExt::split_first_mut(self)
 271     }
 272
 273     /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
 274     ///
 275     /// # Examples
 276     ///
 277     /// ```
 278     /// let x = &[0, 1, 2];
 279     ///
 280     /// if let Some((last, elements)) = x.split_last() {
 281     ///     assert_eq!(last, &2);
 282     ///     assert_eq!(elements, &[0, 1]);
 283     /// }
 284     /// ```
 285     #[stable(feature = "slice_splits", since = "1.5.0")]
 286     #[inline]
 287     pub fn split_last(&self) -> Option<(&T, &[T])> {
 288         core_slice::SliceExt::split_last(self)
 289
 290     }
 291
 292     /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
 293     ///
 294     /// # Examples
 295     ///
 296     /// ```
 297     /// let x = &mut [0, 1, 2];
 298     ///
 299     /// if let Some((last, elements)) = x.split_last_mut() {
 300     ///     *last = 3;
 301     ///     elements[0] = 4;
 302     ///     elements[1] = 5;
 303     /// }
 304     /// assert_eq!(x, &[4, 5, 3]);
 305     /// ```
 306     #[stable(feature = "slice_splits", since = "1.5.0")]
 307     #[inline]
 308     pub fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
 309         core_slice::SliceExt::split_last_mut(self)
 310     }
 311
 312     /// Returns the last element of the slice, or `None` if it is empty.
 313     ///
 314     /// # Examples
 315     ///
 316     /// ```
 317     /// let v = [10, 40, 30];
 318     /// assert_eq!(Some(&30), v.last());
 319     ///
 320     /// let w: &[i32] = &[];
 321     /// assert_eq!(None, w.last());
 322     /// ```
 323     #[stable(feature = "rust1", since = "1.0.0")]
 324     #[inline]
 325     pub fn last(&self) -> Option<&T> {
 326         core_slice::SliceExt::last(self)
 327     }
 328
 329     /// Returns a mutable pointer to the last item in the slice.
 330     ///
 331     /// # Examples
 332     ///
 333     /// ```
 334     /// let x = &mut [0, 1, 2];
 335     ///
 336     /// if let Some(last) = x.last_mut() {
 337     ///     *last = 10;
 338     /// }
 339     /// assert_eq!(x, &[0, 1, 10]);
 340     /// ```
 341     #[stable(feature = "rust1", since = "1.0.0")]
 342     #[inline]
 343     pub fn last_mut(&mut self) -> Option<&mut T> {
 344         core_slice::SliceExt::last_mut(self)
 345     }
 346
 347     /// Returns a reference to an element or subslice depending on the type of
 348     /// index.
 349     ///
 350     /// - If given a position, returns a reference to the element at that
 351     ///   position or `None` if out of bounds.
 352     /// - If given a range, returns the subslice corresponding to that range,
 353     ///   or `None` if out of bounds.
 354     ///
 355     /// # Examples
 356     ///
 357     /// ```
 358     /// let v = [10, 40, 30];
 359     /// assert_eq!(Some(&40), v.get(1));
 360     /// assert_eq!(Some(&[10, 40][..]), v.get(0..2));
 361     /// assert_eq!(None, v.get(3));
 362     /// assert_eq!(None, v.get(0..4));
 363     /// ```
 364     #[stable(feature = "rust1", since = "1.0.0")]
 365     #[inline]
 366     pub fn get<I>(&self, index: I) -> Option<&I::Output>
 367         where I: SliceIndex<Self>
 368     {
 369         core_slice::SliceExt::get(self, index)
 370     }
 371
 372     /// Returns a mutable reference to an element or subslice depending on the
 373     /// type of index (see [`get`]) or `None` if the index is out of bounds.
 374     ///
 375     /// [`get`]: #method.get
 376     ///
 377     /// # Examples
 378     ///
 379     /// ```
 380     /// let x = &mut [0, 1, 2];
 381     ///
 382     /// if let Some(elem) = x.get_mut(1) {
 383     ///     *elem = 42;
 384     /// }
 385     /// assert_eq!(x, &[0, 42, 2]);
 386     /// ```
 387     #[stable(feature = "rust1", since = "1.0.0")]
 388     #[inline]
 389     pub fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
 390         where I: SliceIndex<Self>
 391     {
 392         core_slice::SliceExt::get_mut(self, index)
 393     }
 394
 395     /// Returns a reference to an element or subslice, without doing bounds
 396     /// checking.
 397     ///
 398     /// This is generally not recommended, use with caution! For a safe
 399     /// alternative see [`get`].
 400     ///
 401     /// [`get`]: #method.get
 402     ///
 403     /// # Examples
 404     ///
 405     /// ```
 406     /// let x = &[1, 2, 4];
 407     ///
 408     /// unsafe {
 409     ///     assert_eq!(x.get_unchecked(1), &2);
 410     /// }
 411     /// ```
 412     #[stable(feature = "rust1", since = "1.0.0")]
 413     #[inline]
 414     pub unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
 415         where I: SliceIndex<Self>
 416     {
 417         core_slice::SliceExt::get_unchecked(self, index)
 418     }
 419
 420     /// Returns a mutable reference to an element or subslice, without doing
 421     /// bounds checking.
 422     ///
 423     /// This is generally not recommended, use with caution! For a safe
 424     /// alternative see [`get_mut`].
 425     ///
 426     /// [`get_mut`]: #method.get_mut
 427     ///
 428     /// # Examples
 429     ///
 430     /// ```
 431     /// let x = &mut [1, 2, 4];
 432     ///
 433     /// unsafe {
 434     ///     let elem = x.get_unchecked_mut(1);
 435     ///     *elem = 13;
 436     /// }
 437     /// assert_eq!(x, &[1, 13, 4]);
 438     /// ```
 439     #[stable(feature = "rust1", since = "1.0.0")]
 440     #[inline]
 441     pub unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
 442         where I: SliceIndex<Self>
 443     {
 444         core_slice::SliceExt::get_unchecked_mut(self, index)
 445     }
 446
 447     /// Returns a raw pointer to the slice's buffer.
 448     ///
 449     /// The caller must ensure that the slice outlives the pointer this
 450     /// function returns, or else it will end up pointing to garbage.
 451     ///
 452     /// Modifying the container referenced by this slice may cause its buffer
 453     /// to be reallocated, which would also make any pointers to it invalid.
 454     ///
 455     /// # Examples
 456     ///
 457     /// ```
 458     /// let x = &[1, 2, 4];
 459     /// let x_ptr = x.as_ptr();
 460     ///
 461     /// unsafe {
 462     ///     for i in 0..x.len() {
 463     ///         assert_eq!(x.get_unchecked(i), &*x_ptr.offset(i as isize));
 464     ///     }
 465     /// }
 466     /// ```
 467     #[stable(feature = "rust1", since = "1.0.0")]
 468     #[inline]
 469     pub fn as_ptr(&self) -> *const T {
 470         core_slice::SliceExt::as_ptr(self)
 471     }
 472
 473     /// Returns an unsafe mutable pointer to the slice's buffer.
 474     ///
 475     /// The caller must ensure that the slice outlives the pointer this
 476     /// function returns, or else it will end up pointing to garbage.
 477     ///
 478     /// Modifying the container referenced by this slice may cause its buffer
 479     /// to be reallocated, which would also make any pointers to it invalid.
 480     ///
 481     /// # Examples
 482     ///
 483     /// ```
 484     /// let x = &mut [1, 2, 4];
 485     /// let x_ptr = x.as_mut_ptr();
 486     ///
 487     /// unsafe {
 488     ///     for i in 0..x.len() {
 489     ///         *x_ptr.offset(i as isize) += 2;
 490     ///     }
 491     /// }
 492     /// assert_eq!(x, &[3, 4, 6]);
 493     /// ```
 494     #[stable(feature = "rust1", since = "1.0.0")]
 495     #[inline]
 496     pub fn as_mut_ptr(&mut self) -> *mut T {
 497         core_slice::SliceExt::as_mut_ptr(self)
 498     }
 499
 500     /// Swaps two elements in the slice.
 501     ///
 502     /// # Arguments
 503     ///
 504     /// * a - The index of the first element
 505     /// * b - The index of the second element
 506     ///
 507     /// # Panics
 508     ///
 509     /// Panics if `a` or `b` are out of bounds.
 510     ///
 511     /// # Examples
 512     ///
 513     /// ```
 514     /// let mut v = ["a", "b", "c", "d"];
 515     /// v.swap(1, 3);
 516     /// assert!(v == ["a", "d", "c", "b"]);
 517     /// ```
 518     #[stable(feature = "rust1", since = "1.0.0")]
 519     #[inline]
 520     pub fn swap(&mut self, a: usize, b: usize) {
 521         core_slice::SliceExt::swap(self, a, b)
 522     }
 523
 524     /// Reverses the order of elements in the slice, in place.
 525     ///
 526     /// # Examples
 527     ///
 528     /// ```
 529     /// let mut v = [1, 2, 3];
 530     /// v.reverse();
 531     /// assert!(v == [3, 2, 1]);
 532     /// ```
 533     #[stable(feature = "rust1", since = "1.0.0")]
 534     #[inline]
 535     pub fn reverse(&mut self) {
 536         core_slice::SliceExt::reverse(self)
 537     }
 538
 539     /// Returns an iterator over the slice.
 540     ///
 541     /// # Examples
 542     ///
 543     /// ```
 544     /// let x = &[1, 2, 4];
 545     /// let mut iterator = x.iter();
 546     ///
 547     /// assert_eq!(iterator.next(), Some(&1));
 548     /// assert_eq!(iterator.next(), Some(&2));
 549     /// assert_eq!(iterator.next(), Some(&4));
 550     /// assert_eq!(iterator.next(), None);
 551     /// ```
 552     #[stable(feature = "rust1", since = "1.0.0")]
 553     #[inline]
 554     pub fn iter(&self) -> Iter<T> {
 555         core_slice::SliceExt::iter(self)
 556     }
 557
 558     /// Returns an iterator that allows modifying each value.
 559     ///
 560     /// # Examples
 561     ///
 562     /// ```
 563     /// let x = &mut [1, 2, 4];
 564     /// for elem in x.iter_mut() {
 565     ///     *elem += 2;
 566     /// }
 567     /// assert_eq!(x, &[3, 4, 6]);
 568     /// ```
 569     #[stable(feature = "rust1", since = "1.0.0")]
 570     #[inline]
 571     pub fn iter_mut(&mut self) -> IterMut<T> {
 572         core_slice::SliceExt::iter_mut(self)
 573     }
 574
 575     /// Returns an iterator over all contiguous windows of length
 576     /// `size`. The windows overlap. If the slice is shorter than
 577     /// `size`, the iterator returns no values.
 578     ///
 579     /// # Panics
 580     ///
 581     /// Panics if `size` is 0.
 582     ///
 583     /// # Examples
 584     ///
 585     /// ```
 586     /// let slice = ['r', 'u', 's', 't'];
 587     /// let mut iter = slice.windows(2);
 588     /// assert_eq!(iter.next().unwrap(), &['r', 'u']);
 589     /// assert_eq!(iter.next().unwrap(), &['u', 's']);
 590     /// assert_eq!(iter.next().unwrap(), &['s', 't']);
 591     /// assert!(iter.next().is_none());
 592     /// ```
 593     ///
 594     /// If the slice is shorter than `size`:
 595     ///
 596     /// ```
 597     /// let slice = ['f', 'o', 'o'];
 598     /// let mut iter = slice.windows(4);
 599     /// assert!(iter.next().is_none());
 600     /// ```
 601     #[stable(feature = "rust1", since = "1.0.0")]
 602     #[inline]
 603     pub fn windows(&self, size: usize) -> Windows<T> {
 604         core_slice::SliceExt::windows(self, size)
 605     }
 606
 607     /// Returns an iterator over `size` elements of the slice at a
 608     /// time. The chunks are slices and do not overlap. If `size` does
 609     /// not divide the length of the slice, then the last chunk will
 610     /// not have length `size`.
 611     ///
 612     /// # Panics
 613     ///
 614     /// Panics if `size` is 0.
 615     ///
 616     /// # Examples
 617     ///
 618     /// ```
 619     /// let slice = ['l', 'o', 'r', 'e', 'm'];
 620     /// let mut iter = slice.chunks(2);
 621     /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
 622     /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
 623     /// assert_eq!(iter.next().unwrap(), &['m']);
 624     /// assert!(iter.next().is_none());
 625     /// ```
 626     #[stable(feature = "rust1", since = "1.0.0")]
 627     #[inline]
 628     pub fn chunks(&self, size: usize) -> Chunks<T> {
 629         core_slice::SliceExt::chunks(self, size)
 630     }
 631
 632     /// Returns an iterator over `chunk_size` elements of the slice at a time.
 633     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does
 634     /// not divide the length of the slice, then the last chunk will not
 635     /// have length `chunk_size`.
 636     ///
 637     /// # Panics
 638     ///
 639     /// Panics if `chunk_size` is 0.
 640     ///
 641     /// # Examples
 642     ///
 643     /// ```
 644     /// let v = &mut [0, 0, 0, 0, 0];
 645     /// let mut count = 1;
 646     ///
 647     /// for chunk in v.chunks_mut(2) {
 648     ///     for elem in chunk.iter_mut() {
 649     ///         *elem += count;
 650     ///     }
 651     ///     count += 1;
 652     /// }
 653     /// assert_eq!(v, &[1, 1, 2, 2, 3]);
 654     /// ```
 655     #[stable(feature = "rust1", since = "1.0.0")]
 656     #[inline]
 657     pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> {
 658         core_slice::SliceExt::chunks_mut(self, chunk_size)
 659     }
 660
 661     /// Divides one slice into two at an index.
 662     ///
 663     /// The first will contain all indices from `[0, mid)` (excluding
 664     /// the index `mid` itself) and the second will contain all
 665     /// indices from `[mid, len)` (excluding the index `len` itself).
 666     ///
 667     /// # Panics
 668     ///
 669     /// Panics if `mid > len`.
 670     ///
 671     /// # Examples
 672     ///
 673     /// ```
 674     /// let v = [1, 2, 3, 4, 5, 6];
 675     ///
 676     /// {
 677     ///    let (left, right) = v.split_at(0);
 678     ///    assert!(left == []);
 679     ///    assert!(right == [1, 2, 3, 4, 5, 6]);
 680     /// }
 681     ///
 682     /// {
 683     ///     let (left, right) = v.split_at(2);
 684     ///     assert!(left == [1, 2]);
 685     ///     assert!(right == [3, 4, 5, 6]);
 686     /// }
 687     ///
 688     /// {
 689     ///     let (left, right) = v.split_at(6);
 690     ///     assert!(left == [1, 2, 3, 4, 5, 6]);
 691     ///     assert!(right == []);
 692     /// }
 693     /// ```
 694     #[stable(feature = "rust1", since = "1.0.0")]
 695     #[inline]
 696     pub fn split_at(&self, mid: usize) -> (&[T], &[T]) {
 697         core_slice::SliceExt::split_at(self, mid)
 698     }
 699
 700     /// Divides one `&mut` into two at an index.
 701     ///
 702     /// The first will contain all indices from `[0, mid)` (excluding
 703     /// the index `mid` itself) and the second will contain all
 704     /// indices from `[mid, len)` (excluding the index `len` itself).
 705     ///
 706     /// # Panics
 707     ///
 708     /// Panics if `mid > len`.
 709     ///
 710     /// # Examples
 711     ///
 712     /// ```
 713     /// let mut v = [1, 0, 3, 0, 5, 6];
 714     /// // scoped to restrict the lifetime of the borrows
 715     /// {
 716     ///     let (left, right) = v.split_at_mut(2);
 717     ///     assert!(left == [1, 0]);
 718     ///     assert!(right == [3, 0, 5, 6]);
 719     ///     left[1] = 2;
 720     ///     right[1] = 4;
 721     /// }
 722     /// assert!(v == [1, 2, 3, 4, 5, 6]);
 723     /// ```
 724     #[stable(feature = "rust1", since = "1.0.0")]
 725     #[inline]
 726     pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
 727         core_slice::SliceExt::split_at_mut(self, mid)
 728     }
 729
 730     /// Returns an iterator over subslices separated by elements that match
 731     /// `pred`. The matched element is not contained in the subslices.
 732     ///
 733     /// # Examples
 734     ///
 735     /// ```
 736     /// let slice = [10, 40, 33, 20];
 737     /// let mut iter = slice.split(|num| num % 3 == 0);
 738     ///
 739     /// assert_eq!(iter.next().unwrap(), &[10, 40]);
 740     /// assert_eq!(iter.next().unwrap(), &[20]);
 741     /// assert!(iter.next().is_none());
 742     /// ```
 743     ///
 744     /// If the first element is matched, an empty slice will be the first item
 745     /// returned by the iterator. Similarly, if the last element in the slice
 746     /// is matched, an empty slice will be the last item returned by the
 747     /// iterator:
 748     ///
 749     /// ```
 750     /// let slice = [10, 40, 33];
 751     /// let mut iter = slice.split(|num| num % 3 == 0);
 752     ///
 753     /// assert_eq!(iter.next().unwrap(), &[10, 40]);
 754     /// assert_eq!(iter.next().unwrap(), &[]);
 755     /// assert!(iter.next().is_none());
 756     /// ```
 757     ///
 758     /// If two matched elements are directly adjacent, an empty slice will be
 759     /// present between them:
 760     ///
 761     /// ```
 762     /// let slice = [10, 6, 33, 20];
 763     /// let mut iter = slice.split(|num| num % 3 == 0);
 764     ///
 765     /// assert_eq!(iter.next().unwrap(), &[10]);
 766     /// assert_eq!(iter.next().unwrap(), &[]);
 767     /// assert_eq!(iter.next().unwrap(), &[20]);
 768     /// assert!(iter.next().is_none());
 769     /// ```
 770     #[stable(feature = "rust1", since = "1.0.0")]
 771     #[inline]
 772     pub fn split<F>(&self, pred: F) -> Split<T, F>
 773         where F: FnMut(&T) -> bool
 774     {
 775         core_slice::SliceExt::split(self, pred)
 776     }
 777
 778     /// Returns an iterator over mutable subslices separated by elements that
 779     /// match `pred`. The matched element is not contained in the subslices.
 780     ///
 781     /// # Examples
 782     ///
 783     /// ```
 784     /// let mut v = [10, 40, 30, 20, 60, 50];
 785     ///
 786     /// for group in v.split_mut(|num| *num % 3 == 0) {
 787     ///     group[0] = 1;
 788     /// }
 789     /// assert_eq!(v, [1, 40, 30, 1, 60, 1]);
 790     /// ```
 791     #[stable(feature = "rust1", since = "1.0.0")]
 792     #[inline]
 793     pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<T, F>
 794         where F: FnMut(&T) -> bool
 795     {
 796         core_slice::SliceExt::split_mut(self, pred)
 797     }
 798
 799     /// Returns an iterator over subslices separated by elements that match
 800     /// `pred`, starting at the end of the slice and working backwards.
 801     /// The matched element is not contained in the subslices.
 802     ///
 803     /// # Examples
 804     ///
 805     /// ```
 806     /// #![feature(slice_rsplit)]
 807     ///
 808     /// let slice = [11, 22, 33, 0, 44, 55];
 809     /// let mut iter = slice.rsplit(|num| *num == 0);
 810     ///
 811     /// assert_eq!(iter.next().unwrap(), &[44, 55]);
 812     /// assert_eq!(iter.next().unwrap(), &[11, 22, 33]);
 813     /// assert_eq!(iter.next(), None);
 814     /// ```
 815     ///
 816     /// As with `split()`, if the first or last element is matched, an empty
 817     /// slice will be the first (or last) item returned by the iterator.
 818     ///
 819     /// ```
 820     /// #![feature(slice_rsplit)]
 821     ///
 822     /// let v = &[0, 1, 1, 2, 3, 5, 8];
 823     /// let mut it = v.rsplit(|n| *n % 2 == 0);
 824     /// assert_eq!(it.next().unwrap(), &[]);
 825     /// assert_eq!(it.next().unwrap(), &[3, 5]);
 826     /// assert_eq!(it.next().unwrap(), &[1, 1]);
 827     /// assert_eq!(it.next().unwrap(), &[]);
 828     /// assert_eq!(it.next(), None);
 829     /// ```
 830     #[unstable(feature = "slice_rsplit", issue = "41020")]
 831     #[inline]
 832     pub fn rsplit<F>(&self, pred: F) -> RSplit<T, F>
 833         where F: FnMut(&T) -> bool
 834     {
 835         core_slice::SliceExt::rsplit(self, pred)
 836     }
 837
 838     /// Returns an iterator over mutable subslices separated by elements that
 839     /// match `pred`, starting at the end of the slice and working
 840     /// backwards. The matched element is not contained in the subslices.
 841     ///
 842     /// # Examples
 843     ///
 844     /// ```
 845     /// #![feature(slice_rsplit)]
 846     ///
 847     /// let mut v = [100, 400, 300, 200, 600, 500];
 848     ///
 849     /// let mut count = 0;
 850     /// for group in v.rsplit_mut(|num| *num % 3 == 0) {
 851     ///     count += 1;
 852     ///     group[0] = count;
 853     /// }
 854     /// assert_eq!(v, [3, 400, 300, 2, 600, 1]);
 855     /// ```
 856     ///
 857     #[unstable(feature = "slice_rsplit", issue = "41020")]
 858     #[inline]
 859     pub fn rsplit_mut<F>(&mut self, pred: F) -> RSplitMut<T, F>
 860         where F: FnMut(&T) -> bool
 861     {
 862         core_slice::SliceExt::rsplit_mut(self, pred)
 863     }
 864
 865     /// Returns an iterator over subslices separated by elements that match
 866     /// `pred`, limited to returning at most `n` items. The matched element is
 867     /// not contained in the subslices.
 868     ///
 869     /// The last element returned, if any, will contain the remainder of the
 870     /// slice.
 871     ///
 872     /// # Examples
 873     ///
 874     /// Print the slice split once by numbers divisible by 3 (i.e. `[10, 40]`,
 875     /// `[20, 60, 50]`):
 876     ///
 877     /// ```
 878     /// let v = [10, 40, 30, 20, 60, 50];
 879     ///
 880     /// for group in v.splitn(2, |num| *num % 3 == 0) {
 881     ///     println!("{:?}", group);
 882     /// }
 883     /// ```
 884     #[stable(feature = "rust1", since = "1.0.0")]
 885     #[inline]
 886     pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<T, F>
 887         where F: FnMut(&T) -> bool
 888     {
 889         core_slice::SliceExt::splitn(self, n, pred)
 890     }
 891
 892     /// Returns an iterator over subslices separated by elements that match
 893     /// `pred`, limited to returning at most `n` items. The matched element is
 894     /// not contained in the subslices.
 895     ///
 896     /// The last element returned, if any, will contain the remainder of the
 897     /// slice.
 898     ///
 899     /// # Examples
 900     ///
 901     /// ```
 902     /// let mut v = [10, 40, 30, 20, 60, 50];
 903     ///
 904     /// for group in v.splitn_mut(2, |num| *num % 3 == 0) {
 905     ///     group[0] = 1;
 906     /// }
 907     /// assert_eq!(v, [1, 40, 30, 1, 60, 50]);
 908     /// ```
 909     #[stable(feature = "rust1", since = "1.0.0")]
 910     #[inline]
 911     pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<T, F>
 912         where F: FnMut(&T) -> bool
 913     {
 914         core_slice::SliceExt::splitn_mut(self, n, pred)
 915     }
 916
 917     /// Returns an iterator over subslices separated by elements that match
 918     /// `pred` limited to returning at most `n` items. This starts at the end of
 919     /// the slice and works backwards.  The matched element is not contained in
 920     /// the subslices.
 921     ///
 922     /// The last element returned, if any, will contain the remainder of the
 923     /// slice.
 924     ///
 925     /// # Examples
 926     ///
 927     /// Print the slice split once, starting from the end, by numbers divisible
 928     /// by 3 (i.e. `[50]`, `[10, 40, 30, 20]`):
 929     ///
 930     /// ```
 931     /// let v = [10, 40, 30, 20, 60, 50];
 932     ///
 933     /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
 934     ///     println!("{:?}", group);
 935     /// }
 936     /// ```
 937     #[stable(feature = "rust1", since = "1.0.0")]
 938     #[inline]
 939     pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<T, F>
 940         where F: FnMut(&T) -> bool
 941     {
 942         core_slice::SliceExt::rsplitn(self, n, pred)
 943     }
 944
 945     /// Returns an iterator over subslices separated by elements that match
 946     /// `pred` limited to returning at most `n` items. This starts at the end of
 947     /// the slice and works backwards. The matched element is not contained in
 948     /// the subslices.
 949     ///
 950     /// The last element returned, if any, will contain the remainder of the
 951     /// slice.
 952     ///
 953     /// # Examples
 954     ///
 955     /// ```
 956     /// let mut s = [10, 40, 30, 20, 60, 50];
 957     ///
 958     /// for group in s.rsplitn_mut(2, |num| *num % 3 == 0) {
 959     ///     group[0] = 1;
 960     /// }
 961     /// assert_eq!(s, [1, 40, 30, 20, 60, 1]);
 962     /// ```
 963     #[stable(feature = "rust1", since = "1.0.0")]
 964     #[inline]
 965     pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<T, F>
 966         where F: FnMut(&T) -> bool
 967     {
 968         core_slice::SliceExt::rsplitn_mut(self, n, pred)
 969     }
 970
 971     /// Returns `true` if the slice contains an element with the given value.
 972     ///
 973     /// # Examples
 974     ///
 975     /// ```
 976     /// let v = [10, 40, 30];
 977     /// assert!(v.contains(&30));
 978     /// assert!(!v.contains(&50));
 979     /// ```
 980     #[stable(feature = "rust1", since = "1.0.0")]
 981     pub fn contains(&self, x: &T) -> bool
 982         where T: PartialEq
 983     {
 984         core_slice::SliceExt::contains(self, x)
 985     }
 986
 987     /// Returns `true` if `needle` is a prefix of the slice.
 988     ///
 989     /// # Examples
 990     ///
 991     /// ```
 992     /// let v = [10, 40, 30];
 993     /// assert!(v.starts_with(&[10]));
 994     /// assert!(v.starts_with(&[10, 40]));
 995     /// assert!(!v.starts_with(&[50]));
 996     /// assert!(!v.starts_with(&[10, 50]));
 997     /// ```
 998     ///
 999     /// Always returns `true` if `needle` is an empty slice:
1000     ///
1001     /// ```
1002     /// let v = &[10, 40, 30];
1003     /// assert!(v.starts_with(&[]));
1004     /// let v: &[u8] = &[];
1005     /// assert!(v.starts_with(&[]));
1006     /// ```
1007     #[stable(feature = "rust1", since = "1.0.0")]
1008     pub fn starts_with(&self, needle: &[T]) -> bool
1009         where T: PartialEq
1010     {
1011         core_slice::SliceExt::starts_with(self, needle)
1012     }
1013
1014     /// Returns `true` if `needle` is a suffix of the slice.
1015     ///
1016     /// # Examples
1017     ///
1018     /// ```
1019     /// let v = [10, 40, 30];
1020     /// assert!(v.ends_with(&[30]));
1021     /// assert!(v.ends_with(&[40, 30]));
1022     /// assert!(!v.ends_with(&[50]));
1023     /// assert!(!v.ends_with(&[50, 30]));
1024     /// ```
1025     ///
1026     /// Always returns `true` if `needle` is an empty slice:
1027     ///
1028     /// ```
1029     /// let v = &[10, 40, 30];
1030     /// assert!(v.ends_with(&[]));
1031     /// let v: &[u8] = &[];
1032     /// assert!(v.ends_with(&[]));
1033     /// ```
1034     #[stable(feature = "rust1", since = "1.0.0")]
1035     pub fn ends_with(&self, needle: &[T]) -> bool
1036         where T: PartialEq
1037     {
1038         core_slice::SliceExt::ends_with(self, needle)
1039     }
1040
1041     /// Binary searches this sorted slice for a given element.
1042     ///
1043     /// If the value is found then `Ok` is returned, containing the
1044     /// index of the matching element; if the value is not found then
1045     /// `Err` is returned, containing the index where a matching
1046     /// element could be inserted while maintaining sorted order.
1047     ///
1048     /// # Examples
1049     ///
1050     /// Looks up a series of four elements. The first is found, with a
1051     /// uniquely determined position; the second and third are not
1052     /// found; the fourth could match any position in `[1, 4]`.
1053     ///
1054     /// ```
1055     /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1056     ///
1057     /// assert_eq!(s.binary_search(&13),  Ok(9));
1058     /// assert_eq!(s.binary_search(&4),   Err(7));
1059     /// assert_eq!(s.binary_search(&100), Err(13));
1060     /// let r = s.binary_search(&1);
1061     /// assert!(match r { Ok(1...4) => true, _ => false, });
1062     /// ```
1063     #[stable(feature = "rust1", since = "1.0.0")]
1064     pub fn binary_search(&self, x: &T) -> Result<usize, usize>
1065         where T: Ord
1066     {
1067         core_slice::SliceExt::binary_search(self, x)
1068     }
1069
1070     /// Binary searches this sorted slice with a comparator function.
1071     ///
1072     /// The comparator function should implement an order consistent
1073     /// with the sort order of the underlying slice, returning an
1074     /// order code that indicates whether its argument is `Less`,
1075     /// `Equal` or `Greater` the desired target.
1076     ///
1077     /// If a matching value is found then returns `Ok`, containing
1078     /// the index for the matched element; if no match is found then
1079     /// `Err` is returned, containing the index where a matching
1080     /// element could be inserted while maintaining sorted order.
1081     ///
1082     /// # Examples
1083     ///
1084     /// Looks up a series of four elements. The first is found, with a
1085     /// uniquely determined position; the second and third are not
1086     /// found; the fourth could match any position in `[1, 4]`.
1087     ///
1088     /// ```
1089     /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1090     ///
1091     /// let seek = 13;
1092     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
1093     /// let seek = 4;
1094     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
1095     /// let seek = 100;
1096     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
1097     /// let seek = 1;
1098     /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
1099     /// assert!(match r { Ok(1...4) => true, _ => false, });
1100     /// ```
1101     #[stable(feature = "rust1", since = "1.0.0")]
1102     #[inline]
1103     pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>
1104         where F: FnMut(&'a T) -> Ordering
1105     {
1106         core_slice::SliceExt::binary_search_by(self, f)
1107     }
1108
1109     /// Binary searches this sorted slice with a key extraction function.
1110     ///
1111     /// Assumes that the slice is sorted by the key, for instance with
1112     /// [`sort_by_key`] using the same key extraction function.
1113     ///
1114     /// If a matching value is found then returns `Ok`, containing the
1115     /// index for the matched element; if no match is found then `Err`
1116     /// is returned, containing the index where a matching element could
1117     /// be inserted while maintaining sorted order.
1118     ///
1119     /// [`sort_by_key`]: #method.sort_by_key
1120     ///
1121     /// # Examples
1122     ///
1123     /// Looks up a series of four elements in a slice of pairs sorted by
1124     /// their second elements. The first is found, with a uniquely
1125     /// determined position; the second and third are not found; the
1126     /// fourth could match any position in `[1, 4]`.
1127     ///
1128     /// ```
1129     /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1),
1130     ///          (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
1131     ///          (1, 21), (2, 34), (4, 55)];
1132     ///
1133     /// assert_eq!(s.binary_search_by_key(&13, |&(a,b)| b),  Ok(9));
1134     /// assert_eq!(s.binary_search_by_key(&4, |&(a,b)| b),   Err(7));
1135     /// assert_eq!(s.binary_search_by_key(&100, |&(a,b)| b), Err(13));
1136     /// let r = s.binary_search_by_key(&1, |&(a,b)| b);
1137     /// assert!(match r { Ok(1...4) => true, _ => false, });
1138     /// ```
1139     #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
1140     #[inline]
1141     pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, f: F) -> Result<usize, usize>
1142         where F: FnMut(&'a T) -> B,
1143               B: Ord
1144     {
1145         core_slice::SliceExt::binary_search_by_key(self, b, f)
1146     }
1147
1148     /// Sorts the slice.
1149     ///
1150     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
1151     ///
1152     /// When applicable, unstable sorting is preferred because it is generally faster than stable
1153     /// sorting and it doesn't allocate auxiliary memory.
1154     /// See [`sort_unstable`](#method.sort_unstable).
1155     ///
1156     /// # Current implementation
1157     ///
1158     /// The current algorithm is an adaptive, iterative merge sort inspired by
1159     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
1160     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
1161     /// two or more sorted sequences concatenated one after another.
1162     ///
1163     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
1164     /// non-allocating insertion sort is used instead.
1165     ///
1166     /// # Examples
1167     ///
1168     /// ```
1169     /// let mut v = [-5, 4, 1, -3, 2];
1170     ///
1171     /// v.sort();
1172     /// assert!(v == [-5, -3, 1, 2, 4]);
1173     /// ```
1174     #[stable(feature = "rust1", since = "1.0.0")]
1175     #[inline]
1176     pub fn sort(&mut self)
1177         where T: Ord
1178     {
1179         merge_sort(self, |a, b| a.lt(b));
1180     }
1181
1182     /// Sorts the slice with a comparator function.
1183     ///
1184     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
1185     ///
1186     /// When applicable, unstable sorting is preferred because it is generally faster than stable
1187     /// sorting and it doesn't allocate auxiliary memory.
1188     /// See [`sort_unstable_by`](#method.sort_unstable_by).
1189     ///
1190     /// # Current implementation
1191     ///
1192     /// The current algorithm is an adaptive, iterative merge sort inspired by
1193     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
1194     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
1195     /// two or more sorted sequences concatenated one after another.
1196     ///
1197     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
1198     /// non-allocating insertion sort is used instead.
1199     ///
1200     /// # Examples
1201     ///
1202     /// ```
1203     /// let mut v = [5, 4, 1, 3, 2];
1204     /// v.sort_by(|a, b| a.cmp(b));
1205     /// assert!(v == [1, 2, 3, 4, 5]);
1206     ///
1207     /// // reverse sorting
1208     /// v.sort_by(|a, b| b.cmp(a));
1209     /// assert!(v == [5, 4, 3, 2, 1]);
1210     /// ```
1211     #[stable(feature = "rust1", since = "1.0.0")]
1212     #[inline]
1213     pub fn sort_by<F>(&mut self, mut compare: F)
1214         where F: FnMut(&T, &T) -> Ordering
1215     {
1216         merge_sort(self, |a, b| compare(a, b) == Less);
1217     }
1218
1219     /// Sorts the slice with a key extraction function.
1220     ///
1221     /// This sort is stable (i.e. does not reorder equal elements) and `O(n log n)` worst-case.
1222     ///
1223     /// When applicable, unstable sorting is preferred because it is generally faster than stable
1224     /// sorting and it doesn't allocate auxiliary memory.
1225     /// See [`sort_unstable_by_key`](#method.sort_unstable_by_key).
1226     ///
1227     /// # Current implementation
1228     ///
1229     /// The current algorithm is an adaptive, iterative merge sort inspired by
1230     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
1231     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
1232     /// two or more sorted sequences concatenated one after another.
1233     ///
1234     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
1235     /// non-allocating insertion sort is used instead.
1236     ///
1237     /// # Examples
1238     ///
1239     /// ```
1240     /// let mut v = [-5i32, 4, 1, -3, 2];
1241     ///
1242     /// v.sort_by_key(|k| k.abs());
1243     /// assert!(v == [1, 2, -3, 4, -5]);
1244     /// ```
1245     #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
1246     #[inline]
1247     pub fn sort_by_key<B, F>(&mut self, mut f: F)
1248         where F: FnMut(&T) -> B, B: Ord
1249     {
1250         merge_sort(self, |a, b| f(a).lt(&f(b)));
1251     }
1252
1253     /// Sorts the slice, but may not preserve the order of equal elements.
1254     ///
1255     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1256     /// and `O(n log n)` worst-case.
1257     ///
1258     /// # Current implementation
1259     ///
1260     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1261     /// which combines the fast average case of randomized quicksort with the fast worst case of
1262     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1263     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1264     /// deterministic behavior.
1265     ///
1266     /// It is typically faster than stable sorting, except in a few special cases, e.g. when the
1267     /// slice consists of several concatenated sorted sequences.
1268     ///
1269     /// # Examples
1270     ///
1271     /// ```
1272     /// let mut v = [-5, 4, 1, -3, 2];
1273     ///
1274     /// v.sort_unstable();
1275     /// assert!(v == [-5, -3, 1, 2, 4]);
1276     /// ```
1277     ///
1278     /// [pdqsort]: https://github.com/orlp/pdqsort
1279     #[stable(feature = "sort_unstable", since = "1.20.0")]
1280     #[inline]
1281     pub fn sort_unstable(&mut self)
1282         where T: Ord
1283     {
1284         core_slice::SliceExt::sort_unstable(self);
1285     }
1286
1287     /// Sorts the slice with a comparator function, but may not preserve the order of equal
1288     /// elements.
1289     ///
1290     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1291     /// and `O(n log n)` worst-case.
1292     ///
1293     /// # Current implementation
1294     ///
1295     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1296     /// which combines the fast average case of randomized quicksort with the fast worst case of
1297     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1298     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1299     /// deterministic behavior.
1300     ///
1301     /// It is typically faster than stable sorting, except in a few special cases, e.g. when the
1302     /// slice consists of several concatenated sorted sequences.
1303     ///
1304     /// # Examples
1305     ///
1306     /// ```
1307     /// let mut v = [5, 4, 1, 3, 2];
1308     /// v.sort_unstable_by(|a, b| a.cmp(b));
1309     /// assert!(v == [1, 2, 3, 4, 5]);
1310     ///
1311     /// // reverse sorting
1312     /// v.sort_unstable_by(|a, b| b.cmp(a));
1313     /// assert!(v == [5, 4, 3, 2, 1]);
1314     /// ```
1315     ///
1316     /// [pdqsort]: https://github.com/orlp/pdqsort
1317     #[stable(feature = "sort_unstable", since = "1.20.0")]
1318     #[inline]
1319     pub fn sort_unstable_by<F>(&mut self, compare: F)
1320         where F: FnMut(&T, &T) -> Ordering
1321     {
1322         core_slice::SliceExt::sort_unstable_by(self, compare);
1323     }
1324
1325     /// Sorts the slice with a key extraction function, but may not preserve the order of equal
1326     /// elements.
1327     ///
1328     /// This sort is unstable (i.e. may reorder equal elements), in-place (i.e. does not allocate),
1329     /// and `O(n log n)` worst-case.
1330     ///
1331     /// # Current implementation
1332     ///
1333     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1334     /// which combines the fast average case of randomized quicksort with the fast worst case of
1335     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1336     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1337     /// deterministic behavior.
1338     ///
1339     /// It is typically faster than stable sorting, except in a few special cases, e.g. when the
1340     /// slice consists of several concatenated sorted sequences.
1341     ///
1342     /// # Examples
1343     ///
1344     /// ```
1345     /// let mut v = [-5i32, 4, 1, -3, 2];
1346     ///
1347     /// v.sort_unstable_by_key(|k| k.abs());
1348     /// assert!(v == [1, 2, -3, 4, -5]);
1349     /// ```
1350     ///
1351     /// [pdqsort]: https://github.com/orlp/pdqsort
1352     #[stable(feature = "sort_unstable", since = "1.20.0")]
1353     #[inline]
1354     pub fn sort_unstable_by_key<B, F>(&mut self, f: F)
1355         where F: FnMut(&T) -> B,
1356               B: Ord
1357     {
1358         core_slice::SliceExt::sort_unstable_by_key(self, f);
1359     }
1360
1361     /// Permutes the slice in-place such that `self[mid..]` moves to the
1362     /// beginning of the slice while `self[..mid]` moves to the end of the
1363     /// slice.  Equivalently, rotates the slice `mid` places to the left
1364     /// or `k = self.len() - mid` places to the right.
1365     ///
1366     /// This is a "k-rotation", a permutation in which item `i` moves to
1367     /// position `i + k`, modulo the length of the slice.  See _Elements
1368     /// of Programming_ [§10.4][eop].
1369     ///
1370     /// Rotation by `mid` and rotation by `k` are inverse operations.
1371     ///
1372     /// [eop]: https://books.google.com/books?id=CO9ULZGINlsC&pg=PA178&q=k-rotation
1373     ///
1374     /// # Panics
1375     ///
1376     /// This function will panic if `mid` is greater than the length of the
1377     /// slice.  (Note that `mid == self.len()` does _not_ panic; it's a nop
1378     /// rotation with `k == 0`, the inverse of a rotation with `mid == 0`.)
1379     ///
1380     /// # Complexity
1381     ///
1382     /// Takes linear (in `self.len()`) time.
1383     ///
1384     /// # Examples
1385     ///
1386     /// ```
1387     /// #![feature(slice_rotate)]
1388     ///
1389     /// let mut a = [1, 2, 3, 4, 5, 6, 7];
1390     /// let mid = 2;
1391     /// a.rotate(mid);
1392     /// assert_eq!(&a, &[3, 4, 5, 6, 7, 1, 2]);
1393     /// let k = a.len() - mid;
1394     /// a.rotate(k);
1395     /// assert_eq!(&a, &[1, 2, 3, 4, 5, 6, 7]);
1396     ///
1397     /// use std::ops::Range;
1398     /// fn slide<T>(slice: &mut [T], range: Range<usize>, to: usize) {
1399     ///     if to < range.start {
1400     ///         slice[to..range.end].rotate(range.start-to);
1401     ///     } else if to > range.end {
1402     ///         slice[range.start..to].rotate(range.end-range.start);
1403     ///     }
1404     /// }
1405     /// let mut v: Vec<_> = (0..10).collect();
1406     /// slide(&mut v, 1..4, 7);
1407     /// assert_eq!(&v, &[0, 4, 5, 6, 1, 2, 3, 7, 8, 9]);
1408     /// slide(&mut v, 6..8, 1);
1409     /// assert_eq!(&v, &[0, 3, 7, 4, 5, 6, 1, 2, 8, 9]);
1410     /// ```
1411     #[unstable(feature = "slice_rotate", issue = "41891")]
1412     pub fn rotate(&mut self, mid: usize) {
1413         core_slice::SliceExt::rotate(self, mid);
1414     }
1415
1416     /// Copies the elements from `src` into `self`.
1417     ///
1418     /// The length of `src` must be the same as `self`.
1419     ///
1420     /// If `src` implements `Copy`, it can be more performant to use
1421     /// [`copy_from_slice`].
1422     ///
1423     /// # Panics
1424     ///
1425     /// This function will panic if the two slices have different lengths.
1426     ///
1427     /// # Examples
1428     ///
1429     /// ```
1430     /// let mut dst = [0, 0, 0];
1431     /// let src = [1, 2, 3];
1432     ///
1433     /// dst.clone_from_slice(&src);
1434     /// assert!(dst == [1, 2, 3]);
1435     /// ```
1436     ///
1437     /// [`copy_from_slice`]: #method.copy_from_slice
1438     #[stable(feature = "clone_from_slice", since = "1.7.0")]
1439     pub fn clone_from_slice(&mut self, src: &[T]) where T: Clone {
1440         core_slice::SliceExt::clone_from_slice(self, src)
1441     }
1442
1443     /// Copies all elements from `src` into `self`, using a memcpy.
1444     ///
1445     /// The length of `src` must be the same as `self`.
1446     ///
1447     /// If `src` does not implement `Copy`, use [`clone_from_slice`].
1448     ///
1449     /// # Panics
1450     ///
1451     /// This function will panic if the two slices have different lengths.
1452     ///
1453     /// # Examples
1454     ///
1455     /// ```
1456     /// let mut dst = [0, 0, 0];
1457     /// let src = [1, 2, 3];
1458     ///
1459     /// dst.copy_from_slice(&src);
1460     /// assert_eq!(src, dst);
1461     /// ```
1462     ///
1463     /// [`clone_from_slice`]: #method.clone_from_slice
1464     #[stable(feature = "copy_from_slice", since = "1.9.0")]
1465     pub fn copy_from_slice(&mut self, src: &[T]) where T: Copy {
1466         core_slice::SliceExt::copy_from_slice(self, src)
1467     }
1468
1469     /// Swaps all elements in `self` with those in `src`.
1470     ///
1471     /// The length of `src` must be the same as `self`.
1472     ///
1473     /// # Panics
1474     ///
1475     /// This function will panic if the two slices have different lengths.
1476     ///
1477     /// # Example
1478     ///
1479     /// ```
1480     /// #![feature(swap_with_slice)]
1481     ///
1482     /// let mut src = [1, 2, 3];
1483     /// let mut dst = [7, 8, 9];
1484     ///
1485     /// src.swap_with_slice(&mut dst);
1486     /// assert_eq!(src, [7, 8, 9]);
1487     /// assert_eq!(dst, [1, 2, 3]);
1488     /// ```
1489     #[unstable(feature = "swap_with_slice", issue = "44030")]
1490     pub fn swap_with_slice(&mut self, src: &mut [T]) {
1491         core_slice::SliceExt::swap_with_slice(self, src)
1492     }
1493
1494     /// Copies `self` into a new `Vec`.
1495     ///
1496     /// # Examples
1497     ///
1498     /// ```
1499     /// let s = [10, 40, 30];
1500     /// let x = s.to_vec();
1501     /// // Here, `s` and `x` can be modified independently.
1502     /// ```
1503     #[stable(feature = "rust1", since = "1.0.0")]
1504     #[inline]
1505     pub fn to_vec(&self) -> Vec<T>
1506         where T: Clone
1507     {
1508         // NB see hack module in this file
1509         hack::to_vec(self)
1510     }
1511
1512     /// Converts `self` into a vector without clones or allocation.
1513     ///
1514     /// The resulting vector can be converted back into a box via
1515     /// `Vec<T>`'s `into_boxed_slice` method.
1516     ///
1517     /// # Examples
1518     ///
1519     /// ```
1520     /// let s: Box<[i32]> = Box::new([10, 40, 30]);
1521     /// let x = s.into_vec();
1522     /// // `s` cannot be used anymore because it has been converted into `x`.
1523     ///
1524     /// assert_eq!(x, vec![10, 40, 30]);
1525     /// ```
1526     #[stable(feature = "rust1", since = "1.0.0")]
1527     #[inline]
1528     pub fn into_vec(self: Box<Self>) -> Vec<T> {
1529         // NB see hack module in this file
1530         hack::into_vec(self)
1531     }
1532 }
1533
1534 ////////////////////////////////////////////////////////////////////////////////
1535 // Extension traits for slices over specific kinds of data
1536 ////////////////////////////////////////////////////////////////////////////////
1537 #[unstable(feature = "slice_concat_ext",
1538            reason = "trait should not have to exist",
1539            issue = "27747")]
1540 /// An extension trait for concatenating slices
1541 pub trait SliceConcatExt<T: ?Sized> {
1542     #[unstable(feature = "slice_concat_ext",
1543                reason = "trait should not have to exist",
1544                issue = "27747")]
1545     /// The resulting type after concatenation
1546     type Output;
1547
1548     /// Flattens a slice of `T` into a single value `Self::Output`.
1549     ///
1550     /// # Examples
1551     ///
1552     /// ```
1553     /// assert_eq!(["hello", "world"].concat(), "helloworld");
1554     /// assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
1555     /// ```
1556     #[stable(feature = "rust1", since = "1.0.0")]
1557     fn concat(&self) -> Self::Output;
1558
1559     /// Flattens a slice of `T` into a single value `Self::Output`, placing a
1560     /// given separator between each.
1561     ///
1562     /// # Examples
1563     ///
1564     /// ```
1565     /// assert_eq!(["hello", "world"].join(" "), "hello world");
1566     /// assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]);
1567     /// ```
1568     #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
1569     fn join(&self, sep: &T) -> Self::Output;
1570
1571     #[stable(feature = "rust1", since = "1.0.0")]
1572     #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")]
1573     fn connect(&self, sep: &T) -> Self::Output;
1574 }
1575
1576 #[unstable(feature = "slice_concat_ext",
1577            reason = "trait should not have to exist",
1578            issue = "27747")]
1579 impl<T: Clone, V: Borrow<[T]>> SliceConcatExt<T> for [V] {
1580     type Output = Vec<T>;
1581
1582     fn concat(&self) -> Vec<T> {
1583         let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
1584         let mut result = Vec::with_capacity(size);
1585         for v in self {
1586             result.extend_from_slice(v.borrow())
1587         }
1588         result
1589     }
1590
1591     fn join(&self, sep: &T) -> Vec<T> {
1592         let size = self.iter().fold(0, |acc, v| acc + v.borrow().len());
1593         let mut result = Vec::with_capacity(size + self.len());
1594         let mut first = true;
1595         for v in self {
1596             if first {
1597                 first = false
1598             } else {
1599                 result.push(sep.clone())
1600             }
1601             result.extend_from_slice(v.borrow())
1602         }
1603         result
1604     }
1605
1606     fn connect(&self, sep: &T) -> Vec<T> {
1607         self.join(sep)
1608     }
1609 }
1610
1611 ////////////////////////////////////////////////////////////////////////////////
1612 // Standard trait implementations for slices
1613 ////////////////////////////////////////////////////////////////////////////////
1614
1615 #[stable(feature = "rust1", since = "1.0.0")]
1616 impl<T> Borrow<[T]> for Vec<T> {
1617     fn borrow(&self) -> &[T] {
1618         &self[..]
1619     }
1620 }
1621
1622 #[stable(feature = "rust1", since = "1.0.0")]
1623 impl<T> BorrowMut<[T]> for Vec<T> {
1624     fn borrow_mut(&mut self) -> &mut [T] {
1625         &mut self[..]
1626     }
1627 }
1628
1629 #[stable(feature = "rust1", since = "1.0.0")]
1630 impl<T: Clone> ToOwned for [T] {
1631     type Owned = Vec<T>;
1632     #[cfg(not(test))]
1633     fn to_owned(&self) -> Vec<T> {
1634         self.to_vec()
1635     }
1636
1637     #[cfg(test)]
1638     fn to_owned(&self) -> Vec<T> {
1639         hack::to_vec(self)
1640     }
1641
1642     fn clone_into(&self, target: &mut Vec<T>) {
1643         // drop anything in target that will not be overwritten
1644         target.truncate(self.len());
1645         let len = target.len();
1646
1647         // reuse the contained values' allocations/resources.
1648         target.clone_from_slice(&self[..len]);
1649
1650         // target.len <= self.len due to the truncate above, so the
1651         // slice here is always in-bounds.
1652         target.extend_from_slice(&self[len..]);
1653     }
1654 }
1655
1656 ////////////////////////////////////////////////////////////////////////////////
1657 // Sorting
1658 ////////////////////////////////////////////////////////////////////////////////
1659
1660 /// Inserts `v[0]` into pre-sorted sequence `v[1..]` so that whole `v[..]` becomes sorted.
1661 ///
1662 /// This is the integral subroutine of insertion sort.
1663 fn insert_head<T, F>(v: &mut [T], is_less: &mut F)
1664     where F: FnMut(&T, &T) -> bool
1665 {
1666     if v.len() >= 2 && is_less(&v[1], &v[0]) {
1667         unsafe {
1668             // There are three ways to implement insertion here:
1669             //
1670             // 1. Swap adjacent elements until the first one gets to its final destination.
1671             //    However, this way we copy data around more than is necessary. If elements are big
1672             //    structures (costly to copy), this method will be slow.
1673             //
1674             // 2. Iterate until the right place for the first element is found. Then shift the
1675             //    elements succeeding it to make room for it and finally place it into the
1676             //    remaining hole. This is a good method.
1677             //
1678             // 3. Copy the first element into a temporary variable. Iterate until the right place
1679             //    for it is found. As we go along, copy every traversed element into the slot
1680             //    preceding it. Finally, copy data from the temporary variable into the remaining
1681             //    hole. This method is very good. Benchmarks demonstrated slightly better
1682             //    performance than with the 2nd method.
1683             //
1684             // All methods were benchmarked, and the 3rd showed best results. So we chose that one.
1685             let mut tmp = mem::ManuallyDrop::new(ptr::read(&v[0]));
1686
1687             // Intermediate state of the insertion process is always tracked by `hole`, which
1688             // serves two purposes:
1689             // 1. Protects integrity of `v` from panics in `is_less`.
1690             // 2. Fills the remaining hole in `v` in the end.
1691             //
1692             // Panic safety:
1693             //
1694             // If `is_less` panics at any point during the process, `hole` will get dropped and
1695             // fill the hole in `v` with `tmp`, thus ensuring that `v` still holds every object it
1696             // initially held exactly once.
1697             let mut hole = InsertionHole {
1698                 src: &mut *tmp,
1699                 dest: &mut v[1],
1700             };
1701             ptr::copy_nonoverlapping(&v[1], &mut v[0], 1);
1702
1703             for i in 2..v.len() {
1704                 if !is_less(&v[i], &*tmp) {
1705                     break;
1706                 }
1707                 ptr::copy_nonoverlapping(&v[i], &mut v[i - 1], 1);
1708                 hole.dest = &mut v[i];
1709             }
1710             // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`.
1711         }
1712     }
1713
1714     // When dropped, copies from `src` into `dest`.
1715     struct InsertionHole<T> {
1716         src: *mut T,
1717         dest: *mut T,
1718     }
1719
1720     impl<T> Drop for InsertionHole<T> {
1721         fn drop(&mut self) {
1722             unsafe { ptr::copy_nonoverlapping(self.src, self.dest, 1); }
1723         }
1724     }
1725 }
1726
1727 /// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `buf` as temporary storage, and
1728 /// stores the result into `v[..]`.
1729 ///
1730 /// # Safety
1731 ///
1732 /// The two slices must be non-empty and `mid` must be in bounds. Buffer `buf` must be long enough
1733 /// to hold a copy of the shorter slice. Also, `T` must not be a zero-sized type.
1734 unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F)
1735     where F: FnMut(&T, &T) -> bool
1736 {
1737     let len = v.len();
1738     let v = v.as_mut_ptr();
1739     let v_mid = v.offset(mid as isize);
1740     let v_end = v.offset(len as isize);
1741
1742     // The merge process first copies the shorter run into `buf`. Then it traces the newly copied
1743     // run and the longer run forwards (or backwards), comparing their next unconsumed elements and
1744     // copying the lesser (or greater) one into `v`.
1745     //
1746     // As soon as the shorter run is fully consumed, the process is done. If the longer run gets
1747     // consumed first, then we must copy whatever is left of the shorter run into the remaining
1748     // hole in `v`.
1749     //
1750     // Intermediate state of the process is always tracked by `hole`, which serves two purposes:
1751     // 1. Protects integrity of `v` from panics in `is_less`.
1752     // 2. Fills the remaining hole in `v` if the longer run gets consumed first.
1753     //
1754     // Panic safety:
1755     //
1756     // If `is_less` panics at any point during the process, `hole` will get dropped and fill the
1757     // hole in `v` with the unconsumed range in `buf`, thus ensuring that `v` still holds every
1758     // object it initially held exactly once.
1759     let mut hole;
1760
1761     if mid <= len - mid {
1762         // The left run is shorter.
1763         ptr::copy_nonoverlapping(v, buf, mid);
1764         hole = MergeHole {
1765             start: buf,
1766             end: buf.offset(mid as isize),
1767             dest: v,
1768         };
1769
1770         // Initially, these pointers point to the beginnings of their arrays.
1771         let left = &mut hole.start;
1772         let mut right = v_mid;
1773         let out = &mut hole.dest;
1774
1775         while *left < hole.end && right < v_end {
1776             // Consume the lesser side.
1777             // If equal, prefer the left run to maintain stability.
1778             let to_copy = if is_less(&*right, &**left) {
1779                 get_and_increment(&mut right)
1780             } else {
1781                 get_and_increment(left)
1782             };
1783             ptr::copy_nonoverlapping(to_copy, get_and_increment(out), 1);
1784         }
1785     } else {
1786         // The right run is shorter.
1787         ptr::copy_nonoverlapping(v_mid, buf, len - mid);
1788         hole = MergeHole {
1789             start: buf,
1790             end: buf.offset((len - mid) as isize),
1791             dest: v_mid,
1792         };
1793
1794         // Initially, these pointers point past the ends of their arrays.
1795         let left = &mut hole.dest;
1796         let right = &mut hole.end;
1797         let mut out = v_end;
1798
1799         while v < *left && buf < *right {
1800             // Consume the greater side.
1801             // If equal, prefer the right run to maintain stability.
1802             let to_copy = if is_less(&*right.offset(-1), &*left.offset(-1)) {
1803                 decrement_and_get(left)
1804             } else {
1805                 decrement_and_get(right)
1806             };
1807             ptr::copy_nonoverlapping(to_copy, decrement_and_get(&mut out), 1);
1808         }
1809     }
1810     // Finally, `hole` gets dropped. If the shorter run was not fully consumed, whatever remains of
1811     // it will now be copied into the hole in `v`.
1812
1813     unsafe fn get_and_increment<T>(ptr: &mut *mut T) -> *mut T {
1814         let old = *ptr;
1815         *ptr = ptr.offset(1);
1816         old
1817     }
1818
1819     unsafe fn decrement_and_get<T>(ptr: &mut *mut T) -> *mut T {
1820         *ptr = ptr.offset(-1);
1821         *ptr
1822     }
1823
1824     // When dropped, copies the range `start..end` into `dest..`.
1825     struct MergeHole<T> {
1826         start: *mut T,
1827         end: *mut T,
1828         dest: *mut T,
1829     }
1830
1831     impl<T> Drop for MergeHole<T> {
1832         fn drop(&mut self) {
1833             // `T` is not a zero-sized type, so it's okay to divide by its size.
1834             let len = (self.end as usize - self.start as usize) / mem::size_of::<T>();
1835             unsafe { ptr::copy_nonoverlapping(self.start, self.dest, len); }
1836         }
1837     }
1838 }
1839
1840 /// This merge sort borrows some (but not all) ideas from TimSort, which is described in detail
1841 /// [here](http://svn.python.org/projects/python/trunk/Objects/listsort.txt).
1842 ///
1843 /// The algorithm identifies strictly descending and non-descending subsequences, which are called
1844 /// natural runs. There is a stack of pending runs yet to be merged. Each newly found run is pushed
1845 /// onto the stack, and then some pairs of adjacent runs are merged until these two invariants are
1846 /// satisfied:
1847 ///
1848 /// 1. for every `i` in `1..runs.len()`: `runs[i - 1].len > runs[i].len`
1849 /// 2. for every `i` in `2..runs.len()`: `runs[i - 2].len > runs[i - 1].len + runs[i].len`
1850 ///
1851 /// The invariants ensure that the total running time is `O(n log n)` worst-case.
1852 fn merge_sort<T, F>(v: &mut [T], mut is_less: F)
1853     where F: FnMut(&T, &T) -> bool
1854 {
1855     // Slices of up to this length get sorted using insertion sort.
1856     const MAX_INSERTION: usize = 20;
1857     // Very short runs are extended using insertion sort to span at least this many elements.
1858     const MIN_RUN: usize = 10;
1859
1860     // Sorting has no meaningful behavior on zero-sized types.
1861     if size_of::<T>() == 0 {
1862         return;
1863     }
1864
1865     let len = v.len();
1866
1867     // Short arrays get sorted in-place via insertion sort to avoid allocations.
1868     if len <= MAX_INSERTION {
1869         if len >= 2 {
1870             for i in (0..len-1).rev() {
1871                 insert_head(&mut v[i..], &mut is_less);
1872             }
1873         }
1874         return;
1875     }
1876
1877     // Allocate a buffer to use as scratch memory. We keep the length 0 so we can keep in it
1878     // shallow copies of the contents of `v` without risking the dtors running on copies if
1879     // `is_less` panics. When merging two sorted runs, this buffer holds a copy of the shorter run,
1880     // which will always have length at most `len / 2`.
1881     let mut buf = Vec::with_capacity(len / 2);
1882
1883     // In order to identify natural runs in `v`, we traverse it backwards. That might seem like a
1884     // strange decision, but consider the fact that merges more often go in the opposite direction
1885     // (forwards). According to benchmarks, merging forwards is slightly faster than merging
1886     // backwards. To conclude, identifying runs by traversing backwards improves performance.
1887     let mut runs = vec![];
1888     let mut end = len;
1889     while end > 0 {
1890         // Find the next natural run, and reverse it if it's strictly descending.
1891         let mut start = end - 1;
1892         if start > 0 {
1893             start -= 1;
1894             unsafe {
1895                 if is_less(v.get_unchecked(start + 1), v.get_unchecked(start)) {
1896                     while start > 0 && is_less(v.get_unchecked(start),
1897                                                v.get_unchecked(start - 1)) {
1898                         start -= 1;
1899                     }
1900                     v[start..end].reverse();
1901                 } else {
1902                     while start > 0 && !is_less(v.get_unchecked(start),
1903                                                 v.get_unchecked(start - 1)) {
1904                         start -= 1;
1905                     }
1906                 }
1907             }
1908         }
1909
1910         // Insert some more elements into the run if it's too short. Insertion sort is faster than
1911         // merge sort on short sequences, so this significantly improves performance.
1912         while start > 0 && end - start < MIN_RUN {
1913             start -= 1;
1914             insert_head(&mut v[start..end], &mut is_less);
1915         }
1916
1917         // Push this run onto the stack.
1918         runs.push(Run {
1919             start,
1920             len: end - start,
1921         });
1922         end = start;
1923
1924         // Merge some pairs of adjacent runs to satisfy the invariants.
1925         while let Some(r) = collapse(&runs) {
1926             let left = runs[r + 1];
1927             let right = runs[r];
1928             unsafe {
1929                 merge(&mut v[left.start .. right.start + right.len], left.len, buf.as_mut_ptr(),
1930                       &mut is_less);
1931             }
1932             runs[r] = Run {
1933                 start: left.start,
1934                 len: left.len + right.len,
1935             };
1936             runs.remove(r + 1);
1937         }
1938     }
1939
1940     // Finally, exactly one run must remain in the stack.
1941     debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len);
1942
1943     // Examines the stack of runs and identifies the next pair of runs to merge. More specifically,
1944     // if `Some(r)` is returned, that means `runs[r]` and `runs[r + 1]` must be merged next. If the
1945     // algorithm should continue building a new run instead, `None` is returned.
1946     //
1947     // TimSort is infamous for its buggy implementations, as described here:
1948     // http://envisage-project.eu/timsort-specification-and-verification/
1949     //
1950     // The gist of the story is: we must enforce the invariants on the top four runs on the stack.
1951     // Enforcing them on just top three is not sufficient to ensure that the invariants will still
1952     // hold for *all* runs in the stack.
1953     //
1954     // This function correctly checks invariants for the top four runs. Additionally, if the top
1955     // run starts at index 0, it will always demand a merge operation until the stack is fully
1956     // collapsed, in order to complete the sort.
1957     #[inline]
1958     fn collapse(runs: &[Run]) -> Option<usize> {
1959         let n = runs.len();
1960         if n >= 2 && (runs[n - 1].start == 0 ||
1961                       runs[n - 2].len <= runs[n - 1].len ||
1962                       (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len) ||
1963                       (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len)) {
1964             if n >= 3 && runs[n - 3].len < runs[n - 1].len {
1965                 Some(n - 3)
1966             } else {
1967                 Some(n - 2)
1968             }
1969         } else {
1970             None
1971         }
1972     }
1973
1974     #[derive(Clone, Copy)]
1975     struct Run {
1976         start: usize,
1977         len: usize,
1978     }
1979 }