jena-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From rve...@apache.org
Subject [3/3] jena git commit: More bug fixes to inlining assignments in extend (JENA-780)
Date Mon, 06 Jul 2015 14:49:14 GMT
More bug fixes to inlining assignments in extend (JENA-780)

This commit adds additional test cases and some bug fixes that cover the
case where there are single use assignments that can be inlined where
the value is only used in the extend we are currently processing which
requires some extra work to make sure we eliminate unused assignments
after we inline them.  It also ensures that subsequent assignments which
can also have assignments inlined into them refer to the correct
expression taking into account previous inlinings that have happened.


Project: http://git-wip-us.apache.org/repos/asf/jena/repo
Commit: http://git-wip-us.apache.org/repos/asf/jena/commit/d6f516de
Tree: http://git-wip-us.apache.org/repos/asf/jena/tree/d6f516de
Diff: http://git-wip-us.apache.org/repos/asf/jena/diff/d6f516de

Branch: refs/heads/eliminate-assignments
Commit: d6f516decedd40e0339012279a4e392239865cf0
Parents: 985b995
Author: Rob Vesse <rvesse@apache.org>
Authored: Mon Jul 6 15:46:20 2015 +0100
Committer: Rob Vesse <rvesse@apache.org>
Committed: Mon Jul 6 15:46:20 2015 +0100

----------------------------------------------------------------------
 .../optimize/TransformEliminateAssignments.java | 104 +++++++++++--------
 .../TestTransformEliminateAssignments.java      |  32 ++++++
 2 files changed, 93 insertions(+), 43 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/jena/blob/d6f516de/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 4d59fc3..59e77c2 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
@@ -78,7 +78,6 @@ import com.hp.hpl.jena.sparql.expr.NodeValue;
  * <ul>
  * <li>Filter Expressions</li>
  * <li>Bind and Select Expressions</li>
- * <li>Group By Expressions</li>
  * <li>Order By Expressions if aggressive in-lining is enabled</li>
  * </ul>
  * <p>
