From 9b3ad43f7aa2ec6d5f61fb9ff3c432101a5fba52 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Thu, 17 Sep 2026 19:18:46 -0700 Subject: Major overhaul debug printing --- .../java/com/seaofnodes/simple/DebugSchedule.java | 334 +++++++++++++++++++++ .../main/java/com/seaofnodes/simple/IRPrinter.java | 168 ++--------- .../java/com/seaofnodes/simple/IRPrinterTest.java | 189 ++++++++++++ 3 files changed, 554 insertions(+), 137 deletions(-) create mode 100644 chapter10/src/main/java/com/seaofnodes/simple/DebugSchedule.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/IRPrinterTest.java (limited to 'chapter10') diff --git a/chapter10/src/main/java/com/seaofnodes/simple/DebugSchedule.java b/chapter10/src/main/java/com/seaofnodes/simple/DebugSchedule.java new file mode 100644 index 00000000..fea856d5 --- /dev/null +++ b/chapter10/src/main/java/com/seaofnodes/simple/DebugSchedule.java @@ -0,0 +1,334 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import java.util.*; + +/** A debugger's ordering, independent of compiler scheduling and cached dominators. */ +final class DebugSchedule { + static Node input0(Node n) { + return n==null || n._inputs==null || n._inputs.isEmpty() ? null : n._inputs.get(0); + } + + static boolean head(Node n) { return n instanceof RegionNode || n instanceof MultiNode; } + + static boolean projection(Node n) { return n instanceof ProjNode; } + + static boolean cfg(Node n) { // Old ProjNode.isCFG() dereferences its head, which may be missing. + if( n instanceof ProjNode p ) return p._idx==0 || input0(n) instanceof IfNode; + return n!=null && n.isCFG(); } + + static boolean gap(Node n) { return cfg(n) && !projection(n); } + + static boolean child(Node n) { + Node h = input0(n); + return (n instanceof PhiNode && h instanceof RegionNode) || + (projection(n) && h instanceof MultiNode); + } + + private static Node group(Node n, IdentityHashMap selected) { + return child(n) && selected.containsKey(input0(n)) ? input0(n) : n; + } + + private static int order(Node n) { + if( n instanceof ProjNode proj ) return proj._idx; + return n._nid; + } + + // Use identity, not node equality (GVN), for all debugger bookkeeping. + static ArrayList schedule(Node base, int depth) { + ArrayList nodes = new ArrayList<>(); + IdentityHashMap distance = new IdentityHashMap<>(); + add(base,0,nodes,distance); + for( int i=0; i orderNodes(ArrayList nodes) { + IdentityHashMap selected = new IdentityHashMap<>(); + for( Node n : nodes ) selected.put(n,Boolean.TRUE); + IdentityHashMap> members = new IdentityHashMap<>(); + ArrayList groups = new ArrayList<>(); + for( Node n : nodes ) { + Node g = group(n,selected); + if( !members.containsKey(g) ) { + members.put(g,new ArrayList<>()); + groups.add(g); + } + if( n!=g ) members.get(g).add(n); + } + // Reconstruct uses from inputs: incomplete reverse edges must not + // hide nodes. Ignore loop backedges for ordering, but still print them. + IdentityHashMap> uses = new IdentityHashMap<>(); + IdentityHashMap incoming = new IdentityHashMap<>(); + for( Node g : groups ) uses.put(g,new ArrayList<>()); + for( Node n : nodes ) { + if( n._inputs==null ) continue; + Node to = group(n,selected); + for( int i=0; i=2 && (n instanceof LoopNode || + n instanceof PhiNode && input0(n) instanceof LoopNode) ) continue; + + Node from = group(def,selected); + if( from!=to ) { + uses.get(from).add(to); + incoming.put(to,Boolean.TRUE); + } + } + } + Comparator cfgFirst = Comparator + .comparingInt((Node n) -> cfg(n) ? 0 : 1).thenComparingInt(n -> n._nid); + for( ArrayList us : uses.values() ) us.sort(cfgFirst); + groups.sort(Comparator.comparingInt(n -> n._nid)); + IdentityHashMap seen = new IdentityHashMap<>(); + ArrayList post = new ArrayList<>(); + for( Node g : groups ) + if( !incoming.containsKey(g) ) walk(g,uses,seen,post); + // A broken graph may consist entirely of cycles, with no roots. + for( Node g : groups ) walk(g,uses,seen,post); + Collections.reverse(post); + post=nestLoops(nodes,groups,selected,uses,post); + ArrayList result = new ArrayList<>(); + for( Node g : post ) { + result.add(g); + sortChildren(members.get(g)); + result.addAll(members.get(g)); + } + return result; + } + + // Projection lists are short. Select the next idx directly, including + // -1, sparse indices, and deterministic nid order for duplicate indices. + static void sortChildren(ArrayList children) { + for( int i=0; i children(Node head) { + ArrayList children = new ArrayList<>(); + Set seen = Collections.newSetFromMap(new IdentityHashMap<>()); + if( head!=null && head._outputs!=null ) for( Node use : head._outputs ) + if( child(use) && input0(use)==head && seen.add(use) ) children.add(use); + sortChildren(children); + return children; + } + + // Printer-local natural loops. Never ask idom()/loopDepth() to build or + // repair compiler metadata while inspecting a partly constructed graph. + private static final class Region { + final Node head; + final Set cfg = Collections.newSetFromMap(new IdentityHashMap<>()); + Region parent; + final ArrayList nodes = new ArrayList<>(); + ArrayList rpo; + Region(Node head) { this.head = head; } + } + + private record Use(Node node, int input) {} + + private static ArrayList predecessors(Node n) { + ArrayList preds = new ArrayList<>(); + if( !cfg(n) || n._inputs==null || (n instanceof StartNode || n instanceof StopNode) ) return preds; + if( n instanceof RegionNode ) { + for( int i=1; i path = Collections.newSetFromMap(new IdentityHashMap<>()); + for( Region r=a; r!=null; r=r.parent ) path.add(r); + for( Region r=b; r!=null; r=r.parent ) if( path.contains(r) ) return r; + throw new AssertionError("disjoint printer regions"); + } + + private static Region enclosing(Node cfg, ArrayList loops, Region root) { + Region best = root; + for( Region loop : loops ) + if( loop.cfg.contains(cfg) && (best==root || loop.cfg.size() owner) { + Region r = owner.get(n); + if( r==scope ) return n; + while( r!=null && r.parent!=scope ) r=r.parent; + return r==null ? null : r.head; + } + + private static ArrayList nestLoops(ArrayList nodes, ArrayList groups, + IdentityHashMap selected, + IdentityHashMap> uses, + ArrayList post) { + Region root = new Region(null); + ArrayList loops = new ArrayList<>(); + for( Node n : groups ) { + if( !(n instanceof LoopNode) || n instanceof StartNode ) continue; + Region loop = new Region(n); + loop.cfg.add(n); + ArrayList work = new ArrayList<>(); + Node back = n._inputs==null || n._inputs.size()<3 ? null : n._inputs.get(2); + Node entry = n._inputs==null || n._inputs.size()<2 ? null : n._inputs.get(1); + if( cfg(back) && selected.containsKey(back) && loop.cfg.add(back) ) work.add(back); + boolean closed = back==n; + for( int i=0; iloop.cfg.size() && outer.cfg.containsAll(loop.cfg) && + (loop.parent==root || outer.cfg.size() owner = new IdentityHashMap<>(); + IdentityHashMap> users = new IdentityHashMap<>(); + for( Node g : groups ) { + users.put(g,new ArrayList<>()); + if( cfg(g) ) owner.put(g,enclosing(g,loops,root)); + else if( cfg(input0(g)) ) owner.put(g,enclosing(input0(g),loops,root)); + else if( g instanceof ConstantNode ) owner.put(g,root); + } + for( Node use : nodes ) if( use._inputs!=null ) + for( int i=0; i=0; i-- ) { + Node g = post.get(i); + if( owner.containsKey(g) ) continue; + Region place=null; + boolean ready=true; + for( Use use : users.get(g) ) { + Region r=owner.get(group(use.node(),selected)); + if( r==null ) { ready=false; break; } + if( use.node() instanceof PhiNode && input0(use.node()) instanceof LoopNode && + r.head==input0(use.node()) && use.input()==1 ) r=r.parent; + place=place==null ? r : common(place,r); + } + if( ready ) { owner.put(g,place==null ? root : place); progress=true; } + } + } while( progress ); + // Unresolved data cycles do not prevent the rest of the graph printing. + for( Node g : groups ) owner.putIfAbsent(g,root); + for( Region loop : loops ) owner.put(loop.head,loop); + for( Node g : groups ) owner.get(g).nodes.add(g); + for( Region loop : loops ) loop.parent.nodes.add(loop.head); + + ArrayList regions = new ArrayList<>(loops); + regions.add(root); + for( Region scope : regions ) { + IdentityHashMap> edges = new IdentityHashMap<>(); + IdentityHashMap incoming = new IdentityHashMap<>(); + for( Node n : scope.nodes ) edges.put(n,new ArrayList<>()); + for( Node from : groups ) { + Node a=unit(from,scope,owner); + if( a==null ) continue; + for( Node to : uses.get(from) ) { + Node b=unit(to,scope,owner); + if( b!=null && a!=b ) { edges.get(a).add(b); incoming.put(b,Boolean.TRUE); } + } + } + scope.nodes.sort(Comparator.comparingInt(n -> n._nid)); + for( ArrayList es : edges.values() ) + es.sort(Comparator.comparingInt((Node n) -> cfg(n) ? 0 : 1).thenComparingInt(n -> n._nid)); + IdentityHashMap seen = new IdentityHashMap<>(); + scope.rpo = new ArrayList<>(); + if( scope.head!=null ) walk(scope.head,edges,seen,scope.rpo); + for( Node n : scope.nodes ) if( !incoming.containsKey(n) ) walk(n,edges,seen,scope.rpo); + for( Node n : scope.nodes ) walk(n,edges,seen,scope.rpo); + Collections.reverse(scope.rpo); + // Disconnected floating definitions still follow the loop header. + if( scope.head!=null ) { + scope.rpo.removeIf(n -> n==scope.head); + scope.rpo.add(0,scope.head); + } + } + // Expand nested loop vertices without recursive Java calls. + IdentityHashMap byHead = new IdentityHashMap<>(); + for( Region loop : loops ) byHead.put(loop.head,loop); + ArrayList result = new ArrayList<>(); + ArrayDeque scopes = new ArrayDeque<>(); + ArrayDeque> positions = new ArrayDeque<>(); + scopes.push(root); + positions.push(root.rpo.iterator()); + while( !scopes.isEmpty() ) { + if( !positions.peek().hasNext() ) { scopes.pop(); positions.pop(); continue; } + Node n=positions.peek().next(); + Region nested=byHead.get(n); + if( nested!=null && nested.parent==scopes.peek() ) { + scopes.push(nested); + positions.push(nested.rpo.iterator()); + } else result.add(n); + } + return result; + } + + private static void add(Node n, int d, ArrayList nodes, + IdentityHashMap distance) { + if( n!=null && !distance.containsKey(n) ) { + distance.put(n,d); + nodes.add(n); + } + } + + // An explicit DFS stack handles long chains as well as malformed cycles. + private static void walk(Node root, IdentityHashMap> uses, + IdentityHashMap seen, ArrayList post) { + if( seen.put(root,Boolean.TRUE)!=null ) return; + ArrayDeque stack = new ArrayDeque<>(); + ArrayDeque> edges = new ArrayDeque<>(); + stack.push(root); + edges.push(uses.get(root).iterator()); + while( !stack.isEmpty() ) { + if( edges.peek().hasNext() ) { + Node use = edges.peek().next(); + if( seen.put(use,Boolean.TRUE)==null ) { + stack.push(use); + edges.push(uses.get(use).iterator()); + } + } else { + post.add(stack.pop()); + edges.pop(); + } + } + } +} diff --git a/chapter10/src/main/java/com/seaofnodes/simple/IRPrinter.java b/chapter10/src/main/java/com/seaofnodes/simple/IRPrinter.java index f08f3208..95c83ab1 100644 --- a/chapter10/src/main/java/com/seaofnodes/simple/IRPrinter.java +++ b/chapter10/src/main/java/com/seaofnodes/simple/IRPrinter.java @@ -1,36 +1,33 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.node.LoopNode; -import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.ProjNode; - -import java.util.ArrayList; -import java.util.BitSet; +import com.seaofnodes.simple.node.*; public class IRPrinter { - // Print a node on 1 line, columnar aligned, as: - // NNID NNAME DDEF DDEF [[ UUSE UUSE ]] TYPE - // 1234 sssss 1234 1234 1234 1234 1234 1234 tttttt - public static void _printLine( Node n, StringBuilder sb ) { - sb.append("%4d %-7.7s ".formatted(n._nid,n.label())); - if( n._inputs==null ) { - sb.append("DEAD\n"); - return; - } + // Inspect raw edges so a partly built/dead node is still useful to print. + private static String label(Node n) { + if( n._inputs==null ) return n.getClass().getSimpleName(); + try { return n.label(); } + catch( RuntimeException | AssertionError ex ) { return n.getClass().getSimpleName(); } + } + + private static String type(Node n) { + if( n._type==null ) return ""; + try { return n._type.str(); } + catch( RuntimeException | AssertionError ex ) { return ""; } + } + + public static void _printLine(Node n, StringBuilder sb) { + if( n==null ) return; + sb.append("%4d %-7.7s ".formatted(n._nid,label(n))); + if( n._inputs==null ) { sb.append("DEAD\n"); return; } for( Node def : n._inputs ) sb.append(def==null ? "____ " : "%4d ".formatted(def._nid)); - for( int i = n._inputs.size(); i<3; i++ ) - sb.append(" "); + for( int i=n._inputs.size(); i<4; i++ ) sb.append(" "); sb.append(" [[ "); - for( Node use : n._outputs ) + if( n._outputs!=null ) for( Node use : n._outputs ) sb.append(use==null ? "____ " : "%4d ".formatted(use._nid)); - int lim = 5 - Math.max(n._inputs.size(),3); - for( int i = n._outputs.size(); i"); } + sb.append(" = ").append( label(n) ).append( "(" ); for( int i = 0; i < n._inputs.size(); i++ ) { - Node def = n.in(i); + Node def = n._inputs.get(i); if (i > 0) sb.append(", "); if (def == null) sb.append("_"); @@ -68,121 +67,16 @@ public class IRPrinter { } public static String prettyPrint(Node node, int depth) { - return prettyPrint( node, depth, false ); + return prettyPrint(node,depth,false); } - // Another bulk pretty-printer. Makes more effort at basic-block grouping. - public static String prettyPrint( Node node, int depth, boolean llvmFormat ) { - // First, a Breadth First Search at a fixed depth. - BFS bfs = new BFS(node,depth); - // Convert just that set to a post-order - ArrayList rpos = new ArrayList<>(); - BitSet visit = new BitSet(); - for( int i=bfs._lim; i< bfs._bfs.size(); i++ ) - postOrd( bfs._bfs.get(i), rpos, visit, bfs._bs); - // Reverse the post-order walk + public static String prettyPrint(Node node, int depth, boolean llvmFormat) { StringBuilder sb = new StringBuilder(); - boolean gap=false; - for( int i=rpos.size()-1; i>=0; i-- ) { - Node n = rpos.get(i); - if( n.isCFG() || n.isMultiHead() ) { - if( !gap ) sb.append("\n"); // Blank before multihead - printLine( n, sb, llvmFormat ); // Print head - while( --i >= 0 ) { - Node t = rpos.get(i); - if( !t.isMultiTail() ) { i++; break; } - printLine( t, sb, llvmFormat ); - } - sb.append("\n"); // Blank after multitail - gap = true; - } else { - printLine( n, sb, llvmFormat ); - gap = false; - } + for( Node n : DebugSchedule.schedule(node,depth) ) { + if( DebugSchedule.gap(n) ) sb.append('\n'); + printLine(n,sb,llvmFormat); } return sb.toString(); } - private static void postOrd(Node n, ArrayList rpos, BitSet visit, BitSet bfs) { - if( !bfs.get(n._nid) ) - return; // Not in the BFS visit - if( visit.get(n._nid) ) return; // Already post-order walked - visit.set(n._nid); - // First walk the CFG, then everything - if( n.isCFG() ) { - for( Node use : n._outputs ) - if( use!=null && use.isCFG() && use.nOuts()>=1 && !(use._outputs.get(0) instanceof LoopNode) ) - postOrd(use, rpos,visit,bfs); - for( Node use : n._outputs ) - if( use!=null && use.isCFG() ) - postOrd(use,rpos,visit,bfs); - } - for( Node use : n._outputs ) - if( use != null ) - postOrd(use, rpos,visit,bfs); - // Post-order - rpos.add(n); - } - - // Breadth-first search, broken out in a class to keep in more independent. - // Maintains a root-set of Nodes at the limit (or past by 1 if MultiHead). - public static class BFS { - // A breadth first search, plus MultiHeads for any MultiTails - public final ArrayList _bfs; - public final BitSet _bs; // Visited members by node id - public final int _depth; // Depth limit - public final int _lim; // From here to _bfs._len can be roots for a reverse search - public BFS( Node base, int d ) { - _depth = d; - _bfs = new ArrayList<>(); - _bs = new BitSet(); - - add(base); // Prime the pump - int idx=0, lim=1; // Limit is where depth counter changes - while( idx < _bfs.size() ) { // Ran out of nodes below depth - Node n = _bfs.get(idx++); - for( Node def : n._inputs ) - if( def!=null && !_bs.get(def._nid) ) - add(def); - if( idx==lim ) { // Depth counter changes at limit - if( --d < 0 ) - break; // Ran out of depth - lim = _bfs.size(); // New depth limit - } - } - // Toss things past the limit except multi-heads - while( idx < _bfs.size() ) { - Node n = _bfs.get(idx); - if( n.isMultiHead() ) idx++; - else del(idx); - } - // Root set is any node with no inputs in the visited set - lim = _bfs.size(); - for( int i=_bfs.size()-1; i>=0; i-- ) - if( !any_visited(_bfs.get(i)) ) - swap( i,--lim); - _lim = lim; - } - void swap( int x, int y ) { - if( x==y ) return; - Node tx = _bfs.get(x); - Node ty = _bfs.get(y); - _bfs.set(x,ty); - _bfs.set(y,tx); - } - void add(Node n) { - _bfs.add(n); - _bs.set(n._nid); - } - void del(int idx) { - Node n = Utils.del(_bfs, idx); - _bs.clear(n._nid); - } - boolean any_visited( Node n ) { - for( Node def : n._inputs ) - if( def!=null && _bs.get(def._nid) ) - return true; - return false; - } - } } diff --git a/chapter10/src/test/java/com/seaofnodes/simple/IRPrinterTest.java b/chapter10/src/test/java/com/seaofnodes/simple/IRPrinterTest.java new file mode 100644 index 00000000..91e9f32e --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/IRPrinterTest.java @@ -0,0 +1,189 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.*; +import java.util.*; +import org.junit.Test; +import static org.junit.Assert.*; + +public class IRPrinterTest { + private static final String SOURCE = """ + int sum=0; + int i=0; + while(i nodes = inputs(stop); + IdentityHashMap> defs = new IdentityHashMap<>(); + IdentityHashMap> uses = new IdentityHashMap<>(); + IdentityHashMap types = new IdentityHashMap<>(); + for( Node n : nodes ) { + defs.put(n,copy(n._inputs)); + uses.put(n,copy(n._outputs)); + types.put(n,n._type); + } + String printed = IRPrinter.prettyPrint(stop,999); + assertEquals(printed,IRPrinter.prettyPrint(stop,999)); + List ids = ids(printed); + assertEquals(ids.size(),new HashSet<>(ids).size()); + int loops = 0; + for( Node n : nodes ) { + assertTrue("missing node " + n._nid,ids.contains(n._nid)); + assertEquals(defs.get(n),copy(n._inputs)); + assertEquals(uses.get(n),copy(n._outputs)); + assertSame(types.get(n),n._type); + if( !(n instanceof LoopNode) ) continue; + loops++; + ArrayList phis = new ArrayList<>(); + for( Node use : n._outputs ) + if( use instanceof PhiNode && use._inputs.get(0)==n ) phis.add(use); + phis.sort(Comparator.comparingInt(p -> p._nid)); + int idx = ids.indexOf(n._nid); + for( Node phi : phis ) assertEquals(Integer.valueOf(phi._nid),ids.get(++idx)); + } + assertTrue("nested source loops must remain",loops>=2); + + } + + @Test(timeout=5000) public void testBrokenGraphs() { + Node stop = new Parser(SOURCE).parse(); + // No entry control or backedge yet, and no reverse edge for the Phi. + LoopNode loop = new LoopNode(null); + PhiNode phi = new PhiNode("x",TypeInteger.BOT,loop,null,null); + loop._outputs.clear(); + List header = ids(IRPrinter.prettyPrint(phi,0)); + assertEquals(Arrays.asList(loop._nid,phi._nid),header); + // An orphan projection's label may itself dereference missing inputs. + ProjNode proj = new ProjNode(null,0,"broken"); + assertTrue(ids(IRPrinter.prettyPrint(proj,0)).contains(proj._nid)); + // A data cycle with no roots must terminate and print both nodes once. + AddNode a = new AddNode(null,null); + AddNode b = new AddNode(a,null); + a._inputs.set(1,b); + a._outputs.add(null); // keep edge + List cycle = ids(IRPrinter.prettyPrint(a,999)); + assertEquals(2,cycle.size()); + assertTrue(cycle.contains(a._nid)); + assertTrue(cycle.contains(b._nid)); + a._inputs.clear(); + assertTrue(ids(IRPrinter.prettyPrint(a,999)).contains(a._nid)); + assertEquals("",IRPrinter.prettyPrint(null,999)); + } + + @Test public void testProjectionOrderAndSpacing() { + new Parser("return 0;").parse(); + IfNode multi = new IfNode(null,null); + ProjNode p2 = new ProjNode(multi,2,"two"); + ProjNode pm = new ProjNode(multi,-1,"minus"); + ProjNode p1 = new ProjNode(multi,1,"one"); + ProjNode p0 = new ProjNode(multi,0,"zero"); + String printed = IRPrinter.prettyPrint(p2,0); + assertEquals(Arrays.asList(multi._nid,pm._nid,p0._nid,p1._nid,p2._nid),ids(printed)); + String[] lines = printed.split("\n"); + int first = line(lines,multi); + assertTrue(first>0 && lines[first-1].isBlank()); + assertEquals(first+1,line(lines,pm)); + assertEquals(first+2,line(lines,p0)); + assertEquals(first+3,line(lines,p1)); + assertEquals(first+4,line(lines,p2)); + } + + @Test public void testNestedLoopRpo() { + new Parser("return 0;").parse(); + LoopNode outer = new LoopNode(null); + LoopNode inner = new LoopNode(outer); + PhiNode op = new PhiNode("outer",TypeInteger.BOT,outer,null,null); + PhiNode ip = new PhiNode("inner",TypeInteger.BOT,inner,null,null); + AddNode innerValue = new AddNode(ip,null); + AddNode outerValue = new AddNode(ip,op); + ip._inputs.set(2,innerValue); + op._inputs.set(2,outerValue); + IfNode branch = new IfNode(inner,ip); + ProjNode left = new ProjNode(branch,0,"left"); + ProjNode right = new ProjNode(branch,1,"right"); + RegionNode join = new RegionNode(null,left,right); + IfNode innerLatch = new IfNode(join,ip); + ProjNode innerBack = new ProjNode(innerLatch,0,"innerBack"); + ProjNode innerExit = new ProjNode(innerLatch,1,"innerExit"); + inner._inputs.set(2,innerBack); + IfNode outerLatch = new IfNode(innerExit,op); + ProjNode outerBack = new ProjNode(outerLatch,0,"outerBack"); + ProjNode outerExit = new ProjNode(outerLatch,1,"outerExit"); + outer._inputs.set(2,outerBack); + IfNode after = new IfNode(outerExit,op); + + // Raw input edits deliberately leave incomplete reverse edges. + String printed = IRPrinter.prettyPrint(after,999); + List ids = ids(printed); + assertEquals(ids.size(),new HashSet<>(ids).size()); + before(ids,outer,inner); + before(ids,inner,branch); + before(ids,branch,join); + before(ids,join,innerLatch); + before(ids,innerLatch,outerLatch); + before(ids,innerValue,outerValue); + before(ids,innerLatch,outerValue); + before(ids,outerValue,outerLatch); + before(ids,outerLatch,after); + assertEquals(Integer.valueOf(ip._nid),ids.get(ids.indexOf(inner._nid)+1)); + assertEquals(Integer.valueOf(op._nid),ids.get(ids.indexOf(outer._nid)+1)); + String[] lines = printed.split("\n"); + for( Node cfg : new Node[]{outer,inner,branch,join,innerLatch,outerLatch,after} ) { + int idx=line(lines,cfg); + assertTrue("blank before CFG " + cfg._nid,idx>0 && lines[idx-1].isBlank()); + } + assertEquals(line(lines,branch)+1,line(lines,left)); + assertEquals(line(lines,branch)+2,line(lines,right)); + } + + private static void before(List ids, Node a, Node b) { + assertTrue("missing " + a._nid,ids.contains(a._nid)); + assertTrue("missing " + b._nid,ids.contains(b._nid)); + assertTrue(a._nid + " before " + b._nid,ids.indexOf(a._nid) ids(String text) { + ArrayList ids = new ArrayList<>(); + for( String line : text.split("\n") ) { + String s = line.trim(); + if( !s.isEmpty() && Character.isDigit(s.charAt(0)) ) + ids.add(Integer.valueOf(s.split("\\s+",2)[0])); + } + return ids; + } + + private static ArrayList inputs(Node root) { + ArrayList nodes = new ArrayList<>(); + IdentityHashMap seen = new IdentityHashMap<>(); + nodes.add(root); + seen.put(root,Boolean.TRUE); + for( int i=0; i copy(Iterable edges) { + ArrayList copy = new ArrayList<>(); + if( edges!=null ) for( Node n : edges ) copy.add(n); + return copy; + } +} -- cgit v1.2.3