xalan-j/xsltc/xsl_key

<?xml version="1.0" encoding="UTF-8" standalone="no"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"> <html> <head> <title>ASF: <xsl:key> / key() / IdKeyPattern</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8" /> <meta http-equiv="Content-Style-Type" content="text/css" /> <link rel="stylesheet" type="text/css" href="resources/apache-xalan.css" /> </head>  <body> <div id="title"> <table class="HdrTitle"> <tbody> <tr> <th rowspan="2"> <a href="../index.html"> <img alt="Trademark Logo" src="resources/XalanJ-Logo-tm.png" width="190" height="90" /> </a> </th> <th text-align="center" width="75%"> <a href="index.html">XSLTC Design</a> </th> </tr> <tr> <td valign="middle"><xsl:key> / key() / IdKeyPattern</td> </tr> </tbody> </table> <table class="HdrButtons" align="center" border="1"> <tbody> <tr> <td> <a href="http://www.apache.org">Apache Foundation</a> </td> <td> <a href="http://xalan.apache.org">Xalan Project</a> </td> <td> <a href="http://xerces.apache.org">Xerces Project</a> </td> <td> <a href="http://www.w3.org/TR">Web Consortium</a> </td> <td> <a href="http://www.oasis-open.org/standards">Oasis Open</a> </td> </tr> </tbody> </table> </div> <div id="navLeft"> <ul> <li> <a href="index.html">Overview</a> </li></ul><hr /><ul> <li> <a href="xsltc_compiler.html">Compiler design</a> </li></ul><hr /><ul> <li> <a href="xsl_whitespace_design.html">Whitespace</a> </li> <li> <a href="xsl_sort_design.html">xsl:sort</a> </li> <li>Keys<br /> </li> <li> <a href="xsl_comment_design.html">Comment design</a> </li></ul><hr /><ul> <li> <a href="xsl_lang_design.html">lang()</a> </li> <li> <a href="xsl_unparsed_design.html">Unparsed entities</a> </li></ul><hr /><ul> <li> <a href="xsl_if_design.html">If design</a> </li> <li> <a href="xsl_choose_design.html">Choose|When|Otherwise design</a> </li> <li> <a href="xsl_include_design.html">Include|Import design</a> </li> <li> <a href="xsl_variable_design.html">Variable|Param design</a> </li></ul><hr /><ul> <li> <a href="xsltc_runtime.html">Runtime</a> </li></ul><hr /><ul> <li> <a href="xsltc_dom.html">Internal DOM</a> </li> <li> <a href="xsltc_namespace.html">Namespaces</a> </li></ul><hr /><ul> <li> <a href="xsltc_trax.html">Translet & TrAX</a> </li> <li> <a href="xsltc_predicates.html">XPath Predicates</a> </li> <li> <a href="xsltc_iterators.html">Xsltc Iterators</a> </li> <li> <a href="xsltc_native_api.html">Xsltc Native API</a> </li> <li> <a href="xsltc_trax_api.html">Xsltc TrAX API</a> </li> <li> <a href="xsltc_performance.html">Performance Hints</a> </li> </ul> </div> <div id="content"> <h2><xsl:key> / key() / IdKeyPattern</h2> <p align="right" size="2"> <a href="#content">(top)</a> </p> <h3>Contents</h3> <ul> <li> <a href="#functionality">Functionality</a> </li> <li> <a href="#implementation">Implementation</a> </li> </ul> <a name="functionality">‌</a> <p align="right" size="2"> <a href="#content">(top)</a> </p> <h3>Functionality</h3> <p>The <code><xsl:key></code> 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:</p> <ul> <li> <code>name</code> - the name of the index </li> <li> <code>match</code> - a pattern that defines the nodeset we want indexed </li> <li> <code>use</code> - an expression that defines the value to be used as the index key value. </li> </ul> <p>A named index can be accessed using either the <code>key()</code> 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):</p> <blockquote class="source"> <pre> <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></pre> </blockquote> <p>The KeyPattern can be used within an index definition to create unions and intersections of node sets:</p> <blockquote class="source"> <pre> <xsl:key name="cultcies" match="farmer | fisherman" use="name"/></pre> </blockquote> <p>This could have been done using regular <code><xsl:for-each></code> and <code><xsl:select></code> 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.</p> <a name="implementation">‌</a> <p align="right" size="2"> <a href="#content">(top)</a> </p> <h3>Implementation</h3> <a name="indexing">‌</a> <p align="right" size="2"> <a href="#content">(top)</a> </p> <h4>Indexing</h4> <p>The <code>AbstractTranslet</code> class has a global hashtable that holds an index for each named key in the stylesheet (hashing on the "name" attribute of <code><xsl:key></code>). <code>AbstractTranslet</code> has a couple of public methods for inserting and retrieving data from this hashtable:</p> <blockquote class="source"> <pre> public void buildKeyIndex(String keyName, int nodeID, String value); public KeyIndex KeyIndex getKeyIndex(String keyName);</pre> </blockquote> <p>The <code>Key</code> class compiles code that traverses the input DOM and extracts nodes that match some given parameters (the <code>"match"</code> attribute of the <code><xsl:key></code> element). A new element is inserted into the named key's index. The nodes' DOM index and the value translated from the <code>"use"</code> attribute of the <code><xsl:key></code> element are stored in the new entry in the index.</p> <p>Something similar is done for indexing IDs. This index is generated from the <code>ID</code> and <code>IDREF</code> 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 <code>org.apache.xalan.xsltc.dom.DTDMonitor</code> class. This class implements the <code>org.xml.sax.XMLReader</code> and <code>org.xml.sax.DTDHandler</code> interfaces. A client application using the native API must instanciate a <code>DTDMonitor</code> 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 <a href="xsltc_native_api.html">XSLTC Native API reference</a>. The <code>DTDMonitor</code> class will use the same indexing as the code generated by the <code>Key</code> class. The index for ID's is called "##id". We assume that no stylesheets will contain a key with this name.</p> <p>The index itself is implemented in the <code>org.apache.xalan.xsltc.dom.KeyIndex</code> 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 <code>"use"</code> attribute). For every matching value there is a bit-array (implemented in the <code>org.apache.xalan.xsltc.BitArray</code> class), holding a list of all node indexes for which this value gives a match:</p> <p> <img src="key_relations.gif" alt="key_relations.gif" /> </p> <p> <b> <i>Figure 1: Indexing tables</i> </b> </p> <p>The <code>KeyIndex</code> class implements the <code>NodeIterator</code> interface, so that it can be returned directly by the implementation of the <code>key()</code> function. This is how the index generated by <code><xsl:key></code> and the node-set returned by the <code>key()</code> and KeyPattern are tied together. You can see how this is done in the <code>translate()</code> method of the <code>KeyCall</code> class.</p> <p>The <code>key()</code> function can be called in two ways:</p> <blockquote class="source"> <pre> key('key-name','value') key('key-name','node-set')</pre> </blockquote> <p>The first parameter is always the name of the key. We use this value to lookup our index from the _keyIndexes hashtable in AbstractTranslet:</p> <blockquote class="source"> <pre> il.append(classGen.aloadThis()); _name.translate(classGen, methodGen); il.append(new INVOKEVIRTUAL(getKeyIndex));</pre> </blockquote> <p>This compiles into a call to <code>AbstractTranslet.getKeyIndex(String name)</code>, and it leaves a <code>KeyIndex</code> object on the stack. What we then need to do it to initialise the <code>KeyIndex</code> to give us nodes with the requested value. This is done by leaving the <code>KeyIndex</code> object on the stack and pushing the <code>"value"</code> parameter to <code>key()</code>, before calling <code>lookup()</code> on the index:</p> <blockquote class="source"> <pre> il.append(DUP); // duplicate the KeyIndex obejct before return _value.translate(classGen, methodGen); il.append(new INVOKEVIRTUAL(lookup));</pre> </blockquote> <p>This compiles into a call to <code>KeyIndex.lookup(String value)</code>. This will initialise the <code>KeyIndex</code> object to return nodes that match the given value, so the <code>KeyIndex</code> object can be left on the stack when we return. This because the <code>KeyIndex</code> object implements the <code>NodeIterator</code> interface.</p> <p>This matter is a bit more complex when the second parameter of <code>key()</code> 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:</p> <ul> <li> construct a <code>KeyIndex</code> object that will hold the return node-set </li> <li> find the named <code>KeyIndex</code> object from the hashtable in AbstractTranslet </li> <li> get an iterator for the node-set and do the folowing loop:</li> <ul> <li>get string value for current node</li> <li>do lookup in KeyIndex object for the named index</li> <li>merge the resulting node-set into the return node-set</li> </ul> <li> leave the return node-set on stack when done </li> </ul> <a name="improvements">‌</a> <p align="right" size="2"> <a href="#content">(top)</a> </p> <h4>Possible indexing improvements</h4> <p>The indexing implementation can be very, very memeory exhaustive as there is one <code>BitArray</code> 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 <code>BitArray</code> is used just to contain one node. The <code>KeyIndex</code> class should be updated to hold the first node for a value in an <code>Integer</code> object, and then replace that with a <code>BitArray</code> or a <code>Vector</code> only is a second node is added to the value. Here is an outline for <code>KeyIndex</code>:</p> <blockquote class="source"> <pre> 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); } } }</pre> </blockquote> <p>Other methods inside the <code>KeyIndex</code> should be updated to reflect this.</p> <a name="patterns">‌</a> <p align="right" size="2"> <a href="#content">(top)</a> </p> <h4>Id and Key patterns</h4> <p>As already mentioned, the challenge with the <code>id()</code> and <code>key()</code> 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 <code>org.apache.xalan.xsltc.compiler.Mode</code> class. The <code>Mode</code> class has a method, <code>flatternAlaternative</code>, 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 <code>TestSeq</code> 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 <code>Mode</code> class when generating the <code>applyTemplates</code> 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 <code>switch()</code> in the <code>applyTemplates()</code> 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 <b>not</b> recommend using this type of patterns with XSLTC.</p> <p align="right" size="2"> <a href="#content">(top)</a> </p> </div> <div id="footer">Copyright © 1999-2014 The Apache Software Foundation<br />Apache, Xalan, and the Feather logo are trademarks of The Apache Software Foundation<div class="small">Web Page created on - Thu 2014-05-15</div> </div> </body> </html>

xalan-j/xsltc/xsl_key_design.html (369 lines of code) (raw):