XSLT Recursive Parent/Child Combination

Question

Very interesting Python bounty question which I know can be solved with XSLT 1.0. Please note this is not a duplicate question as previous post centered on Python methods while this is attempting an XSLT solution to the same problem. Below is my attempt but is constrained to a pre-set number of parent/child combinations here being four levels deep and walks through each level conditionally.

Is there a way to generalize my solution for any combination level? I understand this may require tokenizing values with the --> separator. Expected output is current output but need a dynamic solution. I include the Python script to show final end result. To be clear in conflict of interest, I will not use any answer here in above post but do kindly invite you to do so!

XML Input

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<nodes>
    <node name="Car" child="Engine"/>
    <node name="Car" child="Wheel"/>
    <node name="Engine" child="Piston"/>
    <node name="Engine" child="Carb"/>
    <node name="Carb" child="Bolt"/>
    <node name="Spare Wheel"/>
    <node name="Bolt" child="Thread"/>
    <node name="Carb" child="Foat"/>
    <node name="Truck" child="Engine"/>
    <node name="Engine" child="Bolt"/>
    <node name="Wheel" child="Hubcap"/>
</nodes>

XSLT

<xsl:transform xmlns:xsl="http://www.w3.org/1999/XSL/Transform" version="1.0">
<xsl:output version="1.0" encoding="UTF-8" indent="yes" />
<xsl:strip-space elements="*"/>

  <xsl:template match="nodes">
    <data>
      <xsl:apply-templates select="node[not(@name=ancestor::nodes/node/@child)]"/>
    </data>
  </xsl:template>

  <xsl:template match="node">
    <xsl:variable select="@name" name="currname"/>
    <xsl:variable select="@child" name="currchild"/>
    <xsl:variable select="/nodes/node" name="nodeset1"/>
    <xsl:variable select="/nodes/node[@name=$currchild]" name="nodeset2"/>
    <xsl:variable select="/nodes/node[@name=$nodeset2/@child]" name="nodeset3"/>
    <xsl:variable select="/nodes/node[@name=$nodeset3/@child]" name="nodeset4"/>

        <xsl:for-each select="$nodeset2">
          <xsl:variable select="@child" name="nodeset2child"/>

          <xsl:for-each select="$nodeset3">
              <xsl:variable select="@child" name="nodeset3child"/>              
              <xsl:if test="@name=$nodeset2child">

                <xsl:for-each select="$nodeset4">
                  <xsl:if test="@name=$nodeset3child">
                    <xsl:value-of select="$currname"/> --> <xsl:value-of select="$currchild"/> --> <xsl:value-of select="$nodeset2child"/> --> <xsl:value-of select="$nodeset3child"/> --> <xsl:value-of select="@child"/><xsl:text>&#xa;</xsl:text>
                  </xsl:if>                  
                </xsl:for-each>
                <xsl:if test="$nodeset2child!=$nodeset3/@child and $nodeset3child != $nodeset4/@name">                  
                    <xsl:value-of select="$currname"/> --> <xsl:value-of select="$currchild"/> --> <xsl:value-of select="$nodeset2child"/> --> <xsl:value-of select="$nodeset3child"/><xsl:text>&#xa;</xsl:text>
                </xsl:if>

              </xsl:if>              
          </xsl:for-each>

          <xsl:if test="not($nodeset2child=$nodeset3/@child or ancestor::nodes/node[@name=$nodeset2child]/@child)">
              <xsl:value-of select="$currname"/> --> <xsl:value-of select="$currchild"/> --> <xsl:value-of select="$nodeset2child"/><xsl:text>&#xa;</xsl:text>
          </xsl:if>

        </xsl:for-each>
        <xsl:value-of select="@name[not(ancestor::node/@child=$nodeset2/@name)]"/><xsl:text>&#xa;</xsl:text>

  </xsl:template>  
</xsl:transform>

XML Transformed Output

<?xml version='1.0' encoding='UTF-8'?>
<data>Car --&gt; Engine --&gt; Piston
Car --&gt; Engine --&gt; Carb --&gt; Bolt --&gt; Thread
Car --&gt; Engine --&gt; Carb --&gt; Foat
Car --&gt; Engine --&gt; Bolt --&gt; Thread

Car --&gt; Wheel --&gt; Hubcap

Spare Wheel
Truck --&gt; Engine --&gt; Piston
Truck --&gt; Engine --&gt; Carb --&gt; Bolt --&gt; Thread
Truck --&gt; Engine --&gt; Carb --&gt; Foat
Truck --&gt; Engine --&gt; Bolt --&gt; Thread

</data>

Python script (running an xpath on the transformed output root node)

import lxml.etree as ET

# LOAD XML AND XSL DOCS
dom = ET.parse('Input.xml')
xslt = ET.parse('XSLTScript.xsl')

# TRANSFORM XML
transform = ET.XSLT(xslt)
newdom = transform(dom)

# XPATH NEW DOM ROOT NODE (<data>)        
print(newdom.xpath('/data')[0].text.replace("\n\n", "\n"))

# Car --> Engine --> Piston
# Car --> Engine --> Carb --> Bolt --> Thread
# Car --> Engine --> Carb --> Foat
# Car --> Engine --> Bolt --> Thread
# Car --> Wheel --> Hubcap
# Spare Wheel
# Truck --> Engine --> Piston
# Truck --> Engine --> Carb --> Bolt --> Thread
# Truck --> Engine --> Carb --> Foat
# Truck --> Engine --> Bolt --> Thread

