Tcl Source Code

	atom = subre(v, '=', 0, lp, rp);
	NOERR();
    }

    /*
     * Prepare a general-purpose state skeleton.
     *
     * 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]
     *
     * 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 */
    s2 = newstate(v->nfa);
    NOERR();
    moveouts(v->nfa, lp, s);
    moveins(v->nfa, rp, s2);
    NOERR();
    atom->begin = s;
    atom->end = s2;
    s = newstate(v->nfa);	/* set up starting state */

    NOERR();
    EMPTYARC(lp, s);

    NOERR();

    /*
     * Break remaining subRE into x{...} and what follows.
     */

    t = subre(v, '.', COMBINE(qprefer, atom->flags), lp, rp);

	dupnfa(v->nfa, v->subs[subno]->begin, v->subs[subno]->end,
		atom->begin, atom->end);
	NOERR();
    }

    /*


     * It's quantifier time.  If the atom is just a backref, we'll let it deal















     * with quantifiers internally.


     */

    if (atomtype == BACKREF) {
	/*
	 * Special case: backrefs have internal quantifiers.
	 */

	EMPTYARC(s, atom->begin);	/* empty prefix */

	/*
	 * Just stuff everything into atom.
	 */

	repeat(v, atom->begin, atom->end, m, n);
	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 */
	/* rest of branch can be strung starting from atom->end */
	s2 = atom->end;
    } else if (m > 0 && !(atom->flags & BACKR)) {
	/*
	 * 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);
	assert(m >= 1 && m != DUPINF && n >= 1);
	repeat(v, s, atom->begin, m-1, (n == DUPINF) ? n : n-1);
	f = COMBINE(qprefer, atom->flags);
	t = subre(v, '.', f, s, atom->end);	/* prefix and atom */
	NOERR();
	t->left = subre(v, '=', PREF(f), s, atom->begin);
	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 */
    }

    /*
     * And finally, look after that postponed recursion.
     */

    t = top->right;
    if (!(SEE('|') || SEE(stopper) || SEE(EOS))) {
	t->right = parsebranch(v, stopper, type, s2, rp, 1);
    } else {
	EMPTYARC(s2, rp);
	t->right = subre(v, '=', 0, s2, rp);
    }
    NOERR();
    assert(SEE('|') || SEE(stopper) || SEE(EOS));
    t->flags |= COMBINE(t->flags, t->right->flags);
    top->flags |= COMBINE(top->flags, t->flags);
}


	return 0;
    }
    return n;
}

/*
 - 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
 * and right end states, however!) This used to be important for the subRE
 * tree, although the important bits are now handled by the in-line code in
 * parse(), and when this is called, it doesn't matter any more.
 ^ static void repeat(struct vars *, struct state *, struct state *, int, int);

	    ERR(REG_ESPACE);
	    return NULL;
	}
	ret->chain = v->treechain;
	v->treechain = ret;
    }

    assert(strchr("=b|.*(", op) != NULL);

    ret->op = op;
    ret->flags = flags;
    ret->id = 0;		/* will be assigned later */
    ret->subno = 0;
    ret->min = ret->max = 1;
    ret->left = NULL;
    ret->right = NULL;
    ret->begin = begin;
    ret->end = end;
    ZAPCNFA(ret->cnfa);

     * nothing with less effort.
     */

    return;
}

/*
 - numst - number tree nodes (assigning "id" indexes)
 ^ static int numst(struct subre *, int);
 */
