Chapter 13: References

Co-authored-by: Thalia Archibald <thalia@archibald.dev>
Co-authored-by: Dibyendu Majumdar <mobile@majumdar.org.uk>
Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com>
Co-authored-by: tannal <tannal2409@gmail.com>
Co-authored-by: hadha <helsgithub15@gmail.com>
Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com>
Co-authored-by: RobertObkircher <robert.obkircher@gmail.com>
Co-authored-by: Robert Obkircher <robert.obkircher@gmail.com>

10 files changed, 292 insertions, 60 deletions

diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
index 8d15493f..9d154413 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java
@@ -37,7 +37,7 @@ if (arg == 1) {
 }
 return c;""", TypeInteger.BOT);
         StopNode ret = parser.parse().iterate();
-        assertEquals("return Phi(Region18,4,3);", ret.toString());
+        assertEquals("return Phi(Region19,4,3);", ret.toString());
     }
 
     @Test
@@ -116,7 +116,7 @@ if( arg==0 )
 return arg+a+b;
 """, TypeInteger.BOT);
         StopNode stop = parser.parse();
-        assertEquals("return ((arg+Phi(Region15,1,0))+Phi(Region30,2,0));", stop.toString());
+        assertEquals("return ((arg+Phi(Region17,1,0))+Phi(Region33,2,0));", stop.toString());
     }
 
     @Test
@@ -130,7 +130,7 @@ if( arg==1 )
 }
 return a;""");
         StopNode ret = parser.parse().iterate();
-        assertEquals("return (arg==Phi(Region18,3,2));", ret.toString());
+        assertEquals("return (arg==Phi(Region19,3,2));", ret.toString());
     }
 
     @Test
diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
index 7b11bc35..633b25e0 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java
@@ -30,7 +30,7 @@ if (arg)
 return (arg < a) < 3;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return ((arg<Phi(Region14,2,1))<3);", stop.toString());
+        assertEquals("return ((arg<Phi(Region16,2,1))<3);", stop.toString());
     }
 
     @Test
@@ -200,7 +200,7 @@ if( arg ) {
 return a+b;
 """);
         StopNode ret = parser.parse().iterate();
-        assertEquals("return Phi(Region26,4,1);", ret.toString());
+        assertEquals("return Phi(Region28,4,1);", ret.toString());
     }
 
 
