Tcl Source Code

2013-03-06  Don Porter  <[email protected]>

	* generic/regc_nfa.c:	[Bugs 3604074,3606683] Rewrite of the
	* generic/regcomp.c:	fixempties() routine (and supporting
	routines) to completely eliminate the infinite loop hazard.
	Thanks to Tom Lane for the much improved solution.

2013-03-04  Don Porter  <[email protected]>

	* generic/tclUtil.c:	New scheme for keeping the per-process
	tcl_precision value in sync without the need for mutex locks on
	every read.  Uses adapted ProcessGlobalValue machinery backported
	from Tcl 8.5 where it's been working without reported problems.
	Thanks to Phil Brooks for reporting on tests which highlight the

	victim->from = NULL;		/* precautions... */
	victim->to = NULL;
	victim->inchain = NULL;
	victim->outchain = NULL;
	victim->freechain = from->free;
	from->free = victim;
}

/*
 - hasnonemptyout - Does state have a non-EMPTY out arc?
 ^ static int hasnonemptyout(struct state *);
 */
static int
hasnonemptyout(s)
struct state *s;
{
	struct arc *a;

	for (a = s->outs; a != NULL; a = a->outchain)
		if (a->type != EMPTY)
			return 1;
	return 0;
}

/*
 - nonemptyouts - count non-EMPTY out arcs of a state
 ^ static int nonemptyouts(struct state *);
 */
static int
nonemptyouts(s)
struct state *s;
{
	int n = 0;
	struct arc *a;

	for (a = s->outs; a != NULL; a = a->outchain)
		if (a->type != EMPTY)
			n++;
	return n;
}

/*
 - nonemptyins - count non-EMPTY in arcs of a state
 ^ static int nonemptyins(struct state *);
 */
static int
nonemptyins(s)
struct state *s;
{
	int n = 0;
	struct arc *a;

	for (a = s->ins; a != NULL; a = a->inchain)
		if (a->type != EMPTY)
			n++;
	return n;
}

/*
 - findarc - find arc, if any, from given source with given type and color
 * If there is more than one such arc, the result is random.
 ^ static struct arc *findarc(struct state *, int, pcolor);
 */
static struct arc *

		freearc(nfa, a);
	}
	assert(old->nins == 0);
	assert(old->ins == NULL);
}

/*
 - copyins - copy in arcs of a state to another state
 * Either all arcs, or only non-empty ones as determined by all value.
 ^ static VOID copyins(struct nfa *, struct state *, struct state *, int);
 */
static VOID
copyins(nfa, old, new, all)
struct nfa *nfa;
struct state *old;
struct state *new;
int all;
{
	struct arc *a;

	assert(old != new);

	for (a = old->ins; a != NULL; a = a->inchain)
		if (all || a->type != EMPTY)
			cparc(nfa, a, a->from, new);
}

/*
 - moveouts - move all out arcs of a state to another state
 ^ static VOID moveouts(struct nfa *, struct state *, struct state *);
 */
static VOID

	while ((a = old->outs) != NULL) {
		cparc(nfa, a, new, a->to);
		freearc(nfa, a);
	}
}

/*
 - copyouts - copy out arcs of a state to another state
 * Either all arcs, or only non-empty ones as determined by all value.
 ^ static VOID copyouts(struct nfa *, struct state *, struct state *, int);
 */
static VOID
copyouts(nfa, old, new, all)
struct nfa *nfa;
struct state *old;
struct state *new;
int all;
{
	struct arc *a;

	assert(old != new);

	for (a = old->outs; a != NULL; a = a->outchain)
		if (all || a->type != EMPTY)
			cparc(nfa, a, new, a->to);
}

/*
 - cloneouts - copy out arcs of a state to another state pair, modifying type
 ^ static VOID cloneouts(struct nfa *, struct state *, struct state *,
 ^ 	struct state *, int);
 */

	/* first, clone from state if necessary to avoid other outarcs */
	if (from->nouts > 1) {
		s = newstate(nfa);
		if (NISERR())
			return 0;
		assert(to != from);		/* con is not an inarc */
		copyins(nfa, from, s, 1);	/* duplicate inarcs */
		cparc(nfa, con, s, to);		/* move constraint arc */
		freearc(nfa, con);
		from = s;
		con = from->outs;
	}
	assert(from->nouts == 1);

	}

	/* first, clone to state if necessary to avoid other inarcs */
	if (to->nins > 1) {
		s = newstate(nfa);
		if (NISERR())
			return 0;
		copyouts(nfa, to, s, 1);	/* duplicate outarcs */
		cparc(nfa, con, from, s);	/* move constraint */
		freearc(nfa, con);
		to = s;
		con = to->ins;
	}
	assert(to->nins == 1);

 */
