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.
13 * TODO: handle pathological cases like *[*[@a="b"]]
14 * TODO: detect [number] at compilation, optimize accordingly
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 *pattern; /* the pattern */
83 const xmlChar *mode; /* the mode */
84 const xmlChar *modeURI; /* the mode URI */
85 xsltTemplatePtr template; /* the associated template */
87 /* TODO fix the statically allocated size steps[] */
90 xmlNsPtr *nsList; /* the namespaces in scope */
91 int nsNr; /* the number of namespaces in scope */
92 xsltStepOp steps[20]; /* ops for computation */
95 typedef struct _xsltParserContext xsltParserContext;
96 typedef xsltParserContext *xsltParserContextPtr;
97 struct _xsltParserContext {
98 const xmlChar *cur; /* the current char being parsed */
99 const xmlChar *base; /* the full expression */
100 xmlDocPtr doc; /* the source document */
101 xmlNodePtr elem; /* the source element */
102 int error; /* error code */
103 xsltCompMatchPtr comp; /* the result */
106 /************************************************************************
110 ************************************************************************/
115 * Create a new XSLT CompMatch
117 * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
119 static xsltCompMatchPtr
120 xsltNewCompMatch(void) {
121 xsltCompMatchPtr cur;
123 cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
125 xsltGenericError(xsltGenericErrorContext,
126 "xsltNewCompMatch : malloc failed\n");
129 memset(cur, 0, sizeof(xsltCompMatch));
138 * @comp: an XSLT comp
140 * Free up the memory allocated by @comp
143 xsltFreeCompMatch(xsltCompMatchPtr comp) {
149 if (comp->pattern != NULL)
150 xmlFree((xmlChar *)comp->pattern);
151 if (comp->mode != NULL)
152 xmlFree((xmlChar *)comp->mode);
153 if (comp->modeURI != NULL)
154 xmlFree((xmlChar *)comp->modeURI);
155 if (comp->nsList != NULL)
156 xmlFree(comp->nsList);
157 for (i = 0;i < comp->nbStep;i++) {
158 op = &comp->steps[i];
159 if (op->value != NULL)
161 if (op->value2 != NULL)
163 if (op->value3 != NULL)
165 if (op->comp != NULL)
166 xmlXPathFreeCompExpr(op->comp);
168 memset(comp, -1, sizeof(xsltCompMatch));
173 * xsltFreeCompMatchList:
174 * @comp: an XSLT comp list
176 * Free up the memory allocated by all the elements of @comp
179 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
180 xsltCompMatchPtr cur;
182 while (comp != NULL) {
185 xsltFreeCompMatch(cur);
190 * xsltNewParserContext:
192 * Create a new XSLT ParserContext
194 * Returns the newly allocated xsltParserContextPtr or NULL in case of error
196 static xsltParserContextPtr
197 xsltNewParserContext(void) {
198 xsltParserContextPtr cur;
200 cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
202 xsltGenericError(xsltGenericErrorContext,
203 "xsltNewParserContext : malloc failed\n");
206 memset(cur, 0, sizeof(xsltParserContext));
211 * xsltFreeParserContext:
212 * @ctxt: an XSLT parser context
214 * Free up the memory allocated by @ctxt
217 xsltFreeParserContext(xsltParserContextPtr ctxt) {
220 memset(ctxt, -1, sizeof(xsltParserContext));
226 * @comp: the compiled match expression
228 * @value: the first value
229 * @value2: the second value
231 * Add an step to an XSLT Compiled Match
233 * Returns -1 in case of failure, 0 otherwise.
236 xsltCompMatchAdd(xsltCompMatchPtr comp, xsltOp op, xmlChar *value,
238 if (comp->nbStep >= 20) {
239 xsltGenericError(xsltGenericErrorContext,
240 "xsltCompMatchAddOp: overflow\n");
243 comp->steps[comp->nbStep].op = op;
244 comp->steps[comp->nbStep].value = value;
245 comp->steps[comp->nbStep].value2 = value2;
251 * xsltSwapTopCompMatch:
252 * @comp: the compiled match expression
254 * reverse the two top steps.
257 xsltSwapTopCompMatch(xsltCompMatchPtr comp) {
259 int j = comp->nbStep - 1;
262 register xmlChar *tmp;
265 tmp = comp->steps[i].value;
266 comp->steps[i].value = comp->steps[j].value;
267 comp->steps[j].value = tmp;
268 tmp = comp->steps[i].value2;
269 comp->steps[i].value2 = comp->steps[j].value2;
270 comp->steps[j].value2 = tmp;
271 op = comp->steps[i].op;
272 comp->steps[i].op = comp->steps[j].op;
273 comp->steps[j].op = op;
278 * xsltReverseCompMatch:
279 * @comp: the compiled match expression
281 * reverse all the stack of expressions
284 xsltReverseCompMatch(xsltCompMatchPtr comp) {
286 int j = comp->nbStep - 1;
289 register xmlChar *tmp;
291 tmp = comp->steps[i].value;
292 comp->steps[i].value = comp->steps[j].value;
293 comp->steps[j].value = tmp;
294 tmp = comp->steps[i].value2;
295 comp->steps[i].value2 = comp->steps[j].value2;
296 comp->steps[j].value2 = tmp;
297 op = comp->steps[i].op;
298 comp->steps[i].op = comp->steps[j].op;
299 comp->steps[j].op = op;
303 comp->steps[comp->nbStep++].op = XSLT_OP_END;
307 * xsltCleanupCompMatch:
308 * @comp: the compiled match expression
310 * remove all computation state from the pattern
313 xsltCleanupCompMatch(xsltCompMatchPtr comp) {
316 for (i = 0;i < comp->nbStep;i++) {
317 comp->steps[i].previous = NULL;
321 /************************************************************************
323 * The interpreter for the precompiled patterns *
325 ************************************************************************/
329 * @ctxt: a XSLT process context
330 * @comp: the precompiled pattern
332 * @mode: the mode name or NULL
333 * @modeURI: the mode URI or NULL
335 * Test wether the node matches the pattern
337 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
340 xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
341 xmlNodePtr node, const xmlChar *mode,
342 const xmlChar *modeURI) {
344 xsltStepOpPtr step, select = NULL;
346 if ((comp == NULL) || (node == NULL) || (ctxt == NULL)) {
347 xsltGenericError(xsltGenericErrorContext,
348 "xsltTestCompMatch: null arg\n");
352 if (comp->mode == NULL)
354 if ((comp->mode != mode) && (!xmlStrEqual(comp->mode, mode)))
357 if (comp->mode != NULL)
360 if (modeURI != NULL) {
361 if (comp->modeURI == NULL)
363 if ((comp->modeURI != modeURI) &&
364 (!xmlStrEqual(comp->modeURI, modeURI)))
367 if (comp->modeURI != NULL)
370 for (i = 0;i < comp->nbStep;i++) {
371 step = &comp->steps[i];
372 if (step->op != XSLT_OP_PREDICATE)
378 if ((node->type == XML_DOCUMENT_NODE) ||
379 (node->type == XML_HTML_DOCUMENT_NODE))
383 if (node->type != XML_ELEMENT_NODE)
385 if (step->value == NULL)
387 if (!xmlStrEqual(step->value, node->name))
391 if (node->ns == NULL) {
392 if (step->value2 != NULL)
394 } else if (node->ns->href != NULL) {
395 if (step->value2 == NULL)
397 if (!xmlStrEqual(step->value2, node->ns->href))
402 TODO /* Handle OP_CHILD */
405 if (node->type != XML_ATTRIBUTE_NODE)
407 if (step->value == NULL)
409 if (!xmlStrEqual(step->value, node->name))
413 if (node->ns == NULL) {
414 if (step->value2 != NULL)
416 } else if (node->ns->href != NULL) {
417 if (step->value2 == NULL)
419 if (!xmlStrEqual(step->value2, node->ns->href))
427 if (step->value == NULL)
429 if (!xmlStrEqual(step->value, node->name))
432 if (node->ns == NULL) {
433 if (step->value2 != NULL)
435 } else if (node->ns->href != NULL) {
436 if (step->value2 == NULL)
438 if (!xmlStrEqual(step->value2, node->ns->href))
442 case XSLT_OP_ANCESTOR:
443 /* TODO: implement coalescing of ANCESTOR/NODE ops */
444 if (step->value == NULL) {
446 step = &comp->steps[i];
447 if (step->op == XSLT_OP_ROOT)
449 if (step->op != XSLT_OP_ELEM)
451 if (step->value == NULL)
457 while (node != NULL) {
460 if (xmlStrEqual(step->value, node->name)) {
462 if (node->ns == NULL) {
463 if (step->value2 == NULL)
465 } else if (node->ns->href != NULL) {
466 if ((step->value2 != NULL) &&
467 (xmlStrEqual(step->value2, node->ns->href)))
477 /* TODO Handle IDs decently, must be done differently */
480 id = xmlGetID(node->doc, step->value);
481 if ((id == NULL) || (id->parent != node))
489 list = xsltGetKey(ctxt, step->value,
490 step->value3, step->value2);
493 for (indx = 0;indx < list->nodeNr;indx++)
494 if (list->nodeTab[indx] == node)
496 if (indx >= list->nodeNr)
502 if (node->ns == NULL) {
503 if (step->value != NULL)
505 } else if (node->ns->href != NULL) {
506 if (step->value == NULL)
508 if (!xmlStrEqual(step->value, node->ns->href))
513 switch (node->type) {
514 case XML_DOCUMENT_NODE:
515 case XML_HTML_DOCUMENT_NODE:
516 case XML_ELEMENT_NODE:
522 case XSLT_OP_PREDICATE: {
525 int pos = 0, len = 0;
527 * Depending on the last selection, one may need to
528 * recompute contextSize and proximityPosition.
530 oldCS = ctxt->xpathCtxt->contextSize;
531 oldCP = ctxt->xpathCtxt->proximityPosition;
532 if ((select != NULL) &&
533 (select->op == XSLT_OP_ELEM) &&
534 (select->value != NULL) &&
535 (node->type == XML_ELEMENT_NODE) &&
536 (node->parent != NULL)) {
538 if ((select->previous != NULL) &&
539 (select->previous->parent == node->parent)) {
541 * just walk back to adjust the index
544 xmlNodePtr sibling = node;
546 while (sibling != NULL) {
547 if (sibling == select->previous)
549 if (xmlStrEqual(node->name, sibling->name)) {
550 if ((select->value2 == NULL) ||
551 ((sibling->ns != NULL) &&
552 (xmlStrEqual(select->value2,
553 sibling->ns->href))))
556 sibling = sibling->prev;
558 if (sibling == NULL) {
559 /* hum going backward in document order ... */
562 while (sibling != NULL) {
563 if (sibling == select->previous)
565 if ((select->value2 == NULL) ||
566 ((sibling->ns != NULL) &&
567 (xmlStrEqual(select->value2,
568 sibling->ns->href))))
570 sibling = sibling->next;
573 if (sibling != NULL) {
574 pos = select->index + indx;
576 select->previous = node;
582 * recompute the index
584 xmlNodePtr siblings = node->parent->children;
586 while (siblings != NULL) {
587 if (siblings->type == XML_ELEMENT_NODE) {
588 if (siblings == node) {
591 } else if (xmlStrEqual(node->name,
593 if ((select->value2 == NULL) ||
594 ((siblings->ns != NULL) &&
595 (xmlStrEqual(select->value2,
596 siblings->ns->href))))
600 siblings = siblings->next;
604 ctxt->xpathCtxt->contextSize = len;
605 ctxt->xpathCtxt->proximityPosition = pos;
606 select->previous = node;
610 } else if ((select != NULL) && (select->op == XSLT_OP_ALL)) {
611 if ((select->previous != NULL) &&
612 (select->previous->parent == node->parent)) {
614 * just walk back to adjust the index
617 xmlNodePtr sibling = node;
619 while (sibling != NULL) {
620 if (sibling == select->previous)
622 if (sibling->type == XML_ELEMENT_NODE)
624 sibling = sibling->prev;
626 if (sibling == NULL) {
627 /* hum going backward in document order ... */
630 while (sibling != NULL) {
631 if (sibling == select->previous)
633 if (sibling->type == XML_ELEMENT_NODE)
635 sibling = sibling->next;
638 if (sibling != NULL) {
639 pos = select->index + indx;
641 select->previous = node;
647 * recompute the index
649 xmlNodePtr siblings = node->parent->children;
651 while (siblings != NULL) {
652 if (siblings->type == XML_ELEMENT_NODE) {
654 if (siblings == node) {
658 siblings = siblings->next;
662 ctxt->xpathCtxt->contextSize = len;
663 ctxt->xpathCtxt->proximityPosition = pos;
664 select->previous = node;
669 oldNode = ctxt->node;
672 if (step->value == NULL)
675 if (step->comp == NULL) {
676 step->comp = xmlXPathCompile(step->value);
677 if (step->comp == NULL)
680 if (comp->nsList == NULL) {
683 comp->nsList = xmlGetNsList(node->doc, node);
684 if (comp->nsList != NULL) {
685 while (comp->nsList[j] != NULL)
690 if (!xsltEvalXPathPredicate(ctxt, step->comp, comp->nsList,
695 ctxt->xpathCtxt->contextSize = oldCS;
696 ctxt->xpathCtxt->proximityPosition = oldCP;
698 ctxt->node = oldNode;
702 ctxt->xpathCtxt->contextSize = oldCS;
703 ctxt->xpathCtxt->proximityPosition = oldCP;
705 ctxt->node = oldNode;
709 if (node->type != XML_PI_NODE)
711 if (step->value != NULL) {
712 if (!xmlStrEqual(step->value, node->name))
716 case XSLT_OP_COMMENT:
717 if (node->type != XML_COMMENT_NODE)
721 if ((node->type != XML_TEXT_NODE) &&
722 (node->type != XML_CDATA_SECTION_NODE))
726 switch (node->type) {
727 case XML_DOCUMENT_NODE:
728 case XML_HTML_DOCUMENT_NODE:
729 case XML_ELEMENT_NODE:
730 case XML_CDATA_SECTION_NODE:
732 case XML_COMMENT_NODE:
734 case XML_ATTRIBUTE_NODE:
746 * xsltTestCompMatchList:
747 * @ctxt: a XSLT process context
749 * @comp: the precompiled pattern list
751 * Test wether the node matches one of the patterns in the list
753 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
756 xsltTestCompMatchList(xsltTransformContextPtr ctxt, xmlNodePtr node,
757 xsltCompMatchPtr comp) {
760 if ((ctxt == NULL) || (node == NULL))
762 while (comp != NULL) {
763 ret = xsltTestCompMatch(ctxt, comp, node, NULL, NULL);
771 /************************************************************************
773 * Dedicated parser for templates *
775 ************************************************************************/
777 #define CUR (*ctxt->cur)
778 #define SKIP(val) ctxt->cur += (val)
779 #define NXT(val) ctxt->cur[(val)]
780 #define CUR_PTR ctxt->cur
782 #define SKIP_BLANKS \
783 while (IS_BLANK(CUR)) NEXT
785 #define CURRENT (*ctxt->cur)
786 #define NEXT ((*ctxt->cur) ? ctxt->cur++: ctxt->cur)
789 #define PUSH(op, val, val2) \
790 if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
793 xsltSwapTopCompMatch(ctxt->comp);
795 #define XSLT_ERROR(X) \
796 { xsltError(ctxt, __FILE__, __LINE__, X); \
797 ctxt->error = (X); return; }
799 #define XSLT_ERROR0(X) \
800 { xsltError(ctxt, __FILE__, __LINE__, X); \
801 ctxt->error = (X); return(0); }
805 * @ctxt: the XPath Parser context
807 * Parse an XPath Litteral:
809 * [29] Literal ::= '"' [^"]* '"'
812 * Returns the Literal parsed or NULL
816 xsltScanLiteral(xsltParserContextPtr ctxt) {
824 while ((IS_CHAR(CUR)) && (CUR != '"'))
827 /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
831 ret = xmlStrndup(q, CUR_PTR - q);
834 } else if (CUR == '\'') {
837 while ((IS_CHAR(CUR)) && (CUR != '\''))
840 /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
844 ret = xmlStrndup(q, CUR_PTR - q);
848 /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
857 * @ctxt: the XPath Parser context
859 * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
860 * CombiningChar | Extender
862 * [5] Name ::= (Letter | '_' | ':') (NameChar)*
864 * [6] Names ::= Name (S Name)*
866 * Returns the Name parsed or NULL
870 xsltScanName(xsltParserContextPtr ctxt) {
871 xmlChar buf[XML_MAX_NAMELEN];
875 if (!IS_LETTER(CUR) && (CUR != '_') &&
880 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
881 (NXT(len) == '.') || (NXT(len) == '-') ||
882 (NXT(len) == '_') || (NXT(len) == ':') ||
883 (IS_COMBINING(NXT(len))) ||
884 (IS_EXTENDER(NXT(len)))) {
887 if (len >= XML_MAX_NAMELEN) {
888 xmlGenericError(xmlGenericErrorContext,
889 "xmlScanName: reached XML_MAX_NAMELEN limit\n");
890 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
891 (NXT(len) == '.') || (NXT(len) == '-') ||
892 (NXT(len) == '_') || (NXT(len) == ':') ||
893 (IS_COMBINING(NXT(len))) ||
894 (IS_EXTENDER(NXT(len))))
900 return(xmlStrndup(buf, len));
905 * @ctxt: the XPath Parser context
907 * Parses a non qualified name
909 * Returns the Name parsed or NULL
913 xsltScanNCName(xsltParserContextPtr ctxt) {
914 xmlChar buf[XML_MAX_NAMELEN];
918 if (!IS_LETTER(CUR) && (CUR != '_')) {
922 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
923 (NXT(len) == '.') || (NXT(len) == '-') ||
925 (IS_COMBINING(NXT(len))) ||
926 (IS_EXTENDER(NXT(len)))) {
929 if (len >= XML_MAX_NAMELEN) {
930 xmlGenericError(xmlGenericErrorContext,
931 "xmlScanNCName: reached XML_MAX_NAMELEN limit\n");
932 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
933 (NXT(len) == '.') || (NXT(len) == '-') ||
935 (IS_COMBINING(NXT(len))) ||
936 (IS_EXTENDER(NXT(len))))
942 return(xmlStrndup(buf, len));
947 * @ctxt: the XPath Parser context
948 * @prefix: the place to store the prefix
950 * Parse a qualified name
952 * Returns the Name parsed or NULL
956 xsltScanQName(xsltParserContextPtr ctxt, xmlChar **prefix) {
960 ret = xsltScanNCName(ctxt);
964 ret = xsltScanNCName(ctxt);
970 * xsltCompileIdKeyPattern:
971 * @comp: the compilation context
972 * @name: a preparsed name
973 * @aid: whether id/key are allowed there
975 * Compile the XSLT LocationIdKeyPattern
976 * [3] IdKeyPattern ::= 'id' '(' Literal ')'
977 * | 'key' '(' Literal ',' Literal ')'
979 * also handle NodeType and PI from:
981 * [7] NodeTest ::= NameTest
983 * | 'processing-instruction' '(' Literal ')'
986 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
988 xmlChar *lit2 = NULL;
991 xsltGenericError(xsltGenericErrorContext,
992 "xsltCompileIdKeyPattern : ( expected\n");
996 if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
999 lit = xsltScanLiteral(ctxt);
1004 xsltGenericError(xsltGenericErrorContext,
1005 "xsltCompileIdKeyPattern : ) expected\n");
1010 PUSH(XSLT_OP_ID, lit, NULL);
1011 } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
1014 lit = xsltScanLiteral(ctxt);
1019 xsltGenericError(xsltGenericErrorContext,
1020 "xsltCompileIdKeyPattern : , expected\n");
1026 lit2 = xsltScanLiteral(ctxt);
1031 xsltGenericError(xsltGenericErrorContext,
1032 "xsltCompileIdKeyPattern : ) expected\n");
1037 /* TODO: support namespace in keys */
1038 PUSH(XSLT_OP_KEY, lit, lit2);
1039 } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
1043 lit = xsltScanLiteral(ctxt);
1048 xsltGenericError(xsltGenericErrorContext,
1049 "xsltCompileIdKeyPattern : ) expected\n");
1055 PUSH(XSLT_OP_PI, lit, NULL);
1056 } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
1060 xsltGenericError(xsltGenericErrorContext,
1061 "xsltCompileIdKeyPattern : ) expected\n");
1066 PUSH(XSLT_OP_TEXT, NULL, NULL);
1067 } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
1071 xsltGenericError(xsltGenericErrorContext,
1072 "xsltCompileIdKeyPattern : ) expected\n");
1077 PUSH(XSLT_OP_COMMENT, NULL, NULL);
1078 } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
1082 xsltGenericError(xsltGenericErrorContext,
1083 "xsltCompileIdKeyPattern : ) expected\n");
1088 PUSH(XSLT_OP_NODE, NULL, NULL);
1090 xsltGenericError(xsltGenericErrorContext,
1091 "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
1095 xsltGenericError(xsltGenericErrorContext,
1096 "xsltCompileIdKeyPattern : node type\n");
1106 * xsltCompileStepPattern:
1107 * @comp: the compilation context
1108 * @token: a posible precompiled name
1110 * Compile the XSLT StepPattern and generates a precompiled
1111 * form suitable for fast matching.
1113 * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
1114 * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
1115 * | ('child' | 'attribute') '::'
1117 * [7] NodeTest ::= NameTest
1118 * | NodeType '(' ')'
1119 * | 'processing-instruction' '(' Literal ')'
1120 * [8] Predicate ::= '[' PredicateExpr ']'
1121 * [9] PredicateExpr ::= Expr
1122 * [13] AbbreviatedAxisSpecifier ::= '@'?
1123 * [37] NameTest ::= '*' | NCName ':' '*' | QName
1127 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1128 xmlChar *name = NULL;
1129 xmlChar *prefix = NULL;
1130 xmlChar *ncname = NULL;
1131 xmlChar *URL = NULL;
1135 if ((token == NULL) && (CUR == '@')) {
1139 PUSH(XSLT_OP_ATTR, NULL, NULL);
1142 token = xsltScanQName(ctxt, &prefix);
1143 if (prefix != NULL) {
1146 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1148 xsltGenericError(xsltGenericErrorContext,
1149 "xsl: pattern, no namespace bound to prefix %s\n",
1152 URL = xmlStrdup(ns->href);
1156 if (token == NULL) {
1159 PUSH(XSLT_OP_ATTR, NULL, URL);
1162 xsltGenericError(xsltGenericErrorContext,
1163 "xsltCompileStepPattern : Name expected\n");
1167 PUSH(XSLT_OP_ATTR, token, URL);
1171 token = xsltScanName(ctxt);
1172 if (token == NULL) {
1175 PUSH(XSLT_OP_ALL, token, NULL);
1176 goto parse_predicate;
1178 xsltGenericError(xsltGenericErrorContext,
1179 "xsltCompileStepPattern : Name expected\n");
1188 xsltCompileIdKeyPattern(ctxt, token, 0);
1191 } else if (CUR == ':') {
1193 if (NXT(1) != ':') {
1194 xsltGenericError(xsltGenericErrorContext,
1195 "xsltCompileStepPattern : sequence '::' expected\n");
1200 if (xmlStrEqual(token, (const xmlChar *) "child")) {
1201 name = xsltScanName(ctxt);
1203 xsltGenericError(xsltGenericErrorContext,
1204 "xsltCompileStepPattern : QName expected\n");
1208 ncname = xmlSplitQName2(name, &prefix);
1209 if (ncname != NULL) {
1210 if (prefix != NULL) {
1213 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1215 xsltGenericError(xsltGenericErrorContext,
1216 "xsl: pattern, no namespace bound to prefix %s\n",
1219 URL = xmlStrdup(ns->href);
1226 PUSH(XSLT_OP_CHILD, name, URL);
1227 } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
1228 name = xsltScanName(ctxt);
1230 xsltGenericError(xsltGenericErrorContext,
1231 "xsltCompileStepPattern : QName expected\n");
1235 ncname = xmlSplitQName2(name, &prefix);
1236 if (ncname != NULL) {
1237 if (prefix != NULL) {
1240 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1242 xsltGenericError(xsltGenericErrorContext,
1243 "xsl: pattern, no namespace bound to prefix %s\n",
1246 URL = xmlStrdup(ns->href);
1253 PUSH(XSLT_OP_ATTR, name, URL);
1255 xsltGenericError(xsltGenericErrorContext,
1256 "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
1261 } else if (CUR == '*') {
1263 PUSH(XSLT_OP_ALL, token, NULL);
1265 ncname = xmlSplitQName2(token, &prefix);
1266 if (ncname != NULL) {
1267 if (prefix != NULL) {
1270 ns = xmlSearchNs(ctxt->doc, ctxt->elem, prefix);
1272 xsltGenericError(xsltGenericErrorContext,
1273 "xsl: pattern, no namespace bound to prefix %s\n",
1276 URL = xmlStrdup(ns->href);
1283 PUSH(XSLT_OP_ELEM, token, URL);
1288 while (CUR == '[') {
1290 xmlChar *ret = NULL;
1295 /* TODO: avoid breaking in strings ... */
1296 while (IS_CHAR(CUR)) {
1297 /* Skip over nested predicates */
1307 if (!IS_CHAR(CUR)) {
1308 xsltGenericError(xsltGenericErrorContext,
1309 "xsltCompileStepPattern : ']' expected\n");
1313 ret = xmlStrndup(q, CUR_PTR - q);
1314 PUSH(XSLT_OP_PREDICATE, ret, NULL);
1315 /* push the predicate lower than local test */
1328 * xsltCompileRelativePathPattern:
1329 * @comp: the compilation context
1330 * @token: a posible precompiled name
1332 * Compile the XSLT RelativePathPattern and generates a precompiled
1333 * form suitable for fast matching.
1335 * [4] RelativePathPattern ::= StepPattern
1336 * | RelativePathPattern '/' StepPattern
1337 * | RelativePathPattern '//' StepPattern
1340 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1341 xsltCompileStepPattern(ctxt, token);
1345 while ((CUR != 0) && (CUR != '|')) {
1346 if ((CUR == '/') && (NXT(1) == '/')) {
1347 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1351 xsltCompileStepPattern(ctxt, NULL);
1352 } else if (CUR == '/') {
1353 PUSH(XSLT_OP_PARENT, NULL, NULL);
1356 if ((CUR != 0) || (CUR == '|')) {
1357 xsltCompileRelativePathPattern(ctxt, NULL);
1371 * xsltCompileLocationPathPattern:
1372 * @comp: the compilation context
1374 * Compile the XSLT LocationPathPattern and generates a precompiled
1375 * form suitable for fast matching.
1377 * [2] LocationPathPattern ::= '/' RelativePathPattern?
1378 * | IdKeyPattern (('/' | '//') RelativePathPattern)?
1379 * | '//'? RelativePathPattern
1382 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1384 if ((CUR == '/') && (NXT(1) == '/')) {
1386 * since we reverse the query
1387 * a leading // can be safely ignored
1391 xsltCompileRelativePathPattern(ctxt, NULL);
1392 } else if (CUR == '/') {
1394 * We need to find root as the parent
1398 PUSH(XSLT_OP_ROOT, NULL, NULL);
1399 if ((CUR != 0) || (CUR == '|')) {
1400 PUSH(XSLT_OP_PARENT, NULL, NULL);
1401 xsltCompileRelativePathPattern(ctxt, NULL);
1403 } else if (CUR == '*') {
1404 xsltCompileRelativePathPattern(ctxt, NULL);
1405 } else if (CUR == '@') {
1406 xsltCompileRelativePathPattern(ctxt, NULL);
1409 name = xsltScanName(ctxt);
1411 xsltGenericError(xsltGenericErrorContext,
1412 "xsltCompileLocationPathPattern : Name expected\n");
1417 if ((CUR == '(') && !xmlXPathIsNodeType(name)) {
1418 xsltCompileIdKeyPattern(ctxt, name, 1);
1419 if ((CUR == '/') && (NXT(1) == '/')) {
1420 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1424 xsltCompileRelativePathPattern(ctxt, NULL);
1425 } else if (CUR == '/') {
1426 PUSH(XSLT_OP_PARENT, NULL, NULL);
1429 xsltCompileRelativePathPattern(ctxt, NULL);
1433 xsltCompileRelativePathPattern(ctxt, name);
1440 * xsltCompilePattern:
1441 * @pattern: an XSLT pattern
1442 * @doc: the containing document
1443 * @node: the containing element
1445 * Compile the XSLT pattern and generates a list of precompiled form suitable
1446 * for fast matching.
1448 * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1450 * Returns the generated pattern list or NULL in case of failure
1454 xsltCompilePattern(const xmlChar *pattern, xmlDocPtr doc, xmlNodePtr node) {
1455 xsltParserContextPtr ctxt = NULL;
1456 xsltCompMatchPtr element, first = NULL, previous = NULL;
1457 int current, start, end;
1459 if (pattern == NULL) {
1460 xsltGenericError(xsltGenericErrorContext,
1461 "xsltCompilePattern : NULL pattern\n");
1465 ctxt = xsltNewParserContext();
1471 while (pattern[current] != 0) {
1473 while (IS_BLANK(pattern[current]))
1476 while ((pattern[end] != 0) && (pattern[end] != '|'))
1478 if (current == end) {
1479 xsltGenericError(xsltGenericErrorContext,
1480 "xsltCompilePattern : NULL pattern\n");
1483 element = xsltNewCompMatch();
1484 if (element == NULL) {
1489 else if (previous != NULL)
1490 previous->next = element;
1493 ctxt->comp = element;
1494 ctxt->base = xmlStrndup(&pattern[start], end - start);
1495 if (ctxt->base == NULL)
1497 ctxt->cur = &(ctxt->base)[current - start];
1498 element->pattern = ctxt->base;
1500 #ifdef WITH_XSLT_DEBUG_PATTERN
1501 xsltGenericDebug(xsltGenericDebugContext,
1502 "xsltCompilePattern : parsing '%s'\n",
1505 xsltCompileLocationPathPattern(ctxt);
1510 * Reverse for faster interpretation.
1512 xsltReverseCompMatch(element);
1515 * Set-up the priority
1517 if (((element->steps[0].op == XSLT_OP_ELEM) ||
1518 (element->steps[0].op == XSLT_OP_ATTR)) &&
1519 (element->steps[0].value != NULL) &&
1520 (element->steps[1].op == XSLT_OP_END)) {
1521 element->priority = 0;
1523 } else if ((element->steps[0].op == XSLT_OP_ROOT) &&
1524 (element->steps[1].op == XSLT_OP_END)) {
1525 element->priority = 0;
1527 } else if ((element->steps[0].op == XSLT_OP_PI) &&
1528 (element->steps[0].value != NULL) &&
1529 (element->steps[1].op == XSLT_OP_END)) {
1530 element->priority = 0;
1531 } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1532 (element->steps[0].value2 != NULL) &&
1533 (element->steps[1].op == XSLT_OP_END)) {
1534 element->priority = -0.25;
1535 } else if ((element->steps[0].op == XSLT_OP_NS) &&
1536 (element->steps[0].value != NULL) &&
1537 (element->steps[1].op == XSLT_OP_END)) {
1538 element->priority = -0.25;
1539 } else if ((element->steps[0].op == XSLT_OP_ATTR) &&
1540 (element->steps[0].value == NULL) &&
1541 (element->steps[0].value2 == NULL) &&
1542 (element->steps[1].op == XSLT_OP_END)) {
1543 element->priority = -0.5;
1544 } else if (((element->steps[0].op == XSLT_OP_PI) ||
1545 (element->steps[0].op == XSLT_OP_TEXT) ||
1546 (element->steps[0].op == XSLT_OP_ALL) ||
1547 (element->steps[0].op == XSLT_OP_NODE) ||
1548 (element->steps[0].op == XSLT_OP_COMMENT)) &&
1549 (element->steps[1].op == XSLT_OP_END)) {
1550 element->priority = -0.5;
1552 element->priority = 0.5;
1554 #ifdef WITH_XSLT_DEBUG_PATTERN
1555 xsltGenericDebug(xsltGenericDebugContext,
1556 "xsltCompilePattern : parsed %s, default priority %f\n",
1557 element->pattern, element->priority);
1559 if (pattern[end] == '|')
1564 xsltGenericError(xsltGenericErrorContext,
1565 "xsltCompilePattern : NULL pattern\n");
1569 xsltFreeParserContext(ctxt);
1574 xsltFreeParserContext(ctxt);
1576 xsltFreeCompMatchList(first);
1580 /************************************************************************
1582 * Module interfaces *
1584 ************************************************************************/
1588 * @style: an XSLT stylesheet
1589 * @cur: an XSLT template
1590 * @mode: the mode name or NULL
1591 * @modeURI: the mode URI or NULL
1593 * Register the XSLT pattern associated to @cur
1595 * Returns -1 in case of error, 0 otherwise
1598 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1599 const xmlChar *mode, const xmlChar *modeURI) {
1600 xsltCompMatchPtr pat, list, *top = NULL, next;
1601 const xmlChar *name = NULL;
1602 float priority; /* the priority */
1604 if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1607 priority = cur->priority;
1608 pat = xsltCompilePattern(cur->match, style->doc, cur->elem);
1614 pat->template = cur;
1616 pat->mode = xmlStrdup(mode);
1617 if (modeURI != NULL)
1618 pat->modeURI = xmlStrdup(modeURI);
1619 if (priority != XSLT_PAT_NO_PRIORITY)
1620 pat->priority = priority;
1623 * insert it in the hash table list corresponding to its lookup name
1625 switch (pat->steps[0].op) {
1627 if (pat->steps[0].value != NULL)
1628 name = pat->steps[0].value;
1630 top = (xsltCompMatchPtr *) &(style->attrMatch);
1634 case XSLT_OP_PARENT:
1635 case XSLT_OP_ANCESTOR:
1637 name = pat->steps[0].value;
1640 top = (xsltCompMatchPtr *) &(style->rootMatch);
1643 top = (xsltCompMatchPtr *) &(style->keyMatch);
1646 /* TODO optimize ID !!! */
1648 top = (xsltCompMatchPtr *) &(style->elemMatch);
1651 case XSLT_OP_PREDICATE:
1652 xsltGenericError(xsltGenericErrorContext,
1653 "xsltAddTemplate: invalid compiled pattern\n");
1654 xsltFreeCompMatch(pat);
1657 * TODO: some flags at the top level about type based patterns
1658 * would be faster than inclusion in the hash table.
1661 if (pat->steps[0].value != NULL)
1662 name = pat->steps[0].value;
1664 top = (xsltCompMatchPtr *) &(style->piMatch);
1666 case XSLT_OP_COMMENT:
1667 top = (xsltCompMatchPtr *) &(style->commentMatch);
1670 top = (xsltCompMatchPtr *) &(style->textMatch);
1673 if (pat->steps[0].value != NULL)
1674 name = pat->steps[0].value;
1676 top = (xsltCompMatchPtr *) &(style->elemMatch);
1681 if (style->templatesHash == NULL) {
1682 style->templatesHash = xmlHashCreate(1024);
1683 if (style->templatesHash == NULL) {
1684 xsltFreeCompMatch(pat);
1687 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1689 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1690 name, mode, modeURI);
1692 xmlHashAddEntry3(style->templatesHash, name,
1693 mode, modeURI, pat);
1696 * Note '<=' since one must choose among the matching
1697 * template rules that are left, the one that occurs
1698 * last in the stylesheet
1700 if (list->priority <= pat->priority) {
1702 xmlHashUpdateEntry3(style->templatesHash, name,
1703 mode, modeURI, pat, NULL);
1705 while (list->next != NULL) {
1706 if (list->next->priority <= pat->priority)
1710 pat->next = list->next;
1715 } else if (top != NULL) {
1720 } else if (list->priority <= pat->priority) {
1724 while (list->next != NULL) {
1725 if (list->next->priority <= pat->priority)
1729 pat->next = list->next;
1733 xsltGenericError(xsltGenericErrorContext,
1734 "xsltAddTemplate: invalid compiled pattern\n");
1735 xsltFreeCompMatch(pat);
1738 #ifdef WITH_XSLT_DEBUG_PATTERN
1740 xsltGenericDebug(xsltGenericDebugContext,
1741 "added pattern : '%s' mode '%s' priority %f\n",
1742 pat->pattern, pat->mode, pat->priority);
1744 xsltGenericDebug(xsltGenericDebugContext,
1745 "added pattern : '%s' priority %f\n",
1746 pat->pattern, pat->priority);
1756 * @ctxt: a XSLT process context
1758 * @style: the current style
1760 * Finds the template applying to this node, if @style is non-NULL
1761 * it means one need to look for the next imported template in scope.
1763 * Returns the xsltTemplatePtr or NULL if not found
1766 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
1767 xsltStylesheetPtr style) {
1768 xsltStylesheetPtr curstyle;
1769 xsltTemplatePtr ret = NULL;
1770 const xmlChar *name = NULL;
1771 xsltCompMatchPtr list = NULL;
1774 if ((ctxt == NULL) || (node == NULL))
1777 if (style == NULL) {
1778 curstyle = ctxt->style;
1780 curstyle = xsltNextImport(style);
1783 while ((curstyle != NULL) && (curstyle != style)) {
1784 priority = XSLT_PAT_NO_PRIORITY;
1785 /* TODO : handle IDs/keys here ! */
1786 if (curstyle->templatesHash != NULL) {
1788 * Use the top name as selector
1790 switch (node->type) {
1791 case XML_ELEMENT_NODE:
1792 case XML_ATTRIBUTE_NODE:
1796 case XML_DOCUMENT_NODE:
1797 case XML_HTML_DOCUMENT_NODE:
1799 case XML_CDATA_SECTION_NODE:
1800 case XML_COMMENT_NODE:
1801 case XML_ENTITY_REF_NODE:
1802 case XML_ENTITY_NODE:
1803 case XML_DOCUMENT_TYPE_NODE:
1804 case XML_DOCUMENT_FRAG_NODE:
1805 case XML_NOTATION_NODE:
1807 case XML_ELEMENT_DECL:
1808 case XML_ATTRIBUTE_DECL:
1809 case XML_ENTITY_DECL:
1810 case XML_NAMESPACE_DECL:
1811 case XML_XINCLUDE_START:
1812 case XML_XINCLUDE_END:
1821 * find the list of appliable expressions based on the name
1823 list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
1824 name, ctxt->mode, ctxt->modeURI);
1827 while (list != NULL) {
1828 if (xsltTestCompMatch(ctxt, list, node,
1829 ctxt->mode, ctxt->modeURI)) {
1830 ret = list->template;
1831 priority = list->priority;
1839 * find alternate generic matches
1841 switch (node->type) {
1842 case XML_ELEMENT_NODE:
1843 list = curstyle->elemMatch;
1845 case XML_ATTRIBUTE_NODE:
1846 list = curstyle->attrMatch;
1849 list = curstyle->piMatch;
1851 case XML_DOCUMENT_NODE:
1852 case XML_HTML_DOCUMENT_NODE:
1853 list = curstyle->rootMatch;
1856 case XML_CDATA_SECTION_NODE:
1857 list = curstyle->textMatch;
1859 case XML_COMMENT_NODE:
1860 list = curstyle->commentMatch;
1862 case XML_ENTITY_REF_NODE:
1863 case XML_ENTITY_NODE:
1864 case XML_DOCUMENT_TYPE_NODE:
1865 case XML_DOCUMENT_FRAG_NODE:
1866 case XML_NOTATION_NODE:
1868 case XML_ELEMENT_DECL:
1869 case XML_ATTRIBUTE_DECL:
1870 case XML_ENTITY_DECL:
1871 case XML_NAMESPACE_DECL:
1872 case XML_XINCLUDE_START:
1873 case XML_XINCLUDE_END:
1879 while ((list != NULL) &&
1880 ((ret == NULL) || (list->priority > priority))) {
1881 if (xsltTestCompMatch(ctxt, list, node,
1882 ctxt->mode, ctxt->modeURI)) {
1883 ret = list->template;
1888 if (node->_private != NULL) {
1889 list = curstyle->keyMatch;
1890 while ((list != NULL) &&
1891 ((ret == NULL) || (list->priority > priority))) {
1892 if (xsltTestCompMatch(ctxt, list, node,
1893 ctxt->mode, ctxt->modeURI)) {
1894 ret = list->template;
1904 * Cycle on next curstylesheet import.
1906 curstyle = xsltNextImport(curstyle);
1912 * xsltCleanupTemplates:
1913 * @style: an XSLT stylesheet
1915 * Cleanup the state of the templates used by the stylesheet and
1916 * the ones it imports.
1919 xsltCleanupTemplates(xsltStylesheetPtr style) {
1920 while (style != NULL) {
1921 xmlHashScan((xmlHashTablePtr) style->templatesHash,
1922 (xmlHashScanner) xsltCleanupCompMatch, NULL);
1924 style = xsltNextImport(style);
1929 * xsltFreeTemplateHashes:
1930 * @style: an XSLT stylesheet
1932 * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1935 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1936 if (style->templatesHash != NULL)
1937 xmlHashFree((xmlHashTablePtr) style->templatesHash,
1938 (xmlHashDeallocator) xsltFreeCompMatchList);
1939 if (style->rootMatch != NULL)
1940 xsltFreeCompMatchList(style->rootMatch);
1941 if (style->keyMatch != NULL)
1942 xsltFreeCompMatchList(style->keyMatch);
1943 if (style->elemMatch != NULL)
1944 xsltFreeCompMatchList(style->elemMatch);
1945 if (style->attrMatch != NULL)
1946 xsltFreeCompMatchList(style->attrMatch);
1947 if (style->parentMatch != NULL)
1948 xsltFreeCompMatchList(style->parentMatch);
1949 if (style->textMatch != NULL)
1950 xsltFreeCompMatchList(style->textMatch);
1951 if (style->piMatch != NULL)
1952 xsltFreeCompMatchList(style->piMatch);
1953 if (style->commentMatch != NULL)
1954 xsltFreeCompMatchList(style->commentMatch);
1960 * @node: a node in the source tree
1961 * @pattern: an XSLT pattern
1963 * Determine if a node matches a pattern.
1966 xsltMatchPattern(xsltTransformContextPtr context,
1968 const xmlChar *pattern)
1971 xsltCompMatchPtr first, comp;
1973 if ((context != NULL) && (pattern != NULL)) {
1974 first = xsltCompilePattern(pattern);
1975 for (comp = first; comp != NULL; comp = comp->next) {
1976 match = xsltTestCompMatch(context, comp, node, NULL, NULL);
1981 xsltFreeCompMatchList(first);