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 ;
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 usingGhostCell<'brand, T>::borrow
-- note the matching'brand
-- and allows obtaining a&T
reference.&mut GhostToken<'brand>
is the key to usingGhostCell<'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!
And thanks for reading.