diff options
| -rw-r--r-- | generic/rege_dfa.c | 212 | ||||
| -rw-r--r-- | generic/regexec.c | 478 |
2 files changed, 338 insertions, 352 deletions
diff --git a/generic/rege_dfa.c b/generic/rege_dfa.c index e233680..920ea6c 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; @@ -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; /* @@ -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++) { 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; + 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 */ + 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; + noProgress = 0; } FDEBUG(("%d :> %d\n", i, ca->to)); } } } } - if (!gotstate) { + if (!gotState) { return NULL; } h = HASH(d->work, d->wordsper); @@ -585,14 +577,14 @@ miss( } } 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,26 @@ miss( */ } - if (!sawlacons) { /* lookahead conds. always cache miss */ + if (!sawLAConstraints) { /* lookahead conds. always cache miss */ FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, 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 +624,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)); /* @@ -695,8 +685,7 @@ getvacant( 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 +718,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; /* diff --git a/generic/regexec.c b/generic/regexec.c index b369d2b..9b6a693 100644 --- a/generic/regexec.c +++ b/generic/regexec.c @@ -126,33 +126,33 @@ struct vars { /* 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 *); -static inline int cdissect(struct vars *, struct subre *, chr *, chr *); -static int ccaptdissect(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 cbrdissect(struct vars *, struct subre *, chr *, chr *); -static int caltdissect(struct vars *, struct subre *, chr *, chr *); +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 zapSubexpressions(regmatch_t *const, const size_t); +static void zapSubtree(struct vars *const, struct subre *const); +static void subset(struct vars *const, struct subre *const, chr *const, chr *const); +static int dissect(struct vars *const, struct subre *, chr *const, chr *const); +static int concatenationDissect(struct vars *const, struct subre *const, chr *const, chr *const); +static int alternationDissect(struct vars *const, struct subre *, chr *const, chr *const); +static inline int complicatedDissect(struct vars *const, struct subre *const, chr *const, chr *const); +static int complicatedCapturingDissect(struct vars *const, struct subre *const, chr *const, chr *const); +static int complicatedConcatenationDissect(struct vars *const, struct subre *const, chr *const, chr *const); +static int complicatedReversedDissect(struct vars *const, struct subre *const, chr *const, chr *const); +static int complicatedBackrefDissect(struct vars *const, struct subre *const, chr *const, chr *const); +static int complicatedAlternationDissect(struct vars *const, struct subre *, chr *const, chr *const); /* === 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 =====^!^===== */ @@ -172,9 +172,8 @@ exec( int flags) { AllocVars(v); - int st; + int st, backref; size_t n; - int backref; #define LOCALMAT 20 regmatch_t mat[LOCALMAT]; #define LOCALMEM 40 @@ -265,9 +264,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); } /* @@ -275,7 +274,7 @@ exec( */ if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) { - zapsubs(pmatch, nmatch); + zapSubexpressions(pmatch, nmatch); n = (nmatch < v->nmatch) ? nmatch : v->nmatch; memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t)); } @@ -295,23 +294,20 @@ exec( } /* - - find - find a match for the main NFA (no-complications case) - ^ static int find(struct vars *, struct cnfa *, struct colormap *); + - 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; @@ -319,13 +315,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); @@ -351,7 +347,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++) { @@ -370,7 +366,7 @@ find( } } assert(end != NULL); /* search RE succeeded so loop should */ - freedfa(d); + freeDFA(d); /* * And pin down details. @@ -395,38 +391,37 @@ find( * Submatches. */ - zapsubs(v->pmatch, v->nmatch); + zapSubexpressions(v->pmatch, v->nmatch); return dissect(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); @@ -441,30 +436,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; @@ -480,7 +471,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 (;;) { @@ -497,9 +488,9 @@ cfindloop( } MDEBUG(("tentative end %ld\n", LOFF(end))); - zapsubs(v->pmatch, v->nmatch); - zapmem(v, v->g->tree); - er = cdissect(v, v->g->tree, begin, end); + zapSubexpressions(v->pmatch, v->nmatch); + zapSubtree(v, v->g->tree); + er = complicatedDissect(v, v->g->tree, begin, end); if (er == REG_OKAY) { if (v->nmatch > 0) { v->pmatch[0].rm_so = OFF(begin); @@ -539,13 +530,13 @@ cfindloop( } /* - - zapsubs - initialize the subexpression matches to "no match" - ^ static void zapsubs(regmatch_t *, size_t); + - zapSubexpressions - initialize the subexpression matches to "no match" + ^ static void zapSubexpressions(regmatch_t *, size_t); */ static void -zapsubs( - regmatch_t *p, - size_t n) +zapSubexpressions( + regmatch_t *const p, + const size_t n) { size_t i; @@ -556,13 +547,13 @@ zapsubs( } /* - - zapmem - initialize the retry memory of a subtree to zeros - ^ static void zapmem(struct vars *, struct subre *); + - zapSubtree - initialize the retry memory of a subtree to zeros + ^ static void zapSubtree(struct vars *, struct subre *); */ static void -zapmem( - struct vars *v, - struct subre *t) +zapSubtree( + struct vars *const v, + struct subre *const t) { if (t == NULL) { return; @@ -573,14 +564,14 @@ zapmem( if (t->op == '(') { assert(t->subno > 0); v->pmatch[t->subno].rm_so = -1; - v->pmatch[t->subno].rm_eo = -1; + v->pmatch[t->subno].rm_eo = -1; } if (t->left != NULL) { - zapmem(v, t->left); + zapSubtree(v, t->left); } if (t->right != NULL) { - zapmem(v, t->right); + zapSubtree(v, t->right); } } @@ -590,10 +581,10 @@ zapmem( */ 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; @@ -613,10 +604,10 @@ subset( */ static int /* regexec return code */ dissect( - struct vars *v, + struct vars *const v, struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ + chr *const begin, /* beginning of relevant substring */ + chr *const end) /* end of same */ { #ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION restart: @@ -630,12 +621,12 @@ dissect( return REG_OKAY; /* no action, parent did the work */ case '|': /* alternation */ assert(t->left != NULL); - return altdissect(v, t, begin, end); + return alternationDissect(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); + return concatenationDissect(v, t, begin, end); case '(': /* capturing */ assert(t->left != NULL && t->right == NULL); assert(t->subno > 0); @@ -652,18 +643,18 @@ dissect( } /* - - condissect - determine concatenation subexpression matches (uncomplicated) - ^ static int condissect(struct vars *, struct subre *, chr *, chr *); + - concatenationDissect - determine concatenation subexpression matches + - (uncomplicated) + ^ static int concatenationDissect(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 */ +concatenationDissect( + struct vars *const v, + struct subre *const t, + chr *const begin, /* beginning of relevant substring */ + chr *const end) /* end of same */ { - struct dfa *d; - struct dfa *d2; + struct dfa *d, *d2; chr *mid; int i; int shorter = (t->left->flags&SHORTER) ? 1 : 0; @@ -673,12 +664,12 @@ condissect( 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); + d = newDFA(v, &t->left->cnfa, &v->g->cmap, &v->dfa1); NOERR(); - d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &v->dfa2); + d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, &v->dfa2); if (ISERR()) { assert(d2 == NULL); - freedfa(d); + freeDFA(d); return v->err; } @@ -692,8 +683,8 @@ condissect( mid = longest(v, d, begin, end, NULL); } if (mid == NULL) { - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return REG_ASSERT; } MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); @@ -713,8 +704,8 @@ condissect( */ MDEBUG(("no midpoint!\n")); - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return REG_ASSERT; } if (shorter) { @@ -728,8 +719,8 @@ condissect( */ MDEBUG(("failed midpoint!\n")); - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return REG_ASSERT; } MDEBUG(("new midpoint %ld\n", LOFF(mid))); @@ -740,8 +731,8 @@ condissect( */ MDEBUG(("successful\n")); - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); i = dissect(v, t->left, begin, mid); if (i != REG_OKAY) { return i; @@ -750,54 +741,55 @@ condissect( } /* - - altdissect - determine alternative subexpression matches (uncomplicated) - ^ static int altdissect(struct vars *, struct subre *, chr *, chr *); + - alternationDissect - determine alternative subexpression matches (uncomplicated) + ^ static int alternationDissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -altdissect( - struct vars *v, +alternationDissect( + struct vars *const v, struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ + chr *const begin, /* beginning of relevant substring */ + chr *const end) /* end of same */ { - struct dfa *d; int i; assert(t != NULL); assert(t->op == '|'); for (i = 0; t != NULL; t = t->right, i++) { + struct dfa *d; + 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); + 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); + freeDFA(d); return dissect(v, t->left, begin, end); } - freedfa(d); + freeDFA(d); } return REG_ASSERT; /* none of them matched?!? */ } /* - - cdissect - determine subexpression matches (with complications) + - complicatedDissect - 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". - ^ static int cdissect(struct vars *, struct subre *, chr *, chr *); + ^ static int complicatedDissect(struct vars *, struct subre *, chr *, chr *); */ static inline int /* regexec return code */ -cdissect( - struct vars *v, - struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ +complicatedDissect( + struct vars *const v, + struct subre *const t, + chr *const begin, /* beginning of relevant substring */ + chr *const end) /* end of same */ { assert(t != NULL); - MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op)); + MDEBUG(("complicatedDissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op)); switch (t->op) { case '=': /* terminal node */ @@ -805,30 +797,30 @@ cdissect( return REG_OKAY; /* no action, parent did the work */ case '|': /* alternation */ assert(t->left != NULL); - return caltdissect(v, t, begin, end); + return complicatedAlternationDissect(v, t, begin, end); case 'b': /* back ref -- shouldn't be calling us! */ assert(t->left == NULL && t->right == NULL); - return cbrdissect(v, t, begin, end); + return complicatedBackrefDissect(v, t, begin, end); case '.': /* concatenation */ assert(t->left != NULL && t->right != NULL); - return ccondissect(v, t, begin, end); + return complicatedConcatenationDissect(v, t, begin, end); case '(': /* capturing */ assert(t->left != NULL && t->right == NULL); assert(t->subno > 0); - return ccaptdissect(v, t, begin, end); + return complicatedCapturingDissect(v, t, begin, end); default: return REG_ASSERT; } } static int /* regexec return code */ -ccaptdissect( - struct vars *v, - struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ +complicatedCapturingDissect( + struct vars *const v, + struct subre *const t, + chr *const begin, /* beginning of relevant substring */ + chr *const end) /* end of same */ { - int er = cdissect(v, t->left, begin, end); + int er = complicatedDissect(v, t->left, begin, end); if (er == REG_OKAY) { subset(v, t, begin, end); @@ -837,41 +829,39 @@ ccaptdissect( } /* - - ccondissect - concatenation subexpression matches (with complications) + - complicatedConcatenationDissect - 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". - ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *); + ^ static int complicatedConcatenationDissect(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 */ +complicatedConcatenationDissect( + struct vars *const v, + struct subre *const t, + chr *const begin, /* beginning of relevant substring */ + chr *const 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); if (t->left->flags&SHORTER) { /* reverse scan */ - return crevdissect(v, t, begin, end); + return complicatedReversedDissect(v, t, begin, end); } - d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + 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); + d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC); if (ISERR()) { - freedfa(d); + freeDFA(d); return v->err; } - MDEBUG(("cconcat %d\n", t->retry)); + MDEBUG(("cConcat %d\n", t->retry)); /* * Pick a tentative midpoint. @@ -880,8 +870,8 @@ ccondissect( if (v->mem[t->retry] == 0) { mid = longest(v, d, begin, end, NULL); if (mid == NULL) { - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return REG_NOMATCH; } MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); @@ -901,23 +891,24 @@ ccondissect( */ if (longest(v, d2, mid, end, NULL) == end) { - er = cdissect(v, t->left, begin, mid); + int er = complicatedDissect(v, t->left, begin, mid); + if (er == REG_OKAY) { - er = cdissect(v, t->right, mid, end); + er = complicatedDissect(v, t->right, mid, end); if (er == REG_OKAY) { /* * Satisfaction. */ MDEBUG(("successful\n")); - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return REG_OKAY; } } if ((er != REG_OKAY) && (er != REG_NOMATCH)) { - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return er; } } @@ -932,8 +923,8 @@ ccondissect( */ MDEBUG(("%d no midpoint\n", t->retry)); - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return REG_NOMATCH; } mid = longest(v, d, begin, mid-1, NULL); @@ -943,34 +934,33 @@ ccondissect( */ MDEBUG(("%d failed midpoint\n", t->retry)); - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); 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); + zapSubtree(v, t->left); + zapSubtree(v, t->right); } } /* - - crevdissect - determine backref shortest-first subexpression matches + - complicatedReversedDissect - 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 *); + ^ static int complicatedReversedDissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -crevdissect( - struct vars *v, - struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ +complicatedReversedDissect( + struct vars *const v, + struct subre *const t, + chr *const begin, /* beginning of relevant substring */ + chr *const 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); @@ -981,16 +971,16 @@ crevdissect( * Concatenation -- need to split the substring between parts. */ - d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + 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); + d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC); if (ISERR()) { - freedfa(d); + freeDFA(d); return v->err; } - MDEBUG(("crev %d\n", t->retry)); + MDEBUG(("cRev %d\n", t->retry)); /* * Pick a tentative midpoint. @@ -999,8 +989,8 @@ crevdissect( if (v->mem[t->retry] == 0) { mid = shortest(v, d, begin, begin, end, NULL, NULL); if (mid == NULL) { - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return REG_NOMATCH; } MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); @@ -1020,23 +1010,24 @@ crevdissect( */ if (longest(v, d2, mid, end, NULL) == end) { - er = cdissect(v, t->left, begin, mid); + int er = complicatedDissect(v, t->left, begin, mid); + if (er == REG_OKAY) { - er = cdissect(v, t->right, mid, end); + er = complicatedDissect(v, t->right, mid, end); if (er == REG_OKAY) { /* * Satisfaction. */ MDEBUG(("successful\n")); - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return REG_OKAY; } } if (er != REG_OKAY && er != REG_NOMATCH) { - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return er; } } @@ -1051,8 +1042,8 @@ crevdissect( */ MDEBUG(("%d no midpoint\n", t->retry)); - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); return REG_NOMATCH; } mid = shortest(v, d, begin, mid+1, end, NULL, NULL); @@ -1062,36 +1053,31 @@ crevdissect( */ MDEBUG(("%d failed midpoint\n", t->retry)); - freedfa(d); - freedfa(d2); + freeDFA(d); + freeDFA(d2); 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); + zapSubtree(v, t->left); + zapSubtree(v, t->right); } } /* - - cbrdissect - determine backref subexpression matches - ^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *); + - complicatedBackrefDissect - determine backref subexpression matches + ^ static int complicatedBackrefDissect(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 */ +complicatedBackrefDissect( + struct vars *const v, + struct subre *const t, + chr *const begin, /* beginning of relevant substring */ + chr *const end) /* end of same */ { - int i; - int n = t->subno; + int i, n = t->subno, min = t->min, max = t->max; + chr *paren, *p, *stop; size_t len; - chr *paren; - chr *p; - chr *stop; - int min = t->min; - int max = t->max; assert(t != NULL); assert(t->op == 'b'); @@ -1163,55 +1149,67 @@ cbrdissect( } /* - - caltdissect - determine alternative subexpression matches (w. complications) - ^ static int caltdissect(struct vars *, struct subre *, chr *, chr *); + - complicatedAlternationDissect - determine alternative subexpression matches (w. + - complications) + ^ static int complicatedAlternationDissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -caltdissect( - struct vars *v, +complicatedAlternationDissect( + struct vars *const v, struct subre *t, - chr *begin, /* beginning of relevant substring */ - chr *end) /* end of same */ + chr *const begin, /* beginning of relevant substring */ + chr *const 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 */ +#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION + if (0) { + doRight: + t = t->right; + } +#endif if (t == NULL) { return REG_NOMATCH; } assert(t->op == '|'); if (v->mem[t->retry] == TRIED) { - return caltdissect(v, t->right, begin, end); + goto doRight; } - MDEBUG(("calt n%d\n", t->retry)); + MDEBUG(("cAlt n%d\n", t->retry)); assert(t->left != NULL); if (v->mem[t->retry] == UNTRIED) { - d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + struct dfa *d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + if (ISERR()) { return v->err; } if (longest(v, d, begin, end, NULL) != end) { - freedfa(d); + freeDFA(d); v->mem[t->retry] = TRIED; - return caltdissect(v, t->right, begin, end); + goto doRight; } - freedfa(d); - MDEBUG(("calt matched\n")); + freeDFA(d); + MDEBUG(("cAlt matched\n")); v->mem[t->retry] = TRYING; } - er = cdissect(v, t->left, begin, end); + er = complicatedDissect(v, t->left, begin, end); if (er != REG_NOMATCH) { return er; } v->mem[t->retry] = TRIED; - return caltdissect(v, t->right, begin, end); +#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION + goto doRight; +#else + doRight: + return complicatedAlternationDissect(v, t->right, begin, end); +#endif } #include "rege_dfa.c" |