In a recent post to the xml-dev mailing list, "XSLT question on transitive closures", Rick Jelliffe wrote:

"Am I right in thinking that

 1) XPath2 functions don't have have a function for transitive closure (along provided xpaths)

2) SAXON 8 does not have the saxon:closure() extension function that older versions of SAXON had

3) The one to use is probably still Christian Nentwich's code from circa 2001 as adopted into EXSLT ?"

Michael Kay replied:

"I think it would be nice to do it properly based on FXSL higher-order functions, which are much more cleanly specified. Perhaps there is already a suitable function in FXSL.

The other thing that's needed is the ability to check for cycles. Simply blowing the stack or looping isn't good enough."

David Carlisle replied by providing a solution that would dynamically generate a new XSLT stylesheet and a closure function in it that uses only a specific function and implements its closure. He also said:

"> I think it would be nice to do it properly based on FXSL higher-order

True (but I'll leave that for Dimitre  :-)"

Thanks to these nice people I felt just like... something had been left for me  :o)

So, now we have in FXSL the function

   f:closure()

which, given a function pFun and a starting set of items pstartSet, produces the transitive closure of pFun.

While the complete 47 lines of code can be viewed using the above link, the essence of the implementation is in the following 20 lines:

 <xsl:function name="f:closure" as="node()*">
    <xsl:param name="pFun" as="element()"/>
    <xsl:param name="pstartSet" as="node()*"/>
    
    <xsl:sequence select="f:closure2($pFun, $pstartSet,$pstartSet)"/>
  </xsl:function>
  
  <xsl:function name="f:closure2" as="node()*">
    <xsl:param name="pFun" as="element()"/>
    <xsl:param name="pCurClosure" as="node()*"/>
    <xsl:param name="pstartSet" as="node()*"/>
    
    <xsl:if test="exists($pstartSet)">
      <xsl:variable name="vNew" select=
          "f:map($pFun,$pstartSet) except $pCurClosure"/>
      <xsl:sequence select=
           "$pstartSet 
           | $vNew 
           | f:closure2($pFun,$pCurClosure | $vNew, $vNew)"/>
    </xsl:if>
  </xsl:function>

And here is my reply to David's post (code hyperlinked, full code omitted):

"
>> I think it would be nice to do it properly based on FXSL higher-order

> > True (but I'll leave that for Dimitre:-)

I am sorry I only read this a few days ago. Below is the code of the FXSL function. While the code is straightforward, the following must be noted:

1. The "set" at present is only a set of nodes. I will probably produce a more general f:closure() function, which operates on any set of items. Then this function should be also passed as parameters a "union" and a "difference" functions.

2. It seems that David's solution would go into an infinite loop for more involved examples (see the second test with reachability of nodes in cyclic graphs below). Therefore, the algorithm was slightly changed and works correctly. The following files can be downloaded from the CVS of the FXSL project:

func-closure.xsl.

testFunc-closure.xsl,

testFunc-closure2.xsl

The last transformation should be applied on the following xml file:
testFunc-closure2.xml

The result from running the second test transformation above (two cases of finding all nodes of a given graph, reachable from a specific node. In the second case there is a cycle involving the nodes V2, V6, V7) is:

 === Reachable from V1 =======

<node id="V1"/>
<node id="V3"/>
<node id="V4"/>
<node id="V5"/>
=======================

=== Reachable from V2 =======
<node id="V2"/>
<node id="V4"/>
<node id="V5"/>
<node id="V6"/>
<node id="V7"/>
=======================

Due to its generality, the f:closure() function is a useful addition to the FXSL library.

Cheers, Dimitre Novatchev
"