The Visitor Pattern

22 min read

In object-oriented code the Visitor pattern lets you add a new operation to a fixed set of object types without editing those types — at the cost of a fair amount of double-dispatch ceremony. Rust gives you the same power with far less plumbing, because its enum plus match already is a closed set of shapes with exhaustive, compiler-checked dispatch. This page shows the idiomatic Rust form first, then the OO trait form, and explains exactly when each one earns its keep.

Quick Overview

The Visitor pattern separates an algorithm (what you want to do) from the object structure it runs over (the data). A TypeScript/JavaScript developer usually meets it as a class hierarchy with accept(visitor) methods plus a Visitor interface full of visitCircle, visitRect, … callbacks.

In Rust, the everyday answer is much simpler: model the structure as an enum, and write each operation as a free function that matches on it. The compiler enforces exhaustiveness for you, so “add a new operation” is just “write another function,” and “add a new variant” is “let the compiler list every match you must update.” You only reach for the heavier OO-style trait form when you genuinely need an open set of node types that third parties can extend.

Key takeaway: The classic OO Visitor exists to bolt exhaustive dispatch onto languages that lack it. Rust has exhaustive dispatch built in (match over an enum), so most “visitors” collapse into a plain recursive function.

TypeScript/JavaScript Example

Here is the textbook OO Visitor: a small shape hierarchy where each shape can accept a visitor, and an AreaVisitor computes a running total. This is the “double dispatch” version that the Gang of Four book describes.

1
// The element interface: every shape can accept a visitor.
2
interface Shape {
3
  accept(visitor: ShapeVisitor): void;
4
}
5

6
// The visitor interface: one method per concrete shape type.
7
interface ShapeVisitor {
8
  visitCircle(circle: Circle): void;
9
  visitRect(rect: Rect): void;
10
}
11

12
class Circle implements Shape {
13
  constructor(public radius: number) {}
14
  accept(visitor: ShapeVisitor): void {
15
    visitor.visitCircle(this); // dispatch #2: pick visitCircle
16
  }
17
}
18

19
class Rect implements Shape {
20
  constructor(public width: number, public height: number) {}
21
  accept(visitor: ShapeVisitor): void {
22
    visitor.visitRect(this);
23
  }
24
}
25

26
class AreaVisitor implements ShapeVisitor {
27
  total = 0;
28
  visitCircle(circle: Circle): void {
29
    this.total += Math.PI * circle.radius * circle.radius;
30
  }
31
  visitRect(rect: Rect): void {
32
    this.total += rect.width * rect.height;
33
  }
34
}
35

36
const shapes: Shape[] = [new Circle(1), new Rect(2, 3)];
37
const area = new AreaVisitor();
38
for (const shape of shapes) {
39
  shape.accept(area); // dispatch #1: pick the right `accept`
40
}
41
console.log("total area =", area.total.toFixed(4)); // total area = 9.1416

Run with Node v22 (node demo.mjs), this prints:

1
total area = 9.1416

Key points:

Two interfaces (Shape, ShapeVisitor) and the accept/visit* round-trip are the “double dispatch” that picks the right method based on both the shape’s runtime type and the visitor’s.
Adding a new operation (say, a PerimeterVisitor) is cheap: write one new class, touch nothing else.
Adding a new shape (say, Triangle) is expensive: you must add visitTriangle to the interface and to every existing visitor — and TypeScript will only flag the visitor classes, not the data, as needing updates.

Many TypeScript codebases skip all that and use a discriminated union with a switch instead — which, as we’ll see, is the form that maps directly onto idiomatic Rust:

1
type Expr =
2
  | { kind: "number"; value: number }
3
  | { kind: "add"; left: Expr; right: Expr }
4
  | { kind: "mul"; left: Expr; right: Expr };
5

6
function render(node: Expr): string {
7
  switch (node.kind) {
8
    case "number": return String(node.value);
9
    case "add": return `(${render(node.left)} + ${render(node.right)})`;
10
    case "mul": return `(${render(node.left)} * ${render(node.right)})`;
11
    // Exhaustiveness is OPT-IN: only a `never` default catches a missed case.
12
  }
13
}

