Home > Software engineering >  Too many nested function calls in XSLT -- tail recursive?
Too many nested function calls in XSLT -- tail recursive?

Time:12-21

I have a recursive function in my XSLT. It is meant to identify "chains" of elements, where a chain is defined as sequence of elements with start(n 1)=end(n), for example:

<!-- first chain starts here -->
<event start="T0" end="T1">doo</event>
<event start="T1" end="T2">doo</event>
<event start="T2" end="T3">doo</event>
<!-- first chain ends here -->
<event start="T4" end="T5">doo</event>
<event start="T5" end="T6">doo</event>

I am using the following recursive function:

<!-- returns latest event that is connected to the given event through an uninterrupted chain of other events -->
<xsl:function name="exmaralda:last-endpoint-of-segment-chain">
    <xsl:param name="event"/>
    <xsl:choose>
        <xsl:when test="not($event/following-sibling::event) or exmaralda:timeline-position($event/following-sibling::event[1]/@start)&gt;exmaralda:timeline-position($event/@end)">
            <xsl:value-of select="$event/@end"/>
        </xsl:when>
        <xsl:otherwise>
            <xsl:value-of select="exmaralda:last-endpoint-of-segment-chain($event/following-sibling::event[1])"/>
        </xsl:otherwise>
    </xsl:choose>        
</xsl:function>

This works fine as long as sequences of events are not too long (they usually comprise no more than 10 elements). However, if they have a length above a certain value, the transformation throws an error "Too many nested function calls in XSLT". I have read that, in order to avoid this, recursive functions should be made tail-recursive. However, I cannot see why my recursion would not have that property. Can anybody see what might be wrong here?

I am using Saxon 9he as the XSL engine.

CodePudding user response:

The reason your function isn't tail-recursive is that a tail-recursive function must return the result of the recursive call as is, without further processing. Your call requests further processing: the xsl:value-of instruction asks for the result to be converted to a text node.

Saxon can sometimes work out that you didn't really want this conversion, but it can only do that if you declare the type of the function result.

So you should make two improvements to your code, both of which are standard good coding practice: (a) use xsl:sequence rather than xsl:value-of to return function results, and (b) use an as attribute on xsl:function and xsl:param to declare the types of the function parameters and result.

Furthermore, as Martin points out, it's a good idea to use xsl:for-each-group or xsl:iterate rather than recursive functions where it makes sense: it usually makes the code more readable and it's often more efficient.

CodePudding user response:

Assuming XSLT 3 (supported since 9.8) it seems to identify the "chains" you can use group-adjacent:

  <xsl:template match="events">
    <xsl:copy>
      <xsl:for-each-group select="event" composite="yes" group-adjacent="@end => substring-after('T') => xs:integer() - position(), @start => substring-after('T') => xs:integer() - (position()   1)">
        <chain>
          <xsl:sequence select="current-group()"/>
        </chain>
      </xsl:for-each-group>
    </xsl:copy>
  </xsl:template>

https://xsltfiddle.liberty-development.net/nbspVax

A more general and precise declarative grouping implementation might be possible in XSLT using break-when, currently supported by SaxonCS and hopefully soon by Saxon 11:

  <xsl:template match="events">
    <xsl:copy>
      <xsl:for-each-group select="event" break-when="$next/@start => substring-after('T') => xs:integer() gt $group[last()]/@end => substring-after('T') => xs:integer()">
        <chain>
          <xsl:sequence select="current-group()"/>
        </chain>
      </xsl:for-each-group>
    </xsl:copy>
  </xsl:template>
  • Related