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 2014/09/25 16:36:48 UTC
git commit: Initial work on elminating assignments (JENA-780)
Repository: jena
Updated Branches:
refs/heads/eliminate-assignments [created] 308810f27
Initial work on elminating assignments (JENA-780)
This is an initial first pass at a new optimization which aims to
eliminate single use assignments where possible. Currently this is not
entirely working and will break some queries (those not involving an
explicit projection)
Project: http://git-wip-us.apache.org/repos/asf/jena/repo
Commit: http://git-wip-us.apache.org/repos/asf/jena/commit/308810f2
Tree: http://git-wip-us.apache.org/repos/asf/jena/tree/308810f2
Diff: http://git-wip-us.apache.org/repos/asf/jena/diff/308810f2
Branch: refs/heads/eliminate-assignments
Commit: 308810f273203591143ebd9c00d39077d309fa7d
Parents: 913b225
Author: Rob Vesse <rv...@apache.org>
Authored: Thu Sep 25 15:34:37 2014 +0100
Committer: Rob Vesse <rv...@apache.org>
Committed: Thu Sep 25 15:35:31 2014 +0100
----------------------------------------------------------------------
.../optimize/TransformEliminateAssignments.java | 219 +++++++++++++++++++
.../optimize/TransformRemoveAssignment.java | 98 +++++++++
.../algebra/optimize/VariableUsagePopper.java | 39 ++++
.../algebra/optimize/VariableUsagePusher.java | 41 ++++
.../algebra/optimize/VariableUsageTracker.java | 74 +++++++
.../algebra/optimize/VariableUsageVisitor.java | 186 ++++++++++++++++
.../algebra/optimize/TS_Optimization.java | 1 +
.../TestTransformEliminateAssignments.java | 171 +++++++++++++++
8 files changed, 829 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/jena/blob/308810f2/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
new file mode 100644
index 0000000..49f8f1c
--- /dev/null
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformEliminateAssignments.java
@@ -0,0 +1,219 @@
+package com.hp.hpl.jena.sparql.algebra.optimize;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Iterator;
+import java.util.Map;
+
+import org.apache.jena.atlas.lib.CollectionUtils;
+import com.hp.hpl.jena.sparql.algebra.Op;
+import com.hp.hpl.jena.sparql.algebra.OpVisitor;
+import com.hp.hpl.jena.sparql.algebra.OpVisitorBase;
+import com.hp.hpl.jena.sparql.algebra.Transform;
+import com.hp.hpl.jena.sparql.algebra.TransformCopy;
+import com.hp.hpl.jena.sparql.algebra.Transformer;
+import com.hp.hpl.jena.sparql.algebra.op.OpAssign;
+import com.hp.hpl.jena.sparql.algebra.op.OpExt;
+import com.hp.hpl.jena.sparql.algebra.op.OpExtend;
+import com.hp.hpl.jena.sparql.algebra.op.OpFilter;
+import com.hp.hpl.jena.sparql.algebra.op.OpGroup;
+import com.hp.hpl.jena.sparql.algebra.op.OpOrder;
+import com.hp.hpl.jena.sparql.algebra.op.OpProject;
+import com.hp.hpl.jena.sparql.algebra.op.OpTopN;
+import com.hp.hpl.jena.sparql.core.Var;
+import com.hp.hpl.jena.sparql.core.VarExprList;
+import com.hp.hpl.jena.sparql.expr.Expr;
+import com.hp.hpl.jena.sparql.expr.ExprList;
+import com.hp.hpl.jena.sparql.expr.ExprTransformSubstitute;
+import com.hp.hpl.jena.sparql.expr.ExprTransformer;
+import com.hp.hpl.jena.sparql.expr.ExprVars;
+
+/**
+ * A transform that tries to remove unecessary assignments
+ * <p>
+ * There are two classes of assignments that we can try and remove:
+ * </p>
+ * <ol>
+ * <li>Assignments where the assigned variable is used only once in a subsequent
+ * assignment</li>
+ * <li>Assignments where the assigned value is never used elsewhere</li>
+ * </ol>
+ *
+ * @author rvesse
+ *
+ */
+public class TransformEliminateAssignments extends TransformCopy {
+
+ public static Op eliminate(Op op) {
+ AssignmentTracker tracker = new AssignmentTracker();
+ VariableUsagePusher pusher = new VariableUsagePusher(tracker);
+ AssignmentPopper popper = new AssignmentPopper(tracker);
+ Transform transform = new TransformEliminateAssignments(tracker, pusher, popper);
+
+ return Transformer.transform(transform, op, pusher, popper);
+ }
+
+ private OpVisitor before, after;
+ private AssignmentTracker tracker;
+
+ private TransformEliminateAssignments(AssignmentTracker tracker, OpVisitor before, OpVisitor after) {
+ this.tracker = tracker;
+ this.before = before;
+ }
+
+ @Override
+ public Op transform(OpExt opExt) {
+ return opExt.apply(this, this.before, this.after);
+ }
+
+ @Override
+ public Op transform(OpFilter opFilter, Op subOp) {
+ // See what vars are used in the filter
+ Collection<Var> vars = new ArrayList<>();
+ for (Expr expr : opFilter.getExprs().getList()) {
+ ExprVars.varsMentioned(vars, expr);
+ }
+
+ // Are any of these vars single usage?
+ ExprList exprs = opFilter.getExprs();
+ boolean modified = false;
+ for (Var var : vars) {
+ // Usage count will be 2 if we can eliminate the assignment
+ // First usage is when it is introduced by the assignment and the
+ // second is when it is used now in this filter
+ if (this.tracker.getUsageCount(var) == 2 && this.tracker.getAssignments().containsKey(var)) {
+ // Can go back and eliminate that assignment
+ subOp = Transformer.transform(
+ new TransformRemoveAssignment(var, this.tracker.getAssignments().get(var)), subOp);
+ // Replace the variable usage with the expression
+ exprs = ExprTransformer.transform(
+ new ExprTransformSubstitute(var, this.tracker.getAssignments().get(var)), exprs);
+ this.tracker.getAssignments().remove(var);
+ modified = true;
+ }
+ }
+
+ // Create a new filter if we've substituted any expressions
+ if (modified) {
+ return OpFilter.filter(exprs, subOp);
+ }
+
+ return super.transform(opFilter, subOp);
+ }
+
+ @Override
+ public Op transform(OpAssign opAssign, Op subOp) {
+ this.tracker.putAssignments(opAssign.getVarExprList());
+ // Note that for assign we don't eliminate instances where its value is
+ // never used because assign has different semantics to extend that
+ // means in such a case it acts more like a filter
+ return super.transform(opAssign, subOp);
+ }
+
+ @Override
+ public Op transform(OpExtend opExtend, Op subOp) {
+ this.tracker.putAssignments(opExtend.getVarExprList());
+
+ // See if there are any assignments we can eliminate entirely i.e. those
+ // where the assigned value is never used
+ VarExprList assignments = processUnused(opExtend.getVarExprList());
+ if (assignments == null)
+ return super.transform(opExtend, subOp);
+
+ // Can eliminate some assignments entirely
+ if (assignments.size() > 0) {
+ return OpExtend.extend(subOp, assignments);
+ } else {
+ return subOp;
+ }
+ }
+
+ private VarExprList processUnused(VarExprList assignments) {
+ if (CollectionUtils.disjoint(assignments.getVars(), this.tracker.getAssignments().keySet()))
+ return null;
+
+ VarExprList modified = new VarExprList();
+ for (Var var : assignments.getVars()) {
+ if (this.tracker.getUsageCount(var) > 1)
+ modified.add(var, assignments.getExpr(var));
+ }
+
+ if (modified.size() == assignments.size())
+ return null;
+ return modified;
+ }
+
+ @Override
+ public Op transform(OpOrder opOrder, Op subOp) {
+ // TODO Auto-generated method stub
+ return super.transform(opOrder, subOp);
+ }
+
+ @Override
+ public Op transform(OpTopN opTop, Op subOp) {
+ // TODO Auto-generated method stub
+ return super.transform(opTop, subOp);
+ }
+
+ @Override
+ public Op transform(OpGroup opGroup, Op subOp) {
+ // TODO Auto-generated method stub
+ return super.transform(opGroup, subOp);
+ }
+
+ private static class AssignmentTracker extends VariableUsageTracker {
+
+ private Map<Var, Expr> assignments = new HashMap<>();
+
+ public Map<Var, Expr> getAssignments() {
+ return this.assignments;
+ }
+
+ public void putAssignments(VarExprList assignments) {
+ for (Var var : assignments.getVars()) {
+ int i = getUsageCount(var);
+ if (i <= 2) {
+ this.assignments.put(var, assignments.getExpr(var));
+ } else {
+ this.assignments.remove(var);
+ }
+ }
+ }
+
+ @Override
+ public void increment(String var) {
+ super.increment(var);
+
+ int i = getUsageCount(var);
+ if (i > 2) {
+ this.assignments.remove(var);
+ }
+ }
+
+ }
+
+ private static class AssignmentPopper extends OpVisitorBase {
+
+ private AssignmentTracker tracker;
+
+ public AssignmentPopper(AssignmentTracker tracker) {
+ this.tracker = tracker;
+ }
+
+ @Override
+ public void visit(OpProject opProject) {
+ // Any assignments that are not projected should be discarded at
+ // this
+ // point
+ Iterator<Var> vars = tracker.getAssignments().keySet().iterator();
+ while (vars.hasNext()) {
+ Var var = vars.next();
+ if (!opProject.getVars().contains(var))
+ vars.remove();
+ }
+ tracker.pop();
+ }
+
+ }
+}
http://git-wip-us.apache.org/repos/asf/jena/blob/308810f2/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
new file mode 100644
index 0000000..dba9271
--- /dev/null
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/TransformRemoveAssignment.java
@@ -0,0 +1,98 @@
+package com.hp.hpl.jena.sparql.algebra.optimize;
+
+import com.hp.hpl.jena.sparql.algebra.Op;
+import com.hp.hpl.jena.sparql.algebra.TransformCopy;
+import com.hp.hpl.jena.sparql.algebra.op.OpAssign;
+import com.hp.hpl.jena.sparql.algebra.op.OpExtend;
+import com.hp.hpl.jena.sparql.algebra.op.OpExtendAssign;
+import com.hp.hpl.jena.sparql.core.Var;
+import com.hp.hpl.jena.sparql.core.VarExprList;
+import com.hp.hpl.jena.sparql.expr.Expr;
+
+/**
+ * A transform capable of removing assignments from the algebra tree
+ *
+ */
+public class TransformRemoveAssignment extends TransformCopy {
+
+ private Var var;
+ private Expr expr;
+ private boolean topmostOnly = true;
+
+ public TransformRemoveAssignment(Var var, Expr expr, boolean topmostOnly) {
+ this.var = var;
+ this.expr = expr;
+ this.topmostOnly = topmostOnly;
+ }
+
+ public TransformRemoveAssignment(Var var, Expr expr) {
+ this(var, expr, true);
+ }
+
+ @Override
+ public Op transform(OpAssign opAssign, Op subOp) {
+ VarExprList assignments = processAssignments(opAssign);
+ if (assignments == null)
+ return super.transform(opAssign, subOp);
+
+ // Rewrite appropriately
+ if (this.topmostOnly) {
+ // If topmost only ignore any transformations lower down the tree
+ // hence call getSubOp() rather than using the provided subOp
+ if (assignments.size() > 0) {
+ return OpAssign.assign(opAssign.getSubOp(), assignments);
+ } else {
+ return opAssign.getSubOp();
+ }
+ } else {
+ // Otherwise preserve any transformations from lower down the tree
+ if (assignments.size() > 0) {
+ return OpAssign.assign(subOp, assignments);
+ } else {
+ return subOp;
+ }
+ }
+ }
+
+ private VarExprList processAssignments(OpExtendAssign opAssign) {
+ VarExprList orig = opAssign.getVarExprList();
+ if (!orig.contains(this.var))
+ return null;
+ if (!orig.getExpr(this.var).equals(this.expr))
+ return null;
+
+ VarExprList modified = new VarExprList();
+ for (Var v : orig.getVars()) {
+ if (!v.equals(this.var)) {
+ modified.add(v, orig.getExpr(v));
+ }
+ }
+ return modified;
+ }
+
+ @Override
+ public Op transform(OpExtend opExtend, Op subOp) {
+ VarExprList assignments = processAssignments(opExtend);
+ if (assignments == null)
+ return super.transform(opExtend, subOp);
+
+ // Rewrite appropriately
+ if (this.topmostOnly) {
+ // If topmost only ignore any transformations lower down the tree
+ // hence call getSubOp() rather than using the provided subOp
+ if (assignments.size() > 0) {
+ return OpExtend.extend(opExtend.getSubOp(), assignments);
+ } else {
+ return opExtend.getSubOp();
+ }
+ } else {
+ // Otherwise preserve any transformations from lower down the tree
+ if (assignments.size() > 0) {
+ return OpExtend.extend(subOp, assignments);
+ } else {
+ return subOp;
+ }
+ }
+ }
+
+}
http://git-wip-us.apache.org/repos/asf/jena/blob/308810f2/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePopper.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePopper.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePopper.java
new file mode 100644
index 0000000..e73bfee
--- /dev/null
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePopper.java
@@ -0,0 +1,39 @@
+package com.hp.hpl.jena.sparql.algebra.optimize;
+
+import java.util.Collection;
+
+import com.hp.hpl.jena.sparql.algebra.op.OpProject;
+import com.hp.hpl.jena.sparql.core.Var;
+
+/**
+ * An after visitor for tracking variable usage
+ *
+ */
+public class VariableUsagePopper extends VariableUsageVisitor {
+
+ public VariableUsagePopper(VariableUsageTracker tracker) {
+ super(tracker);
+ }
+
+ @Override
+ protected void action(Collection<Var> vars) {
+ this.tracker.decrement(vars);
+ }
+
+ @Override
+ protected void action(Var var) {
+ this.tracker.decrement(var);
+ }
+
+ @Override
+ protected void action(String var) {
+ this.tracker.decrement(var);
+ }
+
+ @Override
+ public void visit(OpProject opProject) {
+ super.visit(opProject);
+ this.tracker.pop();
+ super.visit(opProject);
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/jena/blob/308810f2/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePusher.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePusher.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePusher.java
new file mode 100644
index 0000000..51a04fb
--- /dev/null
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsagePusher.java
@@ -0,0 +1,41 @@
+package com.hp.hpl.jena.sparql.algebra.optimize;
+
+import java.util.Collection;
+
+import com.hp.hpl.jena.sparql.algebra.op.OpProject;
+import com.hp.hpl.jena.sparql.core.Var;
+
+/**
+ * A before visitor for tracking variable usage
+ *
+ */
+public class VariableUsagePusher extends VariableUsageVisitor {
+
+ public VariableUsagePusher(VariableUsageTracker tracker) {
+ super(tracker);
+ }
+
+ @Override
+ protected void action(Collection<Var> vars) {
+ this.tracker.increment(vars);
+ }
+
+ @Override
+ protected void action(Var var) {
+ this.tracker.increment(var);
+ }
+
+ @Override
+ protected void action(String var) {
+ this.tracker.increment(var);
+ }
+
+ @Override
+ public void visit(OpProject opProject) {
+ super.visit(opProject);
+ this.tracker.push();
+ super.visit(opProject);
+ }
+
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/jena/blob/308810f2/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsageTracker.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsageTracker.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsageTracker.java
new file mode 100644
index 0000000..f63e41e
--- /dev/null
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsageTracker.java
@@ -0,0 +1,74 @@
+package com.hp.hpl.jena.sparql.algebra.optimize;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.Stack;
+
+import com.hp.hpl.jena.sparql.core.Var;
+
+/**
+ * Tracker for variable usage
+ *
+ */
+public class VariableUsageTracker {
+
+ private Stack<Map<String, Integer>> stack = new Stack<>();
+ private Map<String, Integer> variables = new HashMap<>();
+
+ public void push() {
+ this.stack.push(this.variables);
+ this.variables = new HashMap<>();
+ }
+
+ public void pop() {
+ if (this.stack.size() == 0)
+ throw new IllegalStateException("Stack is empty");
+ this.variables = this.stack.pop();
+ }
+
+ public void increment(Collection<Var> vars) {
+ for (Var var : vars) {
+ increment(var);
+ }
+ }
+
+ public void increment(String var) {
+ if (!variables.containsKey(var)) {
+ variables.put(var, 1);
+ } else {
+ variables.put(var, variables.get(var) + 1);
+ }
+ }
+
+ public void increment(Var var) {
+ increment(var.getName());
+ }
+
+ public void decrement(Collection<Var> vars) {
+ for (Var var : vars) {
+ decrement(var);
+ }
+ }
+
+ public void decrement(String var) {
+ if (variables.containsKey(var)) {
+ variables.put(var, variables.get(var) - 1);
+ if (variables.get(var) <= 0)
+ variables.remove(var);
+ }
+ }
+
+ public void decrement(Var var) {
+ decrement(var.getName());
+ }
+
+ public int getUsageCount(String var) {
+ Integer i = variables.get(var);
+ return i != null ? i.intValue() : 0;
+ }
+
+ public int getUsageCount(Var var) {
+ return getUsageCount(var.getName());
+ }
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/jena/blob/308810f2/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsageVisitor.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsageVisitor.java b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsageVisitor.java
new file mode 100644
index 0000000..9fda1c4
--- /dev/null
+++ b/jena-arq/src/main/java/com/hp/hpl/jena/sparql/algebra/optimize/VariableUsageVisitor.java
@@ -0,0 +1,186 @@
+package com.hp.hpl.jena.sparql.algebra.optimize;
+
+import java.util.ArrayList;
+import java.util.Collection;
+
+import com.hp.hpl.jena.graph.Node;
+import com.hp.hpl.jena.graph.Triple;
+import com.hp.hpl.jena.query.SortCondition;
+import com.hp.hpl.jena.sparql.algebra.OpVisitorBase;
+import com.hp.hpl.jena.sparql.algebra.op.OpAssign;
+import com.hp.hpl.jena.sparql.algebra.op.OpBGP;
+import com.hp.hpl.jena.sparql.algebra.op.OpDatasetNames;
+import com.hp.hpl.jena.sparql.algebra.op.OpExtend;
+import com.hp.hpl.jena.sparql.algebra.op.OpFilter;
+import com.hp.hpl.jena.sparql.algebra.op.OpGraph;
+import com.hp.hpl.jena.sparql.algebra.op.OpGroup;
+import com.hp.hpl.jena.sparql.algebra.op.OpLeftJoin;
+import com.hp.hpl.jena.sparql.algebra.op.OpOrder;
+import com.hp.hpl.jena.sparql.algebra.op.OpPath;
+import com.hp.hpl.jena.sparql.algebra.op.OpProject;
+import com.hp.hpl.jena.sparql.algebra.op.OpPropFunc;
+import com.hp.hpl.jena.sparql.algebra.op.OpQuadBlock;
+import com.hp.hpl.jena.sparql.algebra.op.OpQuadPattern;
+import com.hp.hpl.jena.sparql.algebra.op.OpTable;
+import com.hp.hpl.jena.sparql.algebra.op.OpTopN;
+import com.hp.hpl.jena.sparql.core.Quad;
+import com.hp.hpl.jena.sparql.core.Var;
+import com.hp.hpl.jena.sparql.core.Vars;
+import com.hp.hpl.jena.sparql.expr.Expr;
+import com.hp.hpl.jena.sparql.expr.ExprVars;
+
+/**
+ * A visitor which tracks variable usage
+ *
+ */
+public abstract class VariableUsageVisitor extends OpVisitorBase {
+
+ protected VariableUsageTracker tracker;
+
+ public VariableUsageVisitor(VariableUsageTracker tracker) {
+ this.tracker = tracker;
+ }
+
+ protected abstract void action(Collection<Var> vars);
+
+ protected abstract void action(Var var);
+
+ protected abstract void action(String var);
+
+ @Override
+ public void visit(OpBGP opBGP) {
+ Collection<Var> vars = new ArrayList<>();
+ for (Triple t : opBGP.getPattern().getList()) {
+ Vars.addVarsFromTriple(vars, t);
+ }
+ action(vars);
+ }
+
+ @Override
+ public void visit(OpQuadPattern quadPattern) {
+ Collection<Var> vars = new ArrayList<>();
+ for (Quad q : quadPattern.getPattern().getList()) {
+ Vars.addVarsFromQuad(vars, q);
+ }
+ action(vars);
+ }
+
+ @Override
+ public void visit(OpQuadBlock quadBlock) {
+ Collection<Var> vars = new ArrayList<>();
+ for (Quad q : quadBlock.getPattern().getList()) {
+ Vars.addVarsFromQuad(vars, q);
+ }
+ action(vars);
+ }
+
+ @Override
+ public void visit(OpPath opPath) {
+ if (opPath.getTriplePath().getSubject().isVariable())
+ action(opPath.getTriplePath().getSubject().getName());
+ if (opPath.getTriplePath().getObject().isVariable())
+ action(opPath.getTriplePath().getObject().getName());
+ }
+
+ @Override
+ public void visit(OpPropFunc opPropFunc) {
+ for (Node subjArg : opPropFunc.getSubjectArgs().getArgList()) {
+ if (subjArg.isVariable())
+ action(subjArg.getName());
+ }
+ for (Node objArg : opPropFunc.getObjectArgs().getArgList()) {
+ if (objArg.isVariable())
+ action(objArg.getName());
+ }
+ }
+
+ @Override
+ public void visit(OpLeftJoin opLeftJoin) {
+ Collection<Var> vars = new ArrayList<>();
+ for (Expr expr : opLeftJoin.getExprs().getList()) {
+ ExprVars.varsMentioned(vars, expr);
+ }
+ action(vars);
+ }
+
+ @Override
+ public void visit(OpFilter opFilter) {
+ Collection<Var> vars = new ArrayList<>();
+ for (Expr expr : opFilter.getExprs().getList()) {
+ ExprVars.varsMentioned(vars, expr);
+ }
+ action(vars);
+ }
+
+ @Override
+ public void visit(OpGraph opGraph) {
+ if (opGraph.getNode().isVariable())
+ action(opGraph.getNode().getName());
+ }
+
+ @Override
+ public void visit(OpDatasetNames dsNames) {
+ if (dsNames.getGraphNode().isVariable())
+ action(dsNames.getGraphNode().getName());
+ }
+
+ @Override
+ public void visit(OpTable opTable) {
+ action(opTable.getTable().getVars());
+ }
+
+ @Override
+ public void visit(OpAssign opAssign) {
+ Collection<Var> vars = new ArrayList<>();
+ for (Var var : opAssign.getVarExprList().getVars()) {
+ vars.add(var);
+ ExprVars.varsMentioned(vars, opAssign.getVarExprList().getExpr(var));
+ }
+ action(vars);
+ }
+
+ @Override
+ public void visit(OpExtend opExtend) {
+ Collection<Var> vars = new ArrayList<>();
+ for (Var var : opExtend.getVarExprList().getVars()) {
+ vars.add(var);
+ ExprVars.varsMentioned(vars, opExtend.getVarExprList().getExpr(var));
+ }
+ action(vars);
+ }
+
+ @Override
+ public void visit(OpOrder opOrder) {
+ Collection<Var> vars = new ArrayList<>();
+ for (SortCondition condition : opOrder.getConditions()) {
+ ExprVars.varsMentioned(vars, condition);
+ }
+ action(vars);
+ }
+
+ @Override
+ public void visit(OpProject opProject) {
+ for (Var var : opProject.getVars()) {
+ action(var);
+ }
+ }
+
+ @Override
+ public void visit(OpGroup opGroup) {
+ Collection<Var> vars = new ArrayList<>();
+ for (Var var : opGroup.getGroupVars().getVars()) {
+ vars.add(var);
+ ExprVars.varsMentioned(vars, opGroup.getGroupVars().getExpr(var));
+ }
+ }
+
+ @Override
+ public void visit(OpTopN opTop) {
+ Collection<Var> vars = new ArrayList<>();
+ for (SortCondition condition : opTop.getConditions()) {
+ ExprVars.varsMentioned(vars, condition);
+ }
+ action(vars);
+ }
+
+}
\ No newline at end of file
http://git-wip-us.apache.org/repos/asf/jena/blob/308810f2/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TS_Optimization.java
----------------------------------------------------------------------
diff --git a/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TS_Optimization.java b/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TS_Optimization.java
index fe3d4c4..56016fa 100644
--- a/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TS_Optimization.java
+++ b/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TS_Optimization.java
@@ -34,6 +34,7 @@ import org.junit.runners.Suite ;
, TestTransformFilterPlacement.class
, TestTransformMergeBGPs.class
, TestTransformPromoteTableEmpty.class
+ , TestTransformEliminateAssignments.class
, TestTransformTopN.class
, TestOptimizer.class
})
http://git-wip-us.apache.org/repos/asf/jena/blob/308810f2/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
new file mode 100644
index 0000000..1b73d25
--- /dev/null
+++ b/jena-arq/src/test/java/com/hp/hpl/jena/sparql/algebra/optimize/TestTransformEliminateAssignments.java
@@ -0,0 +1,171 @@
+package com.hp.hpl.jena.sparql.algebra.optimize;
+
+import org.apache.jena.atlas.lib.StrUtils;
+import org.junit.Assert;
+import org.junit.Test;
+
+import com.hp.hpl.jena.sparql.algebra.Op;
+import com.hp.hpl.jena.sparql.sse.SSE;
+
+/**
+ * Tests for the {@link TransformEliminateAssignments}
+ *
+ */
+public class TestTransformEliminateAssignments {
+
+ private void test(String input, String... output) {
+ Op original = SSE.parseOp(input);
+ test(original, output);
+ }
+
+ private void test(Op original, String... output) {
+ // Transform
+ Op actual = TransformEliminateAssignments.eliminate(original);
+
+ // Check results
+ if (output == null) {
+ // No transformation.
+ Assert.assertEquals(original, actual);
+ } else {
+ // Transformation expected
+ Op expected = SSE.parseOp(StrUtils.strjoinNL(output));
+ Assert.assertEquals(expected, actual);
+ }
+ }
+
+ private void testNoChange(String input) {
+ test(input, (String[]) null);
+ }
+
+ private void testNoChange(String... input) {
+ test(StrUtils.strjoinNL(input), (String[]) null);
+ }
+
+ @Test
+ public void eliminate_single_use_extend_01() {
+ // Assigned variable used only once can substitute expression for the
+ // later usage of the variable
+ //@formatter:off
+ test(StrUtils.strjoinNL("(filter (exprlist ?x)",
+ " (extend (?x true)",
+ " (table unit)))"),
+ "(filter (exprlist true)",
+ " (table unit))");
+ //@formatter:on
+ }
+
+ @Test
+ public void eliminate_single_use_extend_02() {
+ // Assigned variable used only once can substitute expression for the
+ // later usage of the variable
+ // The other assignment is removed because it's value is never used
+ //@formatter:off
+ test(StrUtils.strjoinNL("(filter (exprlist ?x)",
+ " (extend ((?x true) (?y false))",
+ " (table unit)))"),
+ "(filter (exprlist true)",
+ " (table unit))");
+ //@formatter:on
+ }
+
+ @Test
+ public void multi_use_extend_unchanged_01() {
+ // As the assigned variable is used multiple times we leave the
+ // assignment alone
+ //@formatter:off
+ testNoChange("(filter (> (* ?x ?x) 16)",
+ " (extend (?x 3)",
+ " (table unit)))");
+ //@formatter:on
+ }
+
+ @Test
+ public void multi_use_extend_unchanged_02() {
+ // Because the value of the assignment is used in multiple places we
+ // leave the assignment alone
+ //@formatter:off
+ testNoChange("(filter (exprlist ?x)",
+ " (join",
+ " (extend (?x true)",
+ " (table unit))",
+ " (bgp (triple ?x ?y ?z))))");
+ //@formatter:on
+ }
+
+ @Test
+ public void scoped_use_extend_01() {
+ // If the assignment is out of scope by the time it is used in the outer
+ // scope then we can't substitute it out there
+ // However if the scoping means the value is never used we can instead
+ // eliminate it entirely
+ //@formatter:off
+ test(StrUtils.strjoinNL("(filter (exprlist ?x)",
+ " (project (?y)",
+ " (extend (?x true)",
+ " (table unit))))"),
+ "(filter (exprlist ?x)",
+ " (project (?y)",
+ " (table unit)))");
+ //@formatter:on
+ }
+
+ @Test
+ public void scoped_use_extend_02() {
+ // If the assignment is out of scope by the time it is used in the outer
+ // scope then we can't substitute it out there
+ // However in this case we can substitute it in the inner scope
+ //@formatter:off
+ test(StrUtils.strjoinNL("(filter (exprlist ?x)",
+ " (project (?y)",
+ " (filter (exprlist ?x)",
+ " (extend (?x true)",
+ " (table unit)))))"),
+ "(filter (exprlist ?x)",
+ " (project (?y)",
+ " (filter (exprlist true)",
+ " (table unit))))");
+ //@formatter:on
+ }
+
+ @Test
+ public void eliminate_single_use_assign_01() {
+ //@formatter:off
+ test(StrUtils.strjoinNL("(filter (exprlist ?x)",
+ " (assign (?x true)",
+ " (table unit)))"),
+ "(filter (exprlist true)",
+ " (table unit))");
+ //@formatter:on
+ }
+
+ @Test
+ public void multi_use_assign_unchanged_01() {
+ //@formatter:off
+ testNoChange("(filter (> (* ?x ?x) 16)",
+ " (assign (?x 3)",
+ " (table unit)))");
+ //@formatter:on
+ }
+
+ @Test
+ public void multi_use_assign_unchanged_02() {
+ // Left alone because assigned to more than once
+ //@formatter:off
+ testNoChange("(filter (exprlist ?x)",
+ " (assign (?x true)",
+ " (assign (?x true)",
+ " (table unit))))");
+ //@formatter:on
+ }
+
+ @Test
+ public void multi_use_assign_unchanged_03() {
+ // Left alone because assigned to more than once
+ //@formatter:off
+ testNoChange("(filter (exprlist ?x)",
+ " (assign (?x true)",
+ " (assign (?x false)",
+ " (table unit))))");
+ //@formatter:on
+ }
+}