Chapter 1: Introduction

Co-authored-by: Cliff Click <cliffc@acm.org>
Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>

9 files changed, 929 insertions, 0 deletions

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<N extends BaseNode<N>> {
+    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<Edge>();
+        String[] names=edgeNames(n);
+        for( int i=0; i<n.nIns(); i++ ) {
+            String name=names!=null && i<names.length ? names[i] : edgeName(n,i);
+            edges.add(new Edge(i,ref(n.in(i)),role(n,i),name,edgeJump(n,i)));
+        }
+        int idx=projectionIndex(n);
+        Projection proj=idx<0 ? null : new Projection(n.nIns()==0 ? 0 : ref(n.in(0)),idx);
+        String label=n.label();
+        return new GraphSnapshot.Node(n._nid,label==null ? n.getClass().getSimpleName() : label,
+                                      n.typeName(),kind(n),edges,proj,folding(n));
+    }
+
+    protected final int ref(N node) { return node == null ? 0 : id(node); }
+
+    /**
+     * Follow both definitions and uses from the roots, including cycles.
+     * Supply current/replacement nodes as extra roots while a peep is in flight;
+     * they need not be attached to the program yet. Null roots/uses are ignored.
+     * The caller supplies a new compilation key whenever node IDs reset.
+     */
+    @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) {
+        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<N> roots, int scope) {
+        // 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.size()];
+        int len = 0;
+        for( N root : roots )
+            if( enq(root, seen, todo) && show(root) ) rids[len++] = id(root);
+        var nodes = new ArrayList<GraphSnapshot.Node>();
+        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<N> seen, ArrayDeque<N> 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<N extends BaseNode<N>> extends GraphObserver<N> {
+
+    private final GraphAdapter<N> _graph;
+    private String _comp;
+    private GraphSocket _server;
+    private final ArrayList<Peep> _peeps = new ArrayList<>();
+    private final BitSet _pre = new BitSet();
+    private long _next, _step;
+    private boolean _off = true;
+    private boolean _err;
+
+    protected GraphCapture(GraphAdapter<N> 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<N> 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<N>();
+        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<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 || 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<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 parts = 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);
+            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<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); }
+        }
+        // Look for a closed If/Region diamond. Reachable joins are considered
+        // nearest first; a candidate must have no other CFG entry or exit.
+        for( Node n : nodes ) if( n.kind()==Kind.CTRL && n.label().equals("If") && uses[n.id()].length==2 ) {
+            BitSet seen = new BitSet();
+            head=tail=0;
+            work[tail++]=n.id(); seen.set(n.id());
+            while( head<tail ) {
+                int id=work[head++];
+                if( ns[id].kind()==Kind.REGION ) {
+                    BitSet set=diamond(n.id(),id,ns,preds,uses);
+                    if( set!=null ) { body[n.id()]=set; parts.add(n); break; }
+                }
+                for( int use : uses[id] ) if( !seen.get(use) ) {
+                    seen.set(use); work[tail++]=use;
+                }
+            }
+        }
+        // Outer regions first. Only nested or disjoint sets can form boxes;
+        // overlapping loop/diamond candidates keep the already accepted group.
+        parts.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()];
+        var accepted = new ArrayList<Node>();
+        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<tail ) {
+            int id=todo[head++];
+            if( id==exit ) continue;
+            if( uses[id].length==0 || ns[id].kind()==Kind.FUN ||
+                ns[id].kind()==Kind.START || ns[id].kind()==Kind.UNIT ) return null;
+            for( int use : uses[id] ) if( !set.get(use) ) { set.set(use); todo[tail++]=use; }
+        }
+        if( !set.get(exit) ) return null;
+        for( int id=set.nextSetBit(0); id>=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<tail ) for( int p : preds[todo[head++]] )
+            if( set.get(p) && !reaches.get(p) ) { reaches.set(p); todo[tail++]=p; }
+        return reaches.equals(set) ? set : null;
+    }
+
+    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 owner(int a, int b, int[] par) {
+        a=Math.max(0,a); b=Math.max(0,b);
+        if( a==0 ) return b;
+        if( b==0 || a==b ) return a;
+        // Sibling nominations leave the node between the regions. Nested
+        // nominations agree on the enclosing region (e.g. a function and loop).
+        return lca(a,b,par);
+    }
+
+    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
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; 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("]}");
+    }
+
+    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<N> {
+    public abstract void before(N node);
+
+    /**
+     * repl is null for no progress. applied means substitution and cleanup are
+     * complete; otherwise repl is being returned for the caller to attach.
+     * Calls nest when a rewrite invokes another peephole.
+     */
+    public abstract void after(N node, N repl, boolean applied);
+
+    /** A completed compiler phase. */
+    public abstract void phase(String phase);
+
+    /** A 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<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, 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<Edge> edges, Projection proj, boolean folding) {
+        public Node(int id, String label, String type, Kind kind, ArrayList<Edge> 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=<viewer 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("#");
+                }
+            }
+        }
+    }
+}