xsl:apply-templates

The <xsl:apply-templates> instruction defines a set of nodes to be processed , and causes the system to process them by selecting an appropriate template rule for each one.

Changes in 2.0

The mode attribute may now take the value «#current » to continue processing in the current mode.

Built-in template rules now pass parameters through unchanged.

Format

 <xsl:apply-templates     select? = expression     mode? = token>     <!-- Content: (xsl:sort  xsl:with-param)* -->   </xsl:apply-templates>

Position

<xsl:apply-templates> is an instruction, and is always used within a sequence constructor.

Attributes

Name	Value	Meaning
Select optional	Expression	The sequence of nodes to be processed. If omitted, all children of the current node are processed
Mode optional	QName or «#current »	The processing mode. Template rules used to process the selected nodes must have a matching mode. If omitted, the default (unnamed) mode is used. The value «#current » indicates that the current mode should be used

Name

Value

Meaning

Select

optional

Expression

The sequence of nodes to be processed. If omitted, all children of the current node are processed

Mode

optional

QName or «#current »

The processing mode. Template rules used to process the selected nodes must have a matching mode. If omitted, the default (unnamed) mode is used. The value «#current » indicates that the current mode should be used

The constructs Expression and QName are defined at the beginning of this chapter and more formally in Chapter 5 of XPath 2.0 Programmer's Reference .

Content

Zero or more <xsl:sort> elements.

Zero or more <xsl:with-param> elements.

Effect

The <xsl:apply-templates> element selects a sequence of nodes in the input tree, and processes each of them individually by finding a matching template rule for that node. The sequence of nodes is determined by the select attribute; the order in which they are processed is determined by the <xsl:sort> elements (if present), and the parameters passed to the template rules are determined by the <xsl:with-param> elements (if present). The behavior is explained in detail in the following sections.

The Select Attribute

If the select attribute is present, the expression defines the nodes that will be processed. This must be an XPath expression that returns a sequence of (zero or more) nodes. For example <xsl:apply-templates select="*"/> selects the set of all element nodes that are children of the current node. Writing <xsl:apply-templates select="@width+3"/> would cause a type error, because the value of the expression is a number, not a sequence of nodes.

The expression may select nodes relative to the context node (the node currently being processed), as in the example above. Alternatively it may make an absolute selection from the root node (for example <xsl:apply-templates select="//item"/> ), or it may simply select the nodes by reference to a variable initialized earlier (for example <xsl:apply-templates select="$sales-figures"/> ).

If the select attribute is omitted, the nodes processed will be the children of the context node: that is, the elements, text nodes, comments, and processing instructions that occur directly within the context node. It's then an error if the context item isn't a node. Text nodes that consist only of whitespace will be processed along with the others, unless they have been stripped from the tree; for details, see <xsl: strip-space > on page 432. In the XPath tree model (described in Chapter 2) attribute nodes and namespace nodes are not regarded as children of the containing element, so they are not processed: If you want to process attribute nodes, you must include an explicit select attribute, for example <xsl:apply-templates select="@*"/> . However, it is more usual to get the attribute values directly using the <xsl:value-of> instruction, described on page 465.

Omitting the select attribute has exactly the same effect as specifying the expression «child::node() » . This selects all the nodes (elements, text nodes, comments, and processing instructions) that are children of the context node. If the context node is anything other than a root node or an element node, then it has no children, so <xsl:apply-templates/> does nothing, because there are no nodes to process.

For each node in the selected sequence, in turn , one template rule is selected and the sequence constructor contained in its body is evaluated. In general there may be a different template rule for each selected node. Within this sequence constructor, this node becomes the new context node, so it can be referred to using the XPath expression «. » .

The called template can also determine the relative position of this node within the list of nodes selected for processing: Specifically , it can use the position() function to give the position of that node in the list of nodes being processed (the first node processed has position() = 1 , and soon), and the last() function to give the number of nodes in the list being processed. These two functions are described in detail in Chapter 10 of XPath 2.0 Programmer's Reference . They enable the called template to output sequence numbers for the nodes as they are processed, or to take different action for the first and the last nodes, or perhaps to use different background colors for odd-numbered and even-numbered nodes.

Sorting

