mutcursor

此软件包提供用于在遍历树和图结构时安全存储父节点可变引用的类型。

[MutCursor] 更高效，因为它避免了动态分配，而 [MutCursorVec] 提供了任意深度的栈。

[MutCursorRootedVec] 支持对单独的根类型和不同叶类型的可变引用。将来我可能将此模式推广，使其更加灵活。

用法

use mutcursor::MutCursor;

let mut tree = TreeNode::new(5);
let mut node_stack = MutCursor::<TreeNode, 2>::new(&mut tree);

// Traverse to the last node
while node_stack.advance(|node| {
    node.traverse()
}) {}

assert_eq!(node_stack.top().val, 0);
assert_eq!(node_stack.depth(), 1);

node_stack.backtrack();
assert_eq!(node_stack.top().val, 1);
assert_eq!(node_stack.depth(), 0);

/// A simple stand-in for a recursive graph structure
struct TreeNode {
    val: usize,
    next: Option<Box<TreeNode>>
}
impl TreeNode {
    fn new(count: usize) -> Self {
        if count > 0 {
            Self {val: count, next: Some(Box::new(Self::new(count-1)))}
        } else {
            Self {val: 0, next: None}
        }
    }
    fn traverse(&mut self) -> Option<&mut Self> {
        self.next.as_mut().map(|boxed| &mut **boxed)
    }
}

替代方案

此软件包基本上与 generic-cursors 做相同的事情。然而，选择此软件包有以下几个原因

1. [MutCursor] 使用的固定大小栈比 Vec 的开销更低，并且可以在动态分配可能不可用的 no_std 环境中使用。

2. MutCursor::try_map_into_mut API 允许一些在其他情况下无法实现的模式。

安全性论点

每个 [MutCursor] 存储的可变引用都逐层可变借用其下面的引用。栈根对节点本身进行可变（因此是排他性）借用。因此，栈的顶部是一个排他性借用。

您可以将树遍历展开成下面的代码，但这不适合循环。本质上，每个 level 变量都被保留，但由于上一层正在可变借用它，因此无法访问。[MutCursor] 对象包含所有的 level 变量，但只提供对顶部的访问

let level_1 = &mut root;
{
    let level_2 = level_1.traverse().unwrap();
    {
        match level_2.traverse() {
            Some(level_3) => {} // Do something with level_3
            None => {} // Fall back to work level_2 or level_1
        }
    }
}

未来工作

用于定义游标类型的宏

在 [MutCursorRootedVec] 的当前设计中，存在一个预定义的模式，规定了 RootT 和 NodeT 类型可以在栈上存在的位置。然而，我们可能在将来需要支持超过两种类型，并以更灵活的模式进行。看来，定义专用游标类型的宏是最佳解决方案。

支持多种类型的内部枚举

为了实现最大的灵活性，我们希望所有引用都通过栈以可能的引用类型枚举的形式存储。然而，如果用户将枚举作为游标类型的类型参数提供，结果将是双重间接引用。因此，枚举行为需要是 MutCursor 内部的。从用户的枚举类型派生 MutCursor 感觉是一种友好的方法来定义游标类型能够存储的类型。