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
DocDoc · 6ESLintvisit()wordCount(n)DocHeadingHeading ·1IdentifiertotalheadingHeadingParagraphParagraph· 5LiteralaparagraphParagraphImageImage · 0CallExpressionbimageImageWordCountToMarkdownyour rulevisit_NameWordCountDocVisitorinterfaceDocVisitorWordCountWordCountToMarkdownToMarkdownTableTabledoc asks wordCount()2 operations per classHeading todayclass Heading {constructor(public text: string) {}▸wordCount() { return words(this.text); }▸toMarkdown() { return `# ${this.text}`; }}3 classes to editWhere to editHeading+ lint()Paragraph+ lint()Image+ lint()one method per typeone operationOne method per typeinterface DocVisitor<R> {▸heading(n: Heading): R;paragraph(n: Paragraph): R;image(n: Image): R;}interface DocNode {▸accept<R>(v: DocVisitor<R>): R;}h.accept(v)v.heading(this)The node hands overclass Heading implements DocNode {constructor(public text: string) {}accept<R>(v: DocVisitor<R>): R {▸return v.heading(this);}}1 + 5 + 0 = 6The counting visitorconst words = (s: string) =>s.split(/\s+/).filter(Boolean).length;const wordCount: DocVisitor<number> = {heading: (n) => words(n.text),paragraph: (n) => words(n.text),image: () => 0,};new visitornodes unchangedA new visitor+const toMarkdown: DocVisitor<string> = {+heading: (n) => `# ${n.text}`,+paragraph: (n) => n.text,+image: (n) => `![${n.alt}](img.png)`,+};+doc.map((n) => n.accept(toMarkdown));new type: Table+ table(n)The contract growsinterface DocVisitor<R> {heading(n: Heading): R;paragraph(n: Paragraph): R;image(n: Image): R;+table(n: Table): R;}▸// WordCount and ToMarkdown failIdentifier(node)walks the ASTAn ESLint rulecreate(context) {return {Identifier(node) { … },"FunctionExpression:exit"(node) { … },};},prints each namedispatches by classast.NodeVisitorimport astclass Names(ast.NodeVisitor):def visit_Name(self, node):print(node.id)▸self.generic_visit(node)Names().visit(ast.parse("total = a + b"))switch (n.kind)Union + switchfunction wordCount(n: DocNode): number {switch (n.kind) {case "heading": return words(n.text);case "paragraph": return words(n.text);case "image": return 0;▸default: return n satisfies never;}}what grows faster?When not to use ittypes that changeyou edit every visitor1 or 2 operationsa method is enoughsmall treea switch reads betterone operation = one visitorVisitor in one tableproblemeach operation in each classsolutionone visitor per operationacceptcalls the method for its typenew operation0 node classes to editnew typeyou edit every visitor
  • 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 ![diagram](img.png). 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.

You will learn

  • Spot the problem: every new operation makes you edit every node class.
  • Write a visitor with one method per node type and an `accept` on each node.
  • Add a new operation without touching the tree's classes.
  • Recognise the pattern in an ESLint rule and in Python's `ast.NodeVisitor`.
  • Know when a `switch` on `kind` is the better choice.