Как пройти взаимно рекурсивный граф в безопасном Rust?

Question

Как мне express взаимно рекурсивные структуры в Rust? объясняет, как представлять графоподобные структуры, но не объясняется, как ходить график (только чтобы добавить больше детей). Решение Rc<RefCell<T>>, которое я пытался адаптировать, не компилировалось.

Я ищу способ спроектировать и пройтись по графоподобной структуре в безопасном Rust, используя Rc<T> и / или RefCell<T> для интерьера изменчивость. Мой текущий Node не компилируется из-за &mut T правил псевдонимов:

struct Node {
    parent: Option<&mut Node>, // a mutable reference to the Node's owner
    children: Vec<Node>,       // each Node owns its children
}

impl Node {
    fn add_child(&mut self, x: Node) {
        self.children.push(x);
    }
    fn get_child(&mut self, i: usize) -> &mut Node {
        &mut self.children[i]
    }
    fn get_parent(&mut self) -> &mut Node {
        self.parent.expect("No parent!")
    }
}

Пример функциональности:

let mut top_node = Node::new(None); 

let mut ptr = &mut top_node; 

ptr.add_child(Node::new(&mut ptr)); // add a child to top_node

ptr = ptr.get_child(0); // walk down to top_node's 0th child.

ptr = ptr.get_parent(); // walk back up to top_node

Я неоднократно переписывал эту реализацию, заменяя &mut T комбинациями Rc, Weak, RefCell и RefMut безрезультатно. Я не достаточно разбираюсь в базовом управлении памятью.

Может ли кто-то с большим опытом использования внутренней изменчивости объяснить, как правильно проектировать и обходить этот график?

Answer 1

Ключом было использование гибридного решения Arena / Cell. Родители и дети теперь являются просто ссылками на узлы, но изменчивость включается с помощью Cell и RefCell:

struct Node<'a> {
    arena: &'a Arena<Node<'a>>,
    parent: Cell<Option<&'a Node<'a>>>,
    children: RefCell<Vec<&'a Node<'a>>>,
}

impl<'a> Node<'a> {
    fn add_child(&'a self) {
        let child = new_node(self.arena);
        child.parent.set(Some(self));
        self.children.borrow_mut().push(child);
    }
    fn get_child(&'a self, i: usize) -> &'a Node<'a> {
        self.children.borrow()[i]
    }
    fn get_parent(&'a self) -> &'a Node<'a> {
        self.parent.get().expect("No Parent!")
    }
}

Теперь Arena владеет каждым узлом вместо родителей, владеющих своими детьми (это только деталь реализации и не мешает никакой функциональности). В результате нет необходимости передавать родителя на add_child:

let arena: Arena<Node> = Arena::new();
let top_node = new_node(&arena);
top_node.add_child();

let mut ptr = top_node.get_child(0);

ptr.add_child();

ptr = ptr.get_child(0);
ptr = ptr.get_parent();

Решение использует следующую вспомогательную функцию для запуска и сохранения владения на Arena:

fn new_node<'a>(arena: &'a Arena<Node<'a>>) -> &'a mut Node<'a> {
    arena.alloc(Node {
        arena: arena,
        parent: Cell::new(None),
        children: RefCell::new(vec![]),
    })
}