Parallel tree traversal

["Hunsberger, Peter" <Peter.Hunsberger@STJUDE.ORG>]

The discussion the other day on hierarchy and normalization got me
thinking about a particular problem we have. I know this belongs on the
XSLT list, but I'm being lazy and trying to avoid subscribing just to
ask this one question (and I happen to know that some of the people who
are likely to answer also hang out here... :-).

We have a metadata structure that we use to manage our system in various
ways.  At some point we wish to build a hierarchical menu to traverse
various specific data collections.  The overall menu structure is
reflected in the metadata similar to:

<metadata>
	<a>
		<b>
			<c/>
			<d>
				<e>
			</d>
		</c>
		<f/>
	</a>
</metadata>

There are many attributes on each element giving various pieces of
metadata, and in particular for this case, determining how a particular
node gets presented in the menu. For a given metadata structure we need
to map many possible data items, eg:

<data>
	<a id="1"/>
	<b id="2" idref="1"/>
	<c id="3" idref="2/>
	<d id="4" idref="3"/>
	<e id="5" idref="4"/>
	<e id="6" idref="4"/>
	<c id="7" idref="2/>
	<f id="8" idref="1"/>
	<a id="9"/>
	<b id="10" idref="9"/>
		...
</data>

Any given metadata node may not have any data associated with it.  If it
does, it must have a parent data item.  Using the data structure I can
determine that, in this, case I have to present a menu that has a
structure like:

<menu>
	<a id="1">
		<b id="2">
			<c id="3"/>
				<d id="4">
					<e id="5"/>
					<e id="6"/>
				</d>
			</c>
			<c id="7"/>
		</b>
		<f id="8"/>
	</a>
	<a id="9">
		<b id="10">
		...
	</a>
</menu>

The current strategy is to track the current id and pass it to a
recursive XSLT template selecting all the data nodes that have an idref
that is equal.  

It turns out that it would be easy to generate the tree structure for
the data directly.  However, I can't just use it directly, since if
there is a missing data item I may still have to insert a menu item to
create a new instance (depending on the metadata).  So, I need to track
the metadata as well. This is conceptually easy, just select the
children of the current element and recursively pass it on to the
template.  However, practically, this is expensive in XSLT 1.0 since to
subsequently use a parameter created in this manner it appears you have
to use the nodeset function.  Eg:

	<xsl:apply-templates select="*" mode="menu">
      	<xsl:with-param name="data" select="exslt:nodeset($data)/*"/>
	</xsl:apply-templates>

Now, in this particular case we are using Saxon, so this raises two
specific questions: 1) if I just declare the transform to be XSLT 1.1
and skip using the nodeset function will I see any performance gains?
2) Would using Saxon 7 and XSLT 2 have any performance gains?

A more general question is whether anyone sees any other strategy for
managing the above, or whether anyone has any opinions on which approach
should work better?  I can tell you that experiments with the second
approach traversing the metadata and passing the data as a parameter
seem to exhaust memory for large data trees though it works fine for
smaller trees. I'm about to see if I can do the inverse from the above
example: parse the data and pass the metadata as a parameter, but this
is a non-trivial transform (lots of metadata affecting many things) so I
thought I'd check first if anyone has a definite opinion about which way
to proceed.

Peter Hunsberger