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

困ったことがあったり，最終的なコードを全部見たいときはGithubを見てください！
訳に関する文句などはこちら

注意: この本は rustc 1.31 (Dec 8, 2018) でリリースされた Rust 2018 向けに書かれています．もしあなたのRustツールチェインが十分に新しければ，cargo new で作られた Cargo.toml ファイルはedition = "2018"という行を含んでいるはずです（もしあなたが遠い未来にこれを読んでいるなら，もっと新しい数字かもしれません）．古いツールチェインを使うこともできますが，秘密のハードモードが解除され，あなたはこの本に全く書かれていないコンパイルエラーに見舞われるでしょう．楽しそうですね．

私はよくRustでの連結リストの実装について質問を受けます．正直答えはあなたの要件によりますし，その場合ごとのちょうどいい答えを出すのは明らかに簡単ではありません．そんなわけで，そういった質問に一発でまるっと答えられるようにこの本を書きました．

この本では，6つの連結リストの実装を通してRustのプログラミングを基本から応用までお教えします．あなたはこんなことを学ぶでしょう：

ポインタ型：&, &mut, Box, Rc, Arc, *const, *mut
所有権，借用，継承可変性，内部可変性，Copy
用語：struct, enum, fn, pub, impl, use, ...
パターンマッチング，ジェネリクス，デストラクタ
テスト
unsafeの基本

そう，連結リストはこれ全部に触れなくては実装できないくらい本当に恐ろしい代物です．

サイドバーにありますが（モバイルデバイスで見ると畳まれてるかも），こういうものを実装します：

皆さんがちゃんとついてこられるように，私がターミナルに入力するコマンドは全部書いておきます．パッケージマネージャーもRust標準のCargoを使います．Cargoは Rustを書くのに必要不可欠というわけではありませんが，rustcディレクトリを使うよりかなりいいです．ちょっとRustを試してみるくらいのつもりなら， play.rust-lang.orgでブラウザから簡単なコードを実行することもできます．

では手始めにプロジェクトを作りましょう:

> cargo new --lib lists
> cd lists

作ったものに上書きしてしまわないように，それぞれのリストを別々のファイルに作ります．

本物のRustの学習には，コードを書いて，コンパイラにクソ怒られて，それが何を意味するかを解き明かそうとする体験がつきものです．私はそうした状況がなるべく沢山起こるようにしました．Rustのコンパイラが出す（たいてい）有用なエラーメッセージを読んで理解することは，能力あるRustプログラマになるために超重要なことです．

...というのは実は嘘です．これを書く間，私はお見せするよりずっとたくさんのコンパイルエラーにぶち当たりました．特に後ろの方の章ではどんな言語でもあるようなタイプミス/コピペミスのエラーをいちいち見せていません．これはコンパイラに怒られるコースをゆくガイド付きツアーです．

このツアーはゆっくり進みます．そして，正直なところクソ真面目にやるつもりはすこしもありません．プログラミングは楽しいものですよね，クソが！もしあなたが冗長さを嫌う，まじめで格式高い方ならこの本はあなた向きではありません．私が作る何もかもがあなた向きではありません．あなたの人生は間違っています．

どうしても要る公共広告

まず100%はっきりさせておきましょう．私は連結リストが大嫌いです．心の底から．連結リストはマジでひどいデータ構造です．もちろん連結リストが有用な場合もあります：

長大なリストを何回も分割したりくっつけたりするとき．何回も．
めっちゃすごいLockしたりFreeしたりする同期処理をするとき．
侵入型¹リストを使ってカーネルや組み込み系を実装するとき．
純粋な関数型言語を使っていて，セマンティクスが限定されていて可変性がないので連結リストが使いやすいとき．
... とか！

でも上のような場合はRustを書く人にとってはごくまれです．99%の場合Vec（配列スタック）でいいですし，残った1%のうちの99%はVecDeque（配列両端キュー）でいいです．Vecや VecDequeはメモリ割当頻度が少なく，メモリオーバーヘッドが小さく，ランダムアクセスができ，キャッシュ局所性があり，明らかにより優れたデータ構造です．

連結リストはトライ木と同じくらいニッチなデータ構造です．トライ木がニッチじゃないと言ってくる人はほとんどいないでしょう．あなたがエンジニアとしてやっていく分には一生学ばなくてすむのですから．それにもかかわらず連結リストはなぜか優遇されています．私達は学生達全員に連結リストの書き方を教えています．私はこいつだけを std::collectionsから消し損ないました．C++ではリストといえばこいつです！

私達は団結して連結リストが標準的なデータ構造として扱われることに反対すべきです．特定の状況ではいいデータ構造ですが，そういう状況は例外的で，誰もが遭遇するわけではありません．

何人かの人はこの公共広告の１段落目で読むのをやめて，私が挙げた連結リストの 素晴らしい用法を持ち出して私に反論しようとするでしょう．それは次の段落に書いてあるっての！

詳細な議論のために，私が今まで見た反論とそれに対する回答を書いておきます． Rustを学びたい方は遠慮なく一章へどうぞ！

パフォーマンスがいつも重要なわけじゃないだろ

そうですね！多分あなたのアプリケーションにI/O待ちがあるとか，とにかく関係ない感じなんでしょう．でもそれは連結リストを使うかどうかという問題じゃないですよね．それはあらゆるものを使うかどうかという問題です．なんで連結リストを使うんですか？連結ハッシュマップを使いましょう！

パフォーマンスが関係ないならもちろん素の配列を使ってもいいはずです．

ポインタを握ってればO(1)で分割して連結して挿入して削除できるじゃん

はい！Bjarne Stroustrup氏が書かれているように，これは実はどうもいいことです．ポインタを取得する時間が配列の要素を全部コピーする時間より大して速くない場合には．そして配列のコピーはかなり速いです．

分割・連結のコストがめちゃくちゃ大きくない限り，他のあらゆる操作がキャッシュやコードの煩雑さによってダメダメになり，長所を消してしまいます．

でもそうですね，もしあなたのアプリケーションが配列の分割・連結に大きな時間を使っているなら連結リストを使ううま味があるでしょう．

償却 2 する余裕ないんだけど

あなたはすでにニッチな話をしています――ほとんどの人は償却の余裕があります．しかも配列が償却されるのは最悪の場合で，あなたが配列を使うからと言って必ず償却が行われるとは限りません．配列の要素数を予め知ることができるなら（そうでなくても要素の上限を知ることができるなら）必要なメモリ空間をとっておくことができます．経験上，要素数を予め知ることはたいていできます．特にRustではすべてのイテレータがこのためのメソッドsize_hintを持っています．

この前提に立てば，pushとpopは例外なくO(1)の操作で，連結リストのpushとpop よりかなり速い操作になります．ただポインタを動かして，バイトデータを書き込んで， Integerをインクリメントすればいいだけです．データを割り当てる必要なんかありません．

で，連結リストが低遅延だから使うんでしたっけ？

でももしデータ長が予測できないなら，連結リストで償却を回避できます！

連結リストは消費メモリが少ない

うーん，これはちょっと込み入った話ですね．「標準的な」配列のリサイズ戦略は配列の半分が空になるように伸縮することです．たしかにこれは相当なメモリ空間を無駄にしています．特にRustでは，collectionの要素を削除しても自動的に縮めたりしません（なのでもう一度詰め込まない限り無駄になります）．したがって無駄にしてるメモリ空間と時間の積は無限に膨れていきます！

しかしこれは最悪の場合です．最良の場合では，配列スタックはたった3つのポインタぶんのオーバーヘッドしかありません．基本的にはないと言っていいでしょう．

一方で連結リストは，無条件に要素一個ごとにオーバーヘッドがあります．片方向リストではポインタ1つ，双方向リストではポインタ2つ分です．この場合配列と違い，オーバーヘッドの割合は要素のデータサイズと関係してきます．もしリストの要素がどデカい場合，オーバーヘッドはほぼ無視できるでしょう．一方要素が小さい場合（1バイトとか），ポインタのオーバヘッドは要素自体の 16倍です！（要素が32bitのときは8倍です）

実際は要素全体の長さを揃えるためパディングが付加されるので23倍（32bitのとき11倍）のことが多いでしょう．

ところでこれはアロケータの動きが最良の場合です．つまり，メモリの割当と解放が密に行われ，断片化によってメモリが無駄にならない場合です．

でも，そうです．もしバカでかい要素を扱っていて，操作の頻度が予測できて，賢いアロケータを使っているなら，メモリを節約できるでしょう！

いつも<関数型言語>で連結リスト使ってたんだよね

いいですね！連結リストは関数型言語では超いいですよね．ミューテーションなしで操作できて，再帰的に表現できて，遅延評価の魔法のおかでげで無限長のリストを扱えます．

特に優れている点は状態を持たずにイテレーションができる点です．イテレーションの次のステップに行くためにはただ次のノードに行けばよいのです．

しかし，Rustでは配列のパターンマッチができて，スライスを使って配列のサブセットを扱うことができることは言っておくべきでしょう．これらの機能は実際関数型言語のリストより表現の幅が大きいです．なぜなら配列の最後の要素や，「ある配列の最初と最後と最後から二番目の要素を除いた配列」などの狂った表現をを何でも扱えるからです．

でもスライスでリストを作ることができないのは確かです．分割することしかできません．

遅延評価についてはイテレータがあります．イテレータは無限の要素を持てて， map，filter，reverse，結合などの操作を関数型のリストのように行なえますし，これらの操作全てに遅延評価が適用されています．驚かないでいただきたいのですがスライスはすべてイテレータとして扱うことができます．

でもそうです．もし不変のセマンティクスしか使えなければ，連結リストはとてもよい選択でしょう．

誤解しないでいただきたいのですが，関数型言語が必ずしも雑魚いとか悪いとか言っているわけではありません．しかし基本的にセマンティクスが制限されているのは事実です．関数型言語においては，あるものがどのようであるかについて記述できますが どのように行われるかについて記述することができません．これは機能であり，それによっていろいろな変テコな操作ができるようになったり，あなたを煩わせることなく物事を成し遂げる最良の手段を取ることができるようになったりします．しかし，それはあなたの手を煩わせることができるという選択肢と引き換えに，です．たいてい緊急回避手段がありますが，そうでなければ手続き型コードを書くことになるでしょう．

関数型言語といえども，目的にあったデータ構造を選択する努力は行われるべきです．確かに片方向連結リストは制御フローの記述には適していますが，データを保存して検索するという目的には本当に向いていません．

連結リストは並列データ構造を作るのに適している！

そうですね！並列データ構造を書くということはまた別の問題であり，軽い問題でもありませんが，明らかに多くの人にとっては取り組もうとは思いもしないことでしょう．そして一度実装してしまったら，あなたは連結リストではなくMPSCキュー³なりなんなりを使うことになります．この場合連結リストはどっか遠くに行ってしまっています！

でもそうですね，並列処理の暗黒の世界において，連結リストは実績あるヒーローです．

侵入型うんたらかんたらカーネルや組み込みどうのこうの

はいニッチ．あなたは使ってる言語のランタイムすら使わない場合の話をしてます．それはあなたが変わったことをしてることを意味していますよね？

そのうえ激しくメモリ不安全です．

でももちろん，サイコーのメモリ節約リストをシステムに組み込んでください．

連結リストのイテレータは関係ない挿入/削除の影響を受けない

その話はかなりデリケートです．特にガベージコレクターがない場合には．多分ですがあなたの制御フローと所有権の設計はすこしごちゃごちゃしているかもしれません．詳しい状況によりますが．

でもそうですね，カーソルを使えば，本当にクールでクレイジーなことができます．

連結リストはシンプルだし教えるのに適してる！

うん，まあそうですね．あなたが読んでる本はそういう発想に基づいてます．まあ片方向リストはとてもシンプルなんですけど，双方向リストはちょっとひどいです．

閑話休題

はい，こんなものでしょう．では大量の連結リストを書いていきましょう．

第一章に行く！

訳注：intrusive．ポインタではなく値を直接保持するデータ構造

訳注：amortization．ここでは配列の要素数を上回る数の要素を加えようとした際配列のサイズを大きくする，実行時に行われる操作

訳注：Multi-Producer-Single-Consumer Queue．複数の入力と単一の出力を持つ並列処理向きのキュー

クソ片方向スタック

この章は異常に長い章になります．というのも，基本的にRustの全てをこの章で学ぶからというのと，より良い理解のために茨の道を通って実装するからです．

最初のリストをsrc/first.rsに作りましょう．そしたらRustにfirst.rsが私達のライブラリが使うファイルであることを教えなければなりません．必要なことはsrc/lib.rs （このファイルはCargoが自動的に作っておいてくれたはずです）にこのように書くことだけです：

// in lib.rs
pub mod first;

基本データ設計

よし，で，連結リストってなんでしょう？えー，基本的にはヒープに割り当てられたデータの山で（カーネル勢はちょっと黙っててください），それぞれが順番に互いのポインタを持っています．連結リストは，手続き型言語のプログラマが10m以内に近づかないものであり，関数型言語のプログラマがあらゆる用途に使うものです．それなら，関数型言語のプログラマにどんなものか説明してもらうのがよさそうですね．彼らはこんな感じの定義をよこすでしょう：

List a = Empty | Elem a (List a)

これはだいたい「リストは空か，リストが後ろにつながった要素である」みたいな感じに読めます． 直和型を用いた再起的な定義ですね．直和型というのは「異なる型の値を持つことができる型」のことです．Rustでは直和型はenumに相当します！もしCライクな言語に慣れているなら， Rustのenumはあなたが大好きなあのenumそのものです．じゃあ上の関数型の定義をRustっぽく書き換えてみましょう！

とりあえず話を簡単にするためにジェネリクスは使わず，32bit intだけを要素として持つことにします：

// in first.rs

// pubはListが外部から使えることを意味します
pub enum List {
    Empty,
    Elem(i32, List),
}

ぬわ疲．それじゃコンパイルしましょう：

> cargo build

error[E0072]: recursive type `first::List` has infinite size
 --> src/first.rs:4:1
  |
4 | pub enum List {
  | ^^^^^^^^^^^^^ recursive type has infinite size
5 |     Empty,
6 |     Elem(i32, List),
  |               ---- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `first::List` representable

えっと，あなたはどうか分かりませんが私は関数型界隈に裏切られた気分です．

エラーメッセージを見てみると（裏切られた絶望を乗り越えたあとで），rustcはまさにエラーを解決する方法を示しています：

insert indirection (e.g., a Box, Rc, or &) at some point to make first::List representable

おっけー，boxね．何それ？ググってみましょう．rust box...

std::boxed::Box - Rust

これかな...

pub struct Box<T>(_);

A pointer type for heap allocation.
See the module-level documentation for more.

リンクをクリックする

Box<T>, casually referred to as a 'box', provides the simplest form of heap allocation in Rust. Boxes provide ownership for this allocation, and drop their contents when they go out of scope.

Examples

Creating a box:

let x = Box::new(5);

Creating a recursive data structure:

（訳） Box<T>，通称BoxはRustにおける最も単純なヒープ割当を行います．Boxは割り当てられたメモリの所有権を持ち，内容物はBoxがスコープから外れたときにdropされます．

使用例

Boxを作る：

let x = Box::new(5);

再帰的なデータ構造を作る：
#[derive(Debug)]
enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil))));
println!("{:?}", list);
This will print Cons(1, Box(Cons(2, Box(Nil)))).

Recursive structures must be boxed, because if the definition of Cons looked like this:

Cons(T, List<T>),

It wouldn't work. This is because the size of a List depends on how many elements are in the list, and so we don't know how much memory to allocate for a Cons. By introducing a Box, which has a defined size, we know how big Cons needs to be.

（訳）これはCons(1, Box(Cons(2, Box(Nil))))をprintします．

再帰的なデータ構造はBoxを持たなくてはいけません．もしConsの定義がこのようであった場合：

Cons(T, List<T>),

これは動きません．なぜならListの大きさはその要素数によるため，Consのためにどのくらいメモリを割り当てればよいか分からないからです．定義された大きさを持つBoxを使うことで，どのくらいConsが大きければよいかあらかじめ知ることができます．

わお，うん．多分今まで見た中で一番知りたいことが書いてあるドキュメントですね．ドキュメントのまさに最初に書いてあるのは私達がやろうとしていたことそのものと，なぜそれが動かないのかと，どうやって直すかです．

ドキュメントが強すぎる．

よし，じゃあやってみましょう：

pub enum List {
    Empty,
    Elem(i32, Box<List>),
}

> cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

やった，ビルドが通りました！

...でもちょっと考えてみるとこれはかなりバカっぽいリストです．

要素が2つあるリストを考えてみましょう．

[] = スタック
() = ヒープ

[要素A, ポインタ] -> (要素B, ポインタ) -> (Empty *ゴミ*)

問題は2つあります：

最後のノードは「僕は実はノードじゃないヨ」を意味するデータを割り当てられている．
最初のノードは全くヒープのメモリ空間を割り当てられていない．

表面的には，これらは互いに打ち消し合っているように見えます．一方で追加のノードを割当て，もう一方では割り当てていない...でも次のようなデータ構造を見てみましょう：

[ポインタ] -> (要素A, ポインタ) -> (要素B, *null*)

この構成では要素数に関わらず各要素のためにヒープのメモリ空間を割り当てます．重要な違いは一つ目の設計にあったゴミがないことです．このゴミはなんなのでしょうか？それを知るために，enumがどのようにメモリに割り当てられるか見てみましょう．

一般にenumはこんな感じです：

enum Foo {
    D1(T1),
    D2(T2),
    ...
    Dn(Tn),
}

