From 1d961838cff168a101069d08a8ab6594f49f0911 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 22 Sep 2026 09:32:07 -0700 Subject: Graph viewer on ch4 and25 --- .../java/com/seaofnodes/graph/GraphAdapter.java | 11 +- .../java/com/seaofnodes/graph/GraphCapture.java | 125 +++++++++++++++++ .../main/java/com/seaofnodes/graph/GraphJson.java | 6 + .../java/com/seaofnodes/graph/GraphSocket.java | 148 +++++++++++++++++++++ .../java/com/seaofnodes/graph/GraphViewer.java | 49 +++++++ 5 files changed, 338 insertions(+), 1 deletion(-) create mode 100644 graph/src/main/java/com/seaofnodes/graph/GraphCapture.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/main/java/com/seaofnodes') 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 { 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 { */ @SafeVarargs public final GraphSnapshot snap(String comp, long step, N... roots) { + var list = new ArrayList(); + java.util.Collections.addAll(list, roots); + return snap(comp, step, list); + } + + public final GraphSnapshot snap(String comp, long step, ArrayList roots) { // 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.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 extends GraphObserver { + + private final GraphAdapter _graph; + private final String _comp = UUID.randomUUID().toString(); + private final ArrayList _peeps = new ArrayList<>(); + private long _next, _step; + private boolean _off; + + protected GraphCapture(GraphAdapter graph) { _graph = graph; } + + protected abstract String phase(); + protected abstract int pos(); + protected abstract void roots(ArrayList 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(); + 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="); + } + + 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(); } +} -- cgit v1.2.3