tail recursion optimization (was How efficient is DVC?

One thing Robert van Dalen said in his original post was

"Because most XSLT implementations out there still do not support
tail-recursion elimination, DVC is the way to go if you want to process a lot
of nodes."

While DVC is the way to go for large amounts of data (as proven by Dimitre),
it's not accurate that XSLT implementations don't support tail-recursion
elimination. I can't speak for all of them, but many do.

The problem that when the recursive template is a matching template instead of
a named template, it is hard for the processor to recognize that the
apply-templates at the end of the template will result in the same template
being applied. For example, Robert's second example has this:

  <xsl:template match="group">
    <xsl:copy>
      <xsl:copy-of select="@*"/>
      <xsl:copy-of select="./city"/>
    </xsl:copy>
    <xsl:apply-templates select="./group"/>
  </xsl:template>

I don't know if any processors can optimize this. It may seem obvious to you
and me that the apply-templates instruction will result in this same template
being applied, but there might be some other template that also matches
certain 'group' elements at a higher priority, so there's no easy way for the
processor to be sure (before runtime) that this template will be the one that
is invoked for every one of the selected nodes. Or at least, the analysis
required to be certain that this is tail-recursive is not simple enough that
anyone has bothered to figure it out yet. (Suggestions welcome...)

So for now, the way to tell a processor to use its tail recursion optimization
is to use a named template. It's OK to use xsl:if or xsl:choose/xsl:when, as
long as the recursive call is at the end (i.e. nothing else that could generate
output comes after it):

  <xsl:template match="group">
    <xsl:call-template name="process-group"> 
      <xsl:with-param name="group-node" select="."/>
    </xsl:call-template>
  </xsl:template>
  
  <xsl:template name="process-group">
    <xsl:param name="group-node"/>
    <xsl:if test="$group-node">
      <xsl:copy>
        <xsl:copy-of select="$group-node/@*"/>  
        <xsl:copy-of select="$group-node/city"/>
      </xsl:copy>
      <xsl:call-template name="process-group">
        <xsl:with-param name="group-node" select="$group-node/group"/>
      </xsl:call-template>
    </xsl:if>
  </xsl:template>


Mike

-- 
  Mike J. Brown   |  http://skew.org/~mike/resume/
  Denver, CO, USA |  http://skew.org/xml/

 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list