Traitement des dépendances cycliques avec XSLT

Question

Je suis traitement d'un fichier XML, simplifié, ressemble à quelque chose comme ceci:

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

La feuille de style XSLT doit traiter une ressource particulière qui nous intéresse, que je vais appeler le root ressources et toutes les dépendances récursives. Les dépendances sont d'autres ressources, identifiés de manière unique par leur attribut id.

Peu importe si une ressource est traitée deux fois, bien qu'il soit préférable de ne traiter que chaque ressource nécessaire une fois. Il n'a pas d'importance quel ordre les ressources sont traitées.

Il est important que uniquement root ressources et ses dépendances récursives sont traitées. Nous ne pouvons pas traiter simplement toutes les ressources et faire avec elle.

Une mise en œuvre naïve se présente comme suit:

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

Cette mise en œuvre fonctionne très bien pour l'exemple ci-dessus, ainsi que dans de nombreux cas dans le monde réel. Il présente l'inconvénient qu'il traite souvent la même ressource plus d'une fois, mais comme indiqué ci-dessus ce n'est pas extrêmement important.

Le problème est que parfois les ressources ont des dépendances cycliques:

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

Si vous utilisez la mise en œuvre naïve pour traiter cet exemple, et vous commencez par le traitement , b ou c , vous obtenez une récursion infinie .

Malheureusement, je ne peux pas contrôler les données d'entrée et dans tous les cas dépendances cycliques sont parfaitement valables et autorisés par le cahier des charges correspondant.

Je suis venu avec diverses solutions partielles, mais rien qui fonctionne dans tous les cas.

La solution idéale serait une approche générale pour empêcher un nœud d'être traité plus d'une fois, mais je ne pense pas que ce soit possible. En fait, je soupçonne que ce problème est impossible à résoudre.

Si elle aide, je la plupart des EXSLT disponibles (y compris les fonctions). Si nécessaire, je peux aussi prétraiter l'entrée avec un nombre quelconque d'autres scripts XSLT, bien qu'il soit préférable de ne pas faire de pré-traitement excessive des ressources qui ne finira pas dans la sortie.

Ce que je ne peux pas faire est de traiter ce commutateur avec une autre langue (du moins pas sans réingénierie importante). Je ne peux pas utiliser XSLT 2.0.

Toutes les idées?

Answer 1

Ceci est une solution simple :

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

Appliqué sur le document XML fourni :

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

le résultat voulu, correct produit :

<resourceProcessing root="a">
   <resource id="a">
      <resource id="b">
         <resource id="c"/>
      </resource>
      <resource id="d"/>
   </resource>
</resourceProcessing>

L'idée principale est simple : Maintenir une liste des ids des ressources visitées et seulement permettre le traitement d'une nouvelle ressource si son identifiant ne figure pas dans la liste. Le « traitement » est à des fins de démonstration et envoie la demande d'emballage toutes les autres demandes (récursive), dont elle dépend.

Notez également que chaque request est traitée qu'une seule fois.

Il y a des années que j'ai fourni une solution similaire à un problème graphique-traversal - il se trouve dans les archives du groupe xml-dev - ici . :)

Answer 2

Juste pour le plaisir, une autre solution (à la suite Dimitre), mais de plus en plus un ensemble de nœuds avec des noeuds visités. Je posterai deux stylesheet, l'une avec la logique de jeu de nœuds et d'autres avec comparaison ensemble de nœuds, parce que vous devez tester Wich est plus rapide pour les grandes entrées XML.

Alors, cette feuille de style:

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

Et cette feuille de style:

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

Les deux sorties:

(première entrée Wiht)

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

(avec entrée précédente)

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