path: root/graph/README.md

# Shared graph viewer

The browser application lives in `web/` and is shared by chapters 4 and 18–25.
`web/index.html` contains the page and `web/viewer.js` manages playback.
`web/layout.js` runs ELK layout in a browser worker; `web/render.js` draws SVG
and handles selection, pan and zoom. `web/legacy.js` loads Graphviz on demand
for earlier chapters. Libraries live in `web/vendor/`, with one checked-in
copy of each; chapters do not copy them during builds.

From a chapter directory, run `make view`. For chapters 4 and 25, the shared
`GraphViewer` finds
`graph/web/index.html` by walking up from the working directory, serves its
directory through the JDK's HTTP server on a local ephemeral port, and opens
that web address in the browser. This works from a chapter directory, the
repository root, or the root of a linearized checkout. Java launches from elsewhere can specify
`-Dsimple.graph.url=<viewer URL>` before the main class.

The viewer uses a WebSocket connection. Chapters 4 and 25 send structured
JSON snapshots in each frame; chapters 18–24 still send bare DOT.
No JavaScript package installation, frontend build, or separate server process
is required.
For development over HTTP, run this from the repository root:

```sh
python -m http.server 8000 --bind 127.0.0.1 --directory graph/web
```

Then launch Java with `-Dsimple.graph.url=http://127.0.0.1:8000/index.html`.
The compiler WebSocket still uses port 12345; run one viewer session at a time.

The initial program compiles on connection. For another program, click **Compile**
or press **Ctrl+Enter** (**Cmd+Enter** on macOS), then use the arrows to step
through the captured frames. Keep `make view` running while using the tab.

In chapters 4 and 25, scroll to zoom, drag to pan, and use **Fit** to show the whole
graph again. Clicking a node shows its full label, type and input slots, and
highlights its edges. Selection follows that node's ID across frames; Escape
clears it. **Associations** shows scope bindings and lifetime edges, which are
hidden by default. Input slots retain their indices, including null slots.
**Peep neighborhood** outlines nearby nodes in amber, with a darker outline
on the current node/replacement. The event label identifies the phase, rewrite,
and enclosing rewrite when calls nest. This marks context; it does not zoom or
animate the rewrite yet.

For documentation figures, step to the desired frame and click **Save SVG**.
It saves the whole graph, regardless of pan/zoom, with its current association
visibility, neighborhood highlighting and selection. Clear selection with
Escape and uncheck **Peep neighborhood** for an unmarked diagram. The SVG
includes its styles and arrow markers and needs no JavaScript or viewer assets;
check it into the chapter's docs and embed it like the existing static figures.
Existing `.gv` sources and their generated SVGs remain another way to maintain
documentation figures.

The launcher prints the viewer URL before opening the browser. If the desktop
only raises an existing browser window, paste that URL into a new tab. Use
`-Dsimple.graph.open=false` to suppress automatic browser opening when testing
or connecting a browser manually. A disconnected viewer stays open and shows
its connection status instead of silently closing the tab.

After building a chapter, `python graph/test_transport.py chapter25` from the
repository root checks HTTP asset delivery, a delayed and fragmented WebSocket
upgrade, and session shutdown without opening a browser.

`python graph/test_browser.py chapter25 --browser msedge` additionally checks
actual rendering, stepping backward/forward, compiling multiple programs, and
disconnected startup in a headless browser. This optional test requires the
Python `playwright` package and the selected browser; it is not a viewer runtime
dependency. Use `--browser firefox` after `python -m playwright install firefox`
for Firefox testing. Test logs/screenshots are written under `build/graph-browser/`.

## Boundary between chapters and the viewer

Chapters 4 and 25 share the Java viewer plumbing as well as the browser:

- `GraphViewer` owns asset discovery, the source/compile loop, frame serialization,
  and session shutdown. A chapter's `JSViewer` subclass only invokes its compiler
  and attaches/detaches its observer.
