Improve JsStaticEval to be able to perform optimizations on trees of JsBinaryOperations.
Patch by: bobv
Review by: cromwellian
git-svn-id: https://google-web-toolkit.googlecode.com/svn/trunk@6736 8db76d5a-ed1c-0410-87a9-c151d255dfc7
diff --git a/dev/core/src/com/google/gwt/dev/js/JsStaticEval.java b/dev/core/src/com/google/gwt/dev/js/JsStaticEval.java
index 6cb7c4d..6845e21 100644
--- a/dev/core/src/com/google/gwt/dev/js/JsStaticEval.java
+++ b/dev/core/src/com/google/gwt/dev/js/JsStaticEval.java
@@ -21,6 +21,7 @@
import com.google.gwt.dev.js.ast.JsBinaryOperation;
import com.google.gwt.dev.js.ast.JsBinaryOperator;
import com.google.gwt.dev.js.ast.JsBlock;
+import com.google.gwt.dev.js.ast.JsBooleanLiteral;
import com.google.gwt.dev.js.ast.JsBreak;
import com.google.gwt.dev.js.ast.JsConditional;
import com.google.gwt.dev.js.ast.JsContext;
@@ -42,14 +43,17 @@
import com.google.gwt.dev.js.ast.JsUnaryOperator;
import com.google.gwt.dev.js.ast.JsValueLiteral;
import com.google.gwt.dev.js.ast.JsVars;
+import com.google.gwt.dev.js.ast.JsVisitable;
import com.google.gwt.dev.js.ast.JsVisitor;
import com.google.gwt.dev.js.ast.JsWhile;
-import com.google.gwt.dev.js.ast.JsBooleanLiteral;
import com.google.gwt.dev.js.ast.JsVars.JsVar;
import java.util.ArrayList;
+import java.util.EnumSet;
import java.util.HashSet;
+import java.util.IdentityHashMap;
import java.util.List;
+import java.util.Map;
import java.util.Set;
/**
@@ -151,12 +155,21 @@
private Set<JsExpression> evalBooleanContext = new HashSet<JsExpression>();
+ /**
+ * This is used by {@link #additionCoercesToString}.
+ */
+ private Map<JsExpression, Boolean> coercesToStringMap = new IdentityHashMap<JsExpression, Boolean>();
+
@Override
public void endVisit(JsBinaryOperation x, JsContext<JsExpression> ctx) {
JsBinaryOperator op = x.getOperator();
JsExpression arg1 = x.getArg1();
JsExpression arg2 = x.getArg2();
- if (op == JsBinaryOperator.AND) {
+
+ if (MATH_ASSOCIATIVE.contains(op)
+ && trySimplifyAssociativeExpression(x, ctx)) {
+ // Nothing else to do
+ } else if (op == JsBinaryOperator.AND) {
shortCircuitAnd(arg1, arg2, ctx);
} else if (op == JsBinaryOperator.OR) {
shortCircuitOr(arg1, arg2, ctx);
@@ -454,6 +467,52 @@
return true;
}
+ /**
+ * Given an expression, determine if the addition operator would cause a
+ * string coercion to happen.
+ */
+ private boolean additionCoercesToString(JsExpression expr) {
+ if (expr instanceof JsStringLiteral) {
+ return true;
+ }
+
+ /*
+ * Because the nodes passed into this method are visited on exit, it is
+ * worthwile to memoize the result for this function.
+ */
+ Boolean toReturn = coercesToStringMap.get(expr);
+ if (toReturn != null) {
+ return toReturn;
+ }
+ toReturn = false;
+
+ if (expr instanceof JsBinaryOperation) {
+ JsBinaryOperation op = (JsBinaryOperation) expr;
+ switch (op.getOperator()) {
+ case ADD:
+ toReturn = additionCoercesToString(op.getArg1())
+ || additionCoercesToString(op.getArg2());
+ break;
+ case COMMA:
+ toReturn = additionCoercesToString(op.getArg2());
+ break;
+ }
+
+ if (op.getOperator().isAssignment()) {
+ toReturn = additionCoercesToString(op.getArg2());
+ }
+ }
+
+ /*
+ * TODO: Consider adding heuristics to detect String(foo), typeof(foo),
+ * and foo.toString(). The latter is debatable, since an implementation
+ * might not actually return a string.
+ */
+
+ coercesToStringMap.put(expr, toReturn);
+ return toReturn;
+ }
+
private boolean appendLiteral(StringBuilder result, JsValueLiteral val) {
if (val instanceof JsNumberLiteral) {
double number = ((JsNumberLiteral) val).getValue();
@@ -469,7 +528,7 @@
}
return true;
}
-
+
/**
* This method MUST be called whenever any statements are removed from a
* function. This is because some statements, such as JsVars or JsFunction
@@ -502,7 +561,7 @@
}
/*
- * String.valueOf(Double) produces trailing .0 on integers which is
+ * String.valueOf(Double) produces trailing .0 on integers which is
* incorrect for Javascript which produces conversions to string without
* trailing zeroes. Without this, int + String will turn out wrong.
*/
@@ -514,7 +573,7 @@
}
return num;
}
-
+
private SourceInfo makeSourceInfo(HasSourceInfo x, String m) {
return x.getSourceInfo().makeChild(StaticEvalVisitor.class, m);
}
@@ -592,23 +651,121 @@
JsExpression arg2, JsContext<JsExpression> ctx) {
if (arg1 instanceof JsValueLiteral && arg2 instanceof JsValueLiteral) {
// case: number + number
- if (arg1 instanceof JsNumberLiteral &&
- arg2 instanceof JsNumberLiteral) {
- ctx.replaceMe(program.getNumberLiteral(
- ((JsNumberLiteral) arg1).getValue() +
- ((JsNumberLiteral) arg2).getValue()));
+ if (arg1 instanceof JsNumberLiteral && arg2 instanceof JsNumberLiteral) {
+ double value = ((JsNumberLiteral) arg1).getValue()
+ + ((JsNumberLiteral) arg2).getValue();
+ ctx.replaceMe(program.getNumberLiteral(value));
} else {
// cases: number + string or string + number
StringBuilder result = new StringBuilder();
- if (appendLiteral(result, (JsValueLiteral) arg1) &&
- appendLiteral(result, (JsValueLiteral) arg2)) {
+ if (appendLiteral(result, (JsValueLiteral) arg1)
+ && appendLiteral(result, (JsValueLiteral) arg2)) {
ctx.replaceMe(program.getStringLiteral(original.getSourceInfo(),
result.toString()));
}
}
}
}
-
+
+ /**
+ * Attempts to simplify adjoining binary expressions with mathematically
+ * associative operators. This pass also tries to make these binary
+ * expressions as left-normal as possible.
+ */
+ private boolean trySimplifyAssociativeExpression(JsBinaryOperation x,
+ JsContext<JsExpression> ctx) {
+ boolean toReturn = false;
+ JsBinaryOperator op = x.getOperator();
+ JsExpression arg1 = x.getArg1();
+ JsExpression arg2 = x.getArg2();
+
+ /*
+ * First, we'll try to normalize the nesting of any binary expressions
+ * that we encounter. If we do this correctly,it will help to cut down on
+ * the number of unnecessary parens in the emitted JS.
+ */
+ // (X) O (c O d) ==> ((X) O c) O d
+ {
+ JsBinaryOperation rightOp = null;
+ if (arg2 instanceof JsBinaryOperation) {
+ rightOp = (JsBinaryOperation) arg2;
+ }
+ if (rightOp != null && !rightOp.getOperator().isAssignment()
+ && op == rightOp.getOperator()) {
+
+ if (op == JsBinaryOperator.ADD) {
+ /*
+ * JS type coercion is a problem if we don't know for certain that
+ * the right-hand expression will definitely be evaluated in a
+ * string context.
+ */
+ boolean mustBeString = additionCoercesToString(rightOp.getArg1())
+ || (additionCoercesToString(arg1) && additionCoercesToString(rightOp.getArg2()));
+ if (!mustBeString) {
+ return toReturn;
+ }
+ }
+
+ // (X) O c --> Try to reduce this
+ JsExpression newLeft = new JsBinaryOperation(x.getSourceInfo(), op,
+ arg1, rightOp.getArg1());
+
+ // Reset local vars with new state
+ op = rightOp.getOperator();
+ arg1 = accept(newLeft);
+ arg2 = rightOp.getArg2();
+ x = new JsBinaryOperation(x.getSourceInfo(), op, arg1, arg2);
+
+ ctx.replaceMe(x);
+ toReturn = didChange = true;
+ }
+ }
+
+ /*
+ * Now that we know that our AST is as left-normal as we can make it
+ * (because this method is called from endVisit), we now try to simplify
+ * the left-right node and the right node.
+ */
+ // (a O b) O c ==> a O s
+ {
+ JsBinaryOperation leftOp = null;
+ JsExpression leftLeft = null;
+ JsExpression leftRight = null;
+
+ if (arg1 instanceof JsBinaryOperation) {
+ leftOp = (JsBinaryOperation) arg1;
+ if (op.getPrecedence() == leftOp.getOperator().getPrecedence()) {
+ leftLeft = leftOp.getArg1();
+ leftRight = leftOp.getArg2();
+ }
+ }
+
+ if (leftRight != null) {
+ if (op == JsBinaryOperator.ADD) {
+ // Behavior as described above
+ boolean mustBeString = additionCoercesToString(leftRight)
+ || (additionCoercesToString(leftLeft) && additionCoercesToString(arg2));
+ if (!mustBeString) {
+ return toReturn;
+ }
+ }
+
+ // (b O c)
+ JsBinaryOperation middle = new JsBinaryOperation(x.getSourceInfo(),
+ op, leftRight, arg2);
+ StaticEvalVisitor v = new StaticEvalVisitor();
+ JsExpression maybeSimplified = v.accept(middle);
+
+ if (v.didChange()) {
+ x.setArg1(leftLeft);
+ x.setArg2(maybeSimplified);
+ toReturn = didChange = true;
+ }
+ }
+ }
+ return toReturn;
+ }
+
private void trySimplifyEq(JsExpression original, JsExpression arg1,
JsExpression arg2, JsContext<JsExpression> ctx) {
JsExpression updated = simplifyEq(original, arg1, arg2);
@@ -661,10 +818,22 @@
}
}
+ /**
+ * A set of the JS operators that are mathematically associative in nature.
+ */
+ private static final Set<JsBinaryOperator> MATH_ASSOCIATIVE = EnumSet.of(
+ JsBinaryOperator.ADD, JsBinaryOperator.AND, JsBinaryOperator.BIT_AND,
+ JsBinaryOperator.BIT_OR, JsBinaryOperator.BIT_XOR,
+ JsBinaryOperator.COMMA, JsBinaryOperator.MUL, JsBinaryOperator.OR);
+
public static boolean exec(JsProgram program) {
return (new JsStaticEval(program)).execImpl();
}
+ public static <T extends JsVisitable> T exec(JsProgram program, T node) {
+ return (new JsStaticEval(program)).execImpl(node);
+ }
+
/**
* Attempts to extract a single expression from a given statement and returns
* it. If no such expression exists, returns <code>null</code>.
@@ -769,4 +938,8 @@
return sev.didChange();
}
+
+ public <T extends JsVisitable> T execImpl(T node) {
+ return new StaticEvalVisitor().accept(node);
+ }
}
diff --git a/dev/core/test/com/google/gwt/dev/js/JsStaticEvalTest.java b/dev/core/test/com/google/gwt/dev/js/JsStaticEvalTest.java
index ea54e44..b68fd15 100644
--- a/dev/core/test/com/google/gwt/dev/js/JsStaticEvalTest.java
+++ b/dev/core/test/com/google/gwt/dev/js/JsStaticEvalTest.java
@@ -30,6 +30,65 @@
assertEquals("alert('Hello 42.2');", optimize("alert('Hello ' + 42.2);"));
}
+ public void testAssociativity() throws Exception {
+ // Simple test
+ assertEquals("alert(a||b||c||d);", optimize("alert((a||b)||(c||d));"));
+ assertEquals("alert(a&&b&&c&&d);", optimize("alert((a&&b)&&(c&&d));"));
+
+ // Preserve precedence
+ assertEquals("alert((a||b)&&(c||d));",
+ optimize("alert((a || b) && (c || d));"));
+ assertEquals("alert(a&&b||c&&d);",
+ optimize("alert((a && b) || ( c && d));"));
+ assertEquals("a(),b&&c();", optimize("a(), b && c()"));
+ assertEquals("a()&&b,c();", optimize("a() && b, c()"));
+
+ // Don't damage math expressions
+ assertEquals("alert(seconds/(60*60));",
+ optimize("alert(seconds / (60 * 60))"));
+ assertEquals("alert(1-(1-foo));", optimize("alert(1 - (1 - foo))"));
+
+ // Don't damage assignments
+ assertEquals("alert((a=0,b=foo));",
+ optimize("alert((a = 0, b = (bar, foo)))"));
+ assertEquals("alert(1+(a='2')+3+4);",
+ optimize("alert(1 + (a = '2') + 3 + 4);"));
+ assertEquals("alert(1+(a='2')+7);",
+ optimize("alert(1 + (a = '2') + (3 + 4));"));
+
+ // Break comma expressions up
+ assertEquals("alert((a(),b(),c(),d));",
+ optimize("alert(((a(),b()),(c(),d)));"));
+ // and remove expressions without side effects
+ assertEquals("alert(d);", optimize("alert(((a,b),(c,d)));"));
+
+ // Pattern of coercing a numeric add operation to a string
+ assertEquals("alert(''+(a+b));", optimize("alert('' + (a + b))"));
+ assertEquals("alert('foo'+(a+b));",
+ optimize("alert('foo' + ('' + (a + b)))"));
+
+ // Tests involving numeric and string literals and identifiers
+ assertEquals("alert(21+(1+$foo));",
+ optimize("alert((20 + 1) + (1 + $foo));"));
+ assertEquals("alert('211'+$foo);",
+ optimize("alert((20 + 1) + ('1' + $foo));"));
+ assertEquals("alert('2011'+$foo);",
+ optimize("alert((20 + '1') + ('1' + $foo));"));
+ assertEquals("alert('2011'+$foo);",
+ optimize("alert(('20' + 1) + ('1' + $foo));"));
+ assertEquals("alert('2011'+$foo);",
+ optimize("alert(('20' + '1') + ('1' + $foo));"));
+
+ // These are also tricky, because $foo could be non-numeric
+ assertEquals("alert($foo+1+21);", optimize("alert(($foo + 1) + (20 + 1));"));
+ assertEquals("alert($bar+13+7+(2+$foo));",
+ optimize("alert((($bar + (10 + 3)) + (2 + 5)) + (2 + $foo));"));
+
+ // Without type info, there's nothing that can be done for this expr
+ assertEquals("alert($foo+($bar+($baz+$quux)));",
+ optimize("alert($foo + ($bar + ($baz + $quux)));"));
+ }
+
public void testIfWithEmptyThen() throws Exception {
assertEquals("a();", optimize("if (a()) { }"));
}
