troubleshooting Question

Convert Recursive XSLT to avoid stack overflow (Part 2)

Avatar of deleyd
deleydFlag for United States of America asked on
XML
1 Comment1 Solution73 ViewsLast Modified:
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>
This one almost works.
I'm having a problem with the line
<xsl:when test="$nodes[1] = D">
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>
ASKER CERTIFIED SOLUTION
Gertone (Geert Bormans)
Information Architect

Our community of experts have been thoroughly vetted for their expertise and industry experience.

Top Expert 2006

The Distinguished Expert awards are presented to the top veteran and rookie experts to earn the most points in the top 50 topics.

Join our community to see this answer!
Unlock 1 Answer and 1 Comment.
Start Free Trial
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 1 Answer and 1 Comment.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros