Return-Path: X-Original-To: apmail-tinkerpop-commits-archive@minotaur.apache.org Delivered-To: apmail-tinkerpop-commits-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 8490B18DE8 for ; Thu, 3 Dec 2015 16:43:32 +0000 (UTC) Received: (qmail 75795 invoked by uid 500); 3 Dec 2015 16:43:26 -0000 Delivered-To: apmail-tinkerpop-commits-archive@tinkerpop.apache.org Received: (qmail 75754 invoked by uid 500); 3 Dec 2015 16:43:26 -0000 Mailing-List: contact commits-help@tinkerpop.incubator.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@tinkerpop.incubator.apache.org Delivered-To: mailing list commits@tinkerpop.incubator.apache.org Received: (qmail 75744 invoked by uid 99); 3 Dec 2015 16:43:26 -0000 Received: from Unknown (HELO spamd2-us-west.apache.org) (209.188.14.142) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 03 Dec 2015 16:43:26 +0000 Received: from localhost (localhost [127.0.0.1]) by spamd2-us-west.apache.org (ASF Mail Server at spamd2-us-west.apache.org) with ESMTP id 8F1E01A0AD3 for ; Thu, 3 Dec 2015 16:43:25 +0000 (UTC) X-Virus-Scanned: Debian amavisd-new at spamd2-us-west.apache.org X-Spam-Flag: NO X-Spam-Score: 1.246 X-Spam-Level: * X-Spam-Status: No, score=1.246 tagged_above=-999 required=6.31 tests=[KAM_ASCII_DIVIDERS=0.8, KAM_LAZY_DOMAIN_SECURITY=1, RP_MATCHES_RCVD=-0.554] autolearn=disabled Received: from mx1-us-west.apache.org ([10.40.0.8]) by localhost (spamd2-us-west.apache.org [10.40.0.9]) (amavisd-new, port 10024) with ESMTP id fNb3Ofzjsp1a for ; Thu, 3 Dec 2015 16:43:10 +0000 (UTC) Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by mx1-us-west.apache.org (ASF Mail Server at mx1-us-west.apache.org) with SMTP id 4106435C56 for ; Thu, 3 Dec 2015 16:42:58 +0000 (UTC) Received: (qmail 70913 invoked by uid 99); 3 Dec 2015 16:42:57 -0000 Received: from git1-us-west.apache.org (HELO git1-us-west.apache.org) (140.211.11.23) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 03 Dec 2015 16:42:57 +0000 Received: by git1-us-west.apache.org (ASF Mail Server at git1-us-west.apache.org, from userid 33) id DF951E680C; Thu, 3 Dec 2015 16:42:57 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: okram@apache.org To: commits@tinkerpop.incubator.apache.org Date: Thu, 03 Dec 2015 16:43:37 -0000 Message-Id: <92b2d7ab81ef44eba908507cb70fb4ce@git.apache.org> In-Reply-To: <7ddfc1cac2064448b504bfb82908f6f4@git.apache.org> References: <7ddfc1cac2064448b504bfb82908f6f4@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [41/50] 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 i 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-982 Commit: e6a1141a0515f8adc7e51adb2a84495349b06c6a Parents: fdd853b Author: Marko A. Rodriguez Authored: Tue Dec 1 13:16:26 2015 -0700 Committer: Marko A. Rodriguez 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 extends Serializable, Comparable>, 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 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 extends ComputerAwareStep> } 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 extends ComputerAwareStep> private boolean isDuplicate(final Traverser 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 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 traverser) { - final Path path = traverser.path(); + private boolean hasMatched(final ConnectiveStep.Connective connective, final Traverser.Admin traverser) { int counter = 0; boolean matched = false; for (final Traversal.Admin 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 extends ComputerAwareStep> if (!matched) matched = this.matchTraversals.size() == counter; if (matched && this.dedupLabels != null) { + final Path path = traverser.path(); final List 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 extends ComputerAwareStep> this.matchAlgorithm.initialize(traversalEngineType, this.matchTraversals); } + private boolean hasPathLabel(final Path path, final Set labels) { + for (final String label : labels) { + if (path.hasLabel(label)) + return true; + } + return false; + } + @Override protected Iterator>> standardAlgorithm() throws NoSuchElementException { while (true) { @@ -309,10 +318,9 @@ public final class MatchStep extends ComputerAwareStep> } 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 extends ComputerAwareStep> 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 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 extends ComputerAwareStep> 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 extends ComputerAwareStep> } if (this.connective == ConnectiveStep.Connective.AND) { final Traversal.Admin 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>> 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 extends ComputerAwareStep> } public static boolean hasStartLabels(final Traverser.Admin traverser, final Traversal.Admin 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 traverser, final Traversal.Admin traversal) { @@ -512,7 +528,7 @@ public final class MatchStep extends ComputerAwareStep> } public static boolean hasExecutedTraversal(final Traverser.Admin traverser, final Traversal.Admin traversal) { - return traverser.path().hasLabel(traversal.getStartStep().getId()); + return traverser.getTags().contains(traversal.getStartStep().getId()); } public static TraversalType getTraversalType(final Traversal.Admin 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 extends AbstractStep impleme final Traverser.Admin 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 extends AbstractTraverser { + protected Set tags = null; + protected O_Traverser() { } @@ -32,4 +39,34 @@ public class O_Traverser extends AbstractTraverser { super(t); } + + public Set getTags() { + if (null == this.tags) this.tags = new HashSet<>(); + return this.tags; + } + + @Override + public Admin split(final R r, final Step step) { + final O_Traverser clone = (O_Traverser) super.split(r, step); + if (null != this.tags) + clone.tags = new HashSet<>(this.tags); + return clone; + } + + @Override + public Admin split() { + final O_Traverser clone = (O_Traverser) 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 implements Traverser, Traverser.Admin } @Override + public Set 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