Reasonable Object Oriented (OO) type systems have been available for XML Schema languages for several years now[SOX], and in particular the W3C's XML Schema Language (XSD)[XSD], but tools to take advantage of this natively have been slower to appear. The one area that has seen the exploitation of these type systems have been data binding mechanisms, particularly those building programming components from a schema[BINDING]. But the most popular mechanisms for manipulating XML - XSLT[XSLT], SAX[SAX], and DOM[DOM] - have not taken advantage of this. In this paper we will focus on adding object oriented features to XSLT.

The first part of enabling XSD-based object-oriented programming in XSLT is inserting inheritance information into the document where rules can access it. Current processors do not supply this information, although XSLT2 will include an element() function which takes optional element and type QNames and returns true if the current node is in the substitution group of the element or is derived from the type. As current processors have not implemented this feature, we will demonstrate a "poor man's" element() function implemented in Xerces/Xalan. We synthesize attributes containing the type and substitution group information and make this easily accessible through extension functions. Once this is available, it is possible to write XPath expressions using XSD's two type hierarchies, as well as templates that match polymorphically. Polymorphic matching is possible through carefully controlling the priority of the different templates - templates that are "more specific" (further down the inheritance tree) must have higher priorities than those meant to match base types. Having described this mechanism, we'll present a small example of these patterns in use. The conclusion will discuss how XSLT might be extended to provide better support for this programming style.

OO programming is far too well known [OO] to go into a lengthy discussion of features and benefits here. For our purposes we will describe OO systems as having the following three characteristics:

Of these, XSD provides us with inheritance. The substance of this paper is mostly about the message passing. There is no means of ensuring encapsulation, but it is recommended as a programming style.

The XSD specification describes a huge amount of information called the PSVI that is, for the most part, extraneous to the needs of object-oriented applications. The PSVI represents the entire reflection of the schema information of the document. Reflection refers to any system where the underlying structures of the system are made available programmatically at the application level. Java, for example, has a fairly rich reflective API - applications can access the class object, find out about public methods, etc. However this degree of access is unnecessary for the vast majority of OO and XML applications, and may even become a performance issue. Methods are written specialized for a particular class (or in our case, element or type) and reside within the encapsulation layer. They know about the structure they are operating on. Therefore the reflective apparatus is rarely needed. What is needed is the ability to determine which class, or classes, an object belongs to. That is enough information to locate applicable methods. To see this, consider an implementation of methods that ties them to class objects. Given a method name and an object's inheritance hierarchy, one can start at the object's class and climb up the hierarchy, at each level checking for a relevant method on the list attached to that class. As one goes up the list, one will eventually stop at the most specific method.

Because the inheritance hierarchy is the only essential information required to enable most OO programming, the implementation provides three lists, stuffed in synthesized attributes. These lists handle the two inheritance hierarchies of XSD and provide the following information:

The first two of these lists contain a representation of the QNames of the appropriate components. The third is a little more complicated, as it is a list of entries where the first part of each entry is the attribute name, and the second is the type hierarchy. Each QName is represented as the namespace, followed by two colons, and then followed by the local name. For example, http://www.example.com::foobar represents the local name foobar in the http://www.example.com namespace. If found in xsi:subGroup, then it is the QName of an element, else it is the QName of a type. The content of the xsi:attDeriv attribute is a list of bracketed ("[" and "]") values, where the first value in the list is the QName of the attribute followed by the inheritance hierarchy of its type. For example, the value of the attribute for the schemaLocation attribute is xsi:attDeriv="[http://www.w3.org/2001/XMLSchema-instance::schemaLocation http://www.w3.org/2001/XMLSchema::anySimpleType http://www.w3.org/2001/XMLSchema::anyType].

These lists are generated down in the guts of the validator[XERCES] by intercepting events after they have been validated, walking the PSVI information and creating the additional information by synthesizing the attributes and adding them back to the events. The following description describes our work with Xerces, but could be replicated with any validator producing PSVI information.

