Обработка циклических зависимостей с XSLT

Question

Я обработаю файл XML, который, упрощенный, выглядит что-то подобное:

<resources>
  <resource id="a">
    <dependency idref="b"/>
    <!-- some other stuff -->
  </resource>
  <resource id="b">
    <!-- some other stuff -->
  </resource>
</resources>

Styleshe лист XSLT должен обрабатывать конкретный ресурс, который мы заинтересованы в том, что я позвоню корень Ресурс и все рекурсивные зависимости. Зависимости являются другими ресурсами, уникальными идентифицированными их id атрибут.

Неважно, если ресурс обрабатывается дважды, хотя предпочтительно обрабатывать каждый необходимый ресурс только один раз. Это также не имеет значения, какой заказ обрабатывается ресурсы.

Важно, чтобы Только то корень Ресурс и его рекурсивные зависимости обрабатываются. Мы не можем просто обрабатывать все ресурсы и делать с ним.

Наизывая реализация заключается в следующем:

<xsl:key name="resource-id" match="resource" use="@id"/>

<xsl:template match="resource">
  <!-- do whatever is required to process the resource. -->

  <!-- then handle any dependencies -->
  <xsl:apply-templates select="key('resource-id', dependency/@idref)"/>
</xsl:template>

Эта реализация работает нормально для примера выше, а также во многих случаях реального мира. У него есть недостаток, который часто обрабатывает один и тот же ресурс более одного раза, но, как указано выше, это не очень важно.

Проблема в том, что иногда ресурсы имеют циклические зависимости:

<resources>
  <resource id="a">
    <dependency idref="b"/>
    <dependency idref="d"/>
  </resource>
  <resource id="b">
    <dependency idref="c"/>
  </resource>
  <resource id="c">
    <dependency idref="a"/>
  </resource>
  <resource id="d"/>
</resources>

Если вы используете наивную реализацию для обработки этого примера, и вы начинаете при обработке а., преступность или слияние, Вы получаете бесконечную рекурсию.

К сожалению, я не могу контролировать входные данные, и в любом случае циклические зависимости совершенно действительны и допускаются соответствующими спецификацией.

Я придумал различные частичные решения, но ничего не работает во всех случаях.

Идеальное решение было бы общим подходом для предотвращения обработки узла более одного раза, но я не думаю, что это возможно. На самом деле, я подозреваю, что вся эта проблема невозможно решить.

Если это поможет, у меня больше всего есть Exslt (включая функции). При необходимости я также могу предварительно обработать вход с любым количеством других сценариев XSLT, хотя предпочтительно не делать чрезмерную предварительную обработку ресурсов, которые не заканчиваются на выходе.

То, что я не могу сделать, это переключиться на обработку этого с другим языком (по крайней мере, не без существенной реинжингистики). Я также не могу использовать XSLT 2.0.

Есть идеи?

Answer 1

Это простое решение:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
 <xsl:output omit-xml-declaration="yes" indent="yes"/>

 <xsl:param name="pRootResourceId" select="'a'"/>

 <xsl:key name="kResById" match="resource" use="@id"/>

 <xsl:template match="/">
  <resourceProcessing root="{$pRootResourceId}">
    <xsl:apply-templates select=
    "key('kResById', $pRootResourceId)"/>
  </resourceProcessing>
 </xsl:template>

 <xsl:template match="resource">
  <xsl:param name="pVisited" select="'|'"/>

  <xsl:copy>
    <xsl:copy-of select="@*"/>

    <xsl:apply-templates select=
      "key('kResById',
           dependency/@idref
                [not(contains($pVisited, concat('|', ., '|')))])">
      <xsl:with-param name="pVisited"
       select="concat($pVisited, @id, '|')"/>
    </xsl:apply-templates>
  </xsl:copy>
 </xsl:template>
</xsl:stylesheet>

При применении на прилагаемом документе XML:

