Why are non-lexical lifetimes not working when mutably traversing a linked list?

Viewed 64

Consider the following linked list structure:

struct Node {
    value: i64,
    next_ptr: Option<Box<Node>>,
}

struct SortedList {
    head_ptr: Option<Box<Node>>,
}

Assume that the list is always sorted with respect to node values. I would like to write a (private) method that looks for a position where a given value should be if it is in the list ("a position" in this case is &mut Option<Box<Node>>):

impl List {
    fn find_mut(&mut self, value: i64) -> &mut Option<Box<Node>> {
        let mut node_ptr = &mut self.head_ptr;
        while let Some(node) = node_ptr {
            if node.value >= value {
                return node_ptr;
            }
            node_ptr = &mut node.next_ptr;
        }
        node_ptr
    }
}

Playground

This doesn't compile:

error[E0499]: cannot borrow `*node_ptr` as mutable more than once at a time
  --> src/lib.rs:15:24
   |
11 |     fn find_mut(&mut self, value: i64) -> &mut Option<Box<Node>> {
   |                 - let's call the lifetime of this reference `'1`
12 |         let mut node_ptr = &mut self.head_ptr;
13 |         while let Some(node) = node_ptr {
   |                        ---- first mutable borrow occurs here
14 |             if node.value >= value {
15 |                 return node_ptr;
   |                        ^^^^^^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        returning this value requires that `node_ptr.0` is borrowed for `'1`

I am not quite sure why the borrow checker is unhappy, since the node variable can be considered no longer used once we do return node_ptr, so with non-lexical lifetimes this should work. I was able to make it compile with, arguably, less readable code:

fn find_mut(&mut self, value: i64) -> &mut Option<Box<Node>> {
    let mut node_ptr = &mut self.head_ptr;
    while node_ptr.as_ref().map(|n| n.value >= value).unwrap_or(false) {
        node_ptr = &mut node_ptr.as_mut().unwrap().next_ptr;
    }
    node_ptr
}

But why did NLL not help in the first version?

Notice that this question is different from How do I keep a mutable reference to the last node while building a linked list? since NLL actually did allow the code compile as-is in this question, while in my case it doesn't. It looks like the "if" in the loop body makes all the difference.

0 Answers
Related