ASTspec

Changing the Tree

Two things a pass can do to an AST: annotate it, or rewrite it. Annotation is cheap and reversible; rewriting has a legality condition and destroys what was there. Whether the rewrite happens in place or produces a new tree decides whether the frontend can ever serve an editor.

The question

When a pass changes the AST, does it mutate the tree or build a new one — and why does anyone care?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

Before: a tree plus whatever side tables earlier passes filled in. After an *annotating* pass: the same tree, same shape, with more known about it — this is what [[annotated-ast]] describes. After a *rewriting* pass: a different tree that must denote the same program. The representation question is whether the two trees can coexist, because if they can, a second reader can hold the old one while the new one is built.

What this phase may assume or do

A rewrite is legal only if the replacement subtree has the same observable behavior as the original under the language's semantics — same values, same side effects, in the same order, the same number of times, with the same traps and the same exceptions. Two conditions are violated far more often than the rest: duplicating a subtree duplicates its side effects (so any operand that may have effects must be bound to a temporary first), and moving a subtree past another changes evaluation order (legal only where the language leaves that order unspecified, which is a property of the language and not of the compiler). An annotation, by contrast, has no legality condition at all — it adds knowledge and changes nothing — which is why annotating passes are the ones you can run in any order.

Key points

Annotating adds knowledge and has no legality condition; rewriting replaces subtrees and always has one.
The dominant rewriting bug is duplicating a subtree that has side effects — bind operands to fresh temporaries first.
Short-circuit and argument evaluation order are language-specified in some languages and unspecified in others; a rewrite that reorders them is legal in exactly one of those worlds.
In-place mutation is cheap and forecloses versioning, sharing, undo and concurrent readers.
A persistent rewrite copies only the path from the changed node to the root; everything else is shared by reference.
Immutable trees are what make incremental reparse, refactoring preview and multi-threaded language servers possible.
A batch compiler that runs once gains nothing from immutability and is right to mutate.

Annotate, or rewrite

It is worth being strict about the distinction, because the two are casually described with the same words and have almost nothing in common. An annotating pass computes facts and records them: this identifier resolves to that declaration, this expression has type int, this call cannot throw. The tree afterwards has the same nodes in the same places. Nothing has been lost, no legality question arises, and the pass can be re-run or skipped without changing what the program means.

A rewriting pass replaces subtrees. 1 + 2 becomes 3; for (const x of xs) becomes an iterator loop; a?.b becomes a conditional. Something that was in the tree is now not, and every consumer downstream sees only the result. The original is recoverable only from spans and only as text.

The practical rule that follows: do annotation on the AST, and do rewriting as late as you can bear. Every rewrite on the surface tree is a rewrite that a diagnostic, a formatter or a refactoring will later have to undo, and the tooling almost always loses that fight. This is why rustc lowers AST to HIR rather than rewriting the AST, and why [[desugaring]] is a separate phase rather than something the parser does quietly.

The two kinds of pass, and what each one costs you latertypical

	Annotating pass	Rewriting pass
Changes the tree shape	No	Yes
Has a legality condition	No — adds knowledge only	Yes — must preserve observable behavior
Order-dependent	Only on its inputs	On everything: a later pass sees a different program
Recoverable	Discard the side table	Only from the source text, via spans
Safe to run twice	Yes	Frequently not — folding twice is fine, desugaring twice is not
Examples	Name resolution, type checking, effect inference, reachability	Constant folding, desugaring, macro expansion, lowering

The legality condition, with the bug it prevents

specShort-circuit evaluation of ??, && and || is specified behavior in C, C++, Java, JavaScript, Rust and most other languages that have them — a compiler is *required* to not evaluate the second operand when the first decides the result, so hoisting it is a spec violation and not merely unwise. The order of evaluation of ordinary function arguments is the opposite case: unspecified in C and C++ (and, since C++17, merely indeterminately sequenced rather than interleaved), fixed left-to-right in Java, C# and JavaScript. A rewrite that reorders argument evaluation is legal in the first group and illegal in the second.

AST-level rewriting looks safe because the transformations are small and obviously equivalent. They are obviously equivalent for pure expressions and routinely wrong for everything else, and the standard mistake is duplication.

Consider rewriting x ?? f() into x != null ? x : f(). Correct. Now consider g() ?? f(), rewritten the same way into g() != null ? g() : f(). g is now called twice. If g increments a counter, writes a log line, or returns a fresh object each time, the program has changed meaning and nothing in the compiler will say so — the output is a perfectly valid program that does the wrong thing.

The fix is universal and mechanical: bind each operand that may have effects to a temporary before duplicating it. Every production desugaring does this, which is why the desugared output of a real compiler is full of compiler-generated temporaries that look like noise and are not.

Desugaring a null-coalescing operator, correctly

