This is an automated email from the ASF dual-hosted git repository. spmallette pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/tinkerpop.git
commit 4637f82c00878f2b7ad3778ed0ef3ae0d0488c82 Author: Stephen Mallette <[email protected]> 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 fb92e63e56..e3332284cd 100644 --- a/docs/src/upgrade/release-3.8.x.asciidoc +++ b/docs/src/upgrade/release-3.8.x.asciidoc @@ -856,7 +856,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 7e1c4557f6..65d7f8c762 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;
