PreRFC: `std::cmp::CmpKey` trait

language design
1

PreRFC: std::cmp::CmpKey trait

Motivation

Currently, there are four traits in the std::cmp crate about the comparing:

  • std::cmp::PartialEq
  • std::cmp::Eq
  • std::cmp::PartialOrd
  • std::cmp::Ord

Users must ensure every methods implementation are consistent, otherwise some terrible things may happen.

The constraints includes:

  • methods in the same trait: eq and ne, cmp and gt
  • methods in different traits: eq, partial_eq and partial_cmp

In most cases, we only need some fields projection in the implementation, but sometimes we may make some foolish bugs and introduce terrible results. The bug is hard to reported by clippy.

struct Row {
    x: i32,
    y: i32,

    // Assume there were some complex fields which disable we using derive here.
    _z: (),
}

impl PartialEq for Row {
    fn eq(&self, other: &Self) -> bool {
        // A stupid bug
        self.x == other.x && self.y == other.x
    }
}

We may use Row in BTreeMap or other collections and it may be hard to find the bug.

So how about introducing a new trait which is simple enough for users to implement?

Proposed solution

trait CmpKey {
    type K<'a>
    where
        Self: 'a;
    fn key(&self) -> Self::K<'_>;
}

Only one method need to be implemented!

impl CmpKey for Row {
    type K<'a> = (i32, i32);

    fn key(&self) -> Self::K<'_> {
        (self.x, self.y)
    }
}

GAT here is necessary for large type:

struct Row2 {
    x: String,
    y: i32,
    _z: (),
}

impl CmpKey for Row2 {
    type K<'a> = (&'a str, i32);

    fn key(&self) -> Self::K<'_> {
        (self.x.as_ref(), self.y)
    }
}

We can automatically implement all the four traits if users implement CmpKey.

impl<C> PartialEq for C
where
    C: CmpKey,
    for<'a> C::K<'a>: PartialEq<C::K<'a>>,
{
    fn eq(&self, other: &Self) -> bool {
        self.key().eq(&other.key())
    }
    
    fn ne(&self, other: &Self) -> bool {
        self.key().ne(&other.key())
    }
}

impl<C> Eq for C
where
    C: CmpKey,
    for<'a> C::K<'a>: Eq,
{}

impl<C> PartialOrd for C
where
    C: CmpKey,
    for<'a> C::K<'a>: PartialOrd<C::K<'a>>
{
    ...
}

impl<C> Ord for C
where
    C: CmpKey,
    for<'a> C::K<'a>: Ord
{
    ...
}

The trait can only be added in std lib due to the orphan rule.

9 Likes
2

If you introduce other of the existing blanket impls then there start to be compile issues, e.g. with the ref-delegating impl.

1 Like
3

I like the general idea. A few thoughts:

  • How do the other traits get implemented in terms of this? Blankets will give coherence errors. Is it a different derive?

  • Would it make sense to put this on a separate type so it could be used as a strategy? People keep asking for things like BinaryHeap<T, Reverse>, so if that used, say T: CmpKey<Reverse>, it might be handy.

  • Relatedly, I wonder if that GAT on this trait could be used to make new overloads of sort like sort_by_key, but in a way that has better behaviour with borrows.

3 Likes
4

The errors are very strange, is it avoidable?

5

I'm really not sure what's going on, I just had a suspicion that there could be coherence issues and decided to try it (it doesn't look like it caused a coherence issue, but maybe there is one just hiding behind whatever this recursion error seems to be).

1 Like
6

Alternatively could users control how the existing traits are derived by adding annotations to the struct definition? For instance, being able to add #[ignore_in_ordering] before a field that should not be examined as part of a comparison would have a similar effect. Crates like serde_derive do something like this. It is less expressive than what the original post proposed but also more succinct.

7

Moving the bound into CmpKey reveals a conflict.

8

Such macros already exist, e.g.,

It is less expressive

I think it is also somewhat more "expressive" because you can still define inconsistent PartialEq and PartialOrd. :rofl: So I like OP's idea because it provides a way to ensure consistency.

4 Likes
9

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