tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From twil...@apache.org
Subject tinkerpop git commit: 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.
Date Sun, 10 Jul 2016 16:12:08 GMT
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 <twilmes@gmail.com>
Authored: Sun Jul 10 11:10:24 2016 -0500
Committer: Ted Wilmes <twilmes@gmail.com>
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());
         }
     }
 


Mime
View raw message