Rust Equivalent

The idiomatic Rust form drops both interfaces. The structure is an enum; each operation is a function that matches on it. Here is an arithmetic expression tree with two operations — evaluate and render — written as plain recursive functions.

1
#[derive(Debug, Clone)]
2
enum Expr {
3
    Number(f64),
4
    Add(Box<Expr>, Box<Expr>),
5
    Sub(Box<Expr>, Box<Expr>),
6
    Mul(Box<Expr>, Box<Expr>),
7
    Neg(Box<Expr>),
8
}
9

10
// Operation #1: evaluate the tree to a number.
11
fn eval(expr: &Expr) -> f64 {
12
    match expr {
13
        Expr::Number(n) => *n,
14
        Expr::Add(a, b) => eval(a) + eval(b),
15
        Expr::Sub(a, b) => eval(a) - eval(b),
16
        Expr::Mul(a, b) => eval(a) * eval(b),
17
        Expr::Neg(e) => -eval(e),
18
    }
19
}
20

21
// Operation #2: render the tree as a parenthesized string.
22
fn render(expr: &Expr) -> String {
23
    match expr {
24
        Expr::Number(n) => n.to_string(),
25
        Expr::Add(a, b) => format!("({} + {})", render(a), render(b)),
26
        Expr::Sub(a, b) => format!("({} - {})", render(a), render(b)),
27
        Expr::Mul(a, b) => format!("({} * {})", render(a), render(b)),
28
        Expr::Neg(e) => format!("-{}", render(e)),
29
    }
30
}
31

32
fn main() {
33
    // -(2 + 3) * 4
34
    let expr = Expr::Mul(
35
        Box::new(Expr::Neg(Box::new(Expr::Add(
36
            Box::new(Expr::Number(2.0)),
37
            Box::new(Expr::Number(3.0)),
38
        )))),
39
        Box::new(Expr::Number(4.0)),
40
    );
41

42
    println!("{}", render(&expr));
43
    println!("= {}", eval(&expr));
44
}

Running it prints:

1
(-(2 + 3) * 4)
2
= -20

Key points:

enum Expr { ... } declares the entire closed set of node shapes in one place — the equivalent of the whole Shape hierarchy.
Each operation (eval, render) is a single function. There is no accept, no Visitor interface, no double dispatch — match resolves the variant directly.
The recursive variants hold Box<Expr> because an enum must have a known, finite size; the indirection is covered in Section 10 — Smart Pointers.
Crucially, the compiler requires every arm. Add an Expr::Pow variant and eval/render will refuse to compile until you handle it — the safety the OO version can only approximate with a never trick.

Detailed Explanation

Why `enum` + `match` is the real visitor

The Visitor pattern solves one core problem: dispatch on the concrete type of a node, exhaustively. In Java, C#, and pre-never TypeScript, the language gives you only single dispatch (one virtual/method call per object), so the GoF “double dispatch” dance — node.accept(visitor) then visitor.visitX(node) — is a workaround to recover the second dispatch.

Rust does not need the workaround. A match over an enum is a multi-way dispatch on the variant tag, and the compiler verifies you covered every case:

1
fn eval(expr: &Expr) -> f64 {
2
    match expr {
3
        Expr::Number(n) => *n,          // dispatch happens HERE, in one place
4
        Expr::Add(a, b) => eval(a) + eval(b),
5
        // ...
6
    }
7
}

The variant name is the discriminant — there is no separate kind: "add" string to keep in sync (contrast the TypeScript discriminated union, where you invent and maintain that field by hand). See Section 06 — Enums for the full story on data-carrying variants.

Many real visitors carry state — a running total, a counter, a list of collected nodes. In OO code that state lives on the visitor object. In Rust you pass a &mut accumulator into the function, which is the same idea without the object:

1
#[derive(Default, Debug)]
2
struct Stats {
3
    numbers: usize,
4
    operators: usize,
5
}
6

