1 | //! Comparison traits for `[T]`. |
2 | |
3 | use super::{from_raw_parts, memchr}; |
4 | use crate::ascii; |
5 | use crate::cmp::{self, BytewiseEq, Ordering}; |
6 | use crate::intrinsics::compare_bytes; |
7 | use crate::num::NonZero; |
8 | |
9 | #[stable (feature = "rust1" , since = "1.0.0" )] |
10 | impl<T, U> PartialEq<[U]> for [T] |
11 | where |
12 | T: PartialEq<U>, |
13 | { |
14 | fn eq(&self, other: &[U]) -> bool { |
15 | SlicePartialEq::equal(self, other) |
16 | } |
17 | |
18 | fn ne(&self, other: &[U]) -> bool { |
19 | SlicePartialEq::not_equal(self, other) |
20 | } |
21 | } |
22 | |
23 | #[stable (feature = "rust1" , since = "1.0.0" )] |
24 | impl<T: Eq> Eq for [T] {} |
25 | |
26 | /// Implements comparison of slices [lexicographically](Ord#lexicographical-comparison). |
27 | #[stable (feature = "rust1" , since = "1.0.0" )] |
28 | impl<T: Ord> Ord for [T] { |
29 | fn cmp(&self, other: &[T]) -> Ordering { |
30 | SliceOrd::compare(self, right:other) |
31 | } |
32 | } |
33 | |
34 | /// Implements comparison of slices [lexicographically](Ord#lexicographical-comparison). |
35 | #[stable (feature = "rust1" , since = "1.0.0" )] |
36 | impl<T: PartialOrd> PartialOrd for [T] { |
37 | fn partial_cmp(&self, other: &[T]) -> Option<Ordering> { |
38 | SlicePartialOrd::partial_compare(self, right:other) |
39 | } |
40 | } |
41 | |
42 | #[doc (hidden)] |
43 | // intermediate trait for specialization of slice's PartialEq |
44 | trait SlicePartialEq<B> { |
45 | fn equal(&self, other: &[B]) -> bool; |
46 | |
47 | fn not_equal(&self, other: &[B]) -> bool { |
48 | !self.equal(other) |
49 | } |
50 | } |
51 | |
52 | // Generic slice equality |
53 | impl<A, B> SlicePartialEq<B> for [A] |
54 | where |
55 | A: PartialEq<B>, |
56 | { |
57 | default fn equal(&self, other: &[B]) -> bool { |
58 | if self.len() != other.len() { |
59 | return false; |
60 | } |
61 | |
62 | // Implemented as explicit indexing rather |
63 | // than zipped iterators for performance reasons. |
64 | // See PR https://github.com/rust-lang/rust/pull/116846 |
65 | for idx: usize in 0..self.len() { |
66 | // bound checks are optimized away |
67 | if self[idx] != other[idx] { |
68 | return false; |
69 | } |
70 | } |
71 | |
72 | true |
73 | } |
74 | } |
75 | |
76 | // When each element can be compared byte-wise, we can compare all the bytes |
77 | // from the whole size in one call to the intrinsics. |
78 | impl<A, B> SlicePartialEq<B> for [A] |
79 | where |
80 | A: BytewiseEq<B>, |
81 | { |
82 | fn equal(&self, other: &[B]) -> bool { |
83 | if self.len() != other.len() { |
84 | return false; |
85 | } |
86 | |
87 | // SAFETY: `self` and `other` are references and are thus guaranteed to be valid. |
88 | // The two slices have been checked to have the same size above. |
89 | unsafe { |
90 | let size: usize = size_of_val(self); |
91 | compare_bytes(self.as_ptr() as *const u8, right:other.as_ptr() as *const u8, bytes:size) == 0 |
92 | } |
93 | } |
94 | } |
95 | |
96 | #[doc (hidden)] |
97 | // intermediate trait for specialization of slice's PartialOrd |
98 | trait SlicePartialOrd: Sized { |
99 | fn partial_compare(left: &[Self], right: &[Self]) -> Option<Ordering>; |
100 | } |
101 | |
102 | impl<A: PartialOrd> SlicePartialOrd for A { |
103 | default fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> { |
104 | let l: usize = cmp::min(v1:left.len(), v2:right.len()); |
105 | |
106 | // Slice to the loop iteration range to enable bound check |
107 | // elimination in the compiler |
108 | let lhs: &[A] = &left[..l]; |
109 | let rhs: &[A] = &right[..l]; |
110 | |
111 | for i: usize in 0..l { |
112 | match lhs[i].partial_cmp(&rhs[i]) { |
113 | Some(Ordering::Equal) => (), |
114 | non_eq: Option => return non_eq, |
115 | } |
116 | } |
117 | |
118 | left.len().partial_cmp(&right.len()) |
119 | } |
120 | } |
121 | |
122 | // This is the impl that we would like to have. Unfortunately it's not sound. |
123 | // See `partial_ord_slice.rs`. |
124 | /* |
125 | impl<A> SlicePartialOrd for A |
126 | where |
127 | A: Ord, |
128 | { |
129 | default fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> { |
130 | Some(SliceOrd::compare(left, right)) |
131 | } |
132 | } |
133 | */ |
134 | |
135 | impl<A: AlwaysApplicableOrd> SlicePartialOrd for A { |
136 | fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> { |
137 | Some(SliceOrd::compare(left, right)) |
138 | } |
139 | } |
140 | |
141 | #[rustc_specialization_trait ] |
142 | trait AlwaysApplicableOrd: SliceOrd + Ord {} |
143 | |
144 | macro_rules! always_applicable_ord { |
145 | ($([$($p:tt)*] $t:ty,)*) => { |
146 | $(impl<$($p)*> AlwaysApplicableOrd for $t {})* |
147 | } |
148 | } |
149 | |
150 | always_applicable_ord! { |
151 | [] u8, [] u16, [] u32, [] u64, [] u128, [] usize, |
152 | [] i8, [] i16, [] i32, [] i64, [] i128, [] isize, |
153 | [] bool, [] char, |
154 | [T: ?Sized] *const T, [T: ?Sized] *mut T, |
155 | [T: AlwaysApplicableOrd] &T, |
156 | [T: AlwaysApplicableOrd] &mut T, |
157 | [T: AlwaysApplicableOrd] Option<T>, |
158 | } |
159 | |
160 | #[doc (hidden)] |
161 | // intermediate trait for specialization of slice's Ord |
162 | trait SliceOrd: Sized { |
163 | fn compare(left: &[Self], right: &[Self]) -> Ordering; |
164 | } |
165 | |
166 | impl<A: Ord> SliceOrd for A { |
167 | default fn compare(left: &[Self], right: &[Self]) -> Ordering { |
168 | let l: usize = cmp::min(v1:left.len(), v2:right.len()); |
169 | |
170 | // Slice to the loop iteration range to enable bound check |
171 | // elimination in the compiler |
172 | let lhs: &[A] = &left[..l]; |
173 | let rhs: &[A] = &right[..l]; |
174 | |
175 | for i: usize in 0..l { |
176 | match lhs[i].cmp(&rhs[i]) { |
177 | Ordering::Equal => (), |
178 | non_eq: Ordering => return non_eq, |
179 | } |
180 | } |
181 | |
182 | left.len().cmp(&right.len()) |
183 | } |
184 | } |
185 | |
186 | /// Marks that a type should be treated as an unsigned byte for comparisons. |
187 | /// |
188 | /// # Safety |
189 | /// * The type must be readable as an `u8`, meaning it has to have the same |
190 | /// layout as `u8` and always be initialized. |
191 | /// * For every `x` and `y` of this type, `Ord(x, y)` must return the same |
192 | /// value as `Ord::cmp(transmute::<_, u8>(x), transmute::<_, u8>(y))`. |
193 | #[rustc_specialization_trait ] |
194 | unsafe trait UnsignedBytewiseOrd {} |
195 | |
196 | unsafe impl UnsignedBytewiseOrd for bool {} |
197 | unsafe impl UnsignedBytewiseOrd for u8 {} |
198 | unsafe impl UnsignedBytewiseOrd for NonZero<u8> {} |
199 | unsafe impl UnsignedBytewiseOrd for Option<NonZero<u8>> {} |
200 | unsafe impl UnsignedBytewiseOrd for ascii::Char {} |
201 | |
202 | // `compare_bytes` compares a sequence of unsigned bytes lexicographically, so |
203 | // use it if the requirements for `UnsignedBytewiseOrd` are fulfilled. |
204 | impl<A: Ord + UnsignedBytewiseOrd> SliceOrd for A { |
205 | #[inline ] |
206 | fn compare(left: &[Self], right: &[Self]) -> Ordering { |
207 | // Since the length of a slice is always less than or equal to |
208 | // isize::MAX, this never underflows. |
209 | let diff: isize = left.len() as isize - right.len() as isize; |
210 | // This comparison gets optimized away (on x86_64 and ARM) because the |
211 | // subtraction updates flags. |
212 | let len: usize = if left.len() < right.len() { left.len() } else { right.len() }; |
213 | let left: *const u8 = left.as_ptr().cast(); |
214 | let right: *const u8 = right.as_ptr().cast(); |
215 | // SAFETY: `left` and `right` are references and are thus guaranteed to |
216 | // be valid. `UnsignedBytewiseOrd` is only implemented for types that |
217 | // are valid u8s and can be compared the same way. We use the minimum |
218 | // of both lengths which guarantees that both regions are valid for |
219 | // reads in that interval. |
220 | let mut order: isize = unsafe { compare_bytes(left, right, bytes:len) as isize }; |
221 | if order == 0 { |
222 | order = diff; |
223 | } |
224 | order.cmp(&0) |
225 | } |
226 | } |
227 | |
228 | pub(super) trait SliceContains: Sized { |
229 | fn slice_contains(&self, x: &[Self]) -> bool; |
230 | } |
231 | |
232 | impl<T> SliceContains for T |
233 | where |
234 | T: PartialEq, |
235 | { |
236 | default fn slice_contains(&self, x: &[Self]) -> bool { |
237 | x.iter().any(|y: &T| *y == *self) |
238 | } |
239 | } |
240 | |
241 | impl SliceContains for u8 { |
242 | #[inline ] |
243 | fn slice_contains(&self, x: &[Self]) -> bool { |
244 | memchr::memchr(*self, text:x).is_some() |
245 | } |
246 | } |
247 | |
248 | impl SliceContains for i8 { |
249 | #[inline ] |
250 | fn slice_contains(&self, x: &[Self]) -> bool { |
251 | let byte: u8 = *self as u8; |
252 | // SAFETY: `i8` and `u8` have the same memory layout, thus casting `x.as_ptr()` |
253 | // as `*const u8` is safe. The `x.as_ptr()` comes from a reference and is thus guaranteed |
254 | // to be valid for reads for the length of the slice `x.len()`, which cannot be larger |
255 | // than `isize::MAX`. The returned slice is never mutated. |
256 | let bytes: &[u8] = unsafe { from_raw_parts(data:x.as_ptr() as *const u8, x.len()) }; |
257 | memchr::memchr(x:byte, text:bytes).is_some() |
258 | } |
259 | } |
260 | |
261 | macro_rules! impl_slice_contains { |
262 | ($($t:ty),*) => { |
263 | $( |
264 | impl SliceContains for $t { |
265 | #[inline] |
266 | fn slice_contains(&self, arr: &[$t]) -> bool { |
267 | // Make our LANE_COUNT 4x the normal lane count (aiming for 128 bit vectors). |
268 | // The compiler will nicely unroll it. |
269 | const LANE_COUNT: usize = 4 * (128 / (size_of::<$t>() * 8)); |
270 | // SIMD |
271 | let mut chunks = arr.chunks_exact(LANE_COUNT); |
272 | for chunk in &mut chunks { |
273 | if chunk.iter().fold(false, |acc, x| acc | (*x == *self)) { |
274 | return true; |
275 | } |
276 | } |
277 | // Scalar remainder |
278 | return chunks.remainder().iter().any(|x| *x == *self); |
279 | } |
280 | } |
281 | )* |
282 | }; |
283 | } |
284 | |
285 | impl_slice_contains!(u16, u32, u64, i16, i32, i64, f32, f64, usize, isize, char); |
286 | |