If there are no child <xsl:sort> instructions, the selected items are processed in the order of the sequence produced by evaluating the select expression. If the select expression is a path expression, the nodes will be in document order. In the normal case where the nodes all come from the same input document this means they will be processed in the order they are encountered in the original source document: for example, an element node is processed before its children. Attribute nodes belonging to the same element, however, may be processed in any order, because the order of attributes in XML is not considered significant. If there are nodes from several different documents in the sequence, which can happen when you use the document() function (described in Chapter 7, page 532), the relative order of nodes from different documents is not defined, though it is consistent if the same set of nodes is processed more than once.

The direction of the axis used to select the nodes is irrelevant. (The direction of different axes is described in Chapter 7 of XPath 2.0 Programmer's Reference.) For example, «select=" preceding -sibling::*" » will process the preceding siblings of the current node in document order (starting with the first sibling) even though the preceding-sibling axis is in reverse document order. The axis direction affects only the meaning of any positional qualifiers used within the select expression. For example, «select="preceding-sibling::*[1]" » will select the first preceding sibling element in the direction of the axis, which is the element immediately before the current node, if there is one.

Although most XPath expressions return nodes in document order, not all do so. For example, the expression «title, author, publisher » returns a sequence containing first the child title elements, then the child author elements, and then the child publisher elements of the context node, regardless of the order that these nodes appear in the source document. The nodes returned by the XPath expression will be processed in the order of the sequence that is returned, not necessarily in document order.

If there are one or more <xsl:sort> instructions as children of the <xsl:apply-templates> instruction, the nodes are sorted before processing. Each <xsl:sort> instruction defines one sort key. For details of how sorting is controlled, see <xsl:sort> on page 423. If there are several sort keys defined, they apply in major-to-minor order. For example if the first <xsl:sort> defines sorting by country and the second by state, then the nodes will be processed in order of state within country. If two nodes have equal sort keys (or if the same node is included more than once in the sequence), they will be processed in the order that they appeared in the original result of the select expression.

Choosing a Template Rule

For each node to be processed, a template rule is selected. The choice of a template rule is made independently for each selected node; they may all be processed by the same template rule, or a different template rule may be chosen for each one.

The template rule selected for processing a node will always be either an <xsl:template> element with a match attribute, or a built-in template rule provided by the XSLT processor.

An <xsl:template> element will be used to process a node only if it has a matching mode: That is, the mode attribute of the <xsl:apply-templates> element must match the mode attribute of the <xsl:template> element. An <xsl:template> element can define a list of modes that it matches, or it can specify «#all » to indicate that it matches all modes. If the <xsl:template> element has no mode attribute, or if its mode attribute includes the keyword «#default » , then the template rule matches the default mode, which is the mode that is used when <xsl:apply-templates> has no mode attribute. If the <xsl:apply-templates> instruction does have a mode attribute, then the value of the attribute must be a name that matches one of the names listed in the mode attribute of the <xsl:template> element. If the mode name contains a namespace prefix, it is the namespace URI that must match, not necessarily the prefix itself. Alternatively, the <xsl:apply-templates> instruction can specify «mode="#current" » to continue processing in the current mode. This is useful when the instruction is contained in a template rule that can be invoked in a number of different modes. The concept of the current mode is explained more fully in the section for <xsl: apply-imports > .

Note that if the mode attribute is omitted, it makes no difference what mode was originally used to select the template rule containing the <xsl:apply-templates> instruction. The mode is not sticky; it reverts to the default mode as soon as <xsl:apply-templates> is used with no mode attribute. If you want to continue processing in the current mode, either specify the mode explicitly, or set «mode="#current" » .

An <xsl:template> element will be used to process a node only if the node matches the pattern defined in the match attribute of the <xsl:template> element.

If there is more than one <xsl:template> element that matches a selected node, one of them is selected based on its import precedence and priority, as detailed under <xsl:template> on page 450.

If there is no <xsl:template> element that matches a selected node, a built-in template rule is used. The action of the built-in template rule depends on the kind of node, as follows :

Node Kind	Action of Bullt-In Template Rule
Document node Element node	Call apply-templates to process each child of the selected node, using the mode specified on the call to <xsl:apply-templates> . This is done as if the contents of the template were <xsl:apply-templates mode="#current"/>. The parameters passed in the call of <xsl:apply-templates> are passed transparently through the built-in template to the template rules for the child elements
Text node Attribute node	Copy the string value of the node to the result sequence, as a text node. This is done as if the contents of the template were <xsl:value-of select="string (.)">
Comment node Processing Instruction Namespace node	No action

Node Kind

Action of Bullt-In Template Rule

Document node Element node

Call apply-templates to process each child of the selected node, using the mode specified on the call to <xsl:apply-templates> . This is done as if the contents of the template were

 <xsl:apply-templates mode="#current"/>.

The parameters passed in the call of <xsl:apply-templates> are passed transparently through the built-in template to the template rules for the child elements

Text node Attribute node

Copy the string value of the node to the result sequence, as a text node. This is done as if the contents of the template were

 <xsl:value-of select="string (.)">

Comment node Processing Instruction Namespace node

No action

For the document node and for element nodes, the built-in template rule processes the children of the selected node in document order, matching each one against the available template rules as if the template body contained an explicit <xsl:apply-templates> element with no select attribute. Unlike the situation with explicit template rules, the mode is sticky; it is carried through automatically to the template rules that are called. So if you execute <xsl:apply-templates mode="m"/> for an element that has no matching template rule, the built-in template rule will execute <xsl:apply-templates mode="m"/> for each of its children. This process can, of course, recurse to process the grandchildren, and so on.

In XSLT 2.0, the built-in template rules not only pass on the mode they were called with, they also pass on their parameters. This is a change from XSLT 1.0.

Parameters

If there are any <xsl:with-param> elements present as children of the <xsl:apply-templates> element, they define parameters that are made available to the called template rules. The same parameters are made available to each template rule that is evaluated, even though different template rules may be invoked to process different nodes in the list.

Each <xsl:with-param> element is evaluated in the same way as an <xsl:variable> element. Specifically:

if it has a select attribute, it is evaluated as an XPath expression.
if there is no select attribute and the <xsl:with-param> element is empty, the value is a zero-length string, unless there is an as attribute, in which case it is an empty sequence.
otherwise , the value of the parameter is determined by evaluating the sequence constructor contained within the <xsl:with-param> element. If there is an as attribute, this sequence forms the value of the parameter; if not, a temporary tree is constructed from this sequence, and the document node at the root of the temporary tree is passed as the value of the parameter. Tree-valued variables are described under <xsl:variable> on page 471.

If the <xsl:with-param> element has an as attribute, then the value of the parameter must match the type specified in this attribute, and if necessary the value is converted to this type using the standard conversion rules described on page 476. In theory it is possible for a parameter value to be converted twice, first to the type defined on the <xsl:with-param> element, and then to the type defined on the corresponding <xsl:param> element.

It is not defined whether the parameter is evaluated once only, or whether it is evaluated repeatedly, once for each node in the sequence. If the value isn't needed (for example, because the select expression selected no nodes, or because none of the nodes match a template that uses this parameter) then it isn't defined whether the parameter is evaluated at all. Usually this doesn't matter, because evaluating the parameter repeatedly will have exactly the same effect each time. But it's something to watch out for if the parameter is evaluated by calling an external function that has a side effect, such as reading the next record from a database.

If the name of a child <xsl:with-param> element matches the name of an <xsl:param> element in the selected template rule, then the value of the <xsl:with-param> element is assigned to the relevant <xsl:param> variable name.

If there is a child <xsl:with-param> element that does not match the name of any <xsl:param> element in the selected template rule, then it is ignored. This is not treated as an error.

If there is an <xsl:param> element in the selected template rule with no matching <xsl:with-param> element in the <xsl:apply-templates> element, then the parameter is given a default value: see <xsl:param> on page 392 for details. This is an error only if the <xsl:param> element specifies «required="yes" » .

If the selected template rule is a built-in rule, then any parameters that are supplied are passed on to any template rules called by the built-in rule, in the same way that the mode is passed on. This is a change from XSLT 1.0. For example, consider:

  <xsl:template match="section">   <ol>   <xsl:apply-templates>   <xsl:with-param name="in-section" select="true()"/>   </xsl:apply-templates>   </ol>   </xsl:template>   <xsl:template match="clause">   <xsl:param name="in-section" select="false()"/>   ...   </xsl:template>

When a <clause> is contained directly within a <section> , the parameter $in-section will of course take the value «true » as expected. If there is an intervening element, with no explicit template rule, so that the <clause> is the grandchild of the <section> element, the <clause> template rule will still be invoked, and the parameter $in-section will still have the value «true » . The reason is that the built-in template rule for the intermediate element calls <xsl:apply-templates> to process its <clause> children, supplying all the parameters that were supplied when it itself was invoked.

Result

The result of evaluating the <xsl:apply-templates> instruction is an arbitrary sequence, which may include both nodes and atomic values. This sequence is formed by concatenating the sequences produced by each of the template rules that is invoked. These sequences are concatenated in the order of the selected nodes (after any sorting), so that if the selected nodes after sorting were (A, B, C), and the template rule for node A generates the sequence T(A), then the final result sequence is (T(A), T(B), T(C)).

This doesn't mean that the XSLT processor has to process the nodes sequentially. It can process them in any order it likes, or in parallel, so long as it assembles the results in the right order at the end.

Usually, <xsl:apply-templates> is used to produce a sequence of nodes that become siblings in the result tree. This is what happens when <xsl:apply-templates> , or any other instruction, is used in the sequence constructor within an element such as an <xsl:element> instruction or a literal result element. But <xsl:apply-templates> is not confined to such uses. For example, the following code (which is written to take an XSLT stylesheet as input) uses <xsl:apply-templates> to decide which version of XSLT the current element belongs to:

  <xsl:template match="*">   <xsl:variable name="version" as="xs:decimal">   <xsl:apply-templates select="." mode="get-version"/>   </xsl:variable>   <xsl:if test="version='2.0'>   ...   </xsl:if>   </xsl:template>   <xsl:template mode="get-version" as="xs:decimal"   match="xsl:analyze-string  xsl:for-each-group   xsl:character-map  xsl:next-match    ...    ">   <xsl:sequence select="2.0"/>   </xsl:template>   <xsl:template mode="get-version" as="xs:decimal" match="*">   <xsl:sequence select="1.0"/>   </xsl:template>

In this example, the result returned by <xsl:apply-templates> is a single decimal number.

Note that it's quite legitimate to use <xsl:apply-templates> within the body of a global variable definition, for example:

  <xsl:variable name="table-of-contents">   <xsl:apply-templates mode="toc"/>   </xsl:variable>

In this situation the context node is taken as the root of the principal source document, so the <xsl:apply-templates> processes the children of the root node. If the transformation is invoked without supplying a principal source document, this causes a runtime error. There will also be an error reported if a template rule that is invoked attempts to access the value of the global variable: This kind of error is referred to in the specification as a circularity.

Usage and Examples

First, some simple examples are given below:

Construct	Effect
<xsl:apply-templates/>	Processes all the children of the context node
<xsl:apply-templates select="para"/>	Processes all the <para> elements that are children of the context node
<xsl:apply-templates select="//*" mode="toc"/>	Processes every element in the document in mode «toc »
<xsl:apply-templates select="para"> <xsl:with-param name="indent" select="$n+4"/> </xsl:apply-templates>	Process all the <para> elements that are children of the context node, setting the value of the indent parameter in each called template to the value of the variable $n plus 4
<xsl:apply-templates select="//book"> <xsl:sort select="@isbn"/> </xsl:apply-templates>	Process all the <book> elements in the document, sorting them in ascending order of their isbn attribute

The following sections give some hints and tips about using <xsl:apply-templates> . First I'll discuss when to use <xsl:apply-templates> and when to use <xsl:for-each> . Then I'll explain how to use modes.

<xsl:apply-templates> versus <xsl:for-each>

<xsl:apply-templates> is most useful when processing an element that may contain children of a variety of different types in an unpredictable sequence. This is a rule-based design pattern: the body of each individual template rule declares which nodes it is interested in, rather than the template rule for the parent node defining in detail how each of its children should be processed. The rule-based approach works particularly well when the document design is likely to evolve over time. As new child elements are added, template rules to process them can also be added, without changing the logic for the parent elements in which they might appear.

This style of processing is sometimes called push processing. It will be familiar if you have used text processing languages such as awk or Perl, but it may be unfamiliar if you are more used to procedural programming in C++ or Visual Basic.

Where the structure is more regular and predictable, it may be simpler to navigate around the document using <xsl:for-each> , or by accessing the required data directly using <xsl:value-of> . This is sometimes called pull processing. The <xsl-value-of> instruction allows you to fetch data from the XML document using an arbitrarily complex XPath expression. In this sense it is similar to a SELECT statement in SQL.

A unique strength of XSLT is the ability to mix these two styles of programming. I'll discuss both approaches, and their relative merits, in more detail in Chapter 9.

Modes

Modes are useful where the same data is to be processed more than once.

A classic example is when building a table of contents. The main body of the output can be produced by processing the nodes in default mode, while the table of contents is produced by processing the same nodes with «mode="TOC" » .

The following example does something very similar to this: it displays a scene from a play, adding at the start of the page a list of the characters who appear in this scene:

Using Modes

This example uses a mode to create a list of characters appearing in a scene of a play.

Source

The source file, scene.xml , contains a scene from a play (specifically, Act I Scene 1 of Shakespeare's Othello - marked up in XML by Jon Bosak).

It starts like this:

  <?xml version="1.0"?>   <SCENE><TITLE>SCENE I. Venice. A street.</TITLE>   <STAGEDIR>Enter RODERIGO and IAGO</STAGEDIR>   <SPEECH>   <SPSAKER>RODERIGO</SPEAKER>   <LINE>Tush! never tell me; I take it much unkindly</LINE>   <LINE>That thou, Iago, who hast had my purse</LINE>   <LINE>As if the strings we're thine, shouldst know of this.</LINE>   </SPEECH>   <SPEECH>   <SPEAKER>IAGO</SPEAKER>   <LINE>'Sblood, but you will not hear me:</LINE>   <LINE>If ever I did dream of such a matter, Abhor me.</LINE>   </SPEECH>     etc.     </SCENE>

Stylesheet

The stylesheet scene.xsl is designed to display this scene in HTML. This is how it starts:

  <xsl:transform   xmlns:xsl="http://www.w3.org/1999/XSL/Tranaform"   version="2.0">   <xsl:template match="SCENE">   <html><body>   <xsl:apply-templates select="TITLE"/>   <xsl:variable name=    "    speakers" as="element()*">   <xsl:for-each-group select="//SPEAKER" group-by=".">   <xsl:sequence select="current-group()[1]"/>   </xsl:for-each-group>   </xsl:variable>   <h2>Cast:  <xsl:apply-templates select="$speakers"   modes="cast-list"/></h2>   <xsl:apply-templates select="* except TITLE"/>   </body></html>   </xsl:template>

The template rule shown above matches the <SCENE> element. It first displays the <TITLE> element (if there is one) using the appropriate template rule. Then it sets up a variable called «speakers » to be a sequence containing all the distinct <SPEAKER> elements that appear in the document. This is constructed by grouping all the <SPEAKER> elements using the <xsl:for-each-group> instruction, and then taking the first one in each group. The result is a list of the speakers in which each one appears once only.

The template rule then calls <xsl:apply-templates> to process this set of speakers in mode «cast-list » (a nice side effect is that they will be listed in order of appearance). Finally it calls <xsl:apply-templates> again, this time in the default mode, to process all elements ( «* » ) except <TITLE> elements (because the title has already been processed).

The stylesheet carries on as follows:

  <xsl:template match="SPEAKER" mode="cast-list">   <xsl:value-of select="."/>   <xsl:if test="not(position()=last())">, </xsl:if>   </xsl:template>

This template rule defines how the <SPEAKER> element should be processed when it is being processed in «cast-list » mode. The sequence constructor has the effect of outputting the speaker's name, followed by a comma if it is not the last speaker in the list.

Finally the remaining template rules define how each element should be output, when processed in default mode:

  <xsl:template match="TITLE">   <h1><xsl:apply-templates/></h1>   </xsl:template>   <xsl:template match="STAGEDIR">   <i><xsl:apply-templates/></i>   </xsl:template>   <xsl:template match="SPEECH">   <p><xsl:apply-templates/></p>   </xsl:template>   <xsl:template match="SPEAKER">   <b><xsl:apply-templates/></b><br/>   </xsl:template>   <xsl:template match="LINE">   <xsl:apply-templates/><br/>   </xsl:template>   </xsl:transform>

Output

The precise layout of the HTML depends on which XSLT processor you are using, but apart from layout details it should start like this:

  <html>   <body>   <h1>SCENE I. Venice. A street.</h1>   <h2>Cast: RODERIGO, IAGO, BRABANTIO</h2>   <i>Enter RODERIGO and IAGO</i>   <p>   <b>RODERIGO</b><br>   Tush! never tell me; I take it much unkindly<br>   That thou, Iago, who hast had my purse<br>   As if the strings were thine, shouldst know of this.<br>   </p>   <p>   <b>IAGO</b><br>   'Sblood, but you will not hear me:<br>   If ever I did dream of such a matter, Abhor me.<br>   </p>   ...   </body>   </html>

It is sometimes useful to use named modes, even where they are not strictly necessary, to document more clearly the relationship between calling templates and called templates, and to constrain the selection of template rules rather more visibly than can be achieved by relying on template rule priorities. This might even improve performance by reducing the number of rules to be considered, though the effect is likely to be marginal.

For example, suppose that a <poem> consists of a number of <stanza> elements, and that the first <stanza> is to be output using a different style from the rest. The orthodox way to achieve this would be as follows:

  <xsl:template match="poem">   ...   <xsl:apply-templates select="stanza"/>   ...   </xsl:template>   <xsl:template match="stanza[1]">   ...   </xsl:template>   <xsl:template match="stanza">   ...   </xsl:template>

This relies on the default priority rules to ensure that the correct template rule is applied to each stanza-as explained in Chapter 6, the default priority for the pattern «stanza[1] » is higher than the default priority for «stanza » .

Another way of doing this, perhaps less orthodox but equally effective, is as follows:

  <xsl:template match="poem">   ...   <xsl:apply-templates select="stanza[1]" mode="first"/>   <xsl:apply-templates select="stanza[position()>1]"mode="rest"/>   ...   </xsl:template>   <xsl:template match="stanza" mode="first">   ...   </xsl:template>   <xsl:template match="stanza" mode="rest">   ...   </xsl:template>

Another solution, giving even finer control, would be to use <xsl:for-each> and <xsl:call-template> to control precisely which template rules are applied to which nodes, avoiding the pattern-matching mechanisms of <xsl:apply-templates> altogether.

Which you choose is largely a matter of personal style, and it is very hard to argue that one is better than the other in all cases. However, if you find that the match patterns used in defining a template rule are becoming extremely complex and context dependent, then you probably have both a performance and a maintenance problem on your hands, and controlling the selection of template rules in the calling code, by using modes or by calling templates by name, may well be the answer.

Simulating Higher Order Functions

In functional programming languages, a very useful programming technique is to write a function that accepts another function as an argument. This is known as a higher order function. For example, you might write a function that does a depth-first traversal of a tree, and processes each node in the tree using a function that is supplied as an argument. This makes it possible to use one tree-walking routine to achieve many different effects.

In XSLT (and XPath), functions are not first-class objects, so they cannot be passed as arguments to other functions. The same is true of templates. However, the template-matching capability of <xsl:apply-templates> can be used to simulate higher order functions.

This use of <xsl:apply-templates> has been developed to a fine art by Dimitre Novatchev in his FXSL library ( http://fxsl. sourceforge .net/ ), which provides many examples of the technique.

A simple example of a higher order function found in many functional programming languages is the fold function. Given as an argument a function that adds two numbers, fold will find the sum of all the numbers in a sequence. Given a function that multiplies two numbers, it will find the product of the numbers in the sequence. In fact fold takes three arguments: the sequence to be processed, the function to process two values, and the initial value. It turns out that the fold function can be used, with suitable arguments, to perform a wide variety of aggregation functions on sequences.

The key to the technique is that although you cannot pass a function or template as an argument to another function or template, you can pass a node, and can use <xsl:apply-templates> to trigger execution of a template associated with that node.

Rather than show you how fold works, which you can find out on the FXSL Web site, I will use another example that makes greater use of the new capabilities in XSLT 2.0. A common problem is to check whether there are cycles in your data. For example, your data might represent a part explosion, and you want to check that no part is a component of itself, directly or indirectly. Or you might be checking an XSLT stylesheet to check that no attribute set is defined in terms of itself. (There is an example that shows how to do this conventionally, without a higher order function, under <xsl:function> on page 307.) The problem is that there are many ways one can represent a relationship between two nodes in XML, and we don't want to have to write a new function to check for cycles each time we come across a new way of representing a relationship. So we write a general higher order function that looks for cycles, and pass it as a parameter, a function (actually represented by a node that will trigger a template rule) that knows how a particular relationship is represented.

Checking for Cycles in a Graph

This example provides a generic procedure to look for cycles in a graph, and then applies this procedure to a data file to see if the ID/ IDREF links are cyclic.

The algorithm to check for a cycle is this. Given a function links(A) that returns the set of nodes to which A is directly linked, the function refers(A, B) is true if links(A) includes B (that is, if there is a direct reference) or if there is a node C in the result of links(A) such that refers(C, B) is true (this is an indirect reference via C). This is a recursive definition, of course, and it is implemented by a recursive function. Finally, you know that A participates in a cycle if refers(A, A) is true.

Stylesheet

The stylesheet that searches for cycles in a graph is in cycle.xsl .

You can implement the refers function like this:

  <xsl:function name="graph:refers" as="xs:boolean">   <xsl:param name="links" as="node()"/>   <!-- $links is a node that represents the template to be called -->   <xsl:param name="A" as="node()"/>   <xsl:param name="B" as="node()"/>   <!-- find the directly-connected nodes -->   <xsl:variable name="direct" as="node()*">   <xsl:apply-templates select="$links">   <xsl:with-param name="from" select="$A"/>   </xsl:apply-templates>   </xsl:variable>   <!-- return true if B is directly or indirectly connected from A -->   <xsl:sequence select="if (exists($direct intersect $B)) then true()   else if (some $C in $direct   satisfies graph:refers($links, $C, $B))   then true()   else false()"/>   </xsl:function>

When you call this higher order function, you need to supply a node as the $links argument that will always cause a particular template rule to be invoked. Let's do this for the case where the link is established by virtue of the fact that the first node contains an idref attribute whose value matches the id attribute of the node that it references. This is in idref-cycle.xsl :

  <xsl:variable name="graph:idref-links" as="element()">   <graph:idref-link/>   </xsl:variable>   <xsl:template match="graph:idref-link" as="node()*">   <xsl:param name="from" required="yes" as="node()"/>   <xsl:sequence select="$from/id($from/@idref)"/>   </xsl:template>

And now you can test whether the context node participates in a cycle like this:

  <xsl:template name="check-context-node">   <xsl:if test="graph:refers($graph:idref-links,   .,   .)">   <xsl:message terminate="yes">Cycle detected!</xsl:message>   </xsl:if>   </xsl:template>

Let's look at the details of how this works:

The higher order function is implemented using <xsl:function> . It can't actually take a function or a template as a parameter, so what it takes instead is a node, which uniquely identifies the specific code to be executed to follow a link.

The code to follow a link is implemented as a template rule, and is invoked using <xsl:apply-templates> . An element is created ( <graph:idref-link> ) whose sole purpose is to trigger the execution of the associated template rule. Note that because of the «as="element()" » attribute on the <xsl:variable> element, the variable holds a single (parentless) element node, not a temporary tree.

Unlike conventional template rules that create new nodes, this particular rule returns a reference to a sequence of existing nodes: specifically, the nodes selected by the select attribute of the <xsl:sequence> instruction. The result of the <xsl:apply-templates> instruction is also captured in a variable with an as attribute, which means that the result of the variable is the sequence of nodes returned by the template. Without the as attribute, the nodes would be copied to make a temporary tree, which wouldn't work, because the XPath intersect operator relies on the nodes in the variable $direct having their original identity (used in the way it is used here, it tests whether $B is one of the nodes in $direct ).

The important thing about this stylesheet is that the module cycle.xsl is completely general-purpose: it has no knowledge of how the links between nodes are represented, and can therefore be used to look for cycles in any graph, however it is implemented.