Sunday 29 October 2006 Arabica: XSLT: xsl:import and xsl:apply-imports

Last week I wondered aloud whether my current SAX based approach to building an XSLT engine was going to work. Specifically the piece of spec text I was worried about was section 2.6.2 which says

The xsl:import element is only allowed as a top-level element. The xsl:import element children must precede all other element children of an xsl:stylesheet element, including any xsl:include element children. When xsl:include is used to include a stylesheet, any xsl:import elements in the included document are moved up in the including document to after any existing xsl:import elements in the including document.

It was the "moving up" part that I was worried about. Moving up - you can't do that when you're working in a stream mode.

Section 2.6.2 continues with a discussion of import precedence, which gave me the clue I needed. It says

An xsl:stylesheet element in the import tree is defined to have lower import precedence than another xsl:stylesheet element in the import tree if it would be visited before that xsl:stylesheet element in a post-order traversal of the import tree.

...
Each definition and template rule has import precedence determined by the xsl:stylesheet element that contains it.

For example, suppose

• stylesheet A imports stylesheets B and C in that order;
• stylesheet B imports stylesheet D;
• stylesheet C imports stylesheet E.

Then the order of import precedence (lowest first) is D, B, E, C, A.

The first sentence there isn't the world's clearest, but the important bit is "post-order traversal". In English, that means backwards. I'll come back to this in a minute.

While the spec says imports are "moved up", that doesn't mean they have to be actually moved around and processed before the remainder of the stylesheet. In the example above, consider how you'd worked out the import of precedence of B. You need to know not only about B, but also C and E. However, you need to have looked into C to know about E, to work out the precedence of B. Makes my head hurt anyway. But you don't need to do it in the way the spec seems to be leading you. In fact, you can do anything you like so long as the result achieved is equivalent.

Turns out, processing imports can be delayed until the very end of the stylesheet. All you need to do is keep a list of the stylesheets to be imported as you go. Once you hit the end of the initial stylesheet, you work through the list you've made in reverse order (post-order traversal, remember) and load each extra stylesheet. Should one of those stylesheet import a further stylesheet, push it on to the end of the list, which automatically makes it the next stylesheet you pull in. Keep going until your list is empty. Magically, you've pulled in the imported stylesheets in exactly the order required by the spec. Run through the example above, and you'll see it just drops out. Fab.

I was quite startled when I realised how straightforward it was. Initial implementation only took an hour or so, and I've just committed it to svn.

---

Tagged code, arabica, xml, and c++

---