ASTtypical

The Visitor as the Shape of a Pass

A pass is an object with one method per node kind — `visitBinaryExpression`, `visitFunctionDeclaration`, `visitCallExpression` — and the tree calls it. It is the standard shape of a compiler pass because it makes new passes free, and it is the standard complaint about compiler frontends because it makes new node kinds expensive.

The question

Why is every compiler pass written as a visitor, and what does that shape cost me?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The tree is unchanged; the visitor is a way of packaging a traversal so that node-kind dispatch happens once, in the walker, instead of once per pass. What it makes available is a per-node-kind entry point with the traversal already handled — the pass supplies behavior and inherits order. The question the shape answers is "how do I add an operation over every node kind without editing every node kind".

What this phase may assume or do

A visitor may assume that the walker calls exactly one method per node, that the node passed to visitX really is of kind X, and that its children have or have not been visited according to the documented order. It may not assume anything about nodes it does not handle — a default that silently recurses and a default that silently does nothing are different contracts, and a pass written against the wrong one is quietly incomplete. A visitor that mutates the tree is legal only if the walker documents that mutation during iteration is supported; otherwise the edits must be buffered and applied after the walk.

Key points

A visitor is one method per node kind plus a walker that dispatches to it; the pass supplies behavior and inherits traversal.
It makes adding an operation free and adding a node kind expensive — the expression problem, stated in code.
Match-per-function is the exact opposite trade: node kinds break loudly, operations are free.
Dispatch may be double dispatch, one exhaustive match, or a handler table; only the first two are checked by the compiler.
The default behavior of the base visitor — recurse or do nothing — is the most consequential line in the whole mechanism.
Overriding a visit method and forgetting to recurse silently removes an entire subtree from the analysis, with no error.

One method per node kind

The shape is unglamorous and that is its virtue. A pass is a bag of methods named after node kinds. The walker knows the tree, knows the order, and knows how to get from a node to the right method; the pass knows nothing except what to do when it arrives.

The payoff is that a new pass is one new object. A constant folder, a lint rule, a metrics collector, a code generator and a pretty-printer are all the same shape, all reuse the same traversal, and none of them touches the node definitions. In a frontend with dozens of passes that is not a convenience, it is the thing that makes dozens of passes tractable.

A type-checking pass, as a visitor

1interface Visitor<T> {
2  visitNumberLiteral(n: NumberLiteral): T
3  visitIdentifier(n: Identifier): T
4  visitBinaryExpression(n: BinaryExpression): T
5  visitCallExpression(n: CallExpression): T
6  visitFunctionDeclaration(n: FunctionDeclaration): T
7}
8 
9class TypeChecker implements Visitor<Type> {
10  constructor(private env: TypeEnv, private report: (n: Node, m: string) => void) {}
11 
12  visitNumberLiteral(_n: NumberLiteral): Type { return Type.Num }
13 
14  visitIdentifier(n: Identifier): Type { return this.env.lookup(n.name) ?? Type.Error }
15 
16  visitBinaryExpression(n: BinaryExpression): Type {
17    const l = accept(n.lhs, this)          // children first: post-order
18    const r = accept(n.rhs, this)
19    if (l !== r) this.report(n, 'operands of ' + n.op + ' have different types')
20    return l
21  }
22 
23  visitCallExpression(n: CallExpression): Type {
24    const fn = accept(n.callee, this)
25    const args = n.args.map((a) => accept(a, this))
26    return fn.kind === 'fn' && fn.params.length === args.length ? fn.result : Type.Error
27  }
28 
29  visitFunctionDeclaration(n: FunctionDeclaration): Type {
30    this.env.push(n.params)                // context down: pre-order
31    accept(n.body, this)
32    this.env.pop()
33    return Type.Void
34  }
35}

Notice that both traversal orders from [[ast-traversal]] appear in one class: visitBinaryExpression visits children first because it needs their types, and visitFunctionDeclaration pushes an environment before visiting its body. The visitor does not choose an order globally; each method chooses when it recurses.

How the dispatch actually happens

implementationClang provides several visitor flavours that are not interchangeable: RecursiveASTVisitor walks and dispatches, StmtVisitor dispatches without walking, and ASTMatchers express node patterns declaratively for tools. Choosing the wrong one produces a pass that compiles and visits nothing, which is a common first-day mistake with the codebase. Other frontends make similar distinctions under different names.

