library/core/src/slice/cmp.rs

   1 //! Comparison traits for `[T]`.
   2
   3 use crate::cmp;
   4 use crate::cmp::Ordering::{self, Greater, Less};
   5 use crate::mem;
   6
   7 use super::from_raw_parts;
   8 use super::memchr;
   9
  10 extern "C" {
  11     /// Calls implementation provided memcmp.
  12     ///
  13     /// Interprets the data as u8.
  14     ///
  15     /// Returns 0 for equal, < 0 for less than and > 0 for greater
  16     /// than.
  17     // FIXME(#32610): Return type should be c_int
  18     fn memcmp(s1: *const u8, s2: *const u8, n: usize) -> i32;
  19 }
  20
  21 #[stable(feature = "rust1", since = "1.0.0")]
  22 impl<A, B> PartialEq<[B]> for [A]
  23 where
  24     A: PartialEq<B>,
  25 {
  26     fn eq(&self, other: &[B]) -> bool {
  27         SlicePartialEq::equal(self, other)
  28     }
  29
  30     fn ne(&self, other: &[B]) -> bool {
  31         SlicePartialEq::not_equal(self, other)
  32     }
  33 }
  34
  35 #[stable(feature = "rust1", since = "1.0.0")]
  36 impl<T: Eq> Eq for [T] {}
  37
  38 /// Implements comparison of vectors [lexicographically](Ord#lexicographical-comparison).
  39 #[stable(feature = "rust1", since = "1.0.0")]
  40 impl<T: Ord> Ord for [T] {
  41     fn cmp(&self, other: &[T]) -> Ordering {
  42         SliceOrd::compare(self, other)
  43     }
  44 }
  45
  46 /// Implements comparison of vectors [lexicographically](Ord#lexicographical-comparison).
  47 #[stable(feature = "rust1", since = "1.0.0")]
  48 impl<T: PartialOrd> PartialOrd for [T] {
  49     fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
  50         SlicePartialOrd::partial_compare(self, other)
  51     }
  52 }
  53
  54 #[doc(hidden)]
  55 // intermediate trait for specialization of slice's PartialEq
  56 trait SlicePartialEq<B> {
  57     fn equal(&self, other: &[B]) -> bool;
  58
  59     fn not_equal(&self, other: &[B]) -> bool {
  60         !self.equal(other)
  61     }
  62 }
  63
  64 // Generic slice equality
  65 impl<A, B> SlicePartialEq<B> for [A]
  66 where
  67     A: PartialEq<B>,
  68 {
  69     default fn equal(&self, other: &[B]) -> bool {
  70         if self.len() != other.len() {
  71             return false;
  72         }
  73
  74         self.iter().zip(other.iter()).all(|(x, y)| x == y)
  75     }
  76 }
  77
  78 // Use memcmp for bytewise equality when the types allow
  79 impl<A, B> SlicePartialEq<B> for [A]
  80 where
  81     A: BytewiseEquality<B>,
  82 {
  83     fn equal(&self, other: &[B]) -> bool {
  84         if self.len() != other.len() {
  85             return false;
  86         }
  87
  88         // SAFETY: `self` and `other` are references and are thus guaranteed to be valid.
  89         // The two slices have been checked to have the same size above.
  90         unsafe {
  91             let size = mem::size_of_val(self);
  92             memcmp(self.as_ptr() as *const u8, other.as_ptr() as *const u8, size) == 0
  93         }
  94     }
  95 }
  96
  97 #[doc(hidden)]
  98 // intermediate trait for specialization of slice's PartialOrd
  99 trait SlicePartialOrd: Sized {
 100     fn partial_compare(left: &[Self], right: &[Self]) -> Option<Ordering>;
 101 }
 102
 103 impl<A: PartialOrd> SlicePartialOrd for A {
 104     default fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
 105         let l = cmp::min(left.len(), right.len());
 106
 107         // Slice to the loop iteration range to enable bound check
 108         // elimination in the compiler
 109         let lhs = &left[..l];
 110         let rhs = &right[..l];
 111
 112         for i in 0..l {
 113             match lhs[i].partial_cmp(&rhs[i]) {
 114                 Some(Ordering::Equal) => (),
 115                 non_eq => return non_eq,
 116             }
 117         }
 118
 119         left.len().partial_cmp(&right.len())
 120     }
 121 }
 122
 123 // This is the impl that we would like to have. Unfortunately it's not sound.
 124 // See `partial_ord_slice.rs`.
 125 /*
 126 impl<A> SlicePartialOrd for A
 127 where
 128     A: Ord,
 129 {
 130     default fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
 131         Some(SliceOrd::compare(left, right))
 132     }
 133 }
 134 */
 135
 136 impl<A: AlwaysApplicableOrd> SlicePartialOrd for A {
 137     fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
 138         Some(SliceOrd::compare(left, right))
 139     }
 140 }
 141
 142 #[rustc_specialization_trait]
 143 trait AlwaysApplicableOrd: SliceOrd + Ord {}
 144
 145 macro_rules! always_applicable_ord {
 146     ($([$($p:tt)*] $t:ty,)*) => {
 147         $(impl<$($p)*> AlwaysApplicableOrd for $t {})*
 148     }
 149 }
 150
 151 always_applicable_ord! {
 152     [] u8, [] u16, [] u32, [] u64, [] u128, [] usize,
 153     [] i8, [] i16, [] i32, [] i64, [] i128, [] isize,
 154     [] bool, [] char,
 155     [T: ?Sized] *const T, [T: ?Sized] *mut T,
 156     [T: AlwaysApplicableOrd] &T,
 157     [T: AlwaysApplicableOrd] &mut T,
 158     [T: AlwaysApplicableOrd] Option<T>,
 159 }
 160
 161 #[doc(hidden)]
 162 // intermediate trait for specialization of slice's Ord
 163 trait SliceOrd: Sized {
 164     fn compare(left: &[Self], right: &[Self]) -> Ordering;
 165 }
 166
 167 impl<A: Ord> SliceOrd for A {
 168     default fn compare(left: &[Self], right: &[Self]) -> Ordering {
 169         let l = cmp::min(left.len(), right.len());
 170
 171         // Slice to the loop iteration range to enable bound check
 172         // elimination in the compiler
 173         let lhs = &left[..l];
 174         let rhs = &right[..l];
 175
 176         for i in 0..l {
 177             match lhs[i].cmp(&rhs[i]) {
 178                 Ordering::Equal => (),
 179                 non_eq => return non_eq,
 180             }
 181         }
 182
 183         left.len().cmp(&right.len())
 184     }
 185 }
 186
 187 // memcmp compares a sequence of unsigned bytes lexicographically.
 188 // this matches the order we want for [u8], but no others (not even [i8]).
 189 impl SliceOrd for u8 {
 190     #[inline]
 191     fn compare(left: &[Self], right: &[Self]) -> Ordering {
 192         let order =
 193             // SAFETY: `left` and `right` are references and are thus guaranteed to be valid.
 194             // We use the minimum of both lengths which guarantees that both regions are
 195             // valid for reads in that interval.
 196             unsafe { memcmp(left.as_ptr(), right.as_ptr(), cmp::min(left.len(), right.len())) };
 197         if order == 0 {
 198             left.len().cmp(&right.len())
 199         } else if order < 0 {
 200             Less
 201         } else {
 202             Greater
 203         }
 204     }
 205 }
 206
 207 // Hack to allow specializing on `Eq` even though `Eq` has a method.
 208 #[rustc_unsafe_specialization_marker]
 209 trait MarkerEq<T>: PartialEq<T> {}
 210
 211 impl<T: Eq> MarkerEq<T> for T {}
 212
 213 #[doc(hidden)]
 214 /// Trait implemented for types that can be compared for equality using
 215 /// their bytewise representation
 216 #[rustc_specialization_trait]
 217 trait BytewiseEquality<T>: MarkerEq<T> + Copy {}
 218
 219 macro_rules! impl_marker_for {
 220     ($traitname:ident, $($ty:ty)*) => {
 221         $(
 222             impl $traitname<$ty> for $ty { }
 223         )*
 224     }
 225 }
 226
 227 impl_marker_for!(BytewiseEquality,
 228                  u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize char bool);
 229
 230 pub(super) trait SliceContains: Sized {
 231     fn slice_contains(&self, x: &[Self]) -> bool;
 232 }
 233
 234 impl<T> SliceContains for T
 235 where
 236     T: PartialEq,
 237 {
 238     default fn slice_contains(&self, x: &[Self]) -> bool {
 239         x.iter().any(|y| *y == *self)
 240     }
 241 }
 242
 243 impl SliceContains for u8 {
 244     #[inline]
 245     fn slice_contains(&self, x: &[Self]) -> bool {
 246         memchr::memchr(*self, x).is_some()
 247     }
 248 }
 249
 250 impl SliceContains for i8 {
 251     #[inline]
 252     fn slice_contains(&self, x: &[Self]) -> bool {
 253         let byte = *self as u8;
 254         // SAFETY: `i8` and `u8` have the same memory layout, thus casting `x.as_ptr()`
 255         // as `*const u8` is safe. The `x.as_ptr()` comes from a reference and is thus guaranteed
 256         // to be valid for reads for the length of the slice `x.len()`, which cannot be larger
 257         // than `isize::MAX`. The returned slice is never mutated.
 258         let bytes: &[u8] = unsafe { from_raw_parts(x.as_ptr() as *const u8, x.len()) };
 259         memchr::memchr(byte, bytes).is_some()
 260     }
 261 }