We start by creating a new XMLDocumentFilter and a new ParserConfiguration to use the filter when validating. The Xerces XMLDocumentFilter class is very similar to a SAX content handler in that there are callbacks for various parser events. However, the set of events are not quite the same and the method signatures are different. Of particular interest to us is a catch-all parameter added to these methods of type Augmentations. Augmentations basically is an association list of extra information - give it the name of an augmentation, and it will return an object with the corresponding information, if it has one. For example, the augmentation information for a schema-validated element is an XSElementDeclaration object. With this object we can immediately walk up the substitution group hierarchy using getSubstitutionGroupAffiliation method. In order to be able to specify totally general behavior, we've inserted an xs:anyElement to be the root of the hierarchy. This is not a component currently in XSD. After generating the first list, we get the type of the object by calling getTypeDefinition on the element and then walking up the type hierarchy by calling getBaseType until we come to an end. We ensure that the last type is xsd:anyType. Finally we iterate through the attributes and generate the last list in a similar fashion. Having these three type lists, we then create an attribute for each. The document filter then passes the events on to the DocumentHandler for the pipeline. The result is a document with three new attributes inserted containing all the derivation information. This information is now available for any current XML technology, such as a SAX or DOM application - or an XSLT stylesheet.

The information in the three attributes is enough, by itself, to implement polymorphism in XSLT, but it is rather clunky. We can determine if a given element is in the substitution group of another, or if the type of the element is a subtype of another, but we need to do so using string functions. For example, to determine if an element is in the substitution group of the <foo> element in the bar namespace, we need the following: *[contains(@xsi:subGroup,'bar::foo')], i.e., we check whether the contents of the subGroup attribute contains the string "bar::foo". A more elegant solution would be to emulate the element() function of XSLT2. This function takes two parameters. The first is either the name of an element or an asterisk; the second is either the name of a type or an asterisk. If an element name is given, then element() returns true only if the current node is an element in its substitution group. Likewise for type names: element() only returns true if the current node is an element whose type is derived from it. In both cases, the asterisk functions as a wildcard and matches anything (as if either xsd:anyElement or xsd:anyType had been used. We've chosen to follow the XSLT2 example by implementing element() as a extension function. Now the expression above can be replaced by *[ooxml:element('bar::foo', '*')], where ooxml is the namespace of the extension.

Having a way to check types, the next step is implementing polymorphic templates. Given elements foo, bar, and baz, where foo <: bar <: baz, a <foo> element would match all three of the following:

The element function returns a boolean value - true or false. Each of these will return true, so no path expression would be more precise. However, if we consider the templates like methods, then clearly the first is more specific than the other two and should be the correct one to treat a <foo> element. Of course, if we get a <bar> element, then we want the second template to match (which is fine, as such an element would only have ::bar and ::baz in the subGroup attribute anyway).

The mechanism to ensure the desired behavior is to assign each of these templates a different priority. As we want the most specific template to have the highest priority, we assign each template a priority based on the depth of the associated type or element in the hierarchy. Therefore, templates matching anyElement or anyType have priority 0, while templates for baz have priority 1, for bar have priority 2, and for foo have priority 3. This works well, in that it will both have the desired behavior and adding a template for a new component doesn't affect the priorities given to the old templates. So we replace the templates above with the following:

<template match="*[ooxml:element('*','::foo')]" priority="3">...</template> 
<template match="*[ooxml:element('*','::bar')]" priority="2">... </template>
<template match="*[ooxml:element('*','::baz')]" priority="1">... </template> 

While this works well for cases where there is either an element or a type, but not for a combination. In that case, the fact that there are two hierarchies proceeding at different rates means a single numbering of priorities could give the wrong answer. With two, we need a way to vary both type and element inheritance independently. The easiest way to do this is to choose one as a primary index and the other as a secondary. We'll choose substitution group as the primary hierarchy and derivation as the secondary. This means all templates should sort so a match against an element takes precedence over a match against a type. (There may be reasons to give precedence to derivation - only experience will tell.) We associate an asterisk for the element as a match against AnyElement, and an asterisk for the type as a match against anyType. Templates meant to match an element have a non-negative integer (with AnyElement represented by 0). Templates meant to match against a type have a fractional value to the right of the decimal place, with anyType matching a 0. The first derived type has .1, the next .2, up to the ninth. The tenth, though, is .91, etc. Given types tFoo <: tBar <: tBaz, a template meant to match just tBaz would have a priority of 0.3, but a template meant to match a bar element having type tFoo would have priority 2.1.

While none of our examples will require mixed matching, SAML provides an example where it is useful. In SAML, there are extension points where a SAML element is defined with an abstract type, requiring any use of the element to have an extension type not defined by SAML. In such a case it can be important to match both the extension element and the type being used to extend it.

To give a sense of this in use, we will use an example of numbers and operators. In this, we display a list of numbers and operations. Numbers and operations are arranged in hierarchies to aid in manipulating them. In particular, we start with the following schema fragment:

<xs:schema targetNamespace="numbers" xmlns:tns="numbers"
    xmlns:xs="http://www.w3.org/2001/XMLSchema"> 
    <xs:complexType name="tNumber" abstract="true"/> 
    <xs:complexType name="tComplex">
    <xs:complexContent> <xs:extension base="tns:tNumber">
    <xs:sequence> <xs:element name="real" type="xs:decimal"/> 
    <xs:element name="imaginary" type="xs:decimal"/> 
    </xs:sequence> </xs:extension>
    </xs:complexContent> </xs:complexType> 
    <xs:complexType name="tScientific"> 
    <xs:complexContent> 
    <xs:extension base="tns:tNumber"> 
    <xs:sequence> 
    <xs:element name="value" type="xs:decimal"/> 
    <xs:element name="precision" type="xs:integer"/>
    </xs:sequence> </xs:extension> </xs:complexContent>
    </xs:complexType> <xs:complexType name="tCurrency">
    <xs:complexContent> <xs:extension base="tns:tNumber">
    <xs:sequence> <xs:element name="amount" type="xs:decimal"/>
    </xs:sequence> <xs:attribute name="country" type="xs:NMTOKEN"/>
    </xs:extension> </xs:complexContent> </xs:complexType>
    <xs:element abstract="true" name="TwoPartNumber" 
      type="tns:tTwoPartNumber"/>
    <xs:element name="Complex" substitutionGroup="tns:TwoPartNumber" 
      type="tns:tComplex"/>
    <xs:element name="Scientific" substitutionGroup="tns:TwoPartNumber" 
      type="tns:tScientific"/>
    <xs:element name="Currency" substitutionGroup="tns:TwoPartNumber" 
      type="tns:tCurrency"/>
    </xs:schema> 

This defines the basic types we'll be working with. There's an abstract number type, tNumber,and an abstract element, Number, to make sure our type hierarchies has a root. We can now write templates to match all the numbers we will create by matching the approapriate abstract base class. Then we have elements for the different kinds of numbers. We'll concentrate on Currency. In particular, we'll have two particular currencies to consider - the US Dollar and the British Pound:.

At this point, note that each currency has a fixed value for the country attribute, but there is no longer any link in the document back to either Number or Currency. A USDollar element would look like <USDollar>123</USDollar>. The relationship between USDollar and Currency resides in the schema and in the information generated, and then generally discarded, by the validator.

Next we have operations and operators. Operations function over some number of inputs, while (for us) Operators take only one or two inputs. We'll only consider three of these - Add, Minus, and Equals (the last is technically a relation, but that's beyond the scope of this paper). The schema for these is:

