XML Tips

Digg This!

One of the things I enjoy most about working with XML and its related technologies is that there is always more to learn. I have been using XML for three years, but not a week goes by that I'm not pleasantly surprised to find something new I can do with it - or, even better, to find an easier way to do something I thought I had already figured out.

One such discovery occurred recently in connection with the rendering of "connected tree"-style hierarchies. A connected tree is one in which lines link nodes to their parents and children, as in many types of file system and outline displays. (See Figure 1 for an example.) The application we are currently building at PortBlue uses this type of display in many places for different purposes, making it difficult to unify handling of the rendering process across the varying types of data in the hierarchies. However, all the hierarchy types are available as DOM trees. It struck me that if I could find a way to render connected trees using only XSLT, I could remove all the application code associated with tree rendering and use a single stylesheet to handle all the tree rendering, which would vastly simplify our code.

Implementing this idea has resulted in several hundred lines of bug-prone Java rendering code (spread across many classes) being replaced with a few dozen lines of XSL in a single stylesheet, improving our system's reliability, maintainability, and ease of customization. In this article, I'll explain how we did it.

As I'm sure most readers are already aware, XSL and XSLT are paired standards that specify how to describe a transformation between XML and some other desired format for the same data. An XSL stylesheet provides a recipe for finding data in the source XML data, transforming it, and outputting the transformed version. The technology has a multitude of uses, but probably the most commonly encountered application is the transformation of XML data into appropriate HTML for presentation to a human user.

Yet another specification, called XPath, is used extensively in XSLT. XPath is a functional language for locating information in an XML tree structure. Its role in XSLT is as a structural pattern-matching tool for finding the data that is to be transformed into particular parts of the generated document.

For me, at least, XPath has been the hardest part of the XSLT toolkit to learn. One aspect of XPath that gave me particular trouble is the use of "axes" to send the XSLT processor through the document in different "directions." The technique I will describe here depends on three different axes being used, and hopefully will provide a useful introduction to the power of axis specification for those joining me in climbing this learning curve. But before going on, let's examine what is involved in rendering a tree like the one shown in Figure 1.

Four Sticks Make a Tree
If you examine Figure 1 closely, you'll notice that there are only four graphic shapes needed to draw the tree. First, each element is connected to the tree by a graphic with a horizontal prong going from center to right. If it is not the last child element of its parent, the prong is attached to a bar that goes all the way from top to bottom, giving it the shape of a capital T rotated 90º left. The last child is missing the bottom half of the vertical bar, giving it the shape of a capital L, or of the lower-left corner of a square.

If the element is more than one level deep in the hierarchy, there will be other tree graphics to the left of the connector graphics just discussed. For each level of "ancestor" of the current element, one of two graphics appears. If that ancestor is not the last child element of its own parent, then a vertical bar is shown, part of a series of such lines leading down to the next sibling element at that level. If that ancestor is the last child of its own parent, we instead display an empty spacer graphic.

For purposes of this article, I have created four images, tree_tee, tree_corner, tree_bar, and tree_spacer (see Figures 2; images are also available at www.sys-con.com/xml/sourcec.cfm). Each meets the descriptions given here, with the exception that I've added a visible dot to the center of the spacer image to make it clear where it is being used.

With the above analysis in place, we can write an informal algorithm for how each line of a tree is to be rendered:

1. For each level of ancestor from the top of the tree to the parent of the current element, draw a spacer if that element is the last sibling under its parent, a bar if it is not.
2. Draw a corner if the current element is the last sibling of its parent element, a tee if it is not.
3. Draw the identifying information for the current element.

One of my coworkers eloquently dubbed the line of graphics generated in steps 1 and 2 the "stick stack," which is actually a pretty good way to think about it; you're building a stack of sticks (connector graphics), one for each level from the root to the current element. The rightmost graphic will always be a tee or a corner, and those further to the left (if any) will always be bars or spacers. Similarly, we use "item display" to cover what you render to the right of the "stick stack" to provide information about each element - in the case of our example, this is simply the element's title, formatted according to the element type. So you can further summarize the process as "For each element in the tree, draw the stick stack, then the item display."

As usual, the devil is in the details. So let's turn our attention to how this is implemented in XSLT.

Under the Hood
The source document used to produce Figure 1 is called "book.xml" and appears as Listing 1. It is a very simple XML document containing the outline of a book. The top-level book element contains chapter elements, and these contain section elements, which may themselves contain other sections. Each element has a title attribute, which we will use to display its name in the tree. Obviously, this is a very simplistic document, but the principles we will be using to transform it apply equally well to more complex documents.

The stylesheet that we will be applying to the source document is called "connected_tree.xsl" and appears as Listing 2. Again, this is an artificially simple stylesheet, but the concepts it illustrates can be extended to more ambitious transformations.

Lines 1-13 of the XSL file are boilerplate, standard header material that would appear at the top of any XSL file being used to map into HTML.

