How do I deal with wrapper type invariance in Rust?

Question

References to wrapper types like &Rc<T> and &Box<T> are invariant in T (&Rc<T> is not a &Rc<U> even if T is a U). A concrete example of the issue (Rust Playground):

use std::rc::Rc;
use std::rc::Weak;

trait MyTrait {}

struct MyStruct {
}

impl MyTrait for MyStruct {}

fn foo(rc_trait: Weak<MyTrait>) {}

fn main() {
    let a = Rc::new(MyStruct {});
    foo(Rc::downgrade(&a));
}

This code results in the following error:

<anon>:15:23: 15:25 error: mismatched types:
 expected `&alloc::rc::Rc<MyTrait>`,
    found `&alloc::rc::Rc<MyStruct>`

Similar example (with similar error) with Box<T> (Rust Playground):

trait MyTrait {}

struct MyStruct {
}

impl MyTrait for MyStruct {}

fn foo(rc_trait: &Box<MyTrait>) {}

fn main() {
    let a = Box::new(MyStruct {});
    foo(&a);
}

In these cases I could of course just annotate a with the desired type, but in many cases that won't be possible because the original type is needed as well. So what do I do then?

Brainwashing

Note that this is not a variance problem. In Rust, trait implementation does not establish an "is-a" relationship, this is not like inheritance in other languages. Rust does not have subtyping, except in lifetimes of references (like &'a T is a subtype of &'static T for any 'a). You can find more here. – Barabarabarabas

@VladimirMatveev Um, the document you are linking to (which I have read trying to figure this out) specifically states that &T is variant over T and Box<T> is also variant over T. Yet, as my question shows, &Box<T> is not variant over T. If you can explain why that is, please do share it as an answer (if that insight also gives some alternate way of dealing with the invariance, all the better). – Brainwashing

@VladimirMatveev You may be right though that "is a" should be replaced with something like "satisfies the type constraint of" and "variant" should be replaced with something else. But I'm not sure what. – Brainwashing

Actually, your question does not show that &Box<T> is not variant over T, because the only subtyping relationship in Rust is tied to lifetimes (as in &'a T <: &'b T if 'a is larger than 'b), but your question contains only trait implementations, which, as I said before, are not related to subtyping and therefore variance in any way. Try passing, say, &Box<&'static i32> to a function which expects &Box<&i32> and you will see the covariance in action: gist.github.com/20983300fcf6872a583db38cfe96d663 – Barabarabarabas

As I said, the terminology I've chosen to use in the question may be slightly incorrect, but the phenomenon I'm asking about is still very much there (code in question gets type mismatches, code in the answer below type checks fine). If you have suggestions for what terminology I should use instead you are very welcome to suggest it. I guess it has more to do with trait object casting (or something like that) on the compiler level, but it sure feels like variance. – Brainwashing

Okay, I tried to explain it in a little more detail in a separate answer. – Barabarabarabas

Answer 1

What you see here is not related to variance and subtyping at all.

First, the most informative read on subtyping in Rust is this chapter of Nomicon. You can find there that in Rust subtyping relationship (i.e. when you can pass a value of one type to a function or a variable which expects a variable of different type) is very limited. It can only be observed when you're working with lifetimes.

For example, the following piece of code shows how exactly &Box<T> is (co)variant:

fn test<'a>(x: &'a Box<&'a i32>) {}

fn main() {
    static X: i32 = 12;
    let xr: &'static i32 = &X;
    let xb: Box<&'static i32> = Box::new(xr);  // <---- start of box lifetime
    let xbr: &Box<&'static i32> = &xb;
    test(xbr);  // Covariance in action: since 'static is longer than or the 
                // same as any 'a, &Box<&'static i32> can be passed to
                // a function which expects &'a Box<&'a i32>
                //
                // Note that it is important that both "inner" and "outer"
                // references in the function signature are defined with
                // the same lifetime parameter, and thus in `test(xbr)` call
                // 'a gets instantiated with the lifetime associated with
                // the scope I've marked with <----, but nevertheless we are
                // able to pass &'static i32 as &'a i32 because the
                // aforementioned scope is less than 'static, therefore any
                // shared reference type with 'static lifetime is a subtype of
                // a reference type with the lifetime of that scope
}  // <---- end of box lifetime

This program compiles, which means that both & and Box are covariant over their respective type and lifetime parameters.

Unlike most of "conventional" OOP languages which have classes/interfaces like C++ and Java, in Rust traits do not introduce subtyping relationship. Even though, say,

trait Show {
    fn show(&self) -> String;
}

highly resembles

interface Show {
    String show();
}

in some language like Java, they are quite different in semantics. In Rust bare trait, when used as a type, is never a supertype of any type which implements this trait:

impl Show for i32 { ... }

// the above does not mean that i32 <: Show

Show, while being a trait, indeed can be used in type position, but it denotes a special unsized type which can only be used to form trait objects. You cannot have values of the bare trait type, therefore it does not even make sense to talk about subtyping and variance with bare trait types.

Trait objects take form of &SomeTrait or &mut SomeTrait or SmartPointer<SomeTrait>, and they can be passed around and stored in variables and they are needed to abstract away the actual implementation of the trait. However, &T where T: SomeTrait is not a subtype of &SomeTrait, and these types do not participate in variance at all.

Trait objects and regular pointers have incompatible internal structure: &T is just a regular pointer to a concrete type T, while &SomeTrait is a fat pointer which contains a pointer to the original value of a type which implements SomeTrait and also a second pointer to a vtable for the implementation of SomeTrait of the aforementioned type.

The fact that passing &T as &SomeTrait or Rc<T> as Rc<SomeTrait> works happens because Rust does automatic coercion for references and smart pointers: it is able to construct a fat pointer &SomeTrait for a regular reference &T if it knows T; this is quite natural, I believe. For instance, your example with Rc::downgrade() works because Rc::downgrade() returns a value of type Weak<MyStruct> which gets coerced to Weak<MyTrait>.

However, constructing &Box<SomeTrait> out of &Box<T> if T: SomeTrait is much more complex: for one, the compiler would need to allocate a new temporary value because Box<T> and Box<SomeTrait> has different memory representations. If you have, say, Box<Box<T>>, getting Box<Box<SomeTrait>> out of it is even more complex, because it would need creating a new allocation on the heap to store Box<SomeTrait>. Thus, there are no automatic coercions for nested references and smart pointers, and again, this is not connected with subtyping and variance at all.

Barabarabarabas

Okay, I understand that I've probably put more emphasis on the lack of subtyping for traits than it was necessary, but still I've tried to explain why "flat" references and smart pointers can be coerced to trait objects and why "nested" pointers can not. – Barabarabarabas

Thanks. This is great. While I was able to figure out code that worked on my own, now I understand a lot better why the particular variants work and not. :) – Brainwashing

Answer 2

In the case of Rc::downgrade this is actually just a failure of the type inference in this particular case, and will work if it is done as a separate let:

fn foo(rc_trait: Weak<MyTrait>) {}

fn main() {
    let a = Rc::new(MyStruct {});
    let b = Rc::downgrade(&a);
    foo(b);
}

Playground

For Box<T> it is very likely you don't actually want a reference to the box as the argument, but a reference to the contents. In which case there is no invariance to deal with:

fn foo(rc_trait: &MyTrait) {}

fn main() {
    let a = Box::new(MyStruct {});
    foo(a.as_ref());
}

Playground

Similarly, for the case with Rc<T>, if you write a function that takes an Rc<T> you probably want a clone (i.e. a reference counted reference), and not a normal reference:

fn foo(rc_trait: Rc<MyTrait>) {}

fn main() {
    let a = Rc::new(MyStruct {});
    foo(a.clone());
}

Playground

Brainwashing