Downcast traits inside Rc for AST manipulation

Question

I'm trying to manipulate ASTs in Rust. There will be lots of manipulations, and I want my trees to be immutable, so to save time all references will be Rcs.

My tree nodes will look like this:

enum Condition {
    Equals(Rc<Expression>, Rc<Expression>),
    LessThan(Rc<Expression>, Rc<Expression>),
    ...
}

enum Expression {
    Plus(Rc<Expression>, Rc<Expression>),
    ...
}

I want to replace a random node of a given type with another node of the same type. To do generic operations on trees I've made a trait:

trait AstNode {
    fn children(&self) -> Vec<Rc<AstNode>>;
}

And all nodes implement this. This allows me to walk the tree without having to destructure each node type for every operation, by simply calling children().

I also want to clone a node while updating only one of its children, and leaving the other ones in place. Assume that I've been able to generate nodes of the right concrete type (and I'm happy for the program to panic if I'm wrong). I'll add the following method to the trait:

trait AstNode {
    fn clone_with_children(&self, new_children: Vec<Rc<AstNode>>) -> Self
        where Self: Sized;
}

My plan is to take the children returned by childen(), replace one of them, and call clone_with_children() to construct a node of the same enum variant but with one node replaced.

My problem is how to write clone_with_children().

I need to downcast Rc<AstNode> to Rc<Expression> (or what have you), while keeping the refcount inside the Rc the same, but none of the downcasting libraries I've found seem to be able to do that.

Is what I want possible, or should I do it completely differently?

Answer 1

Note: In this answer I will use the dyn Trait syntax to make it more clear when a type is a trait object. The older way to write Rc<dyn Trait> is Rc<Trait>. See What does "dyn" mean in a type?

No, you can't downcast Rc<dyn Trait> to Rc<Concrete>, because trait objects like dyn Trait don't contain any information about the concrete type the data belongs to.

Here's an excerpt from the official documentation that applies to all pointers to trait objects (&dyn Trait, Box<dyn Trait>, Rc<dyn Trait>, etc.):

pub struct TraitObject {
    pub data: *mut (),
    pub vtable: *mut (),
}

The data field points to the struct itself, and the vtable field points to a collection of function pointers, one for each method of the trait. At runtime, that's all you have. And that's not sufficient to reconstruct the struct's type. (With Rc<dyn Trait>, the block data points to also contains the strong and weak reference counts, but no additional type information.)

But there are at least 3 other options.

Put the common behavior in the trait

First, you could add all the operations that you need to do on Expressions or Conditions to the trait AstNode, and implement them for each struct. This way you never need to call a method that isn't available on the trait object, because the trait contains all the methods you need.

This likely entails replacing most Rc<Expression> and Rc<Condition> members in the tree with Rc<dyn AstNode>, since you can't downcast Rc<dyn AstNode> (but see below about Any):

enum Condition {
    Equals(Rc<dyn AstNode>, Rc<dyn AstNode>),
    LessThan(Rc<dyn AstNode>, Rc<dyn AstNode>),
    ...
}

A variation on this might be writing methods on AstNode that take &self and return references to various concrete types:

trait AstNode {
    fn as_expression(&self) -> Option<&Expression> { None }
    fn as_condition(&self) -> Option<&Condition> { None }
    ...
}

impl AstNode for Expression {
    fn as_expression(&self) -> Option<&Expression> { Some(self) }
}

impl AstNode for Condition {
    fn as_condition(&self) -> Option<&Condition> { Some(self) }
}

Instead of downcasting Rc<dyn AstNode> to Rc<Condition>, just store it as an AstNode and call e.g. rc.as_condition().unwrap().method_on_condition(), if you're confident rc is in fact an Rc<Condition>.

Double down on enums

Second, you could create another enum that unifies Condition and Expression, and do away with trait objects entirely. This is what I have done in the AST of my own Scheme interpreter. With this solution, no downcasting is required because all the type information is in the enum variant. (Also with this solution, you definitely have to replace Rc<Condition> or Rc<Expression> if you need to get an Rc<Node> out of it.)

enum Node {
    Condition(Condition),
    Expression(Expression),
    // you may add more here
}
impl Node {
    fn children(&self) -> Vec<Rc<Node>> { ... }
}

Downcast with Any

A third option is to use Any, and Rc::downcast each Rc<dyn Any> into its concrete type as needed.

A slight variation on that would be to add a method fn as_any(&self) -> &Any { self } to AstNode, and then you can call Expression methods (that take &self) by writing node.as_any().downcast_ref::<Expression>().method_on_expression(). But there is currently no way to (safely) upcast an Rc<dyn Trait> to an Rc<dyn Any> (this could change in the future, though).

Any is, strictly speaking, the closest thing to an answer to your question. I don't recommend it because downcasting, or needing to downcast, is often an indication of a poor design. Even in languages with class inheritance, like Java, if you want to do the same kind of thing (store a bunch of nodes in an ArrayList<Node>, for example), you'd have to either make all needed operations available on the base class or somewhere enumerate all the subclasses that you might need to downcast to, which is a terrible anti-pattern. Anything you'd do here with Any would be comparable in complexity to just changing AstNode to an enum.

TL;DR

You need to store each node of the AST as a type that (a) provides all the methods you might need to call and (b) unifies all the types you might need to put in one. Option 1 uses trait objects, while option 2 uses enums, but they're pretty similar in principle. A third option is to use Any to enable downcasting.

See also

• Can I do type introspection with trait objects and then downcast it?
• How to get struct reference from boxed trait?
• (Programmers.SE) Is it a code smell to store generic objects in a container and then get object and downcast the objects from container?