Thursday, December 16, 2010

Recursion in XSLT


I like recursion! It is pure and formal. When you solve problems using recursion you code look cleaner & leaner & meaner! But problem with recursion is that
it is hard to imagine it. You can easily imagine how for loop works, but when you solve complex artificial intelligence algorithms using trees it can get
quite complex and error prone (min-max algorithms for example). I myself like to use recursion only when it might provide substantially more elegant
solution that other methods, and make recursion flow as easy to follow as possible (refactor it to special method,...).

That's all great, but in XSLT (like in any functional language) we are forced to use recursion in situations when we need create functions (templates)
that are not included in XSLT 2.0/1.0 spec. Also using recursion in XSLT is natural way of traversing XML (or any other tree like structured document).

To work with recursion in XSLT, you need to be familiar with couple of things in XSLT. First are off course templates. Templates are analog (or
at least similar) to functions in functional language (Scheme, LISP, F#,...). They have can have parameters and variables. Variables in XSLT are immutable
(they state cannot be changed after first value assignment). For example String object in Java is also immutable. Templates can call itself for recursive calls.
There are no loops in XSLT (don't try to find them). There is xls:forEach but it behave different than loops in imperative language.

Second thing is XPath. XPath is a syntax used to describe parts of XML document. XPath is designed to be used inside an attribute in XML
document. The syntax is a mix of basic programming language expressions and Unix-like path expression.


To show how process XML document using XSLT and recursion we will use example XML document. This document describes F1 2010 season overview for four races.
It shows name of grand Prix (race), data of race, winning driver name, winning team name, no of laps, winning time.

  Fernando Alonso
  Jenson Button
  Sebastian Vettel
  Jenson Button

We will transform this XML document into another document. The customer want to have data within same XML element (tag) put into single XML element
separated by comma. It is maybe strange request, but it is constructed like that to show how recursion is used in XSLT.

Example of transformated XML:

 Bahrain, Australia, Malaysia, China
 14/03/2010, 28/03/2010, 04/04/2010, 18/04/2010
 1:39:20.396, 1:33:36.531, 1:33:48.412, 1:46:42.163


You can download full file from my google code repository. Here I will attach image:

Recursion start at line 34. Here we create template with two parameters. First parameter is sequence (in XPath 2.0) or node-set (in XPath 1.0) of values we are going to traverse and concatenate with delimiter. Second parameter is resulting string that is printed at the end of template (line: 48) (at the end of recursion).
38 check if recursion should stop. It stops if there are no values left (or there was no values at first place) in sequence.
If sequence is not empty, then we go into recursion and call template (line: 40) again with following parameters:
41: Rest of values in sequence (everything after the first item -- position() > 1).
42: Concatenate first value from sequence into resulting string (we only handle first value differently).


No comments:

Post a Comment