From 7279862d57c97063eb46997804b5efb6c0b07189 Mon Sep 17 00:00:00 2001
From: Cliff Click <cliffc@acm.org>
Date: Thu, 24 Sep 2026 10:47:39 -0700
Subject: Bunch better layout options

---
 .../java/com/seaofnodes/graph/GraphGroups.java     | 118 +++++++++++++++++----
 .../main/java/com/seaofnodes/graph/GraphJson.java  |   1 +
 .../java/com/seaofnodes/graph/GraphSnapshot.java   |   6 +-
 3 files changed, 105 insertions(+), 20 deletions(-)

(limited to 'graph/src/main/java')

diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java b/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java
index 75bb90e0..7e46f809 100644
--- a/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java
+++ b/graph/src/main/java/com/seaofnodes/graph/GraphGroups.java
@@ -10,7 +10,7 @@ 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 ) { any=true; break; }
+        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];
@@ -49,13 +49,13 @@ final class GraphGroups {
 
         // Natural loops: walk backwards from the backedge, stopping at the
         // header. An unfinished loop has only its header until it closes.
-        var loops = new ArrayList<Node>();
+        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);
-            loops.add(n);
+            parts.add(n);
             if( back==0 || ns[back]==null ) continue;
             head=tail=0;
             if( back!=id ) { set.set(back); work[tail++]=back; }
@@ -71,14 +71,42 @@ final class GraphGroups {
             }
             if( outside || !closed ) { set.clear(); set.set(id); }
         }
-        // Outer loops first. Simple's structured CFG makes these sets nested
-        // or disjoint.
-        loops.sort((a,b) -> Integer.compare(body[b.id()].cardinality(),body[a.id()].cardinality()));
+        // 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()];
-        for( Node n : loops ) {
+        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;
         }
@@ -92,32 +120,51 @@ final class GraphGroups {
                 anchor!=0 && ns[anchor]!=null && cfg(ns[anchor]) )
                 home[id]=home[anchor];
         }
-        // Floating values belong to the common enclosing group of their uses.
-        // A Phi's input is used on the corresponding predecessor, not at the
-        // header (especially the entry input of a loop Phi).
+        // 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 || fixed.get(id) || e.role()==Role.ASSOC ) continue;
-                int site=n.id();
-                if( n.kind()==Kind.PHI && e.idx()>0 ) {
-                    Node reg=ns[def(n,0)];
-                    site=reg==null ? 0 : def(reg,e.idx());
+                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; }
                 }
-                int grp=site==0 ? 0 : home[site];
-                if( grp<0 ) continue;
-                int next=lca(home[id],grp,par);
+            }
+        } 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 || n.kind()==Kind.LOOP ) {
+        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];
@@ -128,6 +175,30 @@ final class GraphGroups {
         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] )
@@ -135,6 +206,15 @@ final class GraphGroups {
         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;
diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphJson.java b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java
index fd37d5a9..004f6827 100644
--- a/graph/src/main/java/com/seaofnodes/graph/GraphJson.java
+++ b/graph/src/main/java/com/seaofnodes/graph/GraphJson.java
@@ -63,6 +63,7 @@ public class GraphJson {
                 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\":");
diff --git a/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java
index 4d14ed10..b53f3211 100644
--- a/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java
+++ b/graph/src/main/java/com/seaofnodes/graph/GraphSnapshot.java
@@ -34,8 +34,12 @@ public record GraphSnapshot(int ver, String comp, long step,
      * 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) { }
+    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) { }
-- 
cgit v1.2.3