static int			/* next number */
numst(
    struct subre *t,
    int start)			/* starting point for subtree numbers */
{
    int i;

    assert(t != NULL);

    i = start;
    t->id = (short) i++;
    if (t->left != NULL) {
	i = numst(t->left, i);
    }
    if (t->right != NULL) {
	i = numst(t->right, i);
    }
    return i;

static const char *			/* points to buf or constant string */
stid(
    struct subre *t,
    char *buf,
    size_t bufsize)
{
    /*
     * Big enough for hex int or decimal t->id?
     */

    if (bufsize < sizeof(void*)*2 + 3 || bufsize < sizeof(t->id)*3 + 1) {
	return "unable";
    }
    if (t->id != 0) {
	sprintf(buf, "%d", t->id);
    } else {
	sprintf(buf, "%p", t);
    }
    return buf;
}

#include "regc_lex.c"

    int eflags;			/* copies of arguments */
    size_t nmatch;
    regmatch_t *pmatch;
    rm_detail_t *details;
    chr *start;			/* start of string */
    chr *stop;			/* just past end of string */
    int err;			/* error code if any (0 none) */

    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	ERR(e)	VERR(v, e)	/* record an error */

/* =====^!^===== begin forwards =====^!^===== */
/* automatically gathered by fwd; do not hand-edit */
/* === regexec.c === */
int exec(regex_t *, const chr *, size_t, rm_detail_t *, size_t, regmatch_t [], int);
static int simpleFind(struct vars *const, struct cnfa *const, struct colormap *const);
static int complicatedFind(struct vars *const, struct cnfa *const, struct colormap *const);
static int complicatedFindLoop(struct vars *const, struct cnfa *const, struct colormap *const, struct dfa *const, struct dfa *const, chr **const);
static void 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 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);
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);

    int flags)
{
    AllocVars(v);
    int st, backref;
    size_t n;
#define	LOCALMAT	20
    regmatch_t mat[LOCALMAT];



    /*
     * Sanity checks.
     */

    if (re == NULL || string == NULL || re->re_magic != REMAGIC) {
	FreeVars(v);

    } else {
	v->pmatch = pmatch;
    }
    v->details = details;
    v->start = (chr *)string;
    v->stop = (chr *)string + len;
    v->err = 0;























    /*
     * Do it.
     */

    assert(v->g->tree != NULL);
    if (backref) {
	st = complicatedFind(v, &v->g->tree->cnfa, &v->g->cmap);
    } else {
	st = simpleFind(v, &v->g->tree->cnfa, &v->g->cmap);
    }

    /*
     * Copy (portion of) match vector over if necessary.
     */

    if (st == REG_OKAY && v->pmatch != pmatch && nmatch > 0) {
	zapallsubs(pmatch, nmatch);
	n = (nmatch < v->nmatch) ? nmatch : v->nmatch;
	memcpy(VS(pmatch), VS(v->pmatch), n*sizeof(regmatch_t));
    }

    /*
     * Clean up.
     */

    if (v->pmatch != pmatch && v->pmatch != mat) {
	FREE(v->pmatch);
    }



    FreeVars(v);
    return st;
}

/*
 - simpleFind - find a match for the main NFA (no-complications case)
 ^ static int simpleFind(struct vars *, struct cnfa *, struct colormap *);

	v->details->rm_extend.rm_eo = OFF(v->stop);	/* unknown */
    }
    if (v->nmatch == 1) {	/* no need for submatches */
	return REG_OKAY;
    }

    /*
     * Find submatches.
     */

    zapallsubs(v->pmatch, v->nmatch);
    return cdissect(v, v->g->tree, begin, end);
}

/*
 - complicatedFind - find a match for the main NFA (with complications)
 ^ static int complicatedFind(struct vars *, struct cnfa *, struct colormap *);
 */
static int

		    cold = begin;
		}
		if (end == NULL) {
		    break;	/* NOTE BREAK OUT */
		}

		MDEBUG(("tentative end %ld\n", LOFF(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);
			v->pmatch[0].rm_eo = OFF(end);
		    }
		    *coldp = cold;
		    return REG_OKAY;

    } while (close < v->stop);

    *coldp = cold;
    return REG_NOMATCH;
}

/*
 - zapallsubs - initialize all subexpression matches to "no match"
 ^ static void zapallsubs(regmatch_t *, size_t);
 */
static void
zapallsubs(
    regmatch_t *const p,
    const size_t n)
{
    size_t i;

    for (i = n-1; i > 0; i--) {
	p[i].rm_so = -1;
	p[i].rm_eo = -1;
    }
}

/*
 - zaptreesubs - initialize subexpressions within subtree to "no match"
 ^ static void zaptreesubs(struct vars *, struct subre *);
 */
static void
zaptreesubs(
    struct vars *const v,
    struct subre *const t)
{






    if (t->op == '(') {
	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) {
	zaptreesubs(v, t->left);
    }
    if (t->right != NULL) {
	zaptreesubs(v, t->right);
    }
}

/*
 - subset - set subexpression match data for a successful subre
 ^ static void subset(struct vars *, struct subre *, chr *, chr *);
 */
static void
subset(
    struct vars *const v,
    struct subre *const sub,
    chr *const begin,

    MDEBUG(("setting %d\n", n));
    v->pmatch[n].rm_so = OFF(begin);
    v->pmatch[n].rm_eo = OFF(end);
}

