循環参照は、メモリをリークすることもある

Rustのメモリ安全保証により誤って絶対に片付けられることのないメモリ(メモリリークとして知られています)を生成してしまいにくくなりますが、不可能にはなりません。コンパイル時にデータ競合を防ぐのと同じようにメモリリークを完全に回避することは、 Rustの保証の一つではなく、メモリリークはRustにおいてはメモリ安全であることを意味します。 Rustでは、Rc<T>とRefCell<T>を使用してメモリリークを許可するとわかります: 要素がお互いに循環して参照する参照を生成することも可能ということです。循環の各要素の参照カウントが絶対に0にならないので、これはメモリリークを起こし、値は絶対にドロップされません。

循環参照させる

リスト15-25のList enumの定義とtailメソッドから始めて、どう循環参照が起こる可能性があるのかとその回避策を見ましょう:

ファイル名: src/main.rs

fn main() {}
use std::rc::Rc;
use std::cell::RefCell;
use List::{Cons, Nil};

#[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,
        }
    }
}

リスト15-25: Cons列挙子が参照しているものを変更できるようにRefCell<T>を抱えているコンスリストの定義

リスト15-5のList定義の別バリエーションを使用しています。Cons列挙子の2番目の要素はこれでRefCell<Rc<List>>になり、リスト15-24のようにi32値を変更する能力があるのではなく、Cons列挙子が指しているList値の先を変えたいということです。また、tailメソッドを追加してCons列挙子があるときに2番目の要素にアクセスするのが便利になるようにしています。

リスト15-26でリスト15-25の定義を使用するmain関数を追加しています。このコードは、aにリストを、 bにaのリストを指すリストを作成します。それからaのリストを変更してbを指し、循環参照させます。その流れの中に過程のいろんな場所での参照カウントを示すprintln!文が存在しています。

ファイル名: src/main.rs

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の次の要素 = {:?}
}

リスト15-26: 2つのList値がお互いを指して循環参照する

最初のリストが5, NilのList値を保持するRc<List>インスタンスを変数aに生成します。そして、値10とaのリストを指す別のList値を保持するRc<List>インスタンスを変数bに生成します。

aがNilではなくbを指すように変更して、循環させます。tailメソッドを使用して、 aのRefCell<Rc<List>>への参照を得ることで循環させて、この参照は変数linkに配置します。それからRefCell<Rc<List>>のborrow_mutメソッドを使用して中の値をNil値を持つRc<List>から、 bのRc<List>に変更します。

最後のprintln!を今だけコメントアウトしたまま、このコードを実行すると、こんな出力が得られます:

a initial rc count = 1
a next item = Some(RefCell { value: Nil })
a rc count after b creation = 2
b initial rc count = 1
b next item = Some(RefCell { value: Cons(5, RefCell { value: Nil }) })
b rc count after changing a = 2
a rc count after changing a = 2

aのリストをbを指すように変更した後のaとbのRc<List>インスタンスの参照カウントは2です。 mainの終端で、コンパイラはまずbをドロップしようとし、aとbの各Rc<List>インスタンスのカウントを1減らします。

しかしながら、それでもaはbにあったRc<List>を参照しているので、そのRc<List>のカウントは0ではなく1になり、そのRc<List>がヒープに確保していたメモリはドロップされません。メモリはただ、カウント1のままそこに永遠に居座るのです。この循環参照を可視化するために、図15-4に図式を作成しました:

図15-4: お互いを指すリストaとbの循環参照

最後のprintln!のコメントを外してプログラムを実行したら、aがbを指して、bがaを指してと、スタックがオーバーフローするまでコンパイラはこの循環を出力しようとするでしょう。

この場合、循環参照を作る直後にプログラムは終了します。この循環の結果は、それほど悲壮なものではありません。しかしながら、より複雑なプログラムが多くのメモリを循環で確保し長い間その状態を保ったら、プログラムは必要以上のメモリを使用し、使用可能なメモリを枯渇させてシステムを参らせてしまう可能性があります。

循環参照は簡単にできることではありませんが、不可能というわけでもありません。 Rc<T>値を含むRefCell<T>値があるなどの内部可変性と参照カウントのある型がネストして組み合わさっていたら、循環していないことを保証しなければなりません; コンパイラがそれを捕捉することを信頼できないのです。循環参照をするのは、自動テストやコードレビューなどの他のソフトウェア開発手段を使用して最小化すべきプログラム上のロジックバグでしょう。

循環参照を回避する別の解決策は、ある参照は所有権を表現して他の参照はしないというようにデータ構造を再構成することです。結果として、所有権のある関係と所有権のない関係からなる循環ができ、所有権のある関係だけが、値がドロップされうるかどうかに影響します。リスト15-25では、常にCons列挙子にリストを所有してほしいので、データ構造を再構成することはできません。親ノードと子ノードからなるグラフを使った例に目を向けて、どんな時に所有権のない関係が循環参照を回避するのに適切な方法になるか確認しましょう。

循環参照を回避する: `Rc<T>`を`Weak<T>`に変換する

