summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--generic/regc_color.c15
-rw-r--r--generic/regc_cvec.c1
-rw-r--r--generic/regc_lex.c18
-rw-r--r--generic/regc_nfa.c36
-rw-r--r--generic/regcomp.c188
-rw-r--r--generic/rege_dfa.c29
-rw-r--r--generic/regerror.c4
-rw-r--r--generic/regexec.c1049
-rw-r--r--generic/regguts.h63
-rw-r--r--generic/tcl.decls6
-rw-r--r--generic/tcl.h12
-rw-r--r--generic/tclDecls.h13
-rw-r--r--generic/tclHash.c2
-rw-r--r--generic/tclObj.c11
-rw-r--r--generic/tclPanic.c8
-rw-r--r--generic/tclVar.c11
-rw-r--r--tests/reg.test10
-rw-r--r--tools/genStubs.tcl2
-rw-r--r--win/tclWinError.c2
-rwxr-xr-xwin/tclWinFile.c4
20 files changed, 839 insertions, 645 deletions
diff --git a/generic/regc_color.c b/generic/regc_color.c
index f5d6dfd..92e0aad 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) {
@@ -777,18 +777,19 @@ dumpcolors(
}
/*
- * It's hard to do this more efficiently.
+ * Unfortunately, it's hard to do this next bit more efficiently.
+ *
+ * Spencer's original coding has the loop iterating from CHR_MIN
+ * to CHR_MAX, but that's utterly unusable for 32-bit chr, or
+ * even 16-bit. For debugging purposes it seems fine to print
+ * only chr codes up to 1000 or so.
*/
- for (c=CHR_MIN ; c<CHR_MAX ; c++) {
+ for (c=CHR_MIN ; c<1000 ; c++) {
if (GETCOLOR(cm, c) == co) {
dumpchr(c, f);
}
}
- assert(c == CHR_MAX);
- if (GETCOLOR(cm, c) == co) {
- dumpchr(c, f);
- }
fprintf(f, "\n");
}
}
diff --git a/generic/regc_cvec.c b/generic/regc_cvec.c
index 0247521..d450d3e 100644
--- a/generic/regc_cvec.c
+++ b/generic/regc_cvec.c
@@ -81,6 +81,7 @@ addchr(
struct cvec *cv, /* character vector */
pchr c) /* character to add */
{
+ assert(cv->nchrs < 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 4f0c139..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
@@ -593,13 +592,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 +621,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 */
}
}
@@ -1103,11 +1104,17 @@ parseqatom(
/*
* Prepare a general-purpose state skeleton.
*
- * ---> [s] ---prefix---> [begin] ---atom---> [end] ----rest---> [rp]
- * / /
- * [lp] ----> [s2] ----bypass---------------------
+ * In the no-backrefs case, we want this:
+ *
+ * [lp] ---> [s] ---prefix---> [begin] ---atom---> [end] ---rest---> [rp]
+ *
+ * where prefix is some repetitions of atom. In the general case we need
+ *
+ * [lp] ---> [s] ---iterator---> [s2] ---rest---> [rp]
+ *
+ * where the iterator wraps around [begin] ---atom---> [end]
*
- * where bypass is an empty, and prefix is some repetitions of atom
+ * 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 */
@@ -1118,11 +1125,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();
/*
@@ -1169,27 +1174,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) {
@@ -1207,16 +1193,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);
@@ -1229,6 +1223,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 */
}
/*
@@ -1237,10 +1249,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));
@@ -1307,6 +1319,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
@@ -1716,11 +1730,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;
@@ -1773,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 {
@@ -1801,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 */
@@ -1814,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);
}
@@ -1826,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
@@ -1932,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;
@@ -1997,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);
}
/*
@@ -2040,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)) {
@@ -2149,14 +2181,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/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&REG_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&REG_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 3b9af3e..6d12827 100644
--- a/generic/regexec.c
+++ b/generic/regexec.c
@@ -107,13 +107,13 @@ struct vars {
chr *start; /* start of string */
chr *stop; /* just past end of string */
int err; /* error code if any (0 none) */
- regoff_t *mem; /* memory vector for backtracking */
+ struct dfa **subdfas; /* per-subre DFAs */
struct smalldfa dfa1;
struct smalldfa dfa2;
};
#define VISERR(vv) ((vv)->err != 0) /* have we seen an error yet? */
#define ISERR() VISERR(v)
-#define VERR(vv,e) (((vv)->err) ? (vv)->err : ((vv)->err = (e)))
+#define VERR(vv,e) ((vv)->err = ((vv)->err ? (vv)->err : (e)))
#define ERR(e) VERR(v, e) /* record an error */
#define NOERR() {if (ISERR()) return v->err;} /* if error seen, return it */
#define OFF(p) ((p) - v->start)
@@ -126,21 +126,20 @@ 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);
-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);
@@ -174,10 +173,11 @@ exec(
AllocVars(v);
int st, backref;
size_t n;
+ size_t i;
#define LOCALMAT 20
regmatch_t mat[LOCALMAT];
-#define LOCALMEM 40
- regoff_t mem[LOCALMEM];
+#define LOCALDFAS 40
+ struct dfa *subdfas[LOCALDFAS];
/*
* Sanity checks.
@@ -235,28 +235,20 @@ exec(
v->start = (chr *)string;
v->stop = (chr *)string + len;
v->err = 0;
- if (backref) {
- /*
- * Need retry memory.
- */
-
- assert(v->g->ntree >= 0);
- n = (size_t)v->g->ntree;
- if (n <= LOCALMEM) {
- v->mem = mem;
- } else {
- v->mem = (regoff_t *) MALLOC(n*sizeof(regoff_t));
- }
- if (v->mem == NULL) {
- if (v->pmatch != pmatch && v->pmatch != mat) {
- FREE(v->pmatch);
- }
- FreeVars(v);
- return REG_ESPACE;
- }
- } else {
- v->mem = NULL;
+ assert(v->g->ntree >= 0);
+ n = (size_t) v->g->ntree;
+ if (n <= LOCALDFAS)
+ v->subdfas = subdfas;
+ else
+ v->subdfas = (struct dfa **) MALLOC(n * sizeof(struct dfa *));
+ if (v->subdfas == NULL) {
+ if (v->pmatch != pmatch && v->pmatch != mat)
+ FREE(v->pmatch);
+ FreeVars(v);
+ return REG_ESPACE;
}
+ for (i = 0; i < n; i++)
+ v->subdfas[i] = NULL;
/*
* Do it.
@@ -274,7 +266,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,14 +278,35 @@ exec(
if (v->pmatch != pmatch && v->pmatch != mat) {
FREE(v->pmatch);
}
- if (v->mem != NULL && v->mem != mem) {
- FREE(v->mem);
+ n = (size_t) v->g->ntree;
+ for (i = 0; i < n; i++) {
+ if (v->subdfas[i] != NULL)
+ freeDFA(v->subdfas[i]);
}
+ if (v->subdfas != subdfas)
+ FREE(v->subdfas);
FreeVars(v);
return st;
}
/*
+ - 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 *);
*/
@@ -357,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;
}
@@ -388,11 +404,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 +504,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);
@@ -501,6 +516,7 @@ complicatedFindLoop(
}
if (er != REG_NOMATCH) {
ERR(er);
+ *coldp = cold;
return er;
}
if ((shorter) ? end == estop : end == begin) {
@@ -525,11 +541,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 +558,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,247 +607,91 @@ subset(
}
/*
- - dissect - determine subexpression matches (uncomplicated case)
- ^ static int dissect(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 */
-dissect(
- struct vars *const v,
+cdissect(
+ struct vars *v,
struct subre *t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
+ chr *begin, /* beginning of relevant substring */
+ chr *end) /* end of same */
{
-#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
- restart:
-#endif
- assert(t != NULL);
- MDEBUG(("dissect %ld-%ld\n", LOFF(begin), LOFF(end)));
-
- 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 *);
- */
-static int /* regexec return code */
-concatenationDissect(
- struct vars *const v,
- struct subre *const t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
-{
- 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;
-
- assert(t != NULL);
- assert(t->op == '|');
-
- for (i = 0; t != NULL; t = t->right, i++) {
- struct dfa *d;
+ int er;
- 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 - dissect match for concatenation node
+ ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
-complicatedConcatenationDissect(
- struct vars *const v,
- struct subre *const t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
+ccondissect(
+ struct vars *v,
+ struct subre *t,
+ chr *begin, /* beginning of relevant substring */
+ chr *end) /* end of same */
{
struct dfa *d, *d2;
chr *mid;
@@ -842,39 +699,23 @@ complicatedConcatenationDissect(
assert(t->op == '.');
assert(t->left != NULL && t->left->cnfa.nstates > 0);
assert(t->right != NULL && t->right->cnfa.nstates > 0);
+ assert(!(t->left->flags & SHORTER));
- if (t->left->flags&SHORTER) { /* reverse scan */
- return complicatedReversedDissect(v, t, begin, end);
- }
+ d = getsubdfa(v, t->left);
+ NOERR();
+ d2 = getsubdfa(v, t->right);
+ NOERR();
- d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
- if (ISERR()) {
- return v->err;
- }
- d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
- if (ISERR()) {
- freeDFA(d);
- return v->err;
- }
- MDEBUG(("cConcat %d\n", t->retry));
+ MDEBUG(("cConcat %d\n", t->id));
/*
* Pick a tentative midpoint.
*/
-
- if (v->mem[t->retry] == 0) {
- mid = longest(v, d, begin, end, NULL);
- if (mid == NULL) {
- freeDFA(d);
- freeDFA(d2);
- return REG_NOMATCH;
- }
- MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
- v->mem[t->retry] = (mid - begin) + 1;
- } else {
- mid = begin + (v->mem[t->retry] - 1);
- MDEBUG(("working midpoint %ld\n", LOFF(mid)));
+ mid = longest(v, d, begin, end, (int *) NULL);
+ if (mid == NULL) {
+ return REG_NOMATCH;
}
+ MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
/*
* Iterate until satisfaction or failure.
@@ -886,24 +727,20 @@ 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.
*/
MDEBUG(("successful\n"));
- freeDFA(d);
- freeDFA(d2);
return REG_OKAY;
}
}
- if ((er != REG_OKAY) && (er != REG_NOMATCH)) {
- freeDFA(d);
- freeDFA(d2);
+ if (er != REG_NOMATCH) {
return er;
}
}
@@ -917,9 +754,7 @@ complicatedConcatenationDissect(
* All possibilities exhausted.
*/
- MDEBUG(("%d no midpoint\n", t->retry));
- freeDFA(d);
- freeDFA(d2);
+ MDEBUG(("%d no midpoint\n", t->id));
return REG_NOMATCH;
}
mid = longest(v, d, begin, mid-1, NULL);
@@ -928,31 +763,25 @@ complicatedConcatenationDissect(
* Failed to find a new one.
*/
- MDEBUG(("%d failed midpoint\n", t->retry));
- freeDFA(d);
- freeDFA(d2);
+ MDEBUG(("%d failed midpoint\n", t->id));
return REG_NOMATCH;
}
- MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
- v->mem[t->retry] = (mid - begin) + 1;
- 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(
- struct vars *const v,
- struct subre *const t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
+crevcondissect(
+ struct vars *v,
+ struct subre *t,
+ chr *begin, /* beginning of relevant substring */
+ chr *end) /* end of same */
{
struct dfa *d, *d2;
chr *mid;
@@ -962,38 +791,22 @@ complicatedReversedDissect(
assert(t->right != NULL && t->right->cnfa.nstates > 0);
assert(t->left->flags&SHORTER);
- /*
- * Concatenation -- need to split the substring between parts.
- */
+ d = getsubdfa(v, t->left);
+ NOERR();
+ d2 = getsubdfa(v, t->right);
+ NOERR();
- d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
- if (ISERR()) {
- return v->err;
- }
- d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
- if (ISERR()) {
- freeDFA(d);
- return v->err;
- }
- MDEBUG(("cRev %d\n", t->retry));
+ MDEBUG(("crevcon %d\n", t->id));
/*
* Pick a tentative midpoint.
*/
- if (v->mem[t->retry] == 0) {
- mid = shortest(v, d, begin, begin, end, NULL, NULL);
- if (mid == NULL) {
- freeDFA(d);
- freeDFA(d2);
- return REG_NOMATCH;
- }
- MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
- v->mem[t->retry] = (mid - begin) + 1;
- } else {
- mid = begin + (v->mem[t->retry] - 1);
- MDEBUG(("working midpoint %ld\n", LOFF(mid)));
+ mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL);
+ if (mid == NULL) {
+ return REG_NOMATCH;
}
+ MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
/*
* Iterate until satisfaction or failure.
@@ -1005,24 +818,20 @@ 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.
*/
MDEBUG(("successful\n"));
- freeDFA(d);
- freeDFA(d2);
return REG_OKAY;
}
}
- if (er != REG_OKAY && er != REG_NOMATCH) {
- freeDFA(d);
- freeDFA(d2);
+ if (er != REG_NOMATCH) {
return er;
}
}
@@ -1036,9 +845,7 @@ complicatedReversedDissect(
* All possibilities exhausted.
*/
- MDEBUG(("%d no midpoint\n", t->retry));
- freeDFA(d);
- freeDFA(d2);
+ MDEBUG(("%d no midpoint\n", t->id));
return REG_NOMATCH;
}
mid = shortest(v, d, begin, mid+1, end, NULL, NULL);
@@ -1047,164 +854,474 @@ complicatedReversedDissect(
* Failed to find a new one.
*/
- MDEBUG(("%d failed midpoint\n", t->retry));
- freeDFA(d);
- freeDFA(d2);
+ MDEBUG(("%d failed midpoint\n", t->id));
return REG_NOMATCH;
}
- MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
- v->mem[t->retry] = (mid - begin) + 1;
- 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(
- struct vars *const v,
- struct subre *const t,
- chr *const begin, /* beginning of relevant substring */
- chr *const end) /* end of same */
+cbrdissect(
+ struct vars *v,
+ struct subre *t,
+ chr *begin, /* beginning of relevant substring */
+ chr *end) /* end of same */
{
- int i, n = t->subno, min = t->min, max = t->max;
- chr *paren, *p, *stop;
- 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;
- /*
- * No room to maneuver -- retries are pointless.
- */
-
- if (v->mem[t->retry]) {
+ /* special cases for zero-length strings */
+ if (brlen == 0) {
+ /*
+ * matches only if target is zero length, but any number of
+ * repetitions can be considered to be present
+ */
+ if (begin == end && min <= max) {
+ MDEBUG(("cbackref matched trivially\n"));
+ return REG_OKAY;
+ }
return REG_NOMATCH;
}
- v->mem[t->retry] = 1;
-
- /*
- * Special-case zero-length string.
- */
-
- if (len == 0) {
- if (begin == end) {
+ if (begin == end) {
+ /* matches only if zero repetitions are okay */
+ if (min == 0) {
+ MDEBUG(("cbackref matched trivially\n"));
return REG_OKAY;
}
return REG_NOMATCH;
}
/*
- * And too-short string.
+ * check target length to see if it could possibly be an allowed number of
+ * repetitions of brstring
*/
- assert(end >= begin);
- if ((size_t)(end - begin) < len) {
+ assert(end > begin);
+ tlen = end - begin;
+ if (tlen % brlen != 0)
+ return REG_NOMATCH;
+ numreps = tlen / brlen;
+ if (numreps < (size_t)min || (numreps > (size_t)max && max != DUPINF))
return REG_NOMATCH;
+
+ /* okay, compare the actual string contents */
+ p = begin;
+ while (numreps-- > 0) {
+ if ((*v->g->compare) (brstring, p, brlen) != 0)
+ return REG_NOMATCH;
+ p += brlen;
}
- stop = end - len;
- /*
- * Count occurrences.
- */
+ MDEBUG(("cbackref matched\n"));
+ return REG_OKAY;
+}
+
+/*
+ - caltdissect - dissect match for alternation node
+ ^ static int caltdissect(struct vars *, struct subre *, chr *, chr *);
+ */
+static int /* regexec return code */
+caltdissect(
+ struct vars *v,
+ struct subre *t,
+ chr *begin, /* beginning of relevant substring */
+ chr *end) /* end of same */
+{
+ struct dfa *d;
+ int er;
+
+ /* We loop, rather than tail-recurse, to handle a chain of alternatives */
+ while (t != NULL) {
+ assert(t->op == '|');
+ assert(t->left != NULL && t->left->cnfa.nstates > 0);
- i = 0;
- for (p = begin; p <= stop && (i < max || max == DUPINF); p += len) {
- if (v->g->compare(paren, p, len) != 0) {
- break;
+ MDEBUG(("calt n%d\n", t->id));
+
+ d = getsubdfa(v, t->left);
+ NOERR();
+ if (longest(v, d, begin, end, (int *) NULL) == end) {
+ MDEBUG(("calt matched\n"));
+ er = cdissect(v, t->left, begin, end);
+ if (er != REG_NOMATCH) {
+ return er;
+ }
}
- i++;
+
+ t = t->right;
}
- MDEBUG(("cbackref found %d\n", i));
+
+ return REG_NOMATCH;
+}
+
+/*
+ - citerdissect - dissect match for iteration node
+ ^ static int citerdissect(struct vars *, struct subre *, chr *, chr *);
+ */
+static int /* regexec return code */
+citerdissect(struct vars * v,
+ struct subre * t,
+ chr *begin, /* beginning of relevant substring */
+ chr *end) /* end of same */
+{
+ struct dfa *d;
+ chr **endpts;
+ chr *limit;
+ int min_matches;
+ size_t max_matches;
+ int nverified;
+ int k;
+ int i;
+ int er;
+
+ assert(t->op == '*');
+ assert(t->left != NULL && t->left->cnfa.nstates > 0);
+ assert(!(t->left->flags & SHORTER));
+ assert(begin <= end);
/*
- * And sort it out.
+ * If zero matches are allowed, and target string is empty, just declare
+ * victory. OTOH, if target string isn't empty, zero matches can't work
+ * so we pretend the min is 1.
*/
+ min_matches = t->min;
+ if (min_matches <= 0) {
+ if (begin == end)
+ return REG_OKAY;
+ min_matches = 1;
+ }
- if (p != end) { /* didn't consume all of it */
- return REG_NOMATCH;
+ /*
+ * We need workspace to track the endpoints of each sub-match. Normally
+ * we consider only nonzero-length sub-matches, so there can be at most
+ * end-begin of them. However, if min is larger than that, we will also
+ * consider zero-length sub-matches in order to find enough matches.
+ *
+ * For convenience, endpts[0] contains the "begin" pointer and we store
+ * sub-match endpoints in endpts[1..max_matches].
+ */
+ max_matches = end - begin;
+ if (max_matches > (size_t)t->max && t->max != DUPINF)
+ max_matches = t->max;
+ if (max_matches < (size_t)min_matches)
+ max_matches = min_matches;
+ endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *));
+ if (endpts == NULL)
+ return REG_ESPACE;
+ endpts[0] = begin;
+
+ d = getsubdfa(v, t->left);
+ if (ISERR()) {
+ FREE(endpts);
+ return v->err;
}
- if (min <= i && (i <= max || max == DUPINF)) {
- return REG_OKAY;
+ MDEBUG(("citer %d\n", t->id));
+
+ /*
+ * Our strategy is to first find a set of sub-match endpoints that are
+ * valid according to the child node's DFA, and then recursively dissect
+ * each sub-match to confirm validity. If any validity check fails,
+ * backtrack the last sub-match and try again. And, when we next try for
+ * a validity check, we need not recheck any successfully verified
+ * sub-matches that we didn't move the endpoints of. nverified remembers
+ * how many sub-matches are currently known okay.
+ */
+
+ /* initialize to consider first sub-match */
+ nverified = 0;
+ k = 1;
+ limit = end;
+
+ /* iterate until satisfaction or failure */
+ while (k > 0) {
+ /* try to find an endpoint for the k'th sub-match */
+ endpts[k] = longest(v, d, endpts[k - 1], limit, (int *) NULL);
+ if (endpts[k] == NULL) {
+ /* no match possible, so see if we can shorten previous one */
+ k--;
+ goto backtrack;
+ }
+ MDEBUG(("%d: working endpoint %d: %ld\n",
+ t->id, k, LOFF(endpts[k])));
+
+ /* k'th sub-match can no longer be considered verified */
+ if (nverified >= k)
+ nverified = k - 1;
+
+ if (endpts[k] != end) {
+ /* haven't reached end yet, try another iteration if allowed */
+ if ((size_t)k >= max_matches) {
+ /* must try to shorten some previous match */
+ k--;
+ goto backtrack;
+ }
+
+ /* reject zero-length match unless necessary to achieve min */
+ if (endpts[k] == endpts[k - 1] &&
+ (k >= min_matches || min_matches - k < end - endpts[k]))
+ goto backtrack;
+
+ k++;
+ limit = end;
+ continue;
+ }
+
+ /*
+ * We've identified a way to divide the string into k sub-matches
+ * that works so far as the child DFA can tell. If k is an allowed
+ * number of matches, start the slow part: recurse to verify each
+ * sub-match. We always have k <= max_matches, needn't check that.
+ */
+ if (k < min_matches)
+ goto backtrack;
+
+ MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));
+
+ for (i = nverified + 1; i <= k; i++) {
+ zaptreesubs(v, t->left);
+ er = cdissect(v, t->left, endpts[i - 1], endpts[i]);
+ if (er == REG_OKAY) {
+ nverified = i;
+ continue;
+ }
+ if (er == REG_NOMATCH)
+ break;
+ /* oops, something failed */
+ FREE(endpts);
+ return er;
+ }
+
+ if (i > k) {
+ /* satisfaction */
+ MDEBUG(("%d successful\n", t->id));
+ FREE(endpts);
+ return REG_OKAY;
+ }
+
+ /* match failed to verify, so backtrack */
+
+ backtrack:
+ /*
+ * Must consider shorter versions of the current sub-match. However,
+ * we'll only ask for a zero-length match if necessary.
+ */
+ while (k > 0) {
+ chr *prev_end = endpts[k - 1];
+
+ if (endpts[k] > prev_end) {
+ limit = endpts[k] - 1;
+ if (limit > prev_end ||
+ (k < min_matches && min_matches - k >= end - prev_end)) {
+ /* break out of backtrack loop, continue the outer one */
+ break;
+ }
+ }
+ /* can't shorten k'th sub-match any more, consider previous one */
+ k--;
+ }
}
- return REG_NOMATCH; /* out of range */
+
+ /* all possibilities exhausted */
+ MDEBUG(("%d failed\n", t->id));
+ FREE(endpts);
+ return REG_NOMATCH;
}
/*
- - 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 > (size_t)t->max && t->max != DUPINF)
+ max_matches = t->max;
+ if (max_matches < (size_t)min_matches)
+ max_matches = min_matches;
+ endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *));
+ if (endpts == NULL)
+ return REG_ESPACE;
+ endpts[0] = begin;
+
+ d = getsubdfa(v, t->left);
+ if (ISERR()) {
+ FREE(endpts);
+ return v->err;
}
+ MDEBUG(("creviter %d\n", t->id));
- MDEBUG(("cAlt n%d\n", t->retry));
- assert(t->left != NULL);
+ /*
+ * Our strategy is to first find a set of sub-match endpoints that are
+ * valid according to the child node's DFA, and then recursively dissect
+ * each sub-match to confirm validity. If any validity check fails,
+ * backtrack the last sub-match and try again. And, when we next try for
+ * a validity check, we need not recheck any successfully verified
+ * sub-matches that we didn't move the endpoints of. nverified remembers
+ * how many sub-matches are currently known okay.
+ */
- if (v->mem[t->retry] == UNTRIED) {
- 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 ((size_t)k >= max_matches)
+ limit = end;
+
+ /* try to find an endpoint for the k'th sub-match */
+ endpts[k] = shortest(v, d, endpts[k - 1], limit, end,
+ (chr **) NULL, (int *) NULL);
+ if (endpts[k] == NULL) {
+ /* no match possible, so see if we can lengthen previous one */
+ k--;
+ goto backtrack;
+ }
+ MDEBUG(("%d: working endpoint %d: %ld\n",
+ t->id, k, LOFF(endpts[k])));
+
+ /* k'th sub-match can no longer be considered verified */
+ if (nverified >= k)
+ nverified = k - 1;
+
+ if (endpts[k] != end) {
+ /* haven't reached end yet, try another iteration if allowed */
+ if ((size_t)k >= max_matches) {
+ /* must try to lengthen some previous match */
+ k--;
+ goto backtrack;
+ }
- if (ISERR()) {
- return v->err;
+ k++;
+ limit = endpts[k - 1];
+ continue;
}
- if (longest(v, d, begin, end, NULL) != end) {
- freeDFA(d);
- v->mem[t->retry] = TRIED;
- goto doRight;
+
+ /*
+ * We've identified a way to divide the string into k sub-matches
+ * that works so far as the child DFA can tell. If k is an allowed
+ * number of matches, start the slow part: recurse to verify each
+ * sub-match. We always have k <= max_matches, needn't check that.
+ */
+ if (k < min_matches)
+ goto backtrack;
+
+ MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));
+
+ for (i = nverified + 1; i <= k; i++) {
+ zaptreesubs(v, t->left);
+ er = cdissect(v, t->left, endpts[i - 1], endpts[i]);
+ if (er == REG_OKAY) {
+ nverified = i;
+ continue;
+ }
+ if (er == REG_NOMATCH)
+ break;
+ /* oops, something failed */
+ FREE(endpts);
+ return er;
}
- freeDFA(d);
- MDEBUG(("cAlt matched\n"));
- v->mem[t->retry] = TRYING;
- }
- er = complicatedDissect(v, t->left, begin, end);
- if (er != REG_NOMATCH) {
- return er;
+ if (i > k) {
+ /* satisfaction */
+ MDEBUG(("%d successful\n", t->id));
+ FREE(endpts);
+ return REG_OKAY;
+ }
+
+ /* match failed to verify, so backtrack */
+
+ backtrack:
+ /*
+ * Must consider longer versions of the current sub-match.
+ */
+ while (k > 0) {
+ if (endpts[k] < end) {
+ limit = endpts[k] + 1;
+ /* break out of backtrack loop, continue the outer one */
+ break;
+ }
+ /* can't lengthen k'th sub-match any more, consider previous one */
+ k--;
+ }
}
- v->mem[t->retry] = TRIED;
-#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));
+ FREE(endpts);
+ return REG_NOMATCH;
}
#include "rege_dfa.c"
diff --git a/generic/regguts.h b/generic/regguts.h
index 1b6abe6..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)
@@ -329,11 +349,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 +386,10 @@ struct subre {
#define PREF(f) ((f)&NOPROP)
#define PREF2(f1, f2) ((PREF(f1) != 0) ? PREF(f1) : PREF(f2))
#define COMBINE(f1, f2) (UP((f1)|(f2)) | PREF2(f1, f2))
- short retry; /* index into retry memory */
+ short id; /* ID of subre (1..ntree-1) */
int subno; /* subexpression number (for 'b' and '(') */
- short min; /* min repetitions, for backref only */
- short max; /* max repetitions, for backref only */
+ short min; /* min repetitions for iteration or backref */
+ short max; /* max repetitions for iteration or backref */
struct subre *left; /* left child, if any (also freelist chain) */
struct subre *right; /* right child, if any */
struct state *begin; /* outarcs from here... */
@@ -382,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 */
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..a08edde 100644
--- a/generic/tcl.h
+++ b/generic/tcl.h
@@ -143,8 +143,20 @@ extern "C" {
#endif
#if defined(__GNUC__) && (__GNUC__ > 2)
# define TCL_FORMAT_PRINTF(a,b) __attribute__ ((__format__ (__printf__, a, b)))
+# define TCL_NORETURN __attribute__ ((noreturn))
+# if defined(BUILD_tcl) || defined(BUILD_tk)
+# define TCL_NORETURN1 __attribute__ ((noreturn))
+# else
+# define TCL_NORETURN1 /* nothing */
+# endif
#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/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/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/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.
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"
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, ...)
{
generated by cgit v0.12 at 2024-07-08 06:26:39 (GMT)