@@ -251,7 +251,7 @@ if( arg ) {
 return a+b+c;
 """);
         StopNode ret = parser.parse().iterate();
-        assertEquals("return (Phi(Region38,Phi(Region25,2,3),0)+Phi(Region,3,1));", ret.toString());
+        assertEquals("return (Phi(Region40,Phi(Region25,2,3),0)+Phi(Region,3,1));", ret.toString());
     }
 
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
index 6aa74125..7760ae09 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter08Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter08Test.java
@@ -23,7 +23,7 @@ while(arg < 10) {
 return arg;
                 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region36,Phi(Region26,Phi(Loop8,arg,(Phi_arg+1)),Add),Add);", stop.toString());
+        assertEquals("return Phi(Region37,Phi(Region26,Phi(Loop8,arg,(Phi_arg+1)),Add),Add);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof RegionNode);
         Assert.assertEquals(5L, Evaluator.evaluate(stop, 1));
         Assert.assertEquals(10L, Evaluator.evaluate(stop, 6));
@@ -46,7 +46,7 @@ while(arg < 10) {
 return a;
                 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop9,1,Phi(Region41,Phi_a,(Phi_a+1)));", stop.toString());
+        assertEquals("return Phi(Loop9,1,Phi(Region43,Phi_a,(Phi_a+1)));", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof CProjNode);
     }
 
@@ -65,7 +65,7 @@ while(arg < 10) {
 return arg;
                 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region34,Phi(Loop8,arg,(Phi_arg+1)),Add);", stop.toString());
+        assertEquals("return Phi(Region35,Phi(Loop8,arg,(Phi_arg+1)),Add);", stop.toString());
         assertTrue(stop.ret().ctrl() instanceof RegionNode);
     }
 
diff --git a/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
index 4a9521b9..c9f695c9 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter10Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter10Test.java
@@ -1,12 +1,7 @@
 package com.seaofnodes.simple;
 
-import com.seaofnodes.simple.node.Node;
 import com.seaofnodes.simple.node.StopNode;
-import com.seaofnodes.simple.type.*;
 import org.junit.Test;
-
-import java.util.Arrays;
-
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
@@ -33,7 +28,7 @@ if( (arg/13)==0 ) {
 int r = g+h;
 return p-r;
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return 0;", stop.toString());
     }
 
@@ -108,7 +103,7 @@ while (arg) {
 return bar.a;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop11,0,(Phi_a+2));", stop.toString());
+        assertEquals("return Phi(Loop12,0,(Phi_a+2));", stop.toString());
     }
 
     @Test
@@ -160,7 +155,7 @@ if( bar ) bar.a = 1;
 return bar;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region16,null,new Bar);", stop.toString());
+        assertEquals("return Phi(Region31,(*void)Phi(Region19,null,new Bar),null);", stop.toString());
     }
 
     @Test
@@ -176,7 +171,7 @@ else bar.a = 1;
 return rez;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region33,4,3);", stop.toString());
+        assertEquals("return Phi(Region37,4,3);", stop.toString());
     }
 
     @Test
@@ -230,7 +225,7 @@ while( i.x < i.len ) {
 return sum;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop15,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString());
+        assertEquals("return Phi(Loop17,0,(Phi(Loop,0,(Phi_x+1))+Phi_sum));", stop.toString());
     }
 
 
@@ -251,7 +246,7 @@ while(arg) {
 return ret;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop11,new s0,Phi(Region31,new s0,Phi_ret));", stop.toString());
+        assertEquals("return Phi(Loop12,new s0,Phi(Region34,new s0,Phi_ret));", stop.toString());
     }
 
     @Test
@@ -264,11 +259,12 @@ while(arg) {
     v0.v0 = arg;
     arg = arg-1;
     if (arg==5) ret=v0;
+
 }
 return ret;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop13,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString());
+        assertEquals("return Phi(Loop15,new s0,Phi(Region35,new s0,Phi_ret));", stop.toString());
     }
 
 
@@ -285,7 +281,7 @@ while(arg < 10) {
 return ret;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop11,new s0,Phi(Region30,new s0,Phi_ret));", stop.toString());
+        assertEquals("return Phi(Loop12,new s0,Phi(Region33,new s0,Phi_ret));", stop.toString());
     }
 
     @Test
diff --git a/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
index a8b09226..da0bc087 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter11Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter11Test.java
@@ -291,7 +291,7 @@ else {
         }
 }
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("Stop[ return 9; return 0; return 0; return 0; return 0; ]", stop.toString());
     }
 
@@ -324,7 +324,7 @@ while( prime <= arg ) {
 return primeCount;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("Stop[ return 0; return Phi(Loop19,1,Phi(Region81,Phi_primeCount,Phi(Region76,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString());
+        assertEquals("Stop[ return 0; return Phi(Loop20,1,Phi(Region87,Phi_primeCount,Phi(Region81,(Phi_primeCount+1),Phi_primeCount))); ]", stop.toString());
         assertEquals(0L, Evaluator.evaluate(stop,  1)); // No primes 1 or below
         assertEquals(1L, Evaluator.evaluate(stop,  2)); // 2
         assertEquals(2L, Evaluator.evaluate(stop,  3)); // 2, 3
@@ -366,7 +366,7 @@ if (arg) {
 return i;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region31,.f,0);", stop.toString());
+        assertEquals("return Phi(Region34,.f,0);", stop.toString());
     }
 
     @Test
@@ -451,7 +451,7 @@ while (arg) {
 }
 return i;
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return .f;", stop.toString());
     }
 
@@ -471,8 +471,8 @@ while(arg) {
 }
 return arg;
 """);
