循環参照 - Rc<T>とRefCell<T>

循環参照はメモリーをリークする

Rustのメモリ安全保障において、メモリーリークを発生させることはとてつもなく難しい。

Preventing memory leaks entirely is not one of Rust's guarantees in the same way that disallowing data race at compile time is, meaning memory leaks are memory safe in Rust.

完全なるメモリーリークの予防は、コンパイル時間にデータ競合を許さないことと同じでRustの保証の1つではない。 それは、メモリーリークはメモリー安全であることを意味する。

Rc<T>RefCell<T>を使えば、サイクルにおいて互いに参照する参照を作りだすことができ、互いの参照カウントが永遠に0にならないため、メモリーリークを発生させることができる。

循環参照の作成

ConsListの定義。

#[derive(Debug)]
enum List {
    // RefCell<T>にすることによってtailの変更ができる
    Cons(i32, RefCell<Rc<List>>),
    Nil,
}

tailをRefCell<Rc<List>>にすることで、値の取替が行えるようにしている。

impl List {
    // tailの取り出し
    fn tail(&self) -> Option<&RefCell<Rc<List>>> {
        match self {
            Cons(_, item) => Some(item),
            Nil => None,
        }
    }
}

// tailの取り出し Option<&RefCell<Rc<List>>>
if let Some(link) = a.tail() {
    // RefCellの中身を変更
    *link.borrow_mut() = Rc::clone(&b);
}

循環参照の作成。

let a = Rc::new(Cons(5, RefCell::new(Rc::new(Nil))));
println!("a initial rc count = {}", Rc::strong_count(&a));              // 1 aの値は、aのみ参照
println!("a next item = {:?}", a.tail());                               

let b = Rc::new(Cons(10, RefCell::new(Rc::clone(&a))));
println!("a rc count after b creation = {}", Rc::strong_count(&a));     // 2 aの値は、aとbが参照
println!("b initial rc count = {}", Rc::strong_count(&b));              // 1 bの値は、bのみ参照
println!("b next item = {:?}", b.tail());

if let Some(link) = a.tail() {
    // aのお尻のNilをbに変更し、循環参照にする
    *link.borrow_mut() = Rc::clone(&b);
}

println!("b rc count after changing a = {}", Rc::strong_count(&b));     // 2 bの値は、aとbが参照
println!("a rc count after changing a = {}", Rc::strong_count(&a));     // 2 aの値は、aとbが参照

// 以下のコードを実行するとオーバーフローが発生する。
// println!("a next item = {:?}", a.tail());

循環参照の防止: RckらWeakに変更する

Rc::cloneを呼ぶことで、Rc<T>インスタンスstrong_countをインクリメントする。

子供配列を持つノード

f:id:yossan2:20210221170048p:plain

循環参照
f:id:yossan2:20210221170125p:plain

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct Node {
    value: i32,
    children: RefCell<Vec<Rc<Node>>> // Nodeへの所有権を共有する
}

Nodeへの所有権を共有するために、Rc<Node>型の配列を持つようにする。 また他の子供である各ノードを変更できるように、Vec<Rc<Node>>を包むchildrenRefCell<T>で持つようにする。

fn main() {
    // 葉 (辺を持たない)
    let leaf = Rc::new(Node { value: 3, children: RefCell::new(vec![]) });
    // 節 (辺を持つ)
    let branch = Rc::new(Node { value: 5, children: RefCell::new(vec![Rc::clone(&leaf)]) });

leafの値は、2つのオーナーが存在する。(leafbranch)

branchからleafを取得することはできるが、leafからbranchは取得することができないので、parentをもたせるようにする。

子供からその親への参照を追加する

parentへの参照をRc<T>型でもってしまうと、循環参照が発生する。

親ノードは、子供ノードへの所有権を持つべきであるとすると、 もし親ノードがドロップしたならば、全ての子供ノードも同様にドロップするべきと考えられる。 しかしながら、1つの子供ノードがドロップしたとしても親ノードをドロップさせるべきではない。

つまりこれは弱参照を使うためのケースである。

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Debug)]
struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,  // RefCellを挟むことで変更できるようにする
    children: RefCell<Vec<Rc<Node>>>,
}

ノードは、親への参照をもつが所有を持たない。

fn main() {
    let leaf = Rc::new(Node {
        value: 3,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![]),
    });

    // Weak::upgradeは、Option<Rc<T>>を返す
    println!("leaf parent = {:?}", leaf.parent.borrow().upgrade());

    let branch = Rc::new(Node {
        value: 5,
        parent: RefCell::new(Weak::new()),
        children: RefCell::new(vec![Rc::clone(&leaf)]),
    });

    // Rc::downgradeは、Weak<T>を返す
    *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

    println!("leaf parent = {:?}", leaf.parent.borrow().upgrade());
}

Rc::clonestrong_countの値をインクリメントし、Rc<T>インスタンスは、strong_countが0になるまでドロップされない。

そこで、Rc::downgradeを呼び、Rc<T>への参照を渡すことによって、Rc<T>インスタンスを内部に持つ値への弱参照を作ることも可能である。

Rc::downgrade関数を呼び出すと、Weak<T>インスタンス型のポインタを得ることができる。 strong_countの値をインクリメントする代わりに、Rc::downgradeは、weak_countをインクリメントする。

Rc<T>型はweak_countをトラックしつづけるが、strong_countとの違いは、0にならなくてもドロップすることができる。

強参照は、Rc<T>インスタンスの所有権を共有することができる方法である。 弱参照は、所有の関係を表すものではない。 これは循環参照を引き起こさない。なぜならば、弱参照を含んでいるいかなる循環は、強参照の値が0になったさいに破壊される。

Weak<T>インスタンスupgradeメソッドは、Option<Rc<T>>を返す。 もしRc<T>の値がドロップされていなければ、結果がSomeとなる。

leaf.parent.borrow()によって、RefCell<T>の値を借用し、Weak<Node>インスタンスを取得している。値がドロップしていなければ、upgradeメソッドで親ノードの取得が可能となる。

まとめ

  • Box<T>: ヒープ上に配置されたデータへのポインタとサイズの決定
  • Rc<T>: ヒープ上のデータへの参照カウンタによる複数所有者の実現
  • RefCell<T>: イミュータブルな型が必要であるが、その内部の値を変更する必要があるとき、またコンパイル時間ではなくランタイム時に借用ルールを強制するとき
  • Weak<T>: 循環参照を防止する

参照

doc.rust-lang.org