Fooはどの列挙子（D1, D2, .. Dn）であるかを表す整数をもつ必要があります．これが enumのタグです．それに加え，T1, T2, .. Tnのうち最大のものが入るメモリ空間が必要になります（あとメモリの整列のためのパディング）．

ここで発生している大いなるムダは，Emptyがたった1bitの情報であるにもかかわらずポインタ1個と要素1個分のメモリが必要であることです．Elemにいつ変換されてもいいようにしなくてはならないのです．そんなわけで1つ目の設計ではゴミデータを割り当てざるを得ず，2つ目の構成より若干大きいスペースが必要になります．

ノードの一つがヒープにないのも，常に全ノードがヒープに割り当てられるより，多分ビビるほど悪いです．ノードの扱いが統一的でないと，pushやpopではそれほど困らないかもしれませんが分割や結合の際に厄介なことになります．

それぞれの設計でリストを分割することを考えてみましょう：

設計1:

[要素A, ポインタ] -> (要素B, ポインタ) -> (要素C, ポインタ) -> (Empty *ゴミ*)

Cを分割:

[要素A, ポインタ] -> (要素B, ポインタ) -> (Empty *ゴミ*)
[要素C, ポインタ] -> (Empty *ゴミ*)

設計2:

[ポインタ] -> (要素A, ポインタ) -> (要素B, ポインタ) -> (要素C, *null*)

Cを分割:

[ポインタ] -> (要素A, ポインタ) -> (要素B, *null*)
[ポインタ] -> (要素C, *null*)

設計2では要素Bのポインタをスタックにコピーして，元あった場所をnullにするだけです．設計1でも同じことをしていますが，要素Cをヒープからスタックにコピーする必要があります．結合は同じことを逆にやるだけです．

連結リストの数少ない良いところのひとつに要素をノード自体の中で組み立て，メモリ空間を移動させずに順番を入れ替える事ができる点があります．ポインタをいじるだけでリスト内の順番が動くのです．設計1はこの特長を持ちません．

はい，設計1がクソなことが証明されました．ではどう書き直せばいいでしょうか？じゃあこんな感じで：

pub enum List {
    Empty,
    ElemThenEmpty(i32),
    ElemThenNotEmpty(i32, Box<List>),
}

悪化してるように見えたなら良かったです．特筆すべき点は，この設計はElemThenNotEmpty(0, Box(Empty)) というまったく無意味な状態を持てるようになっており，ロジックを複雑にしていることです．しかも相変わらずノードがスタックにあったりヒープにあったりします．

とはいえ，この設計はひとつ興味深い特徴を持っています：Emptyの状態がなく，ヒープの割当が1要素分小さいことです．不幸にもそれによって更に大きいメモリ空間を無駄にしているんですけどね！なぜかというと，先程の設計がヌルポインタ最適化を行っているからです．

さっきenumはどの列挙子を持つかを管理するタグを持っていると言いました．しかし，このような特別な形のenumについては：

enum Foo {
    A,
    B(ContainsANonNullPtr),
}

ヌルポインタ最適化が行われ，タグのためにはメモリ空間が使われなくなります．列挙子Aのとき enumはすべて0が割り当てられ，そうでないとき列挙子Bが割り当てられます．列挙子Bはnullでないポインタを含むため，中身が全て0ということはあり得ないのでこういう事ができるのです．かっこいい！

他にこういう最適化ができるenumの形はどんなのがあるか思いつきますか？実はいっぱいあります！これがRustがenumのメモリレイアウトを定義しない理由です．他にもいくつか複雑なRustの enumメモリレイアウト最適化戦略がありますが，ヌルポインタ最適化が明らかに一番重要です！ヌルポインタ最適化によって&, &mut, Box, Rc, Arc, VecなどをOption に入れてもオーバーヘッドが発生しません（これらの型についてはおいおい触れます）．

で，どうすればゴミデータの割当を防ぎ，統一的にメモリを割り当たうえでヌルポインタ最適化の恩恵を得ることができるでしょうか？要素を持つということとリストを新しく割り当てるということを切り離して考えるほうがよさそうです．そのためにはCライクな構造体についてもう少し考えなくてはいけません！

enumがいくつかある値のひとつを保持する型なら，構造体は複数を一度に保持する型です．リストを2つの型に分割しましょう．ListとNodeです．

さっきと同様Listは空（Empty）かリストが後ろにくっついた要素です．「リストが後ろにくっついた要素」を別の型で表現することでBoxをさらに最適化された状態にもっていくことができます：

struct Node {
    elem: i32,
    next: List,
}

pub enum List {
    Empty,
    More(Box<Node>),
}

ちゃんとできてるか確認してみましょう：

リストの末尾にゴミがない：OK!
enumがヌルポインタ最適化されている：OK!
ノードが統一的に割り当てられる：OK!

よし！これで問題があった（ことがRustの公式ドキュメントに指摘された）はじめの設計の問題点を克服しました．

> cargo build

warning: private type `first::Node` in public interface (error E0446)
 --> src/first.rs:8:10
  |
8 |     More(Box<Node>),
  |          ^^^^^^^^^
  |
  = note: #[warn(private_in_public)] on by default
  = warning: this was previously accepted by the compiler but
    is being phased out; it will become a hard error in a future release!

またRustに怒られました．Listを（外部から使ってほしいので）publicにしましたがNode をpublicにはしていませんでした．問題は，publicなenumの中は全てpublicでなくてはならないことです． Nodeをpublicにすることもできますが，一般にRustでは実装の詳細を隠蔽することが好まれます． Listを構造体にすることで実装の詳細を隠すことにしましょう：

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

Listはフィールドがひとつしかない構造体なので，サイズはフィールドと同じになります．ゼロコスト抽象化です．イエーイ！

> cargo build

warning: field is never used: `head`
 --> src/first.rs:2:5
  |
2 |     head: Link,
  |     ^^^^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

warning: variant is never constructed: `Empty`
 --> src/first.rs:6:5
  |
6 |     Empty,
  |     ^^^^^

warning: variant is never constructed: `More`
 --> src/first.rs:7:5
  |
7 |     More(Box<Node>),
  |     ^^^^^^^^^^^^^^^

warning: field is never used: `elem`
  --> src/first.rs:11:5
   |
11 |     elem: i32,
   |     ^^^^^^^^^

warning: field is never used: `next`
  --> src/first.rs:12:5
   |
12 |     next: Link,
   |     ^^^^^^^^^^

よっしゃ，コンパイルが通りました！Rustは私達が作ったものが完全に無駄だといってめちゃくちゃ怒ってます．headをどこでも使ってないし，プライベートフィールドなので外部からも参照できないからです．したがってLinkとNodeも同様に無意味というわけです．というわけで次はこれを解決しましょう．このリストを使うコードを実装していきましょう！

New

型に対して実装を行うためにはimplを使います：

impl List {
    // TODO: コードを書く
}

あとはコードの書き方がわかればいいだけです．Rustではこんな感じに関数を宣言します：

fn foo(arg1: Type1, arg2: Type2) -> ReturnType {
    // body
}

はじめに必要なのはリストを作る手段です．実装を隠蔽するので関数化する必要があります．Rustでの一般的なやりかたはスタティックメソッドを作るというもので， implのなかに普通に関数を書きます：

impl List {
    pub fn new() -> Self {
        List { head: Link::Empty }
    }
}

いくつか注意事項があります：

Selfというのは「上にあるimplのすぐ右に書いた型」のことです．繰り返しが少ないのはよいことですね！
構造体のインスタンスの生成は宣言とほぼ同じですが，フィールドの型を指定する代わりに値を与えます．
enumの列挙子の指定に::を使いました．これは名前空間を区切る識別子です．
関数の最後に書かれたものが返り値になります．これによって簡単な関数を若干きれいに書けます．もちろん他のCライク言語のようにreturn文を使って早期リターンすることもできます．

所有権

リストを作ることができるようになったので，次はリストで何かできるようになるといいですね．それを実現するために普通の（スタティックでない）メソッドを使います．メソッドはselfという型のない引数を持つ，関数の特別な形です：

fn foo(self, arg2: Type2) -> ReturnType {
    // body
}

selfは主に3つの形をとります：self，&mut self，そして &selfです．これらはRustにおける所有権の3つの形に対応しています：

self - 値
&mut self - 可変参照
&self - 共有参照

値は本物の所有権を表します．この値を煮るなり焼くなり動かすなり破壊するなり変更するなり参照を貸し出すなり自由です．何かの値を渡したとき，それは渡されたところにムーブされます．そして渡されたほうがその値の所有権を持つようになり，渡したほうからはアクセスできなくなります．なので，たいていのメソッドではselfを使いません．pushやpopするたびにアクセスできなくなるリストを使うのはそうとうアホですしね！

可変参照は，所有権を持たない値の一時的かつ排他的なアクセスを表します．可変参照を持つ値に対して何をしても大丈夫ですが，所有権を返すときに有効な状態にしておく必要があります（でないと借りた人に失礼ですからね！）．値を完全に書き換えてしまうこともできるので，別の値とすり替えるようなこともできます．値のすり替えはこのあと沢山やることになります．&mutに対して唯一できないことは代わりの値を用意せずにムーブしてしまうことです．&mut selfをもつメソッドはselfに対して変更を加えたいときにとても有用なメソッドです．

共有参照は，所有権を持たない値の一時的で，共有されたアクセスを表します．共有されているので，値に対して変更を加えることはできません．&は値を博物館のガラスケースに入れてるようなものだと考えてください．selfの状態を取得したいだけのときは&が特に有用です．

あとでこのルールは回避可能であることを見ていきます．共有参照が不変参照と呼ばれていないのはそういう理由からです．可変参照は唯一無二参照とか呼ばれるべきかもしれませんが，所有権と値の可変性は99%の場合直感に即していることがわかりました．

Push

ではリストに値を追加（push）する操作を書いていきましょう．pushはリストの変更を伴うので&mut selfを引数に取ります．pushするi32の値も引数に取る必要があります：

impl List {
    pub fn push(&mut self, elem: i32) {
        // TODO
    }
}

まずは要素をいれるNodeを作りましょう．

    pub fn push(&mut self, elem: i32) {
        let new_node = Node {
            elem: elem,
            next: ?????
        };
    }

nextには何が入るでしょうか？えーっと，リスト全部です！たぶん...こう？

impl List {
    pub fn push(&mut self, elem: i32) {
        let new_node = Node {
            elem: elem,
            next: self.head,
        };
    }
}

> cargo build
error[E0507]: cannot move out of borrowed content
  --> src/first.rs:19:19
   |
19 |             next: self.head,
   |                   ^^^^^^^^^ cannot move out of borrowed content

うえええええん．Rustは私達に正論を突きつけています．でもこれが具体的に何を意味するのか，あるいはどうすればいいかは判然としません：

cannot move out of borrowed content

私達はself.headをnextにムーブしようとしましたが，Rustはそういうことをやってほしくないようです．これをするとselfは一部が欠けた状態でこのメソッドから返されることになります．すでに見たとおり，これは&mutで唯一許されていないことです．借りたものをちゃんと返さないのは超失礼なことで，Rustはとても真面目なのです（超危険なことでもあるのですが，今回はそういう問題ではありません）．

では何かを戻したらどうでしょう？つまり，今作ったノードとか：

pub fn push(&mut self, elem: i32) {
    let new_node = Box::new(Node {
        elem: elem,
        next: self.head,
    });

    self.head = Link::More(new_node);
}

> cargo build
error[E0507]: cannot move out of borrowed content
  --> src/first.rs:19:19
   |
19 |             next: self.head,
   |                   ^^^^^^^^^ cannot move out of borrowed content

だめかー．原則的にはこれはRust的にはOKなのですが，実際にはだめです（理由はいくつかありますが，例外に対する安全性が一番深刻な問題です）．Rustに値を取ったと気づかれないように取る方法が必要です．ここは悪名高いRustのハッカー，インディ・ジョーンズに教えを請うことにしましょう：

mem::replaceの構えを取るインディ

ああ！インディはmem::replaceを使うことを提案しています．この超有能な関数を使うと，借りた値を代わりのものと入れ替えることで盗んでしまうことができます．まずは std::memをファイルの先頭に持ってきてmemをローカルスコープで使えるようにしましょう：

use std::mem;

そしていい感じに使います：

pub fn push(&mut self, elem: i32) {
    let new_node = Box::new(Node {
        elem: elem,
        next: mem::replace(&mut self.head, Link::Empty),
    });

    self.head = Link::More(new_node);
}

ここで，新しいノードをいれる前，一時的にself.headをLink::Emptyにしています．今から嘘をつきます．こういうことをしなきゃいけないのは不幸なことです．こうする他に方法はないのです（いまのところは）．

でもこれでpushは完成です！多分．多分テストしたほうが良さそうですね，正直．とりあえず一番簡単なやり方はpopを書いて，予期したとおりに動くことを確認することでしょう．

Pop

push同様，popもリストに変更を加えますが，pushと違い返り値があります．そしてリストが空の場合という厄介な状態を考えなくてはいけません．このケースに対処するために，信頼できるOption型を使います：

pub fn pop(&mut self) -> Option<i32> {
    // TODO
}

Option<T>は値が存在するかもしれないことを表すのに使われ，Some(T)かNone の状態を取ることができます．Linkのときやったように似たような型を自作することもできますが，このリストを使う人が戻り値の型が一体全体何なのか考えなくていいように， Optionという知らない人がいないほどありふれてる型を使います．実際あまりにも基礎的なので何も書かなくてもSomeとNoneと一緒にすべての.rsファイルにインポートされています（なのでOption::Noneとか書かなくてもいいのです）．

Option<T>のとげとげはOptionがTのジェネリック型であることを表しています．どんな型のOptionも作ることができるのです！

はい，で，このLinkとかいうのがあるわけですが，どうやってこれがEmptyかMoreか判断するのでしょうか？matchを使ったパターンマッチングです！

pub fn pop(&mut self) -> Option<i32> {
    match self.head {
        Link::Empty => {
            // TODO
        }
        Link::More(node) => {
            // TODO
        }
    };
}

> cargo build

error[E0308]: mismatched types
  --> src/first.rs:27:30
   |
