Return-Path: X-Original-To: apmail-jena-commits-archive@www.apache.org Delivered-To: apmail-jena-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id EED5B17720 for ; Thu, 25 Sep 2014 15:02:23 +0000 (UTC) Received: (qmail 21064 invoked by uid 500); 25 Sep 2014 15:02:23 -0000 Delivered-To: apmail-jena-commits-archive@jena.apache.org Received: (qmail 21039 invoked by uid 500); 25 Sep 2014 15:02:23 -0000 Mailing-List: contact commits-help@jena.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@jena.apache.org Delivered-To: mailing list commits@jena.apache.org Received: (qmail 21030 invoked by uid 99); 25 Sep 2014 15:02:23 -0000 Received: from tyr.zones.apache.org (HELO tyr.zones.apache.org) (140.211.11.114) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 25 Sep 2014 15:02:23 +0000 Received: by tyr.zones.apache.org (Postfix, from userid 65534) id 7D2A6914130; Thu, 25 Sep 2014 15:02:23 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: rvesse@apache.org To: commits@jena.apache.org Message-Id: X-Mailer: ASF-Git Admin Mailer Subject: git commit: Fix bug with scope of transform (JENA-780) Date: Thu, 25 Sep 2014 15:02:23 +0000 (UTC) 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 Authored: Thu Sep 25 16:01:18 2014 +0100 Committer: Rob Vesse 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 *
  • Assignments where the assigned value is never used elsewhere
    • * - * - * @author rvesse + *

    + * 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. + *

    * */ 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 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 assignments = new HashMap<>(); + private int depth = 0; public Map 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 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 - } }