/*
 - 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 */
cdissect(
    struct vars *const v,
    struct subre *const t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{


    int er;



    assert(t != NULL);


    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);



	er = REG_OKAY;		/* no action, parent did the work */

	break;





    case 'b':			/* back reference */



	assert(t->left == NULL && t->right == NULL);

	er = cbrdissect(v, t, begin, end);
	break;
    case '.':			/* concatenation */
	assert(t->left != NULL && t->right != NULL);
	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);




	er = cdissect(v, t->left, begin, end);
	if (er == REG_OKAY) {
	    subset(v, t, begin, end);
	}
	break;

    default:
	er = REG_ASSERT;

	break;















    }





















    /*


     * 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));


    return er;
}

/*
 - ccondissect - concatenation subexpression matches (with complications)


 ^ static int ccondissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
ccondissect(
    struct vars *const v,
    struct subre *const t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    struct dfa *d, *d2;
    chr *mid;

    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));



    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->id));

    /*
     * Pick a tentative midpoint.
     */


    mid = longest(v, d, begin, end, (int *) NULL);
    if (mid == NULL) {
	freeDFA(d);
	freeDFA(d2);
	return REG_NOMATCH;
    }
    MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));






    /*
     * Iterate until satisfaction or failure.
     */

    for (;;) {
	/*
	 * Try this midpoint on for size.
	 */

	if (longest(v, d2, mid, end, NULL) == end) {
	    int er = cdissect(v, t->left, begin, mid);

	    if (er == REG_OKAY) {
		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_NOMATCH) {
		freeDFA(d);
		freeDFA(d2);
		return er;
	    }
	}

	/*
	 * That midpoint didn't work, find a new one.
	 */

	if (mid == begin) {
	    /*
	     * All possibilities exhausted.
	     */

	    MDEBUG(("%d no midpoint\n", t->id));
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_NOMATCH;
	}
	mid = longest(v, d, begin, mid-1, NULL);
	if (mid == NULL) {
	    /*
	     * Failed to find a new one.
	     */

	    MDEBUG(("%d failed midpoint\n", t->id));
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_NOMATCH;
	}
	MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));

	zaptreesubs(v, t->left);
	zaptreesubs(v, t->right);
    }
}

/*
 - crevcondissect - dissect match for concatenation node, shortest-first



 ^ static int crevcondissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
crevcondissect(
    struct vars *const v,
    struct subre *const t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    struct dfa *d, *d2;
    chr *mid;

    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);





    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(("crevcon %d\n", t->id));

    /*
     * Pick a tentative midpoint.
     */


    mid = shortest(v, d, begin, begin, end, (chr **) NULL, (int *) NULL);
    if (mid == NULL) {
	freeDFA(d);
	freeDFA(d2);
	return REG_NOMATCH;
    }
    MDEBUG(("tentative midpoint %ld\n", LOFF(mid)));






    /*
     * Iterate until satisfaction or failure.
     */

    for (;;) {
	/*
	 * Try this midpoint on for size.
	 */

	if (longest(v, d2, mid, end, NULL) == end) {
	    int er = cdissect(v, t->left, begin, mid);

	    if (er == REG_OKAY) {
		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_NOMATCH) {
		freeDFA(d);
		freeDFA(d2);
		return er;
	    }
	}

	/*
	 * That midpoint didn't work, find a new one.
	 */

	if (mid == end) {
	    /*
	     * All possibilities exhausted.
	     */

	    MDEBUG(("%d no midpoint\n", t->id));
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_NOMATCH;
	}
	mid = shortest(v, d, begin, mid+1, end, NULL, NULL);
	if (mid == NULL) {
	    /*
	     * Failed to find a new one.
	     */

	    MDEBUG(("%d failed midpoint\n", t->id));
	    freeDFA(d);
	    freeDFA(d2);
	    return REG_NOMATCH;
	}
	MDEBUG(("%d: new midpoint %ld\n", t->id, LOFF(mid)));

	zaptreesubs(v, t->left);
	zaptreesubs(v, t->right);
    }
}

