Non-Nested Lifetimes in Goose: Memory Pools & Graphs
Learn how Goose handles complex non-nested lifetimes, cyclic graphs, and directory trees using slot_pool and slice_pool without a general heap or GC.
In our previous deep dive, we explored the radical architectural premise of Goose: a modern systems programming language that completely eliminates general-purpose heap allocations, discards garbage collection, and automatically reclaims data on compiler-managed Data Stacks at lexical scope boundaries.
However, an experienced systems engineer encountering this model will immediately raise an essential architectural challenge:
“If all dynamic values are tied to lexical scopes on Data Stacks, how do we represent data structures with non-nested lifetimes? How do we build arbitrary N-ary directory trees where nodes are created and deleted out of order, cyclic graphs, game entity-component systems (ECS), or LRU caches?”
In C and C++, developers tackle this via malloc/free, paying the price in use-after-free vulnerabilities and heap fragmentation. In Rust, handling cyclic graphs is notoriously difficult, requiring heavy machinery like Rc<RefCell<T>>, Arc<Mutex<T>>, or external crates like SlotMap backed by generational integer indices.
Goose provides an elegant, safe, and cache-friendly alternative: Memory Pools (slot_pool<T> and slice_pool<T>).
1. The Core Dilemma: Non-Lexical Data Lifetimes#
Consider a standard filesystem directory tree:
/ (root)
├─bin/
│ ├─app
│ └─util
└─docs/
└─readme.mdtextIn real-world usage, files and directories are created, renamed, modified, and deleted in completely arbitrary order. Node lifecycles do not obey the strict Last-In-First-Out (LIFO) discipline of the call stack.
If an architecture only offered linear data stacks:
- You could not delete an intermediate node in a growable array without shuffling all subsequent entries.
- You could not reclaim individual allocations while neighboring elements remain active.
To bridge this gap without reintroducing a fragmented system heap, Goose provides two complementary standard abstractions: slot_pool<T> and slice_pool<T>.
2. Dual Pool Architecture: slot_pool and slice_pool#
1. slot_pool<T>: Fixed-Size Node Management#
- Combines a grow-only backing array (
T[>..]) anchored to a Data Stack with a fast in-memory freelist. alloc_ref(value): Checks the freelist for previously deleted slots. If one exists, it recycles that slot instantly. If the freelist is empty, it advances the stack bump pointer (push) to append a new element.free(slot): Does not return memory to the OS kernel! It simply registers the slot’s index back onto the freelist for subsequent reuse.
2. slice_pool<T>: Contiguous Dynamic Run Management#
- Designed for child lists and variable-length collections (e.g., directory children or adjacency lists).
- Exposes primitive operations:
alloc_slice(n),realloc_slice(s, n), andfree_slice(s). - When a slice is released,
slice_poolautomatically merges adjacent free memory spans, preventing fragmentation without requiring OS heap defragmentation.
3. The Security Guarantee: Type-Safe Reuse#
What makes free() in C and C++ so perilous? Once memory is deallocated, the OS may reassign that physical address space to an entirely different subsystem or data structure. If a dangling pointer reads that location later, it triggers segmentation faults or catastrophic Remote Code Execution (RCE) exploits.
Goose neutralizes this threat through Type-Safe Reuse:
[!TIP] The Goose Safety Invariant: Memory assigned to a pool’s backing array is never returned to the OS until the entire pool’s scope exits. If application logic accidentally dereferences a stale link to a freed slot, it simply reads whatever valid record of type
Tcurrently occupies that slot. It may be a logical bug, but it is physically incapable of causing memory corruption, wild pointer jumps, or arbitrary code execution!
4. Production Walkthrough: The N-ary File Tree (26_file_tree.goose)#
Let us examine how Goose coordinates pools in a real-world directory tree implementation from the official repository:
// A 4-byte narrow relative reference anchored to the 'nodes' pool base
type Link = Node&<u32 in nodes>?;
struct Node {
name: u8[..15], // Fixed inline name (up to 15 bytes)
entries: Link[:], // Contiguous slice of links to child nodes
}
// Instantiate both backing pools
reusable var nodes: Node[>..] = [];
reusable[] var runs: Link[>..] = [];
// Construct a new directory node within the pool
fn make(name: u8[:]) -> Node& {
return nodes.alloc_ref(Node {
name: name,
entries: runs.alloc_slice(0)
});
}
// Create the root directory
let root .= make("/");
// Append a child link to a directory node
fn link(dir: Node&, n: Node&) {
let k = dir.entries.len;
// Reallocate the slice within the runs pool
dir.entries = runs.realloc_slice(dir.entries, k + 1);
dir.entries[k] .= n;
}
// Add a named file or folder
fn add(dir: Node&, name: u8[:]) -> Node& {
let n .= make(name);
link(dir, n);
return n;
}
// Build directory hierarchies naturally:
let home .= add(root, "home");
let user .= add(home, "alice");
let doc .= add(user, "project.txt");rustArchitectural Highlights#
- Ultra-Narrow 4-Byte Links (
Node&<u32 in nodes>?): Rather than consuming 8 bytes for a full virtual pointer, parent-child connections consume only 4 bytes (a 32-bit offset relative to the base of thenodespool). A value of0cleanly representsnullvia?. - Cache-Friendly Contiguous Child Traversal:
A directory’s children are represented as
entries: Link[:]. Walking a directory’s contents streams through a linear, flat memory block with zero pointer-chasing overhead. - In-Place Slice Expansion:
realloc_slicegrows child runs in-place if contiguous unallocated space remains immediately after the slice. If blocked by adjacent data, it relocates the run to the end of the pool and marks the prior span free. - Zero System Heap Overhead: Millions of tree nodes reside exclusively across two pre-allocated Data Stacks. When the directory operation finishes and the enclosing scope terminates, the entire tree structure is reclaimed in two CPU store operations!
5. Seamless Cyclic Graphs#
In Rust, constructing cyclic graphs (Node A points to B, B points to C, and C points back to A) is notoriously complex, frequently running afoul of the borrow checker. In C++, circular references with std::shared_ptr inevitably cause memory leaks unless manually mitigated with std::weak_ptr.
In Goose, cyclic graphs require zero runtime reference counters and zero unsafe blocks:
struct Vertex {
id: i32,
neighbors: VertexLink[:]
}
type VertexLink = Vertex&<u32 in vertices>?;
reusable var vertices: Vertex[>..] = [];
reusable[] var edges: VertexLink[>..] = [];
fn create_vertex(id: i32) -> Vertex& {
return vertices.alloc_ref(Vertex {
id: id,
neighbors: edges.alloc_slice(0)
});
}
fn add_edge(from: Vertex&, to: Vertex&) {
let k = from.neighbors.len;
from.neighbors = edges.realloc_slice(from.neighbors, k + 1);
from.neighbors[k] .= to;
}
// Construct a directed triangle cycle: A -> B -> C -> A
let vA .= create_vertex(1);
let vB .= create_vertex(2);
let vC .= create_vertex(3);
add_edge(vA, vB);
add_edge(vB, vC);
add_edge(vC, vA); // Compiles cleanly, executes safely, zero leaks!rustEvery vertex resides in vertices, and every edge resides in edges. Because cleanup happens in bulk when the pool scope terminates, cyclic cross-references never obstruct deallocation.
6. Technical Comparison: Graph Representations Across Languages#
| Attribute | C++ (std::shared_ptr) | Rust (Rc<RefCell<T>>) | Rust (SlotMap + Id) | Goose (slot_pool + slice_pool) |
|---|---|---|---|---|
| Syntax Overhead | High, prone to cyclic leaks | Heavy boilerplate, runtime panics | Requires manual ID lookups | Natural, transparent .= syntax |
| Link Size | 16 bytes (ptr + control block) | 16 bytes (ptr + strong/weak counts) | 8 bytes (Index + Generation) | 4 bytes (Node&<u32>) |
| Allocation Cost | 1 heap allocation / node | 1 heap allocation / node | Auxiliary array reallocations | Pointer bump () |
| Deallocation Cost | Cascading ref count decrements | Cascading ref count decrements | Array drop | Single CPU store at scope exit |
| Cycle Leak Resistance | ❌ Leaks without weak_ptr | ❌ Leaks without Weak | ✅ Cleaned on map drop | ✅ Zero leaks guaranteed |
7. Conclusion#
Goose’s Memory Pools demonstrate that systems software does not need to compromise between structural flexibility and rock-solid memory safety:
- You do not need a Garbage Collector to clean up complex graphs.
- You do not need a restrictive borrow checker to interlink cyclical nodes.
- You do not need an OS heap allocator with its fragmentation and synchronization lock contention.
By pairing compiler-managed Data Stacks, slot_pool abstractions, and compact 4-byte relative references, Goose provides an extraordinary blueprint for building fast, small, and completely safe systems software.