diff options
author | dkf <dkf@noemail.net> | 2007-12-18 10:53:14 (GMT) |
---|---|---|
committer | dkf <dkf@noemail.net> | 2007-12-18 10:53:14 (GMT) |
commit | 89dcee88bee43586acd1910cdf537e5238c940a0 (patch) | |
tree | 73535333530cb8bb79ed8d41856c01d0f6dc4fd0 /generic/regc_nfa.c | |
parent | 6b67fc3de3834c7b50bde5cb66eb0458359d3bd3 (diff) | |
download | tcl-89dcee88bee43586acd1910cdf537e5238c940a0.zip tcl-89dcee88bee43586acd1910cdf537e5238c940a0.tar.gz tcl-89dcee88bee43586acd1910cdf537e5238c940a0.tar.bz2 |
Fixes for problems created when processing regular expressions that
generate very large automata. An enormous number of thanks to Will
Drewry <wad@google.com>, Tavis Ormandy <taviso@google.com>, and Tom
Lane <tgl@sss.pgh.pa.us> from the Postgresql crowd for their help in
tracking these problems down. [Bug 1810264]
FossilOrigin-Name: 8c98744456467a38e11dab4d25961ee3edd46834
Diffstat (limited to 'generic/regc_nfa.c')
-rw-r--r-- | generic/regc_nfa.c | 75 |
1 files changed, 73 insertions, 2 deletions
diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c index 741887f..19dbe63 100644 --- a/generic/regc_nfa.c +++ b/generic/regc_nfa.c @@ -58,13 +58,14 @@ newnfa( nfa->nstates = 0; nfa->cm = cm; nfa->v = v; + nfa->size = 0; nfa->bos[0] = nfa->bos[1] = COLORLESS; nfa->eos[0] = nfa->eos[1] = COLORLESS; + nfa->parent = parent; /* Precedes newfstate so parent is valid. */ nfa->post = newfstate(nfa, '@'); /* number 0 */ nfa->pre = newfstate(nfa, '>'); /* number 1 */ - nfa->parent = parent; - nfa->init = newstate(nfa); /* may become invalid later */ + nfa->init = newstate(nfa); /* May become invalid later. */ nfa->final = newstate(nfa); if (ISERR()) { freenfa(nfa); @@ -85,6 +86,61 @@ newnfa( } /* + - TooManyStates - checks if the max states exceeds the compile-time value + ^ static int TooManyStates(struct nfa *); + */ +static int +TooManyStates( + struct nfa *nfa) +{ + struct nfa *parent = nfa->parent; + size_t sz = nfa->size; + + while (parent != NULL) { + sz = parent->size; + parent = parent->parent; + } + if (sz > REG_MAX_STATES) { + return 1; + } + return 0; +} + +/* + - IncrementSize - increases the tracked size of the NFA and its parents. + ^ static void IncrementSize(struct nfa *); + */ +static void +IncrementSize( + struct nfa *nfa) +{ + struct nfa *parent = nfa->parent; + + nfa->size++; + while (parent != NULL) { + parent->size++; + parent = parent->parent; + } +} + +/* + - DecrementSize - increases the tracked size of the NFA and its parents. + ^ static void DecrementSize(struct nfa *); + */ +static void +DecrementSize( + struct nfa *nfa) +{ + struct nfa *parent = nfa->parent; + + nfa->size--; + while (parent != NULL) { + parent->size--; + parent = parent->parent; + } +} + +/* - freenfa - free an entire NFA ^ static VOID freenfa(struct nfa *); */ @@ -120,6 +176,11 @@ newstate( { struct state *s; + if (TooManyStates(nfa)) { + /* XXX: add specific error for this */ + NERR(REG_ETOOBIG); + return NULL; + } if (nfa->free != NULL) { s = nfa->free; nfa->free = s->next; @@ -152,6 +213,12 @@ newstate( } s->prev = nfa->slast; nfa->slast = s; + + /* + * Track the current size and the parent size. + */ + + IncrementSize(nfa); return s; } @@ -222,6 +289,7 @@ freestate( s->prev = NULL; s->next = nfa->free; /* don't delete it, put it on the free list */ nfa->free = s; + DecrementSize(nfa); } /* @@ -688,6 +756,9 @@ duptraverse( for (a=s->outs ; a!=NULL && !NISERR() ; a=a->outchain) { duptraverse(nfa, a->to, NULL); + if (NISERR()) { + break; + } assert(a->to->tmp != NULL); cparc(nfa, a, s->tmp, a->to->tmp); } |