summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--generic/rege_dfa.c212
-rw-r--r--generic/regexec.c478
2 files changed, 338 insertions, 352 deletions
diff --git a/generic/rege_dfa.c b/generic/rege_dfa.c
index e233680..920ea6c 100644
--- a/generic/rege_dfa.c
+++ b/generic/rege_dfa.c
@@ -36,17 +36,16 @@
*/
static chr * /* endpoint, or NULL */
longest(
- struct vars *v, /* used only for debug and exec flags */
- struct dfa *d,
- chr *start, /* where the match should start */
- chr *stop, /* match must end at or before here */
- int *hitstopp) /* record whether hit v->stop, if non-NULL */
+ struct vars *const v, /* used only for debug and exec flags */
+ struct dfa *const d,
+ chr *const start, /* where the match should start */
+ chr *const stop, /* match must end at or before here */
+ int *const hitstopp) /* record whether hit v->stop, if non-NULL */
{
chr *cp;
chr *realstop = (stop == v->stop) ? stop : stop + 1;
color co;
- struct sset *css;
- struct sset *ss;
+ struct sset *css, *ss;
chr *post;
int i;
struct colormap *cm = d->cm;
@@ -164,20 +163,19 @@ longest(
*/
static chr * /* endpoint, or NULL */
shortest(
- struct vars *v,
- struct dfa *d,
- chr *start, /* where the match should start */
- chr *min, /* match must end at or after here */
- chr *max, /* match must end at or before here */
- chr **coldp, /* store coldstart pointer here, if nonNULL */
- int *hitstopp) /* record whether hit v->stop, if non-NULL */
+ struct vars *const v,
+ struct dfa *const d,
+ chr *const start, /* where the match should start */
+ chr *const min, /* match must end at or after here */
+ chr *const max, /* match must end at or before here */
+ chr **const coldp, /* store coldstart pointer here, if nonNULL */
+ int *const hitstopp) /* record whether hit v->stop, if non-NULL */
{
chr *cp;
chr *realmin = (min == v->stop) ? min : min + 1;
chr *realmax = (max == v->stop) ? max : max + 1;
color co;
- struct sset *css;
- struct sset *ss;
+ struct sset *css, *ss;
struct colormap *cm = d->cm;
/*
@@ -256,7 +254,7 @@ shortest(
}
if (coldp != NULL) { /* report last no-progress state set, if any */
- *coldp = lastcold(v, d);
+ *coldp = lastCold(v, d);
}
if ((ss->flags&POSTSTATE) && cp > min) {
@@ -284,19 +282,18 @@ shortest(
}
/*
- - lastcold - determine last point at which no progress had been made
- ^ static chr *lastcold(struct vars *, struct dfa *);
+ - lastCold - determine last point at which no progress had been made
+ ^ static chr *lastCold(struct vars *, struct dfa *);
*/
static chr * /* endpoint, or NULL */
-lastcold(
- struct vars *v,
- struct dfa *d)
+lastCold(
+ struct vars *const v,
+ struct dfa *const d)
{
struct sset *ss;
- chr *nopr;
+ chr *nopr = d->lastnopr;
int i;
- nopr = d->lastnopr;
if (nopr == NULL) {
nopr = v->start;
}
@@ -309,15 +306,15 @@ lastcold(
}
/*
- - newdfa - set up a fresh DFA
- ^ static struct dfa *newdfa(struct vars *, struct cnfa *,
+ - newDFA - set up a fresh DFA
+ ^ static struct dfa *newDFA(struct vars *, struct cnfa *,
^ struct colormap *, struct smalldfa *);
*/
static struct dfa *
-newdfa(
- struct vars *v,
- struct cnfa *cnfa,
- struct colormap *cm,
+newDFA(
+ struct vars *const v,
+ struct cnfa *const cnfa,
+ struct colormap *const cm,
struct smalldfa *sml) /* preallocated space, may be NULL */
{
struct dfa *d;
@@ -345,12 +342,12 @@ newdfa(
d->cptsmalloced = 0;
d->mallocarea = (smallwas == NULL) ? (char *)sml : NULL;
} else {
- d = (struct dfa *)MALLOC(sizeof(struct dfa));
+ d = (struct dfa *) MALLOC(sizeof(struct dfa));
if (d == NULL) {
ERR(REG_ESPACE);
return NULL;
}
- d->ssets = (struct sset *)MALLOC(nss * sizeof(struct sset));
+ d->ssets = (struct sset *) MALLOC(nss * sizeof(struct sset));
d->statesarea = (unsigned *)
MALLOC((nss+WORK) * wordsper * sizeof(unsigned));
d->work = &d->statesarea[nss * wordsper];
@@ -362,7 +359,7 @@ newdfa(
d->mallocarea = (char *)d;
if (d->ssets == NULL || d->statesarea == NULL ||
d->outsarea == NULL || d->incarea == NULL) {
- freedfa(d);
+ freeDFA(d);
ERR(REG_ESPACE);
return NULL;
}
@@ -387,12 +384,12 @@ newdfa(
}
/*
- - freedfa - free a DFA
- ^ static void freedfa(struct dfa *);
+ - freeDFA - free a DFA
+ ^ static void freeDFA(struct dfa *);
*/
static void
-freedfa(
- struct dfa *d)
+freeDFA(
+ struct dfa *const d)
{
if (d->cptsmalloced) {
if (d->ssets != NULL) {
@@ -421,8 +418,8 @@ freedfa(
*/
static unsigned
hash(
- unsigned *uv,
- int n)
+ unsigned *const uv,
+ const int n)
{
int i;
unsigned h;
@@ -440,9 +437,9 @@ hash(
*/
static struct sset *
initialize(
- struct vars *v, /* used only for debug flags */
- struct dfa *d,
- chr *start)
+ struct vars *const v, /* used only for debug flags */
+ struct dfa *const d,
+ chr *const start)
{
struct sset *ss;
int i;
@@ -454,7 +451,7 @@ initialize(
if (d->nssused > 0 && (d->ssets[0].flags&STARTER)) {
ss = &d->ssets[0];
} else { /* no, must (re)build it */
- ss = getvacant(v, d, start, start);
+ ss = getVacantSS(v, d, start, start);
for (i = 0; i < d->wordsper; i++) {
ss->states[i] = 0;
}
@@ -484,23 +481,18 @@ initialize(
*/
static struct sset * /* NULL if goes to empty set */
miss(
- struct vars *v, /* used only for debug flags */
- struct dfa *d,
- struct sset *css,
- pcolor co,
- chr *cp, /* next chr */
- chr *start) /* where the attempt got started */
+ struct vars *const v, /* used only for debug flags */
+ struct dfa *const d,
+ struct sset *const css,
+ const pcolor co,
+ chr *const cp, /* next chr */
+ chr *const start) /* where the attempt got started */
{
struct cnfa *cnfa = d->cnfa;
- int i;
unsigned h;
struct carc *ca;
struct sset *p;
- int ispost;
- int noprogress;
- int gotstate;
- int dolacons;
- int sawlacons;
+ int i, isPost, noProgress, gotState, doLAConstraints, sawLAConstraints;
/*
* For convenience, we can be called even if it might not be a miss.
@@ -519,57 +511,57 @@ miss(
for (i = 0; i < d->wordsper; i++) {
d->work[i] = 0;
}
- ispost = 0;
- noprogress = 1;
- gotstate = 0;
+ isPost = 0;
+ noProgress = 1;
+ gotState = 0;
for (i = 0; i < d->nstates; i++) {
if (ISBSET(css->states, i)) {
for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++) {
if (ca->co == co) {
BSET(d->work, ca->to);
- gotstate = 1;
+ gotState = 1;
if (ca->to == cnfa->post) {
- ispost = 1;
+ isPost = 1;
}
if (!cnfa->states[ca->to]->co) {
- noprogress = 0;
+ noProgress = 0;
}
FDEBUG(("%d -> %d\n", i, ca->to));
}
}
}
}
- dolacons = (gotstate) ? (cnfa->flags&HASLACONS) : 0;
- sawlacons = 0;
- while (dolacons) { /* transitive closure */
- dolacons = 0;
+ doLAConstraints = (gotState ? (cnfa->flags&HASLACONS) : 0);
+ sawLAConstraints = 0;
+ while (doLAConstraints) { /* transitive closure */
+ doLAConstraints = 0;
for (i = 0; i < d->nstates; i++) {
if (ISBSET(d->work, i)) {
for (ca = cnfa->states[i]+1; ca->co != COLORLESS; ca++) {
if (ca->co <= cnfa->ncolors) {
- continue; /* NOTE CONTINUE */
+ continue; /* NOTE CONTINUE */
}
- sawlacons = 1;
+ sawLAConstraints = 1;
if (ISBSET(d->work, ca->to)) {
- continue; /* NOTE CONTINUE */
+ continue; /* NOTE CONTINUE */
}
- if (!lacon(v, cnfa, cp, ca->co)) {
- continue; /* NOTE CONTINUE */
+ if (!checkLAConstraint(v, cnfa, cp, ca->co)) {
+ continue; /* NOTE CONTINUE */
}
BSET(d->work, ca->to);
- dolacons = 1;
+ doLAConstraints = 1;
if (ca->to == cnfa->post) {
- ispost = 1;
+ isPost = 1;
}
if (!cnfa->states[ca->to]->co) {
- noprogress = 0;
+ noProgress = 0;
}
FDEBUG(("%d :> %d\n", i, ca->to));
}
}
}
}
- if (!gotstate) {
+ if (!gotState) {
return NULL;
}
h = HASH(d->work, d->wordsper);
@@ -585,14 +577,14 @@ miss(
}
}
if (i == 0) { /* nope, need a new cache entry */
- p = getvacant(v, d, cp, start);
+ p = getVacantSS(v, d, cp, start);
assert(p != css);
for (i = 0; i < d->wordsper; i++) {
p->states[i] = d->work[i];
}
p->hash = h;
- p->flags = (ispost) ? POSTSTATE : 0;
- if (noprogress) {
+ p->flags = (isPost ? POSTSTATE : 0);
+ if (noProgress) {
p->flags |= NOPROGRESS;
}
@@ -601,26 +593,26 @@ miss(
*/
}
- if (!sawlacons) { /* lookahead conds. always cache miss */
+ if (!sawLAConstraints) { /* lookahead conds. always cache miss */
FDEBUG(("c%d[%d]->c%d\n", css - d->ssets, co, p - d->ssets));
css->outs[co] = p;
css->inchain[co] = p->ins;
p->ins.ss = css;
- p->ins.co = (color)co;
+ p->ins.co = (color) co;
}
return p;
}
/*
- - lacon - lookahead-constraint checker for miss()
- ^ static int lacon(struct vars *, struct cnfa *, chr *, pcolor);
+ - checkLAConstraint - lookahead-constraint checker for miss()
+ ^ static int checkLAConstraint(struct vars *, struct cnfa *, chr *, pcolor);
*/
static int /* predicate: constraint satisfied? */
-lacon(
- struct vars *v,
- struct cnfa *pcnfa, /* parent cnfa */
- chr *cp,
- pcolor co) /* "color" of the lookahead constraint */
+checkLAConstraint(
+ struct vars *const v,
+ struct cnfa *const pcnfa, /* parent cnfa */
+ chr *const cp,
+ const pcolor co) /* "color" of the lookahead constraint */
{
int n;
struct subre *sub;
@@ -632,38 +624,36 @@ lacon(
assert(n < v->g->nlacons && v->g->lacons != NULL);
FDEBUG(("=== testing lacon %d\n", n));
sub = &v->g->lacons[n];
- d = newdfa(v, &sub->cnfa, &v->g->cmap, &sd);
+ d = newDFA(v, &sub->cnfa, &v->g->cmap, &sd);
if (d == NULL) {
ERR(REG_ESPACE);
return 0;
}
- end = longest(v, d, cp, v->stop, (int *)NULL);
- freedfa(d);
+ end = longest(v, d, cp, v->stop, NULL);
+ freeDFA(d);
FDEBUG(("=== lacon %d match %d\n", n, (end != NULL)));
return (sub->subno) ? (end != NULL) : (end == NULL);
}
/*
- - getvacant - get a vacant state set
+ - getVacantSS - get a vacant state set
* This routine clears out the inarcs and outarcs, but does not otherwise
* clear the innards of the state set -- that's up to the caller.
- ^ static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
+ ^ static struct sset *getVacantSS(struct vars *, struct dfa *, chr *, chr *);
*/
static struct sset *
-getvacant(
- struct vars *v, /* used only for debug flags */
- struct dfa *d,
- chr *cp,
- chr *start)
+getVacantSS(
+ struct vars *const v, /* used only for debug flags */
+ struct dfa *const d,
+ chr *const cp,
+ chr *const start)
{
int i;
- struct sset *ss;
- struct sset *p;
- struct arcp ap;
- struct arcp lastap = {NULL, 0}; /* silence gcc 4 warning */
+ struct sset *ss, *p;
+ struct arcp ap, lastap = {NULL, 0}; /* silence gcc 4 warning */
color co;
- ss = pickss(v, d, cp, start);
+ ss = pickNextSS(v, d, cp, start);
assert(!(ss->flags&LOCKED));
/*
@@ -695,8 +685,7 @@ getvacant(
p->ins = ss->inchain[i];
} else {
assert(p->ins.ss != NULL);
- for (ap = p->ins; ap.ss != NULL &&
- !(ap.ss == ss && ap.co == i);
+ for (ap = p->ins; ap.ss != NULL && !(ap.ss == ss && ap.co == i);
ap = ap.ss->inchain[ap.co]) {
lastap = ap;
}
@@ -729,19 +718,18 @@ getvacant(
}
/*
- - pickss - pick the next stateset to be used
- ^ static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);
+ - pickNextSS - pick the next stateset to be used
+ ^ static struct sset *pickNextSS(struct vars *, struct dfa *, chr *, chr *);
*/
static struct sset *
-pickss(
- struct vars *v, /* used only for debug flags */
- struct dfa *d,
- chr *cp,
- chr *start)
+pickNextSS(
+ struct vars *const v, /* used only for debug flags */
+ struct dfa *const d,
+ chr *const cp,
+ chr *const start)
{
int i;
- struct sset *ss;
- struct sset *end;
+ struct sset *ss, *end;
chr *ancient;
/*
diff --git a/generic/regexec.c b/generic/regexec.c
index b369d2b..9b6a693 100644
--- a/generic/regexec.c
+++ b/generic/regexec.c
@@ -126,33 +126,33 @@ struct vars {
/* automatically gathered by fwd; do not hand-edit */
/* === regexec.c === */
int exec(regex_t *, const chr *, size_t, rm_detail_t *, size_t, regmatch_t [], int);
-static int find(struct vars *, struct cnfa *, struct colormap *);
-static int cfind(struct vars *, struct cnfa *, struct colormap *);
-static int cfindloop(struct vars *, struct cnfa *, struct colormap *, struct dfa *, struct dfa *, chr **);
-static void zapsubs(regmatch_t *, size_t);
-static void zapmem(struct vars *, struct subre *);
-static void subset(struct vars *, struct subre *, chr *, chr *);
-static int dissect(struct vars *, struct subre *, chr *, chr *);
-static int condissect(struct vars *, struct subre *, chr *, chr *);
-static int altdissect(struct vars *, struct subre *, chr *, chr *);
-static inline int cdissect(struct vars *, struct subre *, chr *, chr *);
-static int ccaptdissect(struct vars *, struct subre *, chr *, chr *);
-static int ccondissect(struct vars *, struct subre *, chr *, chr *);
-static int crevdissect(struct vars *, struct subre *, chr *, chr *);
-static int cbrdissect(struct vars *, struct subre *, chr *, chr *);
-static int caltdissect(struct vars *, struct subre *, chr *, chr *);
+static int simpleFind(struct vars *const, struct cnfa *const, struct colormap *const);
+static int complicatedFind(struct vars *const, struct cnfa *const, struct colormap *const);
+static int complicatedFindLoop(struct vars *const, struct cnfa *const, struct colormap *const, struct dfa *const, struct dfa *const, chr **const);
+static void zapSubexpressions(regmatch_t *const, const size_t);
+static void zapSubtree(struct vars *const, struct subre *const);
+static void subset(struct vars *const, struct subre *const, chr *const, chr *const);
+static int dissect(struct vars *const, struct subre *, chr *const, chr *const);
+static int concatenationDissect(struct vars *const, struct subre *const, chr *const, chr *const);
+static int alternationDissect(struct vars *const, struct subre *, chr *const, chr *const);
+static inline int complicatedDissect(struct vars *const, struct subre *const, chr *const, chr *const);
+static int complicatedCapturingDissect(struct vars *const, struct subre *const, chr *const, chr *const);
+static int complicatedConcatenationDissect(struct vars *const, struct subre *const, chr *const, chr *const);
+static int complicatedReversedDissect(struct vars *const, struct subre *const, chr *const, chr *const);
+static int complicatedBackrefDissect(struct vars *const, struct subre *const, chr *const, chr *const);
+static int complicatedAlternationDissect(struct vars *const, struct subre *, chr *const, chr *const);
/* === rege_dfa.c === */
-static chr *longest(struct vars *, struct dfa *, chr *, chr *, int *);
-static chr *shortest(struct vars *, struct dfa *, chr *, chr *, chr *, chr **, int *);
-static chr *lastcold(struct vars *, struct dfa *);
-static struct dfa *newdfa(struct vars *, struct cnfa *, struct colormap *, struct smalldfa *);
-static void freedfa(struct dfa *);
-static unsigned hash(unsigned *, int);
-static struct sset *initialize(struct vars *, struct dfa *, chr *);
-static struct sset *miss(struct vars *, struct dfa *, struct sset *, pcolor, chr *, chr *);
-static int lacon(struct vars *, struct cnfa *, chr *, pcolor);
-static struct sset *getvacant(struct vars *, struct dfa *, chr *, chr *);
-static struct sset *pickss(struct vars *, struct dfa *, chr *, chr *);
+static chr *longest(struct vars *const, struct dfa *const, chr *const, chr *const, int *const);
+static chr *shortest(struct vars *const, struct dfa *const, chr *const, chr *const, chr *const, chr **const, int *const);
+static chr *lastCold(struct vars *const, struct dfa *const);
+static struct dfa *newDFA(struct vars *const, struct cnfa *const, struct colormap *const, struct smalldfa *);
+static void freeDFA(struct dfa *const);
+static unsigned hash(unsigned *const, const int);
+static struct sset *initialize(struct vars *const, struct dfa *const, chr *const);
+static struct sset *miss(struct vars *const, struct dfa *const, struct sset *const, const pcolor, chr *const, chr *const);
+static int checkLAConstraint(struct vars *const, struct cnfa *const, chr *const, const pcolor);
+static struct sset *getVacantSS(struct vars *const, struct dfa *const, chr *const, chr *const);
+static struct sset *pickNextSS(struct vars *const, struct dfa *const, chr *const, chr *const);
/* automatically gathered by fwd; do not hand-edit */
/* =====^!^===== end forwards =====^!^===== */
@@ -172,9 +172,8 @@ exec(
int flags)
{
AllocVars(v);
- int st;
+ int st, backref;
size_t n;
- int backref;
#define LOCALMAT 20
regmatch_t mat[LOCALMAT];
#define LOCALMEM 40
@@ -265,9 +264,9 @@ exec(
assert(v->g->tree != NULL);
if (backref) {
- st = cfind(v, &v->g->tree->cnfa, &v->g->cmap);
+ st = complicatedFind(v, &v->g->tree->cnfa, &v->g->cmap);
} else {
- st = find(v, &v->g->tree->cnfa, &v->g->cmap);
+ st = simpleFind(v, &v->g->tree->cnfa, &v->g->cmap);
}
/*
@@ -275,7 +274,7 @@ exec(
*/
if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) {
- zapsubs(pmatch, nmatch);
+ zapSubexpressions(pmatch, nmatch);
n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t));
}
@@ -295,23 +294,20 @@ exec(
}
/*
- - find - find a match for the main NFA (no-complications case)
- ^ static int find(struct vars *, struct cnfa *, struct colormap *);
+ - simpleFind - find a match for the main NFA (no-complications case)
+ ^ static int simpleFind(struct vars *, struct cnfa *, struct colormap *);
*/
static int
-find(
- struct vars *v,
- struct cnfa *cnfa,
- struct colormap *cm)
+simpleFind(
+ struct vars *const v,
+ struct cnfa *const cnfa,
+ struct colormap *const cm)
{
- struct dfa *s;
- struct dfa *d;
- chr *begin;
- chr *end = NULL;
+ struct dfa *s, *d;
+ chr *begin, *end = NULL;
chr *cold;
- chr *open; /* Open and close of range of possible
+ chr *open, *close; /* Open and close of range of possible
* starts */
- chr *close;
int hitend;
int shorter = (v->g->tree->flags&SHORTER) ? 1 : 0;
@@ -319,13 +315,13 @@ find(
* First, a shot with the search RE.
*/
- s = newdfa(v, &v->g->search, cm, &v->dfa1);
+ s = newDFA(v, &v->g->search, cm, &v->dfa1);
assert(!(ISERR() && s != NULL));
NOERR();
MDEBUG(("\nsearch at %ld\n", LOFF(v->start)));
cold = NULL;
close = shortest(v, s, v->start, v->start, v->stop, &cold, NULL);
- freedfa(s);
+ freeDFA(s);
NOERR();
if (v->g->cflags&REG_EXPECT) {
assert(v->details != NULL);
@@ -351,7 +347,7 @@ find(
open = cold;
cold = NULL;
MDEBUG(("between %ld and %ld\n", LOFF(open), LOFF(close)));
- d = newdfa(v, cnfa, cm, &v->dfa1);
+ d = newDFA(v, cnfa, cm, &v->dfa1);
assert(!(ISERR() && d != NULL));
NOERR();
for (begin = open; begin <= close; begin++) {
@@ -370,7 +366,7 @@ find(
}
}
assert(end != NULL); /* search RE succeeded so loop should */
- freedfa(d);
+ freeDFA(d);
/*
* And pin down details.
@@ -395,38 +391,37 @@ find(
* Submatches.
*/
- zapsubs(v->pmatch, v->nmatch);
+ zapSubexpressions(v->pmatch, v->nmatch);
return dissect(v, v->g->tree, begin, end);
}
/*
- - cfind - find a match for the main NFA (with complications)
- ^ static int cfind(struct vars *, struct cnfa *, struct colormap *);
+ - complicatedFind - find a match for the main NFA (with complications)
+ ^ static int complicatedFind(struct vars *, struct cnfa *, struct colormap *);
*/
static int
-cfind(
- struct vars *v,
- struct cnfa *cnfa,
- struct colormap *cm)
+complicatedFind(
+ struct vars *const v,
+ struct cnfa *const cnfa,
+ struct colormap *const cm)
{
- struct dfa *s;
- struct dfa *d;
+ struct dfa *s, *d;
chr *cold = NULL; /* silence gcc 4 warning */
int ret;
- s = newdfa(v, &v->g->search, cm, &v->dfa1);
+ s = newDFA(v, &v->g->search, cm, &v->dfa1);
NOERR();
- d = newdfa(v, cnfa, cm, &v->dfa2);
+ d = newDFA(v, cnfa, cm, &v->dfa2);
if (ISERR()) {
assert(d == NULL);
- freedfa(s);
+ freeDFA(s);
return v->err;
}
- ret = cfindloop(v, cnfa, cm, d, s, &cold);
+ ret = complicatedFindLoop(v, cnfa, cm, d, s, &cold);
- freedfa(d);
- freedfa(s);
+ freeDFA(d);
+ freeDFA(s);
NOERR();
if (v->g->cflags&REG_EXPECT) {
assert(v->details != NULL);
@@ -441,30 +436,26 @@ cfind(
}
/*
- - cfindloop - the heart of cfind
- ^ static int cfindloop(struct vars *, struct cnfa *, struct colormap *,
+ - complicatedFindLoop - the heart of complicatedFind
+ ^ static int complicatedFindLoop(struct vars *, struct cnfa *, struct colormap *,
^ struct dfa *, struct dfa *, chr **);
*/
static int
-cfindloop(
- struct vars *v,
- struct cnfa *cnfa,
- struct colormap *cm,
- struct dfa *d,
- struct dfa *s,
- chr **coldp) /* where to put coldstart pointer */
+complicatedFindLoop(
+ struct vars *const v,
+ struct cnfa *const cnfa,
+ struct colormap *const cm,
+ struct dfa *const d,
+ struct dfa *const s,
+ chr **const coldp) /* where to put coldstart pointer */
{
- chr *begin;
- chr *end;
+ chr *begin, *end;
chr *cold;
- chr *open; /* Open and close of range of possible
+ chr *open, *close; /* Open and close of range of possible
* starts */
- chr *close;
- chr *estart;
- chr *estop;
- int er;
+ chr *estart, *estop;
+ int er, hitend;
int shorter = v->g->tree->flags&SHORTER;
- int hitend;
assert(d != NULL && s != NULL);
cold = NULL;
@@ -480,7 +471,7 @@ cfindloop(
cold = NULL;
MDEBUG(("cbetween %ld and %ld\n", LOFF(open), LOFF(close)));
for (begin = open; begin <= close; begin++) {
- MDEBUG(("\ncfind trying at %ld\n", LOFF(begin)));
+ MDEBUG(("\ncomplicatedFind trying at %ld\n", LOFF(begin)));
estart = begin;
estop = v->stop;
for (;;) {
@@ -497,9 +488,9 @@ cfindloop(
}
MDEBUG(("tentative end %ld\n", LOFF(end)));
- zapsubs(v->pmatch, v->nmatch);
- zapmem(v, v->g->tree);
- er = cdissect(v, v->g->tree, begin, end);
+ zapSubexpressions(v->pmatch, v->nmatch);
+ zapSubtree(v, v->g->tree);
+ er = complicatedDissect(v, v->g->tree, begin, end);
if (er == REG_OKAY) {
if (v->nmatch > 0) {
v->pmatch[0].rm_so = OFF(begin);
@@ -539,13 +530,13 @@ cfindloop(
}
/*
- - zapsubs - initialize the subexpression matches to "no match"
- ^ static void zapsubs(regmatch_t *, size_t);
+ - zapSubexpressions - initialize the subexpression matches to "no match"
+ ^ static void zapSubexpressions(regmatch_t *, size_t);
*/
static void
-zapsubs(
- regmatch_t *p,
- size_t n)
+zapSubexpressions(
+ regmatch_t *const p,
+ const size_t n)
{
size_t i;
@@ -556,13 +547,13 @@ zapsubs(
}
/*
- - zapmem - initialize the retry memory of a subtree to zeros
- ^ static void zapmem(struct vars *, struct subre *);
+ - zapSubtree - initialize the retry memory of a subtree to zeros
+ ^ static void zapSubtree(struct vars *, struct subre *);
*/
static void
-zapmem(
- struct vars *v,
- struct subre *t)
+zapSubtree(
+ struct vars *const v,
+ struct subre *const t)
{
if (t == NULL) {
return;
@@ -573,14 +564,14 @@ zapmem(
if (t->op == '(') {
assert(t->subno > 0);
v->pmatch[t->subno].rm_so = -1;
- v->pmatch[t->subno].rm_eo = -1;
+ v->pmatch[t->subno].rm_eo = -1;
}
if (t->left != NULL) {
- zapmem(v, t->left);
+ zapSubtree(v, t->left);
}
if (t->right != NULL) {
- zapmem(v, t->right);
+ zapSubtree(v, t->right);
}
}
@@ -590,10 +581,10 @@ zapmem(
*/
static void
subset(
- struct vars *v,
- struct subre *sub,
- chr *begin,
- chr *end)
+ struct vars *const v,
+ struct subre *const sub,
+ chr *const begin,
+ chr *const end)
{
int n = sub->subno;
@@ -613,10 +604,10 @@ subset(
*/
static int /* regexec return code */
dissect(
- struct vars *v,
+ struct vars *const v,
struct subre *t,
- chr *begin, /* beginning of relevant substring */
- chr *end) /* end of same */
+ chr *const begin, /* beginning of relevant substring */
+ chr *const end) /* end of same */
{
#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
restart:
@@ -630,12 +621,12 @@ dissect(
return REG_OKAY; /* no action, parent did the work */
case '|': /* alternation */
assert(t->left != NULL);
- return altdissect(v, t, begin, end);
+ return alternationDissect(v, t, begin, end);
case 'b': /* back ref -- shouldn't be calling us! */
return REG_ASSERT;
case '.': /* concatenation */
assert(t->left != NULL && t->right != NULL);
- return condissect(v, t, begin, end);
+ return concatenationDissect(v, t, begin, end);
case '(': /* capturing */
assert(t->left != NULL && t->right == NULL);
assert(t->subno > 0);
@@ -652,18 +643,18 @@ dissect(
}
/*
- - condissect - determine concatenation subexpression matches (uncomplicated)
- ^ static int condissect(struct vars *, struct subre *, chr *, chr *);
+ - concatenationDissect - determine concatenation subexpression matches
+ - (uncomplicated)
+ ^ static int concatenationDissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
-condissect(
- struct vars *v,
- struct subre *t,
- chr *begin, /* beginning of relevant substring */
- chr *end) /* end of same */
+concatenationDissect(
+ struct vars *const v,
+ struct subre *const t,
+ chr *const begin, /* beginning of relevant substring */
+ chr *const end) /* end of same */
{
- struct dfa *d;
- struct dfa *d2;
+ struct dfa *d, *d2;
chr *mid;
int i;
int shorter = (t->left->flags&SHORTER) ? 1 : 0;
@@ -673,12 +664,12 @@ condissect(
assert(t->left != NULL && t->left->cnfa.nstates > 0);
assert(t->right != NULL && t->right->cnfa.nstates > 0);
- d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
+ d = newDFA(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
NOERR();
- d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, &v->dfa2);
+ d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, &v->dfa2);
if (ISERR()) {
assert(d2 == NULL);
- freedfa(d);
+ freeDFA(d);
return v->err;
}
@@ -692,8 +683,8 @@ condissect(
mid = longest(v, d, begin, end, NULL);
}
if (mid == NULL) {
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_ASSERT;
}
MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
@@ -713,8 +704,8 @@ condissect(
*/
MDEBUG(("no midpoint!\n"));
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_ASSERT;
}
if (shorter) {
@@ -728,8 +719,8 @@ condissect(
*/
MDEBUG(("failed midpoint!\n"));
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_ASSERT;
}
MDEBUG(("new midpoint %ld\n", LOFF(mid)));
@@ -740,8 +731,8 @@ condissect(
*/
MDEBUG(("successful\n"));
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
i = dissect(v, t->left, begin, mid);
if (i != REG_OKAY) {
return i;
@@ -750,54 +741,55 @@ condissect(
}
/*
- - altdissect - determine alternative subexpression matches (uncomplicated)
- ^ static int altdissect(struct vars *, struct subre *, chr *, chr *);
+ - alternationDissect - determine alternative subexpression matches (uncomplicated)
+ ^ static int alternationDissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
-altdissect(
- struct vars *v,
+alternationDissect(
+ struct vars *const v,
struct subre *t,
- chr *begin, /* beginning of relevant substring */
- chr *end) /* end of same */
+ chr *const begin, /* beginning of relevant substring */
+ chr *const end) /* end of same */
{
- struct dfa *d;
int i;
assert(t != NULL);
assert(t->op == '|');
for (i = 0; t != NULL; t = t->right, i++) {
+ struct dfa *d;
+
MDEBUG(("trying %dth\n", i));
assert(t->left != NULL && t->left->cnfa.nstates > 0);
- d = newdfa(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
+ d = newDFA(v, &t->left->cnfa, &v->g->cmap, &v->dfa1);
if (ISERR()) {
return v->err;
}
if (longest(v, d, begin, end, NULL) == end) {
MDEBUG(("success\n"));
- freedfa(d);
+ freeDFA(d);
return dissect(v, t->left, begin, end);
}
- freedfa(d);
+ freeDFA(d);
}
return REG_ASSERT; /* none of them matched?!? */
}
/*
- - cdissect - determine subexpression matches (with complications)
+ - complicatedDissect - determine subexpression matches (with complications)
* The retry memory stores the offset of the trial midpoint from begin, plus 1
* so that 0 uniquely means "clean slate".
- ^ static int cdissect(struct vars *, struct subre *, chr *, chr *);
+ ^ static int complicatedDissect(struct vars *, struct subre *, chr *, chr *);
*/
static inline int /* regexec return code */
-cdissect(
- struct vars *v,
- struct subre *t,
- chr *begin, /* beginning of relevant substring */
- chr *end) /* end of same */
+complicatedDissect(
+ struct vars *const v,
+ struct subre *const t,
+ chr *const begin, /* beginning of relevant substring */
+ chr *const end) /* end of same */
{
assert(t != NULL);
- MDEBUG(("cdissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));
+ MDEBUG(("complicatedDissect %ld-%ld %c\n", LOFF(begin), LOFF(end), t->op));
switch (t->op) {
case '=': /* terminal node */
@@ -805,30 +797,30 @@ cdissect(
return REG_OKAY; /* no action, parent did the work */
case '|': /* alternation */
assert(t->left != NULL);
- return caltdissect(v, t, begin, end);
+ return complicatedAlternationDissect(v, t, begin, end);
case 'b': /* back ref -- shouldn't be calling us! */
assert(t->left == NULL && t->right == NULL);
- return cbrdissect(v, t, begin, end);
+ return complicatedBackrefDissect(v, t, begin, end);
case '.': /* concatenation */
assert(t->left != NULL && t->right != NULL);
- return ccondissect(v, t, begin, end);
+ return complicatedConcatenationDissect(v, t, begin, end);
case '(': /* capturing */
assert(t->left != NULL && t->right == NULL);
assert(t->subno > 0);
- return ccaptdissect(v, t, begin, end);
+ return complicatedCapturingDissect(v, t, begin, end);
default:
return REG_ASSERT;
}
}
static int /* regexec return code */
-ccaptdissect(
- struct vars *v,
- struct subre *t,
- chr *begin, /* beginning of relevant substring */
- chr *end) /* end of same */
+complicatedCapturingDissect(
+ struct vars *const v,
+ struct subre *const t,
+ chr *const begin, /* beginning of relevant substring */
+ chr *const end) /* end of same */
{
- int er = cdissect(v, t->left, begin, end);
+ int er = complicatedDissect(v, t->left, begin, end);
if (er == REG_OKAY) {
subset(v, t, begin, end);
@@ -837,41 +829,39 @@ ccaptdissect(
}
/*
- - ccondissect - concatenation subexpression matches (with complications)
+ - complicatedConcatenationDissect - concatenation subexpression matches (with complications)
* The retry memory stores the offset of the trial midpoint from begin, plus 1
* so that 0 uniquely means "clean slate".
- ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *);
+ ^ static int complicatedConcatenationDissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
-ccondissect(
- struct vars *v,
- struct subre *t,
- chr *begin, /* beginning of relevant substring */
- chr *end) /* end of same */
+complicatedConcatenationDissect(
+ struct vars *const v,
+ struct subre *const t,
+ chr *const begin, /* beginning of relevant substring */
+ chr *const end) /* end of same */
{
- struct dfa *d;
- struct dfa *d2;
+ struct dfa *d, *d2;
chr *mid;
- int er;
assert(t->op == '.');
assert(t->left != NULL && t->left->cnfa.nstates > 0);
assert(t->right != NULL && t->right->cnfa.nstates > 0);
if (t->left->flags&SHORTER) { /* reverse scan */
- return crevdissect(v, t, begin, end);
+ return complicatedReversedDissect(v, t, begin, end);
}
- d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+ d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
if (ISERR()) {
return v->err;
}
- d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
+ d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
if (ISERR()) {
- freedfa(d);
+ freeDFA(d);
return v->err;
}
- MDEBUG(("cconcat %d\n", t->retry));
+ MDEBUG(("cConcat %d\n", t->retry));
/*
* Pick a tentative midpoint.
@@ -880,8 +870,8 @@ ccondissect(
if (v->mem[t->retry] == 0) {
mid = longest(v, d, begin, end, NULL);
if (mid == NULL) {
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_NOMATCH;
}
MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
@@ -901,23 +891,24 @@ ccondissect(
*/
if (longest(v, d2, mid, end, NULL) == end) {
- er = cdissect(v, t->left, begin, mid);
+ int er = complicatedDissect(v, t->left, begin, mid);
+
if (er == REG_OKAY) {
- er = cdissect(v, t->right, mid, end);
+ er = complicatedDissect(v, t->right, mid, end);
if (er == REG_OKAY) {
/*
* Satisfaction.
*/
MDEBUG(("successful\n"));
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_OKAY;
}
}
if ((er != REG_OKAY) && (er != REG_NOMATCH)) {
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return er;
}
}
@@ -932,8 +923,8 @@ ccondissect(
*/
MDEBUG(("%d no midpoint\n", t->retry));
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_NOMATCH;
}
mid = longest(v, d, begin, mid-1, NULL);
@@ -943,34 +934,33 @@ ccondissect(
*/
MDEBUG(("%d failed midpoint\n", t->retry));
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_NOMATCH;
}
MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
v->mem[t->retry] = (mid - begin) + 1;
- zapmem(v, t->left);
- zapmem(v, t->right);
+ zapSubtree(v, t->left);
+ zapSubtree(v, t->right);
}
}
/*
- - crevdissect - determine backref shortest-first subexpression matches
+ - complicatedReversedDissect - determine backref shortest-first subexpression
+ - matches
* The retry memory stores the offset of the trial midpoint from begin, plus 1
* so that 0 uniquely means "clean slate".
- ^ static int crevdissect(struct vars *, struct subre *, chr *, chr *);
+ ^ static int complicatedReversedDissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
-crevdissect(
- struct vars *v,
- struct subre *t,
- chr *begin, /* beginning of relevant substring */
- chr *end) /* end of same */
+complicatedReversedDissect(
+ struct vars *const v,
+ struct subre *const t,
+ chr *const begin, /* beginning of relevant substring */
+ chr *const end) /* end of same */
{
- struct dfa *d;
- struct dfa *d2;
+ struct dfa *d, *d2;
chr *mid;
- int er;
assert(t->op == '.');
assert(t->left != NULL && t->left->cnfa.nstates > 0);
@@ -981,16 +971,16 @@ crevdissect(
* Concatenation -- need to split the substring between parts.
*/
- d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+ d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
if (ISERR()) {
return v->err;
}
- d2 = newdfa(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
+ d2 = newDFA(v, &t->right->cnfa, &v->g->cmap, DOMALLOC);
if (ISERR()) {
- freedfa(d);
+ freeDFA(d);
return v->err;
}
- MDEBUG(("crev %d\n", t->retry));
+ MDEBUG(("cRev %d\n", t->retry));
/*
* Pick a tentative midpoint.
@@ -999,8 +989,8 @@ crevdissect(
if (v->mem[t->retry] == 0) {
mid = shortest(v, d, begin, begin, end, NULL, NULL);
if (mid == NULL) {
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_NOMATCH;
}
MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));
@@ -1020,23 +1010,24 @@ crevdissect(
*/
if (longest(v, d2, mid, end, NULL) == end) {
- er = cdissect(v, t->left, begin, mid);
+ int er = complicatedDissect(v, t->left, begin, mid);
+
if (er == REG_OKAY) {
- er = cdissect(v, t->right, mid, end);
+ er = complicatedDissect(v, t->right, mid, end);
if (er == REG_OKAY) {
/*
* Satisfaction.
*/
MDEBUG(("successful\n"));
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_OKAY;
}
}
if (er != REG_OKAY && er != REG_NOMATCH) {
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return er;
}
}
@@ -1051,8 +1042,8 @@ crevdissect(
*/
MDEBUG(("%d no midpoint\n", t->retry));
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_NOMATCH;
}
mid = shortest(v, d, begin, mid+1, end, NULL, NULL);
@@ -1062,36 +1053,31 @@ crevdissect(
*/
MDEBUG(("%d failed midpoint\n", t->retry));
- freedfa(d);
- freedfa(d2);
+ freeDFA(d);
+ freeDFA(d2);
return REG_NOMATCH;
}
MDEBUG(("%d: new midpoint %ld\n", t->retry, LOFF(mid)));
v->mem[t->retry] = (mid - begin) + 1;
- zapmem(v, t->left);
- zapmem(v, t->right);
+ zapSubtree(v, t->left);
+ zapSubtree(v, t->right);
}
}
/*
- - cbrdissect - determine backref subexpression matches
- ^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *);
+ - complicatedBackrefDissect - determine backref subexpression matches
+ ^ static int complicatedBackrefDissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
-cbrdissect(
- struct vars *v,
- struct subre *t,
- chr *begin, /* beginning of relevant substring */
- chr *end) /* end of same */
+complicatedBackrefDissect(
+ struct vars *const v,
+ struct subre *const t,
+ chr *const begin, /* beginning of relevant substring */
+ chr *const end) /* end of same */
{
- int i;
- int n = t->subno;
+ int i, n = t->subno, min = t->min, max = t->max;
+ chr *paren, *p, *stop;
size_t len;
- chr *paren;
- chr *p;
- chr *stop;
- int min = t->min;
- int max = t->max;
assert(t != NULL);
assert(t->op == 'b');
@@ -1163,55 +1149,67 @@ cbrdissect(
}
/*
- - caltdissect - determine alternative subexpression matches (w. complications)
- ^ static int caltdissect(struct vars *, struct subre *, chr *, chr *);
+ - complicatedAlternationDissect - determine alternative subexpression matches (w.
+ - complications)
+ ^ static int complicatedAlternationDissect(struct vars *, struct subre *, chr *, chr *);
*/
static int /* regexec return code */
-caltdissect(
- struct vars *v,
+complicatedAlternationDissect(
+ struct vars *const v,
struct subre *t,
- chr *begin, /* beginning of relevant substring */
- chr *end) /* end of same */
+ chr *const begin, /* beginning of relevant substring */
+ chr *const end) /* end of same */
{
- struct dfa *d;
int er;
#define UNTRIED 0 /* not yet tried at all */
#define TRYING 1 /* top matched, trying submatches */
#define TRIED 2 /* top didn't match or submatches exhausted */
+#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
+ if (0) {
+ doRight:
+ t = t->right;
+ }
+#endif
if (t == NULL) {
return REG_NOMATCH;
}
assert(t->op == '|');
if (v->mem[t->retry] == TRIED) {
- return caltdissect(v, t->right, begin, end);
+ goto doRight;
}
- MDEBUG(("calt n%d\n", t->retry));
+ MDEBUG(("cAlt n%d\n", t->retry));
assert(t->left != NULL);
if (v->mem[t->retry] == UNTRIED) {
- d = newdfa(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+ struct dfa *d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
+
if (ISERR()) {
return v->err;
}
if (longest(v, d, begin, end, NULL) != end) {
- freedfa(d);
+ freeDFA(d);
v->mem[t->retry] = TRIED;
- return caltdissect(v, t->right, begin, end);
+ goto doRight;
}
- freedfa(d);
- MDEBUG(("calt matched\n"));
+ freeDFA(d);
+ MDEBUG(("cAlt matched\n"));
v->mem[t->retry] = TRYING;
}
- er = cdissect(v, t->left, begin, end);
+ er = complicatedDissect(v, t->left, begin, end);
if (er != REG_NOMATCH) {
return er;
}
v->mem[t->retry] = TRIED;
- return caltdissect(v, t->right, begin, end);
+#ifndef COMPILER_DOES_TAILCALL_OPTIMIZATION
+ goto doRight;
+#else
+ doRight:
+ return complicatedAlternationDissect(v, t->right, begin, end);
+#endif
}
#include "rege_dfa.c"