XSD transform by XSLT: How to reorder entries according to the dependencies

Question

I'm trying to use XSLT to convert XSD scheme (to C++ classes). The problem I currently have is that I'd would like to reorder the complexType entries according to the dependencies. I.e. if a complexType Type1 contains an attribute of complexType Type2, I'd like the Type2 appear before Type1 in the output (for obvious reasons - in C++ header the Type2 cannot be used to declare attribute in Type1 if the Type2 is defined after Type1).

Example input XSD file:

<?xml version="1.0" encoding="utf-8"?>
<xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
  <xs:complexType name="Type1">
    <xs:sequence>
      <xs:element name="id" type="xs:short" />
    </xs:sequence>
  </xs:complexType>
  <xs:complexType name="Type2">
    <xs:sequence>
      <xs:element name="id" type="xs:short" />
      <xs:element name="value" type="Type3" />
    </xs:sequence>
  </xs:complexType>
  <xs:complexType name="Type3">
    <xs:sequence>
      <xs:element name="id" type="xs:short" />
      <xs:element name="value" type="Type4" />
    </xs:sequence>
  </xs:complexType>
  <xs:complexType name="Type4">
    <xs:sequence>
      <xs:element name="id" type="xs:short" />
    </xs:sequence>
  </xs:complexType>
</xs:schema>

What I managed so far is this XSLT (this is a simplified example just generating the type name ordering, not the actual classes):

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
        xmlns:xs="http://www.w3.org/2001/XMLSchema">
    <xsl:output method="text" encoding="utf-8" indent="no"/>

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

    <xsl:template name="gen-type-list">
        <xsl:param name="name"/>
        <xsl:value-of select="concat('[', $name, ']')"/>
    </xsl:template>

    <!--
        Generate the type order according to dependencies

        Dependency should come before the dependent type.
    -->
    <xsl:template name="gen-type-order">
        <xsl:param name="name"/>
        <xsl:param name="typeList"/>
        <xsl:for-each select="xs:attribute | xs:complexContent/xs:extension//xs:attribute | xs:sequence/xs:element | xs:complexContent/xs:extension/xs:sequence/xs:element">
            <xsl:variable name="typeEntry">
                <xsl:value-of select="concat('[', @type, ']')"/>
            </xsl:variable>
            <xsl:if test="contains($typeList, $typeEntry)">
                <xsl:value-of select="$typeEntry"/>
            </xsl:if>
        </xsl:for-each>
        <xsl:value-of select="concat('[', $name, ']')"/>
    </xsl:template>

    <!--
        Print the ordered listing (line by line)
    -->
    <xsl:template name="print-type-order">
        <xsl:param name="typeList"/>
        <xsl:choose>
            <xsl:when test="not(contains($typeList, ']['))">
                <xsl:value-of select="substring-after(substring-before($typeList, ']'), '[')"/>
                <xsl:text>&#x0a;</xsl:text>
            </xsl:when>
            <xsl:otherwise>
                <xsl:value-of select="substring-after(substring-before($typeList, ']'), '[')"/>
                <xsl:text>&#x0a;</xsl:text>
                <xsl:call-template name="print-type-order">
                    <xsl:with-param name="typeList" select="substring-after($typeList, ']')"/>
                </xsl:call-template>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:template>

    <!--
        The main processing template handling the entire document
    -->
    <xsl:template match="/xs:schema">
        <xsl:variable name="typeList">
            <xsl:for-each select="xs:complexType">
                <xsl:call-template name="gen-type-list">
                    <xsl:with-param name="name" select="@name"/>
                </xsl:call-template>
            </xsl:for-each>
        </xsl:variable>
        <xsl:value-of select="$typeList"/>
        <xsl:text>&#x0a;</xsl:text>
        <xsl:variable name="typeOrder">
            <xsl:for-each select="xs:complexType">
                <xsl:call-template name="gen-type-order">
                    <xsl:with-param name="name" select="@name"/>
                    <xsl:with-param name="typeList" select="$typeList"/>
                </xsl:call-template>
            </xsl:for-each>
        </xsl:variable>
        <xsl:call-template name="print-type-order">
            <xsl:with-param name="typeList" select="$typeOrder"/>
        </xsl:call-template>
    </xsl:template>

