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