//! 动态大小的视图到一个连续的序列， `[T]`.
//!
//! *[See also the slice primitive type](slice).*
//!
//! 切片是一个内存块的视图，表示为一个指针和一个长度。
//!
//! ```
//! // 切片 Vec
//! let vec = vec![1, 2, 3];
//! let int_slice = &vec[..];
//! // 将数组强制转换为切片
//! let str_slice: &[&str] = &["one", "two", "three"];
//! ```
//!
//! 切片是可变的或共享的。
//! 共享切片类型为 `&[T]`，而可变切片类型为 `&mut [T]`，其中 `T` 表示元素类型。
//! 例如，您可以更改可变切片所指向的内存块:
//!
//! ```
//! let x = &mut [1, 2, 3];
//! x[1] = 7;
//! assert_eq!(x, &[1, 7, 3]);
//! ```
//!
//! 以下是此模块包含的一些内容:
//!
//! ## Structs
//!
//! 有几种结构切片可用于切片，例如 [`Iter`]，它表示切片上的迭代。
//!
//! ## Trait 实现
//!
//! 切片具有常见的 traits 的几种实现。一些示例包括:
//!
//! * [`Clone`]
//! * [`Eq`], [`Ord`] - 用于元素类型为 [`Eq`] 或 [`Ord`] 的切片。
//! * [`Hash`] - 用于元素类型为 [`Hash`] 的切片。
//!
//! ## Iteration
//!
//! 切片实现 `IntoIterator`。迭代器产生对切片元素的引用。
//!
//! ```
//! let numbers = &[0, 1, 2];
//! for n in numbers {
//!     println!("{} is a number!", n);
//! }
//! ```
//!
//! 可变切片对以下元素产生了可变引用:
//!
//! ```
//! let mut scores = [7, 8, 9];
//! for score in &mut scores[..] {
//!     *score += 1;
//! }
//! ```
//!
//! 此迭代器产生对切片元素的可变引用，因此，当切片的元素类型为 `i32` 时，迭代器的元素类型为 `&mut i32`。
//!
//!
//! * [`.iter`] [`.iter_mut`] 和 [`.iter_mut`] 是返回默认迭代器的显式方法。
//! * 返回迭代器的其他方法是 [`.split`]，[`.splitn`]，[`.chunks`]，[`.windows`] 等。
//!
//! [`Hash`]: core::hash::Hash
//! [`.iter`]: slice::iter
//! [`.iter_mut`]: slice::iter_mut
//! [`.split`]: slice::split
//! [`.splitn`]: slice::splitn
//! [`.chunks`]: slice::chunks
//! [`.windows`]: slice::windows
//!
//!
//!
//!
//!
//!
//!
//!
#![stable(feature = "rust1", since = "1.0.0")]
// 该模块中的许多用法仅在测试配置中使用。
// 仅关闭 unused_imports 警告比解决它们更干净。
#![cfg_attr(test, allow(unused_imports, dead_code))]

use core::borrow::{Borrow, BorrowMut};
#[cfg(not(no_global_oom_handling))]
use core::cmp::Ordering::{self, Less};
#[cfg(not(no_global_oom_handling))]
use core::mem;
#[cfg(not(no_global_oom_handling))]
use core::mem::size_of;
#[cfg(not(no_global_oom_handling))]
use core::ptr;

use crate::alloc::Allocator;
#[cfg(not(no_global_oom_handling))]
use crate::alloc::Global;
#[cfg(not(no_global_oom_handling))]
use crate::borrow::ToOwned;
use crate::boxed::Box;
use crate::vec::Vec;

#[unstable(feature = "slice_range", issue = "76393")]
pub use core::slice::range;
#[unstable(feature = "array_chunks", issue = "74985")]
pub use core::slice::ArrayChunks;
#[unstable(feature = "array_chunks", issue = "74985")]
pub use core::slice::ArrayChunksMut;
#[unstable(feature = "array_windows", issue = "75027")]
pub use core::slice::ArrayWindows;
#[stable(feature = "slice_get_slice", since = "1.28.0")]
pub use core::slice::SliceIndex;
#[stable(feature = "from_ref", since = "1.28.0")]
pub use core::slice::{from_mut, from_ref};
#[stable(feature = "rust1", since = "1.0.0")]
pub use core::slice::{from_raw_parts, from_raw_parts_mut};
#[stable(feature = "rust1", since = "1.0.0")]
pub use core::slice::{Chunks, Windows};
#[stable(feature = "chunks_exact", since = "1.31.0")]
pub use core::slice::{ChunksExact, ChunksExactMut};
#[stable(feature = "rust1", since = "1.0.0")]
pub use core::slice::{ChunksMut, Split, SplitMut};
#[unstable(feature = "slice_group_by", issue = "80552")]
pub use core::slice::{GroupBy, GroupByMut};
#[stable(feature = "rust1", since = "1.0.0")]
pub use core::slice::{Iter, IterMut};
#[stable(feature = "rchunks", since = "1.31.0")]
pub use core::slice::{RChunks, RChunksExact, RChunksExactMut, RChunksMut};
#[stable(feature = "slice_rsplit", since = "1.27.0")]
pub use core::slice::{RSplit, RSplitMut};
#[stable(feature = "rust1", since = "1.0.0")]
pub use core::slice::{RSplitN, RSplitNMut, SplitN, SplitNMut};

////////////////////////////////////////////////////////////////////////////////
// 基本切片扩展方法
////////////////////////////////////////////////////////////////////////////////

