参照サイクルはメモリリークを引き起こすことがある

Rust のメモリ安全性の保証のおかげで、誤って決してクリーンアップされないメモリ（メモリリーク として知られています）を作ってしまうことは簡単ではありませんが、不可能ではありません。メモリリークを完全に防ぐことは Rust の保証の 1 つではないため、Rust ではメモリリークはメモリ安全性を損ないません。Rc<T> と RefCell<T> を使うと、Rust がメモリリークを許容していることがわかります。要素同士がサイクル状に互いを参照する参照を作成できるのです。これによりメモリリークが発生します。なぜなら、サイクル内の各要素の参照カウントは決して 0 にならず、値が決してドロップされないからです。

参照サイクルを作成する

参照サイクルがどのように発生しうるのか、またそれをどう防ぐのかを見ていきましょう。まずは、リスト 15-25 にある List 列挙型の定義と tail メソッドから始めます。

use crate::List::{Cons, Nil};
use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
enum List {
    Cons(i32, RefCell<Rc<List>>),
    Nil,
}

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

fn main() {}

ここでは、リスト 15-5 にあった List 定義の別の変形を使っています。Cons バリアントの 2 番目の要素は今では RefCell<Rc<List>> になっており、これは、リスト 15-24 で行ったように i32 値を変更できるようにするのではなく、Cons バリアントが指している List 値を変更したいという意味です。また、値が Cons バリアントである場合に 2 番目の要素へ簡単にアクセスできるよう、tail メソッドも追加しています。

リスト 15-26 では、リスト 15-25 の定義を使う main 関数を追加しています。このコードは、a にリストを作成し、さらに a 内のリストを指すリストを b に作成します。その後、a 内のリストが b を指すように変更し、参照サイクルを作ります。途中には println! 文があり、この過程のさまざまな時点で参照カウントがどうなっているかを示しています。

use crate::List::{Cons, Nil};
use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
enum List {
    Cons(i32, RefCell<Rc<List>>),
    Nil,
}

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

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

    println!("a initial rc count = {}", Rc::strong_count(&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));
    println!("b initial rc count = {}", Rc::strong_count(&b));
    println!("b next item = {:?}", b.tail());

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

    println!("b rc count after changing a = {}", Rc::strong_count(&b));
    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());
}

まず、初期リスト 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! はコメントアウトしたままでこのコードを実行すると、次の出力が得られます。

