Repository: tinkerpop Updated Branches: refs/heads/TINKERPOP-1254 a8637a614 -> 2d30be456
Tests passing. Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/2d30be45 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/2d30be45 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/2d30be45 Branch: refs/heads/TINKERPOP-1254 Commit: 2d30be45636813a360bb24bda3cc64f184d4f13d Parents: a8637a6 Author: Ted Wilmes <[email protected]> Authored: Sat Jul 2 20:13:38 2016 -0500 Committer: Ted Wilmes <[email protected]> Committed: Sat Jul 2 20:13:38 2016 -0500 ---------------------------------------------------------------------- .../gremlin/process/traversal/Traverser.java | 2 + .../traversal/dsl/graph/GraphTraversal.java | 5 - .../process/traversal/step/PathProcessor.java | 2 +- .../step/filter/WherePredicateStep.java | 2 +- .../process/traversal/step/map/MatchStep.java | 118 ++++++++++++++++++- .../step/sideEffect/PrunePathStep.java | 55 --------- .../traversal/step/util/ImmutablePath.java | 104 ++++++++++------ .../traversal/step/util/MutablePath.java | 24 ++-- .../optimization/PrunePathStrategy.java | 11 +- .../traverser/B_LP_O_S_SE_SL_Traverser.java | 8 ++ .../traverser/LP_O_OB_P_S_SE_SL_Traverser.java | 5 + .../traverser/util/AbstractTraverser.java | 5 + .../traverser/util/EmptyTraverser.java | 5 + .../gremlin/process/traversal/PathTest.java | 7 +- .../optimization/PrunePathStrategyTest.java | 15 ++- .../structure/TinkerGraphPlayTest.java | 65 ++++++++-- 16 files changed, 302 insertions(+), 131 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/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 c219324..0c37a34 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 @@ -185,6 +185,8 @@ public interface Traverser<T> extends Serializable, Comparable<Traverser<T>>, Cl public void keepLabels(final Set<String> labels); + public void dropLabels(final Set<String> labels); + public void dropPath(); /** http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java index de09332..fa5ab5b 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/dsl/graph/GraphTraversal.java @@ -122,7 +122,6 @@ import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.IdentitySt import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.InjectStep; import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.LambdaSideEffectStep; import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.ProfileSideEffectStep; -import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.PrunePathStep; import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SackValueStep; import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SideEffectCapStep; import org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.StartStep; @@ -1004,10 +1003,6 @@ public interface GraphTraversal<S, E> extends Traversal<S, E> { return this.asAdmin().addStep(new GroupSideEffectStep<>(this.asAdmin(), sideEffectKey)); } -// public default GraphTraversal<S, E> prunePath(final Boolean dropPath, final String... labels) { -// return this.asAdmin().addStep(new PrunePathStep<>(this.asAdmin(), dropPath, labels)); -// } - /** * @deprecated As of release 3.1.0, replaced by {@link #group(String)}. */ http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java index 8905498..11e51cc 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/PathProcessor.java @@ -64,7 +64,7 @@ public interface PathProcessor { static void keepLabels(final Traverser traverser, final Set<String> labels) { if(labels == null || labels.isEmpty()) { - traverser.asAdmin().dropPath(); + //traverser.asAdmin().dropPath(); } else { traverser.asAdmin().keepLabels(labels); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java index f44e417..05ae39d 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WherePredicateStep.java @@ -125,7 +125,7 @@ public final class WherePredicateStep<S> extends FilterStep<S> implements Scopin Set<String> labels = new HashSet<>(); labels.addAll(traverser.getTags()); if(keepLabels != null ) labels.addAll(keepLabels); - if(keepLabels != null) System.out.println(labels); +// if(keepLabels != null) System.out.println(labels); PathProcessor.keepLabels(traverser, labels); return traverser; } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/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 3f02d8d..3c629ce 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 @@ -137,6 +137,8 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } + + public ConnectiveStep.Connective getConnective() { return this.connective; } @@ -320,11 +322,14 @@ 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); + // drop any labels that we can + dropUnnecessaryLabels(traverser, matchTraversal); 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) { final Traverser.Admin split = traverser.split(); + dropUnnecessaryLabels(traverser, matchTraversal); split.getTags().add(matchTraversal.getStartStep().getId()); matchTraversal.addStart(split); } @@ -333,6 +338,22 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } + private void dropUnnecessaryLabels(final Traverser.Admin<Object> traverser, + final Traversal.Admin matchTraversal) { + final List<Traversal.Admin> remainingTraversals = getRemainingTraversals(traverser); + remainingTraversals.add(matchTraversal); + HashSet<String> requiredLabels = new HashSet<>(); + remainingTraversals.stream().forEach(trav -> { + getRequiredLabels(trav, requiredLabels); + }); + requiredLabels.addAll(keepLabels); + requiredLabels.add(matchTraversal.getStartStep().getId()); + System.out.println(requiredLabels); + System.out.println("Before:\t" + traverser.path().labels() + "\t" + traverser.path().objects()); + traverser.keepLabels(requiredLabels); + System.out.println("After:\t" + traverser.path().labels() + "\t" + traverser.path().objects()); + } + @Override protected Iterator<Traverser.Admin<Map<String, E>>> computerAlgorithm() throws NoSuchElementException { while (true) { @@ -355,11 +376,13 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> 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 + dropUnnecessaryLabels(traverser, matchTraversal); return IteratorUtils.of(traverser); } else { // OR final List<Traverser.Admin<Map<String, E>>> traversers = new ArrayList<>(this.matchTraversals.size()); for (final Traversal.Admin<?, ?> matchTraversal : this.matchTraversals) { final Traverser.Admin split = traverser.split(); + //dropUnnecessaryLabels(traverser, matchTraversal); split.getTags().add(matchTraversal.getStartStep().getId()); split.setStepId(matchTraversal.getStartStep().getId()); traversers.add(split); @@ -370,6 +393,57 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } } + private List<Traversal.Admin> getRemainingTraversals(final Traverser.Admin traverser) { + + final Set<String> tags = traverser.getTags(); + final List<Traversal.Admin> remainingTraversals = new ArrayList<>(); + for(final Traversal.Admin matchTraversal : matchTraversals) { + if(!tags.contains(matchTraversal.getStartStep().getId())) { + remainingTraversals.add(matchTraversal); + } else { + // see if we're currently in it + for(Object s : matchTraversal.getSteps()) { + if(((Step)s).getId().equals(traverser.getStepId())) { + remainingTraversals.add(matchTraversal); + break; + } + } +// matchTraversal.getSteps().stream().forEach(step -> { +// +// if(((Step)step).getId().equals(traverser.getStepId())) { +// found = true; +// } +// if(found) { +// remainingTraversals.add(matchTraversal); +// } +// }); + } + } +// System.out.println("Remaining: " + remainingTraversals); + return remainingTraversals; + } + + private void getRequiredLabels(Traversal.Admin trav, Set<String> requiredLabels) { + trav.getSteps().stream().forEach(step -> { +// if(step instanceof Scoping) { +// requiredLabels.addAll(((Scoping) step).getScopeKeys()); +// } + if(step instanceof PathProcessor) { + Set<String> keep = ((PathProcessor) step).getKeepLabels(); + if(keep != null) requiredLabels.addAll(keep); + } else if(step instanceof Scoping) { + Set<String> keep = ((Scoping)step).getScopeKeys(); + if(keep != null) requiredLabels.addAll(keep); + } + if(step instanceof TraversalParent) { + TraversalParent parent = (TraversalParent) step; + List<Traversal.Admin<Object, Object>> children = new ArrayList<>(parent.getGlobalChildren()); + children.addAll(parent.getLocalChildren()); + children.stream().forEach(child -> getRequiredLabels(child, requiredLabels)); + } + }); + } + @Override public int hashCode() { int result = super.hashCode() ^ this.connective.hashCode(); @@ -387,13 +461,29 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> @Override protected Traverser.Admin<Map<String, E>> processNextStart() throws NoSuchElementException { final Traverser.Admin<Map<String, E>> traverser = super.processNextStart(); + // remove labels that we don't need if(keepLabels != null) { // add traverser tags in Set<String> labels = new HashSet<>(); - labels.addAll(traverser.getTags()); - if (keepLabels != null) labels.addAll(keepLabels); - if (keepLabels != null) System.out.println(labels); - PathProcessor.keepLabels(traverser, labels); + // determine which tags to keep vs. drop by looking at which labels still exist in the path + // + +// labels.addAll(getMatchStartLabels()); +// labels.addAll(getMatchEndLabels()); +// if (keepLabels != null) System.out.println(labels); + List<Traversal.Admin> remainingTraversals = getRemainingTraversals(traverser); + if(remainingTraversals.size() == 0) { + System.out.println("none"); + for (Traversal.Admin trav : remainingTraversals) { + getRequiredLabels(trav, labels); + } +// labels.addAll(traverser.getTags()); + if (keepLabels != null) labels.addAll(keepLabels); + System.out.println(labels); + System.out.println(traverser.path().labels()); + PathProcessor.keepLabels(traverser, labels); + System.out.println(traverser.path().labels()); + } } return traverser; } @@ -533,7 +623,16 @@ 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.getTags().contains(traversal.getStartStep().getId()); + final boolean hasExecuted = traverser.getTags().contains(traversal.getStartStep().getId()); + if(hasExecuted) { + String traversalId = traversal.getStartStep().getId(); + List<String> dropMe = new ArrayList(); + // drop labels that matched this step id + dropMe.add(traversalId); + traverser.path().retract(new HashSet(dropMe)); + } + // drop all tags + return hasExecuted; } public static TraversalType getTraversalType(final Traversal.Admin<Object, Object> traversal) { @@ -705,7 +804,14 @@ public final class MatchStep<S, E> extends ComputerAwareStep<S, Map<String, E>> } @Override - public Set<String> getKeepLabels() { return this.keepLabels; } + public Set<String> getKeepLabels() { + // add in start and end labels for this match b/c it's children may need to keep them + HashSet<String> keepThese = new HashSet<>(); + keepThese.addAll(this.keepLabels); + keepThese.addAll(this.getMatchStartLabels()); + keepThese.addAll(this.getMatchEndLabels()); + return keepThese; + } public Set<String> getMatchEndLabels() { return this.matchEndLabels; http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/PrunePathStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/PrunePathStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/PrunePathStep.java deleted file mode 100644 index df519d0..0000000 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/sideEffect/PrunePathStep.java +++ /dev/null @@ -1,55 +0,0 @@ -/* - * Licensed to the Apache Software Foundation (ASF) under one - * or more contributor license agreements. See the NOTICE file - * distributed with this work for additional information - * regarding copyright ownership. The ASF licenses this file - * to you under the Apache License, Version 2.0 (the - * "License"); you may not use this file except in compliance - * with the License. You may obtain a copy of the License at - * - * http://www.apache.org/licenses/LICENSE-2.0 - * - * Unless required by applicable law or agreed to in writing, - * software distributed under the License is distributed on an - * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY - * KIND, either express or implied. See the License for the - * specific language governing permissions and limitations - * under the License. - */ -package org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect; - -import org.apache.tinkerpop.gremlin.process.traversal.Traversal; -import org.apache.tinkerpop.gremlin.process.traversal.Traverser; -import org.apache.tinkerpop.gremlin.structure.util.StringFactory; - -import java.util.Arrays; -import java.util.HashSet; -import java.util.Set; - -/** - * @author Ted Wilmes (http://twilmes.org) - */ -public final class PrunePathStep<S> extends SideEffectStep<S> { - - final Set<String> keepLabels; - final Boolean dropPath; - - public PrunePathStep(final Traversal.Admin traversal, final Boolean dropPath, final String... keepLabels) { - super(traversal); - this.keepLabels = new HashSet<>(Arrays.asList(keepLabels)); - this.dropPath = dropPath; - } - - @Override - protected void sideEffect(Traverser.Admin<S> traverser) { -// final Traverser<S> start = this.starts.next(); - if(this.dropPath) traverser.asAdmin().dropPath(); - else traverser.asAdmin().keepLabels(keepLabels); - } - - @Override - public String toString() { - return StringFactory.stepString(this, this.keepLabels); - } -} - http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java index 4816251..a3cb350 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/ImmutablePath.java @@ -79,6 +79,62 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo return new ImmutablePath(this.previousPath, this.currentObject, temp); } +// @Override + public Path retract3(final Set<String> retractLabels) { + if(retractLabels == null || retractLabels.isEmpty()) { + return this; + } + + List<Set<String>> labelList = this.labels(); + boolean found = false; + for(Set<String> labelSet : labelList) { + if (!Collections.disjoint(labelSet, retractLabels)) { + found = true; + break; + } + } + if(!found) { + return this; + } + return this; + } + + private Path retract(final Set<String> labels, final List<Path> pathTrail) { + Path current = pathTrail.get(0); + if (current instanceof TailPath) { + // return head + return pathTrail.get(pathTrail.size() - 1); + } else { + ImmutablePath immutablePath = (ImmutablePath) current; + if(!Collections.disjoint(labels, immutablePath.currentLabels)) { + // clone all the way back up and replace parents + ImmutablePath parentPath = null; + for(int i = pathTrail.size() - 1; i > 0; i--) { + ImmutablePath clonedPath = cloneImmutablePath((ImmutablePath)pathTrail.get(i)); + if(parentPath != null) { + parentPath.previousPath = clonedPath; + } + parentPath = clonedPath; + pathTrail.set(i, clonedPath); + } + ImmutablePath clonedCurrent = cloneImmutablePath(immutablePath); + clonedCurrent.currentLabels.removeAll(labels); + if(clonedCurrent.currentLabels.isEmpty()) { + if(pathTrail.size() > 1) { + ((ImmutablePath) pathTrail.get(1)).previousPath = clonedCurrent.previousPath; + } else { + pathTrail.remove(0); + } + } + pathTrail.add(clonedCurrent.previousPath); + } else { + pathTrail.add(((ImmutablePath) pathTrail.get(0)).previousPath); + } + retract(labels, pathTrail); + } + return null; + } + @Override public Path retract(final Set<String> labels) { ImmutablePath parent; @@ -103,7 +159,8 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo clone.currentLabels.removeAll(labels); clone.previousPath = TailPath.instance(); if(clone.currentLabels.isEmpty()) { - clone.currentObject = null; + // return the previous tail path because this path segment can be dropped + return clone.previousPath; } return clone; } @@ -119,7 +176,11 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo if(!Collections.disjoint(parent.currentLabels, labels)) { ImmutablePath clonedParent = cloneImmutablePath(parent); clonedParent.currentLabels.removeAll(labels); - parent = clonedParent; + if(clonedParent.currentLabels.isEmpty()) { + parent = (ImmutablePath) parent.previousPath; + } else { + parent = clonedParent; + } } // store the head and return it at the end of this @@ -128,9 +189,7 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo // parents can be a mixture of ImmutablePaths and collapsed // cloned ImmutablePaths that are a result of branching List<Object> parents = new ArrayList<>(); - ImmutablePath previous = null; parents.add(parent); - Set<String> foundLabels = new HashSet<>(); while(true) { @@ -149,6 +208,9 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo // clone child ImmutablePath clone = cloneImmutablePath(child); clone.currentLabels.removeAll(labels); + if(clone.currentLabels.isEmpty()) { + clone.currentObject = null; + } // walk back up and build parent clones or reuse @@ -172,7 +234,11 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo } // if(previous == null) { + if(clone.currentLabels.isEmpty()) { + lastPath.previousPath = clone.previousPath; + } else { lastPath.previousPath = clone; + } // hack! // break; // } @@ -187,35 +253,7 @@ public class ImmutablePath implements Path, ImmutablePathImpl, Serializable, Clo } child = (ImmutablePath)child.previousPath; - -// for(int i = parents.size() - 1; i >= 0; i--) { -// final Object o = parents.get(i); -// if (o instanceof ImmutablePath) { -// ImmutablePath p = (ImmutablePath) o; -// final ImmutablePath clonedP = cloneImmutablePath(p); -// if (previous == null) { -// clonedP.previousPath = clone; -// } else { -// clonedP.previousPath = previous; -// } -// if(first) { -// head = clonedP; -// } -// previous = clonedP; -// } else { -// previous = ((ImmutablePath) o); -// } -// if(first) { -// -// first = false; -// } - } -// parents = new ArrayList<>(); -// parents.add(clone); - - -// parents.add(clone); -// child = (ImmutablePath)child.previousPath; + } } return head; http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java index 1256f2c..26d277e 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/util/MutablePath.java @@ -25,6 +25,7 @@ import java.io.Serializable; import java.util.ArrayList; import java.util.Collections; import java.util.Comparator; +import java.util.HashSet; import java.util.Iterator; import java.util.LinkedHashSet; import java.util.List; @@ -87,14 +88,23 @@ public class MutablePath implements Path, Serializable { } @Override - public Path retract(final Set<String> labels) { + public Path retract(final Set<String> removeLabels) { for (int i = this.labels.size() - 1; i >= 0; i--) { - for (final String label : labels) { - if (this.labels().get(i).contains(label)) { - this.labels.get(i).remove(label); - if (this.labels.get(i).size() == 0) { - for(int x = 0; x < this.objects.size(); x++) this.objects.remove(0); - continue; + for (final String label : removeLabels) { + synchronized (this.labels.get(i)) { + if (this.labels().get(i).contains(label)) { + this.labels.get(i).remove(label); + System.out.println("REMOVED: " + label); + boolean empty = false; + if (this.labels.get(i).size() == 0) { + this.labels.remove(i); + this.objects.remove(i); + empty = true; + } + // label was found, so break out + if(empty) { + break; + } } } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java index a01b51b..6312d4e 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategy.java @@ -103,8 +103,11 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal if(currentStep instanceof Scoping) { Set<String> labels = new HashSet<>(((Scoping) currentStep).getScopeKeys()); if(currentStep instanceof MatchStep) { - labels.addAll(((MatchStep) currentStep).getMatchEndLabels()); - labels.addAll(((MatchStep) currentStep).getMatchStartLabels()); + // if this is the last step, keep everything, else just add founds + if(currentStep.getNextStep() instanceof EmptyStep) { + labels.addAll(((MatchStep) currentStep).getMatchEndLabels()); + labels.addAll(((MatchStep) currentStep).getMatchStartLabels()); + } } for(final String label : labels) { if(foundLabels.contains(label)) { @@ -116,8 +119,8 @@ public final class PrunePathStrategy extends AbstractTraversalStrategy<Traversal } if(currentStep instanceof PathProcessor) { - System.out.println(currentStep); - System.out.println(keepLabels); +// System.out.println(currentStep); +// System.out.println(keepLabels); if(i != traversal.getSteps().size()) { // add in all match labels ((PathProcessor) currentStep).setKeepLabels(new HashSet<>(foundLabels)); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java index d9a1c16..e65a032 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/B_LP_O_S_SE_SL_Traverser.java @@ -101,11 +101,19 @@ public class B_LP_O_S_SE_SL_Traverser<T> extends B_O_S_SE_SL_Traverser<T> { this.path = this.path.retract(retractLabels); } catch (Exception e) { // todo don't retract if it's a head path + e.printStackTrace(); } } } @Override + public void dropLabels(final Set<String> labels) { + if(!labels.isEmpty()) { + this.path = this.path.retract(labels); + } + } + + @Override public void dropPath() { if(path instanceof ImmutablePath) { this.path = ImmutablePath.make(); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java index 1dcce5a..87cfd21 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/LP_O_OB_P_S_SE_SL_Traverser.java @@ -97,6 +97,11 @@ public class LP_O_OB_P_S_SE_SL_Traverser<T> extends O_OB_S_SE_SL_Traverser<T> { } @Override + public void dropLabels(final Set<String> labels) { + this.path = path.retract(new HashSet(labels)); + } + + @Override public void dropPath() { this.path = ImmutablePath.make(); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/AbstractTraverser.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/AbstractTraverser.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/AbstractTraverser.java index 146ba73..f23ac6e 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/AbstractTraverser.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/traverser/util/AbstractTraverser.java @@ -83,6 +83,11 @@ public abstract class AbstractTraverser<T> implements Traverser<T>, Traverser.Ad } @Override + public void dropLabels(final Set<String> labesl) { + + } + + @Override public void dropPath() { } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/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 3e179b5..7c99cb5 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 @@ -55,6 +55,11 @@ public final class EmptyTraverser<T> implements Traverser<T>, Traverser.Admin<T> } @Override + public void dropLabels(final Set<String> labels) { + + } + + @Override public void dropPath() { } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java index ac4f1c9..db60497 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/PathTest.java @@ -42,8 +42,6 @@ public class PathTest { private final static List<Supplier<Path>> PATH_SUPPLIERS = Arrays.asList(MutablePath::make, ImmutablePath::make, DetachedPath::make, ReferencePath::make); -// private final static List<Supplier<Path>> PATH_SUPPLIERS = -// Arrays.asList(ImmutablePath::make); @Test public void shouldHaveStandardSemanticsImplementedCorrectly() { @@ -86,7 +84,10 @@ public class PathTest { path = path.retract(Collections.singleton("a")); assertFalse(path.hasLabel("a")); assertTrue(path.hasLabel("d")); - path.retract(new HashSet<>(Arrays.asList("c", "d"))); + path = path.retract(new HashSet<>(Arrays.asList("c", "d"))); + assertFalse(path.hasLabel("c")); + assertFalse(path.hasLabel("d")); + // todo add object assert to check retract behavior }); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java index a801cfb..e55563d 100644 --- a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java +++ b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/PrunePathStrategyTest.java @@ -28,6 +28,8 @@ import org.junit.runner.RunWith; import org.junit.runners.Parameterized; import java.util.Arrays; +import java.util.List; +import java.util.Set; import java.util.function.Function; import static org.apache.tinkerpop.gremlin.process.traversal.P.neq; @@ -41,10 +43,10 @@ import static org.junit.Assert.assertNull; public class PrunePathStrategyTest { @Parameterized.Parameter(value = 0) - public Traversal original; + public Traversal traversal; @Parameterized.Parameter(value = 1) - public Traversal optimized; + public Set<String> labels; void applyPrunePathStrategy(final Traversal traversal) { final TraversalStrategies strategies = new DefaultTraversalStrategies(); @@ -55,17 +57,18 @@ public class PrunePathStrategyTest { @Test public void doTest() { - applyPrunePathStrategy(original); - assertEquals(optimized, original); - assertNull(((PathProcessor)optimized.asAdmin().getEndStep()).getKeepLabels()); + applyPrunePathStrategy(traversal); + assertEquals(labels, ((PathProcessor)traversal.asAdmin().getEndStep()).getKeepLabels()); } @Parameterized.Parameters(name = "{0}") public static Iterable<Object[]> generateTestParameters() { return Arrays.asList(new Traversal[][]{ + {__.V().as("a").out().as("b").where(neq("a")).out(), } +// {__.V().as("a").select("a"), Arrays.asList(1, 2, 3)} // {__.V().as("a").out().where(neq("a")), __.V().as("a").out().where(neq("a"))}, - {__.V().match(__.as("a").out().as("b"), __.as("b").out().as("c")).select("b"), __.V().match(__.as("a").out().as("b"), __.as("b").out().as("c")).select("b")} +// {__.V().match(__.as("a").out().as("b"), __.as("b").out().as("c")).select("b"), __.V().match(__.as("a").out().as("b"), __.as("b").out().as("c")).select("b")} // {__.V().as("a").out().as("b").out().where((neq("a"))).both().values("name"), __.V().as("a").out().out().where(neq("a")).prunePath(true, "a").both().values("name")}, // {__.V().as("a").out().as("b").select("a", "b"), __.V().as("a").out().as("b").select("a", "b")}, // {__.V().as("a").out().as("b").out().as("c").select("a", "b"), __.V().as("a").out().as("b").out().select("a", "b")}, http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/2d30be45/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java ---------------------------------------------------------------------- diff --git a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java index 60d03b3..c16c2e1 100644 --- a/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java +++ b/tinkergraph-gremlin/src/test/java/org/apache/tinkerpop/gremlin/tinkergraph/structure/TinkerGraphPlayTest.java @@ -18,6 +18,7 @@ */ package org.apache.tinkerpop.gremlin.tinkergraph.structure; +import org.apache.tinkerpop.gremlin.process.computer.Computer; import org.apache.tinkerpop.gremlin.process.computer.bulkloading.BulkLoaderVertexProgram; import org.apache.tinkerpop.gremlin.process.traversal.Operator; import org.apache.tinkerpop.gremlin.process.traversal.Order; @@ -32,6 +33,7 @@ import org.apache.tinkerpop.gremlin.structure.T; import org.apache.tinkerpop.gremlin.structure.Vertex; import org.apache.tinkerpop.gremlin.structure.io.graphml.GraphMLIo; import org.apache.tinkerpop.gremlin.structure.util.GraphFactory; +import org.apache.tinkerpop.gremlin.tinkergraph.process.computer.TinkerGraphComputer; import org.apache.tinkerpop.gremlin.util.TimeUtil; import org.junit.Ignore; import org.junit.Test; @@ -53,6 +55,7 @@ import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.count; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.fold; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.has; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.in; +import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.not; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.or; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.out; import static org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__.outE; @@ -326,8 +329,30 @@ public class TinkerGraphPlayTest { graph = TinkerFactory.createModern(); // graph = TinkerGraph.open(); -// graph.io(GraphMLIo.build()).readGraph("/Users/twilmes/work/repos/incubator-tinkerpop/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/structure/io/graphml/grateful-dead.xml"); - g = graph.traversal();//.withComputer(); + //graph.io(GraphMLIo.build()).readGraph("/Users/twilmes/work/repos/incubator-tinkerpop/gremlin-test/src/main/resources/org/apache/tinkerpop/gremlin/structure/io/graphml/grateful-dead.xml"); + g = graph.traversal().withComputer(Computer.compute(TinkerGraphComputer.class).workers(1)); + +// System.out.println( +// g.V().as("a").out().as("b"). +// match( +// as("a").out().count().as("c"), +// or( +// as("a").out("knows").as("b"), +// as("b").in().count().as("c").and().as("c").is(P.gt(2)) +// ) +// ).select("a").toList()); + + System.out.println(g.V().out().out().match( + as("a").in("created").as("b"), + as("b").in("knows").as("c")).select("c").out("created").values("name").toList()); + + System.out.println(g.V().match( + as("a").out().as("b")). + select("b").by(T.id).toList()); + + // [{a=v[1], b=v[3], c=3}, {a=v[1], b=v[2], c=3}, {a=v[1], b=v[4], c=3}] + // [{a=v[1], b=v[3], c=3}, {a=v[1], b=v[2], c=3}, {a=v[1], b=v[4], c=3}] + // [{a=v[6], b=v[3]}, {a=v[4], b=v[3]}, {a=v[1], b=v[3]}, {a=v[1], b=v[2]}, {a=v[1], b=v[4]}] // a.addEdge("knows", b, "a", 1); @@ -338,7 +363,22 @@ public class TinkerGraphPlayTest { // System.out.println(g.V(a).out("knows").as("a").out("knows").out("knows").toList()); // System.out.println(g.V(a).out().as("a").out().out().select("a", "b").barrier().profile().next()); -// System.out.println(g.V().as("a").match(__.as("a").out().as("b"), __.as("b").out().as("c")).select("a", "b", "c").toList()); +// System.out.println(g.V().as("a").match( +// where("a", neq("b")), +// __.as("a").out().as("b"), +// __.as("b").out().as("c")). +// select("a", "b", "c").by(T.id).toList()); + +// System.out.println(g.V().<Vertex>match( +// as("a").both().as("b"), +// as("b").both().as("c")).dedup("a", "b").toList().size()); + +// System.out.println(g.V(v1Id).out().has(T.id, P.lt(v3Id)).toList()); + +// System.out.println(g.V().out("created") +// .union(as("project").in("created").has("name", "marko").select("project"), +// as("project").in("created").in("knows").has("name", "marko").select("project")). +// groupCount().by("name").toList()); // System.out.println(g.V().match( // as("a").out("knows").as("b"), @@ -346,13 +386,18 @@ public class TinkerGraphPlayTest { // as("b").match( // as("b").out("created").as("d"), // as("d").in("created").as("c")).select("c").as("c")).<Vertex>select("a", "b", "c").toList()); - System.out.println(g.V().match( - as("a").out("knows").as("b"), - as("b").out("created").has("name", "lop"), - as("b").match( - as("b").out("created").as("d"), - as("d").in("created").as("c")).select("c").as("c")).<Vertex>select("a", "b", "c").toList()); -// System.out.println(g.V().aggregate("x").as("a").select("x").unfold().addE("existsWith").to("a").property("time", "now").toList()); +// System.out.println( +// g.V().match( +// as("a").out("knows").as("b"), +// as("b").out("created").has("name", "lop"), +// as("b").match( +// as("b").out("created").as("d"), +// as("d").in("created").as("c")).select("c").as("c")). +// <Vertex>select("a", "b", "c").toList()); +// +// +// +// System.out.println(g.V().aggregate("x").as("a").select("x").unfold().addE("existsWith").to("a").property("time", "now").toList()); // tricky b/c "weight" depends on "e" but since "e" isn't referenced after that select, the object // is dropped
