Composite and Visitor Visualization | File Tree, Double Dispatch

The idea: treat a tree uniformly, add operations outside it

Many things are trees: folders and files, the HTML DOM, a compiler's syntax tree, a GUI window with panels and buttons. The Composite pattern (Gamma, Helm, Johnson and Vlissides, 1994) gives the leaves and the containers one interface, so code can call the same method on a single file or on a whole folder. The Visitor pattern lets you add new operations over such a tree without editing the node classes.

Class diagram. Left: interface Node with size() and accept(Visitor v); File and Folder implement it; Folder holds a list of 0 or more Nodes. Right: interface Visitor with visitFile and visitFolder; SizeVisitor, CountVisitor and FindVisitor implement it. — File and Folder share the Node interface; each operation written as a visitor is one more class on the right.

The canvas holds one tree: root/ with 6 files in 4 folders, 273 KB in all. On the left, each row is one object; grey boxes are Folders, white boxes are Files. Calls fly as blue boxes in the lane on the right of the rows, and answers fly back in green. The call stack shows which calls are open, and the code panels light the line that runs.

Composite: one call, the whole tree

A leaf (File) answers size() with its own size. A composite (Folder) does not know any sizes. It starts with s = 0, calls size() on each child and adds the answers. Because a child may be another Folder, the call recurses until it reaches files, and the sums come back up: lib/ returns 45, src/ returns 30 + 10 + 45 = 85, root/ returns 124 + 85 + 64 = 273 KB (Demo 1).

The client never asks "is this a file or a folder?". The same call works on src/ (85 KB, a small recursion) and on main.js (30 KB, no recursion at all) (Demo 2). The call stack is never deeper than the tree: at most 4 frames here. See recursion and the call stack for the same mechanism in general.

Visitor: double dispatch

Suppose you also want to count files, find all .js files and export the tree as JSON. Adding a method to Node for each one fills File and Folder with unrelated code. A visitor puts one operation in one class instead. Each node has a single extra method, accept(Visitor v), and the visitor has one method per node class: visitFile and visitFolder.

Sequence diagram: the client calls src.accept(v); the Folder calls v.visitFolder(this), then main.js.accept(v); the File calls v.visitFile(this), and the SizeVisitor adds 30 to total. — accept() picks the node's class, visitFile or visitFolder picks the visitor's class: two dispatches in a row.

node.accept(v) runs the method of the node's real class: File.accept calls v.visitFile(this), Folder.accept calls v.visitFolder(this). That call then runs the method of the visitor's real class. Two virtual calls pick the code from two classes, which is called double dispatch. Java, C# and C++ choose a method by one object's class only, so the visitor needs this trick. Here the Folder also passes v on to its children, so the tree does the walking and the visitor only collects.

SizeVisitor adds each file's KB and does nothing for folders: total = 273 KB, the same as size() (Demo 3).
CountVisitor does something different in each method: 6 files, 4 folders (Demo 4).
FindVisitor keeps src/main.js, src/util.js and src/lib/parse.js, in tree order (Demo 5).

None of the three needed a change to File or Folder. Adding files does not need one either: after Add File three times (test.js, todo.txt, fmt.js) the same SizeVisitor reports 289 KB (Demo 6).

Adding operations vs adding node classes

The visitor makes one kind of change cheap and the other expensive. A new operation is one new class. A new node class, for example Symlink, needs a visitSymlink method in the Visitor interface and in every visitor that exists.

Two by two grid. Methods on the nodes: adding an operation edits File and Folder (red), adding a node class is one new class (green). Visitor: adding an operation is one new visitor class (green), adding a node class edits every visitor (red). — Choose by what changes more often: the operations or the node classes.

	methods on the nodes	Visitor
Add an operation	edit every node class	add one visitor class
Add a node class	add one class	edit every visitor
Code of one operation	spread over the node classes	in one class
Access to private node fields	yes	only through public getters

Compilers are the classic fit: the syntax tree's node classes rarely change, but passes keep being added (type checking, constant folding, code generation). See the compiler pipeline. For a simpler choice between objects behind one interface, see Strategy and Factory Method; a macro in the Command pattern is itself a composite of commands.

Where they show up

The DOM. Elements contain elements and text nodes behind one Node type; textContent walks the subtree like size() (see Virtual DOM diffing).
Syntax trees. Java's javax.lang.model and the TypeScript and Babel compilers walk trees with visitors.
File systems. Java's Files.walkFileTree(path, FileVisitor) calls visitFile and preVisitDirectory for you.
Pattern matching. Languages with sealed types and switch on type (Java 21, Kotlin, Rust, Scala) can replace a visitor with one switch per operation; the compiler checks every node class is handled.

What the page leaves out

Real file systems also have links and cycles, so a walker must track what it has seen. The tree here is walked depth first, in preorder; visitors can also walk after the children (postorder) or let the visitor decide the order. Composite has design choices the page skips: whether add() and remove() belong on Node or only on Folder, parent pointers, and caching a folder's size. Visitors that return values (Visitor<R>) and acyclic visitors are left out too.