Visitor — The Exhaustiveness Check Stands In for It
This chapter looks at how much of Visitor's role the type system takes over.
The problem this pattern set out to solve
GoF catalogs Visitor as a pattern that separates an algorithm from the object structure it works on and moves a family of operations into a single object1.
Consider a structure made of a fixed set of node kinds, such as a syntax tree, where you want to keep adding operations. Written naively, every added operation means adding a method to every node class. Visitor turns that around and lines up "one method per node kind" on the operation's side.
The device that makes this work is routing through accept so the node itself picks the call. Even when a node's static type is the parent class, the method chosen matches its runtime type. This two-step arrangement is needed because method calls in most object-oriented languages can only select a destination by the receiver's runtime type. Selecting on both the operation and the node takes two steps, hence the accept in between.
Writing it straightforwardly with classes
The subject here is evaluating arithmetic expressions.
interface ExprVisitor<R> {
visitLiteral(node: LiteralExpr): R;
visitAdd(node: AddExpr): R;
visitMultiply(node: MultiplyExpr): R;
}
abstract class ExprNode {
abstract accept<R>(visitor: ExprVisitor<R>): R;
}
class LiteralExpr extends ExprNode {
constructor(readonly value: number) {
super();
}
accept<R>(visitor: ExprVisitor<R>): R {
return visitor.visitLiteral(this);
}
}
class AddExpr extends ExprNode {
constructor(
readonly left: ExprNode,
readonly right: ExprNode,
) {
super();
}
accept<R>(visitor: ExprVisitor<R>): R {
return visitor.visitAdd(this);
}
}
class MultiplyExpr extends ExprNode {
constructor(
readonly left: ExprNode,
readonly right: ExprNode,
) {
super();
}
accept<R>(visitor: ExprVisitor<R>): R {
return visitor.visitMultiply(this);
}
}
class Evaluator implements ExprVisitor<number> {
visitLiteral(node: LiteralExpr): number {
return node.value;
}
visitAdd(node: AddExpr): number {
return node.left.accept(this) + node.right.accept(this);
}
visitMultiply(node: MultiplyExpr): number {
return node.left.accept(this) * node.right.accept(this);
}
}
const tree = new AddExpr(new LiteralExpr(2), new MultiplyExpr(new LiteralExpr(3), new LiteralExpr(4)));
const result = tree.accept(new Evaluator());
Adding an operation takes one class implementing ExprVisitor and never touches the nodes. A forgotten case is caught by implements — leave out one method and the class declaration fails to compile. That forced exhaustiveness is Visitor's central value.
The cost is accept. Three node kinds mean three of them, boilerplate that is nearly identical each time.
Replacing it with language features
TypeScript has another tool that forces exhaustiveness.
The
nevertype is assignable to every type; however, no type is assignable tonever(exceptneveritself). This means you can use narrowing and rely onneverturning up to do exhaustive checking in aswitchstatement.2
With it, neither accept nor ExprVisitor has to be written.
type ExprNode =
| {kind: 'literal'; value: number}
| {kind: 'add'; left: ExprNode; right: ExprNode}
| {kind: 'multiply'; left: ExprNode; right: ExprNode};
function evaluateExpr(expr: ExprNode): number {
switch (expr.kind) {
case 'literal':
return expr.value;
case 'add':
return evaluateExpr(expr.left) + evaluateExpr(expr.right);
case 'multiply':
return evaluateExpr(expr.left) * evaluateExpr(expr.right);
default: {
const exhaustive: never = expr;
return exhaustive;
}
}
}
// Adding an operation takes one function. The types stay untouched
function formatExpr(expr: ExprNode): string {
switch (expr.kind) {
case 'literal':
return String(expr.value);
case 'add':
return `(${formatExpr(expr.left)} + ${formatExpr(expr.right)})`;
case 'multiply':
return `(${formatExpr(expr.left)} * ${formatExpr(expr.right)})`;
default: {
const exhaustive: never = expr;
return exhaustive;
}
}
}
const tree: ExprNode = {
kind: 'add',
left: {kind: 'literal', value: 2},
right: {
kind: 'multiply',
left: {kind: 'literal', value: 3},
right: {kind: 'literal', value: 4},
},
};
const result = evaluateExpr(tree);
const text = formatExpr(tree);
The accept boilerplate is gone and the nodes are plain objects. Add one kind and the default clauses in both evaluateExpr and formatExpr fail to compile.
The way the enforcement applies differs, though. implements is applied unconditionally by the type system the moment you declare a Visitor class. Assignment to never applies only where the author wrote a default clause. Add a function without a default later and no protection covers it. Getting the same effect takes a convention that keeps everyone writing it the same way.
What corresponds to the type parameter of ExprVisitor<R> is the return type of the function itself. evaluateExpr returns number and formatExpr returns string, so the type parameter is absorbed into the function signature.
How this series judges it
Verdict: language features can replace it. Once discriminated unions and exhaustiveness checks are both in place, no reason remains to write the accept boilerplate.
This is the same axis as Composite, where the rule was "if operations grow, use a union type." Visitor is a pattern aimed precisely at the situation where operations grow, so the verdict lands on one side.
A run of switch statements is not only shorter than Visitor's classes; the whole operation also reads as a single function. In Visitor the operation is split across methods, so following the whole thing means scrolling up and down inside a class.
What would overturn this judgment
The effort of adding a kind does not shrink in either form. In the union type, adding one node kind produces compile errors in every function that wrote an exhaustiveness check. With Visitor the situation is the same or worse — you add the node class and its accept, then add one method to ExprVisitor<R>, then add an implementation to every Visitor class that implements it. The number of places you touch matches the union type, with the new class and accept piled on top.
In other words, switching to Visitor does not make adding kinds cheaper. If cheap kind additions are what you want, the candidate is not Visitor but the plain polymorphic hierarchy covered in Composite, where the node itself carries the methods. There a new kind costs one class, at the price of every added operation rippling through all the classes.
One more thing: when the traversal itself is complex, its implementation gets duplicated across the functions. In the example above, evaluateExpr and formatExpr each recurse into children, and that duplication starts to bite once requirements arrive such as switching between depth-first and breadth-first, stopping partway, or passing a parent's information down to children.
That can be solved without switching to Visitor. Factor the traversal alone into one function and have it take the per-node operation as an argument, and the duplication collects in one place.
That form has the same structure as the hook injection covered in Template Method.
How this relates to existing articles
- Conditionals covers the basics of discriminated unions and exhaustiveness checks. This chapter shows them taking over Visitor's role and does not repeat the fundamentals.
- Composite shares this chapter's axis of judgment. That chapter covers how to represent a structure; this one covers how to add operations to it.