From 0a6732bf275cd138134950549e2f4305e5fa5eed Mon Sep 17 00:00:00 2001 From: dgp Date: Mon, 21 Sep 2015 17:14:52 +0000 Subject: [d7ea9f9853] Contributed patch from tgl with Postgres. --- generic/regcomp.c | 16 +++++++++------- 1 file changed, 9 insertions(+), 7 deletions(-) diff --git a/generic/regcomp.c b/generic/regcomp.c index d23076b..b1c02d8 100644 --- a/generic/regcomp.c +++ b/generic/regcomp.c @@ -593,13 +593,15 @@ makesearch( break; } } + + /* + * We want to mark states as being in the list already by having non + * NULL tmp fields, but we can't just store the old slist value in tmp + * because that doesn't work for the first such state. Instead, the + * first list entry gets its own address in tmp. + */ if (b != NULL && s->tmp == NULL) { - /* - * Must be split if not already in the list (fixes bugs 505048, - * 230589, 840258, 504785). - */ - - s->tmp = slist; + s->tmp = (slist != NULL) ? slist : s; slist = s; } } @@ -620,7 +622,7 @@ makesearch( freearc(nfa, a); } } - s2 = s->tmp; + s2 = (s->tmp != s) ? s->tmp : NULL; s->tmp = NULL; /* clean up while we're at it */ } } -- cgit v0.12 From e4bb6f372f554b29e021e1ab90f875e27479f4a3 Mon Sep 17 00:00:00 2001 From: dgp Date: Mon, 21 Sep 2015 17:29:22 +0000 Subject: [a3c3508599] Fix typo that reversed test sense in prior fix for [3610026]. --- generic/regc_color.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/generic/regc_color.c b/generic/regc_color.c index 58de004..35e7904 100644 --- a/generic/regc_color.c +++ b/generic/regc_color.c @@ -259,7 +259,7 @@ newcolor( return COLORLESS; /* too many colors */ } n = cm->ncds * 2; - if (n < MAX_COLOR + 1) { + if (n > MAX_COLOR + 1) { n = MAX_COLOR + 1; } if (cm->cd == cm->cdspace) { -- cgit v0.12 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 From 066e9abdc308995186dbc4d9bbc2fedc07674296 Mon Sep 17 00:00:00 2001 From: dgp Date: Mon, 21 Sep 2015 19:25:20 +0000 Subject: [187d7f499b] Sync the regexp engine to the Postgres version. --- generic/regc_color.c | 13 +++--- generic/regc_cvec.c | 1 + generic/regc_lex.c | 18 -------- generic/regc_nfa.c | 36 ++++++++-------- generic/regcomp.c | 75 ++++++++++++++++++++------------- generic/rege_dfa.c | 29 ++++++------- generic/regerror.c | 4 +- generic/regexec.c | 115 ++++++++++++++++++++++++++++----------------------- generic/regguts.h | 38 +++++++++++++---- 9 files changed, 182 insertions(+), 147 deletions(-) diff --git a/generic/regc_color.c b/generic/regc_color.c index 2e167fe..92e0aad 100644 --- a/generic/regc_color.c +++ b/generic/regc_color.c @@ -777,18 +777,19 @@ dumpcolors( } /* - * It's hard to do this more efficiently. + * Unfortunately, it's hard to do this next bit more efficiently. + * + * Spencer's original coding has the loop iterating from CHR_MIN + * to CHR_MAX, but that's utterly unusable for 32-bit chr, or + * even 16-bit. For debugging purposes it seems fine to print + * only chr codes up to 1000 or so. */ - for (c=CHR_MIN ; cnchrs < cv->chrspace); cv->chrs[cv->nchrs++] = (chr)c; } diff --git a/generic/regc_lex.c b/generic/regc_lex.c index 132e757..16e3ae9 100644 --- a/generic/regc_lex.c +++ b/generic/regc_lex.c @@ -1139,24 +1139,6 @@ newline(void) } /* - - ch - return the chr sequence for regc_locale.c's fake collating element ch - * This helps confine use of CHR to this source file. Beware that the caller - * knows how long the sequence is. - ^ #ifdef REG_DEBUG - ^ static const chr *ch(NOPARMS); - ^ #endif - */ -#ifdef REG_DEBUG -static const chr * -ch(void) -{ - static const chr chstr[] = { CHR('c'), CHR('h'), CHR('\0') }; - - return chstr; -} -#endif - -/* - chrnamed - return the chr known by a given (chr string) name * The code is a bit clumsy, but this routine gets only such specialized * use that it hardly matters. diff --git a/generic/regc_nfa.c b/generic/regc_nfa.c index 9361d34..1fad85f 100644 --- a/generic/regc_nfa.c +++ b/generic/regc_nfa.c @@ -1652,13 +1652,16 @@ compact( narcs = 0; for (s = nfa->states; s != NULL; s = s->next) { nstates++; - narcs += 1 + s->nouts + 1; - /* 1 as a fake for flags, nouts for arcs, 1 as endmarker */ + narcs += s->nouts + 1; /* need one extra for endmarker */ } + cnfa->stflags = (char *) MALLOC(nstates * sizeof(char)); cnfa->states = (struct carc **) MALLOC(nstates * sizeof(struct carc *)); cnfa->arcs = (struct carc *) MALLOC(narcs * sizeof(struct carc)); - if (cnfa->states == NULL || cnfa->arcs == NULL) { + if (cnfa->stflags == NULL || cnfa->states == NULL || cnfa->arcs == NULL) { + if (cnfa->stflags != NULL) { + FREE(cnfa->stflags); + } if (cnfa->states != NULL) { FREE(cnfa->states); } @@ -1681,9 +1684,8 @@ compact( ca = cnfa->arcs; for (s = nfa->states; s != NULL; s = s->next) { assert((size_t) s->no < nstates); + cnfa->stflags[s->no] = 0; cnfa->states[s->no] = ca; - ca->co = 0; /* clear and skip flags "arc" */ - ca++; first = ca; for (a = s->outs; a != NULL; a = a->outchain) { switch (a->type) { @@ -1717,9 +1719,9 @@ compact( */ for (a = nfa->pre->outs; a != NULL; a = a->outchain) { - cnfa->states[a->to->no]->co = 1; + cnfa->stflags[a->to->no] = CNFA_NOPROGRESS; } - cnfa->states[nfa->pre->no]->co = 1; + cnfa->stflags[nfa->pre->no] = CNFA_NOPROGRESS; } /* @@ -1763,6 +1765,7 @@ freecnfa( { assert(cnfa->nstates != 0); /* not empty already */ cnfa->nstates = 0; + FREE(cnfa->stflags); FREE(cnfa->states); FREE(cnfa->arcs); } @@ -1985,7 +1988,7 @@ dumpcnfa( } fprintf(f, "\n"); for (st = 0; st < cnfa->nstates; st++) { - dumpcstate(st, cnfa->states[st], cnfa, f); + dumpcstate(st, cnfa, f); } fflush(f); #endif @@ -1998,25 +2001,24 @@ dumpcnfa( /* - dumpcstate - dump a compacted-NFA state in human-readable form - ^ static void dumpcstate(int, struct carc *, struct cnfa *, FILE *); + ^ static void dumpcstate(int, struct cnfa *, FILE *); */ static void dumpcstate( int st, - struct carc *ca, struct cnfa *cnfa, FILE *f) { - int i; + struct carc *ca; int pos; - fprintf(f, "%d%s", st, (ca[0].co) ? ":" : "."); + fprintf(f, "%d%s", st, (cnfa->stflags[st] & CNFA_NOPROGRESS) ? ":" : "."); pos = 1; - for (i = 1; ca[i].co != COLORLESS; i++) { - if (ca[i].co < cnfa->ncolors) { - fprintf(f, "\t[%ld]->%d", (long) ca[i].co, ca[i].to); + for (ca = cnfa->states[st]; ca->co != COLORLESS; ca++) { + if (ca->co < cnfa->ncolors) { + fprintf(f, "\t[%ld]->%d", (long) ca->co, ca->to); } else { - fprintf(f, "\t:%ld:->%d", (long) ca[i].co-cnfa->ncolors,ca[i].to); + fprintf(f, "\t:%ld:->%d", (long) (ca->co - cnfa->ncolors), ca->to); } if (pos == 5) { fprintf(f, "\n"); @@ -2025,7 +2027,7 @@ dumpcstate( pos++; } } - if (i == 1 || pos != 1) { + if (ca == cnfa->states[st] || pos != 1) { fprintf(f, "\n"); } fflush(f); diff --git a/generic/regcomp.c b/generic/regcomp.c index b8a5a87..11a389a 100644 --- a/generic/regcomp.c +++ b/generic/regcomp.c @@ -83,9 +83,6 @@ static int lexdigits(struct vars *, int, int, int); static int brenext(struct vars *, pchr); static void skip(struct vars *); static chr newline(NOPARMS); -#ifdef REG_DEBUG -static const chr *ch(NOPARMS); -#endif static chr chrnamed(struct vars *, const chr *, const chr *, pchr); /* === regc_color.c === */ static void initcm(struct vars *, struct colormap *); @@ -165,7 +162,7 @@ static void dumparc(struct arc *, struct state *, FILE *); #endif static void dumpcnfa(struct cnfa *, FILE *); #ifdef REG_DEBUG -static void dumpcstate(int, struct carc *, struct cnfa *, FILE *); +static void dumpcstate(int, struct cnfa *, FILE *); #endif /* === regc_cvec.c === */ static struct cvec *clearcvec(struct cvec *); @@ -210,7 +207,7 @@ struct vars { struct subre *tree; /* subexpression tree */ struct subre *treechain; /* all tree nodes allocated */ struct subre *treefree; /* any free tree nodes */ - int ntree; /* number of tree nodes */ + int ntree; /* number of tree nodes, plus one */ struct cvec *cv; /* interface cvec */ struct cvec *cv2; /* utility cvec */ struct subre *lacons; /* lookahead-constraint vector */ @@ -223,13 +220,13 @@ struct vars { #define EAT(t) (SEE(t) && next(v)) /* if next is this, swallow it */ #define VISERR(vv) ((vv)->err != 0)/* have we seen an error yet? */ #define ISERR() VISERR(v) -#define VERR(vv,e) \ - ((vv)->nexttype = EOS, ((vv)->err) ? (vv)->err : ((vv)->err = (e))) +#define VERR(vv,e) ((vv)->nexttype = EOS, \ + (vv)->err = ((vv)->err ? (vv)->err : (e))) #define ERR(e) VERR(v, e) /* record an error */ #define NOERR() {if (ISERR()) return;} /* if error seen, return */ #define NOERRN() {if (ISERR()) return NULL;} /* NOERR with retval */ #define NOERRZ() {if (ISERR()) return 0;} /* NOERR with retval */ -#define INSIST(c, e) ((c) ? 0 : ERR(e)) /* if condition false, error */ +#define INSIST(c, e) do { if (!(c)) ERR(e); } while (0) /* error if c false */ #define NOTE(b) (v->re->re_info |= (b)) /* note visible condition */ #define EMPTYARC(x, y) newarc(v->nfa, EMPTY, 0, x, y) @@ -258,12 +255,14 @@ struct vars { ((a)->type == PLAIN || (a)->type == AHEAD || (a)->type == BEHIND) /* static function list */ -static struct fns functions = { +static const struct fns functions = { rfree, /* regfree insides */ }; /* - compile - compile regular expression + * Note: on failure, no resources remain allocated, so regfree() + * need not be applied to re. ^ int compile(regex_t *, const chr *, size_t, int); */ int @@ -1788,7 +1787,8 @@ freesrnode( } sr->flags = 0; - if (v != NULL) { + if (v != NULL && v->treechain != NULL) { + /* we're still parsing, maybe we can reuse the subre */ sr->left = v->treefree; v->treefree = sr; } else { @@ -1841,6 +1841,19 @@ numst( /* - markst - mark tree nodes as INUSE + * Note: this is a great deal more subtle than it looks. During initial + * parsing of a regex, all subres are linked into the treechain list; + * discarded ones are also linked into the treefree list for possible reuse. + * After we are done creating all subres required for a regex, we run markst() + * then cleanst(), which results in discarding all subres not reachable from + * v->tree. We then clear v->treechain, indicating that subres must be found + * by descending from v->tree. This changes the behavior of freesubre(): it + * will henceforth FREE() unwanted subres rather than sticking them into the + * treefree list. (Doing that any earlier would result in dangling links in + * the treechain list.) This all means that freev() will clean up correctly + * if invoked before or after markst()+cleanst(); but it would not work if + * called partway through this state conversion, so we mustn't error out + * in or between these two functions. ^ static void markst(struct subre *); */ static void @@ -1947,24 +1960,26 @@ newlacon( struct state *end, int pos) { - struct subre *sub; int n; + struct subre *newlacons; + struct subre *sub; if (v->nlacons == 0) { - v->lacons = (struct subre *) MALLOC(2 * sizeof(struct subre)); n = 1; /* skip 0th */ - v->nlacons = 2; + newlacons = (struct subre *) MALLOC(2 * sizeof(struct subre)); } else { - v->lacons = (struct subre *) REALLOC(v->lacons, - (v->nlacons+1)*sizeof(struct subre)); - n = v->nlacons++; + n = v->nlacons; + newlacons = (struct subre *) REALLOC(v->lacons, + (n + 1) * sizeof(struct subre)); } - if (v->lacons == NULL) { + if (newlacons == NULL) { ERR(REG_ESPACE); return 0; } + v->lacons = newlacons; + v->nlacons = n + 1; sub = &v->lacons[n]; sub->begin = begin; sub->end = end; @@ -2012,18 +2027,20 @@ rfree( g = (struct guts *) re->re_guts; re->re_guts = NULL; re->re_fns = NULL; - g->magic = 0; - freecm(&g->cmap); - if (g->tree != NULL) { - freesubre(NULL, g->tree); - } - if (g->lacons != NULL) { - freelacons(g->lacons, g->nlacons); - } - if (!NULLCNFA(g->search)) { - freecnfa(&g->search); + if (g != NULL) { + g->magic = 0; + freecm(&g->cmap); + if (g->tree != NULL) { + freesubre(NULL, g->tree); + } + if (g->lacons != NULL) { + freelacons(g->lacons, g->nlacons); + } + if (!NULLCNFA(g->search)) { + freecnfa(&g->search); + } + FREE(g); } - FREE(g); } /* @@ -2055,7 +2072,7 @@ dump( fprintf(f, "\n\n\n========= DUMP ==========\n"); fprintf(f, "nsub %d, info 0%lo, csize %d, ntree %d\n", - re->re_nsub, re->re_info, re->re_csize, g->ntree); + (int) re->re_nsub, re->re_info, re->re_csize, g->ntree); dumpcolors(&g->cmap, f); if (!NULLCNFA(g->search)) { diff --git a/generic/rege_dfa.c b/generic/rege_dfa.c index 920ea6c..e5f22c4 100644 --- a/generic/rege_dfa.c +++ b/generic/rege_dfa.c @@ -84,7 +84,7 @@ longest( if (v->eflags®_FTRACE) { while (cp < realstop) { - FDEBUG(("+++ at c%d +++\n", css - d->ssets)); + FDEBUG(("+++ at c%d +++\n", (int) (css - d->ssets))); co = GETCOLOR(cm, *cp); FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co)); ss = css->outs[co]; @@ -118,7 +118,7 @@ longest( * Shutdown. */ - FDEBUG(("+++ shutdown at c%d +++\n", css - d->ssets)); + FDEBUG(("+++ shutdown at c%d +++\n", (int) (css - d->ssets))); if (cp == v->stop && stop == v->stop) { if (hitstopp != NULL) { *hitstopp = 1; @@ -213,7 +213,7 @@ shortest( if (v->eflags®_FTRACE) { while (cp < realmax) { - FDEBUG(("--- at c%d ---\n", css - d->ssets)); + FDEBUG(("--- at c%d ---\n", (int) (css - d->ssets))); co = GETCOLOR(cm, *cp); FDEBUG(("char %c, color %ld\n", (char)*cp, (long)co)); ss = css->outs[co]; @@ -516,14 +516,14 @@ miss( gotState = 0; for (i = 0; i < d->nstates; i++) { if (ISBSET(css->states, i)) { - for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++) { + for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) { if (ca->co == co) { BSET(d->work, ca->to); gotState = 1; if (ca->to == cnfa->post) { isPost = 1; } - if (!cnfa->states[ca->to]->co) { + if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS)) { noProgress = 0; } FDEBUG(("%d -> %d\n", i, ca->to)); @@ -537,8 +537,8 @@ miss( 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) { + for (ca = cnfa->states[i]; ca->co != COLORLESS; ca++) { + if (ca->co < cnfa->ncolors) { continue; /* NOTE CONTINUE */ } sawLAConstraints = 1; @@ -553,7 +553,7 @@ miss( if (ca->to == cnfa->post) { isPost = 1; } - if (!cnfa->states[ca->to]->co) { + if (!(cnfa->stflags[ca->to] & CNFA_NOPROGRESS)) { noProgress = 0; } FDEBUG(("%d :> %d\n", i, ca->to)); @@ -572,7 +572,7 @@ miss( for (p = d->ssets, i = d->nssused; i > 0; p++, i--) { if (HIT(h, d->work, p, d->wordsper)) { - FDEBUG(("cached c%d\n", p - d->ssets)); + FDEBUG(("cached c%d\n", (int) (p - d->ssets))); break; /* NOTE BREAK OUT */ } } @@ -594,7 +594,8 @@ miss( } if (!sawLAConstraints) { /* lookahead conds. always cache miss */ - FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets)); + FDEBUG(("c%d[%d]->c%d\n", + (int) (css - d->ssets), co, (int) (p - d->ssets))); css->outs[co] = p; css->inchain[co] = p->ins; p->ins.ss = css; @@ -663,7 +664,7 @@ getVacantSS( ap = ss->ins; while ((p = ap.ss) != NULL) { co = ap.co; - FDEBUG(("zapping c%d's %ld outarc\n", p - d->ssets, (long)co)); + FDEBUG(("zapping c%d's %ld outarc\n", (int) (p - d->ssets), (long)co)); p->outs[co] = NULL; ap = p->inchain[co]; p->inchain[co].ss = NULL; /* paranoia */ @@ -680,7 +681,7 @@ getVacantSS( if (p == NULL) { continue; /* NOTE CONTINUE */ } - FDEBUG(("del outarc %d from c%d's in chn\n", i, p - d->ssets)); + FDEBUG(("del outarc %d from c%d's in chn\n", i, (int) (p - d->ssets))); if (p->ins.ss == ss && p->ins.co == i) { p->ins = ss->inchain[i]; } else { @@ -772,7 +773,7 @@ pickNextSS( if ((ss->lastseen == NULL || ss->lastseen < ancient) && !(ss->flags&LOCKED)) { d->search = ss + 1; - FDEBUG(("replacing c%d\n", ss - d->ssets)); + FDEBUG(("replacing c%d\n", (int) (ss - d->ssets))); return ss; } } @@ -780,7 +781,7 @@ pickNextSS( if ((ss->lastseen == NULL || ss->lastseen < ancient) && !(ss->flags&LOCKED)) { d->search = ss + 1; - FDEBUG(("replacing c%d\n", ss - d->ssets)); + FDEBUG(("replacing c%d\n", (int) (ss - d->ssets))); return ss; } } diff --git a/generic/regerror.c b/generic/regerror.c index a1a0163..49d93ed 100644 --- a/generic/regerror.c +++ b/generic/regerror.c @@ -41,7 +41,7 @@ static const char unk[] = "*** unknown regex error code 0x%x ***"; * Struct to map among codes, code names, and explanations. */ -static struct rerr { +static const struct rerr { int code; const char *name; const char *explain; @@ -62,7 +62,7 @@ regerror( char *errbuf, /* Result buffer (unless errbuf_size==0) */ size_t errbuf_size) /* Available space in errbuf, can be 0 */ { - struct rerr *r; + const struct rerr *r; const char *msg; char convbuf[sizeof(unk)+50]; /* 50 = plenty for int */ size_t len; diff --git a/generic/regexec.c b/generic/regexec.c index e502ca5..3030913 100644 --- a/generic/regexec.c +++ b/generic/regexec.c @@ -107,12 +107,13 @@ struct vars { chr *start; /* start of string */ chr *stop; /* just past end of string */ int err; /* error code if any (0 none) */ + struct dfa **subdfas; /* per-subre DFAs */ struct smalldfa dfa1; struct smalldfa dfa2; }; #define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */ #define ISERR() VISERR(v) -#define VERR(vv,e) (((vv)->err) ? (vv)->err : ((vv)->err = (e))) +#define VERR(vv,e) ((vv)->err = ((vv)->err ? (vv)->err : (e))) #define ERR(e) VERR(v, e) /* record an error */ #define NOERR() {if (ISERR()) return v->err;} /* if error seen, return it */ #define OFF(p) ((p) - v->start) @@ -125,6 +126,7 @@ 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 struct dfa *getsubdfa(struct vars *, struct subre *); static int simpleFind(struct vars *const, struct cnfa *const, struct colormap *const); static int complicatedFind(struct vars *const, struct cnfa *const, struct colormap *const); static int complicatedFindLoop(struct vars *const, struct cnfa *const, struct colormap *const, struct dfa *const, struct dfa *const, chr **const); @@ -171,8 +173,11 @@ exec( AllocVars(v); int st, backref; size_t n; + size_t i; #define LOCALMAT 20 regmatch_t mat[LOCALMAT]; +#define LOCALDFAS 40 + struct dfa *subdfas[LOCALDFAS]; /* * Sanity checks. @@ -230,6 +235,20 @@ exec( v->start = (chr *)string; v->stop = (chr *)string + len; v->err = 0; + assert(v->g->ntree >= 0); + n = (size_t) v->g->ntree; + if (n <= LOCALDFAS) + v->subdfas = subdfas; + else + v->subdfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *)); + if (v->subdfas == NULL) { + if (v->pmatch != pmatch && v->pmatch != mat) + FREE(v->pmatch); + FreeVars(v); + return REG_ESPACE; + } + for (i = 0; i < n; i++) + v->subdfas[i] = NULL; /* * Do it. @@ -259,11 +278,35 @@ exec( if (v->pmatch != pmatch && v->pmatch != mat) { FREE(v->pmatch); } + n = (size_t) v->g->ntree; + for (i = 0; i < n; i++) { + if (v->subdfas[i] != NULL) + freeDFA(v->subdfas[i]); + } + if (v->subdfas != subdfas) + FREE(v->subdfas); FreeVars(v); return st; } /* + - getsubdfa - create or re-fetch the DFA for a subre node + * We only need to create the DFA once per overall regex execution. + * The DFA will be freed by the cleanup step in exec(). + */ +static struct dfa * +getsubdfa(struct vars * v, + struct subre * t) +{ + if (v->subdfas[t->id] == NULL) { + v->subdfas[t->id] = newDFA(v, &t->cnfa, &v->g->cmap, DOMALLOC); + if (ISERR()) + return NULL; + } + return v->subdfas[t->id]; +} + +/* - simpleFind - find a match for the main NFA (no-complications case) ^ static int simpleFind(struct vars *, struct cnfa *, struct colormap *); */ @@ -327,7 +370,10 @@ simpleFind( } else { end = longest(v, d, begin, v->stop, &hitend); } - NOERR(); + if (ISERR()) { + freeDFA(d); + return v->err; + } if (hitend && cold == NULL) { cold = begin; } @@ -470,6 +516,7 @@ complicatedFindLoop( } if (er != REG_NOMATCH) { ERR(er); + *coldp = cold; return er; } if ((shorter) ? end == estop : end == begin) { @@ -636,7 +683,7 @@ cdissect( } /* - - ccondissect - concatenation subexpression matches (with complications) + - ccondissect - dissect match for concatenation node ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *); */ static int /* regexec return code */ @@ -654,15 +701,11 @@ ccondissect( assert(t->right != NULL && t->right->cnfa.nstates > 0); assert(!(t->left->flags & SHORTER)); - d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); - if (ISERR()) { - return v->err; - } - d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC); - if (ISERR()) { - freeDFA(d); - return v->err; - } + d = getsubdfa(v, t->left); + NOERR(); + d2 = getsubdfa(v, t->right); + NOERR(); + MDEBUG(("cConcat %d\n", t->id)); /* @@ -670,8 +713,6 @@ ccondissect( */ 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))); @@ -696,14 +737,10 @@ ccondissect( */ MDEBUG(("successful\n")); - freeDFA(d); - freeDFA(d2); return REG_OKAY; } } if (er != REG_NOMATCH) { - freeDFA(d); - freeDFA(d2); return er; } } @@ -718,8 +755,6 @@ ccondissect( */ MDEBUG(("%d no midpoint\n", t->id)); - freeDFA(d); - freeDFA(d2); return REG_NOMATCH; } mid = longest(v, d, begin, mid-1, NULL); @@ -729,8 +764,6 @@ ccondissect( */ MDEBUG(("%d failed midpoint\n", t->id)); - freeDFA(d); - freeDFA(d2); return REG_NOMATCH; } MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid))); @@ -758,15 +791,11 @@ crevcondissect( assert(t->right != NULL && t->right->cnfa.nstates > 0); assert(t->left->flags&SHORTER); - d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); - if (ISERR()) { - return v->err; - } - d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC); - if (ISERR()) { - freeDFA(d); - return v->err; - } + d = getsubdfa(v, t->left); + NOERR(); + d2 = getsubdfa(v, t->right); + NOERR(); + MDEBUG(("crevcon %d\n", t->id)); /* @@ -775,8 +804,6 @@ crevcondissect( 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))); @@ -801,14 +828,10 @@ crevcondissect( */ MDEBUG(("successful\n")); - freeDFA(d); - freeDFA(d2); return REG_OKAY; } } if (er != REG_NOMATCH) { - freeDFA(d); - freeDFA(d2); return er; } } @@ -823,8 +846,6 @@ crevcondissect( */ MDEBUG(("%d no midpoint\n", t->id)); - freeDFA(d); - freeDFA(d2); return REG_NOMATCH; } mid = shortest(v, d, begin, mid+1, end, NULL, NULL); @@ -834,8 +855,6 @@ crevcondissect( */ MDEBUG(("%d failed midpoint\n", t->id)); - freeDFA(d); - freeDFA(d2); return REG_NOMATCH; } MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid))); @@ -943,17 +962,15 @@ caltdissect( MDEBUG(("calt n%d\n", t->id)); - d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + d = getsubdfa(v, t->left); 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; } } - freeDFA(d); t = t->right; } @@ -1017,7 +1034,7 @@ citerdissect(struct vars * v, return REG_ESPACE; endpts[0] = begin; - d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + d = getsubdfa(v, t->left); if (ISERR()) { FREE(endpts); return v->err; @@ -1094,7 +1111,6 @@ citerdissect(struct vars * v, if (er == REG_NOMATCH) break; /* oops, something failed */ - freeDFA(d); FREE(endpts); return er; } @@ -1102,7 +1118,6 @@ citerdissect(struct vars * v, if (i > k) { /* satisfaction */ MDEBUG(("%d successful\n", t->id)); - freeDFA(d); FREE(endpts); return REG_OKAY; } @@ -1132,7 +1147,6 @@ citerdissect(struct vars * v, /* all possibilities exhausted */ MDEBUG(("%d failed\n", t->id)); - freeDFA(d); FREE(endpts); return REG_NOMATCH; } @@ -1193,7 +1207,7 @@ creviterdissect(struct vars * v, return REG_ESPACE; endpts[0] = begin; - d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC); + d = getsubdfa(v, t->left); if (ISERR()) { FREE(endpts); return v->err; @@ -1276,7 +1290,6 @@ creviterdissect(struct vars * v, if (er == REG_NOMATCH) break; /* oops, something failed */ - freeDFA(d); FREE(endpts); return er; } @@ -1284,7 +1297,6 @@ creviterdissect(struct vars * v, if (i > k) { /* satisfaction */ MDEBUG(("%d successful\n", t->id)); - freeDFA(d); FREE(endpts); return REG_OKAY; } @@ -1308,7 +1320,6 @@ creviterdissect(struct vars * v, /* all possibilities exhausted */ MDEBUG(("%d failed\n", t->id)); - freeDFA(d); FREE(endpts); return REG_NOMATCH; } diff --git a/generic/regguts.h b/generic/regguts.h index e1c60ce..de760b0 100644 --- a/generic/regguts.h +++ b/generic/regguts.h @@ -186,7 +186,14 @@ struct colordesc { union tree *block; /* block of solid color, if any */ }; -/* the color map itself */ +/* + * The color map itself + * + * Much of the data in the colormap struct is only used at compile time. + * However, the bulk of the space usage is in the "tree" structure, so it's + * not clear that there's much point in converting the rest to a more compact + * form when compilation is finished. + */ struct colormap { int magic; #define CMMAGIC 0x876 @@ -242,15 +249,14 @@ struct cvec { struct state; struct arc { - int type; -#define ARCFREE '\0' + int type; /* 0 if free, else an NFA arc type code */ color co; struct state *from; /* where it's from (and contained within) */ struct state *to; /* where it's to */ - struct arc *outchain; /* *from's outs chain or free chain */ + struct arc *outchain; /* link in *from's outs chain or free chain */ #define freechain outchain - struct arc *inchain; /* *to's ins chain */ - struct arc *colorchain; /* color's arc chain */ + struct arc *inchain; /* link in *to's ins chain */ + struct arc *colorchain; /* link in color's arc chain */ struct arc *colorchainRev; /* back-link in color's arc chain */ }; @@ -297,11 +303,22 @@ struct nfa { /* * definitions for compacted NFA + * + * The main space savings in a compacted NFA is from making the arcs as small + * as possible. We store only the transition color and next-state number for + * each arc. The list of out arcs for each state is an array beginning at + * cnfa.states[statenumber], and terminated by a dummy carc struct with + * co == COLORLESS. + * + * The non-dummy carc structs are of two types: plain arcs and LACON arcs. + * Plain arcs just store the transition color number as "co". LACON arcs + * store the lookahead constraint number plus cnfa.ncolors as "co". LACON + * arcs can be distinguished from plain by testing for co >= cnfa.ncolors. */ struct carc { color co; /* COLORLESS is list terminator */ - int to; /* state number */ + int to; /* next-state number */ }; struct cnfa { @@ -313,7 +330,10 @@ struct cnfa { int post; /* teardown state number */ color bos[2]; /* colors, if any, assigned to BOS and BOL */ color eos[2]; /* colors, if any, assigned to EOS and EOL */ + char *stflags; /* vector of per-state flags bytes */ +#define CNFA_NOPROGRESS 01 /* flag bit for a no-progress state */ struct carc **states; /* vector of pointers to outarc lists */ + /* states[n] are pointers into a single malloc'd array of arcs */ struct carc *arcs; /* the area for the lists */ }; #define ZAPCNFA(cnfa) ((cnfa).nstates = 0) @@ -366,7 +386,7 @@ 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 id; /* ID of subre (1..ntree) */ + short id; /* ID of subre (1..ntree-1) */ int subno; /* subexpression number (for 'b' and '(') */ short min; /* min repetitions for iteration or backref */ short max; /* max repetitions for iteration or backref */ @@ -399,7 +419,7 @@ struct guts { size_t nsub; /* copy of re_nsub */ struct subre *tree; struct cnfa search; /* for fast preliminary search */ - int ntree; + int ntree; /* number of subre's, plus one */ struct colormap cmap; int FUNCPTR(compare, (const chr *, const chr *, size_t)); struct subre *lacons; /* lookahead-constraint vector */ -- cgit v0.12 From bd3fec22b475c3e3e0420a4db76adc41b1cdd8bf Mon Sep 17 00:00:00 2001 From: "jan.nijtmans" Date: Tue, 22 Sep 2015 11:32:11 +0000 Subject: Eliminate compiler warnings for MSVC --- generic/regexec.c | 54 +++++++++++++++++++++++++++--------------------------- 1 file changed, 27 insertions(+), 27 deletions(-) diff --git a/generic/regexec.c b/generic/regexec.c index 3030913..6d12827 100644 --- a/generic/regexec.c +++ b/generic/regexec.c @@ -622,10 +622,10 @@ subset( */ static int /* regexec return code */ cdissect( - struct vars *const v, - struct subre *const t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { int er; @@ -688,10 +688,10 @@ cdissect( */ static int /* regexec return code */ ccondissect( - struct vars *const v, - struct subre *const t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { struct dfa *d, *d2; chr *mid; @@ -778,10 +778,10 @@ ccondissect( */ static int /* regexec return code */ crevcondissect( - struct vars *const v, - struct subre *const t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { struct dfa *d, *d2; chr *mid; @@ -869,10 +869,10 @@ crevcondissect( */ static int /* regexec return code */ cbrdissect( - struct vars *const v, - struct subre *const t, - chr *const begin, /* beginning of relevant substring */ - chr *const end) /* end of same */ + struct vars *v, + struct subre *t, + chr *begin, /* beginning of relevant substring */ + chr *end) /* end of same */ { int n = t->subno, min = t->min, max = t->max; size_t numreps; @@ -926,7 +926,7 @@ cbrdissect( if (tlen % brlen != 0) return REG_NOMATCH; numreps = tlen / brlen; - if (numreps < min || (numreps > max && max != DUPINF)) + if (numreps < (size_t)min || (numreps > (size_t)max && max != DUPINF)) return REG_NOMATCH; /* okay, compare the actual string contents */ @@ -947,10 +947,10 @@ cbrdissect( */ static int /* regexec return code */ caltdissect( - 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 */ { struct dfa *d; int er; @@ -1025,9 +1025,9 @@ citerdissect(struct vars * v, * sub-match endpoints in endpts[1..max_matches]. */ max_matches = end - begin; - if (max_matches > t->max && t->max != DUPINF) + if (max_matches > (size_t)t->max && t->max != DUPINF) max_matches = t->max; - if (max_matches < min_matches) + if (max_matches < (size_t)min_matches) max_matches = min_matches; endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *)); if (endpts == NULL) @@ -1074,7 +1074,7 @@ citerdissect(struct vars * v, if (endpts[k] != end) { /* haven't reached end yet, try another iteration if allowed */ - if (k >= max_matches) { + if ((size_t)k >= max_matches) { /* must try to shorten some previous match */ k--; goto backtrack; @@ -1198,9 +1198,9 @@ creviterdissect(struct vars * v, * sub-match endpoints in endpts[1..max_matches]. */ max_matches = end - begin; - if (max_matches > t->max && t->max != DUPINF) + if (max_matches > (size_t)t->max && t->max != DUPINF) max_matches = t->max; - if (max_matches < min_matches) + if (max_matches < (size_t)min_matches) max_matches = min_matches; endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *)); if (endpts == NULL) @@ -1238,7 +1238,7 @@ creviterdissect(struct vars * v, limit++; /* if this is the last allowed sub-match, it must reach to the end */ - if (k >= max_matches) + if ((size_t)k >= max_matches) limit = end; /* try to find an endpoint for the k'th sub-match */ @@ -1258,7 +1258,7 @@ creviterdissect(struct vars * v, if (endpts[k] != end) { /* haven't reached end yet, try another iteration if allowed */ - if (k >= max_matches) { + if ((size_t)k >= max_matches) { /* must try to lengthen some previous match */ k--; goto backtrack; -- cgit v0.12 From cb1f5ad4901220060bc319970cf3434734b3a1aa Mon Sep 17 00:00:00 2001 From: "jan.nijtmans" Date: Tue, 22 Sep 2015 15:24:11 +0000 Subject: Decorate Tcl_Panic and Tcl_PanicVA with the noreturn option, alowing further optimizations by the C-compiler. --- generic/tcl.decls | 6 +++--- generic/tcl.h | 8 ++++++++ generic/tclDecls.h | 13 +++++++------ generic/tclPanic.c | 8 ++++---- tools/genStubs.tcl | 2 ++ win/tclWinError.c | 2 +- win/tclWinFile.c | 4 ++-- 7 files changed, 27 insertions(+), 16 deletions(-) diff --git a/generic/tcl.decls b/generic/tcl.decls index 1829249..a5cd24d 100644 --- a/generic/tcl.decls +++ b/generic/tcl.decls @@ -37,7 +37,7 @@ declare 1 { void *clientDataPtr) } declare 2 { - void Tcl_Panic(const char *format, ...) + TCL_NORETURN void Tcl_Panic(const char *format, ...) } declare 3 { char *Tcl_Alloc(unsigned int size) @@ -815,7 +815,7 @@ declare 229 { void Tcl_SetMaxBlockTime(const Tcl_Time *timePtr) } declare 230 { - void Tcl_SetPanicProc(Tcl_PanicProc *panicProc) + void Tcl_SetPanicProc(TCL_NORETURN1 Tcl_PanicProc *panicProc) } declare 231 { int Tcl_SetRecursionLimit(Tcl_Interp *interp, int depth) @@ -986,7 +986,7 @@ declare 277 { Tcl_Pid Tcl_WaitPid(Tcl_Pid pid, int *statPtr, int options) } declare 278 { - void Tcl_PanicVA(const char *format, va_list argList) + TCL_NORETURN void Tcl_PanicVA(const char *format, va_list argList) } declare 279 { void Tcl_GetVersion(int *major, int *minor, int *patchLevel, int *type) diff --git a/generic/tcl.h b/generic/tcl.h index 1f7b5cb..13e2303 100644 --- a/generic/tcl.h +++ b/generic/tcl.h @@ -143,8 +143,16 @@ extern "C" { #endif #if defined(__GNUC__) && (__GNUC__ > 2) # define TCL_FORMAT_PRINTF(a,b) __attribute__ ((__format__ (__printf__, a, b))) +# define TCL_NORETURN __attribute__ ((noreturn)) +# define TCL_NORETURN1 __attribute__ ((noreturn)) #else # define TCL_FORMAT_PRINTF(a,b) +# if defined(_MSC_VER) && (_MSC_VER >= 1310) +# define TCL_NORETURN _declspec(noreturn) +# else +# define TCL_NORETURN /* nothing */ +# endif +# define TCL_NORETURN1 /* nothing */ #endif /* diff --git a/generic/tclDecls.h b/generic/tclDecls.h index 91c0add..996129d 100644 --- a/generic/tclDecls.h +++ b/generic/tclDecls.h @@ -48,7 +48,7 @@ EXTERN CONST84_RETURN char * Tcl_PkgRequireEx(Tcl_Interp *interp, const char *name, const char *version, int exact, void *clientDataPtr); /* 2 */ -EXTERN void Tcl_Panic(const char *format, ...) TCL_FORMAT_PRINTF(1, 2); +EXTERN TCL_NORETURN void Tcl_Panic(const char *format, ...) TCL_FORMAT_PRINTF(1, 2); /* 3 */ EXTERN char * Tcl_Alloc(unsigned int size); /* 4 */ @@ -686,7 +686,8 @@ EXTERN void Tcl_SetErrorCode(Tcl_Interp *interp, ...); /* 229 */ EXTERN void Tcl_SetMaxBlockTime(const Tcl_Time *timePtr); /* 230 */ -EXTERN void Tcl_SetPanicProc(Tcl_PanicProc *panicProc); +EXTERN void Tcl_SetPanicProc( + TCL_NORETURN1 Tcl_PanicProc *panicProc); /* 231 */ EXTERN int Tcl_SetRecursionLimit(Tcl_Interp *interp, int depth); /* 232 */ @@ -835,7 +836,7 @@ EXTERN int Tcl_VarEvalVA(Tcl_Interp *interp, va_list argList); /* 277 */ EXTERN Tcl_Pid Tcl_WaitPid(Tcl_Pid pid, int *statPtr, int options); /* 278 */ -EXTERN void Tcl_PanicVA(const char *format, va_list argList); +EXTERN TCL_NORETURN void Tcl_PanicVA(const char *format, va_list argList); /* 279 */ EXTERN void Tcl_GetVersion(int *major, int *minor, int *patchLevel, int *type); @@ -1828,7 +1829,7 @@ typedef struct TclStubs { int (*tcl_PkgProvideEx) (Tcl_Interp *interp, const char *name, const char *version, const void *clientData); /* 0 */ CONST84_RETURN char * (*tcl_PkgRequireEx) (Tcl_Interp *interp, const char *name, const char *version, int exact, void *clientDataPtr); /* 1 */ - void (*tcl_Panic) (const char *format, ...) TCL_FORMAT_PRINTF(1, 2); /* 2 */ + TCL_NORETURN1 void (*tcl_Panic) (const char *format, ...) TCL_FORMAT_PRINTF(1, 2); /* 2 */ char * (*tcl_Alloc) (unsigned int size); /* 3 */ void (*tcl_Free) (char *ptr); /* 4 */ char * (*tcl_Realloc) (char *ptr, unsigned int size); /* 5 */ @@ -2080,7 +2081,7 @@ typedef struct TclStubs { void (*tcl_SetErrno) (int err); /* 227 */ void (*tcl_SetErrorCode) (Tcl_Interp *interp, ...); /* 228 */ void (*tcl_SetMaxBlockTime) (const Tcl_Time *timePtr); /* 229 */ - void (*tcl_SetPanicProc) (Tcl_PanicProc *panicProc); /* 230 */ + void (*tcl_SetPanicProc) (TCL_NORETURN1 Tcl_PanicProc *panicProc); /* 230 */ int (*tcl_SetRecursionLimit) (Tcl_Interp *interp, int depth); /* 231 */ void (*tcl_SetResult) (Tcl_Interp *interp, char *result, Tcl_FreeProc *freeProc); /* 232 */ int (*tcl_SetServiceMode) (int mode); /* 233 */ @@ -2128,7 +2129,7 @@ typedef struct TclStubs { void (*tcl_SetErrorCodeVA) (Tcl_Interp *interp, va_list argList); /* 275 */ int (*tcl_VarEvalVA) (Tcl_Interp *interp, va_list argList); /* 276 */ Tcl_Pid (*tcl_WaitPid) (Tcl_Pid pid, int *statPtr, int options); /* 277 */ - void (*tcl_PanicVA) (const char *format, va_list argList); /* 278 */ + TCL_NORETURN1 void (*tcl_PanicVA) (const char *format, va_list argList); /* 278 */ void (*tcl_GetVersion) (int *major, int *minor, int *patchLevel, int *type); /* 279 */ void (*tcl_InitMemory) (Tcl_Interp *interp); /* 280 */ Tcl_Channel (*tcl_StackChannel) (Tcl_Interp *interp, const Tcl_ChannelType *typePtr, ClientData instanceData, int mask, Tcl_Channel prevChan); /* 281 */ diff --git a/generic/tclPanic.c b/generic/tclPanic.c index 851695f..b032449 100644 --- a/generic/tclPanic.c +++ b/generic/tclPanic.c @@ -15,7 +15,7 @@ #include "tclInt.h" #if defined(_WIN32) || defined(__CYGWIN__) - MODULE_SCOPE void tclWinDebugPanic(const char *format, ...); + MODULE_SCOPE TCL_NORETURN void tclWinDebugPanic(const char *format, ...); #endif /* @@ -24,9 +24,9 @@ */ #if defined(__CYGWIN__) -static Tcl_PanicProc *panicProc = tclWinDebugPanic; +static TCL_NORETURN Tcl_PanicProc *panicProc = tclWinDebugPanic; #else -static Tcl_PanicProc *panicProc = NULL; +static TCL_NORETURN1 Tcl_PanicProc *panicProc = NULL; #endif /* @@ -47,7 +47,7 @@ static Tcl_PanicProc *panicProc = NULL; void Tcl_SetPanicProc( - Tcl_PanicProc *proc) + TCL_NORETURN1 Tcl_PanicProc *proc) { #if defined(_WIN32) /* tclWinDebugPanic only installs if there is no panicProc yet. */ diff --git a/tools/genStubs.tcl b/tools/genStubs.tcl index 7a75dc6..beede9e 100644 --- a/tools/genStubs.tcl +++ b/tools/genStubs.tcl @@ -582,6 +582,8 @@ proc genStubs::makeSlot {name decl index} { } if {[string range $rtype end-8 end] eq "__stdcall"} { append text [string trim [string range $rtype 0 end-9]] " (__stdcall *" $lfname ") " + } elseif {[string range $rtype 0 11] eq "TCL_NORETURN"} { + append text "TCL_NORETURN1 " [string trim [string range $rtype 12 end]] " (*" $lfname ") " } else { append text $rtype " (*" $lfname ") " } diff --git a/win/tclWinError.c b/win/tclWinError.c index 4d3250d..30079b9 100644 --- a/win/tclWinError.c +++ b/win/tclWinError.c @@ -381,7 +381,7 @@ TclWinConvertError( *---------------------------------------------------------------------- */ -void +TCL_NORETURN void tclWinDebugPanic( const char *format, ...) { diff --git a/win/tclWinFile.c b/win/tclWinFile.c index 02927ad..f6e3a4b 100755 --- a/win/tclWinFile.c +++ b/win/tclWinFile.c @@ -172,7 +172,7 @@ static int WinLink(const TCHAR *LinkSource, const TCHAR *LinkTarget, int linkAction); static int WinSymLinkDirectory(const TCHAR *LinkDirectory, const TCHAR *LinkTarget); -MODULE_SCOPE void tclWinDebugPanic(const char *format, ...); +MODULE_SCOPE TCL_NORETURN void tclWinDebugPanic(const char *format, ...); /* *-------------------------------------------------------------------- @@ -789,7 +789,7 @@ NativeWriteReparse( *---------------------------------------------------------------------- */ -void +TCL_NORETURN void tclWinDebugPanic( const char *format, ...) { -- cgit v0.12 From ee0b1f4703492cd3d1889551e782882b6b081b46 Mon Sep 17 00:00:00 2001 From: Miguel Sofer Date: Tue, 22 Sep 2015 20:57:58 +0000 Subject: micro-opt of hash lookups found by drh --- generic/tclHash.c | 2 +- generic/tclObj.c | 11 +++++------ generic/tclVar.c | 11 +++++------ 3 files changed, 11 insertions(+), 13 deletions(-) diff --git a/generic/tclHash.c b/generic/tclHash.c index 90be511..1991aea 100644 --- a/generic/tclHash.c +++ b/generic/tclHash.c @@ -326,7 +326,7 @@ CreateHashEntry( continue; } #endif - if (compareKeysProc((void *) key, hPtr)) { + if (((void *) key == hPtr) || compareKeysProc((void *) key, hPtr)) { if (newPtr) { *newPtr = 0; } diff --git a/generic/tclObj.c b/generic/tclObj.c index f9216b3..15ea91f 100644 --- a/generic/tclObj.c +++ b/generic/tclObj.c @@ -3971,12 +3971,11 @@ TclCompareObjKeys( /* * If the object pointers are the same then they match. - */ - - if (objPtr1 == objPtr2) { - return 1; - } - + * OPT: this comparison was moved to the caller + + if (objPtr1 == objPtr2) return 1; + */ + /* * Don't use Tcl_GetStringFromObj as it would prevent l1 and l2 being * in a register. diff --git a/generic/tclVar.c b/generic/tclVar.c index b37283b..f93de3b 100644 --- a/generic/tclVar.c +++ b/generic/tclVar.c @@ -6364,12 +6364,11 @@ CompareVarKeys( /* * If the object pointers are the same then they match. - */ - - if (objPtr1 == objPtr2) { - return 1; - } - + * OPT: this comparison was moved to the caller + + if (objPtr1 == objPtr2) return 1; + */ + /* * Don't use Tcl_GetStringFromObj as it would prevent l1 and l2 being in a * register. -- cgit v0.12