Why do the lifetimes on a trait object passed as an argument require Higher Ranked Trait Bounds but a struct doesn't?

Question

How are lifetimes handled when there is a trait object passed to a function?

struct Planet<T> {
    i: T,
}

trait Spinner<T> {
    fn spin(&self, value: T);
}

impl<T> Spinner<T> for Planet<T> {
    fn spin(&self, value: T) {}
}

// foo2 fails: Due to lifetime of local variable being less than 'a
fn foo2<'a>(t: &'a Spinner<&'a i32>) {
    let x: i32 = 10;
    t.spin(&x);
}

// foo1 passes: But here also the lifetime of local variable is less than 'a?
fn foo1<'a>(t: &'a Planet<&'a i32>) {
    let x: i32 = 10;
    t.spin(&x);
}

(Playground)

This code results in this error:

error[E0597]: `x` does not live long enough
  --> src/main.rs:16:17
   |
16 |         t.spin(&x);
   |                 ^ borrowed value does not live long enough
17 |     }
   |     - borrowed value only lives until here
   |
note: borrowed value must be valid for the lifetime 'a as defined on the function body at 14:5...
  --> src/main.rs:14:5
   |
14 |     fn foo2<'a>(t: &'a Spinner<&'a i32>) {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

The function signature of foo1 is nearly same as foo2. One receiving the reference to struct and the other a trait object.

I read this is where Higher Ranked Trait Bounds comes in. Modifying foo2 as foo2(t: &for<'a> Spinner<&'a i32>) compiles the code, but I don't understand why.

Why won't 'a shrink for x?

Citing the Nomicon:

How on earth are we supposed to express the lifetimes on F's trait bound? We need to provide some lifetime there, but the lifetime we care about can't be named until we enter the body of call! Also, that isn't some fixed lifetime; call works with any lifetime &self happens to have at that point.

Can this please be elaborated?

Lukas Kalbertodt Lukas Kalbertodt · Accepted Answer · 2018-06-20T12:02:47

In short: foo1 compiles because most types are variant over their generic parameters and the compiler can still chose a Spinner impl for t. foo2 doesn't compile because traits are invariant over their generic parameters and the Spinner impl is already fixed.

Some explanation

Let's take a look at a third version of foo:

fn foo3<'a>(t: &'a Planet<&'a i32>) {
    let x: i32 = 10;
    Spinner::<&'a i32>::spin(t, &x);
}

This results in the same error as your foo2. What's going in there?

By writing Spinner::<&'a i32>::spin, we force the compiler to use a specific implementation of the Spinner trait. And the signature of Spinner::<&'a i32>::spin is fn spin(&self, value: &'a i32). Period. The lifetime 'a is given by the caller; foo can't choose it. Thus we have to pass a reference that lives for at least 'a. That's why the compiler error happens.

So why does foo1 compile? As a reminder:

fn foo1<'a>(t: &'a Planet<&'a i32>) {
    let x: i32 = 10;
    t.spin(&x);
}

Here, the lifetime 'a is also given by the caller and cannot be chosen by foo1. But, foo1 can chose which impl of Spinner to use! Note that impl<T> Spinner<T> for Planet<T> basically defines infinitely many specific implementations (one for each T). So the compiler also knows that Planet<&'x i32> does implement Spinner<&'x i32> (where 'x is the specific lifetime of x in the function)!

Now the compiler just has to figure out if it can turn Planet<&'a i32> into Planet<&'x i32>. And yes, it can, because most types are variant over their generic parameters and thus Planet<&'a i32> is a subtype of Planet<&'x i32> if 'a is a subtype of 'x (which it is). So the compiler just "converts" t to Planet<&'x i32> and then the Spinner<&'x i32> impl can be used.

Fantastic! But now to the main part: why doesn't foo2 compile then? Again, as a reminder:

fn foo2<'a>(t: &'a Spinner<&'a i32>) {
    let x: i32 = 10;
    t.spin(&x);
}

Again, 'a is given by the caller and foo2 cannot chose it. Unfortunately, now we already have a specific implementation! Namely Spinner<&'a i32>. We can't just assume that the thing we were passed also implements Spinner<&'o i32> for any other lifetime 'o != 'a! Traits are invariant over their generic parameters.

In other words: we know we have something that can handle references which live at least as long as 'a. But we can't assume that the thing we were handed can also handle lifetimes shorter than 'a!

As an example:

struct Star;

impl Spinner<&'static i32> for Star {
    fn spin(&self, value: &'static i32) {}
}

static SUN: Star = Star;

foo2(&SUN);

In this example, 'a of foo2 is 'static. And in fact, Star implements Spinner only for 'static references to i32.

By the way: this is not specific to trait objects! Let's look at this fourth version of foo:

fn foo4<'a, S: Spinner<&'a i32>>(t: &'a S) {
    let x: i32 = 10;
    t.spin(&x);
}

Same error once again. The problem is, again, that the Spinner impl is already fixed! As with the trait object, we only know that S implements Spinner<&'a i32>, not necessarily more.

HRTB to the rescue?

Using higher ranked trait bounds resolves the issue:

fn foo2(t: &for<'a> Spinner<&'a i32>)

and

fn foo4<S: for<'a> Spinner<&'a i32>>(t: &S)

As it's hopefully clear from the explanation above, this works because we the specific impl of Spinner isn't fixed anymore! Instead, we again have infinitely many impls to choose from (one for each 'a). Thus we can choose the impl where 'a == 'x.

Why do the lifetimes on a trait object passed as an argument require Higher Ranked Trait Bounds but a struct doesn't?

1 Answers

Some explanation

HRTB to the rescue?