Are XPath queries parsed right to left?

Question

This popular Stack Overflow question explained why CSS selectors are parsed right to left. Are XPath queries evaluated in the same way? If this is dependent on implementation I'd appreciate knowing how libxml2 does it.

Answer 1

It is meaningless and almost impossible to evaluate a path expression from right to left:

/name1/name2/name3/name4

By definition this selects all name4 elements that are children of any name3 element that is a child of any name2 element that is a child of the top element named name1.

Any statement in this chain relies on the next statement being true. Thus, by necessity, the evaluation needs to proceed from /name1 to /name1/name2 to /name1/name2/name3 and finally to /name1/name2/name3/name4

This is explicitly specified in the W3C XPath 1.0 specification:

A relative location path consists of a sequence of one or more location steps separated by /. The steps in a relative location path are composed together from left to right. Each step in turn selects a set of nodes relative to a context node. An initial sequence of steps is composed together with a following step as follows. The initial sequence of steps selects a set of nodes relative to a context node. Each node in that set is used as a context node for the following step. The sets of nodes identified by that step are unioned together. The set of nodes identified by the composition of the steps is this union. For example, child::div/child::para selects the para element children of the div element children of the context node, or, in other words, the para element grandchildren that have div parents.

Answer 2

You should take another careful read at the accepted answer for that question you reference.

CSS selectors are evaluated right-to-left as an implementation detail for the specific scenario where a browser has a single element and is trying to determine which selectors in a CSS stylesheet apply to it. The reason browsers evaluate right-to-left in this case is because candidate selectors can be eliminated more quickly.

There is nothing inherent to CSS selectors that demands they be evaluated right-to-left or left-to-right. In fact, jQuery or querySelectorAll will evaluate from left-to-right, as the answer notes.

In other words:

1. if you have one element and you are testing whether a selector matches it, it is usually faster to evaluate right-to-left as an optimization;
2. but if you want all matching elements, it is usually faster to evaluate left-to-right.

Scenario 1 fits best where you have an element to style (CSS) or an XSL stylesheet's template match="??" (XPath) and you have a large number of selectors or XPaths to test. Scenario 2 fits best when you have a single selector or XPath and you want all matching elements, as when you use querySelectorAll or query a DOM.

XPath expressions can be much more complex than CSS selectors, so there are probably XPaths where a right-to-left short-circuit evaluation is not possible or easy, but conceptually an XSLT engine could certainly try to do that. I don't know if any do.

The most important thing to understand is, however a CSS selector or XPath is evaluated, it must give the same answer as if it were evaluated left-to-right over the entire document tree. So you don't need to evaluate left-to-right, but you must act as if you did because the specifications define them this way.

Answer 3

When XSLT uses a pattern of the form match="a/b/c", you are interested in testing whether a specific node matches the pattern, and the simplest way of doing this is right-to-left. But when XPath uses an expression of the form select="a/b/c", you are interested in finding all the nodes that match, an the simplest way of doing this is left-to-right. However, processors aren't obliged (in either case) to work that way, and there may well be cases where specific processors optimize the expression into some other form. For example, given the XPath expression //a//b, a processor might well rewrite this as the equivalent //b[ancestor::a], which is effectively a right-to-left evaluation.