Visitor pattern

14 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

Visitor moves an operation out of the classes it operates on. Each node type gets one accept(visitor) method, and each operation (evaluate, print, type check, lint) becomes a visitor class with one visit_* method per node type.
It works by double dispatch: node.accept(v) selects the code for the node's runtime type, and inside it v.visit_num(self) selects the code for the visitor's runtime type. Two dynamic calls pick one method from a two-dimensional table.
The trade is the expression problem in miniature. Visitors make adding operations cheap and adding node types expensive, because every visitor must learn the new type. Use it when the set of types is stable and the set of operations keeps growing, as in compilers, linters and serialisers.
Exhaustive pattern matching over sealed types (Java 21, TypeScript unions, Rust) now does the same job with less ceremony. The visitor's lasting value is a checked list of cases and a reusable traversal.
Agents scatter isinstance chains, each missing a different node type. Review asks for one place per operation and a new node type that breaks the build or a test, not production.

How it works

The problem

A pricing team has a small rules language: expressions such as (base + fee) * qty and -discount. The parser produces a tree of four node types: numbers, variables, binary operations and negation. The tree needs many operations: evaluate it, print it back for the audit log, list the variables it reads, check it for division by a constant zero, estimate its cost.

Both obvious designs hurt. Putting every operation on every node class (the Composite lesson's approach, where bundles and items both answer price()) grows the node classes by a method per feature. Writing each operation as a function with an isinstance ladder keeps nodes small, but each function silently ignores node types it forgot, and that shows up as a wrong answer at runtime.

Double dispatch

Visitor gives each node one method that never changes:

class BinOp:
    def __init__(self, op, left, right):
        self.op, self.left, self.right = op, left, right

    def accept(self, visitor):
        return visitor.visit_binop(self)

An operation is a class with a method per node type:

class VarCollector:
    def __init__(self):
        self.names = set()
    def visit_num(self, n): pass
    def visit_var(self, n): self.names.add(n.name)
    def visit_neg(self, n): n.operand.accept(self)
    def visit_binop(self, n):
        n.left.accept(self)
        n.right.accept(self)

Calling tree.accept(VarCollector()) performs two dynamic dispatches: on the node, which runs BinOp.accept, and inside it on the visitor, which runs that visitor's visit_binop. Single-dispatch languages (Java, C#, C++, Go, TypeScript) choose a method by one receiver's runtime type; chaining two dispatches chooses by two. In a static language there is a further payoff: the Visitor interface lists every node type, so adding visit_call to it makes every existing visitor fail to compile until someone decides what it does with calls.

The expression problem

Philip Wadler named the tension in 1998: with types as rows and operations as columns, object-oriented code makes adding a row easy (one new class) and a column hard (edit every class), while functional code with pattern matching is the reverse. Visitor turns an object-oriented design into the functional shape. That is why it lives in compilers: a language's syntax changes rarely, but passes over the syntax tree (desugaring, type checking, optimisation, code generation, formatting, linting) are added constantly, often by different people.

Returning versus accumulating visitors

A visitor can return a value from each visit (the evaluator returns a number, the printer returns text) or accumulate state in its fields (the collector adds to a set). Returning visitors compose naturally with recursion. Accumulating visitors are the only option when the language cannot express a generic return type on the interface; Go's interfaces cannot have type parameters on methods, so a Go visitor typically stores its last result in a field, as the practice solution does.

Walkers: separating traversal from action

Real libraries split walking the tree from acting on nodes. Python's ast.NodeVisitor has generic_visit, which visits all children, so a visitor overrides only the types it cares about; Go has ast.Walk and ast.Inspect; Babel and ESLint take an object keyed by node type. This removes per-method recursion at the cost of exhaustiveness: a walker silently skips types you did not mention, which is right for a lint rule and wrong for an evaluator.

Pattern matching as the modern alternative

Java 21's switch over a sealed interface is exhaustive: the compiler rejects a switch that misses a permitted subtype. TypeScript gets the same check from a discriminated union and a never assignment in the default branch. An operation is then one function with a checked switch and no accept methods. Prefer that where the language supports it; keep the classic visitor for extension by other packages, a shared traversal, or languages without exhaustive matching.

When not to use it

The node types change often. Every new type is an edit to every visitor; put the behaviour on the nodes instead.
There are one or two operations. Methods on the nodes are simpler.
The structure is not a tree of distinct types. Iterating a list of identical records needs a loop, not double dispatch.

Reviewing agent-written code

Asked to "add a check that flags division by zero", an agent usually writes a recursive function with an isinstance ladder that handles three of the four node types, and returns None for the fourth. Asked to "use the visitor pattern", it may generate accept methods on nodes that already have them or a visitor whose methods all recurse by hand when the codebase has a walker. In review, ask: where is the list of node types, and what fails when a new one is added? Is traversal written once? Does the visitor mutate the tree while walking it? Is there a test with every node type in one tree?

The same shape elsewhere

Visitor is the fan-out shape on a type axis: one structure, many independent consumers. The same split appears in a JSON encoder that switches on value kind, in tax calculation where product categories are fixed but jurisdictions keep being added, in query planners that run rewrite rules over a relational algebra tree, and in infrastructure tools that run many checks (cost, security, naming) over one parsed configuration graph.

Down the stack

Layer 1The contract

Each node type promises exactly one accept that calls exactly one matching visit method and nothing else. Each visitor promises a method for every node type; in static languages the compiler enforces this, and in dynamic ones a test with a tree containing every node type must. The traversal order is part of the contract (the evaluator here walks left before right, so the first error reported is the leftmost), and so is mutation: a plain visitor must not change the tree it walks, while a transformer returns new or replacement nodes and leaves the original intact or replaces it in one defined step.

Layer 2The mechanism

Python's ast.NodeVisitor.visit builds the method name at runtime, 'visit_' + node.__class__.__name__, looks it up with getattr, and falls back to generic_visit, which iterates the node's _fields and visits every child node or list of nodes. ast.NodeTransformer uses the return value to replace the node, or deletes it when the value is None. Go's ast.Walk(v, node) calls v.Visit(node); if that returns a non-nil visitor w, it walks each child with w and then calls w.Visit(nil) to signal the end of the subtree, so a visitor can swap itself per subtree or prune by returning nil. ESLint gathers every enabled rule's listeners (keyed by node type or selector, with :exit variants) and calls them all during one traversal per file, so 200 rules cost one walk; Babel merges plugin visitors the same way. LLVM's InstVisitor uses the curiously recurring template pattern: visit(Instruction&) switches on the opcode and calls the derived class's visitAdd statically, so there is no virtual call at all.

Layer 3The machine

Classic double dispatch costs two indirect calls per node. In Go, n.Accept(v) and v.VisitBin(b) are each an itab call of about 1 to 2 ns when predicted, so a 10,000-node tree spends tens of microseconds on dispatch. The tree itself costs more: each node is a separate heap object, and a cold walk misses the CPU cache constantly at roughly 80 to 100 ns per miss to DRAM. Compilers that care store nodes in flat arrays indexed by integers (data-oriented design), and dispatch becomes a switch on a tag byte.

In CPython, NodeVisitor pays for string concatenation, a getattr and a bound-method call per node. Recursion is the other limit: CPython's default recursion limit is 1000, and a generated a + a + ... + a with 5,000 terms is a left-nested tree 5,000 deep that raises RecursionError. Production walkers use an explicit stack or rebalance such chains at parse time.

Concurrency follows from the state. A tree that nobody mutates can be visited by many goroutines or threads at once; a visitor with fields (a result slot, a set of names) cannot be shared, so create one per traversal.

Why it's built this way

Single-dispatch languages choose a method by one runtime type, but an operation over a tree depends on two: the node and the operation.
Chaining two single dispatches (accept, then visit_x) selects by both without type tests.
Listing every node type in the visitor interface makes missing cases a compile error, which isinstance ladders cannot give.
Writing the recursion in every visitor is tedious, so libraries factor the traversal into walkers, trading back some exhaustiveness.
Pointer-heavy trees are slow to walk, so performance-critical compilers flatten them and dispatch on a tag instead.

Diagram

sequenceDiagram
  participant C as Caller
  participant B as Mul node
  participant P as Printer
  participant L as Add node
  participant V as Var c
  C->>B: accept(printer)
  B->>P: visit_binop(self)
  P->>L: left.accept(printer)
  L->>P: visit_binop(self)
  P-->>L: ("a + b", prec 1)
  P->>V: right.accept(printer)
  V->>P: visit_var(self)
  P-->>V: ("c", prec 4)
  P-->>C: "(a + b) * c"

Worked example

A logistics company prices shipments with a rules DSL: about 3,400 expressions written by analysts, averaging 40 nodes each. The language has had the same 7 node types for three years. Operations, on the other hand, grew from 2 (evaluate, print) to 9: variable listing, unit checking, constant folding, a cost estimator, a deprecation linter, a JSON exporter and a diff renderer.

Each operation was a recursive function with an isinstance ladder. When a Clamp(x, lo, hi) node was added, 3 of the 7 operations then in use silently returned None for it; the unit checker passed every clamped expression unchecked, and a rule mixing kilograms and pounds ran in production for 11 days.

The team introduced a typed visitor interface with seven methods and a shared walker for read-only passes. The next node type, Lookup(table, key), broke the build in exactly the 9 places that had to decide what lookups mean. Evaluating all 3,400 rules took 14 ms in Python before and 16 ms after, against a 200 ms request budget.

Trade-offs

Option	Strengths	Weaknesses	Choose when
Methods on each node (Composite style)	Simple; new node types are local	Every new operation edits every class	Few operations, node types still changing
Classic visitor (`accept` + `visit_*`)	New operations are local; exhaustive in static languages	New node types edit every visitor; boilerplate	Stable node types, growing operations
Reflective visitor (`ast.NodeVisitor`)	Override only what you need; traversal built in	Missed types are silent; slower dispatch	Read-only analyses and lint rules
Walker with callbacks (`ast.Inspect`, Babel, ESLint)	One traversal shared by many passes	Order and pruning rules to learn; not exhaustive	Many independent passes over large trees
Exhaustive pattern matching (sealed types, unions)	No `accept`; compiler checks cases	Needs language support; closed set of types	Modern Java, TypeScript, Rust, Kotlin, Scala

Pitfalls in production

A new node type added without updating a reflective visitor, so the pass silently skips it. Fix: a test that builds a tree containing every node type and runs every visitor over it, or a static interface that forces the method.
Visitors that mutate the tree while walking (deleting a child from a list being iterated). Fix: write a transformer that returns new nodes, or collect edits and apply them after the walk.
Deep trees overflowing the stack in generated code. Fix: an explicit work stack, or balance long associative chains when parsing.
Stateful visitors reused across threads or requests, leaking results between traversals. Fix: construct a visitor per traversal; keep shared configuration in an immutable object passed in.
Each pass walking the whole tree separately, so 30 lint rules cost 30 traversals. Fix: a single walker that fans each node out to all interested passes, as ESLint does.

Leadership lens

Decide which axis is meant to grow. If product needs new operations weekly and new node types yearly, visitors pay off; if it is the reverse, they slow every change.
Ask in design review: "When someone adds a node type, what tells them every place that must change?" A compiler error or a failing exhaustive test is an acceptable answer; a code search is not.
Treat the visitor interface as a published contract when other teams write passes. Adding a method is a breaking change for them; a default base class with a loud failure for unknown types softens it.
For agents, "write a new visitor class implementing Visitor; do not edit node classes" is a precise, reviewable instruction, and the compiler checks the result.

Check yourself

Why does the visitor need two method calls (accept and visit_x) instead of one?
Show answer
Single-dispatch languages pick a method by one runtime type. The first call dispatches on the node's type, the second on the visitor's type, so together they select by both.
A team adds node types monthly and operations rarely. Is Visitor a good fit?
Show answer
No. Each new node type requires editing every visitor; methods on the node classes keep that change local.
What does Python's ast.NodeVisitor give up compared with a statically typed visitor interface?
Show answer
Exhaustiveness. It finds methods by name at runtime and falls back to generic_visit, so a forgotten node type is silently walked through instead of failing to compile.
Why do ESLint and Babel merge visitors from many rules or plugins into one traversal?
Show answer
Walking a large tree is the expensive part, mostly in pointer chasing and call overhead, so one walk that calls every interested listener per node is far cheaper than one walk per rule.

Watch

Double Dispatch: Prelude to the Visitor Pattern (Dave Leeds): why single dispatch is not enough, building up to the two-call trick.
Visitor Design Pattern Is Giving Way To Pattern Matching Expressions (Zoran on C#): replacing a visitor with exhaustive pattern matching and what each approach costs.
Visitor, Design Patterns in 5 minutes (levonog): a short visual overview of the structure.

Free resources

Representing Code (Crafting Interpreters, Robert Nystrom): the expression problem and the visitor pattern explained for a real interpreter.
ast module (Python docs): NodeVisitor, generic_visit and NodeTransformer, the reflective visitor in the standard library.
go/ast package (Go docs): Walk, Visitor and Inspect, Go's walker design.
Custom rules (ESLint docs): rule listeners keyed by node type and selector, all run in one traversal.
JEP 441: Pattern Matching for switch (OpenJDK): exhaustive switches over sealed types, the language-level alternative.
Expression problem (Wikipedia): the trade-off between adding types and adding operations, with history and solutions.

Open in the interactive app: practice, quiz, mock interview →