Merge branch 'TINKERPOP-1742' into TINKERPOP-1742-master

Project: http://git-wip-us.apache.org/repos/asf/tinkerpop/repo
Commit: http://git-wip-us.apache.org/repos/asf/tinkerpop/commit/241f6167
Tree: http://git-wip-us.apache.org/repos/asf/tinkerpop/tree/241f6167
Diff: http://git-wip-us.apache.org/repos/asf/tinkerpop/diff/241f6167

Branch: refs/heads/TINKERPOP-1742-master
Commit: 241f61674947d3596aabbce42758ca5bab095047
Parents: 4e418c1 ba6e8e0
Author: Daniel Kuppitz <daniel_kupp...@hotmail.com>
Authored: Wed Aug 9 11:01:40 2017 -0700
Committer: Daniel Kuppitz <daniel_kupp...@hotmail.com>
Committed: Wed Aug 9 11:01:40 2017 -0700

----------------------------------------------------------------------
 CHANGELOG.asciidoc                                           | 1 +
 .../traversal/strategy/optimization/CountStrategy.java       | 8 +++-----
 .../traversal/strategy/optimization/CountStrategyTest.java   | 4 ++++
 3 files changed, 8 insertions(+), 5 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/241f6167/CHANGELOG.asciidoc
----------------------------------------------------------------------

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/241f6167/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategy.java
----------------------------------------------------------------------
diff --cc 
gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategy.java
index ecddd2c,0000000..a6fa06d
mode 100644,000000..100644
--- 
a/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategy.java
+++ 
b/gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategy.java
@@@ -1,191 -1,0 +1,189 @@@
 +/*
 + * 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.optimization;
 +
 +import org.apache.tinkerpop.gremlin.process.traversal.Compare;
 +import org.apache.tinkerpop.gremlin.process.traversal.Contains;
 +import org.apache.tinkerpop.gremlin.process.traversal.P;
 +import org.apache.tinkerpop.gremlin.process.traversal.Step;
 +import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
 +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategy;
 +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
 +import org.apache.tinkerpop.gremlin.process.traversal.step.TraversalParent;
 +import org.apache.tinkerpop.gremlin.process.traversal.step.branch.RepeatStep;
- import org.apache.tinkerpop.gremlin.process.traversal.step.filter.FilterStep;
- import org.apache.tinkerpop.gremlin.process.traversal.step.filter.IsStep;
- import org.apache.tinkerpop.gremlin.process.traversal.step.filter.NotStep;
- import 
org.apache.tinkerpop.gremlin.process.traversal.step.filter.RangeGlobalStep;
++import org.apache.tinkerpop.gremlin.process.traversal.step.filter.*;
 +import 
org.apache.tinkerpop.gremlin.process.traversal.step.map.CountGlobalStep;
 +import org.apache.tinkerpop.gremlin.process.traversal.step.map.GraphStep;
 +import org.apache.tinkerpop.gremlin.process.traversal.step.map.MatchStep;
 +import 
org.apache.tinkerpop.gremlin.process.traversal.step.sideEffect.SideEffectStep;
 +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.ConnectiveP;
 +import org.apache.tinkerpop.gremlin.process.traversal.util.TraversalHelper;
 +
 +import java.util.Collection;
 +import java.util.Collections;
 +import java.util.EnumSet;
 +import java.util.HashMap;
 +import java.util.Map;
 +import java.util.Objects;
 +import java.util.Set;
 +import java.util.function.BiPredicate;
 +
 +/**
 + * This strategy optimizes any occurrence of {@link CountGlobalStep} followed 
by an {@link IsStep}. The idea is to limit
 + * the number of incoming elements in a way that it's enough for the {@link 
IsStep} to decide whether it evaluates
 + * {@code true} or {@code false}. If the traversal already contains a user 
supplied limit, the strategy won't
 + * modify it.
 + *
 + * @author Daniel Kuppitz (http://gremlin.guru)
 + * @example <pre>
 + * __.outE().count().is(0)      // is replaced by __.not(outE())
 + * __.outE().count().is(lt(3))  // is replaced by 
__.outE().limit(3).count().is(lt(3))
 + * __.outE().count().is(gt(3))  // is replaced by 
__.outE().limit(4).count().is(gt(3))
 + * </pre>
 + */
 +public final class CountStrategy extends 