7
fn collect_stats(expr: &Expr, stats: &mut Stats) {
8
    match expr {
9
        Expr::Number(_) => stats.numbers += 1,
10
        Expr::Neg(e) => {
11
            stats.operators += 1;
12
            collect_stats(e, stats);
13
        }
14
        Expr::Add(a, b) | Expr::Sub(a, b) | Expr::Mul(a, b) => {
15
            stats.operators += 1;
16
            collect_stats(a, stats);
17
            collect_stats(b, stats);
18
        }
19
    }
20
}

Note the or-pattern Expr::Add(a, b) | Expr::Sub(a, b) | Expr::Mul(a, b) — when several variants share a shape and you want identical handling, one arm covers them all while still binding a and b. The &mut Stats borrow means the accumulator is threaded through the whole traversal without cloning, enforced by the borrow checker.

The OO trait form, when you actually need it

The enum form has one limitation: the set of variants is closed. Only the crate that defines Expr can add a variant. If you are writing a library and want downstream crates to plug in their own node types — the “open structure” scenario — you need the trait-object form, which trades exhaustiveness for extensibility.

1
trait Shape {
2
    fn accept(&self, visitor: &mut dyn ShapeVisitor);
3
}
4

5
trait ShapeVisitor {
6
    fn visit_circle(&mut self, circle: &Circle);
7
    fn visit_rect(&mut self, rect: &Rect);
8
}
9

10
struct Circle {
11
    radius: f64,
12
}
13
struct Rect {
14
    width: f64,
15
    height: f64,
16
}
17

18
impl Shape for Circle {
19
    fn accept(&self, visitor: &mut dyn ShapeVisitor) {
20
        visitor.visit_circle(self); // dispatch #2: picks visit_circle
21
    }
22
}
23
impl Shape for Rect {
24
    fn accept(&self, visitor: &mut dyn ShapeVisitor) {
25
        visitor.visit_rect(self);
26
    }
27
}
28

29
struct AreaVisitor {
30
    total: f64,
31
}
32
impl ShapeVisitor for AreaVisitor {
33
    fn visit_circle(&mut self, circle: &Circle) {
34
        self.total += std::f64::consts::PI * circle.radius * circle.radius;
35
    }
36
    fn visit_rect(&mut self, rect: &Rect) {
37
        self.total += rect.width * rect.height;
38
    }
39
}
40

41
// A SECOND visitor, added later, WITHOUT touching Circle / Rect / Shape.
42
struct NameVisitor {
43
    names: Vec<&'static str>,
44
}
45
impl ShapeVisitor for NameVisitor {
46
    fn visit_circle(&mut self, _: &Circle) {
47
        self.names.push("circle");
48
    }
49
    fn visit_rect(&mut self, _: &Rect) {
50
        self.names.push("rect");
51
    }
52
}
53

54
fn main() {
55
    let shapes: Vec<Box<dyn Shape>> = vec![
56
        Box::new(Circle { radius: 1.0 }),
57
        Box::new(Rect { width: 2.0, height: 3.0 }),
58
    ];
59

60
    let mut area = AreaVisitor { total: 0.0 };
61
    let mut names = NameVisitor { names: Vec::new() };
62
    for shape in &shapes {
63
        shape.accept(&mut area);
64
        shape.accept(&mut names);
65
    }
66
    println!("total area = {:.4}", area.total);
67
    println!("names = {:?}", names.names);
68
}

Running it prints:

1
total area = 9.1416
2
names = ["circle", "rect"]

This is the literal translation of the TypeScript version: &dyn ShapeVisitor is the trait object (covered in Section 09 — Trait Objects), accept performs the first dispatch, and the visit_* call performs the second. Box<dyn Shape> lets a heterogeneous Vec hold both shapes. Adding AreaVisitor and NameVisitor requires no change to Circle, Rect, or Shape — the operations are open. But adding a new shape (Triangle) means adding visit_triangle to the trait and to every visitor, exactly as in TypeScript.

