summaryrefslogtreecommitdiff
path: root/chapter29/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
diff options
context:
space:
mode:
Diffstat (limited to 'chapter29/src/test/java/com/seaofnodes/simple/Chapter17bTest.java')
-rw-r--r--chapter29/src/test/java/com/seaofnodes/simple/Chapter17bTest.java623
1 files changed, 623 insertions, 0 deletions
diff --git a/chapter29/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/chapter29/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
new file mode 100644
index 00000000..1e99bcd9
--- /dev/null
+++ b/chapter29/src/test/java/com/seaofnodes/simple/Chapter17bTest.java
@@ -0,0 +1,623 @@
+package com.seaofnodes.simple;
+
+import com.seaofnodes.simple.parser.Parser;
+import com.seaofnodes.simple.codegen.CodeGen;
+import org.junit.Ignore;
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
+
+public class Chapter17bTest {
+
+ @Test public void testSinkLoopStores() {
+ var code = new CodeGen("""
+ struct S { int x; };
+ !S !a = new S;
+ a.x = 10;
+ int i = 0;
+ while (i < arg) { a.x = i + 1; i++; }
+ return a;
+ """).driver(CodeGen.Phase.LocalSched);
+ int[] stores = {0};
+ code._stop.walk(n -> {
+ // Constructor zero Stores remain in separate private memory.
+ if( n instanceof com.seaofnodes.simple.node.StoreNode st && st._name.equals("x") &&
+ st.val() instanceof com.seaofnodes.simple.node.PhiNode ) {
+ assertEquals(0,st.cfg0().loopDepth()); // One final Store outside the loop.
+ stores[0]++;
+ }
+ return null;
+ });
+ assertEquals(1,stores[0]);
+ for( int arg : new int[]{-1,0,1,4} ) {
+ long expected = arg<=0 ? 10 : arg;
+ assertEquals("Test.S{x="+expected+"}",Eval2.eval(code,arg));
+ }
+ }
+
+
+ @Ignore
+ @Test
+ public void testJig() {
+ CodeGen code = new CodeGen(
+"""
+return 1;
+""");
+ code.driver(CodeGen.Phase.TypeCheck);
+ assertEquals("return 1;", code.print());
+ assertEquals("1", Eval2.eval(code, 0));
+ }
+
+
+ // ---------------------------------------------------------------
+ @Test
+ public void testInc0() {
+ CodeGen code = new CodeGen("""
+return arg++;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return arg;", code.print());
+ assertEquals("0", Eval2.eval(code, 0));
+ }
+
+ @Test
+ public void testInc1() {
+ CodeGen code = new CodeGen("""
+return arg+++arg++;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return ((arg<<1)+1);", code.print());
+ assertEquals("1", Eval2.eval(code, 0));
+ }
+
+ @Test
+ public void testInc2() {
+ CodeGen code = new CodeGen("""
+// -(arg--)-(arg--)
+return -arg---arg--;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return (-((arg<<1)+-1));", code.print());
+ assertEquals("1", Eval2.eval(code, 0));
+ }
+
+ @Test
+ public void testInc3() {
+ CodeGen code = new CodeGen("""
+int[] !xs = new int[arg];
+xs[0]++;
+xs[1]++;
+return xs[0];
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 1;", code.print());
+ assertEquals("1", Eval2.eval(code, 2));
+ }
+
+ @Test
+ public void testInc4() {
+ CodeGen code = new CodeGen("""
+u8[] !xs = new u8[1];
+xs[0]--;
+return xs[0];
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 255;", code.print());
+ assertEquals("255", Eval2.eval(code, 2));
+ }
+
+ @Test
+ public void testInc5() {
+ CodeGen code = new CodeGen("""
+struct _S { u16 x; };
+!_S !s = new _S;
+s.x--;
+return s.x;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 65535;", code.print());
+ assertEquals("65535", Eval2.eval(code, 2));
+ }
+
+ @Test
+ public void testInc6() {
+ CodeGen code = new CodeGen("return --arg;");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return (arg+-1);", code.print());
+ assertEquals("-1", Eval2.eval(code, 0));
+ }
+
+ @Test
+ public void testInc7() {
+ CodeGen code = new CodeGen("u8 x=0; return --x;");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 255;", code.print());
+ assertEquals("255", Eval2.eval(code, 0));
+ }
+
+ @Test
+ public void testInc8() {
+ CodeGen code = new CodeGen("int x; x+=2; return x+=3;");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 5;", code.print());
+ assertEquals("5", Eval2.eval(code, 0));
+ }
+
+ @Test
+ public void testInc9() {
+ CodeGen code = new CodeGen("flt x = 1.5; x++; return x;");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 2.5f;", code.print());
+ assertEquals("2.5", Eval2.eval(code, 0));
+ }
+
+ @Test public void testInt10() {
+ CodeGen code = new CodeGen("flt x = 1.5; x++; int i = x; return i;");
+ code.driver(CodeGen.Phase.TypeCheck);
+ assertEquals("2",Eval2.eval(code,0));
+ }
+
+
+ // ---------------------------------------------------------------
+ @Test public void testVar0() {
+ CodeGen code = new CodeGen("var d; return d;");
+ try { code.driver(CodeGen.Phase.FinalizeIR); fail(); }
+ catch( Exception e ) { assertEquals("Syntax error, expected `=expression` but found `;`",e.getMessage()); }
+ }
+
+ @Test public void testVar1() {
+ CodeGen code = new CodeGen("val d; return d;");
+ try { code.driver(CodeGen.Phase.FinalizeIR); fail(); }
+ catch( Exception e ) { assertEquals("Syntax error, expected `=expression` but found `;`",e.getMessage()); }
+ }
+
+ @Test public void testVar2() {
+ CodeGen code = new CodeGen("int x; x=3; x++; return x; // Ok, no initializer so x is mutable ");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 4;", code.print());
+ assertEquals("4", Eval2.eval(code, 0));
+ }
+
+ @Test public void testVar3() {
+ CodeGen code = new CodeGen("int x=3; x++; return x; // Ok, primitive so x is mutable despite initializer ");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 4;", code.print());
+ assertEquals("4", Eval2.eval(code, 0));
+ }
+
+ @Test public void testVar4() {
+ CodeGen code = new CodeGen("struct _S{int x;}; !_S? !s; s=new _S; s.x++; return s.x; // Ok, no initializer so x is mutable ");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 1;", code.print());
+ assertEquals("1", Eval2.eval(code, 0));
+ }
+
+ @Test public void testVar5() {
+ CodeGen code = new CodeGen("struct _S{int x; new _S={ int xx -> x=xx; };}; !_S? !s; s=new _S(3); s.x++; return s.x; // Ok, no initializer so x is mutable ");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 4;", code.print());
+ assertEquals("4", Eval2.eval(code, 0));
+ }
+
+ @Test public void testVar6() {
+ CodeGen code = new CodeGen("struct S{int x;}; ~S s = new S; s.x++; return s.x; // Error initializer so x is immutable ");
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); }
+ }
+
+ @Test public void testVar7() {
+ CodeGen code = new CodeGen("struct S{int x; new S={ int xx -> x=xx; };}; ~S s = new S(3); s.x++; return s.x; // Error initializer so x is immutable ");
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); }
+ }
+
+ @Test public void testVar8() {
+ CodeGen code = new CodeGen("struct _S{int x;}; !_S !s=new _S; s.x++; return s.x; // Ok, has '!' so s.x is mutable ");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 1;", code.print());
+ assertEquals("1", Eval2.eval(code, 0));
+ }
+
+ @Test public void testVar9() {
+ CodeGen code = new CodeGen("struct _S{int x;}; var s=new _S; s.x++; return s.x; // Ok, has var so s.x is mutable ");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 1;", code.print());
+ assertEquals("1", Eval2.eval(code, 0));
+ }
+
+ @Test public void testVar10() {
+ CodeGen code = new CodeGen("struct S{int x;}; ~S s=new S; s.x++; return s.x; // Error, has val so x is immutable ");
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); }
+ }
+
+ @Test public void testVar11() {
+ CodeGen code = new CodeGen("""
+struct Bar { int x; };
+!Bar !bar = new Bar;
+bar.x = 3; // Ok, bar is mutable
+
+struct Foo { !Bar? !bar; int y; new Foo = { !Bar? b -> bar = b; }; };
+!Foo !foo = new Foo(bar);
+foo.bar = bar; // Ok foo is mutable
+foo.bar.x++; // Ok foo and foo.bar and foo.bar.x are all mutable
+
+~Foo xfoo = foo; // Throw away mutability
+xfoo.bar.x++; // Error, cannot mutate through xfoo
+return xfoo.bar.x;
+ """);
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); }
+ }
+
+ @Test public void testVar12() {
+ CodeGen code = new CodeGen("""
+struct _Bar { int x; };
+!_Bar !bar = new _Bar;
+bar.x = 3; // Ok, bar is mutable
+
+struct _Foo { !_Bar? !bar; int y; };
+!_Foo !foo = new _Foo;
+foo.bar = bar; // Ok bar is mutable
+foo.bar.x++; // Ok foo and foo.bar and foo.bar.x are all mutable
+
+~_Foo xfoo = foo; // Throw away mutability
+int x4 = xfoo.bar.x; // Ok to read through xfoo, gets 4
+foo.bar.x++; // Bumps to 5
+int x5 = xfoo.bar.x; // Ok to read through xfoo, gets 5
+return x4*10+x5;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 45;", code.print());
+ assertEquals("45", Eval2.eval(code, 0));
+ }
+
+ @Test
+ public void testVar13() {
+ CodeGen code = new CodeGen("""
+int i,i++;
+""");
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Redefining name 'i'",e.getMessage()); }
+ }
+
+
+ @Test
+ public void testVar14() {
+ CodeGen code = new CodeGen("""
+struct B {};
+struct A { !B !b; new A = { ->
+ return b; // read before init
+ b = new B;
+}; };
+A x = new A;
+""");
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Field 'b' might not be initialized",e.getMessage()); }
+ }
+
+ @Test
+ public void testVar15() {
+ for( String fields : new String[] {
+ "!B !b; new A = { -> if (arg) b = new B; };",
+ "!B !b; new A = { -> if (arg) return 0; b = new B; };",
+ "!B !b; new A = { !B !b -> b = new B; };", // Argument shadows field
+ "new A = { -> }; !B !b;", // Field declared later
+ } ) {
+ CodeGen code = new CodeGen("struct B {}; struct A { "+fields+" }; return 0;");
+ try { code.parse(); fail(fields); }
+ catch( Parser.ParseException e ) { assertEquals("'Test.A' is not fully initialized, field 'b' is only partially set in the constructor",e.getMessage()); }
+ }
+ }
+
+ @Test
+ public void testDefaultConstructorFields() {
+ for( String field : new String[] { "!B !b;", "!B !b;" } ) {
+ CodeGen code = new CodeGen("struct B {}; struct A { "+field+" }; return new A;");
+ try { code.parse(); fail(field); }
+ catch( Parser.ParseException e ) { assertEquals("'Test.A' is not fully initialized, field 'b' needs to be set in a constructor",e.getMessage()); }
+ }
+ for( String fields : new String[] {
+ "B b = new B;",
+ "!B !b; b = new B;",
+ "new A = { -> }; B b = new B;",
+ "!B !b; new A = { -> if (arg) { b = new B; return 0; } b = new B; };",
+ } ) {
+ CodeGen code = new CodeGen("struct B {}; struct A { "+fields+" }; return new A.b != null;");
+ code.driver(CodeGen.Phase.TypeCheck);
+ assertEquals("1",Eval2.eval(code,0));
+ assertEquals("1",Eval2.eval(code,1));
+ }
+ // No returning path means no object can escape uninitialized.
+ new CodeGen("struct B {}; struct A { !B !b; new A = { -> while (true) {} }; }; return 0;").parse();
+ }
+
+ @Test
+ public void testVar16() {
+ CodeGen code = new CodeGen(
+"""
+struct S{ new S = { -> x = 2; }; };
+val x = 1;
+~S s = new S;
+return x;
+"""
+);
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Undefined name 'x'",e.getMessage()); }
+ }
+
+ @Test
+ public void testVar17() {
+ CodeGen code = new CodeGen(
+"""
+struct Person {
+ bool focused;
+};
+val focus = { !Person p ->
+ p.focused = true;
+};
+!Person !me; // !Person !me = new Person;
+focus(me);
+return me;
+"""
+);
+ try { code.parse(); fail(); }
+ catch( Exception e ) { assertEquals("Syntax error, expected `=expression` but found `;`",e.getMessage()); }
+ }
+
+ // ---------------------------------------------------------------
+ @Test
+ public void testTrinary0() {
+ CodeGen code = new CodeGen("""
+return arg ? 1 : 2;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Region,1,2);", code.print());
+ assertEquals("2", Eval2.eval(code, 0));
+ assertEquals("1", Eval2.eval(code, 1));
+ }
+
+ @Test
+ public void testTrinary1() {
+ CodeGen code = new CodeGen("""
+return arg ? 0 : arg;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return 0;", code.print());
+ assertEquals("0", Eval2.eval(code, 0));
+ }
+
+ @Test
+ public void testShortCircuitGuard() {
+ CodeGen code = new CodeGen("""
+struct S { int !x; };
+val get = { !S s -> s.x; };
+!S? !s = arg ? new S;
+if( !s || !arg ) return 0;
+return get(s);
+""");
+ code.driver(CodeGen.Phase.TypeCheck);
+ }
+
+ @Test
+ public void testTrinary2() {
+ CodeGen code = new CodeGen("""
+struct _Bar { int x; };
+var b = arg ? new _Bar : null;
+return b ? b.x++ + b.x++ : -1;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Region,((.x<<1)+1),-1);", code.print());
+ assertEquals("-1", Eval2.eval(code, 0));
+
+ assertEquals("1", Eval2.eval(code, 1));
+ }
+
+ @Test
+ public void testTrinary3() {
+ CodeGen code = new CodeGen("""
+struct _Bar { int x; };
+var b = arg ? new _Bar;
+return b ? b.x++ + b.x++ : -1;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Region,((.x<<1)+1),-1);", code.print());
+ assertEquals("-1", Eval2.eval(code, 0));
+ assertEquals("1", Eval2.eval(code, 1));
+ }
+
+ @Test
+ public void testTrinary4() {
+ // This test case will benefit from an unzipping transformation
+ CodeGen code = new CodeGen("""
+struct _Bar { !_Bar? !next; int x; new _Bar = { !_Bar? !n, int xx -> next=n; x=xx; }; };
+var b = arg ? new _Bar((arg==2) ? new _Bar(null,2), 1);
+return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0"
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Region,.x,0,.x);", code.print());
+ assertEquals("0", Eval2.eval(code, 0));
+ assertEquals("1", Eval2.eval(code, 1));
+ assertEquals("2", Eval2.eval(code, 2));
+ }
+
+ @Test
+ public void testTrinary5() {
+ CodeGen code = new CodeGen("""
+flt f=arg?1:1.2;
+return f; // missing widening
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Region,1.0f,1.2);", code.print());
+ assertEquals("1.2", Eval2.eval(code, 0));
+ }
+
+
+ @Test
+ public void testTrinary6() {
+ CodeGen code = new CodeGen("""
+struct S{};
+return arg ? 7 : new S;
+""");
+ try { code.driver(CodeGen.Phase.TypeCheck); fail(); }
+ catch( Exception e ) { assertEquals("Cannot return generic scalar",e.getMessage()); }
+ }
+
+ // ---------------------------------------------------------------
+ @Test
+ public void testFor0() {
+ CodeGen code = new CodeGen("""
+int sum=0;
+for( int i=0; i<arg; i++ )
+ sum += i;
+return sum;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code.print());
+ assertEquals("3", Eval2.eval(code, 3));
+ assertEquals("45", Eval2.eval(code, 10));
+ }
+ @Test
+ public void testFor1() {
+ CodeGen code = new CodeGen("""
+int sum=0, i=0;
+for( ; i<arg; i++ )
+ sum += i;
+return sum;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code.print());
+ assertEquals("3", Eval2.eval(code, 3));
+ assertEquals("45", Eval2.eval(code, 10));
+ }
+ @Test
+ public void testFor2() {
+ CodeGen code = new CodeGen("""
+int sum=0;
+for( int i=0; ; i++ ) {
+ if( i>=arg ) break;
+ sum += i;
+}
+return sum;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code.print());
+ assertEquals("3", Eval2.eval(code, 3));
+ assertEquals("45", Eval2.eval(code, 10));
+ }
+ @Test
+ public void testFor3() {
+ CodeGen code = new CodeGen("""
+int sum=0;
+for( int i=0; i<arg; )
+ sum += i++;
+return sum;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Loop,0,(Phi_sum+Phi(Loop,0,(Phi_i+1))));", code.print());
+ assertEquals("3", Eval2.eval(code, 3));
+ assertEquals("45", Eval2.eval(code, 10));
+ }
+ @Test
+ public void testFor4() {
+ CodeGen code = new CodeGen("""
+int sum=0;
+for( int i=0; i<arg; i++ )
+ sum += i;
+return i;
+""");
+ try { code.driver(CodeGen.Phase.FinalizeIR); fail(); }
+ catch( Exception e ) { assertEquals("Undefined name 'i'",e.getMessage()); }
+ }
+ @Test
+ public void testFor5() {
+ CodeGen code = new CodeGen("""
+for(;;arg++;) {}
+""");
+ try { code.driver(CodeGen.Phase.FinalizeIR); fail(); }
+ catch( Exception e ) { assertEquals("Syntax error, expected `Unexpected code after expression` but found `;`",e.getMessage()); }
+ }
+
+
+
+ // ---------------------------------------------------------------
+ @Test
+ public void testForward0() {
+ CodeGen code = new CodeGen("""
+struct _A {
+ !B? !f1;
+ !B? !f2;
+};
+return new _A;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Test._A;", code.print());
+ assertEquals("Test._A{f1=null,f2=null}", Eval2.eval(code,0));
+ }
+
+ @Test
+ public void testForward1() {
+ CodeGen code = new CodeGen("""
+struct _A {
+ !B?[]? !nil_array_of_b;
+ !B?[] !array_of_b;
+ new _A = { !B?[] bs -> array_of_b = bs; };
+};
+return new _A(new !B?[0]).array_of_b;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return []*B?;", code.print());
+ assertEquals("*B {}?[]", Eval2.eval(code,0));
+ }
+
+ // ---------------------------------------------------------------
+ @Test
+ public void testLinkedList2() {
+ CodeGen code = new CodeGen("""
+struct _LLI { !_LLI? !next; int i; new _LLI = { !_LLI? !n, int ii -> next=n; i=ii; }; };
+!_LLI? !head = null;
+while( arg-- )
+ head = new _LLI(head,arg);
+int sum=0;
+var ptr = head; // A read-only ptr, to be assigned from read-only next fields
+for( ; ptr; ptr = ptr.next )
+ sum += ptr.i;
+return sum;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR);
+ assertEquals("return Phi(Loop,0,(Phi_sum+.i));", code.print());
+ assertEquals("45", Eval2.eval(code, 10));
+ }
+
+ @Test
+ public void sieveOfEratosthenes() {
+ CodeGen code = new CodeGen(
+"""
+var ary = new bool[arg], primes = new int[arg];
+var nprimes=0, p=0;
+// Find primes while p^2 < arg
+for( p=2; p*p < arg; p++ ) {
+ // skip marked non-primes
+ while( ary[p] ) p++;
+ // p is now a prime
+ primes[nprimes++] = p;
+ // Mark out the rest non-primes
+ for( int i = p + p; i < ary#; i += p )
+ ary[i] = true;
+}
+// Now just collect the remaining primes, no more marking
+for( ; p < arg; p++ )
+ if( !ary[p] )
+ primes[nprimes++] = p;
+// Copy/shrink the result array
+var !rez = new int[nprimes];
+for( int j=0; j<nprimes; j++ )
+ rez[j] = primes[j];
+return rez;
+""");
+ code.driver(CodeGen.Phase.FinalizeIR).driver(CodeGen.Phase.Schedule);
+ assertEquals("return []i64;", code.print());
+ assertEquals("i64[ 2,3,5,7,11,13,17,19]",Eval2.eval(code, 20));
+ }
+
+}
generated by cgit v1.2.3 (git 2.25.1) at 2026-11-02 13:18:46 +0000