C++プログラマー向けRust 翻訳シリーズ11

グラフとアリーナ型メモリアロケータ

(注: この章の例は、このディレクトリをダウンロードしてcargo runコマンドを入力すると、実際に動かすことができる)

グラフ構造は、Rustにおいて非常に厳密なライフタイム管理と可変性管理があるため、いささか構築がめんどくさい。ただオブジェクト指向プログラミングにおいて、オブジェクトのグラフ構造は、非常によく使われるものである。
このチュートリアルでは、グラフ構造の実装方法を数種類提示していこうと思う。個人的には、アリーナ型メモリアロケータを使用し、多少ライフタイムの明示を駆使する方法が好みだ。また最後に、今後Rustに導入されそうな機能のうち、ここで紹介する実装方法の簡略化を行ってくれそうなものについて議論して締めたいと思う。

グラフ構造は、一連のノードとそのノード間を結ぶエッジで構成され、リストや木構造を一般化したものと言える。各ノードは、複数の子や親を持つことがある(尤も、グラフ理論では親子とは呼ばずに、内向・外向という)。
グラフ構造は、隣接するリストや行列で表すことができる。前者は、根本的にはグラフのノードを表すオブジェクトがあり、そのオブジェクトが隣接するノードのリストを持つものである。一方、行列で表す場合は、行ノードから列ノードへの辺があるかどうかを表す論理値の行列を使う。
ここでは、隣接リスト方式での実装方法のみ解説する。隣接行列方式は、Rust固有とは言い難い全く別の問題を抱えているのだ。

本質的には、二種の直交する問題が存在する。どうやってグラフ全体のライフタイムを管理するかと、どうやってその可変性を管理するかだ。

一つ目の問題は、究極的には、グラフ内の他のノードを指し示すのにどんなポインタを使うかという問題に帰着する。グラフ様のデータ構造は、再帰的であるため(たとえ、データはそうでなくとも、型自体が再帰的になる)、完全に値だけでグラフ構造を構築することはできず、何らかのポインタを使わざるをえなくなる。
グラフ構造は再帰的になりうるが、Rustの所有権は再帰的にはできないため、Box<Node>型を使用することはできない(ただ、擬似木構造のデータや連結リストには使用できるけど)。

いかなるグラフも真の意味で、不変たりえない。どこかで円環状になる可能性があるため、一文でグラフを構築することはできないからだ。ゆえに、最低限でも、初期化処理中はグラフを可変にする必要がある。
Rustにおいて、通常、ポインタはすべて固有か不変でなければならないというのは、普遍の真理である。グラフの辺は、(少なくとも初期化中は)可変でなければならず、いかなるノードにも内向する辺が２つ以上存在する可能性がある以上、辺の固有性を保証することはできない。したがって、何かしら幾分高度なことをして、可変性を扱わねばならないわけだ。

解決策の一つとして、可変生ポインタ(*mut Node)を使うことが挙げられる。これは、最も柔軟性の高い手段だが、同時に最も危険でもある。
ライフタイム管理は、型システムのサポートなしにすべて自分で行わなければならない。こうすれば、非常に柔軟で効率的なデータ構造を構築できるが、同時に慎重にならねばならない。
この方法ならば、先ほどのライフタイムと可変性問題は一掃できる。しかし、それは結局、Rustの利点をすべて無視することで得られるものである。つまり、コンパイラの支援を受けることはできない(また、生ポインタは、自動(被)参照しないため、特別人間に優しくない)。生ポインタを使ったグラフ構造は、C++のものと大して相違ないので、ここでは解説しない。

ライフタイム管理には参照カウント(共有所有権、Rc<...>を使用)かアリーナ型メモリアロケータ(全ノードがアリーナに管理された同じライフタイムを持つ、無所有権参照&...を使用)を使用するという選択肢がある。前者の方がより柔軟(あらゆるライフタイムを持つ個々のノードを外部から参照することができる)であるが、後者の方はそれ以外のあらゆる点で勝っている。

可変性管理について、RefCellクラスを使用してRustの動的な内部可変性機構を援用するか、可変性を自ら管理することができる(この場合、UnsafeCellクラスを使用して内部可変性をコンパイラとやりとりせねばならない)。前者の方が安全、後者はより効率的、両者ともプログラマーフレンドリーではない。

