tinkerpop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From ok...@apache.org
Subject [1/2] incubator-tinkerpop git commit: 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
Date Wed, 02 Dec 2015 23:13:28 GMT
Repository: incubator-tinkerpop
Updated Branches:
  refs/heads/master 59eaa06e6 -> 6041de663


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/master
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


Mime
View raw message