diff options
Diffstat (limited to 'generic/regexec.c')
| -rw-r--r-- | generic/regexec.c | 505 |
1 files changed, 244 insertions, 261 deletions
diff --git a/generic/regexec.c b/generic/regexec.c index ad4b6e6..205fcc2 100644 --- a/generic/regexec.c +++ b/generic/regexec.c @@ -125,46 +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 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); +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 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 cbrdissect(struct vars *, struct subre *, chr *, chr *); +static int caltdissect(struct vars *, struct subre *, chr *, chr *); /* === rege_dfa.c === */ -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); +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 *); /* 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, @@ -172,8 +171,9 @@ exec( int flags) { AllocVars(v); - int st, backref; + int st; size_t n; + int backref; #define LOCALMAT 20 regmatch_t mat[LOCALMAT]; #define LOCALMEM 40 @@ -264,9 +264,9 @@ exec( assert(v->g->tree != NULL); if (backref) { - st = complicatedFind(v, &v->g->tree->cnfa, &v->g->cmap); + st = cfind(v, &v->g->tree->cnfa, &v->g->cmap); } else { - st = simpleFind(v, &v->g->tree->cnfa, &v->g->cmap); + st = find(v, &v->g->tree->cnfa, &v->g->cmap); } /* @@ -274,7 +274,7 @@ exec( */ if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) { - zapSubexpressions(pmatch, nmatch); + zapsubs(pmatch, nmatch); n = (nmatch < v->nmatch) ? nmatch : v->nmatch; memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t)); } @@ -294,20 +294,23 @@ exec( } /* - - simpleFind - find a match for the main NFA (no-complications case) - ^ static int simpleFind(struct vars *, struct cnfa *, struct colormap *); + - find - find a match for the main NFA (no-complications case) + ^ static int find(struct vars *, struct cnfa *, struct colormap *); */ static int -simpleFind( - struct vars *const v, - struct cnfa *const cnfa, - struct colormap *const cm) +find( + struct vars *v, + struct cnfa *cnfa, + struct colormap *cm) { - struct dfa *s, *d; - chr *begin, *end = NULL; + struct dfa *s; + struct dfa *d; + chr *begin; + chr *end = NULL; chr *cold; - chr *open, *close; /* Open and close of range of possible + chr *open; /* Open and close of range of possible * starts */ + chr *close; int hitend; int shorter = (v->g->tree->flags&SHORTER) ? 1 : 0; @@ -315,13 +318,13 @@ simpleFind( * 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); @@ -347,7 +350,7 @@ simpleFind( 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++) { @@ -366,7 +369,7 @@ simpleFind( } } assert(end != NULL); /* search RE succeeded so loop should */ - freeDFA(d); + freedfa(d); /* * And pin down details. @@ -391,37 +394,38 @@ simpleFind( * Submatches. */ - zapSubexpressions(v->pmatch, v->nmatch); + zapsubs(v->pmatch, v->nmatch); return dissect(v, v->g->tree, begin, end); } /* - - complicatedFind - find a match for the main NFA (with complications) - ^ static int complicatedFind(struct vars *, struct cnfa *, struct colormap *); + - cfind - find a match for the main NFA (with complications) + ^ static int cfind(struct vars *, struct cnfa *, struct colormap *); */ static int -complicatedFind( - struct vars *const v, - struct cnfa *const cnfa, - struct colormap *const cm) +cfind( + struct vars *v, + struct cnfa *cnfa, + struct colormap *cm) { - struct dfa *s, *d; + struct dfa *s; + struct dfa *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 = complicatedFindLoop(v, cnfa, cm, d, s, &cold); + ret = cfindloop(v, cnfa, cm, d, s, &cold); - freeDFA(d); - freeDFA(s); + freedfa(d); + freedfa(s); NOERR(); if (v->g->cflags®_EXPECT) { assert(v->details != NULL); @@ -436,26 +440,30 @@ complicatedFind( } /* - - complicatedFindLoop - the heart of complicatedFind - ^ static int complicatedFindLoop(struct vars *, struct cnfa *, struct colormap *, + - cfindloop - the heart of cfind + ^ static int cfindloop(struct vars *, struct cnfa *, struct colormap *, ^ struct dfa *, struct dfa *, chr **); */ static int -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 */ +cfindloop( + struct vars *v, + struct cnfa *cnfa, + struct colormap *cm, + struct dfa *d, + struct dfa *s, + chr **coldp) /* where to put coldstart pointer */ { - chr *begin, *end; + chr *begin; + chr *end; chr *cold; - chr *open, *close; /* Open and close of range of possible + chr *open; /* Open and close of range of possible * starts */ - chr *estart, *estop; - int er, hitend; + chr *close; + chr *estart; + chr *estop; + int er; int shorter = v->g->tree->flags&SHORTER; + int hitend; assert(d != NULL && s != NULL); cold = NULL; @@ -471,7 +479,7 @@ complicatedFindLoop( cold = NULL; MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close))); for (begin = open; begin <= close; begin++) { - MDEBUG(("\ncomplicatedFind trying at %ld\n", LOFF(begin))); + MDEBUG(("\ncfind trying at %ld\n", LOFF(begin))); estart = begin; estop = v->stop; for (;;) { @@ -488,9 +496,9 @@ complicatedFindLoop( } MDEBUG(("tentative end %ld\n", LOFF(end))); - zapSubexpressions(v->pmatch, v->nmatch); - zapSubtree(v, v->g->tree); - er = complicatedDissect(v, v->g->tree, begin, end); + zapsubs(v->pmatch, v->nmatch); + zapmem(v, v->g->tree); + er = cdissect(v, v->g->tree, begin, end); if (er == REG_OKAY) { if (v->nmatch > 0) { v->pmatch[0].rm_so = OFF(begin); @@ -525,13 +533,13 @@ complicatedFindLoop( } /* - - zapSubexpressions - initialize the subexpression matches to "no match" - ^ static void zapSubexpressions(regmatch_t *, size_t); + - zapsubs - initialize the subexpression matches to "no match" + ^ static VOID zapsubs(regmatch_t *, size_t); */ static void -zapSubexpressions( - regmatch_t *const p, - const size_t n) +zapsubs( + regmatch_t *p, + size_t n) { size_t i; @@ -542,13 +550,13 @@ zapSubexpressions( } /* - - zapSubtree - initialize the retry memory of a subtree to zeros - ^ static void zapSubtree(struct vars *, struct subre *); + - zapmem - initialize the retry memory of a subtree to zeros + ^ static VOID zapmem(struct vars *, struct subre *); */ static void -zapSubtree( - struct vars *const v, - struct subre *const t) +zapmem( + struct vars *v, + struct subre *t) { if (t == NULL) { return; @@ -559,27 +567,27 @@ zapSubtree( 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) { - zapSubtree(v, t->left); + zapmem(v, t->left); } if (t->right != NULL) { - zapSubtree(v, t->right); + zapmem(v, t->right); } } /* - subset - set any subexpression relevant to a successful subre - ^ static void subset(struct vars *, struct subre *, chr *, chr *); + ^ static VOID subset(struct vars *, struct subre *, chr *, chr *); */ static void subset( - struct vars *const v, - struct subre *const sub, - chr *const begin, - chr *const end) + struct vars *v, + struct subre *sub, + chr *begin, + chr *end) { int n = sub->subno; @@ -599,14 +607,11 @@ subset( */ static int /* regexec return code */ dissect( - struct vars *const v, + struct vars *v, struct subre *t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { -#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION - restart: -#endif assert(t != NULL); MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end))); @@ -616,40 +621,35 @@ dissect( return REG_OKAY; /* no action, parent did the work */ case '|': /* alternation */ assert(t->left != NULL); - return alternationDissect(v, t, begin, end); + 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 concatenationDissect(v, t, begin, end); + return condissect(v, t, begin, end); case '(': /* capturing */ assert(t->left != NULL && t->right == NULL); assert(t->subno > 0); subset(v, t, begin, end); -#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION - t = t->left; - goto restart; -#else return dissect(v, t->left, begin, end); -#endif default: return REG_ASSERT; } } /* - - concatenationDissect - determine concatenation subexpression matches - - (uncomplicated) - ^ static int concatenationDissect(struct vars *, struct subre *, chr *, chr *); + - condissect - determine concatenation subexpression matches (uncomplicated) + ^ static int condissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -concatenationDissect( - struct vars *const v, - struct subre *const t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ +condissect( + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { - struct dfa *d, *d2; + struct dfa *d; + struct dfa *d2; chr *mid; int i; int shorter = (t->left->flags&SHORTER) ? 1 : 0; @@ -659,12 +659,12 @@ concatenationDissect( 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; } @@ -678,8 +678,8 @@ concatenationDissect( 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))); @@ -699,8 +699,8 @@ concatenationDissect( */ MDEBUG(("no midpoint!\n")); - freeDFA(d); - freeDFA(d2); + freedfa(d); + freedfa(d2); return REG_ASSERT; } if (shorter) { @@ -714,8 +714,8 @@ concatenationDissect( */ MDEBUG(("failed midpoint!\n")); - freeDFA(d); - freeDFA(d2); + freedfa(d); + freedfa(d2); return REG_ASSERT; } MDEBUG(("new midpoint %ld\n", LOFF(mid))); @@ -726,8 +726,8 @@ concatenationDissect( */ MDEBUG(("successful\n")); - freeDFA(d); - freeDFA(d2); + freedfa(d); + freedfa(d2); i = dissect(v, t->left, begin, mid); if (i != REG_OKAY) { return i; @@ -736,55 +736,56 @@ concatenationDissect( } /* - - alternationDissect - determine alternative subexpression matches (uncomplicated) - ^ static int alternationDissect(struct vars *, struct subre *, chr *, chr *); + - altdissect - determine alternative subexpression matches (uncomplicated) + ^ static int altdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -alternationDissect( - struct vars *const v, +altdissect( + struct vars *v, struct subre *t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ + 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++) { - 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?!? */ } /* - - complicatedDissect - determine subexpression matches (with complications) + - 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". - ^ static int complicatedDissect(struct vars *, struct subre *, chr *, chr *); + ^ static int cdissect(struct vars *, struct subre *, chr *, chr *); */ -static inline int /* regexec return code */ -complicatedDissect( - struct vars *const v, - struct subre *const t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ +static int /* regexec return code */ +cdissect( + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { + int er; + assert(t != NULL); - MDEBUG(("complicatedDissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op)); + MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op)); switch (t->op) { case '=': /* terminal node */ @@ -792,71 +793,61 @@ complicatedDissect( return REG_OKAY; /* no action, parent did the work */ case '|': /* alternation */ assert(t->left != NULL); - return complicatedAlternationDissect(v, t, begin, end); + return caltdissect(v, t, begin, end); case 'b': /* back ref -- shouldn't be calling us! */ assert(t->left == NULL && t->right == NULL); - return complicatedBackrefDissect(v, t, begin, end); + return cbrdissect(v, t, begin, end); case '.': /* concatenation */ assert(t->left != NULL && t->right != NULL); - return complicatedConcatenationDissect(v, t, begin, end); + return ccondissect(v, t, begin, end); case '(': /* capturing */ assert(t->left != NULL && t->right == NULL); assert(t->subno > 0); - return complicatedCapturingDissect(v, t, begin, end); + er = cdissect(v, t->left, begin, end); + if (er == REG_OKAY) { + subset(v, t, begin, end); + } + return er; default: return REG_ASSERT; } } - -static int /* regexec return code */ -complicatedCapturingDissect( - struct vars *const v, - struct subre *const t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ -{ - int er = complicatedDissect(v, t->left, begin, end); - - if (er == REG_OKAY) { - subset(v, t, begin, end); - } - return er; -} /* - - complicatedConcatenationDissect - concatenation subexpression matches (with complications) + - 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". - ^ static int complicatedConcatenationDissect(struct vars *, struct subre *, chr *, chr *); + ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -complicatedConcatenationDissect( - struct vars *const v, - struct subre *const t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ +ccondissect( + struct vars *v, + struct subre *t, + 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); if (t->left->flags&SHORTER) { /* reverse scan */ - return complicatedReversedDissect(v, t, begin, end); + return crevdissect(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. @@ -865,8 +856,8 @@ complicatedConcatenationDissect( 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))); @@ -886,24 +877,23 @@ complicatedConcatenationDissect( */ if (longest(v, d2, mid, end, NULL) == end) { - int er = complicatedDissect(v, t->left, begin, mid); - + er = cdissect(v, t->left, begin, mid); if (er == REG_OKAY) { - er = complicatedDissect(v, t->right, mid, end); + er = cdissect(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; } } @@ -918,8 +908,8 @@ complicatedConcatenationDissect( */ 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); @@ -929,33 +919,34 @@ complicatedConcatenationDissect( */ 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; - zapSubtree(v, t->left); - zapSubtree(v, t->right); + zapmem(v, t->left); + zapmem(v, t->right); } } /* - - complicatedReversedDissect - determine backref shortest-first subexpression - - matches + - 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 complicatedReversedDissect(struct vars *, struct subre *, chr *, chr *); + ^ static int crevdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -complicatedReversedDissect( - struct vars *const v, - struct subre *const t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ +crevdissect( + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { - struct dfa *d, *d2; + struct dfa *d; + struct dfa *d2; chr *mid; + int er; assert(t->op == '.'); assert(t->left != NULL && t->left->cnfa.nstates > 0); @@ -966,16 +957,16 @@ complicatedReversedDissect( * 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. @@ -984,8 +975,8 @@ complicatedReversedDissect( 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))); @@ -1005,24 +996,23 @@ complicatedReversedDissect( */ if (longest(v, d2, mid, end, NULL) == end) { - int er = complicatedDissect(v, t->left, begin, mid); - + er = cdissect(v, t->left, begin, mid); if (er == REG_OKAY) { - er = complicatedDissect(v, t->right, mid, end); + er = cdissect(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; } } @@ -1037,8 +1027,8 @@ complicatedReversedDissect( */ 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); @@ -1048,31 +1038,36 @@ complicatedReversedDissect( */ 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; - zapSubtree(v, t->left); - zapSubtree(v, t->right); + zapmem(v, t->left); + zapmem(v, t->right); } } /* - - complicatedBackrefDissect - determine backref subexpression matches - ^ static int complicatedBackrefDissect(struct vars *, struct subre *, chr *, chr *); + - cbrdissect - determine backref subexpression matches + ^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -complicatedBackrefDissect( - struct vars *const v, - struct subre *const t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ +cbrdissect( + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { - int i, n = t->subno, min = t->min, max = t->max; - chr *paren, *p, *stop; + int i; + int n = t->subno; size_t len; + chr *paren; + chr *p; + chr *stop; + int min = t->min; + int max = t->max; assert(t != NULL); assert(t->op == 'b'); @@ -1123,7 +1118,7 @@ complicatedBackrefDissect( i = 0; for (p = begin; p <= stop && (i < max || max == INFINITY); p += len) { - if (v->g->compare(paren, p, len) != 0) { + if ((*v->g->compare)(paren, p, len) != 0) { break; } i++; @@ -1144,67 +1139,55 @@ complicatedBackrefDissect( } /* - - complicatedAlternationDissect - determine alternative subexpression matches (w. - - complications) - ^ static int complicatedAlternationDissect(struct vars *, struct subre *, chr *, chr *); + - caltdissect - determine alternative subexpression matches (w. complications) + ^ static int caltdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -complicatedAlternationDissect( - struct vars *const v, +caltdissect( + struct vars *v, struct subre *t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ + 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 */ -#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) { - goto doRight; + return caltdissect(v, t->right, begin, end); } - MDEBUG(("cAlt n%d\n", t->retry)); + MDEBUG(("calt n%d\n", t->retry)); assert(t->left != NULL); if (v->mem[t->retry] == UNTRIED) { - struct dfa *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; } if (longest(v, d, begin, end, NULL) != end) { - freeDFA(d); + freedfa(d); v->mem[t->retry] = TRIED; - goto doRight; + return caltdissect(v, t->right, begin, end); } - freeDFA(d); - MDEBUG(("cAlt matched\n")); + freedfa(d); + MDEBUG(("calt matched\n")); v->mem[t->retry] = TRYING; } - er = complicatedDissect(v, t->left, begin, end); + er = cdissect(v, t->left, begin, end); if (er != REG_NOMATCH) { return er; } v->mem[t->retry] = TRIED; -#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION - goto doRight; -#else - doRight: - return complicatedAlternationDissect(v, t->right, begin, end); -#endif + return caltdissect(v, t->right, begin, end); } #include "rege_dfa.c" |