Visitor Pattern

Introduction

Visitor separates algorithms from the structures they operate on. Visitor has one method per element type; structure accepts visitor and dispatches via element.accept(visitor). Solves the expression problem for adding operations — new operation = new Visitor class; new element type = update every Visitor.

The story

A compiler had 30 AST node types and grew operations weekly: pretty-print, type-check, optimise, codegen, lint. Without Visitor each operation forked class hierarchies or bloated nodes. Each new operation became one Visitor class.

The business problem

Operations on stable structure grow faster than structure itself:

• Class bloat: toJson, toXml, validate, lint on every node class.
• Operation explosion: N operations × M node types maintenance.
• Wrong dependency direction: nodes know all export formats.
• Compiler passes: new pass shouldn't edit 30 node classes.

The problem teams faced

Visitor fits when:

• Stable element hierarchy; operations grow frequently.
• Operations need different context return types nodes shouldn't own.
• Double dispatch needed — operation depends on concrete element type.
• Structure is Composite/AST — traversal + typed dispatch.

Understanding the topic

Intent: Add operations without changing element classes.

• Element — accept(visitor) dispatches to visitX(this).
• Visitor — visitA(a), visitB(b) per element type.
• ConcreteVisitor — one operation (TypeCheckVisitor, CodegenVisitor).
• ObjectStructure — walks tree calling accept on each node.

Internal architecture

AST Visitor sketch:

interface ExprVisitor<T> {
  visitLiteral(node: LiteralExpr): T
  visitBinary(node: BinaryExpr): T
  visitVariable(node: VariableExpr): T
}

class TypeCheckVisitor implements ExprVisitor<Type> {
  visitLiteral(n: LiteralExpr) { return n.type }
  visitBinary(n: BinaryExpr) {
    const left = n.left.accept(this)
    const right = n.right.accept(this)
    return unify(left, right, n.op)
  }
  visitVariable(n: VariableExpr) { return lookup(n.name) }
}

// node.accept(v) => v.visitBinary(this)

Visual explanation

Three diagrams cover double dispatch, expression problem, and trade-off:

Informative example

Before / after — methods on nodes to Visitor:

// ❌ Every new pass edits every node class
class BinaryExpr {
  typeCheck() { /* ... */ }
  codegen() { /* ... */ }
  toJson() { /* ... */ }
  lint() { /* ... */ }
}

// ✅ New pass = new Visitor — nodes unchanged
interface ExprVisitor<T> {
  visitBinary(n: BinaryExpr): T
  visitLiteral(n: LiteralExpr): T
}

class CodegenVisitor implements ExprVisitor<string> {
  visitLiteral(n: LiteralExpr) { return String(n.value) }
  visitBinary(n: BinaryExpr) {
    return `(${n.left.accept(this)} ${n.op} ${n.right.accept(this)})`
  }
}

Execution workflow

Real-world use

Compiler AST passes, ESLint/Babel traversals, document export (HTML/PDF/Markdown from same DOM), insurance premium calculators on product trees, double-dispatch in multi-method languages.

Production case study

Compiler with 30 AST node types:

• Scenario: Weekly new passes — type-check, optimize, codegen, lint.
• Decision: Visitor per pass; accept() on each node type.
• Outcome: New pass = one class; node classes stable for years.
• Cost: New node type requires updating every visitor — rare after AST stabilizes.

Trade-offs

• Pro: add operations without editing element classes.
• Pro: related operation logic grouped in one visitor.
• Con: new element type requires updating all visitors.
• Con: breaks encapsulation — visitor accesses node internals.

Decision framework

• Use when structure stable and operations grow (compilers, linters).
• Use when Composite tree needs typed algorithm dispatch.
• Avoid when element types grow frequently — opposite force.
• Consider pattern matching (Rust/Swift) as modern alternative.

Best practices

• Generic Visitor return type for typed pass results.
• Keep node accept methods one-liners — dispatch only.
• Document visitor update checklist when adding node type.

Anti-patterns to avoid

• Visitor on 3-node hierarchy with 1 operation — overkill.
• Visitor accessing private fields without node API — coupling.
• Adding node types weekly in evolving DSL — wrong pattern.

Common mistakes

• Forgetting to update all visitors on new node type — compile errors help in typed languages.
• Visitor holding mutable traversal state without reset between runs.
• Circular node references — visitor infinite loop without visited set.

Debugging tips

• Log visitX entry with node id — trace which pass fails on which node.
• Golden-file test each visitor output on canonical AST fixtures.

Optimization strategies

• Short-circuit visitor when pass completes early (error in type-check).
• Single traversal combining visitors only when profiling proves worth it.

Common misconceptions

• Visitor ≠ Iterator. Visitor runs algorithm on elements; Iterator traverses sequence.
• Expression problem: Visitor adds operations easily, types hard — opposite of OOP default.
• Modern pattern matching reduces Visitor ceremony in Rust/Swift 5.9+.

Advanced interview questions

Summary

You can add compiler passes as Visitors, explain double dispatch and expression problem trade-offs. Tell the 30-node-type compiler story — if you can do that, you own Visitor.