Rc内部的下行特征用于AST操作

Question

我正试图在Rust中操纵AST.会有很多操作,我希望我的树是不可变的,所以为了节省时间,所有引用都将是Rcs.

我的树节点将如下所示:

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

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

我想用另一个相同类型的节点替换给定类型的随机节点.要在树上进行通用操作,我已经做了一个特性:

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

所有节点都实现了这一点.这允许我通过简单地调用来遍历树而不必为每个操作解构每个节点类型children().

我还希望克隆一个节点,同时只更新其中一个子节点,并保留其他子节点.假设我已经能够生成正确的具体类型的节点(如果我错了,我很高兴程序会出现恐慌).我将在特征中添加以下方法:

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

我的计划是把孩子们带回来childen(),替换他们中的一个,然后调用clone_with_children()构建一个相同枚举变量的节点,但是替换了一个节点.

我的问题是如何写clone_with_children().

我需要向下转换Rc<AstNode>到Rc<Expression>(或你有什么),同时保持内部的引用计数Rc相同,但没有我已经找到了向下转换库似乎是能够做到这一点.

我想要的是什么,或者我应该完全不同地做到这一点？

Answer 1

不,你不能垂头丧气Rc<Trait>到Rc<Concrete>,因为特质对象,如Rc<Trait>不包含AOUT具体类型的数据属于任何信息.

下面是摘录的官方文档,适用于所有特质对象(&Trait,Box<Trait>,Rc<Trait>):

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

该data字段指向结构本身,该vtable字段指向函数指针的集合,每个特征对应一个特征.在运行时,这就是你所拥有的一切.而这还不足以重建结构的类型.(有Rc<Trait>,块data指向也包含强和弱引用计数,但没有其他类型信息.)

但至少还有3种其他选择.

首先,您可以将需要对Expressions或Conditions 执行的所有操作添加到特征中AstNode,并为每个结构实现它们.这样,您永远不需要调用特征对象上不可用的方法,因为特征包含您需要的所有方法.

这也需要更换大部分Rc<Expression>,并Rc<Condition>与树中的成员Rc<AstNode>,因为你不能垂头丧气Rc<AstNode>(见下文约Any):

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

在这一个变化可能是写上的方法AstNode是采取&self和返回引用各种具体类型:

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

其次,你可以创建另一个枚举是统一Condition和Expression,并废除特质完全的对象.这就是我在自己的Scheme解释器的AST中所做的.使用此解决方案,不需要向下转换,因为所有类型信息都在编译时出现.(同样有了这个解决方案,你肯定要更换Rc<Condition>或者Rc<Expression>如果你需要更换Rc<Node>它.)

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

第三种选择是根据需要使用Any,.downcast_ref()或者Rc::downcast(或者目前仅在夜间)使用每种Rc<Any>具体类型.

对轻微变化将是添加一个方法fn as_any(&self) -> &Any { self }来AstNode,然后你可以调用Expression的方法(即采取&self由写)node.as_any().downcast_ref::<Expression>().method_on_expression().但是,目前还没有办法(安全)上溯造型的Rc<Trait>一种Rc<Any>,即使没有它不能正常工作的真正原因.

Any严格来说,是最接近你问题答案的东西.我不推荐它,因为向下转换或需要向下转换,往往表明设计不佳.即使在具有类继承的语言(如Java)中,如果您想要执行相同类型的操作(ArrayList<Node>例如,在一个节点中存储一堆节点),您也必须在基类或某个地方进行所有需要的操作.枚举你可能需要向下转换的所有子类,这是一个可怕的反模式.你在这里做的任何事情Any在复杂性上都可以与AstNode改为枚举相提并论.

tl; dr:您需要将AST的每个节点存储为一种类型:(a)提供您可能需要调用的所有方法,以及(b)统一您可能需要放入其中的所有类型.选项1使用特征对象,而选项2使用枚举,但它们原则上非常相似.第三种选择是Any用于启用向下转换.

进一步阅读的相关问答:

• 我可以用特征对象键入内省然后向下转换吗？
• 如何从盒装特征中获取结构参考？
• (Programmers.SE)将通用对象存储在容器中然后从容器中获取对象并向下转换对象是一种代码气味吗？