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

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

4 голосов
/ 04 августа 2010

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

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

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

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

Важно, чтобы only ресурс 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.

Есть идеи?

Ответы [ 2 ]

3 голосов
/ 04 августа 2010

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

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

2 голосов
/ 04 августа 2010

Просто для удовольствия, другое решение (после Димитра), но увеличение набора узлов с посещенными узлами.Я публикую две таблицы стилей, одну с логикой набора узлов, а другую со сравнением наборов узлов, потому что вы должны проверить, что быстрее для больших 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>
...