27 |     pub fn pop(&mut self) -> Option<i32> {
   |            ---               ^^^^^^^^^^^ expected enum `std::option::Option`, found ()
   |            |
   |            this function's body doesn't return
   |
   = note: expected type `std::option::Option<i32>`
              found type `()`

おおおっと．popは値を返さなくてはいけませんが，まだ実装してませんでした． Noneを返すこともできますが，このような場合は関数がまだ未実装であることを表すunimplemented!()を返すのがよさそうです．unimplemented!()はマクロで（!がマクロであることを表しています），実行するとプログラムがパニックします（制御下でクラッシュさせます）．

pub fn pop(&mut self) -> Option<i32> {
    match self.head {
        Link::Empty => {
            // TODO
        }
        Link::More(node) => {
            // TODO
        }
    };
    unimplemented!()
}

無条件でパニックするような関数は発散する関数と呼ばれます．発散する関数は値を返さず，したがってどんな型の値としても使うことができます．ここではunimplemented!()の返り値をOption<T>として使っています．

returnを書かなくていいことにも注目してください．最後の表現（基本的には行）が暗黙的に関数の返り値になります．これでシンプルな関数をより簡潔に書くことができるのです．ほかのCライクな言語のように，明示的にreturnを使って早期リターンすることもできます．

> cargo build

error[E0507]: cannot move out of borrowed content
  --> src/first.rs:28:15
   |
28 |         match self.head {
   |               ^^^^^^^^^
   |               |
   |               cannot move out of borrowed content
   |               help: consider borrowing here: `&self.head`
...
32 |             Link::More(node) => {
   |                        ---- data moved here
   |
note: move occurs because `node` has type `std::boxed::Box<first::Node>`, which does not implement the `Copy` trait
  --> src/first.rs:32:24
   |
32 |             Link::More(node) => {
   |                        ^^^^

頼むぞRust，邪魔しないでくれ！いつもどおりRustは激おこです．ありがたいことに今回は何がいけないのか全部言ってくれています！デフォルトでは，パターンマッチをするときmatch節への値のムーブが発生します．しかし今回はself.headの所有権を持っていないためそれはできません．

help: consider borrowing here: `&self.head`

Rustはmatch節で参照を使えと言ってます．🤷‍♀️まあ試してみましょう：

pub fn pop(&mut self) -> Option<i32> {
    match &self.head {
        Link::Empty => {
            // TODO
        }
        Link::More(ref node) => {
            // TODO
        }
    };
    unimplemented!()
}

> cargo build

warning: unused variable: `node`
  --> src/first.rs:32:24
   |
32 |             Link::More(node) => {
   |                        ^^^^ help: consider prefixing with an underscore: `_node`
   |
   = note: #[warn(unused_variables)] on by default

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

warning: field is never used: `next`
  --> src/first.rs:14:5
   |
14 |     next: Link,
   |     ^^^^^^^^^^

イエーイ，コンパイルが通りました！ではTODOに入る処理を考えていきましょう． Optionを返したいので，そのための変数を作りましょう．EmptyのときにはNoneを返せばいいですね．MoreのときはSome(i32)を返し，Listのheadを更新します．じゃあとりあえずはこんな感じでどうでしょうか？

pub fn pop(&mut self) -> Option<i32> {
    let result;
    match &self.head {
        Link::Empty => {
            result = None;
        }
        Link::More(ref node) => {
            result = Some(node.elem);
            self.head = node.next;
        }
    };
    result
}

> cargo build
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0507]: cannot move out of borrowed content
  --> src/first.rs:35:29
   |
35 |                 self.head = node.next;
   |                             ^^^^^^^^^ cannot move out of borrowed content

(頭を机に伏せる)

共有参照しか持ってないnodeから値を取ろうとしているのがよくないようです．

ここは一旦私達が何をしようとしているのか考え直すべきでしょう．私達がやりたいのはこういうことです：

リストが空か確認する
もし空ならNoneを返す
もし空でないなら...
- リストのheadを消す
- headのelemを消す
- リストのheadを古いheadのnextに更新する
- Some(elem)を返す

重要な点は私達がなにかを消そうとしている点です．つまり，リストのheadの値を持っている必要があります．これは明らかに&self.headの共有参照を使っていては達成できません．そもそもこの関数はselfの可変参照しか持っておらず， 入れ替えることでしか値を取ることができません．これはまたEmptyの出番のようですね！

試してみましょう：

pub fn pop(&mut self) -> Option<i32> {
    let result;
    match mem::replace(&mut self.head, Link::Empty) {
        Link::Empty => {
            result = None;
        }
        Link::More(node) => {
            result = Some(node.elem);
            self.head = node.next;
        }
    };
    result
}

cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

や　っ　た　ぜ

一つの警告もなくコンパイルしました！！！！！

ちょっとここで個人的なlintを行いたいと思います．私達はresultを返り値にしていますが，実はそんなことをする必要はないのです！関数がその最後の行を返すように，全ての節もその最後の行を返すのです．普通はセミコロンをつけることで空タプル()を返すようにします．返り値を定義していない関数（pushみたいな）も空タプルを返します．

そんなわけで，popはこんなふうに書けます：

pub fn pop(&mut self) -> Option<i32> {
    match mem::replace(&mut self.head, Link::Empty) {
        Link::Empty => None,
        Link::More(node) => {
            self.head = node.next;
            Some(node.elem)
        }
    }
}

この方が簡潔で慣用的です．Link::Emptyのところにカッコがないことに注目してください．一つしか表現がないシンプルな場合にはこのように書くことができます．

cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

よしよし，これでも動きますね！

テスト

さてさて，pushとpopが書けたので実際にスタックをテストしてみましょう！ RustとCargoはテストを第一級の機能としてサポートしているので，テストを書くのは超カンタンです．関数を書いて#[test]アノテーションをつければよいだけです．

一般にRust界隈ではテストコードをテストされるコードの横に書く慣習があります．しかし，通常は名前の衝突を避けるためテストのための名前空間を用意します．first.rs をlib.rsで使えるようにmodを使ったのと同じように，modキーワードを使えば新しいファイルを作るのと同じようなことをインラインですることができます：

// in first.rs

mod test {
    #[test]
    fn basics() {
        // TODO
    }
}

cargo testで実行します．

> cargo test
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
    Finished dev [unoptimized + debuginfo] target(s) in 1.00s
     Running /Users/ABeingessner/dev/lists/target/debug/deps/lists-86544f1d97438f1f

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

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

イエーイ　私達の何もしないテストは無事通りました！これを何もしなくないようにしていきましょう．そのためにはassert_eq!マクロを使います．これは不思議な魔法のたぐいではなく，与えた2つの値を比較してそれらが違えばパニックするだけです．キョドることでテストの失敗を知らせるのです！

mod test {
    #[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(3));
        assert_eq!(list.pop(), Some(2));

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

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

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

> cargo test

error[E0433]: failed to resolve: use of undeclared type or module `List`
  --> src/first.rs:43:24
   |
43 |         let mut list = List::new();
   |                        ^^^^ use of undeclared type or module `List`

おおっと！modで新しいモジュールを切ったのでListを明示的に宣言しなくてはいけません．

mod test {
    use super::List;
    // 後は同じ
}

> cargo test

warning: unused import: `super::List`
  --> src/first.rs:45:9
   |
45 |     use super::List;
   |         ^^^^^^^^^^^
   |
   = note: #[warn(unused_imports)] on by default

    Finished dev [unoptimized + debuginfo] target(s) in 0.43s
     Running /Users/ABeingessner/dev/lists/target/debug/deps/lists-86544f1d97438f1f

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

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

やりい！

でもこの警告は何でしょう...？Listはどう見ても使ってるだろ！

...でもテストのためだけに，ですね！コンパイラを黙らせるために（そしてこのパッケージを使う人にわかりやすいように）testモジュール全体をテストのときだけにコンパイルされるようにしましょう．

#[cfg(test)]
mod test {
    use super::List;
    // 後は同じ
}

これでテストは完成です！

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

いいですね！

Bonus

おまけ：早期最適化

私達が実装したdropはwhile let Some(_) = self.pop() { }にとてもよく似ていますし，そう書いたほうが簡潔です．これらの違いはなんでしょうか？また，リストにint以外を入れた場合パフォーマンスにどのように影響するでしょうか？

クリックして答えを見る

popはOption<i32>を返しますが，私達の実装ではLink（Box<Node>）に対する操作を行います．つまり，私達の実装はNodeのポインタを動かすだけであるのに対し，popはNodeの値をムーブするのです．もしListを一般化してDrop実装済みめちゃデカ型（VeryBigThingWithADropImpl 　略して　VBTWADI）も入れられるようにしたとき，これは超コストのかかる操作になるおそれがあります．しかし，Boxは内容物のDropをそのまま呼べるのでこの問題を回避することができます．VBTWADIを入れることこそがまさしく配列ではなく連結リストを使うメリットなので，VBTWADIを使うときパフォーマンスが良くなかったらちょっと残念ですよね．

両方の実装のいいとこ取りをしたいなら，新しくfn pop_node(&mut self) -> Linkというメソッドを作り，これを使ってpopとdropを実装するのがいいでしょう．

最終コード

はい，このコードを書くまでに6000語（翻訳前）かかりました：


# #![allow(unused_variables)]
#fn main() {
use std::mem;

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

impl List {
    pub fn new() -> Self {
        List { head: Link::Empty }
    }

    pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: mem::replace(&mut self.head, Link::Empty),
        });

        self.head = Link::More(new_node);
    }

    pub fn pop(&mut self) -> Option<i32> {
        match mem::replace(&mut self.head, Link::Empty) {
            Link::Empty => None,
            Link::More(node) => {
                self.head = node.next;
                Some(node.elem)
            }
        }
    }
}

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty);

        while let Link::More(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
        }
    }
}

#[cfg(test)]
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(3));
        assert_eq!(list.pop(), Some(2));

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

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

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

マジかよ，80行しかないし半分はテストだぞ！最初に長い章になりますと言ったとおりになりましたね．

まあまあな片方向連結スタック

前章ではギリ実用に耐える片方向連結スタックを書きました．しかし，前章のリストにはいくつか設計上の問題があり，ゆえにクソです．これをクソじゃなくしていきましょう．そのためにこのようなことをしていきます：

車輪の再発明をやめる
どんな型も入れられるようにする
peekを実装する
イテレートできるようにする

そして，これらを通じて以下のことを学んでいきましょう：

Optionの応用
ジェネリクス
借用の寿命
イテレータ

second.rsという名前で新しいファイルを作りましょう:

// in lib.rs

pub mod first;
pub mod second;

そしてfirst.rsの内容をまるごとコピーしてください．

Optionを使う

特別目ざとい人は私達が劣化Optionを再発明したことに気づいたかもしれません：

enum Link {
    Empty,
    More(Box<Node>),
}

LinkはOption<Box<Node>>と同じことです．かといってOption<Box<Node>>をどこにでも書くのは気が引けますし，popの戻り値とは違いLinkは外部から見ることはできないので，これをLinkと呼び続けることは問題なさそうです．しかし，Optionには超いいメソッドがいくつもあり，Optionを使えば（私達がやったように）それらを自力で実装することもありません．なので全部Optionを使いましょう．まずは愚直に全部のMoreとEmptyをSomeとNoneに書き換えていきましょう：

use std::mem;

pub struct List {
    head: Link,
}

// 型エイリアスです！イエーイ！
type Link = Option<Box<Node>>;

struct Node {
    elem: i32,
    next: Link,
}

impl List {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: mem::replace(&mut self.head, None),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<i32> {
        match mem::replace(&mut self.head, None) {
            None => None,
            Some(node) => {
                self.head = node.next;
                Some(node.elem)
            }
        }
    }
}

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, None);
        while let Some(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, None);
        }
    }
}

これは若干良くなった程度ですが，さらなる良さがOptionのメソッドを使うことで得られます．

まずmem::replace(&mut option, None)はめっちゃよくある形で，あまりにもよくあるのでOptionにはそのためのtakeというメソッドがあります．

pub struct List {
    head: Link,
}

type Link = Option<Box<Node>>;

struct Node {
    elem: i32,
    next: Link,
}

impl List {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<i32> {
        match self.head.take() {
            None => None,
            Some(node) => {
                self.head = node.next;
                Some(node.elem)
            }
        }
    }
}

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

次にmatch option { None => None, Some(x) => Some(y) }もめっちゃよくある形で，あまりにもよくあるのでmapというメソッドがあります．mapにはSome(x)のx からSome(y)のyを作る関数を渡す必要があります．fnで関数を宣言して渡すのもいいですが，インラインで書くほうがいいでしょう．

そのためにはクロージャを使います．クロージャは，クロージャ外のローカル変数を参照することができる無名関数です．この強力な機能によって，条件に依存する処理を超簡単に書くことができます．matchを使っているのはpopだけですね．書き換えてみましょう：

pub fn pop(&mut self) -> Option<i32> {
    self.head.take().map(|node| {
        self.head = node.next;
        node.elem
    })
}

アーイイ．今回の変更で何もぶっ壊れてないことを確認しましょう：

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 2 tests
test first::test::basics ... ok
test second::test::basics ... ok

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

いいですね！次はコードの挙動を改善していきましょう！

あらゆるものをジェネリックにする

OptionとBoxですこしだけジェネリクスには触れました．しかし，これまではなんとかジェネリックな要素を持つ型を宣言することは避けることができていました．

実はジェネリック型の宣言はとても簡単です．とりあえず全部ジェネリックにしましょう：

pub struct List<T> {
    head: Link<T>,
}

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

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

コードに若干とげとげを追加することで唐突にジェネリックになりました．もちろんこれだけではだめです．コンパイラにバチクソ怒られるでしょう．

> cargo test

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> src/second.rs:14:6
   |
14 | impl List {
   |      ^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> src/second.rs:36:15
   |
36 | impl Drop for List {
   |               ^^^^ expected 1 type argument

ここでの問題は明らかです．私達はこのListとかいうのを扱っていますが，そんなものはもう存在しません．OptionやBoxのように，常にList<何か>を扱わなくてはいけないのです．

しかしこのimplに渡す何かとは何でしょうか？List同様，全てのコードがTに対して動いてほしいですよね．ではListと同じくimplもとげとげにしましょう：

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

    pub fn push(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.elem
        })
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

...そしてこれで終わりです！

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 2 tests
test first::test::basics ... ok
test second::test::basics ... ok

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

私達のコードはこれで完全に任意の型Tについてジェネリックになりました．いやマジ Rust楽勝だな．ここで一切の変更が加えられていないnewに注目してみましょう：

pub fn new() -> Self {
    List { head: None }
}

リファクタリングとコピペの守護神，Selfの栄光を讃えましょう．Listを生成する際 List<T>と書いていないことにも注目してください．List<T>を返す関数の戻り値であることから，関数を呼んだ側からTの型が推論されます．

さて，次は全く新しい処理を書いていきましょう！

Peek

前回実装する気もなかった機能はpeek¹です．これをやっていきましょう．やることといえば，リストのheadがあるときその参照を返せばいいだけです．簡単そうですね．やってみましょう：

pub fn peek(&self) -> Option<&T> {
    self.head.map(|node| {
        &node.elem
    })
}

> cargo build

error[E0515]: cannot return reference to local data `node.elem`
  --> src/second.rs:37:13
   |
37 |             &node.elem
   |             ^^^^^^^^^^ returns a reference to data owned by the current function

error[E0507]: cannot move out of borrowed content
  --> src/second.rs:36:9
   |
36 |         self.head.map(|node| {
   |         ^^^^^^^^^ cannot move out of borrowed content

ハァ〜今度はなんだよ？

mapはselfの値を取ってしまいますから，Optionの外に要素をムーブしてしまいます．前回はtakeした直後だったのでそれでよかったのですが，今回は値を取っておきたいのでだめです．これに対処する正しい方法はOptionが持つas_refメソッドを使うことです． as_refのシグネチャはこんな感じです：

impl<T> Option<T> {
    pub fn as_ref(&self) -> Option<&T>;
}

このメソッドはT型についてのOptionを，T型の参照についてのOptionに降格させます．これをmatchで自前実装することもできますが嫌ですね．それをやろうとすると Optionを剥がして詰め替えることをしなくてはいけません．幸いなことにそれは. 演算子がやってくれます．

pub fn peek(&self) -> Option<&T> {
    self.head.as_ref().map(|node| {
        &node.elem
    })
}

cargo build

    Finished dev [unoptimized + debuginfo] target(s) in 0.32s

はいバッチリ

これの可変バージョンをas_mutで作ることもできます：

pub fn peek_mut(&mut self) -> Option<&mut T> {
    self.head.as_mut().map(|node| {
        &mut node.elem
    })
}

lists::cargo build

楽勝か？

テストも忘れず書きましょう：

#[test]
fn peek() {
    let mut list = List::new();
    assert_eq!(list.peek(), None);
    assert_eq!(list.peek_mut(), None);
    list.push(1); list.push(2); list.push(3);

    assert_eq!(list.peek(), Some(&3));
    assert_eq!(list.peek_mut(), Some(&mut 3));
}

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 3 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::peek ... ok

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

いいですね．しかし，これではpeek_mutで取った値が本当に可変かどうかわかりませんよね？値が可変だとしても、誰も変更しなかったら可変性をテストしたと本当に言えるでしょうか？返り値のOption<&mut T>にmapを使って全然違う値を突っ込んでみましょう：

#[test]
fn peek() {
    let mut list = List::new();
    assert_eq!(list.peek(), None);
    assert_eq!(list.peek_mut(), None);
    list.push(1); list.push(2); list.push(3);

    assert_eq!(list.peek(), Some(&3));
    assert_eq!(list.peek_mut(), Some(&mut 3));
    list.peek_mut().map(|&mut value| {
        value = 42
    });

    assert_eq!(list.peek(), Some(&42));
    assert_eq!(list.pop(), Some(42));
}

> cargo test

error[E0384]: cannot assign twice to immutable variable `value`
   --> src/second.rs:100:13
    |
99  |         list.peek_mut().map(|&mut value| {
    |                                   -----
    |                                   |
    |                                   first assignment to `value`
    |                                   help: make this binding mutable: `mut value`
100 |             value = 42
    |             ^^^^^^^^^^ cannot assign twice to immutable variable          ^~~~~

コンパイラはvalueが不変だと言って怒っています．でも明らかに&mut valueって書いてますよね．どゆこと？実はこの書き方はクロージャの引数が可変参照であることを指定していることにならないのです．そうではなく，引数に対してマッチするパターンを指定していることになります．|&mut value|は「この引数は可変参照だけど，こいつの値をコピーしてvalueに入れてね」という意味になります．|value|と書くことで valueの型を&mut i32にでき，headを変更できるようになります：

    #[test]
    fn peek() {
        let mut list = List::new();
        assert_eq!(list.peek(), None);
        assert_eq!(list.peek_mut(), None);
        list.push(1); list.push(2); list.push(3);

        assert_eq!(list.peek(), Some(&3));
        assert_eq!(list.peek_mut(), Some(&mut 3));

        list.peek_mut().map(|value| {
            *value = 42
        });

        assert_eq!(list.peek(), Some(&42));
        assert_eq!(list.pop(), Some(42));
    }

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 3 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::peek ... ok

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

かなり良くなりましたね！

訳注：スタックの一番上の要素をpopせずに取得する（覗き見る）機能

IntoIter

Rustでは要素の集まりをイテレートするときにはIteratorトレイトを使います．このトレイトはDropよりも若干複雑です：

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

ここでtype Itemというブロックが新しく出てきました．これはIteratorを実装する型には関連付けられた型があることを表しています．この場合nextしたときに出てくる型のことです．

nextがOption<Self::Item>を返す理由は，このメソッドがhas_nextとget_nextの役割を併せ持つからです．もし次の値があればSome(value)を返し，なければNoneを返すわけです．これによって，より人間工学的で安全なAPIを構築しつつhas_nextと get_nextを別々に実装した際の冗長さを回避できるのです．うまい手ですね！

悲しいことにRustには（まだ）yield文のようなものはありません．なのでそれに相当する処理を自力で実装する必要があります．さらに，実はイテレータには 3つの種類があり，それぞれを実装しなくてはいけません：

IntoIter - T
IterMut - &mut T
Iter - &T

実はIntoIterを実装するために必要なものはすでに揃っています．ただpopを呼びまくればいいだけです．IntoIterをListのラッパーとして，こんな感じに実装できます：

// タプル構造体はstructの変化形の一つです
// 他の型のラッパーを作るときに便利
pub struct IntoIter<T>(List<T>);

impl<T> List<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        // タプル構造体のフィールドには数字でアクセス
        self.0.pop()
    }
}

そしてテストを書きましょう：

#[test]
fn into_iter() {
    let mut list = List::new();
    list.push(1); list.push(2); list.push(3);

    let mut iter = list.into_iter();
    assert_eq!(iter.next(), Some(3));
    assert_eq!(iter.next(), Some(2));
    assert_eq!(iter.next(), Some(1));
    assert_eq!(iter.next(), None);
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 4 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok

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

いい感じですね！

Iter

さて，ではIterを実装していきましょう．今回はすでにある実装に頼るわけにはいかないので，自らの手で実装しましょう．基本的な処理は，次に返したいノードの一つ前のノードのポインタを握り続けることです．というのも，次に返したいノードが存在しないかもしれないからです（リストが空か，最後の要素を返した後そういうことになります）．参照はOptionである必要がありますね．要素を返したらそのノードのnextにポインタを移す処理が要ります．

よし，やってみましょう：

pub struct Iter<T> {
    next: Option<&Node<T>>,
}

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter { next: self.head.map(|node| &node) }
    }
}

impl<T> Iterator for Iter<T> {
    type Item = &T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &node);
            &node.elem
        })
    }
}