/*
 - cbrdissect - dissect match for backref node
 ^ static int cbrdissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
cbrdissect(
    struct vars *const v,
    struct subre *const t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    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->id, n, min, max));

    /* get the backreferenced string */
    if (v->pmatch[n].rm_so == -1) {
	return REG_NOMATCH;
    }
    brstring = v->start + v->pmatch[n].rm_so;
    brlen = v->pmatch[n].rm_eo - v->pmatch[n].rm_so;

    /* special cases for zero-length strings */
    if (brlen == 0) {
	/*

	 * matches only if target is zero length, but any number of
	 * repetitions can be considered to be present
	 */
	if (begin == end && min <= max) {

	    MDEBUG(("cbackref matched trivially\n"));
	    return REG_OKAY;
	}

	return REG_NOMATCH;



    }

    if (begin == end) {
	/* matches only if zero repetitions are okay */
	if (min == 0) {
	    MDEBUG(("cbackref matched trivially\n"));
	    return REG_OKAY;
	}
	return REG_NOMATCH;
    }

    /*
     * check target length to see if it could possibly be an allowed number of
     * repetitions of brstring
     */

    assert(end > begin);
    tlen = end - begin;
    if (tlen % brlen != 0)
	return REG_NOMATCH;

    numreps = tlen / brlen;
    if (numreps < min || (numreps > max && max != DUPINF))

	return REG_NOMATCH;


    /* okay, compare the actual string contents */
    p = begin;
    while (numreps-- > 0) {
	if ((*v->g->compare) (brstring, p, brlen) != 0)
	    return REG_NOMATCH;

	p += brlen;


    }








    MDEBUG(("cbackref matched\n"));
    return REG_OKAY;
}



/*
 - caltdissect - dissect match for alternation node

 ^ static int caltdissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
caltdissect(
    struct vars *const v,
    struct subre *t,
    chr *const begin,		/* beginning of relevant substring */
    chr *const end)		/* end of same */
{
    struct dfa *d;
    int er;

    /* We loop, rather than tail-recurse, to handle a chain of alternatives */
    while (t != NULL) {
	assert(t->op == '|');
	assert(t->left != NULL && t->left->cnfa.nstates > 0);

	MDEBUG(("calt n%d\n", t->id));

	d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
	NOERR();
	if (longest(v, d, begin, end, (int *) NULL) == end) {
	    freeDFA(d);
	    MDEBUG(("calt matched\n"));
	    er = cdissect(v, t->left, begin, end);
	    if (er != REG_NOMATCH) {
		return er;
	    }

	}
	freeDFA(d);

	t = t->right;
    }

    return REG_NOMATCH;
}

/*
 - citerdissect - dissect match for iteration node
 ^ static int citerdissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
citerdissect(struct vars * v,
	     struct subre * t,
	     chr *begin,	/* beginning of relevant substring */
	     chr *end)		/* end of same */
{
    struct dfa *d;
    chr	  **endpts;
    chr	   *limit;
    int		min_matches;
    size_t	max_matches;
    int		nverified;
    int		k;
    int		i;
    int		er;

    assert(t->op == '*');
    assert(t->left != NULL && t->left->cnfa.nstates > 0);
    assert(!(t->left->flags & SHORTER));
    assert(begin <= end);

    /*
     * 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;
    }

    /*
     * We need workspace to track the endpoints of each sub-match.  Normally
     * we consider only nonzero-length sub-matches, so there can be at most
     * end-begin of them.  However, if min is larger than that, we will also
     * consider zero-length sub-matches in order to find enough matches.
     *
     * For convenience, endpts[0] contains the "begin" pointer and we store
     * sub-match endpoints in endpts[1..max_matches].
     */
    max_matches = end - begin;
    if (max_matches > t->max && t->max != DUPINF)
	max_matches = t->max;
    if (max_matches < min_matches)
	max_matches = min_matches;
    endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *));
    if (endpts == NULL)
	return REG_ESPACE;
    endpts[0] = begin;

    d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
    if (ISERR()) {
	FREE(endpts);
	return v->err;
    }
    MDEBUG(("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 (k >= max_matches) {
		/* must try to shorten some previous match */
		k--;
		goto backtrack;
	    }

	    /* reject zero-length match unless necessary to achieve min */
	    if (endpts[k] == endpts[k - 1] &&
		(k >= min_matches || min_matches - k < end - endpts[k]))
		goto backtrack;

	    k++;
	    limit = end;
	    continue;
	}

	/*
	 * We've identified a way to divide the string into k sub-matches
	 * that works so far as the child DFA can tell.  If k is an allowed
	 * number of matches, start the slow part: recurse to verify each
	 * sub-match.  We always have k <= max_matches, needn't check that.
	 */
	if (k < min_matches)
	    goto backtrack;

	MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));

	for (i = nverified + 1; i <= k; i++) {
	    zaptreesubs(v, t->left);
	    er = cdissect(v, t->left, endpts[i - 1], endpts[i]);
	    if (er == REG_OKAY) {
		nverified = i;
		continue;
	    }
	    if (er == REG_NOMATCH)
		break;
	    /* oops, something failed */
	    freeDFA(d);
	    FREE(endpts);
	    return er;
	}

	if (i > k) {
	    /* satisfaction */
	    MDEBUG(("%d successful\n", t->id));
	    freeDFA(d);
	    FREE(endpts);
	    return REG_OKAY;
	}

	/* match failed to verify, so backtrack */

    backtrack:
	/*
	 * Must consider shorter versions of the current sub-match.  However,
	 * we'll only ask for a zero-length match if necessary.
	 */
	while (k > 0) {
	    chr	   *prev_end = endpts[k - 1];

	    if (endpts[k] > prev_end) {
		limit = endpts[k] - 1;
		if (limit > prev_end ||
		    (k < min_matches && min_matches - k >= end - prev_end)) {
		    /* break out of backtrack loop, continue the outer one */
		    break;
		}

	    }
	    /* can't shorten k'th sub-match any more, consider previous one */
	    k--;
	}
    }

    /* all possibilities exhausted */
    MDEBUG(("%d failed\n", t->id));
    freeDFA(d);
    FREE(endpts);
    return REG_NOMATCH;
}

