代码之家 › 专栏 › 技术社区 › Daniel Cassidy

使用XSLT处理循环依赖项

xslt-1.0 exslt xslt

4

Daniel Cassidy · 技术社区 · 15 年前

i_m处理的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>

如果您使用na_ve实现来处理这个示例,那么您首先要处理一 , 乙或 C ,得到无限递归。

不幸的是,我可以控制输入数据,并且在任何情况下,循环依赖性都是完全有效的,并且被相关规范所允许。

我提出了各种局部解决方案,但在所有情况下都不起作用。

理想的解决方案是防止一个节点被多次处理的一般方法,但我不认为这是可能的。事实上,我怀疑整个问题是不可能解决的。

如果有帮助的话,我有很多可用的exslt(包括函数)。如有必要,我还可以使用任何数量的其他XSLT脚本预处理输入,尽管最好不要对不会在输出中结束的资源进行过多的预处理。

我能做的就是切换到用另一种语言来处理这个问题(至少在没有实质性的重新设计的情况下不会)。我也可以使用XSLT2.0。

有什么想法吗?

2 回复 | 直到 15 年前

1

3

Dimitre Novatchev 15 年前

这是一个简单的解决方案 :

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

主要想法很简单 :维护已访问资源的ID列表,仅当新资源的ID不在列表中时才允许处理该资源。“处理”用于演示目的,并输出包含它所依赖的所有其他请求(递归)的请求。

也注意 每一个 request 只处理一次。

几年前,我为一个图遍历问题提供了一个类似的解决方案——它可以在XML开发人员组档案中找到。-- here . :)

2

user357812 15 年前

只是为了好玩,另一个解决方案(在dimitre之后)是增加一个节点集,其中包含访问的节点。我发布了两个样式表,一个带有节点集逻辑,另一个带有节点集比较,因为对于大型XML输入,必须测试wich更快。

所以,这个样式表:

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