How can this instance seemingly outlive its own parameter lifetime?

Before I stumbled upon the code below, I was convinced that a lifetime in a type's lifetime parameter would always outlive its own instances. In other words, given a foo: Foo<'a>, then 'a would always outlive foo. Then I was introduced to this counter-argument code by @Luc Danton (Playground):

#[derive(Debug)]
struct Foo<'a>(std::marker::PhantomData<fn(&'a ())>);

fn hint<'a, Arg>(_: &'a Arg) -> Foo<'a> {
    Foo(std::marker::PhantomData)
}

fn check<'a>(_: &Foo<'a>, _: &'a ()) {}

fn main() {
    let outlived = ();
    let foo;

    {
        let shortlived = ();
        foo = hint(&shortlived);
        // error: `shortlived` does not live long enough
        //check(&foo, &shortlived);
    }

    check(&foo, &outlived);
}

Even though the foo created by hint appears to consider a lifetime that does not live for as long as itself, and a reference to it is passed to a function in a wider scope, the code compiles exactly as it is. Uncommenting the line stated in the code triggers a compilation error. Alternatively, changing Foo to the struct tuple (PhantomData<&'a ()>) also makes the code no longer compile with the same kind of error (Playground).

How is it valid Rust code? What is the reasoning of the compiler here?

Solution 1:

Despite your best intentions, your hint function may not have the effect you expect. But we have quite a bit of ground to cover before we can understand what's going on.

Let's begin with this:

fn ensure_equal<'z>(a: &'z (), b: &'z ()) {}

fn main() {
    let a = ();
    let b = ();
    ensure_equal(&a, &b);
}

OK, so in main, we defining two variables, a and b. They have distinct lifetimes, by virtue of being introduced by distinct let statements. ensure_equal requires two references with the same lifetime. And yet, this code compiles. Why?

That's because, given 'a: 'b (read: 'a outlives 'b), &'a T is a subtype of &'b T.

Let's say the lifetime of a is 'a and the lifetime of b is 'b. It's a fact that 'a: 'b, because a is introduced first. On the call to ensure_equal, the arguments are typed &'a () and &'b (), respectively¹. There's a type mismatch here, because 'a and 'b are not the same lifetime. But the compiler doesn't give up yet! It knows that &'a () is a subtype of &'b (). In other words, a &'a () is a &'b (). The compiler will therefore coerce the expression &a to type &'b (), so that both arguments are typed &'b (). This resolves the type mismatch.

If you're confused by the application of "subtypes" with lifetimes, then let me rephrase this example in Java terms. Let's replace &'a () with Programmer and &'b () with Person. Now let's say that Programmer is derived from Person: Programmer is therefore a subtype of Person. That means that we can take a variable of type Programmer and pass it as an argument to a function that expects a parameter of type Person. That's why the following code will successfully compile: the compiler will resolve T as Person for the call in main.

class Person {}
class Programmer extends Person {}

class Main {
    private static <T> void ensureSameType(T a, T b) {}

    public static void main(String[] args) {
        Programmer a = null;
        Person b = null;
        ensureSameType(a, b);
    }
}

Perhaps the non-intuitive aspect of this subtyping relation is that the longer lifetime is a subtype of the shorter lifetime. But think of it this way: in Java, it's safe to pretend that a Programmer is a Person, but you can't assume that a Person is a Programmer. Likewise, it's safe to pretend that a variable has a shorter lifetime, but you can't assume that a variable with some known lifetime actually has a longer lifetime. After all, the whole point of lifetimes in Rust is to ensure that you don't access objects beyond their actual lifetime.

Now, let's talk about variance. What's that?

Variance is a property that type constructors have with respect to their arguments. A type constructor in Rust is a generic type with unbound arguments. For instance Vec is a type constructor that takes a T and returns a Vec<T>. & and &mut are type constructors that take two inputs: a lifetime, and a type to point to.

Normally, you would expect all elements of a Vec<T> to have the same type (and we're not talking about trait objects here). But variance lets us cheat with that.

&'a T is covariant over 'a and T. That means that wherever we see &'a T in a type argument, we can substitute it with a subtype of &'a T. Let's see how it works out:

fn main() {
    let a = ();
    let b = ();
    let v = vec![&a, &b];
}

We've already established that a and b have different lifetimes, and that the expressions &a and &b don't have the same type¹. So why can we make a Vec out of these? The reasoning is the same as above, so I'll summarize: &a is coerced to &'b (), so that the type of v is Vec<&'b ()>.

fn(T) is a special case in Rust when it comes to variance. fn(T) is contravariant over T. Let's build a Vec of functions!

fn foo(_: &'static ()) {}
fn bar<'a>(_: &'a ()) {}

fn quux<'a>() {
    let v = vec![
        foo as fn(&'static ()),
        bar as fn(&'a ()),
    ];
}

fn main() {
    quux();
}

This compiles. But what's the type of v in quux? Is it Vec<fn(&'static ())> or Vec<fn(&'a ())>?

I'll give you a hint:

fn foo(_: &'static ()) {}
fn bar<'a>(_: &'a ()) {}

fn quux<'a>(a: &'a ()) {
    let v = vec![
        foo as fn(&'static ()),
        bar as fn(&'a ()),
    ];
    v[0](a);
}

fn main() {
    quux(&());
}

This doesn't compile. Here are the compiler messages:

error[E0495]: cannot infer an appropriate lifetime due to conflicting requirements
 --> <anon>:5:13
  |
5 |       let v = vec![
  |  _____________^ starting here...
6 | |         foo as fn(&'static ()),
7 | |         bar as fn(&'a ()),
8 | |     ];
  | |_____^ ...ending here
  |
note: first, the lifetime cannot outlive the lifetime 'a as defined on the body at 4:23...
 --> <anon>:4:24
  |
4 |   fn quux<'a>(a: &'a ()) {
  |  ________________________^ starting here...
5 | |     let v = vec![
6 | |         foo as fn(&'static ()),
7 | |         bar as fn(&'a ()),
8 | |     ];
9 | |     v[0](a);
10| | }
  | |_^ ...ending here
note: ...so that reference does not outlive borrowed content
 --> <anon>:9:10
  |
9 |     v[0](a);
  |          ^
  = note: but, the lifetime must be valid for the static lifetime...
note: ...so that types are compatible (expected fn(&()), found fn(&'static ()))
 --> <anon>:5:13
  |
5 |       let v = vec![
  |  _____________^ starting here...
6 | |         foo as fn(&'static ()),
7 | |         bar as fn(&'a ()),
8 | |     ];
  | |_____^ ...ending here
  = note: this error originates in a macro outside of the current crate

error: aborting due to previous error

We're trying to call one of the functions in the vector with a &'a () argument. But v[0] expects a &'static (), and there's no guarantee that 'a is 'static, so this is invalid. We can therefore conclude that the type of v is Vec<fn(&'static ())>. As you can see, contravariance is the opposite of covariance: we can replace a short lifetime with a longer one.

Whew, now back to your question. First, let's see what the compiler makes out of the call to hint. hint has the following signature:

fn hint<'a, Arg>(_: &'a Arg) -> Foo<'a>

Foo is contravariant over 'a because Foo wraps a fn (or rather, pretends to, thanks to the PhantomData, but that doesn't make a difference when we talk about variance; both have the same effect), fn(T) is contravariant over T and that T here is &'a ().

When the compiler tries to resolve the call to hint, it only considers shortlived's lifetime. Therefore, hint returns a Foo with shortlived's lifetime. But when we try to assign that to the variable foo, we have a problem: a lifetime parameter on a type always outlives the type itself, and shortlived's lifetime doesn't outlive foo's lifetime, so clearly, we can't use that type for foo. If Foo was covariant over 'a, that would be the end of it and you'd get an error. But Foo is contravariant over 'a, so we can replace shortlived's lifetime with a larger lifetime. That lifetime can be any lifetime that outlives foo's lifetime. Note that "outlives" is not the same as "strictly outlives": the difference is that 'a: 'a ('a outlives 'a) is true, but 'a strictly outlives 'a is false (i.e. a lifetime is said to outlive itself, but it doesn't strictly outlive itself). Therefore, we might end up with foo having type Foo<'a> where 'a is exactly the lifetime of foo itself.

Now let's look at check(&foo, &outlived); (that's the second one). This one compiles because &outlived is coerced so that the lifetime is shortened to match foo's lifetime. That's valid because outlived has a longer lifetime than foo, and check's second argument is covariant over 'a because it's a reference.

Why doesn't check(&foo, &shortlived); compile? foo has a longer lifetime than &shortlived. check's second argument is covariant over 'a, but its first argument is contravariant over 'a, because Foo<'a> is contravariant. That is, both arguments are trying to pull 'a in opposite directions for this call: &foo is trying to enlarge &shortlived's lifetime (which is illegal), while &shortlived is trying to shorten &foo's lifetime (which is also illegal). There is no lifetime that will unify these two variables, therefore the call is invalid.

¹ That might actually be a simplification. I believe that the lifetime parameter of a reference actually represents the region in which the borrow is active, rather than the lifetime of the reference. In this example, both borrows would be active for the statement that contains the call to ensure_equal, so they would have the same type. But if you split the borrows to separate let statements, the code still works, so the explanation is still valid. That said, for a borrow to be valid, the referent must outlive the borrow's region, so when I'm thinking of lifetime parameters, I only care about the referent's lifetime and I consider borrows separately.

Solution 2:

Another way of explaining this is to notice that Foo doesn't actually hold a reference to anything with a lifetime of 'a. Rather, it holds a function that accepts a reference with lifetime 'a.

You can construct this same behaviour with an actual function instead of PhantomData. And you can even call that function:

struct Foo<'a>(fn(&'a ()));

fn hint<'a, Arg>(_: &'a Arg) -> Foo<'a> {
    fn bar<'a, T: Debug>(value: &'a T) {
        println!("The value is {:?}", value);
    }
    Foo(bar)
}

fn main() {
    let outlived = ();
    let foo;
    {
        let shortlived = ();
        // &shortlived is borrowed by hint() but NOT stored in foo
        foo = hint(&shortlived);
    }
    foo.0(&outlived);
}

As Francis explained in his excellent answer, the type of outlived is a subtype of the type of shortlived because its lifetime is longer. Therefore, the function inside foo can accept it because it can be coerced to shortlived's (shorter) lifetime.