如何在安全的Rust中表达相互递归的数据结构？

Question

我正在尝试在Rust中实现类似scenegraph的数据结构.我想在安全 Rust中表示这个C++代码的等价物:

struct Node
{
    Node* parent; // should be mutable, and nullable (no parent)
    std::vector<Node*> child;

    virtual ~Node() 
    { 
        for(auto it = child.begin(); it != child.end(); ++it)
        {
            delete *it;
        }
    }

    void addNode(Node* newNode)
    {
        if (newNode->parent)
        {
            newNode->parent.child.erase(newNode->parent.child.find(newNode));
        }
        newNode->parent = this;
        child.push_back(newNode);
    }
}

我想要的属性:

• 父母拥有其子女的所有权
• 可以通过某种参考从外部访问节点
• 触摸一个事件的事件Node可能会改变整个树

Answer 1

Rust试图通过禁止您做可能不安全的事情来确保内存安全.由于此分析是在编译时执行的,因此编译器只能推断已知安全的操作子集.

在锈,你可以很容易地存储或者父的引用(借用母公司,从而防止突变)或子节点的名单(通过拥有它们,给你更多的自由),但不能两者都(不使用unsafe).这对于您的实现addNode尤其成问题,这需要对给定节点的父节点进行可变访问.但是,如果将parent指针存储为可变引用,那么,因为一次只能使用对特定对象的单个可变引用,所以访问父对象的唯一方法是通过子节点,并且您只需要能够拥有一个子节点,否则你有两个对同一父节点的可变引用.

如果你想避免不安全的代码,有很多选择,但他们都需要一些牺牲.

最简单的解决方案是简单地删除该parent字段.我们可以定义一个单独的数据结构,以便在遍历树时记住节点的父节点,而不是将其存储在节点本身中.

首先,让我们来定义Node:

#[derive(Debug)]
struct Node<T> {
    data: T,
    children: Vec<Node<T>>,
}

impl<T> Node<T> {
    fn new(data: T) -> Node<T> {
        Node { data: data, children: vec![] }
    }

    fn add_child(&mut self, child: Node<T>) {
        self.children.push(child);
    }
}

(我添加了一个data字段,因为如果没有节点上的数据,树就不是非常有用!)

现在让我们定义另一个结构来跟踪我们导航时的父级:

#[derive(Debug)]
struct NavigableNode<'a, T: 'a> {
    node: &'a Node<T>,
    parent: Option<&'a NavigableNode<'a, T>>,
}

impl<'a, T> NavigableNode<'a, T> {
    fn child(&self, index: usize) -> NavigableNode<T> {
        NavigableNode {
            node: &self.node.children[index],
            parent: Some(self)
        }
    }
}

impl<T> Node<T> {
    fn navigate<'a>(&'a self) -> NavigableNode<T> {
        NavigableNode { node: self, parent: None }
    }
}

如果您在导航时不需要改变树,并且可以保留父NavigableNode对象(这对于递归算法很有效,但是如果您想要存储NavigableNode一些,则效果不好),此解决方案可以正常工作其他数据结构并保持它周围).第二个限制可以通过使用除借来的指针之外的其他东西来缓解父项; 如果你想要最大的通用性,你可以使用Borrow特征来允许直接值,借用的指针,Boxes Rc,等等.

现在,我们来谈谈拉链.在函数式编程中,拉链用于"聚焦"数据结构的特定元素(列表,树,映射等),以便访问该元素需要恒定的时间,同时仍保留该数据结构的所有数据.如果您需要导航树并在导航过程中对其进行变异,同时保留向上导航的能力,则可以将树变成拉链并通过拉链执行修改.

以下是我们如何为Node上面定义的拉链实现的方法:

#[derive(Debug)]
struct NodeZipper<T> {
    node: Node<T>,
    parent: Option<Box<NodeZipper<T>>>,
    index_in_parent: usize,
}

impl<T> NodeZipper<T> {
    fn child(mut self, index: usize) -> NodeZipper<T> {
        // Remove the specified child from the node's children.
        // A NodeZipper shouldn't let its users inspect its parent,
        // since we mutate the parents
        // to move the focused nodes out of their list of children.
        // We use swap_remove() for efficiency.
        let child = self.node.children.swap_remove(index);

        // Return a new NodeZipper focused on the specified child.
        NodeZipper {
            node: child,
            parent: Some(Box::new(self)),
            index_in_parent: index,
        }
    }

    fn parent(self) -> NodeZipper<T> {
        // Destructure this NodeZipper
        let NodeZipper { node, parent, index_in_parent } = self;

        // Destructure the parent NodeZipper
        let NodeZipper {
            node: mut parent_node,
            parent: parent_parent,
            index_in_parent: parent_index_in_parent,
        } = *parent.unwrap();

        // Insert the node of this NodeZipper back in its parent.
        // Since we used swap_remove() to remove the child,
        // we need to do the opposite of that.
        parent_node.children.push(node);
        let len = parent_node.children.len();
        parent_node.children.swap(index_in_parent, len - 1);

        // Return a new NodeZipper focused on the parent.
        NodeZipper {
            node: parent_node,
            parent: parent_parent,
            index_in_parent: parent_index_in_parent,
        }
    }

    fn finish(mut self) -> Node<T> {
        while let Some(_) = self.parent {
            self = self.parent();
        }

        self.node
    }
}

impl<T> Node<T> {
    fn zipper(self) -> NodeZipper<T> {
        NodeZipper { node: self, parent: None, index_in_parent: 0 }
    }
}

