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