slice.rs - source
Description: Source of the Rust file `library/alloc/src/slice.rs`.

#
alloc/
slice.rs

    1//! Utilities for the slice primitive type.
    2//!
    3//! *[See also the slice primitive type](slice).*
    4//!
    5//! Most of the structs in this module are iterator types which can only be created
    6//! using a certain function. For example, `slice.iter()` yields an [`Iter`].
    7//!
    8//! A few functions are provided to create a slice from a value reference
    9//! or from a raw pointer.
    10#![stable(feature = "rust1", since = "1.0.0")]
    11
    12use core::borrow::{Borrow, BorrowMut};
    13#[cfg(not(no_global_oom_handling))]
    14use core::clone::TrivialClone;
    15#[cfg(not(no_global_oom_handling))]
    16use core::cmp::Ordering::{self, Less};
    17#[cfg(not(no_global_oom_handling))]
    18use core::mem::MaybeUninit;
    19#[cfg(not(no_global_oom_handling))]
    20use core::ptr;
    21#[stable(feature = "array_windows", since = "1.94.0")]
    22pub use core::slice::ArrayWindows;
    23#[stable(feature = "inherent_ascii_escape", since = "1.60.0")]
    24pub use core::slice::EscapeAscii;
    25#[stable(feature = "get_many_mut", since = "1.86.0")]
    26pub use core::slice::GetDisjointMutError;
    27#[stable(feature = "slice_get_slice", since = "1.28.0")]
    28pub use core::slice::SliceIndex;
    29#[cfg(not(no_global_oom_handling))]
    30use core::slice::sort;
    31#[stable(feature = "slice_group_by", since = "1.77.0")]
    32pub use core::slice::{ChunkBy, ChunkByMut};
    33#[stable(feature = "rust1", since = "1.0.0")]
    34pub use core::slice::{Chunks, Windows};
    35#[stable(feature = "chunks_exact", since = "1.31.0")]
    36pub use core::slice::{ChunksExact, ChunksExactMut};
    37#[stable(feature = "rust1", since = "1.0.0")]
    38pub use core::slice::{ChunksMut, Split, SplitMut};
    39#[stable(feature = "rust1", since = "1.0.0")]
    40pub use core::slice::{Iter, IterMut};
    41#[stable(feature = "rchunks", since = "1.31.0")]
    42pub use core::slice::{RChunks, RChunksExact, RChunksExactMut, RChunksMut};
    43#[stable(feature = "slice_rsplit", since = "1.27.0")]
    44pub use core::slice::{RSplit, RSplitMut};
    45#[stable(feature = "rust1", since = "1.0.0")]
    46pub use core::slice::{RSplitN, RSplitNMut, SplitN, SplitNMut};
    47#[stable(feature = "split_inclusive", since = "1.51.0")]
    48pub use core::slice::{SplitInclusive, SplitInclusiveMut};
    49#[stable(feature = "from_ref", since = "1.28.0")]
    50pub use core::slice::{from_mut, from_ref};
    51#[unstable(feature = "slice_from_ptr_range", issue = "89792")]
    52pub use core::slice::{from_mut_ptr_range, from_ptr_range};
    53#[stable(feature = "rust1", since = "1.0.0")]
    54pub use core::slice::{from_raw_parts, from_raw_parts_mut};
    55#[unstable(feature = "slice_range", issue = "76393")]
    56pub use core::slice::{range, try_range};
    57
    58////////////////////////////////////////////////////////////////////////////////
    59// Basic slice extension methods
    60////////////////////////////////////////////////////////////////////////////////
    61use crate::alloc::Allocator;
    62#[cfg(not(no_global_oom_handling))]
    63use crate::alloc::Global;
    64#[cfg(not(no_global_oom_handling))]
    65use crate::borrow::ToOwned;
    66use crate::boxed::Box;
    67use crate::vec::Vec;
    68
    69impl<T> [T] {
    70    /// Sorts the slice in ascending order, preserving initial order of equal elements.
    71    ///
    72    /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*))
    73    /// worst-case.
    74    ///
    75    /// If the implementation of [`Ord`] for `T` does not implement a [total order], the function
    76    /// may panic; even if the function exits normally, the resulting order of elements in the slice
    77    /// is unspecified. See also the note on panicking below.
    78    ///
    79    /// When applicable, unstable sorting is preferred because it is generally faster than stable
    80    /// sorting and it doesn't allocate auxiliary memory. See
    81    /// [`sort_unstable`](slice::sort_unstable). The exception are partially sorted slices, which
    82    /// may be better served with `slice::sort`.
    83    ///
    84    /// Sorting types that only implement [`PartialOrd`] such as [`f32`] and [`f64`] require
    85    /// additional precautions. For example, `f32::NAN != f32::NAN`, which doesn't fulfill the
    86    /// reflexivity requirement of [`Ord`]. By using an alternative comparison function with
    87    /// `slice::sort_by` such as [`f32::total_cmp`] or [`f64::total_cmp`] that defines a [total
    88    /// order] users can sort slices containing floating-point values. Alternatively, if all values
    89    /// in the slice are guaranteed to be in a subset for which [`PartialOrd::partial_cmp`] forms a
    90    /// [total order], it's possible to sort the slice with `sort_by(|a, b|
    91    /// a.partial_cmp(b).unwrap())`.
    92    ///
    93    /// # Current implementation
    94    ///
    95    /// The current implementation is based on [driftsort] by Orson Peters and Lukas Bergdoll, which
    96    /// combines the fast average case of quicksort with the fast worst case and partial run
    97    /// detection of mergesort, achieving linear time on fully sorted and reversed inputs. On inputs
    98    /// with k distinct elements, the expected time to sort the data is *O*(*n* \* log(*k*)).
    99    ///
    100    /// The auxiliary memory allocation behavior depends on the input length. Short slices are
    101    /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it
    102    /// clamps at `self.len() / 2`.
    103    ///
    104    /// # Panics
    105    ///
    106    /// May panic if the implementation of [`Ord`] for `T` does not implement a [total order], or if
    107    /// the [`Ord`] implementation itself panics.
    108    ///
    109    /// All safe functions on slices preserve the invariant that even if the function panics, all
    110    /// original elements will remain in the slice and any possible modifications via interior
    111    /// mutability are observed in the input. This ensures that recovery code (for instance inside
    112    /// of a `Drop` or following a `catch_unwind`) will still have access to all the original
    113    /// elements. For instance, if the slice belongs to a `Vec`, the `Vec::drop` method will be able
    114    /// to dispose of all contained elements.
    115    ///
    116    /// # Examples
    117    ///
    118    /// ```
    119    /// let mut v = [4, -5, 1, -3, 2];
    120    ///
    121    /// v.sort();
    122    /// assert_eq!(v, [-5, -3, 1, 2, 4]);
    123    /// ```
    124    ///
    125    /// [driftsort]: https://github.com/Voultapher/driftsort
    126    /// [total order]: https://en.wikipedia.org/wiki/Total_order
    127    #[cfg(not(no_global_oom_handling))]
    128    #[rustc_allow_incoherent_impl]
    129    #[stable(feature = "rust1", since = "1.0.0")]
    130    #[inline]
    131    pub fn sort(&mut self)
    132    where
    133        T: Ord,
    134    {
    135        stable_sort(self, T::lt);
    136    }
    137
    138    /// Sorts the slice in ascending order with a comparison function, preserving initial order of
    139    /// equal elements.
    140    ///
    141    /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*))
    142    /// worst-case.
    143    ///
    144    /// If the comparison function `compare` does not implement a [total order], the function may
    145    /// panic; even if the function exits normally, the resulting order of elements in the slice is
    146    /// unspecified. See also the note on panicking below.
    147    ///
    148    /// For example `|a, b| (a - b).cmp(a)` is a comparison function that is neither transitive nor
    149    /// reflexive nor total, `a < b < c < a` with `a = 1, b = 2, c = 3`. For more information and
    150    /// examples see the [`Ord`] documentation.
    151    ///
    152    /// # Current implementation
    153    ///
    154    /// The current implementation is based on [driftsort] by Orson Peters and Lukas Bergdoll, which
    155    /// combines the fast average case of quicksort with the fast worst case and partial run
    156    /// detection of mergesort, achieving linear time on fully sorted and reversed inputs. On inputs
    157    /// with k distinct elements, the expected time to sort the data is *O*(*n* \* log(*k*)).
    158    ///
    159    /// The auxiliary memory allocation behavior depends on the input length. Short slices are
    160    /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it
    161    /// clamps at `self.len() / 2`.
    162    ///
    163    /// # Panics
    164    ///
    165    /// May panic if `compare` does not implement a [total order], or if `compare` itself panics.
    166    ///
    167    /// All safe functions on slices preserve the invariant that even if the function panics, all
    168    /// original elements will remain in the slice and any possible modifications via interior
    169    /// mutability are observed in the input. This ensures that recovery code (for instance inside
    170    /// of a `Drop` or following a `catch_unwind`) will still have access to all the original
    171    /// elements. For instance, if the slice belongs to a `Vec`, the `Vec::drop` method will be able
    172    /// to dispose of all contained elements.
    173    ///
    174    /// # Examples
    175    ///
    176    /// ```
    177    /// let mut v = [4, -5, 1, -3, 2];
    178    /// v.sort_by(|a, b| a.cmp(b));
    179    /// assert_eq!(v, [-5, -3, 1, 2, 4]);
    180    ///
    181    /// // reverse sorting
    182    /// v.sort_by(|a, b| b.cmp(a));
    183    /// assert_eq!(v, [4, 2, 1, -3, -5]);
    184    /// ```
    185    ///
    186    /// [driftsort]: https://github.com/Voultapher/driftsort
    187    /// [total order]: https://en.wikipedia.org/wiki/Total_order
    188    #[cfg(not(no_global_oom_handling))]
    189    #[rustc_allow_incoherent_impl]
    190    #[stable(feature = "rust1", since = "1.0.0")]
    191    #[inline]
    192    pub fn sort_by<F>(&mut self, mut compare: F)
    193    where
    194        F: FnMut(&T, &T) -> Ordering,
    195    {
    196        stable_sort(self, |a, b| compare(a, b) == Less);
    197    }
    198
    199    /// Sorts the slice in ascending order with a key extraction function, preserving initial order
    200    /// of equal elements.
    201    ///
    202    /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* \* log(*n*))
    203    /// worst-case, where the key function is *O*(*m*).
    204    ///
    205    /// If the implementation of [`Ord`] for `K` does not implement a [total order], the function
    206    /// may panic; even if the function exits normally, the resulting order of elements in the slice
    207    /// is unspecified. See also the note on panicking below.
    208    ///
    209    /// # Current implementation
    210    ///
    211    /// The current implementation is based on [driftsort] by Orson Peters and Lukas Bergdoll, which
    212    /// combines the fast average case of quicksort with the fast worst case and partial run
    213    /// detection of mergesort, achieving linear time on fully sorted and reversed inputs. On inputs
    214    /// with k distinct elements, the expected time to sort the data is *O*(*n* \* log(*k*)).
    215    ///
    216    /// The auxiliary memory allocation behavior depends on the input length. Short slices are
    217    /// handled without allocation, medium sized slices allocate `self.len()` and beyond that it
    218    /// clamps at `self.len() / 2`.
    219    ///
    220    /// # Panics
    221    ///
    222    /// May panic if the implementation of [`Ord`] for `K` does not implement a [total order], or if
    223    /// the [`Ord`] implementation or the key-function `f` panics.
    224    ///
    225    /// All safe functions on slices preserve the invariant that even if the function panics, all
    226    /// original elements will remain in the slice and any possible modifications via interior
    227    /// mutability are observed in the input. This ensures that recovery code (for instance inside
    228    /// of a `Drop` or following a `catch_unwind`) will still have access to all the original
    229    /// elements. For instance, if the slice belongs to a `Vec`, the `Vec::drop` method will be able
    230    /// to dispose of all contained elements.
    231    ///
    232    /// # Examples
    233    ///
    234    /// ```
    235    /// let mut v = [4i32, -5, 1, -3, 2];
    236    ///
    237    /// v.sort_by_key(|k| k.abs());
    238    /// assert_eq!(v, [1, 2, -3, 4, -5]);
    239    /// ```
    240    ///
    241    /// [driftsort]: https://github.com/Voultapher/driftsort
    242    /// [total order]: https://en.wikipedia.org/wiki/Total_order
    243    #[cfg(not(no_global_oom_handling))]
    244    #[rustc_allow_incoherent_impl]
    245    #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
    246    #[inline]
    247    pub fn sort_by_key<K, F>(&mut self, mut f: F)
    248    where
    249        F: FnMut(&T) -> K,
    250        K: Ord,
    251    {
    252        stable_sort(self, |a, b| f(a).lt(&f(b)));
    253    }
    254
    255    /// Sorts the slice in ascending order with a key extraction function, preserving initial order
    256    /// of equal elements.
    257    ///
    258    /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* + *n* \*
    259    /// log(*n*)) worst-case, where the key function is *O*(*m*).
    260    ///
    261    /// During sorting, the key function is called at most once per element, by using temporary
    262    /// storage to remember the results of key evaluation. The order of calls to the key function is
    263    /// unspecified and may change in future versions of the standard library.
    264    ///
    265    /// If the implementation of [`Ord`] for `K` does not implement a [total order], the function
    266    /// may panic; even if the function exits normally, the resulting order of elements in the slice
    267    /// is unspecified. See also the note on panicking below.
    268    ///
    269    /// For simple key functions (e.g., functions that are property accesses or basic operations),
    270    /// [`sort_by_key`](slice::sort_by_key) is likely to be faster.
    271    ///
    272    /// # Current implementation
    273    ///
    274    /// The current implementation is based on [instruction-parallel-network sort][ipnsort] by Lukas
    275    /// Bergdoll, which combines the fast average case of randomized quicksort with the fast worst
    276    /// case of heapsort, while achieving linear time on fully sorted and reversed inputs. And
    277    /// *O*(*k* \* log(*n*)) where *k* is the number of distinct elements in the input. It leverages
    278    /// superscalar out-of-order execution capabilities commonly found in CPUs, to efficiently
    279    /// perform the operation.
    280    ///
    281    /// In the worst case, the algorithm allocates temporary storage in a `Vec<(K, usize)>` the
    282    /// length of the slice.
    283    ///
    284    /// # Panics
    285    ///
    286    /// May panic if the implementation of [`Ord`] for `K` does not implement a [total order], or if
    287    /// the [`Ord`] implementation panics.
    288    ///
    289    /// All safe functions on slices preserve the invariant that even if the function panics, all
    290    /// original elements will remain in the slice and any possible modifications via interior
    291    /// mutability are observed in the input. This ensures that recovery code (for instance inside
    292    /// of a `Drop` or following a `catch_unwind`) will still have access to all the original
    293    /// elements. For instance, if the slice belongs to a `Vec`, the `Vec::drop` method will be able
    294    /// to dispose of all contained elements.
    295    ///
    296    /// # Examples
    297    ///
    298    /// ```
    299    /// let mut v = [4i32, -5, 1, -3, 2, 10];
    300    ///
    301    /// // Strings are sorted by lexicographical order.
    302    /// v.sort_by_cached_key(|k| k.to_string());
    303    /// assert_eq!(v, [-3, -5, 1, 10, 2, 4]);
    304    /// ```
    305    ///
    306    /// [ipnsort]: https://github.com/Voultapher/sort-research-rs/tree/main/ipnsort
    307    /// [total order]: https://en.wikipedia.org/wiki/Total_order
    308    #[cfg(not(no_global_oom_handling))]
    309    #[rustc_allow_incoherent_impl]
    310    #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")]
    311    #[inline]
    312    pub fn sort_by_cached_key<K, F>(&mut self, f: F)
    313    where
    314        F: FnMut(&T) -> K,
    315        K: Ord,
    316    {
    317        // Helper macro for indexing our vector by the smallest possible type, to reduce allocation.
    318        macro_rules! sort_by_key {
    319            ($t:ty, $slice:ident, $f:ident) => {{
    320                let mut indices: Vec<_> =
    321                    $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect();
    322                // The elements of `indices` are unique, as they are indexed, so any sort will be
    323                // stable with respect to the original slice. We use `sort_unstable` here because
    324                // it requires no memory allocation.
    325                indices.sort_unstable();
    326                for i in 0..$slice.len() {
    327                    let mut index = indices[i].1;
    328                    while (index as usize) < i {
    329                        index = indices[index as usize].1;
    330                    }
    331                    indices[i].1 = index;
    332                    $slice.swap(i, index as usize);
    333                }
    334            }};
    335        }
    336
    337        let len = self.len();
    338        if len < 2 {
    339            return;
    340        }
    341
    342        // Avoids binary-size usage in cases where the alignment doesn't work out to make this
    343        // beneficial or on 32-bit platforms.
    344        let is_using_u32_as_idx_type_helpful =
    345            const { size_of::<(K, u32)>() < size_of::<(K, usize)>() };
    346
    347        // It's possible to instantiate this for u8 and u16 but, doing so is very wasteful in terms
    348        // of compile-times and binary-size, the peak saved heap memory for u16 is (u8 + u16) -> 4
    349        // bytes * u16::MAX vs (u8 + u32) -> 8 bytes * u16::MAX, the saved heap memory is at peak
    350        // ~262KB.
    351        if is_using_u32_as_idx_type_helpful && len <= (u32::MAX as usize) {
    352            return sort_by_key!(u32, self, f);
    353        }
    354
    355        sort_by_key!(usize, self, f)
    356    }
    357
    358    /// Copies `self` into a new `Vec`.
    359    ///
    360    /// # Examples
    361    ///
    362    /// ```
    363    /// let s = [10, 40, 30];
    364    /// let x = s.to_vec();
    365    /// // Here, `s` and `x` can be modified independently.
    366    /// ```
    367    #[cfg(not(no_global_oom_handling))]
    368    #[rustc_allow_incoherent_impl]
    369    #[rustc_conversion_suggestion]
    370    #[stable(feature = "rust1", since = "1.0.0")]
    371    #[inline]
    372    pub fn to_vec(&self) -> Vec<T>
    373    where
    374        T: Clone,
    375    {
    376        self.to_vec_in(Global)
    377    }
    378
    379    /// Copies `self` into a new `Vec` with an allocator.
    380    ///
    381    /// # Examples
    382    ///
    383    /// ```
    384    /// #![feature(allocator_api)]
    385    ///
    386    /// use std::alloc::System;
    387    ///
    388    /// let s = [10, 40, 30];
    389    /// let x = s.to_vec_in(System);
    390    /// // Here, `s` and `x` can be modified independently.
    391    /// ```
    392    #[cfg(not(no_global_oom_handling))]
    393    #[rustc_allow_incoherent_impl]
    394    #[inline]
    395    #[unstable(feature = "allocator_api", issue = "32838")]
    396    pub fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A>
    397    where
    398        T: Clone,
    399    {
    400        return T::to_vec(self, alloc);
    401
    402        trait ConvertVec {
    403            fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A>
    404            where
    405                Self: Sized;
    406        }
    407
    408        impl<T: Clone> ConvertVec for T {
    409            #[inline]
    410            default fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {
    411                struct DropGuard<'a, T, A: Allocator> {
    412                    vec: &'a mut Vec<T, A>,
    413                    num_init: usize,
    414                }
    415                impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
    416                    #[inline]
    417                    fn drop(&mut self) {
    418                        // SAFETY:
    419                        // items were marked initialized in the loop below
    420                        unsafe {
    421                            self.vec.set_len(self.num_init);
    422                        }
    423                    }
    424                }
    425                let mut vec = Vec::with_capacity_in(s.len(), alloc);
    426                let mut guard = DropGuard { vec: &mut vec, num_init: 0 };
    427                let slots = guard.vec.spare_capacity_mut();
    428                // .take(slots.len()) is necessary for LLVM to remove bounds checks
    429                // and has better codegen than zip.
    430                for (i, b) in s.iter().enumerate().take(slots.len()) {
    431                    guard.num_init = i;
    432                    slots[i].write(b.clone());
    433                }
    434                core::mem::forget(guard);
    435                // SAFETY:
    436                // the vec was allocated and initialized above to at least this length.
    437                unsafe {
    438                    vec.set_len(s.len());
    439                }
    440                vec
    441            }
    442        }
    443
    444        impl<T: TrivialClone> ConvertVec for T {
    445            #[inline]
    446            fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {
    447                let mut v = Vec::with_capacity_in(s.len(), alloc);
    448                // SAFETY:
    449                // allocated above with the capacity of `s`, and initialize to `s.len()` in
    450                // ptr::copy_to_non_overlapping below.
    451                unsafe {
    452                    s.as_ptr().copy_to_nonoverlapping(v.as_mut_ptr(), s.len());
    453                    v.set_len(s.len());
    454                }
    455                v
    456            }
    457        }
    458    }
    459
    460    /// Converts `self` into a vector without clones or allocation.
    461    ///
    462    /// The resulting vector can be converted back into a box via
    463    /// `Vec<T>`'s `into_boxed_slice` method.
    464    ///
    465    /// # Examples
    466    ///
    467    /// ```
    468    /// let s: Box<[i32]> = Box::new([10, 40, 30]);
    469    /// let x = s.into_vec();
    470    /// // `s` cannot be used anymore because it has been converted into `x`.
    471    ///
    472    /// assert_eq!(x, vec![10, 40, 30]);
    473    /// ```
    474    #[rustc_allow_incoherent_impl]
    475    #[stable(feature = "rust1", since = "1.0.0")]
    476    #[inline]
    477    #[rustc_diagnostic_item = "slice_into_vec"]
    478    pub fn into_vec<A: Allocator>(self: Box<Self, A>) -> Vec<T, A> {
    479        unsafe {
    480            let len = self.len();
    481            let (b, alloc) = Box::into_raw_with_allocator(self);
    482            Vec::from_raw_parts_in(b as *mut T, len, len, alloc)
    483        }
    484    }
    485
    486    /// Creates a vector by copying a slice `n` times.
    487    ///
    488    /// # Panics
    489    ///
    490    /// This function will panic if the capacity would overflow.
    491    ///
    492    /// # Examples
    493    ///
    494    /// ```
    495    /// assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]);
    496    /// ```
    497    ///
    498    /// A panic upon overflow:
    499    ///
    500    /// ```should_panic
    501    /// // this will panic at runtime
    502    /// b"0123456789abcdef".repeat(usize::MAX);
    503    /// ```
    504    #[rustc_allow_incoherent_impl]
    505    #[cfg(not(no_global_oom_handling))]
    506    #[stable(feature = "repeat_generic_slice", since = "1.40.0")]
    507    pub fn repeat(&self, n: usize) -> Vec<T>
    508    where
    509        T: Copy,
    510    {
    511        if n == 0 {
    512            return Vec::new();
    513        }
    514
    515        // If `n` is larger than zero, it can be split as
    516        // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`.
    517        // `2^expn` is the number represented by the leftmost '1' bit of `n`,
    518        // and `rem` is the remaining part of `n`.
    519
    520        // Using `Vec` to access `set_len()`.
    521        let capacity = self.len().checked_mul(n).expect("capacity overflow");
    522        let mut buf = Vec::with_capacity(capacity);
    523
    524        // `2^expn` repetition is done by doubling `buf` `expn`-times.
    525        buf.extend(self);
    526        {
    527            let mut m = n >> 1;
    528            // If `m > 0`, there are remaining bits up to the leftmost '1'.
    529            while m > 0 {
    530                // `buf.extend(buf)`:
    531                unsafe {
    532                    ptr::copy_nonoverlapping::<T>(
    533                        buf.as_ptr(),
    534                        (buf.as_mut_ptr()).add(buf.len()),
    535                        buf.len(),
    536                    );
    537                    // `buf` has capacity of `self.len() * n`.
    538                    let buf_len = buf.len();
    539                    buf.set_len(buf_len * 2);
    540                }
    541
    542                m >>= 1;
    543            }
    544        }
    545
    546        // `rem` (`= n - 2^expn`) repetition is done by copying
    547        // first `rem` repetitions from `buf` itself.
    548        let rem_len = capacity - buf.len(); // `self.len() * rem`
    549        if rem_len > 0 {
    550            // `buf.extend(buf[0 .. rem_len])`:
    551            unsafe {
    552                // This is non-overlapping since `2^expn > rem`.
    553                ptr::copy_nonoverlapping::<T>(
    554                    buf.as_ptr(),
    555                    (buf.as_mut_ptr()).add(buf.len()),
    556                    rem_len,
    557                );
    558                // `buf.len() + rem_len` equals to `buf.capacity()` (`= self.len() * n`).
    559                buf.set_len(capacity);
    560            }
    561        }
    562        buf
    563    }
    564
    565    /// Flattens a slice of `T` into a single value `Self::Output`.
    566    ///
    567    /// # Examples
    568    ///
    569    /// ```
    570    /// assert_eq!(["hello", "world"].concat(), "helloworld");
    571    /// assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
    572    /// ```
    573    #[rustc_allow_incoherent_impl]
    574    #[stable(feature = "rust1", since = "1.0.0")]
    575    pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output
    576    where
    577        Self: Concat<Item>,
    578    {
    579        Concat::concat(self)
    580    }
    581
    582    /// Flattens a slice of `T` into a single value `Self::Output`, placing a
    583    /// given separator between each.
    584    ///
    585    /// # Examples
    586    ///
    587    /// ```
    588    /// assert_eq!(["hello", "world"].join(" "), "hello world");
    589    /// assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]);
    590    /// assert_eq!([[1, 2], [3, 4]].join(&[0, 0][..]), [1, 2, 0, 0, 3, 4]);
    591    /// ```
    592    #[rustc_allow_incoherent_impl]
    593    #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
    594    pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
    595    where
    596        Self: Join<Separator>,
    597    {
    598        Join::join(self, sep)
    599    }
    600
    601    /// Flattens a slice of `T` into a single value `Self::Output`, placing a
    602    /// given separator between each.
    603    ///
    604    /// # Examples
    605    ///
    606    /// ```
    607    /// # #![allow(deprecated)]
    608    /// assert_eq!(["hello", "world"].connect(" "), "hello world");
    609    /// assert_eq!([[1, 2], [3, 4]].connect(&0), [1, 2, 0, 3, 4]);
    610    /// ```
    611    #[rustc_allow_incoherent_impl]
    612    #[stable(feature = "rust1", since = "1.0.0")]
    613    #[deprecated(since = "1.3.0", note = "renamed to join", suggestion = "join")]
    614    pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
    615    where
    616        Self: Join<Separator>,
    617    {
    618        Join::join(self, sep)
    619    }
    620}
    621
    622impl [u8] {
    623    /// Returns a vector containing a copy of this slice where each byte
    624    /// is mapped to its ASCII upper case equivalent.
    625    ///
    626    /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
    627    /// but non-ASCII letters are unchanged.
    628    ///
    629    /// To uppercase the value in-place, use [`make_ascii_uppercase`].
    630    ///
    631    /// [`make_ascii_uppercase`]: slice::make_ascii_uppercase
    632    #[cfg(not(no_global_oom_handling))]
    633    #[rustc_allow_incoherent_impl]
    634    #[must_use = "this returns the uppercase bytes as a new Vec, \
    635                  without modifying the original"]
    636    #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
    637    #[inline]
    638    pub fn to_ascii_uppercase(&self) -> Vec<u8> {
    639        let mut me = self.to_vec();
    640        me.make_ascii_uppercase();
    641        me
    642    }
    643
    644    /// Returns a vector containing a copy of this slice where each byte
    645    /// is mapped to its ASCII lower case equivalent.
    646    ///
    647    /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
    648    /// but non-ASCII letters are unchanged.
    649    ///
    650    /// To lowercase the value in-place, use [`make_ascii_lowercase`].
    651    ///
    652    /// [`make_ascii_lowercase`]: slice::make_ascii_lowercase
    653    #[cfg(not(no_global_oom_handling))]
    654    #[rustc_allow_incoherent_impl]
    655    #[must_use = "this returns the lowercase bytes as a new Vec, \
    656                  without modifying the original"]
    657    #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
    658    #[inline]
    659    pub fn to_ascii_lowercase(&self) -> Vec<u8> {
    660        let mut me = self.to_vec();
    661        me.make_ascii_lowercase();
    662        me
    663    }
    664}
    665
    666////////////////////////////////////////////////////////////////////////////////
    667// Extension traits for slices over specific kinds of data
    668////////////////////////////////////////////////////////////////////////////////
    669
    670/// Helper trait for [`[T]::concat`](slice::concat).
    671///
    672/// Note: the `Item` type parameter is not used in this trait,
    673/// but it allows impls to be more generic.
    674/// Without it, we get this error:
    675///
    676/// ```error
    677/// error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predica
    678///    --> library/alloc/src/slice.rs:608:6
    679///     |
    680/// 608 | impl<T: Clone, V: Borrow<[T]>> Concat for [V] {
    681///     |      ^ unconstrained type parameter
    682/// ```
    683///
    684/// This is because there could exist `V` types with multiple `Borrow<[_]>` impls,
    685/// such that multiple `T` types would apply:
    686///
    687/// ```
    688/// # #[allow(dead_code)]
    689/// pub struct Foo(Vec<u32>, Vec<String>);
    690///
    691/// impl std::borrow::Borrow<[u32]> for Foo {
    692///     fn borrow(&self) -> &[u32] { &self.0 }
    693/// }
    694///
    695/// impl std::borrow::Borrow<[String]> for Foo {
    696///     fn borrow(&self) -> &[String] { &self.1 }
    697/// }
    698/// ```
    699#[unstable(feature = "slice_concat_trait", issue = "27747")]
    700pub trait Concat<Item: ?Sized> {
    701    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    702    /// The resulting type after concatenation
    703    type Output;
    704
    705    /// Implementation of [`[T]::concat`](slice::concat)
    706    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    707    fn concat(slice: &Self) -> Self::Output;
    708}
    709
    710/// Helper trait for [`[T]::join`](slice::join)
    711#[unstable(feature = "slice_concat_trait", issue = "27747")]
    712pub trait Join<Separator> {
    713    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    714    /// The resulting type after concatenation
    715    type Output;
    716
    717    /// Implementation of [`[T]::join`](slice::join)
    718    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    719    fn join(slice: &Self, sep: Separator) -> Self::Output;
    720}
    721
    722#[cfg(not(no_global_oom_handling))]
    723#[unstable(feature = "slice_concat_ext", issue = "27747")]
    724impl<T: Clone, V: Borrow<[T]>> Concat<T> for [V] {
    725    type Output = Vec<T>;
    726
    727    fn concat(slice: &Self) -> Vec<T> {
    728        let size = slice.iter().map(|slice| slice.borrow().len()).sum();
    729        let mut result = Vec::with_capacity(size);
    730        for v in slice {
    731            result.extend_from_slice(v.borrow())
    732        }
    733        result
    734    }
    735}
    736
    737#[cfg(not(no_global_oom_handling))]
    738#[unstable(feature = "slice_concat_ext", issue = "27747")]
    739impl<T: Clone, V: Borrow<[T]>> Join<&T> for [V] {
    740    type Output = Vec<T>;
    741
    742    fn join(slice: &Self, sep: &T) -> Vec<T> {
    743        let mut iter = slice.iter();
    744        let first = match iter.next() {
    745            Some(first) => first,
    746            None => return vec![],
    747        };
    748        let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + slice.len() - 1;
    749        let mut result = Vec::with_capacity(size);
    750        result.extend_from_slice(first.borrow());
    751
    752        for v in iter {
    753            result.push(sep.clone());
    754            result.extend_from_slice(v.borrow())
    755        }
    756        result
    757    }
    758}
    759
    760#[cfg(not(no_global_oom_handling))]
    761#[unstable(feature = "slice_concat_ext", issue = "27747")]
    762impl<T: Clone, V: Borrow<[T]>> Join<&[T]> for [V] {
    763    type Output = Vec<T>;
    764
    765    fn join(slice: &Self, sep: &[T]) -> Vec<T> {
    766        let mut iter = slice.iter();
    767        let first = match iter.next() {
    768            Some(first) => first,
    769            None => return vec![],
    770        };
    771        let size =
    772            slice.iter().map(|v| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1);
    773        let mut result = Vec::with_capacity(size);
    774        result.extend_from_slice(first.borrow());
    775
    776        for v in iter {
    777            result.extend_from_slice(sep);
    778            result.extend_from_slice(v.borrow())
    779        }
    780        result
    781    }
    782}
    783
    784////////////////////////////////////////////////////////////////////////////////
    785// Standard trait implementations for slices
    786////////////////////////////////////////////////////////////////////////////////
    787
    788#[stable(feature = "rust1", since = "1.0.0")]
    789impl<T, A: Allocator> Borrow<[T]> for Vec<T, A> {
    790    fn borrow(&self) -> &[T] {
    791        &self[..]
    792    }
    793}
    794
    795#[stable(feature = "rust1", since = "1.0.0")]
    796impl<T, A: Allocator> BorrowMut<[T]> for Vec<T, A> {
    797    fn borrow_mut(&mut self) -> &mut [T] {
    798        &mut self[..]
    799    }
    800}
    801
    802// Specializable trait for implementing ToOwned::clone_into. This is
    803// public in the crate and has the Allocator parameter so that
    804// vec::clone_from use it too.
    805#[cfg(not(no_global_oom_handling))]
    806pub(crate) trait SpecCloneIntoVec<T, A: Allocator> {
    807    fn clone_into(&self, target: &mut Vec<T, A>);
    808}
    809
    810#[cfg(not(no_global_oom_handling))]
    811impl<T: Clone, A: Allocator> SpecCloneIntoVec<T, A> for [T] {
    812    default fn clone_into(&self, target: &mut Vec<T, A>) {
    813        // drop anything in target that will not be overwritten
    814        target.truncate(self.len());
    815
    816        // target.len <= self.len due to the truncate above, so the
    817        // slices here are always in-bounds.
    818        let (init, tail) = self.split_at(target.len());
    819
    820        // reuse the contained values' allocations/resources.
    821        target.clone_from_slice(init);
    822        target.extend_from_slice(tail);
    823    }
    824}
    825
    826#[cfg(not(no_global_oom_handling))]
    827impl<T: TrivialClone, A: Allocator> SpecCloneIntoVec<T, A> for [T] {
    828    fn clone_into(&self, target: &mut Vec<T, A>) {
    829        target.clear();
    830        target.extend_from_slice(self);
    831    }
    832}
    833
    834#[cfg(not(no_global_oom_handling))]
    835#[stable(feature = "rust1", since = "1.0.0")]
    836impl<T: Clone> ToOwned for [T] {
    837    type Owned = Vec<T>;
    838
    839    fn to_owned(&self) -> Vec<T> {
    840        self.to_vec()
    841    }
    842
    843    fn clone_into(&self, target: &mut Vec<T>) {
    844        SpecCloneIntoVec::clone_into(self, target);
    845    }
    846}
    847
    848////////////////////////////////////////////////////////////////////////////////
    849// Sorting
    850////////////////////////////////////////////////////////////////////////////////
    851
    852#[inline]
    853#[cfg(not(no_global_oom_handling))]
    854fn stable_sort<T, F>(v: &mut [T], mut is_less: F)
    855where
    856    F: FnMut(&T, &T) -> bool,
    857{
    858    sort::stable::sort::<T, F, Vec<T>>(v, &mut is_less);
    859}
    860
    861#[cfg(not(no_global_oom_handling))]
    862#[unstable(issue = "none", feature = "std_internals")]
    863impl<T> sort::stable::BufGuard<T> for Vec<T> {
    864    fn with_capacity(capacity: usize) -> Self {
    865        Vec::with_capacity(capacity)
    866    }
    867
    868    fn as_uninit_slice_mut(&mut self) -> &mut [MaybeUninit<T>] {
    869        self.spare_capacity_mut()
    870    }
    871}