RE: [xsl] Complex recursion in XSLT 1.0

["Marroc" <marrocdanderfluff@xxxxxxxxxxx>]

Thanks Michael,

those are useful suggestions. The second approach is one that I've pondered
but I think it ends in the same infinite loop when I try to trace all the
paths. In fact, the second solution would need to use the first to find all
paths.

>(b) a stack containing the next node to be visited at each level; the
recursion terminates when this stack becomes empty.

Could you elucidate a little on the concept of a 'stack'. I can only dream
of such a thing. What mechanism would you use? and... does that not sound
like we need to have a list of all entries first - is that another infinite
loop?

All these Catch 22's are piling up and I'm starting to think that this is
fundamentally impossible in XSLT 1.0 because we are not party to essential
information about what went before. If only we could see what is in the
result tree at any given moment we might have a chance.

Richard

-----Original Message-----
From: Michael Kay [mailto:mike@xxxxxxxxxxxx] 
Sent: 18 February 2008 11:02
To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
Subject: RE: [xsl] Complex recursion in XSLT 1.0

Yes, this is quite a tricky one: the conventional recursive algorithms for
traversing graphs are written in a procedural style that involves keeping a
list of the nodes that have already been visited (or marking them as
visited, which amounts to the same thing).

The key to the solution is the idea of "sibling recursion" - only here, it's
not siblings at the XML level that you are concerned with, but siblings in
the topic graph. Specifically, suppose a topic A contains references to
topics X, Y, and Z. Now the way that you process Z depends on the way that X
and Y were processed, which means you can't process X, Y, and Z
independently (which is what will happen if you use xsl:for-each or
xsl:apply-templates to iterate over them). Instead you need to call
something that processes X, which in turn calls something that processes Y,
which in turn calls something that processes Z. That way, the
processing-of-X can pass a parameter to the processing-of-Y, such as the
list of topics already visited.

And then of course you need to do this through multiple levels so it's not
really sibling recursion but descendant recursion, so that if X has
sub-topics P, Q, and R, then it's the processing of R that invokes the
processing of Y. This means that the parameters you pass on each step must
include (a) the set of nodes already visited, and 

This is do-able but it's not easy. Here's a sketch of another approach:

I'm not clear if you need to detect cycles. If you know that the input is an
acyclic graph and the requirement is to visit each node once, then you might
like to build a list of all paths, and then eliminate duplicate paths to the
same node by using grouping (which is easier of course in XSLT 2.0). Then in
the next phase of processing you only follow the paths that were not
eliminated.

Michael Kay
http://www.saxonica.com/


> -----Original Message-----
> From: Marroc [mailto:marrocdanderfluff@xxxxxxxxxxx]
> Sent: 18 February 2008 10:18
> To: xsl-list@xxxxxxxxxxxxxxxxxxxxxx
> Subject: [xsl] Complex recursion in XSLT 1.0
> 
> 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