</xsl:stylesheet>

The output of that run on the example XSD is the following:

[Type1][Type2][Type3][Type4]
Type1
Type3
Type2
Type4
Type3
Type4

The first line is just the simple list of all types (for debugging purposes, and it is used to actually check if the type is a complex type in the gen-type-order template). This is already quite close to what I want, which should be:

Type1
Type4
Type3
Type2

What I struggle with is:

1. How to check if the type is already in the list (to not repeat Type3 as it has been already added as the dependency of type 2)
2. How to call this recursively (so that dependency Type4 will be added before Type3)
3. Is it possible to do that without the initial creation of the complexType list (gen-type-list), i.e. check if a type name is a complexType directly? (I tried initially with something like <xsl:if test="//xs:complexType[name = @type]" but that did not work)
4. Is there an even better / less verbose way to do that? (i.e. process the items in the correct order according to the dependencies)

Indeed the easiest way would be to re-order the XSD itself, unfortunately the XSD is not under my control so it would be difficult to manage that.

Note: I'm aware that there are tools for converting XSD to C++, like Code Synthesis xsdcxx, but I'd prefer to use XSLT, because most of the tools bring dependencies to other libraries like Xerces, which I neither need nor want (besides licensing issues of the tools themselves). And also in the future I'd like to use similar XSLT to convert to different output types (e.g. Thrift message file).

// EDIT

I just managed the point 3) by using the following:

<xsl:template name="gen-type-order">
    <xsl:param name="name"/>
    <xsl:for-each select="xs:attribute | xs:complexContent/xs:extension//xs:attribute | xs:sequence/xs:element | xs:complexContent/xs:extension/xs:sequence/xs:element">
        <xsl:variable name="typeEntry">
            <xsl:value-of select="concat('[', @type, ']')"/>
        </xsl:variable>
        <xsl:variable name="typeName">
            <xsl:value-of select="@type"/>
        </xsl:variable>
        <xsl:if test="//xs:complexType[@name = $typeName]">
            <xsl:value-of select="$typeEntry"/>
        </xsl:if>
    </xsl:for-each>
    <xsl:value-of select="concat('[', $name, ']')"/>
</xsl:template>

But the other points still remain.

Answer 1

In XSLT 2.0, it's not as hard to get things in the right order.

<?xml version="1.0" encoding="UTF-8"?>
<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
  xmlns:xs="http://www.w3.org/2001/XMLSchema">
  <xsl:output method="text" encoding="utf-8" indent="no"/>

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

  <xsl:key name="type" match="xs:complexType" use="@name"/>


  <!-- Returns value 1 if there are no dependencies, 2 if there's 1 etc. -->
  <xsl:template match="*" mode="get-dependency-depth">
    <xsl:param name="depthSummands" as="xs:integer*">
      <xsl:apply-templates mode="get-dependency-depth" 
        select="key('type', (
          xs:attribute | xs:complexContent/xs:extension//xs:attribute | 
          xs:sequence/xs:element | xs:complexContent/xs:extension/xs:sequence/xs:element
        )/@type)"/>
    </xsl:param>
    <xsl:copy-of select="sum($depthSummands) + 1"/>
  </xsl:template>


  <xsl:template match="*" mode="process-types">
    <xsl:value-of select="concat(@name, ' (dependency depth: ')"/>
    <xsl:apply-templates mode="get-dependency-depth" select="."/>
    <xsl:value-of select="')&#10;'"/>
  </xsl:template>


  <xsl:template match="/xs:schema">
    <xsl:apply-templates select="xs:complexType" mode="process-types">
      <xsl:sort data-type="number">
        <xsl:apply-templates mode="get-dependency-depth" select="."/>
      </xsl:sort>
    </xsl:apply-templates>
  </xsl:template>

</xsl:stylesheet>

Output when applied to your input XML:

Type1 (dependency depth: 1)
Type4 (dependency depth: 1)
Type3 (dependency depth: 2)
Type2 (dependency depth: 3)

This does neither test for circular dependencies nor is it particularly efficient for large dependency trees - for those it would be useful to have something like a cache for dependency depths.