XSLT 处理递归深度

Question

首先我要声明我对 XSLT 一无所知。我接到的任务是调查 XSLT 处理期间发生的 Java OutOfMemory 异常的一些 JVM 转储。

我发现在递归 XSLT 处理期间发生了 OutOfMemory（我们使用 XALAN）。

令我震惊的是，递归调用深度超过 100 000 次。

在什么情况下，XSLT 处理过程中如此深度的递归是可以接受的？

---

请注意，线程堆栈跟踪大约有 300k 行长，并充满了这种情况的变体，直到发生 OutOfMemory：

at org/apache/xalan/transformer/TransformerImpl.executeChildTemplates(Bytecode PC:150(Compiled Code)) 在 org/apache/xalan/templates/ElemElement.execute(Bytecode PC:352(编译代码)) 在 org/apache/xalan/transformer/TransformerImpl.executeChildTemplates(字节码 PC:150(编译代码))

Answer 1

当使用原始递归处理很长的序列时，可能会发生这种情况。

想象一下使用递归命名模板实现 sum() 函数：

<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="sum">
   <xsl:with-param name="pSeq" select="/*/*"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template name="sum">
  <xsl:param name="pAccum" select="0"/>
  <xsl:param name="pSeq"/>

  <xsl:choose>
   <xsl:when test="not($pSeq)">
     <xsl:value-of select="$pAccum"/>
   </xsl:when>
   <xsl:otherwise>
    <xsl:call-template name="sum">
     <xsl:with-param name="pAccum"
          select="$pAccum+$pSeq[1]"/>
     <xsl:with-param name="pSeq"
          select="$pSeq[position() >1]"/>
    </xsl:call-template>
   </xsl:otherwise>
  </xsl:choose>
 </xsl:template>
</xsl:stylesheet>

当应用于以下 XML 文档时：

<nums>
  <num>01</num>
  <num>02</num>
  <num>03</num>
  <num>04</num>
  <num>05</num>
  <num>06</num>
  <num>07</num>
  <num>08</num>
  <num>09</num>
  <num>10</num>
</nums>

结果是：

55

现在，想象一下nums 有 1000000 (1M) num 个子级。这将是求一百万个数字之和的合法尝试，但是大多数 XSLT 处理器通常会在递归深度为 1000 或大约 1000 时崩溃。

解决方案：

1. 使用尾递归 （一种特殊的递归，其中递归调用是模板中的最后一条指令）。一些 XSLT 处理器识别尾递归并在内部对其进行优化以进行迭代，因此没有递归，也没有堆栈溢出。

2. 使用 DVC 式递归（分而治之）。这适用于所有 XSLT 处理器。最大递归深度为 log2(N)，对于大多数实际用途来说是可行的。例如，处理 1M 项的序列只需要 19 的堆栈深度。

以下是求和模板的 DVC 实现：

<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="sum">
   <xsl:with-param name="pSeq" select="/*/*"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template name="sum">
  <xsl:param name="pSeq"/>

  <xsl:variable name="vCnt" select="count($pSeq)"/>

  <xsl:choose>
   <xsl:when test="$vCnt = 0">
     <xsl:value-of select="0"/>
   </xsl:when>
   <xsl:when test="$vCnt = 1">
     <xsl:value-of select="$pSeq[1]"/>
   </xsl:when>
   <xsl:otherwise>
    <xsl:variable name="vHalf" select=
     "floor($vCnt div 2)"/>

    <xsl:variable name="vSum1">
     <xsl:call-template name="sum">
      <xsl:with-param name="pSeq" select=
      "$pSeq[not(position() > $vHalf)]"/>
     </xsl:call-template>
    </xsl:variable>

    <xsl:variable name="vSum2">
     <xsl:call-template name="sum">
      <xsl:with-param name="pSeq" select=
      "$pSeq[position() > $vHalf]"/>
     </xsl:call-template>
    </xsl:variable>

    <xsl:value-of select="$vSum1+$vSum2"/>
   </xsl:otherwise>
  </xsl:choose>
 </xsl:template>
</xsl:stylesheet>

使用此模板求一百万个数字的总和需要一些时间，但会产生正确的结果而不会崩溃。

Answer 2

这很可能是 XSLT 中的错误导致无限递归（其中“无限”定义为“直到内存耗尽”）。考虑以下模板：

<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:template match="/">
        <xsl:apply-templates select="/"/>
    </xsl:template>
</xsl:stylesheet>

文档中唯一的 template 与根元素匹配，然后对自身调用 apply-templates，这将启动一个永远不会终止的进程。