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處理遞歸深度

回答

相關問題