有向非循環グラフを安全にトラバースする

Question

DAGを作成してトラバースしようとしています。 2つの実現可能なアプローチがあるように思われる：エッジにはRc<RefCell<Node>>を使用するか、アリーナアロケータおよび一部のunsafeコードを使用する。 （See details here.）

私は元を選ぶが、難易度のエッジにグラフを横断した、子ノードのいずれかのボローがその親に借りに依存しているようだ：

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

// See: https://aminb.gitbooks.io/rust-for-c/content/graphs/index.html, 
//  https://github.com/nrc/r4cppp/blob/master/graphs/src/ref_graph.rs 
pub type Link<T> = Rc<RefCell<T>>; 

pub struct DagNode { 
    /// Each node can have several edges flowing *into* it, i.e. several owners, 
    /// hence the use of Rc. RefCell is used so we can have mutability 
    /// while building the graph. 
    pub edge: Option<Link<DagNode>>, 

    // Other data here 
} 

// Attempt to walk down the DAG until we reach a leaf. 
fn walk_to_end(node: &Link<DagNode>) -> &Link<DagNode> { 
    let nb = node.borrow(); 
    match nb.edge { 
     Some(ref prev) => walk_to_end(prev), 
     // Here be dragons: the borrow relies on all previous borrows, 
     // so this fails to compile. 
     None => node 
    } 
} 

私は修正することができます参照カウント、つまり

fn walk_to_end(node: Link<HistoryNode>) -> Link<HistoryNode> { 
    let nb = node.borrow(); 
    match nb.previous { 
     Some(ref prev) => walk_to_end(prev.clone()), 
     None => node.clone() 
    } 
} 

を参照してください。ただし、ノードを通過するたびに参照カウントが大幅に増加します。ここでの慣用的なアプローチは何ですか？

Answer 1

Rcは実際には問題ではありません。RefCellを取り除くと、すべてがコンパイルされます。実際には、状況によっては解決策かもしれません。ノードの内容を変更する必要がありエッジは変更しない場合は、エッジがRefCell内にないようにデータ構造を変更するだけです。

引数は実際には問題ではありません。

fn walk_to_end(node: &Link<DagNode>) -> Link<DagNode> { 
    let nb = node.borrow(); 
    match nb.edge { 
     Some(ref prev) => walk_to_end(prev), 
     None => node.clone() 
    } 
} 

ここでの問題は本当に結果を返しています。基本的に、あなたが望む戻り値を書く方法はありません。理論的には、あなたのメソッドがVec<Ref<T>>のラッパーを返すようにすることができますが、それは単に結果の参照カウントをバンプするよりもはるかに高価です。

Rc<RefCell<T>>は、複雑なデータ構造であるため、扱いにくいです。複数のノードを同時に安全に変更することができ、各ノードを参照するエッジ数を正確に追跡できます。

アリーナを使用するために安全でないコードに浸漬する必要はありません。 https://crates.io/crates/typed-arenaは、競技場に安全なAPIを提供します。あなたがリンクした例がUnsafeCellを使用する理由がわかりません。確かに必要はありません。