Crate recursive_reference[−][src]
Expand description
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 |