1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
//! 比较 `[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()
    }
}