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

Question

我昨天开始使用 Rust 参加今年的 Advent of Code。挑战 7 让您从文本文件中解析树结构。输入看起来像这样:

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

这种格式代表一棵从“根”开始的树； “root”有两个 child (“child1”和“child2”)，“child1”有一个 child (“child3”)。 “child2”和“child3”没有 child 。该站点永远不会向您发送具有循环的输入。

解析不是问题，但我在构建树结构时遇到了问题。

如果这是 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_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());
        }
    }
}

这不会构建:借用检查器非常不高兴我试图从构建树的循环中双重借用可变的。

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 的目标是找到根节点，因此它可能不是最佳选择。

解决借用冲突问题的主要解决方案是使用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());
        }
    }
}