Why does linking lifetimes matter only with mutable references?

Question

Warning: I’m speaking from a level of expertise that I don’t really have. Given the length of this post, I’m probably wrong a large number of times.

TL;DR: Lifetimes of top-level values are covariant. Lifetimes of referenced values are invariant.

Introducing the problem

You can simplify your example significantly, by replacing VecRef<'a> with &'a mut T.

Further, one should remove main, since it’s more complete to talk about the general behaviour of a function than some particular lifetime instantiation.

Instead of VecRefRef‘s constructor, let’s use this function:

fn use_same_ref_ref<'c>(reference: &'c mut &'c mut ()) {}

Before we go further, it’s important to understand how lifetimes get implicitly cast in Rust. When one assigns a pointer to another explicitly annotated name, lifetime coercion happens. The most obvious thing this allows is shrinking the lifetime of the top-level pointer. As such, this is not a typical move.

Aside: I say “explicitly annotated” because in implicit cases like let x = y or fn f<T>(_: T) {}, reborrowing doesn’t seem to happen. It is not clear whether this is intended.

The full example is then

fn use_same_ref_ref<'c>(reference: &'c mut &'c mut ()) {}

fn use_ref_ref<'a, 'b>(reference: &'a mut &'b mut ()) {
    use_same_ref_ref(reference);
}

which gives the same error:

error[E0623]: lifetime mismatch
 --> src/main.rs:5:26
  |
4 |     fn use_ref_ref<'a, 'b>(reference: &'a mut &'b mut ()) {
  |                                       ------------------
  |                                       |
  |                                       these two types are declared with different lifetimes...
5 |         use_same_ref_ref(reference);
  |                          ^^^^^^^^^ ...but data from `reference` flows into `reference` here

A trivial fix

One can fix it by doing

fn use_same_ref_ref<'c>(reference: &'c mut &'c mut ()) {}

fn use_ref_ref<'a>(reference: &'a mut &'a mut ()) {
    use_same_ref_ref(reference);
}

since the signatures are now logically the same. However, what is not obvious is why

let mut val = ();
let mut reference = &mut val;
let ref_ref = &mut reference;

use_ref_ref(ref_ref);

is able to produce an &'a mut &'a mut ().

A less trivial fix

One can instead enforce 'a: 'b

fn use_same_ref_ref<'c>(reference: &'c mut &'c mut ()) {}

fn use_ref_ref<'a: 'b, 'b>(reference: &'a mut &'b mut ()) {
    use_same_ref_ref(reference);
}

This means that the lifetime of the outer reference is at least as large as the lifetime of the inner one.

It’s not obvious

why &'a mut &'b mut () is not castable to &'c mut &'c mut (), or
whether this is better than &'a mut &'a mut ().

I hope to answer these questions.

A non-fix

Asserting 'b: 'a does not fix the problem.

fn use_same_ref_ref<'c>(reference: &'c mut &'c mut ()) {}

fn use_ref_ref<'a, 'b: 'a>(reference: &'a mut &'b mut ()) {
    use_same_ref_ref(reference);
}

Another, more surprising fix

Making the outer reference immutable fixes the problem

fn use_same_ref_ref<'c>(reference: &'c &'c mut ()) {}

fn use_ref_ref<'a, 'b>(reference: &'a &'b mut ()) {
    use_same_ref_ref(reference);
}

And an even more surprising non-fix!

Making the inner reference immutable doesn’t help at all!

fn use_same_ref_ref<'c>(reference: &'c mut &'c ()) {}

fn use_ref_ref<'a, 'b>(reference: &'a mut &'b ()) {
    use_same_ref_ref(reference);
}

BUT WHY??!

And the reason is…

Hold on, first we cover variance

Two very important concepts in computer science are covariance and contravariance. I’m not going to use these names (I’ll be very explicit about which way I’m casting things) but those names are still very useful for searching the internet.

It’s very important to understand the concept of variance before you can understand the behaviour here. If you’ve taken a university course that covers this, or you can remember it from some other context, you’re in a good position. You might still appreciate the help linking the idea to lifetimes, though.

The simple case – a normal pointer

Consider some stack positions with a pointer:

    ║ Name      │ Type                │ Value
 ───╫───────────┼─────────────────────┼───────
  1 ║ val       │ i32                 │ -1
 ───╫───────────┼─────────────────────┼───────
  2 ║ reference │ &'x mut i32         │ 0x1

The stack grows downwards, so the reference stack position was created after val, and will be removed before val is.

Consider that you do

let new_ref = reference;

