在Rust中构建计算图二叉树：寻求unsafe替代的安全实现方案

问题背景 #

我正用二叉树构建简单计算图，知道Rust里链表类结构实现难度高，但这个结构刚好适配我的需求。试过用Box和Rc<RefCell>实现子节点但没达到预期，于是用了unsafe代码（如下）。想知道有没有安全的实现方式，以及当前unsafe用法的风险程度。

现有unsafe代码 #

use std::ops::{Add, Mul};

#[derive(Debug, Copy, Clone)]
struct MyStruct {
    value: i32,
    lchild: Option<*mut MyStruct>,
    rchild: Option<*mut MyStruct>,
}

impl MyStruct {
    unsafe fn print_tree(&mut self, set_to_zero: bool) {
        if set_to_zero {
            self.value = 0;
        }
        println!("{:?}", self);
    
        let mut nodes = vec![self.lchild, self.rchild];
        while nodes.len() > 0 {
            let child;
            match nodes.pop() {
                Some(popped_child) => child = popped_child.unwrap(),
                None => continue,
            }

            if set_to_zero {
                (*child).value = 0;
            }
            println!("{:?}", *child);
            
            if !(*child).lchild.is_none() {
                nodes.push((*child).lchild);
            }
            if !(*child).rchild.is_none() {
                nodes.push((*child).rchild);
            }
        }
        
        println!("");
    }
}

impl Add for MyStruct {
    type Output = Self;
    fn add(self, other: Self) -> MyStruct {
        MyStruct{
            value: self.value + other.value,
            lchild: Some(&self as *const _ as *mut _),
            rchild: Some(&other as *const _ as *mut _),
        }
    }
}

impl Mul for MyStruct {
   type Output = Self;
   fn mul(self, other: Self) -> MyStruct {
        MyStruct{
            value: self.value * other.value,
            lchild: Some(&self as *const _ as *mut _),
            rchild: Some(&other as *const _ as *mut _),
        }
   }
}

fn main() {
    let mut tree: MyStruct;
    
    {
        let a = MyStruct{ value: 10, lchild: None, rchild: None };
        let b = MyStruct{ value: 20, lchild: None, rchild: None };
        
        let c = a + b;
        println!("c.value: {}", c.value); // 30
        
        let mut d = a + b;
        println!("d.value: {}", d.value); // 30
        
        d.value = 40;
        println!("d.value: {}", d.value); // 40
        
        let mut e = c * d;
        println!("e.value: {}", e.value); // 1200
        
        unsafe {
            e.print_tree(false); // correct values
            e.print_tree(true); // all zeros
            e.print_tree(false); // all zeros, everything is set correctly
        }
        
        tree = e;
    }
    
    unsafe { tree.print_tree(false); } // same here, only zeros
}

当前unsafe代码的核心风险 #

1. 悬垂指针导致未定义行为 #

在Add和Mul的实现中，你保存的是函数参数self和other的指针。但这些参数是按值传递的，函数执行完毕后就会被销毁，对应的内存会被回收或重新利用。后续通过这些指针访问内存时，属于悬垂指针访问，这是Rust中明确的未定义行为，可能导致程序崩溃、数据损坏或其他不可预测的结果。

比如main里的代码块结束后，a和b已经被销毁，但tree变量中的e还持有指向它们的指针，此时调用tree.print_tree访问这些指针，完全是在操作无效内存。

2. 违反借用规则引发数据竞争 #

print_tree中通过裸指针直接修改节点的value，绕过了Rust的借用检查器。这意味着可能同时存在多个可变引用指向同一个节点，违反了"一个值同一时间只能有一个可变引用"的规则，可能引发数据竞争或内存不一致问题。

3. 非法的可变性转换 #

代码中&self as *const _ as *mut _将不可变引用强制转换为可变指针，这破坏了原有的可变性语义。如果原对象是不可变的，这种转换后修改值会导致未定义行为。

安全实现方案：使用Rc<RefCell<Node>> #

计算图需要节点间共享所有权，同时允许修改节点值，Rc<RefCell<Node>>刚好能满足这两个需求：

• Rc：实现共享所有权，确保只要有引用存在，节点就不会被销毁，彻底避免悬垂指针。
• RefCell：提供内部可变性，允许在共享引用的情况下修改节点值，同时在运行时检查借用规则，避免数据竞争。

安全实现代码示例 #

use std::ops::{Add, Mul};
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug, Clone)]
struct Node {
    value: i32,
    lchild: Option<Rc<RefCell<Node>>>,
    rchild: Option<Rc<RefCell<Node>>>,
}

impl Node {
    // 创建叶子节点
    fn new(value: i32) -> Self {
        Node {
            value,
            lchild: None,
            rchild: None,
        }
    }

    // 遍历树并打印，可选将节点值设为0
    fn print_tree(&self, set_to_zero: bool) {
        // 处理当前节点
        let mut current_node = Rc::new(RefCell::new(self.clone()));
        if set_to_zero {
            current_node.borrow_mut().value = 0;
        }
        println!("{:?}", current_node.borrow());

        // 初始化待遍历的子节点队列
        let mut nodes = Vec::new();
        if let Some(ref child) = self.lchild {
            nodes.push(child.clone());
        }
        if let Some(ref child) = self.rchild {
            nodes.push(child.clone());
        }

        // 广度优先遍历子节点
        while let Some(node) = nodes.pop() {
            let mut borrowed_node = node.borrow_mut();
            if set_to_zero {
                borrowed_node.value = 0;
            }
            println!("{:?}", *borrowed_node);

            // 添加子节点到队列
            if let Some(ref child) = borrowed_node.lchild {
                nodes.push(child.clone());
            }
            if let Some(ref child) = borrowed_node.rchild {
                nodes.push(child.clone());
            }
        }
        println!();
    }
}

// 实现加法操作，创建新节点并关联左右子节点
impl Add for Node {
    type Output = Self;
    fn add(self, other: Self) -> Self {
        Node {
            value: self.value + other.value,
            lchild: Some(Rc::new(RefCell::new(self))),
            rchild: Some(Rc::new(RefCell::new(other))),
        }
    }
}

// 实现乘法操作，逻辑同加法
impl Mul for Node {
    type Output = Self;
    fn mul(self, other: Self) -> Self {
        Node {
            value: self.value * other.value,
            lchild: Some(Rc::new(RefCell::new(self))),
            rchild: Some(Rc::new(RefCell::new(other))),
        }
    }
}

fn main() {
    let mut tree: Node;

    {
        let a = Node::new(10);
        let b = Node::new(20);

        let c = a + b;
        println!("c.value: {}", c.value); // 输出30

        let mut d = Node::new(10) + Node::new(20);
        println!("d.value: {}", d.value); // 输出30

        d.value = 40;
        println!("d.value: {}", d.value); // 输出40

        let mut e = c * d;
        println!("e.value: {}", e.value); // 输出1200

        e.print_tree(false); // 打印所有节点的原始值
        e.print_tree(true); // 将所有节点值设为0并打印
        e.print_tree(false); // 打印所有节点的0值

        tree = e;
    }

    tree.print_tree(false); // 代码块结束后仍能正常访问，输出0值
}

安全实现的优势 #

1. 无悬垂指针：Rc会跟踪节点的引用计数，只有当所有引用都被销毁时，节点才会被回收。
2. 内存安全：RefCell在运行时检查借用规则，确保同一时间只有一个可变引用，避免数据竞争。
3. 符合Rust语义：所有操作都在安全边界内，无需unsafe代码，编译器能完全保证内存安全。

内容的提问来源于stack exchange，提问作者Aurelien Montmejat