You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by ok...@apache.org on 2015/06/16 16:44:39 UTC
incubator-tinkerpop git commit: XMatchStep now has optimized
XMatchStartStep and XMatchEndStep -- no more SelectOneStep as there is less
logic involved. New methods in MatchAlgorithm for recording data about each
match pattern. Scoping is used as the mea
Repository: incubator-tinkerpop
Updated Branches:
refs/heads/master 801b2dfae -> 26403c15e
XMatchStep now has optimized XMatchStartStep and XMatchEndStep -- no more SelectOneStep as there is less logic involved. New methods in MatchAlgorithm for recording data about each match pattern. Scoping is used as the means for determing required labels for a pattern. lots of local, adhoc testing.
Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/26403c15
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/26403c15
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/26403c15
Branch: refs/heads/master
Commit: 26403c15e6cd8d5f8439f27ddf54f846d6b97101
Parents: 801b2df
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Tue Jun 16 08:44:21 2015 -0600
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Tue Jun 16 08:44:33 2015 -0600
----------------------------------------------------------------------
.../tinkerpop/gremlin/process/traversal/P.java | 2 +-
.../traversal/step/branch/BranchStep.java | 2 +-
.../traversal/step/filter/exp/XMatchStep.java | 159 ++++++++++++++-----
.../traversal/step/util/ComputerAwareStep.java | 11 +-
.../tinkergraph/structure/TinkerGraphTest.java | 31 ++--
5 files changed, 143 insertions(+), 62 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/26403c15/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/P.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/P.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/P.java
index 738752d..4946b5d 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/P.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/P.java
@@ -66,7 +66,7 @@ public class P<V> implements Predicate<V>, Serializable, Cloneable {
@Override
public int hashCode() {
- return this.biPredicate.hashCode() + this.value.hashCode();
+ return this.biPredicate.hashCode() ^ (null == this.value ? "null".hashCode() : this.value.hashCode());
}
@Override
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/26403c15/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/BranchStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/BranchStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/BranchStep.java
index 2f3c7f1..eee95e7 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/BranchStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/branch/BranchStep.java
@@ -52,7 +52,7 @@ public class BranchStep<S, E, M> extends ComputerAwareStep<S, E> implements Trav
this.traversalOptions.get(pickToken).add(traversalOption);
else
this.traversalOptions.put(pickToken, new ArrayList<>(Collections.singletonList(traversalOption)));
- traversalOption.addStep(new EndStep(traversalOption, false));
+ traversalOption.addStep(new EndStep(traversalOption));
this.integrateChild(traversalOption);
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/26403c15/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java
index d3606ef..1180593 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/exp/XMatchStep.java
@@ -31,8 +31,8 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.Scoping;
import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.AndStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.filter.ConjunctionStep;
-import org.apache.tinkerpop.gremlin.process.traversal.step.map.SelectOneStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.StartStep;
+import org.apache.tinkerpop.gremlin.process.traversal.step.util.AbstractStep;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.ComputerAwareStep;
import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.ConjunctionStrategy;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.TraverserRequirement;
@@ -48,7 +48,6 @@ import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.NoSuchElementException;
-import java.util.Optional;
import java.util.Set;
import java.util.function.Function;
import java.util.stream.Collectors;
@@ -65,6 +64,7 @@ public final class XMatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
private boolean first = true;
private Set<String> matchStartLabels = new HashSet<>();
private Set<String> matchEndLabels = new HashSet<>();
+ private Set<String> scopeKeys = null;
private final Conjunction conjunction;
private final String startKey;
private final MatchAlgorithm matchAlgorithm = new CountMatchAlgorithm();
@@ -93,7 +93,7 @@ public final class XMatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
throw new IllegalArgumentException("The start step of a match()-traversal can only have one label: " + startStep);
final String label = startStep.getLabels().iterator().next();
this.matchStartLabels.add(label);
- TraversalHelper.replaceStep(conjunctionTraversal.getStartStep(), new SelectOneStep<>(conjunctionTraversal, Scope.global, Pop.last, label), conjunctionTraversal);
+ TraversalHelper.replaceStep((Step) conjunctionTraversal.getStartStep(), new XMatchStartStep(conjunctionTraversal, label), conjunctionTraversal);
}
// END STEP to XMatchStep
final Step<?, ?> endStep = conjunctionTraversal.getEndStep();
@@ -103,10 +103,7 @@ public final class XMatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
final String label = endStep.getLabels().size() == 0 ? null : endStep.getLabels().iterator().next();
if (null != label) endStep.removeLabel(label);
final Step<?, ?> xMatchEndStep = new XMatchEndStep(conjunctionTraversal, label);
- if (null != label) {
- this.matchEndLabels.add(label);
- xMatchEndStep.addLabel(label);
- }
+ if (null != label) this.matchEndLabels.add(label);
conjunctionTraversal.asAdmin().addStep(xMatchEndStep);
}
}
@@ -132,10 +129,18 @@ public final class XMatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
@Override
public Set<String> getScopeKeys() {
- final HashSet<String> scopedKeys = new HashSet<>();
- scopedKeys.addAll(this.matchStartLabels);
- scopedKeys.addAll(this.matchEndLabels);
- return scopedKeys;
+ if (null == this.scopeKeys) {
+ this.scopeKeys = new HashSet<>();
+ this.conjunctionTraversals.forEach(traversal -> {
+ traversal.getSteps().forEach(step -> {
+ if (step instanceof XMatchStep.XMatchStartStep || step instanceof XMatchStep) {
+ this.scopeKeys.addAll(((Scoping) step).getScopeKeys());
+ }
+ });
+ });
+ this.scopeKeys.removeAll(this.matchEndLabels);
+ }
+ return this.scopeKeys;
}
@Override
@@ -261,6 +266,65 @@ public final class XMatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
//////////////////////////////
+ public class XMatchStartStep extends AbstractStep<Object, Object> implements Scoping {
+
+ private final String selectKey;
+ private Set<String> scopeKeys = null;
+
+ public XMatchStartStep(final Traversal.Admin traversal, final String selectKey) {
+ super(traversal);
+ this.selectKey = selectKey;
+ }
+
+ @Override
+ protected Traverser<Object> processNextStart() throws NoSuchElementException {
+ final Traverser.Admin<Object> traverser = this.starts.next();
+ XMatchStep.this.matchAlgorithm.recordStart(traverser, this.getTraversal());
+ // TODO: sideEffect check?
+ final Traverser.Admin<Object> split = traverser.split(traverser.path().getSingle(Pop.last, this.selectKey), this);
+ split.path().addLabel(XMatchStep.this.getId());
+ return split;
+ }
+
+ @Override
+ public String toString() {
+ return StringFactory.stepString(this, this.selectKey);
+ }
+
+ @Override
+ public int hashCode() {
+ return super.hashCode() ^ this.selectKey.hashCode();
+ }
+
+ @Override
+ public Scope getScope() {
+ return Scope.global;
+ }
+
+ @Override
+ public Scope recommendNextScope() {
+ return Scope.global;
+ }
+
+ @Override
+ public void setScope(final Scope scope) {
+
+ }
+
+ @Override
+ public Set<String> getScopeKeys() {
+ if (null == this.scopeKeys) {
+ this.scopeKeys = new HashSet<>();
+ this.scopeKeys.add(this.selectKey);
+ this.getTraversal().getSteps().forEach(step -> {
+ if (step instanceof Scoping)
+ this.scopeKeys.addAll(((Scoping) step).getScopeKeys());
+ });
+ }
+ return this.scopeKeys;
+ }
+ }
+
public class XMatchEndStep extends EndStep {
private final String matchKey;
@@ -273,26 +337,34 @@ public final class XMatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
@Override
protected Traverser<S> processNextStart() throws NoSuchElementException {
while (true) {
- final Traverser.Admin<S> start = this.starts.next();
+ final Traverser.Admin traverser = this.starts.next();
// no end label
if (null == this.matchKey) {
- if (this.traverserStepIdSetByChild) start.setStepId(XMatchStep.this.getId());
- return start;
- }
- // side-effect check
- final Optional<S> optional = start.getSideEffects().get(this.matchKey);
- if (optional.isPresent() && start.get().equals(optional.get())) {
- if (this.traverserStepIdSetByChild) start.setStepId(XMatchStep.this.getId());
- return start;
+ if (this.traverserStepIdSetByChild) traverser.setStepId(XMatchStep.this.getId());
+ XMatchStep.this.matchAlgorithm.recordEnd(traverser, this.getTraversal());
+ return traverser;
}
+ // TODO: sideEffect check?
// path check
- final Path path = start.path();
- if (!path.hasLabel(this.matchKey) || start.get().equals(path.getSingle(Pop.first, this.matchKey))) {
- if (this.traverserStepIdSetByChild) start.setStepId(XMatchStep.this.getId());
- return start;
+ final Path path = traverser.path();
+ if (!path.hasLabel(this.matchKey) || traverser.get().equals(path.getSingle(Pop.first, this.matchKey))) {
+ if (this.traverserStepIdSetByChild) traverser.setStepId(XMatchStep.this.getId());
+ traverser.path().addLabel(this.matchKey);
+ XMatchStep.this.matchAlgorithm.recordEnd(traverser, this.getTraversal());
+ return traverser;
}
}
}
+
+ @Override
+ public String toString() {
+ return StringFactory.stepString(this, this.matchKey);
+ }
+
+ @Override
+ public int hashCode() {
+ return super.hashCode() ^ (null == this.matchKey ? "null".hashCode() : this.matchKey.hashCode());
+ }
}
@@ -300,31 +372,37 @@ public final class XMatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
public interface MatchAlgorithm extends Function<Traverser.Admin<Object>, Traversal.Admin<Object, Object>> {
- public static String getStartLabel(final Traversal.Admin<Object, Object> traversal) {
+ public static Set<String> getRequiredLabels(final Traversal.Admin<Object, Object> traversal) {
final Step<?, ?> startStep = traversal.getStartStep();
- if (startStep instanceof XMatchStep)
- return ((XMatchStep) startStep).startKey;
- else if (startStep instanceof SelectOneStep)
- return ((SelectOneStep<?,?>) startStep).getScopeKeys().iterator().next();
+ if (startStep instanceof Scoping)
+ return ((Scoping) startStep).getScopeKeys();
else
- throw new IllegalArgumentException("The provided start step must be either an XMatchStep or a SelectOneStep: " + startStep);
+ throw new IllegalArgumentException("The provided start step must be a scoping step: " + startStep);
}
public void initialize(final List<Traversal.Admin<Object, Object>> traversals);
+
+ public default void recordStart(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) {
+
+ }
+
+ public default void recordEnd(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) {
+
+ }
}
public static class GreedyMatchAlgorithm implements MatchAlgorithm {
private List<Traversal.Admin<Object, Object>> traversals;
private List<String> traversalLabels = new ArrayList<>();
- private List<String> startLabels = new ArrayList<>();
+ private List<Set<String>> requiredLabels = new ArrayList<>();
@Override
public void initialize(final List<Traversal.Admin<Object, Object>> traversals) {
this.traversals = traversals;
for (final Traversal.Admin<Object, Object> traversal : this.traversals) {
this.traversalLabels.add(traversal.getStartStep().getId());
- this.startLabels.add(MatchAlgorithm.getStartLabel(traversal));
+ this.requiredLabels.add(MatchAlgorithm.getRequiredLabels(traversal));
}
}
@@ -332,7 +410,7 @@ public final class XMatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
public Traversal.Admin<Object, Object> apply(final Traverser.Admin<Object> traverser) {
final Path path = traverser.path();
for (int i = 0; i < this.traversals.size(); i++) {
- if (path.hasLabel(this.startLabels.get(i)) && !path.hasLabel(this.traversalLabels.get(i))) {
+ if (this.requiredLabels.get(i).stream().filter(path::hasLabel).findAny().isPresent() && !path.hasLabel(this.traversalLabels.get(i))) {
return this.traversals.get(i);
}
}
@@ -345,31 +423,34 @@ public final class XMatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>>
private List<Traversal.Admin<Object, Object>> traversals;
private List<Integer[]> counts = new ArrayList<>();
private List<String> traversalLabels = new ArrayList<>();
- private List<String> startLabels = new ArrayList<>();
+ private List<Set<String>> requiredLabels = new ArrayList<>();
@Override
public void initialize(final List<Traversal.Admin<Object, Object>> traversals) {
this.traversals = traversals;
-
for (int i = 0; i < this.traversals.size(); i++) {
final Traversal.Admin<Object, Object> traversal = this.traversals.get(i);
this.traversalLabels.add(traversal.getStartStep().getId());
- this.startLabels.add(MatchAlgorithm.getStartLabel(traversal));
+ this.requiredLabels.add(MatchAlgorithm.getRequiredLabels(traversal));
this.counts.add(new Integer[]{i, 0});
}
}
@Override
public Traversal.Admin<Object, Object> apply(final Traverser.Admin<Object> traverser) {
- Collections.sort(this.counts, (a, b) -> b[1].compareTo(a[1]));
final Path path = traverser.path();
for (final Integer[] indexCounts : this.counts) {
- if (path.hasLabel(this.startLabels.get(indexCounts[0])) && !path.hasLabel(this.traversalLabels.get(indexCounts[0]))) {
- indexCounts[1]++;
+ if (this.requiredLabels.get(indexCounts[0]).stream().filter(path::hasLabel).findAny().isPresent() && !path.hasLabel(this.traversalLabels.get(indexCounts[0]))) {
return this.traversals.get(indexCounts[0]);
}
}
throw new IllegalArgumentException("The provided match pattern is unsolvable: " + this.traversals);
}
+
+ public void recordEnd(final Traverser.Admin<Object> traverser, final Traversal.Admin<Object, Object> traversal) {
+ final int currentIndex = this.traversals.indexOf(traversal);
+ this.counts.stream().filter(array -> currentIndex == array[0]).findAny().get()[1]++;
+ Collections.sort(this.counts, (a, b) -> a[1].compareTo(b[1]));
+ }
}
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/26403c15/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ComputerAwareStep.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ComputerAwareStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ComputerAwareStep.java
index 0dee51b..4c819f2 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ComputerAwareStep.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ComputerAwareStep.java
@@ -68,22 +68,15 @@ public abstract class ComputerAwareStep<S, E> extends AbstractStep<S, E> impleme
public class EndStep extends AbstractStep<S, S> implements EngineDependent {
- protected final boolean returnHome;
-
- public EndStep(final Traversal.Admin traversal, final boolean returnHome) {
- super(traversal);
- this.returnHome = returnHome;
- }
-
public EndStep(final Traversal.Admin traversal) {
- this(traversal, false);
+ super(traversal);
}
@Override
protected Traverser<S> processNextStart() throws NoSuchElementException {
final Traverser.Admin<S> start = this.starts.next();
if (this.traverserStepIdSetByChild)
- start.setStepId(this.returnHome ? ComputerAwareStep.this.getId() : ComputerAwareStep.this.getNextStep().getId());
+ start.setStepId(ComputerAwareStep.this.getNextStep().getId());
return start;
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/26403c15/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphTest.java
----------------------------------------------------------------------
diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphTest.java
index e6654bd..9883366 100644
--- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphTest.java
+++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphTest.java
@@ -159,7 +159,7 @@ public class TinkerGraphTest {
@Ignore
public void testPlay5() throws Exception {
GraphTraversalSource g = TinkerFactory.createModern().traversal(GraphTraversalSource.standard());
- final Supplier<Traversal<?, ?>> traversal = () -> g.V().xmatch("a",
+ /*final Supplier<Traversal<?, ?>> traversal = () -> g.V().xmatch("a",
as("a").out("created").as("b"),
or(
as("a").out("knows").as("c"),
@@ -167,17 +167,24 @@ public class TinkerGraphTest {
as("a").out("created").has("name", "ripple"),
as("a").out().out()
)
- )).select().by("name");
- /*
- g.V().as("a").xmatch(
- as("a").out("knows").as("b"),
- as("a").out("created").as("c"),
- as("b").out("created").as("c"),
- as("c").in("created").as("d"),
- as("d").where(neq("a")).where(neq("b")),
- as("b").out("created").has("name", "ripple"))
- .select(Pop.head, "a", "b", "c", "d").forEachRemaining(System.out::println);
- */
+ )).select().by("name");*/
+
+ /*final Supplier<Traversal<?, ?>> traversal = () -> g.V().
+ xmatch("a",
+ as("a").local(out("created").count()).as("b"))
+ .select().by("name");*/
+
+ final Supplier<Traversal<?, ?>> traversal = () ->
+ g.V().xmatch("a",
+ as("a").out("created").as("b"),
+ or(
+ as("a").out("knows").has("name","vadas"),
+ as("a").in("knows")
+ ),
+ as("b").in("created").as("c"),
+ as("b").where(in("created").count().is(P.gt(1))),
+ where("a",P.neq("c")))
+ .select().by("name");
System.out.println(traversal.get());
System.out.println(traversal.get().iterate());