Crate cactusref

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 can detect and deallocate cycles of Rcs 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 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.

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.

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 Rcs that point to members of the now deallocated cycle may dangle.

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 Rcs that may form a cycle. The ownership links tracked by these bookkeeping entries form an object graph of reachable Rcs. 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.

Modules

• implementing_self_referential_data_structures
  Examples of implementing self-referential data structures with CactusRef. CactusRef can be used to implement collections that own strong references to themselves.

Structs

• Rc
  A single-threaded reference-counting pointer. ‘Rc’ stands for ‘Reference Counted’.
• Weak
  Weak is a version of Rc that holds a non-owning reference to the managed allocation. The allocation is accessed by calling upgrade on the Weak pointer, which returns an Option<Rc<T>>.

Traits

• Adopt
  Build a graph of linked Rc smart pointers to enable busting cycles on drop.

Type Aliases

• CactusRef
  Cactus alias for Rc.
• CactusWeakRef
  Cactus alias for Weak.