Rust data structures with circular references (2021)

Original Article ↗ Hacker News Discussion ↗

Rust’s strict ownership and borrowing model makes common cyclic data structures, like trees with parent pointers or general graphs, awkward to express, prompting workarounds such as arenas with integer indices, `Rc`/`Weak` reference counting, `RefCell`, and external garbage collectors. Commenters argue over whether these techniques merely “launder” unsafe pointer logic or meaningfully improve memory safety by confining errors to panics and logic bugs instead of undefined behavior and remote code execution. The thread broadens into a comparison between Rust’s compile-time guarantees and alternatives like isoheap-based manual memory management or GC’d languages, with some seeing Rust’s constraints as productive discipline and others viewing them as unnecessary contortions for many real-world workloads.

Indices, arenas, and “laundered” pointers

  • Several comments critique “manual memory is fine, just use arenas + handles,” arguing it often just hides pointer arithmetic behind vector indices.
  • Others reply that indices are still safer than raw pointers due to bounds checks and defined panic behavior.
  • Memory savings from using small integer indices instead of pointers are highlighted as substantial in pointer-heavy structures.
  • Using indices is seen as good for locality and serialization, but also as easy to misuse (“handle confusion,” logical bugs, leaks).

What counts as memory safety

  • Long subthread debates whether bugs in index-based structures are “memory safety” issues.
  • One side: out-of-bounds or “use index after free” in safe Rust yields panics or logic errors, not UB or RCE, so still memory-safe in Rust’s sense.
  • Other side: you can still get two “owners” of the same logical object and serious semantic bugs, even if not UB.
  • Participants stress that Rust equates memory safety with absence of UB; disagreement arises when people use broader notions.

Encapsulating unsafe: Rust vs C/C++ and older languages

  • Strong view: C/C++ cannot enforce encapsulation of unsafe code; “if you know what you’re doing” is not a safety boundary.
  • Counterpoint: with discipline and libraries, you can approximate this, but the language doesn’t help.
  • Rust’s unsafe and the requirement to explicitly mark unsafe calls are seen as culturally and technically important.
  • Historical notes mention earlier languages with explicit unsafe/checked modules and tainted binaries.

Techniques for circular references in Rust

  • Besides the article’s vector-of-nodes-with-indices, people mention:
    • The “Too Many Linked Lists” guide.
    • Rc/Weak + RefCell.
    • Gc<T>-style pointers and third-party GC runtimes.
    • GhostCell / qcell patterns using higher-rank lifetimes and tokens.
  • Some note that index-based deletion in a Vec<T> can leak or require extra machinery (e.g., Option<T>, free lists).

Are parent links / cyclic structures needed?

  • One camp: avoid parent pointers and cycles when possible; many algorithms don’t truly need them, and cycles are hard to reason about.
  • Others respond that some algorithms genuinely require parent or bidirectional links; if a language blocks that, it’s a limitation, not a virtue.
  • There is a sense that Rust’s friction here reveals when cycles are actually necessary vs habitual.

GC vs Rust-style ownership

  • Some argue a modern GC would suffice for most Rust use cases; Rust’s contortions around graphs show the cost of no GC.
  • Others counter that:
    • Many Rust users already know GC’d languages and chose Rust for predictability, performance, and no runtime.
    • Even low-latency GCs still hurt determinism and cache behavior in high-performance or real-time-ish code.
  • Discussion notes that many projects probably could tolerate GC, but developers value Rust’s other properties (type system, deterministic destruction, ownership-based concurrency).

Isoheaps and alternative memory models

  • Isoheaps (per-type isolated heaps) are proposed as an alternative: similar guarantees to indices/arenas but faster and more ergonomic.
  • Claims: isoheaps and index-based schemes both prevent RCE, though they don’t prevent all logical misuse.
  • Some suggest that borrow-checker-style systems may be overkill compared to isoheap-based manual management.

Ergonomics, lifetimes, and language mix

  • Complaints about Rust ergonomics: adding lifetimes is painful; patterns like &'a Node<'a> are easy mistakes.
  • Some prefer using two languages (e.g., C for low-level, Go/Python for high-level) instead of bending Rust to all roles.
  • Others enjoy Rust as a single language spanning high- and low-level code, citing its expressiveness, safety culture, and performance.