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