Early termination with positional predicates

Some related optimisations and thoughts on how to do it: the slow functions in xpath are last(), count(), sum(). I've actually seen someone this week write this code:

foo[count(.//bar) != 0]

When the lazy-evaluation patches land, thats a slow way of saying 'foo[.//bar]' (right now it makes no difference). More generally, we can also spot comparisons with expressions like 'count(//*)' which only need evaluated once. The transformation looks like this (pseudocode):

relev is a function returning a bitmask of CN, CP, CS; bits are set if x depends on context node, position, or size respectively.

(x = y).simplify() ->

if ((relev & (CP|CS|CN)) == 0) {
// assume if relev == 0 then the subexpression was cached
// if the lhs is an expensive function, transform:
if (y ~ count(z)) { simplify to: count-between(z, x, x+2); (extension fn with the obvious definition) } // and so on. provide position-between(), last-between() functions too.
} else if ((relev & (CP|CS|CN)) == 0) {
// use symmetry:
swap_lhs_rhs(); simplify();
} else {
// no simplification possible.
return;
}

relev() can be calculated recursively quite cheaply, just bitwise-or the relev of subexpressions; a simplifying assumption that all predicates require 'CP', you can do a bit better if you also calculate the types of all subexpressions, since boolean predicates don't necessarily need position.

I've implemented the relev() calculations once before, but ripped them out when they didn't make a difference. A way to add this into jaxen is to use a visitor-like technique with the only thing thats globally available to an evaluation - ContextSupport. Typically an operator would need coded as (pseudocode):
Object eval(Context context) {
ContextSupport cs = context.getContextSupport();
Object lhsVal = cs.eval(lhs, context);
Object rhsVal = cs.eval(rhs, context);
// etc... return something like lhsVal == rhsVal, say
}
int relev(ContextSupport cs) { return cs.relev(lhs) | cs.relev(rhs); }
while ContextSupport would contain this:
Object eval(Expr expr, Context context) {
int relev = relev(expr); // fetch cached or computed relev
if (relev == 0) { // fetch cached or computed eval } else { return expr.eval(context); }
}

That would get us the early termination/reduction of predicates optimisations michael mentions. BTW I implemented this cache stuff once already and ripped it out, its described in the OPTMINCONTEXT papers. It hardly got triggered at all by our current tests. But having seen Michaels examples and the one I mentioned at the top, I now see where triggering it would be useful. The savings could be quite large - O(document nodes) becomes O(exprs in the path), roughly speaking, but my previous tests showed a performance hit of 10-20% on the small docs used in our unit tests.

changing component to core (this requires access to the tree, unavailable in saxpath) and marking for 2.0 as its performance

Hasn't JAXEN-31 addressed this?

Not entirely. JAXEN-31 helps if the user avoids using last() (for example) since we don't have to touch all the nodes. My comment above is that this optimisation is one of family of transformations like these:

count < y is equivalent to: for (node in x) { count++; if (!(count < y)) {return false} } return true;

and

count == y is equivalent to: for (node in x) { count++; if (count > y) {return false} } return count == y;

These loops terminate early without hitting every node in x. There's no way for the user to express this intent in xpath, unless we add some extension functions:

count < y is equivalent to: count-between(x, 0, y - 1)
count == y is equivalent to: count-between(x, y, y)

Where count-between(x, ymin, ymax) is defined as:
for (node in x) { count++; if (count > ymax) {return false} } return count >= ymin;

...once we have these, we can get the optimisation by transforming the parse tree to use these functions wherever theres a count() comparison. Even after JAXEN-31 lands, this is still a win.

Re the bug title, 'early termination with positional predicates'... we /may/ have that one covered. There are still some internal uses of size() in jaxen, I'd have to check.