From this we see that an Operation (which operates on Numbers) can appear anywhere a number can and contains a list of Numbers.

<nm:NumberList xmlns:nm="numbers" 
    xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
    xsi:schemaLocation="numbers file:/Users/matthew/ooxml/numbers.xsd">
  <nm:Complex>
    <real xmlns="">123</real>
    <imaginary xmlns="">456</imaginary>
  </nm:Complex>
  <nm:USDollar>
      <amount>123</amount>
  </nm:USDollar>
  <nm:Pound>
      <amount>123</amount>
  </nm:Pound>
  <nm:Franc>
      <amount>345</amount>
  </nm:Franc>
  <nm:Scientific>
      <value xmlns="">123.456</value>
      <precision xmlns="">5</precision>
  </nm:Scientific>
  <nm:Equals>
      <nm:Add>
          <nm:USDollar>
              <amount>123</amount>
          </nm:USDollar>
          <nm:Add>
              <nm:Pound>
                  <amount>444</amount>
              </nm:Pound>
              <nm:Pound>
                  <amount>123</amount>
              </nm:Pound>
          </nm:Add>
      </nm:Add>
      <nm:Add>
          <nm:USDollar>
              <amount>123</amount>
          </nm:USDollar>
          <nm:Add>
              <nm:Pound>
                  <amount>444</amount>
              </nm:Pound>
              <nm:Pound>
                  <amount>1235</amount>
              </nm:Pound>
          </nm:Add>
      </nm:Add>
  </nm:Equals>
