Htydjtk

Consider the following toy example:

use std::cmp::Ordering;



pub trait SimpleOrder {

    fn key(&self) -> u32;

}



impl PartialOrd for dyn SimpleOrder {

    fn partial_cmp(&self, other: &dyn SimpleOrder) -> Option<Ordering> {

        Some(self.cmp(other))

    }

}



impl Ord for dyn SimpleOrder {

    fn cmp(&self, other: &dyn SimpleOrder) -> Ordering {

        self.key().cmp(&other.key())

    }

}



impl PartialEq for dyn SimpleOrder {

    fn eq(&self, other: &dyn SimpleOrder) -> bool {

        self.key() == other.key()

    }

}



impl Eq for SimpleOrder {}

This doesn't compile. It claims there is a lifetime issue in the implementation for partial_cmp:

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements

 --> src/main.rs:9:23

  |

9 |         Some(self.cmp(other))

  |                       ^^^^^

  |

note: first, the lifetime cannot outlive the anonymous lifetime #2 defined on the method body at 8:5...

 --> src/main.rs:8:5

  |

8 | /     fn partial_cmp(&self, other: &dyn SimpleOrder) -> Option<Ordering> {

9 | |         Some(self.cmp(other))

10| |     }

  | |_____^

note: ...so that the declared lifetime parameter bounds are satisfied

 --> src/main.rs:9:23

  |

9 |         Some(self.cmp(other))

  |                       ^^^^^

  = note: but, the lifetime must be valid for the static lifetime...

  = note: ...so that the types are compatible:

          expected std::cmp::Eq

             found std::cmp::Eq

I really don't understand this error. In particular "expected std::cmp::Eq found std::cmp::Eq" is puzzling.

If I inline the call manually it compiles fine:

fn partial_cmp(&self, other: &dyn SimpleOrder) -> Option<Ordering> {

    Some(self.key().cmp(&other.key()))

}

What's going on here?

Trait object types have an associated lifetime bound, but it can be omitted. A full trait object type is written dyn Trait + 'a (when behind a reference, parentheses must be added around it: &(dyn Trait + 'a)).

The problem is that when a lifetime bound is omitted, the compiler uses different rules to infer the lifetime based on the location where the trait object type is used.

First, we have:

impl PartialOrd for dyn SimpleOrder {

Here, the compiler implies + 'static. Lifetime parameters are never introduced on impl blocks (as of Rust 1.32.0).

Next, we have:

    fn partial_cmp(&self, other: &dyn SimpleOrder) -> Option<Ordering> {

The type of other is inferred to be &(dyn SimpleOrder + 'a), where 'a is an implicit lifetime parameter introduced on partial_cmp.

    fn partial_cmp<'a>(&self, other: &(dyn SimpleOrder + 'a)) -> Option<Ordering> {

So now we have that self has type &(dyn SimpleOrder + 'static) while other has type &(dyn SimpleOrder + 'a). What's the problem?

Indeed, cmp doesn't give any error, because its implementation doesn't require that the lifetime of the two trait objects be equal. Why does partial_cmp care, though?

Because partial_cmp is calling Ord::cmp. When type checking a call to a trait method, the compiler checks against the signature from the trait. Let's review that signature:

pub trait Ord: Eq + PartialOrd<Self> {

    fn cmp(&self, other: &Self) -> Ordering;

The trait requires that other be of type Self. That means that when partial_cmp calls cmp, it tries to pass a &(dyn SimpleOrder + 'a) to a parameter that expects a &(dyn SimpleOrder + 'static), because that's what Self is. This conversion is not valid, so the compiler gives an error.

So then, why is it valid to set the type of other to &(dyn SimpleOrder + 'a) when implementing Ord? Because &(dyn SimpleOrder + 'a) is a supertype of &(dyn SimpleOrder + 'static), and Rust lets you replace a parameter type with one of its supertypes when implementing a trait method (it makes the method strictly more general, even though it's apparently not used much in type checking).

In order to make your implementation as generic as possible, you could introduce a lifetime parameter on the impls:

use std::cmp::Ordering;



pub trait SimpleOrder {

    fn key(&self) -> u32;

}



impl<'a> PartialOrd for dyn SimpleOrder + 'a {

    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {

        Some(self.cmp(other))

    }

}



impl<'a> Ord for dyn SimpleOrder + 'a {

    fn cmp(&self, other: &Self) -> Ordering {

        self.key().cmp(&other.key())

    }

}



impl<'a> PartialEq for dyn SimpleOrder + 'a {

    fn eq(&self, other: &Self) -> bool {

        self.key() == other.key()

    }

}



impl<'a> Eq for dyn SimpleOrder + 'a {}