cmp.rs - source
Description: Source of the Rust file `library/core/src/cmp.rs`.

#
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
    28mod bytewise;
    29pub(crate) use bytewise::BytewiseEq;
    30
    31use self::Ordering::*;
    32use crate::marker::{Destruct, PointeeSized};
    33use crate::ops::ControlFlow;
    34
    35/// Trait for comparisons using the equality operator.
    36///
    37/// Implementing this trait for types provides the `==` and `!=` operators for
    38/// those types.
    39///
    40/// `x.eq(y)` can also be written `x == y`, and `x.ne(y)` can be written `x != y`.
    41/// We use the easier-to-read infix notation in the remainder of this documentation.
    42///
    43/// This trait allows for comparisons using the equality operator, for types
    44/// that do not have a full equivalence relation. For example, in floating point
    45/// numbers `NaN != NaN`, so floating point types implement `PartialEq` but not
    46/// [`trait@Eq`]. Formally speaking, when `Rhs == Self`, this trait corresponds
    47/// to a [partial equivalence relation].
    48///
    49/// [partial equivalence relation]: https://en.wikipedia.org/wiki/Partial_equivalence_relation
    50///
    51/// Implementations must ensure that `eq` and `ne` are consistent with each other:
    52///
    53/// - `a != b` if and only if `!(a == b)`.
    54///
    55/// The default implementation of `ne` provides this consistency and is almost
    56/// always sufficient. It should not be overridden without very good reason.
    57///
    58/// If [`PartialOrd`] or [`Ord`] are also implemented for `Self` and `Rhs`, their methods must also
    59/// be consistent with `PartialEq` (see the documentation of those traits for the exact
    60/// requirements). It's easy to accidentally make them disagree by deriving some of the traits and
    61/// manually implementing others.
    62///
    63/// The equality relation `==` must satisfy the following conditions
    64/// (for all `a`, `b`, `c` of type `A`, `B`, `C`):
    65///
    66/// - **Symmetry**: if `A: PartialEq<B>` and `B: PartialEq<A>`, then **`a == b`
    67///   implies `b == a`**; and
    68///
    69/// - **Transitivity**: if `A: PartialEq<B>` and `B: PartialEq<C>` and `A:
    70///   PartialEq<C>`, then **`a == b` and `b == c` implies `a == c`**.
    71///   This must also work for longer chains, such as when `A: PartialEq<B>`, `B: PartialEq<C>`,
    72///   `C: PartialEq<D>`, and `A: PartialEq<D>` all exist.
    73///
    74/// Note that the `B: PartialEq<A>` (symmetric) and `A: PartialEq<C>`
    75/// (transitive) impls are not forced to exist, but these requirements apply
    76/// whenever they do exist.
    77///
    78/// Violating these requirements is a logic error. The behavior resulting from a logic error is not
    79/// specified, but users of the trait must ensure that such logic errors do *not* result in
    80/// undefined behavior. This means that `unsafe` code **must not** rely on the correctness of these
    81/// methods.
    82///
    83/// ## Cross-crate considerations
    84///
    85/// Upholding the requirements stated above can become tricky when one crate implements `PartialEq`
    86/// for a type of another crate (i.e., to allow comparing one of its own types with a type from the
    87/// standard library). The recommendation is to never implement this trait for a foreign type. In
    88/// other words, such a crate should do `impl PartialEq<ForeignType> for LocalType`, but it should
    89/// *not* do `impl PartialEq<LocalType> for ForeignType`.
    90///
    91/// This avoids the problem of transitive chains that criss-cross crate boundaries: for all local
    92/// types `T`, you may assume that no other crate will add `impl`s that allow comparing `T == U`. In
    93/// other words, if other crates add `impl`s that allow building longer transitive chains `U1 == ...
    94/// == T == V1 == ...`, then all the types that appear to the right of `T` must be types that the
    95/// crate defining `T` already knows about. This rules out transitive chains where downstream crates
    96/// can add new `impl`s that "stitch together" comparisons of foreign types in ways that violate
    97/// transitivity.
    98///
    99/// Not having such foreign `impl`s also avoids forward compatibility issues where one crate adding
    100/// more `PartialEq` implementations can cause build failures in downstream crates.
    101///
    102/// ## Derivable
    103///
    104/// This trait can be used with `#[derive]`. When `derive`d on structs, two
    105/// instances are equal if all fields are equal, and not equal if any fields
    106/// are not equal. When `derive`d on enums, two instances are equal if they
    107/// are the same variant and all fields are equal.
    108///
    109/// ## How can I implement `PartialEq`?
    110///
    111/// An example implementation for a domain in which two books are considered
    112/// the same book if their ISBN matches, even if the formats differ:
    113///
    114/// ```
    115/// enum BookFormat {
    116///     Paperback,
    117///     Hardback,
    118///     Ebook,
    119/// }
    120///
    121/// struct Book {
    122///     isbn: i32,
    123///     format: BookFormat,
    124/// }
    125///
    126/// impl PartialEq for Book {
    127///     fn eq(&self, other: &Self) -> bool {
    128///         self.isbn == other.isbn
    129///     }
    130/// }
    131///
    132/// let b1 = Book { isbn: 3, format: BookFormat::Paperback };
    133/// let b2 = Book { isbn: 3, format: BookFormat::Ebook };
    134/// let b3 = Book { isbn: 10, format: BookFormat::Paperback };
    135///
    136/// assert!(b1 == b2);
    137/// assert!(b1 != b3);
    138/// ```
    139///
    140/// ## How can I compare two different types?
    141///
    142/// The type you can compare with is controlled by `PartialEq`'s type parameter.
    143/// For example, let's tweak our previous code a bit:
    144///
    145/// ```
    146/// // The derive implements <BookFormat> == <BookFormat> comparisons
    147/// #[derive(PartialEq)]
    148/// enum BookFormat {
    149///     Paperback,
    150///     Hardback,
    151///     Ebook,
    152/// }
    153///
    154/// struct Book {
    155///     isbn: i32,
    156///     format: BookFormat,
    157/// }
    158///
    159/// // Implement <Book> == <BookFormat> comparisons
    160/// impl PartialEq<BookFormat> for Book {
    161///     fn eq(&self, other: &BookFormat) -> bool {
    162///         self.format == *other
    163///     }
    164/// }
    165///
    166/// // Implement <BookFormat> == <Book> comparisons
    167/// impl PartialEq<Book> for BookFormat {
    168///     fn eq(&self, other: &Book) -> bool {
    169///         *self == other.format
    170///     }
    171/// }
    172///
    173/// let b1 = Book { isbn: 3, format: BookFormat::Paperback };
    174///
    175/// assert!(b1 == BookFormat::Paperback);
    176/// assert!(BookFormat::Ebook != b1);
    177/// ```
    178///
    179/// By changing `impl PartialEq for Book` to `impl PartialEq<BookFormat> for Book`,
    180/// we allow `BookFormat`s to be compared with `Book`s.
    181///
    182/// A comparison like the one above, which ignores some fields of the struct,
    183/// can be dangerous. It can easily lead to an unintended violation of the
    184/// requirements for a partial equivalence relation. For example, if we kept
    185/// the above implementation of `PartialEq<Book>` for `BookFormat` and added an
    186/// implementation of `PartialEq<Book>` for `Book` (either via a `#[derive]` or
    187/// via the manual implementation from the first example) then the result would
    188/// violate transitivity:
    189///
    190/// ```should_panic
    191/// #[derive(PartialEq)]
    192/// enum BookFormat {
    193///     Paperback,
    194///     Hardback,
    195///     Ebook,
    196/// }
    197///
    198/// #[derive(PartialEq)]
    199/// struct Book {
    200///     isbn: i32,
    201///     format: BookFormat,
    202/// }
    203///
    204/// impl PartialEq<BookFormat> for Book {
    205///     fn eq(&self, other: &BookFormat) -> bool {
    206///         self.format == *other
    207///     }
    208/// }
    209///
    210/// impl PartialEq<Book> for BookFormat {
    211///     fn eq(&self, other: &Book) -> bool {
    212///         *self == other.format
    213///     }
    214/// }
    215///
    216/// fn main() {
    217///     let b1 = Book { isbn: 1, format: BookFormat::Paperback };
    218///     let b2 = Book { isbn: 2, format: BookFormat::Paperback };
    219///
    220///     assert!(b1 == BookFormat::Paperback);
    221///     assert!(BookFormat::Paperback == b2);
    222///
    223///     // The following should hold by transitivity but doesn't.
    224///     assert!(b1 == b2); // <-- PANICS
    225/// }
    226/// ```
    227///
    228/// # Examples
    229///
    230/// ```
    231/// let x: u32 = 0;
    232/// let y: u32 = 1;
    233///
    234/// assert_eq!(x == y, false);
    235/// assert_eq!(x.eq(&y), false);
    236/// ```
    237///
    238/// [`eq`]: PartialEq::eq
    239/// [`ne`]: PartialEq::ne
    240#[lang = "eq"]
    241#[stable(feature = "rust1", since = "1.0.0")]
    242#[doc(alias = "==")]
    243#[doc(alias = "!=")]
    244#[rustc_on_unimplemented(
    245    message = "can't compare `{Self}` with `{Rhs}`",
    246    label = "no implementation for `{Self} == {Rhs}`",
    247    append_const_msg
    248)]
    249#[rustc_diagnostic_item = "PartialEq"]
    250#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    251pub const trait PartialEq<Rhs: PointeeSized = Self>: PointeeSized {
    252    /// Tests for `self` and `other` values to be equal, and is used by `==`.
    253    #[must_use]
    254    #[stable(feature = "rust1", since = "1.0.0")]
    255    #[rustc_diagnostic_item = "cmp_partialeq_eq"]
    256    fn eq(&self, other: &Rhs) -> bool;
    257
    258    /// Tests for `!=`. The default implementation is almost always sufficient,
    259    /// and should not be overridden without very good reason.
    260    #[inline]
    261    #[must_use]
    262    #[stable(feature = "rust1", since = "1.0.0")]
    263    #[rustc_diagnostic_item = "cmp_partialeq_ne"]
    264    fn ne(&self, other: &Rhs) -> bool {
    265        !self.eq(other)
    266    }
    267}
    268
    269/// Derive macro generating an impl of the trait [`PartialEq`].
    270/// The behavior of this macro is described in detail [here](PartialEq#derivable).
    271#[rustc_builtin_macro]
    272#[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
    273#[allow_internal_unstable(core_intrinsics, structural_match)]
    274pub macro PartialEq($item:item) {
    275    /* compiler built-in */
    276}
    277
    278/// Trait for comparisons corresponding to [equivalence relations](
    279/// https://en.wikipedia.org/wiki/Equivalence_relation).
    280///
    281/// The primary difference to [`PartialEq`] is the additional requirement for reflexivity. A type
    282/// that implements [`PartialEq`] guarantees that for all `a`, `b` and `c`:
    283///
    284/// - symmetric: `a == b` implies `b == a` and `a != b` implies `!(a == b)`
    285/// - transitive: `a == b` and `b == c` implies `a == c`
    286///
    287/// `Eq`, which builds on top of [`PartialEq`] also implies:
    288///
    289/// - reflexive: `a == a`
    290///
    291/// This property cannot be checked by the compiler, and therefore `Eq` is a trait without methods.
    292///
    293/// Violating this property is a logic error. The behavior resulting from a logic error is not
    294/// specified, but users of the trait must ensure that such logic errors do *not* result in
    295/// undefined behavior. This means that `unsafe` code **must not** rely on the correctness of these
    296/// methods.
    297///
    298/// Floating point types such as [`f32`] and [`f64`] implement only [`PartialEq`] but *not* `Eq`
    299/// because `NaN` != `NaN`.
    300///
    301/// ## Derivable
    302///
    303/// This trait can be used with `#[derive]`. When `derive`d, because `Eq` has no extra methods, it
    304/// is only informing the compiler that this is an equivalence relation rather than a partial
    305/// equivalence relation. Note that the `derive` strategy requires all fields are `Eq`, which isn't
    306/// always desired.
    307///
    308/// ## How can I implement `Eq`?
    309///
    310/// If you cannot use the `derive` strategy, specify that your type implements `Eq`, which has no
    311/// extra methods:
    312///
    313/// ```
    314/// enum BookFormat {
    315///     Paperback,
    316///     Hardback,
    317///     Ebook,
    318/// }
    319///
    320/// struct Book {
    321///     isbn: i32,
    322///     format: BookFormat,
    323/// }
    324///
    325/// impl PartialEq for Book {
    326///     fn eq(&self, other: &Self) -> bool {
    327///         self.isbn == other.isbn
    328///     }
    329/// }
    330///
    331/// impl Eq for Book {}
    332/// ```
    333#[doc(alias = "==")]
    334#[doc(alias = "!=")]
    335#[stable(feature = "rust1", since = "1.0.0")]
    336#[rustc_diagnostic_item = "Eq"]
    337#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    338pub const trait Eq: [const] PartialEq<Self> + PointeeSized {
    339    // this method is used solely by `impl Eq or #[derive(Eq)]` to assert that every component of a
    340    // type implements `Eq` itself. The current deriving infrastructure means doing this assertion
    341    // without using a method on this trait is nearly impossible.
    342    //
    343    // This should never be implemented by hand.
    344    #[doc(hidden)]
    345    #[coverage(off)]
    346    #[inline]
    347    #[stable(feature = "rust1", since = "1.0.0")]
    348    fn assert_receiver_is_total_eq(&self) {}
    349}
    350
    351/// Derive macro generating an impl of the trait [`Eq`].
    352#[rustc_builtin_macro]
    353#[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
    354#[allow_internal_unstable(core_intrinsics, derive_eq_internals, structural_match)]
    355#[allow_internal_unstable(coverage_attribute)]
    356pub macro Eq($item:item) {
    357    /* compiler built-in */
    358}
    359
    360// FIXME: this struct is used solely by #[derive] to
    361// assert that every component of a type implements Eq.
    362//
    363// This struct should never appear in user code.
    364#[doc(hidden)]
    365#[allow(missing_debug_implementations)]
    366#[unstable(
    367    feature = "derive_eq_internals",
    368    reason = "deriving hack, should not be public",
    369    issue = "none"
    370)]
    371pub struct AssertParamIsEq<T: Eq + PointeeSized> {
    372    _field: crate::marker::PhantomData<T>,
    373}
    374
    375/// An `Ordering` is the result of a comparison between two values.
    376///
    377/// # Examples
    378///
    379/// ```
    380/// use std::cmp::Ordering;
    381///
    382/// assert_eq!(1.cmp(&2), Ordering::Less);
    383///
    384/// assert_eq!(1.cmp(&1), Ordering::Equal);
    385///
    386/// assert_eq!(2.cmp(&1), Ordering::Greater);
    387/// ```
    388#[derive(Copy, Debug, Hash)]
    389#[derive_const(Clone, Eq, PartialOrd, Ord, PartialEq)]
    390#[stable(feature = "rust1", since = "1.0.0")]
    391// This is a lang item only so that `BinOp::Cmp` in MIR can return it.
    392// It has no special behavior, but does require that the three variants
    393// `Less`/`Equal`/`Greater` remain `-1_i8`/`0_i8`/`+1_i8` respectively.
    394#[lang = "Ordering"]
    395#[repr(i8)]
    396pub enum Ordering {
    397    /// An ordering where a compared value is less than another.
    398    #[stable(feature = "rust1", since = "1.0.0")]
    399    Less = -1,
    400    /// An ordering where a compared value is equal to another.
    401    #[stable(feature = "rust1", since = "1.0.0")]
    402    Equal = 0,
    403    /// An ordering where a compared value is greater than another.
    404    #[stable(feature = "rust1", since = "1.0.0")]
    405    Greater = 1,
    406}
    407
    408impl Ordering {
    409    #[inline]
    410    const fn as_raw(self) -> i8 {
    411        // FIXME(const-hack): just use `PartialOrd` against `Equal` once that's const
    412        crate::intrinsics::discriminant_value(&self)
    413    }
    414
    415    /// Returns `true` if the ordering is the `Equal` variant.
    416    ///
    417    /// # Examples
    418    ///
    419    /// ```
    420    /// use std::cmp::Ordering;
    421    ///
    422    /// assert_eq!(Ordering::Less.is_eq(), false);
    423    /// assert_eq!(Ordering::Equal.is_eq(), true);
    424    /// assert_eq!(Ordering::Greater.is_eq(), false);
    425    /// ```
    426    #[inline]
    427    #[must_use]
    428    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
    429    #[stable(feature = "ordering_helpers", since = "1.53.0")]
    430    pub const fn is_eq(self) -> bool {
    431        // All the `is_*` methods are implemented as comparisons against zero
    432        // to follow how clang's libcxx implements their equivalents in
    433        // <https://github.com/llvm/llvm-project/blob/60486292b79885b7800b082754153202bef5b1f0/libcxx/include/__compare/is_eq.h#L23-L28>
    434
    435        self.as_raw() == 0
    436    }
    437
    438    /// Returns `true` if the ordering is not the `Equal` variant.
    439    ///
    440    /// # Examples
    441    ///
    442    /// ```
    443    /// use std::cmp::Ordering;
    444    ///
    445    /// assert_eq!(Ordering::Less.is_ne(), true);
    446    /// assert_eq!(Ordering::Equal.is_ne(), false);
    447    /// assert_eq!(Ordering::Greater.is_ne(), true);
    448    /// ```
    449    #[inline]
    450    #[must_use]
    451    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
    452    #[stable(feature = "ordering_helpers", since = "1.53.0")]
    453    pub const fn is_ne(self) -> bool {
    454        self.as_raw() != 0
    455    }
    456
    457    /// Returns `true` if the ordering is the `Less` variant.
    458    ///
    459    /// # Examples
    460    ///
    461    /// ```
    462    /// use std::cmp::Ordering;
    463    ///
    464    /// assert_eq!(Ordering::Less.is_lt(), true);
    465    /// assert_eq!(Ordering::Equal.is_lt(), false);
    466    /// assert_eq!(Ordering::Greater.is_lt(), false);
    467    /// ```
    468    #[inline]
    469    #[must_use]
    470    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
    471    #[stable(feature = "ordering_helpers", since = "1.53.0")]
    472    pub const fn is_lt(self) -> bool {
    473        self.as_raw() < 0
    474    }
    475
    476    /// Returns `true` if the ordering is the `Greater` variant.
    477    ///
    478    /// # Examples
    479    ///
    480    /// ```
    481    /// use std::cmp::Ordering;
    482    ///
    483    /// assert_eq!(Ordering::Less.is_gt(), false);
    484    /// assert_eq!(Ordering::Equal.is_gt(), false);
    485    /// assert_eq!(Ordering::Greater.is_gt(), true);
    486    /// ```
    487    #[inline]
    488    #[must_use]
    489    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
    490    #[stable(feature = "ordering_helpers", since = "1.53.0")]
    491    pub const fn is_gt(self) -> bool {
    492        self.as_raw() > 0
    493    }
    494
    495    /// Returns `true` if the ordering is either the `Less` or `Equal` variant.
    496    ///
    497    /// # Examples
    498    ///
    499    /// ```
    500    /// use std::cmp::Ordering;
    501    ///
    502    /// assert_eq!(Ordering::Less.is_le(), true);
    503    /// assert_eq!(Ordering::Equal.is_le(), true);
    504    /// assert_eq!(Ordering::Greater.is_le(), false);
    505    /// ```
    506    #[inline]
    507    #[must_use]
    508    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
    509    #[stable(feature = "ordering_helpers", since = "1.53.0")]
    510    pub const fn is_le(self) -> bool {
    511        self.as_raw() <= 0
    512    }
    513
    514    /// Returns `true` if the ordering is either the `Greater` or `Equal` variant.
    515    ///
    516    /// # Examples
    517    ///
    518    /// ```
    519    /// use std::cmp::Ordering;
    520    ///
    521    /// assert_eq!(Ordering::Less.is_ge(), false);
    522    /// assert_eq!(Ordering::Equal.is_ge(), true);
    523    /// assert_eq!(Ordering::Greater.is_ge(), true);
    524    /// ```
    525    #[inline]
    526    #[must_use]
    527    #[rustc_const_stable(feature = "ordering_helpers", since = "1.53.0")]
    528    #[stable(feature = "ordering_helpers", since = "1.53.0")]
    529    pub const fn is_ge(self) -> bool {
    530        self.as_raw() >= 0
    531    }
    532
    533    /// Reverses the `Ordering`.
    534    ///
    535    /// * `Less` becomes `Greater`.
    536    /// * `Greater` becomes `Less`.
    537    /// * `Equal` becomes `Equal`.
    538    ///
    539    /// # Examples
    540    ///
    541    /// Basic behavior:
    542    ///
    543    /// ```
    544    /// use std::cmp::Ordering;
    545    ///
    546    /// assert_eq!(Ordering::Less.reverse(), Ordering::Greater);
    547    /// assert_eq!(Ordering::Equal.reverse(), Ordering::Equal);
    548    /// assert_eq!(Ordering::Greater.reverse(), Ordering::Less);
    549    /// ```
    550    ///
    551    /// This method can be used to reverse a comparison:
    552    ///
    553    /// ```
    554    /// let data: &mut [_] = &mut [2, 10, 5, 8];
    555    ///
    556    /// // sort the array from largest to smallest.
    557    /// data.sort_by(|a, b| a.cmp(b).reverse());
    558    ///
    559    /// let b: &mut [_] = &mut [10, 8, 5, 2];
    560    /// assert!(data == b);
    561    /// ```
    562    #[inline]
    563    #[must_use]
    564    #[rustc_const_stable(feature = "const_ordering", since = "1.48.0")]
    565    #[stable(feature = "rust1", since = "1.0.0")]
    566    pub const fn reverse(self) -> Ordering {
    567        match self {
    568            Less => Greater,
    569            Equal => Equal,
    570            Greater => Less,
    571        }
    572    }
    573
    574    /// Chains two orderings.
    575    ///
    576    /// Returns `self` when it's not `Equal`. Otherwise returns `other`.
    577    ///
    578    /// # Examples
    579    ///
    580    /// ```
    581    /// use std::cmp::Ordering;
    582    ///
    583    /// let result = Ordering::Equal.then(Ordering::Less);
    584    /// assert_eq!(result, Ordering::Less);
    585    ///
    586    /// let result = Ordering::Less.then(Ordering::Equal);
    587    /// assert_eq!(result, Ordering::Less);
    588    ///
    589    /// let result = Ordering::Less.then(Ordering::Greater);
    590    /// assert_eq!(result, Ordering::Less);
    591    ///
    592    /// let result = Ordering::Equal.then(Ordering::Equal);
    593    /// assert_eq!(result, Ordering::Equal);
    594    ///
    595    /// let x: (i64, i64, i64) = (1, 2, 7);
    596    /// let y: (i64, i64, i64) = (1, 5, 3);
    597    /// let result = x.0.cmp(&y.0).then(x.1.cmp(&y.1)).then(x.2.cmp(&y.2));
    598    ///
    599    /// assert_eq!(result, Ordering::Less);
    600    /// ```
    601    #[inline]
    602    #[must_use]
    603    #[rustc_const_stable(feature = "const_ordering", since = "1.48.0")]
    604    #[stable(feature = "ordering_chaining", since = "1.17.0")]
    605    pub const fn then(self, other: Ordering) -> Ordering {
    606        match self {
    607            Equal => other,
    608            _ => self,
    609        }
    610    }
    611
    612    /// Chains the ordering with the given function.
    613    ///
    614    /// Returns `self` when it's not `Equal`. Otherwise calls `f` and returns
    615    /// the result.
    616    ///
    617    /// # Examples
    618    ///
    619    /// ```
    620    /// use std::cmp::Ordering;
    621    ///
    622    /// let result = Ordering::Equal.then_with(|| Ordering::Less);
    623    /// assert_eq!(result, Ordering::Less);
    624    ///
    625    /// let result = Ordering::Less.then_with(|| Ordering::Equal);
    626    /// assert_eq!(result, Ordering::Less);
    627    ///
    628    /// let result = Ordering::Less.then_with(|| Ordering::Greater);
    629    /// assert_eq!(result, Ordering::Less);
    630    ///
    631    /// let result = Ordering::Equal.then_with(|| Ordering::Equal);
    632    /// assert_eq!(result, Ordering::Equal);
    633    ///
    634    /// let x: (i64, i64, i64) = (1, 2, 7);
    635    /// let y: (i64, i64, i64) = (1, 5, 3);
    636    /// let result = x.0.cmp(&y.0).then_with(|| x.1.cmp(&y.1)).then_with(|| x.2.cmp(&y.2));
    637    ///
    638    /// assert_eq!(result, Ordering::Less);
    639    /// ```
    640    #[inline]
    641    #[must_use]
    642    #[stable(feature = "ordering_chaining", since = "1.17.0")]
    643    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    644    pub const fn then_with<F>(self, f: F) -> Ordering
    645    where
    646        F: [const] FnOnce() -> Ordering + [const] Destruct,
    647    {
    648        match self {
    649            Equal => f(),
    650            _ => self,
    651        }
    652    }
    653}
    654
    655/// A helper struct for reverse ordering.
    656///
    657/// This struct is a helper to be used with functions like [`Vec::sort_by_key`] and
    658/// can be used to reverse order a part of a key.
    659///
    660/// [`Vec::sort_by_key`]: ../../std/vec/struct.Vec.html#method.sort_by_key
    661///
    662/// # Examples
    663///
    664/// ```
    665/// use std::cmp::Reverse;
    666///
    667/// let mut v = vec![1, 2, 3, 4, 5, 6];
    668/// v.sort_by_key(|&num| (num > 3, Reverse(num)));
    669/// assert_eq!(v, vec![3, 2, 1, 6, 5, 4]);
    670/// ```
    671#[derive(Copy, Debug, Hash)]
    672#[derive_const(PartialEq, Eq, Default)]
    673#[stable(feature = "reverse_cmp_key", since = "1.19.0")]
    674#[repr(transparent)]
    675pub struct Reverse<T>(#[stable(feature = "reverse_cmp_key", since = "1.19.0")] pub T);
    676
    677#[stable(feature = "reverse_cmp_key", since = "1.19.0")]
    678#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    679impl<T: [const] PartialOrd> const PartialOrd for Reverse<T> {
    680    #[inline]
    681    fn partial_cmp(&self, other: &Reverse<T>) -> Option<Ordering> {
    682        other.0.partial_cmp(&self.0)
    683    }
    684
    685    #[inline]
    686    fn lt(&self, other: &Self) -> bool {
    687        other.0 < self.0
    688    }
    689    #[inline]
    690    fn le(&self, other: &Self) -> bool {
    691        other.0 <= self.0
    692    }
    693    #[inline]
    694    fn gt(&self, other: &Self) -> bool {
    695        other.0 > self.0
    696    }
    697    #[inline]
    698    fn ge(&self, other: &Self) -> bool {
    699        other.0 >= self.0
    700    }
    701}
    702
    703#[stable(feature = "reverse_cmp_key", since = "1.19.0")]
    704#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    705impl<T: [const] Ord> const Ord for Reverse<T> {
    706    #[inline]
    707    fn cmp(&self, other: &Reverse<T>) -> Ordering {
    708        other.0.cmp(&self.0)
    709    }
    710}
    711
    712#[stable(feature = "reverse_cmp_key", since = "1.19.0")]
    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"]
    972#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    973pub const trait Ord: [const] Eq + [const] PartialOrd<Self> + PointeeSized {
    974    /// This method returns an [`Ordering`] between `self` and `other`.
    975    ///
    976    /// By convention, `self.cmp(&other)` returns the ordering matching the expression
    977    /// `self <operator> other` if true.
    978    ///
    979    /// # Examples
    980    ///
    981    /// ```
    982    /// use std::cmp::Ordering;
    983    ///
    984    /// assert_eq!(5.cmp(&10), Ordering::Less);
    985    /// assert_eq!(10.cmp(&5), Ordering::Greater);
    986    /// assert_eq!(5.cmp(&5), Ordering::Equal);
    987    /// ```
    988    #[must_use]
    989    #[stable(feature = "rust1", since = "1.0.0")]
    990    #[rustc_diagnostic_item = "ord_cmp_method"]
    991    fn cmp(&self, other: &Self) -> Ordering;
    992
    993    /// Compares and returns the maximum of two values.
    994    ///
    995    /// Returns the second argument if the comparison determines them to be equal.
    996    ///
    997    /// # Examples
    998    ///
    999    /// ```
    1000    /// assert_eq!(1.max(2), 2);
    1001    /// assert_eq!(2.max(2), 2);
    1002    /// ```
    1003    /// ```
    1004    /// use std::cmp::Ordering;
    1005    ///
    1006    /// #[derive(Eq)]
    1007    /// struct Equal(&'static str);
    1008    ///
    1009    /// impl PartialEq for Equal {
    1010    ///     fn eq(&self, other: &Self) -> bool { true }
    1011    /// }
    1012    /// impl PartialOrd for Equal {
    1013    ///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(Ordering::Equal) }
    1014    /// }
    1015    /// impl Ord for Equal {
    1016    ///     fn cmp(&self, other: &Self) -> Ordering { Ordering::Equal }
    1017    /// }
    1018    ///
    1019    /// assert_eq!(Equal("self").max(Equal("other")).0, "other");
    1020    /// ```
    1021    #[stable(feature = "ord_max_min", since = "1.21.0")]
    1022    #[inline]
    1023    #[must_use]
    1024    #[rustc_diagnostic_item = "cmp_ord_max"]
    1025    fn max(self, other: Self) -> Self
    1026    where
    1027        Self: Sized + [const] Destruct,
    1028    {
    1029        if other < self { self } else { other }
    1030    }
    1031
    1032    /// Compares and returns the minimum of two values.
    1033    ///
    1034    /// Returns the first argument if the comparison determines them to be equal.
    1035    ///
    1036    /// # Examples
    1037    ///
    1038    /// ```
    1039    /// assert_eq!(1.min(2), 1);
    1040    /// assert_eq!(2.min(2), 2);
    1041    /// ```
    1042    /// ```
    1043    /// use std::cmp::Ordering;
    1044    ///
    1045    /// #[derive(Eq)]
    1046    /// struct Equal(&'static str);
    1047    ///
    1048    /// impl PartialEq for Equal {
    1049    ///     fn eq(&self, other: &Self) -> bool { true }
    1050    /// }
    1051    /// impl PartialOrd for Equal {
    1052    ///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(Ordering::Equal) }
    1053    /// }
    1054    /// impl Ord for Equal {
    1055    ///     fn cmp(&self, other: &Self) -> Ordering { Ordering::Equal }
    1056    /// }
    1057    ///
    1058    /// assert_eq!(Equal("self").min(Equal("other")).0, "self");
    1059    /// ```
    1060    #[stable(feature = "ord_max_min", since = "1.21.0")]
    1061    #[inline]
    1062    #[must_use]
    1063    #[rustc_diagnostic_item = "cmp_ord_min"]
    1064    fn min(self, other: Self) -> Self
    1065    where
    1066        Self: Sized + [const] Destruct,
    1067    {
    1068        if other < self { other } else { self }
    1069    }
    1070
    1071    /// Restrict a value to a certain interval.
    1072    ///
    1073    /// Returns `max` if `self` is greater than `max`, and `min` if `self` is
    1074    /// less than `min`. Otherwise this returns `self`.
    1075    ///
    1076    /// # Panics
    1077    ///
    1078    /// Panics if `min > max`.
    1079    ///
    1080    /// # Examples
    1081    ///
    1082    /// ```
    1083    /// assert_eq!((-3).clamp(-2, 1), -2);
    1084    /// assert_eq!(0.clamp(-2, 1), 0);
    1085    /// assert_eq!(2.clamp(-2, 1), 1);
    1086    /// ```
    1087    #[must_use]
    1088    #[inline]
    1089    #[stable(feature = "clamp", since = "1.50.0")]
    1090    fn clamp(self, min: Self, max: Self) -> Self
    1091    where
    1092        Self: Sized + [const] Destruct,
    1093    {
    1094        assert!(min <= max);
    1095        if self < min {
    1096            min
    1097        } else if self > max {
    1098            max
    1099        } else {
    1100            self
    1101        }
    1102    }
    1103}
    1104
    1105/// Derive macro generating an impl of the trait [`Ord`].
    1106/// The behavior of this macro is described in detail [here](Ord#derivable).
    1107#[rustc_builtin_macro]
    1108#[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
    1109#[allow_internal_unstable(core_intrinsics)]
    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::NAN;
    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
    1357#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1358pub const trait PartialOrd<Rhs: PointeeSized = Self>:
    1359    [const] PartialEq<Rhs> + PointeeSized
    1360{
    1361    /// This method returns an ordering between `self` and `other` values if one exists.
    1362    ///
    1363    /// # Examples
    1364    ///
    1365    /// ```
    1366    /// use std::cmp::Ordering;
    1367    ///
    1368    /// let result = 1.0.partial_cmp(&2.0);
    1369    /// assert_eq!(result, Some(Ordering::Less));
    1370    ///
    1371    /// let result = 1.0.partial_cmp(&1.0);
    1372    /// assert_eq!(result, Some(Ordering::Equal));
    1373    ///
    1374    /// let result = 2.0.partial_cmp(&1.0);
    1375    /// assert_eq!(result, Some(Ordering::Greater));
    1376    /// ```
    1377    ///
    1378    /// When comparison is impossible:
    1379    ///
    1380    /// ```
    1381    /// let result = f64::NAN.partial_cmp(&1.0);
    1382    /// assert_eq!(result, None);
    1383    /// ```
    1384    #[must_use]
    1385    #[stable(feature = "rust1", since = "1.0.0")]
    1386    #[rustc_diagnostic_item = "cmp_partialord_cmp"]
    1387    fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>;
    1388
    1389    /// Tests less than (for `self` and `other`) and is used by the `<` operator.
    1390    ///
    1391    /// # Examples
    1392    ///
    1393    /// ```
    1394    /// assert_eq!(1.0 < 1.0, false);
    1395    /// assert_eq!(1.0 < 2.0, true);
    1396    /// assert_eq!(2.0 < 1.0, false);
    1397    /// ```
    1398    #[inline]
    1399    #[must_use]
    1400    #[stable(feature = "rust1", since = "1.0.0")]
    1401    #[rustc_diagnostic_item = "cmp_partialord_lt"]
    1402    fn lt(&self, other: &Rhs) -> bool {
    1403        self.partial_cmp(other).is_some_and(Ordering::is_lt)
    1404    }
    1405
    1406    /// Tests less than or equal to (for `self` and `other`) and is used by the
    1407    /// `<=` operator.
    1408    ///
    1409    /// # Examples
    1410    ///
    1411    /// ```
    1412    /// assert_eq!(1.0 <= 1.0, true);
    1413    /// assert_eq!(1.0 <= 2.0, true);
    1414    /// assert_eq!(2.0 <= 1.0, false);
    1415    /// ```
    1416    #[inline]
    1417    #[must_use]
    1418    #[stable(feature = "rust1", since = "1.0.0")]
    1419    #[rustc_diagnostic_item = "cmp_partialord_le"]
    1420    fn le(&self, other: &Rhs) -> bool {
    1421        self.partial_cmp(other).is_some_and(Ordering::is_le)
    1422    }
    1423
    1424    /// Tests greater than (for `self` and `other`) and is used by the `>`
    1425    /// operator.
    1426    ///
    1427    /// # Examples
    1428    ///
    1429    /// ```
    1430    /// assert_eq!(1.0 > 1.0, false);
    1431    /// assert_eq!(1.0 > 2.0, false);
    1432    /// assert_eq!(2.0 > 1.0, true);
    1433    /// ```
    1434    #[inline]
    1435    #[must_use]
    1436    #[stable(feature = "rust1", since = "1.0.0")]
    1437    #[rustc_diagnostic_item = "cmp_partialord_gt"]
    1438    fn gt(&self, other: &Rhs) -> bool {
    1439        self.partial_cmp(other).is_some_and(Ordering::is_gt)
    1440    }
    1441
    1442    /// Tests greater than or equal to (for `self` and `other`) and is used by
    1443    /// the `>=` operator.
    1444    ///
    1445    /// # Examples
    1446    ///
    1447    /// ```
    1448    /// assert_eq!(1.0 >= 1.0, true);
    1449    /// assert_eq!(1.0 >= 2.0, false);
    1450    /// assert_eq!(2.0 >= 1.0, true);
    1451    /// ```
    1452    #[inline]
    1453    #[must_use]
    1454    #[stable(feature = "rust1", since = "1.0.0")]
    1455    #[rustc_diagnostic_item = "cmp_partialord_ge"]
    1456    fn ge(&self, other: &Rhs) -> bool {
    1457        self.partial_cmp(other).is_some_and(Ordering::is_ge)
    1458    }
    1459
    1460    /// If `self == other`, returns `ControlFlow::Continue(())`.
    1461    /// Otherwise, returns `ControlFlow::Break(self < other)`.
    1462    ///
    1463    /// This is useful for chaining together calls when implementing a lexical
    1464    /// `PartialOrd::lt`, as it allows types (like primitives) which can cheaply
    1465    /// check `==` and `<` separately to do rather than needing to calculate
    1466    /// (then optimize out) the three-way `Ordering` result.
    1467    #[inline]
    1468    // Added to improve the behaviour of tuples; not necessarily stabilization-track.
    1469    #[unstable(feature = "partial_ord_chaining_methods", issue = "none")]
    1470    #[doc(hidden)]
    1471    fn __chaining_lt(&self, other: &Rhs) -> ControlFlow<bool> {
    1472        default_chaining_impl(self, other, Ordering::is_lt)
    1473    }
    1474
    1475    /// Same as `__chaining_lt`, but for `<=` instead of `<`.
    1476    #[inline]
    1477    #[unstable(feature = "partial_ord_chaining_methods", issue = "none")]
    1478    #[doc(hidden)]
    1479    fn __chaining_le(&self, other: &Rhs) -> ControlFlow<bool> {
    1480        default_chaining_impl(self, other, Ordering::is_le)
    1481    }
    1482
    1483    /// Same as `__chaining_lt`, but for `>` instead of `<`.
    1484    #[inline]
    1485    #[unstable(feature = "partial_ord_chaining_methods", issue = "none")]
    1486    #[doc(hidden)]
    1487    fn __chaining_gt(&self, other: &Rhs) -> ControlFlow<bool> {
    1488        default_chaining_impl(self, other, Ordering::is_gt)
    1489    }
    1490
    1491    /// Same as `__chaining_lt`, but for `>=` instead of `<`.
    1492    #[inline]
    1493    #[unstable(feature = "partial_ord_chaining_methods", issue = "none")]
    1494    #[doc(hidden)]
    1495    fn __chaining_ge(&self, other: &Rhs) -> ControlFlow<bool> {
    1496        default_chaining_impl(self, other, Ordering::is_ge)
    1497    }
    1498}
    1499
    1500#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1501const fn default_chaining_impl<T, U>(
    1502    lhs: &T,
    1503    rhs: &U,
    1504    p: impl [const] FnOnce(Ordering) -> bool + [const] Destruct,
    1505) -> ControlFlow<bool>
    1506where
    1507    T: [const] PartialOrd<U> + PointeeSized,
    1508    U: PointeeSized,
    1509{
    1510    // It's important that this only call `partial_cmp` once, not call `eq` then
    1511    // one of the relational operators.  We don't want to `bcmp`-then-`memcp` a
    1512    // `String`, for example, or similarly for other data structures (#108157).
    1513    match <T as PartialOrd<U>>::partial_cmp(lhs, rhs) {
    1514        Some(Equal) => ControlFlow::Continue(()),
    1515        Some(c) => ControlFlow::Break(p(c)),
    1516        None => ControlFlow::Break(false),
    1517    }
    1518}
    1519
    1520/// Derive macro generating an impl of the trait [`PartialOrd`].
    1521/// The behavior of this macro is described in detail [here](PartialOrd#derivable).
    1522#[rustc_builtin_macro]
    1523#[stable(feature = "builtin_macro_prelude", since = "1.38.0")]
    1524#[allow_internal_unstable(core_intrinsics)]
    1525pub macro PartialOrd($item:item) {
    1526    /* compiler built-in */
    1527}
    1528
    1529/// Compares and returns the minimum of two values.
    1530///
    1531/// Returns the first argument if the comparison determines them to be equal.
    1532///
    1533/// Internally uses an alias to [`Ord::min`].
    1534///
    1535/// # Examples
    1536///
    1537/// ```
    1538/// use std::cmp;
    1539///
    1540/// assert_eq!(cmp::min(1, 2), 1);
    1541/// assert_eq!(cmp::min(2, 2), 2);
    1542/// ```
    1543/// ```
    1544/// use std::cmp::{self, Ordering};
    1545///
    1546/// #[derive(Eq)]
    1547/// struct Equal(&'static str);
    1548///
    1549/// impl PartialEq for Equal {
    1550///     fn eq(&self, other: &Self) -> bool { true }
    1551/// }
    1552/// impl PartialOrd for Equal {
    1553///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(Ordering::Equal) }
    1554/// }
    1555/// impl Ord for Equal {
    1556///     fn cmp(&self, other: &Self) -> Ordering { Ordering::Equal }
    1557/// }
    1558///
    1559/// assert_eq!(cmp::min(Equal("v1"), Equal("v2")).0, "v1");
    1560/// ```
    1561#[inline]
    1562#[must_use]
    1563#[stable(feature = "rust1", since = "1.0.0")]
    1564#[rustc_diagnostic_item = "cmp_min"]
    1565#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1566pub const fn min<T: [const] Ord + [const] Destruct>(v1: T, v2: T) -> T {
    1567    v1.min(v2)
    1568}
    1569
    1570/// Returns the minimum of two values with respect to the specified comparison function.
    1571///
    1572/// Returns the first argument if the comparison determines them to be equal.
    1573///
    1574/// The parameter order is preserved when calling the `compare` function, i.e. `v1` is
    1575/// always passed as the first argument and `v2` as the second.
    1576///
    1577/// # Examples
    1578///
    1579/// ```
    1580/// use std::cmp;
    1581///
    1582/// let abs_cmp = |x: &i32, y: &i32| x.abs().cmp(&y.abs());
    1583///
    1584/// let result = cmp::min_by(2, -1, abs_cmp);
    1585/// assert_eq!(result, -1);
    1586///
    1587/// let result = cmp::min_by(2, -3, abs_cmp);
    1588/// assert_eq!(result, 2);
    1589///
    1590/// let result = cmp::min_by(1, -1, abs_cmp);
    1591/// assert_eq!(result, 1);
    1592/// ```
    1593#[inline]
    1594#[must_use]
    1595#[stable(feature = "cmp_min_max_by", since = "1.53.0")]
    1596#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1597pub const fn min_by<T: [const] Destruct, F: [const] FnOnce(&T, &T) -> Ordering>(
    1598    v1: T,
    1599    v2: T,
    1600    compare: F,
    1601) -> T {
    1602    if compare(&v1, &v2).is_le() { v1 } else { v2 }
    1603}
    1604
    1605/// Returns the element that gives the minimum value from the specified function.
    1606///
    1607/// Returns the first argument if the comparison determines them to be equal.
    1608///
    1609/// # Examples
    1610///
    1611/// ```
    1612/// use std::cmp;
    1613///
    1614/// let result = cmp::min_by_key(2, -1, |x: &i32| x.abs());
    1615/// assert_eq!(result, -1);
    1616///
    1617/// let result = cmp::min_by_key(2, -3, |x: &i32| x.abs());
    1618/// assert_eq!(result, 2);
    1619///
    1620/// let result = cmp::min_by_key(1, -1, |x: &i32| x.abs());
    1621/// assert_eq!(result, 1);
    1622/// ```
    1623#[inline]
    1624#[must_use]
    1625#[stable(feature = "cmp_min_max_by", since = "1.53.0")]
    1626#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1627pub const fn min_by_key<T, F, K>(v1: T, v2: T, mut f: F) -> T
    1628where
    1629    T: [const] Destruct,
    1630    F: [const] FnMut(&T) -> K + [const] Destruct,
    1631    K: [const] Ord + [const] Destruct,
    1632{
    1633    if f(&v2) < f(&v1) { v2 } else { v1 }
    1634}
    1635
    1636/// Compares and returns the maximum of two values.
    1637///
    1638/// Returns the second argument if the comparison determines them to be equal.
    1639///
    1640/// Internally uses an alias to [`Ord::max`].
    1641///
    1642/// # Examples
    1643///
    1644/// ```
    1645/// use std::cmp;
    1646///
    1647/// assert_eq!(cmp::max(1, 2), 2);
    1648/// assert_eq!(cmp::max(2, 2), 2);
    1649/// ```
    1650/// ```
    1651/// use std::cmp::{self, Ordering};
    1652///
    1653/// #[derive(Eq)]
    1654/// struct Equal(&'static str);
    1655///
    1656/// impl PartialEq for Equal {
    1657///     fn eq(&self, other: &Self) -> bool { true }
    1658/// }
    1659/// impl PartialOrd for Equal {
    1660///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(Ordering::Equal) }
    1661/// }
    1662/// impl Ord for Equal {
    1663///     fn cmp(&self, other: &Self) -> Ordering { Ordering::Equal }
    1664/// }
    1665///
    1666/// assert_eq!(cmp::max(Equal("v1"), Equal("v2")).0, "v2");
    1667/// ```
    1668#[inline]
    1669#[must_use]
    1670#[stable(feature = "rust1", since = "1.0.0")]
    1671#[rustc_diagnostic_item = "cmp_max"]
    1672#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1673pub const fn max<T: [const] Ord + [const] Destruct>(v1: T, v2: T) -> T {
    1674    v1.max(v2)
    1675}
    1676
    1677/// Returns the maximum of two values with respect to the specified comparison function.
    1678///
    1679/// Returns the second argument if the comparison determines them to be equal.
    1680///
    1681/// The parameter order is preserved when calling the `compare` function, i.e. `v1` is
    1682/// always passed as the first argument and `v2` as the second.
    1683///
    1684/// # Examples
    1685///
    1686/// ```
    1687/// use std::cmp;
    1688///
    1689/// let abs_cmp = |x: &i32, y: &i32| x.abs().cmp(&y.abs());
    1690///
    1691/// let result = cmp::max_by(3, -2, abs_cmp) ;
    1692/// assert_eq!(result, 3);
    1693///
    1694/// let result = cmp::max_by(1, -2, abs_cmp);
    1695/// assert_eq!(result, -2);
    1696///
    1697/// let result = cmp::max_by(1, -1, abs_cmp);
    1698/// assert_eq!(result, -1);
    1699/// ```
    1700#[inline]
    1701#[must_use]
    1702#[stable(feature = "cmp_min_max_by", since = "1.53.0")]
    1703#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1704pub const fn max_by<T: [const] Destruct, F: [const] FnOnce(&T, &T) -> Ordering>(
    1705    v1: T,
    1706    v2: T,
    1707    compare: F,
    1708) -> T {
    1709    if compare(&v1, &v2).is_gt() { v1 } else { v2 }
    1710}
    1711
    1712/// Returns the element that gives the maximum value from the specified function.
    1713///
    1714/// Returns the second argument if the comparison determines them to be equal.
    1715///
    1716/// # Examples
    1717///
    1718/// ```
    1719/// use std::cmp;
    1720///
    1721/// let result = cmp::max_by_key(3, -2, |x: &i32| x.abs());
    1722/// assert_eq!(result, 3);
    1723///
    1724/// let result = cmp::max_by_key(1, -2, |x: &i32| x.abs());
    1725/// assert_eq!(result, -2);
    1726///
    1727/// let result = cmp::max_by_key(1, -1, |x: &i32| x.abs());
    1728/// assert_eq!(result, -1);
    1729/// ```
    1730#[inline]
    1731#[must_use]
    1732#[stable(feature = "cmp_min_max_by", since = "1.53.0")]
    1733#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1734pub const fn max_by_key<T, F, K>(v1: T, v2: T, mut f: F) -> T
    1735where
    1736    T: [const] Destruct,
    1737    F: [const] FnMut(&T) -> K + [const] Destruct,
    1738    K: [const] Ord + [const] Destruct,
    1739{
    1740    if f(&v2) < f(&v1) { v1 } else { v2 }
    1741}
    1742
    1743/// Compares and sorts two values, returning minimum and maximum.
    1744///
    1745/// Returns `[v1, v2]` if the comparison determines them to be equal.
    1746///
    1747/// # Examples
    1748///
    1749/// ```
    1750/// #![feature(cmp_minmax)]
    1751/// use std::cmp;
    1752///
    1753/// assert_eq!(cmp::minmax(1, 2), [1, 2]);
    1754/// assert_eq!(cmp::minmax(2, 1), [1, 2]);
    1755///
    1756/// // You can destructure the result using array patterns
    1757/// let [min, max] = cmp::minmax(42, 17);
    1758/// assert_eq!(min, 17);
    1759/// assert_eq!(max, 42);
    1760/// ```
    1761/// ```
    1762/// #![feature(cmp_minmax)]
    1763/// use std::cmp::{self, Ordering};
    1764///
    1765/// #[derive(Eq)]
    1766/// struct Equal(&'static str);
    1767///
    1768/// impl PartialEq for Equal {
    1769///     fn eq(&self, other: &Self) -> bool { true }
    1770/// }
    1771/// impl PartialOrd for Equal {
    1772///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> { Some(Ordering::Equal) }
    1773/// }
    1774/// impl Ord for Equal {
    1775///     fn cmp(&self, other: &Self) -> Ordering { Ordering::Equal }
    1776/// }
    1777///
    1778/// assert_eq!(cmp::minmax(Equal("v1"), Equal("v2")).map(|v| v.0), ["v1", "v2"]);
    1779/// ```
    1780#[inline]
    1781#[must_use]
    1782#[unstable(feature = "cmp_minmax", issue = "115939")]
    1783#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1784pub const fn minmax<T>(v1: T, v2: T) -> [T; 2]
    1785where
    1786    T: [const] Ord,
    1787{
    1788    if v2 < v1 { [v2, v1] } else { [v1, v2] }
    1789}
    1790
    1791/// Returns minimum and maximum values with respect to the specified comparison function.
    1792///
    1793/// Returns `[v1, v2]` if the comparison determines them to be equal.
    1794///
    1795/// The parameter order is preserved when calling the `compare` function, i.e. `v1` is
    1796/// always passed as the first argument and `v2` as the second.
    1797///
    1798/// # Examples
    1799///
    1800/// ```
    1801/// #![feature(cmp_minmax)]
    1802/// use std::cmp;
    1803///
    1804/// let abs_cmp = |x: &i32, y: &i32| x.abs().cmp(&y.abs());
    1805///
    1806/// assert_eq!(cmp::minmax_by(-2, 1, abs_cmp), [1, -2]);
    1807/// assert_eq!(cmp::minmax_by(-1, 2, abs_cmp), [-1, 2]);
    1808/// assert_eq!(cmp::minmax_by(-2, 2, abs_cmp), [-2, 2]);
    1809///
    1810/// // You can destructure the result using array patterns
    1811/// let [min, max] = cmp::minmax_by(-42, 17, abs_cmp);
    1812/// assert_eq!(min, 17);
    1813/// assert_eq!(max, -42);
    1814/// ```
    1815#[inline]
    1816#[must_use]
    1817#[unstable(feature = "cmp_minmax", issue = "115939")]
    1818#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1819pub const fn minmax_by<T, F>(v1: T, v2: T, compare: F) -> [T; 2]
    1820where
    1821    F: [const] FnOnce(&T, &T) -> Ordering,
    1822{
    1823    if compare(&v1, &v2).is_le() { [v1, v2] } else { [v2, v1] }
    1824}
    1825
    1826/// Returns minimum and maximum values with respect to the specified key function.
    1827///
    1828/// Returns `[v1, v2]` if the comparison determines them to be equal.
    1829///
    1830/// # Examples
    1831///
    1832/// ```
    1833/// #![feature(cmp_minmax)]
    1834/// use std::cmp;
    1835///
    1836/// assert_eq!(cmp::minmax_by_key(-2, 1, |x: &i32| x.abs()), [1, -2]);
    1837/// assert_eq!(cmp::minmax_by_key(-2, 2, |x: &i32| x.abs()), [-2, 2]);
    1838///
    1839/// // You can destructure the result using array patterns
    1840/// let [min, max] = cmp::minmax_by_key(-42, 17, |x: &i32| x.abs());
    1841/// assert_eq!(min, 17);
    1842/// assert_eq!(max, -42);
    1843/// ```
    1844#[inline]
    1845#[must_use]
    1846#[unstable(feature = "cmp_minmax", issue = "115939")]
    1847#[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1848pub const fn minmax_by_key<T, F, K>(v1: T, v2: T, mut f: F) -> [T; 2]
    1849where
    1850    F: [const] FnMut(&T) -> K + [const] Destruct,
    1851    K: [const] Ord + [const] Destruct,
    1852{
    1853    if f(&v2) < f(&v1) { [v2, v1] } else { [v1, v2] }
    1854}
    1855
    1856// Implementation of PartialEq, Eq, PartialOrd and Ord for primitive types
    1857mod impls {
    1858    use crate::cmp::Ordering::{self, Equal, Greater, Less};
    1859    use crate::hint::unreachable_unchecked;
    1860    use crate::marker::PointeeSized;
    1861    use crate::ops::ControlFlow::{self, Break, Continue};
    1862    use crate::panic::const_assert;
    1863
    1864    macro_rules! partial_eq_impl {
    1865        ($($t:ty)*) => ($(
    1866            #[stable(feature = "rust1", since = "1.0.0")]
    1867            #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1868            impl const PartialEq for $t {
    1869                #[inline]
    1870                fn eq(&self, other: &Self) -> bool { *self == *other }
    1871                #[inline]
    1872                fn ne(&self, other: &Self) -> bool { *self != *other }
    1873            }
    1874        )*)
    1875    }
    1876
    1877    #[stable(feature = "rust1", since = "1.0.0")]
    1878    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1879    impl const PartialEq for () {
    1880        #[inline]
    1881        fn eq(&self, _other: &()) -> bool {
    1882            true
    1883        }
    1884        #[inline]
    1885        fn ne(&self, _other: &()) -> bool {
    1886            false
    1887        }
    1888    }
    1889
    1890    partial_eq_impl! {
    1891        bool char usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 f16 f32 f64 f128
    1892    }
    1893
    1894    macro_rules! eq_impl {
    1895        ($($t:ty)*) => ($(
    1896            #[stable(feature = "rust1", since = "1.0.0")]
    1897            #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1898            impl const Eq for $t {}
    1899        )*)
    1900    }
    1901
    1902    eq_impl! { () bool char usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 }
    1903
    1904    #[rustfmt::skip]
    1905    macro_rules! partial_ord_methods_primitive_impl {
    1906        () => {
    1907            #[inline(always)]
    1908            fn lt(&self, other: &Self) -> bool { *self <  *other }
    1909            #[inline(always)]
    1910            fn le(&self, other: &Self) -> bool { *self <= *other }
    1911            #[inline(always)]
    1912            fn gt(&self, other: &Self) -> bool { *self >  *other }
    1913            #[inline(always)]
    1914            fn ge(&self, other: &Self) -> bool { *self >= *other }
    1915
    1916            // These implementations are the same for `Ord` or `PartialOrd` types
    1917            // because if either is NAN the `==` test will fail so we end up in
    1918            // the `Break` case and the comparison will correctly return `false`.
    1919
    1920            #[inline]
    1921            fn __chaining_lt(&self, other: &Self) -> ControlFlow<bool> {
    1922                let (lhs, rhs) = (*self, *other);
    1923                if lhs == rhs { Continue(()) } else { Break(lhs < rhs) }
    1924            }
    1925            #[inline]
    1926            fn __chaining_le(&self, other: &Self) -> ControlFlow<bool> {
    1927                let (lhs, rhs) = (*self, *other);
    1928                if lhs == rhs { Continue(()) } else { Break(lhs <= rhs) }
    1929            }
    1930            #[inline]
    1931            fn __chaining_gt(&self, other: &Self) -> ControlFlow<bool> {
    1932                let (lhs, rhs) = (*self, *other);
    1933                if lhs == rhs { Continue(()) } else { Break(lhs > rhs) }
    1934            }
    1935            #[inline]
    1936            fn __chaining_ge(&self, other: &Self) -> ControlFlow<bool> {
    1937                let (lhs, rhs) = (*self, *other);
    1938                if lhs == rhs { Continue(()) } else { Break(lhs >= rhs) }
    1939            }
    1940        };
    1941    }
    1942
    1943    macro_rules! partial_ord_impl {
    1944        ($($t:ty)*) => ($(
    1945            #[stable(feature = "rust1", since = "1.0.0")]
    1946            #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1947            impl const PartialOrd for $t {
    1948                #[inline]
    1949                fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    1950                    match (*self <= *other, *self >= *other) {
    1951                        (false, false) => None,
    1952                        (false, true) => Some(Greater),
    1953                        (true, false) => Some(Less),
    1954                        (true, true) => Some(Equal),
    1955                    }
    1956                }
    1957
    1958                partial_ord_methods_primitive_impl!();
    1959            }
    1960        )*)
    1961    }
    1962
    1963    #[stable(feature = "rust1", since = "1.0.0")]
    1964    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1965    impl const PartialOrd for () {
    1966        #[inline]
    1967        fn partial_cmp(&self, _: &()) -> Option<Ordering> {
    1968            Some(Equal)
    1969        }
    1970    }
    1971
    1972    #[stable(feature = "rust1", since = "1.0.0")]
    1973    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1974    impl const PartialOrd for bool {
    1975        #[inline]
    1976        fn partial_cmp(&self, other: &bool) -> Option<Ordering> {
    1977            Some(self.cmp(other))
    1978        }
    1979
    1980        partial_ord_methods_primitive_impl!();
    1981    }
    1982
    1983    partial_ord_impl! { f16 f32 f64 f128 }
    1984
    1985    macro_rules! ord_impl {
    1986        ($($t:ty)*) => ($(
    1987            #[stable(feature = "rust1", since = "1.0.0")]
    1988            #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    1989            impl const PartialOrd for $t {
    1990                #[inline]
    1991                fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
    1992                    Some(crate::intrinsics::three_way_compare(*self, *other))
    1993                }
    1994
    1995                partial_ord_methods_primitive_impl!();
    1996            }
    1997
    1998            #[stable(feature = "rust1", since = "1.0.0")]
    1999            #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2000            impl const Ord for $t {
    2001                #[inline]
    2002                fn cmp(&self, other: &Self) -> Ordering {
    2003                    crate::intrinsics::three_way_compare(*self, *other)
    2004                }
    2005
    2006                #[inline]
    2007                #[track_caller]
    2008                fn clamp(self, min: Self, max: Self) -> Self
    2009                {
    2010                    const_assert!(
    2011                        min <= max,
    2012                        "min > max",
    2013                        "min > max. min = {min:?}, max = {max:?}",
    2014                        min: $t,
    2015                        max: $t,
    2016                    );
    2017                    if self < min {
    2018                        min
    2019                    } else if self > max {
    2020                        max
    2021                    } else {
    2022                        self
    2023                    }
    2024                }
    2025            }
    2026        )*)
    2027    }
    2028
    2029    #[stable(feature = "rust1", since = "1.0.0")]
    2030    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2031    impl const Ord for () {
    2032        #[inline]
    2033        fn cmp(&self, _other: &()) -> Ordering {
    2034            Equal
    2035        }
    2036    }
    2037
    2038    #[stable(feature = "rust1", since = "1.0.0")]
    2039    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2040    impl const Ord for bool {
    2041        #[inline]
    2042        fn cmp(&self, other: &bool) -> Ordering {
    2043            // Casting to i8's and converting the difference to an Ordering generates
    2044            // more optimal assembly.
    2045            // See <https://github.com/rust-lang/rust/issues/66780> for more info.
    2046            match (*self as i8) - (*other as i8) {
    2047                -1 => Less,
    2048                0 => Equal,
    2049                1 => Greater,
    2050                // SAFETY: bool as i8 returns 0 or 1, so the difference can't be anything else
    2051                _ => unsafe { unreachable_unchecked() },
    2052            }
    2053        }
    2054
    2055        #[inline]
    2056        fn min(self, other: bool) -> bool {
    2057            self & other
    2058        }
    2059
    2060        #[inline]
    2061        fn max(self, other: bool) -> bool {
    2062            self | other
    2063        }
    2064
    2065        #[inline]
    2066        fn clamp(self, min: bool, max: bool) -> bool {
    2067            assert!(min <= max);
    2068            self.max(min).min(max)
    2069        }
    2070    }
    2071
    2072    ord_impl! { char usize u8 u16 u32 u64 u128 isize i8 i16 i32 i64 i128 }
    2073
    2074    #[unstable(feature = "never_type", issue = "35121")]
    2075    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2076    impl const PartialEq for ! {
    2077        #[inline]
    2078        fn eq(&self, _: &!) -> bool {
    2079            *self
    2080        }
    2081    }
    2082
    2083    #[unstable(feature = "never_type", issue = "35121")]
    2084    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2085    impl const Eq for ! {}
    2086
    2087    #[unstable(feature = "never_type", issue = "35121")]
    2088    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2089    impl const PartialOrd for ! {
    2090        #[inline]
    2091        fn partial_cmp(&self, _: &!) -> Option<Ordering> {
    2092            *self
    2093        }
    2094    }
    2095
    2096    #[unstable(feature = "never_type", issue = "35121")]
    2097    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2098    impl const Ord for ! {
    2099        #[inline]
    2100        fn cmp(&self, _: &!) -> Ordering {
    2101            *self
    2102        }
    2103    }
    2104
    2105    // & pointers
    2106
    2107    #[stable(feature = "rust1", since = "1.0.0")]
    2108    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2109    impl<A: PointeeSized, B: PointeeSized> const PartialEq<&B> for &A
    2110    where
    2111        A: [const] PartialEq<B>,
    2112    {
    2113        #[inline]
    2114        fn eq(&self, other: &&B) -> bool {
    2115            PartialEq::eq(*self, *other)
    2116        }
    2117        #[inline]
    2118        fn ne(&self, other: &&B) -> bool {
    2119            PartialEq::ne(*self, *other)
    2120        }
    2121    }
    2122    #[stable(feature = "rust1", since = "1.0.0")]
    2123    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2124    impl<A: PointeeSized, B: PointeeSized> const PartialOrd<&B> for &A
    2125    where
    2126        A: [const] PartialOrd<B>,
    2127    {
    2128        #[inline]
    2129        fn partial_cmp(&self, other: &&B) -> Option<Ordering> {
    2130            PartialOrd::partial_cmp(*self, *other)
    2131        }
    2132        #[inline]
    2133        fn lt(&self, other: &&B) -> bool {
    2134            PartialOrd::lt(*self, *other)
    2135        }
    2136        #[inline]
    2137        fn le(&self, other: &&B) -> bool {
    2138            PartialOrd::le(*self, *other)
    2139        }
    2140        #[inline]
    2141        fn gt(&self, other: &&B) -> bool {
    2142            PartialOrd::gt(*self, *other)
    2143        }
    2144        #[inline]
    2145        fn ge(&self, other: &&B) -> bool {
    2146            PartialOrd::ge(*self, *other)
    2147        }
    2148        #[inline]
    2149        fn __chaining_lt(&self, other: &&B) -> ControlFlow<bool> {
    2150            PartialOrd::__chaining_lt(*self, *other)
    2151        }
    2152        #[inline]
    2153        fn __chaining_le(&self, other: &&B) -> ControlFlow<bool> {
    2154            PartialOrd::__chaining_le(*self, *other)
    2155        }
    2156        #[inline]
    2157        fn __chaining_gt(&self, other: &&B) -> ControlFlow<bool> {
    2158            PartialOrd::__chaining_gt(*self, *other)
    2159        }
    2160        #[inline]
    2161        fn __chaining_ge(&self, other: &&B) -> ControlFlow<bool> {
    2162            PartialOrd::__chaining_ge(*self, *other)
    2163        }
    2164    }
    2165    #[stable(feature = "rust1", since = "1.0.0")]
    2166    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2167    impl<A: PointeeSized> const Ord for &A
    2168    where
    2169        A: [const] Ord,
    2170    {
    2171        #[inline]
    2172        fn cmp(&self, other: &Self) -> Ordering {
    2173            Ord::cmp(*self, *other)
    2174        }
    2175    }
    2176    #[stable(feature = "rust1", since = "1.0.0")]
    2177    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2178    impl<A: PointeeSized> const Eq for &A where A: [const] Eq {}
    2179
    2180    // &mut pointers
    2181
    2182    #[stable(feature = "rust1", since = "1.0.0")]
    2183    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2184    impl<A: PointeeSized, B: PointeeSized> const PartialEq<&mut B> for &mut A
    2185    where
    2186        A: [const] PartialEq<B>,
    2187    {
    2188        #[inline]
    2189        fn eq(&self, other: &&mut B) -> bool {
    2190            PartialEq::eq(*self, *other)
    2191        }
    2192        #[inline]
    2193        fn ne(&self, other: &&mut B) -> bool {
    2194            PartialEq::ne(*self, *other)
    2195        }
    2196    }
    2197    #[stable(feature = "rust1", since = "1.0.0")]
    2198    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2199    impl<A: PointeeSized, B: PointeeSized> const PartialOrd<&mut B> for &mut A
    2200    where
    2201        A: [const] PartialOrd<B>,
    2202    {
    2203        #[inline]
    2204        fn partial_cmp(&self, other: &&mut B) -> Option<Ordering> {
    2205            PartialOrd::partial_cmp(*self, *other)
    2206        }
    2207        #[inline]
    2208        fn lt(&self, other: &&mut B) -> bool {
    2209            PartialOrd::lt(*self, *other)
    2210        }
    2211        #[inline]
    2212        fn le(&self, other: &&mut B) -> bool {
    2213            PartialOrd::le(*self, *other)
    2214        }
    2215        #[inline]
    2216        fn gt(&self, other: &&mut B) -> bool {
    2217            PartialOrd::gt(*self, *other)
    2218        }
    2219        #[inline]
    2220        fn ge(&self, other: &&mut B) -> bool {
    2221            PartialOrd::ge(*self, *other)
    2222        }
    2223        #[inline]
    2224        fn __chaining_lt(&self, other: &&mut B) -> ControlFlow<bool> {
    2225            PartialOrd::__chaining_lt(*self, *other)
    2226        }
    2227        #[inline]
    2228        fn __chaining_le(&self, other: &&mut B) -> ControlFlow<bool> {
    2229            PartialOrd::__chaining_le(*self, *other)
    2230        }
    2231        #[inline]
    2232        fn __chaining_gt(&self, other: &&mut B) -> ControlFlow<bool> {
    2233            PartialOrd::__chaining_gt(*self, *other)
    2234        }
    2235        #[inline]
    2236        fn __chaining_ge(&self, other: &&mut B) -> ControlFlow<bool> {
    2237            PartialOrd::__chaining_ge(*self, *other)
    2238        }
    2239    }
    2240    #[stable(feature = "rust1", since = "1.0.0")]
    2241    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2242    impl<A: PointeeSized> const Ord for &mut A
    2243    where
    2244        A: [const] Ord,
    2245    {
    2246        #[inline]
    2247        fn cmp(&self, other: &Self) -> Ordering {
    2248            Ord::cmp(*self, *other)
    2249        }
    2250    }
    2251    #[stable(feature = "rust1", since = "1.0.0")]
    2252    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2253    impl<A: PointeeSized> const Eq for &mut A where A: [const] Eq {}
    2254
    2255    #[stable(feature = "rust1", since = "1.0.0")]
    2256    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2257    impl<A: PointeeSized, B: PointeeSized> const PartialEq<&mut B> for &A
    2258    where
    2259        A: [const] PartialEq<B>,
    2260    {
    2261        #[inline]
    2262        fn eq(&self, other: &&mut B) -> bool {
    2263            PartialEq::eq(*self, *other)
    2264        }
    2265        #[inline]
    2266        fn ne(&self, other: &&mut B) -> bool {
    2267            PartialEq::ne(*self, *other)
    2268        }
    2269    }
    2270
    2271    #[stable(feature = "rust1", since = "1.0.0")]
    2272    #[rustc_const_unstable(feature = "const_cmp", issue = "143800")]
    2273    impl<A: PointeeSized, B: PointeeSized> const PartialEq<&B> for &mut A
    2274    where
    2275        A: [const] PartialEq<B>,
    2276    {
    2277        #[inline]
    2278        fn eq(&self, other: &&B) -> bool {
    2279            PartialEq::eq(*self, *other)
    2280        }
    2281        #[inline]
    2282        fn ne(&self, other: &&B) -> bool {
    2283            PartialEq::ne(*self, *other)
    2284        }
    2285    }
    2286}