> cargo build

error[E0106]: missing lifetime specifier
  --> src/second.rs:72:18
   |
72 |     next: Option<&Node<T>>,
   |                  ^ expected lifetime parameter

error[E0106]: missing lifetime specifier
  --> src/second.rs:82:17
   |
82 |     type Item = &T;
   |                 ^ expected lifetime parameter

ああ，ライフタイムね...．ライフタイムについては聞いたことがあります．悪夢のような代物だと言う話ですが．

ちょっと新しいことをやってみましょう．error[E0106]っていうのがありますね？これはコンパイラエラーコードです．これが何なのかrustcに聞くことができるオプションが，えっと，--explainです：

> rustc --explain E0106
This error indicates that a lifetime is missing from a type. If it is an error
inside a function signature, the problem may be with failing to adhere to the
lifetime elision rules (see below).

Here are some simple examples of where you'll run into this error:

struct Foo { x: &bool }        // error
struct Foo<'a> { x: &'a bool } // correct

enum Bar { A(u8), B(&bool), }        // error
enum Bar<'a> { A(u8), B(&'a bool), } // correct

type MyStr = &str;        // error
type MyStr<'a> = &'a str; //correct
...

これは，その...あんまり助けになりませんね（このドキュメントは私達がいま持っているより深いRustへの理解を要求しています）でもこの'aっていうのをstructにつければ良さそうに見えますね？やってみましょう．

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

> cargo build

error[E0106]: missing lifetime specifier
  --> src/second.rs:83:22
   |
83 | impl<T> Iterator for Iter<T> {
   |                      ^^^^^^^ expected lifetime parameter

error[E0106]: missing lifetime specifier
  --> src/second.rs:84:17
   |
84 |     type Item = &T;
   |                 ^ expected lifetime parameter

error: aborting due to 2 previous errors

なるほど，だんだんパターンが見えてきました．このちっこいのをあらゆるところにつけまくってみましょう：

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> List<T> {
    pub fn iter(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.map(|node| &'a node) }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&'a mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &'a node);
            &'a node.elem
        })
    }
}

> cargo build

error: expected `:`, found `node`
  --> src/second.rs:77:47
   |
77 |         Iter { next: self.head.map(|node| &'a node) }
   |         ---- while parsing this struct        ^^^^ expected `:`

error: expected `:`, found `node`
  --> src/second.rs:85:50
   |
85 |             self.next = node.next.map(|node| &'a node);
   |                                                  ^^^^ expected `:`

error[E0063]: missing field `next` in initializer of `second::Iter<'_, _>`
  --> src/second.rs:77:9
   |
77 |         Iter { next: self.head.map(|node| &'a node) }
   |         ^^^^ missing `next`

あーっ．Rustが壊れてしまいました．

多分この'aが一体何を意味するのか知る必要がありそうです．

ライフタイムは沢山の人々を恐怖によって遠ざけてきました．プログラミングの黎明から私達が慣れ親しんできた概念を変えてしまうからです．これまではなんとかライフタイムから逃れ続けてくることができましたが，実はこれまでもずっと私達のプログラムに絡みついていたのです．

ライフタイムはガベージコレクションを持つ言語には必要のないものです．ガベージコレクタ― が魔法のように全ての寿命を管理してくれるからです．Rustではほとんどのデータが 手動で管理されるため，別のやり方が必要でした．CとC++から，人間にポインタを与えて管理させると制御不能のメモリ不安全性がはびこることがすでに分かっています．この不安全性の原因はおおむね次の2種類の誤りに分類できます：

スコープ外に出た物のポインタを持ち続ける
変更されてしまった物のポインタを持ち続ける

ライフタイムはどちらの問題も解決し，99%の場合透過的に処理してくれます．

で，ライフタイムとはなんでしょうか？

簡単に言うと，コードの中の特定の領域（ブロックやスコープ）のことです．終わり．借用がライフタイムに紐付けられたとき，その借用はそのライフタイムのあいだじゅう有効でなくてはならないことを表しています．様々な条件によって借用がどのくらい生存しなくてはいけないか，また生存できるかが決まります．とどのつまりライフタイムという仕組みは，それらの条件の中で借用の寿命を最小化する制約ソルバなのです．もしすべての条件を満たすライフタイムが見つかれば，コンパイルが通ります！さもなければ，何かの寿命が足りないというエラーが返ってくるでしょう．

一般に，関数内でのライフタイムについて言及する必要はありませんし，何があっても 言及したくないはずです．コンパイラは全ての借用の寿命を知っていて，ちゃんと最小のライフタイムを見つけることができます．しかしAPIレベルではコンパイラは十分な情報を持っていません．なので人間がライフタイムどうしの関係を手動で教えてあげる必要があるのです．

原則としては，依存パッケージも含めてライフタイムをチェックすれば人間が教える必要もないはずです．しかしそのようなチェックは膨大な処理が必要なうえ，別パッケージからのエラーを生み出して精神を破壊します．Rustは全ての借用を関数ごとに独立にチェックし，全てのエラーをローカルからのものにとどめています（さもなければあなたが宣言した型のシグネチャが誤っています）．

そういえば過去のコードで，借用を関数のシグネチャに書いたのにライフタイムを指定していないことがありましたね．実はあれはOKです！これはRustがライフタイムを自動で割り当ててくれるよくあるケースで，ライフタイムの省略と呼ばれています．

具体的にいうとこうです：

// 入力が一つしかないので出力のライフタイムはその一つしかない入力に依存すると推測する
fn foo(&A) -> &B; // これは次と同じ：
fn foo<'a>(&'a A) -> &'a B;

// たくさんある入力はそれぞれ独立のライフタイムだと推測する
fn foo(&A, &B, &C); // これは次と同じ：
fn foo<'a, 'b, 'c>(&'a A, &'b B, &'c C);

// メソッドの出力は`self`と同じだと推測する
fn foo(&self, &B, &C) -> &D; // これは次と同じ：
fn foo<'a, 'b, 'c>(&'a self, &'b B, &'c C) -> &'a D;

でfn foo<'a>(&'a A) -> &'a Bは何を意味するのでしょうか？これは要するに fooの引数は少なくとも返り値より長いライフタイムを持たなくてはいけないことを意味しています．つまり，fooの返り値をずっと引き回した場合，引数に与えた借用もずっと生存していなくてはいけません．返り値を使うのをやめたとき，コンパイラは引数も解放して大丈夫と判断します．

この仕組みがあることで，なにかのメモリ割り当てが解放された後に使われることも，なにかが借用されているのに変更されることも防ぐことができます．逆に言えばこの仕組みを守るだけでそれを達成できるのです！

さて，ではIterに話を戻しましょう．

ライフタイムがないバージョンに戻しましょう：

pub struct Iter<T> {
    next: Option<&Node<T>>,
}

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter { next: self.head.map(|node| &node) }
    }
}

impl<T> Iterator for Iter<T> {
    type Item = &T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &node);
            &node.elem
        })
    }
}

ライフタイムをつけなくてはいけないのは関数と型のシグネチャです：

// Iterは*何らかの*ライフタイムに対してジェネリックですが，それが何かはどうでもいいです
pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

// Listには紐づくライフタイムはないのでライフタイムパラメータなし
impl<T> List<T> {
    // iterに使われる*まさにその*借用のためにライフタイムを宣言しました
    // これで&selfはIterが生きる限り生き続ける必要があります
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.map(|node| &node) }
    }
}

// Iterにつける必要があるのでライフタイムは要ります
impl<'a, T> Iterator for Iter<'a, T> {
    // 型宣言なのでここにも要ります
    type Item = &'a T;

    // 上述のシュガーがあるのでここはライフタイムをつけなくても大丈夫です
    // Selfは相変わらずめっちゃ最高
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &node);
            &node.elem
        })
    }
}

おし，今回はうまく行くと思います．

cargo build

error[E0308]: mismatched types
  --> src/second.rs:77:22
   |
77 |         Iter { next: self.head.map(|node| &node) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

error[E0308]: mismatched types
  --> src/second.rs:85:25
   |
85 |             self.next = node.next.map(|node| &node);
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&'a second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

(╯°□°)╯︵ ┻━┻

OK．ライフタイムのエラーは直りましたが別の型エラーが出てきました．

&Nodeを保存したいのに&Box<Node>が返っていると．OK．簡単です．借用の前にBox を外せばいいわけですね：

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.map(|node| &*node) }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &*node);
            &node.elem
        })
    }
}

cargo build
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0515]: cannot return reference to local data `*node`
  --> src/second.rs:77:43
   |
77 |         Iter { next: self.head.map(|node| &*node) }
   |                                           ^^^^^^ returns a reference to data owned by the current function

error[E0507]: cannot move out of borrowed content
  --> src/second.rs:77:22
   |
77 |         Iter { next: self.head.map(|node| &*node) }
   |                      ^^^^^^^^^ cannot move out of borrowed content

error[E0515]: cannot return reference to local data `*node`
  --> src/second.rs:85:46
   |
85 |             self.next = node.next.map(|node| &*node);
   |                                              ^^^^^^ returns a reference to data owned by the current function

error[E0507]: cannot move out of borrowed content
  --> src/second.rs:85:25
   |
85 |             self.next = node.next.map(|node| &*node);
   |                         ^^^^^^^^^ cannot move out of borrowed content

(ﾉಥ益ಥ）ﾉ ┻━┻

as_refを忘れてました．そのせいでBoxをmapにムーブしてしまい，値がドロップされ，借用がもとの値を失ってしまったのです：

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.as_ref().map(|node| &*node) }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &*node);
            &node.elem
        })
    }
}

cargo build
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0308]: mismatched types
  --> src/second.rs:77:22
   |
77 |         Iter { next: self.head.as_ref().map(|node| &*node) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

error[E0308]: mismatched types
  --> src/second.rs:85:25
   |
85 |             self.next = node.next.as_ref().map(|node| &*node);
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&'a second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

😭

as_refを使ったのでもう一段参照外しが必要になりました：

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

cargo build

🎉 🎉 🎉

きっと「うわ，この&**とかいうのはマジでカスだな」と思ってることでしょう．あなたの感性は正しいです．通常Rustは参照外し型強制という機能でこういった操作を暗黙にやってくれます．参照外し型強制がすることは，基本的には*をコード中に入れて型が合うようにすることです．借用チェッカがあるため，ポインタがぐちゃぐちゃになっていないことが分かっているのでこういうことができるのです！

しかし，今回の場合&TではなくOption<&T>を使っていますね．これは参照外し型強制が適用されるには複雑すぎるのです．私の経験上，このような形は幸運にもあまりありません．

完璧を期すために，ターボフィッシュを使ってさらに型のヒントを与えることができます：

    self.next = node.next.as_ref().map::<&Node<T>, _>(|node| &node);

mapの実装を見ると，このようにジェネリックになっています：

pub fn map<U, F>(self, f: F) -> Option<U>

ターボフィッシュ（::<>）によって，コンパイラにmapがどの型を使えばいいか教えることができます．この場合::<&Node<T>, _>によって，「&Node<T>を返してね，でも他の型はどうでもいい」ということを言っています．

すると今度はコンパイラは&nodeに参照外し型強制が適用できることがわかるのでいちいち*をつける必要がなくなります！

でもこれはあんまり大きな進歩とは言えなそうですね．参照外し型強制とたまには使えるターボフィッシュを使いたい言い訳です😅

テストを書いて，動かなくなったりとにかく悪いことが起こったりしていないことを確認しましょう：

#[test]
fn iter() {
    let mut list = List::new();
    list.push(1); list.push(2); list.push(3);

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&3));
    assert_eq!(iter.next(), Some(&2));
    assert_eq!(iter.next(), Some(&1));
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 5 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::peek ... ok

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

イエ〜ィ．

最後に，ここのライフタイムを省略できることに触れておきます：

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

これは次のコードと同じです：

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

やった―！ライフタイムが減りました！

もしライフタイムが実際にはあるのに省略することが気になるのであれば， Rust2018の新機能，「ライフタイム省略明示」記号，'_を使うこともできます：

impl<T> List<T> {
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

IterMut

正直に言います．IterMutは治安が悪いです．この言葉自体が治安悪いですが， IterMutはIterと明らかに同じものです！

意味的にはそうですが，参照の基本に忠実に実装するとIterMutはガチの魔法になり，それに比べればIterは児戯に等しいと言えます．

私達がIterのために実装したIteratorに注目してください：

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> { /* stuff */ }
}

これはこのように書きかえることができます：

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next<'b>(&'b mut self) -> Option<&'a T> { /* stuff */ }
}

nextの入力のライフタイムと出力のライフタイムの間には何の関係もありません．なぜそんなことを気にするのでしょう？これのおかげでnextを無条件に呼びまくることができるからです！

let mut list = List::new();
list.push(1); list.push(2); list.push(3);

let mut iter = list.iter();
let x = iter.next().unwrap();
let y = iter.next().unwrap();
let z = iter.next().unwrap();

いいですね！

共有参照を使うなら間違いなくこれでOKです．共有参照はいくつでも持つことができるからです．しかし可変参照は同時に複数存在できません．

結局安全なコードを使う限り（この言葉の意味はまだ分かりませんが...）IterMutを実装するのはとてつもなく困難なのです．ところが驚くべきことにIterMutは大抵のstructに対し全くもって安全に実装することができます！

とりあえずIterのコードをコピーしてきて，全部可変にするところから始めましょう：

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<T> List<T> {
    pub fn iter_mut(&self) -> IterMut<'_, T> {
        IterMut { next: self.head.as_mut().map(|node| &mut **node) }
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

> cargo build
error[E0596]: cannot borrow `self.head` as mutable, as it is behind a `&` reference
  --> src/second.rs:95:25
   |
94 |     pub fn iter_mut(&self) -> IterMut<'_, T> {
   |                     ----- help: consider changing this to be a mutable reference: `&mut self`
95 |         IterMut { next: self.head.as_mut().map(|node| &mut **node) }
   |                         ^^^^^^^^^ `self` is a `&` reference, so the data it refers to cannot be borrowed as mutable

error[E0507]: cannot move out of borrowed content
   --> src/second.rs:103:9
    |
103 |         self.next.map(|node| {
    |         ^^^^^^^^^ cannot move out of borrowed content

この上下のエラーは別々のもののようです．一つ目はどうやって直すか書いてありますし簡単そうですね！共有参照を可変参照に昇格させることはできないのでiter_mutは&mut selfを引数にとらなくてはいけません．ただのコピペミスですね．

pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    IterMut { next: self.head.as_mut().map(|node| &mut **node) }
}

もう一つのエラーはなんでしょうか？

おっと！前章のiterのコードにバグがあったものの，幸いにも動いていたようです！

私達はCopyの魔法を初めて目の当たりにしています．私達が所有権を使い始めたとき，ムーブされてしまったものは使えないと言いました．幾つかの型に対しては，これは筋の通った挙動です．かしこいBoxくんはムーブした変数のヒープの割当を2つに増やしたりはしません．

しかし他の型については，この挙動はゴミです．例えば整数はただの数であり，所有権もクソもありません．そこで，整数型はCopy型のひとつに入れられています．Copy型はビットごとのコピーによって元通りコピーできる型を指し，ムーブされたときでも元の変数を依然使用できるという強力な特徴を持っています．同様にCopy型は，mem::replaceなどで代わりを用意しなくても参照から取り出すことができるのです！

Rustの数値プリミティブ型（i32, u64, bool, f32, char, などなど）はCopy型です．他の型も，構成要素が全てCopy型である限りCopy型にすることができます．

なぜIterのコードが動いていたかといえば，共有参照もCopy型だからです．そして&がCopy型なので Option<&>もCopy型です．そしてself.next.mapしたとき，Optionがコピーされるので今回私達が出会ったエラーは出なかったというわけです．しかし今回はCopy型ではない&mutを使っているため（もし&mutをコピーできたら同じメモリアドレスに2つの&mutを持つことになってしまいます），takeでOptionの中身を取らないといけません．

fn next(&mut self) -> Option<Self::Item> {
    self.next.take().map(|node| {
        self.next = node.next.as_mut().map(|node| &mut **node);
        &mut node.elem
    })
}

> cargo build

えー...と，やりました！IterMutができました！

テストしてみましょう：

#[test]
fn iter_mut() {
    let mut list = List::new();
    list.push(1); list.push(2); list.push(3);

    let mut iter = list.iter_mut();
    assert_eq!(iter.next(), Some(&mut 3));
    assert_eq!(iter.next(), Some(&mut 2));
    assert_eq!(iter.next(), Some(&mut 1));
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 6 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::peek ... ok

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

やった．うごいてますね．

マジか．

どういうことなの...

いや、ちゃんと動くように実装してはいましたよ．でもいつも何かに邪魔されるんです！ひとつはっきりさせておきましょう：

片方向連結リストの要素をひとつずつ，その可変参照を取得するコードを実装しました．そしてそれが動くことも確認しました．コードは安全です．なにも治安の悪いことをしてません．

私に言わせれば，これは結構すごいことです．うまく行った理由はいくつかあります：

私達はOption<&mut>をtakeしたので，排他的な可変参照を得ることができました．これによって複数回参照される心配はなくなりました．
Rustは，可変参照であるstructのフィールドを切り離しても大丈夫なことをわかっています．切り離されたフィールドから親をたどる手段がないからです．

これらの事実から，今回IterMutを実装した設計を流用して安全な配列やツリーも実装できる事がわかります！イテレータを双方向にして前と後ろから同時にイテレートすることすらできます！すごい！

最終コード

そんなこんなでこれが二つ目のリスト，その最終コードです！


# #![allow(unused_variables)]
#fn main() {
pub struct List<T> {
    head: Link<T>,
}

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 }
    }

    pub fn push(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.elem
        })
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| {
            &node.elem
        })
    }

    pub fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| {
            &mut node.elem
        })
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut { next: self.head.as_mut().map(|node| &mut **node) }
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        // タプル構造体のフィールドには数字でアクセス
        self.0.pop()
    }
}

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

