Different borrowing in match variants

help
#1

I have a tree-walking code:

    fn append_point(&mut self, coords: Point, data: T) -> Result<(), &str>{
        match &mut self.node{
            QuadTreeNode::None => {
                self.node = QuadTreeNode::Leaf(coords, data);
                Ok(())
            }
            QuadTreeNode::Node(quadrants) => {
                for quadrant in quadrants.iter_mut(){
                    if quadrant.is_inside(coords){
                        return quadrant.append_point(coords, data);
                    }
                }
                Err("Point is not in any of quardrants")
            }

It does not compile, complaining

error[E0506]: cannot assign to `self.node` because it is borrowed
   --> src/quadtree.rs:95:17
    |
89  |     fn append_point(&mut self, coords: Point, data: T) -> Result<(), &str>{
    |                     - let's call the lifetime of this reference `'1`
...
93  |         match &mut self.node{
    |               -------------- borrow of `self.node` occurs here
94  |             QuadTreeNode::None => {
95  |                 self.node = QuadTreeNode::Leaf(coords, data);
    |                 ^^^^^^^^^ assignment to borrowed `self.node` occurs here
...
101 |                         return quadrant.append_point(coords, data);
    |                                ----------------------------------- returning this value requires that `self.node` is borrowed for `'1

If I comment out any actions for Leaf part (for loop), it compiles with no issues. The same is for self.node, if I comment it out, code compiles.

I don't understand why borrow checker is not happy here. It's a match statement, it's either one branch or other. They are never executed simultaneously, so they should not influence each other.

Is it borrowck imperfection or I miss something important here? And how to deal with those types of things?

Full code is here: equart/quadtree.rs at 111ea3a9c06ef2669993a7cb4e6816364097a94a · amarao/equart · GitHub

#2

Yes, this is a limitation of the borrow-checker where things being returned cause those things to be borrowed for too long in other contexts.

The main workaround for this issue is to do the borrow twice such that you never return it in the case where you want to assign.

match &mut self.node {
    QuadTreeNode::None => {
        self.node = QuadTreeNode::Leaf(coords, data);
        return Ok(());
    }
}
match &mut self.node {
    QuadTreeNode::None => unreachable!(),
    QuadTreeNode::Node(quadrants) => {
        for quadrant in quadrants.iter_mut(){
            if quadrant.is_inside(coords){
                return quadrant.append_point(coords, data);
            }
        }
        Err("Point is not in any of quardrants")
    }
    _ => {
        Err("")
    }
}
#3

Yes, it's worked! Thank you. Together with clippy complains it become a set of if let's, but it's working now.

#4

Unfortunately, it does not work for all cases.

I update code to be like this:


    fn append_point(&mut self, coords: Point, data: T) -> Result<(), &str>{
        if let QuadTreeNode::None = &mut self.node {
            self.node = QuadTreeNode::Leaf(coords, data);
            return Ok(());
        }

        if let QuadTreeNode::Node(quadrants) = &mut self.node {
            for quadrant in quadrants.iter_mut(){
                if quadrant.is_inside(coords){
                    return quadrant.append_point(coords, data);
                }
            }
            return Err("Point is not in any of quardrants");
        }
        if let QuadTreeNode::Leaf(old_coord, old_data) = &mut self.node {
            return Err("");
        }
        Err("")
    }

and compiler is still unhappy, complaining about second borrow. I do not understand why borrowck is sure it's second borrow, if there are two independent lexical scopes here. Moreover, I have no idea how to implement those kinds of modifying enums. Is this possible?

#5

What is the new error?

#6

Sorry, my miss:

error[E0499]: cannot borrow `self.node` as mutable more than once at a time
   --> src/quadtree.rs:113:58
    |
96  |     fn append_point(&mut self, coords: Point, data: T) -> Result<(), &str>{
    |                     - let's call the lifetime of this reference `'1`
...
105 |         if let QuadTreeNode::Node(quadrants) = &mut self.node {
    |                                                -------------- first mutable borrow occurs here
...
108 |                     return quadrant.append_point(coords, data);
    |                            ----------------------------------- returning this value requires that `self.node` is borrowed for `'1`
...
113 |         if let QuadTreeNode::Leaf(old_coord, old_data) = &mut self.node {
    |                                                          ^^^^^^^^^^^^^^ second mutable borrow occurs here
#7

Swap the order so the if with the Node is last, or merge the Node and Leaf into a match. Basically you can't touch self.node after the place where you make the borrow you later return.

#8

Amazingly, swapping order did the trick! It working, I can reason why, but i still feel myself very much underwhelmed by borrowck unable to see that this is invariant, neither in match, nor in a set of ifs with returns.

Thank you very much for the help!

#9

The reason is that to return something, you must borrow it for a lifetime that extends until after the function returns, but the current implementation makes "until the function returns" extend through every execution path starting from where you originally borrow it.

#10

This will eventually be fixed by Polonius, a new borrow-checker implementation that will be much smarter about control flow and early returns.

#11

Thank you very much for help! I finally was able to write the code I want, and it's uses magic of std::mem::replace. It allows me to move value from the structure without dealing with borrow/move for the whole structure and without requiring Copy trait for data.

My final code (I yet don't know if it works or not) which does not enrage compiler:

fn append_point(&mut self, coords: Point, data: T) -> Result<(), ()>{
        if !self.boundry.is_inside(coords){
            return Err(());
        }
        let newnode = QuadTreeNode::None;
        let oldnode = std::mem::replace(&mut self.node, newnode);
        match oldnode {
            QuadTreeNode::None => {
                self.node = QuadTreeNode::Leaf(coords, data);
                Ok(())
            },
            QuadTreeNode::Leaf(old_coords, old_data) => {
                let subboundries = self.boundry.split();
                let quadrants = [
                    Box::new(QuadTree::new(subboundries[0])),
                    Box::new(QuadTree::new(subboundries[1])),
                    Box::new(QuadTree::new(subboundries[2])),
                    Box::new(QuadTree::new(subboundries[3])),
                ];
                self.node = QuadTreeNode::Node(quadrants);
                let res1 = self.append_point(coords, data);
                let res2 = self.append_point(old_coords, old_data);
                if res1 == Ok(()) && res2 == Ok(()){
                    Ok(())
                }else{
                    Err(())
                }
            },
            QuadTreeNode::Node(quadrants) => {
                self.node = QuadTreeNode::Node(quadrants);
                if let QuadTreeNode::Node(ref mut qw) = & mut self.node{
                    for q in qw.iter_mut(){
                        if q.is_inside(coords){
                            return q.append_point(coords, data);
                        }
                    }
                }
                Err(())
            }
        }
    }