Constructors

Missing arrays yet.
Allow constructor syntax in 2 parts; the type description and at the New.
must-init fields (final and not-null) have to be initialized in at least one of the two places;
finals must be initialized exactly once.
Any code is allowed in the constructors.

6 files changed, 215 insertions, 100 deletions

diff --git a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java
index bdd14de6..572c170a 100644
--- a/chapter16/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter16/src/main/java/com/seaofnodes/simple/Parser.java
@@ -7,7 +7,7 @@ import java.util.*;
 
 /**
  * The Parser converts a Simple source program to the Sea of Nodes intermediate
- * representation directly in one pass. There is no intermediate Abstract
+ * representation directly in one pass.  There is no intermediate Abstract
  * Syntax Tree structure.
  * <p>
  * This is a simple recursive descent parser. All lexical analysis is done here as well.
@@ -97,6 +97,10 @@ public class Parser {
     // have C-style '*ptr' references.
     public static HashMap<String, Type> TYPES = new HashMap<>();
 
+    // Mapping from a type name to the constructor for a Type.
+    public static HashMap<String, StructNode> INITS = new HashMap<>();
+
+
     public Parser(String source, TypeInteger arg) {
         Node.reset();
         IterPeeps.reset();
@@ -115,6 +119,7 @@ public class Parser {
         TYPES.put("u16" ,TypeInteger.U16);
         TYPES.put("u32" ,TypeInteger.U32);
         TYPES.put("u8"  ,TypeInteger.U8 );
+        INITS.clear();
         SCHEDULED = false;
         _lexer = new Lexer(source);
         _scope = new ScopeNode();
@@ -205,65 +210,6 @@ public class Parser {
         // to ambiguity
         else return parseExpressionStatement();
     }
-
-    /**
-     * Parse a struct field.
-     * <pre>
-     *     type IDENTIFIER ;
-     * </pre>
-     */
-    //private Field parseField() {
-    //    Type t = type();
-    //    if( t==null )
-    //        throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'");
-    //    boolean xfinal = match("!");
-    //    return require(Field.make(requireId().intern(),t,ALIAS++,xfinal),";");
-    //}
-
-    /**
-     * Parse a struct declaration, and return the following statement.
-     * Only allowed in top level scope.
-     * Structs cannot be redefined.
-     *
-     * @return The statement following the struct
-     */
-    private Node parseStruct() {
-        if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope");
-        String typeName = requireId();
-        Type t = TYPES.get(typeName);
-        if( t!=null && !(t instanceof TypeMemPtr tmp && tmp._obj._fields==null) )
-            throw errorSyntax("struct '" + typeName + "' cannot be redefined");
-        // A Block scope parse, and inspect the scope afterwards for fields.
-        _scope.push();
-        require("{");
-        while (!peek('}') && !_lexer.isEOF())
-            parseStatement();
-        require("}");
-        // Grab the declarations and build fields
-        HashMap<String,Type> decls = _scope._decls.lastElement();
-        HashMap<String,Integer> idxs = _scope._idxs.lastElement();
-        BitSet finals = _scope._finals;
-
-        Field[] fs = new Field[decls.size()];  int i=0;
-        for( String fname : decls.keySet() ) {
-            int idx = idxs.get(fname);
-            boolean isFinal = finals.get(idx);
-            Type decl = decls.get(fname);
-            fs[i++] = Field.make(fname,decl,ALIAS++,isFinal);
-            if( isFinal ) throw Utils.TODO(); // Track write-once
-            if( _scope.in(idx)._type != decl.makeInit() ) throw Utils.TODO(); // Track non-zero init
-        }
-        // Done with scope
-        _scope.pop();
-
-        // Build and install the TypeStruct
-        TypeStruct ts = TypeStruct.make(typeName, fs);
-        TYPES.put(typeName, TypeMemPtr.make(ts));
-        START.addMemProj(ts, _scope); // Insert memory edges
-        require(";");
-        return null;
-    }
-
     /**
      * Parses a while statement
      *
@@ -452,10 +398,17 @@ public class Parser {
         int old = _lexer._position;
         String name = requireId();
         Node expr;
-        if( match(";") || peek(',') ) {
+        if( peek(';') || peek(',') ) {
             // Bare "name" is not allowed
             if( t==null ) throw errorSyntax("expression");
-            expr = new ConstantNode(t.makeInit()).peephole();
+            // Does this declaration need an initializer and not getting one?
+            Type init = xfinal || t instanceof TypeMemPtr tmp && !tmp._nil
+                // Must be initialized in the "new" constructor
+                ? Type.TOP
+                // Else takes the default
+                : t.makeInit();
+            expr = new ConstantNode(init).peephole();
+
         } else if( !match("=") ) {     // Something else
             _lexer._position = old;
             return null;
@@ -465,9 +418,13 @@ public class Parser {
         // Defining a new variable vs updating an old one
         if( !isDecl ) { // Assigning over an existing name
             // Lookup
-            if( _scope.lookup(name)==null )
+            Node def = _scope.lookup(name);
+            if( def==null )
                 throw error("Undefined name '" + name + "'");
-            if( _scope.lookupFinal(name) )
+            // TOP fields are for late-initialized fields; these have never
+            // been written to, and this must be the final write.  Other writes
+            // need to check the final bit.
+            if( def._type!=Type.TOP && _scope.lookupFinal(name) )
                 throw error("Cannot reassign final '"+name+"'");
             t = _scope.lookupDeclaredType(name);
         }
@@ -485,9 +442,8 @@ public class Parser {
         if( !e.isa(t) )
             throw error("Type " + e.str() + " is not of declared type " + t.str());
 
-
         if( isDecl ) {
-            if( _scope.define(name,t,expr,xfinal) == null )
+            if( !_scope.define(name,t,expr,xfinal) )
                 throw error("Redefining name '" + name + "'");
         } else
             _scope.update(name,expr);
@@ -530,6 +486,60 @@ public class Parser {
         return require(n,";");
     }
 
+
+    /**
+     * Parse a struct declaration, and return the following statement.
+     * Only allowed in top level scope.
+     * Structs cannot be redefined.
+     *
+     * @return The statement following the struct
+     */
+    private Node parseStruct() {
+        if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope");
+        String typeName = requireId();
+        Type t = TYPES.get(typeName);
+        if( t!=null && !(t instanceof TypeMemPtr tmp && tmp._obj._fields==null) )
+            throw errorSyntax("struct '" + typeName + "' cannot be redefined");
+
+        // A Block scope parse, and inspect the scope afterwards for fields.
+        _scope.push();
+        require("{");
+        while (!peek('}') && !_lexer.isEOF())
+            parseStatement();
+
+        // Grab the declarations and build fields and a Struct
+        HashMap<String,Type> decls = _scope._decls.lastElement();
+        HashMap<String,Integer> idxs = _scope._idxs.lastElement();
+        BitSet finals = _scope._finals;
+
+        StructNode s = new StructNode().keep();
+        Field[] fs = new Field[decls.size()];  int i=0;
+        for( String fname : decls.keySet() ) {
+            int idx = idxs.get(fname);
+            boolean isFinal = finals.get(idx);
+            Type decl = decls.get(fname);
+            fs[i++] = Field.make(fname,decl,ALIAS++,isFinal);
+            s.addDef(_scope.in(idx));
+        }
+        // Done with struct/block scope
+        require("}");
+        _scope.pop();
+
+        // Build and install the TypeStruct
+        TypeStruct ts = TypeStruct.make(typeName, fs);
+        TYPES.put(typeName, TypeMemPtr.make(ts));
+        require(";");
+        // Save initial constructor
+        s._ts = ts;
+        INITS.put(typeName,(StructNode)s.peephole());
+
+        // Insert memory edges
+        START.addMemProj(ts, _scope);
+
+        return null;
+    }
+
+
     // Parse and return a type or null.  Valid types always are followed by an
     // 'id' which the caller must parse.  This lets us distinguish forward ref
     // types (which ARE valid here) from local vars in an (optional) forward
