Handling circular dependencies using XSLT

Question

Im processing the XML file, which is simplified, looks something like this:

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

The XSLT stylesheet should handle the resource you are interested in, which I will call the root resource, and all recursive dependencies. Dependencies are other resources uniquely identified by their id attribute.

It does not matter if the resource is processed twice, although it is preferable to process each required resource only once. It also does not matter in which order the resources are processed.

It is important that the root resource and its recursive dependencies are handled only . We cannot just process and do all the resources.

The naive implementation is this:

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

This implementation is great for the example above, as well as in many cases in the real world. It has the disadvantage that it often processes the same resource more than once, but, as indicated above, this is not very important.

The problem is that sometimes resources have cyclic dependencies:

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

If you use a naive implementation to process this example and start by processing a , b or c , you get infinite recursion.

Unfortunately, I can not control the input data, and in any case, cyclic dependencies are quite permissible and allowed by the corresponding specification.

Ive come up with various partial solutions, but nothing works in all cases.

An ideal solution would be a general approach to prevent node processing more than once, but I don't think this is possible. In fact, I suspect that this problem cannot be solved.

If this helps, I have most of EXSLT (including functions). If necessary, I can also pre-process the input with any number of other XSLT scripts, although it is preferable not to do excessive preprocessing of resources that usually do not end with the output.

What I can do is switch to processing this using another language (at least without a significant reorganization). I also cannot use XSLT 2.0.

Any ideas?

Answer 1

This is a simple solution :

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

When applied to the provided XML document :

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

required, the correct result is obtained :

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

The basic idea is simple . It maintains a list of identifiers of visited resources and only allows processing of a new resource if its identifier is not in the list. "Processing" is intended for demonstration purposes and displays a query that wraps all other queries (recursively) on which it depends.

Also note that each request processed only once.

A few years ago I provided a similar solution to the graph traversal problem - it can be found in the xml-dev group archives - here . :)

Answer 2

Just for fun, another solution (after Dimitre), but increasing the node-set with visited nodes. I am posting two stylesheets, one with node set logic and the other with node set comparison, because you have to check which is faster for large XML inputs.

So this 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: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> 

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

Both outputs:

(first Wiht entry)

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

(with the last entry)

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