projects/linux·blob v6.6 · refs

890 lines · 30.7 KiB

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