構築していく

よし、リストの構築から始めましょう。この新しい仕組みなら、これはかなり単純です。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

**大量の dead code 警告が出たがビルドは通った**

やった！

では、リストの先頭に push する処理を書いてみましょう。双方向リンクリストはかなり複雑なので、もう少し多くの作業が必要になります。単方向リンクリストの操作は簡単なワンライナーに還元できましたが、双方向リンクリストの操作はかなり複雑です。

特に、空リスト周辺の境界ケースを特別に扱う必要があります。ほとんどの操作は head または tail ポインタだけに触れます。しかし空リストへ遷移するとき、または空リストから遷移するときには、両方を同時に編集する必要があります。

メソッドが妥当かどうかを検証する簡単な方法は、次の不変条件を維持することです。各ノードには、それを指すポインタがちょうど 2 つあるべきです。リストの中央にある各ノードは、その前のノードと次のノードから指され、端にあるノードはリスト自身から指されます。

試しにやってみましょう。

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 が邪魔をしているようです。

ドキュメントを確認したほうがよさそうです。

Google で「rust refcell」を検索

最初のリンクをクリック

動的にチェックされる借用ルールを持つミュータブルなメモリ位置

詳細については、モジュールレベルのドキュメントを参照してください。

リンクをクリック

共有可能なミュータブルコンテナ。

Cell<T> 型と RefCell<T> 型の値は共有参照（つまり一般的な &T 型）を通じて変更できますが、ほとんどの Rust 型は一意な（&mut T）参照を通じてしか変更できません。 Cell<T> と RefCell<T> は、典型的な Rust 型が示す「継承された可変性」と対照的に、「内部可変性」を提供すると言います。

Cell 型には 2 つの種類があります。Cell<T> と RefCell<T> です。Cell<T> は、1 回のメソッド呼び出しで内部の値を変更する get メソッドと set メソッドを提供します。ただし Cell<T> は、Copy を実装する型としか互換性がありません。他の型では、変更前に書き込みロックを取得して RefCell<T> 型を使う必要があります。

RefCell<T> は Rust のライフタイムを使って「動的借用」を実装します。これは、内部の値に対する一時的で排他的なミュータブルアクセスを主張できるプロセスです。RefCell<T> の借用は「実行時」に追跡されます。これは、Rust のネイティブな参照型がコンパイル時に完全に静的に追跡されるのとは異なります。RefCell<T> の借用は動的であるため、すでにミュータブルに借用されている値を借用しようとすることが可能です。この場合、スレッドの panic が発生します。

内部可変性を選ぶべき場合

値を変更するには一意なアクセスが必要になる、より一般的な継承された可変性は、Rust がポインタのエイリアシングについて強力に推論し、クラッシュバグを静的に防ぐことを可能にする主要な言語要素の 1 つです。そのため、継承された可変性が望ましく、内部可変性はいわば最後の手段です。ただし、cell 型は本来許可されない場所での変更を可能にするため、内部可変性が適切な場合、あるいは使用が必須となる場合があります。たとえば次のような場合です。

共有型に継承された可変性のルートを導入する。

論理的にイミュータブルなメソッドの実装詳細。

Clone のミュータブルな実装。

共有型に継承された可変性のルートを導入する

Rc<T> や Arc<T> を含む共有スマートポインタ型は、複数の関係者の間で clone して共有できるコンテナを提供します。含まれる値は複数のエイリアスを持ち得るため、ミュータブル参照としてではなく共有参照としてしか借用できません。 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

おお、ビルドできました！またもドキュメントの勝利です。

Keyboard shortcuts

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

構築していく

内部可変性を選ぶべき場合

共有型に継承された可変性のルートを導入する