RE: [xsl] XSLT 1.0 Stack Overflow Question

If your XSLT processor optimizes tail calls, you can make this
tail-recursive by changing it so that instead of comparing length(head) with
max-length(tail), you pass longest-so-far as a parameter on the recursive
call, and output its value when you get to the end. That way the result of
the recursive call doesn't need to be further processed by the caller, which
is what makes it a tail call.

Michael Kay
http://www.saxonica.com/

-----Original Message-----
From: Roger L. Cauvin [mailto:roger(_at_)cauvin(_dot_)org] 
Sent: 13 July 2007 18:40
To: xsl-list(_at_)lists(_dot_)mulberrytech(_dot_)com
Subject: [xsl] XSLT 1.0 Stack Overflow Question

I'm parsing raw text (not XML or a node-set) that contains a 
long list of items separated by linefeeds.  Let's say it's a 
list of action items:

  Action Items
  1. Ensure all tests pass.
  2. Get sign-off on documentation from Amy.
  3. Create a new page on web site for product.
  4. Move product from staging area to production.
  .
  .
  .
  205. Send press release announcing release.

What I want to do is find the item with the greatest number 
of characters in it.  So I have a recursive template:

  <xsl:template name="get-longest-item">
    <xsl:param name="items"/>
    <xsl:variable name="index">
      <xsl:value-of select="substring-before(substring-after($items,
'&#10;'), '.')"/>
    </xsl:variable>
    <xsl:choose>
      <xsl:when test="$index = ''">
        <xsl:text disable-output-escaping="yes">-1%-1</xsl:text>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="item">
          <xsl:value-of 
select="substring-before(substring-after($items, '.
'), '&#10;')"/>
        </xsl:variable>
        <xsl:variable name="length" select="string-length($item)"/>
        <xsl:variable name="longest-of-rest">
          <xsl:call-template name="get-longest-item">
            <xsl:with-param name="items" 
select="substring-after($items, '&#10;')" />
          </xsl:call-template>
        </xsl:variable>
        <xsl:choose>
          <xsl:when test="$length &gt; 
substring-after($longest-of-rest, '%')">
            <xsl:value-of select="concat($index, '%', $length)" />
          </xsl:when>
          <xsl:otherwise>
            <xsl:value-of select="$longest-of-rest" />
          </xsl:otherwise>
        </xsl:choose>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

The template "returns" the index of the longest item, 
followed by the percent symbol, followed by the length of that item.

For a large list of action items, applying this template 
results in a stack overflow.  A binary divide-and-conquer 
approach would make much more efficient use of stack space, 
but I can't figure out how to do it using XSLT 1.0.  I try to 
cut the text into two halves, but doing so inevitably seems 
to involve order N recursion.

--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: 
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--



--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--