Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Visitor

Add new operations over a stable set of element types without editing them, through accept, visit and double dispatch, and know the price when a new element type arrives.

A grammar that stopped changing

Seven node types, two years, no change. That is the syntax tree of the alert rules a monitoring team writes, rules such as error_rate("search", 5m) > 0.02 and not maintenance("search"). A parser turns each rule into a tree of seven kinds of node, among them number, string, call, comparison, and and not. What has not stopped changing is the list of things people want to do with those trees. There is a formatter that prints rules back in a standard layout, a type checker that rejects comparing a string with a number, and a growing set of lint checks: a call to a deprecated function, a comparison that can never be true, a not not.

The first version put each tool on the nodes. Every node class had format(), typeCheck() and lint(), and the deprecated-function check, which only cares about calls, still meant editing the classes that describe what a rule looks like. Two teams, one writing the formatter and one the linter, were editing the same seven files. The second version moved each tool into a function that asked each node what it was, if (node instanceof Call) … else if (node instanceof Comparison) …, which kept the node classes clean but repeated that chain in every tool, with nothing to say when a branch was missing.

One method per node type, in one object

Visitor puts each operation in its own object and gives every element type one method to let it in. A RuleVisitor interface declares one method per node type: visitCall(call), visitComparison(cmp), visitNot(not) and so on, seven in all. Each tool is a class that implements it: Formatter, TypeChecker, DeprecatedCall. Each node class gains a single method, accept(visitor), whose body is one line: in Call it is visitor.visitCall(this), in Not it is visitor.visitNot(this).

Nodes call back their own visit

The linter hands a check to each node through accept(). Each node calls the visit method for its own type, so the call that arrives depends on both the node and the check.

Why the round trip, instead of the linter calling the right visit method itself? Because the linter holds each node as a plain Node. In Java, C# and C++, the override of a virtual method is chosen by the runtime type of the object it is called on, but which overload of visit to call is decided at compile time, from the declared type. A call like check.visit(node) cannot reach visit(Call) when node is declared as Node. Visitor gets around this with two calls, each dispatched on one object's runtime type:

  1. The linter calls node.accept(check) on a node it knows only as Node.
  2. The node is a Call, so Call.accept runs: the first choice, made by the element's type.
  3. Call.accept calls check.visitCall(this), and the check is a DeprecatedCall, so DeprecatedCall.visitCall runs: the second choice, made by the visitor's type.

This is double dispatch: the code that runs is picked by both the visitor's type and the element's type. A visitor resembles a Strategy handed to the tree, with one difference that matters: a strategy is one algorithm behind one method, while a visitor carries one method per element type.

Cheap operations, expensive node types

The next lint check, rules that mention a service that no longer exists, is one new class implementing RuleVisitor. None of the seven node classes changes, and neither do the other visitors. That is the whole point of the pattern, and it holds in one direction only.

Then the language gains an eighth node type, between, for rules such as latency_p99("search") between 200ms and 800ms. RuleVisitor gains a visitBetween, and the next build fails with a list: Formatter, TypeChecker, DeprecatedCall and every other visitor, each reported as not implementing visitBetween. Every one of them has to decide what between means for it: how to format it, how to type-check it, which lint checks apply. With eleven visitors, one new node type is eleven edits in eleven classes: the bill for having added operations without touching the nodes. Visitor is a poor fit when element types are added often, because every new element type forces a new visit method on every existing visitor.

Watch outIn open/closed terms, the existing classes stay closed to modification when an operation is added, and only then: a new element type modifies every visitor. SOLID design principles covers the principle itself.

Who walks the tree

A rule is a tree, and and has two children, so something has to visit those too. There are three common answers. The elements can do it, with each accept passing the visitor on to its children; every visitor then gets the same order for free and cannot skip a subtree. The visitors can do it, with visitAnd calling accept(this) on each child itself, which gives full control: the formatter decides where parentheses go, the type checker needs the children's types before it can judge the parent. The cost is that every visitor repeats the walk. Or a separate walker or Iterator can hand the nodes to the visitor one by one.

Syntax-tree libraries often ship a base visitor whose default visit methods simply walk the children, so a check overrides only the node types it cares about: DeprecatedCall overrides visitCall, checks the call, then calls the base visitCall so the walk still reaches calls nested in its arguments, and inherits the walk for everything else. Those defaults resemble the hooks of Template Method, defaults a subclass overrides only where it has something to add, with one difference: overriding one replaces its walk unless the override calls the base method. One caution: when between arrives, a check built on such a base keeps compiling only if the base gains a default visitBetween; that default still walks the children, and what is lost is any check specific to between. The tree itself, where a node and a group of nodes share one interface, is Composite.

When the language does the dispatch

Much of Visitor's machinery exists because those languages dispatch on one type at a time. Languages with closed type hierarchies and pattern matching offer another route. Java's sealed interfaces with switch patterns, Kotlin's sealed classes with when and Rust's enums with match let a tool be written as one function that matches on the node type, with no accept methods at all, and the compiler can check that the match covers every node type, as long as it has no catch-all branch. The trade-off stays where it was: a new operation is one new function, and a new node type means updating every match. What changes is the ceremony. Where the language offers this, many teams prefer it; where it does not, Visitor remains the usual way to get both the dispatch and the compiler's help.

Two counts in the Challenge

The Visitor Pattern Challenge allows ten nodes: enough for a visitor interface with a visit per element type, two concrete visitors, an element interface whose accept takes a visitor, and a few element types, with each element's arrow naming the visit method it calls back. Use it to make two counts. Add a third concrete visitor and count the element boxes that change; the answer should be zero. Then add an element type and count the visitor boxes that change; the answer is all of them, and that is the trade you are choosing.

Practice this