[Xpath-ng] FIXPath (XPath NG core) straw man draft posted

[Joe English]

Uche Ogbuji wrote:
> [Joe English]
> > Is that right?   Since "(ancestor::*/*)" is parenthesized,
> > the predicate "[1]" is evaluated "with respect to the child axis",
> > i.e., in document order (see [XPATH] 3.3, first NOTE.)
> > So it should return {a}, not {c}.
>
> Frankly, that section of the XPath spec makes no sense, and has never really
> made any sense.  The statement "The Predicate filters the node-set with
> respect to the child axis" flat out contradicts the note that follows, which
> states that in the most common case, the axis that applies is *not* the child
> axis.

That part of the XPath spec is _very_ badly written.  It took me
days to to figure out what it was trying to say.

The reason it's there is because of 2.2 "Predicates", paragraph 2:
"A predicate filters a node-set with respect to an axis [...]".
But the axis with respect to which the predicate is evaluated
is only used to determine the "proximity position" (2.2
paragraph 1), and the "proximity position" is only used to
determine the "context position".

It's really not the *axis* that matters, but whether it's
a reverse axis or a forward axis.  You could change 3.3 to say
"the descendants-or-self axis", "the following-sibling axis", or
any other forward axis, without changing the meaning one bit.

It would have made more sense to say that "a predicate
filters a node-set with respect to an ordering", and
change 3.3 to read "with respect to document order"
instead of "with respect to the child axis".

Phil Wadler's XPath denotational semantics makes this
more clear.

(BTW, since FIXPath deals with node lists instead of node sets,
you can delete all the noise about "proximity positions"
and "with respect to an axis", and simply define the context
position as the position of the node in the context list.)


> That having been said, if I squint at that section with enough leeway for
> logical inconsistency, it does come out closer to your position than to mine.
>
> Even if that particular example is so resolved, you haven't yet convinced me
> that there are *no* examples where the merge behavior I proposed won't cause
> non-trivial incompatabilities.

Nor was I trying to convince you of that :-)  I was _hoping_
to convince you that this area of the XPath 1.0 semantics
is confusing and counterintuitive enough that non-trivial
incompatibilities are a worthwhile tradeoff for switching
to a simpler approach :-)

> [...]

> > AFAIK, the best algorithm for comparing the relative order of
> > two nodes requires you to walk up and across the tree.  Unless
> > someone has come up with an efficient way to keep cached ordering
> > information up-to-date when modifying the document, that is --
> > I'm not aware of any such algorithm.
>
> This can be done with a relatively simple algorithm that keeps gaps in the
> document order indices for each node, filling these in as needed, and then
> triggering a recomputation up the tree (a re-balancing) when needed.  There
> are *many* approaches to this algorithm, and a variant of it is what we're
> using in development branches of 4Suite.
>
> This is relatively efficient, adding a tiny bit of overhead to all mutation,
> and the occasional larger bit of overhead to some operations. [...]

I'll have to take a look at that to see how you do it.
In all the caching schemes I've been able to come up with,
the "occasional larger bit of overhead" has been very
expensive, and only worthwhile if updates are infrequent
relative to queries (which probably is the most common case,
but still...)


--Joe English

  jenglish at flightlab.com