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 2020/05/07 14:54:17 UTC
[tinkerpop] 01/14: Implemented `ByModulatorOptimizationStrategy`
which replaces certain standard traversals w/ optimized traversals (e.g.
`TokenTraversal`).
This is an automated email from the ASF dual-hosted git repository.
spmallette pushed a commit to branch TINKERPOP-1682
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
commit 99e52e975211073038b6e107041ede78999198f6
Author: Daniel Kuppitz <da...@hotmail.com>
AuthorDate: Thu Jun 8 15:23:08 2017 +0200
Implemented `ByModulatorOptimizationStrategy` which replaces certain standard traversals w/ optimized traversals (e.g. `TokenTraversal`).
---
CHANGELOG.asciidoc | 1 +
.../process/traversal/TraversalStrategies.java | 4 +-
.../process/traversal/step/TraversalParent.java | 4 +
.../traversal/step/filter/DedupGlobalStep.java | 6 +
.../traversal/step/filter/PathFilterStep.java | 12 ++
.../traversal/step/filter/SampleGlobalStep.java | 6 +
.../traversal/step/filter/WherePredicateStep.java | 13 +-
.../process/traversal/step/map/GroupCountStep.java | 6 +
.../process/traversal/step/map/GroupStep.java | 8 ++
.../traversal/step/map/OrderGlobalStep.java | 13 ++
.../process/traversal/step/map/OrderLocalStep.java | 13 ++
.../process/traversal/step/map/PathStep.java | 12 ++
.../process/traversal/step/map/ProjectStep.java | 12 ++
.../process/traversal/step/map/SelectOneStep.java | 6 +
.../process/traversal/step/map/SelectStep.java | 12 ++
.../process/traversal/step/map/TreeStep.java | 13 +-
.../step/sideEffect/AggregateGlobalStep.java | 6 +
.../step/sideEffect/AggregateLocalStep.java | 6 +
.../step/sideEffect/GroupCountSideEffectStep.java | 6 +
.../step/sideEffect/GroupSideEffectStep.java | 8 ++
.../traversal/step/sideEffect/SackValueStep.java | 6 +
.../step/sideEffect/TreeSideEffectStep.java | 12 ++
.../ByModulatorOptimizationStrategy.java | 110 +++++++++++++++++
.../process/traversal/util/TraversalRing.java | 4 +
.../ByModulatorOptimizationStrategyTest.java | 136 +++++++++++++++++++++
.../optimization/PathProcessorStrategyTest.java | 2 +-
.../traversal/util/TraversalExplanationTest.java | 2 +-
27 files changed, 434 insertions(+), 5 deletions(-)
diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc
index d9f7d14..cf2c8ca 100644
--- a/CHANGELOG.asciidoc
+++ b/CHANGELOG.asciidoc
@@ -1171,6 +1171,7 @@ This release also includes changes from <<release-3-2-6, 3.2.6>>.
* Graphite and Ganglia are no longer packaged with the Gremlin Server distribution.
* `TransactionException` is no longer a class of `AbstractTransaction` and it extends `RuntimeException`.
* Included an ellipse on long property names that are truncated.
+* Added `ByModulatorOptimizationStrategy` which replaces certain standard traversals w/ optimized traversals (e.g. `TokenTraversal`).
* Renamed `RangeByIsCountStrategy` to `CountStrategy`.
* Added more specific typing to various `__` traversal steps. E.g. `<A,Vertex>out()` is `<Vertex,Vertex>out()`.
* Updated Docker build scripts to include Python dependencies (NOTE: users should remove any previously generated TinkerPop Docker images).
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
index f336908..37fde8a 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java
@@ -27,6 +27,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.Prof
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.AdjacentToIncidentStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.CountStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.EarlyLimitStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.ByModulatorOptimizationStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.FilterRankingStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.InlineFilterStrategy;
@@ -228,7 +229,8 @@ public interface TraversalStrategies extends Serializable, Cloneable, Iterable<T
PathRetractionStrategy.instance(),
LazyBarrierStrategy.instance(),
ProfileStrategy.instance(),
- StandardVerificationStrategy.instance());
+ StandardVerificationStrategy.instance(),
+ ByModulatorOptimizationStrategy.instance());
GRAPH_CACHE.put(Graph.class, graphStrategies);
GRAPH_CACHE.put(EmptyGraph.class, new DefaultTraversalStrategies());
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/TraversalParent.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/TraversalParent.java
index 10df950..95a2be1 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/TraversalParent.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/TraversalParent.java
@@ -57,6 +57,10 @@ public interface TraversalParent extends AutoCloseable {
throw new IllegalStateException("This traversal parent does not support the removal of global traversals: " + this.getClass().getCanonicalName());
}
+ public default void replaceLocalChild(final Traversal.Admin<?, ?> oldTrversal, final Traversal.Admin<?, ?> newTrversal) {
+ throw new IllegalStateException("This traversal parent does not support the replacement of local traversals: " + this.getClass().getCanonicalName());
+ }
+
public default Set<TraverserRequirement> getSelfAndChildRequirements(final TraverserRequirement... selfRequirements) {
final Set<TraverserRequirement> requirements = EnumSet.noneOf(TraverserRequirement.class);
Collections.addAll(requirements, selfRequirements);
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/DedupGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/DedupGlobalStep.java
index aa154c3..bbde296 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/DedupGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/DedupGlobalStep.java
@@ -118,6 +118,12 @@ public final class DedupGlobalStep<S> extends FilterStep<S> implements Traversal
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ if (null != this.dedupTraversal && this.dedupTraversal.equals(oldTraversal))
+ this.dedupTraversal = this.integrateChild(newTraversal);
+ }
+
+ @Override
public DedupGlobalStep<S> clone() {
final DedupGlobalStep<S> clone = (DedupGlobalStep<S>) super.clone();
clone.duplicateSet = new HashSet<>();
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/PathFilterStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/PathFilterStep.java
index 16e3f0f..80355ea 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/PathFilterStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/PathFilterStep.java
@@ -109,6 +109,18 @@ public final class PathFilterStep<S> extends FilterStep<S> implements FromToModu
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ int i = 0;
+ for (final Traversal.Admin<?, ?> traversal : this.traversalRing.getTraversals()) {
+ if (null != traversal && traversal.equals(oldTraversal)) {
+ this.traversalRing.setTraversal(i, this.integrateChild(newTraversal));
+ break;
+ }
+ i++;
+ }
+ }
+
+ @Override
public void reset() {
super.reset();
this.traversalRing.reset();
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
index 28d2fb4..fe8fb03 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/SampleGlobalStep.java
@@ -60,6 +60,12 @@ public final class SampleGlobalStep<S> extends CollectingBarrierStep<S> implemen
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ if (null != this.probabilityTraversal && this.probabilityTraversal.equals(oldTraversal))
+ this.probabilityTraversal = this.integrateChild(newTraversal);
+ }
+
+ @Override
public String toString() {
return StringFactory.stepString(this, this.amountToSample, this.probabilityTraversal);
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java
index 62a88f4..1ddcfe1 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java
@@ -28,7 +28,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.Scoping;
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.ConnectiveP;
-import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalRing;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalUtil;
import org.apache.tinkerpop.gremlin.structure.util.StringFactory;
@@ -164,4 +163,16 @@ public final class WherePredicateStep<S> extends FilterStep<S> implements Scopin
public void modulateBy(final Traversal.Admin<?, ?> traversal) throws UnsupportedOperationException {
this.traversalRing.addTraversal(this.integrateChild(traversal));
}
+
+ @Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ int i = 0;
+ for (final Traversal.Admin<?, ?> traversal : this.traversalRing.getTraversals()) {
+ if (null != traversal && traversal.equals(oldTraversal)) {
+ this.traversalRing.setTraversal(i, this.integrateChild(newTraversal));
+ break;
+ }
+ i++;
+ }
+ }
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupCountStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupCountStep.java
index a0c02fd..e679240 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupCountStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupCountStep.java
@@ -79,6 +79,12 @@ public final class GroupCountStep<S, E> extends ReducingBarrierStep<S, Map<E, Lo
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ if (null != this.keyTraversal && this.keyTraversal.equals(oldTraversal))
+ this.keyTraversal = this.integrateChild(newTraversal);
+ }
+
+ @Override
public GroupCountStep<S, E> clone() {
final GroupCountStep<S, E> clone = (GroupCountStep<S, E>) super.clone();
if (null != this.keyTraversal)
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupStep.java
index 4bb06f0..66c9653 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroupStep.java
@@ -119,6 +119,14 @@ public final class GroupStep<S, K, V> extends ReducingBarrierStep<S, Map<K, V>>
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ if (null != this.keyTraversal && this.keyTraversal.equals(oldTraversal))
+ this.keyTraversal = this.integrateChild(newTraversal);
+ else if (null != this.valueTraversal && this.valueTraversal.equals(oldTraversal))
+ this.valueTraversal = this.integrateChild(newTraversal);
+ }
+
+ @Override
public Map<K, V> projectTraverser(final Traverser.Admin<S> traverser) {
final Map<K, V> map = new HashMap<>(1);
this.valueTraversal.reset();
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
index fa80e97..3b227b1 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderGlobalStep.java
@@ -99,6 +99,19 @@ public final class OrderGlobalStep<S, C extends Comparable> extends CollectingBa
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ int i = 0;
+ for (final Pair<Traversal.Admin<S, C>, Comparator<C>> pair : this.comparators) {
+ final Traversal.Admin<S, C> traversal = pair.getValue0();
+ if (null != traversal && traversal.equals(oldTraversal)) {
+ this.comparators.set(i, Pair.with(this.integrateChild(newTraversal), pair.getValue1()));
+ break;
+ }
+ i++;
+ }
+ }
+
+ @Override
public List<Pair<Traversal.Admin<S, C>, Comparator<C>>> getComparators() {
return this.comparators.isEmpty() ? Collections.singletonList(new Pair<>(new IdentityTraversal(), (Comparator) Order.asc)) : Collections.unmodifiableList(this.comparators);
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
index 97a68ff..6597418 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/OrderLocalStep.java
@@ -81,6 +81,19 @@ public final class OrderLocalStep<S, C extends Comparable> extends ScalarMapStep
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ int i = 0;
+ for (final Pair<Traversal.Admin<S, C>, Comparator<C>> pair : this.comparators) {
+ final Traversal.Admin<S, C> traversal = pair.getValue0();
+ if (null != traversal && traversal.equals(oldTraversal)) {
+ this.comparators.set(i, Pair.with(this.integrateChild(newTraversal), pair.getValue1()));
+ break;
+ }
+ i++;
+ }
+ }
+
+ @Override
public List<Pair<Traversal.Admin<S, C>, Comparator<C>>> getComparators() {
return this.comparators.isEmpty() ? Collections.singletonList(new Pair<>(new IdentityTraversal(), (Comparator) Order.asc)) : Collections.unmodifiableList(this.comparators);
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PathStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PathStep.java
index 82f19b4..d5a5337 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PathStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PathStep.java
@@ -99,6 +99,18 @@ public final class PathStep<S> extends ScalarMapStep<S, Path> implements Travers
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ int i = 0;
+ for (final Traversal.Admin<?, ?> traversal : this.traversalRing.getTraversals()) {
+ if (null != traversal && traversal.equals(oldTraversal)) {
+ this.traversalRing.setTraversal(i, this.integrateChild(newTraversal));
+ break;
+ }
+ i++;
+ }
+ }
+
+ @Override
public String toString() {
return StringFactory.stepString(this, this.traversalRing);
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ProjectStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ProjectStep.java
index 66c63e0..718c99c 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ProjectStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/ProjectStep.java
@@ -97,6 +97,18 @@ public final class ProjectStep<S, E> extends ScalarMapStep<S, Map<String, E>> im
this.traversalRing.addTraversal(this.integrateChild(selectTraversal));
}
+ @Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ int i = 0;
+ for (final Traversal.Admin<?, ?> traversal : this.traversalRing.getTraversals()) {
+ if (null != traversal && traversal.equals(oldTraversal)) {
+ this.traversalRing.setTraversal(i, this.integrateChild(newTraversal));
+ break;
+ }
+ i++;
+ }
+ }
+
public List<String> getProjectKeys() {
return this.projectKeys;
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java
index 1f3ebdc..976c512 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java
@@ -114,6 +114,12 @@ public final class SelectOneStep<S, E> extends MapStep<S, E> implements Traversa
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ if (null != this.selectTraversal && this.selectTraversal.equals(oldTraversal))
+ this.selectTraversal = this.integrateChild(newTraversal);
+ }
+
+ @Override
public Set<TraverserRequirement> getRequirements() {
return this.getSelfAndChildRequirements(TraverserRequirement.OBJECT, TraverserRequirement.SIDE_EFFECTS);
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java
index 5034c84..4e1d01d 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java
@@ -123,6 +123,18 @@ public final class SelectStep<S, E> extends MapStep<S, Map<String, E>> implement
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ int i = 0;
+ for (final Traversal.Admin<?, ?> traversal : this.traversalRing.getTraversals()) {
+ if (null != traversal && traversal.equals(oldTraversal)) {
+ this.traversalRing.setTraversal(i, this.integrateChild(newTraversal));
+ break;
+ }
+ i++;
+ }
+ }
+
+ @Override
public Set<TraverserRequirement> getRequirements() {
return this.getSelfAndChildRequirements(TraverserRequirement.OBJECT, TraverserRequirement.SIDE_EFFECTS);
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java
index 41310aa..a6c65a7 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java
@@ -64,6 +64,18 @@ public final class TreeStep<S> extends ReducingBarrierStep<S, Tree> implements T
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ int i = 0;
+ for (final Traversal.Admin<?, ?> traversal : this.traversalRing.getTraversals()) {
+ if (null != traversal && traversal.equals(oldTraversal)) {
+ this.traversalRing.setTraversal(i, this.integrateChild(newTraversal));
+ break;
+ }
+ i++;
+ }
+ }
+
+ @Override
public Set<TraverserRequirement> getRequirements() {
return this.getSelfAndChildRequirements(TraverserRequirement.PATH, TraverserRequirement.SIDE_EFFECTS);
}
@@ -83,7 +95,6 @@ public final class TreeStep<S> extends ReducingBarrierStep<S, Tree> implements T
return topTree;
}
-
@Override
public TreeStep<S> clone() {
final TreeStep<S> clone = (TreeStep<S>) super.clone();
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AggregateGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AggregateGlobalStep.java
index c0e18b0..2419132 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AggregateGlobalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AggregateGlobalStep.java
@@ -72,6 +72,12 @@ public final class AggregateGlobalStep<S> extends AbstractStep<S, S> implements
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ if (null != this.aggregateTraversal && this.aggregateTraversal.equals(oldTraversal))
+ this.aggregateTraversal = this.integrateChild(newTraversal);
+ }
+
+ @Override
public List<Traversal.Admin<S, Object>> getLocalChildren() {
return null == this.aggregateTraversal ? Collections.emptyList() : Collections.singletonList(this.aggregateTraversal);
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AggregateLocalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AggregateLocalStep.java
index cd1fa07..3c7c0fa 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AggregateLocalStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/AggregateLocalStep.java
@@ -78,6 +78,12 @@ public final class AggregateLocalStep<S> extends SideEffectStep<S> implements Si
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ if (null != this.storeTraversal && this.storeTraversal.equals(oldTraversal))
+ this.storeTraversal = this.integrateChild(newTraversal);
+ }
+
+ @Override
public Set<TraverserRequirement> getRequirements() {
return this.getSelfAndChildRequirements(TraverserRequirement.SIDE_EFFECTS, TraverserRequirement.BULK);
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupCountSideEffectStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupCountSideEffectStep.java
index 88a1cb7..41ddeef 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupCountSideEffectStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupCountSideEffectStep.java
@@ -106,4 +106,10 @@ public final class GroupCountSideEffectStep<S, E> extends SideEffectStep<S> impl
public void modulateBy(final Traversal.Admin<?, ?> keyTraversal) throws UnsupportedOperationException {
this.keyTraversal = this.integrateChild(keyTraversal);
}
+
+ @Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ if (null != this.keyTraversal && this.keyTraversal.equals(oldTraversal))
+ this.keyTraversal = this.integrateChild(newTraversal);
+ }
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupSideEffectStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupSideEffectStep.java
index fd31bc3..7eb6659 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupSideEffectStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/GroupSideEffectStep.java
@@ -93,6 +93,14 @@ public final class GroupSideEffectStep<S, K, V> extends SideEffectStep<S> implem
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ if (null != this.keyTraversal && this.keyTraversal.equals(oldTraversal))
+ this.keyTraversal = this.integrateChild(newTraversal);
+ else if (null != this.valueTraversal && this.valueTraversal.equals(oldTraversal))
+ this.valueTraversal = this.integrateChild(newTraversal);
+ }
+
+ @Override
protected void sideEffect(final Traverser.Admin<S> traverser) {
final Map<K, V> map = new HashMap<>(1);
this.valueTraversal.reset();
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/SackValueStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/SackValueStep.java
index 650140e..bd0e828 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/SackValueStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/SackValueStep.java
@@ -52,6 +52,12 @@ public final class SackValueStep<S, A, B> extends SideEffectStep<S> implements T
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ if (null != this.sackTraversal && this.sackTraversal.equals(oldTraversal))
+ this.sackTraversal = this.integrateChild(newTraversal);
+ }
+
+ @Override
public List<Traversal.Admin<S, B>> getLocalChildren() {
return null == this.sackTraversal ? Collections.emptyList() : Collections.singletonList(this.sackTraversal);
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java
index 2d43ddc..d07ebee 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java
@@ -119,6 +119,18 @@ public final class TreeSideEffectStep<S> extends SideEffectStep<S> implements Si
}
@Override
+ public void replaceLocalChild(final Traversal.Admin<?, ?> oldTraversal, final Traversal.Admin<?, ?> newTraversal) {
+ int i = 0;
+ for (final Traversal.Admin<?, ?> traversal : this.traversalRing.getTraversals()) {
+ if (null != traversal && traversal.equals(oldTraversal)) {
+ this.traversalRing.setTraversal(i, this.integrateChild(newTraversal));
+ break;
+ }
+ i++;
+ }
+ }
+
+ @Override
public Set<TraverserRequirement> getRequirements() {
return this.getSelfAndChildRequirements(TraverserRequirement.PATH, TraverserRequirement.SIDE_EFFECTS);
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategy.java
new file mode 100644
index 0000000..8202ca2
--- /dev/null
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategy.java
@@ -0,0 +1,110 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.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.ElementValueTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.IdentityTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.lambda.TokenTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.step.ByModulating;
+import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.IdStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.LabelStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertiesStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.IdentityStep;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
+import org.apache.tinkerpop.gremlin.structure.PropertyType;
+import org.apache.tinkerpop.gremlin.structure.T;
+
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+/**
+ * This strategy looks for standard traversals in by-modulators and replaces them with more optimized traversals
+ * (e.g. {@code TokenTraversal}) if possible.
+ * <p/>
+ *
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ * @example <pre>
+ * __.path().by(id()) // is replaced by __.path().by(id)
+ * __.dedup().by(label()) // is replaced by __.dedup().by(label)
+ * __.group().by(key()) // is replaced by __.group().by(key)
+ * __.group().by(value()) // is replaced by __.group().by(value)
+ * __.order().by(values("name")) // is replaced by __.order().by("name")
+ * </pre>
+ */
+public final class ByModulatorOptimizationStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy>
+ implements TraversalStrategy.OptimizationStrategy {
+
+ private static final ByModulatorOptimizationStrategy INSTANCE = new ByModulatorOptimizationStrategy();
+ private static final Set<Class<? extends OptimizationStrategy>> PRIORS = new HashSet<>(Collections.singletonList(IdentityRemovalStrategy.class));
+
+ private ByModulatorOptimizationStrategy() {
+ }
+
+ public static ByModulatorOptimizationStrategy instance() {
+ return INSTANCE;
+ }
+
+ private void optimizeByModulatingTraversal(final TraversalParent step, final Traversal.Admin<?, ?> traversal) {
+ if (traversal == null) return;
+ final List<Step> steps = traversal.asAdmin().getSteps();
+ if (steps.size() == 1) {
+ final Step singleStep = steps.get(0);
+ if (singleStep instanceof PropertiesStep) {
+ final PropertiesStep ps = (PropertiesStep) singleStep;
+ if (ps.getReturnType().equals(PropertyType.VALUE) && ps.getPropertyKeys().length == 1) {
+ step.replaceLocalChild(traversal, new ElementValueTraversal<>(ps.getPropertyKeys()[0]));
+ }
+ } else if (singleStep instanceof IdStep) {
+ step.replaceLocalChild(traversal, new TokenTraversal<>(T.id));
+ } else if (singleStep instanceof LabelStep) {
+ step.replaceLocalChild(traversal, new TokenTraversal<>(T.label));
+/* todo: this fails for `Property`s (e.g. outE().property().as("a").select("a").by(key/value))
+ } else if (singleStep instanceof PropertyKeyStep) {
+ step.setModulateByTraversal(n, new TokenTraversal<>(T.key));
+ } else if (singleStep instanceof PropertyValueStep) {
+ step.setModulateByTraversal(n, new TokenTraversal<>(T.value));
+*/
+ } else if (singleStep instanceof IdentityStep) {
+ step.replaceLocalChild(traversal, new IdentityTraversal<>());
+ }
+ }
+ }
+
+ @Override
+ public void apply(final Traversal.Admin<?, ?> traversal) {
+ final Step step = traversal.getParent().asStep();
+ if (step instanceof ByModulating && step instanceof TraversalParent) {
+ final TraversalParent byModulatingStep = (TraversalParent) step;
+ for (final Traversal.Admin<?, ?> byModulatingTraversal : byModulatingStep.getLocalChildren()) {
+ optimizeByModulatingTraversal(byModulatingStep, byModulatingTraversal);
+ }
+ }
+ }
+
+ @Override
+ public Set<Class<? extends OptimizationStrategy>> applyPrior() {
+ return PRIORS;
+ }
+}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalRing.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalRing.java
index 09c362e..a3d6972 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalRing.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalRing.java
@@ -62,6 +62,10 @@ public final class TraversalRing<A, B> implements Serializable, Cloneable {
this.traversals.add(traversal);
}
+ public void setTraversal(final int index, final Traversal.Admin<A, B> traversal) {
+ this.traversals.set(index, traversal);
+ }
+
public List<Traversal.Admin<A, B>> getTraversals() {
return Collections.unmodifiableList(this.traversals);
}
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategyTest.java
new file mode 100644
index 0000000..d681447
--- /dev/null
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/ByModulatorOptimizationStrategyTest.java
@@ -0,0 +1,136 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization;
+
+import org.apache.tinkerpop.gremlin.process.traversal.P;
+import org.apache.tinkerpop.gremlin.process.traversal.Scope;
+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.GraphTraversal;
+import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
+import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
+import org.apache.tinkerpop.gremlin.structure.T;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import static org.apache.tinkerpop.gremlin.process.traversal.Operator.assign;
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author Daniel Kuppitz (http://gremlin.guru)
+ */
+@RunWith(Parameterized.class)
+public class ByModulatorOptimizationStrategyTest {
+
+ @Parameterized.Parameter
+ public Traversal original;
+
+ @Parameterized.Parameter(value = 1)
+ public Traversal optimized;
+
+ @Parameterized.Parameters(name = "{0}")
+ public static Iterable<Object[]> generateTestParameters() {
+
+ final List<Object[]> result = new ArrayList<>();
+ final GraphTraversal[] baseTraversals = new GraphTraversal[]{
+ __.aggregate("x"),
+ __.dedup(),
+ __.dedup("a"),
+ __.group(),
+ __.group("x"),
+ __.groupCount(),
+ __.groupCount("x"),
+ __.order(),
+ __.order(Scope.local),
+ __.project("a"),
+ __.path(),
+ __.path().from("a").to("b"),
+ __.sack(assign),
+ __.sample(10),
+ __.select("a"),
+ __.select("a", "b"),
+ __.store("x"),
+ __.tree(),
+ __.tree("x"),
+ __.where(P.eq("a")),
+ __.where("a", P.eq("b"))
+ };
+
+ for (final Traversal traversal : baseTraversals) {
+ result.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.values("name")),
+ ((GraphTraversal) traversal.asAdmin().clone()).by("name"),
+ });
+ result.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.id()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by(T.id),
+ });
+ result.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.label()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by(T.label),
+ });
+ /*result.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.key()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by(T.key),
+ });
+ result.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.value()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by(T.value),
+ });*/
+ result.add(new Traversal[]{
+ ((GraphTraversal<?, ?>) traversal.asAdmin().clone()).by(__.identity()),
+ ((GraphTraversal) traversal.asAdmin().clone()).by(),
+ });
+ }
+
+ result.add(new Traversal[]{
+ __.project("a", "b", "c", "d", "e")
+ .by(__.values("name"))
+ .by(__.id())
+ .by(__.label())
+ .by(__.identity())
+ .by(__.outE().count()),
+ __.project("a", "b", "c", "d", "e")
+ .by("name")
+ .by(T.id)
+ .by(T.label)
+ .by()
+ .by(__.outE().count())
+ });
+
+ return result;
+ }
+
+ private void applyByModulatorOptimizationStrategy(final Traversal traversal) {
+ final TraversalStrategies strategies = new DefaultTraversalStrategies();
+ strategies.addStrategies(ByModulatorOptimizationStrategy.instance());
+ traversal.asAdmin().setStrategies(strategies);
+ traversal.asAdmin().applyStrategies();
+ }
+
+ @Test
+ public void doTest() {
+ applyByModulatorOptimizationStrategy(original);
+ assertEquals(optimized, original);
+ }
+}
\ No newline at end of file
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategyTest.java
index 02635ab..ec0b89c 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategyTest.java
@@ -84,7 +84,7 @@ public class PathProcessorStrategyTest {
{__.select("a").by(__.outE().count()), __.select("a").map(__.outE().count()), Collections.emptyList()},
{__.select("a").by("name"), __.select("a").map(new ValueTraversal<>("name")), Collections.emptyList()},
{__.select("a").out(), __.select("a").out(), Collections.emptyList()},
- {__.select(Pop.all, "a").by(__.values("name")), __.select(Pop.all, "a").by(__.values("name")), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
+ {__.select(Pop.all, "a").by(__.values("name")), __.select(Pop.all, "a").by("name"), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
{__.select(Pop.last, "a").by(__.values("name")), __.select(Pop.last, "a").map(__.values("name")), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
{__.select(Pop.first, "a").by(__.values("name")), __.select(Pop.first, "a").map(__.values("name")), TraversalStrategies.GlobalCache.getStrategies(Graph.class).toList()},
// select("a","b")
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalExplanationTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalExplanationTest.java
index 0a81238..f51b386 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalExplanationTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalExplanationTest.java
@@ -131,7 +131,7 @@ public class TraversalExplanationTest {
assertEquals(4, found);
//
found = 0;
- for (final String line : traversal.explain().prettyPrint(158).split("]\n")) { // need to split cause of word wrap
+ for (final String line : traversal.explain().prettyPrint(160).split("]\n")) { // need to split cause of word wrap
if (line.contains("IncidentToAdjacentStrategy") && line.contains("[VertexStep(IN,vertex)"))
found++;
if (line.contains("IncidentToAdjacentStrategy") && line.contains("[VertexStep(OUT,vertex)"))