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:43 UTC
[29/50] tinkerpop git commit: CTR: Reverted most of the previous
changes around the invalidation of traverser requirements. It turned out that
`PathRetractionStrategy` was to blame for too early caching of requirements.
The problem is that `PathRetr
CTR: Reverted most of the previous changes around the invalidation of traverser requirements. It turned out that `PathRetractionStrategy` was to blame for too early caching of requirements.
The problem is that `PathRetractionStrategy` processes all child traversals before other strategies even had the chance to mutate them. So in order to fix the problem, I used the same
anti-pattern (process all child traversals immediately) in the 2 strategies that can potentially mutate the traversal in a way that its requirements change (`SubgraphStrategy` and
`IncidentToAdjacentStrategy`).
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/b8eb8a02
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/b8eb8a02
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/b8eb8a02
Branch: refs/heads/TINKERPOP-1682
Commit: b8eb8a02f1675a1b22b86ccc54d22453c65f406f
Parents: 00b5a69
Author: Daniel Kuppitz <da...@hotmail.com>
Authored: Thu Mar 15 09:08:02 2018 -0700
Committer: Daniel Kuppitz <da...@hotmail.com>
Committed: Fri Mar 16 00:22:14 2018 -0700
----------------------------------------------------------------------
.../step/map/TraversalVertexProgramStep.java | 3 +++
.../traversal/AbstractRemoteTraversal.java | 5 -----
.../gremlin/process/traversal/Traversal.java | 10 ---------
.../lambda/AbstractLambdaTraversal.java | 7 -------
.../strategy/decoration/SubgraphStrategy.java | 22 +++++++++++---------
.../IncidentToAdjacentStrategy.java | 15 ++++++++-----
.../traversal/util/DefaultTraversal.java | 9 --------
.../decoration/SubgraphStrategyProcessTest.java | 4 +---
.../IncidentToAdjacentStrategyProcessTest.java | 7 +------
9 files changed, 27 insertions(+), 55 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8eb8a02/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/TraversalVertexProgramStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/TraversalVertexProgramStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/TraversalVertexProgramStep.java
index a591a25..642ad00 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/TraversalVertexProgramStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/computer/traversal/step/map/TraversalVertexProgramStep.java
@@ -24,11 +24,14 @@ import org.apache.tinkerpop.gremlin.process.computer.GraphFilter;
import org.apache.tinkerpop.gremlin.process.computer.Memory;
import org.apache.tinkerpop.gremlin.process.computer.traversal.MemoryTraversalSideEffects;
import org.apache.tinkerpop.gremlin.process.computer.traversal.TraversalVertexProgram;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.decoration.VertexProgramStrategy;
+import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.finalization.ComputerFinalizationStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
+import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
import org.apache.tinkerpop.gremlin.process.traversal.util.PureTraversal;
import org.apache.tinkerpop.gremlin.structure.Graph;
import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8eb8a02/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/traversal/AbstractRemoteTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/traversal/AbstractRemoteTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/traversal/AbstractRemoteTraversal.java
index 480d1fc..0c6a7aa 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/traversal/AbstractRemoteTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/remote/traversal/AbstractRemoteTraversal.java
@@ -88,11 +88,6 @@ public abstract class AbstractRemoteTraversal<S,E> implements RemoteTraversal<S,
}
@Override
- public void invalidateTraverserRequirements() {
- throw new UnsupportedOperationException("Remote traversals do not support this method");
- }
-
- @Override
public void setSideEffects(final TraversalSideEffects sideEffects) {
throw new UnsupportedOperationException("Remote traversals do not support this method");
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8eb8a02/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 8f3948c..220c995 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
@@ -426,16 +426,6 @@ public interface Traversal<S, E> extends Iterator<E>, Serializable, Cloneable, A
public Set<TraverserRequirement> getTraverserRequirements();
/**
- * 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.
*/
public default void reset() {
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8eb8a02/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/AbstractLambdaTraversal.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/AbstractLambdaTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/AbstractLambdaTraversal.java
index 84e1896..8f910a0 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/AbstractLambdaTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/lambda/AbstractLambdaTraversal.java
@@ -184,13 +184,6 @@ public abstract class AbstractLambdaTraversal<S, E> implements Traversal.Admin<S
}
@Override
- public void invalidateTraverserRequirements() {
- if (null != this.bypassTraversal) {
- this.bypassTraversal.invalidateTraverserRequirements();
- }
- }
-
- @Override
public int hashCode() {
return null == this.bypassTraversal ? this.getClass().hashCode() : this.bypassTraversal.hashCode();
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8eb8a02/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 ab9ceb8..467689f 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
@@ -149,6 +149,18 @@ public final class SubgraphStrategy extends AbstractTraversalStrategy<TraversalS
traversal.getStartStep().removeLabel(MARKER);
return;
}
+ for (final Step step : traversal.getSteps()) {
+ if (step instanceof TraversalParent) {
+ for (final Traversal.Admin t : ((TraversalParent) step).getLocalChildren()) {
+ this.apply(t);
+ t.getStartStep().addLabel(MARKER);
+ }
+ for (final Traversal.Admin t : ((TraversalParent) step).getGlobalChildren()) {
+ this.apply(t);
+ t.getStartStep().addLabel(MARKER);
+ }
+ }
+ }
//
final List<GraphStep> graphSteps = TraversalHelper.getStepsOfAssignableClass(GraphStep.class, traversal);
final List<VertexStep> vertexSteps = TraversalHelper.getStepsOfAssignableClass(VertexStep.class, traversal);
@@ -171,7 +183,6 @@ public final class SubgraphStrategy extends AbstractTraversalStrategy<TraversalS
}
// turn g.V().out() to g.V().outE().inV() only if there is an edge predicate otherwise
- boolean invalidateTraverserRequirements = false;
for (final VertexStep<?> step : vertexSteps) {
if (step.returnsEdge())
continue;
@@ -192,18 +203,9 @@ public final class SubgraphStrategy extends AbstractTraversalStrategy<TraversalS
TraversalHelper.insertAfterStep(new TraversalFilterStep<>(traversal, this.edgeCriterion.clone()), someEStep, traversal);
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;
}
}
- if (invalidateTraverserRequirements) {
- traversal.invalidateTraverserRequirements();
- }
-
// turn g.V().properties() to g.V().properties().xxx
// turn g.V().values() to g.V().properties().xxx.value()
if (null != this.vertexPropertyCriterion) {
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8eb8a02/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 4ca2465..77e896c 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
@@ -23,6 +23,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.Step;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.PathFilterStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.EdgeOtherVertexStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.EdgeVertexStep;
@@ -111,11 +112,6 @@ 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);
}
@@ -137,6 +133,10 @@ public final class IncidentToAdjacentStrategy extends AbstractTraversalStrategy<
final Collection<Pair<VertexStep, Step>> stepsToReplace = new ArrayList<>();
Step prev = null;
for (final Step curr : traversal.getSteps()) {
+ if (curr instanceof TraversalParent) {
+ ((TraversalParent) curr).getLocalChildren().forEach(this::apply);
+ ((TraversalParent) curr).getGlobalChildren().forEach(this::apply);
+ }
if (isOptimizable(prev, curr)) {
stepsToReplace.add(Pair.with((VertexStep) prev, curr));
}
@@ -153,4 +153,9 @@ public final class IncidentToAdjacentStrategy extends AbstractTraversalStrategy<
public Set<Class<? extends OptimizationStrategy>> applyPrior() {
return Collections.singleton(IdentityRemovalStrategy.class);
}
+
+ @Override
+ public Set<Class<? extends OptimizationStrategy>> applyPost() {
+ return Collections.singleton(PathRetractionStrategy.class);
+ }
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8eb8a02/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 3f5b366..585a82b 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
@@ -166,15 +166,6 @@ 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
public List<Step> getSteps() {
return this.unmodifiableSteps;
}
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8eb8a02/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 c2e3236..10473a8 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
@@ -31,9 +31,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSo
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;
@@ -507,7 +505,7 @@ public class SubgraphStrategyProcessTest extends AbstractGremlinProcessTest {
@Test
@LoadGraphWith(MODERN)
- public void shouldInvalidateTraverserRequirementsIfNecessary() throws Exception {
+ public void shouldGenerateCorrectTraversers() throws Exception {
assumeThat(graph, Matchers.not(Matchers.instanceOf(RemoteGraph.class)));
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/b8eb8a02/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
index 63baf3b..8f640f3 100644
--- 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
@@ -21,18 +21,15 @@ 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)
@@ -42,9 +39,7 @@ public class IncidentToAdjacentStrategyProcessTest extends AbstractGremlinProces
@Test
@LoadGraphWith(MODERN)
- public void shouldInvalidateTraverserRequirementsIfNecessary() throws Exception {
-
- assumeThat(graph, Matchers.not(Matchers.instanceOf(RemoteGraph.class)));
+ public void shouldGenerateCorrectTraversers() throws Exception {
final GraphTraversalSource itag = g.withStrategies(IncidentToAdjacentStrategy.instance());