From e5f4f7b85fbb91a293a7d89d7b85adfbaeeb51f4 Mon Sep 17 00:00:00 2001 From: Thalia Archibald Date: Fri, 21 Jun 2024 06:13:09 -0700 Subject: Format whitespace (#86) * Trim trailing whitespace * Ensure final new lines * Convert line endings from CRLF to LF * Replace tabs with spaces --- .../java/com/seaofnodes/simple/Chapter01Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter02Test.java | 8 +- .../java/com/seaofnodes/simple/Chapter03Test.java | 4 +- .../java/com/seaofnodes/simple/Chapter04Test.java | 10 +- .../java/com/seaofnodes/simple/Chapter05Test.java | 40 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter07Test.java | 5 +- .../java/com/seaofnodes/simple/Chapter08Test.java | 10 +- .../java/com/seaofnodes/simple/Chapter09Test.java | 6 +- .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 340 ++++---- .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 276 +++---- .../java/com/seaofnodes/simple/fuzzer/Reducer.java | 288 +++---- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 912 ++++++++++----------- 13 files changed, 952 insertions(+), 953 deletions(-) (limited to 'chapter09/src/test/java/com') diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java index 48cc716f..5abfc4cf 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter01Test.java @@ -16,7 +16,7 @@ public class Chapter01Test { 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 ) { @@ -40,7 +40,7 @@ public class Chapter01Test { @Test public void testBad2() { - try { + try { new Parser("return 0123;").parse(); fail(); } catch( RuntimeException e ) { diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java index 5efd33e7..3dd22e39 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter02Test.java @@ -9,7 +9,7 @@ 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;"); @@ -64,10 +64,10 @@ public class Chapter02Test { GraphVisualizer gv = new GraphVisualizer(); System.out.println(gv.generateDotOutput(parser)); } - + @Test public void testBad1() { - try { + try { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { @@ -82,7 +82,7 @@ public class Chapter02Test { @Test public void testBad4() { - try { + try { new Parser("return 100").parse(); fail(); } catch( RuntimeException e ) { diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java index 8a11107d..6bcfcc4b 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter03Test.java @@ -9,7 +9,7 @@ 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;"); @@ -49,7 +49,7 @@ public class Chapter03Test { @Test public void testSelfAssign() { - try { + try { new Parser("int a=a; return a;").parse(); fail(); } catch( RuntimeException e ) { diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java index ffbbe9a8..5a024e77 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter04Test.java @@ -9,7 +9,7 @@ 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;"); @@ -37,7 +37,7 @@ public class Chapter04Test { 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;"); @@ -51,7 +51,7 @@ public class Chapter04Test { StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } - + @Test public void testVarArg() { Parser parser = new Parser("return arg; #showGraph;"); @@ -112,7 +112,7 @@ public class Chapter04Test { @Test public void testBug3() { - try { + try { new Parser("inta=1; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -126,5 +126,5 @@ public class Chapter04Test { StopNode ret = parser.parse(); assertEquals("return (-arg);", ret.print()); } - + } diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java index 6bdc0ef6..24ae80b8 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -9,7 +9,7 @@ import org.junit.Ignore; import static org.junit.Assert.*; public class Chapter05Test { - + @Test public void testIfStmt() { Parser parser = new Parser( @@ -26,7 +26,7 @@ return a;"""); StopNode ret = parser.parse().iterate(true); assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); } - + @Test public void testTest() { Parser parser = new Parser( @@ -41,20 +41,20 @@ 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; +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( @@ -140,20 +140,20 @@ return a;"""); StopNode stop = new Parser("return true;").parse(); assertEquals("return 1;",stop.toString()); } - + @Test public void testHalfDef() { - try { + 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 { + try { new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); fail(); } catch( RuntimeException e ) { @@ -163,38 +163,38 @@ return a;"""); @Test public void testRegress1() { - try { + 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 { + 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 { + 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 { + try { new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); fail(); } catch( RuntimeException e ) { @@ -204,7 +204,7 @@ return a;"""); @Test public void testKeyword3() { - try { + try { new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); fail(); } catch( RuntimeException e ) { diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java index ba0ea9f6..5fece2e2 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -292,5 +292,5 @@ return a+b+c; StopNode ret = parser.parse().iterate(true); assertEquals("return 5;", ret.toString()); } - + } diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java index 48876598..d42af6c3 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter07Test.java @@ -10,7 +10,7 @@ import static org.junit.Assert.*; public class Chapter07Test { - + @Test public void testExample() { Parser parser = new Parser( @@ -44,7 +44,7 @@ return a; StopNode stop = parser.parse().iterate(true); assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); } - + @Test public void testWhileNested() { Parser parser = new Parser( @@ -242,4 +242,3 @@ return a; assertTrue(stop.ret().ctrl() instanceof ProjNode); } } - \ No newline at end of file diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 18371494..05485d8c 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -145,10 +145,10 @@ return arg; StopNode stop = parser.parse().iterate(true); assertEquals("return 0;", stop.toString()); } - + @Test public void testBreakOutsideLoop() { - try { + try { new Parser(""" if(arg <= 10) { break; @@ -173,7 +173,7 @@ return arg; StopNode stop = parser.parse().iterate(true); assertEquals("return arg;", stop.toString()); } - + @Test public void testRegress4() { Parser parser = new Parser(""" @@ -189,9 +189,9 @@ 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); + assertTrue(stop.ret().ctrl() instanceof RegionNode); } - + @Test public void testRegress5() { Parser parser = new Parser(""" diff --git a/chapter09/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/chapter09/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 8e198218..834ba3d4 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -149,7 +149,7 @@ while(v1+arg) { if(0) while(0) { int arg=arg; while(0) {} -} +} """); StopNode stop = parser.parse().iterate(true); assertEquals("Stop[ ]", stop.toString()); @@ -170,7 +170,7 @@ if(0) while(0) { assertEquals("return 3;", stop.toString()); } - + @Test public void testFuzz0() { Parser parser = new Parser(""" @@ -209,7 +209,7 @@ return -0+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;"); diff --git a/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index 90817d2b..936fb41e 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -1,170 +1,170 @@ -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) { - for (var ex : exceptions) { - if (FuzzerUtils.isExceptionFromSameCause(ex, e)) return; - } - exceptions.add(e); - System.out.println("========== Stack =========="); - e.printStackTrace(System.out); - 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) { - 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) { - try { - runCheck(script, valid); - } catch (Throwable e) { - recordException(e, script, s->runCheck(s, valid)); - } - } - - /** - * 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, false).genProgram(); - check(sb.toString(), valid); - } - - - /** - * Check that no exceptions happened. - * @return true if no exception happened - */ - public boolean noExceptions() { - return exceptions.isEmpty(); - } -} +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) { + for (var ex : exceptions) { + if (FuzzerUtils.isExceptionFromSameCause(ex, e)) return; + } + exceptions.add(e); + System.out.println("========== Stack =========="); + e.printStackTrace(System.out); + 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) { + 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) { + try { + runCheck(script, valid); + } catch (Throwable e) { + recordException(e, script, s->runCheck(s, valid)); + } + } + + /** + * 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, false).genProgram(); + check(sb.toString(), valid); + } + + + /** + * Check that no exceptions happened. + * @return true if no exception happened + */ + public boolean noExceptions() { + return exceptions.isEmpty(); + } +} diff --git a/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java index a331e5a0..f13a51e1 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -1,138 +1,138 @@ -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 value 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 eiter one of the objects is null or that both are equal. - */ - private static boolean equalOrNull(Object a, Object b) { - if (a == null || b == null) return true; - 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 (!equalOrNull(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 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 eiter one of the objects is null or that both are equal. + */ + private static boolean equalOrNull(Object a, Object b) { + if (a == null || b == null) return true; + 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 (!equalOrNull(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=(])--"), ""), - new Replace(Pattern.compile("\\b--"), "+"), - new Replace(Pattern.compile("\\b\\+-"), "-"), - new Replace(Pattern.compile("\\bfalse\\b"), "0"), - new Replace(Pattern.compile("\\btrue\\b"), "1"), - new Replace(Pattern.compile("-"), ""), - new Replace(Pattern.compile("(?=])(?:-|\\*|/|>=|<=|>|<|!=|==)(?![+\\-*/<>=])"), "+"), - new Replace(Pattern.compile("\\{(?:[^{}]|\\{})+}"), "{}"), - new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)}"), "$1"), - new Replace(Pattern.compile("\\(([^()]+)\\)"), "$1"), - new Replace(Pattern.compile("\\b\\w+\\b"), "0"), - new Replace(Pattern.compile("\\b(?:[^\\W0]|\\w\\w+)\\b"), "1"), - new Replace(Pattern.compile("\\d+\\+"), ""), - new Replace(Pattern.compile("\\+\\d+"), ""), - new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"), - new Replace(Pattern.compile("\\n+"), "\n"), - new Replace(Pattern.compile("^\\n+|\\n+$"), ""), - new Replace(Pattern.compile("else *"), ""), - new Replace(Pattern.compile("\\bif\\([^()]+\\) *"), ""), - new Replace(Pattern.compile("\\bwhile\\([^()]+\\) *"), ""), - }; - - /** - * 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, String with) { - var matcher = pattern.matcher(script); - var sb = new StringBuilder(); - int last = 0; - while (matcher.find()) { - var pos = sb.length(); - matcher.appendReplacement(sb, with); - var tail = sb.length(); - matcher.appendTail(sb); - if (tester.test(sb.toString())) { - sb.setLength(tail); - } else { - sb.setLength(pos); - sb.append(script, last, matcher.end()); - } - last = matcher.end(); - } - matcher.appendTail(sb); - return sb.toString(); - } - - /** - * Clean up variable names from the random ones generated by the fuzzer. - */ - private String cleanVariables(String script) { - var matcher = Pattern.compile("\\bint ([0-9a-zA-Z_]+)").matcher(script); - int num = 0; - while (matcher.find()) { - var var = matcher.group(1); - if (var.matches("v\\d+")) continue; - while (script.contains("v"+num)) num++; - var n = script.replaceAll("\\b"+var+"\\b", "v" + num); - if (tester.test(n)) { - script = n; - } - } - return script; - } - - /** - * Run all rewrite rules once. - */ - private String doAllReplacements(String script) { - for (var replace: REPLACEMENTS) { - script = doReplacement(script, replace.p, replace.r); - } - 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); - }); - } - -} +package com.seaofnodes.simple.fuzzer; + +import java.util.function.Consumer; +import java.util.function.Predicate; +import java.util.regex.Pattern; + +/** + * This class is used to reduce test cases created by the fuzzer. + * It applies rewrite rules to the test case and checks that the + * test still produces the same exception. + * This is done in a fixpoint iteration until every rewrite produces + * no or a different exception. + */ +public class Reducer { + + /** + * Holder for the rewrite rules + */ + private record Replace(Pattern p, String r) {} + + /** + * List of rewrite rules. + */ + private static final Replace[] REPLACEMENTS = { + new Replace(Pattern.compile("(?<=[+\\-*/<>=(])--"), ""), + new Replace(Pattern.compile("\\b--"), "+"), + new Replace(Pattern.compile("\\b\\+-"), "-"), + new Replace(Pattern.compile("\\bfalse\\b"), "0"), + new Replace(Pattern.compile("\\btrue\\b"), "1"), + new Replace(Pattern.compile("-"), ""), + new Replace(Pattern.compile("(?=])(?:-|\\*|/|>=|<=|>|<|!=|==)(?![+\\-*/<>=])"), "+"), + new Replace(Pattern.compile("\\{(?:[^{}]|\\{})+}"), "{}"), + new Replace(Pattern.compile("\\{((?:[^{}]|\\{})+)}"), "$1"), + new Replace(Pattern.compile("\\(([^()]+)\\)"), "$1"), + new Replace(Pattern.compile("\\b\\w+\\b"), "0"), + new Replace(Pattern.compile("\\b(?:[^\\W0]|\\w\\w+)\\b"), "1"), + new Replace(Pattern.compile("\\d+\\+"), ""), + new Replace(Pattern.compile("\\+\\d+"), ""), + new Replace(Pattern.compile("(?<=\\n|^)[^\\n]*(?=\\n|$)"), "\n"), + new Replace(Pattern.compile("\\n+"), "\n"), + new Replace(Pattern.compile("^\\n+|\\n+$"), ""), + new Replace(Pattern.compile("else *"), ""), + new Replace(Pattern.compile("\\bif\\([^()]+\\) *"), ""), + new Replace(Pattern.compile("\\bwhile\\([^()]+\\) *"), ""), + }; + + /** + * 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, String with) { + var matcher = pattern.matcher(script); + var sb = new StringBuilder(); + int last = 0; + while (matcher.find()) { + var pos = sb.length(); + matcher.appendReplacement(sb, with); + var tail = sb.length(); + matcher.appendTail(sb); + if (tester.test(sb.toString())) { + sb.setLength(tail); + } else { + sb.setLength(pos); + sb.append(script, last, matcher.end()); + } + last = matcher.end(); + } + matcher.appendTail(sb); + return sb.toString(); + } + + /** + * Clean up variable names from the random ones generated by the fuzzer. + */ + private String cleanVariables(String script) { + var matcher = Pattern.compile("\\bint ([0-9a-zA-Z_]+)").matcher(script); + int num = 0; + while (matcher.find()) { + var var = matcher.group(1); + if (var.matches("v\\d+")) continue; + while (script.contains("v"+num)) num++; + var n = script.replaceAll("\\b"+var+"\\b", "v" + num); + if (tester.test(n)) { + script = n; + } + } + return script; + } + + /** + * Run all rewrite rules once. + */ + private String doAllReplacements(String script) { + for (var replace: REPLACEMENTS) { + script = doReplacement(script, replace.p, replace.r); + } + 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/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index ad0c0a4a..ad98f7e2 100644 --- a/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter09/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -1,456 +1,456 @@ -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; - -/** - * 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 { - - /** - * 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 = {"-"}; - - - /** - * 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 = 20; - /** - * The depth of expressions allowed. - */ - private int exprDepth = 30; - /** - * Current variables in scope. - */ - private final ArrayList variables = new ArrayList<>(); - /** - * If this needs to generate valid scripts or is also allowed to generate invalid ones. - */ - private final 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< 0 && random.nextInt(10) > 7) { - // Use a variable outside the current scope. - var v = variables.get(random.nextInt(currScopeStart)); - if (variables.lastIndexOf(v) < currScopeStart) return v; - if (!generateValid) { - maybeInvalid = true; - return v; - } - } - // Generate a new random variable name - StringBuilder sb = getRandomName(); - var v = sb.toString(); - if (!generateValid && (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart)) { - maybeInvalid = true; - return v; - } - while (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart) { - sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); - v = sb.toString(); - } - return v; - } - - - - /** - * 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() { - this.maybeInvalid = false; - variables.add(ScopeNode.ARG0); - currScopeStart = variables.size(); - if ((genStatements() & FLAG_STOP) == 0) { - if (generateValid || random.nextInt(10)<7) { - genReturn(); - } else { - this.maybeInvalid = true; - } - } - 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(10); // (30); - for (int i=0; i genBlock(); - case 2 -> genIf(); - case 3 -> genWhile(); - case 4, 5 -> genDecl(); - case 6, 7, 8 -> genAssignment(); - default -> genExit(); - }; - } - - /** - * Generate a statement for if, else and while blocks. - * This is special since it disallows declarations and prefers to generate blocks. - * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement - */ - public int genStatementBlock() { - indentation += INDENTATION; - int res; - if (depth == 0) { - res = random.nextBoolean() ? genAssignment() : genExit(); - } else { - depth--; - res = switch (random.nextInt(10)) { - case 1, 2, 3, 4, 5 -> { - depth++; - indentation -= INDENTATION; - var ret = genBlock(); - indentation += INDENTATION; - depth--; - yield ret; - } - case 6 -> genIf(); - case 7 -> genWhile(); - case 8 -> genAssignment(); - default -> genExit(); - }; - depth++; - } - indentation -= INDENTATION; - 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; - } - depth--; - int oldCSS = currScopeStart; - currScopeStart = variables.size(); - sb.append("{\n"); - indentation += INDENTATION; - var stop = genStatements(); - indentation -= INDENTATION; - printIndentation().append("}"); - while (variables.size() > currScopeStart) - variables.removeLast(); - currScopeStart = oldCSS; - depth++; - 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(); - 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 while loop. - * @return 0 - */ - public int genWhile() { - sb.append("while("); - genExpression(); - sb.append(") "); - loopDepth++; - genStatementBlock(); - loopDepth--; - return 0; - } - - /** - * Generate a declaration statement. - * @return 0 - */ - public int genDecl() { - String name = getVarName(); - sb.append("int ").append(name).append("="); - genExpression(); - sb.append(";"); - variables.add(name); - return 0; - } - - /** - * Generate an assignment statement. - * @return 0 - */ - public int genAssignment() { - if (variables.isEmpty()) return genDecl(); - genVariable(); - sb.append("="); - genExpression(); - sb.append(";"); - return 0; - } - - /** - * Generate a return statement. - * @return FLAG_STOP - */ - public int genReturn() { - sb.append("return "); - genExpression(); - sb.append(";"); - return FLAG_STOP; - } - - - /** - * Generate a binary expression. - * This method does not care about operator precedence. - */ - public void genExpression() { - var num = randLog(10); - while(num-->0) { - genUnary(); - sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]); - } - genUnary(); - } - - /** - * Generate a unary expression. - */ - public void genUnary() { - var num = randLog(6); - while(num-->0) { - sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]); - } - genPrimary(); - } - - /** - * Generate a primary expression. - */ - public void genPrimary() { - switch (random.nextInt(10)) { - case 0: - sb.append("true"); - break; - case 1: - sb.append("false"); - break; - case 2: - if (exprDepth == 0) { - // Ensure termination of the generator. - if (random.nextBoolean()) { - genNumber(); - } else { - genVariable(); - } - } else { - sb.append("("); - exprDepth--; - genExpression(); - exprDepth++; - sb.append(")"); - } - break; - case 3, 4, 5, 6: - genNumber(); - break; - default: - genVariable(); - } - } - - /** - * Generate a number. - */ - public void genNumber() { - sb.append(random.nextInt(100)); - } - - /** - * 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() { - if (!generateValid && random.nextInt(100)>97) { - sb.append(getRandomName()); - maybeInvalid = true; - return; - } - if (variables.isEmpty()) { - genNumber(); - } else { - sb.append(variables.get(random.nextInt(variables.size()))); - } - } - -} +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; + +/** + * 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 { + + /** + * 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 = {"-"}; + + + /** + * 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 = 20; + /** + * The depth of expressions allowed. + */ + private int exprDepth = 30; + /** + * Current variables in scope. + */ + private final ArrayList variables = new ArrayList<>(); + /** + * If this needs to generate valid scripts or is also allowed to generate invalid ones. + */ + private final 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< 0 && random.nextInt(10) > 7) { + // Use a variable outside the current scope. + var v = variables.get(random.nextInt(currScopeStart)); + if (variables.lastIndexOf(v) < currScopeStart) return v; + if (!generateValid) { + maybeInvalid = true; + return v; + } + } + // Generate a new random variable name + StringBuilder sb = getRandomName(); + var v = sb.toString(); + if (!generateValid && (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart)) { + maybeInvalid = true; + return v; + } + while (KEYWORDS.contains(v) || variables.lastIndexOf(v) >= currScopeStart) { + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); + v = sb.toString(); + } + return v; + } + + + + /** + * 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() { + this.maybeInvalid = false; + variables.add(ScopeNode.ARG0); + currScopeStart = variables.size(); + if ((genStatements() & FLAG_STOP) == 0) { + if (generateValid || random.nextInt(10)<7) { + genReturn(); + } else { + this.maybeInvalid = true; + } + } + 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(10); // (30); + for (int i=0; i genBlock(); + case 2 -> genIf(); + case 3 -> genWhile(); + case 4, 5 -> genDecl(); + case 6, 7, 8 -> genAssignment(); + default -> genExit(); + }; + } + + /** + * Generate a statement for if, else and while blocks. + * This is special since it disallows declarations and prefers to generate blocks. + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement + */ + public int genStatementBlock() { + indentation += INDENTATION; + int res; + if (depth == 0) { + res = random.nextBoolean() ? genAssignment() : genExit(); + } else { + depth--; + res = switch (random.nextInt(10)) { + case 1, 2, 3, 4, 5 -> { + depth++; + indentation -= INDENTATION; + var ret = genBlock(); + indentation += INDENTATION; + depth--; + yield ret; + } + case 6 -> genIf(); + case 7 -> genWhile(); + case 8 -> genAssignment(); + default -> genExit(); + }; + depth++; + } + indentation -= INDENTATION; + 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; + } + depth--; + int oldCSS = currScopeStart; + currScopeStart = variables.size(); + sb.append("{\n"); + indentation += INDENTATION; + var stop = genStatements(); + indentation -= INDENTATION; + printIndentation().append("}"); + while (variables.size() > currScopeStart) + variables.removeLast(); + currScopeStart = oldCSS; + depth++; + 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(); + 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 while loop. + * @return 0 + */ + public int genWhile() { + sb.append("while("); + genExpression(); + sb.append(") "); + loopDepth++; + genStatementBlock(); + loopDepth--; + return 0; + } + + /** + * Generate a declaration statement. + * @return 0 + */ + public int genDecl() { + String name = getVarName(); + sb.append("int ").append(name).append("="); + genExpression(); + sb.append(";"); + variables.add(name); + return 0; + } + + /** + * Generate an assignment statement. + * @return 0 + */ + public int genAssignment() { + if (variables.isEmpty()) return genDecl(); + genVariable(); + sb.append("="); + genExpression(); + sb.append(";"); + return 0; + } + + /** + * Generate a return statement. + * @return FLAG_STOP + */ + public int genReturn() { + sb.append("return "); + genExpression(); + sb.append(";"); + return FLAG_STOP; + } + + + /** + * Generate a binary expression. + * This method does not care about operator precedence. + */ + public void genExpression() { + var num = randLog(10); + while(num-->0) { + genUnary(); + sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]); + } + genUnary(); + } + + /** + * Generate a unary expression. + */ + public void genUnary() { + var num = randLog(6); + while(num-->0) { + sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]); + } + genPrimary(); + } + + /** + * Generate a primary expression. + */ + public void genPrimary() { + switch (random.nextInt(10)) { + case 0: + sb.append("true"); + break; + case 1: + sb.append("false"); + break; + case 2: + if (exprDepth == 0) { + // Ensure termination of the generator. + if (random.nextBoolean()) { + genNumber(); + } else { + genVariable(); + } + } else { + sb.append("("); + exprDepth--; + genExpression(); + exprDepth++; + sb.append(")"); + } + break; + case 3, 4, 5, 6: + genNumber(); + break; + default: + genVariable(); + } + } + + /** + * Generate a number. + */ + public void genNumber() { + sb.append(random.nextInt(100)); + } + + /** + * 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() { + if (!generateValid && random.nextInt(100)>97) { + sb.append(getRandomName()); + maybeInvalid = true; + return; + } + if (variables.isEmpty()) { + genNumber(); + } else { + sb.append(variables.get(random.nextInt(variables.size()))); + } + } + +} -- cgit v1.2.3