Module unsafe_linked_general_tree

An unsafe, linked, n-ary tree implementation

About

Following classical DSA curricula, this implementation relies primarily on pointers for the structure’s composition and navigation.

See the module’s companion MD tree tool, which takes a Markdown document and prints a hierarchical tree diagram of its heading contents.

Design

The base GenTree structure only contains basic operations for constructors and metadata retrieval. Most of the magic happens in the CursorMut struct. Both structs rely on a [Position] struct, which provides a safe handle to all the raw pointers required to make the tree go brrr.

The design makes heavy use of unsafe code via raw pointers. The module represents a two-fold exercise: writing recursive traversal functions and understanding Rust’s ownership model well enough to avoid falling back on tricks such as reference counting (std::rc::Rc/std::sync::Arc) or arena-like allocation with safe indexing (Vec) to manage the structure’s operations safely.

Notably, this structure enforces strict lifetime constraints on cursors and positions to lock them to the base tree allocation, utilizing Rust’s variance rules to systematically prevent pointer dangling, cross-tree pointer smuggling, and use-after-free errors.

In addition to leveraging lifetimes for safety bounds, the module also uses Cell for interior mutability on CursorMut. This allows cursor navigation methods to retain immutable &self borrows for a more ergonomic API.

Modules

md_tree

A handy little tool to create tree diagrams from MD headings

Structs

ChildIter

CursorMut

CursorMut takes ’a to tie it to the tree’s lifetime which prevents dangling pointers by gating scopes

GenTree

Represents the actual data structure. Currently this struct only has constructor methods to create a new tree and create new cursor handles which provide the lion’s share of tree operations.

Node

Has no methods, but Position has methods to derive and create Nodes.