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 <[email protected]> Authored: Thu Sep 25 15:34:37 2014 +0100 Committer: Rob Vesse <[email protected]> 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 + } +}
