Rustの入門として、Reference Cycles Can Leak Memory（日本語版）のうち以下に示すコード(以下、本コード)をみていきます。
想定読者は、Rust初学者で特にTRPLを勉強中の方です。
私も勉強中の身なので、全く分かっていない部分が多くあります。誤っている箇所はご指摘ください。
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の次の要素 = {:?}
}
概要
このコードは循環参照によってメモリリークを引き起こし、最終的にスタックオーバーフローします。
メモリリークとはメモリが解放されない状態を指し、ガベージコレクション(GC)のない言語では意識しなければならない現象です。RustにGCはありませんが、所有権と借用やライフタイム1という仕組みによって独自のタイミングで自動的にメモリが解放されます(Rustではこれをドロップと呼びます)。しかし、本コードのように互いに参照するような値がある場合は、メモリリークを起こすことがあります。
スタックオーバーフローとは、スタック容量を超えてスタックを確保しようとすることです。Rustのデフォルトスタック容量は2～8MiBのようなので、例えば以下のコードで簡単に引き起こすことができます。
fn main() {
// aは1を1000万個もつ固定長配列
let a = [1; 10_000_000];
println!("{:?}", a);
}
thread 'main' has overflowed its stack
fatal runtime error: stack overflow
timeout: the monitored command dumped core
循環参照を作るため、本コードでは参照カウンタ方式のポインタと内部可変性を利用しています。
参照カウンタ方式のポインタとは、値の解放を参照カウンタによって決定するポインタです。python言語の変数代入に使用されるポインタが参照カウンタ方式で、自身への参照カウンタが0になったときに値が解放されます。つまり値が解放されないようにするには、参照カウントを1以上に保つ状況を作ればよいということになります。下図のa,bでは互いに参照するポインタを用意して、双方が互いの参照カウントを1以上に保っています。
(画像引用元：https://doc.rust-jp.rs/book-ja/ch15-06-reference-cycles.html)
一方で、Rustにおいては参照カウンタ方式のポインタ (Rcポインタ)で循環参照を作る上では一つ問題があります。それは、Rcポインタから参照されている値は不変でなければならない2ことです。循環参照を作る上では、以下の手順を踏むことになりますが、手順3で値を変更できないということになります。
準備: 再帰的な型(コンスリスト; 後述)を作ります
- コンスリスト(5, Nil)へのRcポインタをaする
- コンスリスト(10, a)へのRcポインタをbとする
- aから参照されるコンスリストを(5, Nil)から(5, b)とする
この問題を解消するため、一部の値のみ可変となるようにコンパイラへ指示します(内部可変性3)。これで構造体のフィールドを可変にせずとも可変参照を作ることできるため、上図のような循環参照をつくることができます。
詳細
使用している列挙型について
#[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を定義しています。
enum List {
Cons(i32, List),
Nil,
}
(画像引用元：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
次の要素を取得する
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を返します。
match式について
match式はパターンマッチを行い、Rustで多用されています。
例えばOption<T>から中身のT値を取得するunwrapメソッドではmatch式が実装されています。
もちろん、match式を書いて明示的に指定することもできます。
#![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の場合を書き損じると丁寧に教えてくれます。
error[E0004]: non-exhaustive patterns: `None` not covered
(エラー: 包括的でないパターン: `None`がカバーされてません)
-->
|
6 | match x {
| ^ pattern `None` not covered
メソッドは第一引数に必ず、メソッドを呼び出す主体を意味するselfを与えなければなりません。
サンプルコード
（下の例でm.call()メソッドのselfにはmの値が入る）
参考： https://doc.rust-jp.rs/book-ja/ch06-01-defining-an-enum.html
#![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(不変参照)であることから、このメソッドは呼び出し元の変更を伴わないことが実装をみなくてもわかったりします。
Option<T>列挙子は標準ライブラリに定義された列挙型であるため、use宣言は不要です。
Option型について
#![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
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とする
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で参照カウント数を確認できます。
コンスリスト(10, a)へのRcポインタをbとする
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)とする
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で中の値への可変参照を借用しています。
これで循環参照ができました。
循環参照によって起こるオーバーフローを確認する
// 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/