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