要使用此拉链,您需要拥有树的根节点的所有权.通过获取节点的所有权,拉链可以移动物体以避免复制或克隆节点.当我们移动拉链时,我们实际上放下旧拉链并创建一个新拉链(虽然我们也可以通过变异来实现它self,但我认为它更清晰,加上它可以让你链接方法调用).

如果上述选项不令人满意,并且您必须绝对将节点的父节点存储在节点中,那么下一个最佳选项是Rc<RefCell<Node<T>>>用于引用父节点和子节点.Rc启用共享所有权,但增加了在运行时执行引用计数的开销.RefCell启用内部可变性,但增加了开销以跟踪运行时的活动借用.请参阅DK.使用Rc和实现的实现答案RefCell.

Answer 2

问题是这种数据结构本质上是不安全的; 它不具有拉斯特不使用直接等同unsafe.这是设计的.

如果您想将其转换为安全的Rust代码,您需要更具体地了解您想要的内容.我知道你列出了上面的一些属性,但是经常有人来到Rust会说"我想要我在这个C/C++代码中拥有的所有东西",直接答案就是"好吧,你做不到".

你也不可避免地要改变你的方法.你给出的例子有指针,没有任何所有权语义,可变别名和循环; 所有这些Rust都不允许你像C++一样忽略它.

最简单的解决方案是删除parent指针,并在外部维护(如文件系统路径).这也很适合借用,因为任何地方都没有循环:

pub struct Node1 {
    children: Vec<Node1>,
}

如果你需要父指针,你可以中途使用Ids代替:

use std::collections::BTreeMap;

type Id = usize;

pub struct Tree {
    descendants: BTreeMap<Id, Node2>,
    root: Option<Id>,
}

pub struct Node2 {
    parent: Id,
    children: Vec<Id>,
}

这BTreeMap实际上是你的"地址空间",不通过直接使用内存地址绕过借用和别名问题.

当然,这引入了一个给定的问题Id没有被绑定到特定的树,这意味着它所属的节点可能被破坏,现在你有一个有效的悬空指针.但是,这是你为混叠和变异付出的代价.它也不那么直接.

或者,您可以全力以赴并使用引用计数和动态借用检查:

use std::cell::RefCell;
use std::rc::{Rc, Weak};

// Note: do not derive Clone to make this move-only.
pub struct Node3(Rc<RefCell<Node3_>>);

pub type WeakNode3 = Weak<RefCell<Node3>>;

pub struct Node3_ {
    parent: Option<WeakNode3>,
    children: Vec<Node3>,
}

impl Node3 {
    pub fn add(&self, node: Node3) {
        // No need to remove from old parent; move semantics mean that must have
        // already been done.
        (node.0).borrow_mut().parent = Some(Rc::downgrade(&self.0));
        self.children.push(node);
    }
}

在这里,您将用于Node3在树的各个部分之间转移节点的所有权,以及WeakNode3用于外部引用.或者,您可以进行Node3克隆并将逻辑添加回来add以确保给定节点不会意外地保留错误父节点的子节点.

这并不比第二种选择严格好,因为这种设计绝对不能从静态借用检查中受益.第二个可以至少阻止你在编译时一次从两个地方改变图形; 在这里,如果发生这种情况,你就会崩溃.

关键是:你不能只拥有一切.您必须决定实际需要支持哪些操作.在这一点上,通常只是选择能够提供必要属性的类型.

Answer 3

在某些情况下，您也可以使用arena。竞技场保证存储在其中的值与竞技场本身具有相同的生存期。这意味着添加更多的值不会使任何现有的生命周期无效，但是会移动竞技场。因此，如果您需要返回树，则这种解决方案是不可行的。

通过从节点本身删除所有权来解决此问题。

这是一个示例，该示例还使用内部可变性来允许节点在创建后进行突变。在其他情况下，如果仅构造树然后简单地对其进行导航，则可以删除此可变性。

use std::{
    cell::{Cell, RefCell},
    fmt,
};
use typed_arena::Arena; // 1.6.1

struct Tree<'a, T: 'a> {
    nodes: Arena<Node<'a, T>>,
}

impl<'a, T> Tree<'a, T> {
    fn new() -> Tree<'a, T> {
        Self {
            nodes: Arena::new(),
        }
    }

    fn new_node(&'a self, data: T) -> &'a mut Node<'a, T> {
        self.nodes.alloc(Node {
            data,
            tree: self,
            parent: Cell::new(None),
            children: RefCell::new(Vec::new()),
        })
    }
}

struct Node<'a, T: 'a> {
    data: T,
    tree: &'a Tree<'a, T>,
    parent: Cell<Option<&'a Node<'a, T>>>,
    children: RefCell<Vec<&'a Node<'a, T>>>,
}

impl<'a, T> Node<'a, T> {
    fn add_node(&'a self, data: T) -> &'a Node<'a, T> {
        let child = self.tree.new_node(data);
        child.parent.set(Some(self));
        self.children.borrow_mut().push(child);
        child
    }
}

impl<'a, T> fmt::Debug for Node<'a, T>
where
    T: fmt::Debug,
{
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "{:?}", self.data)?;
        write!(f, " (")?;
        for c in self.children.borrow().iter() {
            write!(f, "{:?}, ", c)?;
        }
        write!(f, ")")
    }
}

fn main() {
    let tree = Tree::new();
    let head = tree.new_node(1);
    let _left = head.add_node(2);
    let _right = head.add_node(3);

    println!("{:?}", head); // 1 (2 (), 3 (), )
}