Forgot reference:

[1] http://www.w3.org/TR/xslt-30/#streamability-of-path-expressions

This bug was originally discovered by Eugene Fotin.

As discussed on the telcon today. section 19.1 of the spec is designed to address this problem. However, we felt at Prague that 19.1 lacks precision and should be made more prescriptive.

I think this can be done as follows.

(a) For every *selection pattern* P, there is an implicit *matcher function* M<P> [angle brackets indicate a subscript]. The matcher function has the signature M<P>($n as node()) as xs:boolean, and the semantics of the function are such that M<P>(N) returns true if and only if N is a node that matches the pattern P.

(b) Definition: A *scanning expression* is an expression E that is the *equivalent expression* of some *motionless* *selection pattern* P, provided that E is not a subexpression of some containing expression that is itself a *scanning expression*, and that the static type of E does not include attribute or namespace nodes.

Before analyzing a construct C for streamability, but after expansion of abbreviations such as "//", any *scanning expression* E contained (at any depth) within C is rewritten as

descendant::node()[M<P>(.)]

where P is the motionless pattern whose *equivalent expression* is E.

For example, descendant::section/child::head is replaced by descendant::node()[F(.)] where F(N) returns true for nodes that match the pattern descendant::section/head.

(c) A matcher function taking the context item as its argument is grounded and motionless.

Note: any expression that meets these criteria is thus evaluated by scanning all descendant nodes in document order and testing each one to see whether it matches the corresponding pattern. This execution strategy is streamable, whereas a nested-loop evaluation strategy that followed the XPath semantics more closely might not be streamable. Of course, processors are free to adopt a different algorithm that achieves the same effect and preserves guaranteed streamability.

Note: the exclusion of patterns that match attributes or namespace nodes is a simplification that does not adversely affect streamability. It means that given an expression such as //section/head/@status, which is rewritten as descendant-or-self::node()/child::section/child::head/attribute::status, the expression descendant-or-self::node()/child::section/child::head acts as the *selection expression* to be replaced by a filter expression using a matcher function; this filter expression is streamable, with crawling posture, and the addition of an axis step using the attribute or namespace axis then creates an expression with climbing posture.

I failed to capture in the forgoing rules the constraint that the matching operation must occur within the subtree of the context node. I now recall this constraint causing us sime difficulty in Prague.

One approach to this might be to take the definition of the semantics of selection patterns:

<quote>
Specifically, an item N matches a pattern P if the following applies, where EE is the equivalent expression to P:

N is a node, and the result of evaluating the expression root(.)//(EE) with a singleton focus based on N is a sequence that includes the node N
</quote>

and modify it to say:

<new>
an item N matches a pattern P within a (sub)tree rooted at $A if the following applies, where EE is the equivalent expression to P:

N is a node, and the result of evaluating the expression $A//(EE) is a sequence that includes the node N

When $A is not otherwise specified, it is taken as root(N).
</new>

The matcher function M<P> then becomes M<P>(N, A), returning true if the pattern matches a node N within a subtree rooted at A, and the rewrite of a scanning expression  becomes 

let $A := . return $A/descendant::node[M<P>(., $A)]

Unfortunately the above proposal has a rather serious bug. The expression child::x gets rewritten to something like //*[self::x] which not only gives the wrong answer, it also has the wrong posture.

There's also (at least one) further bug. The expression //x is not streamable unless the context item happens to be the document node, but it is equivalent to a motionless pattern and gets rewritten under the proposed rules.

I'm therefore wondering about a different formulation. Delete section 19.1, and instead of preprocessing the expression tree, we do the streamability analysis as described and then have a second attempt if it fails. More specifically, in section 19.8.7.6 Streamability of Path Expressions, we recast the rules as follows:

1. Compute the provisional posture and sweep, as follows:

  (insert the existing rules)

2. If the provisional posture is roaming or the provisional sweep is free-ranging (or both), and if the path expression is a *scanning expression* (defined below), then the posture is crawling and the sweep is consuming. Otherwise, the posture and sweep of the path expression are the provisional posture and sweep.

Definition: A *scanning expression* is a relative path expression in the form L/R that satisfies the following conditions:

(a) each of the operands L and R is either (i) a scanning expression, or (ii) an AxisStep whose axis is child, descendant, descendant-or-self, or self.

(b) the expression is the *equivalent expression* of some *motionless pattern*. (That is, when the expression is considered as a pattern, the rules for classifying patterns (19.8.9) deem the pattern to be motionless.)

Rationale: note that we are no longer doing anything to change the semantics of the expression, we are only defining its streamability properties. The responsibility for devising a correct streaming implementation of such expressions is thus left entirely to the implementor, as it should be. In addition, we only invoke this rule as a fallback if the expression would otherwise be non-streamable, which reduces the risk of introducing bugs.

As an alternative to (b) we could inline the rules for motionless patterns: basically, the top-level predicates must be motionless and non-positional.

We will obviously need to add explanations for the reader; much of the required material already exists.

The new rules no longer apply to union expressions. But I think we've relaxed the rules for unions in 19.8.7.4 sufficiently that they no longer need special treatment. Under the above rules, section//(author|publisher) is not streamable because the expression is not a "scanning expression". I think we can live with this.

Just to add my support and a careful monitoring of this bug because it goes in the direction to fully support "XML Signature Streaming Profile of XPath 1.0" subset [1]


[1] http://www.w3.org/TR/xmldsig-xpath/

*** Bug 24490 has been marked as a duplicate of this bug. ***

A detailed proposal that develops the idea in comment #5 was produced here:

https://lists.w3.org/Archives/Member/w3c-xsl-wg/2014Jul/0007.html

(member only) and was accepted by the WG with minor changes (Minutes 10 July 2014). The changes have been applied.