Prune path work.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/e4e693e4 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/e4e693e4 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/e4e693e4 Branch: refs/heads/TINKERPOP-1254-final Commit: e4e693e4655358cb94be6909751d2094bb1bc521 Parents: a138d55 Author: Ted Wilmes <twil...@gmail.com> Authored: Thu Jul 7 12:59:23 2016 -0500 Committer: Ted Wilmes <twil...@gmail.com> Committed: Thu Jul 7 12:59:23 2016 -0500 ---------------------------------------------------------------------- .../gremlin/process/traversal/Path.java | 8 + .../process/traversal/TraversalStrategies.java | 4 +- .../gremlin/process/traversal/Traverser.java | 6 + .../process/traversal/step/PathProcessor.java | 17 ++ .../traversal/step/filter/DedupGlobalStep.java | 16 ++ .../step/filter/WherePredicateStep.java | 32 ++- .../step/filter/WhereTraversalStep.java | 15 + .../process/traversal/step/map/MatchStep.java | 159 ++++++++++- .../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 | 204 +++++++++++++ .../traversal/step/util/ImmutablePathUtil.java | 37 +++ .../traversal/step/util/MutablePath.java | 37 ++- .../optimization/PrunePathStrategy.java | 285 +++++++++++++++++++ .../traverser/B_LP_O_S_SE_SL_Traverser.java | 42 +++ .../traverser/LP_O_OB_P_S_SE_SL_Traverser.java | 26 ++ .../traverser/util/AbstractTraverser.java | 16 ++ .../traverser/util/EmptyTraverser.java | 15 + .../process/traversal/util/PathUtil.java | 80 ++++++ .../gremlin/process/traversal/PathTest.java | 12 + .../traversal/step/map/MatchStepTest.java | 46 +++ .../optimization/PrunePathStrategyTest.java | 120 ++++++++ .../groovy/loaders/SugarLoaderTest.groovy | 20 +- .../structure/TinkerGraphPlayTest.java | 126 +++++++- 28 files changed, 1378 insertions(+), 16 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e4e693e4/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/e4e693e4/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/e4e693e4/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/e4e693e4/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..9282571 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,18 @@ public interface PathProcessor { } return max; } + + void setKeepLabels(final Set<String> labels); + + static void keepLabels(final Traverser traverser, final Set<String> labels) { + if(labels == null) { + return; + } else { +// final Set<String> keepers = traverser.asAdmin().getTags(); +// keepers.addAll(labels); + traverser.asAdmin().keepLabels(labels); + } + } + + Set<String> getKeepLabels(); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e4e693e4/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..ab5e687 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,18 @@ public final class DedupGlobalStep<S> extends FilterStep<S> implements Traversal } @Override + public void setKeepLabels(Set<String> labels) { + this.keepLabels = labels; + } + + @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 +206,7 @@ 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 Set<String> getKeepLabels() { return this.keepLabels; } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e4e693e4/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..4162716 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,32 @@ 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(); + // add traverser tags in +// Set<String> labels = new HashSet<>(); +// labels.addAll(traverser.getTags()); +// if(keepLabels != null ) labels.addAll(keepLabels); +// if(keepLabels != null) System.out.println(labels); +// System.out.println(traverser); +// System.out.println("Before: " + traverser.path().labels()); +// System.out.println("Keeping: " + keepLabels); +// System.out.println("IN: " + traverser.path().labels()); + PathProcessor.keepLabels(traverser, keepLabels); +// System.out.println("OUT: " + traverser.path().labels()); +// System.out.println("After: " + traverser.path().labels()); + 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/e4e693e4/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..5ba7004 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,10 @@ 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; + + @Override + public Set<String> getKeepLabels() { return this.keepLabels; } public WhereTraversalStep(final Traversal.Admin traversal, final Traversal<?, ?> whereTraversal) { super(traversal); @@ -88,6 +92,17 @@ public final class WhereTraversalStep<S> extends FilterStep<S> implements Traver ElementRequirement.ID; } + @Override + public void setKeepLabels(Set<String> keepLabels) { + this.keepLabels = keepLabels; + } + + @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) { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e4e693e4/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..5f262bd 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.*; @@ -44,7 +45,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 +61,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 +137,8 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } + + public ConnectiveStep.Connective getConnective() { return this.connective; } @@ -318,11 +322,14 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> if (this.connective == ConnectiveStep.Connective.AND) { final Traversal.Admin<Object, Object> matchTraversal = this.getMatchAlgorithm().apply(traverser); + // drop any labels that we can +// dropUnnecessaryLabels(traverser, matchTraversal); traverser.getTags().add(matchTraversal.getStartStep().getId()); matchTraversal.addStart(traverser); // determine which sub-pattern the traverser should try next } else { // OR for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) { final Traverser.Admin split = traverser.split(); +// dropUnnecessaryLabels(traverser, matchTraversal); split.getTags().add(matchTraversal.getStartStep().getId()); matchTraversal.addStart(split); } @@ -331,6 +338,28 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } + private void dropUnnecessaryLabels(final Traverser.Admin<Object> traverser, + final Traversal.Admin matchTraversal) { + if(keepLabels == null) { + return; + } + final List<Traversal.Admin> remainingTraversals = getRemainingTraversals(traverser); + remainingTraversals.add(matchTraversal); + HashSet<String> requiredLabels = new HashSet<>(); + remainingTraversals.stream().forEach(trav -> { + getRequiredLabels(trav, requiredLabels); + }); + requiredLabels.addAll(keepLabels); + if(dedupLabels != null) { + requiredLabels.addAll(dedupLabels); + } + requiredLabels.add(matchTraversal.getStartStep().getId()); +// System.out.println(requiredLabels); +// System.out.println("Before:\t" + traverser.path().labels() + "\t" + traverser.path().objects()); + traverser.keepLabels(requiredLabels); +// System.out.println("After:\t" + traverser.path().labels() + "\t" + traverser.path().objects()); + } + @Override protected Iterator<Traverser.Admin<Map<String, E>>> computerAlgorithm() throws NoSuchElementException { while (true) { @@ -353,11 +382,13 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> final Traversal.Admin<Object, Object> matchTraversal = this.getMatchAlgorithm().apply(traverser); // determine which sub-pattern the traverser should try next traverser.getTags().add(matchTraversal.getStartStep().getId()); traverser.setStepId(matchTraversal.getStartStep().getId()); // go down the traversal match sub-pattern +// dropUnnecessaryLabels(traverser, matchTraversal); return IteratorUtils.of(traverser); } else { // OR final List<Traverser.Admin<Map<String, E>>> traversers = new ArrayList<>(this.matchTraversals.size()); for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) { final Traverser.Admin split = traverser.split(); +// dropUnnecessaryLabels(traverser, matchTraversal); split.getTags().add(matchTraversal.getStartStep().getId()); split.setStepId(matchTraversal.getStartStep().getId()); traversers.add(split); @@ -368,6 +399,57 @@ 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 { + // see if we're currently in it + for(Object s : matchTraversal.getSteps()) { + if(((Step)s).getId().equals(traverser.getStepId())) { + remainingTraversals.add(matchTraversal); + break; + } + } +// matchTraversal.getSteps().stream().forEach(step -> { +// +// if(((Step)step).getId().equals(traverser.getStepId())) { +// found = true; +// } +// if(found) { +// remainingTraversals.add(matchTraversal); +// } +// }); + } + } +// System.out.println("Remaining: " + remainingTraversals); + return remainingTraversals; + } + + private void getRequiredLabels(Traversal.Admin trav, Set<String> requiredLabels) { + trav.getSteps().stream().forEach(step -> { +// if(step instanceof Scoping) { +// requiredLabels.addAll(((Scoping) step).getScopeKeys()); +// } + if(step instanceof PathProcessor) { + //Set<String> keep = ((PathProcessor) step).getKeepLabels(); + //if(keep != null) requiredLabels.addAll(keep); + } else if(step instanceof Scoping) { + Set<String> keep = ((Scoping)step).getScopeKeys(); + if(keep != null) requiredLabels.addAll(keep); + } + if(step instanceof TraversalParent) { + TraversalParent parent = (TraversalParent) step; + List<Traversal.Admin<Object, Object>> children = new ArrayList<>(parent.getGlobalChildren()); + children.addAll(parent.getLocalChildren()); + children.stream().forEach(child -> getRequiredLabels(child, requiredLabels)); + } + }); + } + @Override public int hashCode() { int result = super.hashCode() ^ this.connective.hashCode(); @@ -382,6 +464,44 @@ 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(); + // remove labels that we don't need +// System.out.println("KEEPERS: " + keepLabels); + if(keepLabels != null) { + // add traverser tags in + Set<String> labels = new HashSet<>(); + // determine which tags to keep vs. drop by looking at which labels still exist in the path + // + +// labels.addAll(getMatchStartLabels()); +// labels.addAll(getMatchEndLabels()); +// if (keepLabels != null) System.out.println(labels); + List<Traversal.Admin> remainingTraversals = getRemainingTraversals(traverser); +// System.out.println("REMAINING: " + remainingTraversals.size()); +// if(remainingTraversals.size() == 1) { +// // also remove tags... +// System.out.println("Before droppppping: " + traverser.path().labels()); +// traverser.dropLabels(traverser.getTags()); +// System.out.println("DROPPPPPING TAGS: " + traverser.path().labels()); +// } +// System.out.println("none"); + for (Traversal.Admin trav : remainingTraversals) { + getRequiredLabels(trav, labels); + } +// labels.addAll(traverser.getTags()); + if (keepLabels != null) labels.addAll(keepLabels); +// System.out.println(labels); +// System.out.println("Before: " + traverser.path().labels()); +// System.out.println("Keepers: " + labels); + PathProcessor.keepLabels(traverser, labels); +// System.out.println("After: " + traverser.path().labels()); +// } + } + return traverser; + } + ////////////////////////////// public static class MatchStartStep extends AbstractStep<Object, Object> implements Scoping { @@ -517,7 +637,14 @@ 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) { + String traversalId = traversal.getStartStep().getId(); +// System.out.println("Tag drop: " + traverser.path().labels()); + traverser.dropLabels(Collections.singleton(traversalId)); +// System.out.println(traverser.path().labels()); + } + return hasExecuted; } public static TraversalType getTraversalType(final Traversal.Admin<Object, Object> traversal) { @@ -678,4 +805,32 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } } + + @Override + public void setKeepLabels(Set<String> labels) { +// System.out.println("MATCH KEEP: " + 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/e4e693e4/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/e4e693e4/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/e4e693e4/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/e4e693e4/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/e4e693e4/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/e4e693e4/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/e4e693e4/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..156cd61 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 @@ -22,10 +22,13 @@ import org.apache.tinkerpop.gremlin.process.traversal.Path; import org.apache.tinkerpop.gremlin.process.traversal.Pop; import java.io.Serializable; +import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Collections; +import java.util.HashSet; import java.util.LinkedHashSet; import java.util.List; +import java.util.Queue; import java.util.Set; /** @@ -75,6 +78,201 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo return new ImmutablePath(this.previousPath, this.currentObject, temp); } +// @Override + public Path retract3(final Set<String> retractLabels) { + if(retractLabels == null || retractLabels.isEmpty()) { + return this; + } + + List<Set<String>> labelList = this.labels(); + boolean found = false; + for(Set<String> labelSet : labelList) { + if (!Collections.disjoint(labelSet, retractLabels)) { + found = true; + break; + } + } + if(!found) { + return this; + } + return this; + } + + private Path retract(final Set<String> labels, final List<Path> pathTrail) { + + Path current = pathTrail.get(0); + if (current instanceof TailPath) { + // return head + return pathTrail.get(pathTrail.size() - 1); + } else { + ImmutablePath immutablePath = (ImmutablePath) current; + if(!Collections.disjoint(labels, immutablePath.currentLabels)) { + // clone all the way back up and replace parents + ImmutablePath parentPath = null; + for(int i = pathTrail.size() - 1; i > 0; i--) { + ImmutablePath clonedPath = cloneImmutablePath((ImmutablePath)pathTrail.get(i)); + if(parentPath != null) { + parentPath.previousPath = clonedPath; + } + parentPath = clonedPath; + pathTrail.set(i, clonedPath); + } + ImmutablePath clonedCurrent = cloneImmutablePath(immutablePath); + clonedCurrent.currentLabels.removeAll(labels); + if(clonedCurrent.currentLabels.isEmpty()) { + if(pathTrail.size() > 1) { + ((ImmutablePath) pathTrail.get(1)).previousPath = clonedCurrent.previousPath; + } else { + pathTrail.remove(0); + } + } + pathTrail.add(clonedCurrent.previousPath); + } else { + pathTrail.add(((ImmutablePath) pathTrail.get(0)).previousPath); + } + retract(labels, pathTrail); + } + return null; + } + + @Override + public Path retract(final Set<String> labels) { + if(labels == null || labels.isEmpty()) { + return this; + } + +// System.out.println("RETRACTING: " + labels); +// +// labels.removeIf(val -> (val.indexOf("0") >= 0)); +// +// System.out.println("AFTER LABELS: " + labels); + + ImmutablePath parent; + ImmutablePath child; + + // 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) { + // nothing to do here... + 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; + } + + 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)) { +// child.currentLabels.removeAll(labels); + } else { + parents.add(child); + if(child.previousPath instanceof TailPath) { + // nothing to see...we're done here + 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(previous == null) { + if(clone.currentLabels.isEmpty()) { + lastPath.previousPath = clone.previousPath; + } else { + lastPath.previousPath = clone; + } + // hack! +// break; +// } + + parents = new ArrayList<>(); + headFound = true; + parents.add(lastPath); + + if(child.previousPath instanceof TailPath) { + // nothing to see...we're done here + 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 +393,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/e4e693e4/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePathUtil.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePathUtil.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePathUtil.java new file mode 100644 index 0000000..4b7259b --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePathUtil.java @@ -0,0 +1,37 @@ +/* + * 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.step.util; + +import org.apache.tinkerpop.gremlin.process.traversal.Pop; + +import java.util.Set; + +/** + * Created by twilmes on 4/11/16. + */ +public class ImmutablePathUtil { + + public static ImmutablePath retract(final ImmutablePath path, final Set<String> labels) { + // walk back through immutable path. Drop labels that are our list + for(final String label : labels) { + path.get(Pop.first, label); + } + return null; + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e4e693e4/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..ba1a6ca 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 @@ -24,10 +24,13 @@ import org.apache.tinkerpop.gremlin.process.traversal.Pop; import java.io.Serializable; import java.util.ArrayList; import java.util.Collections; +import java.util.Comparator; +import java.util.HashSet; import java.util.Iterator; import java.util.LinkedHashSet; import java.util.List; import java.util.Set; +import java.util.stream.Collectors; /** * @author Marko A. Rodriguez (http://markorodriguez.com) @@ -80,7 +83,39 @@ 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) { + +// removeLabels.removeIf(val -> (val.indexOf("0") >= 0)); + +// System.out.println("Removing: " + 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).contains(label)) { + this.labels.get(i).remove(label); +// System.out.println("REMOVED: " + 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/e4e693e4/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..5581463 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java @@ -0,0 +1,285 @@ +/* + * 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.Parameterizing; +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.Scoping; +import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep; +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.step.util.Parameters; +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.ArrayList; +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; + } + + private void setKeepLabels(final Traversal.Admin<?, ?> traversal, final Set<String> keepLabels) { + final List<Step> steps = traversal.getSteps(); + for(int i = steps.size() - 1; i >= 0; i--) { + final Step step = steps.get(i); + if (step instanceof PathProcessor) { +// System.out.println("Keeping: " + keepLabels); + if(keepLabels == null) { + ((PathProcessor) step).setKeepLabels(null); + } else { + ((PathProcessor) step).setKeepLabels(new HashSet<>(keepLabels)); + } + } + Set<String> referencedLabels = PathUtil.getReferencedLabels(step); + if(step instanceof MatchStep && step.getNextStep() instanceof EmptyStep) { + ((PathProcessor) step).setKeepLabels(referencedLabels); + } else if (step instanceof MatchStep) { + keepLabels.addAll(referencedLabels); + } + + if(step instanceof TraversalParent) { + TraversalParent traversalParent = ((TraversalParent) step); + final List<Traversal.Admin<?, ?>> subTraversals = new ArrayList<>(); + subTraversals.addAll(traversalParent.getLocalChildren()); + subTraversals.addAll(traversalParent.getGlobalChildren()); + HashSet<String> keepers = new HashSet<>(); + for(final Traversal.Admin<?, ?> subTraversal : subTraversals) { + if(keepLabels != null) { + keepers.addAll(keepLabels); + keepers.addAll(referencedLabels); + if(step instanceof MatchStep) { +// System.out.println(step); + keepers.addAll(((MatchStep)step).getMatchStartLabels()); + keepers.addAll(((MatchStep)step).getMatchEndLabels()); + } + setKeepLabels(subTraversal, keepers); + } else { + setKeepLabels(subTraversal, null); + } + } + } + if(keepLabels != null) { + keepLabels.addAll(referencedLabels); + } + } + } + +// @Override + public void apply3(final Traversal.Admin<?, ?> traversal) { + 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; + } + + // This is a bit weird at this point because the strategy application already happens in a recursive fashion + // but we shortcut that for this strategy because we want to be able to collect all of the referenced labels + // at all levels of the traversal and then set the keep labels accordingly for each PathProcessor + if(!(traversal.getParent() instanceof EmptyStep)) { + return; + } + + Set<String> keepLabels = null; + if(!hasPathStep) { + keepLabels = new HashSet<>(); + } + + setKeepLabels(traversal, keepLabels); + } + + protected Set<String> getParentReferencedLabels(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 the top level? If so, walk forwards and gather labels from that point forward + 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); +// System.out.println("Adding referenced labels." + labels); + if(topLevelParent) { + topLevelLabels.addAll(labels); + } else { + referencedLabels.addAll(labels); + } + step = step.getNextStep(); +// System.out.println(step); + } while(!(step.equals(EmptyStep.instance()))); + if(topLevelParent) { + step = parent; + do { + if(step instanceof PathProcessor) { + ((PathProcessor) step).getKeepLabels().addAll(referencedLabels); +// System.out.println("Added keep labels to: " + step); + } + 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 = getParentReferencedLabels(traversal); + keepLabels.addAll(labels); + } + } + + // check if the traversal contains any path or subgraph steps and + 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 Parameterizing) { +// Parameters parameters = ((Parameterizing) currentStep).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) { +// if (foundLabels.contains(label)) { +// keepLabels.add(label); +// } else { +// // it'll get added later, b/c we can drop after this step +// foundLabels.add(label); +// } +// } +// } +// } +// } +// } +// +// if (currentStep instanceof Scoping) { +// Set<String> labels = new HashSet<>(((Scoping) currentStep).getScopeKeys()); +// if (currentStep instanceof MatchStep) { +// // if this is the last step, keep everything, else just add founds +// if (currentStep.getNextStep() instanceof EmptyStep) { +// labels.addAll(((MatchStep) currentStep).getMatchEndLabels()); +// labels.addAll(((MatchStep) currentStep).getMatchStartLabels()); +// } +// } +// for (final String label : labels) { +// if (foundLabels.contains(label)) { +// keepLabels.add(label); +// } else { +// foundLabels.add(label); +// } +// } +// } + if (currentStep instanceof PathProcessor) { +// if (i != traversal.getSteps().size()) { +// // add in all match labels +// ((PathProcessor) currentStep).setKeepLabels(new HashSet<>(foundLabels)); +// } + ((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/e4e693e4/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/e4e693e4/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..87cfd21 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,30 @@ 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) { + 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/e4e693e4/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/e4e693e4/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/e4e693e4/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..c38a5be --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/util/PathUtil.java @@ -0,0 +1,80 @@ +/* + * 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.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.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.List; +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/e4e693e4/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..db60497 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,18 @@ 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")); + // todo add object assert to check retract behavior }); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e4e693e4/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/e4e693e4/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..3d13ad7 --- /dev/null +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java @@ -0,0 +1,120 @@ +/* + * 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 java.util.function.Function; + +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; +import static org.junit.Assert.assertNull; + +/** + * @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)} + }); + } +}
