Move optimizer visitor to linq4j, add ExpressionType.modifiesLvalue to avoid inlining in such cases
diff --git a/src/main/java/net/hydromatic/linq4j/expressions/BlockBuilder.java b/src/main/java/net/hydromatic/linq4j/expressions/BlockBuilder.java
index a0d005b..7de6704 100644
--- a/src/main/java/net/hydromatic/linq4j/expressions/BlockBuilder.java
+++ b/src/main/java/net/hydromatic/linq4j/expressions/BlockBuilder.java
@@ -18,6 +18,7 @@
package net.hydromatic.linq4j.expressions;
import java.lang.reflect.Modifier;
+import java.lang.reflect.Type;
import java.util.*;
/**
@@ -35,6 +36,7 @@
= new HashMap<Expression, DeclarationStatement>();
private final boolean optimizing;
+ private final BlockBuilder parent;
/**
* Creates a non-optimizing BlockBuilder.
@@ -49,7 +51,17 @@
* @param optimizing Whether to eliminate common sub-expressions
*/
public BlockBuilder(boolean optimizing) {
+ this(optimizing, null);
+ }
+
+ /**
+ * Creates a BlockBuilder.
+ *
+ * @param optimizing Whether to eliminate common sub-expressions
+ */
+ public BlockBuilder(boolean optimizing, BlockBuilder parent) {
this.optimizing = optimizing;
+ this.parent = parent;
}
/**
@@ -126,8 +138,7 @@
statements.remove(statements.size() - 1);
result = append_(name, ((GotoStatement) statement).expression,
optimize);
- if (result instanceof ParameterExpression
- || result instanceof ConstantExpression) {
+ if (isSimpleExpression(result)) {
// already simple; no need to declare a variable or
// even to evaluate the expression
} else {
@@ -182,17 +193,13 @@
private Expression append_(String name, Expression expression,
boolean optimize) {
- // We treat "1" and "null" as atoms, but not "(Comparator) null".
- if (expression instanceof ParameterExpression
- || (expression instanceof ConstantExpression
- && (((ConstantExpression) expression).value != null
- || expression.type == Object.class))) {
+ if (isSimpleExpression(expression)) {
// already simple; no need to declare a variable or
// even to evaluate the expression
return expression;
}
if (optimizing && optimize) {
- DeclarationStatement decl = expressionForReuse.get(expression);
+ DeclarationStatement decl = getComputedExpression(expression);
if (decl != null) {
return decl.parameter;
}
@@ -203,6 +210,24 @@
return declare.parameter;
}
+ /**
+ * Checks if experssion is simple enough for always inline
+ * @param expr expression to test
+ * @return true when given expression is safe to always inline
+ */
+ protected boolean isSimpleExpression(Expression expr) {
+ if (expr instanceof ParameterExpression
+ || expr instanceof ConstantExpression) {
+ return true;
+ }
+ if (expr instanceof UnaryExpression) {
+ UnaryExpression una = (UnaryExpression) expr;
+ return una.getNodeType() == ExpressionType.Convert
+ && isSimpleExpression(una.expression);
+ }
+ return false;
+ }
+
protected boolean isSafeForReuse(DeclarationStatement decl) {
return (decl.modifiers & Modifier.FINAL) != 0
&& decl.initializer != null;
@@ -210,10 +235,43 @@
protected void addExpresisonForReuse(DeclarationStatement decl) {
if (isSafeForReuse(decl)) {
- expressionForReuse.put(decl.initializer, decl);
+ Expression expr = normalizeDeclaration(decl);
+ expressionForReuse.put(expr, decl);
}
}
+ /**
+ * Prepares declaration for inlining: adds cast
+ * @param decl inlining candidate
+ * @return normalized expression
+ */
+ private Expression normalizeDeclaration(DeclarationStatement decl) {
+ Expression expr = decl.initializer;
+ Type declType = decl.parameter.getType();
+ if (expr == null) {
+ expr = Expressions.constant(null, declType);
+ } else if (expr.getType() != declType) {
+ expr = Expressions.convert_(expr, declType);
+ }
+ return expr;
+ }
+
+ /**
+ * Returns the reference to ParameterExpression if given expression was
+ * already computed and stored to local variable
+ * @param expr expression to test
+ * @return existing ParameterExpression or null
+ */
+ public DeclarationStatement getComputedExpression(Expression expr) {
+ if (parent != null) {
+ DeclarationStatement decl = parent.getComputedExpression(expr);
+ if (decl != null) {
+ return decl;
+ }
+ }
+ return optimizing ? expressionForReuse.get(expr) : null;
+ }
+
public void add(Statement statement) {
statements.add(statement);
if (statement instanceof DeclarationStatement) {
@@ -261,18 +319,20 @@
new IdentityHashMap<ParameterExpression, Expression>();
final SubstituteVariableVisitor visitor = new SubstituteVariableVisitor(
subMap);
+ final OptimizeVisitor optimizer = new OptimizeVisitor();
final ArrayList<Statement> oldStatements = new ArrayList<Statement>(
statements);
statements.clear();
+
for (Statement oldStatement : oldStatements) {
if (oldStatement instanceof DeclarationStatement) {
DeclarationStatement statement = (DeclarationStatement) oldStatement;
final Slot slot = useCounter.map.get(statement.parameter);
int count = slot.count;
- if (Expressions.isConstantNull(slot.expression)) {
- // Don't allow 'final Type t = null' to be inlined. There
- // is an implicit cast.
- count = 100;
+ if (count > 1 && isSafeForReuse(statement)
+ && isSimpleExpression(statement.initializer)) {
+ // Inline simple final constants
+ count = 1;
}
if (statement.parameter.name.startsWith("_")) {
// Don't inline variables whose name begins with "_". This
@@ -289,32 +349,36 @@
// anonymous classes.
count = 100;
}
+ Expression normalized = normalizeDeclaration(statement);
+ expressionForReuse.remove(normalized);
switch (count) {
case 0:
// Only declared, never used. Throw away declaration.
break;
case 1:
// declared, used once. inline it.
- subMap.put(slot.parameter, slot.expression);
+ subMap.put(slot.parameter, normalized);
break;
default:
- statements.add(statement);
+ if (!subMap.isEmpty()) {
+ oldStatement = oldStatement.accept(visitor); // remap
+ }
+ oldStatement = oldStatement.accept(optimizer);
+ if (oldStatement != OptimizeVisitor.EMPTY_STATEMENT) {
+ if (oldStatement instanceof DeclarationStatement) {
+ addExpresisonForReuse((DeclarationStatement) oldStatement);
+ }
+ statements.add(oldStatement);
+ }
break;
}
} else {
- statements.add(oldStatement.accept(visitor));
- }
- }
- if (!subMap.isEmpty()) {
- oldStatements.clear();
- oldStatements.addAll(statements);
- statements.clear();
- expressionForReuse.clear();
- for (Statement oldStatement : oldStatements) {
- Statement remappedStatement = oldStatement.accept(visitor);
- statements.add(remappedStatement);
- if (remappedStatement instanceof DeclarationStatement) {
- addExpresisonForReuse((DeclarationStatement) remappedStatement);
+ if (!subMap.isEmpty()) {
+ oldStatement = oldStatement.accept(visitor); // remap
+ }
+ oldStatement = oldStatement.accept(optimizer);
+ if (oldStatement != OptimizeVisitor.EMPTY_STATEMENT) {
+ statements.add(oldStatement);
}
}
}
@@ -338,12 +402,15 @@
public String newName(String suggestion) {
int i = 0;
String candidate = suggestion;
- for (;;) {
- if (!variables.contains(candidate)) {
- return candidate;
- }
+ while (hasVariable(candidate)) {
candidate = suggestion + (i++);
}
+ return candidate;
+ }
+
+ public boolean hasVariable(String name) {
+ return variables.contains(name)
+ || (parent != null && parent.hasVariable(name));
}
public BlockBuilder append(Expression expression) {
@@ -380,17 +447,32 @@
return super.visit(parameterExpression);
}
+ @Override
+ public Expression visit(UnaryExpression unaryExpression, Expression
+ expression) {
+ if (unaryExpression.getNodeType().modifiesLvalue) {
+ expression = unaryExpression.expression; // avoid substitution
+ if (expression instanceof ParameterExpression) {
+ // avoid "optimization of" int t=1; t++; to 1++
+ return unaryExpression;
+ }
+ }
+ return super.visit(unaryExpression, expression);
+ }
+
@Override public Expression visit(BinaryExpression binaryExpression,
Expression expression0, Expression expression1) {
- if (binaryExpression.getNodeType() == ExpressionType.Assign
- && expression0 instanceof ParameterExpression) {
- // If t is a declaration used only once, replace
- // int t;
- // int v = (t = 1) != a ? c : d;
- // with
- // int v = 1 != a ? c : d;
- if (map.containsKey(expression0)) {
- return expression1.accept(this);
+ if (binaryExpression.getNodeType().modifiesLvalue) {
+ expression0 = binaryExpression.expression0; // avoid substitution
+ if (expression0 instanceof ParameterExpression) {
+ // If t is a declaration used only once, replace
+ // int t;
+ // int v = (t = 1) != a ? c : d;
+ // with
+ // int v = 1 != a ? c : d;
+ if (map.containsKey(expression0)) {
+ return expression1.accept(this);
+ }
}
}
return super.visit(binaryExpression, expression0, expression1);
@@ -401,6 +483,7 @@
private final Map<ParameterExpression, Slot> map =
new IdentityHashMap<ParameterExpression, Slot>();
+ @Override
public Expression visit(ParameterExpression parameter) {
final Slot slot = map.get(parameter);
if (slot != null) {
diff --git a/src/main/java/net/hydromatic/linq4j/expressions/ConditionalStatement.java b/src/main/java/net/hydromatic/linq4j/expressions/ConditionalStatement.java
index 5ed1f57..09a2f48 100644
--- a/src/main/java/net/hydromatic/linq4j/expressions/ConditionalStatement.java
+++ b/src/main/java/net/hydromatic/linq4j/expressions/ConditionalStatement.java
@@ -32,7 +32,7 @@
* </p>
*/
public class ConditionalStatement extends Statement {
- private final List<Node> expressionList;
+ public final List<Node> expressionList;
public ConditionalStatement(List<Node> expressionList) {
super(ExpressionType.Conditional, Void.TYPE);
@@ -41,12 +41,9 @@
}
@Override
- public ConditionalStatement accept(Visitor visitor) {
+ public Statement accept(Visitor visitor) {
List<Node> list = Expressions.acceptNodes(expressionList, visitor);
- if (!list.equals(expressionList)) {
- return new ConditionalStatement(list);
- }
- return this;
+ return visitor.visit(this, list);
}
@Override
diff --git a/src/main/java/net/hydromatic/linq4j/expressions/ConstantExpression.java b/src/main/java/net/hydromatic/linq4j/expressions/ConstantExpression.java
index 189123a..e0d8776 100644
--- a/src/main/java/net/hydromatic/linq4j/expressions/ConstantExpression.java
+++ b/src/main/java/net/hydromatic/linq4j/expressions/ConstantExpression.java
@@ -62,6 +62,12 @@
@Override
void accept(ExpressionWriter writer, int lprec, int rprec) {
+ if (value == null) {
+ if (!writer.requireParentheses(this, lprec, rprec)) {
+ writer.append("(").append(type).append(") null");
+ }
+ return;
+ }
write(writer, value, type);
}
diff --git a/src/main/java/net/hydromatic/linq4j/expressions/ConstantUntypedNull.java b/src/main/java/net/hydromatic/linq4j/expressions/ConstantUntypedNull.java
new file mode 100644
index 0000000..acaf864
--- /dev/null
+++ b/src/main/java/net/hydromatic/linq4j/expressions/ConstantUntypedNull.java
@@ -0,0 +1,50 @@
+/*
+// Licensed to Julian Hyde under one or more contributor license
+// agreements. See the NOTICE file distributed with this work for
+// additional information regarding copyright ownership.
+//
+// Julian Hyde licenses this file to you under the Apache License,
+// Version 2.0 (the "License"); you may not use this file except in
+// compliance with the License. You may obtain a copy of the License at:
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+*/
+package net.hydromatic.linq4j.expressions;
+
+/**
+ * Represents a constant null of unknown type
+ * Java allows type inference for such nulls, thus "null" cannot always be
+ * replaced to (Object)null and vise versa.
+ *
+ * ConstantExpression(null, Object.class) is not equal to ConstantUntypedNull
+ * However, optimizers might treat all the nulls equal (e.g. in case of
+ * comparison).
+ */
+public class ConstantUntypedNull extends ConstantExpression {
+ public static final ConstantExpression INSTANCE = new ConstantUntypedNull();
+
+ private ConstantUntypedNull() {
+ super(Object.class, null);
+ }
+
+ @Override
+ void accept(ExpressionWriter writer, int lprec, int rprec) {
+ writer.append("null");
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ return o == INSTANCE;
+ }
+
+ @Override
+ public int hashCode() {
+ return ConstantUntypedNull.class.hashCode();
+ }
+}
diff --git a/src/main/java/net/hydromatic/linq4j/expressions/ExpressionType.java b/src/main/java/net/hydromatic/linq4j/expressions/ExpressionType.java
index 0277ce8..51264cd 100644
--- a/src/main/java/net/hydromatic/linq4j/expressions/ExpressionType.java
+++ b/src/main/java/net/hydromatic/linq4j/expressions/ExpressionType.java
@@ -353,7 +353,7 @@
/**
* An assignment operation, such as (a = b).
*/
- Assign(" = ", false, 14, true),
+ Assign(" = ", null, false, 14, true, true),
/**
* A block of expressions.
@@ -449,49 +449,49 @@
* An addition compound assignment operation, such as (a +=
* b), without overflow checking, for numeric operands.
*/
- AddAssign(" += ", false, 14, true),
+ AddAssign(" += ", null, false, 14, true, true),
/**
* A bitwise or logical AND compound assignment operation,
* such as (a &= b) in C#.
*/
- AndAssign(" &= ", false, 14, true),
+ AndAssign(" &= ", null, false, 14, true, true),
/**
* An division compound assignment operation, such as (a /=
* b), for numeric operands.
*/
- DivideAssign(" /= ", false, 14, true),
+ DivideAssign(" /= ", null, false, 14, true, true),
/**
* A bitwise or logical XOR compound assignment operation,
* such as (a ^= b) in C#.
*/
- ExclusiveOrAssign(" ^= ", false, 14, true),
+ ExclusiveOrAssign(" ^= ", null, false, 14, true, true),
/**
* A bitwise left-shift compound assignment, such as (a <<=
* b).
*/
- LeftShiftAssign(" <<= ", false, 14, true),
+ LeftShiftAssign(" <<= ", null, false, 14, true, true),
/**
* An arithmetic remainder compound assignment operation,
* such as (a %= b) in C#.
*/
- ModuloAssign(" %= ", false, 14, true),
+ ModuloAssign(" %= ", null, false, 14, true, true),
/**
* A multiplication compound assignment operation, such as (a
* *= b), without overflow checking, for numeric operands.
*/
- MultiplyAssign(" *= ", false, 14, true),
+ MultiplyAssign(" *= ", null, false, 14, true, true),
/**
* A bitwise or logical OR compound assignment, such as (a |=
* b) in C#.
*/
- OrAssign(" |= ", false, 14, true),
+ OrAssign(" |= ", null, false, 14, true, true),
/**
* A compound assignment operation that raises a number to a
@@ -503,55 +503,55 @@
* A bitwise right-shift compound assignment operation, such
* as (a >>= b).
*/
- RightShiftAssign(" >>= ", false, 14, true),
+ RightShiftAssign(" >>= ", null, false, 14, true, true),
/**
* A subtraction compound assignment operation, such as (a -=
* b), without overflow checking, for numeric operands.
*/
- SubtractAssign(" -= ", false, 14, true),
+ SubtractAssign(" -= ", null, false, 14, true, true),
/**
* An addition compound assignment operation, such as (a +=
* b), with overflow checking, for numeric operands.
*/
- AddAssignChecked(" += ", false, 14, true),
+ AddAssignChecked(" += ", null, false, 14, true),
/**
* A multiplication compound assignment operation, such as (a
* *= b), that has overflow checking, for numeric operands.
*/
- MultiplyAssignChecked(" *= ", false, 14, true),
+ MultiplyAssignChecked(" *= ", null, false, 14, true, true),
/**
* A subtraction compound assignment operation, such as (a -=
* b), that has overflow checking, for numeric operands.
*/
- SubtractAssignChecked(" -= ", false, 14, true),
+ SubtractAssignChecked(" -= ", null, false, 14, true, true),
/**
* A unary prefix increment, such as (++a). The object a
* should be modified in place.
*/
- PreIncrementAssign("++", false, 2, true),
+ PreIncrementAssign("++", null, false, 2, true, true),
/**
* A unary prefix decrement, such as (--a). The object a
* should be modified in place.
*/
- PreDecrementAssign("--", false, 2, true),
+ PreDecrementAssign("--", null, false, 2, true, true),
/**
* A unary postfix increment, such as (a++). The object a
* should be modified in place.
*/
- PostIncrementAssign("++", true, 2, true),
+ PostIncrementAssign("++", null, true, 2, true, true),
/**
* A unary postfix decrement, such as (a--). The object a
* should be modified in place.
*/
- PostDecrementAssign("--", true, 2, true),
+ PostDecrementAssign("--", null, true, 2, true, true),
/**
* An exact type test.
@@ -587,6 +587,7 @@
final boolean postfix;
final int lprec;
final int rprec;
+ final boolean modifiesLvalue;
ExpressionType() {
this(null, false, 0, false);
@@ -598,9 +599,15 @@
ExpressionType(String op, String op2, boolean postfix, int prec,
boolean right) {
+ this(op, op2, postfix, prec, right, false);
+ }
+
+ ExpressionType(String op, String op2, boolean postfix, int prec,
+ boolean right, boolean modifiesLvalue) {
this.op = op;
this.op2 = op2;
this.postfix = postfix;
+ this.modifiesLvalue = modifiesLvalue;
this.lprec = (20 - prec) * 2 + (right ? 1 : 0);
this.rprec = (20 - prec) * 2 + (right ? 0 : 1);
}
diff --git a/src/main/java/net/hydromatic/linq4j/expressions/Expressions.java b/src/main/java/net/hydromatic/linq4j/expressions/Expressions.java
index d3be4b3..0d7904d 100644
--- a/src/main/java/net/hydromatic/linq4j/expressions/Expressions.java
+++ b/src/main/java/net/hydromatic/linq4j/expressions/Expressions.java
@@ -528,7 +528,7 @@
public static ConstantExpression constant(Object value) {
Class type;
if (value == null) {
- type = Object.class;
+ return ConstantUntypedNull.INSTANCE;
} else {
final Class clazz = value.getClass();
final Primitive primitive = Primitive.ofBox(clazz);
@@ -964,8 +964,20 @@
*/
public static ConditionalStatement ifThenElse(Expression test,
Node... nodes) {
- return new ConditionalStatement(
- new FluentArrayList<Node>().append(test).appendAll(nodes));
+ return ifThenElse(new FluentArrayList<Node>().append(test)
+ .appendAll(nodes));
+ }
+
+ /**
+ * Creates a ConditionalExpression that represents a conditional
+ * block with if and else statements:
+ * <code>if (test) stmt1 [ else if (test2) stmt2 ]... [ else stmtN ]</code>.
+ */
+ public static ConditionalStatement ifThenElse(Iterable<? extends Node>
+ nodes) {
+ List<Node> list = toList(nodes);
+ assert list.size() >= 2 : "At least one test and one statement is required";
+ return new ConditionalStatement(list);
}
/**
@@ -1486,11 +1498,19 @@
final Type type;
switch (ternaryType) {
case Conditional:
- type = isConstantNull(e1)
- ? box(e2.getType())
- : isConstantNull(e2)
- ? box(e1.getType())
- : Types.gcd(e1.getType(), e2.getType());
+ if (e1 instanceof ConstantUntypedNull) {
+ type = box(e2.getType());
+ if (e1.getType() != type) {
+ e1 = constant(null, type);
+ }
+ } else if (e2 instanceof ConstantUntypedNull) {
+ type = box(e1.getType());
+ if (e2.getType() != type) {
+ e2 = constant(null, type);
+ }
+ } else {
+ type = Types.gcd(e1.getType(), e2.getType());
+ }
break;
default:
type = e1.getType();
@@ -3074,7 +3094,16 @@
}
final List<Statement> statements1 = new ArrayList<Statement>();
for (Statement statement : statements) {
- statements1.add(statement.accept(visitor));
+ Statement newStatement = statement.accept(visitor);
+ if (newStatement instanceof GotoStatement) {
+ GotoStatement goto_ = (GotoStatement) newStatement;
+ if (goto_.kind == GotoExpressionKind.Sequence
+ && goto_.expression == null) {
+ // ignore empty statements
+ continue;
+ }
+ }
+ statements1.add(newStatement);
}
return statements1;
}
diff --git a/src/main/java/net/hydromatic/linq4j/expressions/OptimizeVisitor.java b/src/main/java/net/hydromatic/linq4j/expressions/OptimizeVisitor.java
new file mode 100644
index 0000000..e0567eb
--- /dev/null
+++ b/src/main/java/net/hydromatic/linq4j/expressions/OptimizeVisitor.java
@@ -0,0 +1,320 @@
+/*
+// Licensed to Julian Hyde under one or more contributor license
+// agreements. See the NOTICE file distributed with this work for
+// additional information regarding copyright ownership.
+//
+// Julian Hyde licenses this file to you under the Apache License,
+// Version 2.0 (the "License"); you may not use this file except in
+// compliance with the License. You may obtain a copy of the License at:
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+*/
+package net.hydromatic.linq4j.expressions;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static net.hydromatic.linq4j.expressions.ExpressionType.Equal;
+import static net.hydromatic.linq4j.expressions.ExpressionType.NotEqual;
+
+/**
+ * Visitor that optimizes expressions.
+ * <p/>
+ * <p>The optimizations are essential, not mere tweaks. Without
+ * optimization, expressions such as {@code false == null} will be left in,
+ * which are invalid to Janino (because it does not automatically box
+ * primitives).</p>
+ */
+public class OptimizeVisitor extends Visitor {
+ public static final ConstantExpression FALSE_EXPR =
+ Expressions.constant(false);
+ public static final ConstantExpression TRUE_EXPR =
+ Expressions.constant(true);
+ public static final MemberExpression BOXED_FALSE_EXPR =
+ Expressions.field(null, Boolean.class, "FALSE");
+ public static final MemberExpression BOXED_TRUE_EXPR =
+ Expressions.field(null, Boolean.class, "TRUE");
+ public static final Statement EMPTY_STATEMENT = Expressions.statement(null);
+
+ @Override
+ public Expression visit(
+ TernaryExpression ternary,
+ Expression expression0,
+ Expression expression1,
+ Expression expression2) {
+ switch (ternary.getNodeType()) {
+ case Conditional:
+ Boolean always = always(expression0);
+ if (always != null) {
+ // true ? y : z === y
+ // false ? y : z === z
+ return always
+ ? expression1
+ : expression2;
+ }
+ if (expression1.equals(expression2)) {
+ // a ? b : b === b
+ return expression1;
+ }
+ // !a ? b : c == a ? c : b
+ if (expression0 instanceof UnaryExpression) {
+ UnaryExpression una = (UnaryExpression) expression0;
+ if (una.getNodeType() == ExpressionType.Not) {
+ return Expressions.makeTernary(ternary.getNodeType(),
+ una.expression, expression2, expression1);
+ }
+ }
+
+ if (expression0 instanceof BinaryExpression
+ && (expression0.getNodeType() == ExpressionType.Equal
+ || expression0.getNodeType() == ExpressionType.NotEqual)) {
+ BinaryExpression cmp = (BinaryExpression) expression0;
+ Expression expr = null;
+ if (eq(cmp.expression0, expression2)
+ && eq(cmp.expression1, expression1)) {
+ // a == b ? b : a === a (hint: if a==b, then a == b ? a : a)
+ // a != b ? b : a === b (hint: if a==b, then a != b ? b : b)
+ expr = expression0.getNodeType() == ExpressionType.Equal
+ ? expression2 : expression1;
+ }
+ if (eq(cmp.expression0, expression1)
+ && eq(cmp.expression1, expression2)) {
+ // a == b ? a : b === b (hint: if a==b, then a == b ? b : b)
+ // a != b ? a : b === a (hint: if a==b, then a == b ? a : a)
+ expr = expression0.getNodeType() == ExpressionType.Equal
+ ? expression2 : expression1;
+ }
+ if (expr != null) {
+ return expr;
+ }
+ }
+ }
+ return super.visit(ternary, expression0, expression1, expression2);
+ }
+
+ @Override
+ public Expression visit(
+ BinaryExpression binary,
+ Expression expression0,
+ Expression expression1) {
+ //
+ Expression result;
+ switch (binary.getNodeType()) {
+ case AndAlso:
+ case OrElse:
+ if (eq(expression0, expression1)) {
+ return expression0;
+ }
+ }
+ switch (binary.getNodeType()) {
+ case Equal:
+ case NotEqual:
+ if (eq(expression0, expression1)) {
+ return binary.getNodeType() == Equal ? TRUE_EXPR : FALSE_EXPR;
+ } else if (expression0 instanceof ConstantExpression && expression1
+ instanceof ConstantExpression) {
+ ConstantExpression c0 = (ConstantExpression) expression0;
+ ConstantExpression c1 = (ConstantExpression) expression1;
+ if (c0.getType() == c1.getType()
+ || !(Primitive.is(c0.getType()) || Primitive.is(c1.getType()))) {
+ return binary.getNodeType() == NotEqual ? TRUE_EXPR : FALSE_EXPR;
+ }
+ }
+ if (expression0 instanceof TernaryExpression
+ && expression0.getNodeType() == ExpressionType.Conditional) {
+ TernaryExpression ternary = (TernaryExpression) expression0;
+ Expression expr = null;
+ if (eq(ternary.expression1, expression1)) {
+ // (a ? b : c) == b === a || c == b
+ expr = Expressions.orElse(ternary.expression0,
+ Expressions.equal(ternary.expression2, expression1));
+ } else if (eq(ternary.expression2, expression1)) {
+ // (a ? b : c) == c === !a || b == c
+ expr = Expressions.orElse(Expressions.not(ternary.expression0),
+ Expressions.equal(ternary.expression1, expression1));
+ }
+ if (expr != null) {
+ if (binary.getNodeType() == ExpressionType.NotEqual) {
+ expr = Expressions.not(expr);
+ }
+ return expr.accept(this);
+ }
+ }
+ // drop down
+ case AndAlso:
+ case OrElse:
+ result = visit0(binary, expression0, expression1);
+ if (result != null) {
+ return result;
+ }
+ result = visit0(binary, expression1, expression0);
+ if (result != null) {
+ return result;
+ }
+ }
+ return super.visit(binary, expression0, expression1);
+ }
+
+ private Expression visit0(
+ BinaryExpression binary,
+ Expression expression0,
+ Expression expression1) {
+ Boolean always;
+ switch (binary.getNodeType()) {
+ case AndAlso:
+ always = always(expression0);
+ if (always != null) {
+ return always
+ ? expression1
+ : FALSE_EXPR;
+ }
+ break;
+ case OrElse:
+ always = always(expression0);
+ if (always != null) {
+ // true or x --> true
+ // false or x --> x
+ return always
+ ? TRUE_EXPR
+ : expression1;
+ }
+ break;
+ case Equal:
+ if (isConstantNull(expression1)
+ && Primitive.is(expression0.getType())) {
+ return FALSE_EXPR;
+ }
+ // a == true -> a
+ // a == false -> !a
+ always = always(expression0);
+ if (always != null) {
+ return always ? expression1 : Expressions.not(expression1);
+ }
+ break;
+ case NotEqual:
+ if (isConstantNull(expression1)
+ && Primitive.is(expression0.getType())) {
+ return TRUE_EXPR;
+ }
+ // a != true -> !a
+ // a != false -> a
+ always = always(expression0);
+ if (always != null) {
+ return always ? Expressions.not(expression1) : expression1;
+ }
+ break;
+ }
+ return null;
+ }
+
+ @Override
+ public Expression visit(UnaryExpression unaryExpression, Expression
+ expression) {
+ if (unaryExpression.getNodeType() == ExpressionType.Convert) {
+ if (expression.getType() == unaryExpression.getType()) {
+ return expression;
+ }
+ if (expression instanceof ConstantExpression) {
+ return Expressions.constant(((ConstantExpression) expression).value,
+ unaryExpression.getType());
+ }
+ }
+ return super.visit(unaryExpression, expression);
+ }
+
+ @Override
+ public Statement visit(ConditionalStatement conditionalStatement,
+ List<Node> list) {
+ // if (false) { <-- remove branch
+ // } if (true) { <-- stop here
+ // } else if (...)
+ // } else {...}
+ boolean optimal = true;
+ for (int i = 0; i < list.size() - 1 && optimal; i += 2) {
+ Boolean always = always((Expression) list.get(i));
+ if (always == null) {
+ continue;
+ }
+ if (i == 0 && always) {
+ // when the very first test is always true, just return its statement
+ return (Statement) list.get(1);
+ }
+ optimal = false;
+ }
+ if (optimal) {
+ // Nothing to optimize
+ return super.visit(conditionalStatement, list);
+ }
+ List<Node> newList = new ArrayList<Node>(list.size());
+ // Iterate over all the tests, except the latest "else"
+ for (int i = 0; i < list.size() - 1; i += 2) {
+ Expression test = (Expression) list.get(i);
+ Node stmt = list.get(i + 1);
+ Boolean always = always(test);
+ if (always == null) {
+ newList.add(test);
+ newList.add(stmt);
+ continue;
+ }
+ if (always) {
+ // No need to verify other tests
+ newList.add(stmt);
+ break;
+ }
+ }
+ // We might have dangling "else", however if we have just single item
+ // it means we have if (false) else if(false) else if (true) {...} code.
+ // Then we just return statement from true branch
+ if (list.size() == 1) {
+ return (Statement) list.get(0);
+ }
+ // Add "else" from original list
+ if (newList.size() % 2 == 0 && list.size() % 2 == 1) {
+ Node elseBlock = list.get(list.size() - 1);
+ if (newList.isEmpty()) {
+ return (Statement) elseBlock;
+ }
+ newList.add(elseBlock);
+ }
+ if (newList.isEmpty()) {
+ return EMPTY_STATEMENT;
+ }
+ return super.visit(conditionalStatement, newList);
+ }
+
+ private boolean isConstantNull(Expression expression) {
+ return expression instanceof ConstantExpression
+ && ((ConstantExpression) expression).value == null;
+ }
+
+ /**
+ * Returns whether an expression always evaluates to true or false.
+ * Assumes that expression has already been optimized.
+ */
+ private static Boolean always(Expression x) {
+ if (x.equals(FALSE_EXPR) || x.equals(BOXED_FALSE_EXPR)) {
+ return Boolean.FALSE;
+ }
+ if (x.equals(TRUE_EXPR) || x.equals(BOXED_TRUE_EXPR)) {
+ return Boolean.TRUE;
+ }
+ return null;
+ }
+
+ /**
+ * Treats two expressions equal even if they represent different null types
+ */
+ private static boolean eq(Expression a, Expression b) {
+ return a.equals(b)
+ || (a instanceof ConstantExpression
+ && b instanceof ConstantExpression
+ && ((ConstantExpression) a).value == ((ConstantExpression) b).value
+ );
+ }
+}
diff --git a/src/main/java/net/hydromatic/linq4j/expressions/ThrowStatement.java b/src/main/java/net/hydromatic/linq4j/expressions/ThrowStatement.java
index 5807213..9d3bf7a 100644
--- a/src/main/java/net/hydromatic/linq4j/expressions/ThrowStatement.java
+++ b/src/main/java/net/hydromatic/linq4j/expressions/ThrowStatement.java
@@ -30,7 +30,8 @@
@Override
public Statement accept(Visitor visitor) {
- return visitor.visit(this);
+ Expression expression = this.expression.accept(visitor);
+ return visitor.visit(this, expression);
}
@Override
diff --git a/src/main/java/net/hydromatic/linq4j/expressions/Visitor.java b/src/main/java/net/hydromatic/linq4j/expressions/Visitor.java
index 7fd7edf..92a2818 100644
--- a/src/main/java/net/hydromatic/linq4j/expressions/Visitor.java
+++ b/src/main/java/net/hydromatic/linq4j/expressions/Visitor.java
@@ -33,6 +33,13 @@
: Expressions.while_(condition, body);
}
+ public Statement visit(ConditionalStatement conditionalStatement,
+ List<Node> list) {
+ return list.equals(conditionalStatement.expressionList)
+ ? conditionalStatement
+ : Expressions.ifThenElse(list);
+ }
+
public BlockStatement visit(BlockStatement blockStatement,
List<Statement> statements) {
return statements.equals(blockStatement.statements)
@@ -55,11 +62,18 @@
public ForStatement visit(ForStatement forStatement,
List<DeclarationStatement> declarations, Expression condition,
Expression post, Statement body) {
- return forStatement;
+ return declarations.equals(forStatement.declarations)
+ && condition == forStatement.condition
+ && post == forStatement.post
+ && body == forStatement.body
+ ? forStatement
+ : Expressions.for_(declarations, condition, post, body);
}
- public Statement visit(ThrowStatement throwStatement) {
- return throwStatement;
+ public Statement visit(ThrowStatement throwStatement, Expression expression) {
+ return expression == throwStatement.expression
+ ? throwStatement
+ : Expressions.throw_(expression);
}
public DeclarationStatement visit(DeclarationStatement declarationStatement,
diff --git a/src/test/java/net/hydromatic/linq4j/test/BlockBuilderBase.java b/src/test/java/net/hydromatic/linq4j/test/BlockBuilderBase.java
new file mode 100644
index 0000000..f4f9750
--- /dev/null
+++ b/src/test/java/net/hydromatic/linq4j/test/BlockBuilderBase.java
@@ -0,0 +1,48 @@
+/*
+// Licensed to Julian Hyde under one or more contributor license
+// agreements. See the NOTICE file distributed with this work for
+// additional information regarding copyright ownership.
+//
+// Julian Hyde licenses this file to you under the Apache License,
+// Version 2.0 (the "License"); you may not use this file except in
+// compliance with the License. You may obtain a copy of the License at:
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+*/
+package net.hydromatic.linq4j.test;
+
+import net.hydromatic.linq4j.expressions.BlockBuilder;
+import net.hydromatic.linq4j.expressions.Expression;
+import net.hydromatic.linq4j.expressions.Expressions;
+import net.hydromatic.linq4j.expressions.Statement;
+
+/**
+ * Base methods and constant for simplified Expression testing
+ */
+public abstract class BlockBuilderBase {
+ public static final Expression NULL = Expressions.constant(null);
+ public static final Expression NULL_INTEGER = Expressions.constant(null,
+ Integer.class);
+ public static final Expression ONE = Expressions.constant(1);
+ public static final Expression TWO = Expressions.constant(2);
+ public static final Expression THREE = Expressions.constant(3);
+ public static final Expression FOUR = Expressions.constant(4);
+ public static final Expression TRUE = Expressions.constant(true);
+ public static final Expression FALSE = Expressions.constant(false);
+
+ public static String optimize(Expression expr) {
+ return optimize(Expressions.return_(null, expr));
+ }
+
+ public static String optimize(Statement statement) {
+ BlockBuilder b = new BlockBuilder(true);
+ b.add(statement);
+ return b.toBlock().toString();
+ }
+}
diff --git a/src/test/java/net/hydromatic/linq4j/test/BlockBuilderTest.java b/src/test/java/net/hydromatic/linq4j/test/BlockBuilderTest.java
new file mode 100644
index 0000000..0d93c46
--- /dev/null
+++ b/src/test/java/net/hydromatic/linq4j/test/BlockBuilderTest.java
@@ -0,0 +1,55 @@
+/*
+// Licensed to Julian Hyde under one or more contributor license
+// agreements. See the NOTICE file distributed with this work for
+// additional information regarding copyright ownership.
+//
+// Julian Hyde licenses this file to you under the Apache License,
+// Version 2.0 (the "License"); you may not use this file except in
+// compliance with the License. You may obtain a copy of the License at:
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+*/
+package net.hydromatic.linq4j.test;
+
+import net.hydromatic.linq4j.expressions.BlockBuilder;
+import net.hydromatic.linq4j.expressions.Expression;
+import net.hydromatic.linq4j.expressions.Expressions;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Tests BlockBuilder
+ */
+public class BlockBuilderTest extends BlockBuilderBase {
+ BlockBuilder b;
+
+ @Before
+ public void prepareBuilder() {
+ b = new BlockBuilder(true);
+ }
+
+ @Test
+ public void reuseExpressionsFromUpperLevel() {
+ Expression x = b.append("x", Expressions.add(ONE, TWO));
+ BlockBuilder nested = new BlockBuilder(true, b);
+ Expression y = nested.append("y", Expressions.add(ONE, TWO));
+ nested.add(Expressions.return_(null, Expressions.add(y, y)));
+ b.add(nested.toBlock());
+ assertEquals("{\n"
+ + " final int x = 1 + 2;\n"
+ + " {\n"
+ + " return x + x;\n"
+ + " }\n"
+ + "}\n", b.toBlock().toString());
+ }
+
+}
diff --git a/src/test/java/net/hydromatic/linq4j/test/ExpressionTest.java b/src/test/java/net/hydromatic/linq4j/test/ExpressionTest.java
index 025526d..46c6912 100644
--- a/src/test/java/net/hydromatic/linq4j/test/ExpressionTest.java
+++ b/src/test/java/net/hydromatic/linq4j/test/ExpressionTest.java
@@ -907,9 +907,8 @@
BlockStatement expression = statements.toBlock();
assertEquals(
"{\n"
- + " final java.util.Comparator comparator = null;\n"
+ " return new java.util.TreeSet(\n"
- + " comparator).add(null);\n"
+ + " (java.util.Comparator) null).add(null);\n"
+ "}\n",
Expressions.toString(expression));
expression.accept(new Visitor());
@@ -1073,49 +1072,6 @@
Expressions.return_(null, Expressions.constant(1)))));
}
- @Test public void assignInCondition() {
- final BlockBuilder builder = new BlockBuilder(true);
- final ParameterExpression t = Expressions.parameter(int.class, "t");
-
- builder.add(Expressions.declare(0, t, null));
-
- Expression v = builder.append("v",
- Expressions.makeTernary(ExpressionType.Conditional,
- Expressions.makeBinary(ExpressionType.NotEqual,
- Expressions.assign(t, Expressions.constant(1)),
- Expressions.constant(2)),
- t,
- Expressions.constant(3)));
- builder.add(Expressions.return_(null, v));
- assertEquals(
- "{\n"
- + " int t;\n"
- + " return (t = 1) != 2 ? t : 3;\n"
- + "}\n",
- Expressions.toString(builder.toBlock()));
- }
-
- @Test public void assignInConditionOptimizedOut() {
- final BlockBuilder builder = new BlockBuilder(true);
- final ParameterExpression t = Expressions.parameter(int.class, "t");
-
- builder.add(Expressions.declare(0, t, null));
-
- Expression v = builder.append("v",
- Expressions.makeTernary(ExpressionType.Conditional,
- Expressions.makeBinary(ExpressionType.NotEqual,
- Expressions.assign(t, Expressions.constant(1)),
- Expressions.constant(2)),
- Expressions.constant(4),
- Expressions.constant(3)));
- builder.add(Expressions.return_(null, v));
- assertEquals(
- "{\n"
- + " return 1 != 2 ? 4 : 3;\n"
- + "}\n",
- Expressions.toString(builder.toBlock()));
- }
-
/** Test for common sub-expression elimination. */
@Test public void testSubExpressionElimination() {
final BlockBuilder builder = new BlockBuilder(true);
@@ -1131,7 +1087,7 @@
Expressions.constant(4)), Short.class));
Expression v0 = builder.append(
"v0",
- Expressions.convert_(v, Integer.class));
+ Expressions.convert_(v, Number.class));
Expression v1 = builder.append(
"v1",
Expressions.convert_(
@@ -1140,7 +1096,7 @@
Expressions.constant(4)), Short.class));
Expression v2 = builder.append(
"v2",
- Expressions.convert_(v, Integer.class));
+ Expressions.convert_(v, Number.class));
Expression v3 = builder.append(
"v3",
Expressions.convert_(
@@ -1149,7 +1105,7 @@
Expressions.constant(4)), Short.class));
Expression v4 = builder.append(
"v4",
- Expressions.convert_(v3, Integer.class));
+ Expressions.convert_(v3, Number.class));
Expression v5 = builder.append("v5", Expressions.call(v4, "intValue"));
Expression v6 = builder.append(
"v6",
@@ -1160,8 +1116,9 @@
builder.add(Expressions.return_(null, v6));
assertEquals(
"{\n"
- + " final Integer v0 = (Integer) (Short) ((Object[]) p)[4];\n"
- + " return v0 == null ? null : v0.intValue() == 1997;\n"
+ + " final Short v = (Short) ((Object[]) p)[4];\n"
+ + " return (Number) v == null ? (Boolean) null : ("
+ + "(Number) v).intValue() == 1997;\n"
+ "}\n",
Expressions.toString(builder.toBlock()));
}
diff --git a/src/test/java/net/hydromatic/linq4j/test/InlinerTest.java b/src/test/java/net/hydromatic/linq4j/test/InlinerTest.java
new file mode 100644
index 0000000..f965119
--- /dev/null
+++ b/src/test/java/net/hydromatic/linq4j/test/InlinerTest.java
@@ -0,0 +1,152 @@
+/*
+// Licensed to Julian Hyde under one or more contributor license
+// agreements. See the NOTICE file distributed with this work for
+// additional information regarding copyright ownership.
+//
+// Julian Hyde licenses this file to you under the Apache License,
+// Version 2.0 (the "License"); you may not use this file except in
+// compliance with the License. You may obtain a copy of the License at:
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+*/
+package net.hydromatic.linq4j.test;
+
+import net.hydromatic.linq4j.expressions.*;
+
+import org.junit.Before;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Tests expression inlining in BlockBuilder
+ */
+public class InlinerTest extends BlockBuilderBase {
+ BlockBuilder b;
+
+ @Before
+ public void prepareBuilder() {
+ b = new BlockBuilder(true);
+ }
+
+ @Test
+ public void inlineSingleUsage() {
+ DeclarationStatement decl = Expressions.declare(16, "x",
+ Expressions.add(ONE, TWO));
+ b.add(decl);
+ b.add(Expressions.return_(null, decl.parameter));
+ assertEquals("{\n return 1 + 2;\n}\n", b.toBlock().toString());
+ }
+
+ @Test
+ public void inlineConstant() {
+ DeclarationStatement decl = Expressions.declare(16, "x", ONE);
+ b.add(decl);
+ b.add(Expressions.return_(null, Expressions.add(decl.parameter,
+ decl.parameter)));
+ assertEquals("{\n return 1 + 1;\n}\n", b.toBlock().toString());
+ }
+
+ @Test
+ public void inlineParameter() {
+ ParameterExpression pe = Expressions.parameter(int.class, "p");
+ DeclarationStatement decl = Expressions.declare(16, "x", pe);
+ b.add(decl);
+ b.add(Expressions.return_(null, Expressions.add(decl.parameter,
+ decl.parameter)));
+ assertEquals("{\n return p + p;\n}\n", b.toBlock().toString());
+ }
+
+ @Test
+ public void noInlineMultipleUsage() {
+ ParameterExpression p1 = Expressions.parameter(int.class, "p1");
+ ParameterExpression p2 = Expressions.parameter(int.class, "p2");
+ DeclarationStatement decl = Expressions.declare(16, "x",
+ Expressions.subtract(p1, p2));
+ b.add(decl);
+ b.add(Expressions.return_(null, Expressions.add(decl.parameter,
+ decl.parameter)));
+ assertEquals("{\n"
+ + " final int x = p1 - p2;\n"
+ + " return x + x;\n"
+ + "}\n",
+ b.toBlock().toString());
+ }
+
+ @Test public void assignInConditionMultipleUsage() {
+ // int t;
+ // return (t = 1) != a ? t : c
+ final BlockBuilder builder = new BlockBuilder(true);
+ final ParameterExpression t = Expressions.parameter(int.class, "t");
+
+ builder.add(Expressions.declare(0, t, null));
+
+ Expression v = builder.append("v",
+ Expressions.makeTernary(ExpressionType.Conditional,
+ Expressions.makeBinary(ExpressionType.NotEqual,
+ Expressions.assign(t, Expressions.constant(1)),
+ Expressions.parameter(int.class, "a")),
+ t,
+ Expressions.parameter(int.class, "c")));
+ builder.add(Expressions.return_(null, v));
+ assertEquals(
+ "{\n"
+ + " int t;\n"
+ + " return (t = 1) != a ? t : c;\n"
+ + "}\n",
+ Expressions.toString(builder.toBlock()));
+ }
+
+ @Test public void assignInConditionOptimizedOut() {
+ // int t;
+ // return (t = 1) != a ? b : c
+ final BlockBuilder builder = new BlockBuilder(true);
+ final ParameterExpression t = Expressions.parameter(int.class, "t");
+
+ builder.add(Expressions.declare(0, t, null));
+
+ Expression v = builder.append("v",
+ Expressions.makeTernary(ExpressionType.Conditional,
+ Expressions.makeBinary(ExpressionType.NotEqual,
+ Expressions.assign(t, Expressions.constant(1)),
+ Expressions.parameter(int.class, "a")),
+ Expressions.parameter(int.class, "b"),
+ Expressions.parameter(int.class, "c")));
+ builder.add(Expressions.return_(null, v));
+ assertEquals(
+ "{\n"
+ + " return 1 != a ? b : c;\n"
+ + "}\n",
+ Expressions.toString(builder.toBlock()));
+ }
+
+ @Test public void assignInConditionMultipleUsageNonOptimized() {
+ // int t = 2;
+ // return (t = 1) != a ? 1 : c
+ final BlockBuilder builder = new BlockBuilder(true);
+ final ParameterExpression t = Expressions.parameter(int.class, "t");
+
+ builder.add(Expressions.declare(0, t, TWO));
+
+ Expression v = builder.append("v",
+ Expressions.makeTernary(ExpressionType.Conditional,
+ Expressions.makeBinary(ExpressionType.NotEqual,
+ Expressions.assign(t, Expressions.constant(1)),
+ Expressions.parameter(int.class, "a")),
+ t,
+ Expressions.parameter(int.class, "c")));
+ builder.add(Expressions.return_(null, v));
+ assertEquals(
+ "{\n"
+ + " int t = 2;\n"
+ + " return (t = 1) != a ? t : c;\n"
+ + "}\n",
+ Expressions.toString(builder.toBlock()));
+ }
+}
diff --git a/src/test/java/net/hydromatic/linq4j/test/Linq4jSuite.java b/src/test/java/net/hydromatic/linq4j/test/Linq4jSuite.java
index 72deb28..1a338d3 100644
--- a/src/test/java/net/hydromatic/linq4j/test/Linq4jSuite.java
+++ b/src/test/java/net/hydromatic/linq4j/test/Linq4jSuite.java
@@ -32,6 +32,9 @@
PrimitiveTest.class,
Linq4jTest.class,
ExpressionTest.class,
+ OptimizerTest.class,
+ InlinerTest.class,
+ BlockBuilderTest.class,
FunctionTest.class,
TypeTest.class
})
diff --git a/src/test/java/net/hydromatic/linq4j/test/OptimizerTest.java b/src/test/java/net/hydromatic/linq4j/test/OptimizerTest.java
new file mode 100644
index 0000000..c840843
--- /dev/null
+++ b/src/test/java/net/hydromatic/linq4j/test/OptimizerTest.java
@@ -0,0 +1,560 @@
+/*
+// Licensed to Julian Hyde under one or more contributor license
+// agreements. See the NOTICE file distributed with this work for
+// additional information regarding copyright ownership.
+//
+// Julian Hyde licenses this file to you under the Apache License,
+// Version 2.0 (the "License"); you may not use this file except in
+// compliance with the License. You may obtain a copy of the License at:
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+*/
+package net.hydromatic.linq4j.test;
+
+import net.hydromatic.linq4j.expressions.*;
+
+import org.junit.Test;
+
+import static org.junit.Assert.*;
+
+/**
+ * Unit test for {@link net.hydromatic.linq4j.expressions.BlockBuilder}
+ * optimization capabilities.
+ */
+public class OptimizerTest extends BlockBuilderBase {
+ @Test
+ public void optimizeComparison() {
+ assertEquals("{\n return true;\n}\n", optimize(
+ Expressions.equal(ONE, ONE)));
+ }
+
+ @Test
+ public void optimizeTernaryAlwaysTrue() {
+ // true ? 1 : 2
+ assertEquals("{\n return 1;\n}\n", optimize(
+ Expressions.condition(TRUE, ONE, TWO)));
+ }
+
+ @Test
+ public void optimizeTernaryAlwaysFalse() {
+ // false ? 1 : 2
+ assertEquals("{\n return 2;\n}\n", optimize(
+ Expressions.condition(FALSE, ONE, TWO)));
+ }
+
+ @Test
+ public void optimizeTernaryAlwaysSame() {
+ // bool ? 1 : 1
+ assertEquals("{\n return 1;\n}\n", optimize(Expressions.condition(
+ Expressions.parameter(boolean.class, "bool"), ONE, ONE)));
+ }
+
+ @Test
+ public void nonOptimizableTernary() {
+ // bool ? 1 : 2
+ assertEquals("{\n return bool ? 1 : 2;\n}\n",
+ optimize(Expressions.condition(
+ Expressions.parameter(boolean.class, "bool"), ONE, TWO)));
+ }
+
+ @Test
+ public void optimizeTernaryRotateNot() {
+ // !bool ? 1 : 2
+ assertEquals("{\n return bool ? 2 : 1;\n}\n",
+ optimize(Expressions.condition(
+ Expressions.not(Expressions.parameter(boolean.class, "bool")),
+ ONE, TWO)));
+ }
+
+ @Test
+ public void optimizeTernaryRotateEqualFalse() {
+ // bool == false ? 1 : 2
+ assertEquals("{\n return bool ? 2 : 1;\n}\n",
+ optimize(Expressions.condition(
+ Expressions.equal(Expressions.parameter(boolean.class, "bool"),
+ FALSE),
+ ONE, TWO)));
+ }
+
+ @Test
+ public void optimizeTernaryInEqualABCeqB() {
+ // (v ? (Integer) null : inp0_) == null
+ assertEquals("{\n return v || inp0_ == null;\n}\n",
+ optimize(Expressions.equal(Expressions.condition(
+ Expressions.parameter(boolean.class, "v"),
+ NULL_INTEGER, Expressions.parameter(Integer.class, "inp0_")),
+ NULL))
+ );
+ }
+
+ @Test
+ public void optimizeTernaryInEqualABCeqC() {
+ // (v ? inp0_ : (Integer) null) == null
+ assertEquals("{\n return !v || inp0_ == null;\n}\n",
+ optimize(Expressions.equal(Expressions.condition(
+ Expressions.parameter(boolean.class, "v"),
+ Expressions.parameter(Integer.class, "inp0_"), NULL_INTEGER),
+ NULL))
+ );
+ }
+
+ @Test
+ public void optimizeTernaryAeqBBA() {
+ // a == b ? b : a
+ ParameterExpression a = Expressions.parameter(boolean.class, "a");
+ ParameterExpression b = Expressions.parameter(boolean.class, "b");
+ assertEquals("{\n return a;\n}\n",
+ optimize(Expressions.condition(Expressions.equal(a, b), b, a)));
+ }
+
+ @Test
+ public void optimizeTernaryAeqBAB() {
+ // a == b ? b : a
+ ParameterExpression a = Expressions.parameter(boolean.class, "a");
+ ParameterExpression b = Expressions.parameter(boolean.class, "b");
+ assertEquals("{\n return b;\n}\n",
+ optimize(Expressions.condition(Expressions.equal(a, b), a, b)));
+ }
+
+ @Test
+ public void optimizeTernaryInEqualABCneqB() {
+ // (v ? (Integer) null : inp0_) != null
+ assertEquals("{\n return !(v || inp0_ == null);\n}\n",
+ optimize(Expressions.notEqual(Expressions.condition(
+ Expressions.parameter(boolean.class, "v"),
+ NULL_INTEGER, Expressions.parameter(Integer.class, "inp0_")),
+ NULL))
+ );
+ }
+
+ @Test
+ public void optimizeTernaryInEqualABCneqC() {
+ // (v ? inp0_ : (Integer) null) != null
+ assertEquals("{\n return !(!v || inp0_ == null);\n}\n",
+ optimize(Expressions.notEqual(Expressions.condition(
+ Expressions.parameter(boolean.class, "v"),
+ Expressions.parameter(Integer.class, "inp0_"), NULL_INTEGER),
+ NULL))
+ );
+ }
+
+ @Test
+ public void optimizeTernaryAneqBBA() {
+ // a != b ? b : a
+ ParameterExpression a = Expressions.parameter(boolean.class, "a");
+ ParameterExpression b = Expressions.parameter(boolean.class, "b");
+ assertEquals("{\n return b;\n}\n",
+ optimize(Expressions.condition(Expressions.notEqual(a, b), b, a)));
+ }
+
+ @Test
+ public void optimizeTernaryAneqBAB() {
+ // a != b ? a : b
+ ParameterExpression a = Expressions.parameter(boolean.class, "a");
+ ParameterExpression b = Expressions.parameter(boolean.class, "b");
+ assertEquals("{\n return a;\n}\n",
+ optimize(Expressions.condition(Expressions.notEqual(a, b), a, b)));
+ }
+ @Test
+ public void andAlsoTrueBool() {
+ // true && bool
+ assertEquals("{\n return bool;\n}\n", optimize(Expressions.andAlso(TRUE,
+ Expressions.parameter(boolean.class,
+ "bool"))));
+ }
+
+ @Test
+ public void andAlsoBoolTrue() {
+ // bool && true
+ assertEquals("{\n return bool;\n}\n", optimize(Expressions.andAlso(
+ Expressions.parameter(boolean.class,
+ "bool"), TRUE)));
+ }
+
+ @Test
+ public void andAlsoFalseBool() {
+ // false && bool
+ assertEquals("{\n return false;\n}\n", optimize(Expressions.andAlso(FALSE,
+ Expressions.parameter(boolean.class,
+ "bool"))));
+ }
+
+ @Test
+ public void andAlsoNullBool() {
+ // null && bool
+ assertEquals("{\n return null && bool;\n}\n",
+ optimize(Expressions.andAlso(NULL,
+ Expressions.parameter(boolean.class,
+ "bool"))));
+ }
+
+ @Test
+ public void andAlsoXY() {
+ // x && y
+ assertEquals("{\n return x && y;\n}\n", optimize(Expressions.andAlso(
+ Expressions.parameter(
+ boolean.class, "x"),
+ Expressions.parameter(boolean.class,
+ "y"))));
+ }
+
+ @Test
+ public void andAlsoXX() {
+ // x && x
+ ParameterExpression x = Expressions.parameter(boolean.class, "x");
+ assertEquals("{\n return x;\n}\n", optimize(Expressions.andAlso(x, x)));
+ }
+
+ @Test
+ public void orElseTrueBool() {
+ // true || bool
+ assertEquals("{\n return true;\n}\n", optimize(Expressions.orElse(TRUE,
+ Expressions.parameter(boolean.class,
+ "bool"))));
+ }
+
+ @Test
+ public void orElseFalseBool() {
+ // false || bool
+ assertEquals("{\n return bool;\n}\n", optimize(Expressions.orElse(FALSE,
+ Expressions.parameter(boolean.class,
+ "bool"))));
+ }
+
+ @Test
+ public void orElseNullBool() {
+ // null || bool
+ assertEquals("{\n return null || bool;\n}\n",
+ optimize(Expressions.orElse(NULL,
+ Expressions.parameter(boolean.class,
+ "bool"))));
+ }
+
+ @Test
+ public void orElseXY() {
+ // x || y
+ assertEquals("{\n return x || y;\n}\n", optimize(Expressions.orElse(
+ Expressions.parameter(
+ boolean.class, "x"),
+ Expressions.parameter(boolean.class,
+ "y"))));
+ }
+
+ @Test
+ public void orElseXX() {
+ // x || x
+ ParameterExpression x = Expressions.parameter(boolean.class, "x");
+ assertEquals("{\n return x;\n}\n", optimize(Expressions.orElse(x, x)));
+ }
+
+ @Test
+ public void equalSameConst() {
+ // 1 == 1
+ assertEquals("{\n return true;\n}\n", optimize(Expressions.equal(ONE,
+ Expressions.constant(1))));
+ }
+
+ @Test
+ public void equalDifferentConst() {
+ // 1 == 2
+ assertEquals("{\n return false;\n}\n", optimize(Expressions.equal(ONE,
+ TWO)));
+ }
+
+ @Test
+ public void equalSameExpr() {
+ // x == x
+ ParameterExpression x = Expressions.parameter(int.class, "x");
+ assertEquals("{\n return true;\n}\n", optimize(Expressions.equal(x, x)));
+ }
+
+ @Test
+ public void equalDifferentExpr() {
+ // x == y
+ ParameterExpression x = Expressions.parameter(int.class, "x");
+ ParameterExpression y = Expressions.parameter(int.class, "y");
+ assertEquals("{\n return x == y;\n}\n", optimize(Expressions.equal(x, y)));
+ }
+
+ @Test
+ public void equalPrimitiveNull() {
+ // (int) x == null
+ ParameterExpression x = Expressions.parameter(int.class, "x");
+ assertEquals("{\n return false;\n}\n", optimize(Expressions.equal(x,
+ NULL)));
+ }
+
+ @Test
+ public void equalObjectNull() {
+ // (Integer) x == null
+ ParameterExpression x = Expressions.parameter(Integer.class, "x");
+ assertEquals("{\n return x == null;\n}\n",
+ optimize(Expressions.equal(x,
+ NULL)));
+ }
+
+ @Test
+ public void equalStringNull() {
+ // "Y" == null
+ assertEquals("{\n return false;\n}\n",
+ optimize(Expressions.equal(Expressions.constant("Y"), NULL)));
+ }
+
+ @Test
+ public void equalTypedNullUntypedNull() {
+ // (Integer) null == null
+ assertEquals("{\n return true;\n}\n",
+ optimize(Expressions.equal(NULL_INTEGER, NULL)));
+ }
+
+ @Test
+ public void equalUnypedNullTypedNull() {
+ // null == (Integer) null
+ assertEquals("{\n return true;\n}\n",
+ optimize(Expressions.equal(NULL, NULL_INTEGER)));
+ }
+
+ @Test
+ public void equalBoolTrue() {
+ // x == true
+ ParameterExpression x = Expressions.parameter(boolean.class, "x");
+ assertEquals("{\n return x;\n}\n", optimize(Expressions.equal(x, TRUE)));
+ }
+
+ @Test
+ public void equalBoolFalse() {
+ // x == false
+ ParameterExpression x = Expressions.parameter(boolean.class, "x");
+ assertEquals("{\n return !x;\n}\n", optimize(Expressions.equal(x, FALSE)));
+ }
+
+ @Test
+ public void notEqualSameConst() {
+ // 1 != 1
+ assertEquals("{\n return false;\n}\n", optimize(Expressions.notEqual(
+ ONE, Expressions.constant(1))));
+ }
+
+ @Test
+ public void notEqualDifferentConst() {
+ // 1 != 2
+ assertEquals("{\n return true;\n}\n", optimize(Expressions.notEqual(ONE,
+ TWO)));
+ }
+
+ @Test
+ public void notEqualSameExpr() {
+ // x != x
+ ParameterExpression x = Expressions.parameter(int.class, "x");
+ assertEquals("{\n return false;\n}\n", optimize(Expressions.notEqual(x,
+ x)));
+ }
+
+ @Test
+ public void notEqualDifferentExpr() {
+ // x != y
+ ParameterExpression x = Expressions.parameter(int.class, "x");
+ ParameterExpression y = Expressions.parameter(int.class, "y");
+ assertEquals("{\n return x != y;\n}\n", optimize(Expressions.notEqual(x,
+ y)));
+ }
+
+ @Test
+ public void notEqualPrimitiveNull() {
+ // (int) x == null
+ ParameterExpression x = Expressions.parameter(int.class, "x");
+ assertEquals("{\n return true;\n}\n", optimize(Expressions.notEqual(x,
+ NULL)));
+ }
+
+ @Test
+ public void notEqualObjectNull() {
+ // (Integer) x == null
+ ParameterExpression x = Expressions.parameter(Integer.class, "x");
+ assertEquals("{\n return x != null;\n}\n",
+ optimize(Expressions.notEqual(
+ x, NULL)));
+ }
+
+ @Test
+ public void notEqualStringNull() {
+ // "Y" != null
+ assertEquals("{\n return true;\n}\n",
+ optimize(Expressions.notEqual(Expressions.constant("Y"), NULL)));
+ }
+
+ @Test
+ public void notEqualTypedNullUntypedNull() {
+ // (Integer) null != null
+ assertEquals("{\n return false;\n}\n",
+ optimize(Expressions.notEqual(NULL_INTEGER, NULL)));
+ }
+
+ @Test
+ public void notEqualUnypedNullTypedNull() {
+ // null != (Integer) null
+ assertEquals("{\n return false;\n}\n",
+ optimize(Expressions.notEqual(NULL, NULL_INTEGER)));
+ }
+
+ @Test
+ public void notEqualBoolTrue() {
+ // x != true
+ ParameterExpression x = Expressions.parameter(boolean.class, "x");
+ assertEquals("{\n return !x;\n}\n", optimize(Expressions.notEqual(x,
+ TRUE)));
+ }
+
+ @Test
+ public void notEqualBoolFalse() {
+ // x != false
+ ParameterExpression x = Expressions.parameter(boolean.class, "x");
+ assertEquals("{\n return x;\n}\n", optimize(Expressions.notEqual(x,
+ FALSE)));
+ }
+
+ @Test
+ public void multipleFolding() {
+ // ( 1 == 2 ? 3 : 4 ) != (5 != 6 ? 4 : 8) ? 9 : 10
+ assertEquals("{\n return 10;\n}\n", optimize(Expressions.condition(
+ Expressions.notEqual(
+ Expressions.condition(Expressions.equal(ONE, TWO),
+ Expressions.constant(3),
+ Expressions.constant(4)), Expressions.condition(
+ Expressions.notEqual(
+ Expressions.constant(5), Expressions.constant(6)),
+ Expressions.constant(4), Expressions.constant(8))),
+ Expressions.constant(9),
+ Expressions.constant(10))));
+ }
+
+ @Test
+ public void conditionalIfTrue() {
+ // if (true) {return 1}
+ assertEquals("{\n return 1;\n}\n", optimize(Expressions.ifThen(TRUE,
+ Expressions.return_(null, ONE))));
+ }
+
+ @Test
+ public void conditionalIfTrueElse() {
+ // if (true) {return 1} else {return 2}
+ assertEquals("{\n return 1;\n}\n", optimize(Expressions.ifThenElse(TRUE,
+ Expressions.return_(null, ONE), Expressions.return_(null, TWO))));
+ }
+
+ @Test
+ public void conditionalIfFalse() {
+ // if (false) {return 1}
+ assertEquals("{}", optimize(Expressions.ifThen(FALSE,
+ Expressions.return_(null, ONE))));
+ }
+
+ @Test
+ public void conditionalIfFalseElse() {
+ // if (false) {return 1} else {return 2}
+ assertEquals("{\n return 2;\n}\n", optimize(Expressions.ifThenElse(FALSE,
+ Expressions.return_(null, ONE), Expressions.return_(null, TWO))));
+ }
+
+ @Test
+ public void conditionalIfBoolTrue() {
+ // if (bool) {return 1} else if (true) {return 2}
+ Expression bool = Expressions.parameter(boolean.class, "bool");
+ assertEquals("{\n"
+ + " if (bool) {\n"
+ + " return 1;\n"
+ + " } else {\n"
+ + " return 2;\n"
+ + " }\n"
+ + "}\n", optimize(Expressions.ifThenElse(bool,
+ Expressions.return_(null, ONE), TRUE, Expressions.return_(null,
+ TWO))));
+ }
+
+ @Test
+ public void conditionalIfBoolTrueElse() {
+ // if (bool) {return 1} else if (true) {return 2} else {return 3}
+ Expression bool = Expressions.parameter(boolean.class, "bool");
+ assertEquals("{\n"
+ + " if (bool) {\n"
+ + " return 1;\n"
+ + " } else {\n"
+ + " return 2;\n"
+ + " }\n"
+ + "}\n", optimize(Expressions.ifThenElse(bool,
+ Expressions.return_(null, ONE), TRUE, Expressions.return_(null,
+ TWO), Expressions.return_(null, THREE))));
+
+ }
+
+ @Test
+ public void conditionalIfBoolFalse() {
+ // if (bool) {return 1} else if (false) {return 2}
+ Expression bool = Expressions.parameter(boolean.class, "bool");
+ assertEquals("{\n"
+ + " if (bool) {\n"
+ + " return 1;\n"
+ + " }\n"
+ + "}\n", optimize(Expressions.ifThenElse(bool,
+ Expressions.return_(null, ONE), FALSE, Expressions.return_(null,
+ TWO))));
+ }
+
+ @Test
+ public void conditionalIfBoolFalseElse() {
+ // if (bool) {return 1} else if (false) {return 2} else {return 3}
+ Expression bool = Expressions.parameter(boolean.class, "bool");
+ assertEquals("{\n"
+ + " if (bool) {\n"
+ + " return 1;\n"
+ + " } else {\n"
+ + " return 3;\n"
+ + " }\n"
+ + "}\n", optimize(Expressions.ifThenElse(bool,
+ Expressions.return_(null, ONE), FALSE, Expressions.return_(null,
+ TWO), Expressions.return_(null, THREE))));
+ }
+
+ @Test
+ public void conditionalIfBoolFalseTrue() {
+ // if (bool) {1} else if (false) {2} if (true) {4} else {5}
+ Expression bool = Expressions.parameter(boolean.class, "bool");
+ assertEquals("{\n"
+ + " if (bool) {\n"
+ + " return 1;\n"
+ + " } else {\n"
+ + " return 4;\n"
+ + " }\n"
+ + "}\n", optimize(Expressions.ifThenElse(bool,
+ Expressions.return_(null, ONE), FALSE, Expressions.return_(null,
+ TWO), TRUE, Expressions.return_(null, FOUR),
+ Expressions.return_(null, Expressions.constant(5)))));
+ }
+
+ @Test
+ public void castIntToShort() {
+ // return (short) 1 --> return (short) 1
+ assertEquals("{\n return (short)1;\n}\n", optimize(Expressions.convert_(
+ ONE, short.class)));
+ }
+
+ @Test
+ public void castIntToInt() {
+ // return (int) 1 --> return 1L
+ assertEquals("{\n return 1;\n}\n", optimize(Expressions.convert_(ONE,
+ int.class)));
+ }
+
+ @Test
+ public void castIntToLong() {
+ // return (long) 1 --> return 1L
+ assertEquals("{\n return 1L;\n}\n", optimize(Expressions.convert_(ONE,
+ long.class)));
+ }
+}
