聊一聊 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，它是一個鏈條，更準確的說應該是一個套娃