使用 XSLT 处理循环依赖关系

Question

我正在处理一个 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。

有什么想法吗？

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>

主要思想是simple：维护已访问资源的 id 列表，并且仅当新资源的 id 不存在于列表中时才允许处理新资源。 “处理”用于演示目的，并输出包装所有其他请求（递归地）的请求，它所依赖的。

另请注意，每个请求仅处理一次。

几年前，我为图形遍历问题提供了类似的解决方案 - 可以在 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>

两个输出：（

使用第一个输入）

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