Before

g() ?? f()

After

let t = g();
t != null ? t : f()

Legal only when

The rewrite preserves observable behavior only if the left operand is evaluated exactly once and before the right, and if the right operand is evaluated only when the left is null. Binding g() to a temporary guarantees the first two; keeping f() inside the conditional arm guarantees the third. The temporary itself must be fresh — a name no user code can refer to — or it will collide with a user variable and silently shadow it, which is [[shadowing]] as a compiler bug rather than a language feature.

Illegal when

The naive form g() != null ? g() : f() is illegal whenever g has side effects, is expensive, or returns a different value each call — which is to say, whenever g is a function call at all rather than a variable read. It is also illegal if the language specifies that the right operand is not evaluated when the left is non-null and the rewrite hoists f() out of the conditional, turning a lazily-evaluated branch into an eager one.

In place, or a new tree

Given that a rewrite must happen, there are two ways to perform it. Mutate the node in place — set node.kind = NumberLiteral; node.value = 3 — or return a replacement and let the parent install it, building a new tree whose unchanged subtrees are shared with the old one.

In-place mutation is faster in the narrow sense: no allocation, no copying, no parent rewiring. It is also the choice that forecloses everything interesting. There is exactly one version of the tree at any moment, so nothing can hold the previous version; a partially-applied pass leaves the tree in a state no invariant describes; and any reader running concurrently sees a torn structure. If the tree has parent pointers, replacing a node means fixing them up, and getting that wrong produces a tree that walks correctly downward and lies upward.

Building a new tree with structural sharing costs allocation only along the path from the changed node to the root — an O(depth) copy, not an O(nodes) one, because every subtree that did not change is pointed at by both versions. That is the standard persistent-data-structure trick, and it is what makes the old tree remain valid and usable after the new one exists.

Rewriting by returning a replacement, with sharing

1// Returns the original node when nothing changed, so unchanged subtrees
2// are shared by identity between the old tree and the new one.
3function fold(n: Expr): Expr {
4  if (n.kind !== 'Binary') return n
5 
6  const lhs = fold(n.lhs)
7  const rhs = fold(n.rhs)
8 
9  if (lhs.kind === 'Number' && rhs.kind === 'Number' && isTotal(n.op)) {
10    return { kind: 'Number', value: apply(n.op, lhs.value, rhs.value), span: n.span }
11  }
12 
13  // nothing folded and neither child moved: hand back the very same node
14  if (lhs === n.lhs && rhs === n.rhs) return n
15 
16  return { kind: 'Binary', op: n.op, lhs, rhs, span: n.span }
17}

The identity check on the last-but-one line is the whole optimization. Without it every node is reallocated on every pass and the sharing is lost; with it, a pass that changes nothing returns the original tree by reference and costs one traversal. isTotal is the legality guard: folding 1 / 0 or a signed overflow at compile time changes a runtime trap into a compile-time constant, and whether that is allowed depends on the language.

Why editor-facing frontends chose immutability

implementationRoslyn's red-green tree and tree-sitter's incremental parser are the two most-cited production examples, and rust-analyzer's rowan library follows Roslyn's design closely. All three are editor-first. Batch compilers make the opposite choice routinely: GCC and Clang both mutate their trees during semantic analysis, and this is not a defect — they run once per translation unit and exit, so no one is holding the old version. Do not read "immutable is better"; read "immutable is what buys incrementality, and incrementality is what an editor needs".

The languages with the strongest tooling have converged on immutable trees, and not for aesthetic reasons. Three concrete capabilities depend on it.

Incremental reparse. When a user types one character, an immutable tree lets the parser build a new tree that shares every untouched subtree with the old one. The work is proportional to the edit, not to the file. Roslyn and tree-sitter both do this, and it is the difference between an editor that keeps up with typing and one that does not.

Undo, and multiple versions. A refactoring produces a new tree while the old one is still the one on screen. Diffing them tells you what changed; discarding the new one is a pointer assignment. With in-place mutation, "undo" means reparsing the file from text.

Concurrent readers. A language server answers completion, hover and diagnostics requests on several threads over the same document. If the tree is immutable, they can all read the same version with no locking while a background parse builds the next one. If it is mutable, every reader needs a lock or a copy, and the copy is the whole file. This is immutability versus shared mutable state, straight out of the concurrency domain, arriving as an architectural constraint on a compiler frontend.

The price is real: more allocation, a garbage collector or arena that can cope with it, and a rewriting discipline where every pass returns a value rather than mutating one. A batch compiler that runs once and exits gains none of the three benefits and pays all of the cost — which is exactly why batch compilers frequently mutate in place and are right to.

