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