为什么 VecDeque is_empty 阻止进一步借用？

Question

我有一个可以正常工作的函数。我想稍微优化一下，将两个相似的代码块转换成闭包或函数。几次尝试后，我仍然看到一些借用检查器错误。看起来 VecDeque is_empty 阻止了更多代码。我不想仅仅为了满足借用检查器而更改队列和访问过的数据结构。可以这样做吗？

use std::collections::{VecDeque, HashSet, HashMap};

fn day_7() -> i32 {
    let lines: Vec<String> = r"light red bags contain 1 bright white bag, 2 muted yellow bags.
dark orange bags contain 3 bright white bags, 4 muted yellow bags.
bright white bags contain 1 shiny gold bag.
muted yellow bags contain 2 shiny gold bags, 9 faded blue bags.
shiny gold bags contain 1 dark olive bag, 2 vibrant plum bags.
dark olive bags contain 3 faded blue bags, 4 dotted black bags.
vibrant plum bags contain 5 faded blue bags, 6 dotted black bags.
faded blue bags contain no other bags.
dotted black bags contain no other bags.".split('\n').map(|s| s.to_owned()).collect();
    let root_name = String::from("shiny gold");

    let mut connections: HashMap<String, Vec<String>> = HashMap::new();

    for line in &lines {
        let arr: Vec<&str> = line.split(" bags contain ").collect();
        let parent = arr[0];
        let values: Vec<&str> = arr[1].split(", ").collect();
        for val in values {
            if val.starts_with("no other bags") { continue; }
            let parts: Vec<&str> = val.split_whitespace().collect();
            let child = format!("{} {}", parts[1], parts[2]);
            let child_list = connections.entry(child).or_insert(vec![]);
            if !child_list.iter().any(|s| s == parent) {
                child_list.push(parent.to_owned());
            }
        }
    }

    let mut queue: VecDeque<&str> = VecDeque::new();
    let mut visited: HashSet<&str> = HashSet::new();

    // a closure or a function should start here
    visited.insert(&root_name);
    if let Some(list) = connections.get(&root_name) {
        for n in list { queue.push_back(n); }
    }
    // convert above 4 lines to a closure or a function

    // let visit = |name| {
    //     visited.insert(name);
    //     if let Some(list) = connections.get(name) {
    //         for n in list { queue.push_back(n); }
    //     }
    // }
    // visit(&root_name);
    
    let mut result = 0;
    while !queue.is_empty() {
        match queue.pop_front() {
            None => break,
            Some(cur) => {
                if visited.contains(cur) { continue; };
                result += 1;

                // the second use of the code block
                visited.insert(cur);
                if let Some(list) = connections.get(cur) {
                    for n in list { queue.push_back(n); }
                }
                // visit(cur);
            }
        }
    }

    result
}

fn main() {
    println!("day 7: {}", day_7());
}

Playground link

更新：这是来自正确答案的正确函数。请注意 visited 和 queue 没有明确的生命周期参数。

    fn visit<'a>(name: &'a str, visited: &mut HashSet<&'a str>, queue: &mut VecDeque<&'a str>, connections: &'a HashMap<String, Vec<String>>) {
        visited.insert(name);
        if let Some(list) = connections.get(name) {
            for n in list { queue.push_back(n); }
        }
    }

Answer 1

不幸的是，将代码分解为 lambda 与借用检查器有些不兼容。原因是 lambda 本质上是一个结构，其中包含对其关闭的所有变量的引用。因此，如果 lambda 需要引用一个变量，它必须在 lambda 存在的整个时间内被冻结，如果它需要改变它，它必须是唯一这样做的东西。

这是借用规则的不幸交互。我不知道有任何 RFC 对此有帮助，但未来的语言扩展将使像这样的代码工作并非不可能。

至于解决方法，您可以定义一个函数局部宏。宏也可以关闭局部变量，所以效果很好：

    macro_rules! visit {
        ($name:expr) => {
            let name = $name;
            visited.insert(name);
            if let Some(list) = connections.get(name) {
                for n in list { queue.push_back(n); }
            }
        }
    }
    
    visit!(&root_name);

Playground link

请注意我是如何立即将宏参数绑定到变量的。这是为了避免脚枪：when you repeat a macro parameter name, the expression passed in as argument is evaluated twice。这对于一些宏来说是可取的，但是当你想像 lambda 一样使用它们时——就不是那么多了。

如果您宁愿避免为此目的使用宏，您也可以考虑使所需的变量成为函数的显式参数。确保您拥有所有这些的一个好方法是使用内部 fn 函数，因为它们无法捕获变量：

    fn visit<'a>(name: &'a str, visited: &mut HashSet<&'a str>, queue: &mut VecDeque<&'a str>, connections: &'a HashMap<String, Vec<String>>) {
        visited.insert(name);
        if let Some(list) = connections.get(name) {
            for n in list { queue.push_back(n); }
        }
    }

    visit(root_name.as_str(), &mut visited, &mut queue, &connections);

在这种情况下你需要注意生命周期注解：'a是所有涉及的字符串的生命周期，如果你也说visited: &'a mut，那么visited将只要字符串存在，就一直借用。

顺便说一句：您可以使用 while let:

更好地编写循环

    while let Some(cur) = queue.pop_front() {
        if visited.contains(cur) { continue; };
        result += 1;
        visit!(cur);
    }

Answer 2

不是 queue.is_empty() 阻塞了借用，而是持有 queue 的可变借用的闭包阻塞了对 queue 的所有其他访问。这包括对 queue.is_empty() 的调用，但也包括 queue.pop_front() 的调用，或任何你想在 queue 中执行的任何其他操作，同时包含它的闭包处于活动状态。

此问题的标准解决方法是避免捕获，并将 &mut queue 作为显式参数传递给闭包。但不幸的是，在你的情况下它不起作用，因为你还需要将 &connections 和 &mut visited 传递给闭包，并且它们生命周期之间的关系不是编译器目前能够推断的。

不过，还有一个出路，虽然还不清楚你是否会喜欢。问题的核心是闭包试图捕获对您还需要在其外部访问的内容的可变引用。 Rust 确实支持共享可变访问——通过内部可变性。您可以将 queue 和 connections 包装在 RefCell 中，如下所示：

let queue: RefCell<VecDeque<&str>> = Default::default();
let visited: RefCell<HashSet<&str>> = Default::default();

现在闭包将通过共享引用捕获它们，并且与环境共享它们不会有问题：

let visit = |name| {
    visited.borrow_mut().insert(name);
    if let Some(list) = connections.get(name) {
        let mut queue = queue.borrow_mut();
        for n in list {
            queue.push_back(n);
        }
    }
};

let mut result = 0;
while !queue.borrow().is_empty() {
    let cur = match queue.borrow_mut().pop_front() {
        None => break,
        Some(cur) => cur,
    };
    if visited.borrow().contains(cur) {
        continue;
    };
    result += 1;
    visit(cur);
}

Playground

虽然使用 RefCell 感觉有点作弊，因为它将借用检查从编译时间推到运行时间，但它非常适合我们知道我们在做什么的情况，但我们无法向当前的借阅检查员证明这一点。此外，RefCell 并不昂贵，它不会产生分配，例如，borrow() 和 borrow_mut() 归结为一个 check/update 标志。最好衡量它对您的特定用例的影响，但由于所有检查都限于单个代码块，我希望编译器能够完全忽略它们。

为什么 VecDeque is_empty 阻止进一步借用？

Why VecDeque is_empty is blocking further borrows?

rust

borrow-checker