<resources>
  <resource id="a">
    <dependency idref="b"/>
    <dependency idref="d"/>
  </resource>
  <resource id="b">
    <dependency idref="c"/>
  </resource>
  <resource id="c">
    <dependency idref="a"/>
  </resource>
  <resource id="d"/>
</resources>

Требуется, правильный результат производится:

<resourceProcessing root="a">
   <resource id="a">
      <resource id="b">
         <resource id="c"/>
      </resource>
      <resource id="d"/>
   </resource>
</resourceProcessing>

Основная идея проста: Поддерживайте список идентификаторов посещенных ресурсов и разрешают обработку нового ресурса, если его идентификатор не присутствует в списке. «Обработка» предназначена для демонстрационных целей и выводит запрос, оборучающую все другие запросы (рекурсивно), на которых он зависит.

Также примечание что каждый request обрабатывается только один раз.

Годы назад я предоставил аналогичное решение проблеме обхода графов - его можно найти в архивах группы XML-DEV - здесь. :)

Answer 2

Просто для удовольствия, другое решение (следующее Dimitre), но увеличение узла, установленного с посещенными узлами. Я публикую две таблицы стилей, один с логикой узела, установленного и другим с сравнением установленного узла, потому что вы должны проверить, как быстрее для больших входов XML.

Итак, этот стильют:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:output omit-xml-declaration="yes" indent="yes"/>
    <xsl:param name="pRootResourceId" select="'a'"/>
    <xsl:key name="kResById" match="resource" use="@id"/>
    <xsl:template match="/" name="resource">
        <xsl:param name="pVisited" select="key('kResById', $pRootResourceId)"/>
        <xsl:param name="pNew" select="key('kResById',$pVisited/dependency/@idref)"/>
        <xsl:choose>
            <xsl:when test="$pNew">
                <xsl:call-template name="resource">
                    <xsl:with-param name="pVisited" select="$pVisited|$pNew"/>
                    <xsl:with-param name="pNew" select="key('kResById',
           $pNew/dependency/@idref)[not(@id=($pVisited|$pNew)/@id)]"/>
                </xsl:call-template>
            </xsl:when>
            <xsl:otherwise>
                <result>
                    <xsl:copy-of select="$pVisited"/>
                </result>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:template>
</xsl:stylesheet>

И эта таблица стилей:

<xsl:stylesheet version="1.0"
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:output omit-xml-declaration="yes" indent="yes"/>
    <xsl:param name="pRootResourceId" select="'a'"/>
    <xsl:key name="kResById" match="resource" use="@id"/>
    <xsl:template match="/" name="resource">
        <xsl:param name="pVisited" select="key('kResById', $pRootResourceId)"/>
        <xsl:param name="pNew" select="key('kResById', $pVisited/dependency/@idref)"/>
        <xsl:variable name="vAll" select="$pVisited|$pNew"/>
        <xsl:choose>
            <xsl:when test="$pNew">
                <xsl:call-template name="resource">
                    <xsl:with-param name="pVisited" select="$vAll"/>
                    <xsl:with-param name="pNew" select="key('kResById',
           $pNew/dependency/@idref)[count(.|$vAll)>count($vAll)]"/>
                </xsl:call-template>
            </xsl:when>
            <xsl:otherwise>
                <result>
                    <xsl:copy-of select="$pVisited"/>
                </result>
            </xsl:otherwise>
        </xsl:choose>
    </xsl:template>
</xsl:stylesheet>

Оба выхода:

(WIHT первый вход)

<result>
    <resource id="a">
        <dependency idref="b" />
        <!-- some other stuff -->
    </resource>
    <resource id="b">
        <!-- some other stuff -->
    </resource>
</result>

(С последним входом)

<result>
    <resource id="a">
        <dependency idref="b" />
        <dependency idref="d" />
    </resource>
    <resource id="b">
        <dependency idref="c" />
    </resource>
    <resource id="c">
        <dependency idref="a" />
    </resource>
    <resource id="d" />
</result>