Rust self borrowing issue

I'm working through Rust with too many linked list. In the fourth iteration, the example below mentions that the List was self borrowing.

pub struct List<'a, T> {
    head: Link<T>,
    tail: Option<&'a mut Node<T>>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<'a, T> List<'a, T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // When you push onto the tail, your next is always None
            next: None,
        });

        // Put the box in the right place, and then grab a reference to its Node
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // If the old tail existed, update it to point to the new tail
                old_tail.next = Some(new_tail);
                old_tail.next.as_mut().map(|node| &mut **node)
            }
            None => {
                // Otherwise, update the head to point to it
                self.head = Some(new_tail);
                self.head.as_mut().map(|node| &mut **node)
            }
        };

        self.tail = new_tail;
    }
}

The test would fail when pushing the second element into the queue.

        list.push(1);
        list.push(2);

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:68:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
68 |         list.push(1);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

The explanation of this error is that the list was storing a reference of itself inside itself. But I don't see how List is storing a reference of itself in push. I can't deduce where in push the the self-reference occurs.

It isn't that the list is referencing itself, but that the tail field contains a reference to an element that is owned by List. This is still considered "self-referential".

The problem with the second call to push is that the tail reference is mutable (must be unique). In this case push cannot be called a second time because it takes a unique reference to self while an existing unique reference is held in self.tail.

THis line takes a mut ref and return the mut ref to be assigned to tail. Is this the culprit?

  ...next.as_mut().map(|node| &mut **node)

This line, actually:

Because it is assigning tail in a self-referential way, this keeps self "locked" for the remainder of its lifetime.

edit: It occurs to me that I probably misrepresented this line as being the only problem. This assignment and the lifetime annotation are mutually inclusive, i.e. the compiler needs both or it refuses to compile. It is the lifetime annotation itself which "holds the lock" for the remainder of the list's lifetime.

The first time push is called, the None path is taken. The second time push is called, the compiler notices the mutable aliasing, so the Some branch never gets a chance to execute. You can verify that by replacing the Some branch with unreachable!()... playground

Replacing this line with self.tail = None allows us to remove the 'a lifetime from push, which then allows the compiler to drop the borrow at the end of the call. playground

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.