Box<T>

Level 3 — Ownership & Borrowing A smart pointer that allocates data on the heap with single ownership.

1. Prerequisites

• Ownership — The fundamental "One Owner" rule that Box strictly enforces.
• Scalar Types — Types like i32 that default to living on the fast Stack memory.
• Enum — Often used in combination with Box to build recursive data structures.

2. Term Category

Rust-specific (the safe pointer): In C/C++, you move data to the Heap using malloc or new, which requires you to manually free the memory later to prevent leaks. In Rust, Box<T> safely moves data to the Heap and automatically cleans it up using the Drop trait.

3. Explanation

(1) Design Motivation — "Why did we design this?"

By default, simple data in Rust (like integers, booleans, and small structs) is stored on the Stack. The Stack is incredibly fast, but it has one strict rule: the compiler must know the exact size of the data at compile time.

What if you are building a recursive data structure, like a Linked List? A Node contains some data, plus another Node. That Node contains another Node, which contains another Node… The compiler tries to calculate the size of this infinite Russian nesting doll and fails, throwing an error: recursive type has infinite size.

To fix this, you must store the actual data on the Heap, and only keep a fixed-size "pointer" (a memory address) on the Stack.

Box<T> is the simplest smart pointer in Rust. It takes any data, moves it to the Heap, and gives you a single, exclusive pointer to it. Because a pointer is always the exact same size (just an address number like 0x8A45F), the compiler is happy!

(2) Reality Metaphor

Imagine you buy a massive, 10-foot tall grand piano (large data).

You can't fit the piano inside your tiny apartment (the Stack). So, you rent a massive storage unit (the Heap) and put the piano inside. The storage company gives you exactly one physical key (the Box<T>).

You keep the tiny key in your apartment. It doesn't take up much space, and it proves you are the sole owner of the piano. When you move out of your apartment (go out of scope), you throw the key away, and the storage company automatically throws the piano in the trash to clear the unit (the Drop trait).

(3) Rust Code Examples

Short Snippet (Moving an integer to the Heap)

An i32 normally lives on the Stack. By wrapping it in Box::new(), we force it onto the Heap.

fn main() {
    // b is a Box that points to the number 5 on the Heap.
    let b = Box::new(5);
    
    // Rust automatically follows the pointer to print the value!
    println!("b = {}", b);
} // b goes out of scope here. The Heap memory is freed instantly.

Fuller Example (Fixing a Recursive Type)

This is the most common use-case for Box. Without Box, the List enum below would fail to compile because it has infinite size.

// A simple Linked List: It is either a Node (Item + Next List), or Empty.
enum List {
    Node(i32, Box<List>), // The Box makes the `next` field a fixed-size pointer!
    Empty,
}

use List::{Node, Empty};

fn main() {
    // We create a list: [1, 2, 3]
    let my_list = Node(1, Box::new(Node(2, Box::new(Node(3, Box::new(Empty))))));
}

4. Common Mistakes & Pitfalls

Mistake 1: Misunderstanding Box T Scoping and Lifecycle Rules

The mistake: Assuming Box T instances remain valid beyond their declaring scope block or across asynchronous boundaries without explicit lifetime tracking.

Why it's wrong: Rust strictly enforces lexical scope boundaries and non-lexical lifetimes (NLL) at compile time. Accessing dropped values or failing to handle variable drop order results in compiler errors such as E0597 or E0382.

Incorrect:

fn get_ref() -> &str {
    let s = String::from("box_t_data");
    &s // ❌ Error E0106/E0515: returns a reference to data owned by the current function
}

Fix:

fn get_string() -> String {
    let s = String::from("box_t_data");
    s // Ownership of the String is transferred directly to the caller
}

Mistake 2: Mutating Box T State Without Exclusive Ownership or mut Borrowing

The mistake: Attempting to mutate data associated with Box T through an immutable reference &T or without specifying mut in variable declarations.

Why it's wrong: Rust's aliasing XOR mutability rule (&T for shared immutable access, &mut T for exclusive mutable access) prohibits mutating state through shared references unless interior mutability patterns (e.g. RefCell, Mutex) are explicitly used.

Incorrect:

fn update_val(data: &i32) {
    // *data += 1; // ❌ Error E0594: cannot assign to `*data`, which is behind a `&` reference
}

Fix:

fn update_val(data: &mut i32) {
    *data += 1; // Correct: exclusive mutable reference permits mutation
}

