Graph viewer on ch4 and25

5 files changed, 338 insertions, 1 deletions

diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java b/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java
index 77672c45..3e840b54 100644
--- a/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java
+++ b/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java
@@ -17,6 +17,9 @@ public abstract class GraphAdapter<N> {
     protected abstract int nOuts(N node);
     protected abstract N out(N node, int idx);
     protected abstract GraphSnapshot.Node desc(N node);
+    protected abstract boolean dead(N node);
+    protected int nDeps(N node) { return 0; }
+    protected N dep(N node, int idx) { throw new IndexOutOfBoundsException(idx); }
 
     protected final int ref(N node) { return node == null ? 0 : id(node); }
 
@@ -28,10 +31,16 @@ public abstract class GraphAdapter<N> {
      */
     @SafeVarargs
     public final GraphSnapshot snap(String comp, long step, N... roots) {
+        var list = new ArrayList<N>();
+        java.util.Collections.addAll(list, roots);
+        return snap(comp, step, list);
+    }
+
+    public final GraphSnapshot snap(String comp, long step, ArrayList<N> roots) {
         // Node IDs are dense; index directly without boxed keys or map entries.
         var seen = new ArrayList<N>();
         var todo = new ArrayDeque<N>();
-        var rids = new int[roots.length];
+        var rids = new int[roots.size()];
         int len = 0;
         for( N root : roots )
             if( enq(root, seen, todo) ) rids[len++] = id(root);
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..0e2f538d
--- /dev/null
+++ b/graph/src/main/java/com/seaofnodes/graph/GraphCapture.java
@@ -0,0 +1,125 @@
+package com.seaofnodes.graph;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.UUID;
+
+/** Shared capture, event nesting and neighborhoods. Chapter hooks only read the IR. */
+public abstract class GraphCapture<N> extends GraphObserver<N> {
+
+    private final GraphAdapter<N> _graph;
+    private final String _comp = UUID.randomUUID().toString();
+    private final ArrayList<Peep> _peeps = new ArrayList<>();
+    private long _next, _step;
+    private boolean _off;
+
+    protected GraphCapture(GraphAdapter<N> graph) { _graph = graph; }
+
+    protected abstract String phase();
+    protected abstract int pos();
+    protected abstract void roots(ArrayList<N> roots);
+    protected abstract void detach();
+
+    protected abstract void frame(GraphSnapshot snap, int pos, GraphEvent evt) throws IOException;
+
+    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);
+    }
+
+    @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), 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), 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, _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) {
+        var roots = new ArrayList<N>();
+        roots(roots);
+        for( Peep p : _peeps ) if( !_graph.dead(p.node) ) roots.add(p.node);
+        roots.add(extra);
+        return _graph.snap(_comp, 0, roots);
+    }
+
+    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;
+            detach();
+            System.err.println("Graph viewer disconnected: " + e.getMessage());
+        }
+    }
+}
diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphJson.java b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java
index c27076d3..8726d81b 100644
--- a/graph/src/main/java/com/seaofnodes/graph/GraphJson.java
+++ b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java
@@ -2,6 +2,12 @@ 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);
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..dcb2e337
--- /dev/null
+++ b/graph/src/main/java/com/seaofnodes/graph/GraphViewer.java
@@ -0,0 +1,49 @@
+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. Subclasses supply their compiler. */
+public abstract class GraphViewer implements AutoCloseable {
+    private final GraphSocket _server;
+
+    protected GraphViewer() throws IOException { _server = new GraphSocket(viewerURI(), 12345); }
+    protected abstract void compile(String src);
+
+    protected final void frame(GraphSnapshot snap, int pos, GraphEvent evt) throws IOException {
+        _server.put(GraphJson.frame(snap, pos, evt));
+    }
+
+    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=<viewer URL>");
+    }
+
+    public final void run() throws IOException {
+        _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 {
+                compile(src);
+            } catch( RuntimeException e ) {
+                System.err.println(e);
+                _server.put(GraphJson.error(e.toString()));
+            } finally {
+                _server.put("#");
+            }
+        }
+    }
+
+    @Override public final void close() throws IOException { _server.close(); }
+}