jena-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From rve...@apache.org
Subject git commit: Fix bug with scope of transform (JENA-780)
Date Thu, 25 Sep 2014 15:02:23 GMT
Repository: jena
Updated Branches:
  refs/heads/eliminate-assignments 308810f27 -> 79f8765ac


Fix bug with scope of transform (JENA-780)

This commit fixes the transform so that it is only applied to extend
assignments that occur inside a projection.  If it is not within a
projection we have to assume that the variable may be used and thus must
leave it alone.


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

Branch: refs/heads/eliminate-assignments
Commit: 79f8765ac9caeda095db241621da0566ab7bccca
Parents: 308810f
Author: Rob Vesse <rvesse@apache.org>
Authored: Thu Sep 25 16:01:18 2014 +0100
Committer: Rob Vesse <rvesse@apache.org>
Committed: Thu Sep 25 16:01:18 2014 +0100

----------------------------------------------------------------------
 .../optimize/TransformEliminateAssignments.java |  91 ++++++++++++---
 .../algebra/optimize/VariableUsagePusher.java   |  18 +++
 .../algebra/optimize/VariableUsageTracker.java  |  18 +++
 .../algebra/optimize/VariableUsageVisitor.java  |  18 +++
 .../TestTransformEliminateAssignments.java      | 115 ++++++++++---------
 5 files changed, 190 insertions(+), 70 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/jena/blob/79f8765a/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 49f8f1c..d24c500 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
@@ -1,3 +1,21 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
 package com.hp.hpl.jena.sparql.algebra.optimize;
 
 import java.util.ArrayList;
@@ -13,7 +31,6 @@ 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;
@@ -39,15 +56,18 @@ import com.hp.hpl.jena.sparql.expr.ExprVars;
  * assignment</li>
  * <li>Assignments where the assigned value is never used elsewhere</li>
  * </ol>
