2 * pattern.c: Implementation of selectors for nodes
5 * http://www.w3.org/TR/2001/REC-xmlschema-1-20010502/
7 * http://www.w3.org/TR/1999/REC-xml-19991116
9 * See Copyright for the status of this software.
16 * - compilation flags to check for specific syntaxes
17 * using flags of xmlPatterncompile()
18 * - making clear how pattern starting with / or . need to be handled,
19 * currently push(NULL, NULL) means a reset of the streaming context
20 * and indicating we are on / (the document node), probably need
21 * something similar for .
22 * - get rid of the "compile" starting with lowercase
23 * - DONE (2006-05-16): get rid of the Strdup/Strndup in case of dictionary
30 #include <libxml/xmlmemory.h>
31 #include <libxml/tree.h>
32 #include <libxml/hash.h>
33 #include <libxml/dict.h>
34 #include <libxml/xmlerror.h>
35 #include <libxml/parserInternals.h>
36 #include <libxml/pattern.h>
38 #ifdef LIBXML_PATTERN_ENABLED
40 /* #define DEBUG_STREAMING */
45 #define ERROR(a, b, c, d)
46 #define ERROR5(a, b, c, d, e)
48 #define XML_STREAM_STEP_DESC 1
49 #define XML_STREAM_STEP_FINAL 2
50 #define XML_STREAM_STEP_ROOT 4
51 #define XML_STREAM_STEP_ATTR 8
52 #define XML_STREAM_STEP_NODE 16
53 #define XML_STREAM_STEP_IN_SET 32
56 * NOTE: Those private flags (XML_STREAM_xxx) are used
57 * in _xmlStreamCtxt->flag. They extend the public
58 * xmlPatternFlags, so be careful not to interfere with the
59 * reserved values for xmlPatternFlags.
61 #define XML_STREAM_FINAL_IS_ANY_NODE 1<<14
62 #define XML_STREAM_FROM_ROOT 1<<15
63 #define XML_STREAM_DESC 1<<16
66 * XML_STREAM_ANY_NODE is used for comparison against
67 * xmlElementType enums, to indicate a node of any type.
69 #define XML_STREAM_ANY_NODE 100
71 #define XML_PATTERN_NOTPATTERN (XML_PATTERN_XPATH | \
75 #define XML_STREAM_XS_IDC(c) ((c)->flags & \
76 (XML_PATTERN_XSSEL | XML_PATTERN_XSFIELD))
78 #define XML_STREAM_XS_IDC_SEL(c) ((c)->flags & XML_PATTERN_XSSEL)
80 #define XML_STREAM_XS_IDC_FIELD(c) ((c)->flags & XML_PATTERN_XSFIELD)
82 #define XML_PAT_COPY_NSNAME(c, r, nsname) \
83 if ((c)->comp->dict) \
84 r = (xmlChar *) xmlDictLookup((c)->comp->dict, BAD_CAST nsname, -1); \
85 else r = xmlStrdup(BAD_CAST nsname);
87 #define XML_PAT_FREE_STRING(c, r) if ((c)->comp->dict == NULL) xmlFree(r);
89 typedef struct _xmlStreamStep xmlStreamStep
;
90 typedef xmlStreamStep
*xmlStreamStepPtr
;
91 struct _xmlStreamStep
{
92 int flags
; /* properties of that step */
93 const xmlChar
*name
; /* first string value if NULL accept all */
94 const xmlChar
*ns
; /* second string value */
95 int nodeType
; /* type of node */
98 typedef struct _xmlStreamComp xmlStreamComp
;
99 typedef xmlStreamComp
*xmlStreamCompPtr
;
100 struct _xmlStreamComp
{
101 xmlDict
*dict
; /* the dictionary if any */
102 int nbStep
; /* number of steps in the automata */
103 int maxStep
; /* allocated number of steps */
104 xmlStreamStepPtr steps
; /* the array of steps */
108 struct _xmlStreamCtxt
{
109 struct _xmlStreamCtxt
*next
;/* link to next sub pattern if | */
110 xmlStreamCompPtr comp
; /* the compiled stream */
111 int nbState
; /* number of states in the automata */
112 int maxState
; /* allocated number of states */
113 int level
; /* how deep are we ? */
114 int *states
; /* the array of step indexes */
115 int flags
; /* validation options */
119 static void xmlFreeStreamComp(xmlStreamCompPtr comp
);
138 typedef struct _xmlStepState xmlStepState
;
139 typedef xmlStepState
*xmlStepStatePtr
;
140 struct _xmlStepState
{
145 typedef struct _xmlStepStates xmlStepStates
;
146 typedef xmlStepStates
*xmlStepStatesPtr
;
147 struct _xmlStepStates
{
150 xmlStepStatePtr states
;
153 typedef struct _xmlStepOp xmlStepOp
;
154 typedef xmlStepOp
*xmlStepOpPtr
;
157 const xmlChar
*value
;
158 const xmlChar
*value2
; /* The namespace name */
161 #define PAT_FROM_ROOT (1<<8)
162 #define PAT_FROM_CUR (1<<9)
165 void *data
; /* the associated template */
166 xmlDictPtr dict
; /* the optional dictionary */
167 struct _xmlPattern
*next
; /* next pattern if | is used */
168 const xmlChar
*pattern
; /* the pattern */
169 int flags
; /* flags */
172 xmlStepOpPtr steps
; /* ops for computation */
173 xmlStreamCompPtr stream
; /* the streaming data if any */
176 typedef struct _xmlPatParserContext xmlPatParserContext
;
177 typedef xmlPatParserContext
*xmlPatParserContextPtr
;
178 struct _xmlPatParserContext
{
179 const xmlChar
*cur
; /* the current char being parsed */
180 const xmlChar
*base
; /* the full expression */
181 int error
; /* error code */
182 xmlDictPtr dict
; /* the dictionary if any */
183 xmlPatternPtr comp
; /* the result */
184 xmlNodePtr elem
; /* the current node if any */
185 const xmlChar
**namespaces
; /* the namespaces definitions */
186 int nb_namespaces
; /* the number of namespaces */
189 /************************************************************************
193 ************************************************************************/
198 * Create a new XSLT Pattern
200 * Returns the newly allocated xmlPatternPtr or NULL in case of error
203 xmlNewPattern(void) {
206 cur
= (xmlPatternPtr
) xmlMalloc(sizeof(xmlPattern
));
208 ERROR(NULL
, NULL
, NULL
,
209 "xmlNewPattern : malloc failed\n");
212 memset(cur
, 0, sizeof(xmlPattern
));
214 cur
->steps
= (xmlStepOpPtr
) xmlMalloc(cur
->maxStep
* sizeof(xmlStepOp
));
215 if (cur
->steps
== NULL
) {
217 ERROR(NULL
, NULL
, NULL
,
218 "xmlNewPattern : malloc failed\n");
226 * @comp: an XSLT comp
228 * Free up the memory allocated by @comp
231 xmlFreePattern(xmlPatternPtr comp
) {
232 xmlFreePatternList(comp
);
236 xmlFreePatternInternal(xmlPatternPtr comp
) {
242 if (comp
->stream
!= NULL
)
243 xmlFreeStreamComp(comp
->stream
);
244 if (comp
->pattern
!= NULL
)
245 xmlFree((xmlChar
*)comp
->pattern
);
246 if (comp
->steps
!= NULL
) {
247 if (comp
->dict
== NULL
) {
248 for (i
= 0;i
< comp
->nbStep
;i
++) {
249 op
= &comp
->steps
[i
];
250 if (op
->value
!= NULL
)
251 xmlFree((xmlChar
*) op
->value
);
252 if (op
->value2
!= NULL
)
253 xmlFree((xmlChar
*) op
->value2
);
256 xmlFree(comp
->steps
);
258 if (comp
->dict
!= NULL
)
259 xmlDictFree(comp
->dict
);
261 memset(comp
, -1, sizeof(xmlPattern
));
266 * xmlFreePatternList:
267 * @comp: an XSLT comp list
269 * Free up the memory allocated by all the elements of @comp
272 xmlFreePatternList(xmlPatternPtr comp
) {
275 while (comp
!= NULL
) {
279 xmlFreePatternInternal(cur
);
284 * xmlNewPatParserContext:
285 * @pattern: the pattern context
286 * @dict: the inherited dictionary or NULL
287 * @namespaces: the prefix definitions, array of [URI, prefix] terminated
288 * with [NULL, NULL] or NULL if no namespace is used
290 * Create a new XML pattern parser context
292 * Returns the newly allocated xmlPatParserContextPtr or NULL in case of error
294 static xmlPatParserContextPtr
295 xmlNewPatParserContext(const xmlChar
*pattern
, xmlDictPtr dict
,
296 const xmlChar
**namespaces
) {
297 xmlPatParserContextPtr cur
;
302 cur
= (xmlPatParserContextPtr
) xmlMalloc(sizeof(xmlPatParserContext
));
304 ERROR(NULL
, NULL
, NULL
,
305 "xmlNewPatParserContext : malloc failed\n");
308 memset(cur
, 0, sizeof(xmlPatParserContext
));
312 if (namespaces
!= NULL
) {
314 for (i
= 0;namespaces
[2 * i
] != NULL
;i
++)
316 cur
->nb_namespaces
= i
;
318 cur
->nb_namespaces
= 0;
320 cur
->namespaces
= namespaces
;
325 * xmlFreePatParserContext:
326 * @ctxt: an XSLT parser context
328 * Free up the memory allocated by @ctxt
331 xmlFreePatParserContext(xmlPatParserContextPtr ctxt
) {
334 memset(ctxt
, -1, sizeof(xmlPatParserContext
));
340 * @comp: the compiled match expression
342 * @value: the first value
343 * @value2: the second value
345 * Add a step to an XSLT Compiled Match
347 * Returns -1 in case of failure, 0 otherwise.
350 xmlPatternAdd(xmlPatParserContextPtr ctxt ATTRIBUTE_UNUSED
,
352 xmlPatOp op
, xmlChar
* value
, xmlChar
* value2
)
354 if (comp
->nbStep
>= comp
->maxStep
) {
356 temp
= (xmlStepOpPtr
) xmlRealloc(comp
->steps
, comp
->maxStep
* 2 *
359 ERROR(ctxt
, NULL
, NULL
,
360 "xmlPatternAdd: realloc failed\n");
366 comp
->steps
[comp
->nbStep
].op
= op
;
367 comp
->steps
[comp
->nbStep
].value
= value
;
368 comp
->steps
[comp
->nbStep
].value2
= value2
;
375 * xsltSwapTopPattern:
376 * @comp: the compiled match expression
378 * reverse the two top steps.
381 xsltSwapTopPattern(xmlPatternPtr comp
) {
383 int j
= comp
->nbStep
- 1;
386 register const xmlChar
*tmp
;
387 register xmlPatOp op
;
389 tmp
= comp
->steps
[i
].value
;
390 comp
->steps
[i
].value
= comp
->steps
[j
].value
;
391 comp
->steps
[j
].value
= tmp
;
392 tmp
= comp
->steps
[i
].value2
;
393 comp
->steps
[i
].value2
= comp
->steps
[j
].value2
;
394 comp
->steps
[j
].value2
= tmp
;
395 op
= comp
->steps
[i
].op
;
396 comp
->steps
[i
].op
= comp
->steps
[j
].op
;
397 comp
->steps
[j
].op
= op
;
404 * @comp: the compiled match expression
406 * reverse all the stack of expressions
408 * returns 0 in case of success and -1 in case of error.
411 xmlReversePattern(xmlPatternPtr comp
) {
415 * remove the leading // for //a or .//a
417 if ((comp
->nbStep
> 0) && (comp
->steps
[0].op
== XML_OP_ANCESTOR
)) {
418 for (i
= 0, j
= 1;j
< comp
->nbStep
;i
++,j
++) {
419 comp
->steps
[i
].value
= comp
->steps
[j
].value
;
420 comp
->steps
[i
].value2
= comp
->steps
[j
].value2
;
421 comp
->steps
[i
].op
= comp
->steps
[j
].op
;
425 if (comp
->nbStep
>= comp
->maxStep
) {
427 temp
= (xmlStepOpPtr
) xmlRealloc(comp
->steps
, comp
->maxStep
* 2 *
430 ERROR(ctxt
, NULL
, NULL
,
431 "xmlReversePattern: realloc failed\n");
438 j
= comp
->nbStep
- 1;
440 register const xmlChar
*tmp
;
441 register xmlPatOp op
;
442 tmp
= comp
->steps
[i
].value
;
443 comp
->steps
[i
].value
= comp
->steps
[j
].value
;
444 comp
->steps
[j
].value
= tmp
;
445 tmp
= comp
->steps
[i
].value2
;
446 comp
->steps
[i
].value2
= comp
->steps
[j
].value2
;
447 comp
->steps
[j
].value2
= tmp
;
448 op
= comp
->steps
[i
].op
;
449 comp
->steps
[i
].op
= comp
->steps
[j
].op
;
450 comp
->steps
[j
].op
= op
;
454 comp
->steps
[comp
->nbStep
].value
= NULL
;
455 comp
->steps
[comp
->nbStep
].value2
= NULL
;
456 comp
->steps
[comp
->nbStep
++].op
= XML_OP_END
;
460 /************************************************************************
462 * The interpreter for the precompiled patterns *
464 ************************************************************************/
467 xmlPatPushState(xmlStepStates
*states
, int step
, xmlNodePtr node
) {
468 if ((states
->states
== NULL
) || (states
->maxstates
<= 0)) {
469 states
->maxstates
= 4;
470 states
->nbstates
= 0;
471 states
->states
= xmlMalloc(4 * sizeof(xmlStepState
));
473 else if (states
->maxstates
<= states
->nbstates
) {
476 tmp
= (xmlStepStatePtr
) xmlRealloc(states
->states
,
477 2 * states
->maxstates
* sizeof(xmlStepState
));
480 states
->states
= tmp
;
481 states
->maxstates
*= 2;
483 states
->states
[states
->nbstates
].step
= step
;
484 states
->states
[states
->nbstates
++].node
= node
;
486 fprintf(stderr
, "Push: %d, %s\n", step
, node
->name
);
493 * @comp: the precompiled pattern
496 * Test whether the node matches the pattern
498 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
501 xmlPatMatch(xmlPatternPtr comp
, xmlNodePtr node
) {
504 xmlStepStates states
= {0, 0, NULL
}; /* // may require backtrack */
506 if ((comp
== NULL
) || (node
== NULL
)) return(-1);
509 for (;i
< comp
->nbStep
;i
++) {
510 step
= &comp
->steps
[i
];
515 if (node
->type
== XML_NAMESPACE_DECL
)
518 if ((node
->type
== XML_DOCUMENT_NODE
) ||
519 #ifdef LIBXML_DOCB_ENABLED
520 (node
->type
== XML_DOCB_DOCUMENT_NODE
) ||
522 (node
->type
== XML_HTML_DOCUMENT_NODE
))
526 if (node
->type
!= XML_ELEMENT_NODE
)
528 if (step
->value
== NULL
)
530 if (step
->value
[0] != node
->name
[0])
532 if (!xmlStrEqual(step
->value
, node
->name
))
536 if (node
->ns
== NULL
) {
537 if (step
->value2
!= NULL
)
539 } else if (node
->ns
->href
!= NULL
) {
540 if (step
->value2
== NULL
)
542 if (!xmlStrEqual(step
->value2
, node
->ns
->href
))
549 if ((node
->type
!= XML_ELEMENT_NODE
) &&
550 (node
->type
!= XML_DOCUMENT_NODE
) &&
551 #ifdef LIBXML_DOCB_ENABLED
552 (node
->type
!= XML_DOCB_DOCUMENT_NODE
) &&
554 (node
->type
!= XML_HTML_DOCUMENT_NODE
))
557 lst
= node
->children
;
559 if (step
->value
!= NULL
) {
560 while (lst
!= NULL
) {
561 if ((lst
->type
== XML_ELEMENT_NODE
) &&
562 (step
->value
[0] == lst
->name
[0]) &&
563 (xmlStrEqual(step
->value
, lst
->name
)))
573 if (node
->type
!= XML_ATTRIBUTE_NODE
)
575 if (step
->value
!= NULL
) {
576 if (step
->value
[0] != node
->name
[0])
578 if (!xmlStrEqual(step
->value
, node
->name
))
582 if (node
->ns
== NULL
) {
583 if (step
->value2
!= NULL
)
585 } else if (step
->value2
!= NULL
) {
586 if (!xmlStrEqual(step
->value2
, node
->ns
->href
))
591 if ((node
->type
== XML_DOCUMENT_NODE
) ||
592 (node
->type
== XML_HTML_DOCUMENT_NODE
) ||
593 #ifdef LIBXML_DOCB_ENABLED
594 (node
->type
== XML_DOCB_DOCUMENT_NODE
) ||
596 (node
->type
== XML_NAMESPACE_DECL
))
601 if (step
->value
== NULL
)
603 if (step
->value
[0] != node
->name
[0])
605 if (!xmlStrEqual(step
->value
, node
->name
))
608 if (node
->ns
== NULL
) {
609 if (step
->value2
!= NULL
)
611 } else if (node
->ns
->href
!= NULL
) {
612 if (step
->value2
== NULL
)
614 if (!xmlStrEqual(step
->value2
, node
->ns
->href
))
618 case XML_OP_ANCESTOR
:
619 /* TODO: implement coalescing of ANCESTOR/NODE ops */
620 if (step
->value
== NULL
) {
622 step
= &comp
->steps
[i
];
623 if (step
->op
== XML_OP_ROOT
)
625 if (step
->op
!= XML_OP_ELEM
)
627 if (step
->value
== NULL
)
632 if ((node
->type
== XML_DOCUMENT_NODE
) ||
633 (node
->type
== XML_HTML_DOCUMENT_NODE
) ||
634 #ifdef LIBXML_DOCB_ENABLED
635 (node
->type
== XML_DOCB_DOCUMENT_NODE
) ||
637 (node
->type
== XML_NAMESPACE_DECL
))
640 while (node
!= NULL
) {
641 if ((node
->type
== XML_ELEMENT_NODE
) &&
642 (step
->value
[0] == node
->name
[0]) &&
643 (xmlStrEqual(step
->value
, node
->name
))) {
645 if (node
->ns
== NULL
) {
646 if (step
->value2
== NULL
)
648 } else if (node
->ns
->href
!= NULL
) {
649 if ((step
->value2
!= NULL
) &&
650 (xmlStrEqual(step
->value2
, node
->ns
->href
)))
659 * prepare a potential rollback from here
660 * for ancestors of that node.
662 if (step
->op
== XML_OP_ANCESTOR
)
663 xmlPatPushState(&states
, i
, node
);
665 xmlPatPushState(&states
, i
- 1, node
);
668 if (node
->type
!= XML_ELEMENT_NODE
)
670 if (node
->ns
== NULL
) {
671 if (step
->value
!= NULL
)
673 } else if (node
->ns
->href
!= NULL
) {
674 if (step
->value
== NULL
)
676 if (!xmlStrEqual(step
->value
, node
->ns
->href
))
681 if (node
->type
!= XML_ELEMENT_NODE
)
687 if (states
.states
!= NULL
) {
688 /* Free the rollback states */
689 xmlFree(states
.states
);
693 /* got an error try to rollback */
694 if (states
.states
== NULL
)
696 if (states
.nbstates
<= 0) {
697 xmlFree(states
.states
);
701 i
= states
.states
[states
.nbstates
].step
;
702 node
= states
.states
[states
.nbstates
].node
;
704 fprintf(stderr
, "Pop: %d, %s\n", i
, node
->name
);
709 /************************************************************************
711 * Dedicated parser for templates *
713 ************************************************************************/
716 xmlGenericError(xmlGenericErrorContext, \
717 "Unimplemented block at %s:%d\n", \
719 #define CUR (*ctxt->cur)
720 #define SKIP(val) ctxt->cur += (val)
721 #define NXT(val) ctxt->cur[(val)]
722 #define PEEKPREV(val) ctxt->cur[-(val)]
723 #define CUR_PTR ctxt->cur
725 #define SKIP_BLANKS \
726 while (IS_BLANK_CH(CUR)) NEXT
728 #define CURRENT (*ctxt->cur)
729 #define NEXT ((*ctxt->cur) ? ctxt->cur++: ctxt->cur)
732 #define PUSH(op, val, val2) \
733 if (xmlPatternAdd(ctxt, ctxt->comp, (op), (val), (val2))) goto error;
735 #define XSLT_ERROR(X) \
736 { xsltError(ctxt, __FILE__, __LINE__, X); \
737 ctxt->error = (X); return; }
739 #define XSLT_ERROR0(X) \
740 { xsltError(ctxt, __FILE__, __LINE__, X); \
741 ctxt->error = (X); return(0); }
746 * @ctxt: the XPath Parser context
748 * Parse an XPath Literal:
750 * [29] Literal ::= '"' [^"]* '"'
753 * Returns the Literal parsed or NULL
757 xmlPatScanLiteral(xmlPatParserContextPtr ctxt
) {
758 const xmlChar
*q
, *cur
;
766 val
= xmlStringCurrentChar(NULL
, cur
, &len
);
767 while ((IS_CHAR(val
)) && (val
!= '"')) {
769 val
= xmlStringCurrentChar(NULL
, cur
, &len
);
776 ret
= (xmlChar
*) xmlDictLookup(ctxt
->dict
, q
, cur
- q
);
778 ret
= xmlStrndup(q
, cur
- q
);
782 } else if (CUR
== '\'') {
785 val
= xmlStringCurrentChar(NULL
, cur
, &len
);
786 while ((IS_CHAR(val
)) && (val
!= '\'')) {
788 val
= xmlStringCurrentChar(NULL
, cur
, &len
);
795 ret
= (xmlChar
*) xmlDictLookup(ctxt
->dict
, q
, cur
- q
);
797 ret
= xmlStrndup(q
, cur
- q
);
802 /* XP_ERROR(XPATH_START_LITERAL_ERROR); */
812 * @ctxt: the XPath Parser context
814 * [4] NameChar ::= Letter | Digit | '.' | '-' | '_' |
815 * CombiningChar | Extender
817 * [5] Name ::= (Letter | '_' | ':') (NameChar)*
819 * [6] Names ::= Name (S Name)*
821 * Returns the Name parsed or NULL
825 xmlPatScanName(xmlPatParserContextPtr ctxt
) {
826 const xmlChar
*q
, *cur
;
833 val
= xmlStringCurrentChar(NULL
, cur
, &len
);
834 if (!IS_LETTER(val
) && (val
!= '_') && (val
!= ':'))
837 while ((IS_LETTER(val
)) || (IS_DIGIT(val
)) ||
838 (val
== '.') || (val
== '-') ||
840 (IS_COMBINING(val
)) ||
841 (IS_EXTENDER(val
))) {
843 val
= xmlStringCurrentChar(NULL
, cur
, &len
);
846 ret
= (xmlChar
*) xmlDictLookup(ctxt
->dict
, q
, cur
- q
);
848 ret
= xmlStrndup(q
, cur
- q
);
855 * @ctxt: the XPath Parser context
857 * Parses a non qualified name
859 * Returns the Name parsed or NULL
863 xmlPatScanNCName(xmlPatParserContextPtr ctxt
) {
864 const xmlChar
*q
, *cur
;
871 val
= xmlStringCurrentChar(NULL
, cur
, &len
);
872 if (!IS_LETTER(val
) && (val
!= '_'))
875 while ((IS_LETTER(val
)) || (IS_DIGIT(val
)) ||
876 (val
== '.') || (val
== '-') ||
878 (IS_COMBINING(val
)) ||
879 (IS_EXTENDER(val
))) {
881 val
= xmlStringCurrentChar(NULL
, cur
, &len
);
884 ret
= (xmlChar
*) xmlDictLookup(ctxt
->dict
, q
, cur
- q
);
886 ret
= xmlStrndup(q
, cur
- q
);
894 * @ctxt: the XPath Parser context
895 * @prefix: the place to store the prefix
897 * Parse a qualified name
899 * Returns the Name parsed or NULL
903 xmlPatScanQName(xmlPatParserContextPtr ctxt
, xmlChar
**prefix
) {
907 ret
= xmlPatScanNCName(ctxt
);
911 ret
= xmlPatScanNCName(ctxt
);
918 * xmlCompileAttributeTest:
919 * @ctxt: the compilation context
921 * Compile an attribute test.
924 xmlCompileAttributeTest(xmlPatParserContextPtr ctxt
) {
925 xmlChar
*token
= NULL
;
926 xmlChar
*name
= NULL
;
930 name
= xmlPatScanNCName(ctxt
);
933 PUSH(XML_OP_ATTR
, NULL
, NULL
);
936 ERROR(NULL
, NULL
, NULL
,
937 "xmlCompileAttributeTest : Name expected\n");
944 xmlChar
*prefix
= name
;
948 if (IS_BLANK_CH(CUR
)) {
949 ERROR5(NULL
, NULL
, NULL
, "Invalid QName.\n", NULL
);
950 XML_PAT_FREE_STRING(ctxt
, prefix
);
955 * This is a namespace match
957 token
= xmlPatScanName(ctxt
);
958 if ((prefix
[0] == 'x') &&
959 (prefix
[1] == 'm') &&
960 (prefix
[2] == 'l') &&
963 XML_PAT_COPY_NSNAME(ctxt
, URL
, XML_XML_NAMESPACE
);
965 for (i
= 0;i
< ctxt
->nb_namespaces
;i
++) {
966 if (xmlStrEqual(ctxt
->namespaces
[2 * i
+ 1], prefix
)) {
967 XML_PAT_COPY_NSNAME(ctxt
, URL
, ctxt
->namespaces
[2 * i
])
971 if (i
>= ctxt
->nb_namespaces
) {
972 ERROR5(NULL
, NULL
, NULL
,
973 "xmlCompileAttributeTest : no namespace bound to prefix %s\n",
975 XML_PAT_FREE_STRING(ctxt
, prefix
);
980 XML_PAT_FREE_STRING(ctxt
, prefix
);
984 PUSH(XML_OP_ATTR
, NULL
, URL
);
986 ERROR(NULL
, NULL
, NULL
,
987 "xmlCompileAttributeTest : Name expected\n");
992 PUSH(XML_OP_ATTR
, token
, URL
);
995 PUSH(XML_OP_ATTR
, name
, NULL
);
1000 XML_PAT_FREE_STRING(ctxt
, URL
)
1002 XML_PAT_FREE_STRING(ctxt
, token
);
1006 * xmlCompileStepPattern:
1007 * @ctxt: the compilation context
1009 * Compile the Step Pattern and generates a precompiled
1010 * form suitable for fast matching.
1012 * [3] Step ::= '.' | NameTest
1013 * [4] NameTest ::= QName | '*' | NCName ':' '*'
1017 xmlCompileStepPattern(xmlPatParserContextPtr ctxt
) {
1018 xmlChar
*token
= NULL
;
1019 xmlChar
*name
= NULL
;
1020 xmlChar
*URL
= NULL
;
1029 PUSH(XML_OP_ELEM
, NULL
, NULL
);
1036 if (XML_STREAM_XS_IDC_SEL(ctxt
->comp
)) {
1037 ERROR5(NULL
, NULL
, NULL
,
1038 "Unexpected attribute axis in '%s'.\n", ctxt
->base
);
1043 xmlCompileAttributeTest(ctxt
);
1044 if (ctxt
->error
!= 0)
1048 name
= xmlPatScanNCName(ctxt
);
1052 PUSH(XML_OP_ALL
, NULL
, NULL
);
1055 ERROR(NULL
, NULL
, NULL
,
1056 "xmlCompileStepPattern : Name expected\n");
1061 if (IS_BLANK_CH(CUR
)) {
1068 xmlChar
*prefix
= name
;
1071 if (hasBlanks
|| IS_BLANK_CH(CUR
)) {
1072 ERROR5(NULL
, NULL
, NULL
, "Invalid QName.\n", NULL
);
1077 * This is a namespace match
1079 token
= xmlPatScanName(ctxt
);
1080 if ((prefix
[0] == 'x') &&
1081 (prefix
[1] == 'm') &&
1082 (prefix
[2] == 'l') &&
1085 XML_PAT_COPY_NSNAME(ctxt
, URL
, XML_XML_NAMESPACE
)
1087 for (i
= 0;i
< ctxt
->nb_namespaces
;i
++) {
1088 if (xmlStrEqual(ctxt
->namespaces
[2 * i
+ 1], prefix
)) {
1089 XML_PAT_COPY_NSNAME(ctxt
, URL
, ctxt
->namespaces
[2 * i
])
1093 if (i
>= ctxt
->nb_namespaces
) {
1094 ERROR5(NULL
, NULL
, NULL
,
1095 "xmlCompileStepPattern : no namespace bound to prefix %s\n",
1101 XML_PAT_FREE_STRING(ctxt
, prefix
);
1103 if (token
== NULL
) {
1106 PUSH(XML_OP_NS
, URL
, NULL
);
1108 ERROR(NULL
, NULL
, NULL
,
1109 "xmlCompileStepPattern : Name expected\n");
1114 PUSH(XML_OP_ELEM
, token
, URL
);
1118 if (xmlStrEqual(name
, (const xmlChar
*) "child")) {
1119 XML_PAT_FREE_STRING(ctxt
, name
);
1120 name
= xmlPatScanName(ctxt
);
1124 PUSH(XML_OP_ALL
, NULL
, NULL
);
1127 ERROR(NULL
, NULL
, NULL
,
1128 "xmlCompileStepPattern : QName expected\n");
1134 xmlChar
*prefix
= name
;
1138 if (IS_BLANK_CH(CUR
)) {
1139 ERROR5(NULL
, NULL
, NULL
, "Invalid QName.\n", NULL
);
1144 * This is a namespace match
1146 token
= xmlPatScanName(ctxt
);
1147 if ((prefix
[0] == 'x') &&
1148 (prefix
[1] == 'm') &&
1149 (prefix
[2] == 'l') &&
1152 XML_PAT_COPY_NSNAME(ctxt
, URL
, XML_XML_NAMESPACE
)
1154 for (i
= 0;i
< ctxt
->nb_namespaces
;i
++) {
1155 if (xmlStrEqual(ctxt
->namespaces
[2 * i
+ 1], prefix
)) {
1156 XML_PAT_COPY_NSNAME(ctxt
, URL
, ctxt
->namespaces
[2 * i
])
1160 if (i
>= ctxt
->nb_namespaces
) {
1161 ERROR5(NULL
, NULL
, NULL
,
1162 "xmlCompileStepPattern : no namespace bound "
1163 "to prefix %s\n", prefix
);
1168 XML_PAT_FREE_STRING(ctxt
, prefix
);
1170 if (token
== NULL
) {
1173 PUSH(XML_OP_NS
, URL
, NULL
);
1175 ERROR(NULL
, NULL
, NULL
,
1176 "xmlCompileStepPattern : Name expected\n");
1181 PUSH(XML_OP_CHILD
, token
, URL
);
1184 PUSH(XML_OP_CHILD
, name
, NULL
);
1186 } else if (xmlStrEqual(name
, (const xmlChar
*) "attribute")) {
1187 XML_PAT_FREE_STRING(ctxt
, name
)
1189 if (XML_STREAM_XS_IDC_SEL(ctxt
->comp
)) {
1190 ERROR5(NULL
, NULL
, NULL
,
1191 "Unexpected attribute axis in '%s'.\n", ctxt
->base
);
1195 xmlCompileAttributeTest(ctxt
);
1196 if (ctxt
->error
!= 0)
1200 ERROR5(NULL
, NULL
, NULL
,
1201 "The 'element' or 'attribute' axis is expected.\n", NULL
);
1206 } else if (CUR
== '*') {
1212 PUSH(XML_OP_ALL
, token
, NULL
);
1214 PUSH(XML_OP_ELEM
, name
, NULL
);
1219 XML_PAT_FREE_STRING(ctxt
, URL
)
1221 XML_PAT_FREE_STRING(ctxt
, token
)
1223 XML_PAT_FREE_STRING(ctxt
, name
)
1227 * xmlCompilePathPattern:
1228 * @ctxt: the compilation context
1230 * Compile the Path Pattern and generates a precompiled
1231 * form suitable for fast matching.
1233 * [5] Path ::= ('.//')? ( Step '/' )* ( Step | '@' NameTest )
1236 xmlCompilePathPattern(xmlPatParserContextPtr ctxt
) {
1239 ctxt
->comp
->flags
|= PAT_FROM_ROOT
;
1240 } else if ((CUR
== '.') || (ctxt
->comp
->flags
& XML_PATTERN_NOTPATTERN
)) {
1241 ctxt
->comp
->flags
|= PAT_FROM_CUR
;
1244 if ((CUR
== '/') && (NXT(1) == '/')) {
1245 PUSH(XML_OP_ANCESTOR
, NULL
, NULL
);
1248 } else if ((CUR
== '.') && (NXT(1) == '/') && (NXT(2) == '/')) {
1249 PUSH(XML_OP_ANCESTOR
, NULL
, NULL
);
1253 /* Check for incompleteness. */
1256 ERROR5(NULL
, NULL
, NULL
,
1257 "Incomplete expression '%s'.\n", ctxt
->base
);
1264 xmlCompileAttributeTest(ctxt
);
1266 /* TODO: check for incompleteness */
1268 xmlCompileStepPattern(ctxt
);
1269 if (ctxt
->error
!= 0)
1274 PUSH(XML_OP_ROOT
, NULL
, NULL
);
1276 /* Check for incompleteness. */
1279 ERROR5(NULL
, NULL
, NULL
,
1280 "Incomplete expression '%s'.\n", ctxt
->base
);
1285 xmlCompileStepPattern(ctxt
);
1286 if (ctxt
->error
!= 0)
1289 while (CUR
== '/') {
1290 if (NXT(1) == '/') {
1291 PUSH(XML_OP_ANCESTOR
, NULL
, NULL
);
1295 xmlCompileStepPattern(ctxt
);
1296 if (ctxt
->error
!= 0)
1299 PUSH(XML_OP_PARENT
, NULL
, NULL
);
1303 ERROR5(NULL
, NULL
, NULL
,
1304 "Incomplete expression '%s'.\n", ctxt
->base
);
1308 xmlCompileStepPattern(ctxt
);
1309 if (ctxt
->error
!= 0)
1315 ERROR5(NULL
, NULL
, NULL
,
1316 "Failed to compile pattern %s\n", ctxt
->base
);
1324 * xmlCompileIDCXPathPath:
1325 * @ctxt: the compilation context
1327 * Compile the Path Pattern and generates a precompiled
1328 * form suitable for fast matching.
1330 * [5] Path ::= ('.//')? ( Step '/' )* ( Step | '@' NameTest )
1333 xmlCompileIDCXPathPath(xmlPatParserContextPtr ctxt
) {
1336 ERROR5(NULL
, NULL
, NULL
,
1337 "Unexpected selection of the document root in '%s'.\n",
1341 ctxt
->comp
->flags
|= PAT_FROM_CUR
;
1344 /* "." - "self::node()" */
1349 * Selection of the context node.
1351 PUSH(XML_OP_ELEM
, NULL
, NULL
);
1355 /* TODO: A more meaningful error message. */
1356 ERROR5(NULL
, NULL
, NULL
,
1357 "Unexpected token after '.' in '%s'.\n", ctxt
->base
);
1360 /* "./" - "self::node()/" */
1364 if (IS_BLANK_CH(PEEKPREV(1))) {
1368 ERROR5(NULL
, NULL
, NULL
,
1369 "Unexpected '/' token in '%s'.\n", ctxt
->base
);
1372 /* ".//" - "self:node()/descendant-or-self::node()/" */
1373 PUSH(XML_OP_ANCESTOR
, NULL
, NULL
);
1378 goto error_unfinished
;
1384 xmlCompileStepPattern(ctxt
);
1385 if (ctxt
->error
!= 0)
1390 PUSH(XML_OP_PARENT
, NULL
, NULL
);
1395 * Disallow subsequent '//'.
1397 ERROR5(NULL
, NULL
, NULL
,
1398 "Unexpected subsequent '//' in '%s'.\n",
1403 goto error_unfinished
;
1408 ERROR5(NULL
, NULL
, NULL
,
1409 "Failed to compile expression '%s'.\n", ctxt
->base
);
1419 ERROR5(NULL
, NULL
, NULL
,
1420 "Unfinished expression '%s'.\n", ctxt
->base
);
1424 /************************************************************************
1426 * The streaming code *
1428 ************************************************************************/
1430 #ifdef DEBUG_STREAMING
1432 xmlDebugStreamComp(xmlStreamCompPtr stream
) {
1435 if (stream
== NULL
) {
1436 printf("Stream: NULL\n");
1439 printf("Stream: %d steps\n", stream
->nbStep
);
1440 for (i
= 0;i
< stream
->nbStep
;i
++) {
1441 if (stream
->steps
[i
].ns
!= NULL
) {
1442 printf("{%s}", stream
->steps
[i
].ns
);
1444 if (stream
->steps
[i
].name
== NULL
) {
1447 printf("%s ", stream
->steps
[i
].name
);
1449 if (stream
->steps
[i
].flags
& XML_STREAM_STEP_ROOT
)
1451 if (stream
->steps
[i
].flags
& XML_STREAM_STEP_DESC
)
1453 if (stream
->steps
[i
].flags
& XML_STREAM_STEP_FINAL
)
1459 xmlDebugStreamCtxt(xmlStreamCtxtPtr ctxt
, int match
) {
1463 printf("Stream: NULL\n");
1466 printf("Stream: level %d, %d states: ", ctxt
->level
, ctxt
->nbState
);
1468 printf("matches\n");
1471 for (i
= 0;i
< ctxt
->nbState
;i
++) {
1472 if (ctxt
->states
[2 * i
] < 0)
1473 printf(" %d: free\n", i
);
1475 printf(" %d: step %d, level %d", i
, ctxt
->states
[2 * i
],
1476 ctxt
->states
[(2 * i
) + 1]);
1477 if (ctxt
->comp
->steps
[ctxt
->states
[2 * i
]].flags
&
1478 XML_STREAM_STEP_DESC
)
1488 * @size: the number of expected steps
1490 * build a new compiled pattern for streaming
1492 * Returns the new structure or NULL in case of error.
1494 static xmlStreamCompPtr
1495 xmlNewStreamComp(int size
) {
1496 xmlStreamCompPtr cur
;
1501 cur
= (xmlStreamCompPtr
) xmlMalloc(sizeof(xmlStreamComp
));
1503 ERROR(NULL
, NULL
, NULL
,
1504 "xmlNewStreamComp: malloc failed\n");
1507 memset(cur
, 0, sizeof(xmlStreamComp
));
1508 cur
->steps
= (xmlStreamStepPtr
) xmlMalloc(size
* sizeof(xmlStreamStep
));
1509 if (cur
->steps
== NULL
) {
1511 ERROR(NULL
, NULL
, NULL
,
1512 "xmlNewStreamComp: malloc failed\n");
1516 cur
->maxStep
= size
;
1521 * xmlFreeStreamComp:
1522 * @comp: the compiled pattern for streaming
1524 * Free the compiled pattern for streaming
1527 xmlFreeStreamComp(xmlStreamCompPtr comp
) {
1529 if (comp
->steps
!= NULL
)
1530 xmlFree(comp
->steps
);
1531 if (comp
->dict
!= NULL
)
1532 xmlDictFree(comp
->dict
);
1538 * xmlStreamCompAddStep:
1539 * @comp: the compiled pattern for streaming
1540 * @name: the first string, the name, or NULL for *
1541 * @ns: the second step, the namespace name
1542 * @flags: the flags for that step
1544 * Add a new step to the compiled pattern
1546 * Returns -1 in case of error or the step index if successful
1549 xmlStreamCompAddStep(xmlStreamCompPtr comp
, const xmlChar
*name
,
1550 const xmlChar
*ns
, int nodeType
, int flags
) {
1551 xmlStreamStepPtr cur
;
1553 if (comp
->nbStep
>= comp
->maxStep
) {
1554 cur
= (xmlStreamStepPtr
) xmlRealloc(comp
->steps
,
1555 comp
->maxStep
* 2 * sizeof(xmlStreamStep
));
1557 ERROR(NULL
, NULL
, NULL
,
1558 "xmlNewStreamComp: malloc failed\n");
1564 cur
= &comp
->steps
[comp
->nbStep
++];
1568 cur
->nodeType
= nodeType
;
1569 return(comp
->nbStep
- 1);
1574 * @comp: the precompiled pattern
1576 * Tries to stream compile a pattern
1578 * Returns -1 in case of failure and 0 in case of success.
1581 xmlStreamCompile(xmlPatternPtr comp
) {
1582 xmlStreamCompPtr stream
;
1583 int i
, s
= 0, root
= 0, flags
= 0, prevs
= -1;
1586 if ((comp
== NULL
) || (comp
->steps
== NULL
))
1589 * special case for .
1591 if ((comp
->nbStep
== 1) &&
1592 (comp
->steps
[0].op
== XML_OP_ELEM
) &&
1593 (comp
->steps
[0].value
== NULL
) &&
1594 (comp
->steps
[0].value2
== NULL
)) {
1595 stream
= xmlNewStreamComp(0);
1598 /* Note that the stream will have no steps in this case. */
1599 stream
->flags
|= XML_STREAM_FINAL_IS_ANY_NODE
;
1600 comp
->stream
= stream
;
1604 stream
= xmlNewStreamComp((comp
->nbStep
/ 2) + 1);
1607 if (comp
->dict
!= NULL
) {
1608 stream
->dict
= comp
->dict
;
1609 xmlDictReference(stream
->dict
);
1613 if (comp
->flags
& PAT_FROM_ROOT
)
1614 stream
->flags
|= XML_STREAM_FROM_ROOT
;
1616 for (;i
< comp
->nbStep
;i
++) {
1617 step
= comp
->steps
[i
];
1627 s
= xmlStreamCompAddStep(stream
, NULL
, step
.value
,
1628 XML_ELEMENT_NODE
, flags
);
1635 flags
|= XML_STREAM_STEP_ATTR
;
1637 s
= xmlStreamCompAddStep(stream
,
1638 step
.value
, step
.value2
, XML_ATTRIBUTE_NODE
, flags
);
1644 if ((step
.value
== NULL
) && (step
.value2
== NULL
)) {
1646 * We have a "." or "self::node()" here.
1647 * Eliminate redundant self::node() tests like in "/./."
1649 * The only case we won't eliminate is "//.", i.e. if
1650 * self::node() is the last node test and we had
1651 * continuation somewhere beforehand.
1653 if ((comp
->nbStep
== i
+ 1) &&
1654 (flags
& XML_STREAM_STEP_DESC
)) {
1656 * Mark the special case where the expression resolves
1657 * to any type of node.
1659 if (comp
->nbStep
== i
+ 1) {
1660 stream
->flags
|= XML_STREAM_FINAL_IS_ANY_NODE
;
1662 flags
|= XML_STREAM_STEP_NODE
;
1663 s
= xmlStreamCompAddStep(stream
, NULL
, NULL
,
1664 XML_STREAM_ANY_NODE
, flags
);
1669 * If there was a previous step, mark it to be added to
1670 * the result node-set; this is needed since only
1671 * the last step will be marked as "final" and only
1672 * "final" nodes are added to the resulting set.
1675 stream
->steps
[prevs
].flags
|= XML_STREAM_STEP_IN_SET
;
1681 /* Just skip this one. */
1685 /* An element node. */
1686 s
= xmlStreamCompAddStep(stream
, step
.value
, step
.value2
,
1687 XML_ELEMENT_NODE
, flags
);
1694 /* An element node child. */
1695 s
= xmlStreamCompAddStep(stream
, step
.value
, step
.value2
,
1696 XML_ELEMENT_NODE
, flags
);
1703 s
= xmlStreamCompAddStep(stream
, NULL
, NULL
,
1704 XML_ELEMENT_NODE
, flags
);
1712 case XML_OP_ANCESTOR
:
1713 /* Skip redundant continuations. */
1714 if (flags
& XML_STREAM_STEP_DESC
)
1716 flags
|= XML_STREAM_STEP_DESC
;
1718 * Mark the expression as having "//".
1720 if ((stream
->flags
& XML_STREAM_DESC
) == 0)
1721 stream
->flags
|= XML_STREAM_DESC
;
1725 if ((! root
) && (comp
->flags
& XML_PATTERN_NOTPATTERN
) == 0) {
1727 * If this should behave like a real pattern, we will mark
1728 * the first step as having "//", to be reentrant on every
1731 if ((stream
->flags
& XML_STREAM_DESC
) == 0)
1732 stream
->flags
|= XML_STREAM_DESC
;
1734 if (stream
->nbStep
> 0) {
1735 if ((stream
->steps
[0].flags
& XML_STREAM_STEP_DESC
) == 0)
1736 stream
->steps
[0].flags
|= XML_STREAM_STEP_DESC
;
1739 if (stream
->nbStep
<= s
)
1741 stream
->steps
[s
].flags
|= XML_STREAM_STEP_FINAL
;
1743 stream
->steps
[0].flags
|= XML_STREAM_STEP_ROOT
;
1744 #ifdef DEBUG_STREAMING
1745 xmlDebugStreamComp(stream
);
1747 comp
->stream
= stream
;
1750 xmlFreeStreamComp(stream
);
1756 * @size: the number of expected states
1758 * build a new stream context
1760 * Returns the new structure or NULL in case of error.
1762 static xmlStreamCtxtPtr
1763 xmlNewStreamCtxt(xmlStreamCompPtr stream
) {
1764 xmlStreamCtxtPtr cur
;
1766 cur
= (xmlStreamCtxtPtr
) xmlMalloc(sizeof(xmlStreamCtxt
));
1768 ERROR(NULL
, NULL
, NULL
,
1769 "xmlNewStreamCtxt: malloc failed\n");
1772 memset(cur
, 0, sizeof(xmlStreamCtxt
));
1773 cur
->states
= (int *) xmlMalloc(4 * 2 * sizeof(int));
1774 if (cur
->states
== NULL
) {
1776 ERROR(NULL
, NULL
, NULL
,
1777 "xmlNewStreamCtxt: malloc failed\n");
1784 cur
->blockLevel
= -1;
1789 * xmlFreeStreamCtxt:
1790 * @stream: the stream context
1792 * Free the stream context
1795 xmlFreeStreamCtxt(xmlStreamCtxtPtr stream
) {
1796 xmlStreamCtxtPtr next
;
1798 while (stream
!= NULL
) {
1799 next
= stream
->next
;
1800 if (stream
->states
!= NULL
)
1801 xmlFree(stream
->states
);
1808 * xmlStreamCtxtAddState:
1809 * @comp: the stream context
1810 * @idx: the step index for that streaming state
1812 * Add a new state to the stream context
1814 * Returns -1 in case of error or the state index if successful
1817 xmlStreamCtxtAddState(xmlStreamCtxtPtr comp
, int idx
, int level
) {
1819 for (i
= 0;i
< comp
->nbState
;i
++) {
1820 if (comp
->states
[2 * i
] < 0) {
1821 comp
->states
[2 * i
] = idx
;
1822 comp
->states
[2 * i
+ 1] = level
;
1826 if (comp
->nbState
>= comp
->maxState
) {
1829 cur
= (int *) xmlRealloc(comp
->states
,
1830 comp
->maxState
* 4 * sizeof(int));
1832 ERROR(NULL
, NULL
, NULL
,
1833 "xmlNewStreamCtxt: malloc failed\n");
1837 comp
->maxState
*= 2;
1839 comp
->states
[2 * comp
->nbState
] = idx
;
1840 comp
->states
[2 * comp
->nbState
++ + 1] = level
;
1841 return(comp
->nbState
- 1);
1845 * xmlStreamPushInternal:
1846 * @stream: the stream context
1847 * @name: the current name
1848 * @ns: the namespace name
1849 * @nodeType: the type of the node
1851 * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
1852 * indicated a dictionary, then strings for name and ns will be expected
1853 * to come from the dictionary.
1854 * Both @name and @ns being NULL means the / i.e. the root of the document.
1855 * This can also act as a reset.
1857 * Returns: -1 in case of error, 1 if the current state in the stream is a
1858 * match and 0 otherwise.
1861 xmlStreamPushInternal(xmlStreamCtxtPtr stream
,
1862 const xmlChar
*name
, const xmlChar
*ns
,
1864 int ret
= 0, err
= 0, final
= 0, tmp
, i
, m
, match
, stepNr
, desc
;
1865 xmlStreamCompPtr comp
;
1867 #ifdef DEBUG_STREAMING
1868 xmlStreamCtxtPtr orig
= stream
;
1871 if ((stream
== NULL
) || (stream
->nbState
< 0))
1874 while (stream
!= NULL
) {
1875 comp
= stream
->comp
;
1877 if ((nodeType
== XML_ELEMENT_NODE
) &&
1878 (name
== NULL
) && (ns
== NULL
)) {
1879 /* We have a document node here (or a reset). */
1880 stream
->nbState
= 0;
1882 stream
->blockLevel
= -1;
1883 if (comp
->flags
& XML_STREAM_FROM_ROOT
) {
1884 if (comp
->nbStep
== 0) {
1885 /* TODO: We have a "/." here? */
1888 if ((comp
->nbStep
== 1) &&
1889 (comp
->steps
[0].nodeType
== XML_STREAM_ANY_NODE
) &&
1890 (comp
->steps
[0].flags
& XML_STREAM_STEP_DESC
))
1893 * In the case of "//." the document node will match
1897 } else if (comp
->steps
[0].flags
& XML_STREAM_STEP_ROOT
) {
1898 /* TODO: Do we need this ? */
1899 tmp
= xmlStreamCtxtAddState(stream
, 0, 0);
1905 stream
= stream
->next
;
1906 continue; /* while */
1910 * Fast check for ".".
1912 if (comp
->nbStep
== 0) {
1914 * / and . are handled at the XPath node set creation
1915 * level by checking min depth
1917 if (stream
->flags
& XML_PATTERN_XPATH
) {
1918 stream
= stream
->next
;
1919 continue; /* while */
1922 * For non-pattern like evaluation like XML Schema IDCs
1923 * or traditional XPath expressions, this will match if
1924 * we are at the first level only, otherwise on every level.
1926 if ((nodeType
!= XML_ATTRIBUTE_NODE
) &&
1927 (((stream
->flags
& XML_PATTERN_NOTPATTERN
) == 0) ||
1928 (stream
->level
== 0))) {
1934 if (stream
->blockLevel
!= -1) {
1936 * Skip blocked expressions.
1942 if ((nodeType
!= XML_ELEMENT_NODE
) &&
1943 (nodeType
!= XML_ATTRIBUTE_NODE
) &&
1944 ((comp
->flags
& XML_STREAM_FINAL_IS_ANY_NODE
) == 0)) {
1946 * No need to process nodes of other types if we don't
1947 * resolve to those types.
1948 * TODO: Do we need to block the context here?
1955 * Check evolution of existing states
1958 m
= stream
->nbState
;
1960 if ((comp
->flags
& XML_STREAM_DESC
) == 0) {
1962 * If there is no "//", then only the last
1963 * added state is of interest.
1965 stepNr
= stream
->states
[2 * (stream
->nbState
-1)];
1967 * TODO: Security check, should not happen, remove it.
1969 if (stream
->states
[(2 * (stream
->nbState
-1)) + 1] <
1978 * If there are "//", then we need to process every "//"
1979 * occurring in the states, plus any other state for this
1982 stepNr
= stream
->states
[2 * i
];
1984 /* TODO: should not happen anymore: dead states */
1988 tmp
= stream
->states
[(2 * i
) + 1];
1990 /* skip new states just added */
1991 if (tmp
> stream
->level
)
1994 /* skip states at ancestor levels, except if "//" */
1995 desc
= comp
->steps
[stepNr
].flags
& XML_STREAM_STEP_DESC
;
1996 if ((tmp
< stream
->level
) && (!desc
))
2000 * Check for correct node-type.
2002 step
= comp
->steps
[stepNr
];
2003 if (step
.nodeType
!= nodeType
) {
2004 if (step
.nodeType
== XML_ATTRIBUTE_NODE
) {
2006 * Block this expression for deeper evaluation.
2008 if ((comp
->flags
& XML_STREAM_DESC
) == 0)
2009 stream
->blockLevel
= stream
->level
+1;
2011 } else if (step
.nodeType
!= XML_STREAM_ANY_NODE
)
2015 * Compare local/namespace-name.
2018 if (step
.nodeType
== XML_STREAM_ANY_NODE
) {
2020 } else if (step
.name
== NULL
) {
2021 if (step
.ns
== NULL
) {
2023 * This lets through all elements/attributes.
2026 } else if (ns
!= NULL
)
2027 match
= xmlStrEqual(step
.ns
, ns
);
2028 } else if (((step
.ns
!= NULL
) == (ns
!= NULL
)) &&
2030 (step
.name
[0] == name
[0]) &&
2031 xmlStrEqual(step
.name
, name
) &&
2032 ((step
.ns
== ns
) || xmlStrEqual(step
.ns
, ns
)))
2038 * TODO: Pointer comparison won't work, since not guaranteed that the given
2039 * values are in the same dict; especially if it's the namespace name,
2040 * normally coming from ns->href. We need a namespace dict mechanism !
2042 } else if (comp
->dict
) {
2043 if (step
.name
== NULL
) {
2044 if (step
.ns
== NULL
)
2047 match
= (step
.ns
== ns
);
2049 match
= ((step
.name
== name
) && (step
.ns
== ns
));
2051 #endif /* if 0 ------------------------------------------------------- */
2053 final
= step
.flags
& XML_STREAM_STEP_FINAL
;
2058 /* descending match create a new state */
2059 xmlStreamCtxtAddState(stream
, stepNr
+ 1,
2066 xmlStreamCtxtAddState(stream
, stepNr
+ 1,
2070 if ((ret
!= 1) && (step
.flags
& XML_STREAM_STEP_IN_SET
)) {
2072 * Check if we have a special case like "foo/bar//.", where
2073 * "foo" is selected as well.
2078 if (((comp
->flags
& XML_STREAM_DESC
) == 0) &&
2079 ((! match
) || final
)) {
2081 * Mark this expression as blocked for any evaluation at
2082 * deeper levels. Note that this includes "/foo"
2083 * expressions if the *pattern* behaviour is used.
2085 stream
->blockLevel
= stream
->level
+1;
2094 * Re/enter the expression.
2095 * Don't reenter if it's an absolute expression like "/foo",
2098 step
= comp
->steps
[0];
2099 if (step
.flags
& XML_STREAM_STEP_ROOT
)
2102 desc
= step
.flags
& XML_STREAM_STEP_DESC
;
2103 if (stream
->flags
& XML_PATTERN_NOTPATTERN
) {
2105 * Re/enter the expression if it is a "descendant" one,
2106 * or if we are at the 1st level of evaluation.
2109 if (stream
->level
== 1) {
2110 if (XML_STREAM_XS_IDC(stream
)) {
2112 * XS-IDC: The missing "self::node()" will always
2113 * match the first given node.
2120 * A "//" is always reentrant.
2126 * XS-IDC: Process the 2nd level, since the missing
2127 * "self::node()" is responsible for the 2nd level being
2128 * the real start level.
2130 if ((stream
->level
== 2) && XML_STREAM_XS_IDC(stream
))
2138 * Check expected node-type.
2140 if (step
.nodeType
!= nodeType
) {
2141 if (nodeType
== XML_ATTRIBUTE_NODE
)
2143 else if (step
.nodeType
!= XML_STREAM_ANY_NODE
)
2147 * Compare local/namespace-name.
2150 if (step
.nodeType
== XML_STREAM_ANY_NODE
) {
2152 } else if (step
.name
== NULL
) {
2153 if (step
.ns
== NULL
) {
2155 * This lets through all elements/attributes.
2158 } else if (ns
!= NULL
)
2159 match
= xmlStrEqual(step
.ns
, ns
);
2160 } else if (((step
.ns
!= NULL
) == (ns
!= NULL
)) &&
2162 (step
.name
[0] == name
[0]) &&
2163 xmlStrEqual(step
.name
, name
) &&
2164 ((step
.ns
== ns
) || xmlStrEqual(step
.ns
, ns
)))
2168 final
= step
.flags
& XML_STREAM_STEP_FINAL
;
2173 xmlStreamCtxtAddState(stream
, 1, stream
->level
);
2174 if ((ret
!= 1) && (step
.flags
& XML_STREAM_STEP_IN_SET
)) {
2176 * Check if we have a special case like "foo//.", where
2177 * "foo" is selected as well.
2182 if (((comp
->flags
& XML_STREAM_DESC
) == 0) &&
2183 ((! match
) || final
)) {
2185 * Mark this expression as blocked for any evaluation at
2188 stream
->blockLevel
= stream
->level
;
2192 stream
= stream
->next
;
2193 } /* while stream != NULL */
2197 #ifdef DEBUG_STREAMING
2198 xmlDebugStreamCtxt(orig
, ret
);
2205 * @stream: the stream context
2206 * @name: the current name
2207 * @ns: the namespace name
2209 * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
2210 * indicated a dictionary, then strings for name and ns will be expected
2211 * to come from the dictionary.
2212 * Both @name and @ns being NULL means the / i.e. the root of the document.
2213 * This can also act as a reset.
2214 * Otherwise the function will act as if it has been given an element-node.
2216 * Returns: -1 in case of error, 1 if the current state in the stream is a
2217 * match and 0 otherwise.
2220 xmlStreamPush(xmlStreamCtxtPtr stream
,
2221 const xmlChar
*name
, const xmlChar
*ns
) {
2222 return (xmlStreamPushInternal(stream
, name
, ns
, (int) XML_ELEMENT_NODE
));
2226 * xmlStreamPushNode:
2227 * @stream: the stream context
2228 * @name: the current name
2229 * @ns: the namespace name
2230 * @nodeType: the type of the node being pushed
2232 * Push new data onto the stream. NOTE: if the call xmlPatterncompile()
2233 * indicated a dictionary, then strings for name and ns will be expected
2234 * to come from the dictionary.
2235 * Both @name and @ns being NULL means the / i.e. the root of the document.
2236 * This can also act as a reset.
2237 * Different from xmlStreamPush() this function can be fed with nodes of type:
2238 * element-, attribute-, text-, cdata-section-, comment- and
2239 * processing-instruction-node.
2241 * Returns: -1 in case of error, 1 if the current state in the stream is a
2242 * match and 0 otherwise.
2245 xmlStreamPushNode(xmlStreamCtxtPtr stream
,
2246 const xmlChar
*name
, const xmlChar
*ns
,
2249 return (xmlStreamPushInternal(stream
, name
, ns
,
2254 * xmlStreamPushAttr:
2255 * @stream: the stream context
2256 * @name: the current name
2257 * @ns: the namespace name
2259 * Push new attribute data onto the stream. NOTE: if the call xmlPatterncompile()
2260 * indicated a dictionary, then strings for name and ns will be expected
2261 * to come from the dictionary.
2262 * Both @name and @ns being NULL means the / i.e. the root of the document.
2263 * This can also act as a reset.
2264 * Otherwise the function will act as if it has been given an attribute-node.
2266 * Returns: -1 in case of error, 1 if the current state in the stream is a
2267 * match and 0 otherwise.
2270 xmlStreamPushAttr(xmlStreamCtxtPtr stream
,
2271 const xmlChar
*name
, const xmlChar
*ns
) {
2272 return (xmlStreamPushInternal(stream
, name
, ns
, (int) XML_ATTRIBUTE_NODE
));
2277 * @stream: the stream context
2279 * push one level from the stream.
2281 * Returns: -1 in case of error, 0 otherwise.
2284 xmlStreamPop(xmlStreamCtxtPtr stream
) {
2289 while (stream
!= NULL
) {
2291 * Reset block-level.
2293 if (stream
->blockLevel
== stream
->level
)
2294 stream
->blockLevel
= -1;
2297 * stream->level can be zero when XML_FINAL_IS_ANY_NODE is set
2298 * (see the thread at
2299 * http://mail.gnome.org/archives/xslt/2008-July/msg00027.html)
2304 * Check evolution of existing states
2306 for (i
= stream
->nbState
-1; i
>= 0; i
--) {
2307 /* discard obsoleted states */
2308 lev
= stream
->states
[(2 * i
) + 1];
2309 if (lev
> stream
->level
)
2311 if (lev
<= stream
->level
)
2314 stream
= stream
->next
;
2320 * xmlStreamWantsAnyNode:
2321 * @streamCtxt: the stream context
2323 * Query if the streaming pattern additionally needs to be fed with
2324 * text-, cdata-section-, comment- and processing-instruction-nodes.
2325 * If the result is 0 then only element-nodes and attribute-nodes
2326 * need to be pushed.
2328 * Returns: 1 in case of need of nodes of the above described types,
2329 * 0 otherwise. -1 on API errors.
2332 xmlStreamWantsAnyNode(xmlStreamCtxtPtr streamCtxt
)
2334 if (streamCtxt
== NULL
)
2336 while (streamCtxt
!= NULL
) {
2337 if (streamCtxt
->comp
->flags
& XML_STREAM_FINAL_IS_ANY_NODE
)
2339 streamCtxt
= streamCtxt
->next
;
2344 /************************************************************************
2346 * The public interfaces *
2348 ************************************************************************/
2351 * xmlPatterncompile:
2352 * @pattern: the pattern to compile
2353 * @dict: an optional dictionary for interned strings
2354 * @flags: compilation flags, see xmlPatternFlags
2355 * @namespaces: the prefix definitions, array of [URI, prefix] or NULL
2357 * Compile a pattern.
2359 * Returns the compiled form of the pattern or NULL in case of error
2362 xmlPatterncompile(const xmlChar
*pattern
, xmlDict
*dict
, int flags
,
2363 const xmlChar
**namespaces
) {
2364 xmlPatternPtr ret
= NULL
, cur
;
2365 xmlPatParserContextPtr ctxt
= NULL
;
2366 const xmlChar
*or, *start
;
2367 xmlChar
*tmp
= NULL
;
2371 if (pattern
== NULL
)
2378 while ((*or != 0) && (*or != '|')) or++;
2380 ctxt
= xmlNewPatParserContext(start
, dict
, namespaces
);
2382 tmp
= xmlStrndup(start
, or - start
);
2384 ctxt
= xmlNewPatParserContext(tmp
, dict
, namespaces
);
2388 if (ctxt
== NULL
) goto error
;
2389 cur
= xmlNewPattern();
2390 if (cur
== NULL
) goto error
;
2392 * Assign string dict.
2396 xmlDictReference(dict
);
2401 cur
->next
= ret
->next
;
2407 if (XML_STREAM_XS_IDC(cur
))
2408 xmlCompileIDCXPathPath(ctxt
);
2410 xmlCompilePathPattern(ctxt
);
2411 if (ctxt
->error
!= 0)
2413 xmlFreePatParserContext(ctxt
);
2419 type
= cur
->flags
& (PAT_FROM_ROOT
| PAT_FROM_CUR
);
2420 } else if (type
== PAT_FROM_ROOT
) {
2421 if (cur
->flags
& PAT_FROM_CUR
)
2423 } else if (type
== PAT_FROM_CUR
) {
2424 if (cur
->flags
& PAT_FROM_ROOT
)
2429 xmlStreamCompile(cur
);
2430 if (xmlReversePattern(cur
) < 0)
2438 if (streamable
== 0) {
2440 while (cur
!= NULL
) {
2441 if (cur
->stream
!= NULL
) {
2442 xmlFreeStreamComp(cur
->stream
);
2451 if (ctxt
!= NULL
) xmlFreePatParserContext(ctxt
);
2452 if (ret
!= NULL
) xmlFreePattern(ret
);
2453 if (tmp
!= NULL
) xmlFree(tmp
);
2459 * @comp: the precompiled pattern
2462 * Test whether the node matches the pattern
2464 * Returns 1 if it matches, 0 if it doesn't and -1 in case of failure
2467 xmlPatternMatch(xmlPatternPtr comp
, xmlNodePtr node
)
2471 if ((comp
== NULL
) || (node
== NULL
))
2474 while (comp
!= NULL
) {
2475 ret
= xmlPatMatch(comp
, node
);
2484 * xmlPatternGetStreamCtxt:
2485 * @comp: the precompiled pattern
2487 * Get a streaming context for that pattern
2488 * Use xmlFreeStreamCtxt to free the context.
2490 * Returns a pointer to the context or NULL in case of failure
2493 xmlPatternGetStreamCtxt(xmlPatternPtr comp
)
2495 xmlStreamCtxtPtr ret
= NULL
, cur
;
2497 if ((comp
== NULL
) || (comp
->stream
== NULL
))
2500 while (comp
!= NULL
) {
2501 if (comp
->stream
== NULL
)
2503 cur
= xmlNewStreamCtxt(comp
->stream
);
2509 cur
->next
= ret
->next
;
2512 cur
->flags
= comp
->flags
;
2517 xmlFreeStreamCtxt(ret
);
2522 * xmlPatternStreamable:
2523 * @comp: the precompiled pattern
2525 * Check if the pattern is streamable i.e. xmlPatternGetStreamCtxt()
2528 * Returns 1 if streamable, 0 if not and -1 in case of error.
2531 xmlPatternStreamable(xmlPatternPtr comp
) {
2534 while (comp
!= NULL
) {
2535 if (comp
->stream
== NULL
)
2543 * xmlPatternMaxDepth:
2544 * @comp: the precompiled pattern
2546 * Check the maximum depth reachable by a pattern
2548 * Returns -2 if no limit (using //), otherwise the depth,
2549 * and -1 in case of error
2552 xmlPatternMaxDepth(xmlPatternPtr comp
) {
2556 while (comp
!= NULL
) {
2557 if (comp
->stream
== NULL
)
2559 for (i
= 0;i
< comp
->stream
->nbStep
;i
++)
2560 if (comp
->stream
->steps
[i
].flags
& XML_STREAM_STEP_DESC
)
2562 if (comp
->stream
->nbStep
> ret
)
2563 ret
= comp
->stream
->nbStep
;
2570 * xmlPatternMinDepth:
2571 * @comp: the precompiled pattern
2573 * Check the minimum depth reachable by a pattern, 0 mean the / or . are
2576 * Returns -1 in case of error otherwise the depth,
2580 xmlPatternMinDepth(xmlPatternPtr comp
) {
2584 while (comp
!= NULL
) {
2585 if (comp
->stream
== NULL
)
2587 if (comp
->stream
->nbStep
< ret
)
2588 ret
= comp
->stream
->nbStep
;
2597 * xmlPatternFromRoot:
2598 * @comp: the precompiled pattern
2600 * Check if the pattern must be looked at from the root.
2602 * Returns 1 if true, 0 if false and -1 in case of error
2605 xmlPatternFromRoot(xmlPatternPtr comp
) {
2608 while (comp
!= NULL
) {
2609 if (comp
->stream
== NULL
)
2611 if (comp
->flags
& PAT_FROM_ROOT
)
2619 #define bottom_pattern
2620 #include "elfgcchack.h"
2621 #endif /* LIBXML_PATTERN_ENABLED */