我如何反序列化 Rust 中的引用树？

Question

我昨天开始使用 Rust 参加今年的 Advent of Code。挑战 7 让您从文本文件中解析树结构。输入如下所示：

root -> child1, child2
child1 -> child3
child2
child3

此格式表示从 "root" 开始的树； "root"有两个children（"child1"和"child2"），"child1"有一个child（"child3"）。 "child2"和"child3"没有children。该站点永远不会向您发送具有循环的输入。

解析没有问题，但我在构建树结构时遇到问题。

如果这是 C++，我会这样写：

struct Program {
    string name;
    vector<string> children;
};

struct ProgramNode {
    string& name;
    vector<ProgramNode*> children;

    ProgramNode(string& name);
};

vector<Program> programs = parse_programs();
unordered_map<string, ProgramNode> program_nodes;
for (Program& program : programs) {
    program_nodes.emplace(program.name, ProgramNode(program.name));
}

for (Program& program : programs) {
    ProgramNode& node = program_nodes.at(program.name);
    for (string& child : program.children) {
        node.children.push_back(&program_nodes.at(child));
    }
}

这会在第一步中构建名称到 "program" 的映射，然后在第二步中填充对 "child programs" 的引用。如果您假设 program_map 不会超过 programs，这是安全的。然后，如果你知道根节点的名称，你可以做 ProgramNode& root = program_nodes.at(root_name) 并玩弄你的树。

我正在尝试用 Rust 编写相同的东西，但我在使用借用检查器时遇到了问题。到目前为止，我有这样的事情（没有有趣的细节panic）：使用 std::collections::HashMap;

struct Program {
    name: String,
    children: Vec<String>,
}

struct ProgramNode<'a> {
    name: &'a str,
    children: Vec<&'a ProgramNode<'a>>,
}

impl<'a> ProgramNode<'a> {
    fn new(input: &'a Program) -> ProgramNode {
        panic!();
    }
}

fn parse_programs() -> Vec<Program> {
    panic!();
}

fn main() {
    let programs = parse_programs();

    let mut program_nodes = HashMap::new();
    for program in &programs {
        program_nodes.insert(&program.name, ProgramNode::new(&program));
    }

    for program in &programs {
        let mut program_node = program_nodes.get_mut(&program.name).unwrap();
        for child in &program.children {
            program_node
                .children
                .push(&program_nodes.get_mut(&child).unwrap());
        }
    }
}

这不会构建：借用检查器非常不高兴我试图 double-borrow 从构建树的循环中可变。

error[E0597]: borrowed value does not live long enough
  --> src/main.rs:36:63
   |
36 |                 .push(&program_nodes.get_mut(&child).unwrap());
   |                        -------------------------------------- ^ temporary value dropped here while still borrowed
   |                        |
   |                        temporary value created here
...
39 | }
   | - temporary value needs to live until here
   |
   = note: consider using a `let` binding to increase its lifetime

error[E0499]: cannot borrow `program_nodes` as mutable more than once at a time
  --> src/main.rs:32:32
   |
32 |         let mut program_node = program_nodes.get_mut(&program.name).unwrap();
   |                                ^^^^^^^^^^^^^ second mutable borrow occurs here
...
36 |                 .push(&program_nodes.get_mut(&child).unwrap());
   |                        ------------- first mutable borrow occurs here
...
39 | }
   | - first borrow ends here

error[E0499]: cannot borrow `program_nodes` as mutable more than once at a time
  --> src/main.rs:36:24
   |
32 |         let mut program_node = program_nodes.get_mut(&program.name).unwrap();
   |                                ------------- first mutable borrow occurs here
...
36 |                 .push(&program_nodes.get_mut(&child).unwrap());
   |                        ^^^^^^^^^^^^^ second mutable borrow occurs here
37 |         }
38 |     }
   |     - first borrow ends here

当然，借用检查器是绝对正确的。这让我想到了一个问题：我正在尝试做的事情是否可行？

Answer 1

使用拥有的值而不是不可变的引用来为树建模更容易：一个节点拥有它的直接子节点。但是，由于问题7的objective是找到根节点，所以这可能不是最好的选择。

解决借用冲突问题的主要解决方案是使用RefCell.

延迟借用检查到运行时。

use std::cell::RefCell;
use std::collections::HashMap;

struct Program {
    name: String,
    children: Vec<String>,
}

struct ProgramNode<'a> {
    name: &'a str,
    children: RefCell<Vec<&'a ProgramNode<'a>>>,
}

impl<'a> ProgramNode<'a> {
    fn new(input: &'a Program) -> ProgramNode { panic!(); }
}

fn parse_programs() -> Vec<Program> { panic!(); }

fn main() {
    let programs = parse_programs();

    let mut program_nodes = HashMap::new();
    for program in &programs {
        program_nodes.insert(&program.name, ProgramNode::new(&program));
    }

    for program in &programs {
        let mut program_node = program_nodes.get(&program.name).unwrap();
        for child in &program.children {
            program_node.children.borrow_mut().push(&program_nodes.get(&child).unwrap());
        }
    }
}

Answer 2

我发现在 Rust 中将某些树状对象实现为节点向量更容易。

每个节点都有一个id，就是它在vector中的位置，这个id作为一个指针。

struct Node {
    parent: usize,
    children: Vec<usize>,
}

根通常位于位置 0。

每当您通过将 Node 推到树向量上创建一个 Node 时，树向量 returns 其在插入之前的长度作为新 Node 的 ID。

如果您还需要删除节点，则必须稍微细化实现。

我如何反序列化 Rust 中的引用树？

How can I deserialize a tree of references in Rust?

tree

rust

borrow-checker