The Visitor Pattern for Heterogeneous ASTs

In this lesson, you will learn how to traverse complex tree structures safely by decoupling your operations from your data types using the Visitor Pattern.

The Challenge of Heterogeneity

When building an Abstract Syntax Tree (AST), your nodes often represent different concepts: Literal(i32), BinaryOp(Box<Node>, Box<Node>), or UnaryOp(Box<Node>). If you want to perform operations—like evaluating an expression or printing the tree—you typically face a dilemma: either add methods to every node type (polluting the data structures) or use giant match statements that are fragile and hard to extend.

The Visitor Solution

The Visitor Pattern solves this by defining a Visitor trait that contains a method for every node type in your AST. Instead of the nodes "knowing" how to be evaluated, they accept a visitor and "dispatch" themselves to the corresponding visitor method.

trait Visitor {
    fn visit_literal(&mut self, val: &i32);
    fn visit_binary_op(&mut self, left: &Node, right: &Node);
}

enum Node {
    Literal(i32),
    BinaryOp(Box<Node>, Box<Node>),
}

impl Node {
    fn accept(&self, visitor: &mut impl Visitor) {
        match self {
            Node::Literal(v) => visitor.visit_literal(v),
            Node::BinaryOp(l, r) => visitor.visit_binary_op(l, r),
        }
    }
}

Traversing Safely

By using this pattern, you maintain strict type boundaries. Your Visitor implementation doesn't need to know the internal structure of the nodes; it only needs to implement the logic for specific node types. If you add a new operation (like TypeChecker or Optimizer), you simply create a new struct that implements the Visitor trait. The AST nodes remain unchanged, following the Open/Closed Principle while ensuring that every node type is explicitly handled by the compiler.

When your tree is recursive, the visitor implementation handles the recursion by calling accept on child nodes, effectively walking the entire structure while keeping the logic neatly contained within your visitor structs rather than scattering it throughout your data models.

Key Takeaway: The Visitor Pattern enables you to extend your AST's functionality without modifying your node structures, ensuring that every traversal operation remains type-safe and decoupled from the underlying data.