Incremental reparse: work proportional to the edit, because unchanged subtrees are reused by reference.
Versioning and undo: the old tree stays valid, so a rejected refactoring costs nothing to abandon.
Concurrent readers: no locks, because nothing changes under a reader.
Caching: analysis results can be keyed by subtree identity, and identity survives edits elsewhere in the file.
The cost: allocation traffic along every changed path, and a pass style where nothing is mutated and everything is returned.

How it works

The steps, in the order the compiler takes them.

Decide whether the pass annotates or rewrites, and put annotations in a side table keyed by node id rather than in the node.
For a rewrite, state the legality condition before writing the code: what must be true of the operands for the replacement to mean the same thing.
Bind any operand that will be duplicated or reordered to a fresh compiler-generated temporary whose name cannot collide with user code.
Visit children first, then decide whether this node changes — folding is post-order because it depends on already-folded children.
Return the original node by identity when nothing changed, so the parent can also return unchanged and the sharing propagates all the way up.
Carry the original span onto the replacement node, or every later diagnostic about it points at nothing.
Apply buffered edits after the traversal completes if the walker does not support mutation during iteration.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A desugaring duplicates an operand with side effects and a function is called twice. A counter increments by two, a log line appears twice, an HTTP request is sent twice — and the source code shows one call.
A compiler-generated temporary collides with a user variable of the same name, and the user's value is silently overwritten inside the desugared construct. Works in every file except one.
A rewrite drops the span, and the type error reported on the rewritten node points at the top of the file, or at column zero of line one, in every message about that construct.
A pass mutates in place and fails halfway on an error path. The tree is now half-desugared, a later pass sees a shape no invariant allows, and the compiler crashes with an internal error naming a node kind the user never wrote.
A language server mutates the tree while a completion request is reading it. Completion returns entries from a stale or half-built tree, intermittently, and no log line records why.
Constant folding evaluates 1 / 0 at compile time and the program that was supposed to trap at runtime now fails to build — or, worse, folds signed overflow to a value the target would not have produced.

When it helps

Normalising many surface forms into few core forms, so that later passes handle one shape instead of five.
Constant folding and simplification on the AST, where a few obvious wins are available before the IR exists.
Any automated refactoring, which is by definition a tree rewrite followed by printing the result back through the source text.

When it hurts

Anything that must be reported to a user in terms of what they wrote. Once for (const x of xs) is an iterator loop, no message can mention for...of again.
Optimization proper. The AST is a bad place to optimize: no control-flow graph, no data-flow facts, no single-assignment property. Almost everything is better done on the [[what-is-an-ir]] representation.
A tree that other tools consume. A rewrite that suits the code generator can break every formatter and lint rule written against the same tree.

What it costs

Every one of these is paid by something.

Rewriting early buys simpler downstream passes and costs diagnostic quality permanently — every later message speaks the rewritten language, not the user's.
Immutable rewriting buys sharing, versioning, undo and lock-free concurrent readers, and costs allocation on every changed path plus a discipline that every pass must follow without exception.
In-place mutation buys allocation-free passes and costs the ability to hold two versions, to recover from a failed pass, or to read the tree from another thread.
Introducing temporaries to preserve evaluation semantics buys correctness and costs readable output: a desugared listing full of __tmp3 is much harder to review than the naive wrong version.
Keeping annotations in side tables rather than node fields buys a small, stable node and costs an indirection and a lookup on every access — which shows up in profile data for hot passes.

What else you could do

What a different compiler or language does instead, and when that is better.

Do not rewrite the AST at all: lower to a separate representation and rewrite that. rustc's AST-to-HIR lowering and Clang's AST-to-LLVM-IR emission both do this, and it is the reason both frontends can still report errors in the user's own syntax.
Rewrite as a rule set rather than as code: term-rewriting systems and Stratego-style strategies express transformations declaratively, and can be composed and checked. Harder to debug, and legality conditions become side conditions on rules rather than code you can step through.
Rewrite only the printed output — a source-to-source tool that edits text at spans rather than rebuilding a tree. This is what most codemods do, and it preserves formatting perfectly at the cost of being unable to express anything structural.
Rewrite nothing during compilation and instead make the interpreter or code generator handle every surface form directly. Fine for a small language; the cost grows linearly with the number of constructs and is paid by every backend.

See it for yourself

The flag, dump or tool that shows you this directly.

rustc: rustc -Z unpretty=hir prints the tree after desugaring. Compare with -Z unpretty=ast-tree on the same file — for loops, ?, if let and async blocks all visibly change shape, and the compiler-generated temporaries appear.
Babel: npx babel file.js --plugins=@babel/plugin-transform-optional-chaining prints the desugared output, temporaries and all. It is the clearest short demonstration of the duplicate-side-effect problem being solved in production code.
TypeScript: tsc --target es5 on a file using for...of and optional chaining shows the same thing, and its generated _a temporaries are the fresh-name discipline in action.
Python: ast.NodeTransformer rewrites and returns nodes; ast.fix_missing_locations exists specifically because rewrites lose spans, which is the failure mode named above with a standard-library workaround.

