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
13 * TODO: handle pathological cases like *[*[@a="b"]]
14 * TODO: detect [number] at compilation, optimize accordingly
17 #include "xsltconfig.h"
21 #include <libxml/xmlmemory.h>
22 #include <libxml/tree.h>
23 #include <libxml/valid.h>
24 #include <libxml/hash.h>
25 #include <libxml/xmlerror.h>
26 #include <libxml/parserInternals.h>
28 #include "xsltInternals.h"
29 #include "xsltutils.h"
31 #include "templates.h"
61 typedef struct _xsltStepOp xsltStepOp;
62 typedef xsltStepOp *xsltStepOpPtr;
68 xmlXPathCompExprPtr comp;
70 * Optimisations for count
77 struct _xsltCompMatch {
78 struct _xsltCompMatch *next; /* siblings in the name hash */
79 float priority; /* the priority */
80 const xmlChar *mode; /* the mode */
81 const xmlChar *modeURI; /* the mode URI */
82 xsltTemplatePtr template; /* the associated template */
84 /* TODO fix the statically allocated size steps[] */
87 xsltStepOp steps[20]; /* ops for computation */
90 typedef struct _xsltParserContext xsltParserContext;
91 typedef xsltParserContext *xsltParserContextPtr;
92 struct _xsltParserContext {
93 const xmlChar *cur; /* the current char being parsed */
94 const xmlChar *base; /* the full expression */
95 xmlDocPtr doc; /* the source document */
96 xmlNodePtr elem; /* the source element */
97 int error; /* error code */
98 xsltCompMatchPtr comp; /* the result */
101 /************************************************************************
105 ************************************************************************/
110 * Create a new XSLT CompMatch
112 * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
114 static xsltCompMatchPtr
115 xsltNewCompMatch(void) {
116 xsltCompMatchPtr cur;
118 cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
120 xsltGenericError(xsltGenericErrorContext,
121 "xsltNewCompMatch : malloc failed\n");
124 memset(cur, 0, sizeof(xsltCompMatch));
131 * @comp: an XSLT comp
133 * Free up the memory allocated by @comp
136 xsltFreeCompMatch(xsltCompMatchPtr comp) {
142 if (comp->mode != NULL)
143 xmlFree((xmlChar *)comp->mode);
144 if (comp->modeURI != NULL)
145 xmlFree((xmlChar *)comp->modeURI);
146 for (i = 0;i < comp->nbStep;i++) {
147 op = &comp->steps[i];
148 if (op->value != NULL)
150 if (op->value2 != NULL)
152 if (op->value3 != NULL)
154 if (op->comp != NULL)
155 xmlXPathFreeCompExpr(op->comp);
157 memset(comp, -1, sizeof(xsltCompMatch));
162 * xsltFreeCompMatchList:
163 * @comp: an XSLT comp list
165 * Free up the memory allocated by all the elements of @comp
168 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
169 xsltCompMatchPtr cur;
171 while (comp != NULL) {
174 xsltFreeCompMatch(cur);
179 * xsltNewParserContext:
181 * Create a new XSLT ParserContext
183 * Returns the newly allocated xsltParserContextPtr or NULL in case of error
185 static xsltParserContextPtr
186 xsltNewParserContext(void) {
187 xsltParserContextPtr cur;
189 cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
191 xsltGenericError(xsltGenericErrorContext,
192 "xsltNewParserContext : malloc failed\n");
195 memset(cur, 0, sizeof(xsltParserContext));
200 * xsltFreeParserContext:
201 * @ctxt: an XSLT parser context
203 * Free up the memory allocated by @ctxt
206 xsltFreeParserContext(xsltParserContextPtr ctxt) {
209 memset(ctxt, -1, sizeof(xsltParserContext));
215 * @comp: the compiled match expression
217 * @value: the first value
218 * @value2: the second value
220 * Add an step to an XSLT Compiled Match
222 * Returns -1 in case of failure, 0 otherwise.
225 xsltCompMatchAdd(xsltCompMatchPtr comp, xsltOp op, xmlChar *value,
227 if (comp->nbStep >= 20) {
228 xsltGenericError(xsltGenericErrorContext,
229 "xsltCompMatchAddOp: overflow\n");
232 comp->steps[comp->nbStep].op = op;
233 comp->steps[comp->nbStep].value = value;
234 comp->steps[comp->nbStep].value2 = value2;
240 * xsltSwapTopCompMatch:
241 * @comp: the compiled match expression
243 * reverse the two top steps.
246 xsltSwapTopCompMatch(xsltCompMatchPtr comp) {
248 int j = comp->nbStep - 1;
251 register xmlChar *tmp;
254 tmp = comp->steps[i].value;
255 comp->steps[i].value = comp->steps[j].value;
256 comp->steps[j].value = tmp;
257 tmp = comp->steps[i].value2;
258 comp->steps[i].value2 = comp->steps[j].value2;
259 comp->steps[j].value2 = tmp;
260 op = comp->steps[i].op;
261 comp->steps[i].op = comp->steps[j].op;
262 comp->steps[j].op = op;
267 * xsltReverseCompMatch:
268 * @comp: the compiled match expression
270 * reverse all the stack of expressions
273 xsltReverseCompMatch(xsltCompMatchPtr comp) {
275 int j = comp->nbStep - 1;
278 register xmlChar *tmp;
280 tmp = comp->steps[i].value;
281 comp->steps[i].value = comp->steps[j].value;
282 comp->steps[j].value = tmp;
283 tmp = comp->steps[i].value2;
284 comp->steps[i].value2 = comp->steps[j].value2;
285 comp->steps[j].value2 = tmp;
286 op = comp->steps[i].op;
287 comp->steps[i].op = comp->steps[j].op;
288 comp->steps[j].op = op;
292 comp->steps[comp->nbStep++].op = XSLT_OP_END;
296 * xsltCleanupCompMatch:
297 * @comp: the compiled match expression
299 * remove all computation state from the pattern
302 xsltCleanupCompMatch(xsltCompMatchPtr comp) {
305 for (i = 0;i < comp->nbStep;i++) {
306 comp->steps[i].previous = NULL;
310 /************************************************************************
312 * The interpreter for the precompiled patterns *
314 ************************************************************************/
318 * @ctxt: a XSLT process context
319 * @comp: the precompiled pattern
321 * @mode: the mode name or NULL
322 * @modeURI: the mode URI or NULL
324 * Test wether the node matches the pattern
326 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
329 xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
330 xmlNodePtr node, const xmlChar *mode,
331 const xmlChar *modeURI) {
333 xsltStepOpPtr step, select = NULL;
335 if ((comp == NULL) || (node == NULL) || (ctxt == NULL)) {
336 xsltGenericError(xsltGenericErrorContext,
337 "xsltTestCompMatch: null arg\n");
341 if (comp->mode == NULL)
343 if ((comp->mode != mode) && (!xmlStrEqual(comp->mode, mode)))
346 if (comp->mode != NULL)
349 if (modeURI != NULL) {
350 if (comp->modeURI == NULL)
352 if ((comp->modeURI != modeURI) &&
353 (!xmlStrEqual(comp->modeURI, modeURI)))
356 if (comp->modeURI != NULL)
359 for (i = 0;i < comp->nbStep;i++) {
360 step = &comp->steps[i];
361 if (step->op != XSLT_OP_PREDICATE)
367 if ((node->type == XML_DOCUMENT_NODE) ||
368 (node->type == XML_HTML_DOCUMENT_NODE))
372 if (node->type != XML_ELEMENT_NODE)
374 if (step->value == NULL)
376 if (!xmlStrEqual(step->value, node->name))
380 if (node->ns == NULL) {
381 if (step->value2 != NULL)
383 } else if (node->ns->href != NULL) {
384 if (step->value2 == NULL)
386 if (!xmlStrEqual(step->value2, node->ns->href))
391 TODO /* Handle OP_CHILD */
394 if (node->type != XML_ATTRIBUTE_NODE)
396 if (step->value == NULL)
398 if (!xmlStrEqual(step->value, node->name))
402 if (node->ns == NULL) {
403 if (step->value2 != NULL)
405 } else if (node->ns->href != NULL) {
406 if (step->value2 == NULL)
408 if (!xmlStrEqual(step->value2, node->ns->href))
416 if (step->value == NULL)
418 if (!xmlStrEqual(step->value, node->name))
421 if (node->ns == NULL) {
422 if (step->value2 != NULL)
424 } else if (node->ns->href != NULL) {
425 if (step->value2 == NULL)
427 if (!xmlStrEqual(step->value2, node->ns->href))
431 case XSLT_OP_ANCESTOR:
432 /* TODO: implement coalescing of ANCESTOR/NODE ops */
433 if (step->value == NULL) {
435 step = &comp->steps[i];
436 if (step->op == XSLT_OP_ROOT)
438 if (step->op != XSLT_OP_ELEM)
440 if (step->value == NULL)
446 while (node != NULL) {
449 if (xmlStrEqual(step->value, node->name)) {
451 if (node->ns == NULL) {
452 if (step->value2 == NULL)
454 } else if (node->ns->href != NULL) {
455 if ((step->value2 != NULL) &&
456 (xmlStrEqual(step->value2, node->ns->href)))
466 /* TODO Handle IDs decently, must be done differently */
469 id = xmlGetID(node->doc, step->value);
470 if ((id == NULL) || (id->parent != node))
478 list = xsltGetKey(ctxt, step->value,
479 step->value3, step->value2);
482 for (indx = 0;indx < list->nodeNr;indx++)
483 if (list->nodeTab[indx] == node)
485 if (indx >= list->nodeNr)
491 if (node->ns == NULL) {
492 if (step->value != NULL)
494 } else if (node->ns->href != NULL) {
495 if (step->value == NULL)
497 if (!xmlStrEqual(step->value, node->ns->href))
502 switch (node->type) {
503 case XML_DOCUMENT_NODE:
504 case XML_HTML_DOCUMENT_NODE:
505 case XML_ELEMENT_NODE:
511 case XSLT_OP_PREDICATE: {
514 int pos = 0, len = 0;
516 * Depending on the last selection, one may need to
517 * recompute contextSize and proximityPosition.
519 oldCS = ctxt->xpathCtxt->contextSize;
520 oldCP = ctxt->xpathCtxt->proximityPosition;
521 if ((select != NULL) &&
522 (select->op == XSLT_OP_ELEM) &&
523 (select->value != NULL) &&
524 (node->type == XML_ELEMENT_NODE) &&
525 (node->parent != NULL)) {
527 if ((select->previous != NULL) &&
528 (select->previous->parent == node->parent)) {
530 * just walk back to adjust the index
533 xmlNodePtr sibling = node;
535 while (sibling != NULL) {
536 if (sibling == select->previous)
538 if (xmlStrEqual(node->name, sibling->name)) {
539 if ((select->value2 == NULL) ||
540 ((sibling->ns != NULL) &&
541 (xmlStrEqual(select->value2,
542 sibling->ns->href))))
545 sibling = sibling->prev;
547 if (sibling == NULL) {
548 /* hum going backward in document order ... */
551 while (sibling != NULL) {
552 if (sibling == select->previous)
554 if ((select->value2 == NULL) ||
555 ((sibling->ns != NULL) &&
556 (xmlStrEqual(select->value2,
557 sibling->ns->href))))
559 sibling = sibling->next;
562 if (sibling != NULL) {
563 pos = select->index + indx;
565 select->previous = node;
571 * recompute the index
573 xmlNodePtr siblings = node->parent->children;
575 while (siblings != NULL) {
576 if (siblings->type == XML_ELEMENT_NODE) {
577 if (siblings == node) {
580 } else if (xmlStrEqual(node->name,
582 if ((select->value2 == NULL) ||
583 ((siblings->ns != NULL) &&
584 (xmlStrEqual(select->value2,
585 siblings->ns->href))))
589 siblings = siblings->next;
593 ctxt->xpathCtxt->contextSize = len;
594 ctxt->xpathCtxt->proximityPosition = pos;
595 select->previous = node;
599 } else if ((select != NULL) && (select->op == XSLT_OP_ALL)) {
600 if ((select->previous != NULL) &&
601 (select->previous->parent == node->parent)) {
603 * just walk back to adjust the index
606 xmlNodePtr sibling = node;
608 while (sibling != NULL) {
609 if (sibling == select->previous)
611 if (sibling->type == XML_ELEMENT_NODE)
613 sibling = sibling->prev;
615 if (sibling == NULL) {
616 /* hum going backward in document order ... */
619 while (sibling != NULL) {
620 if (sibling == select->previous)
622 if (sibling->type == XML_ELEMENT_NODE)
624 sibling = sibling->next;
627 if (sibling != NULL) {
628 pos = select->index + indx;
630 select->previous = node;
636 * recompute the index
638 xmlNodePtr siblings = node->parent->children;
640 while (siblings != NULL) {
641 if (siblings->type == XML_ELEMENT_NODE) {
643 if (siblings == node) {
647 siblings = siblings->next;
651 ctxt->xpathCtxt->contextSize = len;
652 ctxt->xpathCtxt->proximityPosition = pos;
653 select->previous = node;
658 oldNode = ctxt->node;
661 if (step->value == NULL)
664 if (step->comp == NULL) {
665 step->comp = xmlXPathCompile(step->value);
666 if (step->comp == NULL)
669 if (!xsltEvalXPathPredicate(ctxt, step->comp))
673 ctxt->xpathCtxt->contextSize = oldCS;
674 ctxt->xpathCtxt->proximityPosition = oldCP;
676 ctxt->node = oldNode;
680 ctxt->xpathCtxt->contextSize = oldCS;
681 ctxt->xpathCtxt->proximityPosition = oldCP;
683 ctxt->node = oldNode;
687 if (node->type != XML_PI_NODE)
689 if (step->value != NULL) {
690 if (!xmlStrEqual(step->value, node->name))
694 case XSLT_OP_COMMENT:
695 if (node->type != XML_COMMENT_NODE)
699 if ((node->type != XML_TEXT_NODE) &&
700 (node->type != XML_CDATA_SECTION_NODE))
704 switch (node->type) {
705 case XML_DOCUMENT_NODE:
706 case XML_HTML_DOCUMENT_NODE:
707 case XML_ELEMENT_NODE:
708 case XML_CDATA_SECTION_NODE:
710 case XML_COMMENT_NODE:
712 case XML_ATTRIBUTE_NODE:
724 * xsltTestCompMatchList:
725 * @ctxt: a XSLT process context
727 * @comp: the precompiled pattern list
729 * Test wether the node matches one of the patterns in the list
731 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
734 xsltTestCompMatchList(xsltTransformContextPtr ctxt, xmlNodePtr node,
735 xsltCompMatchPtr comp) {
738 if ((ctxt == NULL) || (node == NULL))
740 while (comp != NULL) {
741 ret = xsltTestCompMatch(ctxt, comp, node, NULL, NULL);
749 /************************************************************************
751 * Dedicated parser for templates *
753 ************************************************************************/
755 #define CUR (*ctxt->cur)
756 #define SKIP(val) ctxt->cur += (val)
757 #define NXT(val) ctxt->cur[(val)]
758 #define CUR_PTR ctxt->cur
760 #define SKIP_BLANKS \
761 while (IS_BLANK(CUR)) NEXT
763 #define CURRENT (*ctxt->cur)
764 #define NEXT ((*ctxt->cur) ? ctxt->cur++: ctxt->cur)
767 #define PUSH(op, val, val2) \
768 if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
771 xsltSwapTopCompMatch(ctxt->comp);
773 #define XSLT_ERROR(X) \
774 { xsltError(ctxt, __FILE__, __LINE__, X); \
775 ctxt->error = (X); return; }
777 #define XSLT_ERROR0(X) \
778 { xsltError(ctxt, __FILE__, __LINE__, X); \
779 ctxt->error = (X); return(0); }
783 * @ctxt: the XPath Parser context
785 * Parse an XPath Litteral:
787 * [29] Literal ::= '"' [^"]* '"'
790 * Returns the Literal parsed or NULL
794 xsltScanLiteral(xsltParserContextPtr ctxt) {
802 while ((IS_CHAR(CUR)) && (CUR != '"'))
805 /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
809 ret = xmlStrndup(q, CUR_PTR - q);
812 } else if (CUR == '\'') {
815 while ((IS_CHAR(CUR)) && (CUR != '\''))
818 /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
822 ret = xmlStrndup(q, CUR_PTR - q);
826 /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
835 * @ctxt: the XPath Parser context
837 * Trickery: parse an XML name but without consuming the input flow
838 * Needed to avoid insanity in the parser state.
840 * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
841 * CombiningChar | Extender
843 * [5] Name ::= (Letter | '_' | ':') (NameChar)*
845 * [6] Names ::= Name (S Name)*
847 * Returns the Name parsed or NULL
851 xsltScanName(xsltParserContextPtr ctxt) {
852 xmlChar buf[XML_MAX_NAMELEN];
856 if (!IS_LETTER(CUR) && (CUR != '_') &&
861 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
862 (NXT(len) == '.') || (NXT(len) == '-') ||
863 (NXT(len) == '_') || (NXT(len) == ':') ||
864 (IS_COMBINING(NXT(len))) ||
865 (IS_EXTENDER(NXT(len)))) {
868 if (len >= XML_MAX_NAMELEN) {
869 xmlGenericError(xmlGenericErrorContext,
870 "xmlScanName: reached XML_MAX_NAMELEN limit\n");
871 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
872 (NXT(len) == '.') || (NXT(len) == '-') ||
873 (NXT(len) == '_') || (NXT(len) == ':') ||
874 (IS_COMBINING(NXT(len))) ||
875 (IS_EXTENDER(NXT(len))))
881 return(xmlStrndup(buf, len));
884 * xsltCompileIdKeyPattern:
885 * @comp: the compilation context
886 * @name: a preparsed name
887 * @aid: whether id/key are allowed there
889 * Compile the XSLT LocationIdKeyPattern
890 * [3] IdKeyPattern ::= 'id' '(' Literal ')'
891 * | 'key' '(' Literal ',' Literal ')'
893 * also handle NodeType and PI from:
895 * [7] NodeTest ::= NameTest
897 * | 'processing-instruction' '(' Literal ')'
900 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
902 xmlChar *lit2 = NULL;
905 xsltGenericError(xsltGenericErrorContext,
906 "xsltCompileIdKeyPattern : ( expected\n");
910 if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
913 lit = xsltScanLiteral(ctxt);
918 xsltGenericError(xsltGenericErrorContext,
919 "xsltCompileIdKeyPattern : ) expected\n");
924 PUSH(XSLT_OP_ID, lit, NULL);
925 } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
928 lit = xsltScanLiteral(ctxt);
933 xsltGenericError(xsltGenericErrorContext,
934 "xsltCompileIdKeyPattern : , expected\n");
940 lit2 = xsltScanLiteral(ctxt);
945 xsltGenericError(xsltGenericErrorContext,
946 "xsltCompileIdKeyPattern : ) expected\n");
951 /* TODO: support namespace in keys */
952 PUSH(XSLT_OP_KEY, lit, lit2);
953 } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
957 lit = xsltScanLiteral(ctxt);
962 xsltGenericError(xsltGenericErrorContext,
963 "xsltCompileIdKeyPattern : ) expected\n");
969 PUSH(XSLT_OP_PI, lit, NULL);
970 } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
974 xsltGenericError(xsltGenericErrorContext,
975 "xsltCompileIdKeyPattern : ) expected\n");
980 PUSH(XSLT_OP_TEXT, NULL, NULL);
981 } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
985 xsltGenericError(xsltGenericErrorContext,
986 "xsltCompileIdKeyPattern : ) expected\n");
991 PUSH(XSLT_OP_COMMENT, NULL, NULL);
992 } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
996 xsltGenericError(xsltGenericErrorContext,
997 "xsltCompileIdKeyPattern : ) expected\n");
1002 PUSH(XSLT_OP_NODE, NULL, NULL);
1004 xsltGenericError(xsltGenericErrorContext,
1005 "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
1009 xsltGenericError(xsltGenericErrorContext,
1010 "xsltCompileIdKeyPattern : node type\n");
1020 * xsltCompileStepPattern:
1021 * @comp: the compilation context
1022 * @token: a posible precompiled name
1024 * Compile the XSLT StepPattern and generates a precompiled
1025 * form suitable for fast matching.
1027 * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
1028 * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
1029 * | ('child' | 'attribute') '::'
1031 * [7] NodeTest ::= NameTest
1032 * | NodeType '(' ')'
1033 * | 'processing-instruction' '(' Literal ')'
1034 * [8] Predicate ::= '[' PredicateExpr ']'
1035 * [9] PredicateExpr ::= Expr
1036 * [13] AbbreviatedAxisSpecifier ::= '@'?
1037 * [37] NameTest ::= '*' | NCName ':' '*' | QName
1041 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1042 xmlChar *name = NULL;
1043 xmlChar *prefix = NULL;
1044 xmlChar *ncname = NULL;
1045 xmlChar *URL = NULL;
1049 if ((token == NULL) && (CUR == '@')) {
1053 PUSH(XSLT_OP_ATTR, NULL, NULL);
1056 token = xsltScanName(ctxt);
1057 if (token == NULL) {
1058 xsltGenericError(xsltGenericErrorContext,
1059 "xsltCompileStepPattern : Name expected\n");
1063 PUSH(XSLT_OP_ATTR, token, NULL);
1067 token = xsltScanName(ctxt);
1068 if (token == NULL) {
1071 PUSH(XSLT_OP_ALL, token, NULL);
1072 goto parse_predicate;
1074 xsltGenericError(xsltGenericErrorContext,
1075 "xsltCompileStepPattern : Name expected\n");
1084 xsltCompileIdKeyPattern(ctxt, token, 0);
1087 } else if (CUR == ':') {
1089 if (NXT(1) != ':') {
1090 xsltGenericError(xsltGenericErrorContext,
1091 "xsltCompileStepPattern : sequence '::' expected\n");
1096 if (xmlStrEqual(token, (const xmlChar *) "child")) {
1097 name = xsltScanName(ctxt);
1099 xsltGenericError(xsltGenericErrorContext,
1100 "xsltCompileStepPattern : QName expected\n");
1104 ncname = xmlSplitQName2(name, &prefix);
1105 if (ncname != NULL) {
1106 if (prefix != NULL) {
1109 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1111 xsltGenericError(xsltGenericErrorContext,
1112 "xsl: pattern, no namespace bound to prefix %s\n",
1115 URL = xmlStrdup(ns->href);
1122 PUSH(XSLT_OP_CHILD, name, URL);
1123 } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
1124 name = xsltScanName(ctxt);
1126 xsltGenericError(xsltGenericErrorContext,
1127 "xsltCompileStepPattern : QName expected\n");
1131 ncname = xmlSplitQName2(name, &prefix);
1132 if (ncname != NULL) {
1133 if (prefix != NULL) {
1136 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1138 xsltGenericError(xsltGenericErrorContext,
1139 "xsl: pattern, no namespace bound to prefix %s\n",
1142 URL = xmlStrdup(ns->href);
1149 PUSH(XSLT_OP_ATTR, name, URL);
1151 xsltGenericError(xsltGenericErrorContext,
1152 "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
1157 } else if (CUR == '*') {
1159 PUSH(XSLT_OP_ALL, token, NULL);
1161 ncname = xmlSplitQName2(token, &prefix);
1162 if (ncname != NULL) {
1163 if (prefix != NULL) {
1166 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1168 xsltGenericError(xsltGenericErrorContext,
1169 "xsl: pattern, no namespace bound to prefix %s\n",
1172 URL = xmlStrdup(ns->href);
1179 PUSH(XSLT_OP_ELEM, token, URL);
1184 while (CUR == '[') {
1186 xmlChar *ret = NULL;
1191 /* TODO: avoid breaking in strings ... */
1192 while (IS_CHAR(CUR)) {
1193 /* Skip over nested predicates */
1203 if (!IS_CHAR(CUR)) {
1204 xsltGenericError(xsltGenericErrorContext,
1205 "xsltCompileStepPattern : ']' expected\n");
1209 ret = xmlStrndup(q, CUR_PTR - q);
1210 PUSH(XSLT_OP_PREDICATE, ret, NULL);
1211 /* push the predicate lower than local test */
1224 * xsltCompileRelativePathPattern:
1225 * @comp: the compilation context
1226 * @token: a posible precompiled name
1228 * Compile the XSLT RelativePathPattern and generates a precompiled
1229 * form suitable for fast matching.
1231 * [4] RelativePathPattern ::= StepPattern
1232 * | RelativePathPattern '/' StepPattern
1233 * | RelativePathPattern '//' StepPattern
1236 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1237 xsltCompileStepPattern(ctxt, token);
1241 while ((CUR != 0) && (CUR != '|')) {
1242 if ((CUR == '/') && (NXT(1) == '/')) {
1243 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1247 xsltCompileStepPattern(ctxt, NULL);
1248 } else if (CUR == '/') {
1249 PUSH(XSLT_OP_PARENT, NULL, NULL);
1252 if ((CUR != 0) || (CUR == '|')) {
1253 xsltCompileRelativePathPattern(ctxt, NULL);
1267 * xsltCompileLocationPathPattern:
1268 * @comp: the compilation context
1270 * Compile the XSLT LocationPathPattern and generates a precompiled
1271 * form suitable for fast matching.
1273 * [2] LocationPathPattern ::= '/' RelativePathPattern?
1274 * | IdKeyPattern (('/' | '//') RelativePathPattern)?
1275 * | '//'? RelativePathPattern
1278 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1280 if ((CUR == '/') && (NXT(1) == '/')) {
1282 * since we reverse the query
1283 * a leading // can be safely ignored
1287 xsltCompileRelativePathPattern(ctxt, NULL);
1288 } else if (CUR == '/') {
1290 * We need to find root as the parent
1294 PUSH(XSLT_OP_ROOT, NULL, NULL);
1295 if ((CUR != 0) || (CUR == '|')) {
1296 PUSH(XSLT_OP_PARENT, NULL, NULL);
1297 xsltCompileRelativePathPattern(ctxt, NULL);
1299 } else if (CUR == '*') {
1300 xsltCompileRelativePathPattern(ctxt, NULL);
1301 } else if (CUR == '@') {
1302 xsltCompileRelativePathPattern(ctxt, NULL);
1305 name = xsltScanName(ctxt);
1307 xsltGenericError(xsltGenericErrorContext,
1308 "xsltCompileLocationPathPattern : Name expected\n");
1313 if ((CUR == '(') && !xmlXPathIsNodeType(name)) {
1314 xsltCompileIdKeyPattern(ctxt, name, 1);
1315 if ((CUR == '/') && (NXT(1) == '/')) {
1316 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1320 xsltCompileRelativePathPattern(ctxt, NULL);
1321 } else if (CUR == '/') {
1322 PUSH(XSLT_OP_PARENT, NULL, NULL);
1325 xsltCompileRelativePathPattern(ctxt, NULL);
1329 xsltCompileRelativePathPattern(ctxt, name);
1336 * xsltCompilePattern:
1337 * @pattern an XSLT pattern
1338 * @doc: the containing document
1339 * @node: the containing element
1341 * Compile the XSLT pattern and generates a list of precompiled form suitable
1342 * for fast matching.
1344 * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1346 * Returns the generated pattern list or NULL in case of failure
1350 xsltCompilePattern(const xmlChar *pattern, xmlDocPtr doc, xmlNodePtr node) {
1351 xsltParserContextPtr ctxt = NULL;
1352 xsltCompMatchPtr element, first = NULL, previous = NULL;
1353 int current, start, end;
1355 if (pattern == NULL) {
1356 xsltGenericError(xsltGenericErrorContext,
1357 "xsltCompilePattern : NULL pattern\n");
1361 #ifdef DEBUG_PATTERN
1362 xsltGenericDebug(xsltGenericDebugContext,
1363 "xsltCompilePattern : parsing '%s'\n", pattern);
1366 ctxt = xsltNewParserContext();
1372 while (pattern[current] != 0) {
1374 while (IS_BLANK(pattern[current]))
1377 while ((pattern[end] != 0) && (pattern[end] != '|'))
1379 if (current == end) {
1380 xsltGenericError(xsltGenericErrorContext,
1381 "xsltCompilePattern : NULL pattern\n");
1384 element = xsltNewCompMatch();
1385 if (element == NULL) {
1390 else if (previous != NULL)
1391 previous->next = element;
1394 ctxt->comp = element;
1395 ctxt->base = xmlStrndup(&pattern[start], end - start);
1396 ctxt->cur = &(ctxt->base)[current - start];
1397 xsltCompileLocationPathPattern(ctxt);
1399 xmlFree((xmlChar *)ctxt->base);
1404 * Reverse for faster interpretation.
1406 xsltReverseCompMatch(element);
1409 * Set-up the priority
1411 if (((element->steps[0].op == XSLT_OP_ELEM) ||
1412 (element->steps[0].op == XSLT_OP_ATTR)) &&
1413 (element->steps[0].value != NULL) &&
1414 (element->steps[1].op == XSLT_OP_END)) {
1415 element->priority = 0;
1416 } else if ((element->steps[0].op == XSLT_OP_ROOT) &&
1417 (element->steps[1].op == XSLT_OP_END)) {
1418 element->priority = 0;
1419 } else if ((element->steps[0].op == XSLT_OP_PI) &&
1420 (element->steps[0].value != NULL) &&
1421 (element->steps[1].op == XSLT_OP_END)) {
1422 element->priority = 0;
1423 } else if ((element->steps[0].op == XSLT_OP_NS) &&
1424 (element->steps[0].value != NULL) &&
1425 (element->steps[1].op == XSLT_OP_END)) {
1426 element->priority = -0.25;
1427 } else if (((element->steps[0].op == XSLT_OP_PI) ||
1428 (element->steps[0].op == XSLT_OP_TEXT) ||
1429 (element->steps[0].op == XSLT_OP_ALL) ||
1430 (element->steps[0].op == XSLT_OP_NODE) ||
1431 (element->steps[0].op == XSLT_OP_COMMENT)) &&
1432 (element->steps[1].op == XSLT_OP_END)) {
1433 element->priority = -0.5;
1435 element->priority = 0.5;
1437 if (pattern[end] == '|')
1442 xsltGenericError(xsltGenericErrorContext,
1443 "xsltCompilePattern : NULL pattern\n");
1447 xsltFreeParserContext(ctxt);
1452 xsltFreeParserContext(ctxt);
1454 xsltFreeCompMatchList(first);
1458 /************************************************************************
1460 * Module interfaces *
1462 ************************************************************************/
1466 * @style: an XSLT stylesheet
1467 * @cur: an XSLT template
1468 * @mode: the mode name or NULL
1469 * @modeURI: the mode URI or NULL
1471 * Register the XSLT pattern associated to @cur
1473 * Returns -1 in case of error, 0 otherwise
1476 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1477 const xmlChar *mode, const xmlChar *modeURI) {
1478 xsltCompMatchPtr pat, list, *top = NULL, next;
1479 const xmlChar *name = NULL;
1481 if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1484 pat = xsltCompilePattern(cur->match, style->doc, cur->elem);
1489 pat->template = cur;
1491 pat->mode = xmlStrdup(mode);
1492 if (modeURI != NULL)
1493 pat->modeURI = xmlStrdup(modeURI);
1494 if (cur->priority == XSLT_PAT_NO_PRIORITY)
1495 cur->priority = pat->priority;
1497 pat->priority = cur->priority;
1500 * insert it in the hash table list corresponding to its lookup name
1502 switch (pat->steps[0].op) {
1504 if (pat->steps[0].value != NULL)
1505 name = pat->steps[0].value;
1507 top = (xsltCompMatchPtr *) &(style->attrMatch);
1511 case XSLT_OP_PARENT:
1512 case XSLT_OP_ANCESTOR:
1514 name = pat->steps[0].value;
1517 top = (xsltCompMatchPtr *) &(style->rootMatch);
1520 top = (xsltCompMatchPtr *) &(style->keyMatch);
1523 /* TODO optimize ID !!! */
1525 top = (xsltCompMatchPtr *) &(style->elemMatch);
1528 case XSLT_OP_PREDICATE:
1529 xsltGenericError(xsltGenericErrorContext,
1530 "xsltAddTemplate: invalid compiled pattern\n");
1531 xsltFreeCompMatch(pat);
1534 * TODO: some flags at the top level about type based patterns
1535 * would be faster than inclusion in the hash table.
1538 if (pat->steps[0].value != NULL)
1539 name = pat->steps[0].value;
1541 top = (xsltCompMatchPtr *) &(style->piMatch);
1543 case XSLT_OP_COMMENT:
1544 top = (xsltCompMatchPtr *) &(style->commentMatch);
1547 top = (xsltCompMatchPtr *) &(style->textMatch);
1550 if (pat->steps[0].value != NULL)
1551 name = pat->steps[0].value;
1553 top = (xsltCompMatchPtr *) &(style->elemMatch);
1558 if (style->templatesHash == NULL) {
1559 style->templatesHash = xmlHashCreate(1024);
1560 if (style->templatesHash == NULL) {
1561 xsltFreeCompMatch(pat);
1564 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1566 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1567 name, mode, modeURI);
1569 xmlHashAddEntry3(style->templatesHash, name,
1570 mode, modeURI, pat);
1573 * Note '<=' since one must choose among the matching
1574 * template rules that are left, the one that occurs
1575 * last in the stylesheet
1577 if (list->priority <= pat->priority) {
1579 xmlHashUpdateEntry3(style->templatesHash, name,
1580 mode, modeURI, pat, NULL);
1582 while (list->next != NULL) {
1583 if (list->next->priority <= pat->priority)
1587 pat->next = list->next;
1592 } else if (top != NULL) {
1597 } else if (list->priority <= pat->priority) {
1601 while (list->next != NULL) {
1602 if (list->next->priority <= pat->priority)
1606 pat->next = list->next;
1610 xsltGenericError(xsltGenericErrorContext,
1611 "xsltAddTemplate: invalid compiled pattern\n");
1612 xsltFreeCompMatch(pat);
1615 #ifdef DEBUG_PATTERN
1617 xsltGenericDebug(xsltGenericDebugContext,
1618 "added pattern : '%s' mode '%s' priority %f\n",
1619 pat->template->match, pat->mode, pat->priority);
1621 xsltGenericDebug(xsltGenericDebugContext,
1622 "added pattern : '%s' priority %f\n",
1623 pat->template->match, pat->priority);
1633 * @ctxt: a XSLT process context
1635 * @style: the current style
1637 * Finds the template applying to this node, if @style is non-NULL
1638 * it means one need to look for the next imported template in scope.
1640 * Returns the xsltTemplatePtr or NULL if not found
1643 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
1644 xsltStylesheetPtr style) {
1645 xsltStylesheetPtr curstyle;
1646 xsltTemplatePtr ret = NULL;
1647 const xmlChar *name = NULL;
1648 xsltCompMatchPtr list = NULL;
1650 if ((ctxt == NULL) || (node == NULL))
1653 if (style == NULL) {
1654 curstyle = ctxt->style;
1656 curstyle = xsltNextImport(style);
1659 while ((curstyle != NULL) && (curstyle != style)) {
1660 /* TODO : handle IDs/keys here ! */
1661 if (curstyle->templatesHash != NULL) {
1663 * Use the top name as selector
1665 switch (node->type) {
1666 case XML_ELEMENT_NODE:
1667 case XML_ATTRIBUTE_NODE:
1671 case XML_DOCUMENT_NODE:
1672 case XML_HTML_DOCUMENT_NODE:
1674 case XML_CDATA_SECTION_NODE:
1675 case XML_COMMENT_NODE:
1676 case XML_ENTITY_REF_NODE:
1677 case XML_ENTITY_NODE:
1678 case XML_DOCUMENT_TYPE_NODE:
1679 case XML_DOCUMENT_FRAG_NODE:
1680 case XML_NOTATION_NODE:
1682 case XML_ELEMENT_DECL:
1683 case XML_ATTRIBUTE_DECL:
1684 case XML_ENTITY_DECL:
1685 case XML_NAMESPACE_DECL:
1686 case XML_XINCLUDE_START:
1687 case XML_XINCLUDE_END:
1696 * find the list of appliable expressions based on the name
1698 list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
1699 name, ctxt->mode, ctxt->modeURI);
1702 while (list != NULL) {
1703 if (xsltTestCompMatch(ctxt, list, node,
1704 ctxt->mode, ctxt->modeURI)) {
1705 ret = list->template;
1713 * find alternate generic matches
1715 switch (node->type) {
1716 case XML_ELEMENT_NODE:
1717 list = curstyle->elemMatch;
1719 case XML_ATTRIBUTE_NODE:
1720 list = curstyle->attrMatch;
1723 list = curstyle->piMatch;
1725 case XML_DOCUMENT_NODE:
1726 case XML_HTML_DOCUMENT_NODE:
1727 list = curstyle->rootMatch;
1730 case XML_CDATA_SECTION_NODE:
1731 list = curstyle->textMatch;
1733 case XML_COMMENT_NODE:
1734 list = curstyle->commentMatch;
1736 case XML_ENTITY_REF_NODE:
1737 case XML_ENTITY_NODE:
1738 case XML_DOCUMENT_TYPE_NODE:
1739 case XML_DOCUMENT_FRAG_NODE:
1740 case XML_NOTATION_NODE:
1742 case XML_ELEMENT_DECL:
1743 case XML_ATTRIBUTE_DECL:
1744 case XML_ENTITY_DECL:
1745 case XML_NAMESPACE_DECL:
1746 case XML_XINCLUDE_START:
1747 case XML_XINCLUDE_END:
1753 while ((list != NULL) &&
1754 ((ret == NULL) || (list->priority > ret->priority))) {
1755 if (xsltTestCompMatch(ctxt, list, node,
1756 ctxt->mode, ctxt->modeURI)) {
1757 ret = list->template;
1762 if (node->_private != NULL) {
1763 list = curstyle->keyMatch;
1764 while ((list != NULL) &&
1765 ((ret == NULL) || (list->priority > ret->priority))) {
1766 if (xsltTestCompMatch(ctxt, list, node,
1767 ctxt->mode, ctxt->modeURI)) {
1768 ret = list->template;
1778 * Cycle on next curstylesheet import.
1780 curstyle = xsltNextImport(curstyle);
1786 * xsltCleanupTemplates:
1787 * @style: an XSLT stylesheet
1789 * Cleanup the state of the templates used by the stylesheet and
1790 * the ones it imports.
1793 xsltCleanupTemplates(xsltStylesheetPtr style) {
1794 while (style != NULL) {
1795 xmlHashScan((xmlHashTablePtr) style->templatesHash,
1796 (xmlHashScanner) xsltCleanupCompMatch, NULL);
1798 style = xsltNextImport(style);
1803 * xsltFreeTemplateHashes:
1804 * @style: an XSLT stylesheet
1806 * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1809 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1810 if (style->templatesHash != NULL)
1811 xmlHashFree((xmlHashTablePtr) style->templatesHash,
1812 (xmlHashDeallocator) xsltFreeCompMatchList);
1813 if (style->rootMatch != NULL)
1814 xsltFreeCompMatchList(style->rootMatch);
1815 if (style->keyMatch != NULL)
1816 xsltFreeCompMatchList(style->keyMatch);
1817 if (style->elemMatch != NULL)
1818 xsltFreeCompMatchList(style->elemMatch);
1819 if (style->attrMatch != NULL)
1820 xsltFreeCompMatchList(style->attrMatch);
1821 if (style->parentMatch != NULL)
1822 xsltFreeCompMatchList(style->parentMatch);
1823 if (style->textMatch != NULL)
1824 xsltFreeCompMatchList(style->textMatch);
1825 if (style->piMatch != NULL)
1826 xsltFreeCompMatchList(style->piMatch);
1827 if (style->commentMatch != NULL)
1828 xsltFreeCompMatchList(style->commentMatch);
1834 * @node: a node in the source tree
1835 * @pattern: an XSLT pattern
1837 * Determine if a node matches a pattern.
1840 xsltMatchPattern(xsltTransformContextPtr context,
1842 const xmlChar *pattern)
1845 xsltCompMatchPtr first, comp;
1847 if ((context != NULL) && (pattern != NULL)) {
1848 first = xsltCompilePattern(pattern);
1849 for (comp = first; comp != NULL; comp = comp->next) {
1850 match = xsltTestCompMatch(context, comp, node, NULL, NULL);
1855 xsltFreeCompMatchList(first);