Recursively including all dependencies of an element

[Scott Sauyet]

I found myself needing to find my way recursively through a document
in XSLT, finding the dependencies one element had on others, and
including only those in an initial set, their dependencies, the
dependencies of those dependencies and so on. I managed to do it, but
I'm not really happy with the method, and I'm wondering if anyone can
suggest something better.

My technique involves manipulating a string containing the names,
calling a template that adds the names of the direct dependencies to a
temporary string and then, if there are no additional names, returning
that list, or, if there are additional ones, returning a recursive
call to the template using the new list. It's pretty simple Recursion
101 code, but there's a level of indirection I don't like here. I
shouldn't be using a string of names; I would rather be using node-
sets. But whenever I tried that, I ran into issues of variables that
held things that looked like but weren't really node-sets.

Any suggestions for how I could do this without resorting to using the
names, would be appreciated.

Here's a simplified sample input document:

<root>
<x name="a">
<y dep="b"/>
<y dep="c"/>
</x>
<x name="b">
<y dep="g"/>
</x>
<x name="c">
<y dep="a"/>
</x>
<x name="e">
<y dep="b"/>
</x>
<x name="f">
<y dep="c"/>
<y dep="e"/>
</x>
<x name="g">
<y dep="h"/>
</x>
<x name="h">
<y dep="i"/>
</x>
<x name="i"/>
<x name="j">
<y dep="i"/>
</x>
</root>

Passed the parameter, "a, b", the stylesheet should note that 'a'
depends on 'b' and' c', 'b' depends on 'g', which depends on 'h',
which depends on 'i', which has no further dependencies. And 'c'
depends on 'a'. That last is important because it demonstrates that
this is not necessarily a tree structure. There are cycles.

The output should be something like:

<root>
<x name="a">
<y dep="b"/>
<y dep="c"/>
</x>
<x name="b">
<y dep="g"/>
</x>
<x name="c">
<y dep="a"/>
</x>
<x name="g">
<y dep="h"/>
</x>
<x name="h">
<y dep="i"/>
</x>
<x name="i"/>
</root>

The XSLT I use for this is pretty straightforward:

<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xslutput method="xml" indent="yes" omit-xml-declaration="no" />

<xslaram name="base" select="'a b'"/>

<xsl:variable name="start">
<xsl:call-template name="normalize">
<xsl:with-param name="data" select="$base"/>
</xsl:call-template>
</xsl:variable>

<xsl:template match="/">
<root>
<xsl:variable name="names">
<xsl:call-template name="choose-names">
<xsl:with-param name="names" select="$start"/>
</xsl:call-template>
</xsl:variable>
<xsl:for-each select="//x">
<xsl:if test="contains($names, @name)">
<xsl:text>
</xsl:text><xsl:copy-of select="."/>
</xsl:if>
</xsl:for-each>
</root>
</xsl:template>

<xsl:template name="normalize">
<xslaram name="data" />
<xsl:value-of select="concat(normalize-space($data), ' ')" />
</xsl:template>

<xsl:template name="choose-names">
<xslaram name="names"/>
<xsl:variable name="temp">
<xsl:for-each select="//x">
<xsl:variable name="name" select="@name"/>
<xsl:if test="contains($names, $name) or
//x[contains($names, @name)]/y[@dep = $name]">
<xsl:value-of select="@name"/><xsl:text> </
xsl:text>
</xsl:if>
</xsl:for-each>
</xsl:variable>
<xsl:choose>
<xsl:when test="$names = $temp">
<xsl:value-of select="$temp"/>
</xsl:when>
<xsltherwise>
<xsl:call-template name="choose-names">
<xsl:with-param name="names" select="$temp" />
</xsl:call-template>
</xsltherwise>
</xsl:choose>
</xsl:template>

</xsl:stylesheet>

I know there are holes in the string processing here. I'm sure I
could tighten it up by using a separator other than space and then
doing some escaping if the name contained the separator, but since I'd
rather not be using the names anyway...

