レイアウト

では、単方向リンクキューとはどのようなものでしょうか？単方向リンクスタックでは、リストの一方の端に 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)

キューを作るには、どちらの操作をリストの末尾へ移動するかを決めるだけです。 push でしょうか、それとも pop でしょうか？リストは単方向リンクなので、実はどちらの操作でも同じ労力で末尾へ移動できます。

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)

今日のところはこれをやって終わりにすることもできますが、それではひどいものになります！これらの操作はどちらもリスト全体を走査します。このようなキュー実装は正しいインターフェイスを公開しているので確かにキューだ、と主張する人もいるでしょう。しかし私は、性能保証もインターフェイスの一部だと考えています。正確な漸近的な境界にはこだわりません。単に「速い」か「遅い」かです。キューは push と pop が速いことを保証しており、リスト全体を走査するのは間違いなく速くありません。

重要な観察点の 1 つは、同じことを何度も繰り返して大量の作業を無駄にしていることです。その作業をすべて「キャッシュ」して再利用できないでしょうか？もちろん、できます！リストの末尾へのポインタを保存して、そこへ直接ジャンプすればよいのです！

これでうまくいくのは、push と pop の反転のうち一方だけであることがわかります。 pop を反転するには「tail」ポインタを後ろへ戻す必要がありますが、リストは単方向リンクなので、それを効率的に行うことはできません。代わりに push を反転するなら、「head」ポインタを前へ進めるだけでよく、これは簡単です。

試してみましょう。

use std::mem;

pub struct List<T> {
    head: Link<T>,
    tail: 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, tail: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // tail に 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);
            }
        }
    }
}

この種のことにはかなり慣れているはずなので、ここでは impl の詳細を少し速いペースで進めています。もっとも、このコードを必ずしも最初の試行で書けると期待すべき、というわけではありません。以前対処してきた試行錯誤の一部を飛ばしているだけです。実際には、このコードを書くときにここでは見せていない大量のミスをしましたが、 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

しまった！

moved された値 new_tail の使用

Box は Copy を実装していないので、単に 2 つの場所に代入することはできません。さらに重要なのは、Box はそれが指しているものを所有しており、drop されるときにそれを解放しようとするということです。もし push の実装がコンパイルできてしまったら、リストの tail を二重解放することになります！実際、書かれているとおりでは、このコードは push のたびに old_tail を解放してしまいます。ひえっ！ 🙀

さて、非所有ポインタの作り方はわかっています。それは単なる参照です！

pub struct List<T> {
    head: Link<T>,
    tail: Option<&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: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // tail に push するとき、next は常に None です
            next: None,
        });

        // box を正しい場所に置き、それからその Node への参照を取得する
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // 古い tail が存在した場合、それが新しい tail を指すように更新する
                old_tail.next = Some(new_tail);
                old_tail.next.as_deref_mut()
            }
            None => {
                // そうでなければ、head がそれを指すように更新する
                self.head = Some(new_tail);
                self.head.as_deref_mut()
            }
        };

        self.tail = new_tail;
    }
}

ここにはそれほど難しいことはありません。前のコードと同じ基本的な考え方ですが、実際の Box を詰め込んだ場所から tail の参照を取り出すために、暗黙の return の便利さを使っている点が違います。

> 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>>, // 新規!
}

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

        // Box を適切な場所に置き、それからその Node への参照を取得する
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // 古い tail が存在する場合は、新しい tail を指すように更新する
                old_tail.next = Some(new_tail);
                old_tail.next.as_deref_mut()
            }
            None => {
                // そうでない場合は、それを指すように head を更新する
                self.head = Some(new_tail);
                self.head.as_deref_mut()
            }
        };

        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_deref_mut()
   |                           ^^^^^^^^^^^^
   |
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 | |             // When you push onto the tail, your next is always 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_deref_mut()
   |                 ^^^^^^^^^
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>>

うわ、これは本当に詳細なエラーメッセージです。少し気がかりです。なぜなら、私たちが何か本当にめちゃくちゃなことをしていると示唆しているからです。興味深い部分はここです。

lifetime は、impl で定義された lifetime 'a に対して有効でなければならない