#[cfg(test)]
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(3));
        assert_eq!(list.pop(), Some(2));

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

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

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

    #[test]
    fn peek() {
        let mut list = List::new();
        assert_eq!(list.peek(), None);
        assert_eq!(list.peek_mut(), None);
        list.push(1); list.push(2); list.push(3);

        assert_eq!(list.peek(), Some(&3));
        assert_eq!(list.peek_mut(), Some(&mut 3));

        list.peek_mut().map(|value| {
            *value = 42
        });

        assert_eq!(list.peek(), Some(&42));
        assert_eq!(list.pop(), Some(42));
    }

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&1));
    }

    #[test]
    fn iter_mut() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter_mut();
        assert_eq!(iter.next(), Some(&mut 3));
        assert_eq!(iter.next(), Some(&mut 2));
        assert_eq!(iter.next(), Some(&mut 1));
    }
}

#}

使えそうな感じになってきましたね！

永続的な片方向スタック

私達は片方向リストを完全に極めました．

単一の所有権だけでなく共有の所有権も扱うことにしましょう．永続的な片方向リストを作るのです．関数型プログラマのみなさんがおなじみのリストはこれです．リストの先頭もしくは末尾を取得できて，リストの先頭をを他のリストの末尾にくっつけることができて...あとは...そのくらいですかね．不変性というのはヤバいクスリですね．

この章の主眼はRcとArcと仲良くなることですが，同時に次章の全く新しい リストに備える章でもあります．

third.rsというファイルを加えましょう：

// in lib.rs

pub mod first;
pub mod second;
pub mod third;

今回は前のコードをコピペしません．無菌手術を執行します．

設計

では再び設計作業に入りましょう．

永続リストで最も重要なことはリストの末尾をほぼノーコストで操作できることです．

例えばこのような操作は永続リストではよくあることです：

list1 = A -> B -> C -> D
list2 = tail(list1) = B -> C -> D
list3 = push(list2, X) = X -> B -> C -> D

そして最終的にはメモリ上でこのような構造になっていてほしいのです：

list1 -> A ---+
              |
              v
list2 ------> B -> C -> D
              ^
              |
list3 -> X ---+

これはBoxでは実現できません．なぜならBが共有参照だからです．Bのメモリ割り当てが解放されるときはどんなときでしょう？今list2を解放したらBは解放されるべきでしょうか？ Boxを使うならそうなって然るべきです！

関数型言語では--ほぼすべての言語でそうですが--これをガベージコレクションで解決しています．ガベージコレクションの魔法のおかげでBが開放されるのはBを参照している全てが解放された後です．うほほーい！

Rustにはガベージコレクションがない代わりに，参照カウンタというものがあります．参照カウンタは極めてシンプルなGCみたいなものです．大抵の場合トレーシングGCよりも性能は著しく低いうえ，参照のループがあるとうまく動きません．でもこれしかないんだからしょうがないですね！幸い私達はループを作ることはないので（検証してみてください．自信あります）大丈夫です．

ではどうすれば参照カウンタを使えるのでしょう？Rcです！RcはBoxのようなものですが，複製することができ，そのメモリは参照が全て外されてはじめて解放されます．不幸にもこの柔軟性の代償は高くつきます．というのは，Rcの中身の共有参照しか得ることができないのです．つまり，Rcを使ったリストはデータを取り出すことも変更することもできないのです．

ではどういう設計になるでしょうか？前回はこうでした：

pub struct List<T> {
    head: Link<T>,
}

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

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

単にBoxをRcに変えるとどうでしょうか？

// in third.rs

pub struct List<T> {
    head: Link<T>,
}

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

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

cargo build

error[E0412]: cannot find type `Rc` in this scope
 --> src/third.rs:5:23
  |
5 | type Link<T> = Option<Rc<Node<T>>>;
  |                       ^^ not found in this scope
help: possible candidate is found in another module, you can import it into scope
  |
1 | use std::rc::Rc;
  |

はいクソ．私達が今まで使ってきたものと違い，RcはRustのプログラムにデフォルトでインポートされていないのでした．雑魚が．

use std::rc::Rc;

cargo build

warning: field is never used: `head`
 --> src/third.rs:4:5
  |
4 |     head: Link<T>,
  |     ^^^^^^^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

warning: field is never used: `elem`
  --> src/third.rs:10:5
   |
10 |     elem: T,
   |     ^^^^^^^

warning: field is never used: `next`
  --> src/third.rs:11:5
   |
11 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

大丈夫そうですね．Rustは相変わらずどうでもいいことをいちいち指摘していますが．でもこれはBoxをRcに書き換えて全部終わりにできそうですね！

...

だめです．そうは問屋がおろしません．

基本

Rustの基本についてはすでにだいぶ分かっていますので，簡単なコードをもう一度書くことは造作もありません．

コンストラクタはコピペで十分です：

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

今回はpushとpopは意味をなしません．代わりにだいたい同じ機能のappend とtailを実装しましょう．

リストに要素を追加するappendから始めましょう．この関数はリストと要素を一つずつとり，それらをくっつけたリストを返します．可変のリストのとき同様新しいノードを作りたいわけですが，そのノードのnextは元のリストを指している必要があります．目新しいことは，どうやってもとのリストに変更を加えずに nextを取得するかということくらいです．

その答えはCloneトレイトです．Cloneはほぼ全ての型に対して実装されており，元の参照から切り離された「元オブジェクトとだいたい同じもの」を得る手段を提供しています．C++のコピーコンストラクタに似ていますが，暗黙的に呼ばれることがない点が異なります．

特にRcはCloneを，参照カウントを増やすために使用しています．なのでRcを使う場合， Boxをサブリストにムーブする代わりに，単に古いリストのheadをCloneすることになります． headをmatchで取り出すことも必要ありません．なぜならOptionに実装されているCloneがまさに私達がやりたいことをやってくれるからです．

よし，じゃあやってみましょう:

pub fn append(&self, elem: T) -> List<T> {
    List { head: Some(Rc::new(Node {
        elem: elem,
        next: self.head.clone(),
    }))}
}

> cargo build

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

warning: field is never used: `next`
  --> src/third.rs:11:5
   |
11 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

うわ．Rustはフィールドを使っているかどうかにめちゃくちゃこだわりますね．このリストを使う人がフィールドを使ってるか知る手段がないと言っています．でもここまではよさそうです．

tailはappendと論理的に逆のことをします．リストを引数に取り，元のリストから先頭の要素を除いたリストを返します．やっていることはリストの二つ目の要素があればそれをCloneするということです．やってみましょう：

pub fn tail(&self) -> List<T> {
    List { head: self.head.as_ref().map(|node| node.next.clone()) }
}

cargo build

error[E0308]: mismatched types
  --> src/third.rs:27:22
   |