static VOID
fixempties(nfa, f)
struct nfa *nfa;
FILE *f;			/* for debug output; NULL none */
{
	struct state *s;
	struct state *s2;
	struct state *nexts;
	struct arc *a;
	struct arc *nexta;


	/*
	 * First, get rid of any states whose sole out-arc is an EMPTY,
	 * since they're basically just aliases for their successor.
	 * The parsing algorithm creates enough of these that it's worth
	 * special-casing this.
	 */
	for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
		nexts = s->next;
		if (s->flag || s->nouts != 1)
			continue;
		a = s->outs;
		assert(a != NULL && a->outchain == NULL);
		if (a->type != EMPTY)
			continue;
		if (s != a->to)
			moveins(nfa, s, a->to);
		dropstate(nfa, s);
	}

	/*
	 * Similarly, get rid of any state with a single EMPTY in-arc,
	 * by folding it into its predecessor.
	 */
	for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
		nexts = s->next;
		/* Ensure tmp fields are clear for next step */
		assert(s->tmp = NULL);
		if (s->flag || s->nins != 1)
			continue;
		a = s->ins;
		assert(a != NULL && a->inchain == NULL);
		if (a->type != EMPTY)
			continue;
		if (s != a->from)
			moveouts(nfa, s, a->from);
		dropstate(nfa, s);
	}

	/*
	 * For each remaining NFA state, find all other states that are
	 * reachable from it by a chain of one or more EMPTY arcs.  Then
	 * generate new arcs that eliminate the need for each such chain.
	 *
	 * If we just do this straightforwardly, the algorithm gets slow
	 * in complex graphs, because the same arcs get copied to all
	 * intermediate states of an EMPTY chain, and then uselessly
	 * pushed repeatedly to the chain's final state; we waste a lot
	 * of time in newarc's duplicate checking.  To improve matters,
	 * we decree that any state with only EMPTY out-arcs is "doomed"
	 * and will not be part of the final NFA. That can be ensured by
	 * not adding any new out-arcs to such a state. Having ensured
	 * that, we need not update the state's in-arcs list either; all
	 * arcs that might have gotten pushed forward to it will just get
	 * pushed directly to successor states.  This eliminates most of
	 * the useless duplicate arcs.
	 */
	for (s = nfa->states; s != NULL && !NISERR(); s = s->next) {
		for (s2 = emptyreachable(s, s); s2 != s && !NISERR();
				s2 = nexts) {
			/*
			 * If s2 is doomed, we decide that (1) we will
			 * always push arcs forward to it, not pull them
			 * back to s; and (2) we can optimize away the

			 * push-forward, per comment above.
			 * So do nothing.


			 */
			if (s2->flag || hasnonemptyout(s2))

				replaceempty(nfa, s, s2);

			/* Reset the tmp fields as we walk back */
			nexts = s2->tmp;
			s2->tmp = NULL;


		}
		s->tmp = NULL;
	}

	/*
	 * Remove all the EMPTY arcs, since we don't need them anymore.
	 */
	for (s = nfa->states; s != NULL; s = s->next)
		for (a = s->outs; a != NULL; a = nexta) {
			nexta = a->outchain;
			if (a->type == EMPTY)
				freearc(nfa, a);
		}




	/*
	 * And remove any states that have become useless.  (This
	 * cleanup is not very thorough, and would be even less so if we
	 * tried to combine it with the previous step; but cleanup()
	 * will take care of anything we miss.)
	 */
	for (s = nfa->states; s != NULL && !NISERR(); s = nexts) {
		nexts = s->next;
		if ((s->nins == 0 || s->nouts == 0) && !s->flag)
			dropstate(nfa, s);
	}

	if (f != NULL && !NISERR())
		dumpnfa(nfa, f);
}

/*
 - emptyreachable - recursively find all states reachable from s by EMPTY arcs

 * The return value is the last such state found.  Its tmp field links back
 * to the next-to-last such state, and so on back to s, so that all these
 * states can be located without searching the whole NFA.
 * The maximum recursion depth here is equal to the length of the longest
 * loop-free chain of EMPTY arcs, which is surely no more than the size of
 * the NFA, and in practice will be a lot less than that.
 ^ static struct state *emptyreachable(struct state *, struct state *);
 */
static struct state *
emptyreachable(s, lastfound)
struct state *s;
struct state *lastfound;
{

	struct arc *a;

	s->tmp = lastfound;
	lastfound = s;
	for (a = s->outs; a != NULL; a = a->outchain)
		if (a->type == EMPTY && a->to->tmp == NULL)

			lastfound = emptyreachable(a->to, lastfound);


	return lastfound;
}

/*
 - replaceempty - replace an EMPTY arc chain with some non-empty arcs
 * The EMPTY arc(s) should be deleted later, but we can't do it here because
 * they may still be needed to identify other arc chains during fixempties().
 ^ static void replaceempty(struct nfa *, struct state *, struct state *);
 */
static VOID
replaceempty(nfa, from, to)
struct nfa *nfa;
struct state *from;
struct state *to;
{
	int fromouts;
	int toins;

	assert(from != to);

