diff options
-rw-r--r-- | generic/regc_color.c | 45 | ||||
-rw-r--r-- | generic/regc_cvec.c | 7 | ||||
-rw-r--r-- | generic/regc_lex.c | 65 | ||||
-rw-r--r-- | generic/regc_locale.c | 2 | ||||
-rw-r--r-- | generic/regc_nfa.c | 127 | ||||
-rw-r--r-- | generic/regcomp.c | 190 | ||||
-rw-r--r-- | generic/regcustom.h | 22 | ||||
-rw-r--r-- | generic/rege_dfa.c | 241 | ||||
-rw-r--r-- | generic/regerror.c | 4 | ||||
-rw-r--r-- | generic/regex.h | 71 | ||||
-rw-r--r-- | generic/regexec.c | 1132 | ||||
-rw-r--r-- | generic/regfronts.c | 6 | ||||
-rw-r--r-- | generic/regguts.h | 80 |
13 files changed, 1078 insertions, 914 deletions
diff --git a/generic/regc_color.c b/generic/regc_color.c index 35e7904..92e0aad 100644 --- a/generic/regc_color.c +++ b/generic/regc_color.c @@ -37,7 +37,7 @@ /* - initcm - set up new colormap - ^ static VOID initcm(struct vars *, struct colormap *); + ^ static void initcm(struct vars *, struct colormap *); */ static void initcm( @@ -88,7 +88,7 @@ initcm( /* - freecm - free dynamically-allocated things in a colormap - ^ static VOID freecm(struct colormap *); + ^ static void freecm(struct colormap *); */ static void freecm( @@ -116,7 +116,7 @@ freecm( /* - cmtreefree - free a non-terminal part of a colormap tree - ^ static VOID cmtreefree(struct colormap *, union tree *, int); + ^ static void cmtreefree(struct colormap *, union tree *, int); */ static void cmtreefree( @@ -294,7 +294,7 @@ newcolor( /* - freecolor - free a color (must have no arcs or subcolor) - ^ static VOID freecolor(struct colormap *, pcolor); + ^ static void freecolor(struct colormap *, pcolor); */ static void freecolor( @@ -327,7 +327,7 @@ freecolor( cm->free = cm->cd[cm->free].sub; } if (cm->free > 0) { - assert(cm->free < cm->max); + assert((size_t)cm->free < cm->max); pco = cm->free; nco = cm->cd[pco].sub; while (nco > 0) { @@ -339,7 +339,7 @@ freecolor( nco = cm->cd[nco].sub; cm->cd[pco].sub = nco; } else { - assert(nco < cm->max); + assert((size_t)nco < cm->max); pco = nco; nco = cm->cd[pco].sub; } @@ -429,7 +429,7 @@ newsub( /* - subrange - allocate new subcolors to this range of chrs, fill in arcs - ^ static VOID subrange(struct vars *, pchr, pchr, struct state *, + ^ static void subrange(struct vars *, pchr, pchr, struct state *, ^ struct state *); */ static void @@ -477,7 +477,7 @@ subrange( /* - subblock - allocate new subcolors for one tree block of chrs, fill in arcs - ^ static VOID subblock(struct vars *, pchr, struct state *, struct state *); + ^ static void subblock(struct vars *, pchr, struct state *, struct state *); */ static void subblock( @@ -582,7 +582,7 @@ subblock( /* - okcolors - promote subcolors to full colors - ^ static VOID okcolors(struct nfa *, struct colormap *); + ^ static void okcolors(struct nfa *, struct colormap *); */ static void okcolors( @@ -643,7 +643,7 @@ okcolors( /* - colorchain - add this arc to the color chain of its color - ^ static VOID colorchain(struct colormap *, struct arc *); + ^ static void colorchain(struct colormap *, struct arc *); */ static void colorchain( @@ -662,7 +662,7 @@ colorchain( /* - uncolorchain - delete this arc from the color chain of its color - ^ static VOID uncolorchain(struct colormap *, struct arc *); + ^ static void uncolorchain(struct colormap *, struct arc *); */ static void uncolorchain( @@ -688,7 +688,7 @@ uncolorchain( /* - rainbow - add arcs of all full colors (but one) between specified states - ^ static VOID rainbow(struct nfa *, struct colormap *, int, pcolor, + ^ static void rainbow(struct nfa *, struct colormap *, int, pcolor, ^ struct state *, struct state *); */ static void @@ -715,7 +715,7 @@ rainbow( /* - colorcomplement - add arcs of complementary colors * The calling sequence ought to be reconciled with cloneouts(). - ^ static VOID colorcomplement(struct nfa *, struct colormap *, int, + ^ static void colorcomplement(struct nfa *, struct colormap *, int, ^ struct state *, struct state *, struct state *); */ static void @@ -748,7 +748,7 @@ colorcomplement( /* - dumpcolors - debugging output - ^ static VOID dumpcolors(struct colormap *, FILE *); + ^ static void dumpcolors(struct colormap *, FILE *); */ static void dumpcolors( @@ -777,18 +777,19 @@ dumpcolors( } /* - * It's hard to do this more efficiently. + * Unfortunately, it's hard to do this next bit more efficiently. + * + * Spencer's original coding has the loop iterating from CHR_MIN + * to CHR_MAX, but that's utterly unusable for 32-bit chr, or + * even 16-bit. For debugging purposes it seems fine to print + * only chr codes up to 1000 or so. */ - for (c=CHR_MIN ; c<CHR_MAX ; c++) { + for (c=CHR_MIN ; c<1000 ; c++) { if (GETCOLOR(cm, c) == co) { dumpchr(c, f); } } - assert(c == CHR_MAX); - if (GETCOLOR(cm, c) == co) { - dumpchr(c, f); - } fprintf(f, "\n"); } } @@ -796,7 +797,7 @@ dumpcolors( /* - fillcheck - check proper filling of a tree - ^ static VOID fillcheck(struct colormap *, union tree *, int, FILE *); + ^ static void fillcheck(struct colormap *, union tree *, int, FILE *); */ static void fillcheck( @@ -825,7 +826,7 @@ fillcheck( /* - dumpchr - print a chr * Kind of char-centric but works well enough for debug use. - ^ static VOID dumpchr(pchr, FILE *); + ^ static void dumpchr(pchr, FILE *); */ static void dumpchr( diff --git a/generic/regc_cvec.c b/generic/regc_cvec.c index 64f34cd..d450d3e 100644 --- a/generic/regc_cvec.c +++ b/generic/regc_cvec.c @@ -74,19 +74,20 @@ clearcvec( /* - addchr - add a chr to a cvec - ^ static VOID addchr(struct cvec *, pchr); + ^ static void addchr(struct cvec *, pchr); */ static void addchr( struct cvec *cv, /* character vector */ pchr c) /* character to add */ { + assert(cv->nchrs < cv->chrspace); cv->chrs[cv->nchrs++] = (chr)c; } /* - addrange - add a range to a cvec - ^ static VOID addrange(struct cvec *, pchr, pchr); + ^ static void addrange(struct cvec *, pchr, pchr); */ static void addrange( @@ -128,7 +129,7 @@ getcvec( /* - freecvec - free a cvec - ^ static VOID freecvec(struct cvec *); + ^ static void freecvec(struct cvec *); */ static void freecvec( diff --git a/generic/regc_lex.c b/generic/regc_lex.c index 8d07c59..16e3ae9 100644 --- a/generic/regc_lex.c +++ b/generic/regc_lex.c @@ -63,7 +63,7 @@ /* - lexstart - set up lexical stuff, scan leading options - ^ static VOID lexstart(struct vars *); + ^ static void lexstart(struct vars *); */ static void lexstart( @@ -89,7 +89,7 @@ lexstart( /* - prefixes - implement various special prefixes - ^ static VOID prefixes(struct vars *); + ^ static void prefixes(struct vars *); */ static void prefixes( @@ -207,7 +207,7 @@ prefixes( - lexnest - "call a subroutine", interpolating string at the lexical level * Note, this is not a very general facility. There are a number of * implicit assumptions about what sorts of strings can be subroutines. - ^ static VOID lexnest(struct vars *, const chr *, const chr *); + ^ static void lexnest(struct vars *, const chr *, const chr *); */ static void lexnest( @@ -275,7 +275,7 @@ static const chr brbackw[] = { /* \w within brackets */ /* - lexword - interpolate a bracket expression for word characters * Possibly ought to inquire whether there is a "word" character class. - ^ static VOID lexword(struct vars *); + ^ static void lexword(struct vars *); */ static void lexword( @@ -742,6 +742,7 @@ lexescape( struct vars *v) { chr c; + int i; static const chr alert[] = { CHR('a'), CHR('l'), CHR('e'), CHR('r'), CHR('t') }; @@ -818,18 +819,23 @@ lexescape( RETV(PLAIN, CHR('\t')); break; case CHR('u'): - c = lexdigits(v, 16, 4, 4); + c = (uchr) lexdigits(v, 16, 1, 4); if (ISERR()) { FAILW(REG_EESCAPE); } RETV(PLAIN, c); break; case CHR('U'): - c = lexdigits(v, 16, 8, 8); + i = lexdigits(v, 16, 1, 8); if (ISERR()) { FAILW(REG_EESCAPE); } - RETV(PLAIN, c); + if (i > 0xFFFF) { + /* TODO: output a Surrogate pair + */ + i = 0xFFFD; + } + RETV(PLAIN, (uchr) i); break; case CHR('v'): RETV(PLAIN, CHR('\v')); @@ -844,7 +850,7 @@ lexescape( break; case CHR('x'): NOTE(REG_UUNPORT); - c = lexdigits(v, 16, 1, 255); /* REs >255 long outside spec */ + c = (uchr) lexdigits(v, 16, 1, 2); if (ISERR()) { FAILW(REG_EESCAPE); } @@ -866,7 +872,7 @@ lexescape( case CHR('9'): save = v->now; v->now--; /* put first digit back */ - c = lexdigits(v, 10, 1, 255); /* REs >255 long outside spec */ + c = (uchr) lexdigits(v, 10, 1, 255); /* REs >255 long outside spec */ if (ISERR()) { FAILW(REG_EESCAPE); } @@ -893,10 +899,15 @@ lexescape( case CHR('0'): NOTE(REG_UUNPORT); v->now--; /* put first digit back */ - c = lexdigits(v, 8, 1, 3); + c = (uchr) lexdigits(v, 8, 1, 3); if (ISERR()) { FAILW(REG_EESCAPE); } + if (c > 0xff) { + /* out of range, so we handled one digit too much */ + v->now--; + c >>= 3; + } RETV(PLAIN, c); break; default: @@ -909,23 +920,27 @@ lexescape( /* - lexdigits - slurp up digits and return chr value - ^ static chr lexdigits(struct vars *, int, int, int); + ^ static int lexdigits(struct vars *, int, int, int); */ -static chr /* chr value; errors signalled via ERR */ +static int /* chr value; errors signalled via ERR */ lexdigits( struct vars *v, int base, int minlen, int maxlen) { - uchr n; /* unsigned to avoid overflow misbehavior */ + int n; int len; chr c; int d; - CONST uchr ub = (uchr) base; + const uchr ub = (uchr) base; n = 0; for (len = 0; len < maxlen && !ATEOS(); len++) { + if (n > 0x10fff) { + /* Stop when continuing would otherwise overflow */ + break; + } c = *v->now++; switch (c) { case CHR('0'): case CHR('1'): case CHR('2'): case CHR('3'): @@ -958,7 +973,7 @@ lexdigits( ERR(REG_EESCAPE); } - return (chr)n; + return n; } /* @@ -1080,7 +1095,7 @@ brenext( /* - skip - skip white space and comments in expanded form - ^ static VOID skip(struct vars *); + ^ static void skip(struct vars *); */ static void skip( @@ -1124,24 +1139,6 @@ newline(void) } /* - - ch - return the chr sequence for regc_locale.c's fake collating element ch - * This helps confine use of CHR to this source file. Beware that the caller - * knows how long the sequence is. - ^ #ifdef REG_DEBUG - ^ static const chr *ch(NOPARMS); - ^ #endif - */ -#ifdef REG_DEBUG -static const chr * -ch(void) -{ - static const chr chstr[] = { CHR('c'), CHR('h'), CHR('\0') }; - - return chstr; -} -#endif - -/* - chrnamed - return the chr known by a given (chr string) name * The code is a bit clumsy, but this routine gets only such specialized * use that it hardly matters. diff --git a/generic/regc_locale.c b/generic/regc_locale.c index 2a4248e..3c10cb6 100644 --- a/generic/regc_locale.c +++ b/generic/regc_locale.c @@ -389,7 +389,7 @@ static const crange spaceRangeTable[] = { #define NUM_SPACE_RANGE (sizeof(spaceRangeTable)/sizeof(crange)) static const chr spaceCharTable[] = { - 0x20, 0xa0, 0x1680, 0x180e, 0x2028, 0x2029, 0x202f, 0x205f, + 0x20, 0x85, 0xa0, 0x1680, 0x180e, 0x2028, 0x2029, 0x202f, 0x205f, 0x2060, 0x3000, 0xfeff }; diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c index 6280e5e..088c6c0 100644 --- a/generic/regc_nfa.c +++ b/generic/regc_nfa.c @@ -90,7 +90,7 @@ newnfa( /* - freenfa - free an entire NFA - ^ static VOID freenfa(struct nfa *); + ^ static void freenfa(struct nfa *); */ static void freenfa( @@ -184,7 +184,7 @@ newfstate( /* - dropstate - delete a state's inarcs and outarcs and free it - ^ static VOID dropstate(struct nfa *, struct state *); + ^ static void dropstate(struct nfa *, struct state *); */ static void dropstate( @@ -204,7 +204,7 @@ dropstate( /* - freestate - free a state, which has no in-arcs or out-arcs - ^ static VOID freestate(struct nfa *, struct state *); + ^ static void freestate(struct nfa *, struct state *); */ static void freestate( @@ -235,7 +235,7 @@ freestate( /* - destroystate - really get rid of an already-freed state - ^ static VOID destroystate(struct nfa *, struct state *); + ^ static void destroystate(struct nfa *, struct state *); */ static void destroystate( @@ -260,7 +260,7 @@ destroystate( /* - newarc - set up a new arc within an NFA - ^ static VOID newarc(struct nfa *, int, pcolor, struct state *, + ^ static void newarc(struct nfa *, int, pcolor, struct state *, ^ struct state *); */ /* @@ -293,7 +293,7 @@ newarc( } } } - + /* no dup, so create the arc */ createarc(nfa, t, co, from, to); } @@ -410,7 +410,7 @@ allocarc( /* - freearc - free an arc - ^ static VOID freearc(struct nfa *, struct arc *); + ^ static void freearc(struct nfa *, struct arc *); */ static void freearc( @@ -569,7 +569,7 @@ findarc( /* - cparc - allocate a new arc within an NFA, copying details from old one - ^ static VOID cparc(struct nfa *, struct arc *, struct state *, + ^ static void cparc(struct nfa *, struct arc *, struct state *, ^ struct state *); */ static void @@ -657,7 +657,7 @@ sortins_cmp( } return 0; } - + /* * sortouts - sort the out arcs of a state by to/color/type */ @@ -756,7 +756,7 @@ sortouts_cmp( * checks become too slow. In that case we proceed by sorting and merging * the arc lists, and then we can indeed just update the arcs in-place. * - ^ static VOID moveins(struct nfa *, struct state *, struct state *); + ^ static void moveins(struct nfa *, struct state *, struct state *); */ static void moveins( @@ -1016,7 +1016,7 @@ mergeins( /* - moveouts - move all out arcs of a state to another state - ^ static VOID moveouts(struct nfa *, struct state *, struct state *); + ^ static void moveouts(struct nfa *, struct state *, struct state *); */ static void moveouts( @@ -1176,7 +1176,7 @@ copyouts( /* - cloneouts - copy out arcs of a state to another state pair, modifying type - ^ static VOID cloneouts(struct nfa *, struct state *, struct state *, + ^ static void cloneouts(struct nfa *, struct state *, struct state *, ^ struct state *, int); */ static void @@ -1200,7 +1200,7 @@ cloneouts( - delsub - delete a sub-NFA, updating subre pointers if necessary * This uses a recursive traversal of the sub-NFA, marking already-seen * states using their tmp pointer. - ^ static VOID delsub(struct nfa *, struct state *, struct state *); + ^ static void delsub(struct nfa *, struct state *, struct state *); */ static void delsub( @@ -1223,7 +1223,7 @@ delsub( /* - deltraverse - the recursive heart of delsub * This routine's basic job is to destroy all out-arcs of the state. - ^ static VOID deltraverse(struct nfa *, struct state *, struct state *); + ^ static void deltraverse(struct nfa *, struct state *, struct state *); */ static void deltraverse( @@ -1266,7 +1266,7 @@ deltraverse( * Another recursive traversal, this time using tmp to point to duplicates as * well as mark already-seen states. (You knew there was a reason why it's a * state pointer, didn't you? :-)) - ^ static VOID dupnfa(struct nfa *, struct state *, struct state *, + ^ static void dupnfa(struct nfa *, struct state *, struct state *, ^ struct state *, struct state *); */ static void @@ -1283,7 +1283,7 @@ dupnfa( } stop->tmp = to; - duptraverse(nfa, start, from); + duptraverse(nfa, start, from, 0); /* done, except for clearing out the tmp pointers */ stop->tmp = NULL; @@ -1292,13 +1292,14 @@ dupnfa( /* - duptraverse - recursive heart of dupnfa - ^ static VOID duptraverse(struct nfa *, struct state *, struct state *); + ^ static void duptraverse(struct nfa *, struct state *, struct state *); */ static void duptraverse( struct nfa *nfa, struct state *s, - struct state *stmp) /* s's duplicate, or NULL */ + struct state *stmp, /* s's duplicate, or NULL */ + int depth) { struct arc *a; @@ -1312,8 +1313,20 @@ duptraverse( return; } + /* + * Arbitrary depth limit. Needs tuning, but this value is sufficient to + * make all normal tests (not reg-33.14) pass. + */ +#ifndef DUPTRAVERSE_MAX_DEPTH +#define DUPTRAVERSE_MAX_DEPTH 15000 +#endif + + if (depth++ > DUPTRAVERSE_MAX_DEPTH) { + NERR(REG_ESPACE); + } + for (a=s->outs ; a!=NULL && !NISERR() ; a=a->outchain) { - duptraverse(nfa, a->to, NULL); + duptraverse(nfa, a->to, NULL, depth); if (NISERR()) { break; } @@ -1324,7 +1337,7 @@ duptraverse( /* - cleartraverse - recursive cleanup for algorithms that leave tmp ptrs set - ^ static VOID cleartraverse(struct nfa *, struct state *); + ^ static void cleartraverse(struct nfa *, struct state *); */ static void cleartraverse( @@ -1345,7 +1358,7 @@ cleartraverse( /* - specialcolors - fill in special colors for an NFA - ^ static VOID specialcolors(struct nfa *); + ^ static void specialcolors(struct nfa *); */ static void specialcolors( @@ -1428,7 +1441,7 @@ optimize( /* - pullback - pull back constraints backward to eliminate them - ^ static VOID pullback(struct nfa *, FILE *); + ^ static void pullback(struct nfa *, FILE *); */ static void pullback( @@ -1608,7 +1621,7 @@ pull( /* - pushfwd - push forward constraints forward to eliminate them - ^ static VOID pushfwd(struct nfa *, FILE *); + ^ static void pushfwd(struct nfa *, FILE *); */ static void pushfwd( @@ -1847,7 +1860,7 @@ combine( /* - fixempties - get rid of EMPTY arcs - ^ static VOID fixempties(struct nfa *, FILE *); + ^ static void fixempties(struct nfa *, FILE *); */ static void fixempties( @@ -2007,7 +2020,7 @@ fixempties( arcarray[arccount++] = a; } } - + /* Reset the tmp fields as we walk back */ nexts = s2->tmp; s2->tmp = NULL; @@ -2029,7 +2042,7 @@ fixempties( } inarcsorig[s->no] = a; } - + FREE(arcarray); FREE(inarcsorig); @@ -2180,7 +2193,7 @@ fixconstraintloops( dropstate(nfa, s); } } - + /* Nothing to do if no remaining constraint arcs */ if (NISERR() || !hasconstraints) { return; @@ -2670,7 +2683,7 @@ clonesuccessorstates( /* - cleanup - clean up NFA after optimizations - ^ static VOID cleanup(struct nfa *); + ^ static void cleanup(struct nfa *); */ static void cleanup( @@ -2711,7 +2724,7 @@ cleanup( /* - markreachable - recursive marking of reachable states - ^ static VOID markreachable(struct nfa *, struct state *, struct state *, + ^ static void markreachable(struct nfa *, struct state *, struct state *, ^ struct state *); */ static void @@ -2735,7 +2748,7 @@ markreachable( /* - markcanreach - recursive marking of states which can reach here - ^ static VOID markcanreach(struct nfa *, struct state *, struct state *, + ^ static void markcanreach(struct nfa *, struct state *, struct state *, ^ struct state *); */ static void @@ -2783,7 +2796,7 @@ analyze( /* - compact - construct the compact representation of an NFA - ^ static VOID compact(struct nfa *, struct cnfa *); + ^ static void compact(struct nfa *, struct cnfa *); */ static void compact( @@ -2803,13 +2816,16 @@ compact( narcs = 0; for (s = nfa->states; s != NULL; s = s->next) { nstates++; - narcs += 1 + s->nouts + 1; - /* 1 as a fake for flags, nouts for arcs, 1 as endmarker */ + narcs += s->nouts + 1; /* need one extra for endmarker */ } + cnfa->stflags = (char *) MALLOC(nstates * sizeof(char)); cnfa->states = (struct carc **) MALLOC(nstates * sizeof(struct carc *)); cnfa->arcs = (struct carc *) MALLOC(narcs * sizeof(struct carc)); - if (cnfa->states == NULL || cnfa->arcs == NULL) { + if (cnfa->stflags == NULL || cnfa->states == NULL || cnfa->arcs == NULL) { + if (cnfa->stflags != NULL) { + FREE(cnfa->stflags); + } if (cnfa->states != NULL) { FREE(cnfa->states); } @@ -2832,9 +2848,8 @@ compact( ca = cnfa->arcs; for (s = nfa->states; s != NULL; s = s->next) { assert((size_t) s->no < nstates); + cnfa->stflags[s->no] = 0; cnfa->states[s->no] = ca; - ca->co = 0; /* clear and skip flags "arc" */ - ca++; first = ca; for (a = s->outs; a != NULL; a = a->outchain) { switch (a->type) { @@ -2868,14 +2883,14 @@ compact( */ for (a = nfa->pre->outs; a != NULL; a = a->outchain) { - cnfa->states[a->to->no]->co = 1; + cnfa->stflags[a->to->no] = CNFA_NOPROGRESS; } - cnfa->states[nfa->pre->no]->co = 1; + cnfa->stflags[nfa->pre->no] = CNFA_NOPROGRESS; } /* - carcsort - sort compacted-NFA arcs by color - ^ static VOID carcsort(struct carc *, struct carc *); + ^ static void carcsort(struct carc *, struct carc *); */ static void carcsort( @@ -2894,7 +2909,7 @@ carc_cmp( { const struct carc *aa = (const struct carc *) a; const struct carc *bb = (const struct carc *) b; - + if (aa->co < bb->co) { return -1; } @@ -2912,7 +2927,7 @@ carc_cmp( /* - freecnfa - free a compacted NFA - ^ static VOID freecnfa(struct cnfa *); + ^ static void freecnfa(struct cnfa *); */ static void freecnfa( @@ -2920,13 +2935,14 @@ freecnfa( { assert(cnfa->nstates != 0); /* not empty already */ cnfa->nstates = 0; + FREE(cnfa->stflags); FREE(cnfa->states); FREE(cnfa->arcs); } /* - dumpnfa - dump an NFA in human-readable form - ^ static VOID dumpnfa(struct nfa *, FILE *); + ^ static void dumpnfa(struct nfa *, FILE *); */ static void dumpnfa( @@ -2972,7 +2988,7 @@ dumpnfa( /* - dumpstate - dump an NFA state in human-readable form - ^ static VOID dumpstate(struct state *, FILE *); + ^ static void dumpstate(struct state *, FILE *); */ static void dumpstate( @@ -3002,7 +3018,7 @@ dumpstate( /* - dumparcs - dump out-arcs in human-readable form - ^ static VOID dumparcs(struct state *, FILE *); + ^ static void dumparcs(struct state *, FILE *); */ static void dumparcs( @@ -3036,7 +3052,7 @@ dumparcs( /* - dumparc - dump one outarc in readable form, including prefixing tab - ^ static VOID dumparc(struct arc *, struct state *, FILE *); + ^ static void dumparc(struct arc *, struct state *, FILE *); */ static void dumparc( @@ -3110,7 +3126,7 @@ dumparc( /* - dumpcnfa - dump a compacted NFA in human-readable form - ^ static VOID dumpcnfa(struct cnfa *, FILE *); + ^ static void dumpcnfa(struct cnfa *, FILE *); */ static void dumpcnfa( @@ -3138,7 +3154,7 @@ dumpcnfa( } fprintf(f, "\n"); for (st = 0; st < cnfa->nstates; st++) { - dumpcstate(st, cnfa->states[st], cnfa, f); + dumpcstate(st, cnfa, f); } fflush(f); #endif @@ -3151,25 +3167,24 @@ dumpcnfa( /* - dumpcstate - dump a compacted-NFA state in human-readable form - ^ static VOID dumpcstate(int, struct carc *, struct cnfa *, FILE *); + ^ static void dumpcstate(int, struct cnfa *, FILE *); */ static void dumpcstate( int st, - struct carc *ca, struct cnfa *cnfa, FILE *f) { - int i; + struct carc *ca; int pos; - fprintf(f, "%d%s", st, (ca[0].co) ? ":" : "."); + fprintf(f, "%d%s", st, (cnfa->stflags[st] & CNFA_NOPROGRESS) ? ":" : "."); pos = 1; - for (i = 1; ca[i].co != COLORLESS; i++) { - if (ca[i].co < cnfa->ncolors) { - fprintf(f, "\t[%ld]->%d", (long) ca[i].co, ca[i].to); + for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++) { + if (ca->co < cnfa->ncolors) { + fprintf(f, "\t[%ld]->%d", (long) ca->co, ca->to); } else { - fprintf(f, "\t:%ld:->%d", (long) ca[i].co-cnfa->ncolors,ca[i].to); + fprintf(f, "\t:%ld:->%d", (long) (ca->co - cnfa->ncolors), ca->to); } if (pos == 5) { fprintf(f, "\n"); @@ -3178,7 +3193,7 @@ dumpcstate( pos++; } } - if (i == 1 || pos != 1) { + if (ca == cnfa->states[st] || pos != 1) { fprintf(f, "\n"); } fflush(f); diff --git a/generic/regcomp.c b/generic/regcomp.c index 8287b7e..211cd70 100644 --- a/generic/regcomp.c +++ b/generic/regcomp.c @@ -79,13 +79,10 @@ static void lexnest(struct vars *, const chr *, const chr *); static void lexword(struct vars *); static int next(struct vars *); static int lexescape(struct vars *); -static chr lexdigits(struct vars *, int, int, int); +static int lexdigits(struct vars *, int, int, int); static int brenext(struct vars *, pchr); static void skip(struct vars *); static chr newline(NOPARMS); -#ifdef REG_DEBUG -static const chr *ch(NOPARMS); -#endif static chr chrnamed(struct vars *, const chr *, const chr *, pchr); /* === regc_color.c === */ static void initcm(struct vars *, struct colormap *); @@ -139,7 +136,7 @@ static void cloneouts(struct nfa *, struct state *, struct state *, struct state static void delsub(struct nfa *, struct state *, struct state *); static void deltraverse(struct nfa *, struct state *, struct state *); static void dupnfa(struct nfa *, struct state *, struct state *, struct state *, struct state *); -static void duptraverse(struct nfa *, struct state *, struct state *); +static void duptraverse(struct nfa *, struct state *, struct state *, int); static void cleartraverse(struct nfa *, struct state *); static void specialcolors(struct nfa *); static long optimize(struct nfa *, FILE *); @@ -177,7 +174,7 @@ static void dumparc(struct arc *, struct state *, FILE *); #endif static void dumpcnfa(struct cnfa *, FILE *); #ifdef REG_DEBUG -static void dumpcstate(int, struct carc *, struct cnfa *, FILE *); +static void dumpcstate(int, struct cnfa *, FILE *); #endif /* === regc_cvec.c === */ static struct cvec *clearcvec(struct cvec *); @@ -222,7 +219,7 @@ struct vars { struct subre *tree; /* subexpression tree */ struct subre *treechain; /* all tree nodes allocated */ struct subre *treefree; /* any free tree nodes */ - int ntree; /* number of tree nodes */ + int ntree; /* number of tree nodes, plus one */ struct cvec *cv; /* interface cvec */ struct cvec *cv2; /* utility cvec */ struct subre *lacons; /* lookahead-constraint vector */ @@ -236,13 +233,13 @@ struct vars { #define EAT(t) (SEE(t) && next(v)) /* if next is this, swallow it */ #define VISERR(vv) ((vv)->err != 0)/* have we seen an error yet? */ #define ISERR() VISERR(v) -#define VERR(vv,e) \ - ((vv)->nexttype = EOS, ((vv)->err) ? (vv)->err : ((vv)->err = (e))) +#define VERR(vv,e) ((vv)->nexttype = EOS, \ + (vv)->err = ((vv)->err ? (vv)->err : (e))) #define ERR(e) VERR(v, e) /* record an error */ #define NOERR() {if (ISERR()) return;} /* if error seen, return */ #define NOERRN() {if (ISERR()) return NULL;} /* NOERR with retval */ #define NOERRZ() {if (ISERR()) return 0;} /* NOERR with retval */ -#define INSIST(c, e) ((c) ? 0 : ERR(e)) /* if condition false, error */ +#define INSIST(c, e) do { if (!(c)) ERR(e); } while (0) /* error if c false */ #define NOTE(b) (v->re->re_info |= (b)) /* note visible condition */ #define EMPTYARC(x, y) newarc(v->nfa, EMPTY, 0, x, y) @@ -271,12 +268,14 @@ struct vars { ((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND) /* static function list */ -static struct fns functions = { +static const struct fns functions = { rfree, /* regfree insides */ }; /* - compile - compile regular expression + * Note: on failure, no resources remain allocated, so regfree() + * need not be applied to re. ^ int compile(regex_t *, const chr *, size_t, int); */ int @@ -607,7 +606,7 @@ makesearch( break; } } - + /* * We want to mark states as being in the list already by having non * NULL tmp fields, but we can't just store the old slist value in tmp @@ -1120,11 +1119,17 @@ parseqatom( /* * Prepare a general-purpose state skeleton. * - * ---> [s] ---prefix---> [begin] ---atom---> [end] ----rest---> [rp] - * / / - * [lp] ----> [s2] ----bypass--------------------- + * In the no-backrefs case, we want this: + * + * [lp] ---> [s] ---prefix---> [begin] ---atom---> [end] ---rest---> [rp] + * + * where prefix is some repetitions of atom. In the general case we need * - * where bypass is an empty, and prefix is some repetitions of atom + * [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp] + * + * where the iterator wraps around [begin] ---atom---> [end] + * + * We make the s state here for both cases; s2 is made below if needed */ s = newstate(v->nfa); /* first, new endpoints for the atom */ @@ -1135,11 +1140,9 @@ parseqatom( NOERR(); atom->begin = s; atom->end = s2; - s = newstate(v->nfa); /* and spots for prefix and bypass */ - s2 = newstate(v->nfa); + s = newstate(v->nfa); /* set up starting state */ NOERR(); EMPTYARC(lp, s); - EMPTYARC(lp, s2); NOERR(); /* @@ -1186,27 +1189,8 @@ parseqatom( } /* - * It's quantifier time; first, turn x{0,...} into x{1,...}|empty - */ - - if (m == 0) { - EMPTYARC(s2, atom->end);/* the bypass */ - assert(PREF(qprefer) != 0); - f = COMBINE(qprefer, atom->flags); - t = subre(v, '|', f, lp, atom->end); - NOERR(); - t->left = atom; - t->right = subre(v, '|', PREF(f), s2, atom->end); - NOERR(); - t->right->left = subre(v, '=', 0, s2, atom->end); - NOERR(); - *atomp = t; - atomp = &t->left; - m = 1; - } - - /* - * Deal with the rest of the quantifier. + * It's quantifier time. If the atom is just a backref, we'll let it deal + * with quantifiers internally. */ if (atomtype == BACKREF) { @@ -1224,16 +1208,24 @@ parseqatom( atom->min = (short) m; atom->max = (short) n; atom->flags |= COMBINE(qprefer, atom->flags); + /* rest of branch can be strung starting from atom->end */ + s2 = atom->end; } else if (m == 1 && n == 1) { /* * No/vacuous quantifier: done. */ EMPTYARC(s, atom->begin); /* empty prefix */ - } else { + /* rest of branch can be strung starting from atom->end */ + s2 = atom->end; + } else if (m > 0 && !(atom->flags & BACKR)) { /* - * Turn x{m,n} into x{m-1,n-1}x, with capturing parens in only second - * x + * If there's no backrefs involved, we can turn x{m,n} into + * x{m-1,n-1}x, with capturing parens in only the second x. This + * is valid because we only care about capturing matches from the + * final iteration of the quantifier. It's a win because we can + * implement the backref-free left side as a plain DFA node, since + * we don't really care where its submatches are. */ dupnfa(v->nfa, atom->begin, atom->end, s, atom->begin); @@ -1246,6 +1238,24 @@ parseqatom( NOERR(); t->right = atom; *atomp = t; + /* rest of branch can be strung starting from atom->end */ + s2 = atom->end; + } else { + /* general case: need an iteration node */ + s2 = newstate(v->nfa); + NOERR(); + moveouts(v->nfa, atom->end, s2); + NOERR(); + dupnfa(v->nfa, atom->begin, atom->end, s, s2); + repeat(v, s, s2, m, n); + f = COMBINE(qprefer, atom->flags); + t = subre(v, '*', f, s, s2); + NOERR(); + t->min = (short) m; + t->max = (short) n; + t->left = atom; + *atomp = t; + /* rest of branch is to be strung from iteration's end state */ } /* @@ -1254,10 +1264,10 @@ parseqatom( t = top->right; if (!(SEE('|') || SEE(stopper) || SEE(EOS))) { - t->right = parsebranch(v, stopper, type, atom->end, rp, 1); + t->right = parsebranch(v, stopper, type, s2, rp, 1); } else { - EMPTYARC(atom->end, rp); - t->right = subre(v, '=', 0, atom->end, rp); + EMPTYARC(s2, rp); + t->right = subre(v, '=', 0, s2, rp); } NOERR(); assert(SEE('|') || SEE(stopper) || SEE(EOS)); @@ -1324,6 +1334,8 @@ scannum( /* - repeat - replicate subNFA for quantifiers + * The sub-NFA strung from lp to rp is modified to represent m to n + * repetitions of its initial contents. * The duplication sequences used here are chosen carefully so that any * pointers starting out pointing into the subexpression end up pointing into * the last occurrence. (Note that it may not be strung between the same left @@ -1484,7 +1496,7 @@ brackpart( celt startc, endc; struct cvec *cv; const chr *startp, *endp; - chr c[1]; + chr c; /* * Parse something, get rid of special cases, take shortcuts. @@ -1496,7 +1508,7 @@ brackpart( return; break; case PLAIN: - c[0] = v->nextvalue; + c = v->nextvalue; NEXT(); /* @@ -1504,10 +1516,10 @@ brackpart( */ if (!SEE(RANGE)) { - onechr(v, c[0], lp, rp); + onechr(v, c, lp, rp); return; } - startc = element(v, c, c+1); + startc = element(v, &c, &c+1); NOERR(); break; case COLLEL: @@ -1551,9 +1563,9 @@ brackpart( switch (v->nexttype) { case PLAIN: case RANGE: - c[0] = v->nextvalue; + c = v->nextvalue; NEXT(); - endc = element(v, c, c+1); + endc = element(v, &c, &c+1); NOERR(); break; case COLLEL: @@ -1733,11 +1745,11 @@ subre( v->treechain = ret; } - assert(strchr("|.b(=", op) != NULL); + assert(strchr("=b|.*(", op) != NULL); ret->op = op; ret->flags = flags; - ret->retry = 0; + ret->id = 0; /* will be assigned later */ ret->subno = 0; ret->min = ret->max = 1; ret->left = NULL; @@ -1790,7 +1802,8 @@ freesrnode( } sr->flags = 0; - if (v != NULL) { + if (v != NULL && v->treechain != NULL) { + /* we're still parsing, maybe we can reuse the subre */ sr->left = v->treefree; v->treefree = sr; } else { @@ -1818,7 +1831,7 @@ optst( } /* - - numst - number tree nodes (assigning retry indexes) + - numst - number tree nodes (assigning "id" indexes) ^ static int numst(struct subre *, int); */ static int /* next number */ @@ -1831,7 +1844,7 @@ numst( assert(t != NULL); i = start; - t->retry = (short) i++; + t->id = (short) i++; if (t->left != NULL) { i = numst(t->left, i); } @@ -1843,6 +1856,19 @@ numst( /* - markst - mark tree nodes as INUSE + * Note: this is a great deal more subtle than it looks. During initial + * parsing of a regex, all subres are linked into the treechain list; + * discarded ones are also linked into the treefree list for possible reuse. + * After we are done creating all subres required for a regex, we run markst() + * then cleanst(), which results in discarding all subres not reachable from + * v->tree. We then clear v->treechain, indicating that subres must be found + * by descending from v->tree. This changes the behavior of freesubre(): it + * will henceforth FREE() unwanted subres rather than sticking them into the + * treefree list. (Doing that any earlier would result in dangling links in + * the treechain list.) This all means that freev() will clean up correctly + * if invoked before or after markst()+cleanst(); but it would not work if + * called partway through this state conversion, so we mustn't error out + * in or between these two functions. ^ static void markst(struct subre *); */ static void @@ -1949,24 +1975,26 @@ newlacon( struct state *end, int pos) { - struct subre *sub; int n; + struct subre *newlacons; + struct subre *sub; if (v->nlacons == 0) { - v->lacons = (struct subre *) MALLOC(2 * sizeof(struct subre)); n = 1; /* skip 0th */ - v->nlacons = 2; + newlacons = (struct subre *) MALLOC(2 * sizeof(struct subre)); } else { - v->lacons = (struct subre *) REALLOC(v->lacons, - (v->nlacons+1)*sizeof(struct subre)); - n = v->nlacons++; + n = v->nlacons; + newlacons = (struct subre *) REALLOC(v->lacons, + (n + 1) * sizeof(struct subre)); } - if (v->lacons == NULL) { + if (newlacons == NULL) { ERR(REG_ESPACE); return 0; } + v->lacons = newlacons; + v->nlacons = n + 1; sub = &v->lacons[n]; sub->begin = begin; sub->end = end; @@ -2014,18 +2042,20 @@ rfree( g = (struct guts *) re->re_guts; re->re_guts = NULL; re->re_fns = NULL; - g->magic = 0; - freecm(&g->cmap); - if (g->tree != NULL) { - freesubre(NULL, g->tree); - } - if (g->lacons != NULL) { - freelacons(g->lacons, g->nlacons); - } - if (!NULLCNFA(g->search)) { - freecnfa(&g->search); + if (g != NULL) { + g->magic = 0; + freecm(&g->cmap); + if (g->tree != NULL) { + freesubre(NULL, g->tree); + } + if (g->lacons != NULL) { + freelacons(g->lacons, g->nlacons); + } + if (!NULLCNFA(g->search)) { + freecnfa(&g->search); + } + FREE(g); } - FREE(g); } /* @@ -2057,7 +2087,7 @@ dump( fprintf(f, "\n\n\n========= DUMP ==========\n"); fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n", - re->re_nsub, re->re_info, re->re_csize, g->ntree); + (int) re->re_nsub, re->re_info, re->re_csize, g->ntree); dumpcolors(&g->cmap, f); if (!NULLCNFA(g->search)) { @@ -2166,14 +2196,14 @@ stid( size_t bufsize) { /* - * Big enough for hex int or decimal t->retry? + * Big enough for hex int or decimal t->id? */ - if (bufsize < sizeof(void*)*2 + 3 || bufsize < sizeof(t->retry)*3 + 1) { + if (bufsize < sizeof(void*)*2 + 3 || bufsize < sizeof(t->id)*3 + 1) { return "unable"; } - if (t->retry != 0) { - sprintf(buf, "%d", t->retry); + if (t->id != 0) { + sprintf(buf, "%d", t->id); } else { sprintf(buf, "%p", t); } diff --git a/generic/regcustom.h b/generic/regcustom.h index 57a2d47..681b97d 100644 --- a/generic/regcustom.h +++ b/generic/regcustom.h @@ -30,16 +30,16 @@ * Headers if any. */ -#include "tclInt.h" +#include "regex.h" /* * Overrides for regguts.h definitions, if any. */ #define FUNCPTR(name, args) (*name)args -#define MALLOC(n) ckalloc(n) +#define MALLOC(n) VS(attemptckalloc(n)) #define FREE(p) ckfree(VS(p)) -#define REALLOC(p,n) ckrealloc(VS(p),n) +#define REALLOC(p,n) VS(attemptckrealloc(VS(p),n)) /* * Do not insert extras between the "begin" and "end" lines - this chunk is @@ -60,12 +60,6 @@ #ifdef __REG_REGOFF_T #undef __REG_REGOFF_T #endif -#ifdef __REG_VOID_T -#undef __REG_VOID_T -#endif -#ifdef __REG_CONST -#undef __REG_CONST -#endif #ifdef __REG_NOFRONT #undef __REG_NOFRONT #endif @@ -75,8 +69,6 @@ /* Interface types */ #define __REG_WIDE_T Tcl_UniChar #define __REG_REGOFF_T long /* Not really right, but good enough... */ -#define __REG_VOID_T void -#define __REG_CONST const /* Names and declarations */ #define __REG_WIDE_COMPILE TclReComp #define __REG_WIDE_EXEC TclReExec @@ -155,7 +147,9 @@ typedef int celt; /* Type to hold chr, or NOCELT */ #endif /* - * And pick up the standard header. + * Local Variables: + * mode: c + * c-basic-offset: 4 + * fill-column: 78 + * End: */ - -#include "regex.h" diff --git a/generic/rege_dfa.c b/generic/rege_dfa.c index e233680..e5f22c4 100644 --- a/generic/rege_dfa.c +++ b/generic/rege_dfa.c @@ -36,17 +36,16 @@ */ static chr * /* endpoint, or NULL */ longest( - struct vars *v, /* used only for debug and exec flags */ - struct dfa *d, - chr *start, /* where the match should start */ - chr *stop, /* match must end at or before here */ - int *hitstopp) /* record whether hit v->stop, if non-NULL */ + struct vars *const v, /* used only for debug and exec flags */ + struct dfa *const d, + chr *const start, /* where the match should start */ + chr *const stop, /* match must end at or before here */ + int *const hitstopp) /* record whether hit v->stop, if non-NULL */ { chr *cp; chr *realstop = (stop == v->stop) ? stop : stop + 1; color co; - struct sset *css; - struct sset *ss; + struct sset *css, *ss; chr *post; int i; struct colormap *cm = d->cm; @@ -85,7 +84,7 @@ longest( if (v->eflags®_FTRACE) { while (cp < realstop) { - FDEBUG(("+++ at c%d +++\n", css - d->ssets)); + FDEBUG(("+++ at c%d +++\n", (int) (css - d->ssets))); co = GETCOLOR(cm, *cp); FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co)); ss = css->outs[co]; @@ -119,7 +118,7 @@ longest( * Shutdown. */ - FDEBUG(("+++ shutdown at c%d +++\n", css - d->ssets)); + FDEBUG(("+++ shutdown at c%d +++\n", (int) (css - d->ssets))); if (cp == v->stop && stop == v->stop) { if (hitstopp != NULL) { *hitstopp = 1; @@ -164,20 +163,19 @@ longest( */ static chr * /* endpoint, or NULL */ shortest( - struct vars *v, - struct dfa *d, - chr *start, /* where the match should start */ - chr *min, /* match must end at or after here */ - chr *max, /* match must end at or before here */ - chr **coldp, /* store coldstart pointer here, if nonNULL */ - int *hitstopp) /* record whether hit v->stop, if non-NULL */ + struct vars *const v, + struct dfa *const d, + chr *const start, /* where the match should start */ + chr *const min, /* match must end at or after here */ + chr *const max, /* match must end at or before here */ + chr **const coldp, /* store coldstart pointer here, if nonNULL */ + int *const hitstopp) /* record whether hit v->stop, if non-NULL */ { chr *cp; chr *realmin = (min == v->stop) ? min : min + 1; chr *realmax = (max == v->stop) ? max : max + 1; color co; - struct sset *css; - struct sset *ss; + struct sset *css, *ss; struct colormap *cm = d->cm; /* @@ -215,7 +213,7 @@ shortest( if (v->eflags®_FTRACE) { while (cp < realmax) { - FDEBUG(("--- at c%d ---\n", css - d->ssets)); + FDEBUG(("--- at c%d ---\n", (int) (css - d->ssets))); co = GETCOLOR(cm, *cp); FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co)); ss = css->outs[co]; @@ -256,7 +254,7 @@ shortest( } if (coldp != NULL) { /* report last no-progress state set, if any */ - *coldp = lastcold(v, d); + *coldp = lastCold(v, d); } if ((ss->flags&POSTSTATE) && cp > min) { @@ -284,19 +282,18 @@ shortest( } /* - - lastcold - determine last point at which no progress had been made - ^ static chr *lastcold(struct vars *, struct dfa *); + - lastCold - determine last point at which no progress had been made + ^ static chr *lastCold(struct vars *, struct dfa *); */ static chr * /* endpoint, or NULL */ -lastcold( - struct vars *v, - struct dfa *d) +lastCold( + struct vars *const v, + struct dfa *const d) { struct sset *ss; - chr *nopr; + chr *nopr = d->lastnopr; int i; - nopr = d->lastnopr; if (nopr == NULL) { nopr = v->start; } @@ -309,15 +306,15 @@ lastcold( } /* - - newdfa - set up a fresh DFA - ^ static struct dfa *newdfa(struct vars *, struct cnfa *, + - newDFA - set up a fresh DFA + ^ static struct dfa *newDFA(struct vars *, struct cnfa *, ^ struct colormap *, struct smalldfa *); */ static struct dfa * -newdfa( - struct vars *v, - struct cnfa *cnfa, - struct colormap *cm, +newDFA( + struct vars *const v, + struct cnfa *const cnfa, + struct colormap *const cm, struct smalldfa *sml) /* preallocated space, may be NULL */ { struct dfa *d; @@ -345,12 +342,12 @@ newdfa( d->cptsmalloced = 0; d->mallocarea = (smallwas == NULL) ? (char *)sml : NULL; } else { - d = (struct dfa *)MALLOC(sizeof(struct dfa)); + d = (struct dfa *) MALLOC(sizeof(struct dfa)); if (d == NULL) { ERR(REG_ESPACE); return NULL; } - d->ssets = (struct sset *)MALLOC(nss * sizeof(struct sset)); + d->ssets = (struct sset *) MALLOC(nss * sizeof(struct sset)); d->statesarea = (unsigned *) MALLOC((nss+WORK) * wordsper * sizeof(unsigned)); d->work = &d->statesarea[nss * wordsper]; @@ -362,7 +359,7 @@ newdfa( d->mallocarea = (char *)d; if (d->ssets == NULL || d->statesarea == NULL || d->outsarea == NULL || d->incarea == NULL) { - freedfa(d); + freeDFA(d); ERR(REG_ESPACE); return NULL; } @@ -387,12 +384,12 @@ newdfa( } /* - - freedfa - free a DFA - ^ static void freedfa(struct dfa *); + - freeDFA - free a DFA + ^ static void freeDFA(struct dfa *); */ static void -freedfa( - struct dfa *d) +freeDFA( + struct dfa *const d) { if (d->cptsmalloced) { if (d->ssets != NULL) { @@ -421,8 +418,8 @@ freedfa( */ static unsigned hash( - unsigned *uv, - int n) + unsigned *const uv, + const int n) { int i; unsigned h; @@ -440,9 +437,9 @@ hash( */ static struct sset * initialize( - struct vars *v, /* used only for debug flags */ - struct dfa *d, - chr *start) + struct vars *const v, /* used only for debug flags */ + struct dfa *const d, + chr *const start) { struct sset *ss; int i; @@ -454,7 +451,7 @@ initialize( if (d->nssused > 0 && (d->ssets[0].flags&STARTER)) { ss = &d->ssets[0]; } else { /* no, must (re)build it */ - ss = getvacant(v, d, start, start); + ss = getVacantSS(v, d, start, start); for (i = 0; i < d->wordsper; i++) { ss->states[i] = 0; } @@ -484,23 +481,18 @@ initialize( */ static struct sset * /* NULL if goes to empty set */ miss( - struct vars *v, /* used only for debug flags */ - struct dfa *d, - struct sset *css, - pcolor co, - chr *cp, /* next chr */ - chr *start) /* where the attempt got started */ + struct vars *const v, /* used only for debug flags */ + struct dfa *const d, + struct sset *const css, + const pcolor co, + chr *const cp, /* next chr */ + chr *const start) /* where the attempt got started */ { struct cnfa *cnfa = d->cnfa; - int i; unsigned h; struct carc *ca; struct sset *p; - int ispost; - int noprogress; - int gotstate; - int dolacons; - int sawlacons; + int i, isPost, noProgress, gotState, doLAConstraints, sawLAConstraints; /* * For convenience, we can be called even if it might not be a miss. @@ -519,57 +511,57 @@ miss( for (i = 0; i < d->wordsper; i++) { d->work[i] = 0; } - ispost = 0; - noprogress = 1; - gotstate = 0; + isPost = 0; + noProgress = 1; + gotState = 0; for (i = 0; i < d->nstates; i++) { if (ISBSET(css->states, i)) { - for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++) { + for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) { if (ca->co == co) { BSET(d->work, ca->to); - gotstate = 1; + gotState = 1; if (ca->to == cnfa->post) { - ispost = 1; + isPost = 1; } - if (!cnfa->states[ca->to]->co) { - noprogress = 0; + if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS)) { + noProgress = 0; } FDEBUG(("%d -> %d\n", i, ca->to)); } } } } - dolacons = (gotstate) ? (cnfa->flags&HASLACONS) : 0; - sawlacons = 0; - while (dolacons) { /* transitive closure */ - dolacons = 0; + doLAConstraints = (gotState ? (cnfa->flags&HASLACONS) : 0); + sawLAConstraints = 0; + while (doLAConstraints) { /* transitive closure */ + doLAConstraints = 0; for (i = 0; i < d->nstates; i++) { if (ISBSET(d->work, i)) { - for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++) { - if (ca->co <= cnfa->ncolors) { - continue; /* NOTE CONTINUE */ + for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) { + if (ca->co < cnfa->ncolors) { + continue; /* NOTE CONTINUE */ } - sawlacons = 1; + sawLAConstraints = 1; if (ISBSET(d->work, ca->to)) { - continue; /* NOTE CONTINUE */ + continue; /* NOTE CONTINUE */ } - if (!lacon(v, cnfa, cp, ca->co)) { - continue; /* NOTE CONTINUE */ + if (!checkLAConstraint(v, cnfa, cp, ca->co)) { + continue; /* NOTE CONTINUE */ } BSET(d->work, ca->to); - dolacons = 1; + doLAConstraints = 1; if (ca->to == cnfa->post) { - ispost = 1; + isPost = 1; } - if (!cnfa->states[ca->to]->co) { - noprogress = 0; + if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS)) { + noProgress = 0; } FDEBUG(("%d :> %d\n", i, ca->to)); } } } } - if (!gotstate) { + if (!gotState) { return NULL; } h = HASH(d->work, d->wordsper); @@ -580,19 +572,19 @@ miss( for (p = d->ssets, i = d->nssused; i > 0; p++, i--) { if (HIT(h, d->work, p, d->wordsper)) { - FDEBUG(("cached c%d\n", p - d->ssets)); + FDEBUG(("cached c%d\n", (int) (p - d->ssets))); break; /* NOTE BREAK OUT */ } } if (i == 0) { /* nope, need a new cache entry */ - p = getvacant(v, d, cp, start); + p = getVacantSS(v, d, cp, start); assert(p != css); for (i = 0; i < d->wordsper; i++) { p->states[i] = d->work[i]; } p->hash = h; - p->flags = (ispost) ? POSTSTATE : 0; - if (noprogress) { + p->flags = (isPost ? POSTSTATE : 0); + if (noProgress) { p->flags |= NOPROGRESS; } @@ -601,26 +593,27 @@ miss( */ } - if (!sawlacons) { /* lookahead conds. always cache miss */ - FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets)); + if (!sawLAConstraints) { /* lookahead conds. always cache miss */ + FDEBUG(("c%d[%d]->c%d\n", + (int) (css - d->ssets), co, (int) (p - d->ssets))); css->outs[co] = p; css->inchain[co] = p->ins; p->ins.ss = css; - p->ins.co = (color)co; + p->ins.co = (color) co; } return p; } /* - - lacon - lookahead-constraint checker for miss() - ^ static int lacon(struct vars *, struct cnfa *, chr *, pcolor); + - checkLAConstraint - lookahead-constraint checker for miss() + ^ static int checkLAConstraint(struct vars *, struct cnfa *, chr *, pcolor); */ static int /* predicate: constraint satisfied? */ -lacon( - struct vars *v, - struct cnfa *pcnfa, /* parent cnfa */ - chr *cp, - pcolor co) /* "color" of the lookahead constraint */ +checkLAConstraint( + struct vars *const v, + struct cnfa *const pcnfa, /* parent cnfa */ + chr *const cp, + const pcolor co) /* "color" of the lookahead constraint */ { int n; struct subre *sub; @@ -632,38 +625,36 @@ lacon( assert(n < v->g->nlacons && v->g->lacons != NULL); FDEBUG(("=== testing lacon %d\n", n)); sub = &v->g->lacons[n]; - d = newdfa(v, &sub->cnfa, &v->g->cmap, &sd); + d = newDFA(v, &sub->cnfa, &v->g->cmap, &sd); if (d == NULL) { ERR(REG_ESPACE); return 0; } - end = longest(v, d, cp, v->stop, (int *)NULL); - freedfa(d); + end = longest(v, d, cp, v->stop, NULL); + freeDFA(d); FDEBUG(("=== lacon %d match %d\n", n, (end != NULL))); return (sub->subno) ? (end != NULL) : (end == NULL); } /* - - getvacant - get a vacant state set + - getVacantSS - get a vacant state set * This routine clears out the inarcs and outarcs, but does not otherwise * clear the innards of the state set -- that's up to the caller. - ^ static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *); + ^ static struct sset *getVacantSS(struct vars *, struct dfa *, chr *, chr *); */ static struct sset * -getvacant( - struct vars *v, /* used only for debug flags */ - struct dfa *d, - chr *cp, - chr *start) +getVacantSS( + struct vars *const v, /* used only for debug flags */ + struct dfa *const d, + chr *const cp, + chr *const start) { int i; - struct sset *ss; - struct sset *p; - struct arcp ap; - struct arcp lastap = {NULL, 0}; /* silence gcc 4 warning */ + struct sset *ss, *p; + struct arcp ap, lastap = {NULL, 0}; /* silence gcc 4 warning */ color co; - ss = pickss(v, d, cp, start); + ss = pickNextSS(v, d, cp, start); assert(!(ss->flags&LOCKED)); /* @@ -673,7 +664,7 @@ getvacant( ap = ss->ins; while ((p = ap.ss) != NULL) { co = ap.co; - FDEBUG(("zapping c%d's %ld outarc\n", p - d->ssets, (long)co)); + FDEBUG(("zapping c%d's %ld outarc\n", (int) (p - d->ssets), (long)co)); p->outs[co] = NULL; ap = p->inchain[co]; p->inchain[co].ss = NULL; /* paranoia */ @@ -690,13 +681,12 @@ getvacant( if (p == NULL) { continue; /* NOTE CONTINUE */ } - FDEBUG(("del outarc %d from c%d's in chn\n", i, p - d->ssets)); + FDEBUG(("del outarc %d from c%d's in chn\n", i, (int) (p - d->ssets))); if (p->ins.ss == ss && p->ins.co == i) { p->ins = ss->inchain[i]; } else { assert(p->ins.ss != NULL); - for (ap = p->ins; ap.ss != NULL && - !(ap.ss == ss && ap.co == i); + for (ap = p->ins; ap.ss != NULL && !(ap.ss == ss && ap.co == i); ap = ap.ss->inchain[ap.co]) { lastap = ap; } @@ -729,19 +719,18 @@ getvacant( } /* - - pickss - pick the next stateset to be used - ^ static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *); + - pickNextSS - pick the next stateset to be used + ^ static struct sset *pickNextSS(struct vars *, struct dfa *, chr *, chr *); */ static struct sset * -pickss( - struct vars *v, /* used only for debug flags */ - struct dfa *d, - chr *cp, - chr *start) +pickNextSS( + struct vars *const v, /* used only for debug flags */ + struct dfa *const d, + chr *const cp, + chr *const start) { int i; - struct sset *ss; - struct sset *end; + struct sset *ss, *end; chr *ancient; /* @@ -784,7 +773,7 @@ pickss( if ((ss->lastseen == NULL || ss->lastseen < ancient) && !(ss->flags&LOCKED)) { d->search = ss + 1; - FDEBUG(("replacing c%d\n", ss - d->ssets)); + FDEBUG(("replacing c%d\n", (int) (ss - d->ssets))); return ss; } } @@ -792,7 +781,7 @@ pickss( if ((ss->lastseen == NULL || ss->lastseen < ancient) && !(ss->flags&LOCKED)) { d->search = ss + 1; - FDEBUG(("replacing c%d\n", ss - d->ssets)); + FDEBUG(("replacing c%d\n", (int) (ss - d->ssets))); return ss; } } diff --git a/generic/regerror.c b/generic/regerror.c index a1a0163..49d93ed 100644 --- a/generic/regerror.c +++ b/generic/regerror.c @@ -41,7 +41,7 @@ static const char unk[] = "*** unknown regex error code 0x%x ***"; * Struct to map among codes, code names, and explanations. */ -static struct rerr { +static const struct rerr { int code; const char *name; const char *explain; @@ -62,7 +62,7 @@ regerror( char *errbuf, /* Result buffer (unless errbuf_size==0) */ size_t errbuf_size) /* Available space in errbuf, can be 0 */ { - struct rerr *r; + const struct rerr *r; const char *msg; char convbuf[sizeof(unk)+50]; /* 50 = plenty for int */ size_t len; diff --git a/generic/regex.h b/generic/regex.h index b5b11bd..8845f72 100644 --- a/generic/regex.h +++ b/generic/regex.h @@ -1,5 +1,8 @@ #ifndef _REGEX_H_ #define _REGEX_H_ /* never again */ + +#include "tclInt.h" + /* * regular expressions * @@ -89,12 +92,6 @@ extern "C" { #ifdef __REG_REGOFF_T #undef __REG_REGOFF_T #endif -#ifdef __REG_VOID_T -#undef __REG_VOID_T -#endif -#ifdef __REG_CONST -#undef __REG_CONST -#endif #ifdef __REG_NOFRONT #undef __REG_NOFRONT #endif @@ -104,8 +101,6 @@ extern "C" { /* interface types */ #define __REG_WIDE_T Tcl_UniChar #define __REG_REGOFF_T long /* not really right, but good enough... */ -#define __REG_VOID_T VOID -#define __REG_CONST CONST /* names and declarations */ #define __REG_WIDE_COMPILE TclReComp #define __REG_WIDE_EXEC TclReExec @@ -131,26 +126,6 @@ typedef long regoff_t; #endif /* - * For benefit of old compilers, we offer <sys/types.h> the option of - * overriding the `void' type used to declare nonexistent return types. - */ -#ifdef __REG_VOID_T -typedef __REG_VOID_T re_void; -#else -typedef void re_void; -#endif - -/* - * Also for benefit of old compilers, <sys/types.h> can supply a macro which - * expands to a substitute for `const'. - */ -#ifndef __REG_CONST -#define __REG_CONST const -#endif - - - -/* * other interface types */ @@ -194,13 +169,13 @@ typedef struct { /* * compilation ^ #ifndef __REG_NOCHAR - ^ int re_comp(regex_t *, __REG_CONST char *, size_t, int); + ^ int re_comp(regex_t *, const char *, size_t, int); ^ #endif ^ #ifndef __REG_NOFRONT - ^ int regcomp(regex_t *, __REG_CONST char *, int); + ^ int regcomp(regex_t *, const char *, int); ^ #endif ^ #ifdef __REG_WIDE_T - ^ int __REG_WIDE_COMPILE(regex_t *, __REG_CONST __REG_WIDE_T *, size_t, int); + ^ int __REG_WIDE_COMPILE(regex_t *, const __REG_WIDE_T *, size_t, int); ^ #endif */ #define REG_BASIC 000000 /* BREs (convenience) */ @@ -225,14 +200,14 @@ typedef struct { /* * execution ^ #ifndef __REG_NOCHAR - ^ int re_exec(regex_t *, __REG_CONST char *, size_t, + ^ int re_exec(regex_t *, const char *, size_t, ^ rm_detail_t *, size_t, regmatch_t [], int); ^ #endif ^ #ifndef __REG_NOFRONT - ^ int regexec(regex_t *, __REG_CONST char *, size_t, regmatch_t [], int); + ^ int regexec(regex_t *, const char *, size_t, regmatch_t [], int); ^ #endif ^ #ifdef __REG_WIDE_T - ^ int __REG_WIDE_EXEC(regex_t *, __REG_CONST __REG_WIDE_T *, size_t, + ^ int __REG_WIDE_EXEC(regex_t *, const __REG_WIDE_T *, size_t, ^ rm_detail_t *, size_t, regmatch_t [], int); ^ #endif */ @@ -245,7 +220,7 @@ typedef struct { /* * misc generics (may be more functions here eventually) - ^ re_void regfree(regex_t *); + ^ void regfree(regex_t *); */ /* @@ -257,7 +232,7 @@ typedef struct { * of character is used for error reports is independent of what kind is used * in matching. * - ^ extern size_t regerror(int, __REG_CONST regex_t *, char *, size_t); + ^ extern size_t regerror(int, const regex_t *, char *, size_t); */ #define REG_OKAY 0 /* no errors detected */ #define REG_NOMATCH 1 /* failed to match */ @@ -290,25 +265,25 @@ typedef struct { /* automatically gathered by fwd; do not hand-edit */ /* === regproto.h === */ #ifndef __REG_NOCHAR -int re_comp(regex_t *, __REG_CONST char *, size_t, int); +int re_comp(regex_t *, const char *, size_t, int); #endif #ifndef __REG_NOFRONT -int regcomp(regex_t *, __REG_CONST char *, int); +int regcomp(regex_t *, const char *, int); #endif #ifdef __REG_WIDE_T -MODULE_SCOPE int __REG_WIDE_COMPILE(regex_t *, __REG_CONST __REG_WIDE_T *, size_t, int); +MODULE_SCOPE int __REG_WIDE_COMPILE(regex_t *, const __REG_WIDE_T *, size_t, int); #endif #ifndef __REG_NOCHAR -int re_exec(regex_t *, __REG_CONST char *, size_t, rm_detail_t *, size_t, regmatch_t [], int); +int re_exec(regex_t *, const char *, size_t, rm_detail_t *, size_t, regmatch_t [], int); #endif #ifndef __REG_NOFRONT -int regexec(regex_t *, __REG_CONST char *, size_t, regmatch_t [], int); +int regexec(regex_t *, const char *, size_t, regmatch_t [], int); #endif #ifdef __REG_WIDE_T -MODULE_SCOPE int __REG_WIDE_EXEC(regex_t *, __REG_CONST __REG_WIDE_T *, size_t, rm_detail_t *, size_t, regmatch_t [], int); +MODULE_SCOPE int __REG_WIDE_EXEC(regex_t *, const __REG_WIDE_T *, size_t, rm_detail_t *, size_t, regmatch_t [], int); #endif -MODULE_SCOPE re_void regfree(regex_t *); -MODULE_SCOPE size_t regerror(int, __REG_CONST regex_t *, char *, size_t); +MODULE_SCOPE void regfree(regex_t *); +MODULE_SCOPE size_t regerror(int, const regex_t *, char *, size_t); /* automatically gathered by fwd; do not hand-edit */ /* =====^!^===== end forwards =====^!^===== */ @@ -320,3 +295,11 @@ MODULE_SCOPE size_t regerror(int, __REG_CONST regex_t *, char *, size_t); #endif #endif + +/* + * Local Variables: + * mode: c + * c-basic-offset: 4 + * fill-column: 78 + * End: + */ diff --git a/generic/regexec.c b/generic/regexec.c index f3be137..6d12827 100644 --- a/generic/regexec.c +++ b/generic/regexec.c @@ -107,13 +107,13 @@ struct vars { chr *start; /* start of string */ chr *stop; /* just past end of string */ int err; /* error code if any (0 none) */ - regoff_t *mem; /* memory vector for backtracking */ + struct dfa **subdfas; /* per-subre DFAs */ struct smalldfa dfa1; struct smalldfa dfa2; }; #define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */ #define ISERR() VISERR(v) -#define VERR(vv,e) (((vv)->err) ? (vv)->err : ((vv)->err = (e))) +#define VERR(vv,e) ((vv)->err = ((vv)->err ? (vv)->err : (e))) #define ERR(e) VERR(v, e) /* record an error */ #define NOERR() {if (ISERR()) return v->err;} /* if error seen, return it */ #define OFF(p) ((p) - v->start) @@ -125,45 +125,45 @@ struct vars { /* =====^!^===== begin forwards =====^!^===== */ /* automatically gathered by fwd; do not hand-edit */ /* === regexec.c === */ -int exec(regex_t *, CONST chr *, size_t, rm_detail_t *, size_t, regmatch_t [], int); -static int find(struct vars *, struct cnfa *, struct colormap *); -static int cfind(struct vars *, struct cnfa *, struct colormap *); -static int cfindloop(struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **); -static VOID zapsubs(regmatch_t *, size_t); -static VOID zapmem(struct vars *, struct subre *); -static VOID subset(struct vars *, struct subre *, chr *, chr *); -static int dissect(struct vars *, struct subre *, chr *, chr *); -static int condissect(struct vars *, struct subre *, chr *, chr *); -static int altdissect(struct vars *, struct subre *, chr *, chr *); +int exec(regex_t *, const chr *, size_t, rm_detail_t *, size_t, regmatch_t [], int); +static struct dfa *getsubdfa(struct vars *, struct subre *); +static int simpleFind(struct vars *const, struct cnfa *const, struct colormap *const); +static int complicatedFind(struct vars *const, struct cnfa *const, struct colormap *const); +static int complicatedFindLoop(struct vars *const, struct cnfa *const, struct colormap *const, struct dfa *const, struct dfa *const, chr **const); +static void zapallsubs(regmatch_t *const, const size_t); +static void zaptreesubs(struct vars *const, struct subre *const); +static void subset(struct vars *const, struct subre *const, chr *const, chr *const); static int cdissect(struct vars *, struct subre *, chr *, chr *); static int ccondissect(struct vars *, struct subre *, chr *, chr *); -static int crevdissect(struct vars *, struct subre *, chr *, chr *); +static int crevcondissect(struct vars *, struct subre *, chr *, chr *); static int cbrdissect(struct vars *, struct subre *, chr *, chr *); static int caltdissect(struct vars *, struct subre *, chr *, chr *); +static int citerdissect(struct vars *, struct subre *, chr *, chr *); +static int creviterdissect(struct vars *, struct subre *, chr *, chr *); /* === rege_dfa.c === */ -static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *); -static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *, chr **, int *); -static chr *lastcold(struct vars *, struct dfa *); -static struct dfa *newdfa(struct vars *, struct cnfa *, struct colormap *, struct smalldfa *); -static VOID freedfa(struct dfa *); -static unsigned hash(unsigned *, int); -static struct sset *initialize(struct vars *, struct dfa *, chr *); -static struct sset *miss(struct vars *, struct dfa *, struct sset *, pcolor, chr *, chr *); -static int lacon(struct vars *, struct cnfa *, chr *, pcolor); -static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *); -static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *); +static chr *longest(struct vars *const, struct dfa *const, chr *const, chr *const, int *const); +static chr *shortest(struct vars *const, struct dfa *const, chr *const, chr *const, chr *const, chr **const, int *const); +static chr *lastCold(struct vars *const, struct dfa *const); +static struct dfa *newDFA(struct vars *const, struct cnfa *const, struct colormap *const, struct smalldfa *); +static void freeDFA(struct dfa *const); +static unsigned hash(unsigned *const, const int); +static struct sset *initialize(struct vars *const, struct dfa *const, chr *const); +static struct sset *miss(struct vars *const, struct dfa *const, struct sset *const, const pcolor, chr *const, chr *const); +static int checkLAConstraint(struct vars *const, struct cnfa *const, chr *const, const pcolor); +static struct sset *getVacantSS(struct vars *const, struct dfa *const, chr *const, chr *const); +static struct sset *pickNextSS(struct vars *const, struct dfa *const, chr *const, chr *const); /* automatically gathered by fwd; do not hand-edit */ /* =====^!^===== end forwards =====^!^===== */ /* - exec - match regular expression - ^ int exec(regex_t *, CONST chr *, size_t, rm_detail_t *, + ^ int exec(regex_t *, const chr *, size_t, rm_detail_t *, ^ size_t, regmatch_t [], int); */ int exec( regex_t *re, - CONST chr *string, + const chr *string, size_t len, rm_detail_t *details, size_t nmatch, @@ -171,13 +171,13 @@ exec( int flags) { AllocVars(v); - int st; + int st, backref; size_t n; - int backref; + size_t i; #define LOCALMAT 20 regmatch_t mat[LOCALMAT]; -#define LOCALMEM 40 - regoff_t mem[LOCALMEM]; +#define LOCALDFAS 40 + struct dfa *subdfas[LOCALDFAS]; /* * Sanity checks. @@ -235,28 +235,20 @@ exec( v->start = (chr *)string; v->stop = (chr *)string + len; v->err = 0; - if (backref) { - /* - * Need retry memory. - */ - - assert(v->g->ntree >= 0); - n = (size_t)v->g->ntree; - if (n <= LOCALMEM) { - v->mem = mem; - } else { - v->mem = (regoff_t *) MALLOC(n*sizeof(regoff_t)); - } - if (v->mem == NULL) { - if (v->pmatch != pmatch && v->pmatch != mat) { - FREE(v->pmatch); - } - FreeVars(v); - return REG_ESPACE; - } - } else { - v->mem = NULL; + assert(v->g->ntree >= 0); + n = (size_t) v->g->ntree; + if (n <= LOCALDFAS) + v->subdfas = subdfas; + else + v->subdfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *)); + if (v->subdfas == NULL) { + if (v->pmatch != pmatch && v->pmatch != mat) + FREE(v->pmatch); + FreeVars(v); + return REG_ESPACE; } + for (i = 0; i < n; i++) + v->subdfas[i] = NULL; /* * Do it. @@ -264,9 +256,9 @@ exec( assert(v->g->tree != NULL); if (backref) { - st = cfind(v, &v->g->tree->cnfa, &v->g->cmap); + st = complicatedFind(v, &v->g->tree->cnfa, &v->g->cmap); } else { - st = find(v, &v->g->tree->cnfa, &v->g->cmap); + st = simpleFind(v, &v->g->tree->cnfa, &v->g->cmap); } /* @@ -274,7 +266,7 @@ exec( */ if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) { - zapsubs(pmatch, nmatch); + zapallsubs(pmatch, nmatch); n = (nmatch < v->nmatch) ? nmatch : v->nmatch; memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t)); } @@ -286,31 +278,49 @@ exec( if (v->pmatch != pmatch && v->pmatch != mat) { FREE(v->pmatch); } - if (v->mem != NULL && v->mem != mem) { - FREE(v->mem); + n = (size_t) v->g->ntree; + for (i = 0; i < n; i++) { + if (v->subdfas[i] != NULL) + freeDFA(v->subdfas[i]); } + if (v->subdfas != subdfas) + FREE(v->subdfas); FreeVars(v); return st; } /* - - find - find a match for the main NFA (no-complications case) - ^ static int find(struct vars *, struct cnfa *, struct colormap *); + - getsubdfa - create or re-fetch the DFA for a subre node + * We only need to create the DFA once per overall regex execution. + * The DFA will be freed by the cleanup step in exec(). + */ +static struct dfa * +getsubdfa(struct vars * v, + struct subre * t) +{ + if (v->subdfas[t->id] == NULL) { + v->subdfas[t->id] = newDFA(v, &t->cnfa, &v->g->cmap, DOMALLOC); + if (ISERR()) + return NULL; + } + return v->subdfas[t->id]; +} + +/* + - simpleFind - find a match for the main NFA (no-complications case) + ^ static int simpleFind(struct vars *, struct cnfa *, struct colormap *); */ static int -find( - struct vars *v, - struct cnfa *cnfa, - struct colormap *cm) +simpleFind( + struct vars *const v, + struct cnfa *const cnfa, + struct colormap *const cm) { - struct dfa *s; - struct dfa *d; - chr *begin; - chr *end = NULL; + struct dfa *s, *d; + chr *begin, *end = NULL; chr *cold; - chr *open; /* Open and close of range of possible + chr *open, *close; /* Open and close of range of possible * starts */ - chr *close; int hitend; int shorter = (v->g->tree->flags&SHORTER) ? 1 : 0; @@ -318,13 +328,13 @@ find( * First, a shot with the search RE. */ - s = newdfa(v, &v->g->search, cm, &v->dfa1); + s = newDFA(v, &v->g->search, cm, &v->dfa1); assert(!(ISERR() && s != NULL)); NOERR(); MDEBUG(("\nsearch at %ld\n", LOFF(v->start))); cold = NULL; close = shortest(v, s, v->start, v->start, v->stop, &cold, NULL); - freedfa(s); + freeDFA(s); NOERR(); if (v->g->cflags®_EXPECT) { assert(v->details != NULL); @@ -350,7 +360,7 @@ find( open = cold; cold = NULL; MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close))); - d = newdfa(v, cnfa, cm, &v->dfa1); + d = newDFA(v, cnfa, cm, &v->dfa1); assert(!(ISERR() && d != NULL)); NOERR(); for (begin = open; begin <= close; begin++) { @@ -360,7 +370,10 @@ find( } else { end = longest(v, d, begin, v->stop, &hitend); } - NOERR(); + if (ISERR()) { + freeDFA(d); + return v->err; + } if (hitend && cold == NULL) { cold = begin; } @@ -369,7 +382,7 @@ find( } } assert(end != NULL); /* search RE succeeded so loop should */ - freedfa(d); + freeDFA(d); /* * And pin down details. @@ -391,41 +404,40 @@ find( } /* - * Submatches. + * Find submatches. */ - zapsubs(v->pmatch, v->nmatch); - return dissect(v, v->g->tree, begin, end); + zapallsubs(v->pmatch, v->nmatch); + return cdissect(v, v->g->tree, begin, end); } /* - - cfind - find a match for the main NFA (with complications) - ^ static int cfind(struct vars *, struct cnfa *, struct colormap *); + - complicatedFind - find a match for the main NFA (with complications) + ^ static int complicatedFind(struct vars *, struct cnfa *, struct colormap *); */ static int -cfind( - struct vars *v, - struct cnfa *cnfa, - struct colormap *cm) +complicatedFind( + struct vars *const v, + struct cnfa *const cnfa, + struct colormap *const cm) { - struct dfa *s; - struct dfa *d; + struct dfa *s, *d; chr *cold = NULL; /* silence gcc 4 warning */ int ret; - s = newdfa(v, &v->g->search, cm, &v->dfa1); + s = newDFA(v, &v->g->search, cm, &v->dfa1); NOERR(); - d = newdfa(v, cnfa, cm, &v->dfa2); + d = newDFA(v, cnfa, cm, &v->dfa2); if (ISERR()) { assert(d == NULL); - freedfa(s); + freeDFA(s); return v->err; } - ret = cfindloop(v, cnfa, cm, d, s, &cold); + ret = complicatedFindLoop(v, cnfa, cm, d, s, &cold); - freedfa(d); - freedfa(s); + freeDFA(d); + freeDFA(s); NOERR(); if (v->g->cflags®_EXPECT) { assert(v->details != NULL); @@ -440,30 +452,26 @@ cfind( } /* - - cfindloop - the heart of cfind - ^ static int cfindloop(struct vars *, struct cnfa *, struct colormap *, + - complicatedFindLoop - the heart of complicatedFind + ^ static int complicatedFindLoop(struct vars *, struct cnfa *, struct colormap *, ^ struct dfa *, struct dfa *, chr **); */ static int -cfindloop( - struct vars *v, - struct cnfa *cnfa, - struct colormap *cm, - struct dfa *d, - struct dfa *s, - chr **coldp) /* where to put coldstart pointer */ +complicatedFindLoop( + struct vars *const v, + struct cnfa *const cnfa, + struct colormap *const cm, + struct dfa *const d, + struct dfa *const s, + chr **const coldp) /* where to put coldstart pointer */ { - chr *begin; - chr *end; + chr *begin, *end; chr *cold; - chr *open; /* Open and close of range of possible + chr *open, *close; /* Open and close of range of possible * starts */ - chr *close; - chr *estart; - chr *estop; - int er; + chr *estart, *estop; + int er, hitend; int shorter = v->g->tree->flags&SHORTER; - int hitend; assert(d != NULL && s != NULL); cold = NULL; @@ -479,7 +487,7 @@ cfindloop( cold = NULL; MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close))); for (begin = open; begin <= close; begin++) { - MDEBUG(("\ncfind trying at %ld\n", LOFF(begin))); + MDEBUG(("\ncomplicatedFind trying at %ld\n", LOFF(begin))); estart = begin; estop = v->stop; for (;;) { @@ -496,8 +504,7 @@ cfindloop( } MDEBUG(("tentative end %ld\n", LOFF(end))); - zapsubs(v->pmatch, v->nmatch); - zapmem(v, v->g->tree); + zapallsubs(v->pmatch, v->nmatch); er = cdissect(v, v->g->tree, begin, end); if (er == REG_OKAY) { if (v->nmatch > 0) { @@ -509,6 +516,7 @@ cfindloop( } if (er != REG_NOMATCH) { ERR(er); + *coldp = cold; return er; } if ((shorter) ? end == estop : end == begin) { @@ -533,13 +541,13 @@ cfindloop( } /* - - zapsubs - initialize the subexpression matches to "no match" - ^ static VOID zapsubs(regmatch_t *, size_t); + - zapallsubs - initialize all subexpression matches to "no match" + ^ static void zapallsubs(regmatch_t *, size_t); */ static void -zapsubs( - regmatch_t *p, - size_t n) +zapallsubs( + regmatch_t *const p, + const size_t n) { size_t i; @@ -550,44 +558,41 @@ zapsubs( } /* - - zapmem - initialize the retry memory of a subtree to zeros - ^ static VOID zapmem(struct vars *, struct subre *); + - zaptreesubs - initialize subexpressions within subtree to "no match" + ^ static void zaptreesubs(struct vars *, struct subre *); */ static void -zapmem( - struct vars *v, - struct subre *t) +zaptreesubs( + struct vars *const v, + struct subre *const t) { - if (t == NULL) { - return; - } - - assert(v->mem != NULL); - v->mem[t->retry] = 0; if (t->op == '(') { - assert(t->subno > 0); - v->pmatch[t->subno].rm_so = -1; - v->pmatch[t->subno].rm_eo = -1; + int n = t->subno; + assert(n > 0); + if ((size_t) n < v->nmatch) { + v->pmatch[n].rm_so = -1; + v->pmatch[n].rm_eo = -1; + } } if (t->left != NULL) { - zapmem(v, t->left); + zaptreesubs(v, t->left); } if (t->right != NULL) { - zapmem(v, t->right); + zaptreesubs(v, t->right); } } /* - - subset - set any subexpression relevant to a successful subre - ^ static VOID subset(struct vars *, struct subre *, chr *, chr *); + - subset - set subexpression match data for a successful subre + ^ static void subset(struct vars *, struct subre *, chr *, chr *); */ static void subset( - struct vars *v, - struct subre *sub, - chr *begin, - chr *end) + struct vars *const v, + struct subre *const sub, + chr *const begin, + chr *const end) { int n = sub->subno; @@ -602,185 +607,25 @@ subset( } /* - - dissect - determine subexpression matches (uncomplicated case) - ^ static int dissect(struct vars *, struct subre *, chr *, chr *); - */ -static int /* regexec return code */ -dissect( - struct vars *v, - struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ -{ - assert(t != NULL); - MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end))); - - switch (t->op) { - case '=': /* terminal node */ - assert(t->left == NULL && t->right == NULL); - return REG_OKAY; /* no action, parent did the work */ - case '|': /* alternation */ - assert(t->left != NULL); - return altdissect(v, t, begin, end); - case 'b': /* back ref -- shouldn't be calling us! */ - return REG_ASSERT; - case '.': /* concatenation */ - assert(t->left != NULL && t->right != NULL); - return condissect(v, t, begin, end); - case '(': /* capturing */ - assert(t->left != NULL && t->right == NULL); - assert(t->subno > 0); - subset(v, t, begin, end); - return dissect(v, t->left, begin, end); - default: - return REG_ASSERT; - } -} - -/* - - condissect - determine concatenation subexpression matches (uncomplicated) - ^ static int condissect(struct vars *, struct subre *, chr *, chr *); - */ -static int /* regexec return code */ -condissect( - struct vars *v, - struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ -{ - struct dfa *d; - struct dfa *d2; - chr *mid; - int i; - int shorter = (t->left->flags&SHORTER) ? 1 : 0; - chr *stop = (shorter) ? end : begin; - - assert(t->op == '.'); - assert(t->left != NULL && t->left->cnfa.nstates > 0); - assert(t->right != NULL && t->right->cnfa.nstates > 0); - - d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1); - NOERR(); - d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &v->dfa2); - if (ISERR()) { - assert(d2 == NULL); - freedfa(d); - return v->err; - } - - /* - * Pick a tentative midpoint. - */ - - if (shorter) { - mid = shortest(v, d, begin, begin, end, NULL, NULL); - } else { - mid = longest(v, d, begin, end, NULL); - } - if (mid == NULL) { - freedfa(d); - freedfa(d2); - return REG_ASSERT; - } - MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); - - /* - * Iterate until satisfaction or failure. - */ - - while (longest(v, d2, mid, end, NULL) != end) { - /* - * That midpoint didn't work, find a new one. - */ - - if (mid == stop) { - /* - * All possibilities exhausted! - */ - - MDEBUG(("no midpoint!\n")); - freedfa(d); - freedfa(d2); - return REG_ASSERT; - } - if (shorter) { - mid = shortest(v, d, begin, mid+1, end, NULL, NULL); - } else { - mid = longest(v, d, begin, mid-1, NULL); - } - if (mid == NULL) { - /* - * Failed to find a new one! - */ - - MDEBUG(("failed midpoint!\n")); - freedfa(d); - freedfa(d2); - return REG_ASSERT; - } - MDEBUG(("new midpoint %ld\n", LOFF(mid))); - } - - /* - * Satisfaction. - */ - - MDEBUG(("successful\n")); - freedfa(d); - freedfa(d2); - i = dissect(v, t->left, begin, mid); - if (i != REG_OKAY) { - return i; - } - return dissect(v, t->right, mid, end); -} - -/* - - altdissect - determine alternative subexpression matches (uncomplicated) - ^ static int altdissect(struct vars *, struct subre *, chr *, chr *); - */ -static int /* regexec return code */ -altdissect( - struct vars *v, - struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ -{ - struct dfa *d; - int i; - - assert(t != NULL); - assert(t->op == '|'); - - for (i = 0; t != NULL; t = t->right, i++) { - MDEBUG(("trying %dth\n", i)); - assert(t->left != NULL && t->left->cnfa.nstates > 0); - d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1); - if (ISERR()) { - return v->err; - } - if (longest(v, d, begin, end, NULL) == end) { - MDEBUG(("success\n")); - freedfa(d); - return dissect(v, t->left, begin, end); - } - freedfa(d); - } - return REG_ASSERT; /* none of them matched?!? */ -} - -/* - - cdissect - determine subexpression matches (with complications) - * The retry memory stores the offset of the trial midpoint from begin, plus 1 - * so that 0 uniquely means "clean slate". + - cdissect - check backrefs and determine subexpression matches + * cdissect recursively processes a subre tree to check matching of backrefs + * and/or identify submatch boundaries for capture nodes. The proposed match + * runs from "begin" to "end" (not including "end"), and we are basically + * "dissecting" it to see where the submatches are. + * Before calling any level of cdissect, the caller must have run the node's + * DFA and found that the proposed substring satisfies the DFA. (We make + * the caller do that because in concatenation and iteration nodes, it's + * much faster to check all the substrings against the child DFAs before we + * recurse.) Also, caller must have cleared subexpression match data via + * zaptreesubs (or zapallsubs at the top level). ^ static int cdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ cdissect( struct vars *v, struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { int er; @@ -790,16 +635,30 @@ cdissect( switch (t->op) { case '=': /* terminal node */ assert(t->left == NULL && t->right == NULL); - return REG_OKAY; /* no action, parent did the work */ - case '|': /* alternation */ - assert(t->left != NULL); - return caltdissect(v, t, begin, end); - case 'b': /* back ref -- shouldn't be calling us! */ + er = REG_OKAY; /* no action, parent did the work */ + break; + case 'b': /* back reference */ assert(t->left == NULL && t->right == NULL); - return cbrdissect(v, t, begin, end); + er = cbrdissect(v, t, begin, end); + break; case '.': /* concatenation */ assert(t->left != NULL && t->right != NULL); - return ccondissect(v, t, begin, end); + if (t->left->flags & SHORTER) /* reverse scan */ + er = crevcondissect(v, t, begin, end); + else + er = ccondissect(v, t, begin, end); + break; + case '|': /* alternation */ + assert(t->left != NULL); + er = caltdissect(v, t, begin, end); + break; + case '*': /* iteration */ + assert(t->left != NULL); + if (t->left->flags & SHORTER) /* reverse scan */ + er = creviterdissect(v, t, begin, end); + else + er = citerdissect(v, t, begin, end); + break; case '(': /* capturing */ assert(t->left != NULL && t->right == NULL); assert(t->subno > 0); @@ -807,65 +666,56 @@ cdissect( if (er == REG_OKAY) { subset(v, t, begin, end); } - return er; + break; default: - return REG_ASSERT; + er = REG_ASSERT; + break; } + + /* + * We should never have a match failure unless backrefs lurk below; + * otherwise, either caller failed to check the DFA, or there's some + * inconsistency between the DFA and the node's innards. + */ + assert(er != REG_NOMATCH || (t->flags & BACKR)); + + return er; } /* - - ccondissect - concatenation subexpression matches (with complications) - * The retry memory stores the offset of the trial midpoint from begin, plus 1 - * so that 0 uniquely means "clean slate". + - ccondissect - dissect match for concatenation node ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ ccondissect( struct vars *v, struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { struct dfa *d, *d2; chr *mid; - int er; assert(t->op == '.'); assert(t->left != NULL && t->left->cnfa.nstates > 0); assert(t->right != NULL && t->right->cnfa.nstates > 0); + assert(!(t->left->flags & SHORTER)); - if (t->left->flags&SHORTER) { /* reverse scan */ - return crevdissect(v, t, begin, end); - } + d = getsubdfa(v, t->left); + NOERR(); + d2 = getsubdfa(v, t->right); + NOERR(); - d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); - if (ISERR()) { - return v->err; - } - d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC); - if (ISERR()) { - freedfa(d); - return v->err; - } - MDEBUG(("cconcat %d\n", t->retry)); + MDEBUG(("cConcat %d\n", t->id)); /* * Pick a tentative midpoint. */ - - if (v->mem[t->retry] == 0) { - mid = longest(v, d, begin, end, NULL); - if (mid == NULL) { - freedfa(d); - freedfa(d2); - return REG_NOMATCH; - } - MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); - v->mem[t->retry] = (mid - begin) + 1; - } else { - mid = begin + (v->mem[t->retry] - 1); - MDEBUG(("working midpoint %ld\n", LOFF(mid))); + mid = longest(v, d, begin, end, (int *) NULL); + if (mid == NULL) { + return REG_NOMATCH; } + MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); /* * Iterate until satisfaction or failure. @@ -877,23 +727,20 @@ ccondissect( */ if (longest(v, d2, mid, end, NULL) == end) { - er = cdissect(v, t->left, begin, mid); + int er = cdissect(v, t->left, begin, mid); + if (er == REG_OKAY) { er = cdissect(v, t->right, mid, end); if (er == REG_OKAY) { /* * Satisfaction. */ - + MDEBUG(("successful\n")); - freedfa(d); - freedfa(d2); return REG_OKAY; } } - if ((er != REG_OKAY) && (er != REG_NOMATCH)) { - freedfa(d); - freedfa(d2); + if (er != REG_NOMATCH) { return er; } } @@ -907,9 +754,7 @@ ccondissect( * All possibilities exhausted. */ - MDEBUG(("%d no midpoint\n", t->retry)); - freedfa(d); - freedfa(d2); + MDEBUG(("%d no midpoint\n", t->id)); return REG_NOMATCH; } mid = longest(v, d, begin, mid-1, NULL); @@ -918,73 +763,50 @@ ccondissect( * Failed to find a new one. */ - MDEBUG(("%d failed midpoint\n", t->retry)); - freedfa(d); - freedfa(d2); + MDEBUG(("%d failed midpoint\n", t->id)); return REG_NOMATCH; } - MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid))); - v->mem[t->retry] = (mid - begin) + 1; - zapmem(v, t->left); - zapmem(v, t->right); + MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid))); + zaptreesubs(v, t->left); + zaptreesubs(v, t->right); } } /* - - crevdissect - determine backref shortest-first subexpression matches - * The retry memory stores the offset of the trial midpoint from begin, plus 1 - * so that 0 uniquely means "clean slate". - ^ static int crevdissect(struct vars *, struct subre *, chr *, chr *); + - crevcondissect - dissect match for concatenation node, shortest-first + ^ static int crevcondissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -crevdissect( +crevcondissect( struct vars *v, struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { - struct dfa *d; - struct dfa *d2; + struct dfa *d, *d2; chr *mid; - int er; assert(t->op == '.'); assert(t->left != NULL && t->left->cnfa.nstates > 0); assert(t->right != NULL && t->right->cnfa.nstates > 0); assert(t->left->flags&SHORTER); - /* - * Concatenation -- need to split the substring between parts. - */ + d = getsubdfa(v, t->left); + NOERR(); + d2 = getsubdfa(v, t->right); + NOERR(); - d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); - if (ISERR()) { - return v->err; - } - d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC); - if (ISERR()) { - freedfa(d); - return v->err; - } - MDEBUG(("crev %d\n", t->retry)); + MDEBUG(("crevcon %d\n", t->id)); /* * Pick a tentative midpoint. */ - if (v->mem[t->retry] == 0) { - mid = shortest(v, d, begin, begin, end, NULL, NULL); - if (mid == NULL) { - freedfa(d); - freedfa(d2); - return REG_NOMATCH; - } - MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); - v->mem[t->retry] = (mid - begin) + 1; - } else { - mid = begin + (v->mem[t->retry] - 1); - MDEBUG(("working midpoint %ld\n", LOFF(mid))); + mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL); + if (mid == NULL) { + return REG_NOMATCH; } + MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); /* * Iterate until satisfaction or failure. @@ -996,7 +818,8 @@ crevdissect( */ if (longest(v, d2, mid, end, NULL) == end) { - er = cdissect(v, t->left, begin, mid); + int er = cdissect(v, t->left, begin, mid); + if (er == REG_OKAY) { er = cdissect(v, t->right, mid, end); if (er == REG_OKAY) { @@ -1005,14 +828,10 @@ crevdissect( */ MDEBUG(("successful\n")); - freedfa(d); - freedfa(d2); return REG_OKAY; } } - if (er != REG_OKAY && er != REG_NOMATCH) { - freedfa(d); - freedfa(d2); + if (er != REG_NOMATCH) { return er; } } @@ -1026,9 +845,7 @@ crevdissect( * All possibilities exhausted. */ - MDEBUG(("%d no midpoint\n", t->retry)); - freedfa(d); - freedfa(d2); + MDEBUG(("%d no midpoint\n", t->id)); return REG_NOMATCH; } mid = shortest(v, d, begin, mid+1, end, NULL, NULL); @@ -1037,157 +854,474 @@ crevdissect( * Failed to find a new one. */ - MDEBUG(("%d failed midpoint\n", t->retry)); - freedfa(d); - freedfa(d2); + MDEBUG(("%d failed midpoint\n", t->id)); return REG_NOMATCH; } - MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid))); - v->mem[t->retry] = (mid - begin) + 1; - zapmem(v, t->left); - zapmem(v, t->right); + MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid))); + zaptreesubs(v, t->left); + zaptreesubs(v, t->right); } } /* - - cbrdissect - determine backref subexpression matches + - cbrdissect - dissect match for backref node ^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ cbrdissect( struct vars *v, struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { - int i; - int n = t->subno; - size_t len; - chr *paren; + int n = t->subno, min = t->min, max = t->max; + size_t numreps; + size_t tlen; + size_t brlen; + chr *brstring; chr *p; - chr *stop; - int min = t->min; - int max = t->max; assert(t != NULL); assert(t->op == 'b'); assert(n >= 0); assert((size_t)n < v->nmatch); - MDEBUG(("cbackref n%d %d{%d-%d}\n", t->retry, n, min, max)); + MDEBUG(("cbackref n%d %d{%d-%d}\n", t->id, n, min, max)); + /* get the backreferenced string */ if (v->pmatch[n].rm_so == -1) { return REG_NOMATCH; } - paren = v->start + v->pmatch[n].rm_so; - len = v->pmatch[n].rm_eo - v->pmatch[n].rm_so; + brstring = v->start + v->pmatch[n].rm_so; + brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so; - /* - * No room to maneuver -- retries are pointless. - */ - - if (v->mem[t->retry]) { + /* special cases for zero-length strings */ + if (brlen == 0) { + /* + * matches only if target is zero length, but any number of + * repetitions can be considered to be present + */ + if (begin == end && min <= max) { + MDEBUG(("cbackref matched trivially\n")); + return REG_OKAY; + } return REG_NOMATCH; } - v->mem[t->retry] = 1; - - /* - * Special-case zero-length string. - */ - - if (len == 0) { - if (begin == end) { + if (begin == end) { + /* matches only if zero repetitions are okay */ + if (min == 0) { + MDEBUG(("cbackref matched trivially\n")); return REG_OKAY; } return REG_NOMATCH; } /* - * And too-short string. + * check target length to see if it could possibly be an allowed number of + * repetitions of brstring */ - assert(end >= begin); - if ((size_t)(end - begin) < len) { + assert(end > begin); + tlen = end - begin; + if (tlen % brlen != 0) return REG_NOMATCH; + numreps = tlen / brlen; + if (numreps < (size_t)min || (numreps > (size_t)max && max != DUPINF)) + return REG_NOMATCH; + + /* okay, compare the actual string contents */ + p = begin; + while (numreps-- > 0) { + if ((*v->g->compare) (brstring, p, brlen) != 0) + return REG_NOMATCH; + p += brlen; } - stop = end - len; - /* - * Count occurrences. - */ + MDEBUG(("cbackref matched\n")); + return REG_OKAY; +} + +/* + - caltdissect - dissect match for alternation node + ^ static int caltdissect(struct vars *, struct subre *, chr *, chr *); + */ +static int /* regexec return code */ +caltdissect( + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ +{ + struct dfa *d; + int er; + + /* We loop, rather than tail-recurse, to handle a chain of alternatives */ + while (t != NULL) { + assert(t->op == '|'); + assert(t->left != NULL && t->left->cnfa.nstates > 0); - i = 0; - for (p = begin; p <= stop && (i < max || max == DUPINF); p += len) { - if ((*v->g->compare)(paren, p, len) != 0) { - break; + MDEBUG(("calt n%d\n", t->id)); + + d = getsubdfa(v, t->left); + NOERR(); + if (longest(v, d, begin, end, (int *) NULL) == end) { + MDEBUG(("calt matched\n")); + er = cdissect(v, t->left, begin, end); + if (er != REG_NOMATCH) { + return er; + } } - i++; + + t = t->right; } - MDEBUG(("cbackref found %d\n", i)); + + return REG_NOMATCH; +} + +/* + - citerdissect - dissect match for iteration node + ^ static int citerdissect(struct vars *, struct subre *, chr *, chr *); + */ +static int /* regexec return code */ +citerdissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ +{ + struct dfa *d; + chr **endpts; + chr *limit; + int min_matches; + size_t max_matches; + int nverified; + int k; + int i; + int er; + + assert(t->op == '*'); + assert(t->left != NULL && t->left->cnfa.nstates > 0); + assert(!(t->left->flags & SHORTER)); + assert(begin <= end); /* - * And sort it out. + * If zero matches are allowed, and target string is empty, just declare + * victory. OTOH, if target string isn't empty, zero matches can't work + * so we pretend the min is 1. */ + min_matches = t->min; + if (min_matches <= 0) { + if (begin == end) + return REG_OKAY; + min_matches = 1; + } - if (p != end) { /* didn't consume all of it */ - return REG_NOMATCH; + /* + * We need workspace to track the endpoints of each sub-match. Normally + * we consider only nonzero-length sub-matches, so there can be at most + * end-begin of them. However, if min is larger than that, we will also + * consider zero-length sub-matches in order to find enough matches. + * + * For convenience, endpts[0] contains the "begin" pointer and we store + * sub-match endpoints in endpts[1..max_matches]. + */ + max_matches = end - begin; + if (max_matches > (size_t)t->max && t->max != DUPINF) + max_matches = t->max; + if (max_matches < (size_t)min_matches) + max_matches = min_matches; + endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *)); + if (endpts == NULL) + return REG_ESPACE; + endpts[0] = begin; + + d = getsubdfa(v, t->left); + if (ISERR()) { + FREE(endpts); + return v->err; } - if (min <= i && (i <= max || max == DUPINF)) { - return REG_OKAY; + MDEBUG(("citer %d\n", t->id)); + + /* + * Our strategy is to first find a set of sub-match endpoints that are + * valid according to the child node's DFA, and then recursively dissect + * each sub-match to confirm validity. If any validity check fails, + * backtrack the last sub-match and try again. And, when we next try for + * a validity check, we need not recheck any successfully verified + * sub-matches that we didn't move the endpoints of. nverified remembers + * how many sub-matches are currently known okay. + */ + + /* initialize to consider first sub-match */ + nverified = 0; + k = 1; + limit = end; + + /* iterate until satisfaction or failure */ + while (k > 0) { + /* try to find an endpoint for the k'th sub-match */ + endpts[k] = longest(v, d, endpts[k - 1], limit, (int *) NULL); + if (endpts[k] == NULL) { + /* no match possible, so see if we can shorten previous one */ + k--; + goto backtrack; + } + MDEBUG(("%d: working endpoint %d: %ld\n", + t->id, k, LOFF(endpts[k]))); + + /* k'th sub-match can no longer be considered verified */ + if (nverified >= k) + nverified = k - 1; + + if (endpts[k] != end) { + /* haven't reached end yet, try another iteration if allowed */ + if ((size_t)k >= max_matches) { + /* must try to shorten some previous match */ + k--; + goto backtrack; + } + + /* reject zero-length match unless necessary to achieve min */ + if (endpts[k] == endpts[k - 1] && + (k >= min_matches || min_matches - k < end - endpts[k])) + goto backtrack; + + k++; + limit = end; + continue; + } + + /* + * We've identified a way to divide the string into k sub-matches + * that works so far as the child DFA can tell. If k is an allowed + * number of matches, start the slow part: recurse to verify each + * sub-match. We always have k <= max_matches, needn't check that. + */ + if (k < min_matches) + goto backtrack; + + MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k)); + + for (i = nverified + 1; i <= k; i++) { + zaptreesubs(v, t->left); + er = cdissect(v, t->left, endpts[i - 1], endpts[i]); + if (er == REG_OKAY) { + nverified = i; + continue; + } + if (er == REG_NOMATCH) + break; + /* oops, something failed */ + FREE(endpts); + return er; + } + + if (i > k) { + /* satisfaction */ + MDEBUG(("%d successful\n", t->id)); + FREE(endpts); + return REG_OKAY; + } + + /* match failed to verify, so backtrack */ + + backtrack: + /* + * Must consider shorter versions of the current sub-match. However, + * we'll only ask for a zero-length match if necessary. + */ + while (k > 0) { + chr *prev_end = endpts[k - 1]; + + if (endpts[k] > prev_end) { + limit = endpts[k] - 1; + if (limit > prev_end || + (k < min_matches && min_matches - k >= end - prev_end)) { + /* break out of backtrack loop, continue the outer one */ + break; + } + } + /* can't shorten k'th sub-match any more, consider previous one */ + k--; + } } - return REG_NOMATCH; /* out of range */ + + /* all possibilities exhausted */ + MDEBUG(("%d failed\n", t->id)); + FREE(endpts); + return REG_NOMATCH; } /* - - caltdissect - determine alternative subexpression matches (w. complications) - ^ static int caltdissect(struct vars *, struct subre *, chr *, chr *); + - creviterdissect - dissect match for iteration node, shortest-first + ^ static int creviterdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -caltdissect( - struct vars *v, - struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ +creviterdissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { struct dfa *d; - int er; -#define UNTRIED 0 /* not yet tried at all */ -#define TRYING 1 /* top matched, trying submatches */ -#define TRIED 2 /* top didn't match or submatches exhausted */ + chr **endpts; + chr *limit; + int min_matches; + size_t max_matches; + int nverified; + int k; + int i; + int er; + + assert(t->op == '*'); + assert(t->left != NULL && t->left->cnfa.nstates > 0); + assert(t->left->flags & SHORTER); + assert(begin <= end); - if (t == NULL) { - return REG_NOMATCH; + /* + * If zero matches are allowed, and target string is empty, just declare + * victory. OTOH, if target string isn't empty, zero matches can't work + * so we pretend the min is 1. + */ + min_matches = t->min; + if (min_matches <= 0) { + if (begin == end) + return REG_OKAY; + min_matches = 1; } - assert(t->op == '|'); - if (v->mem[t->retry] == TRIED) { - return caltdissect(v, t->right, begin, end); + + /* + * We need workspace to track the endpoints of each sub-match. Normally + * we consider only nonzero-length sub-matches, so there can be at most + * end-begin of them. However, if min is larger than that, we will also + * consider zero-length sub-matches in order to find enough matches. + * + * For convenience, endpts[0] contains the "begin" pointer and we store + * sub-match endpoints in endpts[1..max_matches]. + */ + max_matches = end - begin; + if (max_matches > (size_t)t->max && t->max != DUPINF) + max_matches = t->max; + if (max_matches < (size_t)min_matches) + max_matches = min_matches; + endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *)); + if (endpts == NULL) + return REG_ESPACE; + endpts[0] = begin; + + d = getsubdfa(v, t->left); + if (ISERR()) { + FREE(endpts); + return v->err; } + MDEBUG(("creviter %d\n", t->id)); - MDEBUG(("calt n%d\n", t->retry)); - assert(t->left != NULL); + /* + * Our strategy is to first find a set of sub-match endpoints that are + * valid according to the child node's DFA, and then recursively dissect + * each sub-match to confirm validity. If any validity check fails, + * backtrack the last sub-match and try again. And, when we next try for + * a validity check, we need not recheck any successfully verified + * sub-matches that we didn't move the endpoints of. nverified remembers + * how many sub-matches are currently known okay. + */ - if (v->mem[t->retry] == UNTRIED) { - d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); - if (ISERR()) { - return v->err; + /* initialize to consider first sub-match */ + nverified = 0; + k = 1; + limit = begin; + + /* iterate until satisfaction or failure */ + while (k > 0) { + /* disallow zero-length match unless necessary to achieve min */ + if (limit == endpts[k - 1] && + limit != end && + (k >= min_matches || min_matches - k < end - limit)) + limit++; + + /* if this is the last allowed sub-match, it must reach to the end */ + if ((size_t)k >= max_matches) + limit = end; + + /* try to find an endpoint for the k'th sub-match */ + endpts[k] = shortest(v, d, endpts[k - 1], limit, end, + (chr **) NULL, (int *) NULL); + if (endpts[k] == NULL) { + /* no match possible, so see if we can lengthen previous one */ + k--; + goto backtrack; + } + MDEBUG(("%d: working endpoint %d: %ld\n", + t->id, k, LOFF(endpts[k]))); + + /* k'th sub-match can no longer be considered verified */ + if (nverified >= k) + nverified = k - 1; + + if (endpts[k] != end) { + /* haven't reached end yet, try another iteration if allowed */ + if ((size_t)k >= max_matches) { + /* must try to lengthen some previous match */ + k--; + goto backtrack; + } + + k++; + limit = endpts[k - 1]; + continue; } - if (longest(v, d, begin, end, NULL) != end) { - freedfa(d); - v->mem[t->retry] = TRIED; - return caltdissect(v, t->right, begin, end); + + /* + * We've identified a way to divide the string into k sub-matches + * that works so far as the child DFA can tell. If k is an allowed + * number of matches, start the slow part: recurse to verify each + * sub-match. We always have k <= max_matches, needn't check that. + */ + if (k < min_matches) + goto backtrack; + + MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k)); + + for (i = nverified + 1; i <= k; i++) { + zaptreesubs(v, t->left); + er = cdissect(v, t->left, endpts[i - 1], endpts[i]); + if (er == REG_OKAY) { + nverified = i; + continue; + } + if (er == REG_NOMATCH) + break; + /* oops, something failed */ + FREE(endpts); + return er; } - freedfa(d); - MDEBUG(("calt matched\n")); - v->mem[t->retry] = TRYING; - } - er = cdissect(v, t->left, begin, end); - if (er != REG_NOMATCH) { - return er; + if (i > k) { + /* satisfaction */ + MDEBUG(("%d successful\n", t->id)); + FREE(endpts); + return REG_OKAY; + } + + /* match failed to verify, so backtrack */ + + backtrack: + /* + * Must consider longer versions of the current sub-match. + */ + while (k > 0) { + if (endpts[k] < end) { + limit = endpts[k] + 1; + /* break out of backtrack loop, continue the outer one */ + break; + } + /* can't lengthen k'th sub-match any more, consider previous one */ + k--; + } } - v->mem[t->retry] = TRIED; - return caltdissect(v, t->right, begin, end); + /* all possibilities exhausted */ + MDEBUG(("%d failed\n", t->id)); + FREE(endpts); + return REG_NOMATCH; } #include "rege_dfa.c" diff --git a/generic/regfronts.c b/generic/regfronts.c index 5003297..088a640 100644 --- a/generic/regfronts.c +++ b/generic/regfronts.c @@ -39,7 +39,7 @@ int regcomp( regex_t *re, - CONST char *str, + const char *str, int flags) { size_t len; @@ -61,12 +61,12 @@ regcomp( int regexec( regex_t *re, - CONST char *str, + const char *str, size_t nmatch, regmatch_t pmatch[], int flags) { - CONST char *start; + const char *start; size_t len; int f = flags; diff --git a/generic/regguts.h b/generic/regguts.h index 72bdcb3..1ac2465 100644 --- a/generic/regguts.h +++ b/generic/regguts.h @@ -39,15 +39,6 @@ * Things that regcustom.h might override. */ -/* standard header files (NULL is a reasonable indicator for them) */ -#ifndef NULL -#include <stdio.h> -#include <stdlib.h> -#include <ctype.h> -#include <limits.h> -#include <string.h> -#endif - /* assertions */ #ifndef assert #ifndef REG_DEBUG @@ -75,11 +66,6 @@ #define NOPARMS void /* for empty parm lists */ #endif -/* const */ -#ifndef CONST -#define CONST const /* for old compilers, might be empty */ -#endif - /* function-pointer declarator */ #ifndef FUNCPTR #if __STDC__ >= 1 @@ -101,9 +87,6 @@ #endif /* want size of a char in bits, and max value in bounded quantifiers */ -#ifndef CHAR_BIT -#include <limits.h> -#endif #ifndef _POSIX2_RE_DUP_MAX #define _POSIX2_RE_DUP_MAX 255 /* normally from <limits.h> */ #endif @@ -203,7 +186,14 @@ struct colordesc { union tree *block; /* block of solid color, if any */ }; -/* the color map itself */ +/* + * The color map itself + * + * Much of the data in the colormap struct is only used at compile time. + * However, the bulk of the space usage is in the "tree" structure, so it's + * not clear that there's much point in converting the rest to a more compact + * form when compilation is finished. + */ struct colormap { int magic; #define CMMAGIC 0x876 @@ -259,12 +249,11 @@ struct cvec { struct state; struct arc { - int type; -#define ARCFREE '\0' + int type; /* 0 if free, else an NFA arc type code */ color co; struct state *from; /* where it's from (and contained within) */ struct state *to; /* where it's to */ - struct arc *outchain; /* *from's outs chain or free chain */ + struct arc *outchain; /* link in *from's outs chain or free chain */ struct arc *outchainRev; /* back-link in *from's outs chain */ #define freechain outchain /* we do not maintain "freechainRev" */ struct arc *inchain; /* *to's ins chain */ @@ -313,11 +302,22 @@ struct nfa { /* * definitions for compacted NFA + * + * The main space savings in a compacted NFA is from making the arcs as small + * as possible. We store only the transition color and next-state number for + * each arc. The list of out arcs for each state is an array beginning at + * cnfa.states[statenumber], and terminated by a dummy carc struct with + * co == COLORLESS. + * + * The non-dummy carc structs are of two types: plain arcs and LACON arcs. + * Plain arcs just store the transition color number as "co". LACON arcs + * store the lookahead constraint number plus cnfa.ncolors as "co". LACON + * arcs can be distinguished from plain by testing for co >= cnfa.ncolors. */ struct carc { color co; /* COLORLESS is list terminator */ - int to; /* state number */ + int to; /* next-state number */ }; struct cnfa { @@ -329,7 +329,10 @@ struct cnfa { int post; /* teardown state number */ color bos[2]; /* colors, if any, assigned to BOS and BOL */ color eos[2]; /* colors, if any, assigned to EOS and EOL */ + char *stflags; /* vector of per-state flags bytes */ +#define CNFA_NOPROGRESS 01 /* flag bit for a no-progress state */ struct carc **states; /* vector of pointers to outarc lists */ + /* states[n] are pointers into a single malloc'd array of arcs */ struct carc *arcs; /* the area for the lists */ }; #define ZAPCNFA(cnfa) ((cnfa).nstates = 0) @@ -350,11 +353,28 @@ struct cnfa { /* * subexpression tree + * + * "op" is one of: + * '=' plain regex without interesting substructure (implemented as DFA) + * 'b' back-reference (has no substructure either) + * '(' capture node: captures the match of its single child + * '.' concatenation: matches a match for left, then a match for right + * '|' alternation: matches a match for left or a match for right + * '*' iteration: matches some number of matches of its single child + * + * Note: the right child of an alternation must be another alternation or + * NULL; hence, an N-way branch requires N alternation nodes, not N-1 as you + * might expect. This could stand to be changed. Actually I'd rather see + * a single alternation node with N children, but that will take revising + * the representation of struct subre. + * + * Note: when a backref is directly quantified, we stick the min/max counts + * into the backref rather than plastering an iteration node on top. This is + * for efficiency: there is no need to search for possible division points. */ struct subre { - char op; /* '|', '.' (concat), 'b' (backref), '(', - * '=' */ + char op; /* see type codes above */ char flags; #define LONGER 01 /* prefers longer match */ #define SHORTER 02 /* prefers shorter match */ @@ -370,10 +390,10 @@ struct subre { #define PREF(f) ((f)&NOPROP) #define PREF2(f1, f2) ((PREF(f1) != 0) ? PREF(f1) : PREF(f2)) #define COMBINE(f1, f2) (UP((f1)|(f2)) | PREF2(f1, f2)) - short retry; /* index into retry memory */ + short id; /* ID of subre (1..ntree-1) */ int subno; /* subexpression number (for 'b' and '(') */ - short min; /* min repetitions, for backref only */ - short max; /* max repetitions, for backref only */ + short min; /* min repetitions for iteration or backref */ + short max; /* max repetitions for iteration or backref */ struct subre *left; /* left child, if any (also freelist chain) */ struct subre *right; /* right child, if any */ struct state *begin; /* outarcs from here... */ @@ -388,7 +408,7 @@ struct subre { */ struct fns { - VOID FUNCPTR(free, (regex_t *)); + void FUNCPTR(free, (regex_t *)); }; /* @@ -403,9 +423,9 @@ struct guts { size_t nsub; /* copy of re_nsub */ struct subre *tree; struct cnfa search; /* for fast preliminary search */ - int ntree; + int ntree; /* number of subre's, plus one */ struct colormap cmap; - int FUNCPTR(compare, (CONST chr *, CONST chr *, size_t)); + int FUNCPTR(compare, (const chr *, const chr *, size_t)); struct subre *lacons; /* lookahead-constraint vector */ int nlacons; /* size of lacons */ }; |