From 22df891893d30e9906d0b14fc3ae5d8e67d500b2 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 3 Oct 2026 14:03:48 -0700 Subject: Chapter renumber, and split ch 17 Renumber chapters 10a, 10b, 11, 12, 13, 14 -> 10, 11, 13, 12, [11,14]. Split ch 17 into a 17a and 17b; shuffle around im/mutable syntax to be consistent, and present it more slowly. THe new immutable syntax is pushed through all later chapters --- .../java/com/seaofnodes/simple/Chapter10Test.java | 56 +-- .../java/com/seaofnodes/simple/Chapter10bTest.java | 60 --- .../java/com/seaofnodes/simple/Chapter11Test.java | 310 ++---------- .../java/com/seaofnodes/simple/Chapter12Test.java | 281 +++++++++-- .../java/com/seaofnodes/simple/Chapter13Test.java | 363 +++++++------- .../com/seaofnodes/simple/Chapter14FloatTest.java | 82 +++ .../java/com/seaofnodes/simple/Chapter14Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter15Test.java | 32 +- .../java/com/seaofnodes/simple/Chapter16Test.java | 127 +---- .../java/com/seaofnodes/simple/Chapter17Test.java | 556 --------------------- .../java/com/seaofnodes/simple/Chapter17aTest.java | 106 ++++ .../java/com/seaofnodes/simple/Chapter17bTest.java | 556 +++++++++++++++++++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 30 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 14 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 30 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 26 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 22 +- .../java/com/seaofnodes/simple/Chapter23Test.java | 24 +- .../java/com/seaofnodes/simple/Chapter24Test.java | 22 +- .../seaofnodes/simple/CompoundAssignmentTest.java | 2 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 12 +- .../java/com/seaofnodes/simple/MergeSortTest.java | 6 +- .../java/com/seaofnodes/simple/MutabilityTest.java | 73 +++ .../java/com/seaofnodes/simple/SchedulerTest.java | 6 +- .../test/java/com/seaofnodes/simple/TypeTest.java | 10 +- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 14 +- .../java/com/seaofnodes/simple/progs/person21.smp | 2 +- .../com/seaofnodes/simple/progs/stringHash.smp | 6 +- .../com/seaofnodes/simple/progs/stringHash21.smp | 6 +- 29 files changed, 1454 insertions(+), 1382 deletions(-) delete mode 100644 chapter24/src/test/java/com/seaofnodes/simple/Chapter10bTest.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java delete mode 100644 chapter24/src/test/java/com/seaofnodes/simple/Chapter17Test.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/Chapter17aTest.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/Chapter17bTest.java create mode 100644 chapter24/src/test/java/com/seaofnodes/simple/MutabilityTest.java (limited to 'chapter24/src/test') diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java index 121e8a22..0f4ca169 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -25,7 +25,7 @@ public class Chapter10Test { // Issue #246: null-check guards start in Chapter 10; arrays arrive in Chapter 15. private static final String NULLABLE_POINT_SOURCE = """ struct Point { int x; }; - Point?[] !points = new Point?[2]; + !Point?[] !points = new !Point?[2]; points[arg] = new Point { x = 42; }; Point? p = points[1]; """; @@ -117,7 +117,7 @@ struct Foo { int x; }; Foo? foo = null; -Bar !bar = new Bar; +!Bar !bar = new Bar; bar.a = 1; bar.a = 2; return bar.a; @@ -130,7 +130,7 @@ return bar.a; public void testExample() { CodeGen code = new CodeGen(""" struct Vector2D { int x; int y; }; -Vector2D !v = new Vector2D; +!Vector2D !v = new Vector2D; v.x = 1; if (arg) v.y = 2; @@ -169,7 +169,7 @@ arg=0+new s0.0; public void testLoop() { CodeGen code = new CodeGen(""" struct Bar { int a; }; -Bar !bar = new Bar; +!Bar !bar = new Bar; while (arg) { bar.a = bar.a + 2; arg = arg + 1; @@ -184,7 +184,7 @@ return bar.a; public void testIf() { CodeGen code = new CodeGen(""" struct Bar { int a; }; -Bar !bar = new Bar; +!Bar !bar = new Bar; if (arg) bar = null; bar.a = 1; return bar.a; @@ -197,7 +197,7 @@ return bar.a; public void testIf2() { CodeGen code = new CodeGen(""" struct Bar { int a; }; -Bar? !bar = null; +!Bar? !bar = null; if (arg) bar = new Bar; bar.a = 1; return bar.a; @@ -210,7 +210,7 @@ return bar.a; public void testIf3() { CodeGen code = new CodeGen(""" struct Bar { int a; }; -Bar bar = null; +!Bar !bar = null; if (arg) bar = null; bar.a = 1; return bar.a; @@ -223,7 +223,7 @@ return bar.a; public void testIfOrNull() { CodeGen code = new CodeGen(""" struct Bar { int a; }; -Bar? !bar = new Bar; +!Bar? !bar = new Bar; if (arg) bar = null; if( bar ) bar.a = 1; return bar; @@ -237,7 +237,7 @@ return bar; CodeGen code = new CodeGen( """ struct Bar { int a; }; -Bar? !bar = new Bar; +!Bar? !bar = new Bar; if (arg) bar = null; int rez = 3; if( !bar ) rez=4; @@ -252,7 +252,7 @@ return rez; public void testWhileWithNullInside() { CodeGen code = new CodeGen(""" struct s0 {int v0;}; -s0? !v0 = new s0; +!s0? !v0 = new s0; int ret = 0; while(arg) { ret = v0.v0; @@ -273,7 +273,7 @@ struct s0 { int v0; }; s0? v1=new s0; -s0? v1; +!s0? !v1; v1=new s0; """); try { code.parse(); fail(); } @@ -289,7 +289,7 @@ struct Iter { int x; int len; }; -Iter !i = new Iter; +!Iter !i = new Iter; i.len = arg; int sum=0; while( i.x < i.len ) { @@ -307,9 +307,9 @@ return sum; public void test1() { CodeGen code = new CodeGen(""" struct s0 {int v0;}; -s0 !ret = new s0; +!s0 !ret = new s0; while(arg) { - s0 !v0 = new s0; + !s0 !v0 = new s0; v0.v0 = arg; arg = arg-1; if (arg==5) ret=v0; @@ -325,8 +325,8 @@ return ret; public void test2() { CodeGen code = new CodeGen(""" struct s0 {int v0;}; -s0 !ret = new s0; -s0 !v0 = new s0; +!s0 !ret = new s0; +!s0 !v0 = new s0; while(arg) { v0.v0 = arg; arg = arg-1; @@ -344,9 +344,9 @@ return ret; public void test3() { CodeGen code = new CodeGen(""" struct s0 {int v0;}; -s0 !ret = new s0; +!s0 !ret = new s0; while(arg < 10) { - s0 !v0 = new s0; + !s0 !v0 = new s0; if (arg == 5) ret=v0; arg = arg + 1; } @@ -423,7 +423,7 @@ s0 v1 = v0; return v1; """); code.parse().opto(); - assertEquals("return s0;", code.print()); + assertEquals("return (const)s0;", code.print()); } @@ -473,9 +473,9 @@ return 0; @Test public void testReadBeforeStores() { var code = new CodeGen(""" struct S { int x; int y; }; - S !a = new S; S !b = new S; + !S !a = new S; !S !b = new S; a.x = 11; b.x = 22; - S !p = a; if (arg) p = b; + !S !p = a; if (arg) p = b; int before = p.x; a.y = 55; b.y = 66; a.x = 33; b.x = 44; @@ -488,7 +488,7 @@ return 0; static final String NESTED_MEMORY = """ struct S { int x; int y; int z; }; - S !s = new S; + !S !s = new S; s.x = 5; s.y = 7; s.z = 11; while (arg > 0) { s.x = s.x + 1; @@ -517,7 +517,7 @@ return 0; @Test public void testMemoryAtEarlyReturns() { var code = new CodeGen(""" struct S { int x; int y; int z; }; - S !s = new S; + !S !s = new S; s.x = 3; s.y = 5; s.z = 7; if (arg) { s.x = 11; s.z = 13; return s; } s.y = 17; @@ -532,9 +532,9 @@ return 0; @Test public void testKeepLoadsAtMerge() { var code = new CodeGen(""" struct S { int x; }; - S !a = new S; S !b = new S; + !S !a = new S; !S !b = new S; a.x = arg; b.x = arg+1; - S !p = a; S !q = b; + !S !p = a; !S !q = b; if (arg<0) { p=b; q=a; } int v; if (arg>1) v=p.x; else v=q.x; @@ -551,7 +551,7 @@ return 0; @Test public void testDropStores() { var code = new CodeGen(""" struct S { int x; }; - S !s = new S; + !S !s = new S; if (arg) s.x=arg+1; else s.x=arg+2; return s; """).parse().opto(); @@ -564,9 +564,9 @@ return 0; @Test public void testKeepReadsBeforeWrites() { var code = new CodeGen(""" struct S { int x; int y; }; - S !a = new S; S !b = new S; + !S !a = new S; !S !b = new S; a.x=arg; b.x=arg+1; - S !p=a; S !q=b; + !S !p=a; !S !q=b; if (arg<0) { p=b; q=a; } int v; if (arg>1) { v=p.x; p.x=41; p.y=5; } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter10bTest.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter10bTest.java deleted file mode 100644 index f2b83cdd..00000000 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter10bTest.java +++ /dev/null @@ -1,60 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.codegen.*; -import com.seaofnodes.simple.node.*; -import org.junit.Test; -import static org.junit.Assert.*; - -public class Chapter10bTest { - @Test public void testIndependentField() { - var code = new CodeGen(""" - struct S { int x; int y; }; - S !s = new S; - s.x = 42; - while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } - return s.x; - """).parse().opto(); - var stop = code._stop; - assertEquals("return 42;",stop.toString()); - assertEquals("42",Eval2.eval(code,5)); - assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); - } - - @Test public void testParallelMemoryPhis() { - var code = new CodeGen(""" - struct S { int x; int y; int z; }; - S !a = new S; S !b = new S; - S !p = a; if (arg) p = b; - while (arg > 0) { - a.x = p.x + arg; - a.y = p.y + 2; - a.z = p.z + 3; - arg = arg - 1; - } - return a; - """).parse().opto(); - var stop = code._stop; - int[] phis = {0}; - stop.walk(n -> { - if (n instanceof MemPhiNode) phis[0]++; - if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) - for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) - assertTrue(a=3); - assertEquals("S{x=1,y=2,z=3}",Eval2.eval(code,4)); - } - - @Test public void testLateSliceWorklist() { - // Seed 97 exposed a store selecting a bulk predecessor without queuing - // it. Keep both the worklist assertion and the final heap check. - for (int seed : new int[]{0,97,123,456}) { - var code = new CodeGen(Chapter10Test.NESTED_MEMORY,com.seaofnodes.simple.type.TypeInteger.BOT,seed,false).parse(); - code.opto(); - assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4)); - } - } -} diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java index c56d914f..e93da54b 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter11Test.java @@ -1,266 +1,60 @@ package com.seaofnodes.simple; -import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.print.IRPrinter; - +import com.seaofnodes.simple.codegen.*; +import com.seaofnodes.simple.node.*; import org.junit.Test; -import static org.junit.Assert.assertEquals; +import static org.junit.Assert.*; public class Chapter11Test { - - @Test - public void testPrimes() { - CodeGen code = new CodeGen( -""" -if( arg < 2 ) return 0; -int primeCount = 1; -int prime = 3; -while( prime <= arg ) { - int isPrime = 1; - // Check for even case, so the next loop need only check odds - if( (prime/2)*2 == prime ) - continue; - // Check odds up to sqrt of prime - int j = 3; - while( j*j <= prime ) { - if( (prime/j)*j == prime ) { - isPrime = 0; - break; + @Test public void testIndependentField() { + var code = new CodeGen(""" + struct S { int x; int y; }; + !S !s = new S; + s.x = 42; + while (arg > 0) { s.y = s.y + arg; arg = arg - 1; } + return s.x; + """).parse().opto(); + var stop = code._stop; + assertEquals("return 42;",stop.toString()); + assertEquals("42",Eval2.eval(code,5)); + assertNull(stop.walk(n -> n instanceof LoadNode ? n : null)); + } + + @Test public void testParallelMemoryPhis() { + var code = new CodeGen(""" + struct S { int x; int y; int z; }; + !S !a = new S; !S !b = new S; + !S !p = a; if (arg) p = b; + while (arg > 0) { + a.x = p.x + arg; + a.y = p.y + 2; + a.z = p.z + 3; + arg = arg - 1; + } + return a; + """).parse().opto(); + var stop = code._stop; + int[] phis = {0}; + stop.walk(n -> { + if (n instanceof MemPhiNode) phis[0]++; + if (n instanceof MemMergeNode m && m.in(1) instanceof BulkMemPhiNode b) + for(int a=b._aliases.nextSetBit(0); a>=0; a=b._aliases.nextSetBit(a+1)) + assertTrue(a=3); + assertEquals("S{x=1,y=2,z=3}",Eval2.eval(code,4)); + } + + @Test public void testLateSliceWorklist() { + // Seed 97 exposed a store selecting a bulk predecessor without queuing + // it. Keep both the worklist assertion and the final heap check. + for (int seed : new int[]{0,97,123,456}) { + var code = new CodeGen(Chapter10Test.NESTED_MEMORY,com.seaofnodes.simple.type.TypeInteger.BOT,seed,false).parse(); + code.opto(); + assertEquals("S{x=9,y=25,z=17}",Eval2.eval(code,4)); } - j = j + 2; - } - if( isPrime ) - primeCount = primeCount + 1; - prime = prime + 2; -} -return primeCount; -"""); - code.parse().opto(); - assertEquals("return Phi(Region,0,Phi(Loop,1,Phi(Region,Phi_primeCount,Phi_primeCount,(Phi_primeCount+1))));", code.print()); - assertEquals("0", Eval2.eval(code, 1)); // No primes 1 or below - assertEquals("1", Eval2.eval(code, 2)); // 2 - assertEquals("2", Eval2.eval(code, 3)); // 2, 3 - assertEquals("2", Eval2.eval(code, 4)); // 2, 3 - assertEquals("3", Eval2.eval(code, 5)); // 2, 3, 5 - assertEquals("4", Eval2.eval(code, 10)); // 2, 3, 5, 7 - } - - @Test - public void testAntiDeps1() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v=new S; -v.f = 2; -int i=new S.f; -i=v.f; -if (arg) v.f=1; -return i; -"""); - code.parse().opto(); - assertEquals("return 2;", code.print()); - assertEquals("2", Eval2.eval(code, 0)); - assertEquals("2", Eval2.eval(code, 1)); - } - - @Test - public void testAntiDeps2() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -v.f = arg; -S !t = new S; -int i = 0; -if (arg) { - if (arg+1) v = t; - i = v.f; -} else { - v.f = 2; -} -return i; -"""); - code.parse().opto(); - assertEquals("return Phi(Region,.f,0);", code.print()); - } - - @Test - public void testAntiDeps3() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v0 = new S; -S? v1; -if (arg) v1 = new S; -if (v1) { - v0.f = v1.f; -} else { - v0.f = 2; -} -return v0; -"""); - code.parse().opto(); - assertEquals("return S;", code.print()); - } - - - @Test - public void testAntiDeps4() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -v.f = arg; -S t = new S; -int i = v.f; -if (arg+1) arg= 0; -while (arg) v.f = 2; -return i; -"""); - code.parse().opto(); - assertEquals("return arg;", code.print()); - } - - @Test - public void testAntiDeps5() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -while(1) { - while(arg+1) { arg=arg-1; } - if (arg) break; - v.f = 2; -} -return v; -"""); - code.parse().opto(); - assertEquals("return S;", code.print()); - } - - @Test - public void testAntiDeps6() { - CodeGen code = new CodeGen( -""" -struct s { int v; }; -s !ptr=new s; -while( -arg ) - ptr = new s; -while(1) - arg = arg+ptr.v; -"""); - code.parse().opto(); - assertEquals("return Top;", code.print()); } - - @Test - public void testAntiDeps7() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -S t = new S; -int i = v.f; -while (arg) { - v.f = arg; - arg = arg-1; -} -return i; -"""); - code.parse().opto(); - assertEquals("return 0;", code.print()); - } - - @Test - public void testAntiDeps8() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -S t = new S; -while(arg) { - arg=arg-1; - int f = v.f; - v.f = 2; - if (arg) arg = f; - else v.f = 3; -} -return arg; -"""); - code.parse().opto(); - assertEquals("return 0;", code.print()); - } - - @Test - public void testAntiDeps9() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -S t = new S; -if (arg) { - v.f=2; - int i=t.f; - v.f=i; -} -return v; -"""); - code.parse().opto(); - assertEquals("return S;", code.print()); - } - - @Test - public void testExample2() { - CodeGen code = new CodeGen( -""" -struct S { int f; }; -S !v = new S; -int i = arg; -while (arg > 0) { - int j = i/3; - if (arg == 5) - v.f = j; - arg = arg - 1; -} -return v; - """); - code.parse().opto(); - //assertEquals("return new S;", code.print()); - } - - @Test - public void testScheduleUse() { - CodeGen code = new CodeGen( -""" -int v0=0; -while(0>=0) { - u1 v1=0; - v1=v0; - if(v1*0) - v0=-v1; -} -return 0; -"""); - code.parse().opto(); - assertEquals("return Top;", code.print()); - } - - @Test - public void testLoopCarriedDep() { - CodeGen code = new CodeGen( -""" -u32 v0=0; -{ - int v1=0; - while(v1) { - v1=1>>>v0!=0; - v0=v1/0; - } - return v1; -} -"""); - code.parse().opto(); - assertEquals("return 0;", code.print()); - } - } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java index c50be559..8e9aaed6 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter12Test.java @@ -1,82 +1,281 @@ package com.seaofnodes.simple; import com.seaofnodes.simple.codegen.CodeGen; -import com.seaofnodes.simple.node.StopNode; import org.junit.Test; import static org.junit.Assert.assertEquals; import static org.junit.Assert.fail; public class Chapter12Test { - @Test public void testSubZeroFloat() { - var code = new CodeGen("flt x = arg; return 0-x;").parse().opto().typeCheck(); - // Compare strings so +0.0 and -0.0 remain distinct. - assertEquals("0.0", Eval2.eval(code,0)); - assertEquals("-1.0", Eval2.eval(code,1)); + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); } - @Test public void testDeadNumericReturns() { - for( String[] test : new String[][] { - {"if(1) return 7; else return 2.5;", "7"}, - {"if(0) return 7; else return 2.5;", "2.5"}, - {"return 7; return 2.5;", "7"}, - {"return 2.5; return 7;", "2.5"} - } ) { - String src = test[0]; - var code = new CodeGen(src).parse().opto().typeCheck(); - assertEquals(src,test[1],Eval2.eval(code,0)); - } + @Test + public void testLinkedList0() { + CodeGen code = new CodeGen( +""" +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 { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); } } + @Test + public void testLinkedList1() { + CodeGen code = new CodeGen( +""" +struct LLI { !LLI? !next; int q; }; +!LLI? !head = null; +while( arg ) { + !LLI !x = new LLI; + x.next = head; + x.q = arg; + head = x; + arg = arg-1; +} +if( !head ) return 0; +LLI? next = head.next; +if( next==null ) return 1; +return next.q; +"""); + code.parse().opto().typeCheck(); + assertEquals("return Phi(Region,0,1,.q);", code.print()); + assertEquals("2", Eval2.eval(code, 3)); + } @Test - public void testJig() { + public void testCoRecur() { CodeGen code = new CodeGen( """ -return 3.14; +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; """); code.parse().opto(); - assertEquals("return 3.14;", code.print()); - assertEquals("3.14", Eval2.eval(code, 0)); + assertEquals("return 17;", code.print()); } @Test - public void testFloat() { + public void testNullRef0() { CodeGen code = new CodeGen( """ -return 3.14; +struct N { !N? !next; int i; }; +N n = new N; +return n.next; """); code.parse().opto(); - assertEquals("return 3.14;", code.print()); - assertEquals("3.14", Eval2.eval(code, 0)); + assertEquals("return null;", code.print()); } @Test - public void testSquareRoot() { + public void testNullRef1() { CodeGen code = new CodeGen( """ -flt guess = arg; -while( 1 ) { - flt next = (arg/guess + guess)/2; - if( next == guess ) break; - guess = next; -} -return guess; +struct M { int m; }; +struct N { !M !next; int i; }; +N n = new N { next = new M; }; +return n.next; +"""); + code.parse().opto(); + assertEquals("return (const)M;", code.print()); + } + + @Test + public void testNullRef2() { + CodeGen code = new CodeGen( +""" +struct M { int m; }; +struct N { !M !next; int i; }; +N n = new N { next = null; }; +return n.next; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Type null is not of declared type *M",e.getMessage()); } + } + + @Test + public void testNullRef3() { + CodeGen code = new CodeGen( +""" +struct N { !N? !next; int i; }; +!N !n = new N; +n.i = 3.14; +return n.i; +"""); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Type 3.14 is not of declared type i64",e.getMessage()); } + } + + @Test + public void testNullRef4() { + CodeGen code = new CodeGen("return -null-5/null-5;"); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot '//' null",e.getMessage()); } + } + + @Test public void testNullRef5() { + CodeGen code = new CodeGen("return null+42;"); + try { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Cannot '+' null",e.getMessage()); } + } + + @Test + public void testEmpty() { + CodeGen code = new CodeGen( +""" +struct S{}; +return 0; """); code.parse().opto(); - assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)*0.5f));", code.print()); - assertEquals("3.0", Eval2.eval(code, 9)); - assertEquals("1.414213562373095", Eval2.eval(code, 2)); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); } @Test - public void testFPOps() { + public void testForwardRef0() { CodeGen code = new CodeGen( """ -flt x = arg; -return x+1==x; +struct S1 { !S2? !s; }; +return new S2; +"""); + try { code.parse().opto(); fail(); } + catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); } + } + + @Test + public void testForwardRef1() { + CodeGen code = new CodeGen( +""" +struct S1 { !S2? !s; }; +struct S2 { int x; }; +return new S1.s=new S2; """); code.parse().opto(); - assertEquals("return ((flt)arg==(ToFloat+1.0f));", code.print()); - assertEquals("0", Eval2.eval(code, 1)); + assertEquals("return S2;", code.print()); + } + + @Test + public void testcheckNull() { + CodeGen code = new CodeGen( +""" +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 { code.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + } + + @Test + public void testCoRecur2() { + CodeGen code = new CodeGen( +""" +struct A { !B? !f0; !C? !f1; }; !A !a = new A; +struct B { !C? !f0; !A? !f1; }; !B !b = new B; +struct C { !A? !f0; !B? !f1; }; !C !c = new C; + +a.f0=b; a.f1=c; +b.f0=c; b.f1=a; +c.f0=a; c.f1=b; + +return a.f0.f1.f0.f1.f0; + +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("return B;", code._stop.toString()); + assertEquals("B{f0=C},f1=A{f0=$cyclic,f1=$cyclic}}", Eval2.eval(code, 0)); + } + + @Test + public void testCoRecur3() { + CodeGen code = new CodeGen( +""" +struct A { !L? !a; !T? !b; !F? !c; }; !A !a = new A; +struct B { !M? !a; !U? !b; !G? !c; }; !B !b = new B; +struct C { !N? !a; !V? !b; !H? !c; }; !C !c = new C; +struct D { !O? !a; !W? !b; !I? !c; }; !D !d = new D; +struct E { !P? !a; !X? !b; !J? !c; }; !E !e = new E; +struct F { !Q? !a; !Y? !b; !K? !c; }; !F !f = new F; +struct G { !R? !a; !Z? !b; !L? !c; }; !G !g = new G; +struct H { !S? !a; !A? !b; !M? !c; }; !H !h = new H; +struct I { !T? !a; !B? !b; !N? !c; }; !I !i = new I; +struct J { !U? !a; !C? !b; !O? !c; }; !J !j = new J; +struct K { !V? !a; !D? !b; !P? !c; }; !K !k = new K; +struct L { !W? !a; !E? !b; !Q? !c; }; !L !l = new L; +struct M { !X? !a; !F? !b; !R? !c; }; !M !m = new M; +struct N { !Y? !a; !G? !b; !S? !c; }; !N !n = new N; +struct O { !Z? !a; !H? !b; !T? !c; }; !O !o = new O; +struct P { !A? !a; !I? !b; !U? !c; }; !P !p = new P; +struct Q { !B? !a; !J? !b; !V? !c; }; !Q !q = new Q; +struct R { !C? !a; !K? !b; !W? !c; }; !R !r = new R; +struct S { !D? !a; !L? !b; !X? !c; }; !S !s = new S; +struct T { !E? !a; !M? !b; !Y? !c; }; !T !t = new T; +struct U { !F? !a; !N? !b; !Z? !c; }; !U !u = new U; +struct V { !G? !a; !O? !b; !A? !c; }; !V !v = new V; +struct W { !H? !a; !P? !b; !B? !c; }; !W !w = new W; +struct X { !I? !a; !Q? !b; !C? !c; }; !X !x = new X; +struct Y { !J? !a; !R? !b; !D? !c; }; !Y !y = new Y; +struct Z { !K? !a; !S? !b; !E? !c; }; !Z !z = new Z; + +a.a=l; a.b=t; a.c=f; +b.a=m; b.b=u; b.c=g; +c.a=n; c.b=v; c.c=h; +d.a=o; d.b=w; d.c=i; +e.a=p; e.b=x; e.c=j; +f.a=q; f.b=y; f.c=k; +g.a=r; g.b=z; g.c=l; +h.a=s; h.b=a; h.c=m; +i.a=t; i.b=b; i.c=n; +j.a=u; j.b=c; j.c=o; +k.a=v; k.b=d; k.c=p; +l.a=w; l.b=e; l.c=q; +m.a=x; m.b=f; m.c=r; +n.a=y; n.b=g; n.c=s; +o.a=z; o.b=h; o.c=t; +p.a=a; p.b=i; p.c=u; +q.a=b; q.b=j; q.c=v; +r.a=c; r.b=k; r.c=w; +s.a=d; s.b=l; s.c=x; +t.a=e; t.b=m; t.c=y; +u.a=f; u.b=n; u.c=z; +v.a=g; v.b=o; v.c=a; +w.a=h; w.b=p; w.c=b; +x.a=i; x.b=q; x.c=c; +y.a=j; y.b=r; y.c=d; +z.a=k; z.b=s; z.c=e; + +return a.b.c.a.b.c.a.b.c.a.b.c.a.b.c.a.b.c; + +"""); + code.parse().opto().typeCheck().GCM().localSched(); + assertEquals("return R;", code._stop.toString()); + assertEquals("R{a=C{a=N},b=V},c=H}},b=K{a=$cyclic,b=D{a=O},b=W},c=I}},c=P}},c=$cyclic}", Eval2.eval(code, 0)); } } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter13Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter13Test.java index 4e1db3b4..62bc1654 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter13Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter13Test.java @@ -1,281 +1,266 @@ package com.seaofnodes.simple; - import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.print.IRPrinter; + + import org.junit.Test; import static org.junit.Assert.assertEquals; -import static org.junit.Assert.fail; public class Chapter13Test { + @Test - public void testJig() { + public void testPrimes() { CodeGen code = new CodeGen( """ -return 3.14; +if( arg < 2 ) return 0; +int primeCount = 1; +int prime = 3; +while( prime <= arg ) { + int isPrime = 1; + // Check for even case, so the next loop need only check odds + if( (prime/2)*2 == prime ) + continue; + // Check odds up to sqrt of prime + int j = 3; + while( j*j <= prime ) { + if( (prime/j)*j == prime ) { + isPrime = 0; + break; + } + j = j + 2; + } + if( isPrime ) + primeCount = primeCount + 1; + prime = prime + 2; +} +return primeCount; """); code.parse().opto(); - assertEquals("return 3.14;", code.print()); - assertEquals("3.14", Eval2.eval(code, 0)); + assertEquals("return Phi(Region,0,Phi(Loop,1,Phi(Region,Phi_primeCount,Phi_primeCount,(Phi_primeCount+1))));", code.print()); + assertEquals("0", Eval2.eval(code, 1)); // No primes 1 or below + assertEquals("1", Eval2.eval(code, 2)); // 2 + assertEquals("2", Eval2.eval(code, 3)); // 2, 3 + assertEquals("2", Eval2.eval(code, 4)); // 2, 3 + assertEquals("3", Eval2.eval(code, 5)); // 2, 3, 5 + assertEquals("4", Eval2.eval(code, 10)); // 2, 3, 5, 7 } @Test - public void testLinkedList0() { + public void testAntiDeps1() { CodeGen code = new CodeGen( """ -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; +struct S { int f; }; +!S !v=new S; +v.f = 2; +int i=new S.f; +i=v.f; +if (arg) v.f=1; +return i; """); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'next'",e.getMessage()); } + code.parse().opto(); + assertEquals("return 2;", code.print()); + assertEquals("2", Eval2.eval(code, 0)); + assertEquals("2", Eval2.eval(code, 1)); } @Test - public void testLinkedList1() { + public void testAntiDeps2() { CodeGen code = new CodeGen( """ -struct LLI { LLI? next; int q; }; -LLI? !head = null; -while( arg ) { - LLI !x = new LLI; - x.next = head; - x.q = arg; - head = x; - arg = arg-1; +struct S { int f; }; +!S !v = new S; +v.f = arg; +!S !t = new S; +int i = 0; +if (arg) { + if (arg+1) v = t; + i = v.f; +} else { + v.f = 2; } -if( !head ) return 0; -LLI? next = head.next; -if( next==null ) return 1; -return next.q; +return i; """); - code.parse().opto().typeCheck(); - assertEquals("return Phi(Region,0,1,.q);", code.print()); - assertEquals("2", Eval2.eval(code, 3)); + code.parse().opto(); + assertEquals("return Phi(Region,.f,0);", code.print()); } @Test - public void testCoRecur() { + public void testAntiDeps3() { CodeGen code = new CodeGen( """ -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; +struct S { int f; }; +!S !v0 = new S; +!S? !v1; +if (arg) v1 = new S; +if (v1) { + v0.f = v1.f; +} else { + v0.f = 2; +} +return v0; """); code.parse().opto(); - assertEquals("return 17;", code.print()); + assertEquals("return S;", code.print()); } + @Test - public void testNullRef0() { + public void testAntiDeps4() { CodeGen code = new CodeGen( """ -struct N { N? next; int i; }; -N n = new N; -return n.next; +struct S { int f; }; +!S !v = new S; +v.f = arg; +S t = new S; +int i = v.f; +if (arg+1) arg= 0; +while (arg) v.f = 2; +return i; """); code.parse().opto(); - assertEquals("return null;", code.print()); + assertEquals("return arg;", code.print()); } @Test - public void testNullRef1() { + public void testAntiDeps5() { CodeGen code = new CodeGen( """ -struct M { int m; }; -struct N { M next; int i; }; -N n = new N { next = new M; }; -return n.next; +struct S { int f; }; +!S !v = new S; +while(1) { + while(arg+1) { arg=arg-1; } + if (arg) break; + v.f = 2; +} +return v; """); code.parse().opto(); - assertEquals("return (const)M;", code.print()); + assertEquals("return S;", code.print()); } @Test - public void testNullRef2() { + public void testAntiDeps6() { CodeGen code = new CodeGen( """ -struct M { int m; }; -struct N { M next; int i; }; -N n = new N { next = null; }; -return n.next; +struct s { int v; }; +!s !ptr=new s; +while( -arg ) + ptr = new s; +while(1) + arg = arg+ptr.v; """); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Type null is not of declared type *M",e.getMessage()); } + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test - public void testNullRef3() { + public void testAntiDeps7() { CodeGen code = new CodeGen( """ -struct N { N? next; int i; }; -N !n = new N; -n.i = 3.14; -return n.i; +struct S { int f; }; +!S !v = new S; +S t = new S; +int i = v.f; +while (arg) { + v.f = arg; + arg = arg-1; +} +return i; """); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Type 3.14 is not of declared type i64",e.getMessage()); } - } - - @Test - public void testNullRef4() { - CodeGen code = new CodeGen("return -null-5/null-5;"); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot '//' null",e.getMessage()); } - } - - @Test public void testNullRef5() { - CodeGen code = new CodeGen("return null+42;"); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot '+' null",e.getMessage()); } + code.parse().opto(); + assertEquals("return 0;", code.print()); } @Test - public void testEmpty() { + public void testAntiDeps8() { CodeGen code = new CodeGen( """ -struct S{}; -return 0; +struct S { int f; }; +!S !v = new S; +S t = new S; +while(arg) { + arg=arg-1; + int f = v.f; + v.f = 2; + if (arg) arg = f; + else v.f = 3; +} +return arg; """); code.parse().opto(); assertEquals("return 0;", code.print()); - assertEquals("0", Eval2.eval(code, 0)); } @Test - public void testForwardRef0() { + public void testAntiDeps9() { CodeGen code = new CodeGen( """ -struct S1 { S2? s; }; -return new S2; +struct S { int f; }; +!S !v = new S; +S t = new S; +if (arg) { + v.f=2; + int i=t.f; + v.f=i; +} +return v; """); - try { code.parse().opto(); fail(); } - catch( Exception e ) { assertEquals("Unknown struct type 'S2'",e.getMessage()); } + code.parse().opto(); + assertEquals("return S;", code.print()); } @Test - public void testForwardRef1() { + public void testExample2() { CodeGen code = new CodeGen( """ -struct S1 { S2? s; }; -struct S2 { int x; }; -return new S1.s=new S2; -"""); +struct S { int f; }; +!S !v = new S; +int i = arg; +while (arg > 0) { + int j = i/3; + if (arg == 5) + v.f = j; + arg = arg - 1; +} +return v; + """); code.parse().opto(); - assertEquals("return S2;", code.print()); + //assertEquals("return new S;", code.print()); } @Test - public void testcheckNull() { + public void testScheduleUse() { CodeGen code = new CodeGen( """ -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; +int v0=0; +while(0>=0) { + u1 v1=0; + v1=v0; + if(v1*0) + v0=-v1; +} +return 0; """); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Might be null accessing 'i'",e.getMessage()); } + code.parse().opto(); + assertEquals("return Top;", code.print()); } @Test - public void testCoRecur2() { + public void testLoopCarriedDep() { CodeGen code = new CodeGen( """ -struct A { B? f0; C? f1; }; A !a = new A; -struct B { C? f0; A? f1; }; B !b = new B; -struct C { A? f0; B? f1; }; C !c = new C; - -a.f0=b; a.f1=c; -b.f0=c; b.f1=a; -c.f0=a; c.f1=b; - -return a.f0.f1.f0.f1.f0; - -"""); - code.parse().opto().typeCheck().GCM().localSched(); - assertEquals("return B;", code._stop.toString()); - assertEquals("B{f0=C},f1=A{f0=$cyclic,f1=$cyclic}}", Eval2.eval(code, 0)); +u32 v0=0; +{ + int v1=0; + while(v1) { + v1=1>>>v0!=0; + v0=v1/0; } - - @Test - public void testCoRecur3() { - CodeGen code = new CodeGen( -""" -struct A { L? a; T? b; F? c; }; A !a = new A; -struct B { M? a; U? b; G? c; }; B !b = new B; -struct C { N? a; V? b; H? c; }; C !c = new C; -struct D { O? a; W? b; I? c; }; D !d = new D; -struct E { P? a; X? b; J? c; }; E !e = new E; -struct F { Q? a; Y? b; K? c; }; F !f = new F; -struct G { R? a; Z? b; L? c; }; G !g = new G; -struct H { S? a; A? b; M? c; }; H !h = new H; -struct I { T? a; B? b; N? c; }; I !i = new I; -struct J { U? a; C? b; O? c; }; J !j = new J; -struct K { V? a; D? b; P? c; }; K !k = new K; -struct L { W? a; E? b; Q? c; }; L !l = new L; -struct M { X? a; F? b; R? c; }; M !m = new M; -struct N { Y? a; G? b; S? c; }; N !n = new N; -struct O { Z? a; H? b; T? c; }; O !o = new O; -struct P { A? a; I? b; U? c; }; P !p = new P; -struct Q { B? a; J? b; V? c; }; Q !q = new Q; -struct R { C? a; K? b; W? c; }; R !r = new R; -struct S { D? a; L? b; X? c; }; S !s = new S; -struct T { E? a; M? b; Y? c; }; T !t = new T; -struct U { F? a; N? b; Z? c; }; U !u = new U; -struct V { G? a; O? b; A? c; }; V !v = new V; -struct W { H? a; P? b; B? c; }; W !w = new W; -struct X { I? a; Q? b; C? c; }; X !x = new X; -struct Y { J? a; R? b; D? c; }; Y !y = new Y; -struct Z { K? a; S? b; E? c; }; Z !z = new Z; - -a.a=l; a.b=t; a.c=f; -b.a=m; b.b=u; b.c=g; -c.a=n; c.b=v; c.c=h; -d.a=o; d.b=w; d.c=i; -e.a=p; e.b=x; e.c=j; -f.a=q; f.b=y; f.c=k; -g.a=r; g.b=z; g.c=l; -h.a=s; h.b=a; h.c=m; -i.a=t; i.b=b; i.c=n; -j.a=u; j.b=c; j.c=o; -k.a=v; k.b=d; k.c=p; -l.a=w; l.b=e; l.c=q; -m.a=x; m.b=f; m.c=r; -n.a=y; n.b=g; n.c=s; -o.a=z; o.b=h; o.c=t; -p.a=a; p.b=i; p.c=u; -q.a=b; q.b=j; q.c=v; -r.a=c; r.b=k; r.c=w; -s.a=d; s.b=l; s.c=x; -t.a=e; t.b=m; t.c=y; -u.a=f; u.b=n; u.c=z; -v.a=g; v.b=o; v.c=a; -w.a=h; w.b=p; w.c=b; -x.a=i; x.b=q; x.c=c; -y.a=j; y.b=r; y.c=d; -z.a=k; z.b=s; z.c=e; - -return a.b.c.a.b.c.a.b.c.a.b.c.a.b.c.a.b.c; - + return v1; +} """); - code.parse().opto().typeCheck().GCM().localSched(); - assertEquals("return R;", code._stop.toString()); - assertEquals("R{a=C{a=N},b=V},c=H}},b=K{a=$cyclic,b=D{a=O},b=W},c=I}},c=P}},c=$cyclic}", Eval2.eval(code, 0)); + code.parse().opto(); + assertEquals("return 0;", code.print()); } + } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java new file mode 100644 index 00000000..009beb0b --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java @@ -0,0 +1,82 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter14FloatTest { + @Test public void testSubZeroFloat() { + var code = new CodeGen("flt x = arg; return 0-x;").parse().opto().typeCheck(); + // Compare strings so +0.0 and -0.0 remain distinct. + assertEquals("0.0", Eval2.eval(code,0)); + assertEquals("-1.0", Eval2.eval(code,1)); + } + + @Test public void testDeadNumericReturns() { + for( String[] test : new String[][] { + {"if(1) return 7; else return 2.5;", "7"}, + {"if(0) return 7; else return 2.5;", "2.5"}, + {"return 7; return 2.5;", "7"}, + {"return 2.5; return 7;", "2.5"} + } ) { + String src = test[0]; + var code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals(src,test[1],Eval2.eval(code,0)); + } + } + + + @Test + public void testJig() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + } + + @Test + public void testFloat() { + CodeGen code = new CodeGen( +""" +return 3.14; +"""); + code.parse().opto(); + assertEquals("return 3.14;", code.print()); + assertEquals("3.14", Eval2.eval(code, 0)); + } + + @Test + public void testSquareRoot() { + CodeGen code = new CodeGen( +""" +flt guess = arg; +while( 1 ) { + flt next = (arg/guess + guess)/2; + if( next == guess ) break; + guess = next; +} +return guess; +"""); + code.parse().opto(); + assertEquals("return Phi(Loop,(flt)arg,(((ToFloat/Phi_guess)+Phi_guess)*0.5f));", code.print()); + assertEquals("3.0", Eval2.eval(code, 9)); + assertEquals("1.414213562373095", Eval2.eval(code, 2)); + } + + @Test + public void testFPOps() { + CodeGen code = new CodeGen( +""" +flt x = arg; +return x+1==x; +"""); + code.parse().opto(); + assertEquals("return ((flt)arg==(ToFloat+1.0f));", code.print()); + assertEquals("0", Eval2.eval(code, 1)); + } +} diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter14Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter14Test.java index 7af35b56..da7e50bc 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter14Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter14Test.java @@ -93,7 +93,7 @@ return b; CodeGen code = new CodeGen( """ struct Foo { u1 b; }; -Foo !f = new Foo; +!Foo !f = new Foo; f.b = 123; return f.b; """); diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java index 6ba4e2b1..66a50d0f 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter15Test.java @@ -25,8 +25,8 @@ return 3.14; public void testCyclic() { CodeGen code = new CodeGen( """ -struct C { C? l; }; -C !c = new C; +struct C { !C? !l; }; +!C !c = new C; c.l = c; return c; """); @@ -98,7 +98,7 @@ return a[0]; CodeGen code = new CodeGen( """ struct A { int i; }; -A?[] !a = new A?[2]; +!A?[] !a = new !A?[2]; return a; """); code.parse().opto(); @@ -112,16 +112,16 @@ return a; """ struct S { int x; flt y; }; // A new S -S !s = new S; s.x=99; s.y = 3.14; +!S !s = new S; s.x=99; s.y = 3.14; // Double-d array of Ss. Fill in one row. -S?[]?[] !iss = new S?[]?[2]; -iss[0] = new S?[7]; +!S?[]?[] !iss = new !S?[]?[2]; +iss[0] = new !S?[7]; iss[0][2] = s; // Now pull out the filled-in value, with null checks flt rez; -S?[]? is = iss[arg]; +!S?[]? is = iss[arg]; if( !is ) rez = 1.2; else { S? i = is[2]; @@ -142,11 +142,11 @@ return rez; """ struct S { int x; flt y; }; // A new S -S !s = new S; s.x=99; s.y = 3.14; +!S !s = new S; s.x=99; s.y = 3.14; // Double-d array of Ss. Fill in one row. -S?[]?[] !iss = new S?[]?[2]; -iss[0] = new S?[7]; +!S?[]?[] !iss = new !S?[]?[2]; +iss[0] = new !S?[7]; iss[0][2] = s; // Now pull out the filled-in value, with null checks @@ -167,9 +167,9 @@ return rez;"""); CodeGen code = new CodeGen( """ // Can we define a forward-reference array? -struct Tree { Tree?[]? _kids; }; -Tree !root = new Tree; -root._kids = new Tree?[2]; // NO BANG SO ARRAY IS OF IMMUTABLE TREES???? +struct Tree { !Tree?[]? !_kids; }; +!Tree !root = new Tree; +root._kids = new !Tree?[2]; // NO BANG SO ARRAY IS OF IMMUTABLE TREES???? root._kids[0] = new Tree; return root; """); @@ -182,7 +182,7 @@ return root; public void testNestedStructAddMemProj() { CodeGen code = new CodeGen( """ -struct S { int a; int[] b; }; +struct S { int a; int[] !b; }; return 0; """); code.parse().opto(); @@ -227,8 +227,8 @@ return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 CodeGen code = new CodeGen( """ struct S {int i; flt f;}; -S !s1 = new S; -S !s2 = new S; +!S !s1 = new S; +!S !s2 = new S; s2.i = 3; s2.f = 2.0; if (arg) s1 = new S; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter16Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter16Test.java index 57ec5508..692ac8d5 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter16Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter16Test.java @@ -42,31 +42,6 @@ return x+y; assertEquals("5", Eval2.eval(code, 0)); } -// @Test -// public void testFinal0() { -// CodeGen code = new CodeGen( -//""" -//int !x=2; -//x=3; -//return x; -//"""); -// try { code.parse().opto(); fail(); } -// catch( Exception e ) { assertEquals("Cannot reassign final 'x'",e.getMessage()); } -// } - - @Test - public void testFinal1() { - CodeGen code = new CodeGen( -""" -int x=2, y=3; -if( arg ) { int x = y; x = x*x; y=x; } // Shadow final x -return y; -"""); - code.parse().opto(); - assertEquals("return Phi(Region,9,3);", code.print()); - assertEquals("3", Eval2.eval(code, 0)); - assertEquals("9", Eval2.eval(code, 1)); - } @Test public void testConstruct0() { @@ -80,18 +55,6 @@ return z.x; assertEquals("3", Eval2.eval(code, 0)); } - @Test - public void testConstruct1() { - CodeGen code = new CodeGen(""" -struct X { int !x; }; -X z = new X { x=3; }; -return z.x; -"""); - code.parse().opto(); - assertEquals("return 3;", code.print()); - assertEquals("3", Eval2.eval(code, 0)); - } - @Test public void testConstruct2() { CodeGen code = new CodeGen(""" @@ -105,84 +68,12 @@ return z.x; } - @Test - public void testStructFinal0() { - CodeGen code = new CodeGen(""" -struct Point { int !x, !y; }; -Point p = new Point { x=3; y=4; }; -return p; -"""); - code.parse().opto(); - assertEquals("return Point;", code.print()); - assertEquals("Point{x=3,y=4}", Eval2.eval(code, 0)); - } - - @Test - public void testStructFinal1() { - CodeGen code = new CodeGen(""" -struct Point { int x=3, y=4; }; -val p = new Point { x=5; y=6; }; -p.x++; -return p; -"""); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } - } - - @Test - public void testStructFinal2() { - CodeGen code = new CodeGen(""" -struct Point { int x=3, y=4; }; -val p = new Point; -p.x++; -return p; -"""); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } - } - - @Test - public void testStructFinal3() { - for( String fields : new String[] { "var x; var y;", "int[] x;", "int[] !x;" } ) { - String src = "struct Point { "+fields+" }; Point p = new Point; p.x++; return p;"; - try { new CodeGen(src).parse().opto(); fail(fields); } - catch( Exception e ) { assertEquals("'Point' is not fully initialized, field 'x' needs to be set in a constructor",e.getMessage()); } - } - } - - @Test - public void testStructFinal4() { - CodeGen code = new CodeGen(""" -struct Point { val x=3; val y=4; }; -Point p = new Point; -p.x++; -return p; -"""); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot modify final field 'x'",e.getMessage()); } - } - - @Test - public void testStructFinal5() { - CodeGen code = new CodeGen(""" -struct Point { var x=3; var y=4; }; -Point !p = new Point; -p.x++; -return p; -"""); - code.parse().opto(); - assertEquals("return Point;", code.print()); - assertEquals("Point{x=4,y=4}", Eval2.eval(code, 0)); - } - - // Same as the Chapter13 test with the same name, but using the new - // constructor syntax @Test public void testLinkedList1() { CodeGen code = new CodeGen( """ -struct LLI { LLI? next; int i; }; -LLI? !head = null; +struct LLI { !LLI? !next; int i; }; +!LLI? !head = null; while( arg ) { head = new LLI { next=head; i=arg; }; arg = arg-1; @@ -203,8 +94,8 @@ return next.i; public void testLinkedList2() { CodeGen code = new CodeGen( """ -struct LLI { LLI? next; int i; }; -LLI? !head = null; +struct LLI { !LLI? !next; int i; }; +!LLI? !head = null; while( arg ) { head = new LLI { next=head; @@ -256,13 +147,13 @@ return new Square; static final String CONSTRUCTOR_MEMORY = """ struct S { int x; int y; }; struct T { int z=arg+40; }; - T !t = new T; - S !a = new S { x=11; y=7; }; - S !b = new S { x=22; y=9; }; - S !p=a; + !T !t = new T; + !S !a = new S { x=11; y=7; }; + !S !b = new S { x=22; y=9; }; + !S !p=a; if (arg) p=b; int before=p.x; - S !c = new S { + !S !c = new S { x=p.x+1; { int i=0; while (i<2) { p.y=p.y+1; i=i+1; } } y=p.y; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter17Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter17Test.java deleted file mode 100644 index 37208308..00000000 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter17Test.java +++ /dev/null @@ -1,556 +0,0 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.codegen.CodeGen; -import org.junit.Test; -import static org.junit.Assert.assertEquals; -import static org.junit.Assert.fail; - -public class Chapter17Test { - - @Test - public void testJig() { - CodeGen code = new CodeGen( -""" -return 1; -"""); - code.parse().opto().typeCheck(); - assertEquals("return 1;", code.print()); - assertEquals("1", Eval2.eval(code, 0)); - } - - - // --------------------------------------------------------------- - @Test - public void testInc0() { - CodeGen code = new CodeGen(""" -return arg++; -"""); - code.parse().opto(); - assertEquals("return arg;", code.print()); - assertEquals("0", Eval2.eval(code, 0)); - } - - @Test - public void testInc1() { - CodeGen code = new CodeGen(""" -return arg+++arg++; -"""); - code.parse().opto(); - 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.parse().opto(); - 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.parse().opto(); - 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.parse().opto(); - 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.parse().opto(); - assertEquals("return 65535;", code.print()); - assertEquals("65535", Eval2.eval(code, 2)); - } - - @Test - public void testInc6() { - CodeGen code = new CodeGen("return --arg;"); - code.parse().opto(); - 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.parse().opto(); - 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.parse().opto(); - 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.parse().opto(); - 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;"); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Type 2.5f is not of declared type i64",e.getMessage()); } - } - - - // --------------------------------------------------------------- - @Test public void testVar0() { - CodeGen code = new CodeGen("var d; return d;"); - try { code.parse().opto(); fail(); } - catch( Exception e ) { assertEquals("Syntax error, expected =expression: ;",e.getMessage()); } - } - - @Test public void testVar1() { - CodeGen code = new CodeGen("val d; return d;"); - try { code.parse().opto(); fail(); } - catch( Exception e ) { assertEquals("Syntax error, expected =expression: ;",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.parse().opto(); - 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.parse().opto(); - 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.parse().opto(); - assertEquals("return 1;", code.print()); - assertEquals("1", Eval2.eval(code, 0)); - } - - @Test public void testVar5() { - CodeGen code = new CodeGen("struct S{int x;}; S? s; s=new S{x=3;}; s.x++; return s.x; // Ok, no initializer so x is mutable "); - code.parse().opto(); - assertEquals("return 4;", code.print()); - assertEquals("4", Eval2.eval(code, 0)); - } - - @Test public void testVar6() { - CodeGen code = new CodeGen("struct S{int x;}; val s = new S; s.x++; return s.x; // Error initializer so x is immutable "); - try { code.parse().opto().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;}; val s = new S{x=3;}; s.x++; return s.x; // Error initializer so x is immutable "); - try { code.parse().opto().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.parse().opto(); - 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.parse().opto(); - assertEquals("return 1;", code.print()); - assertEquals("1", Eval2.eval(code, 0)); - } - - @Test public void testVar10() { - CodeGen code = new CodeGen("struct S{int x;}; val s=new S; s.x++; return s.x; // Error, has val so x is immutable "); - try { code.parse().opto().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; }; -Foo !foo = new Foo { bar = bar; }; -foo.bar = bar; // Ok foo is mutable -foo.bar.x++; // Ok foo and foo.bar and foo.bar.x are all mutable - -val xfoo = foo; // Throw away mutability -xfoo.bar.x++; // Error, cannot mutate through xfoo -return xfoo.bar.x; - """); - try { code.parse().opto().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 - -val 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.parse().opto(); - assertEquals("return 45;", code.print()); - assertEquals("45", Eval2.eval(code, 0)); - } - - @Test - public void testVar13() { - CodeGen code = new CodeGen(""" -int i,i++; -"""); - try { code.parse().opto().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; }; -A x = new A { - return b; // read before init - b = new B; -}; -"""); - try { code.parse().opto(); fail(); } - catch( Exception e ) { assertEquals("Cannot read uninitialized field 'b'",e.getMessage()); } - } - - @Test - public void testVar15() { - CodeGen code = new CodeGen(""" -struct B {}; -struct A { B b; }; -return new A { - if (arg) b = new B; // Constructor ends with partial init of b -}.b; -"""); - try { code.parse(); fail(); } - catch( Exception e ) { assertEquals("'A' is not fully initialized, field 'b' needs to be set in a constructor",e.getMessage()); } - } - - @Test - public void testVar16() { - CodeGen code = new CodeGen( -""" -struct S{}; -val x = 1; -val s = new S{x = 2;}; -return x; -""" -); - try { code.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Cannot reassign final '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: ;",e.getMessage()); } - } - - // --------------------------------------------------------------- - @Test - public void testTrinary0() { - CodeGen code = new CodeGen(""" -return arg ? 1 : 2; -"""); - code.parse().opto(); - 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.parse().opto(); - assertEquals("return 0;", code.print()); - assertEquals("0", Eval2.eval(code, 0)); - } - - @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.parse().opto(); - 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.parse().opto(); - 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; }; -var b = arg ? new Bar { next = (arg==2) ? new Bar{x=2;}; x=1; }; -return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0" -"""); - code.parse().opto(); - 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.parse().opto(); - 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.parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("No common type amongst int and reference",e.getMessage()); } - } - - // --------------------------------------------------------------- - @Test - public void testFor0() { - CodeGen code = new CodeGen(""" -int sum=0; -for( int i=0; i=arg ) break; - sum += i; -} -return sum; -"""); - code.parse().opto(); - 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 + 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: ;",e.getMessage()); } + } + + // --------------------------------------------------------------- + @Test + public void testTrinary0() { + CodeGen code = new CodeGen(""" +return arg ? 1 : 2; +"""); + code.parse().opto(); + 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.parse().opto(); + assertEquals("return 0;", code.print()); + assertEquals("0", Eval2.eval(code, 0)); + } + + @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.parse().opto(); + 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.parse().opto(); + 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; }; +var b = arg ? new Bar { next = (arg==2) ? new Bar{x=2;}; x=1; }; +return b ? b.next ? b.next.x : b.x; // parses "b ? (b.next ? b.next.x : b.x) : 0" +"""); + code.parse().opto(); + 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.parse().opto(); + 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.parse().opto().typeCheck(); fail(); } + catch( Exception e ) { assertEquals("No common type amongst int and reference",e.getMessage()); } + } + + // --------------------------------------------------------------- + @Test + public void testFor0() { + CodeGen code = new CodeGen(""" +int sum=0; +for( int i=0; i=arg ) break; + sum += i; +} +return sum; +"""); + code.parse().opto(); + 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 int}? i2i = null; +{int -> int}? !i2i = null; var id = {{int->int} f-> return f;}; for(;;) { if (i2i) return i2i(arg); @@ -290,7 +290,7 @@ for(;;) { public void testFcn9() { CodeGen code = new CodeGen( """ -{int -> int}? i2i = null; +{int -> int}? !i2i = null; for(;;) { if (i2i) return i2i(arg); var x = {int i-> return i;}; @@ -311,13 +311,13 @@ struct Person { int age; }; -val fcn = { Person?[] ps, int x -> +val fcn = { !Person?[] !ps, int x -> val tmp = ps[x]; if( ps[x] ) ps[x].age++; }; -var ps = new Person?[2]; +var ps = new !Person?[2]; ps[0] = new Person; ps[1] = new Person; return fcn(ps,1); @@ -382,7 +382,7 @@ struct S { {int} f = { -> x(); return 0; }; // Do not let fref x be a field }; val x = { -> return 1; }; -S? s = null; +!S? !s = null; for(;;) { if (s) return s.x; } @@ -431,7 +431,7 @@ struct S { { int } f = { -> return x(); }; }; val x = { -> return 1; }; -S? s = null; +!S? !s = null; for(;;) { if (s) return s.f; } @@ -465,7 +465,7 @@ return f2f(o)(1); struct Person { int coffee_count; }; -Person !p = new Person; +!Person !p = new Person; p.coffee_count += 1; return p.coffee_count; """); @@ -476,10 +476,10 @@ return p.coffee_count; static final String CALL_MEMORY = """ struct S { int x; int y; }; - val bump = { S s, int d -> int old=s.x; s.x=old+d; return old; }; - S !a = new S { x=10; y=7; }; - S !b = new S { x=20; y=9; }; - S !p=a; if (arg) p=b; + val bump = { !S !s, int d -> int old=s.x; s.x=old+d; return old; }; + !S !a = new S { x=10; y=7; }; + !S !b = new S { x=20; y=9; }; + !S !p=a; if (arg) p=b; int before=p.x; int old=bump(p,3); int after=p.x; @@ -505,13 +505,13 @@ return p.coffee_count; static final String RECURSIVE_MEMORY = """ struct S { int x; }; - val rec = { S s, int n -> + val rec = { !S !s, int n -> if (n==0) return s.x; int before=s.x; s.x=before+1; return before+rec(s,n-1); }; - S !s=new S { x=10; }; + !S !s=new S { x=10; }; int value=rec(s,arg); return value*100+s.x; """; @@ -524,12 +524,12 @@ return p.coffee_count; static final String INLINE_MEMORY = """ struct S { int x; int y; }; - val make = { S s -> + val make = { !S s -> S t = new S { x=s.x+1; y=3; }; s.y=9; return t; }; - S !a = new S { x=arg+40; y=7; }; + !S !a = new S { x=arg+40; y=7; }; S t=make(a); return a.x*10000+a.y*100+t.x+t.y; """; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 841d9298..6196f9af 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -48,12 +48,12 @@ return 0; String src = """ struct String { - u8[] cs; + u8[] !cs; int _hashCode; }; // Compare two Strings -val equals = { String self, String s -> +val equals = { !String !self, !String s -> if( self == s ) return true; if( self.cs# != s.cs# ) return false; for( int i=0; i< self.cs#; i++ ) @@ -63,13 +63,13 @@ val equals = { String self, String s -> }; // Return the String hashCode (cached, and never 0) -val hashCode = { String self -> +val hashCode = { !String self -> self._hashCode ? self._hashCode : (self._hashCode = _hashCodeString(self)); }; -val _hashCodeString = { String self -> +val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) hash = hash*31 + self.cs[i]; @@ -256,7 +256,7 @@ return sum;"""); public void testAlloc1() { CodeGen code = new CodeGen( """ -struct S { int a; S? c; }; +struct S { int a; !S? !c; }; return new S;"""); code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); assertEquals("return S;", code.print()); @@ -474,8 +474,8 @@ return sq(arg) + sq(3); @Test public void testFoldedReadBeforeWrites() { var code = new CodeGen(""" struct S { int x; }; - S !a = new S { x=11; }; S !b = new S { x=22; }; - S !p = a; if( arg ) p = b; + !S !a = new S { x=11; }; !S !b = new S { x=22; }; + !S !p = a; if( arg ) p = b; int before = p.x + arg; a.x=33; b.x=44; return before; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java index 937e24e6..d2bf9df6 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -18,7 +18,7 @@ public class Chapter20Test { // A real integer return merged with a synthetic exit. "if(arg) while(1) {} return arg+1;", // TOP must not widen a non-null pointer or constrain a float register. - "struct S { int x; }; S !s=new S; if(arg) while(1) {} return s;", + "struct S { int x; }; !S !s=new S; if(arg) while(1) {} return s;", "if(arg) while(1) {} return 1.5;", // Several synthetic exits into the same return. "if(arg==1) while(1) {} if(arg==2) while(1) {} return arg+3;", @@ -26,7 +26,7 @@ public class Chapter20Test { "while(1) { arg+=1; }", "if(arg) while(1) {} while(1) {}", // Loop-carried memory and scalar self-conflicts exercise spilling. - "struct S { int x; int y; }; S !a=new S; if(arg) while(1) { a.x+=arg; a.y+=a.x; } return a.x+a.y;" + "struct S { int x; int y; }; !S !a=new S; if(arg) while(1) { a.x+=arg; a.y+=a.x; } return a.x+a.y;" }; for( String target : new String[]{"x86_64_v2","riscv","arm"} ) for( String src : sources ) { @@ -47,7 +47,7 @@ public class Chapter20Test { @Test public void testNarrowStoreMasks() { for( String type : new String[]{"i8","u8","i16","u16"} ) { - CodeGen code = new CodeGen("struct S { "+type+" x; }; S !s=new S; s.x=arg; return 0;") + CodeGen code = new CodeGen("struct S { "+type+" x; }; !S !s=new S; s.x=arg; return 0;") .driver(CodeGen.Phase.RegAlloc,"x86_64_v2","SystemV"); int stores=0; for( var bb : code._cfg ) @@ -63,9 +63,9 @@ public class Chapter20Test { @Test public void testInlinedReturnValue() { String src = """ struct S { int x; }; -val f = { S s -> s.x = g(); }; +val f = { !S s -> s.x = g(); }; val g = { -> 123; }; -S !s = new S; +!S !s = new S; return f(s); """; // The entry of g can disappear before its Return is folded into f. @@ -203,11 +203,11 @@ return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 public void testString() { String src = """ struct String { - u8[] cs; + u8[] !cs; int _hashCode; }; -val equals = { String self, String s -> +val equals = { !String !self, !String s -> if( self == s ) return true; if( self.cs# != s.cs# ) return false; for( int i=0; i< self.cs#; i++ ) @@ -216,13 +216,13 @@ val equals = { String self, String s -> return true; }; -val hashCode = { String self -> +val hashCode = { !String self -> self._hashCode ? self._hashCode : (self._hashCode = _hashCodeString(self)); }; -val _hashCodeString = { String self -> +val _hashCodeString = { !String self -> int hash=0; if( self.cs ) { for( int i=0; i< self.cs#; i++ ) @@ -232,12 +232,12 @@ val _hashCodeString = { String self -> return hash; }; -String !s = new String { cs = new u8[17]; }; +!String !s = new String { cs = new u8[17]; }; s.cs[0] = 67; // C s.cs[1] = 108; // l hashCode(s); """; - testTarget(src,"x86_64_v2", "SystemV",9,null); + testTarget(src,"x86_64_v2", "SystemV",0,null); testTarget(src,"riscv" , "SystemV",0,null); testTarget(src,"arm" , "SystemV",0,null); } @@ -351,12 +351,12 @@ return output; """ // based on the top-down version from https://en.wikipedia.org/wiki/Merge_sort -val merge_sort = { int[] a, int[] b, int n -> +val merge_sort = { int[] !a, int[] !b, int n -> copy_array(a, 0, n, b); split_merge(a, 0, n, b); }; -val split_merge = { int[] b, int begin, int end, int[] a -> +val split_merge = { int[] !b, int begin, int end, int[] a -> if (end - begin <= 1) return 0; int middle = (end + begin) / 2; @@ -366,7 +366,7 @@ val split_merge = { int[] b, int begin, int end, int[] a -> return 0; }; -val merge = { int[] b, int begin, int middle, int end, int[] a -> +val merge = { int[] !b, int begin, int middle, int end, int[] a -> int i = begin, j = middle; for (int k = begin; k < end; k++) { @@ -381,7 +381,7 @@ val merge = { int[] b, int begin, int middle, int end, int[] a -> } }; -val copy_array = { int[] a, int begin, int end, int[] b -> +val copy_array = { int[] !a, int begin, int end, int[] b -> for (int k = begin; k < end; k++) b[k] = a[k]; }; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java index 896b9317..9bfb8c3f 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter21Test.java @@ -20,8 +20,8 @@ public class Chapter21Test { @Test public void testReadBeforeConditionalStore() { var code = new CodeGen(""" - struct S { int x; }; S !a=new S; S !b=new S; - a.x=10; b.x=20; S !p=a; if(arg&1) p=b; + struct S { int x; }; !S !a=new S; !S !b=new S; + a.x=10; b.x=20; !S !p=a; if(arg&1) p=b; int sum=0; for(int i=0; i<6; i++) { sum+=a.x; @@ -222,7 +222,7 @@ public class Chapter21Test { @Test public void testNarrowStores() throws IOException { for( String type : new String[]{"i8","u8","i16","u16"} ) { - String src = "struct S { "+type+" x; }; S !s = new S; s.x = arg; return 0;"; + String src = "struct S { "+type+" x; }; !S !s = new S; s.x = arg; return 0;"; CodeGen code = new CodeGen(src).driver("riscv","SystemV",null); int stores=0; for( var bb : code._cfg ) @@ -335,7 +335,7 @@ public class Chapter21Test { } @Test public void testInfinite() { - String src = "struct S { int i; }; S !s = new S; while(1) s.i++;"; + String src = "struct S { int i; }; !S !s = new S; while(1) s.i++;"; testCPU(src,"x86_64_v2", "SystemV",0,"return Top;"); testCPU(src,"riscv" , "SystemV",2,"return Top;"); testCPU(src,"arm" , "SystemV",2,"return Top;"); @@ -365,7 +365,7 @@ return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """ struct S { int f; }; var v0 = new S; -S? v1; +!S? !v1; if (arg) v1 = new S; if (v1) { v0.f = v1.f; @@ -384,12 +384,12 @@ return v0; String src = """ struct String { - u8[] cs; + u8[] !cs; int _hashCode; }; // Compare two Strings -val equals = { String self, String s -> +val equals = { !String !self, !String s -> if( self == s ) return true; if( self.cs# != s.cs# ) return false; for( int i=0; i< self.cs#; i++ ) @@ -399,13 +399,13 @@ val equals = { String self, String s -> }; // Return the String hashCode (cached, and never 0) -val hashCode = { String self -> +val hashCode = { !String self -> self._hashCode ? self._hashCode : (self._hashCode = _hashCodeString(self)); }; -val _hashCodeString = { String self -> +val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) hash = hash*31 + self.cs[i]; @@ -422,12 +422,12 @@ val _hashCodeString = { String self -> String src = """ struct String { - u8[] cs; + u8[] !cs; int _hashCode; }; // Compare two Strings -val equals = { String self, String s -> +val equals = { !String !self, !String s -> if( self == s ) return true; if( self.cs# != s.cs# ) return false; for( int i=0; i< self.cs#; i++ ) @@ -437,13 +437,13 @@ val equals = { String self, String s -> }; // Return the String hashCode (cached, and never 0) -val hashCode = { String self -> +val hashCode = { !String self -> self._hashCode ? self._hashCode : (self._hashCode = _hashCodeString(self)); }; -val _hashCodeString = { String self -> +val _hashCodeString = { !String self -> int hash=0; for( int i=0; i< self.cs#; i++ ) hash = hash*31 + self.cs[i]; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java index cb4b286c..d34b117d 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter22Test.java @@ -180,7 +180,7 @@ public class Chapter22Test { } @Test public void testInfiniteReturn() { - String src = "struct S { int i; }; S !s = new S; while(1) s.i++; return s.i;"; + String src = "struct S { int i; }; !S !s = new S; while(1) s.i++; return s.i;"; testCPU(src,"x86_64_v2","SystemV",0,"return Top;"); testCPU(src,"riscv","SystemV",2,"return Top;"); testCPU(src,"arm","SystemV",2,"return Top;"); @@ -215,7 +215,7 @@ public class Chapter22Test { @Test public void testSextFail() throws IOException { String src = """ struct Person { i32 age;}; -Person !p = new Person; +!Person !p = new Person; p.age = (arg<<17)>>17; return 0; """; @@ -239,7 +239,7 @@ return 0; String src = """ struct Person { i32 age;}; - Person !p = new Person; + !Person !p = new Person; p.age = (arg<<48)>>48; return 0; """; @@ -263,7 +263,7 @@ return 0; String src = """ // Should fold away sign extend struct Person { i8 age;}; -Person !p = new Person; +!Person !p = new Person; p.age = (arg<<48)>>48; return 0; """; @@ -291,7 +291,7 @@ struct Person { i32 age; }; -val fcn = { Person?[] ps, int x -> +val fcn = { !Person?[] !ps, int x -> if( ps[x] ) ps[x].age++; }; @@ -344,12 +344,12 @@ val fcn = { Person?[] ps, int x -> @Test public void testCoRecur() { String src = """ -struct A { B? b; C? c; i64 ax; val az = x*2; }; -struct B { A? a; C? c; f32 bx; val bz = x*3; }; -struct C { A? a; B? b; f64 cx; val cz = x*x; }; -A !aa = new A{ ax=17; }; -B !bb = new B{ bx=3.14; a = aa; }; -C !cc = new C{ cx=2.73; a = aa; b = bb; }; +struct A { !B? !b; !C? !c; i64 ax; val az = x*2; }; +struct B { !A? !a; !C? !c; f32 bx; val bz = x*3; }; +struct C { !A? !a; !B? !b; f64 cx; val cz = x*x; }; +!A !aa = new A{ ax=17; }; +!B !bb = new B{ bx=3.14; a = aa; }; +!C !cc = new C{ cx=2.73; a = aa; b = bb; }; aa.b = bb; aa.c = cc; bb.c = cc; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 118015e0..75e79664 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -62,7 +62,7 @@ public class Chapter23Test { public void testOrRhsLoopMemory() throws IOException { checkOrRhsLoop(""" struct S { int f; }; - S !s = new S; + !S !s = new S; int result = (arg & 1) || (new S { while (s.f < 3) s.f++; s.f++; @@ -178,13 +178,13 @@ var apply = { i64 x, { i64 -> u32 } fcn -> // Todo: have one src here String src = """ - struct S { S? fld; }; + struct S { !S? !fld; }; val ptr = arg == 1 ? null : new S{fld = arg==1 ? null : new S{fld = null;};}; return ptr && ptr.fld ? "true" : "false"; """; String src2 = """ - struct S { S? fld; }; + struct S { !S? !fld; }; val ptr = arg == 1 ? null : new S{fld = arg==1 ? null : new S{fld = null;};}; if( ptr && ptr.fld ) { @@ -341,21 +341,21 @@ var apply = { i64 x, { i64 -> u32 } fcn -> // A hypothetical scanner class struct Scan { int !x; - u8[~] buf; + u8[~] !buf; // Skip whitespace - val skip = { Scan s -> + val skip = { !Scan s -> while( s.buf[s.x] <= ' ' ) s.x++; }; // Peek a character; if matched consume it, else false. - val peek = { Scan s, u8 c -> + val peek = { !Scan !s, u8 c -> skip(s); if( s.buf[s.x] != c ) return false; s.x++; return true; }; }; -Scan !s = new Scan{ buf = " q"; }; +!Scan !s = new Scan{ buf = " q"; }; return Scan.peek(s,'q'); """; @@ -372,7 +372,7 @@ return Scan.peek(s,'q'); // A hypothetical scanner class struct Scan { int !x; - u8[~] buf; + u8[~] !buf; // Skip whitespace val skip = { -> while( buf[x] <= ' ' ) @@ -380,12 +380,12 @@ struct Scan { return self; }; }; -val s = new Scan{ buf = " q"; }; +~Scan s = new Scan{ buf = " q"; }; return s.skip().x; """; try { new CodeGen(src).parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Argument #0 isa *Scan {i64 x; *[]u8 buf; { *Scan -> *Scan {i64 !x; *[]u8 buf; {21} skip; } #21} skip; }, but must be a *Scan {i64 !x; *[]u8 buf; ... }",e.getMessage()); } + catch( Exception e ) { org.junit.Assert.assertTrue(e.getMessage().startsWith("Argument #0 isa")); } }; @@ -396,7 +396,7 @@ return s.skip().x; // A hypothetical scanner class struct Scan { int !x; - u8[~] buf; + u8[~] !buf; // Skip whitespace val skip = { -> while( buf[x] <= ' ' ) @@ -407,7 +407,7 @@ struct Scan { buf[x++]==ch; }; }; -Scan !s = new Scan{ buf = " [1,2]"; }; +!Scan !s = new Scan{ buf = " [1,2]"; }; return s.require('['); """; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java index 82bfd31f..3a2a957f 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/Chapter24Test.java @@ -123,13 +123,13 @@ return 0; // Todo: have one src here String src = """ -struct S { S? fld; }; +struct S { !S? !fld; }; val ptr = arg == 1 ? null : new S{fld = arg==1 ? null : new S{fld = null;};}; return ptr && ptr.fld ? "true" : "false"; """; String src2 = """ -struct S { S? fld; }; +struct S { !S? !fld; }; val ptr = arg == 1 ? null : new S{fld = arg==1 ? null : new S{fld = null;};}; if( ptr && ptr.fld ) { @@ -603,21 +603,21 @@ return 0 < arg < arg+1 < 4; // A hypothetical scanner class struct Scan { int !x; - u8[~] buf; + u8[~] !buf; // Skip whitespace - val skip = { Scan s -> + val skip = { !Scan s -> while( s.buf[s.x] <= ' ' ) s.x++; }; // Peek a character; if matched consume it, else false. - val peek = { Scan s, u8 c -> + val peek = { !Scan !s, u8 c -> skip(s); if( s.buf[s.x] != c ) return false; s.x++; return true; }; }; -Scan !s = new Scan{ buf = " q"; }; +!Scan !s = new Scan{ buf = " q"; }; return Scan.peek(s,'q'); """; @@ -634,7 +634,7 @@ return Scan.peek(s,'q'); // A hypothetical scanner class struct Scan { int !x; - u8[~] buf; + u8[~] !buf; // Skip whitespace val skip = { -> while( buf[x] <= ' ' ) @@ -642,12 +642,12 @@ struct Scan { return self; }; }; -val s = new Scan{ buf = " q"; }; +~Scan s = new Scan{ buf = " q"; }; return s.skip().x; """; try { new CodeGen(src).parse().opto().typeCheck(); fail(); } - catch( Exception e ) { assertEquals("Argument #0 isa *Scan {i64 x; *[]u8 buf; { *Scan -> *Scan {i64 !x; *[]u8 buf; {21} skip; } #21} skip; }, but must be a *Scan {i64 !x; *[]u8 buf; ... }",e.getMessage()); } + catch( Exception e ) { org.junit.Assert.assertTrue(e.getMessage().startsWith("Argument #0 isa")); } }; @@ -658,7 +658,7 @@ return s.skip().x; // A hypothetical scanner class struct Scan { int !x; - u8[~] buf; + u8[~] !buf; // Skip whitespace val skip = { -> while( buf[x] <= ' ' ) @@ -669,7 +669,7 @@ struct Scan { buf[x++]==ch; }; }; -Scan !s = new Scan{ buf = " [1,2]"; }; +!Scan !s = new Scan{ buf = " [1,2]"; }; return s.require('['); """; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java b/chapter24/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java index 0d67d3c5..48f739cf 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/CompoundAssignmentTest.java @@ -73,7 +73,7 @@ public class CompoundAssignmentTest { @Test public void testFields() { for (String op : OPS) { long expected = apply(op, -8, 3); - check("struct S { int x; }; S !s=new S; s.x=arg; int r=(s.x " + + check("struct S { int x; }; !S !s=new S; s.x=arg; int r=(s.x " + op + " 3); return s.x*10+r;", -8, expected*11); } } diff --git a/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java b/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java index e83e3c0e..8e19426c 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/MemoryEncodingTest.java @@ -32,8 +32,8 @@ public class MemoryEncodingTest { """, // One possibly aliasing arm must reject the unchanged-memory proof. """ - struct S { int x; }; S !a=new S; S !b=new S; - a.x=10; b.x=20; S !p=a; if(arg&1) p=b; + struct S { int x; }; !S !a=new S; !S !b=new S; + a.x=10; b.x=20; !S !p=a; if(arg&1) p=b; int sum=0; for(int i=0; i<6; i++) { if(i==2) p.x=30; @@ -44,8 +44,8 @@ public class MemoryEncodingTest { """, // Unchanged memory does not imply an unchanged loop-carried pointer. """ - struct S { int x; }; S !a=new S; S !b=new S; - a.x=10; b.x=20; S !p=a; int sum=0; + struct S { int x; }; !S !a=new S; !S !b=new S; + a.x=10; b.x=20; !S !p=a; int sum=0; for(int i=0; i<6; i++) { if(i==2) a.x=30; sum+=p.x; @@ -55,7 +55,7 @@ public class MemoryEncodingTest { """, // All arms fold, but their values differ: build a value Phi. """ - struct S { int x; }; S !a=new S; a.x=1; int sum=0; + struct S { int x; }; !S !a=new S; a.x=1; int sum=0; for(int i=0; i<6; i++) { sum+=a.x; if(i&1) a.x=2; @@ -145,7 +145,7 @@ public class MemoryEncodingTest { for( String target : new String[]{"x86_64_v2","riscv","arm"} ) { CodeGen code = new CodeGen(""" struct S { int x; int y; }; - S !a=new S; + !S !a=new S; if( arg ) while( 1 ) { a.x+=arg; a.y+=a.x; } return a.x+a.y; """).driver(CodeGen.Phase.LoopTree); diff --git a/chapter24/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/chapter24/src/test/java/com/seaofnodes/simple/MergeSortTest.java index 55ef5821..453bd35c 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/MergeSortTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -24,7 +24,7 @@ public class MergeSortTest { split_merge(a, 0, a#, b); }; - val split_merge = { int[] b, int begin, int end, int[] a -> + val split_merge = { int[] !b, int begin, int end, int[] a -> if (end - begin <= 1) return 0; int middle = (end + begin) / 2; @@ -34,7 +34,7 @@ public class MergeSortTest { return 0; }; - val merge = { int[] b, int begin, int middle, int end, int[] a -> + val merge = { int[] !b, int begin, int middle, int end, int[] a -> int i = begin, j = middle; for (int k = begin; k < end; k++) { @@ -49,7 +49,7 @@ public class MergeSortTest { } }; - val copy_array = { int[] a, int begin, int end, int[] b -> + val copy_array = { int[] !a, int begin, int end, int[] b -> for (int k = begin; k < end; k++) b[k] = a[k]; }; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/MutabilityTest.java b/chapter24/src/test/java/com/seaofnodes/simple/MutabilityTest.java new file mode 100644 index 00000000..7ae80314 --- /dev/null +++ b/chapter24/src/test/java/com/seaofnodes/simple/MutabilityTest.java @@ -0,0 +1,73 @@ +package com.seaofnodes.simple; + +import org.junit.Test; +import static org.junit.Assert.*; +import com.seaofnodes.simple.codegen.CodeGen; + +public class MutabilityTest { + private static void ok(String src, String result) { + var code = new CodeGen(src).parse().opto().typeCheck(); + assertEquals(result,Eval2.eval(code,0)); + } + private static void bad(String src) { + try { + new CodeGen(src).parse().opto().typeCheck(); + } catch( RuntimeException expected ) { + String msg = expected.getMessage(); + assertTrue("Expected a permission error, got: "+expected, + msg!=null && (msg.contains("final") || msg.contains("not of declared type") || msg.contains("Cannot store") || msg.contains("Argument #"))); + return; + } + fail("Accepted forbidden write: "+src); + } + + @Test public void testIndependentBindingsAndViews() { + ok("struct P { int x; }; !P ~p=new P; p.x=7; return p.x;", "7"); + ok("struct P { int x; }; ~P !p=new P{x=3;}; p=new P{x=7;}; return p.x;", "7"); + bad("struct P { int x; }; !P ~p=new P; p=new P; return 0;"); + bad("struct P { int x; }; ~P !p=new P; p.x=7; return 0;"); + bad("int ~x=3; x=7; return x;"); + ok("int !x=3; x=7; return x;", "7"); + } + + @Test public void testDeepViewAndAliases() { + ok("struct P { int x; }; !P ~p=new P; ~P ~r=p; p.x=7; return r.x;", "7"); + bad("struct P { int x; }; struct Box { !P p; }; !P q=new P; Box b=new Box{p=q;}; b.p.x=7; return 0;"); + bad("struct P { int x; }; P p=new P; !P q=p; q.x=7; return 0;"); + bad("struct P { P? next; int x; }; !P p=new P{next=new P;}; p.next.x=7; return 0;"); + bad("struct P { !P? next; int x; }; P p=new P{next=new P;}; p.next.x=7; return 0;"); + } + + @Test public void testInferencePreservesAccess() { + ok("struct P { int x; }; val p=new P; p.x=7; return p.x;", "7"); + bad("struct P { int x; }; val p=new P; p=new P; return 0;"); + bad("struct P { int x; }; P p=new P; var q=p; q.x=7; return 0;"); + } + + @Test public void testParameterPermissions() { + ok("struct P { int x; }; val f={ !P p -> p.x=7; return p.x; }; return f(new P);", "7"); + ok("val f={ int ~x -> return x; }; return f(7);", "7"); + bad("val f={ int ~x -> x=7; return x; }; return f(3);"); + bad("struct P { int x; }; val f={ P p -> p.x=7; return p.x; }; return f(new P);"); + bad("struct P { int x; }; val f={ !P p -> p.x=7; return p.x; }; P p=new P; return f(p);"); + bad("struct P { int x; }; val f={ P?[] a -> return a#; }; !P?[] a=new !P?[1]; return f(a);"); + } + + @Test public void testConstructorScope() { + ok("struct P { int ~x; }; P p=new P{if(arg) x=3; else x=7;}; return p.x;", "7"); + bad("int ~outer=1; struct P { int x; }; P p=new P{outer=7;}; return outer;"); + bad("struct P { int x; }; P p=new P{int ~local=1; local=7;}; return p.x;"); + } + + @Test public void testArrayLayers() { + bad("struct P { int x; }; !P?[] rw=new !P?[1]; P?[] ro=rw; rw[0]=new P; ro[0].x=7; return 0;"); + ok("u8[] a=new u8[2]; a[0]=7; return a[0];", "7"); + ok("struct P { int x; }; P?[] a=new P?[1]; a[0]=new P{x=7;}; return a[0].x;", "7"); + bad("struct P { int x; }; P?[] a=new P?[1]; a[0]=new P; a[0].x=7; return 0;"); + ok("struct P { int x; }; !P?[] a=new !P?[1]; a[0]=new P; a[0].x=7; return a[0].x;", "7"); + bad("u8[~] a=new u8[1]; a[0]=7; return 0;"); + ok("u8[~]?[] rows=new u8[~]?[1]; rows[0]=new u8[1]; return rows#;", "1"); + bad("u8[~]?[] rows=new u8[~]?[1]; rows[0]=new u8[1]; rows[0][0]=7; return 0;"); + bad("u8[]?[~] rows=new u8[]?[1]; rows[0]=new u8[1]; return 0;"); + } +} diff --git a/chapter24/src/test/java/com/seaofnodes/simple/SchedulerTest.java b/chapter24/src/test/java/com/seaofnodes/simple/SchedulerTest.java index ca29bf84..3b19857a 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/SchedulerTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/SchedulerTest.java @@ -25,7 +25,7 @@ public class SchedulerTest { struct S { int f; } -S !v=new S; +!S !v=new S; v.f = 2; int i=v.f; if (arg) v.f=1; @@ -42,7 +42,7 @@ return i; struct S { int f; }; -S !v0=new S; +!S !v0=new S; if(arg) v0.f=1; return v0; """); @@ -58,7 +58,7 @@ return v0; struct S { int f; }; -S !v=new S; +!S !v=new S; v.f = 2; int i=new S.f; i=v.f; diff --git a/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java index ba7d2a1e..fd3fea9d 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -96,13 +96,13 @@ public class TypeTest { Assert.assertNotEquals(ptr1, ptr2); Type p1glb = ptr1.glb(false); Assert.assertNotEquals(ptr1, p1glb ); - Type p1nro = ptr1nil.makeRO(); - Assert.assertEquals(p1nro, p1glb); + Assert.assertTrue(((TypeMemPtr)p1glb)._ro); + Assert.assertTrue(ptr1nil.isa(p1glb)); Assert.assertEquals(ptr1, ptr1.dual().dual()); Assert.assertTrue(p1glb.makeRO().isa( ptr1.dual().glb(false))); - Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT), ptr1.meet(ptr2nil)); - Assert.assertEquals(p1glb, ptr1.meet(TypeNil.NIL).makeRO()); + Assert.assertEquals(TypeMemPtr.makeNullable(TypeStruct.BOT).withAccess(false), ptr1.meet(ptr2nil)); + Assert.assertEquals(ptr1nil, ptr1.meet(TypeNil.NIL)); TypeMemPtr TOP = TypeMemPtr.TOP; TypeMemPtr BOT = TypeMemPtr.makeNullable(TypeStruct.BOT); @@ -111,7 +111,7 @@ public class TypeTest { Type PTR_meet_NULL = NULL.meet(PTR); Assert.assertEquals(BOT, PTR_meet_NULL); Type ptr1_meet_ptr2 = ptr1.meet(ptr2); - Assert.assertEquals(PTR, ptr1_meet_ptr2); + Assert.assertEquals(PTR.withAccess(false), ptr1_meet_ptr2); Type NULL_join_ptr1 = NULL.join(ptr1); Assert.assertEquals(TypePtr.XNPTR, NULL_join_ptr1); Type NULL_join_PTR = PTR.join(NULL); diff --git a/chapter24/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter24/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index dde5a1dc..20815d5d 100644 --- a/chapter24/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter24/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -452,7 +452,7 @@ public class ScriptGenerator { for (int i=0; i