Search code examples
rustborrow-checkeravl-treemutability

Rust - double mutable borrow in 'while let' statement


Sorry if this is a dumb question, I'm relatively new with Rust and just can't crack this double mutable borrowing error. I'm trying to create an AVL tree method that finds an appropriate position into which a new node can be inserted. I don't understand what I need to do for the first borrow to drop.

I'm trying to do this without RC, RefCell or Unsafe - though it's becoming increasingly unclear to me if my approach is feasible.

Rust Playground Link

    pub fn find_pos(&mut self, key: &K) -> &mut Link<K, V>{
        let mut current = &mut self.root;
        while let Some(node) = current.as_mut() {  // <- first mutable borrow
            match node.key.cmp(&key) {
                Ordering::Equal => break,
                Ordering::Greater => {
                    current = &mut node.right;
                },
                Ordering::Less => {
                    current = &mut node.left;
                },
            }
        };
        current  // <- second mutable borrow
    }

I've also tried something similar to the solution described here, with no luck.

    pub fn find_pos(&mut self, key: &K) -> &mut Link<K, V> {
        let mut current = &mut self.root;
        loop {
            let tmp = current;
            if let Some(ref mut node) = *tmp {
               match node.key.cmp(&key) {
                   Ordering::Equal => {
                       current = tmp;
                       break
                   },
                   Ordering::Greater => {current = &mut node.right},
                   Ordering::Less => {current = &mut node.left},
               }
            } else {
                current = tmp;
                break
            }
        }
        current
    }

Solution

  • This is a known limitation of the borrow checker. The next-gen Polonius will solve this.

    In the meantime, the solution (without unsafe) is to repeat the calculation. In your case, this means some unwrap()s:

    pub fn find_pos(&mut self, key: &K) -> &mut Link<K, V> {
        let mut current = &mut self.root;
        while current.as_mut().is_some() {
            match current.as_mut().unwrap().key.cmp(&key) {
                Ordering::Equal => break,
                Ordering::Greater => {
                    current = &mut current.as_mut().unwrap().right;
                }
                Ordering::Less => {
                    current = &mut current.as_mut().unwrap().left;
                }
            }
        }
        current
    }
    

    See also: