Can I coerce a lifetime parameter to a shorter lifetime (soundly) even in the presence of `&mut T`?

Question

I'm trying to make a tree with parent pointers in Rust. A method on the node struct is giving me lifetime issues. Here's a minimal example, with lifetimes written explicitly so that I can understand them:

use core::mem::transmute;

pub struct LogNode<'n>(Option<&'n mut LogNode<'n>>);

impl<'n> LogNode<'n> {
    pub fn child<'a>(self: &'a mut LogNode<'n>) -> LogNode<'a> {
        LogNode(Some(self))
    }

    pub fn transmuted_child<'a>(self: &'a mut LogNode<'n>) -> LogNode<'a> {
        unsafe {
            LogNode(Some(
                transmute::<&'a mut LogNode<'n>, &'a mut LogNode<'a>>(self)
            ))
        }
    }
}

(Playground link)

Rust complains about child...

error[E0495]: cannot infer an appropriate lifetime for lifetime parameter 'n due to conflicting requirements

...but it's fine with transmuted_child.

I think I understand why child won't compile: the self parameter's type is &'a mut LogNode<'n> but the child node contains an &'a mut LogNode<'a>, and Rust doesn't want to coerce LogNode<'n> to LogNode<'a>. If I change the mutable references to shared references, it compiles fine, so it sounds like the mutable references are a problem specifically because &mut T is invariant over T (whereas &T is covariant). I guess the mutable reference in LogNode bubbles up to make LogNode itself invariant over its lifetime parameter.

But I don't understand why that's true—intuitively it feels like it's perfectly sound to take LogNode<'n> and shorten its contents' lifetimes by turning it into a LogNode<'a>. Since no lifetime is made longer, no value can be accessed past its lifetime, and I can't think of any other unsound behavior that could happen.

transmuted_child avoids the lifetime issue because it sidesteps the borrow checker, but I don't know if the use of unsafe Rust is sound, and even if it is, I'd prefer to use safe Rust if possible. Can I?

I can think of three possible answers to this question:

1. child can be implemented entirely in safe Rust, and here's how.
2. child cannot be implemented entirely in safe Rust, but transmuted_child is sound.
3. child cannot be implemented entirely in safe Rust, and transmuted_child is unsound.

Edit 1: Fixed a claim that &mut T is invariant over the lifetime of the reference. (Wasn't reading the nomicon right.)

Edit 2: Fixed my first edit summary.

Answer 1

The answer is #3: child cannot be implemented in safe Rust, and transmuted_child is unsound¹. Here's a program that uses transmuted_child (and no other unsafe code) to cause a segfault:

fn oops(arg: &mut LogNode<'static>) {
    let mut short = LogNode(None);
    let mut child = arg.transmuted_child();
    if let Some(ref mut arg) = child.0 {
        arg.0 = Some(&mut short);
    }
}

fn main() {
    let mut node = LogNode(None);
    oops(&mut node);
    println!("{:?}", node);
}

short is a short-lived local variable, but since you can use transmuted_child to shorten the lifetime parameter of the LogNode, you can stuff a reference to short inside a LogNode that should be 'static. When oops returns, the reference is no longer valid, and trying to access it causes undefined behavior (segfaulting, for me).

---

¹ There is some subtlety to this. It is true that transmuted_child itself does not have undefined behavior, but because it makes other code such as oops possible, calling or exposing it may make your interface unsound. To expose this function as part of a safe API, you must take great care to not expose other functionality that would let a user write something like oops. If you cannot do that, and you cannot avoid writing transmuted_child, it should be made an unsafe fn.

Answer 2

To understand why the immutable version works and the mutable version is unsound (as written), we have to discuss subtyping and variance.

Rust mostly doesn't have subtyping. Values typically have a unique type. One place where Rust does have subtyping, however, is with lifetimes. If 'a: 'b (read 'a is longer than 'b), then, for example, &'a T is a subtype of &'b T, intuitively because longer lifetimes can be treated as if they were shorter.

Variance is how subtyping propagates. If A is a subtype of B, and we have a generic type Foo<T>, Foo<A> might be a subtype of Foo<B>, vice versa, or neither. In the first case, where the direction of subtyping stays the same, Foo<T> is said to be covariant with respect to T. In the second case, where the direction reverses, it's said to be contravariant, and in the third case, it's said to be invariant.

For this case, the relevant types are &'a T and &'a mut T. Both are covariant in 'a (so references with longer lifetimes can be coerced to references with shorter lifetimes). &'a T is covariant in T, but &'a mut T is invariant in T.

The reason for this is explained in the Nomicon (linked above), so I'll just show you the (somewhat simplified) example given there. Trentcl's code is a working example of what goes wrong if &'a mut T is covariant in T.

fn evil_feeder(pet: &mut Animal) {
    let spike: Dog = ...;

    // `pet` is an Animal, and Dog is a subtype of Animal,
    // so this should be fine, right..?
    *pet = spike;
}

fn main() {
    let mut mr_snuggles: Cat = ...;
    evil_feeder(&mut mr_snuggles);  // Replaces mr_snuggles with a Dog
    mr_snuggles.meow();             // OH NO, MEOWING DOG!
}

---

So why does the immutable version of child work, but not the mutable version? In the immutable version, LogNode contains an immutable reference to a LogNode, so by covariance in both the lifetime and the type parameter, LogNode is covariant in its lifetime parameter. If 'a: 'b, then LogNode<'a> is a subtype of LogNode<'b>.

We have self: &'a LogNode<'n>, which implies 'n: 'a (otherwise this borrow would outlast the data in LogNode<'n>). Thus, since LogNode is covariant, LogNode<'n> is a subtype of LogNode<'a>. Furthermore, covariance in immutable references again allows &'a LogNode<'n> to be a subtype of &'a LogNode<'a>. Thus, self: &'a LogNode<'n> can be coerced to &'a LogNode<'a> as needed for the return type in child.

For the mutable version, LogNode<'n> isn't covariant in 'n. The variance here comes down to the variance of &'n mut LogNode<'n>. But since there's a lifetime in the "T" part of the mutable reference here, the invariance of mutable references (in T) implies that this must also be invariant.

This all combines to show that self: &'a mut LogNode<'n> can't be coerced to &'a mut LogNode<'a>. So the function doesn't compile.

---

One solution to this is to add the lifetime bound 'a: 'n, though as noted above, we already have 'n: 'a, so this forces the two lifetimes to be equal. That may or may not work with the rest of your code, so take it with a grain of salt.