Update evaluator toString for arrays

3 files changed, 148 insertions, 48 deletions

diff --git a/chapter15/src/test/java/com/seaofnodes/simple/BrainFuckTest.java b/chapter15/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
index a7a4966d..f7c66bda 100644
--- a/chapter15/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
+++ b/chapter15/src/test/java/com/seaofnodes/simple/BrainFuckTest.java
@@ -27,12 +27,6 @@ public class BrainFuckTest {
 int pc = 0;
 int d = 0;
 u8[] data = new u8[100];
-int i=0;
-while(i < data#) {
-    data[i] = 0;
-    i = i + 1;
-}
-
 u8[] output = new u8[0];
 
 while (pc < program#) {
@@ -48,7 +42,7 @@ while (pc < program#) {
     } else if (command == 46) {
         u8[] old = output;
         output = new u8[output# + 1];
-        i = 0;
+        int i = 0;
         while (i < old#) {
             output[i] = old[i];
             i = i + 1;
@@ -79,19 +73,9 @@ while (pc < program#) {
     }
     pc = pc + 1;
 }
-int result = 0;
-i = 0;
-while (i < 8) {
-    result = (result << 8) | output[i];
-    i = i + 1;
-}
-return result;
+return output;
                 """);
         StopNode stop = parser.parse(false).iterate(false);
-        long expected = 0;
-        for (byte b : "Hello Wo".getBytes(StandardCharsets.UTF_8)) {
-            expected = (expected << 8) | b;
-        }
-        assertEquals(expected, Evaluator.evaluate(stop, 0, 10000));
+        assertEquals("Hello World!\n", Evaluator.evaluate(stop, 0, 10000).toString());
     }
 }
diff --git a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java
index 266d8a47..dff39ba3 100644
--- a/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java
+++ b/chapter15/src/test/java/com/seaofnodes/simple/Chapter15Test.java
@@ -24,6 +24,22 @@ return 3.14;
     }
 
     @Test
+    public void testCyclic() {
+        Parser parser = new Parser(
+""" 
+struct C {
+    C? l;
+}
+C c = new C;
+c.l = c;
+return c;
+""");
+        StopNode stop = parser.parse(false).iterate(true);
+        assertEquals("return C;", stop.toString());
+        assertEquals("Obj<C>@1{l=obj@1}", Evaluator.evaluate(stop,  0).toString());
+    }
+
+    @Test
     public void testSafetyCheck() {
         Parser parser = new Parser(
 """
@@ -39,7 +55,7 @@ return output;
 """);
         StopNode stop = parser.parse(false).iterate(true);
         assertEquals("return u8[];", stop.toString());
-        assertEquals("Obj<u8[]> {\n  #=1\n  []=1\n}", Evaluator.evaluate(stop,  0).toString());
+        assertEquals("\u0001", Evaluator.evaluate(stop,  0).toString());
     }
 
     @Test
@@ -91,7 +107,7 @@ 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());
+        assertEquals("Obj<*A?[]>{#=2,[]=[null,null]}", Evaluator.evaluate(stop, 0).toString());
     }
 
     @Test
@@ -162,7 +178,7 @@ 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());
+        assertEquals("Obj<Tree>{_kids=Obj<*Tree?[]>{#=2,[]=[Obj<Tree>{_kids=null},null]}}", Evaluator.evaluate(stop,  0).toString());
     }
 
 
diff --git a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
index 26860858..a723095c 100644
--- a/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
+++ b/chapter15/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java
@@ -6,23 +6,115 @@ import com.seaofnodes.simple.type.*;
 
 import java.lang.invoke.MethodHandle;
 import java.lang.invoke.MethodHandles;
-import java.util.ArrayList;
-import java.util.BitSet;
-import java.util.Objects;
+import java.util.*;
 
 public class Evaluator {
 
     private static final Object MEMORY = new Object();
 
     public record Obj(TypeStruct struct, Object[] fields) {
+        private void init(IdentityHashMap<Obj, Integer> objs) {
+            var oid = objs.get(this);
+            if (oid != null) {
+                if (oid != 0) objs.put(this, 0);
+                return;
+            }
+            objs.put(this, -1);
+            for (var obj : fields) {
+                if (obj instanceof Obj o) o.init(objs);
+            }
+        }
+        private static int p(StringBuilder sb, IdentityHashMap<Obj, Integer> objs, int id, String indentation, String step, String sep, Object obj) {
+            if (obj instanceof Obj o) return o.p(sb, objs, id, indentation, step, sep);
+            sb.append(obj);
+            return id;
+        }
+        private int p(StringBuilder sb, IdentityHashMap<Obj, Integer> objs, int id, String indentation, String step, String sep) {
+            var cid = objs.get(this);
+            assert cid != null;
+            if (cid > 0) {
+                sb.append("obj@").append(cid);
+                return id;
+            }
+            if (struct._name.equals("u8[]")) {
+                sb.append('"');
+                for (int i=struct._fields.length-1; i<fields.length; i++) {
+                    var v = fields[i];
+                    if (v == null) v = 0;
+                    assert v instanceof Number;
+                    var n = ((Number)v).byteValue() & 0xFF;
+                    if (n >= 0x20 && n < 0x80) {
+                        if (n == 0x22 || n == 0x5C) sb.append("\\");
+                        sb.append((char)n);
+                    } else {
+                        sb.append("\\x").append("0123456789abcdef".charAt(n >> 4)).append("0123456789abcdef".charAt(n & 0xF));
+                    }
+                }
+                sb.append('"');
+                return id;
+            }
+            sb.append("Obj<").append(struct._name).append(">");
+            if (cid == 0) {
+                cid = id++;
+                objs.put(this, cid);
+                sb.append("@").append(cid);
+            }
+            sb.append("{");
+            if (struct._fields.length == 0) {
+                assert !struct.isAry();
+                sb.append("}");
+                return id;
+            }
+            String nextIndent = indentation + step;
+            int e = struct._fields.length - 1;
+            for(int i=0; i<e; i++) {
+                sb.append(nextIndent).append(struct._fields[i]._fname).append("=");
+                id = p(sb, objs, id, nextIndent, step, sep, fields[i]);
+                sb.append(sep);
+            }
+            sb.append(nextIndent).append(struct._fields[e]._fname).append("=");
+            if (struct.isAry()) {
+                sb.append("[");
+                if (fields.length > e) {
+                    String innerIndent = nextIndent + step;
+                    sb.append(innerIndent);
+                    id = p(sb, objs, id, nextIndent, step, sep, fields[e]);
+                    for (int i = e+1; i < fields.length; i++) {
+                        sb.append(sep).append(innerIndent);
+                        id = p(sb, objs, id, nextIndent, step, sep, fields[i]);
+                    }
+                    sb.append(nextIndent);
+                }
+                sb.append("]");
+            } else {
+                id = p(sb, objs, id, nextIndent, step, sep, fields[e]);
+            }
+            sb.append(indentation).append("}");
+            return id;
+        }
+        private StringBuilder p(StringBuilder sb, String indentation, String step, String sep) {
+            var objs = new IdentityHashMap<Obj, Integer>();
+            init(objs);
+            p(sb, objs, 1, indentation, step, sep);
+            return sb;
+        }
         @Override
         public String toString() {
-            var sb = new StringBuilder();
-            sb.append("Obj<").append(struct._name).append("> {");
-            for(int i=0; i<struct._fields.length; i++) {
-                sb.append("\n  ").append(struct._fields[i]._fname).append("=").append(fields[i]);
+            if (struct._name.equals("u8[]")) {
+                var sb = new StringBuilder();
+                for (int i=struct._fields.length-1; i<fields.length; i++) {
+                    var v = fields[i];
+                    if (v == null) v = 0;
+                    assert v instanceof Number;
+                    var n = ((Number)v).byteValue() & 0xFF;
+                    sb.append((char)n);
+                }
+                return sb.toString();
             }
-            return sb.append("\n}").toString();
+            return p(new StringBuilder(), "", "", ",").toString();
+        }
+        public String pretty() {
+            return p(new StringBuilder(), "\n", "  ", "").toString();
         }
     }
 
@@ -82,19 +174,32 @@ public class Evaluator {
         return in2 == 0 ? 0 : vald(div.in(1)) / in2;
     }
 
+    private static long offToIdx(long off, TypeStruct t) {
+        off -= t.aryBase();
+        int scale = t.aryScale();
+        long mask = (1L << scale)-1;
+        assert (off & mask) == 0;
+        return off>>scale;
+    }
+
     private Object alloc(NewNode alloc) {
-        TypeTuple tt = alloc.compute();
-        TypeStruct type = ((TypeMemPtr)tt._types[1])._obj;
+        TypeStruct type = alloc._ptr._obj;
         Object[] body=null;
         if( type.isAry() ) {
             long sz = (Long)val(alloc.in(1));
-            int base  = alloc._ptr._obj.aryBase();
-            int scale = alloc._ptr._obj.aryScale();
-            long n = (sz-base)>>scale;
+            long n = offToIdx(sz, type);
             if( n < 0 )
                 throw new NegativeArraySizeException(""+n);
             body = new Object[(int)n+1]; // Array body
             body[0] = n;                 // Array length
+            var c = type._fields[type._fields.length-1]._type;
+            if (c instanceof TypeInteger) {
+                for (int i=0; i<n; i++) body[i+type._fields.length-1] = 0L;
+            } else if (c instanceof TypeFloat) {
+                for (int i = 0; i < n; i++) body[i+type._fields.length-1] = 0D;
+            } else {
+                assert c instanceof TypeMemPtr;
+            }
         } else {
             body = new Object[type._fields.length];
         }
@@ -107,16 +212,14 @@ public class Evaluator {
 
     private Object load(LoadNode load) {
         var from = (Obj)val(load.ptr());
-        var off = val(load.off());
+        var off = vall(load.off());
         var idx = getFieldIndex(from.struct, load, (Long)off);
-        if( idx==1 && from.struct.isAry() ) {
+        if( idx==from.struct._fields.length-1 && from.struct.isAry() ) {
             long len = (Long)from.fields[0];
-            int base  = from.struct.aryBase();
-            int scale = from.struct.aryScale();
-            long i = ((Long)off - base)>>scale;
+            long i = offToIdx(off, from.struct);
             if( i < 0 || i >= len )
                 throw new ArrayIndexOutOfBoundsException("Array index out of bounds " + i + " < " + len);
-            return from.fields[(int)i+1];
+            return from.fields[(int)i+from.struct._fields.length-1];
 
         } else
             return from.fields[idx];
@@ -124,18 +227,15 @@ public class Evaluator {
 
     private Object store(StoreNode store) {
         var to = (Obj)val(store.ptr());
-        var off = val(store.off());
+        var off = vall(store.off());
         var val = val(store.val());
         var idx = getFieldIndex(to.struct, store, (Long)off);
-        if( idx==1 && to.struct.isAry() ) {
+        if( idx==to.struct._fields.length-1 && to.struct.isAry() ) {
             long len = (Long)to.fields[0];
-            int base  = to.struct.aryBase();
-            int scale = to.struct.aryScale();
-            long i = ((Long)off - base)>>scale;
+            long i = offToIdx(off, to.struct);
             if( i < 0 || i >= len )
                 throw new RuntimeException("Array index out of bounds " + off + " <= " + len);
-            to.fields[(int)i+1] = val;
-
+            to.fields[(int)i+to.struct._fields.length-1] = val;
         } else
             to.fields[idx] = val;
         return null;