Additional tests and fixes for assignment inlining (JENA-780)
- Don't inline into EXISTS/NOT EXISTS since those are n-ary operators
- Permit inlining within an EXISTS/NOT EXISTS only if the assignments
are subject to all the normal restrictions
- Don't remove projection when inlining/eliminating through projections
since doing so could cause previously hidden variables to become
visible
- Various additional test cases for these
Conflicts:
jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
Project: http://git-wip-us.apache.org/repos/asf/jena/repo
Commit: http://git-wip-us.apache.org/repos/asf/jena/commit/a25c72c9
Tree: http://git-wip-us.apache.org/repos/asf/jena/tree/a25c72c9
Diff: http://git-wip-us.apache.org/repos/asf/jena/diff/a25c72c9
Branch: refs/heads/master
Commit: a25c72c94ecd433fbc4cca78d87f9a7c539841df
Parents: 2031b78
Author: Rob Vesse <rve...@apache.org>
Authored: Wed Jul 8 12:01:28 2015 +0100
Committer: Rob Vesse <rve...@apache.org>
Committed: Wed Jul 8 15:08:47 2015 +0100
----------------------------------------------------------------------
.../optimize/TransformEliminateAssignments.java | 83 ++++++++++++++++-
.../optimize/TransformRemoveAssignment.java | 7 +-
.../org/apache/jena/sparql/expr/ExprVars.java | 27 ++++++
.../TestTransformEliminateAssignments.java | 97 +++++++++++++++++++-
4 files changed, 202 insertions(+), 12 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/jena/blob/a25c72c9/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
----------------------------------------------------------------------
diff --git
a/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
b/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
index 77ba124..3ce4198 100644
---
a/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
+++
b/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
@@ -21,9 +21,11 @@ package org.apache.jena.sparql.algebra.optimize;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
+import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
+import java.util.Set;
import org.apache.jena.atlas.lib.CollectionUtils;
@@ -99,8 +101,9 @@ public class TransformEliminateAssignments extends
TransformCopy {
AssignmentPusher pusher = new AssignmentPusher(tracker);
AssignmentPopper popper = new AssignmentPopper(tracker);
Transform transform = new TransformEliminateAssignments(tracker,
pusher, popper, aggressive);
+ ExprTransform exprTransform = new
ExprTransformEliminateAssignments(aggressive);
- return Transformer.transformSkipService(transform, op, pusher, popper);
+ return Transformer.transformSkipService(transform, exprTransform, op,
pusher, popper);
}
private final OpVisitor before, after;
@@ -161,9 +164,9 @@ public class TransformEliminateAssignments extends
TransformCopy {
return super.transform(opFilter, subOp);
// See what vars are used in the filter
- Collection<Var> vars = new ArrayList<>();
+ Set<Var> vars = new HashSet<>();
for (Expr expr : opFilter.getExprs().getList()) {
- ExprVars.varsMentioned(vars, expr);
+ ExprVars.nonOpVarsMentioned(vars, expr);
}
// Are any of these vars single usage?
@@ -222,8 +225,8 @@ public class TransformEliminateAssignments extends
TransformCopy {
Expr currExpr = opExtend.getVarExprList().getExpr(assignVar);
// See what vars are used in the current expression
- Collection<Var> vars = new ArrayList<>();
- ExprVars.varsMentioned(vars, currExpr);
+ Set<Var> vars = new HashSet<Var>();
+ ExprVars.nonOpVarsMentioned(vars, currExpr);
// See if we can inline anything
for (Var var : vars) {
@@ -532,5 +535,75 @@ public class TransformEliminateAssignments extends
TransformCopy {
this.tracker.decrementDepth();
}
+<<<<<<<
HEAD:jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
+=======
+ @Override
+ public void visit(OpUnion opUnion) {
+ unsafe();
+ }
+
+ @Override
+ public void visit(OpLeftJoin opLeftJoin) {
+ // TODO Technically if the assignment is single use and comes from
+ // the LHS we could keep it but for now we don't try and do this
+ unsafe();
+ }
+
+ @Override
+ public void visit(OpMinus opMinus) {
+ // Anything from the RHS doesn't project out anyway
+ unsafe();
+ }
+
+ @Override
+ public void visit(OpJoin opJoin) {
+ unsafe();
+ }
+
+ private void unsafe() {
+ // Throw out any assignments because if they would be eligible
their
+ // values can't be bound in every branch of the union and thus
+ // inlining could change the semantics
+ tracker.getAssignments().clear();
+ }
+>>>>>>> 67bb248... Additional tests and fixes for assignment inlining
(JENA-780):jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
+ }
+
+ /**
+ * Handles expression transforms for eliminating assignments
+ */
+ private static class ExprTransformEliminateAssignments extends
ExprTransformCopy {
+
+ private final boolean aggressive;
+
+ /**
+ * @param aggressive
+ * Whether to inline aggressively
+ */
+ public ExprTransformEliminateAssignments(boolean aggressive) {
+ this.aggressive = aggressive;
+ }
+
+ @Override
+ public Expr transform(ExprFunctionOp funcOp, ExprList args, Op opArg) {
+ // Need to use fresh visitors when working inside an exists/not
+ // exists as we should only do self-contained inlining
+
+ AssignmentTracker tracker = new AssignmentTracker();
+ AssignmentPusher pusher = new AssignmentPusher(tracker);
+ AssignmentPopper popper = new AssignmentPopper(tracker);
+ Transform transform = new TransformEliminateAssignments(tracker,
pusher, popper, aggressive);
+ ExprTransformEliminateAssignments exprTransform = new
ExprTransformEliminateAssignments(aggressive);
+
+ Op opArg2 = Transformer.transform(transform, exprTransform, opArg,
pusher, popper);
+ if (opArg2 == opArg)
+ return super.transform(funcOp, args, opArg);
+ if (funcOp instanceof E_Exists)
+ return new E_Exists(opArg2);
+ if (funcOp instanceof E_NotExists)
+ return new E_NotExists(opArg2);
+ throw new ARQInternalErrorException("Unrecognized ExprFunctionOp:
\n" + funcOp);
+ }
+
}
}
http://git-wip-us.apache.org/repos/asf/jena/blob/a25c72c9/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
----------------------------------------------------------------------
diff --git
a/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
b/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
index 833de93..fd71ffb 100644
---
a/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
+++
b/jena-arq/src/main/java/org/apache/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
@@ -119,11 +119,6 @@ public class TransformRemoveAssignment extends
TransformCopy {
List<Var> newVars = opProject.getVars();
newVars.remove(this.var);
- if (newVars.size() > 0) {
- return new OpProject(subOp, newVars);
- } else {
- return subOp;
- }
+ return new OpProject(subOp, newVars);
}
-
}
http://git-wip-us.apache.org/repos/asf/jena/blob/a25c72c9/jena-arq/src/main/java/org/apache/jena/sparql/expr/ExprVars.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/org/apache/jena/sparql/expr/ExprVars.java
b/jena-arq/src/main/java/org/apache/jena/sparql/expr/ExprVars.java
index 4ca888a..64541e4 100644
--- a/jena-arq/src/main/java/org/apache/jena/sparql/expr/ExprVars.java
+++ b/jena-arq/src/main/java/org/apache/jena/sparql/expr/ExprVars.java
@@ -59,6 +59,20 @@ public class ExprVars
ExprWalker.walk(vv, expr) ;
}
+ public static void nonOpVarsMentioned(Collection<Var> acc, Expr expr)
+ {
+ ExprVars.Action<Var> action =
+ new ExprVars.Action<Var>(){
+ @Override
+ public void var(Collection<Var> acc, Var var)
+ {
+ acc.add(var) ;
+ }
+ } ;
+ ExprNoOpVarsWorker<Var> vv = new ExprNoOpVarsWorker<>(acc, action) ;
+ ExprWalker.walk(vv, expr) ;
+ }
+
public static Set<String> getVarNamesMentioned(Expr expr)
{
Set<String> acc = new HashSet<>() ;
@@ -124,4 +138,17 @@ public class ExprVars
}
}
+
+ static class ExprNoOpVarsWorker<T> extends ExprVarsWorker<T>
+ {
+ public ExprNoOpVarsWorker(Collection<T> acc, Action<T> action) {
+ super(acc, action);
+ // TODO Auto-generated constructor stub
+ }
+
+ public void visit(ExprFunctionOp funcOp) {
+ // Don't include op vars
+ return;
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/jena/blob/a25c72c9/jena-arq/src/test/java/org/apache/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
----------------------------------------------------------------------
diff --git
a/jena-arq/src/test/java/org/apache/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
b/jena-arq/src/test/java/org/apache/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
index 13e9c7e..56029e5 100644
---
a/jena-arq/src/test/java/org/apache/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
+++
b/jena-arq/src/test/java/org/apache/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
@@ -382,6 +382,100 @@ public class TestTransformEliminateAssignments {
}
@Test
+ public void ineligible_09() {
+ // We can't inline if the assignment will be projected out
+ //@formatter:off
+ testNoChange("(project (?x ?y)",
+ " (filter (exprlist ?x)",
+ " (extend (?x true)",
+ " (bgp (triple ?y <urn:pred> <urn:obj>)))))");;
+ //@formatter:on
+ }
+
+ @Test
+ public void ineligible_10() {
+ // We can't inline out of an EXISTS since the assignment isn't
projected
+ // out anyway
+ //@formatter:off
+ testNoChange("(project (?y)",
+ " (filter (exprlist ?x (exists",
+ " (extend (?x true)",
+ " (table unit))))",
+ " (table unit)))");
+ //@formatter:on
+ }
+
+ @Test
+ public void ineligible_11() {
+ // We can't inline out of an EXISTS since the assignment isn't
projected
+ // out anyway
+ //@formatter:off
+ testNoChange("(project (?y)",
+ " (filter (exprlist ?x)",
+ " (filter (exprlist (exists",
+ " (extend (?x true)",
+ " (table unit))))",
+ " (table unit))))");
+ //@formatter:on
+ }
+
+ @Test
+ public void exists_01() {
+ // We can't inline into an EXISTS since the assignment isn't projected
+ // out anyway and its an n-ary operator so would change semantics
+ // However this makes the assignment unused so can still remove it
+ //@formatter:off
+ test(StrUtils.strjoinNL("(project (?y)",
+ " (filter (exprlist (exists",
+ " (filter (exprlist ?x)",
+ " (table unit))))",
+ " (extend (?x true)",
+ " (table unit))))"),
+ "(project (?y)",
+ " (filter (exprlist (exists",
+ " (filter (exprlist ?x)",
+ " (table unit))))",
+ " (table unit)))");
+ //@formatter:on
+ }
+
+ @Test
+ public void exists_02() {
+ // Could inline within an exists but still needs to meet other rules
+ // Even though an exists is technically a form of projection can't
+ // discount the variable being needed elsewhere
+ //@formatter:off
+ testNoChange("(project (?y)",
+ " (filter (exprlist (exists",
+ " (filter (exprlist ?x)",
+ " (extend (?x true)",
+ " (table unit)))))",
+ " (table unit)))");
+ //@formatter:on
+ }
+
+ @Test
+ public void exists_03() {
+ // Can inline within an exists provided it meets normal conditions of
+ // being inside a projection
+ //@formatter:off
+ test(StrUtils.strjoinNL("(project (?y)",
+ " (filter (exprlist (exists",
+ " (project (?y)",
+ " (filter (exprlist ?x)",
+ " (extend (?x true)",
+ " (table unit))))))",
+ " (table unit)))"),
+ "(project (?y)",
+ " (filter (exprlist (exists",
+ " (project (?y)",
+ " (filter (exprlist true)",
+ " (table unit)))))",
+ " (table unit)))");
+ //@formatter:on
+ }
+
+ @Test
public void through_project_01() {
// We can inline out through a project by also eliminating the
variable
// from the project
@@ -393,7 +487,8 @@ public class TestTransformEliminateAssignments {
" (table unit)))))"),
"(project (?y)",
" (filter true",
- " (table unit)))");
+ " (project ()",
+ " (table unit))))");
//@formatter:on
}