Repository: tinkerpop Updated Branches: refs/heads/TINKERPOP-2029-master [created] 2ce9a6def
Rewrote `ConnectiveStrategy`. It's a breaking change as it now behaves slightly differently, but now it * produces correct AND and OR semantics. * has fewer recursive calls (at most 1). * is faster in its own execution and produces fewer steps in the final traversal which should make the processed traversal faster as well. Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/e518c9af Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/e518c9af Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/e518c9af Branch: refs/heads/TINKERPOP-2029-master Commit: e518c9af9a4aca56449af2b743f24d35a8a43b50 Parents: 46ee426 Author: Daniel Kuppitz <[email protected]> Authored: Mon Sep 10 11:41:34 2018 -0700 Committer: Daniel Kuppitz <[email protected]> Committed: Mon Sep 10 11:41:34 2018 -0700 ---------------------------------------------------------------------- .../strategy/decoration/ConnectiveStrategy.java | 83 ++++++++++++-------- .../decoration/ConnectiveStrategyTest.java | 51 ++++-------- .../optimization/InlineFilterStrategyTest.java | 10 ++- gremlin-test/features/filter/And.feature | 13 ++- 4 files changed, 84 insertions(+), 73 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e518c9af/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/ConnectiveStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/ConnectiveStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/ConnectiveStrategy.java index eb85c7b..3deab6d 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/ConnectiveStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/ConnectiveStrategy.java @@ -34,6 +34,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep; import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy; import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; +import java.util.Collections; +import java.util.List; import java.util.Set; /** @@ -76,42 +78,55 @@ public final class ConnectiveStrategy extends AbstractTraversalStrategy<Traversa private static void processConjunctionMarker(final Class<? extends ConnectiveStep> markerClass, final Traversal.Admin<?, ?> traversal) { - TraversalHelper.getStepsOfClass(markerClass, traversal).stream() - .filter(conjunctionStep -> conjunctionStep.getLocalChildren().isEmpty()) - .findFirst().ifPresent(connectiveStep -> { - - Step<?, ?> currentStep = connectiveStep.getNextStep(); - final Traversal.Admin<?, ?> rightTraversal = __.start().asAdmin(); - if (!connectiveStep.getLabels().isEmpty()) { - final StartStep<?> startStep = new StartStep<>(rightTraversal); - final Set<String> conjunctionLabels = ((Step<?, ?>) connectiveStep).getLabels(); - conjunctionLabels.forEach(startStep::addLabel); - conjunctionLabels.forEach(label -> connectiveStep.removeLabel(label)); - rightTraversal.addStep(startStep); - } - while (legalCurrentStep(currentStep)) { - final Step<?, ?> nextStep = currentStep.getNextStep(); - rightTraversal.addStep(currentStep); - traversal.removeStep(currentStep); - currentStep = nextStep; - } - processConnectiveMarker(rightTraversal); - - currentStep = connectiveStep.getPreviousStep(); - final Traversal.Admin<?, ?> leftTraversal = __.start().asAdmin(); - while (legalCurrentStep(currentStep)) { - final Step<?, ?> previousStep = currentStep.getPreviousStep(); - leftTraversal.addStep(0, currentStep); - traversal.removeStep(currentStep); - currentStep = previousStep; + final List<Step> steps = traversal.getSteps(); + for (int i = 0; i < steps.size(); i++) { + final Step step = steps.get(i); + if (step.getClass().equals(markerClass)) { + final ConnectiveStep<?> currentStep = (ConnectiveStep) step; + if (currentStep.getLocalChildren().isEmpty()) { + Traversal.Admin<?, ?> connectiveTraversal; + currentStep.addLocalChild(connectiveTraversal = __.start().asAdmin()); + for (int j = i - 1; j >= 0; i--, j--) { + final Step previousStep = steps.get(j); + if (legalCurrentStep(previousStep)) { + connectiveTraversal.addStep(0, previousStep); + traversal.removeStep(previousStep); + } else break; + } + i++; + currentStep.addLocalChild(connectiveTraversal = connectiveTraversal(connectiveTraversal, currentStep)); + currentStep.getLabels().forEach(currentStep::removeLabel); + while (i < steps.size()) { + final Step nextStep = steps.get(i); + if (legalCurrentStep(nextStep)) { + if (nextStep.getClass().equals(markerClass) && + ((ConnectiveStep) nextStep).getLocalChildren().isEmpty()) { + final ConnectiveStep<?> nextConnectiveStep = (ConnectiveStep<?>) nextStep; + currentStep.addLocalChild(connectiveTraversal = connectiveTraversal(connectiveTraversal, nextConnectiveStep)); + } else { + connectiveTraversal.addStep(nextStep); + } + traversal.removeStep(nextStep); + } else break; + } + if (currentStep instanceof OrStep) { + currentStep.getLocalChildren().forEach(t -> processConjunctionMarker(AndStep.class, t)); + } + } } - processConnectiveMarker(leftTraversal); + } + } - if (connectiveStep instanceof AndStep) - TraversalHelper.replaceStep((Step) connectiveStep, new AndStep(traversal, leftTraversal, rightTraversal), traversal); - else - TraversalHelper.replaceStep((Step) connectiveStep, new OrStep(traversal, leftTraversal, rightTraversal), traversal); - }); + private static Traversal.Admin<?,?> connectiveTraversal(final Traversal.Admin<?, ?> connectiveTraversal, + final ConnectiveStep connectiveStep) { + final Traversal.Admin<?, ?> traversal = __.start().asAdmin(); + final Set<String> conjunctionLabels = connectiveStep.getLabels(); + if (!conjunctionLabels.isEmpty()) { + final StartStep<?> startStep = new StartStep<>(connectiveTraversal); + conjunctionLabels.forEach(startStep::addLabel); + traversal.addStep(startStep); + } + return traversal; } public static ConnectiveStrategy instance() { http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e518c9af/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/ConnectiveStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/ConnectiveStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/ConnectiveStrategyTest.java index f7a9116..13ccd80 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/ConnectiveStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/decoration/ConnectiveStrategyTest.java @@ -87,43 +87,24 @@ public class ConnectiveStrategyTest { // EXPECT: __.or( __.as("a1").out("a").as("a2"), - __.or( - __.and( - __.as("b1").out("b").as("b2"), - __.as("c1").out("c").as("c2") - ), - __.or( - __.as("d1").out("d").as("d2"), + __.and( + __.as("b1").out("b").as("b2"), + __.as("c1").out("c").as("c2")), + __.as("d1").out("d").as("d2"), + __.and( + __.as("e1").out("e").as("e2"), + __.as("f1").out("f").as("f2"), + __.as("g1").out("g").as("g2")), + __.and( + __.as("h1").out("h").as("h2").or( __.or( + __.as("i1").out("i").as("i2"), __.and( - __.as("e1").out("e").as("e2"), - __.and( - __.as("f1").out("f").as("f2"), - __.as("g1").out("g").as("g2") - ) - ), - __.and( - __.as("h1").out("h").as("h2").or( - __.or( - __.as("i1").out("i").as("i2"), - __.and( - __.as("j1").out("j").as("j2"), - __.as("k1").out("k").as("k2") - ) - ) - ), - __.and( - __.as("l1").out("l").as("l2"), - __.and( - __.as("m1").out("m").as("m2"), - __.as("n1").out("n").as("n2") - ) - ) - ) - ) - ) - ) - ) + __.as("j1").out("j").as("j2"), + __.as("k1").out("k").as("k2")))), + __.as("l1").out("l").as("l2"), + __.as("m1").out("m").as("m2"), + __.as("n1").out("n").as("n2"))) } }); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e518c9af/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategyTest.java index 302a4a5..512f6e5 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategyTest.java @@ -31,6 +31,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.Connec import org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies; import org.apache.tinkerpop.gremlin.process.traversal.util.EmptyTraversal; import org.apache.tinkerpop.gremlin.structure.T; +import org.apache.tinkerpop.gremlin.structure.util.empty.EmptyGraph; import org.junit.Test; import org.junit.runner.RunWith; import org.junit.runners.Parameterized; @@ -41,6 +42,7 @@ import java.util.List; import static org.apache.tinkerpop.gremlin.process.traversal.P.eq; import static org.apache.tinkerpop.gremlin.process.traversal.P.gt; +import static org.apache.tinkerpop.gremlin.process.traversal.P.inside; import static org.apache.tinkerpop.gremlin.process.traversal.P.lt; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.V; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.and; @@ -96,6 +98,7 @@ public class InlineFilterStrategyTest { {filter(has("age", gt(10)).as("b")).as("a"), has("age", gt(10)).as("b", "a"), Collections.emptyList()}, {filter(has("age", gt(10)).as("a")), has("age", gt(10)).as("a"), Collections.emptyList()}, {filter(and(has("age", gt(10)).as("a"), has("name", "marko"))), addHas(__.start(), "age", gt(10), "name", eq("marko")).as("a"), Collections.emptyList()}, + {filter(out("created").and().out("knows").or().in("knows")), filter(or(and(out("created"), out("knows")), __.in("knows"))), Collections.singletonList(ConnectiveStrategy.instance())}, // {or(has("name", "marko"), has("age", 32)), or(has("name", "marko"), has("age", 32)), Collections.emptyList()}, {or(has("name", "marko"), has("name", "bob")), has("name", eq("marko").or(eq("bob"))), Collections.emptyList()}, @@ -110,9 +113,10 @@ public class InlineFilterStrategyTest { {V().has("name", "marko").and().has("name", "marko").and().has("name", "marko"), V().has("name", "marko").has("name", "marko").has("name", "marko"), Collections.emptyList()}, {V().filter(has("name", "marko")).and().filter(has("name", "marko")).and().filter(has("name", "marko")), V().has("name", "marko").has("name", "marko").has("name", "marko"), Collections.emptyList()}, {has("name", "marko").and().has("name", "marko").and().has("name", "marko"), has("name", "marko").has("name", "marko").has("name", "marko"), Collections.singletonList(ConnectiveStrategy.instance())}, - {filter(has("name", "marko")).and().filter(has("name", "marko")).and().filter(has("name", "marko")), has("name", "marko").has("name", "marko").has("name", "marko"), Collections.singletonList(ConnectiveStrategy.instance())}, - {V().has("name", "marko").and().has("name", "marko").and().has("name", "marko"), V().has("name", "marko").has("name", "marko").has("name", "marko"), Collections.singletonList(ConnectiveStrategy.instance())}, - {V().filter(has("name", "marko")).and().filter(has("name", "marko")).and().filter(has("name", "marko")), V().has("name", "marko").has("name", "marko").has("name", "marko"), Collections.singletonList(ConnectiveStrategy.instance())}, + {V().filter(has("name", "marko")).and().filter(has("name", "marko")).and().filter(has("name", "marko")), and(V().has("name", "marko"), has("name", "marko"), has("name", "marko")), Collections.singletonList(ConnectiveStrategy.instance())}, + {V().has("name", "marko").and().has("name", "marko").and().has("name", "marko"), and(V().has("name", "marko"), has("name", "marko"), has("name", "marko")), Collections.singletonList(ConnectiveStrategy.instance())}, + {EmptyGraph.instance().traversal().V().filter(has("name", "marko")).and().filter(has("name", "marko")).and().filter(has("name", "marko")), EmptyGraph.instance().traversal().V().has("name", "marko").has("name", "marko").has("name", "marko"), Collections.singletonList(ConnectiveStrategy.instance())}, + {EmptyGraph.instance().traversal().V().has("name", "marko").and().has("name", "marko").and().has("name", "marko"), EmptyGraph.instance().traversal().V().has("name", "marko").has("name", "marko").has("name", "marko"), Collections.singletonList(ConnectiveStrategy.instance())}, // {and(has("age", gt(10)), filter(has("age", 22))), addHas(__.start(), "age", gt(10), "age", eq(22)), Collections.emptyList()}, {and(has("age", gt(10)).as("a"), filter(has("age", 22).as("b")).as("c")).as("d"), addHas(__.start(), "age", gt(10), "age", eq(22)).as("a", "b", "c", "d"), Collections.emptyList()}, http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/e518c9af/gremlin-test/features/filter/And.feature ---------------------------------------------------------------------- diff --git a/gremlin-test/features/filter/And.feature b/gremlin-test/features/filter/And.feature index 1e8732e..f137841 100644 --- a/gremlin-test/features/filter/And.feature +++ b/gremlin-test/features/filter/And.feature @@ -66,4 +66,15 @@ Feature: Step - and() | v[lop] | | v[josh] | | v[ripple] | - | v[peter] | \ No newline at end of file + | v[peter] | + + Scenario: g_V_hasXname_markoX_and_hasXname_markoX_and_hasXname_markoX + Given the modern graph + And the traversal of + """ + g.V().has("name", "marko").and().has("name", "marko").and().has("name", "marko") + """ + When iterated to list + Then the result should be unordered + | result | + | v[marko] |
