Drop

スタックを作り、そこに push し、そこから pop できるようになり、しかもそれがすべて正しく動くことまでテストできました！

リストのクリーンアップについて心配する必要はあるでしょうか？技術的には、まったくありません！C++ と同様に、Rust はリソースが使い終わったときに自動的にクリーンアップするためにデストラクタを使用します。ある型が Drop というトレイトを実装している場合、その型にはデストラクタがあります。トレイトとは、Rust におけるインターフェイスの気取った呼び方です。Drop トレイトは次のインターフェイスを持ちます。

pub trait Drop {
    fn drop(&mut self);
}

基本的には、「スコープを抜けるときに、後始末をする時間を少しあげます」ということです。

Drop を実装している型を自分の中に含んでいて、やりたいことがそれらのデストラクタを呼ぶことだけであるなら、実際には Drop を実装する必要はありません。List の場合、やりたいことは head を drop することだけであり、それによって今度は Box<Node> を drop しようとするかもしれません。それらはすべて自動的に処理されます……ただし、ひとつ問題があります。

その自動処理はまずいことになります。

単純なリストを考えてみましょう。

list -> A -> B -> C

list が drop されると、A を drop しようとし、A は B を drop しようとし、B は C を drop しようとします。みなさんの中には、当然ながら不安になっている人もいるかもしれません。これは再帰コードであり、再帰コードはスタックを吹き飛ばす可能性があります！

みなさんの中には、「これは明らかに末尾再帰であり、まともな言語ならそのようなコードでスタックが吹き飛ばないことを保証するだろう」と考えている人もいるかもしれません。実は、これは間違いです！その理由を見るために、コンパイラが行わなければならないことを、コンパイラが行うように私たちの List に対して手動で Drop を実装することで書いてみましょう。

impl Drop for List {
    fn drop(&mut self) {
        // 注: 実際の Rust コードでは `drop` を明示的に呼び出すことはできません。
        // ここではコンパイラのふりをしています！
        self.head.drop(); // 末尾再帰 - 良い！
    }
}

impl Drop for Link {
    fn drop(&mut self) {
        match *self {
            Link::Empty => {} // 完了！
            Link::More(ref mut boxed_node) => {
                boxed_node.drop(); // 末尾再帰 - 良い！
            }
        }
    }
}

impl Drop for Box<Node> {
    fn drop(&mut self) {
        self.ptr.drop(); // おっと、末尾再帰ではない！
        deallocate(self.ptr);
    }
}

impl Drop for Node {
    fn drop(&mut self) {
        self.next.drop();
    }
}

Box の内容を解放した後で drop することはできないため、末尾再帰的な方法で drop する手段はありません！代わりに、List のために、ノードを Box から取り出す反復的な drop を手動で書く必要があります。

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty);
        // `while let` == 「このパターンがマッチしなくなるまでこれを行う」
        while let Link::More(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
            // boxed_node はここでスコープを抜け、drop されます。
            // しかし、その Node の `next` フィールドは Link::Empty に設定されているため、
            // 無制限の再帰は発生しません。
        }
    }
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 1 test
test first::test::basics ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured

すばらしい！

早すぎる最適化のためのボーナスセクション！

私たちの drop の実装は、実は while let Some(_) = self.pop() { } と非常に似ており、こちらのほうが確かに単純です。これはどのように違うのでしょうか。また、リストを整数以外のものを格納するように一般化し始めたとき、そこからどのようなパフォーマンス上の問題が生じる可能性があるでしょうか？