[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

Re: [xsl] What is the Maximum number of recurssions


Subject: Re: [xsl] What is the Maximum number of recurssions
From: Dimitre Novatchev <dnovatchev@xxxxxxxxx>
Date: Thu, 1 Mar 2012 13:23:03 -0800

On Thu, Mar 1, 2012 at 12:36 PM, Karl Stubsjoen <kstubs@xxxxxxxxx> wrote:
> I'm just curious, what is the maximum number of times a template can
> recurse?

I guess you men the number of nested recursive calls (nestedness).
There is no fixed maximum and in some cases a correctly written
template/function can have nestedness measured in the millions.

Such are the cases with tail-recursive functions/templates -- and this
requires that the XSLT processor can recognize and optimize tail
recursion.

For example, this transformation run with Saxon 6.5.4 successfully
prints all numbers from 1 to one million:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:template match="/">
  <xsl:call-template name="printToN"/>
 </xsl:template>

 <xsl:template name="printToN">
  <xsl:param name="pUpTo" select="1000000"/>
  <xsl:param name="pDoneWith" select="0"/>

  <xsl:if test="$pUpTo > $pDoneWith">
   <xsl:value-of select="$pDoneWith+1"/>
   <xsl:text>&#xA;</xsl:text>

   <xsl:call-template name="printToN">
    <xsl:with-param name="pUpTo" select="$pUpTo"/>
    <xsl:with-param name="pDoneWith" select="$pDoneWith+1"/>
   </xsl:call-template>
  </xsl:if>
 </xsl:template>
</xsl:stylesheet>

However, other XSLT processors (AltovaXML) produce this error: "XSLT
instruction stack overflow"

A DVC (Divide and Conquer) style recursion is also a practical
solution and processing a sequence of N items requires a maximum
nestedness of only log(N). This recursive style is remarkable in that
it doesn't require (as required in the case of tail recursion) any
special abilities from the XSLT processor and works correctly with any
XSLT processor. Thus the maximum callstack depth when processing a
sequence of one million items with DVC-style recursion, is only 19.

> I would imagine it would be different from engine to engine.
> B Is there any other engine intelligence at play here, for example the
> engine has decided that you've written and endless looping recursion,
> instead of one that knows you'll eventually reach the end of your
> source xml?


This is generally impossible to do, because whether or not an
algorithm finishes often depends on the specific data that is fed to
it -- typical examples are many numerical methods that converge only
if the data is limited in a specific interval or by any other
condition.

Cheers,
Dimitre.

>
> Thanks,
> Karl..
>
> --
> Karl Stubsjoen
> MeetScoresOnline.com
> (602) 845-0006
>



--
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
To avoid situations in which you might make mistakes may be the
biggest mistake of all
------------------------------------
Quality means doing it right when no one is looking.
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play
-------------------------------------
Facts do not cease to exist because they are ignored.
-------------------------------------
I finally figured out the only reason to be alive is to enjoy it.


Current Thread
Keywords