From 17f9d743c06170f20773863bd1eca4f25ef41490 Mon Sep 17 00:00:00 2001 From: Dibyendu Majumdar Date: Tue, 23 Apr 2024 17:23:16 +0100 Subject: Ch10 (#74) * Chapter 10 start * #67 language grammar for chapter 10 * #67 Fix chapter title * #67 Fix typo * #67 assignment to fields * #67 Struct var decl must be initialized * #67 Start to describe memory and aliasing * #67 revision * #67 Start to describe how we construct the graph * #67 Start to describe how we construct the graph * #67 Start to describe how we construct the graph * #67 Parse struct declaration * #67 WIP parse expressions and statements involving struct vars * #67 WIP parse store expressions * #67 WIP parse load expressions * #67 WIP first go at adding aliases and memslices * #67 WIP A store should get bound to the $mem alias replacing previous node * #67 WIP Add MergeMem node * Update script generator to new features (#68) * #67 WIP Drop MergeMem node * #67 WIP Drop MergeMem node * #67 WIP Improve parsing of postfix expressions * #67 WIP Improve parsing of postfix expressions * #67 WIP Update xmeet - these types can only meet another of the same type * #67 WIP Phi's compute should return input type if input is a MemPtr even if region is in progress because parser needs the correct type * #67 WIP If a null meets a non-null ptr then non-null wins; but ideally we want to retain type of null so we do not have this problem * #67 WIP If a null meets a non-null ptr then non-null then the result is type|null * #67 WIP Fix TypeMemPtr.eq() and also intern struct types * #67 WIP Add missing hash and eq implementations Also refactor common code to get field from ptr * #67 Add START as input to New (as proxy for Mem). Other minor adjustments * #67 Phis widen type inside a loop during parse * #67 Fix redeclaration bug * #67 Small refactor * #67 Add an LLVM inspired IR printer based on post by Yasser A * #67 Add instructions to initialize fields of a struct after a new * #67 Make New's ctrl input the current ctrl rather than Start * #67 Refactor to make it cleaner * #67 Fix bug - interned types should be cleared * #67 Fix bug - new node must be kept so that its not prematurely killed * #67 Fix bug - we must do a depp comparison of structs because types get interned and we can't easily clear the interned types across runs, this means we can end up with structs retaining definitions from older runs. * #67 Refactor * #67 When we compute type of a Phi we must stay within the domain of the Phi, Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. To ensure this we need to default to the GLB of the first input * #67 When we compute type of a Phi we must stay within the domain of the Phi, Example Int stays Int, Ptr stays Ptr, Control stays Control, Mem stays Mem. To ensure this we need to default to the GLB of the first input * #67 Tidy up printing and add expected result on tests * #67 Refactor TypeStruct * #67 Refactor TypeStruct When printing IR in new format - show the projection index * #67 Revise the lattice for ptr types to make it more complete * #67 Revise the lattice for mem and struct types. Add initial test * #67 Refactor how we compute phi type * #67 Refactor how we compute phi type * #67 Use the generated graph but an edge is missing in the graph - to be investigated * #67 One more tweek * Partial work on ch10, some tests busted Revamp Types Mem, MemPtr, Struct, FIeld. Add tests to enforce theoretical rules properties., Add parsing "?" to allow nullable types. Enhance GraphViz to show off mem better. Strip trailing WS in many files. * Strip trailing WS * Post-peephole errors Some nicer error reporting for types. Mem Projs following StartNode are indexed by alias, but may have "holes" in the set of projs. * WS cleanup * Simplify TMP dual Add more test type Rename test type so makefile picks it up Failing 1 test * Scopes and Phis track declared type ...not the initial type. * A fuzzer found bug * Some changes on the fuzzer and maybe faster reducer (#69) * WS and printing changes * Kotlin style null checks (partial) Allow `ptr=rand?; if( ptr ) ptr.field` where the if-test upcasts the ptr to not-null. Field assignments are expressions not statements: `if( (ptr.fld=rez) !=null ) .... ` Many WS changes. * missed cleanup * Fuzzer update (#71) * Update script generator * Fix script generator * Reset type cache to prevent alias blowup (#70) * Reset type cache to prevent alias blowup * Remove the default intern Just reset the UNIQUE_ALIAS number. Intern table doesn't care, that's the whole point of the intern table. Passes existing tests, but fuzzer finds some new stuff * Fix a few of the fuzzer bugs More to come * Fix one more fuzzer bug --------- Co-authored-by: Cliff Click * Fix script generated generating invalid code * Greatly simplify Cast usage Casts peephole normally. Added needed Phi optimizations to remove excess casts. Fuzzer bug fixes: Need a plain kill unused on worklist. MemOp error handles aTOP/BOT input. * #67 Add description of lattice to the doc Update grammar - add the '?' nullable syntax Rename VOID to PTR * #67 Some renames * #67 some more text re lattice * #67 Fix the alias ID start to 2 * #67 Revise lattice diagram and doc * #67 Start describing the parser changes and Null Pointer analysis * #67 Draw lattice diagram using graphviz * #67 Revisions to text * #67 Improve description of alias classes * #67 Some renames to make code clearer * #67 Describe null pointer analysis * Fix script generated generating invalid code (#72) * updates to readme shorter example names to make a nicer graph * #67 Revise top level README * #67 Revise top level README --------- Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Cliff Click Co-authored-by: XmiliaH --- .../java/com/seaofnodes/simple/Chapter01Test.java | 50 ++ .../java/com/seaofnodes/simple/Chapter02Test.java | 99 +++ .../java/com/seaofnodes/simple/Chapter03Test.java | 70 ++ .../java/com/seaofnodes/simple/Chapter04Test.java | 130 ++++ .../java/com/seaofnodes/simple/Chapter05Test.java | 225 ++++++ .../java/com/seaofnodes/simple/Chapter06Test.java | 296 ++++++++ .../java/com/seaofnodes/simple/Chapter07Test.java | 243 +++++++ .../java/com/seaofnodes/simple/Chapter08Test.java | 211 ++++++ .../java/com/seaofnodes/simple/Chapter09Test.java | 300 ++++++++ .../java/com/seaofnodes/simple/Chapter10Test.java | 363 ++++++++++ .../java/com/seaofnodes/simple/FuzzerWrap.java | 35 + .../test/java/com/seaofnodes/simple/TypeTest.java | 145 ++++ .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 173 +++++ .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 140 ++++ .../java/com/seaofnodes/simple/fuzzer/Reducer.java | 176 +++++ .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 792 +++++++++++++++++++++ 16 files changed, 3448 insertions(+) create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/Chapter05Test.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/Chapter06Test.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/Chapter07Test.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/Chapter08Test.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/FuzzerWrap.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/TypeTest.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java create mode 100644 chapter10/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java (limited to 'chapter10/src/test/java') diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java new file mode 100644 index 00000000..48cc716f --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -0,0 +1,50 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter01Test { + + @Test + public void testSimpleProgram() { + Parser parser = new Parser("return 1;"); + StopNode stop = parser.parse(); + StartNode start = Parser.START; + ReturnNode ret = (ReturnNode)stop.in(0); + + assertTrue(ret.ctrl() instanceof ProjNode); + Node expr = ret.expr(); + if( expr instanceof ConstantNode con ) { + assertEquals(start,con.in(0)); + assertEquals(TypeInteger.constant(1), con._type); + } else { + fail(); + } + } + + @Test + public void testZero() { + Parser parser = new Parser("return 0;"); + parser.parse(); + StartNode start = Parser.START; + for( Node use : start._outputs ) + if( use instanceof ConstantNode con && con._type instanceof TypeInteger ) + assertEquals(TypeInteger.constant(0),con._type); + } + + + @Test + public void testBad2() { + try { + new Parser("return 0123;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error: integer values cannot start with '0'",e.getMessage()); + } + } +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java new file mode 100644 index 00000000..351cdb16 --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -0,0 +1,99 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter02Test { + + @Test + public void testParseGrammar() { + Parser parser = new Parser("return 1+2*3+-5;"); + Node._disablePeephole = true; // disable peephole so we can observe full graph + StopNode ret = parser.parse(); + assertEquals("return ((1+(2*3))+(-5));", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + Node._disablePeephole = false; + } + + @Test + public void testAddPeephole() { + Parser parser = new Parser("return 1+2;"); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testSubPeephole() { + Parser parser = new Parser("return 1-2;"); + StopNode ret = parser.parse(); + assertEquals("return -1;", ret.print()); + } + + @Test + public void testMulPeephole() { + Parser parser = new Parser("return 2*3;"); + StopNode ret = parser.parse(); + assertEquals("return 6;", ret.print()); + } + + @Test + public void testDivPeephole() { + Parser parser = new Parser("return 6/3;"); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testMinusPeephole() { + Parser parser = new Parser("return 6/-3;"); + StopNode ret = parser.parse(); + assertEquals("return -2;", ret.print()); + } + + @Test + public void testExample() { + Parser parser = new Parser("return 1+2*3+-5;"); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + GraphVisualizer gv = new GraphVisualizer(); + System.out.println(gv.generateDotOutput(parser)); + } + + @Test + public void testBad1() { + try { + new Parser("ret").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'ret'",e.getMessage()); + } + } + @Test + public void testNotBad3() { + // this test used to fail in chapter 1 + assertEquals("return 12;", new Parser("return --12;").parse().print()); + } + + @Test + public void testBad4() { + try { + new Parser("return 100").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected ;: ",e.getMessage()); + } + } + + @Test + public void testNotBad5() { + // this test used to fail in chapter 1 + assertEquals("return -100;", new Parser("return -100;").parse().print()); + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java new file mode 100644 index 00000000..8a11107d --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -0,0 +1,70 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter03Test { + + @Test + public void testVarDecl() { + Parser parser = new Parser("int a=1; return a;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testVarAdd() { + Parser parser = new Parser("int a=1; int b=2; return a+b;"); + StopNode ret = parser.parse(); + assertEquals("return 3;", ret.print()); + } + + @Test + public void testVarScope() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; } return c;"); + StopNode ret = parser.parse(); + assertEquals("return 4;", ret.print()); + } + + @Test + public void testVarScopeNoPeephole() { + Parser parser = new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b; #showGraph; } return c; #showGraph;"); + Node._disablePeephole = true; + StopNode ret = parser.parse(); + Node._disablePeephole = false; + assertEquals("return (1+3);", ret.print()); + } + + @Test + public void testVarDist() { + Parser parser = new Parser("int x0=1; int y0=2; int x1=3; int y1=4; return (x0-x1)*(x0-x1) + (y0-y1)*(y0-y1); #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 8;", ret.print()); + } + + @Test + public void testSelfAssign() { + try { + new Parser("int a=a; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'a'",e.getMessage()); + } + } + + @Test + public void testBad6() { + try { + new Parser("int a=1; int b=2; int c=0; { int b=3; c=a+b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected }: ",e.getMessage()); + } + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java new file mode 100644 index 00000000..ffbbe9a8 --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -0,0 +1,130 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter04Test { + + @Test + public void testPeephole() { + Parser parser = new Parser("return 1+arg+2; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testPeephole2() { + Parser parser = new Parser("return (1+arg)+2;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testAdd0() { + Parser parser = new Parser("return 0+arg;"); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testAddAddMul() { + Parser parser = new Parser("return arg+0+arg;"); + StopNode ret = parser.parse(); + assertEquals("return (arg*2);", ret.print()); + } + + @Test + public void testPeephole3() { + Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return ((arg*2)+6);", ret.print()); + } + + @Test + public void testMul1() { + Parser parser = new Parser("return 1*arg;"); + StopNode ret = parser.parse(); + assertEquals("return arg;", ret.print()); + } + + @Test + public void testVarArg() { + Parser parser = new Parser("return arg; #showGraph;"); + StopNode stop = parser.parse(); + ReturnNode ret = stop.ret(); + assertTrue(ret.in(0) instanceof ProjNode); + assertTrue(ret.in(1) instanceof ProjNode); + } + + @Test + public void testConstantArg() { + Parser parser = new Parser("return arg; #showGraph;", TypeInteger.constant(2)); + StopNode ret = parser.parse(); + assertEquals("return 2;", ret.print()); + } + + @Test + public void testCompEq() { + Parser parser = new Parser("return 3==3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testCompEq2() { + Parser parser = new Parser("return 3==4; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq() { + Parser parser = new Parser("return 3!=3; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 0;", ret.print()); + } + + @Test + public void testCompNEq2() { + Parser parser = new Parser("return 3!=4; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return 1;", ret.print()); + } + + @Test + public void testBug1() { + Parser parser = new Parser("int a=arg+1; int b=a; b=1; return a+2; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+3);", ret.print()); + } + + @Test + public void testBug2() { + Parser parser = new Parser("int a=arg+1; a=a; return a; #showGraph;"); + StopNode ret = parser.parse(); + assertEquals("return (arg+1);", ret.print()); + } + + @Test + public void testBug3() { + try { + new Parser("inta=1; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'inta'",e.getMessage()); + } + } + + @Test + public void testBug4() { + Parser parser = new Parser("return -arg;"); + StopNode ret = parser.parse(); + assertEquals("return (-arg);", ret.print()); + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter05Test.java new file mode 100644 index 00000000..e82aa7da --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -0,0 +1,225 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter05Test { + + @Test + public void testIfStmt() { + Parser parser = new Parser( +""" +int a = 1; +if (arg == 1) + a = arg+2; +else { + a = arg-3; + #showGraph; +} +#showGraph; +return a;"""); + StopNode ret = parser.parse().iterate(true); + assertEquals("return Phi(Region18,(arg+2),(arg-3));", ret.toString()); + } + + @Test + public void testTest() { + Parser parser = new Parser( +""" +int c = 3; +int b = 2; +if (arg == 1) { + b = 3; + c = 4; +} +return c;""", TypeInteger.BOT); + StopNode ret = parser.parse().iterate(true); + assertEquals("return Phi(Region16,4,3);", ret.toString()); + } + + @Test + public void testReturn2() { + Parser parser = new Parser( +""" +if( arg==1 ) + return 3; +else + return 4; +#showGraph;""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("Stop[ return 3; return 4; ]", stop.toString()); + } + + @Test + public void testIfMergeB() { + Parser parser = new Parser( +""" +int a=arg+1; +int b=0; +if( arg==1 ) + b=a; +else + b=a+1; +return a+b;"""); + StopNode ret = parser.parse().iterate(true); + assertEquals("return ((arg*2)+Phi(Region21,2,3));", ret.toString()); + } + + @Test + public void testIfMerge2() { + Parser parser = new Parser( +""" +int a=arg+1; +int b=arg+2; +if( arg==1 ) + b=b+a; +else + a=b+1; +return a+b;"""); + StopNode ret = parser.parse().iterate(true); + assertEquals("return ((Phi(Region32,(arg*2),arg)+arg)+Phi(Region,4,5));", ret.toString()); + } + + @Test + public void testMerge3() { + Parser parser = new Parser( +""" +int a=1; +if( arg==1 ) + if( arg==2 ) + a=2; + else + a=3; +else if( arg==3 ) + a=4; +else + a=5; +return a; +#showGraph;""", TypeInteger.BOT); + StopNode stop = parser.parse().iterate(); + assertEquals("return Phi(Region36,Phi(Region22,2,3),Phi(Region34,4,5));", stop.toString()); + } + + @Test + public void testMerge4() { + Parser parser = new Parser( +""" +int a=0; +int b=0; +if( arg ) + a=1; +if( arg==0 ) + b=2; +return arg+a+b; +#showGraph;""", TypeInteger.BOT); + StopNode stop = parser.parse(); + assertEquals("return ((arg+Phi(Region13,1,0))+Phi(Region28,2,0));", stop.toString()); + } + + @Test + public void testMerge5() { + Parser parser = new Parser( +""" +int a=arg==2; +if( arg==1 ) +{ + a=arg==3; +} +return a;"""); + StopNode ret = parser.parse().iterate(); + assertEquals("return (arg==Phi(Region16,3,2));", ret.toString()); + } + + @Test + public void testTrue() { + StopNode stop = new Parser("return true;").parse(); + assertEquals("return 1;",stop.toString()); + } + + @Test + public void testHalfDef() { + try { + new Parser("if( arg==1 ) int b=2; return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + @Test + public void testHalfDef2() { + try { + new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'b'",e.getMessage()); + } + } + + @Test + public void testRegress1() { + try { + new Parser("if(arg==2) int a=1; else int b=2; return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Cannot define a new name on one arm of an if",e.getMessage()); + } + } + + + @Test + public void testBadNum() { + try { + new Parser("return 1-;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); + } + } + + @Test + public void testKeyword1() { + try { + new Parser("int true=0; return true;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'true'",e.getMessage()); + } + } + + @Test + public void testKeyword2() { + try { + new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Expected an identifier, found 'else'",e.getMessage()); + } + } + + @Test + public void testKeyword3() { + try { + new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Undefined name 'ififif'",e.getMessage()); + } + } + + @Test + public void testBad7() { + try { + new Parser("return 1;}").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("Syntax error, unexpected }",e.getMessage()); + } + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter06Test.java new file mode 100644 index 00000000..6c24992c --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -0,0 +1,296 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter06Test { + + @Test + public void testPeepholeReturn() { + Parser parser = new Parser( +""" +if( true ) return 2; +return 1; +"""); + StopNode stop = parser.parse().iterate(true); + assertEquals("return 2;", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode); + } + + @Test + public void testPeepholeRotate() { + Parser parser = new Parser( +""" +int a = 1; +if (arg) + a = 2; +return (arg < a) < 3; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return ((arg 4 ) + break; +} +return arg; + """); + StopNode stop = parser.parse().iterate(true); + assertEquals("return arg;", stop.toString()); + System.out.println(IRPrinter.prettyPrint(stop,99)); + } + + @Test + public void testRegress2() { + Parser parser = new Parser("if(1) return 0; else while(arg>--arg) arg=arg+1; return 0;"); + StopNode stop = parser.parse().iterate(true); + assertEquals("return 0;", stop.toString()); + } + + @Test + public void testBreakOutsideLoop() { + try { + new Parser(""" +if(arg <= 10) { + break; + arg = arg + 1; +} +return arg; +""").parse(); + fail(); + } catch( RuntimeException e ) { + assertEquals("No active loop for a break or continue",e.getMessage()); + } + } + + @Test + public void testRegress3() { + Parser parser = new Parser(""" +while(arg < 10) { + break; +} +return arg; +"""); + StopNode stop = parser.parse().iterate(true); + assertEquals("return arg;", stop.toString()); + } + + @Test + public void testRegress4() { + Parser parser = new Parser(""" +int a = 1; +while(arg < 10) { + a = a + 1; + if (arg > 2) { + int a = 17; + break; + } +} +return a; +"""); + StopNode stop = parser.parse().iterate(true); + assertEquals("return Phi(Region28,Phi(Loop7,1,(Phi_a+1)),Add);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof RegionNode); + } + + @Test + public void testRegress5() { + Parser parser = new Parser(""" +int a = 1; +while(1) { + a = a + 1; + if (a<10) continue; + break; +} +return a; +"""); + StopNode stop = parser.parse().iterate(true); + assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString()); + assertTrue(stop.ret().ctrl() instanceof ProjNode prj && prj._idx==1 ); + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java new file mode 100644 index 00000000..8e198218 --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -0,0 +1,300 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeInteger; +import org.junit.Assert; +import org.junit.BeforeClass; +import org.junit.Test; +import org.junit.Ignore; + +import static org.junit.Assert.*; + +public class Chapter09Test { + + @Test + @Ignore + public void testJig() { + Parser parser = new Parser(""" +int v0=0; +arg=0; +while(v0) { + while(1) if(arg*arg*0==0) {} + while(0) {} + arg=1; +} +return 0; + """); + StopNode stop = parser.parse().iterate(true); + } + + @Test + public void testGVN1() { + Parser parser = new Parser( + """ +int x = arg + arg; +if(arg < 10) { + return arg + arg; +} +else { + x = x + 1; +} +return x; + """); + StopNode stop = parser.parse(true); + assertEquals("Stop[ return (arg*2); return (Mul+1); ]", stop.toString()); + Assert.assertEquals(2, GraphEvaluator.evaluate(stop, 1)); + Assert.assertEquals(23, GraphEvaluator.evaluate(stop, 11)); + } + + @Test + public void testGVN2() { + Parser parser = new Parser( + """ +return arg*arg-arg*arg; + """); + StopNode stop = parser.parse(true); + assertEquals("return 0;", stop.toString()); + Assert.assertEquals(0, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist1() { + Parser parser = new Parser( + """ +int step = 1; +while (arg < 10) { + arg = arg + step + 1; +} +return arg; + """); + StopNode stop = parser.parse(true).iterate(true); + assertEquals("return Phi(Loop7,arg,(Phi_arg+2));", stop.toString()); + Assert.assertEquals(11, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist2() { + Parser parser = new Parser( + """ +int cond = 0; +int one = 1; +while (arg < 10) { + if (cond) one = 2; + arg = arg + one*3 + 1; +} +return arg; + """); + StopNode stop = parser.parse(true).iterate(true); + assertEquals("return Phi(Loop8,arg,(Phi_arg+4));", stop.toString()); + Assert.assertEquals(13, GraphEvaluator.evaluate(stop, 1)); + } + + @Test + public void testWorklist3() { + Parser parser = new Parser( + """ +int v1 = 0; +int v2 = 0; +int v3 = 0; +int v4 = 0; +int v5 = 0; +int v6 = 0; +int v7 = 0; +int v8 = 0; +while (arg) { + if (v1) v2 = 1; + if (v2) v3 = 1; + if (v3) v4 = 1; + if (v4) v5 = 1; + if (v5) v6 = 1; + if (v6) v7 = 1; + if (v7) v8 = 1; + arg = arg + v8 + 1; +} +return arg; + """); + StopNode stop = parser.parse().iterate(true); + assertEquals("return Phi(Loop14,arg,(Phi_arg+1));", stop.toString()); + } + + @Test + public void testRegionPeepBug() { + Parser parser = new Parser( + """ +int v0=0; +int v1=0; +while(v1+arg) { + arg=0; + int v2=v0; + while(arg+1) {} + v0=1; + v1=v2; +} + """); + StopNode stop = parser.parse().iterate(true); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testWhile0() { + Parser parser = new Parser("while(0) continue; if(0) arg=0;"); + StopNode stop = parser.parse().iterate(true); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testWhile1() { + Parser parser = new Parser(""" +if(0) while(0) { + int arg=arg; + while(0) {} +} +"""); + StopNode stop = parser.parse().iterate(true); + assertEquals("Stop[ ]", stop.toString()); + } + + + @Test + public void testPrecedence() { + Parser parser = new Parser("return 3-1+2;"); + StopNode stop = parser.parse().iterate(true); + assertEquals("return 4;", stop.toString()); + } + + @Test + public void testSwap2() { + Parser parser = new Parser("return 1+(1+1);"); + StopNode stop = parser.parse().iterate(true); + assertEquals("return 3;", stop.toString()); + } + + + @Test + public void testFuzz0() { + Parser parser = new Parser(""" +int one = 1; +int a = 0; +int zero = 0; +while(arg) { + a = -(one + a + 2); + arg = arg + 1; + one = one + zero; +} +return a; +"""); + StopNode stop = parser.parse().iterate(true); + assertEquals("return Phi(Loop9,0,(-(Phi_a+3)));", stop.toString()); + } + + @Test + public void testFuzz1() { + Parser parser = new Parser(""" +while(1) {} +while(arg) break; +while(arg) arg=0; +arg=0; +int v0=0!=0<-0; +return -0+0+0; +"""); + StopNode stop = parser.parse().iterate(true); + assertEquals("Stop[ ]", stop.toString()); + } + + + @Test + public void testFuzz2() { + Parser parser = new Parser("return 0+-0;"); + StopNode stop = parser.parse().iterate(true); + assertEquals("return 0;", stop.toString()); + } + + @Test + public void testFuzz3() { + Parser parser = new Parser("int v0=0; while(0==69) while(v0) return 0;"); + StopNode stop = parser.parse().iterate(true); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz4() { + Parser parser = new Parser(""" +while(1) { + arg=0<=0; + if(1<0) while(arg==-0) arg=arg-arg; +} +"""); + StopNode stop = parser.parse().iterate(true); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz5() { + Parser parser = new Parser(""" +{ + int v0=0; + while(1) + int v1=0--0; + while(v0) + break; + while(-v0) { + while(0+0+v0) continue; + break; + } + if(-0!=-0+0+v0) while(0+0+0+0) + break; +} +return 0!=0; +"""); + StopNode stop = parser.parse().iterate(true); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz6() { + Parser parser = new Parser(""" +int v0=0; +while(0==1) while(v0) + v0=1+v0; + """); + StopNode stop = parser.parse().iterate(true); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz7() { + Parser parser = new Parser(""" +while(1) {} +int v0=0; +while(v0) + {} +int v1=0; +while(1) + v1=1; +return v1+v0; + """); + StopNode stop = parser.parse().iterate(true); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testFuzz8() { + Parser parser = new Parser("while(arg) arg = arg - 1; #showGraph; return arg;"); + StopNode stop = parser.parse().iterate(true); + assertEquals("return Phi(Loop6,arg,(Phi_arg-1));", stop.toString()); + } + + @Test + public void testMeet() { + Type t1 = Type.TOP; + Type t2 = TypeInteger.TOP; + Assert.assertEquals(TypeInteger.TOP, t1.meet(t2)); + Assert.assertEquals(TypeInteger.TOP, t2.meet(t1)); + t1 = Type.BOTTOM; + t2 = TypeInteger.BOT; + Assert.assertEquals(Type.BOTTOM, t1.meet(t2)); + Assert.assertEquals(Type.BOTTOM, t2.meet(t1)); + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java new file mode 100644 index 00000000..6bafe72a --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/Chapter10Test.java @@ -0,0 +1,363 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StopNode; +import com.seaofnodes.simple.type.*; +import org.junit.Assert; +import org.junit.Test; + +import java.util.Arrays; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter10Test { + + + @Test + public void testStruct() { + Parser parser = new Parser(""" +struct Bar { + int a; + int b; +} +struct Foo { + int x; +} +Foo? foo = null; +Bar bar = new Bar; +bar.a = 1; +bar.a = 2; +return bar.a; +"""); + StopNode stop = parser.parse(true).iterate(true); + System.out.println(IRPrinter.prettyPrint(stop, 99, true)); + assertEquals("return .a;", stop.toString()); + } + + @Test + public void testExample() { + Parser parser = new Parser(""" +struct Vector2D { int x; int y; } +Vector2D v = new Vector2D; +v.x = 1; +if (arg) + v.y = 2; +else + v.y = 3; +return v; +"""); + StopNode stop = parser.parse(true).iterate(true); + System.out.println(IRPrinter.prettyPrint(stop, 99, true)); + assertEquals("return new Vector2D;", stop.toString()); + } + + @Test + public void testBug() { + Parser parser = new Parser(""" +struct s0 { + int v0; +} +s0? v1=null; +int v3=v1.zAicm; +"""); + try { parser.parse(true); fail(); } + catch( Exception e ) { assertEquals("Accessing unknown field 'zAicm' from 'null'",e.getMessage()); } + } + + @Test + public void testBug2() { + Parser parser = new Parser(""" +struct s0 { int v0; } +arg=0+new s0.0; +"""); + try { parser.parse(true); fail(); } + catch( Exception e ) { assertEquals("Expected an identifier, found 'null'",e.getMessage()); } + } + + @Test + public void testLoop() { + Parser parser = new Parser(""" +struct Bar { int a; } +Bar bar = new Bar; +while (arg) { + bar.a = bar.a + 2; + arg = arg + 1; +} +return bar.a; +"""); + StopNode stop = parser.parse(true).iterate(true); + assertEquals("return .a;", stop.toString()); + } + + @Test + public void testIf() { + Parser parser = new Parser(""" +struct Bar { int a; } +Bar bar = new Bar; +if (arg) bar = null; +bar.a = 1; +return bar.a; +"""); + try { parser.parse(true).iterate(true); fail(); } + catch( Exception e ) { assertEquals("Type null is not of declared type *Bar",e.getMessage()); } + } + + @Test + public void testIf2() { + Parser parser = new Parser(""" +struct Bar { int a; } +Bar? bar = null; +if (arg) bar = new Bar; +bar.a = 1; +return bar.a; +"""); + try { parser.parse(true).iterate(true); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'a'",e.getMessage()); } + } + + @Test + public void testIf3() { + Parser parser = new Parser(""" +struct Bar { int a; } +Bar bar = null; +if (arg) bar = null; +bar.a = 1; +return bar.a; +"""); + try { parser.parse(true); fail(); } + catch( Exception e ) { assertEquals("Type null is not of declared type *Bar", e.getMessage()); } + } + + @Test + public void testIfOrNull() { + Parser parser = new Parser(""" +struct Bar { int a; } +Bar? bar = new Bar; +if (arg) bar = null; +if( bar ) bar.a = 1; +return bar; +"""); + StopNode stop = parser.parse(false).iterate(true); + assertEquals("return Phi(Region15,null,new Bar);", stop.toString()); + } + + @Test + public void testIfOrNull2() { + Parser parser = new Parser( +""" +struct Bar { int a; } +Bar? bar = new Bar; +if (arg) bar = null; +int rez = 3; +if( !bar ) rez=4; +else bar.a = 1; +return rez; +"""); + StopNode stop = parser.parse(false).iterate(true); + assertEquals("return Phi(Region32,4,3);", stop.toString()); + } + + @Test + public void testWhileWithNullInside() { + Parser parser = new Parser(""" +struct s0 {int v0;} +s0? v0 = new s0; +int ret = 0; +while(arg) { + ret = v0.v0; + v0 = null; + arg = arg - 1; +} +return ret; +"""); + try { parser.parse(true).iterate(true); fail(); } + catch( Exception e ) { assertEquals("Might be null accessing 'v0'", e.getMessage()); } + } + + @Test + public void testRedeclareStruct() { + Parser parser = new Parser(""" +struct s0 { + int v0; +} +s0? v1=new s0; +s0? v1; +v1=new s0; +"""); + try { parser.parse(true); fail(); } + catch( Exception e ) { assertEquals("Redefining name 'v1'", e.getMessage()); } + } + + @Test + public void test1() { + Parser parser = new Parser(""" +struct s0 {int v0;} +s0 ret = new s0; +while(arg) { + s0 v0 = new s0; + v0.v0 = arg; + arg = arg-1; + if (arg==5) ret=v0; + #showGraph; +} +return ret; +"""); + StopNode stop = parser.parse(true).iterate(true); + System.out.println(IRPrinter.prettyPrint(stop, 99, true)); + assertEquals("return Phi(Loop10,new s0,Phi(Region31,new s0,Phi_ret));", stop.toString()); + } + + @Test + public void test2() { + Parser parser = new Parser(""" +struct s0 {int v0;} +s0 ret = new s0; +s0 v0 = new s0; +while(arg) { + v0.v0 = arg; + arg = arg-1; + if (arg==5) ret=v0; + #showGraph; +} +return ret; +"""); + StopNode stop = parser.parse(true).iterate(true); + System.out.println(IRPrinter.prettyPrint(stop, 99, true)); + assertEquals("return Phi(Loop13,new s0,Phi(Region32,new s0,Phi_ret));", stop.toString()); + } + + + @Test + public void test3() { + Parser parser = new Parser(""" +struct s0 {int v0;} +s0 ret = new s0; +while(arg < 10) { + s0 v0 = new s0; + if (arg == 5) ret=v0; + arg = arg + 1; +} +return ret; +"""); + StopNode stop = parser.parse(true).iterate(true); + System.out.println(IRPrinter.prettyPrint(stop, 99, true)); + assertEquals("return Phi(Loop10,new s0,Phi(Region30,new s0,Phi_ret));", stop.toString()); + } + + @Test + public void testBug3() { + Parser parser = new Parser(""" +struct s0 { + int f0; +} +if(0>=0) return new s0; +return new s0; +int v0=null.f0; +"""); + try { parser.parse(true); fail(); } + catch( Exception e ) { assertEquals("Accessing unknown field 'f0' from 'null'", e.getMessage()); } + } + + @Test + public void testBug4() { + Parser parser = new Parser(""" +if(0) { + while(0) if(arg) continue; + int v0=0; + while(1) { + int arg=-arg; + v0=arg; + } +} + """); + StopNode stop = parser.parse(true).iterate(true); + assertEquals("Stop[ ]", stop.toString()); + } + + @Test + public void testBug5() { + Parser parser = new Parser(""" +struct s0 { + int f0; +} +if(0) return 0; +else return new s0; +if(new s0.f0) return 0; + """); + StopNode stop = parser.parse(true).iterate(true); + assertEquals("return new s0;", stop.toString()); + } + + @Test + public void testBug6MissedWorklist() { + Parser parser = new Parser(""" +while(0) {} +int v4=0; +while(0fuzzPeeps methods. + * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line + * via mvn clean test -Dtest=com.seaofnodes.simple.Fuzzer08Test#fuzzPeeps + */ +public class FuzzerWrap { + + @Ignore + @Test + public void fuzzPeeps() { + var fuzzer = new Fuzzer(); + for (int i=0; i<1000000; i++) + fuzzer.fuzzPeeps(i); + assertTrue(fuzzer.noExceptions()); + } + + + @Test + @Ignore + public void fuzzPeepTiming() { + var fuzzer = new Fuzzer(); + int max_nid=0; + for (int i=0; i<1000000; i++) + max_nid = fuzzer.fuzzPeepTiming(i, max_nid); + } +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/TypeTest.java b/chapter10/src/test/java/com/seaofnodes/simple/TypeTest.java new file mode 100644 index 00000000..f18fb306 --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/TypeTest.java @@ -0,0 +1,145 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.type.*; +import org.junit.Assert; +import org.junit.Test; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertSame; + +public class TypeTest { + + // Test basic properties and GLB + @Test + public void testTypeAdHoc() { + TypeStruct s1 = TypeStruct.make("s1", new Field[]{ + Field.make("s1", TypeInteger.BOT, "a"), + Field.make("s1", TypeInteger.BOT, "b") }); + TypeStruct s2 = TypeStruct.make("s2", new Field[]{ + Field.make("s2", TypeInteger.BOT, "a"), + Field.make("s2", TypeInteger.BOT, "b") }); + Assert.assertEquals(s1, s1.glb()); + Assert.assertNotEquals(s1, s1.dual()); + Assert.assertEquals(s1, s1.dual().glb()); + + TypeMem m1 = TypeMem.make(s1.get("a")._alias); + TypeMem m2 = TypeMem.make(s1.get("b")._alias); + TypeMem m3 = TypeMem.make(s2.get("a")._alias); + TypeMem m4 = TypeMem.make(s2.get("b")._alias); + + Assert.assertNotEquals(m1, m2); + Assert.assertNotEquals(m2, m3); + Assert.assertNotEquals(m3, m4); + + Assert.assertEquals(TypeStruct.BOT, s1.meet(s2)); + Assert.assertEquals(TypeMem .BOT, m1.meet(m2)); + Assert.assertEquals(TypeMem .BOT, m2.meet(m3)); + Assert.assertEquals(TypeMem .BOT, m3.meet(m4)); + + Assert.assertEquals(TypeMem.BOT, m1.glb()); + Assert.assertEquals(m1, m1.dual()); + Assert.assertEquals(TypeMem.TOP, m1.glb().dual()); + + TypeMemPtr ptr1 = TypeMemPtr.make(s1); + Assert.assertEquals(s1, ptr1._obj); + TypeMemPtr ptr2 = TypeMemPtr.make(s2); + Assert.assertEquals(s2, ptr2._obj); + + TypeMemPtr ptr1nil = TypeMemPtr.make(s1, true); + Assert.assertEquals(s1, ptr1nil._obj); + Assert.assertTrue(ptr1nil._nil); + Assert.assertFalse(ptr1nil._obj==null); + TypeMemPtr ptr2nil = TypeMemPtr.make(s2, true); + Assert.assertEquals(s2, ptr2nil._obj); + + Assert.assertNotEquals(ptr1, ptr2); + Assert.assertNotEquals(ptr1, ptr1.glb()); + Assert.assertEquals(ptr1nil, ptr1.glb()); + + Assert.assertEquals(ptr1, ptr1.dual().dual()); + Assert.assertEquals(ptr1.glb(), ptr1.dual().glb()); + Assert.assertEquals(TypeMemPtr.BOT, ptr1.meet(ptr2nil)); + Assert.assertEquals(ptr1.glb(), ptr1.meet(TypeMemPtr.NULLPTR)); + + TypeMemPtr TOP = TypeMemPtr.TOP; + TypeMemPtr BOT = TypeMemPtr.BOT; + TypeMemPtr PTR = TypeMemPtr.VOIDPTR; + TypeMemPtr NULL = TypeMemPtr.NULLPTR; + 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); + Type NULL_join_ptr1 = NULL.join(ptr1); + Assert.assertEquals(TOP, NULL_join_ptr1); + Type NULL_join_PTR = PTR.join(NULL); + Assert.assertEquals(TOP, NULL_join_PTR); + Type ptr1_dual = ptr1.dual(); + Type nullableptr1_dual = ptr1nil.dual(); + } + + // Test theoretical properties. + // This is a symmetric complete bounded (ranked) lattice. + // Also the meet is commutative and associative. + // The lattice has a dual (symmetric), and join is ~(~x meet ~y). + // See https://en.wikipedia.org/wiki/Lattice_(order). + @Test + public void testLatticeTheory() { + Type[] ts = Type.gather(); + + // Confirm commutative & complete + for( Type t0 : ts ) + for( Type t1 : ts ) { + check_commute (t0,t1); + check_symmetric(t0,t1); + } + + // Confirm associative + for( Type t0 : ts ) + for( Type t1 : ts ) + for( Type t2 : ts ) + assoc(t0,t1,t2); + + // Confirm symmetry. If A isa B, then A.join(C) isa B.join(C) + for( Type t0 : ts ) + for( Type t1 : ts ) + if( t0.isa(t1) ) + for( Type t2 : ts ) { + Type t02 = t0.join(t2); + Type t12 = t1.join(t2); + Type mt = t02.meet(t12); + assertSame(mt,t12); + } + } + + // By design in meet, args are already flipped to order _type, which forces + // symmetry for things with badly ordered _type fields. The question is + // still interesting for other orders. + private static void check_commute( Type t0, Type t1 ) { + if( t0==t1 ) return; + if( t0.is_simple() && !t1.is_simple() ) return; // By design, flipped the only allowed order + Type mta = t0.meet(t1); + Type mtb = t1.meet(t0); // Reverse args and try again + assertSame(mta,mtb); + } + + // A & B = MT + // Expect: ~A & ~MT == ~A + // Expect: ~B & ~MT == ~B + private static void check_symmetric( Type t0, Type t1 ) { + if( t1==t0 ) return; + Type mt = t0.meet(t1); + Type ta = mt.dual().meet(t1.dual()); + Type tb = mt.dual().meet(t0.dual()); + assertSame(ta,t1.dual()); + assertSame(tb,t0.dual()); + } + + private static void assoc( Type t0, Type t1, Type t2 ) { + Type t01 = t0 .meet(t1 ); + Type t12 = t1 .meet(t2 ); + Type t01_2 = t01.meet(t2 ); + Type t0_12 = t0 .meet(t12); + assertSame(t01_2,t0_12); + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java new file mode 100644 index 00000000..56933248 --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -0,0 +1,173 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.GraphEvaluator; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StopNode; + +import java.util.ArrayList; +import java.util.Random; +import java.util.function.Consumer; + +/** + * Implementation of the fuzzer. + * Random testcases are generated using the ScriptGenerator. + * This will generate a script similar to how the parser parses it but instead of parsing it will + * randomly choose a variation the parser would parse and generate it. + * These scripts are the parsed by the parser and all exceptions are caught and filtered + * to only show one occurrence of one problem. This includes script which generate different + * results when the compiled graph with and without peeps is executed. + * To aid debugging scripts that cause errors are then reduced by applying rules and checking + * that the same issue persists. + */ +public class Fuzzer { + + private static final int EVAL_TIMEOUT = 1000; + + /** + * List of exceptions already encountered. + * This is used to filter new exceptions and discard them if they are already found. + */ + private final ArrayList exceptions = new ArrayList<>(); + + /** + * Filter and record an exception in a script. + * @param e The exception caused by the script + * @param script The script causing the exception + * @param reproducer Reproducer which should be used to reproduce the test case. + */ + private void recordException(Throwable e, String script, Consumer reproducer, long seed) { + for (var ex : exceptions) { + if (FuzzerUtils.isExceptionFromSameCause(ex, e)) return; + } + exceptions.add(e); + System.out.println("========== Stack =========="); + e.printStackTrace(System.out); + System.out.println("========== Seed =========="); + System.out.println(seed); + System.out.println("========== Code ==========="); + System.out.println(script); + System.out.println("========= Reduced ========="); + System.out.println(Reducer.reduce(script, e, reproducer)); + System.out.println("==========================="); + System.out.flush(); + } + + /** + * Check that two graphs result in the same output when supplied with a value + * @param stop1 Stop node of the first graph + * @param stop2 Stop node of the second graph + * @param in The input value to both graphs to test for an equal output + */ + private static void checkGraphs(StopNode stop1, StopNode stop2, long in) { + if (true) return; + var e1 = GraphEvaluator.evaluateWithResult(stop1, in, EVAL_TIMEOUT); + var e2 = GraphEvaluator.evaluateWithResult(stop2, in, EVAL_TIMEOUT); + if (e1.type() == GraphEvaluator.ResultType.TIMEOUT || e2.type() == GraphEvaluator.ResultType.TIMEOUT) return; + if (e1.type() != e2.type()) + throw new RuntimeException("Different calculations types " + e1.type() + " vs " + e2.type()); + if (e1.value() != e2.value()) + throw new RuntimeException("Different calculations values " + e1.value() + " vs " + e2.value()); + } + + /** + * Run checks for script. Compile the script with peeps enabled and disabled. + * Check that exceptions raised in the parser by both methods are the same and only happens if the script may be invalid. + * If the script was successfully parsed check that both version behave the same. + * @param script The script to test + * @param valid If the script is definitely valid. If not some exceptions may be suppressed. + */ + private static void runCheck(String script, boolean valid) { + StopNode stop1; + try { + stop1 = FuzzerUtils.parse(script, false); + } catch (RuntimeException e1) { + try { + FuzzerUtils.parse(script, true); + } catch (RuntimeException e2) { + if (FuzzerUtils.isExceptionFromSameCause(e1, e2)) { + if (!valid || e1.getClass() == RuntimeException.class) return; + } else { + e1.addSuppressed(e2); + } + } + throw e1; + } + var stop2 = FuzzerUtils.parse(script, true); + checkGraphs(stop1, stop2, 0); + checkGraphs(stop1, stop2, 1); + checkGraphs(stop1, stop2, 10); + } + + /** + * Check that the script does not result in exceptions. + * @param script The script to test. + * @param valid If the script is valid or if it might contain syntax errors. + */ + private void check(String script, boolean valid, long seed) { + try { + runCheck(script, valid); + } catch (Throwable e) { + recordException(e, script, s->runCheck(s, valid), seed); + } + } + + /** + * Run one test with the given seed, and check for peephole counts. + * @param seed The seed to use for generating this test case + */ + public int fuzzPeepTiming(long seed, int max_nids) { + var rand = new Random(seed); + var sb = new StringBuilder(); + new ScriptGenerator(rand, sb, true).genProgram(); + try { + var parser = new Parser(sb.toString()); + + var stop = parser.parse(); + int parse_peeps= Node.ITER_CNT; + int parse_nops = Node.ITER_NOP_CNT; + double parse_nop_ratio = (double)parse_nops/parse_peeps; + int nids = Node.UID(); + if( nids <= max_nids ) return max_nids; + + double parse_peeps_per_node = (double)parse_peeps/nids; + + stop.iterate(); + int iter_peeps= Node.ITER_CNT; + int iter_nops = Node.ITER_NOP_CNT; + double iter_nop_ratio = (double)iter_nops/iter_peeps; + double iter_peeps_per_node = (double)iter_peeps/nids; + + System.out.printf("%6d | Parsing: peeps: %5d, nops: %5d, ratio: %5.3f, last UID: %5d ps/node: %5.3f | Iter: peeps: %6d, nops: %6d, ratio: %5.3f, ps/node: %5.3f\n", + seed, + parse_peeps,parse_nops,parse_nop_ratio,nids,parse_peeps_per_node, + iter_peeps , iter_nops, iter_nop_ratio, iter_peeps_per_node); + return nids; + } catch (Throwable e) { + // ignore exceptions, let the normal fullPeeps catch and reduce, + // we're interested in valid program optimizations + } + return max_nids; + } + + + /** + * Run one test with the given seed. + * @param seed The seed to use for generating this test case + */ + public void fuzzPeeps(long seed) { + var rand = new Random(seed); + var sb = new StringBuilder(); + var valid = new ScriptGenerator(rand, sb, true).genProgram(); + check(sb.toString(), valid, seed); + } + + + /** + * Check that no exceptions happened. + * @return true if no exception happened + */ + public boolean noExceptions() { + return exceptions.isEmpty(); + } +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java new file mode 100644 index 00000000..18ef069a --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -0,0 +1,140 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.IterPeeps; +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.Node; +import com.seaofnodes.simple.node.StopNode; + +import java.io.OutputStream; +import java.io.PrintStream; +import java.lang.invoke.MethodHandle; +import java.lang.invoke.MethodHandles; +import java.lang.reflect.Field; +import java.util.BitSet; + +/** + * Some utilities for the fuzzer. + */ +class FuzzerUtils { + + /** + * Get the val of a private field + */ + @SuppressWarnings("unchecked") + public static T getFieldValue(Object obj, String name) throws NoSuchFieldException, IllegalAccessException { + return (T) (obj instanceof Class clz ? getField(clz, name).get(null) : getField(obj.getClass(), name).get(obj)); + } + + /** + * Get access to a private field + */ + public static Field getField(Class clz, String name) throws NoSuchFieldException { + var field = clz.getDeclaredField(name); + try { + field.setAccessible(true); + } catch (Throwable e) { + // Intentionally left empty + } + return field; + } + + /** + * Try to rethrow an exception or create a runtime exception and throw it. + */ + public static RuntimeException rethrow(Throwable e) { + if (e instanceof RuntimeException re) return re; + if (e instanceof Error er) throw er; + return new RuntimeException(e); + } + + /** + * Copy of Node.WVISIST + * Used to clear as exceptions might happen in the walk and left this bitset not cleared + */ + private static final BitSet NodeWalkVisit; + + /** + * Write access to Iterate.MID_ASSERT + * Exception could happen mid assert and left this at true. Used to reset to false prior to parsing. + */ + private static final MethodHandle set_MID_ASSERT; + + /** + * Some problems might trigger debug output. Suppress this output with a null print stream during fuzzing. + */ + public static final PrintStream NULL_PRINT_STREAM = new PrintStream(OutputStream.nullOutputStream()); + + static { + try { + NodeWalkVisit = getFieldValue(Node.class, "WVISIT"); + set_MID_ASSERT = MethodHandles.lookup().unreflectSetter(getField( IterPeeps.class, "MID_ASSERT")); + } catch (Exception e) { + throw new ExceptionInInitializerError(e); + } + } + + /** + * Check that the messages are similar. + */ + private static boolean similarMessages(String a, String b) { + if (a == null || b == null) return true; + a = a.replaceAll("'\\w+'", "'normalized'").replaceAll("variable \\w+", "variable normalized"); + b = b.replaceAll("'\\w+'", "'normalized'").replaceAll("variable \\w+", "variable normalized"); + return a.equals(b); + } + + /** + * Check if both stack traces have the same first entry. Empty stack traces can happen with NPE optimization + * and allow the other to be any stack trace. + */ + private static boolean sameStackTraceOrigin(StackTraceElement[] a, StackTraceElement[] b) { + if (a == null || a.length == 0 || b == null || b.length == 0) return true; // One or both stack traces are missing. + return a[0].equals(b[0]); + } + + /** + * Checks if two exceptions are caused by the same problem. + */ + public static boolean isExceptionFromSameCause(Throwable a, Throwable b) { + if (a == null || b == null) return a == b; // Handle the null case + if (a.getClass() != b.getClass()) return false; // Different classes + if (!similarMessages(a.getMessage(), b.getMessage())) return false; // Different messages. Null is allowed as wildcard + var s1 = a.getStackTrace(); + var s2 = b.getStackTrace(); + if (!sameStackTraceOrigin(s1, s2)) return false; // Different stack trace origins + if (!isExceptionFromSameCause(a.getCause(), b.getCause())) return false; // Different causes + var o1 = a.getSuppressed(); + var o2 = b.getSuppressed(); + if (o1 == null || o2 == null || o1.length != o2.length) return o1 == o2; // Different suppression + for (int i=0; i {} + + /** + * Holder for the rewrite rules + */ + private record Replace(Pattern pattern, boolean iterate, Replacer... replacements) { + Replace(Pattern p, Object... replacements) { + this(p, replacements[0] == Boolean.TRUE, Arrays.stream(replacements).filter(o->!(o instanceof Boolean)).map(Replace::from).toArray(Replacer[]::new)); + } + private static Replacer from(Object o) { + if (o instanceof Replacer r) return r; + if (o instanceof Integer i) return (s, m)->s.append(m.group(i)); + if (o instanceof String r) return (s, m)->s.append(r); + throw new IllegalArgumentException(); + } + } + + /** + * List of rewrite rules. + */ + private static final Replace[] REPLACEMENTS = { + new Replace(Pattern.compile("\\b(?:[^\\W0]|\\w\\w+)\\b"), "0", "1"), + new Replace(Pattern.compile("(?<=\\n|^)[^\\n]+(?=\\n|$)"), true, ""), + new Replace(Pattern.compile("(?<=[+\\-*/<>=(])--"), ""), + new Replace(Pattern.compile("\\b--"), "+"), + new Replace(Pattern.compile("-"), ""), + new Replace(Pattern.compile("\\b\\+-"), "-"), + new Replace(Pattern.compile("(?=])(?:-|\\*|/|>=|<=|>|<|!=|==)(?![+\\-*/<>=])"), "+"), + new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)(?:\\n[ \\t]*)?}"), "", "{}", 1), + new Replace(Pattern.compile("(?<=\\n|^)([ \\t]*)\\{\\n(.*?)\\n\\1}", Pattern.DOTALL), 2), + new Replace(Pattern.compile("\\(([^()]+)\\)"), 1), + new Replace(Pattern.compile("\\d+\\+"), ""), + new Replace(Pattern.compile("\\+\\d+"), ""), + new Replace(Pattern.compile("\\n\\n+"), "\n"), + new Replace(Pattern.compile("^\\n+|\\n+$"), ""), + new Replace(Pattern.compile("else *"), ""), + new Replace(Pattern.compile("\\bif\\([^()]+\\) *"), ""), + new Replace(Pattern.compile("\\bwhile\\([^()]+\\) *"), ""), + new Replace(Pattern.compile("\\bstruct \\w+ \\{[^{}]*}"), "") + }; + + /** + * Predicate to test if the reduced script generates the same error. + */ + private final Predicate tester; + + /** + * Create a reducer with a test function. + * @param tester Test function which returns true when the same issue is found in the script. + */ + private Reducer(Predicate tester) { + this.tester = tester; + } + + /** + * Rewrites the script with one rewrite rule. + */ + private String doReplacement(String script, Pattern pattern, Replacer[] replacements) { + var matcher = pattern.matcher(script); + var sb = new StringBuilder(); + var last = 0; + var skip = 0; + outer: + while (matcher.find(last + skip)) { + sb.append(script, last, matcher.start()); + last = matcher.end(); + skip = last == matcher.start() ? 1 : 0; + var pos = sb.length(); + for (var replacement : replacements) { + replacement.accept(sb, matcher); + var tail = sb.length(); + sb.append(script, last, script.length()); + if (tester.test(sb.toString())) { + sb.setLength(tail); + continue outer; + } + sb.setLength(pos); + } + last = matcher.start(); + skip = 1; + } + sb.append(script, last, script.length()); + return sb.toString(); + } + + /** + * Clean up variable names from the random ones generated by the fuzzer. + */ + private String cleanVariables(String script) { + var matcher = Pattern.compile("\\b([0-9a-zA-Z_]+) ([0-9a-zA-Z_]+)").matcher(script); + int[] num = {0, 0}; + while (matcher.find()) { + var type = matcher.group(1); + var var = matcher.group(2); + if (type.equals("new")) continue; + String prefix = "v"; + int t = 0; + if (type.equals("struct")) { + t = 1; + prefix = "s"; + } + if (var.matches(prefix+"\\d+")) continue; + while (script.contains(prefix+num[t])) num[t]++; + var n = script.replaceAll("\\b"+var+"\\b", prefix + num[t]); + if (tester.test(n)) { + script = n; + } + } + return script; + } + + /** + * Run all rewrite rules once. + */ + private String doAllReplacements(String script) { + for (var replace: REPLACEMENTS) { + String old; + do { + old = script; + script = doReplacement(script, replace.pattern, replace.replacements); + } while (replace.iterate && !old.equals(script)); + } + return script; + } + + /** + * Reduce the script to a minimal version which produces the same problem with a test function. + * @param tester Test function which returns true when the same issue is found in the script. + */ + public static String reduce(String script, Predicate tester) { + var reducer = new Reducer(tester); + String old; + do { + old = script; + script = reducer.doAllReplacements(script); + script = reducer.cleanVariables(script); + } while (!script.equals(old)); + return script; + } + + /** + * Reduce the script to a minimal version which produces the same problem with a reproducer. + * @param ex The exception originally caused by the script + * @param reproducer Test function which throws an exception which will be checked against ex. + */ + public static String reduce(String script, Throwable ex, Consumer reproducer) { + return reduce(script, s->{ + Throwable nex = null; + try { + reproducer.accept(s); + } catch (Throwable e) { + nex = e; + } + return FuzzerUtils.isExceptionFromSameCause(nex, ex); + }); + } + +} diff --git a/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java new file mode 100644 index 00000000..155063ab --- /dev/null +++ b/chapter10/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -0,0 +1,792 @@ +package com.seaofnodes.simple.fuzzer; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.node.ScopeNode; + +import java.util.ArrayList; +import java.util.HashSet; +import java.util.Random; +import java.util.function.Predicate; + +/** + * Generate a pseudo random script. + * This generator will generate the same script for two random number generators initialized with the same seed. + * To generate valid code it implements the parser but instead of parsing it emits the statements and expressions. + * It is guaranteed to terminate. + */ +public class ScriptGenerator { + + private static final int MAX_STATEMENTS_PER_BLOCK = 5; + private static final int MAX_BINARY_EXPRESSIONS_PER_EXPRESSION = 10; + private static final int MAX_UNARY_EXPRESSIONS_PER_EXPRESSION = 6; + private static final int MAX_NAME_LENGTH = 10; + private static final int MAX_BLOCK_DEPTH = 4; + private static final int MAX_EXPRESSION_DEPTH = 10; + + /** + * Number of spaces per indentation + */ + private static final int INDENTATION = 4; + /** + * Valid characters for identifiers. The last 10 are not valid for the first character. + */ + private static final String VAR_CHARS = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_0123456789"; + /** + * List of keywords not valid for identifiers. + */ + private static final HashSet KEYWORDS; + + static { + try { + KEYWORDS = FuzzerUtils.getFieldValue(new Parser(""), "KEYWORDS"); + } catch (Throwable e) { + throw new ExceptionInInitializerError(e); + } + } + + /** + * Flag for a statement that it does not pass on control flow to the next statement. + */ + private static final int FLAG_STOP = 0x01; + /** + * Flag for a statement that it contains a final if statement without an else branch. + */ + private static final int FLAG_IF_WITHOUT_ELSE = 0x02; + /** + * Binary operators. + */ + private static final String[] BINARY_OP = {"==", "!=", "<", "<=", ">", ">=", "+", "-", "*", "/"}; + /** + * Unary operators. + */ + private static final String[] UNARY_OP = {"-"}; + + private static class Type { + final String name; + Type(String name) {this.name=name;} + boolean isa(Type other) { return this == other; } + } + + private static class TypeStruct extends Type { + record Field (String name, Type type) {} + final Field[] fields; + final TypeNullable nullable = new TypeNullable(this); + TypeStruct(String name, Field[] fields) { + super(name); + this.fields = fields; + } + boolean isa(Type other) { return this == other || other == nullable; } + } + + private static class TypeNullable extends Type { + + final Type base; + + TypeNullable(Type base) { + super(base.name+"?"); + this.base = base; + } + + } + + private static final Type TYPE_INT = new Type("int"); + + + private static class Variable { + final String name; + final Type declared; + final Variable shadowing; + Type type; + boolean shadowed = false; + + Variable(String name, Type type, Variable var) { + this.name = name; + this.declared = type; + this.type = type; + this.shadowing = var; + } + } + + /** + * The random number generator used for random decisions. + */ + private final Random random; + /** + * Indentation depth. + */ + private int indentation = 0; + /** + * Output string builder + */ + private final StringBuilder sb; + /** + * Number of nested loops + */ + private int loopDepth = 0; + /** + * Current scope start in the variables list. + */ + private int currScopeStart = 0; + /** + * The depth of blocks allowed. + */ + private int depth = MAX_BLOCK_DEPTH; + /** + * The depth of expressions allowed. + */ + private int exprDepth = MAX_EXPRESSION_DEPTH; + /** + * Current variables in scope. + */ + private final ArrayList variables = new ArrayList<>(); + /** + * All defined structs. + */ + private final ArrayList structs = new ArrayList<>(); + /** + * Allow to declare structs. + */ + private boolean allowStructs = true; + /** + * If this needs to generate valid scripts or is also allowed to generate invalid ones. + */ + private boolean generateValid; + /** + * If this script might be invalid. + */ + private boolean maybeInvalid = false; + + + /** + * + * @param random the random number generator. + * @param sb the script will be written to this string builder. + * @param generateValid if the script should be guaranteed valid or if it is allowed to contain bugs. + */ + public ScriptGenerator(Random random, StringBuilder sb, boolean generateValid) { + this.random = random; + this.sb = sb; + this.generateValid = generateValid; + } + + /** + * Random number with log distribution + * @param max The maximum value + * @return A random number in the range [0, max) with higher numbers being more uncommon. + */ + private int randLog(int max) { + max--; + int n = 1<=0; i--) { + if ((num & (1<2) return false; + maybeInvalid = true; + return true; + } + + /** + * Lookup a variable by name + * @param name name of the variable + * @return The index of the variable in variables or -1 + */ + private int lookup(String name) { + for (int i=variables.size()-1; i>=0; i--) { + if (variables.get(i).name.equals(name)) return i; + } + return -1; + } + + /** + * Lookup a variable by name + * @param name name of the variable + * @return THe variable of null if not found + */ + private Variable lookupVar(String name) { + int idx = lookup(name); + return idx == -1 ? null : variables.get(idx); + } + + /** + * Add a variable to the current scope + * @param name The name of the variable + * @param type The declared type of the variable + */ + private void addVariable(String name, Type type) { + var old = lookupVar(name); + variables.add(new Variable(name, type, old)); + if (old != null) old.shadowed = true; + } + + /** + * Pop variables to level to + * @param to Level until which variables should be popped + */ + private void popVariables(int to) { + while (variables.size() > to) { + var v = variables.removeLast(); + if (v.shadowing != null) v.shadowing.shadowed = false; + } + } + + /** + * Get a random visible variable patching pred + * @param pred The predicate the variable needs to match + * @return A random visible variable matching pred or null if no variable mached pred. + */ + private Variable findVisibleVariablesMatching(Predicate pred) { + int num=0; + for (var v:variables) { + if (!v.shadowed && pred.test(v)) num++; + } + if (num == 0) return null; + num = random.nextInt(num); + for (var v:variables) { + if (!v.shadowed && pred.test(v) && num-- == 0) return v; + } + throw new AssertionError(); + } + + /** + * Get a structure by name + * @param name Name of the structure + * @return The structure of null + */ + private TypeStruct getStruct(String name) { + for (var s:structs) { + if (s.name.equals(name)) return s; + } + return null; + } + + /** + * Generate a variable name. This might be new random name or a name from an outer scope. + * If the program is allowed to be invalid this can return keywords and already used variable names in the current scope. + * @return The variable name. + */ + private String getVarName() { + if (currScopeStart > 0 && random.nextInt(10) > 7) { + // Use a variable outside the current scope. + var v = variables.get(random.nextInt(currScopeStart)); + if (lookup(v.name) < currScopeStart) return v.name; + if (!generateValid) { + maybeInvalid = true; + return v.name; + } + } + // Generate a new random variable name + StringBuilder sb = getRandomName(); + var v = sb.toString(); + if (!generateValid && (KEYWORDS.contains(v) || lookup(v) >= currScopeStart)) { + maybeInvalid = true; + return v; + } + while (KEYWORDS.contains(v) || lookup(v) >= currScopeStart) { + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); + v = sb.toString(); + } + return v; + } + + /** + * Get a random structure name + * @return A random structure name + */ + private String getStructName() { + if (!structs.isEmpty() && generateInvalid()) return structs.get(random.nextInt(structs.size())).name; + // Generate a new random struct name + StringBuilder sb = getRandomName(); + var v = sb.toString(); + if (!generateValid && (KEYWORDS.contains(v) || getStruct(v) != null)) { + maybeInvalid = true; + return v; + } + while (KEYWORDS.contains(v) || getStruct(v) != null) { + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); + v = sb.toString(); + } + return v; + } + + /** + * Get a random type + * @return A random type + */ + private Type getType() { + if (structs.isEmpty() || random.nextBoolean()) return TYPE_INT; + var idx = random.nextInt(structs.size()); + TypeStruct struct = structs.get(idx); + if (random.nextBoolean()) return struct.nullable; + return struct; + } + + /** + * Generates a program and writes it into the string builder supplied in the constructor. + * @return If the program is allowed to be invalid returns if something potentially invalid was generated. + */ + public boolean genProgram() { + var oldGenerateValid = generateValid; + if (!generateValid && random.nextBoolean()) generateValid = true; + this.maybeInvalid = false; + addVariable(ScopeNode.ARG0, TYPE_INT); + currScopeStart = variables.size(); + if ((genStatements() & FLAG_STOP) == 0) { + if (generateValid || random.nextInt(10)<7) { + genReturn(); + } else { + this.maybeInvalid = true; + } + } + generateValid = oldGenerateValid; + return !this.maybeInvalid; + } + + /** + * Generate a list of statements. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the last statement generated + */ + public int genStatements() { + var num = random.nextInt(MAX_STATEMENTS_PER_BLOCK * (depth+1)); + for (int i=0; i allowStructs || generateInvalid() ? genStruct() : genAssignment(); + case 1 -> genBlock(); + case 2 -> genIf(); + case 3 -> genCountedLoop(); + case 4 -> genWhile(); + case 5, 6 -> genDecl(); + case 7, 8, 9 -> genAssignment(); + case 10 -> genNullCheck(); + default -> genExit(); + }; + } + + /** + * Generate a new structure + * @return 0 + */ + public int genStruct() { + var name = getStructName(); + var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)]; + sb.append("struct ").append(name).append(" {\n"); + indentation += INDENTATION; + for (int i=0; i { + depth++; + indentation -= INDENTATION; + var ret = genBlock(); + indentation += INDENTATION; + depth--; + yield ret; + } + case 6 -> genIf(); + case 7 -> genCountedLoop(); + case 8 -> genWhile(); + case 9 -> genAssignment(); + case 10 -> genNullCheck(); + default -> genExit(); + }; + depth++; + } + indentation -= INDENTATION; + allowStructs = oldAllowStructs; + return res; + } + + /** + * Generate an exit. This can be return or break and continue when in a loop. + * @return FLAG_STOP + */ + public int genExit() { + if (loopDepth == 0 && generateValid) return genReturn(); + return switch (random.nextInt(7)) { + case 0,1,2 -> { + if (loopDepth == 0) maybeInvalid = true; + sb.append("continue;"); + yield FLAG_STOP; + } + case 3,4,5 -> { + if (loopDepth == 0) maybeInvalid = true; + sb.append("break;"); + yield FLAG_STOP; + } + default -> genReturn(); + }; + } + + /** + * Generate a block statement. After a certain depth only empty blocks are generated to ensure termination of the generator. + * @return flag FLAG_STOP for the generated statement + */ + public int genBlock() { + if (depth == 0) { + sb.append("{}"); + return 0; + } + var oldAllowStructs = allowStructs; + var oldCSS = currScopeStart; + allowStructs = false; + currScopeStart = variables.size(); + depth--; + sb.append("{\n"); + indentation += INDENTATION; + var stop = genStatements(); + indentation -= INDENTATION; + printIndentation().append("}"); + popVariables(currScopeStart); + depth++; + currScopeStart = oldCSS; + allowStructs = oldAllowStructs; + return stop & ~FLAG_IF_WITHOUT_ELSE; + } + + /** + * Generate an if statement with an optional else block. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement + */ + public int genIf() { + sb.append("if("); + genExpression(TYPE_INT); + sb.append(") "); + var stop = genStatementBlock(); + if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) { + sb.append("\n"); + printIndentation().append("else "); + stop &= genStatementBlock(); + } else { + stop = FLAG_IF_WITHOUT_ELSE; + } + return stop; + } + + /** + * Generate a block with a null check + * if (nullable) { handle_nullable_as_non_nullable; } + */ + public int genNullCheck() { + var v = findVisibleVariablesMatching(va->va.declared instanceof TypeNullable); + if (v == null) return genIf(); + var n = (TypeNullable)v.declared; + boolean negate = random.nextBoolean(); + sb.append("if("); + if (negate) sb.append("!"); + sb.append(v.name).append(")"); + if (!negate) v.type = n.base; + var stop = genStatementBlock(); + v.type = n; + if ((stop & FLAG_IF_WITHOUT_ELSE) == 0 && random.nextInt(10) > 3) { + sb.append("\n"); + printIndentation().append("else "); + if (negate) v.type = n.base; + stop &= genStatementBlock(); + v.type = n; + } else { + stop = FLAG_IF_WITHOUT_ELSE; + } + return stop; + } + + /** + * Generate a while loop. + * @return 0 + */ + public int genWhile() { + sb.append("while("); + genExpression(TYPE_INT); + sb.append(") "); + loopDepth++; + genStatementBlock(); + loopDepth--; + return 0; + } + + /** + * Generate a counted loop of the form + * + * { + * int varname = start_expr; + * while (varname < end_expr) loop_body; + * } + * + * @return 0 + */ + public int genCountedLoop() { + if (depth == 0) return genWhile(); + var oldCSS = currScopeStart; + currScopeStart = variables.size(); + sb.append("{\n"); + indentation += INDENTATION; + String name = getVarName(); + printIndentation().append("int ").append(name).append("="); + genExpression(TYPE_INT); + sb.append(";\n"); + addVariable(name, TYPE_INT); + printIndentation().append("while(").append(name).append("<"); + genExpression(TYPE_INT); + sb.append(") {\n"); + indentation += INDENTATION; + depth--; + loopDepth++; + printIndentation().append(name).append("=").append(name).append("+"); + genExpression(TYPE_INT); + sb.append(";\n"); + genStatements(); + loopDepth--; + depth++; + indentation -= INDENTATION; + printIndentation().append("}\n"); + indentation -= INDENTATION; + printIndentation().append("}"); + popVariables(currScopeStart); + currScopeStart = oldCSS; + return 0; + } + + /** + * Generate a declaration statement. + * @return 0 + */ + public int genDecl() { + var type = getType(); + var name = getVarName(); + sb.append(generateInvalid() ? getRandomName() : type.name).append(" ").append(name); + if (!(type instanceof TypeNullable) || random.nextBoolean()) { + sb.append("="); + genExpression(type); + } + sb.append(";"); + addVariable(name, type); + return 0; + } + + /** + * Generate an assignment statement. + * @return 0 + */ + public int genAssignment() { + Type type; + Type declared; + if (generateInvalid()) { + sb.append(getRandomName()); + type = getType(); + declared = type; + } else { + var v = findVisibleVariablesMatching(va->true); + if (v == null) return genDecl(); + sb.append(v.name); + type = v.type; + declared = v.declared; + } + if (generateInvalid()) { + var name = getRandomName(); + sb.append(".").append(name); + declared = getType(); + } else if (type instanceof TypeStruct s && s.fields.length > 0 && random.nextBoolean()) { + var field = s.fields[random.nextInt(s.fields.length)]; + sb.append(".").append(field.name); + declared = field.type; + } + sb.append("="); + genExpression(declared); + sb.append(";"); + return 0; + } + + /** + * Generate a return statement. + * @return FLAG_STOP + */ + public int genReturn() { + var type = getType(); + sb.append("return "); + genExpression(type); + sb.append(";"); + return FLAG_STOP; + } + + /** + * Generate a binary expression. + * This method does not care about operator precedence. + */ + public void genExpression(Type type) { + if (generateInvalid()) type = getType(); + if (type != TYPE_INT) { + genUnary(type); + return; + } + var num = randLog(MAX_BINARY_EXPRESSIONS_PER_EXPRESSION); + while(num-->0) { + genUnary(TYPE_INT); + sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]); + } + genUnary(TYPE_INT); + } + + /** + * Generate a unary expression. + */ + public void genUnary(Type type) { + if (generateInvalid()) type = getType(); + if (type != TYPE_INT) { + genSuffix(type); + return; + } + var num = randLog(MAX_UNARY_EXPRESSIONS_PER_EXPRESSION); + while(num-->0) { + sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]); + } + genSuffix(TYPE_INT); + } + + /** + * Generate + */ + public void genSuffix(Type type) { + if (generateInvalid()) type = getType(); + if (type == TYPE_INT && random.nextBoolean()) { + var t = getType(); + if (generateInvalid()) { + var field = getRandomName(); + genPrimary(t); + sb.append(".").append(field); + return; + } else if (t instanceof TypeStruct s && s.fields.length > 0) { + var field = s.fields[random.nextInt(s.fields.length)]; + if (field.type == TYPE_INT) { + genPrimary(t); + sb.append(".").append(field.name); + return; + } + } + } + genPrimary(type); + } + + /** + * Generate a primary expression. + */ + public void genPrimary(Type type) { + if (generateInvalid()) type = getType(); + var rand = random.nextInt(10); + if (rand == 0 && exprDepth != 0) { + sb.append("("); + exprDepth--; + genExpression(type); + exprDepth++; + sb.append(")"); + } else if (rand < 6) { + genVariable(type); + } else { + genConst(type); + } + } + + /** + * Generate a constant. + */ + public void genConst(Type type) { + if (generateInvalid()) type = getType(); + if (type == TYPE_INT) { + var rand = random.nextInt(10); + switch (rand) { + case 0 -> sb.append("true"); + case 1 -> sb.append("false"); + default -> sb.append(random.nextInt(1<<(rand-2))); + } + } else if (type instanceof TypeNullable n) { + if (random.nextBoolean()) { + sb.append("null"); + } else { + sb.append("new ").append(generateInvalid() ? getRandomName() : n.base.name); + } + } else { + sb.append("new ").append(generateInvalid() ? getRandomName() : type.name); + } + } + + /** + * Generate a variable. If there are none generate a number instead. + * If the program is allowed to be invalid a random name can be generated in some cases. + */ + public void genVariable(Type type) { + if (generateInvalid()) { + sb.append(getRandomName()); + return; + } + if (generateInvalid()) type = getType(); + var t = type; + var v = findVisibleVariablesMatching(va->va.type.isa(t)); + if (v == null) genConst(type); + else sb.append(v.name); + } + +} -- cgit v1.2.3