The expression problem, made concrete

The two forms sit on opposite sides of the classic expression problem — the tension between adding new types and adding new operations without recompiling existing code:

enum + match: adding an operation is trivial (a new function); adding a variant forces edits to every match — but the compiler hands you the exact list. Easy to add operations, “compiler-guided” to add variants.
trait objects: adding a type is trivial (a new impl); adding an operation forces a new method on the visitor trait and every impl. Easy to add types, painful to add operations.

For a tree you own — an AST, a config document, a JSON value — the enum form wins almost every time. Reach for the trait form only when the set of node types must stay open to other crates.

Key Differences

Aspect	TypeScript OO Visitor	Rust `enum` + `match`	Rust trait-object Visitor
Structure definition	Class hierarchy + `Shape` interface	One `enum`	One trait + many `impl`s
Dispatch mechanism	Double dispatch (`accept` → `visit*`)	Single `match` on the variant tag	Double dispatch (`accept` → `visit*`)
Exhaustiveness	Opt-in (`never` trick)	Compiler-enforced (`E0004`)	Not checked (open set)
Add a new operation	New visitor class (cheap)	New function (cheap)	New trait method + every impl (costly)
Add a new node type	New `visit*` on every visitor (costly)	New variant; compiler lists every `match` to fix	New struct + `impl` (cheap)
Node set	Open (subclasses)	Closed (one crate owns it)	Open (any crate can `impl`)
Runtime cost	Virtual calls + allocation	Tag check; no vtable, no heap	Vtable indirection + `Box` allocation
Boilerplate	High (two interfaces, round-trip)	Minimal (just the function)	Moderate (`accept` + `visit*` plumbing)

Note: “Double dispatch” is not a Rust idiom you should reach for by default. It is a technique to recover exhaustive multi-type dispatch in languages that only have single dispatch. Rust’s match already gives you that, so the accept/visit* round-trip is pure overhead unless you specifically need the open node set.

The deepest difference is who is forced to react to change. In the OO world, a forgotten case is a silent runtime fall-through. In the enum world, a forgotten case is a compile error that names the missing variant — the safety property that makes refactoring large match-heavy codebases tractable.

Common Pitfalls

Pitfall 1: a wildcard arm silently swallows new variants

The single biggest mistake when porting a switch to Rust is reaching for _ => to “handle the rest.” It compiles, but it also defeats the exhaustiveness check: when someone later adds a variant, your match keeps compiling and quietly mishandles it.

1
#[derive(Debug)]
2
enum Event {
3
    Click { x: i64, y: i64 },
4
    KeyPress(char),
5
    Scroll(i64),
6
    Paste(String), // added later
7
}
8

9
fn describe(event: &Event) -> String {
10
    match event {
11
        Event::Click { x, y } => format!("click at ({x}, {y})"),
12
        Event::KeyPress(c) => format!("key '{c}'"),
13
        _ => "other".to_string(), // silently swallows Scroll AND Paste
14
    }
15
}

This compiles and runs — Scroll and Paste both print "other", almost certainly a bug. Clippy can catch it; running cargo clippy -- -W clippy::wildcard_enum_match_arm reports the real warning:

1
warning: wildcard match will also match any future added variants
2
  --> src/main.rs:17:9
3
   |
4
17 |         _ => "other".to_string(), // silently swallows Scroll AND Paste
5
   |         ^ help: try: `Event::Scroll(_) | Event::Paste(_)`
6
   |
7
   = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#wildcard_enum_match_arm

Fix: spell out the remaining variants (or an or-pattern) instead of _, so the next person who adds a variant gets a compile error pointing right at this match.

Pitfall 2: trusting that an added variant “just works”

Conversely, if you do write every arm explicitly, the compiler protects you. Add Expr::Mul and forget to handle it in eval, and the build fails with a precise message:

1
enum Expr {
2
    Number(f64),
3
    Add(Box<Expr>, Box<Expr>),
4
    Mul(Box<Expr>, Box<Expr>), // newly added variant
5
}
6

