Class cycles init checks

7 files changed, 192 insertions, 50 deletions

diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java
index 331ff05d..f0c4567f 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java
@@ -4,6 +4,7 @@ import com.seaofnodes.simple.codegen.*;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.util.Ary;
+import com.seaofnodes.simple.util.BAOS;
 import com.seaofnodes.simple.node.ScopeNode.Kind;
 
 import static com.seaofnodes.simple.util.Utils.TODO;
@@ -168,7 +169,7 @@ public class Parser {
     public Ary<FRefNode> parse( CompUnit ref ) {
         assert _scope == null && _breakScope == null && _continueScope == null && _returnScope == null;
         assert _frefs == null;
-        _lexer = new Lexer(ref._src);
+        _lexer = new Lexer(ref);
         _frefs = new Ary<>(FRefNode.class);
         // Starting Scope has control, memory, initial arguments
         _scope = new ScopeNode();
@@ -2231,6 +2232,8 @@ public class Parser {
         return parsePostfix(expr);
     }
     private Node parsePostfix(Node expr) {
+        _lexer.skipWhiteSpace();
+        Lexer site = loc();
         String name;
         if( match(".") )      name = requireId();
         else if( match("#") ) name = "#";
@@ -2240,7 +2243,7 @@ public class Parser {
         else if( match("(") ) return parsePostfix(require(functionCall(expr,defaultSelf()),")"));
         else return expr;       // No postfix
 
-        return parsePostfixName(expr,name,0);
+        return parsePostfixName(expr,name,0,site);
     }
 
     private Node defaultSelf() {
@@ -2261,6 +2264,10 @@ public class Parser {
 
     // pre is +/-1 for a prefix update, otherwise parse a postfix operation.
     private Node parsePostfixName(Node expr, String name, int pre) {
+        return parsePostfixName(expr,name,pre,loc());
+    }
+
+    private Node parsePostfixName(Node expr, String name, int pre, Lexer site) {
         // Keep expr across possible updates
         expr.keep();
 
@@ -2308,7 +2315,7 @@ public class Parser {
         Kind.Func func = (Kind.Func)_scope._kinds.at(_scope.enclosingFuncOrDecl());
         if( (ts==null || ts==TypeStruct.BOT || ts.isHigh() || startsClzPrefix(ts._name)) &&
             !(ts!=null && (ts._name+".<clinit>").equals(func._name)) )
-            ctrl(new CLInitNode(loc(),ctrl(),expr).peephole());
+            ctrl(new CLInitNode(site,ctrl(),expr).peephole());
 
         // With no field, we will update the bulk memory
         int alias = fld==null ?  1          : fld._alias;
@@ -2473,6 +2480,8 @@ public class Parser {
      * </pre>
      */
     private Node functionCall(Node fcn, Node self) {
+        Lexer site = loc();
+        site._position--; // Opening '('; arguments can contain nested calls.
         if( fcn._type == Type.NIL )
             throw error("Calling a null function pointer");
         fcn.keep();            // Keep while parsing args
@@ -2495,10 +2504,14 @@ public class Parser {
         // Unkeep them all
         for( Node arg : args )
             arg.unkeep();
-        return functionCall(args);
+        return functionCall(args,site);
     }
 
     private Node functionCall( Ary<Node> args ) {
+        return functionCall(args,loc());
+    }
+
+    private Node functionCall( Ary<Node> args, Lexer site ) {
         // Dead into the call?  Skip all the node gen
         if( ctrl()._type == Type.XCONTROL ) {
             for( Node arg : args )
@@ -2508,7 +2521,7 @@ public class Parser {
         }
 
         // Into the call
-        CallNode call = (CallNode)new CallNode(loc(), args.asAry()).peephole();
+        CallNode call = (CallNode)new CallNode(site, args.asAry()).peephole();
         // Post-call setup
         CallEndNode cend = (CallEndNode)new CallEndNode(call,TypeRPC.constant(_code.rpc(_ref._cname))).peephole();
         call.peephole();        // Rerun peeps after CallEnd, allows early inlining
@@ -2694,6 +2707,7 @@ public class Parser {
 
         // Input buffer; an array of text bytes read from a file or a string
         private final byte[] _input;
+        public final CompUnit _cu; // Original source, retained across inlining.
         // Tracks current position in input buffer
         private int _position = 0;
 
@@ -2704,12 +2718,11 @@ public class Parser {
 
         /** True when this location precedes {@code that} in the same source. */
         public boolean before(Lexer that) {
-            return that != null && _input == that._input && _position < that._position;
+            return that != null && (_cu!=null ? _cu==that._cu : _input==that._input) && _position < that._position;
         }
 
         public String position() { return _line_number+":"+(_position-_line_start+1); }
-        // Numeric location for diagnostics that must survive without source text.
-        public long lineColumn() { return ((long)_line_number<<32) | (_position-_line_start+1); }
+        public int pos() { return _position; }
 
         /**
          * Record the source text for lexing
@@ -2723,6 +2736,45 @@ public class Parser {
          */
         public Lexer(byte[] buf) {
             _input = buf;
+            _cu = null;
+        }
+
+        private Lexer(CompUnit cu) {
+            _input = cu._src.getBytes();
+            _cu = cu;
+        }
+
+        // Imported location: source text is only needed when reporting an error.
+        private Lexer(CompUnit cu, int pos) {
+            _input = null;
+            _cu = cu;
+            _position = pos;
+        }
+
+        public static void gather(Lexer loc, HashMap<String,Integer> strs) {
+            if( loc==null || loc._cu==null ) return;
+            Serialize.gather(strs,loc._cu._cname);
+            String file=loc._cu.sourceFile();
+            if( file!=null ) Serialize.gather(strs,file);
+        }
+
+        public static void packed(Lexer loc, BAOS out, HashMap<String,Integer> strs) {
+            if( loc==null || loc._cu==null ) { out.packed4(0); return; }
+            out.packed4(loc._position+1);
+            out.packed4(strs.get(loc._cu._cname));
+            String file=loc._cu.sourceFile();
+            out.packed4(file==null ? 0 : strs.get(file));
+        }
+
+        public static Lexer unpack(BAOS in, String[] strs) {
+            int pos=in.packed4();
+            if( pos==0 ) return null;
+            String owner=strs[in.packed4()];
+            String file=strs[in.packed4()];
+            CompUnit cu=CodeGen.CODE._compunits.get(owner.replace('.','/'));
+            assert cu!=null : owner;
+            if( !file.isEmpty() ) cu._sourceFile=file;
+            return new Lexer(cu,pos-1);
         }
 
         /**
@@ -2730,6 +2782,7 @@ public class Parser {
          */
         private Lexer(Lexer l) {
             _input = l._input;
+            _cu = l._cu;
             _position = l._position;
             _line_number = l._line_number;
             _line_start = l._line_start;
@@ -2738,7 +2791,7 @@ public class Parser {
         // Very handy in the debugger, shows the unparsed program
         @Override
         public String toString() {
-            return new String(_input, _position, _input.length - _position);
+            return _input==null ? _cu._cname+"@"+_position : new String(_input, _position, _input.length - _position);
         }
 
         // True if at EOF
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java
index 0150219e..df3be2d0 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/ClassInitDependencies.java
@@ -1,5 +1,6 @@
 package com.seaofnodes.simple.codegen;
 
+import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.node.*;
 import com.seaofnodes.simple.type.*;
 import com.seaofnodes.simple.util.*;
@@ -15,13 +16,11 @@ import java.util.*;
 // CompUnits from CLInitNodes, and the set of fcn call targets in f and the
 // class parent.  These are all reported as fidxs (ints).
 //
-// (2) Walk the _edges graph using Tarjans SCC.  Stop at cycles containing a
-// <clint> (and continue with cycles NOT containing a <clinit>, which is
-// ordinary recursive functions).
+// (2) Walk the _edges graph using Tarjans SCC. Reject cycles containing more
+// than one <clinit>.
 //
 // (3) Report on <clinit> cycles
 //
-//
 public class ClassInitDependencies {
     private final CodeGen _code;
     // Function FIDX -> callees, touched initializers, and parent initializer.
@@ -50,12 +49,13 @@ public class ClassInitDependencies {
         for( FunNode fun : code._linker )
             if( fun!=null && !fun.isDead() )
                 // Visit function and collect direct class touches and callees
-                _edgess[fun.sig().fidx()] = walk(code,fun,work,iset,visit);
+                _edgess[fun.sig().fidx()] = walk(code,fun,work,iset,visit,null);
         visit.clear();
     }
 
     // Return the outgoing init edge set for this function
-    private static int[] walk( CodeGen code, FunNode fun, Ary<CFGNode> work, IntHashMap iset, BitSet visit) {
+    private static int[] walk( CodeGen code, FunNode fun, Ary<CFGNode> work, IntHashMap iset, BitSet visit,
+                              Ary<Parser.Lexer> sites) {
         // Walk function body, looking for outgoing init edges
         assert iset .isEmpty(); // int hash set for de-dup
         assert visit.isEmpty(); // needs a visit set, because loops
@@ -79,14 +79,17 @@ public class ClassInitDependencies {
             if( cfg instanceof CLInitNode init ) {
                 FunNode clz = code.link(init.cu()); // <clinit> referred to
                 iset.put(clz.sig().fidx(),1);       // Add to edge set
+                if( sites!=null && sites.atX(clz.sig().fidx())==null ) sites.setX(clz.sig().fidx(),init._loc);
             }
 
             // Calls union all their fptr fidxs into the callee set
             if( cfg instanceof CallNode call && call.fptr()._type instanceof TypeFunPtr fp ) {
                 assert !XInt.isHigh(fp.fidxs()) && fp.nfcns()>0; // Call is alive with valid targets
                 // Union call targets into the callee set
-                for( int dstx = XInt.next(fp.fidxs(),0); dstx>=0; dstx=XInt.next(fp.fidxs(),dstx) )
+                for( int dstx = XInt.next(fp.fidxs(),0); dstx>=0; dstx=XInt.next(fp.fidxs(),dstx) ) {
                     iset.put(dstx,1);
+                    if( sites!=null && sites.atX(dstx)==null ) sites.setX(dstx,call._loc);
+                }
             }
 
             // Forward recursion to walk the whole function
@@ -106,36 +109,61 @@ public class ClassInitDependencies {
         return edges;
     }
 
-    // Return an error string, or null for an acyclic class-init graph.
+    // Return an error string, or null if no cycle contains multiple clinits.
     public String check() {
+        Arrays.fill(_pres,0);
+        _sp = 0;
         _pres[0] = 1;           // Preorders stored in pres[0] and start at 1
-        BitSet visit = _code.visit();
 
-        int idx = 0;
-        for( int fidx = 1; fidx < _edgess.length; fidx++ ) {
-            if( _pres[fidx] == 0 ) // Already visited
-                idx = scc(fidx);
-            if( idx != -1 ) break; // Found a clz cycle
-        }
-        visit.clear();
+        int idx = -1;
+        for( int fidx = 1; fidx < _edgess.length; fidx++ )
+            if( _pres[fidx] == 0 &&       // Already visited
+                (idx = scc(fidx)) != -1 ) // And found a cycle
+                return report(idx);       // Report cycle
+        return null;
+    }
 
-        // Error report for a clz heading a cycle
-        if( idx != -1 ) {
-            SB sb = new SB().p("Cyclic class initialization: ");
-            String first = null;
-            for( int i=idx; i<_sp; i++ ) {
-                FunNode fun = _code.link(_stk[i]);
-                if( fun.isClz() ) {
-                    if( first==null ) first = fun._compunit._cname;
-                    sb.p(fun._compunit._cname).p(" -> ");
-                }
-            }
-            sb.p(first);
-            visit.clear();
-            return sb.toString();
+    // Every internal edge of an SCC belongs to a cycle. Print all of them:
+    // stack order is not a path, and enumerating all cycle paths can explode.
+    // This bookkeeping and formatting are only needed on an error.
+    private String report(int idx) {
+        BitSet members = new BitSet();
+        for( int i=idx; i<_sp; i++ ) members.set(_stk[i]);
+        SB sb = new SB().p("Cyclic class initialization:");
+        // Recover one surviving source site per edge only after finding an
+        // error. A representative touch is enough; runtime first-touch order
+        // need not be statically known. Lexer snapshots retain the source CU
+        // even when the node has been inlined into a different function.
+        Ary<CFGNode> work = new Ary<>(CFGNode.class);
+        IntHashMap iset = new IntHashMap(0);
+        BitSet visit = new BitSet();
+        Ary<Parser.Lexer> sites = new Ary<>(Parser.Lexer.class);
+        for( int i=idx; i<_sp; i++ ) {
+            int src = _stk[i];
+            FunNode fun = _code.link(src);
+            Arrays.fill(sites._es,null);
+            sites.clear();
+            walk(_code,fun,work,iset,visit,sites);
+            if( _edgess[src]!=null )
+                for( int dst : _edgess[src] )
+                    if( members.get(dst) ) {
+                        sb.p("\n  ").p(name(src)).p(" -> ").p(name(dst));
+                        Parser.Lexer loc = sites.atX(dst);
+                        if( loc!=null && loc._cu!=null )
+                            sb.p('\n').p(SourceError.format(loc._cu,loc.pos(),"cyclic class initialization"));
+                        else if( fun.isClz() && fun._compunit._par==_code.link(dst)._compunit )
+                            sb.p("\n    parent initialization requirement");
+                    }
         }
+        return sb.toString();
+    }
 
-        return null;            // No errors
+    private String name(int fidx) {
+        FunNode fun = _code.link(fidx);
+        String owner=fun._compunit._cname;
+        if( fun.isClz() ) return owner;
+        String label=fun.label();
+        return (label.startsWith(owner+".") ? label : owner+"."+label)+" [fidx "+fidx+"]";
     }
 
     // Tarjan SCC
@@ -174,10 +202,12 @@ public class ClassInitDependencies {
     private boolean onStk(int e) { return find(e) != -1; }
 
     private boolean hasClzCycle(int idx) {
-        if( idx+1 == _sp ) return false; // Cycle of 1 does not count
-        for( int i=idx; i<_sp; i++ )
-            if( _code.link(_stk[i]).isClz() )
+        int clinits = 0;
+        for( int i=idx; i<_sp; i++ ) {
+            FunNode fun = _code.link(_stk[i]);
+            if( fun!=null && fun.isClz() && ++clinits > 1 )
                 return true;
+        }
         return false;
     }
 
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java
index 544ca27e..128c4136 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/CompUnit.java
@@ -24,6 +24,13 @@ public class CompUnit {
     final File _smp;            // Simple source file, e.g. module_root/A/B/C.smp
     public final File _obj;     // ELF output file, e.g. build/A/B/C.o
     final public String _src;   // Source code, from file or test case
+    // Original source path from an imported diagnostic location. Does not
+    // affect discovery/rebuild decisions, which use _smp and _src.
+    public String _sourceFile;
+
+    public String sourceFile() {
+        return _smp!=null ? _smp.getAbsolutePath() : _sourceFile;
+    }
 
     public TypeStruct _clz; // The one TypeStruct being published
 
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/SourceError.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/SourceError.java
new file mode 100644
index 00000000..f2f46146
--- /dev/null
+++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/SourceError.java
@@ -0,0 +1,49 @@
+package com.seaofnodes.simple.codegen;
+
+import com.seaofnodes.simple.util.SB;
+import java.io.IOException;
+import java.nio.charset.StandardCharsets;
+import java.nio.file.Files;
+import java.nio.file.Path;
+
+/** Format one parser byte offset. Source is read and text built only on error. */
+public abstract class SourceError {
+    public static String format(CompUnit cu, int pos, String message) {
+        String file=cu.sourceFile();
+        String name=file==null ? cu._fname+".smp" : file;
+        byte[] source;
+        try {
+            source=cu._src!=null ? cu._src.getBytes(StandardCharsets.UTF_8)
+                : file==null ? null : Files.readAllBytes(Path.of(file));
+        } catch( IOException ex ) { source=null; }
+        if( source==null || pos<0 || pos>source.length )
+            return name+": error: "+message+" (source unavailable at byte offset "+pos+")";
+
+        int line=1, start=0;
+        for( int i=0; i<pos; i++ )
+            if( source[i]=='\n' ) { line++; start=i+1; }
+        int end=pos;
+        while( end<source.length && source[end]!='\n' ) end++;
+        if( end>start && source[end-1]=='\r' ) end--;
+        int point=Math.min(pos,end);
+        String before=new String(source,start,point-start,StandardCharsets.UTF_8);
+        String text=new String(source,start,end-start,StandardCharsets.UTF_8);
+        int column=before.codePointCount(0,before.length())+1;
+        SB sb=new SB().p(name).p(':').p(line).p(':').p(column).p(": error: ").p(message).p("\n    ");
+        int width=0, caret=0;
+        for( int i=0; i<text.length(); ) {
+            if( i==before.length() ) caret=width;
+            int ch=text.codePointAt(i);
+            if( ch=='\t' ) {
+                int spaces=8-(width%8);
+                for( int j=0; j<spaces; j++ ) sb.p(' ');
+                width+=spaces;
+            } else { sb.p(new String(Character.toChars(ch))); width++; }
+            i+=Character.charCount(ch);
+        }
+        if( before.length()==text.length() ) caret=width;
+        sb.p("\n    ");
+        for( int i=0; i<caret; i++ ) sb.p('-');
+        return sb.p('^').toString();
+    }
+}
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java
index 5131049e..c9aeb874 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CLInitNode.java
@@ -22,10 +22,12 @@ public class CLInitNode extends CFGNode {
         _loc = loc;
     }
 
-    CLInitNode(BAOS bais) { super(null,null); }
+    CLInitNode(BAOS bais, String[] strs) { super(null,null); _loc=Parser.Lexer.unpack(bais,strs); }
     @Override public Tag serialTag() { return Tag.CLInit; }
     @Override public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) {
+        Parser.Lexer.packed(_loc,baos,strs);
     }
+    @Override public void gather(HashMap<String,Integer> strs) { Parser.Lexer.gather(_loc,strs); }
 
     public CLInitNode(CLInitNode init) {
         super(init);
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java
index 38117f23..b4bb5e72 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java
@@ -22,16 +22,17 @@ public class CallNode extends CFGNode {
     // Source location for late reported errors
     public final Parser.Lexer _loc;
 
-    public CallNode(Parser.Lexer loc, Node... nodes) { this(loc,loc==null ? 0 : loc.lineColumn(),nodes); }
-    private CallNode(Parser.Lexer loc, long position, Node... nodes) { super(nodes); _loc=loc; }
+    public CallNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc=loc; }
     public CallNode(CallNode call) { super(call); _loc = call._loc; }
     @Override public Tag serialTag() { return Tag.Call; }
     public void packed( BAOS baos, HashMap<String,Integer> strs, HashMap<Type,Integer> types, IdentityHashMap<Node, Integer> anodes ) {
         baos.packed1(nIns());
+        Parser.Lexer.packed(_loc,baos,strs);
     }
-    static Node make( BAOS bais ) {
+    @Override public void gather(HashMap<String,Integer> strs) { Parser.Lexer.gather(_loc,strs); }
+    static Node make( BAOS bais, String[] strs ) {
         int nIns = bais.packed1();
-        return new CallNode(null,new Node[nIns]);
+        return new CallNode(Parser.Lexer.unpack(bais,strs),new Node[nIns]);
     }
 
     @Override protected ExprPrinter<Node> _print1(ExprPrinter<Node> p) {
diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java
index 796965b5..77b43ba8 100644
--- a/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java
+++ b/chapter25/src/main/java/com/seaofnodes/simple/node/Node.java
@@ -112,9 +112,9 @@ public abstract class Node extends BaseNode<Node> implements Cloneable {
             case LE    -> new  BoolNode.LE (null,null,(byte)bais.packed1());
             case ULT   -> new  BoolNode.ULT(null,null,(byte)bais.packed1());
 
-            case Call  ->      CallNode.make(bais);
+            case Call  ->      CallNode.make(bais,strs);
             case CallEnd->  CallEndNode.make(bais     ,types);
-            case CLInit ->    new CLInitNode(bais);
+            case CLInit ->    new CLInitNode(bais,strs);
             case CProj ->     CProjNode.make(bais,strs);
             case Con   ->  ConstantNode.make(bais     ,types);
             case Escape->    EscapeNode.make(bais     ,types);