If Cell/etc are invariant then how do trait objects work?

We're confused about variance, after having read this: Subtyping and Variance - The Rustonomicon

This seems to imply trait objects follow variance? But it seems more subtle than what is documented, because e.g. this seemingly works:

use std::cell::RefCell;
struct Foo;
struct Why;
trait Bar {}
impl Bar for Foo {}
impl Bar for Why {}

fn main() {
    let x: &RefCell<Foo> = &RefCell::new(Foo);
    let y: &RefCell<dyn Bar> = x;
    y.borrow_mut();
    x.borrow_mut();
}

How does variance actually work? Does it even matter for traits?

3 Likes

As far as I know, Rust only has proper subtyping and variance with regards to lifetimes. Thus I'm not sure the concept of variance even applies to traits or trait objects alone (unless they themselves involve lifetimes).

Specifically what in your example above would you expect not to work?

2 Likes

The reason is the same as why coercing an &mut T to &mut dyn Trait is sound: because with that dyn Trait you can't do anything more than you could with just T.

3 Likes

So an <T: 'static> is invariant?

This is unsizing coercion, and there's a CoerceUnsized impl within std implemented for RefCell to support this.

3 Likes

No that's for pointers:

For wrapper types that directly embed T like Cell<T> and RefCell<T> , [...]. This will let coercions of types like Cell<Box<T>> work.

You're right, it's using Unsize trait directly through the CoerceUnsized implementation on shared references in this case:

#![feature(unsize)]

use std::cell::RefCell;
use std::marker::Unsize;

fn unsize<A, B: ?Sized>(v: &A) -> &B where A:Unsize<B> {
    v
}

struct Foo;
struct Why;
trait Bar {}
impl Bar for Foo {}
impl Bar for Why {}

fn main() {
    let x: &RefCell<Foo> = &RefCell::new(Foo);
    unsize::<RefCell<Foo>, RefCell<dyn Bar>>(&x);
}
1 Like

I’ve wondered the same thing recently after/while pondering on unsized coercion in the context of finding #85099. Turns out, unsized coercion it mostly separate from subtyping. In effect converting a T into an S, which isn’t allowed.

The reason why RefCell<T> is invariant in T is that otherwise, you could have S subtype of T, take an &RefCell<S>, coerce it into &RefCell<T>, then write a T into that, and read the value back as an S from a copy of the original &RefCell<S> reference.

Now, unsizing does feel similar to subtying in a lot of ways. There’s a type T and another type dyn Trait and you’ve got an “is-a” relationship between them. Yet, the coercion from T to dyn Trait only works in types where T exists behind exactly one layer of indirection. So something like &RefCell<T> to &RefCell<dyn Trait> works. But then, this conversion doesn’t present any way of replacing the dyn Trait inside of that RefCell with a different value of type dyn Trait like it was possible for the types S and T above. Why? Well, you cannot more any dyn Trait values because they’re unsized, and any self: &RefCell<dyn Trait> method from Trait that can modify the RefCell’s contents calls a sound method on the underlying type &RefCell<T>, so it doesn’t really offer any way to exploit it either.

The reasoning above isn’t much more than: Turns out the types being unsized and the way trait objects work just don’t offer any way to create unsoundness. I don’t find it particularly convincing myself since I cannot really get any deep intuition about why no way to create unsoundness exists; I just know that the ways I tried don’t seem to offer any weak points.

If for example we’d try to eliminate the problem of being unable to write to the RefCell because it contains an unsized type, we might box the type, so use &RefCell<Box<T>>. But that’s two indirections now so the unsound coercion is gone… We could remove the outer reference and, well…, now we can convert RefCell<Box<T>> into RefCell<Box<dyn Trait>>! But that’s not a particularly dangerous operation; it could be achieved by RefCell::into_inner and RefCell::new. In fact, even for subtypes S of T, direct conversion of RefCell<S> to RefCell<T> aren’t problematic from a soundness perspective (yet they are disallowed by variance; you’d need to do the into_inner+new approach here); having RefCell be invariant is somewhat of a hack that’s only there to ensure that shared references (like &, Rc or Arc) to RefCells aren’t covariant.