なお、円環状になっている可能性のあるグラフがあるのに、Rcクラスを使用している場合、さらなるアクションを行って再帰構造を破り、メモリリークを避ける必要がある。Rustには、Rcポインタを再帰的に保持できるコレクションがないため、グラフ内に再帰構造がある場合、参照カウントが0にならず、グラフは解放されなくなる。
グラフ内にWeakポインタを使用するか、グラフ破棄の時期に再帰構造を手動で破ることで解決できる。前者の方が信頼性が高い。ここでは、どちらも解説しない。例では、単にメモリリークさせる。
無所有権参照とアリーナ型メモリアロケータを使用したアプローチならば、このような問題はないため、その点で優れている。

アプローチの比較のため、例は非常にシンプルに保つ。グラフ内の一ノードを表すNodeオブジェクトに、文字列データ(より複雑なデータの代わり)と隣接ノード(edges)のVecを持たせる。複数ノードを持つシンプルなグラフを作成するinit関数と事前順序付け深さ優先探索を行うtraverse関数を定義する。traverse関数で各ノードのデータを表示する。
最後に、selfが表すノードの最初に隣接したノードへの参照を返すNode::firstメソッドとノードの持つデータを表示するfoo関数を定義する。これらの関数を介してグラフ内部のより複雑なノード操作を行う。

平易になりすぎずになるべく情報量を詰め込めるよう、可能な組み合わせのうち2通りを解説する。参照カウントとRefCellクラスを使用するものと、アリーナ型メモリアロケータとUnsafeCellクラスを使用するものだ。他の2通りの組み合わせは、学習用に残しておく。

Rc<RefCell<Node>>

完全な例はこちら。

unsafeコードがないので、こちらの方が安全な選択肢である。また、最も非効率的で人間工学的でもない。ただ、非常に柔軟ではある。ノードが参照カウントされているため、グラフ外での再利用も利くからね。完全に可変なグラフが必要だったり、グラフ自体の存在にかかわらず、ノードが必要な場合は、こちらの手段を取るといいだろう。

ノードは以下のような構造をしている。

struct Node {
    datum: &'static str,
    edges: Vec<Rc<RefCell<Node>>>,
}

新規ノードを作るのは、さほどめんどくさくない。Rc::new(RefCell::new(Node { ... }))と書けばいい。初期化時に辺を追加するには、先頭ノードを可変無所有権参照し、終端ノードをクローン(こうすると、ポインタをコピーし、参照カウントを1増やす。ノード自体はコピーしない)して辺のベクターコンテナに追加する。

let mut mut_root = root.borrow_mut();
mut_root.edges.push(b.clone());

RefCellクラスを使うことで、書き込み時にノードが読み書き中ではないことが動的に保証される。

ノードへのアクセスは、必ず.borrow()メソッドを使用してRefCellクラスを無所有権参照しなければならない。firstメソッドは、無所有権参照ではなく、参照カウント式ポインタを返す必要がある。従って、firstメソッドの呼び出し元でも、無所有権参照せねばならない。

fn first(&self) -> Rc<RefCell<Node>> {
    self.edges[0].clone()
}

pub fn main() {
    let g = ...;
    let f = g.first();
    foo(&*f.borrow());
}

&NodeとUnsafeCell

完全な例はこちら。

このアプローチでは、辺に無所有権参照を用いる。これは素晴らしく人間工学的だ。こうすれば、主に無所有権参照(なお、Rustの参照カウント式オブジェクトの素晴らしい点は、ライフタイムシステムによく馴染むことにある。Rcクラスへの無所有権参照を作成して、直接かつ安全にデータを参照することができる。先ほどの例において、RefCellクラスのせいでこのようなことはできなかったが、RcかUnsafeCellクラスならば可能なはずだ)を対象とするRustの標準的なライブラリを、ノードに対して援用することができるようになるのだ。

また、破棄も正常に行われる。唯一の制約は、全ノードが同時に破棄されなければいけないことだけである。ノードの破棄および、確保は、アリーナで行われる。

他方、わずかではあるが、ライフタイムを明示しなければいけない。残念ながら、ここでライフタイム省略記法の恩恵にあずかることはできない。この節の末尾で、このような事態を改善する言語の進化の方向性を探っていく。

