From b1df3ff8c890bf6d4cc16fb4f28ddb7833512d71 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Mon, 4 Apr 2016 14:15:27 -0400 Subject: The optimizer is working :) --- .../java/bjc/dicelang/ast/DiceASTOptimizer.java | 144 -------------- .../ast/optimization/DiceASTOptimizer.java | 215 +++++++++++++++++++++ .../dicelang/ast/optimization/package-info.java | 6 + 3 files changed, 221 insertions(+), 144 deletions(-) delete mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/optimization/DiceASTOptimizer.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/optimization/package-info.java (limited to 'dice-lang/src/main/java') diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java deleted file mode 100644 index f5a6696..0000000 --- a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java +++ /dev/null @@ -1,144 +0,0 @@ -package bjc.dicelang.ast; - -import java.util.HashMap; -import java.util.Map; -import java.util.function.BiFunction; -import java.util.function.BinaryOperator; - -import bjc.dicelang.IDiceExpression; -import bjc.dicelang.ast.nodes.DiceASTType; -import bjc.dicelang.ast.nodes.IDiceASTNode; -import bjc.dicelang.ast.nodes.LiteralDiceNode; -import bjc.dicelang.ast.nodes.OperatorDiceNode; - -import static bjc.dicelang.ast.nodes.DiceASTType.*; - -import bjc.utils.parserutils.AST; - -/** - * Optimize an AST - * - * @author ben - * - */ -public class DiceASTOptimizer { - private static final class ArithmeticOperationCollapser - implements BinaryOperator> { - private IDiceASTNode type; - private BiFunction valueCollapser; - private boolean doSwap; - - public ArithmeticOperationCollapser(IDiceASTNode type, - BiFunction valueCollapser, - boolean doSwap) { - this.type = type; - this.valueCollapser = valueCollapser; - this.doSwap = doSwap; - } - - @Override - public AST apply(AST leftAST, - AST rightAST) { - boolean isLeftConstant = - DiceASTOptimizer.checkNodeType(leftAST, LITERAL) - && DiceASTOptimizer.isNodeConstant(leftAST); - - boolean isRightConstant = - DiceASTOptimizer.checkNodeType(rightAST, LITERAL) - && DiceASTOptimizer.isNodeConstant(leftAST); - - if (isLeftConstant) { - if (isRightConstant) { - int combinedValue = valueCollapser.apply( - getNodeValue(leftAST), getNodeValue(rightAST)); - - return new AST<>(new LiteralDiceNode(combinedValue)); - } - - if (doSwap) { - return new AST<>(type, rightAST, leftAST); - } - } - - return new AST<>(type, leftAST, rightAST); - } - } - - private static Map>> - buildConstantCollapsers() { - Map>> operatorCollapsers = - new HashMap<>(); - - operatorCollapsers.put(OperatorDiceNode.ADD, - new ArithmeticOperationCollapser(OperatorDiceNode.ADD, - (leftVal, rightVal) -> leftVal + rightVal, true)); - operatorCollapsers.put(OperatorDiceNode.SUBTRACT, - new ArithmeticOperationCollapser(OperatorDiceNode.SUBTRACT, - (leftVal, rightVal) -> leftVal - rightVal, false)); - operatorCollapsers.put(OperatorDiceNode.DIVIDE, - new ArithmeticOperationCollapser(OperatorDiceNode.DIVIDE, - (leftVal, rightVal) -> leftVal / rightVal, false)); - operatorCollapsers.put(OperatorDiceNode.MULTIPLY, - new ArithmeticOperationCollapser(OperatorDiceNode.MULTIPLY, - (leftVal, rightVal) -> leftVal * rightVal, true)); - - return null; - } - - private static AST collapseLeaf(IDiceASTNode leaf) { - // Can't optimize a simple reference - if (leaf.getType() == VARIABLE) { - return new AST<>(leaf); - } else if (leaf.getType() == LITERAL) { - LiteralDiceNode node = (LiteralDiceNode) leaf; - - return new AST<>(optimizeLiteral(node, node.toExpression())); - } else { - throw new UnsupportedOperationException( - "Found leaf operator. This isn't supported"); - } - } - - private static IDiceASTNode optimizeLiteral(LiteralDiceNode node, - IDiceExpression leaf) { - if (leaf.canOptimize()) { - return new LiteralDiceNode(Integer.toString(leaf.optimize())); - } else { - return node; - } - } - - private static AST finishTree(AST tree) { - return tree; - } - - /** - * Optimize a tree of expressions into a simpler form - * - * @param tree - * The tree to optimize - * @return The optimized tree - */ - public static AST optimizeTree(AST tree) { - AST astWithFoldedConstants = - tree.collapse(DiceASTOptimizer::collapseLeaf, - buildConstantCollapsers()::get, - DiceASTOptimizer::finishTree); - return astWithFoldedConstants; - } - - private static boolean checkNodeType(AST ast, - DiceASTType type) { - return ast.applyToHead((node) -> node.getType()) == type; - } - - private static boolean isNodeConstant(AST ast) { - return ast.applyToHead( - (node) -> ((LiteralDiceNode) node).isConstant()); - } - - private static int getNodeValue(AST ast) { - return ast.applyToHead( - (node) -> ((LiteralDiceNode) node).toConstant()); - } -} diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/optimization/DiceASTOptimizer.java b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/DiceASTOptimizer.java new file mode 100644 index 0000000..e6c62ee --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/DiceASTOptimizer.java @@ -0,0 +1,215 @@ +package bjc.dicelang.ast.optimization; + +import java.util.HashMap; +import java.util.Map; +import java.util.function.BiFunction; +import java.util.function.BinaryOperator; + +import bjc.dicelang.IDiceExpression; +import bjc.dicelang.ast.nodes.DiceASTType; +import bjc.dicelang.ast.nodes.IDiceASTNode; +import bjc.dicelang.ast.nodes.LiteralDiceNode; +import bjc.dicelang.ast.nodes.OperatorDiceNode; + +import static bjc.dicelang.ast.nodes.DiceASTType.*; + +import bjc.utils.parserutils.AST; + +/** + * Optimize an AST + * + * @author ben + * + */ +public class DiceASTOptimizer { + private static final class NestedArithmeticOperationCollapser + implements BinaryOperator> { + private IDiceASTNode type; + private BiFunction valueCollapser; + + public NestedArithmeticOperationCollapser(IDiceASTNode type, + BiFunction valueCollapser) { + this.type = type; + this.valueCollapser = valueCollapser; + } + + @Override + public AST apply(AST leftAST, + AST rightAST) { + AST rightBranchOfLeftAST = + leftAST.applyToRight((rightSideAST) -> rightSideAST); + AST leftBranchOfLeftAST = + leftAST.applyToRight((rightSideAST) -> rightSideAST); + + boolean leftContainsNestedConstant = DiceASTOptimizer + .checkNodeType(rightBranchOfLeftAST, LITERAL) + && DiceASTOptimizer.isNodeConstant(leftAST); + + boolean isRightConstant = + DiceASTOptimizer.checkNodeType(rightAST, LITERAL) + && DiceASTOptimizer.isNodeConstant(leftAST); + + if (leftContainsNestedConstant && isRightConstant) { + int combinedValue = valueCollapser.apply( + getNodeValue(rightBranchOfLeftAST), + getNodeValue(rightAST)); + + AST newRightBranch = + new AST<>(new LiteralDiceNode(combinedValue)); + + return new AST<>(type, leftBranchOfLeftAST, + newRightBranch); + } + + return new AST<>(type, leftAST, rightAST); + } + } + + private static final class ArithmeticOperationCollapser + implements BinaryOperator> { + private IDiceASTNode type; + private BiFunction valueCollapser; + private boolean doSwap; + + public ArithmeticOperationCollapser(IDiceASTNode type, + BiFunction valueCollapser, + boolean doSwap) { + this.type = type; + this.valueCollapser = valueCollapser; + this.doSwap = doSwap; + } + + @Override + public AST apply(AST leftAST, + AST rightAST) { + boolean isLeftConstant = + DiceASTOptimizer.checkNodeType(leftAST, LITERAL) + && DiceASTOptimizer.isNodeConstant(leftAST); + + boolean isRightConstant = + DiceASTOptimizer.checkNodeType(rightAST, LITERAL) + && DiceASTOptimizer.isNodeConstant(leftAST); + + if (isLeftConstant) { + if (isRightConstant) { + int combinedValue = valueCollapser.apply( + getNodeValue(leftAST), getNodeValue(rightAST)); + + return new AST<>(new LiteralDiceNode(combinedValue)); + } + + if (doSwap) { + return new AST<>(type, rightAST, leftAST); + } + } + + return new AST<>(type, leftAST, rightAST); + } + } + + private static Map>> + buildConstantCollapsers() { + Map>> operatorCollapsers = + new HashMap<>(); + + operatorCollapsers.put(OperatorDiceNode.ADD, + new ArithmeticOperationCollapser(OperatorDiceNode.ADD, + (leftVal, rightVal) -> leftVal + rightVal, true)); + + operatorCollapsers.put(OperatorDiceNode.MULTIPLY, + new ArithmeticOperationCollapser(OperatorDiceNode.MULTIPLY, + (leftVal, rightVal) -> leftVal * rightVal, true)); + + operatorCollapsers.put(OperatorDiceNode.SUBTRACT, + new ArithmeticOperationCollapser(OperatorDiceNode.SUBTRACT, + (leftVal, rightVal) -> leftVal - rightVal, false)); + + operatorCollapsers.put(OperatorDiceNode.DIVIDE, + new ArithmeticOperationCollapser(OperatorDiceNode.DIVIDE, + (leftVal, rightVal) -> leftVal / rightVal, false)); + + return operatorCollapsers; + } + + private static Map>> + buildNestedConstantCollapsers() { + Map>> operatorCollapsers = + new HashMap<>(); + + operatorCollapsers.put(OperatorDiceNode.ADD, + new NestedArithmeticOperationCollapser( + OperatorDiceNode.ADD, + (leftVal, rightVal) -> leftVal + rightVal)); + + operatorCollapsers.put(OperatorDiceNode.MULTIPLY, + new NestedArithmeticOperationCollapser( + OperatorDiceNode.MULTIPLY, + (leftVal, rightVal) -> leftVal * rightVal)); + + return operatorCollapsers; + } + + private static AST collapseLeaf(IDiceASTNode leaf) { + // Can't optimize a simple reference + if (leaf.getType() == VARIABLE) { + return new AST<>(leaf); + } else if (leaf.getType() == LITERAL) { + LiteralDiceNode node = (LiteralDiceNode) leaf; + + return new AST<>(optimizeLiteral(node, node.toExpression())); + } else { + throw new UnsupportedOperationException( + "Found leaf operator. This isn't supported"); + } + } + + private static IDiceASTNode optimizeLiteral(LiteralDiceNode node, + IDiceExpression leaf) { + if (leaf.canOptimize()) { + return new LiteralDiceNode(Integer.toString(leaf.optimize())); + } else { + return node; + } + } + + private static AST finishTree(AST tree) { + return tree; + } + + /** + * Optimize a tree of expressions into a simpler form + * + * @param tree + * The tree to optimize + * @return The optimized tree + */ + public static AST optimizeTree(AST tree) { + AST astWithConstantsFolded = + tree.collapse(DiceASTOptimizer::collapseLeaf, + buildConstantCollapsers()::get, + DiceASTOptimizer::finishTree); + + AST astWithNestedConstantsFolded = + astWithConstantsFolded.collapse( + DiceASTOptimizer::collapseLeaf, + buildNestedConstantCollapsers()::get, + DiceASTOptimizer::finishTree); + + return astWithNestedConstantsFolded; + } + + private static boolean checkNodeType(AST ast, + DiceASTType type) { + return ast.applyToHead((node) -> node.getType()) == type; + } + + private static boolean isNodeConstant(AST ast) { + return ast.applyToHead( + (node) -> ((LiteralDiceNode) node).isConstant()); + } + + private static int getNodeValue(AST ast) { + return ast.applyToHead( + (node) -> ((LiteralDiceNode) node).toConstant()); + } +} diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/optimization/package-info.java b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/package-info.java new file mode 100644 index 0000000..132563d --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/package-info.java @@ -0,0 +1,6 @@ +/** + * Contains classes for optimizing ASTs + * @author ben + * + */ +package bjc.dicelang.ast.optimization; \ No newline at end of file -- cgit v1.2.3