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, SizedTypeProperties};
20#[cfg(not(no_global_oom_handling))]
21use core::ptr;
22#[cfg(not(no_global_oom_handling))]
23use core::slice::sort;
24
25use crate::alloc::Allocator;
26#[cfg(not(no_global_oom_handling))]
27use crate::alloc::{self, Global};
28#[cfg(not(no_global_oom_handling))]
29use crate::borrow::ToOwned;
30use crate::boxed::Box;
31use crate::vec::Vec;
32
33#[cfg(test)]
34mod tests;
35
36#[unstable(feature = "array_chunks", issue = "74985")]
37pub use core::slice::ArrayChunks;
38#[unstable(feature = "array_chunks", issue = "74985")]
39pub use core::slice::ArrayChunksMut;
40#[unstable(feature = "array_windows", issue = "75027")]
41pub use core::slice::ArrayWindows;
42#[stable(feature = "inherent_ascii_escape", since = "1.60.0")]
43pub use core::slice::EscapeAscii;
44#[stable(feature = "slice_get_slice", since = "1.28.0")]
45pub use core::slice::SliceIndex;
46#[stable(feature = "from_ref", since = "1.28.0")]
47pub use core::slice::{from_mut, from_ref};
48#[unstable(feature = "slice_from_ptr_range", issue = "89792")]
49pub use core::slice::{from_mut_ptr_range, from_ptr_range};
50#[stable(feature = "rust1", since = "1.0.0")]
51pub use core::slice::{from_raw_parts, from_raw_parts_mut};
52#[unstable(feature = "slice_range", issue = "76393")]
53pub use core::slice::{range, try_range};
54#[stable(feature = "slice_group_by", since = "1.77.0")]
55pub use core::slice::{ChunkBy, ChunkByMut};
56#[stable(feature = "rust1", since = "1.0.0")]
57pub use core::slice::{Chunks, Windows};
58#[stable(feature = "chunks_exact", since = "1.31.0")]
59pub use core::slice::{ChunksExact, ChunksExactMut};
60#[stable(feature = "rust1", since = "1.0.0")]
61pub use core::slice::{ChunksMut, Split, SplitMut};
62#[stable(feature = "rust1", since = "1.0.0")]
63pub use core::slice::{Iter, IterMut};
64#[stable(feature = "rchunks", since = "1.31.0")]
65pub use core::slice::{RChunks, RChunksExact, RChunksExactMut, RChunksMut};
66#[stable(feature = "slice_rsplit", since = "1.27.0")]
67pub use core::slice::{RSplit, RSplitMut};
68#[stable(feature = "rust1", since = "1.0.0")]
69pub use core::slice::{RSplitN, RSplitNMut, SplitN, SplitNMut};
70#[stable(feature = "split_inclusive", since = "1.51.0")]
71pub use core::slice::{SplitInclusive, SplitInclusiveMut};
72
73////////////////////////////////////////////////////////////////////////////////
74// Basic slice extension methods
75////////////////////////////////////////////////////////////////////////////////
76
77// HACK(japaric) needed for the implementation of `vec!` macro during testing
78// N.B., see the `hack` module in this file for more details.
79#[cfg(test)]
80pub use hack::into_vec;
81
82// HACK(japaric) needed for the implementation of `Vec::clone` during testing
83// N.B., see the `hack` module in this file for more details.
84#[cfg(test)]
85pub use hack::to_vec;
86
87// HACK(japaric): With cfg(test) `impl [T]` is not available, these three
88// functions are actually methods that are in `impl [T]` but not in
89// `core::slice::SliceExt` - we need to supply these functions for the
90// `test_permutations` test
91pub(crate) mod hack {
92 use core::alloc::Allocator;
93
94 use crate::boxed::Box;
95 use crate::vec::Vec;
96
97 // We shouldn't add inline attribute to this since this is used in
98 // `vec!` macro mostly and causes perf regression. See #71204 for
99 // discussion and perf results.
100 pub fn into_vec<T, A: Allocator>(b: Box<[T], A>) -> Vec<T, A> {
101 unsafe {
102 let len = b.len();
103 let (b, alloc) = Box::into_raw_with_allocator(b);
104 Vec::from_raw_parts_in(b as *mut T, len, len, alloc)
105 }
106 }
107
108 #[cfg(not(no_global_oom_handling))]
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.
178 ///
179 /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-case.
180 ///
181 /// When applicable, unstable sorting is preferred because it is generally faster than stable
182 /// sorting and it doesn't allocate auxiliary memory.
183 /// See [`sort_unstable`](slice::sort_unstable).
184 ///
185 /// # Current implementation
186 ///
187 /// The current algorithm is an adaptive, iterative merge sort inspired by
188 /// [timsort](https://en.wikipedia.org/wiki/Timsort).
189 /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
190 /// two or more sorted sequences concatenated one after another.
191 ///
192 /// Also, it allocates temporary storage half the size of `self`, but for short slices a
193 /// non-allocating insertion sort is used instead.
194 ///
195 /// # Examples
196 ///
197 /// ```
198 /// let mut v = [-5, 4, 1, -3, 2];
199 ///
200 /// v.sort();
201 /// assert!(v == [-5, -3, 1, 2, 4]);
202 /// ```
203 #[cfg(not(no_global_oom_handling))]
204 #[rustc_allow_incoherent_impl]
205 #[stable(feature = "rust1", since = "1.0.0")]
206 #[inline]
207 pub fn sort(&mut self)
208 where
209 T: Ord,
210 {
211 stable_sort(self, T::lt);
212 }
213
214 /// Sorts the slice with a comparator function.
215 ///
216 /// This sort is stable (i.e., does not reorder equal elements) and *O*(*n* \* log(*n*)) worst-case.
217 ///
218 /// The comparator function must define a total ordering for the elements in the slice. If
219 /// the ordering is not total, the order of the elements is unspecified. An order is a
220 /// total order if it is (for all `a`, `b` and `c`):
221 ///
222 /// * total and antisymmetric: exactly one of `a < b`, `a == b` or `a > b` is true, and
223 /// * transitive, `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`.
224 ///
225 /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use
226 /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`.
227 ///
228 /// ```
229 /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0];
230 /// floats.sort_by(|a, b| a.partial_cmp(b).unwrap());
231 /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]);
232 /// ```
233 ///
234 /// When applicable, unstable sorting is preferred because it is generally faster than stable
235 /// sorting and it doesn't allocate auxiliary memory.
236 /// See [`sort_unstable_by`](slice::sort_unstable_by).
237 ///
238 /// # Current implementation
239 ///
240 /// The current algorithm is an adaptive, iterative merge sort inspired by
241 /// [timsort](https://en.wikipedia.org/wiki/Timsort).
242 /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
243 /// two or more sorted sequences concatenated one after another.
244 ///
245 /// Also, it allocates temporary storage half the size of `self`, but for short slices a
246 /// non-allocating insertion sort is used instead.
247 ///
248 /// # Examples
249 ///
250 /// ```
251 /// let mut v = [5, 4, 1, 3, 2];
252 /// v.sort_by(|a, b| a.cmp(b));
253 /// assert!(v == [1, 2, 3, 4, 5]);
254 ///
255 /// // reverse sorting
256 /// v.sort_by(|a, b| b.cmp(a));
257 /// assert!(v == [5, 4, 3, 2, 1]);
258 /// ```
259 #[cfg(not(no_global_oom_handling))]
260 #[rustc_allow_incoherent_impl]
261 #[stable(feature = "rust1", since = "1.0.0")]
262 #[inline]
263 pub fn sort_by<F>(&mut self, mut compare: F)
264 where
265 F: FnMut(&T, &T) -> Ordering,
266 {
267 stable_sort(self, |a, b| compare(a, b) == Less);
268 }
269
270 /// Sorts the slice with a key extraction function.
271 ///
272 /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* \* log(*n*))
273 /// worst-case, where the key function is *O*(*m*).
274 ///
275 /// For expensive key functions (e.g. functions that are not simple property accesses or
276 /// basic operations), [`sort_by_cached_key`](slice::sort_by_cached_key) is likely to be
277 /// significantly faster, as it does not recompute element keys.
278 ///
279 /// When applicable, unstable sorting is preferred because it is generally faster than stable
280 /// sorting and it doesn't allocate auxiliary memory.
281 /// See [`sort_unstable_by_key`](slice::sort_unstable_by_key).
282 ///
283 /// # Current implementation
284 ///
285 /// The current algorithm is an adaptive, iterative merge sort inspired by
286 /// [timsort](https://en.wikipedia.org/wiki/Timsort).
287 /// It is designed to be very fast in cases where the slice is nearly sorted, or consists of
288 /// two or more sorted sequences concatenated one after another.
289 ///
290 /// Also, it allocates temporary storage half the size of `self`, but for short slices a
291 /// non-allocating insertion sort is used instead.
292 ///
293 /// # Examples
294 ///
295 /// ```
296 /// let mut v = [-5i32, 4, 1, -3, 2];
297 ///
298 /// v.sort_by_key(|k| k.abs());
299 /// assert!(v == [1, 2, -3, 4, -5]);
300 /// ```
301 #[cfg(not(no_global_oom_handling))]
302 #[rustc_allow_incoherent_impl]
303 #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
304 #[inline]
305 pub fn sort_by_key<K, F>(&mut self, mut f: F)
306 where
307 F: FnMut(&T) -> K,
308 K: Ord,
309 {
310 stable_sort(self, |a, b| f(a).lt(&f(b)));
311 }
312
313 /// Sorts the slice with a key extraction function.
314 ///
315 /// During sorting, the key function is called at most once per element, by using
316 /// temporary storage to remember the results of key evaluation.
317 /// The order of calls to the key function is unspecified and may change in future versions
318 /// of the standard library.
319 ///
320 /// This sort is stable (i.e., does not reorder equal elements) and *O*(*m* \* *n* + *n* \* log(*n*))
321 /// worst-case, where the key function is *O*(*m*).
322 ///
323 /// For simple key functions (e.g., functions that are property accesses or
324 /// basic operations), [`sort_by_key`](slice::sort_by_key) is likely to be
325 /// faster.
326 ///
327 /// # Current implementation
328 ///
329 /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
330 /// which combines the fast average case of randomized quicksort with the fast worst case of
331 /// heapsort, while achieving linear time on slices with certain patterns. It uses some
332 /// randomization to avoid degenerate cases, but with a fixed seed to always provide
333 /// deterministic behavior.
334 ///
335 /// In the worst case, the algorithm allocates temporary storage in a `Vec<(K, usize)>` the
336 /// length of the slice.
337 ///
338 /// # Examples
339 ///
340 /// ```
341 /// let mut v = [-5i32, 4, 32, -3, 2];
342 ///
343 /// v.sort_by_cached_key(|k| k.to_string());
344 /// assert!(v == [-3, -5, 2, 32, 4]);
345 /// ```
346 ///
347 /// [pdqsort]: https://github.com/orlp/pdqsort
348 #[cfg(not(no_global_oom_handling))]
349 #[rustc_allow_incoherent_impl]
350 #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")]
351 #[inline]
352 pub fn sort_by_cached_key<K, F>(&mut self, f: F)
353 where
354 F: FnMut(&T) -> K,
355 K: Ord,
356 {
357 // Helper macro for indexing our vector by the smallest possible type, to reduce allocation.
358 macro_rules! sort_by_key {
359 ($t:ty, $slice:ident, $f:ident) => {{
360 let mut indices: Vec<_> =
361 $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect();
362 // The elements of `indices` are unique, as they are indexed, so any sort will be
363 // stable with respect to the original slice. We use `sort_unstable` here because
364 // it requires less memory allocation.
365 indices.sort_unstable();
366 for i in 0..$slice.len() {
367 let mut index = indices[i].1;
368 while (index as usize) < i {
369 index = indices[index as usize].1;
370 }
371 indices[i].1 = index;
372 $slice.swap(i, index as usize);
373 }
374 }};
375 }
376
377 let sz_u8 = mem::size_of::<(K, u8)>();
378 let sz_u16 = mem::size_of::<(K, u16)>();
379 let sz_u32 = mem::size_of::<(K, u32)>();
380 let sz_usize = mem::size_of::<(K, usize)>();
381
382 let len = self.len();
383 if len < 2 {
384 return;
385 }
386 if sz_u8 < sz_u16 && len <= (u8::MAX as usize) {
387 return sort_by_key!(u8, self, f);
388 }
389 if sz_u16 < sz_u32 && len <= (u16::MAX as usize) {
390 return sort_by_key!(u16, self, f);
391 }
392 if sz_u32 < sz_usize && len <= (u32::MAX as usize) {
393 return sort_by_key!(u32, self, f);
394 }
395 sort_by_key!(usize, self, f)
396 }
397
398 /// Copies `self` into a new `Vec`.
399 ///
400 /// # Examples
401 ///
402 /// ```
403 /// let s = [10, 40, 30];
404 /// let x = s.to_vec();
405 /// // Here, `s` and `x` can be modified independently.
406 /// ```
407 #[cfg(not(no_global_oom_handling))]
408 #[rustc_allow_incoherent_impl]
409 #[rustc_conversion_suggestion]
410 #[stable(feature = "rust1", since = "1.0.0")]
411 #[inline]
412 pub fn to_vec(&self) -> Vec<T>
413 where
414 T: Clone,
415 {
416 self.to_vec_in(Global)
417 }
418
419 /// Copies `self` into a new `Vec` with an allocator.
420 ///
421 /// # Examples
422 ///
423 /// ```
424 /// #![feature(allocator_api)]
425 ///
426 /// use std::alloc::System;
427 ///
428 /// let s = [10, 40, 30];
429 /// let x = s.to_vec_in(System);
430 /// // Here, `s` and `x` can be modified independently.
431 /// ```
432 #[cfg(not(no_global_oom_handling))]
433 #[rustc_allow_incoherent_impl]
434 #[inline]
435 #[unstable(feature = "allocator_api", issue = "32838")]
436 pub fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A>
437 where
438 T: Clone,
439 {
440 // N.B., see the `hack` module in this file for more details.
441 hack::to_vec(self, alloc)
442 }
443
444 /// Converts `self` into a vector without clones or allocation.
445 ///
446 /// The resulting vector can be converted back into a box via
447 /// `Vec<T>`'s `into_boxed_slice` method.
448 ///
449 /// # Examples
450 ///
451 /// ```
452 /// let s: Box<[i32]> = Box::new([10, 40, 30]);
453 /// let x = s.into_vec();
454 /// // `s` cannot be used anymore because it has been converted into `x`.
455 ///
456 /// assert_eq!(x, vec![10, 40, 30]);
457 /// ```
458 #[rustc_allow_incoherent_impl]
459 #[stable(feature = "rust1", since = "1.0.0")]
460 #[inline]
461 pub fn into_vec<A: Allocator>(self: Box<Self, A>) -> Vec<T, A> {
462 // N.B., see the `hack` module in this file for more details.
463 hack::into_vec(self)
464 }
465
466 /// Creates a vector by copying a slice `n` times.
467 ///
468 /// # Panics
469 ///
470 /// This function will panic if the capacity would overflow.
471 ///
472 /// # Examples
473 ///
474 /// Basic usage:
475 ///
476 /// ```
477 /// assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]);
478 /// ```
479 ///
480 /// A panic upon overflow:
481 ///
482 /// ```should_panic
483 /// // this will panic at runtime
484 /// b"0123456789abcdef".repeat(usize::MAX);
485 /// ```
486 #[rustc_allow_incoherent_impl]
487 #[cfg(not(no_global_oom_handling))]
488 #[stable(feature = "repeat_generic_slice", since = "1.40.0")]
489 pub fn repeat(&self, n: usize) -> Vec<T>
490 where
491 T: Copy,
492 {
493 if n == 0 {
494 return Vec::new();
495 }
496
497 // If `n` is larger than zero, it can be split as
498 // `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`.
499 // `2^expn` is the number represented by the leftmost '1' bit of `n`,
500 // and `rem` is the remaining part of `n`.
501
502 // Using `Vec` to access `set_len()`.
503 let capacity = self.len().checked_mul(n).expect("capacity overflow");
504 let mut buf = Vec::with_capacity(capacity);
505
506 // `2^expn` repetition is done by doubling `buf` `expn`-times.
507 buf.extend(self);
508 {
509 let mut m = n >> 1;
510 // If `m > 0`, there are remaining bits up to the leftmost '1'.
511 while m > 0 {
512 // `buf.extend(buf)`:
513 unsafe {
514 ptr::copy_nonoverlapping::<T>(
515 buf.as_ptr(),
516 (buf.as_mut_ptr()).add(buf.len()),
517 buf.len(),
518 );
519 // `buf` has capacity of `self.len() * n`.
520 let buf_len = buf.len();
521 buf.set_len(buf_len * 2);
522 }
523
524 m >>= 1;
525 }
526 }
527
528 // `rem` (`= n - 2^expn`) repetition is done by copying
529 // first `rem` repetitions from `buf` itself.
530 let rem_len = capacity - buf.len(); // `self.len() * rem`
531 if rem_len > 0 {
532 // `buf.extend(buf[0 .. rem_len])`:
533 unsafe {
534 // This is non-overlapping since `2^expn > rem`.
535 ptr::copy_nonoverlapping::<T>(
536 buf.as_ptr(),
537 (buf.as_mut_ptr()).add(buf.len()),
538 rem_len,
539 );
540 // `buf.len() + rem_len` equals to `buf.capacity()` (`= self.len() * n`).
541 buf.set_len(capacity);
542 }
543 }
544 buf
545 }
546
547 /// Flattens a slice of `T` into a single value `Self::Output`.
548 ///
549 /// # Examples
550 ///
551 /// ```
552 /// assert_eq!(["hello", "world"].concat(), "helloworld");
553 /// assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
554 /// ```
555 #[rustc_allow_incoherent_impl]
556 #[stable(feature = "rust1", since = "1.0.0")]
557 pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output
558 where
559 Self: Concat<Item>,
560 {
561 Concat::concat(self)
562 }
563
564 /// Flattens a slice of `T` into a single value `Self::Output`, placing a
565 /// given separator between each.
566 ///
567 /// # Examples
568 ///
569 /// ```
570 /// assert_eq!(["hello", "world"].join(" "), "hello world");
571 /// assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]);
572 /// assert_eq!([[1, 2], [3, 4]].join(&[0, 0][..]), [1, 2, 0, 0, 3, 4]);
573 /// ```
574 #[rustc_allow_incoherent_impl]
575 #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
576 pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
577 where
578 Self: Join<Separator>,
579 {
580 Join::join(self, sep)
581 }
582
583 /// Flattens a slice of `T` into a single value `Self::Output`, placing a
584 /// given separator between each.
585 ///
586 /// # Examples
587 ///
588 /// ```
589 /// # #![allow(deprecated)]
590 /// assert_eq!(["hello", "world"].connect(" "), "hello world");
591 /// assert_eq!([[1, 2], [3, 4]].connect(&0), [1, 2, 0, 3, 4]);
592 /// ```
593 #[rustc_allow_incoherent_impl]
594 #[stable(feature = "rust1", since = "1.0.0")]
595 #[deprecated(since = "1.3.0", note = "renamed to join", suggestion = "join")]
596 pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
597 where
598 Self: Join<Separator>,
599 {
600 Join::join(self, sep)
601 }
602}
603
604#[cfg(not(test))]
605impl [u8] {
606 /// Returns a vector containing a copy of this slice where each byte
607 /// is mapped to its ASCII upper case equivalent.
608 ///
609 /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
610 /// but non-ASCII letters are unchanged.
611 ///
612 /// To uppercase the value in-place, use [`make_ascii_uppercase`].
613 ///
614 /// [`make_ascii_uppercase`]: slice::make_ascii_uppercase
615 #[cfg(not(no_global_oom_handling))]
616 #[rustc_allow_incoherent_impl]
617 #[must_use = "this returns the uppercase bytes as a new Vec, \
618 without modifying the original"]
619 #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
620 #[inline]
621 pub fn to_ascii_uppercase(&self) -> Vec<u8> {
622 let mut me = self.to_vec();
623 me.make_ascii_uppercase();
624 me
625 }
626
627 /// Returns a vector containing a copy of this slice where each byte
628 /// is mapped to its ASCII lower 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 lowercase the value in-place, use [`make_ascii_lowercase`].
634 ///
635 /// [`make_ascii_lowercase`]: slice::make_ascii_lowercase
636 #[cfg(not(no_global_oom_handling))]
637 #[rustc_allow_incoherent_impl]
638 #[must_use = "this returns the lowercase 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_lowercase(&self) -> Vec<u8> {
643 let mut me = self.to_vec();
644 me.make_ascii_lowercase();
645 me
646 }
647}
648
649////////////////////////////////////////////////////////////////////////////////
650// Extension traits for slices over specific kinds of data
651////////////////////////////////////////////////////////////////////////////////
652
653/// Helper trait for [`[T]::concat`](slice::concat).
654///
655/// Note: the `Item` type parameter is not used in this trait,
656/// but it allows impls to be more generic.
657/// Without it, we get this error:
658///
659/// ```error
660/// error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predica
661/// --> library/alloc/src/slice.rs:608:6
662/// |
663/// 608 | impl<T: Clone, V: Borrow<[T]>> Concat for [V] {
664/// | ^ unconstrained type parameter
665/// ```
666///
667/// This is because there could exist `V` types with multiple `Borrow<[_]>` impls,
668/// such that multiple `T` types would apply:
669///
670/// ```
671/// # #[allow(dead_code)]
672/// pub struct Foo(Vec<u32>, Vec<String>);
673///
674/// impl std::borrow::Borrow<[u32]> for Foo {
675/// fn borrow(&self) -> &[u32] { &self.0 }
676/// }
677///
678/// impl std::borrow::Borrow<[String]> for Foo {
679/// fn borrow(&self) -> &[String] { &self.1 }
680/// }
681/// ```
682#[unstable(feature = "slice_concat_trait", issue = "27747")]
683pub trait Concat<Item: ?Sized> {
684 #[unstable(feature = "slice_concat_trait", issue = "27747")]
685 /// The resulting type after concatenation
686 type Output;
687
688 /// Implementation of [`[T]::concat`](slice::concat)
689 #[unstable(feature = "slice_concat_trait", issue = "27747")]
690 fn concat(slice: &Self) -> Self::Output;
691}
692
693/// Helper trait for [`[T]::join`](slice::join)
694#[unstable(feature = "slice_concat_trait", issue = "27747")]
695pub trait Join<Separator> {
696 #[unstable(feature = "slice_concat_trait", issue = "27747")]
697 /// The resulting type after concatenation
698 type Output;
699
700 /// Implementation of [`[T]::join`](slice::join)
701 #[unstable(feature = "slice_concat_trait", issue = "27747")]
702 fn join(slice: &Self, sep: Separator) -> Self::Output;
703}
704
705#[cfg(not(no_global_oom_handling))]
706#[unstable(feature = "slice_concat_ext", issue = "27747")]
707impl<T: Clone, V: Borrow<[T]>> Concat<T> for [V] {
708 type Output = Vec<T>;
709
710 fn concat(slice: &Self) -> Vec<T> {
711 let size: usize = slice.iter().map(|slice: &V| slice.borrow().len()).sum();
712 let mut result: Vec = Vec::with_capacity(size);
713 for v: &V in slice {
714 result.extend_from_slice(v.borrow())
715 }
716 result
717 }
718}
719
720#[cfg(not(no_global_oom_handling))]
721#[unstable(feature = "slice_concat_ext", issue = "27747")]
722impl<T: Clone, V: Borrow<[T]>> Join<&T> for [V] {
723 type Output = Vec<T>;
724
725 fn join(slice: &Self, sep: &T) -> Vec<T> {
726 let mut iter: Iter<'_, V> = slice.iter();
727 let first: &V = match iter.next() {
728 Some(first: &V) => first,
729 None => return vec![],
730 };
731 let size: usize = slice.iter().map(|v: &V| v.borrow().len()).sum::<usize>() + slice.len() - 1;
732 let mut result: Vec = Vec::with_capacity(size);
733 result.extend_from_slice(first.borrow());
734
735 for v: &V in iter {
736 result.push(sep.clone());
737 result.extend_from_slice(v.borrow())
738 }
739 result
740 }
741}
742
743#[cfg(not(no_global_oom_handling))]
744#[unstable(feature = "slice_concat_ext", issue = "27747")]
745impl<T: Clone, V: Borrow<[T]>> Join<&[T]> for [V] {
746 type Output = Vec<T>;
747
748 fn join(slice: &Self, sep: &[T]) -> Vec<T> {
749 let mut iter: Iter<'_, V> = slice.iter();
750 let first: &V = match iter.next() {
751 Some(first: &V) => first,
752 None => return vec![],
753 };
754 let size: usize =
755 slice.iter().map(|v: &V| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1);
756 let mut result: Vec = Vec::with_capacity(size);
757 result.extend_from_slice(first.borrow());
758
759 for v: &V in iter {
760 result.extend_from_slice(sep);
761 result.extend_from_slice(v.borrow())
762 }
763 result
764 }
765}
766
767////////////////////////////////////////////////////////////////////////////////
768// Standard trait implementations for slices
769////////////////////////////////////////////////////////////////////////////////
770
771#[stable(feature = "rust1", since = "1.0.0")]
772impl<T, A: Allocator> Borrow<[T]> for Vec<T, A> {
773 fn borrow(&self) -> &[T] {
774 &self[..]
775 }
776}
777
778#[stable(feature = "rust1", since = "1.0.0")]
779impl<T, A: Allocator> BorrowMut<[T]> for Vec<T, A> {
780 fn borrow_mut(&mut self) -> &mut [T] {
781 &mut self[..]
782 }
783}
784
785// Specializable trait for implementing ToOwned::clone_into. This is
786// public in the crate and has the Allocator parameter so that
787// vec::clone_from use it too.
788#[cfg(not(no_global_oom_handling))]
789pub(crate) trait SpecCloneIntoVec<T, A: Allocator> {
790 fn clone_into(&self, target: &mut Vec<T, A>);
791}
792
793#[cfg(not(no_global_oom_handling))]
794impl<T: Clone, A: Allocator> SpecCloneIntoVec<T, A> for [T] {
795 default fn clone_into(&self, target: &mut Vec<T, A>) {
796 // drop anything in target that will not be overwritten
797 target.truncate(self.len());
798
799 // target.len <= self.len due to the truncate above, so the
800 // slices here are always in-bounds.
801 let (init: &[T], tail: &[T]) = self.split_at(mid:target.len());
802
803 // reuse the contained values' allocations/resources.
804 target.clone_from_slice(src:init);
805 target.extend_from_slice(tail);
806 }
807}
808
809#[cfg(not(no_global_oom_handling))]
810impl<T: Copy, A: Allocator> SpecCloneIntoVec<T, A> for [T] {
811 fn clone_into(&self, target: &mut Vec<T, A>) {
812 target.clear();
813 target.extend_from_slice(self);
814 }
815}
816
817#[cfg(not(no_global_oom_handling))]
818#[stable(feature = "rust1", since = "1.0.0")]
819impl<T: Clone> ToOwned for [T] {
820 type Owned = Vec<T>;
821 #[cfg(not(test))]
822 fn to_owned(&self) -> Vec<T> {
823 self.to_vec()
824 }
825
826 #[cfg(test)]
827 fn to_owned(&self) -> Vec<T> {
828 hack::to_vec(self, Global)
829 }
830
831 fn clone_into(&self, target: &mut Vec<T>) {
832 SpecCloneIntoVec::clone_into(self, target);
833 }
834}
835
836////////////////////////////////////////////////////////////////////////////////
837// Sorting
838////////////////////////////////////////////////////////////////////////////////
839
840#[inline]
841#[cfg(not(no_global_oom_handling))]
842fn stable_sort<T, F>(v: &mut [T], mut is_less: F)
843where
844 F: FnMut(&T, &T) -> bool,
845{
846 if T::IS_ZST {
847 // Sorting has no meaningful behavior on zero-sized types. Do nothing.
848 return;
849 }
850
851 let elem_alloc_fn = |len: usize| -> *mut T {
852 // SAFETY: Creating the layout is safe as long as merge_sort never calls this with len >
853 // v.len(). Alloc in general will only be used as 'shadow-region' to store temporary swap
854 // elements.
855 unsafe { alloc::alloc(alloc::Layout::array::<T>(len).unwrap_unchecked()) as *mut T }
856 };
857
858 let elem_dealloc_fn = |buf_ptr: *mut T, len: usize| {
859 // SAFETY: Creating the layout is safe as long as merge_sort never calls this with len >
860 // v.len(). The caller must ensure that buf_ptr was created by elem_alloc_fn with the same
861 // len.
862 unsafe {
863 alloc::dealloc(buf_ptr as *mut u8, alloc::Layout::array::<T>(len).unwrap_unchecked());
864 }
865 };
866
867 let run_alloc_fn = |len: usize| -> *mut sort::TimSortRun {
868 // SAFETY: Creating the layout is safe as long as merge_sort never calls this with an
869 // obscene length or 0.
870 unsafe {
871 alloc::alloc(alloc::Layout::array::<sort::TimSortRun>(len).unwrap_unchecked())
872 as *mut sort::TimSortRun
873 }
874 };
875
876 let run_dealloc_fn = |buf_ptr: *mut sort::TimSortRun, len: usize| {
877 // SAFETY: The caller must ensure that buf_ptr was created by elem_alloc_fn with the same
878 // len.
879 unsafe {
880 alloc::dealloc(
881 buf_ptr as *mut u8,
882 alloc::Layout::array::<sort::TimSortRun>(len).unwrap_unchecked(),
883 );
884 }
885 };
886
887 sort::merge_sort(v, &mut is_less, elem_alloc_fn, elem_dealloc_fn, run_alloc_fn, run_dealloc_fn);
888}
889