[][src]Crate qcell

Statically-checked alternatives to RefCell.

This crate provides four alternatives to RefCell, each of which checks borrows from the cell at compile-time (statically) instead of checking them at runtime as RefCell does. The mechasism for checks is the same for all four. They only differ in how ownership is represented: QCell uses an integer ID, TCell and TLCell use a marker type, and LCell uses a Rust lifetime. Each approach has its advantages and disadvantages.

Taking QCell as an example: QCell is a cell type where the cell contents are logically 'owned' for borrowing purposes by an instance of an owner type, QCellOwner. So the cell contents can only be accessed by making borrowing calls on that owner. This behaves similarly to borrowing fields from a structure, or borrowing elements from a Vec. However actually the only link between the objects is that a reference to the owner instance was provided when the cell was created. Effectively the borrowing-owner and dropping-owner are separated.

This enables a pattern where the compiler can statically check mutable access to data stored behind Rc references (or other reference types) at compile-time. This pattern works as follows: The owner is kept on the stack and a mutable reference to it is passed down the stack to calls (for example as part of a context structure). This is fully checked at compile-time by the borrow checker. Then this static borrow checking is extended to the cell contents (behind Rcs) through using borrowing calls on the owner instance to access the cell contents. This gives a compile-time guarantee that access to the cell contents is safe.

The alternative would be to use RefCell, which panics if two mutable references to the same data are attempted. With RefCell there are no warnings or errors to detect the problem at compile-time. On the other hand, using QCell the error is detected at compile-time, but the restrictions are much stricter than they really need to be. For example it's not possible to borrow from more than a few different cells at the same time if they are protected by the same owner, which RefCell would allow (correctly). However if you are able to work within these restrictions (e.g. by keeping borrows active only for a short time), then the advantage is that there can never be a panic due to erroneous use of borrowing, because everything is checked by the compiler.

Apart from QCell and QCellOwner, this crate also provides TCell and TCellOwner which work the same but use a marker type instead of owner IDs, TLCell and TLCellOwner which also use a marker type but which are thread-local, and LCell and LCellOwner which use lifetimes. See the "Comparison of cell types" below.

Examples

With RefCell, this compiles but panics:

This example panics
let item = Rc::new(RefCell::new(Vec::<u8>::new()));
let mut iref = item.borrow_mut();
test(&item);
iref.push(1);

fn test(item: &Rc<RefCell<Vec<u8>>>) {
    item.borrow_mut().push(2);    // Panics here
}

With QCell, it refuses to compile:

This example deliberately fails to compile
let mut owner = QCellOwner::new();

let item = Rc::new(QCell::new(&owner, Vec::<u8>::new()));
let iref = owner.rw(&item);
test(&mut owner, &item);    // Compile error
iref.push(1);

fn test(owner: &mut QCellOwner, item: &Rc<QCell<Vec<u8>>>) {
    owner.rw(&item).push(2);
}

The solution in both cases is to make sure that the iref is not active when the call is made, but QCell uses standard compile-time borrow-checking to force the bug to be fixed. This is the main advantage of using these types.

Here's a working version using TCell instead:

struct Marker;
type ACell<T> = TCell<Marker, T>;
type ACellOwner = TCellOwner<Marker>;
let mut owner = ACellOwner::new();

let item = Rc::new(ACell::new(Vec::<u8>::new()));
let iref = owner.rw(&item);
iref.push(1);
test(&mut owner, &item);

fn test(owner: &mut ACellOwner, item: &Rc<ACell<Vec<u8>>>) {
    owner.rw(&item).push(2);
}

And the same thing again using LCell:

LCellOwner::scope(|mut owner| {
  let item = Rc::new(LCell::new(Vec::<u8>::new()));
  let iref = owner.rw(&item);
  iref.push(1);
  test(&mut owner, &item);
});

fn test<'id>(owner: &mut LCellOwner<'id>, item: &Rc<LCell<'id, Vec<u8>>>) {
    owner.rw(&item).push(2);
}

Why this is safe

This is the reasoning behind declaring this crate's interface safe:

  • Between the cell creation and destruction, the only way to access the contents (for read or write) is through the borrow-owner instance. So the borrow-owner is the exclusive gatekeeper of this data.

  • The borrowing calls require a & owner reference to return a & cell reference, or a &mut on the owner to return a &mut cell reference. So this is the same kind of borrow on both sides. The only borrow we allow for the cell is the borrow that Rust allows for the borrow-owner, and while that borrow is active, the borrow-owner and the cell's reference are blocked from further incompatible borrows. The contents of the cells act as if they were owned by the borrow-owner, just like elements within a Vec. So Rust's guarantees are maintained.

  • The borrow-owner has no control over when the cell's contents are dropped, so the borrow-owner cannot act as a gatekeeper to the data at that point. However this cannot clash with any active borrow on the data because whilst a borrow is active, the reference to the cell is effectively locked by Rust's borrow checking. If this is behind an Rc, then it's impossible for the last strong reference to be released until that borrow is released.

If you can see a flaw in this reasoning or in the code, please raise an issue, preferably with test code which demonstrates the problem. MIRI in the Rust playground can report on some kinds of unsafety.

Comparison of cell types

RefCell pros and cons:

  • Pro: Simple
  • Pro: Allows very flexible borrowing patterns
  • Con: No compile-time borrowing checks
  • Con: Can panic due to distant code changes
  • Con: Runtime borrow checks and some cell space overhead

