Visitor

The Visitor Pattern is a behavioral design pattern that allows you to separate algorithms from the objects on which they operate. By establishing a double dispatch mechanism, it lets you add new operations to a heterogeneous class hierarchy without modifying the source code of the classes themselves.

1. Learning Objectives

• Identify when to apply the Visitor pattern to decouple operations from complex class structures.
• Understand the mechanics of Double Dispatch and how it resolves concrete class types at runtime.
• Analyze the compile-time dependencies introduced by Visitor interfaces.
• Compare the structure and intent of Visitor, Composite, and Strategy patterns.
• Implement dynamic method dispatch visitors in Python (overcoming the lack of method overloading) and C++.

2. Problem & Naive Solution

Suppose you are building an e-commerce checkout engine. The system contains an object list representing a shopping cart: Book, Electronics, and Clothing. You need to calculate checkout metrics on these items:

• Calculate Sales Tax (varies by product category).
• Calculate Shipping Cost (depends on product weight and size).
• Calculate Loyalty Points earned.

The Naive Solution

A developer might implement these operations directly inside each product class:

This design introduces significant design flaws:

• Violates Single Responsibility Principle: The core domain models (Electronics, Book) are bloated with tax rules, shipping formulas, and discount schemes that are unrelated to basic product properties.
• Violates Open/Closed Principle: Every time a new operation is needed (e.g. export to XML, generate discount invoice), you must modify the source code of all product classes.
• Frequent Recompilations: Changes to tax regulations force recompilation of the entire product hierarchy, risking regressions in core classes.

3. Issues

Directly embedding algorithms inside class structures makes maintenance difficult. If the data structure (product catalog) is stable but the operations (tax calculations, reports) change frequently, subclassing fails, leading to duplicate code and tight coupling.

4. Pattern Introduction & UML

The Visitor Pattern solves this by extracting the operations into separate visitor classes. The products (Elements) implement an ItemElement interface exposing an accept(Visitor) method. When a visitor visits, the element calls visitor.visit(this). This call triggers Double Dispatch, delegating execution to the appropriate overloaded method on the visitor based on the element's concrete type.

UML: Tax & Shipping Visitor

5. Participants

• Element (ItemElement): Interface declaring the accept(Visitor) method.
• Concrete Element (Book, Electronics): Implements accept(), calling the visitor back (visitor.visit(this)).
• Visitor (Visitor): Interface declaring overloaded visit() methods for each concrete element class in the hierarchy.
• Concrete Visitor (TaxVisitor, ShippingWeightVisitor): Implements operations on the elements.
• Object Structure (ShoppingCart): Maintains the collection of elements and iterates over them, letting the visitor visit each.

6. Theory (Double Dispatch Mechanism)

To understand Visitor, you must understand Double Dispatch:

• Single Dispatch (Standard): Most object-oriented languages (like Java and C++) resolve method calls based on the dynamic type of the receiver object (dynamic polymorphism). Parameter types are resolved statically at compile-time.
• Double Dispatch: Bypasses static parameter binding. 1. First Dispatch: Client calls element.accept(visitor). Dynamic dispatch resolves which element's accept() method to call. 2. Second Dispatch: Inside accept(), the element calls visitor.visit(this). Since this has a concrete type known at compile-time within that class, it dispatches execution to the correct overloaded visit() method on the visitor.

7. Syntax Explanation

Syntax construction details:

• Java: Uses method overloading (multiple visit() methods with different parameter types) to support clean double dispatch.
• Python: Lacks method overloading. You must use reflection (e.g. looking up method names dynamically: getattr(self, f"visit_{type(element).__name__.lower()}")(element)) to route execution.
• C++: Requires forward declaring concrete element classes in the visitor header file to resolve compiler dependencies.

8. Step-by-Step Implementation

1. Step 1: Create the Visitor interface defining overloaded visit() methods for each element subclass.
2. Step 2: Create the ItemElement interface declaring accept(Visitor).
3. Step 3: Implement accept(Visitor) inside the concrete element classes, calling visitor.visit(this).
4. Step 4: Build concrete visitor classes implementing the Visitor interface to calculate specific metrics.
5. Step 5: Write the client code to iterate over the elements and pass the visitor to each.

