Iter
さて、Iter の実装を試してみましょう。今回は、List が欲しい機能をすべて提供してくれることには頼れません。自分たちで作る必要があります。必要な基本的なロジックは、次に yield したい現在のノードへのポインタを保持することです。そのノードは存在しない可能性があるため（リストが空である、またはすでに反復が完了している場合）、その参照は Option にしたいです。要素を yield したら、現在のノードの 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
このエラーは、型からライフタイムが欠落していることを示します。関数シグネチャ内でのエラーである場合、ライフタイム省略規則（以下を参照）に従っていないことが原因かもしれません。
このエラーに遭遇する場所の簡単な例をいくつか示します。
struct Foo { x: &bool } // エラー
struct Foo<'a> { x: &'a bool } // 正しい
enum Bar { A(u8), B(&bool), } // エラー
enum Bar<'a> { A(u8), B(&'a bool), } // 正しい
type MyStr = &str; // エラー
type MyStr<'a> = &'a str; //正しい
...
これは、ええと……あまり明確にはなりませんでした（これらのドキュメントは、私たちが現時点よりも Rust をよく理解している前提になっています）。しかし、構造体にこれらの 'a というものを追加すべきように見えますね。試してみましょう。
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 のシステムでは、すべての借用チェックを各関数本体の中で独立して行うことができ、すべてのエラーはかなり局所的であるはずです（あるいは型のシグネチャが間違っています）。
しかし、これまで関数シグネチャに参照を書いたことがあり、それで問題ありませんでした！これは、非常によくある特定のケースでは、Rust が自動的にライフタイムを選んでくれるからです。これがライフタイム省略です。
具体的には次のようになります。
// 入力の参照は 1 つだけなので、出力はその入力から派生している必要がある
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 は何を 意味する のでしょうか？実用上の意味としては、入力は少なくとも出力と同じ長さだけ生存していなければならない、ということだけです。つまり、出力を長い間保持し続けるなら、入力が有効でなければならないリージョンも広がります。出力の使用をやめると、コンパイラは入力も無効になってよいことを認識します。
この仕組みが整っていれば、Rust は解放後に何も使用されないこと、そして未解放の参照が存在している間は何もミューテートされないことを保証できます。単にすべての制約がうまく成り立つようにしているだけです！
よし。では。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/ADesires/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/ADesires/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 によって、取り除く必要のある間接参照の層がもう 1 つ追加されました。
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_deref() }
}
}
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_deref();
&node.elem
})
}
}cargo build
🎉 🎉 🎉
as_deref と as_deref_mut 関数は、Rust 1.40 時点で安定化されています。それ以前は、
map(|node| &**node) と map(|node| &mut**node) を行う必要がありました。
「うわ、その &** ってやつ、本当にぎこちないな」と思っているかもしれませんが、それは間違っていません。
しかし、上質なワインのように Rust は時とともに良くなっていくので、もうそのようなことをする必要はありません。
通常、Rust はこの種の変換を暗黙的に行うのが非常に得意です。
これは deref coercion と呼ばれるプロセスを通じて行われ、基本的には型チェックが通るように
コード全体に * を挿入できます。これができるのは、ポインターを決しておかしくしないことを保証する
borrow checker があるからです！
しかし今回のケースでは、クロージャーと、&T ではなく Option<&T> を持っているという事実の組み合わせが
少し複雑すぎてうまく処理できないため、明示的に書いて手助けする必要があります。幸い、私の経験ではこれはかなりまれです。
完全を期すために言うと、turbofish を使って 別の ヒントを与えることもできます。
self.next = node.next.as_ref().map::<&Node<T>, _>(|node| &node);見てのとおり、map はジェネリック関数です。
pub fn map<U, F>(self, f: F) -> Option<U>ターボフィッシュ、::<> によって、これらのジェネリクスの型が何であるべきだと考えているかを
コンパイラに伝えられます。この場合、::<&Node<T>, _> は「&Node<T> を返すべきであり、
もう一方の型については知らない／気にしない」という意味です。
これにより、コンパイラは &node に deref coercion を適用すべきだと分かるため、
こちらで手動ですべての * を適用する必要がなくなります！
しかし今回のケースでは、これが本当に改善だとは思いません。これは単に、deref coercion と、 時には便利な turbofish を見せびらかすための、うっすらとした口実にすぎませんでした。😅
何もしていない状態になっていないことなどを確認するために、テストを書きましょう。
#[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_deref() }
}
}これは次と同等です。
impl<T> List<T> {
pub fn iter(&self) -> Iter<T> {
Iter { next: self.head.as_deref() }
}
}やった、ライフタイムが減りました！
あるいは、構造体がライフタイムを含んでいることを「隠す」のが気持ち悪い場合は、
Rust 2018 の「明示的に省略されたライフタイム」構文である '_ を使えます。
impl<T> List<T> {
pub fn iter(&self) -> Iter<'_, T> {
Iter { next: self.head.as_deref() }
}
}