core/
cmp.rs

1//! Utilities for comparing and ordering values.
2//!
3//! This module contains various tools for comparing and ordering values. In
4//! summary:
5//!
6//! * [`PartialEq<Rhs>`] overloads the `==` and `!=` operators. In cases where
7//!   `Rhs` (the right hand side's type) is `Self`, this trait corresponds to a
8//!   partial equivalence relation.
9//! * [`Eq`] indicates that the overloaded `==` operator corresponds to an
10//!   equivalence relation.
11//! * [`Ord`] and [`PartialOrd`] are traits that allow you to define total and
12//!   partial orderings between values, respectively. Implementing them overloads
13//!   the `<`, `<=`, `>`, and `>=` operators.
14//! * [`Ordering`] is an enum returned by the main functions of [`Ord`] and
15//!   [`PartialOrd`], and describes an ordering of two values (less, equal, or
16//!   greater).
17//! * [`Reverse`] is a struct that allows you to easily reverse an ordering.
18//! * [`max`] and [`min`] are functions that build off of [`Ord`] and allow you
19//!   to find the maximum or minimum of two values.
20//!
21//! For more details, see the respective documentation of each item in the list.
22//!
23//! [`max`]: Ord::max
24//! [`min`]: Ord::min
25
26#![stable(feature = "rust1", since = "1.0.0")]
27
28#[cfg(not(feature = "ferrocene_certified"))]
29mod bytewise;
30#[cfg(not(feature = "ferrocene_certified"))]
31pub(crate) use bytewise::BytewiseEq;
32
33use self::Ordering::*;
34use crate::marker::PointeeSized;
35use crate::ops::ControlFlow;
36
37/// Trait for comparisons using the equality operator.
38///
39/// Implementing this trait for types provides the `==` and `!=` operators for
40/// those types.
41///
42/// `x.eq(y)` can also be written `x == y`, and `x.ne(y)` can be written `x != y`.
43/// We use the easier-to-read infix notation in the remainder of this documentation.
44///
45/// This trait allows for comparisons using the equality operator, for types
46/// that do not have a full equivalence relation. For example, in floating point
47/// numbers `NaN != NaN`, so floating point types implement `PartialEq` but not
48/// [`trait@Eq`]. Formally speaking, when `Rhs == Self`, this trait corresponds
49/// to a [partial equivalence relation].
50///
51/// [partial equivalence relation]: https://en.wikipedia.org/wiki/Partial_equivalence_relation
52///
53/// Implementations must ensure that `eq` and `ne` are consistent with each other:
54///
55/// - `a != b` if and only if `!(a == b)`.
56///
57/// The default implementation of `ne` provides this consistency and is almost
58/// always sufficient. It should not be overridden without very good reason.
59///
60/// If [`PartialOrd`] or [`Ord`] are also implemented for `Self` and `Rhs`, their methods must also
61/// be consistent with `PartialEq` (see the documentation of those traits for the exact
62/// requirements). It's easy to accidentally make them disagree by deriving some of the traits and
63/// manually implementing others.
64///
65/// The equality relation `==` must satisfy the following conditions
66/// (for all `a`, `b`, `c` of type `A`, `B`, `C`):
67///
68/// - **Symmetry**: if `A: PartialEq<B>` and `B: PartialEq<A>`, then **`a == b`
69///   implies `b == a`**; and
70///
71/// - **Transitivity**: if `A: PartialEq<B>` and `B: PartialEq<C>` and `A:
72///   PartialEq<C>`, then **`a == b` and `b == c` implies `a == c`**.
73///   This must also work for longer chains, such as when `A: PartialEq<B>`, `B: PartialEq<C>`,
74///   `C: PartialEq<D>`, and `A: PartialEq<D>` all exist.
75///
76/// Note that the `B: PartialEq<A>` (symmetric) and `A: PartialEq<C>`
77/// (transitive) impls are not forced to exist, but these requirements apply
78/// whenever they do exist.
79///
80/// Violating these requirements is a logic error. The behavior resulting from a logic error is not
81/// specified, but users of the trait must ensure that such logic errors do *not* result in
82/// undefined behavior. This means that `unsafe` code **must not** rely on the correctness of these
83/// methods.
84///
85/// ## Cross-crate considerations
86///
87/// Upholding the requirements stated above can become tricky when one crate implements `PartialEq`
88/// for a type of another crate (i.e., to allow comparing one of its own types with a type from the
89/// standard library). The recommendation is to never implement this trait for a foreign type. In
90/// other words, such a crate should do `impl PartialEq<ForeignType> for LocalType`, but it should
91/// *not* do `impl PartialEq<LocalType> for ForeignType`.
92///
93/// This avoids the problem of transitive chains that criss-cross crate boundaries: for all local
94/// types `T`, you may assume that no other crate will add `impl`s that allow comparing `T == U`. In
95/// other words, if other crates add `impl`s that allow building longer transitive chains `U1 == ...
96/// == T == V1 == ...`, then all the types that appear to the right of `T` must be types that the
97/// crate defining `T` already knows about. This rules out transitive chains where downstream crates
98/// can add new `impl`s that "stitch together" comparisons of foreign types in ways that violate
99/// transitivity.
100///
101/// Not having such foreign `impl`s also avoids forward compatibility issues where one crate adding
102/// more `PartialEq` implementations can cause build failures in downstream crates.
103///
104/// ## Derivable
105///
106/// This trait can be used with `#[derive]`. When `derive`d on structs, two
107/// instances are equal if all fields are equal, and not equal if any fields
108/// are not equal. When `derive`d on enums, two instances are equal if they
109/// are the same variant and all fields are equal.
110///
111/// ## How can I implement `PartialEq`?
112///
113/// An example implementation for a domain in which two books are considered
114/// the same book if their ISBN matches, even if the formats differ:
115///
116/// ```
117/// enum BookFormat {
118///     Paperback,
119///     Hardback,
120///     Ebook,
121/// }
122///
123/// struct Book {
124///     isbn: i32,
125///     format: BookFormat,
126/// }
127///
128/// impl PartialEq for Book {
129///     fn eq(&self, other: &Self) -> bool {
130///         self.isbn == other.isbn
131///     }
132/// }
133///
134/// let b1 = Book { isbn: 3, format: BookFormat::Paperback };
135/// let b2 = Book { isbn: 3, format: BookFormat::Ebook };
136/// let b3 = Book { isbn: 10, format: BookFormat::Paperback };
137///
138/// assert!(b1 == b2);
139/// assert!(b1 != b3);
140/// ```
141///
142/// ## How can I compare two different types?
143///
144/// The type you can compare with is controlled by `PartialEq`'s type parameter.
145/// For example, let's tweak our previous code a bit:
146///
147/// ```
148/// // The derive implements <BookFormat> == <BookFormat> comparisons
149/// #[derive(PartialEq)]
150/// enum BookFormat {
151///     Paperback,
152///     Hardback,
153///     Ebook,
154/// }
155///
156/// struct Book {
157///     isbn: i32,
158///     format: BookFormat,
159/// }
160///
161/// // Implement <Book> == <BookFormat> comparisons
162/// impl PartialEq<BookFormat> for Book {
163///     fn eq(&self, other: &BookFormat) -> bool {
164///         self.format == *other
165///     }
166/// }
167///
168/// // Implement <BookFormat> == <Book> comparisons
169/// impl PartialEq<Book> for BookFormat {
170///     fn eq(&self, other: &Book) -> bool {
171///         *self == other.format
172///     }
173/// }
174///
175/// let b1 = Book { isbn: 3, format: BookFormat::Paperback };
176///
177/// assert!(b1 == BookFormat::Paperback);
178/// assert!(BookFormat::Ebook != b1);
179/// ```
180///
181/// By changing `impl PartialEq for Book` to `impl PartialEq<BookFormat> for Book`,
182/// we allow `BookFormat`s to be compared with `Book`s.
183///
184/// A comparison like the one above, which ignores some fields of the struct,
185/// can be dangerous. It can easily lead to an unintended violation of the
186/// requirements for a partial equivalence relation. For example, if we kept
187/// the above implementation of `PartialEq<Book>` for `BookFormat` and added an
188/// implementation of `PartialEq<Book>` for `Book` (either via a `#[derive]` or
189/// via the manual implementation from the first example) then the result would
190/// violate transitivity:
191///
192/// ```should_panic
193/// #[derive(PartialEq)]
194/// enum BookFormat {
195///     Paperback,
196///     Hardback,
197///     Ebook,
198/// }
199///
200/// #[derive(PartialEq)]
201/// struct Book {
202///     isbn: i32,
203///     format: BookFormat,
204/// }
205///
206/// impl PartialEq<BookFormat> for Book {
207///     fn eq(&self, other: &BookFormat) -> bool {
208///         self.format == *other
209///     }
210/// }
211///
212/// impl PartialEq<Book> for BookFormat {
213///     fn eq(&self, other: &Book) -> bool {
214///         *self == other.format
215///     }
216/// }
217///
218/// fn main() {
219///     let b1 = Book { isbn: 1, format: BookFormat::Paperback };
220///     let b2 = Book { isbn: 2, format: BookFormat::Paperback };
221///
222///     assert!(b1 == BookFormat::Paperback);
223///     assert!(BookFormat::Paperback == b2);
224///
225///     // The following should hold by transitivity but doesn't.
226///     assert!(b1 == b2); // <-- PANICS
227/// }
228/// ```
229///
230/// # Examples
231///
232/// ```
233/// let x: u32 = 0;
234/// let y: u32 = 1;
235///
236/// assert_eq!(x == y, false);
237/// assert_eq!(x.eq(&y), false);
238/// ```
239///
240/// [`eq`]: PartialEq::eq
241/// [`ne`]: PartialEq::ne
242#[lang = "eq"]
243#[stable(feature = "rust1", since = "1.0.0")]
244#[doc(alias = "==")]
245#[doc(alias = "!=")]
246#[rustc_on_unimplemented(
247    message = "can't compare `{Self}` with `{Rhs}`",
248    label = "no implementation for `{Self} == {Rhs}`",
249    append_const_msg
250)]
251#[rustc_diagnostic_item = "PartialEq"]
252#[const_trait]
253#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
254pub trait PartialEq<Rhs: PointeeSized = Self>: PointeeSized {
255    /// Tests for `self` and `other` values to be equal, and is used by `==`.
256    #[must_use]
257    #[stable(feature = "rust1", since = "1.0.0")]
258    #[rustc_diagnostic_item = "cmp_partialeq_eq"]
259    fn eq(&self, other: &Rhs) -> bool;
260
261    /// Tests for `!=`. The default implementation is almost always sufficient,
262    /// and should not be overridden without very good reason.
263    #[inline]
264    #[must_use]
265    #[stable(feature = "rust1", since = "1.0.0")]
266    #[rustc_diagnostic_item = "cmp_partialeq_ne"]
267    fn ne(&self, other: &Rhs) -> bool {
268        !self.eq(other)
269    }
270}
271
272/// Derive macro generating an impl of the trait [`PartialEq`].
273/// The behavior of this macro is described in detail [here](PartialEq#derivable).
274#[rustc_builtin_macro]
275#[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
276#[allow_internal_unstable(core_intrinsics, structural_match)]
277pub macro PartialEq($item:item) {
278    /* compiler built-in */
279}
280
281/// Trait for comparisons corresponding to [equivalence relations](
282/// https://en.wikipedia.org/wiki/Equivalence_relation).
283///
284/// The primary difference to [`PartialEq`] is the additional requirement for reflexivity. A type
285/// that implements [`PartialEq`] guarantees that for all `a`, `b` and `c`:
286///
287/// - symmetric: `a == b` implies `b == a` and `a != b` implies `!(a == b)`
288/// - transitive: `a == b` and `b == c` implies `a == c`
289///
290/// `Eq`, which builds on top of [`PartialEq`] also implies:
291///
292/// - reflexive: `a == a`
293///
294/// This property cannot be checked by the compiler, and therefore `Eq` is a trait without methods.
295///
296/// Violating this property is a logic error. The behavior resulting from a logic error is not
297/// specified, but users of the trait must ensure that such logic errors do *not* result in
298/// undefined behavior. This means that `unsafe` code **must not** rely on the correctness of these
299/// methods.
300///
301/// Floating point types such as [`f32`] and [`f64`] implement only [`PartialEq`] but *not* `Eq`
302/// because `NaN` != `NaN`.
303///
304/// ## Derivable
305///
306/// This trait can be used with `#[derive]`. When `derive`d, because `Eq` has no extra methods, it
307/// is only informing the compiler that this is an equivalence relation rather than a partial
308/// equivalence relation. Note that the `derive` strategy requires all fields are `Eq`, which isn't
309/// always desired.
310///
311/// ## How can I implement `Eq`?
312///
313/// If you cannot use the `derive` strategy, specify that your type implements `Eq`, which has no
314/// extra methods:
315///
316/// ```
317/// enum BookFormat {
318///     Paperback,
319///     Hardback,
320///     Ebook,
321/// }
322///
323/// struct Book {
324///     isbn: i32,
325///     format: BookFormat,
326/// }
327///
328/// impl PartialEq for Book {
329///     fn eq(&self, other: &Self) -> bool {
330///         self.isbn == other.isbn
331///     }
332/// }
333///
334/// impl Eq for Book {}
335/// ```
336#[doc(alias = "==")]
337#[doc(alias = "!=")]
338#[stable(feature = "rust1", since = "1.0.0")]
339#[rustc_diagnostic_item = "Eq"]
340pub trait Eq: PartialEq<Self> + PointeeSized {
341    // this method is used solely by `impl Eq or #[derive(Eq)]` to assert that every component of a
342    // type implements `Eq` itself. The current deriving infrastructure means doing this assertion
343    // without using a method on this trait is nearly impossible.
344    //
345    // This should never be implemented by hand.
346    #[doc(hidden)]
347    #[coverage(off)]
348    #[inline]
349    #[stable(feature = "rust1", since = "1.0.0")]
350    fn assert_receiver_is_total_eq(&self) {}
351}
352
353/// Derive macro generating an impl of the trait [`Eq`].
354#[rustc_builtin_macro]
355#[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
356#[allow_internal_unstable(core_intrinsics, derive_eq, structural_match)]
357#[allow_internal_unstable(coverage_attribute)]
358pub macro Eq($item:item) {
359    /* compiler built-in */
360}
361
362// FIXME: this struct is used solely by #[derive] to
363// assert that every component of a type implements Eq.
364//
365// This struct should never appear in user code.
366#[doc(hidden)]
367#[allow(missing_debug_implementations)]
368#[unstable(feature = "derive_eq", reason = "deriving hack, should not be public", issue = "none")]
369#[cfg(not(feature = "ferrocene_certified"))]
370pub struct AssertParamIsEq<T: Eq + PointeeSized> {
371    _field: crate::marker::PhantomData<T>,
372}
373
374/// An `Ordering` is the result of a comparison between two values.
375///
376/// # Examples
377///
378/// ```
379/// use std::cmp::Ordering;
380///
381/// assert_eq!(1.cmp(&2), Ordering::Less);
382///
383/// assert_eq!(1.cmp(&1), Ordering::Equal);
384///
385/// assert_eq!(2.cmp(&1), Ordering::Greater);
386/// ```
387#[cfg_attr(
388    not(feature = "ferrocene_certified"),
389    derive(Clone, Copy, Eq, PartialOrd, Ord, Debug, Hash)
390)]
391#[cfg_attr(not(feature = "ferrocene_certified"), derive_const(PartialEq))]
392#[stable(feature = "rust1", since = "1.0.0")]
393// This is a lang item only so that `BinOp::Cmp` in MIR can return it.
394// It has no special behavior, but does require that the three variants
395// `Less`/`Equal`/`Greater` remain `-1_i8`/`0_i8`/`+1_i8` respectively.
396#[lang = "Ordering"]
397#[repr(i8)]
398pub enum Ordering {
399    /// An ordering where a compared value is less than another.
400    #[stable(feature = "rust1", since = "1.0.0")]
401    Less = -1,
402    /// An ordering where a compared value is equal to another.
403    #[stable(feature = "rust1", since = "1.0.0")]
404    Equal = 0,
405    /// An ordering where a compared value is greater than another.
406    #[stable(feature = "rust1", since = "1.0.0")]
407    Greater = 1,
408}
409
410impl Ordering {
411    #[inline]
412    const fn as_raw(self) -> i8 {
413        // FIXME(const-hack): just use `PartialOrd` against `Equal` once that's const
414        crate::intrinsics::discriminant_value(&self)
415    }
416
417    /// Returns `true` if the ordering is the `Equal` variant.
418    ///
419    /// # Examples
420    ///
421    /// ```
422    /// use std::cmp::Ordering;
423    ///
424    /// assert_eq!(Ordering::Less.is_eq(), false);
425    /// assert_eq!(Ordering::Equal.is_eq(), true);
426    /// assert_eq!(Ordering::Greater.is_eq(), false);
427    /// ```
428    #[inline]
429    #[must_use]
430    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
431    #[stable(feature = "ordering_helpers", since = "1.53.0")]
432    pub const fn is_eq(self) -> bool {
433        // All the `is_*` methods are implemented as comparisons against zero
434        // to follow how clang's libcxx implements their equivalents in
435        // <https://github.com/llvm/llvm-project/blob/60486292b79885b7800b082754153202bef5b1f0/libcxx/include/__compare/is_eq.h#L23-L28>
436
437        self.as_raw() == 0
438    }
439
440    /// Returns `true` if the ordering is not the `Equal` variant.
441    ///
442    /// # Examples
443    ///
444    /// ```
445    /// use std::cmp::Ordering;
446    ///
447    /// assert_eq!(Ordering::Less.is_ne(), true);
448    /// assert_eq!(Ordering::Equal.is_ne(), false);
449    /// assert_eq!(Ordering::Greater.is_ne(), true);
450    /// ```
451    #[inline]
452    #[must_use]
453    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
454    #[stable(feature = "ordering_helpers", since = "1.53.0")]
455    pub const fn is_ne(self) -> bool {
456        self.as_raw() != 0
457    }
458
459    /// Returns `true` if the ordering is the `Less` variant.
460    ///
461    /// # Examples
462    ///
463    /// ```
464    /// use std::cmp::Ordering;
465    ///
466    /// assert_eq!(Ordering::Less.is_lt(), true);
467    /// assert_eq!(Ordering::Equal.is_lt(), false);
468    /// assert_eq!(Ordering::Greater.is_lt(), false);
469    /// ```
470    #[inline]
471    #[must_use]
472    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
473    #[stable(feature = "ordering_helpers", since = "1.53.0")]
474    pub const fn is_lt(self) -> bool {
475        self.as_raw() < 0
476    }
477
478    /// Returns `true` if the ordering is the `Greater` variant.
479    ///
480    /// # Examples
481    ///
482    /// ```
483    /// use std::cmp::Ordering;
484    ///
485    /// assert_eq!(Ordering::Less.is_gt(), false);
486    /// assert_eq!(Ordering::Equal.is_gt(), false);
487    /// assert_eq!(Ordering::Greater.is_gt(), true);
488    /// ```
489    #[inline]
490    #[must_use]
491    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
492    #[stable(feature = "ordering_helpers", since = "1.53.0")]
493    pub const fn is_gt(self) -> bool {
494        self.as_raw() > 0
495    }
496
497    /// Returns `true` if the ordering is either the `Less` or `Equal` variant.
498    ///
499    /// # Examples
500    ///
501    /// ```
502    /// use std::cmp::Ordering;
503    ///
504    /// assert_eq!(Ordering::Less.is_le(), true);
505    /// assert_eq!(Ordering::Equal.is_le(), true);
506    /// assert_eq!(Ordering::Greater.is_le(), false);
507    /// ```
508    #[inline]
509    #[must_use]
510    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
511    #[stable(feature = "ordering_helpers", since = "1.53.0")]
512    pub const fn is_le(self) -> bool {
513        self.as_raw() <= 0
514    }
515
516    /// Returns `true` if the ordering is either the `Greater` or `Equal` variant.
517    ///
518    /// # Examples
519    ///
520    /// ```
521    /// use std::cmp::Ordering;
522    ///
523    /// assert_eq!(Ordering::Less.is_ge(), false);
524    /// assert_eq!(Ordering::Equal.is_ge(), true);
525    /// assert_eq!(Ordering::Greater.is_ge(), true);
526    /// ```
527    #[inline]
528    #[must_use]
529    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
530    #[stable(feature = "ordering_helpers", since = "1.53.0")]
531    pub const fn is_ge(self) -> bool {
532        self.as_raw() >= 0
533    }
534
535    /// Reverses the `Ordering`.
536    ///
537    /// * `Less` becomes `Greater`.
538    /// * `Greater` becomes `Less`.
539    /// * `Equal` becomes `Equal`.
540    ///
541    /// # Examples
542    ///
543    /// Basic behavior:
544    ///
545    /// ```
546    /// use std::cmp::Ordering;
547    ///
548    /// assert_eq!(Ordering::Less.reverse(), Ordering::Greater);
549    /// assert_eq!(Ordering::Equal.reverse(), Ordering::Equal);
550    /// assert_eq!(Ordering::Greater.reverse(), Ordering::Less);
551    /// ```
552    ///
553    /// This method can be used to reverse a comparison:
554    ///
555    /// ```
556    /// let data: &mut [_] = &mut [2, 10, 5, 8];
557    ///
558    /// // sort the array from largest to smallest.
559    /// data.sort_by(|a, b| a.cmp(b).reverse());
560    ///
561    /// let b: &mut [_] = &mut [10, 8, 5, 2];
562    /// assert!(data == b);
563    /// ```
564    #[inline]
565    #[must_use]
566    #[rustc_const_stable(feature = "const_ordering", since = "1.48.0")]
567    #[stable(feature = "rust1", since = "1.0.0")]
568    pub const fn reverse(self) -> Ordering {
569        match self {
570            Less => Greater,
571            Equal => Equal,
572            Greater => Less,
573        }
574    }
575
576    /// Chains two orderings.
577    ///
578    /// Returns `self` when it's not `Equal`. Otherwise returns `other`.
579    ///
580    /// # Examples
581    ///
582    /// ```
583    /// use std::cmp::Ordering;
584    ///
585    /// let result = Ordering::Equal.then(Ordering::Less);
586    /// assert_eq!(result, Ordering::Less);
587    ///
588    /// let result = Ordering::Less.then(Ordering::Equal);
589    /// assert_eq!(result, Ordering::Less);
590    ///
591    /// let result = Ordering::Less.then(Ordering::Greater);
592    /// assert_eq!(result, Ordering::Less);
593    ///
594    /// let result = Ordering::Equal.then(Ordering::Equal);
595    /// assert_eq!(result, Ordering::Equal);
596    ///
597    /// let x: (i64, i64, i64) = (1, 2, 7);
598    /// let y: (i64, i64, i64) = (1, 5, 3);
599    /// let result = x.0.cmp(&y.0).then(x.1.cmp(&y.1)).then(x.2.cmp(&y.2));
600    ///
601    /// assert_eq!(result, Ordering::Less);
602    /// ```
603    #[inline]
604    #[must_use]
605    #[rustc_const_stable(feature = "const_ordering", since = "1.48.0")]
606    #[stable(feature = "ordering_chaining", since = "1.17.0")]
607    pub const fn then(self, other: Ordering) -> Ordering {
608        match self {
609            Equal => other,
610            _ => self,
611        }
612    }
613
614    /// Chains the ordering with the given function.
615    ///
616    /// Returns `self` when it's not `Equal`. Otherwise calls `f` and returns
617    /// the result.
618    ///
619    /// # Examples
620    ///
621    /// ```
622    /// use std::cmp::Ordering;
623    ///
624    /// let result = Ordering::Equal.then_with(|| Ordering::Less);
625    /// assert_eq!(result, Ordering::Less);
626    ///
627    /// let result = Ordering::Less.then_with(|| Ordering::Equal);
628    /// assert_eq!(result, Ordering::Less);
629    ///
630    /// let result = Ordering::Less.then_with(|| Ordering::Greater);
631    /// assert_eq!(result, Ordering::Less);
632    ///
633    /// let result = Ordering::Equal.then_with(|| Ordering::Equal);
634    /// assert_eq!(result, Ordering::Equal);
635    ///
636    /// let x: (i64, i64, i64) = (1, 2, 7);
637    /// let y: (i64, i64, i64) = (1, 5, 3);
638    /// let result = x.0.cmp(&y.0).then_with(|| x.1.cmp(&y.1)).then_with(|| x.2.cmp(&y.2));
639    ///
640    /// assert_eq!(result, Ordering::Less);
641    /// ```
642    #[inline]
643    #[must_use]
644    #[stable(feature = "ordering_chaining", since = "1.17.0")]
645    #[cfg(not(feature = "ferrocene_certified"))]
646    pub fn then_with<F: FnOnce() -> Ordering>(self, f: F) -> Ordering {
647        match self {
648            Equal => f(),
649            _ => self,
650        }
651    }
652}
653
654/// A helper struct for reverse ordering.
655///
656/// This struct is a helper to be used with functions like [`Vec::sort_by_key`] and
657/// can be used to reverse order a part of a key.
658///
659/// [`Vec::sort_by_key`]: ../../std/vec/struct.Vec.html#method.sort_by_key
660///
661/// # Examples
662///
663/// ```
664/// use std::cmp::Reverse;
665///
666/// let mut v = vec![1, 2, 3, 4, 5, 6];
667/// v.sort_by_key(|&num| (num > 3, Reverse(num)));
668/// assert_eq!(v, vec![3, 2, 1, 6, 5, 4]);
669/// ```
670#[derive(PartialEq, Eq, Debug, Copy, Default, Hash)]
671#[stable(feature = "reverse_cmp_key", since = "1.19.0")]
672#[repr(transparent)]
673#[cfg(not(feature = "ferrocene_certified"))]
674pub struct Reverse<T>(#[stable(feature = "reverse_cmp_key", since = "1.19.0")] pub T);
675
676#[stable(feature = "reverse_cmp_key", since = "1.19.0")]
677#[cfg(not(feature = "ferrocene_certified"))]
678impl<T: PartialOrd> PartialOrd for Reverse<T> {
679    #[inline]
680    fn partial_cmp(&self, other: &Reverse<T>) -> Option<Ordering> {
681        other.0.partial_cmp(&self.0)
682    }
683
684    #[inline]
685    fn lt(&self, other: &Self) -> bool {
686        other.0 < self.0
687    }
688    #[inline]
689    fn le(&self, other: &Self) -> bool {
690        other.0 <= self.0
691    }
692    #[inline]
693    fn gt(&self, other: &Self) -> bool {
694        other.0 > self.0
695    }
696    #[inline]
697    fn ge(&self, other: &Self) -> bool {
698        other.0 >= self.0
699    }
700}
701
702#[stable(feature = "reverse_cmp_key", since = "1.19.0")]
703#[cfg(not(feature = "ferrocene_certified"))]
704impl<T: Ord> Ord for Reverse<T> {
705    #[inline]
706    fn cmp(&self, other: &Reverse<T>) -> Ordering {
707        other.0.cmp(&self.0)
708    }
709}
710
711#[stable(feature = "reverse_cmp_key", since = "1.19.0")]
712#[cfg(not(feature = "ferrocene_certified"))]
713impl<T: Clone> Clone for Reverse<T> {
714    #[inline]
715    fn clone(&self) -> Reverse<T> {
716        Reverse(self.0.clone())
717    }
718
719    #[inline]
720    fn clone_from(&mut self, source: &Self) {
721        self.0.clone_from(&source.0)
722    }
723}
724
725/// Trait for types that form a [total order](https://en.wikipedia.org/wiki/Total_order).
726///
727/// Implementations must be consistent with the [`PartialOrd`] implementation, and ensure `max`,
728/// `min`, and `clamp` are consistent with `cmp`:
729///
730/// - `partial_cmp(a, b) == Some(cmp(a, b))`.
731/// - `max(a, b) == max_by(a, b, cmp)` (ensured by the default implementation).
732/// - `min(a, b) == min_by(a, b, cmp)` (ensured by the default implementation).
733/// - For `a.clamp(min, max)`, see the [method docs](#method.clamp) (ensured by the default
734///   implementation).
735///
736/// Violating these requirements is a logic error. The behavior resulting from a logic error is not
737/// specified, but users of the trait must ensure that such logic errors do *not* result in
738/// undefined behavior. This means that `unsafe` code **must not** rely on the correctness of these
739/// methods.
740///
741/// ## Corollaries
742///
743/// From the above and the requirements of `PartialOrd`, it follows that for all `a`, `b` and `c`:
744///
745/// - exactly one of `a < b`, `a == b` or `a > b` is true; and
746/// - `<` is transitive: `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and
747///   `>`.
748///
749/// Mathematically speaking, the `<` operator defines a strict [weak order]. In cases where `==`
750/// conforms to mathematical equality, it also defines a strict [total order].
751///
752/// [weak order]: https://en.wikipedia.org/wiki/Weak_ordering
753/// [total order]: https://en.wikipedia.org/wiki/Total_order
754///
755/// ## Derivable
756///
757/// This trait can be used with `#[derive]`.
758///
759/// When `derive`d on structs, it will produce a
760/// [lexicographic](https://en.wikipedia.org/wiki/Lexicographic_order) ordering based on the
761/// top-to-bottom declaration order of the struct's members.
762///
763/// When `derive`d on enums, variants are ordered primarily by their discriminants. Secondarily,
764/// they are ordered by their fields. By default, the discriminant is smallest for variants at the
765/// top, and largest for variants at the bottom. Here's an example:
766///
767/// ```
768/// #[derive(PartialEq, Eq, PartialOrd, Ord)]
769/// enum E {
770///     Top,
771///     Bottom,
772/// }
773///
774/// assert!(E::Top < E::Bottom);
775/// ```
776///
777/// However, manually setting the discriminants can override this default behavior:
778///
779/// ```
780/// #[derive(PartialEq, Eq, PartialOrd, Ord)]
781/// enum E {
782///     Top = 2,
783///     Bottom = 1,
784/// }
785///
786/// assert!(E::Bottom < E::Top);
787/// ```
788///
789/// ## Lexicographical comparison
790///
791/// Lexicographical comparison is an operation with the following properties:
792///  - Two sequences are compared element by element.
793///  - The first mismatching element defines which sequence is lexicographically less or greater
794///    than the other.
795///  - If one sequence is a prefix of another, the shorter sequence is lexicographically less than
796///    the other.
797///  - If two sequences have equivalent elements and are of the same length, then the sequences are
798///    lexicographically equal.
799///  - An empty sequence is lexicographically less than any non-empty sequence.
800///  - Two empty sequences are lexicographically equal.
801///
802/// ## How can I implement `Ord`?
803///
804/// `Ord` requires that the type also be [`PartialOrd`], [`PartialEq`], and [`Eq`].
805///
806/// Because `Ord` implies a stronger ordering relationship than [`PartialOrd`], and both `Ord` and
807/// [`PartialOrd`] must agree, you must choose how to implement `Ord` **first**. You can choose to
808/// derive it, or implement it manually. If you derive it, you should derive all four traits. If you
809/// implement it manually, you should manually implement all four traits, based on the
810/// implementation of `Ord`.
811///
812/// Here's an example where you want to define the `Character` comparison by `health` and
813/// `experience` only, disregarding the field `mana`:
814///
815/// ```
816/// use std::cmp::Ordering;
817///
818/// struct Character {
819///     health: u32,
820///     experience: u32,
821///     mana: f32,
822/// }
823///
824/// impl Ord for Character {
825///     fn cmp(&self, other: &Self) -> Ordering {
826///         self.experience
827///             .cmp(&other.experience)
828///             .then(self.health.cmp(&other.health))
829///     }
830/// }
831///
832/// impl PartialOrd for Character {
833///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
834///         Some(self.cmp(other))
835///     }
836/// }
837///
838/// impl PartialEq for Character {
839///     fn eq(&self, other: &Self) -> bool {
840///         self.health == other.health && self.experience == other.experience
841///     }
842/// }
843///
844/// impl Eq for Character {}
845/// ```
846///
847/// If all you need is to `slice::sort` a type by a field value, it can be simpler to use
848/// `slice::sort_by_key`.
849///
850/// ## Examples of incorrect `Ord` implementations
851///
852/// ```
853/// use std::cmp::Ordering;
854///
855/// #[derive(Debug)]
856/// struct Character {
857///     health: f32,
858/// }
859///
860/// impl Ord for Character {
861///     fn cmp(&self, other: &Self) -> std::cmp::Ordering {
862///         if self.health < other.health {
863///             Ordering::Less
864///         } else if self.health > other.health {
865///             Ordering::Greater
866///         } else {
867///             Ordering::Equal
868///         }
869///     }
870/// }
871///
872/// impl PartialOrd for Character {
873///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
874///         Some(self.cmp(other))
875///     }
876/// }
877///
878/// impl PartialEq for Character {
879///     fn eq(&self, other: &Self) -> bool {
880///         self.health == other.health
881///     }
882/// }
883///
884/// impl Eq for Character {}
885///
886/// let a = Character { health: 4.5 };
887/// let b = Character { health: f32::NAN };
888///
889/// // Mistake: floating-point values do not form a total order and using the built-in comparison
890/// // operands to implement `Ord` irregardless of that reality does not change it. Use
891/// // `f32::total_cmp` if you need a total order for floating-point values.
892///
893/// // Reflexivity requirement of `Ord` is not given.
894/// assert!(a == a);
895/// assert!(b != b);
896///
897/// // Antisymmetry requirement of `Ord` is not given. Only one of a < c and c < a is allowed to be
898/// // true, not both or neither.
899/// assert_eq!((a < b) as u8 + (b < a) as u8, 0);
900/// ```
901///
902/// ```
903/// use std::cmp::Ordering;
904///
905/// #[derive(Debug)]
906/// struct Character {
907///     health: u32,
908///     experience: u32,
909/// }
910///
911/// impl PartialOrd for Character {
912///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
913///         Some(self.cmp(other))
914///     }
915/// }
916///
917/// impl Ord for Character {
918///     fn cmp(&self, other: &Self) -> std::cmp::Ordering {
919///         if self.health < 50 {
920///             self.health.cmp(&other.health)
921///         } else {
922///             self.experience.cmp(&other.experience)
923///         }
924///     }
925/// }
926///
927/// // For performance reasons implementing `PartialEq` this way is not the idiomatic way, but it
928/// // ensures consistent behavior between `PartialEq`, `PartialOrd` and `Ord` in this example.
929/// impl PartialEq for Character {
930///     fn eq(&self, other: &Self) -> bool {
931///         self.cmp(other) == Ordering::Equal
932///     }
933/// }
934///
935/// impl Eq for Character {}
936///
937/// let a = Character {
938///     health: 3,
939///     experience: 5,
940/// };
941/// let b = Character {
942///     health: 10,
943///     experience: 77,
944/// };
945/// let c = Character {
946///     health: 143,
947///     experience: 2,
948/// };
949///
950/// // Mistake: The implementation of `Ord` compares different fields depending on the value of
951/// // `self.health`, the resulting order is not total.
952///
953/// // Transitivity requirement of `Ord` is not given. If a is smaller than b and b is smaller than
954/// // c, by transitive property a must also be smaller than c.
955/// assert!(a < b && b < c && c < a);
956///
957/// // Antisymmetry requirement of `Ord` is not given. Only one of a < c and c < a is allowed to be
958/// // true, not both or neither.
959/// assert_eq!((a < c) as u8 + (c < a) as u8, 2);
960/// ```
961///
962/// The documentation of [`PartialOrd`] contains further examples, for example it's wrong for
963/// [`PartialOrd`] and [`PartialEq`] to disagree.
964///
965/// [`cmp`]: Ord::cmp
966#[doc(alias = "<")]
967#[doc(alias = ">")]
968#[doc(alias = "<=")]
969#[doc(alias = ">=")]
970#[stable(feature = "rust1", since = "1.0.0")]
971#[rustc_diagnostic_item = "Ord"]
972pub trait Ord: Eq + PartialOrd<Self> + PointeeSized {
973    /// This method returns an [`Ordering`] between `self` and `other`.
974    ///
975    /// By convention, `self.cmp(&other)` returns the ordering matching the expression
976    /// `self <operator> other` if true.
977    ///
978    /// # Examples
979    ///
980    /// ```
981    /// use std::cmp::Ordering;
982    ///
983    /// assert_eq!(5.cmp(&10), Ordering::Less);
984    /// assert_eq!(10.cmp(&5), Ordering::Greater);
985    /// assert_eq!(5.cmp(&5), Ordering::Equal);
986    /// ```
987    #[must_use]
988    #[stable(feature = "rust1", since = "1.0.0")]
989    #[rustc_diagnostic_item = "ord_cmp_method"]
990    fn cmp(&self, other: &Self) -> Ordering;
991
992    /// Compares and returns the maximum of two values.
993    ///
994    /// Returns the second argument if the comparison determines them to be equal.
995    ///
996    /// # Examples
997    ///
998    /// ```
999    /// assert_eq!(1.max(2), 2);
1000    /// assert_eq!(2.max(2), 2);
1001    /// ```
1002    /// ```
1003    /// use std::cmp::Ordering;
1004    ///
1005    /// #[derive(Eq)]
1006    /// struct Equal(&'static str);
1007    ///
1008    /// impl PartialEq for Equal {
1009    ///     fn eq(&self, other: &Self) -> bool { true }
1010    /// }
1011    /// impl PartialOrd for Equal {
1012    ///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(Ordering::Equal) }
1013    /// }
1014    /// impl Ord for Equal {
1015    ///     fn cmp(&self, other: &Self) -> Ordering { Ordering::Equal }
1016    /// }
1017    ///
1018    /// assert_eq!(Equal("self").max(Equal("other")).0, "other");
1019    /// ```
1020    #[stable(feature = "ord_max_min", since = "1.21.0")]
1021    #[inline]
1022    #[must_use]
1023    #[rustc_diagnostic_item = "cmp_ord_max"]
1024    fn max(self, other: Self) -> Self
1025    where
1026        Self: Sized,
1027    {
1028        if other < self { self } else { other }
1029    }
1030
1031    /// Compares and returns the minimum of two values.
1032    ///
1033    /// Returns the first argument if the comparison determines them to be equal.
1034    ///
1035    /// # Examples
1036    ///
1037    /// ```
1038    /// assert_eq!(1.min(2), 1);
1039    /// assert_eq!(2.min(2), 2);
1040    /// ```
1041    /// ```
1042    /// use std::cmp::Ordering;
1043    ///
1044    /// #[derive(Eq)]
1045    /// struct Equal(&'static str);
1046    ///
1047    /// impl PartialEq for Equal {
1048    ///     fn eq(&self, other: &Self) -> bool { true }
1049    /// }
1050    /// impl PartialOrd for Equal {
1051    ///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(Ordering::Equal) }
1052    /// }
1053    /// impl Ord for Equal {
1054    ///     fn cmp(&self, other: &Self) -> Ordering { Ordering::Equal }
1055    /// }
1056    ///
1057    /// assert_eq!(Equal("self").min(Equal("other")).0, "self");
1058    /// ```
1059    #[stable(feature = "ord_max_min", since = "1.21.0")]
1060    #[inline]
1061    #[must_use]
1062    #[rustc_diagnostic_item = "cmp_ord_min"]
1063    fn min(self, other: Self) -> Self
1064    where
1065        Self: Sized,
1066    {
1067        if other < self { other } else { self }
1068    }
1069
1070    /// Restrict a value to a certain interval.
1071    ///
1072    /// Returns `max` if `self` is greater than `max`, and `min` if `self` is
1073    /// less than `min`. Otherwise this returns `self`.
1074    ///
1075    /// # Panics
1076    ///
1077    /// Panics if `min > max`.
1078    ///
1079    /// # Examples
1080    ///
1081    /// ```
1082    /// assert_eq!((-3).clamp(-2, 1), -2);
1083    /// assert_eq!(0.clamp(-2, 1), 0);
1084    /// assert_eq!(2.clamp(-2, 1), 1);
1085    /// ```
1086    #[must_use]
1087    #[inline]
1088    #[stable(feature = "clamp", since = "1.50.0")]
1089    fn clamp(self, min: Self, max: Self) -> Self
1090    where
1091        Self: Sized,
1092    {
1093        assert!(min <= max);
1094        if self < min {
1095            min
1096        } else if self > max {
1097            max
1098        } else {
1099            self
1100        }
1101    }
1102}
1103
1104/// Derive macro generating an impl of the trait [`Ord`].
1105/// The behavior of this macro is described in detail [here](Ord#derivable).
1106#[rustc_builtin_macro]
1107#[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
1108#[allow_internal_unstable(core_intrinsics)]
1109#[cfg(not(feature = "ferrocene_certified"))]
1110pub macro Ord($item:item) {
1111    /* compiler built-in */
1112}
1113
1114/// Trait for types that form a [partial order](https://en.wikipedia.org/wiki/Partial_order).
1115///
1116/// The `lt`, `le`, `gt`, and `ge` methods of this trait can be called using the `<`, `<=`, `>`, and
1117/// `>=` operators, respectively.
1118///
1119/// This trait should **only** contain the comparison logic for a type **if one plans on only
1120/// implementing `PartialOrd` but not [`Ord`]**. Otherwise the comparison logic should be in [`Ord`]
1121/// and this trait implemented with `Some(self.cmp(other))`.
1122///
1123/// The methods of this trait must be consistent with each other and with those of [`PartialEq`].
1124/// The following conditions must hold:
1125///
1126/// 1. `a == b` if and only if `partial_cmp(a, b) == Some(Equal)`.
1127/// 2. `a < b` if and only if `partial_cmp(a, b) == Some(Less)`
1128/// 3. `a > b` if and only if `partial_cmp(a, b) == Some(Greater)`
1129/// 4. `a <= b` if and only if `a < b || a == b`
1130/// 5. `a >= b` if and only if `a > b || a == b`
1131/// 6. `a != b` if and only if `!(a == b)`.
1132///
1133/// Conditions 2–5 above are ensured by the default implementation. Condition 6 is already ensured
1134/// by [`PartialEq`].
1135///
1136/// If [`Ord`] is also implemented for `Self` and `Rhs`, it must also be consistent with
1137/// `partial_cmp` (see the documentation of that trait for the exact requirements). It's easy to
1138/// accidentally make them disagree by deriving some of the traits and manually implementing others.
1139///
1140/// The comparison relations must satisfy the following conditions (for all `a`, `b`, `c` of type
1141/// `A`, `B`, `C`):
1142///
1143/// - **Transitivity**: if `A: PartialOrd<B>` and `B: PartialOrd<C>` and `A: PartialOrd<C>`, then `a
1144///   < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`. This must also
1145///   work for longer chains, such as when `A: PartialOrd<B>`, `B: PartialOrd<C>`, `C:
1146///   PartialOrd<D>`, and `A: PartialOrd<D>` all exist.
1147/// - **Duality**: if `A: PartialOrd<B>` and `B: PartialOrd<A>`, then `a < b` if and only if `b >
1148///   a`.
1149///
1150/// Note that the `B: PartialOrd<A>` (dual) and `A: PartialOrd<C>` (transitive) impls are not forced
1151/// to exist, but these requirements apply whenever they do exist.
1152///
1153/// Violating these requirements is a logic error. The behavior resulting from a logic error is not
1154/// specified, but users of the trait must ensure that such logic errors do *not* result in
1155/// undefined behavior. This means that `unsafe` code **must not** rely on the correctness of these
1156/// methods.
1157///
1158/// ## Cross-crate considerations
1159///
1160/// Upholding the requirements stated above can become tricky when one crate implements `PartialOrd`
1161/// for a type of another crate (i.e., to allow comparing one of its own types with a type from the
1162/// standard library). The recommendation is to never implement this trait for a foreign type. In
1163/// other words, such a crate should do `impl PartialOrd<ForeignType> for LocalType`, but it should
1164/// *not* do `impl PartialOrd<LocalType> for ForeignType`.
1165///
1166/// This avoids the problem of transitive chains that criss-cross crate boundaries: for all local
1167/// types `T`, you may assume that no other crate will add `impl`s that allow comparing `T < U`. In
1168/// other words, if other crates add `impl`s that allow building longer transitive chains `U1 < ...
1169/// < T < V1 < ...`, then all the types that appear to the right of `T` must be types that the crate
1170/// defining `T` already knows about. This rules out transitive chains where downstream crates can
1171/// add new `impl`s that "stitch together" comparisons of foreign types in ways that violate
1172/// transitivity.
1173///
1174/// Not having such foreign `impl`s also avoids forward compatibility issues where one crate adding
1175/// more `PartialOrd` implementations can cause build failures in downstream crates.
1176///
1177/// ## Corollaries
1178///
1179/// The following corollaries follow from the above requirements:
1180///
1181/// - irreflexivity of `<` and `>`: `!(a < a)`, `!(a > a)`
1182/// - transitivity of `>`: if `a > b` and `b > c` then `a > c`
1183/// - duality of `partial_cmp`: `partial_cmp(a, b) == partial_cmp(b, a).map(Ordering::reverse)`
1184///
1185/// ## Strict and non-strict partial orders
1186///
1187/// The `<` and `>` operators behave according to a *strict* partial order. However, `<=` and `>=`
1188/// do **not** behave according to a *non-strict* partial order. That is because mathematically, a
1189/// non-strict partial order would require reflexivity, i.e. `a <= a` would need to be true for
1190/// every `a`. This isn't always the case for types that implement `PartialOrd`, for example:
1191///
1192/// ```
1193/// let a = f64::sqrt(-1.0);
1194/// assert_eq!(a <= a, false);
1195/// ```
1196///
1197/// ## Derivable
1198///
1199/// This trait can be used with `#[derive]`.
1200///
1201/// When `derive`d on structs, it will produce a
1202/// [lexicographic](https://en.wikipedia.org/wiki/Lexicographic_order) ordering based on the
1203/// top-to-bottom declaration order of the struct's members.
1204///
1205/// When `derive`d on enums, variants are primarily ordered by their discriminants. Secondarily,
1206/// they are ordered by their fields. By default, the discriminant is smallest for variants at the
1207/// top, and largest for variants at the bottom. Here's an example:
1208///
1209/// ```
1210/// #[derive(PartialEq, PartialOrd)]
1211/// enum E {
1212///     Top,
1213///     Bottom,
1214/// }
1215///
1216/// assert!(E::Top < E::Bottom);
1217/// ```
1218///
1219/// However, manually setting the discriminants can override this default behavior:
1220///
1221/// ```
1222/// #[derive(PartialEq, PartialOrd)]
1223/// enum E {
1224///     Top = 2,
1225///     Bottom = 1,
1226/// }
1227///
1228/// assert!(E::Bottom < E::Top);
1229/// ```
1230///
1231/// ## How can I implement `PartialOrd`?
1232///
1233/// `PartialOrd` only requires implementation of the [`partial_cmp`] method, with the others
1234/// generated from default implementations.
1235///
1236/// However it remains possible to implement the others separately for types which do not have a
1237/// total order. For example, for floating point numbers, `NaN < 0 == false` and `NaN >= 0 == false`
1238/// (cf. IEEE 754-2008 section 5.11).
1239///
1240/// `PartialOrd` requires your type to be [`PartialEq`].
1241///
1242/// If your type is [`Ord`], you can implement [`partial_cmp`] by using [`cmp`]:
1243///
1244/// ```
1245/// use std::cmp::Ordering;
1246///
1247/// struct Person {
1248///     id: u32,
1249///     name: String,
1250///     height: u32,
1251/// }
1252///
1253/// impl PartialOrd for Person {
1254///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1255///         Some(self.cmp(other))
1256///     }
1257/// }
1258///
1259/// impl Ord for Person {
1260///     fn cmp(&self, other: &Self) -> Ordering {
1261///         self.height.cmp(&other.height)
1262///     }
1263/// }
1264///
1265/// impl PartialEq for Person {
1266///     fn eq(&self, other: &Self) -> bool {
1267///         self.height == other.height
1268///     }
1269/// }
1270///
1271/// impl Eq for Person {}
1272/// ```
1273///
1274/// You may also find it useful to use [`partial_cmp`] on your type's fields. Here is an example of
1275/// `Person` types who have a floating-point `height` field that is the only field to be used for
1276/// sorting:
1277///
1278/// ```
1279/// use std::cmp::Ordering;
1280///
1281/// struct Person {
1282///     id: u32,
1283///     name: String,
1284///     height: f64,
1285/// }
1286///
1287/// impl PartialOrd for Person {
1288///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1289///         self.height.partial_cmp(&other.height)
1290///     }
1291/// }
1292///
1293/// impl PartialEq for Person {
1294///     fn eq(&self, other: &Self) -> bool {
1295///         self.height == other.height
1296///     }
1297/// }
1298/// ```
1299///
1300/// ## Examples of incorrect `PartialOrd` implementations
1301///
1302/// ```
1303/// use std::cmp::Ordering;
1304///
1305/// #[derive(PartialEq, Debug)]
1306/// struct Character {
1307///     health: u32,
1308///     experience: u32,
1309/// }
1310///
1311/// impl PartialOrd for Character {
1312///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1313///         Some(self.health.cmp(&other.health))
1314///     }
1315/// }
1316///
1317/// let a = Character {
1318///     health: 10,
1319///     experience: 5,
1320/// };
1321/// let b = Character {
1322///     health: 10,
1323///     experience: 77,
1324/// };
1325///
1326/// // Mistake: `PartialEq` and `PartialOrd` disagree with each other.
1327///
1328/// assert_eq!(a.partial_cmp(&b).unwrap(), Ordering::Equal); // a == b according to `PartialOrd`.
1329/// assert_ne!(a, b); // a != b according to `PartialEq`.
1330/// ```
1331///
1332/// # Examples
1333///
1334/// ```
1335/// let x: u32 = 0;
1336/// let y: u32 = 1;
1337///
1338/// assert_eq!(x < y, true);
1339/// assert_eq!(x.lt(&y), true);
1340/// ```
1341///
1342/// [`partial_cmp`]: PartialOrd::partial_cmp
1343/// [`cmp`]: Ord::cmp
1344#[lang = "partial_ord"]
1345#[stable(feature = "rust1", since = "1.0.0")]
1346#[doc(alias = ">")]
1347#[doc(alias = "<")]
1348#[doc(alias = "<=")]
1349#[doc(alias = ">=")]
1350#[rustc_on_unimplemented(
1351    message = "can't compare `{Self}` with `{Rhs}`",
1352    label = "no implementation for `{Self} < {Rhs}` and `{Self} > {Rhs}`",
1353    append_const_msg
1354)]
1355#[rustc_diagnostic_item = "PartialOrd"]
1356#[allow(multiple_supertrait_upcastable)] // FIXME(sized_hierarchy): remove this
1357pub trait PartialOrd<Rhs: PointeeSized = Self>: PartialEq<Rhs> + PointeeSized {
1358    /// This method returns an ordering between `self` and `other` values if one exists.
1359    ///
1360    /// # Examples
1361    ///
1362    /// ```
1363    /// use std::cmp::Ordering;
1364    ///
1365    /// let result = 1.0.partial_cmp(&2.0);
1366    /// assert_eq!(result, Some(Ordering::Less));
1367    ///
1368    /// let result = 1.0.partial_cmp(&1.0);
1369    /// assert_eq!(result, Some(Ordering::Equal));
1370    ///
1371    /// let result = 2.0.partial_cmp(&1.0);
1372    /// assert_eq!(result, Some(Ordering::Greater));
1373    /// ```
1374    ///
1375    /// When comparison is impossible:
1376    ///
1377    /// ```
1378    /// let result = f64::NAN.partial_cmp(&1.0);
1379    /// assert_eq!(result, None);
1380    /// ```
1381    #[must_use]
1382    #[stable(feature = "rust1", since = "1.0.0")]
1383    #[rustc_diagnostic_item = "cmp_partialord_cmp"]
1384    fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>;
1385
1386    /// Tests less than (for `self` and `other`) and is used by the `<` operator.
1387    ///
1388    /// # Examples
1389    ///
1390    /// ```
1391    /// assert_eq!(1.0 < 1.0, false);
1392    /// assert_eq!(1.0 < 2.0, true);
1393    /// assert_eq!(2.0 < 1.0, false);
1394    /// ```
1395    #[inline]
1396    #[must_use]
1397    #[stable(feature = "rust1", since = "1.0.0")]
1398    #[rustc_diagnostic_item = "cmp_partialord_lt"]
1399    fn lt(&self, other: &Rhs) -> bool {
1400        self.partial_cmp(other).is_some_and(Ordering::is_lt)
1401    }
1402
1403    /// Tests less than or equal to (for `self` and `other`) and is used by the
1404    /// `<=` operator.
1405    ///
1406    /// # Examples
1407    ///
1408    /// ```
1409    /// assert_eq!(1.0 <= 1.0, true);
1410    /// assert_eq!(1.0 <= 2.0, true);
1411    /// assert_eq!(2.0 <= 1.0, false);
1412    /// ```
1413    #[inline]
1414    #[must_use]
1415    #[stable(feature = "rust1", since = "1.0.0")]
1416    #[rustc_diagnostic_item = "cmp_partialord_le"]
1417    fn le(&self, other: &Rhs) -> bool {
1418        self.partial_cmp(other).is_some_and(Ordering::is_le)
1419    }
1420
1421    /// Tests greater than (for `self` and `other`) and is used by the `>`
1422    /// operator.
1423    ///
1424    /// # Examples
1425    ///
1426    /// ```
1427    /// assert_eq!(1.0 > 1.0, false);
1428    /// assert_eq!(1.0 > 2.0, false);
1429    /// assert_eq!(2.0 > 1.0, true);
1430    /// ```
1431    #[inline]
1432    #[must_use]
1433    #[stable(feature = "rust1", since = "1.0.0")]
1434    #[rustc_diagnostic_item = "cmp_partialord_gt"]
1435    fn gt(&self, other: &Rhs) -> bool {
1436        self.partial_cmp(other).is_some_and(Ordering::is_gt)
1437    }
1438
1439    /// Tests greater than or equal to (for `self` and `other`) and is used by
1440    /// the `>=` operator.
1441    ///
1442    /// # Examples
1443    ///
1444    /// ```
1445    /// assert_eq!(1.0 >= 1.0, true);
1446    /// assert_eq!(1.0 >= 2.0, false);
1447    /// assert_eq!(2.0 >= 1.0, true);
1448    /// ```
1449    #[inline]
1450    #[must_use]
1451    #[stable(feature = "rust1", since = "1.0.0")]
1452    #[rustc_diagnostic_item = "cmp_partialord_ge"]
1453    fn ge(&self, other: &Rhs) -> bool {
1454        self.partial_cmp(other).is_some_and(Ordering::is_ge)
1455    }
1456
1457    /// If `self == other`, returns `ControlFlow::Continue(())`.
1458    /// Otherwise, returns `ControlFlow::Break(self < other)`.
1459    ///
1460    /// This is useful for chaining together calls when implementing a lexical
1461    /// `PartialOrd::lt`, as it allows types (like primitives) which can cheaply
1462    /// check `==` and `<` separately to do rather than needing to calculate
1463    /// (then optimize out) the three-way `Ordering` result.
1464    #[inline]
1465    // Added to improve the behaviour of tuples; not necessarily stabilization-track.
1466    #[unstable(feature = "partial_ord_chaining_methods", issue = "none")]
1467    #[doc(hidden)]
1468    fn __chaining_lt(&self, other: &Rhs) -> ControlFlow<bool> {
1469        default_chaining_impl(self, other, Ordering::is_lt)
1470    }
1471
1472    /// Same as `__chaining_lt`, but for `<=` instead of `<`.
1473    #[inline]
1474    #[unstable(feature = "partial_ord_chaining_methods", issue = "none")]
1475    #[doc(hidden)]
1476    fn __chaining_le(&self, other: &Rhs) -> ControlFlow<bool> {
1477        default_chaining_impl(self, other, Ordering::is_le)
1478    }
1479
1480    /// Same as `__chaining_lt`, but for `>` instead of `<`.
1481    #[inline]
1482    #[unstable(feature = "partial_ord_chaining_methods", issue = "none")]
1483    #[doc(hidden)]
1484    fn __chaining_gt(&self, other: &Rhs) -> ControlFlow<bool> {
1485        default_chaining_impl(self, other, Ordering::is_gt)
1486    }
1487
1488    /// Same as `__chaining_lt`, but for `>=` instead of `<`.
1489    #[inline]
1490    #[unstable(feature = "partial_ord_chaining_methods", issue = "none")]
1491    #[doc(hidden)]
1492    fn __chaining_ge(&self, other: &Rhs) -> ControlFlow<bool> {
1493        default_chaining_impl(self, other, Ordering::is_ge)
1494    }
1495}
1496
1497fn default_chaining_impl<T, U>(
1498    lhs: &T,
1499    rhs: &U,
1500    p: impl FnOnce(Ordering) -> bool,
1501) -> ControlFlow<bool>
1502where
1503    T: PartialOrd<U> + PointeeSized,
1504    U: PointeeSized,
1505{
1506    // It's important that this only call `partial_cmp` once, not call `eq` then
1507    // one of the relational operators.  We don't want to `bcmp`-then-`memcp` a
1508    // `String`, for example, or similarly for other data structures (#108157).
1509    match <T as PartialOrd<U>>::partial_cmp(lhs, rhs) {
1510        Some(Equal) => ControlFlow::Continue(()),
1511        Some(c) => ControlFlow::Break(p(c)),
1512        None => ControlFlow::Break(false),
1513    }
1514}
1515
1516/// Derive macro generating an impl of the trait [`PartialOrd`].
1517/// The behavior of this macro is described in detail [here](PartialOrd#derivable).
1518#[rustc_builtin_macro]
1519#[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
1520#[allow_internal_unstable(core_intrinsics)]
1521#[cfg(not(feature = "ferrocene_certified"))]
1522pub macro PartialOrd($item:item) {
1523    /* compiler built-in */
1524}
1525
1526/// Compares and returns the minimum of two values.
1527///
1528/// Returns the first argument if the comparison determines them to be equal.
1529///
1530/// Internally uses an alias to [`Ord::min`].
1531///
1532/// # Examples
1533///
1534/// ```
1535/// use std::cmp;
1536///
1537/// assert_eq!(cmp::min(1, 2), 1);
1538/// assert_eq!(cmp::min(2, 2), 2);
1539/// ```
1540/// ```
1541/// use std::cmp::{self, Ordering};
1542///
1543/// #[derive(Eq)]
1544/// struct Equal(&'static str);
1545///
1546/// impl PartialEq for Equal {
1547///     fn eq(&self, other: &Self) -> bool { true }
1548/// }
1549/// impl PartialOrd for Equal {
1550///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(Ordering::Equal) }
1551/// }
1552/// impl Ord for Equal {
1553///     fn cmp(&self, other: &Self) -> Ordering { Ordering::Equal }
1554/// }
1555///
1556/// assert_eq!(cmp::min(Equal("v1"), Equal("v2")).0, "v1");
1557/// ```
1558#[inline]
1559#[must_use]
1560#[stable(feature = "rust1", since = "1.0.0")]
1561#[rustc_diagnostic_item = "cmp_min"]
1562pub fn min<T: Ord>(v1: T, v2: T) -> T {
1563    v1.min(v2)
1564}
1565
1566/// Returns the minimum of two values with respect to the specified comparison function.
1567///
1568/// Returns the first argument if the comparison determines them to be equal.
1569///
1570/// The parameter order is preserved when calling the `compare` function, i.e. `v1` is
1571/// always passed as the first argument and `v2` as the second.
1572///
1573/// # Examples
1574///
1575/// ```
1576/// use std::cmp;
1577///
1578/// let abs_cmp = |x: &i32, y: &i32| x.abs().cmp(&y.abs());
1579///
1580/// let result = cmp::min_by(2, -1, abs_cmp);
1581/// assert_eq!(result, -1);
1582///
1583/// let result = cmp::min_by(2, -3, abs_cmp);
1584/// assert_eq!(result, 2);
1585///
1586/// let result = cmp::min_by(1, -1, abs_cmp);
1587/// assert_eq!(result, 1);
1588/// ```
1589#[inline]
1590#[must_use]
1591#[stable(feature = "cmp_min_max_by", since = "1.53.0")]
1592#[cfg(not(feature = "ferrocene_certified"))]
1593pub fn min_by<T, F: FnOnce(&T, &T) -> Ordering>(v1: T, v2: T, compare: F) -> T {
1594    if compare(&v1, &v2).is_le() { v1 } else { v2 }
1595}
1596
1597/// Returns the element that gives the minimum value from the specified function.
1598///
1599/// Returns the first argument if the comparison determines them to be equal.
1600///
1601/// # Examples
1602///
1603/// ```
1604/// use std::cmp;
1605///
1606/// let result = cmp::min_by_key(2, -1, |x: &i32| x.abs());
1607/// assert_eq!(result, -1);
1608///
1609/// let result = cmp::min_by_key(2, -3, |x: &i32| x.abs());
1610/// assert_eq!(result, 2);
1611///
1612/// let result = cmp::min_by_key(1, -1, |x: &i32| x.abs());
1613/// assert_eq!(result, 1);
1614/// ```
1615#[inline]
1616#[must_use]
1617#[stable(feature = "cmp_min_max_by", since = "1.53.0")]
1618#[cfg(not(feature = "ferrocene_certified"))]
1619pub fn min_by_key<T, F: FnMut(&T) -> K, K: Ord>(v1: T, v2: T, mut f: F) -> T {
1620    if f(&v2) < f(&v1) { v2 } else { v1 }
1621}
1622
1623/// Compares and returns the maximum of two values.
1624///
1625/// Returns the second argument if the comparison determines them to be equal.
1626///
1627/// Internally uses an alias to [`Ord::max`].
1628///
1629/// # Examples
1630///
1631/// ```
1632/// use std::cmp;
1633///
1634/// assert_eq!(cmp::max(1, 2), 2);
1635/// assert_eq!(cmp::max(2, 2), 2);
1636/// ```
1637/// ```
1638/// use std::cmp::{self, Ordering};
1639///
1640/// #[derive(Eq)]
1641/// struct Equal(&'static str);
1642///
1643/// impl PartialEq for Equal {
1644///     fn eq(&self, other: &Self) -> bool { true }
1645/// }
1646/// impl PartialOrd for Equal {
1647///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(Ordering::Equal) }
1648/// }
1649/// impl Ord for Equal {
1650///     fn cmp(&self, other: &Self) -> Ordering { Ordering::Equal }
1651/// }
1652///
1653/// assert_eq!(cmp::max(Equal("v1"), Equal("v2")).0, "v2");
1654/// ```
1655#[inline]
1656#[must_use]
1657#[stable(feature = "rust1", since = "1.0.0")]
1658#[rustc_diagnostic_item = "cmp_max"]
1659pub fn max<T: Ord>(v1: T, v2: T) -> T {
1660    v1.max(v2)
1661}
1662
1663/// Returns the maximum of two values with respect to the specified comparison function.
1664///
1665/// Returns the second argument if the comparison determines them to be equal.
1666///
1667/// The parameter order is preserved when calling the `compare` function, i.e. `v1` is
1668/// always passed as the first argument and `v2` as the second.
1669///
1670/// # Examples
1671///
1672/// ```
1673/// use std::cmp;
1674///
1675/// let abs_cmp = |x: &i32, y: &i32| x.abs().cmp(&y.abs());
1676///
1677/// let result = cmp::max_by(3, -2, abs_cmp) ;
1678/// assert_eq!(result, 3);
1679///
1680/// let result = cmp::max_by(1, -2, abs_cmp);
1681/// assert_eq!(result, -2);
1682///
1683/// let result = cmp::max_by(1, -1, abs_cmp);
1684/// assert_eq!(result, -1);
1685/// ```
1686#[inline]
1687#[must_use]
1688#[stable(feature = "cmp_min_max_by", since = "1.53.0")]
1689#[cfg(not(feature = "ferrocene_certified"))]
1690pub fn max_by<T, F: FnOnce(&T, &T) -> Ordering>(v1: T, v2: T, compare: F) -> T {
1691    if compare(&v1, &v2).is_gt() { v1 } else { v2 }
1692}
1693
1694/// Returns the element that gives the maximum value from the specified function.
1695///
1696/// Returns the second argument if the comparison determines them to be equal.
1697///
1698/// # Examples
1699///
1700/// ```
1701/// use std::cmp;
1702///
1703/// let result = cmp::max_by_key(3, -2, |x: &i32| x.abs());
1704/// assert_eq!(result, 3);
1705///
1706/// let result = cmp::max_by_key(1, -2, |x: &i32| x.abs());
1707/// assert_eq!(result, -2);
1708///
1709/// let result = cmp::max_by_key(1, -1, |x: &i32| x.abs());
1710/// assert_eq!(result, -1);
1711/// ```
1712#[inline]
1713#[must_use]
1714#[stable(feature = "cmp_min_max_by", since = "1.53.0")]
1715#[cfg(not(feature = "ferrocene_certified"))]
1716pub fn max_by_key<T, F: FnMut(&T) -> K, K: Ord>(v1: T, v2: T, mut f: F) -> T {
1717    if f(&v2) < f(&v1) { v1 } else { v2 }
1718}
1719
1720/// Compares and sorts two values, returning minimum and maximum.
1721///
1722/// Returns `[v1, v2]` if the comparison determines them to be equal.
1723///
1724/// # Examples
1725///
1726/// ```
1727/// #![feature(cmp_minmax)]
1728/// use std::cmp;
1729///
1730/// assert_eq!(cmp::minmax(1, 2), [1, 2]);
1731/// assert_eq!(cmp::minmax(2, 1), [1, 2]);
1732///
1733/// // You can destructure the result using array patterns
1734/// let [min, max] = cmp::minmax(42, 17);
1735/// assert_eq!(min, 17);
1736/// assert_eq!(max, 42);
1737/// ```
1738/// ```
1739/// #![feature(cmp_minmax)]
1740/// use std::cmp::{self, Ordering};
1741///
1742/// #[derive(Eq)]
1743/// struct Equal(&'static str);
1744///
1745/// impl PartialEq for Equal {
1746///     fn eq(&self, other: &Self) -> bool { true }
1747/// }
1748/// impl PartialOrd for Equal {
1749///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(Ordering::Equal) }
1750/// }
1751/// impl Ord for Equal {
1752///     fn cmp(&self, other: &Self) -> Ordering { Ordering::Equal }
1753/// }
1754///
1755/// assert_eq!(cmp::minmax(Equal("v1"), Equal("v2")).map(|v| v.0), ["v1", "v2"]);
1756/// ```
1757#[inline]
1758#[must_use]
1759#[unstable(feature = "cmp_minmax", issue = "115939")]
1760#[cfg(not(feature = "ferrocene_certified"))]
1761pub fn minmax<T>(v1: T, v2: T) -> [T; 2]
1762where
1763    T: Ord,
1764{
1765    if v2 < v1 { [v2, v1] } else { [v1, v2] }
1766}
1767
1768/// Returns minimum and maximum values with respect to the specified comparison function.
1769///
1770/// Returns `[v1, v2]` if the comparison determines them to be equal.
1771///
1772/// The parameter order is preserved when calling the `compare` function, i.e. `v1` is
1773/// always passed as the first argument and `v2` as the second.
1774///
1775/// # Examples
1776///
1777/// ```
1778/// #![feature(cmp_minmax)]
1779/// use std::cmp;
1780///
1781/// let abs_cmp = |x: &i32, y: &i32| x.abs().cmp(&y.abs());
1782///
1783/// assert_eq!(cmp::minmax_by(-2, 1, abs_cmp), [1, -2]);
1784/// assert_eq!(cmp::minmax_by(-1, 2, abs_cmp), [-1, 2]);
1785/// assert_eq!(cmp::minmax_by(-2, 2, abs_cmp), [-2, 2]);
1786///
1787/// // You can destructure the result using array patterns
1788/// let [min, max] = cmp::minmax_by(-42, 17, abs_cmp);
1789/// assert_eq!(min, 17);
1790/// assert_eq!(max, -42);
1791/// ```
1792#[inline]
1793#[must_use]
1794#[unstable(feature = "cmp_minmax", issue = "115939")]
1795#[cfg(not(feature = "ferrocene_certified"))]
1796pub fn minmax_by<T, F>(v1: T, v2: T, compare: F) -> [T; 2]
1797where
1798    F: FnOnce(&T, &T) -> Ordering,
1799{
1800    if compare(&v1, &v2).is_le() { [v1, v2] } else { [v2, v1] }
1801}
1802
1803/// Returns minimum and maximum values with respect to the specified key function.
1804///
1805/// Returns `[v1, v2]` if the comparison determines them to be equal.
1806///
1807/// # Examples
1808///
1809/// ```
1810/// #![feature(cmp_minmax)]
1811/// use std::cmp;
1812///
1813/// assert_eq!(cmp::minmax_by_key(-2, 1, |x: &i32| x.abs()), [1, -2]);
1814/// assert_eq!(cmp::minmax_by_key(-2, 2, |x: &i32| x.abs()), [-2, 2]);
1815///
1816/// // You can destructure the result using array patterns
1817/// let [min, max] = cmp::minmax_by_key(-42, 17, |x: &i32| x.abs());
1818/// assert_eq!(min, 17);
1819/// assert_eq!(max, -42);
1820/// ```
1821#[inline]
1822#[must_use]
1823#[unstable(feature = "cmp_minmax", issue = "115939")]
1824#[cfg(not(feature = "ferrocene_certified"))]
1825pub fn minmax_by_key<T, F, K>(v1: T, v2: T, mut f: F) -> [T; 2]
1826where
1827    F: FnMut(&T) -> K,
1828    K: Ord,
1829{
1830    if f(&v2) < f(&v1) { [v2, v1] } else { [v1, v2] }
1831}
1832
1833// Implementation of PartialEq, Eq, PartialOrd and Ord for primitive types
1834mod impls {
1835    use crate::cmp::Ordering::{self, Equal, Greater, Less};
1836    use crate::hint::unreachable_unchecked;
1837    #[cfg(not(feature = "ferrocene_certified"))]
1838    use crate::marker::PointeeSized;
1839    use crate::ops::ControlFlow::{self, Break, Continue};
1840
1841    macro_rules! partial_eq_impl {
1842        ($($t:ty)*) => ($(
1843            #[stable(feature = "rust1", since = "1.0.0")]
1844            #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
1845            impl const PartialEq for $t {
1846                #[inline]
1847                fn eq(&self, other: &Self) -> bool { *self == *other }
1848                #[inline]
1849                fn ne(&self, other: &Self) -> bool { *self != *other }
1850            }
1851        )*)
1852    }
1853
1854    #[stable(feature = "rust1", since = "1.0.0")]
1855    #[cfg(not(feature = "ferrocene_certified"))]
1856    impl PartialEq for () {
1857        #[inline]
1858        fn eq(&self, _other: &()) -> bool {
1859            true
1860        }
1861        #[inline]
1862        fn ne(&self, _other: &()) -> bool {
1863            false
1864        }
1865    }
1866
1867    #[cfg(not(feature = "ferrocene_certified"))]
1868    partial_eq_impl! {
1869        bool char usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f16 f32 f64 f128
1870    }
1871
1872    #[cfg(feature = "ferrocene_certified")]
1873    partial_eq_impl! {
1874        bool usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f32 f64
1875    }
1876
1877    macro_rules! eq_impl {
1878        ($($t:ty)*) => ($(
1879            #[stable(feature = "rust1", since = "1.0.0")]
1880            impl Eq for $t {}
1881        )*)
1882    }
1883
1884    #[cfg(not(feature = "ferrocene_certified"))]
1885    eq_impl! { () bool char usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 }
1886
1887    #[cfg(feature = "ferrocene_certified")]
1888    eq_impl! { bool usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 }
1889
1890    #[rustfmt::skip]
1891    macro_rules! partial_ord_methods_primitive_impl {
1892        () => {
1893            #[inline(always)]
1894            fn lt(&self, other: &Self) -> bool { *self <  *other }
1895            #[inline(always)]
1896            fn le(&self, other: &Self) -> bool { *self <= *other }
1897            #[inline(always)]
1898            fn gt(&self, other: &Self) -> bool { *self >  *other }
1899            #[inline(always)]
1900            fn ge(&self, other: &Self) -> bool { *self >= *other }
1901
1902            // These implementations are the same for `Ord` or `PartialOrd` types
1903            // because if either is NAN the `==` test will fail so we end up in
1904            // the `Break` case and the comparison will correctly return `false`.
1905
1906            #[inline]
1907            fn __chaining_lt(&self, other: &Self) -> ControlFlow<bool> {
1908                let (lhs, rhs) = (*self, *other);
1909                if lhs == rhs { Continue(()) } else { Break(lhs < rhs) }
1910            }
1911            #[inline]
1912            fn __chaining_le(&self, other: &Self) -> ControlFlow<bool> {
1913                let (lhs, rhs) = (*self, *other);
1914                if lhs == rhs { Continue(()) } else { Break(lhs <= rhs) }
1915            }
1916            #[inline]
1917            fn __chaining_gt(&self, other: &Self) -> ControlFlow<bool> {
1918                let (lhs, rhs) = (*self, *other);
1919                if lhs == rhs { Continue(()) } else { Break(lhs > rhs) }
1920            }
1921            #[inline]
1922            fn __chaining_ge(&self, other: &Self) -> ControlFlow<bool> {
1923                let (lhs, rhs) = (*self, *other);
1924                if lhs == rhs { Continue(()) } else { Break(lhs >= rhs) }
1925            }
1926        };
1927    }
1928
1929    macro_rules! partial_ord_impl {
1930        ($($t:ty)*) => ($(
1931            #[stable(feature = "rust1", since = "1.0.0")]
1932            impl PartialOrd for $t {
1933                #[inline]
1934                fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1935                    match (*self <= *other, *self >= *other) {
1936                        (false, false) => None,
1937                        (false, true) => Some(Greater),
1938                        (true, false) => Some(Less),
1939                        (true, true) => Some(Equal),
1940                    }
1941                }
1942
1943                partial_ord_methods_primitive_impl!();
1944            }
1945        )*)
1946    }
1947
1948    #[stable(feature = "rust1", since = "1.0.0")]
1949    #[cfg(not(feature = "ferrocene_certified"))]
1950    impl PartialOrd for () {
1951        #[inline]
1952        fn partial_cmp(&self, _: &()) -> Option<Ordering> {
1953            Some(Equal)
1954        }
1955    }
1956
1957    #[stable(feature = "rust1", since = "1.0.0")]
1958    impl PartialOrd for bool {
1959        #[inline]
1960        fn partial_cmp(&self, other: &bool) -> Option<Ordering> {
1961            Some(self.cmp(other))
1962        }
1963
1964        partial_ord_methods_primitive_impl!();
1965    }
1966
1967    #[cfg(not(feature = "ferrocene_certified"))]
1968    partial_ord_impl! { f16 f32 f64 f128 }
1969
1970    #[cfg(feature = "ferrocene_certified")]
1971    partial_ord_impl! { f32 f64 }
1972
1973    macro_rules! ord_impl {
1974        ($($t:ty)*) => ($(
1975            #[stable(feature = "rust1", since = "1.0.0")]
1976            impl PartialOrd for $t {
1977                #[inline]
1978                fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1979                    Some(crate::intrinsics::three_way_compare(*self, *other))
1980                }
1981
1982                partial_ord_methods_primitive_impl!();
1983            }
1984
1985            #[stable(feature = "rust1", since = "1.0.0")]
1986            impl Ord for $t {
1987                #[inline]
1988                fn cmp(&self, other: &Self) -> Ordering {
1989                    crate::intrinsics::three_way_compare(*self, *other)
1990                }
1991            }
1992        )*)
1993    }
1994
1995    #[stable(feature = "rust1", since = "1.0.0")]
1996    #[cfg(not(feature = "ferrocene_certified"))]
1997    impl Ord for () {
1998        #[inline]
1999        fn cmp(&self, _other: &()) -> Ordering {
2000            Equal
2001        }
2002    }
2003
2004    #[stable(feature = "rust1", since = "1.0.0")]
2005    impl Ord for bool {
2006        #[inline]
2007        fn cmp(&self, other: &bool) -> Ordering {
2008            // Casting to i8's and converting the difference to an Ordering generates
2009            // more optimal assembly.
2010            // See <https://github.com/rust-lang/rust/issues/66780> for more info.
2011            match (*self as i8) - (*other as i8) {
2012                -1 => Less,
2013                0 => Equal,
2014                1 => Greater,
2015                // Ferrocene annotation: This match arm cannot be covered because it is unreachable.
2016                // See the safety comment below.
2017                //
2018                // SAFETY: bool as i8 returns 0 or 1, so the difference can't be anything else
2019                _ => unsafe { unreachable_unchecked() },
2020            }
2021        }
2022
2023        #[inline]
2024        fn min(self, other: bool) -> bool {
2025            self & other
2026        }
2027
2028        #[inline]
2029        fn max(self, other: bool) -> bool {
2030            self | other
2031        }
2032
2033        #[inline]
2034        fn clamp(self, min: bool, max: bool) -> bool {
2035            assert!(min <= max);
2036            self.max(min).min(max)
2037        }
2038    }
2039
2040    #[cfg(not(feature = "ferrocene_certified"))]
2041    ord_impl! { char usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 }
2042
2043    #[cfg(feature = "ferrocene_certified")]
2044    ord_impl! { usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 }
2045
2046    #[unstable(feature = "never_type", issue = "35121")]
2047    #[cfg(not(feature = "ferrocene_certified"))]
2048    impl PartialEq for ! {
2049        #[inline]
2050        fn eq(&self, _: &!) -> bool {
2051            *self
2052        }
2053    }
2054
2055    #[unstable(feature = "never_type", issue = "35121")]
2056    #[cfg(not(feature = "ferrocene_certified"))]
2057    impl Eq for ! {}
2058
2059    #[unstable(feature = "never_type", issue = "35121")]
2060    #[cfg(not(feature = "ferrocene_certified"))]
2061    impl PartialOrd for ! {
2062        #[inline]
2063        fn partial_cmp(&self, _: &!) -> Option<Ordering> {
2064            *self
2065        }
2066    }
2067
2068    #[unstable(feature = "never_type", issue = "35121")]
2069    #[cfg(not(feature = "ferrocene_certified"))]
2070    impl Ord for ! {
2071        #[inline]
2072        fn cmp(&self, _: &!) -> Ordering {
2073            *self
2074        }
2075    }
2076
2077    // & pointers
2078
2079    #[stable(feature = "rust1", since = "1.0.0")]
2080    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
2081    #[cfg(not(feature = "ferrocene_certified"))]
2082    impl<A: PointeeSized, B: PointeeSized> const PartialEq<&B> for &A
2083    where
2084        A: [const] PartialEq<B>,
2085    {
2086        #[inline]
2087        fn eq(&self, other: &&B) -> bool {
2088            PartialEq::eq(*self, *other)
2089        }
2090        #[inline]
2091        fn ne(&self, other: &&B) -> bool {
2092            PartialEq::ne(*self, *other)
2093        }
2094    }
2095    #[stable(feature = "rust1", since = "1.0.0")]
2096    #[cfg(not(feature = "ferrocene_certified"))]
2097    impl<A: PointeeSized, B: PointeeSized> PartialOrd<&B> for &A
2098    where
2099        A: PartialOrd<B>,
2100    {
2101        #[inline]
2102        fn partial_cmp(&self, other: &&B) -> Option<Ordering> {
2103            PartialOrd::partial_cmp(*self, *other)
2104        }
2105        #[inline]
2106        fn lt(&self, other: &&B) -> bool {
2107            PartialOrd::lt(*self, *other)
2108        }
2109        #[inline]
2110        fn le(&self, other: &&B) -> bool {
2111            PartialOrd::le(*self, *other)
2112        }
2113        #[inline]
2114        fn gt(&self, other: &&B) -> bool {
2115            PartialOrd::gt(*self, *other)
2116        }
2117        #[inline]
2118        fn ge(&self, other: &&B) -> bool {
2119            PartialOrd::ge(*self, *other)
2120        }
2121        #[inline]
2122        fn __chaining_lt(&self, other: &&B) -> ControlFlow<bool> {
2123            PartialOrd::__chaining_lt(*self, *other)
2124        }
2125        #[inline]
2126        fn __chaining_le(&self, other: &&B) -> ControlFlow<bool> {
2127            PartialOrd::__chaining_le(*self, *other)
2128        }
2129        #[inline]
2130        fn __chaining_gt(&self, other: &&B) -> ControlFlow<bool> {
2131            PartialOrd::__chaining_gt(*self, *other)
2132        }
2133        #[inline]
2134        fn __chaining_ge(&self, other: &&B) -> ControlFlow<bool> {
2135            PartialOrd::__chaining_ge(*self, *other)
2136        }
2137    }
2138    #[stable(feature = "rust1", since = "1.0.0")]
2139    #[cfg(not(feature = "ferrocene_certified"))]
2140    impl<A: PointeeSized> Ord for &A
2141    where
2142        A: Ord,
2143    {
2144        #[inline]
2145        fn cmp(&self, other: &Self) -> Ordering {
2146            Ord::cmp(*self, *other)
2147        }
2148    }
2149    #[stable(feature = "rust1", since = "1.0.0")]
2150    #[cfg(not(feature = "ferrocene_certified"))]
2151    impl<A: PointeeSized> Eq for &A where A: Eq {}
2152
2153    // &mut pointers
2154
2155    #[stable(feature = "rust1", since = "1.0.0")]
2156    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
2157    #[cfg(not(feature = "ferrocene_certified"))]
2158    impl<A: PointeeSized, B: PointeeSized> const PartialEq<&mut B> for &mut A
2159    where
2160        A: [const] PartialEq<B>,
2161    {
2162        #[inline]
2163        fn eq(&self, other: &&mut B) -> bool {
2164            PartialEq::eq(*self, *other)
2165        }
2166        #[inline]
2167        fn ne(&self, other: &&mut B) -> bool {
2168            PartialEq::ne(*self, *other)
2169        }
2170    }
2171    #[stable(feature = "rust1", since = "1.0.0")]
2172    #[cfg(not(feature = "ferrocene_certified"))]
2173    impl<A: PointeeSized, B: PointeeSized> PartialOrd<&mut B> for &mut A
2174    where
2175        A: PartialOrd<B>,
2176    {
2177        #[inline]
2178        fn partial_cmp(&self, other: &&mut B) -> Option<Ordering> {
2179            PartialOrd::partial_cmp(*self, *other)
2180        }
2181        #[inline]
2182        fn lt(&self, other: &&mut B) -> bool {
2183            PartialOrd::lt(*self, *other)
2184        }
2185        #[inline]
2186        fn le(&self, other: &&mut B) -> bool {
2187            PartialOrd::le(*self, *other)
2188        }
2189        #[inline]
2190        fn gt(&self, other: &&mut B) -> bool {
2191            PartialOrd::gt(*self, *other)
2192        }
2193        #[inline]
2194        fn ge(&self, other: &&mut B) -> bool {
2195            PartialOrd::ge(*self, *other)
2196        }
2197        #[inline]
2198        fn __chaining_lt(&self, other: &&mut B) -> ControlFlow<bool> {
2199            PartialOrd::__chaining_lt(*self, *other)
2200        }
2201        #[inline]
2202        fn __chaining_le(&self, other: &&mut B) -> ControlFlow<bool> {
2203            PartialOrd::__chaining_le(*self, *other)
2204        }
2205        #[inline]
2206        fn __chaining_gt(&self, other: &&mut B) -> ControlFlow<bool> {
2207            PartialOrd::__chaining_gt(*self, *other)
2208        }
2209        #[inline]
2210        fn __chaining_ge(&self, other: &&mut B) -> ControlFlow<bool> {
2211            PartialOrd::__chaining_ge(*self, *other)
2212        }
2213    }
2214    #[stable(feature = "rust1", since = "1.0.0")]
2215    #[cfg(not(feature = "ferrocene_certified"))]
2216    impl<A: PointeeSized> Ord for &mut A
2217    where
2218        A: Ord,
2219    {
2220        #[inline]
2221        fn cmp(&self, other: &Self) -> Ordering {
2222            Ord::cmp(*self, *other)
2223        }
2224    }
2225    #[stable(feature = "rust1", since = "1.0.0")]
2226    #[cfg(not(feature = "ferrocene_certified"))]
2227    impl<A: PointeeSized> Eq for &mut A where A: Eq {}
2228
2229    #[stable(feature = "rust1", since = "1.0.0")]
2230    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
2231    #[cfg(not(feature = "ferrocene_certified"))]
2232    impl<A: PointeeSized, B: PointeeSized> const PartialEq<&mut B> for &A
2233    where
2234        A: [const] PartialEq<B>,
2235    {
2236        #[inline]
2237        fn eq(&self, other: &&mut B) -> bool {
2238            PartialEq::eq(*self, *other)
2239        }
2240        #[inline]
2241        fn ne(&self, other: &&mut B) -> bool {
2242            PartialEq::ne(*self, *other)
2243        }
2244    }
2245
2246    #[stable(feature = "rust1", since = "1.0.0")]
2247    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
2248    #[cfg(not(feature = "ferrocene_certified"))]
2249    impl<A: PointeeSized, B: PointeeSized> const PartialEq<&B> for &mut A
2250    where
2251        A: [const] PartialEq<B>,
2252    {
2253        #[inline]
2254        fn eq(&self, other: &&B) -> bool {
2255            PartialEq::eq(*self, *other)
2256        }
2257        #[inline]
2258        fn ne(&self, other: &&B) -> bool {
2259            PartialEq::ne(*self, *other)
2260        }
2261    }
2262}