Does lifetime elision work for methods in trait impls?

Question

With this question I am looking for feedback from people who have more knowledge in this area. I am by no means an expert. So I might as well ask my question upfront: Is my reasoning correct here?

The problem

Based on the answer to a question here on SO, I was confused to see the lifetime elided in the implementation of a trait method:

impl<'a, 'b, T> PartialEq<RefEquality<'b, T>> for RefEquality<'a, T> {
    fn eq(&self, other: &RefEquality<T>) -> bool {
        self.0 as *const T == other.0 as *const T
    }
}

Here, in the method signature the lifetime 'b was omitted on the type of other. This works and is correct. I expected it to be &RefEquality<'b, T> for the type to be correct. After all, the 'b here is essential: The lifetime has to be different from 'a. If not, it would be too restrictive: The implementation would only work for another RefEquality<T> with the same lifetime as Self. So those are obviously different semantics. How can the compiler infer the correct lifetime?

Lifetime elision takes care of it

Lifetimes on function signatures can be elided but they cannot be elided on impl blocks. There, the types have to be fully specified which includes naming lifetimes.

On the eq() method on the other hand, I am able to elide the lifetime in the type annotation of other. In fact, the compiler then inserts an arbitrary lifetime for it which is obviously different from 'a. That is the reason why this works while also keeping the same semantics:

impl<'a, 'b, T> PartialEq<RefEquality<'b, T>> for RefEquality<'a, T> {
    fn eq<'c>(&self, other: &RefEquality<'c, T>) -> bool {
        self.0 as *const T == other.0 as *const T
    }
}

Here, I introduced an arbitrary lifetime 'c for the method, which is basically the same the compiler does in case of lifetime elision.

Naming a lifetime 'b in my trait impl just stated that it has to be different from 'a (I also not linked them in any way). It follows logically, that this does not work:

impl<'a, 'b, T> PartialEq<RefEquality<'b, T>> for RefEquality<'a, T> {
    fn eq(&self, other: &RefEquality<'a, T>) -> bool {
        self.0 as *const T == other.0 as *const T
    }
}

I said in on the impl the types would be different (based on their lifetimes) but now the actual eq() implementation says they are the same. This results in a type error as expected.

What if I want the lifetimes to be equal? Can I still use lifetime elision in this case, or will the compiler insert an arbitrary lifetime and report a type error? It turns out, the inference works correctly here as well:

impl<'a, T> PartialEq<RefEquality<'a, T>> for RefEquality<'a, T> {
    fn eq(&self, other: &RefEquality<T>) -> bool {
        self.0 as *const T == other.0 as *const T
    }
}

The elided lifetime will be inferred to be 'a, keeping the desired semantics that both RefEquality<T> types have to have the same lifetime.

Answer 1

Let’s look at rustc’s process to determine if a provided impl method corresponds to the signature declared in the trait.

The location in the code is compare_impl_method in librustc_typeck/check/compare_method.rs, and it's well commented, however even the comments are hard to use for those that are not compiler hackers.

I’m not a compiler developer, so the following is based on my rust experience and interpretation!

The declaration in the trait corresponds to a particular function type, and the definition in the impl block is parsed to its own function type.

For this question I think only the conclusion of the type checking is important:

• “Is the impl function a subtype of the trait function?”

Subtyping I

If S is a subtype of T, the subtyping relation is often written S <: T, to mean that any term of type S can be safely used in a context where a term of type T is expected.

It sounds reasonable. We want the impl block to define a function that can be used safely as if it is the function declared in the trait.

Case 1

This is the elided lifetime case, but spelled out explicitly. I have replaced all method bodies with just a panic to emphasize that function signature checking is completely uninfluenced by the body of the function.

impl<'a, 'b, T> PartialEq<RefEquality<'b, T>> for RefEquality<'a, T> {
    fn eq<'c>(&self, other: &RefEquality<'c, T>) -> bool {
        panic!()
    }
}

The trait expects a function of type:

fn(&RefEquality<'a, T>, &RefEquality<'b, T>)

You provide a function of type:

fn<'c>(&RefEquality<'a, T>, &RefEquality<'c, T>)

It looks like the provided impl is “more general” than required. With 'c == 'b, then the function is of equal type.

It is a subtype of the expected type, because we can always use the fn<'c> version safely in its place.

Case 2

For your second example, that didn't compile:

impl<'a, 'b, T> PartialEq<RefEquality<'b, T>> for RefEquality<'a, T> {
    fn eq(&self, other: &RefEquality<'a, T>) -> bool {
        panic!()
    }
}

You can add a bound 'b: 'a ('b outlives 'a), and then it's ok:

impl<'a, 'b: 'a, T> PartialEq<RefEquality<'b, T>> for RefEquality<'a, T> {
    fn eq(&self, other: &RefEquality<'a, T>) -> bool {
        panic!()
    }
}

The trait expects a function of type:

fn(&RefEquality<'a, T>, &RefEquality<'b, T>)

You provide a function of type:

fn(&RefEquality<'a, T>, &RefEquality<'a, T>)

I think it seems logical that they are compatible if 'b outlives 'a, but let's look at it calmly.

Let's remove the constant factors:

The trait expects a function of type:

fn(Ref<'b>)

You provide a function of type:

fn(Ref<'a>)

We also have the information that where 'b: 'a. How can we see that these are compatible?

Subtyping II: Attack of the Variances

Subtyping: is it safe to use X instead of Y?

Variance: if X is a subtype of Y, what about Foo<X> and Foo<Y>?

See also Wikipedia, Rustonomicon on variance.

The subtyping definition for lifetimes is:

'x <: 'y means that 'x is longer than 'y.

Let's practice subtyping and variance with references.

When is it safe to use &'x i32 instead of &'y i32?

It is when 'x is longer lived than 'y, then it's safe to replace. 'x living longer than 'y implies that &'x i32 is a subtype of &'y i32:

'x <: 'y => &'x i32 <: &'y i32

The subtyping relation is propagated in the same direction, and this is called covariance; &'a i32 is covariant in the 'a parameter.

The variance behavior of a function instead is this:

X <: Y => fn(Y) <: fn(X)

Functions behave in the opposite way of their argument types. This is contravariance, logically “contra” since it's the opposite direction.

Computation

For this question we assume that Ref<'a> behaves as if it contains a &'a reference, and that it has the same variance as &'a itself has.

We were given the bound where 'b: 'a, which means:

'b <: 'a

Use the covariance rule for references and Ref:

'b <: 'a => Ref<'b> <: Ref<'a>

Use the contravariant rule for functions^**

Ref<'b> <: Ref<'a> => fn(Ref<'a>) <: fn(Ref<'b>)

And this was the question that rustc asked, is the impl function a subtype of the trait function. It is!

** ^{w.r.t. function arguments}:

What if I want the lifetimes to be equal?

If your goal is just to define PartialEq for the equal lifetime case, then yes, the elided lifetime case is fine. It provides a more general function in the impl, but the type checker determines that it is compatible.

You can also change the variance of your RefEquality type with respect to the lifetime parameter.

If you want a RefEquality<'a, T> is only subtype compatible with exactly the same lifetime, that's called invariance.

There's a primitive you can use that has invariance, std::cell::Cell<T>. Cell<T> is invariant in the T parameter.

The usual way to accomplish this is a PhantomData member:

struct RefEquality<'a, T: 'a> {
    ptr: &'a T,
    marker: PhantomData<Cell<&'a ()>>,
}

If you want to see an application of invariance, check out the crossbeam crate and how Scope<'a> being invariant in the 'a parameter is the cornerstone in its peculiar borrow rules for safe scoped threads.