// HACK(japaric) 测试 NB 期间实现 `vec!` 宏所需的信息，请参见此文件中的 `hack` 模块以获取更多详细信息。
//
#[cfg(test)]
pub use hack::into_vec;

// HACK(japaric) 测试 NB 期间实现 `Vec::clone` 所需的信息，请参见此文件中的 `hack` 模块以获取更多详细信息。
//
#[cfg(test)]
pub use hack::to_vec;

// HACK(japaric): 对于 cfg(test)，`impl [T]` 不可用，这三个函数实际上是 `impl [T]` 中的方法，但不是 `core::slice::SliceExt` 中的方法 - 我们需要为 `test_permutations` 测试提供这些函数
//
//
//
mod hack {
    use core::alloc::Allocator;

    use crate::boxed::Box;
    use crate::vec::Vec;

    // 我们不应该向此属性添加内联属性，因为该属性主要在 `vec!` 宏中使用，并且会导致性能下降。
    // 有关讨论和性能结果，请参见 #71204。
    //
    pub fn into_vec<T, A: Allocator>(b: Box<[T], A>) -> Vec<T, A> {
        unsafe {
            let len = b.len();
            let (b, alloc) = Box::into_raw_with_allocator(b);
            Vec::from_raw_parts_in(b as *mut T, len, len, alloc)
        }
    }

    #[cfg(not(no_global_oom_handling))]
    #[inline]
    pub fn to_vec<T: ConvertVec, A: Allocator>(s: &[T], alloc: A) -> Vec<T, A> {
        T::to_vec(s, alloc)
    }

    #[cfg(not(no_global_oom_handling))]
    pub trait ConvertVec {
        fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A>
        where
            Self: Sized;
    }

    #[cfg(not(no_global_oom_handling))]
    impl<T: Clone> ConvertVec for T {
        #[inline]
        default fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {
            struct DropGuard<'a, T, A: Allocator> {
                vec: &'a mut Vec<T, A>,
                num_init: usize,
            }
            impl<'a, T, A: Allocator> Drop for DropGuard<'a, T, A> {
                #[inline]
                fn drop(&mut self) {
                    // SAFETY:
                    // 项在下面的循环中被标记为已初始化
                    unsafe {
                        self.vec.set_len(self.num_init);
                    }
                }
            }
            let mut vec = Vec::with_capacity_in(s.len(), alloc);
            let mut guard = DropGuard { vec: &mut vec, num_init: 0 };
            let slots = guard.vec.spare_capacity_mut();
            // .take(slots.len()) 是 LLVM 删除边界检查所必需的，并且具有比 zip 更好的代码生成。
            //
            for (i, b) in s.iter().enumerate().take(slots.len()) {
                guard.num_init = i;
                slots[i].write(b.clone());
            }
            core::mem::forget(guard);
            // SAFETY:
            // vec 的分配和初始化至少要达到此长度。
            unsafe {
                vec.set_len(s.len());
            }
            vec
        }
    }

    #[cfg(not(no_global_oom_handling))]
    impl<T: Copy> ConvertVec for T {
        #[inline]
        fn to_vec<A: Allocator>(s: &[Self], alloc: A) -> Vec<Self, A> {
            let mut v = Vec::with_capacity_in(s.len(), alloc);
            // SAFETY:
            // 在上面分配了 `s` 的容量，并在下面的 ptr::copy_to_non_overlapping 中初始化为 `s.len()`。
            //
            unsafe {
                s.as_ptr().copy_to_nonoverlapping(v.as_mut_ptr(), s.len());
                v.set_len(s.len());
            }
            v
        }
    }
}

#[lang = "slice_alloc"]
#[cfg(not(test))]
impl<T> [T] {
    /// 对切片进行排序。
    ///
    /// 这种排序是稳定的 (即，不对相等的元素重新排序)，并且 *O*(*n*\*log(* n*)) 最坏的情况)。
    ///
    /// 在适用时，首选不稳定排序，因为它通常比稳定排序快，并且不分配辅助内存。
    /// 请参见 [`sort_unstable`](slice::sort_unstable)。
    ///
    /// # 当前实现
    ///
    /// 当前的算法是一种受 [timsort](https://en.wikipedia.org/wiki/Timsort) 启发的自适应迭代合并排序。
    /// 在切片几乎被排序或由两个或多个依次连接的排序序列组成的情况下，它设计得非常快。
    ///
    ///
    /// 同样，它分配临时存储空间的大小是 `self` 的一半，但是对于短片，则使用非分配插入排序。
    ///
    /// # Examples
    ///
    /// ```
    /// let mut v = [-5, 4, 1, -3, 2];
    ///
    /// v.sort();
    /// assert!(v == [-5, -3, 1, 2, 4]);
    /// ```
    ///
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn sort(&mut self)
    where
        T: Ord,
    {
        merge_sort(self, |a, b| a.lt(b));
    }