	/*
	 * Create replacement arcs that bypass the need for the EMPTY
	 * chain.  We can do this either by pushing arcs forward
	 * (linking directly from predecessors of "from" to "to") or by
	 * pulling them back (linking directly from "from" to the
	 * successors of "to").  In general, we choose whichever way
	 * creates greater fan-out or fan-in, so as to improve the odds
	 * of reducing the other state to zero in-arcs or out-arcs and
	 * thereby being able to delete it.  However, if "from" is
	 * doomed (has no non-EMPTY out-arcs), we must keep it so, so
	 * always push forward in that case.
	 *
	 * The fan-out/fan-in comparison should count only non-EMPTY
	 * arcs.  If "from" is doomed, we can skip counting "to"'s arcs,
	 * since we want to force taking the copyins path in that case.
	 */
	fromouts = nonemptyouts(from);
	toins = (fromouts == 0) ? 1 : nonemptyins(to);

	if (fromouts > toins) {
		copyouts(nfa, to, from, 0);
		return;
	}
	if (fromouts < toins) {
		copyins(nfa, from, to, 0);
		return;
	}

	/*
	 * fromouts == toins.  Secondary decision: copy fewest arcs.
	 *
	 * Doesn't seem to be worth the trouble to exclude empties from
	 * these comparisons; that takes extra time and doesn't seem to
	 * improve the resulting graph much.
	 */
	if (from->nins > to->nouts) {
		copyouts(nfa, to, from, 0);
		return;
	}

	copyins(nfa, from, to, 0);

}

/*
 - cleanup - clean up NFA after optimizations
 ^ static VOID cleanup(struct nfa *);
 */
static VOID

static struct state *newfstate _ANSI_ARGS_((struct nfa *, int flag));
static VOID dropstate _ANSI_ARGS_((struct nfa *, struct state *));
static VOID freestate _ANSI_ARGS_((struct nfa *, struct state *));
static VOID destroystate _ANSI_ARGS_((struct nfa *, struct state *));
static VOID newarc _ANSI_ARGS_((struct nfa *, int, pcolor, struct state *, struct state *));
static struct arc *allocarc _ANSI_ARGS_((struct nfa *, struct state *));
static VOID freearc _ANSI_ARGS_((struct nfa *, struct arc *));
static int hasnonemptyout _ANSI_ARGS_((struct state *));
static int nonemptyouts _ANSI_ARGS_((struct state *));
static int nonemptyins _ANSI_ARGS_((struct state *));
static struct arc *findarc _ANSI_ARGS_((struct state *, int, pcolor));
static VOID cparc _ANSI_ARGS_((struct nfa *, struct arc *, struct state *, struct state *));
static VOID moveins _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
static VOID copyins _ANSI_ARGS_((struct nfa *, struct state *, struct state *, int));
static VOID moveouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
static VOID copyouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *, int));
static VOID cloneouts _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *, int));
static VOID delsub _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
static VOID deltraverse _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
static VOID dupnfa _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *, struct state *));
static VOID duptraverse _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
static VOID cleartraverse _ANSI_ARGS_((struct nfa *, struct state *));
static VOID specialcolors _ANSI_ARGS_((struct nfa *));
static long optimize _ANSI_ARGS_((struct nfa *, FILE *));
static VOID pullback _ANSI_ARGS_((struct nfa *, FILE *));
static int pull _ANSI_ARGS_((struct nfa *, struct arc *));
static VOID pushfwd _ANSI_ARGS_((struct nfa *, FILE *));
static int push _ANSI_ARGS_((struct nfa *, struct arc *));
#define	INCOMPATIBLE	1	/* destroys arc */
#define	SATISFIED	2	/* constraint satisfied */
#define	COMPATIBLE	3	/* compatible but not satisfied yet */
static int combine _ANSI_ARGS_((struct arc *, struct arc *));
static VOID fixempties _ANSI_ARGS_((struct nfa *, FILE *));
static struct state *emptyreachable _ANSI_ARGS_((struct state *, struct state *));
static VOID replaceempty _ANSI_ARGS_((struct nfa *, struct state *, struct state *));
static VOID cleanup _ANSI_ARGS_((struct nfa *));
static VOID markreachable _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *));
static VOID markcanreach _ANSI_ARGS_((struct nfa *, struct state *, struct state *, struct state *));
static long analyze _ANSI_ARGS_((struct nfa *));
static VOID compact _ANSI_ARGS_((struct nfa *, struct cnfa *));
static VOID carcsort _ANSI_ARGS_((struct carc *, struct carc *));
static VOID freecnfa _ANSI_ARGS_((struct cnfa *));

			}
		}
	}

	/* do the splits */
	for (s = slist; s != NULL; s = s2) {
		s2 = newstate(nfa);
		copyouts(nfa, s, s2, 1);
		for (a = s->ins; a != NULL; a = b) {
			b = a->inchain;
			if (a->from != pre) {
				cparc(nfa, a, a->from, s2);
				freearc(nfa, a);
			}
		}