-        StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Loop13,arg,Phi(Region35,.f,0));", stop.toString());
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return Phi(Loop15,arg,Phi(Region37,.f,0));", stop.toString());
     }
 
     @Test
@@ -489,7 +489,7 @@ if (arg) {
 }
 return v;
 """);
-        StopNode stop = parser.parse().iterate();
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return new S;", stop.toString());
     }
 
@@ -523,7 +523,7 @@ else if (arg == 1) s.f = 1;
 return s.f;
 """);
         StopNode stop = parser.parse().iterate();
-        assertEquals("return Phi(Region35,1,Phi(Region33,1,0));", stop.toString());
+        assertEquals("return Phi(Region37,1,Phi(Region35,1,0));", stop.toString());
         assertEquals(1L, Evaluator.evaluate(stop,  0));
         assertEquals(1L, Evaluator.evaluate(stop,  1));
         assertEquals(0L, Evaluator.evaluate(stop,  2));
diff --git a/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
index af8fdfe9..62dce12b 100644
--- a/src/test/java/com/seaofnodes/simple/Chapter12Test.java
+++ b/src/test/java/com/seaofnodes/simple/Chapter12Test.java
@@ -2,9 +2,8 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.evaluator.Evaluator;
 import com.seaofnodes.simple.node.StopNode;
+import org.junit.Ignore;
 import org.junit.Test;
-
-
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.fail;
 
@@ -15,7 +14,7 @@ public class Chapter12Test {
 """
 return 3.14;
 """);
-        StopNode stop = parser.parse(false).iterate(false);
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return 3.14;", stop.toString());
         assertEquals(3.14, Evaluator.evaluate(stop,  0));
     }
@@ -26,7 +25,7 @@ return 3.14;
 """
 return 3.14;
 """);
-        StopNode stop = parser.parse(false).iterate(false);
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return 3.14;", stop.toString());
         assertEquals(3.14, Evaluator.evaluate(stop,  0));
     }
@@ -43,7 +42,7 @@ while( 1 ) {
 }
 return guess;
 """);
-        StopNode stop = parser.parse(false).iterate(false);
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return Phi(Loop9,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)/2.0));", stop.toString());
         assertEquals(3.0, Evaluator.evaluate(stop,  9));
         assertEquals(1.414213562373095, Evaluator.evaluate(stop,  2));
@@ -56,7 +55,7 @@ return guess;
 flt x = arg;
 return x+1==x;
 """);
-        StopNode stop = parser.parse(false).iterate(false);
+        StopNode stop = parser.parse().iterate(false);
         assertEquals("return ((flt)arg==(ToFloat+1.0));", stop.toString());
         assertEquals(0L, Evaluator.evaluate(stop, 1));
     }
