Rc内部的向下特性以进行AST操纵 [英] Downcast traits inside Rc for AST manipulation

问题描述

我正在尝试在Rust中操纵AST。会有很多操作，我希望我的树是不可变的，因此为了节省时间，所有引用都将是 Rc s。

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.

我的树节点如下所示：

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>>;
}

所有节点都实现了这一点。只需调用 children（），这使我可以走树而不必破坏每个节点的类型。

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;
}

我的计划是带回由 childen返回的孩子（），替换其中一个，然后调用 clone_with_children（）来构造一个具有相同枚举变量但替换了一个节点的节点。

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.

我的问题是如何写 clone_with_children（）。

我需要将 Rc< AstNode> 转换为 Rc< Expression> （或您拥有的东西），同时保持 Rc 内的refcount相同，但是我发现没有一个向下转换的库似乎能够做到这一点。

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?

推荐答案

不，您不能灰心 Rc< Trait> 到 Rc< Concrete> ，因为特征对象如 Rc< Trait> 不包含数据所属的具体类型的任何信息。

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.

此处摘录自适用于所有特征对象（& Trait ， Box< Trait> ， Rc< Trait> ）：

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

data 字段指向结构本身，而 vtable 字段指向一组函数指针，每个函数指针对应一个特征。在运行时，仅此而已。这还不足以重构结构的类型。 （对于 Rc< Trait> ，块 data 所指向的块也包含强引用计数和弱引用计数，但没有其他计数类型信息。）

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

，但至少还有其他3种选择。

But there are at least 3 other options.

首先，您可以添加所有您需要对 Expression s或 Condition s特质 AstNode 进行的操作code>，并为每个结构实现它们。这样，您就不需要调用trait对象上不可用的方法，因为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.

这也需要替换大多数<树中具有 Rc< AstNode> <的code> Rc< Expression> 和 Rc< Condition> 成员/ code>，因为您不能向下转换 Rc< AstNode> （但请参见以下有关任何的内容） ：

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>),
    ...
}

对此的一种变化可能是在 AstNode 上编写方法，该方法采用& self 并返回对各种具体方法的引用类型：

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) }
}

而不是向下转换 Rc < ; AstNode> 到 Rc< Condition> ，只需将其存储为 AstNode 并调用例如 rc.as_condition（）。unwrap（）。method_on_condition（），如果您确信 rc 实际上是 Rc<条件> 。

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

第二，您可以创建另一个统一 Condition 和 Expression ，并完全删除特征对象。这就是我在自己的Scheme解释器的AST中所做的事情。使用此解决方案，不需要向下转换，因为所有类型信息都在编译时出现。 （此外，使用此解决方案，如果您需要替换 Rc< Condition> 或 Rc< Expression> 从中获得 Rc< Node> 。）

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

第三种选择是使用 任何 ，或者 .downcast_ref（）或 Rc :: downcast （目前仅每晚），每个 Rc 根据需要转换为具体类型。

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.

对此稍作改动就是添加方法 fn as_any（& ; self）-> & Any {self} 到 AstNode ，然后可以调用 Expression 方法（通过编写 node.as_any（）。downcast_ref ::< Expression>（）。method_on_expression（）& self ） $ c>。但是，目前尚无法（安全地）上传将 Rc< Trait> 转换为 Rc< Any< ，即使没有真正的理由不能这样做。

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.

任何严格来说，它是对您问题的答案最接近的东西。我不建议这样做，因为向下转换或需要向下转换通常表示设计不佳。即使在具有类继承的语言（例如Java）中，如果您想做同样的事情（例如，将一堆节点存储在 ArrayList< Node> 中），您必须使所有必需的操作在基类上可用，或者在某个地方枚举您可能需要向下转换的所有子类，这是一个可怕的反模式。您在此处使用任何 c $ c>所做的任何事情，其复杂性都可以与将 AstNode 更改为一个枚举相媲美。

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：：您需要将AST的每个节点存储为（a）提供您可能需要的所有方法的类型。呼叫，然后（b）统一您可能需要放入的所有类型。选项1使用特征对象，而选项2使用枚举，但是它们在原理上非常相似。第三种选择是使用 Any 启用向下转换。

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:

• 如何从盒装特征中获取结构引用？


• （程序员。 SE）将通用对象存储在容器中然后从容器中获取对象并向下转换对象是否有代码味道？

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

这篇关于Rc内部的向下特性以进行AST操纵的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！