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 2025/09/11 13:03:16 UTC
(tinkerpop) 01/01: GValueReductionStrategy moved from finalization to optimization
This is an automated email from the ASF dual-hosted git repository.
spmallette pushed a commit to branch gvalue-spmfixup
in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
commit b617d4f4990cda1a7df0c012bcabd0b7d8b5d8a3
Author: Stephen Mallette <st...@amazon.com>
AuthorDate: Wed Sep 10 13:45:40 2025 -0400
GValueReductionStrategy moved from finalization to optimization
This change lets provider strategies remain unchanged by producing concrete steps prior to provider optimization strategies.
---
docs/src/upgrade/release-3.8.x.asciidoc | 2 +-
.../process/traversal/TraversalStrategies.java | 5 +-
.../process/traversal/TraversalStrategy.java | 14 ++
.../process/traversal/step/HasContainerHolder.java | 4 +-
.../traversal/step/map/AddEdgeStepContract.java | 10 +
.../traversal/step/map/AddEdgeStepPlaceholder.java | 13 ++
.../traversal/step/map/GraphStepContract.java | 11 +
.../GValueReductionStrategy.java | 29 ++-
.../optimization/IncidentToAdjacentStrategy.java | 4 +-
.../optimization/InlineFilterStrategy.java | 4 +-
.../optimization/MatchPredicateStrategy.java | 4 +-
.../optimization/PathProcessorStrategy.java | 22 +-
.../ProviderGValueReductionStrategy.java} | 26 ++-
.../process/traversal/util/ConnectiveP.java | 5 +-
.../process/traversal/util/PureTraversal.java | 2 +-
.../process/traversal/util/TraversalHelper.java | 257 ++++++++++++++++++++-
.../gremlin/process/traversal/ConnectiveTest.java | 63 +++++
.../optimization/EarlyLimitStrategyTest.java | 1 -
.../traversal/util/TraversalHelperTest.java | 118 ++++++----
.../TinkerGraphGremlinLangScriptEngineTest.java | 10 +-
.../process/TinkerGraphNoStrategyProvider.java | 2 +-
21 files changed, 510 insertions(+), 96 deletions(-)
diff --git a/docs/src/upgrade/release-3.8.x.asciidoc b/docs/src/upgrade/release-3.8.x.asciidoc
index 3adaf7b310..2621a2153f 100644
--- a/docs/src/upgrade/release-3.8.x.asciidoc
+++ b/docs/src/upgrade/release-3.8.x.asciidoc
@@ -831,7 +831,7 @@ capabilities by persisting query parameters further in the traversal lifecycle.
are constructed into GValues and passed into `GraphTraversal`. The traversal is then populated with special
`GValueHolder` placeholder steps, which are temporary non-executable steps which implement a corresponding step
interface. TraversalStrategies are able to operate on these placeholder steps and update the traversal as normal. By
-default, there is a new `FinalizationStrategy`, `GValueReductionStrategy` which cleans up the traversal by reducing all
+default, there is a new `OptimizationStrategy`, `GValueReductionStrategy` which cleans up the traversal by reducing all
`GValueHolder` steps with their corresponding concrete step object. Providers may choose disable this strategy in order
to store a fully constructed and optimized traversal with parameters into a query cache.
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 5508c083a7..cb70213eba 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
@@ -31,10 +31,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.EventS
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.HaltedTraverserStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.OptionsStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.PartitionStrategy;
-import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SackStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SeedStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SubgraphStrategy;
-import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.GValueReductionStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.MatchAlgorithmStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ProfileStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ReferenceElementStrategy;
@@ -43,6 +41,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.Coun
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.GValueReductionStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IdentityRemovalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.InlineFilterStrategy;
@@ -255,9 +254,9 @@ public interface TraversalStrategies extends Serializable, Cloneable, Iterable<T
// finalization
put(MatchAlgorithmStrategy.class.getSimpleName(), MatchAlgorithmStrategy.class);
put(ReferenceElementStrategy.class.getSimpleName(), ReferenceElementStrategy.class);
- put(GValueReductionStrategy.class.getSimpleName(), GValueReductionStrategy.class);
// optimizations
+ put(GValueReductionStrategy.class.getSimpleName(), GValueReductionStrategy.class);
put(ProductiveByStrategy.class.getSimpleName(), ProductiveByStrategy.class);
put(PathRetractionStrategy.class.getSimpleName(), PathRetractionStrategy.class);
put(RepeatUnrollStrategy.class.getSimpleName(), RepeatUnrollStrategy.class);
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategy.java
index 530bf411fb..5434bc0fc1 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategy.java
@@ -25,11 +25,13 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.Partit
import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ProfileStrategy;
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.GValueReductionStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.verification.LambdaRestrictionStrategy;
import org.apache.tinkerpop.gremlin.util.GremlinDisabledListDelimiterHandler;
import java.io.Serializable;
import java.util.Collections;
+import java.util.HashSet;
import java.util.Set;
/**
@@ -167,6 +169,18 @@ public interface TraversalStrategy<S extends TraversalStrategy> extends Serializ
else
return 0;
}
+
+ /**
+ * The {@link GValueReductionStrategy} should be the last TinkerPop optimnization strategy applied. Adding it
+ * here ensures will help to enforce that more globally. Implementations overriding this method should have a
+ * good reason to ignore this.
+ */
+ @Override
+ default Set<Class<? extends OptimizationStrategy>> applyPost() {
+ final Set<Class<? extends OptimizationStrategy>> set = new HashSet<>();
+ set.add(GValueReductionStrategy.class);
+ return set;
+ }
}
/**
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/HasContainerHolder.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/HasContainerHolder.java
index 330ee84f4e..03a5d92bb6 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/HasContainerHolder.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/HasContainerHolder.java
@@ -63,9 +63,7 @@ public interface HasContainerHolder<S, E> extends GValueHolder<S, E> {
}
public default void updateVariable(final String name, final Object value) {
- getPredicates().forEach((p) -> {
- p.updateVariable(name, value);
- });
+ getPredicates().forEach((p) -> p.updateVariable(name, value));
}
public default Collection<GValue<?>> getGValues() {
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepContract.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepContract.java
index 13ec8d493a..238462146a 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepContract.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepContract.java
@@ -18,8 +18,12 @@
*/
package org.apache.tinkerpop.gremlin.process.traversal.step.map;
+import java.util.Arrays;
+import java.util.Collections;
import java.util.List;
import java.util.function.Consumer;
+
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.lambda.ConstantTraversal;
@@ -36,6 +40,12 @@ import org.apache.tinkerpop.gremlin.structure.Vertex;
import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceVertex;
public interface AddEdgeStepContract<S> extends TraversalParent, Scoping, FromToModulating, AddElementStepContract<S, Edge>, Writing<Event.EdgeAddedEvent> {
+
+ /**
+ * Concrete implementations of this contract that can be referenced as TinkerPop implementations.
+ */
+ List<Class<? extends Step>> CONCRETE_STEPS = Collections.unmodifiableList(Arrays.asList(AddEdgeStep.class, AddEdgeStepPlaceholder.class));
+
Object getFrom();
Object getTo();
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepPlaceholder.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepPlaceholder.java
index c008b8cbab..78bd735258 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepPlaceholder.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/AddEdgeStepPlaceholder.java
@@ -18,7 +18,10 @@
*/
package org.apache.tinkerpop.gremlin.process.traversal.step.map;
+import java.util.ArrayList;
import java.util.Collection;
+import java.util.List;
+
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.lambda.ConstantTraversal;
import org.apache.tinkerpop.gremlin.process.traversal.lambda.GValueConstantTraversal;
@@ -52,6 +55,7 @@ public class AddEdgeStepPlaceholder<S> extends AbstractAddElementStepPlaceholder
traversal.getGValueManager().register(((GValueConstantTraversal<?, ?>) toObject).getGValue());
}
this.to = toObject;
+ this.integrateChild(this.to);
}
@Override
@@ -61,6 +65,15 @@ public class AddEdgeStepPlaceholder<S> extends AbstractAddElementStepPlaceholder
traversal.getGValueManager().register(((GValueConstantTraversal<?, ?>) fromObject).getGValue());
}
this.from = fromObject;
+ this.integrateChild(this.from);
+ }
+
+ @Override
+ public List<Traversal.Admin<S, Edge>> getLocalChildren() {
+ final List<Traversal.Admin<S, Edge>> childTraversals = super.getLocalChildren();
+ if (from != null) childTraversals.add((Traversal.Admin) from);
+ if (to != null) childTraversals.add((Traversal.Admin) to);
+ return childTraversals;
}
@Override
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GraphStepContract.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GraphStepContract.java
index bbc9ae75e3..a236a20262 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GraphStepContract.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/GraphStepContract.java
@@ -19,11 +19,22 @@
package org.apache.tinkerpop.gremlin.process.traversal.step.map;
import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.step.GraphComputing;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.AbstractStep;
import org.apache.tinkerpop.gremlin.structure.Element;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+
public interface GraphStepContract<S, E extends Element> extends Step<S, E>, GraphComputing {
+ /**
+ * Concrete implementations of this contract that can be referenced as TinkerPop implementations.
+ */
+ List<Class<? extends Step>> CONCRETE_STEPS = Collections.unmodifiableList(Arrays.asList(GraphStep.class, GraphStepPlaceholder.class));
+
Class<E> getReturnClass();
boolean isStartStep();
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/finalization/GValueReductionStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/GValueReductionStrategy.java
similarity index 55%
copy from gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/finalization/GValueReductionStrategy.java
copy to gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/GValueReductionStrategy.java
index 6b775d56bf..2f2888931a 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/finalization/GValueReductionStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/GValueReductionStrategy.java
@@ -16,18 +16,33 @@
* specific language governing permissions and limitations
* under the License.
*/
-package org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization;
+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.step.GValue;
import org.apache.tinkerpop.gremlin.process.traversal.step.GValueHolder;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.provider.ProviderGValueReductionStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import java.util.Collections;
import java.util.List;
+import java.util.Set;
-public final class GValueReductionStrategy extends AbstractTraversalStrategy<TraversalStrategy.FinalizationStrategy> implements TraversalStrategy.FinalizationStrategy {
+/**
+ * Converts placeholder steps that hold {@link GValue} objects to their concrete implementations. While not an
+ * optimization in and of itself, the {@link GValue} functionality in general, provides a mechanism for traversal
+ * optimization so falls in this category. In addition, converting to concrete steps at this stage also allows provider
+ * optimization strategies to execute on concrete steps, rather than step interfaces. Concrete steps are much easier to
+ * reason about and keep strategy application simple for the vast majority of providers.
+ * <p/>
+ * Providers hoping to do more advanced optimizations that require {@link GValue} objects to be present for their
+ * strategies will need to remove {@link GValueReductionStrategy} and offer their own mechanism for converting step
+ * placeholders to concrete steps. {@link ProviderGValueReductionStrategy} is a base class for helping with this need.
+ */
+public final class GValueReductionStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> implements TraversalStrategy.OptimizationStrategy {
private static final GValueReductionStrategy INSTANCE = new GValueReductionStrategy();
@@ -50,5 +65,13 @@ public final class GValueReductionStrategy extends AbstractTraversalStrategy<Tra
return INSTANCE;
}
-
+ /**
+ * No TinkerPop optimization strategy should be applied following this one. The default implementation adds
+ * {@link GValueReductionStrategy} itself so retaining that implementation would create a circular reference so
+ * returning an empty list here removes that dependency.
+ */
+ @Override
+ public Set<Class<? extends OptimizationStrategy>> applyPost() {
+ return Collections.emptySet();
+ }
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java
index e7ec18bc5a..60ef91327b 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java
@@ -160,6 +160,8 @@ public final class IncidentToAdjacentStrategy extends AbstractTraversalStrategy<
@Override
public Set<Class<? extends OptimizationStrategy>> applyPost() {
- return Collections.singleton(PathRetractionStrategy.class);
+ final Set<Class<? extends OptimizationStrategy>> post = OptimizationStrategy.super.applyPost();
+ post.add(PathRetractionStrategy.class);
+ return post;
}
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
index eaff3c86fa..3dc679bcdd 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
@@ -311,7 +311,9 @@ public final class InlineFilterStrategy extends AbstractTraversalStrategy<Traver
@Override
public Set<Class<? extends OptimizationStrategy>> applyPost() {
- return POSTS;
+ final Set<Class<? extends OptimizationStrategy>> post = OptimizationStrategy.super.applyPost();
+ post.addAll(POSTS);
+ return post;
}
@Override
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchPredicateStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchPredicateStrategy.java
index c5652ceccd..25a7a7c8ac 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchPredicateStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/MatchPredicateStrategy.java
@@ -101,6 +101,8 @@ public final class MatchPredicateStrategy extends AbstractTraversalStrategy<Trav
@Override
public Set<Class<? extends OptimizationStrategy>> applyPost() {
- return POSTS;
+ final Set<Class<? extends OptimizationStrategy>> post = OptimizationStrategy.super.applyPost();
+ post.addAll(POSTS);
+ return post;
}
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategy.java
index dc1fd53771..25b43b1742 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategy.java
@@ -76,16 +76,6 @@ public final class PathProcessorStrategy extends AbstractTraversalStrategy<Trave
private PathProcessorStrategy() {
}
- @Override
- public Set<Class<? extends OptimizationStrategy>> applyPrior() {
- return Collections.singleton(MatchPredicateStrategy.class);
- }
-
- @Override
- public Set<Class<? extends OptimizationStrategy>> applyPost() {
- return Collections.singleton(InlineFilterStrategy.class);
- }
-
@Override
public void apply(final Traversal.Admin<?, ?> traversal) {
// using a hidden label marker to denote whether the traversal should not be processed by this strategy
@@ -187,6 +177,18 @@ public final class PathProcessorStrategy extends AbstractTraversalStrategy<Trave
}
}
+ @Override
+ public Set<Class<? extends OptimizationStrategy>> applyPrior() {
+ return Collections.singleton(MatchPredicateStrategy.class);
+ }
+
+ @Override
+ public Set<Class<? extends OptimizationStrategy>> applyPost() {
+ final Set<Class<? extends OptimizationStrategy>> post = OptimizationStrategy.super.applyPost();
+ post.add(InlineFilterStrategy.class);
+ return post;
+ }
+
public static PathProcessorStrategy instance() {
return INSTANCE;
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/finalization/GValueReductionStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/provider/ProviderGValueReductionStrategy.java
similarity index 57%
rename from gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/finalization/GValueReductionStrategy.java
rename to gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/provider/ProviderGValueReductionStrategy.java
index 6b775d56bf..3d2e178964 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/finalization/GValueReductionStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/provider/ProviderGValueReductionStrategy.java
@@ -16,22 +16,36 @@
* specific language governing permissions and limitations
* under the License.
*/
-package org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization;
+package org.apache.tinkerpop.gremlin.process.traversal.strategy.provider;
import org.apache.tinkerpop.gremlin.process.traversal.Step;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.step.GValue;
import org.apache.tinkerpop.gremlin.process.traversal.step.GValueHolder;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
+import java.util.Collections;
import java.util.List;
+import java.util.Set;
-public final class GValueReductionStrategy extends AbstractTraversalStrategy<TraversalStrategy.FinalizationStrategy> implements TraversalStrategy.FinalizationStrategy {
+/**
+ * Converts placeholder steps that hold {@link GValue} objects to their concrete implementations. While not an
+ * optimization in and of itself, the {@link GValue} functionality in general, provides a mechanism for traversal
+ * optimization so falls in this category. In addition, converting to concrete steps at this stage also allows provider
+ * optimization strategies to execute on concrete steps, rather than step interfaces. Concrete steps are much easier to
+ * reason about and keep strategy application simple for the vast majority of providers.
+ * <p/>
+ * Providers hoping to do more advanced optimizations that require {@link GValue} objects to be present for their
+ * strategies will need to remove {@link ProviderGValueReductionStrategy} and offer their own mechanism for converting step
+ * placeholders to concrete steps.
+ */
+public class ProviderGValueReductionStrategy extends AbstractTraversalStrategy<TraversalStrategy.ProviderOptimizationStrategy> implements TraversalStrategy.ProviderOptimizationStrategy {
- private static final GValueReductionStrategy INSTANCE = new GValueReductionStrategy();
+ private static final ProviderGValueReductionStrategy INSTANCE = new ProviderGValueReductionStrategy();
- private GValueReductionStrategy() {}
+ private ProviderGValueReductionStrategy() {}
@Override
public void apply(final Traversal.Admin<?, ?> traversal) {
@@ -46,9 +60,7 @@ public final class GValueReductionStrategy extends AbstractTraversalStrategy<Tra
}, traversal);
}
- public static GValueReductionStrategy instance() {
+ public static ProviderGValueReductionStrategy instance() {
return INSTANCE;
}
-
-
}
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/ConnectiveP.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/ConnectiveP.java
index 6977c284b0..ea1c925861 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/ConnectiveP.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/ConnectiveP.java
@@ -123,10 +123,7 @@ public abstract class ConnectiveP<V> extends P<V> {
@Override
public void updateVariable(final String name, final Object value) {
- predicates.stream().map((p) -> {
- p.updateVariable(name, value);
- return p;
- });
+ predicates.stream().forEach((p) -> p.updateVariable(name, value));
}
@Override
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PureTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PureTraversal.java
index 5102d56b44..e67f1e971a 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PureTraversal.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PureTraversal.java
@@ -22,7 +22,7 @@ package org.apache.tinkerpop.gremlin.process.traversal.util;
import org.apache.commons.configuration2.Configuration;
import org.apache.tinkerpop.gremlin.process.computer.util.VertexProgramHelper;
import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
-import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.GValueReductionStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.GValueReductionStrategy;
import org.apache.tinkerpop.gremlin.structure.Graph;
import java.io.Serializable;
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java
index 28fee5481e..b66f3efca4 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelper.java
@@ -18,11 +18,13 @@
*/
package org.apache.tinkerpop.gremlin.process.traversal.util;
+import org.apache.tinkerpop.gremlin.process.computer.GraphComputer;
import org.apache.tinkerpop.gremlin.process.computer.traversal.step.map.TraversalVertexProgramStep;
import org.apache.tinkerpop.gremlin.process.traversal.GValueManager;
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.AbstractLambdaTraversal;
import org.apache.tinkerpop.gremlin.process.traversal.lambda.ValueTraversal;
import org.apache.tinkerpop.gremlin.process.traversal.lambda.TokenTraversal;
@@ -39,7 +41,9 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.filter.HasStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.NotStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WherePredicateStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.WhereTraversalStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.AddEdgeStepContract;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.EdgeVertexStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStepContract;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.LabelStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.map.PropertiesStep;
@@ -72,14 +76,30 @@ import java.util.function.Predicate;
import java.util.stream.Collectors;
/**
+ * Utility class that provides functions that manipulate {@link Traversal} isntances. These functions are helpful when
+ * writing {@link TraversalStrategy} implementations.
+ *
* @author Marko A. Rodriguez (http://markorodriguez.com)
* @author Stephen Mallette (http://stephen.genoprime.com)
*/
public final class TraversalHelper {
- private TraversalHelper() {
- }
+ /**
+ * Registry mapping a contract/interface type to the explicit list of concrete Step classes that represent it.
+ * This registry is intentionally simple and local to TraversalHelper.
+ */
+ private static final Map<Class<?>, List<Class<? extends Step>>> STEP_CONTRACT_REGISTRY = new HashMap<>() {{
+ put(GraphStepContract.class, GraphStepContract.CONCRETE_STEPS);
+ put(AddEdgeStepContract.class, AddEdgeStepContract.CONCRETE_STEPS);
+ }};
+
+ private TraversalHelper() { }
+ /**
+ * Determines whether the given traversal only touches local vertex/edge properties (i.e. does not traverse the
+ * graph topology). This returns false if a step is encountered that walks the graph (e.g. VertexStep/EdgeVertexStep)
+ * or if a repeat's global children contain such steps. TraversalParent children are inspected recursively.
+ */
public static boolean isLocalProperties(final Traversal.Admin<?, ?> traversal) {
for (final Step step : traversal.getSteps()) {
if (step instanceof RepeatStep) {
@@ -101,6 +121,12 @@ public final class TraversalHelper {
return true;
}
+ /**
+ * Determines whether a traversal is confined to a single-star neighborhood of a starting vertex (i.e., a
+ * topologically local traversal over a vertex and its incident edges/adjacent vertices) without expanding further
+ * into the graph or pulling arbitrary properties that would require remote access. This method delegates to a
+ * state-machine helper and returns true if the traversal remains within the local star graph.
+ */
public static boolean isLocalStarGraph(final Traversal.Admin<?, ?> traversal) {
return 'x' != isLocalStarGraph(traversal, 'v');
}
@@ -207,10 +233,28 @@ public final class TraversalHelper {
traversal.addStep(indexToMoveTo, stepToMove);
}
+ /**
+ * Inserts all steps from the supplied insertTraversal directly after the given previousStep in the specified
+ * traversal, preserving their order.
+ *
+ * @param previousStep the step after which to insert the traversal
+ * @param insertTraversal the traversal whose steps will be inserted
+ * @param traversal the traversal to receive the steps
+ * @return the last step that was inserted
+ */
public static <S, E> Step<?, E> insertTraversal(final Step<?, S> previousStep, final Traversal.Admin<S, E> insertTraversal, final Traversal.Admin<?, ?> traversal) {
return TraversalHelper.insertTraversal(stepIndex(previousStep, traversal), insertTraversal, traversal);
}
+ /**
+ * Inserts all steps from the supplied insertTraversal into the specified traversal starting at the given index.
+ * Steps are inserted in order.
+ *
+ * @param insertIndex the position at which to start inserting
+ * @param insertTraversal the traversal whose steps will be inserted
+ * @param traversal the traversal to receive the steps
+ * @return the last step that was inserted (or the existing step at insertIndex if no steps exist)
+ */
public static <S, E> Step<?, E> insertTraversal(final int insertIndex, final Traversal.Admin<S, E> insertTraversal, final Traversal.Admin<?, ?> traversal) {
traversal.getGValueManager().mergeInto(insertTraversal.getGValueManager());
if (0 == traversal.getSteps().size()) {
@@ -230,6 +274,14 @@ public final class TraversalHelper {
}
}
+ /**
+ * Removes steps from the traversal starting at startStep up to but not including endStep and appends them to
+ * newTraversal, preserving order.
+ *
+ * @param startStep the first step to move
+ * @param endStep the terminal step at which to stop (not moved)
+ * @param newTraversal the traversal to receive the moved steps
+ */
public static <S, E> void removeToTraversal(final Step<S, ?> startStep, final Step<?, E> endStep, final Traversal.Admin<S, E> newTraversal) {
final Traversal.Admin<?, ?> originalTraversal = startStep.getTraversal();
Step<?, ?> currentStep = startStep;
@@ -258,15 +310,56 @@ public final class TraversalHelper {
return -1;
}
+ /**
+ * Returns all steps in the given traversal whose concrete class equals the supplied class. If the supplied class
+ * is an interface registered as a step contract, the method will match by exact equality to any of the registered
+ * concrete implementations for that contract. For example, calling this method with {@link GraphStepContract} will
+ * not match on the interface but instead will match on its {@link GraphStepContract#CONCRETE_STEPS}.
+ *
+ * @param stepClass the concrete step type to match, or a registered contract interface
+ * @param traversal the traversal to scan
+ * @return a list of matching steps (preserving traversal order)
+ */
public static <S> List<S> getStepsOfClass(final Class<S> stepClass, final Traversal.Admin<?, ?> traversal) {
final List<S> steps = new ArrayList<>();
+ // If stepClass is an interface and registered as a contract, expand to its concrete classes
+ final List<Class<? extends Step>> concrete;
+ if (stepClass.isInterface()) {
+ final List<Class<? extends Step>> reg = STEP_CONTRACT_REGISTRY.get(stepClass);
+ concrete = reg != null ? reg : null;
+ } else {
+ concrete = null;
+ }
+
+ if (concrete == null) {
+ // original behavior: exact equality to the provided class
+ for (final Step step : traversal.getSteps()) {
+ if (step.getClass().equals(stepClass))
+ steps.add((S) step);
+ }
+ return steps;
+ }
+
+ // contract expansion path: exact equality against any registered concrete classes
for (final Step step : traversal.getSteps()) {
- if (step.getClass().equals(stepClass))
- steps.add((S) step);
+ final Class<?> sc = step.getClass();
+ for (final Class<?> c : concrete) {
+ if (sc.equals(c)) {
+ steps.add((S) step);
+ break;
+ }
+ }
}
return steps;
}
+ /**
+ * Returns all steps in the given traversal that are instances of (i.e., assignable to) the supplied class.
+ *
+ * @param stepClass the class or interface to test with {@link Class#isAssignableFrom(Class)}
+ * @param traversal the traversal to scan
+ * @return a list of matching steps (preserving traversal order)
+ */
public static <S> List<S> getStepsOfAssignableClass(final Class<S> stepClass, final Traversal.Admin<?, ?> traversal) {
final List<S> steps = new ArrayList<>();
for (final Step step : traversal.getSteps()) {
@@ -276,11 +369,25 @@ public final class TraversalHelper {
return steps;
}
+ /**
+ * Returns the last step in the traversal that is assignable to the supplied class, if present.
+ *
+ * @param stepClass the class or interface to test with {@link Class#isAssignableFrom(Class)}
+ * @param traversal the traversal to scan
+ * @return the last matching step or {@link Optional#empty()} if none found
+ */
public static <S> Optional<S> getLastStepOfAssignableClass(final Class<S> stepClass, final Traversal.Admin<?, ?> traversal) {
final List<S> steps = TraversalHelper.getStepsOfAssignableClass(stepClass, traversal);
return steps.size() == 0 ? Optional.empty() : Optional.of(steps.get(steps.size() - 1));
}
+ /**
+ * Returns the first step in the traversal that is assignable to the supplied class, if present.
+ *
+ * @param stepClass the class or interface to test with {@link Class#isAssignableFrom(Class)}
+ * @param traversal the traversal to scan
+ * @return the first matching step or {@link Optional#empty()} if none found
+ */
public static <S> Optional<S> getFirstStepOfAssignableClass(final Class<S> stepClass, final Traversal.Admin<?, ?> traversal) {
for (final Step step : traversal.getSteps()) {
if (stepClass.isAssignableFrom(step.getClass()))
@@ -289,10 +396,27 @@ public final class TraversalHelper {
return Optional.empty();
}
+ /**
+ * Recursively collects steps assignable to the supplied class from the traversal and all its child traversals
+ * (both local and global).
+ *
+ * @param stepClass the class or interface to test with {@link Class#isAssignableFrom(Class)}
+ * @param traversal the root traversal to scan
+ * @return a list of matching steps found anywhere in the traversal tree
+ */
public static <S> List<S> getStepsOfAssignableClassRecursively(final Class<S> stepClass, final Traversal.Admin<?, ?> traversal) {
return getStepsOfAssignableClassRecursively(null, stepClass, traversal);
}
+ /**
+ * Recursively collects steps assignable to the supplied class from the traversal and its child traversals scoped
+ * by the given Scope.
+ *
+ * @param scope whether to include local, global, or both child traversals (null for both)
+ * @param stepClass the class or interface to test with {@link Class#isAssignableFrom(Class)}
+ * @param traversal the root traversal to scan
+ * @return a list of matching steps found anywhere within the scoped traversal tree
+ */
public static <S> List<S> getStepsOfAssignableClassRecursively(final Scope scope, final Class<S> stepClass, final Traversal.Admin<?, ?> traversal) {
final List<S> list = new ArrayList<>();
for (final Step<?, ?> step : traversal.getSteps()) {
@@ -315,7 +439,12 @@ public final class TraversalHelper {
}
/**
- * Get steps of the specified classes throughout the traversal.
+ * Recursively collects steps that are assignable to any of the supplied classes from the traversal and all its
+ * child traversals (both local and global).
+ *
+ * @param traversal the root traversal to scan
+ * @param stepClasses the classes or interfaces to test with {@link Class#isAssignableFrom(Class)}
+ * @return a list of matching steps found anywhere in the traversal tree
*/
public static List<Step<?,?>> getStepsOfAssignableClassRecursively(final Traversal.Admin<?, ?> traversal, final Class<?>... stepClasses) {
final List<Step<?,?>> list = new ArrayList<>();
@@ -338,8 +467,12 @@ public final class TraversalHelper {
}
/**
- * Get steps of the specified classes throughout the traversal, collecting them in a fashion that orders them
- * from the deepest steps first.
+ * Recursively collects steps assignable to any of the supplied classes from the traversal and children, then
+ * orders the result by depth (deepest child steps first). Depth ordering is determined by {@link DepthComparator}.
+ *
+ * @param traversal the root traversal to scan
+ * @param stepClasses the classes or interfaces to test with {@link Class#isAssignableFrom(Class)}
+ * @return a list of matching steps ordered from deepest to shallowest
*/
public static List<Step<?,?>> getStepsOfAssignableClassRecursivelyFromDepth(final Traversal.Admin<?, ?> traversal, final Class<?>... stepClasses) {
final List<Step<?,?>> list = new ArrayList<>();
@@ -369,6 +502,13 @@ public final class TraversalHelper {
}).collect(Collectors.toList());
}
+ /**
+ * Determines whether the supplied traversal is a global child of its parent (as opposed to a local child).
+ * Walks up the parent chain until the root to make this determination.
+ *
+ * @param traversal the traversal to test
+ * @return true if the traversal is a global child; false if it is a local child
+ */
public static boolean isGlobalChild(Traversal.Admin<?, ?> traversal) {
while (!(traversal.isRoot())) {
if (traversal.getParent().getLocalChildren().contains(traversal))
@@ -550,8 +690,9 @@ public final class TraversalHelper {
/**
* Apply the provider {@link Consumer} function to the provided {@link Traversal} and all of its children.
*
- * @param consumer the function to apply to the each traversal in the tree
- * @param traversal the root traversal to start application
+ * @param consumer the function to apply
+ * @param traversal the root traversal
+ * @param applyToChildrenOnly if true, only child traversals receive the function (the root is skipped)
*/
public static void applyTraversalRecursively(final Consumer<Traversal.Admin<?, ?>> consumer, final Traversal.Admin<?, ?> traversal,
final boolean applyToChildrenOnly) {
@@ -573,6 +714,15 @@ public final class TraversalHelper {
}
}
+ /**
+ * Adds the supplied element to the collection according to the provided bulk count. If the collection is a
+ * {@link BulkSet}, the element is added with the given bulk. If it is a Set, the element is added once. Otherwise
+ * the element is added repeatedly bulk times.
+ *
+ * @param collection the collection to mutate
+ * @param s the element to add
+ * @param bulk the bulk count
+ */
public static <S> void addToCollection(final Collection<S> collection, final S s, final long bulk) {
if (collection instanceof BulkSet) {
((BulkSet<S>) collection).add(s, bulk);
@@ -601,6 +751,14 @@ public final class TraversalHelper {
return name;
}
+ /**
+ * Reassigns identifiers for every step in the supplied traversal using the provided StepPosition state object. The
+ * StepPosition is mutated to reflect the current parent context (x/y/z/parentId) and each step receives a new id
+ * via StepPosition#nextXId().
+ *
+ * @param stepPosition the position tracker to mutate and use to generate ids
+ * @param traversal the traversal whose steps will be re-identified
+ */
public static void reIdSteps(final StepPosition stepPosition, final Traversal.Admin<?, ?> traversal) {
stepPosition.x = 0;
stepPosition.y = -1;
@@ -636,6 +794,12 @@ public final class TraversalHelper {
}
}
+ /**
+ * Returns the root traversal by walking up the parent chain until encountering an {@link EmptyStep} parent.
+ *
+ * @param traversal a traversal that may be nested
+ * @return the root (top-most) traversal
+ */
public static Traversal.Admin<?, ?> getRootTraversal(Traversal.Admin<?, ?> traversal) {
while (!((traversal.getParent()) instanceof EmptyStep)) {
traversal = traversal.getParent().asStep().getTraversal();
@@ -643,6 +807,12 @@ public final class TraversalHelper {
return traversal;
}
+ /**
+ * Determines whether any non-hidden labels are present anywhere in the traversal or its children.
+ *
+ * @param traversal the traversal to inspect
+ * @return true if at least one non-hidden label exists; false otherwise
+ */
public static boolean hasLabels(final Traversal.Admin<?, ?> traversal) {
for (final Step<?, ?> step : traversal.getSteps()) {
for (final String label : step.getLabels()) {
@@ -663,6 +833,12 @@ public final class TraversalHelper {
return false;
}
+ /**
+ * Collects all labels (including hidden) present in the traversal and its child traversals.
+ *
+ * @param traversal the traversal to inspect
+ * @return a set of labels
+ */
public static Set<String> getLabels(final Traversal.Admin<?, ?> traversal) {
return TraversalHelper.getLabels(new HashSet<>(), traversal);
}
@@ -682,6 +858,13 @@ public final class TraversalHelper {
return labels;
}
+ /**
+ * Determines whether labels are referenced at the START and/or END of the traversal by inspecting the first and
+ * last steps (and appropriate children for certain step types). Returned variables include START and/or END.
+ *
+ * @param traversal the traversal to inspect
+ * @return a set containing zero, one, or both of {@link Scoping.Variable#START} and {@link Scoping.Variable#END}
+ */
public static Set<Scoping.Variable> getVariableLocations(final Traversal.Admin<?, ?> traversal) {
return TraversalHelper.getVariableLocations(EnumSet.noneOf(Scoping.Variable.class), traversal);
}
@@ -726,6 +909,13 @@ public final class TraversalHelper {
return variables;
}
+ /**
+ * Determines if the traversal is executing on a {@link GraphComputer} by walking up the parent chain and checking
+ * for a {@link TraversalVertexProgramStep}.
+ *
+ * @param traversal the traversal to inspect
+ * @return true if the traversal is under a TraversalVertexProgramStep; false otherwise
+ */
public static boolean onGraphComputer(Traversal.Admin<?, ?> traversal) {
while (!(traversal.isRoot())) {
if (traversal.getParent() instanceof TraversalVertexProgramStep)
@@ -735,10 +925,22 @@ public final class TraversalHelper {
return false;
}
+ /**
+ * Removes the specified step from the traversal and returns the traversal for chaining.
+ *
+ * @param stepToRemove the step to remove
+ * @param traversal the traversal to mutate
+ * @return the traversal argument for chaining
+ */
public static Traversal.Admin<?, ?> removeStep(final Step<?, ?> stepToRemove, final Traversal.Admin<?, ?> traversal) {
return traversal.removeStep(stepToRemove);
}
+ /**
+ * Removes all steps from the traversal.
+ *
+ * @param traversal the traversal to clear
+ */
public static void removeAllSteps(final Traversal.Admin<?, ?> traversal) {
final int size = traversal.getSteps().size();
for (int i = 0; i < size; i++) {
@@ -746,6 +948,14 @@ public final class TraversalHelper {
}
}
+ /**
+ * Copies labels from one step to another. If moveLabels is true, labels are removed from the source after copying;
+ * otherwise labels are left in place and only added to the target.
+ *
+ * @param fromStep the step to copy labels from
+ * @param toStep the step to add labels to
+ * @param moveLabels whether to remove labels from the source after copying
+ */
public static void copyLabels(final Step<?, ?> fromStep, final Step<?, ?> toStep, final boolean moveLabels) {
if (!fromStep.getLabels().isEmpty()) {
for (final String label : moveLabels ? new LinkedHashSet<>(fromStep.getLabels()) : fromStep.getLabels()) {
@@ -756,6 +966,13 @@ public final class TraversalHelper {
}
}
+ /**
+ * Tests whether every step in the traversal is an instance of at least one of the supplied classes.
+ *
+ * @param traversal the traversal to test
+ * @param classesToCheck the classes to check with {@link Class#isInstance(Object)}
+ * @return true if all steps match at least one class; false otherwise
+ */
public static boolean hasAllStepsOfClass(final Traversal.Admin<?, ?> traversal, final Class<?>... classesToCheck) {
for (final Step step : traversal.getSteps()) {
boolean foundInstance = false;
@@ -771,6 +988,13 @@ public final class TraversalHelper {
return true;
}
+ /**
+ * Tests whether any step in the traversal is an instance of any of the supplied classes.
+ *
+ * @param traversal the traversal to test
+ * @param classesToCheck the classes to check with {@link Class#isInstance(Object)}
+ * @return true if any step matches at least one class; false otherwise
+ */
public static boolean hasStepOfClass(final Traversal.Admin<?, ?> traversal, final Class<?>... classesToCheck) {
for (final Step<?, ?> step : traversal.getSteps()) {
for (final Class<?> classToCheck : classesToCheck) {
@@ -786,7 +1010,6 @@ public final class TraversalHelper {
*
* @param traversal the traversal to fold or append.
* @param hasContainer the container to add left or append.
- * @param <T> the traversal type
* @return the has container folded or appended traversal
*/
public static <T extends Traversal.Admin<?, ?>> T addHasContainer(final T traversal, final HasContainer hasContainer) {
@@ -808,6 +1031,13 @@ public final class TraversalHelper {
}
}
+ /**
+ * Gathers all steps that implement {@link GValueHolder} and returns a map from step to the collection of
+ * {@link GValue} instances they hold.
+ *
+ * @param traversal the traversal to scan recursively
+ * @return a map of steps to their GValue collections
+ */
public static Map<Step, Collection<GValue<?>>> gatherStepGValues(final Traversal.Admin<?, ?> traversal) {
Map<Step, Collection<GValue<?>>> gValues = new HashMap<>();
applyTraversalRecursively(
@@ -822,6 +1052,13 @@ public final class TraversalHelper {
return gValues;
}
+ /**
+ * Gathers all steps that implement {@link GValueHolder} and returns them as a set. This is useful when only the
+ * presence of placeholders is needed and not the values themselves.
+ *
+ * @param traversal the traversal to scan recursively
+ * @return the set of steps that are {@link GValueHolder}s
+ */
public static Set<Step<?,?>> gatherGValuePlaceholders(final Traversal.Admin<?, ?> traversal) {
final Set<Step<?,?>> steps = new HashSet<>();
applyTraversalRecursively(
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/ConnectiveTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/ConnectiveTest.java
index 6e77f8d088..b67949c72b 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/ConnectiveTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/ConnectiveTest.java
@@ -20,6 +20,7 @@ package org.apache.tinkerpop.gremlin.process.traversal;
import org.apache.tinkerpop.gremlin.process.traversal.util.AndP;
import org.apache.tinkerpop.gremlin.process.traversal.util.OrP;
+import org.apache.tinkerpop.gremlin.process.traversal.step.GValue;
import org.junit.Rule;
import org.junit.Test;
import org.junit.experimental.runners.Enclosed;
@@ -37,6 +38,68 @@ import static org.junit.Assert.assertEquals;
@RunWith(Enclosed.class)
public class ConnectiveTest {
+ @Test
+ public void shouldUpdateVariablesInOr() {
+ // P.gt and P.lt have GValue overloads enabling variables
+ final P<Integer> p1 = P.gt(GValue.of("x", 0));
+ final P<Integer> p2 = P.lt(GValue.of("y", 10));
+ final OrP<Integer> or = new OrP<>(Arrays.asList(p1, p2));
+
+ // Initially variables x=0, y=10
+ // For value 5 -> gt(0) true OR lt(10) true => true
+ assertEquals(true, or.test(5));
+
+ // Update only x so that gt(7) for value 5 is false, but lt(10) still true => overall true
+ or.updateVariable("x", 7);
+ assertEquals(true, or.test(5));
+
+ // Update y so that lt(4) for value 5 is false; now both false => overall false
+ or.updateVariable("y", 4);
+ assertEquals(false, or.test(5));
+ }
+
+ @Test
+ public void shouldUpdateVariablesInAndWithNestedConnectives() {
+ // Build nested ((gt(x) AND lt(y)) AND gt(z))
+ final P<Integer> gtX = P.gt(GValue.of("x", 0));
+ final P<Integer> ltY = P.lt(GValue.of("y", 10));
+ final P<Integer> gtZ = P.gt(GValue.of("z", -1));
+ final AndP<Integer> inner = new AndP<>(Arrays.asList(gtX, ltY));
+ final AndP<Integer> and = new AndP<>(Arrays.asList(inner, gtZ));
+
+ // value 5 should satisfy defaults
+ assertEquals(true, and.test(5));
+
+ // change x so gt(6) on 5 becomes false -> whole AND false
+ and.updateVariable("x", 6);
+ assertEquals(false, and.test(5));
+
+ // fix x back and then make y tighter so lt(4) on 5 is false
+ and.updateVariable("x", 0);
+ and.updateVariable("y", 4);
+ assertEquals(false, and.test(5));
+
+ // relax y and tighten z so gt(6) on 5 false
+ and.updateVariable("y", 10);
+ and.updateVariable("z", 6);
+ assertEquals(false, and.test(5));
+
+ // final: set z to -1 so condition holds again
+ and.updateVariable("z", -1);
+ assertEquals(true, and.test(5));
+ }
+
+ @Test
+ public void shouldNotAffectUnknownVariables() {
+ final P<Integer> p1 = P.gt(GValue.of("known", 3));
+ final P<Integer> p2 = P.lt(GValue.of("also", 9));
+ final AndP<Integer> and = new AndP<>(Arrays.asList(p1, p2));
+
+ // Update a name that does not exist should have no effect
+ and.updateVariable("unknown", 100);
+ assertEquals(true, and.test(5));
+ }
+
private static final Object VAL = 1;
private static final P TRUE = P.eq(1);
private static final P FALSE = P.gt(1);
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/EarlyLimitStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/EarlyLimitStrategyTest.java
index 2388546e77..a33dc1dcc4 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/EarlyLimitStrategyTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/EarlyLimitStrategyTest.java
@@ -30,7 +30,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.GValue;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.RangeGlobalStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.RangeGlobalStepContract;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.GValueManagerVerifier;
-import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.GValueReductionStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ProfileStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.translator.GroovyTranslator;
import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelperTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelperTest.java
index aa86a0d913..36b3673413 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelperTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/util/TraversalHelperTest.java
@@ -71,7 +71,6 @@ import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.hamcrest.MatcherAssert.assertThat;
-import static org.junit.Assert.assertTrue;
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
@@ -85,14 +84,14 @@ public class TraversalHelperTest {
//transform the traversal to __.V().not(out())
//the VertexStep's previousStep should be the EmptyStep
Optional<VertexStep> vertexStepOpt = TraversalHelper.getFirstStepOfAssignableClass(VertexStep.class, traversal);
- assertTrue(vertexStepOpt.isPresent());
+ assertThat(vertexStepOpt.isPresent(), is(true));
Traversal.Admin<?,?> inner = __.start().asAdmin();
inner.addStep(0, vertexStepOpt.get());
TraversalHelper.replaceStep(vertexStepOpt.get(), new NotStep<>(__.identity().asAdmin(), inner), traversal);
List<VertexStep> vertexSteps = TraversalHelper.getStepsOfAssignableClassRecursively(VertexStep.class, traversal);
assertEquals(1, vertexSteps.size());
VertexStep vertexStep = vertexSteps.get(0);
- assertTrue("Expected the previousStep to be an EmptyStep, found instead " + vertexStep.getPreviousStep().toString(),vertexStep.getPreviousStep() == EmptyStep.instance());
+ assertThat("Expected the previousStep to be an EmptyStep, found instead " + vertexStep.getPreviousStep().toString(), vertexStep.getPreviousStep() == EmptyStep.instance(), is(true));
}
@Test
@@ -123,25 +122,25 @@ public class TraversalHelperTest {
final Traversal.Admin<?, ?> globalChild = __.select("a", "b").by("name").asAdmin();
TraversalParent parent = new RepeatStep<>(new DefaultTraversal());
((RepeatStep) parent).setRepeatTraversal(globalChild);
- assertTrue(TraversalHelper.isGlobalChild(globalChild));
+ assertThat(TraversalHelper.isGlobalChild(globalChild), is(true));
///
new UnionStep<>(new DefaultTraversal(), globalChild);
- assertTrue(TraversalHelper.isGlobalChild(globalChild));
+ assertThat(TraversalHelper.isGlobalChild(globalChild), is(true));
///
new TraversalVertexProgramStep(new DefaultTraversal<>(), globalChild);
- assertTrue(TraversalHelper.isGlobalChild(globalChild));
+ assertThat(TraversalHelper.isGlobalChild(globalChild), is(true));
///
final Traversal.Admin<?, ?> remoteRemoteChild = __.repeat(globalChild).asAdmin();
new UnionStep<>(new DefaultTraversal(), remoteRemoteChild);
- assertTrue(TraversalHelper.isGlobalChild(globalChild));
+ assertThat(TraversalHelper.isGlobalChild(globalChild), is(true));
}
@Test
public void shouldIdentifyLocalProperties() {
- assertTrue(TraversalHelper.isLocalProperties(__.identity().asAdmin()));
- assertTrue(TraversalHelper.isLocalProperties(__.id().asAdmin()));
- assertTrue(TraversalHelper.isLocalProperties(__.label().asAdmin()));
- assertTrue(TraversalHelper.isLocalProperties(__.values("name").asAdmin()));
+ assertThat(TraversalHelper.isLocalProperties(__.identity().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalProperties(__.id().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalProperties(__.label().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalProperties(__.values("name").asAdmin()), is(true));
assertFalse(TraversalHelper.isLocalProperties(outE("knows").asAdmin()));
}
@@ -333,22 +332,22 @@ public class TraversalHelperTest {
@Test
public void shouldIdentifyStarGraphTraversals() {
- assertTrue(TraversalHelper.isLocalStarGraph(__.identity().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.id().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.out().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.label().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.bothE().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.values().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.properties().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.repeat(__.identity()).asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.repeat(__.has("name")).asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.out().repeat(__.identity()).asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.out().id().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.label().union(__.out(), in()).asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.label().union(__.out(), in()).id().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.coalesce(out("likes"), out("knows"), out("created")).groupCount().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.local(__.out()).groupCount().asAdmin()));
- assertTrue(TraversalHelper.isLocalStarGraph(__.local(__.out()).groupCount().by(T.id).asAdmin()));
+ assertThat(TraversalHelper.isLocalStarGraph(__.identity().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.id().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.out().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.label().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.bothE().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.values().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.properties().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.repeat(__.identity()).asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.repeat(__.has("name")).asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.out().repeat(__.identity()).asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.out().id().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.label().union(__.out(), in()).asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.label().union(__.out(), in()).id().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.coalesce(out("likes"), out("knows"), out("created")).groupCount().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.local(__.out()).groupCount().asAdmin()), is(true));
+ assertThat(TraversalHelper.isLocalStarGraph(__.local(__.out()).groupCount().by(T.id).asAdmin()), is(true));
// assertTrue(TraversalHelper.isLocalStarGraph(__.out().repeat(__.has("name")).asAdmin()));
//
assertFalse(TraversalHelper.isLocalStarGraph(__.out().label().asAdmin()));
@@ -372,25 +371,25 @@ public class TraversalHelperTest {
.flatMap(s -> s.getLabels().stream())
.collect(Collectors.toSet());
assertEquals(2, labels.size());
- assertTrue(labels.contains("a"));
- assertTrue(labels.contains("c"));
+ assertThat(labels.contains("a"), is(true));
+ assertThat(labels.contains("c"), is(true));
//
labels = (Set) TraversalHelper.getStepsOfAssignableClass(VertexStep.class, __.out().as("a").values("name").as("b").in().as("c").groupCount().as("d").asAdmin())
.stream()
.flatMap(s -> s.getLabels().stream())
.collect(Collectors.toSet());
assertEquals(2, labels.size());
- assertTrue(labels.contains("a"));
- assertTrue(labels.contains("c"));
+ assertThat(labels.contains("a"), is(true));
+ assertThat(labels.contains("c"), is(true));
//
labels = (Set) TraversalHelper.getStepsOfAssignableClass(FlatMapStep.class, __.out().as("a").values("name").as("b").in().as("c").groupCount().as("d").asAdmin())
.stream()
.flatMap(s -> s.getLabels().stream())
.collect(Collectors.toSet());
assertEquals(3, labels.size());
- assertTrue(labels.contains("a"));
- assertTrue(labels.contains("b"));
- assertTrue(labels.contains("c"));
+ assertThat(labels.contains("a"), is(true));
+ assertThat(labels.contains("b"), is(true));
+ assertThat(labels.contains("c"), is(true));
//
labels = (Set) TraversalHelper.getStepsOfClass(Step.class, __.out().as("a").values("name").as("b").in().as("c").groupCount().as("d").asAdmin())
.stream()
@@ -403,28 +402,28 @@ public class TraversalHelperTest {
.flatMap(s -> s.getLabels().stream())
.collect(Collectors.toSet());
assertEquals(4, labels.size());
- assertTrue(labels.contains("a"));
- assertTrue(labels.contains("b"));
- assertTrue(labels.contains("c"));
- assertTrue(labels.contains("d"));
+ assertThat(labels.contains("a"), is(true));
+ assertThat(labels.contains("b"), is(true));
+ assertThat(labels.contains("c"), is(true));
+ assertThat(labels.contains("d"), is(true));
}
@Test
public void shouldGetLabels() {
Set<String> labels = (Set) TraversalHelper.getLabels(__.out().as("a").values("name").as("b").in().as("c").groupCount().as("d").asAdmin());
assertEquals(4, labels.size());
- assertTrue(labels.contains("a"));
- assertTrue(labels.contains("b"));
- assertTrue(labels.contains("c"));
- assertTrue(labels.contains("d"));
+ assertThat(labels.contains("a"), is(true));
+ assertThat(labels.contains("b"), is(true));
+ assertThat(labels.contains("c"), is(true));
+ assertThat(labels.contains("d"), is(true));
labels = (Set) TraversalHelper.getLabels(__.out().as("a").repeat(__.out("name").as("b")).local(in().as("c")).as("d").groupCount().by(outE().as("e")).as("f").asAdmin());
assertEquals(6, labels.size());
- assertTrue(labels.contains("a"));
- assertTrue(labels.contains("b"));
- assertTrue(labels.contains("c"));
- assertTrue(labels.contains("d"));
- assertTrue(labels.contains("e"));
- assertTrue(labels.contains("f"));
+ assertThat(labels.contains("a"), is(true));
+ assertThat(labels.contains("b"), is(true));
+ assertThat(labels.contains("c"), is(true));
+ assertThat(labels.contains("d"), is(true));
+ assertThat(labels.contains("e"), is(true));
+ assertThat(labels.contains("f"), is(true));
}
@Test
@@ -578,4 +577,27 @@ public class TraversalHelperTest {
assertEquals(TraversalHelper.getPopInstructions(traversals.get(i)), expectedResults.get(i));
}
}
+
+ @Test
+ public void shouldUseContractRegistryInGetStepsOfClass() {
+ // Build a traversal that will include a GraphStepPlaceholder as start (V()) and then some steps
+ final Traversal.Admin<?,?> t = __.V().out().values("name").asAdmin();
+ // Ensure that asking for GraphStepContract.class returns the start step
+ final List<Step<?,?>> steps = (List) TraversalHelper.getStepsOfClass(org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStepContract.class, t);
+ // There should be exactly one GraphStep* at the start
+ assertEquals(1, steps.size());
+ // And it should be one of the registered concrete classes
+ final Class<?> sc = steps.get(0).getClass();
+ final java.util.List<Class<? extends Step>> concretes = org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStepContract.CONCRETE_STEPS;
+ assertThat(concretes.stream().anyMatch(c -> c.equals(sc)), is(true));
+ }
+
+ @Test
+ public void shouldNotAffectNonRegisteredInterfaces() {
+ // Use a random interface that is not a registered contract
+ final Traversal.Admin<?,?> t = __.out().in().asAdmin();
+ // Step is an interface but exact equality semantics should apply and thus return empty here
+ final List<Step<?,?>> steps = (List) TraversalHelper.getStepsOfClass(Step.class, t);
+ assertEquals(0, steps.size());
+ }
}
diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/jsr223/TinkerGraphGremlinLangScriptEngineTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/jsr223/TinkerGraphGremlinLangScriptEngineTest.java
index 3f24be6f85..3ba32eab2e 100644
--- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/jsr223/TinkerGraphGremlinLangScriptEngineTest.java
+++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/jsr223/TinkerGraphGremlinLangScriptEngineTest.java
@@ -30,6 +30,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.GValue;
import org.apache.tinkerpop.gremlin.structure.Direction;
import org.apache.tinkerpop.gremlin.structure.Vertex;
import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceVertex;
+import org.apache.tinkerpop.gremlin.tinkergraph.process.traversal.strategy.optimization.TinkerGraphCountStrategy;
+import org.apache.tinkerpop.gremlin.tinkergraph.process.traversal.strategy.optimization.TinkerGraphStepStrategy;
import org.apache.tinkerpop.gremlin.tinkergraph.services.TinkerTextSearchFactory;
import org.apache.tinkerpop.gremlin.tinkergraph.structure.TinkerFactory;
import org.apache.tinkerpop.gremlin.tinkergraph.structure.TinkerGraph;
@@ -681,7 +683,13 @@ public class TinkerGraphGremlinLangScriptEngineTest {
public void setup() {
// create a new engine each time to keep the cache clear
scriptEngine = new GremlinLangScriptEngine(variableResolverCustomizer, gremlinLangCustomizer);
- g = traversal().with(graph);
+
+ // remove strategies to allow the tests to pass. the strategies replace placeholder steps with concrete ones
+ // which remove the ability for the GValueReductionStrategy to update bindings in GValue from a cached
+ // traversal. this is a bit of a limitation of the cache features right now. prior to this change it was
+ // working because the TinkerGraphStepStrategy was only doing a replace on GraphStep instances and not on the
+ // new GraphStepContract which would have also included the placeholder. if providers want the
+ g = traversal().with(graph); // .withoutStrategies(TinkerGraphStepStrategy.class, TinkerGraphCountStrategy.class);
}
@Test
diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/TinkerGraphNoStrategyProvider.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/TinkerGraphNoStrategyProvider.java
index 02bfdf4cf5..fb08f8ca9f 100644
--- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/TinkerGraphNoStrategyProvider.java
+++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/process/TinkerGraphNoStrategyProvider.java
@@ -25,7 +25,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.ConnectiveStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.SideEffectStrategy;
-import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.GValueReductionStrategy;
+import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.GValueReductionStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ProfileStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.ProductiveByStrategy;
import org.apache.tinkerpop.gremlin.structure.Graph;