- `GraphSocket` serves local assets, opens the browser, and handles WebSocket
  messages. One buffered stream handles both the upgrade and frames. Payloads
  use exact reads and their advertised length, including 64-bit lengths;
  continuation frames assemble UTF-8 before decoding, and PING data is echoed.
- `GraphCapture<N>` owns nested attempts, buffered snapshots, event numbering,
  neighborhood accumulation and disconnect handling. It extends `GraphObserver<N>`.
  Chapter subclasses supply roots, phase, parser position and observer detachment.
- `GraphAdapter<N>` supplies node facts and indexed graph/dependency access.
  Dependency access defaults to an empty set in chapters without those lists.

Chapter 25's private WebSocket implementation is removed. Chapters 18–24 retain
their old transport until migrated. Shared Java has no dependency on chapter classes.
The WebSocket listener and built-in asset server bind to 127.0.0.1.

The connection messages are:

| Direction | Message | Meaning |
| --- | --- | --- |
| Compiler to browser | `!` | Request the source program |
| Browser to compiler | Source text | Compile and capture a new sequence |
| Compiler to browser | `digraph ...` | One complete DOT snapshot |
| Compiler to browser | JSON `{snap, pos, evt}` | Chapters 4/25's complete graph, parser position and event |
| Compiler to browser | JSON `{error}` | Compilation failed; the session accepts another program |
| Browser to compiler | `+` | Acknowledge/request another frame |
| Compiler to browser | `#` | End of sequence |
| Browser to compiler | `null` | End the session |

The JSON frame has this shape:

```json
{
  "snap": {
    "ver": 1, "comp": "compilation UUID", "step": 0, "roots": [1],
    "nodes": [
      {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}
    ]
  },
  "pos": -1,
  "evt": {
    "kind": "PHASE", "peep": 0, "up": 0, "phase": "Opto",
    "node": 0, "repl": 0, "near": []
  }
}
```

`GraphJson.write(snap)` serializes the graph alone. `GraphJson.frame(snap, pos, evt)`
adds the playback envelope. `comp` changes for each submitted
program, and `step` starts at zero. `nodes` carries the complete graph, including
each node's `id`, `label`, `type`, `kind`, `edges`, and `proj`. Enum values use
their names; absent types, labels and projections use JSON null. Missing node
references use ID zero. `pos` is the parser position, or -1 outside parsing.

The browser caches the parsed objects in `frames`. It computes geometry on the
first visit to a frame and keeps it in `frames[i].layout`; revisiting a frame
uses exactly that geometry. Viewport changes do not rerun layout. Nodes and
edges have stable SVG IDs within a compilation. There is no animation yet.
One `+` acknowledges the whole frame. The shared writer sends UTF-8 bytes
and supports WebSocket's 64-bit length header for frames larger than 65535 bytes.

Legacy chapters' DOT frames may contain a `// POS:` comment identifying the
parser position. The browser owns frame history and backward/forward playback.

Chapter 25 no longer generates DOT for the interactive viewer. The browser
uses ELK's layered layout with fixed input ports and orthogonal routing.
Layout follows def-to-use flow downward, while the displayed arrows point
from use to def, matching Simple's edges. Control edges get a higher layout
priority; known Loop/Phi backedges get a lower priority. Associations are drawn
as a separate overlay and do not constrain layout. Projections remain real
nodes for now.

This first layout is flat. It does not discover compiler loops, compute RPO,
or build a SESE hierarchy. ELK breaks cycles for drawing, which can still put
whole-program cycles in an awkward order. Compiler-provided grouping and CFG
ordering are follow-up work, along with preserving positions across rewrites.
Each visited frame currently retains a full snapshot and layout; bounded
history, checkpoints and deltas are also follow-up work.

ELK runs locally from the pinned elkjs 0.12.0 worker; see
[`web/vendor/elk-README.md`](web/vendor/elk-README.md) for provenance and licensing.
No npm or Maven step is needed to use it.

The linearization workflow includes this directory as a shared root resource.
Chapters 4 and 25 compile the shared Java sources from this directory; the
interactive viewer also loads the web assets from this checkout.