to get

    ║ Name      │ Type        │ Value  
 ───╫───────────┼─────────────┼─────── 
  1 ║ val       │ i32         │ -1     
 ───╫───────────┼─────────────┼─────── 
  2 ║ reference │ &'x mut i32 │ 0x1    
 ───╫───────────┼─────────────┼─────── 
  3 ║ new_ref   │ &'y mut i32 │ 0x1

What lifetimes are valid for 'y?

Consider the two mutable pointer operations:

Read
Write

Read prevents 'y from growing, because a 'x reference only guarantees the object stays alive during the scope of 'x. However, read does not prevent 'y from shrinking since any read when the pointed-to value is alive will result in a value independent of the lifetime 'y.

Write prevents 'y from growing also, since one cannot write to an invalidated pointer. However, write does not prevent 'y from shrinking since any write to the pointer copies the value in, which leaves it independent of the lifetime 'y.

The hard case – a pointer pointer

Consider some stack positions with a pointer pointer:

    ║ Name      │ Type                │ Value  
 ───╫───────────┼─────────────────────┼─────── 
  1 ║ val       │ i32                 │ -1     
 ───╫───────────┼─────────────────────┼─────── 
  2 ║ reference │ &'a mut i32         │ 0x1    
 ───╫───────────┼─────────────────────┼─────── 
  3 ║ ref_ref   │ &'x mut &'a mut i32 │ 0x2

Consider that you do

let new_ref_ref = ref_ref;

to get

    ║ Name        │ Type                │ Value  
 ───╫─────────────┼─────────────────────┼─────── 
  1 ║ val         │ i32                 │ -1     
 ───╫─────────────┼─────────────────────┼─────── 
  2 ║ reference   │ &'a mut i32         │ 0x1    
 ───╫─────────────┼─────────────────────┼─────── 
  3 ║ ref_ref     │ &'x mut &'a mut i32 │ 0x2    
 ───╫─────────────┼─────────────────────┼─────── 
  4 ║ new_ref_ref │ &'y mut &'b mut i32 │ 0x2

Now there are two questions:

What lifetimes are valid for 'y?
What lifetimes are valid for 'b?

Let’s first consider 'y with the two mutable pointer operations:

Read
Write

Read prevents 'y from growing, because a 'x reference only guarantees the object stays alive during the scope of 'x. However, read does not prevent 'y from shrinking since any read when the pointed-to value is alive will result in a value independent of the lifetime 'y.

Write prevents 'y from growing also, since one cannot write to an invalidated pointer. However, write does not prevent 'y from shrinking since any write to the pointer copies the value in, which leaves it independent of the lifetime 'y.

This is the same as before.

Now, consider `'b` with the two mutable pointer operations

Read prevents 'b from growing, since if one was to extract the inner pointer from the outer pointer you would be able to read it after 'a has expired.

Write prevents 'b from growing also, since if one was to extract the inner pointer from the outer pointer you would be able to write to it after 'a has expired.

Read and write together also prevent 'b from shrinking, because of this scenario:

let ref_ref: &'x mut &'a mut i32 = ...;

{
    // Has lifetime 'b, which is smaller than 'a
    let new_val: i32 = 123;

    // Shrink 'a to 'b
    let new_ref_ref: &'x mut &'b mut i32 = ref_ref;

    *new_ref_ref = &mut new_val;
}

// new_ref_ref is out of scope, so ref_ref is usable again
let ref_ref: &'a mut i32 = *ref_ref;
// Oops, we have an &'a mut i32 pointer to a dropped value!

Ergo, 'b cannot shrink and it cannot grow from 'a, so 'a == 'b exactly. This means &'y mut &'b mut i32 is invariant in the lifetime ‘b.

OK, does this solve our questions?

Remember the code?

fn use_same_ref_ref<'c>(reference: &'c mut &'c mut ()) {}

fn use_ref_ref<'a, 'b>(reference: &'a mut &'b mut ()) {
    use_same_ref_ref(reference);
}

When you call use_same_ref_ref, a cast is attempted

&'a mut &'b mut ()  →  &'c mut &'c mut ()

Now note that 'b == 'c because of our discussion about variance. Thus we are actually casting

&'a mut &'b mut ()  →  &'b mut &'b mut ()

The outer &'a can only be shrunk. In order to do this, the compiler needs to know

'a: 'b

The compiler does not know this, and so fails compilation.

What about our other examples?

The first was

fn use_same_ref_ref<'c>(reference: &'c mut &'c mut ()) {}

