diff options
| -rw-r--r-- | chapter25/docs/18-grammar.md | 3 | ||||
| -rw-r--r-- | chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java | 8 | ||||
| -rw-r--r-- | chapter25/src/main/java/com/seaofnodes/simple/Parser.java | 11 | ||||
| -rw-r--r-- | chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java | 7 | ||||
| -rw-r--r-- | chapter25/src/main/java/com/seaofnodes/simple/node/Node.java | 14 | ||||
| -rw-r--r-- | chapter25/src/main/java/com/seaofnodes/simple/print/JSViewer.java | 74 | ||||
| -rw-r--r-- | chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java | 130 | ||||
| -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 |
14 files changed, 361 insertions, 120 deletions
diff --git a/chapter25/docs/18-grammar.md b/chapter25/docs/18-grammar.md index 7b611fbf..2c98f562 100644 --- a/chapter25/docs/18-grammar.md +++ b/chapter25/docs/18-grammar.md @@ -15,7 +15,6 @@ statement | whileStatement | breakStatement | continueStatement - | metaStatement | structDeclaration | expressionStatement ; @@ -31,8 +30,6 @@ breakStatement : 'break' ';' ; continueStatement : 'continue' ';' ; -metaStatement : '#showGraph' ';' ; - structDeclaration : 'struct' IDENTIFIER '{' block '}' ; expressionStatement diff --git a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java index 145e0e03..a54eca73 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/IterPeeps.java @@ -6,7 +6,6 @@ import com.seaofnodes.simple.type.Type; import com.seaofnodes.simple.type.TypeInteger; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.print.JSViewer; import java.util.Arrays; import java.util.BitSet; import java.util.IdentityHashMap; @@ -105,6 +104,8 @@ public class IterPeeps { while( (n=_work.pop()) != null ) { if( n.isDead() ) continue; _cnt++; // Useful for debugging, searching which peephole broke things + var obs = code._obs; + if( obs != null ) obs.before(n); Node x = n.peepholeOpt(); if( n instanceof CallEndNode cend ) _workInline.push(cend); @@ -133,14 +134,15 @@ public class IterPeeps { } // If there are distant neighbors, move to worklist n.moveDepsToWorklist(); - JSViewer.show(); // Show again // Very expensive assert. assert !CodeGen.expensiveAssert(_cnt) || (progressOnList(code, _work) && schedulableUses(code)); } - if( n.isUnused() ) { + boolean unused = n.isUnused(); + if( unused ) { assert !(n instanceof StopNode); // StopNodes can die if all code in the compunit dies n.kill(); // Just plain dead } + if( obs != null ) obs.after(n, x!=null ? x : unused ? n : null, true); } assert !CodeGen.expensiveAssert(0) || schedulableUses(code); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java index 1f03eda6..ffd8bf64 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java @@ -2,7 +2,6 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.*; import com.seaofnodes.simple.node.*; -import com.seaofnodes.simple.print.GraphVisualizer; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.Ary; import com.seaofnodes.simple.node.ScopeNode.Kind; @@ -521,7 +520,6 @@ public class Parser { else if (matchx("continue")) return parseContinue(); else if (matchx("struct") ) return parseStruct(); else if (inStructDeclaration() && matchx("new")) return parseConstructorDeclaration(); - else if (matchx("#showGraph")) return require(showGraph(),";"); else if (matchx(";") ) return _code.ZERO; // Empty statement // Break ambiguity around leading function types and starting a block else if (peek('{') && !isTypeFun() ) { @@ -913,15 +911,6 @@ public class Parser { return expr.unkeep(); } - /** - * Dumps out the node graph - * @return {@code null} - */ - Node showGraph() { - System.out.println(new GraphVisualizer().generateDotOutput(_ref,_scope,_xScopes)); - return null; - } - /** Parse: [name '='] expr */ private Node parseAsgn() { diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index aafaf7ed..f8674d64 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -1,5 +1,6 @@ package com.seaofnodes.simple.codegen; +import com.seaofnodes.graph.GraphObserver; import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.node.*; @@ -41,6 +42,8 @@ public class CodeGen { LastPhase // After last phase } public Phase _phase; + // Null for normal compilation; owned by this compilation, not a global viewer. + public GraphObserver<Node> _obs; /** True when tests deliberately randomize Iter worklist order. */ public static boolean iterSeedOverridden() { return System.getProperty("simple.iter.seed") != null; } @@ -426,7 +429,7 @@ public class CodeGen { } _times[Phase.Parse.ordinal()] = System.currentTimeMillis() - t0; - JSViewer.show(); + if( _obs != null ) _obs.phase(_phase.name()); return this; } @@ -466,6 +469,7 @@ public class CodeGen { assert !expensiveAssert() || Opto.fixedPointCheck(this); _times[Phase.Iter.ordinal()] = System.currentTimeMillis() - t0; + if( _obs != null ) _obs.phase(_phase.name()); return this; } @@ -515,6 +519,7 @@ public class CodeGen { Opto.opto(this); _times[Phase.Opto.ordinal()] = System.currentTimeMillis() - t0; + if( _obs != null ) _obs.phase(_phase.name()); return this; } public <N extends Node> N add( N n ) { return _iter.add(n); } diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java index e884251c..d113a02a 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java @@ -5,7 +5,6 @@ import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.GlobalBits; import com.seaofnodes.simple.print.IRPrinter; -import com.seaofnodes.simple.print.JSViewer; import com.seaofnodes.simple.type.*; import com.seaofnodes.simple.util.*; import java.util.*; @@ -460,12 +459,12 @@ public abstract class Node implements Cloneable { * Always returns some not-null Node (often this). */ public final Node peephole( ) { - if( _type==null ) // Brand-new node, never peeped before - JSViewer.show(); + var obs = CODE._midAssert ? null : CODE._obs; + if( obs != null ) obs.before(this); Node n = peepholeOpt(); - if( n!=null ) // Made progress? - JSViewer.show(); // Show again - return n==null ? this : deadCodeElim(n._nid >= _nid ? n.peephole() : n); // Cannot return null for no-progress + Node rez = n==null ? this : deadCodeElim(n._nid >= _nid ? n.peephole() : n); + if( obs != null ) obs.after(this, n==null ? null : rez, false); + return rez; // Cannot return null for no-progress } /** @@ -637,11 +636,14 @@ public abstract class Node implements Cloneable { // retry the peephole. Track a set of Nodes dependent on `this`, and // revisit them if `this` changes. Ary<Node> _deps; + public int nDeps() { return _deps == null ? 0 : _deps.size(); } + public Node dep(int idx) { return _deps.at(idx); } private boolean addDepImpl( Node dep ) { // Running peepholes during the big assert cannot have side effects // like adding dependencies. if( CODE._midAssert ) return false; + if( CODE._obs != null ) CODE._obs.dep(this, dep); if( dep._deps==null ) dep._deps = new Ary<>(Node.class); if( dep._deps .find(this) != -1 ) return false; // Already on list if( dep._outputs.find(this) != -1 ) return false; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/print/JSViewer.java b/chapter25/src/main/java/com/seaofnodes/simple/print/JSViewer.java index 42f007ea..10c07730 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/print/JSViewer.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/print/JSViewer.java @@ -1,16 +1,14 @@ package com.seaofnodes.simple.print; import com.seaofnodes.graph.GraphJson; +import com.seaofnodes.graph.GraphEvent; +import com.seaofnodes.graph.GraphSnapshot; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.node.*; import java.io.IOException; import java.nio.file.Paths; import java.nio.file.Files; import java.nio.file.Path; import java.net.URI; -import java.util.ArrayList; -import java.util.UUID; -import static com.seaofnodes.simple.codegen.CodeGen.CODE; public class JSViewer implements AutoCloseable { // Display programs in an endless loop @@ -20,18 +18,12 @@ public class JSViewer implements AutoCloseable { } } - static boolean SHOW; - // WebSocket to the browser for display - static SimpleWebSocket SERVER; - - static long N; // Snapshot step within this compilation - static String COMP; - static final SimpleGraphAdapter GRAPH = new SimpleGraphAdapter(); + private final SimpleWebSocket _server; JSViewer() throws Exception { // Launch server; handshake - SERVER = new SimpleWebSocket(viewerURI(),12345); + _server = new SimpleWebSocket(viewerURI(),12345); } // The browser application is shared by all chapters. Search upwards so @@ -48,9 +40,9 @@ public class JSViewer implements AutoCloseable { } void run( ) throws Exception { - SERVER.put("!"); + _server.put("!"); while( true ) { - String src = SERVER.get(); + String src = _server.get(); switch( src ) { case null: return; case "null": return; @@ -58,55 +50,31 @@ public class JSViewer implements AutoCloseable { default: System.out.println(src); try { - N=0; - COMP = UUID.randomUUID().toString(); - // Use parser scope, xscope when building views - CodeGen code = new CodeGen(src); - SHOW = true; - show(); - // Parse program, generating views at every parse point - code.parse(); - // No longer user parse internal state when building views - code.opto(); - + compile(src); // Catch and ignore Parser errors } catch(RuntimeException re) { System.err.println(re); } finally { - SHOW = false; - SERVER.put("#"); // Final frame + _server.put("#"); // Final frame } break; } } } - @Override public void close() throws IOException { - SERVER.close(); - SERVER=null; - } - - public static void show() { if( SERVER!=null && SHOW ) _show(); } - private static void _show() { - // Skip util we at least get the Parse object made - if( CODE._phase==null || CODE._phase.ordinal() < CodeGen.Phase.Parse.ordinal() ) - return; - boolean midParse = CODE._phase == CodeGen.Phase.Parse; - var xScopes = midParse ? CODE.P._xScopes : null; - var roots = new ArrayList<Node>(); - roots.add(CODE._stop); - if( midParse ) { - roots.add(CODE.P._scope); - roots.addAll(xScopes); - } - long step = N++; - var snap = GRAPH.snap(COMP, step, roots.toArray(Node[]::new)); - int pos = midParse ? CODE.P.pos() : -1; - + private void compile(String src) { + CodeGen code = new CodeGen(src); + code._obs = new SimpleGraphObserver(code) { + @Override protected void frame(GraphSnapshot snap, int pos, GraphEvent evt) throws IOException { + _server.put(GraphJson.frame(snap, pos, evt)); + } + }; try { - SERVER.put(GraphJson.frame(snap, pos)); - } catch( IOException ioe ) { - try { SERVER.close(); } catch( IOException ignored ) {} + code.parse().opto(); + } finally { + code._obs = null; } } -}
\ No newline at end of file + + @Override public void close() throws IOException { _server.close(); } +} diff --git a/chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java new file mode 100644 index 00000000..5d511287 --- /dev/null +++ b/chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -0,0 +1,130 @@ +package com.seaofnodes.simple.print; + +import com.seaofnodes.graph.GraphEvent; +import com.seaofnodes.graph.GraphObserver; +import com.seaofnodes.graph.GraphSnapshot; +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.Node; +import java.io.IOException; +import java.util.ArrayList; +import java.util.BitSet; +import java.util.UUID; + +/** Capture events and neighborhoods on the compiler thread. Transport is supplied by the viewer. */ +public abstract class SimpleGraphObserver extends GraphObserver<Node> { + private final CodeGen _code; + private final SimpleGraphAdapter _graph = new SimpleGraphAdapter(); + private final String _comp = UUID.randomUUID().toString(); + private final ArrayList<Peep> _peeps = new ArrayList<>(); + private long _next, _step; + private boolean _off; + + protected SimpleGraphObserver(CodeGen code) { _code = code; } + + protected abstract void frame(GraphSnapshot snap, int pos, GraphEvent evt) throws IOException; + + private static class Peep { + final Node node; + final long id, up; + final String phase; + final int pos; + final BitSet near = new BitSet(); + GraphSnapshot pre; + boolean sent; + + Peep(Node n, long id, long up, String phase, int pos) { + node = n; this.id = id; this.up = up; this.phase = phase; this.pos = pos; + } + } + + @Override public void before(Node n) { + if( _off ) return; + var p = new Peep(n, ++_next, _peeps.isEmpty() ? 0 : _peeps.getLast().id, + _code._phase.name(), pos()); + _peeps.add(p); + near(p, n); + // Buffer until we know that this attempt (or a nested one) made progress. + // Include n explicitly: parse-time nodes need not have any uses yet. + p.pre = snap(n); + } + + @Override public void after(Node n, Node repl, boolean applied) { + if( _off ) return; + Peep p = _peeps.getLast(); + assert p.node == n; + near(p, n); + near(p, repl); + for( Peep up : _peeps ) up.near.or(p.near); + if( repl != null || p.sent ) { + // Emit ancestors first so a nested rewrite always has its context. + for( Peep up : _peeps ) { + if( up.sent ) continue; + emit(up.pre, up.pos, evt(up, GraphEvent.Kind.BEFORE, 0)); + if( _off ) return; + up.pre = null; + up.sent = true; + } + Node rez = repl == null ? n : repl; + emit(snap(rez.isDead() ? null : rez), pos(), + evt(p, applied ? GraphEvent.Kind.APPLY : GraphEvent.Kind.RETURN, + rez.isDead() ? 0 : rez._nid)); + } + _peeps.removeLast(); + } + + @Override public void dep(Node n, Node def) { + if( _off || _peeps.isEmpty() ) return; + Peep p = _peeps.getLast(); + add(p, n); + add(p, def); + } + + @Override public void phase(String phase) { + if( _off ) return; + emit(snap(null), pos(), new GraphEvent(GraphEvent.Kind.PHASE, 0, 0, phase, 0, 0, new int[0])); + } + + private GraphEvent evt(Peep p, GraphEvent.Kind kind, int repl) { + return new GraphEvent(kind, p.id, p.up, p.phase, p.node._nid, repl, p.near.stream().toArray()); + } + + private void add(Peep p, Node n) { if( n != null ) p.near.set(n._nid); } + + private void near(Peep p, Node n) { + if( n == null ) return; + add(p, n); + for( Node def : n._inputs ) add(p, def); + for( Node use : n._outputs ) add(p, use); + // These are wake-up dependents, not all nodes inspected by a rule. + // Read before the compiler drains the list; never move/clear it here. + for( int i = 0; i < n.nDeps(); i++ ) add(p, n.dep(i)); + } + + private int pos() { return _code._phase == CodeGen.Phase.Parse ? _code.P.pos() : -1; } + + private GraphSnapshot snap(Node extra) { + var roots = new ArrayList<Node>(); + roots.add(_code._stop); + if( _code._phase == CodeGen.Phase.Parse ) { + roots.add(_code.P._scope); + roots.addAll(_code.P._xScopes); + } + for( Peep p : _peeps ) if( !p.node.isDead() ) roots.add(p.node); + roots.add(extra); + return _graph.snap(_comp, 0, roots.toArray(Node[]::new)); + } + + private void emit(GraphSnapshot snap, int pos, GraphEvent evt) { + if( _off ) return; + // Assign steps on emission; attempts without progress do not consume frames. + snap = new GraphSnapshot(snap.ver(), _comp, _step++, snap.roots(), snap.nodes()); + try { + frame(snap, pos, evt); + } catch( IOException e ) { + // A disconnected display must not interrupt optimization. + _off = true; + _code._obs = null; + System.err.println("Graph viewer disconnected: " + e.getMessage()); + } + } +} 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); }); |