Repository: tinkerpop Updated Branches: refs/heads/TINKERPOP-1254 a71ce3278 -> 43c6108dd
Updated ReferencePath to copy labels into a new HashSet before adding them to reference path so that ReferencePaths will not end up sharing label sets. Added a number of new PrunePathStrategy tests. Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/43c6108d Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/43c6108d Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/43c6108d Branch: refs/heads/TINKERPOP-1254 Commit: 43c6108ddfb5d08017ab6e4b3099dd3ad3544186 Parents: a71ce32 Author: Ted Wilmes <[email protected]> Authored: Sun Jul 10 11:10:24 2016 -0500 Committer: Ted Wilmes <[email protected]> Committed: Sun Jul 10 11:10:24 2016 -0500 ---------------------------------------------------------------------- .../process/traversal/step/map/MatchStep.java | 6 +-- .../traversal/step/util/MutablePath.java | 5 --- .../optimization/PrunePathStrategy.java | 11 +++-- .../structure/util/reference/ReferencePath.java | 11 ++--- .../optimization/PrunePathStrategyTest.java | 45 +++++++++----------- .../structure/TinkerGraphPlayTest.java | 20 ++++++--- 6 files changed, 47 insertions(+), 51 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/43c6108d/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 ad5f623..6983bd1 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 @@ -749,11 +749,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> @Override public void setKeepLabels(Set<String> labels) { - if (this.keepLabels != null) { - this.keepLabels.addAll(labels); - } else { - this.keepLabels = new HashSet<>(labels); - } + this.keepLabels = labels; } @Override http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/43c6108d/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 02d95c1..fd86e2d 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 @@ -91,11 +91,6 @@ public class MutablePath implements Path, Serializable { for (int i = this.labels.size() - 1; i >= 0; i--) { for (final String label : removeLabels) { synchronized (this.labels.get(i)) { - if (this.labels.get(i).isEmpty()) { - this.labels.remove(i); - this.objects.remove(i); - continue; - } if (this.labels.get(i).contains(label)) { this.labels.get(i).remove(label); boolean empty = false; http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/43c6108d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java index eb55a5f..efd2949 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java @@ -22,7 +22,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.Step; import org.apache.tinkerpop.gremlin.process.traversal.Traversal; import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.step.PathProcessor; -import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent; import org.apache.tinkerpop.gremlin.process.traversal.step.branch.RepeatStep; import org.apache.tinkerpop.gremlin.process.traversal.step.filter.DedupGlobalStep; import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep; @@ -70,7 +69,7 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal 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 later on + // 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) { @@ -120,6 +119,7 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<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())) { @@ -127,7 +127,7 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal parent = parent.getTraversal().getParent().asStep(); } - // set keep on necessary path processors + // reverse the parent traversal list so that labels are kept from the top down Collections.reverse(parentKeeperPairs); boolean hasRepeat = false; @@ -141,7 +141,8 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal hasRepeat = true; } - // propagate requirements of keepLabels backwards + // 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) { @@ -154,6 +155,7 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal 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); @@ -176,6 +178,7 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal 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) { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/43c6108d/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferencePath.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferencePath.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferencePath.java index 13f4cf2..e70554b 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferencePath.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/structure/util/reference/ReferencePath.java @@ -24,6 +24,7 @@ import org.apache.tinkerpop.gremlin.structure.Element; import org.apache.tinkerpop.gremlin.structure.Property; import org.apache.tinkerpop.gremlin.structure.util.Attachable; +import java.util.HashSet; import java.util.function.Function; /** @@ -43,19 +44,19 @@ public class ReferencePath extends MutablePath implements Attachable<Path> { path.forEach((object, labels) -> { if (object instanceof ReferenceElement || object instanceof ReferenceProperty || object instanceof ReferencePath) { this.objects.add(object); - this.labels.add(labels); + this.labels.add(new HashSet<>(labels)); } else if (object instanceof Element) { this.objects.add(ReferenceFactory.detach((Element) object)); - this.labels.add(labels); + this.labels.add(new HashSet<>(labels)); } else if (object instanceof Property) { this.objects.add(ReferenceFactory.detach((Property) object)); - this.labels.add(labels); + this.labels.add(new HashSet<>(labels)); } else if (object instanceof Path) { this.objects.add(ReferenceFactory.detach((Path) object)); - this.labels.add(labels); + this.labels.add(new HashSet<>(labels)); } else { this.objects.add(object); - this.labels.add(labels); + this.labels.add(new HashSet<>(labels)); } }); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/43c6108d/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java index e3e0315..97c6f50 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java @@ -18,8 +18,9 @@ */ package org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization; -import org.apache.tinkerpop.gremlin.process.computer.GraphComputer; +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; @@ -37,11 +38,14 @@ 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; @@ -109,14 +113,11 @@ public class PrunePathStrategyTest { 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}, - // TODO determine why the dedups keep label array is missing -// {__.V().match( -// as("a").both().as("b"), -// as("b").both().as("c")).dedup("a", "b"), "[[a, b, c], []]", 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"), @@ -124,6 +125,10 @@ public class PrunePathStrategyTest { {__.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"), @@ -138,19 +143,13 @@ public class PrunePathStrategyTest { {__.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()}, - // TODO: why are the global children preserving e? (originally was [[b, c, e], [c, e], [[c, e], [c, e]], [[c, e], [c, e]], []]) {__.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}, - // TODO: why are the global children preserving e? - // TODO: should be [[b, c, e], [c, e], [[c], [c]], [[c], [c]], []] + {__.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}, - // TODO: why is the local child preserving e? (originally was [[b, c, e], [c, e], [[c, e], [c, e]], []]) - // TODO: why is the local child preserving e? - // TODO: should be [[b, c, e], [c, e], [[c], []], []] {__.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"), @@ -158,32 +157,26 @@ public class PrunePathStrategyTest { // 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}, - // TODO: repeat should be treated different cause of recursion (thus, below is good!) {__.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}, - // TODO: repeat should be treated different cause of recursion (thus, below is good!) {__.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}, -// // TODO: repeat should be treated different cause of recursion (thus, below is good!) {__.V().as("a").out().as("b").select("a").select("b").repeat(out().as("c").select("b")), "[[b], [b], [[b]]]", null}, - // TODO: below is broken -- the provided answer is correct. (originally was [[b, c], [[b, c], [[b, c]]], []]) {__.V().select("a").map(select("c").map(select("b"))).select("c"), "[[b, c], [[b, c], [[c]]], []]", null}, - // TODO: below is broken -- the provided answer is correct. (Originally was [[a, b, c], [[a, b, c], [[a, b, c]]], []]) {__.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}, - // TODO: still broken (I changed [[b, c], [[b, c], [[b, c]]], []] to [[b, c], [[b, c], [[b]]], []] but need to make sure that's correct) {__.V().select("c").map(select("c").map(select("c"))).select("b"), "[[b, c], [[b, c], [[b]]], []]", null}, - // TODO: below is broken -- the provided answer is correct. - // {__.V().select("a").map(select("c").map(select("b"))).select("c"), - // "[[b, c], [[b, c], [[b, c]]], []]", null} - // TODO: below is broken -- the provided answer is correct. - // {__.V().select("a").map(select("b").repeat(select("c"))).select("a"), - //"[[a, b, c], [[a, b, c], [[a, b, c]]], []]", null} - // TODO: once we are past the path, we can do selective selecting again - // {__.V().select("a").path().select("b").select("c"), "[[c], []]", 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/43c6108d/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 c28c0b5..e6a6c85 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 @@ -39,6 +39,7 @@ import org.slf4j.Logger; import org.slf4j.LoggerFactory; import java.util.Arrays; +import java.util.Comparator; import java.util.List; import java.util.function.Supplier; @@ -294,6 +295,13 @@ public class TinkerGraphPlayTest { __.as("d").has("name", "George_Harrison"), __.as("e").has("name", "Bob_Marley")).select("a").count().next()); +// System.out.println(g.V().out("created"). +// project("a","b"). +// by("name"). +// by(__.in("created").count()). +// order().by(select("b")). +// select("a").toList()); + // System.out.println(g.V().as("a").out().where(neq("a")).barrier().out().count().profile().next()); // System.out.println(g.V().out().as("a").where(out().select("a").values("prop").count().is(gte(1))).out().where(neq("a")).toList()); // System.out.println(g.V().match( @@ -313,12 +321,12 @@ public class TinkerGraphPlayTest { for (final GraphTraversalSource source : Arrays.asList(g, h)) { System.out.println(source.V().match( - as("a").in("sungBy").as("b"), - as("a").in("sungBy").as("c"), - as("b").out("writtenBy").as("d"), - as("c").out("writtenBy").as("e"), - as("d").has("name", "George_Harrison"), - as("e").has("name", "Bob_Marley")).select("a").count().profile().next()); + __.as("a").in("sungBy").as("b"), + __.as("a").in("sungBy").as("c"), + __.as("b").out("writtenBy").as("d"), + __.as("c").out("writtenBy").as("e"), + __.as("d").has("name", "George_Harrison"), + __.as("e").has("name", "Bob_Marley")).select("a").count().profile().next()); } }
