TINKERPOP-1254 Support dropping traverser path information when it is no longer needed
This commit adds support for path retraction to increase the likelihood of bulking in OLTP and OLAP modes. Traversal analysis is performed during the application of the PrunePathStrategy to identify labels that may be dropped at various points in the traversal. MatchStep also performs runtime analysis to determine which labels it can drop in addition to the labels identified during traversal strategy application. Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/88c5d27b Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/88c5d27b Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/88c5d27b Branch: refs/heads/TINKERPOP-1254 Commit: 88c5d27bd4d0e2bb898be7f4c3a86007d6422174 Parents: a138d55 Author: Ted Wilmes <twil...@gmail.com> Authored: Fri Jul 8 07:37:41 2016 -0500 Committer: Ted Wilmes <twil...@gmail.com> Committed: Fri Jul 8 07:37:41 2016 -0500 ---------------------------------------------------------------------- .../gremlin/process/traversal/Path.java | 8 + .../process/traversal/TraversalStrategies.java | 4 +- .../gremlin/process/traversal/Traverser.java | 6 + .../process/traversal/step/PathProcessor.java | 15 ++ .../traversal/step/filter/DedupGlobalStep.java | 16 ++ .../step/filter/WherePredicateStep.java | 21 ++- .../step/filter/WhereTraversalStep.java | 15 ++ .../process/traversal/step/map/MatchStep.java | 78 ++++++++- .../process/traversal/step/map/PathStep.java | 16 ++ .../traversal/step/map/SelectOneStep.java | 18 ++ .../process/traversal/step/map/SelectStep.java | 16 ++ .../process/traversal/step/map/TreeStep.java | 9 + .../step/sideEffect/TreeSideEffectStep.java | 9 + .../process/traversal/step/util/EmptyPath.java | 3 + .../traversal/step/util/ImmutablePath.java | 126 ++++++++++++++ .../traversal/step/util/MutablePath.java | 33 +++- .../optimization/PrunePathStrategy.java | 172 +++++++++++++++++++ .../traverser/B_LP_O_S_SE_SL_Traverser.java | 42 +++++ .../traverser/LP_O_OB_P_S_SE_SL_Traverser.java | 28 +++ .../traverser/util/AbstractTraverser.java | 16 ++ .../traverser/util/EmptyTraverser.java | 15 ++ .../process/traversal/util/PathUtil.java | 77 +++++++++ .../gremlin/process/traversal/PathTest.java | 11 ++ .../traversal/step/map/MatchStepTest.java | 46 +++++ .../optimization/PrunePathStrategyTest.java | 118 +++++++++++++ .../structure/TinkerGraphPlayTest.java | 16 +- 26 files changed, 925 insertions(+), 9 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Path.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Path.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Path.java index a302165..c4bc347 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Path.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Path.java @@ -66,6 +66,14 @@ public interface Path extends Cloneable, Iterable<Object> { public Path extend(final Set<String> labels); /** + * Remove labels from path. + * + * @param labels the labels to remove + * @return the path with removed labels + */ + public Path retract(final Set<String> labels); + + /** * Get the object associated with the particular label of the path. * If the path as multiple labels of the type, then return a {@link List} of those objects. * http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 b093676..850db9f 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 @@ -29,6 +29,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.Inci import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.MatchPredicateStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.OrderLimitStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PathProcessorStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PrunePathStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.RangeByIsCountStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.RepeatUnrollStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.verification.ComputerVerificationStrategy; @@ -197,7 +198,8 @@ public interface TraversalStrategies extends Serializable, Cloneable { RepeatUnrollStrategy.instance(), RangeByIsCountStrategy.instance(), ProfileStrategy.instance(), - StandardVerificationStrategy.instance()); + StandardVerificationStrategy.instance(), + PrunePathStrategy.instance()); GRAPH_CACHE.put(Graph.class, graphStrategies); GRAPH_CACHE.put(EmptyGraph.class, new DefaultTraversalStrategies()); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traverser.java index 0a36b2c..0c37a34 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traverser.java @@ -183,6 +183,12 @@ public interface Traverser<T> extends Serializable, Comparable<Traverser<T>>, Cl public void addLabels(final Set<String> labels); + public void keepLabels(final Set<String> labels); + + public void dropLabels(final Set<String> labels); + + public void dropPath(); + /** * Set the current object location of the traverser. * http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 48a9cc3..7d8a497 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 @@ -19,11 +19,14 @@ package 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.ElementValueTraversal; import org.apache.tinkerpop.gremlin.process.traversal.lambda.IdentityTraversal; import org.apache.tinkerpop.gremlin.process.traversal.lambda.TokenTraversal; import org.apache.tinkerpop.gremlin.structure.T; +import java.util.Set; + /** * @author Marko A. Rodriguez (http://markorodriguez.com) */ @@ -56,4 +59,16 @@ public interface PathProcessor { } return max; } + + 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); + } + } + + Set<String> getKeepLabels(); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 9336a1a..78fd429 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 @@ -56,6 +56,7 @@ public final class DedupGlobalStep<S> extends FilterStep<S> implements Traversal private Set<Object> duplicateSet = new HashSet<>(); private boolean onGraphComputer = false; private final Set<String> dedupLabels; + private Set<String> keepLabels; public DedupGlobalStep(final Traversal.Admin traversal, final String... dedupLabels) { super(traversal); @@ -81,6 +82,13 @@ 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; + } + + @Override public List<Traversal<S, Object>> getLocalChildren() { return null == this.dedupTraversal ? Collections.emptyList() : Collections.singletonList(this.dedupTraversal); } @@ -193,4 +201,12 @@ public final class DedupGlobalStep<S> extends FilterStep<S> implements Traversal public MemoryComputeKey<Map<Object, Traverser.Admin<S>>> getMemoryComputeKey() { return MemoryComputeKey.of(this.getId(), (BinaryOperator) Operator.addAll, false, true); } + + @Override + public void setKeepLabels(Set<String> labels) { + this.keepLabels = labels; + } + + @Override + public Set<String> getKeepLabels() { return this.keepLabels; } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 6fea7d6..0ee7832 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 @@ -22,6 +22,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.P; import org.apache.tinkerpop.gremlin.process.traversal.Pop; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; 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.traverser.TraverserRequirement; import org.apache.tinkerpop.gremlin.process.traversal.util.ConnectiveP; @@ -33,12 +34,13 @@ import java.util.*; /** * @author Marko A. Rodriguez (http://markorodriguez.com) */ -public final class WherePredicateStep<S> extends FilterStep<S> implements Scoping { +public final class WherePredicateStep<S> extends FilterStep<S> implements Scoping, PathProcessor { protected String startKey; protected List<String> selectKeys; protected P<Object> predicate; protected final Set<String> scopeKeys = new HashSet<>(); + protected Set<String> keepLabels; public WherePredicateStep(final Traversal.Admin traversal, final Optional<String> startKey, final P<String> predicate) { super(traversal); @@ -115,4 +117,21 @@ public final class WherePredicateStep<S> extends FilterStep<S> implements Scopin TYPICAL_GLOBAL_REQUIREMENTS : TYPICAL_LOCAL_REQUIREMENTS; } + + @Override + protected Traverser.Admin<S> processNextStart() { + final Traverser.Admin<S> traverser = super.processNextStart(); + PathProcessor.keepLabels(traverser, keepLabels); + return traverser; + } + + @Override + public void setKeepLabels(Set<String> labels) { + this.keepLabels = labels; + } + + @Override + public Set<String> getKeepLabels() { + return this.keepLabels; + } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 388104d..078a370 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 @@ -46,6 +46,7 @@ public final class WhereTraversalStep<S> extends FilterStep<S> implements Traver protected Traversal.Admin<?, ?> whereTraversal; protected final Set<String> scopeKeys = new HashSet<>(); + protected Set<String> keepLabels; public WhereTraversalStep(final Traversal.Admin traversal, final Traversal<?, ?> whereTraversal) { super(traversal); @@ -88,6 +89,12 @@ public final class WhereTraversalStep<S> extends FilterStep<S> implements Traver ElementRequirement.ID; } + @Override + protected Traverser.Admin<S> processNextStart() { + final Traverser.Admin<S> traverser = super.processNextStart(); + PathProcessor.keepLabels(traverser, keepLabels); + return traverser; + } @Override protected boolean filter(final Traverser.Admin<S> traverser) { @@ -134,6 +141,14 @@ public final class WhereTraversalStep<S> extends FilterStep<S> implements Traver TYPICAL_LOCAL_REQUIREMENTS; } + @Override + public void setKeepLabels(Set<String> keepLabels) { + this.keepLabels = keepLabels; + } + + @Override + public Set<String> getKeepLabels() { return this.keepLabels; } + ////////////////////////////// public static class WhereStartStep<S> extends MapStep<S, Object> implements Scoping { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 c6e3bbe..3fb45fc 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 @@ -19,6 +19,7 @@ package org.apache.tinkerpop.gremlin.process.traversal.step.map; import org.apache.tinkerpop.gremlin.process.traversal.*; +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.*; @@ -30,6 +31,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.util.ReducingBarrierS import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.ConnectiveStrategy; import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement; import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal; +import org.apache.tinkerpop.gremlin.process.traversal.util.PathUtil; import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; import org.apache.tinkerpop.gremlin.structure.util.StringFactory; import org.apache.tinkerpop.gremlin.util.iterator.IteratorUtils; @@ -44,7 +46,7 @@ import java.util.stream.Stream; /** * @author Marko A. Rodriguez (http://markorodriguez.com) */ -public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> implements TraversalParent, Scoping { +public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> implements TraversalParent, Scoping, PathProcessor { public enum TraversalType {WHERE_PREDICATE, WHERE_TRAVERSAL, MATCH_TRAVERSAL} @@ -60,6 +62,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> private Set<List<Object>> dedups = null; private Set<String> dedupLabels = null; + private Set<String> keepLabels = null; public MatchStep(final Traversal.Admin traversal, final ConnectiveStep.Connective connective, final Traversal... matchTraversals) { super(traversal); @@ -135,6 +138,8 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } + + public ConnectiveStep.Connective getConnective() { return this.connective; } @@ -368,6 +373,26 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } + 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) { + 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()) { + if (s.getId().equals(traverser.getStepId())) { + remainingTraversals.add(matchTraversal); + break; + } + } + } + } + return remainingTraversals; + } + @Override public int hashCode() { int result = super.hashCode() ^ this.connective.hashCode(); @@ -382,6 +407,21 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> return this.getSelfAndChildRequirements(TraverserRequirement.LABELED_PATH, TraverserRequirement.SIDE_EFFECTS); } + @Override + protected Traverser.Admin<Map<String, E>> processNextStart() throws NoSuchElementException { + final Traverser.Admin<Map<String, E>> traverser = super.processNextStart(); + if (keepLabels != null) { + final Set<String> keepers = new HashSet<>(); + List<Traversal.Admin> remainingTraversals = getRemainingTraversals(traverser); + for (Traversal.Admin trav : remainingTraversals) { + keepers.addAll(PathUtil.getReferencedLabels(trav)); + } + keepers.addAll(keepLabels); + PathProcessor.keepLabels(traverser, keepers); + } + return traverser; + } + ////////////////////////////// public static class MatchStartStep extends AbstractStep<Object, Object> implements Scoping { @@ -517,7 +557,13 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } public static boolean hasExecutedTraversal(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) { - return traverser.getTags().contains(traversal.getStartStep().getId()); + final boolean hasExecuted = traverser.getTags().contains(traversal.getStartStep().getId()); + if (hasExecuted) { + // This traverser has finished this traversal so it is safe to drop the tag label. + String traversalId = traversal.getStartStep().getId(); + traverser.dropLabels(Collections.singleton(traversalId)); + } + return hasExecuted; } public static TraversalType getTraversalType(final Traversal.Admin<Object, Object> traversal) { @@ -552,7 +598,6 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } return 0; }); - //System.out.println(sort); return sort.get(0); } } @@ -678,4 +723,31 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } } + + @Override + public void setKeepLabels(Set<String> labels) { + if (this.keepLabels != null) { + this.keepLabels.addAll(labels); + } else { + this.keepLabels = new HashSet<>(labels); + } + } + + @Override + public Set<String> getKeepLabels() { + // add in start and end labels for this match b/c it's children may need to keep them + HashSet<String> keepThese = new HashSet<>(); + if (keepLabels != null) { + keepThese.addAll(this.keepLabels); + } + keepThese.addAll(this.getMatchStartLabels()); + keepThese.addAll(this.getMatchEndLabels()); + return keepThese; + } + + public Set<String> getMatchEndLabels() { + return this.matchEndLabels; + } + + public Set<String> getMatchStartLabels() { return this.matchStartLabels; } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 039c2a9..885afc1 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 @@ -39,6 +39,7 @@ import java.util.Set; public final class PathStep<S> extends MapStep<S, Path> implements TraversalParent, PathProcessor, ByModulating { private TraversalRing<Object, Object> traversalRing; + private Set<String> keepLabels; public PathStep(final Traversal.Admin traversal) { super(traversal); @@ -101,4 +102,19 @@ public final class PathStep<S> extends MapStep<S, Path> implements TraversalPare public Set<TraverserRequirement> getRequirements() { return this.getSelfAndChildRequirements(TraverserRequirement.PATH); } + + @Override + public void setKeepLabels(Set<String> labels) { + this.keepLabels = labels; + } + + @Override + protected Traverser.Admin<Path> processNextStart() { + final Traverser.Admin<Path> traverser = super.processNextStart(); + PathProcessor.keepLabels(traverser, keepLabels); + return traverser; + } + + @Override + public Set<String> getKeepLabels() { return this.keepLabels; } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 fa38903..3bd5c1d 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 @@ -42,6 +42,7 @@ public final class SelectOneStep<S, E> extends MapStep<S, E> implements Traversa private final Pop pop; private final String selectKey; private Traversal.Admin<S, E> selectTraversal = null; + private Set<String> keepLabels; public SelectOneStep(final Traversal.Admin traversal, Pop pop, final String selectKey) { super(traversal); @@ -115,6 +116,23 @@ public final class SelectOneStep<S, E> extends MapStep<S, E> implements Traversa public Pop getPop() { return this.pop; } + + @Override + public void setKeepLabels(Set<String> labels) { + this.keepLabels = labels; + } + + @Override + public Set<String> getKeepLabels() { return this.keepLabels; } + + @Override + protected Traverser.Admin<E> processNextStart() { + final Traverser.Admin<E> traverser = super.processNextStart(); + if(!(this.getTraversal().getParent() instanceof MatchStep)) { + PathProcessor.keepLabels(traverser, keepLabels); + } + return traverser; + } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 af8cfdb..ecd5581 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 @@ -49,6 +49,7 @@ public final class SelectStep<S, E> extends MapStep<S, Map<String, E>> implement private final Pop pop; private final List<String> selectKeys; private final Set<String> selectKeysSet; + private Set<String> keepLabels; public SelectStep(final Traversal.Admin traversal, final Pop pop, final String... selectKeys) { super(traversal); @@ -141,4 +142,19 @@ public final class SelectStep<S, E> extends MapStep<S, Map<String, E>> implement public Pop getPop() { return this.pop; } + + @Override + public void setKeepLabels(Set<String> labels) { + this.keepLabels = labels; + } + + @Override + 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; + } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java index 3573b98..a3fb054 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/TreeStep.java @@ -44,6 +44,7 @@ import java.util.function.Supplier; public final class TreeStep<S> extends ReducingBarrierStep<S, Tree> implements TraversalParent, ByModulating, PathProcessor { private TraversalRing<Object, Object> traversalRing = new TraversalRing<>(); + private Set<String> keepLabels; public TreeStep(final Traversal.Admin traversal) { super(traversal); @@ -111,6 +112,14 @@ public final class TreeStep<S> extends ReducingBarrierStep<S, Tree> implements T this.traversalRing.reset(); } + @Override + public void setKeepLabels(Set<String> labels) { + this.keepLabels = labels; + } + + @Override + public Set<String> getKeepLabels() { return this.keepLabels; } + /////////// public static final class TreeBiOperator implements BinaryOperator<Tree>, Serializable { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 18a4798..6351455 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 @@ -44,6 +44,7 @@ public final class TreeSideEffectStep<S> extends SideEffectStep<S> implements Si private TraversalRing<Object, Object> traversalRing; private String sideEffectKey; + private Set<String> keepLabels; public TreeSideEffectStep(final Traversal.Admin traversal, final String sideEffectKey) { super(traversal); @@ -115,4 +116,12 @@ public final class TreeSideEffectStep<S> extends SideEffectStep<S> implements Si public Set<TraverserRequirement> getRequirements() { return this.getSelfAndChildRequirements(TraverserRequirement.PATH, TraverserRequirement.SIDE_EFFECTS); } + + @Override + public void setKeepLabels(Set<String> labels) { + this.keepLabels = labels; + } + + @Override + public Set<String> getKeepLabels() { return this.keepLabels; } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/EmptyPath.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/EmptyPath.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/EmptyPath.java index c40f228..0c6827e 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/EmptyPath.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/EmptyPath.java @@ -52,6 +52,9 @@ public final class EmptyPath implements Path, Serializable { } @Override + public Path retract(final Set<String> labels) { return this; } + + @Override public <A> A get(final String label) { throw Path.Exceptions.stepWithProvidedLabelDoesNotExist(label); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java index 1e936c8..68ee2b9 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java @@ -24,6 +24,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.Pop; import java.io.Serializable; import java.util.ArrayList; import java.util.Collections; +import java.util.HashSet; import java.util.LinkedHashSet; import java.util.List; import java.util.Set; @@ -76,6 +77,125 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo } @Override + public Path retract(final Set<String> labels) { + if (labels == null || labels.isEmpty()) { + return this; + } + + // first see if the labels in the set are even present in this path + boolean found = false; + for (final Set<String> labelSet : labels()) { + if (!Collections.disjoint(labelSet, labels)) { + found = true; + break; + } + } + + if (!found) { + return this; + } + + if (this.previousPath instanceof TailPath) { + ImmutablePath clone = cloneImmutablePath(this); + clone.currentLabels.removeAll(labels); + clone.previousPath = TailPath.instance(); + if (clone.currentLabels.isEmpty()) { + // return the previous tail path because this path segment can be dropped + return clone.previousPath; + } + return clone; + } + + ImmutablePath parent; + ImmutablePath child; + if (this.previousPath != null) { + parent = this; + child = (ImmutablePath)this.previousPath; + } else { + parent = (ImmutablePath)this.previousPath; + child = this; + } + + if (!Collections.disjoint(parent.currentLabels, labels)) { + ImmutablePath clonedParent = cloneImmutablePath(parent); + clonedParent.currentLabels.removeAll(labels); + if (clonedParent.currentLabels.isEmpty()) { + parent = (ImmutablePath) parent.previousPath; + } else { + parent = clonedParent; + } + } + + // store the head and return it at the end of this + ImmutablePath head = parent; + + // parents can be a mixture of ImmutablePaths and collapsed + // cloned ImmutablePaths that are a result of branching + List<Object> parents = new ArrayList<>(); + parents.add(parent); + + while(true) { + if (Collections.disjoint(child.currentLabels, labels)) { + parents.add(child); + if (child.previousPath instanceof TailPath) { + break; + } + child = (ImmutablePath)child.previousPath; + continue; + } + // split path + // clone child + ImmutablePath clone = cloneImmutablePath(child); + clone.currentLabels.removeAll(labels); + if (clone.currentLabels.isEmpty()) { + clone.currentObject = null; + } + + // walk back up and build parent clones or reuse + // other previously cloned paths + boolean headFound = false; + if (parents.size() > 0) { + boolean first = true; + // construct parents up to this point + ImmutablePath newPath = cloneImmutablePath((ImmutablePath)parents.get(0)); + // replace the previous + ImmutablePath prevPath = newPath; + ImmutablePath lastPath = prevPath; + if (!headFound) { + head = newPath; + } + for (int i = 1; i < parents.size(); i++) { + ImmutablePath clonedPrev = cloneImmutablePath((ImmutablePath) parents.get(i)); + prevPath.previousPath = clonedPrev; + lastPath = clonedPrev; + prevPath = clonedPrev; + } + + if (clone.currentLabels.isEmpty()) { + lastPath.previousPath = clone.previousPath; + } else { + lastPath.previousPath = clone; + } + + parents = new ArrayList<>(); + parents.add(lastPath); + + if (child.previousPath instanceof TailPath) { + break; + } + + child = (ImmutablePath)child.previousPath; + } + } + + return head; + } + + private static ImmutablePath cloneImmutablePath(final ImmutablePath path) { + return new ImmutablePath(path.previousPath, path.currentObject, new HashSet<>(path.currentLabels)); + } + + @Override public <A> A get(final int index) { return (this.size() - 1) == index ? (A) this.currentObject : this.previousPath.get(index); } @@ -195,6 +315,12 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo @Override public Path extend(final Set<String> labels) { + if (labels.size() == 0) { return this; } + throw new UnsupportedOperationException("A head path can not have labels added to it"); + } + + @Override + public Path retract(final Set<String> labels) { throw new UnsupportedOperationException("A head path can not have labels added to it"); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java index 0a35f90..02d95c1 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java @@ -80,7 +80,38 @@ public class MutablePath implements Path, Serializable { @Override public Path extend(final Set<String> labels) { - this.labels.get(this.labels.size() - 1).addAll(labels); + if(labels.size() > 0) { + this.labels.get(this.labels.size() - 1).addAll(labels); + } + return this; + } + + @Override + public Path retract(final Set<String> removeLabels) { + for (int i = this.labels.size() - 1; i >= 0; i--) { + for (final String label : removeLabels) { + synchronized (this.labels.get(i)) { + if (this.labels.get(i).isEmpty()) { + this.labels.remove(i); + this.objects.remove(i); + continue; + } + if (this.labels.get(i).contains(label)) { + this.labels.get(i).remove(label); + boolean empty = false; + if (this.labels.get(i).size() == 0) { + this.labels.remove(i); + this.objects.remove(i); + empty = true; + } + // label was found, so break out + if (empty) { + break; + } + } + } + } + } return this; } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 new file mode 100644 index 0000000..ebb6b66 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java @@ -0,0 +1,172 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization; + +import org.apache.tinkerpop.gremlin.process.traversal.Step; +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.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.util.PathUtil; +import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; + +import java.util.Collections; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +/** + * @author Ted Wilmes (http://twilmes.org) + */ +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); + } + + private PrunePathStrategy() { + } + + public static PrunePathStrategy instance() { + return INSTANCE; + } + + protected Set<String> getAndPropagateReferencedLabels(final Traversal.Admin<?, ?> traversal) { + if (traversal.getParent().equals(EmptyStep.instance())) { + return Collections.EMPTY_SET; + } + Step<?, ?> parent = traversal.getParent().asStep(); + Set<String> referencedLabels = new HashSet<>(); + // get referenced labels from this traversal + referencedLabels.addAll(PathUtil.getReferencedLabels(traversal)); + Set<String> topLevelLabels = new HashSet<>(); + while (true) { + // is this parent step in the top level traversal? If so, walk forwards and gather labels + // that should be kept because they are required in latter parts of the traversal + Step<?, ?> step; + boolean topLevelParent = false; + if (parent.getTraversal().getParent().equals(EmptyStep.instance())) { + step = parent; + topLevelParent = true; + } else { + // start at the beginning of the traversal + step = parent.getTraversal().getStartStep(); + } + do { + Set<String> labels = PathUtil.getReferencedLabels(step); + if (topLevelParent) { + topLevelLabels.addAll(labels); + } else { + referencedLabels.addAll(labels); + } + step = step.getNextStep(); + } while(!(step.equals(EmptyStep.instance()))); + if (topLevelParent) { + step = parent; + do { + // if this is the top level traversal, propagate all nested labels + // to previous PathProcess steps + if (step instanceof PathProcessor) { + ((PathProcessor) step).getKeepLabels().addAll(referencedLabels); + } + step = step.getPreviousStep(); + } while (!(step.equals(EmptyStep.instance()))); + break; + } else { + parent = parent.getTraversal().getParent().asStep(); + } + } + referencedLabels.addAll(topLevelLabels); + return referencedLabels; + } + + @Override + public void apply(final Traversal.Admin<?, ?> traversal) { + TraversalParent parent = traversal.getParent(); + + Set<String> foundLabels = new HashSet<>(); + 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, + // walk back up to the top level traversal and work forwards to determine which labels + // must be kept. + 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); + } + } + + // check if the traversal contains any path or subgraph 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 List<Step> steps = traversal.getSteps(); + for(int i = steps.size() - 1; i >= 0; i--) { + Step currentStep = steps.get(i); + if (!hasPathStep) { + // maintain our list of labels to keep, repeatedly adding labels that were found during + // the last iteration + keepLabels.addAll(foundLabels); + + final Set<String> labels = PathUtil.getReferencedLabels(currentStep); + for (final String label : labels) { + if (foundLabels.contains(label)) { + keepLabels.add(label); + } else { + foundLabels.add(label); + } + } + + 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 + ((PathProcessor) currentStep).setKeepLabels(null); + } + } + } + } + + @Override + public Set<Class<? extends OptimizationStrategy>> applyPrior() { + return PRIORS; + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java index b32126b..793ead6 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java @@ -23,8 +23,11 @@ import org.apache.tinkerpop.gremlin.process.traversal.Pop; import org.apache.tinkerpop.gremlin.process.traversal.Step; import org.apache.tinkerpop.gremlin.process.traversal.Traverser; import org.apache.tinkerpop.gremlin.process.traversal.step.util.ImmutablePath; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.MutablePath; import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceFactory; +import java.util.HashSet; +import java.util.List; import java.util.Set; /** @@ -85,6 +88,45 @@ public class B_LP_O_S_SE_SL_Traverser<T> extends B_O_S_SE_SL_Traverser<T> { } @Override + public void keepLabels(final Set<String> labels) { + if (!labels.isEmpty()) { + Set<String> retractLabels = new HashSet<>(); + List<Set<String>> existingLabels = this.path.labels(); + for(Set<String> labelSet : existingLabels) { + for(String l : labelSet) { + if(labels.contains(l) == false) { retractLabels.add(l); }; + } + } + this.path = this.path.retract(retractLabels); + } else if (labels.isEmpty()) { + Set<String> retractLabels = new HashSet<>(); + List<Set<String>> existingLabels = this.path.labels(); + for(Set<String> labelSet : existingLabels) { + retractLabels.addAll(labelSet); + } + if(!retractLabels.isEmpty()) { + this.path = this.path.retract(retractLabels); + } + } + } + + @Override + public void dropLabels(final Set<String> labels) { + if(!labels.isEmpty()) { + this.path = this.path.retract(labels); + } + } + + @Override + public void dropPath() { + if(path instanceof ImmutablePath) { + this.path = ImmutablePath.make(); + } else { + this.path = MutablePath.make(); + } + } + + @Override public int hashCode() { return super.hashCode() + this.path.hashCode(); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java index 353d1ef..2e13a33 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java @@ -25,6 +25,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traverser; import org.apache.tinkerpop.gremlin.process.traversal.step.util.ImmutablePath; import org.apache.tinkerpop.gremlin.structure.util.reference.ReferenceFactory; +import java.util.HashSet; +import java.util.List; import java.util.Set; /** @@ -81,6 +83,32 @@ public class LP_O_OB_P_S_SE_SL_Traverser<T> extends O_OB_S_SE_SL_Traverser<T> { } @Override + public void keepLabels(final Set<String> labels) { + if (!labels.isEmpty()) { + Set<String> retractLabels = new HashSet<>(); + List<Set<String>> existingLabels = this.path.labels(); + for(Set<String> labelSet : existingLabels) { + for(String l : labelSet) { + if(labels.contains(l) == false) { retractLabels.add(l); }; + } + } + this.path = this.path.retract(retractLabels); + } + } + + @Override + public void dropLabels(final Set<String> labels) { + if(!labels.isEmpty()) { + this.path = path.retract(new HashSet(labels)); + } + } + + @Override + public void dropPath() { + this.path = ImmutablePath.make(); + } + + @Override public int hashCode() { return super.hashCode() + this.path.hashCode(); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/AbstractTraverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/AbstractTraverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/AbstractTraverser.java index 1ced9ef..f23ac6e 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/AbstractTraverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/AbstractTraverser.java @@ -78,6 +78,22 @@ public abstract class AbstractTraverser<T> implements Traverser<T>, Traverser.Ad } @Override + public void keepLabels(final Set<String> labels) { + + } + + @Override + public void dropLabels(final Set<String> labesl) { + + } + + @Override + public void dropPath() { + + } + + + @Override public void set(final T t) { this.t = t; } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/EmptyTraverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/EmptyTraverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/EmptyTraverser.java index da391f5..7c99cb5 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/EmptyTraverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/EmptyTraverser.java @@ -50,6 +50,21 @@ public final class EmptyTraverser<T> implements Traverser<T>, Traverser.Admin<T> } @Override + public void keepLabels(final Set<String> labels) { + + } + + @Override + public void dropLabels(final Set<String> labels) { + + } + + @Override + public void dropPath() { + + } + + @Override public void set(final T t) { } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 new file mode 100644 index 0000000..d07de50 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java @@ -0,0 +1,77 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.tinkerpop.gremlin.process.traversal.util; + +import org.apache.tinkerpop.gremlin.process.traversal.Parameterizing; +import org.apache.tinkerpop.gremlin.process.traversal.Step; +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.step.Scoping; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.Parameters; + +import java.util.HashSet; +import java.util.Set; + +/** + * @author Ted Wilmes (http://twilmes.org) + */ +public class PathUtil { + + public static Set<String> getReferencedLabels(Traversal.Admin<?, ?> traversal) { + final Set<String> referencedLabels = new HashSet<>(); + for(final Step<?, ?> step : traversal.getSteps()) { + referencedLabels.addAll(getReferencedLabels(step)); + } + return referencedLabels; + } + + public static Set<String> getReferencedLabels(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()) { + if (ss instanceof Scoping) { + Set<String> labels = ((Scoping) ss).getScopeKeys(); + for (String label : labels) { + referencedLabels.add(label); + } + } + } + } + } + + if (step instanceof Scoping) { + 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) { + labels.addAll(((MatchStep) step).getMatchEndLabels()); + labels.addAll(((MatchStep) step).getMatchStartLabels()); + } + } + referencedLabels.addAll(labels); + + } + + return referencedLabels; + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java index 66c1a4d..21f1ec8 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java @@ -76,6 +76,17 @@ public class PathTest { assertEquals(Integer.valueOf(2), path.get(1)); assertEquals(Integer.valueOf(3), path.get(2)); assertEquals(Integer.valueOf(3), path.get(3)); + Path retractedPath = path.retract(Collections.singleton("f")); + assertFalse(path.hasLabel("f")); + assertEquals(retractedPath, path); + path = path.retract(Collections.singleton("b")); + assertFalse(path.hasLabel("b")); + path = path.retract(Collections.singleton("a")); + assertFalse(path.hasLabel("a")); + assertTrue(path.hasLabel("d")); + path = path.retract(new HashSet<>(Arrays.asList("c", "d"))); + assertFalse(path.hasLabel("c")); + assertFalse(path.hasLabel("d")); }); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java index 37e70bf..e47ab4b 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java @@ -21,17 +21,23 @@ package org.apache.tinkerpop.gremlin.process.traversal.step.map; import org.apache.tinkerpop.gremlin.process.traversal.P; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.TraversalEngine; +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies; import org.apache.tinkerpop.gremlin.process.traversal.Traverser; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; +import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor; import org.apache.tinkerpop.gremlin.process.traversal.step.StepTest; import org.apache.tinkerpop.gremlin.process.traversal.step.filter.CoinStep; import org.apache.tinkerpop.gremlin.process.traversal.step.filter.ConnectiveStep; 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.util.EmptyStep; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PrunePathStrategy; import org.apache.tinkerpop.gremlin.process.traversal.traverser.B_LP_O_P_S_SE_SL_TraverserGenerator; import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.EmptyTraverser; +import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; import org.apache.tinkerpop.gremlin.structure.T; +import org.apache.tinkerpop.gremlin.structure.Vertex; import org.junit.Test; import java.util.Arrays; @@ -418,4 +424,44 @@ public class MatchStepTest extends StepTest { as("b").in("created").count().is(P.gt(1))).asAdmin(); assertEquals("a", MatchStep.Helper.computeStartLabel(((MatchStep<?, ?>) traversal.getStartStep()).getGlobalChildren())); } + + @Test + public void testGetRemainingTraversals() { + Traverser.Admin traverser = B_LP_O_P_S_SE_SL_TraverserGenerator.instance().generate(1, EmptyStep.instance(), 1l); + traverser.addLabels(Collections.singleton("a")); + + Traversal<Object, Vertex> mTraversal1 = as("a").out().as("b"); + Traversal<Object, Vertex> mTraversal2 = as("b").out().as("c"); + Traversal<Object, Vertex> mTraversal3 = as("a").out().as("d"); + Traversal<Object, Vertex> mTraversal4 = as("c").out().as("e"); + Traversal<Object, Vertex> mTraversal5 = as("c").out().as("f"); + + + Traversal.Admin<?, ?> traversal = __.match( + mTraversal1, + mTraversal2, + mTraversal3, + mTraversal4, + mTraversal5).asAdmin(); + + final TraversalStrategies strategies = new DefaultTraversalStrategies(); + strategies.addStrategies(PrunePathStrategy.instance()); + traversal.asAdmin().setStrategies(strategies); + traversal.asAdmin().applyStrategies(); + + MatchStep matchStep = (MatchStep) traversal.getStartStep(); + assertEquals(new HashSet<>(Arrays.asList("a", "b", "c", "d", "e", "f")), matchStep.getKeepLabels()); + + traverser.getTags().add(mTraversal1.asAdmin().getStartStep().getId()); + traverser.setStepId(mTraversal2.asAdmin().getStartStep().getId()); + + List<Traversal.Admin<?, ?>> remainingTraversals = matchStep.getRemainingTraversals(traverser); + assertEquals(Arrays.asList(mTraversal2, mTraversal3, mTraversal4, mTraversal5), remainingTraversals); + + traverser.getTags().add(mTraversal2.asAdmin().getStartStep().getId()); + traverser.setStepId(mTraversal3.asAdmin().getStartStep().getId()); + + remainingTraversals = matchStep.getRemainingTraversals(traverser); + assertEquals(Arrays.asList(mTraversal3, mTraversal4, mTraversal5), remainingTraversals); + } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/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 new file mode 100644 index 0000000..e510066 --- /dev/null +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java @@ -0,0 +1,118 @@ +/* + * Licensed to the Apache Software Foundation (ASF) under one + * or more contributor license agreements. See the NOTICE file + * distributed with this work for additional information + * regarding copyright ownership. The ASF licenses this file + * to you under the Apache License, Version 2.0 (the + * "License"); you may not use this file except in compliance + * with the License. You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, + * software distributed under the License is distributed on an + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY + * KIND, either express or implied. See the License for the + * specific language governing permissions and limitations + * under the License. + */ +package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization; + +import org.apache.tinkerpop.gremlin.process.traversal.P; +import org.apache.tinkerpop.gremlin.process.traversal.Step; +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies; +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; +import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor; +import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; +import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; +import org.junit.Test; +import org.junit.runner.RunWith; +import org.junit.runners.Parameterized; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import static org.apache.tinkerpop.gremlin.process.traversal.P.gte; +import static org.apache.tinkerpop.gremlin.process.traversal.P.neq; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.as; +import static org.junit.Assert.assertEquals; + +/** + * @author Ted Wilmes (http://twilmes.org) + */ +@RunWith(Parameterized.class) +public class PrunePathStrategyTest { + + @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); + } + + private List<Object> getKeepLabels(Traversal.Admin traversal) { + List<Object> keepLabels = new ArrayList<>(); + for(Step step : (List<Step>)traversal.getSteps()) { + if(step instanceof PathProcessor) { + final Set<String> keepers = ((PathProcessor) step).getKeepLabels(); + if(keepers != null) { + keepLabels.add(keepers); + } + } + if(step instanceof TraversalParent) { + TraversalParent parent = (TraversalParent) step; + 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) { + keepLabels.add(childLabels); + } + } + } + } + return keepLabels; + } + + @Parameterized.Parameters(name = "{0}") + 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)}, + {__.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().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)}, + {__.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)}, + {__.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)} + }); + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/88c5d27b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java ---------------------------------------------------------------------- diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java index 7097b1c..d6dfa9a 100644 --- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java +++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java @@ -18,8 +18,8 @@ */ package org.apache.tinkerpop.gremlin.tinkergraph.structure; + import org.apache.tinkerpop.gremlin.process.traversal.Operator; -import org.apache.tinkerpop.gremlin.process.traversal.P; import org.apache.tinkerpop.gremlin.process.traversal.Scope; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; @@ -29,6 +29,7 @@ import org.apache.tinkerpop.gremlin.structure.Graph; import org.apache.tinkerpop.gremlin.structure.T; import org.apache.tinkerpop.gremlin.structure.Vertex; import org.apache.tinkerpop.gremlin.structure.io.graphml.GraphMLIo; + import org.apache.tinkerpop.gremlin.util.TimeUtil; import org.junit.Ignore; import org.junit.Test; @@ -40,6 +41,7 @@ import java.util.List; import java.util.function.Supplier; import static org.apache.tinkerpop.gremlin.process.traversal.P.lt; +import static org.apache.tinkerpop.gremlin.process.traversal.P.neq; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.as; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.both; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.choose; @@ -52,7 +54,6 @@ import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.outE; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.select; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.union; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.valueMap; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.values; /** * @author Stephen Mallette (http://stephen.genoprime.com) @@ -262,7 +263,7 @@ public class TinkerGraphPlayTest { as("a").in("writtenBy").as("b"), as("b").out("followedBy").as("c"), as("c").out("writtenBy").as("d"), - as("d").where(P.neq("a"))).select("a", "b", "c", "d").by("name"); + as("d").where(neq("a"))).select("a", "b", "c", "d").by("name"); logger.info(traversal.get().toString()); @@ -289,4 +290,13 @@ public class TinkerGraphPlayTest { graph.vertices(50).next().addEdge("uncle", graph.vertices(70).next()); logger.info(TimeUtil.clockWithResult(500, () -> g.V().match(as("a").out("knows").as("b"), as("a").out("uncle").as("b")).toList()).toString()); } + + @Test + public void testBugs() { + GraphTraversalSource g = TinkerFactory.createModern().traversal(); + + System.out.println(g.V().as("a").both().as("b").dedup("a", "b").by(T.label).select("a", "b").explain()); + System.out.println(g.V().as("a").both().as("b").dedup("a", "b").by(T.label).select("a", "b").toList()); + + } }
