Flat to Nested structure based on attribute value using XSLT

Question

I have a flat structured XML file as below:

<rs>
    <r id="r1" lev="0"/>
    <r id="r2" lev="1"/>
    <r id="r3" lev="0"/>
    <r id="r4" lev="1"/>
    <r id="r5" lev="2"/>
    <r id="r6" lev="3"/>
    <r id="r7" lev="0"/>
    <r id="r8" lev="1"/>
    <r id="r9" lev="2"/>
</rs>

which I need to transform to a nested one. Rule is something, all r[number(@lev) gt 0] should be nested within r[number(@lev) eq 0]. And the output would be something like that:

<rs>
    <r id="r1">
        <r id="r2"/>
    </r>
    <r id="r3">
        <r id="r4">
            <r id="r5">
                <r id="r6"/>
            </r>
        </r>
    </r>
    <r id="r7">
        <r id="r8">
            <r id="r9"/>
        </r>
    </r>
</rs>

What I have tried is the following transformation:

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"
    exclude-result-prefixes="xs"
    version="2.0">

    <xsl:output indent="yes"/>

    <xsl:template match="/">
        <rs>
            <xsl:apply-templates select="node()|@*"/>
        </rs>
    </xsl:template>

    <xsl:template match="r">
        <xsl:variable name="lev" select="number(@lev)" as="xs:double"/>
        <r>
            <xsl:copy-of select="@id"/>
            <xsl:apply-templates select="following-sibling::r[not(number(@lev) eq $lev)
                                         and 
                                         count(preceding-sibling::r[number(@lev) eq $lev]) eq 1]"/>
        </r>
    </xsl:template>

</xsl:stylesheet>

But, this does not gives me the desired result. Pointing out my coding error or any other approach to get job done, is greatly appreciated.

Answer 1

This transformation:

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

 <xsl:key name="kRByLevelAndParent" match="r"
  use="concat(generate-id(preceding-sibling::r
                            [not(@lev >= current()/@lev)][1]),
                          @lev
                          )"/>

 <xsl:template match="/*">
  <rs>
    <xsl:apply-templates select="key('kRByLevelAndParent', '0')"/>
  </rs>
 </xsl:template>

 <xsl:template match="r">
  <r id="{@id}">
    <xsl:apply-templates select=
    "key('kRByLevelAndParent',
         concat(generate-id(), @lev+1)
         )"/>
  </r>
 </xsl:template>
</xsl:stylesheet>

when applied on the provided XML document:

<rs>
    <r id="r1" lev="0"/>
    <r id="r2" lev="1"/>
    <r id="r3" lev="0"/>
    <r id="r4" lev="1"/>
    <r id="r5" lev="2"/>
    <r id="r6" lev="3"/>
    <r id="r7" lev="0"/>
    <r id="r8" lev="1"/>
    <r id="r9" lev="2"/>
</rs>

produces the wanted, correct result:

<rs>
   <r id="r1">
      <r id="r2"/>
   </r>
   <r id="r3">
      <r id="r4">
         <r id="r5">
            <r id="r6"/>
         </r>
      </r>
   </r>
   <r id="r7">
      <r id="r8">
         <r id="r9"/>
      </r>
   </r>
</rs>

Explanation:

Positional grouping using a composite key -- for all its "children" an element is the first preceding sibling such that its lev attribute is less than their respective lev attribute.

Answer 2

Dimitre tends to give answers to questions using XSLT 1.0 unless otherwise requested. That may be a correct guess, but I think it's worth pointing out that XSLT 2.0 is now quite widely available and used, and that the code for grouping problems in XSLT 2.0 is much simpler (it may not always be much shorter, but it is much more readable). Unlike Dimitre, I don't have the time or inclination to give beautiful complete and tested solutions to every question, but if you want to see an XSLT 2.0 solution to this problem there is one in a paper I wrote some years ago here:

http://www.saxonica.com/papers/ideadb-1.1/mhk-paper.xml

Search for the recursive template name="process-level".