Recursively including all dependencies of an element

Discussion in 'XML' started by Scott Sauyet, Jun 4, 2007.

  1. Scott Sauyet

    Scott Sauyet Guest

    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">
    <xsl:eek:utput method="xml" indent="yes" omit-xml-declaration="no" />

    <xsl:param 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">
    <xsl:param name="data" />
    <xsl:value-of select="concat(normalize-space($data), ' ')" />
    </xsl:template>

    <xsl:template name="choose-names">
    <xsl:param 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>
    <xsl:eek:therwise>
    <xsl:call-template name="choose-names">
    <xsl:with-param name="names" select="$temp" />
    </xsl:call-template>
    </xsl:eek:therwise>
    </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
    Scott Sauyet, Jun 4, 2007
    #1
    1. Advertising

  2. Scott Sauyet wrote:
    > 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">
    <xsl:eek:utput method="xml" indent="yes" omit-xml-declaration="no" />

    <xsl:param name="base" select="'a b'"/>

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

    <xsl:template match="root">
    <xsl:param name="set" select="x[contains($base,@name)]"/>
    <xsl:param 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



    --
    http://dpcarlisle.blogspot.com
    David Carlisle, Jun 4, 2007
    #2
    1. Advertising

  3. Scott Sauyet

    Scott Sauyet Guest

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

    David Carlisle wrote:
    > Scott Sauyet wrote:
    >> 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 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, Jun 5, 2007
    #3
  4. Scott Sauyet

    Scott Sauyet Guest

    Scott Sauyet wrote:
    > David Carlisle wrote:
    >> 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.


    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
    >> 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


    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
    Scott Sauyet, Jun 5, 2007
    #4
  5. Scott Sauyet wrote:
    > 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

    --
    http://dpcarlisle.blogspot.com
    David Carlisle, Jun 5, 2007
    #5
  6. Scott Sauyet

    Scott Sauyet Guest

    David Carlisle wrote:
    > 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
    Scott Sauyet, Jun 5, 2007
    #6
  7. 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


    --
    http://dpcarlisle.blogspot.com
    David Carlisle, Jun 6, 2007
    #7
  8. Scott Sauyet

    Scott Sauyet Guest

    On Jun 5, 7:05 pm, David Carlisle <>
    wrote:
    > <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
    Scott Sauyet, Jun 6, 2007
    #8
  9. 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!

    --
    Joe Kesselman / Beware the fury of a patient man. -- John Dryden
    Joseph Kesselman, Jun 6, 2007
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Lanny McDonald
    Replies:
    1
    Views:
    334
    Alvin Bruney [MVP]
    Apr 3, 2004
  2. Cal Who
    Replies:
    13
    Views:
    1,666
    Registered User
    May 23, 2010
  3. Mark

    User Controls including themselves recursively

    Mark, Jul 14, 2003, in forum: ASP .Net Web Controls
    Replies:
    2
    Views:
    111
  4. Tamara
    Replies:
    2
    Views:
    110
    Michele Dondi
    Apr 7, 2004
  5. Feyruz
    Replies:
    15
    Views:
    217
    Tad McClellan
    Nov 30, 2005
Loading...

Share This Page