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