@@ -756,12 +766,32 @@ public class Parser {
                 return newArray(tmp._obj,len);
             }
             if( t instanceof TypeMemPtr tmp ) {
-                TypeStruct obj = tmp._obj;
-                if( obj._fields==null )
-                    throw error("Unknown struct type '" + obj._name + "'");
-                if( obj.isAry() )
-                    throw Utils.TODO(); // Missing array length
-                return newStruct(obj,con(obj.offset(obj._fields.length)));
+                StructNode s = INITS.get(tmp._obj._name);
+                if( s==null ) throw error("Unknown struct type '" + tmp._obj._name + "'");
+                Field[] fs = s._ts._fields;
+                // if the object is fully initialized, we can skip a block here.
+                // Check for constructor block:
+                boolean hasConstructor = match("{");
+                Node init=s;  int idx=0;
+                if( hasConstructor ) {
+                    init = _scope;
+                    idx = _scope.nIns();
+                    // Push a scope, and pre-assign all struct fields.
+                    _scope.push();
+                    for( int i=0; i<fs.length; i++ )
+                        _scope.define(fs[i]._fname, fs[i]._type, s.in(i), fs[i]._final);
+                    // Parse the constructor body
+                    parseBlock();
+                    require("}");
+                }
+                // Check that all fields are initialized
+                for( int i=idx; i<init.nIns(); i++ )
+                    if( init.in(i)._type == Type.TOP )
+                        throw error("'"+tmp._obj._name+"' is not fully initialized, field '" + fs[i-idx]._fname + "' needs to be set in a constructor");
+                Node ptr = newStruct(tmp._obj, init, idx );
+                if( hasConstructor )
+                    _scope.pop();
+                return ptr;
             }
             throw error("Cannot allocate a "+t.str());
         }
