I’m relatively new to XSLT and must admit I’m finding it refreshing, but every now and again something comes along which floors me. Maybe it’s the old imperative language background that is hard to shake. This is an example of a dark cloud in my brave new declarative world. Clearing duplication is bread and butter but in XSLT it’s not. The old preceding axis method is both too slow and destined to failure. The Muenchian method, although sublime to the novice also seems to become unstuck (have I missed something obvious). I cast my sanity and naivety over to the community.

The XML included is a psuedo subset of a much larger file, which is generated from a network management system. Each submap tag contains a collection of devices and essentially other submaps which in-turn can contain a collection of devices and submaps and so on.

The problem is, given a submap level that can be passed as a parameter into the stylesheet. I need to form a unduplicated list of groups ( node grps) contained within the submap nodes at the current context of interest. This includes submaps which are descendants of each of the submaps of the context of interest. Let me get the XML and an example of the target output needed this is getting too wordy already.


XML

<?xml version="1.0" encoding="utf-8"?>
<root>
    <submap name="A">
        <device>
            <devname>rtr001</devname>
            <grp>router</grp>
        </device>
        <submap name="E">
            <device>
                <devname>rtr005</devname>
                <grp>router</grp>
            </device>
            <device>
                <devname>SW0001</devname>
                <grp>switch</grp>
            </device>
        </submap>
    </submap>
    <submap name="B">
        <submap name="F">
            <submap name="G">
                <submap name="H">
                    <device>
                        <devname>ftp003</devname>
                        <grp>ftpserver</grp>
                    </device>
                    <device>
                        <devname>www001</devname>
                        <grp>webserver</grp>
                    </device>
                </submap>
                <device>
                    <devname>rtr007</devname>
                    <grp>router</grp>
                </device>
                <device>
                    <devname>SW0002</devname>
                    <grp>switch</grp>
                </device>
                <device>
                    <devname>rtr006</devname>
                    <grp>router</grp>
                </device>
                <device>
                    <devname>srv001</devname>
                    <grp>server</grp>
                </device>
            </submap>
        </submap>
        <device>
            <devname>rtr002</devname>
            <grp>router</grp>
        </device>
        <submap name="I">
            <device>
                <devname>rtr005</devname>
                <grp>router</grp>
            </device>
            <device>
                <devname>hub001</devname>
                <grp>hub</grp>
            </device>
        </submap>
    </submap>
    <submap name="C">
        <submap name="j">
            <device>
                <devname>rtr006</devname>
                <grp>router</grp>
            </device>
            <device>
                <devname>av0001</devname>
                <grp>antivirus</grp>
            </device>
        </submap>
        <device>
            <devname>rtr003</devname>
            <grp>router</grp>
        </device>
    </submap>
    <submap name="D">
        <device>
            <devname>rtr004</devname>
            <grp>router</grp>
        </device>
        <device>
            <devname>pop001</devname>
            <grp>mailserver</grp>
        </device>
    </submap>
</root>

Target Output ( using target submap B – Context node)

Groups for submaps in B context.

Submap F - router ftpserver,webserver,switch,server
Submap I – router,hub




What I can get, and what I have tried and failed at

What is possible?

A list of all down stream grps split by submap but containing duplicates.

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:param name="targetsubmap">B</xsl:param>

<xsl:template match="/">
<xsl:apply-templates select="//submap[@name=$targetsubmap]" mode="test"/>
</xsl:template>

<xsl:template match="submap" mode="test">
<xsl:text>
Groups for submaps in </xsl:text><xsl:value-of select="@name"/><xsl:text> context.
</xsl:text>
<xsl:apply-templates select="submap" mode="level">
</xsl:apply-templates>
</xsl:template>
<xsl:template match="submap" mode="level">
<xsl:text>
Submap </xsl:text>
<xsl:value-of select="@name"/><xsl:text> - </xsl:text>
<xsl:for-each select="descendant::grp">
<xsl:value-of select="."/>
<xsl:if test="position() != last()">,</xsl:if>
</xsl:for-each>
</xsl:template>

</xsl:stylesheet>


Output

Groups for submaps in B context.

Submap F - ftpserver,webserver,router,switch,router,server
Submap I - router,hub

Note router is duplicated in submap F list, it should be in submap I list

What also fails.

The Muenchian Method

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:param name="targetsubmap">B</xsl:param>
<xsl:key name="kdgroups" match="//device" use="grp"/>

<xsl:template match="/">
<xsl:apply-templates select="//submap[@name=$targetsubmap]" mode="test"/>
</xsl:template>

