//! 比较 `[T]` 的 traits。

use crate::cmp;
use crate::cmp::Ordering::{self, Greater, Less};
use crate::mem;

use super::from_raw_parts;
use super::memchr;

extern "C" {
    /// 调用实现提供了 memcmp。
    ///
    /// 将数据解释为 u8。
    ///
    /// 返回等于 0 的 < 0，小于等于 0，大于等于 0。
    ///
    // FIXME(#32610): 返回类型应为 c_int
    fn memcmp(s1: *const u8, s2: *const u8, n: usize) -> i32;
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> PartialEq<[B]> for [A]
where
    A: PartialEq<B>,
{
    fn eq(&self, other: &[B]) -> bool {
        SlicePartialEq::equal(self, other)
    }

    fn ne(&self, other: &[B]) -> bool {
        SlicePartialEq::not_equal(self, other)
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Eq> Eq for [T] {}

/// 实现 vectors [lexicographically](Ord#lexicographical-comparison) 的比较。
#[stable(feature = "rust1", since = "1.0.0")]
impl<T: Ord> Ord for [T] {
    fn cmp(&self, other: &[T]) -> Ordering {
        SliceOrd::compare(self, other)
    }
}

/// 实现 vectors [lexicographically](Ord#lexicographical-comparison) 的比较。
#[stable(feature = "rust1", since = "1.0.0")]
impl<T: PartialOrd> PartialOrd for [T] {
    fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
        SlicePartialOrd::partial_compare(self, other)
    }
}

#[doc(hidden)]
// 专门用于切片的 PartialEq 的中间 trait
trait SlicePartialEq<B> {
    fn equal(&self, other: &[B]) -> bool;

    fn not_equal(&self, other: &[B]) -> bool {
        !self.equal(other)
    }
}

// 泛型切片平等
impl<A, B> SlicePartialEq<B> for [A]
where
    A: PartialEq<B>,
{
    default fn equal(&self, other: &[B]) -> bool {
        if self.len() != other.len() {
            return false;
        }

        self.iter().zip(other.iter()).all(|(x, y)| x == y)
    }
}

// 当类型允许时，使用 memcmp 进行按字节相等
impl<A, B> SlicePartialEq<B> for [A]
where
    A: BytewiseEquality<B>,
{
    fn equal(&self, other: &[B]) -> bool {
        if self.len() != other.len() {
            return false;
        }

        // SAFETY: `self` 和 `other` 是引用，因此可以保证是有效的。
        // 上面已经检查了两个切片的大小是否相同。
        unsafe {
            let size = mem::size_of_val(self);
            memcmp(self.as_ptr() as *const u8, other.as_ptr() as *const u8, size) == 0
        }
    }
}

#[doc(hidden)]
// 专门用于切片 PartialOrd 的中间 trait
trait SlicePartialOrd: Sized {
    fn partial_compare(left: &[Self], right: &[Self]) -> Option<Ordering>;
}

impl<A: PartialOrd> SlicePartialOrd for A {
    default fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
        let l = cmp::min(left.len(), right.len());

        // 切片到循环迭代范围，以在编译器中启用边界检查消除
        //
        let lhs = &left[..l];
        let rhs = &right[..l];

        for i in 0..l {
            match lhs[i].partial_cmp(&rhs[i]) {
                Some(Ordering::Equal) => (),
                non_eq => return non_eq,
            }
        }

        left.len().partial_cmp(&right.len())
    }
}

// 这就是我们想要的暗示。不幸的是，这不是声音。
// 请参见 `partial_ord_slice.rs`。
/*
impl<A> SlicePartialOrd for A
where
    A: Ord,
{
    default fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
        Some(SliceOrd::compare(left, right))
    }
}
*/

impl<A: AlwaysApplicableOrd> SlicePartialOrd for A {
    fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
        Some(SliceOrd::compare(left, right))
    }
}

#[rustc_specialization_trait]
trait AlwaysApplicableOrd: SliceOrd + Ord {}

