XSLT处理递归深度

Question

XSLT处理递归深度

javaxsltrecursionxalan

3

首先，让我声明我完全不懂XSLT。我被分配了一个任务来调查在XSLT处理期间发生的Java OutOfMemory异常的一些JVM dump。

我发现OutOfMemory是发生在递归XSLT处理过程中（我们使用XALAN）。

令人震惊的是，该递归深度超过了100,000次调用。

在什么情况下，在XSLT处理期间进行这样深的递归才是可接受的呢？

请注意，线程堆栈跟踪大约有300k行，并且与此变体充斥着，直到OutOfMemory发生为止：

at org/apache/xalan/transformer/TransformerImpl.executeChildTemplates(Bytecode PC:150(Compiled Code)) at org/apache/xalan/templates/ElemElement.execute(Bytecode PC:352(Compiled Code)) at org/apache/xalan/transformer/TransformerImpl.executeChildTemplates(Bytecode PC:150(Compiled Code))

- finrod

4

可以编写一个会导致无限递归的转换模板。你能发布你的模板吗？ - dfb

3

这就是为什么它被称为“堆栈溢出”…… - user357812

好问题，+1。请查看我的答案，了解递归处理中堆栈溢出的原因和两种解决方案的详细说明。 - Dimitre Novatchev

2个回答

0

这很可能是 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>

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

- Wayne

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dimitre Novatchev · Accepted Answer

这可能发生在使用原始递归处理非常长的序列时。

想象一下使用递归命名模板实现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>

结果是:

现在，想象一下nums有1000000（1M）个num子节点。这是一个合理的尝试去求解一百万个数字的总和，然而大多数 XSLT 运行器通常在递归深度达到或接近 1000 时就会崩溃。

解决方法：

使用尾递归（一种特殊的递归方式，其中递归调用是模板中的最后一条指令）。一些 XSLT 处理器识别尾递归并在内部将其优化为迭代，因此不存在递归和堆栈溢出问题。
使用 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>

使用此模板求解一百万个数字的总和需要花费一定时间，但是能够在不崩溃的情况下得出正确的结果。