Как моделировать сложные рекурсивные структуры данных (графики)?

Меня очень интересует Rust, и теперь я начинаю свой первый нетривиальный проект на этом языке. У меня все еще есть небольшая проблема, полностью понимающая концепции заимствования и жизни.

Приложение представляет собой логический логический симулятор, в котором компоненты определяются рекурсивно (в терминах других компонентов и их взаимосвязей).

Мой текущий план заключается в том, чтобы реализовать это так же, как и в С++, имея структуру Component, владеющую вектором Компонентов (его подкомпонентов) и вектором Nets, описывающим взаимосвязи между этими компонентами:

pub struct Pin {
    name: String
}

pub struct Net<'a> {
    nodes: Vec<(&'a Component<'a>,&'a Pin)>
}

pub struct Component<'a> {
    sub_components: Vec<Box<Component<'a>>>,
    in_pins: Vec<Pin>,
    out_pins: Vec<Pin>,
    netlist: Vec<Net<'a>>
}

impl<'a> Component<'a> {
    pub fn new() -> Component<'a> {
        ...
    }

    pub fn add_subcomponent( & mut self, comp: Component<'a> ) {
        // -> &Box<Component<'a>> ??
        ....
    }
}

В С++ Net было бы легко реализовать как массив указателей на Компоненты, но я не уверен, что это лучший способ сделать это в Rust, я полагаю, я должен использовать заимствованные указатели? Или есть лучший способ?

Рассмотрим следующую основную:

fn main() {
    let sub1 = Component::new();
    let sub2 = Component::new();
    let circuit = Component::new();

    circuit.add_subcomponent( sub1 );
    circuit.add_subcomponent( sub2 );
    // sub1 and sub2 are now empty...
}

Как настроить схему для создания сети между sub1 и sub2? Должен ли я добавить add_subcomponent возвращенный заимствованный указатель на добавленный компонент? или Коробка?

Было бы здорово, если бы кто-то мог указать мне в правильном направлении.

Большое спасибо.

Ответы

Ответ 1

Вы не можете представлять произвольную структуру графа в безопасной ржавчине.

Лучший способ реализовать этот шаблон - использовать небезопасный код и необработанные указатели или существующую абстракцию, которая обертывает эту функциональность в безопасном api, например http://static.rust-lang.org/doc/master/std/cell/struct.RefCell.html

Например, типичным двунаправленным связанным списком будет:

struct Node {
  next: Option<Node>, // Each node 'owns' the next one
  prev: *mut Node     // Backrefs are unsafe
}

Там было множество "безопасных" реализаций, где у вас есть что-то вроде:

struct Node {
    id: u32,
    next: u32,
    prev: u32
}
struct Nodes {
  all:Vec<Node>,
  root:Option<Node>
}

Это "технически" безопасно, но это ужасная картина; он нарушает все правила безопасности, просто применяя ручные указатели. Я категорически против этого.

Вы можете попробовать использовать ссылки, например:

struct Container<'a> {
  edges:Vec<Edge<'a>>,
  pub root: Node
}

struct Node {
  children:Vec<Node>  
}

struct Edge<'a> {
  n1: &'a Node,
  n2: &'a Node
}

... но ты сразу же наткнешься в адский чек. Например, когда вы удаляете node, как средство проверки займа знает, что связанные ссылки в "ребрах" больше не действительны?

Хотя вы могли бы определить структуры, их заполнение будет крайне затруднительным.

Я знаю, что, вероятно, довольно неудовлетворительный ответ; вам может быть полезно найти github для "графа ржавчины" и "дерева ржавчины" и посмотреть на реализации, сделанные другими людьми.

Обычно они обеспечивают однократное владение поддеревом родительскому объекту.