Why does linking lifetimes matter only with mutable references?

A few days ago, there was a question where someone had a problem with linked lifetimes of a mutable reference to a type which contained borrowed data itself. The problem was supplying a reference to the type with a borrow of the same lifetime as the borrowed data inside the type. I tried to recreate the problem:

struct VecRef<'a>(&'a Vec<u8>);

struct VecRefRef<'a>(&'a mut VecRef<'a>);

fn main() {
    let v = vec![8u8, 9, 10];
    let mut ref_v = VecRef(&v);
    create(&mut ref_v);
}

fn create<'b, 'a>(r: &'b mut VecRef<'a>) {
    VecRefRef(r);
}

Example code

I explicitly annotated 'b here in create(). This does not compile:

error[E0623]: lifetime mismatch
  --> src/main.rs:12:15
   |
11 | fn create<'b, 'a>(r: &'b mut VecRef<'a>) {
   |                      ------------------
   |                      |
   |                      these two types are declared with different lifetimes...
12 |     VecRefRef(r);
   |               ^ ...but data from `r` flows into `r` here

The lifetime 'b is something like 'b < 'a and therefore violating the constraint in the VecRefRef<'a> to be of exactly the same lifetime as the referred to VecRef<'a>.

I linked the lifetime of the mutable reference with the borrowed data inside the VecRef<'a>:

fn create<'a>(r: &'a mut VecRef<'a>) {
    VecRefRef(r);
}

Now it works. But why? How was I even able to supply such a reference? The mutable reference r inside create() has the lifetime of VecRef<'a> not 'a. Why wasn't the problem pushed up to the calling side of the function create()?

I noticed another thing I did not understand. If I use an immutable reference inside the VecRefRef<'a> struct, it somehow does not matter any more when supplying a reference with a different lifetime of 'a:

struct VecRef<'a>(&'a Vec<u8>);

struct VecRefRef<'a>(&'a VecRef<'a>); // now an immutable reference

fn main() {
    let v = vec![8u8, 9, 10];
    let mut ref_v = VecRef(&v);
    create(&mut ref_v);
}

fn create<'b, 'a>(r: &'b mut VecRef<'a>) {
    VecRefRef(r);
}

Example code

This works as opposed to the first example where VecRefRef<'a> took a mutable reference to a VecRef<'a>. I know that mutable references have different aliasing rules (no aliasing at all) but what has that to do with the linked lifetimes here?

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:

1. What lifetimes are valid for 'y?

2. 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!

The mutable reference r inside create() has the lifetime of VecRef<'a> not 'a

This is a common source of confusion. Check this function definition:

fn identity<'a, T>(val: &'a T) -> &'a T { val }

In a function definition, 'a is a generic lifetime parameter, which parallels a generic type parameter (T). When the function is called, the caller decides what the concrete values of 'a and T will be. Let's look back at your main:

fn main() {
    let v = vec![8u8, 9, 10];   // 1 |-lifetime of `v`
    let mut ref_v = VecRef(&v); // 2 |  |-lifetime of `ref_v` 
    create(&mut ref_v);         // 3 |  |
}

v will live for the entire run of main (1-3), but ref_v only lives for the two final statements (2-3). Note that ref_v refers to a value that outlives it. If you then take a reference to ref_v, you have a reference to something that lives from (2-3) that itself has a reference to something that lives from (1-3).

Check out your fixed method:

fn create<'a>(r: &'a mut VecRef<'a>)

This says that for this function call, the reference to the VecRef and the reference it contains must be the same. There is a lifetime that can be picked that satisfies this — (2-3).

Note that your structure definition currently requires that the two lifetimes be the same. You could allow them to differ:

struct VecRefRef<'a, 'b: 'a>(&'a mut VecRef<'b>);
fn create<'a, 'b>(r: &'a mut VecRef<'b>)

Note that you have to use the syntax 'b: 'a to denote that the lifetime 'b will outlive 'a.

If I use an immutable reference [...], it somehow does not matter any more

This I'm less sure about. I believe that what is happening is that because you have an immutable borrow, it's OK for the compiler to reborrow at a smaller scope for you automatically. This allows the lifetimes to match. As you pointed out, a mutable reference cannot have any aliases, even ones with a smaller scope, so the compiler can't help in that case.