Rollup merge of #129003 - Voultapher:improve-ord-docs, r=workingjubilee

Improve Ord docs

- Makes wording more clear and re-structures some sections that can be overwhelming for someone not already in the know.
- Adds examples of how *not* to implement Ord, inspired by various anti-patterns found in real world code.

Many of the wording changes are inspired directly by my personal experience of being confused by the `Ord` docs and seeing other people get it wrong as well, especially lately having looked at a number of `Ord` implementations as part of #128899.

Created with help by `@orlp.`

r​? `@workingjubilee`

1 files changed, 257 insertions, 99 deletions

diff --git a/library/core/src/cmp.rs b/library/core/src/cmp.rs
index 818a36002e7..4377b4993b8 100644
--- a/library/core/src/cmp.rs
+++ b/library/core/src/cmp.rs
@@ -275,49 +275,56 @@ pub macro PartialEq($item:item) {
 /// Trait for comparisons corresponding to [equivalence relations](
 /// https://en.wikipedia.org/wiki/Equivalence_relation).
 ///
-/// This means, that in addition to `a == b` and `a != b` being strict inverses,
-/// the relation must be (for all `a`, `b` and `c`):
+/// The primary difference to [`PartialEq`] is the additional requirement for reflexivity. A type
+/// that implements [`PartialEq`] guarantees that for all `a`, `b` and `c`:
 ///
-/// - reflexive: `a == a`;
-/// - symmetric: `a == b` implies `b == a` (required by `PartialEq` as well); and
-/// - transitive: `a == b` and `b == c` implies `a == c` (required by `PartialEq` as well).
+/// - symmetric: `a == b` implies `b == a` and `a != b` implies `!(a == b)`
+/// - transitive: `a == b` and `b == c` implies `a == c`
 ///
-/// This property cannot be checked by the compiler, and therefore `Eq` implies
-/// [`PartialEq`], and has no extra methods.
+/// `Eq`, which builds on top of [`PartialEq`] also implies:
+///
+/// - reflexive: `a == a`
+///
+/// This property cannot be checked by the compiler, and therefore `Eq` is a trait without methods.
 ///
 /// Violating this property is a logic error. The behavior resulting from a logic error is not
 /// specified, but users of the trait must ensure that such logic errors do *not* result in
 /// undefined behavior. This means that `unsafe` code **must not** rely on the correctness of these
 /// methods.
 ///
-/// Implement `Eq` in addition to `PartialEq` if it's guaranteed that
-/// `PartialEq::eq(a, a)` always returns `true` (reflexivity), in addition to
-/// the symmetric and transitive properties already required by `PartialEq`.
+/// Floating point types such as [`f32`] and [`f64`] implement only [`PartialEq`] but *not* `Eq`
+/// because `NaN` != `NaN`.
 ///
 /// ## Derivable
 ///
-/// This trait can be used with `#[derive]`. When `derive`d, because `Eq` has
-/// no extra methods, it is only informing the compiler that this is an
-/// equivalence relation rather than a partial equivalence relation. Note that
-/// the `derive` strategy requires all fields are `Eq`, which isn't
+/// This trait can be used with `#[derive]`. When `derive`d, because `Eq` has no extra methods, it
+/// is only informing the compiler that this is an equivalence relation rather than a partial
+/// equivalence relation. Note that the `derive` strategy requires all fields are `Eq`, which isn't
 /// always desired.
 ///
 /// ## How can I implement `Eq`?
 ///
-/// If you cannot use the `derive` strategy, specify that your type implements
-/// `Eq`, which has no methods:
+/// If you cannot use the `derive` strategy, specify that your type implements `Eq`, which has no
+/// extra methods:
 ///
 /// ```
-/// enum BookFormat { Paperback, Hardback, Ebook }
+/// enum BookFormat {
+///     Paperback,
+///     Hardback,
+///     Ebook,
+/// }
+///
 /// struct Book {
 ///     isbn: i32,
 ///     format: BookFormat,
 /// }
+///
 /// impl PartialEq for Book {
 ///     fn eq(&self, other: &Self) -> bool {
 ///         self.isbn == other.isbn
 ///     }
 /// }
+///
 /// impl Eq for Book {}
 /// ```
 #[doc(alias = "==")]
@@ -325,11 +332,9 @@ pub macro PartialEq($item:item) {
 #[stable(feature = "rust1", since = "1.0.0")]
 #[rustc_diagnostic_item = "Eq"]
 pub trait Eq: PartialEq<Self> {
-    // this method is used solely by #[derive(Eq)] to assert
-    // that every component of a type implements `Eq`
-    // itself. The current deriving infrastructure means doing this
-    // assertion without using a method on this trait is nearly
-    // impossible.
+    // this method is used solely by `impl Eq or #[derive(Eq)]` to assert that every component of a
+    // type implements `Eq` itself. The current deriving infrastructure means doing this assertion
+    // without using a method on this trait is nearly impossible.
     //
     // This should never be implemented by hand.
     #[doc(hidden)]
@@ -693,17 +698,14 @@ impl<T: Clone> Clone for Reverse<T> {
 
 /// Trait for types that form a [total order](https://en.wikipedia.org/wiki/Total_order).
 ///
-/// Implementations must be consistent with the [`PartialOrd`] implementation, and ensure
-/// `max`, `min`, and `clamp` are consistent with `cmp`:
+/// Implementations must be consistent with the [`PartialOrd`] implementation, and ensure `max`,
+/// `min`, and `clamp` are consistent with `cmp`:
 ///
 /// - `partial_cmp(a, b) == Some(cmp(a, b))`.
 /// - `max(a, b) == max_by(a, b, cmp)` (ensured by the default implementation).
 /// - `min(a, b) == min_by(a, b, cmp)` (ensured by the default implementation).
-/// - For `a.clamp(min, max)`, see the [method docs](#method.clamp)
-///   (ensured by the default implementation).
-///
-/// It's easy to accidentally make `cmp` and `partial_cmp` disagree by
-/// deriving some of the traits and manually implementing others.
+/// - For `a.clamp(min, max)`, see the [method docs](#method.clamp) (ensured by the default
+///   implementation).
 ///
 /// Violating these requirements is a logic error. The behavior resulting from a logic error is not
 /// specified, but users of the trait must ensure that such logic errors do *not* result in
@@ -712,15 +714,14 @@ impl<T: Clone> Clone for Reverse<T> {
 ///
 /// ## Corollaries
 ///
-/// From the above and the requirements of `PartialOrd`, it follows that for
-/// all `a`, `b` and `c`:
+/// From the above and the requirements of `PartialOrd`, it follows that for all `a`, `b` and `c`:
 ///
 /// - exactly one of `a < b`, `a == b` or `a > b` is true; and
-/// - `<` is transitive: `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`.
+/// - `<` is transitive: `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and
+///   `>`.
 ///
-/// Mathematically speaking, the `<` operator defines a strict [weak order]. In
-/// cases where `==` conforms to mathematical equality, it also defines a
-/// strict [total order].
+/// Mathematically speaking, the `<` operator defines a strict [weak order]. In cases where `==`
+/// conforms to mathematical equality, it also defines a strict [total order].
 ///
 /// [weak order]: https://en.wikipedia.org/wiki/Weak_ordering
 /// [total order]: https://en.wikipedia.org/wiki/Total_order
@@ -730,13 +731,12 @@ impl<T: Clone> Clone for Reverse<T> {
 /// This trait can be used with `#[derive]`.
 ///
 /// When `derive`d on structs, it will produce a
-/// [lexicographic](https://en.wikipedia.org/wiki/Lexicographic_order) ordering
-/// based on the top-to-bottom declaration order of the struct's members.
+/// [lexicographic](https://en.wikipedia.org/wiki/Lexicographic_order) ordering based on the
+/// top-to-bottom declaration order of the struct's members.
 ///
-/// When `derive`d on enums, variants are ordered primarily by their discriminants.
-/// Secondarily, they are ordered by their fields.
-/// By default, the discriminant is smallest for variants at the top, and
-/// largest for variants at the bottom. Here's an example:
+/// When `derive`d on enums, variants are ordered primarily by their discriminants. Secondarily,
+/// they are ordered by their fields. By default, the discriminant is smallest for variants at the
+/// top, and largest for variants at the bottom. Here's an example:
 ///
 /// ```
 /// #[derive(PartialEq, Eq, PartialOrd, Ord)]
@@ -748,8 +748,7 @@ impl<T: Clone> Clone for Reverse<T> {
 /// assert!(E::Top < E::Bottom);
 /// ```
 ///
-/// However, manually setting the discriminants can override this default
-/// behavior:
+/// However, manually setting the discriminants can override this default behavior:
 ///
 /// ```
 /// #[derive(PartialEq, Eq, PartialOrd, Ord)]
@@ -765,51 +764,178 @@ impl<T: Clone> Clone for Reverse<T> {
 ///
 /// Lexicographical comparison is an operation with the following properties:
 ///  - Two sequences are compared element by element.
-///  - The first mismatching element defines which sequence is lexicographically less or greater than the other.
-///  - If one sequence is a prefix of another, the shorter sequence is lexicographically less than the other.
-///  - If two sequences have equivalent elements and are of the same length, then the sequences are lexicographically equal.
+///  - The first mismatching element defines which sequence is lexicographically less or greater
+///    than the other.
+///  - If one sequence is a prefix of another, the shorter sequence is lexicographically less than
+///    the other.
+///  - If two sequences have equivalent elements and are of the same length, then the sequences are
+///    lexicographically equal.
 ///  - An empty sequence is lexicographically less than any non-empty sequence.
 ///  - Two empty sequences are lexicographically equal.
 ///
 /// ## How can I implement `Ord`?
 ///
-/// `Ord` requires that the type also be [`PartialOrd`] and [`Eq`] (which requires [`PartialEq`]).
+/// `Ord` requires that the type also be [`PartialOrd`], [`PartialEq`], and [`Eq`].
 ///
-/// Then you must define an implementation for [`cmp`]. You may find it useful to use
-/// [`cmp`] on your type's fields.
+/// Because `Ord` implies a stronger ordering relationship than [`PartialOrd`], and both `Ord` and
+/// [`PartialOrd`] must agree, you must choose how to implement `Ord` **first**. You can choose to
+/// derive it, or implement it manually. If you derive it, you should derive all four traits. If you
+/// implement it manually, you should manually implement all four traits, based on the
+/// implementation of `Ord`.
 ///
-/// Here's an example where you want to sort people by height only, disregarding `id`
-/// and `name`:
+/// Here's an example where you want to define the `Character` comparison by `health` and
+/// `experience` only, disregarding the field `mana`:
 ///
 /// ```
 /// use std::cmp::Ordering;
 ///
-/// #[derive(Eq)]
-/// struct Person {
-///     id: u32,
-///     name: String,
-///     height: u32,
+/// struct Character {
+///     health: u32,
+///     experience: u32,
+///     mana: f32,
 /// }
 ///
-/// impl Ord for Person {
-///     fn cmp(&self, other: &Self) -> Ordering {
-///         self.height.cmp(&other.height)
+/// impl Ord for Character {
+///     fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+///         self.experience
+///             .cmp(&other.experience)
+///             .then(self.health.cmp(&other.health))
 ///     }
 /// }
 ///
-/// impl PartialOrd for Person {
+/// impl PartialOrd for Character {
 ///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
 ///         Some(self.cmp(other))
 ///     }
 /// }
 ///
-/// impl PartialEq for Person {
+/// impl PartialEq for Character {
 ///     fn eq(&self, other: &Self) -> bool {
-///         self.height == other.height
+///         self.health == other.health && self.experience == other.experience
+///     }
+/// }
+///
+/// impl Eq for Character {}
+/// ```
+///
+/// If all you need is to `slice::sort` a type by a field value, it can be simpler to use
+/// `slice::sort_by_key`.
+///
+/// ## Examples of incorrect `Ord` implementations
+///
+/// ```
+/// use std::cmp::Ordering;
+///
+/// #[derive(Debug)]
+/// struct Character {
+///     health: f32,
+/// }
+///
+/// impl Ord for Character {
+///     fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+///         if self.health < other.health {
+///             Ordering::Less
+///         } else if self.health > other.health {
+///             Ordering::Greater
+///         } else {
+///             Ordering::Equal
+///         }
+///     }
+/// }
+///
+/// impl PartialOrd for Character {
+///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+///         Some(self.cmp(other))
+///     }
+/// }
+///
+/// impl PartialEq for Character {
+///     fn eq(&self, other: &Self) -> bool {
+///         self.health == other.health
+///     }
+/// }
+///
+/// impl Eq for Character {}
+///
+/// let a = Character { health: 4.5 };
+/// let b = Character { health: f32::NAN };
+///
+/// // Mistake: floating-point values do not form a total order and using the built-in comparison
+/// // operands to implement `Ord` irregardless of that reality does not change it. Use
+/// // `f32::total_cmp` if you need a total order for floating-point values.
+///
+/// // Reflexivity requirement of `Ord` is not given.
+/// assert!(a == a);
+/// assert!(b != b);
+///
+/// // Antisymmetry requirement of `Ord` is not given. Only one of a < c and c < a is allowed to be
+/// // true, not both or neither.
+/// assert_eq!((a < b) as u8 + (b < a) as u8, 0);
+/// ```
+///
+/// ```
+/// use std::cmp::Ordering;
+///
+/// #[derive(Debug)]
+/// struct Character {
+///     health: u32,
+///     experience: u32,
+/// }
+///
+/// impl PartialOrd for Character {
+///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+///         Some(self.cmp(other))
+///     }
+/// }
+///
+/// impl Ord for Character {
+///     fn cmp(&self, other: &Self) -> std::cmp::Ordering {
+///         if self.health < 50 {
+///             self.health.cmp(&other.health)
+///         } else {
+///             self.experience.cmp(&other.experience)
+///         }
+///     }
+/// }
+///
+/// // For performance reasons implementing `PartialEq` this way is not the idiomatic way, but it
+/// // ensures consistent behavior between `PartialEq`, `PartialOrd` and `Ord` in this example.
+/// impl PartialEq for Character {
+///     fn eq(&self, other: &Self) -> bool {
+///         self.cmp(other) == Ordering::Equal
 ///     }
 /// }
+///
+/// impl Eq for Character {}
+///
+/// let a = Character {
+///     health: 3,
+///     experience: 5,
+/// };
+/// let b = Character {
+///     health: 10,
+///     experience: 77,
+/// };
+/// let c = Character {
+///     health: 143,
+///     experience: 2,
+/// };
+///
+/// // Mistake: The implementation of `Ord` compares different fields depending on the value of
+/// // `self.health`, the resulting order is not total.
+///
+/// // Transitivity requirement of `Ord` is not given. If a is smaller than b and b is smaller than
+/// // c, by transitive property a must also be smaller than c.
+/// assert!(a < b && b < c && c < a);
+///
+/// // Antisymmetry requirement of `Ord` is not given. Only one of a < c and c < a is allowed to be
+/// // true, not both or neither.
+/// assert_eq!((a < c) as u8 + (c < a) as u8, 2);
 /// ```
 ///
+/// The documentation of [`PartialOrd`] contains further examples, for example it's wrong for
+/// [`PartialOrd`] and [`PartialEq`] to disagree.
+///
 /// [`cmp`]: Ord::cmp
 #[doc(alias = "<")]
 #[doc(alias = ">")]
@@ -924,8 +1050,12 @@ pub macro Ord($item:item) {
 
 /// Trait for types that form a [partial order](https://en.wikipedia.org/wiki/Partial_order).
 ///
-/// The `lt`, `le`, `gt`, and `ge` methods of this trait can be called using
-/// the `<`, `<=`, `>`, and `>=` operators, respectively.
+/// The `lt`, `le`, `gt`, and `ge` methods of this trait can be called using the `<`, `<=`, `>`, and
+/// `>=` operators, respectively.
+///
+/// This trait should **only** contain the comparison logic for a type **if one plans on only
+/// implementing `PartialOrd` but not [`Ord`]**. Otherwise the comparison logic should be in [`Ord`]
+/// and this trait implemented with `Some(self.cmp(other))`.
 ///
 /// The methods of this trait must be consistent with each other and with those of [`PartialEq`].
 /// The following conditions must hold:
@@ -937,26 +1067,25 @@ pub macro Ord($item:item) {
 /// 5. `a >= b` if and only if `a > b || a == b`
 /// 6. `a != b` if and only if `!(a == b)`.
 ///
-/// Conditions 2–5 above are ensured by the default implementation.
-/// Condition 6 is already ensured by [`PartialEq`].
+/// Conditions 2–5 above are ensured by the default implementation. Condition 6 is already ensured
+/// by [`PartialEq`].
 ///
 /// If [`Ord`] is also implemented for `Self` and `Rhs`, it must also be consistent with
-/// `partial_cmp` (see the documentation of that trait for the exact requirements). It's
-/// easy to accidentally make them disagree by deriving some of the traits and manually
-/// implementing others.
+/// `partial_cmp` (see the documentation of that trait for the exact requirements). It's easy to
+/// accidentally make them disagree by deriving some of the traits and manually implementing others.
 ///
-/// The comparison relations must satisfy the following conditions
-/// (for all `a`, `b`, `c` of type `A`, `B`, `C`):
+/// The comparison relations must satisfy the following conditions (for all `a`, `b`, `c` of type
+/// `A`, `B`, `C`):
 ///
-/// - **Transitivity**: if `A: PartialOrd<B>` and `B: PartialOrd<C>` and `A:
-///   PartialOrd<C>`, then `a < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`.
-///   This must also work for longer chains, such as when `A: PartialOrd<B>`, `B: PartialOrd<C>`,
-///   `C: PartialOrd<D>`, and `A: PartialOrd<D>` all exist.
-/// - **Duality**: if `A: PartialOrd<B>` and `B: PartialOrd<A>`, then `a < b` if and only if `b > a`.
+/// - **Transitivity**: if `A: PartialOrd<B>` and `B: PartialOrd<C>` and `A: PartialOrd<C>`, then `a
+///   < b` and `b < c` implies `a < c`. The same must hold for both `==` and `>`. This must also
+///   work for longer chains, such as when `A: PartialOrd<B>`, `B: PartialOrd<C>`, `C:
+///   PartialOrd<D>`, and `A: PartialOrd<D>` all exist.
+/// - **Duality**: if `A: PartialOrd<B>` and `B: PartialOrd<A>`, then `a < b` if and only if `b >
+///   a`.
 ///
-/// Note that the `B: PartialOrd<A>` (dual) and `A: PartialOrd<C>`
-/// (transitive) impls are not forced to exist, but these requirements apply
-/// whenever they do exist.
+/// Note that the `B: PartialOrd<A>` (dual) and `A: PartialOrd<C>` (transitive) impls are not forced
+/// to exist, but these requirements apply whenever they do exist.
 ///
 /// Violating these requirements is a logic error. The behavior resulting from a logic error is not
 /// specified, but users of the trait must ensure that such logic errors do *not* result in
@@ -992,12 +1121,10 @@ pub macro Ord($item:item) {
 ///
 /// ## Strict and non-strict partial orders
 ///
-/// The `<` and `>` operators behave according to a *strict* partial order.
-/// However, `<=` and `>=` do **not** behave according to a *non-strict*
-/// partial order.
-/// That is because mathematically, a non-strict partial order would require
-/// reflexivity, i.e. `a <= a` would need to be true for every `a`. This isn't
-/// always the case for types that implement `PartialOrd`, for example:
+/// The `<` and `>` operators behave according to a *strict* partial order. However, `<=` and `>=`
+/// do **not** behave according to a *non-strict* partial order. That is because mathematically, a
+/// non-strict partial order would require reflexivity, i.e. `a <= a` would need to be true for
+/// every `a`. This isn't always the case for types that implement `PartialOrd`, for example:
 ///
 /// ```
 /// let a = f64::sqrt(-1.0);
@@ -1009,13 +1136,12 @@ pub macro Ord($item:item) {
 /// This trait can be used with `#[derive]`.
 ///
 /// When `derive`d on structs, it will produce a
-/// [lexicographic](https://en.wikipedia.org/wiki/Lexicographic_order) ordering
-/// based on the top-to-bottom declaration order of the struct's members.
+/// [lexicographic](https://en.wikipedia.org/wiki/Lexicographic_order) ordering based on the
+/// top-to-bottom declaration order of the struct's members.
 ///
-/// When `derive`d on enums, variants are primarily ordered by their discriminants.
-/// Secondarily, they are ordered by their fields.
-/// By default, the discriminant is smallest for variants at the top, and
-/// largest for variants at the bottom. Here's an example:
+/// When `derive`d on enums, variants are primarily ordered by their discriminants. Secondarily,
+/// they are ordered by their fields. By default, the discriminant is smallest for variants at the
+/// top, and largest for variants at the bottom. Here's an example:
 ///
 /// ```
 /// #[derive(PartialEq, PartialOrd)]
@@ -1027,8 +1153,7 @@ pub macro Ord($item:item) {
 /// assert!(E::Top < E::Bottom);
 /// ```
 ///
-/// However, manually setting the discriminants can override this default
-/// behavior:
+/// However, manually setting the discriminants can override this default behavior:
 ///
 /// ```
 /// #[derive(PartialEq, PartialOrd)]
@@ -1046,8 +1171,8 @@ pub macro Ord($item:item) {
 /// generated from default implementations.
 ///
 /// However it remains possible to implement the others separately for types which do not have a
-/// total order. For example, for floating point numbers, `NaN < 0 == false` and `NaN >= 0 ==
-/// false` (cf. IEEE 754-2008 section 5.11).
+/// total order. For example, for floating point numbers, `NaN < 0 == false` and `NaN >= 0 == false`
+/// (cf. IEEE 754-2008 section 5.11).
 ///
 /// `PartialOrd` requires your type to be [`PartialEq`].
 ///
@@ -1056,7 +1181,6 @@ pub macro Ord($item:item) {
 /// ```
 /// use std::cmp::Ordering;
 ///
-/// #[derive(Eq)]
 /// struct Person {
 ///     id: u32,
 ///     name: String,
@@ -1080,11 +1204,13 @@ pub macro Ord($item:item) {
 ///         self.height == other.height
 ///     }
 /// }
+///
+/// impl Eq for Person {}
 /// ```
 ///
-/// You may also find it useful to use [`partial_cmp`] on your type's fields. Here
-/// is an example of `Person` types who have a floating-point `height` field that
-/// is the only field to be used for sorting:
+/// You may also find it useful to use [`partial_cmp`] on your type's fields. Here is an example of
+/// `Person` types who have a floating-point `height` field that is the only field to be used for
+/// sorting:
 ///
 /// ```
 /// use std::cmp::Ordering;
@@ -1108,6 +1234,38 @@ pub macro Ord($item:item) {
 /// }
 /// ```
 ///
+/// ## Examples of incorrect `PartialOrd` implementations
+///
+/// ```
+/// use std::cmp::Ordering;
+///
+/// #[derive(PartialEq, Debug)]
+/// struct Character {
+///     health: u32,
+///     experience: u32,
+/// }
+///
+/// impl PartialOrd for Character {
+///     fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+///         Some(self.health.cmp(&other.health))
+///     }
+/// }
+///
+/// let a = Character {
+///     health: 10,
+///     experience: 5,
+/// };
+/// let b = Character {
+///     health: 10,
+///     experience: 77,
+/// };
+///
+/// // Mistake: `PartialEq` and `PartialOrd` disagree with each other.
+///
+/// assert_eq!(a.partial_cmp(&b).unwrap(), Ordering::Equal); // a == b according to `PartialOrd`.
+/// assert_ne!(a, b); // a != b according to `PartialEq`.
+/// ```
+///
 /// # Examples
 ///
 /// ```