1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423
//! 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 `Rc`s) 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"](#comparison-of-cell-types) below.
//!
//! # Examples
//!
//! With [`RefCell`], this compiles but panics:
//!
//! ```should_panic
//!# use std::rc::Rc;
//!# use std::cell::RefCell;
//! 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:
//!
//! ```compile_fail
//!# use qcell::{QCell, QCellOwner};
//!# use std::rc::Rc;
//! 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:
//!
#![cfg_attr(
feature = "std",
doc = "
```
# use qcell::{TCell, TCellOwner};
# use std::rc::Rc;
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`]:
//!
//! ```
//!# use qcell::{LCell, LCellOwner};
//!# use std::rc::Rc;
//! 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
//! - 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.
//! - Con: Currently requires `std`
//!
//! [`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
//!
//! Cell | Owner ID | Cell overhead | Borrow check | Owner check | Owner creation check
//! ---|---|---|---|---|---
//! `RefCell` | n/a | `usize` | Runtime | n/a | n/a
//! `QCell` | integer | `usize` | Compile-time | Runtime | Runtime
//! `TCell` or `TLCell` | marker type | none | Compile-time | Compile-time | Runtime
//! `LCell` | lifetime | none | Compile-time | Compile-time | Compile-time
//!
//! Owner ergonomics:
//!
//! Cell | Owner type | Owner creation
//! ---|---|---
//! `RefCell` | n/a | n/a
//! `QCell` | `QCellOwner` | `QCellOwner::new()`
//! `TCell` or<br/>`TLCell` | `ACellOwner`<br/>(or `BCellOwner` or `CCellOwner` etc) | `struct MarkerA;`<br/>`type ACell<T> = TCell<MarkerA, T>;`<br/>`type ACellOwner = TCellOwner<MarkerA>;`<br/>`ACellOwner::new()`
//! `LCell` | `LCellOwner<'id>` | `LCellOwner::scope(`\|`owner`\|` { ... })`
//!
//! Cell ergonomics:
//!
//! Cell | Cell type | Cell creation
//! ---|---|---
//! `RefCell` | `RefCell<T>` | `RefCell::new(v)`
//! `QCell` | `QCell<T>` | `owner.cell(v)` or `QCell::new(&owner, v)`
//! `TCell` or `TLCell` | `ACell<T>` | `owner.cell(v)` or `ACell::new(v)`
//! `LCell` | `LCell<'id, T>` | `owner.cell(v)` or `LCell::new(v)`
//!
//! Borrowing ergonomics:
//!
//! Cell | Cell immutable borrow | Cell mutable borrow
//! ---|---|---
//! `RefCell` | `cell.borrow()` | `cell.borrow_mut()`
//! `QCell` | `cell.ro(&owner)` or<br/>`owner.ro(&cell)` | `cell.rw(&mut owner)` or<br/>`owner.rw(&cell)`
//! `TCell` or `TLCell` | `cell.ro(&owner)` or<br/>`owner.ro(&cell)` | `cell.rw(&mut owner)` or<br/>`owner.rw(&cell)`
//! `LCell` | `cell.ro(&owner)` or<br/>`owner.ro(&cell)` | `cell.rw(&mut owner)` or<br/>`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:
//!
//! Cell | Owner type | Cell type
//! ---|---|---
//! `RefCell` | n/a | Send
//! `QCell` | Send + Sync | Send + Sync
//! `TCell` | Send + Sync | Send + Sync
//! `TLCell` | | Send
//! `LCell` | Send + Sync | Send + 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](http://plv.mpi-sws.org/rustbelt/ghostcell/). 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 three levels at which **qcell** crate can be built:
//!
//! - Full `std` support, which is the default
//!
//! - `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 three levels.
//!
//! # 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.
//!
//! [`RefCell`]: https://doc.rust-lang.org/std/cell/struct.RefCell.html
//! [`RwLock`]: https://doc.rust-lang.org/std/sync/struct.RwLock.html
//! [`QCell`]: struct.QCell.html
//! [`QCellOwner`]: struct.QCellOwner.html
//! [`TCell`]: struct.TCell.html
//! [`TCellOwner`]: struct.TCellOwner.html
//! [`TLCell`]: struct.TLCell.html
//! [`TLCellOwner`]: struct.TLCellOwner.html
//! [`LCell`]: struct.LCell.html
//! [`LCellOwner`]: struct.LCellOwner.html
//! [`doctest_qcell`]: doctest_qcell/index.html
//! [`doctest_qcell_noalloc`]: doctest_qcell_noalloc/index.html
//! [`doctest_tcell`]: doctest_tcell/index.html
//! [`doctest_tlcell`]: doctest_tlcell/index.html
//! [`doctest_lcell`]: doctest_lcell/index.html
//! [`doctest_lcell_generativity`]: doctest_lcell_generativity/index.html
//! [**Migi**]: https://github.com/Migi
//! [**pythonesque**]: https://github.com/pythonesque
#![cfg_attr(not(any(feature = "std", test)), no_std)]
#![cfg_attr(docsrs, feature(doc_cfg))]
#![deny(rust_2018_idioms)]
#[cfg(feature = "alloc")]
extern crate alloc;
mod lcell;
mod qcell;
#[cfg(feature = "std")]
mod tcell;
#[cfg(feature = "std")]
mod tlcell;
pub mod doctest_lcell;
#[cfg(feature = "generativity")]
pub mod doctest_lcell_generativity;
#[cfg(feature = "alloc")]
pub mod doctest_qcell;
pub mod doctest_qcell_noalloc;
#[cfg(feature = "std")]
pub mod doctest_tcell;
#[cfg(feature = "std")]
pub mod doctest_tlcell;
#[cfg(feature = "generativity")]
pub extern crate generativity;
// Used in LCell, TCell and TLCell. See the Rustonomicon chapters
// "Subtyping and Variance"
// (https://doc.rust-lang.org/nomicon/subtyping.html) and
// "PhantomData"
// (https://doc.rust-lang.org/nomicon/phantom-data.html).
//
// `fn(T) -> T` forces T to be treated as invariant. This does not
// change the type of 'T', but changes what that type can be converted
// into. Variance in Rust only applies to lifetimes, so this is about
// blocking conversion of one lifetime into a larger or smaller one.
// We need invariance in the marker type for `TCell` and `TLCell`
// because otherwise it's possible for a malicious programmer to cheat
// the singleton check and obtain undefined behaviour.
//
// `fn(T) -> T` is better than `Cell<T>` or `*mut T` because it passes
// through the `UnwindSafe` trait unaffected.
//
// Needs an abstraction as a struct, since otherwise we'll get errors
// regarding "function pointers cannot appear in constant functions"
struct Invariant<T>(fn(T) -> T);
pub use crate::lcell::LCell;
pub use crate::lcell::LCellOwner;
pub use crate::qcell::QCell;
pub use crate::qcell::QCellOwnerID;
pub use crate::qcell::QCellOwnerPinned;
pub use crate::qcell::QCellOwnerSeq;
#[cfg(feature = "alloc")]
pub use crate::qcell::QCellOwner;
#[cfg(feature = "std")]
pub use crate::{tcell::TCell, tcell::TCellOwner, tlcell::TLCell, tlcell::TLCellOwner};
// Static assertions on traits
#[cfg(test)]
mod assertions;