Drop

スタックを作りましたし，pushとpopもできるようになりましたし，テストまで実装して ちゃんと動くこともわかりました！

リストの後片付けをするコードを書く必要があるでしょうか？技術的には ノーです．全く必要ありません！C++のように，Rustはデストラクタを使って使い終わった リソースを自動的に解放してくれます．Dropという名前のトレイトを実装することで デストラクタを型に与えることができます．Rustではインターフェースをトレイト と呼びます．Dropはこんな感じのインターフェースです：

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

基本的には，スコープの外に出たときに後片付けのためにdropが実行されます．

実はDropを実装してある型を含む型に対してはDropを実装しなくてもよく，その Dropが実装してある型のデストラクタを呼べばいいだけです．私達が実装したListの場合 デストラクタではheadを消せばいいだけですから，何も実装しなくてもBox<Node>を 消してくれるはずです．全ては自動的に処理されます...が，一つだけ問題があります．

その自動処理はクソです．

こんな感じの簡単なリストを考えてみましょう：

list -> A -> B -> C

listがdropされるとき，listはAをdropしようとし，AはBを，BはCをdropしようとします． 不安になってきた人もいますよね？これは再帰なので，スタックを消費し尽くしてしまう 可能性があります！

「これは末尾再帰だから，ちゃんとした言語ならスタックが尽きないようにしてくれるだろ」 と思った人もいるでしょう．それは，実は，間違いです！理由を知るために，コンパイラが 実際にするであろう処理をdropとして実装してみましょう：

impl Drop for List {
    fn drop(&mut self) {
        // NOTE: 本当は`drop`を明示的に呼ぶことはできません
        // 今はコンパイラのふりをしています！
        self.head.drop(); // 末尾再帰 - good!
    }
}

impl Drop for Link {
    fn drop(&mut self) {
        match *self {
            Link::Empty => {} // おわり！
            Link::More(ref mut boxed_node) => {
                boxed_node.drop(); // 末尾再帰 - good!
            }
        }
    }
}

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した後に中身をdropすることはできません．したがって末尾再帰で このListをdropすることはできないのです！なのでBoxからNodeを取り出して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になっているので
            // dropは再帰しません
        }
    }
}

> 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() { }にとてもよく 似ていますし，そう書いたほうが簡潔です．これらの違いはなんでしょうか？ また，リストにint以外を入れた場合パフォーマンスにどのように影響する でしょうか？