27 |         List { head: self.head.as_ref().map(|node| node.next.clone()) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::rc::Rc`, found enum `std::option::Option`
   |
   = note: expected type `std::option::Option<std::rc::Rc<_>>`
              found type `std::option::Option<std::option::Option<std::rc::Rc<_>>>`

ふむ．ぶっ壊れましたね．mapのクロージャはYを返して欲しがっていますが，私達は Option<Y>を返しています．幸いこれもOptionを使う上でよくあるパターンです． and_thenを使えばOptionを返すことができます．

pub fn tail(&self) -> List<T> {
    List { head: self.head.as_ref().and_then(|node| node.next.clone()) }
}

> cargo build

素敵．

これでtailができました．多分一つ目の要素を返すheadも作ったほうがいいでしょう．これはpeekと同じです：

pub fn head(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem )
}

> cargo build

やったぜ．

これだけの機能があればテストも書けそうです：

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

    #[test]
    fn basics() {
        let list = List::new();
        assert_eq!(list.head(), None);

        let list = list.append(1).append(2).append(3);
        assert_eq!(list.head(), Some(&3));

        let list = list.tail();
        assert_eq!(list.head(), Some(&2));

        let list = list.tail();
        assert_eq!(list.head(), Some(&1));

        let list = list.tail();
        assert_eq!(list.head(), None);

        // tailが空のとき動くことを確認
        let list = list.tail();
        assert_eq!(list.head(), None);

    }
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 5 tests
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok

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

完璧！

Iterも可変のリストのときと全く同じです：

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<T> List<T> {
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

#[test]
fn iter() {
    let list = List::new().append(1).append(2).append(3);

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&3));
    assert_eq!(iter.next(), Some(&2));
    assert_eq!(iter.next(), Some(&1));
}

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 7 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok

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

誰だ動的型付けのほうが簡単とか言ったバカは？

このリストにはIntoIterやIterMutは実装できないことに注意してください．私達は要素への共有参照しか持ってません．

Drop

可変のリスト同様，このリストもdropが再帰する問題を抱えています．確かに今回はそれほど大きな問題ではありません．リストの途中のどこかで他のリストに参照されているノードがあればそこでdropが止まるからです．とはいえ，依然として対処すべき問題であり，どうすればいいかは自明ではありません．前回はこうしました：

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

問題はループの中のところです：

cur_link = boxed_node.next.take();

これはBoxの中のNodeを変更していますが，今回はRcを使っているのでそれはできません．他のRcがこの同じノードを参照している可能性があり，私達は共有参照しか持っていません．

しかし，もし他の参照がないことがわかっていれば中のNodeをRcの外に出しても大丈夫なはずです．そして，もし大丈夫でないとき，それはdropを止めるときであるということを意味しています．

刮目してください．Rcにはまさにそのためのメソッド，try_unwrapがあります：

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut head = self.head.take();
        while let Some(node) = head {
            if let Ok(mut node) = Rc::try_unwrap(node) {
                head = node.next.take();
            } else {
                break;
            }
        }
    }
}

cargo test
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/too-many-lists/lists)
    Finished dev [unoptimized + debuginfo] target(s) in 1.10s
     Running /Users/ABeingessner/dev/too-many-lists/lists/target/debug/deps/lists-86544f1d97438f1f

running 8 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok

test result: ok. 8 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

やった！勝ち．

Arc

不変の連結リストを使う理由として，スレッド間でデータを共有したいというものがあります．とどのつまり，諸悪の根源は共有された可変な参照なので，この問題を解決する方法として 可変なというところを永久に葬り去ってしまうという手があります．

私達のリストはこれっぽっちもスレッドセーフではありません．スレッドセーフにしたければ参照カウントをアトミックにする必要があります．そうでなければ2つのスレッドが同時に参照カウントをインクリメントしようとし，片方だけが通ることがあり得ます．そうなればリストはまだ参照されているノードのメモリ割り当てを解放してしまうでしょう！

スレッドセーフにするためにはArcを使う必要があります．Arcはたった一つの特徴，参照カウントがアトミックに変更される点を除いてRcと完全に同じものです．Rcで十分な場合にはこれは若干の余分なオーバーヘッドを伴うので，ArcとRcのどちらも使えるようになっています．私達がすべきことはRcをstd::sync::Arcに変えるだけです．はい，もうスレッドセーフです．終わり！

しかし，ひとつ面白い疑問が湧いてきます．どうすればある型がスレッドセーフかどうか知ることができるでしょうか？私達は何かやらかしてしまったのでしょうか？

いいえ！Rustのスレッド安全性を脅かすことはできません！

なぜなら，RustはSendとSyncという2つのトレイトを使って，スレッド安全性を第一級の機能としてモデル化しているからです．

ある型は他のスレッドに安全にムーブできるときSendを持ちます．また，複数のスレッド間で共有できるときSyncを持ちます．つまりTがSyncのとき&TはSendです．ここで安全と言っているのはデータ競合を防げるという意味です（競合状態という，さらに一般的な問題と取り違えないでください）．

この2つはマーカートレイトです．つまりインターフェースの実装はありません．ある型は Sendであるかそうでないかの二択です．ほかのAPIが，ある型がSendであるかチェックしたりして使われるものです．そしてSendでない型なら他のスレッドに送ることができなくなります！すごい！

また，SendとSyncは型のフィールドが全てSendやSyncであるかどうかによって自動的に付与されます．Copyのときと似ていますが，自分で付与することもできる点が違います．

ほぼ全ての型はSendでありSyncです．たいていの型は自分自身のデータを所有しており，したがってSendです．また，たいていの型をスレッド間で共有する方法は共有参照を取って不変にすることだけであり，したがってSyncです．

しかし，なかには内部可変性という特徴を持ち，これらの条件に当てはまらない型があります．ここまで私達が見てきた可変性は継承可変性（もしくは外部可変性）とよばれるもので，値の可変性がその入れ物から継承されているものでした．継承可変性を持つ型は，不変な値のフィールドをなんとなく変更したりすることはできません．

内部可変性は違います．共有参照の中にあるものを変更できるのです．内部可変性はだいたい 2つに分けられます．単一スレッドでのみ動作するCellと，複数スレッドで動作するLockです． Cellのほうが低コストで使えることは明らかですね．あとはLockと似た動作をするプリミティブ型， atomicがあります．

で，こいつらがどうRcやArcと関係するのでしょうか？実はRcもArcも参照カウントのために内部可変性を持っているのです．更に悪いことに参照カウントは全てのインスタンス間で共有されているのです！RcはCellをつかっており，したがってスレッドセーフではありません． Arcはatomicを使っているのでスレッドセーフです．とはいえ，もちろんArcの中に型を突っ込むことでスレッドセーフにするようなことはできず，他の型と同じようにしかスレッド安全性を得られません．

私はぜっっっっったいにatomicのメモリ設計やSendを自分で実装することについて話したくありません．言うまでもないことですが，Rustのスレッド安全性の話に入り込むほど話は複雑になっていきます．Rustを普通に使う人は，そう動くもんだと思っていればこういったことについて考える必要はありません．

最終コード

不変のスタックについてはこれで全部です．だいぶリストの実装がうまくなってきましたね！


# #![allow(unused_variables)]
#fn main() {
use std::rc::Rc;

pub struct List<T> {
    head: Link<T>,
}

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

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

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

    pub fn append(&self, elem: T) -> List<T> {
        List { head: Some(Rc::new(Node {
            elem: elem,
            next: self.head.clone(),
        }))}
    }

    pub fn tail(&self) -> List<T> {
        List { head: self.head.as_ref().and_then(|node| node.next.clone()) }
    }

    pub fn head(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.elem)
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut head = self.head.take();
        while let Some(node) = head {
            if let Ok(mut node) = Rc::try_unwrap(node) {
                head = node.next.take();
            } else {
                break;
            }
        }
    }
}

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

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

    #[test]
    fn basics() {
        let list = List::new();
        assert_eq!(list.head(), None);

        let list = list.append(1).append(2).append(3);
        assert_eq!(list.head(), Some(&3));

        let list = list.tail();
        assert_eq!(list.head(), Some(&2));

        let list = list.tail();
        assert_eq!(list.head(), Some(&1));

        let list = list.tail();
        assert_eq!(list.head(), None);

        // tailが空のとき動くことを確認
        let list = list.tail();
        assert_eq!(list.head(), None);
    }

    #[test]
    fn iter() {
        let list = List::new().append(1).append(2).append(3);

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&1));
    }
}
#}

クソだけどメモリ安全な両端キュー

Rcと内部可変性について触れたので，こんな興味深い考えが浮かんできます...Rcを使えば値を変更することはできそうです．そしてもしそうなら，双方向リストを安全に実装できるかもしれません！

この章では内部可変性に詳しくなりましょう．そして安全であることは必ずしも正しいことを意味しないことをツラい方法で学んでいくことになるでしょう．双方向リストはむずかしいし，私はいつもどこかで何かを間違えます．

fourth.rsというファイルを新しく作りましょう：

// in lib.rs

pub mod first;
pub mod second;
pub mod third;
pub mod fourth;

今回も無菌手術です．でも，いつもみたいに過去の章のロジックを使い回すこともあるでしょう．

免責事項：この章はダメな例の実演です．

設計

今回のキモはRefCell型です．RefCellの重要な部分はこの2つのメソッドです：

fn borrow(&self) -> Ref<'_, T>;
fn borrow_mut(&self) -> RefMut<'_, T>;

borrowとborrow_mutの関係は&と&mutの関係と全く同じです． borrowは好きなだけ呼ぶことができますがborrow_mutは排他的にしか呼べません．

RefCellはこの条件をコンパイルタイムではなくランタイムにチェックします．もしルールが守られなければRefCellはパニックを起こし，プログラムはクラッシュします．ところで，このRefとかRefMutとかいう型はなんでしょう？これは基本的には借用のために使われるRcみたいなもので，これがスコープ外に出るまでRefCellは借用されたままになります．これについては後で触れます．

そしてRcとRefCellを使えば私達は...ビビるほど冗長であちこち可変だしサイクルを解放できないガベージコレクタを作れます！イエェェェェィ...

はい．今回は双方向連結でやっていきたいんでした．これはそれぞれのノードが一つ前と一つ次のノードを指すポインタを持っていることを意味しています．更にリスト自身ははじめのノードと最後のノードのポインタを持ちます．これによってはじめの要素と最後の要素の両方に対して高速な挿入と削除が行えます．

なので，多分私達が作りたいのはこんな感じのものでしょう：

use std::rc::Rc;
use std::cell::RefCell;

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

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

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

> cargo build

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

warning: field is never used: `tail`
 --> src/fourth.rs:6:5
  |
6 |     tail: Link<T>,
  |     ^^^^^^^^^^^^^

warning: field is never used: `elem`
  --> src/fourth.rs:12:5
   |
12 |     elem: T,
   |     ^^^^^^^

warning: field is never used: `next`
  --> src/fourth.rs:13:5
   |
13 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

warning: field is never used: `prev`
  --> src/fourth.rs:14:5
   |
14 |     prev: Link<T>,
   |     ^^^^^^^^^^^^^

見てください！ビルドしました！未使用コードの警告はありますがビルドは通っています！ではこのコードを使っていきましょう．

作る

ではリストを作る処理からやっていきましょう．これは素直に実装できます． newは相変わらず簡単で，単にNoneで埋めればいいだけです．ちょっと扱いにくくなりつつあるのでNodeのコンストラクタも作ってしまいましょう：

impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

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

> cargo build

**A BUNCH OF DEAD CODE WARNINGS BUT IT BUILT**

いえーい！

今度はリストの先頭に要素をpushする操作を書きましょう．双方向リストは明らかに単方向リストより複雑なのでちょっと手間をかける必要があります．単方向リストのときは関数を1行にすることもできましたが今回はそうはいきません．

とくにリストが空の場合の境界条件に対処する必要があります．大抵の処理は headとtailのどちらかのポインタを操作するだけでいいのですが，空リストがからむと両方を同時に操作する必要があります．

メソッドが機能しているかどうかチェックするには「それぞれのノードを指すポインタが 2つずつある」状態を保っているかを見ると簡単です．リストの間にあるノードは 1つ前と1つ後からのポインタがあり，リストの端のノードは片方がリスト自体からのポインタになりますよね．

やってみましょう：

pub fn push_front(&mut self, elem: T) {
    // 新しいノードはリンクの個数が+2され，他は+0であればよい
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            // 空でないリストなのでold_headをつなげる
            old_head.prev = Some(new_head.clone()); // +1 new_head
            new_head.next = Some(old_head);         // +1 old_head
            self.head = Some(new_head);             // +1 new_head, -1 old_head
            // 計：+2 new_head, +0 old_head -- OK!
        }
        None => {
            // 空リストなのでtailにセットする
            self.tail = Some(new_head.clone());     // +1 new_head
            self.head = Some(new_head);             // +1 new_head
            // 計：+2 new_head -- OK!
        }
    }
}

cargo build

error[E0609]: no field `prev` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:39:26
   |
39 |                 old_head.prev = Some(new_head.clone()); // +1 new_head
   |                          ^^^^ unknown field

error[E0609]: no field `next` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:40:26
   |
40 |                 new_head.next = Some(old_head);         // +1 old_head
   |                          ^^^^ unknown field

はいはい，コンパイルエラーね．まずはね．まずは．

なんでprevとnextを見れないのでしょうか？Rc<Node>だったときには動いていたので RefCellが邪魔してそうです．

ドキュメントを見てみるのがいいでしょう．

"rust refcell"でググる

最初のリンクをクリック

A mutable memory location with dynamically checked borrow rules

See the module-level documentation for more.

リンクをクリック

Shareable mutable containers.

Values of the Cell<T> and RefCell<T> types may be mutated through shared references (i.e. the common &T type), whereas most Rust types can only be mutated through unique (&mut T) references. We say that Cell<T> and RefCell<T> provide 'interior mutability', in contrast with typical Rust types that exhibit 'inherited mutability'.

Cell types come in two flavors: Cell<T> and RefCell<T>. Cell<T> provides get and set methods that change the interior value with a single method call. Cell<T> though is only compatible with types that implement Copy. For other types, one must use the RefCell<T> type, acquiring a write lock before mutating.

RefCell<T> uses Rust's lifetimes to implement 'dynamic borrowing', a process whereby one can claim temporary, exclusive, mutable access to the inner value. Borrows for RefCell<T>s are tracked 'at runtime', unlike Rust's native reference types which are entirely tracked statically, at compile time. Because RefCell<T> borrows are dynamic it is possible to attempt to borrow a value that is already mutably borrowed; when this happens it results in thread panic.

When to choose interior mutability

The more common inherited mutability, where one must have unique access to mutate a value, is one of the key language elements that enables Rust to reason strongly about pointer aliasing, statically preventing crash bugs. Because of that, inherited mutability is preferred, and interior mutability is something of a last resort. Since cell types enable mutation where it would otherwise be disallowed though, there are occasions when interior mutability might be appropriate, or even must be used, e.g.

Introducing inherited mutability roots to shared types.

Implementation details of logically-immutable methods.

Mutating implementations of Clone.

Introducing inherited mutability roots to shared types

Shared smart pointer types, including Rc<T> and Arc<T>, provide containers that can be cloned and shared between multiple parties. Because the contained values may be multiply-aliased, they can only be borrowed as shared references, not mutable references. Without cells it would be impossible to mutate data inside of shared boxes at all!

It's very common then to put a RefCell<T> inside shared pointer types to reintroduce mutability:
use std::collections::HashMap;
use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
    shared_map.borrow_mut().insert("africa", 92388);
    shared_map.borrow_mut().insert("kyoto", 11837);
    shared_map.borrow_mut().insert("piccadilly", 11826);
    shared_map.borrow_mut().insert("marbles", 38);
}
Note that this example uses Rc<T> and not Arc<T>. RefCell<T>s are for single-threaded scenarios. Consider using Mutex<T> if you need shared mutability in a multi-threaded situation.

（訳）

共有可能な可変コンテナ．

一般的なRustの型は可変参照（&mut T）を通してしか変更できませんが，Cell<T>型とRefCell<T>型の値は共有参照（&T）を通して変更される可能性があります．このことをもってCell<T>とRefCell<T> は「内部可変性」を持つと言います．これは他の普通の型が「継承可変性」を持つことと対照的です．

Cell型にはCell<T>とRefCell<T>の2種類があります．Cell<T>には内部の値を操作するためのget とsetメソッドがあります．しかしCell<T>はCopyを実装する型に対してしか機能しません．他の型に対してはRefCell<T>を使用することで変更する前に書き込みロックを獲得する必要があります．

RefCell<T>はRustのライフタイムを「動的借用」を実現するために使っています．動的借用とは一時的かつ排他的な可変参照を得るための手段です．通常のRustの借用がコンパイル時に静的にチェックされるのと違い，RefCell<T>による借用はランタイムにチェックされます．RefCell<T>の借用は動的であり，実際には排他的でない可変な借用が発生する可能性があるからです．もしそうなったときはスレッドがパニックします．

どんなときに内部可変性を使うべきか

値を変更するために排他的なアクセスを要求する継承可変性はRustの重要な言語機能の一つであり，それによってポインタエイリアスを推論したりクラッシュバグを防いだりすることができています．それゆえ継承可変性のほうが好まれ，内部可変性は最後の手段のようなものです．しかしCell型が普通ではできない値の変更を行えるため，内部可変性がふさわしい，もしくは必要である場合があります．例えば次のようなときです．

共有された型に継承可変性を持ち込むとき．

論理的に不変なメソッドの実装を行うとき．

Cloneの実装を変えるとき．

共有された型に継承可変性を持ち込むとき

Rc<T>やArc<T>のような共有スマートポインタ型は，内側の値を複数の部分から利用可能にします．内部の値は共有されているため，可変参照ではなく共有参照しか取得できません．Cell型なしではこれらの内部の値を変化させることは全くできないのです！

可変性を得るためにRefCell<T>をスマートポインタ型に入れることはとても一般的です：
use std::collections::HashMap;
use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
    shared_map.borrow_mut().insert("africa", 92388);
    shared_map.borrow_mut().insert("kyoto", 11837);
    shared_map.borrow_mut().insert("piccadilly", 11826);
    shared_map.borrow_mut().insert("marbles", 38);
}
この例ではArc<T>ではなくRc<T>を使っていることに注目してください．RefCell<T>は単一スレッドで動作します．もしマルチスレッドで共有可変性が欲しい場合Mutex<T>を使ってください．

いやー，Rustのドキュメントは相変わらずマジ最高ですね．

とくに注目したいのはここです：

shared_map.borrow_mut().insert("africa", 92388);

もっというとborrow_mutってやつです．RefCellから借用するときは明示的にやらなくてはいけないようです．.が勝手にやってくれないのは不思議な仕様ですね．まあやってみましょう：

pub fn push_front(&mut self, elem: T) {
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            old_head.borrow_mut().prev = Some(new_head.clone());
            new_head.borrow_mut().next = Some(old_head);
            self.head = Some(new_head);
        }
        None => {
            self.tail = Some(new_head.clone());
            self.head = Some(new_head);
        }
    }
}

> cargo build

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

ビルドしましたよ！またドキュメント勝ちしました．

崩す

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, (no 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

アーッ．RefCellか．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

Consumes the RefCell, returning the wrapped value.

これっぽいですね！

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をムーブしようとしますがRcの中にあるのでそれはできません．前章でみた通りRc<T>からは中身の共有参照しか取れません．でもそりゃそうですよね．参照カウンタがついた値は共有されるためのものなのですから！

この問題を解決するためには，前回と同様Rc::try_unwrapを使います．参照カウントが 1ならRcから中身を取り出すメソッドです．

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

Rc::try_unwrapはResult<T, Rc<T>>を返します．ResultはOptionを汎化したようなもので，Noneにデータを入れられるようになったものです．この場合None の代わりに返されるものは剥こうとしたRcです．今回は失敗の場合を考えないので（プログラムを正しく書けていれば成功するはずです）単にunwrapします．

とにかく，次はどんなコンパイルエラーが出るか見てみましょう（準備はよろしいですか？ 1個はあるはずです）．

> 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を実装する場合のみデバッグ出力できますが， NodeはDebugを実装していませんでした．

Debugを実装するより，okでResultをOptionに変換してしまう方がいいでしょう：

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

頼む！！！

cargo build

や　っ　た　ぜ

フゥ

やりました．

pushとpopができました．

はじめに作ったリストと実装した機能が同じなので，そっちからテストコードを盗んできてテストしましょう：

#[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を実装するに際し再帰が起こらないようにがんばる必要がありましたが，今回はとにかく何かが起こるようにがんばる必要があります．

Rcはサイクルを解放できません．サイクルがあるとそれぞれがそれぞれを生かし続けてしまします．双方向リストは，何と小さいサイクルを大量に集めたものに他なりません！双方向リストをDropしようとすると，端の2つのノードの参照カウントが1に減り...それ以上何も起こりません．ノードが1つだけなら上手くいきますが，リストには複数の要素を持つときにも動いてほしいですね．多分それは私だけでしょう．

すでに見たように，要素を削除するのはちょっと面倒です．一番簡単な方法はNoneが出るまで popし続けることでしょう：

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

cargo build

（実は可変なリストのときもこれと同じようにできたのですが，近道はちゃんと理解している人のためのものです！）

逆方向からのpushとpopの実装について見ていってもいいですが，ただのコピペなので後回しにします．先にもっと面白いものを見ていきましょう！

Peek

さて，pushとpopを実装しました．私はちょっと感動してます．マジで．コンパイル時の正確性があるというのは病みつきになりそうです．

簡単なpeek_frontでも実装して落ち着きましょう．いままでこのメソッドは簡単でしたし今回も簡単なはずです．そうですよね？

そうですよね？

実際コピペで済みそうです！

pub fn peek_front(&self) -> Option<&T> {
    self.head.as_ref().map(|node| {
        &node.elem
    })
}

ちょっと待った．今回はこうです．

pub fn peek_front(&self) -> Option<&T> {
    self.head.as_ref().map(|node| {
        // BORROW!!!!
        &node.borrow().elem
    })
}

どうよ．

cargo build

error[E0515]: cannot return value referencing temporary value
  --> src/fourth.rs:66:13
   |
66 |             &node.borrow().elem
   |             ^   ----------^^^^^
   |             |   |
   |             |   temporary value created here
   |             |
   |             returns a value referencing data owned by the current function

PC燃やしました．

片方向リストのときと同じロジックだろ．なんで違うんだ．なんで...

その答えはこの章から得られる教訓そのものです．その教訓とは，RefCellはあらゆるものに悲しみをもたらす存在であるということです．これまでRefCellはただの困ったちゃんでしたが，今悪夢と化しつつあります．

実際のところ何がどうなってるのでしょうか？それを理解するためにborrowの定義をもう一度見てみましょう：

fn borrow<'a>(&'a self) -> Ref<'a, T>
fn borrow_mut<'a>(&'a self) -> RefMut<'a, T>

設計の節でこのように書きました：

RefCellはこの条件をコンパイルタイムではなくランタイムにチェックします．もしルールが守られなければRefCellはパニックを起こし，プログラムはクラッシュします．ところで，このRefとかRefMutとかいう型はなんでしょう？これは基本的には借用のために使われるRcみたいなもので，これがスコープ外に出るまでRefCellは借用されたままになります．これについては後で触れます．

今がその「後」です．

RefとRefMutはそれぞれDerefとDerefMutを実装しています．これらは&T，&mut T と全く同じ動作をするようになっているのですが，トレイトの実装上，戻り値のライフタイムは RefCellではなくRefに紐付けられるようになっています．つまり戻り値の参照を使い続ける間ずっとRefを生かしておかなくてはいけないということになります．

実はこれは整合性を取るためには必要なことです．Refがdropされれば，RefCellはもうそれを借用しているものはないと判断してしまします．なのでもしRefより長く中の参照を持ち続けることができてしまったら，RefMutの排他性が損なわれRustの型システムを半壊させてしまいます．

結局どうしたらいいのでしょうか？ただ参照を返したいだけなのですが，参照を持ち続ける限り Refを持ち続けなくてはいけません．そしてpeekがreturnしたときRefはスコープ外に行ってしまいます．

😖

私が知る限りこれは手詰まりです．今回のような場合RefCellをカプセル化することはできないのです．

でも...もし実装の隠蔽を諦めたらどうでしょうか？Refを返したらどうなるのでしょう？

pub fn peek_front(&self) -> Option<Ref<T>> {
    self.head.as_ref().map(|node| {
        node.borrow()
    })
}

> cargo build

error[E0412]: cannot find type `Ref` in this scope
  --> src/fourth.rs:63:40
   |
63 |     pub fn peek_front(&self) -> Option<Ref<T>> {
   |                                        ^^^ not found in this scope
help: possible candidates are found in other modules, you can import them into scope
   |
1  | use core::cell::Ref;
   |
1  | use std::cell::Ref;
   |

ぶっは．importしなきゃいけませんね．

use std::cell::{Ref, RefCell};

> cargo build

error[E0308]: mismatched types
  --> src/fourth.rs:64:9
   |
64 | /         self.head.as_ref().map(|node| {
65 | |             node.borrow()
66 | |         })
   | |__________^ expected type parameter, found struct `fourth::Node`
   |
   = note: expected type `std::option::Option<std::cell::Ref<'_, T>>`
              found type `std::option::Option<std::cell::Ref<'_, fourth::Node<T>>>`

うーん...確かに．Ref<Node<T>>を返していますが欲しいのはRef<T>です．全てを諦めて Ref<Node<T>>を返すというのも手ですし，&Tにだけアクセスできるような型でRef<Node<T>> をラップし事態を更に複雑化させるという手もあります．

どちらもまあまあダサいですね．

かわりにさらなる深淵を覗きましょう．楽しもうじゃないですか．楽しみの種はこの やべーやつです：

map<U, F>(orig: Ref<'b, T>, f: F) -> Ref<'b, U>
    where F: FnOnce(&T) -> &U,
          U: ?Sized

Make a new Ref for a component of the borrowed data.

そう，Option同様Refもmapできるのです．

どこかの誰かはモナドとか何とか言って興奮しているかと思いますが，私にはどうでもいいことです．あとこのメソッドはNothingのケースを持たないので厳密にはモナドではないと思います．話がそれました．

このメソッドはイカすというその事実だけが重要です．私にはこいつが必要です．

pub fn peek_front(&self) -> Option<Ref<T>> {
    self.head.as_ref().map(|node| {
        Ref::map(node.borrow(), |node| &node.elem)
    })
}

> cargo build

やっっっった．

ちゃんと動いていることを，スタックのときに実装したテストを修正して確認しましょう．Ref 同士の比較はできないのでちょっと修正が必要です．

#[test]
fn peek() {
    let mut list = List::new();
    assert!(list.peek_front().is_none());
    list.push_front(1); list.push_front(2); list.push_front(3);

    assert_eq!(&*list.peek_front().unwrap(), &3);
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 10 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::basics ... ok
test fourth::test::peek ... ok
test second::test::iter_mut ... ok
test second::test::into_iter ... ok
test third::test::basics ... ok
test second::test::peek ... ok
test second::test::iter ... ok
test third::test::iter ... ok

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

やりました！

対称的な操作

それじゃあ対称なメソッドをやっつけてしまいましょう．

すべきことは文字列置換だけです．

tail <-> head
next <-> prev
front -> back

あ，あとpeekの_mutバージョンもいりますね．

pub fn push_back(&mut self, elem: T) {
    let new_tail = Node::new(elem);
    match self.tail.take() {
        Some(old_tail) => {
            old_tail.borrow_mut().next = Some(new_tail.clone());
            new_tail.borrow_mut().prev = Some(old_tail);
            self.tail = Some(new_tail);
        }
        None => {
            self.head = Some(new_tail.clone());
            self.tail = Some(new_tail);
        }
    }
}

pub fn pop_back(&mut self) -> Option<T> {
    self.tail.take().map(|old_tail| {
        match old_tail.borrow_mut().prev.take() {
            Some(new_tail) => {
                new_tail.borrow_mut().next.take();
                self.tail = Some(new_tail);
            }
            None => {
                self.head.take();
            }
        }
        Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
    })
}

pub fn peek_back(&self) -> Option<Ref<T>> {
    self.tail.as_ref().map(|node| {
        Ref::map(node.borrow(), |node| &node.elem)
    })
}

pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
    self.tail.as_ref().map(|node| {
        RefMut::map(node.borrow_mut(), |node| &mut node.elem)
    })
}

pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
    self.head.as_ref().map(|node| {
        RefMut::map(node.borrow_mut(), |node| &mut node.elem)
    })
}

そしてめっちゃテストを書きます：

#[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);

    // ---- 逆順 -----

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

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

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

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

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

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

#[test]
fn peek() {
    let mut list = List::new();
    assert!(list.peek_front().is_none());
    assert!(list.peek_back().is_none());
    assert!(list.peek_front_mut().is_none());
    assert!(list.peek_back_mut().is_none());

    list.push_front(1); list.push_front(2); list.push_front(3);

    assert_eq!(&*list.peek_front().unwrap(), &3);
    assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
    assert_eq!(&*list.peek_back().unwrap(), &1);
    assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
}

テスト漏れはあるでしょうか？多分あります．メソッド同士の組み合わせ空間はめちゃくちゃ大きいです．でも少なくとも私達のコードは明らかに間違ってる わけではないです．

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 10 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::basics ... ok
test fourth::test::peek ... ok
test second::test::iter ... ok
test third::test::iter ... ok
test second::test::into_iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok

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

いいですね．コピペこそが最高のプログラミングです．

イテレート

この悪い子をイテレートしていきましょう．

IntoIter

いつものようにIntoIterが一番楽です．スタックでラップしてpopを呼びましょう：

pub struct IntoIter<T>(List<T>);

impl<T> List<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        self.0.pop_front()
    }
}

