Designing AST Nodes

Every pass begins by asking "what kind of node is this". The two mainstream answers are a tag you switch on, and a virtual method you dispatch through. They look like a language-preference argument and they are not: they trade the two halves of the expression problem against each other, and the choice is close to irreversible once a hundred passes exist.

A tagged union — a kind enum plus a payload, or a Rust/OCaml/Swift enum — makes every pass a single match over all node kinds. The compiler tells you when you have missed one, which is [[exhaustiveness-checking]] doing real work. Adding a node kind breaks every pass at compile time, loudly and correctly. Adding a *pass* costs nothing: it is one more function.

A class hierarchy with virtual methods inverts it. Adding a node kind is a new subclass and nothing else changes, so a language with hundreds of node kinds and a slowly growing pass count is comfortable. Adding an operation means touching every class in the hierarchy — which is precisely why compilers built this way reach for [[visitor-pattern]] almost immediately, to get the tag-switch shape back without giving up the hierarchy.

The obvious encoding of a child is a pointer — Box<Expr>, unique_ptr<Expr>, an object reference. It is also the one that most modern compiler frontends have moved away from. rustc, Roslyn, rust-analyzer, Zig's self-hosted compiler and Carbon all keep nodes in a flat arena and refer to children by a 32-bit index.

The reasons are concrete, and none of them is "indices are more elegant". First, a node reference becomes Copy and four bytes wide: it can be stored in a side table, put in a hash map, sent across a thread boundary, or serialised into a cache file without any of the questions a pointer raises. Second, it removes lifetimes and ownership from every signature in the compiler — a pass takes &Ast and an index, not a borrow of a node with a lifetime that has to be threaded through every helper. Third, the nodes are contiguous, so a traversal walks memory in order instead of chasing pointers across a heap; that is the pointer-chasing problem from Computer Architecture avoided, and spatial locality gained.

The costs are equally concrete. Every child access is now ast.nodes[i], which is a bounds check and a second field access, and the index carries no type information — nothing stops you indexing the expression arena with a statement index, so implementations wrap indices in newtypes to get that back. And a dangling index is *worse* than a dangling pointer: it silently names some other live node instead of crashing.

The first time a pass needs to ask "what encloses this node" — to report an error in context, to decide whether a return is inside a function, to rewrite a node in place — the temptation to add a parent field is overwhelming. Resist it once and understand why.

A parent pointer makes the tree cyclic. Cyclic structures cannot be shared between two versions of a tree, cannot be built bottom-up without a fixup pass, cannot be freely copied, and defeat every persistent-data-structure trick that [[ast-transformations]] depends on. In a reference-counted implementation they leak; in an arena they are merely a field that every construction site must remember to set correctly, and one that is wrong the moment any node is reparented.

The standard alternative is to pass the parent chain down the traversal instead of storing it. A visitor already knows its ancestors — they are its call stack. Where random access is genuinely needed, compilers build a parent map as a side table on demand: one pass over the tree, an id -> id map, thrown away when the query is done. Roslyn goes further and computes the parent lazily from an immutable green tree while handing the caller a red-tree wrapper that appears to have parents; the cycle exists only in the view, never in the stored data.

Node-kind count is a real design axis. Too few and every pass carries a pile of conditionals distinguishing cases the type system could have separated — a single Expr node with an op: string field means the type checker cannot know that a + node has two children. Too many and every pass is a four-hundred-arm match, most arms identical, and adding a language feature means editing all of them.

The lever that controls the count is what you do with syntactic sugar. a += 1, for (x of xs), if let, string interpolation, optional chaining — each can be its own node kind, or the parser can desugar it immediately into the core forms. Desugaring at parse time collapses the kind count and means every later pass gets the feature for free, which is a very large saving across thirty passes.

It also destroys the ability to say +=. Every diagnostic, every formatter, every "expand this macro" in an IDE and every refactoring now sees the desugared form. This is why compilers that serve editors keep sugar as distinct nodes in the surface tree and desugar during [[lowering]] into a second, smaller representation — rustc's AST-to-HIR step is exactly this, and the reason it exists at all is that the AST has an audience the HIR does not.