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/9ef8a9a6 Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/9ef8a9a6 Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/9ef8a9a6 Branch: refs/heads/TINKERPOP-1458 Commit: 9ef8a9a6ce7fded4a98480de792d62ab0e62abab Parents: 8eb0fdd Author: Marko A. Rodriguez <[email protected]> Authored: Thu Sep 29 13:36:20 2016 -0600 Committer: Marko A. Rodriguez <[email protected]> Committed: Mon Oct 3 08:24:17 2016 -0600 ---------------------------------------------------------------------- .../optimization/InlineFilterStrategy.java | 240 ++++++++++--------- 1 file changed, 125 insertions(+), 115 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/9ef8a9a6/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
