/*

 * 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.

 *

 *

 *

 * 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 *newnfa(struct vars *, struct colormap *, struct nfa *);

 */

static struct nfa *		/* the NFA, or NULL */

newnfa(v, cm, parent)

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->bos[0] = nfa->bos[1] = COLORLESS;

	nfa->eos[0] = nfa->eos[1] = COLORLESS;

	nfa->post = newfstate(nfa, '@');	/* number 0 */

	nfa->pre = newfstate(nfa, '>');		/* number 1 */

	nfa->parent = parent;

	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;

}

/*

 - freenfa - free an entire NFA

 ^ static VOID freenfa(struct nfa *);

 */

static VOID

freenfa(nfa)

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 *newstate(struct nfa *);

 */

static struct state *		/* NULL on error */

newstate(nfa)

struct nfa *nfa;

{

	struct state *s;

	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;

	return s;

}

/*

 - newfstate - allocate an NFA state with a specified flag value

 ^ static struct state *newfstate(struct nfa *, int flag);

 */

static struct state *		/* NULL on error */

newfstate(nfa, flag)

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 *, struct state *);

 */

static VOID

dropstate(nfa, s)

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 *, struct state *);

 */

static VOID

freestate(nfa, s)

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;

}

/*

 - destroystate - really get rid of an already-freed state

 ^ static VOID destroystate(struct nfa *, struct state *);

 */

static VOID

destroystate(nfa, s)

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 *, int, pcolor, struct state *, 

 ^	struct state *);

 */

static VOID

newarc(nfa, t, co, from, to)

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 *allocarc(struct nfa *, struct state *);

 */

static struct arc *		/* NULL for failure */

allocarc(nfa, s)

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 *, struct arc *);

 */

static VOID

freearc(nfa, victim)

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 *, int, pcolor);

 */

static struct arc *

findarc(s, type, co)

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 *, struct arc *, struct state *, 

 ^ 	struct state *);

 */

static VOID

cparc(nfa, oa, from, to)

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 *, struct state *, struct state *);

 */

static VOID

moveins(nfa, old, new)

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 *, struct state *, struct state *);

 */

static VOID

copyins(nfa, old, new)

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 *, struct state *, struct state *);

 */

static VOID

moveouts(nfa, old, new)

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 *, struct state *, struct state *);

 */

static VOID

copyouts(nfa, old, new)

struct nfa *nfa;

struct state *old;

struct state *new;

{

	struct arc *a;

	assert(old != new);

	for (a = old->outs; a != NULL; a = a->outchain)

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

 */

static VOID

cloneouts(nfa, old, from, to, type)

struct nfa *nfa;

struct state *old;

struct state *from;

struct state *to;