ここまで、Rc::cloneを呼び出すとRc<T>インスタンスのstrong_countが増えることと、 strong_countが0になった時にRc<T>インスタンスは片付けられることをデモしてきました。 Rc::downgradeを呼び出し、Rc<T>への参照を渡すことで、Rc<T>インスタンス内部の値への弱い参照(weak reference)を作ることもできます。 Rc::downgradeを呼び出すと、型Weak<T>のスマートポインタが得られます。 Rc<T>インスタンスのstrong_countを1増やす代わりに、Rc::downgradeを呼び出すと、weak_countが1増えます。 strong_count同様、Rc<T>型はweak_countを使用して、幾つのWeak<T>参照が存在しているかを追跡します。違いは、Rc<T>が片付けられるのに、weak_countが0である必要はないということです。

強い参照は、Rc<T>インスタンスの所有権を共有する方法です。弱い参照は、所有権関係を表現しません。ひとたび、関係する値の強い参照カウントが0になれば、弱い参照が関わる循環はなんでも破壊されるので、循環参照にはなりません。

Weak<T>が参照する値はドロップされてしまっている可能性があるので、Weak<T>が指す値に何かをするには、値がまだ存在することを確認しなければなりません。Weak<T>のupgradeメソッドを呼び出すことでこれをしてください。このメソッドはOption<Rc<T>>を返します。Rc<T>値がまだドロップされていなければ、Someの結果が、 Rc<T>値がドロップ済みなら、Noneの結果が得られます。upgradeがOption<T>を返すので、コンパイラは、SomeケースとNoneケースが扱われていることを確かめてくれ、無効なポインタは存在しません。

例として、要素が次の要素を知っているだけのリストを使うのではなく、要素が子要素と親要素を知っている木を作りましょう。

木データ構造を作る: 子ノードのある`Node`

手始めに子ノードを知っているノードのある木を構成します。独自のi32値と子供のNode値への参照を抱えるNodeという構造体を作ります:

ファイル名: src/main.rs


#![allow(unused)]
fn main() {
use std::rc::Rc;
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    value: i32,
    children: RefCell<Vec<Rc<Node>>>,
}
}

Nodeに子供を所有してほしく、木の各Nodeに直接アクセスできるよう、その所有権を変数と共有したいです。こうするために、Vec<T>要素を型Rc<Node>の値になるよう定義しています。どのノードが他のノードの子供になるかも変更したいので、 Vec<Rc<Node>>の周りのchildrenをRefCell<T>にしています。

次にこの構造体定義を使って値3と子供なしのleafという1つのNodeインスタンスと、値5とleafを子要素の一つとして持つbranchという別のインスタンスを作成します。リスト15-27のようにですね:

ファイル名: src/main.rs

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

#[derive(Debug)]
struct Node {
    value: i32,
   children: RefCell<Vec<Rc<Node>>>,
}

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

リスト15-27: 子供なしのleafノードとleafを子要素に持つbranchノードを作る

leafのRc<Node>をクローンし、branchに格納しているので、leafのNodeはleafとbranchという2つの所有者を持つことになります。 branch.childrenを通してbranchからleafへ辿ることはできるものの、leafからbranchへ辿る方法はありません。理由は、leafにはbranchへの参照がなく、関係していることを知らないからです。leafにbranchが親であることを知ってほしいです。次はそれを行います。

子供から親に参照を追加する

子供に親の存在を気付かせるために、Node構造体定義にparentフィールドを追加する必要があります。 parentの型を決める際に困ったことになります。Rc<T>を含むことができないのはわかります。そうしたら、leaf.parentがbranchを指し、branch.childrenがleafを指して循環参照になり、 strong_count値が絶対に0にならなくなってしまうからです。

この関係を別の方法で捉えると、親ノードは子供を所有すべきです: 親ノードがドロップされたら、子ノードもドロップされるべきなのです。ですが、子供は親を所有するべきではありません: 子ノードをドロップしても、親はまだ存在するべきです。弱い参照を使う場面ですね！

従って、Rc<T>の代わりにparentの型をWeak<T>を使ったもの、具体的にはRefCell<Weak<Node>>にします。さあ、Node構造体定義はこんな見た目になりました:

ファイル名: src/main.rs


#![allow(unused)]
fn main() {
use std::rc::{Rc, Weak};
use std::cell::RefCell;

#[derive(Debug)]
struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}
}

ノードは親ノードを参照できるものの、所有はしないでしょう。リスト15-28で、 leafノードが親のbranchを参照できるよう、この新しい定義を使用するようにmainを更新します:

ファイル名: src/main.rs

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

#[derive(Debug)]
struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

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

    // leafの親 = {:?}
    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)]),
    });

    *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

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

リスト15-28: 親ノードのbranchへの弱い参照があるleafノード

leafノードを作成することは、parentフィールドの例外を除いてリスト15-27でのleafノードの作成法の見た目に似ています: leafは親なしで始まるので、新しく空のWeak<Node>参照インスタンスを作ります。

この時点でupgradeメソッドを使用してleafの親への参照を得ようとすると、None値になります。このことは、最初のprintln!文の出力でわかります:

leaf parent = None

