From 787a37d6b1753bb7c6abd36cba293737ad6b9a0a Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Sat, 19 Aug 2023 08:52:57 -0700 Subject: Chapter 1: Introduction MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Cliff Click Co-authored-by: Thalia Archibald Co-authored-by: hadha Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> --- .../java/com/seaofnodes/graph/GraphAdapter.java | 107 +++++++++ .../java/com/seaofnodes/graph/GraphCapture.java | 177 +++++++++++++++ .../main/java/com/seaofnodes/graph/GraphEvent.java | 20 ++ .../java/com/seaofnodes/graph/GraphGroups.java | 238 +++++++++++++++++++++ .../main/java/com/seaofnodes/graph/GraphJson.java | 126 +++++++++++ .../java/com/seaofnodes/graph/GraphObserver.java | 22 ++ .../java/com/seaofnodes/graph/GraphSnapshot.java | 49 +++++ .../java/com/seaofnodes/graph/GraphSocket.java | 148 +++++++++++++ .../java/com/seaofnodes/graph/GraphViewer.java | 42 ++++ 9 files changed, 929 insertions(+) create mode 100644 graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java create mode 100644 graph/src/main/java/com/seaofnodes/graph/GraphCapture.java create mode 100644 graph/src/main/java/com/seaofnodes/graph/GraphEvent.java create mode 100644 graph/src/main/java/com/seaofnodes/graph/GraphGroups.java create mode 100644 graph/src/main/java/com/seaofnodes/graph/GraphJson.java create mode 100644 graph/src/main/java/com/seaofnodes/graph/GraphObserver.java create mode 100644 graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java create mode 100644 graph/src/main/java/com/seaofnodes/graph/GraphSocket.java create mode 100644 graph/src/main/java/com/seaofnodes/graph/GraphViewer.java (limited to 'graph/src') diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java b/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java new file mode 100644 index 00000000..9014ce04 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java @@ -0,0 +1,107 @@ +package com.seaofnodes.graph; + +import com.seaofnodes.print.BaseNode; +import static com.seaofnodes.graph.GraphSnapshot.*; +import java.util.ArrayDeque; +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Comparator; + +/** + * Subclass once per chapter. Only the subclass knows that chapter's IR. + * Capture on the compiler thread, while the graph is not being modified. + * Hooks must only read the IR: no computing types, peepholes or scheduling. + */ +public abstract class GraphAdapter> { + protected final int id(N n) { return n._nid; } + protected final int nIns(N n) { return n.nIns(); } + protected final N in(N n, int i) { return n.in(i); } + protected final int nOuts(N n) { return n.nOuts(); } + protected final N out(N n, int i) { return n.out(i); } + protected final boolean dead(N n) { return n.isDead(); } + protected final int nDeps(N n) { return n.nDeps(); } + protected final N dep(N n, int i) { return n.dep(i); } + + // Chapters supply only semantic distinctions that their IR has introduced. + protected Kind kind(N n) { return n.isCFG() ? Kind.CTRL : Kind.DATA; } + protected Role role(N n, int i) { return i==0 ? Role.CTRL : Role.DATA; } + protected String[] edgeNames(N n) { return null; } + protected String edgeName(N n, int i) { return null; } + protected int edgeJump(N n, int i) { return 0; } + protected int projectionIndex(N n) { return -1; } + protected boolean folding(N n) { return false; } + // Omit cached helpers with no graph uses; still walk through them. + protected boolean show(N n) { return true; } + + protected final GraphSnapshot.Node desc(N n) { + var edges=new ArrayList(); + String[] names=edgeNames(n); + for( int i=0; i(); + java.util.Collections.addAll(list, roots); + return snap(comp, step, list); + } + + public final GraphSnapshot snap(String comp, long step, ArrayList roots) { + return snap(comp, step, roots, 0); + } + + /** scope names the active parser scope, which the caller includes in roots. */ + public final GraphSnapshot snap(String comp, long step, ArrayList roots, int scope) { + // Node IDs are dense; index directly without boxed keys or map entries. + var seen = new ArrayList(); + var todo = new ArrayDeque(); + var rids = new int[roots.size()]; + int len = 0; + for( N root : roots ) + if( enq(root, seen, todo) && show(root) ) rids[len++] = id(root); + var nodes = new ArrayList(); + while( !todo.isEmpty() ) { + N node = todo.removeFirst(); + 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); + } + // 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, GraphGroups.build(nodes)); + } + + private boolean enq(N node, ArrayList seen, ArrayDeque todo) { + if( node == null ) return false; + int nid = id(node); + while( seen.size() <= nid ) seen.add(null); + N old = seen.get(nid); + if( old == null ) { + seen.set(nid, node); + todo.addLast(node); + return true; + } + if( old != node ) + throw new IllegalArgumentException("Different nodes share ID " + nid + + "; mixed compilations?"); + return false; + } +} diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphCapture.java b/graph/src/main/java/com/seaofnodes/graph/GraphCapture.java new file mode 100644 index 00000000..10071755 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphCapture.java @@ -0,0 +1,177 @@ +package com.seaofnodes.graph; + +import com.seaofnodes.print.BaseNode; +import java.io.IOException; +import java.util.ArrayList; +import java.util.BitSet; +import java.util.UUID; + +/** Shared compilation lifecycle, capture, event nesting and neighborhoods. */ +public abstract class GraphCapture> extends GraphObserver { + + private final GraphAdapter _graph; + private String _comp; + private GraphSocket _server; + private final ArrayList _peeps = new ArrayList<>(); + private final BitSet _pre = new BitSet(); + private long _next, _step; + private boolean _off = true; + private boolean _err; + + protected GraphCapture(GraphAdapter graph) { _graph = graph; } + + // Create the chapter's compiler, attach this observer, and run its phases. + protected abstract void compile(String src); + // The remaining hooks only inspect context, except detach which clears it. + protected abstract String phase(); + protected abstract int pos(); + protected abstract void roots(ArrayList roots); + // Called only during parsing; the shared capture adds this root too. + protected N scope() { return null; } + protected abstract void detach(); + + final void run(String src, GraphSocket server) { + _comp = UUID.randomUUID().toString(); + _next = _step = 0; + _server = server; + _off = false; + _err = false; + try { + compile(src); + } catch( RuntimeException e ) { + // Type checking already emitted its diagnostic with the final graph. + if( !_err ) throw e; + System.err.println(e); + } finally { + _off = true; + try { + detach(); + } finally { + _peeps.clear(); + _server = null; + } + } + } + + private class Peep { + final N node; + final long id, up; + final String phase; + final int pos; + final BitSet near = new BitSet(); + GraphSnapshot pre; + boolean sent; + + Peep(N 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(N n) { + if( _off ) return; + var p = new Peep(n, ++_next, _peeps.isEmpty() ? 0 : _peeps.getLast().id, + phase(), 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, true); + if( p.up == 0 ) { + _pre.clear(); + for( var node : p.pre.nodes() ) _pre.set(node.id()); + } + } + + @Override public void after(N n, N 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; + } + N rez = repl == null ? n : repl; + emit(snap(_graph.dead(rez) ? null : rez, true), pos(), + evt(p, applied ? GraphEvent.Kind.APPLY : GraphEvent.Kind.RETURN, + _graph.dead(rez) ? 0 : _graph.id(rez))); + } + _peeps.removeLast(); + } + + @Override public void dep(N n, N 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, false), pos(), new GraphEvent(GraphEvent.Kind.PHASE, 0, 0, phase, 0, 0, new int[0])); + } + + @Override public void error(N node, String msg) { + if( _off ) return; + _err = true; + emit(snap(node, false), pos(), new GraphEvent(GraphEvent.Kind.ERROR, 0, 0, + phase(), _graph.ref(node), 0, new int[0], new int[0], msg)); + } + + private GraphEvent evt(Peep p, GraphEvent.Kind kind, int repl) { + return new GraphEvent(kind, p.id, p.up, p.phase, _graph.id(p.node), repl, p.near.stream().toArray()); + } + + private void add(Peep p, N n) { if( n != null ) p.near.set(_graph.id(n)); } + + private void near(Peep p, N n) { + if( n == null ) return; + add(p, n); + for( int i = 0; i < _graph.nIns(n); i++ ) add(p, _graph.in(n, i)); + for( int i = 0; i < _graph.nOuts(n); i++ ) add(p, _graph.out(n, i)); + // 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 < _graph.nDeps(n); i++ ) add(p, _graph.dep(n, i)); + } + + + private GraphSnapshot snap(N extra, boolean parsing) { + var roots = new ArrayList(); + roots(roots); + // Early parsers retain their emptied scope after returning. A completed + // phase no longer owns that scope, even while phase() still says Parse. + N scope = parsing && "Parse".equals(phase()) ? scope() : null; + roots.add(scope); + for( Peep p : _peeps ) if( !_graph.dead(p.node) ) roots.add(p.node); + roots.add(extra); + return _graph.snap(_comp, 0, roots, _graph.ref(scope)); + } + + private void emit(GraphSnapshot snap, int pos, GraphEvent evt) { + if( _off ) return; + if( evt.up() != 0 ) { + // Nested peepholes can create userless results before their caller + // returns. These belong to the peep, not the parser's expression. + int[] temps = snap.nodes().stream().mapToInt(GraphSnapshot.Node::id) + .filter(id -> !_pre.get(id)).toArray(); + evt = new GraphEvent(evt.kind(), evt.peep(), evt.up(), evt.phase(), + evt.node(), evt.repl(), evt.near(), temps); + } + // 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.groups()); + try { + _server.put(GraphJson.frame(snap, pos, evt)); + } catch( IOException e ) { + // A disconnected display must not interrupt optimization. + _off = true; + System.err.println("Graph viewer disconnected: " + e.getMessage()); + } + } +} 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..d52213c2 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphEvent.java @@ -0,0 +1,20 @@ +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, int[] temps, String msg) { + public enum Kind { BEFORE, RETURN, APPLY, PHASE, ERROR } + + public GraphEvent(Kind kind, long peep, long up, String phase, int node, int repl, int[] near, int[] temps) { + this(kind, peep, up, phase, node, repl, near, temps, null); + } + + public GraphEvent(Kind kind, long peep, long up, String phase, int node, int repl, int[] near) { + this(kind, peep, up, phase, node, repl, near, new int[0]); + } + + public GraphEvent { near = near.clone(); temps = temps.clone(); } + @Override public int[] near() { return near.clone(); } + // Created inside an enclosing peep; not yet returned to the parser. + @Override public int[] temps() { return temps.clone(); } +} 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..7e46f809 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java @@ -0,0 +1,238 @@ +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 build(ArrayList nodes) { + var result = new ArrayList(); + boolean any=false; + for( Node n : nodes ) if( n.kind()==Kind.FUN || n.kind()==Kind.LOOP || n.label().equals("If") ) { 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(); + 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); + parts.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 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()]; + var accepted = new ArrayList(); + BitSet gids = new BitSet(); + for( Node n : parts ) { + int id=n.id(); + boolean fits=true; + for( Node p : accepted ) if( body[id].intersects(body[p.id()]) ) { + BitSet rest=(BitSet)body[id].clone(); + rest.andNot(body[p.id()]); + if( !rest.isEmpty() || body[id].get(p.id()) ) { fits=false; break; } + } + if( !fits ) continue; + accepted.add(n); + gids.set(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]; + } + // Compute input and output ownership independently, so a floating chain + // between two regions cannot pull itself into either end. Null slots and + // parser/lifetime associations do not nominate a region. Phi uses refer + // to the Phi itself, not to its incoming CFG path. + BitSet fixed = new BitSet(); + for( Node n : nodes ) if( home[n.id()]>=0 ) fixed.set(n.id()); + int[] ins=home.clone(), outs=home.clone(); + boolean changed; + do { + changed=false; + for( Node n : nodes ) for( Edge e : n.edges() ) { + int id=e.def(); + if( id==0 || ns[id]==null || e.role()==Role.ASSOC ) continue; + if( !fixed.get(n.id()) && ins[id]>=0 ) { + int next=lca(ins[n.id()],ins[id],par); + if( next!=ins[n.id()] ) { ins[n.id()]=next; changed=true; } + } + if( !fixed.get(id) && outs[n.id()]>=0 ) { + int next=lca(outs[id],outs[n.id()],par); + if( next!=outs[id] ) { outs[id]=next; changed=true; } + } + } + } while( changed ); + for( Node n : nodes ) if( !fixed.get(n.id()) ) { + home[n.id()]=owner(ins[n.id()],outs[n.id()],par); + } + // Unattached floating users may have no directional anchor. Check the + // actual neighbors too, widening unsupported claims until they settle. + // Only moving outward avoids self-supporting cycles of floating nodes. + do { + changed=false; + Arrays.fill(ins,-1); Arrays.fill(outs,-1); + for( Node n : nodes ) for( Edge e : n.edges() ) if( e.def()!=0 && e.role()!=Role.ASSOC ) { + ins[n.id()]=lca(ins[n.id()],home[e.def()],par); + outs[e.def()]=lca(outs[e.def()],home[n.id()],par); + } + for( Node n : nodes ) if( !fixed.get(n.id()) ) { + int id=n.id(), next=lca(home[id],owner(ins[id],outs[id],par),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 || gids.get(n.id()) ) { + 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 BitSet diamond(int entry, int exit, Node[] ns, int[][] preds, int[][] uses) { + BitSet set=new BitSet(); + int[] todo=new int[ns.length]; + int head=0, tail=0; + todo[tail++]=entry; set.set(entry); + while( head=0; id=set.nextSetBit(id+1) ) if( id!=entry ) + for( int p : preds[id] ) if( !set.get(p) ) return null; + // Reject trapped cycles as well as paths to another exit. + BitSet reaches=new BitSet(); + head=tail=0; + todo[tail++]=exit; reaches.set(exit); + while( head 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 new file mode 100644 index 00000000..bcdd46cc --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java @@ -0,0 +1,126 @@ +package com.seaofnodes.graph; + +/** JSON for the shared graph model; no chapter or layout dependencies. */ +public class GraphJson { + public static String error(String msg) { + var sb = new StringBuilder("{\"error\":"); + str(sb, msg); + return sb.append('}').toString(); + } + + public static String write(GraphSnapshot snap) { + var sb = new StringBuilder(); + snap(sb, snap); + return sb.toString(); + } + + public static String frame(GraphSnapshot snap, int pos, GraphEvent evt) { + var sb = new StringBuilder("{\"snap\":"); + snap(sb, snap); + 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("],\"temps\":["); + int[] temps = evt.temps(); + for( int i = 0; i < temps.length; i++ ) { + if( i > 0 ) sb.append(','); + sb.append(temps[i]); + } + sb.append(']'); + if( evt.msg() != null ) { + sb.append(",\"msg\":"); + str(sb, evt.msg()); + } + sb.append('}'); + return sb.append('}').toString(); + } + + private static void snap(StringBuilder sb, GraphSnapshot snap) { + sb.append("{\"ver\":").append(snap.ver()).append(",\"comp\":"); + str(sb, snap.comp()); + sb.append(",\"step\":").append(snap.step()).append(",\"roots\":["); + int[] roots = snap.roots(); + for( int i = 0; i < roots.length; i++ ) { + if( i > 0 ) sb.append(','); + sb.append(roots[i]); + } + sb.append("],\"scope\":").append(snap.scope()).append(",\"nodes\":["); + var nodes = snap.nodes(); + for( int i = 0; i < nodes.size(); i++ ) { + if( i > 0 ) sb.append(','); + var node = nodes.get(i); + sb.append("{\"id\":").append(node.id()).append(",\"label\":"); + str(sb, node.label()); + sb.append(",\"type\":"); + str(sb, node.type()); + sb.append(",\"kind\":"); + str(sb, node.kind().name()); + if( node.folding() ) sb.append(",\"folding\":true"); + sb.append(",\"edges\":["); + var edges = node.edges(); + for( int j = 0; j < edges.size(); j++ ) { + if( j > 0 ) sb.append(','); + var edge = edges.get(j); + sb.append("{\"idx\":").append(edge.idx()) + .append(",\"def\":").append(edge.def()).append(",\"role\":"); + str(sb, edge.role().name()); + sb.append(",\"label\":"); + str(sb, edge.label()); + if( edge.jump()!=0 ) sb.append(",\"jump\":").append(edge.jump()); + sb.append('}'); + } + sb.append("],\"proj\":"); + var proj = node.proj(); + if( proj == null ) sb.append("null"); + else sb.append("{\"par\":").append(proj.par()) + .append(",\"idx\":").append(proj.idx()).append('}'); + sb.append('}'); + } + sb.append("],\"groups\":["); + for( int i=0; i0 ) 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; j0 ) sb.append(','); + sb.append(g.nodes()[j]); + } + sb.append("]}"); + } + sb.append("]}"); + } + + private static void str(StringBuilder sb, String s) { + if( s == null ) { sb.append("null"); return; } + sb.append('"'); + for( int i = 0; i < s.length(); i++ ) { + char c = s.charAt(i); + switch( c ) { + case '"' -> sb.append("\\\""); + case '\\' -> sb.append("\\\\"); + case '\n' -> sb.append("\\n"); + case '\r' -> sb.append("\\r"); + case '\t' -> sb.append("\\t"); + default -> { + // Escape controls and UTF-16 code units that cannot travel alone + // in UTF-8. Surrogate pairs round-trip through JSON as well. + if( c < 32 || Character.isSurrogate(c) ) { + sb.append("\\u"); + for( int shift = 12; shift >= 0; shift -= 4 ) + sb.append("0123456789abcdef".charAt((c >> shift) & 15)); + } else sb.append(c); + } + } + } + sb.append('"'); + } +} 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..4a57c816 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphObserver.java @@ -0,0 +1,22 @@ +package com.seaofnodes.graph; + +/** Optional, compilation-owned observer. Callbacks read the IR without changing it. */ +public abstract class GraphObserver { + 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 compiler diagnostic and its node, or null for an error without a node. */ + public void error(N node, String msg) {} + + /** A rule consulted a dependency, even if already registered or adjacent. */ + public void dep(N node, N def) {} +} diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java new file mode 100644 index 00000000..df1e8837 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java @@ -0,0 +1,49 @@ +package com.seaofnodes.graph; + +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 nodes, ArrayList 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, 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; labels/types are plain text. folding means pending inline cleanup. */ + public record Node(int id, String label, String type, Kind kind, + ArrayList edges, Projection proj, boolean folding) { + public Node(int id, String label, String type, Kind kind, ArrayList edges, Projection proj) { + this(id,label,type,kind,edges,proj,false); + } + public Node { + edges = new ArrayList<>(edges); + } + } + + /** + * The containing Node is the use; def is the referenced node ID. + * idx is the input slot on that use: use.in(idx) == def. + * Each slot has a record, including holes (def == 0). + * label is an optional binding name, not markup. + * jump is a known function entry for a CallEnd link, or zero; def stays the + * actual Return. The browser can replace the drawn link with a shortcut. + */ + public record Edge(int idx, int def, Role role, String label, int jump) { + public Edge(int idx, int def, Role role, String label) { this(idx,def,role,label,0); } + } + + /** Projections remain real nodes; par == 0 means no parent is attached. */ + public record Projection(int par, int idx) { } +} diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphSocket.java b/graph/src/main/java/com/seaofnodes/graph/GraphSocket.java new file mode 100644 index 00000000..b9859b28 --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphSocket.java @@ -0,0 +1,148 @@ +package com.seaofnodes.graph; + +import java.io.*; +import java.net.*; +import java.nio.charset.StandardCharsets; +import java.nio.file.Path; +import java.security.MessageDigest; +import java.security.NoSuchAlgorithmException; +import java.util.Base64; +import com.sun.net.httpserver.HttpServer; +import com.sun.net.httpserver.SimpleFileServer; + +/** One local viewer session. HTTP assets and compiler messages share its lifetime. */ +class GraphSocket extends ServerSocket { + private DataInputStream _in; + private OutputStream _out; + private HttpServer _http; + private Socket _client; + + GraphSocket(URI uri, int port) throws IOException { + super(port, 1, InetAddress.getByName("127.0.0.1")); + try { + if( "file".equals(uri.getScheme()) ) { + Path page = Path.of(uri); + _http = SimpleFileServer.createFileServer( + new InetSocketAddress("127.0.0.1", 0), page.getParent(), + SimpleFileServer.OutputLevel.NONE); + _http.start(); + uri = URI.create("http://127.0.0.1:" + _http.getAddress().getPort() + "/" + page.getFileName()); + } + System.out.println("Graph viewer: " + uri); + if( Boolean.parseBoolean(System.getProperty("simple.graph.open", "true")) ) + java.awt.Desktop.getDesktop().browse(uri); + _client = accept(); + // Keep one buffer across the upgrade and all subsequent frames. + _in = new DataInputStream(new BufferedInputStream(_client.getInputStream())); + _out = new BufferedOutputStream(_client.getOutputStream()); + upgrade(); + } catch( IOException | RuntimeException | Error e ) { + try { close(); } catch( IOException ignored ) {} + throw e; + } + } + + private String line() throws IOException { + var sb = new StringBuilder(); + for( int b; (b = _in.read()) != '\n'; ) { + if( b == -1 ) throw new EOFException("Incomplete WebSocket upgrade"); + if( b != '\r' ) sb.append((char)b); + } + return sb.toString(); + } + + private void upgrade() throws IOException { + String key = null; + for( String line; !(line = line()).isEmpty(); ) { + int colon = line.indexOf(':'); + if( colon > 0 && line.substring(0, colon).equalsIgnoreCase("Sec-WebSocket-Key") ) + key = line.substring(colon + 1).trim(); + } + if( key == null ) throw new IOException("Missing WebSocket key"); + String accept; + try { + byte[] hash = MessageDigest.getInstance("SHA-1").digest( + (key + "258EAFA5-E914-47DA-95CA-C5AB0DC85B11").getBytes(StandardCharsets.US_ASCII)); + accept = Base64.getEncoder().encodeToString(hash); + } catch( NoSuchAlgorithmException e ) { + throw new IllegalStateException(e); // SHA-1 is required by the JDK. + } + _out.write(("HTTP/1.1 101 Switching Protocols\r\nConnection: Upgrade\r\nUpgrade: websocket\r\n" + + "Sec-WebSocket-Accept: " + accept + "\r\n\r\n").getBytes(StandardCharsets.US_ASCII)); + _out.flush(); + } + + public String get() throws IOException { + ByteArrayOutputStream msg = null; + while( true ) { + int head = _in.read(); + if( head == -1 ) { + if( msg != null ) throw new EOFException("Incomplete WebSocket message"); + return null; + } + boolean fin = (head & 128) != 0; + int op = head & 15; + int size = _in.readUnsignedByte(); + if( (head & 112) != 0 || (size & 128) == 0 ) + throw new IOException("Expected a masked WebSocket frame without extensions"); + long len = size & 127; + if( len == 126 ) len = _in.readUnsignedShort(); + else if( len == 127 ) len = _in.readLong(); + if( len < 0 || len > Integer.MAX_VALUE ) throw new IOException("WebSocket frame too large"); + if( op >= 8 && (!fin || len > 125) ) throw new IOException("Invalid WebSocket control frame"); + byte[] mask = new byte[4]; + _in.readFully(mask); + byte[] data = new byte[(int)len]; + _in.readFully(data); // TCP may deliver any header or payload in pieces. + for( int i = 0; i < data.length; i++ ) data[i] ^= mask[i & 3]; + switch( op ) { + case 8: return null; + case 9: put(10, data); continue; // PONG echoes PING, even between fragments. + case 10: continue; + case 1: + if( msg != null ) throw new IOException("Text frame inside an unfinished message"); + if( fin ) return new String(data, StandardCharsets.UTF_8); + msg = new ByteArrayOutputStream(); + break; + case 0: + if( msg == null ) throw new IOException("Continuation without a text frame"); + break; + default: throw new IOException("Unsupported WebSocket opcode: " + op); + } + msg.write(data); + if( fin ) return msg.toString(StandardCharsets.UTF_8); + } + } + + public void put(String msg) throws IOException { put(1, msg.getBytes(StandardCharsets.UTF_8)); } + + private void put(int op, byte[] data) throws IOException { + int len = data.length; + _out.write(128 | op); + if( len <= 125 ) _out.write(len); + else if( len <= 65535 ) { + _out.write(126); + _out.write(len >>> 8); + _out.write(len & 255); + } else { + _out.write(127); + for( int shift = 56; shift >= 0; shift -= 8 ) + _out.write((int)((long)len >>> shift) & 255); + } + _out.write(data); + _out.flush(); + } + + @Override public void close() throws IOException { + try { + if( _out != null && !isClosed() ) put(8, new byte[0]); + } finally { + if( _http != null ) _http.stop(0); + try { + if( _client != null ) _client.close(); + } finally { + super.close(); + } + } + } +} diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphViewer.java b/graph/src/main/java/com/seaofnodes/graph/GraphViewer.java new file mode 100644 index 00000000..e70a12cf --- /dev/null +++ b/graph/src/main/java/com/seaofnodes/graph/GraphViewer.java @@ -0,0 +1,42 @@ +package com.seaofnodes.graph; + +import java.io.IOException; +import java.net.URI; +import java.nio.file.Files; +import java.nio.file.Path; + +/** Shared launcher and source/compile loop. Chapter observers supply their compiler. */ +public final class GraphViewer { + private GraphViewer() {} + + private static URI viewerURI() throws IOException { + String url = System.getProperty("simple.graph.url"); + if( url != null ) return URI.create(url); + for( Path dir = Path.of("").toAbsolutePath(); dir != null; dir = dir.getParent() ) { + Path page = dir.resolve("graph/web/index.html"); + if( Files.isRegularFile(page) ) return page.toUri(); + } + throw new IOException("Cannot find graph/web/index.html; run inside the Simple checkout " + + "or set -Dsimple.graph.url="); + } + + public static void run(GraphCapture obs) throws IOException { + try( var server = new GraphSocket(viewerURI(), 12345) ) { + server.put("!"); + while( true ) { + String src = server.get(); + if( src == null || src.equals("null") ) return; + if( src.equals("+") ) continue; // Frames are currently sent eagerly. + System.out.println(src); + try { + obs.run(src, server); + } catch( RuntimeException e ) { + System.err.println(e); + server.put(GraphJson.error(e.toString())); + } finally { + server.put("#"); + } + } + } + } +} -- cgit v1.2.3