<xsl:template match="submap" mode="test">
<xsl:text>
Groups for submaps in </xsl:text><xsl:value-of select="@name"/><xsl:text> context.
</xsl:text>
<xsl:apply-templates select="submap" mode="level">
</xsl:apply-templates>
</xsl:template>

<xsl:template match="submap" mode="level">
<xsl:text>
Submap </xsl:text>
<xsl:value-of select="@name"/><xsl:text> - </xsl:text>
<xsl:for-each select="descendant::device[generate-id(.)=generate-id(key('kdgroups',grp))]">
<xsl:value-of select="grp"/>
<xsl:if test="position() != last()">,</xsl:if>
</xsl:for-each>
</xsl:template>

</xsl:stylesheet>

OUTPUT

Groups for submaps in B context.

Submap F - ftpserver,webserver,server
Submap I - hub

This seems to fail because, once an id is generated(see what happens to the router group) it is no longer available to subsequent submaps so it is not included within the output tree as needed. Adding the context to the key declaration would reduce the amount of elements the key is applied to but would still fail. The router and switch groups would appear in the submap F list but not the submap I list as needed. Also the context is passed in as a parameter that cannot appear in the match clause of the key declaration.

The preceding axis solution as per O’Reiley Cookbook – although probably way to slow on a larger file. I attempted this method just in-case. It fails for the same reason as the Muenchian Method. Can any one explain the trailing comma?

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:param name="targetsubmap">B</xsl:param>

<xsl:template match="/">
<xsl:apply-templates select="//submap[@name=$targetsubmap]" mode="test"/>
</xsl:template>

<xsl:template match="submap" mode="test">
<xsl:text>
Groups for submaps in </xsl:text><xsl:value-of select="@name"/><xsl:text> context.
</xsl:text>
<xsl:apply-templates select="submap" mode="level">
</xsl:apply-templates>
</xsl:template>

<xsl:template match="submap" mode="level">
<xsl:text>
Submap </xsl:text>
<xsl:value-of select="@name"/><xsl:text> - </xsl:text>
<xsl:for-each select="descendant::grp">
<xsl:sort select="."/>
<xsl:if test="not(self::node()=preceding::node())">
<xsl:value-of select="."/>
<xsl:if test="position() != last()">,</xsl:if>
</xsl:if>
</xsl:for-each>
</xsl:template>

</xsl:stylesheet>


Output

Groups for submaps in B context.

Submap F - ftpserver,server,webserver
Submap I - hub,

If anybody finds a solution which requires the source XML to be altered this is ok as I wrote the Interface to the Network Management System so I can change it. I should note that the XML you can see is a massively simplified abstraction to demonstrate the point. Basically if I have to change it I will.

Hopefully thanks for the help, let me know any methods you have tried even if they fail so I can tick them of the list. I’m hoping I have misunderstood Muenchian.

Ray

This is how I am looking at solving the problem.

The Muenchian Method is good for finding non-duplicated lists throughout the entire document but it seems like it cannot be used to find multiple no-duplicated lists for sub-trees of the main document.

The steps I think I need to follow are (in a kind psuedo wordy descriptive way):

1. Create a non-duplicated list of grps within the entire document call it totgrps use Muenchian to create this list.

2. For each submap which is a child of the context node of interest.

3. Loop through the totgrps list call the active group member loop_grp

4. count the number of descendants that have grp=loop_grp

5. If count > 0 loop_grp needs to be added to the list

I just need to work out the XSLT to do this, I’ll put an update when I have tried it

Ray

Sorry not to give a detailed response to this one, but I tend to live in an XSLT 2.0 world nowadays and am happy to have kissed goodbye to Muenchian grouping.

The usual way of doing Muenchian grouping on a subtree of the document is to use the generate-id() of the subtree root as part of the grouping key.

Your steps look excessively procedural to me: it's much better to express your design in functional terms if you can.

Michael Kay
http://www.saxonica.com/
Author, XSLT Programmer's Reference and XPath 2.0 Programmer's Reference

Hi Michael,

I've just ordered your XSLT 2.0 book from Amazon so I can find my way to XSLT 2.0 world as nobody wants to kiss goodbye to Muenchian grouping more than me.

Is what I am doing possible using XSLT 2.0.

I obviously need to re jig my serverside. I am currently using MSXML via python to transform XML into SVG. Prior to your book arriving where do you recommend I start looking, for an appropriate serverside set up.

In your response you say

The usual way of doing Muenchian grouping on a subtree of the document is to use the generate-id() of the subtree root as part of the grouping key.

How do I do this as the subtree is defined by the parameter which is passed into the stylesheet. I cannot use the parameter within the match clause of the grouping key at the start of the stylesheet.