でもちょっとおもしろいことが起こっています．前はリストをイテレートする「自然な」方向が一意に決まっていましたが，両端キューには2つあります．もし逆方向にイテレートしたい人がいたらどうしたらいいでしょうか？

じつはRustにはそのためのDoubleEndedIteratorトレイトがあります．DoubleEndedIterator はIteratorを継承し（これは全てのDoubleEndedIteratorがIteratorsであることを意味します）， next_backというメソッドの実装を必要とします．このメソッドはnextと全く同じシグネチャを持ちますが，逆側の要素を返すようになっています．DoubleEndedIteratorを使えば簡単にイテレータを両端キューにして，イテレータが空になるまで前からでも後ろからでも要素を取り出すことができます．

next_backはDoubleEndedIteratorを使う人にとってそれほど重要なメソッドではありません．それより，イテレータを逆順にして返すrevメソッドがあることのほうが重要です．このメソッドのやっていることはとてもシンプルです．逆順になったイテレータで呼ばれるnextは代わりにnext_backが呼ばれるというだけです．

なんにせよ私達のリストはすでに両端キューなので，これの実装は超簡単です：

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.0.pop_back()
    }
}

そしてテストします：

#[test]
fn into_iter() {
    let mut list = List::new();
    list.push_front(1); list.push_front(2); list.push_front(3);

    let mut iter = list.into_iter();
    assert_eq!(iter.next(), Some(3));
    assert_eq!(iter.next_back(), Some(1));
    assert_eq!(iter.next(), Some(2));
    assert_eq!(iter.next_back(), None);
    assert_eq!(iter.next(), None);
}

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 11 tests
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test fourth::test::into_iter ... ok
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test third::test::iter ... ok
test third::test::basics ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok

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

イエーイ．

Iter

Iterはもうすこし厳しいです．またあの恐ろしいRefと向き合わなくてはいけません！ Refのせいでこれまでのように&Nodeを保持するわけにはいきません．代わりにRef<Node> を保持します：

pub struct Iter<'a, T>(Option<Ref<'a, Node<T>>>);

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter(self.head.as_ref().map(|head| head.borrow()))
    }
}

> cargo build

ここまでは順調です．nextの実装はちょっと難しいですが，これまでのIterMutの実装に RefCellの狂気を添えた感じで行けると思います：

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = Ref<'a, T>;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.take().map(|node_ref| {
            self.0 = node_ref.next.as_ref().map(|head| head.borrow());
            Ref::map(node_ref, |node| &node.elem)
        })
    }
}

cargo build

error[E0521]: borrowed data escapes outside of closure
   --> src/fourth.rs:155:13
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- `self` is declared here, outside of the closure body
154 |         self.0.take().map(|node_ref| {
155 |             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
    |             ^^^^^^   -------- borrow is only valid in the closure body
    |             |
    |             reference to `node_ref` escapes the closure body here

error[E0505]: cannot move out of `node_ref` because it is borrowed
   --> src/fourth.rs:156:22
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- lifetime `'1` appears in the type of `self`
154 |         self.0.take().map(|node_ref| {
155 |             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
    |             ------   -------- borrow of `node_ref` occurs here
    |             |
    |             assignment requires that `node_ref` is borrowed for `'1`
156 |             Ref::map(node_ref, |node| &node.elem)
    |                      ^^^^^^^^ move out of `node_ref` occurs here

クソが．

node_refのライフタイムが十分ではないようです．普通の参照と違って，Refをこんなふうに分割することはできないようです．head.borrow()でとったRefはnode_refが生きている間しか生きられませんが，私達はRef::mapでnode_refを捨てています．

偶然にも私がこれを書いているとき，私達が使いたい関数が2日前に安定化されました．つまりあと数ヶ月でstableリリースに含まれることになります．なので最新のnightlyビルドを使っていきましょう¹：

pub fn map_split<U, V, F>(orig: Ref<'b, T>, f: F) -> (Ref<'b, U>, Ref<'b, V>) where
    F: FnOnce(&T) -> (&U, &V),
    U: ?Sized,
    V: ?Sized,

ウーッ．やってみましょう...

fn next(&mut self) -> Option<Self::Item> {
    self.0.take().map(|node_ref| {
        let (next, elem) = Ref::map_split(node_ref, |node| {
            (&node.next, &node.elem)
        });

        self.0 = next.as_ref().map(|head| head.borrow());

        elem
    })
}

cargo build
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0521]: borrowed data escapes outside of closure
   --> src/fourth.rs:159:13
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- `self` is declared here, outside of the closure body
...
159 |             self.0 = next.as_ref().map(|head| head.borrow());
    |             ^^^^^^   ---- borrow is only valid in the closure body
    |             |
    |             reference to `next` escapes the closure body here

えー．ライフタイムのつじつまを合わせるためにもう1回Ref::Mapする必要がありますが，私達が欲しいのはOption<Ref>であってRef::Mapから返るRefではありません．しかし OptionをmapするにはRefの中を見る必要があります...

（しばらく虚空を見つめる）

??????

fn next(&mut self) -> Option<Self::Item> {
    self.0.take().map(|node_ref| {
        let (next, elem) = Ref::map_split(node_ref, |node| {
            (&node.next, &node.elem)
        });

        self.0 = if next.is_some() {
            Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
        } else {
            None
        };

        elem
    })
}

error[E0308]: mismatched types
   --> src/fourth.rs:162:22
    |
162 |                 Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
    |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `fourth::Node`, found struct `std::cell::RefCell`
    |
    = note: expected type `std::cell::Ref<'_, fourth::Node<_>>`
               found type `std::cell::Ref<'_, std::cell::RefCell<fourth::Node<_>>>`

あーそうですね．RefCellが二重になっています．リストを深く探索すればするほどRefCellがネストしていってしまいます．複数の参照を一気にカウントしてくれるRefみたいなものが必要です．リストの要素を解放したとき，それまでネストしてきた参照カウントを一気に1つづつデクリメントしてくれるような何か.............

もうなにか手が残っているとは思えません．終わりです．RefCellから離れて考えてみましょう．

Rcを使うというのはどうでしょう．参照を保持する必要なんかありませんよね？単にRcを Cloneして所有権を管理させるのではダメでしょうか？


# #![allow(unused_variables)]
#fn main() {
pub struct Iter<T>(Option<Rc<Node<T>>>);

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter(self.head.as_ref().map(|head| head.clone()))
    }
}

impl<T> Iterator for Iter<T> {
    type Item =
#}

えっと...待ってください，ここの型は何でしょう？&T？Ref<T>？

だめです，どっちもうまくいきません...私達のIterはもはやライフタイムを持っていないのです！ &TもRef<T>もnextする際にライフタイムが必要です．でもRcから出そうとするものは Iteratorを借用します...ウッ，頭が...痛い...ぐあああああああああ

多分Rcを...mapして...Rc<T>にする？本当か？Rcのドキュメントを見る限りそういうことをするメソッドはなさそうです．実際これをできるようにするクレートを作った人がいます．

でも待ってください．かりにそれをやったとしてもさらに大きな問題に直面します．イテレータ破壊という恐ろしい現象です．これまで私達はイテレータ破壊に対して完全に無敵でした．なぜならIterはリストを借用するだけなので，それに変更を加えないからです．しかし，もし IterがRcを返すならそれは借用に留まりません！これによってリストの利用者はポインタを持ち続ける限りpushやpopを呼べてしまえます！

おお神よ！いったいどうすればいいのですか！？

えっと，実はpushは無問題です．私達の見えている範囲よりリストの全体が大きくなるだけです．大したことありません．

でもpopは話が別です．もし私達の知らないところでpopが行われてもまだ大丈夫です．もともとそのノードは私達の知らない所にあるので何も起こりません．しかし，もし私達に見えているノードがpopされれば...全てがぶっ壊れます！具体的にはtry_unwrapの結果をunwrapしようとしたときにpanicするでしょう．

これは実際かなりイケてます．リストを指すポインタを持つイテレータをいくらでも生成できて，他が指しているノードを削除しようとしない限りともかく正常に動作するのですから．しかもそのような削除が発生したときにも，ダングリングポインタを生むこともなくしっかりパニックしてくれるのです！

でもRcのマップをするためにイテレータ破壊に対処しなくてはいけないのはなんというか... よくありません．私達はRc<RefCell>に完膚無きまでに絶望させられました．面白いことにいま私達は永続スタックのときの逆を体験しています．永続スタックのとき，私達はデータの所有権を得ようと苦闘しましたが参照はほぼいつでも得ることができました．今回は所有権を得るのは問題ありませんでしたが参照を貸し出すのに苦労しています．

とはいえ，公平に言って，私達が苦労している理由は実装の詳細を隠蔽し洗練されたAPIを提供しようとしているからと言えるでしょう．もしNodeをどこにでも渡すようにすればすべてうまくやれたでしょう．

そうすればランタイムに同時に同じ要素が変更されないことを保証する並列IterMutすら実装することができます！

本当にこの設計は内部のデータ構造を隠蔽するAPIに向いてませんね．内部可変性は安全な アプリケーションを書くには適していますが，安全なライブラリを書くためにはそれほど有用ではありません．

ともかくIterとIterMutは諦めます．実装できることはできますが，やりたくありません．

訳注：これは原文が書かれた当時の話で，当該関数はとっくにstableに入っています．したがってこのためにnightlyを使う必要はありません

最終コード

はい．これがRustで100%安全な双方向リストを実装するということです．悪夢のような体験でしたし，できたリストは実装の詳細を晒している上いくつか基礎的な機能をがありません．

でも，確かにここに存在します．

あ，それとRcとRefCellで大量の「不要な」ランタイムチェックを行っています．不要なをカッコに入れたのは，実際には本当に安全であることを保証するために必要だからです．実際いくつかのところでは必要でした．双方向リストはエイリアスと所有権がおそろしく複雑に絡み合ったなにかでした！

でも私達はある程度やり遂げました．特に内部のデータ構造を晒すことを気にしないなら上出来といえるでしょう．

ここからは，コインの裏側を見ていきたいと思います．不安全な実装によってあらゆるものの制御を再び取り戻すのです．


# #![allow(unused_variables)]
#fn main() {
use std::rc::Rc;
use std::cell::{Ref, RefMut, RefCell};

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

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

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


impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

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

    pub fn push_front(&mut self, elem: T) {
        let new_head = Node::new(elem);
        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(new_head.clone());
                new_head.borrow_mut().next = Some(old_head);
                self.head = Some(new_head);
            }
            None => {
                self.tail = Some(new_head.clone());
                self.head = Some(new_head);
            }
        }
    }

    pub fn push_back(&mut self, elem: T) {
        let new_tail = Node::new(elem);
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_tail.clone());
                new_tail.borrow_mut().prev = Some(old_tail);
                self.tail = Some(new_tail);
            }
            None => {
                self.head = Some(new_tail.clone());
                self.tail = Some(new_tail);
            }
        }
    }

    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            match old_tail.borrow_mut().prev.take() {
                Some(new_tail) => {
                    new_tail.borrow_mut().next.take();
                    self.tail = Some(new_tail);
                }
                None => {
                    self.head.take();
                }
            }
            Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
        })
    }

    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();
                }
            }
            Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
        })
    }

    pub fn peek_front(&self) -> Option<Ref<T>> {
        self.head.as_ref().map(|node| {
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }

    pub fn peek_back(&self) -> Option<Ref<T>> {
        self.tail.as_ref().map(|node| {
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }

    pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
        self.tail.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |node| &mut node.elem)
        })
    }

    pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
        self.head.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |node| &mut node.elem)
        })
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

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

pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.0.pop_front()
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.0.pop_back()
    }
}

#[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);

        // ---- 逆順 -----

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

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

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

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

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

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

    #[test]
    fn peek() {
        let mut list = List::new();
        assert!(list.peek_front().is_none());
        assert!(list.peek_back().is_none());
        assert!(list.peek_front_mut().is_none());
        assert!(list.peek_back_mut().is_none());

        list.push_front(1); list.push_front(2); list.push_front(3);

        assert_eq!(&*list.peek_front().unwrap(), &3);
        assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
        assert_eq!(&*list.peek_back().unwrap(), &1);
        assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
    }

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push_front(1); list.push_front(2); list.push_front(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next_back(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }
}
#}

不安全な片方向キュー

えー，前回の参照カウントと内部可変性をつかったリストは少し私達の手に余りました．もちろんRustではああいったことを一般的に想定しているわけではないですよね？答えはYESでありNOです．RcとRefCellは簡単なものを扱う場合は素晴らしい型ですがたまに扱いにくいことがあります．何が起こってるか隠蔽したい場合には特に．もっといい方法があるはずです！

この章では片方向リストを再び扱い，その実装を通してちょっとだけ生のポインタ と不安全なRustに触れます．

fifth.rsという新しいファイルを作りましょう：

// in lib.rs

pub mod first;
pub mod second;
pub mod third;
pub mod fourth;
pub mod fifth;

連結リストの形を取る場合キューはほとんどスタックを拡張したものなので，ほとんどのコードをsecond.rsを元にして書くことができます．でも，設計などの基本的な問題があるので何もない状態から始めたいと思います．

設計

で，片方向キューとは何でしょうか？片方向スタックのとき，私達はリストの最後に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（色欲）とかかっている

Unsafe Rust

これは深刻で，大きく，複雑で，危険な話題です．あまりに深刻なので私はもう一冊これについての本を書きました．

とにもかくにも，どんな言語も他の言語を呼び出した途端不安全になります．呼び出したCが適当に悪いことをするのを許さなくてはなりませんから．Javaも，Pythonも，Rubyも，Haskellも... FFI（Foreign Function Interface）の前ではあらゆる言語が不安全になります．

Rustはこの事実を受け止めるために自分自身を2つの言語に分けました．安全なRustと，不安全な Rustです．ここまで私達は安全なRustだけを扱ってきました．安全なRustは100%完全に安全です... 不安全なRustにFFIできることを除いて．

不安全なRustは安全なRustの機能をすべて持っており，それに加えていくつか追加の，C言語に取り付いている恐ろしい未定義動作を引き起こすような，野蛮かつ不安全な操作が行なえます．

繰り返しになりますが，この話題はたくさんの興味深い内容を含みます．私は本当にこの話題に深入りしたくありません（実はしたいです．というかしました．こちらを読んでください）．でも大丈夫です．私達のリストを実装する上では深入りする必要はありません．

主に使う不安全アイテムは生ポインタです．生ポインタとは，基本的にはCのポインタです．エイリアスルールを持たず，ライフタイムを持たず，nullポインタにもダングリングポインタにもなり得る，未初期化のメモリ領域を指すこともでき，整数型と互換性があり，キャストして別の型を指すようにもできます．可変性がほしい？キャストしましょう．あまりにもなんでもできるため，あまりにもよくぶっ壊れます．

