| /* |
| * regexp.c: generic and extensible Regular Expression engine |
| * |
| * Basically designed with the purpose of compiling regexps for |
| * the variety of validation/schemas mechanisms now available in |
| * XML related specifications these include: |
| * - XML-1.0 DTD validation |
| * - XML Schemas structure part 1 |
| * - XML Schemas Datatypes part 2 especially Appendix F |
| * - RELAX-NG/TREX i.e. the counter proposal |
| * |
| * See Copyright for the status of this software. |
| * |
| * Daniel Veillard <veillard@redhat.com> |
| */ |
| |
| #define IN_LIBXML |
| #include "libxml.h" |
| |
| #ifdef LIBXML_REGEXP_ENABLED |
| |
| /* #define DEBUG_ERR */ |
| |
| #include <stdio.h> |
| #include <string.h> |
| #ifdef HAVE_LIMITS_H |
| #include <limits.h> |
| #endif |
| #ifdef HAVE_STDINT_H |
| #include <stdint.h> |
| #endif |
| |
| #include <libxml/tree.h> |
| #include <libxml/parserInternals.h> |
| #include <libxml/xmlregexp.h> |
| #include <libxml/xmlautomata.h> |
| #include <libxml/xmlunicode.h> |
| |
| #ifndef INT_MAX |
| #define INT_MAX 123456789 /* easy to flag and big enough for our needs */ |
| #endif |
| #ifndef SIZE_MAX |
| #define SIZE_MAX ((size_t) -1) |
| #endif |
| |
| /* #define DEBUG_REGEXP_GRAPH */ |
| /* #define DEBUG_REGEXP_EXEC */ |
| /* #define DEBUG_PUSH */ |
| /* #define DEBUG_COMPACTION */ |
| |
| #define MAX_PUSH 10000000 |
| |
| #ifdef ERROR |
| #undef ERROR |
| #endif |
| #define ERROR(str) \ |
| ctxt->error = XML_REGEXP_COMPILE_ERROR; \ |
| xmlRegexpErrCompile(ctxt, str); |
| #define NEXT ctxt->cur++ |
| #define CUR (*(ctxt->cur)) |
| #define NXT(index) (ctxt->cur[index]) |
| |
| #define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l) |
| #define NEXTL(l) ctxt->cur += l; |
| #define XML_REG_STRING_SEPARATOR '|' |
| /* |
| * Need PREV to check on a '-' within a Character Group. May only be used |
| * when it's guaranteed that cur is not at the beginning of ctxt->string! |
| */ |
| #define PREV (ctxt->cur[-1]) |
| |
| /** |
| * TODO: |
| * |
| * macro to flag unimplemented blocks |
| */ |
| #define TODO \ |
| xmlGenericError(xmlGenericErrorContext, \ |
| "Unimplemented block at %s:%d\n", \ |
| __FILE__, __LINE__); |
| |
| /************************************************************************ |
| * * |
| * Datatypes and structures * |
| * * |
| ************************************************************************/ |
| |
| /* |
| * Note: the order of the enums below is significant, do not shuffle |
| */ |
| typedef enum { |
| XML_REGEXP_EPSILON = 1, |
| XML_REGEXP_CHARVAL, |
| XML_REGEXP_RANGES, |
| XML_REGEXP_SUBREG, /* used for () sub regexps */ |
| XML_REGEXP_STRING, |
| XML_REGEXP_ANYCHAR, /* . */ |
| XML_REGEXP_ANYSPACE, /* \s */ |
| XML_REGEXP_NOTSPACE, /* \S */ |
| XML_REGEXP_INITNAME, /* \l */ |
| XML_REGEXP_NOTINITNAME, /* \L */ |
| XML_REGEXP_NAMECHAR, /* \c */ |
| XML_REGEXP_NOTNAMECHAR, /* \C */ |
| XML_REGEXP_DECIMAL, /* \d */ |
| XML_REGEXP_NOTDECIMAL, /* \D */ |
| XML_REGEXP_REALCHAR, /* \w */ |
| XML_REGEXP_NOTREALCHAR, /* \W */ |
| XML_REGEXP_LETTER = 100, |
| XML_REGEXP_LETTER_UPPERCASE, |
| XML_REGEXP_LETTER_LOWERCASE, |
| XML_REGEXP_LETTER_TITLECASE, |
| XML_REGEXP_LETTER_MODIFIER, |
| XML_REGEXP_LETTER_OTHERS, |
| XML_REGEXP_MARK, |
| XML_REGEXP_MARK_NONSPACING, |
| XML_REGEXP_MARK_SPACECOMBINING, |
| XML_REGEXP_MARK_ENCLOSING, |
| XML_REGEXP_NUMBER, |
| XML_REGEXP_NUMBER_DECIMAL, |
| XML_REGEXP_NUMBER_LETTER, |
| XML_REGEXP_NUMBER_OTHERS, |
| XML_REGEXP_PUNCT, |
| XML_REGEXP_PUNCT_CONNECTOR, |
| XML_REGEXP_PUNCT_DASH, |
| XML_REGEXP_PUNCT_OPEN, |
| XML_REGEXP_PUNCT_CLOSE, |
| XML_REGEXP_PUNCT_INITQUOTE, |
| XML_REGEXP_PUNCT_FINQUOTE, |
| XML_REGEXP_PUNCT_OTHERS, |
| XML_REGEXP_SEPAR, |
| XML_REGEXP_SEPAR_SPACE, |
| XML_REGEXP_SEPAR_LINE, |
| XML_REGEXP_SEPAR_PARA, |
| XML_REGEXP_SYMBOL, |
| XML_REGEXP_SYMBOL_MATH, |
| XML_REGEXP_SYMBOL_CURRENCY, |
| XML_REGEXP_SYMBOL_MODIFIER, |
| XML_REGEXP_SYMBOL_OTHERS, |
| XML_REGEXP_OTHER, |
| XML_REGEXP_OTHER_CONTROL, |
| XML_REGEXP_OTHER_FORMAT, |
| XML_REGEXP_OTHER_PRIVATE, |
| XML_REGEXP_OTHER_NA, |
| XML_REGEXP_BLOCK_NAME |
| } xmlRegAtomType; |
| |
| typedef enum { |
| XML_REGEXP_QUANT_EPSILON = 1, |
| XML_REGEXP_QUANT_ONCE, |
| XML_REGEXP_QUANT_OPT, |
| XML_REGEXP_QUANT_MULT, |
| XML_REGEXP_QUANT_PLUS, |
| XML_REGEXP_QUANT_ONCEONLY, |
| XML_REGEXP_QUANT_ALL, |
| XML_REGEXP_QUANT_RANGE |
| } xmlRegQuantType; |
| |
| typedef enum { |
| XML_REGEXP_START_STATE = 1, |
| XML_REGEXP_FINAL_STATE, |
| XML_REGEXP_TRANS_STATE, |
| XML_REGEXP_SINK_STATE, |
| XML_REGEXP_UNREACH_STATE |
| } xmlRegStateType; |
| |
| typedef enum { |
| XML_REGEXP_MARK_NORMAL = 0, |
| XML_REGEXP_MARK_START, |
| XML_REGEXP_MARK_VISITED |
| } xmlRegMarkedType; |
| |
| typedef struct _xmlRegRange xmlRegRange; |
| typedef xmlRegRange *xmlRegRangePtr; |
| |
| struct _xmlRegRange { |
| int neg; /* 0 normal, 1 not, 2 exclude */ |
| xmlRegAtomType type; |
| int start; |
| int end; |
| xmlChar *blockName; |
| }; |
| |
| typedef struct _xmlRegAtom xmlRegAtom; |
| typedef xmlRegAtom *xmlRegAtomPtr; |
| |
| typedef struct _xmlAutomataState xmlRegState; |
| typedef xmlRegState *xmlRegStatePtr; |
| |
| struct _xmlRegAtom { |
| int no; |
| xmlRegAtomType type; |
| xmlRegQuantType quant; |
| int min; |
| int max; |
| |
| void *valuep; |
| void *valuep2; |
| int neg; |
| int codepoint; |
| xmlRegStatePtr start; |
| xmlRegStatePtr start0; |
| xmlRegStatePtr stop; |
| int maxRanges; |
| int nbRanges; |
| xmlRegRangePtr *ranges; |
| void *data; |
| }; |
| |
| typedef struct _xmlRegCounter xmlRegCounter; |
| typedef xmlRegCounter *xmlRegCounterPtr; |
| |
| struct _xmlRegCounter { |
| int min; |
| int max; |
| }; |
| |
| typedef struct _xmlRegTrans xmlRegTrans; |
| typedef xmlRegTrans *xmlRegTransPtr; |
| |
| struct _xmlRegTrans { |
| xmlRegAtomPtr atom; |
| int to; |
| int counter; |
| int count; |
| int nd; |
| }; |
| |
| struct _xmlAutomataState { |
| xmlRegStateType type; |
| xmlRegMarkedType mark; |
| xmlRegMarkedType markd; |
| xmlRegMarkedType reached; |
| int no; |
| int maxTrans; |
| int nbTrans; |
| xmlRegTrans *trans; |
| /* knowing states pointing to us can speed things up */ |
| int maxTransTo; |
| int nbTransTo; |
| int *transTo; |
| }; |
| |
| typedef struct _xmlAutomata xmlRegParserCtxt; |
| typedef xmlRegParserCtxt *xmlRegParserCtxtPtr; |
| |
| #define AM_AUTOMATA_RNG 1 |
| |
| struct _xmlAutomata { |
| xmlChar *string; |
| xmlChar *cur; |
| |
| int error; |
| int neg; |
| |
| xmlRegStatePtr start; |
| xmlRegStatePtr end; |
| xmlRegStatePtr state; |
| |
| xmlRegAtomPtr atom; |
| |
| int maxAtoms; |
| int nbAtoms; |
| xmlRegAtomPtr *atoms; |
| |
| int maxStates; |
| int nbStates; |
| xmlRegStatePtr *states; |
| |
| int maxCounters; |
| int nbCounters; |
| xmlRegCounter *counters; |
| |
| int determinist; |
| int negs; |
| int flags; |
| |
| int depth; |
| }; |
| |
| struct _xmlRegexp { |
| xmlChar *string; |
| int nbStates; |
| xmlRegStatePtr *states; |
| int nbAtoms; |
| xmlRegAtomPtr *atoms; |
| int nbCounters; |
| xmlRegCounter *counters; |
| int determinist; |
| int flags; |
| /* |
| * That's the compact form for determinists automatas |
| */ |
| int nbstates; |
| int *compact; |
| void **transdata; |
| int nbstrings; |
| xmlChar **stringMap; |
| }; |
| |
| typedef struct _xmlRegExecRollback xmlRegExecRollback; |
| typedef xmlRegExecRollback *xmlRegExecRollbackPtr; |
| |
| struct _xmlRegExecRollback { |
| xmlRegStatePtr state;/* the current state */ |
| int index; /* the index in the input stack */ |
| int nextbranch; /* the next transition to explore in that state */ |
| int *counts; /* save the automata state if it has some */ |
| }; |
| |
| typedef struct _xmlRegInputToken xmlRegInputToken; |
| typedef xmlRegInputToken *xmlRegInputTokenPtr; |
| |
| struct _xmlRegInputToken { |
| xmlChar *value; |
| void *data; |
| }; |
| |
| struct _xmlRegExecCtxt { |
| int status; /* execution status != 0 indicate an error */ |
| int determinist; /* did we find an indeterministic behaviour */ |
| xmlRegexpPtr comp; /* the compiled regexp */ |
| xmlRegExecCallbacks callback; |
| void *data; |
| |
| xmlRegStatePtr state;/* the current state */ |
| int transno; /* the current transition on that state */ |
| int transcount; /* the number of chars in char counted transitions */ |
| |
| /* |
| * A stack of rollback states |
| */ |
| int maxRollbacks; |
| int nbRollbacks; |
| xmlRegExecRollback *rollbacks; |
| |
| /* |
| * The state of the automata if any |
| */ |
| int *counts; |
| |
| /* |
| * The input stack |
| */ |
| int inputStackMax; |
| int inputStackNr; |
| int index; |
| int *charStack; |
| const xmlChar *inputString; /* when operating on characters */ |
| xmlRegInputTokenPtr inputStack;/* when operating on strings */ |
| |
| /* |
| * error handling |
| */ |
| int errStateNo; /* the error state number */ |
| xmlRegStatePtr errState; /* the error state */ |
| xmlChar *errString; /* the string raising the error */ |
| int *errCounts; /* counters at the error state */ |
| int nbPush; |
| }; |
| |
| #define REGEXP_ALL_COUNTER 0x123456 |
| #define REGEXP_ALL_LAX_COUNTER 0x123457 |
| |
| static void xmlFAParseRegExp(xmlRegParserCtxtPtr ctxt, int top); |
| static void xmlRegFreeState(xmlRegStatePtr state); |
| static void xmlRegFreeAtom(xmlRegAtomPtr atom); |
| static int xmlRegStrEqualWildcard(const xmlChar *expStr, const xmlChar *valStr); |
| static int xmlRegCheckCharacter(xmlRegAtomPtr atom, int codepoint); |
| static int xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, |
| int neg, int start, int end, const xmlChar *blockName); |
| |
| void xmlAutomataSetFlags(xmlAutomataPtr am, int flags); |
| |
| /************************************************************************ |
| * * |
| * Regexp memory error handler * |
| * * |
| ************************************************************************/ |
| /** |
| * xmlRegexpErrMemory: |
| * @extra: extra information |
| * |
| * Handle an out of memory condition |
| */ |
| static void |
| xmlRegexpErrMemory(xmlRegParserCtxtPtr ctxt, const char *extra) |
| { |
| const char *regexp = NULL; |
| if (ctxt != NULL) { |
| regexp = (const char *) ctxt->string; |
| ctxt->error = XML_ERR_NO_MEMORY; |
| } |
| __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP, |
| XML_ERR_NO_MEMORY, XML_ERR_FATAL, NULL, 0, extra, |
| regexp, NULL, 0, 0, |
| "Memory allocation failed : %s\n", extra); |
| } |
| |
| /** |
| * xmlRegexpErrCompile: |
| * @extra: extra information |
| * |
| * Handle a compilation failure |
| */ |
| static void |
| xmlRegexpErrCompile(xmlRegParserCtxtPtr ctxt, const char *extra) |
| { |
| const char *regexp = NULL; |
| int idx = 0; |
| |
| if (ctxt != NULL) { |
| regexp = (const char *) ctxt->string; |
| idx = ctxt->cur - ctxt->string; |
| ctxt->error = XML_REGEXP_COMPILE_ERROR; |
| } |
| __xmlRaiseError(NULL, NULL, NULL, NULL, NULL, XML_FROM_REGEXP, |
| XML_REGEXP_COMPILE_ERROR, XML_ERR_FATAL, NULL, 0, extra, |
| regexp, NULL, idx, 0, |
| "failed to compile: %s\n", extra); |
| } |
| |
| /************************************************************************ |
| * * |
| * Allocation/Deallocation * |
| * * |
| ************************************************************************/ |
| |
| static int xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt); |
| |
| /** |
| * xmlRegCalloc2: |
| * @dim1: size of first dimension |
| * @dim2: size of second dimension |
| * @elemSize: size of element |
| * |
| * Allocate a two-dimensional array and set all elements to zero. |
| * |
| * Returns the new array or NULL in case of error. |
| */ |
| static void* |
| xmlRegCalloc2(size_t dim1, size_t dim2, size_t elemSize) { |
| size_t totalSize; |
| void *ret; |
| |
| /* Check for overflow */ |
| if (dim1 > SIZE_MAX / dim2 / elemSize) |
| return (NULL); |
| totalSize = dim1 * dim2 * elemSize; |
| ret = xmlMalloc(totalSize); |
| if (ret != NULL) |
| memset(ret, 0, totalSize); |
| return (ret); |
| } |
| |
| /** |
| * xmlRegEpxFromParse: |
| * @ctxt: the parser context used to build it |
| * |
| * Allocate a new regexp and fill it with the result from the parser |
| * |
| * Returns the new regexp or NULL in case of error |
| */ |
| static xmlRegexpPtr |
| xmlRegEpxFromParse(xmlRegParserCtxtPtr ctxt) { |
| xmlRegexpPtr ret; |
| |
| ret = (xmlRegexpPtr) xmlMalloc(sizeof(xmlRegexp)); |
| if (ret == NULL) { |
| xmlRegexpErrMemory(ctxt, "compiling regexp"); |
| return(NULL); |
| } |
| memset(ret, 0, sizeof(xmlRegexp)); |
| ret->string = ctxt->string; |
| ret->nbStates = ctxt->nbStates; |
| ret->states = ctxt->states; |
| ret->nbAtoms = ctxt->nbAtoms; |
| ret->atoms = ctxt->atoms; |
| ret->nbCounters = ctxt->nbCounters; |
| ret->counters = ctxt->counters; |
| ret->determinist = ctxt->determinist; |
| ret->flags = ctxt->flags; |
| if (ret->determinist == -1) { |
| xmlRegexpIsDeterminist(ret); |
| } |
| |
| if ((ret->determinist != 0) && |
| (ret->nbCounters == 0) && |
| (ctxt->negs == 0) && |
| (ret->atoms != NULL) && |
| (ret->atoms[0] != NULL) && |
| (ret->atoms[0]->type == XML_REGEXP_STRING)) { |
| int i, j, nbstates = 0, nbatoms = 0; |
| int *stateRemap; |
| int *stringRemap; |
| int *transitions; |
| void **transdata; |
| xmlChar **stringMap; |
| xmlChar *value; |
| |
| /* |
| * Switch to a compact representation |
| * 1/ counting the effective number of states left |
| * 2/ counting the unique number of atoms, and check that |
| * they are all of the string type |
| * 3/ build a table state x atom for the transitions |
| */ |
| |
| stateRemap = xmlMalloc(ret->nbStates * sizeof(int)); |
| if (stateRemap == NULL) { |
| xmlRegexpErrMemory(ctxt, "compiling regexp"); |
| xmlFree(ret); |
| return(NULL); |
| } |
| for (i = 0;i < ret->nbStates;i++) { |
| if (ret->states[i] != NULL) { |
| stateRemap[i] = nbstates; |
| nbstates++; |
| } else { |
| stateRemap[i] = -1; |
| } |
| } |
| #ifdef DEBUG_COMPACTION |
| printf("Final: %d states\n", nbstates); |
| #endif |
| stringMap = xmlMalloc(ret->nbAtoms * sizeof(char *)); |
| if (stringMap == NULL) { |
| xmlRegexpErrMemory(ctxt, "compiling regexp"); |
| xmlFree(stateRemap); |
| xmlFree(ret); |
| return(NULL); |
| } |
| stringRemap = xmlMalloc(ret->nbAtoms * sizeof(int)); |
| if (stringRemap == NULL) { |
| xmlRegexpErrMemory(ctxt, "compiling regexp"); |
| xmlFree(stringMap); |
| xmlFree(stateRemap); |
| xmlFree(ret); |
| return(NULL); |
| } |
| for (i = 0;i < ret->nbAtoms;i++) { |
| if ((ret->atoms[i]->type == XML_REGEXP_STRING) && |
| (ret->atoms[i]->quant == XML_REGEXP_QUANT_ONCE)) { |
| value = ret->atoms[i]->valuep; |
| for (j = 0;j < nbatoms;j++) { |
| if (xmlStrEqual(stringMap[j], value)) { |
| stringRemap[i] = j; |
| break; |
| } |
| } |
| if (j >= nbatoms) { |
| stringRemap[i] = nbatoms; |
| stringMap[nbatoms] = xmlStrdup(value); |
| if (stringMap[nbatoms] == NULL) { |
| for (i = 0;i < nbatoms;i++) |
| xmlFree(stringMap[i]); |
| xmlFree(stringRemap); |
| xmlFree(stringMap); |
| xmlFree(stateRemap); |
| xmlFree(ret); |
| return(NULL); |
| } |
| nbatoms++; |
| } |
| } else { |
| xmlFree(stateRemap); |
| xmlFree(stringRemap); |
| for (i = 0;i < nbatoms;i++) |
| xmlFree(stringMap[i]); |
| xmlFree(stringMap); |
| xmlFree(ret); |
| return(NULL); |
| } |
| } |
| #ifdef DEBUG_COMPACTION |
| printf("Final: %d atoms\n", nbatoms); |
| #endif |
| transitions = (int *) xmlRegCalloc2(nbstates + 1, nbatoms + 1, |
| sizeof(int)); |
| if (transitions == NULL) { |
| xmlFree(stateRemap); |
| xmlFree(stringRemap); |
| for (i = 0;i < nbatoms;i++) |
| xmlFree(stringMap[i]); |
| xmlFree(stringMap); |
| xmlFree(ret); |
| return(NULL); |
| } |
| |
| /* |
| * Allocate the transition table. The first entry for each |
| * state corresponds to the state type. |
| */ |
| transdata = NULL; |
| |
| for (i = 0;i < ret->nbStates;i++) { |
| int stateno, atomno, targetno, prev; |
| xmlRegStatePtr state; |
| xmlRegTransPtr trans; |
| |
| stateno = stateRemap[i]; |
| if (stateno == -1) |
| continue; |
| state = ret->states[i]; |
| |
| transitions[stateno * (nbatoms + 1)] = state->type; |
| |
| for (j = 0;j < state->nbTrans;j++) { |
| trans = &(state->trans[j]); |
| if ((trans->to == -1) || (trans->atom == NULL)) |
| continue; |
| atomno = stringRemap[trans->atom->no]; |
| if ((trans->atom->data != NULL) && (transdata == NULL)) { |
| transdata = (void **) xmlRegCalloc2(nbstates, nbatoms, |
| sizeof(void *)); |
| if (transdata == NULL) { |
| xmlRegexpErrMemory(ctxt, "compiling regexp"); |
| break; |
| } |
| } |
| targetno = stateRemap[trans->to]; |
| /* |
| * if the same atom can generate transitions to 2 different |
| * states then it means the automata is not deterministic and |
| * the compact form can't be used ! |
| */ |
| prev = transitions[stateno * (nbatoms + 1) + atomno + 1]; |
| if (prev != 0) { |
| if (prev != targetno + 1) { |
| ret->determinist = 0; |
| #ifdef DEBUG_COMPACTION |
| printf("Indet: state %d trans %d, atom %d to %d : %d to %d\n", |
| i, j, trans->atom->no, trans->to, atomno, targetno); |
| printf(" previous to is %d\n", prev); |
| #endif |
| if (transdata != NULL) |
| xmlFree(transdata); |
| xmlFree(transitions); |
| xmlFree(stateRemap); |
| xmlFree(stringRemap); |
| for (i = 0;i < nbatoms;i++) |
| xmlFree(stringMap[i]); |
| xmlFree(stringMap); |
| goto not_determ; |
| } |
| } else { |
| #if 0 |
| printf("State %d trans %d: atom %d to %d : %d to %d\n", |
| i, j, trans->atom->no, trans->to, atomno, targetno); |
| #endif |
| transitions[stateno * (nbatoms + 1) + atomno + 1] = |
| targetno + 1; /* to avoid 0 */ |
| if (transdata != NULL) |
| transdata[stateno * nbatoms + atomno] = |
| trans->atom->data; |
| } |
| } |
| } |
| ret->determinist = 1; |
| #ifdef DEBUG_COMPACTION |
| /* |
| * Debug |
| */ |
| for (i = 0;i < nbstates;i++) { |
| for (j = 0;j < nbatoms + 1;j++) { |
| printf("%02d ", transitions[i * (nbatoms + 1) + j]); |
| } |
| printf("\n"); |
| } |
| printf("\n"); |
| #endif |
| /* |
| * Cleanup of the old data |
| */ |
| if (ret->states != NULL) { |
| for (i = 0;i < ret->nbStates;i++) |
| xmlRegFreeState(ret->states[i]); |
| xmlFree(ret->states); |
| } |
| ret->states = NULL; |
| ret->nbStates = 0; |
| if (ret->atoms != NULL) { |
| for (i = 0;i < ret->nbAtoms;i++) |
| xmlRegFreeAtom(ret->atoms[i]); |
| xmlFree(ret->atoms); |
| } |
| ret->atoms = NULL; |
| ret->nbAtoms = 0; |
| |
| ret->compact = transitions; |
| ret->transdata = transdata; |
| ret->stringMap = stringMap; |
| ret->nbstrings = nbatoms; |
| ret->nbstates = nbstates; |
| xmlFree(stateRemap); |
| xmlFree(stringRemap); |
| } |
| not_determ: |
| ctxt->string = NULL; |
| ctxt->nbStates = 0; |
| ctxt->states = NULL; |
| ctxt->nbAtoms = 0; |
| ctxt->atoms = NULL; |
| ctxt->nbCounters = 0; |
| ctxt->counters = NULL; |
| return(ret); |
| } |
| |
| /** |
| * xmlRegNewParserCtxt: |
| * @string: the string to parse |
| * |
| * Allocate a new regexp parser context |
| * |
| * Returns the new context or NULL in case of error |
| */ |
| static xmlRegParserCtxtPtr |
| xmlRegNewParserCtxt(const xmlChar *string) { |
| xmlRegParserCtxtPtr ret; |
| |
| ret = (xmlRegParserCtxtPtr) xmlMalloc(sizeof(xmlRegParserCtxt)); |
| if (ret == NULL) |
| return(NULL); |
| memset(ret, 0, sizeof(xmlRegParserCtxt)); |
| if (string != NULL) |
| ret->string = xmlStrdup(string); |
| ret->cur = ret->string; |
| ret->neg = 0; |
| ret->negs = 0; |
| ret->error = 0; |
| ret->determinist = -1; |
| return(ret); |
| } |
| |
| /** |
| * xmlRegNewRange: |
| * @ctxt: the regexp parser context |
| * @neg: is that negative |
| * @type: the type of range |
| * @start: the start codepoint |
| * @end: the end codepoint |
| * |
| * Allocate a new regexp range |
| * |
| * Returns the new range or NULL in case of error |
| */ |
| static xmlRegRangePtr |
| xmlRegNewRange(xmlRegParserCtxtPtr ctxt, |
| int neg, xmlRegAtomType type, int start, int end) { |
| xmlRegRangePtr ret; |
| |
| ret = (xmlRegRangePtr) xmlMalloc(sizeof(xmlRegRange)); |
| if (ret == NULL) { |
| xmlRegexpErrMemory(ctxt, "allocating range"); |
| return(NULL); |
| } |
| ret->neg = neg; |
| ret->type = type; |
| ret->start = start; |
| ret->end = end; |
| return(ret); |
| } |
| |
| /** |
| * xmlRegFreeRange: |
| * @range: the regexp range |
| * |
| * Free a regexp range |
| */ |
| static void |
| xmlRegFreeRange(xmlRegRangePtr range) { |
| if (range == NULL) |
| return; |
| |
| if (range->blockName != NULL) |
| xmlFree(range->blockName); |
| xmlFree(range); |
| } |
| |
| /** |
| * xmlRegCopyRange: |
| * @range: the regexp range |
| * |
| * Copy a regexp range |
| * |
| * Returns the new copy or NULL in case of error. |
| */ |
| static xmlRegRangePtr |
| xmlRegCopyRange(xmlRegParserCtxtPtr ctxt, xmlRegRangePtr range) { |
| xmlRegRangePtr ret; |
| |
| if (range == NULL) |
| return(NULL); |
| |
| ret = xmlRegNewRange(ctxt, range->neg, range->type, range->start, |
| range->end); |
| if (ret == NULL) |
| return(NULL); |
| if (range->blockName != NULL) { |
| ret->blockName = xmlStrdup(range->blockName); |
| if (ret->blockName == NULL) { |
| xmlRegexpErrMemory(ctxt, "allocating range"); |
| xmlRegFreeRange(ret); |
| return(NULL); |
| } |
| } |
| return(ret); |
| } |
| |
| /** |
| * xmlRegNewAtom: |
| * @ctxt: the regexp parser context |
| * @type: the type of atom |
| * |
| * Allocate a new atom |
| * |
| * Returns the new atom or NULL in case of error |
| */ |
| static xmlRegAtomPtr |
| xmlRegNewAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomType type) { |
| xmlRegAtomPtr ret; |
| |
| ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom)); |
| if (ret == NULL) { |
| xmlRegexpErrMemory(ctxt, "allocating atom"); |
| return(NULL); |
| } |
| memset(ret, 0, sizeof(xmlRegAtom)); |
| ret->type = type; |
| ret->quant = XML_REGEXP_QUANT_ONCE; |
| ret->min = 0; |
| ret->max = 0; |
| return(ret); |
| } |
| |
| /** |
| * xmlRegFreeAtom: |
| * @atom: the regexp atom |
| * |
| * Free a regexp atom |
| */ |
| static void |
| xmlRegFreeAtom(xmlRegAtomPtr atom) { |
| int i; |
| |
| if (atom == NULL) |
| return; |
| |
| for (i = 0;i < atom->nbRanges;i++) |
| xmlRegFreeRange(atom->ranges[i]); |
| if (atom->ranges != NULL) |
| xmlFree(atom->ranges); |
| if ((atom->type == XML_REGEXP_STRING) && (atom->valuep != NULL)) |
| xmlFree(atom->valuep); |
| if ((atom->type == XML_REGEXP_STRING) && (atom->valuep2 != NULL)) |
| xmlFree(atom->valuep2); |
| if ((atom->type == XML_REGEXP_BLOCK_NAME) && (atom->valuep != NULL)) |
| xmlFree(atom->valuep); |
| xmlFree(atom); |
| } |
| |
| /** |
| * xmlRegCopyAtom: |
| * @ctxt: the regexp parser context |
| * @atom: the original atom |
| * |
| * Allocate a new regexp range |
| * |
| * Returns the new atom or NULL in case of error |
| */ |
| static xmlRegAtomPtr |
| xmlRegCopyAtom(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) { |
| xmlRegAtomPtr ret; |
| |
| ret = (xmlRegAtomPtr) xmlMalloc(sizeof(xmlRegAtom)); |
| if (ret == NULL) { |
| xmlRegexpErrMemory(ctxt, "copying atom"); |
| return(NULL); |
| } |
| memset(ret, 0, sizeof(xmlRegAtom)); |
| ret->type = atom->type; |
| ret->quant = atom->quant; |
| ret->min = atom->min; |
| ret->max = atom->max; |
| if (atom->nbRanges > 0) { |
| int i; |
| |
| ret->ranges = (xmlRegRangePtr *) xmlMalloc(sizeof(xmlRegRangePtr) * |
| atom->nbRanges); |
| if (ret->ranges == NULL) { |
| xmlRegexpErrMemory(ctxt, "copying atom"); |
| goto error; |
| } |
| for (i = 0;i < atom->nbRanges;i++) { |
| ret->ranges[i] = xmlRegCopyRange(ctxt, atom->ranges[i]); |
| if (ret->ranges[i] == NULL) |
| goto error; |
| ret->nbRanges = i + 1; |
| } |
| } |
| return(ret); |
| |
| error: |
| xmlRegFreeAtom(ret); |
| return(NULL); |
| } |
| |
| static xmlRegStatePtr |
| xmlRegNewState(xmlRegParserCtxtPtr ctxt) { |
| xmlRegStatePtr ret; |
| |
| ret = (xmlRegStatePtr) xmlMalloc(sizeof(xmlRegState)); |
| if (ret == NULL) { |
| xmlRegexpErrMemory(ctxt, "allocating state"); |
| return(NULL); |
| } |
| memset(ret, 0, sizeof(xmlRegState)); |
| ret->type = XML_REGEXP_TRANS_STATE; |
| ret->mark = XML_REGEXP_MARK_NORMAL; |
| return(ret); |
| } |
| |
| /** |
| * xmlRegFreeState: |
| * @state: the regexp state |
| * |
| * Free a regexp state |
| */ |
| static void |
| xmlRegFreeState(xmlRegStatePtr state) { |
| if (state == NULL) |
| return; |
| |
| if (state->trans != NULL) |
| xmlFree(state->trans); |
| if (state->transTo != NULL) |
| xmlFree(state->transTo); |
| xmlFree(state); |
| } |
| |
| /** |
| * xmlRegFreeParserCtxt: |
| * @ctxt: the regexp parser context |
| * |
| * Free a regexp parser context |
| */ |
| static void |
| xmlRegFreeParserCtxt(xmlRegParserCtxtPtr ctxt) { |
| int i; |
| if (ctxt == NULL) |
| return; |
| |
| if (ctxt->string != NULL) |
| xmlFree(ctxt->string); |
| if (ctxt->states != NULL) { |
| for (i = 0;i < ctxt->nbStates;i++) |
| xmlRegFreeState(ctxt->states[i]); |
| xmlFree(ctxt->states); |
| } |
| if (ctxt->atoms != NULL) { |
| for (i = 0;i < ctxt->nbAtoms;i++) |
| xmlRegFreeAtom(ctxt->atoms[i]); |
| xmlFree(ctxt->atoms); |
| } |
| if (ctxt->counters != NULL) |
| xmlFree(ctxt->counters); |
| xmlFree(ctxt); |
| } |
| |
| /************************************************************************ |
| * * |
| * Display of Data structures * |
| * * |
| ************************************************************************/ |
| |
| static void |
| xmlRegPrintAtomType(FILE *output, xmlRegAtomType type) { |
| switch (type) { |
| case XML_REGEXP_EPSILON: |
| fprintf(output, "epsilon "); break; |
| case XML_REGEXP_CHARVAL: |
| fprintf(output, "charval "); break; |
| case XML_REGEXP_RANGES: |
| fprintf(output, "ranges "); break; |
| case XML_REGEXP_SUBREG: |
| fprintf(output, "subexpr "); break; |
| case XML_REGEXP_STRING: |
| fprintf(output, "string "); break; |
| case XML_REGEXP_ANYCHAR: |
| fprintf(output, "anychar "); break; |
| case XML_REGEXP_ANYSPACE: |
| fprintf(output, "anyspace "); break; |
| case XML_REGEXP_NOTSPACE: |
| fprintf(output, "notspace "); break; |
| case XML_REGEXP_INITNAME: |
| fprintf(output, "initname "); break; |
| case XML_REGEXP_NOTINITNAME: |
| fprintf(output, "notinitname "); break; |
| case XML_REGEXP_NAMECHAR: |
| fprintf(output, "namechar "); break; |
| case XML_REGEXP_NOTNAMECHAR: |
| fprintf(output, "notnamechar "); break; |
| case XML_REGEXP_DECIMAL: |
| fprintf(output, "decimal "); break; |
| case XML_REGEXP_NOTDECIMAL: |
| fprintf(output, "notdecimal "); break; |
| case XML_REGEXP_REALCHAR: |
| fprintf(output, "realchar "); break; |
| case XML_REGEXP_NOTREALCHAR: |
| fprintf(output, "notrealchar "); break; |
| case XML_REGEXP_LETTER: |
| fprintf(output, "LETTER "); break; |
| case XML_REGEXP_LETTER_UPPERCASE: |
| fprintf(output, "LETTER_UPPERCASE "); break; |
| case XML_REGEXP_LETTER_LOWERCASE: |
| fprintf(output, "LETTER_LOWERCASE "); break; |
| case XML_REGEXP_LETTER_TITLECASE: |
| fprintf(output, "LETTER_TITLECASE "); break; |
| case XML_REGEXP_LETTER_MODIFIER: |
| fprintf(output, "LETTER_MODIFIER "); break; |
| case XML_REGEXP_LETTER_OTHERS: |
| fprintf(output, "LETTER_OTHERS "); break; |
| case XML_REGEXP_MARK: |
| fprintf(output, "MARK "); break; |
| case XML_REGEXP_MARK_NONSPACING: |
| fprintf(output, "MARK_NONSPACING "); break; |
| case XML_REGEXP_MARK_SPACECOMBINING: |
| fprintf(output, "MARK_SPACECOMBINING "); break; |
| case XML_REGEXP_MARK_ENCLOSING: |
| fprintf(output, "MARK_ENCLOSING "); break; |
| case XML_REGEXP_NUMBER: |
| fprintf(output, "NUMBER "); break; |
| case XML_REGEXP_NUMBER_DECIMAL: |
| fprintf(output, "NUMBER_DECIMAL "); break; |
| case XML_REGEXP_NUMBER_LETTER: |
| fprintf(output, "NUMBER_LETTER "); break; |
| case XML_REGEXP_NUMBER_OTHERS: |
| fprintf(output, "NUMBER_OTHERS "); break; |
| case XML_REGEXP_PUNCT: |
| fprintf(output, "PUNCT "); break; |
| case XML_REGEXP_PUNCT_CONNECTOR: |
| fprintf(output, "PUNCT_CONNECTOR "); break; |
| case XML_REGEXP_PUNCT_DASH: |
| fprintf(output, "PUNCT_DASH "); break; |
| case XML_REGEXP_PUNCT_OPEN: |
| fprintf(output, "PUNCT_OPEN "); break; |
| case XML_REGEXP_PUNCT_CLOSE: |
| fprintf(output, "PUNCT_CLOSE "); break; |
| case XML_REGEXP_PUNCT_INITQUOTE: |
| fprintf(output, "PUNCT_INITQUOTE "); break; |
| case XML_REGEXP_PUNCT_FINQUOTE: |
| fprintf(output, "PUNCT_FINQUOTE "); break; |
| case XML_REGEXP_PUNCT_OTHERS: |
| fprintf(output, "PUNCT_OTHERS "); break; |
| case XML_REGEXP_SEPAR: |
| fprintf(output, "SEPAR "); break; |
| case XML_REGEXP_SEPAR_SPACE: |
| fprintf(output, "SEPAR_SPACE "); break; |
| case XML_REGEXP_SEPAR_LINE: |
| fprintf(output, "SEPAR_LINE "); break; |
| case XML_REGEXP_SEPAR_PARA: |
| fprintf(output, "SEPAR_PARA "); break; |
| case XML_REGEXP_SYMBOL: |
| fprintf(output, "SYMBOL "); break; |
| case XML_REGEXP_SYMBOL_MATH: |
| fprintf(output, "SYMBOL_MATH "); break; |
| case XML_REGEXP_SYMBOL_CURRENCY: |
| fprintf(output, "SYMBOL_CURRENCY "); break; |
| case XML_REGEXP_SYMBOL_MODIFIER: |
| fprintf(output, "SYMBOL_MODIFIER "); break; |
| case XML_REGEXP_SYMBOL_OTHERS: |
| fprintf(output, "SYMBOL_OTHERS "); break; |
| case XML_REGEXP_OTHER: |
| fprintf(output, "OTHER "); break; |
| case XML_REGEXP_OTHER_CONTROL: |
| fprintf(output, "OTHER_CONTROL "); break; |
| case XML_REGEXP_OTHER_FORMAT: |
| fprintf(output, "OTHER_FORMAT "); break; |
| case XML_REGEXP_OTHER_PRIVATE: |
| fprintf(output, "OTHER_PRIVATE "); break; |
| case XML_REGEXP_OTHER_NA: |
| fprintf(output, "OTHER_NA "); break; |
| case XML_REGEXP_BLOCK_NAME: |
| fprintf(output, "BLOCK "); break; |
| } |
| } |
| |
| static void |
| xmlRegPrintQuantType(FILE *output, xmlRegQuantType type) { |
| switch (type) { |
| case XML_REGEXP_QUANT_EPSILON: |
| fprintf(output, "epsilon "); break; |
| case XML_REGEXP_QUANT_ONCE: |
| fprintf(output, "once "); break; |
| case XML_REGEXP_QUANT_OPT: |
| fprintf(output, "? "); break; |
| case XML_REGEXP_QUANT_MULT: |
| fprintf(output, "* "); break; |
| case XML_REGEXP_QUANT_PLUS: |
| fprintf(output, "+ "); break; |
| case XML_REGEXP_QUANT_RANGE: |
| fprintf(output, "range "); break; |
| case XML_REGEXP_QUANT_ONCEONLY: |
| fprintf(output, "onceonly "); break; |
| case XML_REGEXP_QUANT_ALL: |
| fprintf(output, "all "); break; |
| } |
| } |
| static void |
| xmlRegPrintRange(FILE *output, xmlRegRangePtr range) { |
| fprintf(output, " range: "); |
| if (range->neg) |
| fprintf(output, "negative "); |
| xmlRegPrintAtomType(output, range->type); |
| fprintf(output, "%c - %c\n", range->start, range->end); |
| } |
| |
| static void |
| xmlRegPrintAtom(FILE *output, xmlRegAtomPtr atom) { |
| fprintf(output, " atom: "); |
| if (atom == NULL) { |
| fprintf(output, "NULL\n"); |
| return; |
| } |
| if (atom->neg) |
| fprintf(output, "not "); |
| xmlRegPrintAtomType(output, atom->type); |
| xmlRegPrintQuantType(output, atom->quant); |
| if (atom->quant == XML_REGEXP_QUANT_RANGE) |
| fprintf(output, "%d-%d ", atom->min, atom->max); |
| if (atom->type == XML_REGEXP_STRING) |
| fprintf(output, "'%s' ", (char *) atom->valuep); |
| if (atom->type == XML_REGEXP_CHARVAL) |
| fprintf(output, "char %c\n", atom->codepoint); |
| else if (atom->type == XML_REGEXP_RANGES) { |
| int i; |
| fprintf(output, "%d entries\n", atom->nbRanges); |
| for (i = 0; i < atom->nbRanges;i++) |
| xmlRegPrintRange(output, atom->ranges[i]); |
| } else if (atom->type == XML_REGEXP_SUBREG) { |
| fprintf(output, "start %d end %d\n", atom->start->no, atom->stop->no); |
| } else { |
| fprintf(output, "\n"); |
| } |
| } |
| |
| static void |
| xmlRegPrintTrans(FILE *output, xmlRegTransPtr trans) { |
| fprintf(output, " trans: "); |
| if (trans == NULL) { |
| fprintf(output, "NULL\n"); |
| return; |
| } |
| if (trans->to < 0) { |
| fprintf(output, "removed\n"); |
| return; |
| } |
| if (trans->nd != 0) { |
| if (trans->nd == 2) |
| fprintf(output, "last not determinist, "); |
| else |
| fprintf(output, "not determinist, "); |
| } |
| if (trans->counter >= 0) { |
| fprintf(output, "counted %d, ", trans->counter); |
| } |
| if (trans->count == REGEXP_ALL_COUNTER) { |
| fprintf(output, "all transition, "); |
| } else if (trans->count >= 0) { |
| fprintf(output, "count based %d, ", trans->count); |
| } |
| if (trans->atom == NULL) { |
| fprintf(output, "epsilon to %d\n", trans->to); |
| return; |
| } |
| if (trans->atom->type == XML_REGEXP_CHARVAL) |
| fprintf(output, "char %c ", trans->atom->codepoint); |
| fprintf(output, "atom %d, to %d\n", trans->atom->no, trans->to); |
| } |
| |
| static void |
| xmlRegPrintState(FILE *output, xmlRegStatePtr state) { |
| int i; |
| |
| fprintf(output, " state: "); |
| if (state == NULL) { |
| fprintf(output, "NULL\n"); |
| return; |
| } |
| if (state->type == XML_REGEXP_START_STATE) |
| fprintf(output, "START "); |
| if (state->type == XML_REGEXP_FINAL_STATE) |
| fprintf(output, "FINAL "); |
| |
| fprintf(output, "%d, %d transitions:\n", state->no, state->nbTrans); |
| for (i = 0;i < state->nbTrans; i++) { |
| xmlRegPrintTrans(output, &(state->trans[i])); |
| } |
| } |
| |
| #ifdef DEBUG_REGEXP_GRAPH |
| static void |
| xmlRegPrintCtxt(FILE *output, xmlRegParserCtxtPtr ctxt) { |
| int i; |
| |
| fprintf(output, " ctxt: "); |
| if (ctxt == NULL) { |
| fprintf(output, "NULL\n"); |
| return; |
| } |
| fprintf(output, "'%s' ", ctxt->string); |
| if (ctxt->error) |
| fprintf(output, "error "); |
| if (ctxt->neg) |
| fprintf(output, "neg "); |
| fprintf(output, "\n"); |
| fprintf(output, "%d atoms:\n", ctxt->nbAtoms); |
| for (i = 0;i < ctxt->nbAtoms; i++) { |
| fprintf(output, " %02d ", i); |
| xmlRegPrintAtom(output, ctxt->atoms[i]); |
| } |
| if (ctxt->atom != NULL) { |
| fprintf(output, "current atom:\n"); |
| xmlRegPrintAtom(output, ctxt->atom); |
| } |
| fprintf(output, "%d states:", ctxt->nbStates); |
| if (ctxt->start != NULL) |
| fprintf(output, " start: %d", ctxt->start->no); |
| if (ctxt->end != NULL) |
| fprintf(output, " end: %d", ctxt->end->no); |
| fprintf(output, "\n"); |
| for (i = 0;i < ctxt->nbStates; i++) { |
| xmlRegPrintState(output, ctxt->states[i]); |
| } |
| fprintf(output, "%d counters:\n", ctxt->nbCounters); |
| for (i = 0;i < ctxt->nbCounters; i++) { |
| fprintf(output, " %d: min %d max %d\n", i, ctxt->counters[i].min, |
| ctxt->counters[i].max); |
| } |
| } |
| #endif |
| |
| /************************************************************************ |
| * * |
| * Finite Automata structures manipulations * |
| * * |
| ************************************************************************/ |
| |
| static void |
| xmlRegAtomAddRange(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom, |
| int neg, xmlRegAtomType type, int start, int end, |
| xmlChar *blockName) { |
| xmlRegRangePtr range; |
| |
| if (atom == NULL) { |
| ERROR("add range: atom is NULL"); |
| return; |
| } |
| if (atom->type != XML_REGEXP_RANGES) { |
| ERROR("add range: atom is not ranges"); |
| return; |
| } |
| if (atom->maxRanges == 0) { |
| atom->maxRanges = 4; |
| atom->ranges = (xmlRegRangePtr *) xmlMalloc(atom->maxRanges * |
| sizeof(xmlRegRangePtr)); |
| if (atom->ranges == NULL) { |
| xmlRegexpErrMemory(ctxt, "adding ranges"); |
| atom->maxRanges = 0; |
| return; |
| } |
| } else if (atom->nbRanges >= atom->maxRanges) { |
| xmlRegRangePtr *tmp; |
| atom->maxRanges *= 2; |
| tmp = (xmlRegRangePtr *) xmlRealloc(atom->ranges, atom->maxRanges * |
| sizeof(xmlRegRangePtr)); |
| if (tmp == NULL) { |
| xmlRegexpErrMemory(ctxt, "adding ranges"); |
| atom->maxRanges /= 2; |
| return; |
| } |
| atom->ranges = tmp; |
| } |
| range = xmlRegNewRange(ctxt, neg, type, start, end); |
| if (range == NULL) |
| return; |
| range->blockName = blockName; |
| atom->ranges[atom->nbRanges++] = range; |
| |
| } |
| |
| static int |
| xmlRegGetCounter(xmlRegParserCtxtPtr ctxt) { |
| if (ctxt->maxCounters == 0) { |
| ctxt->maxCounters = 4; |
| ctxt->counters = (xmlRegCounter *) xmlMalloc(ctxt->maxCounters * |
| sizeof(xmlRegCounter)); |
| if (ctxt->counters == NULL) { |
| xmlRegexpErrMemory(ctxt, "allocating counter"); |
| ctxt->maxCounters = 0; |
| return(-1); |
| } |
| } else if (ctxt->nbCounters >= ctxt->maxCounters) { |
| xmlRegCounter *tmp; |
| ctxt->maxCounters *= 2; |
| tmp = (xmlRegCounter *) xmlRealloc(ctxt->counters, ctxt->maxCounters * |
| sizeof(xmlRegCounter)); |
| if (tmp == NULL) { |
| xmlRegexpErrMemory(ctxt, "allocating counter"); |
| ctxt->maxCounters /= 2; |
| return(-1); |
| } |
| ctxt->counters = tmp; |
| } |
| ctxt->counters[ctxt->nbCounters].min = -1; |
| ctxt->counters[ctxt->nbCounters].max = -1; |
| return(ctxt->nbCounters++); |
| } |
| |
| static int |
| xmlRegAtomPush(xmlRegParserCtxtPtr ctxt, xmlRegAtomPtr atom) { |
| if (atom == NULL) { |
| ERROR("atom push: atom is NULL"); |
| return(-1); |
| } |
| if (ctxt->maxAtoms == 0) { |
| ctxt->maxAtoms = 4; |
| ctxt->atoms = (xmlRegAtomPtr *) xmlMalloc(ctxt->maxAtoms * |
| sizeof(xmlRegAtomPtr)); |
| if (ctxt->atoms == NULL) { |
| xmlRegexpErrMemory(ctxt, "pushing atom"); |
| ctxt->maxAtoms = 0; |
| return(-1); |
| } |
| } else if (ctxt->nbAtoms >= ctxt->maxAtoms) { |
| xmlRegAtomPtr *tmp; |
| ctxt->maxAtoms *= 2; |
| tmp = (xmlRegAtomPtr *) xmlRealloc(ctxt->atoms, ctxt->maxAtoms * |
| sizeof(xmlRegAtomPtr)); |
| if (tmp == NULL) { |
| xmlRegexpErrMemory(ctxt, "allocating counter"); |
| ctxt->maxAtoms /= 2; |
| return(-1); |
| } |
| ctxt->atoms = tmp; |
| } |
| atom->no = ctxt->nbAtoms; |
| ctxt->atoms[ctxt->nbAtoms++] = atom; |
| return(0); |
| } |
| |
| static void |
| xmlRegStateAddTransTo(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr target, |
| int from) { |
| if (target->maxTransTo == 0) { |
| target->maxTransTo = 8; |
| target->transTo = (int *) xmlMalloc(target->maxTransTo * |
| sizeof(int)); |
| if (target->transTo == NULL) { |
| xmlRegexpErrMemory(ctxt, "adding transition"); |
| target->maxTransTo = 0; |
| return; |
| } |
| } else if (target->nbTransTo >= target->maxTransTo) { |
| int *tmp; |
| target->maxTransTo *= 2; |
| tmp = (int *) xmlRealloc(target->transTo, target->maxTransTo * |
| sizeof(int)); |
| if (tmp == NULL) { |
| xmlRegexpErrMemory(ctxt, "adding transition"); |
| target->maxTransTo /= 2; |
| return; |
| } |
| target->transTo = tmp; |
| } |
| target->transTo[target->nbTransTo] = from; |
| target->nbTransTo++; |
| } |
| |
| static void |
| xmlRegStateAddTrans(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state, |
| xmlRegAtomPtr atom, xmlRegStatePtr target, |
| int counter, int count) { |
| |
| int nrtrans; |
| |
| if (state == NULL) { |
| ERROR("add state: state is NULL"); |
| return; |
| } |
| if (target == NULL) { |
| ERROR("add state: target is NULL"); |
| return; |
| } |
| /* |
| * Other routines follow the philosophy 'When in doubt, add a transition' |
| * so we check here whether such a transition is already present and, if |
| * so, silently ignore this request. |
| */ |
| |
| for (nrtrans = state->nbTrans - 1; nrtrans >= 0; nrtrans--) { |
| xmlRegTransPtr trans = &(state->trans[nrtrans]); |
| if ((trans->atom == atom) && |
| (trans->to == target->no) && |
| (trans->counter == counter) && |
| (trans->count == count)) { |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("Ignoring duplicate transition from %d to %d\n", |
| state->no, target->no); |
| #endif |
| return; |
| } |
| } |
| |
| if (state->maxTrans == 0) { |
| state->maxTrans = 8; |
| state->trans = (xmlRegTrans *) xmlMalloc(state->maxTrans * |
| sizeof(xmlRegTrans)); |
| if (state->trans == NULL) { |
| xmlRegexpErrMemory(ctxt, "adding transition"); |
| state->maxTrans = 0; |
| return; |
| } |
| } else if (state->nbTrans >= state->maxTrans) { |
| xmlRegTrans *tmp; |
| state->maxTrans *= 2; |
| tmp = (xmlRegTrans *) xmlRealloc(state->trans, state->maxTrans * |
| sizeof(xmlRegTrans)); |
| if (tmp == NULL) { |
| xmlRegexpErrMemory(ctxt, "adding transition"); |
| state->maxTrans /= 2; |
| return; |
| } |
| state->trans = tmp; |
| } |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("Add trans from %d to %d ", state->no, target->no); |
| if (count == REGEXP_ALL_COUNTER) |
| printf("all transition\n"); |
| else if (count >= 0) |
| printf("count based %d\n", count); |
| else if (counter >= 0) |
| printf("counted %d\n", counter); |
| else if (atom == NULL) |
| printf("epsilon transition\n"); |
| else if (atom != NULL) |
| xmlRegPrintAtom(stdout, atom); |
| #endif |
| |
| state->trans[state->nbTrans].atom = atom; |
| state->trans[state->nbTrans].to = target->no; |
| state->trans[state->nbTrans].counter = counter; |
| state->trans[state->nbTrans].count = count; |
| state->trans[state->nbTrans].nd = 0; |
| state->nbTrans++; |
| xmlRegStateAddTransTo(ctxt, target, state->no); |
| } |
| |
| static int |
| xmlRegStatePush(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) { |
| if (state == NULL) return(-1); |
| if (ctxt->maxStates == 0) { |
| ctxt->maxStates = 4; |
| ctxt->states = (xmlRegStatePtr *) xmlMalloc(ctxt->maxStates * |
| sizeof(xmlRegStatePtr)); |
| if (ctxt->states == NULL) { |
| xmlRegexpErrMemory(ctxt, "adding state"); |
| ctxt->maxStates = 0; |
| return(-1); |
| } |
| } else if (ctxt->nbStates >= ctxt->maxStates) { |
| xmlRegStatePtr *tmp; |
| ctxt->maxStates *= 2; |
| tmp = (xmlRegStatePtr *) xmlRealloc(ctxt->states, ctxt->maxStates * |
| sizeof(xmlRegStatePtr)); |
| if (tmp == NULL) { |
| xmlRegexpErrMemory(ctxt, "adding state"); |
| ctxt->maxStates /= 2; |
| return(-1); |
| } |
| ctxt->states = tmp; |
| } |
| state->no = ctxt->nbStates; |
| ctxt->states[ctxt->nbStates++] = state; |
| return(0); |
| } |
| |
| /** |
| * xmlFAGenerateAllTransition: |
| * @ctxt: a regexp parser context |
| * @from: the from state |
| * @to: the target state or NULL for building a new one |
| * @lax: |
| * |
| */ |
| static void |
| xmlFAGenerateAllTransition(xmlRegParserCtxtPtr ctxt, |
| xmlRegStatePtr from, xmlRegStatePtr to, |
| int lax) { |
| if (to == NULL) { |
| to = xmlRegNewState(ctxt); |
| xmlRegStatePush(ctxt, to); |
| ctxt->state = to; |
| } |
| if (lax) |
| xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_LAX_COUNTER); |
| else |
| xmlRegStateAddTrans(ctxt, from, NULL, to, -1, REGEXP_ALL_COUNTER); |
| } |
| |
| /** |
| * xmlFAGenerateEpsilonTransition: |
| * @ctxt: a regexp parser context |
| * @from: the from state |
| * @to: the target state or NULL for building a new one |
| * |
| */ |
| static void |
| xmlFAGenerateEpsilonTransition(xmlRegParserCtxtPtr ctxt, |
| xmlRegStatePtr from, xmlRegStatePtr to) { |
| if (to == NULL) { |
| to = xmlRegNewState(ctxt); |
| xmlRegStatePush(ctxt, to); |
| ctxt->state = to; |
| } |
| xmlRegStateAddTrans(ctxt, from, NULL, to, -1, -1); |
| } |
| |
| /** |
| * xmlFAGenerateCountedEpsilonTransition: |
| * @ctxt: a regexp parser context |
| * @from: the from state |
| * @to: the target state or NULL for building a new one |
| * counter: the counter for that transition |
| * |
| */ |
| static void |
| xmlFAGenerateCountedEpsilonTransition(xmlRegParserCtxtPtr ctxt, |
| xmlRegStatePtr from, xmlRegStatePtr to, int counter) { |
| if (to == NULL) { |
| to = xmlRegNewState(ctxt); |
| xmlRegStatePush(ctxt, to); |
| ctxt->state = to; |
| } |
| xmlRegStateAddTrans(ctxt, from, NULL, to, counter, -1); |
| } |
| |
| /** |
| * xmlFAGenerateCountedTransition: |
| * @ctxt: a regexp parser context |
| * @from: the from state |
| * @to: the target state or NULL for building a new one |
| * counter: the counter for that transition |
| * |
| */ |
| static void |
| xmlFAGenerateCountedTransition(xmlRegParserCtxtPtr ctxt, |
| xmlRegStatePtr from, xmlRegStatePtr to, int counter) { |
| if (to == NULL) { |
| to = xmlRegNewState(ctxt); |
| xmlRegStatePush(ctxt, to); |
| ctxt->state = to; |
| } |
| xmlRegStateAddTrans(ctxt, from, NULL, to, -1, counter); |
| } |
| |
| /** |
| * xmlFAGenerateTransitions: |
| * @ctxt: a regexp parser context |
| * @from: the from state |
| * @to: the target state or NULL for building a new one |
| * @atom: the atom generating the transition |
| * |
| * Returns 0 if success and -1 in case of error. |
| */ |
| static int |
| xmlFAGenerateTransitions(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr from, |
| xmlRegStatePtr to, xmlRegAtomPtr atom) { |
| xmlRegStatePtr end; |
| int nullable = 0; |
| |
| if (atom == NULL) { |
| ERROR("generate transition: atom == NULL"); |
| return(-1); |
| } |
| if (atom->type == XML_REGEXP_SUBREG) { |
| /* |
| * this is a subexpression handling one should not need to |
| * create a new node except for XML_REGEXP_QUANT_RANGE. |
| */ |
| if (xmlRegAtomPush(ctxt, atom) < 0) { |
| return(-1); |
| } |
| if ((to != NULL) && (atom->stop != to) && |
| (atom->quant != XML_REGEXP_QUANT_RANGE)) { |
| /* |
| * Generate an epsilon transition to link to the target |
| */ |
| xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to); |
| #ifdef DV |
| } else if ((to == NULL) && (atom->quant != XML_REGEXP_QUANT_RANGE) && |
| (atom->quant != XML_REGEXP_QUANT_ONCE)) { |
| to = xmlRegNewState(ctxt); |
| xmlRegStatePush(ctxt, to); |
| ctxt->state = to; |
| xmlFAGenerateEpsilonTransition(ctxt, atom->stop, to); |
| #endif |
| } |
| switch (atom->quant) { |
| case XML_REGEXP_QUANT_OPT: |
| atom->quant = XML_REGEXP_QUANT_ONCE; |
| /* |
| * transition done to the state after end of atom. |
| * 1. set transition from atom start to new state |
| * 2. set transition from atom end to this state. |
| */ |
| if (to == NULL) { |
| xmlFAGenerateEpsilonTransition(ctxt, atom->start, 0); |
| xmlFAGenerateEpsilonTransition(ctxt, atom->stop, |
| ctxt->state); |
| } else { |
| xmlFAGenerateEpsilonTransition(ctxt, atom->start, to); |
| } |
| break; |
| case XML_REGEXP_QUANT_MULT: |
| atom->quant = XML_REGEXP_QUANT_ONCE; |
| xmlFAGenerateEpsilonTransition(ctxt, atom->start, atom->stop); |
| xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start); |
| break; |
| case XML_REGEXP_QUANT_PLUS: |
| atom->quant = XML_REGEXP_QUANT_ONCE; |
| xmlFAGenerateEpsilonTransition(ctxt, atom->stop, atom->start); |
| break; |
| case XML_REGEXP_QUANT_RANGE: { |
| int counter; |
| xmlRegStatePtr inter, newstate; |
| |
| /* |
| * create the final state now if needed |
| */ |
| if (to != NULL) { |
| newstate = to; |
| } else { |
| newstate = xmlRegNewState(ctxt); |
| xmlRegStatePush(ctxt, newstate); |
| } |
| |
| /* |
| * The principle here is to use counted transition |
| * to avoid explosion in the number of states in the |
| * graph. This is clearly more complex but should not |
| * be exploitable at runtime. |
| */ |
| if ((atom->min == 0) && (atom->start0 == NULL)) { |
| xmlRegAtomPtr copy; |
| /* |
| * duplicate a transition based on atom to count next |
| * occurrences after 1. We cannot loop to atom->start |
| * directly because we need an epsilon transition to |
| * newstate. |
| */ |
| /* ???? For some reason it seems we never reach that |
| case, I suppose this got optimized out before when |
| building the automata */ |
| copy = xmlRegCopyAtom(ctxt, atom); |
| if (copy == NULL) |
| return(-1); |
| copy->quant = XML_REGEXP_QUANT_ONCE; |
| copy->min = 0; |
| copy->max = 0; |
| |
| if (xmlFAGenerateTransitions(ctxt, atom->start, NULL, copy) |
| < 0) |
| return(-1); |
| inter = ctxt->state; |
| counter = xmlRegGetCounter(ctxt); |
| ctxt->counters[counter].min = atom->min - 1; |
| ctxt->counters[counter].max = atom->max - 1; |
| /* count the number of times we see it again */ |
| xmlFAGenerateCountedEpsilonTransition(ctxt, inter, |
| atom->stop, counter); |
| /* allow a way out based on the count */ |
| xmlFAGenerateCountedTransition(ctxt, inter, |
| newstate, counter); |
| /* and also allow a direct exit for 0 */ |
| xmlFAGenerateEpsilonTransition(ctxt, atom->start, |
| newstate); |
| } else { |
| /* |
| * either we need the atom at least once or there |
| * is an atom->start0 allowing to easily plug the |
| * epsilon transition. |
| */ |
| counter = xmlRegGetCounter(ctxt); |
| ctxt->counters[counter].min = atom->min - 1; |
| ctxt->counters[counter].max = atom->max - 1; |
| /* count the number of times we see it again */ |
| xmlFAGenerateCountedEpsilonTransition(ctxt, atom->stop, |
| atom->start, counter); |
| /* allow a way out based on the count */ |
| xmlFAGenerateCountedTransition(ctxt, atom->stop, |
| newstate, counter); |
| /* and if needed allow a direct exit for 0 */ |
| if (atom->min == 0) |
| xmlFAGenerateEpsilonTransition(ctxt, atom->start0, |
| newstate); |
| |
| } |
| atom->min = 0; |
| atom->max = 0; |
| atom->quant = XML_REGEXP_QUANT_ONCE; |
| ctxt->state = newstate; |
| } |
| default: |
| break; |
| } |
| return(0); |
| } |
| if ((atom->min == 0) && (atom->max == 0) && |
| (atom->quant == XML_REGEXP_QUANT_RANGE)) { |
| /* |
| * we can discard the atom and generate an epsilon transition instead |
| */ |
| if (to == NULL) { |
| to = xmlRegNewState(ctxt); |
| if (to != NULL) |
| xmlRegStatePush(ctxt, to); |
| else { |
| return(-1); |
| } |
| } |
| xmlFAGenerateEpsilonTransition(ctxt, from, to); |
| ctxt->state = to; |
| xmlRegFreeAtom(atom); |
| return(0); |
| } |
| if (to == NULL) { |
| to = xmlRegNewState(ctxt); |
| if (to != NULL) |
| xmlRegStatePush(ctxt, to); |
| else { |
| return(-1); |
| } |
| } |
| end = to; |
| if ((atom->quant == XML_REGEXP_QUANT_MULT) || |
| (atom->quant == XML_REGEXP_QUANT_PLUS)) { |
| /* |
| * Do not pollute the target state by adding transitions from |
| * it as it is likely to be the shared target of multiple branches. |
| * So isolate with an epsilon transition. |
| */ |
| xmlRegStatePtr tmp; |
| |
| tmp = xmlRegNewState(ctxt); |
| if (tmp != NULL) |
| xmlRegStatePush(ctxt, tmp); |
| else { |
| return(-1); |
| } |
| xmlFAGenerateEpsilonTransition(ctxt, tmp, to); |
| to = tmp; |
| } |
| if (xmlRegAtomPush(ctxt, atom) < 0) { |
| return(-1); |
| } |
| if ((atom->quant == XML_REGEXP_QUANT_RANGE) && |
| (atom->min == 0) && (atom->max > 0)) { |
| nullable = 1; |
| atom->min = 1; |
| if (atom->max == 1) |
| atom->quant = XML_REGEXP_QUANT_OPT; |
| } |
| xmlRegStateAddTrans(ctxt, from, atom, to, -1, -1); |
| ctxt->state = end; |
| switch (atom->quant) { |
| case XML_REGEXP_QUANT_OPT: |
| atom->quant = XML_REGEXP_QUANT_ONCE; |
| xmlFAGenerateEpsilonTransition(ctxt, from, to); |
| break; |
| case XML_REGEXP_QUANT_MULT: |
| atom->quant = XML_REGEXP_QUANT_ONCE; |
| xmlFAGenerateEpsilonTransition(ctxt, from, to); |
| xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1); |
| break; |
| case XML_REGEXP_QUANT_PLUS: |
| atom->quant = XML_REGEXP_QUANT_ONCE; |
| xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1); |
| break; |
| case XML_REGEXP_QUANT_RANGE: |
| if (nullable) |
| xmlFAGenerateEpsilonTransition(ctxt, from, to); |
| break; |
| default: |
| break; |
| } |
| return(0); |
| } |
| |
| /** |
| * xmlFAReduceEpsilonTransitions: |
| * @ctxt: a regexp parser context |
| * @fromnr: the from state |
| * @tonr: the to state |
| * @counter: should that transition be associated to a counted |
| * |
| */ |
| static void |
| xmlFAReduceEpsilonTransitions(xmlRegParserCtxtPtr ctxt, int fromnr, |
| int tonr, int counter) { |
| int transnr; |
| xmlRegStatePtr from; |
| xmlRegStatePtr to; |
| |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("xmlFAReduceEpsilonTransitions(%d, %d)\n", fromnr, tonr); |
| #endif |
| from = ctxt->states[fromnr]; |
| if (from == NULL) |
| return; |
| to = ctxt->states[tonr]; |
| if (to == NULL) |
| return; |
| if ((to->mark == XML_REGEXP_MARK_START) || |
| (to->mark == XML_REGEXP_MARK_VISITED)) |
| return; |
| |
| to->mark = XML_REGEXP_MARK_VISITED; |
| if (to->type == XML_REGEXP_FINAL_STATE) { |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("State %d is final, so %d becomes final\n", tonr, fromnr); |
| #endif |
| from->type = XML_REGEXP_FINAL_STATE; |
| } |
| for (transnr = 0;transnr < to->nbTrans;transnr++) { |
| if (to->trans[transnr].to < 0) |
| continue; |
| if (to->trans[transnr].atom == NULL) { |
| /* |
| * Don't remove counted transitions |
| * Don't loop either |
| */ |
| if (to->trans[transnr].to != fromnr) { |
| if (to->trans[transnr].count >= 0) { |
| int newto = to->trans[transnr].to; |
| |
| xmlRegStateAddTrans(ctxt, from, NULL, |
| ctxt->states[newto], |
| -1, to->trans[transnr].count); |
| } else { |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("Found epsilon trans %d from %d to %d\n", |
| transnr, tonr, to->trans[transnr].to); |
| #endif |
| if (to->trans[transnr].counter >= 0) { |
| xmlFAReduceEpsilonTransitions(ctxt, fromnr, |
| to->trans[transnr].to, |
| to->trans[transnr].counter); |
| } else { |
| xmlFAReduceEpsilonTransitions(ctxt, fromnr, |
| to->trans[transnr].to, |
| counter); |
| } |
| } |
| } |
| } else { |
| int newto = to->trans[transnr].to; |
| |
| if (to->trans[transnr].counter >= 0) { |
| xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom, |
| ctxt->states[newto], |
| to->trans[transnr].counter, -1); |
| } else { |
| xmlRegStateAddTrans(ctxt, from, to->trans[transnr].atom, |
| ctxt->states[newto], counter, -1); |
| } |
| } |
| } |
| to->mark = XML_REGEXP_MARK_NORMAL; |
| } |
| |
| /** |
| * xmlFAEliminateSimpleEpsilonTransitions: |
| * @ctxt: a regexp parser context |
| * |
| * Eliminating general epsilon transitions can get costly in the general |
| * algorithm due to the large amount of generated new transitions and |
| * associated comparisons. However for simple epsilon transition used just |
| * to separate building blocks when generating the automata this can be |
| * reduced to state elimination: |
| * - if there exists an epsilon from X to Y |
| * - if there is no other transition from X |
| * then X and Y are semantically equivalent and X can be eliminated |
| * If X is the start state then make Y the start state, else replace the |
| * target of all transitions to X by transitions to Y. |
| */ |
| static void |
| xmlFAEliminateSimpleEpsilonTransitions(xmlRegParserCtxtPtr ctxt) { |
| int statenr, i, j, newto; |
| xmlRegStatePtr state, tmp; |
| |
| for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
| state = ctxt->states[statenr]; |
| if (state == NULL) |
| continue; |
| if (state->nbTrans != 1) |
| continue; |
| if (state->type == XML_REGEXP_UNREACH_STATE) |
| continue; |
| /* is the only transition out a basic transition */ |
| if ((state->trans[0].atom == NULL) && |
| (state->trans[0].to >= 0) && |
| (state->trans[0].to != statenr) && |
| (state->trans[0].counter < 0) && |
| (state->trans[0].count < 0)) { |
| newto = state->trans[0].to; |
| |
| if (state->type == XML_REGEXP_START_STATE) { |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("Found simple epsilon trans from start %d to %d\n", |
| statenr, newto); |
| #endif |
| } else { |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("Found simple epsilon trans from %d to %d\n", |
| statenr, newto); |
| #endif |
| for (i = 0;i < state->nbTransTo;i++) { |
| tmp = ctxt->states[state->transTo[i]]; |
| for (j = 0;j < tmp->nbTrans;j++) { |
| if (tmp->trans[j].to == statenr) { |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("Changed transition %d on %d to go to %d\n", |
| j, tmp->no, newto); |
| #endif |
| tmp->trans[j].to = -1; |
| xmlRegStateAddTrans(ctxt, tmp, tmp->trans[j].atom, |
| ctxt->states[newto], |
| tmp->trans[j].counter, |
| tmp->trans[j].count); |
| } |
| } |
| } |
| if (state->type == XML_REGEXP_FINAL_STATE) |
| ctxt->states[newto]->type = XML_REGEXP_FINAL_STATE; |
| /* eliminate the transition completely */ |
| state->nbTrans = 0; |
| |
| state->type = XML_REGEXP_UNREACH_STATE; |
| |
| } |
| |
| } |
| } |
| } |
| /** |
| * xmlFAEliminateEpsilonTransitions: |
| * @ctxt: a regexp parser context |
| * |
| */ |
| static void |
| xmlFAEliminateEpsilonTransitions(xmlRegParserCtxtPtr ctxt) { |
| int statenr, transnr; |
| xmlRegStatePtr state; |
| int has_epsilon; |
| |
| if (ctxt->states == NULL) return; |
| |
| /* |
| * Eliminate simple epsilon transition and the associated unreachable |
| * states. |
| */ |
| xmlFAEliminateSimpleEpsilonTransitions(ctxt); |
| for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
| state = ctxt->states[statenr]; |
| if ((state != NULL) && (state->type == XML_REGEXP_UNREACH_STATE)) { |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("Removed unreachable state %d\n", statenr); |
| #endif |
| xmlRegFreeState(state); |
| ctxt->states[statenr] = NULL; |
| } |
| } |
| |
| has_epsilon = 0; |
| |
| /* |
| * Build the completed transitions bypassing the epsilons |
| * Use a marking algorithm to avoid loops |
| * Mark sink states too. |
| * Process from the latest states backward to the start when |
| * there is long cascading epsilon chains this minimize the |
| * recursions and transition compares when adding the new ones |
| */ |
| for (statenr = ctxt->nbStates - 1;statenr >= 0;statenr--) { |
| state = ctxt->states[statenr]; |
| if (state == NULL) |
| continue; |
| if ((state->nbTrans == 0) && |
| (state->type != XML_REGEXP_FINAL_STATE)) { |
| state->type = XML_REGEXP_SINK_STATE; |
| } |
| for (transnr = 0;transnr < state->nbTrans;transnr++) { |
| if ((state->trans[transnr].atom == NULL) && |
| (state->trans[transnr].to >= 0)) { |
| if (state->trans[transnr].to == statenr) { |
| state->trans[transnr].to = -1; |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("Removed loopback epsilon trans %d on %d\n", |
| transnr, statenr); |
| #endif |
| } else if (state->trans[transnr].count < 0) { |
| int newto = state->trans[transnr].to; |
| |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("Found epsilon trans %d from %d to %d\n", |
| transnr, statenr, newto); |
| #endif |
| has_epsilon = 1; |
| state->trans[transnr].to = -2; |
| state->mark = XML_REGEXP_MARK_START; |
| xmlFAReduceEpsilonTransitions(ctxt, statenr, |
| newto, state->trans[transnr].counter); |
| state->mark = XML_REGEXP_MARK_NORMAL; |
| #ifdef DEBUG_REGEXP_GRAPH |
| } else { |
| printf("Found counted transition %d on %d\n", |
| transnr, statenr); |
| #endif |
| } |
| } |
| } |
| } |
| /* |
| * Eliminate the epsilon transitions |
| */ |
| if (has_epsilon) { |
| for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
| state = ctxt->states[statenr]; |
| if (state == NULL) |
| continue; |
| for (transnr = 0;transnr < state->nbTrans;transnr++) { |
| xmlRegTransPtr trans = &(state->trans[transnr]); |
| if ((trans->atom == NULL) && |
| (trans->count < 0) && |
| (trans->to >= 0)) { |
| trans->to = -1; |
| } |
| } |
| } |
| } |
| |
| /* |
| * Use this pass to detect unreachable states too |
| */ |
| for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
| state = ctxt->states[statenr]; |
| if (state != NULL) |
| state->reached = XML_REGEXP_MARK_NORMAL; |
| } |
| state = ctxt->states[0]; |
| if (state != NULL) |
| state->reached = XML_REGEXP_MARK_START; |
| while (state != NULL) { |
| xmlRegStatePtr target = NULL; |
| state->reached = XML_REGEXP_MARK_VISITED; |
| /* |
| * Mark all states reachable from the current reachable state |
| */ |
| for (transnr = 0;transnr < state->nbTrans;transnr++) { |
| if ((state->trans[transnr].to >= 0) && |
| ((state->trans[transnr].atom != NULL) || |
| (state->trans[transnr].count >= 0))) { |
| int newto = state->trans[transnr].to; |
| |
| if (ctxt->states[newto] == NULL) |
| continue; |
| if (ctxt->states[newto]->reached == XML_REGEXP_MARK_NORMAL) { |
| ctxt->states[newto]->reached = XML_REGEXP_MARK_START; |
| target = ctxt->states[newto]; |
| } |
| } |
| } |
| |
| /* |
| * find the next accessible state not explored |
| */ |
| if (target == NULL) { |
| for (statenr = 1;statenr < ctxt->nbStates;statenr++) { |
| state = ctxt->states[statenr]; |
| if ((state != NULL) && (state->reached == |
| XML_REGEXP_MARK_START)) { |
| target = state; |
| break; |
| } |
| } |
| } |
| state = target; |
| } |
| for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
| state = ctxt->states[statenr]; |
| if ((state != NULL) && (state->reached == XML_REGEXP_MARK_NORMAL)) { |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("Removed unreachable state %d\n", statenr); |
| #endif |
| xmlRegFreeState(state); |
| ctxt->states[statenr] = NULL; |
| } |
| } |
| |
| } |
| |
| static int |
| xmlFACompareRanges(xmlRegRangePtr range1, xmlRegRangePtr range2) { |
| int ret = 0; |
| |
| if ((range1->type == XML_REGEXP_RANGES) || |
| (range2->type == XML_REGEXP_RANGES) || |
| (range2->type == XML_REGEXP_SUBREG) || |
| (range1->type == XML_REGEXP_SUBREG) || |
| (range1->type == XML_REGEXP_STRING) || |
| (range2->type == XML_REGEXP_STRING)) |
| return(-1); |
| |
| /* put them in order */ |
| if (range1->type > range2->type) { |
| xmlRegRangePtr tmp; |
| |
| tmp = range1; |
| range1 = range2; |
| range2 = tmp; |
| } |
| if ((range1->type == XML_REGEXP_ANYCHAR) || |
| (range2->type == XML_REGEXP_ANYCHAR)) { |
| ret = 1; |
| } else if ((range1->type == XML_REGEXP_EPSILON) || |
| (range2->type == XML_REGEXP_EPSILON)) { |
| return(0); |
| } else if (range1->type == range2->type) { |
| if (range1->type != XML_REGEXP_CHARVAL) |
| ret = 1; |
| else if ((range1->end < range2->start) || |
| (range2->end < range1->start)) |
| ret = 0; |
| else |
| ret = 1; |
| } else if (range1->type == XML_REGEXP_CHARVAL) { |
| int codepoint; |
| int neg = 0; |
| |
| /* |
| * just check all codepoints in the range for acceptance, |
| * this is usually way cheaper since done only once at |
| * compilation than testing over and over at runtime or |
| * pushing too many states when evaluating. |
| */ |
| if (((range1->neg == 0) && (range2->neg != 0)) || |
| ((range1->neg != 0) && (range2->neg == 0))) |
| neg = 1; |
| |
| for (codepoint = range1->start;codepoint <= range1->end ;codepoint++) { |
| ret = xmlRegCheckCharacterRange(range2->type, codepoint, |
| 0, range2->start, range2->end, |
| range2->blockName); |
| if (ret < 0) |
| return(-1); |
| if (((neg == 1) && (ret == 0)) || |
| ((neg == 0) && (ret == 1))) |
| return(1); |
| } |
| return(0); |
| } else if ((range1->type == XML_REGEXP_BLOCK_NAME) || |
| (range2->type == XML_REGEXP_BLOCK_NAME)) { |
| if (range1->type == range2->type) { |
| ret = xmlStrEqual(range1->blockName, range2->blockName); |
| } else { |
| /* |
| * comparing a block range with anything else is way |
| * too costly, and maintaining the table is like too much |
| * memory too, so let's force the automata to save state |
| * here. |
| */ |
| return(1); |
| } |
| } else if ((range1->type < XML_REGEXP_LETTER) || |
| (range2->type < XML_REGEXP_LETTER)) { |
| if ((range1->type == XML_REGEXP_ANYSPACE) && |
| (range2->type == XML_REGEXP_NOTSPACE)) |
| ret = 0; |
| else if ((range1->type == XML_REGEXP_INITNAME) && |
| (range2->type == XML_REGEXP_NOTINITNAME)) |
| ret = 0; |
| else if ((range1->type == XML_REGEXP_NAMECHAR) && |
| (range2->type == XML_REGEXP_NOTNAMECHAR)) |
| ret = 0; |
| else if ((range1->type == XML_REGEXP_DECIMAL) && |
| (range2->type == XML_REGEXP_NOTDECIMAL)) |
| ret = 0; |
| else if ((range1->type == XML_REGEXP_REALCHAR) && |
| (range2->type == XML_REGEXP_NOTREALCHAR)) |
| ret = 0; |
| else { |
| /* same thing to limit complexity */ |
| return(1); |
| } |
| } else { |
| ret = 0; |
| /* range1->type < range2->type here */ |
| switch (range1->type) { |
| case XML_REGEXP_LETTER: |
| /* all disjoint except in the subgroups */ |
| if ((range2->type == XML_REGEXP_LETTER_UPPERCASE) || |
| (range2->type == XML_REGEXP_LETTER_LOWERCASE) || |
| (range2->type == XML_REGEXP_LETTER_TITLECASE) || |
| (range2->type == XML_REGEXP_LETTER_MODIFIER) || |
| (range2->type == XML_REGEXP_LETTER_OTHERS)) |
| ret = 1; |
| break; |
| case XML_REGEXP_MARK: |
| if ((range2->type == XML_REGEXP_MARK_NONSPACING) || |
| (range2->type == XML_REGEXP_MARK_SPACECOMBINING) || |
| (range2->type == XML_REGEXP_MARK_ENCLOSING)) |
| ret = 1; |
| break; |
| case XML_REGEXP_NUMBER: |
| if ((range2->type == XML_REGEXP_NUMBER_DECIMAL) || |
| (range2->type == XML_REGEXP_NUMBER_LETTER) || |
| (range2->type == XML_REGEXP_NUMBER_OTHERS)) |
| ret = 1; |
| break; |
| case XML_REGEXP_PUNCT: |
| if ((range2->type == XML_REGEXP_PUNCT_CONNECTOR) || |
| (range2->type == XML_REGEXP_PUNCT_DASH) || |
| (range2->type == XML_REGEXP_PUNCT_OPEN) || |
| (range2->type == XML_REGEXP_PUNCT_CLOSE) || |
| (range2->type == XML_REGEXP_PUNCT_INITQUOTE) || |
| (range2->type == XML_REGEXP_PUNCT_FINQUOTE) || |
| (range2->type == XML_REGEXP_PUNCT_OTHERS)) |
| ret = 1; |
| break; |
| case XML_REGEXP_SEPAR: |
| if ((range2->type == XML_REGEXP_SEPAR_SPACE) || |
| (range2->type == XML_REGEXP_SEPAR_LINE) || |
| (range2->type == XML_REGEXP_SEPAR_PARA)) |
| ret = 1; |
| break; |
| case XML_REGEXP_SYMBOL: |
| if ((range2->type == XML_REGEXP_SYMBOL_MATH) || |
| (range2->type == XML_REGEXP_SYMBOL_CURRENCY) || |
| (range2->type == XML_REGEXP_SYMBOL_MODIFIER) || |
| (range2->type == XML_REGEXP_SYMBOL_OTHERS)) |
| ret = 1; |
| break; |
| case XML_REGEXP_OTHER: |
| if ((range2->type == XML_REGEXP_OTHER_CONTROL) || |
| (range2->type == XML_REGEXP_OTHER_FORMAT) || |
| (range2->type == XML_REGEXP_OTHER_PRIVATE)) |
| ret = 1; |
| break; |
| default: |
| if ((range2->type >= XML_REGEXP_LETTER) && |
| (range2->type < XML_REGEXP_BLOCK_NAME)) |
| ret = 0; |
| else { |
| /* safety net ! */ |
| return(1); |
| } |
| } |
| } |
| if (((range1->neg == 0) && (range2->neg != 0)) || |
| ((range1->neg != 0) && (range2->neg == 0))) |
| ret = !ret; |
| return(ret); |
| } |
| |
| /** |
| * xmlFACompareAtomTypes: |
| * @type1: an atom type |
| * @type2: an atom type |
| * |
| * Compares two atoms type to check whether they intersect in some ways, |
| * this is used by xmlFACompareAtoms only |
| * |
| * Returns 1 if they may intersect and 0 otherwise |
| */ |
| static int |
| xmlFACompareAtomTypes(xmlRegAtomType type1, xmlRegAtomType type2) { |
| if ((type1 == XML_REGEXP_EPSILON) || |
| (type1 == XML_REGEXP_CHARVAL) || |
| (type1 == XML_REGEXP_RANGES) || |
| (type1 == XML_REGEXP_SUBREG) || |
| (type1 == XML_REGEXP_STRING) || |
| (type1 == XML_REGEXP_ANYCHAR)) |
| return(1); |
| if ((type2 == XML_REGEXP_EPSILON) || |
| (type2 == XML_REGEXP_CHARVAL) || |
| (type2 == XML_REGEXP_RANGES) || |
| (type2 == XML_REGEXP_SUBREG) || |
| (type2 == XML_REGEXP_STRING) || |
| (type2 == XML_REGEXP_ANYCHAR)) |
| return(1); |
| |
| if (type1 == type2) return(1); |
| |
| /* simplify subsequent compares by making sure type1 < type2 */ |
| if (type1 > type2) { |
| xmlRegAtomType tmp = type1; |
| type1 = type2; |
| type2 = tmp; |
| } |
| switch (type1) { |
| case XML_REGEXP_ANYSPACE: /* \s */ |
| /* can't be a letter, number, mark, punctuation, symbol */ |
| if ((type2 == XML_REGEXP_NOTSPACE) || |
| ((type2 >= XML_REGEXP_LETTER) && |
| (type2 <= XML_REGEXP_LETTER_OTHERS)) || |
| ((type2 >= XML_REGEXP_NUMBER) && |
| (type2 <= XML_REGEXP_NUMBER_OTHERS)) || |
| ((type2 >= XML_REGEXP_MARK) && |
| (type2 <= XML_REGEXP_MARK_ENCLOSING)) || |
| ((type2 >= XML_REGEXP_PUNCT) && |
| (type2 <= XML_REGEXP_PUNCT_OTHERS)) || |
| ((type2 >= XML_REGEXP_SYMBOL) && |
| (type2 <= XML_REGEXP_SYMBOL_OTHERS)) |
| ) return(0); |
| break; |
| case XML_REGEXP_NOTSPACE: /* \S */ |
| break; |
| case XML_REGEXP_INITNAME: /* \l */ |
| /* can't be a number, mark, separator, punctuation, symbol or other */ |
| if ((type2 == XML_REGEXP_NOTINITNAME) || |
| ((type2 >= XML_REGEXP_NUMBER) && |
| (type2 <= XML_REGEXP_NUMBER_OTHERS)) || |
| ((type2 >= XML_REGEXP_MARK) && |
| (type2 <= XML_REGEXP_MARK_ENCLOSING)) || |
| ((type2 >= XML_REGEXP_SEPAR) && |
| (type2 <= XML_REGEXP_SEPAR_PARA)) || |
| ((type2 >= XML_REGEXP_PUNCT) && |
| (type2 <= XML_REGEXP_PUNCT_OTHERS)) || |
| ((type2 >= XML_REGEXP_SYMBOL) && |
| (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || |
| ((type2 >= XML_REGEXP_OTHER) && |
| (type2 <= XML_REGEXP_OTHER_NA)) |
| ) return(0); |
| break; |
| case XML_REGEXP_NOTINITNAME: /* \L */ |
| break; |
| case XML_REGEXP_NAMECHAR: /* \c */ |
| /* can't be a mark, separator, punctuation, symbol or other */ |
| if ((type2 == XML_REGEXP_NOTNAMECHAR) || |
| ((type2 >= XML_REGEXP_MARK) && |
| (type2 <= XML_REGEXP_MARK_ENCLOSING)) || |
| ((type2 >= XML_REGEXP_PUNCT) && |
| (type2 <= XML_REGEXP_PUNCT_OTHERS)) || |
| ((type2 >= XML_REGEXP_SEPAR) && |
| (type2 <= XML_REGEXP_SEPAR_PARA)) || |
| ((type2 >= XML_REGEXP_SYMBOL) && |
| (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || |
| ((type2 >= XML_REGEXP_OTHER) && |
| (type2 <= XML_REGEXP_OTHER_NA)) |
| ) return(0); |
| break; |
| case XML_REGEXP_NOTNAMECHAR: /* \C */ |
| break; |
| case XML_REGEXP_DECIMAL: /* \d */ |
| /* can't be a letter, mark, separator, punctuation, symbol or other */ |
| if ((type2 == XML_REGEXP_NOTDECIMAL) || |
| (type2 == XML_REGEXP_REALCHAR) || |
| ((type2 >= XML_REGEXP_LETTER) && |
| (type2 <= XML_REGEXP_LETTER_OTHERS)) || |
| ((type2 >= XML_REGEXP_MARK) && |
| (type2 <= XML_REGEXP_MARK_ENCLOSING)) || |
| ((type2 >= XML_REGEXP_PUNCT) && |
| (type2 <= XML_REGEXP_PUNCT_OTHERS)) || |
| ((type2 >= XML_REGEXP_SEPAR) && |
| (type2 <= XML_REGEXP_SEPAR_PARA)) || |
| ((type2 >= XML_REGEXP_SYMBOL) && |
| (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || |
| ((type2 >= XML_REGEXP_OTHER) && |
| (type2 <= XML_REGEXP_OTHER_NA)) |
| )return(0); |
| break; |
| case XML_REGEXP_NOTDECIMAL: /* \D */ |
| break; |
| case XML_REGEXP_REALCHAR: /* \w */ |
| /* can't be a mark, separator, punctuation, symbol or other */ |
| if ((type2 == XML_REGEXP_NOTDECIMAL) || |
| ((type2 >= XML_REGEXP_MARK) && |
| (type2 <= XML_REGEXP_MARK_ENCLOSING)) || |
| ((type2 >= XML_REGEXP_PUNCT) && |
| (type2 <= XML_REGEXP_PUNCT_OTHERS)) || |
| ((type2 >= XML_REGEXP_SEPAR) && |
| (type2 <= XML_REGEXP_SEPAR_PARA)) || |
| ((type2 >= XML_REGEXP_SYMBOL) && |
| (type2 <= XML_REGEXP_SYMBOL_OTHERS)) || |
| ((type2 >= XML_REGEXP_OTHER) && |
| (type2 <= XML_REGEXP_OTHER_NA)) |
| )return(0); |
| break; |
| case XML_REGEXP_NOTREALCHAR: /* \W */ |
| break; |
| /* |
| * at that point we know both type 1 and type2 are from |
| * character categories are ordered and are different, |
| * it becomes simple because this is a partition |
| */ |
| case XML_REGEXP_LETTER: |
| if (type2 <= XML_REGEXP_LETTER_OTHERS) |
| return(1); |
| return(0); |
| case XML_REGEXP_LETTER_UPPERCASE: |
| case XML_REGEXP_LETTER_LOWERCASE: |
| case XML_REGEXP_LETTER_TITLECASE: |
| case XML_REGEXP_LETTER_MODIFIER: |
| case XML_REGEXP_LETTER_OTHERS: |
| return(0); |
| case XML_REGEXP_MARK: |
| if (type2 <= XML_REGEXP_MARK_ENCLOSING) |
| return(1); |
| return(0); |
| case XML_REGEXP_MARK_NONSPACING: |
| case XML_REGEXP_MARK_SPACECOMBINING: |
| case XML_REGEXP_MARK_ENCLOSING: |
| return(0); |
| case XML_REGEXP_NUMBER: |
| if (type2 <= XML_REGEXP_NUMBER_OTHERS) |
| return(1); |
| return(0); |
| case XML_REGEXP_NUMBER_DECIMAL: |
| case XML_REGEXP_NUMBER_LETTER: |
| case XML_REGEXP_NUMBER_OTHERS: |
| return(0); |
| case XML_REGEXP_PUNCT: |
| if (type2 <= XML_REGEXP_PUNCT_OTHERS) |
| return(1); |
| return(0); |
| case XML_REGEXP_PUNCT_CONNECTOR: |
| case XML_REGEXP_PUNCT_DASH: |
| case XML_REGEXP_PUNCT_OPEN: |
| case XML_REGEXP_PUNCT_CLOSE: |
| case XML_REGEXP_PUNCT_INITQUOTE: |
| case XML_REGEXP_PUNCT_FINQUOTE: |
| case XML_REGEXP_PUNCT_OTHERS: |
| return(0); |
| case XML_REGEXP_SEPAR: |
| if (type2 <= XML_REGEXP_SEPAR_PARA) |
| return(1); |
| return(0); |
| case XML_REGEXP_SEPAR_SPACE: |
| case XML_REGEXP_SEPAR_LINE: |
| case XML_REGEXP_SEPAR_PARA: |
| return(0); |
| case XML_REGEXP_SYMBOL: |
| if (type2 <= XML_REGEXP_SYMBOL_OTHERS) |
| return(1); |
| return(0); |
| case XML_REGEXP_SYMBOL_MATH: |
| case XML_REGEXP_SYMBOL_CURRENCY: |
| case XML_REGEXP_SYMBOL_MODIFIER: |
| case XML_REGEXP_SYMBOL_OTHERS: |
| return(0); |
| case XML_REGEXP_OTHER: |
| if (type2 <= XML_REGEXP_OTHER_NA) |
| return(1); |
| return(0); |
| case XML_REGEXP_OTHER_CONTROL: |
| case XML_REGEXP_OTHER_FORMAT: |
| case XML_REGEXP_OTHER_PRIVATE: |
| case XML_REGEXP_OTHER_NA: |
| return(0); |
| default: |
| break; |
| } |
| return(1); |
| } |
| |
| /** |
| * xmlFAEqualAtoms: |
| * @atom1: an atom |
| * @atom2: an atom |
| * @deep: if not set only compare string pointers |
| * |
| * Compares two atoms to check whether they are the same exactly |
| * this is used to remove equivalent transitions |
| * |
| * Returns 1 if same and 0 otherwise |
| */ |
| static int |
| xmlFAEqualAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2, int deep) { |
| int ret = 0; |
| |
| if (atom1 == atom2) |
| return(1); |
| if ((atom1 == NULL) || (atom2 == NULL)) |
| return(0); |
| |
| if (atom1->type != atom2->type) |
| return(0); |
| switch (atom1->type) { |
| case XML_REGEXP_EPSILON: |
| ret = 0; |
| break; |
| case XML_REGEXP_STRING: |
| if (!deep) |
| ret = (atom1->valuep == atom2->valuep); |
| else |
| ret = xmlStrEqual((xmlChar *)atom1->valuep, |
| (xmlChar *)atom2->valuep); |
| break; |
| case XML_REGEXP_CHARVAL: |
| ret = (atom1->codepoint == atom2->codepoint); |
| break; |
| case XML_REGEXP_RANGES: |
| /* too hard to do in the general case */ |
| ret = 0; |
| default: |
| break; |
| } |
| return(ret); |
| } |
| |
| /** |
| * xmlFACompareAtoms: |
| * @atom1: an atom |
| * @atom2: an atom |
| * @deep: if not set only compare string pointers |
| * |
| * Compares two atoms to check whether they intersect in some ways, |
| * this is used by xmlFAComputesDeterminism and xmlFARecurseDeterminism only |
| * |
| * Returns 1 if yes and 0 otherwise |
| */ |
| static int |
| xmlFACompareAtoms(xmlRegAtomPtr atom1, xmlRegAtomPtr atom2, int deep) { |
| int ret = 1; |
| |
| if (atom1 == atom2) |
| return(1); |
| if ((atom1 == NULL) || (atom2 == NULL)) |
| return(0); |
| |
| if ((atom1->type == XML_REGEXP_ANYCHAR) || |
| (atom2->type == XML_REGEXP_ANYCHAR)) |
| return(1); |
| |
| if (atom1->type > atom2->type) { |
| xmlRegAtomPtr tmp; |
| tmp = atom1; |
| atom1 = atom2; |
| atom2 = tmp; |
| } |
| if (atom1->type != atom2->type) { |
| ret = xmlFACompareAtomTypes(atom1->type, atom2->type); |
| /* if they can't intersect at the type level break now */ |
| if (ret == 0) |
| return(0); |
| } |
| switch (atom1->type) { |
| case XML_REGEXP_STRING: |
| if (!deep) |
| ret = (atom1->valuep != atom2->valuep); |
| else { |
| xmlChar *val1 = (xmlChar *)atom1->valuep; |
| xmlChar *val2 = (xmlChar *)atom2->valuep; |
| int compound1 = (xmlStrchr(val1, '|') != NULL); |
| int compound2 = (xmlStrchr(val2, '|') != NULL); |
| |
| /* Ignore negative match flag for ##other namespaces */ |
| if (compound1 != compound2) |
| return(0); |
| |
| ret = xmlRegStrEqualWildcard(val1, val2); |
| } |
| break; |
| case XML_REGEXP_EPSILON: |
| goto not_determinist; |
| case XML_REGEXP_CHARVAL: |
| if (atom2->type == XML_REGEXP_CHARVAL) { |
| ret = (atom1->codepoint == atom2->codepoint); |
| } else { |
| ret = xmlRegCheckCharacter(atom2, atom1->codepoint); |
| if (ret < 0) |
| ret = 1; |
| } |
| break; |
| case XML_REGEXP_RANGES: |
| if (atom2->type == XML_REGEXP_RANGES) { |
| int i, j, res; |
| xmlRegRangePtr r1, r2; |
| |
| /* |
| * need to check that none of the ranges eventually matches |
| */ |
| for (i = 0;i < atom1->nbRanges;i++) { |
| for (j = 0;j < atom2->nbRanges;j++) { |
| r1 = atom1->ranges[i]; |
| r2 = atom2->ranges[j]; |
| res = xmlFACompareRanges(r1, r2); |
| if (res == 1) { |
| ret = 1; |
| goto done; |
| } |
| } |
| } |
| ret = 0; |
| } |
| break; |
| default: |
| goto not_determinist; |
| } |
| done: |
| if (atom1->neg != atom2->neg) { |
| ret = !ret; |
| } |
| if (ret == 0) |
| return(0); |
| not_determinist: |
| return(1); |
| } |
| |
| /** |
| * xmlFARecurseDeterminism: |
| * @ctxt: a regexp parser context |
| * |
| * Check whether the associated regexp is determinist, |
| * should be called after xmlFAEliminateEpsilonTransitions() |
| * |
| */ |
| static int |
| xmlFARecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state, |
| int to, xmlRegAtomPtr atom) { |
| int ret = 1; |
| int res; |
| int transnr, nbTrans; |
| xmlRegTransPtr t1; |
| int deep = 1; |
| |
| if (state == NULL) |
| return(ret); |
| if (state->markd == XML_REGEXP_MARK_VISITED) |
| return(ret); |
| |
| if (ctxt->flags & AM_AUTOMATA_RNG) |
| deep = 0; |
| |
| /* |
| * don't recurse on transitions potentially added in the course of |
| * the elimination. |
| */ |
| nbTrans = state->nbTrans; |
| for (transnr = 0;transnr < nbTrans;transnr++) { |
| t1 = &(state->trans[transnr]); |
| /* |
| * check transitions conflicting with the one looked at |
| */ |
| if (t1->atom == NULL) { |
| if (t1->to < 0) |
| continue; |
| state->markd = XML_REGEXP_MARK_VISITED; |
| res = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to], |
| to, atom); |
| if (res == 0) { |
| ret = 0; |
| /* t1->nd = 1; */ |
| } |
| continue; |
| } |
| if (t1->to != to) |
| continue; |
| if (xmlFACompareAtoms(t1->atom, atom, deep)) { |
| ret = 0; |
| /* mark the transition as non-deterministic */ |
| t1->nd = 1; |
| } |
| } |
| return(ret); |
| } |
| |
| /** |
| * xmlFAFinishRecurseDeterminism: |
| * @ctxt: a regexp parser context |
| * |
| * Reset flags after checking determinism. |
| */ |
| static void |
| xmlFAFinishRecurseDeterminism(xmlRegParserCtxtPtr ctxt, xmlRegStatePtr state) { |
| int transnr, nbTrans; |
| |
| if (state == NULL) |
| return; |
| if (state->markd != XML_REGEXP_MARK_VISITED) |
| return; |
| state->markd = 0; |
| |
| nbTrans = state->nbTrans; |
| for (transnr = 0; transnr < nbTrans; transnr++) { |
| xmlRegTransPtr t1 = &state->trans[transnr]; |
| if ((t1->atom == NULL) && (t1->to >= 0)) |
| xmlFAFinishRecurseDeterminism(ctxt, ctxt->states[t1->to]); |
| } |
| } |
| |
| /** |
| * xmlFAComputesDeterminism: |
| * @ctxt: a regexp parser context |
| * |
| * Check whether the associated regexp is determinist, |
| * should be called after xmlFAEliminateEpsilonTransitions() |
| * |
| */ |
| static int |
| xmlFAComputesDeterminism(xmlRegParserCtxtPtr ctxt) { |
| int statenr, transnr; |
| xmlRegStatePtr state; |
| xmlRegTransPtr t1, t2, last; |
| int i; |
| int ret = 1; |
| int deep = 1; |
| |
| #ifdef DEBUG_REGEXP_GRAPH |
| printf("xmlFAComputesDeterminism\n"); |
| xmlRegPrintCtxt(stdout, ctxt); |
| #endif |
| if (ctxt->determinist != -1) |
| return(ctxt->determinist); |
| |
| if (ctxt->flags & AM_AUTOMATA_RNG) |
| deep = 0; |
| |
| /* |
| * First cleanup the automata removing cancelled transitions |
| */ |
| for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
| state = ctxt->states[statenr]; |
| if (state == NULL) |
| continue; |
| if (state->nbTrans < 2) |
| continue; |
| for (transnr = 0;transnr < state->nbTrans;transnr++) { |
| t1 = &(state->trans[transnr]); |
| /* |
| * Determinism checks in case of counted or all transitions |
| * will have to be handled separately |
| */ |
| if (t1->atom == NULL) { |
| /* t1->nd = 1; */ |
| continue; |
| } |
| if (t1->to == -1) /* eliminated */ |
| continue; |
| for (i = 0;i < transnr;i++) { |
| t2 = &(state->trans[i]); |
| if (t2->to == -1) /* eliminated */ |
| continue; |
| if (t2->atom != NULL) { |
| if (t1->to == t2->to) { |
| /* |
| * Here we use deep because we want to keep the |
| * transitions which indicate a conflict |
| */ |
| if (xmlFAEqualAtoms(t1->atom, t2->atom, deep) && |
| (t1->counter == t2->counter) && |
| (t1->count == t2->count)) |
| t2->to = -1; /* eliminated */ |
| } |
| } |
| } |
| } |
| } |
| |
| /* |
| * Check for all states that there aren't 2 transitions |
| * with the same atom and a different target. |
| */ |
| for (statenr = 0;statenr < ctxt->nbStates;statenr++) { |
| state = ctxt->states[statenr]; |
| if (state == NULL) |
| continue; |
| if (state->nbTrans < 2) |
| continue; |
| last = NULL; |
| for (transnr = 0;transnr < state->nbTrans;transnr++) { |
| t1 = &(state->trans[transnr]); |
| /* |
| * Determinism checks in case of counted or all transitions |
| * will have to be handled separately |
| */ |
| if (t1->atom == NULL) { |
| continue; |
| } |
| if (t1->to == -1) /* eliminated */ |
| continue; |
| for (i = 0;i < transnr;i++) { |
| t2 = &(state->trans[i]); |
| if (t2->to == -1) /* eliminated */ |
| continue; |
| if (t2->atom != NULL) { |
| /* |
| * But here we don't use deep because we want to |
| * find transitions which indicate a conflict |
| */ |
| if (xmlFACompareAtoms(t1->atom, t2->atom, 1)) { |
| ret = 0; |
| /* mark the transitions as non-deterministic ones */ |
| t1->nd = 1; |
| t2->nd = 1; |
| last = t1; |
| } |
| } else if (t1->to != -1) { |
| /* |
| * do the closure in case of remaining specific |
| * epsilon transitions like choices or all |
| */ |
| ret = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to], |
| t2->to, t2->atom); |
| xmlFAFinishRecurseDeterminism(ctxt, ctxt->states[t1->to]); |
| /* don't shortcut the computation so all non deterministic |
| transition get marked down |
| if (ret == 0) |
| return(0); |
| */ |
| if (ret == 0) { |
| t1->nd = 1; |
| /* t2->nd = 1; */ |
| last = t1; |
| } |
| } |
| } |
| /* don't shortcut the computation so all non deterministic |
| transition get marked down |
| if (ret == 0) |
| break; */ |
| } |
| |
| /* |
| * mark specifically the last non-deterministic transition |
| * from a state since there is no need to set-up rollback |
| * from it |
| */ |
| if (last != NULL) { |
| last->nd = 2; |
| } |
| |
| /* don't shortcut the computation so all non deterministic |
| transition get marked down |
| if (ret == 0) |
| break; */ |
| } |
| |
| ctxt->determinist = ret; |
| return(ret); |
| } |
| |
| /************************************************************************ |
| * * |
| * Routines to check input against transition atoms * |
| * * |
| ************************************************************************/ |
| |
| static int |
| xmlRegCheckCharacterRange(xmlRegAtomType type, int codepoint, int neg, |
| int start, int end, const xmlChar *blockName) { |
| int ret = 0; |
| |
| switch (type) { |
| case XML_REGEXP_STRING: |
| case XML_REGEXP_SUBREG: |
| case XML_REGEXP_RANGES: |
| case XML_REGEXP_EPSILON: |
| return(-1); |
| case XML_REGEXP_ANYCHAR: |
| ret = ((codepoint != '\n') && (codepoint != '\r')); |
| break; |
| case XML_REGEXP_CHARVAL: |
| ret = ((codepoint >= start) && (codepoint <= end)); |
| break; |
| case XML_REGEXP_NOTSPACE: |
| neg = !neg; |
| /* Falls through. */ |
| case XML_REGEXP_ANYSPACE: |
| ret = ((codepoint == '\n') || (codepoint == '\r') || |
| (codepoint == '\t') || (codepoint == ' ')); |
| break; |
| case XML_REGEXP_NOTINITNAME: |
| neg = !neg; |
| /* Falls through. */ |
| case XML_REGEXP_INITNAME: |
| ret = (IS_LETTER(codepoint) || |
| (codepoint == '_') || (codepoint == ':')); |
| break; |
| case XML_REGEXP_NOTNAMECHAR: |
| neg = !neg; |
| /* Falls through. */ |
| case XML_REGEXP_NAMECHAR: |
| ret = (IS_LETTER(codepoint) || IS_DIGIT(codepoint) || |
| (codepoint == '.') || (codepoint == '-') || |
| (codepoint == '_') || (codepoint == ':') || |
| IS_COMBINING(codepoint) || IS_EXTENDER(codepoint)); |
| break; |
| case XML_REGEXP_NOTDECIMAL: |
| neg = !neg; |
| /* Falls through. */ |
| case XML_REGEXP_DECIMAL: |
| ret = xmlUCSIsCatNd(codepoint); |
| break; |
| case XML_REGEXP_REALCHAR: |
| neg = !neg; |
| /* Falls through. */ |
| case XML_REGEXP_NOTREALCHAR: |
| ret = xmlUCSIsCatP(codepoint); |
| if (ret == 0) |
| ret = xmlUCSIsCatZ(codepoint); |
| if (ret == 0) |
| ret = xmlUCSIsCatC(codepoint); |
| break; |
| case XML_REGEXP_LETTER: |
| ret = xmlUCSIsCatL(codepoint); |
| break; |
| case XML_REGEXP_LETTER_UPPERCASE: |
| ret = xmlUCSIsCatLu(codepoint); |
| break; |
| case XML_REGEXP_LETTER_LOWERCASE: |
| ret = xmlUCSIsCatLl(codepoint); |
| break; |
| case XML_REGEXP_LETTER_TITLECASE: |
| ret = xmlUCSIsCatLt(codepoint); |
| break; |
| case XML_REGEXP_LETTER_MODIFIER: |
| ret = xmlUCSIsCatLm(codepoint); |
| break; |
| case XML_REGEXP_LETTER_OTHERS: |
| ret = xmlUCSIsCatLo(codepoint); |
| break; |
| case XML_REGEXP_MARK: |
| ret = xmlUCSIsCatM(codepoint); |
| break; |
| case XML_REGEXP_MARK_NONSPACING: |
| ret = xmlUCSIsCatMn(codepoint); |
| break; |
| case XML_REGEXP_MARK_SPACECOMBINING: |
| ret = xmlUCSIsCatMc(codepoint); |
| break; |
| case XML_REGEXP_MARK_ENCLOSING: |
| ret = xmlUCSIsCatMe(codepoint); |
| break; |
| case XML_REGEXP_NUMBER: |
| ret = xmlUCSIsCatN(codepoint); |
| break; |
| case XML_REGEXP_NUMBER_DECIMAL: |
| ret = xmlUCSIsCatNd(codepoint); |
| break; |
| case XML_REGEXP_NUMBER_LETTER: |
| ret = xmlUCSIsCatNl(codepoint); |
| break; |
| case XML_REGEXP_NUMBER_OTHERS: |
| ret = xmlUCSIsCatNo(codepoint); |
| break; |
| case XML_REGEXP_PUNCT: |
| ret = xmlUCSIsCatP(codepoint); |
| break; |
| case XML_REGEXP_PUNCT_CONNECTOR: |
| ret = xmlUCSIsCatPc(codepoint); |
| break; |
| case XML_REGEXP_PUNCT_DASH: |
| ret = xmlUCSIsCatPd(codepoint); |
| break; |
| case XML_REGEXP_PUNCT_OPEN: |
| ret = xmlUCSIsCatPs(codepoint); |
| break; |
| case XML_REGEXP_PUNCT_CLOSE: |
| ret = xmlUCSIsCatPe(codepoint); |
| break; |
| case XML_REGEXP_PUNCT_INITQUOTE: |
| ret = xmlUCSIsCatPi(codepoint); |
| break; |
| case XML_REGEXP_PUNCT_FINQUOTE: |
| ret = xmlUCSIsCatPf(codepoint); |
| break; |
| case XML_REGEXP_PUNCT_OTHERS: |
| ret = xmlUCSIsCatPo(codepoint); |
| break; |
| case XML_REGEXP_SEPAR: |
| ret = xmlUCSIsCatZ(codepoint); |
| break; |
| case XML_REGEXP_SEPAR_SPACE: |
| ret = xmlUCSIsCatZs(codepoint); |
| break; |
| case XML_REGEXP_SEPAR_LINE: |
| |