The problem with closed enums
You're building a parser for a mini-language. Your syntax tree is an enum with Number, Add, and Multiply variants. You need to print the tree. Easy. You write a match block that recurses and outputs text. Then you need to count the total operations. You write another match block. Then you need to check if any number exceeds a safety limit. Another match.
In a class-based language, you'd just add print(), count(), and check() methods to your node class. Rust enums don't work that way. You can't bolt methods onto an enum from the outside. Every time you need a new operation, you have to touch the enum definition, recompile the whole crate, and risk breaking existing code. If you publish this enum in a library, your users are stuck. They can't add variants, and they can't add methods. They have to fork your crate or wrap the enum in their own type.
The Visitor pattern solves this by separating the data structure from the operations you perform on it. You define a trait that describes the operations. Your enum implements a single method that accepts any type implementing that trait. The enum handles the traversal. The visitor handles the logic. You can add new visitors without touching the enum. Library authors use this pattern to let users extend functionality without forking the crate.
Separate the shape from the action. The Visitor pattern lets you add behaviors without touching the enum.
How the visitor flips the script
Think of your data structure as a museum building. The building has rooms, hallways, and a fixed layout. It doesn't care what happens inside. The Visitor is a tour guide walking through the building. The guide decides what to do in each room. Maybe one guide counts the paintings. Another guide checks the fire exits. A third guide writes a brochure.
The building provides the path. The guide provides the purpose.
In Rust, the enum is the building. It knows how to walk through its variants. The visitor trait is the interface for the guides. Each variant in the enum calls back to the visitor when the traversal reaches it. This is called double dispatch in other languages, but Rust handles it cleanly with generics. The compiler inlines the calls, so you get the flexibility of dynamic dispatch with the performance of static dispatch.
The building provides the path. The visitor provides the purpose.
Minimal implementation
Here is the skeleton. You define a trait with methods for each node type. You add an accept method to your enum that dispatches to the trait. The visitor takes &mut self so it can accumulate state.
/// A trait that defines how to process each node type.
/// Implement this to add new behaviors without touching the Node enum.
trait Visitor {
/// Handle a leaf node containing a number.
fn visit_leaf(&mut self, value: i32);
/// Handle a branch node containing children.
fn visit_branch(&mut self, children: &[Node]);
}
/// The data structure we want to traverse.
/// This enum is closed. You cannot add variants from outside this module.
enum Node {
Leaf(i32),
Branch(Vec<Node>),
}
impl Node {
/// Dispatches to the visitor based on the node variant.
/// The generic parameter V allows any type implementing Visitor.
fn accept<V: Visitor>(&self, visitor: &mut V) {
match self {
Node::Leaf(val) => visitor.visit_leaf(*val),
Node::Branch(children) => visitor.visit_branch(children),
}
}
}
fn main() {
// A simple tree structure.
let tree = Node::Branch(vec![
Node::Leaf(10),
Node::Branch(vec![Node::Leaf(20)]),
]);
// A visitor that prints the structure.
struct Printer;
impl Visitor for Printer {
fn visit_leaf(&mut self, value: i32) {
println!("Leaf: {}", value);
}
fn visit_branch(&mut self, _children: &[Node]) {
println!("Branch start");
}
}
let mut printer = Printer;
tree.accept(&mut printer);
}
Convention aside: The method on the data structure is usually called accept. The methods on the trait are usually visit_*. This naming convention signals the direction of control. The data accepts the visitor. The visitor visits the nodes.
The enum drives the traversal. The trait drives the logic. Keep them decoupled.
Walkthrough: what happens at runtime
When you call tree.accept(&mut printer), the compiler generates code specific to Printer. There is no virtual table lookup. The match expression checks the variant. If it's a Leaf, it calls Printer::visit_leaf. If it's a Branch, it calls Printer::visit_branch.
Inside visit_branch, the visitor receives a slice of children. The visitor can choose to recurse by calling child.accept(&mut *self) on each child. In this minimal example, the visitor doesn't recurse, but in a realistic tree, the visitor usually drives the recursion for nested structures, or the accept method handles recursion and the visitor gets callbacks for enter/exit events.
The key insight is that accept takes a generic V: Visitor. This means the compiler monomorphizes the function. If you have a Counter visitor and a Printer visitor, the compiler generates two separate versions of accept. One calls Counter methods. One calls Printer methods. You get zero-cost abstraction. The overhead of the pattern is just the code size, not runtime performance.
If you forget the trait bound on accept, the compiler rejects you with E0277 (trait bound not satisfied). The error tells you exactly which trait is missing. Add V: Visitor to the generic parameter list and the error vanishes.
Generics give you speed. Trait objects give you flexibility. Pick based on whether you need to store visitors in a Vec.
Realistic example: expression evaluator
Real data structures often need to return values or accumulate complex state. Here is an expression tree for a calculator. The Expr enum uses Box to avoid infinite size. The Evaluator visitor computes the result by mutating its internal state.
/// Expression nodes for a simple calculator.
/// Box<Expr> is required because Rust enums must have a known size at compile time.
/// Without the box, the compiler would try to allocate infinite space for the recursion.
enum Expr {
Num(i64),
Add(Box<Expr>, Box<Expr>),
Mul(Box<Expr>, Box<Expr>),
}
/// Trait for operations on expressions.
/// Methods take &mut self so the visitor can store intermediate results.
trait ExprVisitor {
fn visit_num(&mut self, val: i64);
fn visit_add(&mut self, left: &Expr, right: &Expr);
fn visit_mul(&mut self, left: &Expr, right: &Expr);
}
impl Expr {
/// Accept a visitor to process this expression.
/// The visitor receives references to children, allowing it to recurse manually.
fn accept<V: ExprVisitor>(&self, v: &mut V) {
match self {
Expr::Num(val) => v.visit_num(*val),
Expr::Add(l, r) => v.visit_add(l, r),
Expr::Mul(l, r) => v.visit_mul(l, r),
}
}
}
/// Visitor that evaluates the expression to a number.
struct Evaluator {
result: i64,
}
impl ExprVisitor for Evaluator {
fn visit_num(&mut self, val: i64) {
self.result = val;
}
fn visit_add(&mut self, left: &Expr, right: &Expr) {
// Create fresh evaluators for children to isolate state.
// This avoids shared mutable state issues.
let mut left_eval = Evaluator { result: 0 };
let mut right_eval = Evaluator { result: 0 };
left.accept(&mut left_eval);
right.accept(&mut right_eval);
self.result = left_eval.result + right_eval.result;
}
fn visit_mul(&mut self, left: &Expr, right: &Expr) {
let mut left_eval = Evaluator { result: 0 };
let mut right_eval = Evaluator { result: 0 };
left.accept(&mut left_eval);
right.accept(&mut right_eval);
self.result = left_eval.result * right_eval.result;
}
}
fn main() {
// 2 * (3 + 4)
let expr = Expr::Mul(
Box::new(Expr::Num(2)),
Box::new(Expr::Add(
Box::new(Expr::Num(3)),
Box::new(Expr::Num(4)),
)),
);
let mut evaluator = Evaluator { result: 0 };
expr.accept(&mut evaluator);
println!("Result: {}", evaluator.result); // Prints 14
}
Convention aside: Recursive enums almost always need Box or Rc in Rust. The compiler enforces this because an enum variant containing the enum itself would have infinite size. The Box puts the recursive content on the heap, giving the enum a fixed pointer size. This is a hard rule. If you try to define enum Expr { Add(Expr, Expr) }, the compiler emits a "recursive type has infinite size" error.
The evaluator creates new instances for children. This is a common pattern when visitors accumulate state. It keeps the code simple and thread-safe by default. If performance is critical, you can use a single visitor with a stack or index, but the fresh-instance pattern is safer and easier to reason about.
Recursive enums need boxes. Visitors need mutable state. Rust handles both, but you have to ask for it.
Pitfalls and compiler traps
Visitors introduce a few specific traps. Watch for these.
Lifetimes can get hairy if your visitor stores references to nodes. If the visitor outlives the data structure, you'll get a borrow checker error. The visitor usually processes nodes synchronously, so this is rare. If you need to store references, add lifetime parameters to the visitor trait. This couples the visitor to the data's lifetime. Most visitors just extract values or mutate internal state, avoiding this entirely.
Using &self instead of &mut self on visitor methods prevents accumulation. If you define fn visit_leaf(&self, value: i32), you can't store the value in the visitor. You can only perform side effects like printing. If you need to collect results, use &mut self. The compiler will reject attempts to mutate self if the trait uses &self.
Trait objects versus generics. If you need to store multiple visitors in a Vec, you must use dyn Visitor. This erases the type and uses dynamic dispatch. Dynamic dispatch is slightly slower than monomorphized generics. Use dyn only when you need heterogeneous collections or API boundaries where the concrete type is unknown. For most use cases, generic parameters are faster and simpler.
If you use dyn Visitor, you must mark the trait as dyn-compatible. Add dyn to the trait definition if you plan to use it as a trait object. Rust 2021 edition requires dyn explicitly. If you forget, the compiler warns you. If you try to create a Vec<Visitor>, the compiler rejects it with a "trait objects must be dyn-compatible" error.
Don't over-engineer. If you only have one operation, a match block is faster to write and easier to read. The Visitor pattern adds indirection. Use it when you have multiple operations or when you need to separate concerns across module boundaries.
Generics give you speed. Trait objects give you flexibility. Pick based on whether you need to store visitors in a Vec.
When to reach for the visitor
Use the Visitor pattern when you have a stable data structure but frequently changing operations. This keeps your enum closed and lets you add behaviors in separate modules without recompiling the core crate.
Use a simple match expression when the operation is local and you don't need to separate concerns. Adding a method to the enum is fine if the logic is short and you control the enum definition.
Use dyn Visitor trait objects when you need to store multiple visitor implementations in a collection or pass them through an API boundary where the concrete type is unknown. This trades a small runtime dispatch cost for type erasure.
Use generic V: Visitor parameters when performance matters and the visitor type is known at compile time. Monomorphization inlines the calls and eliminates dispatch overhead.
Use an enum of operations instead of a visitor when the set of operations is small and fixed. An enum Operation { Print, Count } passed through a match is simpler than a full trait implementation.
Don't over-engineer. If you only have one operation, a match block is faster to write and easier to read.