    /// 用比较器函数对切片进行排序。
    ///
    /// 这种排序是稳定的 (即，不对相等的元素重新排序)，并且 *O*(*n*\*log(* n*)) 最坏的情况)。
    ///
    /// 比较器函数必须为切片中的元素定义总顺序。如果顺序不是总计，则未指定元素的顺序。
    /// 如果一个顺序是（对于所有的`a`, `b` 和 `c`），那么它就是一个总体顺序
    ///
    /// * 完全和反对称的: `a < b`，`a == b` 或 `a > b` 之一正确，并且
    /// * 可传递的，`a < b` 和 `b < c` 表示 `a < c`。`==` 和 `>` 必须保持相同。
    ///
    /// 例如，虽然 [`f64`] 由于 `NaN != NaN` 而不实现 [`Ord`]，但是当我们知道切片不包含 `NaN` 时，可以将 `partial_cmp` 用作我们的排序函数。
    ///
    ///
    /// ```
    /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0];
    /// floats.sort_by(|a, b| a.partial_cmp(b).unwrap());
    /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]);
    /// ```
    ///
    /// 在适用时，首选不稳定排序，因为它通常比稳定排序快，并且不分配辅助内存。
    /// 请参见 [`sort_unstable_by`](slice::sort_unstable_by)。
    ///
    /// # 当前实现
    ///
    /// 当前的算法是一种受 [timsort](https://en.wikipedia.org/wiki/Timsort) 启发的自适应迭代合并排序。
    /// 在切片几乎被排序或由两个或多个依次连接的排序序列组成的情况下，它设计得非常快。
    ///
    /// 同样，它分配临时存储空间的大小是 `self` 的一半，但是对于短片，则使用非分配插入排序。
    ///
    /// # Examples
    ///
    /// ```
    /// let mut v = [5, 4, 1, 3, 2];
    /// v.sort_by(|a, b| a.cmp(b));
    /// assert!(v == [1, 2, 3, 4, 5]);
    ///
    /// // 反向排序
    /// v.sort_by(|a, b| b.cmp(a));
    /// assert!(v == [5, 4, 3, 2, 1]);
    /// ```
    ///
    ///
    ///
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn sort_by<F>(&mut self, mut compare: F)
    where
        F: FnMut(&T, &T) -> Ordering,
    {
        merge_sort(self, |a, b| compare(a, b) == Less);
    }

    /// 用键提取函数对切片进行排序。
    ///
    /// 这种排序是稳定的 (即，不对相等的元素重新排序)，并且是 *O*(*m*\* * n *\* log(*n*)) 最坏的情况，其中键函数为 *O*(*m*)。
    ///
    /// 对于昂贵的键函数 (例如
    /// 不是简单的属性访问或基本操作的函数)，[`sort_by_cached_key`](slice::sort_by_cached_key) 可能会显着提高速度，因为它不会重新计算元素键。
    ///
    ///
    /// 在适用时，首选不稳定排序，因为它通常比稳定排序快，并且不分配辅助内存。
    /// 请参见 [`sort_unstable_by_key`](slice::sort_unstable_by_key)。
    ///
    /// # 当前实现
    ///
    /// 当前的算法是一种受 [timsort](https://en.wikipedia.org/wiki/Timsort) 启发的自适应迭代合并排序。
    /// 在切片几乎被排序或由两个或多个依次连接的排序序列组成的情况下，它设计得非常快。
    ///
    /// 同样，它分配临时存储空间的大小是 `self` 的一半，但是对于短片，则使用非分配插入排序。
    ///
    /// # Examples
    ///
    /// ```
    /// let mut v = [-5i32, 4, 1, -3, 2];
    ///
    /// v.sort_by_key(|k| k.abs());
    /// assert!(v == [1, 2, -3, 4, -5]);
    /// ```
    ///
    ///
    ///
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    #[stable(feature = "slice_sort_by_key", since = "1.7.0")]
    #[inline]
    pub fn sort_by_key<K, F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> K,
        K: Ord,
    {
        merge_sort(self, |a, b| f(a).lt(&f(b)));
    }

    /// 用键提取函数对切片进行排序。
    ///
    /// 在排序期间，键函数每个元素仅被调用一次。
    ///
    /// 这种排序是稳定的 (即，不对相等的元素重新排序)，并且 *O*(*m*\* * n *+* n *\* log(*n*)) 最坏的情况是，其中键函数为 *O*(*m*)。
    ///
    /// 对于简单的键函数 (例如，作为属性访问或基本操作的函数)，[`sort_by_key`](slice::sort_by_key) 可能会更快。
    ///
    /// # 当前实现
    ///
    /// 当前算法基于 Orson Peters 的 [pattern-defeating 的快速排序][pdqsort]，该算法将随机快速排序的快速平均情况与堆排序的快速最坏情况相结合，同时在具有特定模式的切片上实现了线性时间。
    /// 它使用一些随机化来避免退化的情况，但是使用固定的 seed 来始终提供确定性的行为。
    ///
    /// 在最坏的情况下，该算法在 `Vec<(K, usize)>` 中分配切片长度的临时存储。
    ///
    /// # Examples
    ///
    /// ```
    /// let mut v = [-5i32, 4, 32, -3, 2];
    ///
    /// v.sort_by_cached_key(|k| k.to_string());
    /// assert!(v == [-3, -5, 2, 32, 4]);
    /// ```
    ///
    /// [pdqsort]: https://github.com/orlp/pdqsort
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    #[cfg(not(no_global_oom_handling))]
    #[stable(feature = "slice_sort_by_cached_key", since = "1.34.0")]
    #[inline]
    pub fn sort_by_cached_key<K, F>(&mut self, f: F)
    where
        F: FnMut(&T) -> K,
        K: Ord,
    {
        // 辅助宏，用于通过最小的类型索引 vector，以减少分配。
        macro_rules! sort_by_key {
            ($t:ty, $slice:ident, $f:ident) => {{
                let mut indices: Vec<_> =
                    $slice.iter().map($f).enumerate().map(|(i, k)| (k, i as $t)).collect();
                // `indices` 的元素是唯一的，因为它们已被索引，因此任何种类相对于原始切片都是稳定的。
                // 我们在这里使用 `sort_unstable` 是因为它需要较少的内存分配。
                //
                indices.sort_unstable();
                for i in 0..$slice.len() {
                    let mut index = indices[i].1;
                    while (index as usize) < i {
                        index = indices[index as usize].1;
                    }
                    indices[i].1 = index;
                    $slice.swap(i, index as usize);
                }
            }};
        }

        let sz_u8 = mem::size_of::<(K, u8)>();
        let sz_u16 = mem::size_of::<(K, u16)>();
        let sz_u32 = mem::size_of::<(K, u32)>();
        let sz_usize = mem::size_of::<(K, usize)>();

        let len = self.len();
        if len < 2 {
            return;
        }
        if sz_u8 < sz_u16 && len <= (u8::MAX as usize) {
            return sort_by_key!(u8, self, f);
        }
        if sz_u16 < sz_u32 && len <= (u16::MAX as usize) {
            return sort_by_key!(u16, self, f);
        }
        if sz_u32 < sz_usize && len <= (u32::MAX as usize) {
            return sort_by_key!(u32, self, f);
        }
        sort_by_key!(usize, self, f)
    }

    /// 将 `self` 复制到新的 `Vec` 中。
    ///
    /// # Examples
    ///
    /// ```
    /// let s = [10, 40, 30];
    /// let x = s.to_vec();
    /// // 在此，`s` 和 `x` 可以独立修改。
    /// ```
    #[cfg(not(no_global_oom_handling))]
    #[rustc_conversion_suggestion]
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn to_vec(&self) -> Vec<T>
    where
        T: Clone,
    {
        self.to_vec_in(Global)
    }

    /// 使用分配器将 `self` 复制到新的 `Vec` 中。
    ///
    /// # Examples
    ///
    /// ```
    /// #![feature(allocator_api)]
    ///
    /// use std::alloc::System;
    ///
    /// let s = [10, 40, 30];
    /// let x = s.to_vec_in(System);
    /// // 在此，`s` 和 `x` 可以独立修改。
    /// ```
    #[cfg(not(no_global_oom_handling))]
    #[inline]
    #[unstable(feature = "allocator_api", issue = "32838")]
    pub fn to_vec_in<A: Allocator>(&self, alloc: A) -> Vec<T, A>
    where
        T: Clone,
    {
        // 注意，有关更多详细信息，请参见此文件中的 `hack` 模块。
        hack::to_vec(self, alloc)
    }

    /// 将 `self` 转换为 vector，而无需克隆或分配。
    ///
    /// 产生的 vector 可以通过 `Vec 转换回 box<T>` 的 `into_boxed_slice` 方法。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// let s: Box<[i32]> = Box::new([10, 40, 30]);
    /// let x = s.into_vec();
    /// // `s` 由于已将其转换为 `x`，因此无法再使用。
    ///
    /// assert_eq!(x, vec![10, 40, 30]);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    #[inline]
    pub fn into_vec<A: Allocator>(self: Box<Self, A>) -> Vec<T, A> {
        // 注意，有关更多详细信息，请参见此文件中的 `hack` 模块。
        hack::into_vec(self)
    }

    /// 通过重复切片 `n` 次来创建 vector。
    ///
    /// # Panics
    ///
    /// 如果容量溢出，此函数将为 panic。
    ///
    /// # Examples
    ///
    /// 基本用法:
    ///
    /// ```
    /// assert_eq!([1, 2].repeat(3), vec![1, 2, 1, 2, 1, 2]);
    /// ```
    ///
    /// 溢出时为 panic:
    ///
    /// ```should_panic
    /// // 这将在运行时 panic
    /// b"0123456789abcdef".repeat(usize::MAX);
    /// ```
    #[cfg(not(no_global_oom_handling))]
    #[stable(feature = "repeat_generic_slice", since = "1.40.0")]
    pub fn repeat(&self, n: usize) -> Vec<T>
    where
        T: Copy,
    {
        if n == 0 {
            return Vec::new();
        }

        // 如果 `n` 大于零，则可以将其拆分为 `n = 2^expn + rem (2^expn > rem, expn >= 0, rem >= 0)`。
        // `2^expn` 是 `n` 的最左 '1' 位表示的数字，而 `rem` 是 `n` 的其余部分。
        //
        //

        // 使用 `Vec` 访问 `set_len()`。
        let capacity = self.len().checked_mul(n).expect("capacity overflow");
        let mut buf = Vec::with_capacity(capacity);

        // `2^expn` 重复是通过将 `buf` expn`- 的时间加倍来完成的。
        buf.extend(self);
        {
            let mut m = n >> 1;
            // 如果是 `m > 0`，则剩余的位将保留到最左边的 '1'。
            while m > 0 {
                // `buf.extend(buf)`:
                unsafe {
                    ptr::copy_nonoverlapping(
                        buf.as_ptr(),
                        (buf.as_mut_ptr() as *mut T).add(buf.len()),
                        buf.len(),
                    );
                    // `buf` 具有 `self.len() * n` 的容量。
                    let buf_len = buf.len();
                    buf.set_len(buf_len * 2);
                }

                m >>= 1;
            }
        }

        // `rem` (`= n - 2^expn`) 重复是通过从 `buf` 本身复制第一个 `rem` 重复来完成的。
        //
        let rem_len = capacity - buf.len(); // `self.len() * rem`
        if rem_len > 0 {
            // `buf.extend(buf[0 .. rem_len])`:
            unsafe {
                // 自 `2^expn > rem` 起，这是不重叠的。
                ptr::copy_nonoverlapping(
                    buf.as_ptr(),
                    (buf.as_mut_ptr() as *mut T).add(buf.len()),
                    rem_len,
                );
                // `buf.len() + rem_len` 等于 `buf.capacity()` (`= self.len() * n`)。
                buf.set_len(capacity);
            }
        }
        buf
    }

    /// 将 `T` 的切片展平为单个值 `Self::Output`。
    ///
    /// # Examples
    ///
    /// ```
    /// assert_eq!(["hello", "world"].concat(), "helloworld");
    /// assert_eq!([[1, 2], [3, 4]].concat(), [1, 2, 3, 4]);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    pub fn concat<Item: ?Sized>(&self) -> <Self as Concat<Item>>::Output
    where
        Self: Concat<Item>,
    {
        Concat::concat(self)
    }

    /// 将 `T` 的切片展平为单个值 `Self::Output`，并在每个值之间放置一个给定的分隔符。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// assert_eq!(["hello", "world"].join(" "), "hello world");
    /// assert_eq!([[1, 2], [3, 4]].join(&0), [1, 2, 0, 3, 4]);
    /// assert_eq!([[1, 2], [3, 4]].join(&[0, 0][..]), [1, 2, 0, 0, 3, 4]);
    /// ```
    #[stable(feature = "rename_connect_to_join", since = "1.3.0")]
    pub fn join<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
    where
        Self: Join<Separator>,
    {
        Join::join(self, sep)
    }

    /// 将 `T` 的切片展平为单个值 `Self::Output`，并在每个值之间放置一个给定的分隔符。
    ///
    ///
    /// # Examples
    ///
    /// ```
    /// # #![allow(deprecated)]
    /// assert_eq!(["hello", "world"].connect(" "), "hello world");
    /// assert_eq!([[1, 2], [3, 4]].connect(&0), [1, 2, 0, 3, 4]);
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    #[rustc_deprecated(since = "1.3.0", reason = "renamed to join")]
    pub fn connect<Separator>(&self, sep: Separator) -> <Self as Join<Separator>>::Output
    where
        Self: Join<Separator>,
    {
        Join::join(self, sep)
    }
}

