Convert Recursive XSLT to avoid stack overflow (Part 2)

deleyd
deleyd used Ask the Experts™
on
Convert Recursive XSLT to avoid stack overflow (part 2)

Continuing from my previous question "Convert Recursive XSLT to avoid stack overflow"
(see my comment there for why the answer still turned out to have stack overflow problems.)

I have a new test XSLT transform:
<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
    xmlns:msxsl="urn:schemas-microsoft-com:xslt" exclude-result-prefixes="msxsl"
>
    <xsl:strip-space elements="*"/>
    <xsl:output method="text"/>
  
  <!-- 
  E encloses our set of elements
  select="following-sibling::*[1]" gives us the next node in the list
  We call apply-templates passing (@pos + 1) or ($next + @nsize), asking it to process the next node in our E list (select="following-sibling::*[1]")

If the next node is a "D" node,
      1. Output any empty slots not accounted for prior to this D slot, which is at position @pos
      2. Output this D slot
      3. Check if we are at the end of the list, and if we are, output any remaining empty slots not accounted for (from our current position+1 to max)
      
If the next node is a "B" node,
      1. new-next is the next slot after this B node
      2. Output this B node and the slots it covers
      3. Perform the same "check if we are at the end of the list, and if we are, output any remaining empty slots"
  -->

    <xsl:template match="E"><!-- E encloses our set of emelents -->
      <xsl:apply-templates select="." mode="begin"><!-- apply template to the first child element -->
        <xsl:with-param name="next" select="1"/><!-- our slot number. We start at slot #1. -->
        <xsl:with-param name="max" select="@count"/><!-- our total number of slots -->
      </xsl:apply-templates>
    </xsl:template>

  <xsl:template match="E" mode="begin">
    <xsl:param name="max"/>
    <xsl:call-template name="outerloop">
      <xsl:with-param name="nodes" select="*"/>
      <xsl:with-param name="next" select="1"/>
      <xsl:with-param name="max" select="$max"/>
    </xsl:call-template>
  </xsl:template>


  <xsl:template name="outerloop">
    <xsl:param name="nodes"/>
    <xsl:param name="next"/>
    <xsl:param name="max"/>
    <xsl:variable name="return">
      <xsl:call-template name="process2nodes">
        <xsl:with-param name="nodes" select="$nodes[position() &lt; 3]"/>
        <xsl:with-param name="next" select="$next"/>
        <xsl:with-param name="max" select="$max"/>
      </xsl:call-template>
    </xsl:variable>
    <!-- extract $next-so-far from variable "partial-output" -->
    <xsl:variable name="partial-output" select="substring($return, 1, (string-length($return) - 6))"/>
    <xsl:variable name="new-next-str" select="substring($return, (string-length($return) - 5))"/>
    <xsl:variable name="new-next" select="number($new-next-str)" />
    <!-- output what we got so far (minus the appended new-next) -->
    <xsl:value-of select="$partial-output"/>
    <!-- recursively call ourselves -->
    <xsl:variable name="remaining-nodes" select="$nodes[position() >= 3]"/>
    <xsl:if test="($remaining-nodes)">
      <xsl:call-template name="outerloop">
        <xsl:with-param name="nodes" select="$remaining-nodes"/>
        <xsl:with-param name="next" select="$new-next"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>

  
  <xsl:template name="process2nodes">
    <xsl:param name="nodes"/>
    <xsl:param name="next"/>
    <xsl:param name="max"/>
    <xsl:call-template name="ProcessNodes"><!-- apply template to the first child element -->
      <xsl:with-param name="nodes" select="$nodes"/><!-- our slot number. -->
      <xsl:with-param name="next" select="$next"/><!-- our slot number. -->
      <xsl:with-param name="max" select="$max"/><!-- our total number of slots -->
    </xsl:call-template>
  </xsl:template>

  <xsl:template name="ProcessNodes">
    <xsl:param name="nodes"/>
    <xsl:param name="next"/>
    <xsl:param name="max"/>
    <xsl:choose>
      <xsl:when test="not($nodes)">
        <!-- return the $next value to the caller by outputting it as a fixed length 6 charater string. This will be captured and stripped off by the caller. -->
        <xsl:variable name="prepadded_next_num" select="concat('      ', $next)"/>
        <xsl:variable name="next_num_str" select="substring($prepadded_next_num, string-length($prepadded_next_num) - 5)"/>
        <xsl:value-of select="$next_num_str"/>
        <!-- append our fixed length 5 character string representing our next word_num to the output -->
      </xsl:when>
      <xsl:otherwise>
        <xsl:choose>
          <!-- Case: DataWord -->
          <xsl:when test="$nodes[1] = D">
            <xsl:variable name="new-next" select="$next + 1"/>
            <xsl:text>slot </xsl:text>
            <xsl:value-of select="@pos"/>
            <xsl:text> has a D</xsl:text>
            <xsl:text xml:space="preserve">&#10;</xsl:text>
              <xsl:call-template name="ProcessNodes">
                <xsl:with-param name="nodes" select="$nodes[position() != 1]" />
                <xsl:with-param name="next" select="$new-next"/>
              </xsl:call-template>
          </xsl:when>
          <!-- Case: Block -->
          <xsl:when test="$nodes[1] = B">
            <xsl:variable name="new-next" select="$next + @nsize"/>
            <xsl:text>slot </xsl:text>
            <xsl:value-of select="$next"/>
            <xsl:text>-</xsl:text>
            <xsl:value-of select="$new-next - 1"/>
            <xsl:text> are occupied by a B</xsl:text>
            <xsl:text xml:space="preserve">&#10;</xsl:text>
              <xsl:call-template name="ProcessNodes">
                <xsl:with-param name="nodes" select="$nodes[position() != 1]" />
                <xsl:with-param name="next" select="$new-next"/>
              </xsl:call-template>
          </xsl:when>
        </xsl:choose>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>


  <xsl:template match="D">
      <xsl:param name="next"/><!-- our slot number -->
      <xsl:param name="max"/><!-- our total number of slots -->
      
      <xsl:call-template name="add-empty"><!-- first check for any empty slots before this slot. Output for slots n to m, if n <= m -->
        <xsl:with-param name="n" select="$next"/><!-- our slot number -->
        <xsl:with-param name="m" select="@pos - 1"/><!-- previous slot number. D gives us our current slot # as @pos -->
      </xsl:call-template>
      
      <xsl:text>slot </xsl:text>
      <xsl:value-of select="@pos"/>
      <xsl:text> has a D</xsl:text>
      <xsl:text xml:space="preserve">&#10;</xsl:text>
      
      <xsl:variable name="new-next" select="@pos + 1"/><!-- the next slot number -->
      <xsl:call-template name="ProcessNextElementOrEndOfList"><!-- If we are we at the end of the list, fill in next slot if it is empty. (Only adds if we are below or at max) -->
        <xsl:with-param name="new-next" select="$new-next" />
        <xsl:with-param name="max" select="$max" />
      </xsl:call-template>
    </xsl:template>

  
    <xsl:template match="B">
      <xsl:param name="next"/>
      <xsl:param name="max"/>
      
      <xsl:variable name="new-next" select="$next + @nsize"/>
      
      <xsl:text>slot </xsl:text>
      <xsl:value-of select="$next"/>
      <xsl:text>-</xsl:text>
      <xsl:value-of select="$new-next - 1"/>
      <xsl:text> are occupied by a B</xsl:text>
      <xsl:text xml:space="preserve">&#10;</xsl:text>

      <xsl:call-template name="ProcessNextElementOrEndOfList">
        <xsl:with-param name="new-next" select="$new-next" />
        <xsl:with-param name="max" select="$max" />
      </xsl:call-template>
    </xsl:template>

  
  <!-- Fill in empty slots for slots n to m -->
    <xsl:template name="add-empty">
      <xsl:param name="n"/>
      <xsl:param name="m"/>
      <xsl:choose>
        <xsl:when test="$n > $m"></xsl:when>
        <xsl:otherwise>
          <xsl:text>slot </xsl:text>
          <xsl:value-of select="$n"/>
          <xsl:text> is empty</xsl:text>
          <xsl:text xml:space="preserve">&#10;</xsl:text>
          <xsl:call-template name="add-empty">
            <xsl:with-param name="n" select="$n + 1"/>
            <xsl:with-param name="m" select="$m"/>
          </xsl:call-template>
        </xsl:otherwise>
      </xsl:choose>
      <xsl:text> BlankReturn </xsl:text>
      <xsl:value-of select="$n"/>
      <xsl:text xml:space="preserve">&#10;</xsl:text>
    </xsl:template>


  <!-- 
  Check if we are we at the end of the list, and if we are, output any remaining empty slots. (Only adds if we are below or at max) 
  Then process the next element (which there won't be any, if we are at the end of the list)
  -->
  <xsl:template name="ProcessNextElementOrEndOfList">    
    <xsl:param name="new-next"/>
    <xsl:param name="max"/>
    <!-- Check for end of list, and output any remaining empty slots -->
    <xsl:if test="not(following-sibling::*)">
        <xsl:call-template name="add-empty">
          <xsl:with-param name="n" select="$new-next"/>
          <xsl:with-param name="m" select="$max"/>
        </xsl:call-template>
      </xsl:if>
    <!-- Process next element. (There won't be a next element if we are at the end of the list) -->
      <xsl:apply-templates select="following-sibling::*[1]">
        <xsl:with-param name="next" select="$new-next"/>
        <xsl:with-param name="max" select="$max"/>
      </xsl:apply-templates>
    <xsl:text> Return </xsl:text>
    <xsl:value-of select="$new-next"/>
  </xsl:template>

</xsl:stylesheet>

Open in new window

This one almost works.
I'm having a problem with the line
<xsl:when test="$nodes[1] = D">

Open in new window

which is supposed to test to see if the first node in the $nodes list is a <D> node. The test isn't quite right (it's apparently always true no matter what the node is.)

Also, I wondered if there was a way to again get rid of the big "choose" statement in ProcessNodes. (I felt it was nicer not having that.) [The templates at the end, after the ProcessNodes template, are no longer used. Is there a way to get them used again?)

(Again my test input file is:
<?xml version="1.0" encoding="UTF-8"?>
  <E count="17">
    <D pos="1"/>
    <D pos="2"/>
    <D pos="3"/>
    <D pos="5"/>
    <B nsize="5"/>
    <D pos="11"/>
    <B nsize="2"/>
    <B nsize="3"/>
</E>

Open in new window

Comment
Watch Question

Do more with

Expert Office
EXPERT OFFICE® is a registered trademark of EXPERTS EXCHANGE®
Information Architect
Top Expert 2006
Commented:
it might work using 'is' instead of '=' but you don't want to go there

All you elements are empty elements

<xsl:when test="$nodes[1] = D">
(I nodes you have * as the parameter $nodes, so it is element only)
tests the following:
The string value of the first child node is equal to the string value of all the D nodes that are childs of the current context
(whatever that context is is unpredictable because you have all these nested execution of named templates)
All elements are empty and this is XSLT 1, so you are comparing an empty string with a concatenated sequence of empty strings
=> always true

you want to compare the node names
<xsl:when test="local-name($nodes[1]) = 'D'">

or one that I prefer
<xsl:when test="$nodes[1][self::D]">
this one is very XSLT like and no string casting of names

could also work but not tested
<xsl:when test="$nodes[1] is $nodes/self::D[1]">

Do more with

Expert Office
Submit tech questions to Ask the Experts™ at any time to receive solutions, advice, and new ideas from leading industry professionals.

Start 7-Day Free Trial