Пониженные черты внутри Rc для манипуляции AST

Я пытаюсь манипулировать AST в Rust. Будет много манипуляций, и я хочу, чтобы мои деревья были неизменными, поэтому для экономии времени все ссылки будут 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 то же самое, но ни одна из найденных мной библиотек не может это сделать.

Возможно ли то, что я хочу, или я должен сделать это совершенно по-другому?

Источник

1 ответ

Нет, ты не можешь опускать руки Rc<Trait> в Rc<Concrete>, потому что черта объектов, таких как Rc<Trait> не содержат никакой информации о конкретном типе данных.

Вот выдержка из официальной документации, которая относится ко всем объектам черты (&Trait, Box<Trait>, Rc<Trait>):

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

data поле указывает на саму структуру, а vtable поле указывает на коллекцию указателей функций, по одному для каждого метода признака. Во время выполнения это все, что у вас есть. И этого недостаточно для восстановления типа структуры. (С Rc<Trait>, блок data указывает на также содержит сильные и слабые ссылки, но без дополнительной информации о типе.)

Но есть как минимум 3 других варианта.

Во-первых, вы можете добавить все операции, которые вам нужно сделать на Expression с или Condition с чертой 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 и покончить с чертами объектов полностью. Это то, что я сделал в AST моего собственного интерпретатора Scheme. При таком решении не требуется даункастинг, поскольку вся информация о типе присутствует во время компиляции. (Также с этим решением, вы обязательно должны заменить 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 включить даункинг.

Связанные вопросы и ответы для дальнейшего чтения:

Источник
Другие вопросы по тегам