@@ -773,17 +803,27 @@ public class Parser {
     }
 
     /**
-     * Return a NewNode with pre-zeroed memory
+     * Return a NewNode initialized memory.
+     * @param obj is the declared type, with GLB fields
+     * @param init is a collection of initialized fields
      */
-    private Node newStruct(TypeStruct obj, Node size) {
+    private Node newStruct( TypeStruct obj, Node init, int idx ) {
         Field[] fs = obj._fields;
-        Node[] ns = new Node[2+fs.length];
-        ns[0] = ctrl();
-        ns[1] = size;
-        for( int i = 0; i < fs.length; i++ )
-            ns[i+2] = memAlias(fs[i]._alias);
+        if( fs==null )
+            throw error("Unknown struct type '" + obj._name + "'");
+        int len = fs.length;
+        Node[] ns = new Node[2+len+len];
+        ns[0] = ctrl();         // Control in slot 0
+        // Total allocated length in bytes
+        ns[1] = con(obj.offset(len));
+        // Memory aliases for every field
+        for( int i = 0; i < len; i++ )
+            ns[2    +i] = memAlias(fs[i]._alias);
+        // Initial values for every field
+        for( int i = 0; i < len; i++ )
+            ns[2+len+i] = init.in(i+idx);
         Node nnn = new NewNode(TypeMemPtr.make(obj), ns).peephole();
-        for( int i = 0; i < fs.length; i++ )
+        for( int i = 0; i < len; i++ )
             memAlias(fs[i]._alias, new ProjNode(nnn,i+2,memName(fs[i]._alias)).peephole());
         return new ProjNode(nnn,1,obj._name).peephole();
     }
@@ -792,10 +832,11 @@ public class Parser {
         int base = ary.aryBase ();
         int scale= ary.aryScale();
         Node size = new AddNode(con(base),new ShlNode(len,con(scale)).peephole()).peephole();
-        Node ptr = newStruct(ary,size);
-        int alias = ary._fields[0]._alias; // Length alias
-        memAlias(alias,new StoreNode("#",alias,TypeInteger.BOT,memAlias(alias),ptr,con( ary.offset(0) ), len.unkeep(), true ).peephole());
-        return ptr;
+        //Node ptr = newStruct(ary,size);
+        //int alias = ary._fields[0]._alias; // Length alias
+        //memAlias(alias,new StoreNode("#",alias,TypeInteger.BOT,memAlias(alias),ptr,con( ary.offset(0) ), len.unkeep(), true ).peephole());
+        //return ptr;
+        throw Utils.TODO();
     }
 
     // We set up memory aliases by inserting special vars in the scope these
diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java
index 0bdf86f0..bc3f4335 100644
--- a/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java
+++ b/chapter16/src/main/java/com/seaofnodes/simple/node/LoadNode.java
@@ -57,8 +57,8 @@ public class LoadNode extends MemOpNode {
 
         // Simple Load-after-New on same address.
         if( mem() instanceof ProjNode p && p.in(0) instanceof NewNode nnn &&
-            ptr == nnn.proj(1) )  // Must check same object
-            return new ConstantNode(_declaredType.makeInit());
+            ptr == nnn.proj(1) ) // Must check same object
+            return nnn.findAlias(_alias); // Load from New init
 
         // Load-after-Store on same address, but bypassing provably unrelated
         // stores.  This is a more complex superset of the above two peeps.
@@ -82,7 +82,7 @@ public class LoadNode extends MemOpNode {
             case ProjNode mproj:
                 if( mproj.in(0) instanceof NewNode nnn1 ) {
                     if( ptr instanceof ProjNode pproj && pproj.in(0) == mproj.in(0) )
-                        return new ConstantNode(_declaredType.makeInit()); // Load from a New
+                        return nnn1.findAlias(_alias); // Load from New init
                     if( !(ptr instanceof ProjNode pproj && pproj.in(0) instanceof NewNode nnn2) )
                         break outer; // Cannot tell, ptr not related to New
                     mem = nnn1.in(_alias);// Bypass unrelated New
@@ -125,7 +125,6 @@ public class LoadNode extends MemOpNode {
             ptr2 instanceof ProjNode && ptr2.in(0) instanceof NewNode;
     }
 
-
     // Profitable if we find a matching Store on this Phi arm.
     private boolean profit(PhiNode phi, int idx) {
         Node px = phi.in(idx);
diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java
index f06564cd..c65d7ca5 100644
--- a/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java
+++ b/chapter16/src/main/java/com/seaofnodes/simple/node/NewNode.java
@@ -1,6 +1,7 @@
 package com.seaofnodes.simple.node;
 
 import com.seaofnodes.simple.type.*;
+import com.seaofnodes.simple.Utils;
 import java.util.BitSet;
 
 /**
@@ -11,19 +12,23 @@ import java.util.BitSet;
  */
 public class NewNode extends Node implements MultiNode {
 
-    public TypeMemPtr _ptr;
+    public final TypeMemPtr _ptr;
+    public final int _len;
 
     public NewNode(TypeMemPtr ptr, Node... nodes) {
         super(nodes);
+        _ptr = ptr;
+        _len = ptr._obj._fields.length;
         // Control in slot 0
         assert nodes[0]._type==Type.CONTROL || nodes[0]._type == Type.XCONTROL;
         // Malloc-length in slot 1
         assert nodes[1]._type instanceof TypeInteger;
-        // Memory slices in remaining slots
-        for( int i=2; i<nodes.length; i++ )
-            assert nodes[i]._type instanceof TypeMem;
-
-        _ptr = ptr;
+        for( int i=0; i<_len; i++ ) {
+            // Memory slices for all fields.
+            assert nodes[2+     i]._type instanceof TypeMem;
+            // Value  slices for all fields.
+            assert nodes[2+_len+i]._type instanceof Type;
+        }
     }
 
     @Override public String label() {
@@ -36,14 +41,26 @@ public class NewNode extends Node implements MultiNode {
         return sb.append(_ptr._obj.str());
     }
 
+    // Find matching alias input
+    Node findAlias(int alias) {
+        for( int i=0; i<_len; i++ )
+            if( ((TypeMem)in(2+i)._type)._alias == alias )
+                return in(2+i+_len);
+        throw Utils.TODO();     // Must find
+    }
+
+
     @Override
     public TypeTuple compute() {
         Field[] fs = _ptr._obj._fields;
         Type[] ts = new Type[fs.length+2];
         ts[0] = Type.CONTROL;
         ts[1] = _ptr;
-        for( int i=0; i<fs.length; i++ )
-            ts[i+2] = TypeMem.make(fs[i]._alias,fs[i]._type.makeInit()).meet( in(i+2)._type );
+        for( int i=0; i<fs.length; i++ ) {
+            TypeMem mem = (TypeMem)in(i+2)._type;
+            Type tfld = in(2+_len+i)._type.meet(mem._t);
+            ts[i+2] = TypeMem.make(fs[i]._alias,tfld);
+        }
         return TypeTuple.make(ts);
     }
 
diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
index 0e7a5e9b..5842f5b5 100644
--- a/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
+++ b/chapter16/src/main/java/com/seaofnodes/simple/node/ScopeNode.java
@@ -55,7 +55,8 @@ public class ScopeNode extends Node {
                 sb.append("Lazy_");
                 n = loop.in(j);
             }
-            n._print0(sb, visited).append(" ");
+            if( n==null ) sb.append("___");
+            else n._print0(sb, visited).append(" ");
         }
         sb.setLength(sb.length()-1);
         return sb.append("]");
@@ -104,13 +105,14 @@ public class ScopeNode extends Node {
     /**
      * Create a new variable name in the current scope
      */
-    public Node define( String name, Type declaredType, Node n, boolean xfinal ) {
+    public boolean define( String name, Type declaredType, Node n, boolean xfinal ) {
         HashMap<String,Integer> syms = _idxs.lastElement();
         _decls.lastElement().put(name,declaredType);
         if( syms.put(name,nIns()) != null )
-            return null;        // Double define
+            return false;                 // Double define
         if( xfinal ) _finals.set(nIns()); // track finals
-        return addDef(n);
+        addDef(n);
+        return true;
     }
 
     /**
diff --git a/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java b/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java
new file mode 100644
index 00000000..69e9f444
--- /dev/null
+++ b/chapter16/src/main/java/com/seaofnodes/simple/node/StructNode.java
@@ -0,0 +1,53 @@
+package com.seaofnodes.simple.node;
+
+import com.seaofnodes.simple.type.*;
+import java.util.BitSet;
+
+/**
+ * Build a compound object
+ */
+public class StructNode extends Node {
+
+    public TypeStruct _ts;
+
+    @Override public String label() { return _ts==null ? "STRUCT?" : _ts.str(); }
+
+    @Override
+    StringBuilder _print1(StringBuilder sb, BitSet visited) {
+        if( _ts==null ) return sb.append("STRUCT?");
+        sb.append(_ts._name).append(" {");
+        for( int i=0; i<nIns(); i++ ) {
+            sb.append(_ts._fields[i]._fname).append(":");
+            (in(i)==null ? Type.BOTTOM : in(i)._type).print(sb);
+            sb.append("; ");
+        }
+        sb.setLength(sb.length()-2);
+        return sb.append("}");
+    }
+
+    // All fields fully initialized, or a sample not-initialized field
+    public String uninitField() {
+        for( int i=0; i<nIns(); i++ )
+            if( in(i)==null )
+                return _ts._fields[i]._fname;
+        return null;
+    }
+
+    // Sample field not initialized
+    @Override
+    public TypeStruct compute() {
+        Field[] fs = new Field[_ts._fields.length];
+        for( int i=0; i<fs.length; i++ )
+            fs[i] = _ts._fields[i].makeFrom(in(i)==null ? Type.TOP : in(i)._type);
+        return TypeStruct.make(_ts._name,fs);
+    }
+
+    @Override
+    public Node idealize() { return null; }
+
+    @Override
+    boolean eq(Node n) { return _ts == ((StructNode)n)._ts; }
+
+    @Override
+    int hash() { return _ts.hashCode(); }
+}
diff --git a/chapter16/src/main/java/com/seaofnodes/simple/type/Field.java b/chapter16/src/main/java/com/seaofnodes/simple/type/Field.java
index eb49c3af..e2c0aa59 100644
--- a/chapter16/src/main/java/com/seaofnodes/simple/type/Field.java
+++ b/chapter16/src/main/java/com/seaofnodes/simple/type/Field.java
@@ -30,6 +30,9 @@ public class Field extends Type {
     public static Field make( String fname, Type type, int alias, boolean xfinal ) {
         return new Field(fname,type,alias,xfinal).intern();
     }
+    public Field makeFrom( Type type ) {
+        return new Field(_fname,type,_alias,_final).intern();
+    }
 
     public static final Field TEST = make("test",TypeInteger.ZERO,-2,false);
     public static void gather(ArrayList<Type> ts) { ts.add(TEST); }