余計なガラクタ

push と pop が書けたので、それ以外は奇妙なことに、スタックの場合と実際まったく同じです。リストの長さを変更する操作だけが、tail ポインタに触れる必要があります。

しかしもちろん、すべてが unsafe ポインタになったので、それらを使うようにコードを書き直す必要があります！ そしてどうせすべてのコードに触れるなら、 何か見落としていないか確認する機会にしてしまいましょう。

とはいえ、まずはスタック実装からコードをコピペするところから始めましょう。

// ...

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

IntoIter は問題なさそうですが、Iter と IterMut は、もう自分たちの型では安全なポインタを決して使わない、という単純なルールを破っています。安全を期して、これらを生ポインタを使うように変更しましょう。

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

pub struct Iter<'a, T> {
    next: *mut Node<T>,
}

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

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

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

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

よさそうです！

error[E0392]: parameter `'a` is never used
  --> src\fifth.rs:17:17
   |
17 | pub struct Iter<'a, T> {
   |                 ^^ unused parameter
   |
   = help: consider removing `'a`, referring to it in a field, 
     or using a marker such as `PhantomData`

error[E0392]: parameter `'a` is never used
  --> src\fifth.rs:21:20
   |
21 | pub struct IterMut<'a, T> {
   |                    ^^ unused parameter
   |
   = help: consider removing `'a`, referring to it in a field, 
     or using a marker such as `PhantomData`

よくなさそうです！ 彼らが言っているこの PhantomData とは何でしょう？

T を所有している「かのように振る舞う」ものを示すために使われるゼロサイズ型。

型に PhantomData<T> フィールドを追加すると、その型が実際にはそうしていなくても、型 T の値を格納しているかのように振る舞うことをコンパイラに伝えます。この情報は、特定の安全性プロパティを計算するときに使われます。

PhantomData<T> の使い方について、より詳しい説明は Nomicon を参照してください。

おいおい、早まらないでください。私たちは私が書いた本を読んでいるんです。どこかの大きなオタクがたぶん書いた、あの別の本ではありません！ どうせそこにデータ構造を書くなら、配列スタックみたいなつまらないもので、連結リストではないに決まっています。

未使用のライフタイムパラメータ

おそらく PhantomData の最も一般的なユースケースは、未使用のライフタイムパラメータを持つ構造体であり、典型的には何らかの unsafe コードの一部として使われます。

なるほど、つまり私たちは型の中でライフタイムに名前を付けているけれど、実際には使っていないわけです。PhantomData の道に進むこともできますが、それは次章の二重連結リストのために取っておきたいです。そこでは本当にそれが必要になります。

私たちは、実際には PhantomData が必要ないという興味深い状況にいます。たぶん。私はそう主張することにして、それが正しいと信じます。そして最後に miri が私たちに怒鳴ってきたら、その点を認めて PhantomData をやることにします。

実際にやることは、これらの Iterator 型に参照を戻して、一部の場所ではまだ参照を使えることを喜ぶ、というものです。イテレータを使うときには、まだある種の適切なネストがあるので、これは健全だと思います。つまり、イテレータを作成し、しばらく安全な参照を使い、その後イテレータを破棄します。

イテレータがなくなって初めて、リストにアクセスし、tail ポインタや Box をいじる必要がある push や pop のようなものを呼び出せます。さて、イテレーション中には多くの生ポインタを逆参照することになるので、そこにはある種の混在がありますが、それらの参照は unsafe ポインタの再借用として考えられるはずです。

私自身も 100% 納得しているわけではありませんが、とにかく試してみたいんです！

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 into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

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

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

参照を格納するつもりなら、生ポインタを参照の Option に昇格させる必要があります。ポインタが null かどうかを確認することもできますが、これは、厄介な ptr::as_ref と ptr::as_mut メソッドを使ってもよいと思う、信じられないほど狭いケースのひとつです。

私はふだんはこれらのメソッドを疫病のように避けることを勧めています。なぜなら、これらは驚くような厄介なことをいくつか行いますし、私の「簡単なルール」はそうすることを避けることなのに、本質的に参照を再導入してしまうからです！

これらのメソッドには多くの警告が付いていますが、最も興味深いのはこれです。

