while reviewing @twilmes work, I made various adjustments. Coding style things like finalizing variables, simplifiying some methods using existing Helper classes we have, added more tests to PrunePathStrategyTest, added PathProcess updates to TreeSideEffectStep. all in all, this is very solid work. I still need more time to review as there is one thing the troubles me about dynamic pruning in MatchStep. Just want to commit what I have done thus far so I don't corrupt it.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/f9c6ea62 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/f9c6ea62 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/f9c6ea62 Branch: refs/heads/TINKERPOP-1278 Commit: f9c6ea62c4a17d25a681cf0678d9713013302c67 Parents: 88c5d27 Author: Marko A. Rodriguez <okramma...@gmail.com> Authored: Fri Jul 8 10:01:35 2016 -0600 Committer: Marko A. Rodriguez <okramma...@gmail.com> Committed: Fri Jul 8 10:01:35 2016 -0600 ---------------------------------------------------------------------- .../process/traversal/TraversalStrategies.java | 4 +- .../process/traversal/step/PathProcessor.java | 16 ++--- .../traversal/step/filter/DedupGlobalStep.java | 4 +- .../step/filter/WherePredicateStep.java | 4 +- .../step/filter/WhereTraversalStep.java | 8 +-- .../process/traversal/step/map/MatchStep.java | 49 +++++++++----- .../process/traversal/step/map/PathStep.java | 8 +-- .../traversal/step/map/SelectOneStep.java | 2 +- .../process/traversal/step/map/SelectStep.java | 10 +-- .../step/sideEffect/TreeSideEffectStep.java | 9 ++- .../optimization/PathProcessorStrategy.java | 3 +- .../optimization/PrunePathStrategy.java | 67 ++++++++---------- .../process/traversal/util/PathUtil.java | 10 +-- .../optimization/PrunePathStrategyTest.java | 71 +++++++++++--------- 14 files changed, 143 insertions(+), 122 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java ---------------------------------------------------------------------- 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 850db9f..ee3fa76 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 @@ -197,9 +197,9 @@ public interface TraversalStrategies extends Serializable, Cloneable { MatchPredicateStrategy.instance(), RepeatUnrollStrategy.instance(), RangeByIsCountStrategy.instance(), + PrunePathStrategy.instance(), ProfileStrategy.instance(), - StandardVerificationStrategy.instance(), - PrunePathStrategy.instance()); + StandardVerificationStrategy.instance()); GRAPH_CACHE.put(Graph.class, graphStrategies); GRAPH_CACHE.put(EmptyGraph.class, new DefaultTraversalStrategies()); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java index 7d8a497..f3870cb 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java @@ -60,15 +60,15 @@ public interface PathProcessor { return max; } - void setKeepLabels(final Set<String> labels); + public void setKeepLabels(final Set<String> labels); - static void keepLabels(final Traverser traverser, final Set<String> labels) { - if(labels == null || labels.isEmpty()) { - return; - } else { - traverser.asAdmin().keepLabels(labels); - } + public Set<String> getKeepLabels(); + + public static <S> Traverser.Admin<S> processTraverserPathLabels(final Traverser.Admin<S> traverser, final Set<String> labels) { + if (null != labels && !labels.isEmpty()) + traverser.keepLabels(labels); + return traverser; } - Set<String> getKeepLabels(); + } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/DedupGlobalStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/DedupGlobalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/DedupGlobalStep.java index 78fd429..8ef6455 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/DedupGlobalStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/DedupGlobalStep.java @@ -83,9 +83,7 @@ public final class DedupGlobalStep<S> extends FilterStep<S> implements Traversal @Override protected Traverser.Admin<S> processNextStart() { - final Traverser.Admin<S> traverser = super.processNextStart(); - PathProcessor.keepLabels(traverser, keepLabels); - return traverser; + return PathProcessor.processTraverserPathLabels(super.processNextStart(), this.keepLabels); } @Override http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java index 0ee7832..bea9aad 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java @@ -120,9 +120,7 @@ public final class WherePredicateStep<S> extends FilterStep<S> implements Scopin @Override protected Traverser.Admin<S> processNextStart() { - final Traverser.Admin<S> traverser = super.processNextStart(); - PathProcessor.keepLabels(traverser, keepLabels); - return traverser; + return PathProcessor.processTraverserPathLabels(super.processNextStart(), this.keepLabels); } @Override http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WhereTraversalStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WhereTraversalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WhereTraversalStep.java index 078a370..762dfed 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WhereTraversalStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WhereTraversalStep.java @@ -91,9 +91,7 @@ public final class WhereTraversalStep<S> extends FilterStep<S> implements Traver @Override protected Traverser.Admin<S> processNextStart() { - final Traverser.Admin<S> traverser = super.processNextStart(); - PathProcessor.keepLabels(traverser, keepLabels); - return traverser; + return PathProcessor.processTraverserPathLabels(super.processNextStart(), this.keepLabels); } @Override @@ -147,7 +145,9 @@ public final class WhereTraversalStep<S> extends FilterStep<S> implements Traver } @Override - public Set<String> getKeepLabels() { return this.keepLabels; } + public Set<String> getKeepLabels() { + return this.keepLabels; + } ////////////////////////////// http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java index 3fb45fc..0a6d59b 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStep.java @@ -18,11 +18,20 @@ */ package org.apache.tinkerpop.gremlin.process.traversal.step.map; -import org.apache.tinkerpop.gremlin.process.traversal.*; +import org.apache.tinkerpop.gremlin.process.traversal.Path; +import org.apache.tinkerpop.gremlin.process.traversal.Pop; +import org.apache.tinkerpop.gremlin.process.traversal.Step; +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.TraversalEngine; +import org.apache.tinkerpop.gremlin.process.traversal.Traverser; import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor; import org.apache.tinkerpop.gremlin.process.traversal.step.Scoping; import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; -import org.apache.tinkerpop.gremlin.process.traversal.step.filter.*; +import org.apache.tinkerpop.gremlin.process.traversal.step.filter.AndStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.filter.ConnectiveStep; +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.sideEffect.StartStep; import org.apache.tinkerpop.gremlin.process.traversal.step.util.AbstractStep; import org.apache.tinkerpop.gremlin.process.traversal.step.util.ComputerAwareStep; @@ -38,7 +47,17 @@ import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils; import java.io.Serializable; import java.lang.reflect.InvocationTargetException; -import java.util.*; +import java.util.ArrayList; +import java.util.Collections; +import java.util.Comparator; +import java.util.HashMap; +import java.util.HashSet; +import java.util.Iterator; +import java.util.List; +import java.util.Map; +import java.util.NoSuchElementException; +import java.util.Optional; +import java.util.Set; import java.util.function.Function; import java.util.stream.Collectors; import java.util.stream.Stream; @@ -139,7 +158,6 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } - public ConnectiveStep.Connective getConnective() { return this.connective; } @@ -373,16 +391,16 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } - protected List<Traversal.Admin> getRemainingTraversals(final Traverser.Admin traverser) { + protected List<Traversal.Admin<?, ?>> getRemainingTraversals(final Traverser.Admin<?> traverser) { final Set<String> tags = traverser.getTags(); - final List<Traversal.Admin> remainingTraversals = new ArrayList<>(); - for (final Traversal.Admin matchTraversal : matchTraversals) { + final List<Traversal.Admin<?, ?>> remainingTraversals = new ArrayList<>(); + for (final Traversal.Admin<?, ?> matchTraversal : matchTraversals) { if (!tags.contains(matchTraversal.getStartStep().getId())) { remainingTraversals.add(matchTraversal); } else { // include the current traversal that the traverser is executing in the list of // remaining traversals - for (final Step<?, ?> s : (List<Step<?, ?>>)matchTraversal.getSteps()) { + for (final Step<?, ?> s : matchTraversal.getSteps()) { if (s.getId().equals(traverser.getStepId())) { remainingTraversals.add(matchTraversal); break; @@ -410,14 +428,13 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> @Override protected Traverser.Admin<Map<String, E>> processNextStart() throws NoSuchElementException { final Traverser.Admin<Map<String, E>> traverser = super.processNextStart(); - if (keepLabels != null) { + if (null != this.keepLabels) { final Set<String> keepers = new HashSet<>(); - List<Traversal.Admin> remainingTraversals = getRemainingTraversals(traverser); - for (Traversal.Admin trav : remainingTraversals) { - keepers.addAll(PathUtil.getReferencedLabels(trav)); + for (final Traversal.Admin<?, ?> traversal : getRemainingTraversals(traverser)) { + keepers.addAll(PathUtil.getReferencedLabels(traversal)); } - keepers.addAll(keepLabels); - PathProcessor.keepLabels(traverser, keepers); + keepers.addAll(this.keepLabels); + PathProcessor.processTraverserPathLabels(traverser, keepers); } return traverser; } @@ -749,5 +766,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> return this.matchEndLabels; } - public Set<String> getMatchStartLabels() { return this.matchStartLabels; } + public Set<String> getMatchStartLabels() { + return this.matchStartLabels; + } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PathStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PathStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PathStep.java index 885afc1..c4b2534 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PathStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/PathStep.java @@ -110,11 +110,11 @@ public final class PathStep<S> extends MapStep<S, Path> implements TraversalPare @Override protected Traverser.Admin<Path> processNextStart() { - final Traverser.Admin<Path> traverser = super.processNextStart(); - PathProcessor.keepLabels(traverser, keepLabels); - return traverser; + return PathProcessor.processTraverserPathLabels(super.processNextStart(), this.keepLabels); } @Override - public Set<String> getKeepLabels() { return this.keepLabels; } + public Set<String> getKeepLabels() { + return this.keepLabels; + } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java index 3bd5c1d..87a3f9b 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java @@ -129,7 +129,7 @@ public final class SelectOneStep<S, E> extends MapStep<S, E> implements Traversa protected Traverser.Admin<E> processNextStart() { final Traverser.Admin<E> traverser = super.processNextStart(); if(!(this.getTraversal().getParent() instanceof MatchStep)) { - PathProcessor.keepLabels(traverser, keepLabels); + PathProcessor.processTraverserPathLabels(traverser, this.keepLabels); } return traverser; } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java index ecd5581..b875a79 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java @@ -62,7 +62,7 @@ public final class SelectStep<S, E> extends MapStep<S, Map<String, E>> implement @Override protected Map<String, E> map(final Traverser.Admin<S> traverser) { - final Map<String, E> bindings = new LinkedHashMap<>(this.selectKeys.size(),1.0f); + final Map<String, E> bindings = new LinkedHashMap<>(this.selectKeys.size(), 1.0f); for (final String selectKey : this.selectKeys) { final E end = this.getNullableScopeValue(this.pop, selectKey, traverser); if (null != end) @@ -149,12 +149,12 @@ public final class SelectStep<S, E> extends MapStep<S, Map<String, E>> implement } @Override - public Set<String> getKeepLabels() { return this.keepLabels; } + public Set<String> getKeepLabels() { + return this.keepLabels; + } @Override protected Traverser.Admin<Map<String, E>> processNextStart() { - final Traverser.Admin<Map<String, E>> traverser = super.processNextStart(); - PathProcessor.keepLabels(traverser, keepLabels); - return traverser; + return PathProcessor.processTraverserPathLabels(super.processNextStart(), this.keepLabels); } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java index 6351455..4ef5544 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/TreeSideEffectStep.java @@ -69,6 +69,11 @@ public final class TreeSideEffectStep<S> extends SideEffectStep<S> implements Si } @Override + protected Traverser.Admin<S> processNextStart() { + return PathProcessor.processTraverserPathLabels(super.processNextStart(), this.keepLabels); + } + + @Override public String getSideEffectKey() { return this.sideEffectKey; } @@ -123,5 +128,7 @@ public final class TreeSideEffectStep<S> extends SideEffectStep<S> implements Si } @Override - public Set<String> getKeepLabels() { return this.keepLabels; } + public Set<String> getKeepLabels() { + return this.keepLabels; + } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathProcessorStrategy.java ---------------------------------------------------------------------- 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 c0286f2..0b40743 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 @@ -32,6 +32,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversal import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; import java.util.Arrays; +import java.util.Collections; import java.util.HashSet; import java.util.List; import java.util.Map; @@ -44,7 +45,7 @@ public final class PathProcessorStrategy extends AbstractTraversalStrategy<Trave private static final PathProcessorStrategy INSTANCE = new PathProcessorStrategy(); - private static final Set<Class<? extends OptimizationStrategy>> PRIORS = new HashSet<>(Arrays.asList(MatchPredicateStrategy.class)); + private static final Set<Class<? extends OptimizationStrategy>> PRIORS = Collections.singleton(MatchPredicateStrategy.class); private PathProcessorStrategy() { } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java index ebb6b66..e3d50bf 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java @@ -23,13 +23,13 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor; import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; -import org.apache.tinkerpop.gremlin.process.traversal.step.map.PathStep; -import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SubgraphStep; import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep; import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement; import org.apache.tinkerpop.gremlin.process.traversal.util.PathUtil; import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; +import java.util.Arrays; import java.util.Collections; import java.util.HashSet; import java.util.List; @@ -41,11 +41,8 @@ import java.util.Set; public final class PrunePathStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> implements TraversalStrategy.OptimizationStrategy { private static final PrunePathStrategy INSTANCE = new PrunePathStrategy(); - private static final Set<Class<? extends OptimizationStrategy>> PRIORS = new HashSet<>(); - - static { - PRIORS.add(PathProcessorStrategy.class); - } + // these strategies do strong rewrites involving path labeling and thus, should run prior to PrunePathStrategy + private static final Set<Class<? extends OptimizationStrategy>> PRIORS = new HashSet<>(Arrays.asList(RepeatUnrollStrategy.class, MatchPredicateStrategy.class, PathProcessorStrategy.class)); private PrunePathStrategy() { } @@ -54,10 +51,10 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal return INSTANCE; } - protected Set<String> getAndPropagateReferencedLabels(final Traversal.Admin<?, ?> traversal) { - if (traversal.getParent().equals(EmptyStep.instance())) { - return Collections.EMPTY_SET; - } + private Set<String> getAndPropagateReferencedLabels(final Traversal.Admin<?, ?> traversal) { + if (traversal.getParent().equals(EmptyStep.instance())) + return Collections.emptySet(); + Step<?, ?> parent = traversal.getParent().asStep(); Set<String> referencedLabels = new HashSet<>(); // get referenced labels from this traversal @@ -83,7 +80,7 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal referencedLabels.addAll(labels); } step = step.getNextStep(); - } while(!(step.equals(EmptyStep.instance()))); + } while (!(step.equals(EmptyStep.instance()))); if (topLevelParent) { step = parent; do { @@ -105,10 +102,10 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal @Override public void apply(final Traversal.Admin<?, ?> traversal) { - TraversalParent parent = traversal.getParent(); - Set<String> foundLabels = new HashSet<>(); - Set<String> keepLabels = new HashSet<>(); + final TraversalParent parent = traversal.getParent(); + final Set<String> foundLabels = new HashSet<>(); + final Set<String> keepLabels = new HashSet<>(); // If this traversal has a parent, it will need to inherit its // parent's keep labels. If its direct parent is not a PathProcessor, @@ -117,27 +114,20 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal if (!parent.equals(EmptyStep.instance())) { // start with parents keep labels if (parent instanceof PathProcessor) { - PathProcessor parentPathProcess = (PathProcessor) parent; - if (parentPathProcess.getKeepLabels() != null) keepLabels.addAll(parentPathProcess.getKeepLabels()); - } else { - Set<String> labels = getAndPropagateReferencedLabels(traversal); - keepLabels.addAll(labels); - } + final PathProcessor parentPathProcess = (PathProcessor) parent; + if (null != parentPathProcess.getKeepLabels()) keepLabels.addAll(parentPathProcess.getKeepLabels()); + } else + keepLabels.addAll(getAndPropagateReferencedLabels(traversal)); } - // check if the traversal contains any path or subgraph steps and if + // check if the traversal contains any PATH requiring steps and if // it does, note it so that the keep labels are set to null later on // which signals PathProcessors to not drop path information - boolean hasPathStep = false; - final List<PathStep> pathSteps = TraversalHelper.getStepsOfAssignableClassRecursively(PathStep.class, traversal); - final List<SubgraphStep> subgraphSteps = TraversalHelper.getStepsOfAssignableClassRecursively(SubgraphStep.class, traversal); - if (!pathSteps.isEmpty() || !subgraphSteps.isEmpty()) { - hasPathStep = true; - } + final boolean hasPathStep = TraversalHelper.anyStepRecursively(step -> step.getRequirements().contains(TraverserRequirement.PATH), traversal); final List<Step> steps = traversal.getSteps(); - for(int i = steps.size() - 1; i >= 0; i--) { - Step currentStep = steps.get(i); + for (int i = steps.size() - 1; i >= 0; i--) { + final Step currentStep = steps.get(i); if (!hasPathStep) { // maintain our list of labels to keep, repeatedly adding labels that were found during // the last iteration @@ -145,22 +135,19 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal final Set<String> labels = PathUtil.getReferencedLabels(currentStep); for (final String label : labels) { - if (foundLabels.contains(label)) { + if (foundLabels.contains(label)) keepLabels.add(label); - } else { + else foundLabels.add(label); - } } - - if (currentStep instanceof PathProcessor) { + // add the keep labels to the path processor + if (currentStep instanceof PathProcessor) ((PathProcessor) currentStep).setKeepLabels(new HashSet<>(keepLabels)); - } } else { - // if there is a PathStep or SubgraphStep in the traversal, do not drop labels - if (currentStep instanceof PathProcessor) { - // set keep labels to null so that no labels are dropped + // if there is a PATh requiring step in the traversal, do not drop labels + // set keep labels to null so that no labels are dropped + if (currentStep instanceof PathProcessor) ((PathProcessor) currentStep).setKeepLabels(null); - } } } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java index d07de50..5a9bb0a 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java @@ -34,7 +34,7 @@ import java.util.Set; */ public class PathUtil { - public static Set<String> getReferencedLabels(Traversal.Admin<?, ?> traversal) { + public static Set<String> getReferencedLabels(final Traversal.Admin<?, ?> traversal) { final Set<String> referencedLabels = new HashSet<>(); for(final Step<?, ?> step : traversal.getSteps()) { referencedLabels.addAll(getReferencedLabels(step)); @@ -42,13 +42,13 @@ public class PathUtil { return referencedLabels; } - public static Set<String> getReferencedLabels(Step step) { + public static Set<String> getReferencedLabels(final Step step) { final Set<String> referencedLabels = new HashSet<>(); if (step instanceof Parameterizing) { Parameters parameters = ((Parameterizing) step).getParameters(); - for (Traversal.Admin trav : parameters.getTraversals()) { - for (Object ss : trav.getSteps()) { + for (final Traversal.Admin trav : parameters.getTraversals()) { + for (final Object ss : trav.getSteps()) { if (ss instanceof Scoping) { Set<String> labels = ((Scoping) ss).getScopeKeys(); for (String label : labels) { @@ -60,7 +60,7 @@ public class PathUtil { } if (step instanceof Scoping) { - Set<String> labels = new HashSet<>(((Scoping) step).getScopeKeys()); + final Set<String> labels = new HashSet<>(((Scoping) step).getScopeKeys()); if (step instanceof MatchStep) { // if this is the last step, keep everything, else just add founds if (step.getNextStep() instanceof EmptyStep) { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/f9c6ea62/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java index e510066..b064b47 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java @@ -26,6 +26,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor; import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; +import org.apache.tinkerpop.gremlin.structure.Graph; import org.junit.Test; import org.junit.runner.RunWith; import org.junit.runners.Parameterized; @@ -48,45 +49,48 @@ import static org.junit.Assert.assertEquals; @RunWith(Parameterized.class) public class PrunePathStrategyTest { + private final List<TraversalStrategies> strategies = Arrays.asList( + new DefaultTraversalStrategies().addStrategies(PrunePathStrategy.instance()), + new DefaultTraversalStrategies().addStrategies(PrunePathStrategy.instance(), PathProcessorStrategy.instance()), + new DefaultTraversalStrategies().addStrategies(PrunePathStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance()), + new DefaultTraversalStrategies().addStrategies(PrunePathStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance(), RepeatUnrollStrategy.instance()), + TraversalStrategies.GlobalCache.getStrategies(Graph.class)); + @Parameterized.Parameter(value = 0) public Traversal.Admin traversal; @Parameterized.Parameter(value = 1) public List<Set<String>> labels; - void applyPrunePathStrategy(final Traversal traversal) { - final TraversalStrategies strategies = new DefaultTraversalStrategies(); - strategies.addStrategies(PrunePathStrategy.instance()); - traversal.asAdmin().setStrategies(strategies); - traversal.asAdmin().applyStrategies(); - } - @Test public void doTest() { - applyPrunePathStrategy(traversal); - // get all path processors - List<Object> keepLabels = getKeepLabels(traversal); - - assertEquals(labels, keepLabels); + for (final TraversalStrategies currentStrategies : this.strategies) { + final Traversal.Admin<?, ?> currentTraversal = this.traversal.clone(); + currentTraversal.setStrategies(currentStrategies); + System.out.println(currentStrategies); + currentTraversal.applyStrategies(); + final List<Object> keepLabels = getKeepLabels(currentTraversal); + assertEquals(this.labels, keepLabels); + } } - private List<Object> getKeepLabels(Traversal.Admin traversal) { + private List<Object> getKeepLabels(final Traversal.Admin<?, ?> traversal) { List<Object> keepLabels = new ArrayList<>(); - for(Step step : (List<Step>)traversal.getSteps()) { - if(step instanceof PathProcessor) { + for (Step step : traversal.getSteps()) { + if (step instanceof PathProcessor) { final Set<String> keepers = ((PathProcessor) step).getKeepLabels(); - if(keepers != null) { + if (keepers != null) { keepLabels.add(keepers); } } - if(step instanceof TraversalParent) { - TraversalParent parent = (TraversalParent) step; - List<Traversal.Admin<?, ?>> children = new ArrayList<>(); + if (step instanceof TraversalParent) { + final TraversalParent parent = (TraversalParent) step; + final List<Traversal.Admin<?, ?>> children = new ArrayList<>(); children.addAll(parent.getGlobalChildren()); children.addAll(parent.getLocalChildren()); - for(Traversal.Admin<?, ?> child : children) { - List<Object> childLabels = getKeepLabels(child); - if(childLabels.size() > 0) { + for (final Traversal.Admin<?, ?> child : children) { + final List<Object> childLabels = getKeepLabels(child); + if (childLabels.size() > 0) { keepLabels.add(childLabels); } } @@ -99,20 +103,27 @@ public class PrunePathStrategyTest { public static Iterable<Object[]> generateTestParameters() { return Arrays.asList(new Object[][]{ - {__.V().as("a").out().as("b").where(neq("a")).out(), Arrays.asList(Collections.EMPTY_SET)}, - {__.V().as("a").out().where(neq("a")).out().select("a"), Arrays.asList(Collections.singleton("a"), Collections.EMPTY_SET)}, + {__.out(), Arrays.asList()}, + {__.V().as("a").out().as("b").where(neq("a")).out(), Arrays.asList(Collections.emptySet())}, + {__.V().as("a").out().where(neq("a")).out().select("a"), Arrays.asList(Collections.singleton("a"), Collections.emptySet())}, + {__.V().as("a").out().as("b").where(neq("a")).out().select("a", "b").out().select("b"), Arrays.asList(new HashSet<>(Arrays.asList("a", "b")), Collections.singleton("b"), Collections.emptySet())}, {__.V().match(__.as("a").out().as("b")), Arrays.asList(new HashSet<>(Arrays.asList("a", "b")))}, - {__.V().match(__.as("a").out().as("b")).select("a"), Arrays.asList(new HashSet<>(Arrays.asList("a", "b")), Collections.EMPTY_SET)}, + {__.V().match(__.as("a").out().as("b")).select("a"), Arrays.asList(new HashSet<>(Arrays.asList("a", "b")), Collections.emptySet())}, {__.V().out().out().match( as("a").in("created").as("b"), as("b").in("knows").as("c")).select("c").out("created").where(neq("a")).values("name"), - Arrays.asList(new HashSet<>(Arrays.asList("a", "b", "c")), Collections.singleton("a"), Collections.EMPTY_SET)}, + Arrays.asList(new HashSet<>(Arrays.asList("a", "b", "c")), Collections.singleton("a"), Collections.emptySet())}, {__.V().as("a").out().select("a").path(), Arrays.asList()}, - {__.V().as("a").out().select("a").subgraph("b"), Arrays.asList()}, - {__.V().out().as("a").where(neq("a")).out().where(neq("a")), Arrays.asList(Collections.singleton("a"), Collections.EMPTY_SET)}, - {__.V().out().as("a").where(__.out().select("a").values("prop").count().is(gte(1))).out().where(neq("a")), Arrays.asList(Arrays.asList(Collections.singleton("a")), Collections.EMPTY_SET)}, + {__.V().as("a").out().select("a").subgraph("b"), Arrays.asList(Collections.emptySet())}, + {__.V().as("a").out().select("a").subgraph("b").select("a"), Arrays.asList(Collections.singleton("a"), Collections.emptySet())}, + {__.V().out().as("a").where(neq("a")).out().where(neq("a")).out(), Arrays.asList(Collections.singleton("a"), Collections.emptySet())}, + {__.V().out().as("a").where(__.out().select("a").values("prop").count().is(gte(1))).out().where(neq("a")), Arrays.asList(Arrays.asList(Collections.singleton("a")), Collections.emptySet())}, + {__.V().as("a").out().as("b").where(__.out().select("a", "b", "c").values("prop").count().is(gte(1))).out().where(neq("a")).out().select("b"), + Arrays.asList(Arrays.asList(new HashSet<>(Arrays.asList("a", "b", "c"))), Collections.singleton("b"), Collections.emptySet())}, {__.outE().inV().group().by(__.inE().outV().groupCount().by(__.both().count().is(P.gt(2)))), Arrays.asList()}, - {__.V().as("a").repeat(__.out().where(neq("a"))).emit().select("a").values("test"), Arrays.asList(Arrays.asList(Collections.singleton("a")), Collections.EMPTY_SET)} + {__.V().as("a").repeat(__.out().where(neq("a"))).emit().select("a").values("test"), Arrays.asList(Arrays.asList(Collections.singleton("a")), Collections.emptySet())}, + // given the way this test harness is structured, I have to manual test for RepeatUnrollStrategy (and it works) TODO: add more test parameters + // {__.V().as("a").repeat(__.out().where(neq("a"))).times(3).select("a").values("test"), Arrays.asList(Collections.singleton("a"), Collections.singleton("a"), Collections.singleton("a"), Collections.emptySet())} }); } }
