Added ScopingStrategy which does a single TraversalHelper.getLabels() call and recurssively tells where() and select() steps the path labels accessed by the Traversal.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/d130cc81 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/d130cc81 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/d130cc81 Branch: refs/heads/TINKERPOP-1642 Commit: d130cc81678d258256a50eb65696c7846e0c02a4 Parents: d3bb05b Author: Marko A. Rodriguez <okramma...@gmail.com> Authored: Fri Mar 3 09:27:58 2017 -0700 Committer: Stephen Mallette <sp...@genoprime.com> Committed: Mon Mar 20 14:08:31 2017 -0400 ---------------------------------------------------------------------- CHANGELOG.asciidoc | 1 + .../process/traversal/TraversalStrategies.java | 2 + .../gremlin/process/traversal/step/Scoping.java | 10 ++++ .../step/filter/WherePredicateStep.java | 11 +++- .../step/filter/WhereTraversalStep.java | 16 ++++-- .../traversal/step/map/SelectOneStep.java | 21 ++++++-- .../process/traversal/step/map/SelectStep.java | 15 ++++-- .../strategy/finalization/ScopingStrategy.java | 57 ++++++++++++++++++++ 8 files changed, 121 insertions(+), 12 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/d130cc81/CHANGELOG.asciidoc ---------------------------------------------------------------------- diff --git a/CHANGELOG.asciidoc b/CHANGELOG.asciidoc index a77991e..86f30f7 100644 --- a/CHANGELOG.asciidoc +++ b/CHANGELOG.asciidoc @@ -34,6 +34,7 @@ TinkerPop 3.2.5 (Release Date: NOT OFFICIALLY RELEASED YET) * Failed scripts will not be recompiled. * Scripts that take over 5 seconds to compile are logged as a warning. * Fixed an `NullPointerException` in `GraphMLReader` that occurred when an `<edge>` didn't have an ID field and the base graph supported ID assignment. +* Added `ScopingStrategy` which will computer and provide all `Scoping` steps with the path labels of the global `Traversal`. * Split `ComputerVerificationStrategy` into two strategies: `ComputerVerificationStrategy` and `ComputerFinalizationStrategy`. * Removed `HasTest.g_V_hasId_compilationEquality` from process test suite as it makes too many assumptions about provider compilation. * Deprecated `CustomizerProvider` infrastructure. http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/d130cc81/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java index 63ae23f..0ddae91 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/TraversalStrategies.java @@ -24,6 +24,7 @@ import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.optimiza import org.apache.tinkerpop.gremlin.process.computer.traversal.strategy.optimization.MessagePassingReductionStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.decoration.ConnectiveStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ProfileStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.finalization.ScopingStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.AdjacentToIncidentStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.FilterRankingStrategy; import org.apache.tinkerpop.gremlin.process.traversal.strategy.optimization.IncidentToAdjacentStrategy; @@ -214,6 +215,7 @@ public interface TraversalStrategies extends Serializable, Cloneable { RangeByIsCountStrategy.instance(), PathRetractionStrategy.instance(), LazyBarrierStrategy.instance(), + ScopingStrategy.instance(), ProfileStrategy.instance(), StandardVerificationStrategy.instance()); GRAPH_CACHE.put(Graph.class, graphStrategies); http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/d130cc81/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/Scoping.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/Scoping.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/Scoping.java index 8c27405..68655e4 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/Scoping.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/Scoping.java @@ -70,4 +70,14 @@ public interface Scoping { } public Set<String> getScopeKeys(); + + /** + * If a Scoping step can do intelligent optimizations by knowing the step labels being accessed globally, then it should implement this label. + * The default implementation does nothing. + * + * @param labels the step labels of the global traversal + */ + public default void setPathLabels(final Set<String> labels) { + + } } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/d130cc81/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 05637f6..b213314 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 @@ -49,6 +49,7 @@ public final class WherePredicateStep<S> extends FilterStep<S> implements Scopin protected String startKey; protected List<String> selectKeys; + private Boolean pathSelectKey = null; protected P<Object> predicate; protected final Set<String> scopeKeys = new HashSet<>(); protected Set<String> keepLabels; @@ -137,14 +138,22 @@ public final class WherePredicateStep<S> extends FilterStep<S> implements Scopin @Override public Set<TraverserRequirement> getRequirements() { - final Set<TraverserRequirement> requirements = + final Set<TraverserRequirement> requirements = null == this.pathSelectKey ? TraversalHelper.getLabels(TraversalHelper.getRootTraversal(this.traversal)).stream().filter(this.scopeKeys::contains).findAny().isPresent() ? TYPICAL_GLOBAL_REQUIREMENTS : + TYPICAL_LOCAL_REQUIREMENTS : + this.pathSelectKey ? + TYPICAL_GLOBAL_REQUIREMENTS : TYPICAL_LOCAL_REQUIREMENTS; return this.getSelfAndChildRequirements(requirements.toArray(new TraverserRequirement[requirements.size()])); } @Override + public void setPathLabels(final Set<String> labels) { + this.pathSelectKey = labels.stream().filter(this.scopeKeys::contains).findAny().isPresent(); + } + + @Override public List<Traversal.Admin<S, ?>> getLocalChildren() { return (List) this.traversalRing.getTraversals(); } http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/d130cc81/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WhereTraversalStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WhereTraversalStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WhereTraversalStep.java index 1dd92e2..c004d30 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WhereTraversalStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/filter/WhereTraversalStep.java @@ -46,6 +46,7 @@ public final class WhereTraversalStep<S> extends FilterStep<S> implements Traver protected Traversal.Admin<?, ?> whereTraversal; protected final Set<String> scopeKeys = new HashSet<>(); + private Boolean pathSelectKey = null; protected Set<String> keepLabels; public WhereTraversalStep(final Traversal.Admin traversal, final Traversal<?, ?> whereTraversal) { @@ -134,9 +135,18 @@ public final class WhereTraversalStep<S> extends FilterStep<S> implements Traver @Override public Set<TraverserRequirement> getRequirements() { - return TraversalHelper.getLabels(TraversalHelper.getRootTraversal(this.getTraversal())).stream().filter(this.scopeKeys::contains).findAny().isPresent() ? - TYPICAL_GLOBAL_REQUIREMENTS : - TYPICAL_LOCAL_REQUIREMENTS; + return null == this.pathSelectKey ? + TraversalHelper.getLabels(TraversalHelper.getRootTraversal(this.getTraversal())).stream().filter(this.scopeKeys::contains).findAny().isPresent() ? + TYPICAL_GLOBAL_REQUIREMENTS : + TYPICAL_LOCAL_REQUIREMENTS : + this.pathSelectKey ? + TYPICAL_GLOBAL_REQUIREMENTS : + TYPICAL_LOCAL_REQUIREMENTS; + } + + @Override + public void setPathLabels(final Set<String> labels) { + this.pathSelectKey = labels.stream().filter(this.scopeKeys::contains).findAny().isPresent(); } @Override http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/d130cc81/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java index a51a8d2..baedbcf 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectOneStep.java @@ -41,6 +41,7 @@ public final class SelectOneStep<S, E> extends MapStep<S, E> implements Traversa private final Pop pop; private final String selectKey; + private Boolean pathSelectKey = null; private Traversal.Admin<S, E> selectTraversal = null; private Set<String> keepLabels; @@ -103,9 +104,17 @@ public final class SelectOneStep<S, E> extends MapStep<S, E> implements Traversa @Override public Set<TraverserRequirement> getRequirements() { - return this.getSelfAndChildRequirements(TraversalHelper.getLabels(TraversalHelper.getRootTraversal(this.traversal)).contains(this.selectKey) ? - TYPICAL_GLOBAL_REQUIREMENTS_ARRAY : - TYPICAL_LOCAL_REQUIREMENTS_ARRAY); + if (null == this.pathSelectKey) + return this.getSelfAndChildRequirements(TraversalHelper.getLabels(TraversalHelper.getRootTraversal(this.traversal)).contains(this.selectKey) ? + TYPICAL_GLOBAL_REQUIREMENTS_ARRAY : + TYPICAL_LOCAL_REQUIREMENTS_ARRAY); + else + return this.getSelfAndChildRequirements(this.pathSelectKey ? TYPICAL_GLOBAL_REQUIREMENTS_ARRAY : TYPICAL_LOCAL_REQUIREMENTS_ARRAY); + } + + @Override + public void setPathLabels(final Set<String> labels) { + this.pathSelectKey = labels.contains(this.selectKey); } @Override @@ -123,12 +132,14 @@ public final class SelectOneStep<S, E> extends MapStep<S, E> implements Traversa } @Override - public Set<String> getKeepLabels() { return this.keepLabels; } + public Set<String> getKeepLabels() { + return this.keepLabels; + } @Override protected Traverser.Admin<E> processNextStart() { final Traverser.Admin<E> traverser = super.processNextStart(); - if(!(this.getTraversal().getParent() instanceof MatchStep)) { + if (!(this.getTraversal().getParent() instanceof MatchStep)) { PathProcessor.processTraverserPathLabels(traverser, this.keepLabels); } return traverser; http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/d130cc81/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java index 77db60f..3a96380 100644 --- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/step/map/SelectStep.java @@ -48,6 +48,7 @@ public final class SelectStep<S, E> extends MapStep<S, Map<String, E>> implement private TraversalRing<Object, E> traversalRing = new TraversalRing<>(); private final Pop pop; private final List<String> selectKeys; + private Boolean pathSelectKey = null; private final Set<String> selectKeysSet; private Set<String> keepLabels; @@ -120,9 +121,17 @@ public final class SelectStep<S, E> extends MapStep<S, Map<String, E>> implement @Override public Set<TraverserRequirement> getRequirements() { - return this.getSelfAndChildRequirements(TraversalHelper.getLabels(TraversalHelper.getRootTraversal(this.traversal)).stream().filter(this.selectKeys::contains).findAny().isPresent() ? - TYPICAL_GLOBAL_REQUIREMENTS_ARRAY : - TYPICAL_LOCAL_REQUIREMENTS_ARRAY); + if (null == this.pathSelectKey) + return this.getSelfAndChildRequirements(TraversalHelper.getLabels(TraversalHelper.getRootTraversal(this.traversal)).stream().filter(this.selectKeys::contains).findAny().isPresent() ? + TYPICAL_GLOBAL_REQUIREMENTS_ARRAY : + TYPICAL_LOCAL_REQUIREMENTS_ARRAY); + else + return this.getSelfAndChildRequirements(this.pathSelectKey ? TYPICAL_GLOBAL_REQUIREMENTS_ARRAY : TYPICAL_LOCAL_REQUIREMENTS_ARRAY); + } + + @Override + public void setPathLabels(final Set<String> labels) { + this.pathSelectKey = labels.stream().filter(this.selectKeysSet::contains).findAny().isPresent(); } @Override http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/d130cc81/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/finalization/ScopingStrategy.java ---------------------------------------------------------------------- diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/finalization/ScopingStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/finalization/ScopingStrategy.java new file mode 100644 index 0000000..ce66da4 --- /dev/null +++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/finalization/ScopingStrategy.java @@ -0,0 +1,57 @@ +/* + * 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.strategy.finalization; + +import org.apache.tinkerpop.gremlin.process.traversal.Traversal; +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.step.Scoping; +import org.apache.tinkerpop.gremlin.process.traversal.step.util.EmptyStep; +import org.apache.tinkerpop.gremlin.process.traversal.strategy.AbstractTraversalStrategy; +import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper; + +import java.util.Set; + +/** + * @author Marko A. Rodriguez (http://markorodriguez.com) + */ +public final class ScopingStrategy extends AbstractTraversalStrategy<TraversalStrategy.FinalizationStrategy> implements TraversalStrategy.FinalizationStrategy { + + private static final ScopingStrategy INSTANCE = new ScopingStrategy(); + + + private ScopingStrategy() { + } + + @Override + public void apply(final Traversal.Admin<?, ?> traversal) { + // only operate on the root traversal and apply global step labels recursively + if (!(traversal.getParent() instanceof EmptyStep)) + return; + + final Set<String> labels = TraversalHelper.getLabels(traversal); + for (final Scoping scoping : TraversalHelper.getStepsOfAssignableClassRecursively(Scoping.class, traversal)) { + scoping.setPathLabels(labels); + } + } + + public static final ScopingStrategy instance() { + return INSTANCE; + } +}