So, does anyone have suggestions for how to do this without resorting
to using strings (except to get the original set from the input
parameter?)

Thank you very much,

-- Scott Sauyet

 

[David Carlisle]

I would rather be using node-
sets. But whenever I tried that, I ran into issues of variables that
held things that looked like but weren't really node-sets.

result tree fragments. If using XSLT2 is an option then that particular
problem goes away as rtf is no more (node sets are also gone) both
replaced by sequences.

I'm not quite sure what output format you want but probably something
like this in xslt1 will chase your dependencies


<xsl:stylesheet version="1.0"
xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xslutput method="xml" indent="yes" omit-xml-declaration="no" />

<xslaram name="base" select="'a b'"/>

<xsl:key name="x" match="x" use="@name"/>

<xsl:template match="root">
<xslaram name="set" select="x[contains($base,@name)]"/>
<xslaram name="s" select="1"/>
Stage <xsl:value-of select="$s"/> set is <xsl:for-each
select="$set">
<xsl:value-of select="@name"/>
<xsl:text> </xsl:text></xsl:for-each>
<xsl:variable name="nset" select="$set|key('x',$set/y/@dep)"/>
<xsl:if test="count($nset)&gt;count($set)">
<xsl:apply-templates select=".">
<xsl:with-param name="set" select="$nset"/>
<xsl:with-param name="s" select="$s+1"/>
</xsl:apply-templates>
</xsl:if>
</xsl:template>
</xsl:stylesheet>



$ saxon dep.xml dep.xsl
<?xml version="1.0" encoding="utf-8"?>
Stage 1 set is a b
Stage 2 set is a b c g
Stage 3 set is a b c g h
Stage 4 set is a b c g h i

 

[Scott Sauyet]

Thank you very much for your help. This is a real improvement from my
ugly hack!

result tree fragments. If using XSLT2 is an option then that particular
problem goes away as rtf is no more (node sets are also gone) both
replaced by sequences.

I honestly don't even know what XSLT processor I'm using, at the
moment; it's whatever default Ant 1.7 has when running on Java 1.6
(Xalan?). I can switch to whatever I want, as this will just end up
part of the build process. The actual problem is to reduce a WSDL
document to a smaller one based upon a parameter that lists the high-
level services to include. I worked my way through the services,
bindings, port-types, and messages based upon that input parameter.
And, with some help from the kind people on this list, I got the
initial list of the custom xs:simpleTypes and xs:complexTypes needed
to support the selected messages, but I then need to recursively work
through their dependencies.

As I said in my original message, I had this working, but wasn't happy
with the technique. I'm glad to know that there is something better;
and I'll be updating my stylesheet soon with your suggestions.

I'm not quite sure what output format you want but probably something
like this in xslt1 will chase your dependencies

I actually need to output format to be identical to the input format,
just with a smaller set of elements chosen. It was pretty simple to
modify your suggestion, though, to get that. Thank you again for your
help.

-- Scott

 

[Scott Sauyet]

I actually need to output format to be identical to the input format,
just with a smaller set of elements chosen. It was pretty simple to
modify your suggestion, though, to get that. Thank you again for your
help.

