Crate recursive_reference

Recursive reference This module provides a way to walk on 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.

Say we have a recursive linked list structure:

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

Then we can wrap the RecRef in a struct allowing us to walk up and down our list:

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

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

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

     /// Returns `None` when at the tail end of the list
     pub fn value_mut(&mut self) -> Option<&mut T> {
         match &mut *self.rec_ref {
             List::Root(node) => Some(&mut node.value),
             List::Empty => None,
         }
     }
 }

 fn main() {
     let node1 = Node { value : 5, next : List::Empty };
     let node2 = Node { value : 2, next : List::Root(Box::new(node1)) };
     let mut list = List::Root(Box::new(node2));

     let mut walker = Walker::new(&mut list);
     assert_eq!(walker.value_mut().cloned(), Some(2));
     *walker.value_mut().unwrap() = 7;
     walker.next().unwrap();
     assert_eq!(walker.value_mut().cloned(), Some(5));
     walker.next().unwrap();
     assert_eq!(walker.value_mut().cloned(), None); // end of the list
     walker.prev().unwrap();
     assert_eq!(walker.value_mut().cloned(), Some(5));
     walker.prev().unwrap();
     assert_eq!(walker.value_mut().cloned(), Some(7)); // we changed the value at the head
 }

This works by having a stack of references in the RecRef. You can do these toperations:

• You can always use the current reference. that is, the current reference - the RecRef is a smart pointer to it.
• using extend, freeze the current reference and extend the RecRef with a new reference derived from it. for example, pushing to the stack the child of the current node.
• pop the stack to get back to the previous references, unfreezing them.

Safety

The RecRef type is implemented using unsafe rust, but provides a safe interface.

The RecRef obeys rust’s borrowing rules, by simulating freezing. Whenever you extend the 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 decoupled from the actual call stack.

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

Internally, the RecRef keeps a stack of pointers, instead of reference, in order not to violate rust’s invariants.

Structs

RecRef

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

Constants

NO_VALUE_ERROR
NULL_POINTER_ERROR