You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@tinkerpop.apache.org by ok...@apache.org on 2016/09/29 19:36:27 UTC
tinkerpop git commit: cleaned up InlineFilterStrategy. Processing
methods for step-types introduced. This is not only cleaner,
but will allow users/providers to turn on/off InlineFiltering for different
step types.
Repository: tinkerpop
Updated Branches:
refs/heads/TINKERPOP-1470 6da9151ef -> c9f8de87c
cleaned up InlineFilterStrategy. Processing methods for step-types introduced. This is not only cleaner, but will allow users/providers to turn on/off InlineFiltering for different step types.
Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/c9f8de87
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/c9f8de87
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/c9f8de87
Branch: refs/heads/TINKERPOP-1470
Commit: c9f8de87c470d2511dc222c2b50125dbfa92447b
Parents: 6da9151
Author: Marko A. Rodriguez <ok...@gmail.com>
Authored: Thu Sep 29 13:36:20 2016 -0600
Committer: Marko A. Rodriguez <ok...@gmail.com>
Committed: Thu Sep 29 13:36:20 2016 -0600
----------------------------------------------------------------------
.../optimization/InlineFilterStrategy.java | 240 ++++++++++---------
1 file changed, 125 insertions(+), 115 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/c9f8de87/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
----------------------------------------------------------------------
diff --git a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
index 0b7a5cc..a3ed9a1 100644
--- a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
+++ b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/InlineFilterStrategy.java
@@ -75,137 +75,147 @@ public final class InlineFilterStrategy extends AbstractTraversalStrategy<Traver
boolean changed = true; // recursively walk child traversals trying to inline them into the current traversal line.
while (changed) {
changed = false;
- // filter(x.y) --> x.y
- for (final TraversalFilterStep<?> step : TraversalHelper.getStepsOfClass(TraversalFilterStep.class, traversal)) {
- final Traversal.Admin<?, ?> childTraversal = step.getLocalChildren().get(0);
- if (TraversalHelper.hasAllStepsOfClass(childTraversal, FilterStep.class) &&
- !TraversalHelper.hasStepOfClass(childTraversal,
- DropStep.class,
- RangeGlobalStep.class,
- DedupGlobalStep.class,
- LambdaHolder.class)) {
+ for (final FilterStep<?> step : TraversalHelper.getStepsOfAssignableClass(FilterStep.class, traversal)) {
+ if (step instanceof TraversalFilterStep && InlineFilterStrategy.processTraversalFilterStep((TraversalFilterStep) step, traversal))
+ // filter(x.y) --> x.y
changed = true;
- TraversalHelper.applySingleLevelStrategies(traversal, childTraversal, InlineFilterStrategy.class);
- final Step<?, ?> finalStep = childTraversal.getEndStep();
- TraversalHelper.insertTraversal((Step) step, childTraversal, traversal);
- TraversalHelper.copyLabels(step, finalStep, false);
- traversal.removeStep(step);
+ else if (step instanceof OrStep && InlineFilterStrategy.processOrStep((OrStep) step, traversal))
+ // or(has(x,y),has(x,z)) --> has(x,y.or(z))
+ changed = true;
+ else if (step instanceof AndStep && InlineFilterStrategy.processAndStep((AndStep) step, traversal))
+ // and(x,y) --> x.y
+ changed = true;
+ }
+ // match(as('a').has(key,value),...) --> as('a').has(key,value).match(...)
+ if (traversal.getParent() instanceof EmptyStep) {
+ for (final MatchStep<?, ?> step : TraversalHelper.getStepsOfClass(MatchStep.class, traversal)) {
+ if (InlineFilterStrategy.processMatchStep(step, traversal))
+ changed = true;
}
}
- // or(has(x,y),has(x,z)) --> has(x,y.or(z))
- for (final OrStep<?> step : TraversalHelper.getStepsOfClass(OrStep.class, traversal)) {
- boolean process = true;
- String key = null;
- P predicate = null;
- final List<String> labels = new ArrayList<>();
- for (final Traversal.Admin<?, ?> childTraversal : step.getLocalChildren()) {
- this.apply(childTraversal); // todo: this may be a bad idea, but I can't seem to find a test case to break it
- for (final Step<?, ?> childStep : childTraversal.getSteps()) {
- if (childStep instanceof HasStep) {
- for (final HasContainer hasContainer : ((HasStep<?>) childStep).getHasContainers()) {
- if (null == key)
- key = hasContainer.getKey();
- else if (!hasContainer.getKey().equals(key)) {
- process = false;
- break;
- }
- predicate = null == predicate ?
- hasContainer.getPredicate() :
- predicate.or(hasContainer.getPredicate());
- }
- labels.addAll(childStep.getLabels());
- } else {
+ }
+ }
+
+ ////////////////////////////
+ ///////////////////////////
+
+ private static final boolean processTraversalFilterStep(final TraversalFilterStep<?> step, final Traversal.Admin<?, ?> traversal) {
+ final Traversal.Admin<?, ?> childTraversal = step.getLocalChildren().get(0);
+ if (TraversalHelper.hasAllStepsOfClass(childTraversal, FilterStep.class) &&
+ !TraversalHelper.hasStepOfClass(childTraversal,
+ DropStep.class,
+ RangeGlobalStep.class,
+ DedupGlobalStep.class,
+ LambdaHolder.class)) {
+ TraversalHelper.applySingleLevelStrategies(traversal, childTraversal, InlineFilterStrategy.class);
+ final Step<?, ?> finalStep = childTraversal.getEndStep();
+ TraversalHelper.insertTraversal((Step) step, childTraversal, traversal);
+ TraversalHelper.copyLabels(step, finalStep, false);
+ traversal.removeStep(step);
+ return true;
+ }
+ return false;
+ }
+
+ private static final boolean processOrStep(final OrStep<?> step, final Traversal.Admin<?, ?> traversal) {
+ boolean process = true;
+ String key = null;
+ P predicate = null;
+ final List<String> labels = new ArrayList<>();
+ for (final Traversal.Admin<?, ?> childTraversal : step.getLocalChildren()) {
+ InlineFilterStrategy.instance().apply(childTraversal); // todo: this may be a bad idea, but I can't seem to find a test case to break it
+ for (final Step<?, ?> childStep : childTraversal.getSteps()) {
+ if (childStep instanceof HasStep) {
+ for (final HasContainer hasContainer : ((HasStep<?>) childStep).getHasContainers()) {
+ if (null == key)
+ key = hasContainer.getKey();
+ else if (!hasContainer.getKey().equals(key)) {
process = false;
break;
}
+ predicate = null == predicate ?
+ hasContainer.getPredicate() :
+ predicate.or(hasContainer.getPredicate());
}
- if (!process)
- break;
- }
- if (process) {
- changed = true;
- final HasStep hasStep = new HasStep<>(traversal, new HasContainer(key, predicate));
- TraversalHelper.replaceStep(step, hasStep, traversal);
- TraversalHelper.copyLabels(step, hasStep, false);
- for (final String label : labels) {
- hasStep.addLabel(label);
- }
+ labels.addAll(childStep.getLabels());
+ } else {
+ process = false;
+ break;
}
}
- // and(x,y) --> x.y
- for (final AndStep<?> step : TraversalHelper.getStepsOfClass(AndStep.class, traversal)) {
- boolean process = true;
- for (final Traversal.Admin<?, ?> childTraversal : step.getLocalChildren()) {
- if (!TraversalHelper.hasAllStepsOfClass(childTraversal, FilterStep.class) ||
- TraversalHelper.hasStepOfClass(childTraversal,
- DropStep.class,
- RangeGlobalStep.class,
- DedupGlobalStep.class,
- LambdaHolder.class)) {
- process = false;
- break;
- }
- }
- if (process) {
- changed = true;
- final List<Traversal.Admin<?, ?>> childTraversals = (List) step.getLocalChildren();
- Step<?, ?> finalStep = null;
- for (int i = childTraversals.size() - 1; i >= 0; i--) {
- final Traversal.Admin<?, ?> childTraversal = childTraversals.get(i);
- TraversalHelper.applySingleLevelStrategies(traversal, childTraversal, InlineFilterStrategy.class);
- if (null == finalStep)
- finalStep = childTraversal.getEndStep();
- TraversalHelper.insertTraversal((Step) step, childTraversals.get(i), traversal);
+ if (!process)
+ break;
+ }
+ if (process) {
+ final HasStep hasStep = new HasStep<>(traversal, new HasContainer(key, predicate));
+ TraversalHelper.replaceStep(step, hasStep, traversal);
+ TraversalHelper.copyLabels(step, hasStep, false);
+ for (final String label : labels) {
+ hasStep.addLabel(label);
+ }
+ return true;
+ }
+ return false;
+ }
- }
- if (null != finalStep) TraversalHelper.copyLabels(step, finalStep, false);
- traversal.removeStep(step);
- }
+ private static final boolean processAndStep(final AndStep<?> step, final Traversal.Admin<?, ?> traversal) {
+ boolean process = true;
+ for (final Traversal.Admin<?, ?> childTraversal : step.getLocalChildren()) {
+ if (!TraversalHelper.hasAllStepsOfClass(childTraversal, FilterStep.class) ||
+ TraversalHelper.hasStepOfClass(childTraversal,
+ DropStep.class,
+ RangeGlobalStep.class,
+ DedupGlobalStep.class,
+ LambdaHolder.class)) {
+ process = false;
+ break;
}
- // match(as('a').has(key,value),...) --> as('a').has(key,value).match(...)
- if (traversal.getParent() instanceof EmptyStep) {
- for (final MatchStep<?, ?> step : TraversalHelper.getStepsOfClass(MatchStep.class, traversal)) {
- final String startLabel = determineStartLabelForHasPullOut(step);
- if (null != startLabel) {
- for (final Traversal.Admin<?, ?> matchTraversal : new ArrayList<>(step.getGlobalChildren())) {
- if (!(step.getPreviousStep() instanceof EmptyStep) &&
- TraversalHelper.hasAllStepsOfClass(matchTraversal,
- HasStep.class,
- MatchStep.MatchStartStep.class,
- MatchStep.MatchEndStep.class) &&
- matchTraversal.getStartStep() instanceof MatchStep.MatchStartStep &&
- startLabel.equals(((MatchStep.MatchStartStep) matchTraversal.getStartStep()).getSelectKey().orElse(null))) {
- changed = true;
- final String endLabel = ((MatchStep.MatchEndStep) matchTraversal.getEndStep()).getMatchKey().orElse(null); // why would this exist? but just in case
- matchTraversal.removeStep(0); // remove MatchStartStep
- matchTraversal.removeStep(matchTraversal.getSteps().size() - 1); // remove MatchEndStep
- TraversalHelper.applySingleLevelStrategies(traversal, matchTraversal, InlineFilterStrategy.class);
- step.removeGlobalChild(matchTraversal);
- step.getPreviousStep().addLabel(startLabel);
- // TODO: matchTraversal.getEndStep().addLabel(startLabel); (perhaps insert an identity so filter rank can push has()-left)
- if (null != endLabel) matchTraversal.getEndStep().addLabel(endLabel);
- TraversalHelper.insertTraversal((Step) step.getPreviousStep(), matchTraversal, traversal);
- }
- }
- if (step.getGlobalChildren().isEmpty())
- traversal.removeStep(step);
- }
- }
+ }
+ if (process) {
+ final List<Traversal.Admin<?, ?>> childTraversals = (List) step.getLocalChildren();
+ Step<?, ?> finalStep = null;
+ for (int i = childTraversals.size() - 1; i >= 0; i--) {
+ final Traversal.Admin<?, ?> childTraversal = childTraversals.get(i);
+ TraversalHelper.applySingleLevelStrategies(traversal, childTraversal, InlineFilterStrategy.class);
+ if (null == finalStep)
+ finalStep = childTraversal.getEndStep();
+ TraversalHelper.insertTraversal((Step) step, childTraversals.get(i), traversal);
+
}
+ if (null != finalStep) TraversalHelper.copyLabels(step, finalStep, false);
+ traversal.removeStep(step);
+ return true;
}
+ return false;
}
- private static final String determineStartLabelForHasPullOut(final MatchStep<?, ?> matchStep) {
- final String startLabel = MatchStep.Helper.computeStartLabel(matchStep.getGlobalChildren());
- Step<?, ?> previousStep = matchStep.getPreviousStep();
- if (previousStep.getLabels().contains(startLabel))
- return startLabel;
- while (!(previousStep instanceof EmptyStep)) {
- if (!previousStep.getLabels().isEmpty())
- return null;
- previousStep = previousStep.getPreviousStep();
+ private static final boolean processMatchStep(final MatchStep<?, ?> step, final Traversal.Admin<?, ?> traversal) {
+ if (step.getPreviousStep() instanceof EmptyStep)
+ return false;
+ boolean changed = false;
+ final String startLabel = MatchStep.Helper.computeStartLabel(step.getGlobalChildren());
+ for (final Traversal.Admin<?, ?> matchTraversal : new ArrayList<>(step.getGlobalChildren())) {
+ if (TraversalHelper.hasAllStepsOfClass(matchTraversal,
+ HasStep.class,
+ MatchStep.MatchStartStep.class,
+ MatchStep.MatchEndStep.class) &&
+ matchTraversal.getStartStep() instanceof MatchStep.MatchStartStep &&
+ startLabel.equals(((MatchStep.MatchStartStep) matchTraversal.getStartStep()).getSelectKey().orElse(null))) {
+ changed = true;
+ final String endLabel = ((MatchStep.MatchEndStep) matchTraversal.getEndStep()).getMatchKey().orElse(null); // why would this exist? but just in case
+ matchTraversal.removeStep(0); // remove MatchStartStep
+ matchTraversal.removeStep(matchTraversal.getSteps().size() - 1); // remove MatchEndStep
+ TraversalHelper.applySingleLevelStrategies(traversal, matchTraversal, InlineFilterStrategy.class);
+ step.removeGlobalChild(matchTraversal);
+ step.getPreviousStep().addLabel(startLabel);
+ // TODO: matchTraversal.getEndStep().addLabel(startLabel); (perhaps insert an identity so filter rank can push has()-left)
+ if (null != endLabel) matchTraversal.getEndStep().addLabel(endLabel);
+ TraversalHelper.insertTraversal((Step) step.getPreviousStep(), matchTraversal, traversal);
+ }
}
- return startLabel;
+ if (step.getGlobalChildren().isEmpty())
+ traversal.removeStep(step);
+ return changed;
}
@Override