Reference does not live long enough in nested structure

Question

I'm creating a series of data structures containing mutable references to lower level structures. I've been fairly happily working with A, B, and C below but I've attempted to add a new layer D. A, B, C, D are actually the states of a state machine for protocol decoding, but I've deleted all of that here:

struct A {}

fn init_A() -> A {
    A {}
}

struct B<'l> {
    ed: &'l mut A,
}

fn init_B(mut e: &mut A) -> B {
    B { ed: e }
}

struct C<'l> {
    pd: &'l mut B<'l>,
}

fn init_C<'l>(mut p: &'l mut B<'l>) -> C<'l> {
    C { pd: p }
}

struct D<'lifetime> {
    sd: &'lifetime mut C<'lifetime>,
}

fn init_D<'l>(mut p: &'l mut C<'l>) -> D<'l> {
    D { sd: p }
}

fn main() {
    let mut a = init_A();
    let mut b = init_B(&mut a);
    let mut c = init_C(&mut b);

    // COMMENT OUT THE BELOW LINE FOR SUCCESSFUL COMPILE
    let mut d = init_D(&mut c);
}

I get an error:

error[E0597]: `c` does not live long enough
  --> src/main.rs:38:1
   |
37 |     let mut d = init_D(&mut c);
   |                             - borrow occurs here
38 | }
   | ^ `c` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

I'm completely lacking understanding of what is happening differently for D compared to C as far as lifetimes go: I don't understand what the lifetime mismatch is.

Answer 1

I'll address the point why the code in question doesn't work.

TL;DR: Invariance over the lifetimes of types C<'l> and D<'l> and the use of a single lifetime parameter ('l) for them cause variables of those types to keep their borrows for as long as variable b exists, but variable c (borrowed by d) is dropped before b.

The borrow checker is essentially a constraint solver. It searches for the shortest lifetimes⁰ which satisfy various constraints: a reference must not live longer than a value it references, lifetimes must obey constraints specified in function signatures and types, and lifetimes must obey variance rules¹.

0 — The shortest lifetime of a reference is the best because then the reference doesn't borrow a value for longer than necessary.

1 — Rust has a concept of variance which determines whether it is possible to use a value with longer lifetime in a place which expects a value of lesser lifetime. The Rustonomicon link explains it in detail.

The code below is a simplified version of the code in question and it fails with the same error: c does not live long enough. The blocks are marked with the lifetimes of variables. 'a is the lifetime of variable a and so on. Those lifetimes are determined by the structure of the code and they are fixed.

Lifetimes in type annotations (B(&'ar A) -> B<'ar> and so on) are variables. The borrow checker tries to find valid assignments of fixed lifetimes ('a, 'b, 'c, 'd) to these variables.

The comments below the let statements show the lifetime constraints which I'll explain below.

struct A;

struct B<'l>(&'l mut A);

struct C<'l>(&'l mut B<'l>);

struct D<'l>(&'l mut C<'l>);

fn main() {
    // lifetime 'a
    let mut a = A;
    { // lifetime 'b
        // B(&'r mut A) -> B<'ar>   
        let mut b = B(&mut a); 
        // 'r >= 'ar & 'r <= 'a
        { // lifetime 'c
            // C(&'br mut B<'ar>) -> C<'abr>  
            let mut c = C(&mut b); 
            // 'br <= 'b & 'abr = 'ar & 'br >= 'abr
            { // lifetime 'd
                // D(&'cr mut C<'abr>) -> D<'cabr> 
                let d = D(&mut c); 
                // 'cr <= 'c & 'cabr = 'abr & 'cr >= 'cabr
            }
        }
    }
}

First assignment

// B(&'r mut A) -> B<'ar>   
let mut b = B(&mut a); 
// 'r <= 'a & 'r >= 'ar

Reference to a cannot outlive a, hence 'r <= 'a.

&'r mut A is variant over 'r, so we can pass it into the type constructor of B<'ar> which expects &'ar mut A iff 'r >= 'ar.

Second assignment

 // C(&'br mut B<'ar>) -> C<'abr>  
 let mut c = C(&mut b); 
 // 'br <= 'b & 'abr = 'ar & 'br >= 'abr

Reference cannot outlive b ('br <= 'b), &mut B is invariant over B ('abr = 'ar), &'br mut B is variant over 'br ('br >= 'abr)

d's assignment is analogous to c.

Rust doesn't seem to consider lifetimes it hasn't encountered yet as possible assignments. The possible assignments for 'ar thus are 'a or 'b, the ones for 'abr are 'a, 'b, or 'c and so on.

This set of constraints boils down to 'ar = 'abr = 'cabr and the smallest allowed assignment for 'ar is 'b. Therefore the types of b, c, and d are B<'b>, C<'b>, D<'b>. That is, the variable d holds a reference to c for the lifetime 'b, but c is dropped at the end of the 'c lifetime.

If we remove d, then c still keeps b borrowed to the end of the lifetime 'b, but it isn't a problem because b doesn't outlive the lifetime 'b.

This description is still simplified. For example, while the type of c is C<'b>, c doesn't borrow b for the entire lifetime 'b, it borrows it for a part of 'b starting after definition of c, but it is something I don't have clear understanding yet.