Rust Tree implementation borrowing problem

Question

I am new to rust, want to write some code to grade up in it. Now I am writing a simple B-tree implementation and have problems with mutable refs.

use std::fmt::Debug;

#[allow(dead_code)]
#[derive(Clone, Debug)]
struct Node<T: PartialOrd + Clone + Debug> {
    leaf: bool,
    count: usize,
    keys: Vec<T>,
    children: Vec<Box<Node<T>>>,
    t: usize,
}

#[allow(dead_code)]
impl<T: PartialOrd + Clone + Debug> Node<T> {
    fn empty(t: usize) -> Self {
        return Node {
            keys: Vec::with_capacity(t),
            children: Vec::with_capacity(t + 1),
            count: 0,
            leaf: false,
            t,
        };
    }

    fn leaf(t: usize) -> Self {
        return Node {
            keys: Vec::with_capacity(t),
            children: Vec::with_capacity(t + 1),
            count: 0,
            leaf: true,
            t,
        };
    }
   
    /**
     * return siblings of node with given index
     * first element is given node
     */
    fn siblings(&mut self, index: usize) -> Vec<&mut Box<Node<T>>> {
        let mut result: Vec<_> = self
            .children
            .iter_mut()
            .enumerate()
            .filter(|(i, _)| *i == index || *i + 1 == index || *i == index + 1)
            .map(|(_, v)| v)
            .collect();

        if result.len() == 3 {
            result.swap(0, 1);
        } else {
            if index == 0 {
                result.swap(0, 1);
            }
        }

        result
    }

    fn remove_key(&mut self, key: T) -> bool {
        let result = self.keys.iter().position(|element| *element == key);

        match result {
            None => false,
            Some(index) => {
                self.keys.remove(index);

                return true;
            }
        }
    }

    /**
     * self refers to root of leaf
     * i is index of child, where we want to remove value
     * returns status of operation: did element remove
     */
    fn delete_from_leaf(&mut self, value: T, i: usize) -> bool {
        let t = self.t;
        let mut siblings = self.siblings(i);
        let target_leaf = siblings.remove(0);

        if target_leaf.count >= t {
            return target_leaf.remove_key(value);
        }

        if siblings.is_empty() {
            return false;
        }

        while siblings.len() > 0 {
            let current_node = siblings.remove(0);

            if current_node.count < t {
                continue;
            }

            let max_value = current_node.keys.pop().unwrap();
            let delimeter_value = self.keys.remove(i);

            target_leaf.keys.insert(0, delimeter_value);
            self.keys.insert(i, max_value);

        }

        true
    }
}

cargo check:

error[E0499]: cannot borrow `self.keys` as mutable more than once at a time
   --> src/main.rs:212:35
    |
193 |         let mut siblings = self.siblings(i);
    |                            ---------------- first mutable borrow occurs here
...
204 |         while siblings.len() > 0 {
    |               -------------- first borrow later used here
...
212 |             let delimeter_value = self.keys.remove(i);
    |                                   ^^^^^^^^^^^^^^^^^^^ second mutable borrow occurs here

error[E0499]: cannot borrow `self.keys` as mutable more than once at a time
   --> src/main.rs:215:13
    |
193 |         let mut siblings = self.siblings(i);
    |                            ---------------- first mutable borrow occurs here
...
204 |         while siblings.len() > 0 {
    |               -------------- first borrow later used here
...
215 |             self.keys.insert(i, max_value);
    |             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ second mutable borrow occurs here

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

How can I change self.keys in delete_from_leaf function? As I understand, first mutable ref is in self.siblings(), but it does not access self.keys at all. Should I use unsafe {} block here? Or re-write code to more low-level. I wrote fn self.siblings() to access multiple mut refs in self.children Vec. Is there better way to do it?

Answer 1

The problem is you borrow self twice.

    fn delete_from_leaf(&mut self, value: T, i: usize) -> bool {
        let t = self.t;
        // Calling siblings() here has to borrow self
        let mut siblings = self.siblings(i);
    
        while siblings.len() > 0 {
            ... ... ...

            // Accessing any field of self has to borrow it again
            let delimeter_value = self.keys.remove(i);

            ... ... ...
        }

        true
    }

To avoid this, you should borrow only the sub-fields you need in siblings() instead of the entire struct. The modified method would be:

    fn siblings(children: &mut Vec<Box<Node<T>>>, index: usize) -> Vec<&mut Box<Node<T>>> {
        let mut result: Vec<_> = children
            .iter_mut()
            .enumerate()
        ...

And calling it becomes let mut siblings = Self::siblings(&mut self.children, i);.

I must admit that the compiler could be a little bit more helpful here with a better error message, but I bet it is not an easy task to do so.