| 1 | <?xml version="1.0" encoding="ISO-8859-1"?>
|
|---|
| 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
|---|
| 3 | <html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" /><style type="text/css">
|
|---|
| 4 | TD {font-family: Verdana,Arial,Helvetica}
|
|---|
| 5 | BODY {font-family: Verdana,Arial,Helvetica; margin-top: 2em; margin-left: 0em; margin-right: 0em}
|
|---|
| 6 | H1 {font-family: Verdana,Arial,Helvetica}
|
|---|
| 7 | H2 {font-family: Verdana,Arial,Helvetica}
|
|---|
| 8 | H3 {font-family: Verdana,Arial,Helvetica}
|
|---|
| 9 | A:link, A:visited, A:active { text-decoration: underline }
|
|---|
| 10 | </style><title>Library internals</title></head><body bgcolor="#8b7765" text="#000000" link="#a06060" vlink="#000000"><table border="0" width="100%" cellpadding="5" cellspacing="0" align="center"><tr><td width="120"><a href="http://swpat.ffii.org/"><img src="epatents.png" alt="Action against software patents" /></a></td><td width="180"><a href="http://www.gnome.org/"><img src="gnome2.png" alt="GNOME2 Logo" /></a><a href="http://www.w3.org/Status"><img src="w3c.png" alt="W3C logo" /></a><a href="http://www.redhat.com"><img src="redhat.gif" alt="Red Hat Logo" /></a><div align="left"><a href="http://xmlsoft.org/XSLT/"><img src="Libxslt-Logo-180x168.gif" alt="Made with Libxslt Logo" /></a></div></td><td><table border="0" width="90%" cellpadding="2" cellspacing="0" align="center" bgcolor="#000000"><tr><td><table width="100%" border="0" cellspacing="1" cellpadding="3" bgcolor="#fffacd"><tr><td align="center"><h1>The XSLT C library for GNOME</h1><h2>Library internals</h2></td></tr></table></td></tr></table></td></tr></table><table border="0" cellpadding="4" cellspacing="0" width="100%" align="center"><tr><td bgcolor="#8b7765"><table border="0" cellspacing="0" cellpadding="2" width="100%"><tr><td valign="top" width="200" bgcolor="#8b7765"><table border="0" cellspacing="0" cellpadding="1" width="100%" bgcolor="#000000"><tr><td><table width="100%" border="0" cellspacing="1" cellpadding="3"><tr><td colspan="1" bgcolor="#eecfa1" align="center"><center><b>Main Menu</b></center></td></tr><tr><td bgcolor="#fffacd"><form action="search.php" enctype="application/x-www-form-urlencoded" method="get"><input name="query" type="text" size="20" value="" /><input name="submit" type="submit" value="Search ..." /></form><ul><li><a href="index.html">Home</a></li><li><a href="intro.html">Introduction</a></li><li><a href="docs.html">Documentation</a></li><li><a href="bugs.html">Reporting bugs and getting help</a></li><li><a href="help.html">How to help</a></li><li><a href="downloads.html">Downloads</a></li><li><a href="FAQ.html">FAQ</a></li><li><a href="news.html">News</a></li><li><a href="xsltproc2.html">The xsltproc tool</a></li><li><a href="docbook.html">DocBook</a></li><li><a href="API.html">The programming API</a></li><li><a href="python.html">Python and bindings</a></li><li><a href="internals.html">Library internals</a></li><li><a href="extensions.html">Writing extensions</a></li><li><a href="contribs.html">Contributions</a></li><li><a href="EXSLT/index.html" style="font-weight:bold">libexslt</a></li><li><a href="xslt.html">flat page</a>, <a href="site.xsl">stylesheet</a></li><li><a href="html/index.html" style="font-weight:bold">API Menu</a></li><li><a href="ChangeLog.html">ChangeLog</a></li></ul></td></tr></table><table width="100%" border="0" cellspacing="1" cellpadding="3"><tr><td colspan="1" bgcolor="#eecfa1" align="center"><center><b>Related links</b></center></td></tr><tr><td bgcolor="#fffacd"><ul><li><a href="tutorial/libxslttutorial.html">Tutorial</a>,
|
|---|
| 11 | <a href="tutorial2/libxslt_pipes.html">Tutorial2</a></li><li><a href="xsltproc.html">Man page for xsltproc</a></li><li><a href="http://mail.gnome.org/archives/xslt/">Mail archive</a></li><li><a href="http://xmlsoft.org/">XML libxml2</a></li><li><a href="ftp://xmlsoft.org/">FTP</a></li><li><a href="http://www.zlatkovic.com/projects/libxml/">Windows binaries</a></li><li><a href="http://garypennington.net/libxml2/">Solaris binaries</a></li><li><a href="http://www.explain.com.au/oss/libxml2xslt.html">MacOsX binaries</a></li><li><a href="http://bugzilla.gnome.org/buglist.cgi?product=libxslt">Bug Tracker</a></li><li><a href="http://codespeak.net/lxml/">lxml Python bindings</a></li><li><a href="http://cpan.uwinnipeg.ca/dist/XML-LibXSLT">Perl XSLT bindings</a></li><li><a href="http://www.zend.com/php5/articles/php5-xmlphp.php#Heading17">XSLT with PHP</a></li><li><a href="http://www.mod-xslt2.com/">Apache module</a></li><li><a href="http://sourceforge.net/projects/libxml2-pas/">Pascal bindings</a></li><li><a href="http://xsldbg.sourceforge.net/">Xsldbg Debugger</a></li></ul></td></tr></table><table width="100%" border="0" cellspacing="1" cellpadding="3"><tr><td colspan="1" bgcolor="#eecfa1" align="center"><center><b>API Indexes</b></center></td></tr><tr><td bgcolor="#fffacd"><ul><li><a href="APIchunk0.html">Alphabetic</a></li><li><a href="APIconstructors.html">Constructors</a></li><li><a href="APIfunctions.html">Functions/Types</a></li><li><a href="APIfiles.html">Modules</a></li><li><a href="APIsymbols.html">Symbols</a></li></ul></td></tr></table></td></tr></table></td><td valign="top" bgcolor="#8b7765"><table border="0" cellspacing="0" cellpadding="1" width="100%"><tr><td><table border="0" cellspacing="0" cellpadding="1" width="100%" bgcolor="#000000"><tr><td><table border="0" cellpadding="3" cellspacing="1" width="100%"><tr><td bgcolor="#fffacd"><h3>Table of contents</h3><ul><li><a href="internals.html#Introducti">Introduction</a></li>
|
|---|
| 12 | <li><a href="internals.html#Basics">Basics</a></li>
|
|---|
| 13 | <li><a href="internals.html#Keep">Keep it simple stupid</a></li>
|
|---|
| 14 | <li><a href="internals.html#libxml">The libxml nodes</a></li>
|
|---|
| 15 | <li><a href="internals.html#XSLT">The XSLT processing steps</a></li>
|
|---|
| 16 | <li><a href="internals.html#XSLT1">The XSLT stylesheet compilation</a></li>
|
|---|
| 17 | <li><a href="internals.html#XSLT2">The XSLT template compilation</a></li>
|
|---|
| 18 | <li><a href="internals.html#processing">The processing itself</a></li>
|
|---|
| 19 | <li><a href="internals.html#XPath">XPath expressions compilation</a></li>
|
|---|
| 20 | <li><a href="internals.html#XPath1">XPath interpretation</a></li>
|
|---|
| 21 | <li><a href="internals.html#Descriptio">Description of XPath
|
|---|
| 22 | Objects</a></li>
|
|---|
| 23 | <li><a href="internals.html#XPath3">XPath functions</a></li>
|
|---|
| 24 | <li><a href="internals.html#stack">The variables stack frame</a></li>
|
|---|
| 25 | <li><a href="internals.html#Extension">Extension support</a></li>
|
|---|
| 26 | <li><a href="internals.html#Futher">Further reading</a></li>
|
|---|
| 27 | <li><a href="internals.html#TODOs">TODOs</a></li>
|
|---|
| 28 | </ul><h3><a name="Introducti2" id="Introducti2">Introduction</a></h3><p>This document describes the processing of <a href="http://xmlsoft.org/XSLT/">libxslt</a>, the <a href="http://www.w3.org/TR/xslt">XSLT</a> C library developed for the <a href="http://www.gnome.org/">GNOME</a> project.</p><p>Note: this documentation is by definition incomplete and I am not good at
|
|---|
| 29 | spelling, grammar, so patches and suggestions are <a href="mailto:[email protected]">really welcome</a>.</p><h3><a name="Basics1" id="Basics1">Basics</a></h3><p>XSLT is a transformation language. It takes an input document and a
|
|---|
| 30 | stylesheet document and generates an output document:</p><p align="center"><img src="processing.gif" alt="the XSLT processing model" /></p><p>Libxslt is written in C. It relies on <a href="http://www.xmlsoft.org/">libxml</a>, the XML C library for GNOME, for
|
|---|
| 31 | the following operations:</p><ul><li>parsing files</li>
|
|---|
| 32 | <li>building the in-memory DOM structure associated with the documents
|
|---|
| 33 | handled</li>
|
|---|
| 34 | <li>the XPath implementation</li>
|
|---|
| 35 | <li>serializing back the result document to XML and HTML. (Text is handled
|
|---|
| 36 | directly.)</li>
|
|---|
| 37 | </ul><h3><a name="Keep1" id="Keep1">Keep it simple stupid</a></h3><p>Libxslt is not very specialized. It is built under the assumption that all
|
|---|
| 38 | nodes from the source and output document can fit in the virtual memory of
|
|---|
| 39 | the system. There is a big trade-off there. It is fine for reasonably sized
|
|---|
| 40 | documents but may not be suitable for large sets of data. The gain is that it
|
|---|
| 41 | can be used in a relatively versatile way. The input or output may never be
|
|---|
| 42 | serialized, but the size of documents it can handle are limited by the size
|
|---|
| 43 | of the memory available.</p><p>More specialized memory handling approaches are possible, like building
|
|---|
| 44 | the input tree from a serialization progressively as it is consumed,
|
|---|
| 45 | factoring repetitive patterns, or even on-the-fly generation of the output as
|
|---|
| 46 | the input is parsed but it is possible only for a limited subset of the
|
|---|
| 47 | stylesheets. In general the implementation of libxslt follows the following
|
|---|
| 48 | pattern:</p><ul><li>KISS (keep it simple stupid)</li>
|
|---|
| 49 | <li>when there is a clear bottleneck optimize on top of this simple
|
|---|
| 50 | framework and refine only as much as is needed to reach the expected
|
|---|
| 51 | result</li>
|
|---|
| 52 | </ul><p>The result is not that bad, clearly one can do a better job but more
|
|---|
| 53 | specialized too. Most optimization like building the tree on-demand would
|
|---|
| 54 | need serious changes to the libxml XPath framework. An easy step would be to
|
|---|
| 55 | serialize the output directly (or call a set of SAX-like output handler to
|
|---|
| 56 | keep this a flexible interface) and hence avoid the memory consumption of the
|
|---|
| 57 | result.</p><h3><a name="libxml" id="libxml">The libxml nodes</a></h3><p>DOM-like trees, as used and generated by libxml and libxslt, are
|
|---|
| 58 | relatively complex. Most node types follow the given structure except a few
|
|---|
| 59 | variations depending on the node type:</p><p align="center"><img src="node.gif" alt="description of a libxml node" /></p><p>Nodes carry a <strong>name</strong> and the node <strong>type</strong>
|
|---|
| 60 | indicates the kind of node it represents, the most common ones are:</p><ul><li>document nodes</li>
|
|---|
| 61 | <li>element nodes</li>
|
|---|
| 62 | <li>text nodes</li>
|
|---|
| 63 | </ul><p>For the XSLT processing, entity nodes should not be generated (i.e. they
|
|---|
| 64 | should be replaced by their content). Most nodes also contains the following
|
|---|
| 65 | "navigation" information:</p><ul><li>the containing <strong>doc</strong>ument</li>
|
|---|
| 66 | <li>the <strong>parent</strong> node</li>
|
|---|
| 67 | <li>the first <strong>children</strong> node</li>
|
|---|
| 68 | <li>the <strong>last</strong> children node</li>
|
|---|
| 69 | <li>the <strong>prev</strong>ious sibling</li>
|
|---|
| 70 | <li>the following sibling (<strong>next</strong>)</li>
|
|---|
| 71 | </ul><p>Elements nodes carries the list of attributes in the properties, an
|
|---|
| 72 | attribute itself holds the navigation pointers and the children list (the
|
|---|
| 73 | attribute value is not represented as a simple string to allow usage of
|
|---|
| 74 | entities references).</p><p>The <strong>ns</strong> points to the namespace declaration for the
|
|---|
| 75 | namespace associated to the node, <strong>nsDef</strong> is the linked list
|
|---|
| 76 | of namespace declaration present on element nodes.</p><p>Most nodes also carry an <strong>_private</strong> pointer which can be
|
|---|
| 77 | used by the application to hold specific data on this node.</p><h3><a name="XSLT" id="XSLT">The XSLT processing steps</a></h3><p>There are a few steps which are clearly decoupled at the interface
|
|---|
| 78 | level:</p><ol><li>parse the stylesheet and generate a DOM tree</li>
|
|---|
| 79 | <li>take the stylesheet tree and build a compiled version of it (the
|
|---|
| 80 | compilation phase)</li>
|
|---|
| 81 | <li>take the input and generate a DOM tree</li>
|
|---|
| 82 | <li>process the stylesheet against the input tree and generate an output
|
|---|
| 83 | tree</li>
|
|---|
| 84 | <li>serialize the output tree</li>
|
|---|
| 85 | </ol><p>A few things should be noted here:</p><ul><li>the steps 1/ 3/ and 5/ are optional</li>
|
|---|
| 86 | <li>the stylesheet obtained at 2/ can be reused by multiple processing 4/
|
|---|
| 87 | (and this should also work in threaded programs)</li>
|
|---|
| 88 | <li>the tree provided in 2/ should never be freed using xmlFreeDoc, but by
|
|---|
| 89 | freeing the stylesheet.</li>
|
|---|
| 90 | <li>the input tree 4/ is not modified except the _private field which may
|
|---|
| 91 | be used for labelling keys if used by the stylesheet</li>
|
|---|
| 92 | </ul><h3><a name="XSLT1" id="XSLT1">The XSLT stylesheet compilation</a></h3><p>This is the second step described. It takes a stylesheet tree, and
|
|---|
| 93 | "compiles" it. This associates to each node a structure stored in the
|
|---|
| 94 | _private field and containing information computed in the stylesheet:</p><p align="center"><img src="stylesheet.gif" alt="a compiled XSLT stylesheet" /></p><p>One xsltStylesheet structure is generated per document parsed for the
|
|---|
| 95 | stylesheet. XSLT documents allow includes and imports of other documents,
|
|---|
| 96 | imports are stored in the <strong>imports</strong> list (hence keeping the
|
|---|
| 97 | tree hierarchy of includes which is very important for a proper XSLT
|
|---|
| 98 | processing model) and includes are stored in the <strong>doclist</strong>
|
|---|
| 99 | list. An imported stylesheet has a parent link to allow browsing of the
|
|---|
| 100 | tree.</p><p>The DOM tree associated to the document is stored in <strong>doc</strong>.
|
|---|
| 101 | It is preprocessed to remove ignorable empty nodes and all the nodes in the
|
|---|
| 102 | XSLT namespace are subject to precomputing. This usually consist of
|
|---|
| 103 | extracting all the context information from the context tree (attributes,
|
|---|
| 104 | namespaces, XPath expressions), and storing them in an xsltStylePreComp
|
|---|
| 105 | structure associated to the <strong>_private</strong> field of the node.</p><p>A couple of notable exceptions to this are XSLT template nodes (more on
|
|---|
| 106 | this later) and attribute value templates. If they are actually templates,
|
|---|
| 107 | the value cannot be computed at compilation time. (Some preprocessing could
|
|---|
| 108 | be done like isolation and preparsing of the XPath subexpressions but it's
|
|---|
| 109 | not done, yet.)</p><p>The xsltStylePreComp structure also allows storing of the precompiled form
|
|---|
| 110 | of an XPath expression that can be associated to an XSLT element (more on
|
|---|
| 111 | this later).</p><h3><a name="XSLT2" id="XSLT2">The XSLT template compilation</a></h3><p>A proper handling of templates lookup is one of the keys of fast XSLT
|
|---|
| 112 | processing. (Given a node in the source document this is the process of
|
|---|
| 113 | finding which templates should be applied to this node.) Libxslt follows the
|
|---|
| 114 | hint suggested in the <a href="http://www.w3.org/TR/xslt#patterns">5.2
|
|---|
| 115 | Patterns</a> section of the XSLT Recommendation, i.e. it doesn't evaluate it
|
|---|
| 116 | as an XPath expression but tokenizes it and compiles it as a set of rules to
|
|---|
| 117 | be evaluated on a candidate node. There usually is an indication of the node
|
|---|
| 118 | name in the last step of this evaluation and this is used as a key check for
|
|---|
| 119 | the match. As a result libxslt builds a relatively more complex set of
|
|---|
| 120 | structures for the templates:</p><p align="center"><img src="templates.gif" alt="The templates related structure" /></p><p>Let's describe a bit more closely what is built. First the xsltStylesheet
|
|---|
| 121 | structure holds a pointer to the template hash table. All the XSLT patterns
|
|---|
| 122 | compiled in this stylesheet are indexed by the value of the the target
|
|---|
| 123 | element (or attribute, pi ...) name, so when a element or an attribute "foo"
|
|---|
| 124 | needs to be processed the lookup is done using the name as a key.</p><p>Each of the patterns is compiled into an xsltCompMatch structure. It holds
|
|---|
| 125 | the set of rules based on the tokenization of the pattern stored in reverse
|
|---|
| 126 | order (matching is easier this way). It also holds some information about the
|
|---|
| 127 | previous matches used to speed up the process when one iterates over a set of
|
|---|
| 128 | siblings. (This optimization may be defeated by trashing when running
|
|---|
| 129 | threaded computation, it's unclear that this is a big deal in practice.)
|
|---|
| 130 | Predicate expressions are not compiled at this stage, they may be at run-time
|
|---|
| 131 | if needed, but in this case they are compiled as full XPath expressions (the
|
|---|
| 132 | use of some fixed predicate can probably be optimized, they are not yet).</p><p>The xsltCompMatch are then stored in the hash table, the clash list is
|
|---|
| 133 | itself sorted by priority of the template to implement "naturally" the XSLT
|
|---|
| 134 | priority rules.</p><p>Associated to the compiled pattern is the xsltTemplate itself containing
|
|---|
| 135 | the information required for the processing of the pattern including, of
|
|---|
| 136 | course, a pointer to the list of elements used for building the pattern
|
|---|
| 137 | result.</p><p>Last but not least a number of patterns do not fit in the hash table
|
|---|
| 138 | because they are not associated to a name, this is the case for patterns
|
|---|
| 139 | applying to the root, any element, any attributes, text nodes, pi nodes, keys
|
|---|
| 140 | etc. Those are stored independently in the stylesheet structure as separate
|
|---|
| 141 | linked lists of xsltCompMatch.</p><h3><a name="processing" id="processing">The processing itself</a></h3><p>The processing is defined by the XSLT specification (the basis of the
|
|---|
| 142 | algorithm is explained in <a href="http://www.w3.org/TR/xslt#section-Introduction">the Introduction</a>
|
|---|
| 143 | section). Basically it works by taking the root of the input document and
|
|---|
| 144 | applying the following algorithm:</p><ol><li>Finding the template applying to it. This is a lookup in the template
|
|---|
| 145 | hash table, walking the hash list until the node satisfies all the steps
|
|---|
| 146 | of the pattern, then checking the appropriate(s) global templates to see
|
|---|
| 147 | if there isn't a higher priority rule to apply</li>
|
|---|
| 148 | <li>If there is no template, apply the default rule (recurse on the
|
|---|
| 149 | children)</li>
|
|---|
| 150 | <li>else walk the content list of the selected templates, for each of them:
|
|---|
| 151 | <ul><li>if the node is in the XSLT namespace then the node has a _private
|
|---|
| 152 | field pointing to the preprocessed values, jump to the specific
|
|---|
| 153 | code</li>
|
|---|
| 154 | <li>if the node is in an extension namespace, look up the associated
|
|---|
| 155 | behavior</li>
|
|---|
| 156 | <li>otherwise copy the node.</li>
|
|---|
| 157 | </ul><p>The closure is usually done through the XSLT
|
|---|
| 158 | <strong>apply-templates</strong> construct recursing by applying the
|
|---|
| 159 | adequate template on the input node children or on the result of an
|
|---|
| 160 | associated XPath selection lookup.</p>
|
|---|
| 161 | </li>
|
|---|
| 162 | </ol><p>Note that large parts of the input tree may not be processed by a given
|
|---|
| 163 | stylesheet and that on the opposite some may be processed multiple times.
|
|---|
| 164 | (This often is the case when a Table of Contents is built).</p><p>The module <code>transform.c</code> is the one implementing most of this
|
|---|
| 165 | logic. <strong>xsltApplyStylesheet()</strong> is the entry point, it
|
|---|
| 166 | allocates an xsltTransformContext containing the following:</p><ul><li>a pointer to the stylesheet being processed</li>
|
|---|
| 167 | <li>a stack of templates</li>
|
|---|
| 168 | <li>a stack of variables and parameters</li>
|
|---|
| 169 | <li>an XPath context</li>
|
|---|
| 170 | <li>the template mode</li>
|
|---|
| 171 | <li>current document</li>
|
|---|
| 172 | <li>current input node</li>
|
|---|
| 173 | <li>current selected node list</li>
|
|---|
| 174 | <li>the current insertion points in the output document</li>
|
|---|
| 175 | <li>a couple of hash tables for extension elements and functions</li>
|
|---|
| 176 | </ul><p>Then a new document gets allocated (HTML or XML depending on the type of
|
|---|
| 177 | output), the user parameters and global variables and parameters are
|
|---|
| 178 | evaluated. Then <strong>xsltProcessOneNode()</strong> which implements the
|
|---|
| 179 | 1-2-3 algorithm is called on the root element of the input. Step 1/ is
|
|---|
| 180 | implemented by calling <strong>xsltGetTemplate()</strong>, step 2/ is
|
|---|
| 181 | implemented by <strong>xsltDefaultProcessOneNode()</strong> and step 3/ is
|
|---|
| 182 | implemented by <strong>xsltApplyOneTemplate()</strong>.</p><h3><a name="XPath" id="XPath">XPath expression compilation</a></h3><p>The XPath support is actually implemented in the libxml module (where it
|
|---|
| 183 | is reused by the XPointer implementation). XPath is a relatively classic
|
|---|
| 184 | expression language. The only uncommon feature is that it is working on XML
|
|---|
| 185 | trees and hence has specific syntax and types to handle them.</p><p>XPath expressions are compiled using <strong>xmlXPathCompile()</strong>.
|
|---|
| 186 | It will take an expression string in input and generate a structure
|
|---|
| 187 | containing the parsed expression tree, for example the expression:</p><pre>/doc/chapter[title='Introduction']</pre><p>will be compiled as</p><pre>Compiled Expression : 10 elements
|
|---|
| 188 | SORT
|
|---|
| 189 | COLLECT 'child' 'name' 'node' chapter
|
|---|
| 190 | COLLECT 'child' 'name' 'node' doc
|
|---|
| 191 | ROOT
|
|---|
| 192 | PREDICATE
|
|---|
| 193 | SORT
|
|---|
| 194 | EQUAL =
|
|---|
| 195 | COLLECT 'child' 'name' 'node' title
|
|---|
| 196 | NODE
|
|---|
| 197 | ELEM Object is a string : Introduction
|
|---|
| 198 | COLLECT 'child' 'name' 'node' title
|
|---|
| 199 | NODE</pre><p>This can be tested using the <code>testXPath</code> command (in the
|
|---|
| 200 | libxml codebase) using the <code>--tree</code> option.</p><p>Again, the KISS approach is used. No optimization is done. This could be
|
|---|
| 201 | an interesting thing to add. <a href="http://www-106.ibm.com/developerworks/library/x-xslt2/?dwzone=x?open&l=132%2ct=gr%2c+p=saxon">Michael
|
|---|
| 202 | Kay describes</a> a lot of possible and interesting optimizations done in
|
|---|
| 203 | Saxon which would be possible at this level. I'm unsure they would provide
|
|---|
| 204 | much gain since the expressions tends to be relatively simple in general and
|
|---|
| 205 | stylesheets are still hand generated. Optimizations at the interpretation
|
|---|
| 206 | sounds likely to be more efficient.</p><h3><a name="XPath1" id="XPath1">XPath interpretation</a></h3><p>The interpreter is implemented by <strong>xmlXPathCompiledEval()</strong>
|
|---|
| 207 | which is the front-end to <strong>xmlXPathCompOpEval()</strong> the function
|
|---|
| 208 | implementing the evaluation of the expression tree. This evaluation follows
|
|---|
| 209 | the KISS approach again. It's recursive and calls
|
|---|
| 210 | <strong>xmlXPathNodeCollectAndTest()</strong> to collect nodes set when
|
|---|
| 211 | evaluating a <code>COLLECT</code> node.</p><p>An evaluation is done within the framework of an XPath context stored in
|
|---|
| 212 | an <strong>xmlXPathContext</strong> structure, in the framework of a
|
|---|
| 213 | transformation the context is maintained within the XSLT context. Its content
|
|---|
| 214 | follows the requirements from the XPath specification:</p><ul><li>the current document</li>
|
|---|
| 215 | <li>the current node</li>
|
|---|
| 216 | <li>a hash table of defined variables (but not used by XSLT)</li>
|
|---|
| 217 | <li>a hash table of defined functions</li>
|
|---|
| 218 | <li>the proximity position (the place of the node in the current node
|
|---|
| 219 | list)</li>
|
|---|
| 220 | <li>the context size (the size of the current node list)</li>
|
|---|
| 221 | <li>the array of namespace declarations in scope (there also is a namespace
|
|---|
| 222 | hash table but it is not used in the XSLT transformation).</li>
|
|---|
| 223 | </ul><p>For the purpose of XSLT an <strong>extra</strong> pointer has been added
|
|---|
| 224 | allowing to retrieve the XSLT transformation context. When an XPath
|
|---|
| 225 | evaluation is about to be performed, an XPath parser context is allocated
|
|---|
| 226 | containing and XPath object stack (this is actually an XPath evaluation
|
|---|
| 227 | context, this is a remain of the time where there was no separate parsing and
|
|---|
| 228 | evaluation phase in the XPath implementation). Here is an overview of the set
|
|---|
| 229 | of contexts associated to an XPath evaluation within an XSLT
|
|---|
| 230 | transformation:</p><p align="center"><img src="contexts.gif" alt="The set of contexts associated " /></p><p>Clearly this is a bit too complex and confusing and should be refactored
|
|---|
| 231 | at the next set of binary incompatible releases of libxml. For example the
|
|---|
| 232 | xmlXPathCtxt has a lot of unused parts and should probably be merged with
|
|---|
| 233 | xmlXPathParserCtxt.</p><h3><a name="Descriptio" id="Descriptio">Description of XPath Objects</a></h3><p>An XPath expression manipulates XPath objects. XPath defines the default
|
|---|
| 234 | types boolean, numbers, strings and node sets. XSLT adds the result tree
|
|---|
| 235 | fragment type which is basically an unmodifiable node set.</p><p>Implementation-wise, libxml follows again a KISS approach, the
|
|---|
| 236 | xmlXPathObject is a structure containing a type description and the various
|
|---|
| 237 | possibilities. (Using an enum could have gained some bytes.) In the case of
|
|---|
| 238 | node sets (or result tree fragments), it points to a separate xmlNodeSet
|
|---|
| 239 | object which contains the list of pointers to the document nodes:</p><p align="center"><img src="object.gif" alt="An Node set object pointing to " /></p><p>The <a href="http://xmlsoft.org/html/libxml-xpath.html">XPath API</a> (and
|
|---|
| 240 | its <a href="http://xmlsoft.org/html/libxml-xpathinternals.html">'internal'
|
|---|
| 241 | part</a>) includes a number of functions to create, copy, compare, convert or
|
|---|
| 242 | free XPath objects.</p><h3><a name="XPath3" id="XPath3">XPath functions</a></h3><p>All the XPath functions available to the interpreter are registered in the
|
|---|
| 243 | function hash table linked from the XPath context. They all share the same
|
|---|
| 244 | signature:</p><pre>void xmlXPathFunc (xmlXPathParserContextPtr ctxt, int nargs);</pre><p>The first argument is the XPath interpretation context, holding the
|
|---|
| 245 | interpretation stack. The second argument defines the number of objects
|
|---|
| 246 | passed on the stack for the function to consume (last argument is on top of
|
|---|
| 247 | the stack).</p><p>Basically an XPath function does the following:</p><ul><li>check <code>nargs</code> for proper handling of errors or functions
|
|---|
| 248 | with variable numbers of parameters</li>
|
|---|
| 249 | <li>pop the parameters from the stack using <code>obj =
|
|---|
| 250 | valuePop(ctxt);</code></li>
|
|---|
| 251 | <li>do the function specific computation</li>
|
|---|
| 252 | <li>push the result parameter on the stack using <code>valuePush(ctxt,
|
|---|
| 253 | res);</code></li>
|
|---|
| 254 | <li>free up the input parameters with
|
|---|
| 255 | <code>xmlXPathFreeObject(obj);</code></li>
|
|---|
| 256 | <li>return</li>
|
|---|
| 257 | </ul><p>Sometime the work can be done directly by modifying in-situ the top object
|
|---|
| 258 | on the stack <code>ctxt->value</code>.</p><h3><a name="stack" id="stack">The XSLT variables stack frame</a></h3><p>Not to be confused with XPath object stack, this stack holds the XSLT
|
|---|
| 259 | variables and parameters as they are defined through the recursive calls of
|
|---|
| 260 | call-template, apply-templates and default templates. This is used to define
|
|---|
| 261 | the scope of variables being called.</p><p>This part seems to be the most urgent attention right now, first it is
|
|---|
| 262 | done in a very inefficient way since the location of the variables and
|
|---|
| 263 | parameters within the stylesheet tree is still done at run time (it really
|
|---|
| 264 | should be done statically at compile time), and I am still unsure that my
|
|---|
| 265 | understanding of the template variables and parameter scope is actually
|
|---|
| 266 | right.</p><p>This part of the documentation is still to be written once this part of
|
|---|
| 267 | the code will be stable. <span style="background-color: #FF0000">TODO</span></p><h3><a name="Extension" id="Extension">Extension support</a></h3><p>There is a separate document explaining <a href="extensions.html">how the
|
|---|
| 268 | extension support works</a>.</p><h3><a name="Futher" id="Futher">Further reading</a></h3><p>Michael Kay wrote <a href="http://www-106.ibm.com/developerworks/library/x-xslt2/?dwzone=x?open&l=132%2ct=gr%2c+p=saxon">a
|
|---|
| 269 | really interesting article on Saxon internals</a> and the work he did on
|
|---|
| 270 | performance issues. I wishes I had read it before starting libxslt design (I
|
|---|
| 271 | would probably have avoided a few mistakes and progressed faster). A lot of
|
|---|
| 272 | the ideas in his papers should be implemented or at least tried in
|
|---|
| 273 | libxslt.</p><p>The <a href="http://xmlsoft.org/">libxml documentation</a>, especially <a href="http://xmlsoft.org/xmlio.html">the I/O interfaces</a> and the <a href="http://xmlsoft.org/xmlmem.html">memory management</a>.</p><h3><a name="TODOs" id="TODOs">TODOs</a></h3><p>redesign the XSLT stack frame handling. Far too much work is done at
|
|---|
| 274 | execution time. Similarly for the attribute value templates handling, at
|
|---|
| 275 | least the embedded subexpressions ought to be precompiled.</p><p>Allow output to be saved to a SAX like output (this notion of SAX like API
|
|---|
| 276 | for output should be added directly to libxml).</p><p>Implement and test some of the optimization explained by Michael Kay
|
|---|
| 277 | especially:</p><ul><li>static slot allocation on the stack frame</li>
|
|---|
| 278 | <li>specific boolean interpretation of an XPath expression</li>
|
|---|
| 279 | <li>some of the sorting optimization</li>
|
|---|
| 280 | <li>Lazy evaluation of location path. (this may require more changes but
|
|---|
| 281 | sounds really interesting. XT does this too.)</li>
|
|---|
| 282 | <li>Optimization of an expression tree (This could be done as a completely
|
|---|
| 283 | independent module.)</li>
|
|---|
| 284 | </ul><p></p><p>Error reporting, there is a lot of case where the XSLT specification
|
|---|
| 285 | specify that a given construct is an error are not checked adequately by
|
|---|
| 286 | libxslt. Basically one should do a complete pass on the XSLT spec again and
|
|---|
| 287 | add all tests to the stylesheet compilation. Using the DTD provided in the
|
|---|
| 288 | appendix and making direct checks using the libxml validation API sounds a
|
|---|
| 289 | good idea too (though one should take care of not raising errors for
|
|---|
| 290 | elements/attributes in different namespaces).</p><p>Double check all the places where the stylesheet compiled form might be
|
|---|
| 291 | modified at run time (extra removal of blanks nodes, hint on the
|
|---|
| 292 | xsltCompMatch).</p><p></p><p><a href="bugs.html">Daniel Veillard</a></p></td></tr></table></td></tr></table></td></tr></table></td></tr></table></td></tr></table></body></html>
|
|---|