## Chapter adapters

The shared Java code is in `src/main/java/com/seaofnodes/graph/`:

- `GraphAdapter<N>` is an abstract base with hooks for `id`, `desc`, and indexed
  edge access (`nIns`/`in`, `nOuts`/`out`). Its final `snap` method walks definitions and
  uses iteratively, handles cycles, and sorts the copied records by ID.
- `GraphSnapshot` is detached data: compilation key, step, roots, and nodes.
  Each node has an ID, plain-text label/type, kind, edges to its defs, and optional
  projection metadata. It contains no chapter classes or layout coordinates.
  Node and edge lists are concrete `ArrayList`s, treated as read-only after capture.

Root IDs use `int[]`. Capture uses a node table indexed by ID for visitation and
root deduplication; no boxed integer lists, sets or map keys are needed.
Indexed edge access reads each chapter's native storage without copying it into
a different collection type.

Both chapters implement `com.seaofnodes.simple.print.SimpleGraphAdapter`,
extending `GraphAdapter<Node>`. No changes to `Node` or its subclasses are
needed. The chapter owns classification and extraction; the base owns traversal
and snapshot assembly. No new Java interface is involved.

For chapter 4:

```java
var parser = new Parser("return 1+arg+2;");
var ret = parser.parse();
var adapter = new SimpleGraphAdapter();
var frame = adapter.snap("compile-1", 0, ret, parser._scope);
```

For chapter 25:

```java
var code = new CodeGen("while(arg < 10) arg = arg + 1; return arg;").parse();
var adapter = new SimpleGraphAdapter();
var frame = adapter.snap("compile-1", 0, code._stop);
```

During a peephole, pass the current node and any unattached replacement as
additional roots. Null roots are ignored. Capture runs on the compiler thread
at a point where the graph is not changing; consumers can retain the returned
records after compilation resumes. The adapter does not compute types, invoke
peepholes, schedule nodes, or rearrange use lists.

Node IDs are the chapter's `_nid`, scoped by the caller's compilation key. Use
a new key whenever a parser/compiler resets IDs. A snapshot rejects two distinct
nodes sharing one ID. Each edge belongs to its use node and names the referenced
`def` ID and the input slot `idx` on that use: `use.in(idx) == def`. The adapter
derives these edges from the compiler's `_inputs`; `_outputs` only speeds up
traversal. Repeated definitions produce distinct edges with different slot
indices. Each input slot has an `Edge` record, including holes with `def == 0`.
Edges remain in input-slot order under their use node.
Projection nodes retain their own IDs and identify their parent and tuple
index, allowing the renderer to fold them into ports later. A missing parent
has `par == 0`; real node IDs are never zero.

Chapter 4 adds control/data roles and scope binding names. Chapter 25 adds
memory roles and node kinds for Phis, Regions, Loops,
Functions and compilation-unit boundaries. These are existing IR facts, not
computed region membership or a SESE hierarchy. Scope bindings and constant
lifetime edges are associations, so they need not constrain CFG layout.
Types may be absent on newly constructed nodes. Source locations, grouping,
and delta encoding remain follow-up work. Both chapters use the observer events
described below.

Make compiles these shared sources directly into each participating chapter's
classes using `javac`. From the repository root:

```sh
make -C chapter04 build
make -C chapter25 build
```

`build` compiles the compiler and adapter without running tests or opening a
browser. Shared source changes trigger recompilation. No Maven executable,
Maven-built artifacts, generated source copies or separately installed graph
JARs are needed. Existing `make tests`, `make release` and chapter 25's
`make view` also include the shared sources through their normal prerequisites.
Chapter 4's `make view` depends on `build` and runs the same shared viewer.

For the existing Maven/CI build path, `build-helper:add-source` describes the
same source directory. The two chapter POMs select `../graph`, while the root
POM defaults to `graph` for linearized checkouts. These entries are independent
of the Make build.

