Borrow pointer errors recursively traversing tree
rust
Solution
This seems to be a weakness of the borrow checker, and is perhaps a bug. The problem is that you are borrowing `at` in the match and then modifying it. Unfortunately, the compiler doesn't see that the `at` inside the loop and outside the loop are conceptually different. We can make them explicitly different, however:
enum AVLTree {
Tree(Box<AVLTree>),
Empty,
}
impl AVLTree {
fn insert_element(&mut self) {
let mut at = self;
loop {
let tmp_at = at; // Main change
match tmp_at {
&mut AVLTree::Tree(ref mut left) => {
at = &mut **left;
}
&mut AVLTree::Empty => unreachable!()
}
}
}
}
fn main() {}
Here, we transfer the mutable borrow from `at` to `tmp_at`, then transfer it to `left`, then transfer it back to `at`.
A prettier option may be to use a new scope:
fn insert_element(&mut self) {
let mut at = self;
loop {
match {at} { // Main change
&mut AVLTree::Tree(ref mut left) => {
at = &mut **left;
}
&mut AVLTree::Empty => unreachable!(),
}
}
}
Problem
To learn Rust, I am implementing an AVL tree/dictionary. To insert a new element, I descend into the tree until I find a node where it could be inserted. Unfortunately it complains about several issues with borrowing pointers, and I'm having trouble deciphering them. I've highlighted where and which errors occur. ``` enum AVLTree<T, U> { Tree(T, U, Box<AVLTree<T, U>>, Box<AVLTree<T, U>>), Empty, } impl<T, U> AVLTree<T, U> where T: PartialOrd + PartialEq + Copy, U: Copy { fn insert_element(&mut self, key: T, val: U) { let new_node = AVLTree::Tree(key, val, Box::new(AVLTree::Empty), Box::new(AVLTree::Empty)); if let AVLTree::Empty = *self { *self = new_node; return; } let mut at = self; loop { match at { &mut AVLTree::Tree(key2, _, ref mut left, ref mut right) => { // ^~~~~~~~~~~~ // error: cannot borrow `at.2` as mutable more than once at a time // ^~~~~~~~~~~~~ // error: cannot borrow `at.3` as mutable more than once at a time if key < key2 { if let AVLTree::Empty = **left { *left = Box::new(new_node); break; } at = &mut **left; // error: cannot assign to `at` because it is borrowed } else { if let AVLTree::Empty = **right { *right = Box::new(new_node); break; } at = &mut **right; // error: cannot assign to `at` because it is borrowed } } &mut AVLTree::Empty => unreachable!(), } } // Do something } } ``` Why is deconstructing `at` borrowing it? Why is the compiler complaining about multiple mutable borrows when this should never happen? How could this code be written instead to avoid such errors?