Drop メソッド

スタックを作成し，push を実装し，pop もできるようにし，さらにそれが全て正しく動くことのテストもやりました．

この上さらに drop を実装し，リストの片付けができるようにする必要があるのでしょうか？ 技術的には，全く必要ありません． C++ と同じように，Rust はリソースを使い終わった時に自動的にデストラクタを呼んでクリーンアップを行います． 型は，Drop という トレイト を実装している時にデストラクタを持ちます．

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

基本的に「スコープから出たら，さっさと荷物をまとめろ」ということです．

リストの要素の型に Drop が実装されていれば，実際に Drop を実装する必要はありません． デストラクタを呼び出すだけでいいのです． List の場合，デストラクタがやることはそのヘッドを drop することですが，その結果 Box<Node> を drop することになる可能性があります． その全てが自動的に処理されるのですが，一つだけ難点があります．

自動的な処理だとまずいことがあるのです．

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

list -> A -> B -> C

list がドロップされると，A をドロップしようとし，B をドロップしようとし，C をドロップしようとします． お分かりいただけたでしょうか…？ 処理が再帰的になっているので，スタックを吹っ飛ばしてしまう可能性があるのです．

「これは明らかに末尾再帰的だ．まともな言語であれば，このようなコードでスタックが吹っ飛ぶことはないはずだ」と思われた方もいらっしゃるかもしれません． これは，実は間違っているのです！ その理由を知るために，コンパイラが 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 の中身を deallocate した後にドロップすることはできないので，末尾再帰的な方法でドロップすることは できません． 代わりに，Node を Box から出すのを手動で繰り返す必要があります．

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 はスコープ外に出るので，ここでドロップされる
            // しかし，そのノードの `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

最高！

Bonus Section For Premature Optimization!

Our implementation of drop is actually very similar to while let Some(_) = self.pop() { }, which is certainly simpler. How is it different, and what performance issues could result from it once we start generalizing our list to store things other than integers?