Crate recursive_reference

Recursive reference.

This crate provides a way to traverse recursive structures easily and safely. Rust’s lifetime rules will usually force you to either only walk forward through the structure, or use recursion, calling your method recursively every time you go down a node, and returning every time you want to go back up, which leads to terrible code.

Instead, you can use the RecRef type, to safely and dynamically walk up and down your recursive structure.

Examples

Say we have a recursive linked list structure

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

We can use a RecRef directly

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(())
}

We can also wrap a RecRef in a walker struct

Note: this time we are using a RecRef<List<T>> and not a RecRef<Node<T>>, to allow pointing at the empty end of the list.

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(())
}

With a RecRef you can

• Use the current reference (i.e, the top reference). the RecRef is a smart pointer to it.
• Freeze the current reference and extend the RecRef with a new reference derived from it, using extend and similar functions. for example, push to the stack a reference to the child of the current node.
• Pop the stack to get back to the previous reference, unfreezing it.

Safety

The RecRef type is implemented using unsafe rust, but provides a safe interface. The RecRef methods’ types guarantee that the references will always have a legal lifetime and will respect rust’s borrow rules, even if that lifetime is not known in advance.

The RecRef obeys rust’s borrowing rules, by simulating freezing. Whenever you extend a RecRef with a reference child_ref that is derived from the current reference parent_ref, the RecRef freezes parent_ref, and no longer allows parent_ref to be used. When child_ref will be popped from the RecRef, parent_ref will be allowed to be used again.

This is essentially the same as what would have happened if you wrote your functions recursively, but it’s decoupled from the actual call stack.

Another important point to consider is the safety of the actual call to extend: see its documentation.

Structs

• RecRef
  A Recursive reference. This struct is used to allow recursively reborrowing mutable references in a dynamic but safe way.