diff options
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/README.md | 126 | ||||
| -rw-r--r-- | graph/src/main/java/com/seaofnodes/graph/GraphEvent.java | 10 | ||||
| -rw-r--r-- | graph/src/main/java/com/seaofnodes/graph/GraphJson.java | 16 | ||||
| -rw-r--r-- | graph/src/main/java/com/seaofnodes/graph/GraphObserver.java | 19 | ||||
| -rw-r--r-- | graph/web/index.html | 7 | ||||
| -rw-r--r-- | graph/web/render.js | 39 | ||||
| -rw-r--r-- | graph/web/viewer.js | 17 |
7 files changed, 191 insertions, 43 deletions
diff --git a/graph/README.md b/graph/README.md index 224fa031..27a96c01 100644 --- a/graph/README.md +++ b/graph/README.md @@ -36,6 +36,19 @@ 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 @@ -68,7 +81,7 @@ The connection messages are: | 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}` | Chapter 25's complete graph and parser position | +| Compiler to browser | JSON `{snap, pos, evt}` | Chapter 25's complete graph, parser position and event | | Browser to compiler | `+` | Acknowledge/request another frame | | Compiler to browser | `#` | End of sequence | | Browser to compiler | `null` | End the session | @@ -83,11 +96,15 @@ Chapter 25's JSON frame has this shape: {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null} ] }, - "pos": -1 + "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)` +`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 @@ -190,7 +207,8 @@ 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, -observer events and delta encoding remain follow-up work. +and delta encoding remain follow-up work. Chapter 25 adds observer events as +described below; the chapter 4 adapter is still independent of an observer. Make compiles these shared sources directly into each participating chapter's classes using `javac`. From the repository root: @@ -211,40 +229,72 @@ 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 hook investigation - -The current chapter25 capture sites are: - -- `Node.peephole()`: before a new node's first optimization, and after - `peepholeOpt()` reports progress. The latter happens before recursive - optimization and `deadCodeElim`, and before the caller attaches the result. -- `IterPeeps.iteratePeeps()`: after a successful worklist optimization and - substitution, but before the subsequent unused-node cleanup. -- `CodeGen.parse()`: after parsing, at the phase boundary. - -These sites capture different meanings of “after.” Recursive peepholes can -also produce intermediate frames. Replacing `JSViewer.show()` with a generic -callback alone would preserve that ambiguity. - -Chapter 25's interactive viewer now uses the adapter's numeric IDs and plain-text -labels; browser rendering does not interpret labels as HTML. Capture traverses -`_outputs` without changing their order. The older DOT exporters still need -review before extending their adapters. - -A follow-up should introduce an optional compilation observer, owned by the -compilation/session, with explicit events for an attempted rewrite, an applied -replacement, and a phase boundary. Events should identify the node/replacement -and let the chapter adapter capture a snapshot without modifying the IR. The -viewer can group nested rewrites into one visible step. Capture completed -rewrites after the caller has installed the replacement and performed cleanup; -keep intermediate snapshots available when teaching the rewrite itself. -For parse-time nodes not yet reachable from the normal roots, the adapter must -also include the event's current node/replacement as snapshot roots. - -Serialization and transport should be inactive when no observer is installed. -Graph drawing should not appear in `Node`'s API, and browser connection failures -should not change compilation behavior. These are design notes, not changes to -the current compiler callbacks. +## Peephole observer (chapter 25) + +`GraphObserver<N>` is a shared abstract base for `before`, `after`, `phase`, and +`dep` callbacks. `CodeGen._obs` owns the optional observer. 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`. + +`SimpleGraphObserver` supplies chapter 25's capture and neighborhood logic. +`JSViewer` installs one for each compilation and supplies only the frame sink. +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, Iter, or Opto completed, 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. The chapter 4 observer hookup is follow-up +work; its adapter already targets the same graph model. + +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. diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphEvent.java b/graph/src/main/java/com/seaofnodes/graph/GraphEvent.java new file mode 100644 index 00000000..7d889b21 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphEvent.java @@ -0,0 +1,10 @@ +package com.seaofnodes.graph; + +/** IDs refer to nodes in this compilation; near may include nodes since deleted. */ +public record GraphEvent(Kind kind, long peep, long up, String phase, + int node, int repl, int[] near) { + public enum Kind { BEFORE, RETURN, APPLY, PHASE } + + public GraphEvent { near = near.clone(); } + @Override public int[] near() { return near.clone(); } +} diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphJson.java b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java index 440be034..c27076d3 100644 --- a/graph/src/main/java/com/seaofnodes/graph/GraphJson.java +++ b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java @@ -8,10 +8,22 @@ public class GraphJson { return sb.toString(); } - public static String frame(GraphSnapshot snap, int pos) { + public static String frame(GraphSnapshot snap, int pos, GraphEvent evt) { var sb = new StringBuilder("{\"snap\":"); snap(sb, snap); - sb.append(",\"pos\":").append(pos); + sb.append(",\"pos\":").append(pos).append(",\"evt\":{\"kind\":"); + str(sb, evt.kind().name()); + sb.append(",\"peep\":").append(evt.peep()).append(",\"up\":").append(evt.up()) + .append(",\"phase\":"); + str(sb, evt.phase()); + sb.append(",\"node\":").append(evt.node()).append(",\"repl\":").append(evt.repl()) + .append(",\"near\":["); + int[] near = evt.near(); + for( int i = 0; i < near.length; i++ ) { + if( i > 0 ) sb.append(','); + sb.append(near[i]); + } + sb.append("]}"); return sb.append('}').toString(); } diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphObserver.java b/graph/src/main/java/com/seaofnodes/graph/GraphObserver.java new file mode 100644 index 00000000..24879fe2 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphObserver.java @@ -0,0 +1,19 @@ +package com.seaofnodes.graph; + +/** Optional, compilation-owned observer. Callbacks read the IR without changing it. */ +public abstract class GraphObserver<N> { + public abstract void before(N node); + + /** + * repl is null for no progress. applied means substitution and cleanup are + * complete; otherwise repl is being returned for the caller to attach. + * Calls nest when a rewrite invokes another peephole. + */ + public abstract void after(N node, N repl, boolean applied); + + /** A completed compiler phase. */ + public abstract void phase(String phase); + + /** A rule consulted a dependency, even if already registered or adjacent. */ + public void dep(N node, N def) {} +} diff --git a/graph/web/index.html b/graph/web/index.html index 1badd8e1..f91f1710 100644 --- a/graph/web/index.html +++ b/graph/web/index.html @@ -13,7 +13,7 @@ #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } #elk, #dot { width:100%; height:100%; } #graph svg { display:block; } - .tools { display:flex; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } .hint { color:#616c78; } .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } .edge { fill:none; stroke-width:1.5; } @@ -22,6 +22,8 @@ .edge.selected { stroke-width:3.5; } .node { cursor:pointer; } .box { stroke:#758191; stroke-width:1; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } .node.selected .box { stroke:#1569b9; stroke-width:3; } .head { font-size:10px; fill:#596674; } .label { font-size:12px; fill:#152330; font-weight:600; } @@ -51,10 +53,13 @@ <div id="status" role="status">Connecting to compiler...</div> <div class="tools"> <button id="fit" type="button" disabled>Fit</button> + <button id="save" type="button" disabled>Save SVG</button> <label><input id="assocs" type="checkbox"> Associations</label> + <label><input id="near" type="checkbox" checked> Peep neighborhood</label> <span class="ctrl">Control</span><span class="data">Data</span><span class="mem">Memory</span> <span class="hint">Scroll to zoom · drag to pan · click a node for details</span> </div> + <div id="event" class="hint" role="status"></div> </div> <div id="graph"><div id="elk"></div><div id="dot" hidden></div><pre id="detail" hidden></pre></div> <div class="controls"> diff --git a/graph/web/render.js b/graph/web/render.js index b488ed0e..76cf8c06 100644 --- a/graph/web/render.js +++ b/graph/web/render.js @@ -30,7 +30,7 @@ class GraphView { this.resize.observe(host); } - show(snap, scene) { + show(snap, scene, evt) { if (this.comp !== snap.comp) { this.comp = snap.comp; this.pick = 0; @@ -39,6 +39,7 @@ class GraphView { this.links.selectAll("*").remove(); } this.scene = scene; + this.evt = evt; this.links.selectAll("path.edge").data(scene.edges, e => e.id).join("path") .attr("class", e => "edge " + e.role).attr("id", e => e.id) .attr("d", e => e.path).attr("stroke", e => this.colors[e.role]) @@ -78,6 +79,7 @@ class GraphView { .attr("text-anchor", "middle").text((p, j) => n.n.edges[j].idx); }); this.assocs(document.getElementById("assocs").checked); + this.mark(); this.select(this.pick); if (this.auto) this.fit(); } @@ -100,6 +102,41 @@ class GraphView { assocs(show) { this.links.selectAll(".ASSOC").style("display", show ? null : "none"); } + mark() { + const evt = this.evt; + const show = document.getElementById("near").checked; + const near = new Set(show ? evt?.near : []); + this.nodes.selectAll("g.node").classed("near", n => near.has(n.n.id)) + .classed("focus", n => show && (n.n.id === evt?.node || n.n.id === evt?.repl)); + } + + // Save the whole graph at its layout size, independent of pan/zoom. + save(step) { + const svg = this.svg.node().cloneNode(true); + svg.setAttribute("xmlns", "http://www.w3.org/2000/svg"); + svg.setAttribute("width", this.scene.width); + svg.setAttribute("height", this.scene.height); + svg.setAttribute("viewBox", `0 0 ${this.scene.width} ${this.scene.height}`); + svg.style.fontFamily = getComputedStyle(this.host).fontFamily; + svg.querySelector("g").removeAttribute("transform"); + // Keep styles, markers and labels in the file; no viewer assets are needed. + const style = document.createElementNS(svg.namespaceURI, "style"); + style.textContent = document.querySelector("style").textContent; + svg.prepend(style); + const bg = document.createElementNS(svg.namespaceURI, "rect"); + bg.setAttribute("width", "100%"); bg.setAttribute("height", "100%"); + bg.setAttribute("fill", getComputedStyle(this.host.parentElement).backgroundColor); + svg.insertBefore(bg, svg.querySelector("g")); + const blob = new Blob([new XMLSerializer().serializeToString(svg)], {type: "image/svg+xml"}); + const url = URL.createObjectURL(blob); + const link = document.createElement("a"); + link.href = url; link.download = `simple-${step}.svg`; + document.body.append(link); + link.click(); + link.remove(); + setTimeout(() => URL.revokeObjectURL(url), 1000); + } + fit() { if (!this.scene || !this.host.clientWidth || !this.host.clientHeight) return; const w = this.host.clientWidth, h = this.host.clientHeight; diff --git a/graph/web/viewer.js b/graph/web/viewer.js index e193a4b3..9aaaa154 100644 --- a/graph/web/viewer.js +++ b/graph/web/viewer.js @@ -28,7 +28,20 @@ function updateUI() { document.getElementById("compile").disabled = !socket || socket.readyState !== WebSocket.OPEN || compiling || rendering; document.getElementById("fit").disabled = rendering || current < 0; + document.getElementById("save").disabled = rendering || !frames[current]?.snap; document.getElementById("assocs").disabled = !frames[current]?.snap; + document.getElementById("near").disabled = !frames[current]?.evt; + const evt = frames[current]?.evt; + let label = ""; + if (evt) { + const text = evt.kind === "PHASE" ? "Phase complete" : + evt.kind === "BEFORE" ? `Before peephole #${evt.peep} at node #${evt.node}` : + evt.kind === "RETURN" ? `Return #${evt.repl} for #${evt.node}` : + !evt.repl ? `Removed #${evt.node}` : evt.repl === evt.node ? `Updated #${evt.node}` : + `Replaced #${evt.node} with #${evt.repl}`; + label = `${evt.phase} · ${text}${evt.up ? " (inside peephole #" + evt.up + ")" : ""}`; + } + document.getElementById("event").textContent = label; } function reportError(error) { @@ -75,7 +88,7 @@ async function render(index) { if (frame.snap) { if (!layout) layout = new GraphLayout(); if (!frame.layout) frame.layout = await layout.run(frame.snap); - if (generation === frameGeneration) renderer.show(frame.snap, frame.layout); + if (generation === frameGeneration) renderer.show(frame.snap, frame.layout, frame.evt); } else { document.getElementById("detail").hidden = true; await drawDot(frame.dot); @@ -108,6 +121,8 @@ document.getElementById("fit").addEventListener("click", () => { else render(current); }); document.getElementById("assocs").addEventListener("change", event => renderer.assocs(event.target.checked)); +document.getElementById("near").addEventListener("change", () => renderer.mark()); +document.getElementById("save").addEventListener("click", () => renderer.save(frames[current].snap.step)); document.addEventListener("keydown", event => { if (event.key === "Escape") renderer.select(0); }); |