We help IT Professionals succeed at work.
Get Started

Convert Recursive XSLT to avoid stack overflow (Part 2)

deleyd
deleyd asked
on
69 Views
Last Modified: 2019-12-12
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
Information Architect
CERTIFIED EXPERT
Top Expert 2006
Commented:
This problem has been solved!
Unlock 1 Answer and 1 Comment.
See Answer
Why Experts Exchange?

Experts Exchange always has the answer, or at the least points me in the correct direction! It is like having another employee that is extremely experienced.

Jim Murphy
Programmer at Smart IT Solutions

When asked, what has been your best career decision?

Deciding to stick with EE.

Mohamed Asif
Technical Department Head

Being involved with EE helped me to grow personally and professionally.

Carl Webster
CTP, Sr Infrastructure Consultant
Ask ANY Question

Connect with Certified Experts to gain insight and support on specific technology challenges including:

  • Troubleshooting
  • Research
  • Professional Opinions
Did You Know?

We've partnered with two important charities to provide clean water and computer science education to those who need it most. READ MORE