Traits in algebraic data types

Question

I'm having trouble understanding the rules about traits in algebraic data types. Here's a simplified example:

use std::rc::Rc;
use std::cell::RefCell;

trait Quack {
    fn quack(&self);
}

struct Duck;

impl Quack for Duck {
    fn quack(&self) { println!("Quack!"); }
}

fn main() {
    let mut pond: Vec<Box<Quack>> = Vec::new();
    let duck: Box<Duck> = Box::new(Duck);
    pond.push(duck); // This is valid.

    let mut lake: Vec<Rc<RefCell<Box<Quack>>>> = Vec::new();
    let mallard: Rc<RefCell<Box<Duck>>> = Rc::new(RefCell::new(Box::new(Duck)));
    lake.push(mallard); // This is a type mismatch.
}

The above fails to compile, yielding the following error message:

 expected `alloc::rc::Rc<core::cell::RefCell<Box<Quack>>>`,
    found `alloc::rc::Rc<core::cell::RefCell<Box<Duck>>>`
(expected trait Quack,
    found struct `Duck`) [E0308]
src/main.rs:19     lake.push(mallard);

Why is it that pond.push(duck) is valid, yet lake.push(mallard) isn't? In both cases, a Duck has been supplied where a Quack was expected. In the former, the compiler is happy, but in the latter, it's not.

Is the reason for this difference related to CoerceUnsized?

Note: `RefCell` is unnecessary here, I can reproduce the issue with `Rc>`. — Matthieu M., Jun 05 '15 at 06:29
Matthieu, you are correct. `RefCell` is unnecessary to make the error occur. Based on Vladimir's answer below, I can see why the same error occurs with or without `RefCell`. — rlkw1024, Jun 05 '15 at 17:00

Vladimir Matveev · Accepted Answer · 2015-06-05T08:38:28.017

This is a correct behavior, even if it is somewhat unfortunate.

In the first case we have this:

let mut pond: Vec<Box<Quack>> = Vec::new();
let duck: Box<Duck> = Box::new(Duck);
pond.push(duck);

Note that push(), when called on Vec<Box<Quack>>, accepts Box<Quack>, and you're passing Box<Duck>. This is OK - rustc is able to understand that you want to convert a boxed value to a trait object, like here:

let duck: Box<Duck> = Box::new(Duck);
let quack: Box<Quack> = duck;  // automatic coercion to a trait object

In the second case we have this:

let mut lake: Vec<Rc<RefCell<Box<Quack>>>> = Vec::new();
let mallard: Rc<RefCell<Box<Duck>>> = Rc::new(RefCell::new(Box::new(Duck)));
lake.push(mallard);

Here push() accepts Rc<RefCell<Box<Quack>>> while you provide Rc<RefCell<Box<Duck>>>:

let mallard: Rc<RefCell<Box<Duck>>> = Rc::new(RefCell::new(Box::new(Duck)));
let quack: Rc<RefCell<Box<Quack>>> = mallard;

And now there is a trouble. Box<T> is a DST-compatible type, so it can be used as a container for a trait object. The same thing will soon be true for Rc and other smart pointers when this RFC is implemented. However, in this case there is no coercion from a concrete type to a trait object because Box<Duck> is inside of additional layers of types (Rc<RefCell<..>>).

Remember, trait object is a fat pointer, so Box<Duck> is different from Box<Quack> in size. Consequently, in principle, they are not directly compatible: you can't just take bytes of Box<Duck> and write them to where Box<Quack> is expected. Rust performs a special conversion, that is, it obtains a pointer to the virtual table for Duck, constructs a fat pointer and writes it to Box<Quack>-typed variable.

When you have Rc<RefCell<Box<Duck>>>, however, rustc would need to know how to construct and destructure both RefCell and Rc in order to apply the same fat pointer conversion to its internals. Naturally, because these are library types, it can't know how to do it. This is also true for any other wrapper type, e.g. Arc or Mutex or even Vec. You don't expect that it would be possible to use Vec<Box<Duck>> as Vec<Box<Quack>>, right?

Also there is a fact that in the example with Rc the Rcs created out of Box<Duck> and Box<Quack> wouldn't have been connected - they would have had different reference counters.

