如何将 Rust 中的树状结构展平为 Vec<&mut ...>？

Question

我在 Rust 中有一个树状结构：

#[derive(Debug, Clone)]
struct Dir {
    name: String,
    children: Vec<Node>,
}

#[derive(Debug, Clone)]
enum Node {
    File(File),
    Dir(Dir),
}

#[derive(Debug, Clone)]
struct FileSystem {
    root: Dir,
}

我想把这个结构压扁成一个

Vec<&mut Node>

（顺序不相关）。

我的想法是递归遍历树并将每个节点添加到 vec：

impl Node {
    fn flatten(&mut self, nodes: &mut Vec<&mut Node>) {
        nodes.push(self);

        if let Node::Dir(dir) = self {
            for node in dir.children.iter_mut() {
                node.flatten(nodes);
            }
        }
    }
}

显然我收到一个错误，因为

self

已经被移入

nodes

，但我不知道如何解决这个问题。我试过使用

Rc

和

RefCell

但我对它们知之甚少。

Answer 1

这是不可能的，如果你可以同时获得 2 个对孩子的可变引用，一个通过

self

引用，另一个通过对同一个

Vec

中的孩子的直接可变引用。

所以假设你有一棵这样的树：

let mut root = Dir {
    name: "root".into(),
    children: vec![],
};
let child = Dir {
    name: "child".into(),
    children: vec![],
};
root.children.push(child);
// assume this produces [&mut root, &mut root.children[0]]
let refs = root.flatten();
let child1 = &mut refs[0].children[0];
let child2 = refs[1];

child1

和

child2

都是对同一内存位置的可变引用，这在 Rust 中被认为是 undefined behavior。

如果你把你的孩子放在共享引用后面并使用内部可变性来恢复可变性，你可以展平嵌套结构，一种方法是这样做：

use std::{cell::RefCell, rc::Rc};
#[derive(Debug, Clone)]
struct Dir {
    name: String,
    children: Vec<Rc<RefCell<Dir>>>,
}

trait Flatten {
    fn flatten(self, flat: &mut Vec<Self>) where Self: Sized;
}
impl Flatten for Rc<RefCell<Dir>> {
    fn flatten(self, flat: &mut Vec<Self>) {
        flat.push(Rc::clone(&self));
        for child in &self.borrow().children {
            Rc::clone(child).flatten(flat);
        }
    }
}

impl Dir {
    fn new(name: impl Into<String>) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Dir {
            name: name.into(),
            children: Vec::new(),
        }))
    }
}

fn main() {
    let root = Dir::new("root");
    let child = Dir::new("child");
    let sibling = Dir::new("sibling");
    let grandchild = Dir::new("grandchild");
    child.borrow_mut().children.push(grandchild);
    root.borrow_mut().children.extend([child, sibling]);
    let mut refs = Vec::with_capacity(4);
    root.flatten(&mut refs);
    dbg!(refs);
}

Answer 2

我想扩展@cafce25 的回答：你不能扁平化为

Vec<&mut Dir>

因为这会给你两种方法来获得对同一事物的可变引用。其中一种方式通过

children

。因此：您仍然可以获得

Vec<&mut …>

，它只是不能包括访问

children

.

所以如果你例如有

#[derive(Debug, Clone)]
struct NodeCommon {
    name: String,
    …
}

#[derive(Debug, Clone)]
struct Dir {
    common: NodeCommon,
    children: Vec<Node>,
}

您可以使用上面的代码获得

Vec<&mut NodeCommon>

。 游乐场

虽然我想问：你会用那个

Vec

做什么？如果你只是为了改变一些东西而迭代它，那么为此构建一个

Vec

会有点浪费。一个更好的解决“抽象走过树”问题的方法可能是在每个

FnMut

:

 上调用 

Dir

impl Node {
    fn for_each_dir_mut<'a>(&'a mut self, f: &mut impl FnMut(&mut Dir)) {
        if let Node::Dir(dir) = self {
            f(dir);
            for node in dir.children.iter_mut() {
                node.for_each_dir_mut(f);
            }
        }
    }
}

游乐场