You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by sp...@apache.org on 2018/09/18 16:48:27 UTC
[09/50] [abbrv] tinkerpop git commit: Rewrote `ConnectiveStrategy`.
It's a breaking change as it now behaves slightly differently, but now it
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-1913
Commit: e518c9af9a4aca56449af2b743f24d35a8a43b50
Parents: 46ee426
Author: Daniel Kuppitz <da...@hotmail.com>
Authored: Mon Sep 10 11:41:34 2018 -0700
Committer: Daniel Kuppitz <da...@hotmail.com>
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] |