Transforming tree structure from one format into another

An interesting question was asked on xsl-list,

The input XML file is something as:

<Objs>
   <obj name="a" child="b"/>
   <obj name="b" child="c"/>
   <obj name="b" child="d"/>
   <obj name="c" child="e"/>
</Objs>

Let's say that XML file has only one root node.

The output XML file would be:

<Obj name="a">
  <Obj name="b">
      <Obj name="c">
         <Obj name="e"/>
      </Obj>
      <Obj name="d"/>
  </Obj>
</Obj>

A tree structure is defined in input XML, by the 'name' and 'child' attributes. The output represents a true logical tree. We should be able to cater to unlimited number of tree nodes.

We need to write a XSLT stylesheet for this.

At first thought, I imagined that this could be a tough problem. But a little bit of patience helped me to write the stylesheet for this. The solution is presented below.

<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
                version="1.0">

<xsl:output method="xml" indent="yes" />

<xsl:template match="Objs">
  <xsl:variable name="start" select="obj[not(@name = ../obj/@child)]" />
  <xsl:variable name="startName" select="$start[1]/@name" />
  <Obj name="{$startName}">
    <xsl:for-each select="obj[(@name = $startName) and not(../obj/@name = @child)]">
      <Obj name="{@child}" />
    </xsl:for-each>
    <xsl:call-template name="makeTree">
      <xsl:with-param name="list" select="obj[@name = $start/@child]" />
    </xsl:call-template>
  </Obj>
</xsl:template>

<xsl:template name="makeTree">
 <xsl:param name="list" />

 <Obj name="{$list[1]/@name}">
   <xsl:for-each select="$list">
     <xsl:variable name="child" select="@child" />
     <xsl:choose>
       <xsl:when test="not(../obj[@name = $child])">
         <Obj name="{$child}" />
       </xsl:when>
       <xsl:otherwise>
         <xsl:call-template name="makeTree">
           <xsl:with-param name="list" select="../obj[@name = $child]" />
         </xsl:call-template>
       </xsl:otherwise>
     </xsl:choose>
   </xsl:for-each>
 </Obj>
</xsl:template>

</xsl:stylesheet>

At first thought, I felt that XSLT 2.0 constructs will be required to solve this problem. But the problem can be solved completely with a XSLT 1.0 stylesheet.

My belief that XSLT is a wonderful language for processing XML data, became stronger after solving this problem.