Semantic Analysis

Semantic Analysis

Who this is for: consumers querying scopes/symbols/references (start at The facade and result and Querying in API Reference) and engineers studying the resolver. Resolver container types and the checkRedeclarations pass breakdown are in Internals.

Semantic analysis builds the lexical scope tree, the symbol table, the reference table (with each reference resolved to its symbol), the control-flow graph, and per-node reachability. The core resolver does not walk the AST: it consumes the linear event stream the parser emits (scope_events.zig) in a single forward pass (event_resolver.zig). Two later post-passes do scan the AST — computeLoopBodyExitability (loop-exit reachability) and, when build_parents is set, buildParentsOnly — but the scope/symbol/reference/CFG construction is event-driven. The public facade is semantic.SemanticAnalyzer. (Note: the combined walk in the default path is single-threaded; a ScopeCfgParallel scope/CFG split exists but analyze does not use it.)

The facade and result

pub fn analyze(allocator, ast: *const Ast) !SemanticResult            // module mode
pub fn analyzeModule(allocator, ast, is_module: bool) !SemanticResult
pub fn analyzeWithGlobals(allocator, ast, globals: []const u8) !SemanticResult
pub fn analyzeWithOptions(allocator, ast, opts: Options) !SemanticResult

pub const SemanticAnalyzer.Options = struct {
    is_module: bool = true,
    globals: []const u8 = &.{},     // null-separated global names
    build_parents: bool = false,    // compute parent_indices on demand
    build_ref_ranges: bool = true,  // per-symbol reference ranges (getRefRange)
    need_cfg: bool = true,          // build the CFG + reachability
    diagnose_redeclare: bool = false,  // emit duplicate-binding early-errors
    annex_b: bool = true,
};

analyze* requires that the AST was parsed with event emission on; if ast.scope_events.len == 0 it returns error.MissingScopeEvents rather than a silently-empty result. (Parser.parse enables emission by default; a manual parseWithOptions must set emit_events = true or pass events_out.)

pub const SemanticResult = struct {
    scopes: ScopeTree,
    symbols: SymbolTable,
    references: ReferenceTable,
    diagnostics: []const Diagnostic = &.{},
    node_reachable: []u8 = &.{},        // 1 = live, 0 = dead
    loop_exit_reachable: []u8 = &.{},   // per-loop: is the loop exit reachable
    code_path_result: ?CodePathBuilder.Result = null,
    parent_indices: []const u32 = &.{}, // populated iff build_parents
    ref_by_sym: []const ReferenceId = &.{}, // populated iff build_ref_ranges
    pub fn deinit(self, allocator) void { … }
};

need_cfg = false skips the control-flow build (a substantial fraction of total analysis work). When it is off, node_reachable/loop_exit_reachable are empty (consumers bounds-check → treat all nodes as alive) and code_path_result is null. analyzeWithOptions runs resolveFull when CFG is needed, otherwise the scope-only resolveFullScope.

⚠️ Allocator contract. The analyzer reads sentinel-initialized scope/CFG buffers assuming freshly-allocated memory is zero. Pass an allocator that zero-fills new allocations: an ArenaAllocator over std.heap.page_allocator (zeroed OS pages — what the bundled runners use), or wrap any other allocator with semantic.ZeroingAllocator. A raw GeneralPurposeAllocator, or an arena over c_allocator (which hands back dirty reused blocks), can yield UB/crashes in ReleaseFast. This cannot be enforced by a runtime probe (Debug/ReleaseSafe poison-fill all fresh memory with 0xAA; ReleaseFast has no safety hook), so it is a caller contract.

The event stream

The parser emits a packed 8-byte Event (scope_events.zig):

pub const Event = packed struct(u64) { kind: EventKind, aux: u8, _pad: u16, node: u32 };

EventKind is the full control-and-binding alphabet: scope_open/scope_close, declare, reference, terminator (return/throw/break/continue), the branching families branch_*/if_*/cond_*/logical_*, the loop family loop_open/loop_test_end/loop_body_end/loop_close, try_*, switch_*, label_*, and nop (a neutralized event — used to cancel reference events that were speculatively emitted for would-be arrow parameters). aux carries the sub-kind (e.g. ScopeKind for scope_open, BindingKind for declare, ReferenceKind for reference). node is the NodeIndex; the resolver pulls names lazily from that node's main_token.

The resolver