/*
 - creviterdissect - dissect match for iteration node, shortest-first
 ^ static int creviterdissect(struct vars *, struct subre *, chr *, chr *);
 */
static int			/* regexec return code */
creviterdissect(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);

    /*
     * 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;
    }

    /*
     * We need workspace to track the endpoints of each sub-match.  Normally
     * we consider only nonzero-length sub-matches, so there can be at most
     * end-begin of them.  However, if min is larger than that, we will also
     * consider zero-length sub-matches in order to find enough matches.
     *
     * For convenience, endpts[0] contains the "begin" pointer and we store
     * sub-match endpoints in endpts[1..max_matches].
     */
    max_matches = end - begin;
    if (max_matches > t->max && t->max != DUPINF)
	max_matches = t->max;
    if (max_matches < min_matches)
	max_matches = min_matches;
    endpts = (chr **) MALLOC((max_matches + 1) * sizeof(chr *));
    if (endpts == NULL)
	return REG_ESPACE;
    endpts[0] = begin;

    d = newDFA(v, &t->left->cnfa, &v->g->cmap, DOMALLOC);
    if (ISERR()) {
	FREE(endpts);
	return v->err;
    }
    MDEBUG(("creviter %d\n", t->id));

    /*
     * 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 = begin;

    /* iterate until satisfaction or failure */
    while (k > 0) {
	/* disallow zero-length match unless necessary to achieve min */
	if (limit == endpts[k - 1] &&
	    limit != end &&
	    (k >= min_matches || min_matches - k < end - limit))
	    limit++;

	/* if this is the last allowed sub-match, it must reach to the end */
	if (k >= max_matches)
	    limit = end;

	/* try to find an endpoint for the k'th sub-match */
	endpts[k] = shortest(v, d, endpts[k - 1], limit, end,
			     (chr **) NULL, (int *) NULL);
	if (endpts[k] == NULL) {
	    /* no match possible, so see if we can lengthen previous one */
	    k--;
	    goto backtrack;
	}
	MDEBUG(("%d: working endpoint %d: %ld\n",
		t->id, k, LOFF(endpts[k])));

	/* k'th sub-match can no longer be considered verified */
	if (nverified >= k)
	    nverified = k - 1;

	if (endpts[k] != end) {
	    /* haven't reached end yet, try another iteration if allowed */
	    if (k >= max_matches) {
		/* must try to lengthen some previous match */
		k--;
		goto backtrack;
	    }

	    k++;
	    limit = endpts[k - 1];
	    continue;
	}

	/*
	 * We've identified a way to divide the string into k sub-matches
	 * that works so far as the child DFA can tell.  If k is an allowed
	 * number of matches, start the slow part: recurse to verify each
	 * sub-match.  We always have k <= max_matches, needn't check that.
	 */
	if (k < min_matches)
	    goto backtrack;

	MDEBUG(("%d: verifying %d..%d\n", t->id, nverified + 1, k));

	for (i = nverified + 1; i <= k; i++) {
	    zaptreesubs(v, t->left);
	    er = cdissect(v, t->left, endpts[i - 1], endpts[i]);
	    if (er == REG_OKAY) {
		nverified = i;
		continue;
	    }
	    if (er == REG_NOMATCH)
		break;
	    /* oops, something failed */
	    freeDFA(d);
	    FREE(endpts);
	    return er;
	}

	if (i > k) {
	    /* satisfaction */
	    MDEBUG(("%d successful\n", t->id));
	    freeDFA(d);
	    FREE(endpts);
	    return REG_OKAY;
	}

	/* match failed to verify, so backtrack */

    backtrack:
	/*
	 * Must consider 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--;
	}
    }

    /* all possibilities exhausted */
    MDEBUG(("%d failed\n", t->id));
    freeDFA(d);
    FREE(endpts);
    return REG_NOMATCH;
}