diff --git a/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/src/test/java/com/seaofnodes/simple/Chapter13Test.java
new file mode 100644
index 00000000..59f08963
--- /dev/null
+++ b/src/test/java/com/seaofnodes/simple/Chapter13Test.java
@@ -0,0 +1,197 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.evaluator.Evaluator;
+import com.seaofnodes.simple.node.StopNode;
+import org.junit.Ignore;
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class Chapter13Test {
+    @Test
+    public void testJig() {
+        Parser parser = new Parser(
+"""
+return 3.14;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return 3.14;", stop.toString());
+        assertEquals(3.14, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testLinkedList0() {
+        Parser parser = new Parser(
+"""
+struct LLI { LLI? next; int i; }
+LLI? head = null;
+while( arg ) {
+    LLI x = new LLI;
+    x.next = head;
+    x.i = arg;
+    head = x;
+    arg = arg-1;
+}
+return head.next.i;
+""");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); }
+    }
+
+    @Test
+    public void testLinkedList1() {
+        Parser parser = new Parser(
+"""
+struct LLI { LLI? next; int i; }
+LLI? head = null;
+while( arg ) {
+    LLI x = new LLI;
+    x.next = head;
+    x.i = arg;
+    head = x;
+    arg = arg-1;
+}
+if( !head ) return 0;
+LLI? next = head.next;
+if( next==null ) return 1;
+return next.i;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("Stop[ return 0; return 1; return .i; ]", stop.toString());
+        assertEquals(2L, Evaluator.evaluate(stop,  3));
+    }
+
+    @Test
+    public void testCoRecur() {
+        Parser parser = new Parser(
+"""
+struct int0 { int i; flt0? f; }
+struct flt0 { flt f; int0? i; }
+int0 i0 = new int0;
+i0.i = 17;
+flt0 f0 = new flt0;
+f0.f = 3.14;
+i0.f = f0;
+f0.i = i0;
+return f0.i.f.i.i;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return 17;", stop.toString());
+    }
+
+    @Test
+    public void testNullRef0() {
+        Parser parser = new Parser(
+"""
+struct N { N next; int i; }
+N n = new N;
+return n.next;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return null;", stop.toString());
+    }
+
+    @Test
+    public void testNullRef1() {
+        Parser parser = new Parser(
+"""
+struct N { N next; int i; }
+N n = new N;
+n.next = new N;
+return n.next;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return new N;", stop.toString());
+    }
+
+    @Test
+    public void testNullRef2() {
+        Parser parser = new Parser(
+"""
+struct N { N next; int i; }
+N n = new N;
+n.next = null;
+return n.next;
+""");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Cannot store null into field *N next",e.getMessage()); }
+    }
+
+    @Test
+    public void testNullRef3() {
+        Parser parser = new Parser(
+"""
+struct N { N next; int i; }
+N n = new N;
+n.i = 3.14;
+return n.i;
+""");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Cannot store 3.14 into field IntBot i",e.getMessage()); }
+    }
+
+    @Test
+    public void testNullRef4() {
+        Parser parser = new Parser("-null-5/null-5");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); }
+    }
+
+    @Test public void testNullRef5() {
+        Parser parser = new Parser("return null+42;");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Cannot 'Add' null",e.getMessage()); }
+    }
+
+    @Test
+    public void testEmpty() {
+        Parser parser = new Parser(
+"""
+struct S{};
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return 0;", stop.toString());
+        assertEquals(0L, Evaluator.evaluate(stop,  0));
+    }
+
+    @Test
+    public void testForwardRef0() {
+        Parser parser = new Parser(
+"""
+struct S1 { S2 s; }
+return new S2;
+""");
+        try { parser.parse().iterate(); fail(); }
+        catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); }
+    }
+
+    @Test
+    public void testForwardRef1() {
+        Parser parser = new Parser(
+"""
+struct S1 { S2? s; }
+struct S2 { int x; }
+return new S1.s=new S2;
+""");
+        StopNode stop = parser.parse().iterate(false);
+        assertEquals("return new S1;", stop.toString());
+    }
+
+    @Test
+    public void testcheckNull() {
+        Parser parser = new Parser(
+"""
+struct I {int i;}
+struct P {I pi;}
+P p1 = new P;
+P p2 = new P;
+p2.pi = new I;
+p2.pi.i = 2;
+if (arg) p1 = new P;
+return p1.pi.i + 1;
+""");
+        try { parser.parse(false).iterate();  fail(); }
+        catch( Exception e ) {  assertEquals("Might be null accessing 'i'",e.getMessage());  }
+    }
+
+}
diff --git a/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/src/test/java/com/seaofnodes/simple/SchedulerTest.java
index 5def2782..853999b1 100644
--- a/src/test/java/com/seaofnodes/simple/SchedulerTest.java
+++ b/src/test/java/com/seaofnodes/simple/SchedulerTest.java
@@ -31,7 +31,7 @@ if (arg) v.f=1;
 return i;
 """);
         StopNode._disablePeephole = true;
-        StopNode stop = parser.parse(true);//.iterate();
+        StopNode stop = parser.parse();//.iterate();
         var eval = new Evaluator(stop);
         assertEquals(2L, eval.evaluate(1, 10));
     }
diff --git a/src/test/java/com/seaofnodes/simple/TypeTest.java b/src/test/java/com/seaofnodes/simple/TypeTest.java
index f9c580cc..9e8a1418 100644
--- a/src/test/java/com/seaofnodes/simple/TypeTest.java
+++ b/src/test/java/com/seaofnodes/simple/TypeTest.java
@@ -2,8 +2,8 @@ package com.seaofnodes.simple;
 
 import com.seaofnodes.simple.type.*;
 import org.junit.Assert;
+import org.junit.Ignore;
 import org.junit.Test;
-
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertSame;
 
@@ -36,9 +36,9 @@ public class TypeTest {
         Assert.assertEquals(TypeMem   .BOT, m2.meet(m3));
         Assert.assertEquals(TypeMem   .BOT, m3.meet(m4));
 
-        Assert.assertEquals(TypeMem.BOT, m1.glb());
-        Assert.assertEquals(m1, m1.dual());
-        Assert.assertEquals(TypeMem.TOP, m1.glb().dual());
+        Assert.assertEquals(m1, m1.glb());
+        Assert.assertEquals(TypeMem.make(1), m1.dual());
+        Assert.assertEquals(m1.dual(), m1.glb().dual());
 
         TypeMemPtr ptr1 = TypeMemPtr.make(s1);
         Assert.assertEquals(s1, ptr1._obj);
@@ -128,10 +128,13 @@ public class TypeTest {
     private static void check_symmetric( Type t0, Type t1 ) {
         if( t1==t0 ) return;
         Type mt = t0.meet(t1);
-        Type ta = mt.dual().meet(t1.dual());
-        Type tb = mt.dual().meet(t0.dual());
-        assertSame(ta,t1.dual());
-        assertSame(tb,t0.dual());
+        Type dm = mt.dual();
+        Type d0 = t0.dual();
+        Type d1 = t1.dual();
+        Type ta = dm.meet(d1);
+        Type tb = dm.meet(d0);
+        assertSame(ta,d1);
+        assertSame(tb,d0);
     }
 
     private static void assoc( Type t0, Type t1, Type t2 ) {
@@ -142,4 +145,13 @@ public class TypeTest {
         assertSame(t01_2,t0_12);
     }
 
+    // Test cyclic types and meets
+    @Test
+    public void testCyclic0() {
+        Type d0 = TypeStruct.S1.dual();
+        Type d1 = d0.dual();
+        assertSame(TypeStruct.S1,d1);
+    }
+
+
 }
diff --git a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
index b8437b50..94929241 100644
--- a/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
+++ b/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java
@@ -3,9 +3,7 @@ package com.seaofnodes.simple.fuzzer;
 import com.seaofnodes.simple.Parser;
 import com.seaofnodes.simple.node.ScopeNode;
 
-import java.util.ArrayList;
-import java.util.HashSet;
-import java.util.Random;
+import java.util.*;
 import java.util.function.Predicate;
 
 /**
@@ -70,11 +68,10 @@ public class ScriptGenerator {
 
     private static class TypeStruct extends Type {
         record Field (String name, Type type, TypeStruct struct) {}
-        final Field[] fields;
+        Field[] fields;
         final TypeNullable nullable = new TypeNullable(this);
-        TypeStruct(String name, Field[] fields) {
+        TypeStruct(String name) {
             super(name);
-            this.fields = fields;
         }
         boolean isa(Type other) { return this == other || other == nullable; }
     }
@@ -159,6 +156,10 @@ public class ScriptGenerator {
      */
     private final ArrayList<TypeStruct> structs = new ArrayList<>();
     /**
+     * All forward declared structs
+     */
+    private final ArrayList<TypeStruct> forwardStructs = new ArrayList<>();
+    /**
      * Allow to declare structs.
      */
     private boolean allowStructs = true;
@@ -301,6 +302,7 @@ public class ScriptGenerator {
         for (var s:structs) {
             if (s.name.equals(name)) return s;
         }
+        for (var s:forwardStructs) if (s.name.equals(name)) return s;
         return null;
     }
 
@@ -333,12 +335,18 @@ public class ScriptGenerator {
         return v;
     }
 
+    private <T> T randFromList(List<T> list) {
+        return list.get(random.nextInt(list.size()));
+    }
+
     /**
      * Get a random structure name
      * @return A random structure name
      */
     private String getStructName() {
-        if (!structs.isEmpty() && generateInvalid()) return structs.get(random.nextInt(structs.size())).name;
+        if (!structs.isEmpty() && generateInvalid()) return randFromList(structs).name;
+        if (!forwardStructs.isEmpty() && generateInvalid()) return randFromList(forwardStructs).name;
+
         // Generate a new random struct name
         StringBuilder sb = getRandomName();
         var v = sb.toString();
@@ -357,16 +365,27 @@ public class ScriptGenerator {
      * Get a random type
      * @return A random type
      */
-    private Type getType() {
+    private Type getType(boolean allowForward) {
         int t = random.nextInt(10);
         if( t<5 || structs.isEmpty() ) return TYPE_INT;
         if( t<7 ) return TYPE_FLT;
-        var idx = random.nextInt(structs.size());
-        TypeStruct struct = structs.get(idx);
+        if (allowForward && random.nextInt(10)==0) {
+            int i=random.nextInt(forwardStructs.size()+1);
+            if (i>0) return forwardStructs.get(i-1).nullable;
+            var name = getStructName();
+            var struct = new TypeStruct(name);
+            forwardStructs.add(struct);
+            return struct.nullable;
+        }
+        TypeStruct struct = randFromList(structs);
         if (random.nextBoolean()) return struct.nullable;
         return struct;
     }
 
+    private Type getType() {
+        return getType(false);
+    }
+
     /**
      * Generates a program and writes it into the string builder supplied in the constructor.
      * @return If the program is allowed to be invalid returns if something potentially invalid was generated.
@@ -426,19 +445,28 @@ public class ScriptGenerator {
      * @return 0
      */
     public int genStruct() {
-        var name = getStructName();
+        int idx = random.nextInt(forwardStructs.size()+10);
+        TypeStruct struct;
+        if (idx < 10) {
+            var name = getStructName();
+            struct = new TypeStruct(name);
+            forwardStructs.add(struct);
+        } else {
+            struct = forwardStructs.get(idx-10);
+        }
         var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)];
-        var struct = new TypeStruct(name, fields);
-        sb.append("struct ").append(name).append(" {\n");
+        sb.append("struct ").append(struct.name).append(" {\n");
         indentation += INDENTATION;
         for (int i=0; i<fields.length; i++) {
             var fieldName = getRandomName();
-            var type = getType();
+            var type = getType(true);
             printIndentation().append(type.name).append(" ").append(fieldName).append(";\n");
             fields[i] = new TypeStruct.Field(fieldName.toString(), type, struct);
         }
         indentation -= INDENTATION;
         printIndentation().append("}");
+        struct.fields = fields;
+        forwardStructs.remove(struct);
         structs.add(struct);
         return 0;
     }
@@ -804,7 +832,7 @@ public class ScriptGenerator {
         } else if (type == TYPE_FLT) {
             sb.append(random.nextFloat());
         } else if (type instanceof TypeNullable n) {
-            if (random.nextBoolean()) {
+            if ((n.base instanceof TypeStruct s && s.fields == null) || random.nextBoolean()) {
                 sb.append("null");
             } else {
                 sb.append("new ").append(generateInvalid() ? getRandomName() : n.base.name);