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