Answer 1

And if you want only the leaf nodes

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

<xsl:output method="text"/>
<xsl:strip-space elements="*"/>

<xsl:template match="node">
    <xsl:param name="already" select="''"/>
    <xsl:choose>
    <xsl:when test="$already = '' and not(@child)">
        <!-- no child (sparewheel) -->
        <xsl:value-of select="concat(@name,'&#xa;')"/>
    </xsl:when>
    <xsl:when test="not(../node[@child = current()/@name])">
        <!-- else will already have prefix -->
        <xsl:choose>
            <xsl:when test="../node[@name = current()/@child]">
                <xsl:apply-templates select="../node[@name = current()/@child]">
                    <xsl:with-param name="already">
                        <xsl:value-of select="concat(@name, ' --&gt; ', @child)"/>
                    </xsl:with-param>
                </xsl:apply-templates>
            </xsl:when>
            <xsl:otherwise>
                <xsl:value-of select="concat(@name, ' --&gt; ', @child,'&#xa;')"/>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:when>
    <xsl:when test="$already != ''">
        <!-- called with prefix -->
        <xsl:choose>
            <xsl:when test="../node[@name = current()/@child]">
                <xsl:apply-templates select="../node[@name = current()/@child]">
                    <xsl:with-param name="already">
                        <xsl:value-of select="concat($already, ' --&gt; ', @child)"/>
                    </xsl:with-param>
                </xsl:apply-templates>
            </xsl:when>
            <xsl:otherwise>
                <xsl:value-of select="concat($already, ' --&gt; ', @child,'&#xa;')"/>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:when>
    </xsl:choose>
</xsl:template>

</xsl:transform>

Answer 2

This should do any recursion level but will also output all intermediate steps:

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

<xsl:output method="text"/>
<xsl:strip-space elements="*"/>

<xsl:template match="node">
    <xsl:param name="already" select="''"/>
    <xsl:choose>
    <xsl:when test="$already = '' and not(@child)">
        <!-- no child (sparewheel) -->
        <xsl:value-of select="concat(@name,'&#xa;')"/>
    </xsl:when>
    <xsl:when test="not(../node[@child = current()/@name])">
        <!-- else will already have prefix -->
        <xsl:value-of select="concat(@name, ' --&gt; ', @child,'&#xa;')"/>
        <xsl:apply-templates select="../node[@name = current()/@child]">
            <xsl:with-param name="already">
                <xsl:value-of select="concat(@name, ' --&gt; ', @child)"/>
            </xsl:with-param>
        </xsl:apply-templates>
    </xsl:when>
    <xsl:when test="$already != ''">
        <!-- called with prefix -->
        <xsl:value-of select="concat($already, ' --&gt; ', @child,'&#xa;')"/>
        <xsl:apply-templates select="../node[@name = current()/@child]">
            <xsl:with-param name="already">
                <xsl:value-of select="concat($already, ' --&gt; ', @child)"/>
            </xsl:with-param>
        </xsl:apply-templates>
    </xsl:when>
    </xsl:choose>
</xsl:template>

</xsl:transform>

Ups, had to adjust the output in third case, @name no more necessary as already in the $already...

Answer 3

Here is a much shorter (23-line) and efficient solution

This is also computationally the simplest one -- compare nesting level 1 to nesting level of 3 - 4 ...

This solution is tail-recursive meaning that any good XSLT processor optimizes it with iteration, thus avoiding the possibility of stack-overflow, as the maximum call-stack depth remains constant (1):

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

 <xsl:key name="kNodeByChild" match="node" use="@child"/>
 <xsl:key name="kNodeByName" match="node" use="@name"/>

  <xsl:template match="/*">
    <xsl:apply-templates select="node[not(key('kNodeByChild', @name))]"/>
  </xsl:template>

  <xsl:template match="node[not(key('kNodeByName', @child))]">
    <xsl:param name="pParentPath"/>
    <xsl:value-of select="concat($pParentPath, @name, ' ---> ', @child, '&#xA;')"/>
  </xsl:template>

  <xsl:template match="node">
    <xsl:param name="pParentPath"/>

    <xsl:apply-templates select="key('kNodeByName', @child)">
      <xsl:with-param name="pParentPath" select="concat($pParentPath, @name, ' ---> ')"/>
    </xsl:apply-templates>
  </xsl:template>
</xsl:stylesheet>

When this transformation is applied on the provided XML document:

<nodes>
    <node name="Car" child="Engine"/>
    <node name="Car" child="Wheel"/>
    <node name="Engine" child="Piston"/>
    <node name="Engine" child="Carb"/>
    <node name="Carb" child="Bolt"/>
    <node name="Spare Wheel"/>
    <node name="Bolt" child="Thread"/>
    <node name="Carb" child="Foat"/>
    <node name="Truck" child="Engine"/>
    <node name="Engine" child="Bolt"/>
    <node name="Wheel" child="Hubcap"/>
</nodes>

The wanted, correct result is produced:

Car ---> Engine ---> Piston
Car ---> Engine ---> Carb ---> Bolt ---> Thread
Car ---> Engine ---> Carb ---> Foat
Car ---> Engine ---> Bolt ---> Thread
Car ---> Wheel ---> Hubcap
Spare Wheel ---> 
Truck ---> Engine ---> Piston
Truck ---> Engine ---> Carb ---> Bolt ---> Thread
Truck ---> Engine ---> Carb ---> Foat
Truck ---> Engine ---> Bolt ---> Thread