スタック割り当てのリンクリスト

この本は主にヒープ割り当てのリンクリストに焦点を当てています。なぜなら、それらが最も一般的で実用的だからです。しかし、ヒープ割り当てを使わなければならないわけではありません。ヒープ割り当ては、メモリを動的に割り当てるのを簡単にしてくれるので便利です。この点でスタック割り当てはあまり扱いやすくありません — C の alloca のようなものは、広く「非常に呪われていて問題が多いもの」と見なされています。

そこで、簡単な方法でスタック上にメモリを割り当てましょう。関数を呼び出して、より多くの領域を持つ新しいスタックフレームを得るのです！これは私たちの問題に対する非常に馬鹿げた解決策ですが、同時に本当に実用的で有用でもあります。これは常に行われていて、実際にはリンクリストとして意識されることすらないかもしれません！

何かを再帰的に行っているときはいつでも、現在のステップの状態へのポインタを次のステップに渡すだけで済みます。そのポインタ自体が状態の一部であるなら、スタック割り当てされたリンクリストを作成したことになります！

もちろん今はこの本の馬鹿げた部分にいるので、これを馬鹿げた方法でやります。リンクリストを主役にし、ユーザーのコードをすべてコールバックの沼に住まわせるのです。みんなネストしたコールバックが大好きです！

私たちの List 型は、別の Node への参照を持つ Node にすぎません。

#![allow(unused)]
fn main() {
pub struct List<'a, T> {
    pub data: T,
    pub prev: Option<&'a List<'a, T>>,
}
}

そして操作は push ただ 1 つだけで、これは古いリスト、現在のノードの状態、そしてコールバックを受け取ります。新しいリストはコールバック内で生成されます。また、コールバックが任意の値を返せるようにし、push は完了時にそれを返すようにします。

impl<'a, T> List<'a, T> {
    pub fn push<U>(
        prev: Option<&'a List<'a, T>>, 
        data: T, 
        callback: impl FnOnce(&List<'a, T>) -> U,
    ) -> U {
        let list = List { data, prev };
        callback(&list)
    }
}

これだけです！次のように使えます。

List::push(None, 3, |list| {
    println!("{}", list.data);
    List::push(Some(list), 5, |list| {
        println!("{}", list.data);
        List::push(Some(list), 13, |list| {
            println!("{}", list.data);
        })
    })
})

美しいですね。😿

ユーザーはすでに、prev の値をたどるために while-let を使ってこのリストを走査できますが、せっかくなので、いつものようにイテレータを実装してみましょう。

impl<'a, T> List<'a, T> {
    pub fn iter(&'a self) -> Iter<'a, T> {
        Iter { next: Some(self) }
    }
}

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.prev;
            &node.data
        })
    }
}

試してみましょう。

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn elegance() {
        List::push(None, 3, |list| {
            assert_eq!(list.iter().copied().sum::<i32>(), 3);
            List::push(Some(list), 5, |list| {
                assert_eq!(list.iter().copied().sum::<i32>(), 5 + 3);
                List::push(Some(list), 13, |list| {
                    assert_eq!(list.iter().copied().sum::<i32>(), 13 + 5 + 3);
                })
            })
        })
    }
}

> cargo test

running 18 tests
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fifth::test::basics ... ok
test fifth::test::miri_food ... ok
test first::test::basics ... ok
test second::test::into_iter ... ok
test fourth::test::peek ... ok
test fourth::test::into_iter ... ok
test second::test::iter_mut ... ok
test fourth::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok
test silly1::test::walk_aboot ... ok
test silly2::test::elegance ... ok
test second::test::peek ... ok
test third::test::iter ... ok

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

さて、この時点で「ノードに格納されているデータを変更できるのかな？」と思うかもしれません。できるかもしれません！リストが共有参照ではなくミュータブル参照を使うようにしてみましょう。

#![allow(unused)]
fn main() {
pub struct List<'a, T> {
    pub data: T,
    pub prev: Option<&'a mut List<'a, T>>,
}

pub struct Iter<'a, T> {
    next: Option<&'a List<'a, T>>,
}