branchノードを作る際、branchには親ノードがないので、こちらもparentフィールドには新しいWeak<Node>参照が入ります。それでも、leafはbranchの子供になっています。一旦branchにNodeインスタンスができたら、 leafを変更して親へのWeak<Node>参照を与えることができます。leafのparentフィールドには、 RefCell<Weak<Node>>のborrow_mutメソッドを使用して、それからRc::downgrade関数を使用して、 branchのRc<Node>からbranchへのWeak<Node>参照を作ります。

再度leafの親を出力すると、今度はbranchを保持するSome列挙子が得られます: これでleafが親にアクセスできるようになったのです！ leafを出力すると、リスト15-26で起こっていたような最終的にスタックオーバーフローに行き着く循環を避けることもできます; Weak<Node>参照は、(Weak)と出力されます:

leaf parent = Some(Node { value: 5, parent: RefCell { value: (Weak) },
children: RefCell { value: [Node { value: 3, parent: RefCell { value: (Weak) },
children: RefCell { value: [] } }] } })

無限の出力が欠けているということは、このコードは循環参照しないことを示唆します。このことは、Rc::strong_countとRc::weak_countを呼び出すことで得られる値を見てもわかります。

`strong_count`と`weak_count`への変更を可視化する

新しい内部スコープを作り、branchの作成をそのスコープに移動することで、 Rc<Node>インスタンスのstrong_countとweak_count値がどう変化するかを眺めましょう。そうすることで、branchが作成され、それからスコープを抜けてドロップされる時に起こることが確認できます。変更は、リスト15-29に示してあります:

ファイル名: src/main.rs

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

#[derive(Debug)]
struct Node {
    value: i32,
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

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

    println!(
        // leafのstrong_count = {}, weak_count = {}
        "leaf strong = {}, weak = {}",
        Rc::strong_count(&leaf),
        Rc::weak_count(&leaf),
    );

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

        *leaf.parent.borrow_mut() = Rc::downgrade(&branch);

        println!(
            // branchのstrong_count = {}, weak_count = {}
            "branch strong = {}, weak = {}",
            Rc::strong_count(&branch),
            Rc::weak_count(&branch),
        );

        println!(
            "leaf strong = {}, weak = {}",
            Rc::strong_count(&leaf),
            Rc::weak_count(&leaf),
        );
    }

    println!("leaf parent = {:?}", leaf.parent.borrow().upgrade());
    println!(
        "leaf strong = {}, weak = {}",
        Rc::strong_count(&leaf),
        Rc::weak_count(&leaf),
    );
}

リスト15-29: 内側のスコープでbranchを作成し、強弱参照カウントを調査する

leaf作成後、そのRc<Node>の強カウントは1、弱カウントは0になります。内側のスコープでbranchを作成し、 leafに紐付け、この時点でカウントを出力すると、branchのRc<Node>の強カウントは1、弱カウントも1になります(leaf.parentがWeak<Node>でbranchを指しているため)。 leafのカウントを出力すると、強カウントが2になっていることがわかります。branchが今は、 branch.childrenに格納されたleafのRc<Node>のクローンを持っているからですが、それでも弱カウントは0でしょう。

内側のスコープが終わると、branchはスコープを抜け、Rc<Node>の強カウントは0に減るので、このNodeはドロップされます。leaf.parentからの弱カウント1は、Nodeがドロップされるか否かには関係ないので、メモリリークはしないのです！

このスコープの終端以後にleafの親にアクセスしようとしたら、再びNoneが得られます。プログラムの終端でleafのRc<Node>の強カウントは1、弱カウントは0です。変数leafが今ではRc<Node>への唯一の参照に再度なったからです。

カウントや値のドロップを管理するロジックは全て、Rc<T>やWeak<T>とそのDropトレイトの実装に組み込まれています。 Nodeの定義で子供から親への関係はWeak<T>参照になるべきと指定することで、循環参照やメモリリークを引き起こさずに親ノードに子ノードを参照させたり、その逆を行うことができます。

まとめ

この章は、スマートポインタを使用してRustが既定で普通の参照に対して行うのと異なる保証や代償を行う方法を講義しました。 Box<T>型は、既知のサイズで、ヒープに確保されたデータを指します。Rc<T>型は、ヒープのデータへの参照の数を追跡するので、データは複数の所有者を保有できます。内部可変性のあるRefCell<T>型は、不変型が必要だけれども、その型の中の値を変更する必要がある時に使用できる型を与えてくれます; また、コンパイル時ではなく実行時に借用規則を強制します。

DerefとDropトレイトについても議論しましたね。これらは、スマートポインタの多くの機能を可能にしてくれます。メモリリークを引き起こす循環参照とWeak<T>でそれを回避する方法も探究しました。

この章で興味をそそられ、独自のスマートポインタを実装したくなったら、もっと役に立つ情報を求めて、 “The Rustonomicon”をチェックしてください。

訳注: 日本語版のThe Rustonomiconはこちらです。

次は、Rustでの並行性について語ります。もういくつか新しいスマートポインタについてさえも学ぶでしょう。

関連キーワード: 　Rc, leaf, Node, RefCell, count, 参照, Weak, リスト, List, new

The Rust Programming Language 日本語版