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

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

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

Таблица стилей 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>

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

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

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

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

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

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

Есть идеи?

Источник

2 ответа

Решение

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

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

Источник

Просто для удовольствия, другое решение (после 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>
Источник
Другие вопросы по тегам