有Rc指针可变性的问题

Question

我试图实现一个简单的树结构与Rc指针:

use std::rc::Rc;
fn main() {
println!("Hello, world!");
}
enum Expr {
B(i128),
A(Rc<Expr>, Rc<Expr>),
O(Rc<Expr>, Rc<Expr>),
}
struct Node  {
data: Rc<Expr>,
parent: Option<Rc<Node>>,
children: Vec<Rc<Node>>,
}
impl Node {
fn add_to_children(mut self, node: &Rc<Node>) {
self.children.push(Rc::clone(node))
}
fn set_as_parent(mut self, node: &Rc<Node>) {
self.parent = Some(Rc::clone(node))
}
fn link_parent_child(parent: &mut Rc<Node>, child: &mut Rc<Node>) {
println!("eheeh");

parent.add_to_children(&child);
child.set_as_parent(&parent);
}
}

但是不能编译:

error[E0507]: cannot move out of an `Rc`
--> src/main.rs:32:9
|
32 |         parent.add_to_children(&child);
|         ^^^^^^^-----------------------
|         |      |
|         |      value moved due to this method call
|         move occurs because value has type `Node`, which does not implement the `Copy` trait
|
note: this function takes ownership of the receiver `self`, which moves value
--> src/main.rs:21:28
|
21 |     fn add_to_children(mut self, node: &Rc<Node>) {

实现这种树的更好方法是什么?是我的签名错了?

Answer 1

您的add_to_children和set_as_parent方法占用mut self，这意味着它们消耗self并试图移出Rc。这是不允许的，因为可能存在对该对象的其他引用。

方法应该采取&mut self…但是您会遇到另一个问题:Rc只公开不可变引用。因为，同样，可能有多个引用。

解决这个问题的方法是内部可变性。在您的示例中，RefCell是最简单的—它本质上是一个单线程锁，一次只允许一个位置可变访问。它不是指针，也不会自己在堆上分配——它只是包装底层的值。

还有另一个问题:因为你的父节点和子节点都通过Rc相互引用，你最终会得到一个循环引用，这意味着当你删除它们时，你的节点不会释放内存。使用std::rc::Weak作为父引用可以解决这个问题。

正如Chaymin Friedman指出的那样，Rust关于可变性的规则可能会使实现树结构变得有些困难，特别是当它包含父引用时。crates.io上有许多板条箱使用各种技术实现了这种树状结构。