1 /* libxml2 - Library for parsing XML documents
2 * Copyright (C) 2006-2019 Free Software Foundation, Inc.
3 *
4 * This file is not part of the GNU gettext program, but is used with
5 * GNU gettext.
6 *
7 * The original copyright notice is as follows:
8 */
9
10 /*
11 * Copyright (C) 1998-2012 Daniel Veillard. All Rights Reserved.
12 *
13 * Permission is hereby granted, free of charge, to any person obtaining a copy
14 * of this software and associated documentation files (the "Software"), to deal
15 * in the Software without restriction, including without limitation the rights
16 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
17 * copies of the Software, and to permit persons to whom the Software is fur-
18 * nished to do so, subject to the following conditions:
19 *
20 * The above copyright notice and this permission notice shall be included in
21 * all copies or substantial portions of the Software.
22 *
23 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
24 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FIT-
25 * NESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
26 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
27 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
28 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
29 * THE SOFTWARE.
30 *
31 * daniel@veillard.com
32 */
33
34 /*
35 * pattern.c: Implemetation of selectors for nodes
36 *
37 * Reference:
38 * http://www.w3.org/TR/2001/REC-xmlschema-1-20010502/
39 * to some extent
40 * http://www.w3.org/TR/1999/REC-xml-19991116
41 */
42
43 /*
44 * TODO:
45 * - compilation flags to check for specific syntaxes
46 * using flags of xmlPatterncompile()
47 * - making clear how pattern starting with / or . need to be handled,
48 * currently push(NULL, NULL) means a reset of the streaming context
49 * and indicating we are on / (the document node), probably need
50 * something similar for .
51 * - get rid of the "compile" starting with lowercase
52 * - DONE (2006-05-16): get rid of the Strdup/Strndup in case of dictionary
53 */
54
55 #define IN_LIBXML
56 #include "libxml.h"
57
58 #include <string.h>
59 #include <libxml/xmlmemory.h>
60 #include <libxml/tree.h>
61 #include <libxml/hash.h>
62 #include <libxml/dict.h>
63 #include <libxml/xmlerror.h>
64 #include <libxml/parserInternals.h>
65 #include <libxml/pattern.h>
66
67 #ifdef LIBXML_PATTERN_ENABLED
68
69 /* #define DEBUG_STREAMING */
70
71 #ifdef ERROR
72 #undef ERROR
73 #endif
74 #define ERROR(a, b, c, d)
75 #define ERROR5(a, b, c, d, e)
76
77 #define XML_STREAM_STEP_DESC 1
78 #define XML_STREAM_STEP_FINAL 2
79 #define XML_STREAM_STEP_ROOT 4
80 #define XML_STREAM_STEP_ATTR 8
81 #define XML_STREAM_STEP_NODE 16
82 #define XML_STREAM_STEP_IN_SET 32
83
84 /*
85 * NOTE: Those private flags (XML_STREAM_xxx) are used
86 * in _xmlStreamCtxt->flag. They extend the public
87 * xmlPatternFlags, so be carefull not to interfere with the
88 * reserved values for xmlPatternFlags.
89 */
90 #define XML_STREAM_FINAL_IS_ANY_NODE 1<<14
91 #define XML_STREAM_FROM_ROOT 1<<15
92 #define XML_STREAM_DESC 1<<16
93
94 /*
95 * XML_STREAM_ANY_NODE is used for comparison against
96 * xmlElementType enums, to indicate a node of any type.
97 */
98 #define XML_STREAM_ANY_NODE 100
99
100 #define XML_PATTERN_NOTPATTERN (XML_PATTERN_XPATH | \
101 XML_PATTERN_XSSEL | \
102 XML_PATTERN_XSFIELD)
103
104 #define XML_STREAM_XS_IDC(c) ((c)->flags & \
105 (XML_PATTERN_XSSEL | XML_PATTERN_XSFIELD))
106
107 #define XML_STREAM_XS_IDC_SEL(c) ((c)->flags & XML_PATTERN_XSSEL)
108
109 #define XML_STREAM_XS_IDC_FIELD(c) ((c)->flags & XML_PATTERN_XSFIELD)
110
111 #define XML_PAT_COPY_NSNAME(c, r, nsname) \
112 if ((c)->comp->dict) \
113 r = (xmlChar *) xmlDictLookup((c)->comp->dict, BAD_CAST nsname, -1); \
114 else r = xmlStrdup(BAD_CAST nsname);
115
116 #define XML_PAT_FREE_STRING(c, r) if ((c)->comp->dict == NULL) xmlFree(r);
117
118 typedef struct _xmlStreamStep xmlStreamStep;
119 typedef xmlStreamStep *xmlStreamStepPtr;
120 struct _xmlStreamStep {
121 int flags; /* properties of that step */
122 const xmlChar *name; /* first string value if NULL accept all */
123 const xmlChar *ns; /* second string value */
124 int nodeType; /* type of node */
125 };
126
127 typedef struct _xmlStreamComp xmlStreamComp;
128 typedef xmlStreamComp *xmlStreamCompPtr;
129 struct _xmlStreamComp {
130 xmlDict *dict; /* the dictionary if any */
131 int nbStep; /* number of steps in the automata */
132 int maxStep; /* allocated number of steps */
133 xmlStreamStepPtr steps; /* the array of steps */
134 int flags;
135 };
136
137 struct _xmlStreamCtxt {
138 struct _xmlStreamCtxt *next;/* link to next sub pattern if | */
139 xmlStreamCompPtr comp; /* the compiled stream */
140 int nbState; /* number of states in the automata */
141 int maxState; /* allocated number of states */
142 int level; /* how deep are we ? */
143 int *states; /* the array of step indexes */
144 int flags; /* validation options */
145 int blockLevel;
146 };
147
148 static void xmlFreeStreamComp(xmlStreamCompPtr comp);
149
150 /*
151 * Types are private:
152 */
153
154 typedef enum {
155 XML_OP_END=0,
156 XML_OP_ROOT,
157 XML_OP_ELEM,
158 XML_OP_CHILD,
159 XML_OP_ATTR,
160 XML_OP_PARENT,
161 XML_OP_ANCESTOR,
162 XML_OP_NS,
163 XML_OP_ALL
164 } xmlPatOp;
165
166
167 typedef struct _xmlStepState xmlStepState;
168 typedef xmlStepState *xmlStepStatePtr;
169 struct _xmlStepState {
170 int step;
171 xmlNodePtr node;
172 };
173
174 typedef struct _xmlStepStates xmlStepStates;
175 typedef xmlStepStates *xmlStepStatesPtr;
176 struct _xmlStepStates {
177 int nbstates;
178 int maxstates;
179 xmlStepStatePtr states;
180 };
181
182 typedef struct _xmlStepOp xmlStepOp;
183 typedef xmlStepOp *xmlStepOpPtr;
184 struct _xmlStepOp {
185 xmlPatOp op;
186 const xmlChar *value;
187 const xmlChar *value2; /* The namespace name */
188 };
189
190 #define PAT_FROM_ROOT (1<<8)
191 #define PAT_FROM_CUR (1<<9)
192
193 struct _xmlPattern {
194 void *data; /* the associated template */
195 xmlDictPtr dict; /* the optional dictionary */
196 struct _xmlPattern *next; /* next pattern if | is used */
197 const xmlChar *pattern; /* the pattern */
198 int flags; /* flags */
199 int nbStep;
200 int maxStep;
201 xmlStepOpPtr steps; /* ops for computation */
202 xmlStreamCompPtr stream; /* the streaming data if any */
203 };
204
205 typedef struct _xmlPatParserContext xmlPatParserContext;
206 typedef xmlPatParserContext *xmlPatParserContextPtr;
207 struct _xmlPatParserContext {
208 const xmlChar *cur; /* the current char being parsed */
209 const xmlChar *base; /* the full expression */
210 int error; /* error code */
211 xmlDictPtr dict; /* the dictionary if any */
212 xmlPatternPtr comp; /* the result */
213 xmlNodePtr elem; /* the current node if any */
214 const xmlChar **namespaces; /* the namespaces definitions */
215 int nb_namespaces; /* the number of namespaces */
216 };
217
218 /************************************************************************
219 * *
220 * Type functions *
221 * *
222 ************************************************************************/
223
224 /**
225 * xmlNewPattern:
226 *
227 * Create a new XSLT Pattern
228 *
229 * Returns the newly allocated xmlPatternPtr or NULL in case of error
230 */
231 static xmlPatternPtr
xmlNewPattern(void)232 xmlNewPattern(void) {
233 xmlPatternPtr cur;
234
235 cur = (xmlPatternPtr) xmlMalloc(sizeof(xmlPattern));
236 if (cur == NULL) {
237 ERROR(NULL, NULL, NULL,
238 "xmlNewPattern : malloc failed\n");
239 return(NULL);
240 }
241 memset(cur, 0, sizeof(xmlPattern));
242 cur->maxStep = 10;
243 cur->steps = (xmlStepOpPtr) xmlMalloc(cur->maxStep * sizeof(xmlStepOp));
244 if (cur->steps == NULL) {
245 xmlFree(cur);
246 ERROR(NULL, NULL, NULL,
247 "xmlNewPattern : malloc failed\n");
248 return(NULL);
249 }
250 return(cur);
251 }
252
253 /**
254 * xmlFreePattern:
255 * @comp: an XSLT comp
256 *
257 * Free up the memory allocated by @comp
258 */
259 void
xmlFreePattern(xmlPatternPtr comp)260 xmlFreePattern(xmlPatternPtr comp) {
261 xmlStepOpPtr op;
262 int i;
263
264 if (comp == NULL)
265 return;
266 if (comp->next != NULL)
267 xmlFreePattern(comp->next);
268 if (comp->stream != NULL)
269 xmlFreeStreamComp(comp->stream);
270 if (comp->pattern != NULL)
271 xmlFree((xmlChar *)comp->pattern);
272 if (comp->steps != NULL) {
273 if (comp->dict == NULL) {
274 for (i = 0;i < comp->nbStep;i++) {
275 op = &comp->steps[i];
276 if (op->value != NULL)
277 xmlFree((xmlChar *) op->value);
278 if (op->value2 != NULL)
279 xmlFree((xmlChar *) op->value2);
280 }
281 }
282 xmlFree(comp->steps);
283 }
284 if (comp->dict != NULL)
285 xmlDictFree(comp->dict);
286
287 memset(comp, -1, sizeof(xmlPattern));
288 xmlFree(comp);
289 }
290
291 /**
292 * xmlFreePatternList:
293 * @comp: an XSLT comp list
294 *
295 * Free up the memory allocated by all the elements of @comp
296 */
297 void
xmlFreePatternList(xmlPatternPtr comp)298 xmlFreePatternList(xmlPatternPtr comp) {
299 xmlPatternPtr cur;
300
301 while (comp != NULL) {
302 cur = comp;
303 comp = comp->next;
304 cur->next = NULL;
305 xmlFreePattern(cur);
306 }
307 }
308
309 /**
310 * xmlNewPatParserContext:
311 * @pattern: the pattern context
312 * @dict: the inherited dictionary or NULL
313 * @namespaces: the prefix definitions, array of [URI, prefix] terminated
314 * with [NULL, NULL] or NULL if no namespace is used
315 *
316 * Create a new XML pattern parser context
317 *
318 * Returns the newly allocated xmlPatParserContextPtr or NULL in case of error
319 */
320 static xmlPatParserContextPtr
xmlNewPatParserContext(const xmlChar * pattern,xmlDictPtr dict,const xmlChar ** namespaces)321 xmlNewPatParserContext(const xmlChar *pattern, xmlDictPtr dict,
322 const xmlChar **namespaces) {
323 xmlPatParserContextPtr cur;
324
325 if (pattern == NULL)
326 return(NULL);
327
328 cur = (xmlPatParserContextPtr) xmlMalloc(sizeof(xmlPatParserContext));
329 if (cur == NULL) {
330 ERROR(NULL, NULL, NULL,
331 "xmlNewPatParserContext : malloc failed\n");
332 return(NULL);
333 }
334 memset(cur, 0, sizeof(xmlPatParserContext));
335 cur->dict = dict;
336 cur->cur = pattern;
337 cur->base = pattern;
338 if (namespaces != NULL) {
339 int i;
340 for (i = 0;namespaces[2 * i] != NULL;i++)
341 ;
342 cur->nb_namespaces = i;
343 } else {
344 cur->nb_namespaces = 0;
345 }
346 cur->namespaces = namespaces;
347 return(cur);
348 }
349
350 /**
351 * xmlFreePatParserContext:
352 * @ctxt: an XSLT parser context
353 *
354 * Free up the memory allocated by @ctxt
355 */
356 static void
xmlFreePatParserContext(xmlPatParserContextPtr ctxt)357 xmlFreePatParserContext(xmlPatParserContextPtr ctxt) {
358 if (ctxt == NULL)
359 return;
360 memset(ctxt, -1, sizeof(xmlPatParserContext));
361 xmlFree(ctxt);
362 }
363
364 /**
365 * xmlPatternAdd:
366 * @comp: the compiled match expression
367 * @op: an op
368 * @value: the first value
369 * @value2: the second value
370 *
371 * Add a step to an XSLT Compiled Match
372 *
373 * Returns -1 in case of failure, 0 otherwise.
374 */
375 static int
xmlPatternAdd(xmlPatParserContextPtr ctxt ATTRIBUTE_UNUSED,xmlPatternPtr comp,xmlPatOp op,xmlChar * value,xmlChar * value2)376 xmlPatternAdd(xmlPatParserContextPtr ctxt ATTRIBUTE_UNUSED,
377 xmlPatternPtr comp,
378 xmlPatOp op, xmlChar * value, xmlChar * value2)
379 {
380 if (comp->nbStep >= comp->maxStep) {
381 xmlStepOpPtr temp;
382 temp = (xmlStepOpPtr) xmlRealloc(comp->steps, comp->maxStep * 2 *
383 sizeof(xmlStepOp));
384 if (temp == NULL) {
385 ERROR(ctxt, NULL, NULL,
386 "xmlPatternAdd: realloc failed\n");
387 return (-1);
388 }
389 comp->steps = temp;
390 comp->maxStep *= 2;
391 }
392 comp->steps[comp->nbStep].op = op;
393 comp->steps[comp->nbStep].value = value;
394 comp->steps[comp->nbStep].value2 = value2;
395 comp->nbStep++;
396 return (0);
397 }
398
399 #if 0
400 /**
401 * xsltSwapTopPattern:
402 * @comp: the compiled match expression
403 *
404 * reverse the two top steps.
405 */
406 static void
407 xsltSwapTopPattern(xmlPatternPtr comp) {
408 int i;
409 int j = comp->nbStep - 1;
410
411 if (j > 0) {
412 register const xmlChar *tmp;
413 register xmlPatOp op;
414 i = j - 1;
415 tmp = comp->steps[i].value;
416 comp->steps[i].value = comp->steps[j].value;
417 comp->steps[j].value = tmp;
418 tmp = comp->steps[i].value2;
419 comp->steps[i].value2 = comp->steps[j].value2;
420 comp->steps[j].value2 = tmp;
421 op = comp->steps[i].op;
422 comp->steps[i].op = comp->steps[j].op;
423 comp->steps[j].op = op;
424 }
425 }
426 #endif
427
428 /**
429 * xmlReversePattern:
430 * @comp: the compiled match expression
431 *
432 * reverse all the stack of expressions
433 *
434 * returns 0 in case of success and -1 in case of error.
435 */
436 static int
xmlReversePattern(xmlPatternPtr comp)437 xmlReversePattern(xmlPatternPtr comp) {
438 int i, j;
439
440 /*
441 * remove the leading // for //a or .//a
442 */
443 if ((comp->nbStep > 0) && (comp->steps[0].op == XML_OP_ANCESTOR)) {
444 for (i = 0, j = 1;j < comp->nbStep;i++,j++) {
445 comp->steps[i].value = comp->steps[j].value;
446 comp->steps[i].value2 = comp->steps[j].value2;
447 comp->steps[i].op = comp->steps[j].op;
448 }
449 comp->nbStep--;
450 }
451 if (comp->nbStep >= comp->maxStep) {
452 xmlStepOpPtr temp;
453 temp = (xmlStepOpPtr) xmlRealloc(comp->steps, comp->maxStep * 2 *
454 sizeof(xmlStepOp));
455 if (temp == NULL) {
456 ERROR(ctxt, NULL, NULL,
457 "xmlReversePattern: realloc failed\n");
458 return (-1);
459 }
460 comp->steps = temp;
461 comp->maxStep *= 2;
462 }
463 i = 0;
464 j = comp->nbStep - 1;
465 while (j > i) {
466 register const xmlChar *tmp;
467 register xmlPatOp op;
468 tmp = comp->steps[i].value;
469 comp->steps[i].value = comp->steps[j].value;
470 comp->steps[j].value = tmp;
471 tmp = comp->steps[i].value2;
472 comp->steps[i].value2 = comp->steps[j].value2;
473 comp->steps[j].value2 = tmp;
474 op = comp->steps[i].op;
475 comp->steps[i].op = comp->steps[j].op;
476 comp->steps[j].op = op;
477 j--;
478 i++;
479 }
480 comp->steps[comp->nbStep].value = NULL;
481 comp->steps[comp->nbStep].value2 = NULL;
482 comp->steps[comp->nbStep++].op = XML_OP_END;
483 return(0);
484 }
485
486 /************************************************************************
487 * *
488 * The interpreter for the precompiled patterns *
489 * *
490 ************************************************************************/
491
492 static int
xmlPatPushState(xmlStepStates * states,int step,xmlNodePtr node)493 xmlPatPushState(xmlStepStates *states, int step, xmlNodePtr node) {
494 if ((states->states == NULL) || (states->maxstates <= 0)) {
495 states->maxstates = 4;
496 states->nbstates = 0;
497 states->states = xmlMalloc(4 * sizeof(xmlStepState));
498 }
499 else if (states->maxstates <= states->nbstates) {
500 xmlStepState *tmp;
501
502 tmp = (xmlStepStatePtr) xmlRealloc(states->states,
503 2 * states->maxstates * sizeof(xmlStepState));
504 if (tmp == NULL)
505 return(-1);
506 states->states = tmp;
507 states->maxstates *= 2;
508 }
509 states->states[states->nbstates].step = step;
510 states->states[states->nbstates++].node = node;
511 #if 0
512 fprintf(stderr, "Push: %d, %s\n", step, node->name);
513 #endif
514 return(0);
515 }
516
517 /**
518 * xmlPatMatch:
519 * @comp: the precompiled pattern
520 * @node: a node
521 *
522 * Test whether the node matches the pattern
523 *
524 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
525 */
526 static int
xmlPatMatch(xmlPatternPtr comp,xmlNodePtr node)527 xmlPatMatch(xmlPatternPtr comp, xmlNodePtr node) {
528 int i;
529 xmlStepOpPtr step;
530 xmlStepStates states = {0, 0, NULL}; /* // may require backtrack */
531
532 if ((comp == NULL) || (node == NULL)) return(-1);
533 i = 0;
534 restart:
535 for (;i < comp->nbStep;i++) {
536 step = &comp->steps[i];
537 switch (step->op) {
538 case XML_OP_END:
539 goto found;
540 case XML_OP_ROOT:
541 if (node->type == XML_NAMESPACE_DECL)
542 goto rollback;
543 node = node->parent;
544 if ((node->type == XML_DOCUMENT_NODE) ||
545 #ifdef LIBXML_DOCB_ENABLED
546 (node->type == XML_DOCB_DOCUMENT_NODE) ||
547 #endif
548 (node->type == XML_HTML_DOCUMENT_NODE))
549 continue;
550 goto rollback;
551 case XML_OP_ELEM:
552 if (node->type != XML_ELEMENT_NODE)
553 goto rollback;
554 if (step->value == NULL)
555 continue;
556 if (step->value[0] != node->name[0])
557 goto rollback;
558 if (!xmlStrEqual(step->value, node->name))
559 goto rollback;
560
561 /* Namespace test */
562 if (node->ns == NULL) {
563 if (step->value2 != NULL)
564 goto rollback;
565 } else if (node->ns->href != NULL) {
566 if (step->value2 == NULL)
567 goto rollback;
568 if (!xmlStrEqual(step->value2, node->ns->href))
569 goto rollback;
570 }
571 continue;
572 case XML_OP_CHILD: {
573 xmlNodePtr lst;
574
575 if ((node->type != XML_ELEMENT_NODE) &&
576 (node->type != XML_DOCUMENT_NODE) &&
577 #ifdef LIBXML_DOCB_ENABLED
578 (node->type != XML_DOCB_DOCUMENT_NODE) &&
579 #endif
580 (node->type != XML_HTML_DOCUMENT_NODE))
581 goto rollback;
582
583 lst = node->children;
584
585 if (step->value != NULL) {
586 while (lst != NULL) {
587 if ((lst->type == XML_ELEMENT_NODE) &&
588 (step->value[0] == lst->name[0]) &&
589 (xmlStrEqual(step->value, lst->name)))
590 break;
591 lst = lst->next;
592 }
593 if (lst != NULL)
594 continue;
595 }
596 goto rollback;
597 }
598 case XML_OP_ATTR:
599 if (node->type != XML_ATTRIBUTE_NODE)
600 goto rollback;
601 if (step->value != NULL) {
602 if (step->value[0] != node->name[0])
603 goto rollback;
604 if (!xmlStrEqual(step->value, node->name))
605 goto rollback;
606 }
607 /* Namespace test */
608 if (node->ns == NULL) {
609 if (step->value2 != NULL)
610 goto rollback;
611 } else if (step->value2 != NULL) {
612 if (!xmlStrEqual(step->value2, node->ns->href))
613 goto rollback;
614 }
615 continue;
616 case XML_OP_PARENT:
617 if ((node->type == XML_DOCUMENT_NODE) ||
618 (node->type == XML_HTML_DOCUMENT_NODE) ||
619 #ifdef LIBXML_DOCB_ENABLED
620 (node->type == XML_DOCB_DOCUMENT_NODE) ||
621 #endif
622 (node->type == XML_NAMESPACE_DECL))
623 goto rollback;
624 node = node->parent;
625 if (node == NULL)
626 goto rollback;
627 if (step->value == NULL)
628 continue;
629 if (step->value[0] != node->name[0])
630 goto rollback;
631 if (!xmlStrEqual(step->value, node->name))
632 goto rollback;
633 /* Namespace test */
634 if (node->ns == NULL) {
635 if (step->value2 != NULL)
636 goto rollback;
637 } else if (node->ns->href != NULL) {
638 if (step->value2 == NULL)
639 goto rollback;
640 if (!xmlStrEqual(step->value2, node->ns->href))
641 goto rollback;
642 }
643 continue;
644 case XML_OP_ANCESTOR:
645 /* TODO: implement coalescing of ANCESTOR/NODE ops */
646 if (step->value == NULL) {
647 i++;
648 step = &comp->steps[i];
649 if (step->op == XML_OP_ROOT)
650 goto found;
651 if (step->op != XML_OP_ELEM)
652 goto rollback;
653 if (step->value == NULL)
654 return(-1);
655 }
656 if (node == NULL)
657 goto rollback;
658 if ((node->type == XML_DOCUMENT_NODE) ||
659 (node->type == XML_HTML_DOCUMENT_NODE) ||
660 #ifdef LIBXML_DOCB_ENABLED
661 (node->type == XML_DOCB_DOCUMENT_NODE) ||
662 #endif
663 (node->type == XML_NAMESPACE_DECL))
664 goto rollback;
665 node = node->parent;
666 while (node != NULL) {
667 if ((node->type == XML_ELEMENT_NODE) &&
668 (step->value[0] == node->name[0]) &&
669 (xmlStrEqual(step->value, node->name))) {
670 /* Namespace test */
671 if (node->ns == NULL) {
672 if (step->value2 == NULL)
673 break;
674 } else if (node->ns->href != NULL) {
675 if ((step->value2 != NULL) &&
676 (xmlStrEqual(step->value2, node->ns->href)))
677 break;
678 }
679 }
680 node = node->parent;
681 }
682 if (node == NULL)
683 goto rollback;
684 /*
685 * prepare a potential rollback from here
686 * for ancestors of that node.
687 */
688 if (step->op == XML_OP_ANCESTOR)
689 xmlPatPushState(&states, i, node);
690 else
691 xmlPatPushState(&states, i - 1, node);
692 continue;
693 case XML_OP_NS:
694 if (node->type != XML_ELEMENT_NODE)
695 goto rollback;
696 if (node->ns == NULL) {
697 if (step->value != NULL)
698 goto rollback;
699 } else if (node->ns->href != NULL) {
700 if (step->value == NULL)
701 goto rollback;
702 if (!xmlStrEqual(step->value, node->ns->href))
703 goto rollback;
704 }
705 break;
706 case XML_OP_ALL:
707 if (node->type != XML_ELEMENT_NODE)
708 goto rollback;
709 break;
710 }
711 }
712 found:
713 if (states.states != NULL) {
714 /* Free the rollback states */
715 xmlFree(states.states);
716 }
717 return(1);
718 rollback:
719 /* got an error try to rollback */
720 if (states.states == NULL)
721 return(0);
722 if (states.nbstates <= 0) {
723 xmlFree(states.states);
724 return(0);
725 }
726 states.nbstates--;
727 i = states.states[states.nbstates].step;
728 node = states.states[states.nbstates].node;
729 #if 0
730 fprintf(stderr, "Pop: %d, %s\n", i, node->name);
731 #endif
732 goto restart;
733 }
734
735 /************************************************************************
736 * *
737 * Dedicated parser for templates *
738 * *
739 ************************************************************************/
740
741 #define TODO \
742 xmlGenericError(xmlGenericErrorContext, \
743 "Unimplemented block at %s:%d\n", \
744 __FILE__, __LINE__);
745 #define CUR (*ctxt->cur)
746 #define SKIP(val) ctxt->cur += (val)
747 #define NXT(val) ctxt->cur[(val)]
748 #define PEEKPREV(val) ctxt->cur[-(val)]
749 #define CUR_PTR ctxt->cur
750
751 #define SKIP_BLANKS \
752 while (IS_BLANK_CH(CUR)) NEXT
753
754 #define CURRENT (*ctxt->cur)
755 #define NEXT ((*ctxt->cur) ? ctxt->cur++: ctxt->cur)
756
757
758 #define PUSH(op, val, val2) \
759 if (xmlPatternAdd(ctxt, ctxt->comp, (op), (val), (val2))) goto error;
760
761 #define XSLT_ERROR(X) \
762 { xsltError(ctxt, __FILE__, __LINE__, X); \
763 ctxt->error = (X); return; }
764
765 #define XSLT_ERROR0(X) \
766 { xsltError(ctxt, __FILE__, __LINE__, X); \
767 ctxt->error = (X); return(0); }
768
769 #if 0
770 /**
771 * xmlPatScanLiteral:
772 * @ctxt: the XPath Parser context
773 *
774 * Parse an XPath Litteral:
775 *
776 * [29] Literal ::= '"' [^"]* '"'
777 * | "'" [^']* "'"
778 *
779 * Returns the Literal parsed or NULL
780 */
781
782 static xmlChar *
783 xmlPatScanLiteral(xmlPatParserContextPtr ctxt) {
784 const xmlChar *q, *cur;
785 xmlChar *ret = NULL;
786 int val, len;
787
788 SKIP_BLANKS;
789 if (CUR == '"') {
790 NEXT;
791 cur = q = CUR_PTR;
792 val = xmlStringCurrentChar(NULL, cur, &len);
793 while ((IS_CHAR(val)) && (val != '"')) {
794 cur += len;
795 val = xmlStringCurrentChar(NULL, cur, &len);
796 }
797 if (!IS_CHAR(val)) {
798 ctxt->error = 1;
799 return(NULL);
800 } else {
801 if (ctxt->dict)
802 ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
803 else
804 ret = xmlStrndup(q, cur - q);
805 }
806 cur += len;
807 CUR_PTR = cur;
808 } else if (CUR == '\'') {
809 NEXT;
810 cur = q = CUR_PTR;
811 val = xmlStringCurrentChar(NULL, cur, &len);
812 while ((IS_CHAR(val)) && (val != '\'')) {
813 cur += len;
814 val = xmlStringCurrentChar(NULL, cur, &len);
815 }
816 if (!IS_CHAR(val)) {
817 ctxt->error = 1;
818 return(NULL);
819 } else {
820 if (ctxt->dict)
821 ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
822 else
823 ret = xmlStrndup(q, cur - q);
824 }
825 cur += len;
826 CUR_PTR = cur;
827 } else {
828 /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
829 ctxt->error = 1;
830 return(NULL);
831 }
832 return(ret);
833 }
834 #endif
835
836 /**
837 * xmlPatScanName:
838 * @ctxt: the XPath Parser context
839 *
840 * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' |
841 * CombiningChar | Extender
842 *
843 * [5] Name ::= (Letter | '_' | ':') (NameChar)*
844 *
845 * [6] Names ::= Name (S Name)*
846 *
847 * Returns the Name parsed or NULL
848 */
849
850 static xmlChar *
xmlPatScanName(xmlPatParserContextPtr ctxt)851 xmlPatScanName(xmlPatParserContextPtr ctxt) {
852 const xmlChar *q, *cur;
853 xmlChar *ret = NULL;
854 int val, len;
855
856 SKIP_BLANKS;
857
858 cur = q = CUR_PTR;
859 val = xmlStringCurrentChar(NULL, cur, &len);
860 if (!IS_LETTER(val) && (val != '_') && (val != ':'))
861 return(NULL);
862
863 while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
864 (val == '.') || (val == '-') ||
865 (val == '_') ||
866 (IS_COMBINING(val)) ||
867 (IS_EXTENDER(val))) {
868 cur += len;
869 val = xmlStringCurrentChar(NULL, cur, &len);
870 }
871 if (ctxt->dict)
872 ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
873 else
874 ret = xmlStrndup(q, cur - q);
875 CUR_PTR = cur;
876 return(ret);
877 }
878
879 /**
880 * xmlPatScanNCName:
881 * @ctxt: the XPath Parser context
882 *
883 * Parses a non qualified name
884 *
885 * Returns the Name parsed or NULL
886 */
887
888 static xmlChar *
xmlPatScanNCName(xmlPatParserContextPtr ctxt)889 xmlPatScanNCName(xmlPatParserContextPtr ctxt) {
890 const xmlChar *q, *cur;
891 xmlChar *ret = NULL;
892 int val, len;
893
894 SKIP_BLANKS;
895
896 cur = q = CUR_PTR;
897 val = xmlStringCurrentChar(NULL, cur, &len);
898 if (!IS_LETTER(val) && (val != '_'))
899 return(NULL);
900
901 while ((IS_LETTER(val)) || (IS_DIGIT(val)) ||
902 (val == '.') || (val == '-') ||
903 (val == '_') ||
904 (IS_COMBINING(val)) ||
905 (IS_EXTENDER(val))) {
906 cur += len;
907 val = xmlStringCurrentChar(NULL, cur, &len);
908 }
909 if (ctxt->dict)
910 ret = (xmlChar *) xmlDictLookup(ctxt->dict, q, cur - q);
911 else
912 ret = xmlStrndup(q, cur - q);
913 CUR_PTR = cur;
914 return(ret);
915 }
916
917 #if 0
918 /**
919 * xmlPatScanQName:
920 * @ctxt: the XPath Parser context
921 * @prefix: the place to store the prefix
922 *
923 * Parse a qualified name
924 *
925 * Returns the Name parsed or NULL
926 */
927
928 static xmlChar *
929 xmlPatScanQName(xmlPatParserContextPtr ctxt, xmlChar **prefix) {
930 xmlChar *ret = NULL;
931
932 *prefix = NULL;
933 ret = xmlPatScanNCName(ctxt);
934 if (CUR == ':') {
935 *prefix = ret;
936 NEXT;
937 ret = xmlPatScanNCName(ctxt);
938 }
939 return(ret);
940 }
941 #endif
942
943 /**
944 * xmlCompileAttributeTest:
945 * @ctxt: the compilation context
946 *
947 * Compile an attribute test.
948 */
949 static void
xmlCompileAttributeTest(xmlPatParserContextPtr ctxt)950 xmlCompileAttributeTest(xmlPatParserContextPtr ctxt) {
951 xmlChar *token = NULL;
952 xmlChar *name = NULL;
953 xmlChar *URL = NULL;
954
955 SKIP_BLANKS;
956 name = xmlPatScanNCName(ctxt);
957 if (name == NULL) {
958 if (CUR == '*') {
959 PUSH(XML_OP_ATTR, NULL, NULL);
960 NEXT;
961 } else {
962 ERROR(NULL, NULL, NULL,
963 "xmlCompileAttributeTest : Name expected\n");
964 ctxt->error = 1;
965 }
966 return;
967 }
968 if (CUR == ':') {
969 int i;
970 xmlChar *prefix = name;
971
972 NEXT;
973
974 if (IS_BLANK_CH(CUR)) {
975 ERROR5(NULL, NULL, NULL, "Invalid QName.\n", NULL);
976 XML_PAT_FREE_STRING(ctxt, prefix);
977 ctxt->error = 1;
978 goto error;
979 }
980 /*
981 * This is a namespace match
982 */
983 token = xmlPatScanName(ctxt);
984 if ((prefix[0] == 'x') &&
985 (prefix[1] == 'm') &&
986 (prefix[2] == 'l') &&
987 (prefix[3] == 0))
988 {
989 XML_PAT_COPY_NSNAME(ctxt, URL, XML_XML_NAMESPACE);
990 } else {
991 for (i = 0;i < ctxt->nb_namespaces;i++) {
992 if (xmlStrEqual(ctxt->namespaces[2 * i + 1], prefix)) {
993 XML_PAT_COPY_NSNAME(ctxt, URL, ctxt->namespaces[2 * i])
994 break;
995 }
996 }
997 if (i >= ctxt->nb_namespaces) {
998 ERROR5(NULL, NULL, NULL,
999 "xmlCompileAttributeTest : no namespace bound to prefix %s\n",
1000 prefix);
1001 XML_PAT_FREE_STRING(ctxt, prefix);
1002 ctxt->error = 1;
1003 goto error;
1004 }
1005 }
1006 XML_PAT_FREE_STRING(ctxt, prefix);
1007 if (token == NULL) {
1008 if (CUR == '*') {
1009 NEXT;
1010 PUSH(XML_OP_ATTR, NULL, URL);
1011 } else {
1012 ERROR(NULL, NULL, NULL,
1013 "xmlCompileAttributeTest : Name expected\n");
1014 ctxt->error = 1;
1015 goto error;
1016 }
1017 } else {
1018 PUSH(XML_OP_ATTR, token, URL);
1019 }
1020 } else {
1021 PUSH(XML_OP_ATTR, name, NULL);
1022 }
1023 return;
1024 error:
1025 if (URL != NULL)
1026 XML_PAT_FREE_STRING(ctxt, URL)
1027 if (token != NULL)
1028 XML_PAT_FREE_STRING(ctxt, token);
1029 }
1030
1031 /**
1032 * xmlCompileStepPattern:
1033 * @ctxt: the compilation context
1034 *
1035 * Compile the Step Pattern and generates a precompiled
1036 * form suitable for fast matching.
1037 *
1038 * [3] Step ::= '.' | NameTest
1039 * [4] NameTest ::= QName | '*' | NCName ':' '*'
1040 */
1041
1042 static void
xmlCompileStepPattern(xmlPatParserContextPtr ctxt)1043 xmlCompileStepPattern(xmlPatParserContextPtr ctxt) {
1044 xmlChar *token = NULL;
1045 xmlChar *name = NULL;
1046 xmlChar *URL = NULL;
1047 int hasBlanks = 0;
1048
1049 SKIP_BLANKS;
1050 if (CUR == '.') {
1051 /*
1052 * Context node.
1053 */
1054 NEXT;
1055 PUSH(XML_OP_ELEM, NULL, NULL);
1056 return;
1057 }
1058 if (CUR == '@') {
1059 /*
1060 * Attribute test.
1061 */
1062 if (XML_STREAM_XS_IDC_SEL(ctxt->comp)) {
1063 ERROR5(NULL, NULL, NULL,
1064 "Unexpected attribute axis in '%s'.\n", ctxt->base);
1065 ctxt->error = 1;
1066 return;
1067 }
1068 NEXT;
1069 xmlCompileAttributeTest(ctxt);
1070 if (ctxt->error != 0)
1071 goto error;
1072 return;
1073 }
1074 name = xmlPatScanNCName(ctxt);
1075 if (name == NULL) {
1076 if (CUR == '*') {
1077 NEXT;
1078 PUSH(XML_OP_ALL, NULL, NULL);
1079 return;
1080 } else {
1081 ERROR(NULL, NULL, NULL,
1082 "xmlCompileStepPattern : Name expected\n");
1083 ctxt->error = 1;
1084 return;
1085 }
1086 }
1087 if (IS_BLANK_CH(CUR)) {
1088 hasBlanks = 1;
1089 SKIP_BLANKS;
1090 }
1091 if (CUR == ':') {
1092 NEXT;
1093 if (CUR != ':') {
1094 xmlChar *prefix = name;
1095 int i;
1096
1097 if (hasBlanks || IS_BLANK_CH(CUR)) {
1098 ERROR5(NULL, NULL, NULL, "Invalid QName.\n", NULL);
1099 ctxt->error = 1;
1100 goto error;
1101 }
1102 /*
1103 * This is a namespace match
1104 */
1105 token = xmlPatScanName(ctxt);
1106 if ((prefix[0] == 'x') &&
1107 (prefix[1] == 'm') &&
1108 (prefix[2] == 'l') &&
1109 (prefix[3] == 0))
1110 {
1111 XML_PAT_COPY_NSNAME(ctxt, URL, XML_XML_NAMESPACE)
1112 } else {
1113 for (i = 0;i < ctxt->nb_namespaces;i++) {
1114 if (xmlStrEqual(ctxt->namespaces[2 * i + 1], prefix)) {
1115 XML_PAT_COPY_NSNAME(ctxt, URL, ctxt->namespaces[2 * i])
1116 break;
1117 }
1118 }
1119 if (i >= ctxt->nb_namespaces) {
1120 ERROR5(NULL, NULL, NULL,
1121 "xmlCompileStepPattern : no namespace bound to prefix %s\n",
1122 prefix);
1123 ctxt->error = 1;
1124 goto error;
1125 }
1126 }
1127 XML_PAT_FREE_STRING(ctxt, prefix);
1128 name = NULL;
1129 if (token == NULL) {
1130 if (CUR == '*') {
1131 NEXT;
1132 PUSH(XML_OP_NS, URL, NULL);
1133 } else {
1134 ERROR(NULL, NULL, NULL,
1135 "xmlCompileStepPattern : Name expected\n");
1136 ctxt->error = 1;
1137 goto error;
1138 }
1139 } else {
1140 PUSH(XML_OP_ELEM, token, URL);
1141 }
1142 } else {
1143 NEXT;
1144 if (xmlStrEqual(name, (const xmlChar *) "child")) {
1145 XML_PAT_FREE_STRING(ctxt, name);
1146 name = xmlPatScanName(ctxt);
1147 if (name == NULL) {
1148 if (CUR == '*') {
1149 NEXT;
1150 PUSH(XML_OP_ALL, NULL, NULL);
1151 return;
1152 } else {
1153 ERROR(NULL, NULL, NULL,
1154 "xmlCompileStepPattern : QName expected\n");
1155 ctxt->error = 1;
1156 goto error;
1157 }
1158 }
1159 if (CUR == ':') {
1160 xmlChar *prefix = name;
1161 int i;
1162
1163 NEXT;
1164 if (IS_BLANK_CH(CUR)) {
1165 ERROR5(NULL, NULL, NULL, "Invalid QName.\n", NULL);
1166 ctxt->error = 1;
1167 goto error;
1168 }
1169 /*
1170 * This is a namespace match
1171 */
1172 token = xmlPatScanName(ctxt);
1173 if ((prefix[0] == 'x') &&
1174 (prefix[1] == 'm') &&
1175 (prefix[2] == 'l') &&
1176 (prefix[3] == 0))
1177 {
1178 XML_PAT_COPY_NSNAME(ctxt, URL, XML_XML_NAMESPACE)
1179 } else {
1180 for (i = 0;i < ctxt->nb_namespaces;i++) {
1181 if (xmlStrEqual(ctxt->namespaces[2 * i + 1], prefix)) {
1182 XML_PAT_COPY_NSNAME(ctxt, URL, ctxt->namespaces[2 * i])
1183 break;
1184 }
1185 }
1186 if (i >= ctxt->nb_namespaces) {
1187 ERROR5(NULL, NULL, NULL,
1188 "xmlCompileStepPattern : no namespace bound "
1189 "to prefix %s\n", prefix);
1190 ctxt->error = 1;
1191 goto error;
1192 }
1193 }
1194 XML_PAT_FREE_STRING(ctxt, prefix);
1195 name = NULL;
1196 if (token == NULL) {
1197 if (CUR == '*') {
1198 NEXT;
1199 PUSH(XML_OP_NS, URL, NULL);
1200 } else {
1201 ERROR(NULL, NULL, NULL,
1202 "xmlCompileStepPattern : Name expected\n");
1203 ctxt->error = 1;
1204 goto error;
1205 }
1206 } else {
1207 PUSH(XML_OP_CHILD, token, URL);
1208 }
1209 } else
1210 PUSH(XML_OP_CHILD, name, NULL);
1211 return;
1212 } else if (xmlStrEqual(name, (const xmlChar *) "attribute")) {
1213 XML_PAT_FREE_STRING(ctxt, name)
1214 name = NULL;
1215 if (XML_STREAM_XS_IDC_SEL(ctxt->comp)) {
1216 ERROR5(NULL, NULL, NULL,
1217 "Unexpected attribute axis in '%s'.\n", ctxt->base);
1218 ctxt->error = 1;
1219 goto error;
1220 }
1221 xmlCompileAttributeTest(ctxt);
1222 if (ctxt->error != 0)
1223 goto error;
1224 return;
1225 } else {
1226 ERROR5(NULL, NULL, NULL,
1227 "The 'element' or 'attribute' axis is expected.\n", NULL);
1228 ctxt->error = 1;
1229 goto error;
1230 }
1231 }
1232 } else if (CUR == '*') {
1233 if (name != NULL) {
1234 ctxt->error = 1;
1235 goto error;
1236 }
1237 NEXT;
1238 PUSH(XML_OP_ALL, token, NULL);
1239 } else {
1240 PUSH(XML_OP_ELEM, name, NULL);
1241 }
1242 return;
1243 error:
1244 if (URL != NULL)
1245 XML_PAT_FREE_STRING(ctxt, URL)
1246 if (token != NULL)
1247 XML_PAT_FREE_STRING(ctxt, token)
1248 if (name != NULL)
1249 XML_PAT_FREE_STRING(ctxt, name)
1250 }
1251
1252 /**
1253 * xmlCompilePathPattern:
1254 * @ctxt: the compilation context
1255 *
1256 * Compile the Path Pattern and generates a precompiled
1257 * form suitable for fast matching.
1258 *
1259 * [5] Path ::= ('.//')? ( Step '/' )* ( Step | '@' NameTest )
1260 */
1261 static void
xmlCompilePathPattern(xmlPatParserContextPtr ctxt)1262 xmlCompilePathPattern(xmlPatParserContextPtr ctxt) {
1263 SKIP_BLANKS;
1264 if (CUR == '/') {
1265 ctxt->comp->flags |= PAT_FROM_ROOT;
1266 } else if ((CUR == '.') || (ctxt->comp->flags & XML_PATTERN_NOTPATTERN)) {
1267 ctxt->comp->flags |= PAT_FROM_CUR;
1268 }
1269
1270 if ((CUR == '/') && (NXT(1) == '/')) {
1271 PUSH(XML_OP_ANCESTOR, NULL, NULL);
1272 NEXT;
1273 NEXT;
1274 } else if ((CUR == '.') && (NXT(1) == '/') && (NXT(2) == '/')) {
1275 PUSH(XML_OP_ANCESTOR, NULL, NULL);
1276 NEXT;
1277 NEXT;
1278 NEXT;
1279 /* Check for incompleteness. */
1280 SKIP_BLANKS;
1281 if (CUR == 0) {
1282 ERROR5(NULL, NULL, NULL,
1283 "Incomplete expression '%s'.\n", ctxt->base);
1284 ctxt->error = 1;
1285 goto error;
1286 }
1287 }
1288 if (CUR == '@') {
1289 NEXT;
1290 xmlCompileAttributeTest(ctxt);
1291 SKIP_BLANKS;
1292 /* TODO: check for incompleteness */
1293 if (CUR != 0) {
1294 xmlCompileStepPattern(ctxt);
1295 if (ctxt->error != 0)
1296 goto error;
1297 }
1298 } else {
1299 if (CUR == '/') {
1300 PUSH(XML_OP_ROOT, NULL, NULL);
1301 NEXT;
1302 /* Check for incompleteness. */
1303 SKIP_BLANKS;
1304 if (CUR == 0) {
1305 ERROR5(NULL, NULL, NULL,
1306 "Incomplete expression '%s'.\n", ctxt->base);
1307 ctxt->error = 1;
1308 goto error;
1309 }
1310 }
1311 xmlCompileStepPattern(ctxt);
1312 if (ctxt->error != 0)
1313 goto error;
1314 SKIP_BLANKS;
1315 while (CUR == '/') {
1316 if (NXT(1) == '/') {
1317 PUSH(XML_OP_ANCESTOR, NULL, NULL);
1318 NEXT;
1319 NEXT;
1320 SKIP_BLANKS;
1321 xmlCompileStepPattern(ctxt);
1322 if (ctxt->error != 0)
1323 goto error;
1324 } else {
1325 PUSH(XML_OP_PARENT, NULL, NULL);
1326 NEXT;
1327 SKIP_BLANKS;
1328 if (CUR == 0) {
1329 ERROR5(NULL, NULL, NULL,
1330 "Incomplete expression '%s'.\n", ctxt->base);
1331 ctxt->error = 1;
1332 goto error;
1333 }
1334 xmlCompileStepPattern(ctxt);
1335 if (ctxt->error != 0)
1336 goto error;
1337 }
1338 }
1339 }
1340 if (CUR != 0) {
1341 ERROR5(NULL, NULL, NULL,
1342 "Failed to compile pattern %s\n", ctxt->base);
1343 ctxt->error = 1;
1344 }
1345 error:
1346 return;
1347 }
1348
1349 /**
1350 * xmlCompileIDCXPathPath:
1351 * @ctxt: the compilation context
1352 *
1353 * Compile the Path Pattern and generates a precompiled
1354 * form suitable for fast matching.
1355 *
1356 * [5] Path ::= ('.//')? ( Step '/' )* ( Step | '@' NameTest )
1357 */
1358 static void
xmlCompileIDCXPathPath(xmlPatParserContextPtr ctxt)1359 xmlCompileIDCXPathPath(xmlPatParserContextPtr ctxt) {
1360 SKIP_BLANKS;
1361 if (CUR == '/') {
1362 ERROR5(NULL, NULL, NULL,
1363 "Unexpected selection of the document root in '%s'.\n",
1364 ctxt->base);
1365 goto error;
1366 }
1367 ctxt->comp->flags |= PAT_FROM_CUR;
1368
1369 if (CUR == '.') {
1370 /* "." - "self::node()" */
1371 NEXT;
1372 SKIP_BLANKS;
1373 if (CUR == 0) {
1374 /*
1375 * Selection of the context node.
1376 */
1377 PUSH(XML_OP_ELEM, NULL, NULL);
1378 return;
1379 }
1380 if (CUR != '/') {
1381 /* TODO: A more meaningful error message. */
1382 ERROR5(NULL, NULL, NULL,
1383 "Unexpected token after '.' in '%s'.\n", ctxt->base);
1384 goto error;
1385 }
1386 /* "./" - "self::node()/" */
1387 NEXT;
1388 SKIP_BLANKS;
1389 if (CUR == '/') {
1390 if (IS_BLANK_CH(PEEKPREV(1))) {
1391 /*
1392 * Disallow "./ /"
1393 */
1394 ERROR5(NULL, NULL, NULL,
1395 "Unexpected '/' token in '%s'.\n", ctxt->base);
1396 goto error;
1397 }
1398 /* ".//" - "self:node()/descendant-or-self::node()/" */
1399 PUSH(XML_OP_ANCESTOR, NULL, NULL);
1400 NEXT;
1401 SKIP_BLANKS;
1402 }
1403 if (CUR == 0)
1404 goto error_unfinished;
1405 }
1406 /*
1407 * Process steps.
1408 */
1409 do {
1410 xmlCompileStepPattern(ctxt);
1411 if (ctxt->error != 0)
1412 goto error;
1413 SKIP_BLANKS;
1414 if (CUR != '/')
1415 break;
1416 PUSH(XML_OP_PARENT, NULL, NULL);
1417 NEXT;
1418 SKIP_BLANKS;
1419 if (CUR == '/') {
1420 /*
1421 * Disallow subsequent '//'.
1422 */
1423 ERROR5(NULL, NULL, NULL,
1424 "Unexpected subsequent '//' in '%s'.\n",
1425 ctxt->base);
1426 goto error;
1427 }
1428 if (CUR == 0)
1429 goto error_unfinished;
1430
1431 } while (CUR != 0);
1432
1433 if (CUR != 0) {
1434 ERROR5(NULL, NULL, NULL,
1435 "Failed to compile expression '%s'.\n", ctxt->base);
1436 ctxt->error = 1;
1437 }
1438 return;
1439 error:
1440 ctxt->error = 1;
1441 return;
1442
1443 error_unfinished:
1444 ctxt->error = 1;
1445 ERROR5(NULL, NULL, NULL,
1446 "Unfinished expression '%s'.\n", ctxt->base);
1447 return;
1448 }
1449
1450 /************************************************************************
1451 * *
1452 * The streaming code *
1453 * *
1454 ************************************************************************/
1455
1456 #ifdef DEBUG_STREAMING
1457 static void
xmlDebugStreamComp(xmlStreamCompPtr stream)1458 xmlDebugStreamComp(xmlStreamCompPtr stream) {
1459 int i;
1460
1461 if (stream == NULL) {
1462 printf("Stream: NULL\n");
1463 return;
1464 }
1465 printf("Stream: %d steps\n", stream->nbStep);
1466 for (i = 0;i < stream->nbStep;i++) {
1467 if (stream->steps[i].ns != NULL) {
1468 printf("{%s}", stream->steps[i].ns);
1469 }
1470 if (stream->steps[i].name == NULL) {
1471 printf("* ");
1472 } else {
1473 printf("%s ", stream->steps[i].name);
1474 }
1475 if (stream->steps[i].flags & XML_STREAM_STEP_ROOT)
1476 printf("root ");
1477 if (stream->steps[i].flags & XML_STREAM_STEP_DESC)
1478 printf("// ");
1479 if (stream->steps[i].flags & XML_STREAM_STEP_FINAL)
1480 printf("final ");
1481 printf("\n");
1482 }
1483 }
1484 static void
xmlDebugStreamCtxt(xmlStreamCtxtPtr ctxt,int match)1485 xmlDebugStreamCtxt(xmlStreamCtxtPtr ctxt, int match) {
1486 int i;
1487
1488 if (ctxt == NULL) {
1489 printf("Stream: NULL\n");
1490 return;
1491 }
1492 printf("Stream: level %d, %d states: ", ctxt->level, ctxt->nbState);
1493 if (match)
1494 printf("matches\n");
1495 else
1496 printf("\n");
1497 for (i = 0;i < ctxt->nbState;i++) {
1498 if (ctxt->states[2 * i] < 0)
1499 printf(" %d: free\n", i);
1500 else {
1501 printf(" %d: step %d, level %d", i, ctxt->states[2 * i],
1502 ctxt->states[(2 * i) + 1]);
1503 if (ctxt->comp->steps[ctxt->states[2 * i]].flags &
1504 XML_STREAM_STEP_DESC)
1505 printf(" //\n");
1506 else
1507 printf("\n");
1508 }
1509 }
1510 }
1511 #endif
1512 /**
1513 * xmlNewStreamComp:
1514 * @size: the number of expected steps
1515 *
1516 * build a new compiled pattern for streaming
1517 *
1518 * Returns the new structure or NULL in case of error.
1519 */
1520 static xmlStreamCompPtr
xmlNewStreamComp(int size)1521 xmlNewStreamComp(int size) {
1522 xmlStreamCompPtr cur;
1523
1524 if (size < 4)
1525 size = 4;
1526
1527 cur = (xmlStreamCompPtr) xmlMalloc(sizeof(xmlStreamComp));
1528 if (cur == NULL) {
1529 ERROR(NULL, NULL, NULL,
1530 "xmlNewStreamComp: malloc failed\n");
1531 return(NULL);
1532 }
1533 memset(cur, 0, sizeof(xmlStreamComp));
1534 cur->steps = (xmlStreamStepPtr) xmlMalloc(size * sizeof(xmlStreamStep));
1535 if (cur->steps == NULL) {
1536 xmlFree(cur);
1537 ERROR(NULL, NULL, NULL,
1538 "xmlNewStreamComp: malloc failed\n");
1539 return(NULL);
1540 }
1541 cur->nbStep = 0;
1542 cur->maxStep = size;
1543 return(cur);
1544 }
1545
1546 /**
1547 * xmlFreeStreamComp:
1548 * @comp: the compiled pattern for streaming
1549 *
1550 * Free the compiled pattern for streaming
1551 */
1552 static void
xmlFreeStreamComp(xmlStreamCompPtr comp)1553 xmlFreeStreamComp(xmlStreamCompPtr comp) {
1554 if (comp != NULL) {
1555 if (comp->steps != NULL)
1556 xmlFree(comp->steps);
1557 if (comp->dict != NULL)
1558 xmlDictFree(comp->dict);
1559 xmlFree(comp);
1560 }
1561 }
1562
1563 /**
1564 * xmlStreamCompAddStep:
1565 * @comp: the compiled pattern for streaming
1566 * @name: the first string, the name, or NULL for *
1567 * @ns: the second step, the namespace name
1568 * @flags: the flags for that step
1569 *
1570 * Add a new step to the compiled pattern
1571 *
1572 * Returns -1 in case of error or the step index if successful
1573 */
1574 static int
xmlStreamCompAddStep(xmlStreamCompPtr comp,const xmlChar * name,const xmlChar * ns,int nodeType,int flags)1575 xmlStreamCompAddStep(xmlStreamCompPtr comp, const xmlChar *name,
1576 const xmlChar *ns, int nodeType, int flags) {
1577 xmlStreamStepPtr cur;
1578
1579 if (comp->nbStep >= comp->maxStep) {
1580 cur = (xmlStreamStepPtr) xmlRealloc(comp->steps,
1581 comp->maxStep * 2 * sizeof(xmlStreamStep));
1582 if (cur == NULL) {
1583 ERROR(NULL, NULL, NULL,
1584 "xmlNewStreamComp: malloc failed\n");
1585 return(-1);
1586 }
1587 comp->steps = cur;
1588 comp->maxStep *= 2;
1589 }
1590 cur = &comp->steps[comp->nbStep++];
1591 cur->flags = flags;
1592 cur->name = name;
1593 cur->ns = ns;
1594 cur->nodeType = nodeType;
1595 return(comp->nbStep - 1);
1596 }
1597
1598 /**
1599 * xmlStreamCompile:
1600 * @comp: the precompiled pattern
1601 *
1602 * Tries to stream compile a pattern
1603 *
1604 * Returns -1 in case of failure and 0 in case of success.
1605 */
1606 static int
xmlStreamCompile(xmlPatternPtr comp)1607 xmlStreamCompile(xmlPatternPtr comp) {
1608 xmlStreamCompPtr stream;
1609 int i, s = 0, root = 0, flags = 0, prevs = -1;
1610 xmlStepOp step;
1611
1612 if ((comp == NULL) || (comp->steps == NULL))
1613 return(-1);
1614 /*
1615 * special case for .
1616 */
1617 if ((comp->nbStep == 1) &&
1618 (comp->steps[0].op == XML_OP_ELEM) &&
1619 (comp->steps[0].value == NULL) &&
1620 (comp->steps[0].value2 == NULL)) {
1621 stream = xmlNewStreamComp(0);
1622 if (stream == NULL)
1623 return(-1);
1624 /* Note that the stream will have no steps in this case. */
1625 stream->flags |= XML_STREAM_FINAL_IS_ANY_NODE;
1626 comp->stream = stream;
1627 return(0);
1628 }
1629
1630 stream = xmlNewStreamComp((comp->nbStep / 2) + 1);
1631 if (stream == NULL)
1632 return(-1);
1633 if (comp->dict != NULL) {
1634 stream->dict = comp->dict;
1635 xmlDictReference(stream->dict);
1636 }
1637
1638 i = 0;
1639 if (comp->flags & PAT_FROM_ROOT)
1640 stream->flags |= XML_STREAM_FROM_ROOT;
1641
1642 for (;i < comp->nbStep;i++) {
1643 step = comp->steps[i];
1644 switch (step.op) {
1645 case XML_OP_END:
1646 break;
1647 case XML_OP_ROOT:
1648 if (i != 0)
1649 goto error;
1650 root = 1;
1651 break;
1652 case XML_OP_NS:
1653 s = xmlStreamCompAddStep(stream, NULL, step.value,
1654 XML_ELEMENT_NODE, flags);
1655 if (s < 0)
1656 goto error;
1657 prevs = s;
1658 flags = 0;
1659 break;
1660 case XML_OP_ATTR:
1661 flags |= XML_STREAM_STEP_ATTR;
1662 prevs = -1;
1663 s = xmlStreamCompAddStep(stream,
1664 step.value, step.value2, XML_ATTRIBUTE_NODE, flags);
1665 flags = 0;
1666 if (s < 0)
1667 goto error;
1668 break;
1669 case XML_OP_ELEM:
1670 if ((step.value == NULL) && (step.value2 == NULL)) {
1671 /*
1672 * We have a "." or "self::node()" here.
1673 * Eliminate redundant self::node() tests like in "/./."
1674 * or "//./"
1675 * The only case we won't eliminate is "//.", i.e. if
1676 * self::node() is the last node test and we had
1677 * continuation somewhere beforehand.
1678 */
1679 if ((comp->nbStep == i + 1) &&
1680 (flags & XML_STREAM_STEP_DESC)) {
1681 /*
1682 * Mark the special case where the expression resolves
1683 * to any type of node.
1684 */
1685 if (comp->nbStep == i + 1) {
1686 stream->flags |= XML_STREAM_FINAL_IS_ANY_NODE;
1687 }
1688 flags |= XML_STREAM_STEP_NODE;
1689 s = xmlStreamCompAddStep(stream, NULL, NULL,
1690 XML_STREAM_ANY_NODE, flags);
1691 if (s < 0)
1692 goto error;
1693 flags = 0;
1694 /*
1695 * If there was a previous step, mark it to be added to
1696 * the result node-set; this is needed since only
1697 * the last step will be marked as "final" and only
1698 * "final" nodes are added to the resulting set.
1699 */
1700 if (prevs != -1) {
1701 stream->steps[prevs].flags |= XML_STREAM_STEP_IN_SET;
1702 prevs = -1;
1703 }
1704 break;
1705
1706 } else {
1707 /* Just skip this one. */
1708 continue;
1709 }
1710 }
1711 /* An element node. */
1712 s = xmlStreamCompAddStep(stream, step.value, step.value2,
1713 XML_ELEMENT_NODE, flags);
1714 if (s < 0)
1715 goto error;
1716 prevs = s;
1717 flags = 0;
1718 break;
1719 case XML_OP_CHILD:
1720 /* An element node child. */
1721 s = xmlStreamCompAddStep(stream, step.value, step.value2,
1722 XML_ELEMENT_NODE, flags);
1723 if (s < 0)
1724 goto error;
1725 prevs = s;
1726 flags = 0;
1727 break;
1728 case XML_OP_ALL:
1729 s = xmlStreamCompAddStep(stream, NULL, NULL,
1730 XML_ELEMENT_NODE, flags);
1731 if (s < 0)
1732 goto error;
1733 prevs = s;
1734 flags = 0;
1735 break;
1736 case XML_OP_PARENT:
1737 break;
1738 case XML_OP_ANCESTOR:
1739 /* Skip redundant continuations. */
1740 if (flags & XML_STREAM_STEP_DESC)
1741 break;
1742 flags |= XML_STREAM_STEP_DESC;
1743 /*
1744 * Mark the expression as having "//".
1745 */
1746 if ((stream->flags & XML_STREAM_DESC) == 0)
1747 stream->flags |= XML_STREAM_DESC;
1748 break;
1749 }
1750 }
1751 if ((! root) && (comp->flags & XML_PATTERN_NOTPATTERN) == 0) {
1752 /*
1753 * If this should behave like a real pattern, we will mark
1754 * the first step as having "//", to be reentrant on every
1755 * tree level.
1756 */
1757 if ((stream->flags & XML_STREAM_DESC) == 0)
1758 stream->flags |= XML_STREAM_DESC;
1759
1760 if (stream->nbStep > 0) {
1761 if ((stream->steps[0].flags & XML_STREAM_STEP_DESC) == 0)
1762 stream->steps[0].flags |= XML_STREAM_STEP_DESC;
1763 }
1764 }
1765 if (stream->nbStep <= s)
1766 goto error;
1767 stream->steps[s].flags |= XML_STREAM_STEP_FINAL;
1768 if (root)
1769 stream->steps[0].flags |= XML_STREAM_STEP_ROOT;
1770 #ifdef DEBUG_STREAMING
1771 xmlDebugStreamComp(stream);
1772 #endif
1773 comp->stream = stream;
1774 return(0);
1775 error:
1776 xmlFreeStreamComp(stream);
1777 return(0);
1778 }
1779
1780 /**
1781 * xmlNewStreamCtxt:
1782 * @size: the number of expected states
1783 *
1784 * build a new stream context
1785 *
1786 * Returns the new structure or NULL in case of error.
1787 */
1788 static xmlStreamCtxtPtr
xmlNewStreamCtxt(xmlStreamCompPtr stream)1789 xmlNewStreamCtxt(xmlStreamCompPtr stream) {
1790 xmlStreamCtxtPtr cur;
1791
1792 cur = (xmlStreamCtxtPtr) xmlMalloc(sizeof(xmlStreamCtxt));
1793 if (cur == NULL) {
1794 ERROR(NULL, NULL, NULL,
1795 "xmlNewStreamCtxt: malloc failed\n");
1796 return(NULL);
1797 }
1798 memset(cur, 0, sizeof(xmlStreamCtxt));
1799 cur->states = (int *) xmlMalloc(4 * 2 * sizeof(int));
1800 if (cur->states == NULL) {
1801 xmlFree(cur);
1802 ERROR(NULL, NULL, NULL,
1803 "xmlNewStreamCtxt: malloc failed\n");
1804 return(NULL);
1805 }
1806 cur->nbState = 0;
1807 cur->maxState = 4;
1808 cur->level = 0;
1809 cur->comp = stream;
1810 cur->blockLevel = -1;
1811 return(cur);
1812 }
1813
1814 /**
1815 * xmlFreeStreamCtxt:
1816 * @stream: the stream context
1817 *
1818 * Free the stream context
1819 */
1820 void
xmlFreeStreamCtxt(xmlStreamCtxtPtr stream)1821 xmlFreeStreamCtxt(xmlStreamCtxtPtr stream) {
1822 xmlStreamCtxtPtr next;
1823
1824 while (stream != NULL) {
1825 next = stream->next;
1826 if (stream->states != NULL)
1827 xmlFree(stream->states);
1828 xmlFree(stream);
1829 stream = next;
1830 }
1831 }
1832
1833 /**
1834 * xmlStreamCtxtAddState:
1835 * @comp: the stream context
1836 * @idx: the step index for that streaming state
1837 *
1838 * Add a new state to the stream context
1839 *
1840 * Returns -1 in case of error or the state index if successful
1841 */
1842 static int
xmlStreamCtxtAddState(xmlStreamCtxtPtr comp,int idx,int level)1843 xmlStreamCtxtAddState(xmlStreamCtxtPtr comp, int idx, int level) {
1844 int i;
1845 for (i = 0;i < comp->nbState;i++) {
1846 if (comp->states[2 * i] < 0) {
1847 comp->states[2 * i] = idx;
1848 comp->states[2 * i + 1] = level;
1849 return(i);
1850 }
1851 }
1852 if (comp->nbState >= comp->maxState) {
1853 int *cur;
1854
1855 cur = (int *) xmlRealloc(comp->states,
1856 comp->maxState * 4 * sizeof(int));
1857 if (cur == NULL) {
1858 ERROR(NULL, NULL, NULL,
1859 "xmlNewStreamCtxt: malloc failed\n");
1860 return(-1);
1861 }
1862 comp->states = cur;
1863 comp->maxState *= 2;
1864 }
1865 comp->states[2 * comp->nbState] = idx;
1866 comp->states[2 * comp->nbState++ + 1] = level;
1867 return(comp->nbState - 1);
1868 }
1869
1870 /**
1871 * xmlStreamPushInternal:
1872 * @stream: the stream context
1873 * @name: the current name
1874 * @ns: the namespace name
1875 * @nodeType: the type of the node
1876 *
1877 * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
1878 * indicated a dictionary, then strings for name and ns will be expected
1879 * to come from the dictionary.
1880 * Both @name and @ns being NULL means the / i.e. the root of the document.
1881 * This can also act as a reset.
1882 *
1883 * Returns: -1 in case of error, 1 if the current state in the stream is a
1884 * match and 0 otherwise.
1885 */
1886 static int
xmlStreamPushInternal(xmlStreamCtxtPtr stream,const xmlChar * name,const xmlChar * ns,int nodeType)1887 xmlStreamPushInternal(xmlStreamCtxtPtr stream,
1888 const xmlChar *name, const xmlChar *ns,
1889 int nodeType) {
1890 int ret = 0, err = 0, final = 0, tmp, i, m, match, stepNr, desc;
1891 xmlStreamCompPtr comp;
1892 xmlStreamStep step;
1893 #ifdef DEBUG_STREAMING
1894 xmlStreamCtxtPtr orig = stream;
1895 #endif
1896
1897 if ((stream == NULL) || (stream->nbState < 0))
1898 return(-1);
1899
1900 while (stream != NULL) {
1901 comp = stream->comp;
1902
1903 if ((nodeType == XML_ELEMENT_NODE) &&
1904 (name == NULL) && (ns == NULL)) {
1905 /* We have a document node here (or a reset). */
1906 stream->nbState = 0;
1907 stream->level = 0;
1908 stream->blockLevel = -1;
1909 if (comp->flags & XML_STREAM_FROM_ROOT) {
1910 if (comp->nbStep == 0) {
1911 /* TODO: We have a "/." here? */
1912 ret = 1;
1913 } else {
1914 if ((comp->nbStep == 1) &&
1915 (comp->steps[0].nodeType == XML_STREAM_ANY_NODE) &&
1916 (comp->steps[0].flags & XML_STREAM_STEP_DESC))
1917 {
1918 /*
1919 * In the case of "//." the document node will match
1920 * as well.
1921 */
1922 ret = 1;
1923 } else if (comp->steps[0].flags & XML_STREAM_STEP_ROOT) {
1924 /* TODO: Do we need this ? */
1925 tmp = xmlStreamCtxtAddState(stream, 0, 0);
1926 if (tmp < 0)
1927 err++;
1928 }
1929 }
1930 }
1931 stream = stream->next;
1932 continue; /* while */
1933 }
1934
1935 /*
1936 * Fast check for ".".
1937 */
1938 if (comp->nbStep == 0) {
1939 /*
1940 * / and . are handled at the XPath node set creation
1941 * level by checking min depth
1942 */
1943 if (stream->flags & XML_PATTERN_XPATH) {
1944 stream = stream->next;
1945 continue; /* while */
1946 }
1947 /*
1948 * For non-pattern like evaluation like XML Schema IDCs
1949 * or traditional XPath expressions, this will match if
1950 * we are at the first level only, otherwise on every level.
1951 */
1952 if ((nodeType != XML_ATTRIBUTE_NODE) &&
1953 (((stream->flags & XML_PATTERN_NOTPATTERN) == 0) ||
1954 (stream->level == 0))) {
1955 ret = 1;
1956 }
1957 stream->level++;
1958 goto stream_next;
1959 }
1960 if (stream->blockLevel != -1) {
1961 /*
1962 * Skip blocked expressions.
1963 */
1964 stream->level++;
1965 goto stream_next;
1966 }
1967
1968 if ((nodeType != XML_ELEMENT_NODE) &&
1969 (nodeType != XML_ATTRIBUTE_NODE) &&
1970 ((comp->flags & XML_STREAM_FINAL_IS_ANY_NODE) == 0)) {
1971 /*
1972 * No need to process nodes of other types if we don't
1973 * resolve to those types.
1974 * TODO: Do we need to block the context here?
1975 */
1976 stream->level++;
1977 goto stream_next;
1978 }
1979
1980 /*
1981 * Check evolution of existing states
1982 */
1983 i = 0;
1984 m = stream->nbState;
1985 while (i < m) {
1986 if ((comp->flags & XML_STREAM_DESC) == 0) {
1987 /*
1988 * If there is no "//", then only the last
1989 * added state is of interest.
1990 */
1991 stepNr = stream->states[2 * (stream->nbState -1)];
1992 /*
1993 * TODO: Security check, should not happen, remove it.
1994 */
1995 if (stream->states[(2 * (stream->nbState -1)) + 1] <
1996 stream->level) {
1997 return (-1);
1998 }
1999 desc = 0;
2000 /* loop-stopper */
2001 i = m;
2002 } else {
2003 /*
2004 * If there are "//", then we need to process every "//"
2005 * occuring in the states, plus any other state for this
2006 * level.
2007 */
2008 stepNr = stream->states[2 * i];
2009
2010 /* TODO: should not happen anymore: dead states */
2011 if (stepNr < 0)
2012 goto next_state;
2013
2014 tmp = stream->states[(2 * i) + 1];
2015
2016 /* skip new states just added */
2017 if (tmp > stream->level)
2018 goto next_state;
2019
2020 /* skip states at ancestor levels, except if "//" */
2021 desc = comp->steps[stepNr].flags & XML_STREAM_STEP_DESC;
2022 if ((tmp < stream->level) && (!desc))
2023 goto next_state;
2024 }
2025 /*
2026 * Check for correct node-type.
2027 */
2028 step = comp->steps[stepNr];
2029 if (step.nodeType != nodeType) {
2030 if (step.nodeType == XML_ATTRIBUTE_NODE) {
2031 /*
2032 * Block this expression for deeper evaluation.
2033 */
2034 if ((comp->flags & XML_STREAM_DESC) == 0)
2035 stream->blockLevel = stream->level +1;
2036 goto next_state;
2037 } else if (step.nodeType != XML_STREAM_ANY_NODE)
2038 goto next_state;
2039 }
2040 /*
2041 * Compare local/namespace-name.
2042 */
2043 match = 0;
2044 if (step.nodeType == XML_STREAM_ANY_NODE) {
2045 match = 1;
2046 } else if (step.name == NULL) {
2047 if (step.ns == NULL) {
2048 /*
2049 * This lets through all elements/attributes.
2050 */
2051 match = 1;
2052 } else if (ns != NULL)
2053 match = xmlStrEqual(step.ns, ns);
2054 } else if (((step.ns != NULL) == (ns != NULL)) &&
2055 (name != NULL) &&
2056 (step.name[0] == name[0]) &&
2057 xmlStrEqual(step.name, name) &&
2058 ((step.ns == ns) || xmlStrEqual(step.ns, ns)))
2059 {
2060 match = 1;
2061 }
2062 #if 0
2063 /*
2064 * TODO: Pointer comparison won't work, since not guaranteed that the given
2065 * values are in the same dict; especially if it's the namespace name,
2066 * normally coming from ns->href. We need a namespace dict mechanism !
2067 */
2068 } else if (comp->dict) {
2069 if (step.name == NULL) {
2070 if (step.ns == NULL)
2071 match = 1;
2072 else
2073 match = (step.ns == ns);
2074 } else {
2075 match = ((step.name == name) && (step.ns == ns));
2076 }
2077 #endif /* if 0 ------------------------------------------------------- */
2078 if (match) {
2079 final = step.flags & XML_STREAM_STEP_FINAL;
2080 if (desc) {
2081 if (final) {
2082 ret = 1;
2083 } else {
2084 /* descending match create a new state */
2085 xmlStreamCtxtAddState(stream, stepNr + 1,
2086 stream->level + 1);
2087 }
2088 } else {
2089 if (final) {
2090 ret = 1;
2091 } else {
2092 xmlStreamCtxtAddState(stream, stepNr + 1,
2093 stream->level + 1);
2094 }
2095 }
2096 if ((ret != 1) && (step.flags & XML_STREAM_STEP_IN_SET)) {
2097 /*
2098 * Check if we have a special case like "foo/bar//.", where
2099 * "foo" is selected as well.
2100 */
2101 ret = 1;
2102 }
2103 }
2104 if (((comp->flags & XML_STREAM_DESC) == 0) &&
2105 ((! match) || final)) {
2106 /*
2107 * Mark this expression as blocked for any evaluation at
2108 * deeper levels. Note that this includes "/foo"
2109 * expressions if the *pattern* behaviour is used.
2110 */
2111 stream->blockLevel = stream->level +1;
2112 }
2113 next_state:
2114 i++;
2115 }
2116
2117 stream->level++;
2118
2119 /*
2120 * Re/enter the expression.
2121 * Don't reenter if it's an absolute expression like "/foo",
2122 * except "//foo".
2123 */
2124 step = comp->steps[0];
2125 if (step.flags & XML_STREAM_STEP_ROOT)
2126 goto stream_next;
2127
2128 desc = step.flags & XML_STREAM_STEP_DESC;
2129 if (stream->flags & XML_PATTERN_NOTPATTERN) {
2130 /*
2131 * Re/enter the expression if it is a "descendant" one,
2132 * or if we are at the 1st level of evaluation.
2133 */
2134
2135 if (stream->level == 1) {
2136 if (XML_STREAM_XS_IDC(stream)) {
2137 /*
2138 * XS-IDC: The missing "self::node()" will always
2139 * match the first given node.
2140 */
2141 goto stream_next;
2142 } else
2143 goto compare;
2144 }
2145 /*
2146 * A "//" is always reentrant.
2147 */
2148 if (desc)
2149 goto compare;
2150
2151 /*
2152 * XS-IDC: Process the 2nd level, since the missing
2153 * "self::node()" is responsible for the 2nd level being
2154 * the real start level.
2155 */
2156 if ((stream->level == 2) && XML_STREAM_XS_IDC(stream))
2157 goto compare;
2158
2159 goto stream_next;
2160 }
2161
2162 compare:
2163 /*
2164 * Check expected node-type.
2165 */
2166 if (step.nodeType != nodeType) {
2167 if (nodeType == XML_ATTRIBUTE_NODE)
2168 goto stream_next;
2169 else if (step.nodeType != XML_STREAM_ANY_NODE)
2170 goto stream_next;
2171 }
2172 /*
2173 * Compare local/namespace-name.
2174 */
2175 match = 0;
2176 if (step.nodeType == XML_STREAM_ANY_NODE) {
2177 match = 1;
2178 } else if (step.name == NULL) {
2179 if (step.ns == NULL) {
2180 /*
2181 * This lets through all elements/attributes.
2182 */
2183 match = 1;
2184 } else if (ns != NULL)
2185 match = xmlStrEqual(step.ns, ns);
2186 } else if (((step.ns != NULL) == (ns != NULL)) &&
2187 (name != NULL) &&
2188 (step.name[0] == name[0]) &&
2189 xmlStrEqual(step.name, name) &&
2190 ((step.ns == ns) || xmlStrEqual(step.ns, ns)))
2191 {
2192 match = 1;
2193 }
2194 final = step.flags & XML_STREAM_STEP_FINAL;
2195 if (match) {
2196 if (final)
2197 ret = 1;
2198 else
2199 xmlStreamCtxtAddState(stream, 1, stream->level);
2200 if ((ret != 1) && (step.flags & XML_STREAM_STEP_IN_SET)) {
2201 /*
2202 * Check if we have a special case like "foo//.", where
2203 * "foo" is selected as well.
2204 */
2205 ret = 1;
2206 }
2207 }
2208 if (((comp->flags & XML_STREAM_DESC) == 0) &&
2209 ((! match) || final)) {
2210 /*
2211 * Mark this expression as blocked for any evaluation at
2212 * deeper levels.
2213 */
2214 stream->blockLevel = stream->level;
2215 }
2216
2217 stream_next:
2218 stream = stream->next;
2219 } /* while stream != NULL */
2220
2221 if (err > 0)
2222 ret = -1;
2223 #ifdef DEBUG_STREAMING
2224 xmlDebugStreamCtxt(orig, ret);
2225 #endif
2226 return(ret);
2227 }
2228
2229 /**
2230 * xmlStreamPush:
2231 * @stream: the stream context
2232 * @name: the current name
2233 * @ns: the namespace name
2234 *
2235 * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
2236 * indicated a dictionary, then strings for name and ns will be expected
2237 * to come from the dictionary.
2238 * Both @name and @ns being NULL means the / i.e. the root of the document.
2239 * This can also act as a reset.
2240 * Otherwise the function will act as if it has been given an element-node.
2241 *
2242 * Returns: -1 in case of error, 1 if the current state in the stream is a
2243 * match and 0 otherwise.
2244 */
2245 int
xmlStreamPush(xmlStreamCtxtPtr stream,const xmlChar * name,const xmlChar * ns)2246 xmlStreamPush(xmlStreamCtxtPtr stream,
2247 const xmlChar *name, const xmlChar *ns) {
2248 return (xmlStreamPushInternal(stream, name, ns, (int) XML_ELEMENT_NODE));
2249 }
2250
2251 /**
2252 * xmlStreamPushNode:
2253 * @stream: the stream context
2254 * @name: the current name
2255 * @ns: the namespace name
2256 * @nodeType: the type of the node being pushed
2257 *
2258 * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
2259 * indicated a dictionary, then strings for name and ns will be expected
2260 * to come from the dictionary.
2261 * Both @name and @ns being NULL means the / i.e. the root of the document.
2262 * This can also act as a reset.
2263 * Different from xmlStreamPush() this function can be fed with nodes of type:
2264 * element-, attribute-, text-, cdata-section-, comment- and
2265 * processing-instruction-node.
2266 *
2267 * Returns: -1 in case of error, 1 if the current state in the stream is a
2268 * match and 0 otherwise.
2269 */
2270 int
xmlStreamPushNode(xmlStreamCtxtPtr stream,const xmlChar * name,const xmlChar * ns,int nodeType)2271 xmlStreamPushNode(xmlStreamCtxtPtr stream,
2272 const xmlChar *name, const xmlChar *ns,
2273 int nodeType)
2274 {
2275 return (xmlStreamPushInternal(stream, name, ns,
2276 nodeType));
2277 }
2278
2279 /**
2280 * xmlStreamPushAttr:
2281 * @stream: the stream context
2282 * @name: the current name
2283 * @ns: the namespace name
2284 *
2285 * Push new attribute data onto the stream. NOTE: if the call xmlPatterncompile()
2286 * indicated a dictionary, then strings for name and ns will be expected
2287 * to come from the dictionary.
2288 * Both @name and @ns being NULL means the / i.e. the root of the document.
2289 * This can also act as a reset.
2290 * Otherwise the function will act as if it has been given an attribute-node.
2291 *
2292 * Returns: -1 in case of error, 1 if the current state in the stream is a
2293 * match and 0 otherwise.
2294 */
2295 int
xmlStreamPushAttr(xmlStreamCtxtPtr stream,const xmlChar * name,const xmlChar * ns)2296 xmlStreamPushAttr(xmlStreamCtxtPtr stream,
2297 const xmlChar *name, const xmlChar *ns) {
2298 return (xmlStreamPushInternal(stream, name, ns, (int) XML_ATTRIBUTE_NODE));
2299 }
2300
2301 /**
2302 * xmlStreamPop:
2303 * @stream: the stream context
2304 *
2305 * push one level from the stream.
2306 *
2307 * Returns: -1 in case of error, 0 otherwise.
2308 */
2309 int
xmlStreamPop(xmlStreamCtxtPtr stream)2310 xmlStreamPop(xmlStreamCtxtPtr stream) {
2311 int i, lev;
2312
2313 if (stream == NULL)
2314 return(-1);
2315 while (stream != NULL) {
2316 /*
2317 * Reset block-level.
2318 */
2319 if (stream->blockLevel == stream->level)
2320 stream->blockLevel = -1;
2321
2322 /*
2323 * stream->level can be zero when XML_FINAL_IS_ANY_NODE is set
2324 * (see the thread at
2325 * http://mail.gnome.org/archives/xslt/2008-July/msg00027.html)
2326 */
2327 if (stream->level)
2328 stream->level--;
2329 /*
2330 * Check evolution of existing states
2331 */
2332 for (i = stream->nbState -1; i >= 0; i--) {
2333 /* discard obsoleted states */
2334 lev = stream->states[(2 * i) + 1];
2335 if (lev > stream->level)
2336 stream->nbState--;
2337 if (lev <= stream->level)
2338 break;
2339 }
2340 stream = stream->next;
2341 }
2342 return(0);
2343 }
2344
2345 /**
2346 * xmlStreamWantsAnyNode:
2347 * @streamCtxt: the stream context
2348 *
2349 * Query if the streaming pattern additionally needs to be fed with
2350 * text-, cdata-section-, comment- and processing-instruction-nodes.
2351 * If the result is 0 then only element-nodes and attribute-nodes
2352 * need to be pushed.
2353 *
2354 * Returns: 1 in case of need of nodes of the above described types,
2355 * 0 otherwise. -1 on API errors.
2356 */
2357 int
xmlStreamWantsAnyNode(xmlStreamCtxtPtr streamCtxt)2358 xmlStreamWantsAnyNode(xmlStreamCtxtPtr streamCtxt)
2359 {
2360 if (streamCtxt == NULL)
2361 return(-1);
2362 while (streamCtxt != NULL) {
2363 if (streamCtxt->comp->flags & XML_STREAM_FINAL_IS_ANY_NODE)
2364 return(1);
2365 streamCtxt = streamCtxt->next;
2366 }
2367 return(0);
2368 }
2369
2370 /************************************************************************
2371 * *
2372 * The public interfaces *
2373 * *
2374 ************************************************************************/
2375
2376 /**
2377 * xmlPatterncompile:
2378 * @pattern: the pattern to compile
2379 * @dict: an optional dictionary for interned strings
2380 * @flags: compilation flags, see xmlPatternFlags
2381 * @namespaces: the prefix definitions, array of [URI, prefix] or NULL
2382 *
2383 * Compile a pattern.
2384 *
2385 * Returns the compiled form of the pattern or NULL in case of error
2386 */
2387 xmlPatternPtr
xmlPatterncompile(const xmlChar * pattern,xmlDict * dict,int flags,const xmlChar ** namespaces)2388 xmlPatterncompile(const xmlChar *pattern, xmlDict *dict, int flags,
2389 const xmlChar **namespaces) {
2390 xmlPatternPtr ret = NULL, cur;
2391 xmlPatParserContextPtr ctxt = NULL;
2392 const xmlChar *or, *start;
2393 xmlChar *tmp = NULL;
2394 int type = 0;
2395 int streamable = 1;
2396
2397 if (pattern == NULL)
2398 return(NULL);
2399
2400 start = pattern;
2401 or = start;
2402 while (*or != 0) {
2403 tmp = NULL;
2404 while ((*or != 0) && (*or != '|')) or++;
2405 if (*or == 0)
2406 ctxt = xmlNewPatParserContext(start, dict, namespaces);
2407 else {
2408 tmp = xmlStrndup(start, or - start);
2409 if (tmp != NULL) {
2410 ctxt = xmlNewPatParserContext(tmp, dict, namespaces);
2411 }
2412 or++;
2413 }
2414 if (ctxt == NULL) goto error;
2415 cur = xmlNewPattern();
2416 if (cur == NULL) goto error;
2417 /*
2418 * Assign string dict.
2419 */
2420 if (dict) {
2421 cur->dict = dict;
2422 xmlDictReference(dict);
2423 }
2424 if (ret == NULL)
2425 ret = cur;
2426 else {
2427 cur->next = ret->next;
2428 ret->next = cur;
2429 }
2430 cur->flags = flags;
2431 ctxt->comp = cur;
2432
2433 if (XML_STREAM_XS_IDC(cur))
2434 xmlCompileIDCXPathPath(ctxt);
2435 else
2436 xmlCompilePathPattern(ctxt);
2437 if (ctxt->error != 0)
2438 goto error;
2439 xmlFreePatParserContext(ctxt);
2440 ctxt = NULL;
2441
2442
2443 if (streamable) {
2444 if (type == 0) {
2445 type = cur->flags & (PAT_FROM_ROOT | PAT_FROM_CUR);
2446 } else if (type == PAT_FROM_ROOT) {
2447 if (cur->flags & PAT_FROM_CUR)
2448 streamable = 0;
2449 } else if (type == PAT_FROM_CUR) {
2450 if (cur->flags & PAT_FROM_ROOT)
2451 streamable = 0;
2452 }
2453 }
2454 if (streamable)
2455 xmlStreamCompile(cur);
2456 if (xmlReversePattern(cur) < 0)
2457 goto error;
2458 if (tmp != NULL) {
2459 xmlFree(tmp);
2460 tmp = NULL;
2461 }
2462 start = or;
2463 }
2464 if (streamable == 0) {
2465 cur = ret;
2466 while (cur != NULL) {
2467 if (cur->stream != NULL) {
2468 xmlFreeStreamComp(cur->stream);
2469 cur->stream = NULL;
2470 }
2471 cur = cur->next;
2472 }
2473 }
2474
2475 return(ret);
2476 error:
2477 if (ctxt != NULL) xmlFreePatParserContext(ctxt);
2478 if (ret != NULL) xmlFreePattern(ret);
2479 if (tmp != NULL) xmlFree(tmp);
2480 return(NULL);
2481 }
2482
2483 /**
2484 * xmlPatternMatch:
2485 * @comp: the precompiled pattern
2486 * @node: a node
2487 *
2488 * Test whether the node matches the pattern
2489 *
2490 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
2491 */
2492 int
xmlPatternMatch(xmlPatternPtr comp,xmlNodePtr node)2493 xmlPatternMatch(xmlPatternPtr comp, xmlNodePtr node)
2494 {
2495 int ret = 0;
2496
2497 if ((comp == NULL) || (node == NULL))
2498 return(-1);
2499
2500 while (comp != NULL) {
2501 ret = xmlPatMatch(comp, node);
2502 if (ret != 0)
2503 return(ret);
2504 comp = comp->next;
2505 }
2506 return(ret);
2507 }
2508
2509 /**
2510 * xmlPatternGetStreamCtxt:
2511 * @comp: the precompiled pattern
2512 *
2513 * Get a streaming context for that pattern
2514 * Use xmlFreeStreamCtxt to free the context.
2515 *
2516 * Returns a pointer to the context or NULL in case of failure
2517 */
2518 xmlStreamCtxtPtr
xmlPatternGetStreamCtxt(xmlPatternPtr comp)2519 xmlPatternGetStreamCtxt(xmlPatternPtr comp)
2520 {
2521 xmlStreamCtxtPtr ret = NULL, cur;
2522
2523 if ((comp == NULL) || (comp->stream == NULL))
2524 return(NULL);
2525
2526 while (comp != NULL) {
2527 if (comp->stream == NULL)
2528 goto failed;
2529 cur = xmlNewStreamCtxt(comp->stream);
2530 if (cur == NULL)
2531 goto failed;
2532 if (ret == NULL)
2533 ret = cur;
2534 else {
2535 cur->next = ret->next;
2536 ret->next = cur;
2537 }
2538 cur->flags = comp->flags;
2539 comp = comp->next;
2540 }
2541 return(ret);
2542 failed:
2543 xmlFreeStreamCtxt(ret);
2544 return(NULL);
2545 }
2546
2547 /**
2548 * xmlPatternStreamable:
2549 * @comp: the precompiled pattern
2550 *
2551 * Check if the pattern is streamable i.e. xmlPatternGetStreamCtxt()
2552 * should work.
2553 *
2554 * Returns 1 if streamable, 0 if not and -1 in case of error.
2555 */
2556 int
xmlPatternStreamable(xmlPatternPtr comp)2557 xmlPatternStreamable(xmlPatternPtr comp) {
2558 if (comp == NULL)
2559 return(-1);
2560 while (comp != NULL) {
2561 if (comp->stream == NULL)
2562 return(0);
2563 comp = comp->next;
2564 }
2565 return(1);
2566 }
2567
2568 /**
2569 * xmlPatternMaxDepth:
2570 * @comp: the precompiled pattern
2571 *
2572 * Check the maximum depth reachable by a pattern
2573 *
2574 * Returns -2 if no limit (using //), otherwise the depth,
2575 * and -1 in case of error
2576 */
2577 int
xmlPatternMaxDepth(xmlPatternPtr comp)2578 xmlPatternMaxDepth(xmlPatternPtr comp) {
2579 int ret = 0, i;
2580 if (comp == NULL)
2581 return(-1);
2582 while (comp != NULL) {
2583 if (comp->stream == NULL)
2584 return(-1);
2585 for (i = 0;i < comp->stream->nbStep;i++)
2586 if (comp->stream->steps[i].flags & XML_STREAM_STEP_DESC)
2587 return(-2);
2588 if (comp->stream->nbStep > ret)
2589 ret = comp->stream->nbStep;
2590 comp = comp->next;
2591 }
2592 return(ret);
2593 }
2594
2595 /**
2596 * xmlPatternMinDepth:
2597 * @comp: the precompiled pattern
2598 *
2599 * Check the minimum depth reachable by a pattern, 0 mean the / or . are
2600 * part of the set.
2601 *
2602 * Returns -1 in case of error otherwise the depth,
2603 *
2604 */
2605 int
xmlPatternMinDepth(xmlPatternPtr comp)2606 xmlPatternMinDepth(xmlPatternPtr comp) {
2607 int ret = 12345678;
2608 if (comp == NULL)
2609 return(-1);
2610 while (comp != NULL) {
2611 if (comp->stream == NULL)
2612 return(-1);
2613 if (comp->stream->nbStep < ret)
2614 ret = comp->stream->nbStep;
2615 if (ret == 0)
2616 return(0);
2617 comp = comp->next;
2618 }
2619 return(ret);
2620 }
2621
2622 /**
2623 * xmlPatternFromRoot:
2624 * @comp: the precompiled pattern
2625 *
2626 * Check if the pattern must be looked at from the root.
2627 *
2628 * Returns 1 if true, 0 if false and -1 in case of error
2629 */
2630 int
xmlPatternFromRoot(xmlPatternPtr comp)2631 xmlPatternFromRoot(xmlPatternPtr comp) {
2632 if (comp == NULL)
2633 return(-1);
2634 while (comp != NULL) {
2635 if (comp->stream == NULL)
2636 return(-1);
2637 if (comp->flags & PAT_FROM_ROOT)
2638 return(1);
2639 comp = comp->next;
2640 }
2641 return(0);
2642
2643 }
2644
2645 #define bottom_pattern
2646 #include "elfgcchack.h"
2647 #endif /* LIBXML_PATTERN_ENABLED */
2648