</nm:NumberList>

<html xmlns:xsm="http://matt" 
  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" 
  xmlns:xalan="http://xml.apache.org/xalan" xmlns:num="numbers">
<body>
<ul>
<li>123 + 456 i </li>
<li>$123</li>
<li>£123</li>
<li>345FR</li>
<li>UnknownNumericType</li>
<li>($123+(<i>£444</i>+£123))!=($123+(<i>£444</i>+£1235))</li>
</ul>
</body>
</html>

<xsl:template match="/"> 
  <html> 
    <body>
           <xsl:apply-templates/> 
     </body> 
  </html> 
</xsl:template>
<xsl:template match="*[matt:element('numbers::NumberList','*')]" 
  mode="li" priority="1"> 
    <ul> 
        <xsl:apply-templates mode="li"/> 
    </ul>
 </xsl:template> 
 <xsl:template match="*[matt:element('numbers::Number','*')]" 
  mode="li" priority="1"> 
     <li> 
       <xsl:apply-templates mode="display" select="."/> 
     </li> 
 </xsl:template>

<xsl:template match="*[matt:element('numbers::Complex','*')]" 
  mode="display" priority="2"> 
<xsl:value-of select="./*[position()=1]"/> 
<xsl:text> + </xsl:text> 
<xsl:value-of select="./*[position()=2]"/> 
<xsl:text> i </xsl:text> </xsl:template>

We have presented a number of patterns for object-oriented programming in XSLT given access to a polymorphic operator, element(). We hope this will enable the intrepid to start exploiting this ability, even at this early date, about six years after this because possible. However, experimenting with this naturally demonstrates how much better it would be to provide support for these patterns and more natively within XSL. Therefore, the rest of this conclusion will be devoted to identifying issues in XSLT related to supporting full Object-Oriented programming.

The most obvious area in which XSLT could be improved would be to provide some syntactic support. Calculating appropriate priorities for templates could easily be done mechanically. XPath could also make type or substitution group traversal axes, reducing the size of expressions.

The most severe limitation XSLT places on this approach is the strict separation of input values and result values. The full panoply of XPath can be applied to input values, but only a very limited set can be applied to output values. The means it is very difficult to do function composition. For example, the result of adding two Number elements is another number element, but the add template cannot return one, because that result cannot be added to another element returned by an add template. Functional composition is a very common programming style not easily supported by XSLT. Many OO languages also allow a method to call the same method on a super class. In XSLT terms, this would mean allowing a template to call the template with next highest priority.

We hope this will spur further development to exploit the OO features of XSD in native XML processing.