From bf726639e1bc70b30dc5e5ae2cf349a5bbdfb0ae Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Sun, 10 Apr 2016 20:10:36 -0400 Subject: Moved things around for rewrite of AST mechanisms --- .../main/java/bjc/dicelang/ast/DiceASTParser.java | 70 +++++++ .../java/bjc/dicelang/ast/nodes/DiceASTType.java | 27 --- .../java/bjc/dicelang/ast/nodes/IDiceASTNode.java | 23 --- .../bjc/dicelang/ast/nodes/LiteralDiceNode.java | 192 ------------------ .../bjc/dicelang/ast/nodes/OperatorDiceNode.java | 92 --------- .../bjc/dicelang/ast/nodes/VariableDiceNode.java | 101 ---------- .../java/bjc/dicelang/ast/nodes/package-info.java | 6 - .../ast/optimization/DiceASTOptimizer.java | 210 -------------------- .../dicelang/ast/optimization/package-info.java | 6 - .../main/java/bjc/dicelang/ast/package-info.java | 6 + .../dicelang/old/ast/DiceASTDefinedChecker.java | 10 +- .../bjc/dicelang/old/ast/DiceASTExpression.java | 46 ++--- .../bjc/dicelang/old/ast/DiceASTFlattener.java | 10 +- .../java/bjc/dicelang/old/ast/DiceASTInliner.java | 6 +- .../java/bjc/dicelang/old/ast/DiceASTParser.java | 37 +--- .../dicelang/old/ast/DiceASTReferenceChecker.java | 10 +- .../bjc/dicelang/old/ast/IOperatorCollapser.java | 2 +- .../bjc/dicelang/old/ast/nodes/DiceASTType.java | 27 +++ .../bjc/dicelang/old/ast/nodes/IDiceASTNode.java | 23 +++ .../dicelang/old/ast/nodes/LiteralDiceNode.java | 217 +++++++++++++++++++++ .../dicelang/old/ast/nodes/OperatorDiceNode.java | 92 +++++++++ .../dicelang/old/ast/nodes/VariableDiceNode.java | 101 ++++++++++ .../bjc/dicelang/old/ast/nodes/package-info.java | 6 + .../old/ast/optimization/DiceASTOptimizer.java | 209 ++++++++++++++++++++ .../old/ast/optimization/package-info.java | 6 + 25 files changed, 798 insertions(+), 737 deletions(-) create mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/DiceASTParser.java delete mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/nodes/DiceASTType.java delete mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/nodes/IDiceASTNode.java delete mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/nodes/LiteralDiceNode.java delete mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/nodes/OperatorDiceNode.java delete mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/nodes/VariableDiceNode.java delete mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/nodes/package-info.java delete mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/optimization/DiceASTOptimizer.java delete mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/optimization/package-info.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/package-info.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/DiceASTType.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/IDiceASTNode.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/LiteralDiceNode.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/OperatorDiceNode.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/VariableDiceNode.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/package-info.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/old/ast/optimization/DiceASTOptimizer.java create mode 100644 dice-lang/src/main/java/bjc/dicelang/old/ast/optimization/package-info.java (limited to 'dice-lang/src/main/java') diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTParser.java b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTParser.java new file mode 100644 index 0000000..db2ba98 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTParser.java @@ -0,0 +1,70 @@ +package bjc.dicelang.ast; + +import java.util.InputMismatchException; + +import bjc.dicelang.old.ast.nodes.IDiceASTNode; +import bjc.dicelang.old.ast.nodes.LiteralDiceNode; +import bjc.dicelang.old.ast.nodes.OperatorDiceNode; +import bjc.dicelang.old.ast.nodes.VariableDiceNode; +import bjc.utils.funcdata.IFunctionalList; +import bjc.utils.parserutils.AST; +import bjc.utils.parserutils.TreeConstructor; + +/** + * Parse a string expression into AST form. Doesn't do anything else + * + * @author ben + * + */ +public class DiceASTParser { + /** + * Create an AST from a list of tokens + * + * @param tokens + * The list of tokens to convert + * @return An AST built from the tokens + */ + public static AST createFromString( + IFunctionalList tokens) { + AST rawTokens = + TreeConstructor.constructTree(tokens, (token) -> { + return isOperatorNode(token); + }, (operator) -> false, null); + // The last argument is valid because there are no special + // operators yet, so it'll never get called + + return rawTokens.rebuildTree(DiceASTParser::convertLeafNode, + DiceASTParser::convertOperatorNode); + } + + private static boolean isOperatorNode(String token) { + try { + OperatorDiceNode.fromString(token); + return true; + } catch (@SuppressWarnings("unused") IllegalArgumentException iaex) { + // We don't care about details + return false; + } + } + + private static IDiceASTNode convertLeafNode(String leafNode) { + if (LiteralDiceNode.isLiteral(leafNode)) { + return new LiteralDiceNode(leafNode); + } + + return new VariableDiceNode(leafNode); + } + + private static IDiceASTNode convertOperatorNode(String operatorNode) { + try { + return OperatorDiceNode.fromString(operatorNode); + } catch (IllegalArgumentException iaex) { + InputMismatchException imex = new InputMismatchException( + "Attempted to parse invalid operator " + operatorNode); + + imex.initCause(iaex); + + throw imex; + } + } +} diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/DiceASTType.java b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/DiceASTType.java deleted file mode 100644 index 9feb461..0000000 --- a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/DiceASTType.java +++ /dev/null @@ -1,27 +0,0 @@ -package bjc.dicelang.ast.nodes; - -/** - * An enum to represent the type of node an AST node is - * - * @author ben - * - */ -public enum DiceASTType { - /** - * A node that contains a literal value - */ - LITERAL, - /** - * A node that contains an operator expression - */ - OPERATOR, - /** - * A node that contains a variable reference - */ - VARIABLE; - - @Override - public String toString() { - return this.name().toLowerCase(); - } -} \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/IDiceASTNode.java b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/IDiceASTNode.java deleted file mode 100644 index afa0bcd..0000000 --- a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/IDiceASTNode.java +++ /dev/null @@ -1,23 +0,0 @@ -package bjc.dicelang.ast.nodes; - -/** - * The interface for a node in a dice AST - * - * @author ben - * - */ -public interface IDiceASTNode { - /** - * Check if this node represents an operator or not - * - * @return Whether or not this node represents an operator - */ - public boolean isOperator(); - - /** - * Get the type of AST node this node is - * - * @return The type of AST node this AST node is - */ - public DiceASTType getType(); -} \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/LiteralDiceNode.java b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/LiteralDiceNode.java deleted file mode 100644 index 1a6d2bf..0000000 --- a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/LiteralDiceNode.java +++ /dev/null @@ -1,192 +0,0 @@ -package bjc.dicelang.ast.nodes; - -import org.apache.commons.lang3.StringUtils; - -import bjc.dicelang.ComplexDice; -import bjc.dicelang.CompoundDice; -import bjc.dicelang.IDiceExpression; -import bjc.dicelang.ScalarDie; -import bjc.utils.data.Pair; -import bjc.utils.parserutils.AST; - -/** - * A AST node that represents a literal value - * - * @author ben - * - */ -public class LiteralDiceNode implements IDiceASTNode { - private static boolean isValidInfixOperator(String dat, String op) { - return StringUtils.countMatches(dat, op) == 1 - && !dat.equalsIgnoreCase(op) && !dat.startsWith(op); - } - - /** - * The value contained by this node - */ - private String value; - - /** - * Create a new node with the given value - * - * @param data - * The value to be in this node - */ - public LiteralDiceNode(String data) { - this.value = data; - } - - /** - * Create a new node with the given value - * - * @param val - * The value for this node - */ - public LiteralDiceNode(int val) { - this(Integer.toString(val)); - } - - /* - * (non-Javadoc) - * - * @see java.lang.Object#equals(java.lang.Object) - */ - @Override - public boolean equals(Object obj) { - if (this == obj) { - return true; - } else if (obj == null) { - return false; - } else if (getClass() != obj.getClass()) { - return false; - } else { - LiteralDiceNode other = (LiteralDiceNode) obj; - - if (value == null) { - if (other.value != null) { - return false; - } - } else if (!value.equals(other.value)) { - return false; - } - - return true; - } - } - - /** - * Get the data stored in this AST node - * - * @return the data stored in this AST node - */ - public String getData() { - return value; - } - - @Override - public DiceASTType getType() { - return DiceASTType.LITERAL; - } - - /* - * (non-Javadoc) - * - * @see java.lang.Object#hashCode() - */ - @Override - public int hashCode() { - final int prime = 31; - int result = 1; - result = prime * result + ((value == null) ? 0 : value.hashCode()); - return result; - } - - @Override - public boolean isOperator() { - return false; - } - - /** - * Parse this node into an expression - * - * @return The node in expression form - */ - public IDiceExpression toExpression() { - String literalData = this.getData(); - - if (LiteralDiceNode.isValidInfixOperator(literalData, "c")) { - String[] strangs = literalData.split("c"); - - return new CompoundDice(strangs); - } else if (LiteralDiceNode.isValidInfixOperator(literalData, - "d")) { - /* - * Handle dice groups - */ - return ComplexDice.fromString(literalData); - } else { - try { - return new ScalarDie(Integer.parseInt(literalData)); - } catch (NumberFormatException nfex) { - UnsupportedOperationException usex = new UnsupportedOperationException( - "Found malformed leaf token " + this); - - usex.initCause(nfex); - - throw usex; - } - } - } - - /** - * Parse this node into an expression - * - * @return The node as a pair of a sample value and the AST it - * represents - */ - public Pair> toParseValue() { - AST returnedAST = new AST<>(this); - - IDiceExpression expression = toExpression(); - - return new Pair<>(expression.roll(), returnedAST); - } - - /* - * (non-Javadoc) - * - * @see java.lang.Object#toString() - */ - @Override - public String toString() { - return value; - } - - /** - * Check if this node represents a constant value - * - * @return Whether or not this node represents a constant value - */ - public boolean isConstant() { - try { - Integer.parseInt(value); - return true; - } catch (@SuppressWarnings("unused") NumberFormatException nfex) { - // We don't care about details - return false; - } - } - - /** - * Return the constant value this node represents - * - * @return The constant value of this node - * - * @throws NumberFormatException - * if you call this on a node that doesn't represent a - * constant value - */ - public int toConstant() { - return Integer.parseInt(value); - } -} \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/OperatorDiceNode.java b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/OperatorDiceNode.java deleted file mode 100644 index 2820cfb..0000000 --- a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/OperatorDiceNode.java +++ /dev/null @@ -1,92 +0,0 @@ -package bjc.dicelang.ast.nodes; - -// The following classes need to be changed upon addition of a new operator -// 1. DiceASTExpression -// 2. DiceASTFlattener -// 3. DiceASTParser -/** - * A node that represents an operator - * - * @author ben - * - */ -public enum OperatorDiceNode implements IDiceASTNode { - /** - * Represents adding two nodes - */ - ADD, - /** - * Represents assigning one node to another - */ - ASSIGN, - /** - * Representings combining two node values together - */ - COMPOUND, - /** - * Represents dividing two nodes - */ - DIVIDE, - /** - * Represents using one node a variable number of times - */ - GROUP, - /** - * Represents multiplying two nodes - */ - MULTIPLY, - /** - * Represents subtracting two nodes - */ - SUBTRACT, - /** - * Represents executing one statement in the context of the other - */ - LET; - - /** - * Create a operator node from a string - * - * @param s - * The string to convert to a node - * @return The operator corresponding to the node - */ - public static OperatorDiceNode fromString(String s) { - switch (s) { - case ":=": - return ASSIGN; - case "+": - return ADD; - case "-": - return SUBTRACT; - case "*": - return MULTIPLY; - case "/": - return DIVIDE; - case "d": - return GROUP; - case "c": - return COMPOUND; - case "->": - return LET; - default: - throw new IllegalArgumentException( - s + " is not a valid operator node"); - } - } - - @Override - public DiceASTType getType() { - return DiceASTType.OPERATOR; - } - - /* - * (non-Javadoc) - * - * @see bjc.utils.dice.ast.IDiceASTNode#isOperator() - */ - @Override - public boolean isOperator() { - return true; - } -} diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/VariableDiceNode.java b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/VariableDiceNode.java deleted file mode 100644 index 29fd483..0000000 --- a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/VariableDiceNode.java +++ /dev/null @@ -1,101 +0,0 @@ -package bjc.dicelang.ast.nodes; - -/** - * A node that represents a variable reference - * - * @author ben - * - */ -public class VariableDiceNode implements IDiceASTNode { - /** - * The variable referenced by this node - */ - private String variableName; - - /** - * Create a new node representing the specified variable - * - * @param varName - * The name of the variable being referenced - */ - public VariableDiceNode(String varName) { - this.variableName = varName; - } - - /* - * (non-Javadoc) - * - * @see java.lang.Object#equals(java.lang.Object) - */ - @Override - public boolean equals(Object obj) { - // Handle special cases - if (this == obj) { - return true; - } else if (obj == null) { - return false; - } else if (getClass() != obj.getClass()) { - return false; - } else { - VariableDiceNode other = (VariableDiceNode) obj; - - if (variableName == null) { - if (other.variableName != null) { - return false; - } - } else if (!variableName.equals(other.variableName)) { - return false; - } - - return true; - } - } - - @Override - public DiceASTType getType() { - return DiceASTType.VARIABLE; - } - - /** - * Get the variable referenced by this AST node - * - * @return the variable referenced by this AST node - */ - public String getVariable() { - return variableName; - } - - /* - * (non-Javadoc) - * - * @see java.lang.Object#hashCode() - */ - @Override - public int hashCode() { - final int prime = 31; - int result = 1; - result = prime * result - + ((variableName == null) ? 0 : variableName.hashCode()); - return result; - } - - /* - * (non-Javadoc) - * - * @see bjc.utils.dice.ast.IDiceASTNode#isOperator() - */ - @Override - public boolean isOperator() { - return false; - } - - /* - * (non-Javadoc) - * - * @see java.lang.Object#toString() - */ - @Override - public String toString() { - return variableName; - } -} \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/package-info.java b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/package-info.java deleted file mode 100644 index 97f1990..0000000 --- a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/package-info.java +++ /dev/null @@ -1,6 +0,0 @@ -/** - * This package contains the various Node types in the Dice AST - * @author ben - * - */ -package bjc.dicelang.ast.nodes; \ No newline at end of file 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 deleted file mode 100644 index f6be7ab..0000000 --- a/dice-lang/src/main/java/bjc/dicelang/ast/optimization/DiceASTOptimizer.java +++ /dev/null @@ -1,210 +0,0 @@ -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())); - } - - 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 deleted file mode 100644 index 132563d..0000000 --- a/dice-lang/src/main/java/bjc/dicelang/ast/optimization/package-info.java +++ /dev/null @@ -1,6 +0,0 @@ -/** - * Contains classes for optimizing ASTs - * @author ben - * - */ -package bjc.dicelang.ast.optimization; \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/package-info.java b/dice-lang/src/main/java/bjc/dicelang/ast/package-info.java new file mode 100644 index 0000000..105af50 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/package-info.java @@ -0,0 +1,6 @@ +/** + * New implementation of AST for dice-lang + * @author ben + * + */ +package bjc.dicelang.ast; \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTDefinedChecker.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTDefinedChecker.java index 4a20a82..e279d8e 100644 --- a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTDefinedChecker.java +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTDefinedChecker.java @@ -3,9 +3,9 @@ package bjc.dicelang.old.ast; import java.util.Map; import java.util.function.Consumer; -import bjc.dicelang.ast.nodes.DiceASTType; -import bjc.dicelang.ast.nodes.IDiceASTNode; -import bjc.dicelang.ast.nodes.VariableDiceNode; +import bjc.dicelang.old.ast.nodes.DiceASTType; +import bjc.dicelang.old.ast.nodes.IDiceASTNode; +import bjc.dicelang.old.ast.nodes.VariableDiceNode; import bjc.utils.data.IHolder; /** @@ -54,8 +54,8 @@ public final class DiceASTDefinedChecker VariableDiceNode node = (VariableDiceNode) astNode; return !enviroment.containsKey(node.getVariable()); - } else { - return false; } + + return false; } } \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTExpression.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTExpression.java index 7651093..e6dca9e 100644 --- a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTExpression.java +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTExpression.java @@ -7,11 +7,11 @@ import java.util.function.Function; import bjc.dicelang.ComplexDice; 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 bjc.dicelang.ast.nodes.VariableDiceNode; +import bjc.dicelang.old.ast.nodes.DiceASTType; +import bjc.dicelang.old.ast.nodes.IDiceASTNode; +import bjc.dicelang.old.ast.nodes.LiteralDiceNode; +import bjc.dicelang.old.ast.nodes.OperatorDiceNode; +import bjc.dicelang.old.ast.nodes.VariableDiceNode; import bjc.utils.data.GenHolder; import bjc.utils.data.Pair; import bjc.utils.funcdata.bst.ITreePart.TreeLinearizationMethod; @@ -79,8 +79,8 @@ public class DiceASTExpression implements IDiceExpression { * The enviroment to evaluate bindings and such against * @return The operations to use when collapsing the AST */ - private static Map - buildOperations(Map enviroment) { + private static Map buildOperations( + Map enviroment) { Map operatorCollapsers = new HashMap<>(); @@ -111,14 +111,13 @@ public class DiceASTExpression implements IDiceExpression { DiceASTExpression::parseGroup); operatorCollapsers.put(OperatorDiceNode.LET, (left, right) -> { - return doLet(enviroment, left, right); + return doLet(left, right); }); return operatorCollapsers; } private static Pair> doLet( - Map enviroment, Pair> left, Pair> right) { return left.merge((leftValue, leftAST) -> { @@ -127,21 +126,10 @@ public class DiceASTExpression implements IDiceExpression { .applyToHead(DiceASTExpression::isAssignNode)) { // Just ignore the left block then return new Pair<>(rightValue, rightAST); - } else { - // Left block has an assignment to handle - String varName = leftAST.applyToLeft((leftBranch) -> { - return getAssignmentVar(leftBranch); - }); - - return null; } - }); - }); - } - private static String getAssignmentVar(AST leftBranch) { - return leftBranch.applyToHead((node) -> { - return ((VariableDiceNode) node).getVariable(); + return null; + }); }); } @@ -268,8 +256,8 @@ public class DiceASTExpression implements IDiceExpression { * @return A pair consisting of the token's value and the AST it * represents */ - private Pair> - evaluateLeaf(IDiceASTNode leafNode) { + private Pair> evaluateLeaf( + IDiceASTNode leafNode) { if (leafNode.getType() == DiceASTType.VARIABLE) { VariableDiceNode node = (VariableDiceNode) leafNode; @@ -284,17 +272,17 @@ public class DiceASTExpression implements IDiceExpression { } } - private Pair> - parseVariable(VariableDiceNode leafNode) { + private Pair> parseVariable( + VariableDiceNode leafNode) { String varName = leafNode.getVariable(); if (env.containsKey(varName)) { return new Pair<>(env.get(varName).roll(), new AST<>(leafNode)); - } else { - // Handle special case for defining variables - return new Pair<>(0, new AST<>(leafNode)); } + + // Handle special case for defining variables + return new Pair<>(0, new AST<>(leafNode)); } /** diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTFlattener.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTFlattener.java index a7500a8..39c0797 100644 --- a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTFlattener.java +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTFlattener.java @@ -15,11 +15,11 @@ import bjc.dicelang.DiceExpressionType; import bjc.dicelang.IDiceExpression; import bjc.dicelang.ReferenceDiceExpression; import bjc.dicelang.ScalarDie; -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 bjc.dicelang.ast.nodes.VariableDiceNode; +import bjc.dicelang.old.ast.nodes.DiceASTType; +import bjc.dicelang.old.ast.nodes.IDiceASTNode; +import bjc.dicelang.old.ast.nodes.LiteralDiceNode; +import bjc.dicelang.old.ast.nodes.OperatorDiceNode; +import bjc.dicelang.old.ast.nodes.VariableDiceNode; import bjc.utils.parserutils.AST; /** diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTInliner.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTInliner.java index 3a8e796..802741f 100644 --- a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTInliner.java +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTInliner.java @@ -2,9 +2,9 @@ package bjc.dicelang.old.ast; import java.util.function.Function; -import bjc.dicelang.ast.nodes.DiceASTType; -import bjc.dicelang.ast.nodes.IDiceASTNode; -import bjc.dicelang.ast.nodes.VariableDiceNode; +import bjc.dicelang.old.ast.nodes.DiceASTType; +import bjc.dicelang.old.ast.nodes.IDiceASTNode; +import bjc.dicelang.old.ast.nodes.VariableDiceNode; import bjc.utils.funcdata.FunctionalList; import bjc.utils.funcdata.FunctionalMap; import bjc.utils.funcdata.IFunctionalList; diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTParser.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTParser.java index d8e13f7..c9b48c8 100644 --- a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTParser.java +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTParser.java @@ -4,12 +4,10 @@ import java.util.Deque; import java.util.LinkedList; import java.util.function.Function; -import org.apache.commons.lang3.StringUtils; - -import bjc.dicelang.ast.nodes.IDiceASTNode; -import bjc.dicelang.ast.nodes.LiteralDiceNode; -import bjc.dicelang.ast.nodes.OperatorDiceNode; -import bjc.dicelang.ast.nodes.VariableDiceNode; +import bjc.dicelang.old.ast.nodes.IDiceASTNode; +import bjc.dicelang.old.ast.nodes.LiteralDiceNode; +import bjc.dicelang.old.ast.nodes.OperatorDiceNode; +import bjc.dicelang.old.ast.nodes.VariableDiceNode; import bjc.utils.data.IPair; import bjc.utils.data.Pair; import bjc.utils.funcdata.FunctionalStringTokenizer; @@ -32,37 +30,12 @@ public class DiceASTParser { public IDiceASTNode apply(String tok) { if (isOperator(tok)) { return OperatorDiceNode.fromString(tok); - } else if (NodeBaker.isLiteral(tok)) { + } else if (LiteralDiceNode.isLiteral(tok)) { return new LiteralDiceNode(tok); } else { return new VariableDiceNode(tok); } } - - /** - * Check if a token represents a literal - * - * @param tok - * The token to check - * @return Whether or not the token represents a literal - */ - private static boolean isLiteral(String tok) { - if (StringUtils.countMatches(tok, 'c') == 1 - && !tok.equalsIgnoreCase("c")) { - return true; - } else if (StringUtils.countMatches(tok, 'd') == 1 - && !tok.equalsIgnoreCase("d")) { - return true; - } else { - try { - Integer.parseInt(tok); - return true; - } catch (@SuppressWarnings("unused") NumberFormatException nfex) { - // We don't care about details - return false; - } - } - } } /** diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTReferenceChecker.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTReferenceChecker.java index e526ee9..3e0ceec 100644 --- a/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTReferenceChecker.java +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/DiceASTReferenceChecker.java @@ -2,9 +2,9 @@ package bjc.dicelang.old.ast; import java.util.function.Consumer; -import bjc.dicelang.ast.nodes.DiceASTType; -import bjc.dicelang.ast.nodes.IDiceASTNode; -import bjc.dicelang.ast.nodes.VariableDiceNode; +import bjc.dicelang.old.ast.nodes.DiceASTType; +import bjc.dicelang.old.ast.nodes.IDiceASTNode; +import bjc.dicelang.old.ast.nodes.VariableDiceNode; import bjc.utils.data.IHolder; /** @@ -53,8 +53,8 @@ public final class DiceASTReferenceChecker VariableDiceNode node = (VariableDiceNode) astNode; return node.getVariable().equals(varName); - } else { - return false; } + + return false; } } \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/IOperatorCollapser.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/IOperatorCollapser.java index 65cb264..36243a6 100644 --- a/dice-lang/src/main/java/bjc/dicelang/old/ast/IOperatorCollapser.java +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/IOperatorCollapser.java @@ -2,7 +2,7 @@ package bjc.dicelang.old.ast; import java.util.function.BinaryOperator; -import bjc.dicelang.ast.nodes.IDiceASTNode; +import bjc.dicelang.old.ast.nodes.IDiceASTNode; import bjc.utils.data.Pair; import bjc.utils.parserutils.AST; diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/DiceASTType.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/DiceASTType.java new file mode 100644 index 0000000..633d1d9 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/DiceASTType.java @@ -0,0 +1,27 @@ +package bjc.dicelang.old.ast.nodes; + +/** + * An enum to represent the type of node an AST node is + * + * @author ben + * + */ +public enum DiceASTType { + /** + * A node that contains a literal value + */ + LITERAL, + /** + * A node that contains an operator expression + */ + OPERATOR, + /** + * A node that contains a variable reference + */ + VARIABLE; + + @Override + public String toString() { + return this.name().toLowerCase(); + } +} \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/IDiceASTNode.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/IDiceASTNode.java new file mode 100644 index 0000000..579c595 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/IDiceASTNode.java @@ -0,0 +1,23 @@ +package bjc.dicelang.old.ast.nodes; + +/** + * The interface for a node in a dice AST + * + * @author ben + * + */ +public interface IDiceASTNode { + /** + * Check if this node represents an operator or not + * + * @return Whether or not this node represents an operator + */ + public boolean isOperator(); + + /** + * Get the type of AST node this node is + * + * @return The type of AST node this AST node is + */ + public DiceASTType getType(); +} \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/LiteralDiceNode.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/LiteralDiceNode.java new file mode 100644 index 0000000..46c84d0 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/LiteralDiceNode.java @@ -0,0 +1,217 @@ +package bjc.dicelang.old.ast.nodes; + +import org.apache.commons.lang3.StringUtils; + +import bjc.dicelang.ComplexDice; +import bjc.dicelang.CompoundDice; +import bjc.dicelang.IDiceExpression; +import bjc.dicelang.ScalarDie; +import bjc.utils.data.Pair; +import bjc.utils.parserutils.AST; + +/** + * A AST node that represents a literal value + * + * @author ben + * + */ +public class LiteralDiceNode implements IDiceASTNode { + private static boolean isValidInfixOperator(String dat, String op) { + return StringUtils.countMatches(dat, op) == 1 + && !dat.equalsIgnoreCase(op) && !dat.startsWith(op); + } + + /** + * The value contained by this node + */ + private String value; + + /** + * Create a new node with the given value + * + * @param data + * The value to be in this node + */ + public LiteralDiceNode(String data) { + this.value = data; + } + + /** + * Create a new node with the given value + * + * @param val + * The value for this node + */ + public LiteralDiceNode(int val) { + this(Integer.toString(val)); + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#equals(java.lang.Object) + */ + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } else if (obj == null) { + return false; + } else if (getClass() != obj.getClass()) { + return false; + } else { + LiteralDiceNode other = (LiteralDiceNode) obj; + + if (value == null) { + if (other.value != null) { + return false; + } + } else if (!value.equals(other.value)) { + return false; + } + + return true; + } + } + + /** + * Get the data stored in this AST node + * + * @return the data stored in this AST node + */ + public String getData() { + return value; + } + + @Override + public DiceASTType getType() { + return DiceASTType.LITERAL; + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + ((value == null) ? 0 : value.hashCode()); + return result; + } + + @Override + public boolean isOperator() { + return false; + } + + /** + * Parse this node into an expression + * + * @return The node in expression form + */ + public IDiceExpression toExpression() { + String literalData = this.getData(); + + if (LiteralDiceNode.isValidInfixOperator(literalData, "c")) { + String[] strangs = literalData.split("c"); + + return new CompoundDice(strangs); + } else if (LiteralDiceNode.isValidInfixOperator(literalData, + "d")) { + /* + * Handle dice groups + */ + return ComplexDice.fromString(literalData); + } else { + try { + return new ScalarDie(Integer.parseInt(literalData)); + } catch (NumberFormatException nfex) { + UnsupportedOperationException usex = new UnsupportedOperationException( + "Found malformed leaf token " + this); + + usex.initCause(nfex); + + throw usex; + } + } + } + + /** + * Parse this node into an expression + * + * @return The node as a pair of a sample value and the AST it + * represents + */ + public Pair> toParseValue() { + AST returnedAST = new AST<>(this); + + IDiceExpression expression = toExpression(); + + return new Pair<>(expression.roll(), returnedAST); + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return value; + } + + /** + * Check if this node represents a constant value + * + * @return Whether or not this node represents a constant value + */ + public boolean isConstant() { + try { + Integer.parseInt(value); + return true; + } catch (@SuppressWarnings("unused") NumberFormatException nfex) { + // We don't care about details + return false; + } + } + + /** + * Return the constant value this node represents + * + * @return The constant value of this node + * + * @throws NumberFormatException + * if you call this on a node that doesn't represent a + * constant value + */ + public int toConstant() { + return Integer.parseInt(value); + } + + /** + * Check if a token represents a literal + * + * @param tok + * The token to check + * @return Whether or not the token represents a literal + */ + public static boolean isLiteral(String tok) { + if (StringUtils.countMatches(tok, 'c') == 1 + && !tok.equalsIgnoreCase("c")) { + return true; + } else if (StringUtils.countMatches(tok, 'd') == 1 + && !tok.equalsIgnoreCase("d")) { + return true; + } else { + try { + Integer.parseInt(tok); + return true; + } catch (@SuppressWarnings("unused") NumberFormatException nfex) { + // We don't care about details + return false; + } + } + } +} \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/OperatorDiceNode.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/OperatorDiceNode.java new file mode 100644 index 0000000..3c06553 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/OperatorDiceNode.java @@ -0,0 +1,92 @@ +package bjc.dicelang.old.ast.nodes; + +// The following classes need to be changed upon addition of a new operator +// 1. DiceASTExpression +// 2. DiceASTFlattener +// 3. DiceASTParser +/** + * A node that represents an operator + * + * @author ben + * + */ +public enum OperatorDiceNode implements IDiceASTNode { + /** + * Represents adding two nodes + */ + ADD, + /** + * Represents assigning one node to another + */ + ASSIGN, + /** + * Representings combining two node values together + */ + COMPOUND, + /** + * Represents dividing two nodes + */ + DIVIDE, + /** + * Represents using one node a variable number of times + */ + GROUP, + /** + * Represents multiplying two nodes + */ + MULTIPLY, + /** + * Represents subtracting two nodes + */ + SUBTRACT, + /** + * Represents executing one statement in the context of the other + */ + LET; + + /** + * Create a operator node from a string + * + * @param s + * The string to convert to a node + * @return The operator corresponding to the node + */ + public static OperatorDiceNode fromString(String s) { + switch (s) { + case ":=": + return ASSIGN; + case "+": + return ADD; + case "-": + return SUBTRACT; + case "*": + return MULTIPLY; + case "/": + return DIVIDE; + case "d": + return GROUP; + case "c": + return COMPOUND; + case "->": + return LET; + default: + throw new IllegalArgumentException( + s + " is not a valid operator node"); + } + } + + @Override + public DiceASTType getType() { + return DiceASTType.OPERATOR; + } + + /* + * (non-Javadoc) + * + * @see bjc.utils.dice.ast.IDiceASTNode#isOperator() + */ + @Override + public boolean isOperator() { + return true; + } +} diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/VariableDiceNode.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/VariableDiceNode.java new file mode 100644 index 0000000..262f99b --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/VariableDiceNode.java @@ -0,0 +1,101 @@ +package bjc.dicelang.old.ast.nodes; + +/** + * A node that represents a variable reference + * + * @author ben + * + */ +public class VariableDiceNode implements IDiceASTNode { + /** + * The variable referenced by this node + */ + private String variableName; + + /** + * Create a new node representing the specified variable + * + * @param varName + * The name of the variable being referenced + */ + public VariableDiceNode(String varName) { + this.variableName = varName; + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#equals(java.lang.Object) + */ + @Override + public boolean equals(Object obj) { + // Handle special cases + if (this == obj) { + return true; + } else if (obj == null) { + return false; + } else if (getClass() != obj.getClass()) { + return false; + } else { + VariableDiceNode other = (VariableDiceNode) obj; + + if (variableName == null) { + if (other.variableName != null) { + return false; + } + } else if (!variableName.equals(other.variableName)) { + return false; + } + + return true; + } + } + + @Override + public DiceASTType getType() { + return DiceASTType.VARIABLE; + } + + /** + * Get the variable referenced by this AST node + * + * @return the variable referenced by this AST node + */ + public String getVariable() { + return variableName; + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#hashCode() + */ + @Override + public int hashCode() { + final int prime = 31; + int result = 1; + result = prime * result + + ((variableName == null) ? 0 : variableName.hashCode()); + return result; + } + + /* + * (non-Javadoc) + * + * @see bjc.utils.dice.ast.IDiceASTNode#isOperator() + */ + @Override + public boolean isOperator() { + return false; + } + + /* + * (non-Javadoc) + * + * @see java.lang.Object#toString() + */ + @Override + public String toString() { + return variableName; + } +} \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/package-info.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/package-info.java new file mode 100644 index 0000000..f99776f --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/nodes/package-info.java @@ -0,0 +1,6 @@ +/** + * This package contains the various Node types in the Dice AST + * @author ben + * + */ +package bjc.dicelang.old.ast.nodes; \ No newline at end of file diff --git a/dice-lang/src/main/java/bjc/dicelang/old/ast/optimization/DiceASTOptimizer.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/optimization/DiceASTOptimizer.java new file mode 100644 index 0000000..dead812 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/optimization/DiceASTOptimizer.java @@ -0,0 +1,209 @@ +package bjc.dicelang.old.ast.optimization; + +import static bjc.dicelang.old.ast.nodes.DiceASTType.*; + +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.old.ast.nodes.DiceASTType; +import bjc.dicelang.old.ast.nodes.IDiceASTNode; +import bjc.dicelang.old.ast.nodes.LiteralDiceNode; +import bjc.dicelang.old.ast.nodes.OperatorDiceNode; +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())); + } + + 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/old/ast/optimization/package-info.java b/dice-lang/src/main/java/bjc/dicelang/old/ast/optimization/package-info.java new file mode 100644 index 0000000..ef39522 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/old/ast/optimization/package-info.java @@ -0,0 +1,6 @@ +/** + * Contains classes for optimizing ASTs + * @author ben + * + */ +package bjc.dicelang.old.ast.optimization; \ No newline at end of file -- cgit v1.2.3