Cannot borrow `*tree` as mutable more than once at a time

[square-db]

Hello,

I was trying to solve this issue but i simply cannot! If any one can help me i will be thankful!
This is the code :

use std::convert::TryInto;

#[derive(Clone, Debug)]
enum Node {
  InternalNode(InternalNode),
  LeafNode(LeafNode),
}

#[derive(Clone, Debug)]
struct InternalNode {
  keys: Vec<i32>,
  children: Vec<Node>,
  parent: Option<Box<InternalNode>>,
  size: i32,
  order: i32,
}

#[derive(Clone, Debug)]
struct LeafNode {
  values: Vec<String>,
  next: Option<Box<LeafNode>>,
  prev: Option<Box<LeafNode>>,
  parent: Option<Box<InternalNode>>,
  size: i32,
}

#[derive(Debug, Clone)]
struct BPlusTree {
  root: Node,
  order: i32,
}

impl BPlusTree {
  fn new(order: i32) -> Self {
    BPlusTree {
      root: Node::LeafNode(LeafNode {
        values: Vec::new(),
        next: None,
        prev: None,
        parent: None,
        size: 0,
      }),
      order,
    }
  }
}

fn insert(tree: &mut BPlusTree, key: i32, value: String) {
    let tree_ref  = &mut *tree; // Borrowing leaf_node_mut as a separate reference
    let leaf_node = find_leaf_node_mut(&mut tree_ref.root, &key);
    leaf_node.values.push(value);
    leaf_node.size += 1;
    balance_tree(leaf_node, tree);
}


fn find_leaf_node_mut<'a>(root: &'a mut Node, key: &'a i32) -> &'a mut LeafNode {
  let mut current_node = root;
  loop {
    match current_node {
      Node::LeafNode(leaf) => return leaf,
      Node::InternalNode(internal) => {
        let idx = internal.keys.binary_search(key).unwrap_or_else(|x| x);
        current_node = &mut internal.children[idx];
      }
    }
  }
}

fn balance_tree(leaf_node: &mut LeafNode, tree: &mut BPlusTree) {
  if leaf_node.values.len() as i32 > tree.order {
    let mid = leaf_node.values.len() / 2;
    let new_values = leaf_node.values.split_off(mid);
    let new_leaf = LeafNode {
      values: new_values.clone(),
      next: leaf_node.next.take(),
      prev: Some(Box::new(leaf_node.clone())),
      parent: leaf_node.parent.take(),
      size: new_values.len() as i32,
    };

    if let Some(parent) = &mut leaf_node.parent {
      let idx = parent.keys.binary_search(&new_leaf.values[0].len().try_into().unwrap()).unwrap_or_else(|x| x);
      parent.keys.insert(idx, new_leaf.values[0].len().try_into().unwrap());
      parent.children.insert(idx + 1, Node::LeafNode(new_leaf));
      parent.size += 1;
    } else {
      let new_root = Node::InternalNode(InternalNode {
        keys: vec![new_leaf.values[0].len().try_into().unwrap()],
        children: vec![
          tree.root.clone(),
          Node::LeafNode(new_leaf),
        ],
        parent: None,
        size: 2,
        order: tree.order,
      });
      tree.root = new_root;
    }
  }
}

fn main() {
  let mut bplus_tree = BPlusTree::new(3);
  insert(&mut bplus_tree, 10, "Value1".to_string());
  insert(&mut bplus_tree, 20, "Value2".to_string());
  println!("{:?}", bplus_tree);
}

And this is the error :

error[E0499]: cannot borrow `*tree` as mutable more than once at a time
  --> src/main.rs:53:29
   |
49 |     let tree_ref  = &mut *tree; // Borrowing leaf_node_m...
   |                     ---------- first mutable borrow occurs here
...
53 |     balance_tree(leaf_node, tree);
   |     ------------            ^^^^ second mutable borrow occurs here
   |     |
   |     first borrow later used by call

For more information about this error, try `rustc --explain E0499`.
error: could not compile `squaredb_fm` (bin "squaredb_fm") due to 1 previous error

Can any explain me this error, too?

Thanks

[quinedot]

I didn't study your code enough to offer a solution, so this is just attempting to explain the error.

fn insert(tree: &mut BPlusTree, key: i32, value: String) {
    let tree_ref  = &mut *tree; // Borrowing leaf_node_mut as a separate reference
    // ...

That doesn't hurt, but it doesn't help either, so let's just get rid of it:

fn insert(tree: &mut BPlusTree, key: i32, value: String) {
    let leaf_node = find_leaf_node_mut(&mut tree.root, &key);
    leaf_node.values.push(value);
    leaf_node.size += 1;
    balance_tree(leaf_node, tree);
}

Now if we look at find_leaf_node_mut, it has this signature:^[1]

fn find_leaf_node_mut<'a>(root: &'a mut Node, key: &'a i32) -> &'a mut LeafNode
//                               ^^                             ^^

Which means that as long as the returned &mut LeafNode is valid, the input &mut Node must also be valid -- that is, the Node much remain exclusively borrowed.

Then back in insert, when you get to

balance_tree(leaf_node, tree);

You can't use the entirety of tree like this while it's field is borrowed, but leaf_node being valid means the &mut tree.root is still valid -- tree.root is still borrowed.

Or taking a step back and looking at balance_tree:

fn balance_tree(leaf_node: &mut LeafNode, tree: &mut BPlusTree) {

You can't pass in a &mut BPlusTree from which you could reach the same &mut LeafNode you pass in, because that would mean you could get two &mut BPlusTree to the same data active at the same time. That's undefined behavior, because &mut are exclusive references.

---

1. the way key is passed is also not ideal, but isn't relevant to the question so I'll ignore it ↩︎

[square-db]

Thank You!
This helped me so much...