Fix parsing forward ref arrays

5 files changed, 85 insertions, 43 deletions

diff --git a/chapter15/README.md b/chapter15/README.md
index 50a0493b..354b6c66 100644
--- a/chapter15/README.md
+++ b/chapter15/README.md
@@ -14,12 +14,12 @@ Like Java, arrays are always safety checked, and failing a runtime check
 will panic the Evaluator.
 
 - Indexing out of bounds:
-- - `ary[-1]`
-- - `ary[ary#]`
+- `ary[-1]`
+- `ary[ary#]`
 - Creating an array with a bad length:
-- - `new int[-1];    // Negative length`
-- - `new int[1<<63]; // Too large`
-- - `new int[3.14];  // Not an integer`
+- `new int[-1];    // Negative length`
+- `new int[1<<63]; // Too large`
+- `new int[3.14];  // Not an integer`
  
 
 ## Parser
@@ -33,8 +33,10 @@ Arrays are always created with zero/null bodies, so implicitly always allow
 `null` values.
 
 We make a new array with much the same syntax as making a new object: `new
-int[99][99]`.  The length is required and is any integer expression, so
-e.g. `int[arg]` is an integer array of length `arg`.
+int[99]`.  The length is required and is any integer expression, so
+e.g. `int[arg]` is an integer array of length `arg`.  Multi-dimensional arrays
+only make the outer dimension; the elements themselves are all null and typed
+as the next lower dimension array.
 
 Arrays implicitly have two fields: the length and the body.  The length is a
 read-only field set when the array is allocated; it is referenced with the
diff --git a/chapter15/src/main/java/com/seaofnodes/simple/Parser.java b/chapter15/src/main/java/com/seaofnodes/simple/Parser.java
index b503bf15..e0077102 100644
--- a/chapter15/src/main/java/com/seaofnodes/simple/Parser.java
+++ b/chapter15/src/main/java/com/seaofnodes/simple/Parser.java
@@ -92,7 +92,9 @@ public class Parser {
     ScopeNode _continueScope;
     ScopeNode _breakScope;
 
-    // Mapping from a type name to a Type.
+    // Mapping from a type name to a Type.  The string name matches
+    // `type.str()` call.  No TypeMemPtrs are in here, because Simple does not
+    // have C-style '*ptr' references.
     public static HashMap<String, Type> TYPES = new HashMap<>();
 
     public Parser(String source, TypeInteger arg) {
@@ -488,17 +490,10 @@ public class Parser {
         if( tname==null ) return null;
         // Convert the type name to a type.
         Type t0 = TYPES.get(tname);
-        Type t1 = t0==null ? TypeStruct.BOT : t0; // Null: assume a forward ref type
+        Type t1 = t0 == null ? TypeStruct.make(tname) : t0; // Null: assume a forward ref type
         // Nest arrays as needed
-        while( match("[]") ) {
-            Type t2 = TYPES.get("[]"+tname);
-            if( t2==null ) {
-                TYPES.put("[]"+tname,t1 = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t1,ALIAS++));
-                START.addMemProj((TypeStruct)t1, _scope); // Insert memory edges
-            } else {
-                t1 = t2;
-            }
-        }
+        while( match("[]") )
+            t1 = typeAry(t1);
         // Handle trailing '?' for nullable
         Type t2 = t1 instanceof TypeStruct obj ? TypeMemPtr.make(obj,match("?")) : t1;
 
@@ -514,8 +509,23 @@ public class Parser {
             return null;        // Not a type
         }
         // Yes a forward ref, so declare it
-        TYPES.put(tname, t0 = TypeStruct.make(tname));
-        return ((TypeMemPtr)t2).makeFrom((TypeStruct)t0);
+        TYPES.put(tname,t1);
+        return t2;
+    }
+
+    // Make an array type of t
+    private TypeStruct typeAry( Type t ) {
+        assert !(t instanceof TypeMemPtr); // Arrays of references, not inlined structs
+        String tname = t.str()+"[]";
+        Type ta = TYPES.get(tname);
+        if( ta != null ) return (TypeStruct)ta;
+        // Need make an array type.  If the base type is a struct, wrap it.
+        if( t instanceof TypeStruct obj )
+            t = TypeMemPtr.make(obj,true);
+        TypeStruct ts = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t,ALIAS++);
+        TYPES.put(tname,ts);
+        START.addMemProj(ts, _scope); // Insert memory alias edges
+        return ts;
     }
 
 
@@ -677,14 +687,21 @@ public class Parser {
             String typeName = _lexer.matchId();
             if( typeName==null ) throw error("Expected a type");
             Type t = TYPES.get(typeName);
-            if( match("[") )
-                return require(newArray(t),"]");
-            if( t instanceof TypeStruct obj ) {
-                if( obj._fields==null )
-                    throw error("Unknown struct type '" + typeName + "'");
+            if( t instanceof TypeStruct obj && obj._fields==null )
+                throw error("Unknown struct type '" + typeName + "'");
+            if( t!=null && match("[") ) {
+                Node len = parseExpression().keep();
+                if( !(len._type instanceof TypeInteger) )
+                    throw error("Cannot allocate an array with length "+len._type);
+                require("]");
+                TypeStruct ary = typeAry(t);
+                while( match("[]") )
+                    ary = typeAry(ary);
+                return newArray(ary,len);
+            } else if( t instanceof TypeStruct obj ) {
                 return newStruct(obj,con(obj.offset(obj._fields.length)));
             }
-            throw error("Cannot allocate a "+t);
+            throw error("Cannot allocate a "+typeName);
         }
         String name = _lexer.matchId();
         if( name == null) throw errorSyntax("an identifier or expression");
@@ -709,15 +726,7 @@ public class Parser {
         return new ProjNode(nnn,1,obj._name).peephole();
     }
 
-    private Node newArray(Type t) {
-        Node len = parseExpression().keep();
-        if( !(len._type instanceof TypeInteger) )
-            throw error("Cannot allocate an array with length "+len._type);
-        TypeStruct ary = (TypeStruct)TYPES.get("[]"+t.str());
-        if( ary == null ) {
-            TYPES.put("[]"+t.str(), ary = TypeStruct.makeAry(TypeInteger.BOT,ALIAS++,t,ALIAS++));
-            START.addMemProj(ary, _scope); // Insert memory edges
-        }
+    private Node newArray(TypeStruct ary, Node len) {
         int base = ary.aryBase ();
         int scale= ary.aryScale();
         Node size = new AddNode(con(base),new ShlNode(len,con(scale)).peephole()).peephole();
diff --git a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
index 9e38e025..b3a8f867 100644
--- a/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
+++ b/chapter15/src/main/java/com/seaofnodes/simple/type/TypeStruct.java
@@ -40,8 +40,9 @@ public class TypeStruct extends Type {
 
     // Array
     public static TypeStruct makeAry(TypeInteger len, int lenAlias, Type body, int bodyAlias) {
-        String name = "[]" + body.str();
-        return make("[]" + body.str(),
+        Type t = body;
+        if( t instanceof TypeMemPtr tmp ) { assert tmp._nil; t = tmp._obj; }
+        return make(t.str() + "[]",
                     Field.make("#" , lenAlias,len ),
                     Field.make("[]",bodyAlias,body));
     }
diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java
index 6ba6eed4..62e865aa 100644
--- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java
+++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java
@@ -61,6 +61,36 @@ return a[0];
     }
 
     @Test
+    public void testBasic4() {
+        Parser parser = new Parser(
+"""
+struct A { int i; }
+A[] a = new A[2];
+return a;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return A[];", stop.toString());
+        assertEquals("Obj<A[]> {\n  #=2\n  []=null\n}", Evaluator.evaluate(stop, 0).toString());
+    }
+
+    @Test
+    public void testTree() {
+        Parser parser = new Parser(
+"""
+// Can we define a forward-reference array?
+struct Tree { Tree[] _kids; }
+Tree root = new Tree;
+root._kids = new Tree[2];
+root._kids[0] = new Tree;
+return root;
+""");
+        StopNode stop = parser.parse(false).iterate(false);
+        assertEquals("return Tree;", stop.toString());
+        assertEquals("Obj<Tree> {\n  _kids=Obj<Tree[]> {\n  #=2\n  []=Obj<Tree> {\n  _kids=null\n}\n}\n}", Evaluator.evaluate(stop,  0).toString());
+    }
+
+
+    @Test
     public void testRollingSum() {
         Parser parser = new Parser(
 """
@@ -123,9 +153,9 @@ while( j < nprimes ) {
 return rez;
 """);
         StopNode stop = parser.parse(false).iterate(true);
-        assertEquals("return []int;", stop.toString());
+        assertEquals("return int[];", stop.toString());
         Evaluator.Obj obj = (Evaluator.Obj)Evaluator.evaluate(stop, 20);
-        assertEquals("[]int {\n  # :int;\n  [] :int;\n}",obj.struct().toString());
+        assertEquals("int[] {\n  # :int;\n  [] :int;\n}",obj.struct().toString());
         long nprimes = (Long)obj.fields()[0];
         long[] primes = new long[]{2,3,5,7,11,13,17,19};
         for( int i=0; i<nprimes; i++ )
@@ -140,7 +170,7 @@ return rez;
 return new flt;
 """);
         try { parser.parse(false).iterate(false); fail(); }
-        catch( Exception e ) { assertEquals("Cannot allocate a FltBot",e.getMessage()); }
+        catch( Exception e ) { assertEquals("Cannot allocate a flt",e.getMessage()); }
     }
 
     @Test
@@ -150,7 +180,7 @@ return new flt;
 int is = new int[2];
 """);
         try { parser.parse(false).iterate(false); fail(); }
-        catch( Exception e ) { assertEquals("Type *[]int is not of declared type int",e.getMessage()); }
+        catch( Exception e ) { assertEquals("Type *int[] is not of declared type int",e.getMessage()); }
     }
 
     @Test
diff --git a/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
index 324dd42d..7cd854bf 100644
--- a/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
+++ b/chapter15/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -109,8 +109,8 @@ public class ScriptGenerator {
 
     static {
         new Parser("", TypeInteger.BOT);
-        for(var e : Parser.TYPES.entrySet() ) {
-            if (e.getValue() instanceof TypeInteger) {
+        for( var e : Parser.TYPES.entrySet() ) {
+            if( e.getValue() instanceof TypeInteger ) {
                 INTTYPES.add(new TypeInt(e.getKey()));
             }
         }