generic-cursors

一个用于可变遍历无环递归数据结构的Rust库。

示例

use generic_cursors::simple::MutRefStack;

#[derive(Debug, Clone)]
/// A simple recursive data structure
pub struct SimpleLinkedList<T> {
    data: T,
    child: Option<Box<SimpleLinkedList<T>>>,
}

impl<T> SimpleLinkedList<T> {
    fn child_mut(&mut self) -> Option<&mut Self> {
        self.child.as_deref_mut()
    }
    fn insert_child(&mut self, new_child: Box<Self>) -> Option<Box<Self>> {
        std::mem::replace(&mut self.child, Some(new_child))
    }
}

fn main() {
    let mut the_t = SimpleLinkedList {
        data: 0_u32,
        child: None,
    };

    // Using a MutRefStack to descend the data structure.
    // This could be done with regular mutable references.
    let mut stack = MutRefStack::new(&mut the_t);
    for i in 1..10 {
        stack.top_mut().insert_child(Box::new(SimpleLinkedList {
            data: i,
            child: None,
        }));
        stack.descend_with(SimpleLinkedList::child_mut).unwrap();
    }
    println!("{:?}", the_t);

    // Using regular mutable references to descend the data structure.
    let mut top = &mut the_t;
    for i in 1..10 {
        top.insert_child(Box::new(SimpleLinkedList {
            data: i,
            child: None,
        }));
        top = top.child_mut();
    }
    println!("{:?}", the_t);

    // Using a MutRefStack to descend *and then ascend* the data structure.
    // This cannot be done with regular mutable references.
    let mut stack = MutRefStack::new(&mut the_t);
    println!("Stack currently at item with value: {}", stack.top().data);
    loop {
        if let None = stack.descend_with(SimpleLinkedList::child_mut) {
            println!("Reached the end of the linked list!");
            break;
        }
        println!("Descended successfully!");
        println!("Stack currently at item with value: {}", stack.top().data);
    }
    println!("Stack currently at item with value: {}", stack.top().data);
    loop {
        if let None = stack.ascend() {
            println!("Reached the head of the linked list!");
            break;
        }
        println!("Ascended successfully!");
        println!("Stack currently at item with value: {}", stack.top().data);
    }
}

安全性

该库（可以说：应该）在具有类似Stacked Borrows的内存模型的情况下完全安全，因为每个引用（指针）在MutRefStack上从上一个引用借出，只有最顶层的引用是可访问的，因此后来的引用不会被先前引用无效化。弹出引用（通过上升）结束当前最顶层引用的生存期，并将上一个最顶层引用变为新的最顶层引用。推送引用（通过下降或注入）使上一个最顶层引用直到它再次变为最顶层引用（通过返回它）之前不可访问。