diff options
Diffstat (limited to 'dice-lang/src/main/java/bjc')
11 files changed, 442 insertions, 60 deletions
diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTEvaluator.java b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTEvaluator.java index 016fa8a..411212e 100644 --- a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTEvaluator.java +++ b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTEvaluator.java @@ -1,7 +1,6 @@ package bjc.dicelang.ast; import bjc.dicelang.ComplexDice; -import bjc.dicelang.ast.nodes.DiceASTType; import bjc.dicelang.ast.nodes.DiceLiteralNode; import bjc.dicelang.ast.nodes.DiceLiteralType; import bjc.dicelang.ast.nodes.IDiceASTNode; @@ -59,7 +58,11 @@ public class DiceASTEvaluator { }); operatorCollapsers.put(OperatorDiceNode.COMPOUND, - DiceASTEvaluator::parseCompound); + new ArithmeticCollapser(OperatorDiceNode.COMPOUND, + (left, right) -> { + return Integer.parseInt(Integer.toString(left) + + Integer.toString(right)); + })); operatorCollapsers.put(OperatorDiceNode.GROUP, DiceASTEvaluator::parseGroup); @@ -128,7 +131,7 @@ public class DiceASTEvaluator { switch (literalType) { case DICE: - return ((DiceLiteralNode) leafNode).getValue(); + return ((DiceLiteralNode) leafNode).getValue().roll(); case INTEGER: return ((IntegerLiteralNode) leafNode).getValue(); default: @@ -156,7 +159,7 @@ public class DiceASTEvaluator { return nameNode.bindRight((nameTree) -> { return valueNode.bind((valueValue, valueTree) -> { - if (containsSimpleVariable(nameTree)) { + if (DiceASTUtils.containsSimpleVariable(nameTree)) { String varName = nameTree.transformHead((nameNod) -> { return ((VariableDiceNode) nameNod).getVariable(); }); @@ -166,46 +169,9 @@ public class DiceASTEvaluator { return new Pair<>(valueValue, nameTree); } - throw new IllegalStateException( - "Statement that shouldn't be hit was hit."); - }); - }); - } - - private static boolean - containsSimpleVariable(ITree<IDiceASTNode> nameTree) { - return nameTree.transformHead((nameNod) -> { - if (nameNod.getType() != DiceASTType.VARIABLE) { throw new UnsupportedOperationException( "Assigning to complex variables isn't supported. Problem node is " - + nameNod); - } - - return true; - }); - } - - private static IPair<Integer, ITree<IDiceASTNode>> parseCompound( - IFunctionalList<IPair<Integer, ITree<IDiceASTNode>>> nodes) { - if (nodes.getSize() != 2) { - throw new UnsupportedOperationException( - "Can only form a group from two dice"); - } - - IPair<Integer, ITree<IDiceASTNode>> leftDiceNode = - nodes.getByIndex(0); - IPair<Integer, ITree<IDiceASTNode>> rightDiceNode = - nodes.getByIndex(1); - - return leftDiceNode.bind((leftDiceValue, leftDiceTree) -> { - return rightDiceNode.bind((rightDiceValue, rightDiceTree) -> { - Integer result = - Integer.parseInt(Integer.toString(leftDiceValue) - + Integer.toString(rightDiceValue)); - - return new Pair<>(result, - new Tree<>(OperatorDiceNode.GROUP, leftDiceTree, - rightDiceTree)); + + nameNode.getRight()); }); }); } diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java new file mode 100644 index 0000000..00ac871 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java @@ -0,0 +1,57 @@ +package bjc.dicelang.ast; + +import bjc.dicelang.ast.nodes.IDiceASTNode; +import bjc.dicelang.ast.optimization.IOptimizationPass; +import bjc.utils.funcdata.FunctionalList; +import bjc.utils.funcdata.IFunctionalList; +import bjc.utils.funcdata.IFunctionalMap; +import bjc.utils.funcdata.ITree; + +/** + * Contains optimizations appliable to a dice AST + * + * @author ben + * + */ +public class DiceASTOptimizer { + private IFunctionalList<IOptimizationPass> passes; + + /** + * Create a new optimizer + */ + public DiceASTOptimizer() { + passes = new FunctionalList<>(); + } + + /** + * Add a pass to the list of optimization passes + * + * @param pass + * The pass to add + */ + public void addPass(IOptimizationPass pass) { + passes.add(pass); + } + + /** + * Optimize the passed in tree + * + * @param ast + * The tree to optimize + * @param enviroment + * The enviroment for variable references + * @return The optimized tree + */ + public ITree<IDiceASTNode> optimizeTree(ITree<IDiceASTNode> ast, + IFunctionalMap<String, ITree<IDiceASTNode>> enviroment) { + return passes.reduceAux(ast, (currentPass, currentTree) -> { + return currentTree.collapse(currentPass::optimizeLeaf, + (operator) -> { + return (nodes) -> { + return currentPass.optimizeOperator(operator, + nodes); + }; + }, (tree) -> tree); + }, (tree) -> tree); + } +} diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTReferenceSanitizer.java b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTReferenceSanitizer.java new file mode 100644 index 0000000..08f84e3 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTReferenceSanitizer.java @@ -0,0 +1,85 @@ +package bjc.dicelang.ast; + +import bjc.dicelang.ast.nodes.IDiceASTNode; +import bjc.dicelang.ast.nodes.OperatorDiceNode; +import bjc.dicelang.ast.nodes.VariableDiceNode; +import bjc.utils.funcdata.IFunctionalMap; +import bjc.utils.funcdata.ITree; +import bjc.utils.funcdata.TopDownTransformResult; +import bjc.utils.funcdata.Tree; + +/** + * Sanitize the references in an AST so that a variable that refers to + * itself in its definition has the occurance of it replaced with its + * previous definition + * + * @author ben + * + */ +public class DiceASTReferenceSanitizer { + /** + * Sanitize the references in an AST + * + * @param ast + * @param enviroment + * @return The sanitized AST + */ + public static ITree<IDiceASTNode> sanitize(ITree<IDiceASTNode> ast, + IFunctionalMap<String, ITree<IDiceASTNode>> enviroment) { + return ast.topDownTransform( + DiceASTReferenceSanitizer::shouldSanitize, (subTree) -> { + return doSanitize(subTree, enviroment); + }); + } + + private static TopDownTransformResult + shouldSanitize(IDiceASTNode node) { + if (!node.isOperator()) { + return TopDownTransformResult.SKIP; + } + + switch (((OperatorDiceNode) node)) { + case ASSIGN: + return TopDownTransformResult.TRANSFORM; + case ADD: + case COMPOUND: + case DIVIDE: + case GROUP: + case MULTIPLY: + case SUBTRACT: + default: + return TopDownTransformResult.SKIP; + } + } + + private static ITree<IDiceASTNode> doSanitize(ITree<IDiceASTNode> ast, + IFunctionalMap<String, ITree<IDiceASTNode>> enviroment) { + if (ast.getChildrenCount() != 2) { + throw new UnsupportedOperationException( + "Assignment must have two arguments."); + } + + ITree<IDiceASTNode> nameTree = ast.getChild(0); + ITree<IDiceASTNode> valueTree = ast.getChild(1); + + if (!DiceASTUtils.containsSimpleVariable(nameTree)) { + throw new UnsupportedOperationException( + "Assignment must be between a variable and a expression"); + } + + String variableName = nameTree.transformHead( + (node) -> ((VariableDiceNode) node).getVariable()); + + if (enviroment.containsKey(variableName)) { + // We should always inline out references to last, because it + // will always change + ITree<IDiceASTNode> inlinedValue = + DiceASTInliner.selectiveInline(valueTree, enviroment, + variableName, "last"); + + return new Tree<>(ast.getHead(), nameTree, inlinedValue); + } + + return ast; + } +} diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTUtils.java b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTUtils.java new file mode 100644 index 0000000..20a46c7 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTUtils.java @@ -0,0 +1,83 @@ +package bjc.dicelang.ast; + +import bjc.dicelang.IDiceExpression; +import bjc.dicelang.ScalarDie; +import bjc.dicelang.ast.nodes.DiceASTType; +import bjc.dicelang.ast.nodes.DiceLiteralNode; +import bjc.dicelang.ast.nodes.IDiceASTNode; +import bjc.dicelang.ast.nodes.ILiteralDiceNode; +import bjc.dicelang.ast.nodes.IntegerLiteralNode; +import bjc.utils.funcdata.ITree; + +/** + * Functions that are useful when dealing with dice ASTs + * + * @author ben + * + */ +public class DiceASTUtils { + /** + * Check if a dice AST contains a simple variable reference + * + * @param nameTree + * @return Whether or not a dice AST contains a simple variable + * reference + */ + public static boolean + containsSimpleVariable(ITree<IDiceASTNode> nameTree) { + return nameTree.transformHead((nameNod) -> { + if (nameNod.getType() != DiceASTType.VARIABLE) { + return false; + } + + return true; + }); + } + + /** + * Convert an AST tree to an integer, if possible. + * + * @param tree + * The tree to convert + * @return The tree as an integer + * + * @throws ClassCastException + * if the head of the tree is not a literal (implements + * {@link ILiteralDiceNode}) + * @throws UnsupportedOperationException + * if the head of the tree is not optimizable + */ + public static int toInt(ITree<IDiceASTNode> tree) { + return tree.transformHead((node) -> { + return ((ILiteralDiceNode) node).optimize(); + }); + } + + /** + * Convert an AST tree to a dice expression, if possible. + * + * @param tree + * The tree to convert + * @return The tree as a dice expression + * + * @throws ClassCastException + * if the head of the tree is not a literal (implements + * {@link ILiteralDiceNode}) + * @throws UnsupportedOperationException + * if the head of the tree is not optimizable + */ + public static IDiceExpression toExpression(ITree<IDiceASTNode> tree) { + ILiteralDiceNode litNode = (ILiteralDiceNode) tree.getHead(); + + switch (litNode.getLiteralType()) { + case DICE: + return ((DiceLiteralNode) litNode).getValue(); + case INTEGER: + return new ScalarDie( + ((IntegerLiteralNode) litNode).getValue()); + default: + throw new UnsupportedOperationException( + "This type of literal isn't convertable to an expression"); + } + } +} diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/DiceLiteralNode.java b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/DiceLiteralNode.java index b2e1825..b398ac6 100644 --- a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/DiceLiteralNode.java +++ b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/DiceLiteralNode.java @@ -21,12 +21,7 @@ public class DiceLiteralNode implements ILiteralDiceNode { expression = exp; } - /** - * Check if this node can be optimized to a constant - * - * @return Whether or not this node can be optimized to a constant - * @see bjc.dicelang.IDiceExpression#canOptimize() - */ + @Override public boolean canOptimize() { return expression.canOptimize(); } @@ -37,24 +32,19 @@ public class DiceLiteralNode implements ILiteralDiceNode { } /** - * Return a value from the expression being represented + * Return the expression being represented * - * @return A value from the expression being represented + * @return The expression being represented */ - public int getValue() { - return expression.roll(); + public IDiceExpression getValue() { + return expression; } - /** - * Optimize this node to a constant if possible - * - * @return This node in constant form if possible - * @see bjc.dicelang.IDiceExpression#optimize() - */ + @Override public int optimize() { return expression.optimize(); } - + @Override public String toString() { return expression.toString(); diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/ILiteralDiceNode.java b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/ILiteralDiceNode.java index b12b516..994a680 100644 --- a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/ILiteralDiceNode.java +++ b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/ILiteralDiceNode.java @@ -27,6 +27,22 @@ public interface ILiteralDiceNode extends IDiceASTNode { DiceLiteralType getLiteralType(); /** + * Optimize this node to a constant if possible + * + * @return This node in constant form if possible + * @see bjc.dicelang.IDiceExpression#optimize() + */ + int optimize(); + + /** + * Check if this node can be optimized to a constant + * + * @return Whether or not this node can be optimized to a constant + * @see bjc.dicelang.IDiceExpression#canOptimize() + */ + boolean canOptimize(); + + /** * Check if a token represents a literal, and if so, what type * * @param tok diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/IntegerLiteralNode.java b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/IntegerLiteralNode.java index 0ed2c2c..d25adbc 100644 --- a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/IntegerLiteralNode.java +++ b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/IntegerLiteralNode.java @@ -32,9 +32,19 @@ public class IntegerLiteralNode implements ILiteralDiceNode { public int getValue() { return value; } - + @Override public String toString() { return Integer.toString(value); } + + @Override + public int optimize() { + return value; + } + + @Override + public boolean canOptimize() { + return true; + } } diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/optimization/ArithmeticCollapser.java b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/ArithmeticCollapser.java new file mode 100644 index 0000000..5318119 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/ArithmeticCollapser.java @@ -0,0 +1,49 @@ +package bjc.dicelang.ast.optimization; + +import java.util.function.BinaryOperator; + +import bjc.dicelang.ast.DiceASTUtils; +import bjc.dicelang.ast.nodes.DiceASTType; +import bjc.dicelang.ast.nodes.IDiceASTNode; +import bjc.dicelang.ast.nodes.ILiteralDiceNode; +import bjc.dicelang.ast.nodes.IntegerLiteralNode; +import bjc.dicelang.ast.nodes.OperatorDiceNode; +import bjc.utils.funcdata.IFunctionalList; +import bjc.utils.funcdata.ITree; +import bjc.utils.funcdata.Tree; + +class ArithmeticCollapser { + private BinaryOperator<Integer> reducer; + private OperatorDiceNode type; + + public ArithmeticCollapser(BinaryOperator<Integer> reducr, + OperatorDiceNode typ) { + reducer = reducr; + this.type = typ; + } + + public ITree<IDiceASTNode> + collapse(IFunctionalList<ITree<IDiceASTNode>> children) { + boolean allConstant = children.allMatch((subtree) -> { + return subtree.transformHead((node) -> { + if (node.getType() == DiceASTType.LITERAL) { + return ((ILiteralDiceNode) node).canOptimize(); + } + + return false; + }); + }); + + if (!allConstant) { + return new Tree<>(type, children); + } + + int initState = DiceASTUtils.toInt(children.first()); + + return children.tail().reduceAux(initState, + (currentNode, state) -> { + return reducer.apply(state, + DiceASTUtils.toInt(currentNode)); + }, (state) -> new Tree<>(new IntegerLiteralNode(state))); + } +} diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/optimization/ConstantCollapser.java b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/ConstantCollapser.java new file mode 100644 index 0000000..5062170 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/ConstantCollapser.java @@ -0,0 +1,86 @@ +package bjc.dicelang.ast.optimization; + +import bjc.dicelang.ComplexDice; +import bjc.dicelang.ast.DiceASTUtils; +import bjc.dicelang.ast.nodes.IDiceASTNode; +import bjc.dicelang.ast.nodes.IntegerLiteralNode; +import bjc.dicelang.ast.nodes.OperatorDiceNode; +import bjc.utils.funcdata.IFunctionalList; +import bjc.utils.funcdata.ITree; +import bjc.utils.funcdata.Tree; + +/** + * Collapses operations with constants to constants + * + * @author ben + * + */ +public class ConstantCollapser implements IOptimizationPass { + private static final ArithmeticCollapser additionCollapser = + new ArithmeticCollapser((left, right) -> left + right, + OperatorDiceNode.ADD); + + private static final ArithmeticCollapser divideCollapser = + new ArithmeticCollapser((left, right) -> left / right, + OperatorDiceNode.DIVIDE); + + private static final ArithmeticCollapser multiplyCollapser = + new ArithmeticCollapser((left, right) -> left * right, + OperatorDiceNode.MULTIPLY); + + private static final ArithmeticCollapser subtractCollapser = + new ArithmeticCollapser((left, right) -> left - right, + OperatorDiceNode.SUBTRACT); + + private static final ArithmeticCollapser compoundCollapser = + new ArithmeticCollapser((left, + right) -> Integer.parseInt(Integer.toString(left) + + Integer.toString(left)), + OperatorDiceNode.SUBTRACT); + + @Override + public ITree<IDiceASTNode> optimizeLeaf(IDiceASTNode leafNode) { + // We don't do anything special here + return new Tree<>(leafNode); + } + + @Override + public ITree<IDiceASTNode> optimizeOperator(IDiceASTNode operator, + IFunctionalList<ITree<IDiceASTNode>> children) { + if (!operator.isOperator()) { + return new Tree<>(operator, children); + } + + switch ((OperatorDiceNode) operator) { + case ADD: + return additionCollapser.collapse(children); + case DIVIDE: + return divideCollapser.collapse(children); + case MULTIPLY: + return multiplyCollapser.collapse(children); + case SUBTRACT: + return subtractCollapser.collapse(children); + case COMPOUND: + return compoundCollapser.collapse(children); + case GROUP: + if (children.getSize() != 2) { + return new Tree<>(operator, children); + } + + ComplexDice dice = new ComplexDice( + DiceASTUtils.toExpression(children.getByIndex(0)), + DiceASTUtils.toExpression(children.getByIndex(1))); + + if (dice.canOptimize()) { + return new Tree<>( + new IntegerLiteralNode(dice.optimize())); + } + + return new Tree<>(operator, children); + case ASSIGN: + default: + // We don't optimize these operators + return new Tree<>(operator, children); + } + } +} diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/optimization/IOptimizationPass.java b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/IOptimizationPass.java new file mode 100644 index 0000000..b631fb5 --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/IOptimizationPass.java @@ -0,0 +1,34 @@ +package bjc.dicelang.ast.optimization; + +import bjc.dicelang.ast.nodes.IDiceASTNode; +import bjc.utils.funcdata.IFunctionalList; +import bjc.utils.funcdata.ITree; + +/** + * Represents a pass of optimizations over a dice AST + * + * @author ben + * + */ +public interface IOptimizationPass { + /** + * Optimize a leaf in the tree + * + * @param leafNode + * The node to optimize + * @return The optimized node + */ + public ITree<IDiceASTNode> optimizeLeaf(IDiceASTNode leafNode); + + /** + * Optimize an operator in an AST node + * + * @param operator + * The operator being optimized + * @param children + * The children of the operator being optimized + * @return The optimized node + */ + public ITree<IDiceASTNode> optimizeOperator(IDiceASTNode operator, + IFunctionalList<ITree<IDiceASTNode>> children); +} 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..a3ec93c --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/package-info.java @@ -0,0 +1,6 @@ +/** + * Contains optimizations on dice ASTs + * @author ben + * + */ +package bjc.dicelang.ast.optimization;
\ No newline at end of file |