🔧 Interior Mutability, Smart Pointers, and Tree Structures in Rust

When writing system-level code or complex data structures like trees and graphs in Rust, one challenge quickly becomes apparent:

how do you share and mutate data across many parts of a program without sacrificing memory safety?

Rust’s ownership system doesn’t allow multiple &mut references or shared ownership by default.

But the standard library offers powerful tools to overcome this — while maintaining safety guarantees.

In this post, we explore some of Rust’s most important tools for working with shared, recursive, and mutable data structures:

• Box<T>
• Rc<T> / Arc<T>
• RefCell<T> / Mutex<T>
• Weak<T>

We use a tree structure as our running example and discuss real-world system programming, GUIs, and interpreters.

📆 Box: Owning Recursive Types

struct TreeNode {
    value: i32,
    left: Option<Box<TreeNode>>,
    right: Option<Box<TreeNode>>,
}

🔍 Why Use Box?

• Enables recursive types by storing nodes on the heap
• Only allows single ownership (no sharing)

✅ When to Use:

• Heap allocation for simple trees, linked lists
• No need for shared or mutable access
• Example: Binary tree leaves in a compiler, simple DOM nodes in a web renderer

♻️ Rc and RefCell: Shared & Mutable Trees

use std::rc::Rc;
use std::cell::RefCell;

type NodeRef = Rc<RefCell<Node>>;

struct Node {
    value: i32,
    children: Vec<NodeRef>,
}

impl Node {
    fn new(value: i32) -> NodeRef {
        Rc::new(RefCell::new(Node { value, children: vec![] }))
    }
}

🔍 Why Combine Rc + RefCell?

• Rc<T> enables shared ownership
• RefCell<T> enables interior mutability, allowing mutation even through &self

✅ When to Use:

• Build tree or graph structures
• Allow many owners to read and mutate data
• Example: GUI widget trees (druid, iced), ASTs for interpreters

⚠️ Memory Leaks Warning

Rc uses reference counting — but cannot detect cycles!

If two Rcs reference each other, they’ll leak memory.

🧰 Weak: Breaking Cycles Safely

use std::rc::{Rc, Weak};
use std::cell::RefCell;

struct Node {
    parent: RefCell<Weak<Node>>,
    children: RefCell<Vec<Rc<Node>>>,
}

🔍 Why Use Weak?

• Weak<T> is a non-owning reference
• Does not increase the strong reference count
• Prevents cyclic leaks between parent and child nodes

✅ When to Use:

• Parent pointers in trees
• Bidirectional linked structures
• Example: Filesystem directory trees, scene graphs

🔐 Mutex and Arc: Thread-Safe Shared State

When moving to multithreading, Rc and RefCell aren't enough.

Instead, use:

use std::sync::{Arc, Mutex};

let data = Arc::new(Mutex::new(vec![1, 2, 3]));

let cloned = data.clone();
std::thread::spawn(move || {
    let mut locked = cloned.lock().unwrap();
    locked.push(4);
});

🔍 Why Use Arc + Mutex?

• Arc<T> = atomic reference counted smart pointer (safe across threads)
• Mutex<T> = exclusive mutable access with runtime locking

✅ When to Use:

• Share state between threads
• Build concurrent task queues, database caches
• Example: Shared blockchain ledger across network threads

✅ Summary: Choose the Right Tool

🧐 Final Thoughts

Understanding Box, Rc, RefCell, Arc, Mutex, and Weak is essential if you want to write serious system-level Rust.

These tools aren't "cheating" Rust’s rules — they are specialized, powerful, safe ways to express complicated relationships (ownership, sharing, mutation, concurrency) while keeping the Rust safety guarantees.

With these patterns, you can build:

• Blockchain nodes
• Compilers
• Embedded device controllers
• Multithreaded servers
• Real-time operating systems (RTOS)

Master these — and you master Rust system programming.