| Contents |

- Functionality
- Implementation

| Functionality |

The `<xsl:key>` element is a top-level element that can be used to define a named index of nodes from the source XML tree(s). The element has three attributes:

- `name` - the name of the index
- `match` - a pattern that defines the nodeset we want indexed
- `use` - an expression that defines the value to be used as the index key value.

A named index can be accessed using either the `key()` function or a KeyPattern. Both these methods address the index using its defined name (the "name" attribute above) and a parameter defining one or more lookup values for the index. The function or pattern returns a node set containing all nodes in the index whose key value match the parameter's value(s):

        <xsl:key name="book-author" match="book" use="author"/>
            :
            :
        <xsl:for-each select="key('book-author', 'Mikhail Bulgakov')">
          <xsl:value-of select="author"/>
          <xsl:text>: </xsl:text>
          <xsl:value-of select="author"/>
          <xsl:text>&#xa;</xsl:text>
        </xsl:for-each>

The KeyPattern can be used within an index definition to create unions and intersections of node sets:

        <xsl:key name="cultcies" match="farmer | fisherman" use="name"/>

This could have been done using regular `<xsl:for-each>` and `<xsl:select>` elements. However, if your stylesheet accesses the same selection of nodes over and over again, the transformation will be much more efficient using pre-indexed keys as shown above.

| Implementation |

| Indexing |

The `AbstractTranslet` class has a global hashtable that holds an index for each named key in the stylesheet (hashing on the "name" attribute of `<xsl:key>`). `AbstractTranslet` has a couple of public methods for inserting and retrieving data from this hashtable:

        public void buildKeyIndex(String keyName, int nodeID, String value);
        public KeyIndex KeyIndex getKeyIndex(String keyName);

The `Key` class compiles code that traverses the input DOM and extracts nodes that match some given parameters (the `"match"` attribute of the `<xsl:key>` element). A new element is inserted into the named key's index. The nodes' DOM index and the value translated from the `"use"` attribute of the `<xsl:key>` element are stored in the new entry in the index.

Something similar is done for indexing IDs. This index is generated from the `ID` and `IDREF` fields in the input document's DTD. This means that the code for generating this index cannot be generated at compile-time, which again means that the code has to be generic enough to handle all DTDs. The class that handles this is the `org.apache.xalan.xsltc.dom.DTDMonitor` class. This class implements the `org.xml.sax.XMLReader` and `org.xml.sax.DTDHandler` interfaces. A client application using the native API must instanciate a `DTDMonitor` and pass it to the translet code - if, and only if, it wants IDs indexed (one can improve performance by omitting this step). This is descrived in the XSLTC Native API reference. The `DTDMonitor` class will use the same indexing as the code generated by the `Key` class. The index for ID's is called "##id". We assume that no stylesheets will contain a key with this name.

The index itself is implemented in the `org.apache.xalan.xsltc.dom.KeyIndex` class. The index has an hashtable with all the values from the matching nodes (the part of the node used to generate this value is the one specified in the `"use"` attribute). For every matching value there is a bit-array (implemented in the `org.apache.xalan.xsltc.BitArray` class), holding a list of all node indexes for which this value gives a match:

Figure 1: Indexing tables

The `KeyIndex` class implements the `NodeIterator` interface, so that it can be returned directly by the implementation of the `key()` function. This is how the index generated by `<xsl:key>` and the node-set returned by the `key()` and KeyPattern are tied together. You can see how this is done in the `translate()` method of the `KeyCall` class.

The `key()` function can be called in two ways:

        key('key-name','value')
        key('key-name','node-set')

The first parameter is always the name of the key. We use this value to lookup our index from the _keyIndexes hashtable in AbstractTranslet:

        il.append(classGen.aloadThis());
        _name.translate(classGen, methodGen);
        il.append(new INVOKEVIRTUAL(getKeyIndex));

This compiles into a call to `AbstractTranslet.getKeyIndex(String name)`, and it leaves a `KeyIndex` object on the stack. What we then need to do it to initialise the `KeyIndex` to give us nodes with the requested value. This is done by leaving the `KeyIndex` object on the stack and pushing the `"value"` parameter to `key()`, before calling `lookup()` on the index:

        il.append(DUP);  // duplicate the KeyIndex obejct before return
        _value.translate(classGen, methodGen);
        il.append(new INVOKEVIRTUAL(lookup));

This compiles into a call to `KeyIndex.lookup(String value)`. This will initialise the `KeyIndex` object to return nodes that match the given value, so the `KeyIndex` object can be left on the stack when we return. This because the `KeyIndex` object implements the `NodeIterator` interface.

This matter is a bit more complex when the second parameter of `key()` is a node-set. In this case we need to traverse the nodes in the set and do a lookup for each node in the set. What I do is this:

- construct a `KeyIndex` object that will hold the return node-set
- find the named `KeyIndex` object from the hashtable in AbstractTranslet
- get an iterator for the node-set and do the folowing loop:

- get string value for current node
- do lookup in KeyIndex object for the named index
- merge the resulting node-set into the return node-set

- leave the return node-set on stack when done

| Possible indexing improvements |

The indexing implementation can be very, very memeory exhaustive as there is one `BitArray` allocated for each value for every index. This is particulary bad for the index used for IDs ('##id'), where a single value should only map to one, single node. This means that a whole `BitArray` is used just to contain one node. The `KeyIndex` class should be updated to hold the first node for a value in an `Integer` object, and then replace that with a `BitArray` or a `Vector` only is a second node is added to the value. Here is an outline for `KeyIndex`:

        public void add(Object value, int node) {
            Object container;
    	if ((container = (BitArray)_index.get(value)) == null) {
                _index.put(value, new Integer(node));
    	}
    	else {
                // Check if there is _one_ node for this value
                if (container instanceof Integer) {
                    int first = ((Integer)container
                    _nodes = new BitArray(_arraySize);
                    _nodes.setMask(node & 0xff000000);
                    _nodes.setBit(first & 0x00ffffff);
                    _nodes.setBit(node & 0x00ffffff);
                    _index.put(value, _nodes);
                }
                // Otherwise add node to axisting bit array
                else {
                    _nodex = (BitArray)container;
                    _nodes.setBit(node & 0x00ffffff);
                }
            }
        }

Other methods inside the `KeyIndex` should be updated to reflect this.

| Id and Key patterns |

As already mentioned, the challenge with the `id()` and `key()` patterns is that they have no specific node type. Patterns are normally grouped based on their pattern's "kernel" node type. This is done in the `org.apache.xalan.xsltc.compiler.Mode` class. The `Mode` class has a method, `flatternAlaternative`, that does this grouping, and all templates with a common kernel node type will be inserted into a "test sequence". A test sequence is a set templates with the same kernel node type. The `TestSeq` class generates code that will figure out which pattern, amongst several patterns with the same kernel node type, that matches a certain node. This is used by the `Mode` class when generating the `applyTemplates` method in the translet. A test sequence is also generated for all templates whose pattern does not have a kernel node type. This is the case for all Id and KeyPatterns. This test sequence, if necessary, is put before the big `switch()` in the `applyTemplates()` mehtod. This test has to be done for every single node that is traversed, causing the transformation to slow down siginificantly. This is why we do not recommend using this type of patterns with XSLTC.

Copyright © 2004 The Apache Software Foundation. All Rights Reserved.