XSLT обработка глубины рекурсии

Question

Прежде всего позвольте мне заявить, что я вообще не имею понятия о XSLT. Передо мной была поставлена ​​задача исследовать некоторые дампы JVM исключения Java OutOfMemory, возникшего во время обработки XSLT.

Я обнаружил, что OutOfMemory произошел во время рекурсивной обработки XSLT (мы используем XALAN).

Что меня поразило, так это то, что рекурсия была> 100 000 вызовов глубиной.

При каких обстоятельствах такая рекурсия может быть настолько глубокой во время обработки XSLT?

---

Обратите внимание, что трассировка стека потоков составляет около 300 тыс. Строк и заполнена вариациями этого до момента появления 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))

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.

Решение :

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 для самого себя, что запускает процесс, который никогда не завершится.