This is an archived snapshot of W3C's public bugzilla bug tracker, decommissioned in April 2019. Please see the home page for more details.

Bug 24534 - Streamability of the following-sibling axis with numbered predicates
Summary: Streamability of the following-sibling axis with numbered predicates
Status: CLOSED LATER
Alias: None
Product: XPath / XQuery / XSLT
Classification: Unclassified
Component: XSLT 3.0 (show other bugs)
Version: Last Call drafts
Hardware: PC Windows NT
: P2 normal
Target Milestone: ---
Assignee: Michael Kay
QA Contact: Mailing list for public feedback on specs from XSL and XML Query WGs
URL:
Whiteboard:
Keywords:
Depends on:
Blocks:
 
Reported: 2014-02-05 21:41 UTC by Abel Braaksma
Modified: 2014-05-15 14:00 UTC (History)
2 users (show)

See Also:


Attachments

Description Abel Braaksma 2014-02-05 21:41:53 UTC
Currently, the following-sibling axis is not streamable at all when applied to a streamable node. However, I think we can apply the same rules as for path expressions here if (and only if?) there is a predicate that is numeric.

We already define the notion of a numeric predicate, so we could reuse that.

It is quite easy to recognize this is streamable. Consider a counter-example first:

<xsl:template match="foo">
  <xsl:apply-templates select="following-sibling::bar" />
</xsl:template>

<xsl:template match="bar">
   <xsl:copy-of select="following-sibling::bar" />
</xsl:template>

This example is clearly _not_ streamable, because it travels the same nodes multiple times because of the two select statements using an unspecified following-sibling axis.

However, if we change it to use numeric predicates, this changes drastically:

<xsl:template match="foo">
  <xsl:apply-templates select="following-sibling::bar[1]" />
</xsl:template>

<xsl:template match="bar">
   <xsl:copy-of select="following-sibling::bar[2]" />
</xsl:template>

Now there is no potential for overlap. And it doesn't matter what positive numeric value is used, as it will always select only one following-sibling node.

The same does not apply to the following axis, in which case there can be overlapping nodes even when using numeric predicates as above.

There's a page by Michael Kay that I currently cannot find that mentions a similar scenario to be streamable in the Saxon processor. Not sure his scenario required the numeric predicate. I think it worthwhile to investigate whether we can add this to our toolset of streamable expressions, because it covers quite a few use-cases.
Comment 1 Michael Kay 2014-02-06 10:54:08 UTC
While I agree that we could theoretically extend our streaming model to permit the "sibling recursion" pattern, I think this would be a significant extension of the model and we should not attempt it.

Given a template that does

<xsl:apply-templates select="foo"/>

then if the template that matches "foo" attempts to process its following siblings, those following siblings are going to be processed more than once, so there is "overlap". This doesn't necessarily make it impossible (we could manage the overlap using output buffering) but it needs careful thought. Equally, we could eliminate the overlap if we constrain the apply-templates to only select the first child; a mode would then be streamable if either (a) all templates satisfy the current streamability rules, allowing selection of all children, or (b) all templates follow the sibling-recursion pattern by selecting only the first child and/or the first following sibling. That's possible but a big extension to our current scope.

I think the Saxon reference is probably a mis-remembering. Saxon does currently retain not only the stack of ancestors and their attributes, but positional information about the position of the ancestors among their siblings. This is something we once proposed in the WG but which has disappeared from the spec. Saxon currently uses it primarily to permit positional patterns of the form match="para[1]". Theoretically it could also be used to support some simple forms of xsl:number, but Saxon doesn't currently do that. Supporting streamed sibling recursion seems a different matter entirely, and is certainly something Saxon has never attempted.
Comment 2 Abel Braaksma 2014-02-12 09:52:16 UTC
The place where you mentioned this as streamable, although being hard to analyse, is a Balisage talk: http://www.balisage.net/Proceedings/vol5/html/Kay01/BalisageVol5-Kay01.html
Comment 3 C. M. Sperberg-McQueen 2014-02-12 09:59:50 UTC
The WG discussed this during the ftf meeting in Prague.

We agreed that right-sibling selection is streamable under some conditions, but those include abandoning the current emphasis on the single-downward-select safety mechanism and replacing it with a more subtle analysis.  (Declaration of the tree traversal discipline on a mode declaration could make it possible.)

We were not inclined to extend the streamability analysis so deeply at this point.