Rust: Why the first borrow later used here?

user_3461440 0
Viewed 319

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?

rust lifetime
2 Answers

You could track the size of your linked list so you know how to modify it depending on the size:

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

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

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

impl<T> LinkedList<T> {
    pub fn new() -> Self {
        Self {
            head: None,
            size: 0,
        }
    }

    pub fn pop_tail(&mut self) -> Option<T> {
        if self.size == 0 {
            return None;
        }
        if self.size == 1 {
            let res = self.head.take().map(|n| n.ele);
            self.size -= 1;
            return res;
        }
        let mut last_node = self.head.as_mut();
        for _ in 0..self.size-2 {
            last_node = last_node.and_then(|e| e.next.as_mut());
        }
        self.size -= 1;
        last_node.unwrap().next.take().map(|n| n.ele)
    }
}

fn main() {
    let mut list = LinkedList {
        head: Some(Box::new(Node {ele: 10, next: Some(Box::new(Node {ele: 20, next: None}))})),
        size: 2,
    };
    
    
    let value = list.pop_tail();
    println!("{}", list.size);
    println!("{}", value.unwrap());
    
}

Playground

user_16951720

It's much easier to work with "owned" values rather than with references.

Implementation:

impl<T> LinkedList<T> {
    pub fn pop_tail(&mut self) -> Option<T> {
        if self.head.is_none() {
            return None;
        }

        let mut node = self.head.take().unwrap();
        let mut tail = &mut self.head;

        while let Some(next) = node.next.take() {
            *tail = Some(node);
            tail = &mut tail.as_mut().unwrap().next;
            node = next;
        }

        Some(node.ele)
    }
}

A rather lame test-case (playground link):

fn main() {
    let mut head: LinkedList<i32> = LinkedList { head: None };
    println!("Before: {:?}", head);
    assert_eq!(None, head.pop_tail());
    println!("After: {:?}", head);

    let mut head = LinkedList {
        head: Some(Box::new(Node { next: None, ele: 1 })),
    };
    println!("Before: {:?}", head);
    assert_eq!(Some(1), head.pop_tail());
    println!("After: {:?}", head);

    let mut head = LinkedList {
        head: Some(Box::new(Node {
            ele: 1,
            next: Some(Box::new(Node { next: None, ele: 2 })),
        })),
    };
    println!("Before: {:?}", head);
    assert_eq!(Some(2), head.pop_tail());
    println!("After: {:?}", head);
}
user_25888000
Related