Thamirawaran

Engineering / Compilers / Languages

Program Analysis in the Jac Compiler

Rebuilding how the Jac compiler maps the paths a program can take (its control-flow graph), and making the type errors built on that map more precise.

Problem The compiler’s map of the paths a program can take was wrong for several common statements, so the errors and warnings built on it were wrong too.

abbodyelseTTFF · skips b
Schematic

Overview

Jac is an open-source, Python-like programming language from Jaseci Labs. Its compiler works in a sequence of passes over the program’s syntax tree. One of those passes builds the control-flow graph (CFG): blocks of code and the paths execution can take between them. Nobody reads the CFG directly. Reachability checks, type narrowing and language-server diagnostics all use it, so an error in the graph later appears as a wrong diagnostic somewhere else.

Problem

The existing CFGBuildPass kept a to_connect worklist and separate loop stacks, and connected blocks as it went. That design broke on the constructs with the most complex control flow:

  • boolean conditions were a single node, so if a and b had no record that b only runs when a is true;
  • try / except / finally, with, match and switch had no explicit edge building;
  • raise and disengage were not treated as terminal, so code after them looked reachable;
  • an if with an else produced a spurious edge to its next sibling.

Architecture

The pass was rewritten as a stateless entry/exit visitor. Each statement kind describes its own entry block and the set of exits it leaves open, through twenty type-specific exit handlers, and a parent statement wires its children’s exits together. There is no global worklist, so a nested construct cannot leave stale state for the next statement.

Several AST nodes had to change status for this to work: MatchCase, SwitchCase and Test were promoted to code-block statements, and BoolExpr to a CFG node, so they appear in the graph as nodes of their own.

Control-flow graph for "if a and b", before and after short-circuit wiringBefore: a single condition node "a and b" branches to the body or the else block. After: node "a" branches on false directly to the else block, and on true to node "b", which then branches to the body or the else block.BEFOREa and bbodyelseTFAFTERabbodyelseTTFF · b never runs
The condition if a and b. Before, it is one opaque node. After, each operand is a branch point, so the graph records that b only runs when a is true. Analyses that read the graph, such as narrowing, can then rely on a being true inside b.

Key engineering decisions

  • Short-circuit wiring. Conditions are wired per operand (_wire_bool_condition), so a and b becomes two branch points. Narrowing can then rely on the left operand being true while it checks the right one.
  • Unreachable code keeps its own block. Code after a terminal statement goes into a separate basic block with no incoming edges. Diagnostics can still point at it, and the graph marks it as unreachable.
  • Known gaps listed in the PR. Conditional expressions, the safe-call operator, comprehensions and switch fall-through were recorded as follow-up work.

Type analysis on top

Two related changes made the type checker’s reports more precise:

  • Union member access (#5010). Accessing x.attr on a union used to return UnknownType silently when a variant lacked the attribute. It now reports an error naming which variants are missing it.
  • Union and special-form narrowing (#4951, co-authored) extended which checks narrow a union to a specific member.

Validation

Seven new CFG fixtures cover the shapes the old pass got wrong: cfg_bool_expr, cfg_for_else, cfg_match, cfg_nested_if, cfg_nested_loop, cfg_raise and cfg_try_except.

Evidence

All engineering