1/*
2 * regexp.c: generic and extensible Regular Expression engine
3 *
4 * Basically designed with the purpose of compiling regexps for
5 * the variety of validation/shemas mechanisms now available in
6 * XML related specifications these include:
7 *    - XML-1.0 DTD validation
8 *    - XML Schemas structure part 1
9 *    - XML Schemas Datatypes part 2 especially Appendix F
10 *    - RELAX-NG/TREX i.e. the counter proposal
11 *
12 * See Copyright for the status of this software.
13 *
14 * Daniel Veillard <veillard@redhat.com>
15 */
16
17#define IN_LIBXML
18#include "libxml.h"
19
20#ifdef LIBXML_REGEXP_ENABLED
21
22/* #define DEBUG_ERR */
23
24#include <stdio.h>
25#include <string.h>
26#ifdef HAVE_LIMITS_H
27#include <limits.h>
28#endif
29
30#include <libxml/tree.h>
31#include <libxml/parserInternals.h>
32#include <libxml/xmlregexp.h>
33#include <libxml/xmlautomata.h>
34#include <libxml/xmlunicode.h>
35
36#ifndef INT_MAX
37#define INT_MAX 123456789 /* easy to flag and big enough for our needs */
38#endif
39
40/* #define DEBUG_REGEXP_GRAPH */
41/* #define DEBUG_REGEXP_EXEC */
42/* #define DEBUG_PUSH */
43/* #define DEBUG_COMPACTION */
44
45#define MAX_PUSH 10000000
46
47#define ERROR(str)							\
48    ctxt->error = XML_REGEXP_COMPILE_ERROR;				\
49    xmlRegexpErrCompile(ctxt, str);
50#define NEXT ctxt->cur++
51#define CUR (*(ctxt->cur))
52#define NXT(index) (ctxt->cur[index])
53
54#define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)
55#define NEXTL(l) ctxt->cur += l;
56#define XML_REG_STRING_SEPARATOR '|'
57/*
58 * Need PREV to check on a '-' within a Character Group. May only be used
59 * when it's guaranteed that cur is not at the beginning of ctxt->string!
60 */
61#define PREV (ctxt->cur[-1])
62
63/**
64 * TODO:
65 *
66 * macro to flag unimplemented blocks
67 */
68#define TODO 								\
69    xmlGenericError(xmlGenericErrorContext,				\
70	    "Unimplemented block at %s:%d\n",				\
71            __FILE__, __LINE__);
72
73/************************************************************************
74 * 									*
75 * 			Datatypes and structures			*
76 * 									*
77 ************************************************************************/
78
79/*
80 * Note: the order of the enums below is significant, do not shuffle
81 */
82typedef enum {
83    XML_REGEXP_EPSILON = 1,
84    XML_REGEXP_CHARVAL,
85    XML_REGEXP_RANGES,
86    XML_REGEXP_SUBREG,  /* used for () sub regexps */
87    XML_REGEXP_STRING,
88    XML_REGEXP_ANYCHAR, /* . */
89    XML_REGEXP_ANYSPACE, /* \s */
90    XML_REGEXP_NOTSPACE, /* \S */
91    XML_REGEXP_INITNAME, /* \l */
92    XML_REGEXP_NOTINITNAME, /* \L */
93    XML_REGEXP_NAMECHAR, /* \c */
94    XML_REGEXP_NOTNAMECHAR, /* \C */
95    XML_REGEXP_DECIMAL, /* \d */
96    XML_REGEXP_NOTDECIMAL, /* \D */
97    XML_REGEXP_REALCHAR, /* \w */
98    XML_REGEXP_NOTREALCHAR, /* \W */
99    XML_REGEXP_LETTER = 100,
100    XML_REGEXP_LETTER_UPPERCASE,
101    XML_REGEXP_LETTER_LOWERCASE,
102    XML_REGEXP_LETTER_TITLECASE,
103    XML_REGEXP_LETTER_MODIFIER,
104    XML_REGEXP_LETTER_OTHERS,
105    XML_REGEXP_MARK,
106    XML_REGEXP_MARK_NONSPACING,
107    XML_REGEXP_MARK_SPACECOMBINING,
108    XML_REGEXP_MARK_ENCLOSING,
109    XML_REGEXP_NUMBER,
110    XML_REGEXP_NUMBER_DECIMAL,
111    XML_REGEXP_NUMBER_LETTER,
112    XML_REGEXP_NUMBER_OTHERS,
113    XML_REGEXP_PUNCT,
114    XML_REGEXP_PUNCT_CONNECTOR,
115    XML_REGEXP_PUNCT_DASH,
116    XML_REGEXP_PUNCT_OPEN,
117    XML_REGEXP_PUNCT_CLOSE,
118    XML_REGEXP_PUNCT_INITQUOTE,
119    XML_REGEXP_PUNCT_FINQUOTE,
120    XML_REGEXP_PUNCT_OTHERS,
121    XML_REGEXP_SEPAR,
122    XML_REGEXP_SEPAR_SPACE,
123    XML_REGEXP_SEPAR_LINE,
124    XML_REGEXP_SEPAR_PARA,
125    XML_REGEXP_SYMBOL,
126    XML_REGEXP_SYMBOL_MATH,
127    XML_REGEXP_SYMBOL_CURRENCY,
128    XML_REGEXP_SYMBOL_MODIFIER,
129    XML_REGEXP_SYMBOL_OTHERS,
130    XML_REGEXP_OTHER,
131    XML_REGEXP_OTHER_CONTROL,
132    XML_REGEXP_OTHER_FORMAT,
133    XML_REGEXP_OTHER_PRIVATE,
134    XML_REGEXP_OTHER_NA,
135    XML_REGEXP_BLOCK_NAME
136} xmlRegAtomType;
137
138typedef enum {
139    XML_REGEXP_QUANT_EPSILON = 1,
140    XML_REGEXP_QUANT_ONCE,
141    XML_REGEXP_QUANT_OPT,
142    XML_REGEXP_QUANT_MULT,
143    XML_REGEXP_QUANT_PLUS,
144    XML_REGEXP_QUANT_ONCEONLY,
145    XML_REGEXP_QUANT_ALL,
146    XML_REGEXP_QUANT_RANGE
147} xmlRegQuantType;
148
149typedef enum {
150    XML_REGEXP_START_STATE = 1,
151    XML_REGEXP_FINAL_STATE,
152    XML_REGEXP_TRANS_STATE,
153    XML_REGEXP_SINK_STATE,
154    XML_REGEXP_UNREACH_STATE
155} xmlRegStateType;
156
157typedef enum {
158    XML_REGEXP_MARK_NORMAL = 0,
159    XML_REGEXP_MARK_START,
160    XML_REGEXP_MARK_VISITED
161} xmlRegMarkedType;
162
163typedef struct _xmlRegRange xmlRegRange;
164typedef xmlRegRange *xmlRegRangePtr;
165
166struct _xmlRegRange {
167    int neg;		/* 0 normal, 1 not, 2 exclude */
168    xmlRegAtomType type;
169    int start;
170    int end;
171    xmlChar *blockName;
172};
173
174typedef struct _xmlRegAtom xmlRegAtom;
175typedef xmlRegAtom *xmlRegAtomPtr;
176
177typedef struct _xmlAutomataState xmlRegState;
178typedef xmlRegState *xmlRegStatePtr;
179
180struct _xmlRegAtom {
181    int no;
182    xmlRegAtomType type;
183    xmlRegQuantType quant;
184    int min;
185    int max;
186
187    void *valuep;
188    void *valuep2;
189    int neg;
190    int codepoint;
191    xmlRegStatePtr start;
192    xmlRegStatePtr start0;
193    xmlRegStatePtr stop;
194    int maxRanges;
195    int nbRanges;
196    xmlRegRangePtr *ranges;
197    void *data;
198};
199
200typedef struct _xmlRegCounter xmlRegCounter;
201typedef xmlRegCounter *xmlRegCounterPtr;
202
203struct _xmlRegCounter {
204    int min;
205    int max;
206};
207
208typedef struct _xmlRegTrans xmlRegTrans;
209typedef xmlRegTrans *xmlRegTransPtr;
210
211struct _xmlRegTrans {
212    xmlRegAtomPtr atom;
213    int to;
214    int counter;
215    int count;
216    int nd;
217};
218
219struct _xmlAutomataState {
220    xmlRegStateType type;
221    xmlRegMarkedType mark;
222    xmlRegMarkedType reached;
223    int no;
224    int maxTrans;
225    int nbTrans;
226    xmlRegTrans *trans;
227    /*  knowing states ponting to us can speed things up */
228    int maxTransTo;
229    int nbTransTo;
230    int *transTo;
231};
232
233typedef struct _xmlAutomata xmlRegParserCtxt;
234typedef xmlRegParserCtxt *xmlRegParserCtxtPtr;
235
236struct _xmlAutomata {
237    xmlChar *string;
238    xmlChar *cur;
239
240    int error;
241    int neg;
242
243    xmlRegStatePtr start;
244    xmlRegStatePtr end;
245    xmlRegStatePtr state;
246
247    xmlRegAtomPtr atom;
248
249    int maxAtoms;
250    int nbAtoms;
251    xmlRegAtomPtr *atoms;
252
253    int maxStates;
254    int nbStates;
255    xmlRegStatePtr *states;
256
257    int maxCounters;
258    int nbCounters;
259    xmlRegCounter *counters;
260
261    int determinist;
262    int negs;
263};
264
265struct _xmlRegexp {
266    xmlChar *string;
267    int nbStates;
268    xmlRegStatePtr *states;
269    int nbAtoms;
270    xmlRegAtomPtr *atoms;
271    int nbCounters;
272    xmlRegCounter *counters;
273    int determinist;
274    /*
275     * That's the compact form for determinists automatas
276     */
277    int nbstates;
278    int *compact;
279    void **transdata;
280    int nbstrings;
281    xmlChar **stringMap;
282};
283
284typedef struct _xmlRegExecRollback xmlRegExecRollback;
285typedef xmlRegExecRollback *xmlRegExecRollbackPtr;
286
287struct _xmlRegExecRollback {
288    xmlRegStatePtr state;/* the current state */
289    int index;		/* the index in the input stack */
290    int nextbranch;	/* the next transition to explore in that state */
291    int *counts;	/* save the automata state if it has some */
292};
293
294typedef struct _xmlRegInputToken xmlRegInputToken;
295typedef xmlRegInputToken *xmlRegInputTokenPtr;
296
297struct _xmlRegInputToken {
298    xmlChar *value;
299    void *data;
300};
301
302struct _xmlRegExecCtxt {
303    int status;		/* execution status != 0 indicate an error */
304    int determinist;	/* did we find an indeterministic behaviour */
305    xmlRegexpPtr comp;	/* the compiled regexp */
306    xmlRegExecCallbacks callback;
307    void *data;
308
309    xmlRegStatePtr state;/* the current state */
310    int transno;	/* the current transition on that state */
311    int transcount;	/* the number of chars in char counted transitions */
312
313    /*
314     * A stack of rollback states
315     */
316    int maxRollbacks;
317    int nbRollbacks;
318    xmlRegExecRollback *rollbacks;
319
320    /*
321     * The state of the automata if any
322     */
323    int *counts;
324
325    /*
326     * The input stack
327     */
328    int inputStackMax;
329    int inputStackNr;
330    int index;
331    int *charStack;
332    const xmlChar *inputString; /* when operating on characters */
333    xmlRegInputTokenPtr inputStack;/* when operating on strings */
334
335    /*
336     * error handling
337     */
338    int errStateNo;		/* the error state number */
339    xmlRegStatePtr errState;    /* the error state */
340    xmlChar *errString;		/* the string raising the error */
341    int *errCounts;		/* counters at the error state */
342    int nbPush;
343};
344
345#define REGEXP_ALL_COUNTER	0x123456
346#define REGEXP_ALL_LAX_COUNTER	0x123457
347
348static void xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top);
349static void xmlRegFreeState(xmlRegStatePtr state);
350static void xmlRegFreeAtom(xmlRegAtomPtr atom);
351static int xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr);
352static int xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint);
353static int xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint,
354                  int neg, int start, int end, const xmlChar *blockName);
355
356/************************************************************************
357 *									*
358 * 		Regexp memory error handler				*
359 *									*
360 ************************************************************************/
361/**
362 * xmlRegexpErrMemory:
363 * @extra:  extra information
364 *
365 * Handle an out of memory condition
366 */
367static void
368xmlRegexpErrMemory(xmlRegParserCtxtPtr ctxt, const char *extra)
369{
370    const char *regexp = NULL;
371    if (ctxt != NULL) {
372        regexp = (const char *) ctxt->string;
373	ctxt->error = XML_ERR_NO_MEMORY;
374    }
375    __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP,
376		    XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0, extra,
377		    regexp, NULL, 0, 0,
378		    "Memory allocation failed : %s\n", extra);
379}
380
381/**
382 * xmlRegexpErrCompile:
383 * @extra:  extra information
384 *
385 * Handle a compilation failure
386 */
387static void
388xmlRegexpErrCompile(xmlRegParserCtxtPtr ctxt, const char *extra)
389{
390    const char *regexp = NULL;
391    int idx = 0;
392
393    if (ctxt != NULL) {
394        regexp = (const char *) ctxt->string;
395	idx = ctxt->cur - ctxt->string;
396	ctxt->error = XML_REGEXP_COMPILE_ERROR;
397    }
398    __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP,
399		    XML_REGEXP_COMPILE_ERROR, XML_ERR_FATAL, NULL, 0, extra,
400		    regexp, NULL, idx, 0,
401		    "failed to compile: %s\n", extra);
402}
403
404/************************************************************************
405 * 									*
406 * 			Allocation/Deallocation				*
407 * 									*
408 ************************************************************************/
409
410static int xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt);
411/**
412 * xmlRegEpxFromParse:
413 * @ctxt:  the parser context used to build it
414 *
415 * Allocate a new regexp and fill it with the result from the parser
416 *
417 * Returns the new regexp or NULL in case of error
418 */
419static xmlRegexpPtr
420xmlRegEpxFromParse(xmlRegParserCtxtPtr ctxt) {
421    xmlRegexpPtr ret;
422
423    ret = (xmlRegexpPtr) xmlMalloc(sizeof(xmlRegexp));
424    if (ret == NULL) {
425	xmlRegexpErrMemory(ctxt, "compiling regexp");
426	return(NULL);
427    }
428    memset(ret, 0, sizeof(xmlRegexp));
429    ret->string = ctxt->string;
430    ret->nbStates = ctxt->nbStates;
431    ret->states = ctxt->states;
432    ret->nbAtoms = ctxt->nbAtoms;
433    ret->atoms = ctxt->atoms;
434    ret->nbCounters = ctxt->nbCounters;
435    ret->counters = ctxt->counters;
436    ret->determinist = ctxt->determinist;
437    if (ret->determinist == -1) {
438        xmlRegexpIsDeterminist(ret);
439    }
440
441    if ((ret->determinist != 0) &&
442	(ret->nbCounters == 0) &&
443	(ctxt->negs == 0) &&
444	(ret->atoms != NULL) &&
445	(ret->atoms[0] != NULL) &&
446	(ret->atoms[0]->type == XML_REGEXP_STRING)) {
447	int i, j, nbstates = 0, nbatoms = 0;
448	int *stateRemap;
449	int *stringRemap;
450	int *transitions;
451	void **transdata;
452	xmlChar **stringMap;
453        xmlChar *value;
454
455	/*
456	 * Switch to a compact representation
457	 * 1/ counting the effective number of states left
458	 * 2/ counting the unique number of atoms, and check that
459	 *    they are all of the string type
460	 * 3/ build a table state x atom for the transitions
461	 */
462
463	stateRemap = xmlMalloc(ret->nbStates * sizeof(int));
464	if (stateRemap == NULL) {
465	    xmlRegexpErrMemory(ctxt, "compiling regexp");
466	    xmlFree(ret);
467	    return(NULL);
468	}
469	for (i = 0;i < ret->nbStates;i++) {
470	    if (ret->states[i] != NULL) {
471		stateRemap[i] = nbstates;
472		nbstates++;
473	    } else {
474		stateRemap[i] = -1;
475	    }
476	}
477#ifdef DEBUG_COMPACTION
478	printf("Final: %d states\n", nbstates);
479#endif
480	stringMap = xmlMalloc(ret->nbAtoms * sizeof(char *));
481	if (stringMap == NULL) {
482	    xmlRegexpErrMemory(ctxt, "compiling regexp");
483	    xmlFree(stateRemap);
484	    xmlFree(ret);
485	    return(NULL);
486	}
487	stringRemap = xmlMalloc(ret->nbAtoms * sizeof(int));
488	if (stringRemap == NULL) {
489	    xmlRegexpErrMemory(ctxt, "compiling regexp");
490	    xmlFree(stringMap);
491	    xmlFree(stateRemap);
492	    xmlFree(ret);
493	    return(NULL);
494	}
495	for (i = 0;i < ret->nbAtoms;i++) {
496	    if ((ret->atoms[i]->type == XML_REGEXP_STRING) &&
497		(ret->atoms[i]->quant == XML_REGEXP_QUANT_ONCE)) {
498		value = ret->atoms[i]->valuep;
499                for (j = 0;j < nbatoms;j++) {
500		    if (xmlStrEqual(stringMap[j], value)) {
501			stringRemap[i] = j;
502			break;
503		    }
504		}
505		if (j >= nbatoms) {
506		    stringRemap[i] = nbatoms;
507		    stringMap[nbatoms] = xmlStrdup(value);
508		    if (stringMap[nbatoms] == NULL) {
509			for (i = 0;i < nbatoms;i++)
510			    xmlFree(stringMap[i]);
511			xmlFree(stringRemap);
512			xmlFree(stringMap);
513			xmlFree(stateRemap);
514			xmlFree(ret);
515			return(NULL);
516		    }
517		    nbatoms++;
518		}
519	    } else {
520		xmlFree(stateRemap);
521		xmlFree(stringRemap);
522		for (i = 0;i < nbatoms;i++)
523		    xmlFree(stringMap[i]);
524		xmlFree(stringMap);
525		xmlFree(ret);
526		return(NULL);
527	    }
528	}
529#ifdef DEBUG_COMPACTION
530	printf("Final: %d atoms\n", nbatoms);
531#endif
532	transitions = (int *) xmlMalloc((nbstates + 1) *
533	                                (nbatoms + 1) * sizeof(int));
534	if (transitions == NULL) {
535	    xmlFree(stateRemap);
536	    xmlFree(stringRemap);
537	    xmlFree(stringMap);
538	    xmlFree(ret);
539	    return(NULL);
540	}
541	memset(transitions, 0, (nbstates + 1) * (nbatoms + 1) * sizeof(int));
542
543	/*
544	 * Allocate the transition table. The first entry for each
545	 * state corresponds to the state type.
546	 */
547	transdata = NULL;
548
549	for (i = 0;i < ret->nbStates;i++) {
550	    int stateno, atomno, targetno, prev;
551	    xmlRegStatePtr state;
552	    xmlRegTransPtr trans;
553
554	    stateno = stateRemap[i];
555	    if (stateno == -1)
556		continue;
557	    state = ret->states[i];
558
559	    transitions[stateno * (nbatoms + 1)] = state->type;
560
561	    for (j = 0;j < state->nbTrans;j++) {
562		trans = &(state->trans[j]);
563		if ((trans->to == -1) || (trans->atom == NULL))
564		    continue;
565                atomno = stringRemap[trans->atom->no];
566		if ((trans->atom->data != NULL) && (transdata == NULL)) {
567		    transdata = (void **) xmlMalloc(nbstates * nbatoms *
568			                            sizeof(void *));
569		    if (transdata != NULL)
570			memset(transdata, 0,
571			       nbstates * nbatoms * sizeof(void *));
572		    else {
573			xmlRegexpErrMemory(ctxt, "compiling regexp");
574			break;
575		    }
576		}
577		targetno = stateRemap[trans->to];
578		/*
579		 * if the same atom can generate transitions to 2 different
580		 * states then it means the automata is not determinist and
581		 * the compact form can't be used !
582		 */
583		prev = transitions[stateno * (nbatoms + 1) + atomno + 1];
584		if (prev != 0) {
585		    if (prev != targetno + 1) {
586			ret->determinist = 0;
587#ifdef DEBUG_COMPACTION
588			printf("Indet: state %d trans %d, atom %d to %d : %d to %d\n",
589			       i, j, trans->atom->no, trans->to, atomno, targetno);
590			printf("       previous to is %d\n", prev);
591#endif
592			if (transdata != NULL)
593			    xmlFree(transdata);
594			xmlFree(transitions);
595			xmlFree(stateRemap);
596			xmlFree(stringRemap);
597			for (i = 0;i < nbatoms;i++)
598			    xmlFree(stringMap[i]);
599			xmlFree(stringMap);
600			goto not_determ;
601		    }
602		} else {
603#if 0
604		    printf("State %d trans %d: atom %d to %d : %d to %d\n",
605			   i, j, trans->atom->no, trans->to, atomno, targetno);
606#endif
607		    transitions[stateno * (nbatoms + 1) + atomno + 1] =
608			targetno + 1; /* to avoid 0 */
609		    if (transdata != NULL)
610			transdata[stateno * nbatoms + atomno] =
611			    trans->atom->data;
612		}
613	    }
614	}
615	ret->determinist = 1;
616#ifdef DEBUG_COMPACTION
617	/*
618	 * Debug
619	 */
620	for (i = 0;i < nbstates;i++) {
621	    for (j = 0;j < nbatoms + 1;j++) {
622                printf("%02d ", transitions[i * (nbatoms + 1) + j]);
623	    }
624	    printf("\n");
625	}
626	printf("\n");
627#endif
628	/*
629	 * Cleanup of the old data
630	 */
631	if (ret->states != NULL) {
632	    for (i = 0;i < ret->nbStates;i++)
633		xmlRegFreeState(ret->states[i]);
634	    xmlFree(ret->states);
635	}
636	ret->states = NULL;
637	ret->nbStates = 0;
638	if (ret->atoms != NULL) {
639	    for (i = 0;i < ret->nbAtoms;i++)
640		xmlRegFreeAtom(ret->atoms[i]);
641	    xmlFree(ret->atoms);
642	}
643	ret->atoms = NULL;
644	ret->nbAtoms = 0;
645
646	ret->compact = transitions;
647	ret->transdata = transdata;
648	ret->stringMap = stringMap;
649	ret->nbstrings = nbatoms;
650	ret->nbstates = nbstates;
651	xmlFree(stateRemap);
652	xmlFree(stringRemap);
653    }
654not_determ:
655    ctxt->string = NULL;
656    ctxt->nbStates = 0;
657    ctxt->states = NULL;
658    ctxt->nbAtoms = 0;
659    ctxt->atoms = NULL;
660    ctxt->nbCounters = 0;
661    ctxt->counters = NULL;
662    return(ret);
663}
664
665/**
666 * xmlRegNewParserCtxt:
667 * @string:  the string to parse
668 *
669 * Allocate a new regexp parser context
670 *
671 * Returns the new context or NULL in case of error
672 */
673static xmlRegParserCtxtPtr
674xmlRegNewParserCtxt(const xmlChar *string) {
675    xmlRegParserCtxtPtr ret;
676
677    ret = (xmlRegParserCtxtPtr) xmlMalloc(sizeof(xmlRegParserCtxt));
678    if (ret == NULL)
679	return(NULL);
680    memset(ret, 0, sizeof(xmlRegParserCtxt));
681    if (string != NULL)
682	ret->string = xmlStrdup(string);
683    ret->cur = ret->string;
684    ret->neg = 0;
685    ret->negs = 0;
686    ret->error = 0;
687    ret->determinist = -1;
688    return(ret);
689}
690
691/**
692 * xmlRegNewRange:
693 * @ctxt:  the regexp parser context
694 * @neg:  is that negative
695 * @type:  the type of range
696 * @start:  the start codepoint
697 * @end:  the end codepoint
698 *
699 * Allocate a new regexp range
700 *
701 * Returns the new range or NULL in case of error
702 */
703static xmlRegRangePtr
704xmlRegNewRange(xmlRegParserCtxtPtr ctxt,
705	       int neg, xmlRegAtomType type, int start, int end) {
706    xmlRegRangePtr ret;
707
708    ret = (xmlRegRangePtr) xmlMalloc(sizeof(xmlRegRange));
709    if (ret == NULL) {
710	xmlRegexpErrMemory(ctxt, "allocating range");
711	return(NULL);
712    }
713    ret->neg = neg;
714    ret->type = type;
715    ret->start = start;
716    ret->end = end;
717    return(ret);
718}
719
720/**
721 * xmlRegFreeRange:
722 * @range:  the regexp range
723 *
724 * Free a regexp range
725 */
726static void
727xmlRegFreeRange(xmlRegRangePtr range) {
728    if (range == NULL)
729	return;
730
731    if (range->blockName != NULL)
732	xmlFree(range->blockName);
733    xmlFree(range);
734}
735
736/**
737 * xmlRegCopyRange:
738 * @range:  the regexp range
739 *
740 * Copy a regexp range
741 *
742 * Returns the new copy or NULL in case of error.
743 */
744static xmlRegRangePtr
745xmlRegCopyRange(xmlRegParserCtxtPtr ctxt, xmlRegRangePtr range) {
746    xmlRegRangePtr ret;
747
748    if (range == NULL)
749	return(NULL);
750
751    ret = xmlRegNewRange(ctxt, range->neg, range->type, range->start,
752                         range->end);
753    if (ret == NULL)
754        return(NULL);
755    if (range->blockName != NULL) {
756	ret->blockName = xmlStrdup(range->blockName);
757	if (ret->blockName == NULL) {
758	    xmlRegexpErrMemory(ctxt, "allocating range");
759	    xmlRegFreeRange(ret);
760	    return(NULL);
761	}
762    }
763    return(ret);
764}
765
766/**
767 * xmlRegNewAtom:
768 * @ctxt:  the regexp parser context
769 * @type:  the type of atom
770 *
771 * Allocate a new atom
772 *
773 * Returns the new atom or NULL in case of error
774 */
775static xmlRegAtomPtr
776xmlRegNewAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomType type) {
777    xmlRegAtomPtr ret;
778
779    ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));
780    if (ret == NULL) {
781	xmlRegexpErrMemory(ctxt, "allocating atom");
782	return(NULL);
783    }
784    memset(ret, 0, sizeof(xmlRegAtom));
785    ret->type = type;
786    ret->quant = XML_REGEXP_QUANT_ONCE;
787    ret->min = 0;
788    ret->max = 0;
789    return(ret);
790}
791
792/**
793 * xmlRegFreeAtom:
794 * @atom:  the regexp atom
795 *
796 * Free a regexp atom
797 */
798static void
799xmlRegFreeAtom(xmlRegAtomPtr atom) {
800    int i;
801
802    if (atom == NULL)
803	return;
804
805    for (i = 0;i < atom->nbRanges;i++)
806	xmlRegFreeRange(atom->ranges[i]);
807    if (atom->ranges != NULL)
808	xmlFree(atom->ranges);
809    if ((atom->type == XML_REGEXP_STRING) && (atom->valuep != NULL))
810	xmlFree(atom->valuep);
811    if ((atom->type == XML_REGEXP_STRING) && (atom->valuep2 != NULL))
812	xmlFree(atom->valuep2);
813    if ((atom->type == XML_REGEXP_BLOCK_NAME) && (atom->valuep != NULL))
814	xmlFree(atom->valuep);
815    xmlFree(atom);
816}
817
818/**
819 * xmlRegCopyAtom:
820 * @ctxt:  the regexp parser context
821 * @atom:  the oiginal atom
822 *
823 * Allocate a new regexp range
824 *
825 * Returns the new atom or NULL in case of error
826 */
827static xmlRegAtomPtr
828xmlRegCopyAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {
829    xmlRegAtomPtr ret;
830
831    ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));
832    if (ret == NULL) {
833	xmlRegexpErrMemory(ctxt, "copying atom");
834	return(NULL);
835    }
836    memset(ret, 0, sizeof(xmlRegAtom));
837    ret->type = atom->type;
838    ret->quant = atom->quant;
839    ret->min = atom->min;
840    ret->max = atom->max;
841    if (atom->nbRanges > 0) {
842        int i;
843
844        ret->ranges = (xmlRegRangePtr *) xmlMalloc(sizeof(xmlRegRangePtr) *
845	                                           atom->nbRanges);
846	if (ret->ranges == NULL) {
847	    xmlRegexpErrMemory(ctxt, "copying atom");
848	    goto error;
849	}
850	for (i = 0;i < atom->nbRanges;i++) {
851	    ret->ranges[i] = xmlRegCopyRange(ctxt, atom->ranges[i]);
852	    if (ret->ranges[i] == NULL)
853	        goto error;
854	    ret->nbRanges = i + 1;
855	}
856    }
857    return(ret);
858
859error:
860    xmlRegFreeAtom(ret);
861    return(NULL);
862}
863
864static xmlRegStatePtr
865xmlRegNewState(xmlRegParserCtxtPtr ctxt) {
866    xmlRegStatePtr ret;
867
868    ret = (xmlRegStatePtr) xmlMalloc(sizeof(xmlRegState));
869    if (ret == NULL) {
870	xmlRegexpErrMemory(ctxt, "allocating state");
871	return(NULL);
872    }
873    memset(ret, 0, sizeof(xmlRegState));
874    ret->type = XML_REGEXP_TRANS_STATE;
875    ret->mark = XML_REGEXP_MARK_NORMAL;
876    return(ret);
877}
878
879/**
880 * xmlRegFreeState:
881 * @state:  the regexp state
882 *
883 * Free a regexp state
884 */
885static void
886xmlRegFreeState(xmlRegStatePtr state) {
887    if (state == NULL)
888	return;
889
890    if (state->trans != NULL)
891	xmlFree(state->trans);
892    if (state->transTo != NULL)
893	xmlFree(state->transTo);
894    xmlFree(state);
895}
896
897/**
898 * xmlRegFreeParserCtxt:
899 * @ctxt:  the regexp parser context
900 *
901 * Free a regexp parser context
902 */
903static void
904xmlRegFreeParserCtxt(xmlRegParserCtxtPtr ctxt) {
905    int i;
906    if (ctxt == NULL)
907	return;
908
909    if (ctxt->string != NULL)
910	xmlFree(ctxt->string);
911    if (ctxt->states != NULL) {
912	for (i = 0;i < ctxt->nbStates;i++)
913	    xmlRegFreeState(ctxt->states[i]);
914	xmlFree(ctxt->states);
915    }
916    if (ctxt->atoms != NULL) {
917	for (i = 0;i < ctxt->nbAtoms;i++)
918	    xmlRegFreeAtom(ctxt->atoms[i]);
919	xmlFree(ctxt->atoms);
920    }
921    if (ctxt->counters != NULL)
922	xmlFree(ctxt->counters);
923    xmlFree(ctxt);
924}
925
926/************************************************************************
927 * 									*
928 * 			Display of Data structures			*
929 * 									*
930 ************************************************************************/
931
932static void
933xmlRegPrintAtomType(FILE *output, xmlRegAtomType type) {
934    switch (type) {
935        case XML_REGEXP_EPSILON:
936	    fprintf(output, "epsilon "); break;
937        case XML_REGEXP_CHARVAL:
938	    fprintf(output, "charval "); break;
939        case XML_REGEXP_RANGES:
940	    fprintf(output, "ranges "); break;
941        case XML_REGEXP_SUBREG:
942	    fprintf(output, "subexpr "); break;
943        case XML_REGEXP_STRING:
944	    fprintf(output, "string "); break;
945        case XML_REGEXP_ANYCHAR:
946	    fprintf(output, "anychar "); break;
947        case XML_REGEXP_ANYSPACE:
948	    fprintf(output, "anyspace "); break;
949        case XML_REGEXP_NOTSPACE:
950	    fprintf(output, "notspace "); break;
951        case XML_REGEXP_INITNAME:
952	    fprintf(output, "initname "); break;
953        case XML_REGEXP_NOTINITNAME:
954	    fprintf(output, "notinitname "); break;
955        case XML_REGEXP_NAMECHAR:
956	    fprintf(output, "namechar "); break;
957        case XML_REGEXP_NOTNAMECHAR:
958	    fprintf(output, "notnamechar "); break;
959        case XML_REGEXP_DECIMAL:
960	    fprintf(output, "decimal "); break;
961        case XML_REGEXP_NOTDECIMAL:
962	    fprintf(output, "notdecimal "); break;
963        case XML_REGEXP_REALCHAR:
964	    fprintf(output, "realchar "); break;
965        case XML_REGEXP_NOTREALCHAR:
966	    fprintf(output, "notrealchar "); break;
967        case XML_REGEXP_LETTER:
968            fprintf(output, "LETTER "); break;
969        case XML_REGEXP_LETTER_UPPERCASE:
970            fprintf(output, "LETTER_UPPERCASE "); break;
971        case XML_REGEXP_LETTER_LOWERCASE:
972            fprintf(output, "LETTER_LOWERCASE "); break;
973        case XML_REGEXP_LETTER_TITLECASE:
974            fprintf(output, "LETTER_TITLECASE "); break;
975        case XML_REGEXP_LETTER_MODIFIER:
976            fprintf(output, "LETTER_MODIFIER "); break;
977        case XML_REGEXP_LETTER_OTHERS:
978            fprintf(output, "LETTER_OTHERS "); break;
979        case XML_REGEXP_MARK:
980            fprintf(output, "MARK "); break;
981        case XML_REGEXP_MARK_NONSPACING:
982            fprintf(output, "MARK_NONSPACING "); break;
983        case XML_REGEXP_MARK_SPACECOMBINING:
984            fprintf(output, "MARK_SPACECOMBINING "); break;
985        case XML_REGEXP_MARK_ENCLOSING:
986            fprintf(output, "MARK_ENCLOSING "); break;
987        case XML_REGEXP_NUMBER:
988            fprintf(output, "NUMBER "); break;
989        case XML_REGEXP_NUMBER_DECIMAL:
990            fprintf(output, "NUMBER_DECIMAL "); break;
991        case XML_REGEXP_NUMBER_LETTER:
992            fprintf(output, "NUMBER_LETTER "); break;
993        case XML_REGEXP_NUMBER_OTHERS:
994            fprintf(output, "NUMBER_OTHERS "); break;
995        case XML_REGEXP_PUNCT:
996            fprintf(output, "PUNCT "); break;
997        case XML_REGEXP_PUNCT_CONNECTOR:
998            fprintf(output, "PUNCT_CONNECTOR "); break;
999        case XML_REGEXP_PUNCT_DASH:
1000            fprintf(output, "PUNCT_DASH "); break;
1001        case XML_REGEXP_PUNCT_OPEN:
1002            fprintf(output, "PUNCT_OPEN "); break;
1003        case XML_REGEXP_PUNCT_CLOSE:
1004            fprintf(output, "PUNCT_CLOSE "); break;
1005        case XML_REGEXP_PUNCT_INITQUOTE:
1006            fprintf(output, "PUNCT_INITQUOTE "); break;
1007        case XML_REGEXP_PUNCT_FINQUOTE:
1008            fprintf(output, "PUNCT_FINQUOTE "); break;
1009        case XML_REGEXP_PUNCT_OTHERS:
1010            fprintf(output, "PUNCT_OTHERS "); break;
1011        case XML_REGEXP_SEPAR:
1012            fprintf(output, "SEPAR "); break;
1013        case XML_REGEXP_SEPAR_SPACE:
1014            fprintf(output, "SEPAR_SPACE "); break;
1015        case XML_REGEXP_SEPAR_LINE:
1016            fprintf(output, "SEPAR_LINE "); break;
1017        case XML_REGEXP_SEPAR_PARA:
1018            fprintf(output, "SEPAR_PARA "); break;
1019        case XML_REGEXP_SYMBOL:
1020            fprintf(output, "SYMBOL "); break;
1021        case XML_REGEXP_SYMBOL_MATH:
1022            fprintf(output, "SYMBOL_MATH "); break;
1023        case XML_REGEXP_SYMBOL_CURRENCY:
1024            fprintf(output, "SYMBOL_CURRENCY "); break;
1025        case XML_REGEXP_SYMBOL_MODIFIER:
1026            fprintf(output, "SYMBOL_MODIFIER "); break;
1027        case XML_REGEXP_SYMBOL_OTHERS:
1028            fprintf(output, "SYMBOL_OTHERS "); break;
1029        case XML_REGEXP_OTHER:
1030            fprintf(output, "OTHER "); break;
1031        case XML_REGEXP_OTHER_CONTROL:
1032            fprintf(output, "OTHER_CONTROL "); break;
1033        case XML_REGEXP_OTHER_FORMAT:
1034            fprintf(output, "OTHER_FORMAT "); break;
1035        case XML_REGEXP_OTHER_PRIVATE:
1036            fprintf(output, "OTHER_PRIVATE "); break;
1037        case XML_REGEXP_OTHER_NA:
1038            fprintf(output, "OTHER_NA "); break;
1039        case XML_REGEXP_BLOCK_NAME:
1040	    fprintf(output, "BLOCK "); break;
1041    }
1042}
1043
1044static void
1045xmlRegPrintQuantType(FILE *output, xmlRegQuantType type) {
1046    switch (type) {
1047        case XML_REGEXP_QUANT_EPSILON:
1048	    fprintf(output, "epsilon "); break;
1049        case XML_REGEXP_QUANT_ONCE:
1050	    fprintf(output, "once "); break;
1051        case XML_REGEXP_QUANT_OPT:
1052	    fprintf(output, "? "); break;
1053        case XML_REGEXP_QUANT_MULT:
1054	    fprintf(output, "* "); break;
1055        case XML_REGEXP_QUANT_PLUS:
1056	    fprintf(output, "+ "); break;
1057	case XML_REGEXP_QUANT_RANGE:
1058	    fprintf(output, "range "); break;
1059	case XML_REGEXP_QUANT_ONCEONLY:
1060	    fprintf(output, "onceonly "); break;
1061	case XML_REGEXP_QUANT_ALL:
1062	    fprintf(output, "all "); break;
1063    }
1064}
1065static void
1066xmlRegPrintRange(FILE *output, xmlRegRangePtr range) {
1067    fprintf(output, "  range: ");
1068    if (range->neg)
1069	fprintf(output, "negative ");
1070    xmlRegPrintAtomType(output, range->type);
1071    fprintf(output, "%c - %c\n", range->start, range->end);
1072}
1073
1074static void
1075xmlRegPrintAtom(FILE *output, xmlRegAtomPtr atom) {
1076    fprintf(output, " atom: ");
1077    if (atom == NULL) {
1078	fprintf(output, "NULL\n");
1079	return;
1080    }
1081    if (atom->neg)
1082        fprintf(output, "not ");
1083    xmlRegPrintAtomType(output, atom->type);
1084    xmlRegPrintQuantType(output, atom->quant);
1085    if (atom->quant == XML_REGEXP_QUANT_RANGE)
1086	fprintf(output, "%d-%d ", atom->min, atom->max);
1087    if (atom->type == XML_REGEXP_STRING)
1088	fprintf(output, "'%s' ", (char *) atom->valuep);
1089    if (atom->type == XML_REGEXP_CHARVAL)
1090	fprintf(output, "char %c\n", atom->codepoint);
1091    else if (atom->type == XML_REGEXP_RANGES) {
1092	int i;
1093	fprintf(output, "%d entries\n", atom->nbRanges);
1094	for (i = 0; i < atom->nbRanges;i++)
1095	    xmlRegPrintRange(output, atom->ranges[i]);
1096    } else if (atom->type == XML_REGEXP_SUBREG) {
1097	fprintf(output, "start %d end %d\n", atom->start->no, atom->stop->no);
1098    } else {
1099	fprintf(output, "\n");
1100    }
1101}
1102
1103static void
1104xmlRegPrintTrans(FILE *output, xmlRegTransPtr trans) {
1105    fprintf(output, "  trans: ");
1106    if (trans == NULL) {
1107	fprintf(output, "NULL\n");
1108	return;
1109    }
1110    if (trans->to < 0) {
1111	fprintf(output, "removed\n");
1112	return;
1113    }
1114    if (trans->nd != 0) {
1115	if (trans->nd == 2)
1116	    fprintf(output, "last not determinist, ");
1117	else
1118	    fprintf(output, "not determinist, ");
1119    }
1120    if (trans->counter >= 0) {
1121	fprintf(output, "counted %d, ", trans->counter);
1122    }
1123    if (trans->count == REGEXP_ALL_COUNTER) {
1124	fprintf(output, "all transition, ");
1125    } else if (trans->count >= 0) {
1126	fprintf(output, "count based %d, ", trans->count);
1127    }
1128    if (trans->atom == NULL) {
1129	fprintf(output, "epsilon to %d\n", trans->to);
1130	return;
1131    }
1132    if (trans->atom->type == XML_REGEXP_CHARVAL)
1133	fprintf(output, "char %c ", trans->atom->codepoint);
1134    fprintf(output, "atom %d, to %d\n", trans->atom->no, trans->to);
1135}
1136
1137static void
1138xmlRegPrintState(FILE *output, xmlRegStatePtr state) {
1139    int i;
1140
1141    fprintf(output, " state: ");
1142    if (state == NULL) {
1143	fprintf(output, "NULL\n");
1144	return;
1145    }
1146    if (state->type == XML_REGEXP_START_STATE)
1147	fprintf(output, "START ");
1148    if (state->type == XML_REGEXP_FINAL_STATE)
1149	fprintf(output, "FINAL ");
1150
1151    fprintf(output, "%d, %d transitions:\n", state->no, state->nbTrans);
1152    for (i = 0;i < state->nbTrans; i++) {
1153	xmlRegPrintTrans(output, &(state->trans[i]));
1154    }
1155}
1156
1157#ifdef DEBUG_REGEXP_GRAPH
1158static void
1159xmlRegPrintCtxt(FILE *output, xmlRegParserCtxtPtr ctxt) {
1160    int i;
1161
1162    fprintf(output, " ctxt: ");
1163    if (ctxt == NULL) {
1164	fprintf(output, "NULL\n");
1165	return;
1166    }
1167    fprintf(output, "'%s' ", ctxt->string);
1168    if (ctxt->error)
1169	fprintf(output, "error ");
1170    if (ctxt->neg)
1171	fprintf(output, "neg ");
1172    fprintf(output, "\n");
1173    fprintf(output, "%d atoms:\n", ctxt->nbAtoms);
1174    for (i = 0;i < ctxt->nbAtoms; i++) {
1175	fprintf(output, " %02d ", i);
1176	xmlRegPrintAtom(output, ctxt->atoms[i]);
1177    }
1178    if (ctxt->atom != NULL) {
1179	fprintf(output, "current atom:\n");
1180	xmlRegPrintAtom(output, ctxt->atom);
1181    }
1182    fprintf(output, "%d states:", ctxt->nbStates);
1183    if (ctxt->start != NULL)
1184	fprintf(output, " start: %d", ctxt->start->no);
1185    if (ctxt->end != NULL)
1186	fprintf(output, " end: %d", ctxt->end->no);
1187    fprintf(output, "\n");
1188    for (i = 0;i < ctxt->nbStates; i++) {
1189	xmlRegPrintState(output, ctxt->states[i]);
1190    }
1191    fprintf(output, "%d counters:\n", ctxt->nbCounters);
1192    for (i = 0;i < ctxt->nbCounters; i++) {
1193	fprintf(output, " %d: min %d max %d\n", i, ctxt->counters[i].min,
1194		                                ctxt->counters[i].max);
1195    }
1196}
1197#endif
1198
1199/************************************************************************
1200 * 									*
1201 *		 Finite Automata structures manipulations		*
1202 * 									*
1203 ************************************************************************/
1204
1205static void
1206xmlRegAtomAddRange(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom,
1207	           int neg, xmlRegAtomType type, int start, int end,
1208		   xmlChar *blockName) {
1209    xmlRegRangePtr range;
1210
1211    if (atom == NULL) {
1212	ERROR("add range: atom is NULL");
1213	return;
1214    }
1215    if (atom->type != XML_REGEXP_RANGES) {
1216	ERROR("add range: atom is not ranges");
1217	return;
1218    }
1219    if (atom->maxRanges == 0) {
1220	atom->maxRanges = 4;
1221	atom->ranges = (xmlRegRangePtr *) xmlMalloc(atom->maxRanges *
1222		                             sizeof(xmlRegRangePtr));
1223	if (atom->ranges == NULL) {
1224	    xmlRegexpErrMemory(ctxt, "adding ranges");
1225	    atom->maxRanges = 0;
1226	    return;
1227	}
1228    } else if (atom->nbRanges >= atom->maxRanges) {
1229	xmlRegRangePtr *tmp;
1230	atom->maxRanges *= 2;
1231	tmp = (xmlRegRangePtr *) xmlRealloc(atom->ranges, atom->maxRanges *
1232		                             sizeof(xmlRegRangePtr));
1233	if (tmp == NULL) {
1234	    xmlRegexpErrMemory(ctxt, "adding ranges");
1235	    atom->maxRanges /= 2;
1236	    return;
1237	}
1238	atom->ranges = tmp;
1239    }
1240    range = xmlRegNewRange(ctxt, neg, type, start, end);
1241    if (range == NULL)
1242	return;
1243    range->blockName = blockName;
1244    atom->ranges[atom->nbRanges++] = range;
1245
1246}
1247
1248static int
1249xmlRegGetCounter(xmlRegParserCtxtPtr ctxt) {
1250    if (ctxt->maxCounters == 0) {
1251	ctxt->maxCounters = 4;
1252	ctxt->counters = (xmlRegCounter *) xmlMalloc(ctxt->maxCounters *
1253		                             sizeof(xmlRegCounter));
1254	if (ctxt->counters == NULL) {
1255	    xmlRegexpErrMemory(ctxt, "allocating counter");
1256	    ctxt->maxCounters = 0;
1257	    return(-1);
1258	}
1259    } else if (ctxt->nbCounters >= ctxt->maxCounters) {
1260	xmlRegCounter *tmp;
1261	ctxt->maxCounters *= 2;
1262	tmp = (xmlRegCounter *) xmlRealloc(ctxt->counters, ctxt->maxCounters *
1263		                           sizeof(xmlRegCounter));
1264	if (tmp == NULL) {
1265	    xmlRegexpErrMemory(ctxt, "allocating counter");
1266	    ctxt->maxCounters /= 2;
1267	    return(-1);
1268	}
1269	ctxt->counters = tmp;
1270    }
1271    ctxt->counters[ctxt->nbCounters].min = -1;
1272    ctxt->counters[ctxt->nbCounters].max = -1;
1273    return(ctxt->nbCounters++);
1274}
1275
1276static int
1277xmlRegAtomPush(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {
1278    if (atom == NULL) {
1279	ERROR("atom push: atom is NULL");
1280	return(-1);
1281    }
1282    if (ctxt->maxAtoms == 0) {
1283	ctxt->maxAtoms = 4;
1284	ctxt->atoms = (xmlRegAtomPtr *) xmlMalloc(ctxt->maxAtoms *
1285		                             sizeof(xmlRegAtomPtr));
1286	if (ctxt->atoms == NULL) {
1287	    xmlRegexpErrMemory(ctxt, "pushing atom");
1288	    ctxt->maxAtoms = 0;
1289	    return(-1);
1290	}
1291    } else if (ctxt->nbAtoms >= ctxt->maxAtoms) {
1292	xmlRegAtomPtr *tmp;
1293	ctxt->maxAtoms *= 2;
1294	tmp = (xmlRegAtomPtr *) xmlRealloc(ctxt->atoms, ctxt->maxAtoms *
1295		                             sizeof(xmlRegAtomPtr));
1296	if (tmp == NULL) {
1297	    xmlRegexpErrMemory(ctxt, "allocating counter");
1298	    ctxt->maxAtoms /= 2;
1299	    return(-1);
1300	}
1301	ctxt->atoms = tmp;
1302    }
1303    atom->no = ctxt->nbAtoms;
1304    ctxt->atoms[ctxt->nbAtoms++] = atom;
1305    return(0);
1306}
1307
1308static void
1309xmlRegStateAddTransTo(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr target,
1310                      int from) {
1311    if (target->maxTransTo == 0) {
1312	target->maxTransTo = 8;
1313	target->transTo = (int *) xmlMalloc(target->maxTransTo *
1314		                             sizeof(int));
1315	if (target->transTo == NULL) {
1316	    xmlRegexpErrMemory(ctxt, "adding transition");
1317	    target->maxTransTo = 0;
1318	    return;
1319	}
1320    } else if (target->nbTransTo >= target->maxTransTo) {
1321	int *tmp;
1322	target->maxTransTo *= 2;
1323	tmp = (int *) xmlRealloc(target->transTo, target->maxTransTo *
1324		                             sizeof(int));
1325	if (tmp == NULL) {
1326	    xmlRegexpErrMemory(ctxt, "adding transition");
1327	    target->maxTransTo /= 2;
1328	    return;
1329	}
1330	target->transTo = tmp;
1331    }
1332    target->transTo[target->nbTransTo] = from;
1333    target->nbTransTo++;
1334}
1335
1336static void
1337xmlRegStateAddTrans(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
1338	            xmlRegAtomPtr atom, xmlRegStatePtr target,
1339		    int counter, int count) {
1340
1341    int nrtrans;
1342
1343    if (state == NULL) {
1344	ERROR("add state: state is NULL");
1345	return;
1346    }
1347    if (target == NULL) {
1348	ERROR("add state: target is NULL");
1349	return;
1350    }
1351    /*
1352     * Other routines follow the philosophy 'When in doubt, add a transition'
1353     * so we check here whether such a transition is already present and, if
1354     * so, silently ignore this request.
1355     */
1356
1357    for (nrtrans = state->nbTrans - 1; nrtrans >= 0; nrtrans--) {
1358	xmlRegTransPtr trans = &(state->trans[nrtrans]);
1359	if ((trans->atom == atom) &&
1360	    (trans->to == target->no) &&
1361	    (trans->counter == counter) &&
1362	    (trans->count == count)) {
1363#ifdef DEBUG_REGEXP_GRAPH
1364	    printf("Ignoring duplicate transition from %d to %d\n",
1365		    state->no, target->no);
1366#endif
1367	    return;
1368	}
1369    }
1370
1371    if (state->maxTrans == 0) {
1372	state->maxTrans = 8;
1373	state->trans = (xmlRegTrans *) xmlMalloc(state->maxTrans *
1374		                             sizeof(xmlRegTrans));
1375	if (state->trans == NULL) {
1376	    xmlRegexpErrMemory(ctxt, "adding transition");
1377	    state->maxTrans = 0;
1378	    return;
1379	}
1380    } else if (state->nbTrans >= state->maxTrans) {
1381	xmlRegTrans *tmp;
1382	state->maxTrans *= 2;
1383	tmp = (xmlRegTrans *) xmlRealloc(state->trans, state->maxTrans *
1384		                             sizeof(xmlRegTrans));
1385	if (tmp == NULL) {
1386	    xmlRegexpErrMemory(ctxt, "adding transition");
1387	    state->maxTrans /= 2;
1388	    return;
1389	}
1390	state->trans = tmp;
1391    }
1392#ifdef DEBUG_REGEXP_GRAPH
1393    printf("Add trans from %d to %d ", state->no, target->no);
1394    if (count == REGEXP_ALL_COUNTER)
1395	printf("all transition\n");
1396    else if (count >= 0)
1397	printf("count based %d\n", count);
1398    else if (counter >= 0)
1399	printf("counted %d\n", counter);
1400    else if (atom == NULL)
1401	printf("epsilon transition\n");
1402    else if (atom != NULL)
1403        xmlRegPrintAtom(stdout, atom);
1404#endif
1405
1406    state->trans[state->nbTrans].atom = atom;
1407    state->trans[state->nbTrans].to = target->no;
1408    state->trans[state->nbTrans].counter = counter;
1409    state->trans[state->nbTrans].count = count;
1410    state->trans[state->nbTrans].nd = 0;
1411    state->nbTrans++;
1412    xmlRegStateAddTransTo(ctxt, target, state->no);
1413}
1414
1415static int
1416xmlRegStatePush(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) {
1417    if (state == NULL) return(-1);
1418    if (ctxt->maxStates == 0) {
1419	ctxt->maxStates = 4;
1420	ctxt->states = (xmlRegStatePtr *) xmlMalloc(ctxt->maxStates *
1421		                             sizeof(xmlRegStatePtr));
1422	if (ctxt->states == NULL) {
1423	    xmlRegexpErrMemory(ctxt, "adding state");
1424	    ctxt->maxStates = 0;
1425	    return(-1);
1426	}
1427    } else if (ctxt->nbStates >= ctxt->maxStates) {
1428	xmlRegStatePtr *tmp;
1429	ctxt->maxStates *= 2;
1430	tmp = (xmlRegStatePtr *) xmlRealloc(ctxt->states, ctxt->maxStates *
1431		                             sizeof(xmlRegStatePtr));
1432	if (tmp == NULL) {
1433	    xmlRegexpErrMemory(ctxt, "adding state");
1434	    ctxt->maxStates /= 2;
1435	    return(-1);
1436	}
1437	ctxt->states = tmp;
1438    }
1439    state->no = ctxt->nbStates;
1440    ctxt->states[ctxt->nbStates++] = state;
1441    return(0);
1442}
1443
1444/**
1445 * xmlFAGenerateAllTransition:
1446 * @ctxt:  a regexp parser context
1447 * @from:  the from state
1448 * @to:  the target state or NULL for building a new one
1449 * @lax:
1450 *
1451 */
1452static void
1453xmlFAGenerateAllTransition(xmlRegParserCtxtPtr ctxt,
1454			   xmlRegStatePtr from, xmlRegStatePtr to,
1455			   int lax) {
1456    if (to == NULL) {
1457	to = xmlRegNewState(ctxt);
1458	xmlRegStatePush(ctxt, to);
1459	ctxt->state = to;
1460    }
1461    if (lax)
1462	xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_LAX_COUNTER);
1463    else
1464	xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_COUNTER);
1465}
1466
1467/**
1468 * xmlFAGenerateEpsilonTransition:
1469 * @ctxt:  a regexp parser context
1470 * @from:  the from state
1471 * @to:  the target state or NULL for building a new one
1472 *
1473 */
1474static void
1475xmlFAGenerateEpsilonTransition(xmlRegParserCtxtPtr ctxt,
1476			       xmlRegStatePtr from, xmlRegStatePtr to) {
1477    if (to == NULL) {
1478	to = xmlRegNewState(ctxt);
1479	xmlRegStatePush(ctxt, to);
1480	ctxt->state = to;
1481    }
1482    xmlRegStateAddTrans(ctxt, from, NULL, to, -1, -1);
1483}
1484
1485/**
1486 * xmlFAGenerateCountedEpsilonTransition:
1487 * @ctxt:  a regexp parser context
1488 * @from:  the from state
1489 * @to:  the target state or NULL for building a new one
1490 * counter:  the counter for that transition
1491 *
1492 */
1493static void
1494xmlFAGenerateCountedEpsilonTransition(xmlRegParserCtxtPtr ctxt,
1495	    xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
1496    if (to == NULL) {
1497	to = xmlRegNewState(ctxt);
1498	xmlRegStatePush(ctxt, to);
1499	ctxt->state = to;
1500    }
1501    xmlRegStateAddTrans(ctxt, from, NULL, to, counter, -1);
1502}
1503
1504/**
1505 * xmlFAGenerateCountedTransition:
1506 * @ctxt:  a regexp parser context
1507 * @from:  the from state
1508 * @to:  the target state or NULL for building a new one
1509 * counter:  the counter for that transition
1510 *
1511 */
1512static void
1513xmlFAGenerateCountedTransition(xmlRegParserCtxtPtr ctxt,
1514	    xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
1515    if (to == NULL) {
1516	to = xmlRegNewState(ctxt);
1517	xmlRegStatePush(ctxt, to);
1518	ctxt->state = to;
1519    }
1520    xmlRegStateAddTrans(ctxt, from, NULL, to, -1, counter);
1521}
1522
1523/**
1524 * xmlFAGenerateTransitions:
1525 * @ctxt:  a regexp parser context
1526 * @from:  the from state
1527 * @to:  the target state or NULL for building a new one
1528 * @atom:  the atom generating the transition
1529 *
1530 * Returns 0 if success and -1 in case of error.
1531 */
1532static int
1533xmlFAGenerateTransitions(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from,
1534	                 xmlRegStatePtr to, xmlRegAtomPtr atom) {
1535    xmlRegStatePtr end;
1536
1537    if (atom == NULL) {
1538	ERROR("genrate transition: atom == NULL");
1539	return(-1);
1540    }
1541    if (atom->type == XML_REGEXP_SUBREG) {
1542	/*
1543	 * this is a subexpression handling one should not need to
1544	 * create a new node except for XML_REGEXP_QUANT_RANGE.
1545	 */
1546	if (xmlRegAtomPush(ctxt, atom) < 0) {
1547	    return(-1);
1548	}
1549	if ((to != NULL) && (atom->stop != to) &&
1550	    (atom->quant != XML_REGEXP_QUANT_RANGE)) {
1551	    /*
1552	     * Generate an epsilon transition to link to the target
1553	     */
1554	    xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);
1555#ifdef DV
1556	} else if ((to == NULL) && (atom->quant != XML_REGEXP_QUANT_RANGE) &&
1557		   (atom->quant != XML_REGEXP_QUANT_ONCE)) {
1558	    to = xmlRegNewState(ctxt);
1559	    xmlRegStatePush(ctxt, to);
1560	    ctxt->state = to;
1561	    xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);
1562#endif
1563	}
1564	switch (atom->quant) {
1565	    case XML_REGEXP_QUANT_OPT:
1566		atom->quant = XML_REGEXP_QUANT_ONCE;
1567		/*
1568		 * transition done to the state after end of atom.
1569		 *      1. set transition from atom start to new state
1570		 *      2. set transition from atom end to this state.
1571		 */
1572		xmlFAGenerateEpsilonTransition(ctxt, atom->start, 0);
1573		xmlFAGenerateEpsilonTransition(ctxt, atom->stop, ctxt->state);
1574		break;
1575	    case XML_REGEXP_QUANT_MULT:
1576		atom->quant = XML_REGEXP_QUANT_ONCE;
1577		xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);
1578		xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1579		break;
1580	    case XML_REGEXP_QUANT_PLUS:
1581		atom->quant = XML_REGEXP_QUANT_ONCE;
1582		xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1583		break;
1584	    case XML_REGEXP_QUANT_RANGE: {
1585		int counter;
1586		xmlRegStatePtr inter, newstate;
1587
1588		/*
1589		 * create the final state now if needed
1590		 */
1591		if (to != NULL) {
1592		    newstate = to;
1593		} else {
1594		    newstate = xmlRegNewState(ctxt);
1595		    xmlRegStatePush(ctxt, newstate);
1596		}
1597
1598		/*
1599		 * The principle here is to use counted transition
1600		 * to avoid explosion in the number of states in the
1601		 * graph. This is clearly more complex but should not
1602		 * be exploitable at runtime.
1603		 */
1604		if ((atom->min == 0) && (atom->start0 == NULL)) {
1605		    xmlRegAtomPtr copy;
1606		    /*
1607		     * duplicate a transition based on atom to count next
1608		     * occurences after 1. We cannot loop to atom->start
1609		     * directly because we need an epsilon transition to
1610		     * newstate.
1611		     */
1612		     /* ???? For some reason it seems we never reach that
1613		        case, I suppose this got optimized out before when
1614			building the automata */
1615		    copy = xmlRegCopyAtom(ctxt, atom);
1616		    if (copy == NULL)
1617		        return(-1);
1618		    copy->quant = XML_REGEXP_QUANT_ONCE;
1619		    copy->min = 0;
1620		    copy->max = 0;
1621
1622		    if (xmlFAGenerateTransitions(ctxt, atom->start, NULL, copy)
1623		        < 0)
1624			return(-1);
1625		    inter = ctxt->state;
1626		    counter = xmlRegGetCounter(ctxt);
1627		    ctxt->counters[counter].min = atom->min - 1;
1628		    ctxt->counters[counter].max = atom->max - 1;
1629		    /* count the number of times we see it again */
1630		    xmlFAGenerateCountedEpsilonTransition(ctxt, inter,
1631						   atom->stop, counter);
1632		    /* allow a way out based on the count */
1633		    xmlFAGenerateCountedTransition(ctxt, inter,
1634			                           newstate, counter);
1635		    /* and also allow a direct exit for 0 */
1636		    xmlFAGenerateEpsilonTransition(ctxt, atom->start,
1637		                                   newstate);
1638		} else {
1639		    /*
1640		     * either we need the atom at least once or there
1641		     * is an atom->start0 allowing to easilly plug the
1642		     * epsilon transition.
1643		     */
1644		    counter = xmlRegGetCounter(ctxt);
1645		    ctxt->counters[counter].min = atom->min - 1;
1646		    ctxt->counters[counter].max = atom->max - 1;
1647		    /* count the number of times we see it again */
1648		    xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop,
1649						   atom->start, counter);
1650		    /* allow a way out based on the count */
1651		    xmlFAGenerateCountedTransition(ctxt, atom->stop,
1652			                           newstate, counter);
1653		    /* and if needed allow a direct exit for 0 */
1654		    if (atom->min == 0)
1655			xmlFAGenerateEpsilonTransition(ctxt, atom->start0,
1656						       newstate);
1657
1658		}
1659		atom->min = 0;
1660		atom->max = 0;
1661		atom->quant = XML_REGEXP_QUANT_ONCE;
1662		ctxt->state = newstate;
1663	    }
1664	    default:
1665		break;
1666	}
1667	return(0);
1668    }
1669    if ((atom->min == 0) && (atom->max == 0) &&
1670               (atom->quant == XML_REGEXP_QUANT_RANGE)) {
1671        /*
1672	 * we can discard the atom and generate an epsilon transition instead
1673	 */
1674	if (to == NULL) {
1675	    to = xmlRegNewState(ctxt);
1676	    if (to != NULL)
1677		xmlRegStatePush(ctxt, to);
1678	    else {
1679		return(-1);
1680	    }
1681	}
1682	xmlFAGenerateEpsilonTransition(ctxt, from, to);
1683	ctxt->state = to;
1684	xmlRegFreeAtom(atom);
1685	return(0);
1686    }
1687    if (to == NULL) {
1688	to = xmlRegNewState(ctxt);
1689	if (to != NULL)
1690	    xmlRegStatePush(ctxt, to);
1691	else {
1692	    return(-1);
1693	}
1694    }
1695    end = to;
1696    if ((atom->quant == XML_REGEXP_QUANT_MULT) ||
1697        (atom->quant == XML_REGEXP_QUANT_PLUS)) {
1698	/*
1699	 * Do not pollute the target state by adding transitions from
1700	 * it as it is likely to be the shared target of multiple branches.
1701	 * So isolate with an epsilon transition.
1702	 */
1703        xmlRegStatePtr tmp;
1704
1705	tmp = xmlRegNewState(ctxt);
1706	if (tmp != NULL)
1707	    xmlRegStatePush(ctxt, tmp);
1708	else {
1709	    return(-1);
1710	}
1711	xmlFAGenerateEpsilonTransition(ctxt, tmp, to);
1712	to = tmp;
1713    }
1714    if (xmlRegAtomPush(ctxt, atom) < 0) {
1715	return(-1);
1716    }
1717    xmlRegStateAddTrans(ctxt, from, atom, to, -1, -1);
1718    ctxt->state = end;
1719    switch (atom->quant) {
1720	case XML_REGEXP_QUANT_OPT:
1721	    atom->quant = XML_REGEXP_QUANT_ONCE;
1722	    xmlFAGenerateEpsilonTransition(ctxt, from, to);
1723	    break;
1724	case XML_REGEXP_QUANT_MULT:
1725	    atom->quant = XML_REGEXP_QUANT_ONCE;
1726	    xmlFAGenerateEpsilonTransition(ctxt, from, to);
1727	    xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1728	    break;
1729	case XML_REGEXP_QUANT_PLUS:
1730	    atom->quant = XML_REGEXP_QUANT_ONCE;
1731	    xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1732	    break;
1733	case XML_REGEXP_QUANT_RANGE:
1734#if DV_test
1735	    if (atom->min == 0) {
1736		xmlFAGenerateEpsilonTransition(ctxt, from, to);
1737	    }
1738#endif
1739	    break;
1740	default:
1741	    break;
1742    }
1743    return(0);
1744}
1745
1746/**
1747 * xmlFAReduceEpsilonTransitions:
1748 * @ctxt:  a regexp parser context
1749 * @fromnr:  the from state
1750 * @tonr:  the to state
1751 * @counter:  should that transition be associated to a counted
1752 *
1753 */
1754static void
1755xmlFAReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int fromnr,
1756	                      int tonr, int counter) {
1757    int transnr;
1758    xmlRegStatePtr from;
1759    xmlRegStatePtr to;
1760
1761#ifdef DEBUG_REGEXP_GRAPH
1762    printf("xmlFAReduceEpsilonTransitions(%d, %d)\n", fromnr, tonr);
1763#endif
1764    from = ctxt->states[fromnr];
1765    if (from == NULL)
1766	return;
1767    to = ctxt->states[tonr];
1768    if (to == NULL)
1769	return;
1770    if ((to->mark == XML_REGEXP_MARK_START) ||
1771	(to->mark == XML_REGEXP_MARK_VISITED))
1772	return;
1773
1774    to->mark = XML_REGEXP_MARK_VISITED;
1775    if (to->type == XML_REGEXP_FINAL_STATE) {
1776#ifdef DEBUG_REGEXP_GRAPH
1777	printf("State %d is final, so %d becomes final\n", tonr, fromnr);
1778#endif
1779	from->type = XML_REGEXP_FINAL_STATE;
1780    }
1781    for (transnr = 0;transnr < to->nbTrans;transnr++) {
1782        if (to->trans[transnr].to < 0)
1783	    continue;
1784	if (to->trans[transnr].atom == NULL) {
1785	    /*
1786	     * Don't remove counted transitions
1787	     * Don't loop either
1788	     */
1789	    if (to->trans[transnr].to != fromnr) {
1790		if (to->trans[transnr].count >= 0) {
1791		    int newto = to->trans[transnr].to;
1792
1793		    xmlRegStateAddTrans(ctxt, from, NULL,
1794					ctxt->states[newto],
1795					-1, to->trans[transnr].count);
1796		} else {
1797#ifdef DEBUG_REGEXP_GRAPH
1798		    printf("Found epsilon trans %d from %d to %d\n",
1799			   transnr, tonr, to->trans[transnr].to);
1800#endif
1801		    if (to->trans[transnr].counter >= 0) {
1802			xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1803					      to->trans[transnr].to,
1804					      to->trans[transnr].counter);
1805		    } else {
1806			xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1807					      to->trans[transnr].to,
1808					      counter);
1809		    }
1810		}
1811	    }
1812	} else {
1813	    int newto = to->trans[transnr].to;
1814
1815	    if (to->trans[transnr].counter >= 0) {
1816		xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1817				    ctxt->states[newto],
1818				    to->trans[transnr].counter, -1);
1819	    } else {
1820		xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1821				    ctxt->states[newto], counter, -1);
1822	    }
1823	}
1824    }
1825    to->mark = XML_REGEXP_MARK_NORMAL;
1826}
1827
1828/**
1829 * xmlFAEliminateSimpleEpsilonTransitions:
1830 * @ctxt:  a regexp parser context
1831 *
1832 * Eliminating general epsilon transitions can get costly in the general
1833 * algorithm due to the large amount of generated new transitions and
1834 * associated comparisons. However for simple epsilon transition used just
1835 * to separate building blocks when generating the automata this can be
1836 * reduced to state elimination:
1837 *    - if there exists an epsilon from X to Y
1838 *    - if there is no other transition from X
1839 * then X and Y are semantically equivalent and X can be eliminated
1840 * If X is the start state then make Y the start state, else replace the
1841 * target of all transitions to X by transitions to Y.
1842 */
1843static void
1844xmlFAEliminateSimpleEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {
1845    int statenr, i, j, newto;
1846    xmlRegStatePtr state, tmp;
1847
1848    for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1849	state = ctxt->states[statenr];
1850	if (state == NULL)
1851	    continue;
1852	if (state->nbTrans != 1)
1853	    continue;
1854	if (state->type == XML_REGEXP_UNREACH_STATE)
1855	    continue;
1856	/* is the only transition out a basic transition */
1857	if ((state->trans[0].atom == NULL) &&
1858	    (state->trans[0].to >= 0) &&
1859	    (state->trans[0].to != statenr) &&
1860	    (state->trans[0].counter < 0) &&
1861	    (state->trans[0].count < 0)) {
1862	    newto = state->trans[0].to;
1863
1864            if (state->type == XML_REGEXP_START_STATE) {
1865#ifdef DEBUG_REGEXP_GRAPH
1866		printf("Found simple epsilon trans from start %d to %d\n",
1867		       statenr, newto);
1868#endif
1869            } else {
1870#ifdef DEBUG_REGEXP_GRAPH
1871		printf("Found simple epsilon trans from %d to %d\n",
1872		       statenr, newto);
1873#endif
1874	        for (i = 0;i < state->nbTransTo;i++) {
1875		    tmp = ctxt->states[state->transTo[i]];
1876		    for (j = 0;j < tmp->nbTrans;j++) {
1877			if (tmp->trans[j].to == statenr) {
1878#ifdef DEBUG_REGEXP_GRAPH
1879			    printf("Changed transition %d on %d to go to %d\n",
1880				   j, tmp->no, newto);
1881#endif
1882			    tmp->trans[j].to = -1;
1883			    xmlRegStateAddTrans(ctxt, tmp, tmp->trans[j].atom,
1884			    			ctxt->states[newto],
1885					        tmp->trans[j].counter,
1886						tmp->trans[j].count);
1887			}
1888		    }
1889		}
1890		if (state->type == XML_REGEXP_FINAL_STATE)
1891		    ctxt->states[newto]->type = XML_REGEXP_FINAL_STATE;
1892		/* eliminate the transition completely */
1893		state->nbTrans = 0;
1894
1895                state->type = XML_REGEXP_UNREACH_STATE;
1896
1897	    }
1898
1899	}
1900    }
1901}
1902/**
1903 * xmlFAEliminateEpsilonTransitions:
1904 * @ctxt:  a regexp parser context
1905 *
1906 */
1907static void
1908xmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {
1909    int statenr, transnr;
1910    xmlRegStatePtr state;
1911    int has_epsilon;
1912
1913    if (ctxt->states == NULL) return;
1914
1915    /*
1916     * Eliminate simple epsilon transition and the associated unreachable
1917     * states.
1918     */
1919    xmlFAEliminateSimpleEpsilonTransitions(ctxt);
1920    for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1921	state = ctxt->states[statenr];
1922	if ((state != NULL) && (state->type == XML_REGEXP_UNREACH_STATE)) {
1923#ifdef DEBUG_REGEXP_GRAPH
1924	    printf("Removed unreachable state %d\n", statenr);
1925#endif
1926	    xmlRegFreeState(state);
1927	    ctxt->states[statenr] = NULL;
1928	}
1929    }
1930
1931    has_epsilon = 0;
1932
1933    /*
1934     * Build the completed transitions bypassing the epsilons
1935     * Use a marking algorithm to avoid loops
1936     * Mark sink states too.
1937     * Process from the latests states backward to the start when
1938     * there is long cascading epsilon chains this minimize the
1939     * recursions and transition compares when adding the new ones
1940     */
1941    for (statenr = ctxt->nbStates - 1;statenr >= 0;statenr--) {
1942	state = ctxt->states[statenr];
1943	if (state == NULL)
1944	    continue;
1945	if ((state->nbTrans == 0) &&
1946	    (state->type != XML_REGEXP_FINAL_STATE)) {
1947	    state->type = XML_REGEXP_SINK_STATE;
1948	}
1949	for (transnr = 0;transnr < state->nbTrans;transnr++) {
1950	    if ((state->trans[transnr].atom == NULL) &&
1951		(state->trans[transnr].to >= 0)) {
1952		if (state->trans[transnr].to == statenr) {
1953		    state->trans[transnr].to = -1;
1954#ifdef DEBUG_REGEXP_GRAPH
1955		    printf("Removed loopback epsilon trans %d on %d\n",
1956			   transnr, statenr);
1957#endif
1958		} else if (state->trans[transnr].count < 0) {
1959		    int newto = state->trans[transnr].to;
1960
1961#ifdef DEBUG_REGEXP_GRAPH
1962		    printf("Found epsilon trans %d from %d to %d\n",
1963			   transnr, statenr, newto);
1964#endif
1965		    has_epsilon = 1;
1966		    state->trans[transnr].to = -2;
1967		    state->mark = XML_REGEXP_MARK_START;
1968		    xmlFAReduceEpsilonTransitions(ctxt, statenr,
1969				      newto, state->trans[transnr].counter);
1970		    state->mark = XML_REGEXP_MARK_NORMAL;
1971#ifdef DEBUG_REGEXP_GRAPH
1972		} else {
1973		    printf("Found counted transition %d on %d\n",
1974			   transnr, statenr);
1975#endif
1976	        }
1977	    }
1978	}
1979    }
1980    /*
1981     * Eliminate the epsilon transitions
1982     */
1983    if (has_epsilon) {
1984	for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1985	    state = ctxt->states[statenr];
1986	    if (state == NULL)
1987		continue;
1988	    for (transnr = 0;transnr < state->nbTrans;transnr++) {
1989		xmlRegTransPtr trans = &(state->trans[transnr]);
1990		if ((trans->atom == NULL) &&
1991		    (trans->count < 0) &&
1992		    (trans->to >= 0)) {
1993		    trans->to = -1;
1994		}
1995	    }
1996	}
1997    }
1998
1999    /*
2000     * Use this pass to detect unreachable states too
2001     */
2002    for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2003	state = ctxt->states[statenr];
2004	if (state != NULL)
2005	    state->reached = XML_REGEXP_MARK_NORMAL;
2006    }
2007    state = ctxt->states[0];
2008    if (state != NULL)
2009	state->reached = XML_REGEXP_MARK_START;
2010    while (state != NULL) {
2011	xmlRegStatePtr target = NULL;
2012	state->reached = XML_REGEXP_MARK_VISITED;
2013	/*
2014	 * Mark all states reachable from the current reachable state
2015	 */
2016	for (transnr = 0;transnr < state->nbTrans;transnr++) {
2017	    if ((state->trans[transnr].to >= 0) &&
2018		((state->trans[transnr].atom != NULL) ||
2019		 (state->trans[transnr].count >= 0))) {
2020		int newto = state->trans[transnr].to;
2021
2022		if (ctxt->states[newto] == NULL)
2023		    continue;
2024		if (ctxt->states[newto]->reached == XML_REGEXP_MARK_NORMAL) {
2025		    ctxt->states[newto]->reached = XML_REGEXP_MARK_START;
2026		    target = ctxt->states[newto];
2027		}
2028	    }
2029	}
2030
2031	/*
2032	 * find the next accessible state not explored
2033	 */
2034	if (target == NULL) {
2035	    for (statenr = 1;statenr < ctxt->nbStates;statenr++) {
2036		state = ctxt->states[statenr];
2037		if ((state != NULL) && (state->reached ==
2038			XML_REGEXP_MARK_START)) {
2039		    target = state;
2040		    break;
2041		}
2042	    }
2043	}
2044	state = target;
2045    }
2046    for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2047	state = ctxt->states[statenr];
2048	if ((state != NULL) && (state->reached == XML_REGEXP_MARK_NORMAL)) {
2049#ifdef DEBUG_REGEXP_GRAPH
2050	    printf("Removed unreachable state %d\n", statenr);
2051#endif
2052	    xmlRegFreeState(state);
2053	    ctxt->states[statenr] = NULL;
2054	}
2055    }
2056
2057}
2058
2059static int
2060xmlFACompareRanges(xmlRegRangePtr range1, xmlRegRangePtr range2) {
2061    int ret = 0;
2062
2063    if ((range1->type == XML_REGEXP_RANGES) ||
2064        (range2->type == XML_REGEXP_RANGES) ||
2065        (range2->type == XML_REGEXP_SUBREG) ||
2066        (range1->type == XML_REGEXP_SUBREG) ||
2067        (range1->type == XML_REGEXP_STRING) ||
2068        (range2->type == XML_REGEXP_STRING))
2069	return(-1);
2070
2071    /* put them in order */
2072    if (range1->type > range2->type) {
2073        xmlRegRangePtr tmp;
2074
2075	tmp = range1;
2076	range1 = range2;
2077	range2 = tmp;
2078    }
2079    if ((range1->type == XML_REGEXP_ANYCHAR) ||
2080        (range2->type == XML_REGEXP_ANYCHAR)) {
2081	ret = 1;
2082    } else if ((range1->type == XML_REGEXP_EPSILON) ||
2083               (range2->type == XML_REGEXP_EPSILON)) {
2084	return(0);
2085    } else if (range1->type == range2->type) {
2086        if ((range1->type != XML_REGEXP_CHARVAL) ||
2087	    (range1->end < range2->start) ||
2088	    (range2->end < range1->start))
2089	    ret = 1;
2090	else
2091	    ret = 0;
2092    } else if (range1->type == XML_REGEXP_CHARVAL) {
2093        int codepoint;
2094	int neg = 0;
2095
2096	/*
2097	 * just check all codepoints in the range for acceptance,
2098	 * this is usually way cheaper since done only once at
2099	 * compilation than testing over and over at runtime or
2100	 * pushing too many states when evaluating.
2101	 */
2102	if (((range1->neg == 0) && (range2->neg != 0)) ||
2103	    ((range1->neg != 0) && (range2->neg == 0)))
2104	    neg = 1;
2105
2106	for (codepoint = range1->start;codepoint <= range1->end ;codepoint++) {
2107	    ret = xmlRegCheckCharacterRange(range2->type, codepoint,
2108					    0, range2->start, range2->end,
2109					    range2->blockName);
2110	    if (ret < 0)
2111	        return(-1);
2112	    if (((neg == 1) && (ret == 0)) ||
2113	        ((neg == 0) && (ret == 1)))
2114		return(1);
2115	}
2116	return(0);
2117    } else if ((range1->type == XML_REGEXP_BLOCK_NAME) ||
2118               (range2->type == XML_REGEXP_BLOCK_NAME)) {
2119	if (range1->type == range2->type) {
2120	    ret = xmlStrEqual(range1->blockName, range2->blockName);
2121	} else {
2122	    /*
2123	     * comparing a block range with anything else is way
2124	     * too costly, and maintining the table is like too much
2125	     * memory too, so let's force the automata to save state
2126	     * here.
2127	     */
2128	    return(1);
2129	}
2130    } else if ((range1->type < XML_REGEXP_LETTER) ||
2131               (range2->type < XML_REGEXP_LETTER)) {
2132	if ((range1->type == XML_REGEXP_ANYSPACE) &&
2133	    (range2->type == XML_REGEXP_NOTSPACE))
2134	    ret = 0;
2135	else if ((range1->type == XML_REGEXP_INITNAME) &&
2136	         (range2->type == XML_REGEXP_NOTINITNAME))
2137	    ret = 0;
2138	else if ((range1->type == XML_REGEXP_NAMECHAR) &&
2139	         (range2->type == XML_REGEXP_NOTNAMECHAR))
2140	    ret = 0;
2141	else if ((range1->type == XML_REGEXP_DECIMAL) &&
2142	         (range2->type == XML_REGEXP_NOTDECIMAL))
2143	    ret = 0;
2144	else if ((range1->type == XML_REGEXP_REALCHAR) &&
2145	         (range2->type == XML_REGEXP_NOTREALCHAR))
2146	    ret = 0;
2147	else {
2148	    /* same thing to limit complexity */
2149	    return(1);
2150	}
2151    } else {
2152        ret = 0;
2153        /* range1->type < range2->type here */
2154        switch (range1->type) {
2155	    case XML_REGEXP_LETTER:
2156	         /* all disjoint except in the subgroups */
2157	         if ((range2->type == XML_REGEXP_LETTER_UPPERCASE) ||
2158		     (range2->type == XML_REGEXP_LETTER_LOWERCASE) ||
2159		     (range2->type == XML_REGEXP_LETTER_TITLECASE) ||
2160		     (range2->type == XML_REGEXP_LETTER_MODIFIER) ||
2161		     (range2->type == XML_REGEXP_LETTER_OTHERS))
2162		     ret = 1;
2163		 break;
2164	    case XML_REGEXP_MARK:
2165	         if ((range2->type == XML_REGEXP_MARK_NONSPACING) ||
2166		     (range2->type == XML_REGEXP_MARK_SPACECOMBINING) ||
2167		     (range2->type == XML_REGEXP_MARK_ENCLOSING))
2168		     ret = 1;
2169		 break;
2170	    case XML_REGEXP_NUMBER:
2171	         if ((range2->type == XML_REGEXP_NUMBER_DECIMAL) ||
2172		     (range2->type == XML_REGEXP_NUMBER_LETTER) ||
2173		     (range2->type == XML_REGEXP_NUMBER_OTHERS))
2174		     ret = 1;
2175		 break;
2176	    case XML_REGEXP_PUNCT:
2177	         if ((range2->type == XML_REGEXP_PUNCT_CONNECTOR) ||
2178		     (range2->type == XML_REGEXP_PUNCT_DASH) ||
2179		     (range2->type == XML_REGEXP_PUNCT_OPEN) ||
2180		     (range2->type == XML_REGEXP_PUNCT_CLOSE) ||
2181		     (range2->type == XML_REGEXP_PUNCT_INITQUOTE) ||
2182		     (range2->type == XML_REGEXP_PUNCT_FINQUOTE) ||
2183		     (range2->type == XML_REGEXP_PUNCT_OTHERS))
2184		     ret = 1;
2185		 break;
2186	    case XML_REGEXP_SEPAR:
2187	         if ((range2->type == XML_REGEXP_SEPAR_SPACE) ||
2188		     (range2->type == XML_REGEXP_SEPAR_LINE) ||
2189		     (range2->type == XML_REGEXP_SEPAR_PARA))
2190		     ret = 1;
2191		 break;
2192	    case XML_REGEXP_SYMBOL:
2193	         if ((range2->type == XML_REGEXP_SYMBOL_MATH) ||
2194		     (range2->type == XML_REGEXP_SYMBOL_CURRENCY) ||
2195		     (range2->type == XML_REGEXP_SYMBOL_MODIFIER) ||
2196		     (range2->type == XML_REGEXP_SYMBOL_OTHERS))
2197		     ret = 1;
2198		 break;
2199	    case XML_REGEXP_OTHER:
2200	         if ((range2->type == XML_REGEXP_OTHER_CONTROL) ||
2201		     (range2->type == XML_REGEXP_OTHER_FORMAT) ||
2202		     (range2->type == XML_REGEXP_OTHER_PRIVATE))
2203		     ret = 1;
2204		 break;
2205            default:
2206	         if ((range2->type >= XML_REGEXP_LETTER) &&
2207		     (range2->type < XML_REGEXP_BLOCK_NAME))
2208		     ret = 0;
2209		 else {
2210		     /* safety net ! */
2211		     return(1);
2212		 }
2213	}
2214    }
2215    if (((range1->neg == 0) && (range2->neg != 0)) ||
2216        ((range1->neg != 0) && (range2->neg == 0)))
2217	ret = !ret;
2218    return(1);
2219}
2220
2221/**
2222 * xmlFACompareAtomTypes:
2223 * @type1:  an atom type
2224 * @type2:  an atom type
2225 *
2226 * Compares two atoms type to check whether they intersect in some ways,
2227 * this is used by xmlFACompareAtoms only
2228 *
2229 * Returns 1 if they may intersect and 0 otherwise
2230 */
2231static int
2232xmlFACompareAtomTypes(xmlRegAtomType type1, xmlRegAtomType type2) {
2233    if ((type1 == XML_REGEXP_EPSILON) ||
2234        (type1 == XML_REGEXP_CHARVAL) ||
2235	(type1 == XML_REGEXP_RANGES) ||
2236	(type1 == XML_REGEXP_SUBREG) ||
2237	(type1 == XML_REGEXP_STRING) ||
2238	(type1 == XML_REGEXP_ANYCHAR))
2239	return(1);
2240    if ((type2 == XML_REGEXP_EPSILON) ||
2241        (type2 == XML_REGEXP_CHARVAL) ||
2242	(type2 == XML_REGEXP_RANGES) ||
2243	(type2 == XML_REGEXP_SUBREG) ||
2244	(type2 == XML_REGEXP_STRING) ||
2245	(type2 == XML_REGEXP_ANYCHAR))
2246	return(1);
2247
2248    if (type1 == type2) return(1);
2249
2250    /* simplify subsequent compares by making sure type1 < type2 */
2251    if (type1 > type2) {
2252        xmlRegAtomType tmp = type1;
2253	type1 = type2;
2254	type2 = tmp;
2255    }
2256    switch (type1) {
2257        case XML_REGEXP_ANYSPACE: /* \s */
2258	    /* can't be a letter, number, mark, pontuation, symbol */
2259	    if ((type2 == XML_REGEXP_NOTSPACE) ||
2260		((type2 >= XML_REGEXP_LETTER) &&
2261		 (type2 <= XML_REGEXP_LETTER_OTHERS)) ||
2262	        ((type2 >= XML_REGEXP_NUMBER) &&
2263		 (type2 <= XML_REGEXP_NUMBER_OTHERS)) ||
2264	        ((type2 >= XML_REGEXP_MARK) &&
2265		 (type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
2266	        ((type2 >= XML_REGEXP_PUNCT) &&
2267		 (type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
2268	        ((type2 >= XML_REGEXP_SYMBOL) &&
2269		 (type2 <= XML_REGEXP_SYMBOL_OTHERS))
2270	        ) return(0);
2271	    break;
2272        case XML_REGEXP_NOTSPACE: /* \S */
2273	    break;
2274        case XML_REGEXP_INITNAME: /* \l */
2275	    /* can't be a number, mark, separator, pontuation, symbol or other */
2276	    if ((type2 == XML_REGEXP_NOTINITNAME) ||
2277	        ((type2 >= XML_REGEXP_NUMBER) &&
2278		 (type2 <= XML_REGEXP_NUMBER_OTHERS)) ||
2279	        ((type2 >= XML_REGEXP_MARK) &&
2280		 (type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
2281	        ((type2 >= XML_REGEXP_SEPAR) &&
2282		 (type2 <= XML_REGEXP_SEPAR_PARA)) ||
2283	        ((type2 >= XML_REGEXP_PUNCT) &&
2284		 (type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
2285	        ((type2 >= XML_REGEXP_SYMBOL) &&
2286		 (type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
2287	        ((type2 >= XML_REGEXP_OTHER) &&
2288		 (type2 <= XML_REGEXP_OTHER_NA))
2289		) return(0);
2290	    break;
2291        case XML_REGEXP_NOTINITNAME: /* \L */
2292	    break;
2293        case XML_REGEXP_NAMECHAR: /* \c */
2294	    /* can't be a mark, separator, pontuation, symbol or other */
2295	    if ((type2 == XML_REGEXP_NOTNAMECHAR) ||
2296	        ((type2 >= XML_REGEXP_MARK) &&
2297		 (type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
2298	        ((type2 >= XML_REGEXP_PUNCT) &&
2299		 (type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
2300	        ((type2 >= XML_REGEXP_SEPAR) &&
2301		 (type2 <= XML_REGEXP_SEPAR_PARA)) ||
2302	        ((type2 >= XML_REGEXP_SYMBOL) &&
2303		 (type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
2304	        ((type2 >= XML_REGEXP_OTHER) &&
2305		 (type2 <= XML_REGEXP_OTHER_NA))
2306		) return(0);
2307	    break;
2308        case XML_REGEXP_NOTNAMECHAR: /* \C */
2309	    break;
2310        case XML_REGEXP_DECIMAL: /* \d */
2311	    /* can't be a letter, mark, separator, pontuation, symbol or other */
2312	    if ((type2 == XML_REGEXP_NOTDECIMAL) ||
2313	        (type2 == XML_REGEXP_REALCHAR) ||
2314		((type2 >= XML_REGEXP_LETTER) &&
2315		 (type2 <= XML_REGEXP_LETTER_OTHERS)) ||
2316	        ((type2 >= XML_REGEXP_MARK) &&
2317		 (type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
2318	        ((type2 >= XML_REGEXP_PUNCT) &&
2319		 (type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
2320	        ((type2 >= XML_REGEXP_SEPAR) &&
2321		 (type2 <= XML_REGEXP_SEPAR_PARA)) ||
2322	        ((type2 >= XML_REGEXP_SYMBOL) &&
2323		 (type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
2324	        ((type2 >= XML_REGEXP_OTHER) &&
2325		 (type2 <= XML_REGEXP_OTHER_NA))
2326		)return(0);
2327	    break;
2328        case XML_REGEXP_NOTDECIMAL: /* \D */
2329	    break;
2330        case XML_REGEXP_REALCHAR: /* \w */
2331	    /* can't be a mark, separator, pontuation, symbol or other */
2332	    if ((type2 == XML_REGEXP_NOTDECIMAL) ||
2333	        ((type2 >= XML_REGEXP_MARK) &&
2334		 (type2 <= XML_REGEXP_MARK_ENCLOSING)) ||
2335	        ((type2 >= XML_REGEXP_PUNCT) &&
2336		 (type2 <= XML_REGEXP_PUNCT_OTHERS)) ||
2337	        ((type2 >= XML_REGEXP_SEPAR) &&
2338		 (type2 <= XML_REGEXP_SEPAR_PARA)) ||
2339	        ((type2 >= XML_REGEXP_SYMBOL) &&
2340		 (type2 <= XML_REGEXP_SYMBOL_OTHERS)) ||
2341	        ((type2 >= XML_REGEXP_OTHER) &&
2342		 (type2 <= XML_REGEXP_OTHER_NA))
2343		)return(0);
2344	    break;
2345        case XML_REGEXP_NOTREALCHAR: /* \W */
2346	    break;
2347	/*
2348	 * at that point we know both type 1 and type2 are from
2349	 * character categories are ordered and are different,
2350	 * it becomes simple because this is a partition
2351	 */
2352        case XML_REGEXP_LETTER:
2353	    if (type2 <= XML_REGEXP_LETTER_OTHERS)
2354	        return(1);
2355	    return(0);
2356        case XML_REGEXP_LETTER_UPPERCASE:
2357        case XML_REGEXP_LETTER_LOWERCASE:
2358        case XML_REGEXP_LETTER_TITLECASE:
2359        case XML_REGEXP_LETTER_MODIFIER:
2360        case XML_REGEXP_LETTER_OTHERS:
2361	    return(0);
2362        case XML_REGEXP_MARK:
2363	    if (type2 <= XML_REGEXP_MARK_ENCLOSING)
2364	        return(1);
2365	    return(0);
2366        case XML_REGEXP_MARK_NONSPACING:
2367        case XML_REGEXP_MARK_SPACECOMBINING:
2368        case XML_REGEXP_MARK_ENCLOSING:
2369	    return(0);
2370        case XML_REGEXP_NUMBER:
2371	    if (type2 <= XML_REGEXP_NUMBER_OTHERS)
2372	        return(1);
2373	    return(0);
2374        case XML_REGEXP_NUMBER_DECIMAL:
2375        case XML_REGEXP_NUMBER_LETTER:
2376        case XML_REGEXP_NUMBER_OTHERS:
2377	    return(0);
2378        case XML_REGEXP_PUNCT:
2379	    if (type2 <= XML_REGEXP_PUNCT_OTHERS)
2380	        return(1);
2381	    return(0);
2382        case XML_REGEXP_PUNCT_CONNECTOR:
2383        case XML_REGEXP_PUNCT_DASH:
2384        case XML_REGEXP_PUNCT_OPEN:
2385        case XML_REGEXP_PUNCT_CLOSE:
2386        case XML_REGEXP_PUNCT_INITQUOTE:
2387        case XML_REGEXP_PUNCT_FINQUOTE:
2388        case XML_REGEXP_PUNCT_OTHERS:
2389	    return(0);
2390        case XML_REGEXP_SEPAR:
2391	    if (type2 <= XML_REGEXP_SEPAR_PARA)
2392	        return(1);
2393	    return(0);
2394        case XML_REGEXP_SEPAR_SPACE:
2395        case XML_REGEXP_SEPAR_LINE:
2396        case XML_REGEXP_SEPAR_PARA:
2397	    return(0);
2398        case XML_REGEXP_SYMBOL:
2399	    if (type2 <= XML_REGEXP_SYMBOL_OTHERS)
2400	        return(1);
2401	    return(0);
2402        case XML_REGEXP_SYMBOL_MATH:
2403        case XML_REGEXP_SYMBOL_CURRENCY:
2404        case XML_REGEXP_SYMBOL_MODIFIER:
2405        case XML_REGEXP_SYMBOL_OTHERS:
2406	    return(0);
2407        case XML_REGEXP_OTHER:
2408	    if (type2 <= XML_REGEXP_OTHER_NA)
2409	        return(1);
2410	    return(0);
2411        case XML_REGEXP_OTHER_CONTROL:
2412        case XML_REGEXP_OTHER_FORMAT:
2413        case XML_REGEXP_OTHER_PRIVATE:
2414        case XML_REGEXP_OTHER_NA:
2415	    return(0);
2416	default:
2417	    break;
2418    }
2419    return(1);
2420}
2421
2422/**
2423 * xmlFAEqualAtoms:
2424 * @atom1:  an atom
2425 * @atom2:  an atom
2426 *
2427 * Compares two atoms to check whether they are the same exactly
2428 * this is used to remove equivalent transitions
2429 *
2430 * Returns 1 if same and 0 otherwise
2431 */
2432static int
2433xmlFAEqualAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2) {
2434    int ret = 0;
2435
2436    if (atom1 == atom2)
2437	return(1);
2438    if ((atom1 == NULL) || (atom2 == NULL))
2439	return(0);
2440
2441    if (atom1->type != atom2->type)
2442        return(0);
2443    switch (atom1->type) {
2444        case XML_REGEXP_EPSILON:
2445	    ret = 0;
2446	    break;
2447        case XML_REGEXP_STRING:
2448	    ret = xmlStrEqual((xmlChar *)atom1->valuep,
2449	                      (xmlChar *)atom2->valuep);
2450	    break;
2451        case XML_REGEXP_CHARVAL:
2452	    ret = (atom1->codepoint == atom2->codepoint);
2453	    break;
2454	case XML_REGEXP_RANGES:
2455	    /* too hard to do in the general case */
2456	    ret = 0;
2457	default:
2458	    break;
2459    }
2460    return(ret);
2461}
2462
2463/**
2464 * xmlFACompareAtoms:
2465 * @atom1:  an atom
2466 * @atom2:  an atom
2467 *
2468 * Compares two atoms to check whether they intersect in some ways,
2469 * this is used by xmlFAComputesDeterminism and xmlFARecurseDeterminism only
2470 *
2471 * Returns 1 if yes and 0 otherwise
2472 */
2473static int
2474xmlFACompareAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2) {
2475    int ret = 1;
2476
2477    if (atom1 == atom2)
2478	return(1);
2479    if ((atom1 == NULL) || (atom2 == NULL))
2480	return(0);
2481
2482    if ((atom1->type == XML_REGEXP_ANYCHAR) ||
2483        (atom2->type == XML_REGEXP_ANYCHAR))
2484	return(1);
2485
2486    if (atom1->type > atom2->type) {
2487	xmlRegAtomPtr tmp;
2488	tmp = atom1;
2489	atom1 = atom2;
2490	atom2 = tmp;
2491    }
2492    if (atom1->type != atom2->type) {
2493        ret = xmlFACompareAtomTypes(atom1->type, atom2->type);
2494	/* if they can't intersect at the type level break now */
2495	if (ret == 0)
2496	    return(0);
2497    }
2498    switch (atom1->type) {
2499        case XML_REGEXP_STRING:
2500	    ret = xmlRegStrEqualWildcard((xmlChar *)atom1->valuep,
2501	                                 (xmlChar *)atom2->valuep);
2502	    break;
2503        case XML_REGEXP_EPSILON:
2504	    goto not_determinist;
2505        case XML_REGEXP_CHARVAL:
2506	    if (atom2->type == XML_REGEXP_CHARVAL) {
2507		ret = (atom1->codepoint == atom2->codepoint);
2508	    } else {
2509	        ret = xmlRegCheckCharacter(atom2, atom1->codepoint);
2510		if (ret < 0)
2511		    ret = 1;
2512	    }
2513	    break;
2514        case XML_REGEXP_RANGES:
2515	    if (atom2->type == XML_REGEXP_RANGES) {
2516	        int i, j, res;
2517		xmlRegRangePtr r1, r2;
2518
2519		/*
2520		 * need to check that none of the ranges eventually matches
2521		 */
2522		for (i = 0;i < atom1->nbRanges;i++) {
2523		    for (j = 0;j < atom2->nbRanges;j++) {
2524			r1 = atom1->ranges[i];
2525			r2 = atom2->ranges[j];
2526			res = xmlFACompareRanges(r1, r2);
2527			if (res == 1) {
2528			    ret = 1;
2529			    goto done;
2530			}
2531		    }
2532		}
2533		ret = 0;
2534	    }
2535	    break;
2536	default:
2537	    goto not_determinist;
2538    }
2539done:
2540    if (atom1->neg != atom2->neg) {
2541        ret = !ret;
2542    }
2543    if (ret == 0)
2544        return(0);
2545not_determinist:
2546    return(1);
2547}
2548
2549/**
2550 * xmlFARecurseDeterminism:
2551 * @ctxt:  a regexp parser context
2552 *
2553 * Check whether the associated regexp is determinist,
2554 * should be called after xmlFAEliminateEpsilonTransitions()
2555 *
2556 */
2557static int
2558xmlFARecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
2559	                 int to, xmlRegAtomPtr atom) {
2560    int ret = 1;
2561    int res;
2562    int transnr, nbTrans;
2563    xmlRegTransPtr t1;
2564
2565    if (state == NULL)
2566	return(ret);
2567    /*
2568     * don't recurse on transitions potentially added in the course of
2569     * the elimination.
2570     */
2571    nbTrans = state->nbTrans;
2572    for (transnr = 0;transnr < nbTrans;transnr++) {
2573	t1 = &(state->trans[transnr]);
2574	/*
2575	 * check transitions conflicting with the one looked at
2576	 */
2577	if (t1->atom == NULL) {
2578	    if (t1->to < 0)
2579		continue;
2580	    res = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
2581		                           to, atom);
2582	    if (res == 0) {
2583	        ret = 0;
2584		/* t1->nd = 1; */
2585	    }
2586	    continue;
2587	}
2588	if (t1->to != to)
2589	    continue;
2590	if (xmlFACompareAtoms(t1->atom, atom)) {
2591	    ret = 0;
2592	    /* mark the transition as non-deterministic */
2593	    t1->nd = 1;
2594	}
2595    }
2596    return(ret);
2597}
2598
2599/**
2600 * xmlFAComputesDeterminism:
2601 * @ctxt:  a regexp parser context
2602 *
2603 * Check whether the associated regexp is determinist,
2604 * should be called after xmlFAEliminateEpsilonTransitions()
2605 *
2606 */
2607static int
2608xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt) {
2609    int statenr, transnr;
2610    xmlRegStatePtr state;
2611    xmlRegTransPtr t1, t2, last;
2612    int i;
2613    int ret = 1;
2614
2615#ifdef DEBUG_REGEXP_GRAPH
2616    printf("xmlFAComputesDeterminism\n");
2617    xmlRegPrintCtxt(stdout, ctxt);
2618#endif
2619    if (ctxt->determinist != -1)
2620	return(ctxt->determinist);
2621
2622    /*
2623     * First cleanup the automata removing cancelled transitions
2624     */
2625    for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2626	state = ctxt->states[statenr];
2627	if (state == NULL)
2628	    continue;
2629	if (state->nbTrans < 2)
2630	    continue;
2631	for (transnr = 0;transnr < state->nbTrans;transnr++) {
2632	    t1 = &(state->trans[transnr]);
2633	    /*
2634	     * Determinism checks in case of counted or all transitions
2635	     * will have to be handled separately
2636	     */
2637	    if (t1->atom == NULL) {
2638		/* t1->nd = 1; */
2639		continue;
2640	    }
2641	    if (t1->to == -1) /* eliminated */
2642		continue;
2643	    for (i = 0;i < transnr;i++) {
2644		t2 = &(state->trans[i]);
2645		if (t2->to == -1) /* eliminated */
2646		    continue;
2647		if (t2->atom != NULL) {
2648		    if (t1->to == t2->to) {
2649			if (xmlFAEqualAtoms(t1->atom, t2->atom))
2650			    t2->to = -1; /* eliminated */
2651		    }
2652		}
2653	    }
2654	}
2655    }
2656
2657    /*
2658     * Check for all states that there aren't 2 transitions
2659     * with the same atom and a different target.
2660     */
2661    for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2662	state = ctxt->states[statenr];
2663	if (state == NULL)
2664	    continue;
2665	if (state->nbTrans < 2)
2666	    continue;
2667	last = NULL;
2668	for (transnr = 0;transnr < state->nbTrans;transnr++) {
2669	    t1 = &(state->trans[transnr]);
2670	    /*
2671	     * Determinism checks in case of counted or all transitions
2672	     * will have to be handled separately
2673	     */
2674	    if (t1->atom == NULL) {
2675		continue;
2676	    }
2677	    if (t1->to == -1) /* eliminated */
2678		continue;
2679	    for (i = 0;i < transnr;i++) {
2680		t2 = &(state->trans[i]);
2681		if (t2->to == -1) /* eliminated */
2682		    continue;
2683		if (t2->atom != NULL) {
2684		    /* not determinist ! */
2685		    if (xmlFACompareAtoms(t1->atom, t2->atom)) {
2686			ret = 0;
2687			/* mark the transitions as non-deterministic ones */
2688			t1->nd = 1;
2689			t2->nd = 1;
2690			last = t1;
2691		    }
2692		} else if (t1->to != -1) {
2693		    /*
2694		     * do the closure in case of remaining specific
2695		     * epsilon transitions like choices or all
2696		     */
2697		    ret = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
2698						   t2->to, t2->atom);
2699		    /* don't shortcut the computation so all non deterministic
2700		       transition get marked down
2701		    if (ret == 0)
2702			return(0);
2703		     */
2704		    if (ret == 0) {
2705			t1->nd = 1;
2706			/* t2->nd = 1; */
2707			last = t1;
2708		    }
2709		}
2710	    }
2711	    /* don't shortcut the computation so all non deterministic
2712	       transition get marked down
2713	    if (ret == 0)
2714		break; */
2715	}
2716
2717	/*
2718	 * mark specifically the last non-deterministic transition
2719	 * from a state since there is no need to set-up rollback
2720	 * from it
2721	 */
2722	if (last != NULL) {
2723	    last->nd = 2;
2724	}
2725
2726	/* don't shortcut the computation so all non deterministic
2727	   transition get marked down
2728	if (ret == 0)
2729	    break; */
2730    }
2731
2732    ctxt->determinist = ret;
2733    return(ret);
2734}
2735
2736/************************************************************************
2737 * 									*
2738 *	Routines to check input against transition atoms		*
2739 * 									*
2740 ************************************************************************/
2741
2742static int
2743xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg,
2744	                  int start, int end, const xmlChar *blockName) {
2745    int ret = 0;
2746
2747    switch (type) {
2748        case XML_REGEXP_STRING:
2749        case XML_REGEXP_SUBREG:
2750        case XML_REGEXP_RANGES:
2751        case XML_REGEXP_EPSILON:
2752	    return(-1);
2753        case XML_REGEXP_ANYCHAR:
2754	    ret = ((codepoint != '\n') && (codepoint != '\r'));
2755	    break;
2756        case XML_REGEXP_CHARVAL:
2757	    ret = ((codepoint >= start) && (codepoint <= end));
2758	    break;
2759        case XML_REGEXP_NOTSPACE:
2760	    neg = !neg;
2761        case XML_REGEXP_ANYSPACE:
2762	    ret = ((codepoint == '\n') || (codepoint == '\r') ||
2763		   (codepoint == '\t') || (codepoint == ' '));
2764	    break;
2765        case XML_REGEXP_NOTINITNAME:
2766	    neg = !neg;
2767        case XML_REGEXP_INITNAME:
2768	    ret = (IS_LETTER(codepoint) ||
2769		   (codepoint == '_') || (codepoint == ':'));
2770	    break;
2771        case XML_REGEXP_NOTNAMECHAR:
2772	    neg = !neg;
2773        case XML_REGEXP_NAMECHAR:
2774	    ret = (IS_LETTER(codepoint) || IS_DIGIT(codepoint) ||
2775		   (codepoint == '.') || (codepoint == '-') ||
2776		   (codepoint == '_') || (codepoint == ':') ||
2777		   IS_COMBINING(codepoint) || IS_EXTENDER(codepoint));
2778	    break;
2779        case XML_REGEXP_NOTDECIMAL:
2780	    neg = !neg;
2781        case XML_REGEXP_DECIMAL:
2782	    ret = xmlUCSIsCatNd(codepoint);
2783	    break;
2784        case XML_REGEXP_REALCHAR:
2785	    neg = !neg;
2786        case XML_REGEXP_NOTREALCHAR:
2787	    ret = xmlUCSIsCatP(codepoint);
2788	    if (ret == 0)
2789		ret = xmlUCSIsCatZ(codepoint);
2790	    if (ret == 0)
2791		ret = xmlUCSIsCatC(codepoint);
2792	    break;
2793        case XML_REGEXP_LETTER:
2794	    ret = xmlUCSIsCatL(codepoint);
2795	    break;
2796        case XML_REGEXP_LETTER_UPPERCASE:
2797	    ret = xmlUCSIsCatLu(codepoint);
2798	    break;
2799        case XML_REGEXP_LETTER_LOWERCASE:
2800	    ret = xmlUCSIsCatLl(codepoint);
2801	    break;
2802        case XML_REGEXP_LETTER_TITLECASE:
2803	    ret = xmlUCSIsCatLt(codepoint);
2804	    break;
2805        case XML_REGEXP_LETTER_MODIFIER:
2806	    ret = xmlUCSIsCatLm(codepoint);
2807	    break;
2808        case XML_REGEXP_LETTER_OTHERS:
2809	    ret = xmlUCSIsCatLo(codepoint);
2810	    break;
2811        case XML_REGEXP_MARK:
2812	    ret = xmlUCSIsCatM(codepoint);
2813	    break;
2814        case XML_REGEXP_MARK_NONSPACING:
2815	    ret = xmlUCSIsCatMn(codepoint);
2816	    break;
2817        case XML_REGEXP_MARK_SPACECOMBINING:
2818	    ret = xmlUCSIsCatMc(codepoint);
2819	    break;
2820        case XML_REGEXP_MARK_ENCLOSING:
2821	    ret = xmlUCSIsCatMe(codepoint);
2822	    break;
2823        case XML_REGEXP_NUMBER:
2824	    ret = xmlUCSIsCatN(codepoint);
2825	    break;
2826        case XML_REGEXP_NUMBER_DECIMAL:
2827	    ret = xmlUCSIsCatNd(codepoint);
2828	    break;
2829        case XML_REGEXP_NUMBER_LETTER:
2830	    ret = xmlUCSIsCatNl(codepoint);
2831	    break;
2832        case XML_REGEXP_NUMBER_OTHERS:
2833	    ret = xmlUCSIsCatNo(codepoint);
2834	    break;
2835        case XML_REGEXP_PUNCT:
2836	    ret = xmlUCSIsCatP(codepoint);
2837	    break;
2838        case XML_REGEXP_PUNCT_CONNECTOR:
2839	    ret = xmlUCSIsCatPc(codepoint);
2840	    break;
2841        case XML_REGEXP_PUNCT_DASH:
2842	    ret = xmlUCSIsCatPd(codepoint);
2843	    break;
2844        case XML_REGEXP_PUNCT_OPEN:
2845	    ret = xmlUCSIsCatPs(codepoint);
2846	    break;
2847        case XML_REGEXP_PUNCT_CLOSE:
2848	    ret = xmlUCSIsCatPe(codepoint);
2849	    break;
2850        case XML_REGEXP_PUNCT_INITQUOTE:
2851	    ret = xmlUCSIsCatPi(codepoint);
2852	    break;
2853        case XML_REGEXP_PUNCT_FINQUOTE:
2854	    ret = xmlUCSIsCatPf(codepoint);
2855	    break;
2856        case XML_REGEXP_PUNCT_OTHERS:
2857	    ret = xmlUCSIsCatPo(codepoint);
2858	    break;
2859        case XML_REGEXP_SEPAR:
2860	    ret = xmlUCSIsCatZ(codepoint);
2861	    break;
2862        case XML_REGEXP_SEPAR_SPACE:
2863	    ret = xmlUCSIsCatZs(codepoint);
2864	    break;
2865        case XML_REGEXP_SEPAR_LINE:
2866	    ret = xmlUCSIsCatZl(codepoint);
2867	    break;
2868        case XML_REGEXP_SEPAR_PARA:
2869	    ret = xmlUCSIsCatZp(codepoint);
2870	    break;
2871        case XML_REGEXP_SYMBOL:
2872	    ret = xmlUCSIsCatS(codepoint);
2873	    break;
2874        case XML_REGEXP_SYMBOL_MATH:
2875	    ret = xmlUCSIsCatSm(codepoint);
2876	    break;
2877        case XML_REGEXP_SYMBOL_CURRENCY:
2878	    ret = xmlUCSIsCatSc(codepoint);
2879	    break;
2880        case XML_REGEXP_SYMBOL_MODIFIER:
2881	    ret = xmlUCSIsCatSk(codepoint);
2882	    break;
2883        case XML_REGEXP_SYMBOL_OTHERS:
2884	    ret = xmlUCSIsCatSo(codepoint);
2885	    break;
2886        case XML_REGEXP_OTHER:
2887	    ret = xmlUCSIsCatC(codepoint);
2888	    break;
2889        case XML_REGEXP_OTHER_CONTROL:
2890	    ret = xmlUCSIsCatCc(codepoint);
2891	    break;
2892        case XML_REGEXP_OTHER_FORMAT:
2893	    ret = xmlUCSIsCatCf(codepoint);
2894	    break;
2895        case XML_REGEXP_OTHER_PRIVATE:
2896	    ret = xmlUCSIsCatCo(codepoint);
2897	    break;
2898        case XML_REGEXP_OTHER_NA:
2899	    /* ret = xmlUCSIsCatCn(codepoint); */
2900	    /* Seems it doesn't exist anymore in recent Unicode releases */
2901	    ret = 0;
2902	    break;
2903        case XML_REGEXP_BLOCK_NAME:
2904	    ret = xmlUCSIsBlock(codepoint, (const char *) blockName);
2905	    break;
2906    }
2907    if (neg)
2908	return(!ret);
2909    return(ret);
2910}
2911
2912static int
2913xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint) {
2914    int i, ret = 0;
2915    xmlRegRangePtr range;
2916
2917    if ((atom == NULL) || (!IS_CHAR(codepoint)))
2918	return(-1);
2919
2920    switch (atom->type) {
2921        case XML_REGEXP_SUBREG:
2922        case XML_REGEXP_EPSILON:
2923	    return(-1);
2924        case XML_REGEXP_CHARVAL:
2925            return(codepoint == atom->codepoint);
2926        case XML_REGEXP_RANGES: {
2927	    int accept = 0;
2928
2929	    for (i = 0;i < atom->nbRanges;i++) {
2930		range = atom->ranges[i];
2931		if (range->neg == 2) {
2932		    ret = xmlRegCheckCharacterRange(range->type, codepoint,
2933						0, range->start, range->end,
2934						range->blockName);
2935		    if (ret != 0)
2936			return(0); /* excluded char */
2937		} else if (range->neg) {
2938		    ret = xmlRegCheckCharacterRange(range->type, codepoint,
2939						0, range->start, range->end,
2940						range->blockName);
2941		    if (ret == 0)
2942		        accept = 1;
2943		    else
2944		        return(0);
2945		} else {
2946		    ret = xmlRegCheckCharacterRange(range->type, codepoint,
2947						0, range->start, range->end,
2948						range->blockName);
2949		    if (ret != 0)
2950			accept = 1; /* might still be excluded */
2951		}
2952	    }
2953	    return(accept);
2954	}
2955        case XML_REGEXP_STRING:
2956	    printf("TODO: XML_REGEXP_STRING\n");
2957	    return(-1);
2958        case XML_REGEXP_ANYCHAR:
2959        case XML_REGEXP_ANYSPACE:
2960        case XML_REGEXP_NOTSPACE:
2961        case XML_REGEXP_INITNAME:
2962        case XML_REGEXP_NOTINITNAME:
2963        case XML_REGEXP_NAMECHAR:
2964        case XML_REGEXP_NOTNAMECHAR:
2965        case XML_REGEXP_DECIMAL:
2966        case XML_REGEXP_NOTDECIMAL:
2967        case XML_REGEXP_REALCHAR:
2968        case XML_REGEXP_NOTREALCHAR:
2969        case XML_REGEXP_LETTER:
2970        case XML_REGEXP_LETTER_UPPERCASE:
2971        case XML_REGEXP_LETTER_LOWERCASE:
2972        case XML_REGEXP_LETTER_TITLECASE:
2973        case XML_REGEXP_LETTER_MODIFIER:
2974        case XML_REGEXP_LETTER_OTHERS:
2975        case XML_REGEXP_MARK:
2976        case XML_REGEXP_MARK_NONSPACING:
2977        case XML_REGEXP_MARK_SPACECOMBINING:
2978        case XML_REGEXP_MARK_ENCLOSING:
2979        case XML_REGEXP_NUMBER:
2980        case XML_REGEXP_NUMBER_DECIMAL:
2981        case XML_REGEXP_NUMBER_LETTER:
2982        case XML_REGEXP_NUMBER_OTHERS:
2983        case XML_REGEXP_PUNCT:
2984        case XML_REGEXP_PUNCT_CONNECTOR:
2985        case XML_REGEXP_PUNCT_DASH:
2986        case XML_REGEXP_PUNCT_OPEN:
2987        case XML_REGEXP_PUNCT_CLOSE:
2988        case XML_REGEXP_PUNCT_INITQUOTE:
2989        case XML_REGEXP_PUNCT_FINQUOTE:
2990        case XML_REGEXP_PUNCT_OTHERS:
2991        case XML_REGEXP_SEPAR:
2992        case XML_REGEXP_SEPAR_SPACE:
2993        case XML_REGEXP_SEPAR_LINE:
2994        case XML_REGEXP_SEPAR_PARA:
2995        case XML_REGEXP_SYMBOL:
2996        case XML_REGEXP_SYMBOL_MATH:
2997        case XML_REGEXP_SYMBOL_CURRENCY:
2998        case XML_REGEXP_SYMBOL_MODIFIER:
2999        case XML_REGEXP_SYMBOL_OTHERS:
3000        case XML_REGEXP_OTHER:
3001        case XML_REGEXP_OTHER_CONTROL:
3002        case XML_REGEXP_OTHER_FORMAT:
3003        case XML_REGEXP_OTHER_PRIVATE:
3004        case XML_REGEXP_OTHER_NA:
3005	case XML_REGEXP_BLOCK_NAME:
3006	    ret = xmlRegCheckCharacterRange(atom->type, codepoint, 0, 0, 0,
3007		                            (const xmlChar *)atom->valuep);
3008	    if (atom->neg)
3009		ret = !ret;
3010	    break;
3011    }
3012    return(ret);
3013}
3014
3015/************************************************************************
3016 * 									*
3017 *	Saving and restoring state of an execution context		*
3018 * 									*
3019 ************************************************************************/
3020
3021#ifdef DEBUG_REGEXP_EXEC
3022static void
3023xmlFARegDebugExec(xmlRegExecCtxtPtr exec) {
3024    printf("state: %d:%d:idx %d", exec->state->no, exec->transno, exec->index);
3025    if (exec->inputStack != NULL) {
3026	int i;
3027	printf(": ");
3028	for (i = 0;(i < 3) && (i < exec->inputStackNr);i++)
3029	    printf("%s ", (const char *)
3030	           exec->inputStack[exec->inputStackNr - (i + 1)].value);
3031    } else {
3032	printf(": %s", &(exec->inputString[exec->index]));
3033    }
3034    printf("\n");
3035}
3036#endif
3037
3038static void
3039xmlFARegExecSave(xmlRegExecCtxtPtr exec) {
3040#ifdef DEBUG_REGEXP_EXEC
3041    printf("saving ");
3042    exec->transno++;
3043    xmlFARegDebugExec(exec);
3044    exec->transno--;
3045#endif
3046#ifdef MAX_PUSH
3047    if (exec->nbPush > MAX_PUSH) {
3048        return;
3049    }
3050    exec->nbPush++;
3051#endif
3052
3053    if (exec->maxRollbacks == 0) {
3054	exec->maxRollbacks = 4;
3055	exec->rollbacks = (xmlRegExecRollback *) xmlMalloc(exec->maxRollbacks *
3056		                             sizeof(xmlRegExecRollback));
3057	if (exec->rollbacks == NULL) {
3058	    xmlRegexpErrMemory(NULL, "saving regexp");
3059	    exec->maxRollbacks = 0;
3060	    return;
3061	}
3062	memset(exec->rollbacks, 0,
3063	       exec->maxRollbacks * sizeof(xmlRegExecRollback));
3064    } else if (exec->nbRollbacks >= exec->maxRollbacks) {
3065	xmlRegExecRollback *tmp;
3066	int len = exec->maxRollbacks;
3067
3068	exec->maxRollbacks *= 2;
3069	tmp = (xmlRegExecRollback *) xmlRealloc(exec->rollbacks,
3070			exec->maxRollbacks * sizeof(xmlRegExecRollback));
3071	if (tmp == NULL) {
3072	    xmlRegexpErrMemory(NULL, "saving regexp");
3073	    exec->maxRollbacks /= 2;
3074	    return;
3075	}
3076	exec->rollbacks = tmp;
3077	tmp = &exec->rollbacks[len];
3078	memset(tmp, 0, (exec->maxRollbacks - len) * sizeof(xmlRegExecRollback));
3079    }
3080    exec->rollbacks[exec->nbRollbacks].state = exec->state;
3081    exec->rollbacks[exec->nbRollbacks].index = exec->index;
3082    exec->rollbacks[exec->nbRollbacks].nextbranch = exec->transno + 1;
3083    if (exec->comp->nbCounters > 0) {
3084	if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
3085	    exec->rollbacks[exec->nbRollbacks].counts = (int *)
3086		xmlMalloc(exec->comp->nbCounters * sizeof(int));
3087	    if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
3088		xmlRegexpErrMemory(NULL, "saving regexp");
3089		exec->status = -5;
3090		return;
3091	    }
3092	}
3093	memcpy(exec->rollbacks[exec->nbRollbacks].counts, exec->counts,
3094	       exec->comp->nbCounters * sizeof(int));
3095    }
3096    exec->nbRollbacks++;
3097}
3098
3099static void
3100xmlFARegExecRollBack(xmlRegExecCtxtPtr exec) {
3101    if (exec->nbRollbacks <= 0) {
3102	exec->status = -1;
3103#ifdef DEBUG_REGEXP_EXEC
3104	printf("rollback failed on empty stack\n");
3105#endif
3106	return;
3107    }
3108    exec->nbRollbacks--;
3109    exec->state = exec->rollbacks[exec->nbRollbacks].state;
3110    exec->index = exec->rollbacks[exec->nbRollbacks].index;
3111    exec->transno = exec->rollbacks[exec->nbRollbacks].nextbranch;
3112    if (exec->comp->nbCounters > 0) {
3113	if (exec->rollbacks[exec->nbRollbacks].counts == NULL) {
3114	    fprintf(stderr, "exec save: allocation failed");
3115	    exec->status = -6;
3116	    return;
3117	}
3118	memcpy(exec->counts, exec->rollbacks[exec->nbRollbacks].counts,
3119	       exec->comp->nbCounters * sizeof(int));
3120    }
3121
3122#ifdef DEBUG_REGEXP_EXEC
3123    printf("restored ");
3124    xmlFARegDebugExec(exec);
3125#endif
3126}
3127
3128/************************************************************************
3129 * 									*
3130 *	Verifier, running an input against a compiled regexp		*
3131 * 									*
3132 ************************************************************************/
3133
3134static int
3135xmlFARegExec(xmlRegexpPtr comp, const xmlChar *content) {
3136    xmlRegExecCtxt execval;
3137    xmlRegExecCtxtPtr exec = &execval;
3138    int ret, codepoint = 0, len, deter;
3139
3140    exec->inputString = content;
3141    exec->index = 0;
3142    exec->nbPush = 0;
3143    exec->determinist = 1;
3144    exec->maxRollbacks = 0;
3145    exec->nbRollbacks = 0;
3146    exec->rollbacks = NULL;
3147    exec->status = 0;
3148    exec->comp = comp;
3149    exec->state = comp->states[0];
3150    exec->transno = 0;
3151    exec->transcount = 0;
3152    exec->inputStack = NULL;
3153    exec->inputStackMax = 0;
3154    if (comp->nbCounters > 0) {
3155	exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int));
3156	if (exec->counts == NULL) {
3157	    xmlRegexpErrMemory(NULL, "running regexp");
3158	    return(-1);
3159	}
3160        memset(exec->counts, 0, comp->nbCounters * sizeof(int));
3161    } else
3162	exec->counts = NULL;
3163    while ((exec->status == 0) &&
3164	   ((exec->inputString[exec->index] != 0) ||
3165	    ((exec->state != NULL) &&
3166	     (exec->state->type != XML_REGEXP_FINAL_STATE)))) {
3167	xmlRegTransPtr trans;
3168	xmlRegAtomPtr atom;
3169
3170	/*
3171	 * If end of input on non-terminal state, rollback, however we may
3172	 * still have epsilon like transition for counted transitions
3173	 * on counters, in that case don't break too early.  Additionally,
3174	 * if we are working on a range like "AB{0,2}", where B is not present,
3175	 * we don't want to break.
3176	 */
3177	len = 1;
3178	if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL)) {
3179	    /*
3180	     * if there is a transition, we must check if
3181	     *  atom allows minOccurs of 0
3182	     */
3183	    if (exec->transno < exec->state->nbTrans) {
3184	        trans = &exec->state->trans[exec->transno];
3185		if (trans->to >=0) {
3186		    atom = trans->atom;
3187		    if (!((atom->min == 0) && (atom->max > 0)))
3188		        goto rollback;
3189		}
3190	    } else
3191	        goto rollback;
3192	}
3193
3194	exec->transcount = 0;
3195	for (;exec->transno < exec->state->nbTrans;exec->transno++) {
3196	    trans = &exec->state->trans[exec->transno];
3197	    if (trans->to < 0)
3198		continue;
3199	    atom = trans->atom;
3200	    ret = 0;
3201	    deter = 1;
3202	    if (trans->count >= 0) {
3203		int count;
3204		xmlRegCounterPtr counter;
3205
3206		if (exec->counts == NULL) {
3207		    exec->status = -1;
3208		    goto error;
3209		}
3210		/*
3211		 * A counted transition.
3212		 */
3213
3214		count = exec->counts[trans->count];
3215		counter = &exec->comp->counters[trans->count];
3216#ifdef DEBUG_REGEXP_EXEC
3217		printf("testing count %d: val %d, min %d, max %d\n",
3218		       trans->count, count, counter->min,  counter->max);
3219#endif
3220		ret = ((count >= counter->min) && (count <= counter->max));
3221		if ((ret) && (counter->min != counter->max))
3222		    deter = 0;
3223	    } else if (atom == NULL) {
3224		fprintf(stderr, "epsilon transition left at runtime\n");
3225		exec->status = -2;
3226		break;
3227	    } else if (exec->inputString[exec->index] != 0) {
3228                codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);
3229		ret = xmlRegCheckCharacter(atom, codepoint);
3230		if ((ret == 1) && (atom->min >= 0) && (atom->max > 0)) {
3231		    xmlRegStatePtr to = comp->states[trans->to];
3232
3233		    /*
3234		     * this is a multiple input sequence
3235		     * If there is a counter associated increment it now.
3236		     * before potentially saving and rollback
3237		     * do not increment if the counter is already over the
3238		     * maximum limit in which case get to next transition
3239		     */
3240		    if (trans->counter >= 0) {
3241			xmlRegCounterPtr counter;
3242
3243			if ((exec->counts == NULL) ||
3244			    (exec->comp == NULL) ||
3245			    (exec->comp->counters == NULL)) {
3246			    exec->status = -1;
3247			    goto error;
3248			}
3249			counter = &exec->comp->counters[trans->counter];
3250			if (exec->counts[trans->counter] >= counter->max)
3251			    continue; /* for loop on transitions */
3252
3253#ifdef DEBUG_REGEXP_EXEC
3254			printf("Increasing count %d\n", trans->counter);
3255#endif
3256			exec->counts[trans->counter]++;
3257		    }
3258		    if (exec->state->nbTrans > exec->transno + 1) {
3259			xmlFARegExecSave(exec);
3260		    }
3261		    exec->transcount = 1;
3262		    do {
3263			/*
3264			 * Try to progress as much as possible on the input
3265			 */
3266			if (exec->transcount == atom->max) {
3267			    break;
3268			}
3269			exec->index += len;
3270			/*
3271			 * End of input: stop here
3272			 */
3273			if (exec->inputString[exec->index] == 0) {
3274			    exec->index -= len;
3275			    break;
3276			}
3277			if (exec->transcount >= atom->min) {
3278			    int transno = exec->transno;
3279			    xmlRegStatePtr state = exec->state;
3280
3281			    /*
3282			     * The transition is acceptable save it
3283			     */
3284			    exec->transno = -1; /* trick */
3285			    exec->state = to;
3286			    xmlFARegExecSave(exec);
3287			    exec->transno = transno;
3288			    exec->state = state;
3289			}
3290			codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),
3291				              len);
3292			ret = xmlRegCheckCharacter(atom, codepoint);
3293			exec->transcount++;
3294		    } while (ret == 1);
3295		    if (exec->transcount < atom->min)
3296			ret = 0;
3297
3298		    /*
3299		     * If the last check failed but one transition was found
3300		     * possible, rollback
3301		     */
3302		    if (ret < 0)
3303			ret = 0;
3304		    if (ret == 0) {
3305			goto rollback;
3306		    }
3307		    if (trans->counter >= 0) {
3308			if (exec->counts == NULL) {
3309			    exec->status = -1;
3310			    goto error;
3311			}
3312#ifdef DEBUG_REGEXP_EXEC
3313			printf("Decreasing count %d\n", trans->counter);
3314#endif
3315			exec->counts[trans->counter]--;
3316		    }
3317		} else if ((ret == 0) && (atom->min == 0) && (atom->max > 0)) {
3318		    /*
3319		     * we don't match on the codepoint, but minOccurs of 0
3320		     * says that's ok.  Setting len to 0 inhibits stepping
3321		     * over the codepoint.
3322		     */
3323		    exec->transcount = 1;
3324		    len = 0;
3325		    ret = 1;
3326		}
3327	    } else if ((atom->min == 0) && (atom->max > 0)) {
3328	        /* another spot to match when minOccurs is 0 */
3329		exec->transcount = 1;
3330		len = 0;
3331		ret = 1;
3332	    }
3333	    if (ret == 1) {
3334		if ((trans->nd == 1) ||
3335		    ((trans->count >= 0) && (deter == 0) &&
3336		     (exec->state->nbTrans > exec->transno + 1))) {
3337#ifdef DEBUG_REGEXP_EXEC
3338		    if (trans->nd == 1)
3339		        printf("Saving on nd transition atom %d for %c at %d\n",
3340			       trans->atom->no, codepoint, exec->index);
3341		    else
3342		        printf("Saving on counted transition count %d for %c at %d\n",
3343			       trans->count, codepoint, exec->index);
3344#endif
3345		    xmlFARegExecSave(exec);
3346		}
3347		if (trans->counter >= 0) {
3348		    xmlRegCounterPtr counter;
3349
3350                    /* make sure we don't go over the counter maximum value */
3351		    if ((exec->counts == NULL) ||
3352			(exec->comp == NULL) ||
3353			(exec->comp->counters == NULL)) {
3354			exec->status = -1;
3355			goto error;
3356		    }
3357		    counter = &exec->comp->counters[trans->counter];
3358		    if (exec->counts[trans->counter] >= counter->max)
3359			continue; /* for loop on transitions */
3360#ifdef DEBUG_REGEXP_EXEC
3361		    printf("Increasing count %d\n", trans->counter);
3362#endif
3363		    exec->counts[trans->counter]++;
3364		}
3365		if ((trans->count >= 0) &&
3366		    (trans->count < REGEXP_ALL_COUNTER)) {
3367		    if (exec->counts == NULL) {
3368		        exec->status = -1;
3369			goto error;
3370		    }
3371#ifdef DEBUG_REGEXP_EXEC
3372		    printf("resetting count %d on transition\n",
3373		           trans->count);
3374#endif
3375		    exec->counts[trans->count] = 0;
3376		}
3377#ifdef DEBUG_REGEXP_EXEC
3378		printf("entering state %d\n", trans->to);
3379#endif
3380		exec->state = comp->states[trans->to];
3381		exec->transno = 0;
3382		if (trans->atom != NULL) {
3383		    exec->index += len;
3384		}
3385		goto progress;
3386	    } else if (ret < 0) {
3387		exec->status = -4;
3388		break;
3389	    }
3390	}
3391	if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
3392rollback:
3393	    /*
3394	     * Failed to find a way out
3395	     */
3396	    exec->determinist = 0;
3397#ifdef DEBUG_REGEXP_EXEC
3398	    printf("rollback from state %d on %d:%c\n", exec->state->no,
3399	           codepoint,codepoint);
3400#endif
3401	    xmlFARegExecRollBack(exec);
3402	}
3403progress:
3404	continue;
3405    }
3406error:
3407    if (exec->rollbacks != NULL) {
3408	if (exec->counts != NULL) {
3409	    int i;
3410
3411	    for (i = 0;i < exec->maxRollbacks;i++)
3412		if (exec->rollbacks[i].counts != NULL)
3413		    xmlFree(exec->rollbacks[i].counts);
3414	}
3415	xmlFree(exec->rollbacks);
3416    }
3417    if (exec->counts != NULL)
3418	xmlFree(exec->counts);
3419    if (exec->status == 0)
3420	return(1);
3421    if (exec->status == -1) {
3422	if (exec->nbPush > MAX_PUSH)
3423	    return(-1);
3424	return(0);
3425    }
3426    return(exec->status);
3427}
3428
3429/************************************************************************
3430 * 									*
3431 *	Progressive interface to the verifier one atom at a time	*
3432 * 									*
3433 ************************************************************************/
3434#ifdef DEBUG_ERR
3435static void testerr(xmlRegExecCtxtPtr exec);
3436#endif
3437
3438/**
3439 * xmlRegNewExecCtxt:
3440 * @comp: a precompiled regular expression
3441 * @callback: a callback function used for handling progresses in the
3442 *            automata matching phase
3443 * @data: the context data associated to the callback in this context
3444 *
3445 * Build a context used for progressive evaluation of a regexp.
3446 *
3447 * Returns the new context
3448 */
3449xmlRegExecCtxtPtr
3450xmlRegNewExecCtxt(xmlRegexpPtr comp, xmlRegExecCallbacks callback, void *data) {
3451    xmlRegExecCtxtPtr exec;
3452
3453    if (comp == NULL)
3454	return(NULL);
3455    if ((comp->compact == NULL) && (comp->states == NULL))
3456        return(NULL);
3457    exec = (xmlRegExecCtxtPtr) xmlMalloc(sizeof(xmlRegExecCtxt));
3458    if (exec == NULL) {
3459	xmlRegexpErrMemory(NULL, "creating execution context");
3460	return(NULL);
3461    }
3462    memset(exec, 0, sizeof(xmlRegExecCtxt));
3463    exec->inputString = NULL;
3464    exec->index = 0;
3465    exec->determinist = 1;
3466    exec->maxRollbacks = 0;
3467    exec->nbRollbacks = 0;
3468    exec->rollbacks = NULL;
3469    exec->status = 0;
3470    exec->comp = comp;
3471    if (comp->compact == NULL)
3472	exec->state = comp->states[0];
3473    exec->transno = 0;
3474    exec->transcount = 0;
3475    exec->callback = callback;
3476    exec->data = data;
3477    if (comp->nbCounters > 0) {
3478        /*
3479	 * For error handling, exec->counts is allocated twice the size
3480	 * the second half is used to store the data in case of rollback
3481	 */
3482	exec->counts = (int *) xmlMalloc(comp->nbCounters * sizeof(int)
3483	                                 * 2);
3484	if (exec->counts == NULL) {
3485	    xmlRegexpErrMemory(NULL, "creating execution context");
3486	    xmlFree(exec);
3487	    return(NULL);
3488	}
3489        memset(exec->counts, 0, comp->nbCounters * sizeof(int) * 2);
3490	exec->errCounts = &exec->counts[comp->nbCounters];
3491    } else {
3492	exec->counts = NULL;
3493	exec->errCounts = NULL;
3494    }
3495    exec->inputStackMax = 0;
3496    exec->inputStackNr = 0;
3497    exec->inputStack = NULL;
3498    exec->errStateNo = -1;
3499    exec->errString = NULL;
3500    exec->nbPush = 0;
3501    return(exec);
3502}
3503
3504/**
3505 * xmlRegFreeExecCtxt:
3506 * @exec: a regular expression evaulation context
3507 *
3508 * Free the structures associated to a regular expression evaulation context.
3509 */
3510void
3511xmlRegFreeExecCtxt(xmlRegExecCtxtPtr exec) {
3512    if (exec == NULL)
3513	return;
3514
3515    if (exec->rollbacks != NULL) {
3516	if (exec->counts != NULL) {
3517	    int i;
3518
3519	    for (i = 0;i < exec->maxRollbacks;i++)
3520		if (exec->rollbacks[i].counts != NULL)
3521		    xmlFree(exec->rollbacks[i].counts);
3522	}
3523	xmlFree(exec->rollbacks);
3524    }
3525    if (exec->counts != NULL)
3526	xmlFree(exec->counts);
3527    if (exec->inputStack != NULL) {
3528	int i;
3529
3530	for (i = 0;i < exec->inputStackNr;i++) {
3531	    if (exec->inputStack[i].value != NULL)
3532		xmlFree(exec->inputStack[i].value);
3533	}
3534	xmlFree(exec->inputStack);
3535    }
3536    if (exec->errString != NULL)
3537        xmlFree(exec->errString);
3538    xmlFree(exec);
3539}
3540
3541static void
3542xmlFARegExecSaveInputString(xmlRegExecCtxtPtr exec, const xmlChar *value,
3543	                    void *data) {
3544#ifdef DEBUG_PUSH
3545    printf("saving value: %d:%s\n", exec->inputStackNr, value);
3546#endif
3547    if (exec->inputStackMax == 0) {
3548	exec->inputStackMax = 4;
3549	exec->inputStack = (xmlRegInputTokenPtr)
3550	    xmlMalloc(exec->inputStackMax * sizeof(xmlRegInputToken));
3551	if (exec->inputStack == NULL) {
3552	    xmlRegexpErrMemory(NULL, "pushing input string");
3553	    exec->inputStackMax = 0;
3554	    return;
3555	}
3556    } else if (exec->inputStackNr + 1 >= exec->inputStackMax) {
3557	xmlRegInputTokenPtr tmp;
3558
3559	exec->inputStackMax *= 2;
3560	tmp = (xmlRegInputTokenPtr) xmlRealloc(exec->inputStack,
3561			exec->inputStackMax * sizeof(xmlRegInputToken));
3562	if (tmp == NULL) {
3563	    xmlRegexpErrMemory(NULL, "pushing input string");
3564	    exec->inputStackMax /= 2;
3565	    return;
3566	}
3567	exec->inputStack = tmp;
3568    }
3569    exec->inputStack[exec->inputStackNr].value = xmlStrdup(value);
3570    exec->inputStack[exec->inputStackNr].data = data;
3571    exec->inputStackNr++;
3572    exec->inputStack[exec->inputStackNr].value = NULL;
3573    exec->inputStack[exec->inputStackNr].data = NULL;
3574}
3575
3576/**
3577 * xmlRegStrEqualWildcard:
3578 * @expStr:  the string to be evaluated
3579 * @valStr:  the validation string
3580 *
3581 * Checks if both strings are equal or have the same content. "*"
3582 * can be used as a wildcard in @valStr; "|" is used as a seperator of
3583 * substrings in both @expStr and @valStr.
3584 *
3585 * Returns 1 if the comparison is satisfied and the number of substrings
3586 * is equal, 0 otherwise.
3587 */
3588
3589static int
3590xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr) {
3591    if (expStr == valStr) return(1);
3592    if (expStr == NULL) return(0);
3593    if (valStr == NULL) return(0);
3594    do {
3595	/*
3596	* Eval if we have a wildcard for the current item.
3597	*/
3598        if (*expStr != *valStr) {
3599	    /* if one of them starts with a wildcard make valStr be it */
3600	    if (*valStr == '*') {
3601	        const xmlChar *tmp;
3602
3603		tmp = valStr;
3604		valStr = expStr;
3605		expStr = tmp;
3606	    }
3607	    if ((*valStr != 0) && (*expStr != 0) && (*expStr++ == '*')) {
3608		do {
3609		    if (*valStr == XML_REG_STRING_SEPARATOR)
3610			break;
3611		    valStr++;
3612		} while (*valStr != 0);
3613		continue;
3614	    } else
3615		return(0);
3616	}
3617	expStr++;
3618	valStr++;
3619    } while (*valStr != 0);
3620    if (*expStr != 0)
3621	return (0);
3622    else
3623	return (1);
3624}
3625
3626/**
3627 * xmlRegCompactPushString:
3628 * @exec: a regexp execution context
3629 * @comp:  the precompiled exec with a compact table
3630 * @value: a string token input
3631 * @data: data associated to the token to reuse in callbacks
3632 *
3633 * Push one input token in the execution context
3634 *
3635 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
3636 *     a negative value in case of error.
3637 */
3638static int
3639xmlRegCompactPushString(xmlRegExecCtxtPtr exec,
3640	                xmlRegexpPtr comp,
3641	                const xmlChar *value,
3642	                void *data) {
3643    int state = exec->index;
3644    int i, target;
3645
3646    if ((comp == NULL) || (comp->compact == NULL) || (comp->stringMap == NULL))
3647	return(-1);
3648
3649    if (value == NULL) {
3650	/*
3651	 * are we at a final state ?
3652	 */
3653	if (comp->compact[state * (comp->nbstrings + 1)] ==
3654            XML_REGEXP_FINAL_STATE)
3655	    return(1);
3656	return(0);
3657    }
3658
3659#ifdef DEBUG_PUSH
3660    printf("value pushed: %s\n", value);
3661#endif
3662
3663    /*
3664     * Examine all outside transitions from current state
3665     */
3666    for (i = 0;i < comp->nbstrings;i++) {
3667	target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
3668	if ((target > 0) && (target <= comp->nbstates)) {
3669	    target--; /* to avoid 0 */
3670	    if (xmlRegStrEqualWildcard(comp->stringMap[i], value)) {
3671		exec->index = target;
3672		if ((exec->callback != NULL) && (comp->transdata != NULL)) {
3673		    exec->callback(exec->data, value,
3674			  comp->transdata[state * comp->nbstrings + i], data);
3675		}
3676#ifdef DEBUG_PUSH
3677		printf("entering state %d\n", target);
3678#endif
3679		if (comp->compact[target * (comp->nbstrings + 1)] ==
3680		    XML_REGEXP_SINK_STATE)
3681		    goto error;
3682
3683		if (comp->compact[target * (comp->nbstrings + 1)] ==
3684		    XML_REGEXP_FINAL_STATE)
3685		    return(1);
3686		return(0);
3687	    }
3688	}
3689    }
3690    /*
3691     * Failed to find an exit transition out from current state for the
3692     * current token
3693     */
3694#ifdef DEBUG_PUSH
3695    printf("failed to find a transition for %s on state %d\n", value, state);
3696#endif
3697error:
3698    if (exec->errString != NULL)
3699        xmlFree(exec->errString);
3700    exec->errString = xmlStrdup(value);
3701    exec->errStateNo = state;
3702    exec->status = -1;
3703#ifdef DEBUG_ERR
3704    testerr(exec);
3705#endif
3706    return(-1);
3707}
3708
3709/**
3710 * xmlRegExecPushStringInternal:
3711 * @exec: a regexp execution context or NULL to indicate the end
3712 * @value: a string token input
3713 * @data: data associated to the token to reuse in callbacks
3714 * @compound: value was assembled from 2 strings
3715 *
3716 * Push one input token in the execution context
3717 *
3718 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
3719 *     a negative value in case of error.
3720 */
3721static int
3722xmlRegExecPushStringInternal(xmlRegExecCtxtPtr exec, const xmlChar *value,
3723	                     void *data, int compound) {
3724    xmlRegTransPtr trans;
3725    xmlRegAtomPtr atom;
3726    int ret;
3727    int final = 0;
3728    int progress = 1;
3729
3730    if (exec == NULL)
3731	return(-1);
3732    if (exec->comp == NULL)
3733	return(-1);
3734    if (exec->status != 0)
3735	return(exec->status);
3736
3737    if (exec->comp->compact != NULL)
3738	return(xmlRegCompactPushString(exec, exec->comp, value, data));
3739
3740    if (value == NULL) {
3741        if (exec->state->type == XML_REGEXP_FINAL_STATE)
3742	    return(1);
3743	final = 1;
3744    }
3745
3746#ifdef DEBUG_PUSH
3747    printf("value pushed: %s\n", value);
3748#endif
3749    /*
3750     * If we have an active rollback stack push the new value there
3751     * and get back to where we were left
3752     */
3753    if ((value != NULL) && (exec->inputStackNr > 0)) {
3754	xmlFARegExecSaveInputString(exec, value, data);
3755	value = exec->inputStack[exec->index].value;
3756	data = exec->inputStack[exec->index].data;
3757#ifdef DEBUG_PUSH
3758	printf("value loaded: %s\n", value);
3759#endif
3760    }
3761
3762    while ((exec->status == 0) &&
3763	   ((value != NULL) ||
3764	    ((final == 1) &&
3765	     (exec->state->type != XML_REGEXP_FINAL_STATE)))) {
3766
3767	/*
3768	 * End of input on non-terminal state, rollback, however we may
3769	 * still have epsilon like transition for counted transitions
3770	 * on counters, in that case don't break too early.
3771	 */
3772	if ((value == NULL) && (exec->counts == NULL))
3773	    goto rollback;
3774
3775	exec->transcount = 0;
3776	for (;exec->transno < exec->state->nbTrans;exec->transno++) {
3777	    trans = &exec->state->trans[exec->transno];
3778	    if (trans->to < 0)
3779		continue;
3780	    atom = trans->atom;
3781	    ret = 0;
3782	    if (trans->count == REGEXP_ALL_LAX_COUNTER) {
3783		int i;
3784		int count;
3785		xmlRegTransPtr t;
3786		xmlRegCounterPtr counter;
3787
3788		ret = 0;
3789
3790#ifdef DEBUG_PUSH
3791		printf("testing all lax %d\n", trans->count);
3792#endif
3793		/*
3794		 * Check all counted transitions from the current state
3795		 */
3796		if ((value == NULL) && (final)) {
3797		    ret = 1;
3798		} else if (value != NULL) {
3799		    for (i = 0;i < exec->state->nbTrans;i++) {
3800			t = &exec->state->trans[i];
3801			if ((t->counter < 0) || (t == trans))
3802			    continue;
3803			counter = &exec->comp->counters[t->counter];
3804			count = exec->counts[t->counter];
3805			if ((count < counter->max) &&
3806		            (t->atom != NULL) &&
3807			    (xmlStrEqual(value, t->atom->valuep))) {
3808			    ret = 0;
3809			    break;
3810			}
3811			if ((count >= counter->min) &&
3812			    (count < counter->max) &&
3813			    (t->atom != NULL) &&
3814			    (xmlStrEqual(value, t->atom->valuep))) {
3815			    ret = 1;
3816			    break;
3817			}
3818		    }
3819		}
3820	    } else if (trans->count == REGEXP_ALL_COUNTER) {
3821		int i;
3822		int count;
3823		xmlRegTransPtr t;
3824		xmlRegCounterPtr counter;
3825
3826		ret = 1;
3827
3828#ifdef DEBUG_PUSH
3829		printf("testing all %d\n", trans->count);
3830#endif
3831		/*
3832		 * Check all counted transitions from the current state
3833		 */
3834		for (i = 0;i < exec->state->nbTrans;i++) {
3835                    t = &exec->state->trans[i];
3836		    if ((t->counter < 0) || (t == trans))
3837			continue;
3838                    counter = &exec->comp->counters[t->counter];
3839		    count = exec->counts[t->counter];
3840		    if ((count < counter->min) || (count > counter->max)) {
3841			ret = 0;
3842			break;
3843		    }
3844		}
3845	    } else if (trans->count >= 0) {
3846		int count;
3847		xmlRegCounterPtr counter;
3848
3849		/*
3850		 * A counted transition.
3851		 */
3852
3853		count = exec->counts[trans->count];
3854		counter = &exec->comp->counters[trans->count];
3855#ifdef DEBUG_PUSH
3856		printf("testing count %d: val %d, min %d, max %d\n",
3857		       trans->count, count, counter->min,  counter->max);
3858#endif
3859		ret = ((count >= counter->min) && (count <= counter->max));
3860	    } else if (atom == NULL) {
3861		fprintf(stderr, "epsilon transition left at runtime\n");
3862		exec->status = -2;
3863		break;
3864	    } else if (value != NULL) {
3865		ret = xmlRegStrEqualWildcard(atom->valuep, value);
3866		if (atom->neg) {
3867		    ret = !ret;
3868		    if (!compound)
3869		        ret = 0;
3870		}
3871		if ((ret == 1) && (trans->counter >= 0)) {
3872		    xmlRegCounterPtr counter;
3873		    int count;
3874
3875		    count = exec->counts[trans->counter];
3876		    counter = &exec->comp->counters[trans->counter];
3877		    if (count >= counter->max)
3878			ret = 0;
3879		}
3880
3881		if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
3882		    xmlRegStatePtr to = exec->comp->states[trans->to];
3883
3884		    /*
3885		     * this is a multiple input sequence
3886		     */
3887		    if (exec->state->nbTrans > exec->transno + 1) {
3888			if (exec->inputStackNr <= 0) {
3889			    xmlFARegExecSaveInputString(exec, value, data);
3890			}
3891			xmlFARegExecSave(exec);
3892		    }
3893		    exec->transcount = 1;
3894		    do {
3895			/*
3896			 * Try to progress as much as possible on the input
3897			 */
3898			if (exec->transcount == atom->max) {
3899			    break;
3900			}
3901			exec->index++;
3902			value = exec->inputStack[exec->index].value;
3903			data = exec->inputStack[exec->index].data;
3904#ifdef DEBUG_PUSH
3905			printf("value loaded: %s\n", value);
3906#endif
3907
3908			/*
3909			 * End of input: stop here
3910			 */
3911			if (value == NULL) {
3912			    exec->index --;
3913			    break;
3914			}
3915			if (exec->transcount >= atom->min) {
3916			    int transno = exec->transno;
3917			    xmlRegStatePtr state = exec->state;
3918
3919			    /*
3920			     * The transition is acceptable save it
3921			     */
3922			    exec->transno = -1; /* trick */
3923			    exec->state = to;
3924			    if (exec->inputStackNr <= 0) {
3925				xmlFARegExecSaveInputString(exec, value, data);
3926			    }
3927			    xmlFARegExecSave(exec);
3928			    exec->transno = transno;
3929			    exec->state = state;
3930			}
3931			ret = xmlStrEqual(value, atom->valuep);
3932			exec->transcount++;
3933		    } while (ret == 1);
3934		    if (exec->transcount < atom->min)
3935			ret = 0;
3936
3937		    /*
3938		     * If the last check failed but one transition was found
3939		     * possible, rollback
3940		     */
3941		    if (ret < 0)
3942			ret = 0;
3943		    if (ret == 0) {
3944			goto rollback;
3945		    }
3946		}
3947	    }
3948	    if (ret == 1) {
3949		if ((exec->callback != NULL) && (atom != NULL) &&
3950			(data != NULL)) {
3951		    exec->callback(exec->data, atom->valuep,
3952			           atom->data, data);
3953		}
3954		if (exec->state->nbTrans > exec->transno + 1) {
3955		    if (exec->inputStackNr <= 0) {
3956			xmlFARegExecSaveInputString(exec, value, data);
3957		    }
3958		    xmlFARegExecSave(exec);
3959		}
3960		if (trans->counter >= 0) {
3961#ifdef DEBUG_PUSH
3962		    printf("Increasing count %d\n", trans->counter);
3963#endif
3964		    exec->counts[trans->counter]++;
3965		}
3966		if ((trans->count >= 0) &&
3967		    (trans->count < REGEXP_ALL_COUNTER)) {
3968#ifdef DEBUG_REGEXP_EXEC
3969		    printf("resetting count %d on transition\n",
3970		           trans->count);
3971#endif
3972		    exec->counts[trans->count] = 0;
3973		}
3974#ifdef DEBUG_PUSH
3975		printf("entering state %d\n", trans->to);
3976#endif
3977                if ((exec->comp->states[trans->to] != NULL) &&
3978		    (exec->comp->states[trans->to]->type ==
3979		     XML_REGEXP_SINK_STATE)) {
3980		    /*
3981		     * entering a sink state, save the current state as error
3982		     * state.
3983		     */
3984		    if (exec->errString != NULL)
3985			xmlFree(exec->errString);
3986		    exec->errString = xmlStrdup(value);
3987		    exec->errState = exec->state;
3988		    memcpy(exec->errCounts, exec->counts,
3989			   exec->comp->nbCounters * sizeof(int));
3990		}
3991		exec->state = exec->comp->states[trans->to];
3992		exec->transno = 0;
3993		if (trans->atom != NULL) {
3994		    if (exec->inputStack != NULL) {
3995			exec->index++;
3996			if (exec->index < exec->inputStackNr) {
3997			    value = exec->inputStack[exec->index].value;
3998			    data = exec->inputStack[exec->index].data;
3999#ifdef DEBUG_PUSH
4000			    printf("value loaded: %s\n", value);
4001#endif
4002			} else {
4003			    value = NULL;
4004			    data = NULL;
4005#ifdef DEBUG_PUSH
4006			    printf("end of input\n");
4007#endif
4008			}
4009		    } else {
4010			value = NULL;
4011			data = NULL;
4012#ifdef DEBUG_PUSH
4013			printf("end of input\n");
4014#endif
4015		    }
4016		}
4017		goto progress;
4018	    } else if (ret < 0) {
4019		exec->status = -4;
4020		break;
4021	    }
4022	}
4023	if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
4024rollback:
4025            /*
4026	     * if we didn't yet rollback on the current input
4027	     * store the current state as the error state.
4028	     */
4029	    if ((progress) && (exec->state != NULL) &&
4030	        (exec->state->type != XML_REGEXP_SINK_STATE)) {
4031	        progress = 0;
4032		if (exec->errString != NULL)
4033		    xmlFree(exec->errString);
4034		exec->errString = xmlStrdup(value);
4035		exec->errState = exec->state;
4036		memcpy(exec->errCounts, exec->counts,
4037		       exec->comp->nbCounters * sizeof(int));
4038	    }
4039
4040	    /*
4041	     * Failed to find a way out
4042	     */
4043	    exec->determinist = 0;
4044	    xmlFARegExecRollBack(exec);
4045	    if (exec->status == 0) {
4046		value = exec->inputStack[exec->index].value;
4047		data = exec->inputStack[exec->index].data;
4048#ifdef DEBUG_PUSH
4049		printf("value loaded: %s\n", value);
4050#endif
4051	    }
4052	}
4053	continue;
4054progress:
4055        progress = 1;
4056	continue;
4057    }
4058    if (exec->status == 0) {
4059        return(exec->state->type == XML_REGEXP_FINAL_STATE);
4060    }
4061#ifdef DEBUG_ERR
4062    if (exec->status < 0) {
4063	testerr(exec);
4064    }
4065#endif
4066    return(exec->status);
4067}
4068
4069/**
4070 * xmlRegExecPushString:
4071 * @exec: a regexp execution context or NULL to indicate the end
4072 * @value: a string token input
4073 * @data: data associated to the token to reuse in callbacks
4074 *
4075 * Push one input token in the execution context
4076 *
4077 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
4078 *     a negative value in case of error.
4079 */
4080int
4081xmlRegExecPushString(xmlRegExecCtxtPtr exec, const xmlChar *value,
4082	             void *data) {
4083    return(xmlRegExecPushStringInternal(exec, value, data, 0));
4084}
4085
4086/**
4087 * xmlRegExecPushString2:
4088 * @exec: a regexp execution context or NULL to indicate the end
4089 * @value: the first string token input
4090 * @value2: the second string token input
4091 * @data: data associated to the token to reuse in callbacks
4092 *
4093 * Push one input token in the execution context
4094 *
4095 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
4096 *     a negative value in case of error.
4097 */
4098int
4099xmlRegExecPushString2(xmlRegExecCtxtPtr exec, const xmlChar *value,
4100                      const xmlChar *value2, void *data) {
4101    xmlChar buf[150];
4102    int lenn, lenp, ret;
4103    xmlChar *str;
4104
4105    if (exec == NULL)
4106	return(-1);
4107    if (exec->comp == NULL)
4108	return(-1);
4109    if (exec->status != 0)
4110	return(exec->status);
4111
4112    if (value2 == NULL)
4113        return(xmlRegExecPushString(exec, value, data));
4114
4115    lenn = strlen((char *) value2);
4116    lenp = strlen((char *) value);
4117
4118    if (150 < lenn + lenp + 2) {
4119	str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
4120	if (str == NULL) {
4121	    exec->status = -1;
4122	    return(-1);
4123	}
4124    } else {
4125	str = buf;
4126    }
4127    memcpy(&str[0], value, lenp);
4128    str[lenp] = XML_REG_STRING_SEPARATOR;
4129    memcpy(&str[lenp + 1], value2, lenn);
4130    str[lenn + lenp + 1] = 0;
4131
4132    if (exec->comp->compact != NULL)
4133	ret = xmlRegCompactPushString(exec, exec->comp, str, data);
4134    else
4135        ret = xmlRegExecPushStringInternal(exec, str, data, 1);
4136
4137    if (str != buf)
4138        xmlFree(str);
4139    return(ret);
4140}
4141
4142/**
4143 * xmlRegExecGetValues:
4144 * @exec: a regexp execution context
4145 * @err: error extraction or normal one
4146 * @nbval: pointer to the number of accepted values IN/OUT
4147 * @nbneg: return number of negative transitions
4148 * @values: pointer to the array of acceptable values
4149 * @terminal: return value if this was a terminal state
4150 *
4151 * Extract informations from the regexp execution, internal routine to
4152 * implement xmlRegExecNextValues() and xmlRegExecErrInfo()
4153 *
4154 * Returns: 0 in case of success or -1 in case of error.
4155 */
4156static int
4157xmlRegExecGetValues(xmlRegExecCtxtPtr exec, int err,
4158                    int *nbval, int *nbneg,
4159		    xmlChar **values, int *terminal) {
4160    int maxval;
4161    int nb = 0;
4162
4163    if ((exec == NULL) || (nbval == NULL) || (nbneg == NULL) ||
4164        (values == NULL) || (*nbval <= 0))
4165        return(-1);
4166
4167    maxval = *nbval;
4168    *nbval = 0;
4169    *nbneg = 0;
4170    if ((exec->comp != NULL) && (exec->comp->compact != NULL)) {
4171        xmlRegexpPtr comp;
4172	int target, i, state;
4173
4174        comp = exec->comp;
4175
4176	if (err) {
4177	    if (exec->errStateNo == -1) return(-1);
4178	    state = exec->errStateNo;
4179	} else {
4180	    state = exec->index;
4181	}
4182	if (terminal != NULL) {
4183	    if (comp->compact[state * (comp->nbstrings + 1)] ==
4184	        XML_REGEXP_FINAL_STATE)
4185		*terminal = 1;
4186	    else
4187		*terminal = 0;
4188	}
4189	for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) {
4190	    target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
4191	    if ((target > 0) && (target <= comp->nbstates) &&
4192	        (comp->compact[(target - 1) * (comp->nbstrings + 1)] !=
4193		 XML_REGEXP_SINK_STATE)) {
4194	        values[nb++] = comp->stringMap[i];
4195		(*nbval)++;
4196	    }
4197	}
4198	for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) {
4199	    target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
4200	    if ((target > 0) && (target <= comp->nbstates) &&
4201	        (comp->compact[(target - 1) * (comp->nbstrings + 1)] ==
4202		 XML_REGEXP_SINK_STATE)) {
4203	        values[nb++] = comp->stringMap[i];
4204		(*nbneg)++;
4205	    }
4206	}
4207    } else {
4208        int transno;
4209	xmlRegTransPtr trans;
4210	xmlRegAtomPtr atom;
4211	xmlRegStatePtr state;
4212
4213	if (terminal != NULL) {
4214	    if (exec->state->type == XML_REGEXP_FINAL_STATE)
4215		*terminal = 1;
4216	    else
4217		*terminal = 0;
4218	}
4219
4220	if (err) {
4221	    if (exec->errState == NULL) return(-1);
4222	    state = exec->errState;
4223	} else {
4224	    if (exec->state == NULL) return(-1);
4225	    state = exec->state;
4226	}
4227	for (transno = 0;
4228	     (transno < state->nbTrans) && (nb < maxval);
4229	     transno++) {
4230	    trans = &state->trans[transno];
4231	    if (trans->to < 0)
4232		continue;
4233	    atom = trans->atom;
4234	    if ((atom == NULL) || (atom->valuep == NULL))
4235		continue;
4236	    if (trans->count == REGEXP_ALL_LAX_COUNTER) {
4237	        /* this should not be reached but ... */
4238	        TODO;
4239	    } else if (trans->count == REGEXP_ALL_COUNTER) {
4240	        /* this should not be reached but ... */
4241	        TODO;
4242	    } else if (trans->counter >= 0) {
4243		xmlRegCounterPtr counter = NULL;
4244		int count;
4245
4246		if (err)
4247		    count = exec->errCounts[trans->counter];
4248		else
4249		    count = exec->counts[trans->counter];
4250		if (exec->comp != NULL)
4251		    counter = &exec->comp->counters[trans->counter];
4252		if ((counter == NULL) || (count < counter->max)) {
4253		    if (atom->neg)
4254			values[nb++] = (xmlChar *) atom->valuep2;
4255		    else
4256			values[nb++] = (xmlChar *) atom->valuep;
4257		    (*nbval)++;
4258		}
4259	    } else {
4260                if ((exec->comp->states[trans->to] != NULL) &&
4261		    (exec->comp->states[trans->to]->type !=
4262		     XML_REGEXP_SINK_STATE)) {
4263		    if (atom->neg)
4264			values[nb++] = (xmlChar *) atom->valuep2;
4265		    else
4266			values[nb++] = (xmlChar *) atom->valuep;
4267		    (*nbval)++;
4268		}
4269	    }
4270	}
4271	for (transno = 0;
4272	     (transno < state->nbTrans) && (nb < maxval);
4273	     transno++) {
4274	    trans = &state->trans[transno];
4275	    if (trans->to < 0)
4276		continue;
4277	    atom = trans->atom;
4278	    if ((atom == NULL) || (atom->valuep == NULL))
4279		continue;
4280	    if (trans->count == REGEXP_ALL_LAX_COUNTER) {
4281	        continue;
4282	    } else if (trans->count == REGEXP_ALL_COUNTER) {
4283	        continue;
4284	    } else if (trans->counter >= 0) {
4285	        continue;
4286	    } else {
4287                if ((exec->comp->states[trans->to] != NULL) &&
4288		    (exec->comp->states[trans->to]->type ==
4289		     XML_REGEXP_SINK_STATE)) {
4290		    if (atom->neg)
4291			values[nb++] = (xmlChar *) atom->valuep2;
4292		    else
4293			values[nb++] = (xmlChar *) atom->valuep;
4294		    (*nbneg)++;
4295		}
4296	    }
4297	}
4298    }
4299    return(0);
4300}
4301
4302/**
4303 * xmlRegExecNextValues:
4304 * @exec: a regexp execution context
4305 * @nbval: pointer to the number of accepted values IN/OUT
4306 * @nbneg: return number of negative transitions
4307 * @values: pointer to the array of acceptable values
4308 * @terminal: return value if this was a terminal state
4309 *
4310 * Extract informations from the regexp execution,
4311 * the parameter @values must point to an array of @nbval string pointers
4312 * on return nbval will contain the number of possible strings in that
4313 * state and the @values array will be updated with them. The string values
4314 * returned will be freed with the @exec context and don't need to be
4315 * deallocated.
4316 *
4317 * Returns: 0 in case of success or -1 in case of error.
4318 */
4319int
4320xmlRegExecNextValues(xmlRegExecCtxtPtr exec, int *nbval, int *nbneg,
4321                     xmlChar **values, int *terminal) {
4322    return(xmlRegExecGetValues(exec, 0, nbval, nbneg, values, terminal));
4323}
4324
4325/**
4326 * xmlRegExecErrInfo:
4327 * @exec: a regexp execution context generating an error
4328 * @string: return value for the error string
4329 * @nbval: pointer to the number of accepted values IN/OUT
4330 * @nbneg: return number of negative transitions
4331 * @values: pointer to the array of acceptable values
4332 * @terminal: return value if this was a terminal state
4333 *
4334 * Extract error informations from the regexp execution, the parameter
4335 * @string will be updated with the value pushed and not accepted,
4336 * the parameter @values must point to an array of @nbval string pointers
4337 * on return nbval will contain the number of possible strings in that
4338 * state and the @values array will be updated with them. The string values
4339 * returned will be freed with the @exec context and don't need to be
4340 * deallocated.
4341 *
4342 * Returns: 0 in case of success or -1 in case of error.
4343 */
4344int
4345xmlRegExecErrInfo(xmlRegExecCtxtPtr exec, const xmlChar **string,
4346                  int *nbval, int *nbneg, xmlChar **values, int *terminal) {
4347    if (exec == NULL)
4348        return(-1);
4349    if (string != NULL) {
4350        if (exec->status != 0)
4351	    *string = exec->errString;
4352	else
4353	    *string = NULL;
4354    }
4355    return(xmlRegExecGetValues(exec, 1, nbval, nbneg, values, terminal));
4356}
4357
4358#ifdef DEBUG_ERR
4359static void testerr(xmlRegExecCtxtPtr exec) {
4360    const xmlChar *string;
4361    xmlChar *values[5];
4362    int nb = 5;
4363    int nbneg;
4364    int terminal;
4365    xmlRegExecErrInfo(exec, &string, &nb, &nbneg, &values[0], &terminal);
4366}
4367#endif
4368
4369#if 0
4370static int
4371xmlRegExecPushChar(xmlRegExecCtxtPtr exec, int UCS) {
4372    xmlRegTransPtr trans;
4373    xmlRegAtomPtr atom;
4374    int ret;
4375    int codepoint, len;
4376
4377    if (exec == NULL)
4378	return(-1);
4379    if (exec->status != 0)
4380	return(exec->status);
4381
4382    while ((exec->status == 0) &&
4383	   ((exec->inputString[exec->index] != 0) ||
4384	    (exec->state->type != XML_REGEXP_FINAL_STATE))) {
4385
4386	/*
4387	 * End of input on non-terminal state, rollback, however we may
4388	 * still have epsilon like transition for counted transitions
4389	 * on counters, in that case don't break too early.
4390	 */
4391	if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL))
4392	    goto rollback;
4393
4394	exec->transcount = 0;
4395	for (;exec->transno < exec->state->nbTrans;exec->transno++) {
4396	    trans = &exec->state->trans[exec->transno];
4397	    if (trans->to < 0)
4398		continue;
4399	    atom = trans->atom;
4400	    ret = 0;
4401	    if (trans->count >= 0) {
4402		int count;
4403		xmlRegCounterPtr counter;
4404
4405		/*
4406		 * A counted transition.
4407		 */
4408
4409		count = exec->counts[trans->count];
4410		counter = &exec->comp->counters[trans->count];
4411#ifdef DEBUG_REGEXP_EXEC
4412		printf("testing count %d: val %d, min %d, max %d\n",
4413		       trans->count, count, counter->min,  counter->max);
4414#endif
4415		ret = ((count >= counter->min) && (count <= counter->max));
4416	    } else if (atom == NULL) {
4417		fprintf(stderr, "epsilon transition left at runtime\n");
4418		exec->status = -2;
4419		break;
4420	    } else if (exec->inputString[exec->index] != 0) {
4421                codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len);
4422		ret = xmlRegCheckCharacter(atom, codepoint);
4423		if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
4424		    xmlRegStatePtr to = exec->comp->states[trans->to];
4425
4426		    /*
4427		     * this is a multiple input sequence
4428		     */
4429		    if (exec->state->nbTrans > exec->transno + 1) {
4430			xmlFARegExecSave(exec);
4431		    }
4432		    exec->transcount = 1;
4433		    do {
4434			/*
4435			 * Try to progress as much as possible on the input
4436			 */
4437			if (exec->transcount == atom->max) {
4438			    break;
4439			}
4440			exec->index += len;
4441			/*
4442			 * End of input: stop here
4443			 */
4444			if (exec->inputString[exec->index] == 0) {
4445			    exec->index -= len;
4446			    break;
4447			}
4448			if (exec->transcount >= atom->min) {
4449			    int transno = exec->transno;
4450			    xmlRegStatePtr state = exec->state;
4451
4452			    /*
4453			     * The transition is acceptable save it
4454			     */
4455			    exec->transno = -1; /* trick */
4456			    exec->state = to;
4457			    xmlFARegExecSave(exec);
4458			    exec->transno = transno;
4459			    exec->state = state;
4460			}
4461			codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),
4462				              len);
4463			ret = xmlRegCheckCharacter(atom, codepoint);
4464			exec->transcount++;
4465		    } while (ret == 1);
4466		    if (exec->transcount < atom->min)
4467			ret = 0;
4468
4469		    /*
4470		     * If the last check failed but one transition was found
4471		     * possible, rollback
4472		     */
4473		    if (ret < 0)
4474			ret = 0;
4475		    if (ret == 0) {
4476			goto rollback;
4477		    }
4478		}
4479	    }
4480	    if (ret == 1) {
4481		if (exec->state->nbTrans > exec->transno + 1) {
4482		    xmlFARegExecSave(exec);
4483		}
4484		/*
4485		 * restart count for expressions like this ((abc){2})*
4486		 */
4487		if (trans->count >= 0) {
4488#ifdef DEBUG_REGEXP_EXEC
4489		    printf("Reset count %d\n", trans->count);
4490#endif
4491		    exec->counts[trans->count] = 0;
4492		}
4493		if (trans->counter >= 0) {
4494#ifdef DEBUG_REGEXP_EXEC
4495		    printf("Increasing count %d\n", trans->counter);
4496#endif
4497		    exec->counts[trans->counter]++;
4498		}
4499#ifdef DEBUG_REGEXP_EXEC
4500		printf("entering state %d\n", trans->to);
4501#endif
4502		exec->state = exec->comp->states[trans->to];
4503		exec->transno = 0;
4504		if (trans->atom != NULL) {
4505		    exec->index += len;
4506		}
4507		goto progress;
4508	    } else if (ret < 0) {
4509		exec->status = -4;
4510		break;
4511	    }
4512	}
4513	if ((exec->transno != 0) || (exec->state->nbTrans == 0)) {
4514rollback:
4515	    /*
4516	     * Failed to find a way out
4517	     */
4518	    exec->determinist = 0;
4519	    xmlFARegExecRollBack(exec);
4520	}
4521progress:
4522	continue;
4523    }
4524}
4525#endif
4526/************************************************************************
4527 * 									*
4528 *	Parser for the Schemas Datatype Regular Expressions		*
4529 *	http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/#regexs	*
4530 * 									*
4531 ************************************************************************/
4532
4533/**
4534 * xmlFAIsChar:
4535 * @ctxt:  a regexp parser context
4536 *
4537 * [10]   Char   ::=   [^.\?*+()|#x5B#x5D]
4538 */
4539static int
4540xmlFAIsChar(xmlRegParserCtxtPtr ctxt) {
4541    int cur;
4542    int len;
4543
4544    cur = CUR_SCHAR(ctxt->cur, len);
4545    if ((cur == '.') || (cur == '\\') || (cur == '?') ||
4546	(cur == '*') || (cur == '+') || (cur == '(') ||
4547	(cur == ')') || (cur == '|') || (cur == 0x5B) ||
4548	(cur == 0x5D) || (cur == 0))
4549	return(-1);
4550    return(cur);
4551}
4552
4553/**
4554 * xmlFAParseCharProp:
4555 * @ctxt:  a regexp parser context
4556 *
4557 * [27]   charProp   ::=   IsCategory | IsBlock
4558 * [28]   IsCategory ::= Letters | Marks | Numbers | Punctuation |
4559 *                       Separators | Symbols | Others
4560 * [29]   Letters   ::=   'L' [ultmo]?
4561 * [30]   Marks   ::=   'M' [nce]?
4562 * [31]   Numbers   ::=   'N' [dlo]?
4563 * [32]   Punctuation   ::=   'P' [cdseifo]?
4564 * [33]   Separators   ::=   'Z' [slp]?
4565 * [34]   Symbols   ::=   'S' [mcko]?
4566 * [35]   Others   ::=   'C' [cfon]?
4567 * [36]   IsBlock   ::=   'Is' [a-zA-Z0-9#x2D]+
4568 */
4569static void
4570xmlFAParseCharProp(xmlRegParserCtxtPtr ctxt) {
4571    int cur;
4572    xmlRegAtomType type = (xmlRegAtomType) 0;
4573    xmlChar *blockName = NULL;
4574
4575    cur = CUR;
4576    if (cur == 'L') {
4577	NEXT;
4578	cur = CUR;
4579	if (cur == 'u') {
4580	    NEXT;
4581	    type = XML_REGEXP_LETTER_UPPERCASE;
4582	} else if (cur == 'l') {
4583	    NEXT;
4584	    type = XML_REGEXP_LETTER_LOWERCASE;
4585	} else if (cur == 't') {
4586	    NEXT;
4587	    type = XML_REGEXP_LETTER_TITLECASE;
4588	} else if (cur == 'm') {
4589	    NEXT;
4590	    type = XML_REGEXP_LETTER_MODIFIER;
4591	} else if (cur == 'o') {
4592	    NEXT;
4593	    type = XML_REGEXP_LETTER_OTHERS;
4594	} else {
4595	    type = XML_REGEXP_LETTER;
4596	}
4597    } else if (cur == 'M') {
4598	NEXT;
4599	cur = CUR;
4600	if (cur == 'n') {
4601	    NEXT;
4602	    /* nonspacing */
4603	    type = XML_REGEXP_MARK_NONSPACING;
4604	} else if (cur == 'c') {
4605	    NEXT;
4606	    /* spacing combining */
4607	    type = XML_REGEXP_MARK_SPACECOMBINING;
4608	} else if (cur == 'e') {
4609	    NEXT;
4610	    /* enclosing */
4611	    type = XML_REGEXP_MARK_ENCLOSING;
4612	} else {
4613	    /* all marks */
4614	    type = XML_REGEXP_MARK;
4615	}
4616    } else if (cur == 'N') {
4617	NEXT;
4618	cur = CUR;
4619	if (cur == 'd') {
4620	    NEXT;
4621	    /* digital */
4622	    type = XML_REGEXP_NUMBER_DECIMAL;
4623	} else if (cur == 'l') {
4624	    NEXT;
4625	    /* letter */
4626	    type = XML_REGEXP_NUMBER_LETTER;
4627	} else if (cur == 'o') {
4628	    NEXT;
4629	    /* other */
4630	    type = XML_REGEXP_NUMBER_OTHERS;
4631	} else {
4632	    /* all numbers */
4633	    type = XML_REGEXP_NUMBER;
4634	}
4635    } else if (cur == 'P') {
4636	NEXT;
4637	cur = CUR;
4638	if (cur == 'c') {
4639	    NEXT;
4640	    /* connector */
4641	    type = XML_REGEXP_PUNCT_CONNECTOR;
4642	} else if (cur == 'd') {
4643	    NEXT;
4644	    /* dash */
4645	    type = XML_REGEXP_PUNCT_DASH;
4646	} else if (cur == 's') {
4647	    NEXT;
4648	    /* open */
4649	    type = XML_REGEXP_PUNCT_OPEN;
4650	} else if (cur == 'e') {
4651	    NEXT;
4652	    /* close */
4653	    type = XML_REGEXP_PUNCT_CLOSE;
4654	} else if (cur == 'i') {
4655	    NEXT;
4656	    /* initial quote */
4657	    type = XML_REGEXP_PUNCT_INITQUOTE;
4658	} else if (cur == 'f') {
4659	    NEXT;
4660	    /* final quote */
4661	    type = XML_REGEXP_PUNCT_FINQUOTE;
4662	} else if (cur == 'o') {
4663	    NEXT;
4664	    /* other */
4665	    type = XML_REGEXP_PUNCT_OTHERS;
4666	} else {
4667	    /* all punctuation */
4668	    type = XML_REGEXP_PUNCT;
4669	}
4670    } else if (cur == 'Z') {
4671	NEXT;
4672	cur = CUR;
4673	if (cur == 's') {
4674	    NEXT;
4675	    /* space */
4676	    type = XML_REGEXP_SEPAR_SPACE;
4677	} else if (cur == 'l') {
4678	    NEXT;
4679	    /* line */
4680	    type = XML_REGEXP_SEPAR_LINE;
4681	} else if (cur == 'p') {
4682	    NEXT;
4683	    /* paragraph */
4684	    type = XML_REGEXP_SEPAR_PARA;
4685	} else {
4686	    /* all separators */
4687	    type = XML_REGEXP_SEPAR;
4688	}
4689    } else if (cur == 'S') {
4690	NEXT;
4691	cur = CUR;
4692	if (cur == 'm') {
4693	    NEXT;
4694	    type = XML_REGEXP_SYMBOL_MATH;
4695	    /* math */
4696	} else if (cur == 'c') {
4697	    NEXT;
4698	    type = XML_REGEXP_SYMBOL_CURRENCY;
4699	    /* currency */
4700	} else if (cur == 'k') {
4701	    NEXT;
4702	    type = XML_REGEXP_SYMBOL_MODIFIER;
4703	    /* modifiers */
4704	} else if (cur == 'o') {
4705	    NEXT;
4706	    type = XML_REGEXP_SYMBOL_OTHERS;
4707	    /* other */
4708	} else {
4709	    /* all symbols */
4710	    type = XML_REGEXP_SYMBOL;
4711	}
4712    } else if (cur == 'C') {
4713	NEXT;
4714	cur = CUR;
4715	if (cur == 'c') {
4716	    NEXT;
4717	    /* control */
4718	    type = XML_REGEXP_OTHER_CONTROL;
4719	} else if (cur == 'f') {
4720	    NEXT;
4721	    /* format */
4722	    type = XML_REGEXP_OTHER_FORMAT;
4723	} else if (cur == 'o') {
4724	    NEXT;
4725	    /* private use */
4726	    type = XML_REGEXP_OTHER_PRIVATE;
4727	} else if (cur == 'n') {
4728	    NEXT;
4729	    /* not assigned */
4730	    type = XML_REGEXP_OTHER_NA;
4731	} else {
4732	    /* all others */
4733	    type = XML_REGEXP_OTHER;
4734	}
4735    } else if (cur == 'I') {
4736	const xmlChar *start;
4737	NEXT;
4738	cur = CUR;
4739	if (cur != 's') {
4740	    ERROR("IsXXXX expected");
4741	    return;
4742	}
4743	NEXT;
4744	start = ctxt->cur;
4745	cur = CUR;
4746	if (((cur >= 'a') && (cur <= 'z')) ||
4747	    ((cur >= 'A') && (cur <= 'Z')) ||
4748	    ((cur >= '0') && (cur <= '9')) ||
4749	    (cur == 0x2D)) {
4750	    NEXT;
4751	    cur = CUR;
4752	    while (((cur >= 'a') && (cur <= 'z')) ||
4753		((cur >= 'A') && (cur <= 'Z')) ||
4754		((cur >= '0') && (cur <= '9')) ||
4755		(cur == 0x2D)) {
4756		NEXT;
4757		cur = CUR;
4758	    }
4759	}
4760	type = XML_REGEXP_BLOCK_NAME;
4761	blockName = xmlStrndup(start, ctxt->cur - start);
4762    } else {
4763	ERROR("Unknown char property");
4764	return;
4765    }
4766    if (ctxt->atom == NULL) {
4767	ctxt->atom = xmlRegNewAtom(ctxt, type);
4768	if (ctxt->atom != NULL)
4769	    ctxt->atom->valuep = blockName;
4770    } else if (ctxt->atom->type == XML_REGEXP_RANGES) {
4771        xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4772		           type, 0, 0, blockName);
4773    }
4774}
4775
4776/**
4777 * xmlFAParseCharClassEsc:
4778 * @ctxt:  a regexp parser context
4779 *
4780 * [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc | complEsc )
4781 * [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E]
4782 * [25] catEsc   ::=   '\p{' charProp '}'
4783 * [26] complEsc ::=   '\P{' charProp '}'
4784 * [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW])
4785 */
4786static void
4787xmlFAParseCharClassEsc(xmlRegParserCtxtPtr ctxt) {
4788    int cur;
4789
4790    if (CUR == '.') {
4791	if (ctxt->atom == NULL) {
4792	    ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_ANYCHAR);
4793	} else if (ctxt->atom->type == XML_REGEXP_RANGES) {
4794	    xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4795			       XML_REGEXP_ANYCHAR, 0, 0, NULL);
4796	}
4797	NEXT;
4798	return;
4799    }
4800    if (CUR != '\\') {
4801	ERROR("Escaped sequence: expecting \\");
4802	return;
4803    }
4804    NEXT;
4805    cur = CUR;
4806    if (cur == 'p') {
4807	NEXT;
4808	if (CUR != '{') {
4809	    ERROR("Expecting '{'");
4810	    return;
4811	}
4812	NEXT;
4813	xmlFAParseCharProp(ctxt);
4814	if (CUR != '}') {
4815	    ERROR("Expecting '}'");
4816	    return;
4817	}
4818	NEXT;
4819    } else if (cur == 'P') {
4820	NEXT;
4821	if (CUR != '{') {
4822	    ERROR("Expecting '{'");
4823	    return;
4824	}
4825	NEXT;
4826	xmlFAParseCharProp(ctxt);
4827	ctxt->atom->neg = 1;
4828	if (CUR != '}') {
4829	    ERROR("Expecting '}'");
4830	    return;
4831	}
4832	NEXT;
4833    } else if ((cur == 'n') || (cur == 'r') || (cur == 't') || (cur == '\\') ||
4834	(cur == '|') || (cur == '.') || (cur == '?') || (cur == '*') ||
4835	(cur == '+') || (cur == '(') || (cur == ')') || (cur == '{') ||
4836	(cur == '}') || (cur == 0x2D) || (cur == 0x5B) || (cur == 0x5D) ||
4837	(cur == 0x5E)) {
4838	if (ctxt->atom == NULL) {
4839	    ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);
4840	    if (ctxt->atom != NULL) {
4841	        switch (cur) {
4842		    case 'n':
4843		        ctxt->atom->codepoint = '\n';
4844			break;
4845		    case 'r':
4846		        ctxt->atom->codepoint = '\r';
4847			break;
4848		    case 't':
4849		        ctxt->atom->codepoint = '\t';
4850			break;
4851		    default:
4852			ctxt->atom->codepoint = cur;
4853		}
4854	    }
4855	} else if (ctxt->atom->type == XML_REGEXP_RANGES) {
4856	    xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4857			       XML_REGEXP_CHARVAL, cur, cur, NULL);
4858	}
4859	NEXT;
4860    } else if ((cur == 's') || (cur == 'S') || (cur == 'i') || (cur == 'I') ||
4861	(cur == 'c') || (cur == 'C') || (cur == 'd') || (cur == 'D') ||
4862	(cur == 'w') || (cur == 'W')) {
4863	xmlRegAtomType type = XML_REGEXP_ANYSPACE;
4864
4865	switch (cur) {
4866	    case 's':
4867		type = XML_REGEXP_ANYSPACE;
4868		break;
4869	    case 'S':
4870		type = XML_REGEXP_NOTSPACE;
4871		break;
4872	    case 'i':
4873		type = XML_REGEXP_INITNAME;
4874		break;
4875	    case 'I':
4876		type = XML_REGEXP_NOTINITNAME;
4877		break;
4878	    case 'c':
4879		type = XML_REGEXP_NAMECHAR;
4880		break;
4881	    case 'C':
4882		type = XML_REGEXP_NOTNAMECHAR;
4883		break;
4884	    case 'd':
4885		type = XML_REGEXP_DECIMAL;
4886		break;
4887	    case 'D':
4888		type = XML_REGEXP_NOTDECIMAL;
4889		break;
4890	    case 'w':
4891		type = XML_REGEXP_REALCHAR;
4892		break;
4893	    case 'W':
4894		type = XML_REGEXP_NOTREALCHAR;
4895		break;
4896	}
4897	NEXT;
4898	if (ctxt->atom == NULL) {
4899	    ctxt->atom = xmlRegNewAtom(ctxt, type);
4900	} else if (ctxt->atom->type == XML_REGEXP_RANGES) {
4901	    xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4902			       type, 0, 0, NULL);
4903	}
4904    } else {
4905	ERROR("Wrong escape sequence, misuse of character '\\'");
4906    }
4907}
4908
4909/**
4910 * xmlFAParseCharRange:
4911 * @ctxt:  a regexp parser context
4912 *
4913 * [17]   charRange   ::=     seRange | XmlCharRef | XmlCharIncDash
4914 * [18]   seRange   ::=   charOrEsc '-' charOrEsc
4915 * [20]   charOrEsc   ::=   XmlChar | SingleCharEsc
4916 * [21]   XmlChar   ::=   [^\#x2D#x5B#x5D]
4917 * [22]   XmlCharIncDash   ::=   [^\#x5B#x5D]
4918 */
4919static void
4920xmlFAParseCharRange(xmlRegParserCtxtPtr ctxt) {
4921    int cur, len;
4922    int start = -1;
4923    int end = -1;
4924
4925    if (CUR == '\0') {
4926        ERROR("Expecting ']'");
4927	return;
4928    }
4929
4930    cur = CUR;
4931    if (cur == '\\') {
4932	NEXT;
4933	cur = CUR;
4934	switch (cur) {
4935	    case 'n': start = 0xA; break;
4936	    case 'r': start = 0xD; break;
4937	    case 't': start = 0x9; break;
4938	    case '\\': case '|': case '.': case '-': case '^': case '?':
4939	    case '*': case '+': case '{': case '}': case '(': case ')':
4940	    case '[': case ']':
4941		start = cur; break;
4942	    default:
4943		ERROR("Invalid escape value");
4944		return;
4945	}
4946	end = start;
4947        len = 1;
4948    } else if ((cur != 0x5B) && (cur != 0x5D)) {
4949        end = start = CUR_SCHAR(ctxt->cur, len);
4950    } else {
4951	ERROR("Expecting a char range");
4952	return;
4953    }
4954    /*
4955     * Since we are "inside" a range, we can assume ctxt->cur is past
4956     * the start of ctxt->string, and PREV should be safe
4957     */
4958    if ((start == '-') && (NXT(1) != ']') && (PREV != '[') && (PREV != '^')) {
4959	NEXTL(len);
4960	return;
4961    }
4962    NEXTL(len);
4963    cur = CUR;
4964    if ((cur != '-') || (NXT(1) == ']')) {
4965        xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4966		              XML_REGEXP_CHARVAL, start, end, NULL);
4967	return;
4968    }
4969    NEXT;
4970    cur = CUR;
4971    if (cur == '\\') {
4972	NEXT;
4973	cur = CUR;
4974	switch (cur) {
4975	    case 'n': end = 0xA; break;
4976	    case 'r': end = 0xD; break;
4977	    case 't': end = 0x9; break;
4978	    case '\\': case '|': case '.': case '-': case '^': case '?':
4979	    case '*': case '+': case '{': case '}': case '(': case ')':
4980	    case '[': case ']':
4981		end = cur; break;
4982	    default:
4983		ERROR("Invalid escape value");
4984		return;
4985	}
4986        len = 1;
4987    } else if ((cur != 0x5B) && (cur != 0x5D)) {
4988        end = CUR_SCHAR(ctxt->cur, len);
4989    } else {
4990	ERROR("Expecting the end of a char range");
4991	return;
4992    }
4993    NEXTL(len);
4994    /* TODO check that the values are acceptable character ranges for XML */
4995    if (end < start) {
4996	ERROR("End of range is before start of range");
4997    } else {
4998        xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,
4999		           XML_REGEXP_CHARVAL, start, end, NULL);
5000    }
5001    return;
5002}
5003
5004/**
5005 * xmlFAParsePosCharGroup:
5006 * @ctxt:  a regexp parser context
5007 *
5008 * [14]   posCharGroup ::= ( charRange | charClassEsc  )+
5009 */
5010static void
5011xmlFAParsePosCharGroup(xmlRegParserCtxtPtr ctxt) {
5012    do {
5013	if (CUR == '\\') {
5014	    xmlFAParseCharClassEsc(ctxt);
5015	} else {
5016	    xmlFAParseCharRange(ctxt);
5017	}
5018    } while ((CUR != ']') && (CUR != '^') && (CUR != '-') &&
5019             (CUR != 0) && (ctxt->error == 0));
5020}
5021
5022/**
5023 * xmlFAParseCharGroup:
5024 * @ctxt:  a regexp parser context
5025 *
5026 * [13]   charGroup    ::= posCharGroup | negCharGroup | charClassSub
5027 * [15]   negCharGroup ::= '^' posCharGroup
5028 * [16]   charClassSub ::= ( posCharGroup | negCharGroup ) '-' charClassExpr
5029 * [12]   charClassExpr ::= '[' charGroup ']'
5030 */
5031static void
5032xmlFAParseCharGroup(xmlRegParserCtxtPtr ctxt) {
5033    int n = ctxt->neg;
5034    while ((CUR != ']') && (ctxt->error == 0)) {
5035	if (CUR == '^') {
5036	    int neg = ctxt->neg;
5037
5038	    NEXT;
5039	    ctxt->neg = !ctxt->neg;
5040	    xmlFAParsePosCharGroup(ctxt);
5041	    ctxt->neg = neg;
5042	} else if ((CUR == '-') && (NXT(1) == '[')) {
5043	    int neg = ctxt->neg;
5044	    ctxt->neg = 2;
5045	    NEXT;	/* eat the '-' */
5046	    NEXT;	/* eat the '[' */
5047	    xmlFAParseCharGroup(ctxt);
5048	    if (CUR == ']') {
5049		NEXT;
5050	    } else {
5051		ERROR("charClassExpr: ']' expected");
5052		break;
5053	    }
5054	    ctxt->neg = neg;
5055	    break;
5056	} else if (CUR != ']') {
5057	    xmlFAParsePosCharGroup(ctxt);
5058	}
5059    }
5060    ctxt->neg = n;
5061}
5062
5063/**
5064 * xmlFAParseCharClass:
5065 * @ctxt:  a regexp parser context
5066 *
5067 * [11]   charClass   ::=     charClassEsc | charClassExpr
5068 * [12]   charClassExpr   ::=   '[' charGroup ']'
5069 */
5070static void
5071xmlFAParseCharClass(xmlRegParserCtxtPtr ctxt) {
5072    if (CUR == '[') {
5073	NEXT;
5074	ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_RANGES);
5075	if (ctxt->atom == NULL)
5076	    return;
5077	xmlFAParseCharGroup(ctxt);
5078	if (CUR == ']') {
5079	    NEXT;
5080	} else {
5081	    ERROR("xmlFAParseCharClass: ']' expected");
5082	}
5083    } else {
5084	xmlFAParseCharClassEsc(ctxt);
5085    }
5086}
5087
5088/**
5089 * xmlFAParseQuantExact:
5090 * @ctxt:  a regexp parser context
5091 *
5092 * [8]   QuantExact   ::=   [0-9]+
5093 *
5094 * Returns 0 if success or -1 in case of error
5095 */
5096static int
5097xmlFAParseQuantExact(xmlRegParserCtxtPtr ctxt) {
5098    int ret = 0;
5099    int ok = 0;
5100
5101    while ((CUR >= '0') && (CUR <= '9')) {
5102	ret = ret * 10 + (CUR - '0');
5103	ok = 1;
5104	NEXT;
5105    }
5106    if (ok != 1) {
5107	return(-1);
5108    }
5109    return(ret);
5110}
5111
5112/**
5113 * xmlFAParseQuantifier:
5114 * @ctxt:  a regexp parser context
5115 *
5116 * [4]   quantifier   ::=   [?*+] | ( '{' quantity '}' )
5117 * [5]   quantity   ::=   quantRange | quantMin | QuantExact
5118 * [6]   quantRange   ::=   QuantExact ',' QuantExact
5119 * [7]   quantMin   ::=   QuantExact ','
5120 * [8]   QuantExact   ::=   [0-9]+
5121 */
5122static int
5123xmlFAParseQuantifier(xmlRegParserCtxtPtr ctxt) {
5124    int cur;
5125
5126    cur = CUR;
5127    if ((cur == '?') || (cur == '*') || (cur == '+')) {
5128	if (ctxt->atom != NULL) {
5129	    if (cur == '?')
5130		ctxt->atom->quant = XML_REGEXP_QUANT_OPT;
5131	    else if (cur == '*')
5132		ctxt->atom->quant = XML_REGEXP_QUANT_MULT;
5133	    else if (cur == '+')
5134		ctxt->atom->quant = XML_REGEXP_QUANT_PLUS;
5135	}
5136	NEXT;
5137	return(1);
5138    }
5139    if (cur == '{') {
5140	int min = 0, max = 0;
5141
5142	NEXT;
5143	cur = xmlFAParseQuantExact(ctxt);
5144	if (cur >= 0)
5145	    min = cur;
5146	if (CUR == ',') {
5147	    NEXT;
5148	    if (CUR == '}')
5149	        max = INT_MAX;
5150	    else {
5151	        cur = xmlFAParseQuantExact(ctxt);
5152	        if (cur >= 0)
5153		    max = cur;
5154		else {
5155		    ERROR("Improper quantifier");
5156		}
5157	    }
5158	}
5159	if (CUR == '}') {
5160	    NEXT;
5161	} else {
5162	    ERROR("Unterminated quantifier");
5163	}
5164	if (max == 0)
5165	    max = min;
5166	if (ctxt->atom != NULL) {
5167	    ctxt->atom->quant = XML_REGEXP_QUANT_RANGE;
5168	    ctxt->atom->min = min;
5169	    ctxt->atom->max = max;
5170	}
5171	return(1);
5172    }
5173    return(0);
5174}
5175
5176/**
5177 * xmlFAParseAtom:
5178 * @ctxt:  a regexp parser context
5179 *
5180 * [9]   atom   ::=   Char | charClass | ( '(' regExp ')' )
5181 */
5182static int
5183xmlFAParseAtom(xmlRegParserCtxtPtr ctxt) {
5184    int codepoint, len;
5185
5186    codepoint = xmlFAIsChar(ctxt);
5187    if (codepoint > 0) {
5188	ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_CHARVAL);
5189	if (ctxt->atom == NULL)
5190	    return(-1);
5191	codepoint = CUR_SCHAR(ctxt->cur, len);
5192	ctxt->atom->codepoint = codepoint;
5193	NEXTL(len);
5194	return(1);
5195    } else if (CUR == '|') {
5196	return(0);
5197    } else if (CUR == 0) {
5198	return(0);
5199    } else if (CUR == ')') {
5200	return(0);
5201    } else if (CUR == '(') {
5202	xmlRegStatePtr start, oldend, start0;
5203
5204	NEXT;
5205	/*
5206	 * this extra Epsilon transition is needed if we count with 0 allowed
5207	 * unfortunately this can't be known at that point
5208	 */
5209	xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL);
5210	start0 = ctxt->state;
5211	xmlFAGenerateEpsilonTransition(ctxt, ctxt->state, NULL);
5212	start = ctxt->state;
5213	oldend = ctxt->end;
5214	ctxt->end = NULL;
5215	ctxt->atom = NULL;
5216	xmlFAParseRegExp(ctxt, 0);
5217	if (CUR == ')') {
5218	    NEXT;
5219	} else {
5220	    ERROR("xmlFAParseAtom: expecting ')'");
5221	}
5222	ctxt->atom = xmlRegNewAtom(ctxt, XML_REGEXP_SUBREG);
5223	if (ctxt->atom == NULL)
5224	    return(-1);
5225	ctxt->atom->start = start;
5226	ctxt->atom->start0 = start0;
5227	ctxt->atom->stop = ctxt->state;
5228	ctxt->end = oldend;
5229	return(1);
5230    } else if ((CUR == '[') || (CUR == '\\') || (CUR == '.')) {
5231	xmlFAParseCharClass(ctxt);
5232	return(1);
5233    }
5234    return(0);
5235}
5236
5237/**
5238 * xmlFAParsePiece:
5239 * @ctxt:  a regexp parser context
5240 *
5241 * [3]   piece   ::=   atom quantifier?
5242 */
5243static int
5244xmlFAParsePiece(xmlRegParserCtxtPtr ctxt) {
5245    int ret;
5246
5247    ctxt->atom = NULL;
5248    ret = xmlFAParseAtom(ctxt);
5249    if (ret == 0)
5250	return(0);
5251    if (ctxt->atom == NULL) {
5252	ERROR("internal: no atom generated");
5253    }
5254    xmlFAParseQuantifier(ctxt);
5255    return(1);
5256}
5257
5258/**
5259 * xmlFAParseBranch:
5260 * @ctxt:  a regexp parser context
5261 * @to: optional target to the end of the branch
5262 *
5263 * @to is used to optimize by removing duplicate path in automata
5264 * in expressions like (a|b)(c|d)
5265 *
5266 * [2]   branch   ::=   piece*
5267 */
5268static int
5269xmlFAParseBranch(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr to) {
5270    xmlRegStatePtr previous;
5271    int ret;
5272
5273    previous = ctxt->state;
5274    ret = xmlFAParsePiece(ctxt);
5275    if (ret != 0) {
5276	if (xmlFAGenerateTransitions(ctxt, previous,
5277	        (CUR=='|' || CUR==')') ? to : NULL, ctxt->atom) < 0)
5278	    return(-1);
5279	previous = ctxt->state;
5280	ctxt->atom = NULL;
5281    }
5282    while ((ret != 0) && (ctxt->error == 0)) {
5283	ret = xmlFAParsePiece(ctxt);
5284	if (ret != 0) {
5285	    if (xmlFAGenerateTransitions(ctxt, previous,
5286	            (CUR=='|' || CUR==')') ? to : NULL, ctxt->atom) < 0)
5287		    return(-1);
5288	    previous = ctxt->state;
5289	    ctxt->atom = NULL;
5290	}
5291    }
5292    return(0);
5293}
5294
5295/**
5296 * xmlFAParseRegExp:
5297 * @ctxt:  a regexp parser context
5298 * @top:  is this the top-level expression ?
5299 *
5300 * [1]   regExp   ::=     branch  ( '|' branch )*
5301 */
5302static void
5303xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top) {
5304    xmlRegStatePtr start, end;
5305
5306    /* if not top start should have been generated by an epsilon trans */
5307    start = ctxt->state;
5308    ctxt->end = NULL;
5309    xmlFAParseBranch(ctxt, NULL);
5310    if (top) {
5311#ifdef DEBUG_REGEXP_GRAPH
5312	printf("State %d is final\n", ctxt->state->no);
5313#endif
5314	ctxt->state->type = XML_REGEXP_FINAL_STATE;
5315    }
5316    if (CUR != '|') {
5317	ctxt->end = ctxt->state;
5318	return;
5319    }
5320    end = ctxt->state;
5321    while ((CUR == '|') && (ctxt->error == 0)) {
5322	NEXT;
5323	ctxt->state = start;
5324	ctxt->end = NULL;
5325	xmlFAParseBranch(ctxt, end);
5326    }
5327    if (!top) {
5328	ctxt->state = end;
5329	ctxt->end = end;
5330    }
5331}
5332
5333/************************************************************************
5334 * 									*
5335 * 			The basic API					*
5336 * 									*
5337 ************************************************************************/
5338
5339/**
5340 * xmlRegexpPrint:
5341 * @output: the file for the output debug
5342 * @regexp: the compiled regexp
5343 *
5344 * Print the content of the compiled regular expression
5345 */
5346void
5347xmlRegexpPrint(FILE *output, xmlRegexpPtr regexp) {
5348    int i;
5349
5350    if (output == NULL)
5351        return;
5352    fprintf(output, " regexp: ");
5353    if (regexp == NULL) {
5354	fprintf(output, "NULL\n");
5355	return;
5356    }
5357    fprintf(output, "'%s' ", regexp->string);
5358    fprintf(output, "\n");
5359    fprintf(output, "%d atoms:\n", regexp->nbAtoms);
5360    for (i = 0;i < regexp->nbAtoms; i++) {
5361	fprintf(output, " %02d ", i);
5362	xmlRegPrintAtom(output, regexp->atoms[i]);
5363    }
5364    fprintf(output, "%d states:", regexp->nbStates);
5365    fprintf(output, "\n");
5366    for (i = 0;i < regexp->nbStates; i++) {
5367	xmlRegPrintState(output, regexp->states[i]);
5368    }
5369    fprintf(output, "%d counters:\n", regexp->nbCounters);
5370    for (i = 0;i < regexp->nbCounters; i++) {
5371	fprintf(output, " %d: min %d max %d\n", i, regexp->counters[i].min,
5372		                                regexp->counters[i].max);
5373    }
5374}
5375
5376/**
5377 * xmlRegexpCompile:
5378 * @regexp:  a regular expression string
5379 *
5380 * Parses a regular expression conforming to XML Schemas Part 2 Datatype
5381 * Appendix F and builds an automata suitable for testing strings against
5382 * that regular expression
5383 *
5384 * Returns the compiled expression or NULL in case of error
5385 */
5386xmlRegexpPtr
5387xmlRegexpCompile(const xmlChar *regexp) {
5388    xmlRegexpPtr ret;
5389    xmlRegParserCtxtPtr ctxt;
5390
5391    ctxt = xmlRegNewParserCtxt(regexp);
5392    if (ctxt == NULL)
5393	return(NULL);
5394
5395    /* initialize the parser */
5396    ctxt->end = NULL;
5397    ctxt->start = ctxt->state = xmlRegNewState(ctxt);
5398    xmlRegStatePush(ctxt, ctxt->start);
5399
5400    /* parse the expression building an automata */
5401    xmlFAParseRegExp(ctxt, 1);
5402    if (CUR != 0) {
5403	ERROR("xmlFAParseRegExp: extra characters");
5404    }
5405    if (ctxt->error != 0) {
5406	xmlRegFreeParserCtxt(ctxt);
5407	return(NULL);
5408    }
5409    ctxt->end = ctxt->state;
5410    ctxt->start->type = XML_REGEXP_START_STATE;
5411    ctxt->end->type = XML_REGEXP_FINAL_STATE;
5412
5413    /* remove the Epsilon except for counted transitions */
5414    xmlFAEliminateEpsilonTransitions(ctxt);
5415
5416
5417    if (ctxt->error != 0) {
5418	xmlRegFreeParserCtxt(ctxt);
5419	return(NULL);
5420    }
5421    ret = xmlRegEpxFromParse(ctxt);
5422    xmlRegFreeParserCtxt(ctxt);
5423    return(ret);
5424}
5425
5426/**
5427 * xmlRegexpExec:
5428 * @comp:  the compiled regular expression
5429 * @content:  the value to check against the regular expression
5430 *
5431 * Check if the regular expression generates the value
5432 *
5433 * Returns 1 if it matches, 0 if not and a negative value in case of error
5434 */
5435int
5436xmlRegexpExec(xmlRegexpPtr comp, const xmlChar *content) {
5437    if ((comp == NULL) || (content == NULL))
5438	return(-1);
5439    return(xmlFARegExec(comp, content));
5440}
5441
5442/**
5443 * xmlRegexpIsDeterminist:
5444 * @comp:  the compiled regular expression
5445 *
5446 * Check if the regular expression is determinist
5447 *
5448 * Returns 1 if it yes, 0 if not and a negative value in case of error
5449 */
5450int
5451xmlRegexpIsDeterminist(xmlRegexpPtr comp) {
5452    xmlAutomataPtr am;
5453    int ret;
5454
5455    if (comp == NULL)
5456	return(-1);
5457    if (comp->determinist != -1)
5458	return(comp->determinist);
5459
5460    am = xmlNewAutomata();
5461    if (am->states != NULL) {
5462	int i;
5463
5464	for (i = 0;i < am->nbStates;i++)
5465	    xmlRegFreeState(am->states[i]);
5466	xmlFree(am->states);
5467    }
5468    am->nbAtoms = comp->nbAtoms;
5469    am->atoms = comp->atoms;
5470    am->nbStates = comp->nbStates;
5471    am->states = comp->states;
5472    am->determinist = -1;
5473    ret = xmlFAComputesDeterminism(am);
5474    am->atoms = NULL;
5475    am->states = NULL;
5476    xmlFreeAutomata(am);
5477    return(ret);
5478}
5479
5480/**
5481 * xmlRegFreeRegexp:
5482 * @regexp:  the regexp
5483 *
5484 * Free a regexp
5485 */
5486void
5487xmlRegFreeRegexp(xmlRegexpPtr regexp) {
5488    int i;
5489    if (regexp == NULL)
5490	return;
5491
5492    if (regexp->string != NULL)
5493	xmlFree(regexp->string);
5494    if (regexp->states != NULL) {
5495	for (i = 0;i < regexp->nbStates;i++)
5496	    xmlRegFreeState(regexp->states[i]);
5497	xmlFree(regexp->states);
5498    }
5499    if (regexp->atoms != NULL) {
5500	for (i = 0;i < regexp->nbAtoms;i++)
5501	    xmlRegFreeAtom(regexp->atoms[i]);
5502	xmlFree(regexp->atoms);
5503    }
5504    if (regexp->counters != NULL)
5505	xmlFree(regexp->counters);
5506    if (regexp->compact != NULL)
5507	xmlFree(regexp->compact);
5508    if (regexp->transdata != NULL)
5509	xmlFree(regexp->transdata);
5510    if (regexp->stringMap != NULL) {
5511	for (i = 0; i < regexp->nbstrings;i++)
5512	    xmlFree(regexp->stringMap[i]);
5513	xmlFree(regexp->stringMap);
5514    }
5515
5516    xmlFree(regexp);
5517}
5518
5519#ifdef LIBXML_AUTOMATA_ENABLED
5520/************************************************************************
5521 * 									*
5522 * 			The Automata interface				*
5523 * 									*
5524 ************************************************************************/
5525
5526/**
5527 * xmlNewAutomata:
5528 *
5529 * Create a new automata
5530 *
5531 * Returns the new object or NULL in case of failure
5532 */
5533xmlAutomataPtr
5534xmlNewAutomata(void) {
5535    xmlAutomataPtr ctxt;
5536
5537    ctxt = xmlRegNewParserCtxt(NULL);
5538    if (ctxt == NULL)
5539	return(NULL);
5540
5541    /* initialize the parser */
5542    ctxt->end = NULL;
5543    ctxt->start = ctxt->state = xmlRegNewState(ctxt);
5544    if (ctxt->start == NULL) {
5545	xmlFreeAutomata(ctxt);
5546	return(NULL);
5547    }
5548    ctxt->start->type = XML_REGEXP_START_STATE;
5549    if (xmlRegStatePush(ctxt, ctxt->start) < 0) {
5550        xmlRegFreeState(ctxt->start);
5551	xmlFreeAutomata(ctxt);
5552	return(NULL);
5553    }
5554
5555    return(ctxt);
5556}
5557
5558/**
5559 * xmlFreeAutomata:
5560 * @am: an automata
5561 *
5562 * Free an automata
5563 */
5564void
5565xmlFreeAutomata(xmlAutomataPtr am) {
5566    if (am == NULL)
5567	return;
5568    xmlRegFreeParserCtxt(am);
5569}
5570
5571/**
5572 * xmlAutomataGetInitState:
5573 * @am: an automata
5574 *
5575 * Initial state lookup
5576 *
5577 * Returns the initial state of the automata
5578 */
5579xmlAutomataStatePtr
5580xmlAutomataGetInitState(xmlAutomataPtr am) {
5581    if (am == NULL)
5582	return(NULL);
5583    return(am->start);
5584}
5585
5586/**
5587 * xmlAutomataSetFinalState:
5588 * @am: an automata
5589 * @state: a state in this automata
5590 *
5591 * Makes that state a final state
5592 *
5593 * Returns 0 or -1 in case of error
5594 */
5595int
5596xmlAutomataSetFinalState(xmlAutomataPtr am, xmlAutomataStatePtr state) {
5597    if ((am == NULL) || (state == NULL))
5598	return(-1);
5599    state->type = XML_REGEXP_FINAL_STATE;
5600    return(0);
5601}
5602
5603/**
5604 * xmlAutomataNewTransition:
5605 * @am: an automata
5606 * @from: the starting point of the transition
5607 * @to: the target point of the transition or NULL
5608 * @token: the input string associated to that transition
5609 * @data: data passed to the callback function if the transition is activated
5610 *
5611 * If @to is NULL, this creates first a new target state in the automata
5612 * and then adds a transition from the @from state to the target state
5613 * activated by the value of @token
5614 *
5615 * Returns the target state or NULL in case of error
5616 */
5617xmlAutomataStatePtr
5618xmlAutomataNewTransition(xmlAutomataPtr am, xmlAutomataStatePtr from,
5619			 xmlAutomataStatePtr to, const xmlChar *token,
5620			 void *data) {
5621    xmlRegAtomPtr atom;
5622
5623    if ((am == NULL) || (from == NULL) || (token == NULL))
5624	return(NULL);
5625    atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5626    if (atom == NULL)
5627        return(NULL);
5628    atom->data = data;
5629    if (atom == NULL)
5630	return(NULL);
5631    atom->valuep = xmlStrdup(token);
5632
5633    if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {
5634        xmlRegFreeAtom(atom);
5635	return(NULL);
5636    }
5637    if (to == NULL)
5638	return(am->state);
5639    return(to);
5640}
5641
5642/**
5643 * xmlAutomataNewTransition2:
5644 * @am: an automata
5645 * @from: the starting point of the transition
5646 * @to: the target point of the transition or NULL
5647 * @token: the first input string associated to that transition
5648 * @token2: the second input string associated to that transition
5649 * @data: data passed to the callback function if the transition is activated
5650 *
5651 * If @to is NULL, this creates first a new target state in the automata
5652 * and then adds a transition from the @from state to the target state
5653 * activated by the value of @token
5654 *
5655 * Returns the target state or NULL in case of error
5656 */
5657xmlAutomataStatePtr
5658xmlAutomataNewTransition2(xmlAutomataPtr am, xmlAutomataStatePtr from,
5659			  xmlAutomataStatePtr to, const xmlChar *token,
5660			  const xmlChar *token2, void *data) {
5661    xmlRegAtomPtr atom;
5662
5663    if ((am == NULL) || (from == NULL) || (token == NULL))
5664	return(NULL);
5665    atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5666    if (atom == NULL)
5667	return(NULL);
5668    atom->data = data;
5669    if ((token2 == NULL) || (*token2 == 0)) {
5670	atom->valuep = xmlStrdup(token);
5671    } else {
5672	int lenn, lenp;
5673	xmlChar *str;
5674
5675	lenn = strlen((char *) token2);
5676	lenp = strlen((char *) token);
5677
5678	str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
5679	if (str == NULL) {
5680	    xmlRegFreeAtom(atom);
5681	    return(NULL);
5682	}
5683	memcpy(&str[0], token, lenp);
5684	str[lenp] = '|';
5685	memcpy(&str[lenp + 1], token2, lenn);
5686	str[lenn + lenp + 1] = 0;
5687
5688	atom->valuep = str;
5689    }
5690
5691    if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {
5692        xmlRegFreeAtom(atom);
5693	return(NULL);
5694    }
5695    if (to == NULL)
5696	return(am->state);
5697    return(to);
5698}
5699
5700/**
5701 * xmlAutomataNewNegTrans:
5702 * @am: an automata
5703 * @from: the starting point of the transition
5704 * @to: the target point of the transition or NULL
5705 * @token: the first input string associated to that transition
5706 * @token2: the second input string associated to that transition
5707 * @data: data passed to the callback function if the transition is activated
5708 *
5709 * If @to is NULL, this creates first a new target state in the automata
5710 * and then adds a transition from the @from state to the target state
5711 * activated by any value except (@token,@token2)
5712 * Note that if @token2 is not NULL, then (X, NULL) won't match to follow
5713 # the semantic of XSD ##other
5714 *
5715 * Returns the target state or NULL in case of error
5716 */
5717xmlAutomataStatePtr
5718xmlAutomataNewNegTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
5719		       xmlAutomataStatePtr to, const xmlChar *token,
5720		       const xmlChar *token2, void *data) {
5721    xmlRegAtomPtr atom;
5722    xmlChar err_msg[200];
5723
5724    if ((am == NULL) || (from == NULL) || (token == NULL))
5725	return(NULL);
5726    atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5727    if (atom == NULL)
5728	return(NULL);
5729    atom->data = data;
5730    atom->neg = 1;
5731    if ((token2 == NULL) || (*token2 == 0)) {
5732	atom->valuep = xmlStrdup(token);
5733    } else {
5734	int lenn, lenp;
5735	xmlChar *str;
5736
5737	lenn = strlen((char *) token2);
5738	lenp = strlen((char *) token);
5739
5740	str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
5741	if (str == NULL) {
5742	    xmlRegFreeAtom(atom);
5743	    return(NULL);
5744	}
5745	memcpy(&str[0], token, lenp);
5746	str[lenp] = '|';
5747	memcpy(&str[lenp + 1], token2, lenn);
5748	str[lenn + lenp + 1] = 0;
5749
5750	atom->valuep = str;
5751    }
5752    snprintf((char *) err_msg, 199, "not %s", (const char *) atom->valuep);
5753    err_msg[199] = 0;
5754    atom->valuep2 = xmlStrdup(err_msg);
5755
5756    if (xmlFAGenerateTransitions(am, from, to, atom) < 0) {
5757        xmlRegFreeAtom(atom);
5758	return(NULL);
5759    }
5760    am->negs++;
5761    if (to == NULL)
5762	return(am->state);
5763    return(to);
5764}
5765
5766/**
5767 * xmlAutomataNewCountTrans2:
5768 * @am: an automata
5769 * @from: the starting point of the transition
5770 * @to: the target point of the transition or NULL
5771 * @token: the input string associated to that transition
5772 * @token2: the second input string associated to that transition
5773 * @min:  the minimum successive occurences of token
5774 * @max:  the maximum successive occurences of token
5775 * @data:  data associated to the transition
5776 *
5777 * If @to is NULL, this creates first a new target state in the automata
5778 * and then adds a transition from the @from state to the target state
5779 * activated by a succession of input of value @token and @token2 and
5780 * whose number is between @min and @max
5781 *
5782 * Returns the target state or NULL in case of error
5783 */
5784xmlAutomataStatePtr
5785xmlAutomataNewCountTrans2(xmlAutomataPtr am, xmlAutomataStatePtr from,
5786			 xmlAutomataStatePtr to, const xmlChar *token,
5787			 const xmlChar *token2,
5788			 int min, int max, void *data) {
5789    xmlRegAtomPtr atom;
5790    int counter;
5791
5792    if ((am == NULL) || (from == NULL) || (token == NULL))
5793	return(NULL);
5794    if (min < 0)
5795	return(NULL);
5796    if ((max < min) || (max < 1))
5797	return(NULL);
5798    atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5799    if (atom == NULL)
5800	return(NULL);
5801    if ((token2 == NULL) || (*token2 == 0)) {
5802	atom->valuep = xmlStrdup(token);
5803    } else {
5804	int lenn, lenp;
5805	xmlChar *str;
5806
5807	lenn = strlen((char *) token2);
5808	lenp = strlen((char *) token);
5809
5810	str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
5811	if (str == NULL) {
5812	    xmlRegFreeAtom(atom);
5813	    return(NULL);
5814	}
5815	memcpy(&str[0], token, lenp);
5816	str[lenp] = '|';
5817	memcpy(&str[lenp + 1], token2, lenn);
5818	str[lenn + lenp + 1] = 0;
5819
5820	atom->valuep = str;
5821    }
5822    atom->data = data;
5823    if (min == 0)
5824	atom->min = 1;
5825    else
5826	atom->min = min;
5827    atom->max = max;
5828
5829    /*
5830     * associate a counter to the transition.
5831     */
5832    counter = xmlRegGetCounter(am);
5833    am->counters[counter].min = min;
5834    am->counters[counter].max = max;
5835
5836    /* xmlFAGenerateTransitions(am, from, to, atom); */
5837    if (to == NULL) {
5838        to = xmlRegNewState(am);
5839	xmlRegStatePush(am, to);
5840    }
5841    xmlRegStateAddTrans(am, from, atom, to, counter, -1);
5842    xmlRegAtomPush(am, atom);
5843    am->state = to;
5844
5845    if (to == NULL)
5846	to = am->state;
5847    if (to == NULL)
5848	return(NULL);
5849    if (min == 0)
5850	xmlFAGenerateEpsilonTransition(am, from, to);
5851    return(to);
5852}
5853
5854/**
5855 * xmlAutomataNewCountTrans:
5856 * @am: an automata
5857 * @from: the starting point of the transition
5858 * @to: the target point of the transition or NULL
5859 * @token: the input string associated to that transition
5860 * @min:  the minimum successive occurences of token
5861 * @max:  the maximum successive occurences of token
5862 * @data:  data associated to the transition
5863 *
5864 * If @to is NULL, this creates first a new target state in the automata
5865 * and then adds a transition from the @from state to the target state
5866 * activated by a succession of input of value @token and whose number
5867 * is between @min and @max
5868 *
5869 * Returns the target state or NULL in case of error
5870 */
5871xmlAutomataStatePtr
5872xmlAutomataNewCountTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
5873			 xmlAutomataStatePtr to, const xmlChar *token,
5874			 int min, int max, void *data) {
5875    xmlRegAtomPtr atom;
5876    int counter;
5877
5878    if ((am == NULL) || (from == NULL) || (token == NULL))
5879	return(NULL);
5880    if (min < 0)
5881	return(NULL);
5882    if ((max < min) || (max < 1))
5883	return(NULL);
5884    atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5885    if (atom == NULL)
5886	return(NULL);
5887    atom->valuep = xmlStrdup(token);
5888    atom->data = data;
5889    if (min == 0)
5890	atom->min = 1;
5891    else
5892	atom->min = min;
5893    atom->max = max;
5894
5895    /*
5896     * associate a counter to the transition.
5897     */
5898    counter = xmlRegGetCounter(am);
5899    am->counters[counter].min = min;
5900    am->counters[counter].max = max;
5901
5902    /* xmlFAGenerateTransitions(am, from, to, atom); */
5903    if (to == NULL) {
5904        to = xmlRegNewState(am);
5905	xmlRegStatePush(am, to);
5906    }
5907    xmlRegStateAddTrans(am, from, atom, to, counter, -1);
5908    xmlRegAtomPush(am, atom);
5909    am->state = to;
5910
5911    if (to == NULL)
5912	to = am->state;
5913    if (to == NULL)
5914	return(NULL);
5915    if (min == 0)
5916	xmlFAGenerateEpsilonTransition(am, from, to);
5917    return(to);
5918}
5919
5920/**
5921 * xmlAutomataNewOnceTrans2:
5922 * @am: an automata
5923 * @from: the starting point of the transition
5924 * @to: the target point of the transition or NULL
5925 * @token: the input string associated to that transition
5926 * @token2: the second input string associated to that transition
5927 * @min:  the minimum successive occurences of token
5928 * @max:  the maximum successive occurences of token
5929 * @data:  data associated to the transition
5930 *
5931 * If @to is NULL, this creates first a new target state in the automata
5932 * and then adds a transition from the @from state to the target state
5933 * activated by a succession of input of value @token and @token2 and whose
5934 * number is between @min and @max, moreover that transition can only be
5935 * crossed once.
5936 *
5937 * Returns the target state or NULL in case of error
5938 */
5939xmlAutomataStatePtr
5940xmlAutomataNewOnceTrans2(xmlAutomataPtr am, xmlAutomataStatePtr from,
5941			 xmlAutomataStatePtr to, const xmlChar *token,
5942			 const xmlChar *token2,
5943			 int min, int max, void *data) {
5944    xmlRegAtomPtr atom;
5945    int counter;
5946
5947    if ((am == NULL) || (from == NULL) || (token == NULL))
5948	return(NULL);
5949    if (min < 1)
5950	return(NULL);
5951    if ((max < min) || (max < 1))
5952	return(NULL);
5953    atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
5954    if (atom == NULL)
5955	return(NULL);
5956    if ((token2 == NULL) || (*token2 == 0)) {
5957	atom->valuep = xmlStrdup(token);
5958    } else {
5959	int lenn, lenp;
5960	xmlChar *str;
5961
5962	lenn = strlen((char *) token2);
5963	lenp = strlen((char *) token);
5964
5965	str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
5966	if (str == NULL) {
5967	    xmlRegFreeAtom(atom);
5968	    return(NULL);
5969	}
5970	memcpy(&str[0], token, lenp);
5971	str[lenp] = '|';
5972	memcpy(&str[lenp + 1], token2, lenn);
5973	str[lenn + lenp + 1] = 0;
5974
5975	atom->valuep = str;
5976    }
5977    atom->data = data;
5978    atom->quant = XML_REGEXP_QUANT_ONCEONLY;
5979    atom->min = min;
5980    atom->max = max;
5981    /*
5982     * associate a counter to the transition.
5983     */
5984    counter = xmlRegGetCounter(am);
5985    am->counters[counter].min = 1;
5986    am->counters[counter].max = 1;
5987
5988    /* xmlFAGenerateTransitions(am, from, to, atom); */
5989    if (to == NULL) {
5990	to = xmlRegNewState(am);
5991	xmlRegStatePush(am, to);
5992    }
5993    xmlRegStateAddTrans(am, from, atom, to, counter, -1);
5994    xmlRegAtomPush(am, atom);
5995    am->state = to;
5996    return(to);
5997}
5998
5999
6000
6001/**
6002 * xmlAutomataNewOnceTrans:
6003 * @am: an automata
6004 * @from: the starting point of the transition
6005 * @to: the target point of the transition or NULL
6006 * @token: the input string associated to that transition
6007 * @min:  the minimum successive occurences of token
6008 * @max:  the maximum successive occurences of token
6009 * @data:  data associated to the transition
6010 *
6011 * If @to is NULL, this creates first a new target state in the automata
6012 * and then adds a transition from the @from state to the target state
6013 * activated by a succession of input of value @token and whose number
6014 * is between @min and @max, moreover that transition can only be crossed
6015 * once.
6016 *
6017 * Returns the target state or NULL in case of error
6018 */
6019xmlAutomataStatePtr
6020xmlAutomataNewOnceTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
6021			 xmlAutomataStatePtr to, const xmlChar *token,
6022			 int min, int max, void *data) {
6023    xmlRegAtomPtr atom;
6024    int counter;
6025
6026    if ((am == NULL) || (from == NULL) || (token == NULL))
6027	return(NULL);
6028    if (min < 1)
6029	return(NULL);
6030    if ((max < min) || (max < 1))
6031	return(NULL);
6032    atom = xmlRegNewAtom(am, XML_REGEXP_STRING);
6033    if (atom == NULL)
6034	return(NULL);
6035    atom->valuep = xmlStrdup(token);
6036    atom->data = data;
6037    atom->quant = XML_REGEXP_QUANT_ONCEONLY;
6038    atom->min = min;
6039    atom->max = max;
6040    /*
6041     * associate a counter to the transition.
6042     */
6043    counter = xmlRegGetCounter(am);
6044    am->counters[counter].min = 1;
6045    am->counters[counter].max = 1;
6046
6047    /* xmlFAGenerateTransitions(am, from, to, atom); */
6048    if (to == NULL) {
6049	to = xmlRegNewState(am);
6050	xmlRegStatePush(am, to);
6051    }
6052    xmlRegStateAddTrans(am, from, atom, to, counter, -1);
6053    xmlRegAtomPush(am, atom);
6054    am->state = to;
6055    return(to);
6056}
6057
6058/**
6059 * xmlAutomataNewState:
6060 * @am: an automata
6061 *
6062 * Create a new disconnected state in the automata
6063 *
6064 * Returns the new state or NULL in case of error
6065 */
6066xmlAutomataStatePtr
6067xmlAutomataNewState(xmlAutomataPtr am) {
6068    xmlAutomataStatePtr to;
6069
6070    if (am == NULL)
6071	return(NULL);
6072    to = xmlRegNewState(am);
6073    xmlRegStatePush(am, to);
6074    return(to);
6075}
6076
6077/**
6078 * xmlAutomataNewEpsilon:
6079 * @am: an automata
6080 * @from: the starting point of the transition
6081 * @to: the target point of the transition or NULL
6082 *
6083 * If @to is NULL, this creates first a new target state in the automata
6084 * and then adds an epsilon transition from the @from state to the
6085 * target state
6086 *
6087 * Returns the target state or NULL in case of error
6088 */
6089xmlAutomataStatePtr
6090xmlAutomataNewEpsilon(xmlAutomataPtr am, xmlAutomataStatePtr from,
6091		      xmlAutomataStatePtr to) {
6092    if ((am == NULL) || (from == NULL))
6093	return(NULL);
6094    xmlFAGenerateEpsilonTransition(am, from, to);
6095    if (to == NULL)
6096	return(am->state);
6097    return(to);
6098}
6099
6100/**
6101 * xmlAutomataNewAllTrans:
6102 * @am: an automata
6103 * @from: the starting point of the transition
6104 * @to: the target point of the transition or NULL
6105 * @lax: allow to transition if not all all transitions have been activated
6106 *
6107 * If @to is NULL, this creates first a new target state in the automata
6108 * and then adds a an ALL transition from the @from state to the
6109 * target state. That transition is an epsilon transition allowed only when
6110 * all transitions from the @from node have been activated.
6111 *
6112 * Returns the target state or NULL in case of error
6113 */
6114xmlAutomataStatePtr
6115xmlAutomataNewAllTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
6116		       xmlAutomataStatePtr to, int lax) {
6117    if ((am == NULL) || (from == NULL))
6118	return(NULL);
6119    xmlFAGenerateAllTransition(am, from, to, lax);
6120    if (to == NULL)
6121	return(am->state);
6122    return(to);
6123}
6124
6125/**
6126 * xmlAutomataNewCounter:
6127 * @am: an automata
6128 * @min:  the minimal value on the counter
6129 * @max:  the maximal value on the counter
6130 *
6131 * Create a new counter
6132 *
6133 * Returns the counter number or -1 in case of error
6134 */
6135int
6136xmlAutomataNewCounter(xmlAutomataPtr am, int min, int max) {
6137    int ret;
6138
6139    if (am == NULL)
6140	return(-1);
6141
6142    ret = xmlRegGetCounter(am);
6143    if (ret < 0)
6144	return(-1);
6145    am->counters[ret].min = min;
6146    am->counters[ret].max = max;
6147    return(ret);
6148}
6149
6150/**
6151 * xmlAutomataNewCountedTrans:
6152 * @am: an automata
6153 * @from: the starting point of the transition
6154 * @to: the target point of the transition or NULL
6155 * @counter: the counter associated to that transition
6156 *
6157 * If @to is NULL, this creates first a new target state in the automata
6158 * and then adds an epsilon transition from the @from state to the target state
6159 * which will increment the counter provided
6160 *
6161 * Returns the target state or NULL in case of error
6162 */
6163xmlAutomataStatePtr
6164xmlAutomataNewCountedTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
6165		xmlAutomataStatePtr to, int counter) {
6166    if ((am == NULL) || (from == NULL) || (counter < 0))
6167	return(NULL);
6168    xmlFAGenerateCountedEpsilonTransition(am, from, to, counter);
6169    if (to == NULL)
6170	return(am->state);
6171    return(to);
6172}
6173
6174/**
6175 * xmlAutomataNewCounterTrans:
6176 * @am: an automata
6177 * @from: the starting point of the transition
6178 * @to: the target point of the transition or NULL
6179 * @counter: the counter associated to that transition
6180 *
6181 * If @to is NULL, this creates first a new target state in the automata
6182 * and then adds an epsilon transition from the @from state to the target state
6183 * which will be allowed only if the counter is within the right range.
6184 *
6185 * Returns the target state or NULL in case of error
6186 */
6187xmlAutomataStatePtr
6188xmlAutomataNewCounterTrans(xmlAutomataPtr am, xmlAutomataStatePtr from,
6189		xmlAutomataStatePtr to, int counter) {
6190    if ((am == NULL) || (from == NULL) || (counter < 0))
6191	return(NULL);
6192    xmlFAGenerateCountedTransition(am, from, to, counter);
6193    if (to == NULL)
6194	return(am->state);
6195    return(to);
6196}
6197
6198/**
6199 * xmlAutomataCompile:
6200 * @am: an automata
6201 *
6202 * Compile the automata into a Reg Exp ready for being executed.
6203 * The automata should be free after this point.
6204 *
6205 * Returns the compiled regexp or NULL in case of error
6206 */
6207xmlRegexpPtr
6208xmlAutomataCompile(xmlAutomataPtr am) {
6209    xmlRegexpPtr ret;
6210
6211    if ((am == NULL) || (am->error != 0)) return(NULL);
6212    xmlFAEliminateEpsilonTransitions(am);
6213    /* xmlFAComputesDeterminism(am); */
6214    ret = xmlRegEpxFromParse(am);
6215
6216    return(ret);
6217}
6218
6219/**
6220 * xmlAutomataIsDeterminist:
6221 * @am: an automata
6222 *
6223 * Checks if an automata is determinist.
6224 *
6225 * Returns 1 if true, 0 if not, and -1 in case of error
6226 */
6227int
6228xmlAutomataIsDeterminist(xmlAutomataPtr am) {
6229    int ret;
6230
6231    if (am == NULL)
6232	return(-1);
6233
6234    ret = xmlFAComputesDeterminism(am);
6235    return(ret);
6236}
6237#endif /* LIBXML_AUTOMATA_ENABLED */
6238
6239#ifdef LIBXML_EXPR_ENABLED
6240/************************************************************************
6241 *									*
6242 *		Formal Expression handling code				*
6243 *									*
6244 ************************************************************************/
6245/************************************************************************
6246 *									*
6247 *		Expression handling context				*
6248 *									*
6249 ************************************************************************/
6250
6251struct _xmlExpCtxt {
6252    xmlDictPtr dict;
6253    xmlExpNodePtr *table;
6254    int size;
6255    int nbElems;
6256    int nb_nodes;
6257    const char *expr;
6258    const char *cur;
6259    int nb_cons;
6260    int tabSize;
6261};
6262
6263/**
6264 * xmlExpNewCtxt:
6265 * @maxNodes:  the maximum number of nodes
6266 * @dict:  optional dictionnary to use internally
6267 *
6268 * Creates a new context for manipulating expressions
6269 *
6270 * Returns the context or NULL in case of error
6271 */
6272xmlExpCtxtPtr
6273xmlExpNewCtxt(int maxNodes, xmlDictPtr dict) {
6274    xmlExpCtxtPtr ret;
6275    int size = 256;
6276
6277    if (maxNodes <= 4096)
6278        maxNodes = 4096;
6279
6280    ret = (xmlExpCtxtPtr) xmlMalloc(sizeof(xmlExpCtxt));
6281    if (ret == NULL)
6282        return(NULL);
6283    memset(ret, 0, sizeof(xmlExpCtxt));
6284    ret->size = size;
6285    ret->nbElems = 0;
6286    ret->table = xmlMalloc(size * sizeof(xmlExpNodePtr));
6287    if (ret->table == NULL) {
6288        xmlFree(ret);
6289	return(NULL);
6290    }
6291    memset(ret->table, 0, size * sizeof(xmlExpNodePtr));
6292    if (dict == NULL) {
6293        ret->dict = xmlDictCreate();
6294	if (ret->dict == NULL) {
6295	    xmlFree(ret->table);
6296	    xmlFree(ret);
6297	    return(NULL);
6298	}
6299    } else {
6300        ret->dict = dict;
6301	xmlDictReference(ret->dict);
6302    }
6303    return(ret);
6304}
6305
6306/**
6307 * xmlExpFreeCtxt:
6308 * @ctxt:  an expression context
6309 *
6310 * Free an expression context
6311 */
6312void
6313xmlExpFreeCtxt(xmlExpCtxtPtr ctxt) {
6314    if (ctxt == NULL)
6315        return;
6316    xmlDictFree(ctxt->dict);
6317    if (ctxt->table != NULL)
6318	xmlFree(ctxt->table);
6319    xmlFree(ctxt);
6320}
6321
6322/************************************************************************
6323 *									*
6324 *		Structure associated to an expression node		*
6325 *									*
6326 ************************************************************************/
6327#define MAX_NODES 10000
6328
6329/* #define DEBUG_DERIV */
6330
6331/*
6332 * TODO:
6333 * - Wildcards
6334 * - public API for creation
6335 *
6336 * Started
6337 * - regression testing
6338 *
6339 * Done
6340 * - split into module and test tool
6341 * - memleaks
6342 */
6343
6344typedef enum {
6345    XML_EXP_NILABLE = (1 << 0)
6346} xmlExpNodeInfo;
6347
6348#define IS_NILLABLE(node) ((node)->info & XML_EXP_NILABLE)
6349
6350struct _xmlExpNode {
6351    unsigned char type;/* xmlExpNodeType */
6352    unsigned char info;/* OR of xmlExpNodeInfo */
6353    unsigned short key;	/* the hash key */
6354    unsigned int ref;	/* The number of references */
6355    int c_max;		/* the maximum length it can consume */
6356    xmlExpNodePtr exp_left;
6357    xmlExpNodePtr next;/* the next node in the hash table or free list */
6358    union {
6359	struct {
6360	    int f_min;
6361	    int f_max;
6362	} count;
6363	struct {
6364	    xmlExpNodePtr f_right;
6365	} children;
6366        const xmlChar *f_str;
6367    } field;
6368};
6369
6370#define exp_min field.count.f_min
6371#define exp_max field.count.f_max
6372/* #define exp_left field.children.f_left */
6373#define exp_right field.children.f_right
6374#define exp_str field.f_str
6375
6376static xmlExpNodePtr xmlExpNewNode(xmlExpCtxtPtr ctxt, xmlExpNodeType type);
6377static xmlExpNode forbiddenExpNode = {
6378    XML_EXP_FORBID, 0, 0, 0, 0, NULL, NULL, {{ 0, 0}}
6379};
6380xmlExpNodePtr forbiddenExp = &forbiddenExpNode;
6381static xmlExpNode emptyExpNode = {
6382    XML_EXP_EMPTY, 1, 0, 0, 0, NULL, NULL, {{ 0, 0}}
6383};
6384xmlExpNodePtr emptyExp = &emptyExpNode;
6385
6386/************************************************************************
6387 *									*
6388 *  The custom hash table for unicity and canonicalization		*
6389 *  of sub-expressions pointers						*
6390 *									*
6391 ************************************************************************/
6392/*
6393 * xmlExpHashNameComputeKey:
6394 * Calculate the hash key for a token
6395 */
6396static unsigned short
6397xmlExpHashNameComputeKey(const xmlChar *name) {
6398    unsigned short value = 0L;
6399    char ch;
6400
6401    if (name != NULL) {
6402	value += 30 * (*name);
6403	while ((ch = *name++) != 0) {
6404	    value = value ^ ((value << 5) + (value >> 3) + (unsigned short)ch);
6405	}
6406    }
6407    return (value);
6408}
6409
6410/*
6411 * xmlExpHashComputeKey:
6412 * Calculate the hash key for a compound expression
6413 */
6414static unsigned short
6415xmlExpHashComputeKey(xmlExpNodeType type, xmlExpNodePtr left,
6416                     xmlExpNodePtr right) {
6417    unsigned long value;
6418    unsigned short ret;
6419
6420    switch (type) {
6421        case XML_EXP_SEQ:
6422	    value = left->key;
6423	    value += right->key;
6424	    value *= 3;
6425	    ret = (unsigned short) value;
6426	    break;
6427        case XML_EXP_OR:
6428	    value = left->key;
6429	    value += right->key;
6430	    value *= 7;
6431	    ret = (unsigned short) value;
6432	    break;
6433        case XML_EXP_COUNT:
6434	    value = left->key;
6435	    value += right->key;
6436	    ret = (unsigned short) value;
6437	    break;
6438	default:
6439	    ret = 0;
6440    }
6441    return(ret);
6442}
6443
6444
6445static xmlExpNodePtr
6446xmlExpNewNode(xmlExpCtxtPtr ctxt, xmlExpNodeType type) {
6447    xmlExpNodePtr ret;
6448
6449    if (ctxt->nb_nodes >= MAX_NODES)
6450        return(NULL);
6451    ret = (xmlExpNodePtr) xmlMalloc(sizeof(xmlExpNode));
6452    if (ret == NULL)
6453        return(NULL);
6454    memset(ret, 0, sizeof(xmlExpNode));
6455    ret->type = type;
6456    ret->next = NULL;
6457    ctxt->nb_nodes++;
6458    ctxt->nb_cons++;
6459    return(ret);
6460}
6461
6462/**
6463 * xmlExpHashGetEntry:
6464 * @table: the hash table
6465 *
6466 * Get the unique entry from the hash table. The entry is created if
6467 * needed. @left and @right are consumed, i.e. their ref count will
6468 * be decremented by the operation.
6469 *
6470 * Returns the pointer or NULL in case of error
6471 */
6472static xmlExpNodePtr
6473xmlExpHashGetEntry(xmlExpCtxtPtr ctxt, xmlExpNodeType type,
6474                   xmlExpNodePtr left, xmlExpNodePtr right,
6475		   const xmlChar *name, int min, int max) {
6476    unsigned short kbase, key;
6477    xmlExpNodePtr entry;
6478    xmlExpNodePtr insert;
6479
6480    if (ctxt == NULL)
6481	return(NULL);
6482
6483    /*
6484     * Check for duplicate and insertion location.
6485     */
6486    if (type == XML_EXP_ATOM) {
6487	kbase = xmlExpHashNameComputeKey(name);
6488    } else if (type == XML_EXP_COUNT) {
6489        /* COUNT reduction rule 1 */
6490	/* a{1} -> a */
6491	if (min == max) {
6492	    if (min == 1) {
6493		return(left);
6494	    }
6495	    if (min == 0) {
6496		xmlExpFree(ctxt, left);
6497	        return(emptyExp);
6498	    }
6499	}
6500	if (min < 0) {
6501	    xmlExpFree(ctxt, left);
6502	    return(forbiddenExp);
6503	}
6504        if (max == -1)
6505	    kbase = min + 79;
6506	else
6507	    kbase = max - min;
6508	kbase += left->key;
6509    } else if (type == XML_EXP_OR) {
6510        /* Forbid reduction rules */
6511        if (left->type == XML_EXP_FORBID) {
6512	    xmlExpFree(ctxt, left);
6513	    return(right);
6514	}
6515        if (right->type == XML_EXP_FORBID) {
6516	    xmlExpFree(ctxt, right);
6517	    return(left);
6518	}
6519
6520        /* OR reduction rule 1 */
6521	/* a | a reduced to a */
6522        if (left == right) {
6523	    left->ref--;
6524	    return(left);
6525	}
6526        /* OR canonicalization rule 1 */
6527	/* linearize (a | b) | c into a | (b | c) */
6528        if ((left->type == XML_EXP_OR) && (right->type != XML_EXP_OR)) {
6529	    xmlExpNodePtr tmp = left;
6530            left = right;
6531	    right = tmp;
6532	}
6533        /* OR reduction rule 2 */
6534	/* a | (a | b) and b | (a | b) are reduced to a | b */
6535        if (right->type == XML_EXP_OR) {
6536	    if ((left == right->exp_left) ||
6537	        (left == right->exp_right)) {
6538		xmlExpFree(ctxt, left);
6539		return(right);
6540	    }
6541	}
6542        /* OR canonicalization rule 2 */
6543	/* linearize (a | b) | c into a | (b | c) */
6544        if (left->type == XML_EXP_OR) {
6545	    xmlExpNodePtr tmp;
6546
6547	    /* OR canonicalization rule 2 */
6548	    if ((left->exp_right->type != XML_EXP_OR) &&
6549	        (left->exp_right->key < left->exp_left->key)) {
6550	        tmp = left->exp_right;
6551		left->exp_right = left->exp_left;
6552		left->exp_left = tmp;
6553	    }
6554	    left->exp_right->ref++;
6555	    tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left->exp_right, right,
6556	                             NULL, 0, 0);
6557	    left->exp_left->ref++;
6558	    tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left->exp_left, tmp,
6559	                             NULL, 0, 0);
6560
6561	    xmlExpFree(ctxt, left);
6562	    return(tmp);
6563	}
6564	if (right->type == XML_EXP_OR) {
6565	    /* Ordering in the tree */
6566	    /* C | (A | B) -> A | (B | C) */
6567	    if (left->key > right->exp_right->key) {
6568		xmlExpNodePtr tmp;
6569		right->exp_right->ref++;
6570		tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_right,
6571		                         left, NULL, 0, 0);
6572		right->exp_left->ref++;
6573		tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_left,
6574		                         tmp, NULL, 0, 0);
6575		xmlExpFree(ctxt, right);
6576		return(tmp);
6577	    }
6578	    /* Ordering in the tree */
6579	    /* B | (A | C) -> A | (B | C) */
6580	    if (left->key > right->exp_left->key) {
6581		xmlExpNodePtr tmp;
6582		right->exp_right->ref++;
6583		tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, left,
6584		                         right->exp_right, NULL, 0, 0);
6585		right->exp_left->ref++;
6586		tmp = xmlExpHashGetEntry(ctxt, XML_EXP_OR, right->exp_left,
6587		                         tmp, NULL, 0, 0);
6588		xmlExpFree(ctxt, right);
6589		return(tmp);
6590	    }
6591	}
6592	/* we know both types are != XML_EXP_OR here */
6593        else if (left->key > right->key) {
6594	    xmlExpNodePtr tmp = left;
6595            left = right;
6596	    right = tmp;
6597	}
6598	kbase = xmlExpHashComputeKey(type, left, right);
6599    } else if (type == XML_EXP_SEQ) {
6600        /* Forbid reduction rules */
6601        if (left->type == XML_EXP_FORBID) {
6602	    xmlExpFree(ctxt, right);
6603	    return(left);
6604	}
6605        if (right->type == XML_EXP_FORBID) {
6606	    xmlExpFree(ctxt, left);
6607	    return(right);
6608	}
6609        /* Empty reduction rules */
6610        if (right->type == XML_EXP_EMPTY) {
6611	    return(left);
6612	}
6613        if (left->type == XML_EXP_EMPTY) {
6614	    return(right);
6615	}
6616	kbase = xmlExpHashComputeKey(type, left, right);
6617    } else
6618        return(NULL);
6619
6620    key = kbase % ctxt->size;
6621    if (ctxt->table[key] != NULL) {
6622	for (insert = ctxt->table[key]; insert != NULL;
6623	     insert = insert->next) {
6624	    if ((insert->key == kbase) &&
6625	        (insert->type == type)) {
6626		if (type == XML_EXP_ATOM) {
6627		    if (name == insert->exp_str) {
6628			insert->ref++;
6629			return(insert);
6630		    }
6631		} else if (type == XML_EXP_COUNT) {
6632		    if ((insert->exp_min == min) && (insert->exp_max == max) &&
6633		        (insert->exp_left == left)) {
6634			insert->ref++;
6635			left->ref--;
6636			return(insert);
6637		    }
6638		} else if ((insert->exp_left == left) &&
6639			   (insert->exp_right == right)) {
6640		    insert->ref++;
6641		    left->ref--;
6642		    right->ref--;
6643		    return(insert);
6644		}
6645	    }
6646	}
6647    }
6648
6649    entry = xmlExpNewNode(ctxt, type);
6650    if (entry == NULL)
6651        return(NULL);
6652    entry->key = kbase;
6653    if (type == XML_EXP_ATOM) {
6654	entry->exp_str = name;
6655	entry->c_max = 1;
6656    } else if (type == XML_EXP_COUNT) {
6657        entry->exp_min = min;
6658        entry->exp_max = max;
6659	entry->exp_left = left;
6660	if ((min == 0) || (IS_NILLABLE(left)))
6661	    entry->info |= XML_EXP_NILABLE;
6662	if (max < 0)
6663	    entry->c_max = -1;
6664	else
6665	    entry->c_max = max * entry->exp_left->c_max;
6666    } else {
6667	entry->exp_left = left;
6668	entry->exp_right = right;
6669	if (type == XML_EXP_OR) {
6670	    if ((IS_NILLABLE(left)) || (IS_NILLABLE(right)))
6671		entry->info |= XML_EXP_NILABLE;
6672	    if ((entry->exp_left->c_max == -1) ||
6673	        (entry->exp_right->c_max == -1))
6674		entry->c_max = -1;
6675	    else if (entry->exp_left->c_max > entry->exp_right->c_max)
6676	        entry->c_max = entry->exp_left->c_max;
6677	    else
6678	        entry->c_max = entry->exp_right->c_max;
6679	} else {
6680	    if ((IS_NILLABLE(left)) && (IS_NILLABLE(right)))
6681		entry->info |= XML_EXP_NILABLE;
6682	    if ((entry->exp_left->c_max == -1) ||
6683	        (entry->exp_right->c_max == -1))
6684		entry->c_max = -1;
6685	    else
6686	        entry->c_max = entry->exp_left->c_max + entry->exp_right->c_max;
6687	}
6688    }
6689    entry->ref = 1;
6690    if (ctxt->table[key] != NULL)
6691        entry->next = ctxt->table[key];
6692
6693    ctxt->table[key] = entry;
6694    ctxt->nbElems++;
6695
6696    return(entry);
6697}
6698
6699/**
6700 * xmlExpFree:
6701 * @ctxt: the expression context
6702 * @exp: the expression
6703 *
6704 * Dereference the expression
6705 */
6706void
6707xmlExpFree(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp) {
6708    if ((exp == NULL) || (exp == forbiddenExp) || (exp == emptyExp))
6709        return;
6710    exp->ref--;
6711    if (exp->ref == 0) {
6712        unsigned short key;
6713
6714        /* Unlink it first from the hash table */
6715	key = exp->key % ctxt->size;
6716	if (ctxt->table[key] == exp) {
6717	    ctxt->table[key] = exp->next;
6718	} else {
6719	    xmlExpNodePtr tmp;
6720
6721	    tmp = ctxt->table[key];
6722	    while (tmp != NULL) {
6723	        if (tmp->next == exp) {
6724		    tmp->next = exp->next;
6725		    break;
6726		}
6727	        tmp = tmp->next;
6728	    }
6729	}
6730
6731        if ((exp->type == XML_EXP_SEQ) || (exp->type == XML_EXP_OR)) {
6732	    xmlExpFree(ctxt, exp->exp_left);
6733	    xmlExpFree(ctxt, exp->exp_right);
6734	} else if (exp->type == XML_EXP_COUNT) {
6735	    xmlExpFree(ctxt, exp->exp_left);
6736	}
6737        xmlFree(exp);
6738	ctxt->nb_nodes--;
6739    }
6740}
6741
6742/**
6743 * xmlExpRef:
6744 * @exp: the expression
6745 *
6746 * Increase the reference count of the expression
6747 */
6748void
6749xmlExpRef(xmlExpNodePtr exp) {
6750    if (exp != NULL)
6751        exp->ref++;
6752}
6753
6754/**
6755 * xmlExpNewAtom:
6756 * @ctxt: the expression context
6757 * @name: the atom name
6758 * @len: the atom name lenght in byte (or -1);
6759 *
6760 * Get the atom associated to this name from that context
6761 *
6762 * Returns the node or NULL in case of error
6763 */
6764xmlExpNodePtr
6765xmlExpNewAtom(xmlExpCtxtPtr ctxt, const xmlChar *name, int len) {
6766    if ((ctxt == NULL) || (name == NULL))
6767        return(NULL);
6768    name = xmlDictLookup(ctxt->dict, name, len);
6769    if (name == NULL)
6770        return(NULL);
6771    return(xmlExpHashGetEntry(ctxt, XML_EXP_ATOM, NULL, NULL, name, 0, 0));
6772}
6773
6774/**
6775 * xmlExpNewOr:
6776 * @ctxt: the expression context
6777 * @left: left expression
6778 * @right: right expression
6779 *
6780 * Get the atom associated to the choice @left | @right
6781 * Note that @left and @right are consumed in the operation, to keep
6782 * an handle on them use xmlExpRef() and use xmlExpFree() to release them,
6783 * this is true even in case of failure (unless ctxt == NULL).
6784 *
6785 * Returns the node or NULL in case of error
6786 */
6787xmlExpNodePtr
6788xmlExpNewOr(xmlExpCtxtPtr ctxt, xmlExpNodePtr left, xmlExpNodePtr right) {
6789    if (ctxt == NULL)
6790        return(NULL);
6791    if ((left == NULL) || (right == NULL)) {
6792        xmlExpFree(ctxt, left);
6793        xmlExpFree(ctxt, right);
6794        return(NULL);
6795    }
6796    return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, left, right, NULL, 0, 0));
6797}
6798
6799/**
6800 * xmlExpNewSeq:
6801 * @ctxt: the expression context
6802 * @left: left expression
6803 * @right: right expression
6804 *
6805 * Get the atom associated to the sequence @left , @right
6806 * Note that @left and @right are consumed in the operation, to keep
6807 * an handle on them use xmlExpRef() and use xmlExpFree() to release them,
6808 * this is true even in case of failure (unless ctxt == NULL).
6809 *
6810 * Returns the node or NULL in case of error
6811 */
6812xmlExpNodePtr
6813xmlExpNewSeq(xmlExpCtxtPtr ctxt, xmlExpNodePtr left, xmlExpNodePtr right) {
6814    if (ctxt == NULL)
6815        return(NULL);
6816    if ((left == NULL) || (right == NULL)) {
6817        xmlExpFree(ctxt, left);
6818        xmlExpFree(ctxt, right);
6819        return(NULL);
6820    }
6821    return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, left, right, NULL, 0, 0));
6822}
6823
6824/**
6825 * xmlExpNewRange:
6826 * @ctxt: the expression context
6827 * @subset: the expression to be repeated
6828 * @min: the lower bound for the repetition
6829 * @max: the upper bound for the repetition, -1 means infinite
6830 *
6831 * Get the atom associated to the range (@subset){@min, @max}
6832 * Note that @subset is consumed in the operation, to keep
6833 * an handle on it use xmlExpRef() and use xmlExpFree() to release it,
6834 * this is true even in case of failure (unless ctxt == NULL).
6835 *
6836 * Returns the node or NULL in case of error
6837 */
6838xmlExpNodePtr
6839xmlExpNewRange(xmlExpCtxtPtr ctxt, xmlExpNodePtr subset, int min, int max) {
6840    if (ctxt == NULL)
6841        return(NULL);
6842    if ((subset == NULL) || (min < 0) || (max < -1) ||
6843        ((max >= 0) && (min > max))) {
6844	xmlExpFree(ctxt, subset);
6845        return(NULL);
6846    }
6847    return(xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, subset,
6848                              NULL, NULL, min, max));
6849}
6850
6851/************************************************************************
6852 *									*
6853 *		Public API for operations on expressions		*
6854 *									*
6855 ************************************************************************/
6856
6857static int
6858xmlExpGetLanguageInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
6859                     const xmlChar**list, int len, int nb) {
6860    int tmp, tmp2;
6861tail:
6862    switch (exp->type) {
6863        case XML_EXP_EMPTY:
6864	    return(0);
6865        case XML_EXP_ATOM:
6866	    for (tmp = 0;tmp < nb;tmp++)
6867	        if (list[tmp] == exp->exp_str)
6868		    return(0);
6869            if (nb >= len)
6870	        return(-2);
6871	    list[nb++] = exp->exp_str;
6872	    return(1);
6873        case XML_EXP_COUNT:
6874	    exp = exp->exp_left;
6875	    goto tail;
6876        case XML_EXP_SEQ:
6877        case XML_EXP_OR:
6878	    tmp = xmlExpGetLanguageInt(ctxt, exp->exp_left, list, len, nb);
6879	    if (tmp < 0)
6880	        return(tmp);
6881	    tmp2 = xmlExpGetLanguageInt(ctxt, exp->exp_right, list, len,
6882	                                nb + tmp);
6883	    if (tmp2 < 0)
6884	        return(tmp2);
6885            return(tmp + tmp2);
6886    }
6887    return(-1);
6888}
6889
6890/**
6891 * xmlExpGetLanguage:
6892 * @ctxt: the expression context
6893 * @exp: the expression
6894 * @langList: where to store the tokens
6895 * @len: the allocated lenght of @list
6896 *
6897 * Find all the strings used in @exp and store them in @list
6898 *
6899 * Returns the number of unique strings found, -1 in case of errors and
6900 *         -2 if there is more than @len strings
6901 */
6902int
6903xmlExpGetLanguage(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
6904                  const xmlChar**langList, int len) {
6905    if ((ctxt == NULL) || (exp == NULL) || (langList == NULL) || (len <= 0))
6906        return(-1);
6907    return(xmlExpGetLanguageInt(ctxt, exp, langList, len, 0));
6908}
6909
6910static int
6911xmlExpGetStartInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
6912                  const xmlChar**list, int len, int nb) {
6913    int tmp, tmp2;
6914tail:
6915    switch (exp->type) {
6916        case XML_EXP_FORBID:
6917	    return(0);
6918        case XML_EXP_EMPTY:
6919	    return(0);
6920        case XML_EXP_ATOM:
6921	    for (tmp = 0;tmp < nb;tmp++)
6922	        if (list[tmp] == exp->exp_str)
6923		    return(0);
6924            if (nb >= len)
6925	        return(-2);
6926	    list[nb++] = exp->exp_str;
6927	    return(1);
6928        case XML_EXP_COUNT:
6929	    exp = exp->exp_left;
6930	    goto tail;
6931        case XML_EXP_SEQ:
6932	    tmp = xmlExpGetStartInt(ctxt, exp->exp_left, list, len, nb);
6933	    if (tmp < 0)
6934	        return(tmp);
6935	    if (IS_NILLABLE(exp->exp_left)) {
6936		tmp2 = xmlExpGetStartInt(ctxt, exp->exp_right, list, len,
6937					    nb + tmp);
6938		if (tmp2 < 0)
6939		    return(tmp2);
6940		tmp += tmp2;
6941	    }
6942            return(tmp);
6943        case XML_EXP_OR:
6944	    tmp = xmlExpGetStartInt(ctxt, exp->exp_left, list, len, nb);
6945	    if (tmp < 0)
6946	        return(tmp);
6947	    tmp2 = xmlExpGetStartInt(ctxt, exp->exp_right, list, len,
6948	                                nb + tmp);
6949	    if (tmp2 < 0)
6950	        return(tmp2);
6951            return(tmp + tmp2);
6952    }
6953    return(-1);
6954}
6955
6956/**
6957 * xmlExpGetStart:
6958 * @ctxt: the expression context
6959 * @exp: the expression
6960 * @tokList: where to store the tokens
6961 * @len: the allocated lenght of @list
6962 *
6963 * Find all the strings that appears at the start of the languages
6964 * accepted by @exp and store them in @list. E.g. for (a, b) | c
6965 * it will return the list [a, c]
6966 *
6967 * Returns the number of unique strings found, -1 in case of errors and
6968 *         -2 if there is more than @len strings
6969 */
6970int
6971xmlExpGetStart(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
6972               const xmlChar**tokList, int len) {
6973    if ((ctxt == NULL) || (exp == NULL) || (tokList == NULL) || (len <= 0))
6974        return(-1);
6975    return(xmlExpGetStartInt(ctxt, exp, tokList, len, 0));
6976}
6977
6978/**
6979 * xmlExpIsNillable:
6980 * @exp: the expression
6981 *
6982 * Finds if the expression is nillable, i.e. if it accepts the empty sequqnce
6983 *
6984 * Returns 1 if nillable, 0 if not and -1 in case of error
6985 */
6986int
6987xmlExpIsNillable(xmlExpNodePtr exp) {
6988    if (exp == NULL)
6989        return(-1);
6990    return(IS_NILLABLE(exp) != 0);
6991}
6992
6993static xmlExpNodePtr
6994xmlExpStringDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, const xmlChar *str)
6995{
6996    xmlExpNodePtr ret;
6997
6998    switch (exp->type) {
6999	case XML_EXP_EMPTY:
7000	    return(forbiddenExp);
7001	case XML_EXP_FORBID:
7002	    return(forbiddenExp);
7003	case XML_EXP_ATOM:
7004	    if (exp->exp_str == str) {
7005#ifdef DEBUG_DERIV
7006		printf("deriv atom: equal => Empty\n");
7007#endif
7008	        ret = emptyExp;
7009	    } else {
7010#ifdef DEBUG_DERIV
7011		printf("deriv atom: mismatch => forbid\n");
7012#endif
7013	        /* TODO wildcards here */
7014		ret = forbiddenExp;
7015	    }
7016	    return(ret);
7017	case XML_EXP_OR: {
7018	    xmlExpNodePtr tmp;
7019
7020#ifdef DEBUG_DERIV
7021	    printf("deriv or: => or(derivs)\n");
7022#endif
7023	    tmp = xmlExpStringDeriveInt(ctxt, exp->exp_left, str);
7024	    if (tmp == NULL) {
7025		return(NULL);
7026	    }
7027	    ret = xmlExpStringDeriveInt(ctxt, exp->exp_right, str);
7028	    if (ret == NULL) {
7029	        xmlExpFree(ctxt, tmp);
7030		return(NULL);
7031	    }
7032            ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, tmp, ret,
7033			     NULL, 0, 0);
7034	    return(ret);
7035	}
7036	case XML_EXP_SEQ:
7037#ifdef DEBUG_DERIV
7038	    printf("deriv seq: starting with left\n");
7039#endif
7040	    ret = xmlExpStringDeriveInt(ctxt, exp->exp_left, str);
7041	    if (ret == NULL) {
7042	        return(NULL);
7043	    } else if (ret == forbiddenExp) {
7044	        if (IS_NILLABLE(exp->exp_left)) {
7045#ifdef DEBUG_DERIV
7046		    printf("deriv seq: left failed but nillable\n");
7047#endif
7048		    ret = xmlExpStringDeriveInt(ctxt, exp->exp_right, str);
7049		}
7050	    } else {
7051#ifdef DEBUG_DERIV
7052		printf("deriv seq: left match => sequence\n");
7053#endif
7054	        exp->exp_right->ref++;
7055	        ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, exp->exp_right,
7056		                         NULL, 0, 0);
7057	    }
7058	    return(ret);
7059	case XML_EXP_COUNT: {
7060	    int min, max;
7061	    xmlExpNodePtr tmp;
7062
7063	    if (exp->exp_max == 0)
7064		return(forbiddenExp);
7065	    ret = xmlExpStringDeriveInt(ctxt, exp->exp_left, str);
7066	    if (ret == NULL)
7067	        return(NULL);
7068	    if (ret == forbiddenExp) {
7069#ifdef DEBUG_DERIV
7070		printf("deriv count: pattern mismatch => forbid\n");
7071#endif
7072	        return(ret);
7073	    }
7074	    if (exp->exp_max == 1)
7075		return(ret);
7076	    if (exp->exp_max < 0) /* unbounded */
7077		max = -1;
7078	    else
7079		max = exp->exp_max - 1;
7080	    if (exp->exp_min > 0)
7081		min = exp->exp_min - 1;
7082	    else
7083		min = 0;
7084	    exp->exp_left->ref++;
7085	    tmp = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left, NULL,
7086				     NULL, min, max);
7087	    if (ret == emptyExp) {
7088#ifdef DEBUG_DERIV
7089		printf("deriv count: match to empty => new count\n");
7090#endif
7091	        return(tmp);
7092	    }
7093#ifdef DEBUG_DERIV
7094	    printf("deriv count: match => sequence with new count\n");
7095#endif
7096	    return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, tmp,
7097	                              NULL, 0, 0));
7098	}
7099    }
7100    return(NULL);
7101}
7102
7103/**
7104 * xmlExpStringDerive:
7105 * @ctxt: the expression context
7106 * @exp: the expression
7107 * @str: the string
7108 * @len: the string len in bytes if available
7109 *
7110 * Do one step of Brzozowski derivation of the expression @exp with
7111 * respect to the input string
7112 *
7113 * Returns the resulting expression or NULL in case of internal error
7114 */
7115xmlExpNodePtr
7116xmlExpStringDerive(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
7117                   const xmlChar *str, int len) {
7118    const xmlChar *input;
7119
7120    if ((exp == NULL) || (ctxt == NULL) || (str == NULL)) {
7121        return(NULL);
7122    }
7123    /*
7124     * check the string is in the dictionnary, if yes use an interned
7125     * copy, otherwise we know it's not an acceptable input
7126     */
7127    input = xmlDictExists(ctxt->dict, str, len);
7128    if (input == NULL) {
7129        return(forbiddenExp);
7130    }
7131    return(xmlExpStringDeriveInt(ctxt, exp, input));
7132}
7133
7134static int
7135xmlExpCheckCard(xmlExpNodePtr exp, xmlExpNodePtr sub) {
7136    int ret = 1;
7137
7138    if (sub->c_max == -1) {
7139        if (exp->c_max != -1)
7140	    ret = 0;
7141    } else if ((exp->c_max >= 0) && (exp->c_max < sub->c_max)) {
7142        ret = 0;
7143    }
7144#if 0
7145    if ((IS_NILLABLE(sub)) && (!IS_NILLABLE(exp)))
7146        ret = 0;
7147#endif
7148    return(ret);
7149}
7150
7151static xmlExpNodePtr xmlExpExpDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp,
7152                                        xmlExpNodePtr sub);
7153/**
7154 * xmlExpDivide:
7155 * @ctxt: the expressions context
7156 * @exp: the englobing expression
7157 * @sub: the subexpression
7158 * @mult: the multiple expression
7159 * @remain: the remain from the derivation of the multiple
7160 *
7161 * Check if exp is a multiple of sub, i.e. if there is a finite number n
7162 * so that sub{n} subsume exp
7163 *
7164 * Returns the multiple value if successful, 0 if it is not a multiple
7165 *         and -1 in case of internel error.
7166 */
7167
7168static int
7169xmlExpDivide(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub,
7170             xmlExpNodePtr *mult, xmlExpNodePtr *remain) {
7171    int i;
7172    xmlExpNodePtr tmp, tmp2;
7173
7174    if (mult != NULL) *mult = NULL;
7175    if (remain != NULL) *remain = NULL;
7176    if (exp->c_max == -1) return(0);
7177    if (IS_NILLABLE(exp) && (!IS_NILLABLE(sub))) return(0);
7178
7179    for (i = 1;i <= exp->c_max;i++) {
7180        sub->ref++;
7181        tmp = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT,
7182				 sub, NULL, NULL, i, i);
7183	if (tmp == NULL) {
7184	    return(-1);
7185	}
7186	if (!xmlExpCheckCard(tmp, exp)) {
7187	    xmlExpFree(ctxt, tmp);
7188	    continue;
7189	}
7190	tmp2 = xmlExpExpDeriveInt(ctxt, tmp, exp);
7191	if (tmp2 == NULL) {
7192	    xmlExpFree(ctxt, tmp);
7193	    return(-1);
7194	}
7195	if ((tmp2 != forbiddenExp) && (IS_NILLABLE(tmp2))) {
7196	    if (remain != NULL)
7197	        *remain = tmp2;
7198	    else
7199	        xmlExpFree(ctxt, tmp2);
7200	    if (mult != NULL)
7201	        *mult = tmp;
7202	    else
7203	        xmlExpFree(ctxt, tmp);
7204#ifdef DEBUG_DERIV
7205	    printf("Divide succeeded %d\n", i);
7206#endif
7207	    return(i);
7208	}
7209	xmlExpFree(ctxt, tmp);
7210	xmlExpFree(ctxt, tmp2);
7211    }
7212#ifdef DEBUG_DERIV
7213    printf("Divide failed\n");
7214#endif
7215    return(0);
7216}
7217
7218/**
7219 * xmlExpExpDeriveInt:
7220 * @ctxt: the expressions context
7221 * @exp: the englobing expression
7222 * @sub: the subexpression
7223 *
7224 * Try to do a step of Brzozowski derivation but at a higher level
7225 * the input being a subexpression.
7226 *
7227 * Returns the resulting expression or NULL in case of internal error
7228 */
7229static xmlExpNodePtr
7230xmlExpExpDeriveInt(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) {
7231    xmlExpNodePtr ret, tmp, tmp2, tmp3;
7232    const xmlChar **tab;
7233    int len, i;
7234
7235    /*
7236     * In case of equality and if the expression can only consume a finite
7237     * amount, then the derivation is empty
7238     */
7239    if ((exp == sub) && (exp->c_max >= 0)) {
7240#ifdef DEBUG_DERIV
7241        printf("Equal(exp, sub) and finite -> Empty\n");
7242#endif
7243        return(emptyExp);
7244    }
7245    /*
7246     * decompose sub sequence first
7247     */
7248    if (sub->type == XML_EXP_EMPTY) {
7249#ifdef DEBUG_DERIV
7250        printf("Empty(sub) -> Empty\n");
7251#endif
7252	exp->ref++;
7253        return(exp);
7254    }
7255    if (sub->type == XML_EXP_SEQ) {
7256#ifdef DEBUG_DERIV
7257        printf("Seq(sub) -> decompose\n");
7258#endif
7259        tmp = xmlExpExpDeriveInt(ctxt, exp, sub->exp_left);
7260	if (tmp == NULL)
7261	    return(NULL);
7262	if (tmp == forbiddenExp)
7263	    return(tmp);
7264	ret = xmlExpExpDeriveInt(ctxt, tmp, sub->exp_right);
7265	xmlExpFree(ctxt, tmp);
7266	return(ret);
7267    }
7268    if (sub->type == XML_EXP_OR) {
7269#ifdef DEBUG_DERIV
7270        printf("Or(sub) -> decompose\n");
7271#endif
7272        tmp = xmlExpExpDeriveInt(ctxt, exp, sub->exp_left);
7273	if (tmp == forbiddenExp)
7274	    return(tmp);
7275	if (tmp == NULL)
7276	    return(NULL);
7277	ret = xmlExpExpDeriveInt(ctxt, exp, sub->exp_right);
7278	if ((ret == NULL) || (ret == forbiddenExp)) {
7279	    xmlExpFree(ctxt, tmp);
7280	    return(ret);
7281	}
7282	return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, tmp, ret, NULL, 0, 0));
7283    }
7284    if (!xmlExpCheckCard(exp, sub)) {
7285#ifdef DEBUG_DERIV
7286        printf("CheckCard(exp, sub) failed -> Forbid\n");
7287#endif
7288        return(forbiddenExp);
7289    }
7290    switch (exp->type) {
7291        case XML_EXP_EMPTY:
7292	    if (sub == emptyExp)
7293	        return(emptyExp);
7294#ifdef DEBUG_DERIV
7295	    printf("Empty(exp) -> Forbid\n");
7296#endif
7297	    return(forbiddenExp);
7298        case XML_EXP_FORBID:
7299#ifdef DEBUG_DERIV
7300	    printf("Forbid(exp) -> Forbid\n");
7301#endif
7302	    return(forbiddenExp);
7303        case XML_EXP_ATOM:
7304	    if (sub->type == XML_EXP_ATOM) {
7305	        /* TODO: handle wildcards */
7306	        if (exp->exp_str == sub->exp_str) {
7307#ifdef DEBUG_DERIV
7308		    printf("Atom match -> Empty\n");
7309#endif
7310		    return(emptyExp);
7311                }
7312#ifdef DEBUG_DERIV
7313		printf("Atom mismatch -> Forbid\n");
7314#endif
7315	        return(forbiddenExp);
7316	    }
7317	    if ((sub->type == XML_EXP_COUNT) &&
7318	        (sub->exp_max == 1) &&
7319	        (sub->exp_left->type == XML_EXP_ATOM)) {
7320	        /* TODO: handle wildcards */
7321	        if (exp->exp_str == sub->exp_left->exp_str) {
7322#ifdef DEBUG_DERIV
7323		    printf("Atom match -> Empty\n");
7324#endif
7325		    return(emptyExp);
7326		}
7327#ifdef DEBUG_DERIV
7328		printf("Atom mismatch -> Forbid\n");
7329#endif
7330	        return(forbiddenExp);
7331	    }
7332#ifdef DEBUG_DERIV
7333	    printf("Compex exp vs Atom -> Forbid\n");
7334#endif
7335	    return(forbiddenExp);
7336        case XML_EXP_SEQ:
7337	    /* try to get the sequence consumed only if possible */
7338	    if (xmlExpCheckCard(exp->exp_left, sub)) {
7339		/* See if the sequence can be consumed directly */
7340#ifdef DEBUG_DERIV
7341		printf("Seq trying left only\n");
7342#endif
7343		ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub);
7344		if ((ret != forbiddenExp) && (ret != NULL)) {
7345#ifdef DEBUG_DERIV
7346		    printf("Seq trying left only worked\n");
7347#endif
7348		    /*
7349		     * TODO: assumption here that we are determinist
7350		     *       i.e. we won't get to a nillable exp left
7351		     *       subset which could be matched by the right
7352		     *       part too.
7353		     * e.g.: (a | b)+,(a | c) and 'a+,a'
7354		     */
7355		    exp->exp_right->ref++;
7356		    return(xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret,
7357					      exp->exp_right, NULL, 0, 0));
7358		}
7359#ifdef DEBUG_DERIV
7360	    } else {
7361		printf("Seq: left too short\n");
7362#endif
7363	    }
7364	    /* Try instead to decompose */
7365	    if (sub->type == XML_EXP_COUNT) {
7366		int min, max;
7367
7368#ifdef DEBUG_DERIV
7369		printf("Seq: sub is a count\n");
7370#endif
7371	        ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub->exp_left);
7372		if (ret == NULL)
7373		    return(NULL);
7374		if (ret != forbiddenExp) {
7375#ifdef DEBUG_DERIV
7376		    printf("Seq , Count match on left\n");
7377#endif
7378		    if (sub->exp_max < 0)
7379		        max = -1;
7380	            else
7381		        max = sub->exp_max -1;
7382		    if (sub->exp_min > 0)
7383		        min = sub->exp_min -1;
7384		    else
7385		        min = 0;
7386		    exp->exp_right->ref++;
7387		    tmp = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret,
7388		                             exp->exp_right, NULL, 0, 0);
7389		    if (tmp == NULL)
7390		        return(NULL);
7391
7392		    sub->exp_left->ref++;
7393		    tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT,
7394				      sub->exp_left, NULL, NULL, min, max);
7395		    if (tmp2 == NULL) {
7396		        xmlExpFree(ctxt, tmp);
7397			return(NULL);
7398		    }
7399		    ret = xmlExpExpDeriveInt(ctxt, tmp, tmp2);
7400		    xmlExpFree(ctxt, tmp);
7401		    xmlExpFree(ctxt, tmp2);
7402		    return(ret);
7403		}
7404	    }
7405	    /* we made no progress on structured operations */
7406	    break;
7407        case XML_EXP_OR:
7408#ifdef DEBUG_DERIV
7409	    printf("Or , trying both side\n");
7410#endif
7411	    ret = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub);
7412	    if (ret == NULL)
7413	        return(NULL);
7414	    tmp = xmlExpExpDeriveInt(ctxt, exp->exp_right, sub);
7415	    if (tmp == NULL) {
7416		xmlExpFree(ctxt, ret);
7417	        return(NULL);
7418	    }
7419	    return(xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, tmp, NULL, 0, 0));
7420        case XML_EXP_COUNT: {
7421	    int min, max;
7422
7423	    if (sub->type == XML_EXP_COUNT) {
7424	        /*
7425		 * Try to see if the loop is completely subsumed
7426		 */
7427	        tmp = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub->exp_left);
7428		if (tmp == NULL)
7429		    return(NULL);
7430		if (tmp == forbiddenExp) {
7431		    int mult;
7432
7433#ifdef DEBUG_DERIV
7434		    printf("Count, Count inner don't subsume\n");
7435#endif
7436		    mult = xmlExpDivide(ctxt, sub->exp_left, exp->exp_left,
7437		                        NULL, &tmp);
7438		    if (mult <= 0) {
7439#ifdef DEBUG_DERIV
7440			printf("Count, Count not multiple => forbidden\n");
7441#endif
7442                        return(forbiddenExp);
7443		    }
7444		    if (sub->exp_max == -1) {
7445		        max = -1;
7446			if (exp->exp_max == -1) {
7447			    if (exp->exp_min <= sub->exp_min * mult)
7448			        min = 0;
7449			    else
7450			        min = exp->exp_min - sub->exp_min * mult;
7451			} else {
7452#ifdef DEBUG_DERIV
7453			    printf("Count, Count finite can't subsume infinite\n");
7454#endif
7455                            xmlExpFree(ctxt, tmp);
7456			    return(forbiddenExp);
7457			}
7458		    } else {
7459			if (exp->exp_max == -1) {
7460#ifdef DEBUG_DERIV
7461			    printf("Infinite loop consume mult finite loop\n");
7462#endif
7463			    if (exp->exp_min > sub->exp_min * mult) {
7464				max = -1;
7465				min = exp->exp_min - sub->exp_min * mult;
7466			    } else {
7467				max = -1;
7468				min = 0;
7469			    }
7470			} else {
7471			    if (exp->exp_max < sub->exp_max * mult) {
7472#ifdef DEBUG_DERIV
7473				printf("loops max mult mismatch => forbidden\n");
7474#endif
7475				xmlExpFree(ctxt, tmp);
7476				return(forbiddenExp);
7477			    }
7478			    if (sub->exp_max * mult > exp->exp_min)
7479				min = 0;
7480			    else
7481				min = exp->exp_min - sub->exp_max * mult;
7482			    max = exp->exp_max - sub->exp_max * mult;
7483			}
7484		    }
7485		} else if (!IS_NILLABLE(tmp)) {
7486		    /*
7487		     * TODO: loop here to try to grow if working on finite
7488		     *       blocks.
7489		     */
7490#ifdef DEBUG_DERIV
7491		    printf("Count, Count remain not nillable => forbidden\n");
7492#endif
7493		    xmlExpFree(ctxt, tmp);
7494		    return(forbiddenExp);
7495		} else if (sub->exp_max == -1) {
7496		    if (exp->exp_max == -1) {
7497		        if (exp->exp_min <= sub->exp_min) {
7498#ifdef DEBUG_DERIV
7499			    printf("Infinite loops Okay => COUNT(0,Inf)\n");
7500#endif
7501                            max = -1;
7502			    min = 0;
7503			} else {
7504#ifdef DEBUG_DERIV
7505			    printf("Infinite loops min => Count(X,Inf)\n");
7506#endif
7507                            max = -1;
7508			    min = exp->exp_min - sub->exp_min;
7509			}
7510		    } else if (exp->exp_min > sub->exp_min) {
7511#ifdef DEBUG_DERIV
7512			printf("loops min mismatch 1 => forbidden ???\n");
7513#endif
7514		        xmlExpFree(ctxt, tmp);
7515		        return(forbiddenExp);
7516		    } else {
7517			max = -1;
7518			min = 0;
7519		    }
7520		} else {
7521		    if (exp->exp_max == -1) {
7522#ifdef DEBUG_DERIV
7523			printf("Infinite loop consume finite loop\n");
7524#endif
7525		        if (exp->exp_min > sub->exp_min) {
7526			    max = -1;
7527			    min = exp->exp_min - sub->exp_min;
7528			} else {
7529			    max = -1;
7530			    min = 0;
7531			}
7532		    } else {
7533		        if (exp->exp_max < sub->exp_max) {
7534#ifdef DEBUG_DERIV
7535			    printf("loops max mismatch => forbidden\n");
7536#endif
7537			    xmlExpFree(ctxt, tmp);
7538			    return(forbiddenExp);
7539			}
7540			if (sub->exp_max > exp->exp_min)
7541			    min = 0;
7542			else
7543			    min = exp->exp_min - sub->exp_max;
7544			max = exp->exp_max - sub->exp_max;
7545		    }
7546		}
7547#ifdef DEBUG_DERIV
7548		printf("loops match => SEQ(COUNT())\n");
7549#endif
7550		exp->exp_left->ref++;
7551		tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left,
7552		                          NULL, NULL, min, max);
7553		if (tmp2 == NULL) {
7554		    return(NULL);
7555		}
7556                ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, tmp, tmp2,
7557		                         NULL, 0, 0);
7558		return(ret);
7559	    }
7560	    tmp = xmlExpExpDeriveInt(ctxt, exp->exp_left, sub);
7561	    if (tmp == NULL)
7562		return(NULL);
7563	    if (tmp == forbiddenExp) {
7564#ifdef DEBUG_DERIV
7565		printf("loop mismatch => forbidden\n");
7566#endif
7567		return(forbiddenExp);
7568	    }
7569	    if (exp->exp_min > 0)
7570		min = exp->exp_min - 1;
7571	    else
7572		min = 0;
7573	    if (exp->exp_max < 0)
7574		max = -1;
7575	    else
7576		max = exp->exp_max - 1;
7577
7578#ifdef DEBUG_DERIV
7579	    printf("loop match => SEQ(COUNT())\n");
7580#endif
7581	    exp->exp_left->ref++;
7582	    tmp2 = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, exp->exp_left,
7583				      NULL, NULL, min, max);
7584	    if (tmp2 == NULL)
7585		return(NULL);
7586	    ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, tmp, tmp2,
7587				     NULL, 0, 0);
7588	    return(ret);
7589	}
7590    }
7591
7592#ifdef DEBUG_DERIV
7593    printf("Fallback to derivative\n");
7594#endif
7595    if (IS_NILLABLE(sub)) {
7596        if (!(IS_NILLABLE(exp)))
7597	    return(forbiddenExp);
7598	else
7599	    ret = emptyExp;
7600    } else
7601	ret = NULL;
7602    /*
7603     * here the structured derivation made no progress so
7604     * we use the default token based derivation to force one more step
7605     */
7606    if (ctxt->tabSize == 0)
7607        ctxt->tabSize = 40;
7608
7609    tab = (const xmlChar **) xmlMalloc(ctxt->tabSize *
7610	                               sizeof(const xmlChar *));
7611    if (tab == NULL) {
7612	return(NULL);
7613    }
7614
7615    /*
7616     * collect all the strings accepted by the subexpression on input
7617     */
7618    len = xmlExpGetStartInt(ctxt, sub, tab, ctxt->tabSize, 0);
7619    while (len < 0) {
7620        const xmlChar **temp;
7621	temp = (const xmlChar **) xmlRealloc((xmlChar **) tab, ctxt->tabSize * 2 *
7622	                                     sizeof(const xmlChar *));
7623	if (temp == NULL) {
7624	    xmlFree((xmlChar **) tab);
7625	    return(NULL);
7626	}
7627	tab = temp;
7628	ctxt->tabSize *= 2;
7629	len = xmlExpGetStartInt(ctxt, sub, tab, ctxt->tabSize, 0);
7630    }
7631    for (i = 0;i < len;i++) {
7632        tmp = xmlExpStringDeriveInt(ctxt, exp, tab[i]);
7633	if ((tmp == NULL) || (tmp == forbiddenExp)) {
7634	    xmlExpFree(ctxt, ret);
7635	    xmlFree((xmlChar **) tab);
7636	    return(tmp);
7637	}
7638	tmp2 = xmlExpStringDeriveInt(ctxt, sub, tab[i]);
7639	if ((tmp2 == NULL) || (tmp2 == forbiddenExp)) {
7640	    xmlExpFree(ctxt, tmp);
7641	    xmlExpFree(ctxt, ret);
7642	    xmlFree((xmlChar **) tab);
7643	    return(tmp);
7644	}
7645	tmp3 = xmlExpExpDeriveInt(ctxt, tmp, tmp2);
7646	xmlExpFree(ctxt, tmp);
7647	xmlExpFree(ctxt, tmp2);
7648
7649	if ((tmp3 == NULL) || (tmp3 == forbiddenExp)) {
7650	    xmlExpFree(ctxt, ret);
7651	    xmlFree((xmlChar **) tab);
7652	    return(tmp3);
7653	}
7654
7655	if (ret == NULL)
7656	    ret = tmp3;
7657	else {
7658	    ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, tmp3, NULL, 0, 0);
7659	    if (ret == NULL) {
7660		xmlFree((xmlChar **) tab);
7661	        return(NULL);
7662	    }
7663	}
7664    }
7665    xmlFree((xmlChar **) tab);
7666    return(ret);
7667}
7668
7669/**
7670 * xmlExpExpDerive:
7671 * @ctxt: the expressions context
7672 * @exp: the englobing expression
7673 * @sub: the subexpression
7674 *
7675 * Evaluates the expression resulting from @exp consuming a sub expression @sub
7676 * Based on algebraic derivation and sometimes direct Brzozowski derivation
7677 * it usually tatkes less than linear time and can handle expressions generating
7678 * infinite languages.
7679 *
7680 * Returns the resulting expression or NULL in case of internal error, the
7681 *         result must be freed
7682 */
7683xmlExpNodePtr
7684xmlExpExpDerive(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) {
7685    if ((exp == NULL) || (ctxt == NULL) || (sub == NULL))
7686        return(NULL);
7687
7688    /*
7689     * O(1) speedups
7690     */
7691    if (IS_NILLABLE(sub) && (!IS_NILLABLE(exp))) {
7692#ifdef DEBUG_DERIV
7693	printf("Sub nillable and not exp : can't subsume\n");
7694#endif
7695        return(forbiddenExp);
7696    }
7697    if (xmlExpCheckCard(exp, sub) == 0) {
7698#ifdef DEBUG_DERIV
7699	printf("sub generate longuer sequances than exp : can't subsume\n");
7700#endif
7701        return(forbiddenExp);
7702    }
7703    return(xmlExpExpDeriveInt(ctxt, exp, sub));
7704}
7705
7706/**
7707 * xmlExpSubsume:
7708 * @ctxt: the expressions context
7709 * @exp: the englobing expression
7710 * @sub: the subexpression
7711 *
7712 * Check whether @exp accepts all the languages accexpted by @sub
7713 * the input being a subexpression.
7714 *
7715 * Returns 1 if true 0 if false and -1 in case of failure.
7716 */
7717int
7718xmlExpSubsume(xmlExpCtxtPtr ctxt, xmlExpNodePtr exp, xmlExpNodePtr sub) {
7719    xmlExpNodePtr tmp;
7720
7721    if ((exp == NULL) || (ctxt == NULL) || (sub == NULL))
7722        return(-1);
7723
7724    /*
7725     * TODO: speedup by checking the language of sub is a subset of the
7726     *       language of exp
7727     */
7728    /*
7729     * O(1) speedups
7730     */
7731    if (IS_NILLABLE(sub) && (!IS_NILLABLE(exp))) {
7732#ifdef DEBUG_DERIV
7733	printf("Sub nillable and not exp : can't subsume\n");
7734#endif
7735        return(0);
7736    }
7737    if (xmlExpCheckCard(exp, sub) == 0) {
7738#ifdef DEBUG_DERIV
7739	printf("sub generate longuer sequances than exp : can't subsume\n");
7740#endif
7741        return(0);
7742    }
7743    tmp = xmlExpExpDeriveInt(ctxt, exp, sub);
7744#ifdef DEBUG_DERIV
7745    printf("Result derivation :\n");
7746    PRINT_EXP(tmp);
7747#endif
7748    if (tmp == NULL)
7749        return(-1);
7750    if (tmp == forbiddenExp)
7751	return(0);
7752    if (tmp == emptyExp)
7753	return(1);
7754    if ((tmp != NULL) && (IS_NILLABLE(tmp))) {
7755        xmlExpFree(ctxt, tmp);
7756        return(1);
7757    }
7758    xmlExpFree(ctxt, tmp);
7759    return(0);
7760}
7761
7762/************************************************************************
7763 *									*
7764 *			Parsing expression 				*
7765 *									*
7766 ************************************************************************/
7767
7768static xmlExpNodePtr xmlExpParseExpr(xmlExpCtxtPtr ctxt);
7769
7770#undef CUR
7771#define CUR (*ctxt->cur)
7772#undef NEXT
7773#define NEXT ctxt->cur++;
7774#undef IS_BLANK
7775#define IS_BLANK(c) ((c == ' ') || (c == '\n') || (c == '\r') || (c == '\t'))
7776#define SKIP_BLANKS while (IS_BLANK(*ctxt->cur)) ctxt->cur++;
7777
7778static int
7779xmlExpParseNumber(xmlExpCtxtPtr ctxt) {
7780    int ret = 0;
7781
7782    SKIP_BLANKS
7783    if (CUR == '*') {
7784	NEXT
7785	return(-1);
7786    }
7787    if ((CUR < '0') || (CUR > '9'))
7788        return(-1);
7789    while ((CUR >= '0') && (CUR <= '9')) {
7790        ret = ret * 10 + (CUR - '0');
7791	NEXT
7792    }
7793    return(ret);
7794}
7795
7796static xmlExpNodePtr
7797xmlExpParseOr(xmlExpCtxtPtr ctxt) {
7798    const char *base;
7799    xmlExpNodePtr ret;
7800    const xmlChar *val;
7801
7802    SKIP_BLANKS
7803    base = ctxt->cur;
7804    if (*ctxt->cur == '(') {
7805        NEXT
7806	ret = xmlExpParseExpr(ctxt);
7807	SKIP_BLANKS
7808	if (*ctxt->cur != ')') {
7809	    fprintf(stderr, "unbalanced '(' : %s\n", base);
7810	    xmlExpFree(ctxt, ret);
7811	    return(NULL);
7812	}
7813	NEXT;
7814	SKIP_BLANKS
7815	goto parse_quantifier;
7816    }
7817    while ((CUR != 0) && (!(IS_BLANK(CUR))) && (CUR != '(') &&
7818           (CUR != ')') && (CUR != '|') && (CUR != ',') && (CUR != '{') &&
7819	   (CUR != '*') && (CUR != '+') && (CUR != '?') && (CUR != '}'))
7820	NEXT;
7821    val = xmlDictLookup(ctxt->dict, BAD_CAST base, ctxt->cur - base);
7822    if (val == NULL)
7823        return(NULL);
7824    ret = xmlExpHashGetEntry(ctxt, XML_EXP_ATOM, NULL, NULL, val, 0, 0);
7825    if (ret == NULL)
7826        return(NULL);
7827    SKIP_BLANKS
7828parse_quantifier:
7829    if (CUR == '{') {
7830        int min, max;
7831
7832        NEXT
7833	min = xmlExpParseNumber(ctxt);
7834	if (min < 0) {
7835	    xmlExpFree(ctxt, ret);
7836	    return(NULL);
7837	}
7838	SKIP_BLANKS
7839	if (CUR == ',') {
7840	    NEXT
7841	    max = xmlExpParseNumber(ctxt);
7842	    SKIP_BLANKS
7843	} else
7844	    max = min;
7845	if (CUR != '}') {
7846	    xmlExpFree(ctxt, ret);
7847	    return(NULL);
7848	}
7849        NEXT
7850	ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,
7851	                         min, max);
7852	SKIP_BLANKS
7853    } else if (CUR == '?') {
7854        NEXT
7855	ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,
7856	                         0, 1);
7857	SKIP_BLANKS
7858    } else if (CUR == '+') {
7859        NEXT
7860	ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,
7861	                         1, -1);
7862	SKIP_BLANKS
7863    } else if (CUR == '*') {
7864        NEXT
7865	ret = xmlExpHashGetEntry(ctxt, XML_EXP_COUNT, ret, NULL, NULL,
7866	                         0, -1);
7867	SKIP_BLANKS
7868    }
7869    return(ret);
7870}
7871
7872
7873static xmlExpNodePtr
7874xmlExpParseSeq(xmlExpCtxtPtr ctxt) {
7875    xmlExpNodePtr ret, right;
7876
7877    ret = xmlExpParseOr(ctxt);
7878    SKIP_BLANKS
7879    while (CUR == '|') {
7880        NEXT
7881	right = xmlExpParseOr(ctxt);
7882	if (right == NULL) {
7883	    xmlExpFree(ctxt, ret);
7884	    return(NULL);
7885	}
7886	ret = xmlExpHashGetEntry(ctxt, XML_EXP_OR, ret, right, NULL, 0, 0);
7887	if (ret == NULL)
7888	    return(NULL);
7889    }
7890    return(ret);
7891}
7892
7893static xmlExpNodePtr
7894xmlExpParseExpr(xmlExpCtxtPtr ctxt) {
7895    xmlExpNodePtr ret, right;
7896
7897    ret = xmlExpParseSeq(ctxt);
7898    SKIP_BLANKS
7899    while (CUR == ',') {
7900        NEXT
7901	right = xmlExpParseSeq(ctxt);
7902	if (right == NULL) {
7903	    xmlExpFree(ctxt, ret);
7904	    return(NULL);
7905	}
7906	ret = xmlExpHashGetEntry(ctxt, XML_EXP_SEQ, ret, right, NULL, 0, 0);
7907	if (ret == NULL)
7908	    return(NULL);
7909    }
7910    return(ret);
7911}
7912
7913/**
7914 * xmlExpParse:
7915 * @ctxt: the expressions context
7916 * @expr: the 0 terminated string
7917 *
7918 * Minimal parser for regexps, it understand the following constructs
7919 *  - string terminals
7920 *  - choice operator |
7921 *  - sequence operator ,
7922 *  - subexpressions (...)
7923 *  - usual cardinality operators + * and ?
7924 *  - finite sequences  { min, max }
7925 *  - infinite sequences { min, * }
7926 * There is minimal checkings made especially no checking on strings values
7927 *
7928 * Returns a new expression or NULL in case of failure
7929 */
7930xmlExpNodePtr
7931xmlExpParse(xmlExpCtxtPtr ctxt, const char *expr) {
7932    xmlExpNodePtr ret;
7933
7934    ctxt->expr = expr;
7935    ctxt->cur = expr;
7936
7937    ret = xmlExpParseExpr(ctxt);
7938    SKIP_BLANKS
7939    if (*ctxt->cur != 0) {
7940        xmlExpFree(ctxt, ret);
7941        return(NULL);
7942    }
7943    return(ret);
7944}
7945
7946static void
7947xmlExpDumpInt(xmlBufferPtr buf, xmlExpNodePtr expr, int glob) {
7948    xmlExpNodePtr c;
7949
7950    if (expr == NULL) return;
7951    if (glob) xmlBufferWriteChar(buf, "(");
7952    switch (expr->type) {
7953        case XML_EXP_EMPTY:
7954	    xmlBufferWriteChar(buf, "empty");
7955	    break;
7956        case XML_EXP_FORBID:
7957	    xmlBufferWriteChar(buf, "forbidden");
7958	    break;
7959        case XML_EXP_ATOM:
7960	    xmlBufferWriteCHAR(buf, expr->exp_str);
7961	    break;
7962        case XML_EXP_SEQ:
7963	    c = expr->exp_left;
7964	    if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))
7965	        xmlExpDumpInt(buf, c, 1);
7966	    else
7967	        xmlExpDumpInt(buf, c, 0);
7968	    xmlBufferWriteChar(buf, " , ");
7969	    c = expr->exp_right;
7970	    if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))
7971	        xmlExpDumpInt(buf, c, 1);
7972	    else
7973	        xmlExpDumpInt(buf, c, 0);
7974            break;
7975        case XML_EXP_OR:
7976	    c = expr->exp_left;
7977	    if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))
7978	        xmlExpDumpInt(buf, c, 1);
7979	    else
7980	        xmlExpDumpInt(buf, c, 0);
7981	    xmlBufferWriteChar(buf, " | ");
7982	    c = expr->exp_right;
7983	    if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))
7984	        xmlExpDumpInt(buf, c, 1);
7985	    else
7986	        xmlExpDumpInt(buf, c, 0);
7987            break;
7988        case XML_EXP_COUNT: {
7989	    char rep[40];
7990
7991	    c = expr->exp_left;
7992	    if ((c->type == XML_EXP_SEQ) || (c->type == XML_EXP_OR))
7993	        xmlExpDumpInt(buf, c, 1);
7994	    else
7995	        xmlExpDumpInt(buf, c, 0);
7996	    if ((expr->exp_min == 0) && (expr->exp_max == 1)) {
7997		rep[0] = '?';
7998		rep[1] = 0;
7999	    } else if ((expr->exp_min == 0) && (expr->exp_max == -1)) {
8000		rep[0] = '*';
8001		rep[1] = 0;
8002	    } else if ((expr->exp_min == 1) && (expr->exp_max == -1)) {
8003		rep[0] = '+';
8004		rep[1] = 0;
8005	    } else if (expr->exp_max == expr->exp_min) {
8006	        snprintf(rep, 39, "{%d}", expr->exp_min);
8007	    } else if (expr->exp_max < 0) {
8008	        snprintf(rep, 39, "{%d,inf}", expr->exp_min);
8009	    } else {
8010	        snprintf(rep, 39, "{%d,%d}", expr->exp_min, expr->exp_max);
8011	    }
8012	    rep[39] = 0;
8013	    xmlBufferWriteChar(buf, rep);
8014	    break;
8015	}
8016	default:
8017	    fprintf(stderr, "Error in tree\n");
8018    }
8019    if (glob)
8020        xmlBufferWriteChar(buf, ")");
8021}
8022/**
8023 * xmlExpDump:
8024 * @buf:  a buffer to receive the output
8025 * @expr:  the compiled expression
8026 *
8027 * Serialize the expression as compiled to the buffer
8028 */
8029void
8030xmlExpDump(xmlBufferPtr buf, xmlExpNodePtr expr) {
8031    if ((buf == NULL) || (expr == NULL))
8032        return;
8033    xmlExpDumpInt(buf, expr, 0);
8034}
8035
8036/**
8037 * xmlExpMaxToken:
8038 * @expr: a compiled expression
8039 *
8040 * Indicate the maximum number of input a expression can accept
8041 *
8042 * Returns the maximum length or -1 in case of error
8043 */
8044int
8045xmlExpMaxToken(xmlExpNodePtr expr) {
8046    if (expr == NULL)
8047        return(-1);
8048    return(expr->c_max);
8049}
8050
8051/**
8052 * xmlExpCtxtNbNodes:
8053 * @ctxt: an expression context
8054 *
8055 * Debugging facility provides the number of allocated nodes at a that point
8056 *
8057 * Returns the number of nodes in use or -1 in case of error
8058 */
8059int
8060xmlExpCtxtNbNodes(xmlExpCtxtPtr ctxt) {
8061    if (ctxt == NULL)
8062        return(-1);
8063    return(ctxt->nb_nodes);
8064}
8065
8066/**
8067 * xmlExpCtxtNbCons:
8068 * @ctxt: an expression context
8069 *
8070 * Debugging facility provides the number of allocated nodes over lifetime
8071 *
8072 * Returns the number of nodes ever allocated or -1 in case of error
8073 */
8074int
8075xmlExpCtxtNbCons(xmlExpCtxtPtr ctxt) {
8076    if (ctxt == NULL)
8077        return(-1);
8078    return(ctxt->nb_cons);
8079}
8080
8081#endif /* LIBXML_EXPR_ENABLED */
8082#define bottom_xmlregexp
8083#include "elfgcchack.h"
8084#endif /* LIBXML_REGEXP_ENABLED */
8085