How to fix this ‘second mutable borrow occurs here’ error

Here is the example to show the compiling error.

The error result:

   Compiling playground v0.0.1 (/playground)
error[E0499]: cannot borrow `*link` as mutable more than once at a time
  --> src/main.rs:26:32
   |
20 |     fn search(&mut self, elem: &T) -> Result<&mut Link<T>, &mut Link<T>> {
   |               - let's call the lifetime of this reference `'1`
21 |         let mut link = &mut self.root;
22 |         while let Some(node) = link {
   |                        ---- first mutable borrow occurs here
...
26 |                 _ => return Ok(link),
   |                                ^^^^ second mutable borrow occurs here
...
30 |         Err(link)
   |         --------- returning this value requires that `link.0` is borrowed for `'1`

Here is my example code:

#[derive(Debug)]
struct BinTreeNode<T> {
    elem: T,
    left: Option<Box<BinTreeNode<T>>>,
    right: Option<Box<BinTreeNode<T>>>,
}

#[derive(Debug)]
struct BinTree<T> {
    root: Option<Box<BinTreeNode<T>>>,
}

type Link<T> = Option<Box<BinTreeNode<T>>>;

impl<T: std::cmp::Ord> BinTree<T> {
    fn new() -> Self {
        Self { root: None }
    }

    fn search(&mut self, elem: &T) -> Result<&mut Link<T>, &mut Link<T>> {
        let mut link = &mut self.root;
        while let Some(node) = link {
            match elem.cmp(&node.elem) {
                std::cmp::Ordering::Less => link = &mut node.left,
                std::cmp::Ordering::Greater => link = &mut node.right,
                _ => return Ok(link),
            }
        }

        Err(link)
    }

    fn insert(&mut self, elem: T) -> bool {
        match self.search(&elem) {
            Err(node) => {
                node.replace(Box::new(BinTreeNode{
                    elem,
                    left:None,
                    right:None,
                }));
                true
            }
            _ => false,
        }
    }
}

pub fn main() {
    let mut a = BinTree::new();
    a.insert(5);
    a.insert(3);
    a.insert(4);
    a.insert(6);
    println!("{:?}", a);
}

(Playground)

Does anyone know how to solve this error?

Your code compiles successfully with the experimental new Polonius borrow checker. (Using the nightly toolchain, build it with rustc -Z polonius main.rs.) This means that what you are trying to do is actually safe, but the borrow checker isn’t smart enough to verify it yet. Specifically, the current borrow checker has known limitations with borrows that get returned to the calling function in one branch, and also get used “later” in a different branch.

One workaround for now would be to use the exact same code but with a raw pointer in place of the reference:

    fn search(&mut self, elem: &T) -> Result<&mut Link<T>, &mut Link<T>> {
        let mut link = &mut self.root as *mut Link<T>;
        while let Some(node) = unsafe { &mut *link } {
            match elem.cmp(&node.elem) {
                std::cmp::Ordering::Less => link = &mut node.left,
                std::cmp::Ordering::Greater => link = &mut node.right,
                _ => return Ok(unsafe { &mut * link }),
            }
        }

        Err(unsafe { &mut *link })
    }

There might be a better workaround possible (e.g., one without unsafe); I’ll see if I can find one.

2 Likes

I came up with

    fn search(&mut self, elem: &T) -> Result<&mut Link<T>, &mut Link<T>> {
        let mut link = &mut self.root;
        while let Some(ref node) = link {
            match elem.cmp(&node.elem) {
                std::cmp::Ordering::Less => link = &mut link.as_mut().unwrap().left,
                std::cmp::Ordering::Greater => link = &mut link.as_mut().unwrap().right,
                _ => return Ok(link),
            }
        }

        Err(link)
    }

which seems to work?

2 Likes

Thanks for the quick solution.

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.