3

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.

Shepmaster
  • 388,571
  • 95
  • 1,107
  • 1,366
rubo
  • 377
  • 1
  • 8
  • 1
    Narrowed the question down to "why NLL is not working in given code". This question does not arise in any posts you have referred (in 2 out of 3, NLL actually does allow the code to compile as-is). – rubo May 04 '21 at 16:37
  • 1
    TL;DR the duplicate: the current implementation of the borrow checker is not smart enough to handle conditional control flow across functions. A proposed future reworking of the implementation (known as *Polonius*) might help. Compiling your original code with `-Zpolonius` works, for example. – Shepmaster May 04 '21 at 17:19

0 Answers0