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:13 UTC
[tinkerpop] 01/01: TINKERPOP-1994 Used LazyBarrierStrategy to
control barrier() insertion in other strategies.
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()},
-
});
}
}