聊一聊 Rust 的 stack overflow

早上看到了这篇文章 智能指针有可能会让你的应用崩溃, 下面分析一下

会导致 stack overflow 的代码

struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>,
}
struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}
impl<T> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }
    fn push_front(&mut self, val: T) {
        let next = self.head.take();
        self.head = Some(Box::new(Node { val, next }));
    }
}

fn main() {
    let mut list = LinkedList::new();
    for i in 0..1000000 {
        list.push_front(i);
    }
}

playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=dfb32796d46df05fd6bcc4855fc11ae1

输出的结果:

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
timeout: the monitored command dumped core
/playground/tools/entrypoint.sh: line 11:     8 Aborted                 timeout --signal=KILL ${timeout} "$@"

原文中给出了解释:

程序崩溃是因为LinkedList的智能指针头部的默认释放导致对下一个节点的递归调用，这不是尾递归的，无法优化。修复方法是手动覆盖LinkedList数据结构的析构函数方法，迭代地释放每个节点，而不需要递归。从某种意义上说，这违背了智能指针的目的——它们无法从程序员那里解放手动内存管理的负担。

但是这个解释还不够直观，也没有给出修复代码

接下来我们一起以更直白的方式看看这个 LinkedList 被 Drop 时到底发生了什么

我们先给 Node<T> 和 LinkedList<T> 加上 Drop trait, 方便我们观察代码执行过程

struct Node<T> {
    val: T,
    next: Option<Box<Node<T>>>,
}
struct LinkedList<T> {
    head: Option<Box<Node<T>>>,
}
impl<T> LinkedList<T> {
    fn new() -> Self {
        Self { head: None }
    }
    fn push_front(&mut self, val: T) {
        let next = self.head.take();
        self.head = Some(Box::new(Node { val, next }));
    }
}

impl<T> Drop for Node<T> {
    fn drop(&mut self) {
        println!("drop node begin");
        let _ = self.next.take();
        println!("drop node end");
    }
}

impl<T> Drop for LinkedList<T> {
    fn drop(&mut self) {
        println!("drop linkedlist begin");
        let _ = self.head.take();
        println!("drop linkedlist end");
    }
}

fn main() {
    let mut list = LinkedList::new();
    for i in 0..1000000 {
        list.push_front(i);
    }
    println!("EOF");
}

playground: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=61f7aad2bf8ddcd133a146cd88744e97

查看执行结果:

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
timeout: the monitored command dumped core
/playground/tools/entrypoint.sh: line 11:     7 Aborted                 timeout --signal=KILL ${timeout} "$@"

跟原来的代码一致

查看标准输出:

EOF
drop linkedlist begin
drop node begin
drop node begin
drop node begin
(...)
drop node begin

省略处全部都是 drop node begin, 可见我们的程序在链式调用 Node<T> 的 drop 函数。因为 drop 一个 Node 就是依次 drop 它内部的 fields(val 和 next)，当所有 fields 被 drop 完了，这个 Node 结构也就算被释放了

问题就在它内部这个 next，它是一个链条，更准确的说应该是一个套娃