The problem with duplicated matches
You are writing a configuration parser. You have a Config enum with variants for keys, values, sections, and nested blocks. You write a function print_config that walks the tree and formats it. It works. Then you need validate_config to check for duplicate keys. You write another function. Both functions contain a giant match block that mirrors the structure of the enum. You copy-paste the shape of the data into two places.
You add a new variant Array. The compiler saves you with E0004 (non-exhaustive patterns), forcing you to update both functions. But you still have the shape of the data repeated twice. If you have ten operations, you have ten copies of the shape. Adding a variant means touching ten functions. The code becomes brittle. The Visitor pattern solves this by extracting the shape once. The enum owns the structure. The visitors own the behavior. You add a variant, and the compiler forces you to update every visitor trait implementation. You get the safety of exhaustive matching without the duplication.
Double dispatch without classes
Think of your data structure as a museum layout. The exhibits sit in fixed positions. They don't move. They don't change. But you can send different inspectors through the halls. One inspector checks fire safety. Another counts inventory. A third writes a tour brochure. The exhibits don't need to know about the inspectors. The inspectors just walk the route and react to what they find.
In Rust, the enum is the museum. The trait is the inspector. The accept method is the entry point that hands the inspector to the right room. This mechanism is called double dispatch. The first dispatch happens when the enum matches the variant. The second dispatch happens when the trait method is called on the concrete visitor type. You get the right behavior for the right data and the right operation, all without inheritance or virtual methods.
Separate the shape from the action. The data stays dumb. The behavior stays flexible.
Minimal working example
Here is the skeleton. The enum defines the data. The trait defines the operations. The accept method bridges them.
/// Represents a simple arithmetic expression tree.
/// Uses Box to handle recursive structure on the heap.
enum Expr {
/// A literal number.
Num(i32),
/// Addition of two sub-expressions.
Add(Box<Expr>, Box<Expr>),
}
/// The interface for any operation that walks the tree.
/// Read-only visitors use &self to avoid mutation overhead.
trait Visitor {
/// Called when the visitor encounters a number.
fn visit_num(&self, n: i32);
/// Called when the visitor encounters an addition node.
fn visit_add(&self, left: &Expr, right: &Expr);
}
impl Expr {
/// Dispatches the visitor to the correct method based on the variant.
/// Takes &dyn Visitor to allow dynamic dispatch over any concrete type.
fn accept(&self, v: &dyn Visitor) {
match self {
Expr::Num(n) => v.visit_num(*n),
Expr::Add(l, r) => v.visit_add(l, r),
}
}
}
/// A visitor that prints the expression structure with parentheses.
struct PrintVisitor;
impl Visitor for PrintVisitor {
fn visit_num(&self, n: i32) {
print!("{}", n);
}
fn visit_add(&self, left: &Expr, right: &Expr) {
print!("(");
// Recursively visit children to print the full tree.
left.accept(self);
print!(" + ");
right.accept(self);
print!(")");
}
}
fn main() {
// Build a tree: (1 + 2).
let expr = Expr::Add(
Box::new(Expr::Num(1)),
Box::new(Expr::Num(2)),
);
let printer = PrintVisitor;
expr.accept(&printer);
println!();
}
The community convention is to name the dispatch method accept. Some codebases use apply or visit, but accept is the standard term from the GoF pattern and appears in most Rust libraries that adopt this approach. Stick with accept so other developers recognize the pattern immediately.
How the compiler handles the dispatch
The magic happens in accept. It takes &dyn Visitor. This is a trait object. The compiler doesn't know the concrete type at compile time. It generates a vtable for the Visitor trait. The vtable contains function pointers for visit_num and visit_add. When you call v.visit_num, the compiler looks up the function pointer in the vtable and jumps there. This is dynamic dispatch. It has a tiny cost, usually a single pointer indirection, but it gives you flexibility. You can pass any type that implements Visitor without changing accept.
The match inside accept performs the first dispatch based on the enum variant. This is static dispatch. The compiler generates a jump table or a series of checks for the enum discriminant. The call to v.visit_num performs the second dispatch based on the concrete visitor type. This is dynamic dispatch. You get double dispatch. The enum handles the data shape. The trait handles the operation type.
Convention aside: Rustaceans often keep accept methods private or pub(crate) if the visitor is an internal implementation detail. Exposing accept publicly invites users to pass arbitrary visitors, which can complicate the API surface. If you only need one or two operations, consider keeping the match logic internal and exposing specific methods like print or eval instead.
Realistic usage with stateful visitors
Read-only visitors are clean, but real work often requires state. You might need to accumulate results, track indentation, or collect errors. For this, you need mutable access. The pattern adapts by using &mut self in the trait.
use std::fmt;
/// Collects diagnostic messages during traversal.
/// Uses a Vec to store errors found in the tree.
struct LintVisitor {
errors: Vec<String>,
}
impl LintVisitor {
fn new() -> Self {
Self { errors: Vec::new() }
}
fn errors(&self) -> &[String] {
&self.errors
}
}
/// Mutable visitor trait for operations that accumulate state.
/// Uses &mut self to allow writing to internal buffers.
trait MutVisitor {
fn visit_num(&mut self, n: i32);
fn visit_add(&mut self, left: &Expr, right: &Expr);
}
impl MutVisitor for LintVisitor {
fn visit_num(&mut self, n: i32) {
// Check for negative numbers and record a warning.
if n < 0 {
self.errors.push(format!("Negative number: {}", n));
}
}
fn visit_add(&mut self, left: &Expr, right: &Expr) {
// Recursively lint children.
// The visitor is borrowed mutably, but the tree is borrowed immutably.
left.accept_mut(self);
right.accept_mut(self);
}
}
impl Expr {
/// Mutable version of accept for stateful visitors.
/// Takes &mut dyn MutVisitor to allow the visitor to update its state.
fn accept_mut(&self, v: &mut dyn MutVisitor) {
match self {
Expr::Num(n) => v.visit_num(*n),
Expr::Add(l, r) => v.visit_add(l, r),
}
}
}
fn main() {
let expr = Expr::Add(
Box::new(Expr::Num(-5)),
Box::new(Expr::Num(10)),
);
let mut linter = LintVisitor::new();
expr.accept_mut(&mut linter);
for error in linter.errors() {
println!("Lint: {}", error);
}
}
Split your traits. Read-only visitors get &self. Stateful visitors get &mut self. Keep the API honest. Mixing them forces users to use RefCell everywhere, which hurts performance and clarity. If you need both, define two traits or use a generic parameter with a marker trait. Don't compromise on mutability semantics.
Pitfalls and compiler traps
If you write fn accept(&self, v: Visitor), the compiler rejects you. Visitor is a trait, not a sized type. The compiler doesn't know how much space to allocate. You must use &dyn Visitor. The error is E0277 (trait bound not satisfied) or a size mismatch error. The fix is adding dyn. This tells the compiler to use a fat pointer with a vtable.
Borrowing issues arise when visitors try to store references to the tree. If your visitor holds a &Expr and you call accept_mut, you might get E0502 (cannot borrow as mutable because it is also borrowed as immutable). The tree is borrowed immutably by accept_mut. If the visitor holds an immutable reference, the compiler blocks the mutable borrow of the visitor. Don't store references to the tree inside the visitor. Pass values or indices instead. If you need to cache data, clone it or use owned types.
Performance matters in tight loops. Trait objects use vtables. There is a pointer indirection for every method call. If you are processing millions of nodes in a hot path, the overhead can add up. Profile first. If the visitor is the bottleneck, consider inlining the logic or using an enum of closures for small behaviors. Dynamic dispatch is flexible, but static dispatch is faster.
Convention aside: When defining the enum, use Box<T> for recursive variants. This keeps the enum size fixed. Without Box, the compiler cannot determine the size of the enum because it contains itself. Box puts the recursive part on the heap. If your tree nodes are shared between branches, use Rc<T> instead of Box<T>. Rc adds reference counting, allowing multiple owners. Use Box for exclusive ownership trees. Use Rc for graphs with shared nodes.
If you find yourself fighting the borrow checker to store a reference in the visitor, step back. You're holding onto data too long. Drop the reference. Pass the value.
When to use the Visitor pattern
Use the Visitor pattern when you have a stable data structure and need to add multiple unrelated behaviors without modifying the enum. Use a simple match function when you only need one operation on the data; the overhead of a trait isn't worth it. Use an enum of closures or a functional approach when the behavior is small and local; traits add ceremony that can obscure simple logic. Use RefCell inside a visitor only when you must mutate state through an immutable reference; prefer &mut self traits for clarity and performance. Use recursive descent parsing with direct function calls instead of Visitor when building a parser; the pattern adds indirection that slows down token processing.
Reach for the Visitor pattern when the data is stable and the behaviors are volatile. Otherwise, keep it simple.