RE: [xsl] Walking a complex object graph

Subject: RE: [xsl] Walking a complex object graph
From: William R. Swanson <traveler@xxxxxxxxxxxxx>
Date: Fri, 16 Jul 2004 14:48:5 EST
   From: Michael Kay [mailto:mhk@xxxxxxxxx]
   To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
   Subject: RE: [xsl] Walking a complex object graph

   You need to explain the problem in more concrete terms.

   Graph traversal becomes much easier in XSLT 2.0, which allows you to
   recursive functions that return existing nodes, rather than copies, and
   which makes it much easier to compare node identity.

   Some algorithms also benefit from function memoisation, which is
   provided in
   Saxon (though only working with some restrictions in 8.0).

   Michael Kay

Thanks much for the reply --

Specifically, assume that one has a set of in-memory objects X, Y, Z...
etc, with properties such as "name", "ID", etc. These objects have
references to each other, and these references might be single objects
or they might be lists. So for example X.ref1 might be Y,
and Y.ref2 might be the list ( X, Y, Z ).

Note in particular that there may be circularities in the references,
so this is best viewed as an arbitrarily-connected graph of objects.

We'd like to construct an XSLT-processable object (in .NET this is
an XPathNavigator, in Xalan or other environments it might be a DOM class
or the like) that allows an XSLT script to "walk" this graph of objects
and pull out specific instances or values.

>From the point of view of the XSLT processor, the above-described
set of objects X, Y, and Z could be represented as a "virtual"
XML document something like:

    <object name="X">
        <object name="Y">
            <object name="X">
            <object name="Y">
            <object name="Z">
    <object name="Y">

So for example, given the objects X, Y, and Z noted above,
where X.ref1 = Y and Y.ref2 = (X, Y, Z), we'd like to be able
to write the following XSLT:

    <xsl:for-each select="/allobjects/object[@name='X']/ref1/object[@name='Y']/ref2" >
      <name><xsl:value-of select="@name"></name>

To produce XML something like:


Now, it seems that to do this one should be able to write a custom
XPathNavigator, DOM object, etc. that simply keeps track of where
it is in the object graph, and simply returns the right "attribute"
and "child node" information accordingly when this is demanded of
it by the XSLT transform processing engine.

However, it appears that the .NET XSLT engine is either attempting
to read the entire XML structure into memory, or simply performing
very deep searches, which often results in the XSLT engine getting
stuck in an infinite loop. (I.e. if X -> Y and Y -> X, then you can
keep ping-ponging back and forth endlessly between the two objects.)

We're suspecting the problem is not an issue with the XSLT code we're
writing, but a problem with the way the XSLT engine is processing it,
and we're wondering if there's a better XSLT engine (Xalan? Saxon?)
to use for this kind of application.

Or is this simply an incorrect application of XSLT?
For example do XSLT implementations generally assume the source
document is finite, and can be completely read into memory
before the transformation begins?

--- WRS

Current Thread