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

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

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

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<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.

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 also entails replacing most Rc<Expression> and Rc<Condition> members in the tree with Rc<AstNode>, since you can't downcast Rc<AstNode> (but see below about Any):

enum Condition {
    Equals(Rc<AstNode>, Rc<AstNode>),
    LessThan(Rc<AstNode>, Rc<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<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>.

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 present at compile time. (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>> { ... }
}

A third option is to use Any, and either .downcast_ref() or Rc::downcast (currently only on nightly) each Rc<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<Trait> to an Rc<Any>, even though there is no real reason it couldn't work.

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.

Related Q&A for further reading:

• 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?