Define a new graph interaction API

2 files changed, 105 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..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) { }
+}