Trait objects of combined traits and type reconstruction

help
1

Hello,

I have some question about trait objects of combined traits.

They need some build up, you'll find them at the very end. A
complete minimal example is on GitHub, runs with cargo run.

I've been playing with trait objects, which seem to solve a similar
problem as Haskell's existential types: They allow you to put things
of different type (A and B) into a generic datastructure like
Vec<T>, which would normally force you to choose T=A, or
T=B, exclusively, or use a sum type like Either.

However, if A and B both implement a common trait, say:
Printable, then you may create a Vec<&dyn Printable> which can
hold items of both types.

let a = A{};
let b = B{};
let items: Vec<&dyn Printable> = vec!(&a, &b);

This is type safe, since the compiler only allows you to use those
properties of the elements of the vector that are provided by the
common trait.

In other words: When taking an item from the vector, all you know for
sure is it's printable. That's what the type says, and that's what
the compiler allows you to do. You may print them.

So far, so good.

I have then tried (obviously) to reconstruct the original type of the
vector's members, and this is also possible: Define an enum for every
possible case, here this would be

enum Discovery<'a> { IsA(&'a A), IsB(&'a B) }

extend A and B with a function to report their case

trait Discoverable { fn discover(&self) -> Discovery; }

impl Discoverable for A { fn discover(&self) -> Discovery { IsA(&self) } }
impl Discoverable for B { fn discover(&self) -> Discovery { IsB(&self) } }

and almost! Next I wanted to create a vector of type

Vec<&dyn Printable + Discoverable>

which failed with “only auto traits can be used as additional traits
in a trait object”, but included a helpful suggestion (Thanks!)
making me try

trait CombinedTrait: Printable + Discoverable {}
impl<T: Printable + Discoverable> CombinedTrait for T {}

let items: Vec<&dyn CombinedTrait> = vec!(&a, &b);

Now this works partially. The function

fn print_and_discover<T: CombinedTrait>(x: &T) {
    x.print();
    match x.discover() {
        IsA(a) => a.only_a(),
        IsB(b) => b.only_b(),
    }
}

happily prints the items using their common “printability”, then
discovers their type and dispatches accordingly, calling functions
only_ that are ony implemented for the individual types.

But this seems to go only so far. While I can create my vector

let items: Vec<&dyn CombinedTrait> = vec!(&a, &b);

print and rediscover the items

items[i].print();
match items[i].discover() { … }

I fail to pass the vector to a function:

fn print_list(items: &Vec<&dyn Printable>) { … }
print_list(&items);

gives “expected trait Printable, found trait CombinedTrait”.

Question 1: Why does a found CombinedTrait not satisfy an
expected Printable?

Also, I fail to create and use an iterator (other than the counting
loop above):

for i in items.iter() { print_and_discover(i); }

gives “the trait bound &dyn CombinedTrait: CombinedTrait is not
satisfied”

Question 2: is it not? should it not be?

Cheers!


struct A {}

impl A {
    fn only_a(&self) {
        println!("only A");
    }
}


struct B {}

impl B {
    fn only_b(&self) {
        println!("only B");
    }
}



trait Printable {
    fn print(&self);
}

impl Printable for A {
    fn print(&self) {
        println!("print A");
    }
}

impl Printable for B {
    fn print(&self) {
        println!("print B");
    }
}

fn print_list(items: &Vec<&dyn Printable>) {
    for i in items {
        i.print();
    }
}



enum Discovery<'a> {
    IsA(&'a A),
    IsB(&'a B)
}
use Discovery::*;

trait Discoverable {
    fn discover(&self) -> Discovery;
}

impl Discoverable for A {
    fn discover(&self) -> Discovery { IsA(&self) }
}

impl Discoverable for B {
    fn discover(&self) -> Discovery { IsB(&self) }
}

trait CombinedTrait: Printable + Discoverable {}

impl<T: Printable + Discoverable> CombinedTrait for T {}

fn print_and_discover<T: CombinedTrait>(x: &T) {
    x.print();
    match x.discover() {
        IsA(a) => a.only_a(),
        IsB(b) => b.only_b(),
    }
}



fn main() {

    let a = A{};
    let b = B{};


    // Nice!

    println!("-- different types in one list");
    let items: Vec<&dyn Printable> = vec!(&a, &b);
    print_list(&items);


    // Quality!!!

    println!("-- reconstruction of original type");
    print_and_discover(&a);
    print_and_discover(&b);


    // Looking good...

    println!("-- combined trait in vector (commented out)");

    #[allow(unused_variables)]
    let items: Vec<&dyn CombinedTrait> = vec!(&a, &b);

    for i in 0..items.len() {
        items[i].print();
        match items[i].discover() {
            IsA(a) => a.only_a(),
            IsB(b) => b.only_b(),
        }
    }


    // These two don't compile, and I don't understand why.

    /*
    print_list(&items);
    // */

    /*
    for i in items.iter() {
        print_and_discover(i);
    }
    // */
}
2

Because the actual data making up a &dyn CombinedTrait is not the same format as &dyn Printable (specifically, it does not have the same vtable pointer). Interpreting the former as the latter would call the wrong functions.

What you should do instead is make the function more generic. For example, to fix this immediate error:

fn print_list<P: ?Sized + Printable>(items: &[&P]) {

This now accepts references to any type that implements Printable, including a reference to dyn CombinedTrait. This is not quite as flexible as it could be, though — it demands that the elements are references. What you should do is add a forwarding trait implementation:

impl<P: ?Sized + Printable> Printable for &P {
    fn print(&self) {
        P::print(&*self)
    }
}

Now &P implements Printable too, so we can generalize print_list to a slice of anything printable that can go in a slice even if it is not a reference:

fn print_list<P: Printable>(items: &[P]) {

This way, the caller is not obligated to construct a vector or other slice of references. The final generalization would be to accept IntoIterator<Item = P> instead of a slice, thus freeing the caller of the obligation to construct a slice (data placed in contiguous memory) at all.

References do not automatically implement new traits. In order for &dyn CombinedTrait to implement CombinedTrait, you will need to add trait implementations so that it does. This means you must add a forwarding implementation for Discoverable like Printable:

impl<D: ?Sized + Discoverable> Discoverable for &D {
    fn discover(&self) -> Discovery {
        D::discover(&*self)
    }
}

Once you do this, your existing blanket impl CombinedTrait for T will start working for the reference type &dyn CombinedTrait.

In general, whenever you define a new trait, you should, if possible, add this kind of forwarding implementation for &T, &mut T, Box<T>, Rc<T>, and Arc<T>. This gives users of the trait important flexibility.

1 Like
3

What stops the compiler from passing a different vtable pointer?

4

It may help to highlight that dyn Trait + 'd is a concrete, statically known type (albeit not Sized). It's not a generic and it's not a dynamic type. It's also not a supertype of the implementors. And a dyn SuperTrait is not a supertype of dyn SubTrait, either.

These are forms of an "unsizing coercion" which may need to change the reference (to add or change the vtable pointer):

  • &A to &dyn Printable
  • &dyn CombinedTrait to &dyn Printable

"Satisfy" is perhaps not the right word, as this is a type mismatch. But there's no way to automatically perform conversion (coercion) of the Vec full of &dyn _s.

You'd have to create a new Vec<_> and coerce each &dyn _ during construction.

Note that &T and T are also distinct types.

It's not always possible to supply the implementation. Perhaps you have a &mut self method, or perhaps an unsatisfiable supertrait bound.

In this case, you'd have to change every vtable pointer for every reference inside the Vec. That's a library type, the compiler doesn't even know how to find the contents in the language currently; even if it did, you'd need some place to store the coerced references... that couldn't be shared without synchronization.

In other cases, you can coerce to a supertrait.

I've written more about dyn generally here. (N.b. I haven't got around to updating it with regards to the now-stable supertrait coercions.)

1 Like
5

When you create a Vec<&dyn CombinedTrait>, you create a memory allocation for a slice [&dyn CombinedTrait] which contains data pointers and dyn CombinedTrait vtable pointers. In order to have a [&dyn Printable] you would have to make a new allocation for a new slice whose contents are &dyn Printables instead. The compiler will never implicitly create a heap allocation like that.

The key fact is that these vector (or slice) types don't contain one vtable pointer, they contain many vtable pointers, one per element. That means that we have to think about where the storage for all those pointers comes from.

1 Like
6

Yeah, sorry, I overlooked that it was a Vec.