Rust — Trait Objects, Sized, and Why My DAG Needed `Box<dyn Fn>`

TL;DR — When building a DAG executor, I needed to store arbitrary task closures.
Generics weren’t enough. The solution required trait objects, dynamic dispatch, and 'static bounds.

Introduction

While building a DAG executor, I needed to store arbitrary task closures in a graph structure.

A naïve approach would be:

struct Node<F> {
    f: F
}

At first glance, this looks fine. But it immediately breaks when we try to store multiple nodes.

2. Why Generics Don't Work

Each closure in Rust has a unique anonymous type.

With generics:

Vec<Node<F>>

Each Node<F> is monomorphized for one concrete F. That means F can represent only one concrete type.

But my graph needs:

Vec<Node<different closure types>>

That is impossible because Vec<T> requires a single concrete T.

Even if all closures implement Fn(...), they are distinct concrete types. This means:

Generics fail because we need heterogeneity inside a homogeneous container.

We thus need type erasure.

An alternative would be to use an enum with predefined variants. This works when the set of possible tasks is closed and known in advance. However, in a general-purpose DAG library, users can provide arbitrary closures. This makes the set of possible task types open-ended, which requires trait objects rather than enums.

3. Trait Objects and Dynamically Sized Types

The solution is to use trait objects:

Box<dyn Fn(&[Arc<O>]) -> Result<O, E>>

Why does this work?

Because dyn Fn erases the concrete closure type.

When we write dyn Fn, we are effectively saying:

"I do not care about the concrete type. I only care that it implements Fn."

Once the concrete type is erased, the compiler no longer knows:

• The size
• The layout
• The alignment

Therefore, dyn Trait becomes a Dynamically Sized Type (DST).

DSTs cannot live directly on the stack because the compiler must know stack frame sizes at compile time.

So they must be placed behind a pointer.

What Box<dyn Fn> Actually Contains

A Box<dyn Fn> is a fat pointer:

(data_ptr, vtable_ptr)

• data_ptr → pointer to the heap allocation containing the concrete closure
• vtable_ptr → pointer to a virtual method table that enables dynamic dispatch

This is conceptually similar to how &str is represented as:

(ptr, len)

But instead of length metadata, trait objects store a vtable pointer.

Dynamic dispatch happens through this vtable.

In summary: dyn Fn is unsized because trait objects erase the concrete type, so the compiler no longer knows its layout at compile time. Therefore it must be placed behind a pointer (e.g., Box) which carries the necessary metadata (vtable pointer) to enable dynamic dispatch.

4. Why 'static, Send and Sync Are Required

My task type is defined as:

pub type TaskFn<O, E> =
    dyn Fn(&[Arc<O>]) -> Result<O, E> + Send + Sync + 'static;

What 'static Actually Means

T: 'static does not mean "lives forever".

It means:

The type does not contain non-static references.

For example:

let x = 5;
 
builder.add_task("a", vec![], |_| Ok(x));

If x were captured by reference, this closure would contain a reference tied to the current stack frame.

If the task is stored and executed later (possibly in another thread), that reference would become invalid.

Requiring 'static ensures:

• The closure owns its captured data
• Or only references 'static data

This prevents stack-local references from escaping.

Why Thread Pools implies 'static

When spawning threads:

std::thread::spawn(move || { ... });

The closure must be 'static.

Why?

Because the thread may outlive the current function stack frame.

Rust cannot guarantee when the thread completes.

Therefore:

Anything moved into a thread must not contain references tied to the current stack.

Since my tasks will eventually run in worker threads for parallel execution, 'static is necessary.

It is not about “threads need to know”, it is about preventing captured stack references from escaping.

5. Tradeoffs: Generics vs Trait Objects

Using trait objects means:

• Dynamic dispatch (vtable lookup)
• Slight runtime indirection

But it avoids:

• Monomorphization bloat
• Inability to store heterogeneous closures

In a system where tasks are CPU-heavy, the dynamic dispatch overhead is negligible compared to the work being performed.

The flexibility gain is worth it.

Final Thoughts

Understanding trait objects requires understanding:

• Type erasure
• Dynamically sized types
• Fat pointers
• Lifetime bounds like 'static

These concepts become unavoidable when building systems that store executable logic.