Lesson 4.7 — Syntax-tree design: hierarchies, sum types, arenas, red–green trees and lowering

Techniques: owning class hierarchies with LLVM-style RTTI (Clang), sum types with std::variant (Rust's enum, ML datatypes), arena and index-based trees (Hanson 1990; llvm::BumpPtrAllocator, rustc's HirId), lossless red–green trees (Roslyn; rowan/rust-analyzer; SwiftSyntax), lowering CST → AST → HIR (rustc) · Pebble implements: a kind-tagged class hierarchy allocated in ASTContext's bump arena (pebble/include/pebble/AST/), an index-based tree in the comparison lab (solutions/labs/ch04-paradigms/src/Tree.h) · Prerequisites: Lesson 4.6 (error nodes, lossless trees) · Time: 3 hours

The parser's output is the data structure every later phase walks, queries, rewrites and prints: name resolution, type checking, the language server, the formatter, the lowering to IR. Its design decides how fast the compiler runs (allocation and pointer chasing), how safe the code that walks it is (can a pass forget a node kind?), what an IDE can do with it (is the whitespace still there? can a node be shared between two versions of a file?), and how many node kinds each later phase must understand. This lesson compares the five designs production compilers use and the lowering chain that connects them.

1. Problem and motivation

The problem. Choose a representation for syntax trees: given the productions of a grammar, represent each tree node with its kind, its children and its source range so that (a) building a tree costs \(O(1)\) per node, (b) later phases can test a node's kind and reach its children in \(O(1)\), (c) a phase can be checked, ideally by the compiler, to handle every kind, and (d) the representation keeps exactly the information its consumers need — every byte of the source for a formatter or an IDE, only the semantically relevant structure for a type checker.

Class hierarchies with LLVM-style RTTI

The object-oriented answer is one class per node kind under an abstract base: Expr ← BinaryOperator, CallExpr, … Clang has 281 StmtNode definitions, abstract and concrete (clang/include/clang/Basic/StmtNodes.td [CLANG-StmtNodes]). C++'s own RTTI (dynamic_cast) is too slow and too big for millions of nodes, so LLVM projects store a small kind field in the base and give each class a static classof; isa<>, cast<> and dyn_cast<> [LLVM-Casting, LLVM-RTTI] then test the kind with one or two integer comparisons. pebblec's AST (pebble/include/pebble/AST/Expr.h) is built the same way, with its 18 expression kinds generated from ASTNodes.def. Lesson 10.4 studies the casting machinery itself; here the question is what it means for the design of the tree.

Sum types with std::variant

The functional answer is a sum type (algebraic data type): Expr = Num(int) | Add(Expr, Expr) | …, as in ML, Haskell and Rust's enum; the compiler checks that each match covers every constructor. This is how rustc's AST is written (enum ExprKind in compiler/rustc_ast/src/ast.rs [RUSTC-AST]) and how most compilers written in ML-family languages represent syntax [ModernML]. C++17's std::variant with std::visit brings the same shape into C++. The trade-off between the two answers — adding a new kind vs adding a new operation — is Wadler's expression problem [Wad98].

Arena and index-based trees

Both answers still need memory. Compiler trees have one lifetime (the compilation unit), so individual new/delete is waste: an arena allocates by bumping a pointer through large slabs and frees everything at once (Hanson 1990 [Han90]). Clang allocates every AST node in ASTContext's llvm::BumpPtrAllocator [LLVM-Allocator]; pebblec does the same. Going one step further, nodes can live in a vector and refer to each other by integer index: 4-byte references instead of 8-byte pointers, trivial serialization, and IDs that are stable across runs. rustc's HIR names every node by a HirId (owner item, local index) [RUSTC-HirId], and the comparison lab's parsers build their trees this way.

Lossless red–green trees

