The implicit contract of `PartialOrd: PartialEq`


#1

Something has been bothering me.

Consider the following wrapper type, which provides a custom Ord for the purpose of e.g. usage in BTreeSet:

use std::cmp::Ordering;
use std::collections::BTreeSet;

// A wrapper around (i32,i32) that compares by sum.
#[derive(PartialEq,Eq,Copy,Clone,Debug)]
struct Wrapper(i32, i32);

impl Wrapper {
    fn key(self) -> i32 { self.0 + self.1 }
}

impl PartialOrd for Wrapper {
    fn partial_cmp(&self, other: &Wrapper) -> Option<Ordering> {
        self.key().partial_cmp(&other.key())
    }
}

impl Ord for Wrapper {
    fn cmp(&self, other: &Wrapper) -> Ordering {
        self.key().cmp(&other.key())
    }
}

fn main() {
    let vec = vec![Wrapper(2, 3), Wrapper(5, 4), Wrapper(1, 4)];
    let set: BTreeSet<_> = vec.into_iter().collect();
    
    assert_eq!(
        set.into_iter().collect::<Vec<_>>(),
        vec![Wrapper(2,3), Wrapper(5,4)]
    );
}

Looks innocent, right? Perhaps others themselves have even written such a type at least once.

But there is, in fact, a subtle problem with this type:

a == b is not equivalent to a.cmp(&b) == Ordering::Equal.

This violates a contract which is embedded in the very fact that PartialOrd: PartialEq and Ord: Eq.


To be honest, this relationship isn’t one that I tend to think about. In my mind, equivalence and order are orthogonal concepts, and it wouldn’t surprise me if at some point in the past I had written a type just like Wrapper, unaware of the contract it violates.

What do others think? How prevalent might types like Wrapper be in existing rust code, and are they ticking time bombs or no big deal? Could/Should something be done to discourage their creation?


#2

PartialEq, Eq(*), PartialOrd and Ord must(**) all define the same order when they are implemented (any number of them) for a type. That requirement or contract may not be completely spelled out in the docs. It is unclear if the comparison operators used in the Ord docs are intended to hint to the PartialOrd trait or are just there for talking about orderings in general. I’d assume the latter.

(*) Eq does not define any operator or method, but is just an extra contract for the equivalence implemented by PartialEq.

(**) must what? Simply if a type’s trait implementations violate it, they are buggy. There is no trust relationship; unsafe code blocks are not allowed to trust arbitrary trait impls to behave in any particular way at all.

This is my very own digression, but the deal with buggy implementations is more or less: if my function requires T: Ord as input, and is used with a T whose implementations violate the contracts of the implied traits, then my function might violate its implicit or explicit contracts too.