data-structures - 如何在安全的Rust中遍历相互递归的图？

Question

How do I express mutually recursive structures in 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混合解决方案。现在，父级和子级只是对Node的引用，但是可以使用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!")
    }
}

现在，竞技场拥有每个节点，而不是 parent 拥有自己的 child (这只是实现细节，并不妨碍任何功能)。结果，不需要将父级传递给 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![]),
    })
}