構築フェーズでは、複数参照される可能性のあるノードを可変化するだろう。このようなことは、通常のRustコード内では不可能なので、unsafeブロック内で初期化しなければならない。ノードが可変かつ複数参照されているので、UnsafeCellクラスを使用して通常の不変性原則に依存しないことを、Rustコンパイラに通知するのだ。

では、いつこのアプローチは現実的になるのだろうか？
グラフは、初期化時のみ可変である必要がある。加えて、グラフ内の全ノードは同じライフタイムである必要がある(同時に破棄することが可能であれば、この制約を緩めて後々ノードを追加するようにもできる)。
同様に、ノードを可変化できる時期について、より複雑な不変性原則に依存することもできるが、実装を単純には保てなくなる。プログラマーがそれらの安全について面倒を見なければいけなくなるからね。

アリーナ型メモリアロケーションは、メモリ管理法の一種であり、一まとまりのオブジェクトが同じライフタイムを持ち、同時に解放される。
アリーナとは、メモリ確保と解放を司るオブジェクトである。(個々のオブジェクトごとにメモリ確保するのではなく)ひとくくりに巨大なメモリ領域が確保されたり、解放されたりするため、アリーナのメモリ確保は非常に効率的だ。
通常、オブジェクトはすべて連続したメモリ領域に確保される。そうすれば、グラフを辿る際のキャッシュ利用効率が上がる。

Rustにおいて、アリーナ型メモリアロケーションは、libarenaでサポートされ、コンパイラ全体で活用されている。アリーナには二種類ある。型付けアリーナと型なしアリーナだ。
前者の方が、効率的で使いやすいが、ある型のオブジェクトしか確保できない一方で、後者ならば、より柔軟でどんなオブジェクトでも確保することができる。
アリーナで確保されたオブジェクトは、すべて同じライフタイムであり、このライフタイムはアリーナオブジェクトのパラメータになる。型システムにより、アリーナにより確保されたオブジェクトへの参照が、アリーナ自体よりも長く生き残り続けないことを保証してくれる。

さて、ノード構造体にグラフのライフタイム('a)を含める必要が出た。隣接ノードのVecコンテナをUnsafeCellクラスで包んで、不変であるはずのVecコンテナを可変化できるようにする。

struct Node<'a> {
    datum: &'static str,
    edges: UnsafeCell<Vec<&'a Node<'a>>>,
}

new関数もこのライフタイムを使用し、メモリ確保を行うアリーナオブジェクトを引数に取らなければならない。

fn new<'a>(datum: &'static str, arena: &'a TypedArena<Node<'a>>) -> &'a Node<'a> {
    arena.alloc(Node {
        datum: datum,
        edges: UnsafeCell::new(Vec::new()),
    })
}

アリーナオブジェクトを使ってノードオブジェクトのメモリ確保を行っている。グラフのライフタイムは、アリーナオブジェクトへの参照から派生している。そのため、アリーナオブジェクトは、グラフのライフタイムを包括するスコープから渡す必要がある。今回の例で言えば、initメソッドに渡すことを意味する。(表記上のスコープ外で値を生成できるように型システムを拡張することが考えられるが、今すぐ実装の予定はない)。
アリーナオブジェクトがスコープ外に抜ければ、グラフ全体も破棄される(Rustの型システムにより、この時点以降までグラフへの参照が残らないことが保証される)。

辺の追加方法は少し趣が異なる。

(*root.edges.get()).push(b);

本質的には、root.edges.push(b)を呼び出してノード(b)を辺のリストに追加しているだけである。とはいえ、edgesフィールドがUnsafeCellクラスに包まれているため、get()を呼んであげる必要がある。こうすると、辺への可変生ポインタ(*mut Vec<&Node>)が得られ、edgesフィールドを可変化することができる。ところが、これはこのポインタを手動で被参照しなければいけないこと(生ポインタは自動被参照できない)でもあり、(*...)と書いているのだ。
最後に、生ポインタの被参照は非安全なので、全体をunsafeブロックに入れ込む必要がある。

traverse関数の気になる箇所は以下の通りだ。

for n in &(*self.edges.get()) {
    n.traverse(f, seen);
}

辺のリストを取得するのに先ほどと同じ手順を踏んでいるため、unsafeブロックが必要になる。この場合、実際には安全である。なぜなら、すでに初期化は完了しており、可変化処理がないからだ。