macro_rules! always_applicable_ord {
    ($([$($p:tt)*] $t:ty,)*) => {
        $(impl<$($p)*> AlwaysApplicableOrd for $t {})*
    }
}

always_applicable_ord! {
    [] u8, [] u16, [] u32, [] u64, [] u128, [] usize,
    [] i8, [] i16, [] i32, [] i64, [] i128, [] isize,
    [] bool, [] char,
    [T: ?Sized] *const T, [T: ?Sized] *mut T,
    [T: AlwaysApplicableOrd] &T,
    [T: AlwaysApplicableOrd] &mut T,
    [T: AlwaysApplicableOrd] Option<T>,
}

#[doc(hidden)]
// 用于切片 Ord 专业化的中间 trait
trait SliceOrd: Sized {
    fn compare(left: &[Self], right: &[Self]) -> Ordering;
}

impl<A: Ord> SliceOrd for A {
    default fn compare(left: &[Self], right: &[Self]) -> Ordering {
        let l = cmp::min(left.len(), right.len());

        // 切片到循环迭代范围，以在编译器中启用边界检查消除
        //
        let lhs = &left[..l];
        let rhs = &right[..l];

        for i in 0..l {
            match lhs[i].cmp(&rhs[i]) {
                Ordering::Equal => (),
                non_eq => return non_eq,
            }
        }

        left.len().cmp(&right.len())
    }
}

// memcmp 按字典顺序比较无符号字节序列。
// 这与我们想要的 [u8] 顺序相匹配，但没有其他顺序 (甚至 [i8] 也没有)。
impl SliceOrd for u8 {
    #[inline]
    fn compare(left: &[Self], right: &[Self]) -> Ordering {
        let order =
            // SAFETY: `left` 和 `right` 是引用，因此可以保证是有效的。
            // 我们使用两个长度中的最小值，以确保两个区域都适用于该时间间隔内的读取。
            //
            unsafe { memcmp(left.as_ptr(), right.as_ptr(), cmp::min(left.len(), right.len())) };
        if order == 0 {
            left.len().cmp(&right.len())
        } else if order < 0 {
            Less
        } else {
            Greater
        }
    }
}

// 即使 `Eq` 有一种方法，也可以允许专门研究 `Eq`。
#[rustc_unsafe_specialization_marker]
trait MarkerEq<T>: PartialEq<T> {}

impl<T: Eq> MarkerEq<T> for T {}

#[doc(hidden)]
/// Trait 为可使用其字节表示形式进行相等性比较的类型实现
///
#[rustc_specialization_trait]
trait BytewiseEquality<T>: MarkerEq<T> + Copy {}

macro_rules! impl_marker_for {
    ($traitname:ident, $($ty:ty)*) => {
        $(
            impl $traitname<$ty> for $ty { }
        )*
    }
}

impl_marker_for!(BytewiseEquality,
                 u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize char bool);

pub(super) trait SliceContains: Sized {
    fn slice_contains(&self, x: &[Self]) -> bool;
}

impl<T> SliceContains for T
where
    T: PartialEq,
{
    default fn slice_contains(&self, x: &[Self]) -> bool {
        x.iter().any(|y| *y == *self)
    }
}

impl SliceContains for u8 {
    #[inline]
    fn slice_contains(&self, x: &[Self]) -> bool {
        memchr::memchr(*self, x).is_some()
    }
}

impl SliceContains for i8 {
    #[inline]
    fn slice_contains(&self, x: &[Self]) -> bool {
        let byte = *self as u8;
        // SAFETY: `i8` 和 `u8` 具有相同的内存布局，因此将 `x.as_ptr()` 强制转换为 `*const u8` 是安全的。
        // `x.as_ptr()` 来自引用，因此可以保证对切片 `x.len()` 的长度有效，该长度不能大于 `isize::MAX`。
        //
        // 返回的切片永远不会发生可变的。
        let bytes: &[u8] = unsafe { from_raw_parts(x.as_ptr() as *const u8, x.len()) };
        memchr::memchr(byte, bytes).is_some()
    }
}