Repository: incubator-tinkerpop
Updated Branches:
refs/heads/TINKERPOP3-1013 [created] e6a1141a0
Added Traverser.getTags(). This gives us more flexbility in how we handle branch-history.
This improves MatchStep, future IntersectStep, future SymmetricDifferenceStep, and will allow
us to do traversal rewriting in MatchStep (TINKERPOP3-736). No more awkward hack of traverser.path().extend(step.getId())...
the stepID is NOT a path label, its a tag.
Project: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/commit/e6a1141a
Tree: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/tree/e6a1141a
Diff: http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/diff/e6a1141a
Branch: refs/heads/TINKERPOP3-1013
Commit: e6a1141a0515f8adc7e51adb2a84495349b06c6a
Parents: fdd853b
Author: Marko A. Rodriguez <okrammarko@gmail.com>
Authored: Tue Dec 1 13:16:26 2015 -0700
Committer: Marko A. Rodriguez <okrammarko@gmail.com>
Committed: Tue Dec 1 13:16:26 2015 -0700
----------------------------------------------------------------------
.../gremlin/process/traversal/Traverser.java | 9 ++++
.../process/traversal/step/map/MatchStep.java | 56 +++++++++++++-------
.../traversal/step/util/ComputerAwareStep.java | 2 +-
.../traversal/traverser/O_Traverser.java | 37 +++++++++++++
.../traverser/util/EmptyTraverser.java | 6 +++
.../traversal/step/map/MatchStepTest.java | 15 ++++--
6 files changed, 99 insertions(+), 26 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/e6a1141a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traverser.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traverser.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traverser.java
index 06925a8..da43fdf 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traverser.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/Traverser.java
@@ -272,5 +272,14 @@ public interface Traverser<T> extends Serializable, Comparable<Traverser<T>>,
Cl
* @return the traversal sideEffects of the traverser
*/
public TraversalSideEffects getSideEffects();
+
+ /**
+ * Get the tags associated with the traverser.
+ * Tags are used to categorize historic behavior of a traverser.
+ * The returned set is mutable.
+ *
+ * @return the set of tags associated with the traverser.
+ */
+ public Set<String> getTags();
}
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/e6a1141a/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 38da656..5452c17 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
@@ -206,7 +206,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
}
public MatchAlgorithm getMatchAlgorithm() {
- if(null == this.matchAlgorithm)
+ if (null == this.matchAlgorithm)
this.initializeMatchAlgorithm(this.traverserStepIdAndLabelsSetByChild ? TraversalEngine.Type.COMPUTER
: TraversalEngine.Type.STANDARD);
return this.matchAlgorithm;
}
@@ -236,23 +236,23 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
private boolean isDuplicate(final Traverser<S> traverser) {
if (null == this.dedups)
return false;
+ final Path path = traverser.path();
for (final String label : this.dedupLabels) {
- if (!traverser.path().hasLabel(label))
+ if (!path.hasLabel(label))
return false;
}
final List<Object> objects = new ArrayList<>(this.dedupLabels.size());
for (final String label : this.dedupLabels) {
- objects.add(traverser.path().get(Pop.last, label));
+ objects.add(path.get(Pop.last, label));
}
return this.dedups.contains(objects);
}
- private boolean hasMatched(final ConnectiveStep.Connective connective, final Traverser<S>
traverser) {
- final Path path = traverser.path();
+ private boolean hasMatched(final ConnectiveStep.Connective connective, final Traverser.Admin<S>
traverser) {
int counter = 0;
boolean matched = false;
for (final Traversal.Admin<Object, Object> matchTraversal : this.matchTraversals)
{
- if (path.hasLabel(matchTraversal.getStartStep().getId())) {
+ if (traverser.getTags().contains(matchTraversal.getStartStep().getId())) {
if (connective == ConnectiveStep.Connective.OR) {
matched = true;
break;
@@ -263,9 +263,10 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
if (!matched)
matched = this.matchTraversals.size() == counter;
if (matched && this.dedupLabels != null) {
+ final Path path = traverser.path();
final List<Object> objects = new ArrayList<>(this.dedupLabels.size());
for (final String label : this.dedupLabels) {
- objects.add(traverser.path().get(Pop.last, label));
+ objects.add(path.get(Pop.last, label));
}
this.dedups.add(objects);
}
@@ -292,6 +293,14 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
this.matchAlgorithm.initialize(traversalEngineType, this.matchTraversals);
}
+ private boolean hasPathLabel(final Path path, final Set<String> labels) {
+ for (final String label : labels) {
+ if (path.hasLabel(label))
+ return true;
+ }
+ return false;
+ }
+
@Override
protected Iterator<Traverser<Map<String, E>>> standardAlgorithm() throws
NoSuchElementException {
while (true) {
@@ -309,10 +318,9 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
}
if (null == traverser) {
traverser = this.starts.next();
- final Path path = traverser.path();
- if (!this.matchStartLabels.stream().filter(path::hasLabel).findAny().isPresent())
+ if (!this.hasPathLabel(traverser.path(), this.matchStartLabels))
traverser.addLabels(Collections.singleton(this.computedStartLabel));
// if the traverser doesn't have a legal start, then provide it the pre-computed one
- traverser.addLabels(Collections.singleton(this.getId())); // so the traverser
never returns to this branch ever again
+ traverser.getTags().add(this.getId()); // so the traverser never returns
to this branch ever again
}
///
if (!this.isDuplicate(traverser)) {
@@ -320,10 +328,14 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
return IteratorUtils.of(traverser.split(this.getBindings(traverser),
this));
if (this.connective == ConnectiveStep.Connective.AND) {
- this.getMatchAlgorithm().apply(traverser).addStart(traverser); // determine
which sub-pattern the traverser should try next
+ final Traversal.Admin<Object, Object> matchTraversal = this.getMatchAlgorithm().apply(traverser);
+ traverser.getTags().add(matchTraversal.getStartStep().getId());
+ matchTraversal.addStart(traverser); // determine which sub-pattern the
traverser should try next
} else { // OR
for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals)
{
- matchTraversal.addStart(traverser.split());
+ final Traverser.Admin split = traverser.split();
+ split.getTags().add(matchTraversal.getStartStep().getId());
+ matchTraversal.addStart(split);
}
}
}
@@ -338,11 +350,9 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
this.initializeMatchAlgorithm(TraversalEngine.Type.COMPUTER);
}
final Traverser.Admin traverser = this.starts.next();
- final Path path = traverser.path();
- if (!this.matchStartLabels.stream().filter(path::hasLabel).findAny().isPresent())
+ if (!this.hasPathLabel(traverser.path(), this.matchStartLabels))
traverser.addLabels(Collections.singleton(this.computedStartLabel)); // if
the traverser doesn't have a legal start, then provide it the pre-computed one
- if (!path.hasLabel(this.getId()))
- traverser.addLabels(Collections.singleton(this.getId())); // so the traverser
never returns to this branch ever again
+ traverser.getTags().add(this.getId()); // so the traverser never returns to this
branch ever again
///
if (!this.isDuplicate(traverser)) {
if (hasMatched(this.connective, traverser)) {
@@ -352,15 +362,17 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
}
if (this.connective == ConnectiveStep.Connective.AND) {
final Traversal.Admin<Object, Object> matchTraversal = this.getMatchAlgorithm().apply(traverser);
// determine which sub-pattern the traverser should try next
+ traverser.getTags().add(matchTraversal.getStartStep().getId());
traverser.setStepId(matchTraversal.getStartStep().getId()); // go down
the traversal match sub-pattern
return IteratorUtils.of(traverser);
} else { // OR
final List<Traverser<Map<String, E>>> traversers =
new ArrayList<>(this.matchTraversals.size());
- this.matchTraversals.forEach(matchTraversal -> {
+ for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals)
{
final Traverser.Admin split = traverser.split();
+ split.getTags().add(matchTraversal.getStartStep().getId());
split.setStepId(matchTraversal.getStartStep().getId());
traversers.add(split);
- });
+ }
return traversers.iterator();
}
}
@@ -503,7 +515,11 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
}
public static boolean hasStartLabels(final Traverser.Admin<Object> traverser,
final Traversal.Admin<Object, Object> traversal) {
- return !Helper.getStartLabels(traversal).stream().filter(label -> !traverser.path().hasLabel(label)).findAny().isPresent();
+ for (final String label : Helper.getStartLabels(traversal)) {
+ if (!traverser.path().hasLabel(label))
+ return false;
+ }
+ return true;
}
public static boolean hasEndLabel(final Traverser.Admin<Object> traverser,
final Traversal.Admin<Object, Object> traversal) {
@@ -512,7 +528,7 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S,
Map<String, E>>
}
public static boolean hasExecutedTraversal(final Traverser.Admin<Object> traverser,
final Traversal.Admin<Object, Object> traversal) {
- return traverser.path().hasLabel(traversal.getStartStep().getId());
+ return traverser.getTags().contains(traversal.getStartStep().getId());
}
public static TraversalType getTraversalType(final Traversal.Admin<Object, Object>
traversal) {
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/e6a1141a/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 2c7ecc5..419205c 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
@@ -77,7 +77,7 @@ public abstract class ComputerAwareStep<S, E> extends AbstractStep<S,
E> impleme
final Traverser.Admin<S> start = this.starts.next();
if (this.traverserStepIdAndLabelsSetByChild) {
start.setStepId(((ComputerAwareStep<?, ?>) this.getTraversal().getParent()).getNextStep().getId());
- start.addLabels(((ComputerAwareStep<?, ?>) this.getTraversal().getParent()).getLabels());
+ start.path().extend(((ComputerAwareStep<?, ?>) this.getTraversal().getParent()).getLabels());
}
return start;
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/e6a1141a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_Traverser.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_Traverser.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_Traverser.java
index 4fc3f5d..44e0f6e 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_Traverser.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/O_Traverser.java
@@ -18,13 +18,20 @@
*/
package org.apache.tinkerpop.gremlin.process.traversal.traverser;
+import org.apache.tinkerpop.gremlin.process.traversal.Step;
+import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.traverser.util.AbstractTraverser;
+import java.util.HashSet;
+import java.util.Set;
+
/**
* @author Marko A. Rodriguez (http://markorodriguez.com)
*/
public class O_Traverser<T> extends AbstractTraverser<T> {
+ protected Set<String> tags = null;
+
protected O_Traverser() {
}
@@ -32,4 +39,34 @@ public class O_Traverser<T> extends AbstractTraverser<T> {
super(t);
}
+
+ public Set<String> getTags() {
+ if (null == this.tags) this.tags = new HashSet<>();
+ return this.tags;
+ }
+
+ @Override
+ public <R> Admin<R> split(final R r, final Step<T, R> step) {
+ final O_Traverser<R> clone = (O_Traverser<R>) super.split(r, step);
+ if (null != this.tags)
+ clone.tags = new HashSet<>(this.tags);
+ return clone;
+ }
+
+ @Override
+ public Admin<T> split() {
+ final O_Traverser<T> clone = (O_Traverser<T>) super.split();
+ if (null != this.tags)
+ clone.tags = new HashSet<>(this.tags);
+ return clone;
+ }
+
+ @Override
+ public void merge(final Traverser.Admin<?> other) {
+ super.merge(other);
+ if (!other.getTags().isEmpty()) {
+ if (this.tags == null) this.tags = new HashSet<>();
+ this.tags.addAll(other.getTags());
+ }
+ }
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/e6a1141a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/EmptyTraverser.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/EmptyTraverser.java
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/EmptyTraverser.java
index a099505..da391f5 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/EmptyTraverser.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/EmptyTraverser.java
@@ -25,6 +25,7 @@ import org.apache.tinkerpop.gremlin.process.traversal.Traverser;
import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyPath;
import org.apache.tinkerpop.gremlin.structure.util.Attachable;
+import java.util.Collections;
import java.util.Set;
import java.util.function.Function;
@@ -144,6 +145,11 @@ public final class EmptyTraverser<T> implements Traverser<T>,
Traverser.Admin<T>
}
@Override
+ public Set<String> getTags() {
+ return Collections.emptySet();
+ }
+
+ @Override
public int hashCode() {
return 380473707;
}
http://git-wip-us.apache.org/repos/asf/incubator-tinkerpop/blob/e6a1141a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java
index 4f7c231..7360e24 100644
--- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java
+++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/MatchStepTest.java
@@ -365,23 +365,28 @@ public class MatchStepTest extends StepTest {
traverser.addLabels(Collections.singleton("a"));
assertEquals(firstPattern, countMatchAlgorithm.apply(traverser));
traverser = traverser.split(1, EmptyStep.instance());
- traverser.addLabels(new HashSet<>(Arrays.asList("b", firstPattern.getStartStep().getId())));
+ traverser.getTags().add(firstPattern.getStartStep().getId());
+ traverser.addLabels(Collections.singleton("b"));
//
assertEquals(secondPattern, countMatchAlgorithm.apply(traverser));
traverser = traverser.split(1, EmptyStep.instance());
- traverser.addLabels(new HashSet<>(Arrays.asList("c", secondPattern.getStartStep().getId())));
+ traverser.getTags().add(secondPattern.getStartStep().getId());
+ traverser.addLabels(Collections.singleton("c"));
//
assertEquals(fifthPattern, countMatchAlgorithm.apply(traverser));
traverser = traverser.split(1, EmptyStep.instance());
- traverser.addLabels(new HashSet<>(Arrays.asList("f", fifthPattern.getStartStep().getId())));
+ traverser.getTags().add(fifthPattern.getStartStep().getId());
+ traverser.addLabels(Collections.singleton("f"));
//
assertEquals(forthPattern, countMatchAlgorithm.apply(traverser));
traverser = traverser.split(1, EmptyStep.instance());
- traverser.addLabels(new HashSet<>(Arrays.asList("e", forthPattern.getStartStep().getId())));
+ traverser.getTags().add(forthPattern.getStartStep().getId());
+ traverser.addLabels(Collections.singleton("e"));
//
assertEquals(thirdPattern, countMatchAlgorithm.apply(traverser));
traverser = traverser.split(1, EmptyStep.instance());
- traverser.addLabels(new HashSet<>(Arrays.asList("d", thirdPattern.getStartStep().getId())));
+ traverser.getTags().add(thirdPattern.getStartStep().getId());
+ traverser.addLabels(Collections.singleton("d"));
}
@Test
|