Simplifying custom comparison and hashing

[matthieum]

There have been some discussions lately about comparison:

• the fact that PartialOrd and PartialEq are generally “clutter” for most beginners who just want a comparable type,
• the issue that non-type generic parameters would require structural equality, to get avoid incorrectly written comparison operators leading to unsafety,
• the issue that some algorithms (sorts, binary searchs, …) could be sped up if they could rely on Ord having correct semantics (eliding bounds-checks).

---

I have been thinking for a while about the former issue.

The second reason is that:

#[derive(PartialEq, Eq, PartialOrd, Ord, Hash)]

is an eye-full for what seems to be “basic” functionality.

The first reason is that when defining custom definitions for those, it is easy to accidentally mess up the definitions, resulting:

• in equality that is not reflexive, transitive, …
• in inequality that is not irreflexive, transitive, …
• in inconsistency between different traits (for example, #[derive(Ord)] with a custom PartialOrd does not work).

---

Most of the times, when I’ve seen the need for custom comparisons, it has been related to simply picking a subset of fields as the “key” part.

Since C++11 I’ve largely solved the issue in C++ by simply creating a key() method, which gives me a tuple of references to the fields of interest in my struct/class. Comparison being implemented for tuples, it’s then a simple matter of throwing in a macro to automatically generate the <, >, … for the current type based on forwarding the operation to the result of .key(). It works pretty well.

It has the downside of (unfortunately) exposing internal implementation details. I am not sure how impacting this is in practice.

I think it could be ported over to Rust, and I made a prototype on the playground:

trait Key {
    type Output;
    fn key(&self) -> Self::Output;
}

impl<T> PartialEq for T
    where
        T: Key,
        <T as Key>::Output: PartialEq
{
    fn eq(&self, other: &T) -> bool { self.key().eq(&other.key()) }
}

impl<T> PartialOrd for T
    where
        T: Key,
        <T as Key>::Output: PartialOrd
{
    fn partial_cmp(&self, other: &T) -> Option<Ordering> {
        self.key().partial_cmp(&other.key())
    }
}

It is one of those usecases where ACT would help tremendously, as the ideal implementation would connect the lifetime of Output to that of self, however it’s still partially usable today:

struct Pair(String, String);

impl<'a> Key for &'a Pair {
    type Output = (&'a str, &'a str);
    fn key(&self) -> Self::Output { (&*self.0, &*self.1) }
}

The fact that it cannot be implemented directly for Pair is annoying, though. And leads to a weird syntax: (&p).partial_cmp(&&p) where p is Pair. Hopefully, said syntax can be hidden from the general public when using the regular operators.

Still, Key has the advantage of allowing defining the notion of comparison once and for all for a given type, and from there the implementations of PartialEq, Eq, PartialOrd, Ord and Hash can be automatically generated:

• guaranteed to follow the mathematical rules, if the base types do,
• guaranteed to be consistent with each other.

It should also be relatively trivial to allow easy customization: #[derive(Key)] and #[derive(Key(field1, field3))].

Also, if everything is Key all the way down (to trusted types), then we should get structural equality as needed for constant types; though that would be a bonus.

Thoughts?