Mistake 3: Concurrent Access to Box T Across Threads Without Send / Sync Guards

The mistake: Sharing non-thread-safe Box T instances across OS threads via std::thread::spawn.

Why it's wrong: Types that do not implement Send or Sync marker traits cannot safely cross thread boundaries. The compiler prevents data races by raising compile errors E0277 (trait Send is not implemented).

Incorrect:

use std::rc::Rc;
use std::thread;

let rc = Rc::new(42);
// thread::spawn(move || { println!("{}", rc); }); // ❌ Error E0277: `Rc` cannot be sent between threads safely

Fix:

use std::sync::Arc;
use std::thread;

let arc = Arc::new(42);
thread::spawn(move || {
    println!("{}", arc); // Correct: `Arc` implements `Send` and `Sync`
});

5. Practice Exercises

Exercise 1: Recursive AST & Dynamic Expression Evaluator with Constant Folding

Scenario: Problem Scenario: You are designing an Abstract Syntax Tree (AST) query engine for a production financial rules calculator. Because sub-expression nodes in an AST are inherently recursive (Expr::BinaryOp contains child Expr nodes) and customizable via dynamic plugins (Box<dyn CustomExpr>), stack allocation fails at compile time due to infinite type size.

Requirements: Implement an AST calculation engine using Box<T> that supports recursive traversal, dynamic trait dispatch, depth computation, and AST constant folding (evaluating static literal subtrees into single literal nodes).

Requirements:

1. Define an enum Op with arithmetic operations (Add, Sub, Mul, Div).
2. Define a trait CustomExpr: Send + Sync + std::fmt::Debug with fn eval(&self) -> Result<f64, String> and fn clone_box(&self) -> Box<dyn CustomExpr>.
3. Define recursive enum Expr containing Literal(f64), BinaryOp { op: Op, left: Box<Expr>, right: Box<Expr> }, and Custom(Box<dyn CustomExpr>).
4. Implement eval(&self) -> Result<f64, String> handling division by zero with Err("Division by zero".to_string()).
5. Implement tree_depth(&self) -> usize returning max AST depth.
6. Implement fold_constants(self) -> Expr to optimize literal subtrees into a single Expr::Literal.

use std::fmt::Debug;

#[derive(Debug, Clone, PartialEq)]
pub enum Op {
    Add,
    Sub,
    Mul,
    Div,
}

pub trait CustomExpr: Send + Sync + Debug {
    fn eval(&self) -> Result<f64, String>;
    fn clone_box(&self) -> Box<dyn CustomExpr>;
}

impl Clone for Box<dyn CustomExpr> {
    fn clone(&self) -> Self {
        self.clone_box()
    }
}

#[derive(Debug, Clone)]
pub enum Expr {
    Literal(f64),
    BinaryOp {
        op: Op,
        left: Box<Expr>,
        right: Box<Expr>,
    },
    Custom(Box<dyn CustomExpr>),
}

impl Expr {
    pub fn eval(&self) -> Result<f64, String> {
        match self {
            Expr::Literal(val) => Ok(*val),
            Expr::Custom(custom) => custom.eval(),
            Expr::BinaryOp { op, left, right } => {
                let l = left.eval()?;
                let r = right.eval()?;
                match op {
                    Op::Add => Ok(l + r),
                    Op::Sub => Ok(l - r),
                    Op::Mul => Ok(l * r),
                    Op::Div => {
                        if r == 0.0 {
                            Err("Division by zero".to_string())
                        } else {
                            Ok(l / r)
                        }
                    }
                }
            }
        }
    }

    pub fn tree_depth(&self) -> usize {
        match self {
            Expr::Literal(_) | Expr::Custom(_) => 1,
            Expr::BinaryOp { left, right, .. } => {
                1 + usize::max(left.tree_depth(), right.tree_depth())
            }
        }
    }