AbstractTraversalStrategy<TraversalStrategy.OptimizationStrategy> implements 
TraversalStrategy.OptimizationStrategy {
 +
 +    private static final Map<BiPredicate, Long> RANGE_PREDICATES = new 
HashMap<BiPredicate, Long>() {{
 +        put(Contains.within, 1L);
 +        put(Contains.without, 0L);
 +    }};
 +    private static final Set<Compare> INCREASED_OFFSET_SCALAR_PREDICATES =
 +            EnumSet.of(Compare.eq, Compare.neq, Compare.lte, Compare.gt);
 +
 +    private static final CountStrategy INSTANCE = new CountStrategy();
 +
 +    private CountStrategy() {
 +    }
 +
 +    public static CountStrategy instance() {
 +        return INSTANCE;
 +    }
 +
 +    @Override
 +    public void apply(final Traversal.Admin<?, ?> traversal) {
 +        final TraversalParent parent = traversal.getParent();
 +        int size = traversal.getSteps().size();
 +        Step prev = null;
 +        for (int i = 0; i < size; i++) {
 +            final Step curr = traversal.getSteps().get(i);
 +            if (i < size - 1 && doStrategy(curr)) {
 +                final IsStep isStep = (IsStep) traversal.getSteps().get(i + 
1);
 +                final P isStepPredicate = isStep.getPredicate();
 +                Long highRange = null;
 +                boolean useNotStep = false, dismissCountIs = false;
 +                for (P p : isStepPredicate instanceof ConnectiveP ? 
((ConnectiveP<?>) isStepPredicate).getPredicates() : 
Collections.singletonList(isStepPredicate)) {
 +                    final Object value = p.getValue();
 +                    final BiPredicate predicate = p.getBiPredicate();
 +                    if (value instanceof Number) {
 +                        final long highRangeOffset = 
INCREASED_OFFSET_SCALAR_PREDICATES.contains(predicate) ? 1L : 0L;
 +                        final Long highRangeCandidate = ((Number) 
value).longValue() + highRangeOffset;
 +                        final boolean update = highRange == null || 
highRangeCandidate > highRange;
 +                        if (update) {
 +                            if (parent instanceof EmptyStep) {
 +                                useNotStep = false;
 +                            } else {
 +                                if (parent instanceof RepeatStep) {
 +                                    final RepeatStep repeatStep = 
(RepeatStep) parent;
 +                                    dismissCountIs = useNotStep = 
Objects.equals(traversal, repeatStep.getUntilTraversal())
 +                                            || Objects.equals(traversal, 
repeatStep.getEmitTraversal());
 +                                } else {
 +                                    dismissCountIs = useNotStep = parent 
instanceof FilterStep || parent instanceof SideEffectStep;
 +                                }
 +                            }
 +                            highRange = highRangeCandidate;
 +                            useNotStep &= curr.getLabels().isEmpty() && 
isStep.getLabels().isEmpty()
 +                                    && isStep.getNextStep() instanceof 
EmptyStep
 +                                    && ((highRange <= 1L && 
predicate.equals(Compare.lt))
 +                                    || (highRange == 1L && 
(predicate.equals(Compare.eq) || predicate.equals(Compare.lte))));
 +                            dismissCountIs &= curr.getLabels().isEmpty() && 
isStep.getLabels().isEmpty()
 +                                    && isStep.getNextStep() instanceof 
EmptyStep
 +                                    && (highRange == 1L && 
(predicate.equals(Compare.gt) || predicate.equals(Compare.gte)));
 +                        }
 +                    } else {
 +                        final Long highRangeOffset = 
RANGE_PREDICATES.get(predicate);
 +                        if (value instanceof Collection && highRangeOffset != 
null) {
 +                            final Object high = Collections.max((Collection) 
value);
 +                            if (high instanceof Number) {
 +                                final Long highRangeCandidate = ((Number) 
high).longValue() + highRangeOffset;
 +                                final boolean update = highRange == null || 
highRangeCandidate > highRange;
 +                                if (update) highRange = highRangeCandidate;
 +                            }
 +                        }
 +                    }
 +                }
 +                if (highRange != null) {
 +                    if (useNotStep || dismissCountIs) {
 +                        traversal.asAdmin().removeStep(isStep); // IsStep
 +                        traversal.asAdmin().removeStep(curr); // CountStep
 +                        size -= 2;
 +                        if (!dismissCountIs) {
-                             if (traversal.getParent() instanceof FilterStep) {
++                            final TraversalParent p;
++                            if ((p = traversal.getParent()) instanceof 
FilterStep && !(p instanceof ConnectiveStep)) {
 +                                final Step<?, ?> filterStep = parent.asStep();
 +                                final Traversal.Admin parentTraversal = 
filterStep.getTraversal();
 +                                final Step notStep = new 
NotStep<>(parentTraversal,
 +                                        traversal.getSteps().isEmpty() ? 
__.identity() : traversal);
 +                                
filterStep.getLabels().forEach(notStep::addLabel);
 +                                TraversalHelper.replaceStep(filterStep, 
notStep, parentTraversal);
 +                            } else {
 +                                final Traversal.Admin inner;
 +                                if (prev != null) {
 +                                    inner = __.start().asAdmin();
 +                                    for (; ; ) {
 +                                        final Step pp = 
prev.getPreviousStep();
 +                                        inner.addStep(0, prev);
 +                                        if (pp instanceof EmptyStep || pp 
instanceof GraphStep ||
 +                                                !(prev instanceof FilterStep 
|| prev instanceof SideEffectStep)) break;
 +                                        traversal.removeStep(prev);
 +                                        prev = pp;
 +                                        size--;
 +                                    }
 +                                } else {
 +                                    inner = __.identity().asAdmin();
 +                                }
 +                                if (prev != null)
 +                                    TraversalHelper.replaceStep(prev, new 
NotStep<>(traversal, inner), traversal);
 +                                else
 +                                    traversal.asAdmin().addStep(new 
NotStep<>(traversal, inner));
 +                            }
 +                        }
 +                    } else {
 +                        TraversalHelper.insertBeforeStep(new 
RangeGlobalStep<>(traversal, 0L, highRange), curr, traversal);
 +                    }
 +                    i++;
 +                }
 +            }
 +            prev = curr;
 +        }
 +    }
 +
 +    private boolean doStrategy(final Step step) {
 +        if (!(step instanceof CountGlobalStep) ||
 +                !(step.getNextStep() instanceof IsStep) ||
 +                step.getPreviousStep() instanceof RangeGlobalStep) // if a 
RangeStep was provided, assume that the user knows what he's doing
 +            return false;
 +
 +        final Step parent = step.getTraversal().getParent().asStep();
 +        return (parent instanceof FilterStep || parent.getLabels().isEmpty()) 
&& // if the parent is labeled, then the count matters
 +                !(parent.getNextStep() instanceof MatchStep.MatchEndStep && 
// if this is in a pattern match, then don't do it.
 +                        ((MatchStep.MatchEndStep) 
parent.getNextStep()).getMatchKey().isPresent());
 +    }
 +}

http://git-wip-us.apache.org/repos/asf/tinkerpop/blob/241f6167/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java
----------------------------------------------------------------------
diff --cc 
gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java
index 8408c07,0000000..ee4ce38
mode 100644,000000..100644
--- 
a/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java
+++ 
b/gremlin-core/src/test/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategyTest.java
@@@ -1,113 -1,0 +1,117 @@@
 +/*
 + * 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.optimization;
 +
 +import org.apache.tinkerpop.gremlin.process.traversal.Traversal;
 +import org.apache.tinkerpop.gremlin.process.traversal.TraversalStrategies;
 +import org.apache.tinkerpop.gremlin.process.traversal.dsl.graph.__;
 +import 
org.apache.tinkerpop.gremlin.process.traversal.util.DefaultTraversalStrategies;
 +import org.junit.Test;
 +import org.junit.runner.RunWith;
 +import org.junit.runners.Parameterized;
 +
 +import java.util.Arrays;
 +
 +import static org.apache.tinkerpop.gremlin.process.traversal.P.gt;
 +import static org.apache.tinkerpop.gremlin.process.traversal.P.gte;
 +import static org.apache.tinkerpop.gremlin.process.traversal.P.inside;
 +import static org.apache.tinkerpop.gremlin.process.traversal.P.lt;
 +import static org.apache.tinkerpop.gremlin.process.traversal.P.lte;
 +import static org.apache.tinkerpop.gremlin.process.traversal.P.neq;
 +import static org.apache.tinkerpop.gremlin.process.traversal.P.outside;
 +import static org.apache.tinkerpop.gremlin.process.traversal.P.within;
 +import static org.apache.tinkerpop.gremlin.process.traversal.P.without;
 +import static org.junit.Assert.assertEquals;
 +
 +/**
 + * @author Daniel Kuppitz (http://gremlin.guru)
 + * @author Stephen Mallette (http://stephen.genoprime.com)
 + */
 +@RunWith(Parameterized.class)
 +public class CountStrategyTest {
 +
 +    @Parameterized.Parameter(value = 0)
 +    public Traversal original;
 +
 +    @Parameterized.Parameter(value = 1)
 +    public Traversal optimized;
 +
 +    @Parameterized.Parameters(name = "{0}")
 +    public static Iterable<Object[]> generateTestParameters() {
 +
 +        return Arrays.asList(new Traversal[][]{
 +                {__.count().is(0), __.limit(1).count().is(0)},
 +                {__.count().is(1), __.limit(2).count().is(1)},
 +                {__.out().count().is(0), __.out().limit(1).count().is(0)},
 +                {__.outE().count().is(lt(1)), 
__.outE().limit(1).count().is(lt(1))},
 +                {__.both().count().is(lte(0)), 
__.both().limit(1).count().is(lte(0))},
 +                {__.map(__.out().count().is(0)), 
__.map(__.out().limit(1).count().is(0))},
 +                {__.map(__.outE().count().is(lt(1))), 
__.map(__.outE().limit(1).count().is(lt(1)))},
 +                {__.map(__.both().count().is(lte(0))), 
__.map(__.both().limit(1).count().is(lte(0)))},
 +                {__.filter(__.out().count().is(0)), __.not(__.out())},
 +                {__.filter(__.outE().count().is(lt(1))), __.not(__.outE())},
 +                {__.filter(__.both().count().is(lte(0))), __.not(__.both())},
 +                {__.store("x").count().is(0).as("a"), 
__.store("x").limit(1).count().is(0).as("a")},
 +                {__.out().count().as("a").is(0), 
__.out().limit(1).count().as("a").is(0)},
 +                {__.out().count().is(neq(4)), 
__.out().limit(5).count().is(neq(4))},
 +                {__.out().count().is(lte(3)), 
__.out().limit(4).count().is(lte(3))},
 +                {__.out().count().is(lt(3)), 
__.out().limit(3).count().is(lt(3))},
 +                {__.out().count().is(gt(2)), 
__.out().limit(3).count().is(gt(2))},
 +                {__.out().count().is(gte(2)), 
__.out().limit(2).count().is(gte(2))},
 +                {__.out().count().is(inside(2, 4)), 
__.out().limit(4).count().is(inside(2, 4))},
 +                {__.out().count().is(outside(2, 4)), 
__.out().limit(5).count().is(outside(2, 4))},
 +                {__.out().count().is(within(2, 6, 4)), 
__.out().limit(7).count().is(within(2, 6, 4))},
 +                {__.out().count().is(without(2, 6, 4)), 
__.out().limit(6).count().is(without(2, 6, 4))},
 +                {__.map(__.count().is(0)), __.map(__.limit(1).count().is(0))},
 +                {__.flatMap(__.count().is(0)), 
__.flatMap(__.limit(1).count().is(0))},
 +                {__.flatMap(__.count().is(0)).as("a"), 
__.flatMap(__.count().is(0)).as("a")},
 +                {__.filter(__.count().is(0)).as("a"), 
__.not(__.identity()).as("a")},
 +                {__.filter(__.count().is(0)), __.not(__.identity())},
 +                {__.sideEffect(__.count().is(0)), 
__.sideEffect(__.not(__.identity()))},
 +                {__.branch(__.count().is(0)), 
__.branch(__.limit(1).count().is(0))},
 +                {__.count().is(0).store("x"), 
__.limit(1).count().is(0).store("x")},
 +                {__.repeat(__.out()).until(__.outE().count().is(0)), 
__.repeat(__.out()).until(__.not(__.outE()))},
 +                {__.repeat(__.out()).emit(__.outE().count().is(0)), 
__.repeat(__.out()).emit(__.not(__.outE()))},
 +                {__.where(__.outE().hasLabel("created").count().is(0)), 
__.not(__.outE().hasLabel("created"))},
 +                {__.where(__.out().outE().hasLabel("created").count().is(0)), 
__.not(__.out().outE().hasLabel("created"))},
 +                
{__.where(__.out().outE().hasLabel("created").count().is(0).store("x")), 
__.where(__.out().outE().hasLabel("created").limit(1).count().is(0).store("x"))},
 +                {__.filter(__.bothE().count().is(gt(0))), 
__.filter(__.bothE())},
 +                {__.filter(__.bothE().count().is(gte(1))), 
__.filter(__.bothE())},
 +                {__.filter(__.bothE().count().is(gt(1))), 
__.filter(__.bothE().limit(2).count().is(gt(1)))},
 +                {__.filter(__.bothE().count().is(gte(2))), 
__.filter(__.bothE().limit(2).count().is(gte(2)))},
++                {__.and(__.out().count().is(0), __.in().count().is(0)), 
__.and(__.not(__.out()), __.not(__.in()))},
++                {__.and(__.out().count().is(0), __.in().count().is(1)), 
__.and(__.not(__.out()), __.in().limit(2).count().is(1))},
++                {__.and(__.out().count().is(1), __.in().count().is(0)), 
__.and(__.out().limit(2).count().is(1), __.not(__.in()))},
++                {__.or(__.out().count().is(0), __.in().count().is(0)), 
__.or(__.not(__.out()), __.not(__.in()))},
 +        });
 +    }
 +
 +    void applyCountStrategy(final Traversal traversal) {
 +        final TraversalStrategies strategies = new 
DefaultTraversalStrategies();
 +        strategies.addStrategies(CountStrategy.instance());
 +        traversal.asAdmin().setStrategies(strategies);
 +        traversal.asAdmin().applyStrategies();
 +    }
 +
 +    @Test
 +    public void doTest() {
 +        applyCountStrategy(original);
 +        assertEquals(optimized, original);
 +    }
 +}

Reply via email to