递归引用 —

这个crate提供了一种轻松且安全地遍历递归结构的方法。Rust的生命周期规则通常会强制你只能向前遍历结构，或者使用递归，每次向下遍历节点时都递归调用你的方法，并在想要向上返回时返回，这会导致糟糕的代码。

相反，你可以使用RecRef类型，来安全且动态地在你的递归结构中上下移动。

文档 crates.io 仓库

示例

假设我们有一个递归链表结构

enum List<T> {
    Root(Box<Node<T>>),
    Empty,
}
struct Node<T> {
    value: T,
    next: List<T>,
}

我们可以直接使用一个RecRef

use recursive_reference::*;

fn main() -> Result<(), ()> {
    // crate a list to test
    let node1 = Node {
        value: 5,
        next: List::Empty,
    };
    let mut node2 = Node {
        value: 2,
        next: List::Root(Box::new(node1)),
    };

    // create a `RecRef`
    let mut rec_ref = RecRef::new(&mut node2);
    // rec_ref is a smart pointer to the current node
    assert_eq!(rec_ref.value, 2);

    // move forward through the list
    RecRef::extend_result(&mut rec_ref, |node| match &mut node.next {
        List::Root(next_node) => Ok(next_node),
        List::Empty => Err(()),
    })?;
    assert_eq!(rec_ref.value, 5); // now we're at the second node

    // pop the `RecRef`, moving it back to the head
    RecRef::pop(&mut rec_ref).ok_or(())?;
    assert_eq!(rec_ref.value, 2);
    Ok(())
}

我们还可以将RecRef封装在一个walker结构体中

use recursive_reference::*;
struct Walker<'a, T> {
    rec_ref: RecRef<'a, Node<T>>,
}
impl<'a, T> Walker<'a, T> {
    /// Crates a new Walker
    pub fn new(node: &'a mut Node<T>) -> Self {
        Walker {
            rec_ref: RecRef::new(node),
        }
    }

    /// Returns `None` when at the tail end of the list.
    /// Moves to the next node.
    pub fn next(&mut self) -> Option<()> {
        RecRef::extend_result(&mut self.rec_ref, |current| match &mut current.next {
            List::Empty => Err(()),
            List::Root(node) => Ok(node),
        })
        .ok()
    }

    /// Returns `None` when at the head of the list.
    /// Goes back to the previous node.
    pub fn prev(&mut self) -> Option<()> {
        RecRef::pop(&mut self.rec_ref)?;
        Some(())
    }

    /// Returns `None` when at the tail end of the list.
    /// Returns `Some(reference)` where `reference` is a mutqable reference to the current value.
    pub fn value_mut(&mut self) -> &mut T {
        &mut self.rec_ref.value
    }
}

fn main() -> Result<(), ()> {
    // crate a list to test
    let node1 = Node {
        value: 5,
        next: List::Empty,
    };
    let mut node2 = Node {
        value: 2,
        next: List::Root(Box::new(node1)),
    };

    // create a walker for the list
    let mut walker = Walker::new(&mut node2);
    // walker has mutable access to the node value
    assert_eq!(*walker.value_mut(), 2);
    // move to the next node
    walker.next().ok_or(())?;
    assert_eq!(*walker.value_mut(), 5);
    assert_eq!(walker.next(), None); // currently at the end of the list
                                     // move back
    walker.prev().ok_or(())?;
    assert_eq!(*walker.value_mut(), 2);
    Ok(())
}

使用RecRef，你可以

• 使用当前引用（即，顶部引用）。RecRef是它的智能指针。
• 冻结当前引用，并使用extend和类似函数扩展RecRef，从中派生出一个新的引用。例如，将当前节点的子节点的引用压入栈中。
• 弹出栈以返回到上一个引用，解冻它。

替代比较

使用 RecRef 的替代方案有很多。它们各有优缺点。我们只与 RecRef 进行比较，因此只列出 RecRef 解决的缺点。许多这些替代方案根据用例可能更好。以下是它们，从基本到复杂：

• 普通递归数据结构。这需要编写递归函数，其中递归与您的访问模式完全匹配。除了最基本的函数之外，这种方法很难编写。
• 基于指针的数据结构可以高效方便，但不够安全。
• Rc 和 RefCell 基于的数据结构可能很方便，但需要开销来存储元数据和检查它。它们还会在运行时而不是编译时使所有权错误暴露出来。（您可能想看看 static-rc，这是一个可以改进此功能的 crate）。
• 基于标签。也就是说，将所有节点存储在某种类型的集合中，并将链接作为集合中的索引。
  • 需要您的指针通过额外的间接引用。
  • 您的结构将绑定到标签（您不能分割它的部分并发送到另一个所有者）。
  • 如果您从结构中借用，整个结构可能会被更改。
• 基于区域的递归数据结构。也就是说，区域就像标签，不能删除其元素，因此可以为其元素提供长期引用。
  • 节点必须在整个结构释放之前才能被释放。
  • 您的结构将绑定到区域（您不能分割它的部分并发送到另一个所有者）。
• 在 qcell crate 和 ghost-cell crate 中也有其他替代单元，甚至可能还有更多有趣的选择。

RecRef 优点

• RecRef 可以与任何现有数据结构一起使用，包括您未编写的数据结构。《a href="https://docs.rs/recursive_reference/*/recursive_reference/struct.RecRef.html" rel="noopener ugc nofollow">RecRef 可以与普通结构、Rc/RefCell 基于的结构、基于区域的结构等一起工作。尽管如此，建议使用普通结构。
• RecRef 不向结构增加空间开销。
• RecRef 是安全的，不会崩溃。
• RecRef 不会将其限制住，即，防止您分割结构的所有权。