設計

で，片方向キューとは何でしょうか？片方向スタックのとき，私達はリストの最後にpushして同じ方向からpopしました．キューとスタックの違いはpopするのが逆側からであることだけです．スタックのときはこんな感じでした：

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

stack push X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)

stack pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

キューを作るには，popとpushのどちらでリストの最後の要素を操作するか決めなくてはいけません．片方向リストなのでどっちにしろ同程度の計算量になります．

pushを最後にするなら，リストをNoneが出るまでたどり新しい要素が入ったSomeに入れ替えます．

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

flipped push X:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

popを最後にするなら，リストをNoneが出る直前までたどりtakeします．

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

flipped pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

これのどちらかをやって完成でもいいですが，これではお粗末です！どちらにせよリストの全体をたどる必要があります．正しいインターフェースを提供しているのでキューの実装としてはこれでいいという人もいるでしょう．ですが私はパフォーマンスを保証することもインターフェースの一部であると考えます．漸近的境界がどうのという話ではなく速いか遅いかです．キューは popとpushが速いことを保証するデータ構造であり，リスト全体をたどる操作は明らかに速くはありません．

ひとつの重要な視点は，同じことを何回も繰り返してリソースを無駄にしていることです．この操作を記憶できないでしょうか？なんと，できます！リストの末尾へのポインタを持ち，そこに直接行けばいいのです！

リストの末尾を使う操作はpushとpopのどちらかで大丈夫です．popで使う場合末尾へのポインタを逆向きにたどる必要がありますが，片方向リストの性質上これを効率的に行うのは困難です．pushで使うようにすれば，popするときはリストの先頭のポインタを順方向にたどればいいので楽ですね．

試してみましょう：

use std::mem;

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // pushしたときのnextは常にNone
            next: None,
        });

        // 古いtailを新しいtailに更新
        let old_tail = mem::replace(&mut self.tail, Some(new_tail));

        match old_tail {
            Some(mut old_tail) => {
                // もしtailがすでにあれば新しいtailを入れる
                old_tail.next = Some(new_tail);
            }
            None => {
                // そうでなければheadに入れる
                self.head = Some(new_tail);
            }
        }
    }
}

この手の操作を書くのはかなり慣れてきていると思うので実装のペースをすこし上げていきます．とはいえ上のようなコードを一発で書き上げる必要はありません．今まであったようなトライアンドエラーをとばして書いているだけです．実際私はこのコードを書くにあたってめちゃくちゃ間違えてます．私が出したエラーを全部見せていたらmutや;の書き忘れがあまりにも多く教本の体をなしていないでしょう．でも心配しないでください．これから別のエラーメッセージを沢山見ることになります！

> cargo build

error[E0382]: use of moved value: `new_tail`
  --> src/fifth.rs:38:38
   |
26 |         let new_tail = Box::new(Node {
   |             -------- move occurs because `new_tail` has type `std::boxed::Box<fifth::Node<T>>`, which does not implement the `Copy` trait
...
33 |         let old_tail = mem::replace(&mut self.tail, Some(new_tail));
   |                                                          -------- value moved here
...
38 |                 old_tail.next = Some(new_tail);
   |                                      ^^^^^^^^ value used here after move

クソ！

use of moved value: new_tail

BoxはCopyを実装していないので2箇所に入れることはできません．更に重要なことはBoxは中身の所有権を持つのでBoxがdropされたとき中身を解放しようとする点です．もしこの実装がコンパイルしてしまったらpushするたびにリストの末尾を2回解放することになります．というか実際私達のコードはpushのたびにold_tailを解放しています！ギエー！🙀

OK，でも私達は所有権を持たないポインタがなにか知っています．ふつうの参照です！

pub struct List<T> {
    head: Link<T>,
    tail: Option<&mut Node<T>>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // pushしたときのnextは常にNone
            next: None,
        });

        // Put the box in the right place, and then grab a reference to its Node
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // もしtailがすでにあれば新しいtailを入れる
                old_tail.next = Some(new_tail);
                old_tail.next.as_mut().map(|node| &mut **node)
            }
            None => {
                // そうでなければheadに入れる
                self.head = Some(new_tail);
                self.head.as_mut().map(|node| &mut **node)
            }
        };

        self.tail = new_tail;
    }
}

特にトリッキーなことはしていません．基本的な発想はさっきと同じで，違いは暗黙のリターンを使ってnew_tailを作っていることくらいです．

> cargo build

error[E0106]: missing lifetime specifier
 --> src/fifth.rs:3:18
  |
3 |     tail: Option<&mut Node<T>>, // NEW!
  |                  ^ expected lifetime parameter

ああそうでした．ライフタイムを与えなくてはいけません．うーん...ここのライフタイムは何でしょう？えっと，これってIterMutに似てますよね？IterMutと同じことをして，パラメータ名は'aを使いましょう：

