A novel safe and zero-cost borrow-checking paradigm from the GhostCell paper.

Motivation

A number of collections, such as linked-lists, binary-trees, or B-Trees are most easily implemented with aliasing pointers.

Traditionally, this means using run-time borrow-checking in order to still be able to mutate said structures, or using unsafe in the name of performance.

By using brands, GhostCell separate the data from the permission to mutate it, and uses a unique GhostToken to model this permission, tied at compile-time to a number of said GhostCell via the brand.

Safety

In the GhostCell paper, Ralf Jung and his colleagues from MPI-SWS, Germany, formally demonstrate the safety of GhostCell using the separation logic they have developed as part of the Rust Belt project. I personally would trust them on this.

This implementation is, unfortunately, unofficial. Furthermore, a number of methods were left as an exercise to the reader, and this reader cannot guarantee that they successfully managed in filling the blanks without introducing any unsafety.

Use at your own risks!

(And please report any issue)

Maturity

This is very much an Alpha quality release, at best.

If you haven't looked closer, there's one lone doctest.

(Though the one doctest runs under MIRI, eh!)

How to use?

Let's start from a self-contained example:

use ghost_cell::{GhostToken, GhostCell};

fn demo(n: usize) {
    let value = GhostToken::new(|mut token| {
        let cell = GhostCell::new(42);

        let vec: Vec<_> = (0..n).map(|_| &cell).collect();

        *vec[n / 2].borrow_mut(&mut token) = 33;

        *cell.borrow(&token)
    });

    assert_eq!(value, 33);
}

GhostToken uses the best known way to generate a unique lifetime, hence used as a brand, which is to combine:

A local variable, created within the GhostToken::new method.
A closure which must be valid for all lifetimes.

This means 2 restrictions:

Since the closure must be valid for all lifetimes, it must notably be valid for the 'static lifetime.
None of the branded items can be returned by the closure.

Then, within the closure, any GhostCell can be associated to one, and only one, GhostToken which will encode its borrowing permissions:

&GhostToken<'brand> is the key to using GhostCell<'brand, T>::borrow -- note the matching 'brand -- and allows obtaining a &T reference.
&mut GhostToken<'brand> is the key to using GhostCell<'brand, T>::borrow_mut and allows obtaining a &mut T reference.

Using borrow or borrow_mut borrow both the cell and the token.

So what?

A GhostCell is a safe, zero-cost, cell. It allows aliasing with compile-time checked borrow-checking.

Combined with StaticRc, it allows writing Doubly Linked Lists, Binary Trees and B-Trees with parent pointers, etc... in safe, stable, Rust.

That's all folks!