in gremlin-core/src/main/java/org/apache/tinkerpop/gremlin/process/traversal/strategy/optimization/CountStrategy.java [86:204]
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, hasGtOrLtNegative = 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 = (long) Math.ceil(((Number) value).doubleValue()) + highRangeOffset;
if ((predicate.equals(Compare.gt) || predicate.equals(Compare.gte) || predicate.equals(Compare.lt) || predicate.equals(Compare.lte)) &&
highRangeCandidate < 1) {
hasGtOrLtNegative = true;
}
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)));
}
if (hasGtOrLtNegative) {
// TINKERPOP-2893. Certain combinations of AND and OR will cause this optimization to be incorrect.
// E.g. is(lt(x)) where x < 0, is always false since count() will return at least 0.
// In this case, ANDing a "less than negative" predicate with another predicate should also return false regardless of highRange.
useNotStep = false;
dismissCountIs = false;
}
} 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 (parent instanceof ConnectiveStep) {
// wrap the child of and()/or() in not().
final Step<?, ?> notStep = transformToNotStep(traversal, parent);
TraversalHelper.removeAllSteps(traversal);
traversal.addStep(notStep);
} else if (parent instanceof FilterStep) {
// converts entire where(<x>.count().is(0)) to not(<x>). that's why ConnectiveStep
// is handled differently above.
final Step filterStep = parent.asStep();
final Step<?, ?> notStep = transformToNotStep(traversal, parent);
TraversalHelper.replaceStep(filterStep, notStep, filterStep.getTraversal());
} 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 if (size == 0) {
final Step parentStep = traversal.getParent().asStep();
if (!(parentStep instanceof EmptyStep)) {
final Traversal.Admin parentTraversal = parentStep.getTraversal();
//parentTraversal.removeStep(parentStep); // this leads to IndexOutOfBoundsExceptions
TraversalHelper.replaceStep(parentStep, new IdentityStep<>(parentTraversal), parentTraversal);
}
}
} else {
TraversalHelper.insertBeforeStep(new RangeGlobalStep<>(traversal, 0L, highRange < 0 ? 0 : highRange), curr, traversal);
}
i++;
}
}
prev = curr;
}
}