#[lang = "slice_u8_alloc"]
#[cfg(not(test))]
impl [u8] {
    /// 返回一个 vector，其中包含此切片的副本，其中每个字节都映射到其等效的 ASCII 大写字母。
    ///
    ///
    /// ASCII 字母 'a' 到 'z' 映射到 'A' 到 'Z'，但是非 ASCII 字母不变。
    ///
    /// 要就地将值大写，请使用 [`make_ascii_uppercase`]。
    ///
    /// [`make_ascii_uppercase`]: slice::make_ascii_uppercase
    ///
    #[cfg(not(no_global_oom_handling))]
    #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
    #[inline]
    pub fn to_ascii_uppercase(&self) -> Vec<u8> {
        let mut me = self.to_vec();
        me.make_ascii_uppercase();
        me
    }

    /// 返回一个 vector，其中包含该切片的副本，其中每个字节均映射为其等效的 ASCII 小写字母。
    ///
    ///
    /// ASCII 字母 'A' 到 'Z' 映射到 'a' 到 'z'，但是非 ASCII 字母不变。
    ///
    /// 要就地小写该值，请使用 [`make_ascii_lowercase`]。
    ///
    /// [`make_ascii_lowercase`]: slice::make_ascii_lowercase
    ///
    #[cfg(not(no_global_oom_handling))]
    #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
    #[inline]
    pub fn to_ascii_lowercase(&self) -> Vec<u8> {
        let mut me = self.to_vec();
        me.make_ascii_lowercase();
        me
    }
}

