xmlregexp.c

Bug Summary

File:	xmlregexp.c
Location:	line 2229, column 2
Description:	Value stored to 'ret' is never read

Annotated Source Code

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_H1
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_MAX2147483647
37	#define INT_MAX2147483647 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_PUSH10000000 10000000
46
47	#define ERROR(str)ctxt->error = XML_REGEXP_COMPILE_ERROR; xmlRegexpErrCompile (ctxt, str); \
48	ctxt->error = XML_REGEXP_COMPILE_ERROR; \
49	xmlRegexpErrCompile(ctxt, str);
50	#define NEXTctxt->cur++; ctxt->cur++
51	#define CUR(ctxt->cur) ((ctxt->cur))
52	#define NXT(index)(ctxt->cur[index]) (ctxt->cur[index])
53
54	#define CUR_SCHAR(s, l)xmlStringCurrentChar(((void)0), s, &l) xmlStringCurrentChar(NULL((void)0), s, &l)
55	#define NEXTL(l)ctxt->cur += 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]) (ctxt->cur[-1])
62
63	/**
64	* TODO:
65	*
66	* macro to flag unimplemented blocks
67	*/
68	#define TODO((__xmlGenericError()))(((__xmlGenericErrorContext())), "Unimplemented block at %s:%d\n" , "xmlregexp.c", 68); \
69	xmlGenericError((__xmlGenericError()))(xmlGenericErrorContext((__xmlGenericErrorContext())), \
70	"Unimplemented block at %s:%d\n", \
71	__FILE__"xmlregexp.c", __LINE__71);
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	*/
82	typedef 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
138	typedef 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
149	typedef 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
157	typedef enum {
158	XML_REGEXP_MARK_NORMAL = 0,
159	XML_REGEXP_MARK_START,
160	XML_REGEXP_MARK_VISITED
161	} xmlRegMarkedType;
162
163	typedef struct _xmlRegRange xmlRegRange;
164	typedef xmlRegRange *xmlRegRangePtr;
165
166	struct _xmlRegRange {
167	int neg; /* 0 normal, 1 not, 2 exclude */
168	xmlRegAtomType type;
169	int start;
170	int end;
171	xmlChar *blockName;
172	};
173
174	typedef struct _xmlRegAtom xmlRegAtom;
175	typedef xmlRegAtom *xmlRegAtomPtr;
176
177	typedef struct _xmlAutomataState xmlRegState;
178	typedef xmlRegState *xmlRegStatePtr;
179
180	struct _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
200	typedef struct _xmlRegCounter xmlRegCounter;
201	typedef xmlRegCounter *xmlRegCounterPtr;
202
203	struct _xmlRegCounter {
204	int min;
205	int max;
206	};
207
208	typedef struct _xmlRegTrans xmlRegTrans;
209	typedef xmlRegTrans *xmlRegTransPtr;
210
211	struct _xmlRegTrans {
212	xmlRegAtomPtr atom;
213	int to;
214	int counter;
215	int count;
216	int nd;
217	};
218
219	struct _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
233	typedef struct _xmlAutomata xmlRegParserCtxt;
234	typedef xmlRegParserCtxt *xmlRegParserCtxtPtr;
235
236	#define AM_AUTOMATA_RNG1 1
237
238	struct _xmlAutomata {
239	xmlChar *string;
240	xmlChar *cur;
241
242	int error;
243	int neg;
244
245	xmlRegStatePtr start;
246	xmlRegStatePtr end;
247	xmlRegStatePtr state;
248
249	xmlRegAtomPtr atom;
250
251	int maxAtoms;
252	int nbAtoms;
253	xmlRegAtomPtr *atoms;
254
255	int maxStates;
256	int nbStates;
257	xmlRegStatePtr *states;
258
259	int maxCounters;
260	int nbCounters;
261	xmlRegCounter *counters;
262
263	int determinist;
264	int negs;
265	int flags;
266	};
267
268	struct _xmlRegexp {
269	xmlChar *string;
270	int nbStates;
271	xmlRegStatePtr *states;
272	int nbAtoms;
273	xmlRegAtomPtr *atoms;
274	int nbCounters;
275	xmlRegCounter *counters;
276	int determinist;
277	int flags;
278	/*
279	* That's the compact form for determinists automatas
280	*/
281	int nbstates;
282	int *compact;
283	void **transdata;
284	int nbstrings;
285	xmlChar **stringMap;
286	};
287
288	typedef struct _xmlRegExecRollback xmlRegExecRollback;
289	typedef xmlRegExecRollback *xmlRegExecRollbackPtr;
290
291	struct _xmlRegExecRollback {
292	xmlRegStatePtr state;/* the current state */
293	int index; /* the index in the input stack */
294	int nextbranch; /* the next transition to explore in that state */
295	int counts; / save the automata state if it has some */
296	};
297
298	typedef struct _xmlRegInputToken xmlRegInputToken;
299	typedef xmlRegInputToken *xmlRegInputTokenPtr;
300
301	struct _xmlRegInputToken {
302	xmlChar *value;
303	void *data;
304	};
305
306	struct _xmlRegExecCtxt {
307	int status; /* execution status != 0 indicate an error */
308	int determinist; /* did we find an indeterministic behaviour */
309	xmlRegexpPtr comp; /* the compiled regexp */
310	xmlRegExecCallbacks callback;
311	void *data;
312
313	xmlRegStatePtr state;/* the current state */
314	int transno; /* the current transition on that state */
315	int transcount; /* the number of chars in char counted transitions */
316
317	/*
318	* A stack of rollback states
319	*/
320	int maxRollbacks;
321	int nbRollbacks;
322	xmlRegExecRollback *rollbacks;
323
324	/*
325	* The state of the automata if any
326	*/
327	int *counts;
328
329	/*
330	* The input stack
331	*/
332	int inputStackMax;
333	int inputStackNr;
334	int index;
335	int *charStack;
336	const xmlChar inputString; / when operating on characters */
337	xmlRegInputTokenPtr inputStack;/* when operating on strings */
338
339	/*
340	* error handling
341	*/
342	int errStateNo; /* the error state number */
343	xmlRegStatePtr errState; /* the error state */
344	xmlChar errString; / the string raising the error */
345	int errCounts; / counters at the error state */
346	int nbPush;
347	};
348
349	#define REGEXP_ALL_COUNTER0x123456 0x123456
350	#define REGEXP_ALL_LAX_COUNTER0x123457 0x123457
351
352	static void xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top);
353	static void xmlRegFreeState(xmlRegStatePtr state);
354	static void xmlRegFreeAtom(xmlRegAtomPtr atom);
355	static int xmlRegStrEqualWildcard(const xmlChar expStr, const xmlChar valStr);
356	static int xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint);
357	static int xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint,
358	int neg, int start, int end, const xmlChar *blockName);
359
360	void xmlAutomataSetFlags(xmlAutomataPtr am, int flags);
361
362	/************************************************************************
363	* *
364	* Regexp memory error handler *
365	* *
366	************************************************************************/
367	/**
368	* xmlRegexpErrMemory:
369	* @extra: extra information
370	*
371	* Handle an out of memory condition
372	*/
373	static void
374	xmlRegexpErrMemory(xmlRegParserCtxtPtr ctxt, const char *extra)
375	{
376	const char regexp = NULL((void)0);
377	if (ctxt != NULL((void*)0)) {
378	regexp = (const char *) ctxt->string;
379	ctxt->error = XML_ERR_NO_MEMORY;
380	}
381	__xmlRaiseError(NULL((void)0), NULL((void)0), NULL((void)0), NULL((void)0), NULL((void*)0), XML_FROM_REGEXP,
382	XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL((void*)0), 0, extra,
383	regexp, NULL((void*)0), 0, 0,
384	"Memory allocation failed : %s\n", extra);
385	}
386
387	/**
388	* xmlRegexpErrCompile:
389	* @extra: extra information
390	*
391	* Handle a compilation failure
392	*/
393	static void
394	xmlRegexpErrCompile(xmlRegParserCtxtPtr ctxt, const char *extra)
395	{
396	const char regexp = NULL((void)0);
397	int idx = 0;
398
399	if (ctxt != NULL((void*)0)) {
400	regexp = (const char *) ctxt->string;
401	idx = ctxt->cur - ctxt->string;
402	ctxt->error = XML_REGEXP_COMPILE_ERROR;
403	}
404	__xmlRaiseError(NULL((void)0), NULL((void)0), NULL((void)0), NULL((void)0), NULL((void*)0), XML_FROM_REGEXP,
405	XML_REGEXP_COMPILE_ERROR, XML_ERR_FATAL, NULL((void*)0), 0, extra,
406	regexp, NULL((void*)0), idx, 0,
407	"failed to compile: %s\n", extra);
408	}
409
410	/************************************************************************
411	* *
412	* Allocation/Deallocation *
413	* *
414	************************************************************************/
415
416	static int xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt);
417	/**
418	* xmlRegEpxFromParse:
419	* @ctxt: the parser context used to build it
420	*
421	* Allocate a new regexp and fill it with the result from the parser
422	*
423	* Returns the new regexp or NULL in case of error
424	*/
425	static xmlRegexpPtr
426	xmlRegEpxFromParse(xmlRegParserCtxtPtr ctxt) {
427	xmlRegexpPtr ret;
428
429	ret = (xmlRegexpPtr) xmlMalloc(sizeof(xmlRegexp));
430	if (ret == NULL((void*)0)) {
431	xmlRegexpErrMemory(ctxt, "compiling regexp");
432	return(NULL((void*)0));
433	}
434	memset(ret, 0, sizeof(xmlRegexp));
435	ret->string = ctxt->string;
436	ret->nbStates = ctxt->nbStates;
437	ret->states = ctxt->states;
438	ret->nbAtoms = ctxt->nbAtoms;
439	ret->atoms = ctxt->atoms;
440	ret->nbCounters = ctxt->nbCounters;
441	ret->counters = ctxt->counters;
442	ret->determinist = ctxt->determinist;
443	ret->flags = ctxt->flags;
444	if (ret->determinist == -1) {
445	xmlRegexpIsDeterminist(ret);
446	}
447
448	if ((ret->determinist != 0) &&
449	(ret->nbCounters == 0) &&
450	(ctxt->negs == 0) &&
451	(ret->atoms != NULL((void*)0)) &&
452	(ret->atoms[0] != NULL((void*)0)) &&
453	(ret->atoms[0]->type == XML_REGEXP_STRING)) {
454	int i, j, nbstates = 0, nbatoms = 0;
455	int *stateRemap;
456	int *stringRemap;
457	int *transitions;
458	void **transdata;
459	xmlChar **stringMap;
460	xmlChar *value;
461
462	/*
463	* Switch to a compact representation
464	* 1/ counting the effective number of states left
465	* 2/ counting the unique number of atoms, and check that
466	* they are all of the string type
467	* 3/ build a table state x atom for the transitions
468	*/
469
470	stateRemap = xmlMalloc(ret->nbStates * sizeof(int));
471	if (stateRemap == NULL((void*)0)) {
472	xmlRegexpErrMemory(ctxt, "compiling regexp");
473	xmlFree(ret);
474	return(NULL((void*)0));
475	}
476	for (i = 0;i < ret->nbStates;i++) {
477	if (ret->states[i] != NULL((void*)0)) {
478	stateRemap[i] = nbstates;
479	nbstates++;
480	} else {
481	stateRemap[i] = -1;
482	}
483	}
484	#ifdef DEBUG_COMPACTION
485	printf("Final: %d states\n", nbstates);
486	#endif
487	stringMap = xmlMalloc(ret->nbAtoms * sizeof(char *));
488	if (stringMap == NULL((void*)0)) {
489	xmlRegexpErrMemory(ctxt, "compiling regexp");
490	xmlFree(stateRemap);
491	xmlFree(ret);
492	return(NULL((void*)0));
493	}
494	stringRemap = xmlMalloc(ret->nbAtoms * sizeof(int));
495	if (stringRemap == NULL((void*)0)) {
496	xmlRegexpErrMemory(ctxt, "compiling regexp");
497	xmlFree(stringMap);
498	xmlFree(stateRemap);
499	xmlFree(ret);
500	return(NULL((void*)0));
501	}
502	for (i = 0;i < ret->nbAtoms;i++) {
503	if ((ret->atoms[i]->type == XML_REGEXP_STRING) &&
504	(ret->atoms[i]->quant == XML_REGEXP_QUANT_ONCE)) {
505	value = ret->atoms[i]->valuep;
506	for (j = 0;j < nbatoms;j++) {
507	if (xmlStrEqual(stringMap[j], value)) {
508	stringRemap[i] = j;
509	break;
510	}
511	}
512	if (j >= nbatoms) {
513	stringRemap[i] = nbatoms;
514	stringMap[nbatoms] = xmlStrdup(value);
515	if (stringMap[nbatoms] == NULL((void*)0)) {
516	for (i = 0;i < nbatoms;i++)
517	xmlFree(stringMap[i]);
518	xmlFree(stringRemap);
519	xmlFree(stringMap);
520	xmlFree(stateRemap);
521	xmlFree(ret);
522	return(NULL((void*)0));
523	}
524	nbatoms++;
525	}
526	} else {
527	xmlFree(stateRemap);
528	xmlFree(stringRemap);
529	for (i = 0;i < nbatoms;i++)
530	xmlFree(stringMap[i]);
531	xmlFree(stringMap);
532	xmlFree(ret);
533	return(NULL((void*)0));
534	}
535	}
536	#ifdef DEBUG_COMPACTION
537	printf("Final: %d atoms\n", nbatoms);
538	#endif
539	transitions = (int ) xmlMalloc((nbstates + 1)
540	(nbatoms + 1) * sizeof(int));
541	if (transitions == NULL((void*)0)) {
542	xmlFree(stateRemap);
543	xmlFree(stringRemap);
544	xmlFree(stringMap);
545	xmlFree(ret);
546	return(NULL((void*)0));
547	}
548	memset(transitions, 0, (nbstates + 1) * (nbatoms + 1) * sizeof(int));
549
550	/*
551	* Allocate the transition table. The first entry for each
552	* state corresponds to the state type.
553	*/
554	transdata = NULL((void*)0);
555
556	for (i = 0;i < ret->nbStates;i++) {
557	int stateno, atomno, targetno, prev;
558	xmlRegStatePtr state;
559	xmlRegTransPtr trans;
560
561	stateno = stateRemap[i];
562	if (stateno == -1)
563	continue;
564	state = ret->states[i];
565
566	transitions[stateno * (nbatoms + 1)] = state->type;
567
568	for (j = 0;j < state->nbTrans;j++) {
569	trans = &(state->trans[j]);
570	if ((trans->to == -1) \|\| (trans->atom == NULL((void*)0)))
571	continue;
572	atomno = stringRemap[trans->atom->no];
573	if ((trans->atom->data != NULL((void)0)) && (transdata == NULL((void)0))) {
574	transdata = (void *) xmlMalloc(nbstates nbatoms *
575	sizeof(void *));
576	if (transdata != NULL((void*)0))
577	memset(transdata, 0,
578	nbstates * nbatoms * sizeof(void *));
579	else {
580	xmlRegexpErrMemory(ctxt, "compiling regexp");
581	break;
582	}
583	}
584	targetno = stateRemap[trans->to];
585	/*
586	* if the same atom can generate transitions to 2 different
587	* states then it means the automata is not determinist and
588	* the compact form can't be used !
589	*/
590	prev = transitions[stateno * (nbatoms + 1) + atomno + 1];
591	if (prev != 0) {
592	if (prev != targetno + 1) {
593	ret->determinist = 0;
594	#ifdef DEBUG_COMPACTION
595	printf("Indet: state %d trans %d, atom %d to %d : %d to %d\n",
596	i, j, trans->atom->no, trans->to, atomno, targetno);
597	printf(" previous to is %d\n", prev);
598	#endif
599	if (transdata != NULL((void*)0))
600	xmlFree(transdata);
601	xmlFree(transitions);
602	xmlFree(stateRemap);
603	xmlFree(stringRemap);
604	for (i = 0;i < nbatoms;i++)
605	xmlFree(stringMap[i]);
606	xmlFree(stringMap);
607	goto not_determ;
608	}
609	} else {
610	#if 0
611	printf("State %d trans %d: atom %d to %d : %d to %d\n",
612	i, j, trans->atom->no, trans->to, atomno, targetno);
613	#endif
614	transitions[stateno * (nbatoms + 1) + atomno + 1] =
615	targetno + 1; /* to avoid 0 */
616	if (transdata != NULL((void*)0))
617	transdata[stateno * nbatoms + atomno] =
618	trans->atom->data;
619	}
620	}
621	}
622	ret->determinist = 1;
623	#ifdef DEBUG_COMPACTION
624	/*
625	* Debug
626	*/
627	for (i = 0;i < nbstates;i++) {
628	for (j = 0;j < nbatoms + 1;j++) {
629	printf("%02d ", transitions[i * (nbatoms + 1) + j]);
630	}
631	printf("\n");
632	}
633	printf("\n");
634	#endif
635	/*
636	* Cleanup of the old data
637	*/
638	if (ret->states != NULL((void*)0)) {
639	for (i = 0;i < ret->nbStates;i++)
640	xmlRegFreeState(ret->states[i]);
641	xmlFree(ret->states);
642	}
643	ret->states = NULL((void*)0);
644	ret->nbStates = 0;
645	if (ret->atoms != NULL((void*)0)) {
646	for (i = 0;i < ret->nbAtoms;i++)
647	xmlRegFreeAtom(ret->atoms[i]);
648	xmlFree(ret->atoms);
649	}
650	ret->atoms = NULL((void*)0);
651	ret->nbAtoms = 0;
652
653	ret->compact = transitions;
654	ret->transdata = transdata;
655	ret->stringMap = stringMap;
656	ret->nbstrings = nbatoms;
657	ret->nbstates = nbstates;
658	xmlFree(stateRemap);
659	xmlFree(stringRemap);
660	}
661	not_determ:
662	ctxt->string = NULL((void*)0);
663	ctxt->nbStates = 0;
664	ctxt->states = NULL((void*)0);
665	ctxt->nbAtoms = 0;
666	ctxt->atoms = NULL((void*)0);
667	ctxt->nbCounters = 0;
668	ctxt->counters = NULL((void*)0);
669	return(ret);
670	}
671
672	/**
673	* xmlRegNewParserCtxt:
674	* @string: the string to parse
675	*
676	* Allocate a new regexp parser context
677	*
678	* Returns the new context or NULL in case of error
679	*/
680	static xmlRegParserCtxtPtr
681	xmlRegNewParserCtxt(const xmlChar *string) {
682	xmlRegParserCtxtPtr ret;
683
684	ret = (xmlRegParserCtxtPtr) xmlMalloc(sizeof(xmlRegParserCtxt));
685	if (ret == NULL((void*)0))
686	return(NULL((void*)0));
687	memset(ret, 0, sizeof(xmlRegParserCtxt));
688	if (string != NULL((void*)0))
689	ret->string = xmlStrdup(string);
690	ret->cur = ret->string;
691	ret->neg = 0;
692	ret->negs = 0;
693	ret->error = 0;
694	ret->determinist = -1;
695	return(ret);
696	}
697
698	/**
699	* xmlRegNewRange:
700	* @ctxt: the regexp parser context
701	* @neg: is that negative
702	* @type: the type of range
703	* @start: the start codepoint
704	* @end: the end codepoint
705	*
706	* Allocate a new regexp range
707	*
708	* Returns the new range or NULL in case of error
709	*/
710	static xmlRegRangePtr
711	xmlRegNewRange(xmlRegParserCtxtPtr ctxt,
712	int neg, xmlRegAtomType type, int start, int end) {
713	xmlRegRangePtr ret;
714
715	ret = (xmlRegRangePtr) xmlMalloc(sizeof(xmlRegRange));
716	if (ret == NULL((void*)0)) {
717	xmlRegexpErrMemory(ctxt, "allocating range");
718	return(NULL((void*)0));
719	}
720	ret->neg = neg;
721	ret->type = type;
722	ret->start = start;
723	ret->end = end;
724	return(ret);
725	}
726
727	/**
728	* xmlRegFreeRange:
729	* @range: the regexp range
730	*
731	* Free a regexp range
732	*/
733	static void
734	xmlRegFreeRange(xmlRegRangePtr range) {
735	if (range == NULL((void*)0))
736	return;
737
738	if (range->blockName != NULL((void*)0))
739	xmlFree(range->blockName);
740	xmlFree(range);
741	}
742
743	/**
744	* xmlRegCopyRange:
745	* @range: the regexp range
746	*
747	* Copy a regexp range
748	*
749	* Returns the new copy or NULL in case of error.
750	*/
751	static xmlRegRangePtr
752	xmlRegCopyRange(xmlRegParserCtxtPtr ctxt, xmlRegRangePtr range) {
753	xmlRegRangePtr ret;
754
755	if (range == NULL((void*)0))
756	return(NULL((void*)0));
757
758	ret = xmlRegNewRange(ctxt, range->neg, range->type, range->start,
759	range->end);
760	if (ret == NULL((void*)0))
761	return(NULL((void*)0));
762	if (range->blockName != NULL((void*)0)) {
763	ret->blockName = xmlStrdup(range->blockName);
764	if (ret->blockName == NULL((void*)0)) {
765	xmlRegexpErrMemory(ctxt, "allocating range");
766	xmlRegFreeRange(ret);
767	return(NULL((void*)0));
768	}
769	}
770	return(ret);
771	}
772
773	/**
774	* xmlRegNewAtom:
775	* @ctxt: the regexp parser context
776	* @type: the type of atom
777	*
778	* Allocate a new atom
779	*
780	* Returns the new atom or NULL in case of error
781	*/
782	static xmlRegAtomPtr
783	xmlRegNewAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomType type) {
784	xmlRegAtomPtr ret;
785
786	ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));
787	if (ret == NULL((void*)0)) {
788	xmlRegexpErrMemory(ctxt, "allocating atom");
789	return(NULL((void*)0));
790	}
791	memset(ret, 0, sizeof(xmlRegAtom));
792	ret->type = type;
793	ret->quant = XML_REGEXP_QUANT_ONCE;
794	ret->min = 0;
795	ret->max = 0;
796	return(ret);
797	}
798
799	/**
800	* xmlRegFreeAtom:
801	* @atom: the regexp atom
802	*
803	* Free a regexp atom
804	*/
805	static void
806	xmlRegFreeAtom(xmlRegAtomPtr atom) {
807	int i;
808
809	if (atom == NULL((void*)0))
810	return;
811
812	for (i = 0;i < atom->nbRanges;i++)
813	xmlRegFreeRange(atom->ranges[i]);
814	if (atom->ranges != NULL((void*)0))
815	xmlFree(atom->ranges);
816	if ((atom->type == XML_REGEXP_STRING) && (atom->valuep != NULL((void*)0)))
817	xmlFree(atom->valuep);
818	if ((atom->type == XML_REGEXP_STRING) && (atom->valuep2 != NULL((void*)0)))
819	xmlFree(atom->valuep2);
820	if ((atom->type == XML_REGEXP_BLOCK_NAME) && (atom->valuep != NULL((void*)0)))
821	xmlFree(atom->valuep);
822	xmlFree(atom);
823	}
824
825	/**
826	* xmlRegCopyAtom:
827	* @ctxt: the regexp parser context
828	* @atom: the oiginal atom
829	*
830	* Allocate a new regexp range
831	*
832	* Returns the new atom or NULL in case of error
833	*/
834	static xmlRegAtomPtr
835	xmlRegCopyAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {
836	xmlRegAtomPtr ret;
837
838	ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom));
839	if (ret == NULL((void*)0)) {
840	xmlRegexpErrMemory(ctxt, "copying atom");
841	return(NULL((void*)0));
842	}
843	memset(ret, 0, sizeof(xmlRegAtom));
844	ret->type = atom->type;
845	ret->quant = atom->quant;
846	ret->min = atom->min;
847	ret->max = atom->max;
848	if (atom->nbRanges > 0) {
849	int i;
850
851	ret->ranges = (xmlRegRangePtr ) xmlMalloc(sizeof(xmlRegRangePtr)
852	atom->nbRanges);
853	if (ret->ranges == NULL((void*)0)) {
854	xmlRegexpErrMemory(ctxt, "copying atom");
855	goto error;
856	}
857	for (i = 0;i < atom->nbRanges;i++) {
858	ret->ranges[i] = xmlRegCopyRange(ctxt, atom->ranges[i]);
859	if (ret->ranges[i] == NULL((void*)0))
860	goto error;
861	ret->nbRanges = i + 1;
862	}
863	}
864	return(ret);
865
866	error:
867	xmlRegFreeAtom(ret);
868	return(NULL((void*)0));
869	}
870
871	static xmlRegStatePtr
872	xmlRegNewState(xmlRegParserCtxtPtr ctxt) {
873	xmlRegStatePtr ret;
874
875	ret = (xmlRegStatePtr) xmlMalloc(sizeof(xmlRegState));
876	if (ret == NULL((void*)0)) {
877	xmlRegexpErrMemory(ctxt, "allocating state");
878	return(NULL((void*)0));
879	}
880	memset(ret, 0, sizeof(xmlRegState));
881	ret->type = XML_REGEXP_TRANS_STATE;
882	ret->mark = XML_REGEXP_MARK_NORMAL;
883	return(ret);
884	}
885
886	/**
887	* xmlRegFreeState:
888	* @state: the regexp state
889	*
890	* Free a regexp state
891	*/
892	static void
893	xmlRegFreeState(xmlRegStatePtr state) {
894	if (state == NULL((void*)0))
895	return;
896
897	if (state->trans != NULL((void*)0))
898	xmlFree(state->trans);
899	if (state->transTo != NULL((void*)0))
900	xmlFree(state->transTo);
901	xmlFree(state);
902	}
903
904	/**
905	* xmlRegFreeParserCtxt:
906	* @ctxt: the regexp parser context
907	*
908	* Free a regexp parser context
909	*/
910	static void
911	xmlRegFreeParserCtxt(xmlRegParserCtxtPtr ctxt) {
912	int i;
913	if (ctxt == NULL((void*)0))
914	return;
915
916	if (ctxt->string != NULL((void*)0))
917	xmlFree(ctxt->string);
918	if (ctxt->states != NULL((void*)0)) {
919	for (i = 0;i < ctxt->nbStates;i++)
920	xmlRegFreeState(ctxt->states[i]);
921	xmlFree(ctxt->states);
922	}
923	if (ctxt->atoms != NULL((void*)0)) {
924	for (i = 0;i < ctxt->nbAtoms;i++)
925	xmlRegFreeAtom(ctxt->atoms[i]);
926	xmlFree(ctxt->atoms);
927	}
928	if (ctxt->counters != NULL((void*)0))
929	xmlFree(ctxt->counters);
930	xmlFree(ctxt);
931	}
932
933	/************************************************************************
934	* *
935	* Display of Data structures *
936	* *
937	************************************************************************/
938
939	static void
940	xmlRegPrintAtomType(FILE *output, xmlRegAtomType type) {
941	switch (type) {
942	case XML_REGEXP_EPSILON:
943	fprintf(output, "epsilon "); break;
944	case XML_REGEXP_CHARVAL:
945	fprintf(output, "charval "); break;
946	case XML_REGEXP_RANGES:
947	fprintf(output, "ranges "); break;
948	case XML_REGEXP_SUBREG:
949	fprintf(output, "subexpr "); break;
950	case XML_REGEXP_STRING:
951	fprintf(output, "string "); break;
952	case XML_REGEXP_ANYCHAR:
953	fprintf(output, "anychar "); break;
954	case XML_REGEXP_ANYSPACE:
955	fprintf(output, "anyspace "); break;
956	case XML_REGEXP_NOTSPACE:
957	fprintf(output, "notspace "); break;
958	case XML_REGEXP_INITNAME:
959	fprintf(output, "initname "); break;
960	case XML_REGEXP_NOTINITNAME:
961	fprintf(output, "notinitname "); break;
962	case XML_REGEXP_NAMECHAR:
963	fprintf(output, "namechar "); break;
964	case XML_REGEXP_NOTNAMECHAR:
965	fprintf(output, "notnamechar "); break;
966	case XML_REGEXP_DECIMAL:
967	fprintf(output, "decimal "); break;
968	case XML_REGEXP_NOTDECIMAL:
969	fprintf(output, "notdecimal "); break;
970	case XML_REGEXP_REALCHAR:
971	fprintf(output, "realchar "); break;
972	case XML_REGEXP_NOTREALCHAR:
973	fprintf(output, "notrealchar "); break;
974	case XML_REGEXP_LETTER:
975	fprintf(output, "LETTER "); break;
976	case XML_REGEXP_LETTER_UPPERCASE:
977	fprintf(output, "LETTER_UPPERCASE "); break;
978	case XML_REGEXP_LETTER_LOWERCASE:
979	fprintf(output, "LETTER_LOWERCASE "); break;
980	case XML_REGEXP_LETTER_TITLECASE:
981	fprintf(output, "LETTER_TITLECASE "); break;
982	case XML_REGEXP_LETTER_MODIFIER:
983	fprintf(output, "LETTER_MODIFIER "); break;
984	case XML_REGEXP_LETTER_OTHERS:
985	fprintf(output, "LETTER_OTHERS "); break;
986	case XML_REGEXP_MARK:
987	fprintf(output, "MARK "); break;
988	case XML_REGEXP_MARK_NONSPACING:
989	fprintf(output, "MARK_NONSPACING "); break;
990	case XML_REGEXP_MARK_SPACECOMBINING:
991	fprintf(output, "MARK_SPACECOMBINING "); break;
992	case XML_REGEXP_MARK_ENCLOSING:
993	fprintf(output, "MARK_ENCLOSING "); break;
994	case XML_REGEXP_NUMBER:
995	fprintf(output, "NUMBER "); break;
996	case XML_REGEXP_NUMBER_DECIMAL:
997	fprintf(output, "NUMBER_DECIMAL "); break;
998	case XML_REGEXP_NUMBER_LETTER:
999	fprintf(output, "NUMBER_LETTER "); break;
1000	case XML_REGEXP_NUMBER_OTHERS:
1001	fprintf(output, "NUMBER_OTHERS "); break;
1002	case XML_REGEXP_PUNCT:
1003	fprintf(output, "PUNCT "); break;
1004	case XML_REGEXP_PUNCT_CONNECTOR:
1005	fprintf(output, "PUNCT_CONNECTOR "); break;
1006	case XML_REGEXP_PUNCT_DASH:
1007	fprintf(output, "PUNCT_DASH "); break;
1008	case XML_REGEXP_PUNCT_OPEN:
1009	fprintf(output, "PUNCT_OPEN "); break;
1010	case XML_REGEXP_PUNCT_CLOSE:
1011	fprintf(output, "PUNCT_CLOSE "); break;
1012	case XML_REGEXP_PUNCT_INITQUOTE:
1013	fprintf(output, "PUNCT_INITQUOTE "); break;
1014	case XML_REGEXP_PUNCT_FINQUOTE:
1015	fprintf(output, "PUNCT_FINQUOTE "); break;
1016	case XML_REGEXP_PUNCT_OTHERS:
1017	fprintf(output, "PUNCT_OTHERS "); break;
1018	case XML_REGEXP_SEPAR:
1019	fprintf(output, "SEPAR "); break;
1020	case XML_REGEXP_SEPAR_SPACE:
1021	fprintf(output, "SEPAR_SPACE "); break;
1022	case XML_REGEXP_SEPAR_LINE:
1023	fprintf(output, "SEPAR_LINE "); break;
1024	case XML_REGEXP_SEPAR_PARA:
1025	fprintf(output, "SEPAR_PARA "); break;
1026	case XML_REGEXP_SYMBOL:
1027	fprintf(output, "SYMBOL "); break;
1028	case XML_REGEXP_SYMBOL_MATH:
1029	fprintf(output, "SYMBOL_MATH "); break;
1030	case XML_REGEXP_SYMBOL_CURRENCY:
1031	fprintf(output, "SYMBOL_CURRENCY "); break;
1032	case XML_REGEXP_SYMBOL_MODIFIER:
1033	fprintf(output, "SYMBOL_MODIFIER "); break;
1034	case XML_REGEXP_SYMBOL_OTHERS:
1035	fprintf(output, "SYMBOL_OTHERS "); break;
1036	case XML_REGEXP_OTHER:
1037	fprintf(output, "OTHER "); break;
1038	case XML_REGEXP_OTHER_CONTROL:
1039	fprintf(output, "OTHER_CONTROL "); break;
1040	case XML_REGEXP_OTHER_FORMAT:
1041	fprintf(output, "OTHER_FORMAT "); break;
1042	case XML_REGEXP_OTHER_PRIVATE:
1043	fprintf(output, "OTHER_PRIVATE "); break;
1044	case XML_REGEXP_OTHER_NA:
1045	fprintf(output, "OTHER_NA "); break;
1046	case XML_REGEXP_BLOCK_NAME:
1047	fprintf(output, "BLOCK "); break;
1048	}
1049	}
1050
1051	static void
1052	xmlRegPrintQuantType(FILE *output, xmlRegQuantType type) {
1053	switch (type) {
1054	case XML_REGEXP_QUANT_EPSILON:
1055	fprintf(output, "epsilon "); break;
1056	case XML_REGEXP_QUANT_ONCE:
1057	fprintf(output, "once "); break;
1058	case XML_REGEXP_QUANT_OPT:
1059	fprintf(output, "? "); break;
1060	case XML_REGEXP_QUANT_MULT:
1061	fprintf(output, "* "); break;
1062	case XML_REGEXP_QUANT_PLUS:
1063	fprintf(output, "+ "); break;
1064	case XML_REGEXP_QUANT_RANGE:
1065	fprintf(output, "range "); break;
1066	case XML_REGEXP_QUANT_ONCEONLY:
1067	fprintf(output, "onceonly "); break;
1068	case XML_REGEXP_QUANT_ALL:
1069	fprintf(output, "all "); break;
1070	}
1071	}
1072	static void
1073	xmlRegPrintRange(FILE *output, xmlRegRangePtr range) {
1074	fprintf(output, " range: ");
1075	if (range->neg)
1076	fprintf(output, "negative ");
1077	xmlRegPrintAtomType(output, range->type);
1078	fprintf(output, "%c - %c\n", range->start, range->end);
1079	}
1080
1081	static void
1082	xmlRegPrintAtom(FILE *output, xmlRegAtomPtr atom) {
1083	fprintf(output, " atom: ");
1084	if (atom == NULL((void*)0)) {
1085	fprintf(output, "NULL\n");
1086	return;
1087	}
1088	if (atom->neg)
1089	fprintf(output, "not ");
1090	xmlRegPrintAtomType(output, atom->type);
1091	xmlRegPrintQuantType(output, atom->quant);
1092	if (atom->quant == XML_REGEXP_QUANT_RANGE)
1093	fprintf(output, "%d-%d ", atom->min, atom->max);
1094	if (atom->type == XML_REGEXP_STRING)
1095	fprintf(output, "'%s' ", (char *) atom->valuep);
1096	if (atom->type == XML_REGEXP_CHARVAL)
1097	fprintf(output, "char %c\n", atom->codepoint);
1098	else if (atom->type == XML_REGEXP_RANGES) {
1099	int i;
1100	fprintf(output, "%d entries\n", atom->nbRanges);
1101	for (i = 0; i < atom->nbRanges;i++)
1102	xmlRegPrintRange(output, atom->ranges[i]);
1103	} else if (atom->type == XML_REGEXP_SUBREG) {
1104	fprintf(output, "start %d end %d\n", atom->start->no, atom->stop->no);
1105	} else {
1106	fprintf(output, "\n");
1107	}
1108	}
1109
1110	static void
1111	xmlRegPrintTrans(FILE *output, xmlRegTransPtr trans) {
1112	fprintf(output, " trans: ");
1113	if (trans == NULL((void*)0)) {
1114	fprintf(output, "NULL\n");
1115	return;
1116	}
1117	if (trans->to < 0) {
1118	fprintf(output, "removed\n");
1119	return;
1120	}
1121	if (trans->nd != 0) {
1122	if (trans->nd == 2)
1123	fprintf(output, "last not determinist, ");
1124	else
1125	fprintf(output, "not determinist, ");
1126	}
1127	if (trans->counter >= 0) {
1128	fprintf(output, "counted %d, ", trans->counter);
1129	}
1130	if (trans->count == REGEXP_ALL_COUNTER0x123456) {
1131	fprintf(output, "all transition, ");
1132	} else if (trans->count >= 0) {
1133	fprintf(output, "count based %d, ", trans->count);
1134	}
1135	if (trans->atom == NULL((void*)0)) {
1136	fprintf(output, "epsilon to %d\n", trans->to);
1137	return;
1138	}
1139	if (trans->atom->type == XML_REGEXP_CHARVAL)
1140	fprintf(output, "char %c ", trans->atom->codepoint);
1141	fprintf(output, "atom %d, to %d\n", trans->atom->no, trans->to);
1142	}
1143
1144	static void
1145	xmlRegPrintState(FILE *output, xmlRegStatePtr state) {
1146	int i;
1147
1148	fprintf(output, " state: ");
1149	if (state == NULL((void*)0)) {
1150	fprintf(output, "NULL\n");
1151	return;
1152	}
1153	if (state->type == XML_REGEXP_START_STATE)
1154	fprintf(output, "START ");
1155	if (state->type == XML_REGEXP_FINAL_STATE)
1156	fprintf(output, "FINAL ");
1157
1158	fprintf(output, "%d, %d transitions:\n", state->no, state->nbTrans);
1159	for (i = 0;i < state->nbTrans; i++) {
1160	xmlRegPrintTrans(output, &(state->trans[i]));
1161	}
1162	}
1163
1164	#ifdef DEBUG_REGEXP_GRAPH
1165	static void
1166	xmlRegPrintCtxt(FILE *output, xmlRegParserCtxtPtr ctxt) {
1167	int i;
1168
1169	fprintf(output, " ctxt: ");
1170	if (ctxt == NULL((void*)0)) {
1171	fprintf(output, "NULL\n");
1172	return;
1173	}
1174	fprintf(output, "'%s' ", ctxt->string);
1175	if (ctxt->error)
1176	fprintf(output, "error ");
1177	if (ctxt->neg)
1178	fprintf(output, "neg ");
1179	fprintf(output, "\n");
1180	fprintf(output, "%d atoms:\n", ctxt->nbAtoms);
1181	for (i = 0;i < ctxt->nbAtoms; i++) {
1182	fprintf(output, " %02d ", i);
1183	xmlRegPrintAtom(output, ctxt->atoms[i]);
1184	}
1185	if (ctxt->atom != NULL((void*)0)) {
1186	fprintf(output, "current atom:\n");
1187	xmlRegPrintAtom(output, ctxt->atom);
1188	}
1189	fprintf(output, "%d states:", ctxt->nbStates);
1190	if (ctxt->start != NULL((void*)0))
1191	fprintf(output, " start: %d", ctxt->start->no);
1192	if (ctxt->end != NULL((void*)0))
1193	fprintf(output, " end: %d", ctxt->end->no);
1194	fprintf(output, "\n");
1195	for (i = 0;i < ctxt->nbStates; i++) {
1196	xmlRegPrintState(output, ctxt->states[i]);
1197	}
1198	fprintf(output, "%d counters:\n", ctxt->nbCounters);
1199	for (i = 0;i < ctxt->nbCounters; i++) {
1200	fprintf(output, " %d: min %d max %d\n", i, ctxt->counters[i].min,
1201	ctxt->counters[i].max);
1202	}
1203	}
1204	#endif
1205
1206	/************************************************************************
1207	* *
1208	* Finite Automata structures manipulations *
1209	* *
1210	************************************************************************/
1211
1212	static void
1213	xmlRegAtomAddRange(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom,
1214	int neg, xmlRegAtomType type, int start, int end,
1215	xmlChar *blockName) {
1216	xmlRegRangePtr range;
1217
1218	if (atom == NULL((void*)0)) {
1219	ERROR("add range: atom is NULL")ctxt->error = XML_REGEXP_COMPILE_ERROR; xmlRegexpErrCompile (ctxt, "add range: atom is NULL");;
1220	return;
1221	}
1222	if (atom->type != XML_REGEXP_RANGES) {
1223	ERROR("add range: atom is not ranges")ctxt->error = XML_REGEXP_COMPILE_ERROR; xmlRegexpErrCompile (ctxt, "add range: atom is not ranges");;
1224	return;
1225	}
1226	if (atom->maxRanges == 0) {
1227	atom->maxRanges = 4;
1228	atom->ranges = (xmlRegRangePtr ) xmlMalloc(atom->maxRanges
1229	sizeof(xmlRegRangePtr));
1230	if (atom->ranges == NULL((void*)0)) {
1231	xmlRegexpErrMemory(ctxt, "adding ranges");
1232	atom->maxRanges = 0;
1233	return;
1234	}
1235	} else if (atom->nbRanges >= atom->maxRanges) {
1236	xmlRegRangePtr *tmp;
1237	atom->maxRanges *= 2;
1238	tmp = (xmlRegRangePtr ) xmlRealloc(atom->ranges, atom->maxRanges
1239	sizeof(xmlRegRangePtr));
1240	if (tmp == NULL((void*)0)) {
1241	xmlRegexpErrMemory(ctxt, "adding ranges");
1242	atom->maxRanges /= 2;
1243	return;
1244	}
1245	atom->ranges = tmp;
1246	}
1247	range = xmlRegNewRange(ctxt, neg, type, start, end);
1248	if (range == NULL((void*)0))
1249	return;
1250	range->blockName = blockName;
1251	atom->ranges[atom->nbRanges++] = range;
1252
1253	}
1254
1255	static int
1256	xmlRegGetCounter(xmlRegParserCtxtPtr ctxt) {
1257	if (ctxt->maxCounters == 0) {
1258	ctxt->maxCounters = 4;
1259	ctxt->counters = (xmlRegCounter ) xmlMalloc(ctxt->maxCounters
1260	sizeof(xmlRegCounter));
1261	if (ctxt->counters == NULL((void*)0)) {
1262	xmlRegexpErrMemory(ctxt, "allocating counter");
1263	ctxt->maxCounters = 0;
1264	return(-1);
1265	}
1266	} else if (ctxt->nbCounters >= ctxt->maxCounters) {
1267	xmlRegCounter *tmp;
1268	ctxt->maxCounters *= 2;
1269	tmp = (xmlRegCounter ) xmlRealloc(ctxt->counters, ctxt->maxCounters
1270	sizeof(xmlRegCounter));
1271	if (tmp == NULL((void*)0)) {
1272	xmlRegexpErrMemory(ctxt, "allocating counter");
1273	ctxt->maxCounters /= 2;
1274	return(-1);
1275	}
1276	ctxt->counters = tmp;
1277	}
1278	ctxt->counters[ctxt->nbCounters].min = -1;
1279	ctxt->counters[ctxt->nbCounters].max = -1;
1280	return(ctxt->nbCounters++);
1281	}
1282
1283	static int
1284	xmlRegAtomPush(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) {
1285	if (atom == NULL((void*)0)) {
1286	ERROR("atom push: atom is NULL")ctxt->error = XML_REGEXP_COMPILE_ERROR; xmlRegexpErrCompile (ctxt, "atom push: atom is NULL");;
1287	return(-1);
1288	}
1289	if (ctxt->maxAtoms == 0) {
1290	ctxt->maxAtoms = 4;
1291	ctxt->atoms = (xmlRegAtomPtr ) xmlMalloc(ctxt->maxAtoms
1292	sizeof(xmlRegAtomPtr));
1293	if (ctxt->atoms == NULL((void*)0)) {
1294	xmlRegexpErrMemory(ctxt, "pushing atom");
1295	ctxt->maxAtoms = 0;
1296	return(-1);
1297	}
1298	} else if (ctxt->nbAtoms >= ctxt->maxAtoms) {
1299	xmlRegAtomPtr *tmp;
1300	ctxt->maxAtoms *= 2;
1301	tmp = (xmlRegAtomPtr ) xmlRealloc(ctxt->atoms, ctxt->maxAtoms
1302	sizeof(xmlRegAtomPtr));
1303	if (tmp == NULL((void*)0)) {
1304	xmlRegexpErrMemory(ctxt, "allocating counter");
1305	ctxt->maxAtoms /= 2;
1306	return(-1);
1307	}
1308	ctxt->atoms = tmp;
1309	}
1310	atom->no = ctxt->nbAtoms;
1311	ctxt->atoms[ctxt->nbAtoms++] = atom;
1312	return(0);
1313	}
1314
1315	static void
1316	xmlRegStateAddTransTo(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr target,
1317	int from) {
1318	if (target->maxTransTo == 0) {
1319	target->maxTransTo = 8;
1320	target->transTo = (int ) xmlMalloc(target->maxTransTo
1321	sizeof(int));
1322	if (target->transTo == NULL((void*)0)) {
1323	xmlRegexpErrMemory(ctxt, "adding transition");
1324	target->maxTransTo = 0;
1325	return;
1326	}
1327	} else if (target->nbTransTo >= target->maxTransTo) {
1328	int *tmp;
1329	target->maxTransTo *= 2;
1330	tmp = (int ) xmlRealloc(target->transTo, target->maxTransTo
1331	sizeof(int));
1332	if (tmp == NULL((void*)0)) {
1333	xmlRegexpErrMemory(ctxt, "adding transition");
1334	target->maxTransTo /= 2;
1335	return;
1336	}
1337	target->transTo = tmp;
1338	}
1339	target->transTo[target->nbTransTo] = from;
1340	target->nbTransTo++;
1341	}
1342
1343	static void
1344	xmlRegStateAddTrans(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
1345	xmlRegAtomPtr atom, xmlRegStatePtr target,
1346	int counter, int count) {
1347
1348	int nrtrans;
1349
1350	if (state == NULL((void*)0)) {
1351	ERROR("add state: state is NULL")ctxt->error = XML_REGEXP_COMPILE_ERROR; xmlRegexpErrCompile (ctxt, "add state: state is NULL");;
1352	return;
1353	}
1354	if (target == NULL((void*)0)) {
1355	ERROR("add state: target is NULL")ctxt->error = XML_REGEXP_COMPILE_ERROR; xmlRegexpErrCompile (ctxt, "add state: target is NULL");;
1356	return;
1357	}
1358	/*
1359	* Other routines follow the philosophy 'When in doubt, add a transition'
1360	* so we check here whether such a transition is already present and, if
1361	* so, silently ignore this request.
1362	*/
1363
1364	for (nrtrans = state->nbTrans - 1; nrtrans >= 0; nrtrans--) {
1365	xmlRegTransPtr trans = &(state->trans[nrtrans]);
1366	if ((trans->atom == atom) &&
1367	(trans->to == target->no) &&
1368	(trans->counter == counter) &&
1369	(trans->count == count)) {
1370	#ifdef DEBUG_REGEXP_GRAPH
1371	printf("Ignoring duplicate transition from %d to %d\n",
1372	state->no, target->no);
1373	#endif
1374	return;
1375	}
1376	}
1377
1378	if (state->maxTrans == 0) {
1379	state->maxTrans = 8;
1380	state->trans = (xmlRegTrans ) xmlMalloc(state->maxTrans
1381	sizeof(xmlRegTrans));
1382	if (state->trans == NULL((void*)0)) {
1383	xmlRegexpErrMemory(ctxt, "adding transition");
1384	state->maxTrans = 0;
1385	return;
1386	}
1387	} else if (state->nbTrans >= state->maxTrans) {
1388	xmlRegTrans *tmp;
1389	state->maxTrans *= 2;
1390	tmp = (xmlRegTrans ) xmlRealloc(state->trans, state->maxTrans
1391	sizeof(xmlRegTrans));
1392	if (tmp == NULL((void*)0)) {
1393	xmlRegexpErrMemory(ctxt, "adding transition");
1394	state->maxTrans /= 2;
1395	return;
1396	}
1397	state->trans = tmp;
1398	}
1399	#ifdef DEBUG_REGEXP_GRAPH
1400	printf("Add trans from %d to %d ", state->no, target->no);
1401	if (count == REGEXP_ALL_COUNTER0x123456)
1402	printf("all transition\n");
1403	else if (count >= 0)
1404	printf("count based %d\n", count);
1405	else if (counter >= 0)
1406	printf("counted %d\n", counter);
1407	else if (atom == NULL((void*)0))
1408	printf("epsilon transition\n");
1409	else if (atom != NULL((void*)0))
1410	xmlRegPrintAtom(stdoutstdout, atom);
1411	#endif
1412
1413	state->trans[state->nbTrans].atom = atom;
1414	state->trans[state->nbTrans].to = target->no;
1415	state->trans[state->nbTrans].counter = counter;
1416	state->trans[state->nbTrans].count = count;
1417	state->trans[state->nbTrans].nd = 0;
1418	state->nbTrans++;
1419	xmlRegStateAddTransTo(ctxt, target, state->no);
1420	}
1421
1422	static int
1423	xmlRegStatePush(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) {
1424	if (state == NULL((void*)0)) return(-1);
1425	if (ctxt->maxStates == 0) {
1426	ctxt->maxStates = 4;
1427	ctxt->states = (xmlRegStatePtr ) xmlMalloc(ctxt->maxStates
1428	sizeof(xmlRegStatePtr));
1429	if (ctxt->states == NULL((void*)0)) {
1430	xmlRegexpErrMemory(ctxt, "adding state");
1431	ctxt->maxStates = 0;
1432	return(-1);
1433	}
1434	} else if (ctxt->nbStates >= ctxt->maxStates) {
1435	xmlRegStatePtr *tmp;
1436	ctxt->maxStates *= 2;
1437	tmp = (xmlRegStatePtr ) xmlRealloc(ctxt->states, ctxt->maxStates
1438	sizeof(xmlRegStatePtr));
1439	if (tmp == NULL((void*)0)) {
1440	xmlRegexpErrMemory(ctxt, "adding state");
1441	ctxt->maxStates /= 2;
1442	return(-1);
1443	}
1444	ctxt->states = tmp;
1445	}
1446	state->no = ctxt->nbStates;
1447	ctxt->states[ctxt->nbStates++] = state;
1448	return(0);
1449	}
1450
1451	/**
1452	* xmlFAGenerateAllTransition:
1453	* @ctxt: a regexp parser context
1454	* @from: the from state
1455	* @to: the target state or NULL for building a new one
1456	* @lax:
1457	*
1458	*/
1459	static void
1460	xmlFAGenerateAllTransition(xmlRegParserCtxtPtr ctxt,
1461	xmlRegStatePtr from, xmlRegStatePtr to,
1462	int lax) {
1463	if (to == NULL((void*)0)) {
1464	to = xmlRegNewState(ctxt);
1465	xmlRegStatePush(ctxt, to);
1466	ctxt->state = to;
1467	}
1468	if (lax)
1469	xmlRegStateAddTrans(ctxt, from, NULL((void*)0), to, -1, REGEXP_ALL_LAX_COUNTER0x123457);
1470	else
1471	xmlRegStateAddTrans(ctxt, from, NULL((void*)0), to, -1, REGEXP_ALL_COUNTER0x123456);
1472	}
1473
1474	/**
1475	* xmlFAGenerateEpsilonTransition:
1476	* @ctxt: a regexp parser context
1477	* @from: the from state
1478	* @to: the target state or NULL for building a new one
1479	*
1480	*/
1481	static void
1482	xmlFAGenerateEpsilonTransition(xmlRegParserCtxtPtr ctxt,
1483	xmlRegStatePtr from, xmlRegStatePtr to) {
1484	if (to == NULL((void*)0)) {
1485	to = xmlRegNewState(ctxt);
1486	xmlRegStatePush(ctxt, to);
1487	ctxt->state = to;
1488	}
1489	xmlRegStateAddTrans(ctxt, from, NULL((void*)0), to, -1, -1);
1490	}
1491
1492	/**
1493	* xmlFAGenerateCountedEpsilonTransition:
1494	* @ctxt: a regexp parser context
1495	* @from: the from state
1496	* @to: the target state or NULL for building a new one
1497	* counter: the counter for that transition
1498	*
1499	*/
1500	static void
1501	xmlFAGenerateCountedEpsilonTransition(xmlRegParserCtxtPtr ctxt,
1502	xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
1503	if (to == NULL((void*)0)) {
1504	to = xmlRegNewState(ctxt);
1505	xmlRegStatePush(ctxt, to);
1506	ctxt->state = to;
1507	}
1508	xmlRegStateAddTrans(ctxt, from, NULL((void*)0), to, counter, -1);
1509	}
1510
1511	/**
1512	* xmlFAGenerateCountedTransition:
1513	* @ctxt: a regexp parser context
1514	* @from: the from state
1515	* @to: the target state or NULL for building a new one
1516	* counter: the counter for that transition
1517	*
1518	*/
1519	static void
1520	xmlFAGenerateCountedTransition(xmlRegParserCtxtPtr ctxt,
1521	xmlRegStatePtr from, xmlRegStatePtr to, int counter) {
1522	if (to == NULL((void*)0)) {
1523	to = xmlRegNewState(ctxt);
1524	xmlRegStatePush(ctxt, to);
1525	ctxt->state = to;
1526	}
1527	xmlRegStateAddTrans(ctxt, from, NULL((void*)0), to, -1, counter);
1528	}
1529
1530	/**
1531	* xmlFAGenerateTransitions:
1532	* @ctxt: a regexp parser context
1533	* @from: the from state
1534	* @to: the target state or NULL for building a new one
1535	* @atom: the atom generating the transition
1536	*
1537	* Returns 0 if success and -1 in case of error.
1538	*/
1539	static int
1540	xmlFAGenerateTransitions(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from,
1541	xmlRegStatePtr to, xmlRegAtomPtr atom) {
1542	xmlRegStatePtr end;
1543
1544	if (atom == NULL((void*)0)) {
1545	ERROR("genrate transition: atom == NULL")ctxt->error = XML_REGEXP_COMPILE_ERROR; xmlRegexpErrCompile (ctxt, "genrate transition: atom == NULL");;
1546	return(-1);
1547	}
1548	if (atom->type == XML_REGEXP_SUBREG) {
1549	/*
1550	* this is a subexpression handling one should not need to
1551	* create a new node except for XML_REGEXP_QUANT_RANGE.
1552	*/
1553	if (xmlRegAtomPush(ctxt, atom) < 0) {
1554	return(-1);
1555	}
1556	if ((to != NULL((void*)0)) && (atom->stop != to) &&
1557	(atom->quant != XML_REGEXP_QUANT_RANGE)) {
1558	/*
1559	* Generate an epsilon transition to link to the target
1560	*/
1561	xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);
1562	#ifdef DV
1563	} else if ((to == NULL((void*)0)) && (atom->quant != XML_REGEXP_QUANT_RANGE) &&
1564	(atom->quant != XML_REGEXP_QUANT_ONCE)) {
1565	to = xmlRegNewState(ctxt);
1566	xmlRegStatePush(ctxt, to);
1567	ctxt->state = to;
1568	xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to);
1569	#endif
1570	}
1571	switch (atom->quant) {
1572	case XML_REGEXP_QUANT_OPT:
1573	atom->quant = XML_REGEXP_QUANT_ONCE;
1574	/*
1575	* transition done to the state after end of atom.
1576	* 1. set transition from atom start to new state
1577	* 2. set transition from atom end to this state.
1578	*/
1579	if (to == NULL((void*)0)) {
1580	xmlFAGenerateEpsilonTransition(ctxt, atom->start, 0);
1581	xmlFAGenerateEpsilonTransition(ctxt, atom->stop,
1582	ctxt->state);
1583	} else {
1584	xmlFAGenerateEpsilonTransition(ctxt, atom->start, to);
1585	}
1586	break;
1587	case XML_REGEXP_QUANT_MULT:
1588	atom->quant = XML_REGEXP_QUANT_ONCE;
1589	xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop);
1590	xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1591	break;
1592	case XML_REGEXP_QUANT_PLUS:
1593	atom->quant = XML_REGEXP_QUANT_ONCE;
1594	xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start);
1595	break;
1596	case XML_REGEXP_QUANT_RANGE: {
1597	int counter;
1598	xmlRegStatePtr inter, newstate;
1599
1600	/*
1601	* create the final state now if needed
1602	*/
1603	if (to != NULL((void*)0)) {
1604	newstate = to;
1605	} else {
1606	newstate = xmlRegNewState(ctxt);
1607	xmlRegStatePush(ctxt, newstate);
1608	}
1609
1610	/*
1611	* The principle here is to use counted transition
1612	* to avoid explosion in the number of states in the
1613	* graph. This is clearly more complex but should not
1614	* be exploitable at runtime.
1615	*/
1616	if ((atom->min == 0) && (atom->start0 == NULL((void*)0))) {
1617	xmlRegAtomPtr copy;
1618	/*
1619	* duplicate a transition based on atom to count next
1620	* occurences after 1. We cannot loop to atom->start
1621	* directly because we need an epsilon transition to
1622	* newstate.
1623	*/
1624	/* ???? For some reason it seems we never reach that
1625	case, I suppose this got optimized out before when
1626	building the automata */
1627	copy = xmlRegCopyAtom(ctxt, atom);
1628	if (copy == NULL((void*)0))
1629	return(-1);
1630	copy->quant = XML_REGEXP_QUANT_ONCE;
1631	copy->min = 0;
1632	copy->max = 0;
1633
1634	if (xmlFAGenerateTransitions(ctxt, atom->start, NULL((void*)0), copy)
1635	< 0)
1636	return(-1);
1637	inter = ctxt->state;
1638	counter = xmlRegGetCounter(ctxt);
1639	ctxt->counters[counter].min = atom->min - 1;
1640	ctxt->counters[counter].max = atom->max - 1;
1641	/* count the number of times we see it again */
1642	xmlFAGenerateCountedEpsilonTransition(ctxt, inter,
1643	atom->stop, counter);
1644	/* allow a way out based on the count */
1645	xmlFAGenerateCountedTransition(ctxt, inter,
1646	newstate, counter);
1647	/* and also allow a direct exit for 0 */
1648	xmlFAGenerateEpsilonTransition(ctxt, atom->start,
1649	newstate);
1650	} else {
1651	/*
1652	* either we need the atom at least once or there
1653	* is an atom->start0 allowing to easilly plug the
1654	* epsilon transition.
1655	*/
1656	counter = xmlRegGetCounter(ctxt);
1657	ctxt->counters[counter].min = atom->min - 1;
1658	ctxt->counters[counter].max = atom->max - 1;
1659	/* count the number of times we see it again */
1660	xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop,
1661	atom->start, counter);
1662	/* allow a way out based on the count */
1663	xmlFAGenerateCountedTransition(ctxt, atom->stop,
1664	newstate, counter);
1665	/* and if needed allow a direct exit for 0 */
1666	if (atom->min == 0)
1667	xmlFAGenerateEpsilonTransition(ctxt, atom->start0,
1668	newstate);
1669
1670	}
1671	atom->min = 0;
1672	atom->max = 0;
1673	atom->quant = XML_REGEXP_QUANT_ONCE;
1674	ctxt->state = newstate;
1675	}
1676	default:
1677	break;
1678	}
1679	return(0);
1680	}
1681	if ((atom->min == 0) && (atom->max == 0) &&
1682	(atom->quant == XML_REGEXP_QUANT_RANGE)) {
1683	/*
1684	* we can discard the atom and generate an epsilon transition instead
1685	*/
1686	if (to == NULL((void*)0)) {
1687	to = xmlRegNewState(ctxt);
1688	if (to != NULL((void*)0))
1689	xmlRegStatePush(ctxt, to);
1690	else {
1691	return(-1);
1692	}
1693	}
1694	xmlFAGenerateEpsilonTransition(ctxt, from, to);
1695	ctxt->state = to;
1696	xmlRegFreeAtom(atom);
1697	return(0);
1698	}
1699	if (to == NULL((void*)0)) {
1700	to = xmlRegNewState(ctxt);
1701	if (to != NULL((void*)0))
1702	xmlRegStatePush(ctxt, to);
1703	else {
1704	return(-1);
1705	}
1706	}
1707	end = to;
1708	if ((atom->quant == XML_REGEXP_QUANT_MULT) \|\|
1709	(atom->quant == XML_REGEXP_QUANT_PLUS)) {
1710	/*
1711	* Do not pollute the target state by adding transitions from
1712	* it as it is likely to be the shared target of multiple branches.
1713	* So isolate with an epsilon transition.
1714	*/
1715	xmlRegStatePtr tmp;
1716
1717	tmp = xmlRegNewState(ctxt);
1718	if (tmp != NULL((void*)0))
1719	xmlRegStatePush(ctxt, tmp);
1720	else {
1721	return(-1);
1722	}
1723	xmlFAGenerateEpsilonTransition(ctxt, tmp, to);
1724	to = tmp;
1725	}
1726	if (xmlRegAtomPush(ctxt, atom) < 0) {
1727	return(-1);
1728	}
1729	xmlRegStateAddTrans(ctxt, from, atom, to, -1, -1);
1730	ctxt->state = end;
1731	switch (atom->quant) {
1732	case XML_REGEXP_QUANT_OPT:
1733	atom->quant = XML_REGEXP_QUANT_ONCE;
1734	xmlFAGenerateEpsilonTransition(ctxt, from, to);
1735	break;
1736	case XML_REGEXP_QUANT_MULT:
1737	atom->quant = XML_REGEXP_QUANT_ONCE;
1738	xmlFAGenerateEpsilonTransition(ctxt, from, to);
1739	xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1740	break;
1741	case XML_REGEXP_QUANT_PLUS:
1742	atom->quant = XML_REGEXP_QUANT_ONCE;
1743	xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1744	break;
1745	case XML_REGEXP_QUANT_RANGE:
1746	#if DV_test
1747	if (atom->min == 0) {
1748	xmlFAGenerateEpsilonTransition(ctxt, from, to);
1749	}
1750	#endif
1751	break;
1752	default:
1753	break;
1754	}
1755	return(0);
1756	}
1757
1758	/**
1759	* xmlFAReduceEpsilonTransitions:
1760	* @ctxt: a regexp parser context
1761	* @fromnr: the from state
1762	* @tonr: the to state
1763	* @counter: should that transition be associated to a counted
1764	*
1765	*/
1766	static void
1767	xmlFAReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int fromnr,
1768	int tonr, int counter) {
1769	int transnr;
1770	xmlRegStatePtr from;
1771	xmlRegStatePtr to;
1772
1773	#ifdef DEBUG_REGEXP_GRAPH
1774	printf("xmlFAReduceEpsilonTransitions(%d, %d)\n", fromnr, tonr);
1775	#endif
1776	from = ctxt->states[fromnr];
1777	if (from == NULL((void*)0))
1778	return;
1779	to = ctxt->states[tonr];
1780	if (to == NULL((void*)0))
1781	return;
1782	if ((to->mark == XML_REGEXP_MARK_START) \|\|
1783	(to->mark == XML_REGEXP_MARK_VISITED))
1784	return;
1785
1786	to->mark = XML_REGEXP_MARK_VISITED;
1787	if (to->type == XML_REGEXP_FINAL_STATE) {
1788	#ifdef DEBUG_REGEXP_GRAPH
1789	printf("State %d is final, so %d becomes final\n", tonr, fromnr);
1790	#endif
1791	from->type = XML_REGEXP_FINAL_STATE;
1792	}
1793	for (transnr = 0;transnr < to->nbTrans;transnr++) {
1794	if (to->trans[transnr].to < 0)
1795	continue;
1796	if (to->trans[transnr].atom == NULL((void*)0)) {
1797	/*
1798	* Don't remove counted transitions
1799	* Don't loop either
1800	*/
1801	if (to->trans[transnr].to != fromnr) {
1802	if (to->trans[transnr].count >= 0) {
1803	int newto = to->trans[transnr].to;
1804
1805	xmlRegStateAddTrans(ctxt, from, NULL((void*)0),
1806	ctxt->states[newto],
1807	-1, to->trans[transnr].count);
1808	} else {
1809	#ifdef DEBUG_REGEXP_GRAPH
1810	printf("Found epsilon trans %d from %d to %d\n",
1811	transnr, tonr, to->trans[transnr].to);
1812	#endif
1813	if (to->trans[transnr].counter >= 0) {
1814	xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1815	to->trans[transnr].to,
1816	to->trans[transnr].counter);
1817	} else {
1818	xmlFAReduceEpsilonTransitions(ctxt, fromnr,
1819	to->trans[transnr].to,
1820	counter);
1821	}
1822	}
1823	}
1824	} else {
1825	int newto = to->trans[transnr].to;
1826
1827	if (to->trans[transnr].counter >= 0) {
1828	xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1829	ctxt->states[newto],
1830	to->trans[transnr].counter, -1);
1831	} else {
1832	xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom,
1833	ctxt->states[newto], counter, -1);
1834	}
1835	}
1836	}
1837	to->mark = XML_REGEXP_MARK_NORMAL;
1838	}
1839
1840	/**
1841	* xmlFAEliminateSimpleEpsilonTransitions:
1842	* @ctxt: a regexp parser context
1843	*
1844	* Eliminating general epsilon transitions can get costly in the general
1845	* algorithm due to the large amount of generated new transitions and
1846	* associated comparisons. However for simple epsilon transition used just
1847	* to separate building blocks when generating the automata this can be
1848	* reduced to state elimination:
1849	* - if there exists an epsilon from X to Y
1850	* - if there is no other transition from X
1851	* then X and Y are semantically equivalent and X can be eliminated
1852	* If X is the start state then make Y the start state, else replace the
1853	* target of all transitions to X by transitions to Y.
1854	*/
1855	static void
1856	xmlFAEliminateSimpleEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {
1857	int statenr, i, j, newto;
1858	xmlRegStatePtr state, tmp;
1859
1860	for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1861	state = ctxt->states[statenr];
1862	if (state == NULL((void*)0))
1863	continue;
1864	if (state->nbTrans != 1)
1865	continue;
1866	if (state->type == XML_REGEXP_UNREACH_STATE)
1867	continue;
1868	/* is the only transition out a basic transition */
1869	if ((state->trans[0].atom == NULL((void*)0)) &&
1870	(state->trans[0].to >= 0) &&
1871	(state->trans[0].to != statenr) &&
1872	(state->trans[0].counter < 0) &&
1873	(state->trans[0].count < 0)) {
1874	newto = state->trans[0].to;
1875
1876	if (state->type == XML_REGEXP_START_STATE) {
1877	#ifdef DEBUG_REGEXP_GRAPH
1878	printf("Found simple epsilon trans from start %d to %d\n",
1879	statenr, newto);
1880	#endif
1881	} else {
1882	#ifdef DEBUG_REGEXP_GRAPH
1883	printf("Found simple epsilon trans from %d to %d\n",
1884	statenr, newto);
1885	#endif
1886	for (i = 0;i < state->nbTransTo;i++) {
1887	tmp = ctxt->states[state->transTo[i]];
1888	for (j = 0;j < tmp->nbTrans;j++) {
1889	if (tmp->trans[j].to == statenr) {
1890	#ifdef DEBUG_REGEXP_GRAPH
1891	printf("Changed transition %d on %d to go to %d\n",
1892	j, tmp->no, newto);
1893	#endif
1894	tmp->trans[j].to = -1;
1895	xmlRegStateAddTrans(ctxt, tmp, tmp->trans[j].atom,
1896	ctxt->states[newto],
1897	tmp->trans[j].counter,
1898	tmp->trans[j].count);
1899	}
1900	}
1901	}
1902	if (state->type == XML_REGEXP_FINAL_STATE)
1903	ctxt->states[newto]->type = XML_REGEXP_FINAL_STATE;
1904	/* eliminate the transition completely */
1905	state->nbTrans = 0;
1906
1907	state->type = XML_REGEXP_UNREACH_STATE;
1908
1909	}
1910
1911	}
1912	}
1913	}
1914	/**
1915	* xmlFAEliminateEpsilonTransitions:
1916	* @ctxt: a regexp parser context
1917	*
1918	*/
1919	static void
1920	xmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) {
1921	int statenr, transnr;
1922	xmlRegStatePtr state;
1923	int has_epsilon;
1924
1925	if (ctxt->states == NULL((void*)0)) return;
1926
1927	/*
1928	* Eliminate simple epsilon transition and the associated unreachable
1929	* states.
1930	*/
1931	xmlFAEliminateSimpleEpsilonTransitions(ctxt);
1932	for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1933	state = ctxt->states[statenr];
1934	if ((state != NULL((void*)0)) && (state->type == XML_REGEXP_UNREACH_STATE)) {
1935	#ifdef DEBUG_REGEXP_GRAPH
1936	printf("Removed unreachable state %d\n", statenr);
1937	#endif
1938	xmlRegFreeState(state);
1939	ctxt->states[statenr] = NULL((void*)0);
1940	}
1941	}
1942
1943	has_epsilon = 0;
1944
1945	/*
1946	* Build the completed transitions bypassing the epsilons
1947	* Use a marking algorithm to avoid loops
1948	* Mark sink states too.
1949	* Process from the latests states backward to the start when
1950	* there is long cascading epsilon chains this minimize the
1951	* recursions and transition compares when adding the new ones
1952	*/
1953	for (statenr = ctxt->nbStates - 1;statenr >= 0;statenr--) {
1954	state = ctxt->states[statenr];
1955	if (state == NULL((void*)0))
1956	continue;
1957	if ((state->nbTrans == 0) &&
1958	(state->type != XML_REGEXP_FINAL_STATE)) {
1959	state->type = XML_REGEXP_SINK_STATE;
1960	}
1961	for (transnr = 0;transnr < state->nbTrans;transnr++) {
1962	if ((state->trans[transnr].atom == NULL((void*)0)) &&
1963	(state->trans[transnr].to >= 0)) {
1964	if (state->trans[transnr].to == statenr) {
1965	state->trans[transnr].to = -1;
1966	#ifdef DEBUG_REGEXP_GRAPH
1967	printf("Removed loopback epsilon trans %d on %d\n",
1968	transnr, statenr);
1969	#endif
1970	} else if (state->trans[transnr].count < 0) {
1971	int newto = state->trans[transnr].to;
1972
1973	#ifdef DEBUG_REGEXP_GRAPH
1974	printf("Found epsilon trans %d from %d to %d\n",
1975	transnr, statenr, newto);
1976	#endif
1977	has_epsilon = 1;
1978	state->trans[transnr].to = -2;
1979	state->mark = XML_REGEXP_MARK_START;
1980	xmlFAReduceEpsilonTransitions(ctxt, statenr,
1981	newto, state->trans[transnr].counter);
1982	state->mark = XML_REGEXP_MARK_NORMAL;
1983	#ifdef DEBUG_REGEXP_GRAPH
1984	} else {
1985	printf("Found counted transition %d on %d\n",
1986	transnr, statenr);
1987	#endif
1988	}
1989	}
1990	}
1991	}
1992	/*
1993	* Eliminate the epsilon transitions
1994	*/
1995	if (has_epsilon) {
1996	for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
1997	state = ctxt->states[statenr];
1998	if (state == NULL((void*)0))
1999	continue;
2000	for (transnr = 0;transnr < state->nbTrans;transnr++) {
2001	xmlRegTransPtr trans = &(state->trans[transnr]);
2002	if ((trans->atom == NULL((void*)0)) &&
2003	(trans->count < 0) &&
2004	(trans->to >= 0)) {
2005	trans->to = -1;
2006	}
2007	}
2008	}
2009	}
2010
2011	/*
2012	* Use this pass to detect unreachable states too
2013	*/
2014	for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2015	state = ctxt->states[statenr];
2016	if (state != NULL((void*)0))
2017	state->reached = XML_REGEXP_MARK_NORMAL;
2018	}
2019	state = ctxt->states[0];
2020	if (state != NULL((void*)0))
2021	state->reached = XML_REGEXP_MARK_START;
2022	while (state != NULL((void*)0)) {
2023	xmlRegStatePtr target = NULL((void*)0);
2024	state->reached = XML_REGEXP_MARK_VISITED;
2025	/*
2026	* Mark all states reachable from the current reachable state
2027	*/
2028	for (transnr = 0;transnr < state->nbTrans;transnr++) {
2029	if ((state->trans[transnr].to >= 0) &&
2030	((state->trans[transnr].atom != NULL((void*)0)) \|\|
2031	(state->trans[transnr].count >= 0))) {
2032	int newto = state->trans[transnr].to;
2033
2034	if (ctxt->states[newto] == NULL((void*)0))
2035	continue;
2036	if (ctxt->states[newto]->reached == XML_REGEXP_MARK_NORMAL) {
2037	ctxt->states[newto]->reached = XML_REGEXP_MARK_START;
2038	target = ctxt->states[newto];
2039	}
2040	}
2041	}
2042
2043	/*
2044	* find the next accessible state not explored
2045	*/
2046	if (target == NULL((void*)0)) {
2047	for (statenr = 1;statenr < ctxt->nbStates;statenr++) {
2048	state = ctxt->states[statenr];
2049	if ((state != NULL((void*)0)) && (state->reached ==
2050	XML_REGEXP_MARK_START)) {
2051	target = state;
2052	break;
2053	}
2054	}
2055	}
2056	state = target;
2057	}
2058	for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2059	state = ctxt->states[statenr];
2060	if ((state != NULL((void*)0)) && (state->reached == XML_REGEXP_MARK_NORMAL)) {
2061	#ifdef DEBUG_REGEXP_GRAPH
2062	printf("Removed unreachable state %d\n", statenr);
2063	#endif
2064	xmlRegFreeState(state);
2065	ctxt->states[statenr] = NULL((void*)0);
2066	}
2067	}
2068
2069	}
2070
2071	static int
2072	xmlFACompareRanges(xmlRegRangePtr range1, xmlRegRangePtr range2) {
2073	int ret = 0;
2074
2075	if ((range1->type == XML_REGEXP_RANGES) \|\|
2076	(range2->type == XML_REGEXP_RANGES) \|\|
2077	(range2->type == XML_REGEXP_SUBREG) \|\|
2078	(range1->type == XML_REGEXP_SUBREG) \|\|
2079	(range1->type == XML_REGEXP_STRING) \|\|
2080	(range2->type == XML_REGEXP_STRING))
2081	return(-1);
2082
2083	/* put them in order */
2084	if (range1->type > range2->type) {
2085	xmlRegRangePtr tmp;
2086
2087	tmp = range1;
2088	range1 = range2;
2089	range2 = tmp;
2090	}
2091	if ((range1->type == XML_REGEXP_ANYCHAR) \|\|
2092	(range2->type == XML_REGEXP_ANYCHAR)) {
2093	ret = 1;
2094	} else if ((range1->type == XML_REGEXP_EPSILON) \|\|
2095	(range2->type == XML_REGEXP_EPSILON)) {
2096	return(0);
2097	} else if (range1->type == range2->type) {
2098	if ((range1->type != XML_REGEXP_CHARVAL) \|\|
2099	(range1->end < range2->start) \|\|
2100	(range2->end < range1->start))
2101	ret = 1;
2102	else
2103	ret = 0;
2104	} else if (range1->type == XML_REGEXP_CHARVAL) {
2105	int codepoint;
2106	int neg = 0;
2107
2108	/*
2109	* just check all codepoints in the range for acceptance,
2110	* this is usually way cheaper since done only once at
2111	* compilation than testing over and over at runtime or
2112	* pushing too many states when evaluating.
2113	*/
2114	if (((range1->neg == 0) && (range2->neg != 0)) \|\|
2115	((range1->neg != 0) && (range2->neg == 0)))
2116	neg = 1;
2117
2118	for (codepoint = range1->start;codepoint <= range1->end ;codepoint++) {
2119	ret = xmlRegCheckCharacterRange(range2->type, codepoint,
2120	0, range2->start, range2->end,
2121	range2->blockName);
2122	if (ret < 0)
2123	return(-1);
2124	if (((neg == 1) && (ret == 0)) \|\|
2125	((neg == 0) && (ret == 1)))
2126	return(1);
2127	}
2128	return(0);
2129	} else if ((range1->type == XML_REGEXP_BLOCK_NAME) \|\|
2130	(range2->type == XML_REGEXP_BLOCK_NAME)) {
2131	if (range1->type == range2->type) {
2132	ret = xmlStrEqual(range1->blockName, range2->blockName);
2133	} else {
2134	/*
2135	* comparing a block range with anything else is way
2136	* too costly, and maintining the table is like too much
2137	* memory too, so let's force the automata to save state
2138	* here.
2139	*/
2140	return(1);
2141	}
2142	} else if ((range1->type < XML_REGEXP_LETTER) \|\|
2143	(range2->type < XML_REGEXP_LETTER)) {
2144	if ((range1->type == XML_REGEXP_ANYSPACE) &&
2145	(range2->type == XML_REGEXP_NOTSPACE))
2146	ret = 0;
2147	else if ((range1->type == XML_REGEXP_INITNAME) &&
2148	(range2->type == XML_REGEXP_NOTINITNAME))
2149	ret = 0;
2150	else if ((range1->type == XML_REGEXP_NAMECHAR) &&
2151	(range2->type == XML_REGEXP_NOTNAMECHAR))
2152	ret = 0;
2153	else if ((range1->type == XML_REGEXP_DECIMAL) &&
2154	(range2->type == XML_REGEXP_NOTDECIMAL))
2155	ret = 0;
2156	else if ((range1->type == XML_REGEXP_REALCHAR) &&
2157	(range2->type == XML_REGEXP_NOTREALCHAR))
2158	ret = 0;
2159	else {
2160	/* same thing to limit complexity */
2161	return(1);
2162	}
2163	} else {
2164	ret = 0;
2165	/* range1->type < range2->type here */
2166	switch (range1->type) {
2167	case XML_REGEXP_LETTER:
2168	/* all disjoint except in the subgroups */
2169	if ((range2->type == XML_REGEXP_LETTER_UPPERCASE) \|\|
2170	(range2->type == XML_REGEXP_LETTER_LOWERCASE) \|\|
2171	(range2->type == XML_REGEXP_LETTER_TITLECASE) \|\|
2172	(range2->type == XML_REGEXP_LETTER_MODIFIER) \|\|
2173	(range2->type == XML_REGEXP_LETTER_OTHERS))
2174	ret = 1;
2175	break;
2176	case XML_REGEXP_MARK:
2177	if ((range2->type == XML_REGEXP_MARK_NONSPACING) \|\|
2178	(range2->type == XML_REGEXP_MARK_SPACECOMBINING) \|\|
2179	(range2->type == XML_REGEXP_MARK_ENCLOSING))
2180	ret = 1;
2181	break;
2182	case XML_REGEXP_NUMBER:
2183	if ((range2->type == XML_REGEXP_NUMBER_DECIMAL) \|\|
2184	(range2->type == XML_REGEXP_NUMBER_LETTER) \|\|
2185	(range2->type == XML_REGEXP_NUMBER_OTHERS))
2186	ret = 1;
2187	break;
2188	case XML_REGEXP_PUNCT:
2189	if ((range2->type == XML_REGEXP_PUNCT_CONNECTOR) \|\|
2190	(range2->type == XML_REGEXP_PUNCT_DASH) \|\|
2191	(range2->type == XML_REGEXP_PUNCT_OPEN) \|\|
2192	(range2->type == XML_REGEXP_PUNCT_CLOSE) \|\|
2193	(range2->type == XML_REGEXP_PUNCT_INITQUOTE) \|\|
2194	(range2->type == XML_REGEXP_PUNCT_FINQUOTE) \|\|
2195	(range2->type == XML_REGEXP_PUNCT_OTHERS))
2196	ret = 1;
2197	break;
2198	case XML_REGEXP_SEPAR:
2199	if ((range2->type == XML_REGEXP_SEPAR_SPACE) \|\|
2200	(range2->type == XML_REGEXP_SEPAR_LINE) \|\|
2201	(range2->type == XML_REGEXP_SEPAR_PARA))
2202	ret = 1;
2203	break;
2204	case XML_REGEXP_SYMBOL:
2205	if ((range2->type == XML_REGEXP_SYMBOL_MATH) \|\|
2206	(range2->type == XML_REGEXP_SYMBOL_CURRENCY) \|\|
2207	(range2->type == XML_REGEXP_SYMBOL_MODIFIER) \|\|
2208	(range2->type == XML_REGEXP_SYMBOL_OTHERS))
2209	ret = 1;
2210	break;
2211	case XML_REGEXP_OTHER:
2212	if ((range2->type == XML_REGEXP_OTHER_CONTROL) \|\|
2213	(range2->type == XML_REGEXP_OTHER_FORMAT) \|\|
2214	(range2->type == XML_REGEXP_OTHER_PRIVATE))
2215	ret = 1;
2216	break;
2217	default:
2218	if ((range2->type >= XML_REGEXP_LETTER) &&
2219	(range2->type < XML_REGEXP_BLOCK_NAME))
2220	ret = 0;
2221	else {
2222	/* safety net ! */
2223	return(1);
2224	}
2225	}
2226	}
2227	if (((range1->neg == 0) && (range2->neg != 0)) \|\|
2228	((range1->neg != 0) && (range2->neg == 0)))
2229	ret = !ret;
	Value stored to 'ret' is never read
2230	return(1);
2231	}
2232
2233	/**
2234	* xmlFACompareAtomTypes:
2235	* @type1: an atom type
2236	* @type2: an atom type
2237	*
2238	* Compares two atoms type to check whether they intersect in some ways,
2239	* this is used by xmlFACompareAtoms only
2240	*
2241	* Returns 1 if they may intersect and 0 otherwise
2242	*/
2243	static int
2244	xmlFACompareAtomTypes(xmlRegAtomType type1, xmlRegAtomType type2) {
2245	if ((type1 == XML_REGEXP_EPSILON) \|\|
2246	(type1 == XML_REGEXP_CHARVAL) \|\|
2247	(type1 == XML_REGEXP_RANGES) \|\|
2248	(type1 == XML_REGEXP_SUBREG) \|\|
2249	(type1 == XML_REGEXP_STRING) \|\|
2250	(type1 == XML_REGEXP_ANYCHAR))
2251	return(1);
2252	if ((type2 == XML_REGEXP_EPSILON) \|\|
2253	(type2 == XML_REGEXP_CHARVAL) \|\|
2254	(type2 == XML_REGEXP_RANGES) \|\|
2255	(type2 == XML_REGEXP_SUBREG) \|\|
2256	(type2 == XML_REGEXP_STRING) \|\|
2257	(type2 == XML_REGEXP_ANYCHAR))
2258	return(1);
2259
2260	if (type1 == type2) return(1);
2261
2262	/* simplify subsequent compares by making sure type1 < type2 */
2263	if (type1 > type2) {
2264	xmlRegAtomType tmp = type1;
2265	type1 = type2;
2266	type2 = tmp;
2267	}
2268	switch (type1) {
2269	case XML_REGEXP_ANYSPACE: /* \s */
2270	/* can't be a letter, number, mark, pontuation, symbol */
2271	if ((type2 == XML_REGEXP_NOTSPACE) \|\|
2272	((type2 >= XML_REGEXP_LETTER) &&
2273	(type2 <= XML_REGEXP_LETTER_OTHERS)) \|\|
2274	((type2 >= XML_REGEXP_NUMBER) &&
2275	(type2 <= XML_REGEXP_NUMBER_OTHERS)) \|\|
2276	((type2 >= XML_REGEXP_MARK) &&
2277	(type2 <= XML_REGEXP_MARK_ENCLOSING)) \|\|
2278	((type2 >= XML_REGEXP_PUNCT) &&
2279	(type2 <= XML_REGEXP_PUNCT_OTHERS)) \|\|
2280	((type2 >= XML_REGEXP_SYMBOL) &&
2281	(type2 <= XML_REGEXP_SYMBOL_OTHERS))
2282	) return(0);
2283	break;
2284	case XML_REGEXP_NOTSPACE: /* \S */
2285	break;
2286	case XML_REGEXP_INITNAME: /* \l */
2287	/* can't be a number, mark, separator, pontuation, symbol or other */
2288	if ((type2 == XML_REGEXP_NOTINITNAME) \|\|
2289	((type2 >= XML_REGEXP_NUMBER) &&
2290	(type2 <= XML_REGEXP_NUMBER_OTHERS)) \|\|
2291	((type2 >= XML_REGEXP_MARK) &&
2292	(type2 <= XML_REGEXP_MARK_ENCLOSING)) \|\|
2293	((type2 >= XML_REGEXP_SEPAR) &&
2294	(type2 <= XML_REGEXP_SEPAR_PARA)) \|\|
2295	((type2 >= XML_REGEXP_PUNCT) &&
2296	(type2 <= XML_REGEXP_PUNCT_OTHERS)) \|\|
2297	((type2 >= XML_REGEXP_SYMBOL) &&
2298	(type2 <= XML_REGEXP_SYMBOL_OTHERS)) \|\|
2299	((type2 >= XML_REGEXP_OTHER) &&
2300	(type2 <= XML_REGEXP_OTHER_NA))
2301	) return(0);
2302	break;
2303	case XML_REGEXP_NOTINITNAME: /* \L */
2304	break;
2305	case XML_REGEXP_NAMECHAR: /* \c */
2306	/* can't be a mark, separator, pontuation, symbol or other */
2307	if ((type2 == XML_REGEXP_NOTNAMECHAR) \|\|
2308	((type2 >= XML_REGEXP_MARK) &&
2309	(type2 <= XML_REGEXP_MARK_ENCLOSING)) \|\|
2310	((type2 >= XML_REGEXP_PUNCT) &&
2311	(type2 <= XML_REGEXP_PUNCT_OTHERS)) \|\|
2312	((type2 >= XML_REGEXP_SEPAR) &&
2313	(type2 <= XML_REGEXP_SEPAR_PARA)) \|\|
2314	((type2 >= XML_REGEXP_SYMBOL) &&
2315	(type2 <= XML_REGEXP_SYMBOL_OTHERS)) \|\|
2316	((type2 >= XML_REGEXP_OTHER) &&
2317	(type2 <= XML_REGEXP_OTHER_NA))
2318	) return(0);
2319	break;
2320	case XML_REGEXP_NOTNAMECHAR: /* \C */
2321	break;
2322	case XML_REGEXP_DECIMAL: /* \d */
2323	/* can't be a letter, mark, separator, pontuation, symbol or other */
2324	if ((type2 == XML_REGEXP_NOTDECIMAL) \|\|
2325	(type2 == XML_REGEXP_REALCHAR) \|\|
2326	((type2 >= XML_REGEXP_LETTER) &&
2327	(type2 <= XML_REGEXP_LETTER_OTHERS)) \|\|
2328	((type2 >= XML_REGEXP_MARK) &&
2329	(type2 <= XML_REGEXP_MARK_ENCLOSING)) \|\|
2330	((type2 >= XML_REGEXP_PUNCT) &&
2331	(type2 <= XML_REGEXP_PUNCT_OTHERS)) \|\|
2332	((type2 >= XML_REGEXP_SEPAR) &&
2333	(type2 <= XML_REGEXP_SEPAR_PARA)) \|\|
2334	((type2 >= XML_REGEXP_SYMBOL) &&
2335	(type2 <= XML_REGEXP_SYMBOL_OTHERS)) \|\|
2336	((type2 >= XML_REGEXP_OTHER) &&
2337	(type2 <= XML_REGEXP_OTHER_NA))
2338	)return(0);
2339	break;
2340	case XML_REGEXP_NOTDECIMAL: /* \D */
2341	break;
2342	case XML_REGEXP_REALCHAR: /* \w */
2343	/* can't be a mark, separator, pontuation, symbol or other */
2344	if ((type2 == XML_REGEXP_NOTDECIMAL) \|\|
2345	((type2 >= XML_REGEXP_MARK) &&
2346	(type2 <= XML_REGEXP_MARK_ENCLOSING)) \|\|
2347	((type2 >= XML_REGEXP_PUNCT) &&
2348	(type2 <= XML_REGEXP_PUNCT_OTHERS)) \|\|
2349	((type2 >= XML_REGEXP_SEPAR) &&
2350	(type2 <= XML_REGEXP_SEPAR_PARA)) \|\|
2351	((type2 >= XML_REGEXP_SYMBOL) &&
2352	(type2 <= XML_REGEXP_SYMBOL_OTHERS)) \|\|
2353	((type2 >= XML_REGEXP_OTHER) &&
2354	(type2 <= XML_REGEXP_OTHER_NA))
2355	)return(0);
2356	break;
2357	case XML_REGEXP_NOTREALCHAR: /* \W */
2358	break;
2359	/*
2360	* at that point we know both type 1 and type2 are from
2361	* character categories are ordered and are different,
2362	* it becomes simple because this is a partition
2363	*/
2364	case XML_REGEXP_LETTER:
2365	if (type2 <= XML_REGEXP_LETTER_OTHERS)
2366	return(1);
2367	return(0);
2368	case XML_REGEXP_LETTER_UPPERCASE:
2369	case XML_REGEXP_LETTER_LOWERCASE:
2370	case XML_REGEXP_LETTER_TITLECASE:
2371	case XML_REGEXP_LETTER_MODIFIER:
2372	case XML_REGEXP_LETTER_OTHERS:
2373	return(0);
2374	case XML_REGEXP_MARK:
2375	if (type2 <= XML_REGEXP_MARK_ENCLOSING)
2376	return(1);
2377	return(0);
2378	case XML_REGEXP_MARK_NONSPACING:
2379	case XML_REGEXP_MARK_SPACECOMBINING:
2380	case XML_REGEXP_MARK_ENCLOSING:
2381	return(0);
2382	case XML_REGEXP_NUMBER:
2383	if (type2 <= XML_REGEXP_NUMBER_OTHERS)
2384	return(1);
2385	return(0);
2386	case XML_REGEXP_NUMBER_DECIMAL:
2387	case XML_REGEXP_NUMBER_LETTER:
2388	case XML_REGEXP_NUMBER_OTHERS:
2389	return(0);
2390	case XML_REGEXP_PUNCT:
2391	if (type2 <= XML_REGEXP_PUNCT_OTHERS)
2392	return(1);
2393	return(0);
2394	case XML_REGEXP_PUNCT_CONNECTOR:
2395	case XML_REGEXP_PUNCT_DASH:
2396	case XML_REGEXP_PUNCT_OPEN:
2397	case XML_REGEXP_PUNCT_CLOSE:
2398	case XML_REGEXP_PUNCT_INITQUOTE:
2399	case XML_REGEXP_PUNCT_FINQUOTE:
2400	case XML_REGEXP_PUNCT_OTHERS:
2401	return(0);
2402	case XML_REGEXP_SEPAR:
2403	if (type2 <= XML_REGEXP_SEPAR_PARA)
2404	return(1);
2405	return(0);
2406	case XML_REGEXP_SEPAR_SPACE:
2407	case XML_REGEXP_SEPAR_LINE:
2408	case XML_REGEXP_SEPAR_PARA:
2409	return(0);
2410	case XML_REGEXP_SYMBOL:
2411	if (type2 <= XML_REGEXP_SYMBOL_OTHERS)
2412	return(1);
2413	return(0);
2414	case XML_REGEXP_SYMBOL_MATH:
2415	case XML_REGEXP_SYMBOL_CURRENCY:
2416	case XML_REGEXP_SYMBOL_MODIFIER:
2417	case XML_REGEXP_SYMBOL_OTHERS:
2418	return(0);
2419	case XML_REGEXP_OTHER:
2420	if (type2 <= XML_REGEXP_OTHER_NA)
2421	return(1);
2422	return(0);
2423	case XML_REGEXP_OTHER_CONTROL:
2424	case XML_REGEXP_OTHER_FORMAT:
2425	case XML_REGEXP_OTHER_PRIVATE:
2426	case XML_REGEXP_OTHER_NA:
2427	return(0);
2428	default:
2429	break;
2430	}
2431	return(1);
2432	}
2433
2434	/**
2435	* xmlFAEqualAtoms:
2436	* @atom1: an atom
2437	* @atom2: an atom
2438	* @deep: if not set only compare string pointers
2439	*
2440	* Compares two atoms to check whether they are the same exactly
2441	* this is used to remove equivalent transitions
2442	*
2443	* Returns 1 if same and 0 otherwise
2444	*/
2445	static int
2446	xmlFAEqualAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2, int deep) {
2447	int ret = 0;
2448
2449	if (atom1 == atom2)
2450	return(1);
2451	if ((atom1 == NULL((void)0)) \|\| (atom2 == NULL((void)0)))
2452	return(0);
2453
2454	if (atom1->type != atom2->type)
2455	return(0);
2456	switch (atom1->type) {
2457	case XML_REGEXP_EPSILON:
2458	ret = 0;
2459	break;
2460	case XML_REGEXP_STRING:
2461	if (!deep)
2462	ret = (atom1->valuep == atom2->valuep);
2463	else
2464	ret = xmlStrEqual((xmlChar *)atom1->valuep,
2465	(xmlChar *)atom2->valuep);
2466	break;
2467	case XML_REGEXP_CHARVAL:
2468	ret = (atom1->codepoint == atom2->codepoint);
2469	break;
2470	case XML_REGEXP_RANGES:
2471	/* too hard to do in the general case */
2472	ret = 0;
2473	default:
2474	break;
2475	}
2476	return(ret);
2477	}
2478
2479	/**
2480	* xmlFACompareAtoms:
2481	* @atom1: an atom
2482	* @atom2: an atom
2483	* @deep: if not set only compare string pointers
2484	*
2485	* Compares two atoms to check whether they intersect in some ways,
2486	* this is used by xmlFAComputesDeterminism and xmlFARecurseDeterminism only
2487	*
2488	* Returns 1 if yes and 0 otherwise
2489	*/
2490	static int
2491	xmlFACompareAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2, int deep) {
2492	int ret = 1;
2493
2494	if (atom1 == atom2)
2495	return(1);
2496	if ((atom1 == NULL((void)0)) \|\| (atom2 == NULL((void)0)))
2497	return(0);
2498
2499	if ((atom1->type == XML_REGEXP_ANYCHAR) \|\|
2500	(atom2->type == XML_REGEXP_ANYCHAR))
2501	return(1);
2502
2503	if (atom1->type > atom2->type) {
2504	xmlRegAtomPtr tmp;
2505	tmp = atom1;
2506	atom1 = atom2;
2507	atom2 = tmp;
2508	}
2509	if (atom1->type != atom2->type) {
2510	ret = xmlFACompareAtomTypes(atom1->type, atom2->type);
2511	/* if they can't intersect at the type level break now */
2512	if (ret == 0)
2513	return(0);
2514	}
2515	switch (atom1->type) {
2516	case XML_REGEXP_STRING:
2517	if (!deep)
2518	ret = (atom1->valuep != atom2->valuep);
2519	else
2520	ret = xmlRegStrEqualWildcard((xmlChar *)atom1->valuep,
2521	(xmlChar *)atom2->valuep);
2522	break;
2523	case XML_REGEXP_EPSILON:
2524	goto not_determinist;
2525	case XML_REGEXP_CHARVAL:
2526	if (atom2->type == XML_REGEXP_CHARVAL) {
2527	ret = (atom1->codepoint == atom2->codepoint);
2528	} else {
2529	ret = xmlRegCheckCharacter(atom2, atom1->codepoint);
2530	if (ret < 0)
2531	ret = 1;
2532	}
2533	break;
2534	case XML_REGEXP_RANGES:
2535	if (atom2->type == XML_REGEXP_RANGES) {
2536	int i, j, res;
2537	xmlRegRangePtr r1, r2;
2538
2539	/*
2540	* need to check that none of the ranges eventually matches
2541	*/
2542	for (i = 0;i < atom1->nbRanges;i++) {
2543	for (j = 0;j < atom2->nbRanges;j++) {
2544	r1 = atom1->ranges[i];
2545	r2 = atom2->ranges[j];
2546	res = xmlFACompareRanges(r1, r2);
2547	if (res == 1) {
2548	ret = 1;
2549	goto done;
2550	}
2551	}
2552	}
2553	ret = 0;
2554	}
2555	break;
2556	default:
2557	goto not_determinist;
2558	}
2559	done:
2560	if (atom1->neg != atom2->neg) {
2561	ret = !ret;
2562	}
2563	if (ret == 0)
2564	return(0);
2565	not_determinist:
2566	return(1);
2567	}
2568
2569	/**
2570	* xmlFARecurseDeterminism:
2571	* @ctxt: a regexp parser context
2572	*
2573	* Check whether the associated regexp is determinist,
2574	* should be called after xmlFAEliminateEpsilonTransitions()
2575	*
2576	*/
2577	static int
2578	xmlFARecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state,
2579	int to, xmlRegAtomPtr atom) {
2580	int ret = 1;
2581	int res;
2582	int transnr, nbTrans;
2583	xmlRegTransPtr t1;
2584	int deep = 1;
2585
2586	if (state == NULL((void*)0))
2587	return(ret);
2588
2589	if (ctxt->flags & AM_AUTOMATA_RNG1)
2590	deep = 0;
2591
2592	/*
2593	* don't recurse on transitions potentially added in the course of
2594	* the elimination.
2595	*/
2596	nbTrans = state->nbTrans;
2597	for (transnr = 0;transnr < nbTrans;transnr++) {
2598	t1 = &(state->trans[transnr]);
2599	/*
2600	* check transitions conflicting with the one looked at
2601	*/
2602	if (t1->atom == NULL((void*)0)) {
2603	if (t1->to < 0)
2604	continue;
2605	res = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
2606	to, atom);
2607	if (res == 0) {
2608	ret = 0;
2609	/* t1->nd = 1; */
2610	}
2611	continue;
2612	}
2613	if (t1->to != to)
2614	continue;
2615	if (xmlFACompareAtoms(t1->atom, atom, deep)) {
2616	ret = 0;
2617	/* mark the transition as non-deterministic */
2618	t1->nd = 1;
2619	}
2620	}
2621	return(ret);
2622	}
2623
2624	/**
2625	* xmlFAComputesDeterminism:
2626	* @ctxt: a regexp parser context
2627	*
2628	* Check whether the associated regexp is determinist,
2629	* should be called after xmlFAEliminateEpsilonTransitions()
2630	*
2631	*/
2632	static int
2633	xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt) {
2634	int statenr, transnr;
2635	xmlRegStatePtr state;
2636	xmlRegTransPtr t1, t2, last;
2637	int i;
2638	int ret = 1;
2639	int deep = 1;
2640
2641	#ifdef DEBUG_REGEXP_GRAPH
2642	printf("xmlFAComputesDeterminism\n");
2643	xmlRegPrintCtxt(stdoutstdout, ctxt);
2644	#endif
2645	if (ctxt->determinist != -1)
2646	return(ctxt->determinist);
2647
2648	if (ctxt->flags & AM_AUTOMATA_RNG1)
2649	deep = 0;
2650
2651	/*
2652	* First cleanup the automata removing cancelled transitions
2653	*/
2654	for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2655	state = ctxt->states[statenr];
2656	if (state == NULL((void*)0))
2657	continue;
2658	if (state->nbTrans < 2)
2659	continue;
2660	for (transnr = 0;transnr < state->nbTrans;transnr++) {
2661	t1 = &(state->trans[transnr]);
2662	/*
2663	* Determinism checks in case of counted or all transitions
2664	* will have to be handled separately
2665	*/
2666	if (t1->atom == NULL((void*)0)) {
2667	/* t1->nd = 1; */
2668	continue;
2669	}
2670	if (t1->to == -1) /* eliminated */
2671	continue;
2672	for (i = 0;i < transnr;i++) {
2673	t2 = &(state->trans[i]);
2674	if (t2->to == -1) /* eliminated */
2675	continue;
2676	if (t2->atom != NULL((void*)0)) {
2677	if (t1->to == t2->to) {
2678	/*
2679	* Here we use deep because we want to keep the
2680	* transitions which indicate a conflict
2681	*/
2682	if (xmlFAEqualAtoms(t1->atom, t2->atom, deep) &&
2683	(t1->counter == t2->counter) &&
2684	(t1->count == t2->count))
2685	t2->to = -1; /* eliminated */
2686	}
2687	}
2688	}
2689	}
2690	}
2691
2692	/*
2693	* Check for all states that there aren't 2 transitions
2694	* with the same atom and a different target.
2695	*/
2696	for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
2697	state = ctxt->states[statenr];
2698	if (state == NULL((void*)0))
2699	continue;
2700	if (state->nbTrans < 2)
2701	continue;
2702	last = NULL((void*)0);
2703	for (transnr = 0;transnr < state->nbTrans;transnr++) {
2704	t1 = &(state->trans[transnr]);
2705	/*
2706	* Determinism checks in case of counted or all transitions
2707	* will have to be handled separately
2708	*/
2709	if (t1->atom == NULL((void*)0)) {
2710	continue;
2711	}
2712	if (t1->to == -1) /* eliminated */
2713	continue;
2714	for (i = 0;i < transnr;i++) {
2715	t2 = &(state->trans[i]);
2716	if (t2->to == -1) /* eliminated */
2717	continue;
2718	if (t2->atom != NULL((void*)0)) {
2719	/*
2720	* But here we don't use deep because we want to
2721	* find transitions which indicate a conflict
2722	*/
2723	if (xmlFACompareAtoms(t1->atom, t2->atom, 1)) {
2724	ret = 0;
2725	/* mark the transitions as non-deterministic ones */
2726	t1->nd = 1;
2727	t2->nd = 1;
2728	last = t1;
2729	}
2730	} else if (t1->to != -1) {
2731	/*
2732	* do the closure in case of remaining specific
2733	* epsilon transitions like choices or all
2734	*/
2735	ret = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
2736	t2->to, t2->atom);
2737	/* don't shortcut the computation so all non deterministic
2738	transition get marked down
2739	if (ret == 0)
2740	return(0);
2741	*/
2742	if (ret == 0) {
2743	t1->nd = 1;
2744	/* t2->nd = 1; */
2745	last = t1;
2746	}
2747	}
2748	}
2749	/* don't shortcut the computation so all non deterministic
2750	transition get marked down
2751	if (ret == 0)
2752	break; */
2753	}
2754
2755	/*
2756	* mark specifically the last non-deterministic transition
2757	* from a state since there is no need to set-up rollback
2758	* from it
2759	*/
2760	if (last != NULL((void*)0)) {
2761	last->nd = 2;
2762	}
2763
2764	/* don't shortcut the computation so all non deterministic
2765	transition get marked down
2766	if (ret == 0)
2767	break; */
2768	}
2769
2770	ctxt->determinist = ret;
2771	return(ret);
2772	}
2773
2774	/************************************************************************
2775	* *
2776	* Routines to check input against transition atoms *
2777	* *
2778	************************************************************************/
2779
2780	static int
2781	xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg,
2782	int start, int end, const xmlChar *blockName) {
2783	int ret = 0;
2784
2785	switch (type) {
2786	case XML_REGEXP_STRING:
2787	case XML_REGEXP_SUBREG:
2788	case XML_REGEXP_RANGES:
2789	case XML_REGEXP_EPSILON:
2790	return(-1);
2791	case XML_REGEXP_ANYCHAR:
2792	ret = ((codepoint != '\n') && (codepoint != '\r'));
2793	break;
2794	case XML_REGEXP_CHARVAL:
2795	ret = ((codepoint >= start) && (codepoint <= end));
2796	break;
2797	case XML_REGEXP_NOTSPACE:
2798	neg = !neg;
2799	case XML_REGEXP_ANYSPACE:
2800	ret = ((codepoint == '\n') \|\| (codepoint == '\r') \|\|
2801	(codepoint == '\t') \|\| (codepoint == ' '));
2802	break;
2803	case XML_REGEXP_NOTINITNAME:
2804	neg = !neg;
2805	case XML_REGEXP_INITNAME:
2806	ret = (IS_LETTER(codepoint)((((codepoint) < 0x100) ? (((0x41 <= ((codepoint))) && (((codepoint)) <= 0x5a)) \|\| ((0x61 <= ((codepoint))) && (((codepoint)) <= 0x7a)) \|\| ((0xc0 <= ((codepoint))) && (((codepoint)) <= 0xd6)) \|\| ((0xd8 <= ((codepoint))) && (((codepoint)) <= 0xf6)) \|\| (0xf8 <= ((codepoint)))) : xmlCharInRange((codepoint), &xmlIsBaseCharGroup)) \|\| ((( codepoint) < 0x100) ? 0 : (((0x4e00 <= (codepoint)) && ((codepoint) <= 0x9fa5)) \|\| ((codepoint) == 0x3007) \|\| (( 0x3021 <= (codepoint)) && ((codepoint) <= 0x3029 ))))) \|\|
2807	(codepoint == '_') \|\| (codepoint == ':'));
2808	break;
2809	case XML_REGEXP_NOTNAMECHAR:
2810	neg = !neg;
2811	case XML_REGEXP_NAMECHAR:
2812	ret = (IS_LETTER(codepoint)((((codepoint) < 0x100) ? (((0x41 <= ((codepoint))) && (((codepoint)) <= 0x5a)) \|\| ((0x61 <= ((codepoint))) && (((codepoint)) <= 0x7a)) \|\| ((0xc0 <= ((codepoint))) && (((codepoint)) <= 0xd6)) \|\| ((0xd8 <= ((codepoint))) && (((codepoint)) <= 0xf6)) \|\| (0xf8 <= ((codepoint)))) : xmlCharInRange((codepoint), &xmlIsBaseCharGroup)) \|\| ((( codepoint) < 0x100) ? 0 : (((0x4e00 <= (codepoint)) && ((codepoint) <= 0x9fa5)) \|\| ((codepoint) == 0x3007) \|\| (( 0x3021 <= (codepoint)) && ((codepoint) <= 0x3029 ))))) \|\| IS_DIGIT(codepoint)(((codepoint) < 0x100) ? (((0x30 <= ((codepoint))) && (((codepoint)) <= 0x39))) : xmlCharInRange((codepoint), & xmlIsDigitGroup)) \|\|
2813	(codepoint == '.') \|\| (codepoint == '-') \|\|
2814	(codepoint == '_') \|\| (codepoint == ':') \|\|
2815	IS_COMBINING(codepoint)(((codepoint) < 0x100) ? 0 : xmlCharInRange((codepoint), & xmlIsCombiningGroup)) \|\| IS_EXTENDER(codepoint)(((codepoint) < 0x100) ? ((((codepoint)) == 0xb7)) : xmlCharInRange ((codepoint), &xmlIsExtenderGroup)));
2816	break;
2817	case XML_REGEXP_NOTDECIMAL:
2818	neg = !neg;
2819	case XML_REGEXP_DECIMAL:
2820	ret = xmlUCSIsCatNd(codepoint);
2821	break;
2822	case XML_REGEXP_REALCHAR:
2823	neg = !neg;
2824	case XML_REGEXP_NOTREALCHAR:
2825	ret = xmlUCSIsCatP(codepoint);
2826	if (ret == 0)
2827	ret = xmlUCSIsCatZ(codepoint);
2828	if (ret == 0)
2829	ret = xmlUCSIsCatC(codepoint);
2830	break;
2831	case XML_REGEXP_LETTER:
2832	ret = xmlUCSIsCatL(codepoint);
2833	break;
2834	case XML_REGEXP_LETTER_UPPERCASE:
2835	ret = xmlUCSIsCatLu(codepoint);
2836	break;
2837	case XML_REGEXP_LETTER_LOWERCASE:
2838	ret = xmlUCSIsCatLl(codepoint);
2839	break;
2840	case XML_REGEXP_LETTER_TITLECASE:
2841	ret = xmlUCSIsCatLt(codepoint);
2842	break;
2843	case XML_REGEXP_LETTER_MODIFIER:
2844	ret = xmlUCSIsCatLm(codepoint);
2845	break;
2846	case XML_REGEXP_LETTER_OTHERS:
2847	ret = xmlUCSIsCatLo(codepoint);
2848	break;
2849	case XML_REGEXP_MARK:
2850	ret = xmlUCSIsCatM(codepoint);
2851	break;
2852	case XML_REGEXP_MARK_NONSPACING:
2853	ret = xmlUCSIsCatMn(codepoint);
2854	break;
2855	case XML_REGEXP_MARK_SPACECOMBINING:
2856	ret = xmlUCSIsCatMc(codepoint);
2857	break;
2858	case XML_REGEXP_MARK_ENCLOSING:
2859	ret = xmlUCSIsCatMe(codepoint);
2860	break;
2861	case XML_REGEXP_NUMBER:
2862	ret = xmlUCSIsCatN(codepoint);
2863	break;
2864	case XML_REGEXP_NUMBER_DECIMAL:
2865	ret = xmlUCSIsCatNd(codepoint);
2866	break;
2867	case XML_REGEXP_NUMBER_LETTER:
2868	ret = xmlUCSIsCatNl(codepoint);
2869	break;
2870	case XML_REGEXP_NUMBER_OTHERS:
2871	ret = xmlUCSIsCatNo(codepoint);
2872	break;
2873	case XML_REGEXP_PUNCT:
2874	ret = xmlUCSIsCatP(codepoint);
2875	break;
2876	case XML_REGEXP_PUNCT_CONNECTOR:
2877	ret = xmlUCSIsCatPc(codepoint);
2878	break;
2879	case XML_REGEXP_PUNCT_DASH:
2880	ret = xmlUCSIsCatPd(codepoint);
2881	break;
2882	case XML_REGEXP_PUNCT_OPEN:
2883	ret = xmlUCSIsCatPs(codepoint);
2884	break;
2885	case XML_REGEXP_PUNCT_CLOSE:
2886	ret = xmlUCSIsCatPe(codepoint);
2887	break;
2888	case XML_REGEXP_PUNCT_INITQUOTE:
2889	ret = xmlUCSIsCatPi(codepoint);
2890	break;
2891	case XML_REGEXP_PUNCT_FINQUOTE:
2892	ret = xmlUCSIsCatPf(codepoint);
2893	break;
2894	case XML_REGEXP_PUNCT_OTHERS:
2895	ret = xmlUCSIsCatPo(codepoint);
2896	break;
2897	case XML_REGEXP_SEPAR:
2898	ret = xmlUCSIsCatZ(codepoint);
2899	break;
2900	case XML_REGEXP_SEPAR_SPACE:
2901	ret = xmlUCSIsCatZs(codepoint);
2902	break;
2903	case XML_REGEXP_SEPAR_LINE:
2904	ret = xmlUCSIsCatZl(codepoint);
2905	break;
2906	case XML_REGEXP_SEPAR_PARA:
2907	ret = xmlUCSIsCatZp(codepoint);
2908	break;
2909	case XML_REGEXP_SYMBOL:
2910	ret = xmlUCSIsCatS(codepoint);
2911	break;
2912	case XML_REGEXP_SYMBOL_MATH:
2913	ret = xmlUCSIsCatSm(codepoint);
2914	break;
2915	case XML_REGEXP_SYMBOL_CURRENCY:
2916	ret = xmlUCSIsCatSc(codepoint);
2917	break;
2918	case XML_REGEXP_SYMBOL_MODIFIER:
2919	ret = xmlUCSIsCatSk(codepoint);
2920	break;
2921	case XML_REGEXP_SYMBOL_OTHERS:
2922	ret = xmlUCSIsCatSo(codepoint);
2923	break;
2924	case XML_REGEXP_OTHER:
2925	ret = xmlUCSIsCatC(codepoint);
2926	break;
2927	case XML_REGEXP_OTHER_CONTROL:
2928	ret = xmlUCSIsCatCc(codepoint);
2929	break;
2930	case XML_REGEXP_OTHER_FORMAT:
2931	ret = xmlUCSIsCatCf(codepoint);
2932	break;
2933	case XML_REGEXP_OTHER_PRIVATE:
2934	ret = xmlUCSIsCatCo(codepoint);
2935	break;
2936	case XML_REGEXP_OTHER_NA:
2937	/* ret = xmlUCSIsCatCn(codepoint); */
2938	/* Seems it doesn't exist anymore in recent Unicode releases */
2939	ret = 0;
2940	break;
2941	case XML_REGEXP_BLOCK_NAME:
2942	ret = xmlUCSIsBlock(codepoint, (const char *) blockName);
2943	break;
2944	}
2945	if (neg)
2946	return(!ret);
2947	return(ret);
2948	}
2949
2950	static int
2951	xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint) {
2952	int i, ret = 0;
2953	xmlRegRangePtr range;
2954
2955	if ((atom == NULL((void*)0)) \|\| (!IS_CHAR(codepoint)(((codepoint) < 0x100) ? (((0x9 <= ((codepoint))) && (((codepoint)) <= 0xa)) \|\| (((codepoint)) == 0xd) \|\| (0x20 <= ((codepoint)))) : (((0x100 <= (codepoint)) && ((codepoint) <= 0xd7ff)) \|\| ((0xe000 <= (codepoint)) && ((codepoint) <= 0xfffd)) \|\| ((0x10000 <= (codepoint)) && ((codepoint) <= 0x10ffff))))))
2956	return(-1);
2957
2958	switch (atom->type) {
2959	case XML_REGEXP_SUBREG:
2960	case XML_REGEXP_EPSILON:
2961	return(-1);
2962	case XML_REGEXP_CHARVAL:
2963	return(codepoint == atom->codepoint);
2964	case XML_REGEXP_RANGES: {
2965	int accept = 0;
2966
2967	for (i = 0;i < atom->nbRanges;i++) {
2968	range = atom->ranges[i];
2969	if (range->neg == 2) {
2970	ret = xmlRegCheckCharacterRange(range->type, codepoint,
2971	0, range->start, range->end,
2972	range->blockName);
2973	if (ret != 0)
2974	return(0); /* excluded char */
2975	} else if (range->neg) {
2976	ret = xmlRegCheckCharacterRange(range->type, codepoint,
2977	0, range->start, range->end,
2978	range->blockName);
2979	if (ret == 0)
2980	accept = 1;
2981	else
2982	return(0);
2983	} else {
2984	ret = xmlRegCheckCharacterRange(range->type, codepoint,
2985	0, range->start, range->end,
2986	range->blockName);
2987	if (ret != 0)
2988	accept = 1; /* might still be excluded */
2989	}
2990	}
2991	return(accept);
2992	}
2993	case XML_REGEXP_STRING:
2994	printf("TODO: XML_REGEXP_STRING\n");
2995	return(-1);
2996	case XML_REGEXP_ANYCHAR:
2997	case XML_REGEXP_ANYSPACE:
2998	case XML_REGEXP_NOTSPACE:
2999	case XML_REGEXP_INITNAME:
3000	case XML_REGEXP_NOTINITNAME:
3001	case XML_REGEXP_NAMECHAR:
3002	case XML_REGEXP_NOTNAMECHAR:
3003	case XML_REGEXP_DECIMAL:
3004	case XML_REGEXP_NOTDECIMAL:
3005	case XML_REGEXP_REALCHAR:
3006	case XML_REGEXP_NOTREALCHAR:
3007	case XML_REGEXP_LETTER:
3008	case XML_REGEXP_LETTER_UPPERCASE:
3009	case XML_REGEXP_LETTER_LOWERCASE:
3010	case XML_REGEXP_LETTER_TITLECASE:
3011	case XML_REGEXP_LETTER_MODIFIER:
3012	case XML_REGEXP_LETTER_OTHERS:
3013	case XML_REGEXP_MARK:
3014	case XML_REGEXP_MARK_NONSPACING:
3015	case XML_REGEXP_MARK_SPACECOMBINING:
3016	case XML_REGEXP_MARK_ENCLOSING:
3017	case XML_REGEXP_NUMBER:
3018	case XML_REGEXP_NUMBER_DECIMAL:
3019	case XML_REGEXP_NUMBER_LETTER:
3020	case XML_REGEXP_NUMBER_OTHERS:
3021	case XML_REGEXP_PUNCT:
3022	case XML_REGEXP_PUNCT_CONNECTOR:
3023	case XML_REGEXP_PUNCT_DASH:
3024	case XML_REGEXP_PUNCT_OPEN:
3025	case XML_REGEXP_PUNCT_CLOSE:
3026	case XML_REGEXP_PUNCT_INITQUOTE:
3027	case XML_REGEXP_PUNCT_FINQUOTE:
3028	case XML_REGEXP_PUNCT_OTHERS:
3029	case XML_REGEXP_SEPAR:
3030	case XML_REGEXP_SEPAR_SPACE:
3031	case XML_REGEXP_SEPAR_LINE:
3032	case XML_REGEXP_SEPAR_PARA:
3033	case XML_REGEXP_SYMBOL:
3034	case XML_REGEXP_SYMBOL_MATH:
3035	case XML_REGEXP_SYMBOL_CURRENCY:
3036	case XML_REGEXP_SYMBOL_MODIFIER:
3037	case XML_REGEXP_SYMBOL_OTHERS:
3038	case XML_REGEXP_OTHER:
3039	case XML_REGEXP_OTHER_CONTROL:
3040	case XML_REGEXP_OTHER_FORMAT:
3041	case XML_REGEXP_OTHER_PRIVATE:
3042	case XML_REGEXP_OTHER_NA:
3043	case XML_REGEXP_BLOCK_NAME:
3044	ret = xmlRegCheckCharacterRange(atom->type, codepoint, 0, 0, 0,
3045	(const xmlChar *)atom->valuep);
3046	if (atom->neg)
3047	ret = !ret;
3048	break;
3049	}
3050	return(ret);
3051	}
3052
3053	/************************************************************************
3054	* *
3055	* Saving and restoring state of an execution context *
3056	* *
3057	************************************************************************/
3058
3059	#ifdef DEBUG_REGEXP_EXEC
3060	static void
3061	xmlFARegDebugExec(xmlRegExecCtxtPtr exec) {
3062	printf("state: %d:%d:idx %d", exec->state->no, exec->transno, exec->index);
3063	if (exec->inputStack != NULL((void*)0)) {
3064	int i;
3065	printf(": ");
3066	for (i = 0;(i < 3) && (i < exec->inputStackNr);i++)
3067	printf("%s ", (const char *)
3068	exec->inputStack[exec->inputStackNr - (i + 1)].value);
3069	} else {
3070	printf(": %s", &(exec->inputString[exec->index]));
3071	}
3072	printf("\n");
3073	}
3074	#endif
3075
3076	static void
3077	xmlFARegExecSave(xmlRegExecCtxtPtr exec) {
3078	#ifdef DEBUG_REGEXP_EXEC
3079	printf("saving ");
3080	exec->transno++;
3081	xmlFARegDebugExec(exec);
3082	exec->transno--;
3083	#endif
3084	#ifdef MAX_PUSH10000000
3085	if (exec->nbPush > MAX_PUSH10000000) {
3086	return;
3087	}
3088	exec->nbPush++;
3089	#endif
3090
3091	if (exec->maxRollbacks == 0) {
3092	exec->maxRollbacks = 4;
3093	exec->rollbacks = (xmlRegExecRollback ) xmlMalloc(exec->maxRollbacks
3094	sizeof(xmlRegExecRollback));
3095	if (exec->rollbacks == NULL((void*)0)) {
3096	xmlRegexpErrMemory(NULL((void*)0), "saving regexp");
3097	exec->maxRollbacks = 0;
3098	return;
3099	}
3100	memset(exec->rollbacks, 0,
3101	exec->maxRollbacks * sizeof(xmlRegExecRollback));
3102	} else if (exec->nbRollbacks >= exec->maxRollbacks) {
3103	xmlRegExecRollback *tmp;
3104	int len = exec->maxRollbacks;
3105
3106	exec->maxRollbacks *= 2;
3107	tmp = (xmlRegExecRollback *) xmlRealloc(exec->rollbacks,
3108	exec->maxRollbacks * sizeof(xmlRegExecRollback));
3109	if (tmp == NULL((void*)0)) {
3110	xmlRegexpErrMemory(NULL((void*)0), "saving regexp");
3111	exec->maxRollbacks /= 2;
3112	return;
3113	}
3114	exec->rollbacks = tmp;
3115	tmp = &exec->rollbacks[len];
3116	memset(tmp, 0, (exec->maxRollbacks - len) * sizeof(xmlRegExecRollback));
3117	}
3118	exec->rollbacks[exec->nbRollbacks].state = exec->state;
3119	exec->rollbacks[exec->nbRollbacks].index = exec->index;
3120	exec->rollbacks[exec->nbRollbacks].nextbranch = exec->transno + 1;
3121	if (exec->comp->nbCounters > 0) {
3122	if (exec->rollbacks[exec->nbRollbacks].counts == NULL((void*)0)) {
3123	exec->rollbacks[exec->nbRollbacks].counts = (int *)
3124	xmlMalloc(exec->comp->nbCounters * sizeof(int));
3125	if (exec->rollbacks[exec->nbRollbacks].counts == NULL((void*)0)) {
3126	xmlRegexpErrMemory(NULL((void*)0), "saving regexp");
3127	exec->status = -5;
3128	return;
3129	}
3130	}
3131	memcpy(exec->rollbacks[exec->nbRollbacks].counts, exec->counts,
3132	exec->comp->nbCounters * sizeof(int));
3133	}
3134	exec->nbRollbacks++;
3135	}
3136
3137	static void
3138	xmlFARegExecRollBack(xmlRegExecCtxtPtr exec) {
3139	if (exec->nbRollbacks <= 0) {
3140	exec->status = -1;
3141	#ifdef DEBUG_REGEXP_EXEC
3142	printf("rollback failed on empty stack\n");
3143	#endif
3144	return;
3145	}
3146	exec->nbRollbacks--;
3147	exec->state = exec->rollbacks[exec->nbRollbacks].state;
3148	exec->index = exec->rollbacks[exec->nbRollbacks].index;
3149	exec->transno = exec->rollbacks[exec->nbRollbacks].nextbranch;
3150	if (exec->comp->nbCounters > 0) {
3151	if (exec->rollbacks[exec->nbRollbacks].counts == NULL((void*)0)) {
3152	fprintf(stderrstderr, "exec save: allocation failed");
3153	exec->status = -6;
3154	return;
3155	}
3156	memcpy(exec->counts, exec->rollbacks[exec->nbRollbacks].counts,
3157	exec->comp->nbCounters * sizeof(int));
3158	}
3159
3160	#ifdef DEBUG_REGEXP_EXEC
3161	printf("restored ");
3162	xmlFARegDebugExec(exec);
3163	#endif
3164	}
3165
3166	/************************************************************************
3167	* *
3168	* Verifier, running an input against a compiled regexp *
3169	* *
3170	************************************************************************/
3171
3172	static int
3173	xmlFARegExec(xmlRegexpPtr comp, const xmlChar *content) {
3174	xmlRegExecCtxt execval;
3175	xmlRegExecCtxtPtr exec = &execval;
3176	int ret, codepoint = 0, len, deter;
3177
3178	exec->inputString = content;
3179	exec->index = 0;
3180	exec->nbPush = 0;
3181	exec->determinist = 1;
3182	exec->maxRollbacks = 0;
3183	exec->nbRollbacks = 0;
3184	exec->rollbacks = NULL((void*)0);
3185	exec->status = 0;
3186	exec->comp = comp;
3187	exec->state = comp->states[0];
3188	exec->transno = 0;
3189	exec->transcount = 0;
3190	exec->inputStack = NULL((void*)0);
3191	exec->inputStackMax = 0;
3192	if (comp->nbCounters > 0) {
3193	exec->counts = (int ) xmlMalloc(comp->nbCounters sizeof(int));
3194	if (exec->counts == NULL((void*)0)) {
3195	xmlRegexpErrMemory(NULL((void*)0), "running regexp");
3196	return(-1);
3197	}
3198	memset(exec->counts, 0, comp->nbCounters * sizeof(int));
3199	} else
3200	exec->counts = NULL((void*)0);
3201	while ((exec->status == 0) &&
3202	((exec->inputString[exec->index] != 0) \|\|
3203	((exec->state != NULL((void*)0)) &&
3204	(exec->state->type != XML_REGEXP_FINAL_STATE)))) {
3205	xmlRegTransPtr trans;
3206	xmlRegAtomPtr atom;
3207
3208	/*
3209	* If end of input on non-terminal state, rollback, however we may
3210	* still have epsilon like transition for counted transitions
3211	* on counters, in that case don't break too early. Additionally,
3212	* if we are working on a range like "AB{0,2}", where B is not present,
3213	* we don't want to break.
3214	*/
3215	len = 1;
3216	if ((exec->inputString[exec->index] == 0) && (exec->counts == NULL((void*)0))) {
3217	/*
3218	* if there is a transition, we must check if
3219	* atom allows minOccurs of 0
3220	*/
3221	if (exec->transno < exec->state->nbTrans) {
3222	trans = &exec->state->trans[exec->transno];
3223	if (trans->to >=0) {
3224	atom = trans->atom;
3225	if (!((atom->min == 0) && (atom->max > 0)))
3226	goto rollback;
3227	}
3228	} else
3229	goto rollback;
3230	}
3231
3232	exec->transcount = 0;
3233	for (;exec->transno < exec->state->nbTrans;exec->transno++) {
3234	trans = &exec->state->trans[exec->transno];
3235	if (trans->to < 0)
3236	continue;
3237	atom = trans->atom;
3238	ret = 0;
3239	deter = 1;
3240	if (trans->count >= 0) {
3241	int count;
3242	xmlRegCounterPtr counter;
3243
3244	if (exec->counts == NULL((void*)0)) {
3245	exec->status = -1;
3246	goto error;
3247	}
3248	/*
3249	* A counted transition.
3250	*/
3251
3252	count = exec->counts[trans->count];
3253	counter = &exec->comp->counters[trans->count];
3254	#ifdef DEBUG_REGEXP_EXEC
3255	printf("testing count %d: val %d, min %d, max %d\n",
3256	trans->count, count, counter->min, counter->max);
3257	#endif
3258	ret = ((count >= counter->min) && (count <= counter->max));
3259	if ((ret) && (counter->min != counter->max))
3260	deter = 0;
3261	} else if (atom == NULL((void*)0)) {
3262	fprintf(stderrstderr, "epsilon transition left at runtime\n");
3263	exec->status = -2;
3264	break;
3265	} else if (exec->inputString[exec->index] != 0) {
3266	codepoint = CUR_SCHAR(&(exec->inputString[exec->index]), len)xmlStringCurrentChar(((void*)0), &(exec->inputString[exec ->index]), &len);
3267	ret = xmlRegCheckCharacter(atom, codepoint);
3268	if ((ret == 1) && (atom->min >= 0) && (atom->max > 0)) {
3269	xmlRegStatePtr to = comp->states[trans->to];
3270
3271	/*
3272	* this is a multiple input sequence
3273	* If there is a counter associated increment it now.
3274	* before potentially saving and rollback
3275	* do not increment if the counter is already over the
3276	* maximum limit in which case get to next transition
3277	*/
3278	if (trans->counter >= 0) {
3279	xmlRegCounterPtr counter;
3280
3281	if ((exec->counts == NULL((void*)0)) \|\|
3282	(exec->comp == NULL((void*)0)) \|\|
3283	(exec->comp->counters == NULL((void*)0))) {
3284	exec->status = -1;
3285	goto error;
3286	}
3287	counter = &exec->comp->counters[trans->counter];
3288	if (exec->counts[trans->counter] >= counter->max)
3289	continue; /* for loop on transitions */
3290
3291	#ifdef DEBUG_REGEXP_EXEC
3292	printf("Increasing count %d\n", trans->counter);
3293	#endif
3294	exec->counts[trans->counter]++;
3295	}
3296	if (exec->state->nbTrans > exec->transno + 1) {
3297	xmlFARegExecSave(exec);
3298	}
3299	exec->transcount = 1;
3300	do {
3301	/*
3302	* Try to progress as much as possible on the input
3303	*/
3304	if (exec->transcount == atom->max) {
3305	break;
3306	}
3307	exec->index += len;
3308	/*
3309	* End of input: stop here
3310	*/
3311	if (exec->inputString[exec->index] == 0) {
3312	exec->index -= len;
3313	break;
3314	}
3315	if (exec->transcount >= atom->min) {
3316	int transno = exec->transno;
3317	xmlRegStatePtr state = exec->state;
3318
3319	/*
3320	* The transition is acceptable save it
3321	*/
3322	exec->transno = -1; /* trick */
3323	exec->state = to;
3324	xmlFARegExecSave(exec);
3325	exec->transno = transno;
3326	exec->state = state;
3327	}
3328	codepoint = CUR_SCHAR(&(exec->inputString[exec->index]),xmlStringCurrentChar(((void*)0), &(exec->inputString[exec ->index]), &len)
3329	len)xmlStringCurrentChar(((void*)0), &(exec->inputString[exec ->index]), &len);
3330	ret = xmlRegCheckCharacter(atom, codepoint);
3331	exec->transcount++;
3332	} while (ret == 1);
3333	if (exec->transcount < atom->min)
3334	ret = 0;
3335
3336	/*
3337	* If the last check failed but one transition was found
3338	* possible, rollback
3339	*/
3340	if (ret < 0)
3341	ret = 0;
3342	if (ret == 0) {
3343	goto rollback;
3344	}
3345	if (trans->counter >= 0) {
3346	if (exec->counts == NULL((void*)0)) {
3347	exec->status = -1;
3348	goto error;
3349	}
3350	#ifdef DEBUG_REGEXP_EXEC
3351	printf("Decreasing count %d\n", trans->counter);
3352	#endif
3353	exec->counts[trans->counter]--;
3354	}
3355	} else if ((ret == 0) && (atom->min == 0) && (atom->max > 0)) {
3356	/*
3357	* we don't match on the codepoint, but minOccurs of 0
3358	* says that's ok. Setting len to 0 inhibits stepping
3359	* over the codepoint.
3360	*/
3361	exec->transcount = 1;
3362	len = 0;
3363	ret = 1;
3364	}
3365	} else if ((atom->min == 0) && (atom->max > 0)) {
3366	/* another spot to match when minOccurs is 0 */
3367	exec->transcount = 1;
3368	len = 0;
3369	ret = 1;
3370	}
3371	if (ret == 1) {
3372	if ((trans->nd == 1) \|\|
3373	((trans->count >= 0) && (deter == 0) &&
3374	(exec->state->nbTrans > exec->transno + 1))) {
3375	#ifdef DEBUG_REGEXP_EXEC
3376	if (trans->nd == 1)
3377	printf("Saving on nd transition atom %d for %c at %d\n",
3378	trans->atom->no, codepoint, exec->index);
3379	else
3380	printf("Saving on counted transition count %d for %c at %d\n",
3381	trans->count, codepoint, exec->index);
3382	#endif
3383	xmlFARegExecSave(exec);
3384	}
3385	if (trans->counter >= 0) {
3386	xmlRegCounterPtr counter;
3387
3388	/* make sure we don't go over the counter maximum value */
3389	if ((exec->counts == NULL((void*)0)) \|\|
3390	(exec->comp == NULL((void*)0)) \|\|
3391	(exec->comp->counters == NULL((void*)0))) {
3392	exec->status = -1;
3393	goto error;
3394	}
3395	counter = &exec->comp->counters[trans->counter];
3396	if (exec->counts[trans->counter] >= counter->max)
3397	continue; /* for loop on transitions */
3398	#ifdef DEBUG_REGEXP_EXEC
3399	printf("Increasing count %d\n", trans->counter);
3400	#endif
3401	exec->counts[trans->counter]++;
3402	}
3403	if ((trans->count >= 0) &&
3404	(trans->count < REGEXP_ALL_COUNTER0x123456)) {
3405	if (exec->counts == NULL((void*)0)) {
3406	exec->status = -1;
3407	goto error;
3408	}
3409	#ifdef DEBUG_REGEXP_EXEC
3410	printf("resetting count %d on transition\n",
3411	trans->count);
3412	#endif
3413	exec->counts[trans->count] = 0;
3414	}
3415	#ifdef DEBUG_REGEXP_EXEC
3416	printf("entering state %d\n", trans->to);
3417	#endif
3418	exec->state = comp->states[trans->to];
3419	exec->transno = 0;
3420	if (trans->atom != NULL((void*)0)) {
3421	exec->index += len;
3422	}
3423	goto progress;
3424	} else if (ret < 0) {
3425	exec->status = -4;
3426	break;
3427	}
3428	}
3429	if ((exec->transno != 0) \|\| (exec->state->nbTrans == 0)) {
3430	rollback:
3431	/*
3432	* Failed to find a way out
3433	*/
3434	exec->determinist = 0;
3435	#ifdef DEBUG_REGEXP_EXEC
3436	printf("rollback from state %d on %d:%c\n", exec->state->no,
3437	codepoint,codepoint);
3438	#endif
3439	xmlFARegExecRollBack(exec);
3440	}
3441	progress:
3442	continue;
3443	}
3444	error:
3445	if (exec->rollbacks != NULL((void*)0)) {
3446	if (exec->counts != NULL((void*)0)) {
3447	int i;
3448
3449	for (i = 0;i < exec->maxRollbacks;i++)
3450	if (exec->rollbacks[i].counts != NULL((void*)0))
3451	xmlFree(exec->rollbacks[i].counts);
3452	}
3453	xmlFree(exec->rollbacks);
3454	}
3455	if (exec->counts != NULL((void*)0))
3456	xmlFree(exec->counts);
3457	if (exec->status == 0)
3458	return(1);
3459	if (exec->status == -1) {
3460	if (exec->nbPush > MAX_PUSH10000000)
3461	return(-1);
3462	return(0);
3463	}
3464	return(exec->status);
3465	}
3466
3467	/************************************************************************
3468	* *
3469	* Progressive interface to the verifier one atom at a time *
3470	* *
3471	************************************************************************/
3472	#ifdef DEBUG_ERR
3473	static void testerr(xmlRegExecCtxtPtr exec);
3474	#endif
3475
3476	/**
3477	* xmlRegNewExecCtxt:
3478	* @comp: a precompiled regular expression
3479	* @callback: a callback function used for handling progresses in the
3480	* automata matching phase
3481	* @data: the context data associated to the callback in this context
3482	*
3483	* Build a context used for progressive evaluation of a regexp.
3484	*
3485	* Returns the new context
3486	*/
3487	xmlRegExecCtxtPtr
3488	xmlRegNewExecCtxt(xmlRegexpPtr comp, xmlRegExecCallbacks callback, void *data) {
3489	xmlRegExecCtxtPtr exec;
3490
3491	if (comp == NULL((void*)0))
3492	return(NULL((void*)0));
3493	if ((comp->compact == NULL((void)0)) && (comp->states == NULL((void)0)))
3494	return(NULL((void*)0));
3495	exec = (xmlRegExecCtxtPtr) xmlMalloc(sizeof(xmlRegExecCtxt));
3496	if (exec == NULL((void*)0)) {
3497	xmlRegexpErrMemory(NULL((void*)0), "creating execution context");
3498	return(NULL((void*)0));
3499	}
3500	memset(exec, 0, sizeof(xmlRegExecCtxt));
3501	exec->inputString = NULL((void*)0);
3502	exec->index = 0;
3503	exec->determinist = 1;
3504	exec->maxRollbacks = 0;
3505	exec->nbRollbacks = 0;
3506	exec->rollbacks = NULL((void*)0);
3507	exec->status = 0;
3508	exec->comp = comp;
3509	if (comp->compact == NULL((void*)0))
3510	exec->state = comp->states[0];
3511	exec->transno = 0;
3512	exec->transcount = 0;
3513	exec->callback = callback;
3514	exec->data = data;
3515	if (comp->nbCounters > 0) {
3516	/*
3517	* For error handling, exec->counts is allocated twice the size
3518	* the second half is used to store the data in case of rollback
3519	*/
3520	exec->counts = (int ) xmlMalloc(comp->nbCounters sizeof(int)
3521	* 2);
3522	if (exec->counts == NULL((void*)0)) {
3523	xmlRegexpErrMemory(NULL((void*)0), "creating execution context");
3524	xmlFree(exec);
3525	return(NULL((void*)0));
3526	}
3527	memset(exec->counts, 0, comp->nbCounters * sizeof(int) * 2);
3528	exec->errCounts = &exec->counts[comp->nbCounters];
3529	} else {
3530	exec->counts = NULL((void*)0);
3531	exec->errCounts = NULL((void*)0);
3532	}
3533	exec->inputStackMax = 0;
3534	exec->inputStackNr = 0;
3535	exec->inputStack = NULL((void*)0);
3536	exec->errStateNo = -1;
3537	exec->errString = NULL((void*)0);
3538	exec->nbPush = 0;
3539	return(exec);
3540	}
3541
3542	/**
3543	* xmlRegFreeExecCtxt:
3544	* @exec: a regular expression evaulation context
3545	*
3546	* Free the structures associated to a regular expression evaulation context.
3547	*/
3548	void
3549	xmlRegFreeExecCtxt(xmlRegExecCtxtPtr exec) {
3550	if (exec == NULL((void*)0))
3551	return;
3552
3553	if (exec->rollbacks != NULL((void*)0)) {
3554	if (exec->counts != NULL((void*)0)) {
3555	int i;
3556
3557	for (i = 0;i < exec->maxRollbacks;i++)
3558	if (exec->rollbacks[i].counts != NULL((void*)0))
3559	xmlFree(exec->rollbacks[i].counts);
3560	}
3561	xmlFree(exec->rollbacks);
3562	}
3563	if (exec->counts != NULL((void*)0))
3564	xmlFree(exec->counts);
3565	if (exec->inputStack != NULL((void*)0)) {
3566	int i;
3567
3568	for (i = 0;i < exec->inputStackNr;i++) {
3569	if (exec->inputStack[i].value != NULL((void*)0))
3570	xmlFree(exec->inputStack[i].value);
3571	}
3572	xmlFree(exec->inputStack);
3573	}
3574	if (exec->errString != NULL((void*)0))
3575	xmlFree(exec->errString);
3576	xmlFree(exec);
3577	}
3578
3579	static void
3580	xmlFARegExecSaveInputString(xmlRegExecCtxtPtr exec, const xmlChar *value,
3581	void *data) {
3582	#ifdef DEBUG_PUSH
3583	printf("saving value: %d:%s\n", exec->inputStackNr, value);
3584	#endif
3585	if (exec->inputStackMax == 0) {
3586	exec->inputStackMax = 4;
3587	exec->inputStack = (xmlRegInputTokenPtr)
3588	xmlMalloc(exec->inputStackMax * sizeof(xmlRegInputToken));
3589	if (exec->inputStack == NULL((void*)0)) {
3590	xmlRegexpErrMemory(NULL((void*)0), "pushing input string");
3591	exec->inputStackMax = 0;
3592	return;
3593	}
3594	} else if (exec->inputStackNr + 1 >= exec->inputStackMax) {
3595	xmlRegInputTokenPtr tmp;
3596
3597	exec->inputStackMax *= 2;
3598	tmp = (xmlRegInputTokenPtr) xmlRealloc(exec->inputStack,
3599	exec->inputStackMax * sizeof(xmlRegInputToken));
3600	if (tmp == NULL((void*)0)) {
3601	xmlRegexpErrMemory(NULL((void*)0), "pushing input string");
3602	exec->inputStackMax /= 2;
3603	return;
3604	}
3605	exec->inputStack = tmp;
3606	}
3607	exec->inputStack[exec->inputStackNr].value = xmlStrdup(value);
3608	exec->inputStack[exec->inputStackNr].data = data;
3609	exec->inputStackNr++;
3610	exec->inputStack[exec->inputStackNr].value = NULL((void*)0);
3611	exec->inputStack[exec->inputStackNr].data = NULL((void*)0);
3612	}
3613
3614	/**
3615	* xmlRegStrEqualWildcard:
3616	* @expStr: the string to be evaluated
3617	* @valStr: the validation string
3618	*
3619	* Checks if both strings are equal or have the same content. "*"
3620	* can be used as a wildcard in @valStr; "\|" is used as a seperator of
3621	* substrings in both @expStr and @valStr.
3622	*
3623	* Returns 1 if the comparison is satisfied and the number of substrings
3624	* is equal, 0 otherwise.
3625	*/
3626
3627	static int
3628	xmlRegStrEqualWildcard(const xmlChar expStr, const xmlChar valStr) {
3629	if (expStr == valStr) return(1);
3630	if (expStr == NULL((void*)0)) return(0);
3631	if (valStr == NULL((void*)0)) return(0);
3632	do {
3633	/*
3634	* Eval if we have a wildcard for the current item.
3635	*/
3636	if (expStr != valStr) {
3637	/* if one of them starts with a wildcard make valStr be it */
3638	if (valStr == '') {
3639	const xmlChar *tmp;
3640
3641	tmp = valStr;
3642	valStr = expStr;
3643	expStr = tmp;
3644	}
3645	if ((valStr != 0) && (expStr != 0) && (expStr++ == '')) {
3646	do {
3647	if (*valStr == XML_REG_STRING_SEPARATOR'\|')
3648	break;
3649	valStr++;
3650	} while (*valStr != 0);
3651	continue;
3652	} else
3653	return(0);
3654	}
3655	expStr++;
3656	valStr++;
3657	} while (*valStr != 0);
3658	if (*expStr != 0)
3659	return (0);
3660	else
3661	return (1);
3662	}
3663
3664	/**
3665	* xmlRegCompactPushString:
3666	* @exec: a regexp execution context
3667	* @comp: the precompiled exec with a compact table
3668	* @value: a string token input
3669	* @data: data associated to the token to reuse in callbacks
3670	*
3671	* Push one input token in the execution context
3672	*
3673	* Returns: 1 if the regexp reached a final state, 0 if non-final, and
3674	* a negative value in case of error.
3675	*/
3676	static int
3677	xmlRegCompactPushString(xmlRegExecCtxtPtr exec,
3678	xmlRegexpPtr comp,
3679	const xmlChar *value,
3680	void *data) {
3681	int state = exec->index;
3682	int i, target;
3683
3684	if ((comp == NULL((void)0)) \|\| (comp->compact == NULL((void)0)) \|\| (comp->stringMap == NULL((void*)0)))
3685	return(-1);
3686
3687	if (value == NULL((void*)0)) {
3688	/*
3689	* are we at a final state ?
3690	*/
3691	if (comp->compact[state * (comp->nbstrings + 1)] ==
3692	XML_REGEXP_FINAL_STATE)
3693	return(1);
3694	return(0);
3695	}
3696
3697	#ifdef DEBUG_PUSH
3698	printf("value pushed: %s\n", value);
3699	#endif
3700
3701	/*
3702	* Examine all outside transitions from current state
3703	*/
3704	for (i = 0;i < comp->nbstrings;i++) {
3705	target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
3706	if ((target > 0) && (target <= comp->nbstates)) {
3707	target--; /* to avoid 0 */
3708	if (xmlRegStrEqualWildcard(comp->stringMap[i], value)) {
3709	exec->index = target;
3710	if ((exec->callback != NULL((void)0)) && (comp->transdata != NULL((void)0))) {
3711	exec->callback(exec->data, value,
3712	comp->transdata[state * comp->nbstrings + i], data);
3713	}
3714	#ifdef DEBUG_PUSH
3715	printf("entering state %d\n", target);
3716	#endif
3717	if (comp->compact[target * (comp->nbstrings + 1)] ==
3718	XML_REGEXP_SINK_STATE)
3719	goto error;
3720
3721	if (comp->compact[target * (comp->nbstrings + 1)] ==
3722	XML_REGEXP_FINAL_STATE)
3723	return(1);
3724	return(0);
3725	}
3726	}
3727	}
3728	/*
3729	* Failed to find an exit transition out from current state for the
3730	* current token
3731	*/
3732	#ifdef DEBUG_PUSH
3733	printf("failed to find a transition for %s on state %d\n", value, state);
3734	#endif
3735	error:
3736	if (exec->errString != NULL((void*)0))
3737	xmlFree(exec->errString);
3738	exec->errString = xmlStrdup(value);
3739	exec->errStateNo = state;
3740	exec->status = -1;
3741	#ifdef DEBUG_ERR
3742	testerr(exec);
3743	#endif
3744	return(-1);
3745	}
3746
3747	/**
3748	* xmlRegExecPushStringInternal:
3749	* @exec: a regexp execution context or NULL to indicate the end
3750	* @value: a string token input
3751	* @data: data associated to the token to reuse in callbacks
3752	* @compound: value was assembled from 2 strings
3753	*
3754	* Push one input token in the execution context
3755	*
3756	* Returns: 1 if the regexp reached a final state, 0 if non-final, and
3757	* a negative value in case of error.
3758	*/
3759	static int
3760	xmlRegExecPushStringInternal(xmlRegExecCtxtPtr exec, const xmlChar *value,
3761	void *data, int compound) {
3762	xmlRegTransPtr trans;
3763	xmlRegAtomPtr atom;
3764	int ret;
3765	int final = 0;
3766	int progress = 1;
3767
3768	if (exec == NULL((void*)0))
3769	return(-1);
3770	if (exec->comp == NULL((void*)0))
3771	return(-1);
3772	if (exec->status != 0)
3773	return(exec->status);
3774
3775	if (exec->comp->compact != NULL((void*)0))
3776	return(xmlRegCompactPushString(exec, exec->comp, value, data));
3777
3778	if (value == NULL((void*)0)) {
3779	if (exec->state->type == XML_REGEXP_FINAL_STATE)
3780	return(1);
3781	final = 1;
3782	}
3783
3784	#ifdef DEBUG_PUSH
3785	printf("value pushed: %s\n", value);
3786	#endif
3787	/*
3788	* If we have an active rollback stack push the new value there
3789	* and get back to where we were left
3790	*/
3791	if ((value != NULL((void*)0)) && (exec->inputStackNr > 0)) {
3792	xmlFARegExecSaveInputString(exec, value, data);
3793	value = exec->inputStack[exec->index].value;
3794	data = exec->inputStack[exec->index].data;
3795	#ifdef DEBUG_PUSH
3796	printf("value loaded: %s\n", value);
3797	#endif
3798	}
3799
3800	while ((exec->status == 0) &&
3801	((value != NULL((void*)0)) \|\|
3802	((final == 1) &&
3803	(exec->state->type != XML_REGEXP_FINAL_STATE)))) {
3804
3805	/*
3806	* End of input on non-terminal state, rollback, however we may
3807	* still have epsilon like transition for counted transitions
3808	* on counters, in that case don't break too early.
3809	*/
3810	if ((value == NULL((void)0)) && (exec->counts == NULL((void)0)))
3811	goto rollback;
3812
3813	exec->transcount = 0;
3814	for (;exec->transno < exec->state->nbTrans;exec->transno++) {
3815	trans = &exec->state->trans[exec->transno];
3816	if (trans->to < 0)
3817	continue;
3818	atom = trans->atom;
3819	ret = 0;
3820	if (trans->count == REGEXP_ALL_LAX_COUNTER0x123457) {
3821	int i;
3822	int count;
3823	xmlRegTransPtr t;
3824	xmlRegCounterPtr counter;
3825
3826	ret = 0;
3827
3828	#ifdef DEBUG_PUSH
3829	printf("testing all lax %d\n", trans->count);
3830	#endif
3831	/*
3832	* Check all counted transitions from the current state
3833	*/
3834	if ((value == NULL((void*)0)) && (final)) {
3835	ret = 1;
3836	} else if (value != NULL((void*)0)) {
3837	for (i = 0;i < exec->state->nbTrans;i++) {
3838	t = &exec->state->trans[i];
3839	if ((t->counter < 0) \|\| (t == trans))
3840	continue;
3841	counter = &exec->comp->counters[t->counter];
3842	count = exec->counts[t->counter];
3843	if ((count < counter->max) &&
3844	(t->atom != NULL((void*)0)) &&
3845	(xmlStrEqual(value, t->atom->valuep))) {
3846	ret = 0;
3847	break;
3848	}
3849	if ((count >= counter->min) &&
3850	(count < counter->max) &&
3851	(t->atom != NULL((void*)0)) &&
3852	(xmlStrEqual(value, t->atom->valuep))) {
3853	ret = 1;
3854	break;
3855	}
3856	}
3857	}
3858	} else if (trans->count == REGEXP_ALL_COUNTER0x123456) {
3859	int i;
3860	int count;
3861	xmlRegTransPtr t;
3862	xmlRegCounterPtr counter;
3863
3864	ret = 1;
3865
3866	#ifdef DEBUG_PUSH
3867	printf("testing all %d\n", trans->count);
3868	#endif
3869	/*
3870	* Check all counted transitions from the current state
3871	*/
3872	for (i = 0;i < exec->state->nbTrans;i++) {
3873	t = &exec->state->trans[i];
3874	if ((t->counter < 0) \|\| (t == trans))
3875	continue;
3876	counter = &exec->comp->counters[t->counter];
3877	count = exec->counts[t->counter];
3878	if ((count < counter->min) \|\| (count > counter->max)) {
3879	ret = 0;
3880	break;
3881	}
3882	}
3883	} else if (trans->count >= 0) {
3884	int count;
3885	xmlRegCounterPtr counter;
3886
3887	/*
3888	* A counted transition.
3889	*/
3890
3891	count = exec->counts[trans->count];
3892	counter = &exec->comp->counters[trans->count];
3893	#ifdef DEBUG_PUSH
3894	printf("testing count %d: val %d, min %d, max %d\n",
3895	trans->count, count, counter->min, counter->max);
3896	#endif
3897	ret = ((count >= counter->min) && (count <= counter->max));
3898	} else if (atom == NULL((void*)0)) {
3899	fprintf(stderrstderr, "epsilon transition left at runtime\n");
3900	exec->status = -2;
3901	break;
3902	} else if (value != NULL((void*)0)) {
3903	ret = xmlRegStrEqualWildcard(atom->valuep, value);
3904	if (atom->neg) {
3905	ret = !ret;
3906	if (!compound)
3907	ret = 0;
3908	}
3909	if ((ret == 1) && (trans->counter >= 0)) {
3910	xmlRegCounterPtr counter;
3911	int count;
3912
3913	count = exec->counts[trans->counter];
3914	counter = &exec->comp->counters[trans->counter];
3915	if (count >= counter->max)
3916	ret = 0;
3917	}
3918
3919	if ((ret == 1) && (atom->min > 0) && (atom->max > 0)) {
3920	xmlRegStatePtr to = exec->comp->states[trans->to];
3921
3922	/*
3923	* this is a multiple input sequence
3924	*/
3925	if (exec->state->nbTrans > exec->transno + 1) {
3926	if (exec->inputStackNr <= 0) {
3927	xmlFARegExecSaveInputString(exec, value, data);
3928	}
3929	xmlFARegExecSave(exec);
3930	}
3931	exec->transcount = 1;
3932	do {
3933	/*
3934	* Try to progress as much as possible on the input
3935	*/
3936	if (exec->transcount == atom->max) {
3937	break;
3938	}
3939	exec->index++;
3940	value = exec->inputStack[exec->index].value;
3941	data = exec->inputStack[exec->index].data;
3942	#ifdef DEBUG_PUSH
3943	printf("value loaded: %s\n", value);
3944	#endif
3945
3946	/*
3947	* End of input: stop here
3948	*/
3949	if (value == NULL((void*)0)) {
3950	exec->index --;
3951	break;
3952	}
3953	if (exec->transcount >= atom->min) {
3954	int transno = exec->transno;
3955	xmlRegStatePtr state = exec->state;
3956
3957	/*
3958	* The transition is acceptable save it
3959	*/
3960	exec->transno = -1; /* trick */
3961	exec->state = to;
3962	if (exec->inputStackNr <= 0) {
3963	xmlFARegExecSaveInputString(exec, value, data);
3964	}
3965	xmlFARegExecSave(exec);
3966	exec->transno = transno;
3967	exec->state = state;
3968	}
3969	ret = xmlStrEqual(value, atom->valuep);
3970	exec->transcount++;
3971	} while (ret == 1);
3972	if (exec->transcount < atom->min)
3973	ret = 0;
3974
3975	/*
3976	* If the last check failed but one transition was found
3977	* possible, rollback
3978	*/
3979	if (ret < 0)
3980	ret = 0;
3981	if (ret == 0) {
3982	goto rollback;
3983	}
3984	}
3985	}
3986	if (ret == 1) {
3987	if ((exec->callback != NULL((void)0)) && (atom != NULL((void)0)) &&
3988	(data != NULL((void*)0))) {
3989	exec->callback(exec->data, atom->valuep,
3990	atom->data, data);
3991	}
3992	if (exec->state->nbTrans > exec->transno + 1) {
3993	if (exec->inputStackNr <= 0) {
3994	xmlFARegExecSaveInputString(exec, value, data);
3995	}
3996	xmlFARegExecSave(exec);
3997	}
3998	if (trans->counter >= 0) {
3999	#ifdef DEBUG_PUSH
4000	printf("Increasing count %d\n", trans->counter);
4001	#endif
4002	exec->counts[trans->counter]++;
4003	}
4004	if ((trans->count >= 0) &&
4005	(trans->count < REGEXP_ALL_COUNTER0x123456)) {
4006	#ifdef DEBUG_REGEXP_EXEC
4007	printf("resetting count %d on transition\n",
4008	trans->count);
4009	#endif
4010	exec->counts[trans->count] = 0;
4011	}
4012	#ifdef DEBUG_PUSH
4013	printf("entering state %d\n", trans->to);
4014	#endif
4015	if ((exec->comp->states[trans->to] != NULL((void*)0)) &&
4016	(exec->comp->states[trans->to]->type ==
4017	XML_REGEXP_SINK_STATE)) {
4018	/*
4019	* entering a sink state, save the current state as error
4020	* state.
4021	*/
4022	if (exec->errString != NULL((void*)0))
4023	xmlFree(exec->errString);
4024	exec->errString = xmlStrdup(value);
4025	exec->errState = exec->state;
4026	memcpy(exec->errCounts, exec->counts,
4027	exec->comp->nbCounters * sizeof(int));
4028	}
4029	exec->state = exec->comp->states[trans->to];
4030	exec->transno = 0;
4031	if (trans->atom != NULL((void*)0)) {
4032	if (exec->inputStack != NULL((void*)0)) {
4033	exec->index++;
4034	if (exec->index < exec->inputStackNr) {
4035	value = exec->inputStack[exec->index].value;
4036	data = exec->inputStack[exec->index].data;
4037	#ifdef DEBUG_PUSH
4038	printf("value loaded: %s\n", value);
4039	#endif
4040	} else {
4041	value = NULL((void*)0);
4042	data = NULL((void*)0);
4043	#ifdef DEBUG_PUSH
4044	printf("end of input\n");
4045	#endif
4046	}
4047	} else {
4048	value = NULL((void*)0);
4049	data = NULL((void*)0);
4050	#ifdef DEBUG_PUSH
4051	printf("end of input\n");
4052	#endif
4053	}
4054	}
4055	goto progress;
4056	} else if (ret < 0) {
4057	exec->status = -4;
4058	break;
4059	}
4060	}
4061	if ((exec->transno != 0) \|\| (exec->state->nbTrans == 0)) {
4062	rollback:
4063	/*
4064	* if we didn't yet rollback on the current input
4065	* store the current state as the error state.
4066	*/
4067	if ((progress) && (exec->state != NULL((void*)0)) &&
4068	(exec->state->type != XML_REGEXP_SINK_STATE)) {
4069	progress = 0;
4070	if (exec->errString != NULL((void*)0))
4071	xmlFree(exec->errString);
4072	exec->errString = xmlStrdup(value);
4073	exec->errState = exec->state;
4074	memcpy(exec->errCounts, exec->counts,
4075	exec->comp->nbCounters * sizeof(int));
4076	}
4077
4078	/*
4079	* Failed to find a way out
4080	*/
4081	exec->determinist = 0;
4082	xmlFARegExecRollBack(exec);
4083	if (exec->status == 0) {
4084	value = exec->inputStack[exec->index].value;
4085	data = exec->inputStack[exec->index].data;
4086	#ifdef DEBUG_PUSH
4087	printf("value loaded: %s\n", value);
4088	#endif
4089	}
4090	}
4091	continue;
4092	progress:
4093	progress = 1;
4094	continue;
4095	}
4096	if (exec->status == 0) {
4097	return(exec->state->type == XML_REGEXP_FINAL_STATE);
4098	}
4099	#ifdef DEBUG_ERR
4100	if (exec->status < 0) {
4101	testerr(exec);
4102	}
4103	#endif
4104	return(exec->status);
4105	}
4106
4107	/**
4108	* xmlRegExecPushString:
4109	* @exec: a regexp execution context or NULL to indicate the end
4110	* @value: a string token input
4111	* @data: data associated to the token to reuse in callbacks
4112	*
4113	* Push one input token in the execution context
4114	*
4115	* Returns: 1 if the regexp reached a final state, 0 if non-final, and
4116	* a negative value in case of error.
4117	*/
4118	int
4119	xmlRegExecPushString(xmlRegExecCtxtPtr exec, const xmlChar *value,
4120	void *data) {
4121	return(xmlRegExecPushStringInternal(exec, value, data, 0));
4122	}
4123
4124	/**
4125	* xmlRegExecPushString2:
4126	* @exec: a regexp execution context or NULL to indicate the end
4127	* @value: the first string token input
4128	* @value2: the second string token input
4129	* @data: data associated to the token to reuse in callbacks
4130	*
4131	* Push one input token in the execution context
4132	*
4133	* Returns: 1 if the regexp reached a final state, 0 if non-final, and
4134	* a negative value in case of error.
4135	*/
4136	int
4137	xmlRegExecPushString2(xmlRegExecCtxtPtr exec, const xmlChar *value,
4138	const xmlChar value2, void data) {
4139	xmlChar buf[150];
4140	int lenn, lenp, ret;
4141	xmlChar *str;
4142
4143	if (exec == NULL((void*)0))
4144	return(-1);
4145	if (exec->comp == NULL((void*)0))
4146	return(-1);
4147	if (exec->status != 0)
4148	return(exec->status);
4149
4150	if (value2 == NULL((void*)0))
4151	return(xmlRegExecPushString(exec, value, data));
4152
4153	lenn = strlen((char *) value2);
4154	lenp = strlen((char *) value);
4155
4156	if (150 < lenn + lenp + 2) {
4157	str = (xmlChar *) xmlMallocAtomic(lenn + lenp + 2);
4158	if (str == NULL((void*)0)) {
4159	exec->status = -1;
4160	return(-1);
4161	}
4162	} else {
4163	str = buf;
4164	}
4165	memcpy(&str[0], value, lenp);
4166	str[lenp] = XML_REG_STRING_SEPARATOR'\|';
4167	memcpy(&str[lenp + 1], value2, lenn);
4168	str[lenn + lenp + 1] = 0;
4169
4170	if (exec->comp->compact != NULL((void*)0))
4171	ret = xmlRegCompactPushString(exec, exec->comp, str, data);
4172	else
4173	ret = xmlRegExecPushStringInternal(exec, str, data, 1);
4174
4175	if (str != buf)
4176	xmlFree(str);
4177	return(ret);
4178	}
4179
4180	/**
4181	* xmlRegExecGetValues:
4182	* @exec: a regexp execution context
4183	* @err: error extraction or normal one
4184	* @nbval: pointer to the number of accepted values IN/OUT
4185	* @nbneg: return number of negative transitions
4186	* @values: pointer to the array of acceptable values
4187	* @terminal: return value if this was a terminal state
4188	*
4189	* Extract informations from the regexp execution, internal routine to
4190	* implement xmlRegExecNextValues() and xmlRegExecErrInfo()
4191	*
4192	* Returns: 0 in case of success or -1 in case of error.
4193	*/
4194	static int
4195	xmlRegExecGetValues(xmlRegExecCtxtPtr exec, int err,
4196	int nbval, int nbneg,
4197	xmlChar *values, int terminal) {
4198	int maxval;
4199	int nb = 0;
4200
4201	if ((exec == NULL((void)0)) \|\| (nbval == NULL((void)0)) \|\| (nbneg == NULL((void*)0)) \|\|
4202	(values == NULL((void)0)) \|\| (nbval <= 0))
4203	return(-1);
4204
4205	maxval = *nbval;
4206	*nbval = 0;
4207	*nbneg = 0;
4208	if ((exec->comp != NULL((void)0)) && (exec->comp->compact != NULL((void)0))) {
4209	xmlRegexpPtr comp;
4210	int target, i, state;
4211
4212	comp = exec->comp;
4213
4214	if (err) {
4215	if (exec->errStateNo == -1) return(-1);
4216	state = exec->errStateNo;
4217	} else {
4218	state = exec->index;
4219	}
4220	if (terminal != NULL((void*)0)) {
4221	if (comp->compact[state * (comp->nbstrings + 1)] ==
4222	XML_REGEXP_FINAL_STATE)
4223	*terminal = 1;
4224	else
4225	*terminal = 0;
4226	}
4227	for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) {
4228	target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
4229	if ((target > 0) && (target <= comp->nbstates) &&
4230	(comp->compact[(target - 1) * (comp->nbstrings + 1)] !=
4231	XML_REGEXP_SINK_STATE)) {
4232	values[nb++] = comp->stringMap[i];
4233	(*nbval)++;
4234	}
4235	}
4236	for (i = 0;(i < comp->nbstrings) && (nb < maxval);i++) {
4237	target = comp->compact[state * (comp->nbstrings + 1) + i + 1];
4238	if ((target > 0) && (target <= comp->nbstates) &&
4239	(comp->compact[(target - 1) * (comp->nbstrings + 1)] ==
4240	XML_REGEXP_SINK_STATE)) {
4241	values[nb++] = comp->stringMap[i];
4242	(*nbneg)++;
4243	}
4244	}
4245	} else {
4246	int transno;
4247	xmlRegTransPtr trans;
4248	xmlRegAtomPtr atom;
4249	xmlRegStatePtr state;
4250
4251	if (terminal != NULL((void*)0)) {
4252	if (exec->state->type == XML_REGEXP_FINAL_STATE)
4253	*terminal = 1;
4254	else
4255	*terminal = 0;
4256	}
4257
4258	if (err) {
4259	if (exec->errState == NULL((void*)0)<