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 of course be 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.

AbstractTranslet 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 name, int nodeID, String value); public KeyIndex KeyIndex getKeyIndex(String name);

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.

The index itself is implemented in the 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 Vector 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

The only work that remains is to update the merge() method of the KeyIndex class so that it eliminates duplicate nodes in the resulting node-set.