An IDE needs a tree that keeps every character — whitespace, comments, error tokens — can be shared between versions of a file (Lesson 4.6's incremental reparsing), and still gives each node its absolute position and parent. Roslyn, Microsoft's C# and Visual Basic compiler, split the tree in two [ROSLYN-Green]: immutable, position-independent green nodes that store only kind, width and children (so identical subtrees can be shared, even within one file), and lightweight red nodes, created on demand while walking, that add parent pointers and absolute offsets. rust-analyzer's rowan library [ROWAN, RA-SyntaxDoc] and Apple's SwiftSyntax [SWIFTSYNTAX-Arena] use the same design.

Lowering CST → AST → HIR

No single tree fits all phases. A production front end is a chain: a lossless concrete syntax tree for the IDE and formatter; an abstract syntax tree without trivia and parentheses for macro expansion and name resolution; a high-level IR in which surface constructs are desugared into a few core ones (for into loop + match, ? into match, if let into match) for type checking. rustc lowers its AST to HIR in compiler/rustc_ast_lowering [RUSTC-Lower]; Swift and Kotlin have similar steps. Each lowering removes cases that the next phase would otherwise handle again.

2. Definitions and algorithms

Class hierarchies with LLVM-style RTTI

Definition 4.7.1 (Kind-tagged class hierarchy)

A kind-tagged hierarchy is a finite tree \(H\) of classes rooted at a base class \(B\), whose leaves are the concrete classes, together with an injective numbering \(\kappa : \mathrm{leaves}(H) \to \{0, \dots, m-1\}\). Every object of concrete class \(C\) stores \(\kappa(C)\) in a field of \(B\). For a class \(D\) of \(H\), let \(S_D = \{\kappa(C) : C \text{ is a leaf below or equal to } D\}\). The static test \(\mathrm{classof}_D(o)\) returns true iff the stored kind of \(o\) is in \(S_D\). The numbering is a preorder numbering if a depth-first traversal of \(H\) that visits children in a fixed order meets the leaves in the order \(\kappa^{-1}(0), \kappa^{-1}(1), \dots\)

Pebble's and Clang's expression hierarchies

In pebblec the hierarchy is flat: \(B\) = Expr, 18 concrete leaves (IntegerLiteralExpr, …, BinaryExpr, …, ParenExpr, ErrorExpr) numbered by their order in ASTNodes.def, and every \(S_D\) is a single kind, so classof is E->getKind() == Kind::BinaryExpr. Clang's is deep: Stmt ← ValueStmt ← Expr ← AbstractConditionalOperator ← {ConditionalOperator, BinaryConditionalOperator}, generated from StmtNodes.td in preorder, so Expr::classof is firstExprConstant <= K && K <= lastExprConstant [CLANG-StmtNodes].

Algorithm 4.7.2 (Kind-directed dispatch: isa, dyn_cast and the visitor switch)

• Input: a pointer \(o\) to an object whose dynamic class is a leaf of \(H\); a target class \(D\); for the visitor, one handler per concrete class.
• Output: isa: whether \(o\)'s class is below \(D\); dyn_cast: \(o\) as a D*, or null; visit: the result of the handler for \(o\)'s concrete class.
• Precondition: every constructor of a concrete class \(C\) sets the kind field to \(\kappa(C)\); kinds are never changed afterwards.
• Postcondition: isa<D>(o) ⇔ \(o\)'s class is a descendant of \(D\) (Theorem 4.7.11); visit calls exactly one handler.
• Invariant: the kind field of every live object equals \(\kappa\) of its dynamic class.

function IsA(D, o):
    k ← o.kind
    if D is concrete:  return k = κ(D)
    return first(D) ≤ k ≤ last(D)            # S_D = [first(D), last(D)] under preorder numbering
function DynCast(D, o):
    if o ≠ null and IsA(D, o): return o reinterpreted as D
    return null
function Visit(o, handlers):                   # pebble's ASTVisitor: switch (E->getKind())
    switch o.kind:
        case κ(C1): return handlers.C1(o as C1)
        ...one case per concrete class Ci, generated from the node list...
        case κ(Cm): return handlers.Cm(o as Cm)

Clang's AST: a class per node kind, allocated in the ASTContext

Reproduce (clang 23.1.2):

printf 'int f(int a, int b) { return a + b * 2; }\n' > f.c
clang-23 -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics f.c | tail -12

Output (the last 12 lines, the whole function; the hex addresses change from run to run):

`-FunctionDecl 0x557b6f08fa78 <f.c:1:1, col:41> col:5 f 'int (int, int)' external-linkage
  |-ParmVarDecl 0x557b6f08f910 <col:7, col:11> col:11 used a 'int'
  |-ParmVarDecl 0x557b6f08f990 <col:14, col:18> col:18 used b 'int'
  `-CompoundStmt 0x557b6f08fc58 <col:21, col:41>
    `-ReturnStmt 0x557b6f08fc48 <col:23, col:38>
      `-BinaryOperator 0x557b6f08fc28 <col:30, col:38> 'int' '+'
        |-ImplicitCastExpr 0x557b6f08fc10 <col:30> 'int' <LValueToRValue>
        | `-DeclRefExpr 0x557b6f08fb78 <col:30> 'int' lvalue ParmVar 0x557b6f08f910 'a' 'int'
        `-BinaryOperator 0x557b6f08fbf0 <col:34, col:38> 'int' '*'
          |-ImplicitCastExpr 0x557b6f08fbd8 <col:34> 'int' <LValueToRValue>
          | `-DeclRefExpr 0x557b6f08fb98 <col:34> 'int' lvalue ParmVar 0x557b6f08f990 'b' 'int'
          `-IntegerLiteral 0x557b6f08fbb8 <col:38> 'int' 2

What to notice: each line is one object whose class name is its kind (BinaryOperator, DeclRefExpr, IntegerLiteral); the dumper is exactly Algorithm 4.7.2's Visit, generated from StmtNodes.td. The addresses are close together and increase in construction order (DeclRefExpr a at …fb78, b at …fb98, 2 at …fbb8, * at …fbf0, + at …fc28): the nodes come from one bump arena, not from malloc. clang/include/clang/AST/Stmt.h enforces this: the plain operator new of Stmt is protected and llvm_unreachable("Stmts cannot be allocated with regular 'new'."), and the public one takes an ASTContext& [CLANG-Stmt]. Clang's tree is not purely syntactic: ImplicitCastExpr <LValueToRValue> is inserted by semantic analysis, which runs interleaved with parsing.

Sum types with std::variant

Definition 4.7.3 (Sum type, tagged union, exhaustive case analysis)

A sum type \(T = C_1(\tau_{1,1}, \dots, \tau_{1,a_1}) + \dots + C_k(\tau_{k,1}, \dots, \tau_{k,a_k})\) has as values the tagged tuples \((C_i, v_1, \dots, v_{a_i})\) with \(v_j : \tau_{i,j}\); it is recursive if some \(\tau_{i,j}\) mentions \(T\) (behind a pointer, in C++). A tagged-union representation stores the tag \(i \in \{0, \dots, k-1\}\) next to storage large enough for the largest alternative: its size is \(\mathrm{round}_{\alpha}(\max_i \mathrm{size}(C_i) + \mathrm{size}(\text{tag}))\), where \(\alpha\) is the largest alignment. A case analysis on \(T\) is a function given by one clause per constructor; it is exhaustive if every \(C_i\) has a clause. std::variant<A_1, …, A_k> is a tagged union; std::visit(f, v) is a case analysis that is rejected at compile time unless f is callable with every alternative.

A variant expression tree

using Expr = std::variant<Num, Add, Neg> with struct Num { long V; }, struct Add { std::unique_ptr<Expr> L, R; } and struct Neg { std::unique_ptr<Expr> E; }: the largest alternative is Add (16 bytes), the tag takes one byte, and rounding to 8-byte alignment gives sizeof(Expr) = 24 (measured in the box below). Add{Num 40, Neg(Num -2)} has tag 1 (index() == 1).

Algorithm 4.7.4 (Structural fold over a sum type)

• Input: a finite tree \(e\) of a recursive sum type \(T\); one clause \(f_i\) per constructor \(C_i\), which receives the non-recursive fields of the node and the fold's results for its recursive fields.
• Output: \(\mathrm{fold}(e)\).
• Precondition: the clause set is exhaustive; the tree is finite and acyclic (owned children, as with unique_ptr).
• Postcondition: \(\mathrm{fold}(C_i(v_1, \dots, v_a)) = f_i(v'_1, \dots, v'_a)\) where \(v'_j = \mathrm{fold}(v_j)\) for recursive fields and \(v'_j = v_j\) otherwise.
• Invariant: each call is made on a proper subtree of its caller's argument.

function Fold(e):
    i ← tag(e)                                   # std::visit dispatches on index()
    for each field v_j of e:
        v'_j ← Fold(*v_j) if v_j is recursive else v_j
    return f_i(v'_1, ..., v'_a)

std::visit rejects a non-exhaustive fold; sizeof is the tagged-union formula

Reproduce (clang 23.1.2 with libstdc++ 14; var.cpp is the example above with eval written as a fold with one lambda per alternative, and the Neg lambda wrapped in #ifndef FORGET_NEG):

cat > var.cpp <<'EOF'
#include <cstdio>
#include <memory>
#include <variant>
struct Num; struct Add; struct Neg;
using Expr = std::variant<Num, Add, Neg>;
struct Num { long V; };
struct Add { std::unique_ptr<Expr> L, R; };
struct Neg { std::unique_ptr<Expr> E; };
template <class... F> struct overloaded : F... { using F::operator()...; };
long eval(const Expr &E) {
  return std::visit(overloaded{
      [](const Num &N) { return N.V; },
      [](const Add &A) { return eval(*A.L) + eval(*A.R); },
#ifndef FORGET_NEG
      [](const Neg &N) { return -eval(*N.E); },
#endif
  }, E);
}
int main() {
  Expr E = Add{std::make_unique<Expr>(Num{40}), std::make_unique<Expr>(Neg{std::make_unique<Expr>(Num{-2})})};
  std::printf("eval = %ld, sizeof(Expr) = %zu, index = %zu\n", eval(E), sizeof(Expr), E.index());
}
EOF
G=--gcc-install-dir=/usr/lib/gcc/x86_64-linux-gnu/14
clang++-23 $G -std=c++23 -o var var.cpp && ./var
clang++-23 $G -std=c++23 -fsyntax-only -DFORGET_NEG var.cpp 2>&1 | grep -E 'error' | head -1

Output (complete):

eval = 42, sizeof(Expr) = 24, index = 1
/usr/lib/gcc/x86_64-linux-gnu/14/../../../../include/c++/14/type_traits:3155:5: error: no type named 'type' in 'std::invoke_result<overloaded<(lambda at var.cpp:12:7), (lambda at var.cpp:13:7)>, const Neg &>'

What to notice: removing one clause is a compile-time error (seven errors in all, the first shown), the C++ counterpart of Rust's "non-exhaustive patterns" — but the message comes from inside the library, not from the language. sizeof(Expr) = 24 is Definition 4.7.3's formula: every node pays for the largest alternative, which is why real variant ASTs keep alternatives small and box the big ones.

rustc's AST is a sum type

Reproduce (rustc 1.94.1; -Zunpretty is unstable, so RUSTC_BOOTSTRAP=1 enables it on a stable toolchain):

printf 'fn f(a: i32, b: i32) -> i32 { a + b * 2 }\n' > f.rs
RUSTC_BOOTSTRAP=1 rustc --crate-type=lib -Zunpretty=ast-tree f.rs | sed -n 144,150p

Output (lines 144–150 of 242):

                                    kind: Expr(
                                        Expr {
                                            id: NodeId(4294967040),
                                            kind: Binary(
                                                Spanned {
                                                    node: Add,
                                                    span: f.rs:1:33: 1:34 (#0),

What to notice: a rustc Expr is a struct with common fields (id, span, attrs, tokens) and a kind that is a sum type: ExprKind::Binary(BinOp, Box<Expr>, Box<Expr>) in compiler/rustc_ast/src/ast.rs [RUSTC-AST], with the operator itself another enum (Add, Mul). This "struct + kind enum" split is the variant design with the shared fields factored out. NodeId(4294967040) is 0xFFFFFF00, rustc's DUMMY_NODE_ID: the parser does not number nodes; ids are assigned after macro expansion.

Arena and index-based trees

Definition 4.7.5 (Arena, bump allocation, index-based tree)

An arena is an allocator whose objects are all freed together. A bump allocator implements it with a list of slabs (contiguous blocks of \(S\) bytes) and a pointer \(p\) into the current slab: an allocation of \(s \le S\) bytes with alignment \(a\) rounds \(p\) up to a multiple of \(a\), returns it and advances \(p\) by \(s\), opening a new slab when the current one has fewer than \(s\) bytes left; requests larger than a threshold get a slab of their own. An index-based tree stores its nodes in an array \(N[0..n)\); a node refers to its children by indices into \(N\) (a typed index wraps the integer in a distinct type per node array, e.g. ExprId). An id of a node is a key under which other tables (types, resolutions, spans) store facts about it.

The lab's index tree for a + b * 2

The lab's Pratt parser (solutions/labs/ch04-paradigms/src/Tree.h) appends nodes in construction order: \(N[0]\) = leaf a, \(N[1]\) = leaf b, \(N[2]\) = leaf 2, \(N[3]\) = (* 1 2), \(N[4]\) = (+ 0 3); the root is index 4. Children always have smaller indices than their parent (the tree is built bottom-up), so a single forward pass over \(N\) is a post-order traversal.

Algorithm 4.7.6 (Bump allocation, after llvm::BumpPtrAllocatorImpl)

• Input: a size \(s\) and an alignment \(a\) (a power of two); the allocator state: current pointer \(p\), end \(e\) of the current slab, slab list \(L\), slab size \(S\) (4096 bytes by default in LLVM) and threshold \(\theta\) (default \(S\)).
• Output: a pointer to \(s\) fresh bytes aligned to \(a\).
• Precondition: \(a \le\) the alignment guaranteed by the system allocator.
• Postcondition: the returned block does not overlap any block returned earlier; nothing is freed until the arena is destroyed.
• Invariant: every block handed out lies inside a slab in \(L\) (or a custom-sized slab); \(p \le e\).

function Allocate(s, a):
    q ← AlignUp(p, a)
    if q + s ≤ e:                                  # fast path: bump
        p ← q + s;  return q
    if s + a − 1 > θ:                              # large object: its own slab
        B ← SystemAlloc(s + a − 1);  append B to L's custom list
        return AlignUp(B.start, a)
    B ← SystemAlloc(SlabSize(|L|));  append B to L    # SlabSize doubles every 128 slabs
    p ← B.start;  e ← B.start + SlabSize(|L| − 1)
    q ← AlignUp(p, a);  p ← q + s;  return q
function AlignUp(x, a): return (x + a − 1) & ~(a − 1)

Clang's AST lives in 4096-byte slabs

Reproduce (clang 23.1.2, same f.c as above):

clang-23 -fsyntax-only -Xclang -print-stats f.c 2>&1 | grep -v '^ *0 ' |
  awk '/AST Context Stats/{on=1} on{print} on&&/^Total bytes/{if(++n==3)exit}'

Output (complete for this filter: the AST-context part of the statistics, with zero-count lines removed):

*** AST Context Stats:
  70 types total.
    1 ConstantArray types, 48 each (48 bytes)
    61 Builtin types, 32 each (1952 bytes)
    1 FunctionProto types, 48 each (48 bytes)
    4 Pointer types, 48 each (192 bytes)
    1 PredefinedSugar types, 32 each (32 bytes)
    2 Record types, 32 each (64 bytes)
Total bytes = 2336
0/0 implicit default constructors created
0/0 implicit copy constructors created
0/0 implicit copy assignment operators created
0/0 implicit destructors created

Number of memory regions: 2
Bytes allocated: 8192
 (includes alignment, etc)

*** Decl Stats:
  19 decls total.
    1 ExternCContext decls, 72 each (72 bytes)
    1 Function decls, 168 each (168 bytes)
    2 ParmVar decls, 104 each (208 bytes)
    8 Field decls, 80 each (640 bytes)
    2 Record decls, 128 each (256 bytes)
    5 Typedef decls, 88 each (440 bytes)
Total bytes = 1784

*** Stmt/Expr Stats:
  9 stmts/exprs total.
    1 IntegerLiteral, 32 each (32 bytes)
    2 DeclRefExpr, 32 each (64 bytes)
    2 ImplicitCastExpr, 24 each (48 bytes)
    2 BinaryOperator, 32 each (64 bytes)
    1 ReturnStmt, 16 each (16 bytes)
    1 CompoundStmt, 16 each (16 bytes)
Total bytes = 240

What to notice: "memory regions: 2, bytes allocated: 8192" is the ASTContext's BumpPtrAllocator with LLVM's default slab size \(S = 4096\) (llvm/include/llvm/Support/Allocator.h [LLVM-Allocator]). Types, declarations and statements need \(2336 + 1784 + 240 = 4360\) bytes, just over one slab, hence two. Expression nodes are tiny (16–32 bytes): a kind field, a type pointer and child pointers, with no vtable in Stmt (dispatch is by kind, Algorithm 4.7.2).

rustc's HIR names every node by (owner, local index)

Reproduce (rustc 1.94.1, f.rs from the sum-type box):

RUSTC_BOOTSTRAP=1 rustc --crate-type=lib -Zunpretty=hir-tree f.rs | grep -n 'hir_id: HirId(DefId(0:3' | sed -n '12,16p'

Output (complete for this range; the crate hash fbdf depends on the file name and compiler):

340:                hir_id: HirId(DefId(0:3 ~ f[fbdf]::f).13),
346:                                hir_id: HirId(DefId(0:3 ~ f[fbdf]::f).6),
353:                                        hir_id: HirId(DefId(0:3 ~ f[fbdf]::f).7),
365:                                                            hir_id: HirId(DefId(0:3 ~ f[fbdf]::f).8),
379:                                        hir_id: HirId(DefId(0:3 ~ f[fbdf]::f).9),

What to notice: the body block is .13, a + b * 2 is .6, a is .7 (its path segment .8), b * 2 is .9: every HIR node is an index local to its owner item f (DefId(0:3)), and in the same dump the path a is resolved as res: Local(HirId(DefId(0:3 ~ f[fbdf]::f).2)), an index again rather than a pointer. compiler/rustc_hir_id/src/lib.rs [RUSTC-HirId] explains the two-level design: moving an item or editing another one does not change the local ids inside it, which makes them stable keys for incremental compilation.

Lossless red–green trees

Definition 4.7.7 (Green tree, red node, lossless)

A green token is a pair (kind, text); its width is \(|\text{text}|\). A green node is a pair (kind, \([g_1, \dots, g_k]\)) of a kind and a sequence of green elements (nodes or tokens); its width is \(w(g) = \sum_i w(g_i)\), and it stores, for each child, the relative offset \(r_i = \sum_{j<i} w(g_j)\). Green elements are immutable and contain no position and no parent, so equal green elements are interchangeable and may be shared (hash-consing). A red node is a triple (green element \(g\), parent red node or none, absolute offset \(o\)); the root is \((g_{\text{root}}, \text{none}, 0)\) and the \(i\)-th child of \((g, \_, o)\) is \((g_i, \text{that node}, o + r_i)\). A tree is lossless for a text \(x\) if the concatenation of its green tokens' texts, left to right, is \(x\).

Green and red for a + b * 2

With rust-analyzer's grammar, the green tree of the 9-byte text a + b * 2 is \(\mathrm{BIN}[\mathrm{PATH}(a), \mathrm{WS}, {+}, \mathrm{WS}, \mathrm{BIN}[\mathrm{PATH}(b), \mathrm{WS}, {*}, \mathrm{WS}, \mathrm{LIT}(2)]]\) with widths \(1,1,1,1,5\) and relative offsets \(0,1,2,3,4\); the inner node's children have relative offsets \(0,1,2,3,4\) again. The red node of 2 is reached as root \((\cdot, \text{none}, 0)\) → fifth child at \(0 + 4 = 4\) → fifth child at \(4 + 4 = 8\): byte 8, as expected.

Algorithm 4.7.8 (Building a green tree with a node cache; red navigation)

• Input: the parser's event stream (start node of kind \(K\), token \((K, \text{text})\), finish node) in which every byte of the text belongs to exactly one token (trivia and error tokens included, Lesson 4.6); a cache \(H\) from (kind, children) to green nodes.
• Output: the root green node; red nodes on demand.
• Precondition: start and finish events are properly nested.
• Postcondition: the tree is lossless for the text; equal cached subtrees are the same object.
• Invariant: the stack holds, for each open node, the green children built so far, in order.

function Build(events):
    stack ← [[]]
    for ev in events:
        if ev = Start(K):    push [] on stack;  kinds.push(K)
        if ev = Token(K, t): top(stack).append(Intern((K, t)))
        if ev = Finish:      cs ← pop(stack);  K ← kinds.pop()
                             top(stack).append(InternNode(K, cs))
    return the single element of top(stack)
function InternNode(K, cs):                      # rowan: only nodes with ≤ 3 children are cached
    if |cs| > 3: return new GreenNode(K, cs, offsets = prefix sums of widths)
    key ← (K, identities of cs)
    if key ∉ H: H[key] ← new GreenNode(K, cs, prefix sums)
    return H[key]
function Intern(tok): look up or insert tok in H     # tokens are always cached
function Child(red (g, parent, o), i):            # O(1): relative offsets are stored
    return (g.children[i], (g, parent, o), o + g.offsets[i])

rowan shares equal green subtrees; the red nodes still have their own offsets

Reproduce (ra_ap_syntax 0.0.331, rowan 0.15.18, rustc 1.94.1; the cargo new setup of the box after Algorithm 4.6.7):

cat > src/bin/green.rs <<'EOF'
// rust-analyzer's syntax trees: shared green nodes for equal subtrees, distinct red nodes with their own offsets.
use ra_ap_syntax::{ast, AstNode, Edition, SourceFile};

fn main() {
    let text = "fn f() { g(1 + 1, 1 + 1, 1+1, 1+1) }";
    let file = SourceFile::parse(text, Edition::CURRENT).tree();
    let lits: Vec<ast::Literal> = file.syntax().descendants().filter_map(ast::Literal::cast).collect();
    for l in &lits {
        println!("red LITERAL {} at {:?}  green {:p}", l.syntax().text(), l.syntax().text_range(), &*l.syntax().green());
    }
    let bins: Vec<ast::BinExpr> = file.syntax().descendants().filter_map(ast::BinExpr::cast).collect();
    for b in &bins {
        println!("red BIN_EXPR {} at {:?}  green {:p}", b.syntax().text(), b.syntax().text_range(), &*b.syntax().green());
    }
    println!("lossless: {}", file.syntax().text() == text);
}
EOF
cargo run -q --bin green

Output (complete; the addresses change from run to run, their equalities do not):

red LITERAL 1 at 11..12  green 0x5606e02fbc58
red LITERAL 1 at 15..16  green 0x5606e02fbc58
red LITERAL 1 at 18..19  green 0x5606e02fbc58
red LITERAL 1 at 22..23  green 0x5606e02fbc58
red LITERAL 1 at 25..26  green 0x5606e02fbc58
red LITERAL 1 at 27..28  green 0x5606e02fbc58
red LITERAL 1 at 30..31  green 0x5606e02fbc58
red LITERAL 1 at 32..33  green 0x5606e02fbc58
red BIN_EXPR 1 + 1 at 11..16  green 0x5606e02fae08
red BIN_EXPR 1 + 1 at 18..23  green 0x5606e02fbff8
red BIN_EXPR 1+1 at 25..28  green 0x5606e02fb4b8
red BIN_EXPR 1+1 at 30..33  green 0x5606e02fb4b8
lossless: true

What to notice: all eight LITERAL red nodes, at eight different offsets, view one green node. 1+1 (three children) is shared too, but 1 + 1 (five children, counting the two whitespace tokens) is not: rowan/src/green/node_cache.rs builds nodes with more than three children without consulting the cache (if children_ref.len() > 3) [ROWAN] — a bound on hashing cost, since small nodes are where the duplicates are. rust-analyzer's own design notes [RA-SyntaxDoc] say interior nodes are shared "for example in (1 + 1) * (1 + 1)"; with rowan 0.15.18 that holds only for the spaceless form. lossless: true: printing the tree gives back the text, whitespace included.

Lowering CST → AST → HIR

Definition 4.7.9 (Lowering, desugaring, core language)

Let \(L_1\) and \(L_2\) be two tree languages with meanings \([\![\cdot]\!]_1\) and \([\![\cdot]\!]_2\) (for example, the observable behavior of a program). A lowering is a total function \(\ell : L_1 \to L_2\) computed by structural recursion; it is meaning-preserving if \([\![\ell(t)]\!]_2 = [\![t]\!]_1\) for all well-formed \(t\). A desugaring is a lowering where \(L_2 \subseteq L_1\) is a core language: some constructs of \(L_1\) ("sugar") are rewritten into combinations of the others. CST → AST drops trivia, parentheses and punctuation and keeps error nodes; AST → HIR resolves or desugars (rustc: for, while let, ?, async, format strings), and gives every node an id (Definition 4.7.5).

Algorithm 4.7.10 (Desugaring a counted loop: pebble-spec §7 and rustc's lower_expr_for)

• Input: a statement for i in a..b { B } of Pebble, or for p in head { B } of Rust.
• Output: an equivalent statement of the core language without for.
• Precondition: start, end, k, iter, result are fresh names (no capture, the hygiene condition of Lesson 4.8); in the Pebble case, \(B\) contains no continue that targets this loop, or continue is lowered to a jump to the increment (see Proposition 4.7.15).
• Postcondition: the result runs \(B\) with the same sequence of values for the loop variable, and evaluates a, b (or head) exactly once, before the first iteration.
• Invariant (Pebble form): at the top of the while, \(\mathit{start} \le k \le \max(\mathit{start}, \mathit{end})\) and the body has run for \(i = \mathit{start}, \dots, k-1\).

function LowerFor(for i in a..b { B }):                      # pebble-spec §7
    return { let start = a; let end = b; var k = start;
             while k < end { let i = k; B; k = k &+ 1; } }
function LowerForRust(for p in head { B }):                  # rustc_ast_lowering, lower_expr_for
    return { let result = match IntoIterator::into_iter(head) {
                 mut iter => loop {
                     match Iterator::next(&mut iter) {
                         None => break,
                         Some(p) => B,
                     };
                 }
             };
             result }

rustc lowers for to loop + match in the HIR

Reproduce (rustc 1.94.1):

cat > sum.rs <<'EOF'
fn f(a: i32, b: i32) -> i32 { a + b * 2 }
fn main() { let v = [1, 2, 3]; for x in v { println!("{}", f(x, 1)); } }
EOF
RUSTC_BOOTSTRAP=1 rustc -Zunpretty=hir sum.rs

Output (complete):

extern crate std;
#[prelude_import]
use ::std::prelude::rust_2015::*;
fn f(a: i32, b: i32) -> i32 { a + b * 2 }
fn main() {
    let v = [1, 2, 3];
    {
        let _t =
            match into_iter(v) {
                mut iter =>
                    loop {
                        match next(&mut iter) {
                            None {} => break,
                            Some {  0: x } => {
                                {
                                    ::std::io::_print({
                                            super let args = (&f(x, 1),);
                                            super let args = [format_argument::new_display(args.0)];
                                            unsafe { format_arguments::new(b"\xc0\x01\n\x00", &args) }
                                        });
                                };
                            }
                        }
                    },
            };
        _t
    }
}

What to notice: the HIR has no for and no println!: the loop is exactly LowerForRust (the doc comment of lower_expr_for in compiler/rustc_ast_lowering/src/expr.rs [RUSTC-Lower] shows the same template), with into_iter and next resolved to lang items, and the macro has become a call with a pre-encoded format template. The type checker, borrow checker and MIR builder never see a for loop. f is unchanged: arithmetic is already core.

3. Worked example

One expression, a + b * 2, in the five representations; the first four are built by code in this repository or shown in the boxes above.

Representation	What a node is	+ node	Its children	Navigation to the parent
Clang (hierarchy + arena)	object of class BinaryOperator, 32 bytes, in a 4096-byte slab	kind BinaryOperatorClass, opcode BO_Add	two Expr*	none stored (use ParentMapContext)
pebblec AST (hierarchy + arena)	BinaryExpr in ASTContext's BumpPtrAllocator	Kind::BinaryExpr, operator +	two Expr*	none
variant	std::variant<…>, 24 bytes + heap children	index() == 1 (Add)	two unique_ptr<Expr>	none
lab arena (Tree.h)	N in std::vector<N>	N[4] = ("+", {0, 3})	indices 0 and 3	none (a parent array is one pass away)
rowan (red–green)	green BIN_EXPR, width 9; red view with offset 0	BIN_EXPR with 5 children	PATH_EXPR, WHITESPACE, PLUS, WHITESPACE, BIN_EXPR	red node's parent

Red offsets. Walking to the literal 2 in the red–green tree (Algorithm 4.7.8's Child):

step	red node	green child index	relative offset \(r_i\)	absolute offset
0	outer BIN_EXPR	—	—	0
1	inner BIN_EXPR	4	\(1+1+1+1 = 4\)	\(0 + 4 = 4\)
2	LITERAL 2	4	\(1+1+1+1 = 4\)	\(4 + 4 = 8\)

Lowering. The Pebble loop for i in 0..n { s = s + i; } becomes, by LowerFor, { let start = 0; let end = n; var k = start; while k < end { let i = k; s = s + i; k = k &+ 1; } }; with n = 3 the invariant holds at the four loop tests with \(k = 0, 1, 2, 3\), and the body has run for \(i = 0, 1, 2\) when the loop exits.

Try it

build/<preset>/bin/ch04-parsedump --expr 'a + b * 2' prints pebblec's AST; the ch04-parse --algo=pratt tool of the lab prints the S-expression that Tree.h produces from its index array. Change the rowan example to (1+1)*(1+1) and predict which green nodes are shared before running it.

4. Invariants and correctness

Class hierarchies with LLVM-style RTTI

Theorem 4.7.11 (Preorder numbering makes classof an interval test)

If \(\kappa\) is a preorder numbering (Definition 4.7.1), then for every class \(D\) of \(H\) the set \(S_D\) is an interval \([\mathit{first}(D), \mathit{last}(D)]\), so Algorithm 4.7.2's IsA returns true exactly for objects whose class is a descendant of \(D\).

Proof

A depth-first traversal visits all nodes of the subtree of \(D\) consecutively: it enters \(D\), visits the subtrees of \(D\)'s children one after the other, and leaves \(D\) before visiting anything outside. Hence the leaves of \(D\)'s subtree are met consecutively, and under a preorder numbering they receive consecutive numbers: \(S_D = \{\mathit{first}(D), \dots, \mathit{last}(D)\}\) with \(\mathit{first}(D) = \min S_D\) and \(\mathit{last}(D) = \max S_D\). By the invariant of Algorithm 4.7.2 the stored kind of \(o\) is \(\kappa(C)\) for its dynamic class \(C\), and \(\kappa(C) \in S_D\) iff \(C\) is a leaf of \(D\)'s subtree, since \(\kappa\) is injective. So the interval test is equivalent to "\(C\) is a descendant of \(D\)". The same statement, with the LLVM-specific details (abstract classes with no kind of their own, firstXConstant), is Theorem 10.4.10 in Lesson 10.4.

Sum types with std::variant

Theorem 4.7.12 (An exhaustive structural fold is total)

Under the preconditions of Algorithm 4.7.4, Fold terminates on every finite tree and returns the value determined by the postcondition; in particular it never reaches a missing case.

Proof

By induction on the height \(h\) of the tree \(e\). If \(h = 0\), \(e\) has no recursive fields; its tag is some \(i\), a clause \(f_i\) exists by exhaustiveness, and Fold returns \(f_i\) of the non-recursive fields. If \(h > 0\), each recursive field \(v_j\) is a subtree of height less than \(h\) (the invariant), so by induction \(\mathrm{Fold}(v_j)\) terminates with the right value; then \(f_i\) exists by exhaustiveness and is applied once. Acyclicity is needed for "subtree of smaller height": with a shared cycle the height is undefined, which is why variant trees own their children. For a kind-tagged hierarchy the same proof holds for Visit provided the switch has a case for every kind — a property the C++ compiler checks only with -Wswitch and no default:, which is why the LLVM coding standards say not to use default labels in fully covered switches over enumerations.

Arena and index-based trees

Proposition 4.7.13 (Memory used by a bump arena)

Let an arena with fixed slab size \(S\) serve requests of sizes \(s_1, \dots, s_n\), each at most \(s_{\max} \le S\) after alignment padding, with total \(T = \sum_t s_t\). Then it allocates at most \(\lceil T / (S - s_{\max}) \rceil + 1\) slabs, i.e. at most \(S \cdot (T/(S - s_{\max}) + 2)\) bytes; for \(s_{\max} \le S/2\) that is less than \(2T + 2S\). Each allocation takes \(O(1)\) time, and freeing the arena takes \(O(\text{number of slabs})\).

Proof

A new slab is opened only when the next request does not fit in the current one, i.e. when fewer than \(s_{\max}\) bytes remain; so every slab except the last is filled with more than \(S - s_{\max}\) bytes of requests (padding included in \(s_t\)). If \(k\) slabs are used, \((k - 1)(S - s_{\max}) < T\), so \(k < T/(S - s_{\max}) + 1\) and \(k \le \lceil T/(S - s_{\max}) \rceil + 1\). With \(s_{\max} \le S/2\), \(S \cdot T/(S - s_{\max}) \le 2T\). The time bound is Algorithm 4.7.6: the fast path is a round-up, a compare and an add; the slow path calls the system allocator once and happens at most once per slab, so \(O(1)\) even without amortization. LLVM's allocator doubles \(S\) every 128 slabs, which only reduces the number of slabs. In the Clang box, \(T \approx 4360\) bytes of AST objects with \(s_{\max} \le 168\) bytes gives \(k = 2\) slabs of 4096 bytes, as reported.

Lossless red–green trees

Theorem 4.7.14 (Red offsets are exact; sharing is sound; edits copy one path)

For a green tree built by Algorithm 4.7.8 from a text \(x\): (a) the tree is lossless for \(x\); (b) the red node reached by any path of Child calls from the root has as offset the position in \(x\) of the first byte of its green element; (c) replacing one green subtree at depth \(d\) by another builds \(O(d)\) new green nodes (path copying), each in time proportional to its arity, and shares all others with the old tree.

Proof

(a) Every byte of \(x\) belongs to exactly one token event (precondition), tokens are appended to the innermost open node in text order, and nodes are appended to their parent when they finish, so an in-order walk of the leaves yields the tokens in text order; interning does not change any element's text. (b) By induction on the path length. The root has offset 0, the position of its first byte. If the red node \((g, \_, o)\) starts at byte \(o\), then by (a) its \(i\)-th child starts after the bytes of its children \(g_1, \dots, g_{i-1}\), whose widths sum to \(r_i\); so it starts at \(o + r_i\), which is what Child computes. Sharing does not interfere: the offset is a property of the path, not of the green node, which is why green nodes may be shared between positions (the eight LITERAL views in the box) and between versions of a file. (c) Only the ancestors of the replaced subtree have a changed child list; each is rebuilt once with the same children except one, \(d\) nodes in all; every other node's children are unchanged and are reused by identity (Lesson 4.6's ReplaceNode, and rust-analyzer's block reparse box).

Lowering CST → AST → HIR

Proposition 4.7.15 (LowerFor preserves the meaning of a Pebble loop)

LowerFor (Algorithm 4.7.10) preserves meaning (Definition 4.7.9) when every continue of the loop is lowered to a jump to the increment k = k &+ 1; lowering continue to a jump to the while test instead is wrong.

Proof

With \(\mathit{start} = a\), \(\mathit{end} = b\) evaluated once, the invariant of Algorithm 4.7.10 holds initially (\(k = \mathit{start}\), no iterations), and one iteration with \(k < \mathit{end}\) runs \(B\) with \(i = k\) and then sets \(k \leftarrow k + 1\) (no overflow, since \(k < \mathit{end} \le 2^{63} - 1\)), preserving it; a continue must still execute the increment, otherwise \(k\) is unchanged and the next iteration repeats \(i = k\) — the reason the spec says "a continue in B jumps to the increment" and pebblec keeps ForStmt in its AST instead of desugaring it in the parser. At exit \(k \ge \mathit{end}\), so the body has run for \(i = \mathit{start}, \dots, \mathit{end} - 1\) (none if \(\mathit{start} \ge \mathit{end}\)), as pebble-spec §7 requires.

Proposition 4.7.16 (A chain of meaning-preserving lowerings preserves meaning; each removes cases)

If \(\ell_1 : L_1 \to L_2\) and \(\ell_2 : L_2 \to L_3\) are meaning-preserving (Definition 4.7.9), so is \(\ell_2 \circ \ell_1\). If \(\ell_2\) is a desugaring whose image avoids the constructs \(X \subseteq L_2\), then every phase that consumes \(L_3\) needs no case for \(X\), and a property proved for all trees of \(L_3\) holds for the lowered image of every tree of \(L_1\).

Proof

\([\![\ell_2(\ell_1(t))]\!]_3 = [\![\ell_1(t)]\!]_2 = [\![t]\!]_1\) by the two hypotheses. A consumer of \(L_3\) only receives trees in the image of \(\ell_2\), in which no construct of \(X\) occurs, so a case for \(X\) would be dead. A property \(P\) proved for all of \(L_3\) holds in particular for \(\ell_2(\ell_1(t))\). This is the formal reason for rustc's HIR: the type checker is written once for loop and match, and is correct for for loops because lower_expr_for is.

5. Complexity

Let \(n\) be the number of nodes, \(k\) the number of node kinds, \(d\) the tree depth, and \(w\) the pointer width (8 bytes).

Technique	Build (per node)	Kind test / dispatch	Child access	Memory per node	Notes
Hierarchy + LLVM RTTI	\(O(1)\) (arena)	\(O(1)\): one or two compares (Theorem 4.7.11); switch = jump table	\(O(1)\) pointer	own fields + 1-byte kind + padding; Clang BinaryOperator 32 B	no vtable needed
std::variant	\(O(1)\) + a heap allocation per boxed child	\(O(1)\): std::visit jump table on index()	\(O(1)\) pointer	\(\max\) over alternatives + tag, rounded (Definition 4.7.3): 24 B in the box	every node pays for the largest alternative
Arena / index tree	\(O(1)\) amortized (vector::push_back) or \(O(1)\) bump	as for the node representation used	\(O(1)\) index + base	4-byte indices instead of \(w\)-byte pointers	Proposition 4.7.13: \(< 2T + 2S\) bytes
Red–green	\(O(1)\) per event; \(O(\text{arity})\) hashing for cached nodes	\(O(1)\) kind compare	\(O(1)\) via stored relative offsets; red nodes created lazily	green: kind, width, children with offsets; tokens interned	edits: \(O(d)\) new green nodes (Theorem 4.7.14)
Lowering CST → AST → HIR	\(O(n)\) per lowering pass	—	—	one extra tree per level (freed or kept by id maps)	desugaring grows a node into a constant number of nodes (for → block, match, loop, match, two arms)

Pathological cases. A std::variant whose largest alternative is large (say a 128-byte FunctionDecl next to 16-byte literals) multiplies memory by eight for the small nodes; box the large alternatives. An arena never frees, so a long-lived IDE process that rebuilds the tree on every keystroke must drop whole arenas (rust-analyzer's green nodes are reference-counted instead). Red nodes are cheap only while they are not kept: a query that materializes every red node doubles memory. Hash-consing with unbounded arity would hash every node, \(\Theta(n \cdot \text{arity})\) extra work, which rowan avoids with its three-children limit.

6. Variants and refinements

Class hierarchies with LLVM-style RTTI

• Tablegen'd node lists (Clang's StmtNodes.td, Pebble's ASTNodes.def): one list generates the kind enum, classof, visitors and dumpers — trade-off: an extra generator step, but adding a kind updates every switch.
• Virtual dispatch (virtual void accept(Visitor&) in every node class): trade-off: open to new node kinds without editing a switch, but one vtable pointer per node and no inlining.

Sum types with std::variant

• Struct + kind enum (rustc's Expr { id, span, kind: ExprKind }): shared fields outside the sum — trade-off: common data in one place, one more indirection level in patterns.
• Visitor over variant vs over hierarchy is the expression problem [Wad98]: variants make adding an operation easy and adding a kind hard (every visit must change), hierarchies with virtual methods the opposite.

Arena and index-based trees

• Typed indices per node kind (ExprId, StmtId in rust-analyzer's hir-def arenas; la-arena crate): trade-off: stronger types, several arrays.
• Struct-of-arrays node storage (Zig's self-hosted compiler stores AST node tags, main tokens and data in parallel arrays): trade-off: cache-friendly scans by kind, more index arithmetic.

Lossless red–green trees

• Trivia attached to tokens (Roslyn, SwiftSyntax: leading/trailing trivia fields instead of whitespace tokens): trade-off: fewer nodes, but the "which token owns this comment" rule must be designed ([RA-SyntaxDoc] discusses both).
• Arena-allocated raw nodes (SwiftSyntax's RawSyntax in a SyntaxArena [SWIFTSYNTAX-Arena]): green nodes are freed with their arena instead of reference-counted — trade-off: faster allocation, but a tree must not outlive its arena.

Lowering CST → AST → HIR

• Typed AST views over the CST (rust-analyzer's ast::BinExpr wraps a red node): no separate AST, just typed accessors — trade-off: every accessor searches the children; missing children are Option.
• Desugar in the parser (C compilers turning a[i] into *(a + i) early): trade-off: fewer node kinds, but diagnostics and IDE features lose the source form, which is why modern compilers desugar late.

7. In real compilers

Class hierarchies with LLVM-style RTTI

Clang: clang/include/clang/AST/Stmt.h, Expr.h (Expr::classof) and clang/include/clang/Basic/StmtNodes.td at llvmorg-23.1.2 [CLANG-Stmt, CLANG-StmtNodes]; the casting templates in llvm/include/llvm/Support/Casting.h [LLVM-Casting]; pebblec's pebble/include/pebble/AST/{Expr,Stmt,Decl}.h and ASTVisitor.h. The box after Algorithm 4.7.2 shows Clang's tree.

Sum types with std::variant

rustc's enum ExprKind in compiler/rustc_ast/src/ast.rs at 1.94.1 [RUSTC-AST]; OCaml's own compiler (Parsetree), GHC's HsSyn, and most compilers written in ML-family languages [ModernML]. The boxes after Algorithm 4.7.4 show std::visit and rustc's AST.

Arena and index-based trees

Clang and pebblec (ASTContext::create over llvm::BumpPtrAllocator [LLVM-Allocator]); rustc's HIR ids (compiler/rustc_hir_id/src/lib.rs [RUSTC-HirId]); the lab's Tree.h. The boxes after Algorithm 4.7.6 show Clang's slabs and rustc's HirIds.

Lossless red–green trees

Roslyn src/Compilers/Core/Portable/Syntax/GreenNode.cs and SyntaxNode.cs [ROSLYN-Green]; rowan src/green/node.rs, src/green/node_cache.rs, src/cursor.rs [ROWAN] with rust-analyzer's syntax design notes [RA-SyntaxDoc]; SwiftSyntax Sources/SwiftSyntax/Raw/RawSyntax.swift and SyntaxArena.swift [SWIFTSYNTAX-Arena]. The box after Algorithm 4.7.8 shows rowan's sharing.

Lowering CST → AST → HIR

rustc: compiler/rustc_ast_lowering/src/expr.rs (lower_expr_for) [RUSTC-Lower]; rust-analyzer lowers its CST to hir-def bodies; Swift lowers its AST to SIL, Kotlin its PSI to FIR. The box after Algorithm 4.7.10 shows rustc's HIR.

8. Comparison

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Class hierarchies with LLVM-style RTTI	Any node shape; open to new operations via visitors	\(O(1)\) kind tests · Clang nodes 16–32 B, 2 slabs for a small file	Exhaustiveness only via -Wswitch	Medium: node list + classof per class (generated)	Clang, LLVM IR, Swift, pebblec
Sum types with std::variant	Closed set of kinds, checked exhaustive case analysis	\(O(1)\) visit · every node sized to the largest alternative (24 B example)	Missing cases rejected at compile time (7 errors, library-deep)	Low in Rust/ML; medium in C++	rustc AST/HIR, OCaml, GHC
Arena and index-based trees	Any shape; ids usable as keys in side tables	\(O(1)\) bump allocation (Prop. 4.7.13) · 4-byte links	Stale indices are logic errors, not crashes	Low	Clang/pebblec arenas, rustc HirId, the lab's Tree.h
Lossless red–green trees	Every byte kept; shareable across versions	\(O(1)\) navigation, \(O(d)\) edits · 1+1 shared, 1 + 1 not	Error tokens stay in the tree (Lesson 4.6)	High: two layers, interning, typed views	Roslyn, rust-analyzer, SwiftSyntax
Lowering CST → AST → HIR	Each level fits one family of phases	\(O(n)\) per level	Diagnostics must map back through ids/spans	Medium per level	rustc, rust-analyzer, Swift, Kotlin

Choose a kind-tagged hierarchy when you write the compiler in C++ with LLVM and nodes have many different shapes. Choose sum types when your language checks exhaustiveness (Rust, OCaml) or the node set is small and closed. Choose arenas always for trees with a compilation-unit lifetime; choose indices when nodes are keys for many side tables or must be serialized. Choose red–green trees when an IDE, formatter or refactoring tool needs the exact text and incremental updates. Lower in stages when later phases would otherwise have to handle sugar again and again.

9. Assessment

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Class hierarchies with LLVM-style RTTI	rtti-interval, find-clang-stmt-new	—	ast-hierarchy	E1 (Pebble AST construction)
Sum types with std::variant	variant-size, expression-problem	—	sum-types	—
Arena and index-based trees	arena-slabs, index-postorder	—	arena	lab L1 (Tree.h-style tree of your design)
Lossless red–green trees	red-offset, green-sharing	—	red-green	—
Lowering CST → AST → HIR	for-desugar-continue, hir-for	—	lowering	—

These techniques are design choices, not algorithms with a unique trace, so there is no random drill; the quiz computes sizes, offsets and slab counts on concrete trees.

References

See the chapter references.