Another interesting point on the interaction of trait objects and variance: There are subtle cases of what works and what doesn’t work when you’re comparing dyn for<'a> Foo<'a> with dyn Foo<'b>.

Certainly, intuitively a dyn for<'a> Foo<'a> is a dyn Foo<'b>, so this is subtyping-like. And in fact it does interact with subtyping/variance, so something like

trait Foo<'a> {}

fn foo<'b>(x: Box<Box<Box<dyn for<'a> Foo<'a>>>>) -> Box<Box<Box<dyn Foo<'b>>>> {
    x
}

compiles. But the same coercion appears to also work in contexts where unsized coercion would be allowed. For example this also compiles

fn bar<'b>(x: Box<RefCell<dyn for<'a> Foo<'a>>>) -> Box<RefCell<dyn Foo<'b>>> {
    x
}

fn bar_1<'b>(x: RefCell<Box<dyn for<'a> Foo<'a>>>) -> RefCell<Box<dyn Foo<'b>>> {
    x
}

fn bar_2<'b>(x: RefCell<Box<RefCell<dyn for<'a> Foo<'a>>>>) -> RefCell<Box<RefCell<dyn Foo<'b>>>> {
    x
}

but it doesn’t compose with other covariant wrappers, e.g.

fn baz<'b>(x: Box<Box<RefCell<dyn for<'a> Foo<'a>>>>) -> Box<Box<RefCell<dyn Foo<'b>>>> {
    x
    // error[E0308]: mismatched types
    //   --> src/lib.rs:14:5
    //    |
    // 22 |     x
    //    |     ^ one type is more general than the other
    //    |
    //    = note: expected struct `Box<Box<RefCell<(dyn Foo<'b> + 'static)>>>`
    //               found struct `Box<Box<RefCell<(dyn for<'a> Foo<'a> + 'static)>>>`
}

or

fn qux<'b>(x: Box<RefCell<Box<dyn for<'a> Foo<'a>>>>) -> Box<RefCell<Box<dyn Foo<'b>>>> {
    todo!() // wouldn’t work either
}

and here, at least the last example qux would also be unsound if it did compile successfully. Edit: In my head I was thinking of something like &RefCell<Box<dyn Foo<'b>> or Arc<RefCell<Box<dyn Foo<'b>>> which would actually be unsound. With a Box of course it’s not a problem, in fact it can be implemented by dereferencing and Box::new.

(all code examples in a playground)


I do believe that all of this isn’t sufficiently documented in the reference, at least as far as I’m aware. Especially the way that for<'a> Foo<'a> worked is something I could only find out by trying out what compiles and what doesn’t. Looks like the functions bar[_(1|2)] aren’t even compiling on not-too-recent compilers. Seems like they’re only accepted since Rust 1.46 (no mention of this in the release notes though).

7 Likes

We think the thing with unsizing is that the vtable pointer is... actually external to the invariant element.

That is to say, a &RefCell<dyn Bar> is, effectively, a (&RefCell<Foo>, &'static VTable<dyn Bar, Foo>) (with the <Foo> parts elided), rather than a form of subtyping. Any attempts to write to it wouldn't/cannot work, because you can't change the storage size or the vtable of the original object. Of course, Foo itself (and the Bar for Foo) is able to do whatever it wants to the underlying storage.

But it's not particularly intuitive.

1 Like

for<> dyn Trait and dyn Trait<> do have a subtyping relationship as far as I'm aware, just like for<> fn and fn. And I'm also not aware of any other higher-ranked types (vs. bounds); if there are any, I imagine they act the same as well. (You can use this to compare against unsized coercion: If I update your baz to use fns, I get the same error, for example.)

More here (which you're aware of but others may not be).


This conversation as a whole so far has been ignoring dyn's elision-happy lifetime bound. Every dyn Trait has one, which is basically the limit of all the lifetimes that got erased. Surprisingly, this bound acts covariant-like in a way that bypasses invariance as part of unsized coercion.

use core::cell::RefCell;
trait Foo<'a> {}

// works
fn foo_1<'a: 'b, 'b, 'c>(x: Box<RefCell<dyn Foo<'c> + 'a>>) -> Box<RefCell<dyn Foo<'c> + 'b>> {
    x
}

// fails
fn foo_2<'a: 'b, 'b, 'c>(x: Box<RefCell<dyn Foo<'c> + 'b>>) -> Box<RefCell<dyn Foo<'c> + 'a>> {
    x
}

This is working as specified in RFC 599 (skip forward to "Interaction with object coercion") as best I can tell (which isn't 100%).

See this previous discussion for more on this from Ralf, eddyb, Yandros and others.

2 Likes

We haven't been able to do a safe lifetime transmute with it, at least. We don't know how you'd break it.

use core::cell::RefCell;
trait Foo<'a> {
  fn thing(&mut self) -> &mut &'a str;
}

impl<'a, 'b> Foo<'b> for &'a mut &'b str {
  fn thing(&mut self) -> &mut &'b str {
      self
  }
}