Believe me I am trying to think in a declarative style but old habits are hard to shake.

Cheers
Ray

The only viable XSLT 2.0 processor at the moment is still probably my own Saxon product. (OK, that's not impartial advice: there are others available - Gestalt and Altova - but they are far less mature and complete). The primary interface to Saxon is Java. There's a Saxon.NET port which gives you .NET versions of the interfaces, but they are still basically Java interfaces. So a lot depends on how Javaphilic or -phobic you are.

I haven't looked at your actual grouping problems in any detail but at first sight they look well within the capabilities of XSLT 2.0 grouping constructs.

Michael Kay
http://www.saxonica.com/
Author, XSLT Programmer's Reference and XPath 2.0 Programmer's Reference

At last I’ve got the swine, well almost, I need to fix the trailing comma (<xsl:if test="position() != last()">,</xsl:if> does not work as I cannot guarantee position).


I know it probably has flaws but it works. If anybody has a better way could you let me know or if anybody knows a clever way to get rid of the trailing comma I’d be grateful.


<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:param name="targetsubmap">B</xsl:param>
<xsl:key name="kdgroups" match="//device" use="grp"/>

<xsl:template match="/">
<xsl:apply-templates select="//submap[@name=$targetsubmap]" mode="test"/>
</xsl:template>

<xsl:template match="submap" mode="test">
<xsl:text>
Groups for submaps in </xsl:text><xsl:value-of select="@name"/><xsl:text> context.
</xsl:text>
<xsl:apply-templates select="submap" mode="level">
</xsl:apply-templates>
</xsl:template>

<xsl:template match="submap" mode="level">
<xsl:variable name="cursub" select="."/>
<xsl:variable name="totgrps" select="//device[generate-id(.)=generate-id(key('kdgroups',grp))]"/>
<xsl:text>
Submap </xsl:text>
<xsl:value-of select="@name"/>
<xsl:text> - </xsl:text>
<xsl:for-each select="$totgrps">
<xsl:variable name="loopgrp" select="grp"/>
<xsl:for-each select="$cursub">
<xsl:if test="count(descendant::device[grp=$loopgrp]) > 0">
<xsl:value-of select="$loopgrp"/>
<xsl:text>,</xsl:text>
</xsl:if>
</xsl:for-each>
</xsl:for-each>
</xsl:template>

</xsl:stylesheet>

Again, I haven't analyzed the problem in detail, but there seem to be a few things odd about your code. I often find the way to get to the bottom of the problem is to simplify it progressively.

Starting with the template

<xsl:template match="submap" mode="level">
<xsl:variable name="cursub" select="."/>
<xsl:variable name="totgrps" select="//device[generate-id(.)=generate-id(key('kdgroups',grp))]"/>
<xsl:text>
Submap </xsl:text>
<xsl:value-of select="@name"/>
<xsl:text> - </xsl:text>
<xsl:for-each select="$totgrps">
<xsl:variable name="loopgrp" select="grp"/>
<xsl:for-each select="$cursub">
<xsl:if test="count(descendant::device[grp=$loopgrp]) > 0">
<xsl:value-of select="$loopgrp"/>
<xsl:text>,</xsl:text>
</xsl:if>
</xsl:for-each>
</xsl:for-each>
</xsl:template>

(a) the value of $totgrps doesn't depend on the context node (assuming that the stylesheet only has one input document), so it can be pulled out of the template and turned into a global variable. Its value is all the device elements that are the first in their group.

(b) $cursub is a single node, therefore the expression

<xsl:for-each select="$cursub">
<xsl:if test="count(descendant::device[grp=$loopgrp]) > 0">
<xsl:value-of select="$loopgrp"/>
<xsl:text>,</xsl:text>
</xsl:if>
</xsl:for-each>

can be replaced by

<xsl:if test="$cursub/descendant::device[grp=$loopgrp]">
  <xsl:value-of select="$loopgrp"/>
  <xsl:text>,</xsl:text>
</xsl:if>

and this of course means that you don't need the variable $loopgrp, so I think the template reduces to:

<xsl:template match="submap" mode="level">
<xsl:variable name="cursub" select="."/>
<xsl:text>
Submap </xsl:text>
<xsl:value-of select="@name"/>
<xsl:text> - </xsl:text>
<xsl:for-each select="$totgrps">
 <xsl:if test="$cursub/descendant::device[grp=current()/grp]">
  <xsl:value-of select="grp"/>
  <xsl:text>,</xsl:text>
 </xsl:if>
</xsl:for-each>
</xsl:template>

I think the test on position()=last() will then work: it isn't working at the moment because the innermost xsl:for-each is iterating over a single node, so position() is always equal to last().


Michael Kay
http://www.saxonica.com/
Author, XSLT Programmer's Reference and XPath 2.0 Programmer's Reference

Hi Michael,

Thanks again for looking at the problem.

The points you make are right

A $totgrps can become a global variable. I think psychologically because I’m new to XSLT I was stumbling through it and wanted to keep it close.

B I knew $cursub was a single nodeset and looked odd, I was just so ecstatic, I had finally got the answer I forgot to go back to it. The simplified template works as expected.

However the removal of the inner loop structure does not solve the trailing comma problem. As the if statement dictates if the grp is passed to the output tree, the last grp to be passed to output is not necessarily the last member of $totgrps so an if last() clause cannot be used.

The full stylesheet now looks like this

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:param name="targetsubmap">B</xsl:param>
<xsl:key name="kdgroups" match="//device" use="grp"/>
<xsl:variable name="totgrps" select="//device[generate-id(.)=generate-id(key('kdgroups',grp))]"/>

<xsl:template match="/">
<xsl:apply-templates select="//submap[@name=$targetsubmap]" mode="test"/>
</xsl:template>

<xsl:template match="submap" mode="test">
<xsl:text>
Groups for submaps in </xsl:text><xsl:value-of select="@name"/><xsl:text> context.
</xsl:text>
<xsl:apply-templates select="submap" mode="level">
</xsl:apply-templates>
</xsl:template>

<xsl:template match="submap" mode="level">
<xsl:variable name="cursub" select="."/>
<xsl:text>
Submap </xsl:text>
<xsl:value-of select="@name"/>
<xsl:text> - </xsl:text>
<xsl:for-each select="$totgrps">
 <xsl:if test="$cursub/descendant::device[grp=current()/grp]">
  <xsl:value-of select="grp"/>
<xsl:if test="position() != last()">,</xsl:if>
 </xsl:if>
</xsl:for-each>
</xsl:template>


</xsl:stylesheet>

In response to one of your earlier postings in this thread I’m afraid I lean more to the javaphobic side of life. As I feel happier the deadline I was working towards is now achievable, when the book arrives I’ll have a gander at XSLT 2.0 and Saxon. As I do not need to do to much on the java side I’ll probably get away with it as the bulk of the processing is done via the XSLT and parameters passed into it. Recently the language freshest in my head is python. If I need complex java, python has a java compiled variant called jython which can use exposed java classes in a pythonic frame work. That however is an exploration for another day.

Anyway thanks for the help it’s greatly appreciated.

Ray

The position()=last() problem is a bit tricky. The usual solution would be to replace

<xsl:for-each select="X">
  <xsl:if test="Y">
     ...position()...
  </xsl:if>
</xsl:for-each>

by

<xsl:for-each select="X[Y]">
   ... position() ...
</xsl:for-each>

but that can't be done here because of the dependency on current(), which would change its meaning if moved inside the predicate.

However I think it might be possible to do it by juggling the condition a bit, like this:

<xsl:for-each select="$totgrps[grp = $cursub//device/grp]
  <xsl:value-of select="grp"/>
  <xsl:if test="position() != last()">,</xsl:if>
</


Michael Kay
http://www.saxonica.com/
Author, XSLT Programmer's Reference and XPath 2.0 Programmer's Reference

Yep works like a treat.

Thanks again

Final Solution is

<?xml version="1.0"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
<xsl:param name="targetsubmap">B</xsl:param>
<xsl:key name="kdgroups" match="//device" use="grp"/>
<xsl:variable name="totgrps" select="//device[generate-id(.)=generate-id(key('kdgroups',grp))]"/>

<xsl:template match="/">
<xsl:apply-templates select="//submap[@name=$targetsubmap]" mode="test"/>
</xsl:template>

<xsl:template match="submap" mode="test">
<xsl:text>
Groups for submaps in </xsl:text><xsl:value-of select="@name"/><xsl:text> context.
</xsl:text>
<xsl:apply-templates select="submap" mode="level">
</xsl:apply-templates>
</xsl:template>

<xsl:template match="submap" mode="level">
<xsl:variable name="cursub" select="."/>
<xsl:text>
Submap </xsl:text>
<xsl:value-of select="@name"/>
<xsl:text> - </xsl:text>
<xsl:for-each select="$totgrps[grp = $cursub//device/grp]">
  <xsl:value-of select="grp"/>
  <xsl:if test="position() != last()">,</xsl:if>
</xsl:for-each>
</xsl:template>


</xsl:stylesheet>