RE: 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@xxxxxxxxxx] 
> Sent: 13 July 2007 18:40
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject:  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.