"Borrowed value does not live long enough" when matching on a B-Tree node enum to get a reference

Question

I am trying to implement a B-tree in Rust, and I'm struggling with how to manage lifetimes interacting with match statements. I am new to Rust and while I think I understand what lifetimes are and how they work, I can't figure out how to make them do what I want.

My data structure looks like this:

enum Node<T: Key> {
    Internal(InternalNode<T>),
    Leaf(LeafNode<T>),
}

enum NodeRef<'a, T: 'a + Key> {
    Internal(&'a InternalNode<T>),
    Leaf(&'a LeafNode<T>),
}

enum NodeRefMut<'a, T: 'a + Key> {
    Internal(&'a mut InternalNode<T>),
    Leaf(&'a mut LeafNode<T>),
}

struct InternalNode<T: Key> {
    keys: Vec<T>,
    children: Vec<Box<Node<T>>>,
    num_keys: usize,
}

struct LeafNode<T: Key> {
    keys: Vec<T>,
    num_keys: usize,
}

pub struct BTree<T: Key> {
    num_keys: usize,
    root: Node<T>
}

In a B-tree insertion, you need to insert into a node and then keep a reference to the node you inserted into, so you can balance and split. This is not a question about the algorithm but here is a code fragment which illustrates the problem:

pub fn insert(&mut self, key: T) -> bool {
    let (_inserted_at, success) = match self.root {
        Node::Internal(ref mut node) =>
            BTree::insert_at_internal_node(&mut node, key),

        Node::Leaf(ref mut node) =>
            BTree::insert_at_leaf_node(&mut node, key),
    };

    panic!() // snip
}

fn insert_at_leaf_node<'a>(leaf: &'a mut LeafNode<T>, key: T) -> (NodeRefMut<'a, T>, bool) {
    panic!() // snip
}

fn insert_at_internal_node<'a>(internal: &'a mut InternalNode<T>, key: T) -> (NodeRefMut<'a, T>, bool) {
    panic!() // snip
}

Then we get the following fairly clear error that I don't know how to resolve:

   error[E0597]: `node` does not live long enough
--> src/trees/mod.rs:102:53
    |
102 |                 BTree::insert_at_internal_node(&mut node, key),
    |                                                     ^^^^ borrowed value does not live long enough
...
106 |         };
    |         - `node` dropped here while still borrowed
...
109 |     }
    |     - borrowed value needs to live until here

error[E0597]: `node` does not live long enough
--> src/trees/mod.rs:105:49
    |
105 |                 BTree::insert_at_leaf_node(&mut node, key),
    |                                                 ^^^^ borrowed value does not live long enough
106 |         };
    |         - `node` dropped here while still borrowed
...
109 |     }
    |     - borrowed value needs to live until here

Essentially, we need a mutable reference to the leaf node we inserted into, which the insert_at methods have no trouble producing. However, when I'm doing the match statement it produces a mutable reference to a node that only lives as long as the match statement (so the produced reference can't outlive the match block, defeating the purpose).

At the moment I just want to mutably borrow everything (I have an &mut self for a reason) but I don't know how to do this.

Answer 1

TL;DR — remove &mut from the calls:

let (_inserted_at, success) = match self.root {
    Node::Internal(ref mut node) => BTree::insert_at_internal_node(node, key),
    Node::Leaf(ref mut node) => BTree::insert_at_leaf_node(node, key),
};

---

Your problem can be reduced to this (and probably further, but this still has the general shape of the original):

enum Node {
    Internal(InternalNode),
}

enum NodeRefMut<'a> {
    Internal(&'a mut InternalNode),
}

struct InternalNode;

fn insert(mut root: Node) {
    let _inserted_at = match root {
        Node::Internal(ref mut node) => internal(&mut node),
    };
}

fn internal<'a>(_internal: &'a mut InternalNode) -> NodeRefMut<'a> {
    unimplemented!()
}

If you print out the type of node, you'll see that by using ref mut in the pattern, you've already created a &mut Node:

Node::Internal(ref mut node) => {
    let _: () = node;
    internal(&mut node)
}

error[E0308]: mismatched types
  --> src/main.rs:14:21
   |
14 |         let _: () = node; 
   |                     ^^^^ expected (), found mutable reference
   |
   = note: expected type `()`
              found type `&mut InternalNode`

When you take a second mutable reference, you are taking a mutable reference to the variable that's only in scope in the match arm. The lifetime of that variable is exactly what the error message points out: the match arm itself.

Interestingly, this error only occurs because you are returning a value from the match. If you don't, you get a different error:

error[E0596]: cannot borrow immutable local variable `node` as mutable
  --> src/main.rs:17:27
   |
17 |             internal(&mut node)
   |                           ^^^^
   |                           |
   |                           cannot reborrow mutably
   |                           try removing `&mut` here

Because the variable node is indeed itself not mutable!