返されるライフタイム 'a は任意に選ばれ、データの実際のライフタイムを必ずしも反映しないため、Rust のエイリアシング規則を自分で強制しなければなりません。特に、このライフタイムの間、ポインタが指すメモリには、他のいかなるポインタ経由でもアクセス（読み取りまたは書き込み）してはなりません。

ほら、25 ページにわたって話していたやつです！ ここで参照を使っても私たちは絶対に大丈夫だと、私はすでに断言しました。なのでエイリアシングは解決です！ もうひとつの邪悪な部分はシグネチャです。

pub unsafe fn as_mut<'a>(self) -> Option<&'a mut T>

そのライフタイムが入力にまったく結び付いていないことがわかりますか？ なぜなら self が値渡しだからです。そうです、これを「非境界ライフタイム」と呼びます。そして厄介なものです。こちらが求めるだけ大きいふりをしてくれます。'static でさえも！ それに対処する方法は、それを境界付けられている場所に置くことです。たいていの場合、それは単に「関数シグネチャによって制限されるように、できるだけ早くこの値を関数から返す」という意味です。

いやあ、不安ですが、このまま押し進めましょう！ スタックからいくつかのイテレータ impl を盗んできます。

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> {
        unsafe {
            self.next.map(|node| {
                self.next = node.next.as_ref();
                &node.elem
            })
        }
    }
}

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

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

真実の瞬間です…

```text
cargo test

running 15 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... 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::iter ... ok
test third::test::basics ... ok

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

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test

running 15 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... 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. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

やった！！！ 思い知ったか、語り手！ ときには私だって間違えないんだ！

語り手: でも、そもそもの狙いは、その間違いが読者に教えるためにある、ということではなかったのですか。

ああそうだよ、でもときには「私が正しくて、unsafe コードについて私が何か言うときは全員が私の言うことを聞くべきだ、なぜなら私はイテレータ実装の健全性について考えるのにあまりにも長い時間を費やしてきたからだ」というのが教訓になることもあるんだよ？！ いいか？！ いいな。

ともあれ、これが peek と peek_mut です。

pub fn peek(&self) -> Option<&T> {
    unsafe {
        self.head.as_ref()
    }
}

pub fn peek_mut(&mut self) -> Option<&mut T> {
    unsafe {
        self.head.as_mut()
    }
}

もう間違えることなんてないので、テストすらしません。

語り手: cargo build

error[E0308]: mismatched types
  --> src\fifth.rs:66:13
   |
25 | impl<T> List<T> {
   |      - this type parameter
...
64 |     pub fn peek(&self) -> Option<&T> {
   |                           ---------- expected `Option<&T>` 
   |                                      because of return type
65 |         unsafe {
66 |             self.head.as_ref()
   |             ^^^^^^^^^^^^^^^^^^ expected type parameter `T`, 
   |                                found struct `fifth::Node`
   |
   = note: expected enum `Option<&T>`
              found enum `Option<&fifth::Node<T>>`

わかったよ。

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

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

どうやら私はこれからも間違え続けるらしいので、これからは一段と慎重になって、「miri food」と呼ぶ新しいテストを追加します。つまり、miri が私たちの間違いを見つけやすいように、いろいろいじくり回して私たちの API をごちゃ混ぜに使うものです。

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

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

    assert!(list.pop() == Some(1));
    list.push(4);
    assert!(list.pop() == Some(2));
    list.push(5);

    assert!(list.peek() == Some(&3));
    list.push(6);
    list.peek_mut().map(|x| *x *= 10);
    assert!(list.peek() == Some(&30));
    assert!(list.pop() == Some(30));

    for elem in list.iter_mut() {
        *elem *= 100;
    }

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&400));
    assert_eq!(iter.next(), Some(&500));
    assert_eq!(iter.next(), Some(&600));
    assert_eq!(iter.next(), None);
    assert_eq!(iter.next(), None);

    assert!(list.pop() == Some(400));
    list.peek_mut().map(|x| *x *= 10);
    assert!(list.peek() == Some(&5000));
    list.push(7);

    // そこらに放り出して、dtor に自分で仕事をさせる
}

cargo test

running 16 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fifth::test::miri_food ... 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::into_iter ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::iter ... ok
test second::test::iter ... ok
test third::test::basics ... ok

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



MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test

running 16 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fifth::test::miri_food ... 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::into_iter ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::iter ... ok
test second::test::iter ... ok
test third::test::basics ... ok

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

完璧です。