- * 
- * @author rvesse
+ * <p>
+ * Both of these changes can only happen inside of projections as otherwise we
+ * have to assume that the user may need the resulting variable and thus we
+ * leave the assignment alone.
+ * </p>
  * 
  */
 public class TransformEliminateAssignments extends TransformCopy {
 
     public static Op eliminate(Op op) {
         AssignmentTracker tracker = new AssignmentTracker();
-        VariableUsagePusher pusher = new VariableUsagePusher(tracker);
+        AssignmentPusher pusher = new AssignmentPusher(tracker);
         AssignmentPopper popper = new AssignmentPopper(tracker);
         Transform transform = new TransformEliminateAssignments(tracker, pusher, popper);
 
@@ -62,6 +82,19 @@ public class TransformEliminateAssignments extends TransformCopy {
         this.before = before;
     }
 
+    protected boolean isApplicable() {
+        // Can only be applied if we are inside a projection as otherwise the
+        // assigned variables need to remain visible
+        if (!this.tracker.insideProjection())
+            return false;
+        // If there are no eligible assignments then don't bother doing any work
+        if (this.tracker.assignments.size() == 0)
+            return false;
+
+        // Otherwise may be applicable
+        return true;
+    }
+
     @Override
     public Op transform(OpExt opExt) {
         return opExt.apply(this, this.before, this.after);
@@ -69,6 +102,9 @@ public class TransformEliminateAssignments extends TransformCopy {
 
     @Override
     public Op transform(OpFilter opFilter, Op subOp) {
+        if (!this.isApplicable())
+            return super.transform(opFilter, subOp);
+
         // See what vars are used in the filter
         Collection<Var> vars = new ArrayList<>();
         for (Expr expr : opFilter.getExprs().getList()) {
@@ -103,16 +139,10 @@ public class TransformEliminateAssignments extends TransformCopy {
     }
 
     @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) {
+        if (!this.tracker.insideProjection())
+            return super.transform(opExtend, subOp);
+
         this.tracker.putAssignments(opExtend.getVarExprList());
 
         // See if there are any assignments we can eliminate entirely i.e. those
@@ -165,6 +195,7 @@ public class TransformEliminateAssignments extends TransformCopy {
     private static class AssignmentTracker extends VariableUsageTracker {
 
         private Map<Var, Expr> assignments = new HashMap<>();
+        private int depth = 0;
 
         public Map<Var, Expr> getAssignments() {
             return this.assignments;
@@ -191,6 +222,36 @@ public class TransformEliminateAssignments extends TransformCopy {
             }
         }
 
+        public void incrementDepth() {
+            this.depth++;
+        }
+
+        public void decrementDepth() {
+            this.depth--;
+            // Clear all assignments if not inside a project
+            if (this.depth == 0)
+                this.assignments.clear();
+        }
+
+        public boolean insideProjection() {
+            return this.depth > 0;
+        }
+    }
+
+    private static class AssignmentPusher extends VariableUsagePusher {
+
+        private AssignmentTracker tracker;
+
+        public AssignmentPusher(AssignmentTracker tracker) {
+            super(tracker);
+            this.tracker = tracker;
+        }
+
+        @Override
+        public void visit(OpProject opProject) {
+            super.visit(opProject);
+            this.tracker.incrementDepth();
+        }
     }
 
     private static class AssignmentPopper extends OpVisitorBase {
@@ -204,8 +265,7 @@ public class TransformEliminateAssignments extends TransformCopy {
         @Override
         public void visit(OpProject opProject) {
             // Any assignments that are not projected should be discarded at
-            // this
-            // point
+            // this point
             Iterator<Var> vars = tracker.getAssignments().keySet().iterator();
             while (vars.hasNext()) {
                 Var var = vars.next();
@@ -213,6 +273,7 @@ public class TransformEliminateAssignments extends TransformCopy {
                     vars.remove();
             }
             tracker.pop();
+            this.tracker.decrementDepth();
         }
 
     }

http://git-wip-us.apache.org/repos/asf/jena/blob/79f8765a/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
index 51a04fb..437a104 100644
--- 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
@@ -1,3 +1,21 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
 package com.hp.hpl.jena.sparql.algebra.optimize;
 
 import java.util.Collection;

http://git-wip-us.apache.org/repos/asf/jena/blob/79f8765a/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
index f63e41e..770738c 100644
--- 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
@@ -1,3 +1,21 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
 package com.hp.hpl.jena.sparql.algebra.optimize;
 
 import java.util.Collection;

http://git-wip-us.apache.org/repos/asf/jena/blob/79f8765a/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
index 9fda1c4..664c7b0 100644
--- 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
@@ -1,3 +1,21 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
 package com.hp.hpl.jena.sparql.algebra.optimize;
 
 import java.util.ArrayList;

http://git-wip-us.apache.org/repos/asf/jena/blob/79f8765a/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 1b73d25..ff8b65f 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
@@ -1,3 +1,21 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
 package com.hp.hpl.jena.sparql.algebra.optimize;
 
 import org.apache.jena.atlas.lib.StrUtils;
@@ -33,6 +51,7 @@ public class TestTransformEliminateAssignments {
         }
     }
 
+    @SuppressWarnings("unused")
     private void testNoChange(String input) {
         test(input, (String[]) null);
     }
@@ -45,26 +64,54 @@ public class TestTransformEliminateAssignments {
     public void eliminate_single_use_extend_01() {
         // 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("(filter (exprlist ?x)",
-                                "  (extend (?x true)",
-                                "    (table unit)))"),
-             "(filter (exprlist true)",
-             "  (table unit))");
+        test(StrUtils.strjoinNL("(project (?y)",
+                                "  (filter (exprlist ?x)",
+                                "    (extend (?x true)",
+                                "      (table unit))))"),
+             "(project (?y)",
+             "  (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
+        // Assignment for ?y can be removed because it is never used
+        // 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("(filter (exprlist ?x)",
-                                "  (extend ((?x true) (?y false))",
-                                "    (table unit)))"),
-             "(filter (exprlist true)",
-             "    (table unit))");
+        test(StrUtils.strjoinNL("(project (?z)",
+                                "  (filter (exprlist ?x)",
+                                "    (extend ((?x true) (?y false))",
+                                "      (table unit))))"),
+             "(project (?z)",
+             "  (filter (exprlist true)",
+             "    (table unit)))");
+        //@formatter:on
+    }
+
+    @Test
+    public void single_use_extend_unchanged_01() {
+        // Cannot eliminate as there is no projection so the assigned variable
+        // is visible even though in the algebra given it is used only once
+        //@formatter:off
+        testNoChange("(filter (exprlist ?x)",
+                     "  (extend (?x true)",
+                     "    (table unit)))");
+        //@formatter:on
+    }
+
+    @Test
+    public void single_use_extend_unchanged_02() {
+        // Cannot eliminate as there is no projection so the assigned variable
+        // is visible even though in the algebra given it is used only once
+        //@formatter:off
+        testNoChange("(filter (exprlist ?x)",
+                     "  (extend ((?x true) (?y false))",
+                     "    (table unit)))");
         //@formatter:on
     }
 
@@ -126,46 +173,4 @@ public class TestTransformEliminateAssignments {
             "      (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