Lesson 5.6 — Where semantic results live: AST annotation, side tables, query-based incremental analysis, desugaring and HIR lowering¶

Techniques: annotating the AST in place (Clang, pebblec), side tables keyed by node identity (Go's types.Info, rustc's TypeckResults, CPython's symtable), query-based incremental semantic analysis with demand-driven memoization and red–green re-validation (rustc's query system; salsa, used by rust-analyzer; Swift's request evaluator; Roslyn's immutable compilations; Adapton, Hammer et al. 2014), and desugaring into a smaller core / HIR lowering (rustc AST → HIR; Clang's implicit variables for range-based for; Pebble's for-range → while scheme) · Pebble implements: annotation (NameExpr::setDecl, TypeRepr::setResolvedType, BreakStmt::setTarget; exercises E1–E3); the for desugaring of pebble-spec §7 is what Chapter 11's lowering does · Prerequisites: Lesson 4.7 (arenas, ids, CST → AST → HIR), Lesson 5.5 · Time: 3 hours

Name resolution produces facts — "this use denotes that declaration", "this type repr means [int; 3]", "this break leaves that loop" — and later phases consume them. Where those facts are stored is a design decision with long consequences: it decides whether the AST can be shared between threads or kept across edits, whether an IDE can answer a question without re-analyzing the whole file, and what a phase must do when the program changes. This lesson compares the three answers used in production — write into the tree, write into a map beside the tree, or compute on demand and memoize — and the companion technique of changing the tree itself into a simpler one (desugaring) so that later phases have less to understand.

1. Problem and motivation¶

The problem. A semantic phase computes a partial function from program entities (nodes, declarations, items) to facts. Choose a representation that later phases can read cheaply, that stays correct when the program changes, and that does not force later phases to understand every surface construct.

AST annotation¶

The simplest store is the tree: add a field to each node class and have the resolver fill it. Clang's DeclRefExpr holds a pointer to its ValueDecl, every Expr holds its QualType, and ImplicitCastExpr nodes are inserted where conversions happen; the resulting "semantic AST" is what CodeGen reads. pebblec does the same (NameExpr::getDecl(), Expr::getType()). The price: the AST is mutated after parsing, so it is not a pure function of the source text, it cannot be shared between two analyses that disagree, and every node pays for fields that only some analyses need.

Side tables¶

