You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by dk...@apache.org on 2018/03/20 15:42:37 UTC
[23/50] tinkerpop git commit: CTR: Added comments to describe
`Traversal::invalidateTraverserRequirements()`. Also added some test cases
and made `IncidentToAdjacentStrategy` better by adding
`invalidateTraverserRequirements()` in case the strategy repla
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 <da...@hotmail.com>
Authored: Thu Mar 15 07:40:41 2018 -0700
Committer: Daniel Kuppitz <da...@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);
+ }
+}