    pub fn fold_constants(self) -> Expr {
        match self {
            Expr::BinaryOp { op, left, right } => {
                let folded_left = left.fold_constants();
                let folded_right = right.fold_constants();

                if let (Expr::Literal(l), Expr::Literal(r)) = (&folded_left, &folded_right) {
                    match op {
                        Op::Add => Expr::Literal(l + r),
                        Op::Sub => Expr::Literal(l - r),
                        Op::Mul => Expr::Literal(l * r),
                        Op::Div => {
                            if *r != 0.0 {
                                Expr::Literal(l / r)
                            } else {
                                Expr::BinaryOp {
                                    op,
                                    left: Box::new(folded_left),
                                    right: Box::new(folded_right),
                                }
                            }
                        }
                    }
                } else {
                    Expr::BinaryOp {
                        op,
                        left: Box::new(folded_left),
                        right: Box::new(folded_right),
                    }
                }
            }
            other => other,
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[derive(Debug, Clone)]
    struct ConstantSquare(f64);

    impl CustomExpr for ConstantSquare {
        fn eval(&self) -> Result<f64, String> {
            Ok(self.0 * self.0)
        }
        fn clone_box(&self) -> Box<dyn CustomExpr> {
            Box::new(self.clone())
        }
    }

    #[test]
    fn test_ast_evaluation_and_folding() {
        // Tree: (10 + 20) * 2
        let expr = Expr::BinaryOp {
            op: Op::Mul,
            left: Box::new(Expr::BinaryOp {
                op: Op::Add,
                left: Box::new(Expr::Literal(10.0)),
                right: Box::new(Expr::Literal(20.0)),
            }),
            right: Box::new(Expr::Literal(2.0)),
        };

        assert_eq!(expr.tree_depth(), 3);
        let res = expr.eval();
        assert!(res.is_ok());
        assert_eq!(res.unwrap(), 60.0);

        let folded = expr.fold_constants();
        assert_eq!(folded.tree_depth(), 1);
        assert!(matches!(folded, Expr::Literal(val) if val == 60.0));
        assert_eq!(folded.eval().unwrap(), 60.0);
    }

    #[test]
    fn test_custom_expr_and_div_by_zero() {
        let custom_node = Expr::Custom(Box::new(ConstantSquare(4.0)));
        assert_eq!(custom_node.eval().unwrap(), 16.0);

        let div_zero = Expr::BinaryOp {
            op: Op::Div,
            left: Box::new(Expr::Literal(10.0)),
            right: Box::new(Expr::Literal(0.0)),
        };
        let err_res = div_zero.eval();
        assert!(err_res.is_err());
        assert_eq!(err_res.unwrap_err(), "Division by zero");

        let folded_div_zero = div_zero.fold_constants();
        assert_ne!(folded_div_zero.tree_depth(), 1);
    }
}

Exercise 2: FFI Memory Bridge & Zero-Copy Packet Buffer (Box::into_raw & Box::from_raw)

Scenario: Problem Scenario: You are building a zero-copy low-latency packet queue bridging Rust network logic with an external C driver framework (such as DPDK or raw Linux socket callbacks). Safe automatic Drop behavior must be suspended when releasing heap buffers into C raw pointer boundaries, and re-established when reclaiming buffer ownership in Rust.

Requirements: Implement a raw packet management handle using Box::into_raw and Box::from_raw that prevents memory leaks and ensures panic-safe memory deallocation.

Requirements:

1. Define PacketPayload containing id: u64, timestamp: u64, and data: Vec<u8>.
2. Implement PacketPayload::into_raw(payload: Self) -> *mut PacketPayload to convert Box<PacketPayload> into a raw pointer, leaking ownership safely.
3. Implement unsafe fn PacketPayload::from_raw(ptr: *mut PacketPayload) -> Box<PacketPayload> to reconstitute heap ownership.
4. Implement RawPacketHandle wrapper managing raw pointers with safe mutation via process_mut and ownership reclamation via reclaim(self).
5. Implement Drop for RawPacketHandle so that if a handle drops without manual reclamation, the underlying pointer is safely reclaimed and freed, eliminating memory leaks.

#[derive(Debug, PartialEq, Eq)]
pub struct PacketPayload {
    pub id: u64,
    pub timestamp: u64,
    pub data: Vec<u8>,
}

impl PacketPayload {
    pub fn new(id: u64, timestamp: u64, data: Vec<u8>) -> Self {
        Self { id, timestamp, data }
    }

    pub fn into_raw(payload: Self) -> *mut PacketPayload {
        Box::into_raw(Box::new(payload))
    }

    pub unsafe fn from_raw(ptr: *mut PacketPayload) -> Box<PacketPayload> {
        assert!(!ptr.is_null(), "Attempted to reconstruct Box from null pointer");
        Box::from_raw(ptr)
    }
}

#[derive(Debug)]
pub struct RawPacketHandle {
    ptr: *mut PacketPayload,
}

impl RawPacketHandle {
    pub fn new(payload: PacketPayload) -> Self {
        let raw_ptr = PacketPayload::into_raw(payload);
        Self { ptr: raw_ptr }
    }

    pub fn is_null(&self) -> bool {
        self.ptr.is_null()
    }

    pub fn raw_ptr(&self) -> *mut PacketPayload {
        self.ptr
    }

    pub fn process_mut<F, R>(&mut self, f: F) -> Result<R, &'static str>
    where
        F: FnOnce(&mut PacketPayload) -> R,
    {
        if self.ptr.is_null() {
            return Err("Null pointer handle");
        }
        // SAFETY: ptr is validated non-null and owned exclusively by this RawPacketHandle.
        unsafe {
            let payload_ref = &mut *self.ptr;
            Ok(f(payload_ref))
        }
    }

    pub fn reclaim(mut self) -> Result<PacketPayload, &'static str> {
        if self.ptr.is_null() {
            return Err("Null pointer handle");
        }
        let ptr = self.ptr;
        self.ptr = std::ptr::null_mut(); // Disarm Drop handler to avoid double-free
        // SAFETY: ptr was created via Box::into_raw and has not been freed.
        unsafe {
            let boxed = PacketPayload::from_raw(ptr);
            Ok(*boxed)
        }
    }
}

impl Drop for RawPacketHandle {
    fn drop(&mut self) {
        if !self.ptr.is_null() {
            // SAFETY: Reclaim ownership and trigger Box drop to clean up heap memory.
            unsafe {
                let _ = Box::from_raw(self.ptr);
            }
            self.ptr = std::ptr::null_mut();
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_raw_packet_handle_lifecycle() {
        let payload = PacketPayload::new(101, 1690000000, vec![0xDE, 0xAD, 0xBE, 0xEF]);
        let mut handle = RawPacketHandle::new(payload);

        assert!(!handle.is_null());
        assert_ne!(handle.raw_ptr(), std::ptr::null_mut());

        let result = handle.process_mut(|p| {
            p.data.push(0xFE);
            p.data.len()
        });

        assert!(result.is_ok());
        assert_eq!(result.unwrap(), 5);

        let reclaimed = handle.reclaim();
        assert!(reclaimed.is_ok());
        let inner = reclaimed.unwrap();

        assert_eq!(inner.id, 101);
        assert_eq!(inner.timestamp, 1690000000);
        assert_eq!(inner.data, vec![0xDE, 0xAD, 0xBE, 0xEF, 0xFE]);
    }

    #[test]
    fn test_automatic_leak_prevention_on_drop() {
        let payload = PacketPayload::new(202, 1690000500, vec![1, 2, 3]);
        let handle = RawPacketHandle::new(payload);
        // Letting handle go out of scope invokes Drop, executing Box::from_raw cleanup cleanly.
        drop(handle);
    }
}

Exercise 3: Dynamic API Gateway Pipeline with Box<dyn Middleware> & Pointer Layout Profiling

Scenario: Problem Scenario: In an asynchronous microservice gateway, inbound HTTP requests pass through a sequence of dynamic middleware plug-in stages (Authentication, Header Injection, Logging). Because middleware implementations vary in size, storing them in a uniform Vec requires boxed trait objects (Box<dyn Middleware>).

Requirements: Implement a dynamic middleware execution pipeline and analyze the memory layout differences between thin pointer boxed types (Box<T>) and fat pointer dynamic trait objects (Box<dyn Trait>).

Requirements:

1. Define RequestContext holding uri: String, headers: Vec<(String, String)>, body: Vec<u8>, and status_code: u16.
2. Define trait Middleware: Send + Sync with method fn handle(&self, ctx: &mut RequestContext) -> Result<(), String>.
3. Implement Pipeline holding stages: Vec<Box<dyn Middleware>> with add_stage and sequential execute.
4. Implement concrete middleware: HeaderInjectorMiddleware and AuthMiddleware (which validates the Authorization: Bearer <token> header).
5. Implement inspect_pointer_sizes() returning (usize, usize) representing size_of::<Box<RequestContext>>() vs size_of::<Box<dyn Middleware>>().

#[derive(Debug, Clone, PartialEq, Eq)]
pub struct RequestContext {
    pub uri: String,
    pub headers: Vec<(String, String)>,
    pub body: Vec<u8>,
    pub status_code: u16,
}

impl RequestContext {
    pub fn new(uri: &str) -> Self {
        Self {
            uri: uri.to_string(),
            headers: Vec::new(),
            body: Vec::new(),
            status_code: 200,
        }
    }
}

pub trait Middleware: Send + Sync {
    fn handle(&self, ctx: &mut RequestContext) -> Result<(), String>;
}

pub struct Pipeline {
    stages: Vec<Box<dyn Middleware>>,
}

impl Pipeline {
    pub fn new() -> Self {
        Self { stages: Vec::new() }
    }

    pub fn add_stage(&mut self, stage: Box<dyn Middleware>) {
        self.stages.push(stage);
    }

    pub fn execute(&self, ctx: &mut RequestContext) -> Result<(), String> {
        for stage in &self.stages {
            stage.handle(ctx)?;
        }
        Ok(())
    }

    pub fn stage_count(&self) -> usize {
        self.stages.len()
    }

    pub fn inspect_pointer_sizes() -> (usize, usize) {
        (
            std::mem::size_of::<Box<RequestContext>>(),
            std::mem::size_of::<Box<dyn Middleware>>(),
        )
    }
}

pub struct AuthMiddleware {
    pub token: String,
}

impl Middleware for AuthMiddleware {
    fn handle(&self, ctx: &mut RequestContext) -> Result<(), String> {
        let expected = format!("Bearer {}", self.token);
        let authorized = ctx
            .headers
            .iter()
            .any(|(k, v)| k.eq_ignore_ascii_case("Authorization") && v == &expected);

        if authorized {
            Ok(())
        } else {
            ctx.status_code = 401;
            Err("Unauthorized: Invalid token".to_string())
        }
    }
}

pub struct HeaderInjectorMiddleware {
    pub key: String,
    pub value: String,
}

impl Middleware for HeaderInjectorMiddleware {
    fn handle(&self, ctx: &mut RequestContext) -> Result<(), String> {
        ctx.headers.push((self.key.clone(), self.value.clone()));
        Ok(())
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_pipeline_execution_success() {
        let mut pipeline = Pipeline::new();
        pipeline.add_stage(Box::new(HeaderInjectorMiddleware {
            key: "Authorization".to_string(),
            value: "Bearer secret123".to_string(),
        }));
        pipeline.add_stage(Box::new(AuthMiddleware {
            token: "secret123".to_string(),
        }));

        assert_eq!(pipeline.stage_count(), 2);

        let mut ctx = RequestContext::new("/api/v1/resource");
        let res = pipeline.execute(&mut ctx);

        assert!(res.is_ok());
        assert_eq!(ctx.status_code, 200);
        assert_eq!(ctx.headers.len(), 1);
    }

    #[test]
    fn test_pipeline_auth_failure() {
        let mut pipeline = Pipeline::new();
        pipeline.add_stage(Box::new(AuthMiddleware {
            token: "secret123".to_string(),
        }));

        let mut ctx = RequestContext::new("/api/v1/resource");
        let res = pipeline.execute(&mut ctx);

        assert!(res.is_err());
        assert_eq!(ctx.status_code, 401);
        assert!(matches!(res, Err(ref msg) if msg.contains("Unauthorized")));
    }

    #[test]
    fn test_fat_vs_thin_pointer_sizes() {
        let (thin_ptr_size, fat_ptr_size) = Pipeline::inspect_pointer_sizes();

        // On 64-bit systems: thin pointer is 8 bytes (1 word), fat pointer is 16 bytes (2 words).
        assert_eq!(thin_ptr_size, std::mem::size_of::<usize>());
        assert_eq!(fat_ptr_size, std::mem::size_of::<usize>() * 2);
        assert_ne!(thin_ptr_size, fat_ptr_size);
    }
}

6. Related Terms

• Rc<T> — The smart pointer you use when you need Heap allocation and multiple owners. (Box strictly enforces One Owner).
• Vec<T> — Under the hood, Vec actually uses a Box to store its growable list of items on the Heap!
• Trait Objects (dyn Trait) — Related concept: Trait Objects (dyn Trait).
• Smart Pointers (Box, Rc, Arc) — Related concept: Smart Pointers (Box, Rc, Arc).

7. Key Takeaways

• Box<T> moves data from the Stack to the Heap.
• It maintains strict Single Ownership (unlike Rc).
• When the Box goes out of scope, the Heap data is automatically freed.
• It is primarily used to create recursive data structures (like Trees and Linked Lists) where the compiler cannot determine the size at compile time.
• You can access or modify the inner data by using the dereference operator (*my_box).