イテレーション

この厄介者をイテレートすることに取り組んでみましょう。

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<Self::Item> {
        self.0.pop_front()
    }
}

しかし、興味深い新展開があります。以前はリストに対して「自然な」イテレーション順序は常に 1 つしかありませんでしたが、Deque は本質的に双方向です。前から後ろへ進むことの何がそんなに特別なのでしょうか？逆方向にイテレートしたい人がいたらどうでしょう？

Rust には実はこれに対する答えがあります。DoubleEndedIterator です。DoubleEndedIterator は Iterator から継承しており（つまり、すべての DoubleEndedIterator は Iterator です）、新しいメソッドを 1 つ要求します。それが next_back です。これは next とまったく同じシグネチャを持ちますが、反対側の端から要素を生成することが期待されます。 DoubleEndedIterator のセマンティクスは私たちにとって非常に便利です。イテレータが deque になるのです。両端が収束するまで前後から要素を消費でき、その時点でイテレータは空になります。

Iterator と next の場合とよく似て、next_back は実のところ DoubleEndedIterator の利用者が本当に気にするものではないことがわかります。むしろ、このインターフェイスの最も良い部分は、要素を逆順に生成する新しいイテレータを作るためにイテレータをラップする rev メソッドを公開していることです。このセマンティクスはかなり単純です。反転されたイテレータに対する next の呼び出しは、単に next_back の呼び出しです。

ともあれ、私たちはすでに deque なので、この API を提供するのはかなり簡単です。

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 の寿命が十分ではありません。通常の参照とは異なり、Rust はこのように Ref を単純に分割させてはくれません。head.borrow() から得られる Ref は node_ref と同じ期間だけしか生存できませんが、私たちは最終的に Ref::map 呼び出しでそれを破棄してしまいます。

私たちが求めている関数は存在し、[map_split][] と呼ばれています。

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/ADesires/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

うーん。ライフタイムを正しくするには、再び Ref::Map する必要があります。しかし Ref::Map は Ref を返し、私たちが必要としているのは Option<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 のスタックを維持する必要があります。というのも、ある要素を見るのをやめるなら、その前にあるすべての RefCell の借用カウントをデクリメントしなければならないからです……………..

ここでできることは何もないと思います。行き止まりです。RefCell から抜け出すことを試してみましょう。

では Rc はどうでしょう。そもそも参照を保存する必要があると誰が言ったのでしょうか？ Rc 全体を Clone して、リストの途中への扱いやすい所有ハンドルを得ればよいのではないでしょうか？

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 します。

これは実際かなりすごいことです。リスト内部への所有ポインタを大量に取得し、それと同時にリストを変更できます。そして、私たちが指しているノードを削除しようとするまでは ただ動くのです。さらにその場合でも、ダングリングポインタなどが発生するわけではなく、プログラムは決定的に panic します！

しかし、Rc の map に加えてイテレータの無効化にも対処しなければならないのは、どうにも……よくありません。Rc<RefCell> は本当に、本当に、ついに私たちを裏切りました。興味深いことに、永続スタックの場合とは逆転した状況を経験しました。永続スタックはデータの所有権を取り戻すのに苦労した一方で参照はいくらでも取得できましたが、私たちのリストは所有権を得ることには何の問題もない一方で、参照を貸し出すことに非常に苦労しました。

もっとも公平を期すなら、苦労の大部分は、実装の詳細を隠し、まともな API を持ちたいということを中心にしていました。あちこちで Node を渡し回すつもりなら、すべて問題なく行うことはできました。

実際、同じ要素に対して可変アクセスしていないことをランタイムでチェックされる、複数の並行した IterMut を作ることだってできました！

本当に、この設計は API の利用者に決して公開されない内部データ構造により適しています。内部可変性は、安全なアプリケーションを書くには素晴らしいものです。安全なライブラリには、それほど向いていません。

ともあれ、これが Iter と IterMut を諦めるということです。実装することはできるでしょうが、 うへえ。

Keyboard shortcuts

Learning Rust With Entirely Too Many Linked Lists 日本語版

イテレーション

IntoIter

Iter