1//! Comparison traits for `[T]`.
2
3use super::{from_raw_parts, memchr};
4use crate::ascii;
5use crate::cmp::{self, BytewiseEq, Ordering};
6use crate::intrinsics::compare_bytes;
7use crate::num::NonZero;
8use crate::ops::ControlFlow;
9
10#[stable(feature = "rust1", since = "1.0.0")]
11#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
12impl<T, U> const PartialEq<[U]> for [T]
13where
14 T: [const] PartialEq<U>,
15{
16 fn eq(&self, other: &[U]) -> bool {
17 SlicePartialEq::equal(self, other)
18 }
19
20 fn ne(&self, other: &[U]) -> bool {
21 SlicePartialEq::not_equal(self, other)
22 }
23}
24
25#[stable(feature = "rust1", since = "1.0.0")]
26#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
27impl<T: [const] Eq> const Eq for [T] {}
28
29/// Implements comparison of slices [lexicographically](Ord#lexicographical-comparison).
30#[stable(feature = "rust1", since = "1.0.0")]
31impl<T: Ord> Ord for [T] {
32 fn cmp(&self, other: &[T]) -> Ordering {
33 SliceOrd::compare(self, right:other)
34 }
35}
36
37#[inline]
38const fn as_underlying(x: ControlFlow<bool>) -> u8 {
39 // SAFETY: This will only compile if `bool` and `ControlFlow<bool>` have the same
40 // size (which isn't guaranteed but this is libcore). Because they have the same
41 // size, it's a niched implementation, which in one byte means there can't be
42 // any uninitialized memory. The callers then only check for `0` or `1` from this,
43 // which must necessarily match the `Break` variant, and we're fine no matter
44 // what ends up getting picked as the value representing `Continue(())`.
45 unsafe { crate::mem::transmute(src:x) }
46}
47
48/// Implements comparison of slices [lexicographically](Ord#lexicographical-comparison).
49#[stable(feature = "rust1", since = "1.0.0")]
50impl<T: PartialOrd> PartialOrd for [T] {
51 #[inline]
52 fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
53 SlicePartialOrd::partial_compare(self, other)
54 }
55 #[inline]
56 fn lt(&self, other: &Self) -> bool {
57 // This is certainly not the obvious way to implement these methods.
58 // Unfortunately, using anything that looks at the discriminant means that
59 // LLVM sees a check for `2` (aka `ControlFlow<bool>::Continue(())`) and
60 // gets very distracted by that, ending up generating extraneous code.
61 // This should be changed to something simpler once either LLVM is smarter,
62 // see <https://github.com/llvm/llvm-project/issues/132678>, or we generate
63 // niche discriminant checks in a way that doesn't trigger it.
64
65 as_underlying(self.__chaining_lt(other)) == 1
66 }
67 #[inline]
68 fn le(&self, other: &Self) -> bool {
69 as_underlying(self.__chaining_le(other)) != 0
70 }
71 #[inline]
72 fn gt(&self, other: &Self) -> bool {
73 as_underlying(self.__chaining_gt(other)) == 1
74 }
75 #[inline]
76 fn ge(&self, other: &Self) -> bool {
77 as_underlying(self.__chaining_ge(other)) != 0
78 }
79 #[inline]
80 fn __chaining_lt(&self, other: &Self) -> ControlFlow<bool> {
81 SliceChain::chaining_lt(self, other)
82 }
83 #[inline]
84 fn __chaining_le(&self, other: &Self) -> ControlFlow<bool> {
85 SliceChain::chaining_le(self, other)
86 }
87 #[inline]
88 fn __chaining_gt(&self, other: &Self) -> ControlFlow<bool> {
89 SliceChain::chaining_gt(self, other)
90 }
91 #[inline]
92 fn __chaining_ge(&self, other: &Self) -> ControlFlow<bool> {
93 SliceChain::chaining_ge(self, other)
94 }
95}
96
97#[doc(hidden)]
98// intermediate trait for specialization of slice's PartialEq
99#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
100const trait SlicePartialEq<B> {
101 fn equal(&self, other: &[B]) -> bool;
102
103 fn not_equal(&self, other: &[B]) -> bool {
104 !self.equal(other)
105 }
106}
107
108// Generic slice equality
109#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
110impl<A, B> const SlicePartialEq<B> for [A]
111where
112 A: [const] PartialEq<B>,
113{
114 default fn equal(&self, other: &[B]) -> bool {
115 if self.len() != other.len() {
116 return false;
117 }
118
119 // Implemented as explicit indexing rather
120 // than zipped iterators for performance reasons.
121 // See PR https://github.com/rust-lang/rust/pull/116846
122 // FIXME(const_hack): make this a `for idx in 0..self.len()` loop.
123 let mut idx: usize = 0;
124 while idx < self.len() {
125 // bound checks are optimized away
126 if self[idx] != other[idx] {
127 return false;
128 }
129 idx += 1;
130 }
131
132 true
133 }
134}
135
136// When each element can be compared byte-wise, we can compare all the bytes
137// from the whole size in one call to the intrinsics.
138#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
139impl<A, B> const SlicePartialEq<B> for [A]
140where
141 A: [const] BytewiseEq<B>,
142{
143 fn equal(&self, other: &[B]) -> bool {
144 if self.len() != other.len() {
145 return false;
146 }
147
148 // SAFETY: `self` and `other` are references and are thus guaranteed to be valid.
149 // The two slices have been checked to have the same size above.
150 unsafe {
151 let size: usize = size_of_val(self);
152 compare_bytes(self.as_ptr() as *const u8, right:other.as_ptr() as *const u8, bytes:size) == 0
153 }
154 }
155}
156
157#[doc(hidden)]
158#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
159// intermediate trait for specialization of slice's PartialOrd
160const trait SlicePartialOrd: Sized {
161 fn partial_compare(left: &[Self], right: &[Self]) -> Option<Ordering>;
162}
163
164#[doc(hidden)]
165#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
166// intermediate trait for specialization of slice's PartialOrd chaining methods
167const trait SliceChain: Sized {
168 fn chaining_lt(left: &[Self], right: &[Self]) -> ControlFlow<bool>;
169 fn chaining_le(left: &[Self], right: &[Self]) -> ControlFlow<bool>;
170 fn chaining_gt(left: &[Self], right: &[Self]) -> ControlFlow<bool>;
171 fn chaining_ge(left: &[Self], right: &[Self]) -> ControlFlow<bool>;
172}
173
174type AlwaysBreak<B> = ControlFlow<B, crate::convert::Infallible>;
175
176impl<A: PartialOrd> SlicePartialOrd for A {
177 default fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
178 let elem_chain: impl Fn(&A, &A) -> ControlFlow<…> = |a: &A, b: &A| match PartialOrd::partial_cmp(self:a, other:b) {
179 Some(Ordering::Equal) => ControlFlow::Continue(()),
180 non_eq: Option => ControlFlow::Break(non_eq),
181 };
182 let len_chain: impl Fn(&usize, &usize) -> … = |a: &_, b: &_| ControlFlow::Break(usize::partial_cmp(self:a, other:b));
183 let AlwaysBreak::Break(b: Option) = chaining_impl(left, right, elem_chain, len_chain);
184 b
185 }
186}
187
188impl<A: PartialOrd> SliceChain for A {
189 default fn chaining_lt(left: &[Self], right: &[Self]) -> ControlFlow<bool> {
190 chaining_impl(left, right, elem_chain:PartialOrd::__chaining_lt, len_chain:usize::__chaining_lt)
191 }
192 default fn chaining_le(left: &[Self], right: &[Self]) -> ControlFlow<bool> {
193 chaining_impl(left, right, elem_chain:PartialOrd::__chaining_le, len_chain:usize::__chaining_le)
194 }
195 default fn chaining_gt(left: &[Self], right: &[Self]) -> ControlFlow<bool> {
196 chaining_impl(left, right, elem_chain:PartialOrd::__chaining_gt, len_chain:usize::__chaining_gt)
197 }
198 default fn chaining_ge(left: &[Self], right: &[Self]) -> ControlFlow<bool> {
199 chaining_impl(left, right, elem_chain:PartialOrd::__chaining_ge, len_chain:usize::__chaining_ge)
200 }
201}
202
203#[inline]
204fn chaining_impl<'l, 'r, A: PartialOrd, B, C>(
205 left: &'l [A],
206 right: &'r [A],
207 elem_chain: impl Fn(&'l A, &'r A) -> ControlFlow<B>,
208 len_chain: impl for<'a> FnOnce(&'a usize, &'a usize) -> ControlFlow<B, C>,
209) -> ControlFlow<B, C> {
210 let l: usize = cmp::min(v1:left.len(), v2:right.len());
211
212 // Slice to the loop iteration range to enable bound check
213 // elimination in the compiler
214 let lhs: &[A] = &left[..l];
215 let rhs: &[A] = &right[..l];
216
217 for i: usize in 0..l {
218 elem_chain(&lhs[i], &rhs[i])?;
219 }
220
221 len_chain(&left.len(), &right.len())
222}
223
224// This is the impl that we would like to have. Unfortunately it's not sound.
225// See `partial_ord_slice.rs`.
226/*
227impl<A> SlicePartialOrd for A
228where
229 A: Ord,
230{
231 default fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
232 Some(SliceOrd::compare(left, right))
233 }
234}
235*/
236
237#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
238impl<A: [const] AlwaysApplicableOrd> const SlicePartialOrd for A {
239 fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
240 Some(SliceOrd::compare(left, right))
241 }
242}
243
244#[rustc_specialization_trait]
245#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
246const trait AlwaysApplicableOrd: [const] SliceOrd + [const] Ord {}
247
248macro_rules! always_applicable_ord {
249 ($([$($p:tt)*] $t:ty,)*) => {
250 $(impl<$($p)*> AlwaysApplicableOrd for $t {})*
251 }
252}
253
254always_applicable_ord! {
255 [] u8, [] u16, [] u32, [] u64, [] u128, [] usize,
256 [] i8, [] i16, [] i32, [] i64, [] i128, [] isize,
257 [] bool, [] char,
258 [T: ?Sized] *const T, [T: ?Sized] *mut T,
259 [T: AlwaysApplicableOrd] &T,
260 [T: AlwaysApplicableOrd] &mut T,
261 [T: AlwaysApplicableOrd] Option<T>,
262}
263
264#[doc(hidden)]
265#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
266// intermediate trait for specialization of slice's Ord
267const trait SliceOrd: Sized {
268 fn compare(left: &[Self], right: &[Self]) -> Ordering;
269}
270
271impl<A: Ord> SliceOrd for A {
272 default fn compare(left: &[Self], right: &[Self]) -> Ordering {
273 let elem_chain: impl Fn(&A, &A) -> ControlFlow<…> = |a: &A, b: &A| match Ord::cmp(self:a, other:b) {
274 Ordering::Equal => ControlFlow::Continue(()),
275 non_eq: Ordering => ControlFlow::Break(non_eq),
276 };
277 let len_chain: impl Fn(&usize, &usize) -> … = |a: &_, b: &_| ControlFlow::Break(usize::cmp(self:a, other:b));
278 let AlwaysBreak::Break(b: Ordering) = chaining_impl(left, right, elem_chain, len_chain);
279 b
280 }
281}
282
283/// Marks that a type should be treated as an unsigned byte for comparisons.
284///
285/// # Safety
286/// * The type must be readable as an `u8`, meaning it has to have the same
287/// layout as `u8` and always be initialized.
288/// * For every `x` and `y` of this type, `Ord(x, y)` must return the same
289/// value as `Ord::cmp(transmute::<_, u8>(x), transmute::<_, u8>(y))`.
290#[rustc_specialization_trait]
291const unsafe trait UnsignedBytewiseOrd: [const] Ord {}
292
293#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
294unsafe impl const UnsignedBytewiseOrd for bool {}
295#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
296unsafe impl const UnsignedBytewiseOrd for u8 {}
297#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
298unsafe impl const UnsignedBytewiseOrd for NonZero<u8> {}
299#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
300unsafe impl const UnsignedBytewiseOrd for Option<NonZero<u8>> {}
301#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
302unsafe impl const UnsignedBytewiseOrd for ascii::Char {}
303
304// `compare_bytes` compares a sequence of unsigned bytes lexicographically, so
305// use it if the requirements for `UnsignedBytewiseOrd` are fulfilled.
306#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
307impl<A: [const] Ord + [const] UnsignedBytewiseOrd> const SliceOrd for A {
308 #[inline]
309 fn compare(left: &[Self], right: &[Self]) -> Ordering {
310 // Since the length of a slice is always less than or equal to
311 // isize::MAX, this never underflows.
312 let diff: isize = left.len() as isize - right.len() as isize;
313 // This comparison gets optimized away (on x86_64 and ARM) because the
314 // subtraction updates flags.
315 let len: usize = if left.len() < right.len() { left.len() } else { right.len() };
316 let left: *const u8 = left.as_ptr().cast();
317 let right: *const u8 = right.as_ptr().cast();
318 // SAFETY: `left` and `right` are references and are thus guaranteed to
319 // be valid. `UnsignedBytewiseOrd` is only implemented for types that
320 // are valid u8s and can be compared the same way. We use the minimum
321 // of both lengths which guarantees that both regions are valid for
322 // reads in that interval.
323 let mut order: isize = unsafe { compare_bytes(left, right, bytes:len) as isize };
324 if order == 0 {
325 order = diff;
326 }
327 order.cmp(&0)
328 }
329}
330
331// Don't generate our own chaining loops for `memcmp`-able things either.
332
333#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
334impl<A: [const] PartialOrd + [const] UnsignedBytewiseOrd> const SliceChain for A {
335 #[inline]
336 fn chaining_lt(left: &[Self], right: &[Self]) -> ControlFlow<bool> {
337 match SliceOrd::compare(left, right) {
338 Ordering::Equal => ControlFlow::Continue(()),
339 ne => ControlFlow::Break(ne.is_lt()),
340 }
341 }
342 #[inline]
343 fn chaining_le(left: &[Self], right: &[Self]) -> ControlFlow<bool> {
344 match SliceOrd::compare(left, right) {
345 Ordering::Equal => ControlFlow::Continue(()),
346 ne => ControlFlow::Break(ne.is_le()),
347 }
348 }
349 #[inline]
350 fn chaining_gt(left: &[Self], right: &[Self]) -> ControlFlow<bool> {
351 match SliceOrd::compare(left, right) {
352 Ordering::Equal => ControlFlow::Continue(()),
353 ne => ControlFlow::Break(ne.is_gt()),
354 }
355 }
356 #[inline]
357 fn chaining_ge(left: &[Self], right: &[Self]) -> ControlFlow<bool> {
358 match SliceOrd::compare(left, right) {
359 Ordering::Equal => ControlFlow::Continue(()),
360 ne => ControlFlow::Break(ne.is_ge()),
361 }
362 }
363}
364
365pub(super) trait SliceContains: Sized {
366 fn slice_contains(&self, x: &[Self]) -> bool;
367}
368
369impl<T> SliceContains for T
370where
371 T: PartialEq,
372{
373 default fn slice_contains(&self, x: &[Self]) -> bool {
374 x.iter().any(|y: &T| *y == *self)
375 }
376}
377
378impl SliceContains for u8 {
379 #[inline]
380 fn slice_contains(&self, x: &[Self]) -> bool {
381 memchr::memchr(*self, text:x).is_some()
382 }
383}
384
385impl SliceContains for i8 {
386 #[inline]
387 fn slice_contains(&self, x: &[Self]) -> bool {
388 let byte: u8 = *self as u8;
389 // SAFETY: `i8` and `u8` have the same memory layout, thus casting `x.as_ptr()`
390 // as `*const u8` is safe. The `x.as_ptr()` comes from a reference and is thus guaranteed
391 // to be valid for reads for the length of the slice `x.len()`, which cannot be larger
392 // than `isize::MAX`. The returned slice is never mutated.
393 let bytes: &[u8] = unsafe { from_raw_parts(data:x.as_ptr() as *const u8, x.len()) };
394 memchr::memchr(x:byte, text:bytes).is_some()
395 }
396}
397
398macro_rules! impl_slice_contains {
399 ($($t:ty),*) => {
400 $(
401 impl SliceContains for $t {
402 #[inline]
403 fn slice_contains(&self, arr: &[$t]) -> bool {
404 // Make our LANE_COUNT 4x the normal lane count (aiming for 128 bit vectors).
405 // The compiler will nicely unroll it.
406 const LANE_COUNT: usize = 4 * (128 / (size_of::<$t>() * 8));
407 // SIMD
408 let mut chunks = arr.chunks_exact(LANE_COUNT);
409 for chunk in &mut chunks {
410 if chunk.iter().fold(false, |acc, x| acc | (*x == *self)) {
411 return true;
412 }
413 }
414 // Scalar remainder
415 return chunks.remainder().iter().any(|x| *x == *self);
416 }
417 }
418 )*
419 };
420}
421
422impl_slice_contains!(u16, u32, u64, i16, i32, i64, f32, f64, usize, isize, char);
423