////////////////////////////////////////////////////////////////////////////////
// 扩展 traits 用于切片特定类型的数据
////////////////////////////////////////////////////////////////////////////////

/// [`[T]::concat`](slice::concat) 的辅助程序 trait。
///
/// Note: `Item` 类型参数未在此 trait 中使用，但它使 impls 更具泛型性。
/// 没有它，我们将收到此错误:
///
/// ```error
/// error[E0207]: the type parameter `T` is not constrained by the impl trait, self type, or predica
///    --> src/liballoc/slice.rs:608:6
///     |
/// 608 | impl<T: Clone, V: Borrow<[T]>> Concat for [V] {
///     |      ^ unconstrained type parameter
/// ```
///
/// 这是因为可能存在具有多个 `Borrow<[_]>` 表示的 `V` 类型，因此将应用多个 `T` 类型:
///
///
/// ```
/// # #[allow(dead_code)]
/// pub struct Foo(Vec<u32>, Vec<String>);
///
/// impl std::borrow::Borrow<[u32]> for Foo {
///     fn borrow(&self) -> &[u32] { &self.0 }
/// }
///
/// impl std::borrow::Borrow<[String]> for Foo {
///     fn borrow(&self) -> &[String] { &self.1 }
/// }
/// ```
///
#[unstable(feature = "slice_concat_trait", issue = "27747")]
pub trait Concat<Item: ?Sized> {
    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    /// 串联后的结果类型
    type Output;

    /// [`[T]::concat`](slice::concat) 的实现
    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    fn concat(slice: &Self) -> Self::Output;
}

/// [`[T]::join`](slice::join) 的辅助 trait
#[unstable(feature = "slice_concat_trait", issue = "27747")]
pub trait Join<Separator> {
    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    /// 串联后的结果类型
    type Output;

