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/Chapter08Test.java | 72 +- .../java/com/seaofnodes/simple/Fuzzer08Test.java | 52 +- .../java/com/seaofnodes/simple/fuzzer/Fuzzer.java | 256 +++--- .../com/seaofnodes/simple/fuzzer/FuzzerUtils.java | 116 +-- .../java/com/seaofnodes/simple/fuzzer/Reducer.java | 288 +++---- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 924 ++++++++++----------- 6 files changed, 854 insertions(+), 854 deletions(-) (limited to 'chapter08/src/test/java') diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java index 3df49f4a..f8bbfaa3 100644 --- a/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java +++ b/chapter08/src/test/java/com/seaofnodes/simple/Chapter08Test.java @@ -154,10 +154,10 @@ return arg; StopNode stop = parser.parse(true); assertEquals("Stop[ return 0; return 0; ]", stop.toString()); } - + @Test public void testChapter8BreakOutsideLoop() { - try { + try { new Parser(""" if(arg <= 10) { break; @@ -182,7 +182,7 @@ return arg; StopNode stop = parser.parse(true); assertEquals("return arg;", stop.toString()); } - + @Test public void testChapter8Regress4() { Parser parser = new Parser(""" @@ -198,9 +198,9 @@ return a; """); StopNode stop = parser.parse(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 testChapter8Regress5() { Parser parser = new Parser(""" @@ -216,7 +216,7 @@ return a; assertEquals("return (Phi(Loop7,1,Add)+1);", stop.toString()); assertTrue(stop.ret().ctrl() instanceof RegionNode); } - + @Test public void testChapter7Example() { Parser parser = new Parser( @@ -250,7 +250,7 @@ return a; StopNode stop = parser.parse(true); assertEquals("return Phi(Region22,1,Phi(Loop11,1,(Phi_a+1)));", stop.toString()); } - + @Test public void testChapter7WhileNested() { Parser parser = new Parser( @@ -749,7 +749,7 @@ return a;"""); StopNode ret = parser.parse(true); assertEquals("return Phi(Region17,(arg+2),(arg-3));", ret.toString()); } - + @Test public void testChapter5Test() { Parser parser = new Parser( @@ -764,20 +764,20 @@ return c;""", TypeInteger.BOT); StopNode ret = parser.parse(true); assertEquals("return Phi(Region16,4,3);", ret.toString()); } - + @Test public void testChapter5Return2() { 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 testChapter5IfMergeB() { Parser parser = new Parser( @@ -863,20 +863,20 @@ return a;"""); StopNode stop = new Parser("return true;").parse(); assertEquals("return 1;",stop.toString()); } - + @Test public void testChapter5HalfDef() { - 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 testChapter5HalfDef2() { - try { + try { new Parser("if( arg==1 ) { int b=2; } else { int b=3; } return b;").parse(); fail(); } catch( RuntimeException e ) { @@ -886,38 +886,38 @@ return a;"""); @Test public void testChapter5Regress1() { - 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 testChapter5BadNum() { - try { + try { new Parser("return 1-;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Syntax error, expected an identifier or expression: ;",e.getMessage()); } } - + @Test public void testChapter5Keyword1() { - 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 testChapter5Keyword2() { - try { + try { new Parser("int else=arg; if(else) else=2; else else=1; return else;").parse(); fail(); } catch( RuntimeException e ) { @@ -927,14 +927,14 @@ return a;"""); @Test public void testChapter5Keyword3() { - try { + try { new Parser("int a=1; ififif(arg)inta=2;return a;").parse(); fail(); } catch( RuntimeException e ) { assertEquals("Syntax error, expected =: (",e.getMessage()); } } - + @Test public void testChapter4Peephole() { Parser parser = new Parser("return 1+arg+2; #showGraph;"); @@ -962,7 +962,7 @@ return a;"""); StopNode ret = parser.parse(); assertEquals("return (arg*2);", ret.print()); } - + @Test public void testChapter4Peephole3() { Parser parser = new Parser("return 1+arg+2+arg+3; #showGraph;"); @@ -976,7 +976,7 @@ return a;"""); StopNode ret = parser.parse(); assertEquals("return arg;", ret.print()); } - + @Test public void testChapter4VarArg() { Parser parser = new Parser("return arg; #showGraph;"); @@ -1037,7 +1037,7 @@ return a;"""); @Test public void testChapter4Bug3() { - try { + try { new Parser("inta=1; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -1051,7 +1051,7 @@ return a;"""); StopNode ret = parser.parse(); assertEquals("return (-arg);", ret.print()); } - + @Test public void testVarDecl() { Parser parser = new Parser("int a=1; return a;"); @@ -1091,7 +1091,7 @@ return a;"""); @Test public void testSelfAssign() { - try { + try { new Parser("int a=a; return a;").parse(); fail(); } catch( RuntimeException e ) { @@ -1160,7 +1160,7 @@ return a;"""); 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 ) { @@ -1183,7 +1183,7 @@ return a;"""); @Test public void testBad1() { - try { + try { new Parser("ret").parse(); fail(); } catch( RuntimeException e ) { @@ -1193,7 +1193,7 @@ return a;"""); @Test public void testBad2() { - try { + try { new Parser("return 0123;").parse(); fail(); } catch( RuntimeException e ) { @@ -1209,7 +1209,7 @@ return a;"""); @Test public void testBad4() { - try { + try { new Parser("return 100").parse(); fail(); } catch( RuntimeException e ) { diff --git a/chapter08/src/test/java/com/seaofnodes/simple/Fuzzer08Test.java b/chapter08/src/test/java/com/seaofnodes/simple/Fuzzer08Test.java index b8c0a8e5..ee635c22 100644 --- a/chapter08/src/test/java/com/seaofnodes/simple/Fuzzer08Test.java +++ b/chapter08/src/test/java/com/seaofnodes/simple/Fuzzer08Test.java @@ -1,26 +1,26 @@ -package com.seaofnodes.simple; - -import com.seaofnodes.simple.fuzzer.Fuzzer; -import org.junit.Ignore; -import org.junit.Test; - - -import static org.junit.Assert.assertTrue; - -/** - * To use the fuzzer run the fuzzPeeps 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 Fuzzer08Test { - - @Test - @Ignore - public void fuzzPeeps() { - var fuzzer = new Fuzzer(); - for (int i=0; i<100000; i++) - fuzzer.fuzzPeeps(i); - assertTrue(fuzzer.noExceptions()); - } - -} +package com.seaofnodes.simple; + +import com.seaofnodes.simple.fuzzer.Fuzzer; +import org.junit.Ignore; +import org.junit.Test; + + +import static org.junit.Assert.assertTrue; + +/** + * To use the fuzzer run the fuzzPeeps 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 Fuzzer08Test { + + @Test + @Ignore + public void fuzzPeeps() { + var fuzzer = new Fuzzer(); + for (int i=0; i<100000; i++) + fuzzer.fuzzPeeps(i); + assertTrue(fuzzer.noExceptions()); + } + +} diff --git a/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java b/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java index 2af22f1d..5fcd8764 100644 --- a/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java +++ b/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/Fuzzer.java @@ -1,128 +1,128 @@ -package com.seaofnodes.simple.fuzzer; - -import com.seaofnodes.simple.GraphEvaluator; -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. - * @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.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. + * @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/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java b/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java index ad499836..37a57e11 100644 --- a/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java +++ b/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/FuzzerUtils.java @@ -1,58 +1,58 @@ -package com.seaofnodes.simple.fuzzer; - -import com.seaofnodes.simple.Parser; -import com.seaofnodes.simple.node.Node; -import com.seaofnodes.simple.node.StopNode; - -/** - * Some utilities for the fuzzer. - */ -class FuzzerUtils { - - /** - * 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"), "1"), - new Replace(Pattern.compile("\\b\\w+\\b"), "0"), - 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"), "1"), + new Replace(Pattern.compile("\\b\\w+\\b"), "0"), + 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/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java b/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java index 9df3dfcc..148c2319 100644 --- a/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java +++ b/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/ScriptGenerator.java @@ -1,462 +1,462 @@ -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 { - - /** - * Get the list of keywords from the parser. - */ - @SuppressWarnings("unchecked") - private static HashSet getKeywords() { - try { - var field = Parser.class.getDeclaredField("KEYWORDS"); - field.setAccessible(true); - return (HashSet) field.get(new Parser("")); - } catch (Throwable e) { - throw new ExceptionInInitializerError(e); - } - } - - /** - * 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 = getKeywords(); - - /** - * 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 = 7; - /** - * The depth of expressions allowed. - */ - private int exprDepth = 3; - /** - * 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); - 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 { + + /** + * Get the list of keywords from the parser. + */ + @SuppressWarnings("unchecked") + private static HashSet getKeywords() { + try { + var field = Parser.class.getDeclaredField("KEYWORDS"); + field.setAccessible(true); + return (HashSet) field.get(new Parser("")); + } catch (Throwable e) { + throw new ExceptionInInitializerError(e); + } + } + + /** + * 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 = getKeywords(); + + /** + * 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 = 7; + /** + * The depth of expressions allowed. + */ + private int exprDepth = 3; + /** + * 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); + 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