Struct RecRef

pub struct RecRef<'a, T: ?Sized> { /* private fields */ }

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

RecRef<'a, T> represents a reference to a value of type T, with lifetime 'a, which can move recursively into and out of its subfields of the same type T.

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.

The 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.

Internally, the RecRef stores a Vec of pointers, that it extends and pops from.

Implementations

impl<'a, T: ?Sized> RecRef<'a, T>

pub fn new(r: &'a mut T) -> Self

Creates a new RecRef containing only a single reference.

pub fn size(rec_ref: &Self) -> usize

Returns the size of rec_ref, i.e, the amount of references in it. It increases every time you extend rec_ref, and decreases every time you pop rec_ref. The size of a new RecRef is always 1.

pub fn extend<F>(rec_ref: &mut Self, func: F)

where F: for<'b> FnOnce(&'b mut T) -> &'b mut T,

This function extends rec_ref one time. If the current reference is current_ref: &mut T, then this call extends rec_ref with the new reference ref2: &mut T = func(current_ref). After this call, rec_ref will expose the new ref2, and current_ref will be frozen (As it is borrowed by ref2), until ref2 is popped off, unfreezing current_ref.

Safety:

Pay close attention to the type of func: we require that F: for<'b> FnOnce(&'b mut T) -> &'b mut T. That is, for every lifetime 'b, we require that F: FnOnce(&'b mut T) -> &'b mut T.

Let’s define 'freeze_time to be the time ref2 will be in the RecRef. That is, 'freeze_time is the time for which ref2 will live, and the lifetime in which current_ref will be frozen by ref2. Then, the type of func should have been FnOnce(&'freeze_time mut T) -> &'freeze_time mut T. If that woudld have been the type of func, the code would’ve followed rust’s borrowing rules correctly.

However, we can’t know yet what that lifetime is: it will be whatever amount of time passes until the programmer decides to pop ref2 out of the RecRef. And that hasn’t even been decided at this point. Whatever lifetime 'freeze_time that turns out to be, we will know after-the-fact that the type of func should have been FnOnce(&'freeze_time mut T) -> &'freeze_time mut T.

Therefore, the solution is to require that func will be able to work with any value of 'freeze_time. Then we can be sure that the code would’ve worked correctly if we put the correct lifetime there. Therefore, we can always pick correct lifetimes after-the-fact, so the code must be safe.

Also note: The type ensures that the current reference can’t be leaked outside of func. func can’t guarantee that current_ref will live for any length of time, so it can’t store it outside anywhere or give it to anything. It can only use current_ref while still inside func, and use it in order to return ref2, which is the intended usage.

pub fn extend_result<E, F>(rec_ref: &mut Self, func: F) -> Result<(), E>

where F: for<'b> FnOnce(&'b mut T) -> Result<&'b mut T, E>,

Same as Self::extend, but allows the function to return an error value.

pub fn extend_result_precise<E, F>(rec_ref: &mut Self, func: F) -> Result<(), E>

where F: for<'b> FnOnce(&'b mut T, PhantomData<&'b &'a ()>) -> Result<&'b mut T, E>,

Same as Self::extend, but allows the function to return an error value, and also tells the inner function that 'a : 'b using a phantom argument.

pub fn map<F>(rec_ref: &mut Self, func: F)

where F: for<'b> FnOnce(&'b mut T) -> &'b mut T,

This function maps the top of the RecRef. It’s similar to Self::extend, but it replaces the current reference instead of keeping it. See Self::extend for more details.

pub fn map_result<E, F>(rec_ref: &mut Self, func: F) -> Result<(), E>

where F: for<'b> FnOnce(&'b mut T) -> Result<&'b mut T, E>,

Same as Self::map, but allows the function to return an error value.

pub fn map_result_precise<E, F>(rec_ref: &mut Self, func: F) -> Result<(), E>

where F: for<'b> FnOnce(&'b mut T, PhantomData<&'b &'a ()>) -> Result<&'b mut T, E>,

Same as Self::map, but allows the function to return an error value, and also tells the inner function that 'a : 'b using a phantom argument.

pub fn push(rec_ref: &mut Self, r: &'a mut T)

Push another reference to the RecRef, unrelated to the current one. rec_ref.push(new_ref) is morally equivalent to rec_ref.extend_result_precise(move |_, _| { Ok(new_ref) }). However, you might have some trouble making the anonymous function conform to the right type.

pub fn pop(rec_ref: &mut Self) -> Option<&mut T>

Lets the user use the last reference for some time, and discards it completely. After the user uses it, the next time they inspect the RecRef, it won’t be there. If the RecRef has only one reference left, this returns None, because the RecRef can’t be empty.

pub fn into_ref(rec_ref: Self) -> &'a mut T

Discards the RecRef and returns the last reference. The difference between this and using Self::pop are:

• This will consume the RecRef
• Self::pop will never pop the first original reference, because that would produce an invalid RecRef. Self::into_ref will.

Trait Implementations

impl<'a, Q: ?Sized, T: ?Sized + AsMut<Q>> AsMut<Q> for RecRef<'a, T>

fn as_mut(&mut self) -> &mut Q

Converts this type into a mutable reference of the (usually inferred) input type.

impl<'a, Q: ?Sized, T: ?Sized + AsRef<Q>> AsRef<Q> for RecRef<'a, T>

fn as_ref(&self) -> &Q

Converts this type into a shared reference of the (usually inferred) input type.

impl<'a, T: ?Sized> Deref for RecRef<'a, T>

RecRef<T> represents a reference to a value of type T, which can move recursively into and out of its subfields of the same type T. Therefore, it implements Deref and DerefMut with Item=T.

type Target = T

The resulting type after dereferencing.

fn deref(&self) -> &T

Dereferences the value.

impl<'a, T: ?Sized> DerefMut for RecRef<'a, T>

RecRef<T> represents a reference to a value of type T, which can move recursively into and out of its subfields of the same type T. Therefore, it implements Deref and DerefMut with Item=T.

fn deref_mut(&mut self) -> &mut T

Mutably dereferences the value.

impl<'a, T: ?Sized> From<&'a mut T> for RecRef<'a, T>

fn from(r: &'a mut T) -> Self

Converts to this type from the input type.

impl<'a, T: ?Sized + Send> Send for RecRef<'a, T>

where Vec<&'a mut T>: Send,

Safety:

Behaviorally, A RecRef is the same as &'a mut T, and should be Send for the same reason. Additionally, it contains a Vec. The Send instance for Vec contains the bound A: Send for the allocator type A, so we should require that as well. However, we don’t have direct access to the default allocator type. So instead we require Vec<&'a mut T>: Send.

impl<'a, T: ?Sized + Sync> Sync for RecRef<'a, T>

where Vec<&'a mut T>: Sync,

Safety:

Behaviorally, A RecRef is the same as &'a mut T, and should be Sync for the same reason. Additionally, it contains a Vec. The Sync instance for Vec contains the bound A: Sync for the allocator type A, so we should require that as well. However, we don’t have direct access to the default allocator type. So instead we require Vec<&'a mut T>: Sync.