pub struct List<'a, T> {
    head: Link<T>,
    tail: Option<&'a mut Node<T>>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<'a, T> List<'a, T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // pushしたときのnextは常にNone
            next: None,
        });

        // Put the box in the right place, and then grab a reference to its Node
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // もしtailがすでにあれば新しいtailを入れる
                old_tail.next = Some(new_tail);
                old_tail.next.as_mut().map(|node| &mut **node)
            }
            None => {
                // そうでなければheadに入れる
                self.head = Some(new_tail);
                self.head.as_mut().map(|node| &mut **node)
            }
        };

        self.tail = new_tail;
    }
}

cargo build

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/fifth.rs:35:27
   |
35 |                 self.head.as_mut().map(|node| &mut **node)
   |                           ^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 18:5...
  --> src/fifth.rs:18:5
   |
18 | /     pub fn push(&mut self, elem: T) {
19 | |         let new_tail = Box::new(Node {
20 | |             elem: elem,
21 | |             // pushしたときのnextは常にNone
...  |
39 | |         self.tail = new_tail;
40 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/fifth.rs:35:17
   |
35 |                 self.head.as_mut().map(|node| &mut **node)
   |                 ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 13:6...
  --> src/fifth.rs:13:6
   |
13 | impl<'a, T> List<'a, T> {
   |      ^^
   = note: ...so that the expression is assignable:
           expected std::option::Option<&'a mut fifth::Node<T>>
              found std::option::Option<&mut fifth::Node<T>>

わー，これはずいぶん詳細なエラーメッセージですね．これはすこし憂慮すべきエラーです．というのもこれによると私達はかなりめちゃくちゃなことをやっているからです．興味深いのは部分です：

the lifetime must be valid for the lifetime 'a as defined on the impl

selfを借用しているわけですが，コンパイラは少なくとも'aだけ生存して欲しがっています．ではselfが実際'aだけ生存すると示せばどうでしょう...？

    pub fn push(&'a mut self, elem: T) {

cargo build

warning: field is never used: `elem`
 --> src/fifth.rs:9:5
  |
9 |     elem: T,
  |     ^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

見てください，動きました！やった！

popも同様に実装します：

pub fn pop(&'a mut self) -> Option<T> {
    // リストの今のheadを取る
    self.head.take().map(|head| {
        let head = *head;
        self.head = head.next;

        // もし`head`がなかったらtailに`None`を入れる
        if self.head.is_none() {
            self.tail = None;
        }

        head.elem
    })
}

そしてちゃちゃっとテストを書いてしまいましょう：

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

        // 空のリストが動くことを確認
        assert_eq!(list.pop(), None);

        // リストの要素をつめる
        list.push(1);
        list.push(2);
        list.push(3);

        // 普通に要素を削除してみる
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), Some(2));

        // 何も壊れてないことを確認するためにもう一回push
        list.push(4);
        list.push(5);

        // 普通に要素を削除してみる
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(4));

        // リストを出し切ったとき
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), None);
    }
}

cargo test

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:68:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
68 |         list.push(1);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:69:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
69 |         list.push(2);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:70:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
70 |         list.push(3);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here


....

** まだまだあるエラー **

....

error: aborting due to 11 previous errors

🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀

何ということでしょう．

コンパイラは悪くありません．私達はたった今Rustの原罪¹を犯したのです．私達は自分への参照を自分自身の中に持ってしまいました．pushとpopの実装ではなんとかRustを言いくるめることができました（それができたのは衝撃的でしたが）．私はRustがpushとpopを見た時点では参照がそれ自身の中にあるかどうか分からなかったんだと思いますが--というか，Rustにはそういう概念がありません．自分自身への参照が動作しないのは単なる現象に過ぎず，根本的な問題ではありません．

私達のリストは使おうとした途端全てが空中分解します．pushやpopを呼んだ瞬間リストは自分への参照を持ち，詰みます．自分自身を借用しているのです．

popの実装を見るとなぜこれが危険であるかわかります：

// ...
if self.head.is_none() {
    self.tail = None;
}

もし私達がこれを忘れたらどうなっていたでしょう？リストのtailはリストから除外されたノードを指すことになります．リストから除外されたノードのメモリは解放され，Rust が防いでくれるはずのダングリングポインタが生まれてしまいます！

Rustはたしかにそういう危険から私達を守ってくれているのです．ただかなり... 回りくどいやりかたですが．

ではどうしたらいいでしょうか？またRc<RefCell>>地獄に戻る？

だめです．勘弁してください．

かわりに敷かれたレールを外れて生のポインタを使います．私達のリストはこんな感じになるでしょう：

pub struct List<T> {
    head: Link<T>,
    tail: *mut Node<T>, // DANGER DANGER
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

そしてこれが全てです．もうクソ雑魚参照カウント付動的借用チェックには頼りません！本物の，過酷な，未検査の，ポインタを使います．

みなさん，C言語でいきましょう．いつも，いつでもCで．

私はここに帰ってきました．もう準備はできてます．

Hello, unsafe.

訳注：Lust（色欲）とかかっている

あまりにも超大量の連結リストで学ぶRust

設計