diff options
| author | Cliff Click <cliffc@acm.org> | 2026-09-23 16:35:50 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-09-23 16:35:50 -0700 |
| commit | 0f32001b466def0cee753557ad6e296cf15e2504 (patch) | |
| tree | 9e16038c574407bbd3f5c21f469c2df71e6835f8 /graph | |
| parent | 695429df954b084d2226fe2a6c1a47e1861bcc01 (diff) | |
| download | Simple-0f32001b466def0cee753557ad6e296cf15e2504.tar.gz Simple-0f32001b466def0cee753557ad6e296cf15e2504.zip | |
Keyboard shortcuts
Fast forward/reverse, pick-a-frame.
Shorter type names.
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/README.md | 94 | ||||
| -rw-r--r-- | graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java | 8 | ||||
| -rw-r--r-- | graph/src/main/java/com/seaofnodes/graph/GraphCapture.java | 2 | ||||
| -rw-r--r-- | graph/src/main/java/com/seaofnodes/graph/GraphGroups.java | 158 | ||||
| -rw-r--r-- | graph/src/main/java/com/seaofnodes/graph/GraphJson.java | 11 | ||||
| -rw-r--r-- | graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java | 8 | ||||
| -rw-r--r-- | graph/web/groups.js | 46 | ||||
| -rw-r--r-- | graph/web/index.html | 18 | ||||
| -rw-r--r-- | graph/web/layout.js | 161 | ||||
| -rw-r--r-- | graph/web/render.js | 71 | ||||
| -rw-r--r-- | graph/web/viewer.js | 82 |
11 files changed, 568 insertions, 91 deletions
diff --git a/graph/README.md b/graph/README.md index eb3e8d18..ac9af4d6 100644 --- a/graph/README.md +++ b/graph/README.md @@ -2,7 +2,8 @@ The browser application lives in `web/` and is shared by chapters 1–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 +`web/groups.js` projects folded regions into display nodes; `web/layout.js` +runs ELK layout in a browser worker; `web/render.js` draws SVG and handles selection, pan and zoom. Libraries live in `web/vendor/`, with one checked-in copy of each; chapters do not copy them during builds. @@ -27,8 +28,21 @@ 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. +or press **Ctrl+Enter** (**Cmd+Enter** on macOS). Use the arrows to step through +frames, the first/last buttons to jump to either end, or enter a frame number +and press **Enter**. The slider scrubs through available frames; its arrow keys +step and **Home/End** jump to either end. Keep `make view` running while using the tab. +Frame numbers start at 1. Jumps lay out only their destination. When the slider +moves during layout, the viewer finishes that calculation and then handles the +latest request, skipping intermediate requests. Already visited layouts stay cached. + +Functions and loops have enclosing boxes. Click **−** in a box's upper-left +corner to fold it into a thick-bordered node; click **+** to reopen it. +**Unfold all** restores the complete graph. Folds persist while stepping forward +or backward, including child folds inside a folded parent. Compiling a new +program resets them. Crossing edges attach to the folded node; hover an edge +for its original node IDs and input slot. Selection and peephole highlights +follow hidden nodes onto their enclosing folded box. 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 @@ -108,7 +122,8 @@ The JSON frame has this shape: "ver": 1, "comp": "compilation UUID", "step": 0, "roots": [1], "scope": 0, "nodes": [ {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null} - ] + ], + "groups": [] }, "pos": -1, "evt": { @@ -132,6 +147,8 @@ 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. +Each frame also caches its most recent folded layout, keyed by the folded +header IDs; changing folds recomputes that view without changing the snapshot. 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. @@ -153,8 +170,19 @@ definition ID. Value inputs stay along the top. Each Region (including a loop header) and its Phis form one layout row, with the Region on the left. Their boxes, ports, selections and node IDs stay separate. This also keeps a newly created Phi on its Region's row while the parser holds it. -Stops occupy the bottom row, beside the Parser box when it is present, even -before return edges attach. Chapter adapters identify Stops with `Kind.STOP`. +Stops occupy the bottom of the graph, beside the Parser box when it is present, +even before return edges attach. StopCUs share a row above their outer Stop; +StartCUs sit below Start, connected by their real control inputs. Chapter adapters +identify Stops with `Kind.STOP`. +Stops and chapter 25's Start/StartCU nodes use compact single-line boxes; their +full types remain in the tooltip and selection details. Start-to-Stop SCCP +feedback edges remain in the snapshot/details but have no drawn edge or port. +Chapter 25 omits its cached zero and XCtrl nodes when only keep references hold +them alive. Actual graph uses, including Scope bindings, make them visible. +Type printers use short names for common extrema, including `MemBot`/`MemTop`, +`StructBot`/`StructTop`, `PtrBot`/`PtrTop` and `FunBot`/`FunTop`. These aliases +apply only to the exact types; more precise aliases, fields and escape sets +still print normally. Integer and float types retain their existing short names. Scopes have named slots across the top, including control, memory and variable bindings. Edges leave these slots upward toward their definitions. They stay visible @@ -171,22 +199,56 @@ and get an arrow to their own cell. These marks disappear when real uses attach or parsing finishes; they do not add nodes or edges to the compiler graph. This identifies unconsumed values from the snapshot, not Java stack references. -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. +Function and loop membership comes from the compiler process; ELK lays out +the supplied hierarchy. This does not yet compute RPO or a full SESE hierarchy, +and placement can still shift substantially between rewrites. Each visited frame currently retains a full snapshot and layout; bounded history, checkpoints and deltas are also follow-up work. Pending graph work: -- Improve CFG placement with compiler-provided RPO and nested regions for - compilation units, functions and loops. +- Refine CFG placement with compiler-provided RPO, compilation-unit containers, + and fuller membership for unfinished loops and paths leaving loops. - Preserve positions across peepholes, then animate edits and zoom into the peep neighborhood before returning to the whole graph. - For large compilations, add checkpoints and forward deltas with a bounded cache of recent backward steps. +### Function and loop grouping + +Shared Java `GraphGroups` computes display ownership from detached snapshots. +The snapshot's `groups` array contains `{id, par, nodes}`: the header ID, parent +group ID (zero outside), and directly owned node IDs. A node has one display +home. Functions contain their CFG; natural loops nest inside functions and +other loops. Pinned values follow their control, floating values follow the +common enclosing group of their uses, and constants can remain outside. +Phi inputs belong to their incoming CFG paths when assigning floating values. +Scopes and Stops remain outside containers for their existing placement rules. + +Loop membership walks backward from the backedge to the header. Before that +backedge is attached, only the header and values anchored there belong to the +loop. Paths that leave via break/return can remain in the enclosing group. +This is conservative display grouping, not a SESE analysis or the compiler's +loop tree. Capture never invokes the compiler loop-tree pass, which can mutate +the graph by adding exits for infinite loops. No chapter-specific grouping +hooks or compiler edits are needed. + +Expanded groups are ELK compound layout containers with a visible border and +a fold button. Sibling functions/loops occupy disjoint boxes; nested loops +remain inside their parent. The hierarchy constrains layout and edge routing. + +Browser-side folding replaces the group's visible contents with one thick-bordered box, +its label, a hidden-node count and an unfold button. It hides internal edges and +redirects each crossing edge to the folded box, retaining its original node IDs +and use-slot index for details and selection. Crossing edges retain distinct +input ports; uses of the same hidden definition share its output port. This is a browser view of the +snapshot, not a compiler graph rewrite. + +Fold state persists by header ID across frames and backward playback, +including remembered child folds when a parent is unfolded. A folded group +containing a selected node or an active peephole carries that highlight. +Recompiling resets fold state along with frame history. + 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. @@ -202,7 +264,7 @@ 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, active scope, and nodes. +- `GraphSnapshot` is detached data: compilation key, step, roots, active scope, nodes and groups. 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. @@ -253,10 +315,10 @@ 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 +Functions and compilation-unit boundaries. Shared grouping uses these existing +IR facts to compute display membership. 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, +Types may be absent on newly constructed nodes. Node source locations and delta encoding remain follow-up work. All chapters use the observer events described below. diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java b/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java index 47bf3444..eaa308f9 100644 --- a/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java +++ b/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java @@ -18,6 +18,8 @@ public abstract class GraphAdapter<N> { protected abstract N out(N node, int idx); protected abstract GraphSnapshot.Node desc(N node); protected abstract boolean dead(N node); + // Omit cached helpers with no graph uses; still walk through them. + protected boolean show(N node) { return true; } protected int nDeps(N node) { return 0; } protected N dep(N node, int idx) { throw new IndexOutOfBoundsException(idx); } @@ -48,11 +50,11 @@ public abstract class GraphAdapter<N> { var rids = new int[roots.size()]; int len = 0; for( N root : roots ) - if( enq(root, seen, todo) ) rids[len++] = id(root); + if( enq(root, seen, todo) && show(root) ) rids[len++] = id(root); var nodes = new ArrayList<GraphSnapshot.Node>(); while( !todo.isEmpty() ) { N node = todo.removeFirst(); - nodes.add(desc(node)); + if( show(node) ) nodes.add(desc(node)); for( int i = 0; i < nIns(node); i++ ) enq(in(node, i), seen, todo); // Uses are a traversal shortcut, never the source of edge semantics. for( int i = 0; i < nOuts(node); i++ ) enq(out(node, i), seen, todo); @@ -60,7 +62,7 @@ public abstract class GraphAdapter<N> { // Determinism without reordering the compiler's use lists. nodes.sort(Comparator.comparingInt(GraphSnapshot.Node::id)); return new GraphSnapshot(GraphSnapshot.VER, comp, step, - Arrays.copyOf(rids, len), scope, nodes); + Arrays.copyOf(rids, len), scope, nodes, GraphGroups.build(nodes)); } private boolean enq(N node, ArrayList<N> seen, ArrayDeque<N> todo) { diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphCapture.java b/graph/src/main/java/com/seaofnodes/graph/GraphCapture.java index 4be65392..1a9c8c62 100644 --- a/graph/src/main/java/com/seaofnodes/graph/GraphCapture.java +++ b/graph/src/main/java/com/seaofnodes/graph/GraphCapture.java @@ -138,7 +138,7 @@ public abstract class GraphCapture<N> extends GraphObserver<N> { 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.scope(), snap.nodes()); + snap = new GraphSnapshot(snap.ver(), _comp, _step++, snap.roots(), snap.scope(), snap.nodes(), snap.groups()); try { _server.put(GraphJson.frame(snap, pos, evt)); } catch( IOException e ) { diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java b/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java new file mode 100644 index 00000000..75bb90e0 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java @@ -0,0 +1,158 @@ +package com.seaofnodes.graph; + +import com.seaofnodes.graph.GraphSnapshot.*; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.BitSet; + +/** Read-only display ownership, computed from detached snapshots, never compiler passes. */ +final class GraphGroups { + static ArrayList<Group> build(ArrayList<Node> nodes) { + var result = new ArrayList<Group>(); + boolean any=false; + for( Node n : nodes ) if( n.kind()==Kind.FUN || n.kind()==Kind.LOOP ) { any=true; break; } + if( !any ) return result; + int len = nodes.getLast().id()+1; + Node[] ns = new Node[len]; + for( Node n : nodes ) ns[n.id()] = n; + int[][] preds = new int[len][]; + int[] cnt = new int[len]; + for( Node n : nodes ) { + int[] ps = new int[n.edges().size()]; + int size=0; + for( Edge e : n.edges() ) + if( pred(n,e) && cfg(ns[e.def()]) ) { + ps[size++] = e.def(); + cnt[e.def()]++; + } + preds[n.id()] = Arrays.copyOf(ps,size); + } + int[][] uses = new int[len][]; + for( Node n : nodes ) uses[n.id()] = new int[cnt[n.id()]]; + Arrays.fill(cnt,0); + for( Node n : nodes ) for( int p : preds[n.id()] ) uses[p][cnt[p]++] = n.id(); + + // Function calls/returns never carry ownership into another function. + int[] fun = new int[len], work = new int[len]; + int head=0, tail=0; + for( Node n : nodes ) if( n.kind()==Kind.FUN ) { + fun[n.id()] = n.id(); + work[tail++] = n.id(); + } + while( head<tail ) { + int id = work[head++]; + for( int use : uses[id] ) if( fun[use]==0 ) { + fun[use] = fun[id]; + work[tail++] = use; + } + } + + // Natural loops: walk backwards from the backedge, stopping at the + // header. An unfinished loop has only its header until it closes. + var loops = new ArrayList<Node>(); + BitSet[] body = new BitSet[len]; + for( Node n : nodes ) if( n.kind()==Kind.LOOP ) { + int id = n.id(), back = def(n,2); + BitSet set = body[id] = new BitSet(); + set.set(id); + loops.add(n); + if( back==0 || ns[back]==null ) continue; + head=tail=0; + if( back!=id ) { set.set(back); work[tail++]=back; } + boolean closed=false, outside=false; + while( head<tail ) { + int cur = work[head++]; + if( fun[cur]!=fun[id] || ns[cur].kind()==Kind.FUN || + ns[cur].kind()==Kind.START || ns[cur].kind()==Kind.UNIT ) { outside=true; break; } + for( int p : preds[cur] ) { + if( p==id ) closed=true; + if( !set.get(p) ) { set.set(p); work[tail++]=p; } + } + } + if( outside || !closed ) { set.clear(); set.set(id); } + } + // Outer loops first. Simple's structured CFG makes these sets nested + // or disjoint. + loops.sort((a,b) -> Integer.compare(body[b.id()].cardinality(),body[a.id()].cardinality())); + int[] par = new int[len], home = new int[len]; + Arrays.fill(home,-1); + for( Node n : nodes ) if( cfg(n) ) home[n.id()] = fun[n.id()]; + for( Node n : loops ) { + int id=n.id(); + par[id]=home[id]; + for( int i=body[id].nextSetBit(0); i>=0; i=body[id].nextSetBit(i+1) ) home[i]=id; + } + for( Node n : nodes ) { + int id=n.id(); + if( n.kind()==Kind.SCOPE || n.kind()==Kind.STOP ) home[id]=0; + if( !cfg(n) && n.proj()==null && n.kind()!=Kind.PHI && + n.edges().stream().noneMatch(e -> e.def()!=0 && e.role()!=Role.ASSOC) ) home[id]=0; + int anchor = n.proj()!=null ? n.proj().par() : def(n,0); + if( !cfg(n) && n.kind()!=Kind.SCOPE && n.kind()!=Kind.STOP && + anchor!=0 && ns[anchor]!=null && cfg(ns[anchor]) ) + home[id]=home[anchor]; + } + // Floating values belong to the common enclosing group of their uses. + // A Phi's input is used on the corresponding predecessor, not at the + // header (especially the entry input of a loop Phi). + BitSet fixed = new BitSet(); + for( Node n : nodes ) if( home[n.id()]>=0 ) fixed.set(n.id()); + boolean changed; + do { + changed=false; + for( Node n : nodes ) for( Edge e : n.edges() ) { + int id=e.def(); + if( id==0 || ns[id]==null || fixed.get(id) || e.role()==Role.ASSOC ) continue; + int site=n.id(); + if( n.kind()==Kind.PHI && e.idx()>0 ) { + Node reg=ns[def(n,0)]; + site=reg==null ? 0 : def(reg,e.idx()); + } + int grp=site==0 ? 0 : home[site]; + if( grp<0 ) continue; + int next=lca(home[id],grp,par); + if( next!=home[id] ) { home[id]=next; changed=true; } + } + } while( changed ); + // Projections and their MultiNode are one display box. + for( Node n : nodes ) if( n.proj()!=null && n.proj().par()!=0 ) + home[n.id()]=home[n.proj().par()]; + for( Node n : nodes ) if( n.kind()==Kind.FUN || n.kind()==Kind.LOOP ) { + int id=n.id(), size=0; + for( Node m : nodes ) if( home[m.id()]==id ) size++; + int[] ids = new int[size]; + size=0; + for( Node m : nodes ) if( home[m.id()]==id ) ids[size++]=m.id(); + result.add(new Group(id,par[id],ids)); + } + return result; + } + + private static int lca(int a, int b, int[] par) { + if( a<0 ) return b; + for( int x=a; x!=0; x=par[x] ) + for( int y=b; y!=0; y=par[y] ) if( x==y ) return x; + return 0; + } + + private static int def(Node n, int idx) { + for( Edge e : n.edges() ) if( e.idx()==idx ) return e.def(); + return 0; + } + + private static boolean pred(Node n, Edge e) { + if( e.def()==0 || e.role()!=Role.CTRL ) return false; + return switch( n.kind() ) { + case REGION, LOOP -> e.idx()>0; + case CTRL -> e.idx()==0; + default -> false; + }; + } + + private static boolean cfg(Node n) { + return n!=null && switch( n.kind() ) { + case CTRL, REGION, LOOP, FUN, START, UNIT -> true; + default -> false; + }; + } +} diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphJson.java b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java index c920763a..fd37d5a9 100644 --- a/graph/src/main/java/com/seaofnodes/graph/GraphJson.java +++ b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java @@ -72,6 +72,17 @@ public class GraphJson { .append(",\"idx\":").append(proj.idx()).append('}'); sb.append('}'); } + sb.append("],\"groups\":["); + for( int i=0; i<snap.groups().size(); i++ ) { + if( i>0 ) sb.append(','); + var g = snap.groups().get(i); + sb.append("{\"id\":").append(g.id()).append(",\"par\":").append(g.par()).append(",\"nodes\":["); + for( int j=0; j<g.nodes().length; j++ ) { + if( j>0 ) sb.append(','); + sb.append(g.nodes()[j]); + } + sb.append("]}"); + } sb.append("]}"); } diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java index 53d74706..4d14ed10 100644 --- a/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java +++ b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java @@ -4,19 +4,23 @@ import java.util.ArrayList; /** A detached graph. Lists are read-only; scope is the active parser scope ID, or zero. */ public record GraphSnapshot(int ver, String comp, long step, - int[] roots, int scope, ArrayList<Node> nodes) { + int[] roots, int scope, ArrayList<Node> nodes, ArrayList<Group> groups) { public static final int VER = 1; public GraphSnapshot { roots = roots.clone(); nodes = new ArrayList<>(nodes); + groups = new ArrayList<>(groups); } @Override public int[] roots() { return roots.clone(); } - public enum Kind { DATA, CTRL, MEM, SCOPE, PHI, REGION, LOOP, FUN, UNIT, STOP } + public enum Kind { DATA, CTRL, MEM, SCOPE, PHI, REGION, LOOP, FUN, UNIT, START, STOP } public enum Role { DATA, CTRL, MEM, ASSOC } + /** Header ID, enclosing group (zero outside), and directly owned node IDs. */ + public record Group(int id, int par, int[] nodes) { } + /** IDs are stable within one compilation. Labels and types are plain text. */ public record Node(int id, String label, String type, Kind kind, ArrayList<Edge> edges, Projection proj) { diff --git a/graph/web/groups.js b/graph/web/groups.js new file mode 100644 index 00000000..6ee4e091 --- /dev/null +++ b/graph/web/groups.js @@ -0,0 +1,46 @@ +// A display projection of a snapshot. Original nodes and edge slots stay intact. +class GraphGroups { + static view(snap, folded) { + const raw = new Map(snap.nodes.map(n => [n.id, n])); + const groups = new Map((snap.groups || []).map(g => [g.id, {...g, members: new Set(g.nodes)}])); + const home = new Map(), cover = new Map(); + for (const g of groups.values()) for (const id of g.nodes) home.set(id, g.id); + for (const g of groups.values()) { + for (let p = groups.get(g.par); p; p = groups.get(p.par)) + for (const id of g.nodes) p.members.add(id); + } + for (const n of snap.nodes) { + let id = n.id; + for (let g = groups.get(home.get(id)); g; g = groups.get(g.par)) + if (folded.has(g.id)) id = g.id; + cover.set(n.id, id); + } + const nodes = [], byId = new Map(); + for (const n of snap.nodes) { + if (cover.get(n.id) !== n.id) continue; + const fold = groups.has(n.id) && folded.has(n.id); + const v = {...n, edges: [], fold: fold ? groups.get(n.id) : null}; + if (fold) { + v.proj = null; + v.type = `${v.fold.members.size} nodes folded`; + } + nodes.push(v); byId.set(n.id, v); + } + for (const n of snap.nodes) for (const e of n.edges) { + const use = byId.get(cover.get(n.id)), def = cover.get(e.def) || 0; + if (use.fold && (!def || def === use.id)) continue; + use.edges.push({...e, idx: use.fold ? use.edges.length : e.idx, def, + orig: {use: n.id, def: e.def, idx: e.idx}}); + } + // Expanded groups only; a folded group is represented by its header box. + const open = [...groups.values()].filter(g => !folded.has(g.id) && cover.get(g.id) === g.id); + const depth = g => { + let n = 0; + for (; g.par; g = groups.get(g.par)) n++; + return n; + }; + // Paint outer containers before inner ones, even after headers are cloned. + open.sort((a,b) => depth(a) - depth(b) || a.id - b.id); + return {snap: {...snap, nodes}, raw, home, cover, open, groups}; + } +} diff --git a/graph/web/index.html b/graph/web/index.html index a568cbc6..909f7b1d 100644 --- a/graph/web/index.html +++ b/graph/web/index.html @@ -28,6 +28,12 @@ .node.near .box { stroke:#c18221; stroke-width:2; } .node.focus .box { stroke:#9c4900; stroke-width:3; } .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } .head { font-size:10px; fill:#596674; } .label { font-size:12px; fill:#152330; font-weight:600; } .type { font-size:11px; fill:#455768; } @@ -38,13 +44,16 @@ #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } - .controls { display:flex; justify-content:center; align-items:center; gap:4px; padding:4px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } .button { color:white; background:black; font-size:20px; min-width:30px; } .button:disabled { background:grey; } .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } </style> <script src="vendor/d3.v7.min.js"></script> <script src="vendor/elk-api.js"></script> + <script src="groups.js"></script> <script src="layout.js"></script> <script src="render.js"></script> </head> @@ -58,6 +67,7 @@ <div class="tools"> <button id="fit" type="button" disabled>Fit</button> <button id="save" type="button" disabled>Save SVG</button> + <button id="unfold" type="button" disabled>Unfold all</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> @@ -67,11 +77,15 @@ </div> <div id="graph"><div id="elk"></div><pre id="detail" hidden></pre></div> <div class="controls"> + <button id="doFirst" type="button" onclick="doFirst()" class="button" aria-label="First frame" title="First frame">|⮜</button> <button id="doPrev" type="button" onclick="doPrev()" class="button" aria-label="Previous frame">⮜</button> - <span id="N" class="count">0</span> + <label for="N">Frame</label> + <input id="N" class="count" type="number" min="1" max="1" step="1" value="0" disabled title="Enter a frame number"> <span>/</span> <span id="len" class="count">0</span> <button id="doNext" type="button" onclick="doNext()" class="button" aria-label="Next frame">⮞</button> + <button id="doLast" type="button" onclick="doLast()" class="button" aria-label="Last frame" title="Last available frame">⮞|</button> + <input id="scrub" type="range" min="1" max="1" step="1" value="1" disabled aria-label="Frame slider"> <button id="doExit" type="button" onclick="doExit()" class="button">Exit</button> </div> </div> diff --git a/graph/web/layout.js b/graph/web/layout.js index b192de87..53e26f53 100644 --- a/graph/web/layout.js +++ b/graph/web/layout.js @@ -11,9 +11,20 @@ class GraphLayout { return chars.length > 44 ? chars.slice(0, 43).join("") + "…" : chars.join(""); } - async run(snap, evt) { + async run(snap, evt, folded = new Set()) { + const view = GraphGroups.view(snap, folded); + snap = view.snap; + const raw = new Map(snap.nodes.map(n => [n.id, n])); + const outs = new Map(); + for (const n of snap.nodes) for (const e of n.edges) if (raw.get(e.def)?.fold) { + if (!outs.has(e.def)) outs.set(e.def, new Set()); + outs.get(e.def).add(e.orig.def); + } + // The whole-program SCCP cycle is not source control flow. + const hidden = (n, e) => ["START", "UNIT"].includes(n.kind) && raw.get(e.def)?.kind === "STOP"; const nodes = snap.nodes.map(n => { const label = this.clip(n.label), type = this.clip(n.type); + const compact = ["START", "UNIT", "STOP"].includes(n.kind); let w = Math.ceil(Math.max(120, this.ctx.measureText(label).width + 24, this.ctx.measureText(type).width + 24, (n.edges.length + 1) * 18)); const scope = n.kind === "SCOPE"; @@ -21,8 +32,14 @@ class GraphLayout { this.ctx.measureText(e.label || "[" + e.idx + "]").width + 24))) : []; if (scope) w = Math.ceil(Math.max(120, this.ctx.measureText(label).width + 24, cols.reduce((sum, w) => sum + w, 0))); - return {id: "n" + n.id, width: w, height: 62, - ports: [], n, label, type, scope, cols, stop: n.kind === "STOP", ox: 0, oy: 0}; + if (compact) w = Math.ceil(Math.max(72, this.ctx.measureText(`#${n.id} ${label}`).width + 24, + (n.edges.filter(e => !hidden(n, e)).length + 1) * 18)); + if (n.fold) { + const slot = Math.max(18, ...n.edges.map(e => this.ctx.measureText(`${e.orig.use}:${e.orig.idx}`).width + 12)); + w = Math.ceil(Math.max(200, w + 32, (n.edges.length + 1) * slot, ((outs.get(n.id)?.size || 0) + 1) * 18)); + } + return {id: "n" + n.id, width: w, height: compact ? 26 : 62, + ports: [], n, label, type, scope, cols, compact, stop: n.kind === "STOP", ox: 0, oy: 0}; }); const byId = new Map(nodes.map(n => [n.n.id, n])); const parsing = evt?.phase === "Parse" && evt.kind !== "PHASE"; @@ -41,16 +58,16 @@ class GraphLayout { for (const n of nodes) { const par = byId.get(n.n.proj?.par); // A projection without its parent still gets a standalone box. - if (!par || par.n.proj) continue; + if (!par || par.n.proj || par.n.fold || n.n.fold) continue; if (!projs.has(par)) projs.set(par, []); projs.get(par).push(n); n.par = par; } const phis = new Map(); for (const n of nodes) { - if (n.n.kind !== "PHI") continue; + if (n.n.kind !== "PHI" || n.n.fold) continue; const reg = byId.get(n.n.edges.find(e => e.idx === 0)?.def); - if (!reg || !["REGION", "LOOP", "FUN"].includes(reg.n.kind)) continue; + if (!reg || reg.n.fold || !["REGION", "LOOP", "FUN"].includes(reg.n.kind)) continue; if (!phis.has(reg)) phis.set(reg, []); phis.get(reg).push(n); n.reg = reg; @@ -84,10 +101,11 @@ class GraphLayout { (p.width - p.cols.reduce((sum, w) => sum + w, 0)) / p.cols.length : 0; let x = 0; for (const [idx, e] of p.n.edges.entries()) { + if (hidden(p.n, e)) continue; // The parent/projection link is represented by the shared box. if (p.par && e.idx === 0 && e.def === p.par.n.id) continue; // Phi's Region input is a local left-facing marker, not a routed edge. - if (p.n.kind === "PHI" && e.idx === 0) continue; + if (p.reg && e.idx === 0) continue; if (p.scope) { const span = p.cols[idx] + extra; ports.push({id: p.id + "i" + e.idx, x: x + span / 2 - 3, y: -3, span, @@ -104,52 +122,93 @@ class GraphLayout { ports.push({id: p.id + "o", x: p.ox + (side === "EAST" ? p.width : p.width / 2) - 3, y: p.oy + (side === "EAST" ? p.height / 2 : p.height) - 3, width: 6, height: 6, layoutOptions: {"elk.port.side": side}}); + const defs = [...(outs.get(p.n.id) || [])]; + for (const [i, id] of defs.entries()) ports.push({id: p.id + "o" + id, + x: p.width * (i + 1) / (defs.length + 1) - 3, y: p.height - 3, + width: 6, height: 6, layoutOptions: {"elk.port.side": "SOUTH"}}); } - return {id: n.id, width, height: n.height * (slots.length ? 2 : 1), ports, parts}; + return {id: n.id, width, height: n.height + (slots.length ? Math.max(...slots.map(p => p.height)) : 0), ports, parts}; }); const edges = []; for (const use of snap.nodes) { for (const e of use.edges) { - if (!e.def) continue; - if (use.kind === "PHI" && e.idx === 0) continue; + if (!e.def || hidden(use, e)) continue; + if (byId.get(use.id).reg && e.idx === 0) continue; if (byId.get(use.id).par && e.idx === 0 && e.def === use.proj.par) continue; - const id = "e" + use.id + "i" + e.idx; + const id = "e" + e.orig.use + "i" + e.orig.idx; const reg = byId.get(use.edges[0]?.def)?.n; - const back = e.idx === 2 && (use.kind === "LOOP" || + const back = !use.fold && e.idx === 2 && (use.kind === "LOOP" || (use.kind === "PHI" && reg?.kind === "LOOP")); - edges.push({id, use: use.id, def: e.def, idx: e.idx, role: e.role, label: e.label, + edges.push({id, use: use.id, def: e.def, idx: e.orig.idx, orig: e.orig, role: e.role, label: e.label, bind: use.kind === "SCOPE", // Layout follows value/control flow downward. SVG arrows point back // from use to def, matching Simple's actual edge direction. - sources: ["n" + e.def + "o"], targets: ["n" + use.id + "i" + e.idx], + sources: ["n" + e.def + "o" + (byId.get(e.def).n.fold ? e.orig.def : "")], targets: ["n" + use.id + "i" + e.idx], layoutOptions: {"elk.layered.priority.direction": back ? 0 : e.role === "CTRL" ? 10 : 1}}); } } - const graph = await this.elk.layout({ - id: "root", children: groups.filter(g => !g.parts[0].scope && !g.parts[0].stop).map(({parts, ...box}) => ({...box, - layoutOptions: {"elk.portConstraints": "FIXED_POS", - // Keep a projection with its parent even when that parent has real uses. - "elk.layered.layering.layerConstraint": parts.length === 1 && parts[0].held ? "LAST_SEPARATE" : "NONE"} - })), + const opts = { + "elk.algorithm": "layered", "elk.direction": "DOWN", "elk.edgeRouting": "ORTHOGONAL", + "elk.hierarchyHandling": "INCLUDE_CHILDREN", + "elk.spacing.nodeNode": 32, "elk.layered.spacing.nodeNodeBetweenLayers": 48, + "elk.padding": "[top=24,left=24,bottom=24,right=24]", + "elk.separateConnectedComponents": held.length === 0, + // ELK 0.12's model-order presort fails on nested hierarchy edge dummies. + "elk.layered.considerModelOrder.strategy": view.open.length ? "NONE" : "NODES_AND_EDGES", + "elk.randomSeed": 1 + }; + const containers = new Map(view.open.map(g => [g.id, {id: "g" + g.id, children: [], + layoutOptions: {...opts, "elk.padding": "[top=58,left=28,bottom=28,right=28]"}}])); + const children = []; + const add = (par, box) => (containers.get(par)?.children || children).push(box); + for (const g of view.open) add(g.par, containers.get(g.id)); + for (const {parts, ...box} of groups) { + const n = parts[0]; + if (n.scope || n.stop) continue; + // The folded header replaces its own container inside the parent group. + const par = n.n.fold ? n.n.fold.par : view.home.get(n.n.id); + add(par, {...box, layoutOptions: {"elk.portConstraints": "FIXED_POS", + // LAST_SEPARATE conflicts with ELK's hierarchical boundary ports. + "elk.layered.layering.layerConstraint": parts.length === 1 && n.held ? + (view.open.length ? "LAST" : "LAST_SEPARATE") : "NONE"}}); + } + const input = { + id: "root", children, // Scope bindings and lifetime associations must not impose CFG ranks. edges: edges.filter(e => e.role !== "ASSOC" && !e.bind && !byId.get(e.def).scope && !byId.get(e.use).stop && !byId.get(e.def).stop).map(e => ({ id: e.id, sources: e.sources, targets: e.targets, layoutOptions: e.layoutOptions })), - layoutOptions: { - "elk.algorithm": "layered", "elk.direction": "DOWN", "elk.edgeRouting": "ORTHOGONAL", - "elk.spacing.nodeNode": 32, "elk.layered.spacing.nodeNodeBetweenLayers": 48, - "elk.padding": "[top=24,left=24,bottom=24,right=24]", - "elk.separateConnectedComponents": held.length === 0, - "elk.layered.considerModelOrder.strategy": "NODES_AND_EDGES", - "elk.randomSeed": 1 - } - }); + layoutOptions: opts + }; + // ELK expects an edge on the lowest container containing both endpoints. + const portBox = new Map(), parents = new Map(); + const index = box => { + for (const p of box.ports || []) portBox.set(p.id, box); + for (const child of box.children || []) { parents.set(child, box); index(child); } + }; + index(input); + const flow = input.edges; + input.edges = []; + for (const e of flow) { + const ancestors = new Set(); + for (let p = parents.get(portBox.get(e.sources[0])); p; p = parents.get(p)) ancestors.add(p); + let p = parents.get(portBox.get(e.targets[0])); + while (!ancestors.has(p)) p = parents.get(p); + (p.edges ||= []).push(e); + } + const graph = await this.elk.layout(input); // Place scopes and Stops after the flow graph; their ports stay local. for (const g of groups.filter(g => g.parts[0].scope || g.parts[0].stop)) graph.children.push({...g, x: 0, y: 0}); - const boxes = new Map(graph.children.map(n => [n.id, n])); - const routes = new Map((graph.edges || []).map(e => [e.id, e])); + const boxes = new Map(), routes = new Map(); + const collect = (box, x, y) => { + box.x = (box.x || 0) + x; box.y = (box.y || 0) + y; + boxes.set(box.id, box); + for (const e of box.edges || []) routes.set(e.id, {e, box}); + for (const child of box.children || []) collect(child, box.x, box.y); + }; + collect(graph, 0, 0); for (const group of groups) { const box = boxes.get(group.id); const ports = new Map(box.ports.map(p => [p.id, p])); @@ -157,13 +216,14 @@ class GraphLayout { n.x = box.x + n.ox; n.y = box.y + n.oy; // Keep semantic nodes/slots intact for selection and neighborhood marks. n.ports = n.n.edges.map(e => { - if (n.n.kind === "PHI" && e.idx === 0) + if (n.reg && e.idx === 0) return {id: n.id + "i0", x: -6, y: n.height / 2 - 3, width: 6, height: 6, reg: true, edge: e}; const p = ports.get(n.id + "i" + e.idx); return p && {...p, x: p.x - n.ox, y: p.y - n.oy, edge: e}; }).filter(Boolean); const out = ports.get(n.id + "o"); n.ports.push({...out, x: out.x - n.ox, y: out.y - n.oy}); + for (const id of outs.get(n.n.id) || []) n.ports.push(ports.get(n.id + "o" + id)); } } // Saved scopes describe suspended parser states at their control points. @@ -193,8 +253,21 @@ class GraphLayout { } // Parser ownership is an overlay, never an IR node or an ELK flow edge. const parser = owned.length ? {width: Math.max(180, (owned.length + 1) * 18), height: 36} : null; - // Stop belongs at the bottom even before any Return has attached to it. - const foot = [...nodes.filter(n => n.stop), ...(parser ? [parser] : [])]; + // Stack Stop inputs before their collector: StopCUs above the outer Stop. + // Peers share a row, so adding CUs costs width rather than another level. + const pending = new Set(nodes.filter(n => n.stop)), rows = []; + while (pending.size) { + const row = [...pending].filter(n => !n.n.edges.some(e => pending.has(byId.get(e.def)))); + // A malformed cycle should still be drawable. + if (!row.length) row.push(...pending); + for (const n of row) pending.delete(n); + rows.push({nodes: row, width: row.reduce((sum, n) => sum + n.width, 0) + (row.length - 1) * 32, + height: Math.max(...row.map(n => n.height))}); + } + const stops = rows.length ? {width: Math.max(...rows.map(r => r.width)), + height: rows.reduce((sum, r) => sum + r.height, 0) + (rows.length - 1) * 32} : null; + // The whole Stop stack stays below the flow graph, beside the Parser. + const foot = [...(stops ? [stops] : []), ...(parser ? [parser] : [])]; if (foot.length) { const width = foot.reduce((sum, n) => sum + n.width, 0) + (foot.length - 1) * 32; const height = Math.max(...foot.map(n => n.height)); @@ -207,6 +280,18 @@ class GraphLayout { } graph.height += height + 48; } + if (stops) { + let y = stops.y; + for (const row of rows) { + let x = stops.x + (stops.width - row.width) / 2; + for (const n of row.nodes) { + n.x = x; + n.y = y; + x += n.width + 32; + } + y += row.height + 32; + } + } if (parser) { owned.sort((a, b) => a.x - b.x || a.n.id - b.n.id); parser.ports = owned.map((n, i) => ({id: "parser-i" + n.n.id, @@ -224,12 +309,14 @@ class GraphLayout { const u = use.x + b.x + 3, v = use.y + b.y + 3; e.path = `M${x},${y} C${x},${y + 24} ${u},${v - 24} ${u},${v}`; } else { - e.path = routes.get(e.id).sections.map(s => + const route = routes.get(e.id), origin = boxes.get(route.e.container) || route.box; + e.path = route.e.sections.map(s => [s.startPoint, ...(s.bendPoints || []), s.endPoint] - .map((p, i) => `${i ? "L" : "M"}${p.x},${p.y}`).join(" ")).join(" "); + .map((p, i) => `${i ? "L" : "M"}${p.x + origin.x},${p.y + origin.y}`).join(" ")).join(" "); } } - return {width: graph.width, height: graph.height, nodes, edges, + return {width: graph.width, height: graph.height, nodes, edges, raw: view.raw, cover: view.cover, + groups: view.open.map(g => ({...g, ...boxes.get("g" + g.id), gid: g.id, n: view.raw.get(g.id)})), parser, scope: active?.n.id || 0, scopes: new Set(owned.filter(n => n.scope).map(n => n.n.id)), held: new Set(held.map(n => n.n.id))}; } diff --git a/graph/web/render.js b/graph/web/render.js index 883475f5..f0b622db 100644 --- a/graph/web/render.js +++ b/graph/web/render.js @@ -16,6 +16,7 @@ class GraphView { .append("path").attr("d", "M0,-4L8,0L0,4Z").attr("fill", color); } this.world = this.svg.append("g"); + this.regions = this.world.append("g").attr("class", "regions"); this.links = this.world.append("g").attr("class", "edges"); this.parser = this.world.append("g").attr("class", "parser"); this.nodes = this.world.append("g").attr("class", "nodes"); @@ -41,6 +42,18 @@ class GraphView { } this.scene = scene; this.evt = evt; + const regions = this.regions.selectAll("g.region").data(scene.groups || [], g => g.gid).join(enter => { + const g = enter.append("g").attr("class", "region"); + g.append("rect").attr("class", "region-box").attr("rx", 8); + g.append("text").attr("class", "label").attr("x", 34).attr("y", 22); + g.append("title"); + return g; + }).attr("transform", g => `translate(${g.x},${g.y})`); + regions.select("rect.region-box").attr("width", g => g.width).attr("height", g => g.height) + .attr("fill", g => g.n.kind === "LOOP" ? "#f1f6fc" : "#fff8ec"); + regions.select("text.label").text(g => (`#${g.gid} ${g.n.label}`).slice(0, Math.max(12, Math.floor((g.width-48)/7)))); + regions.select("title").text(g => `${g.n.label} · ${g.members.size} nodes`); + regions.each((g, i, items) => this.foldButton(d3.select(items[i]), g.gid, false, 8, 8)); 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]) @@ -49,7 +62,7 @@ class GraphView { d3.select(this).selectAll("title").data([e]).join("title") .text(e.role === "PARSER" ? (e.scope ? `Parser holds ${e.active ? "active" : "saved"} scope #${e.def}` : `Parser holds #${e.def}; no graph users yet`) : - `#${e.use}[${e.idx}] → #${e.def} · ${e.role}${e.label ? " · " + e.label : ""}`); + `#${e.orig?.use ?? e.use}[${e.idx}] → #${e.orig?.def ?? e.def} · ${e.role}${e.label ? " · " + e.label : ""}`); }); this.parser.selectAll("g").data(scene.parser ? [scene.parser] : []).join(enter => { const g = enter.append("g"); @@ -73,20 +86,22 @@ class GraphView { }); boxes.attr("id", n => n.id).attr("data-id", n => n.n.id) .classed("held", n => !!n.held) + .classed("folded", n => !!n.n.fold) .attr("transform", n => `translate(${n.x},${n.y})`) .on("click", (event, n) => { event.stopPropagation(); this.select(n.n.id); }); boxes.select("path.box").attr("d", n => this.shape(n)) .attr("fill", n => ({CTRL: "#fff1c4", REGION: "#fff1c4", LOOP: "#ffe0ab", FUN: "#ffe0ab", - UNIT: "#ffe0ab", STOP: "#fff1c4", MEM: "#dcecff", PHI: "#f5e4fa", SCOPE: "#e5e0ff", DATA: "#edf3f7"})[n.n.kind]); + UNIT: "#ffe0ab", START: "#fff1c4", STOP: "#fff1c4", MEM: "#dcecff", PHI: "#f5e4fa", SCOPE: "#e5e0ff", DATA: "#edf3f7"})[n.n.kind]); boxes.select("text.head").attr("y", n => n.scope ? 47 : 15) - .text(n => `#${n.n.id}${n.n.proj ? " · p" + n.n.proj.idx : ""}`); - boxes.select("text.label").attr("x", n => n.width / 2).attr("y", n => n.scope ? 51 : 33) - .text(n => n.label); - boxes.select("text.type").attr("x", n => n.width / 2).text(n => n.scope ? "" : n.type); + .text(n => n.compact ? "" : `#${n.n.id}${n.n.proj ? " · p" + n.n.proj.idx : ""}`); + boxes.select("text.label").attr("x", n => n.width / 2).attr("y", n => n.compact ? 17 : n.scope ? 51 : 33) + .text(n => n.compact ? `#${n.n.id} ${n.label}` : n.label); + boxes.select("text.type").attr("x", n => n.width / 2).text(n => n.scope || n.compact ? "" : n.type); boxes.select("title").text(n => this.info(n.n)); boxes.each((n, i, groups) => { - const ports = n.ports.filter(p => p.id !== n.id + "o"); + const ports = n.ports.filter(p => p.edge); const group = d3.select(groups[i]); + this.foldButton(group, n.n.fold?.id, true, n.width - 24, 6); group.selectAll("line.row").data(n.scope ? ports : [], p => p.id).join("line") .attr("class", "row").attr("x1", (p, i) => i ? p.x + 3 - p.span / 2 : 0) .attr("x2", (p, i) => i ? p.x + 3 - p.span / 2 : n.width) @@ -106,7 +121,7 @@ class GraphView { }); group.selectAll("text.slot").data(ports, p => p.id).join("text") .attr("class", "slot").attr("x", p => p.reg ? -10 : p.x + 3).attr("y", p => p.y - 4) - .attr("text-anchor", "middle").text(p => p.edge.idx); + .attr("text-anchor", "middle").text(p => n.n.fold ? `${p.edge.orig.use}:${p.edge.orig.idx}` : p.edge.idx); }); this.assocs(document.getElementById("assocs").checked); this.mark(); @@ -114,10 +129,29 @@ class GraphView { if (this.auto) this.fit(); } + foldButton(host, id, folded, x, y) { + const btn = host.selectAll("g.fold-btn").data(id ? [id] : []).join(enter => { + const g = enter.append("g").attr("class", "fold-btn").attr("role", "button").attr("tabindex", 0); + g.append("rect").attr("width", 16).attr("height", 16).attr("rx", 2); + g.append("text").attr("x", 8).attr("y", 12).attr("text-anchor", "middle"); + g.append("title"); + return g; + }).attr("transform", `translate(${x},${y})`) + .attr("aria-label", `${folded ? "Unfold" : "Fold"} region #${id}`) + .on("click", (event, id) => { event.stopPropagation(); this.onFold?.(id); }) + .on("keydown", (event, id) => { + if (event.key === "Enter" || event.key === " ") { + event.preventDefault(); event.stopPropagation(); this.onFold?.(id); + } + }); + btn.select("text").text(folded ? "+" : "−"); + btn.select("title").text(folded ? "Unfold region" : "Fold region"); + } + shape(n) { const w = n.width, h = n.height; // A MultiNode and its projection cells tile one rectangular box. - if (n.cell || ["CTRL", "UNIT", "STOP"].includes(n.n.kind)) return `M0,0H${w}V${h}H0Z`; + if (n.cell || ["CTRL", "UNIT", "START", "STOP"].includes(n.n.kind)) return `M0,0H${w}V${h}H0Z`; if (n.n.kind === "REGION") return `M12,0H${w - 12}L${w},${h}H0Z`; if (n.n.kind === "PHI") return `M12,0H${w - 12}L${w},${h / 2}L${w - 12},${h}H12L0,${h / 2}Z`; if (n.n.kind === "MEM" || n.n.kind === "FUN") @@ -128,7 +162,10 @@ class GraphView { } info(n) { + const fold = this.scene.nodes.find(v => v.n.id === n.id)?.n.fold; + n = this.scene.raw?.get(n.id) || n; return `#${n.id} ${n.label}${n.proj ? "\nProjection " + n.proj.idx + " of #" + n.proj.par : ""}` + + (fold ? `\n${fold.members.size} nodes folded` : "") + (this.scene.held.has(n.id) ? "\nHeld by parser; no graph users yet" : "") + (this.scene.scopes.has(n.id) ? (this.scene.scope === n.id ? "\nActive parser scope" : "\nSaved parser scope") : "") + `\n${n.type || "Type not computed"}\n\n` + n.edges.map(e => @@ -137,12 +174,14 @@ class GraphView { select(id) { this.pick = id; - const node = this.scene?.nodes.find(n => n.n.id === id); - this.nodes.selectAll("g.node").classed("selected", n => n.n.id === id); - this.links.selectAll("path.edge").classed("selected", e => id !== 0 && (e.use === id || e.def === id)); + const node = this.scene?.raw?.get(id) || this.scene?.nodes.find(n => n.n.id === id)?.n; + this.nodes.selectAll("g.node").classed("selected", n => n.n.id === (this.scene.cover?.get(id) || id)); + this.links.selectAll("path.edge").classed("selected", e => id !== 0 && + ((e.orig?.use ?? e.use) === id || (e.orig?.def ?? e.def) === id || e.use === id || e.def === id)); const detail = document.getElementById("detail"); detail.hidden = !id; - detail.textContent = node ? this.info(node.n) : `#${id} is absent in this frame.`; + const box = this.scene?.cover?.get(id); + detail.textContent = node ? this.info(node) + (box && box !== id ? `\nInside folded region #${box}` : "") : `#${id} is absent in this frame.`; } assocs(show) { this.links.selectAll(".ASSOC").style("display", e => show || e.bind ? null : "none"); } @@ -151,8 +190,10 @@ class GraphView { 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)); + this.nodes.selectAll("g.node").classed("near", n => near.has(n.n.id) || + n.n.fold && [...n.n.fold.members].some(id => near.has(id))) + .classed("focus", n => show && (n.n.id === evt?.node || n.n.id === evt?.repl || + n.n.fold && (n.n.fold.members.has(evt?.node) || n.n.fold.members.has(evt?.repl)))); } // Save the whole graph at its layout size, independent of pan/zoom. diff --git a/graph/web/viewer.js b/graph/web/viewer.js index 4a88245b..77703b71 100644 --- a/graph/web/viewer.js +++ b/graph/web/viewer.js @@ -1,6 +1,8 @@ // Connection and playback state are independent of renderer initialization. const program = document.getElementById("program"); const status = document.getElementById("status"); +const frameNo = document.getElementById("N"); +const scrub = document.getElementById("scrub"); let socket; let renderer; let layout; @@ -8,6 +10,9 @@ let rendererReady = false; let rendering = false; let frames = []; let current = -1; +let wanted = -1; +const folded = new Set(); +const foldKey = () => [...folded].sort((a,b) => a-b).join(","); let generation = 0; let done = false; let compiling = false; @@ -20,15 +25,22 @@ function updateUI() { !rendererReady ? "Connected; initializing graph renderer..." : busy ? busy : compiling ? "Compiling... " + frames.length + " frames received" : done ? frames.length + " frames ready" : "Connected"); - document.getElementById("N").textContent = current < 0 ? "0" : String(current + 1); + const at = wanted >= 0 ? wanted : current; + if (document.activeElement !== frameNo) frameNo.value = String(at + 1); + frameNo.max = scrub.max = String(Math.max(1, frames.length)); + frameNo.disabled = scrub.disabled = !rendererReady || !frames.length; + scrub.value = String(Math.max(1, at + 1)); + scrub.setAttribute("aria-valuetext", `Frame ${at + 1} of ${frames.length}`); document.getElementById("len").textContent = String(frames.length); - document.getElementById("doPrev").disabled = rendering || current <= 0; - document.getElementById("doNext").disabled = - !rendererReady || rendering || current + 1 >= frames.length; + document.getElementById("doFirst").disabled = document.getElementById("doPrev").disabled = + !rendererReady || at <= 0; + document.getElementById("doLast").disabled = document.getElementById("doNext").disabled = + !rendererReady || !frames.length || at + 1 >= frames.length; 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("unfold").disabled = !folded.size; document.getElementById("assocs").disabled = !frames[current]?.snap; document.getElementById("near").disabled = !frames[current]?.evt; const evt = frames[current]?.evt; @@ -47,6 +59,7 @@ function updateUI() { function reportError(error) { failure = "Viewer error: " + (error && error.message || error || "Graph rendering failed"); rendering = false; + wanted = -1; busy = ""; updateUI(); console.error(error); @@ -66,7 +79,9 @@ function get_program() { generation++; frames = []; current = -1; + wanted = -1; done = false; + folded.clear(); compiling = true; failure = ""; document.getElementById("detail").hidden = true; @@ -75,17 +90,31 @@ function get_program() { } async function render(index) { - if (!rendererReady || rendering || index < 0 || index >= frames.length) return; + if (!rendererReady || index < 0 || index >= frames.length) return; + wanted = index; + if (rendering) { updateUI(); return; } const frameGeneration = generation; rendering = true; - const frame = frames[index]; - busy = !frame.layout ? "Laying out frame " + (index + 1) + "..." : "Drawing..."; - updateUI(); try { if (!layout) layout = new GraphLayout(); - if (!frame.layout) frame.layout = await layout.run(frame.snap, frame.evt); - if (generation === frameGeneration) { - renderer.show(frame.snap, frame.layout, frame.evt); + while (wanted >= 0 && generation === frameGeneration) { + index = wanted; + const frame = frames[index]; + const key = foldKey(); + let scene = key ? (frame.foldKey === key ? frame.foldLayout : null) : frame.layout; + busy = !scene ? "Laying out frame " + (index + 1) + "..." : "Drawing..."; + updateUI(); + if (!scene) { + scene = await layout.run(frame.snap, frame.evt, new Set(folded)); + // Keep the ordinary layout plus only the most recent folded variant. + if (key) { frame.foldKey = key; frame.foldLayout = scene; } + else frame.layout = scene; + } + if (generation !== frameGeneration) break; + // Scrubbing can change the destination while ELK works. Draw only the + // latest request, without computing all the intervening frames. + if (wanted !== index || foldKey() !== key) continue; + renderer.show(frame.snap, scene, frame.evt); if (frame.pos >= 0) { // A newline or EOF has no visible character to highlight. Show the last // parsed character there, rather than losing the position indicator. @@ -93,20 +122,34 @@ async function render(index) { while (pos > 0 && (!program.value[pos] || /\s/.test(program.value[pos]))) pos--; program.setSelectionRange(pos, pos + 1); // Focus after selecting, so the browser brings the new position into view. - program.focus({preventScroll: true}); + if (document.activeElement !== frameNo && document.activeElement !== scrub) + program.focus({preventScroll: true}); } + current = index; + wanted = -1; } rendering = false; busy = ""; - if (generation === frameGeneration) current = index; updateUI(); } catch (error) { reportError(error); } } -function doNext() { render(current + 1); } -function doPrev() { render(current - 1); } +function doFirst() { render(0); } +function toggleFold(id) { + if (folded.has(id)) folded.delete(id); else folded.add(id); + render(wanted >= 0 ? wanted : current); +} +function doLast() { render(frames.length - 1); } +function doNext() { render((wanted >= 0 ? wanted : current) + 1); } +function doPrev() { render((wanted >= 0 ? wanted : current) - 1); } +function jump() { + const n = frameNo.valueAsNumber; + const index = Number.isFinite(n) ? Math.max(0, Math.min(frames.length - 1, Math.trunc(n) - 1)) : current; + frameNo.value = String(index + 1); + render(index); +} function doExit() { if (socket && socket.readyState === WebSocket.OPEN) socket.send("null"); } @@ -119,6 +162,14 @@ program.addEventListener("keydown", event => { } }); document.getElementById("compile").addEventListener("click", get_program); +document.getElementById("unfold").addEventListener("click", () => { + folded.clear(); render(wanted >= 0 ? wanted : current); +}); +frameNo.addEventListener("change", jump); +frameNo.addEventListener("keydown", event => { + if (event.key === "Enter") { event.preventDefault(); jump(); } +}); +scrub.addEventListener("input", () => render(scrub.valueAsNumber - 1)); document.getElementById("fit").addEventListener("click", () => { renderer.auto = true; renderer.fit(); @@ -132,6 +183,7 @@ document.addEventListener("keydown", event => { try { renderer = new GraphView(document.getElementById("elk")); + renderer.onFold = toggleFold; rendererReady = true; socket = new WebSocket("ws://" + (location.hostname || "127.0.0.1") + ":12345"); socket.onopen = () => { |
