tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From dkupp...@apache.org
Subject [1/2] 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 replace
Date Thu, 15 Mar 2018 14:43:56 GMT
Repository: tinkerpop
Updated Branches:
  refs/heads/master cb322aca0 -> e80cd574c


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/master
Commit: 89e722e0def599664f024c2d6dc5bb24440e2603
Parents: 0c6459d
Author: Daniel Kuppitz <daniel_kuppitz@hotmail.com>
Authored: Thu Mar 15 07:40:41 2018 -0700
Committer: Daniel Kuppitz <daniel_kuppitz@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);
+    }
+}


Mime
View raw message