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.
documentation crates.io repository
Examples
Say we have a recursive linked list structure
We can use a RecRef
directly
use *;
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 *;
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, usingextend
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.
License
dual licensed with MIT and APACHE 2.0