jena-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From rve...@apache.org
Subject [01/26] jena git commit: Initial work on elminating assignments (JENA-780)
Date Tue, 07 Jul 2015 09:24:06 GMT
Repository: jena
Updated Branches:
  refs/heads/jena2 21b5e602e -> b02309f6d
  refs/heads/master 651f05311 -> 459f06935


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/jena2
Commit: 308810f273203591143ebd9c00d39077d309fa7d
Parents: 913b225
Author: Rob Vesse <rvesse@apache.org>
Authored: Thu Sep 25 15:34:37 2014 +0100
Committer: Rob Vesse <rvesse@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
+    }
+}


Mime
View raw message