A novel safe and zero-cost borrow-checking paradigm from the
[`GhostCell`](http://plv.mpi-sws.org/rustbelt/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](https://plv.mpi-sws.org/rustbelt/). 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:
```rust
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`](https://crates.io/crates/static-rc), it allows writing Doubly Linked Lists, Binary Trees and
B-Trees with parent pointers, etc... in safe, stable, Rust.
# That's all folks!
And thanks for reading.