Why does this mutable borrow live beyond its scope?

Question

I've encountered a confusing error about the use of a mutable and immutable borrow at the same time, after I expect the mutable borrow to end. I've done a lot of research on similar questions (1, 2, 3, 4, 5) which has led me to believe my problem has something to do with lexical lifetimes (though turning on the NLL feature and compiling on nightly doesn't change the result), I just have no idea what; my situation doesn't seem to fit into any of the scenarios of the other questions.

pub enum Chain<'a> {
    Root {
        value: String,
    },
    Child {
        parent: &'a mut Chain<'a>,
    },
}

impl Chain<'_> {
    pub fn get(&self) -> &String {
        match self {
            Chain::Root { ref value } => value,
            Chain::Child { ref parent } => parent.get(),
        }
    }

    pub fn get_mut(&mut self) -> &mut String {
        match self {
            Chain::Root { ref mut value } => value,
            Chain::Child { ref mut parent } => parent.get_mut(),
        }
    }
}

#[test]
fn test() {
    let mut root = Chain::Root { value: "foo".to_string() };

    {
        let mut child = Chain::Child { parent: &mut root };

        *child.get_mut() = "bar".to_string();
    } // I expect child's borrow to go out of scope here

    assert_eq!("bar".to_string(), *root.get());
}

playground

The error is:

error[E0502]: cannot borrow `root` as immutable because it is also borrowed as mutable
  --> example.rs:36:36
   |
31 |         let mut child = Chain::Child { parent: &mut root };
   |                                                --------- mutable borrow occurs here
...
36 |     assert_eq!("bar".to_string(), *root.get());
   |                                    ^^^^
   |                                    |
   |                                    immutable borrow occurs here
   |                                    mutable borrow later used here

I understand why an immutable borrow happens there, but I do not understand how a mutable borrow is used there. How can both be used at the same place? I'm hoping someone can explain what is happening and how I can avoid it.

Answer 1

In short, &'a mut Chain<'a> is extremely limiting and pervasive.

For an immutable reference &T<'a>, the compiler is allowed to shorten the lifetime of 'a when necessary to match other lifetimes or as part of NLL (this is not always the case, it depends on what T is). However, it cannot do so for mutable references &mut T<'a>, otherwise you could assign it a value with a shorter lifetime.

So when the compiler tries to reconcile the lifetimes when the reference and the parameter are linked &'a mut T<'a>, the lifetime of the reference is conceptually expanded to match the lifetime of the parameter. Which essentially means you've created a mutable borrow that will never be released.

Applying that knowledge to your question: creating a reference-based hierarchy is really only possible if the nested values are covariant over their lifetimes. Which excludes:

• mutable references
• trait objects
• structs with interior mutability

Refer to these variations on the playground to see how these don't quite work as expected.

See also:

• Why does linking lifetimes matter only with mutable references?
• How do I implement the Chain of Responsibility pattern using a chain of trait objects?
• What are the differences when getting an immutable reference from a mutable reference with self-linked lifetimes?

If you think you need these lifetimes to match due to other compiler errors, you may be creating a "self-referential struct"; see here why that doesn't really work.

---

For fun, I'll include a case where the Rust standard library does this sort of thing on purpose. The signature of std::thread::scope looks like:

pub fn scope<'env, F, T>(f: F) -> T
where
    F: for<'scope> FnOnce(&'scope Scope<'scope, 'env>) -> T

The Scope that is provided to the user-defined function intentionally has its lifetimes tied in a knot to ensure it is only used in intended ways. This is not always the case since structs may be covariant or contravariant over their generic types, but Scope is defined to be invariant. Also, the only function that can be called on it is .spawn() which intentionally takes &'scope self as the self-parameter as well, ensuring that the reference does not have a shorter lifetime than what is given by scope.

Internally, the standard library contains this documentation (source):

Invariance over 'scope, to make sure 'scope cannot shrink, which is necessary for soundness.

Without invariance, this would compile fine but be unsound:

std::thread::scope(|s| {
    s.spawn(|| {
        let a = String::from("abcd");
        s.spawn(|| println!("{a:?}")); // might run after `a` is dropped
    });
});

Even if the lifetime of the reference is invariant with respect to itself, this still avoids many problems above because it uses an immutable reference and interior-mutability. If the parameter to .spawn() required &'scope mut self, then this would not work and run into the same problems above when trying to spawn more than one thread.