Crate qcell

source ·
Expand description

Statically-checked alternatives to RefCell and RwLock.

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:

ⓘ
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:

ⓘ
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
  • Pro: no_std support
  • 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
  • Pro: no_std support
  • 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
  • Pro: no_std support (via external crate)
  • 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
  • Pro: no_std support
  • 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
QCellintegerusizeCompile-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()
QCellcell.ro(&owner) or
owner.ro(&cell)		cell.rw(&mut owner) or
owner.rw(&cell)
TCell or TLCellcell.ro(&owner) or
owner.ro(&cell)		cell.rw(&mut owner) or
owner.rw(&cell)
LCellcell.ro(&owner) or
owner.ro(&cell)		cell.rw(&mut owner) or
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 am grateful for contributions from Github users Migi and pythonesque to justify the reasoning behind enabling Send and/or Sync. (GhostCell by pythonesque is a lifetime-based cell that predated LCell, but which was only officially published in 2021. The authors of that paper proved that the logical reasoning behind GhostCell is correct, which indirectly strengthens the theoretical justification for other similar cell types, such as the ones in this crate.)

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.

Multi-threaded use: RwLock

QCell and similar types can also be used as a replacement for RwLock. For example if you have a collection of Arc<RwLock<T>>, you can replace them with Arc<QCell<T>>. Essentially you’re exchanging the fine-grained locking (one for every single T) for a coarse-grained lock around the QCellOwner. Depending on the access patterns, this might work out better or worse. For example if you often need to access several T instances in one logical operation, and there is low contention on the big lock, then it will work out better. Or if you already have &mut on the struct containing the QCellOwner, then you get access to the T instances essentially for free.

no_std support

There are four levels at which qcell crate can be built:

  • Full std support, which is the default

  • no_std with exclusion-set, when built with --no-default-features and --features exclusion-set

  • no_std with alloc, when built with --no-default-features and --features alloc

  • no_std without alloc, when built with --no-default-features

Both QCell and LCell support all four levels, and TCell is also available for the first two.

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, doctest_lcell, doctest_qcell_noalloc and doctest_lcell_generativity modules, whose docs and doc-tests show which unsafe patterns are blocked.

Re-exports

Modules

Structs