【Rust入門】意図的にメモリリークを起こす


Rustの入門として、[Reference Cycles Can Leak Memory](https://doc.rust-lang.org/book/ch15-06-reference-cycles.html)（[日本語版](https://doc.rust-jp.rs/book-ja/ch15-06-reference-cycles.html)）のうち以下に示すコード(以下、本コード)をみていきます。
想定読者は、Rust初学者で特に[TRPL](https://doc.rust-lang.org/book/title-page.html)を勉強中の方です。
私も勉強中の身なので、全く分かっていない部分が多くあります。誤っている箇所はご指摘ください。

```rust
use List::{Cons, Nil};
use std::rc::Rc;
use std::cell::RefCell;
#[derive(Debug)]
enum List {
    Cons(i32, RefCell<Rc<List>>),
    Nil,
}

impl List {
    fn tail(&self) -> Option<&RefCell<Rc<List>>> {
        match *self {
            Cons(_, ref item) => Some(item),
            Nil => None,
        }
    }
}

fn main() {
    let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil))));

    // aの最初の参照カウント = {}
    println!("a initial rc count = {}", Rc::strong_count(&a));
    // aの次の要素は = {:?}
    println!("a next item = {:?}", a.tail());

    let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a))));

    // b作成後のaの参照カウント = {}
    println!("a rc count after b creation = {}", Rc::strong_count(&a));
    // bの最初の参照カウント = {}
    println!("b initial rc count = {}", Rc::strong_count(&b));
    // bの次の要素 = {:?}
    println!("b next item = {:?}", b.tail());

    if let Some(link) = a.tail() {
        *link.borrow_mut() = Rc::clone(&b);
    }

    // aを変更後のbの参照カウント = {}
    println!("b rc count after changing a = {}", Rc::strong_count(&b));
    // aを変更後のaの参照カウント = {}
    println!("a rc count after changing a = {}", Rc::strong_count(&a));

    // Uncomment the next line to see that we have a cycle;
    // it will overflow the stack
    // 次の行のコメントを外して循環していると確認してください; スタックオーバーフローします
    println!("a next item = {:?}", a.tail());        // aの次の要素 = {:?}
}

```
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=49367541f3f49fc6dbb5b78436767bfb

## 概要

　このコードは循環参照によってメモリリークを引き起こし、最終的にスタックオーバーフローします。
メモリリークとはメモリが解放されない状態を指し、ガベージコレクション(GC)のない言語では意識しなければならない現象です。RustにGCはありませんが、所有権と借用やライフタイム[^1]という仕組みによって独自のタイミングで自動的にメモリが解放されます(Rustではこれをドロップと呼びます)。しかし、本コードのように互いに参照するような値がある場合は、メモリリークを起こすことがあります。
スタックオーバーフローとは、スタック容量を超えてスタックを確保しようとすることです。Rustのデフォルトスタック容量は2～8MiBのようなので、例えば以下のコードで簡単に引き起こすことができます。

[^1]: 参照が有効なスコープのことです ([docs](https://doc.rust-jp.rs/book-ja/ch10-03-lifetime-syntax.html))。

```rust
fn main() {
    // aは1を1000万個もつ固定長配列
    let a = [1; 10_000_000];
    println!("{:?}", a);
}
```

```bash:スタックオーバーフローのエラー表示
thread 'main' has overflowed its stack
fatal runtime error: stack overflow
timeout: the monitored command dumped core
```

　循環参照を作るため、本コードでは参照カウンタ方式のポインタと内部可変性を利用しています。
参照カウンタ方式のポインタとは、値の解放を参照カウンタによって決定するポインタです。python言語の変数代入に使用されるポインタが参照カウンタ方式で、自身への参照カウンタが0になったときに値が解放されます。つまり値が解放されないようにするには、参照カウントを1以上に保つ状況を作ればよいということになります。下図のa,bでは互いに参照するポインタを用意して、双方が互いの参照カウントを1以上に保っています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/782908/145dc1e2-964a-4b96-b399-6438ec533ddc.png)
(画像引用元：https://doc.rust-jp.rs/book-ja/ch15-06-reference-cycles.html)

一方で、Rustにおいては参照カウンタ方式のポインタ (Rcポインタ)で循環参照を作る上では一つ問題があります。それは、Rcポインタから参照されている値は不変でなければならない[^2]ことです。循環参照を作る上では、以下の手順を踏むことになりますが、手順3で値を変更できないということになります。

準備: 再帰的な型(コンスリスト; 後述)を作ります
1. コンスリスト(5, Nil)へのRcポインタをaする
2. コンスリスト(10, a)へのRcポインタをbとする
3. aから参照されるコンスリストを(5, Nil)から(5, b)とする

[^2]: 値が複数の所有者から共有されるという前提があるためです。Rustでは可変参照の生存期間中は排他的アクセスとなり、例えば他の所有者から読み取れなくなるという仕様があります。

この問題を解消するため、一部の値のみ可変となるようにコンパイラへ指示します(内部可変性[^3])。これで構造体のフィールドを可変にせずとも可変参照を作ることできるため、上図のような循環参照をつくることができます。

[^3]: 構造体のもつ値のうち、ほとんどが不変であるにもかかわらず一部の値のみ可変であるような性質を指します。これは例えば`Cell<T>`や`RefCell<T>`によって実装できます。

## 詳細
### 使用している列挙型について

```rust:src/main.rs
#[derive(Debug)]
enum List {
    Cons(i32, RefCell<Rc<List>>),
    Nil,
}
```

`enum`は列挙型の宣言で、`List`型には`Cons(i32, RefCell<Rc<List>>)`か`Nil`といういずれかの列挙子が当てはまることになります。
※　`Cons()`や`Nil`はここで初めて定義した列挙子であり、Rustによって標準化された型ではないことに注意
(なお`Nil`は一般的なnull, nilと異なり、繰り返しの基底を示すときに使われる単語のようです)
参考：　https://doc.rust-jp.rs/book-ja/ch15-01-box.html

`Cons(i32, RefCell<Rc<List>>)`は`i32`型と`RefCell<Rc<List>>`型との二要素によるコンスリストとなっています。
コンスリストは、二要素(現在の要素と次の要素)による構成であり、最後の要素には`nil`という値のみを持つようなデータ構造です。これはリストを作るために関数型プログラミング言語で頻繁に使用されますが、Rustでは`Vec<T>`を使用するのが一般的です。それでも本コードで使用している理由は再帰的なデータ型の一例としてシンプルだからとのことでした。

例えば下記コードは、下図のように`i32`型のコンスリストを表現するための列挙型`List`を定義しています。
```rust
enum List {
    Cons(i32, List),
    Nil,
}
```
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/782908/ec2c7c3c-a761-f269-2645-2f06d2b4916d.png)

(画像引用元：https://doc.rust-jp.rs/book-ja/ch15-01-box.html)

参考：
https://doc.rust-jp.rs/book-ja/ch15-01-box.html#%E3%82%B3%E3%83%B3%E3%82%B9%E3%83%AA%E3%82%B9%E3%83%88%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6%E3%82%82%E3%81%A3%E3%81%A8%E8%A9%B3%E3%81%97%E3%81%8F
https://ja.wikipedia.org/wiki/Cons_(Lisp)

`RefCell<Rc<List>>)`は、`Rc<List>`の値について可変性を許容する構造体型です。
内部的にはunsafeなコード[^4]により、コンパイル時のエラーを回避し、ライフタイム[^1]を活用して実行時の動的な借用を実現しているようです。
参考：
https://zenn.dev/mebiusbox/books/22d4c1ed9b0003/viewer/5df75e
https://doc.rust-lang.org/std/cell/index.html

[^4]: コンパイラが安全性を保証できないことを理解した上で使用する必要があるコードを指します(このコードによる結果に対してコンパイラは責任を持たない)。

### 次の要素を取得する

```rust:src/main.rs
impl List {
    fn tail(&self) -> Option<&RefCell<Rc<List>>> {
        match *self {
            Cons(_, ref item) => Some(item),
            Nil => None,
        }
    }
}
```

impl宣言で`List`型にメソッドを定義します。


`tail`メソッドは、次の要素 (`match`句で式`*self`の値)が`Nil`ならば`None`を返します。
<!-- selfがでリファレンスされているのは、match式へ&をつけなければならないため慣習的にか？ためしにselfでも同じ値となるが、matchが解決しているのだろうか？ -->
<details><summary>match式について</summary>

match式はパターンマッチを行い、Rustで多用されています。
例えば`Option<T>`から中身の`T`値を取得する[unwrapメソッド](https://doc.rust-lang.org/std/option/enum.Option.html#method.unwrap)ではmatch式が実装されています。
もちろん、match式を書いて明示的に指定することもできます。

```rust
#![allow(unused)]
fn main() {
  fn plus_one(x: Option<i32>) -> Option<i32> {
      match x {
          None => None,
          Some(i) => Some(i + 1),
      }
  }

  let five = Some(5);
  let six = plus_one(five);
  assert_eq!(six, Some(6));
  let none = plus_one(None);
  assert_eq!(none, None);
}
```
コンパイラによってmatch式には網羅性が要求され、`None`の場合を書き損じると丁寧に教えてくれます。
```bash
error[E0004]: non-exhaustive patterns: `None` not covered
(エラー: 包括的でないパターン: `None`がカバーされてません)
 -->
  |
6 |         match x {
  |               ^ pattern `None` not covered

```
参考：　https://doc.rust-jp.rs/book-ja/ch06-02-match.html#match%E5%88%B6%E5%BE%A1%E3%83%95%E3%83%AD%E3%83%BC%E6%BC%94%E7%AE%97%E5%AD%90
</details>

メソッドは第一引数に必ず、メソッドを呼び出す主体を意味する`self`を与えなければなりません。
<details><summary>サンプルコード</summary>


（下の例で`m.call()`メソッドの`self`には`m`の値が入る）
参考：　https://doc.rust-jp.rs/book-ja/ch06-01-defining-an-enum.html
```rust
#![allow(unused)]
fn main() {
enum Message {
    Quit,
    Move { x: i32, y: i32 },
    Write(String),
    ChangeColor(i32, i32, i32),
}

impl Message {　
    fn call(&self) {
        // method body would be defined here
        // メソッド本体はここに定義される
    }
}

let m = Message::Write(String::from("hello"));
m.call();
}
```

ちなみに、引数が`self`(値)や`&mut self`(可変参照)ではなく`&self`(不変参照)であることから、このメソッドは呼び出し元の変更を伴わないことが実装をみなくてもわかったりします。

</details>

`Option<T>`列挙子は標準ライブラリに定義された列挙型であるため、use宣言は不要です。

<details><summary>Option<T>型について</summary>

```rust
#![allow(unused)]
fn main() {
  enum Option<T> {
      Some(T),
      None,
  }
}
```
Rustはnullの代わりに`Option<T>`型の`None`列挙子を用いています。そうすることで`Option<T>`を使用している箇所には値がnullになる場合の処理を強制させることができるし、`Option<T>`を使用しない値にnullが当てはまらないことを暗黙的に担保することができます。
参考：　https://doc.rust-jp.rs/book-ja/ch06-01-defining-an-enum.html#option-enum%E3%81%A8null%E5%80%A4%E3%81%AB%E5%8B%9D%E3%82%8B%E5%88%A9%E7%82%B9
</details>

`ref`はタプルのフィールドへの参照を取得しているようです。参照でない場合は所有権が移動してしまいます。
参考：　https://doc.rust-jp.rs/rust-by-example-ja/scope/borrow/ref.html
　　　　https://doc.rust-jp.rs/rust-by-example-ja/flow_control/match/destructuring/destructure_pointers.html




### main関数でやっていることについて


#### コンスリスト(5, Nil)へのRcポインタをaとする

```rust:main.rs
    let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil))));

    // aの最初の参照カウント = {}
    println!("a initial rc count = {}", Rc::strong_count(&a));
    // aの次の要素は = {:?}
    println!("a next item = {:?}", a.tail());

```

変数`a`の初期化には、`Cons()`列挙子に`List::Cons(1, RefCell<Rc<Nil>>)`という値を付与しています。
参考：　https://doc.rust-jp.rs/book-ja/ch06-01-defining-an-enum.html

`a.tail()`では、aの暗黙的なデリファレンスが起こっています。コンパイラが`Rc<T>`から`T`の参照を借用してくれるため、`tail`メソッドの引数`self`には`List`型が該当するようになります。
[Rc::strong_count](https://doc.rust-lang.org/std/rc/struct.Rc.html#method.strong_count)で参照カウント数を確認できます。


#### コンスリスト(10, a)へのRcポインタをbとする

```rust:main.rs
    let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a))));

    // b作成後のaの参照カウント = {}
    println!("a rc count after b creation = {}", Rc::strong_count(&a));
    // bの最初の参照カウント = {}
    println!("b initial rc count = {}", Rc::strong_count(&b));
    // bの次の要素 = {:?}
    println!("b next item = {:?}", b.tail());

```

変数`b`の初期化には、`a.clone()`ではなく`Rc::clone(&a)`を使うことで、ディープコピーでなく参照カウンタをインクリメントするようにしています。
aの参照カウンタが増えていることも確認できていますね。

#### aから参照されるコンスリストを(5, Nil)から(5, b)とする

```rust:main.rs
    if let Some(link) = a.tail() {
        *link.borrow_mut() = Rc::clone(&b);
    }

    // aを変更後のbの参照カウント = {}
    println!("b rc count after changing a = {}", Rc::strong_count(&b));
    // aを変更後のaの参照カウント = {}
    println!("a rc count after changing a = {}", Rc::strong_count(&a));

```

if let記法で一つのパターンにマッチする値を扱っています。
参考：　https://doc.rust-jp.rs/book-ja/ch06-03-if-let.html

[RefCell::borrow_mut](https://doc.rust-lang.org/std/cell/struct.RefCell.html#method.borrow_mut)で中の値への可変参照を借用しています。

これで循環参照ができました。


#### 循環参照によって起こるオーバーフローを確認する

```rust:main.rs
    // Uncomment the next line to see that we have a cycle;
    // it will overflow the stack
    // 次の行のコメントを外して循環していると確認してください; スタックオーバーフローします
    println!("a next item = {:?}", a.tail());        // aの次の要素 = {:?}

```
`a`と`b`の参照カウントは2となっており（それぞれ自身と`a`または`b`）、main関数の終端でコンパイラが`b`をドロップしようとカウントを1減らしても0にならないため、`b`が参照しているヒープ中のメモリがドロップされません。


## 参考

https://doc.rust-jp.rs/book-ja/ch15-06-reference-cycles.html
https://www.oreilly.co.jp/books/9784873119786/