7.2 AST Node Design and Source Ranges

An AST is the interface between parser, resolver, type checker, optimizer, formatter, debugger, and diagnostics. Node design should make invalid shapes hard to construct and common analyses easy to write.

Expr = IntExpr(value, range)
     | NameExpr(token, range)
     | BinaryExpr(left, operator, right, range)
     | CallExpr(callee, arguments, range)

The broad range for a + b runs from the start of a to the end of b. Keep narrower ranges too: the name token for “unknown name,” the operator for “operator not defined,” and a delimiter for “expected ).” One whole-expression range cannot produce every useful diagnostic.

The table below maps common diagnostics to the range each one should use:

Choosing the wrong range makes users see “the error is over there, but the cursor points here.” Keeping both a wide range and a few key sub-ranges on each node is what lets every diagnostic land precisely.

Ranges Need a Clear Contract

Use half-open offsets [start, end): start is included and end is the first character after the node. Adjacent ranges then compose cleanly, empty ranges are well-defined, and extracting source text is direct. A file object can map offsets to line/column only when displaying a message, avoiding inconsistent cached locations on every node.

Synthetic nodes need honest ranges. A desugared node inherits its source construct. A recovery node points at the unexpected token or insertion position. Never spread a synthetic node over unrelated source merely to give an error somewhere to point.

Traversal and Semantic Side Tables

Many phases traverse the same tree. Start with a simple recursive walker; introduce a visitor when many passes need exhaustive dispatch. Avoid placing every fact directly on mutable nodes. The parser owns syntax, the resolver can record NameExpr -> SymbolId, and the type checker can record Expr -> Type in side tables or a later annotated tree. This separation helps testing and incremental analysis.

Source range is not identity. Inserting one character moves many ranges. Use a separate NodeId only when tooling needs stable identity, and keep NodeId, range, and semantic facts as distinct concepts.

Debugging Hint

If every error highlights the whole file, find the first constructor that copied a parent range into a child. If a new feature is silently ignored, require exhaustive switching over node kinds rather than a default branch.

Design Nodes Around Invariants

Make each constructor enforce a small truth. A CallExpr owns one callee and an ordered list of arguments; it should not permit a null callee or a comma token disguised as an argument. A BinaryExpr should have exactly two expressions and an operator from the language's binary-operator set. It is easier to reject a malformed AST at construction time than to debug a type checker that encountered a missing child many passes later.

Lists deserve the same care. An empty block can be BlockStmt(statements=[]); an absent else is usually elseBranch=null, not an empty block, because those forms have different source meaning. Optional syntax, missing recovery values, and empty lists are three different states. Name them differently in the data model.

Range Tests Worth Writing

• The range of f(a, b) includes the final ); its first argument does not.

• A nested expression range is contained by its parent range.

• Every parser-created node has a range in the current source file.

• A synthetic recovery node has a deliberate zero-width or token-width range.