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

Question

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

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

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

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

В C++ 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 возвращенный заимствованный указатель на добавленный компонент? или ящик?

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

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

Answer 1

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

Лучший способ реализации этого шаблона является использование небезопасного кода и сырых указателей, или существующей абстракции, которая оборачивает эту функциональность в безопасном апи, например 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 
} 

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

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

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

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