自定义指针类型的安全包装？

Question

我正在尝试创建一个包含对父级和子级的引用的数据结构，如下所示：

pub struct TreeBox<T> {
    value: T,
    parent: Option<*mut TreeBox<T>>,
    children: Vec<*mut TreeBox<T>>,
}

这个结构可以有父级和子级，当被删除时，它会警告父级和子级它不再存在：

impl<T> Drop for TreeBox<T> {
    fn drop(&mut self) {
        for child in self.children.iter() {
            unsafe {
                let child = &mut **child;
                child.parent = None;
            }
        }
        if let Some(parent) = self.parent {
            unsafe {
                let parent = &mut *parent;
                for (i, child) in parent.children.iter().enumerate() {
                    if *child == self {
                        parent.children.remove(i);
                        break;
                    }
                }
            }
        }
    }
}

现在，没有什么可以阻止我这样做：

let mut tree_box: TreeBox<String> = String::from("Hello").into();
let child = tree_box.create_child(String::from("World"));

let child_ref = tree_box.children().next().unwrap();
drop(child);

println!("child_ref: {}", child_ref.value());
assert_eq!(child_ref.value(), &"World".to_string());

当函数像下面这样实现时，这个例子就有效，即使在删除子项之后，我也能恢复它的值。现在，我猜这是不安全的，我正在访问丢失的内存，但由于它尚未被替换，所以工作正常。

我想围绕这个结构创建一个安全的包装器，那么我可以实现什么机制来防止这种事情发生？

impl<T> TreeBox<T> {
    pub fn create_child(&mut self, value: T) -> TreeBox<T> {
        let child = TreeBox{
            value,
            parent: Some(self),
            children: Vec::new(),
        };
        let child_ref = &child_ref as *const TreeBox<T> as *mut TreeBox<T>;
        self.children.push(child_ref);
        child
    }

    pub fn value(&self) -> &T {
        &self.value
    }

    pub fn children(&self) -> impl Iterator<Item = &TreeBox<T>> {
        self.children.iter().map(|child| {
            unsafe {
                &**child
            }
        })
    }
}

impl<T> From<T> for TreeBox<T> {
    fn from(value: T) -> Self {
        TreeBox{
            value,
            parent: None,
            children: Vec::new(),
        }
    }
}

Answer 1

您已经做出了决定：节点的所有者将是调用代码（创建它们的代码）。简而言之，这个决定是错误的（或者很可能是错误的）。

为这种数据结构实现安全接口很困难。 真的很难。算了，即使为这样的代码开发一个正确的“不安全”实现也是极其困难的（而且你没有这样做，不是正确的）。你不应该搞乱它，除非你“真的”知道自己在做什么。从您编写的代码来看，您可能不知道。 如果你想看看这样的数据结构是如何实现的，请看tokio的侵入式链表。它们比树更简单，但它们仍然需要复杂的代码，其中 Rust 的细节和最难的部分（例如固定）尚未确定。

但你可能不

需要

这样：在 Rust 的典型数据结构中，节点的所有者是

数据结构本身

。例如，Vec 以及 LinkedList

就是这种情况。 LinkedList需要相互指针（下一个和上一个），但只要一切都是内部的，就可以保持封装。公开一个安全的接口来访问节点，并在内部管理一切。例如，您可以保留相同的

TreeBox

声明，但不使用指向

borrow

节点的指针，只有

parent

链接将被借用，但子链接将是 owning （概念上；原始指针本身并不表明他们是借用还是拥有）。这意味着您只向外部公开对它们的引用，但树会分配它们并在需要时销毁它们。实现这样的数据结构仍然很困难；当然，最好的是完全避免不安全的代码（或者使用 Rc<RefCell> 和

Weak<RefCell>

，或者使用索引或诸如

petgraph 之类的库来简化事情）。但这样一来，至少是可行

。