Visitor: new operations over a tree
- Lesson 27 of 32
- 12 min
- Intermediate
- 12 steps
A document stored as a tree of nodes, and operations that keep coming: count words, export to Markdown, check for mistakes. You will move each operation into a visitor and see what you gain and what you pay.
- Node classes to edit per new operation
- 0
- Visitors to edit per new node type
- 2
- request
- response
Step 1 of 12
Problem
Every operation lives in every class
An editor stores a document as a tree: a Heading («Patterns»), a Paragraph and an Image («diagram»). To count words, Doc asks each node for wordCount() and adds up the answers.
Each class carries its own wordCount() and toMarkdown(). It works, but each operation is spread across every class in the tree: to read how words are counted, you open three files.
Step 2 of 12
Problem
A third operation arrives: lint
Now you want to check the document: warn when a heading is empty or an image has no alt text. One more operation, lint().
You have to open all three classes and add a method to each. The node types barely change, but operations keep coming, and each one makes you touch all of them.
What changed
- lint()
- Heading, Paragraph and Image
Step 3 of 12
Concept
One operation, one object
The idea of Visitor: take each operation out of the nodes and put it in a separate object, the visitor. That object has one method per node type: heading(), paragraph() and image().
The contract is DocVisitor<R>, where R is what the operation returns: a number to count words, a string for Markdown. WordCount implements it. The nodes keep a single method: accept(v).
What changed
- interface DocVisitor<R>
- DocNode.accept(v)
Step 4 of 12
Technique
Two calls pick the method
Doc calls h.accept(v) without knowing what h is. Inside Heading, accept does one thing: v.heading(this). The node knows its own type, so it picks the right method on the visitor.
That is two calls: the first picks which node (the object that receives accept) and the second picks which operation (the visitor that came in). This is called double dispatch.
Step 5 of 12
Solution
WordCount walks the document
wordCount is an object with three functions. Doc passes the same visitor to each node, and each node answers with the method for its type.
Heading returns 1, Paragraph («A visitor separates the operation») returns 5 and Image returns 0. Doc adds 1 + 5 + 0 = 6. All the counting logic is in one place.
Step 6 of 12
Solution
New operation, zero classes touched
You need a Markdown export. With Visitor it is one new object, toMarkdown, with the same three methods. You pass it to accept just like before.
Heading, Paragraph and Image do not change. Out come # Patterns, the paragraph as is and . The lint from step 2 would be a third visitor, just as isolated.
What changed
- toMarkdown
Step 7 of 12
Trade-off
The price: a new node type
Now the document supports tables. Table is born, and DocVisitor needs table(n). Every existing visitor stops compiling until it implements it: WordCount and ToMarkdown, 2 in this example.
Visitor makes new operations cheap and new types expensive. The Java docs warn about this for their own ElementVisitor: it may gain methods as the language adds constructs, and they recommend extending the provided abstract visitors instead of implementing the interface directly.
What changed
- Table
- WordCount and ToMarkdown
Step 8 of 12
Technique
An ESLint rule is a visitor
If you write an ESLint rule, you already use Visitor. create(context) returns an object whose keys are node types or selectors, such as Identifier. ESLint walks the AST and calls that function on every node that matches.
With :exit, as in "FunctionExpression:exit", the call comes while going up the tree instead of down. Babel plugins work the same way: an object with methods per node type, which receive a path holding the node and its parent.
Step 9 of 12
Technique
Walking and dispatching are two things
A common mistake is to think Visitor means «walking a tree». In Python's ast.NodeVisitor, visit(node) dispatches: it looks for visit_<Class>, here visit_Name, and when there is none it uses generic_visit, which walks the children.
If you write your own visit_Name and want to keep going down, you must call self.generic_visit(node). With total = a + b it prints total, a and b. To change nodes instead of reading them there is NodeTransformer.
Step 10 of 12
Technique
In TypeScript, a switch is sometimes enough
Visitor does not require accept methods either. If each node has a kind field ("heading", "paragraph" or "image") and DocNode is the union of the three, a function with switch (n.kind) does the dispatch, like ESLint's object keyed by node type.
The default line is the key: if tomorrow you add Table to DocNode and forget its case, n satisfies never does not compile. You get the same warning as with DocVisitor, with less ceremony.
Step 11 of 12
Trade-off
When Visitor is too much
If node types change often, every new type makes you edit every visitor. If you only have one or two operations, a method on each class is easier to follow. And with a small tree, a switch reads at a glance.
Also, the visitor needs to read each node's data (n.text, n.alt), so the nodes stop hiding their fields. And double dispatch is hard to follow in a debugger the first few times.
Step 12 of 12
Summary
Operations out, types still
When a tree has stable node types and operations that keep coming, move each operation into a visitor with one method per type. Each node only has accept, which calls the method for its type.
A new operation is a new visitor, with no node touched. A new type makes you edit every visitor. If types change often, do not use it.
← → step · R replay · Space pause
You will learn
- Spot the problem: every new operation makes you edit every node class. (covered)
- Write a visitor with one method per node type and an `accept` on each node. (covered)
- Add a new operation without touching the tree's classes. (covered)
- Recognise the pattern in an ESLint rule and in Python's `ast.NodeVisitor`. (covered)
- Know when a `switch` on `kind` is the better choice. (covered)