生ポインタは悪いやつであり，正直関わらないほうが幸せな人生を送れます．しかし不幸にも私達はおぞましい連結リストを書きたいのです．つまり私達は不安全な生ポインタを使わなくてはいけません．

生ポインタには二種類あります．*const Tと*mut Tです．これはそれぞれCでいうところの const T*とT*ですが，実はCでどう扱われているかはそれほど重要ではありません． *const Tは参照外しによって&Tにしか変換できませんが，これは変数の可変性と同じ感じで誤った使い方を防ぐためです．要はたいていの場合，まず*constを*mutにキャストする必要があるということです．たとえポインタの指す値を変える権限がなくてもよくないことが起こりうるのです．

まあなんにせよ書いていくうちに慣れてくるでしょう．とりあえず*mut T == &unchecked mut T と考えてください！

基本

はい，では基本に立ち返りましょう．どうやってリストを初期化したらよいでしょうか？

前回はこうしました：

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

しかしもはやtailにOptionを使っていません：

> cargo build

error[E0308]: mismatched types
  --> src/fifth.rs:15:34
   |
15 |         List { head: None, tail: None }
   |                                  ^^^^ expected *-ptr, found enum `std::option::Option`
   |
   = note: expected type `*mut fifth::Node<T>`
              found type `std::option::Option<_>`

Optionを使うこともできるにはできますが，Boxと違って*mutはnullになり得ます．つまりヌルポインタ最適化の恩恵を受けられないのです．なので，Optionを使う代わりにnullで Noneを表すことにしましょう．

ではヌルポインタを代入するにはどうすればいいでしょうか？いくつかやり方はありますが，私はstd::ptr::null_mut()を使うのが好きです．0 as *mut _を使う手もありますがちょっと汚く見えます．

use std::ptr;

// defns...

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

cargo build

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

warning: field is never used: `tail`
 --> src/fifth.rs:5:5
  |
5 |     tail: *mut Node<T>,
  |     ^^^^^^^^^^^^^^^^^^

warning: field is never used: `elem`
  --> src/fifth.rs:11:5
   |
11 |     elem: T,
   |     ^^^^^^^

warning: field is never used: `head`
  --> src/fifth.rs:12:5
   |
12 |     head: Link<T>,
   |     ^^^^^^^^^^^^^

黙ってろコンパイラ，今から使うから．

はい，ではもう一度pushを実装していきましょう．今回は挿入したあとにOption<&mut Node<T>> を取るのではなく，Boxの中にある*mut Node<T>をそのまま取ります．これがうまくいくのは Boxを移動しても中身のメモリアドレスは変わらないからですね．もちろんこれは不安全な操作です．もしBoxをdropしてしまったら私達は解放されたメモリを指すポインタを持つことになります．

どうすれば普通のポインタから生ポインタを作れるのでしょうか？Coercionです！もし変数が生ポインタとして宣言されていれば，普通の参照は生ポインタになることを強制（Coerce）されます：

let raw_tail: *mut _ = &mut *new_tail;

これで必要なものは揃いました．前回の参照を使ったバージョンとだいたい同じ感じに書けます：

pub fn push(&mut self, elem: T) {
    let mut new_tail = Box::new(Node {
        elem: elem,
        next: None,
    });

    let raw_tail: *mut _ = &mut *new_tail;

    // .is_nullはnullかどうかをチェックします
    // Noneかどうかをチェックするのと同じ役割です
    if !self.tail.is_null() {
        // もしtailがすでにあれば新しいtailを入れる
        self.tail.next = Some(new_tail);
    } else {
        // そうでなければheadに入れる
        self.head = Some(new_tail);
    }

    self.tail = raw_tail;
}

> cargo build

error[E0609]: no field `next` on type `*mut fifth::Node<T>`
  --> src/fifth.rs:31:23
   |
31 |             self.tail.next = Some(new_tail);
   |             ----------^^^^
   |             |
   |             help: `self.tail` is a raw pointer; try dereferencing it: `(*self.tail).next`

は？Nodeのポインタを持ってるのにnextをとれないの？

Rustは生ポインタを使い出すとちょっと嫌なヤツになります．生ポインタの中身にアクセスするとき，不安全な操作だと言って手動で参照外しをすることを強制してくるのです．ではそのようにやってみましょう：

*self.tail.next = Some(new_tail);

> cargo build

error[E0609]: no field `next` on type `*mut fifth::Node<T>`
  --> src/fifth.rs:31:23
   |
31 |             *self.tail.next = Some(new_tail);
   |             -----------^^^^
   |             |
   |             help: `self.tail` is a raw pointer; try dereferencing it: `(*self.tail).next`

うううううオペレータの優先順を考えなくてはいけませんでした．

(*self.tail).next = Some(new_tail);

> cargo build

error[E0133]: dereference of raw pointer is unsafe and requires unsafe function or block
  --> src/fifth.rs:31:13
   |
31 |             (*self.tail).next = Some(new_tail);
   |             ^^^^^^^^^^^^^^^^^ dereference of raw pointer
   |
   = note: raw pointers may be NULL, dangling or unaligned; they can violate aliasing rules and cause data races: all of these are undefined behavior

こんな難しいわけないだろ．

不安全なRustは安全なRustにとってFFIみたいなものだと言ったことを覚えていますか？えっと，私達はコンパイラにどこでFFIしているか明示する必要があります．方法は二つです．一つ目は関数全体を不安全にすることで，そうすると関数は不安全なRustに属し，unsafeなところからしか呼べなくなります．これはあまり良くありません．私達はリストを使う分には安全にしたいのですから．二つ目は関数内にunsafeブロックを書き，FFIの境界を切ることです．この場合関数自体は安全なままです．後者でいってみましょう：

pub fn push(&mut self, elem: T) {
    let mut new_tail = Box::new(Node {
        elem: elem,
        next: None,
    });

    let raw_tail: *mut _ = &mut *new_tail;

    // .is_nullはnullかどうかをチェックします
    // Noneかどうかをチェックするのと同じ役割です
    if !self.tail.is_null() {
        // もしtailがすでにあれば新しいtailを入れる
        unsafe {
            (*self.tail).next = Some(new_tail);
        }
    } else {
        // そうでなければheadに入れる
        self.head = Some(new_tail);
    }

    self.tail = raw_tail;
}

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

イエーイ！

他のいろんなところでも生ポインタを扱っているのにここしかunsafeにしなくていいのはちょっとおもしろいですね．何が起こっているのでしょうか？

unsafeのことになるとRustはかなり仕切りたがり屋であるようです．私達は安全なRustのほうが自信があるので当然できるだけそっちを使いたいわけですが，Rustはそれを達成するために不安全な部分が最小になるような境界を注意深く引いてくれるのです．私達が生ポインタを使っている他の部分はポインタに代入しているか，nullかどうかチェックしているだけであることに注目してください．

もし参照を外さないのであれば，生ポインタは完全に安全です．ただ整数を読んだり書いたりしているだけです！生ポインタで問題が起きるのは参照を外すときだけなので，Rustはその操作だけを不安全だと言い，ほかは安全な操作として扱うのです．

超．衒学的．でも技術的には正しいですね．

しかしこれは興味深い問題を生みます．もしunsafeブロックを区切っても，その中の状態はunsafeブロックの外部に依存します．もしかしたら関数の外にすら依存するかもしれません！

わたしはこれをunsafe汚染と呼んでいます．unsafeを使うや否やモジュール全体が不安全に汚染されてしまうのです．コードの不変性が不安全さを支えて持ちこたえられるためには，全てが正しく実装されている必要があります．

この汚染はプライバシーによって食い止められます．私達のモジュール外からはstructのフィールドは操作できないので私達以外の誰もそれらの内部状態を好き勝手することはできません．私達のAPIをどんなふうに組み合わせも安全であり，かつ外部から操作できる範囲がちゃんと正しく決められている限り，私達のコードは安全です！そして本当にこれはFFIと何も変わりません．PythonのライブラリがCを呼び出していようと，安全なインターフェースを提供している限り誰も気にしません．

ともかくpopにいきましょう．参照をつかうバージョンとほぼ一緒です：

pub fn pop(&mut self) -> Option<T> {
    self.head.take().map(|head| {
        let head = *head;
        self.head = head.next;

        if self.head.is_none() {
            self.tail = ptr::null_mut();
        }

        head.elem
    })
}

またしても安全とはステートフルであることを示すケースに遭遇しました．もしこの関数で tailのポインタをnullにするのを忘れても，すぐにはなんの問題も現れません．しかしそのあとpushするとダングリングポインタになっているtailに書き込んでしまいます！

テストしていきましょう：

#[cfg(test)]
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);

        // リストを出し切ってもポインタが破壊されてないことを確認
        list.push(6);
        list.push(7);

        // 普通に要素を削除してみる
        assert_eq!(list.pop(), Some(6));
        assert_eq!(list.pop(), Some(7));
        assert_eq!(list.pop(), None);
    }
}

これはスタックのテストそのままですが，popが逆順に出てくることを期待している点が違います．また，最後にpopが空振りしたときもポインタが壊れていないか確認するケースを追加しています．

cargo test

     Running target/debug/lists-5c71138492ad4b4a

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

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

大金星！

その他のゴミ

pushとpopが書けたので後はスタックのときと完全に同じです．リストの長さを変える操作だけが末尾ポインタのことを気にかければよいのです．

というわけで二番目のリストから全てをパクってきましょう（テストでpopが逆順に出てくることを期待するよう変えることを忘れないでください）：

// ...

pub struct IntoIter<T>(List<T>);

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}




impl<T> List<T> {
    // ...

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| {
            &node.elem
        })
    }

    pub fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| {
            &mut node.elem
        })
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut { next: self.head.as_mut().map(|node| &mut **node) }
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}





#[cfg(test)]
mod test {
    // ...

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter_mut() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter_mut();
        assert_eq!(iter.next(), Some(&mut 1));
        assert_eq!(iter.next(), Some(&mut 2));
        assert_eq!(iter.next(), Some(&mut 3));
        assert_eq!(iter.next(), None);
    }
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

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

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

コピペプログラミングに感謝を．

一瞬IntoIterが動かないんじゃないかと思いましたがいい感じに逆順にpopできていましたね！

最終コード

さて，不安全にほんのちょびっと触っただけで安全なキューから線形時間の性能向上が得られました．しかもほとんどすべてのロジックを安全なスタックから再利用することができています！

そしてRcとかRefCellとかの狂ったものを書かずに済んでいます．


# #![allow(unused_variables)]
#fn main() {
use std::ptr;

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

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: ptr::null_mut() }
    }

    pub fn push(&mut self, elem: T) {
        let mut new_tail = Box::new(Node {
            elem: elem,
            next: None,
        });

        let raw_tail: *mut _ = &mut *new_tail;

        if !self.tail.is_null() {
            unsafe {
                (*self.tail).next = Some(new_tail);
            }
        } else {
            self.head = Some(new_tail);
        }

        self.tail = raw_tail;
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|head| {
            let head = *head;
            self.head = head.next;

            if self.head.is_none() {
                self.tail = ptr::null_mut();
            }

            head.elem
        })
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| {
            &node.elem
        })
    }

    pub fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| {
            &mut node.elem
        })
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut { next: self.head.as_mut().map(|node| &mut **node) }
    }
}

pub struct IntoIter<T>(List<T>);

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|node| {
            self.next = node.next.as_mut().map(|node| &mut **node);
            &mut node.elem
        })
    }
}

#[cfg(test)]
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);

        // リストを出し切ってもポインタが破壊されてないことを確認
        list.push(6);
        list.push(7);

        // 普通に要素を削除してみる
        assert_eq!(list.pop(), Some(6));
        assert_eq!(list.pop(), Some(7));
        assert_eq!(list.pop(), None);
    }

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter_mut() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter_mut();
        assert_eq!(iter.next(), Some(&mut 1));
        assert_eq!(iter.next(), Some(&mut 2));
        assert_eq!(iter.next(), Some(&mut 3));
        assert_eq!(iter.next(), None);
    }
}
#}

まあまあなメモリ不安全双方向両端キュー

いや，これを書き忘れてました！これはそんなにためになるものではありません．

もし本当にこれを実装したければ裏本とstd::collections::LinkedListのソースを読んでください！

アホなリストたち

よし，これで終わりです．全てのリストを実装しました．

ワハハハハハハ

まだです

リストはいくらでもあります．

この章はほかの馬鹿げたリストと，それらがRustでどう扱われるかについての更新中¹のドキュメントです．

二重片方向リスト
TODO: BList?
TODO: SkipList?
TODO: std::channel? -- That's like another whole chapter. Or 3.

訳注：途絶えてます

二重片方向リスト

複雑な所有権を持っていたため双方向リストでは苦戦しました．というのも，どのノードも他のノードの所有権をはっきりと持っていたわけではなかったからです．しかし私達は連結リストに対する先入観があったために苦戦していたとも言えます．つまり，すべてのリンクが同じ方向に行くことを想定していたのです．

そうではなく，リストを半分に分割して，片方を右回り，もう片方を左回りのリストにすることもできます：

// lib.rs
// ...
pub mod silly1;     // NEW!

// silly1.rs
use second::List as Stack;

struct List<T> {
    left: Stack<T>,
    right: Stack<T>,
}

これでただのスタックではなく汎用リストになりました．好きな方のスタックにpush することでどちらの方向にもリストを伸ばすことができます．さらに片方の端からもう片方の端にNodeを移すことでリストを渡ることもできます．不要なメモリ割り当てを避けるために，安全なスタックのソースをコピーして実装の詳細を得ます：

pub struct Stack<T> {
    head: Link<T>,
}

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

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

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

    pub fn push(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            let node = *node;
            self.head = node.next;
            node.elem
        })
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| {
            &node.elem
        })
    }

    pub fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| {
            &mut node.elem
        })
    }
}

impl<T> Drop for Stack<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

そしてpushとpopをちょっと作り変えます：

pub fn push(&mut self, elem: T) {
    let new_node = Box::new(Node {
        elem: elem,
        next: None,
    });

    self.push_node(new_node);
}

fn push_node(&mut self, mut node: Box<Node<T>>) {
    node.next = self.head.take();
    self.head = Some(node);
}

pub fn pop(&mut self) -> Option<T> {
    self.pop_node().map(|node| {
        node.elem
    })
}

fn pop_node(&mut self) -> Option<Box<Node<T>>> {
    self.head.take().map(|mut node| {
        self.head = node.next.take();
        node
    })
}

これでListのコンストラクタを書けます：

pub struct List<T> {
    left: Stack<T>,
    right: Stack<T>,
}

impl<T> List<T> {
    fn new() -> Self {
        List { left: Stack::new(), right: Stack::new() }
    }
}

いつもの：

pub fn push_left(&mut self, elem: T) { self.left.push(elem) }
pub fn push_right(&mut self, elem: T) { self.right.push(elem) }
pub fn pop_left(&mut self) -> Option<T> { self.left.pop() }
pub fn pop_right(&mut self) -> Option<T> { self.right.pop() }
pub fn peek_left(&self) -> Option<&T> { self.left.peek() }
pub fn peek_right(&self) -> Option<&T> { self.right.peek() }
pub fn peek_left_mut(&mut self) -> Option<&mut T> { self.left.peek_mut() }
pub fn peek_right_mut(&mut self) -> Option<&mut T> { self.right.peek_mut() }

一番面白いのはリストを渡ることができることです！

pub fn go_left(&mut self) -> bool {
    self.left.pop_node().map(|node| {
        self.right.push_node(node);
    }).is_some()
}

pub fn go_right(&mut self) -> bool {
    self.right.pop_node().map(|node| {
        self.left.push_node(node);
    }).is_some()
}

本当に移動ができたかどうかを示すためにbooleanを返しています．テストしてみましょう：

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

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

        list.push_left(0);                      // [0,_]
        list.push_right(1);                     // [0, _, 1]
        assert_eq!(list.peek_left(), Some(&0));
        assert_eq!(list.peek_right(), Some(&1));

        list.push_left(2);                      // [0, 2, _, 1]
        list.push_left(3);                      // [0, 2, 3, _, 1]
        list.push_right(4);                     // [0, 2, 3, _, 4, 1]

        while list.go_left() {}                 // [_, 0, 2, 3, 4, 1]

        assert_eq!(list.pop_left(), None);
        assert_eq!(list.pop_right(), Some(0));  // [_, 2, 3, 4, 1]
        assert_eq!(list.pop_right(), Some(2));  // [_, 3, 4, 1]

        list.push_left(5);                      // [5, _, 3, 4, 1]
        assert_eq!(list.pop_right(), Some(3));  // [5, _, 4, 1]
        assert_eq!(list.pop_left(), Some(5));   // [_, 4, 1]
        assert_eq!(list.pop_right(), Some(4));  // [_, 1]
        assert_eq!(list.pop_right(), Some(1));  // [_]

        assert_eq!(list.pop_right(), None);
        assert_eq!(list.pop_left(), None);

    }
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 16 tests
test fifth::test::into_iter ... ok
test fifth::test::basics ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fourth::test::into_iter ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test second::test::peek ... ok
test silly1::test::walk_aboot ... ok

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

これは指差しデータ構造の極端な例です．指差しデータ構造は，データのどこかを指で指し続けることで指からの距離に比例した時間で操作を行えるようにするデータ構造です．

指の周りのノードに対しては高速で操作が行なえますが，指から離れたところに対してはリストを渡っていかなくてはいけません．要素を片側からもう片側に移すことで永続的に渡る事もできますし，&mutを使って一時的に移動することもできます．しかし&mutはリストを逆にたどることはできないのに対し，指を使えばそれが出来るのです！