XSLT处理递归深度

首先我要指出，我没有XSLT的线索可言。我获得了一项任务，以调查在XSLT处理期间发生的Java OutOfMemory异常的一些JVM转储。XSLT处理递归深度

我发现，内存溢出的递归XSLT处理（我们使用XALAN）过程中发生。

我发现令人震惊的是，递归> 100万个电话深。

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

注意，线程堆栈跟踪约30万线长，充满直到内存不足发生的那一刻起的这种变化：

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))

来源

2011-03-25 finrod

可以创建导致无限递归的转换。你可以发布你的模板？ – dfb 2011-03-25 17:21:20

这就是为什么这被称为stackoverflow ... – 2011-03-25 22:39:34

好问题，+1。请参阅我的答案，以详细解释递归处理引起堆栈覆盖的原因以及解决问题的两种解决方案。 – 2011-03-26 17:44:41

处理与原始递归很长的序列时，就会出现这种情况。

试想实施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左右

解决方案：

使用tail-递归（递归调用是模板中最后一条指令的一种特殊递归）。一些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>

使用该模板找到百万数字的总和需要一些时间，但会产生正确的结果没有崩溃。

来源

2011-03-26 17:43:15

+1，这就是我一直在寻找的。导致深度递归的合法处理。再一次，没有任何XSLT经验：你会说如果开始触击StackOverflow异常，是时候研究和优化模板了吗？（而不是把-Xss增加到一个可笑的巨大数字（比如700megs）来解决它们） – finrod 2011-03-27 00:36:42

问过一些奇怪的问题，然后无法跟进和验证自己是如此。 – finrod 2011-03-27 09:40:44

这是最有可能的一个bug在导致无限递归的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，这将启动一个过程，永远不会终止。

来源

2011-03-25 17:36:18

XSLT处理递归深度

回答

相关问题