regc_nfa.c

从一个开源软件中摘取的正则表达式模块

/*
 * NFA utilities.
 * This file is #included by regcomp.c.
 *
 * Copyright (c) 1998, 1999 Henry Spencer.	All rights reserved.
 *
 * Development of this software was funded, in part, by Cray Research Inc.,
 * UUNET Communications Services Inc., Sun Microsystems Inc., and Scriptics
 * Corporation, none of whom are responsible for the results.  The author
 * thanks all of them.
 *
 * Redistribution and use in source and binary forms -- with or without
 * modification -- are permitted for any purpose, provided that
 * redistributions in source form retain this entire copyright notice and
 * indicate the origin and nature of any modifications.
 *
 * I'd appreciate being given credit for this package in the documentation
 * of software which uses it, but that is not a requirement.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
 * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY
 * AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL
 * HENRY SPENCER BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * $PostgreSQL: pgsql/src/backend/regex/regc_nfa.c,v 1.5 2008/01/03 20:47:55 tgl Exp $
 *
 *
 * One or two things that technically ought to be in here
 * are actually in color.c, thanks to some incestuous relationships in
 * the color chains.
 */

#define NISERR()	VISERR(nfa->v)
#define NERR(e)		VERR(nfa->v, (e))


/*
 * newnfa - set up an NFA
 */
static struct nfa *				/* the NFA, or NULL */
newnfa(struct vars * v, struct colormap * cm, struct nfa * parent)		/* NULL if primary NFA */
{
	struct nfa *nfa;

	nfa = (struct nfa *) MALLOC(sizeof(struct nfa));
	if (nfa == NULL)
		return NULL;

	nfa->states = NULL;
	nfa->slast = NULL;
	nfa->free = NULL;
	nfa->nstates = 0;
	nfa->cm = cm;
	nfa->v = v;
	nfa->size = 0;
	nfa->bos[0] = nfa->bos[1] = COLORLESS;
	nfa->eos[0] = nfa->eos[1] = COLORLESS;
	nfa->parent = parent;		/* Precedes newfstate so parent is valid. */
	nfa->post = newfstate(nfa, '@');	/* number 0 */
	nfa->pre = newfstate(nfa, '>');		/* number 1 */

	nfa->init = newstate(nfa);	/* may become invalid later */
	nfa->final = newstate(nfa);
	if (ISERR())
	{
		freenfa(nfa);
		return NULL;
	}
	rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->pre, nfa->init);
	newarc(nfa, '^', 1, nfa->pre, nfa->init);
	newarc(nfa, '^', 0, nfa->pre, nfa->init);
	rainbow(nfa, nfa->cm, PLAIN, COLORLESS, nfa->final, nfa->post);
	newarc(nfa, '$', 1, nfa->final, nfa->post);
	newarc(nfa, '$', 0, nfa->final, nfa->post);

	if (ISERR())
	{
		freenfa(nfa);
		return NULL;
	}
	return nfa;
}

/*
 * TooManyStates - checks if the max states exceeds the compile-time value
 */
static int
TooManyStates(struct nfa *nfa)
{
	struct nfa *parent = nfa->parent;
	size_t		sz = nfa->size;

	while (parent != NULL)
	{
		sz = parent->size;
		parent = parent->parent;
	}
	if (sz > REG_MAX_STATES)
		return 1;
	return 0;
}

/*
 * IncrementSize - increases the tracked size of the NFA and its parents.
 */
static void
IncrementSize(struct nfa *nfa)
{
	struct nfa *parent = nfa->parent;

	nfa->size++;
	while (parent != NULL)
	{
		parent->size++;
		parent = parent->parent;
	}
}

/*
 * DecrementSize - decreases the tracked size of the NFA and its parents.
 */
static void
DecrementSize(struct nfa *nfa)
{
	struct nfa *parent = nfa->parent;

	nfa->size--;
	while (parent != NULL)
	{
		parent->size--;
		parent = parent->parent;
	}
}

/*
 * freenfa - free an entire NFA
 */
static void
freenfa(struct nfa * nfa)
{
	struct state *s;

	while ((s = nfa->states) != NULL)
	{
		s->nins = s->nouts = 0; /* don't worry about arcs */
		freestate(nfa, s);
	}
	while ((s = nfa->free) != NULL)
	{
		nfa->free = s->next;
		destroystate(nfa, s);
	}

	nfa->slast = NULL;
	nfa->nstates = -1;
	nfa->pre = NULL;
	nfa->post = NULL;
	FREE(nfa);
}