Plausible wrong readings

Stated the way a confident engineer states them.

"Constant folding on the AST is always safe — the values are right there." Division by zero, signed overflow, floating-point rounding modes and the target's NaN behavior all say otherwise. Folding is arithmetic *on the target's semantics*, not on the host's.
"Immutable trees are slow because they allocate." They allocate along one root path per edit and share everything else. The relevant comparison is against reparsing the file, which is what the mutable design has to do instead.
"A rewrite that produces an equivalent program is legal." Equivalent in value is not enough. Same effects, same order, same number of evaluations, same traps — all four, or it is not the same program.
"Desugaring is the parser's job, it saves a phase." It saves a phase and costs every diagnostic, every formatter and every refactoring the ability to speak the user's syntax.

Misconceptions

The claim, and what is actually true.

Annotating and rewriting are the same kind of pass.

One adds information and is always safe; the other destroys information and always needs a proof. Conflating them is how legality conditions go unstated.

Mutation is an implementation detail invisible from outside.

It determines whether the frontend can ever support incremental reparse, refactoring preview or a multi-threaded language server. It is visible as the absence of those features.

If the rewritten program produces the same result, the rewrite was correct.

The same result on the inputs you tested. Side effects, evaluation counts, ordering and traps are all part of observable behavior, and all four are what rewrites break.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

practical

Before writing any rewrite, write down its legality condition as a sentence, then check three things in the code: are any operands duplicated (bind them to fresh temporaries), is any evaluation order changed (check the language spec, not your intuition), and does the replacement carry the original span (or every diagnostic about it is lost). Those three cover the large majority of AST-rewriting bugs that reach production.

advanced

The decision that matters is not mutation versus immutability but *where the rewriting boundary sits*. Frontends that must serve editors keep the surface tree pristine and do every structural change in a lowering step to a second representation; the surface tree is then a pure function of the source text, which is what makes it cacheable, shareable and reproducible. Frontends that rewrite in place have merged those two representations into one, and every consumer of the tree now depends on which passes have run — a dependency that is invisible in the type system and discovered by whoever adds the twentieth pass.

internals

Roslyn's red-green split is the fullest expression of this. The green tree is immutable, parent-free, position-free and fully shareable: identical subtrees anywhere in any file can be the same object, and the node caches its own width so absolute positions are computable on demand. The red tree is a lazily-materialised facade over it that supplies parents and absolute positions, created on access and discarded freely. An edit rebuilds green nodes only along the root path and reuses everything else, so a keystroke costs O(depth) rather than O(file); the red wrappers for untouched regions are simply re-created if anyone asks. The design buys incremental parsing, undo, concurrent readers and cross-file subtree sharing, and pays for it in two node types, a second allocation on every access path, and a rule that no field on a green node may ever mention position.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

specWhether a compiler may fold an expression that would trap is language-defined and not a matter of taste. C and C++ make signed overflow undefined, so folding it is permitted and implementations do; they also make division by zero undefined, and GCC and Clang will refuse to fold it into a constant while still assuming it cannot happen. Java specifies wrapping integer overflow and an ArithmeticException on integer division by zero, so neither may be folded away. The same rewrite is legal in one language and a miscompilation in the other.

implementationStructural sharing on rewrite is what Roslyn, rowan (rust-analyzer) and tree-sitter provide; it is not something an AST has by default. A tree of mutable objects with parent pointers cannot share subtrees at all, because a shared node would need two parents. If sharing matters, it has to be designed for in [[ast-node-design]] before any pass is written.

simplifiedThe fold example handles only binary expressions over number literals and delegates the entire legality question to an isTotal predicate. A real folder must also model the target's integer width and signedness, the language's overflow rules, floating-point rounding and NaN propagation, and must decline to fold anything whose result depends on the host machine rather than the target — see [[constant-folding]].

If you were asked this in an interview

You are asked to desugar a ?? b into a conditional. Write the transformation and then say what is wrong with the obvious version.
Why do editor-facing compilers use immutable syntax trees? Name three capabilities that depend on it.
How expensive is one edit to a persistent tree, and what is the cost proportional to?
A rewritten node lost its span. What does the user see?

Connections

DSAn-ary-tree dfs

Concurrencyimmutability shared-mutable-state thread-safety

Domains that do not exist yet

Programming Languages & Runtime Internals — Persistent data structures and the allocation behavior of structural sharing
Copy-on-write along a root path is a general technique with a general cost model, and how a garbage collector reacts to that allocation pattern is a runtime question. What is ours is that this is the mechanism an incremental compiler frontend is built on.