I suppose I should double-check that I'm looking at the output of my
new process rather than the old one before I claim that it's
working! :-(

Things aren't working correctly in Ant1.7/Java1.6. When I run them
through Saxon, though, it's all fine. Any idea what might be causing
this?

I was going to move this into my main code and noticed an odd bit in
my output. I had been looking at the output of an earlier version
before; the one I called the ugly hack. So I ran again with David'
Carlisle's code and noticed a subtle difference in output:

David Carlisle's
Mine:
Stage 1 set is a b
Stage 2 set is a b c g
Stage 3 set is a b c g h
Stage 4 set is a b c g h i

Note the extra space after "Stage 3 set is"? And stage 4 too? This
is the output of

<xsl:value-of select="@name"/>
<xsl:text> </xsl:text>

for the context node of the third and fourth iteration, which seems to
be the document node itself. !!?? I checked this by inserting a line
that counts the child elements of the context node:

<xsl:value-of select="count(.//*)"/><xsl:text>:</xsl:text>
<xsl:value-of select="@name"/>
<xsl:text> </xsl:text>

And I get this output:

Stage 1 set is 2:a 1:b
Stage 2 set is 2:a 1:b 1:c 1:g
Stage 3 set is 20: 2:a 1:b 1:c 1:g 1:h
Stage 4 set is 20: 2:a 1:b 1:c 1:g 1:h 0:i

Note that the input document has twenty elements, and the counts in
this list for the number of elements inside the named elements are all
correct (x[@name='a'] has two children, 'b' has one, ... 'i' has
zero.)

I can't understand how this line:

<xsl:variable name="nset" select="$set|key('x',$set/y/@dep)"/>

with the key

<xsl:key name="x" match="x" use="@name"/>

and a $set value that contains only elements of type "x" could ever
generate a value for $nset that includes the root node. But that is
certainly what seems to be happening.

I thought I was just going crazy, but I've realized it's not me, it's
my XSLT processor that's awry. When I run it through SAXON,
everything works fine.

Anyone have an idea what this is about?

-- Scott

 

[David Carlisle]

Scott Sauyet wrote:

I thought I was just going crazy, but I've realized it's not me, it's
my XSLT processor that's awry. When I run it through SAXON,
everything works fine.

Anyone have an idea what this is about?

-- Scott

when something works in saxon and not in another processor you always
have the possibility that you've hit a bug somewhere. If your
description is accurate it sounds like something strange is happening
with the key.

David

 

[Scott Sauyet]

when something works in saxon and not in another processor you always
have the possibility that you've hit a bug somewhere. If your
description is accurate it sounds like something strange is happening
with the key.

As you may be able to tell, I haven't been doing all that much XSLT
recently. I'm much more likely to doubt myself than the tools when
I'm inexperienced or rusty with a technology. But there is a clear-
cut difference between when I run this stylesheet through Saxon and
when I run it through my default processor. Maybe it's not me after
all!

Is Saxon generally considered the gold standard? I don't know what
version of Xalan is being used in my default setup (Ant 1.7 on Java 6)
but it looks as though it is Xalan, since this:

javax.xml.transform.TransformerFactory.newInstance().getClass()

returns this:


com.sun.org.apache.xalan.internal.xsltc.trax.TransformerFactoryImpl


In any case, thank you very much for your help,

-- Scott

 

[David Carlisle]

Scott Sauyet wrote:

> I don't know what
version of Xalan is being used in my default setup (Ant 1.7 on Java 6)
but it looks as though it is Xalan,

<xsl:value-of select="system-property('xsl:vendor')" />

<xsl:value-of select="system-property('xsl:vendor-url')" />

should reveal all

 

[Scott Sauyet]

<xsl:value-of select="system-property('xsl:vendor')" />
<xsl:value-of select="system-property('xsl:vendor-url')" />

should reveal all

And it does.:

Vendor: Apache Software Foundation (Xalan XSLTC)
URL: http://xml.apache.org/xalan-j

Thank you very much. I'm pretty swamped today, but later this week,
I'll try to post a simple test case and see about reporting a bug to
Xalan.

Thanks,

-- Scott

 

[Joseph Kesselman]

Reminder: The version of Xalan that ships with the JVM is pretty far
outdated. If you've found a bug, the first thing to try is downloading a
current version from Apache, overriding the JVM's copy (you'll need to
play with the bootclasspath/endorsed-libraries configuration to do this;
instructions are also on the Xalan website), and see if the problem
persists.

If that cures it, you're good to go... except that anyone else using
your code will also have to install the updated version of the processor.

If not, then by all means submit a bug report!