fn use_ref_ref<'a>(reference: &'a mut &'a mut ()) {
    use_same_ref_ref(reference);
}

Instead of 'a: 'b, the compiler now needs 'a: 'a, which is trivially true.

The second directly asserted 'a: 'b

fn use_same_ref_ref<'c>(reference: &'c mut &'c mut ()) {}

fn use_ref_ref<'a: 'b, 'b>(reference: &'a mut &'b mut ()) {
    use_same_ref_ref(reference);
}

The third asserted 'b: 'a

fn use_same_ref_ref<'c>(reference: &'c mut &'c mut ()) {}

fn use_ref_ref<'a, 'b: 'a>(reference: &'a mut &'b mut ()) {
    use_same_ref_ref(reference);
}

This does not work, because this is not the needed assertion.

What about immutability?

We had two cases here. The first was to make the outer reference immutable.

fn use_same_ref_ref<'c>(reference: &'c &'c mut ()) {}

fn use_ref_ref<'a, 'b>(reference: &'a &'b mut ()) {
    use_same_ref_ref(reference);
}

This one worked. Why?

Well, consider our problem with shrinking &'b from before:

Read and write together also prevent 'b from shrinking, because of this scenario:

let ref_ref: &'x mut &'a mut i32 = ...;

{
    // Has lifetime 'b, which is smaller than 'a
    let new_val: i32 = 123;

    // Shrink 'a to 'b
    let new_ref_ref: &'x mut &'b mut i32 = ref_ref;

    *new_ref_ref = &mut new_val;
}

// new_ref_ref is out of scope, so ref_ref is usable again
let ref_ref: &'a mut i32 = *ref_ref;
// Oops, we have an &'a mut i32 pointer to a dropped value!

Ergo, 'b cannot shrink and it cannot grow from 'a, so 'a == 'b exactly.

This can only happen because we can swap the inner reference for some new, insufficiently long lived reference. If we are not able to swap the reference, this is not a problem. Thus shrinking the lifetime of the inner reference is possible.

And the failing one?

Making the inner reference immutable does not help:

fn use_same_ref_ref<'c>(reference: &'c mut &'c ()) {}

fn use_ref_ref<'a, 'b>(reference: &'a mut &'b ()) {
    use_same_ref_ref(reference);
}

This makes sense when you consider that the problem mentioned before never involves any reads from the inner reference. In fact, here’s the problematic code modified to demonstrate that:

let ref_ref: &'x mut &'a i32 = ...;

{
    // Has lifetime 'b, which is smaller than 'a
    let new_val: i32 = 123;

    // Shrink 'a to 'b
    let new_ref_ref: &'x mut &'b i32 = ref_ref;

    *new_ref_ref = &new_val;
}

// new_ref_ref is out of scope, so ref_ref is usable again
let ref_ref: &'a i32 = *ref_ref;
// Oops, we have an &'a i32 pointer to a dropped value!

There was another question

It’s been quite long, but think back to:

One can instead enforce 'a: 'b
fn use_same_ref_ref<'c>(reference: &'c mut &'c mut ()) {}

fn use_ref_ref<'a: 'b, 'b>(reference: &'a mut &'b mut ()) {
    use_same_ref_ref(reference);
}
This means that the lifetime of the outer reference is at least as large as the lifetime of the inner one.

It’s not obvious

why &'a mut &'b mut () is not castable to &'c mut &'c mut (), or

whether this is better than &'a mut &'a mut ().

I hope to answer these questions.

We’ve answered the first bullet-pointed question, but what about the second? Does 'a: 'b permit more than 'a == 'b?

Consider some caller with type &'x mut &'y mut (). If 'x : 'y, then it will be automatically cast to &'y mut &'y mut (). Instead, if 'x == 'y, then 'x : 'y holds already! The difference is thus only important if you wish to return a type containing 'x to the caller, who is the only one able to distinguish the two. Since this is not the case here, the two are equivalent.

One more thing

If you write

let mut val = ();
let mut reference = &mut val;
let ref_ref = &mut reference;

use_ref_ref(ref_ref);

where use_ref_ref is defined

fn use_ref_ref<'a: 'b, 'b>(reference: &'a mut &'b mut ()) {
    use_same_ref_ref(reference);
}

how is the code able to enforce 'a: 'b? It looks on inspection like the opposite is true!

Well, remember that

let reference = &mut val;

is able to shrink its lifetime, since it’s the outer lifetime at this point. Thus, it can refer to a lifetime smaller than the real lifetime of val, even when the pointer is outside of that lifetime!