You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by sp...@apache.org on 2021/03/05 13:06:12 UTC
[tinkerpop] branch TINKERPOP-1994 updated (ecd225d -> afdff05)
This is an automated email from the ASF dual-hosted git repository.
spmallette pushed a change to branch TINKERPOP-1994
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git.
discard ecd225d TINKERPOP-1994 Used LazyBarrierStrategy to control barrier() insertion in other strategies.
new afdff05 TINKERPOP-1994 Used LazyBarrierStrategy to control barrier() insertion in other strategies.
This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version. This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:
* -- * -- B -- O -- O -- O (ecd225d)
\
N -- N -- N refs/heads/TINKERPOP-1994 (afdff05)
You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.
Any revisions marked "omit" are not gone; other references still
refer to them. Any revisions marked "discard" are gone forever.
The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../optimization/RepeatUnrollStrategyTest.java | 47 ++++++++++++++++------
1 file changed, 35 insertions(+), 12 deletions(-)
[tinkerpop] 01/01: TINKERPOP-1994 Used LazyBarrierStrategy to
control barrier() insertion in other strategies.
Posted by sp...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
spmallette pushed a commit to branch TINKERPOP-1994
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
commit afdff05cb87385ea7f9515af2fe75c750b029794
Author: Stephen Mallette <st...@amazon.com>
AuthorDate: Thu Mar 4 18:30:01 2021 -0500
TINKERPOP-1994 Used LazyBarrierStrategy to control barrier() insertion in other strategies.
---
CHANGELOG.asciidoc | 1 +
docs/src/upgrade/release-3.4.x.asciidoc | 73 ++++++++++++++++++
.../strategy/optimization/LazyBarrierStrategy.java | 18 ++++-
.../optimization/PathRetractionStrategy.java | 7 +-
.../optimization/RepeatUnrollStrategy.java | 21 ++++--
.../strategy/decoration/SubgraphStrategyTest.java | 3 +-
.../optimization/LazyBarrierStrategyTest.java | 4 +-
.../optimization/PathRetractionStrategyTest.java | 21 ++++--
.../optimization/RepeatUnrollStrategyTest.java | 88 ++++++++++++++--------
9 files changed, 186 insertions(+), 50 deletions(-)
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index e396795..54a19ea 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -31,6 +31,7 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
* Fixed bug with Javascript Groovy `Translator` when generating Gremlin with multiple embedded traversals.
* Modified Gremlin Server `Settings` to be more extensible allowing for custom options with the YAML parser.
* Fixed `toString()` representation of `P` when string values are present in Javascript.
+* Ensured that `barrier()` additions by strategies were controlled solely by `LazyBarrierStrategy`.
[[release-3-4-10]]
=== TinkerPop 3.4.10 (Release Date: January 18, 2021)
diff --git a/docs/src/upgrade/release-3.4.x.asciidoc b/docs/src/upgrade/release-3.4.x.asciidoc
index d26adc7..f6f4883 100644
--- a/docs/src/upgrade/release-3.4.x.asciidoc
+++ b/docs/src/upgrade/release-3.4.x.asciidoc
@@ -21,6 +21,79 @@ image::https://raw.githubusercontent.com/apache/tinkerpop/master/docs/static/ima
*Avant-Gremlin Construction #3 for Theremin and Flowers*
+== TinkerPop 3.4.11
+
+*Release Date: NOT OFFICIALLY RELEASED YET*
+
+Please see the link:https://github.com/apache/tinkerpop/blob/3.4.11/CHANGELOG.asciidoc#release-3-4-11[changelog] for a
+complete list of all the modifications that are part of this release.
+
+=== Upgrading for Users
+
+==== barrier() Control
+
+Various `TraversalStrategy` implementations inject `barrier()` instances to improve traversal performance. It is often
+helpful in debugging situations or in tweaking traversal performance activities that it may be necessary to prevent
+automated `barrier()` injection. Formerly, that involved removing `LazyBarrierStrategy`, `RepeatUnrollStrategy`, and
+`PathRetractionStrategy` as all three of those strategies had the potential to add a `barrier()`. While this approach
+would work, it may be hard to recall those three strategies easily and you may be removing optimizations that might
+have been useful in addition to the `barrier()`.
+
+In 3.4.11, it is only necessary to remove `LazyBarrierStrategy`. Doing so will disable `barrier()` additions in other
+strategies and as this is the new model of execution, it can be expected to work as the approach in the future even
+if other strategies attempt to add `barrier()` steps for some reason. Note of course that this rule only applies to
+TinkerPop-enabled strategies. It is possible that provider-specific strategies could add `barrier()`-steps and thus
+still require direct removal.
+
+[source,text]
+----
+gremlin> g.V().repeat(out()).times(2).in().explain()
+==>Traversal Explanation
+====================================================================================================================================================================================
+Original Traversal [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,vertex), RepeatEndStep],until(loops(2)),emit(false)), VertexStep(IN,vertex)]
+
+ConnectiveStrategy [D] [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,vertex), RepeatEndStep],until(loops(2)),emit(false)), VertexStep(IN,vertex)]
+RepeatUnrollStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+IncidentToAdjacentStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+MatchPredicateStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+PathRetractionStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+FilterRankingStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+InlineFilterStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+AdjacentToIncidentStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+CountStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+EarlyLimitStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+LazyBarrierStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(IN,vertex)]
+TinkerGraphCountStrategy [P] [GraphStep(vertex,[]), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(IN,vertex)]
+TinkerGraphStepStrategy [P] [TinkerGraphStep(vertex,[]), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(IN,vertex)]
+ProfileStrategy [F] [TinkerGraphStep(vertex,[]), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(IN,vertex)]
+StandardVerificationStrategy [V] [TinkerGraphStep(vertex,[]), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(IN,vertex)]
+
+Final Traversal [TinkerGraphStep(vertex,[]), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(OUT,vertex), NoOpBarrierStep(2500), VertexStep(IN,vertex)]
+gremlin> g.withoutStrategies(LazyBarrierStrategy).V().repeat(out()).times(2).in().explain()
+==>Traversal Explanation
+=================================================================================================================================================================
+Original Traversal [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,vertex), RepeatEndStep],until(loops(2)),emit(false)), VertexStep(IN,vertex)]
+
+ConnectiveStrategy [D] [GraphStep(vertex,[]), RepeatStep([VertexStep(OUT,vertex), RepeatEndStep],until(loops(2)),emit(false)), VertexStep(IN,vertex)]
+RepeatUnrollStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+CountStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+EarlyLimitStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+MatchPredicateStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+FilterRankingStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+IncidentToAdjacentStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+PathRetractionStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+InlineFilterStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+AdjacentToIncidentStrategy [O] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+TinkerGraphCountStrategy [P] [GraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+TinkerGraphStepStrategy [P] [TinkerGraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+ProfileStrategy [F] [TinkerGraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+StandardVerificationStrategy [V] [TinkerGraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+
+Final Traversal [TinkerGraphStep(vertex,[]), VertexStep(OUT,vertex), VertexStep(OUT,vertex), VertexStep(IN,vertex)]
+----
+
+See: link:https://issues.apache.org/jira/browse/TINKERPOP-1994[TINKERPOP-1994]
+
== TinkerPop 3.4.10
*Release Date: January 18, 2021*
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategy.java
index b942d8f..d7cf224 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategy.java
@@ -36,6 +36,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.util.ProfileStep;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import org.apache.tinkerpop.gremlin.structure.Graph;
import java.util.Arrays;
import java.util.HashSet;
@@ -55,7 +56,8 @@ import java.util.Set;
*/
public final class LazyBarrierStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> implements TraversalStrategy.OptimizationStrategy {
- private final boolean IS_TESTING = Boolean.valueOf(System.getProperty("is.testing", "false"));
+ public static final String BARRIER_PLACEHOLDER = Graph.Hidden.hide("gremlin.lazyBarrier.position");
+ public static final String BARRIER_COPY_LABELS = Graph.Hidden.hide("gremlin.lazyBarrier.copyLabels");
private static final LazyBarrierStrategy INSTANCE = new LazyBarrierStrategy();
private static final Set<Class<? extends OptimizationStrategy>> PRIORS = new HashSet<>(Arrays.asList(
CountStrategy.class,
@@ -65,7 +67,8 @@ public final class LazyBarrierStrategy extends AbstractTraversalStrategy<Travers
FilterRankingStrategy.class,
InlineFilterStrategy.class,
MatchPredicateStrategy.class,
- EarlyLimitStrategy.class));
+ EarlyLimitStrategy.class,
+ RepeatUnrollStrategy.class));
private static final int BIG_START_SIZE = 5;
protected static final int MAX_BARRIER_SIZE = 2500;
@@ -88,11 +91,21 @@ public final class LazyBarrierStrategy extends AbstractTraversalStrategy<Travers
for (int i = 0; i < traversal.getSteps().size(); i++) {
final Step<?, ?> step = traversal.getSteps().get(i);
+ if (step.getLabels().contains(BARRIER_PLACEHOLDER)) {
+ TraversalHelper.insertAfterStep(new NoOpBarrierStep<>(traversal, MAX_BARRIER_SIZE), step, traversal);
+ step.removeLabel(BARRIER_PLACEHOLDER);
+ if (step.getLabels().contains(BARRIER_COPY_LABELS)) {
+ step.removeLabel(BARRIER_COPY_LABELS);
+ TraversalHelper.copyLabels(step, step.getNextStep(), true);
+ }
+ }
+
if (step instanceof PathProcessor) {
final Set<String> keepLabels = ((PathProcessor) step).getKeepLabels();
if (null != keepLabels && keepLabels.isEmpty()) // if no more path data, then start barrier'ing again
labeledPath = false;
}
+
if (step instanceof FlatMapStep &&
!(step instanceof VertexStep && ((VertexStep) step).returnsEdge()) ||
(step instanceof GraphStep &&
@@ -115,6 +128,7 @@ public final class LazyBarrierStrategy extends AbstractTraversalStrategy<Travers
} else
foundFlatMap = true;
}
+
if (!step.getLabels().isEmpty())
labeledPath = true;
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java
index d370c38..e6ba8f3 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java
@@ -92,6 +92,8 @@ public final class PathRetractionStrategy extends AbstractTraversalStrategy<Trav
return;
}
+ final boolean lazyBarrierStrategyInstalled = traversal.getStrategies().getStrategy(LazyBarrierStrategy.class).isPresent();
+
final boolean onGraphComputer = TraversalHelper.onGraphComputer(traversal);
final Set<String> foundLabels = new HashSet<>();
final Set<String> keepLabels = new HashSet<>();
@@ -131,8 +133,9 @@ public final class PathRetractionStrategy extends AbstractTraversalStrategy<Trav
pathProcessor.getKeepLabels().addAll(((MatchStep) currentStep.getTraversal().getParent().asStep()).getMatchEndLabels());
}
- // OLTP barrier optimization that will try and bulk traversers after a path processor step to thin the stream
- if (!onGraphComputer &&
+ // LazyBarrierStrategy should control all barrier() additions. OLTP barrier optimization that will try
+ // and bulk traversers after a path processor step to thin the stream
+ if (lazyBarrierStrategyInstalled && !onGraphComputer &&
!(currentStep instanceof MatchStep) &&
!(currentStep instanceof Barrier) &&
!(currentStep.getNextStep() instanceof Barrier) &&
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategy.java
index 924b4d4..2b08f17 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategy.java
@@ -20,6 +20,7 @@
package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization;
import org.apache.tinkerpop.gremlin.process.traversal.Scope;
+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.lambda.LoopTraversal;
@@ -66,6 +67,8 @@ public final class RepeatUnrollStrategy extends AbstractTraversalStrategy<Traver
if (TraversalHelper.onGraphComputer(traversal))
return;
+ final boolean lazyBarrierStrategyInstalled = traversal.getStrategies().getStrategy(LazyBarrierStrategy.class).isPresent();
+
for (int i = 0; i < traversal.getSteps().size(); i++) {
if (traversal.getSteps().get(i) instanceof RepeatStep) {
final RepeatStep<?> repeatStep = (RepeatStep) traversal.getSteps().get(i);
@@ -82,16 +85,24 @@ public final class RepeatUnrollStrategy extends AbstractTraversalStrategy<Traver
for (int j = 0; j < loops; j++) {
TraversalHelper.insertTraversal(insertIndex, repeatTraversal.clone(), traversal);
insertIndex = insertIndex + repeatLength;
- if ((j != (loops - 1) || !(traversal.getSteps().get(insertIndex).getNextStep() instanceof Barrier)) // only add a final NoOpBarrier is subsequent step is not a barrier
- && !(traversal.getSteps().get(insertIndex) instanceof NoOpBarrierStep) // Don't add a barrier if this step is a barrier (prevents nested repeat adding the barrier multiple times)
- ) {
- traversal.addStep(++insertIndex, new NoOpBarrierStep<>(traversal, MAX_BARRIER_SIZE));
+
+ // the addition of barriers is determined by the existence of LazyBarrierStrategy
+ if (lazyBarrierStrategyInstalled) {
+ // only add a final NoOpBarrier is subsequent step is not a barrier
+ // Don't add a barrier if this step is a barrier (prevents nested repeat adding the barrier multiple times)
+ Step step = traversal.getSteps().get(insertIndex);
+ if ((j != (loops - 1) || !(step.getNextStep() instanceof Barrier)) && !(step instanceof NoOpBarrierStep)) {
+ traversal.addStep(++insertIndex, new NoOpBarrierStep<>(traversal, MAX_BARRIER_SIZE));
+ }
}
}
+
// label last step if repeat() was labeled
if (!repeatStep.getLabels().isEmpty())
TraversalHelper.copyLabels(repeatStep, traversal.getSteps().get(insertIndex), false);
- traversal.removeStep(i); // remove the RepeatStep
+
+ // remove the RepeatStep
+ traversal.removeStep(i);
}
}
}
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyTest.java
index bb51103..5f6c82d 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/SubgraphStrategyTest.java
@@ -110,8 +110,7 @@ public class SubgraphStrategyTest {
strategy.apply(traversal);
final List<TraversalFilterStep> steps = TraversalHelper.getStepsOfClass(TraversalFilterStep.class, traversal);
- System.out.println(repr + "+" + steps.stream().map(s -> s.getFilterTraversal().toString()).collect(Collectors.joining()));
- assertEquals(repr + ":" + traversal.toString(), expectedInsertedSteps, steps.size());
+ assertEquals(repr, expectedInsertedSteps, steps.size());
}
}
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategyTest.java
index 332a38e..b6f461c 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/LazyBarrierStrategyTest.java
@@ -19,10 +19,12 @@
package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization;
import org.apache.tinkerpop.gremlin.process.traversal.P;
+import org.apache.tinkerpop.gremlin.process.traversal.Translator;
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.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.translator.GroovyTranslator;
import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
import org.junit.Test;
import org.junit.runner.RunWith;
@@ -47,7 +49,7 @@ public class LazyBarrierStrategyTest {
}
@Parameterized.Parameter(value = 0)
- public Traversal original;
+ public Traversal.Admin original;
@Parameterized.Parameter(value = 1)
public Traversal optimized;
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java
index 1a9ae43..d6130e9 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java
@@ -23,11 +23,13 @@ import org.apache.tinkerpop.gremlin.process.traversal.Order;
import org.apache.tinkerpop.gremlin.process.traversal.P;
import org.apache.tinkerpop.gremlin.process.traversal.Scope;
import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Translator;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.translator.GroovyTranslator;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
@@ -68,11 +70,14 @@ import static org.mockito.Mockito.when;
public class PathRetractionStrategyTest {
private static final Translator<String,String> translator = GroovyTranslator.of("__");
+ /**
+ * Always need LazyBarrierStrategy because it will trigger barrier() additions in PathRetractionStrategy.
+ */
private final List<TraversalStrategies> strategies = Arrays.asList(
- new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance()),
- new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance(), PathProcessorStrategy.instance()),
- new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance()),
- new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance(), RepeatUnrollStrategy.instance()));
+ new DefaultTraversalStrategies().addStrategies(LazyBarrierStrategy.instance(), PathRetractionStrategy.instance()),
+ new DefaultTraversalStrategies().addStrategies(LazyBarrierStrategy.instance(), PathRetractionStrategy.instance(), PathProcessorStrategy.instance()),
+ new DefaultTraversalStrategies().addStrategies(LazyBarrierStrategy.instance(), PathRetractionStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance()),
+ new DefaultTraversalStrategies().addStrategies(LazyBarrierStrategy.instance(), PathRetractionStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance(), RepeatUnrollStrategy.instance()));
@Parameterized.Parameter(value = 0)
public Traversal.Admin original;
@@ -161,16 +166,16 @@ public class PathRetractionStrategyTest {
{__.V().as("a").repeat(out().where(neq("a"))).emit().select("a").values("test"), "[[[a]], []]", null},
// given the way this test harness is structured, I have to manual test for RepeatUnrollStrategy (and it works) TODO: add more test parameters
// {__.V().as("a").repeat(__.out().where(neq("a"))).times(3).select("a").values("test"), Arrays.asList(Collections.singleton("a"), Collections.singleton("a"), Collections.singleton("a"), Collections.emptySet())}
- {__.V().as("a").out().as("b").select("a").out().out(), "[[]]", __.V().as("a").out().as("b").select("a").barrier(MAX_BARRIER_SIZE).out().out()},
+ {__.V().as("a").out().as("b").select("a").out().out(), "[[]]", __.V().as("a").out().as("b").select("a").barrier(PathRetractionStrategy.MAX_BARRIER_SIZE).out().barrier(LazyBarrierStrategy.MAX_BARRIER_SIZE).out()},
{__.V().as("a").out().as("b").select("a").count(), "[[]]", __.V().as("a").out().as("b").select("a").count()},
{__.V().as("a").out().as("b").select("a").barrier().count(), "[[]]", __.V().as("a").out().as("b").select("a").barrier().count()},
{__.V().as("a").out().as("b").dedup("a", "b").out(), "[[]]", __.V().as("a").out().as("b").dedup("a", "b").out()},
{__.V().as("a").out().as("b").match(as("a").out().as("b")), "[[a, b]]", __.V().as("a").out().as("b").match(as("a").out().as("b"))},
{__.V().as("a").out().as("b").match(as("a").out().as("b")).select("a"), "[[a], []]", __.V().as("a").out().as("b").match(as("a").out().as("b")).select("a")},
- {__.V().as("a").out().as("b").match(as("a").out().as("b")).select("a").out().dedup("a"), "[[a], [a], []]", __.V().as("a").out().as("b").match(as("a").out().as("b")).select("a").barrier(MAX_BARRIER_SIZE).out().dedup("a")},
- {__.V().as("a").out().as("b").where(P.gt("a")).out().out(), "[[]]", __.V().as("a").out().as("b").where(P.gt("a")).barrier(MAX_BARRIER_SIZE).out().out()},
+ {__.V().as("a").out().as("b").match(as("a").out().as("b")).select("a").out().dedup("a"), "[[a], [a], []]", __.V().as("a").out().as("b").match(as("a").out().as("b")).select("a").barrier(PathRetractionStrategy.MAX_BARRIER_SIZE).out().dedup("a")},
+ {__.V().as("a").out().as("b").where(P.gt("a")).out().out(), "[[]]", __.V().as("a").out().as("b").where(P.gt("a")).barrier(PathRetractionStrategy.MAX_BARRIER_SIZE).out().barrier(LazyBarrierStrategy.MAX_BARRIER_SIZE).out()},
{__.V().as("a").out().as("b").where(P.gt("a")).count(), "[[]]", __.V().as("a").out().as("b").where(P.gt("a")).count()},
- {__.V().as("a").out().as("b").select("a").as("c").where(P.gt("b")).out(), "[[b], []]", __.V().as("a").out().as("b").select("a").as("c").barrier(MAX_BARRIER_SIZE).where(P.gt("b")).barrier(MAX_BARRIER_SIZE).out()},
+ {__.V().as("a").out().as("b").select("a").as("c").where(P.gt("b")).out(), "[[b], []]", __.V().as("a").out().as("b").select("a").as("c").barrier(PathRetractionStrategy.MAX_BARRIER_SIZE).where(P.gt("b")).barrier(PathRetractionStrategy.MAX_BARRIER_SIZE).out()},
{__.V().select("c").map(select("c").map(select("c"))).select("c"), "[[c], [[c], [[c]]], []]", null},
{__.V().select("c").map(select("c").map(select("c"))).select("b"), "[[b, c], [[b, c], [[b]]], []]", null},
{__.V().as("a").out().as("b").select("a").select("b").union(
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategyTest.java
index 1ebbd3f..5990ae9 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/RepeatUnrollStrategyTest.java
@@ -25,8 +25,10 @@ import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.NoOpBarrierStep;
import org.apache.tinkerpop.gremlin.process.traversal.translator.GroovyTranslator;
import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
+import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import org.junit.Test;
import org.junit.runner.RunWith;
@@ -49,60 +51,86 @@ public class RepeatUnrollStrategyTest {
private static final Translator<String,String> translator = GroovyTranslator.of("__");
@Parameterized.Parameter(value = 0)
- public Traversal.Admin original;
+ public Traversal.Admin<?,?> original;
@Parameterized.Parameter(value = 1)
- public Traversal optimized;
+ public Traversal<?,?> optimized;
@Parameterized.Parameter(value = 2)
- public Collection<TraversalStrategy> otherStrategies;
+ public Collection<TraversalStrategy<?>> otherStrategies;
@Test
public void doTest() {
final String repr = translator.translate(original.getBytecode());
- final TraversalStrategies strategies = new DefaultTraversalStrategies();
- strategies.addStrategies(RepeatUnrollStrategy.instance());
- for (final TraversalStrategy strategy : this.otherStrategies) {
- strategies.addStrategies(strategy);
+ final TraversalStrategies strategiesWithLazy = new DefaultTraversalStrategies();
+ strategiesWithLazy.addStrategies(RepeatUnrollStrategy.instance());
+ Traversal.Admin<?, ?> clonedOriginal = this.original.clone();
+
+ // adding LazyBarrierStrategy as RepeatUnrollStrategy adds barriers and the existence of this strategy
+ // triggers those additions. if they are not there they will not be present and most of these assertions
+ // assume this strategy present
+ strategiesWithLazy.addStrategies(LazyBarrierStrategy.instance());
+ for (final TraversalStrategy<?> strategy : this.otherStrategies) {
+ strategiesWithLazy.addStrategies(strategy);
+ }
+ clonedOriginal.setStrategies(strategiesWithLazy);
+ clonedOriginal.applyStrategies();
+ assertEquals("With LazyBarrierStrategy: " + repr, this.optimized, clonedOriginal);
+
+ final TraversalStrategies strategiesWithoutLazy = new DefaultTraversalStrategies();
+ strategiesWithoutLazy.addStrategies(RepeatUnrollStrategy.instance());
+ for (final TraversalStrategy<?> strategy : this.otherStrategies) {
+ strategiesWithoutLazy.addStrategies(strategy);
}
- this.original.asAdmin().setStrategies(strategies);
- this.original.asAdmin().applyStrategies();
- assertEquals(repr, this.optimized, this.original);
+ clonedOriginal = this.original.clone();
+ clonedOriginal.setStrategies(strategiesWithoutLazy);
+ clonedOriginal.applyStrategies();
+ final Traversal.Admin<?, ?> optimizedWithoutBarriers = this.optimized.asAdmin().clone();
+
+ // remove all the barriers as LazyBarrierStrategy is not present and therefore RepeatUnrollStrategy should
+ // not add any
+ TraversalHelper.getStepsOfAssignableClassRecursively(NoOpBarrierStep.class, optimizedWithoutBarriers).forEach(s -> {
+ TraversalHelper.copyLabels(s, s.getPreviousStep(), true);
+ s.getTraversal().removeStep(s);
+ });
+ assertEquals("Without LazyBarrierStrategy: " + repr, optimizedWithoutBarriers, clonedOriginal);
+
}
@Parameterized.Parameters(name = "{0}")
public static Iterable<Object[]> generateTestParameters() {
- final int maxBarrierSize = RepeatUnrollStrategy.MAX_BARRIER_SIZE;
+ // tests added here should be written to assume that LazyBarrierStrategy is present. if a barrier() is
+ // manually added as the "original" then include an exclusion in doTest()
+ final int repeatBarrierSize = RepeatUnrollStrategy.MAX_BARRIER_SIZE;
final Predicate<Traverser<Vertex>> predicate = t -> t.loops() > 5;
return Arrays.asList(new Object[][]{
{__.repeat(out()).times(0), __.repeat(out()).times(0), Collections.emptyList()},
{__.<Vertex>times(0).repeat(out()), __.<Vertex>times(0).repeat(out()), Collections.emptyList()},
{__.identity(), __.identity(), Collections.emptyList()},
- {out().as("a").in().repeat(__.outE("created").bothV()).times(2).in(), out().as("a").in().outE("created").bothV().barrier(maxBarrierSize).outE("created").bothV().barrier(maxBarrierSize).in(), Collections.emptyList()},
- {out().repeat(__.outE("created").bothV()).times(1).in(), out().outE("created").bothV().barrier(maxBarrierSize).in(), Collections.emptyList()},
- {__.repeat(__.outE("created").bothV()).times(1).in(), __.outE("created").bothV().barrier(maxBarrierSize).in(), Collections.emptyList()},
- {__.repeat(out()).times(2).as("x").repeat(__.in().as("b")).times(3), out().barrier(maxBarrierSize).out().barrier(maxBarrierSize).as("x").in().as("b").barrier(maxBarrierSize).in().as("b").barrier(maxBarrierSize).in().as("b").barrier(maxBarrierSize), Collections.emptyList()},
- {__.repeat(__.outE("created").inV()).times(2), __.outE("created").inV().barrier(maxBarrierSize).outE("created").inV().barrier(maxBarrierSize), Collections.emptyList()},
- {__.repeat(out()).times(3), out().barrier(maxBarrierSize).out().barrier(maxBarrierSize).out().barrier(maxBarrierSize), Collections.emptyList()},
- {__.repeat(__.local(__.select("a").out("knows"))).times(2), __.local(__.select("a").out("knows")).barrier(maxBarrierSize).local(__.select("a").out("knows")).barrier(maxBarrierSize), Collections.emptyList()},
- {__.<Vertex>times(2).repeat(out()), out().barrier(maxBarrierSize).out().barrier(maxBarrierSize), Collections.emptyList()},
- {__.<Vertex>out().times(2).repeat(out().as("a")).as("x"), out().out().as("a").barrier(maxBarrierSize).out().as("a").barrier(maxBarrierSize).as("x"), Collections.emptyList()},
+ {out().as("a").in().repeat(__.outE("created").bothV()).times(2).in(), out().as("a").in().outE("created").bothV().barrier(repeatBarrierSize).outE("created").bothV().barrier(repeatBarrierSize).in(), Collections.emptyList()},
+ {out().repeat(__.outE("created").bothV()).times(1).in(), out().outE("created").bothV().barrier(repeatBarrierSize).in(), Collections.emptyList()},
+ {__.repeat(__.outE("created").bothV()).times(1).in(), __.outE("created").bothV().barrier(repeatBarrierSize).in(), Collections.emptyList()},
+ {__.repeat(out()).times(2).as("x").repeat(__.in().as("b")).times(3), out().barrier(repeatBarrierSize).out().barrier(repeatBarrierSize).as("x").in().as("b").barrier(repeatBarrierSize).in().as("b").barrier(repeatBarrierSize).in().as("b").barrier(repeatBarrierSize), Collections.emptyList()},
+ {__.repeat(__.outE("created").inV()).times(2), __.outE("created").inV().barrier(repeatBarrierSize).outE("created").inV().barrier(repeatBarrierSize), Collections.emptyList()},
+ {__.repeat(out()).times(3), out().barrier(repeatBarrierSize).out().barrier(repeatBarrierSize).out().barrier(repeatBarrierSize), Collections.emptyList()},
+ {__.repeat(__.local(__.select("a").out("knows"))).times(2), __.local(__.select("a").out("knows")).barrier(repeatBarrierSize).local(__.select("a").out("knows")).barrier(repeatBarrierSize), Collections.emptyList()},
+ {__.<Vertex>times(2).repeat(out()), out().barrier(repeatBarrierSize).out().barrier(repeatBarrierSize), Collections.emptyList()},
+ {__.<Vertex>out().times(2).repeat(out().as("a")).as("x"), out().out().as("a").barrier(repeatBarrierSize).out().as("a").barrier(repeatBarrierSize).as("x"), Collections.emptyList()},
{__.repeat(out()).emit().times(2), __.repeat(out()).emit().times(2), Collections.emptyList()},
{__.repeat(out()).until(predicate), __.repeat(out()).until(predicate), Collections.emptyList()},
- {__.repeat(out()).until(predicate).repeat(out()).times(2), __.repeat(out()).until(predicate).out().barrier(maxBarrierSize).out().barrier(maxBarrierSize), Collections.emptyList()},
- {__.repeat(__.union(__.both(), __.identity())).times(2).out(), __.union(__.both(), __.identity()).barrier(maxBarrierSize).union(__.both(), __.identity()).barrier(maxBarrierSize).out(), Collections.emptyList()},
- {__.in().repeat(out("knows")).times(3).as("a").count().is(0), __.in().out("knows").barrier(maxBarrierSize).out("knows").barrier(maxBarrierSize).out("knows").as("a").count().is(0), Collections.emptyList()},
+ {__.repeat(out()).until(predicate).repeat(out()).times(2), __.repeat(out()).until(predicate).out().barrier(repeatBarrierSize).out().barrier(repeatBarrierSize), Collections.emptyList()},
+ {__.repeat(__.union(__.both(), __.identity())).times(2).out(), __.union(__.both(), __.identity()).barrier(repeatBarrierSize).union(__.both(), __.identity()).barrier(repeatBarrierSize).out(), Collections.emptyList()},
+ {__.in().repeat(out("knows")).times(3).as("a").count().is(0), __.in().out("knows").barrier(repeatBarrierSize).out("knows").barrier(repeatBarrierSize).out("knows").as("a").count().is(0), Collections.emptyList()},
//
- {__.repeat(__.outE().inV()).times(2), __.outE().inV().barrier(maxBarrierSize).outE().inV().barrier(maxBarrierSize), Collections.emptyList()},
- {__.repeat(__.outE().filter(path()).inV()).times(2), __.outE().filter(path()).inV().barrier(maxBarrierSize).outE().filter(path()).inV().barrier(maxBarrierSize), Collections.singletonList(IncidentToAdjacentStrategy.instance())},
- {__.repeat(__.outE().inV()).times(2), __.out().barrier(maxBarrierSize).out().barrier(maxBarrierSize), Collections.singletonList(IncidentToAdjacentStrategy.instance())},
+ {__.repeat(__.outE().inV()).times(2), __.outE().inV().barrier(repeatBarrierSize).outE().inV().barrier(repeatBarrierSize), Collections.emptyList()},
+ {__.repeat(__.outE().filter(path()).inV()).times(2), __.outE().filter(path()).inV().barrier(repeatBarrierSize).outE().filter(path()).inV().barrier(repeatBarrierSize), Collections.singletonList(IncidentToAdjacentStrategy.instance())},
+ {__.repeat(__.outE().inV()).times(2), __.out().barrier(repeatBarrierSize).out().barrier(repeatBarrierSize), Collections.singletonList(IncidentToAdjacentStrategy.instance())},
// Nested Loop tests
- {__.repeat(out().repeat(out()).times(0)).times(1), __.out().repeat(out()).times(0).barrier(maxBarrierSize), Collections.emptyList()},
- {__.repeat(out().repeat(out()).times(1)).times(1), __.out().out().barrier(maxBarrierSize), Collections.emptyList()},
+ {__.repeat(out().repeat(out()).times(0)).times(1), __.out().repeat(out()).times(0).barrier(repeatBarrierSize), Collections.emptyList()},
+ {__.repeat(out().repeat(out()).times(1)).times(1), __.out().out().barrier(repeatBarrierSize), Collections.emptyList()},
{__.repeat(out()).until(__.repeat(out()).until(predicate)), __.repeat(out()).until(__.repeat(out()).until(predicate)), Collections.emptyList()},
- {__.repeat(__.repeat(out()).times(2)).until(predicate), __.repeat(__.out().barrier(maxBarrierSize).out().barrier(maxBarrierSize)).until(predicate), Collections.emptyList()},
+ {__.repeat(__.repeat(out()).times(2)).until(predicate), __.repeat(__.out().barrier(repeatBarrierSize).out().barrier(repeatBarrierSize)).until(predicate), Collections.emptyList()},
{__.repeat(__.repeat(out("created")).until(__.has("name", "ripple"))), __.repeat(__.repeat(out("created")).until(__.has("name", "ripple"))), Collections.emptyList()},
-
});
}
}