There are three common mechanics, and they differ in where the node-kind decision lives. In a class hierarchy, each node has an accept(visitor) method that calls the right visitX — the classic double dispatch, and the reason the pattern has that name. In a tagged-union language, the walker does one match on the node kind and calls the method; the "pattern" collapses into a single switch statement in one place, which is all it ever was.

The third mechanic is a table: a map from node kind to handler function, which is what most JavaScript AST tooling uses (ESLint rules register BinaryExpression and BinaryExpression:exit handlers, and the walker looks them up). It is the most flexible — handlers can be registered dynamically, and several passes can share one walk — and the least checked, because a typo in a node-kind string is a handler that is simply never called.

None of these is more "correct". They differ in what the compiler can check for you and in how much machinery a new pass needs. The pattern is worth its name only in the first case; in the other two it is a convention, and calling it a pattern mostly obscures how little is going on.

Three dispatch mechanics for the same shapetypical

Mechanic	Where kind dispatch lives	Checked by the compiler?	Typical home
Double dispatch (`accept`)	On the node, one `accept` per class	Yes — a missing `visitX` fails to compile if the interface requires it	C++ and Java frontends, Clang's `StmtVisitor`
Match in the walker	One exhaustive `match` in one place	Yes — exhaustiveness checking flags a new kind	Rust, OCaml, Swift frontends
Handler table by kind name	A map from string to function	No — an unregistered or misspelled kind is silently never visited	ESLint, Babel plugins, ESTree tooling

The expression problem, briefly and concretely

The visitor makes one kind of change free and the opposite kind expensive, and there is a name for that trade: the expression problem. Data lives in two dimensions — the set of node kinds, and the set of operations over them — and mainstream languages let you extend one dimension without editing existing code, not both.

Visitors extend the *operation* dimension. A new pass is a new class; no node type changes; nothing recompiles that did not need to. Adding a node kind is the expensive direction: every visitor interface grows a method, and every implementation must supply one or inherit a default whose behavior is now silently applied to a construct it was never written for.

Match-per-function is the mirror image. A new node kind breaks every function that matches on kinds, loudly and at compile time, and you go fix them — which is the *good* failure. A new operation is one new function and costs nothing. So the two styles are not competing implementations of the same idea; they are opposite answers, and the right one depends on which dimension is still moving.

For a mature language whose syntax is settled and whose tooling keeps growing — C++, Java, C# — visitors are clearly right, and their frontends are full of them. For a language still adding syntax, or for a research compiler, the loud break on a new node kind is worth more than cheap new operations. The practical resolution most frontends reach is to use tagged unions with exhaustive matching *and* provide a visitor helper for the passes that want traversal handled, accepting the small redundancy.

Adding a pass with visitors: one new class, nothing else changes.
Adding a node kind with visitors: every visitor interface and implementation is touched, or silently inherits a default.
Adding a node kind with exhaustive matching: everything breaks at compile time and you fix it, which is what you want.
Adding a pass with exhaustive matching: one new function, nothing else changes — same as visitors.
The asymmetry is only about *which change the compiler will not let you forget*. Both styles work; only one of them protects the direction you care about.

Defaults are the part that goes wrong

The single most common visitor bug is not in a visit method, it is in the default. A base visitor whose default recurses into children makes a partial pass work: implement visitCallExpression only, and the walker still reaches every call anywhere in the tree. A base visitor whose default does nothing makes the same pass silently visit only calls that happen to be at the root.

Both defaults are defensible and both are common, which is why the mistake keeps happening across codebases. The rule worth carrying is that a visitor base class must document its default in the same sentence as its name, and that a pass which handles a node kind must decide explicitly whether it still wants children visited — because implementing visitFunctionDeclaration and forgetting to recurse is how an entire function body stops being analysed with no error anywhere.

Overriding a visit method without recursing

Before

visitFunctionDeclaration(n) { recordFunction(n) }

After

visitFunctionDeclaration(n) { recordFunction(n); visitChildren(n) }

Legal only when

Adding the recursion is required whenever the pass must observe anything inside the function body, which is every pass except those that genuinely operate on declarations alone (a signature collector, an export list, a symbol index). Omitting it is legal only when the pass has a stated reason not to descend, and that reason belongs in a comment because the next reader will assume it is a bug.

