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

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の保証の１つではない。それは、メモリーリークはメモリー安全であることを意味する。

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

循環参照の作成

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);
}

循環参照の作成。

f:id:yossan2:20210221170048p: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>>を包むchildrenをRefCell<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の値は、２つのオーナーが存在する。(leafとbranch)

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

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

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

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

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

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::cloneはstrong_countの値をインクリメントし、Rc<T>インスタンスは、strong_countが０になるまでドロップされない。

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

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

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

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

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

あるマのメモ書き

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

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

循環参照の作成

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

子供配列を持つノード

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

まとめ

参照