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