2 * pattern.c: Implemetation of the template match compilation and lookup
5 * http://www.w3.org/TR/1999/REC-xslt-19991116
7 * See Copyright for the status of this software.
9 * Daniel.Veillard@imag.fr
12 #include "xsltconfig.h"
16 #include <libxml/xmlmemory.h>
17 #include <libxml/tree.h>
18 #include <libxml/valid.h>
19 #include <libxml/hash.h>
20 #include <libxml/xmlerror.h>
21 #include <libxml/parserInternals.h>
23 #include "xsltInternals.h"
24 #include "xsltutils.h"
26 #include "templates.h"
30 /* #define DEBUG_PARSING */
56 typedef struct _xsltStepOp xsltStepOp;
57 typedef xsltStepOp *xsltStepOpPtr;
65 struct _xsltCompMatch {
66 struct _xsltCompMatch *next; /* siblings in the name hash */
67 float priority; /* the priority */
68 const xmlChar *mode; /* the mode */
69 const xmlChar *modeURI; /* the mode URI */
70 xsltTemplatePtr template; /* the associated template */
72 /* TODO fix the statically allocated size steps[] */
75 xsltStepOp steps[20]; /* ops for computation */
78 typedef struct _xsltParserContext xsltParserContext;
79 typedef xsltParserContext *xsltParserContextPtr;
80 struct _xsltParserContext {
81 const xmlChar *cur; /* the current char being parsed */
82 const xmlChar *base; /* the full expression */
83 int error; /* error code */
84 xsltCompMatchPtr comp; /* the result */
87 /************************************************************************
91 ************************************************************************/
96 * Create a new XSLT CompMatch
98 * Returns the newly allocated xsltCompMatchPtr or NULL in case of error
101 xsltNewCompMatch(void) {
102 xsltCompMatchPtr cur;
104 cur = (xsltCompMatchPtr) xmlMalloc(sizeof(xsltCompMatch));
106 xsltGenericError(xsltGenericErrorContext,
107 "xsltNewCompMatch : malloc failed\n");
110 memset(cur, 0, sizeof(xsltCompMatch));
117 * @comp: an XSLT comp
119 * Free up the memory allocated by @comp
122 xsltFreeCompMatch(xsltCompMatchPtr comp) {
128 if (comp->mode != NULL)
129 xmlFree((xmlChar *)comp->mode);
130 if (comp->modeURI != NULL)
131 xmlFree((xmlChar *)comp->modeURI);
132 for (i = 0;i < comp->nbStep;i++) {
133 op = &comp->steps[i];
134 if (op->value != NULL)
136 if (op->value2 != NULL)
138 if (op->value3 != NULL)
141 memset(comp, -1, sizeof(xsltCompMatch));
146 * xsltFreeCompMatchList:
147 * @comp: an XSLT comp list
149 * Free up the memory allocated by all the elements of @comp
152 xsltFreeCompMatchList(xsltCompMatchPtr comp) {
153 xsltCompMatchPtr cur;
155 while (comp != NULL) {
158 xsltFreeCompMatch(cur);
163 * xsltNewParserContext:
165 * Create a new XSLT ParserContext
167 * Returns the newly allocated xsltParserContextPtr or NULL in case of error
170 xsltNewParserContext(void) {
171 xsltParserContextPtr cur;
173 cur = (xsltParserContextPtr) xmlMalloc(sizeof(xsltParserContext));
175 xsltGenericError(xsltGenericErrorContext,
176 "xsltNewParserContext : malloc failed\n");
179 memset(cur, 0, sizeof(xsltParserContext));
184 * xsltFreeParserContext:
185 * @ctxt: an XSLT parser context
187 * Free up the memory allocated by @ctxt
190 xsltFreeParserContext(xsltParserContextPtr ctxt) {
193 memset(ctxt, -1, sizeof(xsltParserContext));
199 * @comp: the compiled match expression
201 * @value: the first value
202 * @value2: the second value
204 * Add an step to an XSLT Compiled Match
206 * Returns -1 in case of failure, 0 otherwise.
209 xsltCompMatchAdd(xsltCompMatchPtr comp, xsltOp op, xmlChar *value,
211 if (comp->nbStep >= 20) {
212 xsltGenericError(xsltGenericErrorContext,
213 "xsltCompMatchAddOp: overflow\n");
216 comp->steps[comp->nbStep].op = op;
217 comp->steps[comp->nbStep].value = value;
218 comp->steps[comp->nbStep].value2 = value2;
224 * xsltSwapTopCompMatch:
225 * @comp: the compiled match expression
227 * reverse the two top steps.
230 xsltSwapTopCompMatch(xsltCompMatchPtr comp) {
232 int j = comp->nbStep - 1;
235 register xmlChar *tmp;
238 tmp = comp->steps[i].value;
239 comp->steps[i].value = comp->steps[j].value;
240 comp->steps[j].value = tmp;
241 tmp = comp->steps[i].value2;
242 comp->steps[i].value2 = comp->steps[j].value2;
243 comp->steps[j].value2 = tmp;
244 op = comp->steps[i].op;
245 comp->steps[i].op = comp->steps[j].op;
246 comp->steps[j].op = op;
251 * xsltReverseCompMatch:
252 * @comp: the compiled match expression
254 * reverse all the stack of expressions
257 xsltReverseCompMatch(xsltCompMatchPtr comp) {
259 int j = comp->nbStep - 1;
262 register xmlChar *tmp;
264 tmp = comp->steps[i].value;
265 comp->steps[i].value = comp->steps[j].value;
266 comp->steps[j].value = tmp;
267 tmp = comp->steps[i].value2;
268 comp->steps[i].value2 = comp->steps[j].value2;
269 comp->steps[j].value2 = tmp;
270 op = comp->steps[i].op;
271 comp->steps[i].op = comp->steps[j].op;
272 comp->steps[j].op = op;
276 comp->steps[comp->nbStep++].op = XSLT_OP_END;
279 /************************************************************************
281 * The interpreter for the precompiled patterns *
283 ************************************************************************/
287 * @ctxt: a XSLT process context
288 * @comp: the precompiled pattern
290 * @mode: the mode name or NULL
291 * @modeURI: the mode URI or NULL
293 * Test wether the node matches the pattern
295 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
298 xsltTestCompMatch(xsltTransformContextPtr ctxt, xsltCompMatchPtr comp,
299 xmlNodePtr node, const xmlChar *mode,
300 const xmlChar *modeURI) {
302 xsltStepOpPtr step, select = NULL;
304 if ((comp == NULL) || (node == NULL) || (ctxt == NULL)) {
305 xsltGenericError(xsltGenericErrorContext,
306 "xsltTestCompMatch: null arg\n");
310 if (comp->mode == NULL)
312 if ((comp->mode != mode) && (!xmlStrEqual(comp->mode, mode)))
315 if (comp->mode != NULL)
318 if (modeURI != NULL) {
319 if (comp->modeURI == NULL)
321 if ((comp->modeURI != modeURI) &&
322 (!xmlStrEqual(comp->modeURI, modeURI)))
325 if (comp->modeURI != NULL)
328 for (i = 0;i < comp->nbStep;i++) {
329 step = &comp->steps[i];
330 if (step->op != XSLT_OP_PREDICATE)
336 if ((node->type != XML_DOCUMENT_NODE) &&
337 (node->type != XML_HTML_DOCUMENT_NODE))
341 if (node->type != XML_ELEMENT_NODE)
343 if (step->value == NULL)
345 if (!xmlStrEqual(step->value, node->name))
349 if (node->ns == NULL) {
350 if (step->value2 != NULL)
352 } else if (node->ns->href != NULL) {
353 if (step->value2 == NULL)
355 if (!xmlStrEqual(step->value2, node->ns->href))
360 TODO /* Handle OP_CHILD */
363 if (node->type != XML_ATTRIBUTE_NODE)
365 if (step->value == NULL)
367 if (!xmlStrEqual(step->value, node->name))
371 if (node->ns == NULL) {
372 if (step->value2 != NULL)
374 } else if (node->ns->href != NULL) {
375 if (step->value2 == NULL)
377 if (!xmlStrEqual(step->value2, node->ns->href))
385 if (step->value == NULL)
387 if (!xmlStrEqual(step->value, node->name))
390 if (node->ns == NULL) {
391 if (step->value2 != NULL)
393 } else if (node->ns->href != NULL) {
394 if (step->value2 == NULL)
396 if (!xmlStrEqual(step->value2, node->ns->href))
400 case XSLT_OP_ANCESTOR:
401 /* TODO: implement coalescing of ANCESTOR/NODE ops */
402 if (step->value == NULL) {
404 step = &comp->steps[i];
405 if (step->op == XSLT_OP_ROOT)
407 if (step->op != XSLT_OP_ELEM)
409 if (step->value == NULL)
415 while (node != NULL) {
418 if (xmlStrEqual(step->value, node->name)) {
420 if (node->ns == NULL) {
421 if (step->value2 == NULL)
423 } else if (node->ns->href != NULL) {
424 if ((step->value2 != NULL) &&
425 (xmlStrEqual(step->value2, node->ns->href)))
435 /* TODO Handle IDs decently, must be done differently */
438 id = xmlGetID(node->doc, step->value);
439 if ((id == NULL) || (id->parent != node))
447 list = xsltGetKey(ctxt, step->value,
448 step->value3, step->value2);
451 for (i = 0;i < list->nodeNr;i++)
452 if (list->nodeTab[i] == node)
454 if (i >= list->nodeNr)
460 if (node->ns == NULL) {
461 if (step->value != NULL)
463 } else if (node->ns->href != NULL) {
464 if (step->value == NULL)
466 if (!xmlStrEqual(step->value, node->ns->href))
471 switch (node->type) {
472 case XML_DOCUMENT_NODE:
473 case XML_HTML_DOCUMENT_NODE:
474 case XML_ELEMENT_NODE:
480 case XSLT_OP_PREDICATE: {
483 int pos = 0, len = 0;
485 * Depending on the last selection, one may need to
486 * recompute contextSize and proximityPosition.
488 oldCS = ctxt->xpathCtxt->contextSize;
489 oldCP = ctxt->xpathCtxt->proximityPosition;
490 if ((select != NULL) &&
491 (select->op == XSLT_OP_ELEM) &&
492 (select->value != NULL) &&
493 (node->type == XML_ELEMENT_NODE) &&
494 (node->parent != NULL)) {
496 /* TODO: cache those informations ?!? */
497 xmlNodePtr siblings = node->parent->children;
499 while (siblings != NULL) {
500 if (siblings->type == XML_ELEMENT_NODE) {
501 if (siblings == node) {
504 } else if (xmlStrEqual(node->name,
509 siblings = siblings->next;
512 ctxt->xpathCtxt->contextSize = len;
513 ctxt->xpathCtxt->proximityPosition = pos;
515 } else if ((select != NULL) && (select->op == XSLT_OP_ALL)) {
516 xmlNodePtr siblings = node->parent->children;
518 while (siblings != NULL) {
519 if (siblings->type == XML_ELEMENT_NODE) {
521 if (siblings == node) {
525 siblings = siblings->next;
528 ctxt->xpathCtxt->contextSize = len;
529 ctxt->xpathCtxt->proximityPosition = pos;
532 oldNode = ctxt->node;
535 if ((step->value == NULL) ||
536 (!xsltEvalXPathPredicate(ctxt, step->value))) {
538 ctxt->xpathCtxt->contextSize = oldCS;
539 ctxt->xpathCtxt->proximityPosition = oldCP;
541 ctxt->node = oldNode;
545 ctxt->xpathCtxt->contextSize = oldCS;
546 ctxt->xpathCtxt->proximityPosition = oldCP;
548 ctxt->node = oldNode;
552 if (node->type != XML_PI_NODE)
554 if (step->value != NULL) {
555 if (!xmlStrEqual(step->value, node->name))
559 case XSLT_OP_COMMENT:
560 if (node->type != XML_COMMENT_NODE)
564 if ((node->type != XML_TEXT_NODE) &&
565 (node->type != XML_CDATA_SECTION_NODE))
569 switch (node->type) {
570 case XML_DOCUMENT_NODE:
571 case XML_HTML_DOCUMENT_NODE:
572 case XML_ELEMENT_NODE:
573 case XML_CDATA_SECTION_NODE:
575 case XML_COMMENT_NODE:
577 case XML_ATTRIBUTE_NODE:
589 * xsltTestCompMatchList:
590 * @ctxt: a XSLT process context
592 * @comp: the precompiled pattern list
594 * Test wether the node matches one of the patterns in the list
596 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
599 xsltTestCompMatchList(xsltTransformContextPtr ctxt, xmlNodePtr node,
600 xsltCompMatchPtr comp) {
603 if ((ctxt == NULL) || (node == NULL))
605 while (comp != NULL) {
606 ret = xsltTestCompMatch(ctxt, comp, node, NULL, NULL);
614 /************************************************************************
616 * Dedicated parser for templates *
618 ************************************************************************/
620 #define CUR (*ctxt->cur)
621 #define SKIP(val) ctxt->cur += (val)
622 #define NXT(val) ctxt->cur[(val)]
623 #define CUR_PTR ctxt->cur
625 #define SKIP_BLANKS \
626 while (IS_BLANK(CUR)) NEXT
628 #define CURRENT (*ctxt->cur)
629 #define NEXT ((*ctxt->cur) ? ctxt->cur++: ctxt->cur)
632 #define PUSH(op, val, val2) \
633 if (xsltCompMatchAdd(ctxt->comp, (op), (val), (val2))) goto error;
636 xsltSwapTopCompMatch(ctxt->comp);
638 #define XSLT_ERROR(X) \
639 { xsltError(ctxt, __FILE__, __LINE__, X); \
640 ctxt->error = (X); return; }
642 #define XSLT_ERROR0(X) \
643 { xsltError(ctxt, __FILE__, __LINE__, X); \
644 ctxt->error = (X); return(0); }
648 * @ctxt: the XPath Parser context
650 * Parse an XPath Litteral:
652 * [29] Literal ::= '"' [^"]* '"'
655 * Returns the Literal parsed or NULL
659 xsltScanLiteral(xsltParserContextPtr ctxt) {
667 while ((IS_CHAR(CUR)) && (CUR != '"'))
670 /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
674 ret = xmlStrndup(q, CUR_PTR - q);
677 } else if (CUR == '\'') {
680 while ((IS_CHAR(CUR)) && (CUR != '\''))
683 /* XP_ERROR(XPATH_UNFINISHED_LITERAL_ERROR); */
687 ret = xmlStrndup(q, CUR_PTR - q);
691 /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
700 * @ctxt: the XPath Parser context
702 * Trickery: parse an XML name but without consuming the input flow
703 * Needed to avoid insanity in the parser state.
705 * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' | ':' |
706 * CombiningChar | Extender
708 * [5] Name ::= (Letter | '_' | ':') (NameChar)*
710 * [6] Names ::= Name (S Name)*
712 * Returns the Name parsed or NULL
716 xsltScanName(xsltParserContextPtr ctxt) {
717 xmlChar buf[XML_MAX_NAMELEN];
721 if (!IS_LETTER(CUR) && (CUR != '_') &&
726 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
727 (NXT(len) == '.') || (NXT(len) == '-') ||
728 (NXT(len) == '_') || (NXT(len) == ':') ||
729 (IS_COMBINING(NXT(len))) ||
730 (IS_EXTENDER(NXT(len)))) {
733 if (len >= XML_MAX_NAMELEN) {
734 xmlGenericError(xmlGenericErrorContext,
735 "xmlScanName: reached XML_MAX_NAMELEN limit\n");
736 while ((IS_LETTER(NXT(len))) || (IS_DIGIT(NXT(len))) ||
737 (NXT(len) == '.') || (NXT(len) == '-') ||
738 (NXT(len) == '_') || (NXT(len) == ':') ||
739 (IS_COMBINING(NXT(len))) ||
740 (IS_EXTENDER(NXT(len))))
746 return(xmlStrndup(buf, len));
749 * xsltCompileIdKeyPattern:
750 * @comp: the compilation context
751 * @name: a preparsed name
752 * @aid: whether id/key are allowed there
754 * Compile the XSLT LocationIdKeyPattern
755 * [3] IdKeyPattern ::= 'id' '(' Literal ')'
756 * | 'key' '(' Literal ',' Literal ')'
758 * also handle NodeType and PI from:
760 * [7] NodeTest ::= NameTest
762 * | 'processing-instruction' '(' Literal ')'
765 xsltCompileIdKeyPattern(xsltParserContextPtr ctxt, xmlChar *name, int aid) {
767 xmlChar *lit2 = NULL;
770 xsltGenericError(xsltGenericErrorContext,
771 "xsltCompileIdKeyPattern : ( expected\n");
775 if ((aid) && (xmlStrEqual(name, (const xmlChar *)"id"))) {
778 lit = xsltScanLiteral(ctxt);
783 xsltGenericError(xsltGenericErrorContext,
784 "xsltCompileIdKeyPattern : ) expected\n");
789 PUSH(XSLT_OP_ID, lit, NULL);
790 } else if ((aid) && (xmlStrEqual(name, (const xmlChar *)"key"))) {
793 lit = xsltScanLiteral(ctxt);
798 xsltGenericError(xsltGenericErrorContext,
799 "xsltCompileIdKeyPattern : , expected\n");
805 lit2 = xsltScanLiteral(ctxt);
810 xsltGenericError(xsltGenericErrorContext,
811 "xsltCompileIdKeyPattern : ) expected\n");
816 /* TODO: support namespace in keys */
817 PUSH(XSLT_OP_KEY, lit, lit2);
818 } else if (xmlStrEqual(name, (const xmlChar *)"processing-instruction")) {
822 lit = xsltScanLiteral(ctxt);
827 xsltGenericError(xsltGenericErrorContext,
828 "xsltCompileIdKeyPattern : ) expected\n");
834 PUSH(XSLT_OP_PI, lit, NULL);
835 } else if (xmlStrEqual(name, (const xmlChar *)"text")) {
839 xsltGenericError(xsltGenericErrorContext,
840 "xsltCompileIdKeyPattern : ) expected\n");
845 PUSH(XSLT_OP_TEXT, NULL, NULL);
846 } else if (xmlStrEqual(name, (const xmlChar *)"comment")) {
850 xsltGenericError(xsltGenericErrorContext,
851 "xsltCompileIdKeyPattern : ) expected\n");
856 PUSH(XSLT_OP_COMMENT, NULL, NULL);
857 } else if (xmlStrEqual(name, (const xmlChar *)"node")) {
861 xsltGenericError(xsltGenericErrorContext,
862 "xsltCompileIdKeyPattern : ) expected\n");
867 PUSH(XSLT_OP_NODE, NULL, NULL);
869 xsltGenericError(xsltGenericErrorContext,
870 "xsltCompileIdKeyPattern : expecting 'key' or 'id' or node type\n");
874 xsltGenericError(xsltGenericErrorContext,
875 "xsltCompileIdKeyPattern : node type\n");
885 * xsltCompileStepPattern:
886 * @comp: the compilation context
887 * @token: a posible precompiled name
889 * Compile the XSLT StepPattern and generates a precompiled
890 * form suitable for fast matching.
892 * [5] StepPattern ::= ChildOrAttributeAxisSpecifier NodeTest Predicate*
893 * [6] ChildOrAttributeAxisSpecifier ::= AbbreviatedAxisSpecifier
894 * | ('child' | 'attribute') '::'
896 * [7] NodeTest ::= NameTest
898 * | 'processing-instruction' '(' Literal ')'
899 * [8] Predicate ::= '[' PredicateExpr ']'
900 * [9] PredicateExpr ::= Expr
901 * [13] AbbreviatedAxisSpecifier ::= '@'?
902 * [37] NameTest ::= '*' | NCName ':' '*' | QName
906 xsltCompileStepPattern(xsltParserContextPtr ctxt, xmlChar *token) {
907 xmlChar *name = NULL;
910 if ((token == NULL) && (CUR == '@')) {
914 PUSH(XSLT_OP_ATTR, NULL, NULL);
917 token = xsltScanName(ctxt);
919 xsltGenericError(xsltGenericErrorContext,
920 "xsltCompileStepPattern : Name expected\n");
924 PUSH(XSLT_OP_ATTR, token, NULL);
928 token = xsltScanName(ctxt);
932 PUSH(XSLT_OP_ALL, token, NULL);
933 goto parse_predicate;
935 xsltGenericError(xsltGenericErrorContext,
936 "xsltCompileStepPattern : Name expected\n");
943 xsltCompileIdKeyPattern(ctxt, token, 0);
946 } else if (CUR == ':') {
949 xsltGenericError(xsltGenericErrorContext,
950 "xsltCompileStepPattern : sequence '::' expected\n");
955 if (xmlStrEqual(token, (const xmlChar *) "child")) {
956 /* TODO: handle namespace */
957 name = xsltScanName(ctxt);
959 xsltGenericError(xsltGenericErrorContext,
960 "xsltCompileStepPattern : QName expected\n");
964 PUSH(XSLT_OP_CHILD, name, NULL);
965 } else if (xmlStrEqual(token, (const xmlChar *) "attribute")) {
966 /* TODO: handle namespace */
967 name = xsltScanName(ctxt);
969 xsltGenericError(xsltGenericErrorContext,
970 "xsltCompileStepPattern : QName expected\n");
974 PUSH(XSLT_OP_ATTR, name, NULL);
976 xsltGenericError(xsltGenericErrorContext,
977 "xsltCompileStepPattern : 'child' or 'attribute' expected\n");
982 } else if (CUR == '*') {
984 PUSH(XSLT_OP_ALL, token, NULL);
986 /* TODO: handle namespace */
987 PUSH(XSLT_OP_ELEM, token, NULL);
997 /* TODO: avoid breaking in strings ... */
998 while ((IS_CHAR(CUR)) && (CUR != ']'))
1000 if (!IS_CHAR(CUR)) {
1001 xsltGenericError(xsltGenericErrorContext,
1002 "xsltCompileStepPattern : ']' expected\n");
1006 ret = xmlStrndup(q, CUR_PTR - q);
1007 PUSH(XSLT_OP_PREDICATE, ret, NULL);
1008 /* push the predicate lower than local test */
1021 * xsltCompileRelativePathPattern:
1022 * @comp: the compilation context
1023 * @token: a posible precompiled name
1025 * Compile the XSLT RelativePathPattern and generates a precompiled
1026 * form suitable for fast matching.
1028 * [4] RelativePathPattern ::= StepPattern
1029 * | RelativePathPattern '/' StepPattern
1030 * | RelativePathPattern '//' StepPattern
1033 xsltCompileRelativePathPattern(xsltParserContextPtr ctxt, xmlChar *token) {
1034 xsltCompileStepPattern(ctxt, token);
1038 while ((CUR != 0) && (CUR != '|')) {
1039 if ((CUR == '/') && (NXT(1) == '/')) {
1040 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1044 xsltCompileStepPattern(ctxt, NULL);
1045 } else if (CUR == '/') {
1046 PUSH(XSLT_OP_PARENT, NULL, NULL);
1049 if ((CUR != 0) || (CUR == '|')) {
1050 xsltCompileRelativePathPattern(ctxt, NULL);
1064 * xsltCompileLocationPathPattern:
1065 * @comp: the compilation context
1067 * Compile the XSLT LocationPathPattern and generates a precompiled
1068 * form suitable for fast matching.
1070 * [2] LocationPathPattern ::= '/' RelativePathPattern?
1071 * | IdKeyPattern (('/' | '//') RelativePathPattern)?
1072 * | '//'? RelativePathPattern
1075 xsltCompileLocationPathPattern(xsltParserContextPtr ctxt) {
1077 if ((CUR == '/') && (NXT(1) == '/')) {
1079 * since we reverse the query
1080 * a leading // can be safely ignored
1084 xsltCompileRelativePathPattern(ctxt, NULL);
1085 } else if (CUR == '/') {
1087 * We need to find root as the parent
1091 PUSH(XSLT_OP_ROOT, NULL, NULL);
1092 if ((CUR != 0) || (CUR == '|')) {
1093 PUSH(XSLT_OP_PARENT, NULL, NULL);
1094 xsltCompileRelativePathPattern(ctxt, NULL);
1096 } else if (CUR == '*') {
1097 xsltCompileRelativePathPattern(ctxt, NULL);
1098 } else if (CUR == '@') {
1099 xsltCompileRelativePathPattern(ctxt, NULL);
1102 name = xsltScanName(ctxt);
1104 xsltGenericError(xsltGenericErrorContext,
1105 "xsltCompileLocationPathPattern : Name expected\n");
1111 xsltCompileIdKeyPattern(ctxt, name, 1);
1112 if ((CUR == '/') && (NXT(1) == '/')) {
1113 PUSH(XSLT_OP_ANCESTOR, NULL, NULL);
1117 xsltCompileRelativePathPattern(ctxt, NULL);
1118 } else if (CUR == '/') {
1119 PUSH(XSLT_OP_PARENT, NULL, NULL);
1122 xsltCompileRelativePathPattern(ctxt, NULL);
1126 xsltCompileRelativePathPattern(ctxt, name);
1133 * xsltCompilePattern:
1134 * @pattern an XSLT pattern
1136 * Compile the XSLT pattern and generates a list of precompiled form suitable
1137 * for fast matching.
1139 * [1] Pattern ::= LocationPathPattern | Pattern '|' LocationPathPattern
1141 * Returns the generated pattern list or NULL in case of failure
1145 xsltCompilePattern(const xmlChar *pattern) {
1146 xsltParserContextPtr ctxt = NULL;
1147 xsltCompMatchPtr element, first = NULL, previous = NULL;
1148 int current, start, end;
1150 if (pattern == NULL) {
1151 xsltGenericError(xsltGenericErrorContext,
1152 "xsltCompilePattern : NULL pattern\n");
1156 #ifdef DEBUG_PARSING
1157 xsltGenericDebug(xsltGenericDebugContext,
1158 "xsltCompilePattern : parsing '%s'\n", pattern);
1161 ctxt = xsltNewParserContext();
1165 while (pattern[current] != 0) {
1167 while (IS_BLANK(pattern[current]))
1170 while ((pattern[end] != 0) && (pattern[end] != '|'))
1172 if (current == end) {
1173 xsltGenericError(xsltGenericErrorContext,
1174 "xsltCompilePattern : NULL pattern\n");
1177 element = xsltNewCompMatch();
1178 if (element == NULL) {
1183 else if (previous != NULL)
1184 previous->next = element;
1187 ctxt->comp = element;
1188 ctxt->base = xmlStrndup(&pattern[start], end - start);
1189 ctxt->cur = &(ctxt->base)[current - start];
1190 xsltCompileLocationPathPattern(ctxt);
1192 xmlFree((xmlChar *)ctxt->base);
1197 * Reverse for faster interpretation.
1199 xsltReverseCompMatch(element);
1202 * Set-up the priority
1204 if (((element->steps[0].op == XSLT_OP_ELEM) ||
1205 (element->steps[0].op == XSLT_OP_ATTR)) &&
1206 (element->steps[0].value != NULL) &&
1207 (element->steps[1].op == XSLT_OP_END)) {
1208 element->priority = 0;
1209 } else if ((element->steps[0].op == XSLT_OP_PI) &&
1210 (element->steps[0].value != NULL) &&
1211 (element->steps[1].op == XSLT_OP_END)) {
1212 element->priority = 0;
1213 } else if ((element->steps[0].op == XSLT_OP_NS) &&
1214 (element->steps[0].value != NULL) &&
1215 (element->steps[1].op == XSLT_OP_END)) {
1216 element->priority = -0.25;
1217 } else if (((element->steps[0].op == XSLT_OP_PI) ||
1218 (element->steps[0].op == XSLT_OP_TEXT) ||
1219 (element->steps[0].op == XSLT_OP_ALL) ||
1220 (element->steps[0].op == XSLT_OP_NODE) ||
1221 (element->steps[0].op == XSLT_OP_COMMENT)) &&
1222 (element->steps[1].op == XSLT_OP_END)) {
1223 element->priority = -0.5;
1225 element->priority = 0.5;
1227 if (pattern[end] == '|')
1232 xsltGenericError(xsltGenericErrorContext,
1233 "xsltCompilePattern : NULL pattern\n");
1237 xsltFreeParserContext(ctxt);
1242 xsltFreeParserContext(ctxt);
1244 xsltFreeCompMatchList(first);
1248 /************************************************************************
1250 * Module interfaces *
1252 ************************************************************************/
1256 * @style: an XSLT stylesheet
1257 * @cur: an XSLT template
1258 * @mode: the mode name or NULL
1259 * @modeURI: the mode URI or NULL
1261 * Register the XSLT pattern associated to @cur
1263 * Returns -1 in case of error, 0 otherwise
1266 xsltAddTemplate(xsltStylesheetPtr style, xsltTemplatePtr cur,
1267 const xmlChar *mode, const xmlChar *modeURI) {
1268 xsltCompMatchPtr pat, list, *top = NULL, next;
1269 const xmlChar *name = NULL;
1271 if ((style == NULL) || (cur == NULL) || (cur->match == NULL))
1274 pat = xsltCompilePattern(cur->match);
1279 pat->template = cur;
1281 pat->mode = xmlStrdup(mode);
1282 if (modeURI != NULL)
1283 pat->modeURI = xmlStrdup(modeURI);
1284 if (pat->priority != XSLT_PAT_NO_PRIORITY)
1285 cur->priority = pat->priority;
1287 pat->priority = cur->priority;
1290 * insert it in the hash table list corresponding to its lookup name
1292 switch (pat->steps[0].op) {
1294 if (pat->steps[0].value != NULL)
1295 name = pat->steps[0].value;
1297 top = (xsltCompMatchPtr *) &(style->attrMatch);
1301 case XSLT_OP_PARENT:
1302 case XSLT_OP_ANCESTOR:
1304 name = pat->steps[0].value;
1307 top = (xsltCompMatchPtr *) &(style->rootMatch);
1310 top = (xsltCompMatchPtr *) &(style->keyMatch);
1313 /* TODO optimize ID !!! */
1315 top = (xsltCompMatchPtr *) &(style->elemMatch);
1318 case XSLT_OP_PREDICATE:
1319 xsltGenericError(xsltGenericErrorContext,
1320 "xsltAddTemplate: invalid compiled pattern\n");
1321 xsltFreeCompMatch(pat);
1324 * TODO: some flags at the top level about type based patterns
1325 * would be faster than inclusion in the hash table.
1328 if (pat->steps[0].value != NULL)
1329 name = pat->steps[0].value;
1331 top = (xsltCompMatchPtr *) &(style->piMatch);
1333 case XSLT_OP_COMMENT:
1334 top = (xsltCompMatchPtr *) &(style->commentMatch);
1337 top = (xsltCompMatchPtr *) &(style->textMatch);
1340 if (pat->steps[0].value != NULL)
1341 name = pat->steps[0].value;
1343 top = (xsltCompMatchPtr *) &(style->elemMatch);
1348 if (style->templatesHash == NULL) {
1349 style->templatesHash = xmlHashCreate(1024);
1350 if (style->templatesHash == NULL) {
1351 xsltFreeCompMatch(pat);
1354 #ifdef DEBUG_PARSING
1355 xsltGenericDebug(xsltGenericDebugContext,
1356 "xsltAddTemplate: created template hash\n");
1358 xmlHashAddEntry3(style->templatesHash, name, mode, modeURI, pat);
1359 #ifdef DEBUG_PARSING
1360 xsltGenericDebug(xsltGenericDebugContext,
1361 "xsltAddTemplate: added new hash %s\n", name);
1364 list = (xsltCompMatchPtr) xmlHashLookup3(style->templatesHash,
1365 name, mode, modeURI);
1367 xmlHashAddEntry3(style->templatesHash, name,
1368 mode, modeURI, pat);
1369 #ifdef DEBUG_PARSING
1370 xsltGenericDebug(xsltGenericDebugContext,
1371 "xsltAddTemplate: added new hash %s\n", name);
1375 * Note '<=' since one must choose among the matching
1376 * template rules that are left, the one that occurs
1377 * last in the stylesheet
1379 if (list->priority <= pat->priority) {
1381 xmlHashUpdateEntry3(style->templatesHash, name,
1382 mode, modeURI, pat, NULL);
1383 #ifdef DEBUG_PARSING
1384 xsltGenericDebug(xsltGenericDebugContext,
1385 "xsltAddTemplate: added head hash for %s\n", name);
1388 while (list->next != NULL) {
1389 if (list->next->priority <= pat->priority)
1393 pat->next = list->next;
1398 } else if (top != NULL) {
1403 } else if (list->priority <= pat->priority) {
1407 while (list->next != NULL) {
1408 if (list->next->priority <= pat->priority)
1412 pat->next = list->next;
1416 xsltGenericError(xsltGenericErrorContext,
1417 "xsltAddTemplate: invalid compiled pattern\n");
1418 xsltFreeCompMatch(pat);
1428 * @ctxt: a XSLT process context
1430 * @style: the current style
1432 * Finds the template applying to this node, if @style is non-NULL
1433 * it means one need to look for the next imported template in scope.
1435 * Returns the xsltTemplatePtr or NULL if not found
1438 xsltGetTemplate(xsltTransformContextPtr ctxt, xmlNodePtr node,
1439 xsltStylesheetPtr style) {
1440 xsltStylesheetPtr curstyle;
1441 xsltTemplatePtr ret = NULL;
1442 const xmlChar *name = NULL;
1443 xsltCompMatchPtr list = NULL;
1445 if ((ctxt == NULL) || (node == NULL))
1448 if (style == NULL) {
1449 curstyle = ctxt->style;
1451 curstyle = xsltNextImport(style);
1454 while ((curstyle != NULL) && (curstyle != style)) {
1455 /* TODO : handle IDs/keys here ! */
1456 if (curstyle->templatesHash != NULL) {
1458 * Use the top name as selector
1460 switch (node->type) {
1461 case XML_ELEMENT_NODE:
1462 case XML_ATTRIBUTE_NODE:
1466 case XML_DOCUMENT_NODE:
1467 case XML_HTML_DOCUMENT_NODE:
1469 case XML_CDATA_SECTION_NODE:
1470 case XML_COMMENT_NODE:
1471 case XML_ENTITY_REF_NODE:
1472 case XML_ENTITY_NODE:
1473 case XML_DOCUMENT_TYPE_NODE:
1474 case XML_DOCUMENT_FRAG_NODE:
1475 case XML_NOTATION_NODE:
1477 case XML_ELEMENT_DECL:
1478 case XML_ATTRIBUTE_DECL:
1479 case XML_ENTITY_DECL:
1480 case XML_NAMESPACE_DECL:
1481 case XML_XINCLUDE_START:
1482 case XML_XINCLUDE_END:
1491 * find the list of appliable expressions based on the name
1493 list = (xsltCompMatchPtr) xmlHashLookup3(curstyle->templatesHash,
1494 name, ctxt->mode, ctxt->modeURI);
1496 while (list != NULL) {
1497 if (xsltTestCompMatch(ctxt, list, node,
1498 ctxt->mode, ctxt->modeURI)) {
1499 ret = list->template;
1507 * find alternate generic matches
1509 switch (node->type) {
1510 case XML_ELEMENT_NODE:
1511 list = curstyle->elemMatch;
1513 case XML_ATTRIBUTE_NODE:
1514 list = curstyle->attrMatch;
1517 list = curstyle->piMatch;
1519 case XML_DOCUMENT_NODE:
1520 case XML_HTML_DOCUMENT_NODE:
1521 list = curstyle->rootMatch;
1524 case XML_CDATA_SECTION_NODE:
1525 list = curstyle->textMatch;
1527 case XML_COMMENT_NODE:
1528 list = curstyle->commentMatch;
1530 case XML_ENTITY_REF_NODE:
1531 case XML_ENTITY_NODE:
1532 case XML_DOCUMENT_TYPE_NODE:
1533 case XML_DOCUMENT_FRAG_NODE:
1534 case XML_NOTATION_NODE:
1536 case XML_ELEMENT_DECL:
1537 case XML_ATTRIBUTE_DECL:
1538 case XML_ENTITY_DECL:
1539 case XML_NAMESPACE_DECL:
1540 case XML_XINCLUDE_START:
1541 case XML_XINCLUDE_END:
1547 while ((list != NULL) &&
1548 ((ret == NULL) || (list->priority > ret->priority))) {
1549 if (xsltTestCompMatch(ctxt, list, node,
1550 ctxt->mode, ctxt->modeURI)) {
1551 ret = list->template;
1556 if (node->_private != NULL) {
1557 list = curstyle->keyMatch;
1558 while ((list != NULL) &&
1559 ((ret == NULL) || (list->priority > ret->priority))) {
1560 if (xsltTestCompMatch(ctxt, list, node,
1561 ctxt->mode, ctxt->modeURI)) {
1562 ret = list->template;
1573 * Cycle on next curstylesheet import.
1575 curstyle = xsltNextImport(curstyle);
1582 * xsltFreeTemplateHashes:
1583 * @style: an XSLT stylesheet
1585 * Free up the memory used by xsltAddTemplate/xsltGetTemplate mechanism
1588 xsltFreeTemplateHashes(xsltStylesheetPtr style) {
1589 if (style->templatesHash != NULL)
1590 xmlHashFree((xmlHashTablePtr) style->templatesHash,
1591 (xmlHashDeallocator) xsltFreeCompMatchList);
1592 if (style->rootMatch != NULL)
1593 xsltFreeCompMatchList(style->rootMatch);
1594 if (style->keyMatch != NULL)
1595 xsltFreeCompMatchList(style->keyMatch);
1596 if (style->elemMatch != NULL)
1597 xsltFreeCompMatchList(style->elemMatch);
1598 if (style->attrMatch != NULL)
1599 xsltFreeCompMatchList(style->attrMatch);
1600 if (style->parentMatch != NULL)
1601 xsltFreeCompMatchList(style->parentMatch);
1602 if (style->textMatch != NULL)
1603 xsltFreeCompMatchList(style->textMatch);
1604 if (style->piMatch != NULL)
1605 xsltFreeCompMatchList(style->piMatch);
1606 if (style->commentMatch != NULL)
1607 xsltFreeCompMatchList(style->commentMatch);
1612 * @node: a node in the source tree
1613 * @pattern: an XSLT pattern
1615 * Determine if a node matches a pattern.
1618 xsltMatchPattern(xsltTransformContextPtr context,
1620 const xmlChar *pattern)
1623 xsltCompMatchPtr first, comp;
1625 if ((context != NULL) && (pattern != NULL)) {
1626 first = xsltCompilePattern(pattern);
1627 for (comp = first; comp != NULL; comp = comp->next) {
1628 match = xsltTestCompMatch(context, comp, node, NULL, NULL);
1633 xsltFreeCompMatchList(first);