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

[Joe English]

Uche Ogbuji wrote:

> [Joe English]
> > That might be desirable.  The result of any multi-step
> > location path will be a list in document order with no
> > duplicates, which is compatible with XPath 1 node sets.
>
> You mean that is how XPath 1.0 node sets are often interpreted, right?

Right.

XPath 1.0 expressions "officially" return node sets,
but in almost all use cases the result is processed
sequentially (i.e., as a node list).

> To go back to my example.  Document:
>
> <a>
>     <b>
>         <c/>     <--- context node
>     </b>
>     <d/>
>     <e/>
> </a>
>
> In XPath 1.0,
>
> (ancestor::*/*)[1]
>
> Would return
>
> {c}

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}.

> [...]

> > IOW, instead of merging the result lists, simply concatenate them.
> And remove dupes.
>
> > I like this approach better, but it's a bigger change from XPath 1.
> Hmm.  Or do you mean *don't* remove dupes?  I do think that would be too big
> a change.

Right, I mean *don't* remove duplicates.  At least that's the
approach I would favor if XPath 1.0 compatibility weren't an issue.
Depending on how _important_ that issue is, sorting and removing
duplicates might still be preferable.

Something else to consider:  although sorting in document order
can be done fairly cheaply for static documents, (O(N log N) worst
case, O(N+M) for merging), it's more expensive on mutable documents.
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.


--Joe English

  jenglish at flightlab.com