    /// [`[T]::join`](slice::join) 的实现
    #[unstable(feature = "slice_concat_trait", issue = "27747")]
    fn join(slice: &Self, sep: Separator) -> Self::Output;
}

#[cfg(not(no_global_oom_handling))]
#[unstable(feature = "slice_concat_ext", issue = "27747")]
impl<T: Clone, V: Borrow<[T]>> Concat<T> for [V] {
    type Output = Vec<T>;

    fn concat(slice: &Self) -> Vec<T> {
        let size = slice.iter().map(|slice| slice.borrow().len()).sum();
        let mut result = Vec::with_capacity(size);
        for v in slice {
            result.extend_from_slice(v.borrow())
        }
        result
    }
}

#[cfg(not(no_global_oom_handling))]
#[unstable(feature = "slice_concat_ext", issue = "27747")]
impl<T: Clone, V: Borrow<[T]>> Join<&T> for [V] {
    type Output = Vec<T>;

    fn join(slice: &Self, sep: &T) -> Vec<T> {
        let mut iter = slice.iter();
        let first = match iter.next() {
            Some(first) => first,
            None => return vec![],
        };
        let size = slice.iter().map(|v| v.borrow().len()).sum::<usize>() + slice.len() - 1;
        let mut result = Vec::with_capacity(size);
        result.extend_from_slice(first.borrow());

        for v in iter {
            result.push(sep.clone());
            result.extend_from_slice(v.borrow())
        }
        result
    }
}

#[cfg(not(no_global_oom_handling))]
#[unstable(feature = "slice_concat_ext", issue = "27747")]
impl<T: Clone, V: Borrow<[T]>> Join<&[T]> for [V] {
    type Output = Vec<T>;

    fn join(slice: &Self, sep: &[T]) -> Vec<T> {
        let mut iter = slice.iter();
        let first = match iter.next() {
            Some(first) => first,
            None => return vec![],
        };
        let size =
            slice.iter().map(|v| v.borrow().len()).sum::<usize>() + sep.len() * (slice.len() - 1);
        let mut result = Vec::with_capacity(size);
        result.extend_from_slice(first.borrow());

        for v in iter {
            result.extend_from_slice(sep);
            result.extend_from_slice(v.borrow())
        }
        result
    }
}

