xsl-list
[Top] [All Lists]

Re: [xsl] Complex recursion in XSLT 1.0

2008-02-27 10:21:11
As Florent, I am also at a loss figuring out what exactly problem is described.

In case it has something to do with traversing graphs, as later
replies hint, then probably this early 2004 work can be helpful: on
finding all paths connecting two nodes in a graph:

   http://lists.xml.org/archives/xml-dev/200401/msg00444.html

The above is a pure XSLT 1.0 solution.

In case one needs to find the set of all nodes in a graph, reachable
from a specific given node, then the FXSL function

    f:closure()

can be used.

It is described on my blog:

   http://dnovatchev.spaces.live.com/Blog/cns!44B0A32C2CCF7488!384.entry

and the source code can be found on the CVS of FXSL:

    
http://fxsl.cvs.sourceforge.net/fxsl/fxsl-xslt2/f/func-closure.xsl?revision=1.1&view=markup&sortby=date


Needless to say, this function is quite simple and the important code
actually occupies 14 lines (15 - 28):

    1 <xsl:stylesheet version="2.0"
    2  xmlns:xsl="http://www.w3.org/1999/XSL/Transform";
    3  xmlns:f="http://fxsl.sf.net/";
    4  exclude-result-prefixes="f"
    5 >
    6   <xsl:import href="func-map.xsl"/>
    7
    8   <xsl:function name="f:closure" as="node()*">
    9           <xsl:param name="pFun" as="element()"/>
   10           <xsl:param name="pstartSet" as="node()*"/>
   11
   12           <xsl:sequence select="f:closure2($pFun, 
$pstartSet,$pstartSet)"/>
   13   </xsl:function>
   14
   15   <xsl:function name="f:closure2" as="node()*">
   16           <xsl:param name="pFun" as="element()"/>
   17           <xsl:param name="pCurClosure" as="node()*"/>
   18           <xsl:param name="pstartSet" as="node()*"/>
   19
   20           <xsl:if test="exists($pstartSet)">
   21                   <xsl:variable name="vNew" select=
   22                 "f:map($pFun,$pstartSet) except $pCurClosure"/>
   23                   <xsl:sequence select=
   24                  "$pstartSet
   25                  | $vNew
   26                  | f:closure2($pFun,$pCurClosure | $vNew, $vNew)"/>
   27           </xsl:if>
   28   </xsl:function>
   29
   30   <xsl:function name="f:closure" as="node()">
   31           <xsl:param name="pFun" as="element()"/>
   32
   33           <xsl:sequence select="f:curry(f:closure(), 2, $pFun)"/>
   34   </xsl:function>
   35
   36   <xsl:function name="f:closure" as="element()">
   37           <f:closure/>
   38   </xsl:function>
   39
   40   <xsl:template match="f:closure" mode="f:FXSL"
   41    as="node()*">
   42           <xsl:param name="arg1" as="element()"/>
   43           <xsl:param name="arg2" as="node()*"/>
   44
   45           <xsl:sequence select="f:closure($arg1,$arg2)"/>
   46   </xsl:template>
   47 </xsl:stylesheet>




-- 
Cheers,
Dimitre Novatchev
---------------------------------------
Truly great madness cannot be achieved without significant intelligence.
---------------------------------------
To invent, you need a good imagination and a pile of junk
-------------------------------------
Never fight an inanimate object
-------------------------------------
You've achieved success in your field when you don't know whether what
you're doing is work or play



On Mon, Feb 18, 2008 at 2:17 AM, Marroc 
<marrocdanderfluff(_at_)yahoo(_dot_)co(_dot_)in> wrote:
Hi all,

I haven't written to the list with this one up until now because I doubted
my ability to describe it adequately for you. But now I'm really stuck and I
feel like it is down to the inadequacies of XSLT 1.0 so I wanted to find out
if I'm right or wrong.

Basically, I've tried every approach I can think of but each time I find
that XSLT 1.0 lacks any kind of 'memory' of what it has done. I can't find a
way of passing parameters back up the tree to effectively say 'done this
one' or stop processing these sub-nodes now.

The scenario is that, I have a set of xhtml files that together describe a
table of contents (toc) with different branches expanded. I only ever know
the name of the first one, that is, 'toc.htm'. From toc.htm, I can read the
second level of toc in files with names similar to 'toc41837.htm'. Inside
these are further topic and toc filenames, potentially up to 5 or 6 levels
deep but I'm only dealing with 3 levels at the moment. From these files, I
need to create a mapping file of the form:

<mappings>
       <relationship topic="123.htm" toc="toc.htm" />
       <relationship topic="456.htm" toc="toc41837.htm" />
</mappings>

This is then used by the next xsl to relate topics to toc's in all
hyperlinks so that they can remain synchronised when a page is generated
server-side by asp.net.

So, I started by attempting a recursive a template that uses several
repeated 'mode' templates level1, level2 through levela (to give 10).

<xsl:template match="/">
       <xsl:variable "container"
               <xsl:call-template name="toc_load"
                       <xsl:with-param name="toc_name">toc.htm</
               </
       </
<!-- sort and output to output document -->
</xsl:template>

<xsl:template "load_toc" open first document and process links
       <apply-templates select="a"
               <xsl:with-param "toc_name"

<xsl:template process links to topics (a @href not starting with 'toc')
       <xsl:with-param "toc_name"
       < create mapping using current @href and current toc_name

<xsl:template process links to other toc's
       <xsl:with param "toc_name"
               but don't process same toc again
               <xsl:call-template "load_toc2"
                       <xsl:with-param name="toc_name" select="toc_name" />
                       <xsl:with-param name="toc_name2" select="@href" />

<!-- Level2 -->

<xsl:template "load_toc2"
       same again with mode="level2" and param toc_name and toc_name2

<xsl:template process links to topics (a @href not starting with 'toc')
mode="level2"

<xsl:template process links to other toc's
       <params toc_name and toc_name2
       <call toc_load3

<!-- Level3 -->

etc. to Levela passing params for all previously opened tocs


Now the problem was that each toc mentions all the earlier tocs and all the
later tocs as follows:

               <a href="toc.htm" target="TOC"><img src="minus.gif" /></a><a
href="1598.htm">Topic abc</a><br/>
expanding-->    <a href="toc15974.htm"><img src="plus.gif" /></a><a
href="1601.htm">Topic def</a><br/>
topic-->        <a href="1604.htm">Topic hij</a><br/>
               <a href="toc159710.htm" target="TOC"><img
src="plus.gif"/></a><a href="1599.htm">Topic klm</a><br/>
               <a href="toc159717.htm" target="TOC"><img
src="plus.gif"/></a><a href="1600.htm">Topic nop</a><br/>

So, once Levela is finished, the transform works it's way up to finish off
the stack of templates it has completed. But, it has now forgotten that it
processed that Levela template and so it is called again where it is found.

I need a way to either give the transform an overall memory of what it has
already processed, or, stop processing subsequent nodes once the first toc
file has been called from within a branch.

I hope someone can suggest some sensible ideas on this one because I've
tried everytning I can find and still can't get this particular recursion to
work!

Richard


--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: 
<mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--



--~------------------------------------------------------------------
XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list
To unsubscribe, go to: http://lists.mulberrytech.com/xsl-list/
or e-mail: <mailto:xsl-list-unsubscribe(_at_)lists(_dot_)mulberrytech(_dot_)com>
--~--

<Prev in Thread] Current Thread [Next in Thread>