rustc weirdly assuming that type parameters have to be the same even when they're separate?

Question

I'm working on a library that requires as part of its functionality comparison between different types based on a key contained within them.

There is no way to require that the keys are the same in stable Rust (can't use equality bounds), so I'm using PartialOrd even though the keys are required to be Ord. Because of this requirement, it's safe to unwrap the result of partial_cmp() (it must be Some by specification).

However, with this bound, Rust seems to give up trying to resolve the associated type Key and whether it has PartialOrd with the other key, and just assumes that the types must be the same:

error[E0308]: mismatched types
  --> src/main.rs:60:29
   |
60 |     let order = compare(&a, &b);
   |                             ^^ expected struct `TypeA`, found struct `TypeB`
   |
   = note: expected type `&TypeA`
              found type `&TypeB`

In my much more complex example, where Keyed has another type parameter that determines the sort method (to allow for flexibility), the error I get looks like this:

can't compare `<types::test_helpers::TestObject as types::Keyed<'a, types::test_helpers::SortFirst>>::Key` with `<i32 as types::Keyed<'a, types::test_helpers::SortFirst>>::Key`

even though the associated type Key for both is just i32. This maybe provides more clarity into where the compiler is having a problem. The other errors before that seem to end up assuming that the types should be the same, just like in the little example I'm including.

Here is a minimal reproducible example (link):

use std::cmp::Ordering;

trait Keyed<'a> {
    type Key: 'a + Eq + Ord;

    fn key(&'a self) -> Self::Key;
}

#[derive(Debug, Clone)]
struct TypeA {
    key: (i32, i32),
    value: String,
}

impl<'a> Keyed<'a> for TypeA {
    type Key = (&'a i32, &'a i32);

    fn key(&'a self) -> (&'a i32, &'a i32) {
        (&self.key.0, &self.key.1)
    }
}

#[derive(Debug, Clone)]
struct TypeB {
    key_a: i32,
    key_b: i32,
    value: u64,
}

impl<'a> Keyed<'a> for TypeB {
    type Key = (&'a i32, &'a i32);

    fn key(&'a self) -> (&'a i32, &'a i32) {
        (&self.key_a, &self.key_b)
    }
}

fn compare<A, B>(a: &A, b: &B) -> Ordering
where
    for<'a> A: Keyed<'a>,
    for<'a> B: Keyed<'a>,
    for<'a> <A as Keyed<'a>>::Key: Ord,
    for<'a> <B as Keyed<'a>>::Key: Ord,
    for<'a> <A as Keyed<'a>>::Key: PartialOrd<<B as Keyed<'a>>::Key>,
{
    a.key().partial_cmp(&b.key()).unwrap()
}

fn main() {
    let a = TypeA {
        key: (3, 4),
        value: "Hello!".into(),
    };

    let b = TypeB {
        key_a: 3,
        key_b: 5,
        value: 9292,
    };

    let order = compare(&a, &b);

    println!("{:?}.key() = {:?}", a, a.key());
    println!("{:?}.key() = {:?}", b, b.key());
    println!("compare({:?}, {:?}) = {:?}", a, b, order);

    assert_eq!(order, Ordering::Less);
}

Anyone who has experience with how rustc does type calculus or who has had a similar problem have any clue what's going on here?

Answer 1

I believe I have found a workaround. By providing the following trait and being very specific about which types need to be comparable, you can avoid what I assume to be a Rust bug about evaluating HRTB associated types. It may be related to this issue as noted by @edwardw.

This trait does work fine with HRTBs as long as you use the exact types that you require to be comparable in your bounds. I'm thinking this workaround may be applicable to some other cases of that bug too.

pub trait KeyedCmp<'a, B>: Keyed<'a> where B: Keyed<'a> {
    fn keyed_cmp(&'a self, other: &'a B) -> Ordering;
}

impl<'a, A, B> KeyedCmp<'a, B> for A
    where A: Keyed<'a>,
          B: Keyed<'a>,
          <A as Keyed<'a>>::Key: PartialOrd<<B as Keyed<'a>>::Key> {

    fn keyed_cmp(&'a self, other: &'a B) -> Ordering {
        self.key().partial_cmp(&other.key()).unwrap()
    }
}