////////////////////////////////////////////////////////////////////////////////
// 切片的标准 trait 实现
////////////////////////////////////////////////////////////////////////////////

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> Borrow<[T]> for Vec<T> {
    fn borrow(&self) -> &[T] {
        &self[..]
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T> BorrowMut<[T]> for Vec<T> {
    fn borrow_mut(&mut self) -> &mut [T] {
        &mut self[..]
    }
}

#[cfg(not(no_global_oom_handling))]
#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Clone> ToOwned for [T] {
    type Owned = Vec<T>;
    #[cfg(not(test))]
    fn to_owned(&self) -> Vec<T> {
        self.to_vec()
    }

    #[cfg(test)]
    fn to_owned(&self) -> Vec<T> {
        hack::to_vec(self, Global)
    }

    fn clone_into(&self, target: &mut Vec<T>) {
        // 丢弃目标中不会被覆盖的任何内容
        target.truncate(self.len());

        // target.len <= self.len 由于上面的截断，因此这里的切片始终是入站的。
        //
        let (init, tail) = self.split_at(target.len());

        // 重用包含的值的 allocations/resources。
        target.clone_from_slice(init);
        target.extend_from_slice(tail);
    }
}

////////////////////////////////////////////////////////////////////////////////
// Sorting
////////////////////////////////////////////////////////////////////////////////

/// 将 `v[0]` 插入到预排序序列 `v[1..]` 中，以便整个 `v[..]` 都被排序。
///
/// 这是插入排序的必不可少的子例程。
#[cfg(not(no_global_oom_handling))]
fn insert_head<T, F>(v: &mut [T], is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    if v.len() >= 2 && is_less(&v[1], &v[0]) {
        unsafe {
            // 这里有三种实现插入的方法:
            //
            // 1. 交换相邻的元素，直到第一个到达其最终目的地。
            //    但是，这样一来，我们就可以复制不必要的数据。
            //    如果元素是大结构 (复制成本很高)，则此方法将很慢。
            //
            // 2. 迭代直到找到第一个元素的正确位置。
            // 然后，移动后继的元素为其腾出空间，最后将其放入剩余的 hole 中。
            // 这是一个好方法。
            //
            // 3. 将第一个元素复制到一个临时变量中。迭代直到找到正确的位置。
            // 在继续操作时，将每个遍历的元素复制到它前面的插槽中。
            // 最后，将数据从临时变量复制到剩余的 hole 中。
            // 这个方法很好。
            // 基准测试显示出比第二种方法更好的性能。
            //
            // 所有方法均进行了基准测试，第 3 种方法显示最佳结果。因此，我们选择了那个。
            let mut tmp = mem::ManuallyDrop::new(ptr::read(&v[0]));

            // `hole` 始终跟踪插入过程的中间状态，这有两个目的:
            // 1. 从 `is_less` 中的 panics 保护 `v` 的完整性。
            // 2. 最后将 `v` 中剩余的 hole 填充。
            //
            // Panic 安全性:
            //
            // 如果在此过程中的任何时候 `is_less` panics，`hole` 都会被丢弃，并用 `tmp` 填充 `v` 中的 hole，从而确保 `v` 仍将其最初持有的每个对象精确地保留一次。
            //
            //
            //
            let mut hole = InsertionHole { src: &mut *tmp, dest: &mut v[1] };
            ptr::copy_nonoverlapping(&v[1], &mut v[0], 1);

            for i in 2..v.len() {
                if !is_less(&v[i], &*tmp) {
                    break;
                }
                ptr::copy_nonoverlapping(&v[i], &mut v[i - 1], 1);
                hole.dest = &mut v[i];
            }
            // `hole` 被丢弃，从而将 `tmp` 复制到 `v` 中剩余的 hole 中。
        }
    }

    // 丢弃时，从 `src` 复制到 `dest`。
    struct InsertionHole<T> {
        src: *mut T,
        dest: *mut T,
    }

    impl<T> Drop for InsertionHole<T> {
        fn drop(&mut self) {
            unsafe {
                ptr::copy_nonoverlapping(self.src, self.dest, 1);
            }
        }
    }
}

/// 使用 `buf` 作为临时存储合并非递减运行 `v[..mid]` 和 `v[mid..]`，并将结果存储到 `v[..]` 中。
///
/// # Safety
///
/// 这两个片必须是非空的，并且 `mid` 必须在范围之内。
/// 缓冲区 `buf` 必须足够长才能容纳较短切片的副本。
/// 另外，`T` 不能为零大小类型。
#[cfg(not(no_global_oom_handling))]
unsafe fn merge<T, F>(v: &mut [T], mid: usize, buf: *mut T, is_less: &mut F)
where
    F: FnMut(&T, &T) -> bool,
{
    let len = v.len();
    let v = v.as_mut_ptr();
    let (v_mid, v_end) = unsafe { (v.add(mid), v.add(len)) };

    // 合并过程首先将较短的运行复制到 `buf` 中。
    // 然后，它将跟踪新复制的运行，以及向前运行 (或向后运行) 的较长运行，比较它们的下一个未消耗元素，并将较小 (或较大) 的运行复制到 `v` 中。
    //
    // 一旦较短的运行时间被完全用尽，该过程就完成了。如果较长的运行首先被消耗，那么我们必须将较短的运行剩下的任何内容复制到 `v` 中剩余的 hole 中。
    //
    // `hole` 始终跟踪过程的中间状态，这有两个目的:
    // 1. 从 `is_less` 中的 panics 保护 `v` 的完整性。
    // 2. 如果较长时间的运行首先被消耗，则将 `v` 中剩余的 hole 填充。
    //
    // Panic 安全性:
    //
    // 如果在此过程中的任何时候 `is_less` panics，`hole` 都会丢弃并用 `buf` 中的未消耗范围填充 `v` 中的 hole，从而确保 `v` 仍将其最初持有的每个对象精确地保留一次。
    //
    //
    //
    //
    //
    let mut hole;

    if mid <= len - mid {
        // 左边的运行更短。
        unsafe {
            ptr::copy_nonoverlapping(v, buf, mid);
            hole = MergeHole { start: buf, end: buf.add(mid), dest: v };
        }

        // 最初，这些指针指向其数组的开头。
        let left = &mut hole.start;
        let mut right = v_mid;
        let out = &mut hole.dest;

        while *left < hole.end && right < v_end {
            // 消耗较小的一面。
            // 如果相等，则选择左旋以保持稳定性。
            unsafe {
                let to_copy = if is_less(&*right, &**left) {
                    get_and_increment(&mut right)
                } else {
                    get_and_increment(left)
                };
                ptr::copy_nonoverlapping(to_copy, get_and_increment(out), 1);
            }
        }
    } else {
        // 右边的运行更短
        unsafe {
            ptr::copy_nonoverlapping(v_mid, buf, len - mid);
            hole = MergeHole { start: buf, end: buf.add(len - mid), dest: v_mid };
        }

        // 最初，这些指针指向其数组的两端。
        let left = &mut hole.dest;
        let right = &mut hole.end;
        let mut out = v_end;

        while v < *left && buf < *right {
            // 消耗更大的一面。
            // 如果相等，则选择正确的行程以保持稳定性。
            unsafe {
                let to_copy = if is_less(&*right.offset(-1), &*left.offset(-1)) {
                    decrement_and_get(left)
                } else {
                    decrement_and_get(right)
                };
                ptr::copy_nonoverlapping(to_copy, decrement_and_get(&mut out), 1);
            }
        }
    }
    // 最后，`hole` 被丢弃。
    // 如果较短的运行没有被完全消耗，则其剩余的任何内容现在都将被复制到 `v` 的 hole 中。

    unsafe fn get_and_increment<T>(ptr: &mut *mut T) -> *mut T {
        let old = *ptr;
        *ptr = unsafe { ptr.offset(1) };
        old
    }

    unsafe fn decrement_and_get<T>(ptr: &mut *mut T) -> *mut T {
        *ptr = unsafe { ptr.offset(-1) };
        *ptr
    }

    // 丢弃时，将范围 `start..end` 复制到 `dest..`。
    struct MergeHole<T> {
        start: *mut T,
        end: *mut T,
        dest: *mut T,
    }

    impl<T> Drop for MergeHole<T> {
        fn drop(&mut self) {
            // `T` 不是零大小的类型，因此可以将其除以大小。
            let len = (self.end as usize - self.start as usize) / mem::size_of::<T>();
            unsafe {
                ptr::copy_nonoverlapping(self.start, self.dest, len);
            }
        }
    }
}

/// 这个归并排序借用了 TimSort 的一些 (但不是全部) 想法，在 [这里](https://github.com/python/cpython/blob/main/Objects/listsort.txt) 有详细描述。
///
///
/// 该算法识别严格降序和非降序的子序列，这些子序列称为自然行程。有待合并的待处理运行栈。
/// 将每个新发现的运行推入栈，然后合并几对相邻的运行，直到满足这两个不可变变量:
///
/// 1. 对于 `1..runs.len()` 中的每个 `i`: `runs[i - 1].len > runs[i].len`
/// 2. 对于 `2..runs.len()` 中的每个 `i`: `runs[i - 2].len > runs[i - 1].len + runs[i].len`
///
/// 不可变变量确保总运行时间为 *O*(*n*\*log(* n*)) 最坏的情况。
///
///
#[cfg(not(no_global_oom_handling))]
fn merge_sort<T, F>(v: &mut [T], mut is_less: F)
where
    F: FnMut(&T, &T) -> bool,
{
    // 长度不超过此长度的切片将使用插入排序进行排序。
    const MAX_INSERTION: usize = 20;
    // 使用插入排序可扩展非常短的运行时间，以至少涵盖这么多的元素。
    const MIN_RUN: usize = 10;

    // 零大小类型的排序没有有意义的行为。
    if size_of::<T>() == 0 {
        return;
    }

    let len = v.len();

    // 短数组通过插入排序进行就地排序，以避免分配。
    if len <= MAX_INSERTION {
        if len >= 2 {
            for i in (0..len - 1).rev() {
                insert_head(&mut v[i..], &mut is_less);
            }
        }
        return;
    }

    // 分配缓冲区以用作暂存器。我们将长度保持为 0，这样就可以在其中保留 `v` 内容的浅表副本，而不会冒 `is_less` panics 在副本上运行 dtor 的风险。
    //
    // 合并两个已排序的运行时，此缓冲区将保存一个较短运行的副本，该副本的长度始终最多为 `len / 2`。
    //
    let mut buf = Vec::with_capacity(len / 2);

    // 为了识别 `v` 中的自然行程，我们将其向后移动。
    // 这看起来似乎是一个奇怪的决定，但请考虑以下事实: 合并更多是朝相反的方向 (forwards) 进行。
    // 根据基准，向前合并比向后合并要快一些。
    // 总而言之，通过向后遍历来识别运行可提高性能。
    let mut runs = vec![];
    let mut end = len;
    while end > 0 {
        // 找到下一个自然行程，如果严格下降，则将其反转。
        let mut start = end - 1;
        if start > 0 {
            start -= 1;
            unsafe {
                if is_less(v.get_unchecked(start + 1), v.get_unchecked(start)) {
                    while start > 0 && is_less(v.get_unchecked(start), v.get_unchecked(start - 1)) {
                        start -= 1;
                    }
                    v[start..end].reverse();
                } else {
                    while start > 0 && !is_less(v.get_unchecked(start), v.get_unchecked(start - 1))
                    {
                        start -= 1;
                    }
                }
            }
        }

        // 如果过短，请在运行中插入更多元素。
        // 插入排序比短序列上的合并排序要快，因此可以显着提高性能。
        while start > 0 && end - start < MIN_RUN {
            start -= 1;
            insert_head(&mut v[start..end], &mut is_less);
        }

        // 将此运行推入栈。
        runs.push(Run { start, len: end - start });
        end = start;

        // 合并一些成对的相邻行程以满足不变性。
        while let Some(r) = collapse(&runs) {
            let left = runs[r + 1];
            let right = runs[r];
            unsafe {
                merge(
                    &mut v[left.start..right.start + right.len],
                    left.len,
                    buf.as_mut_ptr(),
                    &mut is_less,
                );
            }
            runs[r] = Run { start: left.start, len: left.len + right.len };
            runs.remove(r + 1);
        }
    }

    // 最后，必须在栈中仅保留一次运行。
    debug_assert!(runs.len() == 1 && runs[0].start == 0 && runs[0].len == len);

    // 检查运行栈，并确定要合并的下一对运行。
    // 更具体地说，如果返回 `Some(r)`，则意味着接下来必须合并 `runs[r]` 和 `runs[r + 1]`。
    // 如果算法应继续构建新的运行，则返回 `None`。
    //
    // TimSort 因其 buggy 实现而臭名昭著，如下所述:
    // http://envisage-project.eu/timsort-specification-and-verification/
    //
    // 故事的要旨是: 我们必须在栈的前四个运行中强制执行不变式。
    // 仅在前三个上强制执行它们不足以确保不可变变量仍然适用于栈中的所有运行。
    //
    // 此函数正确检查前四个运行的不可变变量。
    // 另外，如果最高运行从索引 0 开始，它将始终要求合并操作，直到栈完全展开为止，以完成排序。
    //
    //
    #[inline]
    fn collapse(runs: &[Run]) -> Option<usize> {
        let n = runs.len();
        if n >= 2
            && (runs[n - 1].start == 0
                || runs[n - 2].len <= runs[n - 1].len
                || (n >= 3 && runs[n - 3].len <= runs[n - 2].len + runs[n - 1].len)
                || (n >= 4 && runs[n - 4].len <= runs[n - 3].len + runs[n - 2].len))
        {
            if n >= 3 && runs[n - 3].len < runs[n - 1].len { Some(n - 3) } else { Some(n - 2) }
        } else {
            None
        }
    }

    #[derive(Clone, Copy)]
    struct Run {
        start: usize,
        len: usize,
    }
}