impl<'a, T> List<'a, T> {
    pub fn push<U>(
        prev: Option<&'a mut List<'a, T>>, 
        data: T, 
        callback: impl FnOnce(&mut List<'a, T>) -> U,
    ) -> U {
        let mut list = List { data, prev };
        callback(&mut list)
    }

    pub fn iter(&'a self) -> Iter<'a, T> {
        Iter { next: Some(self) }
    }
}

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.prev.as_ref().map(|prev| &**prev);
            &node.data
        })
    }
}

}

> cargo test

error[E0521]: borrowed data escapes outside of closure
  --> src\silly2.rs:47:32
   |
46 |  List::push(Some(list), 13, |list| {
   |                              ----
   |                              |
   |              `list` declared here, outside of the closure body
   |              `list` is a reference that is only valid in the closure body
47 |      assert_eq!(list.iter().copied().sum::<i32>(), 13 + 5 + 3);
   |                 ^^^^^^^^^^^ `list` escapes the closure body here

error[E0521]: borrowed data escapes outside of closure
  --> src\silly2.rs:45:28
   |
44 |  List::push(Some(list), 5, |list| {
   |                             ----
   |                             |
   |              `list` declared here, outside of the closure body
   |              `list` is a reference that is only valid in the closure body
45 |      assert_eq!(list.iter().copied().sum::<i32>(), 5 + 3);
   |                 ^^^^^^^^^^^ `list` escapes the closure body here


<ad infinitum>

うーん。どうやらイテレータが気に入らないようです。私たちが何か間違えたのでしょうか？確認するために、テストを少し単純化してみましょう。

#[test]
fn elegance() {
    List::push(None, 3, |list| {
        assert_eq!(list.data, 3);
        List::push(Some(list), 5, |list| {
            assert_eq!(list.data, 5);
            List::push(Some(list), 13, |list| {
                assert_eq!(list.data, 13);
            })
        })
    })
}

> cargo test

error[E0521]: borrowed data escapes outside of closure
  --> src\silly2.rs:46:17
   |
44 |   List::push(Some(list), 5, |list| {
   |                              ----
   |                              |
   |              `list` declared here, outside of the closure body
   |              `list` is a reference that is only valid in the closure body
45 |       assert_eq!(list.data, 5);
46 | /     List::push(Some(list), 13, |list| {
47 | |         assert_eq!(list.data, 13);
48 | |     })
   | |______^ `list` escapes the closure body here

error[E0521]: borrowed data escapes outside of closure
  --> src\silly2.rs:44:13
   |
42 |   List::push(None, 3, |list| {
   |                        ----
   |                        |
   |              `list` declared here, outside of the closure body
   |              `list` is a reference that is only valid in the closure body
43 |       assert_eq!(list.data, 3);
44 | /     List::push(Some(list), 5, |list| {
45 | |         assert_eq!(list.data, 5);
46 | |         List::push(Some(list), 13, |list| {
47 | |             assert_eq!(list.data, 13);
48 | |         })
49 | |     })
   | |______________^ `list` escapes the closure body here

うーん、いや、これはまだかなりひどい代物です。

問題は、私たちのリストがうっかり(😉) 分散性に依存していることです。分散性は複雑なトピックですが、ここでは簡略化して見てみましょう。

各リストは、自分自身とまったく同じ型を持つ List への参照を含んでいます。最も内側のリストの視点からすると、それはすべてのリストが自分自身と同じライフタイムを使っていることを意味しますが、これは客観的に誤りです。リスト内の各ノードは、次のノードよりも厳密に長く生存します。なぜなら、それらは文字どおりネストしたスコープ内にあるからです！

では……なぜ共有参照を使っていたときはコードがコンパイルできたのでしょうか？ 多くの場合、コンパイラは「長すぎる」寿命を持つものがあっても安全だと知っているからです！ リストへの参照を次のリストに詰め込むとき、コンパイラはライフタイムを静かに「縮めて」、新しいリストが期待するものに合うようにしています。このライフタイムの縮小が分散性です。

これは、継承のある言語で、Animal（Cat のスーパータイプ）が期待される場所に Cat を渡せるのとまったく同じトリックです。直感的には、Animal が期待されているときに Cat を渡しても問題ないことが分かります。Cat は単に Animal であり、さらにそれ以上だからです。しばらく「さらにそれ以上」の部分を忘れても問題ありませんよね？

同様に、より大きなライフタイムは、より小さなライフタイムであり、さらにそれ以上です。ですから、ここでも「さらにそれ以上」を忘れて構いません！

しかしもちろん、今あなたは疑問に思っているでしょう。ではなぜ可変参照版は動かないのか！？

さて、分散性は常に安全とは限りません。もし私たちのコードがコンパイルできたなら、次のような use-after-free を書けてしまいます。

List::push(None, 3, |list| {
    List::push(Some(list), 5, |list| {
        List::push(Some(list), 13, |list| {
            // ハハハ、すべてのライフタイムは同じだから、コンパイラは
            // 親を書き換えて、自分自身への可変参照を持たせることを許してくれる！
            // use-after-free を作り放題だ！！
            *list.prev.as_mut().unwrap().prev = Some(list);
        })
    })
})

詳細を忘れることの問題は、どこか別の場所がその詳細を覚えていて、 それが真であり続けることを期待しているかもしれないことです。これは、変更を導入すると 非常に大きな問題になります。注意しないと、私たちが捨てた「さらにそれ以上」を 覚えていないコードが、「覚えていて」かつ「さらにそれ以上」がまだそこにあることを期待している 場所へ書き込んでも問題ない、と考えてしまうかもしれません。

継承の観点で言うと、このコードは不正でなければなりません。

let mut my_kitty = Cat;                  // Cat を作る（長いライフタイム）
let animal: &mut Animal = &mut my_kitty; // それが Cat であることを忘れる（ライフタイムを縮める）
*animal = Dog;                           // Dog を書き込む（短いライフタイム）
my_kitty.meow();                         // 鳴く Dog！（Use After Free）

そのため、可変参照のライフタイムを縮めること自体は可能ですが、それらをネストし始めると、物事は「不変」になり、もはやライフタイムを縮めることは許されません。

具体的には、&mut &'big mut T を &mut &'small mut T に変換することはできません。ここで 'big は 'small よりも大きいものとします。より形式的に言えば、&'a mut T は 'a に関しては共変ですが、T に関しては不変です。

面白い事実として、Java は実際にはこの種のことを特に許可していますが、鳴く犬を防ぐために実行時チェックを行います。

では、データを変更するにはどうすればよいのでしょうか？ 内部可変性を使います！ これにより、コンパイラに対して、私たちはデータを変更できるようにしたいだけで、参照には触れないと伝えられます。

共有参照を使っていた以前のバージョンのコードに戻し、新しいテストで Cell を使うだけで済みます。

#[test]
fn cell() {
    use std::cell::Cell;

    List::push(None, Cell::new(3), |list| {
        List::push(Some(list), Cell::new(5), |list| {
            List::push(Some(list), Cell::new(13), |list| {
                // リスト内のすべての値を 10 倍する
                for val in list.iter() {
                    val.set(val.get() * 10)
                }

                let mut vals = list.iter();
                assert_eq!(vals.next().unwrap().get(), 130);
                assert_eq!(vals.next().unwrap().get(), 50);
                assert_eq!(vals.next().unwrap().get(), 30);
                assert_eq!(vals.next(), None);
                assert_eq!(vals.next(), None);
            })
        })
    })
}

> cargo test

running 19 tests
test fifth::test::into_iter ... ok
test fifth::test::basics ... ok
test fifth::test::iter_mut ... ok
test fifth::test::iter ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test second::test::into_iter ... ok
test first::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fifth::test::miri_food ... ok
test silly2::test::cell ... ok
test third::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test silly1::test::walk_aboot ... ok
test silly2::test::elegance ... ok
test third::test::basics ... ok
test second::test::iter ... ok

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

再帰的なパイのように簡単ですね！ ✨