7
fn eval(expr: &Expr) -> f64 {
8
    match expr {
9
        Expr::Number(n) => *n,
10
        Expr::Add(a, b) => eval(a) + eval(b),
11
        // forgot Expr::Mul
12
    }
13
}

The real error from cargo build:

1
error[E0004]: non-exhaustive patterns: `&Expr::Mul(_, _)` not covered
2
 --> src/main.rs:8:11
3
  |
4
8 |     match expr {
5
  |           ^^^^ pattern `&Expr::Mul(_, _)` not covered
6
  |
7
note: `Expr` defined here
8
 --> src/main.rs:1:6
9
  |
10
1 | enum Expr {
11
  |      ^^^^
12
...
13
4 |     Mul(Box<Expr>, Box<Expr>), // newly added variant
14
  |     --- not covered
15
  = note: the matched value is of type `&Expr`

This E0004 is the feature, not the obstacle: it is the compiler doing the bookkeeping the OO Visitor pattern was invented to force on you. Embrace it — and resist the urge to silence it with _.

Pitfall 3: over-engineering with a `Visitor` trait when a function would do

Coming from an OO background, it is tempting to build a full trait ExprVisitor { fn visit_number(...); fn visit_add(...); ... } for a tree you fully own. That recreates all the boilerplate the enum form eliminated, and you give up nothing in return because the node set is closed anyway. Start with a free function over the enum; only introduce a visitor trait if you find yourself with many operations that share a fixed traversal order and want to factor the walk out (see Exercise 2).

Pitfall 4: forgetting the box on recursive variants

A self-referential enum has no finite size, so a naive Add(Expr, Expr) is rejected. The fix is indirection — Box<Expr>. The error is E0072 (“recursive type has infinite size”); the compiler even suggests inserting Box. This is a property of value-typed enums, unlike TypeScript objects which are always behind a reference.

Best Practices

Default to enum + match. For any tree or node set you own (ASTs, documents, protocol messages, state machines), the recursive-function form is the idiomatic, zero-overhead visitor.
Write every arm; avoid _ for enums you control. Spell out variants so adding one becomes a guided compile error rather than a silent fall-through. Turn on clippy::wildcard_enum_match_arm in code where this matters.
Thread mutable state through a &mut accumulator. It is the direct analog of visitor instance fields, without an object.
Use or-patterns (A(x) | B(x) | C(x)) to share one arm across structurally similar variants.
Reach for the trait-object form only for an open node set — when third-party crates must add node types. Accept that you then lose exhaustiveness and that new operations become expensive.
Consider a default-method visitor trait when you have many operations that all need the same recursive traversal: put the walk in a provided method and let each visitor override only the per-node hook (Exercise 2).
Return new trees for transformations. A “transforming visitor” (constant folding, desugaring, optimization) is just a function fn(&Expr) -> Expr that pattern-matches and rebuilds — no mutation, no visitor object (Exercise 3).

Real-World Example

A production-flavored use: walking a JSON document with two independent passes — one that gathers statistics, one that collects every string leaf in document order — plus a compact serializer. This is exactly the shape of work a linter, a config validator, or a redaction tool does, and it shows multiple “visitors” over one owned enum.

1
use std::collections::BTreeMap;
2

3
#[derive(Debug, Clone)]
4
enum Json {
5
    Null,
6
    Bool(bool),
7
    Number(f64),
8
    Str(String),
9
    Array(Vec<Json>),
10
    Object(BTreeMap<String, Json>),
11
}
12

13
// Operation: serialize to compact JSON (reads every payload).
14
fn to_compact(value: &Json) -> String {
15
    match value {
16
        Json::Null => "null".to_string(),
17
        Json::Bool(b) => b.to_string(),
18
        Json::Number(n) => n.to_string(),
19
        Json::Str(s) => format!("\"{s}\""),
20
        Json::Array(items) => {
21
            let inner: Vec<String> = items.iter().map(to_compact).collect();
22
            format!("[{}]", inner.join(","))
23
        }
24
        Json::Object(map) => {
25
            let inner: Vec<String> = map
26
                .iter()
27
                .map(|(k, v)| format!("\"{k}\":{}", to_compact(v)))
28
                .collect();
29
            format!("{{{}}}", inner.join(","))
30
        }
31
    }
32
}
33

34
// Operation: count nodes by kind, accumulating into shared state.
35
#[derive(Default, Debug)]
36
struct Stats {
37
    nulls: usize,
38
    bools: usize,
39
    numbers: usize,
40
    strings: usize,
41
    arrays: usize,
42
    objects: usize,
43
}
44

45
fn collect_stats(value: &Json, stats: &mut Stats) {
46
    match value {
47
        Json::Null => stats.nulls += 1,
48
        Json::Bool(_) => stats.bools += 1,
49
        Json::Number(_) => stats.numbers += 1,
50
        Json::Str(_) => stats.strings += 1,
51
        Json::Array(items) => {
52
            stats.arrays += 1;
53
            for item in items {
54
                collect_stats(item, stats);
55
            }
56
        }
57
        Json::Object(map) => {
58
            stats.objects += 1;
59
            for child in map.values() {
60
                collect_stats(child, stats);
61
            }
62
        }
63
    }
64
}
65

66
// Operation: gather every string leaf, in document order, borrowing in place.
67
fn collect_strings<'a>(value: &'a Json, out: &mut Vec<&'a str>) {
68
    match value {
69
        Json::Str(s) => out.push(s),
70
        Json::Array(items) => items.iter().for_each(|v| collect_strings(v, out)),
71
        Json::Object(map) => map.values().for_each(|v| collect_strings(v, out)),
72
        _ => {} // leaf kinds with no strings: deliberately ignored
73
    }
74
}
75

76
fn main() {
77
    let doc = Json::Object(BTreeMap::from([
78
        ("name".into(), Json::Str("Ada".into())),
79
        ("active".into(), Json::Bool(true)),
80
        (
81
            "tags".into(),
82
            Json::Array(vec![Json::Str("a".into()), Json::Str("b".into())]),
83
        ),
84
        ("score".into(), Json::Number(9.5)),
85
        ("note".into(), Json::Null),
86
    ]));
87

88
    println!("{}", to_compact(&doc));
89

90
    let mut stats = Stats::default();
91
    collect_stats(&doc, &mut stats);
92
    println!("{stats:?}");
93

94
    let mut strings = Vec::new();
95
    collect_strings(&doc, &mut strings);
96
    println!("strings = {strings:?}");
97
}

Running it prints (the BTreeMap keeps keys sorted, so output is deterministic):

1
{"active":true,"name":"Ada","note":null,"score":9.5,"tags":["a","b"]}
2
Stats { nulls: 1, bools: 1, numbers: 1, strings: 3, arrays: 1, objects: 1 }
3
strings = ["Ada", "a", "b"]

Three operations, one data type, zero accept/visit* ceremony. Note collect_strings borrows the strings (&'a str) instead of cloning them — the lifetime 'a ties the borrowed slices to the document, so the visitor allocates nothing for the strings it gathers. (The deliberate _ => {} here is safe because the ignored kinds genuinely have no strings; if Json ever gained a string-bearing variant, you’d want to switch to explicit arms per Pitfall 1.)

Tip: This is precisely how the serde_json::Value enum and many real parsers are consumed: an owned enum, traversed by ordinary functions. Production crates layer the same idea — syn’s Visit/VisitMut traits, for instance, are a default-method visitor over Rust’s own AST enums, used by procedural macros (see Section 23 — The Ecosystem).

Exercises

Exercise 1: Extend the expression tree

Difficulty: Beginner

Objective: Experience the compiler-guided workflow for adding a variant.

Instructions: Starting from the Expr enum with Number, Add, and Mul, add a Pow(Box<Expr>, Box<Expr>) variant (exponentiation). Extend both eval (using f64::powf) and render (rendering a ^ b). Build after adding the variant before updating the functions, and observe which E0004 errors the compiler reports.

Solution

1
#[derive(Debug, Clone)]
2
enum Expr {
3
    Number(f64),
4
    Add(Box<Expr>, Box<Expr>),
5
    Mul(Box<Expr>, Box<Expr>),
6
    Pow(Box<Expr>, Box<Expr>),
7
}
8

9
fn eval(expr: &Expr) -> f64 {
10
    match expr {
11
        Expr::Number(n) => *n,
12
        Expr::Add(a, b) => eval(a) + eval(b),
13
        Expr::Mul(a, b) => eval(a) * eval(b),
14
        Expr::Pow(base, exp) => eval(base).powf(eval(exp)),
15
    }
16
}
17

18
fn render(expr: &Expr) -> String {
19
    match expr {
20
        Expr::Number(n) => n.to_string(),
21
        Expr::Add(a, b) => format!("({} + {})", render(a), render(b)),
22
        Expr::Mul(a, b) => format!("({} * {})", render(a), render(b)),
23
        Expr::Pow(base, exp) => format!("({} ^ {})", render(base), render(exp)),
24
    }
25
}
26

27
fn main() {
28
    // (2 + 3) ^ 2
29
    let expr = Expr::Pow(
30
        Box::new(Expr::Add(
31
            Box::new(Expr::Number(2.0)),
32
            Box::new(Expr::Number(3.0)),
33
        )),
34
        Box::new(Expr::Number(2.0)),
35
    );
36
    println!("{} = {}", render(&expr), eval(&expr)); // ((2 + 3) ^ 2) = 25
37
}

Running it prints:

1
((2 + 3) ^ 2) = 25

Exercise 2: A default-method visitor trait

Difficulty: Intermediate

Objective: Factor a shared traversal into a trait so multiple operations reuse it, while still matching on an owned enum.

Instructions: Define a trait ExprVisitor with a provided visit(&mut self, expr: &Expr) method that recursively walks children and then calls a required on_node(&mut self, expr: &Expr) hook. Implement a NodeCounter that counts how many nodes the tree has by overriding only on_node. (Use the Expr from Exercise 1.)

Solution

1
#[derive(Debug, Clone)]
2
enum Expr {
3
    Number(f64),
4
    Add(Box<Expr>, Box<Expr>),
5
    Mul(Box<Expr>, Box<Expr>),
6
    Pow(Box<Expr>, Box<Expr>),
7
}
8

9
trait ExprVisitor {
10
    // Provided method: the shared post-order walk.
11
    fn visit(&mut self, expr: &Expr) {
12
        match expr {
13
            Expr::Number(_) => {}
14
            Expr::Add(a, b) | Expr::Mul(a, b) | Expr::Pow(a, b) => {
15
                self.visit(a);
16
                self.visit(b);
17
            }
18
        }
19
        self.on_node(expr);
20
    }
21
    // Required hook: what each concrete visitor does per node.
22
    fn on_node(&mut self, expr: &Expr);
23
}
24

25
struct NodeCounter {
26
    count: usize,
27
}
28
impl ExprVisitor for NodeCounter {
29
    fn on_node(&mut self, _expr: &Expr) {
30
        self.count += 1;
31
    }
32
}
33

34
fn main() {
35
    // (2 + 3) ^ 2  -> nodes: Number(2), Number(3), Add, Number(2), Pow = 5
36
    let expr = Expr::Pow(
37
        Box::new(Expr::Add(
38
            Box::new(Expr::Number(2.0)),
39
            Box::new(Expr::Number(3.0)),
40
        )),
41
        Box::new(Expr::Number(2.0)),
42
    );
43

44
    let mut counter = NodeCounter { count: 0 };
45
    counter.visit(&expr);
46
    println!("nodes = {}", counter.count); // nodes = 5
47
}

Running it prints:

1
nodes = 5

The provided visit method centralizes the walk; each visitor overrides only on_node. This is the pattern syn’s Visit trait uses — worth it only when several operations share one traversal.

Exercise 3: A transforming visitor (constant folding)

Difficulty: Advanced

Objective: Write a visitor that produces a new tree, the way a compiler optimization pass does.

Instructions: Write fn fold_consts(expr: &Expr) -> Expr that recursively simplifies any subtree of literal numbers into a single Number. For example, (2 + 3) * x should fold the 2 + 3 into 5, leaving 5 * x (model x as a Number for the demo). Operations on non-literal subtrees must be rebuilt unchanged.

Solution

1
#[derive(Debug, Clone)]
2
enum Expr {
3
    Number(f64),
4
    Add(Box<Expr>, Box<Expr>),
5
    Mul(Box<Expr>, Box<Expr>),
6
    Pow(Box<Expr>, Box<Expr>),
7
}
8

9
fn render(expr: &Expr) -> String {
10
    match expr {
11
        Expr::Number(n) => n.to_string(),
12
        Expr::Add(a, b) => format!("({} + {})", render(a), render(b)),
13
        Expr::Mul(a, b) => format!("({} * {})", render(a), render(b)),
14
        Expr::Pow(a, b) => format!("({} ^ {})", render(a), render(b)),
15
    }
16
}
17

18
fn fold_consts(expr: &Expr) -> Expr {
19
    match expr {
20
        Expr::Number(n) => Expr::Number(*n),
21
        Expr::Add(a, b) => match (fold_consts(a), fold_consts(b)) {
22
            (Expr::Number(x), Expr::Number(y)) => Expr::Number(x + y),
23
            (l, r) => Expr::Add(Box::new(l), Box::new(r)),
24
        },
25
        Expr::Mul(a, b) => match (fold_consts(a), fold_consts(b)) {
26
            (Expr::Number(x), Expr::Number(y)) => Expr::Number(x * y),
27
            (l, r) => Expr::Mul(Box::new(l), Box::new(r)),
28
        },
29
        Expr::Pow(a, b) => match (fold_consts(a), fold_consts(b)) {
30
            (Expr::Number(x), Expr::Number(y)) => Expr::Number(x.powf(y)),
31
            (l, r) => Expr::Pow(Box::new(l), Box::new(r)),
32
        },
33
    }
34
}
35

36
fn main() {
37
    // (2 + 3) * 10  (10 stands in for a variable that can't be folded away)
38
    let expr = Expr::Mul(
39
        Box::new(Expr::Add(
40
            Box::new(Expr::Number(2.0)),
41
            Box::new(Expr::Number(3.0)),
42
        )),
43
        Box::new(Expr::Number(10.0)),
44
    );
45

46
    println!("before = {}", render(&expr));        // ((2 + 3) * 10)
47
    let folded = fold_consts(&expr);
48
    println!("after  = {}", render(&folded));       // (5 * 10) -> further folds to 50
49
}

Running it prints:

1
before = ((2 + 3) * 10)
2
after  = 50

Because 10 is itself a literal here, the whole tree folds to Number(50). If 10 were a non-literal node (a variable), only the 2 + 3 would fold, leaving (5 * x) — the rebuild-unchanged branch handles that case.

The Visitor Pattern

Quick Overview

TypeScript/JavaScript Example

Rust Equivalent

Detailed Explanation

Why enum + match is the real visitor

Multiple operations sharing accumulator state

The OO trait form, when you actually need it

The expression problem, made concrete

Key Differences

Common Pitfalls

Pitfall 1: a wildcard arm silently swallows new variants

Pitfall 2: trusting that an added variant “just works”

Pitfall 3: over-engineering with a Visitor trait when a function would do

Pitfall 4: forgetting the box on recursive variants

Best Practices

Real-World Example

Further Reading

Exercises

Exercise 1: Extend the expression tree

Exercise 2: A default-method visitor trait

Exercise 3: A transforming visitor (constant folding)

Why `enum` + `match` is the real visitor

Pitfall 3: over-engineering with a `Visitor` trait when a function would do