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;
69 * Optimisations for count
76 struct _xsltCompMatch {
77 struct _xsltCompMatch *next; /* siblings in the name hash */
78 float priority; /* the priority */
79 const xmlChar *mode; /* the mode */
80 const xmlChar *modeURI; /* the mode URI */
81 xsltTemplatePtr template; /* the associated template */
83 /* TODO fix the statically allocated size steps[] */
86 xsltStepOp steps[20]; /* ops for computation */
89 typedef struct _xsltParserContext xsltParserContext;
90 typedef xsltParserContext *xsltParserContextPtr;
91 struct _xsltParserContext {
92 const xmlChar *cur; /* the current char being parsed */
93 const xmlChar *base; /* the full expression */
94 xmlDocPtr doc; /* the source document */
95 xmlNodePtr elem; /* the source element */
96 int error; /* error code */
97 xsltCompMatchPtr comp; /* the result */
100 /************************************************************************
104 ************************************************************************/
109 * Create a new XSLT CompMatch
111 * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
114 xsltNewCompMatch(void) {
115 xsltCompMatchPtr cur;
117 cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
119 xsltGenericError(xsltGenericErrorContext,
120 "xsltNewCompMatch : malloc failed\n");
123 memset(cur, 0, sizeof(xsltCompMatch));
130 * @comp: an XSLT comp
132 * Free up the memory allocated by @comp
135 xsltFreeCompMatch(xsltCompMatchPtr comp) {
141 if (comp->mode != NULL)
142 xmlFree((xmlChar *)comp->mode);
143 if (comp->modeURI != NULL)
144 xmlFree((xmlChar *)comp->modeURI);
145 for (i = 0;i < comp->nbStep;i++) {
146 op = &comp->steps[i];
147 if (op->value != NULL)
149 if (op->value2 != NULL)
151 if (op->value3 != NULL)
154 memset(comp, -1, sizeof(xsltCompMatch));
159 * xsltFreeCompMatchList:
160 * @comp: an XSLT comp list
162 * Free up the memory allocated by all the elements of @comp
165 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
166 xsltCompMatchPtr cur;
168 while (comp != NULL) {
171 xsltFreeCompMatch(cur);
176 * xsltNewParserContext:
178 * Create a new XSLT ParserContext
180 * Returns the newly allocated xsltParserContextPtr or NULL in case of error
183 xsltNewParserContext(void) {
184 xsltParserContextPtr cur;
186 cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
188 xsltGenericError(xsltGenericErrorContext,
189 "xsltNewParserContext : malloc failed\n");
192 memset(cur, 0, sizeof(xsltParserContext));
197 * xsltFreeParserContext:
198 * @ctxt: an XSLT parser context
200 * Free up the memory allocated by @ctxt
203 xsltFreeParserContext(xsltParserContextPtr ctxt) {
206 memset(ctxt, -1, sizeof(xsltParserContext));
212 * @comp: the compiled match expression
214 * @value: the first value
215 * @value2: the second value
217 * Add an step to an XSLT Compiled Match
219 * Returns -1 in case of failure, 0 otherwise.
222 xsltCompMatchAdd(xsltCompMatchPtr comp, xsltOp op, xmlChar *value,
224 if (comp->nbStep >= 20) {
225 xsltGenericError(xsltGenericErrorContext,
226 "xsltCompMatchAddOp: overflow\n");
229 comp->steps[comp->nbStep].op = op;
230 comp->steps[comp->nbStep].value = value;
231 comp->steps[comp->nbStep].value2 = value2;
237 * xsltSwapTopCompMatch:
238 * @comp: the compiled match expression
240 * reverse the two top steps.
243 xsltSwapTopCompMatch(xsltCompMatchPtr comp) {
245 int j = comp->nbStep - 1;
248 register xmlChar *tmp;
251 tmp = comp->steps[i].value;
252 comp->steps[i].value = comp->steps[j].value;
253 comp->steps[j].value = tmp;
254 tmp = comp->steps[i].value2;
255 comp->steps[i].value2 = comp->steps[j].value2;
256 comp->steps[j].value2 = tmp;
257 op = comp->steps[i].op;
258 comp->steps[i].op = comp->steps[j].op;
259 comp->steps[j].op = op;
264 * xsltReverseCompMatch:
265 * @comp: the compiled match expression
267 * reverse all the stack of expressions
270 xsltReverseCompMatch(xsltCompMatchPtr comp) {
272 int j = comp->nbStep - 1;
275 register xmlChar *tmp;
277 tmp = comp->steps[i].value;
278 comp->steps[i].value = comp->steps[j].value;
279 comp->steps[j].value = tmp;
280 tmp = comp->steps[i].value2;
281 comp->steps[i].value2 = comp->steps[j].value2;
282 comp->steps[j].value2 = tmp;
283 op = comp->steps[i].op;
284 comp->steps[i].op = comp->steps[j].op;
285 comp->steps[j].op = op;
289 comp->steps[comp->nbStep++].op = XSLT_OP_END;
292 /************************************************************************
294 * The interpreter for the precompiled patterns *
296 ************************************************************************/
300 * @ctxt: a XSLT process context
301 * @comp: the precompiled pattern
303 * @mode: the mode name or NULL
304 * @modeURI: the mode URI or NULL
306 * Test wether the node matches the pattern
308 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
311 xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
312 xmlNodePtr node, const xmlChar *mode,
313 const xmlChar *modeURI) {
315 xsltStepOpPtr step, select = NULL;
317 if ((comp == NULL) || (node == NULL) || (ctxt == NULL)) {
318 xsltGenericError(xsltGenericErrorContext,
319 "xsltTestCompMatch: null arg\n");
323 if (comp->mode == NULL)
325 if ((comp->mode != mode) && (!xmlStrEqual(comp->mode, mode)))
328 if (comp->mode != NULL)
331 if (modeURI != NULL) {
332 if (comp->modeURI == NULL)
334 if ((comp->modeURI != modeURI) &&
335 (!xmlStrEqual(comp->modeURI, modeURI)))
338 if (comp->modeURI != NULL)
341 for (i = 0;i < comp->nbStep;i++) {
342 step = &comp->steps[i];
343 if (step->op != XSLT_OP_PREDICATE)
349 if ((node->type == XML_DOCUMENT_NODE) ||
350 (node->type == XML_HTML_DOCUMENT_NODE))
354 if (node->type != XML_ELEMENT_NODE)
356 if (step->value == NULL)
358 if (!xmlStrEqual(step->value, node->name))
362 if (node->ns == NULL) {
363 if (step->value2 != NULL)
365 } else if (node->ns->href != NULL) {
366 if (step->value2 == NULL)
368 if (!xmlStrEqual(step->value2, node->ns->href))
373 TODO /* Handle OP_CHILD */
376 if (node->type != XML_ATTRIBUTE_NODE)
378 if (step->value == NULL)
380 if (!xmlStrEqual(step->value, node->name))
384 if (node->ns == NULL) {
385 if (step->value2 != NULL)
387 } else if (node->ns->href != NULL) {
388 if (step->value2 == NULL)
390 if (!xmlStrEqual(step->value2, node->ns->href))
398 if (step->value == NULL)
400 if (!xmlStrEqual(step->value, node->name))
403 if (node->ns == NULL) {
404 if (step->value2 != NULL)
406 } else if (node->ns->href != NULL) {
407 if (step->value2 == NULL)
409 if (!xmlStrEqual(step->value2, node->ns->href))
413 case XSLT_OP_ANCESTOR:
414 /* TODO: implement coalescing of ANCESTOR/NODE ops */
415 if (step->value == NULL) {
417 step = &comp->steps[i];
418 if (step->op == XSLT_OP_ROOT)
420 if (step->op != XSLT_OP_ELEM)
422 if (step->value == NULL)
428 while (node != NULL) {
431 if (xmlStrEqual(step->value, node->name)) {
433 if (node->ns == NULL) {
434 if (step->value2 == NULL)
436 } else if (node->ns->href != NULL) {
437 if ((step->value2 != NULL) &&
438 (xmlStrEqual(step->value2, node->ns->href)))
448 /* TODO Handle IDs decently, must be done differently */
451 id = xmlGetID(node->doc, step->value);
452 if ((id == NULL) || (id->parent != node))
460 list = xsltGetKey(ctxt, step->value,
461 step->value3, step->value2);
464 for (i = 0;i < list->nodeNr;i++)
465 if (list->nodeTab[i] == node)
467 if (i >= list->nodeNr)
473 if (node->ns == NULL) {
474 if (step->value != NULL)
476 } else if (node->ns->href != NULL) {
477 if (step->value == NULL)
479 if (!xmlStrEqual(step->value, node->ns->href))
484 switch (node->type) {
485 case XML_DOCUMENT_NODE:
486 case XML_HTML_DOCUMENT_NODE:
487 case XML_ELEMENT_NODE:
493 case XSLT_OP_PREDICATE: {
496 int pos = 0, len = 0;
498 * Depending on the last selection, one may need to
499 * recompute contextSize and proximityPosition.
501 oldCS = ctxt->xpathCtxt->contextSize;
502 oldCP = ctxt->xpathCtxt->proximityPosition;
503 if ((select != NULL) &&
504 (select->op == XSLT_OP_ELEM) &&
505 (select->value != NULL) &&
506 (node->type == XML_ELEMENT_NODE) &&
507 (node->parent != NULL)) {
509 if ((select->previous != NULL) &&
510 (select->previous->parent == node->parent)) {
512 * just walk back to adjust the index
515 xmlNodePtr sibling = node;
517 while (sibling != NULL) {
518 if (sibling == select->previous)
520 if (xmlStrEqual(node->name, sibling->name)) {
521 if ((select->value2 == NULL) ||
522 ((sibling->ns != NULL) &&
523 (xmlStrEqual(select->value2,
524 sibling->ns->href))))
527 sibling = sibling->prev;
529 if (sibling == NULL) {
530 /* hum going backward in document order ... */
533 while (sibling != NULL) {
534 if (sibling == select->previous)
536 if ((select->value2 == NULL) ||
537 ((sibling->ns != NULL) &&
538 (xmlStrEqual(select->value2,
539 sibling->ns->href))))
541 sibling = sibling->next;
544 if (sibling != NULL) {
545 pos = select->index + i;
547 select->previous = node;
553 * recompute the index
555 xmlNodePtr siblings = node->parent->children;
557 while (siblings != NULL) {
558 if (siblings->type == XML_ELEMENT_NODE) {
559 if (siblings == node) {
562 } else if (xmlStrEqual(node->name,
564 if ((select->value2 == NULL) ||
565 ((siblings->ns != NULL) &&
566 (xmlStrEqual(select->value2,
567 siblings->ns->href))))
571 siblings = siblings->next;
575 ctxt->xpathCtxt->contextSize = len;
576 ctxt->xpathCtxt->proximityPosition = pos;
577 select->previous = node;
581 } else if ((select != NULL) && (select->op == XSLT_OP_ALL)) {
582 if ((select->previous != NULL) &&
583 (select->previous->parent == node->parent)) {
585 * just walk back to adjust the index
588 xmlNodePtr sibling = node;
590 while (sibling != NULL) {
591 if (sibling == select->previous)
593 if (sibling->type == XML_ELEMENT_NODE)
595 sibling = sibling->prev;
597 if (sibling == NULL) {
598 /* hum going backward in document order ... */
601 while (sibling != NULL) {
602 if (sibling == select->previous)
604 if (sibling->type == XML_ELEMENT_NODE)
606 sibling = sibling->next;
609 if (sibling != NULL) {
610 pos = select->index + i;
612 select->previous = node;
618 * recompute the index
620 xmlNodePtr siblings = node->parent->children;
622 while (siblings != NULL) {
623 if (siblings->type == XML_ELEMENT_NODE) {
625 if (siblings == node) {
629 siblings = siblings->next;
633 ctxt->xpathCtxt->contextSize = len;
634 ctxt->xpathCtxt->proximityPosition = pos;
635 select->previous = node;
640 oldNode = ctxt->node;
643 if ((step->value == NULL) ||
644 (!xsltEvalXPathPredicate(ctxt, step->value))) {
646 ctxt->xpathCtxt->contextSize = oldCS;
647 ctxt->xpathCtxt->proximityPosition = oldCP;
649 ctxt->node = oldNode;
653 ctxt->xpathCtxt->contextSize = oldCS;
654 ctxt->xpathCtxt->proximityPosition = oldCP;
656 ctxt->node = oldNode;
660 if (node->type != XML_PI_NODE)
662 if (step->value != NULL) {
663 if (!xmlStrEqual(step->value, node->name))
667 case XSLT_OP_COMMENT:
668 if (node->type != XML_COMMENT_NODE)
672 if ((node->type != XML_TEXT_NODE) &&
673 (node->type != XML_CDATA_SECTION_NODE))
677 switch (node->type) {
678 case XML_DOCUMENT_NODE:
679 case XML_HTML_DOCUMENT_NODE:
680 case XML_ELEMENT_NODE:
681 case XML_CDATA_SECTION_NODE:
683 case XML_COMMENT_NODE:
685 case XML_ATTRIBUTE_NODE:
697 * xsltTestCompMatchList:
698 * @ctxt: a XSLT process context
700 * @comp: the precompiled pattern list
702 * Test wether the node matches one of the patterns in the list
704 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
707 xsltTestCompMatchList(xsltTransformContextPtr ctxt, xmlNodePtr node,
708 xsltCompMatchPtr comp) {
711 if ((ctxt == NULL) || (node == NULL))
713 while (comp != NULL) {
714 ret = xsltTestCompMatch(ctxt, comp, node, NULL, NULL);
722 /************************************************************************
724 * Dedicated parser for templates *
726 ************************************************************************/
728 #define CUR (*ctxt->cur)
729 #define SKIP(val) ctxt->cur += (val)
730 #define NXT(val) ctxt->cur[(val)]
731 #define CUR_PTR ctxt->cur
733 #define SKIP_BLANKS \
734 while (IS_BLANK(CUR)) NEXT
736 #define CURRENT (*ctxt->cur)
737 #define NEXT ((*ctxt->cur) ? ctxt->cur++: ctxt->cur)
740 #define PUSH(op, val, val2) \
741 if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
744 xsltSwapTopCompMatch(ctxt->comp);
746 #define XSLT_ERROR(X) \
747 { xsltError(ctxt, __FILE__, __LINE__, X); \
748 ctxt->error = (X); return; }
750 #define XSLT_ERROR0(X) \
751 { xsltError(ctxt, __FILE__, __LINE__, X); \
752 ctxt->error = (X); return(0); }
756 * @ctxt: the XPath Parser context
758 * Parse an XPath Litteral:
760 * [29] Literal ::= '"' [^"]* '"'
763 * Returns the Literal parsed or NULL
767 xsltScanLiteral(xsltParserContextPtr ctxt) {
775 while ((IS_CHAR(CUR)) && (CUR != '"'))
778 /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
782 ret = xmlStrndup(q, CUR_PTR - q);
785 } else if (CUR == '\'') {
788 while ((IS_CHAR(CUR)) && (CUR != '\''))
791 /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
795 ret = xmlStrndup(q, CUR_PTR - q);
799 /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
808 * @ctxt: the XPath Parser context
810 * Trickery: parse an XML name but without consuming the input flow
811 * Needed to avoid insanity in the parser state.
813 * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
814 * CombiningChar | Extender
816 * [5] Name ::= (Letter | '_' | ':') (NameChar)*
818 * [6] Names ::= Name (S Name)*
820 * Returns the Name parsed or NULL
824 xsltScanName(xsltParserContextPtr ctxt) {
825 xmlChar buf[XML_MAX_NAMELEN];
829 if (!IS_LETTER(CUR) && (CUR != '_') &&
834 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
835 (NXT(len) == '.') || (NXT(len) == '-') ||
836 (NXT(len) == '_') || (NXT(len) == ':') ||
837 (IS_COMBINING(NXT(len))) ||
838 (IS_EXTENDER(NXT(len)))) {
841 if (len >= XML_MAX_NAMELEN) {
842 xmlGenericError(xmlGenericErrorContext,
843 "xmlScanName: reached XML_MAX_NAMELEN limit\n");
844 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
845 (NXT(len) == '.') || (NXT(len) == '-') ||
846 (NXT(len) == '_') || (NXT(len) == ':') ||
847 (IS_COMBINING(NXT(len))) ||
848 (IS_EXTENDER(NXT(len))))
854 return(xmlStrndup(buf, len));
857 * xsltCompileIdKeyPattern:
858 * @comp: the compilation context
859 * @name: a preparsed name
860 * @aid: whether id/key are allowed there
862 * Compile the XSLT LocationIdKeyPattern
863 * [3] IdKeyPattern ::= 'id' '(' Literal ')'
864 * | 'key' '(' Literal ',' Literal ')'
866 * also handle NodeType and PI from:
868 * [7] NodeTest ::= NameTest
870 * | 'processing-instruction' '(' Literal ')'
873 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
875 xmlChar *lit2 = NULL;
878 xsltGenericError(xsltGenericErrorContext,
879 "xsltCompileIdKeyPattern : ( expected\n");
883 if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
886 lit = xsltScanLiteral(ctxt);
891 xsltGenericError(xsltGenericErrorContext,
892 "xsltCompileIdKeyPattern : ) expected\n");
897 PUSH(XSLT_OP_ID, lit, NULL);
898 } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
901 lit = xsltScanLiteral(ctxt);
906 xsltGenericError(xsltGenericErrorContext,
907 "xsltCompileIdKeyPattern : , expected\n");
913 lit2 = xsltScanLiteral(ctxt);
918 xsltGenericError(xsltGenericErrorContext,
919 "xsltCompileIdKeyPattern : ) expected\n");
924 /* TODO: support namespace in keys */
925 PUSH(XSLT_OP_KEY, lit, lit2);
926 } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
930 lit = xsltScanLiteral(ctxt);
935 xsltGenericError(xsltGenericErrorContext,
936 "xsltCompileIdKeyPattern : ) expected\n");
942 PUSH(XSLT_OP_PI, lit, NULL);
943 } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
947 xsltGenericError(xsltGenericErrorContext,
948 "xsltCompileIdKeyPattern : ) expected\n");
953 PUSH(XSLT_OP_TEXT, NULL, NULL);
954 } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
958 xsltGenericError(xsltGenericErrorContext,
959 "xsltCompileIdKeyPattern : ) expected\n");
964 PUSH(XSLT_OP_COMMENT, NULL, NULL);
965 } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
969 xsltGenericError(xsltGenericErrorContext,
970 "xsltCompileIdKeyPattern : ) expected\n");
975 PUSH(XSLT_OP_NODE, NULL, NULL);
977 xsltGenericError(xsltGenericErrorContext,
978 "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
982 xsltGenericError(xsltGenericErrorContext,
983 "xsltCompileIdKeyPattern : node type\n");
993 * xsltCompileStepPattern:
994 * @comp: the compilation context
995 * @token: a posible precompiled name
997 * Compile the XSLT StepPattern and generates a precompiled
998 * form suitable for fast matching.
1000 * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
1001 * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
1002 * | ('child' | 'attribute') '::'
1004 * [7] NodeTest ::= NameTest
1005 * | NodeType '(' ')'
1006 * | 'processing-instruction' '(' Literal ')'
1007 * [8] Predicate ::= '[' PredicateExpr ']'
1008 * [9] PredicateExpr ::= Expr
1009 * [13] AbbreviatedAxisSpecifier ::= '@'?
1010 * [37] NameTest ::= '*' | NCName ':' '*' | QName
1014 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1015 xmlChar *name = NULL;
1016 xmlChar *prefix = NULL;
1017 xmlChar *ncname = NULL;
1018 xmlChar *URL = NULL;
1021 if ((token == NULL) && (CUR == '@')) {
1025 PUSH(XSLT_OP_ATTR, NULL, NULL);
1028 token = xsltScanName(ctxt);
1029 if (token == NULL) {
1030 xsltGenericError(xsltGenericErrorContext,
1031 "xsltCompileStepPattern : Name expected\n");
1035 PUSH(XSLT_OP_ATTR, token, NULL);
1039 token = xsltScanName(ctxt);
1040 if (token == NULL) {
1043 PUSH(XSLT_OP_ALL, token, NULL);
1044 goto parse_predicate;
1046 xsltGenericError(xsltGenericErrorContext,
1047 "xsltCompileStepPattern : Name expected\n");
1056 xsltCompileIdKeyPattern(ctxt, token, 0);
1059 } else if (CUR == ':') {
1061 if (NXT(1) != ':') {
1062 xsltGenericError(xsltGenericErrorContext,
1063 "xsltCompileStepPattern : sequence '::' expected\n");
1068 if (xmlStrEqual(token, (const xmlChar *) "child")) {
1069 name = xsltScanName(ctxt);
1071 xsltGenericError(xsltGenericErrorContext,
1072 "xsltCompileStepPattern : QName expected\n");
1076 ncname = xmlSplitQName2(name, &prefix);
1077 if (ncname != NULL) {
1078 if (prefix != NULL) {
1081 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1083 xsltGenericError(xsltGenericErrorContext,
1084 "xsl: pattern, no namespace bound to prefix %s\n",
1087 URL = xmlStrdup(ns->href);
1094 PUSH(XSLT_OP_CHILD, name, URL);
1095 } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
1096 name = xsltScanName(ctxt);
1098 xsltGenericError(xsltGenericErrorContext,
1099 "xsltCompileStepPattern : QName expected\n");
1103 ncname = xmlSplitQName2(name, &prefix);
1104 if (ncname != NULL) {
1105 if (prefix != NULL) {
1108 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1110 xsltGenericError(xsltGenericErrorContext,
1111 "xsl: pattern, no namespace bound to prefix %s\n",
1114 URL = xmlStrdup(ns->href);
1121 PUSH(XSLT_OP_ATTR, name, URL);
1123 xsltGenericError(xsltGenericErrorContext,
1124 "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
1129 } else if (CUR == '*') {
1131 PUSH(XSLT_OP_ALL, token, NULL);
1133 ncname = xmlSplitQName2(token, &prefix);
1134 if (ncname != NULL) {
1135 if (prefix != NULL) {
1138 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1140 xsltGenericError(xsltGenericErrorContext,
1141 "xsl: pattern, no namespace bound to prefix %s\n",
1144 URL = xmlStrdup(ns->href);
1151 PUSH(XSLT_OP_ELEM, token, URL);
1155 while (CUR == '[') {
1157 xmlChar *ret = NULL;
1161 /* TODO: avoid breaking in strings ... */
1162 while ((IS_CHAR(CUR)) && (CUR != ']'))
1164 if (!IS_CHAR(CUR)) {
1165 xsltGenericError(xsltGenericErrorContext,
1166 "xsltCompileStepPattern : ']' expected\n");
1170 ret = xmlStrndup(q, CUR_PTR - q);
1171 PUSH(XSLT_OP_PREDICATE, ret, NULL);
1172 /* push the predicate lower than local test */
1185 * xsltCompileRelativePathPattern:
1186 * @comp: the compilation context
1187 * @token: a posible precompiled name
1189 * Compile the XSLT RelativePathPattern and generates a precompiled
1190 * form suitable for fast matching.
1192 * [4] RelativePathPattern ::= StepPattern
1193 * | RelativePathPattern '/' StepPattern
1194 * | RelativePathPattern '//' StepPattern
1197 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1198 xsltCompileStepPattern(ctxt, token);
1202 while ((CUR != 0) && (CUR != '|')) {
1203 if ((CUR == '/') && (NXT(1) == '/')) {
1204 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1208 xsltCompileStepPattern(ctxt, NULL);
1209 } else if (CUR == '/') {
1210 PUSH(XSLT_OP_PARENT, NULL, NULL);
1213 if ((CUR != 0) || (CUR == '|')) {
1214 xsltCompileRelativePathPattern(ctxt, NULL);
1228 * xsltCompileLocationPathPattern:
1229 * @comp: the compilation context
1231 * Compile the XSLT LocationPathPattern and generates a precompiled
1232 * form suitable for fast matching.
1234 * [2] LocationPathPattern ::= '/' RelativePathPattern?
1235 * | IdKeyPattern (('/' | '//') RelativePathPattern)?
1236 * | '//'? RelativePathPattern
1239 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1241 if ((CUR == '/') && (NXT(1) == '/')) {
1243 * since we reverse the query
1244 * a leading // can be safely ignored
1248 xsltCompileRelativePathPattern(ctxt, NULL);
1249 } else if (CUR == '/') {
1251 * We need to find root as the parent
1255 PUSH(XSLT_OP_ROOT, NULL, NULL);
1256 if ((CUR != 0) || (CUR == '|')) {
1257 PUSH(XSLT_OP_PARENT, NULL, NULL);
1258 xsltCompileRelativePathPattern(ctxt, NULL);
1260 } else if (CUR == '*') {
1261 xsltCompileRelativePathPattern(ctxt, NULL);
1262 } else if (CUR == '@') {
1263 xsltCompileRelativePathPattern(ctxt, NULL);
1266 name = xsltScanName(ctxt);
1268 xsltGenericError(xsltGenericErrorContext,
1269 "xsltCompileLocationPathPattern : Name expected\n");
1273 if (!xmlXPathIsNodeType(name)) {
1276 xsltCompileIdKeyPattern(ctxt, name, 1);
1277 if ((CUR == '/') && (NXT(1) == '/')) {
1278 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1282 xsltCompileRelativePathPattern(ctxt, NULL);
1283 } else if (CUR == '/') {
1284 PUSH(XSLT_OP_PARENT, NULL, NULL);
1287 xsltCompileRelativePathPattern(ctxt, NULL);
1292 xsltCompileRelativePathPattern(ctxt, name);
1299 * xsltCompilePattern:
1300 * @pattern an XSLT pattern
1301 * @doc: the containing document
1302 * @node: the containing element
1304 * Compile the XSLT pattern and generates a list of precompiled form suitable
1305 * for fast matching.
1307 * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1309 * Returns the generated pattern list or NULL in case of failure
1313 xsltCompilePattern(const xmlChar *pattern, xmlDocPtr doc, xmlNodePtr node) {
1314 xsltParserContextPtr ctxt = NULL;
1315 xsltCompMatchPtr element, first = NULL, previous = NULL;
1316 int current, start, end;
1318 if (pattern == NULL) {
1319 xsltGenericError(xsltGenericErrorContext,
1320 "xsltCompilePattern : NULL pattern\n");
1324 #ifdef DEBUG_PATTERN
1325 xsltGenericDebug(xsltGenericDebugContext,
1326 "xsltCompilePattern : parsing '%s'\n", pattern);
1329 ctxt = xsltNewParserContext();
1335 while (pattern[current] != 0) {
1337 while (IS_BLANK(pattern[current]))
1340 while ((pattern[end] != 0) && (pattern[end] != '|'))
1342 if (current == end) {
1343 xsltGenericError(xsltGenericErrorContext,
1344 "xsltCompilePattern : NULL pattern\n");
1347 element = xsltNewCompMatch();
1348 if (element == NULL) {
1353 else if (previous != NULL)
1354 previous->next = element;
1357 ctxt->comp = element;
1358 ctxt->base = xmlStrndup(&pattern[start], end - start);
1359 ctxt->cur = &(ctxt->base)[current - start];
1360 xsltCompileLocationPathPattern(ctxt);
1362 xmlFree((xmlChar *)ctxt->base);
1367 * Reverse for faster interpretation.
1369 xsltReverseCompMatch(element);
1372 * Set-up the priority
1374 if (((element->steps[0].op == XSLT_OP_ELEM) ||
1375 (element->steps[0].op == XSLT_OP_ATTR)) &&
1376 (element->steps[0].value != NULL) &&
1377 (element->steps[1].op == XSLT_OP_END)) {
1378 element->priority = 0;
1379 } else if ((element->steps[0].op == XSLT_OP_ROOT) &&
1380 (element->steps[1].op == XSLT_OP_END)) {
1381 element->priority = 0;
1382 } else if ((element->steps[0].op == XSLT_OP_PI) &&
1383 (element->steps[0].value != NULL) &&
1384 (element->steps[1].op == XSLT_OP_END)) {
1385 element->priority = 0;
1386 } else if ((element->steps[0].op == XSLT_OP_NS) &&
1387 (element->steps[0].value != NULL) &&
1388 (element->steps[1].op == XSLT_OP_END)) {
1389 element->priority = -0.25;
1390 } else if (((element->steps[0].op == XSLT_OP_PI) ||
1391 (element->steps[0].op == XSLT_OP_TEXT) ||
1392 (element->steps[0].op == XSLT_OP_ALL) ||
1393 (element->steps[0].op == XSLT_OP_NODE) ||
1394 (element->steps[0].op == XSLT_OP_COMMENT)) &&
1395 (element->steps[1].op == XSLT_OP_END)) {
1396 element->priority = -0.5;
1398 element->priority = 0.5;
1400 if (pattern[end] == '|')
1405 xsltGenericError(xsltGenericErrorContext,
1406 "xsltCompilePattern : NULL pattern\n");
1410 xsltFreeParserContext(ctxt);
1415 xsltFreeParserContext(ctxt);
1417 xsltFreeCompMatchList(first);
1421 /************************************************************************
1423 * Module interfaces *
1425 ************************************************************************/
1429 * @style: an XSLT stylesheet
1430 * @cur: an XSLT template
1431 * @mode: the mode name or NULL
1432 * @modeURI: the mode URI or NULL
1434 * Register the XSLT pattern associated to @cur
1436 * Returns -1 in case of error, 0 otherwise
1439 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1440 const xmlChar *mode, const xmlChar *modeURI) {
1441 xsltCompMatchPtr pat, list, *top = NULL, next;
1442 const xmlChar *name = NULL;
1444 if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1447 pat = xsltCompilePattern(cur->match, style->doc, cur->elem);
1452 pat->template = cur;
1454 pat->mode = xmlStrdup(mode);
1455 if (modeURI != NULL)
1456 pat->modeURI = xmlStrdup(modeURI);
1457 if (cur->priority == XSLT_PAT_NO_PRIORITY)
1458 cur->priority = pat->priority;
1460 pat->priority = cur->priority;
1463 * insert it in the hash table list corresponding to its lookup name
1465 switch (pat->steps[0].op) {
1467 if (pat->steps[0].value != NULL)
1468 name = pat->steps[0].value;
1470 top = (xsltCompMatchPtr *) &(style->attrMatch);
1474 case XSLT_OP_PARENT:
1475 case XSLT_OP_ANCESTOR:
1477 name = pat->steps[0].value;
1480 top = (xsltCompMatchPtr *) &(style->rootMatch);
1483 top = (xsltCompMatchPtr *) &(style->keyMatch);
1486 /* TODO optimize ID !!! */
1488 top = (xsltCompMatchPtr *) &(style->elemMatch);
1491 case XSLT_OP_PREDICATE:
1492 xsltGenericError(xsltGenericErrorContext,
1493 "xsltAddTemplate: invalid compiled pattern\n");
1494 xsltFreeCompMatch(pat);
1497 * TODO: some flags at the top level about type based patterns
1498 * would be faster than inclusion in the hash table.
1501 if (pat->steps[0].value != NULL)
1502 name = pat->steps[0].value;
1504 top = (xsltCompMatchPtr *) &(style->piMatch);
1506 case XSLT_OP_COMMENT:
1507 top = (xsltCompMatchPtr *) &(style->commentMatch);
1510 top = (xsltCompMatchPtr *) &(style->textMatch);
1513 if (pat->steps[0].value != NULL)
1514 name = pat->steps[0].value;
1516 top = (xsltCompMatchPtr *) &(style->elemMatch);
1521 if (style->templatesHash == NULL) {
1522 style->templatesHash = xmlHashCreate(1024);
1523 if (style->templatesHash == NULL) {
1524 xsltFreeCompMatch(pat);
1527 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1529 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1530 name, mode, modeURI);
1532 xmlHashAddEntry3(style->templatesHash, name,
1533 mode, modeURI, pat);
1536 * Note '<=' since one must choose among the matching
1537 * template rules that are left, the one that occurs
1538 * last in the stylesheet
1540 if (list->priority <= pat->priority) {
1542 xmlHashUpdateEntry3(style->templatesHash, name,
1543 mode, modeURI, pat, NULL);
1545 while (list->next != NULL) {
1546 if (list->next->priority <= pat->priority)
1550 pat->next = list->next;
1555 } else if (top != NULL) {
1560 } else if (list->priority <= pat->priority) {
1564 while (list->next != NULL) {
1565 if (list->next->priority <= pat->priority)
1569 pat->next = list->next;
1573 xsltGenericError(xsltGenericErrorContext,
1574 "xsltAddTemplate: invalid compiled pattern\n");
1575 xsltFreeCompMatch(pat);
1578 #ifdef DEBUG_PATTERN
1580 xsltGenericDebug(xsltGenericDebugContext,
1581 "added pattern : '%s' mode '%s' priority %f\n",
1582 pat->template->match, pat->mode, pat->priority);
1584 xsltGenericDebug(xsltGenericDebugContext,
1585 "added pattern : '%s' priority %f\n",
1586 pat->template->match, pat->priority);
1596 * @ctxt: a XSLT process context
1598 * @style: the current style
1600 * Finds the template applying to this node, if @style is non-NULL
1601 * it means one need to look for the next imported template in scope.
1603 * Returns the xsltTemplatePtr or NULL if not found
1606 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
1607 xsltStylesheetPtr style) {
1608 xsltStylesheetPtr curstyle;
1609 xsltTemplatePtr ret = NULL;
1610 const xmlChar *name = NULL;
1611 xsltCompMatchPtr list = NULL;
1613 if ((ctxt == NULL) || (node == NULL))
1616 if (style == NULL) {
1617 curstyle = ctxt->style;
1619 curstyle = xsltNextImport(style);
1622 while ((curstyle != NULL) && (curstyle != style)) {
1623 /* TODO : handle IDs/keys here ! */
1624 if (curstyle->templatesHash != NULL) {
1626 * Use the top name as selector
1628 switch (node->type) {
1629 case XML_ELEMENT_NODE:
1630 case XML_ATTRIBUTE_NODE:
1634 case XML_DOCUMENT_NODE:
1635 case XML_HTML_DOCUMENT_NODE:
1637 case XML_CDATA_SECTION_NODE:
1638 case XML_COMMENT_NODE:
1639 case XML_ENTITY_REF_NODE:
1640 case XML_ENTITY_NODE:
1641 case XML_DOCUMENT_TYPE_NODE:
1642 case XML_DOCUMENT_FRAG_NODE:
1643 case XML_NOTATION_NODE:
1645 case XML_ELEMENT_DECL:
1646 case XML_ATTRIBUTE_DECL:
1647 case XML_ENTITY_DECL:
1648 case XML_NAMESPACE_DECL:
1649 case XML_XINCLUDE_START:
1650 case XML_XINCLUDE_END:
1659 * find the list of appliable expressions based on the name
1661 list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
1662 name, ctxt->mode, ctxt->modeURI);
1665 while (list != NULL) {
1666 if (xsltTestCompMatch(ctxt, list, node,
1667 ctxt->mode, ctxt->modeURI)) {
1668 ret = list->template;
1676 * find alternate generic matches
1678 switch (node->type) {
1679 case XML_ELEMENT_NODE:
1680 list = curstyle->elemMatch;
1682 case XML_ATTRIBUTE_NODE:
1683 list = curstyle->attrMatch;
1686 list = curstyle->piMatch;
1688 case XML_DOCUMENT_NODE:
1689 case XML_HTML_DOCUMENT_NODE:
1690 list = curstyle->rootMatch;
1693 case XML_CDATA_SECTION_NODE:
1694 list = curstyle->textMatch;
1696 case XML_COMMENT_NODE:
1697 list = curstyle->commentMatch;
1699 case XML_ENTITY_REF_NODE:
1700 case XML_ENTITY_NODE:
1701 case XML_DOCUMENT_TYPE_NODE:
1702 case XML_DOCUMENT_FRAG_NODE:
1703 case XML_NOTATION_NODE:
1705 case XML_ELEMENT_DECL:
1706 case XML_ATTRIBUTE_DECL:
1707 case XML_ENTITY_DECL:
1708 case XML_NAMESPACE_DECL:
1709 case XML_XINCLUDE_START:
1710 case XML_XINCLUDE_END:
1716 while ((list != NULL) &&
1717 ((ret == NULL) || (list->priority > ret->priority))) {
1718 if (xsltTestCompMatch(ctxt, list, node,
1719 ctxt->mode, ctxt->modeURI)) {
1720 ret = list->template;
1725 if (node->_private != NULL) {
1726 list = curstyle->keyMatch;
1727 while ((list != NULL) &&
1728 ((ret == NULL) || (list->priority > ret->priority))) {
1729 if (xsltTestCompMatch(ctxt, list, node,
1730 ctxt->mode, ctxt->modeURI)) {
1731 ret = list->template;
1741 * Cycle on next curstylesheet import.
1743 curstyle = xsltNextImport(curstyle);
1750 * xsltFreeTemplateHashes:
1751 * @style: an XSLT stylesheet
1753 * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1756 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1757 if (style->templatesHash != NULL)
1758 xmlHashFree((xmlHashTablePtr) style->templatesHash,
1759 (xmlHashDeallocator) xsltFreeCompMatchList);
1760 if (style->rootMatch != NULL)
1761 xsltFreeCompMatchList(style->rootMatch);
1762 if (style->keyMatch != NULL)
1763 xsltFreeCompMatchList(style->keyMatch);
1764 if (style->elemMatch != NULL)
1765 xsltFreeCompMatchList(style->elemMatch);
1766 if (style->attrMatch != NULL)
1767 xsltFreeCompMatchList(style->attrMatch);
1768 if (style->parentMatch != NULL)
1769 xsltFreeCompMatchList(style->parentMatch);
1770 if (style->textMatch != NULL)
1771 xsltFreeCompMatchList(style->textMatch);
1772 if (style->piMatch != NULL)
1773 xsltFreeCompMatchList(style->piMatch);
1774 if (style->commentMatch != NULL)
1775 xsltFreeCompMatchList(style->commentMatch);
1781 * @node: a node in the source tree
1782 * @pattern: an XSLT pattern
1784 * Determine if a node matches a pattern.
1787 xsltMatchPattern(xsltTransformContextPtr context,
1789 const xmlChar *pattern)
1792 xsltCompMatchPtr first, comp;
1794 if ((context != NULL) && (pattern != NULL)) {
1795 first = xsltCompilePattern(pattern);
1796 for (comp = first; comp != NULL; comp = comp->next) {
1797 match = xsltTestCompMatch(context, comp, node, NULL, NULL);
1802 xsltFreeCompMatchList(first);