Illegal when

Recursing is wrong when the pass is deliberately shallow — a declaration-collecting pre-pass that must record every top-level name *without* resolving anything inside bodies, because the bodies refer to names the pass has not collected yet. Descending there does not merely waste time, it produces resolution errors for names that are about to become valid; see [[declaration-order]].

How it works

The steps, in the order the compiler takes them.

Define a visitor interface with one method per node kind, parameterised by the result type the pass produces.
Provide a walker that, given a node, determines its kind and calls the matching method — by accept, by an exhaustive match, or by a table lookup.
Provide a base implementation whose default either recurses into children or does nothing, and document which.
A pass implements the methods it cares about and decides, in each, whether to recurse before, after, or not at all.
Results are returned up (post-order information) or accumulated in fields on the visitor (context and collected output).
Passes that need to run together either share a handler table over one walk, or run as separate walks — the second being the default choice for anything that is not measured to be too slow.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A visit method is overridden without recursing, and every node inside that construct disappears from the analysis. The lint rule finds nothing in any function body; the pass reports success; no error is raised anywhere.
A new node kind is added and every visitor inherits the base default. Behavior looks right in tests written before the feature and is quietly wrong for the new syntax — this is the failure mode the visitor pattern structurally invites.
A handler is registered under a misspelled node-kind string. The rule is never called, the test that would have caught it was written against the same typo, and the rule ships doing nothing.
Two passes were merged into one visitor with shared mutable fields, and one pass leaves state behind that the other reads. The compiler produces different output depending on file order.
A visitor mutates the tree while the walker is iterating a child list. Nodes are visited twice or skipped, and the output is non-deterministic across runs.

When it helps

A stable set of node kinds with a growing set of analyses — the situation of every mature language's tooling ecosystem.
Letting third parties add passes: a lint plugin API is a visitor interface, and that is not a coincidence.
Keeping traversal logic in exactly one place, so a fix to child ordering or a new construct's children benefits every pass at once.

When it hurts

A language still gaining syntax. Every new node kind ripples through every visitor, and the ones that silently inherit a default are the ones you will not find.
Passes whose behavior does not decompose by node kind — a whole-tree structural diff, or an analysis keyed on paths rather than nodes, fights the shape the whole way.
Passes that must rewrite the tree in place, where the visitor's "visit and return nothing" shape is the wrong signature and a transformer that returns replacements is what you want — see [[ast-transformations]].

What it costs

Every one of these is paid by something.

Visitors buy free addition of operations and pay for it in every future node kind, which must be added to every interface and every implementation or silently fall through to a default.
A recursing default buys correct-by-accident partial passes and costs the ability to notice that a pass never handled a construct at all — everything "works", nothing was checked.
A do-nothing default buys explicitness and costs a class of subtle bugs where a pass silently sees only the top of the tree.
Handler tables buy dynamic registration and shared walks and cost every static check: an unregistered kind is indistinguishable from a kind with nothing to do.
Putting traversal in the walker buys one place to fix child ordering and costs pass authors the ability to control the walk without escaping the abstraction, which they periodically need to do anyway.

What else you could do

What a different compiler or language does instead, and when that is better.

Exhaustive pattern matching per function, in a language that checks it. Adding a node kind becomes a compile error in every pass, which is precisely the protection visitors cannot give — see [[pattern-matching]] and [[exhaustiveness-checking]].
Declarative node matchers: Clang's ASTMatchers and Semgrep-style patterns let a tool state the shape it wants rather than implement dispatch. Far less code for pattern-shaped queries, and no help at all for a pass that must compute something over everything.
Query-driven analysis, where nothing traverses eagerly and each fact is demanded and memoised. Buys incrementality, costs a query framework and cycle detection.
Open multi-methods or type classes, which solve the expression problem properly in languages that have them — Clojure's multimethods, Haskell's type classes. Rarely available in the language a production compiler is written in, which is why the trade is usually just accepted.

See it for yourself

The flag, dump or tool that shows you this directly.