A side table maps node identities to facts and leaves the tree untouched: Go's type checker returns everything in a types.Info (Types, Defs, Uses, Scopes maps keyed by AST node) [GO-Info]; rustc's type check of a function body produces TypeckResults, maps keyed by HirId; CPython's compiler stores scope information in a symtable next to the AST. The tree stays immutable (and can be shared or cached), several analyses can coexist, and dropping a phase's results is dropping a map. The price is a hash lookup per access and the need for stable node identities (Lesson 4.7's arena indices, HirId).

Query-based incremental analysis¶

An IDE or an incremental compiler re-analyzes after every edit, and most facts do not change. Query-based compilers structure the whole front end as memoized functions ("queries") — type_of(def), resolve(module), typeck(fn) — that call each other on demand; the system records which queries each query read, and after an edit it re-validates cached results instead of recomputing them. rustc's query system with red–green marking [RUSTC-DevQueries, RUSTC-DevIncr], the salsa framework used by rust-analyzer [SALSA], Swift's request evaluator (with cycle detection between requests) [SWIFT-RequestEvaluator] and Roslyn's immutable, lazily bound compilations [ROSLYN-Overview] follow this design; its theory is demand-driven incremental computation (Adapton [HPHF14]) and, earlier, incremental attribute evaluation [RTD83].

Desugaring and HIR lowering¶

Instead of teaching every later phase every surface construct, a front end can desugar: rewrite constructs into combinations of simpler ones with the same meaning. rustc lowers its AST to HIR, turning for loops into loop + match on Iterator::next, while let into loop + match, and ? into a match (lower_expr_for in rustc_ast_lowering) [RUSTC-Lowering]; Clang keeps CXXForRangeStmt but builds the implicit __range, __begin and __end variables into it. Pebble's specification defines for i in a..b { B } by a while loop with fresh names (pebble-spec §7). The price is diagnostics: an error found after desugaring must still be reported in terms of what the user wrote, so desugared nodes keep the source spans (and a "desugaring kind") of the original.

2. Definitions and algorithms¶

Definition 5.6.1 (Semantic fact store)

Let \(\mathcal{E}\) be a set of program entities with stable identities (node pointers in an arena, indices such as HirId, or path-like ids such as rustc's DefPath). A fact store for a phase is a partial function \(F : \mathcal{E} \rightharpoonup V\). It is an annotation if \(F(e)\) is stored in the entity's own node, a side table if it is stored in a map from identities to \(V\) owned by the phase, and a query if \(F\) is computed on demand by a memoized function.

Definition 5.6.2 (Query system, revisions, dependency graph)

A query system consists of inputs \(\iota(k)\) (source files, configuration), set by the user, and derived queries \(q(k)\) defined by pure functions that may call other queries. A revision counter increases whenever an input changes. Executing a derived query records a dependency list: the queries it read, in order. Each memoized result carries the revision in which it was computed or last validated and a fingerprint (a hash of the value). A result is green (valid in the current revision) or red (recomputed and changed).

Algorithm 5.6.3 (Demand-driven memoized query with dependency recording)

Input: a query key \(q(k)\) and the current revision \(R\).
Output: its value.
Precondition: every query function is deterministic and reads the program only through queries.
Postcondition: the value equals a from-scratch computation in revision \(R\).
Invariant: active is the stack of queries being computed; a query found on it is a cycle.

function Get(q(k)):
    if q(k) ∈ active: report "cycle" (with the stack as the explanation)
    if memo[q(k)] exists and memo[q(k)].verified = R: return memo[q(k)].value
    if memo[q(k)] exists and TryMarkGreen(q(k)): return memo[q(k)].value
    push q(k) on active;  deps ← [];  v ← run q's function (each Get it makes is appended to deps)
    pop active
    changed ← (memo[q(k)] missing or fingerprint(v) ≠ memo[q(k)].fingerprint)
    memo[q(k)] ← {value: v, deps, verified: R, changedAt: R if changed else memo's old changedAt}
    return v

Algorithm 5.6.4 (Red–green re-validation, try_mark_green)

Input: a query \(q(k)\) with a memo from an earlier revision.
Output: true if the memo is still valid in revision \(R\) (and marks it verified), false otherwise.
Precondition: inputs record changedAt, the revision of their last change.
Postcondition: returns true only if recomputing \(q(k)\) now would give a value with the same fingerprint (Theorem 5.6.8).
Invariant: dependencies are examined in the order they were read, so every dependency examined was read under the same earlier values as last time.

function TryMarkGreen(q(k)):
    m ← memo[q(k)]
    for d in m.deps, in order:
        if d is an input:
            if d.changedAt > m.verified: return false
        else:
            if memo[d].verified ≠ R and not TryMarkGreen(d):
                Get(d)                                   # recompute d (may turn it red)
            if memo[d].changedAt > m.verified: return false   # d is red: q must rerun
    m.verified ← R                                         # all dependencies green
    return true

Definition 5.6.5 (Desugaring)

Let \(L\) be a surface language and \(L_0 \subseteq L\) a core sublanguage with meaning \([\![\cdot]\!]\). A desugaring is a function \(\delta : L \to L_0\) defined construct by construct, such that \([\![\delta(t)]\!] = [\![t]\!]\) for every program \(t\). HIR lowering is a desugaring into a separate, smaller tree type (the HIR), usually combined with name resolution (the HIR refers to declarations by id rather than by name).

Algorithm 5.6.6 (Desugaring Pebble's for into while, pebble-spec §7)

Input: a statement for i in a..b { B }.
Output: an equivalent block in the while core.
Precondition: \(s\), \(e\), \(k\) are fresh: not writable in Pebble source (so they can neither capture nor be captured, as in Lesson 5.4's hygiene); \(B\) has been resolved, so its break/continue targets are known.
Postcondition: the output runs \(B\) with \(i = a, a+1, \dots, b-1\) and has the same effect as the loop (Theorem 5.6.9).
Invariant: at the start of each iteration, \(k\) holds the next value of \(i\) and \(s \le k\).

function DesugarFor(i, a, b, B):
    return {
        let s = a;                   # evaluate the bounds once, left to right
        let e = b;
        var k = s;
        while k < e {
            let i = k;               # a fresh immutable i per iteration
            B'                       # B with every `continue` targeting this loop
                                     #   replaced by `k = k &+ 1; continue;`
            k = k &+ 1;
        }
    }

3. Worked example¶

AST annotation¶

For fn f(n: int) -> int { let m = n; return m; }, resolveNames writes three annotations: the NameExpr n points to the ParamDecl, the NameExpr m to the VarDecl, and the two NamedTypeReprs int to the uniqued int type. ch05-resolve prints them (with an E0311 for the missing main, which does not matter here):

node	field written	value
`NamedTypeRepr int` (parameter)	`ResolvedType`	`int`
`NamedTypeRepr int` (result)	`ResolvedType`	`int`
`NameExpr n`	`Decl`	`ParamDecl n`
`NameExpr m`	`Decl`	`VarDecl m`

Side tables¶

The same facts as a side table (what Go's types.Info.Uses would hold, and what the reference ch05-resolve dump is):

key (node id = position)	value
1:9 (`int`)	builtin int
1:17 (`int`)	builtin int
1:31 (`n`)	`param n@1:6`
1:41 (`m`)	`let m@1:27`

Query-based incremental analysis¶

A query graph for a two-function file, and what happens after an edit inside g's body that does not change its signature:

flowchart LR
  SRC([source text]) --> PARSE[parse]
  PARSE --> ITEMS["items: signatures of f, g"]
  PARSE --> BF["body(f)"]
  PARSE --> BG["body(g)"]
  ITEMS --> RF["resolve(f)"]
  BF --> RF
  ITEMS --> RG["resolve(g)"]
  BG --> RG
  RF --> TF["check(f)"]
  RG --> TG["check(g)"]

check(f) was computed in revision 1 with dependencies in the order [resolve(f)], and resolve(f) with [items, body(f)]. The user edits g's body (revision 2) and asks for check(f) and check(g):

step	query	action (Algorithm 5.6.4)	color
1	check(f)	TryMarkGreen: first dependency resolve(f) is not verified in rev 2 → TryMarkGreen(resolve(f))
2	resolve(f)	first dependency `items`: not verified → TryMarkGreen(items)
3	items	dependency `parse` not verified → TryMarkGreen(parse): its input `source` changed in rev 2 → false; recompute parse (new tree)	parse red
4	items	parse is red → recompute items: same signatures, same fingerprint → `changedAt` stays 1	items green (early cutoff)
5	resolve(f)	items green; next dependency body(f): recompute from the new parse, same fingerprint	body(f) green
6	resolve(f)	all dependencies green → mark verified, reuse	resolve(f) green
7	check(f)	dependency green → reuse	check(f) green
8	check(g)	resolve(g) → body(g) recomputed: fingerprint changed → resolve(g) recomputed → check(g) recomputed	red

Only the parse, the two cheap projections and g's analyses ran again; f's resolution and checking were re-validated without running. Step 4 is the early cutoff: a recomputed query whose value did not change stops the invalidation from spreading.

Desugaring and HIR lowering¶

Algorithm 5.6.6 on for i in 0..3 { if i == 1 { continue; } print(i); }:

{
    let s = 0;
    let e = 3;
    var k = s;
    while k < e {
        let i = k;
        if i == 1 { k = k &+ 1; continue; }
        print(i);
        k = k &+ 1;
    }
}

iteration	\(k\) at the test	`i`	effect	\(k\) after
1	0	0	prints 0	1
2	1	1	`continue`: skips the print, but increments first	2
3	2	2	prints 2	3
exit	3		\(3 < 3\) is false

A naive rewrite that kept continue unchanged would jump to the test without incrementing and loop forever at \(k = 1\): the reason the algorithm rewrites continue (and why Pebble's spec says "a continue in B jumps to the increment").

Try it

Run build/<preset>/bin/ch05-resolve tests/ch05/Inputs/scopes.pbl and read the output as a side table keyed by position. There is no drill for this lesson; the quiz items red-green-trace and desugar-continue are traces of the kind above.

4. Invariants and correctness¶

AST annotation¶

Correctness of annotation is correctness of the phase that writes it (Lessons 5.1–5.3), plus one structural rule: every node is annotated at most once, by one phase, and later phases only read. The reference solution follows it: resolveNames writes Decl, ResolvedType and loop targets; the type checker (Chapter 6) writes only Type. A phase that re-runs on the same tree must reset what it wrote, or annotation becomes a source of stale facts — the main reason IDE front ends prefer side tables or queries.

Side tables¶

Proposition 5.6.7 (Side tables are equivalent to annotations and keep the tree immutable)

For any annotation-writing phase \(\Phi\) there is a side-table phase \(\Phi'\) that reads the same inputs and writes \(F'(\mathrm{id}(n)) = F(n)\) for every annotated node \(n\); every later phase that reads \(F(n)\) gives the same results when it reads \(F'(\mathrm{id}(n))\) instead, provided identities are injective.

Proof

Define \(\Phi'\) as \(\Phi\) with each write "\(n.\mathit{field} := v\)" replaced by "\(\mathit{table}[\mathrm{id}(n)] := v\)", and each read replaced likewise. Injectivity makes the table a function on nodes, so every read returns the value the corresponding field would hold at that point (by induction on the sequence of reads and writes, which is the same in both versions). The tree is never written by \(\Phi'\).

Query-based incremental analysis¶

Theorem 5.6.8 (Red–green re-validation is from-scratch consistent)

Suppose every derived query is a deterministic function of the values of the queries it reads, and fingerprints are injective on the values that occur (no collisions). If TryMarkGreen(q(k)) returns true in revision \(R\), then recomputing \(q(k)\) from scratch in revision \(R\) yields a value with the memoized fingerprint.

Proof

By induction on the depth of \(q(k)\) in the dependency graph (the graph is acyclic: a cycle is reported by Algorithm 5.6.3). Let \(d_1, \dots, d_m\) be the recorded dependencies, read in this order when \(q(k)\) was last computed or validated (revision \(R_0 = m.\mathit{verified}\)). The function is deterministic, so its execution, and hence the next query it reads, depends only on the values read so far. TryMarkGreen returns true only if, for each \(d_j\) in order, \(d_j\)'s value has not changed since \(R_0\): inputs by their changedAt; derived queries because they were validated (green, by the induction hypothesis their current value equals the one from revision \(R_0\)) or recomputed with an unchanged fingerprint (so an equal value, by injectivity). Then a from-scratch execution in revision \(R\) reads \(d_1\) first (same as before), gets the same value, therefore reads \(d_2\) next, and so on: it follows the same path, reads the same values, and returns the same result — with the memoized fingerprint.

Why dependencies are checked in order

If q is if a() { b() } else { c() } and a changed from true to false, the recorded dependencies are [a, b]. Checking them in order stops at a (changed) and reruns q, which now reads c. Checking b first could find it green and wrongly conclude that q is green: the order is what makes the induction work.

Desugaring and HIR lowering¶

Theorem 5.6.9 (The for desugaring preserves meaning)

Let for i in a..b { B } evaluate \(a\) to \(\alpha\) and \(b\) to \(\beta\). Its desugaring by Algorithm 5.6.6 evaluates \(a\) and \(b\) once, in this order, and then runs \(B\) with \(i = \alpha, \alpha + 1, \dots, \beta - 1\) in order (zero times if \(\alpha \ge \beta\)), leaving the loop exactly when the original leaves it (the bound is reached, a break, or a return), with the same effects.

Proof

Bounds: let s = a; let e = b; evaluate them once, left to right; \(s, e\) are fresh and immutable, so nothing in \(B\) can change them. Loop invariant: at the \(j\)-th evaluation of the test (\(j \ge 0\)), \(k = \alpha + j\) and the body has run exactly for \(\alpha, \dots, \alpha + j - 1\). It holds for \(j = 0\). If the test \(k < e\) succeeds, the body binds a fresh i = k \(= \alpha + j\) and runs \(B'\). \(B'\) differs from \(B\) only at continue statements targeting this loop, each preceded by the increment, and \(B'\) falls off its end into the increment otherwise; either way \(k\) becomes \(\alpha + j + 1\) before the next test (no overflow: \(k < e \le 2^{63} - 1\), so &+ equals +). break and return leave the while exactly as they leave the for. continues of inner loops are untouched because \(B\) was resolved first and only this loop's targets are rewritten. Termination of the iteration: the test fails when \(k = \beta\) (or immediately if \(\alpha \ge \beta\)). Hygiene: since \(s\), \(e\), \(k\) are not source names, no use in \(B\) refers to them and no declaration in \(B\) shadows them, so \(B'\) sees exactly the bindings \(B\) saw (with i the fresh per-iteration binding, as the original's scoping says).

5. Complexity¶

Variables: \(n\) nodes, \(f\) facts per node on average, \(q\) queries executed, \(e_d\) recorded dependency edges, \(c\) the size of the change after an edit.

Technique	Time per access	Space	Cost after an edit	Pathological case
AST annotation	\(O(1)\), a field load	\(O(n f)\) inside the nodes; every node pays for every field	re-run the phase on the changed tree (whole function or file)	many optional facts: memory for unused fields
Side tables	\(O(1)\) expected hash lookup	\(O(\text{facts})\) only where present	drop and recompute the table	hashing overhead in hot loops (rustc's `FxHash` exists for this)
Queries (Alg. 5.6.3–5.6.4)	\(O(1)\) for a verified memo	\(O(q + e_d)\) memo + dependency graph	\(O(\text{dependencies re-validated} + \text{queries recomputed})\), proportional to what the change affects	an early, widely read query whose value changes (e.g., a crate-wide item list) re-runs everything below it
Desugaring	— (a transformation)	\(O(n)\) for the new tree (HIR is usually smaller)	redo for the changed item	constructs that expand to large code (C++ coroutines, Swift result builders)

Justification. Algorithm 5.6.4 visits each recorded dependency of a query at most once per revision (a query is marked verified the first time it is validated), so re-validation is linear in the part of the dependency graph reachable from the requested queries; recomputation happens only for red queries and the queries that read them before an early cutoff. rustc reports that incremental rebuilds after small edits re-use most query results; the -Z self-profile and -Z incremental-info flags (nightly) show the counts [RUSTC-DevIncr].

AST annotation¶

Two trees instead of annotating one: Clang's semantic AST differs from the syntactic one only by inserted implicit nodes (casts, temporaries), so "annotation" includes adding nodes.
Arena + indices (Lesson 4.7) make annotations cheap to clear: facts live in parallel arrays indexed by node id — halfway to side tables.

Side tables¶

Per-owner tables (rustc's TypeckResults per function body) bound the size of a table and make it a unit of caching.
Weak/identity-keyed maps (JavaScript WeakMap, Java IdentityHashMap) let tables be attached to nodes without changing the node class, and be collected with the tree.

Query-based incremental analysis¶

Red–green with fingerprints (rustc) vs salsa's durability levels and revision checks: salsa records the revision at which each input changed and skips re-validating queries that only depend on "durable" inputs (the standard library) [SALSA].
Request evaluator (Swift): requests are memoized per key and cycle detection reports a cycle between requests as a diagnostic instead of a stack overflow [SWIFT-RequestEvaluator].
Immutable snapshots (Roslyn): each edit creates a new Compilation sharing unchanged syntax trees and lazily computed symbols; semantic models are computed on demand per tree [ROSLYN-Overview].

Desugaring and HIR lowering¶

Keep the sugar and lower later (Clang keeps CXXForRangeStmt for tools and diagnostics, but adds the implicit variables inside it) vs desugar early (rustc's HIR has no for).
Desugaring kinds on spans: rustc marks spans produced by lowering with a DesugaringKind (ForLoop, QuestionMark, Await) so that diagnostics can say "in this for loop" and lints can ignore generated code.

7. In real compilers¶

AST annotation¶

Clang annotates in place: Sema builds DeclRefExprs that point to the resolved declaration and sets every expression's type (clang/lib/Sema/SemaExpr.cpp, Sema::BuildDeclRefExpr, LLVM 23.1.2 [CLANG-SemaExpr]). pebblec does the same through the setters in pebble/include/pebble/AST/Expr.h.

Clang 23's semantic AST: bindings, types and inserted conversions

Reproduce (clang 23.1.2; node addresses renumbered by the perl filter):

cat > annot.c <<'EOF'
double scale(int n) { return n * 1.5; }
EOF
clang-23 -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics annot.c 2>&1 \
  | sed -n '/FunctionDecl.*scale/,$p' | perl -pe 's/0x[0-9a-f]+/$h{$&}||=("#".++$n)/ge'

Output (complete):

`-FunctionDecl #1 <annot.c:1:1, col:39> col:8 scale 'double (int)' external-linkage
  |-ParmVarDecl #2 <col:14, col:18> col:18 used n 'int'
  `-CompoundStmt #3 <col:21, col:39>
    `-ReturnStmt #4 <col:23, col:34>
      `-BinaryOperator #5 <col:30, col:34> 'double' '*'
        |-ImplicitCastExpr #6 <col:30> 'double' <IntegralToFloating>
        | `-ImplicitCastExpr #7 <col:30> 'int' <LValueToRValue>
        |   `-DeclRefExpr #8 <col:30> 'int' lvalue ParmVar #2 'n' 'int'
        `-FloatingLiteral #9 <col:34> 'double' 1.500000e+00

What to notice: three kinds of annotation in one tree: the binding (DeclRefExpr #8 → ParmVar #2), a type on every expression ('int', 'double'), and two inserted nodes (ImplicitCastExpr) that the source does not contain. The parser built n * 1.5; Sema rewrote and annotated it in place.

Side tables¶

Go: types.Info with its Types, Defs, Uses, Implicits, Selections and Scopes maps (src/go/types/api.go, go1.24.7 [GO-Info]). rustc: TypeckResults holds per-body maps keyed by HirId (compiler/rustc_middle/src/ty/typeck_results.rs, rustc 1.94.1 [RUSTC-TypeckResults]). CPython: the symtable built by Python/symtable.c is consulted by the code generator without annotating the AST [CPY-Symtable].

Go 1.24's types.Info: every result in a map beside an immutable AST

Reproduce (go 1.24.7):

mkdir -p goside && cd goside && go mod init goside >/dev/null 2>&1
cat > main.go <<'EOF'
package main

import (
    "fmt"
    "go/ast"
    "go/parser"
    "go/token"
    "go/types"
    "sort"
)

const src = `package p

func scale(n int) float64 {
    k := 1.5
    return float64(n) * k
}
`

func main() {
    fset := token.NewFileSet()
    file, _ := parser.ParseFile(fset, "p.go", src, 0)
    // The AST is never modified: every result goes into a side table keyed by AST node.
    info := &types.Info{
        Types: map[ast.Expr]types.TypeAndValue{},
        Defs:  map[*ast.Ident]types.Object{},
        Uses:  map[*ast.Ident]types.Object{},
    }
    if _, err := new(types.Config).Check("p", fset, []*ast.File{file}, info); err != nil {
        panic(err)
    }
    var lines []string
    for e, tv := range info.Types {
        if _, isIdent := e.(*ast.Ident); isIdent || tv.IsType() {
            continue
        }
        lines = append(lines, fmt.Sprintf("Types[%v %q] = %v", fset.Position(e.Pos()), types.ExprString(e), tv.Type))
    }
    for id, obj := range info.Defs {
        if obj != nil {
            lines = append(lines, fmt.Sprintf("Defs[%v %s] = %v", fset.Position(id.Pos()), id.Name, obj))
        }
    }
    for id, obj := range info.Uses {
        lines = append(lines, fmt.Sprintf("Uses[%v %s] = %v", fset.Position(id.Pos()), id.Name, obj))
    }
    sort.Strings(lines)
    for _, l := range lines {
        fmt.Println(l)
    }
}
EOF
go run .

Output (complete):

Defs[p.go:3:12 n] = var n int
Defs[p.go:3:6 scale] = func p.scale(n int) float64
Defs[p.go:4:2 k] = var k float64
Types[p.go:4:7 "1.5"] = float64
Types[p.go:5:9 "float64(n) * k"] = float64
Types[p.go:5:9 "float64(n)"] = float64
Uses[p.go:3:14 int] = type int
Uses[p.go:3:19 float64] = type float64
Uses[p.go:5:17 n] = var n int
Uses[p.go:5:22 k] = var k float64
Uses[p.go:5:9 float64] = type float64

What to notice: the same kinds of facts as Clang's semantic AST — declarations, uses and expression types — but stored in three maps keyed by AST node (Definition 5.6.1); the ast.File is exactly what the parser produced, so another tool can type-check the same tree with different settings.

Query-based incremental analysis¶

rustc: every analysis is a query declared in compiler/rustc_middle/src/query/mod.rs; the dependency graph and try_mark_green (Algorithm 5.6.4) live in compiler/rustc_query_system/src/dep_graph/graph.rs (rustc 1.94.1 [RUSTC-DepGraph]); the incremental cache is saved in the -C incremental directory between runs. Swift: Evaluator::operator() evaluates and caches requests and reports cycles (lib/AST/Evaluator.cpp, swift-6.1-RELEASE [SWIFT-Evaluator]). salsa 0.23 (salsa-rs/salsa, tag salsa-v0.23.0) implements revisions, durability and early cutoff for rust-analyzer [SALSA].

rustc 1.94 persists its query results and dependency graph between runs

Reproduce (rustc 1.94.1; the sed hides the crate and session hashes, which vary):

printf 'pub fn a() -> u32 { 1 }\npub fn b() -> u32 { a() + 1 }\n' > q.rs
rustc --edition 2021 --crate-type=lib -C incremental=inc q.rs
find inc -type f -name '*.bin' | sed -E 's#q-[^/]+#q-<crate>#; s#s-[^/]+#s-<session>#' | sort

Output (complete):

inc/q-<crate>/s-<session>/dep-graph.bin
inc/q-<crate>/s-<session>/query-cache.bin
inc/q-<crate>/s-<session>/work-products.bin

What to notice: dep-graph.bin is the recorded dependency graph of Definition 5.6.2 (with fingerprints), query-cache.bin the memoized results that the next compilation can mark green instead of recomputing (Algorithm 5.6.4), and work-products.bin the codegen units that can be reused. A second rustc with the same -C incremental=inc after an edit re-validates against this session.

Desugaring and HIR lowering¶

rustc: LoweringContext::lower_expr_for turns for pat in expr { body } into match IntoIterator::into_iter(expr) { mut iter => loop { match Iterator::next(&mut iter) { None => break, Some(pat) => body } } } (compiler/rustc_ast_lowering/src/expr.rs, rustc 1.94.1 [RUSTC-Lowering]). Clang: Sema::BuildCXXForRangeStmt creates the implicit __range, __begin, __end variables (clang/lib/Sema/SemaStmt.cpp, LLVM 23.1.2 [CLANG-SemaStmt]).

The desugared for loop in rustc 1.94's MIR, and Clang 23's range-for variables

Reproduce (rustc 1.94.1, clang 23.1.2; -Z unpretty=hir needs a nightly compiler, so the box shows MIR, which is built from the HIR):

cat > forloop.rs <<'EOF'
pub fn sum(n: u64) -> u64 {
    let mut s = 0;
    for i in 0..n {
        s += i;
    }
    s
}
EOF
rustc --edition 2021 --crate-type=lib -C opt-level=0 -C overflow-checks=off --emit=mir -o forloop.mir forloop.rs
sed -n '4,60p' forloop.mir
cat > rangefor.cpp <<'EOF'
int sum(const int (&xs)[4]) {
  int s = 0;
  for (int x : xs) s += x;
  return s;
}
EOF
clang++-23 -std=c++20 -fsyntax-only -Xclang -ast-dump -fno-color-diagnostics rangefor.cpp 2>&1 \
  | grep -E "CXXForRangeStmt|VarDecl.*(__range|__begin|__end| x )" | sed -E 's/0x[0-9a-f]+ //; s/<[^>]*> //'

Output (complete):

fn sum(_1: u64) -> u64 {
    debug n => _1;
    let mut _0: u64;
    let mut _2: u64;
    let mut _3: std::ops::Range<u64>;
    let mut _4: std::ops::Range<u64>;
    let mut _6: std::option::Option<u64>;
    let mut _7: &mut std::ops::Range<u64>;
    let mut _8: isize;
    scope 1 {
        debug s => _2;
        let mut _5: std::ops::Range<u64>;
        scope 2 {
            debug iter => _5;
            let _9: u64;
            scope 3 {
                debug i => _9;
            }
        }
    }

    bb0: {
        _2 = const 0_u64;
        _4 = std::ops::Range::<u64> { start: const 0_u64, end: copy _1 };
        _3 = <std::ops::Range<u64> as IntoIterator>::into_iter(move _4) -> [return: bb1, unwind continue];
    }

    bb1: {
        _5 = move _3;
        goto -> bb2;
    }

    bb2: {
        _7 = &mut _5;
        _6 = <std::ops::Range<u64> as Iterator>::next(copy _7) -> [return: bb3, unwind continue];
    }

    bb3: {
        _8 = discriminant(_6);
        switchInt(move _8) -> [0: bb6, 1: bb5, otherwise: bb4];
    }

    bb4: {
        unreachable;
    }

    bb5: {
        _9 = copy ((_6 as Some).0: u64);
        _2 = Add(copy _2, copy _9);
        goto -> bb2;
    }

    bb6: {
        _0 = copy _2;
        return;
    }
}
    |-CXXForRangeStmt <line:3:3, col:25>
    | | `-VarDecl col:16 implicit used __range1 'const int (&)[4]' cinit
    | | `-VarDecl col:14 implicit used __begin1 'const int *' cinit
    | | `-VarDecl col:14 implicit used __end1 'const int *' cinit
    | | `-VarDecl col:12 used x 'int' cinit

What to notice: nothing called "for" survives in the MIR: there is a hidden iter variable (_5, the compiler-generated name of the desugaring, which user code cannot reference: Algorithm 5.6.6's freshness), a call to into_iter once, a loop header calling next (bb2), and a match on Some/None (bb3). The nested scopes are the HIR's scopes: i lives in scope 3, inside the scope of iter — one fresh i per iteration, as in Pebble. Clang instead keeps the CXXForRangeStmt node and adds three implicit variables to it: desugaring by annotation.

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
AST annotation	Any fact, stored where it is used; one version of the tree at a time	\(O(1)\) field access · the fastest	Diagnostics read facts directly from nodes	Lowest	Clang, GCC, `pebblec`, most batch compilers
Side tables	Same facts (Proposition 5.6.7), several analyses side by side, immutable tree	\(O(1)\) expected hash lookup	Same	Low; needs stable node ids	Go `types.Info`, rustc `TypeckResults`, CPython `symtable`, analyzers
Query-based incremental analysis	Same facts, computed on demand, re-validated after edits (Theorem 5.6.8)	Proportional to what an edit affects; overhead of recording dependencies	Cycles become diagnostics (Swift); consistent results across edits	High: every phase must be a pure query	rustc, rust-analyzer (salsa), Swift, Roslyn
Desugaring and HIR lowering	Fewer constructs for later phases; meaning preserved (Theorem 5.6.9)	\(O(n)\) per lowering	Needs desugaring-aware spans, or errors mention generated code	Medium per construct	rustc HIR, Kotlin, Swift SIL generation, Pebble's `for` (Ch 11)

Choose annotation for a batch compiler that analyzes each file once. Choose side tables when the tree must stay immutable or be shared (tools, parallel analyses, several configurations). Choose queries when the compiler also serves an IDE or must be incremental; design every phase as a pure function from the start, because retrofitting is expensive (rustc's multi-year migration). Desugar a construct when later phases would otherwise duplicate its logic and the core form expresses it exactly; keep its source spans.

9. Assessment¶

Technique	Quiz ids	Drill	Flashcard tag	Exercises
AST annotation	`annotation-fields`, `find-clang-declrefexpr`	— (E1–E3 write the annotations; the tests read them)	`ast-annotation`	E1–E3
Side tables	`side-table-equivalence`, `go-info-maps`	—	`side-tables`	— (the `ch05-resolve` dump is one)
Query-based incremental analysis	`red-green-trace`, `early-cutoff`	— (quiz traces; a drill would need a query engine)	`query-incremental`	—
Desugaring and HIR lowering	`desugar-continue`, `rust-for-mir`	—	`desugaring`	Ch 11 lowers `for` this way

References¶

See the chapter references.

Lesson 5.6 — Where semantic results live: AST annotation, side tables, query-based incremental analysis, desugaring and HIR lowering¶

1. Problem and motivation¶

AST annotation¶

Side tables¶

Query-based incremental analysis¶

Desugaring and HIR lowering¶

2. Definitions and algorithms¶

3. Worked example¶

AST annotation¶

Side tables¶

Query-based incremental analysis¶

Desugaring and HIR lowering¶

4. Invariants and correctness¶

AST annotation¶

Side tables¶

Query-based incremental analysis¶

Desugaring and HIR lowering¶

5. Complexity¶

6. Variants and refinements¶

AST annotation¶

Side tables¶

Query-based incremental analysis¶

Desugaring and HIR lowering¶

7. In real compilers¶

AST annotation¶

Side tables¶

Query-based incremental analysis¶

Desugaring and HIR lowering¶

8. Comparison¶

9. Assessment¶

References¶