# Simplifying custom comparison and hashing

**URL:** <https://internals.rust-lang.org/t/simplifying-custom-comparison-and-hashing/5108>\
**Category:** libs\
**Created:** [April 17, 2017, 3:23pm UTC](https://internals.rust-lang.org/t/simplifying-custom-comparison-and-hashing/5108 "2017-04-17T15:23:32Z")\
**Posts on this page:** 2\
**Page:** 1

<div class="post-metadata">

**Author:** ![matthieum](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/matthieum/32/4023_2.png) [@matthieum](https://internals.rust-lang.org/u/matthieum)\
**Post date:** [April 17, 2017, 3:23pm UTC](https://internals.rust-lang.org/t/simplifying-custom-comparison-and-hashing/5108/1 "2017-04-17T15:23:32Z")

</div>

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](https://play.rust-lang.org/?gist=b4445e8d2ffe2e8fe99bce52ecf507d4&version=stable&backtrace=0):

```
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?

---

<div class="post-metadata">

**Author:** ![matthieum](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/matthieum/32/4023_2.png) [@matthieum](https://internals.rust-lang.org/u/matthieum)\
**Post date:** [March 25, 2019, 8:28am UTC](https://internals.rust-lang.org/t/simplifying-custom-comparison-and-hashing/5108/2 "2019-03-25T08:28:23Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.