RefCell confuses the compiler (well, mostly me)

[Bytekeeper]

I'm a bit confused why RefCell would mess up lifetimes here:

use core::cell::RefCell;

struct A<'a> {
    b: Vec<B<'a>>,
    //cell: RefCell<B<'a>>
}

struct B<'a> {
    a: &'a A<'a>
}

impl<'a> A<'a> {
    fn new_b(&self) -> B {
        // Uncomment cell above and this will not compile
        B { a: self }
    }
}

fn main() {
}

Even with multiple references to A through B and some variables - it should not change, or should it?

[alice]

This is due to variance. If you allow the two lifetimes inside B to be different it will work (by defining the struct with two lifetimes). The issue is that the inner lifetime cannot be shortened to be equal to the outer lifetime if A is invariant.

[Yandros]

For a more detailed response:

@Bytekeeper

fn new_b(&self) -> B {

This is a typical case where so many lifetimes have been elided that what is happening under the rug becomes magic. Let's remove the sugar / the elisions:

impl<'a> A<'a> {
    fn new_b (self: &'_ A<'a>) -> B<'_> /* i.e. &'_ A<'_> */
// i.e.
    fn new_b<'b> (self: &'b A<'a>) -> B<'b> /* i.e. &'b A<'b> */
    where
        'a : 'b, // i.e. 'a ≥ 'b

So, as you can see, you are trying to go from &'b A<'a> to &'b A<'b> where 'b is smaller than 'a (or equal).

For this to work, it is thus necessary to "be able to shrink the inner 'a lifetime down to 'b", which, in more technical terms, is expressed as:

&'b A<'a> must (be a) subtype (of) &'b A<'b>

which is a property I will write as

&'b A<'a> : &'b A<'b>
          ≥
         (I am using a greater sign here since for lifetimes it corresponds to the intuitive "outlives" relation)

For this to work, we need to study the "function"

type f<'x> = &'b A<'x>

Do we have
'a : 'b ⇒ f<'a> : f<'b>, i.e., with a more friendly notation:
'a ≥ 'b ⇒ f<'a> ≥ f<'b>, i.e.,
"is our f 'function' monotonically increasing"?

Here, since f<'x> is a type / f is a type constructor, instead of monotonicity and ≥, we talk of variance and subtyping:

• x ≥ y becomes X : Y and is phrased as X is a subtype of Y

• monotonically increasing becomes covariant,

• monotonically decreasing becomes contravariant,

• and being neither is called invariant.

In other words:

is type f<'x> = &'b A<'x> covariant?

And to answer that, we have to see f<'x> as the composition of type g<A> = &'b A with type A<'x> = struct { ... B<'x>, RefCell<B<'x>> }. And to studiy the mononoty of a composition ("chaining transformations") the intuitive rules apply:

Since g is covariant / monotonically increasing, f<'x> has the same monotony / variance as the inner A<'x>.

So, the final question is:

Is A<'x> covariant?

And in this case, to be honest, since you talked about a difference in behavior, it meant that without RefCell it had to be covariant, but it isn't obvious at all, since the type is recursive (it contains a B<'x> which itself uses A<'x>...)).

So, I have tested it a bit to be sure, and a recursive struct A<'x> /* = */ (&'x A<'x>); definition is indeed covariant: Playground.

But <B> -> RefCell<B> is not covariant (it's invariant), so 'x -> RefCell<B<'x>> isn't either (by function composition / chaining).

And for a struct <'x> to be covariant over <'x>, all its fields need to be so.

Thus: adding / removing RefCell to the struct changes the variance of A from covariant (without the RefCell) to invariant, and your new_b function signature happens to require that A be covariant in order to typecheck, hence the error.

[Bytekeeper]

Thanks, actually I think I was mostly surprised by RefCell making the whole thing invariant. I read the chapter on Variance, @alice posted, again. (Including that &mut T is also invariant)

[Yandros]

The rules about what is covariant and what isn't, are surprisingly simple:

1. When in doubt, be invariant: this conservative choice is always sound;

2. If something is immutable, then it can be covariant. "That's why" type f<X> = &'_ X is covariant.

3. If the thing is owned, then covariance is fine too, even if immutability is no longer guaranteed (X, Box<X>, ARc<X>, etc.).

4. When something is mutable but not owned (such as &'_ mut X), then it is invariant (covariance would be unsound).

This leads to the awkward situation of the shared mutability wrappers, such as UnsafeCell, Cell, RefCell, Mutex, RwLock. These, by value, are owned, so covariance would be fine.

But if they were covariant and &'_ X was covariant too, by composition &'_ Cell<X>, etc. would be covariant too, which is unsound, since these are mutable non-owning types.

So the choice was made that mutability wrappers be invariant, even when owned.