Clang: read clang/AST/RecursiveASTVisitor.h. The TraverseX / WalkUpFromX / VisitX split is the enter/exit/dispatch distinction made explicit in a production frontend.
Python: ast.NodeVisitor and ast.NodeTransformer — the first recurses via generic_visit only if you call it, which is the recursing-default trap in ten lines of standard library.
JavaScript: write an ESLint rule with BinaryExpression(node) {} and BinaryExpression:exit(node) {} and log both; the handler-table mechanic and the two visit points become concrete immediately.
Rust: syn::visit::Visit and syn::visit_mut::VisitMut show the read-only and mutating variants side by side, including why they cannot be the same trait.

Plausible wrong readings

Stated the way a confident engineer states them.

"The visitor pattern is object-oriented ceremony you can skip in a modern language." What you skip is the accept boilerplate. The shape — one handler per node kind, traversal factored out — remains, because it is what a pass *is*.
"Visitors are for traversal." They are for dispatch. Some visitors traverse and some do not, and confusing the two is how you write a pass that visits exactly one node.
"The expression problem is academic." It is the reason adding one node kind to a mature frontend is a multi-day change, and the reason your lint plugin silently ignored the new syntax.
"If my visit method is called, my pass saw that construct." Only if something recursed into it. Silence from a visitor is not evidence of absence.

Misconceptions

The claim, and what is actually true.

The visitor pattern exists to walk trees.

It exists to dispatch on node kind. Walking is a separate concern that visitor implementations usually bundle in, which is why so many of them get the default recursion wrong.

A pattern-matching language does not need visitors.

It does not need the accept double dispatch. It still needs the traversal factored out somewhere, and most such compilers ship a Visit/VisitMut trait for exactly that.

A visitor with a method for every node kind is a complete pass.

Completeness depends on recursion, not on method count. A visitor with every method implemented and no recursion sees exactly one node.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

practical

When adopting a frontend's visitor, answer two questions before writing a line: does the base default recurse, and does overriding a method suppress the recursion? Every silent-nothing-happened bug in a first pass comes from one of those two, and both are answered by reading ten lines of the base class. Then log every visit with kind and span on your first run; a pass that visits fewer nodes than you expect is far easier to see than to reason about.

advanced

The expression problem tells you which style a codebase should use, but real frontends do not choose once. rustc matches exhaustively in the compiler proper and also exposes visitor traits for lints; Clang has RecursiveASTVisitor for passes and ASTMatchers for tools, because a refactoring tool wants to state a pattern and a semantic analysis wants to compute over everything. The mature position is that dispatch style is per-consumer, and a frontend serving several audiences will provide more than one — which is a maintenance cost accepted deliberately, and one more reason [[ast-as-shared-infrastructure]] is a design stance rather than a happy accident.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

typicalThat compiler passes are written as visitors describes frontends in class-based languages — Clang, Roslyn, javac, the TypeScript compiler. Frontends in ML-family languages usually write a plain recursive function with an exhaustive match and no visitor object at all; rustc does this pervasively. Both are the same computation, and the difference is which extension direction the host language protects.

implementationThe claim that a missing visitX fails to compile holds only when the visitor interface requires every method. Base classes that supply defaults for all of them — which is most of them, because otherwise every pass must implement two hundred no-ops — remove exactly that protection. Check whether the base class in front of you is an interface or a convenience default before relying on the compiler to catch an omission.

simplifiedThe TypeChecker above returns a type from every method and reports errors through a callback. A real checker also records the type on a side table keyed by node id (so later phases can read it), handles error types without cascading, and distinguishes "no type yet" from "type error" — omitting all three is what keeps the example to one screen.

If you were asked this in an interview

Why is a compiler pass usually a visitor rather than a free function with a switch?
State the expression problem using a compiler frontend as the example, and say which direction visitors protect.
A new lint rule reports nothing on code that obviously matches it. What are the first two things you check?
When would you deliberately *not* recurse in a visit method?

Connections

DSAdfs n-ary-tree

Domains that do not exist yet

Software Design — The visitor as a general-purpose design pattern, and double dispatch
The pattern is not compiler-specific: it is the standard answer to "add an operation over a closed set of types". The general form, its relationship to double dispatch, and the expression problem as a design-of-code question belong there. What is ours is that a compiler frontend is the case where the set of types really is closed, really is large, and really does keep acquiring operations — which is why the pattern is more load-bearing here than anywhere else it appears.