diff options
Diffstat (limited to 'chapter08')
35 files changed, 1139 insertions, 1141 deletions
diff --git a/chapter08/README.md b/chapter08/README.md index 6d5ce026..4c095912 100644 --- a/chapter08/README.md +++ b/chapter08/README.md @@ -14,7 +14,7 @@ In [chapter 7](../chapter07/README.md), we created `PhiNode`s for all variables in the loop head eagerly. This approach creates some unnecessary Phis but the redundant Phis get cleaned up later. -In this chapter we add support for creating the `PhiNode`s lazily. +In this chapter we add support for creating the `PhiNode`s lazily. The main complication with creating `PhiNode`s lazily is that when we create a Phi, it must be created in the innermost loop head scope where it would have @@ -166,7 +166,7 @@ The implementation is a variation of above. return toScope; } ``` - + * The continue scope becomes the base scope for the subsequent `continue` statement, thus forming a stack of continue scopes/regions. * After the loop is done, if we find that a continue scope was created within @@ -266,7 +266,7 @@ We talk about resolving nodes above, but what does that mean? A node will either With that, a simple non-looping program can be evaluated. -Looping is almost functional with that, too, with only a couple of small extra details. Whenever control moves through a `LoopNode`, the evaluator checks that it hasn't run out of loop iterations. If it has, a timeout RuntimeException will be thrown. +Looping is almost functional with that, too, with only a couple of small extra details. Whenever control moves through a `LoopNode`, the evaluator checks that it hasn't run out of loop iterations. If it has, a timeout RuntimeException will be thrown. Finally, while calculating the value of `PhiNode`s in the loop region, we must be careful to compute all of their new values before we update any of their cached values. That's because as a loop iterates, we must ensure that all `PhiNode` values are consistently the value from the same point in time. Once all of the new values are calculated, we can update the cache for all of them at once. To illustrate this, consider the following code: @@ -292,5 +292,3 @@ return arg; ``` On the other hand, this engine is not designed to be particularly fast! Because not all expressions are cached, it's possible to construct programs like the preceeding one which have exponential runtime. - - diff --git a/chapter08/docs/08-grammar.md b/chapter08/docs/08-grammar.md index c603f335..4c61bfd7 100644 --- a/chapter08/docs/08-grammar.md +++ b/chapter08/docs/08-grammar.md @@ -10,7 +10,7 @@ program statement : returnStatement | declStatement - | blockStatment + | blockStatment | expressionStatement | ifStatement | whileStatement @@ -26,10 +26,10 @@ whileStatement breakStatement : 'break' ';' ; - + continueStatement : 'continue' ';' - ; + ; ifStatement : 'if' '(' expression ')' statement ('else' statement)? @@ -58,15 +58,15 @@ returnStatement expression : comparisonExpression ; - + comparisonExpression : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* ; - + additiveExpression - : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* ; - + multiplicativeExpression : unaryExpression (('*' | '/') unaryExpression)* ; @@ -88,11 +88,11 @@ INTEGER_LITERAL : [1-9][0-9]* | [0] ; - + IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; - + NON_DIGIT: [a-zA-Z_]; DEC_DIGIT: [0-9]; -```
\ No newline at end of file +``` diff --git a/chapter08/pom.xml b/chapter08/pom.xml index 5942485f..738653fe 100644 --- a/chapter08/pom.xml +++ b/chapter08/pom.xml @@ -11,4 +11,4 @@ <artifactId>chapter08</artifactId> <packaging>jar</packaging> <name>Chapter 8</name> -</project>
\ No newline at end of file +</project> diff --git a/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java b/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java index b89189f5..f5694a78 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/GraphEvaluator.java @@ -1,181 +1,181 @@ -package com.seaofnodes.simple;
-
-import com.seaofnodes.simple.node.*;
-import com.seaofnodes.simple.type.TypeInteger;
-
-import java.util.Arrays;
-import java.util.BitSet;
-import java.util.HashMap;
-
-public class GraphEvaluator {
-
- public enum ResultType { VALUE, FALLTHROUGH, TIMEOUT }
-
- public record Result(ResultType type, long value) {}
-
- /**
- * Find the start node from some node in the graph or null if there is no start node
- */
- private static StartNode findStart(BitSet visit, Node node) {
- if (node == null) return null;
- if (node instanceof StartNode start) return start;
- if( visit.get(node._nid) ) return null;
- visit.set(node._nid);
- for( Node def : node._inputs ) {
- var res = findStart(visit,def);
- if( res != null ) return res;
- }
- for( Node use : node._outputs ) {
- var res = findStart(visit,use);
- if( res != null ) return res;
- }
- return null;
- }
-
- /**
- * Find the control output from a control node
- */
- private static Node findControl(Node control) {
- for( Node use : control._outputs ) {
- if (use.isCFG()) return use;
- }
- return null;
- }
-
- /**
- * Find the projection for a node
- */
- private static ProjNode findProjection(Node node, int idx) {
- for( Node use : node._outputs ) {
- if (use instanceof ProjNode proj && proj._idx == idx) return proj;
- }
- return null;
- }
-
- /**
- * Cache values for phi and parameter projection nodes.
- */
- private final HashMap<Node, Long> cacheValues = new HashMap<>();
- /**
- * Cache for loop phis as they can depend on itself or other loop phis
- */
- private long[] loopPhiCache = new long[16];
-
- private GraphEvaluator() {
- }
-
- private long div(DivNode div) {
- long in2 = getValue(div.in(2));
- return in2 == 0 ? 0 : getValue(div.in(1)) / in2;
- }
-
- /**
- * Calculate the value of a node
- */
- private long getValue(Node node) {
- var cache = cacheValues.get(node);
- if (cache != null) return cache;
- return switch (node) {
- case ConstantNode cons -> ((TypeInteger)cons.compute()).value();
- case AddNode add -> getValue(add.in(1)) + getValue(add.in(2));
- case BoolNode.EQ eq -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0;
- case BoolNode.LE le -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0;
- case BoolNode.LT lt -> getValue(lt.in(1)) < getValue(lt.in(2)) ? 1 : 0;
- case DivNode div -> div(div);
- case MinusNode minus -> -getValue(minus.in(1));
- case MulNode mul -> getValue(mul.in(1)) * getValue(mul.in(2));
- case NotNode not -> getValue(not.in(1)) == 0 ? 1 : 0;
- case SubNode sub -> getValue(sub.in(1)) - getValue(sub.in(2));
- default -> throw Utils.TODO("Unexpected node " + node);
- };
- }
-
- /**
- * Special case of latchPhis when phis can depend on phis of the same region.
- */
- private void latchLoopPhis(RegionNode region, Node prev) {
- int idx = Utils.find(region._inputs, prev);
- assert idx > 0;
- int i = 0;
- for( Node use : region._outputs ) {
- if (use instanceof PhiNode phi) {
- var value = getValue(phi.in(idx));
- if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2);
- loopPhiCache[i++] = value;
- }
- }
- i = 0;
- for( Node use : region._outputs ) {
- if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]);
- }
- }
-
- /**
- * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region.
- */
- private void latchPhis(RegionNode region, Node prev) {
- int idx = Utils.find(region._inputs, prev);
- assert idx > 0;
- for( Node use : region._outputs ) {
- if (use instanceof PhiNode phi) {
- var value = getValue(phi.in(idx));
- cacheValues.put(phi, value);
- }
- }
- }
-
- /**
- * Run the graph until either a return is found or the number of loop iterations are done.
- */
- private Result evaluate(StartNode start, long parameter, int loops) {
- var parameter1 = findProjection(start, 1);
- if (parameter1 != null) cacheValues.put(parameter1, parameter);
- Node control = findProjection(start, 0);
- Node prev = start;
- while (control != null) {
- Node next;
- switch (control) {
- case RegionNode region -> {
- if (region instanceof LoopNode && region.in(1) != prev) {
- if (loops--<=0) return new Result(ResultType.TIMEOUT, 0);
- latchLoopPhis(region, prev);
- } else {
- latchPhis(region, prev);
- }
- next = findControl(region);
- }
- case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1);
- case ReturnNode ret -> {
- return new Result(ResultType.VALUE, getValue(ret.in(1)));
- }
- case ProjNode ignored -> next = findControl(control);
- default -> throw Utils.TODO("Unexpected control node " + control);
- }
- prev = control;
- control = next;
- }
- return new Result(ResultType.FALLTHROUGH, 0);
- }
-
- public static long evaluate(Node graph) {
- return evaluate(graph, 0);
- }
-
- public static long evaluate(Node graph, long parameter) {
- return evaluate(graph, parameter, 1000);
- }
-
- public static long evaluate(Node graph, long parameter, int loops) {
- var res = evaluateWithResult(graph, parameter, loops);
- if (res.type==ResultType.TIMEOUT) throw new RuntimeException("Timeout");
- return res.value;
- }
-
- public static Result evaluateWithResult(Node graph, long parameter, int loops) {
- var start = findStart(new BitSet(), graph);
- if (start == null) return new Result(ResultType.TIMEOUT, 0);
- var evaluator = new GraphEvaluator();
- return evaluator.evaluate(start, parameter, loops);
- }
-
-}
+package com.seaofnodes.simple; + +import com.seaofnodes.simple.node.*; +import com.seaofnodes.simple.type.TypeInteger; + +import java.util.Arrays; +import java.util.BitSet; +import java.util.HashMap; + +public class GraphEvaluator { + + public enum ResultType { VALUE, FALLTHROUGH, TIMEOUT } + + public record Result(ResultType type, long value) {} + + /** + * Find the start node from some node in the graph or null if there is no start node + */ + private static StartNode findStart(BitSet visit, Node node) { + if (node == null) return null; + if (node instanceof StartNode start) return start; + if( visit.get(node._nid) ) return null; + visit.set(node._nid); + for( Node def : node._inputs ) { + var res = findStart(visit,def); + if( res != null ) return res; + } + for( Node use : node._outputs ) { + var res = findStart(visit,use); + if( res != null ) return res; + } + return null; + } + + /** + * Find the control output from a control node + */ + private static Node findControl(Node control) { + for( Node use : control._outputs ) { + if (use.isCFG()) return use; + } + return null; + } + + /** + * Find the projection for a node + */ + private static ProjNode findProjection(Node node, int idx) { + for( Node use : node._outputs ) { + if (use instanceof ProjNode proj && proj._idx == idx) return proj; + } + return null; + } + + /** + * Cache values for phi and parameter projection nodes. + */ + private final HashMap<Node, Long> cacheValues = new HashMap<>(); + /** + * Cache for loop phis as they can depend on itself or other loop phis + */ + private long[] loopPhiCache = new long[16]; + + private GraphEvaluator() { + } + + private long div(DivNode div) { + long in2 = getValue(div.in(2)); + return in2 == 0 ? 0 : getValue(div.in(1)) / in2; + } + + /** + * Calculate the value of a node + */ + private long getValue(Node node) { + var cache = cacheValues.get(node); + if (cache != null) return cache; + return switch (node) { + case ConstantNode cons -> ((TypeInteger)cons.compute()).value(); + case AddNode add -> getValue(add.in(1)) + getValue(add.in(2)); + case BoolNode.EQ eq -> getValue(eq.in(1)) == getValue(eq.in(2)) ? 1 : 0; + case BoolNode.LE le -> getValue(le.in(1)) <= getValue(le.in(2)) ? 1 : 0; + case BoolNode.LT lt -> getValue(lt.in(1)) < getValue(lt.in(2)) ? 1 : 0; + case DivNode div -> div(div); + case MinusNode minus -> -getValue(minus.in(1)); + case MulNode mul -> getValue(mul.in(1)) * getValue(mul.in(2)); + case NotNode not -> getValue(not.in(1)) == 0 ? 1 : 0; + case SubNode sub -> getValue(sub.in(1)) - getValue(sub.in(2)); + default -> throw Utils.TODO("Unexpected node " + node); + }; + } + + /** + * Special case of latchPhis when phis can depend on phis of the same region. + */ + private void latchLoopPhis(RegionNode region, Node prev) { + int idx = Utils.find(region._inputs, prev); + assert idx > 0; + int i = 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) { + var value = getValue(phi.in(idx)); + if (i == loopPhiCache.length) loopPhiCache = Arrays.copyOf(loopPhiCache, loopPhiCache.length*2); + loopPhiCache[i++] = value; + } + } + i = 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) cacheValues.put(phi, loopPhiCache[i++]); + } + } + + /** + * Calculate the values of phis of the region and caches the values. The phis are not allowed to depend on other phis of the region. + */ + private void latchPhis(RegionNode region, Node prev) { + int idx = Utils.find(region._inputs, prev); + assert idx > 0; + for( Node use : region._outputs ) { + if (use instanceof PhiNode phi) { + var value = getValue(phi.in(idx)); + cacheValues.put(phi, value); + } + } + } + + /** + * Run the graph until either a return is found or the number of loop iterations are done. + */ + private Result evaluate(StartNode start, long parameter, int loops) { + var parameter1 = findProjection(start, 1); + if (parameter1 != null) cacheValues.put(parameter1, parameter); + Node control = findProjection(start, 0); + Node prev = start; + while (control != null) { + Node next; + switch (control) { + case RegionNode region -> { + if (region instanceof LoopNode && region.in(1) != prev) { + if (loops--<=0) return new Result(ResultType.TIMEOUT, 0); + latchLoopPhis(region, prev); + } else { + latchPhis(region, prev); + } + next = findControl(region); + } + case IfNode cond -> next = findProjection(cond, getValue(cond.in(1)) != 0 ? 0 : 1); + case ReturnNode ret -> { + return new Result(ResultType.VALUE, getValue(ret.in(1))); + } + case ProjNode ignored -> next = findControl(control); + default -> throw Utils.TODO("Unexpected control node " + control); + } + prev = control; + control = next; + } + return new Result(ResultType.FALLTHROUGH, 0); + } + + public static long evaluate(Node graph) { + return evaluate(graph, 0); + } + + public static long evaluate(Node graph, long parameter) { + return evaluate(graph, parameter, 1000); + } + + public static long evaluate(Node graph, long parameter, int loops) { + var res = evaluateWithResult(graph, parameter, loops); + if (res.type==ResultType.TIMEOUT) throw new RuntimeException("Timeout"); + return res.value; + } + + public static Result evaluateWithResult(Node graph, long parameter, int loops) { + var start = findStart(new BitSet(), graph); + if (start == null) return new Result(ResultType.TIMEOUT, 0); + var evaluator = new GraphEvaluator(); + return evaluator.evaluate(start, parameter, loops); + } + +} diff --git a/chapter08/src/main/java/com/seaofnodes/simple/GraphVisualizer.java b/chapter08/src/main/java/com/seaofnodes/simple/GraphVisualizer.java index 5009264f..d75e5bea 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/GraphVisualizer.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/GraphVisualizer.java @@ -30,7 +30,7 @@ public class GraphVisualizer { sb.append("/*\n"); sb.append(parser.src()); sb.append("\n*/\n"); - + // To keep the Scopes below the graph and pointing up into the graph we // need to group the Nodes in a subgraph cluster, and the scopes into a // different subgraph cluster. THEN we can draw edges between the @@ -50,7 +50,7 @@ public class GraphVisualizer { // Just the Nodes first, in a cluster no edges nodes(sb, all); - + // Now the scopes, in a cluster no edges for( ScopeNode scope : parser._xScopes ) scope( sb, scope ); @@ -61,7 +61,7 @@ public class GraphVisualizer { // Walk the active Scope edges for( ScopeNode scope : parser._xScopes ) scopeEdges( sb, scope ); - + sb.append("}\n"); return sb.toString(); } @@ -195,13 +195,13 @@ public class GraphVisualizer { sb.append(" color=red"); // Backedges do not add a ranking constraint if( i==2 && (n instanceof PhiNode || n instanceof LoopNode) ) - sb.append(" constraint=false"); + sb.append(" constraint=false"); sb.append("];\n"); } } } } - + // Walk the scope edges private void scopeEdges( StringBuilder sb, ScopeNode scope ) { sb.append("\tedge [style=dashed color=cornflowerblue];\n"); @@ -228,7 +228,7 @@ public class GraphVisualizer { level++; } } - + /** * Finds all nodes in the graph. */ diff --git a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java index 45332396..d4b0c327 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/Parser.java @@ -13,7 +13,7 @@ import java.util.*; * This is a simple recursive descent parser. All lexical analysis is done here as well. */ public class Parser { - + /** * A Global Static, unique to each compilation. This is a public, so we * can make constants everywhere without having to thread the StartNode @@ -57,7 +57,7 @@ public class Parser { add("while"); }}; - + /** * We clone ScopeNodes when control flows branch; it is useful to have * a list of all active ScopeNodes for purposes of visualization of the SoN graph @@ -82,12 +82,12 @@ public class Parser { @Override public String toString() { return _lexer.toString(); } - + String src() { return new String( _lexer._input ); } // Debugging utility to find a Node by index public static Node find(int nid) { return START.find(nid); } - + private Node ctrl() { return _scope.ctrl(); } private Node ctrl(Node n) { return _scope.ctrl(n); } @@ -108,7 +108,7 @@ public class Parser { return STOP; } - + /** * Parses a block * @@ -199,7 +199,7 @@ public class Parser { // No continues yet _continueScope = null; - + // Parse the true side, which corresponds to loop body // Our current scope is the body Scope ctrl(ifT); // set ctrl token to ifTrue projection @@ -283,7 +283,7 @@ public class Parser { ctrl(ifT); // set ctrl token to ifTrue projection parseStatement(); // Parse true-side ScopeNode tScope = _scope; - + // Parse the false side _scope = fScope; // Restore scope, then parse else block if any ctrl(ifF); // Ctrl token is now set to ifFalse projection @@ -294,7 +294,7 @@ public class Parser { if( tScope.nIns() != ndefs || fScope.nIns() != ndefs ) throw error("Cannot define a new name on one arm of an if"); - + // Merge results _scope = tScope; _xScopes.pop(); // Discard pushed from graph display @@ -583,7 +583,7 @@ public class Parser { skipWhiteSpace(); return peek()==ch; } - + // Return an identifier or null String matchId() { skipWhiteSpace(); @@ -610,7 +610,7 @@ public class Parser { return TypeInteger.constant(Long.parseLong(snum)); } - // First letter of an identifier + // First letter of an identifier private boolean isIdStart(char ch) { return Character.isAlphabetic(ch) || ch == '_'; } @@ -626,7 +626,7 @@ public class Parser { return new String(_input, start, --_position - start); } - // + // private boolean isPunctuation(char ch) { return "=;[]<>()+-/*".indexOf(ch) != -1; } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/Utils.java b/chapter08/src/main/java/com/seaofnodes/simple/Utils.java index 4d663c25..45f15327 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/Utils.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/Utils.java @@ -36,4 +36,4 @@ public class Utils { return i; return -1; } -}
\ No newline at end of file +} diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/AddNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/AddNode.java index 5878f340..84a368fd 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -8,7 +8,7 @@ public class AddNode extends Node { public AddNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Add"; } - + @Override public String glabel() { return "+"; } @Override @@ -17,7 +17,7 @@ public class AddNode extends Node { in(2)._print0(sb.append("+"), visited); return sb.append(")"); } - + @Override public Type compute() { @@ -44,13 +44,13 @@ public class AddNode extends Node { // canonicalize to (x+0) if( t2 instanceof TypeInteger i && i.value()==0 ) return lhs; - + // Add of same to a multiply by 2 if( lhs==rhs ) return new MulNode(lhs,new ConstantNode(TypeInteger.constant(2)).peephole()); // Goal: a left-spine set of adds, with constants on the rhs (which then fold). - + // Move non-adds to RHS if( !(lhs instanceof AddNode) && rhs instanceof AddNode ) return swap12(); @@ -74,7 +74,7 @@ public class AddNode extends Node { // the loop will peep as dead after a bit. if( lhs.in(1) == lhs ) return null; - + // Do we have (x + con1) + con2? // Replace with (x + (con1+con2) which then fold the constants if( lhs.in(2)._type.isConstant() && t2.isConstant() ) @@ -88,12 +88,12 @@ public class AddNode extends Node { if( phicon!=null ) return phicon; // Now we sort along the spline via rotates, to gather similar things together. - + // Do we rotate (x + y) + z // into (x + z) + y ? if( spline_cmp(lhs.in(2),rhs) ) return new AddNode(new AddNode(lhs.in(1),rhs).peephole(),lhs.in(2)); - + return null; } @@ -111,11 +111,11 @@ public class AddNode extends Node { lphi = pcon(lhs.in(2)); // Will rotate with the Phi push } if( lphi==null ) return null; - + // RHS is a constant or a Phi of constants if( !(rhs instanceof ConstantNode con) && pcon(rhs)==null ) return null; - + // If both are Phis, must be same Region if( rhs instanceof PhiNode && lphi.in(0) != rhs.in(0) ) return null; @@ -137,7 +137,7 @@ public class AddNode extends Node { static PhiNode pcon(Node op) { return op instanceof PhiNode phi && phi.allCons() ? phi : null; } - + // Compare two off-spline nodes and decide what order they should be in. // Do we rotate ((x + hi) + lo) into ((x + lo) + hi) ? // Generally constants always go right, then Phi-of-constants, then muls, then others. @@ -146,16 +146,16 @@ public class AddNode extends Node { static boolean spline_cmp( Node hi, Node lo ) { if( lo._type.isConstant() ) return false; if( hi._type.isConstant() ) return true ; - + if( lo instanceof PhiNode && lo.allCons() ) return false; if( hi instanceof PhiNode && hi.allCons() ) return true ; if( lo instanceof PhiNode && !(hi instanceof PhiNode) ) return true; if( hi instanceof PhiNode && !(lo instanceof PhiNode) ) return false; - + // Same category of "others" return lo._nid > hi._nid; } - + @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/BoolNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/BoolNode.java index d65fbf14..0c32d50d 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/BoolNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/BoolNode.java @@ -12,7 +12,7 @@ abstract public class BoolNode extends Node { } abstract String op(); // String opcode name - + @Override public String label() { return getClass().getSimpleName(); } @@ -41,7 +41,7 @@ abstract public class BoolNode extends Node { @Override public Node idealize() { - // Compare of same + // Compare of same if( in(1)==in(2) ) return new ConstantNode(TypeInteger.constant(doOp(3,3)?1:0)); diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/ConstantNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/ConstantNode.java index 0e13d2f2..13006bfb 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/ConstantNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/ConstantNode.java @@ -23,10 +23,10 @@ public class ConstantNode extends Node { super(Parser.START); _con = type; } - + @Override public String label() { return ""+_con; } - + @Override public String uniqueName() { return "Con_" + _nid; } @@ -34,9 +34,9 @@ public class ConstantNode extends Node { StringBuilder _print1(StringBuilder sb, BitSet visited) { return _con._print(sb); } - + @Override public boolean isMultiTail() { return true; } - + @Override public Type compute() { return _con; } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/DivNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/DivNode.java index b0e12547..2213d2e7 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/DivNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/DivNode.java @@ -18,7 +18,7 @@ public class DivNode extends Node { in(2)._print0(sb.append("/"), visited); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && @@ -34,6 +34,6 @@ public class DivNode extends Node { @Override public Node idealize() { return null; } - + @Override Node copy(Node lhs, Node rhs) { return new DivNode(lhs,rhs); } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/IfNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/IfNode.java index 1d1da4fa..23a8fafc 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -47,7 +47,7 @@ public class IfNode extends MultiNode { // Repeated test, dominated on one side. Test result is the same. ? (proj._idx==0 ? TypeTuple.IF_TRUE : TypeTuple.IF_FALSE) : dom._type; // Repeated test not dominated on one side - + return TypeTuple.IF_BOTH; } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java index 0b84f897..c192bc20 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/LoopNode.java @@ -25,5 +25,5 @@ public class LoopNode extends RegionNode { return inProgress() ? null : super.idealize(); } - @Override Node idom() { return entry(); } + @Override Node idom() { return entry(); } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/MinusNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/MinusNode.java index 8a96693d..3d944fd4 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/MinusNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/MinusNode.java @@ -9,15 +9,15 @@ public class MinusNode extends Node { public MinusNode(Node in) { super(null, in); } @Override public String label() { return "Minus"; } - + @Override public String glabel() { return "-"; } - + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("(-"), visited); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0) diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/MulNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/MulNode.java index 70e6c0db..2e701a4e 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -9,7 +9,7 @@ public class MulNode extends Node { public MulNode(Node lhs, Node rhs) { super(null, lhs, rhs); } @Override public String label() { return "Mul"; } - + @Override public String glabel() { return "*"; } @Override @@ -36,12 +36,12 @@ public class MulNode extends Node { Node rhs = in(2); Type t1 = lhs._type; Type t2 = rhs._type; - + // Mul of 1. We do not check for (1*x) because this will already // canonicalize to (x*1) if ( t2.isConstant() && t2 instanceof TypeInteger i && i.value()==1 ) return lhs; - + // Move constants to RHS: con*arg becomes arg*con if ( t1.isConstant() && !t2.isConstant() ) return swap12(); diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/MultiNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/MultiNode.java index 81c90f68..7ba1aa19 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/MultiNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/MultiNode.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.node; public abstract class MultiNode extends Node { - + public MultiNode(Node... inputs) { super(inputs); } } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java index fd312c3d..2d6d5ad5 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/Node.java @@ -47,7 +47,7 @@ public abstract class Node { */ public Type _type; - + /** * Immediate dominator tree depth, used to approximate a real IDOM during * parsing where we do not have the whole program, and also peepholes @@ -56,7 +56,7 @@ public abstract class Node { * See {@link <a href="https://en.wikipedia.org/wiki/Dominator_(graph_theory)">...</a>} */ int _idepth; - + /** * A private Global Static mutable counter, for unique node id generation. * To make the compiler multithreaded, this field will have to move into a TLS. @@ -85,9 +85,9 @@ public abstract class Node { // ------------------------------------------------------------------------ - + // Debugger Printing. - + // {@code toString} is what you get in the debugger. It has to print 1 // line (because this is what a debugger typically displays by default) and // has to be robust with broken graph/nodes. @@ -101,7 +101,7 @@ public abstract class Node { public final String print() { return _print0(new StringBuilder(), new BitSet()).toString(); } - + // This is the common print: check for repeats, check for DEAD and print // "DEAD" else call the per-Node print1. final StringBuilder _print0(StringBuilder sb, BitSet visited) { @@ -141,13 +141,13 @@ public abstract class Node { } public String p(int depth) { return IRPrinter.prettyPrint(this,depth); } - + public boolean isMultiHead() { return false; } public boolean isMultiTail() { return false; } - + // ------------------------------------------------------------------------ // Graph Node & Edge manipulation - + /** * Gets the ith input node * @param i Offset of the input node @@ -162,19 +162,19 @@ public abstract class Node { public boolean isUnused() { return nOuts() == 0; } public boolean isCFG() { return false; } - + /** * Change a <em>def</em> into a Node. Keeps the edges correct, by removing * the corresponding <em>use->def</em> edge. This may make the original * <em>def</em> go dead. This function is co-recursive with {@link #kill}. * <p> - + * This method is the normal path for altering a Node, because it does the * proper default edge maintenance. It also <em>immediately</em> kills * Nodes that lose their last use; at times care must be taken to avoid * killing Nodes that are being used without having an output Node. This * definitely happens in the middle of recursive {@link #peephole} calls. - * + * * @param idx which def to set * @param new_def the new definition * @return new_def for flow coding @@ -195,7 +195,7 @@ public abstract class Node { // Return self for easy flow-coding return new_def; } - + // Remove the numbered input, compressing the inputs in-place. This // shuffles the order deterministically - which is suitable for Region and // Phi, but not for every Node. @@ -244,7 +244,7 @@ public abstract class Node { old_def.kill(); // Kill old def } } - + /** * Kill a Node with no <em>uses</em>, by setting all of its <em>defs</em> * to null. This may recursively kill more Nodes and is basically dead @@ -278,10 +278,10 @@ public abstract class Node { } kill(); } - + // ------------------------------------------------------------------------ // Graph-based optimizations - + /** * We allow disabling peephole opt so that we can observe the * full graph, vs the optimized graph. @@ -306,7 +306,7 @@ public abstract class Node { public final Node peephole( ) { // Compute initial or improved Type Type type = _type = compute(); - + if (_disablePeephole) return this; // Peephole optimizations turned off @@ -315,13 +315,13 @@ public abstract class Node { return deadCodeElim(new ConstantNode(type).peephole()); // Future chapter: Global Value Numbering goes here - + // Ask each node for a better replacement Node n = idealize(); if( n != null ) // Something changed // Recursively optimize return deadCodeElim(n.peephole()); - + return this; // No progress } @@ -341,7 +341,7 @@ public abstract class Node { } return m; } - + /** * This function needs to be * <a href="https://en.wikipedia.org/wiki/Monotonic_function">Monotonic</a> @@ -410,7 +410,7 @@ public abstract class Node { // ------------------------------------------------------------------------ // Peephole utilities - + // Swap inputs without letting either input go dead during the swap. Node swap12() { Node tmp = in(1); @@ -418,7 +418,7 @@ public abstract class Node { _inputs.set(2,tmp); return this; } - + // does this node contain all constants? // Ignores in(0), as is usually control. boolean allCons() { diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/NotNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/NotNode.java index 04e6c75b..39df410d 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/NotNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/NotNode.java @@ -9,15 +9,15 @@ public class NotNode extends Node { public NotNode(Node in) { super(null, in); } @Override public String label() { return "Not"; } - + @Override public String glabel() { return "!"; } - + @Override StringBuilder _print1(StringBuilder sb, BitSet visited) { in(1)._print0(sb.append("(!"), visited); return sb.append(")"); } - + @Override public Type compute() { if( in(1)._type instanceof TypeInteger i0 ) diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java index 975630d0..c7b5b357 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/PhiNode.java @@ -7,7 +7,7 @@ import java.util.BitSet; public class PhiNode extends Node { final String _label; - + public PhiNode(String label, Node... inputs) { super(inputs); _label = label; } @Override public String label() { return "Phi_"+_label; } @@ -35,7 +35,7 @@ public class PhiNode extends Node { @Override public Type compute() { if( !(region() instanceof RegionNode r) || r.inProgress() ) - return Type.BOTTOM; + return Type.BOTTOM; Type t = Type.TOP; for (int i = 1; i < nIns(); i++) t = t.meet(in(i)._type); @@ -53,7 +53,7 @@ public class PhiNode extends Node { return live; // Pull "down" a common data op. One less op in the world. One more - // Phi, but Phis do not make code. + // Phi, but Phis do not make code. // Phi(op(A,B),op(Q,R),op(X,Y)) becomes // op(Phi(A,Q,X), Phi(B,R,Y)). Node op = in(1); diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/ProjNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/ProjNode.java index 79ba9d13..c263502d 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/ProjNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/ProjNode.java @@ -12,7 +12,7 @@ public class ProjNode extends Node { // Debugging label public final String _label; - + public ProjNode(MultiNode ctrl, int idx, String label) { super(ctrl); _idx = idx; diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java index 00c010b2..453d028f 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/RegionNode.java @@ -9,7 +9,7 @@ import java.util.BitSet; public class RegionNode extends Node { public RegionNode(Node... nodes) { super(nodes); } - + @Override public String label() { return "Region"; } diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 4dea773a..312058b9 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -21,7 +21,7 @@ public class ReturnNode extends Node { public Node ctrl() { return in(0); } public Node expr() { return in(1); } - + @Override public String label() { return "Return"; } @@ -31,7 +31,7 @@ public class ReturnNode extends Node { } @Override public boolean isCFG() { return true; } - + @Override public Type compute() { return new TypeTuple(ctrl()._type,expr()._type); diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index a6a7f536..e5d03d93 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -28,8 +28,8 @@ public class ScopeNode extends Node { _scopes = new Stack<>(); _type = Type.BOTTOM; } - - + + @Override public String label() { return "Scope"; } @Override @@ -63,7 +63,7 @@ public class ScopeNode extends Node { names[syms.get(name)] = name; return names; } - + @Override public Type compute() { return Type.BOTTOM; } @Override public Node idealize() { return null; } @@ -190,7 +190,7 @@ public class ScopeNode extends Node { that.kill(); // Kill merged scope return r.unkeep().peephole(); } - + // Merge the backedge scope into this loop head scope // We set the second input to the phi from the back edge (i.e. loop body) public void endLoop(ScopeNode back, ScopeNode exit ) { diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java index 19d03e0f..01f1485a 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/StartNode.java @@ -15,7 +15,7 @@ import java.util.BitSet; public class StartNode extends MultiNode { final TypeTuple _args; - + public StartNode(Type[] args) { super(); _args = new TypeTuple(args); diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/StopNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/StopNode.java index a0aacf2b..417790d9 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/StopNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/StopNode.java @@ -30,7 +30,7 @@ public class StopNode extends Node { public ReturnNode ret() { return nIns()==1 ? (ReturnNode)in(0) : null; } - + @Override public Type compute() { return Type.BOTTOM; diff --git a/chapter08/src/main/java/com/seaofnodes/simple/node/SubNode.java b/chapter08/src/main/java/com/seaofnodes/simple/node/SubNode.java index 1484ab8a..4a06fcb3 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/node/SubNode.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/node/SubNode.java @@ -18,7 +18,7 @@ public class SubNode extends Node { in(2)._print0(sb.append("-"), visited); return sb.append(")"); } - + @Override public Type compute() { if (in(1)._type instanceof TypeInteger i0 && diff --git a/chapter08/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter08/src/main/java/com/seaofnodes/simple/type/Type.java index f88403a5..2f0e6171 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/type/Type.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/type/Type.java @@ -4,7 +4,7 @@ package com.seaofnodes.simple.type; /** * These types are part of a Monotone Analysis Framework, * @see <a href="https://www.cse.psu.edu/~gxt29/teaching/cse597s21/slides/08monotoneFramework.pdf">see for example this set of slides</a>. - * <p> + * <p> * The types form a lattice; @see <a href="https://en.wikipedia.org/wiki/Lattice_(order)">a symmetric complete bounded (ranked) lattice.</a> * <p> * This wild lattice theory will be needed later to allow us to easily beef up @@ -15,7 +15,7 @@ package com.seaofnodes.simple.type; * actual implementation is darn near trivial and is generally really obvious * what we're doing with it. Right now, it's just simple integer math to do * simple constant folding e.g. 1+2 == 3 stuff. - */ + */ public class Type { diff --git a/chapter08/src/main/java/com/seaofnodes/simple/type/TypeInteger.java b/chapter08/src/main/java/com/seaofnodes/simple/type/TypeInteger.java index 93f5eae3..b30e21d8 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/type/TypeInteger.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/type/TypeInteger.java @@ -28,7 +28,7 @@ public class TypeInteger extends Type { public boolean isTop() { return !_is_con && _con==0; } public boolean isBot() { return !_is_con && _con==1; } - @Override + @Override public StringBuilder _print(StringBuilder sb) { if (isTop()) return sb.append("IntTop"); if (isBot()) return sb.append("IntBot"); diff --git a/chapter08/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter08/src/main/java/com/seaofnodes/simple/type/TypeTuple.java index f8c3b3c8..0f8b95bd 100644 --- a/chapter08/src/main/java/com/seaofnodes/simple/type/TypeTuple.java +++ b/chapter08/src/main/java/com/seaofnodes/simple/type/TypeTuple.java @@ -1,7 +1,7 @@ package com.seaofnodes.simple.type; public class TypeTuple extends Type { - + public final Type[] _types; public TypeTuple(Type... _types) { 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 <code>fuzzPeeps</code> methods.
- * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line
- * via <code>mvn clean test -Dtest=com.seaofnodes.simple.Fuzzer08Test#fuzzPeeps</code>
- */
-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 <code>fuzzPeeps</code> methods. + * This can be done from IntelliJ Gui or remove the `@Ignore` annotation and start the test case from the command line + * via <code>mvn clean test -Dtest=com.seaofnodes.simple.Fuzzer08Test#fuzzPeeps</code> + */ +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<Throwable> 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<String> 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<Throwable> 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<String> 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<o1.length; i++) {
- if (!isExceptionFromSameCause(o1[i], o2[i])) return false; // Different suppression
- }
- return true;
- }
-
- /**
- * Parse script with peepholes enabled or disabled
- */
- public static StopNode parse(String script, boolean runPeeps) {
- var parser = new Parser(script);
- Node._disablePeephole = !runPeeps;
- return parser.parse();
- }
-
-}
+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<o1.length; i++) { + if (!isExceptionFromSameCause(o1[i], o2[i])) return false; // Different suppression + } + return true; + } + + /** + * Parse script with peepholes enabled or disabled + */ + public static StopNode parse(String script, boolean runPeeps) { + var parser = new Parser(script); + Node._disablePeephole = !runPeeps; + return parser.parse(); + } + +} diff --git a/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java b/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java index 355793bf..b7fc18ec 100644 --- a/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java +++ b/chapter08/src/test/java/com/seaofnodes/simple/fuzzer/Reducer.java @@ -1,144 +1,144 @@ -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<String> 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<String> 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<String> 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<String> 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<String> 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<String> 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<String> 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<String> 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<String> getKeywords() {
- try {
- var field = Parser.class.getDeclaredField("KEYWORDS");
- field.setAccessible(true);
- return (HashSet<String>) 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<String> 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<String> 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<<max;
- var num = random.nextInt(n);
- for (int i=max-1; i>=0; i--) {
- if ((num & (1<<i))!=0) return max-i-1;
- }
- return max;
- }
-
- /**
- * Helper function to print indentation.
- * @return sb for chaining
- */
- private StringBuilder printIndentation() {
- return sb.repeat(' ', indentation);
- }
-
- /**
- * Generate a random name for variables. This might be invalid when it is a keyword.
- * @return The random name generated
- */
- private StringBuilder getRandomName() {
- int len = random.nextInt(10) + 1;
- StringBuilder sb = new StringBuilder(len);
- sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10)));
- for (int i=1; i<len; i++)
- sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length())));
- return sb;
- }
-
- /**
- * Generate a variable name. This might be new random name or a name from an outer scope.
- * If the program is allowed to be invalid this can return keywords and already used variable names in the current scope.
- * @return The variable name.
- */
- private String getVarName() {
- if (currScopeStart > 0 && random.nextInt(10) > 7) {
- // Use a variable outside the current scope.
- var v = variables.get(random.nextInt(currScopeStart));
- if (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<num; i++) {
- printIndentation();
- var stop = genStatement();
- sb.append("\n");
- if ((stop & FLAG_STOP) != 0) return stop;
- }
- return 0;
- }
-
- /**
- * Generate a single statement
- * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement
- */
- public int genStatement() {
- return switch (random.nextInt(10)) {
- case 1 -> 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<String> getKeywords() { + try { + var field = Parser.class.getDeclaredField("KEYWORDS"); + field.setAccessible(true); + return (HashSet<String>) 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<String> 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<String> 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<<max; + var num = random.nextInt(n); + for (int i=max-1; i>=0; i--) { + if ((num & (1<<i))!=0) return max-i-1; + } + return max; + } + + /** + * Helper function to print indentation. + * @return sb for chaining + */ + private StringBuilder printIndentation() { + return sb.repeat(' ', indentation); + } + + /** + * Generate a random name for variables. This might be invalid when it is a keyword. + * @return The random name generated + */ + private StringBuilder getRandomName() { + int len = random.nextInt(10) + 1; + StringBuilder sb = new StringBuilder(len); + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()-10))); + for (int i=1; i<len; i++) + sb.append(VAR_CHARS.charAt(random.nextInt(VAR_CHARS.length()))); + return sb; + } + + /** + * Generate a variable name. This might be new random name or a name from an outer scope. + * If the program is allowed to be invalid this can return keywords and already used variable names in the current scope. + * @return The variable name. + */ + private String getVarName() { + if (currScopeStart > 0 && random.nextInt(10) > 7) { + // Use a variable outside the current scope. + var v = variables.get(random.nextInt(currScopeStart)); + if (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<num; i++) { + printIndentation(); + var stop = genStatement(); + sb.append("\n"); + if ((stop & FLAG_STOP) != 0) return stop; + } + return 0; + } + + /** + * Generate a single statement + * @return flags FLAG_STOP and FLAG_IF_WITHOUT_ELSE for the generated statement + */ + public int genStatement() { + return switch (random.nextInt(10)) { + case 1 -> 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()))); + } + } + +} |