cactusref/lib.rs
1#![feature(
2 allocator_api,
3 core_intrinsics,
4 dropck_eyepatch,
5 layout_for_ptr,
6 set_ptr_value,
7 slice_ptr_get
8)]
9#![allow(incomplete_features)]
10#![allow(internal_features)]
11#![warn(clippy::all)]
12#![warn(clippy::pedantic)]
13#![warn(clippy::cargo)]
14#![allow(clippy::cast_possible_wrap)]
15#![allow(clippy::inline_always)]
16#![allow(clippy::let_underscore_untyped)]
17#![allow(clippy::manual_let_else)]
18#![allow(clippy::missing_panics_doc)]
19#![allow(clippy::needless_pass_by_ref_mut)]
20#![allow(clippy::option_if_let_else)]
21#![allow(clippy::ref_as_ptr)]
22#![allow(clippy::too_long_first_doc_paragraph)]
23#![allow(unknown_lints)]
24#![warn(missing_copy_implementations)]
25#![warn(missing_debug_implementations)]
26#![warn(missing_docs)]
27#![warn(rust_2018_idioms)]
28#![warn(unused_qualifications)]
29#![warn(variant_size_differences)]
30
31//! Single-threaded, cycle-aware, reference-counting pointers. 'Rc' stands
32//! for 'Reference Counted'.
33//!
34//! The type [`Rc<T>`] provides shared ownership of a value of type `T`,
35//! allocated in the heap. Invoking [`clone`] on [`Rc`] produces a new pointer
36//! to the same value in the heap. When the last externally reachable [`Rc`]
37//! pointer to a given value is destroyed, the pointed-to value is also
38//! destroyed.
39//!
40//! [`Rc<T>`]: crate::Rc
41//! [`clone`]: Clone::clone
42//!
43//! `Rc` can **detect and deallocate cycles** of `Rc`s through the use of
44//! [`Adopt`]. Cycle detection is opt-in and no reachability checks are
45//! performed unless graphs have adoptions.
46//!
47//! # Nightly
48//!
49//! CactusRef depends on several unstable Rust features and can only be built
50//! on a nightly toolchain.
51//!
52//! # Maturity
53//!
54//! CactusRef is experimental. This crate has several limitations:
55//!
56//! - CactusRef is nightly only.
57//! - Cycle detection requires [unsafe code][adopt-api] to use.
58//!
59//! CactusRef is a non-trivial extension to `std::rc::Rc` and has not been
60//! proven to be safe. Although CactusRef makes a best effort to abort the
61//! program if it detects a dangling `Rc`, this crate may be unsound.
62//!
63//! [adopt-api]: crate::Adopt
64//!
65//! # CactusRef vs. `std::rc`
66//!
67//! The `Rc` in CactusRef is derived from [`std::rc::Rc`] and CactusRef
68//! implements most of the API from `std`.
69//!
70//! CactusRef does not implement the following APIs that are present on
71//! [`std::rc::Rc`]:
72//!
73//! - [`std::rc::Rc::downcast`]
74//! - [`CoerceUnsized`]
75//! - [`DispatchFromDyn`]
76//! - `From<Cow<'_, T>>`
77//!
78//! CactusRef cannot be used with unsized types like `[T]` or `str`.
79//!
80//! If you do not depend on these APIs, CactusRef is a drop-in replacement for
81//! [`std::rc::Rc`].
82//!
83//! Like [`std::rc`], [`Rc`] and [`Weak`] are not `Send` and are not `Sync`.
84//!
85//! [`std::rc`]: https://doc.rust-lang.org/stable/std/rc/index.html
86//!
87//! # Building an object graph
88//!
89//! CactusRef smart pointers can be used to implement a tracing garbage
90//! collector local to a graph objects. Graphs of CactusRefs are cycle-aware and
91//! can deallocate a cycle of strong references that is otherwise unreachable
92//! from the rest of the object graph, unlike [`std::rc::Rc`].
93//!
94//! `CactusRef` relies on proper use of [`Adopt::adopt_unchecked`] and [`Adopt::unadopt`]
95//! to maintain bookkeeping about the object graph for breaking cycles. These
96//! functions are unsafe because improperly managing the bookkeeping can cause
97//! the `Rc` drop implementation to deallocate cycles while they are still
98//! externally reachable. Failure to uphold [`Adopt`]'s safety invariants will
99//! result in *[undefined behavior]* and held `Rc`s that point to members of the
100//! now deallocated cycle may dangle.
101//!
102//! [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
103//!
104//! CactusRef makes a best-effort attempt to abort the program if it detects an
105//! access to a dangling `Rc`.
106//!
107//! # Cycle Detection
108//!
109//! `Rc` implements [`Adopt`] to log bookkeeping entries for strong ownership
110//! links to other `Rc`s that may form a cycle. The ownership links tracked by
111//! these bookkeeping entries form an object graph of reachable `Rc`s. On
112//! `drop`, `Rc` uses these entries to conduct a reachability trace of the
113//! object graph to determine if it is part of an _orphaned cycle_. An orphaned
114//! cycle is a cycle where the only strong references to all nodes in the cycle
115//! come from other nodes in the cycle.
116//!
117//! Cycle detection is a zero-cost abstraction. If you never
118//! `use cactusref::Adopt;`, `drop` uses the same implementation as
119//! [`std::rc::Rc`] (and leaks in the same way as `std::rc::Rc` if you form a
120//! cycle of strong references). The only costs you pay are the memory costs of
121//! one empty hash map used to track adoptions and an if statement to check if
122//! these structures are empty on `drop`.
123//!
124//! Cycle detection uses breadth-first search for traversing the object graph.
125//! The algorithm supports arbitrarily large object graphs and will not overflow
126//! the stack during the reachability trace.
127//!
128//! [`std::rc::Rc`]: alloc::rc::Rc
129//! [`std::rc::Rc::downcast`]: alloc::rc::Rc::downcast
130//! [`CoerceUnsized`]: core::ops::CoerceUnsized
131//! [`DispatchFromDyn`]: core::ops::DispatchFromDyn
132
133#![doc(html_root_url = "https://docs.rs/cactusref/0.5.0")]
134#![no_std]
135
136// Ensure code blocks in README.md compile
137#[cfg(doctest)]
138#[doc = include_str!("../README.md")]
139mod readme {}
140
141extern crate alloc;
142#[cfg(any(feature = "std", test, doctest, miri))]
143extern crate std;
144#[macro_use]
145extern crate log;
146
147mod adopt;
148mod cycle;
149mod drop;
150mod hash;
151mod link;
152mod rc;
153
154// Doc modules
155#[cfg(any(doctest, docsrs))]
156#[path = "doc/implementing_self_referential_data_structures.rs"]
157/// Examples of implementing self-referential data structures with CactusRef.
158pub mod implementing_self_referential_data_structures;
159
160pub use adopt::Adopt;
161pub use rc::Rc;
162pub use rc::Weak;
163
164/// Cactus alias for [`Rc`].
165pub type CactusRef<T> = Rc<T>;
166
167/// Cactus alias for [`Weak`].
168pub type CactusWeakRef<T> = Weak<T>;