Why can't Rust downgrade my lifetime but instead complains about type mismatch?

Question

Consider the following struct:

struct State<'a> {
    parent: Option<&'a mut State<'a>>,
    // ...
}

My state stores some values that I might need later. Now I want to implement substates, i.e. allow the manipulation of those values in the substate without touching the parent state, but forwarding lookup of values not in the substate to its parent. Unfortunately, I need a mutable reference to every parent state at all times. I tried the following, but it doesn't work (Playground):

impl<'a> State<'a> {
    fn substate<'b>(&'b mut self) -> State<'b>
    where
        'a: 'b,
    {
        State::<'b> { parent: Some(self) }
    }
}

This gives the following error message:

error[E0308]: mismatched types
  --> src/main.rs:10:36
   |
10 |         State::<'b> { parent: Some(self) }
   |                                    ^^^^ lifetime mismatch
   |
   = note: expected mutable reference `&mut State<'b>`
              found mutable reference `&mut State<'a>`
note: the lifetime `'b` as defined here...
  --> src/main.rs:6:17
   |
6  |     fn substate<'b>(&'b mut self) -> State<'b>
   |                 ^^
note: ...does not necessarily outlive the lifetime `'a` as defined here
  --> src/main.rs:5:6
   |
5  | impl<'a> State<'a> {
   |      ^^

I don't understand why the compiler wants 'b to outlive 'a. In fact, the parent of a state will always live longer than its substate, so in my case the opposite is always true. So why can't the compiler just downgrade the "longer" lifetime 'a into the "shorter" lifetime 'b?

Answer 1

The function signature is unsound, and here's an example of why:

struct State<'a> {
    parent: Option<&'a mut State<'a>>,
}

impl<'a> State<'a> {
    fn substate<'b>(&'b mut self) -> State<'b>
    where
        'a: 'b,
    {
        /* implementation hidden but assumed to be implemented as described */
    }
}

// [root]
let mut root = State { parent: None };

// [foo] -> [root]
let mut foo = root.substate();

{
    // [bar] -> [foo] -> [root]
    let mut bar = foo.substate();

    // [bar] -> [foo] -> [tmp]
    let mut tmp = State { parent: None };
    bar.parent.as_mut().unwrap().parent = Some(&mut tmp);

    // tmp is dropped
}

// [foo] -> {uninitialized memory}
drop(foo);

(Full playground example)

The function signature allows us to store a reference inside foo here that lives shorter than foo itself does, so after we leave the block foo points to uninitialized memory, which is undefined behavior and bad.

If you run the above code with cargo miri, it will give this error, confirming that it is indeed undefined behavior:

error: Undefined Behavior: type validation failed at .parent.<enum-variant(Some)>.0: encountered a dangling reference (use-after-free)
  --> src/main.rs:40:10
   |
40 |     drop(foo);
   |          ^^^ type validation failed at .parent.<enum-variant(Some)>.0: encountered a dangling reference (use-after-free)
   |
   = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
   = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information

   = note: inside `main` at src/main.rs:40:10

note: some details are omitted, run with `MIRIFLAGS=-Zmiri-backtrace=full` for a verbose backtrace

error: aborting due to previous error

Answer 2

The error message on nightly is better (thanks to NLL stabilization that may be removed before hitting stable, but now it is there):

error: lifetime may not live long enough
  --> src/main.rs:10:31
   |
5  | impl<'a> State<'a> {
   |      -- lifetime `'a` defined here
6  |     fn substate<'b>(&'b mut self) -> State<'b>
   |                 -- lifetime `'b` defined here
...
10 |         State::<'b> { parent: Some(self) }
   |                               ^^^^^^^^^^ this usage requires that `'b` must outlive `'a`
   |
   = help: consider adding the following bound: `'b: 'a`
   = note: requirement occurs because of a mutable reference to `State<'_>`
   = note: mutable references are invariant over their type parameter
   = help: see <https://doc.rust-lang.org/nomicon/subtyping.html> for more information about variance

It is not enough that 'a outlives 'b, it should be exactly the same since it is invariant and invariant lifetimes cannot be shortened. Look at the link the compiler gives or the reference entry about variance to better understand what variance is and why mutable references are invariant.