Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

グラフとアリーナ割り当て

（この章の例は、このディレクトリをダウンロードして cargo run を実行することで動かせます）。

Rust では、ライフタイムと可変性に関する厳格な要件があるため、グラフを構築するのは少し扱いにくいです。オブジェクトのグラフは、OO プログラミングでは非常に一般的です。このチュートリアルでは、実装に対するいくつかの異なるアプローチを見ていきます。私が好むアプローチでは、アリーナ割り当てを使い、明示的なライフタイムをやや高度に利用します。最後に、このようなアプローチをより使いやすくする可能性のある Rust の機能についていくつか議論します。

グラフは、いくつかのノード間にエッジを持つノードの集合です。グラフはリストや木を一般化したものです。各ノードは複数の子と複数の親を持つことができます（通常は親/子というより、ノードに入るエッジとノードから出るエッジについて話します）。グラフは隣接リストまたは隣接行列で表現できます。前者は基本的に、グラフ内の各ノードに対するノードオブジェクトであり、各ノードオブジェクトが隣接ノードのリストを保持します。隣接行列は、行のノードから列のノードへのエッジが存在するかどうかを示す真偽値の行列です。ここでは隣接リスト表現のみを扱います。隣接行列には、Rust 固有性が比較的低い、まったく異なる問題があります。

本質的には、直交する 2 つの問題があります。グラフのライフタイムをどう扱うか、そしてその可変性をどう扱うかです。

最初の問題は、本質的にはグラフ内の他のノードを指すためにどの種類のポインタを使うかに帰着します。グラフのようなデータ構造は再帰的であるため（データ自体がそうでなくても型は再帰的です）、完全に値ベースの構造にするのではなく、何らかの種類のポインタを使わざるを得ません。グラフは循環を持つことができ、Rust の所有権は循環できないため、（木のようなデータ構造や連結リストで行うかもしれないように）ポインタ型として Box<Node> を使うことはできません。

完全に不変なグラフはありません。循環が存在し得るため、グラフを単一の文で作成することはできません。したがって、少なくとも初期化フェーズの間は、グラフは可変でなければなりません。Rust における通常の不変条件は、すべてのポインタは一意であるか不変でなければならない、というものです。グラフのエッジは可変でなければならず（少なくとも初期化中は）、任意のノードに入るエッジは複数存在し得るため、どのエッジも一意であることは保証されません。そのため、可変性を扱うには少し高度なことをする必要があります。

1 つの解決策は、可変な生ポインタ（*mut Node）を使うことです。これは最も柔軟なアプローチですが、最も危険でもあります。型システムからの助けなしに、すべてのライフタイム管理を自分で処理しなければなりません。この方法では非常に柔軟で効率的なデータ構造を作れますが、非常に注意深く行う必要があります。このアプローチは、ライフタイムと可変性の問題の両方を一挙に扱います。しかし、それらを扱う方法は本質的に Rust の利点をすべて無視することです。ここではコンパイラから何の助けも得られません（また、生ポインタは自動的に参照/参照外しされないため、特にエルゴノミックでもありません）。生ポインタを使うグラフは C++ のグラフと大きく変わらないため、ここではその選択肢は扱いません。

ライフタイム管理の選択肢としては、参照カウント（共有所有権、Rc<...> を使用）またはアリーナ割り当て（すべてのノードが同じライフタイムを持ち、アリーナによって管理される。借用参照 &... を使用）があります。前者はより柔軟で（グラフの外部から個々のノードへ任意のライフタイムを持つ参照を持てます）、後者はそれ以外のあらゆる点で優れています。

可変性の管理については、RefCell を使う、つまり Rust の動的な内部可変性の仕組みを利用するか、自分で可変性を管理するかのどちらかです（この場合、内部可変性をコンパイラに伝えるために UnsafeCell を使う必要があります）。前者はより安全で、後者はより効率的です。どちらも特にエルゴノミックではありません。

グラフが循環を持つ可能性がある場合、Rc を使うなら、循環を断ち切ってメモリをリークしないようにするための追加の対処が必要であることに注意してください。Rust には Rc ポインタの循環回収がないため、グラフ内に循環があると参照カウントは決して 0 にならず、グラフは決して解放されません。これは、グラフ内で Weak ポインタを使うか、グラフが破棄されるべきだと分かっているときに手動で循環を断ち切ることで解決できます。前者の方がより信頼できます。ここではどちらも扱わず、例では単にメモリをリークします。借用参照とアリーナ割り当てを使うアプローチにはこの問題がないため、その点で優れています。

異なるアプローチを比較するために、かなり単純な例を使います。グラフ内のノードを表す Node オブジェクトだけを用意します。これは文字列データ（より複雑なデータペイロードを代表するもの）と、隣接ノード（edges）の Vec を保持します。ノードの単純なグラフを作成する init 関数と、グラフを行きがけ順・深さ優先で走査する traverse 関数を用意します。これを使って、グラフ内の各ノードのペイロードを出力します。最後に、self ノードに隣接する最初のノードへの参照を返す Node::first メソッドと、個々のノードのペイロードを出力する foo 関数を用意します。これらの関数は、グラフ内部のノードの操作を伴う、より複雑な操作の代わりです。