QCell pros and cons:

  • Pro: Simple
  • Pro: Compile-time borrowing checks
  • Pro: Dynamic owner creation, not limited in any way
  • Pro: No lifetime annotations or type parameters required
  • Con: Can only borrow up to 3 objects at a time
  • Con: Runtime owner checks and some cell space overhead

TCell and TLCell pros and cons:

  • Pro: Compile-time borrowing checks
  • Pro: No overhead at runtime for borrowing or ownership checks
  • Pro: No cell space overhead
  • Con: Can only borrow up to 3 objects at a time
  • Con: Uses singletons, either per-process (TCell) or per-thread (TLCell), meaning only one owner is allowed per thread or process per marker type. Code intended to be nested on the call stack must be parameterised with an external marker type.

LCell pros and cons:

  • Pro: Compile-time borrowing checks
  • Pro: No overhead at runtime for borrowing or ownership checks
  • Pro: No cell space overhead
  • Pro: No need for singletons, meaning that one use does not limit other nested uses
  • Con: Can only borrow up to 3 objects at a time
  • Con: Requires lifetime annotations on calls and structures
CellOwner IDCell overheadBorrow checkOwner checkOwner creation check
RefCelln/ausizeRuntimen/an/a
QCellintegeru32Compile-timeRuntimeRuntime
TCell or TLCellmarker typenoneCompile-timeCompile-timeRuntime
LCelllifetimenoneCompile-timeCompile-timeCompile-time

Owner ergonomics:

CellOwner typeOwner creation
RefCelln/an/a
QCellQCellOwnerQCellOwner::new()
TCell or
TLCell
ACellOwner
(or BCellOwner or CCellOwner etc)
struct MarkerA;
type ACell<T> = TCell<MarkerA, T>;
type ACellOwner = TCellOwner<MarkerA>;
ACellOwner::new()
LCellLCellOwner<'id>LCellOwner::scope(|owner| { ... })

Cell ergonomics:

CellCell typeCell creation
RefCellRefCell<T>RefCell::new(v)
QCellQCell<T>owner.cell(v) or QCell::new(&owner, v)
TCell or TLCellACell<T>owner.cell(v) or ACell::new(v)
LCellLCell<'id, T>owner.cell(v) or LCell::new(v)

Borrowing ergonomics:

CellCell immutable borrowCell mutable borrow
RefCellcell.borrow()cell.borrow_mut()
QCellowner.ro(&cell)owner.rw(&cell)
TCell or TLCellowner.ro(&cell)owner.rw(&cell)
LCellowner.ro(&cell)owner.rw(&cell)

Multi-threaded use: Send and Sync

Most often the cell-owner will be held by just one thread, and all access to cells will be made within that thread. However it is still safe to pass or share these objects between threads in some cases, where permitted by the contained type:

CellOwner typeCell type
RefCelln/aSend
QCellSend + SyncSend + Sync
TCellSend + SyncSend + Sync
TLCellSend
LCellSend + SyncSend + Sync

I believe that the reasoning behind enabling Send and/or Sync is sound, but I welcome review of this in case anything has been overlooked. I am grateful for contributions from Github users Migi and pythonesque. GhostCell by pythonesque is a lifetime-based cell that predated LCell. It appears that he has proved some properties of GhostCell using Coq, and I hope that that research becomes public in due course.

Here's an overview of the reasoning:

  • Unlike RefCell these cell types may be Sync because mutable access is protected by the cell owner. You can get mutable access to the cell contents only if you have mutable access to the cell owner. (Note that Sync is only available where the contained type is Send + Sync.)

  • The cell owner may be Sync because Sync only allows shared immutable access to the cell owner across threads. So there may exist &QCell and &QCellOwner references in two threads, but only immutable access to the cell contents is possible like that, so there is no soundness issue.

  • In general Send is safe because that is a complete transfer of some right from one thread to another (assuming the contained type is also Send).

  • TLCell is the exception because there can be a different owner with the same marker type in each thread, so owners must not be sent or shared. Also if two threads have &TLCell references to the same cell then mutable references to the contained data could be created in both threads which would break Rust's guarantees. So TLCell cannot be Sync. However it can be Send because in that case the right to access the data is being transferred completely from one thread to another.

Origin of names

"Q" originally referred to quantum entanglement, the idea being that this is a kind of remote ownership. "T" refers to it being type system based, "TL" thread-local, "L" to lifetime-based.

Unsafe code patterns blocked

See the doctest_qcell, doctest_tcell, doctest_tlcell and doctest_lcell modules

Modules

doctest_lcell

This tests the LCell implementation.

doctest_qcell

This tests the QCell implementation.

doctest_tcell

This tests the TCell implementation.

doctest_tlcell

This tests the TLCell implementation.

Structs

LCell

Cell whose contents are owned (for borrowing purposes) by a LCellOwner.

LCellOwner

Borrowing-owner of zero or more LCell instances.

QCell

Cell whose contents is owned (for borrowing purposes) by a QCellOwner.

QCellOwner

Borrowing-owner of zero or more QCell instances.

QCellOwnerID

Internal ID associated with a QCellOwner.

TCell

Cell whose contents is owned (for borrowing purposes) by a TCellOwner.

TCellOwner

Borrowing-owner of zero or more TCell instances.

TLCell

Cell whose contents is owned (for borrowing purposes) by a TLCellOwner.

TLCellOwner

Borrowing-owner of zero or more TLCell instances.