renamed PrunePathStrategy to PathRetractionStrategy to better align with the Path API retract() naming. PathRetractionStrategy should NOT execute if there are lambdas steps or path steps. Do a global analysis to ensure that. Added a new MatchTest to ensure a sneaking suspicion I had with lazy barrier wasn't true -- it wasn't, thats good.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/01fd5dc5 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/01fd5dc5 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/01fd5dc5 Branch: refs/heads/TINKERPOP-1278 Commit: 01fd5dc507f9f135f458be32661c92f39569212f Parents: 983538d Author: Marko A. Rodriguez <okramma...@gmail.com> Authored: Mon Jul 11 09:49:28 2016 -0600 Committer: Marko A. Rodriguez <okramma...@gmail.com> Committed: Mon Jul 11 09:49:28 2016 -0600 ---------------------------------------------------------------------- .../process/traversal/TraversalStrategies.java | 4 +- .../process/traversal/step/map/MatchStep.java | 40 ++-- .../AdjacentToIncidentStrategy.java | 2 +- .../IncidentToAdjacentStrategy.java | 5 +- .../optimization/PathRetractionStrategy.java | 193 ++++++++++++++++++ .../optimization/PrunePathStrategy.java | 195 ------------------- .../traversal/step/map/MatchStepTest.java | 6 +- .../PathRetractionStrategyTest.java | 184 +++++++++++++++++ .../optimization/PrunePathStrategyTest.java | 183 ----------------- .../groovy/loaders/SugarLoaderTest.groovy | 12 +- .../traversal/step/map/GroovyMatchTest.groovy | 5 + .../process/traversal/step/map/MatchTest.java | 17 ++ .../structure/TinkerGraphPlayTest.java | 10 +- 13 files changed, 439 insertions(+), 417 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/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 ee3fa76..53b2e77 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,7 +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.PathRetractionStrategy; 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 +197,7 @@ public interface TraversalStrategies extends Serializable, Cloneable { MatchPredicateStrategy.instance(), RepeatUnrollStrategy.instance(), RangeByIsCountStrategy.instance(), - PrunePathStrategy.instance(), + PathRetractionStrategy.instance(), ProfileStrategy.instance(), StandardVerificationStrategy.instance()); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/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 813b85c..998b7d3 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 @@ -38,7 +38,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.util.ComputerAwareSte import org.apache.tinkerpop.gremlin.process.traversal.step.util.ProfileStep; import org.apache.tinkerpop.gremlin.process.traversal.step.util.ReducingBarrierStep; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.ConnectiveStrategy; -import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PrunePathStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PathRetractionStrategy; import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement; import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.TraverserSet; import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversal; @@ -180,6 +180,24 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } @Override + public void setKeepLabels(Set<String> labels) { + this.keepLabels = labels; + } + + @Override + public Set<String> getKeepLabels() { + return keepLabels; + } + + public Set<String> getMatchEndLabels() { + return this.matchEndLabels; + } + + public Set<String> getMatchStartLabels() { + return this.matchStartLabels; + } + + @Override public Set<String> getScopeKeys() { if (null == this.scopeKeys) { this.scopeKeys = new HashSet<>(); @@ -327,7 +345,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } else if (this.standardAlgorithmBarrier.isEmpty()) { for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) { while (matchTraversal.hasNext() && - this.standardAlgorithmBarrier.size() < PrunePathStrategy.MAX_BARRIER_SIZE) { // TODO: perhaps make MatchStep a LocalBarrierStep ?? + this.standardAlgorithmBarrier.size() < PathRetractionStrategy.DEFAULT_STANDARD_BARRIER_SIZE) { // TODO: perhaps make MatchStep a LocalBarrierStep ?? this.standardAlgorithmBarrier.add(matchTraversal.getEndStep().next()); } } @@ -752,22 +770,4 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } } - - @Override - public void setKeepLabels(Set<String> labels) { - this.keepLabels = labels; - } - - @Override - public Set<String> getKeepLabels() { - return keepLabels; - } - - public Set<String> getMatchEndLabels() { - return this.matchEndLabels; - } - - public Set<String> getMatchStartLabels() { - return this.matchStartLabels; - } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/AdjacentToIncidentStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/AdjacentToIncidentStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/AdjacentToIncidentStrategy.java index aace11a..2d19479 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/AdjacentToIncidentStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/AdjacentToIncidentStrategy.java @@ -67,7 +67,7 @@ public final class AdjacentToIncidentStrategy extends AbstractTraversalStrategy< } @Override - public void apply(Traversal.Admin<?, ?> traversal) { + public void apply(final Traversal.Admin<?, ?> traversal) { final List<Step> steps = traversal.getSteps(); final int size = steps.size() - 1; Step prev = null; http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java index 712110d..18e1c50 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/IncidentToAdjacentStrategy.java @@ -69,9 +69,8 @@ public final class IncidentToAdjacentStrategy extends AbstractTraversalStrategy< } @Override - public void apply(Traversal.Admin<?, ?> traversal) { - final Traversal.Admin root = TraversalHelper.getRootTraversal(traversal); - if (TraversalHelper.hasStepOfAssignableClassRecursively(INVALIDATING_STEP_CLASSES, root)) + public void apply(final Traversal.Admin<?, ?> traversal) { + if (TraversalHelper.hasStepOfAssignableClassRecursively(INVALIDATING_STEP_CLASSES, TraversalHelper.getRootTraversal(traversal))) return; final Collection<Pair<VertexStep, Step>> stepsToReplace = new ArrayList<>(); Step prev = null; http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java new file mode 100644 index 0000000..ee697f3 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategy.java @@ -0,0 +1,193 @@ +/* + * 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.Barrier; +import org.apache.tinkerpop.gremlin.process.traversal.step.LambdaHolder; +import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor; +import org.apache.tinkerpop.gremlin.process.traversal.step.branch.RepeatStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.filter.DedupGlobalStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.MapStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.map.NoOpBarrierStep; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement; +import org.apache.tinkerpop.gremlin.process.traversal.util.PathUtil; +import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; +import org.javatuples.Pair; + +import java.util.ArrayList; +import java.util.Arrays; +import java.util.Collections; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +/** + * @author Ted Wilmes (http://twilmes.org) + * @author Marko A. Rodriguez (http://markorodriguez.com) + */ +public final class PathRetractionStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> implements TraversalStrategy.OptimizationStrategy { + + public static Integer DEFAULT_STANDARD_BARRIER_SIZE = 2500; + + private static final PathRetractionStrategy INSTANCE = new PathRetractionStrategy(DEFAULT_STANDARD_BARRIER_SIZE); + // these strategies do strong rewrites involving path labeling and thus, should run prior to PathRetractionStrategy + private static final Set<Class<? extends OptimizationStrategy>> PRIORS = new HashSet<>(Arrays.asList( + RepeatUnrollStrategy.class, MatchPredicateStrategy.class, PathProcessorStrategy.class)); + + private final int standardBarrierSize; + + private PathRetractionStrategy(final int standardBarrierSize) { + this.standardBarrierSize = standardBarrierSize; + } + + public static PathRetractionStrategy instance() { + return INSTANCE; + } + + @Override + public void apply(final Traversal.Admin<?, ?> traversal) { + // do not apply this strategy if there are lambdas as you can't introspect to know what path information the lambdas are using + // do not apply this strategy if a PATH requirement step is being used (in the future, we can do PATH requirement lookhead to be more intelligent about its usage) + if (TraversalHelper.anyStepRecursively(step -> step instanceof LambdaHolder || step.getRequirements().contains(TraverserRequirement.PATH), TraversalHelper.getRootTraversal(traversal))) + return; + + final boolean onGraphComputer = TraversalHelper.onGraphComputer(traversal); + final Set<String> foundLabels = new HashSet<>(); + final Set<String> keepLabels = new HashSet<>(); + + final List<Step> steps = traversal.getSteps(); + for (int i = steps.size() - 1; i >= 0; i--) { + final Step currentStep = steps.get(i); + // 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); + } + // add the keep labels to the path processor + if (currentStep instanceof PathProcessor) { + final PathProcessor pathProcessor = (PathProcessor) currentStep; + if (currentStep instanceof MatchStep && (currentStep.getNextStep().equals(EmptyStep.instance()) || currentStep.getNextStep() instanceof DedupGlobalStep)) { + pathProcessor.setKeepLabels(((MatchStep) currentStep).getMatchStartLabels()); + pathProcessor.getKeepLabels().addAll(((MatchStep) currentStep).getMatchEndLabels()); + } else + pathProcessor.setKeepLabels(new HashSet<>(keepLabels)); + + if (currentStep.getTraversal().getParent() instanceof MatchStep) { + pathProcessor.setKeepLabels(((MatchStep) currentStep.getTraversal().getParent().asStep()).getMatchStartLabels()); + pathProcessor.getKeepLabels().addAll(((MatchStep) currentStep.getTraversal().getParent().asStep()).getMatchEndLabels()); + } + + // OLTP barrier optimization that will try and bulk traversers after a path processor step to thin the stream + if (!onGraphComputer && + !(currentStep.getNextStep() instanceof Barrier) && + !(currentStep.getTraversal().getParent() instanceof MatchStep)) + TraversalHelper.insertAfterStep(new NoOpBarrierStep<>(traversal, this.standardBarrierSize), currentStep, traversal); + } + } + + keepLabels.addAll(foundLabels); + + // build a list of parent traversals and their required labels + Step<?, ?> parent = traversal.getParent().asStep(); + final List<Pair<Step, Set<String>>> parentKeeperPairs = new ArrayList<>(); + while (!parent.equals(EmptyStep.instance())) { + parentKeeperPairs.add(new Pair<>(parent, PathUtil.whichLabelsReferencedFromHereForward(parent))); + parent = parent.getTraversal().getParent().asStep(); + } + + // reverse the parent traversal list so that labels are kept from the top down + Collections.reverse(parentKeeperPairs); + + boolean hasRepeat = false; + + final Set<String> keeperTrail = new HashSet<>(); + for (final Pair<Step, Set<String>> pair : parentKeeperPairs) { + Step step = pair.getValue0(); + final Set<String> levelLabels = pair.getValue1(); + + if (step instanceof RepeatStep) { + hasRepeat = true; + } + + // propagate requirements of keep labels back through the traversal's previous steps + // to ensure that the label is not dropped before it reaches the step(s) that require it + step = step.getPreviousStep(); + while (!(step.equals(EmptyStep.instance()))) { + if (step instanceof PathProcessor) { + if (((PathProcessor) step).getKeepLabels() == null) { + ((PathProcessor) step).setKeepLabels(new HashSet<>(keepLabels)); + } else { + ((PathProcessor) step).getKeepLabels().addAll(new HashSet<>(keepLabels)); + } + } + step = step.getPreviousStep(); + } + + // propagate keep labels forwards if future steps require a particular nested label + while (!(step.equals(EmptyStep.instance()))) { + if (step instanceof PathProcessor) { + final Set<String> referencedLabels = PathUtil.getReferencedLabelsAfterStep(step); + for (final String ref : referencedLabels) { + if (levelLabels.contains(ref)) { + if (((PathProcessor) step).getKeepLabels() == null) { + final HashSet<String> newKeepLabels = new HashSet<>(); + newKeepLabels.add(ref); + ((PathProcessor) step).setKeepLabels(newKeepLabels); + } else { + ((PathProcessor) step).getKeepLabels().addAll(Collections.singleton(ref)); + } + } + } + } + + step = step.getNextStep(); + } + + keeperTrail.addAll(levelLabels); + } + + for (final Step currentStep : traversal.getSteps()) { + // go back through current level and add all keepers + // if there is one more RepeatSteps in this traversal's lineage, preserve keep labels + if (currentStep instanceof PathProcessor) { + ((PathProcessor) currentStep).getKeepLabels().addAll(keeperTrail); + if (hasRepeat) { + ((PathProcessor) currentStep).getKeepLabels().addAll(keepLabels); + } + } + } + } + + @Override + public Set<Class<? extends OptimizationStrategy>> applyPrior() { + return PRIORS; + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/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 deleted file mode 100644 index b8a5b39..0000000 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java +++ /dev/null @@ -1,195 +0,0 @@ -/* - * 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.branch.RepeatStep; -import org.apache.tinkerpop.gremlin.process.traversal.step.filter.DedupGlobalStep; -import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep; -import org.apache.tinkerpop.gremlin.process.traversal.step.map.NoOpBarrierStep; -import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep; -import org.apache.tinkerpop.gremlin.process.traversal.step.util.ReducingBarrierStep; -import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy; -import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement; -import org.apache.tinkerpop.gremlin.process.traversal.util.PathUtil; -import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; -import org.javatuples.Pair; - -import java.util.ArrayList; -import java.util.Arrays; -import java.util.Collections; -import java.util.HashSet; -import java.util.List; -import java.util.Set; - -/** - * @author Ted Wilmes (http://twilmes.org) - * @author Marko A. Rodriguez (http://markorodriguez.com) - */ -public final class PrunePathStrategy extends AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> implements TraversalStrategy.OptimizationStrategy { - - public static Integer MAX_BARRIER_SIZE = 2500; - - private static final PrunePathStrategy INSTANCE = new PrunePathStrategy(); - // these strategies do strong rewrites involving path labeling and thus, should run prior to PrunePathStrategy - private static final Set<Class<? extends OptimizationStrategy>> PRIORS = new HashSet<>(Arrays.asList( - RepeatUnrollStrategy.class, MatchPredicateStrategy.class, PathProcessorStrategy.class)); - - private PrunePathStrategy() { - } - - public static PrunePathStrategy instance() { - return INSTANCE; - } - - @Override - public void apply(final Traversal.Admin<?, ?> traversal) { - final boolean onGraphComputer = TraversalHelper.onGraphComputer(traversal); - final Set<String> foundLabels = new HashSet<>(); - final Set<String> keepLabels = new HashSet<>(); - - // check if the traversal contains any PATH requiring steps and if - // it does, note it so that the keep labels are set to null - // which signals PathProcessors to not drop path information - final boolean hasPathStep = TraversalHelper.anyStepRecursively(step -> step.getRequirements().contains(TraverserRequirement.PATH), traversal); - if (hasPathStep) { - for (final Step<?, ?> step : traversal.getSteps()) { - if (step instanceof PathProcessor) { - ((PathProcessor) step).setKeepLabels(null); - } - } - return; - } - - final List<Step> steps = traversal.getSteps(); - for (int i = steps.size() - 1; i >= 0; i--) { - final Step currentStep = steps.get(i); - // 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); - } - // add the keep labels to the path processor - if (currentStep instanceof PathProcessor) { - PathProcessor pathProcessor = (PathProcessor) currentStep; - if (currentStep instanceof MatchStep && (currentStep.getNextStep().equals(EmptyStep.instance()) || currentStep.getNextStep() instanceof DedupGlobalStep)) { - pathProcessor.setKeepLabels(((MatchStep) currentStep).getMatchStartLabels()); - pathProcessor.getKeepLabels().addAll(((MatchStep) currentStep).getMatchEndLabels()); - } else - ((PathProcessor) currentStep).setKeepLabels(new HashSet<>(keepLabels)); - - if (currentStep.getTraversal().getParent() instanceof MatchStep) { - pathProcessor.setKeepLabels(((MatchStep) currentStep.getTraversal().getParent().asStep()).getMatchStartLabels()); - pathProcessor.getKeepLabels().addAll(((MatchStep) currentStep.getTraversal().getParent().asStep()).getMatchEndLabels()); - } - - // OLTP barrier optimization that will try and bulk traversers after a path processor step to thin the stream - if (!onGraphComputer && - !(currentStep.getNextStep() instanceof ReducingBarrierStep) && - !(currentStep.getNextStep() instanceof NoOpBarrierStep) && - !(currentStep.getTraversal().getParent() instanceof MatchStep)) - TraversalHelper.insertAfterStep(new NoOpBarrierStep<>(traversal, MAX_BARRIER_SIZE), currentStep, traversal); - } - } - - keepLabels.addAll(foundLabels); - - // build a list of parent traversals and their required labels - Step<?, ?> parent = traversal.getParent().asStep(); - final List<Pair<Step, Set<String>>> parentKeeperPairs = new ArrayList<>(); - while (!parent.equals(EmptyStep.instance())) { - parentKeeperPairs.add(new Pair<>(parent, PathUtil.whichLabelsReferencedFromHereForward(parent))); - parent = parent.getTraversal().getParent().asStep(); - } - - // reverse the parent traversal list so that labels are kept from the top down - Collections.reverse(parentKeeperPairs); - - boolean hasRepeat = false; - - final Set<String> keeperTrail = new HashSet<>(); - for (final Pair<Step, Set<String>> pair : parentKeeperPairs) { - Step step = pair.getValue0(); - final Set<String> levelLabels = pair.getValue1(); - - if (step instanceof RepeatStep) { - hasRepeat = true; - } - - // propagate requirements of keep labels back through the traversal's previous steps - // to ensure that the label is not dropped before it reaches the step(s) that require it - step = step.getPreviousStep(); - while (!(step.equals(EmptyStep.instance()))) { - if (step instanceof PathProcessor) { - if (((PathProcessor) step).getKeepLabels() == null) { - ((PathProcessor) step).setKeepLabels(new HashSet<>(keepLabels)); - } else { - ((PathProcessor) step).getKeepLabels().addAll(new HashSet<>(keepLabels)); - } - } - step = step.getPreviousStep(); - } - - // propagate keep labels forwards if future steps require a particular nested label - while (!(step.equals(EmptyStep.instance()))) { - if (step instanceof PathProcessor) { - final Set<String> referencedLabels = PathUtil.getReferencedLabelsAfterStep(step); - for (final String ref : referencedLabels) { - if (levelLabels.contains(ref)) { - if (((PathProcessor) step).getKeepLabels() == null) { - ((PathProcessor) step).setKeepLabels(new HashSet<>(Arrays.asList(ref))); - } else { - ((PathProcessor) step).getKeepLabels().addAll(new HashSet<>(Arrays.asList(ref))); - } - } - } - } - - step = step.getNextStep(); - } - - keeperTrail.addAll(levelLabels); - } - - for (final Step currentStep : traversal.getSteps()) { - // go back through current level and add all keepers - // if there is one more RepeatSteps in this traversal's lineage, preserve keep labels - if (currentStep instanceof PathProcessor) { - ((PathProcessor) currentStep).getKeepLabels().addAll(keeperTrail); - if (hasRepeat) { - ((PathProcessor) currentStep).getKeepLabels().addAll(keepLabels); - } - } - } - } - - @Override - public Set<Class<? extends OptimizationStrategy>> applyPrior() { - return PRIORS; - } -} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/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 e47ab4b..201207b 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 @@ -23,16 +23,14 @@ 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.strategy.optimization.PathRetractionStrategy; 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; @@ -445,7 +443,7 @@ public class MatchStepTest extends StepTest { mTraversal5).asAdmin(); final TraversalStrategies strategies = new DefaultTraversalStrategies(); - strategies.addStrategies(PrunePathStrategy.instance()); + strategies.addStrategies(PathRetractionStrategy.instance()); traversal.asAdmin().setStrategies(strategies); traversal.asAdmin().applyStrategies(); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java new file mode 100644 index 0000000..4404cfd --- /dev/null +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PathRetractionStrategyTest.java @@ -0,0 +1,184 @@ +/* + * 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.Order; +import org.apache.tinkerpop.gremlin.process.traversal.P; +import org.apache.tinkerpop.gremlin.process.traversal.Scope; +import org.apache.tinkerpop.gremlin.process.traversal.Step; +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.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.apache.tinkerpop.gremlin.structure.Graph; +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.List; +import java.util.Set; + +import static org.apache.tinkerpop.gremlin.process.traversal.P.eq; +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.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.limit; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.out; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.select; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.values; +import static org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PathRetractionStrategy.DEFAULT_STANDARD_BARRIER_SIZE; +import static org.junit.Assert.assertEquals; + +/** + * @author Ted Wilmes (http://twilmes.org) + * @author Marko A. Rodriguez (http://markorodriguez.com) + */ +@RunWith(Parameterized.class) +public class PathRetractionStrategyTest { + + private final List<TraversalStrategies> strategies = Arrays.asList( + new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance()), + new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance(), PathProcessorStrategy.instance()), + new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance()), + new DefaultTraversalStrategies().addStrategies(PathRetractionStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance(), RepeatUnrollStrategy.instance()), + TraversalStrategies.GlobalCache.getStrategies(Graph.class)); + + @Parameterized.Parameter(value = 0) + public Traversal.Admin traversal; + + @Parameterized.Parameter(value = 1) + public String labels; + + @Parameterized.Parameter(value = 2) + public Traversal.Admin optimized; + + @Test + public void doTest() { + for (final TraversalStrategies currentStrategies : this.strategies) { + final Traversal.Admin<?, ?> currentTraversal = this.traversal.clone(); + currentTraversal.setStrategies(currentStrategies); + currentTraversal.applyStrategies(); + assertEquals(this.labels, getKeepLabels(currentTraversal).toString()); + if (null != optimized) + assertEquals(currentTraversal, optimized); + } + } + + private List<Object> getKeepLabels(final Traversal.Admin<?, ?> traversal) { + List<Object> keepLabels = new ArrayList<>(); + for (Step step : traversal.getSteps()) { + if (step instanceof PathProcessor) { + final Set<String> keepers = ((PathProcessor) step).getKeepLabels(); + if (keepers != null) + keepLabels.add(keepers); + } + if (step instanceof TraversalParent) { + final TraversalParent parent = (TraversalParent) step; + final List<Traversal.Admin<?, ?>> children = new ArrayList<>(); + children.addAll(parent.getGlobalChildren()); + children.addAll(parent.getLocalChildren()); + for (final Traversal.Admin<?, ?> child : children) { + final 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[][]{ + {out(), "[]", null}, + {__.V().as("a").out().as("b").where(neq("a")).out(), "[[]]", null}, + {__.V().as("a").out().where(out().where(neq("a"))).out(), "[[[]]]", null}, + {__.V().as("a").out().where(neq("a")).out().select("a"), "[[a], []]", null}, + {__.V().as("a").out().as("b").where(neq("a")).out().select("a", "b").out().select("b"), "[[a, b], [b], []]", null}, + {__.V().match(__.as("a").out().as("b")), "[[a, b]]", null}, + {__.V().match(__.as("a").out().as("b")).select("a"), "[[a], []]", null}, + {__.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"), + "[[a, c], [a], []]", null}, + {__.V().as("a").out().select("a").path(), "[]", null}, + {__.V().as("a").out().select("a").map(t -> t.path().get("a")), "[]", null}, // lambda introspection is not possible + {__.V().as("a").out().select("a").subgraph("b"), "[[]]", null}, + {__.V().as("a").out().select("a").subgraph("b").select("a"), "[[a], []]", null}, + {__.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").path(), + "[]", null}, + {__.V().out().as("a").where(neq("a")).out().where(neq("a")).out(), "[[a], []]", null}, + {__.V().out().as("a").where(out().select("a").values("prop").count().is(gte(1))).out().where(neq("a")), "[[[a]], []]", null}, + {__.V().as("a").out().as("b").where(out().select("a", "b", "c").values("prop").count().is(gte(1))).out().where(neq("a")).out().select("b"), + "[[[a, b]], [b], []]", null}, + {__.outE().inV().group().by(__.inE().outV().groupCount().by(__.both().count().is(P.gt(2)))), "[]", null}, + {__.V().as("a").repeat(out().where(neq("a"))).emit().select("a").values("test"), "[[[a]], []]", null}, + // given the way this test harness is structured, I have to manual test for RepeatUnrollStrategy (and it works) TODO: add more test parameters + // {__.V().as("a").repeat(__.out().where(neq("a"))).times(3).select("a").values("test"), Arrays.asList(Collections.singleton("a"), Collections.singleton("a"), Collections.singleton("a"), Collections.emptySet())} + {__.V().as("a").out().as("b").select("a").out().out(), "[[]]", __.V().as("a").out().as("b").select("a").barrier(DEFAULT_STANDARD_BARRIER_SIZE).out().out()}, + {__.V().as("a").out().as("b").select("a").count(), "[[]]", __.V().as("a").out().as("b").select("a").count()}, + {__.V().as("a").out().as("b").select("a").barrier().count(), "[[]]", __.V().as("a").out().as("b").select("a").barrier().count()}, + {__.V().as("a").out().as("b").where(P.gt("a")).out().out(), "[[]]", __.V().as("a").out().as("b").where(P.gt("a")).barrier(DEFAULT_STANDARD_BARRIER_SIZE).out().out()}, + {__.V().as("a").out().as("b").where(P.gt("a")).count(), "[[]]", __.V().as("a").out().as("b").where(P.gt("a")).count()}, + {__.V().as("a").out().as("b").select("a").as("c").where(P.gt("b")).out(), "[[b], []]", __.V().as("a").out().as("b").select("a").as("c").barrier(DEFAULT_STANDARD_BARRIER_SIZE).where(P.gt("b")).barrier(DEFAULT_STANDARD_BARRIER_SIZE).out()}, + {__.V().select("c").map(select("c").map(select("c"))).select("c"), "[[c], [[c], [[c]]], []]", null}, + {__.V().select("c").map(select("c").map(select("c"))).select("b"), "[[b, c], [[b, c], [[b]]], []]", null}, + {__.V().as("a").out().as("b").select("a").select("b").union( + as("c").out().as("d", "e").select("c", "e").out().select("c"), + as("c").out().as("d", "e").select("c", "e").out().select("c")). + out().select("c"), + "[[b, c, e], [c, e], [[c], [c]], [[c], [c]], []]", null}, + {__.V().as("a").out().as("b").select("a").select("b"). + local(as("c").out().as("d", "e").select("c", "e").out().select("c")). + out().select("c"), + "[[b, c, e], [c, e], [[c], [c]], []]", null}, + // TODO: same as above but note how path() makes things react +// {__.V().as("a").out().as("b").select("a").select("b").path().local(as("c").out().as("d", "e").select("c", "e").out().select("c")).out().select("c"), +// "[[[c, e], [c, e]]]", null}, + {__.V().as("a").out().as("b").select("a").select("b").repeat(out().as("c").select("b", "c").out().select("c")).out().select("c").out().select("b"), + "[[b, c], [b, c], [[b, c], [b, c]], [b], []]", null}, + {__.V().as("a").out().as("b").select("a").select("b").repeat(out().as("c").select("b")).out().select("c").out().select("b"), + "[[b, c], [b, c], [[b, c]], [b], []]", null}, + {__.V().as("a").out().as("b").select("a").select("b").repeat(out().as("c").select("b")), + "[[b], [b], [[b]]]", null}, + {__.V().select("a").map(select("c").map(select("b"))).select("c"), + "[[b, c], [[b, c], [[c]]], []]", null}, + {__.V().select("a").map(select("b").repeat(select("c"))).select("a"), + "[[a, b, c], [[a, c], [[a, c]]], []]", null}, + {__.V().select("c").map(select("c").map(select("c"))).select("c"), "[[c], [[c], [[c]]], []]", null}, + {__.V().select("c").map(select("c").map(select("c"))).select("b"), "[[b, c], [[b, c], [[b]]], []]", null}, + {__.V().select("a").map(select("c").map(select("b"))).select("c"), + "[[b, c], [[b, c], [[c]]], []]", null}, + {__.V().select("a").map(select("b").repeat(select("c"))).select("a"), + "[[a, b, c], [[a, c], [[a, c]]], []]", null}, + {__.V().out("created").project("a", "b").by("name").by(__.in("created").count()).order().by(select("b")).select("a"), "[[[a]], []]", null}, + {__.order().by("weight", Order.decr).store("w").by("weight").filter(values("weight").as("cw"). + select("w").by(limit(Scope.local, 1)).as("mw").where("cw", eq("mw"))).project("from", "to", "weight").by(__.outV()).by(__.inV()).by("weight"), + "[[[cw, mw], []]]", null} + }); + } +} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/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 deleted file mode 100644 index 44cc333..0000000 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java +++ /dev/null @@ -1,183 +0,0 @@ -/* - * 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.Order; -import org.apache.tinkerpop.gremlin.process.traversal.P; -import org.apache.tinkerpop.gremlin.process.traversal.Scope; -import org.apache.tinkerpop.gremlin.process.traversal.Step; -import org.apache.tinkerpop.gremlin.process.traversal.Traversal; -import org.apache.tinkerpop.gremlin.process.traversal.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.apache.tinkerpop.gremlin.structure.Graph; -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.List; -import java.util.Set; - -import static org.apache.tinkerpop.gremlin.process.traversal.P.eq; -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.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.limit; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.out; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.select; -import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.values; -import static org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PrunePathStrategy.MAX_BARRIER_SIZE; -import static org.junit.Assert.assertEquals; - -/** - * @author Ted Wilmes (http://twilmes.org) - * @author Marko A. Rodriguez (http://markorodriguez.com) - */ -@RunWith(Parameterized.class) -public class PrunePathStrategyTest { - - private final List<TraversalStrategies> strategies = Arrays.asList( - new DefaultTraversalStrategies().addStrategies(PrunePathStrategy.instance()), - new DefaultTraversalStrategies().addStrategies(PrunePathStrategy.instance(), PathProcessorStrategy.instance()), - new DefaultTraversalStrategies().addStrategies(PrunePathStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance()), - new DefaultTraversalStrategies().addStrategies(PrunePathStrategy.instance(), PathProcessorStrategy.instance(), MatchPredicateStrategy.instance(), RepeatUnrollStrategy.instance()), - TraversalStrategies.GlobalCache.getStrategies(Graph.class)); - - @Parameterized.Parameter(value = 0) - public Traversal.Admin traversal; - - @Parameterized.Parameter(value = 1) - public String labels; - - @Parameterized.Parameter(value = 2) - public Traversal.Admin optimized; - - @Test - public void doTest() { - for (final TraversalStrategies currentStrategies : this.strategies) { - final Traversal.Admin<?, ?> currentTraversal = this.traversal.clone(); - currentTraversal.setStrategies(currentStrategies); - currentTraversal.applyStrategies(); - assertEquals(this.labels, getKeepLabels(currentTraversal).toString()); - if (null != optimized) - assertEquals(currentTraversal, optimized); - } - } - - private List<Object> getKeepLabels(final Traversal.Admin<?, ?> traversal) { - List<Object> keepLabels = new ArrayList<>(); - for (Step step : traversal.getSteps()) { - if (step instanceof PathProcessor) { - final Set<String> keepers = ((PathProcessor) step).getKeepLabels(); - if (keepers != null) - keepLabels.add(keepers); - } - if (step instanceof TraversalParent) { - final TraversalParent parent = (TraversalParent) step; - final List<Traversal.Admin<?, ?>> children = new ArrayList<>(); - children.addAll(parent.getGlobalChildren()); - children.addAll(parent.getLocalChildren()); - for (final Traversal.Admin<?, ?> child : children) { - final 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[][]{ - {out(), "[]", null}, - {__.V().as("a").out().as("b").where(neq("a")).out(), "[[]]", null}, - {__.V().as("a").out().where(out().where(neq("a"))).out(), "[[[]]]", null}, - {__.V().as("a").out().where(neq("a")).out().select("a"), "[[a], []]", null}, - {__.V().as("a").out().as("b").where(neq("a")).out().select("a", "b").out().select("b"), "[[a, b], [b], []]", null}, - {__.V().match(__.as("a").out().as("b")), "[[a, b]]", null}, - {__.V().match(__.as("a").out().as("b")).select("a"), "[[a], []]", null}, - {__.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"), - "[[a, c], [a], []]", null}, - {__.V().as("a").out().select("a").path(), "[]", null}, - {__.V().as("a").out().select("a").subgraph("b"), "[[]]", null}, - {__.V().as("a").out().select("a").subgraph("b").select("a"), "[[a], []]", null}, - {__.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").path(), - "[]", null}, - {__.V().out().as("a").where(neq("a")).out().where(neq("a")).out(), "[[a], []]", null}, - {__.V().out().as("a").where(out().select("a").values("prop").count().is(gte(1))).out().where(neq("a")), "[[[a]], []]", null}, - {__.V().as("a").out().as("b").where(out().select("a", "b", "c").values("prop").count().is(gte(1))).out().where(neq("a")).out().select("b"), - "[[[a, b]], [b], []]", null}, - {__.outE().inV().group().by(__.inE().outV().groupCount().by(__.both().count().is(P.gt(2)))), "[]", null}, - {__.V().as("a").repeat(out().where(neq("a"))).emit().select("a").values("test"), "[[[a]], []]", null}, - // given the way this test harness is structured, I have to manual test for RepeatUnrollStrategy (and it works) TODO: add more test parameters - // {__.V().as("a").repeat(__.out().where(neq("a"))).times(3).select("a").values("test"), Arrays.asList(Collections.singleton("a"), Collections.singleton("a"), Collections.singleton("a"), Collections.emptySet())} - {__.V().as("a").out().as("b").select("a").out().out(), "[[]]", __.V().as("a").out().as("b").select("a").barrier(MAX_BARRIER_SIZE).out().out()}, - {__.V().as("a").out().as("b").select("a").count(), "[[]]", __.V().as("a").out().as("b").select("a").count()}, - {__.V().as("a").out().as("b").select("a").barrier().count(), "[[]]", __.V().as("a").out().as("b").select("a").barrier().count()}, - {__.V().as("a").out().as("b").where(P.gt("a")).out().out(), "[[]]", __.V().as("a").out().as("b").where(P.gt("a")).barrier(MAX_BARRIER_SIZE).out().out()}, - {__.V().as("a").out().as("b").where(P.gt("a")).count(), "[[]]", __.V().as("a").out().as("b").where(P.gt("a")).count()}, - {__.V().as("a").out().as("b").select("a").as("c").where(P.gt("b")).out(), "[[b], []]", __.V().as("a").out().as("b").select("a").as("c").barrier(MAX_BARRIER_SIZE).where(P.gt("b")).barrier(MAX_BARRIER_SIZE).out()}, - {__.V().select("c").map(select("c").map(select("c"))).select("c"), "[[c], [[c], [[c]]], []]", null}, - {__.V().select("c").map(select("c").map(select("c"))).select("b"), "[[b, c], [[b, c], [[b]]], []]", null}, - {__.V().as("a").out().as("b").select("a").select("b").union( - as("c").out().as("d", "e").select("c", "e").out().select("c"), - as("c").out().as("d", "e").select("c", "e").out().select("c")). - out().select("c"), - "[[b, c, e], [c, e], [[c], [c]], [[c], [c]], []]", null}, - {__.V().as("a").out().as("b").select("a").select("b"). - local(as("c").out().as("d", "e").select("c", "e").out().select("c")). - out().select("c"), - "[[b, c, e], [c, e], [[c], [c]], []]", null}, - // TODO: same as above but note how path() makes things react -// {__.V().as("a").out().as("b").select("a").select("b").path().local(as("c").out().as("d", "e").select("c", "e").out().select("c")).out().select("c"), -// "[[[c, e], [c, e]]]", null}, - {__.V().as("a").out().as("b").select("a").select("b").repeat(out().as("c").select("b", "c").out().select("c")).out().select("c").out().select("b"), - "[[b, c], [b, c], [[b, c], [b, c]], [b], []]", null}, - {__.V().as("a").out().as("b").select("a").select("b").repeat(out().as("c").select("b")).out().select("c").out().select("b"), - "[[b, c], [b, c], [[b, c]], [b], []]", null}, - {__.V().as("a").out().as("b").select("a").select("b").repeat(out().as("c").select("b")), - "[[b], [b], [[b]]]", null}, - {__.V().select("a").map(select("c").map(select("b"))).select("c"), - "[[b, c], [[b, c], [[c]]], []]", null}, - {__.V().select("a").map(select("b").repeat(select("c"))).select("a"), - "[[a, b, c], [[a, c], [[a, c]]], []]", null}, - {__.V().select("c").map(select("c").map(select("c"))).select("c"), "[[c], [[c], [[c]]], []]", null}, - {__.V().select("c").map(select("c").map(select("c"))).select("b"), "[[b, c], [[b, c], [[b]]], []]", null}, - {__.V().select("a").map(select("c").map(select("b"))).select("c"), - "[[b, c], [[b, c], [[c]]], []]", null}, - {__.V().select("a").map(select("b").repeat(select("c"))).select("a"), - "[[a, b, c], [[a, c], [[a, c]]], []]", null}, - {__.V().out("created").project("a", "b").by("name").by(__.in("created").count()).order().by(select("b")).select("a"), "[[[a]], []]", null}, - {__.order().by("weight", Order.decr).store("w").by("weight").filter(values("weight").as("cw"). - select("w").by(limit(Scope.local, 1)).as("mw").where("cw", eq("mw"))).project("from", "to", "weight").by(__.outV()).by(__.inV()).by("weight"), - "[[[cw, mw], []]]", null} - }); - } -} http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/groovy/loaders/SugarLoaderTest.groovy ---------------------------------------------------------------------- diff --git a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/groovy/loaders/SugarLoaderTest.groovy b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/groovy/loaders/SugarLoaderTest.groovy index 54471cd..dc973c4 100644 --- a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/groovy/loaders/SugarLoaderTest.groovy +++ b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/groovy/loaders/SugarLoaderTest.groovy @@ -22,13 +22,18 @@ import org.apache.tinkerpop.gremlin.AbstractGremlinTest import org.apache.tinkerpop.gremlin.LoadGraphWith import org.apache.tinkerpop.gremlin.groovy.util.SugarTestHelper import org.apache.tinkerpop.gremlin.process.traversal.Traversal -import org.apache.tinkerpop.gremlin.structure.* +import org.apache.tinkerpop.gremlin.structure.Edge +import org.apache.tinkerpop.gremlin.structure.Graph +import org.apache.tinkerpop.gremlin.structure.Property +import org.apache.tinkerpop.gremlin.structure.Vertex +import org.apache.tinkerpop.gremlin.structure.VertexProperty import org.apache.tinkerpop.gremlin.structure.util.StringFactory -import org.junit.Ignore import org.junit.Test import static org.apache.tinkerpop.gremlin.process.traversal.P.eq -import static org.junit.Assert.* +import static org.junit.Assert.assertEquals +import static org.junit.Assert.assertTrue +import static org.junit.Assert.fail /** * @author Marko A. Rodriguez (http://markorodriguez.com) @@ -91,7 +96,6 @@ class SugarLoaderTest extends AbstractGremlinTest { } } - @Ignore // TODO this is currently set to ignore because the PrunePathStrategy has no insight into the ending map and drops the path information @Test @LoadGraphWith(LoadGraphWith.GraphData.MODERN) public void shouldUseTraverserCategoryCorrectly() { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy ---------------------------------------------------------------------- diff --git a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy index b269dfd..2dd2f03 100644 --- a/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy +++ b/gremlin-groovy-test/src/main/groovy/org/apache/tinkerpop/gremlin/process/traversal/step/map/GroovyMatchTest.groovy @@ -348,5 +348,10 @@ public abstract class GroovyMatchTest { ).select('b', 'c').count(); """) } + + @Override + public Traversal<Vertex, Long> get_g_V_matchXa_knows_count_bX_selectXbX() { + new ScriptTraversal<>(g, "gremlin-groovy", "g.V().match(__.as('a').out('knows').count().as('b')).select('b')") + } } } \ No newline at end of file http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java ---------------------------------------------------------------------- diff --git a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java index 346caa8..2c4789e 100644 --- a/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java +++ b/gremlin-test/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchTest.java @@ -148,6 +148,9 @@ public abstract class MatchTest extends AbstractGremlinProcessTest { public abstract Traversal<Vertex, Long> get_g_V_hasLabelXsongsX_matchXa_name_b__a_performances_cX_selectXb_cX_count(); + // reducing barrier on lazy standard shouldn't yield an empty barrier + public abstract Traversal<Vertex, Long> get_g_V_matchXa_knows_count_bX_selectXbX(); + @Test @LoadGraphWith(MODERN) public void g_V_valueMap_matchXa_selectXnameX_bX() { @@ -521,6 +524,15 @@ public abstract class MatchTest extends AbstractGremlinProcessTest { assertFalse(traversal.hasNext()); } + @Test + @LoadGraphWith(MODERN) + public void g_V_matchXa_knows_count_bX_selectXbX() { + final Traversal<Vertex, Long> traversal = get_g_V_matchXa_knows_count_bX_selectXbX(); + printTraversalForm(traversal); + checkResults(Arrays.asList(0L, 0L, 0L, 0L, 0L, 2L), traversal); + assertFalse(traversal.hasNext()); + } + public static class GreedyMatchTraversals extends Traversals { @Before public void setupTest() { @@ -785,5 +797,10 @@ public abstract class MatchTest extends AbstractGremlinProcessTest { __.as("a").values("performances").as("c") ).select("b", "c").count(); } + + @Override + public Traversal<Vertex, Long> get_g_V_matchXa_knows_count_bX_selectXbX() { + return g.V().match(as("a").out("knows").count().as("b")).select("b"); + } } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/01fd5dc5/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 5bf3c48..7237dfa 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 @@ -26,7 +26,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversal; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.GraphTraversalSource; import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__; -import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PrunePathStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.PathRetractionStrategy; import org.apache.tinkerpop.gremlin.structure.Graph; import org.apache.tinkerpop.gremlin.structure.T; import org.apache.tinkerpop.gremlin.structure.Vertex; @@ -69,8 +69,8 @@ public class TinkerGraphPlayTest { graph.io(GraphMLIo.build()).readGraph("../data/grateful-dead.xml"); //Graph graph = TinkerFactory.createModern(); - GraphTraversalSource g = graph.traversal().withStrategies(PrunePathStrategy.instance()); - GraphTraversalSource h = graph.traversal().withoutStrategies(PrunePathStrategy.class); + GraphTraversalSource g = graph.traversal().withStrategies(PathRetractionStrategy.instance()); + GraphTraversalSource h = graph.traversal().withoutStrategies(PathRetractionStrategy.class); for (final GraphTraversalSource source : Arrays.asList(h, g)) { System.out.println(source.V().match( @@ -309,8 +309,8 @@ public class TinkerGraphPlayTest { Graph graph = TinkerGraph.open(); graph.io(GraphMLIo.build()).readGraph("../data/grateful-dead.xml"); - GraphTraversalSource g = graph.traversal().withComputer(Computer.compute().workers(4)).withStrategies(PrunePathStrategy.instance()); - GraphTraversalSource h = graph.traversal().withComputer(Computer.compute().workers(4)).withoutStrategies(PrunePathStrategy.class); + GraphTraversalSource g = graph.traversal().withComputer(Computer.compute().workers(4)).withStrategies(PathRetractionStrategy.instance()); + GraphTraversalSource h = graph.traversal().withComputer(Computer.compute().workers(4)).withoutStrategies(PathRetractionStrategy.class); for (final GraphTraversalSource source : Arrays.asList(g, h)) { System.out.println(source.V().match(