/*
 * newstate - allocate an NFA state, with zero flag value
 */
static struct state *			/* NULL on error */
newstate(struct nfa * nfa)
{
	struct state *s;

	if (TooManyStates(nfa))
	{
		NERR(REG_ETOOBIG);
		return NULL;
	}
	if (nfa->free != NULL)
	{
		s = nfa->free;
		nfa->free = s->next;
	}
	else
	{
		s = (struct state *) MALLOC(sizeof(struct state));
		if (s == NULL)
		{
			NERR(REG_ESPACE);
			return NULL;
		}
		s->oas.next = NULL;
		s->free = NULL;
		s->noas = 0;
	}

	assert(nfa->nstates >= 0);
	s->no = nfa->nstates++;
	s->flag = 0;
	if (nfa->states == NULL)
		nfa->states = s;
	s->nins = 0;
	s->ins = NULL;
	s->nouts = 0;
	s->outs = NULL;
	s->tmp = NULL;
	s->next = NULL;
	if (nfa->slast != NULL)
	{
		assert(nfa->slast->next == NULL);
		nfa->slast->next = s;
	}
	s->prev = nfa->slast;
	nfa->slast = s;
	/* track the current size and the parent size */
	IncrementSize(nfa);
	return s;
}

/*
 * newfstate - allocate an NFA state with a specified flag value
 */
static struct state *			/* NULL on error */
newfstate(struct nfa * nfa, int flag)
{
	struct state *s;

	s = newstate(nfa);
	if (s != NULL)
		s->flag = (char) flag;
	return s;
}

/*
 * dropstate - delete a state's inarcs and outarcs and free it
 */
static void
dropstate(struct nfa * nfa,
		  struct state * s)
{
	struct arc *a;

	while ((a = s->ins) != NULL)
		freearc(nfa, a);
	while ((a = s->outs) != NULL)
		freearc(nfa, a);
	freestate(nfa, s);
}

/*
 * freestate - free a state, which has no in-arcs or out-arcs
 */
static void
freestate(struct nfa * nfa,
		  struct state * s)
{
	assert(s != NULL);
	assert(s->nins == 0 && s->nouts == 0);

	s->no = FREESTATE;
	s->flag = 0;
	if (s->next != NULL)
		s->next->prev = s->prev;
	else
	{
		assert(s == nfa->slast);
		nfa->slast = s->prev;
	}
	if (s->prev != NULL)
		s->prev->next = s->next;
	else
	{
		assert(s == nfa->states);
		nfa->states = s->next;
	}
	s->prev = NULL;
	s->next = nfa->free;		/* don't delete it, put it on the free list */
	nfa->free = s;
	DecrementSize(nfa);
}

/*
 * destroystate - really get rid of an already-freed state
 */
static void
destroystate(struct nfa * nfa,
			 struct state * s)
{
	struct arcbatch *ab;
	struct arcbatch *abnext;

	assert(s->no == FREESTATE);
	for (ab = s->oas.next; ab != NULL; ab = abnext)
	{
		abnext = ab->next;
		FREE(ab);
	}
	s->ins = NULL;
	s->outs = NULL;
	s->next = NULL;
	FREE(s);
}

/*
 * newarc - set up a new arc within an NFA
 */
static void
newarc(struct nfa * nfa,
	   int t,
	   pcolor co,
	   struct state * from,
	   struct state * to)
{
	struct arc *a;

	assert(from != NULL && to != NULL);

	/* check for duplicates */
	for (a = from->outs; a != NULL; a = a->outchain)
		if (a->to == to && a->co == co && a->type == t)
			return;

	a = allocarc(nfa, from);
	if (NISERR())
		return;
	assert(a != NULL);

	a->type = t;
	a->co = (color) co;
	a->to = to;
	a->from = from;

	/*
	 * Put the new arc on the beginning, not the end, of the chains. Not only
	 * is this easier, it has the very useful side effect that deleting the
	 * most-recently-added arc is the cheapest case rather than the most
	 * expensive one.
	 */
	a->inchain = to->ins;
	to->ins = a;
	a->outchain = from->outs;
	from->outs = a;

	from->nouts++;
	to->nins++;

	if (COLORED(a) && nfa->parent == NULL)
		colorchain(nfa->cm, a);

