rec_cell 0.1.0

//! Zero-cost borrow-checking of aliased references supporting cyclic
//! construction.
//!
//! [`RecCell`] enforces borrow checking rules using a [`RecToken`], created
//! with [`RecToken::new`]. This creates a scope where the token grants
//! access to associated `RecCell`s:
//!
//! - `&RecToken` borrows a cell as `&T`.
//! - `&mut RecToken` borrows a cell as `&mut T`.
//!
//! Each cell is associated with exactly one token, and mismatched access is a
//! compile error. The correctness of the design above has been proven in the
//! [GhostCell paper].
//!
//! # Building cycles directly
//!
//! On top of that, this crate experiments with providing cyclic constructors
//! like [`RecCell::new_cyclic`], similar in spirit to
//! [`Rc::new_cyclic`][std::rc::Rc::new_cyclic], to initialize a
//! caller-provided [`MaybeUninit`][core::mem::MaybeUninit] slot. The
//! initialization closure receives a reference to the future cell, then returns
//! the value to write into it. That constructed value is allowed to refer to
//! the cell itself, creating a cycle. To prohibit accessing the cell's contents
//! before it is initialized, the cyclic constructors take the `RecToken` by
//! value and return it only when construction succeeds.
//!
//! Such an API comes with the following caveats:
//!
//! - Cyclic constructors write a `T` into a `&mut MaybeUninit<T>`.
//!   `MaybeUninit` does not run `T`'s destructor, so cyclically initialized
//!   values **leak unless you explicitly drop them**.
//!
//! - Cyclic constructors provide a reference to an uninitialized cell that must
//!   not be accessed before initialization. If you fail to initialize the cell,
//!   the token needs to be forever lost, so every cell under the same token
//!   becomes permanently inaccessible by shared reference.
//!
//! - This crate does not allocate or own the storage. It is best paired with an
//!   arena or any other allocation mechanism that provides storage with stable
//!   addresses.
//!
//! # Cursors
//!
//! [`Cursor`]s are simple wrappers around (cell, &token) pairs and provide a
//! convenient way to traverse a structure of `RecCell`s. [`CursorMut`] provides
//! mutable access to the cell, and [`SliceCursor`] and [`SliceCursorMut`]
//! provide cursors over slices of `RecCell`s.
//!
//! From a safety perspective, they are just wrappers and anything that can be
//! done using them can also be done by managing the cell and token separately.
//!
//! # Initializing multiple cells cyclicly
//!
//! The [`RecToken::make_cyclic`] method generalizes [`RecCell::new_cyclic`] to
//! allow cyclicly initializing multiple cells at once. Arbitrary composition of
//! cyclic initializations is possible by making use of [`RecBuilder`], which is
//! used to check whether all initializations have been properly completed. If
//! any initialization fails, the builder is destroyed and the original
//! [`RecToken`] cannot be recovered, prohibiting access to uninitialized cells.
//! See [`RecToken::with_builder`] for more details.
//!
//! # Examples
//!
//! A self-referential node:
//!
//! ```
//! use std::mem::MaybeUninit;
//! use rec_cell::{RecCell, RecToken};
//!
//! struct Node<'a, 't> {
//!     value: u32,
//!     // No `Option` is needed, since we can cyclicly initialize the node to
//!     // indirectly refer to itself, without modifying the node after node creation.
//!     next: &'a RecCell<'t, Self>,
//! }
//!
//! RecToken::new(|token| {
//!     let [mut node0, mut node1, mut node2] = [const { MaybeUninit::<Node>::uninit() }; 3];
//!
//!     // Build a structure with node0 -> node1 -> node2 -> node0.
//!     let (nodes, token) = RecCell::new_cyclic(&mut node0, token, |n0| {
//!         let n2 = RecCell::from_mut(node2.write(Node { value: 20, next: n0 }));
//!         let n1 = RecCell::from_mut(node1.write(Node { value: 10, next: n2 }));
//!         let node0 = Node { value: 0, next: n1 };
//!         ([n0, n1, n2], node0)
//!     });
//!
//!     // Walk the structure with a cursor.
//!     let mut cursor = nodes[0].cursor(&token);
//!     let target = [0, 10, 20, 0, 10, 20];
//!     for i in 0..6 {
//!         assert_eq!(cursor.get().value, target[i]);
//!         cursor.update(|node| node.next);
//!     }
//! });
//! ```
//!
//! # Prior art
//!
//! This crate is heavily based on [`ghost_cell`] and [`qcell::LCell`], which
//! provide similar methods except that they do not permit cyclic
//! initialization.
//!
//! `RecCell` is almost a drop-in replacement for the non-experimental parts of
//! `GhostCell`, except that `RecCell<'_, T>` requires `T: Sized` due to
//! `MaybeUninit<T>` requiring `T: Sized`. Use `[RecCell<'_, T>]` to manage a
//! slice `[T]`.
//!
//! [`ghost_cell`]: https://docs.rs/ghost-cell
//! [`qcell::LCell`]: https://docs.rs/qcell/latest/qcell/struct.LCell.html
//! [GhostCell paper]: https://plv.mpi-sws.org/rustbelt/ghostcell/
#![no_std]
#![warn(missing_docs)]
#![warn(clippy::pedantic, clippy::cargo)]
#![warn(clippy::undocumented_unsafe_blocks)]
// All our errors arise from propagating closure errors.
#![allow(clippy::missing_errors_doc)]
#![cfg_attr(docsrs, allow(internal_features))]
#![cfg_attr(docsrs, feature(doc_cfg, rustdoc_internals))]

#[cfg(any(doc, test, feature = "std"))]
extern crate std;

mod builder;
mod cell;
#[cfg(doc)]
mod compile_fail;
mod cursor;
#[cfg(test)]
mod tests;

pub use crate::{
    builder::{CyclicBuildable, RecBuilder},
    cell::{RecCell, RecToken},
    cursor::{CellLike, Cursor, CursorMut, SliceCursor, SliceCursorMut},
};

mod utils {
    use core::{convert::Infallible, marker::PhantomData};

    pub(crate) type Invariant<'a> = PhantomData<fn(&'a ()) -> &'a ()>;

    pub(crate) fn into_ok<T>(value: Result<T, Infallible>) -> T {
        let Ok(value) = value;
        value
    }
}