2 * pattern.c: Implemetation of the template match compilation and lookup
5 * http://www.w3.org/TR/1999/REC-xslt-19991116
7 * See Copyright for the status of this software.
9 * Daniel.Veillard@imag.fr
12 #include "xsltconfig.h"
16 #include <libxml/xmlmemory.h>
17 #include <libxml/tree.h>
18 #include <libxml/valid.h>
19 #include <libxml/hash.h>
20 #include <libxml/xmlerror.h>
21 #include <libxml/parserInternals.h>
23 #include "xsltInternals.h"
25 /* #define DEBUG_PARSING */
28 xsltGenericError(xsltGenericErrorContext, \
29 "Unimplemented block at %s:%d\n", \
35 xmlChar *xmlSplitQName2(const xmlChar *name, xmlChar **prefix);
38 * There is no XSLT specific error reporting module yet
40 #define xsltGenericError xmlGenericError
41 #define xsltGenericErrorContext xmlGenericErrorContext
63 typedef struct _xsltStepOp xsltStepOp;
64 typedef xsltStepOp *xsltStepOpPtr;
71 typedef struct _xsltCompMatch xsltCompMatch;
72 typedef xsltCompMatch *xsltCompMatchPtr;
73 struct _xsltCompMatch {
74 struct _xsltCompMatch *next; /* siblings in the name hash */
75 int priority; /* the priority */
76 xsltTemplatePtr template; /* the associated template */
78 /* TODO fix the statically allocated size */
81 xsltStepOp steps[20]; /* ops for computation */
84 typedef struct _xsltParserContext xsltParserContext;
85 typedef xsltParserContext *xsltParserContextPtr;
86 struct _xsltParserContext {
87 const xmlChar *cur; /* the current char being parsed */
88 const xmlChar *base; /* the full expression */
89 int error; /* error code */
90 xsltCompMatchPtr comp; /* the result */
93 /************************************************************************
97 ************************************************************************/
102 * Create a new XSLT CompMatch
104 * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
107 xsltNewCompMatch(void) {
108 xsltCompMatchPtr cur;
110 cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
112 xsltGenericError(xsltGenericErrorContext,
113 "xsltNewCompMatch : malloc failed\n");
116 memset(cur, 0, sizeof(xsltCompMatch));
123 * @comp: an XSLT comp
125 * Free up the memory allocated by @comp
128 xsltFreeCompMatch(xsltCompMatchPtr comp) {
134 for (i = 0;i < comp->nbStep;i++) {
135 op = &comp->steps[i];
136 if (op->value != NULL)
138 if (op->value2 != NULL)
141 memset(comp, -1, sizeof(xsltCompMatch));
146 * xsltFreeCompMatchList:
147 * @comp: an XSLT comp list
149 * Free up the memory allocated by all the elements of @comp
152 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
153 xsltCompMatchPtr cur;
155 while (comp != NULL) {
158 xsltFreeCompMatch(cur);
163 * xsltNewParserContext:
165 * Create a new XSLT ParserContext
167 * Returns the newly allocated xsltParserContextPtr or NULL in case of error
170 xsltNewParserContext(void) {
171 xsltParserContextPtr cur;
173 cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
175 xsltGenericError(xsltGenericErrorContext,
176 "xsltNewParserContext : malloc failed\n");
179 memset(cur, 0, sizeof(xsltParserContext));
184 * xsltFreeParserContext:
185 * @ctxt: an XSLT parser context
187 * Free up the memory allocated by @ctxt
190 xsltFreeParserContext(xsltParserContextPtr ctxt) {
193 memset(ctxt, -1, sizeof(xsltParserContext));
199 * @comp: the compiled match expression
201 * @value: the first value
202 * @value2: the second value
204 * Add an step to an XSLT Compiled Match
206 * Returns -1 in case of failure, 0 otherwise.
209 xsltCompMatchAdd(xsltCompMatchPtr comp, xsltOp op, xmlChar *value,
211 if (comp->nbStep >= 20) {
212 xsltGenericError(xsltGenericErrorContext,
213 "xsltCompMatchAddOp: overflow\n");
216 comp->steps[comp->nbStep].op = op;
217 comp->steps[comp->nbStep].value = value;
218 comp->steps[comp->nbStep].value2 = value2;
224 * xsltReverseCompMatch:
225 * @comp: the compiled match expression
227 * reverse all the stack of expressions
230 xsltReverseCompMatch(xsltCompMatchPtr comp) {
232 int j = comp->nbStep - 1;
235 register xmlChar *tmp;
237 tmp = comp->steps[i].value;
238 comp->steps[i].value = comp->steps[j].value;
239 comp->steps[j].value = tmp;
240 tmp = comp->steps[i].value2;
241 comp->steps[i].value2 = comp->steps[j].value2;
242 comp->steps[j].value2 = tmp;
243 op = comp->steps[i].op;
244 comp->steps[i].op = comp->steps[j].op;
245 comp->steps[j].op = op;
249 comp->steps[comp->nbStep++].op = XSLT_OP_END;
252 /************************************************************************
254 * The interpreter for the precompiled patterns *
256 ************************************************************************/
260 * @comp: the precompiled pattern
263 * Test wether the node matches the pattern
265 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
268 xsltTestCompMatch(xsltCompMatchPtr comp, xmlNodePtr node) {
272 if ((comp == NULL) || (node == NULL)) {
273 xsltGenericError(xsltGenericErrorContext,
274 "xsltTestCompMatch: null arg\n");
277 for (i = 0;i < comp->nbStep;i++) {
278 step = &comp->steps[i];
283 if ((node->type != XML_DOCUMENT_NODE) &&
284 (node->type != XML_HTML_DOCUMENT_NODE))
288 if (node->type != XML_ELEMENT_NODE)
290 if (step->value == NULL)
292 if (!xmlStrEqual(step->value, node->name))
294 /* TODO: Handle namespace ... */
300 if (node->type != XML_ATTRIBUTE_NODE)
302 if (step->value == NULL)
304 if (!xmlStrEqual(step->value, node->name))
306 /* TODO: Handle namespace ... */
312 if (step->value == NULL)
314 if (!xmlStrEqual(step->value, node->name))
316 /* TODO: Handle namespace ... */
318 case XSLT_OP_ANCESTOR:
319 /* TODO: implement coalescing of ANCESTOR/NODE ops */
320 if (step->value == NULL) {
322 step = &comp->steps[i];
323 if (step->op == XSLT_OP_ROOT)
325 if (step->op != XSLT_OP_ELEM)
327 if (step->value == NULL)
333 while (node != NULL) {
336 if (xmlStrEqual(step->value, node->name)) {
337 /* TODO: Handle namespace ... */
345 TODO /* Handle IDs, might be done differently */
348 TODO /* Handle Keys, might be done differently */
351 TODO /* Handle Namespace */
354 TODO /* Handle Namespace */
356 case XSLT_OP_PREDICATE:
357 TODO /* Handle Namespace */
364 /************************************************************************
366 * Dedicated parser for templates *
368 ************************************************************************/
370 #define CUR (*ctxt->cur)
371 #define SKIP(val) ctxt->cur += (val)
372 #define NXT(val) ctxt->cur[(val)]
373 #define CUR_PTR ctxt->cur
375 #define SKIP_BLANKS \
376 while (IS_BLANK(CUR)) NEXT
378 #define CURRENT (*ctxt->cur)
379 #define NEXT ((*ctxt->cur) ? ctxt->cur++: ctxt->cur)
382 #define PUSH(op, val, val2) \
383 if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
387 * @ctxt: the XPath Parser context
389 * Trickery: parse an XML name but without consuming the input flow
390 * Needed to avoid insanity in the parser state.
392 * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
393 * CombiningChar | Extender
395 * [5] Name ::= (Letter | '_' | ':') (NameChar)*
397 * [6] Names ::= Name (S Name)*
399 * Returns the Name parsed or NULL
403 xsltScanName(xsltParserContextPtr ctxt) {
404 xmlChar buf[XML_MAX_NAMELEN];
408 if (!IS_LETTER(CUR) && (CUR != '_') &&
413 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
414 (NXT(len) == '.') || (NXT(len) == '-') ||
415 (NXT(len) == '_') || (NXT(len) == ':') ||
416 (IS_COMBINING(NXT(len))) ||
417 (IS_EXTENDER(NXT(len)))) {
420 if (len >= XML_MAX_NAMELEN) {
421 xmlGenericError(xmlGenericErrorContext,
422 "xmlScanName: reached XML_MAX_NAMELEN limit\n");
423 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
424 (NXT(len) == '.') || (NXT(len) == '-') ||
425 (NXT(len) == '_') || (NXT(len) == ':') ||
426 (IS_COMBINING(NXT(len))) ||
427 (IS_EXTENDER(NXT(len))))
433 return(xmlStrndup(buf, len));
436 * Compile the XSLT LocationPathPattern
437 * [3] IdKeyPattern ::= 'id' '(' Literal ')'
438 * | 'key' '(' Literal ',' Literal ')'
442 * xsltCompileStepPattern:
443 * @comp: the compilation context
444 * @token: a posible precompiled name
446 * Compile the XSLT StepPattern and generates a precompiled
447 * form suitable for fast matching.
449 * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
450 * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
451 * | ('child' | 'attribute') '::'
453 * [7] NodeTest ::= NameTest
455 * | 'processing-instruction' '(' Literal ')'
456 * [8] Predicate ::= '[' PredicateExpr ']'
457 * [9] PredicateExpr ::= Expr
458 * [13] AbbreviatedAxisSpecifier ::= '@'?
459 * [37] NameTest ::= '*' | NCName ':' '*' | QName
463 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
465 if ((token == NULL) && (CUR == '@')) {
466 token = xsltScanName(ctxt);
468 xsltGenericError(xsltGenericErrorContext,
469 "xsltCompilePattern : Name expected\n");
475 token = xsltScanName(ctxt);
477 xsltGenericError(xsltGenericErrorContext,
478 "xsltCompilePattern : Name expected\n");
485 /* if (xmlStrEqual(token, "processing-instruction")) */
486 } else if (CUR == ':') {
488 } else if (CUR == '*') {
491 PUSH(XSLT_OP_ELEM, token, NULL);
503 * xsltCompileRelativePathPattern:
504 * @comp: the compilation context
505 * @token: a posible precompiled name
507 * Compile the XSLT RelativePathPattern and generates a precompiled
508 * form suitable for fast matching.
510 * [4] RelativePathPattern ::= StepPattern
511 * | RelativePathPattern '/' StepPattern
512 * | RelativePathPattern '//' StepPattern
515 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
516 xsltCompileStepPattern(ctxt, token);
520 while ((CUR != 0) && (CUR != '|')) {
521 if ((CUR == '/') && (NXT(1) == '/')) {
522 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
526 xsltCompileStepPattern(ctxt, NULL);
527 } else if (CUR == '/') {
528 PUSH(XSLT_OP_PARENT, NULL, NULL);
531 if ((CUR != 0) || (CUR == '|')) {
532 xsltCompileRelativePathPattern(ctxt, NULL);
546 * xsltCompileLocationPathPattern:
547 * @comp: the compilation context
549 * Compile the XSLT LocationPathPattern and generates a precompiled
550 * form suitable for fast matching.
552 * [2] LocationPathPattern ::= '/' RelativePathPattern?
553 * | IdKeyPattern (('/' | '//') RelativePathPattern)?
554 * | '//'? RelativePathPattern
557 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
559 if ((CUR == '/') && (NXT(1) == '/')) {
561 * since we reverse the query
562 * a leading // can be safely ignored
566 xsltCompileRelativePathPattern(ctxt, NULL);
567 } else if (CUR == '/') {
569 * We need to find root as the parent
573 PUSH(XSLT_OP_ROOT, NULL, NULL);
574 if ((CUR != 0) || (CUR == '|')) {
575 PUSH(XSLT_OP_PARENT, NULL, NULL);
576 xsltCompileRelativePathPattern(ctxt, NULL);
580 name = xsltScanName(ctxt);
582 xsltGenericError(xsltGenericErrorContext,
583 "xsltCompilePattern : Name expected\n");
591 xsltCompileRelativePathPattern(ctxt, name);
598 * xsltCompilePattern:
599 * @pattern an XSLT pattern
601 * Compile the XSLT pattern and generates a precompiled form suitable
603 * Note that the splitting as union of patterns is expected to be handled
606 * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
608 * Returns the generated xsltCompMatchPtr or NULL in case of failure
612 xsltCompilePattern(const xmlChar *pattern) {
613 xsltParserContextPtr ctxt;
614 xsltCompMatchPtr ret;
617 if (pattern == NULL) {
618 xsltGenericError(xsltGenericErrorContext,
619 "xsltCompilePattern : NULL pattern\n");
624 xsltGenericError(xsltGenericErrorContext,
625 "xsltCompilePattern : parsing '%s'\n", pattern);
629 while (IS_BLANK(*cur)) cur++;
631 xsltGenericError(xsltGenericErrorContext,
632 "xsltCompilePattern : NULL pattern\n");
635 ctxt = xsltNewParserContext();
638 ret = xsltNewCompMatch();
640 xsltFreeParserContext(ctxt);
645 ctxt->base = pattern;
647 xsltCompileLocationPathPattern(ctxt);
652 * Reverse for faster interpretation.
654 xsltReverseCompMatch(ret);
656 xsltFreeParserContext(ctxt);
660 xsltFreeParserContext(ctxt);
661 xsltFreeCompMatch(ret);
667 /************************************************************************
669 * Module interfaces *
671 ************************************************************************/
675 * @style: an XSLT stylesheet
676 * @cur: an XSLT template
678 * Register the XSLT pattern associated to @cur
680 * Returns -1 in case of error, 0 otherwise
683 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur) {
684 xsltCompMatchPtr pat, list;
688 * get a compiled form of the pattern
690 /* TODO : handle | in patterns as multple pat !!! */
691 pat = xsltCompilePattern(cur->match);
695 if (cur->priority != XSLT_PAT_NO_PRIORITY)
696 pat->priority = cur->priority;
699 * insert it in the hash table list corresponding to its lookup name
701 switch (pat->steps[0].op) {
706 case XSLT_OP_ANCESTOR:
710 name = pat->steps[0].value;
713 name = (const xmlChar *) "/";
716 name = (const xmlChar *) "*";
719 case XSLT_OP_PREDICATE:
720 xsltGenericError(xsltGenericErrorContext,
721 "xsltAddTemplate: invalid compiled pattern\n");
722 xsltFreeCompMatch(pat);
726 xsltGenericError(xsltGenericErrorContext,
727 "xsltAddTemplate: invalid compiled pattern\n");
728 xsltFreeCompMatch(pat);
731 if (style->templatesHash == NULL) {
732 style->templatesHash = xmlHashCreate(0);
733 if (style->templatesHash == NULL) {
734 xsltFreeCompMatch(pat);
738 xsltGenericError(xsltGenericErrorContext,
739 "xsltAddTemplate: created template hash\n");
741 xmlHashAddEntry(style->templatesHash, name, pat);
743 xsltGenericError(xsltGenericErrorContext,
744 "xsltAddTemplate: added new hash %s\n", name);
747 list = (xsltCompMatchPtr) xmlHashLookup(style->templatesHash, name);
749 xmlHashAddEntry(style->templatesHash, name, pat);
751 xsltGenericError(xsltGenericErrorContext,
752 "xsltAddTemplate: added new hash %s\n", name);
756 * Note '<=' since one must choose among the matching template
757 * rules that are left, the one that occurs last in the stylesheet
759 if (list->priority <= pat->priority) {
761 xmlHashUpdateEntry(style->templatesHash, name, pat, NULL);
763 xsltGenericError(xsltGenericErrorContext,
764 "xsltAddTemplate: added head hash for %s\n", name);
767 while (list->next != NULL) {
768 if (list->next->priority <= pat->priority)
771 pat->next = list->next;
781 * @style: an XSLT stylesheet
784 * Finds the template applying to this node
786 * Returns the xsltTemplatePtr or NULL if not found
789 xsltGetTemplate(xsltStylesheetPtr style, xmlNodePtr node) {
791 xsltCompMatchPtr list;
793 if ((style == NULL) || (node == NULL))
796 /* TODO : handle IDs/keys here ! */
797 if (style->templatesHash == NULL)
801 * Use a name as selector
803 switch (node->type) {
804 case XML_ELEMENT_NODE:
805 case XML_ATTRIBUTE_NODE:
809 case XML_DOCUMENT_NODE:
810 case XML_HTML_DOCUMENT_NODE:
811 name = (const xmlChar *)"/";
814 case XML_CDATA_SECTION_NODE:
815 case XML_ENTITY_REF_NODE:
816 case XML_ENTITY_NODE:
817 case XML_COMMENT_NODE:
818 case XML_DOCUMENT_TYPE_NODE:
819 case XML_DOCUMENT_FRAG_NODE:
820 case XML_NOTATION_NODE:
822 case XML_ELEMENT_DECL:
823 case XML_ATTRIBUTE_DECL:
824 case XML_ENTITY_DECL:
825 case XML_NAMESPACE_DECL:
826 case XML_XINCLUDE_START:
827 case XML_XINCLUDE_END:
837 * find the list of appliable expressions based on the name
839 list = (xsltCompMatchPtr) xmlHashLookup(style->templatesHash, name);
841 #ifdef DEBUG_MATCHING
842 xsltGenericError(xsltGenericErrorContext,
843 "xsltGetTemplate: empty set for %s\n", name);
847 while (list != NULL) {
848 if (xsltTestCompMatch(list, node))
849 return(list->template);
858 * xsltFreeTemplateHashes:
859 * @style: an XSLT stylesheet
861 * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
864 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
865 if (style->templatesHash != NULL)
866 xmlHashFree((xmlHashTablePtr) style->templatesHash,
867 (xmlHashDeallocator) xsltFreeCompMatchList);