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"
35 #ifdef WITH_XSLT_DEBUG
36 #define WITH_XSLT_DEBUG_PATTERN
63 typedef struct _xsltStepOp xsltStepOp;
64 typedef xsltStepOp *xsltStepOpPtr;
70 xmlXPathCompExprPtr comp;
72 * Optimisations for count
79 struct _xsltCompMatch {
80 struct _xsltCompMatch *next; /* siblings in the name hash */
81 float priority; /* the priority */
82 const xmlChar *mode; /* the mode */
83 const xmlChar *modeURI; /* the mode URI */
84 xsltTemplatePtr template; /* the associated template */
86 /* TODO fix the statically allocated size steps[] */
89 xmlNsPtr *nsList; /* the namespaces in scope */
90 int nsNr; /* the number of namespaces in scope */
91 xsltStepOp steps[20]; /* ops for computation */
94 typedef struct _xsltParserContext xsltParserContext;
95 typedef xsltParserContext *xsltParserContextPtr;
96 struct _xsltParserContext {
97 const xmlChar *cur; /* the current char being parsed */
98 const xmlChar *base; /* the full expression */
99 xmlDocPtr doc; /* the source document */
100 xmlNodePtr elem; /* the source element */
101 int error; /* error code */
102 xsltCompMatchPtr comp; /* the result */
105 /************************************************************************
109 ************************************************************************/
114 * Create a new XSLT CompMatch
116 * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
118 static xsltCompMatchPtr
119 xsltNewCompMatch(void) {
120 xsltCompMatchPtr cur;
122 cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
124 xsltGenericError(xsltGenericErrorContext,
125 "xsltNewCompMatch : malloc failed\n");
128 memset(cur, 0, sizeof(xsltCompMatch));
137 * @comp: an XSLT comp
139 * Free up the memory allocated by @comp
142 xsltFreeCompMatch(xsltCompMatchPtr comp) {
148 if (comp->mode != NULL)
149 xmlFree((xmlChar *)comp->mode);
150 if (comp->modeURI != NULL)
151 xmlFree((xmlChar *)comp->modeURI);
152 if (comp->nsList != NULL)
153 xmlFree(comp->nsList);
154 for (i = 0;i < comp->nbStep;i++) {
155 op = &comp->steps[i];
156 if (op->value != NULL)
158 if (op->value2 != NULL)
160 if (op->value3 != NULL)
162 if (op->comp != NULL)
163 xmlXPathFreeCompExpr(op->comp);
165 memset(comp, -1, sizeof(xsltCompMatch));
170 * xsltFreeCompMatchList:
171 * @comp: an XSLT comp list
173 * Free up the memory allocated by all the elements of @comp
176 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
177 xsltCompMatchPtr cur;
179 while (comp != NULL) {
182 xsltFreeCompMatch(cur);
187 * xsltNewParserContext:
189 * Create a new XSLT ParserContext
191 * Returns the newly allocated xsltParserContextPtr or NULL in case of error
193 static xsltParserContextPtr
194 xsltNewParserContext(void) {
195 xsltParserContextPtr cur;
197 cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
199 xsltGenericError(xsltGenericErrorContext,
200 "xsltNewParserContext : malloc failed\n");
203 memset(cur, 0, sizeof(xsltParserContext));
208 * xsltFreeParserContext:
209 * @ctxt: an XSLT parser context
211 * Free up the memory allocated by @ctxt
214 xsltFreeParserContext(xsltParserContextPtr ctxt) {
217 memset(ctxt, -1, sizeof(xsltParserContext));
223 * @comp: the compiled match expression
225 * @value: the first value
226 * @value2: the second value
228 * Add an step to an XSLT Compiled Match
230 * Returns -1 in case of failure, 0 otherwise.
233 xsltCompMatchAdd(xsltCompMatchPtr comp, xsltOp op, xmlChar *value,
235 if (comp->nbStep >= 20) {
236 xsltGenericError(xsltGenericErrorContext,
237 "xsltCompMatchAddOp: overflow\n");
240 comp->steps[comp->nbStep].op = op;
241 comp->steps[comp->nbStep].value = value;
242 comp->steps[comp->nbStep].value2 = value2;
248 * xsltSwapTopCompMatch:
249 * @comp: the compiled match expression
251 * reverse the two top steps.
254 xsltSwapTopCompMatch(xsltCompMatchPtr comp) {
256 int j = comp->nbStep - 1;
259 register xmlChar *tmp;
262 tmp = comp->steps[i].value;
263 comp->steps[i].value = comp->steps[j].value;
264 comp->steps[j].value = tmp;
265 tmp = comp->steps[i].value2;
266 comp->steps[i].value2 = comp->steps[j].value2;
267 comp->steps[j].value2 = tmp;
268 op = comp->steps[i].op;
269 comp->steps[i].op = comp->steps[j].op;
270 comp->steps[j].op = op;
275 * xsltReverseCompMatch:
276 * @comp: the compiled match expression
278 * reverse all the stack of expressions
281 xsltReverseCompMatch(xsltCompMatchPtr comp) {
283 int j = comp->nbStep - 1;
286 register xmlChar *tmp;
288 tmp = comp->steps[i].value;
289 comp->steps[i].value = comp->steps[j].value;
290 comp->steps[j].value = tmp;
291 tmp = comp->steps[i].value2;
292 comp->steps[i].value2 = comp->steps[j].value2;
293 comp->steps[j].value2 = tmp;
294 op = comp->steps[i].op;
295 comp->steps[i].op = comp->steps[j].op;
296 comp->steps[j].op = op;
300 comp->steps[comp->nbStep++].op = XSLT_OP_END;
304 * xsltCleanupCompMatch:
305 * @comp: the compiled match expression
307 * remove all computation state from the pattern
310 xsltCleanupCompMatch(xsltCompMatchPtr comp) {
313 for (i = 0;i < comp->nbStep;i++) {
314 comp->steps[i].previous = NULL;
318 /************************************************************************
320 * The interpreter for the precompiled patterns *
322 ************************************************************************/
326 * @ctxt: a XSLT process context
327 * @comp: the precompiled pattern
329 * @mode: the mode name or NULL
330 * @modeURI: the mode URI or NULL
332 * Test wether the node matches the pattern
334 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
337 xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
338 xmlNodePtr node, const xmlChar *mode,
339 const xmlChar *modeURI) {
341 xsltStepOpPtr step, select = NULL;
343 if ((comp == NULL) || (node == NULL) || (ctxt == NULL)) {
344 xsltGenericError(xsltGenericErrorContext,
345 "xsltTestCompMatch: null arg\n");
349 if (comp->mode == NULL)
351 if ((comp->mode != mode) && (!xmlStrEqual(comp->mode, mode)))
354 if (comp->mode != NULL)
357 if (modeURI != NULL) {
358 if (comp->modeURI == NULL)
360 if ((comp->modeURI != modeURI) &&
361 (!xmlStrEqual(comp->modeURI, modeURI)))
364 if (comp->modeURI != NULL)
367 for (i = 0;i < comp->nbStep;i++) {
368 step = &comp->steps[i];
369 if (step->op != XSLT_OP_PREDICATE)
375 if ((node->type == XML_DOCUMENT_NODE) ||
376 (node->type == XML_HTML_DOCUMENT_NODE))
380 if (node->type != XML_ELEMENT_NODE)
382 if (step->value == NULL)
384 if (!xmlStrEqual(step->value, node->name))
388 if (node->ns == NULL) {
389 if (step->value2 != NULL)
391 } else if (node->ns->href != NULL) {
392 if (step->value2 == NULL)
394 if (!xmlStrEqual(step->value2, node->ns->href))
399 TODO /* Handle OP_CHILD */
402 if (node->type != XML_ATTRIBUTE_NODE)
404 if (step->value == NULL)
406 if (!xmlStrEqual(step->value, node->name))
410 if (node->ns == NULL) {
411 if (step->value2 != NULL)
413 } else if (node->ns->href != NULL) {
414 if (step->value2 == NULL)
416 if (!xmlStrEqual(step->value2, node->ns->href))
424 if (step->value == NULL)
426 if (!xmlStrEqual(step->value, node->name))
429 if (node->ns == NULL) {
430 if (step->value2 != NULL)
432 } else if (node->ns->href != NULL) {
433 if (step->value2 == NULL)
435 if (!xmlStrEqual(step->value2, node->ns->href))
439 case XSLT_OP_ANCESTOR:
440 /* TODO: implement coalescing of ANCESTOR/NODE ops */
441 if (step->value == NULL) {
443 step = &comp->steps[i];
444 if (step->op == XSLT_OP_ROOT)
446 if (step->op != XSLT_OP_ELEM)
448 if (step->value == NULL)
454 while (node != NULL) {
457 if (xmlStrEqual(step->value, node->name)) {
459 if (node->ns == NULL) {
460 if (step->value2 == NULL)
462 } else if (node->ns->href != NULL) {
463 if ((step->value2 != NULL) &&
464 (xmlStrEqual(step->value2, node->ns->href)))
474 /* TODO Handle IDs decently, must be done differently */
477 id = xmlGetID(node->doc, step->value);
478 if ((id == NULL) || (id->parent != node))
486 list = xsltGetKey(ctxt, step->value,
487 step->value3, step->value2);
490 for (indx = 0;indx < list->nodeNr;indx++)
491 if (list->nodeTab[indx] == node)
493 if (indx >= list->nodeNr)
499 if (node->ns == NULL) {
500 if (step->value != NULL)
502 } else if (node->ns->href != NULL) {
503 if (step->value == NULL)
505 if (!xmlStrEqual(step->value, node->ns->href))
510 switch (node->type) {
511 case XML_DOCUMENT_NODE:
512 case XML_HTML_DOCUMENT_NODE:
513 case XML_ELEMENT_NODE:
519 case XSLT_OP_PREDICATE: {
522 int pos = 0, len = 0;
524 * Depending on the last selection, one may need to
525 * recompute contextSize and proximityPosition.
527 oldCS = ctxt->xpathCtxt->contextSize;
528 oldCP = ctxt->xpathCtxt->proximityPosition;
529 if ((select != NULL) &&
530 (select->op == XSLT_OP_ELEM) &&
531 (select->value != NULL) &&
532 (node->type == XML_ELEMENT_NODE) &&
533 (node->parent != NULL)) {
535 if ((select->previous != NULL) &&
536 (select->previous->parent == node->parent)) {
538 * just walk back to adjust the index
541 xmlNodePtr sibling = node;
543 while (sibling != NULL) {
544 if (sibling == select->previous)
546 if (xmlStrEqual(node->name, sibling->name)) {
547 if ((select->value2 == NULL) ||
548 ((sibling->ns != NULL) &&
549 (xmlStrEqual(select->value2,
550 sibling->ns->href))))
553 sibling = sibling->prev;
555 if (sibling == NULL) {
556 /* hum going backward in document order ... */
559 while (sibling != NULL) {
560 if (sibling == select->previous)
562 if ((select->value2 == NULL) ||
563 ((sibling->ns != NULL) &&
564 (xmlStrEqual(select->value2,
565 sibling->ns->href))))
567 sibling = sibling->next;
570 if (sibling != NULL) {
571 pos = select->index + indx;
573 select->previous = node;
579 * recompute the index
581 xmlNodePtr siblings = node->parent->children;
583 while (siblings != NULL) {
584 if (siblings->type == XML_ELEMENT_NODE) {
585 if (siblings == node) {
588 } else if (xmlStrEqual(node->name,
590 if ((select->value2 == NULL) ||
591 ((siblings->ns != NULL) &&
592 (xmlStrEqual(select->value2,
593 siblings->ns->href))))
597 siblings = siblings->next;
601 ctxt->xpathCtxt->contextSize = len;
602 ctxt->xpathCtxt->proximityPosition = pos;
603 select->previous = node;
607 } else if ((select != NULL) && (select->op == XSLT_OP_ALL)) {
608 if ((select->previous != NULL) &&
609 (select->previous->parent == node->parent)) {
611 * just walk back to adjust the index
614 xmlNodePtr sibling = node;
616 while (sibling != NULL) {
617 if (sibling == select->previous)
619 if (sibling->type == XML_ELEMENT_NODE)
621 sibling = sibling->prev;
623 if (sibling == NULL) {
624 /* hum going backward in document order ... */
627 while (sibling != NULL) {
628 if (sibling == select->previous)
630 if (sibling->type == XML_ELEMENT_NODE)
632 sibling = sibling->next;
635 if (sibling != NULL) {
636 pos = select->index + indx;
638 select->previous = node;
644 * recompute the index
646 xmlNodePtr siblings = node->parent->children;
648 while (siblings != NULL) {
649 if (siblings->type == XML_ELEMENT_NODE) {
651 if (siblings == node) {
655 siblings = siblings->next;
659 ctxt->xpathCtxt->contextSize = len;
660 ctxt->xpathCtxt->proximityPosition = pos;
661 select->previous = node;
666 oldNode = ctxt->node;
669 if (step->value == NULL)
672 if (step->comp == NULL) {
673 step->comp = xmlXPathCompile(step->value);
674 if (step->comp == NULL)
677 if (comp->nsList == NULL) {
680 comp->nsList = xmlGetNsList(node->doc, node);
681 if (comp->nsList != NULL) {
682 while (comp->nsList[j] != NULL)
687 if (!xsltEvalXPathPredicate(ctxt, step->comp, comp->nsList,
692 ctxt->xpathCtxt->contextSize = oldCS;
693 ctxt->xpathCtxt->proximityPosition = oldCP;
695 ctxt->node = oldNode;
699 ctxt->xpathCtxt->contextSize = oldCS;
700 ctxt->xpathCtxt->proximityPosition = oldCP;
702 ctxt->node = oldNode;
706 if (node->type != XML_PI_NODE)
708 if (step->value != NULL) {
709 if (!xmlStrEqual(step->value, node->name))
713 case XSLT_OP_COMMENT:
714 if (node->type != XML_COMMENT_NODE)
718 if ((node->type != XML_TEXT_NODE) &&
719 (node->type != XML_CDATA_SECTION_NODE))
723 switch (node->type) {
724 case XML_DOCUMENT_NODE:
725 case XML_HTML_DOCUMENT_NODE:
726 case XML_ELEMENT_NODE:
727 case XML_CDATA_SECTION_NODE:
729 case XML_COMMENT_NODE:
731 case XML_ATTRIBUTE_NODE:
743 * xsltTestCompMatchList:
744 * @ctxt: a XSLT process context
746 * @comp: the precompiled pattern list
748 * Test wether the node matches one of the patterns in the list
750 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
753 xsltTestCompMatchList(xsltTransformContextPtr ctxt, xmlNodePtr node,
754 xsltCompMatchPtr comp) {
757 if ((ctxt == NULL) || (node == NULL))
759 while (comp != NULL) {
760 ret = xsltTestCompMatch(ctxt, comp, node, NULL, NULL);
768 /************************************************************************
770 * Dedicated parser for templates *
772 ************************************************************************/
774 #define CUR (*ctxt->cur)
775 #define SKIP(val) ctxt->cur += (val)
776 #define NXT(val) ctxt->cur[(val)]
777 #define CUR_PTR ctxt->cur
779 #define SKIP_BLANKS \
780 while (IS_BLANK(CUR)) NEXT
782 #define CURRENT (*ctxt->cur)
783 #define NEXT ((*ctxt->cur) ? ctxt->cur++: ctxt->cur)
786 #define PUSH(op, val, val2) \
787 if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
790 xsltSwapTopCompMatch(ctxt->comp);
792 #define XSLT_ERROR(X) \
793 { xsltError(ctxt, __FILE__, __LINE__, X); \
794 ctxt->error = (X); return; }
796 #define XSLT_ERROR0(X) \
797 { xsltError(ctxt, __FILE__, __LINE__, X); \
798 ctxt->error = (X); return(0); }
802 * @ctxt: the XPath Parser context
804 * Parse an XPath Litteral:
806 * [29] Literal ::= '"' [^"]* '"'
809 * Returns the Literal parsed or NULL
813 xsltScanLiteral(xsltParserContextPtr ctxt) {
821 while ((IS_CHAR(CUR)) && (CUR != '"'))
824 /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
828 ret = xmlStrndup(q, CUR_PTR - q);
831 } else if (CUR == '\'') {
834 while ((IS_CHAR(CUR)) && (CUR != '\''))
837 /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
841 ret = xmlStrndup(q, CUR_PTR - q);
845 /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
854 * @ctxt: the XPath Parser context
856 * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
857 * CombiningChar | Extender
859 * [5] Name ::= (Letter | '_' | ':') (NameChar)*
861 * [6] Names ::= Name (S Name)*
863 * Returns the Name parsed or NULL
867 xsltScanName(xsltParserContextPtr ctxt) {
868 xmlChar buf[XML_MAX_NAMELEN];
872 if (!IS_LETTER(CUR) && (CUR != '_') &&
877 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
878 (NXT(len) == '.') || (NXT(len) == '-') ||
879 (NXT(len) == '_') || (NXT(len) == ':') ||
880 (IS_COMBINING(NXT(len))) ||
881 (IS_EXTENDER(NXT(len)))) {
884 if (len >= XML_MAX_NAMELEN) {
885 xmlGenericError(xmlGenericErrorContext,
886 "xmlScanName: reached XML_MAX_NAMELEN limit\n");
887 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
888 (NXT(len) == '.') || (NXT(len) == '-') ||
889 (NXT(len) == '_') || (NXT(len) == ':') ||
890 (IS_COMBINING(NXT(len))) ||
891 (IS_EXTENDER(NXT(len))))
897 return(xmlStrndup(buf, len));
902 * @ctxt: the XPath Parser context
904 * Parses a non qualified name
906 * Returns the Name parsed or NULL
910 xsltScanNCName(xsltParserContextPtr ctxt) {
911 xmlChar buf[XML_MAX_NAMELEN];
915 if (!IS_LETTER(CUR) && (CUR != '_')) {
919 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
920 (NXT(len) == '.') || (NXT(len) == '-') ||
922 (IS_COMBINING(NXT(len))) ||
923 (IS_EXTENDER(NXT(len)))) {
926 if (len >= XML_MAX_NAMELEN) {
927 xmlGenericError(xmlGenericErrorContext,
928 "xmlScanNCName: reached XML_MAX_NAMELEN limit\n");
929 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
930 (NXT(len) == '.') || (NXT(len) == '-') ||
932 (IS_COMBINING(NXT(len))) ||
933 (IS_EXTENDER(NXT(len))))
939 return(xmlStrndup(buf, len));
944 * @ctxt: the XPath Parser context
945 * @prefix: the place to store the prefix
947 * Parse a qualified name
949 * Returns the Name parsed or NULL
953 xsltScanQName(xsltParserContextPtr ctxt, xmlChar **prefix) {
957 ret = xsltScanNCName(ctxt);
961 ret = xsltScanNCName(ctxt);
967 * xsltCompileIdKeyPattern:
968 * @comp: the compilation context
969 * @name: a preparsed name
970 * @aid: whether id/key are allowed there
972 * Compile the XSLT LocationIdKeyPattern
973 * [3] IdKeyPattern ::= 'id' '(' Literal ')'
974 * | 'key' '(' Literal ',' Literal ')'
976 * also handle NodeType and PI from:
978 * [7] NodeTest ::= NameTest
980 * | 'processing-instruction' '(' Literal ')'
983 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
985 xmlChar *lit2 = NULL;
988 xsltGenericError(xsltGenericErrorContext,
989 "xsltCompileIdKeyPattern : ( expected\n");
993 if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
996 lit = xsltScanLiteral(ctxt);
1001 xsltGenericError(xsltGenericErrorContext,
1002 "xsltCompileIdKeyPattern : ) expected\n");
1007 PUSH(XSLT_OP_ID, lit, NULL);
1008 } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
1011 lit = xsltScanLiteral(ctxt);
1016 xsltGenericError(xsltGenericErrorContext,
1017 "xsltCompileIdKeyPattern : , expected\n");
1023 lit2 = xsltScanLiteral(ctxt);
1028 xsltGenericError(xsltGenericErrorContext,
1029 "xsltCompileIdKeyPattern : ) expected\n");
1034 /* TODO: support namespace in keys */
1035 PUSH(XSLT_OP_KEY, lit, lit2);
1036 } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
1040 lit = xsltScanLiteral(ctxt);
1045 xsltGenericError(xsltGenericErrorContext,
1046 "xsltCompileIdKeyPattern : ) expected\n");
1052 PUSH(XSLT_OP_PI, lit, NULL);
1053 } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
1057 xsltGenericError(xsltGenericErrorContext,
1058 "xsltCompileIdKeyPattern : ) expected\n");
1063 PUSH(XSLT_OP_TEXT, NULL, NULL);
1064 } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
1068 xsltGenericError(xsltGenericErrorContext,
1069 "xsltCompileIdKeyPattern : ) expected\n");
1074 PUSH(XSLT_OP_COMMENT, NULL, NULL);
1075 } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
1079 xsltGenericError(xsltGenericErrorContext,
1080 "xsltCompileIdKeyPattern : ) expected\n");
1085 PUSH(XSLT_OP_NODE, NULL, NULL);
1087 xsltGenericError(xsltGenericErrorContext,
1088 "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
1092 xsltGenericError(xsltGenericErrorContext,
1093 "xsltCompileIdKeyPattern : node type\n");
1103 * xsltCompileStepPattern:
1104 * @comp: the compilation context
1105 * @token: a posible precompiled name
1107 * Compile the XSLT StepPattern and generates a precompiled
1108 * form suitable for fast matching.
1110 * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
1111 * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
1112 * | ('child' | 'attribute') '::'
1114 * [7] NodeTest ::= NameTest
1115 * | NodeType '(' ')'
1116 * | 'processing-instruction' '(' Literal ')'
1117 * [8] Predicate ::= '[' PredicateExpr ']'
1118 * [9] PredicateExpr ::= Expr
1119 * [13] AbbreviatedAxisSpecifier ::= '@'?
1120 * [37] NameTest ::= '*' | NCName ':' '*' | QName
1124 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1125 xmlChar *name = NULL;
1126 xmlChar *prefix = NULL;
1127 xmlChar *ncname = NULL;
1128 xmlChar *URL = NULL;
1132 if ((token == NULL) && (CUR == '@')) {
1136 PUSH(XSLT_OP_ATTR, NULL, NULL);
1139 token = xsltScanQName(ctxt, &prefix);
1140 if (prefix != NULL) {
1143 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1145 xsltGenericError(xsltGenericErrorContext,
1146 "xsl: pattern, no namespace bound to prefix %s\n",
1149 URL = xmlStrdup(ns->href);
1153 if (token == NULL) {
1156 PUSH(XSLT_OP_ATTR, NULL, URL);
1159 xsltGenericError(xsltGenericErrorContext,
1160 "xsltCompileStepPattern : Name expected\n");
1164 PUSH(XSLT_OP_ATTR, token, URL);
1168 token = xsltScanName(ctxt);
1169 if (token == NULL) {
1172 PUSH(XSLT_OP_ALL, token, NULL);
1173 goto parse_predicate;
1175 xsltGenericError(xsltGenericErrorContext,
1176 "xsltCompileStepPattern : Name expected\n");
1185 xsltCompileIdKeyPattern(ctxt, token, 0);
1188 } else if (CUR == ':') {
1190 if (NXT(1) != ':') {
1191 xsltGenericError(xsltGenericErrorContext,
1192 "xsltCompileStepPattern : sequence '::' expected\n");
1197 if (xmlStrEqual(token, (const xmlChar *) "child")) {
1198 name = xsltScanName(ctxt);
1200 xsltGenericError(xsltGenericErrorContext,
1201 "xsltCompileStepPattern : QName expected\n");
1205 ncname = xmlSplitQName2(name, &prefix);
1206 if (ncname != NULL) {
1207 if (prefix != NULL) {
1210 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1212 xsltGenericError(xsltGenericErrorContext,
1213 "xsl: pattern, no namespace bound to prefix %s\n",
1216 URL = xmlStrdup(ns->href);
1223 PUSH(XSLT_OP_CHILD, name, URL);
1224 } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
1225 name = xsltScanName(ctxt);
1227 xsltGenericError(xsltGenericErrorContext,
1228 "xsltCompileStepPattern : QName expected\n");
1232 ncname = xmlSplitQName2(name, &prefix);
1233 if (ncname != NULL) {
1234 if (prefix != NULL) {
1237 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1239 xsltGenericError(xsltGenericErrorContext,
1240 "xsl: pattern, no namespace bound to prefix %s\n",
1243 URL = xmlStrdup(ns->href);
1250 PUSH(XSLT_OP_ATTR, name, URL);
1252 xsltGenericError(xsltGenericErrorContext,
1253 "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
1258 } else if (CUR == '*') {
1260 PUSH(XSLT_OP_ALL, token, NULL);
1262 ncname = xmlSplitQName2(token, &prefix);
1263 if (ncname != NULL) {
1264 if (prefix != NULL) {
1267 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1269 xsltGenericError(xsltGenericErrorContext,
1270 "xsl: pattern, no namespace bound to prefix %s\n",
1273 URL = xmlStrdup(ns->href);
1280 PUSH(XSLT_OP_ELEM, token, URL);
1285 while (CUR == '[') {
1287 xmlChar *ret = NULL;
1292 /* TODO: avoid breaking in strings ... */
1293 while (IS_CHAR(CUR)) {
1294 /* Skip over nested predicates */
1304 if (!IS_CHAR(CUR)) {
1305 xsltGenericError(xsltGenericErrorContext,
1306 "xsltCompileStepPattern : ']' expected\n");
1310 ret = xmlStrndup(q, CUR_PTR - q);
1311 PUSH(XSLT_OP_PREDICATE, ret, NULL);
1312 /* push the predicate lower than local test */
1325 * xsltCompileRelativePathPattern:
1326 * @comp: the compilation context
1327 * @token: a posible precompiled name
1329 * Compile the XSLT RelativePathPattern and generates a precompiled
1330 * form suitable for fast matching.
1332 * [4] RelativePathPattern ::= StepPattern
1333 * | RelativePathPattern '/' StepPattern
1334 * | RelativePathPattern '//' StepPattern
1337 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1338 xsltCompileStepPattern(ctxt, token);
1342 while ((CUR != 0) && (CUR != '|')) {
1343 if ((CUR == '/') && (NXT(1) == '/')) {
1344 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1348 xsltCompileStepPattern(ctxt, NULL);
1349 } else if (CUR == '/') {
1350 PUSH(XSLT_OP_PARENT, NULL, NULL);
1353 if ((CUR != 0) || (CUR == '|')) {
1354 xsltCompileRelativePathPattern(ctxt, NULL);
1368 * xsltCompileLocationPathPattern:
1369 * @comp: the compilation context
1371 * Compile the XSLT LocationPathPattern and generates a precompiled
1372 * form suitable for fast matching.
1374 * [2] LocationPathPattern ::= '/' RelativePathPattern?
1375 * | IdKeyPattern (('/' | '//') RelativePathPattern)?
1376 * | '//'? RelativePathPattern
1379 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1381 if ((CUR == '/') && (NXT(1) == '/')) {
1383 * since we reverse the query
1384 * a leading // can be safely ignored
1388 xsltCompileRelativePathPattern(ctxt, NULL);
1389 } else if (CUR == '/') {
1391 * We need to find root as the parent
1395 PUSH(XSLT_OP_ROOT, NULL, NULL);
1396 if ((CUR != 0) || (CUR == '|')) {
1397 PUSH(XSLT_OP_PARENT, NULL, NULL);
1398 xsltCompileRelativePathPattern(ctxt, NULL);
1400 } else if (CUR == '*') {
1401 xsltCompileRelativePathPattern(ctxt, NULL);
1402 } else if (CUR == '@') {
1403 xsltCompileRelativePathPattern(ctxt, NULL);
1406 name = xsltScanName(ctxt);
1408 xsltGenericError(xsltGenericErrorContext,
1409 "xsltCompileLocationPathPattern : Name expected\n");
1414 if ((CUR == '(') && !xmlXPathIsNodeType(name)) {
1415 xsltCompileIdKeyPattern(ctxt, name, 1);
1416 if ((CUR == '/') && (NXT(1) == '/')) {
1417 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1421 xsltCompileRelativePathPattern(ctxt, NULL);
1422 } else if (CUR == '/') {
1423 PUSH(XSLT_OP_PARENT, NULL, NULL);
1426 xsltCompileRelativePathPattern(ctxt, NULL);
1430 xsltCompileRelativePathPattern(ctxt, name);
1437 * xsltCompilePattern:
1438 * @pattern: an XSLT pattern
1439 * @doc: the containing document
1440 * @node: the containing element
1442 * Compile the XSLT pattern and generates a list of precompiled form suitable
1443 * for fast matching.
1445 * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1447 * Returns the generated pattern list or NULL in case of failure
1451 xsltCompilePattern(const xmlChar *pattern, xmlDocPtr doc, xmlNodePtr node) {
1452 xsltParserContextPtr ctxt = NULL;
1453 xsltCompMatchPtr element, first = NULL, previous = NULL;
1454 int current, start, end;
1456 if (pattern == NULL) {
1457 xsltGenericError(xsltGenericErrorContext,
1458 "xsltCompilePattern : NULL pattern\n");
1462 #ifdef WITH_XSLT_DEBUG_PATTERN
1463 xsltGenericDebug(xsltGenericDebugContext,
1464 "xsltCompilePattern : parsing '%s'\n", pattern);
1467 ctxt = xsltNewParserContext();
1473 while (pattern[current] != 0) {
1475 while (IS_BLANK(pattern[current]))
1478 while ((pattern[end] != 0) && (pattern[end] != '|'))
1480 if (current == end) {
1481 xsltGenericError(xsltGenericErrorContext,
1482 "xsltCompilePattern : NULL pattern\n");
1485 element = xsltNewCompMatch();
1486 if (element == NULL) {
1491 else if (previous != NULL)
1492 previous->next = element;
1495 ctxt->comp = element;
1496 ctxt->base = xmlStrndup(&pattern[start], end - start);
1497 ctxt->cur = &(ctxt->base)[current - start];
1498 xsltCompileLocationPathPattern(ctxt);
1500 xmlFree((xmlChar *)ctxt->base);
1505 * Reverse for faster interpretation.
1507 xsltReverseCompMatch(element);
1510 * Set-up the priority
1512 if (((element->steps[0].op == XSLT_OP_ELEM) ||
1513 (element->steps[0].op == XSLT_OP_ATTR)) &&
1514 (element->steps[0].value != NULL) &&
1515 (element->steps[1].op == XSLT_OP_END)) {
1516 element->priority = 0;
1517 } else if ((element->steps[0].op == XSLT_OP_ROOT) &&
1518 (element->steps[1].op == XSLT_OP_END)) {
1519 element->priority = 0;
1520 } else if ((element->steps[0].op == XSLT_OP_PI) &&
1521 (element->steps[0].value != NULL) &&
1522 (element->steps[1].op == XSLT_OP_END)) {
1523 element->priority = 0;
1524 } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1525 (element->steps[0].value2 != NULL) &&
1526 (element->steps[1].op == XSLT_OP_END)) {
1527 element->priority = -0.25;
1528 } else if ((element->steps[0].op == XSLT_OP_NS) &&
1529 (element->steps[0].value != NULL) &&
1530 (element->steps[1].op == XSLT_OP_END)) {
1531 element->priority = -0.25;
1532 } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1533 (element->steps[0].value == NULL) &&
1534 (element->steps[0].value2 == NULL) &&
1535 (element->steps[1].op == XSLT_OP_END)) {
1536 element->priority = -0.5;
1537 } else if (((element->steps[0].op == XSLT_OP_PI) ||
1538 (element->steps[0].op == XSLT_OP_TEXT) ||
1539 (element->steps[0].op == XSLT_OP_ALL) ||
1540 (element->steps[0].op == XSLT_OP_NODE) ||
1541 (element->steps[0].op == XSLT_OP_COMMENT)) &&
1542 (element->steps[1].op == XSLT_OP_END)) {
1543 element->priority = -0.5;
1545 element->priority = 0.5;
1547 if (pattern[end] == '|')
1552 xsltGenericError(xsltGenericErrorContext,
1553 "xsltCompilePattern : NULL pattern\n");
1557 xsltFreeParserContext(ctxt);
1562 xsltFreeParserContext(ctxt);
1564 xsltFreeCompMatchList(first);
1568 /************************************************************************
1570 * Module interfaces *
1572 ************************************************************************/
1576 * @style: an XSLT stylesheet
1577 * @cur: an XSLT template
1578 * @mode: the mode name or NULL
1579 * @modeURI: the mode URI or NULL
1581 * Register the XSLT pattern associated to @cur
1583 * Returns -1 in case of error, 0 otherwise
1586 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1587 const xmlChar *mode, const xmlChar *modeURI) {
1588 xsltCompMatchPtr pat, list, *top = NULL, next;
1589 const xmlChar *name = NULL;
1591 if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1594 pat = xsltCompilePattern(cur->match, style->doc, cur->elem);
1599 pat->template = cur;
1601 pat->mode = xmlStrdup(mode);
1602 if (modeURI != NULL)
1603 pat->modeURI = xmlStrdup(modeURI);
1604 if (cur->priority == XSLT_PAT_NO_PRIORITY)
1605 cur->priority = pat->priority;
1607 pat->priority = cur->priority;
1610 * insert it in the hash table list corresponding to its lookup name
1612 switch (pat->steps[0].op) {
1614 if (pat->steps[0].value != NULL)
1615 name = pat->steps[0].value;
1617 top = (xsltCompMatchPtr *) &(style->attrMatch);
1621 case XSLT_OP_PARENT:
1622 case XSLT_OP_ANCESTOR:
1624 name = pat->steps[0].value;
1627 top = (xsltCompMatchPtr *) &(style->rootMatch);
1630 top = (xsltCompMatchPtr *) &(style->keyMatch);
1633 /* TODO optimize ID !!! */
1635 top = (xsltCompMatchPtr *) &(style->elemMatch);
1638 case XSLT_OP_PREDICATE:
1639 xsltGenericError(xsltGenericErrorContext,
1640 "xsltAddTemplate: invalid compiled pattern\n");
1641 xsltFreeCompMatch(pat);
1644 * TODO: some flags at the top level about type based patterns
1645 * would be faster than inclusion in the hash table.
1648 if (pat->steps[0].value != NULL)
1649 name = pat->steps[0].value;
1651 top = (xsltCompMatchPtr *) &(style->piMatch);
1653 case XSLT_OP_COMMENT:
1654 top = (xsltCompMatchPtr *) &(style->commentMatch);
1657 top = (xsltCompMatchPtr *) &(style->textMatch);
1660 if (pat->steps[0].value != NULL)
1661 name = pat->steps[0].value;
1663 top = (xsltCompMatchPtr *) &(style->elemMatch);
1668 if (style->templatesHash == NULL) {
1669 style->templatesHash = xmlHashCreate(1024);
1670 if (style->templatesHash == NULL) {
1671 xsltFreeCompMatch(pat);
1674 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1676 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1677 name, mode, modeURI);
1679 xmlHashAddEntry3(style->templatesHash, name,
1680 mode, modeURI, pat);
1683 * Note '<=' since one must choose among the matching
1684 * template rules that are left, the one that occurs
1685 * last in the stylesheet
1687 if (list->priority <= pat->priority) {
1689 xmlHashUpdateEntry3(style->templatesHash, name,
1690 mode, modeURI, pat, NULL);
1692 while (list->next != NULL) {
1693 if (list->next->priority <= pat->priority)
1697 pat->next = list->next;
1702 } else if (top != NULL) {
1707 } else if (list->priority <= pat->priority) {
1711 while (list->next != NULL) {
1712 if (list->next->priority <= pat->priority)
1716 pat->next = list->next;
1720 xsltGenericError(xsltGenericErrorContext,
1721 "xsltAddTemplate: invalid compiled pattern\n");
1722 xsltFreeCompMatch(pat);
1725 #ifdef WITH_XSLT_DEBUG_PATTERN
1727 xsltGenericDebug(xsltGenericDebugContext,
1728 "added pattern : '%s' mode '%s' priority %f\n",
1729 pat->template->match, pat->mode, pat->priority);
1731 xsltGenericDebug(xsltGenericDebugContext,
1732 "added pattern : '%s' priority %f\n",
1733 pat->template->match, pat->priority);
1743 * @ctxt: a XSLT process context
1745 * @style: the current style
1747 * Finds the template applying to this node, if @style is non-NULL
1748 * it means one need to look for the next imported template in scope.
1750 * Returns the xsltTemplatePtr or NULL if not found
1753 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
1754 xsltStylesheetPtr style) {
1755 xsltStylesheetPtr curstyle;
1756 xsltTemplatePtr ret = NULL;
1757 const xmlChar *name = NULL;
1758 xsltCompMatchPtr list = NULL;
1760 if ((ctxt == NULL) || (node == NULL))
1763 if (style == NULL) {
1764 curstyle = ctxt->style;
1766 curstyle = xsltNextImport(style);
1769 while ((curstyle != NULL) && (curstyle != style)) {
1770 /* TODO : handle IDs/keys here ! */
1771 if (curstyle->templatesHash != NULL) {
1773 * Use the top name as selector
1775 switch (node->type) {
1776 case XML_ELEMENT_NODE:
1777 case XML_ATTRIBUTE_NODE:
1781 case XML_DOCUMENT_NODE:
1782 case XML_HTML_DOCUMENT_NODE:
1784 case XML_CDATA_SECTION_NODE:
1785 case XML_COMMENT_NODE:
1786 case XML_ENTITY_REF_NODE:
1787 case XML_ENTITY_NODE:
1788 case XML_DOCUMENT_TYPE_NODE:
1789 case XML_DOCUMENT_FRAG_NODE:
1790 case XML_NOTATION_NODE:
1792 case XML_ELEMENT_DECL:
1793 case XML_ATTRIBUTE_DECL:
1794 case XML_ENTITY_DECL:
1795 case XML_NAMESPACE_DECL:
1796 case XML_XINCLUDE_START:
1797 case XML_XINCLUDE_END:
1806 * find the list of appliable expressions based on the name
1808 list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
1809 name, ctxt->mode, ctxt->modeURI);
1812 while (list != NULL) {
1813 if (xsltTestCompMatch(ctxt, list, node,
1814 ctxt->mode, ctxt->modeURI)) {
1815 ret = list->template;
1823 * find alternate generic matches
1825 switch (node->type) {
1826 case XML_ELEMENT_NODE:
1827 list = curstyle->elemMatch;
1829 case XML_ATTRIBUTE_NODE:
1830 list = curstyle->attrMatch;
1833 list = curstyle->piMatch;
1835 case XML_DOCUMENT_NODE:
1836 case XML_HTML_DOCUMENT_NODE:
1837 list = curstyle->rootMatch;
1840 case XML_CDATA_SECTION_NODE:
1841 list = curstyle->textMatch;
1843 case XML_COMMENT_NODE:
1844 list = curstyle->commentMatch;
1846 case XML_ENTITY_REF_NODE:
1847 case XML_ENTITY_NODE:
1848 case XML_DOCUMENT_TYPE_NODE:
1849 case XML_DOCUMENT_FRAG_NODE:
1850 case XML_NOTATION_NODE:
1852 case XML_ELEMENT_DECL:
1853 case XML_ATTRIBUTE_DECL:
1854 case XML_ENTITY_DECL:
1855 case XML_NAMESPACE_DECL:
1856 case XML_XINCLUDE_START:
1857 case XML_XINCLUDE_END:
1863 while ((list != NULL) &&
1864 ((ret == NULL) || (list->priority > ret->priority))) {
1865 if (xsltTestCompMatch(ctxt, list, node,
1866 ctxt->mode, ctxt->modeURI)) {
1867 ret = list->template;
1872 if (node->_private != NULL) {
1873 list = curstyle->keyMatch;
1874 while ((list != NULL) &&
1875 ((ret == NULL) || (list->priority > ret->priority))) {
1876 if (xsltTestCompMatch(ctxt, list, node,
1877 ctxt->mode, ctxt->modeURI)) {
1878 ret = list->template;
1888 * Cycle on next curstylesheet import.
1890 curstyle = xsltNextImport(curstyle);
1896 * xsltCleanupTemplates:
1897 * @style: an XSLT stylesheet
1899 * Cleanup the state of the templates used by the stylesheet and
1900 * the ones it imports.
1903 xsltCleanupTemplates(xsltStylesheetPtr style) {
1904 while (style != NULL) {
1905 xmlHashScan((xmlHashTablePtr) style->templatesHash,
1906 (xmlHashScanner) xsltCleanupCompMatch, NULL);
1908 style = xsltNextImport(style);
1913 * xsltFreeTemplateHashes:
1914 * @style: an XSLT stylesheet
1916 * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1919 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1920 if (style->templatesHash != NULL)
1921 xmlHashFree((xmlHashTablePtr) style->templatesHash,
1922 (xmlHashDeallocator) xsltFreeCompMatchList);
1923 if (style->rootMatch != NULL)
1924 xsltFreeCompMatchList(style->rootMatch);
1925 if (style->keyMatch != NULL)
1926 xsltFreeCompMatchList(style->keyMatch);
1927 if (style->elemMatch != NULL)
1928 xsltFreeCompMatchList(style->elemMatch);
1929 if (style->attrMatch != NULL)
1930 xsltFreeCompMatchList(style->attrMatch);
1931 if (style->parentMatch != NULL)
1932 xsltFreeCompMatchList(style->parentMatch);
1933 if (style->textMatch != NULL)
1934 xsltFreeCompMatchList(style->textMatch);
1935 if (style->piMatch != NULL)
1936 xsltFreeCompMatchList(style->piMatch);
1937 if (style->commentMatch != NULL)
1938 xsltFreeCompMatchList(style->commentMatch);
1944 * @node: a node in the source tree
1945 * @pattern: an XSLT pattern
1947 * Determine if a node matches a pattern.
1950 xsltMatchPattern(xsltTransformContextPtr context,
1952 const xmlChar *pattern)
1955 xsltCompMatchPtr first, comp;
1957 if ((context != NULL) && (pattern != NULL)) {
1958 first = xsltCompilePattern(pattern);
1959 for (comp = first; comp != NULL; comp = comp->next) {
1960 match = xsltTestCompMatch(context, comp, node, NULL, NULL);
1965 xsltFreeCompMatchList(first);