	return;
}

/*
 * allocarc - allocate a new out-arc within a state
 */
static struct arc *				/* NULL for failure */
allocarc(struct nfa * nfa,
		 struct state * s)
{
	struct arc *a;
	struct arcbatch *new;
	int			i;

	/* shortcut */
	if (s->free == NULL && s->noas < ABSIZE)
	{
		a = &s->oas.a[s->noas];
		s->noas++;
		return a;
	}

	/* if none at hand, get more */
	if (s->free == NULL)
	{
		new = (struct arcbatch *) MALLOC(sizeof(struct arcbatch));
		if (new == NULL)
		{
			NERR(REG_ESPACE);
			return NULL;
		}
		new->next = s->oas.next;
		s->oas.next = new;

		for (i = 0; i < ABSIZE; i++)
		{
			new->a[i].type = 0;
			new->a[i].freechain = &new->a[i + 1];
		}
		new->a[ABSIZE - 1].freechain = NULL;
		s->free = &new->a[0];
	}
	assert(s->free != NULL);

	a = s->free;
	s->free = a->freechain;
	return a;
}

/*
 * freearc - free an arc
 */
static void
freearc(struct nfa * nfa,
		struct arc * victim)
{
	struct state *from = victim->from;
	struct state *to = victim->to;
	struct arc *a;

	assert(victim->type != 0);

	/* take it off color chain if necessary */
	if (COLORED(victim) && nfa->parent == NULL)
		uncolorchain(nfa->cm, victim);

	/* take it off source's out-chain */
	assert(from != NULL);
	assert(from->outs != NULL);
	a = from->outs;
	if (a == victim)			/* simple case:  first in chain */
		from->outs = victim->outchain;
	else
	{
		for (; a != NULL && a->outchain != victim; a = a->outchain)
			continue;
		assert(a != NULL);
		a->outchain = victim->outchain;
	}
	from->nouts--;

	/* take it off target's in-chain */
	assert(to != NULL);
	assert(to->ins != NULL);
	a = to->ins;
	if (a == victim)			/* simple case:  first in chain */
		to->ins = victim->inchain;
	else
	{
		for (; a != NULL && a->inchain != victim; a = a->inchain)
			continue;
		assert(a != NULL);
		a->inchain = victim->inchain;
	}
	to->nins--;

	/* clean up and place on free list */
	victim->type = 0;
	victim->from = NULL;		/* precautions... */
	victim->to = NULL;
	victim->inchain = NULL;
	victim->outchain = NULL;
	victim->freechain = from->free;
	from->free = victim;
}

/*
 * 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 * s,
		int type,
		pcolor co)
{
	struct arc *a;

	for (a = s->outs; a != NULL; a = a->outchain)
		if (a->type == type && a->co == co)
			return a;
	return NULL;
}

/*
 * cparc - allocate a new arc within an NFA, copying details from old one
 */
static void
cparc(struct nfa * nfa,
	  struct arc * oa,
	  struct state * from,
	  struct state * to)
{
	newarc(nfa, oa->type, oa->co, from, to);
}

/*
 * moveins - move all in arcs of a state to another state
 *
 * You might think this could be done better by just updating the
 * existing arcs, and you would be right if it weren't for the desire
 * for duplicate suppression, which makes it easier to just make new
 * ones to exploit the suppression built into newarc.
 */
static void
moveins(struct nfa * nfa,
		struct state * old,
		struct state * new)
{
	struct arc *a;

	assert(old != new);

	while ((a = old->ins) != NULL)
	{
		cparc(nfa, a, a->from, new);
		freearc(nfa, a);
	}
	assert(old->nins == 0);
	assert(old->ins == NULL);
}

/*
 * copyins - copy all in arcs of a state to another state
 */
static void
copyins(struct nfa * nfa,
		struct state * old,
		struct state * new)
{
	struct arc *a;

	assert(old != new);

	for (a = old->ins; a != NULL; a = a->inchain)
		cparc(nfa, a, a->from, new);
}

/*
 * moveouts - move all out arcs of a state to another state
 */
static void
moveouts(struct nfa * nfa,
		 struct state * old,
		 struct state * new)
{
	struct arc *a;

	assert(old != new);

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

/*
 * copyouts - copy all out arcs of a state to another state
 */
static void
copyouts(struct nfa * nfa,
		 struct state * old,
		 struct state * new)
{