@@ -211,11 +210,7 @@ public class TransformEliminateAssignments extends TransformCopy {
         // Track the assignments for future reference
         this.tracker.putAssignments(opExtend.getVarExprList());
 
-        // TODO Could also eliminate assignments where the value is only used in
-        // a subsequent assignment
-
-        // See if there are any assignments we can eliminate entirely i.e. those
-        // where the assigned value is never used
+        // Eliminate and inline assignments
         VarExprList unusedAssignments = processUnused(opExtend.getVarExprList());
         VarExprList newAssignments = new VarExprList();
         for (Var assignVar : opExtend.getVarExprList().getVars()) {
@@ -229,6 +224,7 @@ public class TransformEliminateAssignments extends TransformCopy {
             Collection<Var> vars = new ArrayList<>();
             ExprVars.varsMentioned(vars, currExpr);
 
+            // See if we can inline anything
             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
@@ -242,6 +238,10 @@ public class TransformEliminateAssignments extends TransformCopy {
                     currExpr = ExprTransformer.transform(new ExprTransformSubstitute(var,
e), currExpr);
                     this.tracker.getAssignments().remove(var);
 
+                    // Need to update any assignments we may be tracking that
+                    // refer to the variable we just inlined
+                    this.tracker.updateAssignments(var, e);
+
                     // If the assignment to be eliminated was introduced by the
                     // extend we are processing need to remove it from the
                     // VarExprList we are currently building
@@ -271,7 +271,7 @@ public class TransformEliminateAssignments extends TransformCopy {
             if (this.tracker.getUsageCount(var) == 1)
                 singleUse.add(var, assignments.getExpr(var));
         }
-        
+
         // If nothing is single use
         if (singleUse.size() == 0)
             return null;
@@ -367,49 +367,57 @@ public class TransformEliminateAssignments extends TransformCopy {
 
     @Override
     public Op transform(OpGroup opGroup, Op subOp) {
-        if (!this.isApplicable())
-            return super.transform(opGroup, subOp);
-
-        // See what vars are used in the filter
-        Collection<Var> vars = new ArrayList<>();
-        VarExprList exprs = new VarExprList(opGroup.getGroupVars());
-        List<ExprAggregator> aggs = new ArrayList<ExprAggregator>(opGroup.getAggregators());
-        for (Expr expr : exprs.getExprs().values()) {
-            ExprVars.varsMentioned(vars, expr);
-        }
-
-        // Are any of these vars single usage?
-        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 group by
-            Expr e = getAssignExpr(var);
-            if (this.tracker.getUsageCount(var) == 2 && hasAssignment(var) &&
canInline(e)) {
-                // Can go back and eliminate that assignment
-                subOp = eliminateAssignment(subOp, var);
-                // Replace the variable usage with the expression in both the
-                // expressions and the aggregators
-                ExprTransform transform = new ExprTransformSubstitute(var, e);
-                exprs = processVarExprList(exprs, transform);
-                aggs = processAggregators(aggs, transform);
-                this.tracker.getAssignments().remove(var);
-                modified = true;
-            }
-        }
-
-        // Create a new group by if we've substituted any expressions
-        if (modified) {
-            return new OpGroup(subOp, exprs, aggs);
-        }
-
         return super.transform(opGroup, subOp);
+
+        // TODO Unclear if this will work properly or not because group can
+        // introduce new assignments as well as evaluate expressions
+
+        //@formatter:off
+//        if (!this.isApplicable())
+//            return super.transform(opGroup, subOp);
+//
+//        // See what vars are used in the filter
+//        Collection<Var> vars = new ArrayList<>();
+//        VarExprList exprs = new VarExprList(opGroup.getGroupVars());
+//        List<ExprAggregator> aggs = new ArrayList<ExprAggregator>(opGroup.getAggregators());
+//        for (Expr expr : exprs.getExprs().values()) {
+//            ExprVars.varsMentioned(vars, expr);
+//        }
+//
+//        // Are any of these vars single usage?
+//        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 group by
+//            Expr e = getAssignExpr(var);
+//            if (this.tracker.getUsageCount(var) == 2 && hasAssignment(var) &&
canInline(e)) {
+//                // Can go back and eliminate that assignment
+//                subOp = eliminateAssignment(subOp, var);
+//                // Replace the variable usage with the expression in both the
+//                // expressions and the aggregators
+//                ExprTransform transform = new ExprTransformSubstitute(var, e);
+//                exprs = processVarExprList(exprs, transform);
+//                aggs = processAggregators(aggs, transform);
+//                this.tracker.getAssignments().remove(var);
+//                modified = true;
+//            }
+//        }
+//
+//        // Create a new group by if we've substituted any expressions
+//        if (modified) {
+//            return new OpGroup(subOp, exprs, aggs);
+//        }
+//
+//        return super.transform(opGroup, subOp);
+        //@formatter:on
     }
 
     private Op eliminateAssignment(Op subOp, Var var) {
         return Transformer.transform(new TransformRemoveAssignment(var, getAssignExpr(var)),
subOp);
     }
 
+    @SuppressWarnings("unused")
     private VarExprList processVarExprList(VarExprList exprs, ExprTransform transform) {
         VarExprList newExprs = new VarExprList();
         for (Var v : exprs.getVars()) {
@@ -420,6 +428,7 @@ public class TransformEliminateAssignments extends TransformCopy {
         return newExprs;
     }
 
+    @SuppressWarnings("unused")
     private List<ExprAggregator> processAggregators(List<ExprAggregator> aggs,
ExprTransform transform) {
         List<ExprAggregator> newAggs = new ArrayList<ExprAggregator>();
         for (ExprAggregator agg : aggs) {
@@ -459,6 +468,15 @@ public class TransformEliminateAssignments extends TransformCopy {
             }
         }
 
+        public void updateAssignments(Var v, Expr e) {
+            ExprTransformSubstitute transform = new ExprTransformSubstitute(v, e);
+            for (Var assignVar : this.assignments.keySet()) {
+                Expr assignExpr = this.assignments.get(assignVar);
+                assignExpr = ExprTransformer.transform(transform, assignExpr);
+                this.assignments.put(assignVar, assignExpr);
+            }
+        }
+
         public void incrementDepth() {
             this.depth++;
         }

http://git-wip-us.apache.org/repos/asf/jena/blob/d6f516de/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 cd0904b..7d6cf40 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
@@ -145,6 +145,38 @@ public class TestTransformEliminateAssignments {
              "    (table unit)))");
         //@formatter:on
     }
+    
+    @Test
+    public void extend_02() {
+        // Assigned variable used only once can substitute expression for the
+        // later usage of the variable
+        // However we must be inside a projection as otherwise the assigned
+        // variable would be visible and we couldn't eliminate the assignment
+        //@formatter:off
+        test(StrUtils.strjoinNL("(project (?z)",
+                                "  (extend ((?x true) (?y ?x) (?z ?y))",
+                                "    (table unit)))"),
+             "(project (?z)",
+             "  (extend (?z true)",
+             "    (table unit)))");
+        //@formatter:on
+    }
+    
+    @Test
+    public void extend_03() {
+        // Assigned variable used only once can substitute expression for the
+        // later usage of the variable
+        // However we must be inside a projection as otherwise the assigned
+        // variable would be visible and we couldn't eliminate the assignment
+        //@formatter:off
+        test(StrUtils.strjoinNL("(project (?z)",
+                                "  (extend ((?a true) (?b ?a) (?c false) (?d ?c) (?z (||
?b ?d)))",
+                                "    (table unit)))"),
+             "(project (?z)",
+             "  (extend (?z (|| true false))",
+             "    (table unit)))");
+        //@formatter:on
+    }
 
     @Test
     public void orderby_01() {


Mime
View raw message