src/liballoc/slice.rs

   1 //! A dynamically-sized view into a contiguous sequence, `[T]`.
   2 //!
   3 //! *[See also the slice primitive type](../../std/primitive.slice.html).*
   4 //!
   5 //! Slices are a view into a block of memory represented as a pointer and a
   6 //! length.
   7 //!
   8 //! ```
   9 //! // slicing a Vec
  10 //! let vec = vec![1, 2, 3];
  11 //! let int_slice = &vec[..];
  12 //! // coercing an array to a slice
  13 //! let str_slice: &[&str] = &["one", "two", "three"];
  14 //! ```
  15 //!
  16 //! Slices are either mutable or shared. The shared slice type is `&[T]`,
  17 //! while the mutable slice type is `&mut [T]`, where `T` represents the element
  18 //! type. For example, you can mutate the block of memory that a mutable slice
  19 //! points to:
  20 //!
  21 //! ```
  22 //! let x = &mut [1, 2, 3];
  23 //! x[1] = 7;
  24 //! assert_eq!(x, &[1, 7, 3]);
  25 //! ```
  26 //!
  27 //! Here are some of the things this module contains:
  28 //!
  29 //! ## Structs
  30 //!
  31 //! There are several structs that are useful for slices, such as [`Iter`], which
  32 //! represents iteration over a slice.
  33 //!
  34 //! ## Trait Implementations
  35 //!
  36 //! There are several implementations of common traits for slices. Some examples
  37 //! include:
  38 //!
  39 //! * [`Clone`]
  40 //! * [`Eq`], [`Ord`] - for slices whose element type are [`Eq`] or [`Ord`].
  41 //! * [`Hash`] - for slices whose element type is [`Hash`].
  42 //!
  43 //! ## Iteration
  44 //!
  45 //! The slices implement `IntoIterator`. The iterator yields references to the
  46 //! slice elements.
  47 //!
  48 //! ```
  49 //! let numbers = &[0, 1, 2];
  50 //! for n in numbers {
  51 //!     println!("{} is a number!", n);
  52 //! }
  53 //! ```
  54 //!
  55 //! The mutable slice yields mutable references to the elements:
  56 //!
  57 //! ```
  58 //! let mut scores = [7, 8, 9];
  59 //! for score in &mut scores[..] {
  60 //!     *score += 1;
  61 //! }
  62 //! ```
  63 //!
  64 //! This iterator yields mutable references to the slice's elements, so while
  65 //! the element type of the slice is `i32`, the element type of the iterator is
  66 //! `&mut i32`.
  67 //!
  68 //! * [`.iter`] and [`.iter_mut`] are the explicit methods to return the default
  69 //!   iterators.
  70 //! * Further methods that return iterators are [`.split`], [`.splitn`],
  71 //!   [`.chunks`], [`.windows`] and more.
  72 //!
  73 //! [`Clone`]: ../../std/clone/trait.Clone.html
  74 //! [`Eq`]: ../../std/cmp/trait.Eq.html
  75 //! [`Ord`]: ../../std/cmp/trait.Ord.html
  76 //! [`Iter`]: struct.Iter.html
  77 //! [`Hash`]: ../../std/hash/trait.Hash.html
  78 //! [`.iter`]: ../../std/primitive.slice.html#method.iter
  79 //! [`.iter_mut`]: ../../std/primitive.slice.html#method.iter_mut
  80 //! [`.split`]: ../../std/primitive.slice.html#method.split
  81 //! [`.splitn`]: ../../std/primitive.slice.html#method.splitn
  82 //! [`.chunks`]: ../../std/primitive.slice.html#method.chunks
  83 //! [`.windows`]: ../../std/primitive.slice.html#method.windows
  84 #![stable(feature = "rust1", since = "1.0.0")]
  85 // Many of the usings in this module are only used in the test configuration.
  86 // It's cleaner to just turn off the unused_imports warning than to fix them.
  87 #![cfg_attr(test, allow(unused_imports, dead_code))]
  88
  89 use core::borrow::{Borrow, BorrowMut};
  90 use core::cmp::Ordering::{self, Less};
  91 use core::mem::{self, size_of};
  92 use core::ptr;
  93
  94 use crate::borrow::ToOwned;
  95 use crate::boxed::Box;
  96 use crate::vec::Vec;
  97
  98 #[stable(feature = "slice_get_slice", since = "1.28.0")]
  99 pub use core::slice::SliceIndex;
 100 #[stable(feature = "from_ref", since = "1.28.0")]
 101 pub use core::slice::{from_mut, from_ref};
 102 #[stable(feature = "rust1", since = "1.0.0")]
 103 pub use core::slice::{from_raw_parts, from_raw_parts_mut};
 104 #[stable(feature = "rust1", since = "1.0.0")]
 105 pub use core::slice::{Chunks, Windows};
 106 #[stable(feature = "chunks_exact", since = "1.31.0")]
 107 pub use core::slice::{ChunksExact, ChunksExactMut};
 108 #[stable(feature = "rust1", since = "1.0.0")]
 109 pub use core::slice::{ChunksMut, Split, SplitMut};
 110 #[stable(feature = "rust1", since = "1.0.0")]
 111 pub use core::slice::{Iter, IterMut};
 112 #[stable(feature = "rchunks", since = "1.31.0")]
 113 pub use core::slice::{RChunks, RChunksExact, RChunksExactMut, RChunksMut};
 114 #[stable(feature = "slice_rsplit", since = "1.27.0")]
 115 pub use core::slice::{RSplit, RSplitMut};
 116 #[stable(feature = "rust1", since = "1.0.0")]
 117 pub use core::slice::{RSplitN, RSplitNMut, SplitN, SplitNMut};
 118
 119 ////////////////////////////////////////////////////////////////////////////////
 120 // Basic slice extension methods
 121 ////////////////////////////////////////////////////////////////////////////////
 122
 123 // HACK(japaric) needed for the implementation of `vec!` macro during testing
 124 // N.B., see the `hack` module in this file for more details.
 125 #[cfg(test)]
 126 pub use hack::into_vec;
 127
 128 // HACK(japaric) needed for the implementation of `Vec::clone` during testing
 129 // N.B., see the `hack` module in this file for more details.
 130 #[cfg(test)]
 131 pub use hack::to_vec;
 132
 133 // HACK(japaric): With cfg(test) `impl [T]` is not available, these three
 134 // functions are actually methods that are in `impl [T]` but not in
 135 // `core::slice::SliceExt` - we need to supply these functions for the
 136 // `test_permutations` test
 137 mod hack {
 138     use crate::boxed::Box;
 139     #[cfg(test)]
 140     use crate::string::ToString;
 141     use crate::vec::Vec;
 142
 143     // We shouldn't add inline attribute to this since this is used in
 144     // `vec!` macro mostly and causes perf regression. See #71204 for
 145     // discussion and perf results.
 146     pub fn into_vec<T>(b: Box<[T]>) -> Vec<T> {
 147         unsafe {
 148             let len = b.len();
 149             let b = Box::into_raw(b);
 150             Vec::from_raw_parts(b as *mut T, len, len)
 151         }
 152     }
 153
 154     #[inline]
 155     pub fn to_vec<T>(s: &[T]) -> Vec<T>
 156     where
 157         T: Clone,
 158     {
 159         let mut vector = Vec::with_capacity(s.len());
 160         vector.extend_from_slice(s);
 161         vector
 162     }
 163 }
 164
 165 #[lang = "slice_alloc"]
 166 #[cfg(not(test))]
 167 impl<T> [T] {
 168     /// Sorts the slice.
 169     ///
 170     /// This sort is stable (i.e., does not reorder equal elements) and `O(n * log(n))` worst-case.
 171     ///
 172     /// When applicable, unstable sorting is preferred because it is generally faster than stable
 173     /// sorting and it doesn't allocate auxiliary memory.
 174     /// See [`sort_unstable`](#method.sort_unstable).
 175     ///
 176     /// # Current implementation
 177     ///
 178     /// The current algorithm is an adaptive, iterative merge sort inspired by
 179     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
 180     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
 181     /// two or more sorted sequences concatenated one after another.
 182     ///
 183     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
 184     /// non-allocating insertion sort is used instead.
 185     ///
 186     /// # Examples
 187     ///
 188     /// ```
 189     /// let mut v = [-5, 4, 1, -3, 2];
 190     ///
 191     /// v.sort();
 192     /// assert!(v == [-5, -3, 1, 2, 4]);
 193     /// ```
 194     #[stable(feature = "rust1", since = "1.0.0")]
 195     #[inline]
 196     pub fn sort(&mut self)
 197     where
 198         T: Ord,
 199     {
 200         merge_sort(self, |a, b| a.lt(b));
 201     }
 202
 203     /// Sorts the slice with a comparator function.
 204     ///
 205     /// This sort is stable (i.e., does not reorder equal elements) and `O(n * log(n))` worst-case.
 206     ///
 207     /// The comparator function must define a total ordering for the elements in the slice. If
 208     /// the ordering is not total, the order of the elements is unspecified. An order is a
 209     /// total order if it is (for all `a`, `b` and `c`):
 210     ///
 211     /// * total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true, and
 212     /// * transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`.
 213     ///
 214     /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use
 215     /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`.
 216     ///
 217     /// ```
 218     /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0];
 219     /// floats.sort_by(|a, b| a.partial_cmp(b).unwrap());
 220     /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]);
 221     /// ```
 222     ///
 223     /// When applicable, unstable sorting is preferred because it is generally faster than stable
 224     /// sorting and it doesn't allocate auxiliary memory.
 225     /// See [`sort_unstable_by`](#method.sort_unstable_by).
 226     ///
 227     /// # Current implementation
 228     ///
 229     /// The current algorithm is an adaptive, iterative merge sort inspired by
 230     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
 231     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
 232     /// two or more sorted sequences concatenated one after another.
 233     ///
 234     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
 235     /// non-allocating insertion sort is used instead.
 236     ///
 237     /// # Examples
 238     ///
 239     /// ```
 240     /// let mut v = [5, 4, 1, 3, 2];
 241     /// v.sort_by(|a, b| a.cmp(b));
 242     /// assert!(v == [1, 2, 3, 4, 5]);
 243     ///
 244     /// // reverse sorting
 245     /// v.sort_by(|a, b| b.cmp(a));
 246     /// assert!(v == [5, 4, 3, 2, 1]);
 247     /// ```
 248     #[stable(feature = "rust1", since = "1.0.0")]
 249     #[inline]
 250     pub fn sort_by<F>(&mut self, mut compare: F)
 251     where
 252         F: FnMut(&T, &T) -> Ordering,
 253     {
 254         merge_sort(self, |a, b| compare(a, b) == Less);
 255     }
 256
 257     /// Sorts the slice with a key extraction function.
 258     ///
 259     /// This sort is stable (i.e., does not reorder equal elements) and `O(m * n * log(n))`
 260     /// worst-case, where the key function is `O(m)`.
 261     ///
 262     /// For expensive key functions (e.g. functions that are not simple property accesses or
 263     /// basic operations), [`sort_by_cached_key`](#method.sort_by_cached_key) is likely to be
 264     /// significantly faster, as it does not recompute element keys.
 265     ///
 266     /// When applicable, unstable sorting is preferred because it is generally faster than stable
 267     /// sorting and it doesn't allocate auxiliary memory.
 268     /// See [`sort_unstable_by_key`](#method.sort_unstable_by_key).
 269     ///
 270     /// # Current implementation
 271     ///
 272     /// The current algorithm is an adaptive, iterative merge sort inspired by
 273     /// [timsort](https://en.wikipedia.org/wiki/Timsort).
 274     /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
 275     /// two or more sorted sequences concatenated one after another.
 276     ///
 277     /// Also, it allocates temporary storage half the size of `self`, but for short slices a
 278     /// non-allocating insertion sort is used instead.
 279     ///
 280     /// # Examples
 281     ///
 282     /// ```
 283     /// let mut v = [-5i32, 4, 1, -3, 2];
 284     ///
 285     /// v.sort_by_key(|k| k.abs());
 286     /// assert!(v == [1, 2, -3, 4, -5]);
 287     /// ```
 288     #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
 289     #[inline]
 290     pub fn sort_by_key<K, F>(&mut self, mut f: F)
 291     where
 292         F: FnMut(&T) -> K,
 293         K: Ord,
 294     {
 295         merge_sort(self, |a, b| f(a).lt(&f(b)));
 296     }
 297
 298     /// Sorts the slice with a key extraction function.
 299     ///
 300     /// During sorting, the key function is called only once per element.
 301     ///
 302     /// This sort is stable (i.e., does not reorder equal elements) and `O(m * n + n * log(n))`
 303     /// worst-case, where the key function is `O(m)`.
 304     ///
 305     /// For simple key functions (e.g., functions that are property accesses or
 306     /// basic operations), [`sort_by_key`](#method.sort_by_key) is likely to be
 307     /// faster.
 308     ///
 309     /// # Current implementation
 310     ///
 311     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
 312     /// which combines the fast average case of randomized quicksort with the fast worst case of
 313     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
 314     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
 315     /// deterministic behavior.
 316     ///
 317     /// In the worst case, the algorithm allocates temporary storage in a `Vec<(K, usize)>` the
 318     /// length of the slice.
 319     ///
 320     /// # Examples
 321     ///
 322     /// ```
 323     /// let mut v = [-5i32, 4, 32, -3, 2];
 324     ///
 325     /// v.sort_by_cached_key(|k| k.to_string());
 326     /// assert!(v == [-3, -5, 2, 32, 4]);
 327     /// ```
 328     ///
 329     /// [pdqsort]: https://github.com/orlp/pdqsort
 330     #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")]
 331     #[inline]
 332     pub fn sort_by_cached_key<K, F>(&mut self, f: F)
 333     where
 334         F: FnMut(&T) -> K,
 335         K: Ord,
 336     {
 337         // Helper macro for indexing our vector by the smallest possible type, to reduce allocation.
 338         macro_rules! sort_by_key {
 339             ($t:ty, $slice:ident, $f:ident) => {{
 340                 let mut indices: Vec<_> =
 341                     $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect();
 342                 // The elements of `indices` are unique, as they are indexed, so any sort will be
 343                 // stable with respect to the original slice. We use `sort_unstable` here because
 344                 // it requires less memory allocation.
 345                 indices.sort_unstable();
 346                 for i in 0..$slice.len() {
 347                     let mut index = indices[i].1;
 348                     while (index as usize) < i {
 349                         index = indices[index as usize].1;
 350                     }
 351                     indices[i].1 = index;
 352                     $slice.swap(i, index as usize);
 353                 }
 354             }};
 355         }
 356
 357         let sz_u8 = mem::size_of::<(K, u8)>();
 358         let sz_u16 = mem::size_of::<(K, u16)>();
 359         let sz_u32 = mem::size_of::<(K, u32)>();
 360         let sz_usize = mem::size_of::<(K, usize)>();
 361
 362         let len = self.len();
 363         if len < 2 {
 364             return;
 365         }
 366         if sz_u8 < sz_u16 && len <= (u8::MAX as usize) {
 367             return sort_by_key!(u8, self, f);
 368         }
 369         if sz_u16 < sz_u32 && len <= (u16::MAX as usize) {
 370             return sort_by_key!(u16, self, f);
 371         }
 372         if sz_u32 < sz_usize && len <= (u32::MAX as usize) {
 373             return sort_by_key!(u32, self, f);
 374         }
 375         sort_by_key!(usize, self, f)
 376     }
 377
 378     /// Copies `self` into a new `Vec`.
 379     ///
 380     /// # Examples
 381     ///
 382     /// ```
 383     /// let s = [10, 40, 30];
 384     /// let x = s.to_vec();
 385     /// // Here, `s` and `x` can be modified independently.
 386     /// ```
 387     #[rustc_conversion_suggestion]
 388     #[stable(feature = "rust1", since = "1.0.0")]
 389     #[inline]
 390     pub fn to_vec(&self) -> Vec<T>
 391     where
 392         T: Clone,
 393     {
 394         // N.B., see the `hack` module in this file for more details.
 395         hack::to_vec(self)
 396     }
 397
 398     /// Converts `self` into a vector without clones or allocation.
 399     ///
 400     /// The resulting vector can be converted back into a box via
 401     /// `Vec<T>`'s `into_boxed_slice` method.
 402     ///
 403     /// # Examples
 404     ///
 405     /// ```
 406     /// let s: Box<[i32]> = Box::new([10, 40, 30]);
 407     /// let x = s.into_vec();
 408     /// // `s` cannot be used anymore because it has been converted into `x`.
 409     ///
 410     /// assert_eq!(x, vec![10, 40, 30]);
 411     /// ```
 412     #[stable(feature = "rust1", since = "1.0.0")]
 413     #[inline]
 414     pub fn into_vec(self: Box<Self>) -> Vec<T> {
 415         // N.B., see the `hack` module in this file for more details.
 416         hack::into_vec(self)
 417     }
 418
 419     /// Creates a vector by repeating a slice `n` times.
 420     ///
 421     /// # Panics
 422     ///
 423     /// This function will panic if the capacity would overflow.
 424     ///
 425     /// # Examples
 426     ///
 427     /// Basic usage:
 428     ///
 429     /// ```
 430     /// assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]);
 431     /// ```
 432     ///
 433     /// A panic upon overflow:
 434     ///
 435     /// ```should_panic
 436     /// // this will panic at runtime
 437     /// b"0123456789abcdef".repeat(usize::MAX);
 438     /// ```
 439     #[stable(feature = "repeat_generic_slice", since = "1.40.0")]
 440     pub fn repeat(&self, n: usize) -> Vec<T>
 441     where
 442         T: Copy,
 443     {
 444         if n == 0 {
 445             return Vec::new();
 446         }
 447
 448         // If `n` is larger than zero, it can be split as
 449         // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`.
 450         // `2^expn` is the number represented by the leftmost '1' bit of `n`,
 451         // and `rem` is the remaining part of `n`.
 452
 453         // Using `Vec` to access `set_len()`.
 454         let capacity = self.len().checked_mul(n).expect("capacity overflow");
 455         let mut buf = Vec::with_capacity(capacity);
 456
 457         // `2^expn` repetition is done by doubling `buf` `expn`-times.
 458         buf.extend(self);
 459         {
 460             let mut m = n >> 1;
 461             // If `m > 0`, there are remaining bits up to the leftmost '1'.
 462             while m > 0 {
 463                 // `buf.extend(buf)`:
 464                 unsafe {
 465                     ptr::copy_nonoverlapping(
 466                         buf.as_ptr(),
 467                         (buf.as_mut_ptr() as *mut T).add(buf.len()),
 468                         buf.len(),
 469                     );
 470                     // `buf` has capacity of `self.len() * n`.
 471                     let buf_len = buf.len();
 472                     buf.set_len(buf_len * 2);
 473                 }
 474
 475                 m >>= 1;
 476             }
 477         }
 478
 479         // `rem` (`= n - 2^expn`) repetition is done by copying
 480         // first `rem` repetitions from `buf` itself.
 481         let rem_len = capacity - buf.len(); // `self.len() * rem`
 482         if rem_len > 0 {
 483             // `buf.extend(buf[0 .. rem_len])`:
 484             unsafe {
 485                 // This is non-overlapping since `2^expn > rem`.
 486                 ptr::copy_nonoverlapping(
 487                     buf.as_ptr(),
 488                     (buf.as_mut_ptr() as *mut T).add(buf.len()),
 489                     rem_len,
 490                 );
 491                 // `buf.len() + rem_len` equals to `buf.capacity()` (`= self.len() * n`).
 492                 buf.set_len(capacity);
 493             }
 494         }
 495         buf
 496     }
 497
 498     /// Flattens a slice of `T` into a single value `Self::Output`.
 499     ///
 500     /// # Examples
 501     ///
 502     /// ```
 503     /// assert_eq!(["hello", "world"].concat(), "helloworld");
 504     /// assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
 505     /// ```
 506     #[stable(feature = "rust1", since = "1.0.0")]
 507     pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output
 508     where
 509         Self: Concat<Item>,
 510     {
 511         Concat::concat(self)
 512     }
 513
 514     /// Flattens a slice of `T` into a single value `Self::Output`, placing a
 515     /// given separator between each.
 516     ///
 517     /// # Examples
 518     ///
 519     /// ```
 520     /// assert_eq!(["hello", "world"].join(" "), "hello world");
 521     /// assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]);
 522     /// assert_eq!([[1, 2], [3, 4]].join(&[0, 0][..]), [1, 2, 0, 0, 3, 4]);
 523     /// ```
 524     #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
 525     pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
 526     where
 527         Self: Join<Separator>,
 528     {
 529         Join::join(self, sep)
 530     }
 531
 532     /// Flattens a slice of `T` into a single value `Self::Output`, placing a
 533     /// given separator between each.
 534     ///
 535     /// # Examples
 536     ///
 537     /// ```
 538     /// # #![allow(deprecated)]
 539     /// assert_eq!(["hello", "world"].connect(" "), "hello world");
 540     /// assert_eq!([[1, 2], [3, 4]].connect(&0), [1, 2, 0, 3, 4]);
 541     /// ```
 542     #[stable(feature = "rust1", since = "1.0.0")]
 543     #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")]
 544     pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
 545     where
 546         Self: Join<Separator>,
 547     {
 548         Join::join(self, sep)
 549     }
 550 }
 551
 552 #[lang = "slice_u8_alloc"]
 553 #[cfg(not(test))]
 554 impl [u8] {
 555     /// Returns a vector containing a copy of this slice where each byte
 556     /// is mapped to its ASCII upper case equivalent.
 557     ///
 558     /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
 559     /// but non-ASCII letters are unchanged.
 560     ///
 561     /// To uppercase the value in-place, use [`make_ascii_uppercase`].
 562     ///
 563     /// [`make_ascii_uppercase`]: #method.make_ascii_uppercase
 564     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
 565     #[inline]
 566     pub fn to_ascii_uppercase(&self) -> Vec<u8> {
 567         let mut me = self.to_vec();
 568         me.make_ascii_uppercase();
 569         me
 570     }
 571
 572     /// Returns a vector containing a copy of this slice where each byte
 573     /// is mapped to its ASCII lower case equivalent.
 574     ///
 575     /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
 576     /// but non-ASCII letters are unchanged.
 577     ///
 578     /// To lowercase the value in-place, use [`make_ascii_lowercase`].
 579     ///
 580     /// [`make_ascii_lowercase`]: #method.make_ascii_lowercase
 581     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
 582     #[inline]
 583     pub fn to_ascii_lowercase(&self) -> Vec<u8> {
 584         let mut me = self.to_vec();
 585         me.make_ascii_lowercase();
 586         me
 587     }
 588 }
 589
 590 ////////////////////////////////////////////////////////////////////////////////
 591 // Extension traits for slices over specific kinds of data
 592 ////////////////////////////////////////////////////////////////////////////////
 593
 594 /// Helper trait for [`[T]::concat`](../../std/primitive.slice.html#method.concat).
 595 ///
 596 /// Note: the `Item` type parameter is not used in this trait,
 597 /// but it allows impls to be more generic.
 598 /// Without it, we get this error:
 599 ///
 600 /// ```error
 601 /// error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predica
 602 ///    --> src/liballoc/slice.rs:608:6
 603 ///     |
 604 /// 608 | impl<T: Clone, V: Borrow<[T]>> Concat for [V] {
 605 ///     |      ^ unconstrained type parameter
 606 /// ```
 607 ///
 608 /// This is because there could exist `V` types with multiple `Borrow<[_]>` impls,
 609 /// such that multiple `T` types would apply:
 610 ///
 611 /// ```
 612 /// # #[allow(dead_code)]
 613 /// pub struct Foo(Vec<u32>, Vec<String>);
 614 ///
 615 /// impl std::borrow::Borrow<[u32]> for Foo {
 616 ///     fn borrow(&self) -> &[u32] { &self.0 }
 617 /// }
 618 ///
 619 /// impl std::borrow::Borrow<[String]> for Foo {
 620 ///     fn borrow(&self) -> &[String] { &self.1 }
 621 /// }
 622 /// ```
 623 #[unstable(feature = "slice_concat_trait", issue = "27747")]
 624 pub trait Concat<Item: ?Sized> {
 625     #[unstable(feature = "slice_concat_trait", issue = "27747")]
 626     /// The resulting type after concatenation
 627     type Output;
 628
 629     /// Implementation of [`[T]::concat`](../../std/primitive.slice.html#method.concat)
 630     #[unstable(feature = "slice_concat_trait", issue = "27747")]
 631     fn concat(slice: &Self) -> Self::Output;
 632 }
 633
 634 /// Helper trait for [`[T]::join`](../../std/primitive.slice.html#method.join)
 635 #[unstable(feature = "slice_concat_trait", issue = "27747")]
 636 pub trait Join<Separator> {
 637     #[unstable(feature = "slice_concat_trait", issue = "27747")]
 638     /// The resulting type after concatenation
 639     type Output;
 640
 641     /// Implementation of [`[T]::join`](../../std/primitive.slice.html#method.join)
 642     #[unstable(feature = "slice_concat_trait", issue = "27747")]
 643     fn join(slice: &Self, sep: Separator) -> Self::Output;
 644 }
 645
 646 #[unstable(feature = "slice_concat_ext", issue = "27747")]
 647 impl<T: Clone, V: Borrow<[T]>> Concat<T> for [V] {
 648     type Output = Vec<T>;
 649
 650     fn concat(slice: &Self) -> Vec<T> {
 651         let size = slice.iter().map(|slice| slice.borrow().len()).sum();
 652         let mut result = Vec::with_capacity(size);
 653         for v in slice {
 654             result.extend_from_slice(v.borrow())
 655         }
 656         result
 657     }
 658 }
 659
 660 #[unstable(feature = "slice_concat_ext", issue = "27747")]
 661 impl<T: Clone, V: Borrow<[T]>> Join<&T> for [V] {
 662     type Output = Vec<T>;
 663
 664     fn join(slice: &Self, sep: &T) -> Vec<T> {
 665         let mut iter = slice.iter();
 666         let first = match iter.next() {
 667             Some(first) => first,
 668             None => return vec![],
 669         };
 670         let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + slice.len() - 1;
 671         let mut result = Vec::with_capacity(size);
 672         result.extend_from_slice(first.borrow());
 673
 674         for v in iter {
 675             result.push(sep.clone());
 676             result.extend_from_slice(v.borrow())
 677         }
 678         result
 679     }
 680 }
 681
 682 #[unstable(feature = "slice_concat_ext", issue = "27747")]
 683 impl<T: Clone, V: Borrow<[T]>> Join<&[T]> for [V] {
 684     type Output = Vec<T>;
 685
 686     fn join(slice: &Self, sep: &[T]) -> Vec<T> {
 687         let mut iter = slice.iter();
 688         let first = match iter.next() {
 689             Some(first) => first,
 690             None => return vec![],
 691         };
 692         let size =
 693             slice.iter().map(|v| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1);
 694         let mut result = Vec::with_capacity(size);
 695         result.extend_from_slice(first.borrow());
 696
 697         for v in iter {
 698             result.extend_from_slice(sep);
 699             result.extend_from_slice(v.borrow())
 700         }
 701         result
 702     }
 703 }
 704
 705 ////////////////////////////////////////////////////////////////////////////////
 706 // Standard trait implementations for slices
 707 ////////////////////////////////////////////////////////////////////////////////
 708
 709 #[stable(feature = "rust1", since = "1.0.0")]
 710 impl<T> Borrow<[T]> for Vec<T> {
 711     fn borrow(&self) -> &[T] {
 712         &self[..]
 713     }
 714 }
 715
 716 #[stable(feature = "rust1", since = "1.0.0")]
 717 impl<T> BorrowMut<[T]> for Vec<T> {
 718     fn borrow_mut(&mut self) -> &mut [T] {
 719         &mut self[..]
 720     }
 721 }
 722
 723 #[stable(feature = "rust1", since = "1.0.0")]
 724 impl<T: Clone> ToOwned for [T] {
 725     type Owned = Vec<T>;
 726     #[cfg(not(test))]
 727     fn to_owned(&self) -> Vec<T> {
 728         self.to_vec()
 729     }
 730
 731     #[cfg(test)]
 732     fn to_owned(&self) -> Vec<T> {
 733         hack::to_vec(self)
 734     }
 735
 736     fn clone_into(&self, target: &mut Vec<T>) {
 737         // drop anything in target that will not be overwritten
 738         target.truncate(self.len());
 739
 740         // target.len <= self.len due to the truncate above, so the
 741         // slices here are always in-bounds.
 742         let (init, tail) = self.split_at(target.len());
 743
 744         // reuse the contained values' allocations/resources.
 745         target.clone_from_slice(init);
 746         target.extend_from_slice(tail);
 747     }
 748 }
 749
 750 ////////////////////////////////////////////////////////////////////////////////
 751 // Sorting
 752 ////////////////////////////////////////////////////////////////////////////////
 753
 754 /// Inserts `v[0]` into pre-sorted sequence `v[1..]` so that whole `v[..]` becomes sorted.
 755 ///
 756 /// This is the integral subroutine of insertion sort.
 757 fn insert_head<T, F>(v: &mut [T], is_less: &mut F)
 758 where
 759     F: FnMut(&T, &T) -> bool,
 760 {
 761     if v.len() >= 2 && is_less(&v[1], &v[0]) {
 762         unsafe {
 763             // There are three ways to implement insertion here:
 764             //
 765             // 1. Swap adjacent elements until the first one gets to its final destination.
 766             //    However, this way we copy data around more than is necessary. If elements are big
 767             //    structures (costly to copy), this method will be slow.
 768             //
 769             // 2. Iterate until the right place for the first element is found. Then shift the
 770             //    elements succeeding it to make room for it and finally place it into the
 771             //    remaining hole. This is a good method.
 772             //
 773             // 3. Copy the first element into a temporary variable. Iterate until the right place
 774             //    for it is found. As we go along, copy every traversed element into the slot
 775             //    preceding it. Finally, copy data from the temporary variable into the remaining
 776             //    hole. This method is very good. Benchmarks demonstrated slightly better
 777             //    performance than with the 2nd method.
 778             //
 779             // All methods were benchmarked, and the 3rd showed best results. So we chose that one.
 780             let mut tmp = mem::ManuallyDrop::new(ptr::read(&v[0]));
 781
 782             // Intermediate state of the insertion process is always tracked by `hole`, which
 783             // serves two purposes:
 784             // 1. Protects integrity of `v` from panics in `is_less`.
 785             // 2. Fills the remaining hole in `v` in the end.
 786             //
 787             // Panic safety:
 788             //
 789             // If `is_less` panics at any point during the process, `hole` will get dropped and
 790             // fill the hole in `v` with `tmp`, thus ensuring that `v` still holds every object it
 791             // initially held exactly once.
 792             let mut hole = InsertionHole { src: &mut *tmp, dest: &mut v[1] };
 793             ptr::copy_nonoverlapping(&v[1], &mut v[0], 1);
 794
 795             for i in 2..v.len() {
 796                 if !is_less(&v[i], &*tmp) {
 797                     break;
 798                 }
 799                 ptr::copy_nonoverlapping(&v[i], &mut v[i - 1], 1);
 800                 hole.dest = &mut v[i];
 801             }
 802             // `hole` gets dropped and thus copies `tmp` into the remaining hole in `v`.
 803         }
 804     }
 805
 806     // When dropped, copies from `src` into `dest`.
 807     struct InsertionHole<T> {
 808         src: *mut T,
 809         dest: *mut T,
 810     }
 811
 812     impl<T> Drop for InsertionHole<T> {
 813         fn drop(&mut self) {
 814             unsafe {
 815                 ptr::copy_nonoverlapping(self.src, self.dest, 1);
 816             }
 817         }
 818     }
 819 }
 820
 821 /// Merges non-decreasing runs `v[..mid]` and `v[mid..]` using `buf` as temporary storage, and
 822 /// stores the result into `v[..]`.
 823 ///
 824 /// # Safety
 825 ///
 826 /// The two slices must be non-empty and `mid` must be in bounds. Buffer `buf` must be long enough
 827 /// to hold a copy of the shorter slice. Also, `T` must not be a zero-sized type.
 828 unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F)
 829 where
 830     F: FnMut(&T, &T) -> bool,
 831 {
 832     let len = v.len();
 833     let v = v.as_mut_ptr();
 834     let v_mid = v.add(mid);
 835     let v_end = v.add(len);
 836
 837     // The merge process first copies the shorter run into `buf`. Then it traces the newly copied
 838     // run and the longer run forwards (or backwards), comparing their next unconsumed elements and
 839     // copying the lesser (or greater) one into `v`.
 840     //
 841     // As soon as the shorter run is fully consumed, the process is done. If the longer run gets
 842     // consumed first, then we must copy whatever is left of the shorter run into the remaining
 843     // hole in `v`.
 844     //
 845     // Intermediate state of the process is always tracked by `hole`, which serves two purposes:
 846     // 1. Protects integrity of `v` from panics in `is_less`.
 847     // 2. Fills the remaining hole in `v` if the longer run gets consumed first.
 848     //
 849     // Panic safety:
 850     //
 851     // If `is_less` panics at any point during the process, `hole` will get dropped and fill the
 852     // hole in `v` with the unconsumed range in `buf`, thus ensuring that `v` still holds every
 853     // object it initially held exactly once.
 854     let mut hole;
 855
 856     if mid <= len - mid {
 857         // The left run is shorter.
 858         ptr::copy_nonoverlapping(v, buf, mid);
 859         hole = MergeHole { start: buf, end: buf.add(mid), dest: v };
 860
 861         // Initially, these pointers point to the beginnings of their arrays.
 862         let left = &mut hole.start;
 863         let mut right = v_mid;
 864         let out = &mut hole.dest;
 865
 866         while *left < hole.end && right < v_end {
 867             // Consume the lesser side.
 868             // If equal, prefer the left run to maintain stability.
 869             let to_copy = if is_less(&*right, &**left) {
 870                 get_and_increment(&mut right)
 871             } else {
 872                 get_and_increment(left)
 873             };
 874             ptr::copy_nonoverlapping(to_copy, get_and_increment(out), 1);
 875         }
 876     } else {
 877         // The right run is shorter.
 878         ptr::copy_nonoverlapping(v_mid, buf, len - mid);
 879         hole = MergeHole { start: buf, end: buf.add(len - mid), dest: v_mid };
 880
 881         // Initially, these pointers point past the ends of their arrays.
 882         let left = &mut hole.dest;
 883         let right = &mut hole.end;
 884         let mut out = v_end;
 885
 886         while v < *left && buf < *right {
 887             // Consume the greater side.
 888             // If equal, prefer the right run to maintain stability.
 889             let to_copy = if is_less(&*right.offset(-1), &*left.offset(-1)) {
 890                 decrement_and_get(left)
 891             } else {
 892                 decrement_and_get(right)
 893             };
 894             ptr::copy_nonoverlapping(to_copy, decrement_and_get(&mut out), 1);
 895         }
 896     }
 897     // Finally, `hole` gets dropped. If the shorter run was not fully consumed, whatever remains of
 898     // it will now be copied into the hole in `v`.
 899
 900     unsafe fn get_and_increment<T>(ptr: &mut *mut T) -> *mut T {
 901         let old = *ptr;
 902         *ptr = ptr.offset(1);
 903         old
 904     }
 905
 906     unsafe fn decrement_and_get<T>(ptr: &mut *mut T) -> *mut T {
 907         *ptr = ptr.offset(-1);
 908         *ptr
 909     }
 910
 911     // When dropped, copies the range `start..end` into `dest..`.
 912     struct MergeHole<T> {
 913         start: *mut T,
 914         end: *mut T,
 915         dest: *mut T,
 916     }
 917
 918     impl<T> Drop for MergeHole<T> {
 919         fn drop(&mut self) {
 920             // `T` is not a zero-sized type, so it's okay to divide by its size.
 921             let len = (self.end as usize - self.start as usize) / mem::size_of::<T>();
 922             unsafe {
 923                 ptr::copy_nonoverlapping(self.start, self.dest, len);
 924             }
 925         }
 926     }
 927 }
 928
 929 /// This merge sort borrows some (but not all) ideas from TimSort, which is described in detail
 930 /// [here](http://svn.python.org/projects/python/trunk/Objects/listsort.txt).
 931 ///
 932 /// The algorithm identifies strictly descending and non-descending subsequences, which are called
 933 /// natural runs. There is a stack of pending runs yet to be merged. Each newly found run is pushed
 934 /// onto the stack, and then some pairs of adjacent runs are merged until these two invariants are
 935 /// satisfied:
 936 ///
 937 /// 1. for every `i` in `1..runs.len()`: `runs[i - 1].len > runs[i].len`
 938 /// 2. for every `i` in `2..runs.len()`: `runs[i - 2].len > runs[i - 1].len + runs[i].len`
 939 ///
 940 /// The invariants ensure that the total running time is `O(n * log(n))` worst-case.
 941 fn merge_sort<T, F>(v: &mut [T], mut is_less: F)
 942 where
 943     F: FnMut(&T, &T) -> bool,
 944 {
 945     // Slices of up to this length get sorted using insertion sort.
 946     const MAX_INSERTION: usize = 20;
 947     // Very short runs are extended using insertion sort to span at least this many elements.
 948     const MIN_RUN: usize = 10;
 949
 950     // Sorting has no meaningful behavior on zero-sized types.
 951     if size_of::<T>() == 0 {
 952         return;
 953     }
 954
 955     let len = v.len();
 956
 957     // Short arrays get sorted in-place via insertion sort to avoid allocations.
 958     if len <= MAX_INSERTION {
 959         if len >= 2 {
 960             for i in (0..len - 1).rev() {
 961                 insert_head(&mut v[i..], &mut is_less);
 962             }
 963         }
 964         return;
 965     }
 966
 967     // Allocate a buffer to use as scratch memory. We keep the length 0 so we can keep in it
 968     // shallow copies of the contents of `v` without risking the dtors running on copies if
 969     // `is_less` panics. When merging two sorted runs, this buffer holds a copy of the shorter run,
 970     // which will always have length at most `len / 2`.
 971     let mut buf = Vec::with_capacity(len / 2);
 972
 973     // In order to identify natural runs in `v`, we traverse it backwards. That might seem like a
 974     // strange decision, but consider the fact that merges more often go in the opposite direction
 975     // (forwards). According to benchmarks, merging forwards is slightly faster than merging
 976     // backwards. To conclude, identifying runs by traversing backwards improves performance.
 977     let mut runs = vec![];
 978     let mut end = len;
 979     while end > 0 {
 980         // Find the next natural run, and reverse it if it's strictly descending.
 981         let mut start = end - 1;
 982         if start > 0 {
 983             start -= 1;
 984             unsafe {
 985                 if is_less(v.get_unchecked(start + 1), v.get_unchecked(start)) {
 986                     while start > 0 && is_less(v.get_unchecked(start), v.get_unchecked(start - 1)) {
 987                         start -= 1;
 988                     }
 989                     v[start..end].reverse();
 990                 } else {
 991                     while start > 0 && !is_less(v.get_unchecked(start), v.get_unchecked(start - 1))
 992                     {
 993                         start -= 1;
 994                     }
 995                 }
 996             }
 997         }
 998
 999         // Insert some more elements into the run if it's too short. Insertion sort is faster than
1000         // merge sort on short sequences, so this significantly improves performance.
1001         while start > 0 && end - start < MIN_RUN {
1002             start -= 1;
1003             insert_head(&mut v[start..end], &mut is_less);
1004         }
1005
1006         // Push this run onto the stack.
1007         runs.push(Run { start, len: end - start });
1008         end = start;
1009
1010         // Merge some pairs of adjacent runs to satisfy the invariants.
1011         while let Some(r) = collapse(&runs) {
1012             let left = runs[r + 1];
1013             let right = runs[r];
1014             unsafe {
1015                 merge(
1016                     &mut v[left.start..right.start + right.len],
1017                     left.len,
1018                     buf.as_mut_ptr(),
1019                     &mut is_less,
1020                 );
1021             }
1022             runs[r] = Run { start: left.start, len: left.len + right.len };
1023             runs.remove(r + 1);
1024         }
1025     }
1026
1027     // Finally, exactly one run must remain in the stack.
1028     debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len);
1029
1030     // Examines the stack of runs and identifies the next pair of runs to merge. More specifically,
1031     // if `Some(r)` is returned, that means `runs[r]` and `runs[r + 1]` must be merged next. If the
1032     // algorithm should continue building a new run instead, `None` is returned.
1033     //
1034     // TimSort is infamous for its buggy implementations, as described here:
1035     // http://envisage-project.eu/timsort-specification-and-verification/
1036     //
1037     // The gist of the story is: we must enforce the invariants on the top four runs on the stack.
1038     // Enforcing them on just top three is not sufficient to ensure that the invariants will still
1039     // hold for *all* runs in the stack.
1040     //
1041     // This function correctly checks invariants for the top four runs. Additionally, if the top
1042     // run starts at index 0, it will always demand a merge operation until the stack is fully
1043     // collapsed, in order to complete the sort.
1044     #[inline]
1045     fn collapse(runs: &[Run]) -> Option<usize> {
1046         let n = runs.len();
1047         if n >= 2
1048             && (runs[n - 1].start == 0
1049                 || runs[n - 2].len <= runs[n - 1].len
1050                 || (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len)
1051                 || (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len))
1052         {
1053             if n >= 3 && runs[n - 3].len < runs[n - 1].len { Some(n - 3) } else { Some(n - 2) }
1054         } else {
1055             None
1056         }
1057     }
1058
1059     #[derive(Clone, Copy)]
1060     struct Run {
1061         start: usize,
1062         len: usize,
1063     }
1064 }