core/

cell.rs

//! Shareable mutable containers.
//!
//! Rust memory safety is based on this rule: Given an object `T`, it is only possible to
//! have one of the following:
//!
//! - Several immutable references (`&T`) to the object (also known as **aliasing**).
//! - One mutable reference (`&mut T`) to the object (also known as **mutability**).
//!
//! This is enforced by the Rust compiler. However, there are situations where this rule is not
//! flexible enough. Sometimes it is required to have multiple references to an object and yet
//! mutate it.
//!
//! Shareable mutable containers exist to permit mutability in a controlled manner, even in the
//! presence of aliasing. [`Cell<T>`], [`RefCell<T>`], and [`OnceCell<T>`] allow doing this in
//! a single-threaded way—they do not implement [`Sync`]. (If you need to do aliasing and
//! mutation among multiple threads, [`Mutex<T>`], [`RwLock<T>`], [`OnceLock<T>`] or [`atomic`]
//! types are the correct data structures to do so).
//!
//! Values of the `Cell<T>`, `RefCell<T>`, and `OnceCell<T>` types may be mutated through shared
//! references (i.e. the common `&T` type), whereas most Rust types can only be mutated through
//! unique (`&mut T`) references. We say these cell types provide 'interior mutability'
//! (mutable via `&T`), in contrast with typical Rust types that exhibit 'inherited mutability'
//! (mutable only via `&mut T`).
//!
//! Cell types come in four flavors: `Cell<T>`, `RefCell<T>`, `OnceCell<T>`, and `LazyCell<T>`.
//! Each provides a different way of providing safe interior mutability.
//!
//! ## `Cell<T>`
//!
//! [`Cell<T>`] implements interior mutability by moving values in and out of the cell. That is, a
//! `&T` to the inner value can never be obtained, and the value itself cannot be directly
//! obtained without replacing it with something else. This type provides the following
//! methods:
//!
//!  - For types that implement [`Copy`], the [`get`](Cell::get) method retrieves the current
//!    interior value by duplicating it.
//!  - For types that implement [`Default`], the [`take`](Cell::take) method replaces the current
//!    interior value with [`Default::default()`] and returns the replaced value.
//!  - All types have:
//!    - [`replace`](Cell::replace): replaces the current interior value and returns the replaced
//!      value.
//!    - [`into_inner`](Cell::into_inner): this method consumes the `Cell<T>` and returns the
//!      interior value.
//!    - [`set`](Cell::set): this method replaces the interior value, dropping the replaced value.
//!
//! `Cell<T>` is typically used for more simple types where copying or moving values isn't too
//! resource intensive (e.g. numbers), and should usually be preferred over other cell types when
//! possible. For larger and non-copy types, `RefCell` provides some advantages.
//!
//! ## `RefCell<T>`
//!
//! [`RefCell<T>`] uses Rust's lifetimes to implement "dynamic borrowing", a process whereby one can
//! claim temporary, exclusive, mutable access to the inner value. Borrows for `RefCell<T>`s are
//! tracked at _runtime_, unlike Rust's native reference types which are entirely tracked
//! statically, at compile time.
//!
//! An immutable reference to a `RefCell`'s inner value (`&T`) can be obtained with
//! [`borrow`](`RefCell::borrow`), and a mutable borrow (`&mut T`) can be obtained with
//! [`borrow_mut`](`RefCell::borrow_mut`). When these functions are called, they first verify that
//! Rust's borrow rules will be satisfied: any number of immutable borrows are allowed or a
//! single mutable borrow is allowed, but never both. If a borrow is attempted that would violate
//! these rules, the thread will panic.
//!
//! The corresponding [`Sync`] version of `RefCell<T>` is [`RwLock<T>`].
//!
//! ## `OnceCell<T>`
//!
//! [`OnceCell<T>`] is somewhat of a hybrid of `Cell` and `RefCell` that works for values that
//! typically only need to be set once. This means that a reference `&T` can be obtained without
//! moving or copying the inner value (unlike `Cell`) but also without runtime checks (unlike
//! `RefCell`). However, its value can also not be updated once set unless you have a mutable
//! reference to the `OnceCell`.
//!
//! `OnceCell` provides the following methods:
//!
//! - [`get`](OnceCell::get): obtain a reference to the inner value
//! - [`set`](OnceCell::set): set the inner value if it is unset (returns a `Result`)
//! - [`get_or_init`](OnceCell::get_or_init): return the inner value, initializing it if needed
//! - [`get_mut`](OnceCell::get_mut): provide a mutable reference to the inner value, only available
//!   if you have a mutable reference to the cell itself.
//!
//! The corresponding [`Sync`] version of `OnceCell<T>` is [`OnceLock<T>`].
//!
//! ## `LazyCell<T, F>`
//!
//! A common pattern with OnceCell is, for a given OnceCell, to use the same function on every
//! call to [`OnceCell::get_or_init`] with that cell. This is what is offered by [`LazyCell`],
//! which pairs cells of `T` with functions of `F`, and always calls `F` before it yields `&T`.
//! This happens implicitly by simply attempting to dereference the LazyCell to get its contents,
//! so its use is much more transparent with a place which has been initialized by a constant.
//!
//! More complicated patterns that don't fit this description can be built on `OnceCell<T>` instead.
//!
//! `LazyCell` works by providing an implementation of `impl Deref` that calls the function,
//! so you can just use it by dereference (e.g. `*lazy_cell` or `lazy_cell.deref()`).
//!
//! The corresponding [`Sync`] version of `LazyCell<T, F>` is [`LazyLock<T, F>`].
//!
//! # When to choose interior mutability
//!
//! The more common inherited mutability, where one must have unique access to mutate a value, is
//! one of the key language elements that enables Rust to reason strongly about pointer aliasing,
//! statically preventing crash bugs. Because of that, inherited mutability is preferred, and
//! interior mutability is something of a last resort. Since cell types enable mutation where it
//! would otherwise be disallowed though, there are occasions when interior mutability might be
//! appropriate, or even *must* be used, e.g.
//!
//! * Introducing mutability 'inside' of something immutable
//! * Implementation details of logically-immutable methods.
//! * Mutating implementations of [`Clone`].
//!
//! ## Introducing mutability 'inside' of something immutable
//!
//! Many shared smart pointer types, including [`Rc<T>`] and [`Arc<T>`], provide containers that can
//! be cloned and shared between multiple parties. Because the contained values may be
//! multiply-aliased, they can only be borrowed with `&`, not `&mut`. Without cells it would be
//! impossible to mutate data inside of these smart pointers at all.
//!
//! It's very common then to put a `RefCell<T>` inside shared pointer types to reintroduce
//! mutability:
//!
//! ```
//! use std::cell::{RefCell, RefMut};
//! use std::collections::HashMap;
//! use std::rc::Rc;
//!
//! fn main() {
//!     let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
//!     // Create a new block to limit the scope of the dynamic borrow
//!     {
//!         let mut map: RefMut<'_, _> = shared_map.borrow_mut();
//!         map.insert("africa", 92388);
//!         map.insert("kyoto", 11837);
//!         map.insert("piccadilly", 11826);
//!         map.insert("marbles", 38);
//!     }
//!
//!     // Note that if we had not let the previous borrow of the cache fall out
//!     // of scope then the subsequent borrow would cause a dynamic thread panic.
//!     // This is the major hazard of using `RefCell`.
//!     let total: i32 = shared_map.borrow().values().sum();
//!     println!("{total}");
//! }
//! ```
//!
//! Note that this example uses `Rc<T>` and not `Arc<T>`. `RefCell<T>`s are for single-threaded
//! scenarios. Consider using [`RwLock<T>`] or [`Mutex<T>`] if you need shared mutability in a
//! multi-threaded situation.
//!
//! ## Implementation details of logically-immutable methods
//!
//! Occasionally it may be desirable not to expose in an API that there is mutation happening
//! "under the hood". This may be because logically the operation is immutable, but e.g., caching
//! forces the implementation to perform mutation; or because you must employ mutation to implement
//! a trait method that was originally defined to take `&self`.
//!
//! ```
//! # #![allow(dead_code)]
//! use std::cell::OnceCell;
//!
//! struct Graph {
//!     edges: Vec<(i32, i32)>,
//!     span_tree_cache: OnceCell<Vec<(i32, i32)>>
//! }
//!
//! impl Graph {
//!     fn minimum_spanning_tree(&self) -> Vec<(i32, i32)> {
//!         self.span_tree_cache
//!             .get_or_init(|| self.calc_span_tree())
//!             .clone()
//!     }
//!
//!     fn calc_span_tree(&self) -> Vec<(i32, i32)> {
//!         // Expensive computation goes here
//!         vec![]
//!     }
//! }
//! ```
//!
//! ## Mutating implementations of `Clone`
//!
//! This is simply a special - but common - case of the previous: hiding mutability for operations
//! that appear to be immutable. The [`clone`](Clone::clone) method is expected to not change the
//! source value, and is declared to take `&self`, not `&mut self`. Therefore, any mutation that
//! happens in the `clone` method must use cell types. For example, [`Rc<T>`] maintains its
//! reference counts within a `Cell<T>`.
//!
//! ```
//! use std::cell::Cell;
//! use std::ptr::NonNull;
//! use std::process::abort;
//! use std::marker::PhantomData;
//!
//! struct Rc<T: ?Sized> {
//!     ptr: NonNull<RcInner<T>>,
//!     phantom: PhantomData<RcInner<T>>,
//! }
//!
//! struct RcInner<T: ?Sized> {
//!     strong: Cell<usize>,
//!     refcount: Cell<usize>,
//!     value: T,
//! }
//!
//! impl<T: ?Sized> Clone for Rc<T> {
//!     fn clone(&self) -> Rc<T> {
//!         self.inc_strong();
//!         Rc {
//!             ptr: self.ptr,
//!             phantom: PhantomData,
//!         }
//!     }
//! }
//!
//! trait RcInnerPtr<T: ?Sized> {
//!
//!     fn inner(&self) -> &RcInner<T>;
//!
//!     fn strong(&self) -> usize {
//!         self.inner().strong.get()
//!     }
//!
//!     fn inc_strong(&self) {
//!         self.inner()
//!             .strong