退屈させずにできるだけ有益にするため、可能性のある組み合わせのうち 2 つを扱います。参照カウントと RefCell、そしてアリーナ割り当てと UnsafeCell です。他の 2 つの組み合わせは演習として残しておきます。

Rc<RefCell<Node>>

完全な例を参照してください。

これは unsafe コードがないため、より安全な選択肢です。また、最も効率が悪く、最もエルゴノミックでない選択肢でもあります。ただし、かなり柔軟ではあります。グラフのノードは参照カウントされているため、グラフの外部で簡単に再利用できます。完全に可変なグラフが必要な場合、またはノードをグラフから独立して存在させる必要がある場合には、このアプローチをお勧めします。

ノード構造は次のようになります。

#![allow(unused)]
fn main() {
struct Node {
    datum: &'static str,
    edges: Vec<Rc<RefCell<Node>>>,
}
}

新しいノードの作成はそれほど悪くありません: Rc::new(RefCell::new(Node { ... }))。初期化中にエッジを追加するには、始点ノードを可変として借用し、終点ノードをエッジの Vec に clone する必要があります（これは実際のノードではなくポインタを clone し、参照カウントを増やします）。例えば、次のようになります。

#![allow(unused)]
fn main() {
let mut mut_root = root.borrow_mut();
mut_root.edges.push(b.clone());
}

RefCell は、ノードに書き込むときに、そのノードをすでに読み取り中または書き込み中でないことを動的に保証します。

ノードにアクセスするときはいつでも、RefCell を借用するために .borrow() を使う必要があります。私たちの 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 ライブラリでノードを使用できます （Rust の参照カウントオブジェクトの良い点の 1 つは、ライフタイムシステムとうまく連携することです。 Rc の内部への借用参照を作成して、データを直接（かつ安全に）参照できます。 前の例では、RefCell がこれを妨げていますが、Rc/UnsafeCell アプローチなら可能になるはずです）。

破棄も正しく処理されます。唯一の制約は、すべてのノードを同時に破棄しなければならないことです。 ノードの破棄と割り当てはアリーナを使って処理されます。

一方で、かなり多くの明示的なライフタイムを使用する必要があります。 残念ながら、ここではライフタイムエリジョンの恩恵は受けられません。 このセクションの最後では、状況を改善できるかもしれない言語の今後の方向性について説明します。

構築中には、複数から参照されている可能性のあるノードを変更します。 これは安全な Rust コードでは不可能なので、unsafe ブロック内で初期化しなければなりません。 ノードは可変であり、かつ複数から参照されるため、Rust コンパイラに対して、 通常の不変条件に依存できないことを伝えるために UnsafeCell を使用しなければなりません。

このアプローチが実行可能なのはどのような場合でしょうか。グラフは初期化中にのみ変更されなければなりません。 さらに、グラフ内のすべてのノードが同じライフタイムを持つことを要求します （すべてを同時に破棄できる限り、後からノードを追加できるようにするために、 これらの制約をある程度緩めることはできます）。同様に、ノードをいつ変更できるかについて、 より複雑な不変条件に依存することもできますが、そうした点ではプログラマーが安全性に責任を持つため、 物事をシンプルに保つことには価値があります。

アリーナ割り当ては、あるオブジェクトの集合が同じライフタイムを持ち、 同時に解放できる場合のメモリ管理手法です。アリーナは、メモリの割り当てと解放を担うオブジェクトです。 個々のオブジェクトを割り当てるのではなく、大きなメモリの塊をまとめて割り当て・解放するため、 アリーナ割り当ては非常に効率的です。通常、すべてのオブジェクトは連続したメモリ領域から割り当てられます。 これにより、グラフを走査するときのキャッシュコヒーレンシが向上します。

Rust では、アリーナ割り当ては libarena crate によってサポートされており、コンパイラ全体で使用されています。アリーナには 2 種類あります。 型付きと型なしです。前者はより効率的で使いやすい一方、単一の型のオブジェクトしか割り当てられません。 後者はより柔軟で、任意のオブジェクトを割り当てられます。アリーナに割り当てられたオブジェクトはすべて同じライフタイムを持ち、 それはアリーナオブジェクトのパラメータです。型システムにより、アリーナに割り当てられたオブジェクトへの参照が、 アリーナ自体より長く生存できないことが保証されます。

ノード構造体には、グラフのライフタイムである 'a を含める必要があります。 隣接ノードの Vec を UnsafeCell でラップし、それが不変であるべきときでも 変更することを示します。

#![allow(unused)]
fn main() {
struct Node<'a> {
    datum: &'static str,
    edges: UnsafeCell<Vec<&'a Node<'a>>>,
}
}

新しい関数もこのライフタイムを使用しなければならず、割り当てを行うアリーナを引数として受け取らなければなりません。