$ cargo run
   Compiling cons-list v0.1.0 (file:///projects/cons-list)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.53s
     Running `target/debug/cons-list`
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 の末尾では、Rust は変数 b をドロップするので、b の Rc<List> インスタンスの参照カウントは 2 から 1 に減ります。Rc<List> がヒープ上に確保しているメモリは、この時点では参照カウントが 0 ではなく 1 なのでドロップされません。次に Rust は a をドロップし、a の Rc<List> インスタンスの参照カウントも 2 から 1 に減ります。このインスタンスのメモリも、もう一方の Rc<List> インスタンスがまだそれを参照しているため、やはりドロップできません。リストに割り当てられたメモリは永遠に回収されないままになります。この参照サイクルを視覚化したものが図15-4です。

図15-4: 互いを指すリスト a と b の参照サイクル

最後の println! のコメントを外してプログラムを実行すると、Rust は a が b を指し、b が a を指すという具合にこのサイクルを出力しようとして、最終的にスタックオーバーフローします。

現実のプログラムと比べれば、この例で参照サイクルを作成した結果はそれほど深刻ではありません。参照サイクルを作成した直後にプログラムが終了するからです。しかし、より複雑なプログラムがサイクル内に大量のメモリを確保し、それを長時間保持した場合、そのプログラムは必要以上のメモリを使い、システムを圧迫して、利用可能なメモリを使い果たしてしまうかもしれません。

参照サイクルを作るのは簡単ではありませんが、不可能でもありません。Rc<T> 値を含む RefCell<T> 値、あるいは内部可変性と参照カウントを持つ型の同様の入れ子の組み合わせがある場合は、サイクルを作らないよう自分で保証しなければなりません。Rust がそれを検出してくれると期待することはできません。参照サイクルを作ることはプログラム中のロジックバグであり、自動テスト、コードレビュー、そのほかのソフトウェア開発の実践を使って最小限に抑えるべきです。

参照サイクルを避ける別の解決策は、データ構造を再編成して、一部の参照は所有権を表し、一部の参照は所有権を表さないようにすることです。そうすると、いくつかの所有関係といくつかの非所有関係から成るサイクルを持つことができ、値をドロップできるかどうかに影響するのは所有関係だけになります。リスト 15-25 では、Cons バリアントには常に自分のリストを所有させたいので、データ構造を再編成することはできません。親ノードと子ノードからなるグラフを使った例を見て、所有権を伴わない関係が参照サイクルを防ぐのに適切な方法となるのはどのような場合かを確認しましょう。

Weak<T> を使って参照サイクルを防ぐ

ここまでは、Rc::clone を呼び出すと Rc<T> インスタンスの strong_count が増加し、Rc<T> インスタンスはその strong_count が 0 の場合にのみクリーンアップされることを示してきました。Rc::downgrade を呼び出して Rc<T> への参照を渡すことで、Rc<T> インスタンス内の値への弱参照を作成することもできます。強参照 は、Rc<T> インスタンスの所有権を共有するための仕組みです。弱参照 は所有関係を表さず、そのカウントは Rc<T> インスタンスがいつクリーンアップされるかに影響しません。弱参照は参照サイクルの原因になりません。なぜなら、一部に弱参照を含むサイクルは、関係する値の強参照カウントが 0 になれば壊れるからです。 Rc::downgrade を呼び出すと、Weak<T> 型のスマートポインタが得られます。 Rc<T> インスタンスの strong_count を 1 増やす代わりに、 Rc::downgrade を呼び出すと weak_count が 1 増えます。Rc<T> 型は strong_count と同様に、存在する Weak<T> 参照の数を追跡するために weak_count を使用します。違いは、Rc<T> インスタンスがクリーンアップされるために weak_count が 0 である必要はないという点です。

Weak<T> が参照している値はすでにドロップされている可能性があるため、 Weak<T> が指している値に対して何かを行うには、その値がまだ存在していることを 確認しなければなりません。これを行うには、Weak<T> インスタンスに対して upgrade メソッドを呼び出します。これにより Option<Rc<T>> が返されます。 Rc<T> の値がまだドロップされていなければ結果は Some になり、 Rc<T> の値がドロップされていれば結果は None になります。upgrade は Option<Rc<T>> を返すため、Rust は Some の場合と None の場合が処理されることを保証し、 無効なポインタは発生しません。

例として、各要素が次の要素しか知らないリストを使う代わりに、 各ノードが子ノード と 親ノードを把握している木を作成します。

ツリーデータ構造を作成する

まず、子ノードを把握しているノードを持つ木を構築します。 自身の i32 値と、その子である Node 値への参照を保持する、 Node という名前の構造体を作成します。

ファイル名: src/main.rs

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

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

Node にその子を所有させたい一方で、その所有権を変数と共有して、 木の中の各 Node に直接アクセスできるようにもしたいと考えています。これを実現するために、 Vec<T> の要素を Rc<Node> 型の値として定義します。また、どのノードが別のノードの子であるかを 変更できるようにしたいので、children では Vec<Rc<Node>> を RefCell<T> で包みます。

次に、この構造体定義を使って、値 3 と子を持たない leaf という名前の Node インスタンスを 1 つ作成し、さらに値 5 を持ち、leaf をその子の 1 つとして持つ branch という名前の別のインスタンスを作成します。これは リスト 15-27 に示されています。

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

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

leaf 内の Rc<Node> をクローンして branch に格納します。つまり、 leaf 内の Node には現在 2 つの所有者がいます: leaf と branch です。 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

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

#[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 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 では、 leaf ノードがその親である branch を参照できるように、 この新しい定義を使うよう main を更新しています。

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

#[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 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());
}

leaf ノードの作成は、parent フィールドを除けばリスト 15-27 と似ています。 leaf は最初は親を持たないため、新しい空の Weak<Node> 参照インスタンスを作成します。

この時点で、upgrade メソッドを使って leaf の親への参照を取得しようとすると、 None の値が得られます。これは最初の println! 文の出力で確認できます。

leaf parent = None

branch ノードを作成すると、その parent フィールドにも新しい Weak<Node> 参照が入ります。これは branch が親ノードを持たないためです。また、 leaf は引き続き branch の子の 1 つです。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 の変化を視覚化する

Rc<Node> インスタンスの strong_count と weak_count の値が どのように変化するかを、新しい内側のスコープを作成し、branch の作成を そのスコープ内に移すことで見てみましょう。そうすることで、branch が作成され、 スコープを抜けたときにドロップされると何が起こるのかを確認できます。 変更内容をリスト 15-29 に示します。

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

#[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 = {}, 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 = {}, 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),
    );
}

leaf が作成された後、その Rc<Node> の強参照カウントは 1、弱参照カウントは 0 です。内側のスコープでは、branch を作成してそれを leaf に関連付けます。この時点でカウントを出力すると、branch 内の Rc<Node> は強参照カウントが 1、弱参照カウントが 1 になります（leaf.parent が Weak<Node> で branch を指しているためです）。leaf のカウントを出力すると、branch.children に格納された leaf の Rc<Node> のクローンを branch が持つようになったため、強参照カウントが 2 になっていることがわかりますが、弱参照カウントは引き続き 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” を参照してください。

次は、Rust における並行性について話します。いくつかの新しいスマートポインタについても学ぶことになります。