To get a mutable reference to the leftmost node, what would be the minimal element in a BST, I wrote this code:
impl Node {
fn left_child_mut(&mut self) -> Option<&mut Node> {
match *self {
Node::Good { left: Some(ref mut child), .. } => Some(child),
_ => None,
}
}
fn leftmost_mut(&mut self) -> &mut Node {
let mut cur = self;
while let Some(child) = cur.left_child_mut() {
cur = child;
}
cur
}
}
The borrow checker complains (playground) that *cur can't be mutably borrowed by left_child_mut(), because another mutable reference is returned on the last line. If I match on *cur directly in leftmost_mut() (basically inlining left_child_mut()), there's no issue. Since I have several methods that traverse a tree in this way, I'd like to avoid writing a match every time; is there a way to modify the code so that this works out?
(There are several questions on StackOverflow and this forum about similar-looking problems, but they all seem to boil down to the lack of NLLs, and I'm using the 2018 edition. I haven't had any luck with the posted solutions to these other problems, though I might be adapting them incorrectly to my case.)
Sorry, I probably wasn't clear about this -- what I want is for leftmost_mut() to call out to left_child() instead of destructuring Node itself (because the real Node type is more complicated and I don't want to replicate the pattern match in every method that needs to traverse the tree).
The answer is similar though. The main problem is limitations in Rust’s borrow checker. I don’t fully understand the details myself but the way you can tell is that it compiles with -Zpolonius, a WIP alternative borrow-checker which fixes this and similar limitations.
For the time being, trying to restructure the program may help, let’s see...
So to make the borrow checker happy, we probably need a new version of left_child_mut that returns Result<&mut Node, &mut Node> instead of Option<&mut Node>.
(The alternative would be to call it twice but that seems inefficient)
With a Result<&mut Node, &mut Node> return type, there’s no need to borrow the node mutably a second time anymore and you can make it work like this.
Thanks! I was hoping to find (and @steffahn provided) an iterative implementation, for the usual efficiency reasons, but it's good to know it can be done recursively as well.