event_resolver.resolveFullImpl parameterizes over a phase (both/scope_only/cfg_only). The default analyze path runs the both phase single-threaded. The scope and CFG halves can instead run on separate threads via the opt-in ScopeCfgParallel.start/.join (the library's only Thread.spawn, not invoked by analyze), stitched by combineParts, which aligns the two halves on the running count of .reference events (ScopePart.ref_event_to_id ↔ CfgPart.ref_event_seg_ids/ref_event_alive — both filled in identical event order, so index k aligns by construction), stamping each reference's seg_id and marking dead references' nodes unreachable.

Scope/symbol/reference construction (single pass)

The resolver keeps a small set of hot structures (exact types from the source):

It maintains a name-hash → currently-visible-symbol map (scope_map) fronted by a small direct-mapped L1 cache (ref_cache), a scope-keyed hoist_map for the retry pass, per-depth LIFO undo_stacks to restore visibility on scope exit, a sym_to_canonical map (so var/function redeclarations route to one symbol), and an unresolved_refs queue. (Exact container types and load factors: Internals.)

The main loop dispatches on EventKind:

• scope_open creates a ScopeTree entry of the event's ScopeKind under the current scope and pushes it; for var-scopes/functions it also pushes a code path onto the CFG builder.
• scope_close pops the scope and LIFO-restores scope_map and ref_cache from undo_stacks[depth] (re-inserting the previous binding for each shadowed name, or removing it).
• declare computes the hoist target (var / function_decl_annex_b climb to the nearest var-scope; everything else stays in the current scope), creates the symbol, inserts into scope_map + ref_cache, records the prior binding in undo_stacks, registers in hoist_map, and bumps the scope's binding count.
• reference appends to the ReferenceTable and tries to resolve immediately: check ref_cache[hash & 511], fall back to scope_map. A hit resolves to the canonical symbol and marks read/write/typeof; a miss is queued in unresolved_refs.

Reference resolution is therefore two-phase: an O(1) immediate resolve during the walk for already-visible bindings, then a retry pass over unresolved_refs that walks the var-scope ancestor chain via hoist_map (O(1) per level) to catch forward references to hoisted var/function bindings, then the lexical chain for forward let/const/class references captured in closures (const cb = () => { x = 1 }; let x;). References still unresolved after the retry are left with symbol_id = .none (potential globals, or genuinely undeclared).

Globals

opts.globals is a null-separated name list (ESLint's languageOptions.globals). After the main walk, a post-pass scans the still- unresolved references and, for any whose name matches a configured global, creates an implicit_global symbol in the global scope and resolves the reference to it — so globals resolve, but only where a real binding did not already (an existing local binding still wins).

The scope tree

scope.ScopeTree is a flat SoA tree (MultiArrayList(Entry)) addressed by ScopeId = enum(u32) (none = maxInt). It uses the classic left-child / right-sibling encoding (parent, first_child, last_child, next_sibling) so no per-scope heap allocation is needed. ScopeKind covers global, module, function, arrow_function, block, class, catch_clause, switch_stmt, static_block, with_stmt, class_field_initializer, and elided.

Flags are derived at addScope time from the kind and propagated:

• module and class scopes are always strict_mode; strictness is inherited downward at creation, so isStrictMode is a flag read, not an ancestor walk.
• function provides arguments and this; arrow_function is a var-scope but provides neither (inherited from the enclosing non-arrow function).
• static_block and class_field_initializer are strict var-scopes with this.
• Each entry caches var_scope (the nearest enclosing var-scope, self included), so nearestVarScope — the var-hoisting target — is O(1).
• elided is a block scope the parser emitted speculatively but that holds no block-scoped declarations; the resolver skips it (no ScopeId, no scope_close) and attributes its references to the enclosing scope.

Bindings are not stored on the scope; bindings_start/bindings_count index into the SymbolTable.

The symbol table

symbol.SymbolTable is SoA (MultiArrayList), SymbolId = enum(u32). Each entry: name (zero-copy slice into source), flags: SymbolFlags (packed u16: is_var/is_let/is_const/is_function/is_class/is_parameter/ is_catch_param/is_import/is_export/is_hoisted/is_written/is_read/ is_type_of/is_implicit_global/is_member_written/is_expr_name), binding_kind, scope_id, decl_node, and a ref_range into the per-symbol reference index.

Binding kinds and merging

BindingKind distinguishes var, let, const, function_decl, function_decl_annex_b (Annex B B.3.2.1-eligible function in an if/label body), class_decl, parameter, catch_param, import_binding, type_import_binding, implicit_global, the TS declaration kinds (type_decl, interface_decl, enum_decl, namespace_decl, type_param), and the named function/class-expression self-names (fn_expr_name, class_expr_name). It exposes hasTDZ() (true for let/const/class_decl), isHoisted() (var, both function kinds), isImmutable() (const, imports), and canRedeclare().

Note (verified against source): canRedeclare() is currently a predicate with no callers — TypeScript declaration merging is not achieved through it. The redeclaration check (checkRedeclarations) instead bails out wholesale for TypeScript input (if (ast.is_ts) return &.{};), so duplicate interface/namespace/enum/overload bindings simply never reach the check. A consequence: diagnose_redeclare produces no diagnostics on .ts/.tsx/ .d.ts ASTs.

The reference table

reference.ReferenceTable is SoA, ReferenceId = enum(u32). Each reference: symbol_id (.none until resolved), kind: ReferenceKind, node_id, scope_id, write_expr_id (the RHS for write/read-write refs, .none otherwise), and seg_id (the CFG segment, stamped during the parallel CFG join; maxInt(u32) if no path was active). ReferenceKind is read, write, read_write (x++, x += …), type_of, write_init (the initializing write of a declarator — counts as a write for liveness but does not set the symbol's is_written, so prefer-const-style rules can still see "never reassigned"), and type_read (a TS type-position use).

When build_ref_ranges is on, sortBySymbolWithMax groups references by symbol with a counting sort (O(n + k)), unresolved refs sorting to the end, and each symbol's ref_range is set to point into the resulting ref_by_sym array — so symbols.getRefRange(sym) yields a symbol's references in O(1).

Worked queries

Iterate every reference to a symbol, and classify it:

const range = sem.symbols.getRefRange(sym_id);          // needs build_ref_ranges
for (sem.ref_by_sym[range.start..range.end]) |ref_id| {
    const kind = sem.references.getKind(ref_id);         // .read / .write / .read_write / …
    const node = sem.references.getNode(ref_id);         // the identifier NodeIndex
    const live = sem.node_reachable.len == 0 or
                 sem.node_reachable[@intFromEnum(node)] != 0;  // empty ⇒ all-alive
    _ = .{ kind, live };
}

A symbol's declaration site is sem.symbols.getDeclNode(sym_id); its scope is getScope(sym_id). To list the symbols declared in a given scope, filter the table by scope (the scope's getBindingsCount gives the size, but the symbol table is in declaration order, so scan rather than slice):

for (sem.symbols.list.items(.scope_id), 0..) |sid, i|
    if (sid == scope_id) { const sym = symbol.SymbolId.fromInt(@intCast(i)); _ = sym; }

Early errors and reachability post-pass

When diagnose_redeclare is on, the resolver runs checkRedeclarations, a multi-pass duplicate-binding check (same-scope lexical duplicates, lexical-vs-var across the block/var-scope boundary, duplicate block functions with the Annex B B.3.3.4 exemption, parameter-vs-body, and catch-param-vs-var per B.3.5 — see Internals). It is opt-in because consumers with their own no-redeclare rule (a linter) handle it themselves; spec-conformance callers opt in.

After the CFG is built (need_cfg), semantic.computeLoopBodyExitability derives loop_exit_reachable: it walks each loop body to decide whether every path through it exits on the first iteration (so a no-unreachable-loop-style rule can fire), correctly handling break vs. continue vs. return/throw, switch fall-through, labeled statements, and infinite-empty-loop trapping. It also propagates unreachability to statements following a terminator or an infinite empty loop within a block, so reachability is marked on statement nodes, not just on the reference sub-nodes the resolver touched.

Parents (on demand)

Parent links are not stored on nodes and not built by the parser. When a consumer needs them, build_parents triggers parent_builder.buildParentsOnly(ast, allocator): a single forward scan that, for each node, writes itself as the parent of each child it owns (a tag-driven switch plus SubRange loops). Because every child index is less than its parent's index, one pass suffices. It then replays ast.parent_fixups — the small set of non-structural (child, parent) links the parser recorded for cases not derivable from tree structure (e.g. type annotations on destructured parameters/bindings, whose pattern node has no slot to hold them).

---

Next: Control-Flow Analysis · Performance and Concurrency