Crate rec_cell 

Zero-cost borrow-checking of aliased references supporting cyclic construction.

RecCell enforces borrow checking rules using a RecToken, created with RecToken::new. This creates a scope where the token grants access to associated RecCells:

• &RecToken borrows a cell as &T.
• &mut RecToken borrows a cell as &mut T.

Each cell is associated with exactly one token, and mismatched access is a compile error. The correctness of the design above has been proven in the GhostCell paper.

Building cycles directly

On top of that, this crate experiments with providing cyclic constructors like RecCell::new_cyclic, similar in spirit to Rc::new_cyclic, to initialize a caller-provided MaybeUninit slot. The initialization closure receives a reference to the future cell, then returns the value to write into it. That constructed value is allowed to refer to the cell itself, creating a cycle. To prohibit accessing the cell’s contents before it is initialized, the cyclic constructors take the RecToken by value and return it only when construction succeeds.

Such an API comes with the following caveats:

• Cyclic constructors write a T into a &mut MaybeUninit<T>. MaybeUninit does not run T’s destructor, so cyclically initialized values leak unless you explicitly drop them.

• Cyclic constructors provide a reference to an uninitialized cell that must not be accessed before initialization. If you fail to initialize the cell, the token needs to be forever lost, so every cell under the same token becomes permanently inaccessible by shared reference.

• This crate does not allocate or own the storage. It is best paired with an arena or any other allocation mechanism that provides storage with stable addresses.

Cursors

Cursors are simple wrappers around (cell, &token) pairs and provide a convenient way to traverse a structure of RecCells. CursorMut provides mutable access to the cell, and SliceCursor and SliceCursorMut provide cursors over slices of RecCells.

From a safety perspective, they are just wrappers and anything that can be done using them can also be done by managing the cell and token separately.

Initializing multiple cells cyclicly

The RecToken::make_cyclic method generalizes RecCell::new_cyclic to allow cyclicly initializing multiple cells at once. Arbitrary composition of cyclic initializations is possible by making use of RecBuilder, which is used to check whether all initializations have been properly completed. If any initialization fails, the builder is destroyed and the original RecToken cannot be recovered, prohibiting access to uninitialized cells. See RecToken::with_builder for more details.

Examples

A self-referential node:

use std::mem::MaybeUninit;
use rec_cell::{RecCell, RecToken};

struct Node<'a, 't> {
    value: u32,
    // No `Option` is needed, since we can cyclicly initialize the node to
    // indirectly refer to itself, without modifying the node after node creation.
    next: &'a RecCell<'t, Self>,
}

RecToken::new(|token| {
    let [mut node0, mut node1, mut node2] = [const { MaybeUninit::<Node>::uninit() }; 3];

    // Build a structure with node0 -> node1 -> node2 -> node0.
    let (nodes, token) = RecCell::new_cyclic(&mut node0, token, |n0| {
        let n2 = RecCell::from_mut(node2.write(Node { value: 20, next: n0 }));
        let n1 = RecCell::from_mut(node1.write(Node { value: 10, next: n2 }));
        let node0 = Node { value: 0, next: n1 };
        ([n0, n1, n2], node0)
    });

    // Walk the structure with a cursor.
    let mut cursor = nodes[0].cursor(&token);
    let target = [0, 10, 20, 0, 10, 20];
    for i in 0..6 {
        assert_eq!(cursor.get().value, target[i]);
        cursor.update(|node| node.next);
    }
});

Prior art

This crate is heavily based on ghost_cell and qcell::LCell, which provide similar methods except that they do not permit cyclic initialization.

RecCell is almost a drop-in replacement for the non-experimental parts of GhostCell, except that RecCell<'_, T> requires T: Sized due to MaybeUninit<T> requiring T: Sized. Use [RecCell<'_, T>] to manage a slice [T].

Structs

Cursor

A read-only cursor over a RecCell.

CursorMut

A mutable cursor over a RecCell.

RecBuilder

A builder used to compose cyclic initializations.

RecCell

A cell that can be used to create recursive data structures.

RecToken

A token that grants access to RecCell values from the same scope.

SliceCursor

A read-only cursor over a slice of RecCells.

SliceCursorMut

A mutable cursor over a slice of RecCells.

Traits

CellLike

A cell or collection of cells that a cursor can visit.

CyclicBuildable

Storage where cyclic initialization can be performed.