That is, a conversion from a concrete type to a trait object can only happen if you have direct access to a smart pointer which supports DST, not when it is hidden inside some other structure.

That said, I see how it may be possible to allow this for a few select types. For example, we could introduce some kind of Construct/Unwrap traits which are known to the compiler and which it could use to "reach" inside of a stack of wrappers and perform trait object conversion inside them. However, no one designed this thing and provided an RFC about it yet - probably because it is not a widely needed feature.

Thanks! How would you implement this pattern? The pattern I mean is this: You have a bunch of mutable objects. For efficiency, they can be accessed via different lookup structures, e.g. a hash, a binary tray, and a vector. Some of these lookup structures need objects of different types that all implement a trait. I could wrap them in Enums. Or I could create wrapper structs that own Boxes. — rlkw1024, Jun 05 '15 at 16:10
According to this RFC ( https://github.com/rust-lang/rfcs/blob/master/text/0982-dst-coercion.md ) the target wrapper type should implement CoerceUnsized in order to make trait auto-coersion possible. However RefCell at the moment misses this implementation, but still is coerseable for stack-based entities ( https://stackoverflow.com/questions/30861295/how-to-i-pass-rcrefcellboxmystruct-to-a-function-accepting-rcrefcellbox ). Box implements CoerceUnsized and is coerseable on its own, but not in the RefCell, which is utterly weird. — snuk182, Aug 03 '16 at 12:59
I tried to implement own RefCell that implements CoerceUnsized, with no success ( https://play.rust-lang.org/?gist=27e5b540bfceaa9db79abea5f6526d48&version=nightly&backtrace=2 ), and it's is even more unclear why it's so, cause the RefCell is just a runtime borrow checker for the UnsafeCell, which is just a wrapper like QuackWrap from the example below. — snuk182, Aug 03 '16 at 13:01
Ah, I see. Box here acts as &T, so besides of the inner value's vtable cut while holding a trait object, it also does not give the full vtable info to the objects that wrap it, and that is why it's so far not possible to cast wrapped DST types. Looks like we need to use unsafe and make a new DST type wrapper with manual vtable management. — snuk182, Aug 03 '16 at 14:20
Also this article describes that very well http://cglab.ca/~abeinges/blah/rust-reuse-and-recycle/ — snuk182, Aug 03 '16 at 15:30

rlkw1024 · Answer 2 · 2015-06-05T17:56:43.320

Vladimir's answer explained what the compiler is doing. Based on that information, I developed a solution: Creating a wrapper struct around Box<Quack>.

The wrapper is called QuackWrap. It has a fixed size, and it can be used just like any other struct (I think). The Box inside QuackWrap allows me to build a QuackWrap around any trait that implements Quack. Thus, I can have a Vec<Rc<RefCell<QuackWrap>>> where the inner values are a mixture of Ducks, Gooses, etc.

use std::rc::Rc;
use std::cell::RefCell;

trait Quack {
    fn quack(&self);
}

struct Duck;

impl Quack for Duck {
    fn quack(&self) { println!("Quack!"); }
}

struct QuackWrap(Box<Quack>);

impl QuackWrap {
    pub fn new<T: Quack + 'static>(value: T) -> QuackWrap {
        QuackWrap(Box::new(value))
    }
}

fn main() {
    let mut pond: Vec<Box<Quack>> = Vec::new();
    let duck: Box<Duck> = Box::new(Duck);
    pond.push(duck); // This is valid.

    // This would be a type error:
    //let mut lake: Vec<Rc<RefCell<Box<Quack>>>> = Vec::new();
    //let mallard: Rc<RefCell<Box<Duck>>> = Rc::new(RefCell::new(Box::new(Duck)));
    //lake.push(mallard); // This is a type mismatch.

    // Instead, we can do this:
    let mut lake: Vec<Rc<RefCell<QuackWrap>>> = Vec::new();
    let mallard: Rc<RefCell<QuackWrap>> = Rc::new(RefCell::new(QuackWrap::new(Duck)));
    lake.push(mallard); // This is valid.
}

As an added convenience, I'll probably want to implement Deref and DefrefMut on QuackWrap. But that's not necessary for the above example.

Traits in algebraic data types

2 Answers2

Linked