Cast Box<dyn TraitA<T>> to Box<dyn TraitB> where TraitA<T> impl TraitB

Hello everyone,
once again I have a problem casting trait objects. Here is my scenario:
I’m implementing a parser for typed expressions. All expressions implement the Expression trait

trait Expression<T: ExpType> {
  fn evaluate(&self) -> T;

This works fine and enables evaluation with exact types like f64 or bool. For giving a further abstraction I introduced the Value enum

enum Value {

The ExpType trait implements convertion functions from/into Value.

The next step was to hide the Expression type by a further trait

trait GeneralExpression {
  fn evaluate(&self) -> Value;

impl<T: ExpType> GeneralExpression for Expression<T> {
  fn evaluate(&self) -> Value { (self as &Expression<T>).evaluate().into() }

This works fine so far… until now. I want to collect expressions in a Vec<Box<dyn GeneralExpression>> but I constantly fail to cast from Box<dyn Expression<impl ExpType>> to Box<dyn GeneralExpression>>.

Has anyone an idea how this cast could work? Or is such a convertion the edge of compiler inference since it cannot infer that Expression<impl ExpType> implements GeneralExpression?

I know something like trait GeneralExpression: Expression<T> works but I want to hide the generic.

Since you’re working with boxed trait objects, you likely meant:

impl<T: ExpType> GeneralExpression for Box<dyn Expression<T>> { ... }

However, this doesn’t allow casting (unsizing), say, a Box<dyn Expression<f64>> to a Box<dyn GeneralExpression>. It does allow something like the following though:

fn into_general(expr: Box<dyn Expression<T>>) -> Box<dyn GeneralExpression> {

The difference is into_general creates a new trait object.

As you probably know, trait objects are represented as two pointers (aka “fat pointer”): one to the data (i.e. the value) and the other to the vtbl that holds (amongst a few other things) that type’s implementation of the trait.

A Box<dyn Expression<T>> therefore has such a fat pointer. If you implement GeneralExpression for Box<dyn Expression<T>>, you now need a fat pointer whose data pointer points to the fat ptr of Box<dyn Expression<T>> (because thats its own representation), and the vtbl pointer for the implementation of GeneralExpression for this type. So you need a fat pointer to a fat pointer, essentially - the problem is Box<dyn Expression<T>> is already storing its own fat pointer, and you can’t “insert” another one directly into it (which is what casting, or unsizing, Box<dyn Expression<T>> to Box<dyn GeneralExpression> would involve). Therefore, if you wanted such a box, you’d need to create a new Box wrapping the other one.

If you wanted to avoid the extra layer of boxes, you can try a trampoline (aka landing pad) approach - this is basically handwritten conversion infrastructure. Here is an example of what that might look like. The key bit is the into_boxed_general method that’s added, which takes a boxed Self. What this ends up doing is, given a Box<dyn Expression<T>>, it dispatches to the concrete type behind that fat pointer, while preserving the wrapper Box, and that concrete type just echoes itself back. This gives the compiler the ability to unsize the box in-place, since it knows the concrete type inside the Box. I’m not a MIR expert, but the MIR for DummyExpr::into_boxed_general() looks like this:

fn <impl at src/ 32:2>::into_boxed_general(_1: std::boxed::Box<DummyExpr>) -> std::boxed::Box<dyn GeneralExpression>{
    let mut _0: std::boxed::Box<dyn GeneralExpression>; // return place
    let mut _2: std::boxed::Box<dyn GeneralExpression>;
    let mut _3: std::boxed::Box<DummyExpr>;

    bb0: {                              
        StorageLive(_2);                 // bb0[0]: scope 0 at src/ 30:13
        StorageLive(_3);                 // bb0[1]: scope 0 at src/ 30:13
        _3 = move _1;                    // bb0[2]: scope 0 at src/ 30:13
        _2 = move _3 as std::boxed::Box<dyn GeneralExpression> (Unsize); // bb0[3]: scope 0 at src/ 30:13
        StorageDead(_3);                 // bb0[4]: scope 0 at src/ 30:13
        _0 = move _2 as std::boxed::Box<dyn GeneralExpression> (Unsize); // bb0[5]: scope 0 at src/ 30:13
        StorageDead(_2);                 // bb0[6]: scope 0 at src/ 31:6
        return;                          // bb0[7]: scope 0 at src/ 31:6

The actual assembly for it is simply loading the new vtbl pointer:

<playground::DummyExpr as playground::Expression<f64>>::into_boxed_general:
	leaq	.L__unnamed_2(%rip), %rdx
	movq	%rdi, %rax

Alright, all that said - do you really need Expression and GeneralExpression? It seems like you can make your life a lot easier by just sticking to GeneralExpression and removing Expression altogether.

1 Like

Ok I have to have a closer look at your solution tomorrow.
However, the Expression<T> allows me for direct use of, e.g. f64, during evaluation of nested expressions. If I only use GeneralExpression I always have to check if the returned Value is of the corret type.

@vitalyd Again thank you for your efforts helping me. I’ve been trying around a hole day and have come to a working solution.

Your Playgroud example gave me a good starting point the only drawback was that an additional impl_general_for!(bool) broke the example.
However the additional method into_boxed_general() worked well, so the only prolem left was to implement GeneralExpression for all impl’s of Expression. I thought

impl<T: ExpType> GeneralExpression for Expression<T> {...}

would do this for me but it seems not to work correctly (or I don’t understand that impl right). In the end I always got compiler errors like:

// I modified the message in order to hide some context details.
error[E0277]: the trait bound `...::IfClause<T>: ...::GeneralExpression` is not satisfied                                                                                                          
   --> src/.../expressions/                                                                                                                                                                                                            
6   |                 self                                                                                                                                                                                                                                           
    |                 ^^^^ the trait `...::GeneralExpression` is not implemented for `...::IfClause<T>`                                                                                            
207 |     impl_into_boxed_general!();                                                                                                                                                                                                                                
    |     --------------------------- in this macro invocation                                                                                                                                                                                                       
    = note: required for the cast to the object type `dyn ...::GeneralExpression` 

My solution for now is to implement GeneralExpression by hand on each of my expression structs. I failed in writting a suitable macro for this because I’m not that into macros and my expressions are very diverse, e.g.:

struct IfClause<T> {
  cond: Box<dyn Expression<bool>>,
  then: Box<dyn Expression<T>>,
  else_: Box<dyn Expression<T>>,

impl<T: ExpType> Expression<T> for IfClause<T> {...}
impl<T: ExpType> GeneralExpression for IfClause<T> {...}

struct Negation(Box<dyn Expression<f64>>);

impl Expression<f64> for Negation {...}
impl GeneralExpression for Negation {...}

struct Comparison<T> {
  left: Box<dyn Expression<T>>,
  op: Operator,
  right: Box<dyn Expression<T>>,

impl Expression<bool> for Comparison<f64> {...}
impl GeneralExpression for Comparison<f64> {...}

impl Expression<bool> for Comparison<bool> {...}
impl GeneralExpression for Comparison<bool> {...}

// and so on