CTR: Added comments to describe `Traversal::invalidateTraverserRequirements()`. Also added some test cases and made `IncidentToAdjacentStrategy` better by adding `invalidateTraverserRequirements()` in case the strategy replaces `bothE().otherV()` with `both()`.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/89e722e0 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/89e722e0 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/89e722e0 Branch: refs/heads/TINKERPOP-1682 Commit: 89e722e0def599664f024c2d6dc5bb24440e2603 Parents: 0c6459d Author: Daniel Kuppitz <daniel_kupp...@hotmail.com> Authored: Thu Mar 15 07:40:41 2018 -0700 Committer: Daniel Kuppitz <daniel_kupp...@hotmail.com> Committed: Thu Mar 15 07:40:41 2018 -0700 ---------------------------------------------------------------------- .../gremlin/process/traversal/Traversal.java | 5 +- .../strategy/decoration/SubgraphStrategy.java | 3 + .../IncidentToAdjacentStrategy.java | 5 ++ .../traversal/util/DefaultTraversal.java | 4 ++ .../gremlin/process/ProcessComputerSuite.java | 6 +- .../gremlin/process/ProcessStandardSuite.java | 6 +- .../decoration/SubgraphStrategyProcessTest.java | 56 +++++++++++++-- .../IncidentToAdjacentStrategyProcessTest.java | 76 ++++++++++++++++++++ 8 files changed, 151 insertions(+), 10 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/89e722e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java index 7a6ddce..8f3948c 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traversal.java @@ -427,10 +427,13 @@ public interface Traversal<S, E> extends Iterator<E>, Serializable, Cloneable, A /** * Invalidates the set of all {@link TraverserRequirement}s for this traversal. + * This method should be used by strategies, which mutate the traversal and possibly change the + * traversal's requirements. + * Implementations should reset the internal requirements cache, if it exists. */ public default void invalidateTraverserRequirements() { - }; + } /** * Call the {@link Step#reset} method on every step in the traversal. http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/89e722e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategy.java index 7968363..ab9ceb8 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategy.java @@ -193,6 +193,9 @@ public final class SubgraphStrategy extends AbstractTraversalStrategy<TraversalS if (null != this.vertexCriterion) TraversalHelper.insertAfterStep(new TraversalFilterStep<>(traversal, this.vertexCriterion.clone()), someVStep, traversal); + // if a both() step is replaced by bothE().filter.otherV(), the traversal relies on path information, + // which isn't necessarily a traverser requirement at this point. To be sure, that the traversal will + // track path information, the (possibly cached) traverser requirements need to be invalidated. invalidateTraverserRequirements |= addsPathRequirement; } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/89e722e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java index 1c96cf8..4ca2465 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java @@ -111,6 +111,11 @@ public final class IncidentToAdjacentStrategy extends AbstractTraversalStrategy< newStep.addLabel(label); } TraversalHelper.replaceStep(step1, newStep, traversal); + if (step2 instanceof EdgeOtherVertexStep) { + // bothE().otherV() might have been the only step sequence that required path tracking. Invalidate the + // requirements to possibly end up with more optimized traversers. + traversal.invalidateTraverserRequirements(); + } traversal.removeStep(step2); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/89e722e0/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversal.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversal.java index 57c271b..3f5b366 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversal.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/DefaultTraversal.java @@ -168,6 +168,10 @@ public class DefaultTraversal<S, E> implements Traversal.Admin<S, E> { @Override public void invalidateTraverserRequirements() { this.requirements = null; + final TraversalParent parent = this.getParent(); + if (!(parent instanceof EmptyStep)) { + parent.asStep().getTraversal().invalidateTraverserRequirements(); + } } @Override http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/89e722e0/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java ---------------------------------------------------------------------- diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java index 0e0fc81..3d51a94 100644 --- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java +++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessComputerSuite.java @@ -87,6 +87,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SubgraphTe import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.TreeTest; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SubgraphStrategyProcessTest; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.TranslationStrategyProcessTest; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategyProcessTest; import org.apache.tinkerpop.gremlin.process.traversal.strategy.verification.ReadOnlyStrategyProcessTest; import org.apache.tinkerpop.gremlin.structure.Graph; import org.apache.tinkerpop.gremlin.structure.StructureStandardSuite; @@ -196,7 +197,10 @@ public class ProcessComputerSuite extends AbstractGremlinSuite { // decorations ReadOnlyStrategyProcessTest.class, - SubgraphStrategyProcessTest.class + SubgraphStrategyProcessTest.class, + + // optimizations + IncidentToAdjacentStrategyProcessTest.class }; /** http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/89e722e0/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessStandardSuite.java ---------------------------------------------------------------------- diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessStandardSuite.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessStandardSuite.java index 18e25d7..f7c19ac 100644 --- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessStandardSuite.java +++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/ProcessStandardSuite.java @@ -84,6 +84,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.EventS import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.PartitionStrategyProcessTest; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SubgraphStrategyProcessTest; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.TranslationStrategyProcessTest; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategyProcessTest; import org.apache.tinkerpop.gremlin.process.traversal.strategy.verification.ReadOnlyStrategyProcessTest; import org.apache.tinkerpop.gremlin.structure.Graph; import org.apache.tinkerpop.gremlin.structure.StructureStandardSuite; @@ -183,7 +184,10 @@ public class ProcessStandardSuite extends AbstractGremlinSuite { EventStrategyProcessTest.class, ReadOnlyStrategyProcessTest.class, PartitionStrategyProcessTest.class, - SubgraphStrategyProcessTest.class + SubgraphStrategyProcessTest.class, + + // optimizations + IncidentToAdjacentStrategyProcessTest.class }; /** http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/89e722e0/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyProcessTest.java ---------------------------------------------------------------------- diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyProcessTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyProcessTest.java index 2565770..c2e3236 100644 --- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyProcessTest.java +++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyProcessTest.java @@ -22,17 +22,24 @@ import org.apache.commons.configuration.MapConfiguration; import org.apache.tinkerpop.gremlin.LoadGraphWith; import org.apache.tinkerpop.gremlin.process.AbstractGremlinProcessTest; import org.apache.tinkerpop.gremlin.process.GremlinProcessRunner; +import org.apache.tinkerpop.gremlin.process.remote.RemoteGraph; import org.apache.tinkerpop.gremlin.process.traversal.Order; import org.apache.tinkerpop.gremlin.process.traversal.P; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; import org.apache.tinkerpop.gremlin.process.traversal.step.filter.TraversalFilterStep; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.InlineFilterStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_LP_O_P_S_SE_SL_Traverser; +import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_LP_O_P_S_SE_SL_TraverserGenerator; +import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_O_Traverser; +import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_O_TraverserGenerator; import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; import org.apache.tinkerpop.gremlin.structure.Column; import org.apache.tinkerpop.gremlin.structure.Edge; import org.apache.tinkerpop.gremlin.structure.Vertex; +import org.hamcrest.Matchers; import org.junit.Test; import org.junit.runner.RunWith; @@ -43,18 +50,14 @@ import java.util.NoSuchElementException; import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.CREW; import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.MODERN; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.both; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.bothE; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.has; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.hasNot; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.out; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.outE; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.*; import static org.hamcrest.MatcherAssert.assertThat; import static org.hamcrest.core.IsCollectionContaining.hasItems; import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertFalse; import static org.junit.Assert.assertTrue; import static org.junit.Assert.fail; +import static org.junit.Assume.assumeThat; /** * @author Stephen Mallette (http://stephen.genoprime.com) @@ -502,5 +505,44 @@ public class SubgraphStrategyProcessTest extends AbstractGremlinProcessTest { checkResults(Arrays.asList(3, 3, 3, 4, 4, 5, 5, 5), sg.V().as("a").properties().select("a").dedup().outE().properties("skill").as("b").identity().select("b").by(__.value())); } - + @Test + @LoadGraphWith(MODERN) + public void shouldInvalidateTraverserRequirementsIfNecessary() throws Exception { + + assumeThat(graph, Matchers.not(Matchers.instanceOf(RemoteGraph.class))); + + GraphTraversalSource sg; + GraphTraversal.Admin traversal; + SubgraphStrategy strategy; + + strategy = SubgraphStrategy.build().vertices(has("name", P.within("josh", "lop", "ripple"))).create(); + sg = g.withStrategies(strategy); + + traversal = sg.V().outE().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = sg.V().outE().inV().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = sg.V().out().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + + traversal = sg.V().bothE().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = sg.V().bothE().otherV().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_LP_O_P_S_SE_SL_TraverserGenerator); + traversal = sg.V().both().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_LP_O_P_S_SE_SL_TraverserGenerator); + + traversal = sg.V().flatMap(bothE()).iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = sg.V().flatMap(bothE().otherV()).iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_LP_O_P_S_SE_SL_TraverserGenerator); + traversal = sg.V().flatMap(both()).iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_LP_O_P_S_SE_SL_TraverserGenerator); + + strategy = SubgraphStrategy.build().vertices(__.filter(__.simplePath())).create(); + sg = g.withStrategies(strategy); + + traversal = sg.V().out().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_LP_O_P_S_SE_SL_TraverserGenerator); + } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/89e722e0/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategyProcessTest.java ---------------------------------------------------------------------- diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategyProcessTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategyProcessTest.java new file mode 100644 index 0000000..63baf3b --- /dev/null +++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategyProcessTest.java @@ -0,0 +1,76 @@ +/* + * 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 org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization; + +import org.apache.tinkerpop.gremlin.LoadGraphWith; +import org.apache.tinkerpop.gremlin.process.AbstractGremlinProcessTest; +import org.apache.tinkerpop.gremlin.process.GremlinProcessRunner; +import org.apache.tinkerpop.gremlin.process.remote.RemoteGraph; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource; +import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_O_TraverserGenerator; +import org.hamcrest.Matchers; +import org.junit.Test; +import org.junit.runner.RunWith; + +import static org.apache.tinkerpop.gremlin.LoadGraphWith.GraphData.MODERN; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.*; +import static org.junit.Assert.*; +import static org.junit.Assume.assumeThat; + +/** + * @author Daniel Kuppitz (http://gremlin.guru) + */ +@RunWith(GremlinProcessRunner.class) +public class IncidentToAdjacentStrategyProcessTest extends AbstractGremlinProcessTest { + + @Test + @LoadGraphWith(MODERN) + public void shouldInvalidateTraverserRequirementsIfNecessary() throws Exception { + + assumeThat(graph, Matchers.not(Matchers.instanceOf(RemoteGraph.class))); + + final GraphTraversalSource itag = g.withStrategies(IncidentToAdjacentStrategy.instance()); + + GraphTraversal.Admin traversal; + + traversal = itag.V().outE().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = itag.V().outE().inV().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = itag.V().outE().otherV().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = itag.V().out().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + + traversal = itag.V().bothE().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = itag.V().bothE().otherV().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = itag.V().both().iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + + traversal = itag.V().flatMap(bothE()).iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = itag.V().flatMap(bothE().otherV()).iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + traversal = itag.V().flatMap(both()).iterate().asAdmin(); + assertTrue(traversal.getTraverserGenerator() instanceof B_O_TraverserGenerator); + } +}