You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@jena.apache.org by rv...@apache.org on 2015/07/08 16:12:01 UTC
[3/7] jena git commit: Additional tests and fixes for assignment
inlining (JENA-780)
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
Project: http://git-wip-us.apache.org/repos/asf/jena/repo
Commit: http://git-wip-us.apache.org/repos/asf/jena/commit/67bb2482
Tree: http://git-wip-us.apache.org/repos/asf/jena/tree/67bb2482
Diff: http://git-wip-us.apache.org/repos/asf/jena/diff/67bb2482
Branch: refs/heads/jena2
Commit: 67bb2482edd163127318e5280f3a84142a83cc8b
Parents: a188648
Author: Rob Vesse <rv...@apache.org>
Authored: Wed Jul 8 12:01:28 2015 +0100
Committer: Rob Vesse <rv...@apache.org>
Committed: Wed Jul 8 12:01:28 2015 +0100
----------------------------------------------------------------------
.../optimize/TransformEliminateAssignments.java | 61 ++++++++++--
.../optimize/TransformRemoveAssignment.java | 7 +-
.../com/hp/hpl/jena/sparql/expr/ExprVars.java | 27 ++++++
.../TestTransformEliminateAssignments.java | 97 +++++++++++++++++++-
4 files changed, 178 insertions(+), 14 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/jena/blob/67bb2482/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
index 7044cc9..d36f036 100644
--- a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
@@ -21,13 +21,16 @@ package com.hp.hpl.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;
import com.hp.hpl.jena.query.SortCondition;
+import com.hp.hpl.jena.sparql.ARQInternalErrorException;
import com.hp.hpl.jena.sparql.algebra.Op;
import com.hp.hpl.jena.sparql.algebra.OpVisitor;
import com.hp.hpl.jena.sparql.algebra.OpVisitorBase;
@@ -47,11 +50,15 @@ import com.hp.hpl.jena.sparql.algebra.op.OpTopN;
import com.hp.hpl.jena.sparql.algebra.op.OpUnion;
import com.hp.hpl.jena.sparql.core.Var;
import com.hp.hpl.jena.sparql.core.VarExprList;
+import com.hp.hpl.jena.sparql.expr.E_Exists;
+import com.hp.hpl.jena.sparql.expr.E_NotExists;
import com.hp.hpl.jena.sparql.expr.Expr;
import com.hp.hpl.jena.sparql.expr.ExprAggregator;
+import com.hp.hpl.jena.sparql.expr.ExprFunctionOp;
import com.hp.hpl.jena.sparql.expr.ExprLib;
import com.hp.hpl.jena.sparql.expr.ExprList;
import com.hp.hpl.jena.sparql.expr.ExprTransform;
+import com.hp.hpl.jena.sparql.expr.ExprTransformCopy;
import com.hp.hpl.jena.sparql.expr.ExprTransformSubstitute;
import com.hp.hpl.jena.sparql.expr.ExprTransformer;
import com.hp.hpl.jena.sparql.expr.ExprVars;
@@ -103,8 +110,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;
@@ -165,9 +173,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?
@@ -226,8 +234,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) {
@@ -547,12 +555,13 @@ public class TransformEliminateAssignments extends TransformCopy {
// 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();
@@ -565,4 +574,42 @@ public class TransformEliminateAssignments extends TransformCopy {
tracker.getAssignments().clear();
}
}
+
+ /**
+ * 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/67bb2482/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
index 855ec10..da56116 100644
--- a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
@@ -122,11 +122,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/67bb2482/jena-arq/src/main/java/com/hp/hpl/jena/sparql/expr/ExprVars.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/expr/ExprVars.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/expr/ExprVars.java
index 03da875..7afe2d2 100644
--- a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/expr/ExprVars.java
+++ b/jena-arq/src/main/java/com/hp/hpl/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/67bb2482/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java b/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
index ed96785..52c6cf3 100644
--- a/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
+++ b/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
@@ -440,6 +440,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
@@ -451,7 +545,8 @@ public class TestTransformEliminateAssignments {
" (table unit)))))"),
"(project (?y)",
" (filter true",
- " (table unit)))");
+ " (project ()",
+ " (table unit))))");
//@formatter:on
}