Rust: Why the first borrow later used here?

tutorials
1

I am learning rust and was trying to implement a singly linked list. Everything went well until I tried to implement a function that removes the tail from the list.

The definition of the LinkedList:

pub struct LinkedList<T> {
    head: Link<T>,
}

#[derive(Debug)]
struct Node<T> {
    ele: T,
    next: Link<T>,
}

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

I first tried to use while let but failed:

impl<T: Copy + std::fmt::Debug> LinkedList<T> {
    pub fn pop_tail_not_working_1(&mut self) -> Option<T> {
        let mut cur = &mut self.head;
        while let Some(node) = cur {
            if node.next.is_none() {
                return cur.take().map(|tail| tail.ele);
            }
            cur = &mut node.next;
        }
        None
    }
}

with the error message

error[E0499]: cannot borrow `*cur` as mutable more than once at a time
  --> src/linked_list.rs:66:24
   |
64 |         while let Some(node) = cur {
   |                        ---- first mutable borrow occurs here
65 |             if node.next.is_none() {
66 |                 return cur.take().map(|tail| tail.ele);
   |                        ^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        first borrow later used here

Then I tried the loop + match, still failed:

impl<T: Copy + std::fmt::Debug> LinkedList<T> {
    pub fn pop_tail_not_working_2(&mut self) -> Option<T> {
        let mut cur = &mut self.head;
        loop {
            match cur {
                None => return None,
                Some(node) => {
                    if node.next.is_none() {
                        return cur.take().map(|tail| tail.ele);
                    }
                    cur = &mut node.next;
                }
            }
        }
    }
}

with similar error message:

error[E0499]: cannot borrow `*cur` as mutable more than once at a time
  --> src/linked_list.rs:54:32
   |
52 |                 Some(node) => {
   |                      ---- first mutable borrow occurs here
53 |                     if node.next.is_none() {
54 |                         return cur.take().map(|tail| tail.ele);
   |                                ^^^
   |                                |
   |                                second mutable borrow occurs here
   |                                first borrow later used here

Finally, I tried the match guard, and it worked

impl<T: Copy + std::fmt::Debug> LinkedList<T> {
    pub fn pop_tail(&mut self) -> Option<T> {
        let mut cur = &mut self.head;
        loop {
            match cur {
                None => return None,
                Some(node) if node.next.is_none() => {
                    return cur.take().map(|tail| tail.ele);
                }
                Some(node) => cur = &mut node.next,
            }
        }
    }
}

I am not sure why the third implementation works but the first two don't, I think they all share the same logic. Specifically, I am really confused with the phrase first borrow later used here, I can't tell why the first borrow is used when the second mutable borrowed happen?

2

The third iteration does not have any code which requires both cur and node to live at the same time. In both of the first node needs to live up to cur = &mut node.next; because it is being used there, but you try to use cur.take() before. Compiler told you everything correctly, though I do not understand why “first borrow later used here” does not point to any location.

3

You hit a known limitation of the current borrow checker. It compiles with the next-gen checker (Polonius).

See more detail in this similar thread. Applying @steffahn's workaround in that thread works for your code as well.

1 Like
4

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.