Several modified borrowings while searching the depth tree
How would I refactor this function, which does depth-first search and returns the parent of the matching node?
I know there have been variations of this problem very often (e.g. Multiple mutable roles when creating a tree structure with a recursive function in Rust , Mut borrow not ending where expected ), but I still can't figure out how to change it to work. I've tried options using slices, std::mem::drop
and adding lifetime parameters where 'a: 'b
, but I still don't realize that I wrote it without conditionally mutating borrowing a variable in one branch, and then using a 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
Here it is with @huons suggestions and ongoing 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
source to share
I managed to get it to work like this:
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 }
First, in the second try, you wrote for child in root.children
instead of for child in &mut root.children
(note the missing one &mut
), which causes root.children to be consumed by the loop and not just renamed, hence the cannot move out of borrowed content
error.
I also displaced it in a more iterative way using any(..)
.
In the second loop I'm not entirely sure what is going on, apparently by binding references to variables, confusing the borrowing mechanism. I removed the temporary variable and now it compiles.
source to share
You can do this in a single pass by doing a search, writing some data from it, and then effectively calculating the return value outside of the loop:
let mut found = Err(());
for (i, child) in root.children.iter_mut().enumerate() {
if child.id == id {
found = Ok(None);
break;
} else find_parent_mut(child, id).is_some() {
found = Ok(Some(i));
break;
}
}
match found {
Ok(Some(i)) => Some(&mut root.children[i]),
Ok(None) => Some(root),
Err(()) => None,
}
This avoids the problems caused by conditionally returning mutable variables (these are the problems you encountered with my answer below) by completely avoiding returning inside the inner loop.
Old / Wrong Answer:
I can't check my suggestions right now, but I believe the best way to solve this is to return root
outside of the loop.
for child in &mut root.children {
if child.id == id {
found = true;
break
} ...
}
if found {
Some(root)
} else {
None
}
This (hopefully) ensures that it is root
not borrowed through children
when it is managed.
However, I suspect that returning early inside the main loop might get in the way, in which case one can simply revert to integers and indexing:
for i in 0..root.children.len() {
if root.children[i].id == id {
return Some(root)
...
}
source to share