From d9db840088cdabd2863a7bd92ca051cda3f56c46 Mon Sep 17 00:00:00 2001 From: dgp Date: Mon, 21 Sep 2015 19:04:40 +0000 Subject: [1115587][0e0e150e49] Major fix for regexp handling of quantified backrefs. Contributed by Tom Lane from the Postgres project. --- generic/regcomp.c | 97 +++--- generic/regexec.c | 940 ++++++++++++++++++++++++++++++------------------------ generic/regguts.h | 27 +- tests/reg.test | 10 +- 4 files changed, 609 insertions(+), 465 deletions(-) diff --git a/generic/regcomp.c b/generic/regcomp.c index 6fa3964..b8a5a87 100644 --- a/generic/regcomp.c +++ b/generic/regcomp.c @@ -1105,11 +1105,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: * - * where bypass is an empty, and prefix is some repetitions of atom + * [lp] ---> [s] ---prefix---> [begin] ---atom---> [end] ---rest---> [rp] + * + * where prefix is some repetitions of atom. In the general case we need + * + * [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 */ @@ -1120,11 +1126,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(); /* @@ -1171,27 +1175,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) { @@ -1209,16 +1194,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); @@ -1231,6 +1224,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 */ } /* @@ -1239,10 +1250,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)); @@ -1309,6 +1320,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 @@ -1718,11 +1731,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; @@ -1803,7 +1816,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 */ @@ -1816,7 +1829,7 @@ numst( assert(t != NULL); i = start; - t->retry = (short) i++; + t->id = (short) i++; if (t->left != NULL) { i = numst(t->left, i); } @@ -2151,14 +2164,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/regexec.c b/generic/regexec.c index 3b9af3e..e502ca5 100644 --- a/generic/regexec.c +++ b/generic/regexec.c @@ -107,7 +107,6 @@ 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 smalldfa dfa1; struct smalldfa dfa2; }; @@ -129,18 +128,16 @@ int exec(regex_t *, const chr *, size_t, rm_detail_t *, size_t, regmatch_t [], i 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 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 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); +static int cdissect(struct vars *, struct subre *, chr *, chr *); +static int ccondissect(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 *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); @@ -176,8 +173,6 @@ exec( size_t n; #define LOCALMAT 20 regmatch_t mat[LOCALMAT]; -#define LOCALMEM 40 - regoff_t mem[LOCALMEM]; /* * Sanity checks. @@ -235,28 +230,6 @@ 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; - } /* * Do it. @@ -274,7 +247,7 @@ exec( */ if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) { - zapSubexpressions(pmatch, nmatch); + zapallsubs(pmatch, nmatch); n = (nmatch < v->nmatch) ? nmatch : v->nmatch; memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t)); } @@ -286,9 +259,6 @@ exec( if (v->pmatch != pmatch && v->pmatch != mat) { FREE(v->pmatch); } - if (v->mem != NULL && v->mem != mem) { - FREE(v->mem); - } FreeVars(v); return st; } @@ -388,11 +358,11 @@ simpleFind( } /* - * Submatches. + * Find submatches. */ - zapSubexpressions(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); } /* @@ -488,9 +458,8 @@ 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); + zapallsubs(v->pmatch, v->nmatch); + er = cdissect(v, v->g->tree, begin, end); if (er == REG_OKAY) { if (v->nmatch > 0) { v->pmatch[0].rm_so = OFF(begin); @@ -525,11 +494,11 @@ complicatedFindLoop( } /* - - zapSubexpressions - initialize the subexpression matches to "no match" - ^ static void zapSubexpressions(regmatch_t *, size_t); + - zapallsubs - initialize all subexpression matches to "no match" + ^ static void zapallsubs(regmatch_t *, size_t); */ static void -zapSubexpressions( +zapallsubs( regmatch_t *const p, const size_t n) { @@ -542,36 +511,33 @@ zapSubexpressions( } /* - - zapSubtree - initialize the retry memory of a subtree to zeros - ^ static void zapSubtree(struct vars *, struct subre *); + - zaptreesubs - initialize subexpressions within subtree to "no match" + ^ static void zaptreesubs(struct vars *, struct subre *); */ static void -zapSubtree( +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) { - zapSubtree(v, t->left); + zaptreesubs(v, t->left); } if (t->right != NULL) { - zapSubtree(v, t->right); + zaptreesubs(v, t->right); } } /* - - subset - set any subexpression relevant to a successful subre + - subset - set subexpression match data for a successful subre ^ static void subset(struct vars *, struct subre *, chr *, chr *); */ static void @@ -594,243 +560,87 @@ subset( } /* - - dissect - determine subexpression matches (uncomplicated case) - ^ static int dissect(struct vars *, struct subre *, chr *, chr *); - */ -static int /* regexec return code */ -dissect( - struct vars *const v, - struct subre *t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ -{ -#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION - restart: -#endif - 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 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 concatenationDissect(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 *); + - 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 */ -concatenationDissect( +cdissect( struct vars *const v, struct subre *const t, chr *const begin, /* beginning of relevant substring */ chr *const end) /* end of same */ { - struct dfa *d, *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); -} - -/* - - alternationDissect - determine alternative subexpression matches (uncomplicated) - ^ static int alternationDissect(struct vars *, struct subre *, chr *, chr *); - */ -static int /* regexec return code */ -alternationDissect( - struct vars *const v, - struct subre *t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ -{ - int i; + int er; 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); - 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?!? */ -} - -/* - - 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 complicatedDissect(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 */ -{ - 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 */ assert(t->left == NULL && t->right == NULL); - return REG_OKAY; /* no action, parent did the work */ - case '|': /* alternation */ - assert(t->left != NULL); - return complicatedAlternationDissect(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 complicatedBackrefDissect(v, t, begin, end); + er = cbrdissect(v, t, begin, end); + break; case '.': /* concatenation */ assert(t->left != NULL && t->right != NULL); - return complicatedConcatenationDissect(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); - return complicatedCapturingDissect(v, t, begin, end); + er = cdissect(v, t->left, begin, end); + if (er == REG_OKAY) { + subset(v, t, begin, end); + } + break; default: - return REG_ASSERT; + er = REG_ASSERT; + break; } -} -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); + /* + * 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)); - if (er == REG_OKAY) { - subset(v, t, begin, end); - } return er; } /* - - 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 complicatedConcatenationDissect(struct vars *, struct subre *, chr *, chr *); + - ccondissect - concatenation subexpression matches (with complications) + ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -complicatedConcatenationDissect( +ccondissect( struct vars *const v, struct subre *const t, chr *const begin, /* beginning of relevant substring */ @@ -842,10 +652,7 @@ complicatedConcatenationDissect( 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); - } + assert(!(t->left->flags & SHORTER)); d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); if (ISERR()) { @@ -856,25 +663,18 @@ complicatedConcatenationDissect( 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) { + freeDFA(d); + freeDFA(d2); + return REG_NOMATCH; } + MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); /* * Iterate until satisfaction or failure. @@ -886,10 +686,10 @@ complicatedConcatenationDissect( */ if (longest(v, d2, mid, end, NULL) == end) { - int er = complicatedDissect(v, t->left, begin, mid); + int 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. @@ -901,7 +701,7 @@ complicatedConcatenationDissect( return REG_OKAY; } } - if ((er != REG_OKAY) && (er != REG_NOMATCH)) { + if (er != REG_NOMATCH) { freeDFA(d); freeDFA(d2); return er; @@ -917,7 +717,7 @@ complicatedConcatenationDissect( * All possibilities exhausted. */ - MDEBUG(("%d no midpoint\n", t->retry)); + MDEBUG(("%d no midpoint\n", t->id)); freeDFA(d); freeDFA(d2); return REG_NOMATCH; @@ -928,27 +728,23 @@ complicatedConcatenationDissect( * Failed to find a new one. */ - MDEBUG(("%d failed midpoint\n", t->retry)); + MDEBUG(("%d failed midpoint\n", t->id)); 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); + MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid))); + zaptreesubs(v, t->left); + zaptreesubs(v, t->right); } } /* - - 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 complicatedReversedDissect(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 */ -complicatedReversedDissect( +crevcondissect( struct vars *const v, struct subre *const t, chr *const begin, /* beginning of relevant substring */ @@ -962,10 +758,6 @@ complicatedReversedDissect( assert(t->right != NULL && t->right->cnfa.nstates > 0); assert(t->left->flags&SHORTER); - /* - * Concatenation -- need to split the substring between parts. - */ - d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); if (ISERR()) { return v->err; @@ -975,25 +767,19 @@ complicatedReversedDissect( 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) { + freeDFA(d); + freeDFA(d2); + return REG_NOMATCH; } + MDEBUG(("tentative midpoint %ld\n", LOFF(mid))); /* * Iterate until satisfaction or failure. @@ -1005,10 +791,10 @@ complicatedReversedDissect( */ if (longest(v, d2, mid, end, NULL) == end) { - int er = complicatedDissect(v, t->left, begin, mid); + int 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. @@ -1020,7 +806,7 @@ complicatedReversedDissect( return REG_OKAY; } } - if (er != REG_OKAY && er != REG_NOMATCH) { + if (er != REG_NOMATCH) { freeDFA(d); freeDFA(d2); return er; @@ -1036,7 +822,7 @@ complicatedReversedDissect( * All possibilities exhausted. */ - MDEBUG(("%d no midpoint\n", t->retry)); + MDEBUG(("%d no midpoint\n", t->id)); freeDFA(d); freeDFA(d2); return REG_NOMATCH; @@ -1047,164 +833,484 @@ complicatedReversedDissect( * Failed to find a new one. */ - MDEBUG(("%d failed midpoint\n", t->retry)); + MDEBUG(("%d failed midpoint\n", t->id)); 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); + MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid))); + zaptreesubs(v, t->left); + zaptreesubs(v, t->right); } } /* - - complicatedBackrefDissect - determine backref subexpression matches - ^ static int complicatedBackrefDissect(struct vars *, struct subre *, chr *, chr *); + - cbrdissect - dissect match for backref node + ^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ -complicatedBackrefDissect( +cbrdissect( struct vars *const v, struct subre *const t, chr *const begin, /* beginning of relevant substring */ chr *const end) /* end of same */ { - int i, n = t->subno, min = t->min, max = t->max; - chr *paren, *p, *stop; - size_t len; + int n = t->subno, min = t->min, max = t->max; + size_t numreps; + size_t tlen; + size_t brlen; + chr *brstring; + chr *p; 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; + + /* 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; + } + if (begin == end) { + /* matches only if zero repetitions are okay */ + if (min == 0) { + MDEBUG(("cbackref matched trivially\n")); + return REG_OKAY; + } + return REG_NOMATCH; + } /* - * No room to maneuver -- retries are pointless. + * check target length to see if it could possibly be an allowed number of + * repetitions of brstring */ - if (v->mem[t->retry]) { + assert(end > begin); + tlen = end - begin; + if (tlen % brlen != 0) + return REG_NOMATCH; + numreps = tlen / brlen; + if (numreps < min || (numreps > 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; } - v->mem[t->retry] = 1; - /* - * Special-case zero-length string. - */ + 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 *const v, + struct subre *t, + chr *const begin, /* beginning of relevant substring */ + chr *const end) /* end of same */ +{ + struct dfa *d; + int er; - if (len == 0) { - if (begin == end) { - return REG_OKAY; + /* 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); + + MDEBUG(("calt n%d\n", t->id)); + + d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + NOERR(); + if (longest(v, d, begin, end, (int *) NULL) == end) { + freeDFA(d); + MDEBUG(("calt matched\n")); + er = cdissect(v, t->left, begin, end); + if (er != REG_NOMATCH) { + return er; + } } - return REG_NOMATCH; + freeDFA(d); + + t = t->right; } + 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 too-short string. + * 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. */ - - assert(end >= begin); - if ((size_t)(end - begin) < len) { - return REG_NOMATCH; + min_matches = t->min; + if (min_matches <= 0) { + if (begin == end) + return REG_OKAY; + min_matches = 1; } - stop = end - len; /* - * Count occurrences. + * 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 > t->max && t->max != DUPINF) + max_matches = t->max; + if (max_matches < min_matches) + max_matches = min_matches; + endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *)); + if (endpts == NULL) + return REG_ESPACE; + endpts[0] = begin; - i = 0; - for (p = begin; p <= stop && (i < max || max == DUPINF); p += len) { - if (v->g->compare(paren, p, len) != 0) { - break; - } - i++; + d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + if (ISERR()) { + FREE(endpts); + return v->err; } - MDEBUG(("cbackref found %d\n", i)); + MDEBUG(("citer %d\n", t->id)); /* - * And sort it out. + * 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 (p != end) { /* didn't consume all of it */ - return REG_NOMATCH; - } - if (min <= i && (i <= max || max == DUPINF)) { - return REG_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 (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 */ + freeDFA(d); + FREE(endpts); + return er; + } + + if (i > k) { + /* satisfaction */ + MDEBUG(("%d successful\n", t->id)); + freeDFA(d); + 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)); + freeDFA(d); + FREE(endpts); + return REG_NOMATCH; } /* - - complicatedAlternationDissect - determine alternative subexpression matches (w. - - complications) - ^ static int complicatedAlternationDissect(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 */ -complicatedAlternationDissect( - struct vars *const v, - struct subre *t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ +creviterdissect(struct vars * v, + struct subre * t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { - 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 */ + 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); -#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION - if (0) { - doRight: - t = t->right; - } -#endif - 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) { - goto doRight; + + /* + * 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 > t->max && t->max != DUPINF) + max_matches = t->max; + if (max_matches < min_matches) + max_matches = min_matches; + endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *)); + if (endpts == NULL) + return REG_ESPACE; + endpts[0] = begin; + + d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + 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) { - struct dfa *d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + /* 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 (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 (k >= max_matches) { + /* must try to lengthen some previous match */ + k--; + goto backtrack; + } - if (ISERR()) { - return v->err; + k++; + limit = endpts[k - 1]; + continue; } - if (longest(v, d, begin, end, NULL) != 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 */ freeDFA(d); - v->mem[t->retry] = TRIED; - goto doRight; + FREE(endpts); + return er; } - freeDFA(d); - MDEBUG(("cAlt matched\n")); - v->mem[t->retry] = TRYING; - } - er = complicatedDissect(v, t->left, begin, end); - if (er != REG_NOMATCH) { - return er; + if (i > k) { + /* satisfaction */ + MDEBUG(("%d successful\n", t->id)); + freeDFA(d); + 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; -#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION - goto doRight; -#else - doRight: - return complicatedAlternationDissect(v, t->right, begin, end); -#endif + /* all possibilities exhausted */ + MDEBUG(("%d failed\n", t->id)); + freeDFA(d); + FREE(endpts); + return REG_NOMATCH; } #include "rege_dfa.c" diff --git a/generic/regguts.h b/generic/regguts.h index 1b6abe6..e1c60ce 100644 --- a/generic/regguts.h +++ b/generic/regguts.h @@ -329,11 +329,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 */ @@ -349,10 +366,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) */ 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... */ diff --git a/tests/reg.test b/tests/reg.test index e6ce42c..647bba8 100644 --- a/tests/reg.test +++ b/tests/reg.test @@ -669,7 +669,13 @@ expectError 14.19 - {a(b)c\2} ESUBREG expectMatch 14.20 bR {a\(b*\)c\1} abbcbb abbcbb bb expectMatch 14.21 RP {^([bc])\1*$} bbb bbb b expectMatch 14.22 RP {^([bc])\1*$} ccc ccc c -knownBug expectNomatch 14.23 R {^([bc])\1*$} bcb +expectNomatch 14.23 RP {^([bc])\1*$} bcb +expectMatch 14.24 LRP {^(\w+)( \1)+$} {abc abc abc} {abc abc abc} abc { abc} +expectNomatch 14.25 LRP {^(\w+)( \1)+$} {abc abd abc} +expectNomatch 14.26 LRP {^(\w+)( \1)+$} {abc abc abd} +expectMatch 14.27 RP {^(.+)( \1)+$} {abc abc abc} {abc abc abc} abc { abc} +expectNomatch 14.28 RP {^(.+)( \1)+$} {abc abd abc} +expectNomatch 14.29 RP {^(.+)( \1)+$} {abc abc abd} doing 15 "octal escapes vs back references" @@ -796,6 +802,7 @@ expectMatch 21.31 LP "\\y(\\w+)\\y" "-- abc-" "abc" "abc" expectMatch 21.32 - a((b|c)d+)+ abacdbd acdbd bd b expectMatch 21.33 N (.*).* abc abc abc expectMatch 21.34 N (a*)* bc "" "" +expectMatch 21.35 M { TO (([a-z0-9._]+|"([^"]+|"")+")+)} {asd TO foo} { TO foo} foo o {} doing 22 "multicharacter collating elements" @@ -848,6 +855,7 @@ expectMatch 24.9 - 3z* 123zzzz456 3zzzz expectMatch 24.10 PT 3z*? 123zzzz456 3 expectMatch 24.11 - z*4 123zzzz456 zzzz4 expectMatch 24.12 PT z*?4 123zzzz456 zzzz4 +expectMatch 24.13 PT {^([^/]+?)(?:/([^/]+?))(?:/([^/]+?))?$} {foo/bar/baz} {foo/bar/baz} {foo} {bar} {baz} doing 25 "mixed quantifiers" -- cgit v0.12