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
#![feature(
allocator_api,
core_intrinsics,
dropck_eyepatch,
layout_for_ptr,
set_ptr_value,
slice_ptr_get
)]
#![allow(incomplete_features)]
#![allow(internal_features)]
#![warn(clippy::all)]
#![warn(clippy::pedantic)]
#![warn(clippy::cargo)]
#![allow(clippy::cast_possible_wrap)]
#![allow(clippy::inline_always)]
#![allow(clippy::let_underscore_untyped)]
#![allow(clippy::manual_let_else)]
#![allow(clippy::missing_panics_doc)]
#![allow(clippy::option_if_let_else)]
#![allow(clippy::needless_pass_by_ref_mut)]
#![allow(clippy::ref_as_ptr)]
#![allow(unknown_lints)]
#![warn(missing_copy_implementations)]
#![warn(missing_debug_implementations)]
#![warn(missing_docs)]
#![warn(rust_2018_idioms)]
#![warn(unused_qualifications)]
#![warn(variant_size_differences)]
//! Single-threaded, cycle-aware, reference-counting pointers. 'Rc' stands
//! for 'Reference Counted'.
//!
//! The type [`Rc<T>`] provides shared ownership of a value of type `T`,
//! allocated in the heap. Invoking [`clone`] on [`Rc`] produces a new pointer
//! to the same value in the heap. When the last externally reachable [`Rc`]
//! pointer to a given value is destroyed, the pointed-to value is also
//! destroyed.
//!
//! [`Rc<T>`]: crate::Rc
//! [`clone`]: Clone::clone
//!
//! `Rc` can **detect and deallocate cycles** of `Rc`s through the use of
//! [`Adopt`]. Cycle detection is opt-in and no reachability checks are
//! performed unless graphs have adoptions.
//!
//! # Nightly
//!
//! CactusRef depends on several unstable Rust features and can only be built
//! on a nightly toolchain.
//!
//! # Maturity
//!
//! CactusRef is experimental. This crate has several limitations:
//!
//! - CactusRef is nightly only.
//! - Cycle detection requires [unsafe code][adopt-api] to use.
//!
//! CactusRef is a non-trivial extension to `std::rc::Rc` and has not been
//! proven to be safe. Although CactusRef makes a best effort to abort the
//! program if it detects a dangling `Rc`, this crate may be unsound.
//!
//! [adopt-api]: crate::Adopt
//!
//! # CactusRef vs. `std::rc`
//!
//! The `Rc` in CactusRef is derived from [`std::rc::Rc`] and CactusRef
//! implements most of the API from `std`.
//!
//! CactusRef does not implement the following APIs that are present on
//! [`std::rc::Rc`]:
//!
//! - [`std::rc::Rc::downcast`]
//! - [`CoerceUnsized`]
//! - [`DispatchFromDyn`]
//! - `From<Cow<'_, T>>`
//!
//! CactusRef cannot be used with unsized types like `[T]` or `str`.
//!
//! If you do not depend on these APIs, CactusRef is a drop-in replacement for
//! [`std::rc::Rc`].
//!
//! Like [`std::rc`], [`Rc`] and [`Weak`] are not `Send` and are not `Sync`.
//!
//! [`std::rc`]: https://doc.rust-lang.org/stable/std/rc/index.html
//!
//! # Building an object graph
//!
//! CactusRef smart pointers can be used to implement a tracing garbage
//! collector local to a graph objects. Graphs of CactusRefs are cycle-aware and
//! can deallocate a cycle of strong references that is otherwise unreachable
//! from the rest of the object graph, unlike [`std::rc::Rc`].
//!
//! `CactusRef` relies on proper use of [`Adopt::adopt_unchecked`] and [`Adopt::unadopt`]
//! to maintain bookkeeping about the object graph for breaking cycles. These
//! functions are unsafe because improperly managing the bookkeeping can cause
//! the `Rc` drop implementation to deallocate cycles while they are still
//! externally reachable. Failure to uphold [`Adopt`]'s safety invariants will
//! result in *[undefined behavior]* and held `Rc`s that point to members of the
//! now deallocated cycle may dangle.
//!
//! [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
//!
//! CactusRef makes a best-effort attempt to abort the program if it detects an
//! access to a dangling `Rc`.
//!
//! # Cycle Detection
//!
//! `Rc` implements [`Adopt`] to log bookkeeping entries for strong ownership
//! links to other `Rc`s that may form a cycle. The ownership links tracked by
//! these bookkeeping entries form an object graph of reachable `Rc`s. On
//! `drop`, `Rc` uses these entries to conduct a reachability trace of the
//! object graph to determine if it is part of an _orphaned cycle_. An orphaned
//! cycle is a cycle where the only strong references to all nodes in the cycle
//! come from other nodes in the cycle.
//!
//! Cycle detection is a zero-cost abstraction. If you never
//! `use cactusref::Adopt;`, `drop` uses the same implementation as
//! [`std::rc::Rc`] (and leaks in the same way as `std::rc::Rc` if you form a
//! cycle of strong references). The only costs you pay are the memory costs of
//! one empty hash map used to track adoptions and an if statement to check if
//! these structures are empty on `drop`.
//!
//! Cycle detection uses breadth-first search for traversing the object graph.
//! The algorithm supports arbitrarily large object graphs and will not overflow
//! the stack during the reachability trace.
//!
//! [`std::rc::Rc`]: alloc::rc::Rc
//! [`std::rc::Rc::downcast`]: alloc::rc::Rc::downcast
//! [`CoerceUnsized`]: core::ops::CoerceUnsized
//! [`DispatchFromDyn`]: core::ops::DispatchFromDyn
#![doc(html_root_url = "https://docs.rs/cactusref/0.5.0")]
#![no_std]
// Ensure code blocks in README.md compile
#[cfg(doctest)]
#[doc = include_str!("../README.md")]
mod readme {}
extern crate alloc;
#[cfg(any(feature = "std", test, doctest, miri))]
extern crate std;
#[macro_use]
extern crate log;
mod adopt;
mod cycle;
mod drop;
mod hash;
mod link;
mod rc;
// Doc modules
#[cfg(any(doctest, docsrs))]
#[path = "doc/implementing_self_referential_data_structures.rs"]
/// Examples of implementing self-referential data structures with CactusRef.
pub mod implementing_self_referential_data_structures;
pub use adopt::Adopt;
pub use rc::Rc;
pub use rc::Weak;
/// Cactus alias for [`Rc`].
pub type CactusRef<T> = Rc<T>;
/// Cactus alias for [`Weak`].
pub type CactusWeakRef<T> = Weak<T>;