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