방향 지정 비순환 그래프를 안전하게 트래버스

Question

DAG를 빌드하고 트래버스하려고합니다. 가능한 두 가지 방법이있을 것 같습니다 : 가장자리에 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을 사용하는 이유는 확실하지 않습니다. 확실히 필요하지 않습니다.