#include "rege_dfa.c"

/*
 * Local Variables:
 * mode: c
 * c-basic-offset: 4
 * fill-column: 78
 * End:
 */

#ifndef REG_MAX_STATES
#   define REG_MAX_STATES	100000
#endif

/*
 * 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;			/* see type codes above */

    char flags;
#define	LONGER	01		/* prefers longer match */
#define	SHORTER	02		/* prefers shorter match */
#define	MIXED	04		/* mixed preference below */
#define	CAP	010		/* capturing parens below */
#define	BACKR	020		/* back reference below */
#define	INUSE	0100		/* in use in final tree */
#define	NOPROP	03		/* bits which may not propagate up */
#define	LMIX(f)	((f)<<2)	/* LONGER -> MIXED */
#define	SMIX(f)	((f)<<1)	/* SHORTER -> MIXED */
#define	UP(f)	(((f)&~NOPROP) | (LMIX(f) & SMIX(f) & MIXED))
#define	MESSY(f)	((f)&(MIXED|CAP|BACKR))
#define	PREF(f)	((f)&NOPROP)
#define	PREF2(f1, f2)	((PREF(f1) != 0) ? PREF(f1) : PREF(f2))
#define	COMBINE(f1, f2)	(UP((f1)|(f2)) | PREF2(f1, f2))
    short id;			/* ID of subre (1..ntree) */
    int subno;			/* subexpression number (for 'b' and '(') */
    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... */
    struct state *end;		/* ...ending in inarcs here */
    struct cnfa cnfa;		/* compacted NFA, if any */
    struct subre *chain;	/* for bookkeeping and error cleanup */
};

expectMatch	14.16 RP	{a([bc])\1*}	ab	ab	b
expectMatch	14.17 RP	{a([bc])(\1*)}	ab	ab	b	""
expectError	14.18 -		{a((b)\1)}	ESUBREG
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
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"
# initial zero is always octal
expectMatch	15.1  MP	"a\\010b"	"a\bb"	"a\bb"
expectMatch	15.2  MP	"a\\0070b"	"a\0070b"	"a\0070b"
expectMatch	15.3  MP	"a\\07b"	"a\007b"	"a\007b"

expectIndices	21.28 Q		"a(b){2,3}c"	xabbbcy	{1 5}	{4 4}
expectIndices	21.29 Q		"a(b){2,3}c"	xabbcy	{1 4}	{3 3}
expectNomatch	21.30 Q		"a(b){2,3}c"	xabcy
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"
# again ugh
expectMatch	22.1  &+L	{a[c]e}		ace	ace
expectNomatch	22.2  &+IL	{a[c]h}		ach
expectMatch	22.3  &+L	{a[[.ch.]]}	ach	ach

expectMatch	24.6  PT	ab??c		abc	abc
expectMatch	24.7  PQT	"ab{2,4}?"	abbbb	abb
expectMatch	24.8  PQT	"ab{2,4}?c"	abbbbc	abbbbc
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"
# this is very incomplete as yet
# should include |
expectMatch	25.1 PNT	{^(.*?)(a*)$}	"xyza"	xyza	xyz	a
expectMatch	25.2 PNT	{^(.*?)(a*)$}	"xyzaa"	xyzaa	xyz	aa