私たちは self から借用していますが、コンパイラはそれが 'a と同じだけ長く続くことを求めています。では、self は実際にその長さだけ続く、と伝えたらどうなるでしょうか..?

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

そして、そのための簡単なテストを書きます。

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

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


....

** WAY MORE LINES OF ERRORS **

....

error: aborting due to 11 previous errors

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

なんということでしょう。

コンパイラが私たちに向かって盛大に吐き散らすのも無理はありません。私たちは Rust における重大な罪を犯しました。自分自身への参照を、自分自身の中に格納したのです。どういうわけか、push と pop の実装の中では、これがまったく筋が通っていると Rust を納得させることに成功してしまいました（正直、できたことに本当に驚きました）。

これがある程度うまくいく理由は、Rust にはそもそも自分自身の中へのポインタという概念が実質的に存在しないからです。コードの各部分は、単独で見れば技術的には正しいのです（push と pop を一度だけ呼ぶことはできます）。しかし、その後、私たちが作り出したものの不条理さが効いてきて、すべてが固まってしまいます。

私たちが書いたものにも何らかの用途はあるのかもしれませんが、少なくとも私に言わせれば、これは構文的には有効な意味不明な代物にすぎません。私たちは lifetime 'a を持つ何かを自分が含んでおり、push と pop はその lifetime の間ずっと self を借用する、と言っているのです。それは奇妙ですが、Rust は私たちのコードの各部分を個別に見て、破られているルールがないと判断できます。

しかし、実際にリストを使おうとした瞬間、コンパイラはすぐに「はい、あなたは self を 'a の間ミュータブルに借用しました。したがって 'a の終わりまで self はもう使えません」と言い、同時に「あなたは 'a を含んでいるので、それはリストが存在する全期間に対して有効でなければなりません」と言います。

これはほとんど矛盾ですが、解は1つあります。push または pop した瞬間、リストは自分自身をその場に「ピン留め」し、それ以上アクセスできなくなります。ことわざに言う自分の尻尾を飲み込み、夢の世界へと昇っていったのです。

ナレーター: この本が最初に書かれたときには存在していませんでしたが、Rust は実際に pin という概念を有用なものとして正式化しました！これはおそらく、借用チェッカー 以来、言語に加えられた最も複雑な追加でした。とはいえ、私たちのリストはピン留めされたくはありません！

Pin は async-await/futures/coroutines にとっては必要で有用です。なぜならコンパイラは、関数のすべてのローカル変数を何らかの構造体にまとめ、 future/coroutine が再開可能になるまでどこかに保存できる必要があるからです。ローカル変数は他のローカル変数を参照でき、私たちはそれが動作することを望むため、これらの構造体は自分自身への参照を含むことになり得ます！

そのため、Rust が await や yield を行うには、ピン留めされた値を適切に記述し、操作できる方法が必要です。ありがたいことに、これらのものはすべて大部分 自動的なコンパイラの仕組みの中に隠されており、通常の状況では実際に Pin（あるいは Futures でさえ）について考える必要はありません。主な例外は、 tokio のような async ランタイム を構築・設計している人たちにとっては、この仕組みが非常に重要だということです。

この本では async ランタイムを実装しません。私の友人たちが Pin でできるさまざまな「クールな」（めちゃくちゃな）トリックを知っていることは分かっていますが、私の見る限り、それらを知らないままでいたほうが幸せそうです。私はこれからも、ピン留めされた型など実在せず、私を傷つけることはできないと自分に言い聞かせ続けます。

私たちの 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>, // 危険 危険
}

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

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

これで終わりです。参照カウント付き動的借用チェックなんていう軟弱なたわごとは一切ありません！本物の。ハードな。未チェックの。ポインタです。

ナレーター: 実際には、この実装は依然として危険なほど間違っていましたが、その教訓を学ぶ時はまだ来ていませんでした。次のセクションでは、いつものように痛い目を見てそれを学ぶことになります。

みんなで C になりましょう。一日中 C でいましょう。

ただいま。準備はできています。

こんにちは、unsafe。

ナレーター: わあ、ここで著者の信じられないほどの思い上がりです。

Keyboard shortcuts

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

レイアウト