Folding an AST: separating traversal from action

Parse a small expression language into a recursive enum, then run four different analyses over the same tree with one traversal skeleton.

pub fn analyse(src: String, ops: Vec<String>) -> Vec<String>

This is the item where the pieces stop being separate topics and become an architecture. Recursive enums, exhaustive match, Box for indirection, ownership of subtrees, and higher-order functions all serve one realistic task. Compilers, linters, serialisers, query planners, template engines and every “walk this document and do something” library you will ever write are this exact shape.

The language

expr := term (('+' | '-') term)*, term := factor ('*' factor)*, factor := INT | IDENT | '(' expr ')'. Integers are i64, identifiers are the usual [A-Za-z_][A-Za-z0-9_]*. The tokenizer and the recursive-descent parser are given to you — parsing is not the lesson.

The four analyses

ops names them, in order, and each contributes one output line.

free with no variables emits free -. An op you do not recognise emits unknown <op>. If the source does not parse, the whole result is the single line parse error.

Constant folding is bottom-up: a binary node whose children are both literals collapses to a literal. If the arithmetic would overflow, leave the node alone — this harness compiles with -O, so overflow checks are off and a + b would silently wrap. checked_add and friends are how you notice.

The starter does not compile, on purpose

pub enum Expr {
    Lit(i64),
    Var(String),
    Bin(Op, Expr, Expr),
}

::: question What is wrong with that, in one sentence? E0072: recursive type Expr has infinite size.

Expr is a value, not a pointer. To lay it out, rustc must know how many bytes it takes; the Bin variant contains two Exprs, so its size is 2 * size_of::<Expr>() + tag, which has no finite solution. The error message spells out the fix: insert some indirection (e.g., a Box, Rc, or &) to break the cycle. Box<Expr> makes the child a pointer of known size and moves the node itself to the heap.

This is not a Rust quirk. Every language with algebraic data types has the same constraint; most hide it by making all values pointers. Rust makes you say where the indirection is, which is also why Box<Expr> in a signature tells a reader “this owns a heap-allocated subtree”. :::

Borrow the tree, do not eat it

The single most consequential design decision in this item is whether your traversal takes &Expr or Expr.

A fold over Expr consumes the tree. It can move Strings out of Var nodes without cloning, which is efficient — and it can run exactly once. The second analysis has nothing left to look at. Worse, moving out of a Box inside a match on an owned enum is where you meet E0507 in its most irritating form.

A fold over &Expr borrows. It can run four times over the same tree, each Box<Expr> deref-coerces to &Expr for free, and nothing is moved anywhere. It costs a to_string() in the two folds that actually need owned names. That is the right trade here, and it is the right trade in most real compilers, which is why rustc‘s own visitors take &.

Choose the borrowing form before you write the first line. Discovering halfway through analysis three that analysis one ate the tree is a rewrite, not a fix.

The skeleton

The starter gives you the shape:

fn fold<T, L, V, B>(e: &Expr, lit: &L, var: &V, bin: &B) -> T
where
    L: Fn(i64) -> T,
    V: Fn(&str) -> T,
    B: Fn(Op, T, T) -> T,

One match, three arms, and the Bin arm recurses into both children before handing their results to bin. That is a catamorphism: the recursion happens once, in one place, and each analysis supplies only the three “what to do at this node” pieces. count becomes 1 + l + r; depth becomes 1 + l.max(r); free concatenates two Vec<String>s; fold builds a new Expr.

The closures are taken by reference (&L, not L) so the recursive calls can pass them along without moving them. Try it with by-value parameters once and read the resulting E0382 — it is a good five minutes.

The other idiomatic spelling, and what it costs

The alternative is a trait with a default-implemented walk:

trait Visit {
    fn lit(&mut self, n: i64);
    fn var(&mut self, name: &str);
    fn walk(&mut self, e: &Expr) { /* default recursion */ }
}

It is more extensible: a new visitor is a new type, and a visitor can override walk to prune subtrees. It reads better when the action needs to accumulate into a struct with several fields.

It also has a real cost, and it is the exhaustiveness trade-off in its most consequential form. Add a variant to Expr and the closure-fold breaks at compile time in every one of its match arms — you are told, everywhere, what needs updating. Add a variant to Expr with a default walk, and every existing visitor silently gets the default behaviour for the new node. It compiles. It runs. It quietly produces wrong answers. Neither design is better; know which failure mode you have chosen.

Two smaller things worth having met

only_used_in_recursion. Clippy denies, by default, a parameter that a recursive function passes along but never reads. It is very easy to hit here: a first attempt at depth often threads a level: usize down the recursion and then computes the answer from the return value instead, leaving level write-only. The lint is telling you the parameter is not carrying anything.

Recursion depth. Every one of these folds recurses as deep as the tree, and a deep enough expression overflows the stack — that is a crash, not an error you can catch. The inputs here are bounded. Production parsers either bound the nesting depth explicitly or convert the traversal to an explicit worklist (Vec<&Expr> as a stack) so the depth lives on the heap. It is worth knowing that the second option exists before you need it at three in the morning.