为什么在Rust中先借用后使用？

Question

我正在学习Rust，并尝试实现一个单向链表。一切都很顺利，直到我尝试实现从链表中删除末尾节点的函数。

链表的定义如下：

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

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

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

我最初尝试使用while let但失败了：

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
    }
}

带有错误信息

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

然后我尝试了循环+匹配，但仍然失败了：

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;
                }
            }
        }
    }
}

出现相似的错误信息：

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

最后，我尝试了match守卫，并且它起作用了。

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,
            }
        }
    }
}

我不确定为什么第三种实现方法可行而前两种不行，我认为它们都使用了同样的逻辑。特别是，我对“先借后用”这个短语非常困惑，我无法理解为何在第二个可变借用发生时会使用第一个借用。

- DistributedSlacker

---

https://rust-unofficial.github.io/too-many-lists/ - Stargateur

@Stargateur 我认为 too-many-list 没有实现类似的功能，即从列表中删除尾部或任意链接的函数。 - DistributedSlacker

@SilvioMayolo 是的，我同意。但我尝试了 Rust 的困难方式。另外，第三个实现是有效的，我正在努力理解前两个实现的错误信息。 - DistributedSlacker

@SvetlinZarev 我已经请求管理员删除了它。但我认为自从一开始我在问题中描述了细节以来，它并没有完全改变。我不是在寻找解决方案，我已经在问题主体中发布了一个可行的实现，并正在寻找解释。 - DistributedSlacker

我经常感觉应该有一个好的参考资料，用大量真实案例来解释这些类型的错误。我很容易理解为什么最后两个实现会让人困惑。从语法上看，唯一的区别是匹配分支中的守卫表达式。也许只需简单明了地解释这一点就足够了。 - Todd

Answer 1

与引用相比，使用“拥有”的值要容易得多。

实现：

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)
    }
}

一个相当无聊的测试用例（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);
}

- Svetlin Zarev

---

是的，我同意“拥有值”可以让事情变得更简单。但我不想消耗原始数据结构。 - DistributedSlacker

从任何外部观察者的角度来看，数据结构在任何情况下都不会被“消耗”。由于Rust具有“零成本”抽象，复制Option<Box<T>>的成本与复制对Option<Box<T>>的引用相同，但无需与借用检查器搏斗。 - Svetlin Zarev

是的，这个实现绕过了借用检查器。但我们能否以一种更惯用的方式来完成它？ - DistributedSlacker

我认为在示例中使用.take()会消耗列表。.take()将所有权传递给调用者，并用None替换原始选项。 - Todd

@Todd 如果运行游乐场示例，你会发现它不会消耗列表。 - Svetlin Zarev

哦，我明白了。因为这行代码：*tail = Some(node); 把它放回去了。 - Todd

Answer 2

你可以跟踪你的链表大小，以便根据大小进行修改：

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());
    
}

游乐场

- Netwave