Define a new graph interaction API

10 files changed, 345 insertions, 10 deletions

diff --git a/chapter04/Makefile b/chapter04/Makefile
index 7f55b343..e6c8f275 100644
--- a/chapter04/Makefile
+++ b/chapter04/Makefile
@@ -36,6 +36,10 @@ CLZDIR:= build/classes
 main_javas   := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java)
 test_javas   := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java)
 main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas))
+# Compile the common adapter into this chapter without copying its sources.
+GRAPH_DIR := $(firstword $(wildcard ../graph graph))
+graph_javas := $(wildcard $(GRAPH_DIR)/src/main/java/com/seaofnodes/graph/*.java)
+main_javas += $(graph_javas)
 test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas))
 test_cp      := $(patsubst $(TST)/$(SIMPLE)/%.java,com.seaofnodes.simple.%,$(wildcard $(TST)/$(SIMPLE)/*Test.java))
 classes = $(main_classes) $(test_classes)
@@ -52,8 +56,11 @@ endif
 
 default: $(default_targets)
 
+.PHONY: build
+build: $(main_classes)
+
 # Compile just the out-of-date files
-$(main_classes): build/classes/main/%class: $(SRC)/%java
+$(main_classes): $(CLZDIR)/main/%class: $(SRC)/%java $(graph_javas)
 	@echo "compiling " $@ " because " $?
 	@[ -d $(CLZDIR)/main ] || mkdir -p $(CLZDIR)/main
 	@javac $(JAVAC_ARGS) -cp "$(CLZDIR)/main$(SEP)$(jars)" -sourcepath $(SRC) -d $(CLZDIR)/main $(main_javas)
diff --git a/chapter04/pom.xml b/chapter04/pom.xml
index 0fdebb14..5b9c7c6e 100644
--- a/chapter04/pom.xml
+++ b/chapter04/pom.xml
@@ -11,4 +11,7 @@
     <artifactId>chapter04</artifactId>
     <packaging>jar</packaging>
     <name>Chapter 4</name>
+    <properties>
+        <simple.graph.directory>${project.basedir}/../graph</simple.graph.directory>
+    </properties>
 </project>
diff --git a/chapter04/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter04/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
new file mode 100644
index 00000000..0755613b
--- /dev/null
+++ b/chapter04/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -0,0 +1,38 @@
+package com.seaofnodes.simple.print;
+
+import com.seaofnodes.graph.GraphAdapter;
+import com.seaofnodes.graph.GraphSnapshot;
+import com.seaofnodes.graph.GraphSnapshot.*;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.node.Node;
+import java.util.ArrayList;
+
+/** Chapter 4's view of the IR; no knowledge of browser, transport or layout. */
+public class SimpleGraphAdapter extends GraphAdapter<Node> {
+    @Override protected int id(Node n) { return n._nid; }
+    @Override protected int nIns(Node n) { return n.nIns(); }
+    @Override protected Node in(Node n, int idx) { return n.in(idx); }
+    @Override protected int nOuts(Node n) { return n.nOuts(); }
+    @Override protected Node out(Node n, int idx) { return n.out(idx); }
+
+    private ArrayList<Edge> edges(Node n) {
+        String[] names = n instanceof ScopeNode scope ? scope.reverseNames() : null;
+        var edges = new ArrayList<Edge>();
+        for( int i = 0; i < n.nIns(); i++ ) {
+            Role role = n instanceof ScopeNode || n instanceof ConstantNode ? Role.ASSOC
+                : n instanceof ProjNode ? (n.isCFG() ? Role.CTRL : Role.DATA)
+                : i == 0 ? Role.CTRL : Role.DATA;
+            edges.add(new Edge(i, ref(n.in(i)), role, names == null ? null : names[i]));
+        }
+        return edges;
+    }
+
+    @Override protected GraphSnapshot.Node desc(Node n) {
+        Projection proj = n instanceof ProjNode p
+            ? new Projection(n.nIns() == 0 ? 0 : ref(n.in(0)), p._idx) : null;
+        Kind kind = n instanceof ScopeNode ? Kind.SCOPE : n.isCFG() ? Kind.CTRL : Kind.DATA;
+        String label = n.label();
+        return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label,
+                                      n._type == null ? null : n._type.toString(), kind, edges(n), proj);
+    }
+}
diff --git a/chapter25/Makefile b/chapter25/Makefile
index 08b7ce56..886354d3 100644
--- a/chapter25/Makefile
+++ b/chapter25/Makefile
@@ -65,6 +65,10 @@ main_javas   := $(wildcard $(SRC)/$(SIMPLE)/*java $(SRC)/$(SIMPLE)/*/*java $(SRC
 test_javas   := $(wildcard $(TST)/$(SIMPLE)/*java $(TST)/$(SIMPLE)/*/*java)
 simple_driver := $(TST)/$(SIMPLE)/Simple.java
 main_classes := $(patsubst $(SRC)/%java,$(CLZDIR)/main/%class,$(main_javas))
+# Compile the common adapter into this chapter without copying its sources.
+GRAPH_DIR := $(firstword $(wildcard ../graph graph))
+graph_javas := $(wildcard $(GRAPH_DIR)/src/main/java/com/seaofnodes/graph/*.java)
+main_javas += $(graph_javas)
 test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas))
 # These tests do not rely on the stdlib
 test_alone := com.seaofnodes.simple.BrainFuckTest com.seaofnodes.simple.MergeSortTest com.seaofnodes.simple.TypeTest
@@ -100,6 +104,9 @@ endif
 
 default: $(default_targets)
 
+.PHONY: build
+build: $(CLZDIR)/main/.mtag
+
 #######################################################
 # Compile Java as a whole source set.  javac tracks Java dependencies
 # internally, so compiling only the directly out-of-date .java files can leave
diff --git a/chapter25/pom.xml b/chapter25/pom.xml
index 6a59188f..7a2b2b78 100644
--- a/chapter25/pom.xml
+++ b/chapter25/pom.xml
@@ -11,4 +11,7 @@
     <artifactId>chapter23</artifactId>
     <packaging>jar</packaging>
     <name>Chapter 23</name>
+    <properties>
+        <simple.graph.directory>${project.basedir}/../graph</simple.graph.directory>
+    </properties>
 </project>
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java b/chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
new file mode 100644
index 00000000..592abb5c
--- /dev/null
+++ b/chapter25/src/main/java/com/seaofnodes/simple/print/SimpleGraphAdapter.java
@@ -0,0 +1,74 @@
+package com.seaofnodes.simple.print;
+
+import com.seaofnodes.graph.GraphAdapter;
+import com.seaofnodes.graph.GraphSnapshot;
+import com.seaofnodes.graph.GraphSnapshot.*;
+import com.seaofnodes.simple.node.*;
+import com.seaofnodes.simple.node.Node;
+import com.seaofnodes.simple.type.TypeMem;
+import java.util.ArrayList;
+
+/** Chapter 25's view of the IR, including partially constructed parse-time graphs. */
+public class SimpleGraphAdapter extends GraphAdapter<Node> {
+    @Override protected int id(Node n) { return n._nid; }
+    @Override protected int nIns(Node n) { return n.nIns(); }
+    @Override protected Node in(Node n, int idx) { return n.in(idx); }
+    @Override protected int nOuts(Node n) { return n.nOuts(); }
+    @Override protected Node out(Node n, int idx) { return n.out(idx); }
+
+    private ArrayList<Edge> edges(Node n) {
+        var edges = new ArrayList<Edge>();
+        for( int i = 0; i < n.nIns(); i++ ) {
+            String name = n instanceof ScopeNode scope && i < scope._vars.size()
+                ? scope.var(i)._name : null;
+            edges.add(new Edge(i, ref(n.in(i)), role(n, i), name));
+        }
+        return edges;
+    }
+
+    @Override protected GraphSnapshot.Node desc(Node n) {
+        Projection proj = n instanceof Proj p
+            ? new Projection(n.nIns() == 0 ? 0 : ref(n.in(0)), p.idx()) : null;
+        String label = n.label();
+        return new GraphSnapshot.Node(n._nid, label == null ? n.getClass().getSimpleName() : label,
+                                      n._type == null ? null : n._type.toString(), kind(n), edges(n), proj);
+    }
+
+    private Kind kind(Node n) {
+        if( n instanceof ScopeNode ) return Kind.SCOPE;
+        if( n instanceof StartCUNode || n instanceof StopCUNode ) return Kind.UNIT;
+        if( n instanceof FunNode ) return Kind.FUN;
+        // Start inherits Loop for whole-program analysis, but is not a source loop.
+        if( n instanceof StartNode ) return Kind.CTRL;
+        if( n instanceof LoopNode ) return Kind.LOOP;
+        if( n instanceof RegionNode ) return Kind.REGION;
+        if( n instanceof PhiNode ) return Kind.PHI;
+        if( n instanceof CFGNode ) return Kind.CTRL;
+        return isMem(n) ? Kind.MEM : Kind.DATA;
+    }
+
+    private Role role(Node n, int i) {
+        if( n instanceof ScopeNode || n instanceof ConstantNode || n instanceof FunPtrNode ||
+            n instanceof CtrlNode || n instanceof XCtrlNode )
+            return Role.ASSOC;
+        if( n instanceof PhiNode )
+            return i == 0 ? Role.ASSOC : isMem(n) ? Role.MEM : Role.DATA;
+        if( n instanceof Proj )
+            return n instanceof CFGNode ? Role.CTRL : isMem(n) ? Role.MEM : Role.DATA;
+        if( n instanceof RegionNode && i == 0 ) return Role.ASSOC;
+        // Preserve known slot roles even when an input is not attached/typed yet.
+        if( i == 0 || n instanceof RegionNode || n instanceof StopNode ) return Role.CTRL;
+        if( n instanceof MemMergeNode ||
+            i == 1 && (n instanceof MemOpNode || n instanceof ReturnNode || n instanceof CallNode) ||
+            n instanceof EscapeNode && i >= 2 ) return Role.MEM;
+        Node def = n.in(i);
+        if( def instanceof CFGNode ) return Role.CTRL;
+        if( def != null && isMem(def) ) return Role.MEM;
+        return Role.DATA;
+    }
+
+    private boolean isMem(Node n) {
+        // These Phi subclasses are memory even before their first type computation.
+        return n instanceof MemPhiNode || n instanceof BulkMemPhiNode || n.isMem() || n._type instanceof TypeMem;
+    }
+}
diff --git a/graph/README.md b/graph/README.md
index d428b2c7..caf18f70 100644
--- a/graph/README.md
+++ b/graph/README.md
@@ -48,8 +48,8 @@ for Firefox testing. Test logs/screenshots are written under `build/graph-browse
 
 Each chapter currently retains its Java graph exporter, compiler hooks, and
 WebSocket transport. The browser code has no dependency on a chapter's Java
-classes. Moving the transport into a shared Java library is a separate step;
-the frontend extraction does not add dependencies to the compiler builds.
+classes. The adapters below share snapshot capture; moving the transport into
+the shared Java code is a separate step.
 
 The legacy protocol is:
 
@@ -65,15 +65,96 @@ The legacy protocol is:
 DOT frames may contain a `// POS:` comment identifying the parser position.
 The browser owns frame history and backward/forward playback.
 
-The next layout implementation belongs here. Its chapter interface should use
-versioned snapshots with stable IDs, node labels/roles, indexed inputs, edge
-roles, and optional source/grouping metadata. Keep compiler-specific traversal
-in chapter adapters, and layout, routing, animation, and interaction here.
-Full snapshots are a useful first interface; deltas can follow if needed.
+The next layout implementation belongs here. The compiler-side adapter below
+is its first building block; the running viewer still consumes DOT.
 
 The linearization workflow includes this directory as a shared root resource.
-The compiler remains self-contained in each chapter; the optional interactive
-viewer additionally needs this directory from the same checkout.
+Chapters 4 and 25 compile the shared Java sources from this directory; the
+interactive viewer also loads the web assets from this checkout.
+
+## Chapter adapters
+
+The shared Java code is in `src/main/java/com/seaofnodes/graph/`:
+
+- `GraphAdapter<N>` is an abstract base with hooks for `id`, `desc`, and indexed
+  edge access (`nIns`/`in`, `nOuts`/`out`). Its final `snap` method walks definitions and
+  uses iteratively, handles cycles, and sorts the copied records by ID.
+- `GraphSnapshot` is detached data: compilation key, step, roots, and nodes.
+  Each node has an ID, plain-text label/type, kind, edges to its defs, and optional
+  projection metadata. It contains no chapter classes or layout coordinates.
+  Node and edge lists are concrete `ArrayList`s, treated as read-only after capture.
+
+Root IDs use `int[]`. Capture uses a node table indexed by ID for visitation and
+root deduplication; no boxed integer lists, sets or map keys are needed.
+Indexed edge access reads each chapter's native storage without copying it into
+a different collection type.
+
+Both chapters implement `com.seaofnodes.simple.print.SimpleGraphAdapter`,
+extending `GraphAdapter<Node>`. No changes to `Node` or its subclasses are
+needed. The chapter owns classification and extraction; the base owns traversal
+and snapshot assembly. No new Java interface is involved.
+
+For chapter 4:
+
+```java
+var parser = new Parser("return 1+arg+2;");
+var ret = parser.parse();
+var adapter = new SimpleGraphAdapter();
+var frame = adapter.snap("compile-1", 0, ret, parser._scope);
+```
+
+For chapter 25:
+
+```java
+var code = new CodeGen("while(arg < 10) arg = arg + 1; return arg;").parse();
+var adapter = new SimpleGraphAdapter();
+var frame = adapter.snap("compile-1", 0, code._stop);
+```
+
+During a peephole, pass the current node and any unattached replacement as
+additional roots. Null roots are ignored. Capture runs on the compiler thread
+at a point where the graph is not changing; consumers can retain the returned
+records after compilation resumes. The adapter does not compute types, invoke
+peepholes, schedule nodes, or rearrange use lists.
+
+Node IDs are the chapter's `_nid`, scoped by the caller's compilation key. Use
+a new key whenever a parser/compiler resets IDs. A snapshot rejects two distinct
+nodes sharing one ID. Each edge belongs to its use node and names the referenced
+`def` ID and the input slot `idx` on that use: `use.in(idx) == def`. The adapter
+derives these edges from the compiler's `_inputs`; `_outputs` only speeds up
+traversal. Repeated definitions produce distinct edges with different slot
+indices. Each input slot has an `Edge` record, including holes with `def == 0`.
+Edges remain in input-slot order under their use node.
+Projection nodes retain their own IDs and identify their parent and tuple
+index, allowing the renderer to fold them into ports later. A missing parent
+has `par == 0`; real node IDs are never zero.
+
+Chapter 4 adds control/data roles and scope binding names. Chapter 25 adds
+memory roles and node kinds for Phis, Regions, Loops,
+Functions and compilation-unit boundaries. These are existing IR facts, not
+computed region membership or a SESE hierarchy. Scope bindings and constant
+lifetime edges are associations, so they need not constrain CFG layout.
+Types may be absent on newly constructed nodes. Source locations, grouping,
+observer events, serialization and delta encoding remain follow-up work.
+
+Make compiles these shared sources directly into each participating chapter's
+classes using `javac`. From the repository root:
+
+```sh
+make -C chapter04 build
+make -C chapter25 build
+```
+
+`build` compiles the compiler and adapter without running tests or opening a
+browser. Shared source changes trigger recompilation. No Maven executable,
+Maven-built artifacts, generated source copies or separately installed graph
+JARs are needed. Existing `make tests`, `make release` and chapter 25's
+`make view` also include the shared sources through their normal prerequisites.
+
+For the existing Maven/CI build path, `build-helper:add-source` describes the
+same source directory. The two chapter POMs select `../graph`, while the root
+POM defaults to `graph` for linearized checkouts. These entries are independent
+of the Make build.
 
 ## Peephole hook investigation
 
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..77672c45
--- /dev/null
+++ b/graph/src/main/java/com/seaofnodes/graph/GraphAdapter.java
@@ -0,0 +1,67 @@
+package com.seaofnodes.graph;
+
+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> {
+    protected abstract int id(N node);
+    protected abstract int nIns(N node);
+    protected abstract N in(N node, int idx);
+    protected abstract int nOuts(N node);
+    protected abstract N out(N node, int idx);
+    protected abstract GraphSnapshot.Node desc(N node);
+
+    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) {
+        // 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];
+        int len = 0;
+        for( N root : roots )
+            if( enq(root, seen, todo) ) rids[len++] = id(root);
+        var nodes = new ArrayList<GraphSnapshot.Node>();
+        while( !todo.isEmpty() ) {
+            N node = todo.removeFirst();
+            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), 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/GraphSnapshot.java b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java
new file mode 100644
index 00000000..18926726
--- /dev/null
+++ b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java
@@ -0,0 +1,38 @@
+package com.seaofnodes.graph;
+
+import java.util.ArrayList;
+
+/** A detached graph. Treat its lists as read-only after capture. */
+public record GraphSnapshot(int ver, String comp, long step,
+                            int[] roots, ArrayList<Node> nodes) {
+    public static final int VER = 1;
+
+    public GraphSnapshot {
+        roots = roots.clone();
+        nodes = new ArrayList<>(nodes);
+    }
+
+    @Override public int[] roots() { return roots.clone(); }
+
+    public enum Kind { DATA, CTRL, MEM, SCOPE, PHI, REGION, LOOP, FUN, UNIT }
+    public enum Role { DATA, CTRL, MEM, ASSOC }
+
+    /** IDs are stable within one compilation. Labels and types are plain text. */
+    public record Node(int id, String label, String type, Kind kind,
+                       ArrayList<Edge> edges, Projection proj) {
+        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.
+     */
+    public record Edge(int idx, int def, Role role, String label) { }
+
+    /** Projections remain real nodes; par == 0 means no parent is attached. */
+    public record Projection(int par, int idx) { }
+}
diff --git a/pom.xml b/pom.xml
index edf08496..19ef8b74 100644
--- a/pom.xml
+++ b/pom.xml
@@ -50,6 +50,8 @@
         <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
         <maven.compiler.source>21</maven.compiler.source>
         <maven.compiler.target>21</maven.compiler.target>
+        <!-- Also works at the root of a linearized chapter checkout. -->
+        <simple.graph.directory>${project.basedir}/graph</simple.graph.directory>
     </properties>
 
     <dependencies>
@@ -64,6 +66,21 @@
     <build>
         <plugins>
             <plugin>
+                <groupId>org.codehaus.mojo</groupId>
+                <artifactId>build-helper-maven-plugin</artifactId>
+                <version>3.4.0</version>
+                <executions>
+                    <execution>
+                        <id>shared-graph-sources</id>
+                        <phase>generate-sources</phase>
+                        <goals><goal>add-source</goal></goals>
+                        <configuration>
+                            <sources><source>${simple.graph.directory}/src/main/java</source></sources>
+                        </configuration>
+                    </execution>
+                </executions>
+            </plugin>
+            <plugin>
                 <groupId>org.apache.maven.plugins</groupId>
                 <artifactId>maven-surefire-plugin</artifactId>
                 <version>3.1.2</version>