## Peephole observers

`GraphObserver<N>` is a shared abstract base for `before`, `after`, `phase`, and
`dep` callbacks. Chapter 25's `CodeGen._obs` and chapter 4's `Parser._obs` own the
optional observer. Chapter 4 uses `Parser.PARSER` as its current compilation
context, alongside its existing global `START`. Normal compilation
leaves it null, so it does no snapshot capture or serialization. Assertions
that probe peepholes with `_midAssert` set do not generate observer calls.
Neither `Node` nor `IterPeeps` refers to `JSViewer`.

`GraphCapture` supplies capture and neighborhood logic. Each chapter's small
`SimpleGraphObserver` supplies its compilation context. `JSViewer` installs one
for each compilation and forwards frames to `GraphViewer`.
An I/O failure disables the observer and allows optimization to continue.
The observer is detached in a `finally` block when compilation finishes or fails.

The event kinds distinguish the actual capture boundaries:

| Kind | Meaning |
| --- | --- |
| `BEFORE` | Graph before an attempt that made progress, or contained a nested rewrite |
| `RETURN` | Recursive `Node.peephole()` finished, including its local DCE; the caller has not yet attached the returned node |
| `APPLY` | A worklist attempt finished after substitution, dependency draining, and unused-node cleanup |
| `PHASE` | Parse completed in chapter 4; Parse, Iter, or Opto completed in chapter 25, including work outside individual peepholes |

`peep` identifies an attempt; `up` identifies its enclosing attempt, or zero.
`node` and `repl` identify the original and result nodes. A zero `repl` on
`APPLY` means removal without a surviving result. Phase events use zero IDs.
An in-place rewrite has equal `node` and `repl` IDs. Type changes also count as
progress; these events are not restricted to structural rewrites.

Before snapshots are buffered until the outcome is known. Attempts without
progress are discarded unless they contain a visible child rewrite. Ancestor
before frames are emitted before their children; after frames close the nested
attempts. Frame steps are assigned consecutively on emission, while attempt IDs
may have gaps. A failed compilation can leave an unfinished attempt; the next
compilation gets a fresh observer and compilation key.

Capture includes the active attempts and returned node as extra roots, so nodes
not yet attached by the parser remain visible. Dead originals are not added as
after-frame roots. The observer never adds keep edges, changes use lists, or
modifies the compiler's dependency tracking.

`near` is a primitive array of node IDs, assembled with a `BitSet`. It combines:

- The current node and replacement, with their immediate defs and uses before
  and after the rewrite.
- Existing wake-up dependents, read before those lists are drained.
- Nodes named by `addDep`/`addDepForwards` during the attempt, including calls
  whose dependency already exists or is an immediate neighbor.
- Neighborhoods of nested attempts.

This is initial display context, not an exact record of every node read or
changed by a rule. Dependency lists contain wake-up dependents; they do not
describe an entire successful pattern match. Some rules inspect distant nodes
without registering a dependency. Before events include context known when
emitted; their matching after events can add more. IDs of deleted nodes remain
in `near`, and the browser highlights only those present in the current frame.
Actual graph diffs and explicit rule annotations can refine this later.

The browser keeps the event alongside its snapshot and layout. It labels and
highlights the current step, but does not yet collapse nested rewrites or move
the camera to their neighborhoods. Chapter 4 uses the same event model, with
defs/uses for its neighborhoods and no worklist or dependency lists. Its parser
retains the final Return as a root after scope cleanup.

Chapter 25's parser no longer accepts `#showGraph;`; use the browser to inspect
the graph and **Save SVG** for a static figure. Earlier chapters retain their
directive until migrated. Chapter 25 still supports the independent `--dot`
dump option; it and `GraphVisualizer` can be retired separately.

Constant-folding peepholes already exist in chapter02. Chapters 03 and 04 add
variables and algebraic rewrites, respectively, and are useful next adapters.
They should not need the later chapters' `CodeGen`, worklist, or type hierarchy
to use the shared display.