Saxon

It doesn't actually look very difficult to do this. We handle streaming expressions like //book and //magazine by treating them as patterns and matching them against nodes in the streamed document; we already have the capability to construct a VennPattern representing the union, intersection, or difference between two patterns.

I've added tests sx-union-300 to -335 that test unions between (for the most part) two consuming operands, and a good number of them work as written. However, some are failing and need further examination to see what the spec says.

For example test -317 does

<xsl:value-of select="(/BOOKLIST/BOOKS/ITEM[1]/* union /BOOKLIST/BOOKS/ITEM[2]/*) ! contains(name(), 'E')"/>

and is failing

SXST0061  Navigation using child axis is not supported from a streamed input node

This failure seems spurious. The failure typically occurs because static analysis has concluded that the expression is streamable, but the run-time code fails to provide a streaming implementation. In particular, the union expression cannot be converted to a pattern because the filtered operands cannot be converted to patterns, which is ultimately because SubscriptExpressionAdjunct.toStreamingPattern() returns null (as does FirstItemExpressionAdjunct).

We implement streaming of an expression like /BOOKLIST/BOOKS/ITEM[1]/* not by generating a pattern that matches these nodes and nothing else, but by matching /BOOKLIST/BOOKS/ITEM nodes and counting them as they pass by. Union expressions seem to be streamable only if the operands can both be treated as patterns.

To make this test work, we need to be smarter than this. Essentially we need to treat it like an xsl:fork, where the two operands are evaluated independently (as separate Watches in the WatchManager) and the two feeds are then merged into one. This isn't a completely new concept, we do much the same thing for merging entries in a streamed map constructor, but it's certainly new code.

I've made good progress in allowing a union of striding sequences like (A/B/C union A/B/D), by having a watch for each operand feeding into a CombiningUnionFeed that forms the union of the two sequences. This is straightforward enough because the nodes arrive in the right order, and if the same node arrives from both inputs, they will be adjacent which makes it easy to detect the duplicate.

I'm having more difficulty with sequences that use the ancestor axis, for example

ITEM[1]/ancestor::* | ITEM[2]/ancestor::*

where the nodes arrive in the CombiningUnionFeed in the order BOOKLIST BOOKS ITEM[1] BOOKLIST BOOKS ITEM[2], and the BOOKLIST and BOOKS elements need to be de-duplicated.

The answer may be for the CombiningUnionFeed to accumulate nodes so long as they derive from the same WatchManager event (we could detect that by maintaining an event counter in the WatchManager).

Investigating sx-union-331 which does

select="(/BOOKLIST/BOOKS/ITEM[1]/PRICE/ancestor::* union /BOOKLIST/BOOKS/ITEM[2]/PRICE/ancestor::*) ! name()

there seems to be a problem with the streamed evaluation of the two operands. An expression of the form child::*/ancestor::* is handled by a DocumentSorterAdjunct which is supposed to sort the ancestors of a node before the node itself; but in fact it seems to be sorting the entire node sequence, meaning that it's not really streamed at all.

Considering the first expression on its own,

/BOOKLIST/BOOKS/ITEM[1]/PRICE/ancestor::*

it seems that when ITEM[1] is processed, a watch is created to catch PRICE, which fires and computes PRICE/ancestor::*, which sits around in the DocumentSorter until another event comes along. When ITEM[2] is processed, the watch correctly recognises that it doesn't need to do anything; it also recognises that there will be no further matches on future ITEMS; but it doesn't send any close() event up the pipeline until the end of the sequence of ITEMs is notified.

So in combining the two branches of the union, all the events for BOOKLIST BOOKS ITEM[1] BOOKLIST BOOKS ITEM[2] actually arrive when the endDocument() is processed.

With some careful tweaking to ensure that the combined stream of items is only closed once, I've now got the correct elements in the result: BOOKLIST BOOKS ITEM ITEM. The only problem is, the two items are in the wrong order. This is because the CombiningUnionFeed is designed to eliminate duplicates, but not to do a full sort into document order.

Items arrive at the CombiningUnionFeed in the order BOOKLIST BOOKS ITEM[2] BOOKLIST BOOKS ITEM[1] which implies we need to do a full sort into document order, which obviously isn't streamable.

Perhaps, though, we only need to do a full sort for items associated with the same WatchManager event (in this case all the items are associated with the endDocument() event, but that won't always be true. It's only true here because all the items in the incoming streams were buffered.)

This works for this test case...

Now looking at sx-union-334 which does

/BOOKLIST/BOOKS/ITEM/PRICE/ancestor-or-self::*/@CAT union /BOOKLIST/BOOKS/ITEM/QUANTITY/ancestor-or-self::*/@CAT

and -335 which does

//PRICE/ancestor-or-self::*/@* union //QUANTITY/ancestor-or-self::*/@*

The problem is eliminating duplicates. Looking at the second case, we're going to get a sequence of attributes by looking upwards from a PRICE element, followed by another sequence looking upwards from a QUANTITY. How can we eliminate duplicates with buffering the entire sequence? The technique of flushing the buffer if the WatchManager position has moved doesn't work - it has moved from PRICE to QUANTITY but still we can get duplicates.

Surely it can't be that difficult? We have two sequences of nodes coming from separate sources, each of which is in document order. We can flush a node N1 from sequence S1 as soon as we see a node from S2 that is beyond N1 in document order. The problem about this rule is that we currently don't know which operand expression the incoming nodes come from, because they both arrive via the same append() call. So we need to find a way of distinguishing the two input sequences.

Tests for intersect with two streaming operands have been added, and are now working.

The "except" case is giving me a little trouble. Given a case like (sx-except-316):

<xsl:copy-of select="(WEIGHT except *[@UNIT = 'oz'])"/>

we receive first a startSelectedParentNode() call for the first operand, immediately followed by a startSelectedParentNode() call for the second (assuming the same node satisfies both conditions). We can't register a receiver for the CopyOf action when the first event occurs until we know that the second event isn't going to occur. We need to start the CopyOf process while handling the start() event, but we can't respond to the absence of an event. (This is different from the intersect case where we only need to take action if there are two events).

Can we perhaps arrange things so the event for the second operand is guaranteed to come first?

Or can we rewrite the "except" as an "intersect", so we are notified of all events that are NOT selected by the second operand?

(Actually, this test -016 works, because the except expression can be translated to an equivalent motionless pattern. It's more complex conditions like test -017 where the problem arises.)

Putting the watch for the second operand first on the watchlist seems to work for most of the tests, but not for sx-except-312, where the event for the first watch is still being reported before the second. The reason for this is that the second operand first adds a watch for BOOKS elements, and only when this is matched does it add a watch for ITEM elements, and this watch is queued up behind the watch for the first operand.

Perhaps the startSelectedParentNode() action for the LHS operand could add a watch to the WatchManager that matches the current element; this will automatically be added to the end of the list, and will fire for this node after all the other startElement events; it can then see whether there have been any events for the second operand, and immediately remove the watch.