さて、firstメソッドも辺リストを取得する手順は同じであり、unsafeブロックが必要になる。ただ、Rc<RefCell<_>>を使用したグラフとは対照的に、ノードへの単純な無所有権参照を返せばいい。とても便利だ。どこにも可変化処理がなく、初期化済みのため、このunsafeブロックは安全だと推論できる。

fn first(&'a self) -> &'a Node<'a> {
    unsafe {
        (*self.edges.get())[0]
    }
}

このアプローチに対する将来的な言語の改善点

Rustにおいて、アリーナ型メモリアロケーションと無所有権参照の使用は、重要なパターンと考えられる。言語に改良を施して、これらのパターンをより安全に使いやすくするべきだ。アリーナの使用がメモリアロケータに対する現在進行中の改良によって、よりプログラマーフレンドリーになることを願っている。
その他、著者が把握している改良点は3つある。

安全な初期化処理

オブジェクト指向の世界では、初期化時のみ可変性を保つ機構に関して多数の調査が行われてきた。一体、この機構がRustでいかように作動するかは、未解決な疑問だが、可変ではあるが固有ではなく、スコープに閉じられたポインタを示す必要があるということのようだ。そのスコープ外では、既存のポインタはいかなるものであっても、通常の無所有権参照、つまり、不変か、固有になるのだ。

そのような機構の利点は、初期化時は可変で、それから不変になる一般的なパターンを示す手段ができることにある。また、これは、個々のオブジェクト自体は、複数所有されているものの、その集合全体(今は、グラフ)は単一所有されているという普遍的原則にも依存している。
こうすれば、UnsafeCellクラスとunsafeブロックの必要なく、参照とUnsafeCellクラスを使用するアプローチを適用することができるようになり、この手段がよりプログラマーフレンドリーかつ安全なものになる。

ETH Zurich(訳注: 大学名か何か？)のAlex SummersとJulian Viereckが、これを追求している。

汎用的なモジュール

グラフのライフタイムは、いかなるグラフでも定数になる。ライフタイムを繰り返し記述するのは、冗長でしかない。
これをプログラマーフレンドリーにする一手段は、グラフのモジュールにライフタイムのパラメータを持たせられるようにすることだ。そうすれば、struct、impl、関数ごとに記述する必要がなくなる。
それでも、グラフのライフタイムは、モジュール外から指定する必要があるが、たいていの場合、推論でなんとかなる(今日、関数呼び出しではできている)と好ましい。

モジュールがどんな見た目になるかは、ref_graph_generic_mod.rsを参照されたし。((上記で確約されている)安全初期化処理を援用してunsafeコードを排除することもできるはずだ)

また、このRFC issueも参照されたし。

この機能によって、参照とUnsafeCellクラスアプローチのコードの重複箇所が大幅に削減されるだろう。

ライフタイム省略

現時点で、プログラマーは関数定義のライフタイムを一部省略してプログラマーフレンドリーにすることができる。グラフに対して&Node型を使用するアプローチが、いささか見目麗しくない理由の一つは、ライフタイム省略記法を使用していないからだ。

Rustにおいてよく使われるイディオムに共通ライフタイムを持つデータ構造がある。そのようなデータ構造への参照は、&'a Foo<'a>のような型を立てる。具体例: グラフの例では&'a Node<'a>。
このようなケースに役に立つ省略記法があると便利だが、どんな挙動をすべきかは確信が持てない。

汎用モジュールの例を見ると、さほどライフタイム省略記法を拡張する必要はないようだ(Node::newメソッドがライフタイムを与えられなくても動作するか皆目見当がつかないが、仮にそうであっても、ほんの些細な拡張を施すだけで、動作するようになるだろう)。
スコープ内で唯一のときは、モジュール全体で('static以外の)ライフタイムを省略できる何らかの新しいルールを追加したくなるかもしれないが、スコープ内に複数のライフタイムがある場合(fooとinit関数を参照)の挙動が読めない。

汎用モジュールを追加しなくても、&'a Node<'a>という書き方に特化した省略記法を導入する可能性はある。まあ、どう実装するのかは知ったこっちゃないけど。


原文: https://github.com/nrc/r4cppp/blob/master/graphs/README.md