The more interesting stuff starts on line 17, with the definition of a template that will match the top-level book element in the XML document. Within this template, we generate the static HTML components for the output page. One of these is an embedded CSS style definition section in the header, which we use to adjust margins and borders so that our tree graphics will join pixel-to-pixel without unsightly gaps, and also to adjust vertical alignment so text will flow cleanly from the ends of the rightmost connector graphics.

On line 28 we output the title of the book (that is, the value of the title attribute of the book element), enclosed in <b>...</b> tags so that it will be displayed in boldface. Then, on line 29, we apply relevant templates to the children of the book element, operating in "line" mode. In this and other cases of applying templates to children, the child elements will be processed in document order. As each will in turn do its own processing and then apply templates to its own children, the desired "tree-order" output generation is accomplished.

XSL modes allow us to process the same element in different ways in different circumstances, which you're about to see is the key to this solution. "Line" mode selects templates that handle rendering of the full output line, including the stick stack and the item display. The other modes used here are "item" and "tree," which we'll discuss later.

All element types handle "line" mode the same way, so there's only one "line" mode template, matching all element types; it begins on line 36. Within this template we will generate all of the output for one horizontal line of the tree diagram. We wrap the display in a <div> element of the appropriate CSS class to achieve the desired zero-border, vertically centered display. Within the <div> we find two predictable components. The first, on line 38, calls the "graft" template (as in "graft this branch onto the tree") to build the stick stack; we'll discuss how that works below. The second, on line 39, applies templates to the current node again, but this time in "item" mode rather than in "line" mode. Outside the <div>, at the end of the template, we do all this in turn to the children of the current element, continuing the full-tree traversal.

"Item" mode is used to achieve the item display rendering mentioned previously. Each element type will typically do this differently. For this example, each of the two element types that can appear in a book (chapter and section) has its own "item"-mode template (see lines 46-52). Again, we simply output element title attributes with different formatting for each type.

And with this, at last we reach the fun part. I mentioned above that the "graft" template (which starts on line 57) builds the stick stack for the element on which it is called. How does it do this? The easiest way to approach this question turns out to be backwards, conceptually from right to left on the line. So skip down to line 62, where we generate the connector graphic - the one that will be right next to our item display, with a "prong" sticking out to the right. As we noted above, this will be a corner graphic if this element is the last child of its parent, a tee otherwise. If you read the source, that's exactly what it says - the tricky part is understanding how it determines if the current element is the last child of its parent.

The key to accomplishing this is the use of an alternative "XPath axis." For most common purposes, the default child axis is what you want; it selects the children of the current node. We've used it extensively to get this far. However, there are many other axes you can use to traverse the source document in various "directions." The first one we will discuss is following-sibling, which (not surprisingly) selects the siblings (children of the same parent) of the current element that are later in document order. You can see it being used on line 63, in a conditional test. If "following-sibling::*" returns a non-empty node set, it is considered true for test purposes and we choose the tee graphic; otherwise, if the set of following siblings is empty, this counts as a false result, and we display the corner graphic. The following-sibling axis (and its complement, the preceding-sibling axis) are extremely useful in any case where you need to do something special at the ends of a list of sibling elements.

So that's how the rightmost stick in the stack is rendered. But what about the rest of it? As you'll recall, there should be one graphic for every chapter or section that is an ancestor of the current element, with each being a bar or spacer depending on whether that ancestral element has following siblings. Half the solution should be obvious from how I phrased that, but how do we visit our ancestors to make the decision?

This time, the trick is another XPath axis: ancestor. On line 59, you'll notice that we are applying templates in "tree" mode to a node set selected as "ancestor::*". This expression means "all the ancestors of the current node, from the root downward, excluding the node itself." This is exactly the set for which we need to generate "sticks," which occurs in the two final templates, each tagged as being applicable to "tree" mode.

The first, on line 74, simply suppresses generating a graphic for the root (book) element. We're dealing with that element separately, in the "/book" template we discussed earlier, so we want to ignore it for tree-rendering purposes.

The second, starting on line 78, uses logic just like that we discussed above to choose between a bar or a spacer graphic based on the presence or absence of following siblings.

The Road (to XSLT) Goes Ever On and On
And that's it! If you apply the stylesheet to the XML source, you will obtain HTML that produces a display like that shown in Figure 1. There are numerous ways to do this; my preferred technique for XSL experimentation is to use the Apache Xalan command-line mode, which (assuming you have it installed, working, and in your CLASSPATH) looks like this:

java org.apache.xalan.xslt.Process
-IN book.xml -XSLconnected_tree.xsl
-OUT book.html

Note that this article examines just one way to do the connected-tree rendering trick, and there are endless ways to customize, enhance, or otherwise fiddle with it. In my own experience, the key to learning XSLT has been experimentation, so I encourage you to try changing both connected_tree.xsl and book.xml in various ways to see what happens. A lot of the ideas behind XSLT and XPath can be counterintuitive at first, but gradually you'll discover that it all actually makes a rather beautiful kind of sense. And then you'll be able to share your own interesting tricks with the world.