How does Rust know that a lifetime may propagate into a type or not?

In the below code, the compiler knows that &str may theoretically get stored in B and C (theoretically; if it were &Option<str> and not &Option<()>).
It somehow detects the interior mutability of RefCell and Mutex and marks &mut x as still being active.

It is also knows that it can't get stored in A or D.

How is this possible?
How would I do the same for MyContainer?

use std::{cell::RefCell, sync::Mutex};

#[derive(Default)]
struct A<'a>(Option<&'a ()>);

impl<'a> A<'a> {
    fn x(&self, _x: &'a mut str) {}
}

#[derive(Default)]
struct B<'a>(RefCell<Option<&'a ()>>);

impl<'a> B<'a> {
    fn x(&self, _x: &'a mut str) {}
}

#[derive(Default)]
struct C<'a>(Mutex<Option<&'a ()>>);

impl<'a> C<'a> {
    fn x(&self, _x: &'a mut str) {}
}

#[derive(Default)]
struct MyContainer<T> {
    t: T,
}

#[derive(Default)]
struct D<'a>(MyContainer<Option<&'a ()>>);

impl<'a> D<'a> {
    fn x(&self, _x: &'a mut str) {}
}

fn test() {
    {
        let mut x = String::new();
        let a: A<'_> = Default::default();
        a.x(&mut x);
        a.x(&mut x); // OK
    }

    {
        let mut x = String::new();
        let b: B<'_> = Default::default();
        b.x(&mut x);
        b.x(&mut x); // Error: x already mutably borrowed in previous line
    }

    {
        let mut x = String::new();
        let c: C<'_> = Default::default();
        c.x(&mut x);
        c.x(&mut x); // Error: x already mutably borrowed in previous line
    }

    {
        let mut x = String::new();
        let d: D<'_> = Default::default();
        d.x(&mut x);
        d.x(&mut x); // OK
    }
}

The magic sauce is the std::cell::UnsafeCell lang-item. Mutexes and RefCells contain an instance of that type. Accordingly, this errors on line 62, too.

It's about Subtyping and Variance.

&'a mut T is covariant over 'a, and A<'a> is covariant over 'a, so it means you can pass &'long mut T and A<'long> where &'short mut T and A<'short> is needed.

For this snippet

{
    let mut x = String::new();
    let a: A<'static> = A(None);
    a.x(&mut x);
    a.x(&mut x);
    drop(x); let b: A<'static> = a; dbg!(b.0);
}
impl<'any> A<'any> {
    fn x(&self, _x: &'any mut str) {}
}

a.x(&mut x) desugars to A::x(&A<'any>, &'any mut str):

  • &mut x ⇒ &'short mut x
  • A<'static> ⇒ A<'short>
  • both can be reached, so code is pass

Note a doesn't need to be A<'static>:

// Ok
{
    let mut x = String::new();
    let y = String::new();
    let a: A<'_> = A(Some(&y));
    a.x(&mut x);
    a.x(&mut x);
    drop(x);
    drop(a);
}
// Ok
{
    let mut x = String::new();
    let y = String::new();
    let a: A<'_> = A(Some(&y));
    a.x(&mut x);
    a.x(&mut x);
    drop(a);
    drop(x);
}

For your custom type

struct MyContainer<T> {
    t: T,
}

it works the same way because MyContainer<Option<&'a ()>> is covariant over 'a according to the link I give above.

how is variance determined for types that you define? A struct, informally speaking, inherits the variance of its fields. If a struct MyType has a generic argument A that is used in a field a, then MyType's variance over A is exactly a's variance over A.

However if A is used in multiple fields:

  • If all uses of A are covariant, then MyType is covariant over A
  • If all uses of A are contravariant, then MyType is contravariant over A
  • Otherwise, MyType is invariant over A

But &mut T / UnsafeCell<T> e.t.c.[1] are invariant over T, which means you must pass the exact 'lifetime where 'lifetime is needed.

struct B<'a>(RefCell<Option<&'a ()>>);

impl<'given> B<'given> {
    fn x(&self, _x: &'given mut str) {} // fn x(&B<'given>, _x: &'given mut str)
}

{
    let mut x = String::new();
    let b: B<'_> = Default::default();
    b.x(&mut x);
    b.x(&mut x); // Error: cannot borrow `x` as mutable more than once at a time
}

b.x(&mut x) desugars to B::x(&B<'given>, _x: &'given mut str):

  • &mut x ⇒ &'short mut x
  • B<'_> is inferred as B<'short>
  • so code is pass at the first occurence of b.x()
  • but this means you must hold the first &mut x alive as long as you use b
{
    let mut x = String::new();
    let b: B<'_> = Default::default();
    b.x(&mut x);
    &b; // ok
    &x; // ok: you don't use b anymore, so the lifetime of `&mut x` and `b` stop before you use `&x`
}
{
    let mut x = String::new();
    let b: B<'_> = Default::default();
    b.x(&mut x);
    &b; // ok
    &x; // error: cannot borrow `x` as immutable because it is also borrowed as mutable
    drop(b); // Using b will extend the lifetime of `&mut x`, thus `&mut x` and `&x` overlaps
}

{ // in your case
    let mut x = String::new();
    let b: B<'_> = Default::default();
    b.x(&mut x);
    b.x(&mut x); // Using b will extend the lifetime of `&mut x`, but you can't have two `&mut x` and `&mut x` at the same point in Rust

error[E0499]: cannot borrow `x` as mutable more than once at a time
  --> src/lib.rs:48:13
   |
47 |         b.x(&mut x);
   |             ------ first mutable borrow occurs here
48 |         b.x(&mut x); // Error: x already mutably borrowed in previous line
   |           - ^^^^^^ second mutable borrow occurs here
   |           |
   |           first borrow later used by call 
}

  1. Cell<T> / RefCell<T> / Mutex<T> use UnsafeCell<T> behind the scene ↩ī¸Ž

5 Likes

To confirm this, you can see that you get an error by making MyContainer invariant in T by means other than an UnsafeCell as well.

2 Likes