深度优先树搜索期间的多个可变借用 [英] Multiple mutable borrows during a depth-first tree search

问题描述

如何重构这个执行深度优先搜索并返回匹配节点的父节点的函数?

How would one restructure this function that does a depth-first search and returns the parent of the matching node?

我知道这个问题的变体经常出现(例如 在 Rust 中生成具有递归函数的树结构时的多个可变借用，Mut 借用没有在预期的地方结束)，但我仍然不知道如何修改它才能工作.我尝试过使用切片、std::mem::drop 和添加生命周期参数 where 'a: 'b 的变体，但我仍然没有想出在没有的情况下编写它有条件地在一个分支中可变地借用一个变量，然后在另一个分支中使用该变量.

I know that variations of this problem have come up very often (e.g. Multiple mutable borrows when generating a tree structure with a recursive function in Rust, Mut borrow not ending where expected), but I still can’t figure out how to modify it to work. I have tried variations using slices, std::mem::drop, and adding lifetime parameters where 'a: 'b but I still haven’t figured out write it without conditionally mutably borrowing a variable in one branch and then using the variable in another branch.

#[derive(Clone, Debug)]
struct TreeNode {
    id: i32,
    children: Vec<TreeNode>,
}

// Returns a mutable reference to the parent of the node that matches the given id.
fn find_parent_mut<'a>(root: &'a mut TreeNode, id: i32) -> Option<&'a mut TreeNode> {
    for child in root.children.iter_mut() {
        if child.id == id {
            return Some(root);
        } else {
            let descendent_result = find_parent_mut(child, id);
            if descendent_result.is_some() {
                return descendent_result;
            }
        }
    }
    None
}

fn main() {
    let mut tree = TreeNode {
        id: 1,
        children: vec![TreeNode {
                           id: 2,
                           children: vec![TreeNode {
                                              id: 3,
                                              children: vec![],
                                          }],
                       }],
    };
    let a: Option<&mut TreeNode> = find_parent_mut(&mut tree, 3);
    assert_eq!(a.unwrap().id, 2);
}

error[E0499]: cannot borrow `*root` as mutable more than once at a time
  --> src/main.rs:11:25
   |
9  |     for child in root.children.iter_mut() {
   |                  ------------- first mutable borrow occurs here
10 |         if child.id == id {
11 |             return Some(root);
   |                         ^^^^ second mutable borrow occurs here
...
20 | }
   | - first borrow ends here

这是@huon 的建议和持续的编译器错误:

Here it is with @huon’s suggestions and continued compiler errors:

fn find_parent_mut<'a>(root: &'a mut TreeNode, id: i32) -> Option<&'a mut TreeNode> {
    for child in root.children {
        if child.id == id {
            return Some(root);
        }
    }
    for i in 0..root.children.len() {
        let child: &'a mut TreeNode = &mut root.children[i];
        let descendent_result = find_parent_mut(child, id);
        if descendent_result.is_some() {
            return descendent_result;
        }
    }
    None
}

error[E0507]: cannot move out of borrowed content
 --> src/main.rs:9:18
  |
9 |     for child in root.children {
  |                  ^^^^ cannot move out of borrowed content

error[E0499]: cannot borrow `root.children` as mutable more than once at a time
  --> src/main.rs:15:44
   |
15 |         let child: &'a mut TreeNode = &mut root.children[i];
   |                                            ^^^^^^^^^^^^^
   |                                            |
   |                                            second mutable borrow occurs here
   |                                            first mutable borrow occurs here
...
22 | }
   | - first borrow ends here

推荐答案

我设法让它以这种方式工作:

I managed to have it working this way:

fn find_parent_mut<'a>(root: &'a mut TreeNode, id: i32)
        -> Option<&'a mut TreeNode> {
    if root.children.iter().any(|child| {child.id == id}) {
        return Some(root); 
    }
    for child in &mut root.children {
        match find_parent_mut(child, id) {
            Some(result) => return Some(result),
            None => {}
        }
    }
    None
}

第一次在你的第二次尝试中，你写了 for child in root.children 而不是 for child in &mut root.children(注意缺少的 &mut)，这导致 root.children 被循环消耗而不是仅仅迭代，因此 cannot move out ofbored content 错误.

First in you second attempt, you wrote for child in root.children instead of the for child in &mut root.children (note the missing &mut),which caused root.children to be consumed by the loop instead of just iterated over, hence the cannot move out of borrowed content error.

我还使用 any(..) 函数.

I also folded it in a more iterator-ich way, using the any(..) function.

对于第二个循环，我不确定发生了什么，显然将引用绑定到变量会使借用检查器感到困惑.我删除了所有临时变量，现在可以编译了.

For the second loop, I'm not exactly sure what was going on, by apparently binding the references to variables was confusing the borrow-checker. I removed any temporary variable, and now it compiles.

这篇关于深度优先树搜索期间的多个可变借用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！