Understanding the compile error about borrowing and the implementation difference from Vec

Suppose I have a linked-list and its iterator defined as below. Then I'd like to find a node using the iterator and then modify that node:

use std::ptr::null_mut;
use std::marker::PhantomData;

struct Node {
    value: i32,
    next: *mut Node,
}

struct List {
    head: Node,
}

struct Iter<'a> {
    ptr: *mut Node,
    marker: PhantomData<&'a i32>,
}

impl<'a> Iterator for Iter<'a> {
    type Item = &'a mut Node;

    fn next(&mut self) -> Option<Self::Item> {
        if self.ptr.is_null() {
            None
        } else {
            let node = unsafe { self.ptr.as_mut().unwrap() };
            self.ptr = node.next;
            Some(node)
        }
    }
}

impl List {
    fn iter(&self) -> Iter<'_> {
        Iter {
            ptr: self.head.next,
            marker: PhantomData,
        }
    }

    fn modify(&mut self, node: &mut Node) {
    }
}

fn main() {
    let mut list = List {
        head: Node {
            value: 0,
            next: null_mut(),
        }
    };
    if let Some(node) = list.iter().find(|x| { x.value == 123 }) {
        list.modify(node);
    }
}

Compiling this code (playground link) gives me:

error[E0502]: cannot borrow `list` as mutable because it is also borrowed as immutable
  --> src/main.rs:57:9
   |
56 |     if let Some(node) = list.iter().find(|x| { x.value == 123 }) {
   |                         ---- immutable borrow occurs here
57 |         list.modify(node);
   |         ^^^^^------^^^^^^
   |         |    |
   |         |    immutable borrow later used by call
   |         mutable borrow occurs here

If I understand correctly, the error is because of the chain of reference: we are still borrowing list as we hold a reference in node produced by the iterator. (Please let me know if I'm wrong.)

However doing the same search-then-modify thing on a Vec compiles:

    let mut v = vec![1, 2, 3, 4, 5];
    if let Some(value) = v.iter().find(|&&x| x == 3) {
        v.remove(*value);
    }
    assert_eq!(v, vec![1, 2, 3, 5]);

What I don't understand is that, the iterator returned by v.iter() seems to have a similar definition, and it produces items as references &'a T. But why doesn't v.remove() trigger the same compile error? What is missing from my code?

No, they are not the same at all.

In the vector example, you are doing v.remove(*value), ie. you are dereferencing the borrow, copying out of it. Thus, NLL can determine that you don't actually use the borrow. In your linked list example, however, you are still passing a reference to the node to remove() (because you are not dereferencing the return value of find()).


By the way, your example with Vec has the wrong semantics. Vec::remove() removes by index, so your code would always remove the 4th element (ie., the one at index 3), not the element with value 3 (no matter its position).

1 Like

this type signature will never work. you cannot pass a mut reference which is part of the whole data structure to an method that also takes self by mut reference.

2 Likes

Thanks for the explanation! I totally missed that.
Yeah I noticed the semantic issue. I just picked a method (remove) that takes &mut self for the demo code.

Right, that makes sense, thanks for pointing out!

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.