分解する

pop_front は基本的に push_front と同じロジックを、逆向きにしたものであるはずです。試してみましょう。

pub fn pop_front(&mut self) -> Option<T> {
    // 古いheadをtakeして、-2になるようにする必要がある
    self.head.take().map(|old_head| {                         // -1 old
        match old_head.borrow_mut().next.take() {
            Some(new_head) => {                               // -1 new
                // リストは空にならない
                new_head.borrow_mut().prev.take();            // -1 old
                self.head = Some(new_head);                   // +1 new
                // 合計: -2 old, +0 new
            }
            None => {
                // リストが空になる
                self.tail.take();                             // -1 old
                // 合計: -2 old, (newはなし)
            }
        }
        old_head.elem
    })
}

> cargo build

error[E0609]: no field `elem` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:64:22
   |
64 |             old_head.elem
   |                      ^^^^ unknown field

しまった。RefCells。たぶんまた borrow_mut しないといけないですね……。

pub fn pop_front(&mut self) -> Option<T> {
    self.head.take().map(|old_head| {
        match old_head.borrow_mut().next.take() {
            Some(new_head) => {
                new_head.borrow_mut().prev.take();
                self.head = Some(new_head);
            }
            None => {
                self.tail.take();
            }
        }
        old_head.borrow_mut().elem
    })
}

cargo build

error[E0507]: cannot move out of borrowed content
  --> src/fourth.rs:64:13
   |
64 |             old_head.borrow_mut().elem
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot move out of borrowed content

はぁ

cannot move out of borrowed content

ふむ…… Box には本当に甘やかされていたようです。borrow_mut で得られるのは &mut Node<T> だけで、そこからムーブすることはできません！

必要なのは、RefCell<T> を受け取って T を返してくれる何かです。ドキュメントでそういうものがないか確認してみましょう。

fn into_inner(self) -> T

RefCell を消費し、ラップされている値を返します。

これは有望そうです！

old_head.into_inner().elem

> cargo build

error[E0507]: cannot move out of an `Rc`
  --> src/fourth.rs:64:13
   |
64 |             old_head.into_inner().elem
   |             ^^^^^^^^ cannot move out of an `Rc`

ああ、だめでした。into_inner は RefCell からムーブしたがりますが、それはできません。なぜなら RefCell は Rc の中にあるからです。前の章で見たように、Rc<T> はその内部への共有参照を得ることしか許してくれません。それは当然です。なぜなら、それこそが参照カウントポインターの存在意義そのものだからです。共有されるのです！

参照カウントされたリストに Drop を実装しようとしたとき、これは問題になりました。そして解決策も同じです。Rc::try_unwrap です。これは refcount が 1 の場合に Rc の中身を取り出します。

Rc::try_unwrap(old_head).unwrap().into_inner().elem

Rc::try_unwrap は Result<T, Rc<T>> を返します。Result は基本的に一般化された Option で、None の場合にデータが紐づいているものです。この場合は、unwrap しようとした Rc です。失敗する場合については気にしないので（プログラムを正しく書けていれば、これは成功しなければなりません）、単にそれに対して unwrap を呼びます。

さて、次はどんなコンパイラーエラーが出るか見てみましょう（正直、出るに決まっています）。

> cargo build

error[E0599]: no method named `unwrap` found for type `std::result::Result<std::cell::RefCell<fourth::Node<T>>, std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>>` in the current scope
  --> src/fourth.rs:64:38
   |
64 |             Rc::try_unwrap(old_head).unwrap().into_inner().elem
   |                                      ^^^^^^
   |
   = note: the method `unwrap` exists but the following trait bounds were not satisfied:
           `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>> : std::fmt::Debug`

うわあ。Result に対する unwrap は、エラーの場合をデバッグ出力できることを要求します。RefCell<T> は、T が Debug を実装している場合にのみ Debug を実装します。Node は Debug を実装していません。

それを実装するのではなく、ok で Result を Option に変換して回避しましょう。

Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem

頼む。

cargo build

よし。

ふぅ

やりました。

push と pop を実装しました。

古い stack の基本テストを拝借してテストしましょう（ここまでに実装したのはそれだけなので）。

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let mut list = List::new();

        // 空リストが正しく振る舞うことを確認
        assert_eq!(list.pop_front(), None);

        // リストに要素を追加
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        // 通常の削除を確認
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));

        // 何も壊れていないことを確認するため、さらにいくつかpush
        list.push_front(4);
        list.push_front(5);

        // 通常の削除を確認
        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(4));

        // 使い切ったことを確認
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);
    }
}

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 9 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::basics ... ok
test fifth::test::iter_mut ... ok
test third::test::basics ... ok
test second::test::iter ... ok
test third::test::iter ... ok
test second::test::into_iter ... ok

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

決まりました。

リストから要素を適切に取り除けるようになったので、Drop を実装できます。今回の Drop は概念的に少し興味深いものです。以前は、無制限の再帰を避けるためにわざわざスタックへ Drop を実装しましたが、今回はそもそも何かを起こすために Drop を実装する必要があります。

Rc はサイクルを扱えません。サイクルがあると、すべてが他のすべてを生かし続けます。実のところ、双方向リストは小さなサイクルが連なった大きな鎖にすぎません！ そのため、リストを drop すると、両端のノードの refcount は 1 までデクリメントされます……そしてその後は何も起きません。まあ、リストにノードがちょうど 1 つだけ含まれているなら問題ありません。しかし理想的には、リストは複数の要素を含んでいても正しく動作するべきです。そう思うのは私だけかもしれませんが。

見てきたように、要素の削除は少し面倒でした。なので、私たちにとって一番簡単なのは、None が返るまで単に pop し続けることです。

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

cargo build

（実際には、可変スタックでもこれを行うことはできましたが、近道は物事を理解している人のためのものです！）

push と pop の _back 版の実装を見てもよいのですが、それらは単なるコピペ作業なので、この章の後のほうに回します。今はもっと面白いものを見ていきましょう！