fn foo_1<'a: 'b, 'b, 'c>(x: &'b RefCell<dyn Foo<'c> + 'a>) -> &'b RefCell<dyn Foo<'c> + 'b> {
    x
}

fn foo_2<'a, 'b>(x: &'a mut &'b str) {
    let x: RefCell<&'a mut &'b str> = RefCell::new(x);
    let y = foo_1(&x);
    let z = foo_3(y, &String::new());
}

fn foo_3<'b: 'c, 'c>(x: &'b RefCell<dyn Foo<'c> + 'b>, y: &'b str) {
    *x.borrow_mut().thing() = y;
}

But we're not sure how this would interact with the hypothetical Arc locking, with Invariant<T>: Arc locking by SoniEx2 · Pull Request #88112 · rust-lang/rust · GitHub

Literally an eye-opener! :+1:

1 Like

T: 'static is not invariant. (found by @SkiFire13 ) Rust Playground

So unfortunately one would actually need Invariant<T> for Arc locking, but nobody wants Invariant<T>. (We're also still not sure if this is sound, even with Invariant<T>, altho Invariant<T> is sufficient to block the above example.)

move leak-check to during coherence, candidate eval landed in 1.46.0. I'm not sure it's that but seems like it could be.

Tbh, when I saw the thread title, I immediately thought of that :grinning_face_with_smiling_eyes:. So the thing is that, for instance, a &'a mut (dyn Trait + 'static) can be used where a &'a mut (dyn Trait + 'bound) is expected, which looks like covariance (especially in that thread at the time); which is why I've since learned that to make sure we are dealing with covariance, wrapping the stuff within a layer that doesn't allow this "coercion" to happen is best

  • e.g., when wondering if T : U, rather than checking with |it: T| -> U { it }, it's better to check with |it: *const T| -> *const U { it } or |it: (T, )| -> (U, ) { it } since the last two prevent coercions from taking place (and correctly error when T = &'a mut (dyn Trait + 'long) and U = &'a mut (dyn Trait + 'short), for instance, as eddyb pointed out at the time).

  • regarding the coercion, we already know from the unsizing coercion that &'a mut (impl Sized + Tr + 'lt) can be coerced to a &'a mut (dyn Tr + 'lt); and if that is sound, it's not based on the Sized bound, so we ought to be able to remove that from the left and say that &'a mut (impl ?Sized + Tr + 'lt) could theoretically (it wouldn't be unsound, although it may technically be impossible in some cases) be coerced to a &'a mut (dyn Tr + 'lt), which yields that it is not absurd that &'a mut (dyn Tr + 'long) can be coerced to a &'a mut (dyn Tr + 'short). How and when that "reunsizing" coercion is implemented by the compiler exactly is another question (one which I can't totally answer yet), but at least it's not something that should be theoretically surprising when we look at it this way :slightly_smiling_face:

The prior discussion being referenced here

1 Like

That’s a nice term for this :grin:

I think that tuples might eventually implement

impl<T, U> CoerceUnsized<(U,)> for (T,) where T: CoerceUnsized<U> {}

so the second approach isn’t 100% future-proof. However, pointers (or anything with indirections) should keep “working” (i.e. failing to compile) indefinitely.

2 Likes