9. Complete Code (Mini Project)

10. Code Walkthrough

Let's review the double dispatch execution path:

• First Dispatch: The client calls item.accept(taxVisitor) polymorphically. Dynamic dispatch resolves which element's accept() method to call (e.g. Book.accept()).
• Second Dispatch: Inside Book.accept(), the class executes visitor.visit(this). Since this has the concrete type Book known at compile-time within that class, it routes execution to the correct overloaded visit(Book) method on the visitor.
• Decoupled Algorithms: Calculations are isolated inside visitor subclasses (TaxVisitor, ShippingVisitor). Adding a new calculation doesn't require modifying the product classes.

11. Execution Flow

1. Accept Call: Client calls accept(visitor) on an element.
2. Type Resolution: Dynamic dispatch resolves which element's accept() method is called.
3. Visit Call: The element calls visitor.visit(this).
4. Double Dispatch: The compiler matches the overloaded method, executing the concrete visitor logic.
5. Return Value: The calculation result is returned to the client.

12. Internal Working (JVM Dispatch & Memory Layout)

How the JVM resolves double dispatch at runtime:

• Dynamic Method Dispatch table (vtable): The first dispatch (item.accept()) performs a runtime lookup in the class's Virtual Method Table (vtable) to find the correct method address.
• Static Overload Resolution: The second dispatch (visitor.visit(this)) is resolved statically by the compiler because the type of this is explicitly known inside each element class. This avoids a second vtable lookup, keeping execution fast.

13. Complexity Analysis

• Time Complexity: $O(1)$ constant time overhead to resolve the double dispatch.
• Space Complexity: $O(1)$ constant memory overhead to hold base class reference pointers.

14. Best Practices

• Use when Elements are Stable: Only apply Visitor when the class hierarchy is stable. If new product types (e.g. Grocery) are added frequently, you must update the Visitor interface and all its subclasses, defeating the pattern's benefit.
• Keep Visitors Stateless: Avoid storing state inside visitor classes. Instead, pass calculation results back using return types or accumulator parameters.

15. Common Mistakes

• Skipping Double Dispatch: Using instanceof checks inside visitors instead of implementing accept() loops, which breaks runtime polymorphism.
• Applying to Unstable Hierarchies: Using Visitor in rapidly changing class hierarchies, causing massive refactoring work whenever a new class is added.

16. Framework Usage

• Abstract Syntax Tree (AST) Parsers: Compilers (like javac, python compiler, Babel) use Visitor to traverse AST node structures, applying optimizations, type checks, and code generation steps polymorphically.
• Static Analysis Tools: Code linters (like ESLint, Checkstyle) parse code structures into trees and use visitors to identify security vulnerabilities or formatting issues.

17. Interview Discussion

18. Practice Exercises

• Easy: Write a Python program containing a visitor that prints elements as formatted strings.
• Medium: Design a Shape hierarchy (Circle, Rectangle) with a DrawingVisitor rendering shapes on different graphics backends.
• Hard: Build a file system representations explorer. Elements are files and directories. Implement visitors that print directory trees and calculate total file sizes.

19. Challenge Problem

Design an Abstract Syntax Tree (AST) Math Equation Compiler. The expression compiler represents equation elements in a tree: NumberNode, AdditionNode, and MultiplicationNode. You must implement visitors to perform two tasks: EvaluationVisitor (computes the final numeric value) and LaTeXGeneratorVisitor (compiles the node tree into LaTeX markup format strings). Write this system in Java, Python, or C++ and test it with nested expressions.

20. Summary & Cheat Sheet

• Visitor separates algorithms from the objects on which they operate.
• Enables double dispatch: dynamic dispatch on the element type and static overloading on the visitor.
• Only use Visitor when the element class hierarchy is stable.
• Avoid using instanceof checks inside visitors to preserve polymorphism.

21. Quiz

22. Next Lesson Preview

In the next lesson, we will explore the Mediator Pattern. We will learn how to reduce chaotic dependencies between classes by forcing them to communicate solely through a central mediator object!