How to explain this "cannot assign to xxx because it is borrowed" error

I am a teaching assistant of a Rust course in our school. Today I received a piece of code from student:

struct Node {
    value: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

struct Tree {
    root: Option<Box<Node>>,
}

enum Error {
    DuplicateValue,
}

impl Tree {
    fn insert(&mut self, value: i32) -> Result<(), Error> {
        if let Some(root) = &mut self.root {
            let mut current_node = root;
            loop {
                if current_node.value == value {
                    return Err(Error::DuplicateValue);
                }
                if value > current_node.value {
                    if let Some(right) = &mut current_node.right {
                        current_node = right;
                        continue;
                    } else {
                        current_node.right = Some(Box::new(Node {
                            value,
                            left: None,
                            right: None,
                        }));
                        return Ok(());
                    }
                }
                if value < current_node.value {
                    let left = &mut current_node.left;
                    if let Some(left) = left {
                        current_node = left;
                        continue;
                    } else {
                        *left = Some(Box::new(Node {
                            value,
                            left: None,
                            right: None,
                        }));
                        return Ok(());
                    }
                }
            }
        } else {
            self.root = Some(Box::new(Node {
                value,
                left: None,
                right: None,
            }));
            return Ok(());
        }
    }
}

The code implements a binary search tree in Rust. You can run it on rust playground. The error message is shown as:

error[E0506]: cannot assign to `current_node.right` because it is borrowed
  --> src/lib.rs:28:25
   |
24 |                     if let Some(right) = &mut current_node.right {
   |                                          ----------------------- borrow of `current_node.right` occurs here
...
28 |                         current_node.right = Some(Box::new(Node {
   |                         ^^^^^^^^^^^^^^^^^^
   |                         |
   |                         assignment to borrowed `current_node.right` occurs here
   |                         borrow later used here

For more information about this error, try `rustc --explain E0506`.

The relevant code is:

                    if let Some(right) = &mut current_node.right {
                        current_node = right;
                        continue;
                    } else {
                        current_node.right = Some(Box::new(Node {
                            value,
                            left: None,
                            right: None,
                        }));
                        return Ok(());
                    }

I think the borrow check can figure it out that the first mutable borrow to current_node.right can drop before the assignment, but somehow it didn't. Of course, we can use one mutable borrow reference to fix it, like the code for left branch below:

                    let left = &mut current_node.left;
                    if let Some(left) = left {
                        current_node = left;
                        continue;
                    } else {
                        *left = Some(Box::new(Node {
                            value,
                            left: None,
                            right: None,
                        }));
                        return Ok(());
                    }

But as TA, I need to explain to user why the original code should not work.

I found a similar issue: rust - If let borrow stays after return even with #![feature(nll)] - Stack Overflow. I am not sure whether this is another limitation of the current nll borrow checker.

You can't because it's not the question of whether it “should” or “shouldn't”. It's just question of whether dropping it early is “expected” or not.

Unfortunately it's the situation where any choice would be confusing to anyone: if temporary would be dropped before if branch then people would ask why you can't lock the Mutex with if let.

And since it's safety issue (the code like what you are discussing can be easily fixed, but drops that happen too early may be dangerous) the decision was to do what is done today.

I think you're reading it wrong: there's no safety issue here, and the code compiles under Polonius. &mut references don't have drop glue like mutex guards do. The only reason this doesn't compile is because the compiler isn't yet clever enough to figure out that it should.

4 Likes

Thanks for the observation! I can say to students that this is a limitation of the current borrow checker, and may work in a future Rust version.

2 Likes

Also known as NLL Problem Case 3, and here's the tracking issue.

3 Likes

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.