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

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

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

Таблица стилей XSLT должна обрабатывать конкретный интересующий нас ресурс, который я буду называть корневым ресурсом, и все рекурсивные зависимости. Зависимости — это другие ресурсы, однозначно идентифицируемые своим атрибутом id.

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

Важно, чтобы обрабатывались только ресурс root и его рекурсивные зависимости. Мы не можем просто обработать все ресурсы и покончить с этим.

Наивная реализация выглядит следующим образом:

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

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

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

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

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

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

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

Есть идеи?


xslt xslt-1.0 exslt
person Daniel Cassidy    schedule 03.08.2010    source источник
comment
+1 за очень хорошо написанный вопрос. Удачи в поиске решения в XSLT 1.0. Если вы не получили ответа здесь, вы можете попробовать XSL-LIST на mulberrytech.com/ xsl/xsl-список   -  person Jim Garrison    schedule 04.08.2010
comment
Хороший вопрос (+1). Смотрите мой ответ для полного и простого решения. :)   -  person Dimitre Novatchev    schedule 04.08.2010
comment
@Jim-Garrison: Похоже, Дэниелу повезло :)   -  person Dimitre Novatchev    schedule 04.08.2010

Ответы (2)


arrow_upward
3
arrow_downward

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

<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 — здесь. :)

person Dimitre Novatchev    schedule 04.08.2010
comment
Великолепно! Спасибо. Как только я задал XSLT-вопрос, у меня было ощущение, что вы ответите на него :). Судя по всему, должно быть возможно поддерживать список посещенных ресурсов в виде набора узлов, а не строки, что может быть немного понятнее. Спасибо, что указали мне правильное направление. - person Daniel Cassidy; 04.08.2010
comment
@Daniel-Cassidy: я не рекомендую сохранять узлы в переменной pVisited, потому что повторное копирование каждый раз, когда необходимо добавить новый узел, намного медленнее, чем простое объединение строки. В XPath 2.0 XSLT-процессор может оптимизировать либо предварительную обработку, либо добавление к последовательности (например, Saxon оптимизирует добавление), и это можно использовать для улучшения этого алгоритма с O (N ^ 2) до O (N). - person Dimitre Novatchev; 04.08.2010
comment
Справедливо. Кстати, ваше решение не гарантирует, что каждый resource обрабатывается только один раз, например, в случае, когда a зависит от b и c, а b зависит от c. В этом случае c обрабатывается дважды. Однако, как я уже сказал, для меня это не проблема; ваше решение должно предотвращать циклы, и это все, что требуется. - person Daniel Cassidy; 04.08.2010
comment
@Daniel-Cassidy: я могу заставить решение обрабатывать каждый ресурс только один раз - для этого я изменю преобразование, чтобы использовать обход узла за узлом, где инструкция <xsl:apply-templates> всегда применяется только к одному (следующему) узлу. - person Dimitre Novatchev; 04.08.2010
comment
Вы правы конечно. Я упомянул об этом только из-за строки в конце вашего ответа, в которой говорилось: «Также обратите внимание, что каждый request [вы имели в виду resource?] обрабатывается только один раз». - person Daniel Cassidy; 04.08.2010

arrow_upward
2
arrow_downward

Просто для удовольствия, другое решение (после 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>

Оба выхода:

(с первым вводом)

<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>
person Community    schedule 04.08.2010