#![allow(unused)]
fn main() {
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 の型システムにより、 その時点を越えてグラフへの参照を保持できないことが保証されます）。

エッジの追加は少し違った見た目になります。

#![allow(unused)]
fn main() {
(*root.edges.get()).push(b);
}

本質的には、ノード（b）をエッジのリストに追加するために、明らかな root.edges.push(b) を行っています。しかし、edges は UnsafeCell でラップされているため、 それに対して get() を呼び出す必要があります。これにより、edges への可変な生ポインタ（*mut Vec<&Node>）が得られ、edges を変更できるようになります。ただし、それにはポインタを手動で デリファレンスする必要もあります（生ポインタは自動デリファレンスされません）。したがって (*...) という構造になります。最後に、生ポインタのデリファレンスは unsafe なので、 全体を unsafe ブロックで囲む必要があります。

traverse の興味深い部分は次のとおりです。

#![allow(unused)]
fn main() {
for n in &(*self.edges.get()) {
    n.traverse(f, seen);
}
}

エッジリストにアクセスするために、前と同じパターンに従います。これには unsafe ブロックが必要です。 この場合、実際には安全であることがわかっています。なぜなら、初期化後でなければならず、 したがって変更は発生しないからです。

繰り返しになりますが、first メソッドも edges リストにアクセスするために同じパターンに従います。 そしてこれも unsafe ブロック内になければなりません。しかし、Rc<RefCell<_>> を使用するグラフとは対照的に、 ノードへの素直な借用参照を返すことができます。これは非常に便利です。 変更を行わず、初期化後であるため、この unsafe ブロックは安全であると判断できます。

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

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

アリーナ割り当てと借用参照の使用は、Rust における重要なパターンだと私は考えています。 これらのパターンをより安全で使いやすくするために、言語側でさらに多くのことを行うべきです。 allocators に関する進行中の作業によって、 アリーナの使用がより扱いやすくなることを期待しています。ほかに 3 つの改善点があると考えています。

安全な初期化

OO の世界では、初期化中にのみ可変性を保証する仕組みについて多くの研究が行われてきました。 これが Rust で具体的にどのように機能するかは未解決の研究課題ですが、 可変で一意ではないものの、スコープが制限されたポインタを表現する必要があるように思われます。 そのスコープの外側では、既存のポインタは通常の借用参照、すなわち不変 または 一意なものになります。

このような方式の利点は、初期化中は可変で、その後は不変という一般的なパターンを表現する方法が得られることです。 またこれは、個々のオブジェクトは複数から所有されている一方で、集約体 （この場合はグラフ）は一意に所有されている、という不変条件にも依存しています。 そうすれば、UnsafeCell や unsafe ブロックなしで、参照と UnsafeCell のアプローチを採用できるようになり、 そのアプローチをより扱いやすく、より安全にできるはずです。

ETH Zurich の Alex Summers と Julian Viereck がこれをさらに調査しています。

ジェネリックモジュール

「グラフのライフタイム」は、特定のグラフに対して一定です。ライフタイムを繰り返すのは単なるボイラープレートです。これをより人間工学的にする方法の 1 つは、グラフモジュールをライフタイムでパラメーター化できるようにして、すべての struct、impl、関数にライフタイムを追加する必要をなくすことです。グラフのライフタイムは依然としてモジュールの外部から指定する必要がありますが、ほとんどの用途では推論が処理してくれることが期待できます（現在、関数呼び出しでそうなっているように）。

それがどのように見えるかについては、ref_graph_generic_mod.rs を参照してください。 （上で提案した安全な初期化も使用できるはずで、それにより unsafe コードを取り除けるはずです）。

こちらの RFC issue も参照してください。

この機能により、参照と UnsafeCell によるアプローチの構文上のオーバーヘッドが大幅に削減されるでしょう。

ライフタイム省略

現在、エルゴノミクスを向上させるために、プログラマーが関数シグネチャ内の一部のライフタイムを省略できるようにしています。グラフに対する &Node アプローチが少し見苦しい理由の 1 つは、ライフタイム省略規則の恩恵をまったく受けないためです。

Rust でよく見られるパターンは、共通のライフタイムを持つデータ構造です。そのようなデータ構造への参照は、たとえばグラフの例における &'a Node<'a> のように、&'a Foo<'a> のような型を生じさせます。このケースに役立つ省略規則があるとよいでしょう。ただし、それがどのように機能すべきかは、私にはあまり確信がありません。

ジェネリックモジュールを使った例を見ると、ライフタイム省略規則をそれほど拡張する必要はなさそうです（実際のところ、指定されたライフタイムなしで Node::new が機能するかどうかは確信がありませんが、もし機能しないとしても、機能させるための拡張はかなり些細なものに思えます）。モジュールジェネリックなライフタイムがスコープ内で唯一のものである場合（'static 以外）に、それを省略できるようにする新しい規則を追加したくなるかもしれませんが、スコープ内に複数のライフタイムがある場合にそれがどう機能するかはよく分かりません（たとえば foo 関数と init 関数を参照してください）。

ジェネリックモジュールを追加しないとしても、&'a Node<'a> を特に対象とする省略規則を追加できるかもしれませんが、どのようにするかは分かりません。