Visitor Pattern

Overview

Intent: Represent an operation to be performed on elements of an object structure. Visitor lets you define a new operation without changing the classes of the elements on which it operates.

Category: Behavioural Design Pattern
Complexity: High
Also Known As: Double Dispatch Pattern

The Visitor pattern separates an algorithm from the object structure it operates on. Instead of embedding every possible operation inside each element class, you externalize operations into visitor objects. Each visitor encapsulates a single cohesive operation across all element types, and elements simply "accept" visitors by dispatching to the appropriate method.

This inversion of control is powerful when your object structure is stable (elements rarely change) but you frequently need new operations over those elements.

---

Problem It Solves

The core tension: You have a class hierarchy of elements (e.g., AST nodes, document parts, UI components) and you need to perform many unrelated operations on them. Without Visitor, you face two bad options:

1. Pollute element classes - Add every operation (rendering, exporting, validation, metrics) directly into each element. This violates Single Responsibility and requires modifying elements for every new operation.

2. Use instanceof/type-checking - Scatter if/else or switch statements across your codebase. This is fragile, violates Open/Closed Principle, and misses compile-time safety.

Double dispatch in single-dispatch languages: Most OOP languages (Java, C++, C#) dispatch method calls based only on the receiver's runtime type (single dispatch). The Visitor pattern achieves double dispatch - selecting behaviour based on both the element type and the visitor type - through the accept/visit protocol. The element's accept() resolves the first dispatch (element type), and the overloaded visit() resolves the second (visitor type).

---

When to Use / When NOT to Use

---

Key Concepts & Theory

Double Dispatch

In single-dispatch languages, element.render() dispatches based on the runtime type of element. But visitor.visit(element) dispatches based on the compile-time type of the parameter. Double dispatch solves this: element.accept(visitor) dispatches on element type first, then visitor.visitConcreteElement(this) dispatches on visitor type - achieving selection based on both runtime types.

Accept/Visit Protocol

Every element implements accept(Visitor v) by calling v.visit(this). The this reference carries concrete type information, enabling the compiler to select the correct overloaded visit() method. This two-step handshake is the mechanical heart of the pattern.

Element Stability vs Operation Variability

The Visitor pattern bets on the stability of the element hierarchy. Adding a new element type forces changes to every visitor (violating OCP for visitors). Adding a new operation only requires a new visitor class (satisfying OCP for operations). This asymmetry is the fundamental trade-off.

Open/Closed Principle Application

• Open for extension: New operations (visitors) can be added without modifying existing code.
• Closed for modification: Existing element classes and existing visitors remain untouched when adding new operations.
• The flip side: Adding new element types violates OCP for all existing visitors.

---

ASCII Class Diagram

┌─────────────────────────────┐         ┌─────────────────────────────────┐
│      <<interface>>          │         │        <<interface>>             │
│         Visitor             │         │          Element                 │
├─────────────────────────────┤         ├─────────────────────────────────┤
│ + visitElementA(ElementA)   │         │ + accept(Visitor v)             │
│ + visitElementB(ElementB)   │         └────────────┬────────────────────┘
└──────────┬──────────────────┘                      │
           │                               ┌─────────┴─────────┐
    ┌──────┴──────┐                        │                   │
    │             │                        ▼                   ▼
┌───┴─────────┐ ┌┴──────────────┐  ┌─────────────┐    ┌─────────────┐
│ConcreteVisit│ │ConcreteVisitor│  │  ElementA   │    │  ElementB   │
│   or1       │ │      2        │  ├─────────────┤    ├─────────────┤
├─────────────┤ ├───────────────┤  │+accept(v):  │    │+accept(v):  │
│visitElementA│ │visitElementA  │  │ v.visitA(th)│    │ v.visitB(th)│
│visitElementB│ │visitElementB  │  └─────────────┘    └─────────────┘
└─────────────┘ └───────────────┘

        Flow: client → element.accept(visitor)
                     → visitor.visitElementX(this)

---

Pseudocode Implementation

Document Elements with Multiple Visitors

// ─── Element Interface ───
interface DocumentElement {
    accept(visitor: DocumentVisitor)
}

// ─── Concrete Elements ───
class TextElement implements DocumentElement {
    content: String
    accept(visitor: DocumentVisitor) {
        visitor.visitText(this)       // double dispatch: resolves to concrete visitor method
    }
}

class ImageElement implements DocumentElement {
    url: String
    altText: String
    accept(visitor: DocumentVisitor) {
        visitor.visitImage(this)
    }
}

class TableElement implements DocumentElement {
    rows: List<List<String>>
    accept(visitor: DocumentVisitor) {
        visitor.visitTable(this)
    }
}

// ─── Visitor Interface ───
interface DocumentVisitor {
    visitText(element: TextElement)
    visitImage(element: ImageElement)
    visitTable(element: TableElement)
}

// ─── Concrete Visitors ───
class RenderVisitor implements DocumentVisitor {
    output: StringBuilder

    visitText(e: TextElement) {
        output.append("<p>" + e.content + "</p>")
    }
    visitImage(e: ImageElement) {
        output.append("<img src='" + e.url + "' alt='" + e.altText + "'/>")
    }
    visitTable(e: TableElement) {
        output.append("<table>")
        for row in e.rows:
            output.append("<tr>")
            for cell in row:
                output.append("<td>" + cell + "</td>")
            output.append("</tr>")
        output.append("</table>")
    }
}

class ExportVisitor implements DocumentVisitor {
    pdfWriter: PdfWriter

    visitText(e: TextElement) {
        pdfWriter.addParagraph(e.content)
    }
    visitImage(e: ImageElement) {
        pdfWriter.embedImage(e.url)
    }
    visitTable(e: TableElement) {
        pdfWriter.addTable(e.rows)
    }
}

class WordCountVisitor implements DocumentVisitor {
    count: int = 0

    visitText(e: TextElement) {
        count += e.content.split(" ").length
    }
    visitImage(e: ImageElement) {
        count += e.altText.split(" ").length
    }
    visitTable(e: TableElement) {
        for row in e.rows:
            for cell in row:
                count += cell.split(" ").length
    }
}

// ─── Client Usage ───
document = [TextElement("Hello world"), ImageElement("/img.png", "logo"), TableElement([["A","B"]])]
renderer = RenderVisitor()
for element in document:
    element.accept(renderer)
print(renderer.output)    // <p>Hello world</p><img .../>...

AST Example: Compiler Visiting Expression Nodes

// ─── AST Elements ───
interface ASTNode {
    accept(visitor: ASTVisitor)
}

class NumberLiteral implements ASTNode {
    value: double
    accept(v: ASTVisitor) { v.visitNumber(this) }
}

class BinaryExpression implements ASTNode {
    left: ASTNode
    right: ASTNode
    operator: String
    accept(v: ASTVisitor) { v.visitBinary(this) }
}

class FunctionCall implements ASTNode {
    name: String
    args: List<ASTNode>
    accept(v: ASTVisitor) { v.visitFunctionCall(this) }
}

// ─── Visitor Interface ───
interface ASTVisitor {
    visitNumber(node: NumberLiteral)
    visitBinary(node: BinaryExpression)
    visitFunctionCall(node: FunctionCall)
}

// ─── Code Generator Visitor ───
class CodeGenVisitor implements ASTVisitor {
    instructions: List<String>

    visitNumber(node: NumberLiteral) {
        instructions.add("PUSH " + node.value)
    }
    visitBinary(node: BinaryExpression) {
        node.left.accept(this)      // recurse into children
        node.right.accept(this)
        instructions.add(operatorToOpcode(node.operator))
    }
    visitFunctionCall(node: FunctionCall) {
        for arg in node.args:
            arg.accept(this)
        instructions.add("CALL " + node.name + " " + node.args.size)
    }
}

// ─── Type Checker Visitor ───
class TypeCheckVisitor implements ASTVisitor {
    visitNumber(node: NumberLiteral) { return Type.NUMBER }
    visitBinary(node: BinaryExpression) {
        leftType = node.left.accept(this)
        rightType = node.right.accept(this)
        if leftType != rightType: throw TypeError(...)
    }
    visitFunctionCall(node: FunctionCall) {
        // look up function signature, validate arg types
    }
}

---

Double Dispatch Explained

Consider element.accept(visitor) where element is a TextElement and visitor is a RenderVisitor:

Step 1: Client calls element.accept(visitor)
        ┌─────────────────────────────────────────────────┐
        │ Runtime resolves element → TextElement           │
        │ (First dispatch: based on element's type)       │
        └─────────────────────────────────────────────────┘

Step 2: Inside TextElement.accept(), calls visitor.visitText(this)
        ┌─────────────────────────────────────────────────┐
        │ 'this' is statically typed as TextElement       │
        │ Compiler selects visitText(TextElement) overload│
        │ Runtime resolves visitor → RenderVisitor        │
        │ (Second dispatch: based on visitor's type)      │
        └─────────────────────────────────────────────────┘

Step 3: RenderVisitor.visitText(TextElement) executes
        ┌─────────────────────────────────────────────────┐
        │ Correct method selected based on BOTH types:    │
        │   - Element type (TextElement)                  │
        │   - Visitor type (RenderVisitor)                │
        └─────────────────────────────────────────────────┘

Why not just overload visit()? If you wrote visitor.visit(element) where element is declared as Element (the interface), the compiler would bind to visit(Element) - not visit(TextElement). The accept() indirection ensures this carries the concrete type at compile time, enabling correct overload resolution.

---

Real-World Examples

Notable implementations in practice:

• Java's javax.lang.model (annotation processing) uses Visitor extensively
• LLVM's InstVisitor for visiting IR instructions
• Babel/ESLint AST visitors for JavaScript transformation
• java.nio.file.FileVisitor for walking directory trees
• Roslyn (C# compiler) syntax tree visitors

---

Visitor vs Iterator vs Strategy

---

Advantages & Disadvantages

---

Constraints & Edge Cases

Adding New Element Types Breaks All Visitors (OCP Violation)

This is the fundamental constraint. If you add VideoElement to the document hierarchy, every existing visitor must be updated with a visitVideo() method. Mitigation strategies:

• Provide a visitDefault() fallback in the visitor interface
• Use the Acyclic Visitor variant (see below)
• Accept this trade-off only when element types are genuinely stable

Circular Dependencies

Visitor depends on all ConcreteElement types (method parameters), and each ConcreteElement depends on Visitor (accept parameter). In languages with header files (C++), this creates circular includes. Solutions: forward declarations, or separating visitor interface into its own compilation unit.

Visitor with State

Visitors that accumulate state (e.g., WordCountVisitor.count) are not thread-safe by default. Options:

• Create a new visitor instance per traversal
• Use thread-local state
• Make the visitor immutable and return new state from each visit

Acyclic Visitor Variant (Robert Martin)

Breaks the dependency cycle by using an empty marker interface as the base visitor and individual ElementXVisitor interfaces per element type. Each element's accept() does a runtime type check:

class TextElement {
    accept(visitor: Visitor) {
        if visitor instanceof TextVisitor:
            (visitor as TextVisitor).visitText(this)
    }
}

Trade-off: loses compile-time safety but gains the ability to add elements without breaking existing visitors.

Other Edge Cases

• Null elements in structure: Guard accept() calls or use Null Object pattern
• Recursive structures: Visitor must handle re-entrant calls (e.g., BinaryExpression visiting children)
• Return values: Some implementations use generics (Visitor<R>) to return typed results from visit methods

---

Interview Follow-ups

Q1: How does the Visitor pattern relate to the Open/Closed Principle?

A: It applies OCP asymmetrically. The design is open for new operations (add a visitor) and closed for modification of elements. However, it violates OCP in the other dimension - adding a new element type requires modifying all existing visitors. This makes it ideal when the element hierarchy is stable but operations change frequently.

Q2: Can you implement Visitor without modifying the element classes (no accept() method)?

A: Yes, but you lose type-safe double dispatch. Alternatives include:

• Reflection-based dispatch: Use runtime type inspection to select the correct visit method. Languages like Python/Ruby do this naturally with dynamic dispatch.
• Pattern matching: Languages with sealed classes and pattern matching (Kotlin when, Scala match) achieve the same effect without the accept/visit ceremony.
• Extension methods + type checks: Less elegant but avoids modifying elements.

Q3: How would you handle a visitor that needs to return different types for different elements?

A: Use a generic visitor interface: Visitor<R> with methods returning R. Each accept() also returns R. For heterogeneous return types, use a wrapper type or union. In practice, many visitors accumulate results in internal state rather than returning from visit methods.

Hint-Only Questions

H1: Design a visitor that transforms an AST in-place versus one that produces a new tree. What are the trade-offs?

Hints:

• Consider immutability and functional transformation vs mutation
• Think about parent references and how replacement propagates upward
• Look at how Babel's visitor returns null to delete, a new node to replace, or undefined to keep

H2: How would you implement undo/redo using the Visitor pattern?

Hints:

• Each visitor could produce a "reverse visitor" or command object
• Consider combining Visitor with Memento or Command pattern
• Think about what state the visitor captures before making changes

---

Counter Questions to Ask Interviewer

1. "How stable is the element hierarchy?" - If new element types are added frequently, Visitor may be the wrong pattern. This question demonstrates you understand the core trade-off.

2. "Do operations need to accumulate state across elements, or are they independent per element?" - Stateful traversal is a Visitor strength; independent operations might be simpler with polymorphism.

3. "Does the language support pattern matching or multiple dispatch?" - In Kotlin, Scala, or Julia, the Visitor ceremony may be unnecessary since the language provides the dispatch mechanism natively.

4. "Are there performance constraints on the double dispatch?" - Virtual method calls have overhead; in hot paths (game loops, real-time systems), the indirection may matter.

5. "Should visitors be composable?" - Can we chain visitors or run them in parallel? This affects whether visitors should be stateless or carry isolated state.

---

References & Whitepapers

1. Gamma, Helm, Johnson, Vlissides - Design Patterns: Elements of Reusable Object-Oriented Software (1994), Chapter 5: Visitor Pattern. The canonical reference.

2. Robert C. Martin - Acyclic Visitor (1996). Proposes breaking the dependency cycle using degenerate base visitors and runtime type checks. Published in Pattern Languages of Program Design 3.

3. "Visitor Pattern Considered Harmful" - Various discussions (notably by Radu Grigore and others) arguing that Visitor's complexity is rarely justified in modern languages with pattern matching, sealed classes, or algebraic data types.

4. Palsberg & Jay - The Essence of the Visitor Pattern (1998). Formalizes the pattern using type theory and shows its connection to catamorphisms (folds over algebraic data types).

5. Krishnamurthi, Felleisen, Friedman - Synthesizing Object-Oriented and Functional Design to Promote Re-Use (1998). Discusses the expression problem and how Visitor addresses one dimension of extensibility.

6. Oracle Java Documentation - javax.lang.model.element.ElementVisitor, java.nio.file.FileVisitor - production implementations in the Java standard library.

---

Related Topics

• Strategy Pattern - swaps algorithms without Visitor's type-aware dispatch
• Iterator Pattern - traverses structures uniformly without type-specific operations
• Composite Pattern - often paired with Visitor; Visitor traverses composite structures
• Command Pattern - encapsulates operations as objects; can complement Visitor for undo
• Interpreter Pattern - uses Visitor-like traversal for evaluating grammar trees
• Double Dispatch & Multimethods - language-level alternatives to the Visitor ceremony