ragel-6.10/ragel/fsmgraph.cpp

/*
 *  Copyright 2001, 2002, 2006 Adrian Thurston <thurston@complang.org>
 */

/*  This file is part of Ragel.
 *
 *  Ragel is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 2 of the License, or
 *  (at your option) any later version.
 *
 *  Ragel is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with Ragel; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include <assert.h>
#include <iostream>

#include "fsmgraph.h"
#include "mergesort.h"
#include "parsedata.h"

using std::cerr;
using std::endl;

/* Make a new state. The new state will be put on the graph's
 * list of state. The new state can be created final or non final. */
StateAp *FsmAp::addState()
{
	/* Make the new state to return. */
	StateAp *state = new StateAp();

	if ( misfitAccounting ) {
		/* Create the new state on the misfit list. All states are created
		 * with no foreign in transitions. */
		misfitList.append( state );
	}
	else {
		/* Create the new state. */
		stateList.append( state );
	}

	return state;
}

/* Construct an FSM that is the concatenation of an array of characters. A new
 * machine will be made that has len+1 states with one transition between each
 * state for each integer in str. IsSigned determines if the integers are to
 * be considered as signed or unsigned ints. */
void FsmAp::concatFsm( Key *str, int len )
{
	/* Make the first state and set it as the start state. */
	StateAp *last = addState();
	setStartState( last );

	/* Attach subsequent states. */
	for ( int i = 0; i < len; i++ ) {
		StateAp *newState = addState();
		attachNewTrans( last, newState, str[i], str[i] );
		last = newState;
	}

	/* Make the last state the final state. */
	setFinState( last );
}

/* Case insensitive version of concatFsm. */
void FsmAp::concatFsmCI( Key *str, int len )
{
	/* Make the first state and set it as the start state. */
	StateAp *last = addState();
	setStartState( last );

	/* Attach subsequent states. */
	for ( int i = 0; i < len; i++ ) {
		StateAp *newState = addState();

		KeySet keySet;
		if ( str[i].isLower() )
			keySet.insert( str[i].toUpper() );
		if ( str[i].isUpper() )
			keySet.insert( str[i].toLower() );
		keySet.insert( str[i] );

		for ( int i = 0; i < keySet.length(); i++ )
			attachNewTrans( last, newState, keySet[i], keySet[i] );

		last = newState;
	}

	/* Make the last state the final state. */
	setFinState( last );
}

/* Construct a machine that matches one character.  A new machine will be made
 * that has two states with a single transition between the states. IsSigned
 * determines if the integers are to be considered as signed or unsigned ints. */
void FsmAp::concatFsm( Key chr )
{
	/* Two states first start, second final. */
	setStartState( addState() );

	StateAp *end = addState();
	setFinState( end );

	/* Attach on the character. */
	attachNewTrans( startState, end, chr, chr );
}

/* Construct a machine that matches any character in set.  A new machine will
 * be made that has two states and len transitions between the them. The set
 * should be ordered correctly accroding to KeyOps and should not contain
 * any duplicates. */
void FsmAp::orFsm( Key *set, int len )
{
	/* Two states first start, second final. */
	setStartState( addState() );

	StateAp *end = addState();
	setFinState( end );

	for ( int i = 1; i < len; i++ )
		assert( set[i-1] < set[i] );

	/* Attach on all the integers in the given string of ints. */
	for ( int i = 0; i < len; i++ )
		attachNewTrans( startState, end, set[i], set[i] );
}

/* Construct a machine that matches a range of characters.  A new machine will
 * be made with two states and a range transition between them. The range will
 * match any characters from low to high inclusive. Low should be less than or
 * equal to high otherwise undefined behaviour results.  IsSigned determines
 * if the integers are to be considered as signed or unsigned ints. */
void FsmAp::rangeFsm( Key low, Key high )
{
	/* Two states first start, second final. */
	setStartState( addState() );

	StateAp *end = addState();
	setFinState( end );

	/* Attach using the range of characters. */
	attachNewTrans( startState, end, low, high );
}

/* Construct a machine that a repeated range of characters.  */
void FsmAp::rangeStarFsm( Key low, Key high)
{
	/* One state which is final and is the start state. */
	setStartState( addState() );
	setFinState( startState );

	/* Attach start to start using range of characters. */
	attachNewTrans( startState, startState, low, high );
}

/* Construct a machine that matches the empty string.  A new machine will be
 * made with only one state. The new state will be both a start and final
 * state. IsSigned determines if the machine has a signed or unsigned
 * alphabet. Fsm operations must be done on machines with the same alphabet
 * signedness. */
void FsmAp::lambdaFsm( )
{
	/* Give it one state with no transitions making it
	 * the start state and final state. */
	setStartState( addState() );
	setFinState( startState );
}

/* Construct a machine that matches nothing at all. A new machine will be
 * made with only one state. It will not be final. */
void FsmAp::emptyFsm( )
{
	/* Give it one state with no transitions making it
	 * the start state and final state. */
	setStartState( addState() );
}

void FsmAp::transferOutData( StateAp *destState, StateAp *srcState )
{
	for ( TransList::Iter trans = destState->outList; trans.lte(); trans++ ) {
		if ( trans->toState != 0 ) {
			/* Get the actions data from the outActionTable. */
			trans->actionTable.setActions( srcState->outActionTable );

			/* Get the priorities from the outPriorTable. */
			trans->priorTable.setPriors( srcState->outPriorTable );
		}
	}
}

/* Kleene star operator. Makes this machine the kleene star of itself. Any
 * transitions made going out of the machine and back into itself will be
 * notified that they are leaving transitions by having the leavingFromState
 * callback invoked. */
void FsmAp::starOp( )
{
	/* For the merging process. */
	MergeData md;

	/* Turn on misfit accounting to possibly catch the old start state. */
	setMisfitAccounting( true );

	/* Create the new new start state. It will be set final after the merging
	 * of the final states with the start state is complete. */
	StateAp *prevStartState = startState;
	unsetStartState();
	setStartState( addState() );

	/* Merge the new start state with the old one to isolate it. */
	mergeStates( md, startState, prevStartState );

	/* Merge the start state into all final states. Except the start state on
	 * the first pass. If the start state is set final we will be doubling up
	 * its transitions, which will get transfered to any final states that
	 * follow it in the final state set. This will be determined by the order
	 * of items in the final state set. To prevent this we just merge with the
	 * start on a second pass. */
	for ( StateSet::Iter st = finStateSet; st.lte(); st++ ) {
		if ( *st != startState )
			mergeStatesLeaving( md, *st, startState );
	}

	/* Now it is safe to merge the start state with itself (provided it
	 * is set final). */
	if ( startState->isFinState() )
		mergeStatesLeaving( md, startState, startState );

	/* Now ensure the new start state is a final state. */
	setFinState( startState );

	/* Fill in any states that were newed up as combinations of others. */
	fillInStates( md );

	/* Remove the misfits and turn off misfit accounting. */
	removeMisfits();
	setMisfitAccounting( false );
}

void FsmAp::repeatOp( int times )
{
	/* Must be 1 and up. 0 produces null machine and requires deleting this. */
	assert( times > 0 );

	/* A repeat of one does absolutely nothing. */
	if ( times == 1 )
		return;

	/* Make a machine to make copies from. */
	FsmAp *copyFrom = new FsmAp( *this );

	/* Concatentate duplicates onto the end up until before the last. */
	for ( int i = 1; i < times-1; i++ ) {
		FsmAp *dup = new FsmAp( *copyFrom );
		doConcat( dup, 0, false );
	}

	/* Now use the copyFrom on the end. */
	doConcat( copyFrom, 0, false );
}

void FsmAp::optionalRepeatOp( int times )
{
	/* Must be 1 and up. 0 produces null machine and requires deleting this. */
	assert( times > 0 );

	/* A repeat of one optional merely allows zero string. */
	if ( times == 1 ) {
		setFinState( startState );
		return;
	}

	/* Make a machine to make copies from. */
	FsmAp *copyFrom = new FsmAp( *this );

	/* The state set used in the from end of the concatentation. Starts with
	 * the initial final state set, then after each concatenation, gets set to
	 * the the final states that come from the the duplicate. */
	StateSet lastFinSet( finStateSet );

	/* Set the initial state to zero to allow zero copies. */
	setFinState( startState );

	/* Concatentate duplicates onto the end up until before the last. */
	for ( int i = 1; i < times-1; i++ ) {
		/* Make a duplicate for concating and set the fin bits to graph 2 so we
		 * can pick out it's final states after the optional style concat. */
		FsmAp *dup = new FsmAp( *copyFrom );
		dup->setFinBits( STB_GRAPH2 );
		doConcat( dup, &lastFinSet, true );

		/* Clear the last final state set and make the new one by taking only
		 * the final states that come from graph 2.*/
		lastFinSet.empty();
		for ( int i = 0; i < finStateSet.length(); i++ ) {
			/* If the state came from graph 2, add it to the last set and clear
			 * the bits. */
			StateAp *fs = finStateSet[i];
			if ( fs->stateBits & STB_GRAPH2 ) {
				lastFinSet.insert( fs );
				fs->stateBits &= ~STB_GRAPH2;
			}
		}
	}

	/* Now use the copyFrom on the end, no bits set, no bits to clear. */
	doConcat( copyFrom, &lastFinSet, true );
}


/* Fsm concatentation worker. Supports treating the concatentation as optional,
 * which essentially leaves the final states of machine one as final. */
void FsmAp::doConcat( FsmAp *other, StateSet *fromStates, bool optional )
{
	/* For the merging process. */
	StateSet finStateSetCopy, startStateSet;
	MergeData md;

	/* Turn on misfit accounting for both graphs. */
	setMisfitAccounting( true );
	other->setMisfitAccounting( true );

	/* Get the other's start state. */
	StateAp *otherStartState = other->startState;

	/* Unset other's start state before bringing in the entry points. */
	other->unsetStartState();

	/* Bring in the rest of other's entry points. */
	copyInEntryPoints( other );
	other->entryPoints.empty();

	/* Bring in other's states into our state lists. */
	stateList.append( other->stateList );
	misfitList.append( other->misfitList );

	/* If from states is not set, then get a copy of our final state set before
	 * we clobber it and use it instead. */
	if ( fromStates == 0 ) {
		finStateSetCopy = finStateSet;
		fromStates = &finStateSetCopy;
	}

	/* Unset all of our final states and get the final states from other. */
	if ( !optional )
		unsetAllFinStates();
	finStateSet.insert( other->finStateSet );

	/* Since other's lists are empty, we can delete the fsm without
	 * affecting any states. */
	delete other;

	/* Merge our former final states with the start state of other. */
	for ( int i = 0; i < fromStates->length(); i++ ) {
		StateAp *state = fromStates->data[i];

		/* Merge the former final state with other's start state. */
		mergeStatesLeaving( md, state, otherStartState );

		/* If the former final state was not reset final then we must clear
		 * the state's out trans data. If it got reset final then it gets to
		 * keep its out trans data. This must be done before fillInStates gets
		 * called to prevent the data from being sourced. */
		if ( ! state->isFinState() )
			clearOutData( state );
	}

	/* Fill in any new states made from merging. */
	fillInStates( md );

	/* Remove the misfits and turn off misfit accounting. */
	removeMisfits();
	setMisfitAccounting( false );
}

/* Concatenates other to the end of this machine. Other is deleted.  Any
 * transitions made leaving this machine and entering into other are notified
 * that they are leaving transitions by having the leavingFromState callback
 * invoked. */
void FsmAp::concatOp( FsmAp *other )
{
	/* Assert same signedness and return graph concatenation op. */
	doConcat( other, 0, false );
}


void FsmAp::doOr( FsmAp *other )
{
	/* For the merging process. */
	MergeData md;

	/* Build a state set consisting of both start states */
	StateSet startStateSet;
	startStateSet.insert( startState );
	startStateSet.insert( other->startState );

	/* Both of the original start states loose their start state status. */
	unsetStartState();
	other->unsetStartState();

	/* Bring in the rest of other's entry points. */
	copyInEntryPoints( other );
	other->entryPoints.empty();

	/* Merge the lists. This will move all the states from other
	 * into this. No states will be deleted. */
	stateList.append( other->stateList );
	misfitList.append( other->misfitList );

	/* Move the final set data from other into this. */
	finStateSet.insert(other->finStateSet);
	other->finStateSet.empty();

	/* Since other's list is empty, we can delete the fsm without
	 * affecting any states. */
	delete other;

	/* Create a new start state. */
	setStartState( addState() );

	/* Merge the start states. */
	mergeStates( md, startState, startStateSet.data, startStateSet.length() );

	/* Fill in any new states made from merging. */
	fillInStates( md );
}

/* Unions other with this machine. Other is deleted. */
void FsmAp::unionOp( FsmAp *other )
{
	/* Turn on misfit accounting for both graphs. */
	setMisfitAccounting( true );
	other->setMisfitAccounting( true );

	/* Call Worker routine. */
	doOr( other );

	/* Remove the misfits and turn off misfit accounting. */
	removeMisfits();
	setMisfitAccounting( false );
}

/* Intersects other with this machine. Other is deleted. */
void FsmAp::intersectOp( FsmAp *other )
{
	/* Turn on misfit accounting for both graphs. */
	setMisfitAccounting( true );
	other->setMisfitAccounting( true );

	/* Set the fin bits on this and other to want each other. */
	setFinBits( STB_GRAPH1 );
	other->setFinBits( STB_GRAPH2 );

	/* Call worker Or routine. */
	doOr( other );

	/* Unset any final states that are no longer to
	 * be final due to final bits. */
	unsetIncompleteFinals();

	/* Remove the misfits and turn off misfit accounting. */
	removeMisfits();
	setMisfitAccounting( false );

	/* Remove states that have no path to a final state. */
	removeDeadEndStates();
}

/* Set subtracts other machine from this machine. Other is deleted. */
void FsmAp::subtractOp( FsmAp *other )
{
	/* Turn on misfit accounting for both graphs. */
	setMisfitAccounting( true );
	other->setMisfitAccounting( true );

	/* Set the fin bits of other to be killers. */
	other->setFinBits( STB_GRAPH1 );

	/* Call worker Or routine. */
	doOr( other );

	/* Unset any final states that are no longer to
	 * be final due to final bits. */
	unsetKilledFinals();

	/* Remove the misfits and turn off misfit accounting. */
	removeMisfits();
	setMisfitAccounting( false );

	/* Remove states that have no path to a final state. */
	removeDeadEndStates();
}

bool FsmAp::inEptVect( EptVect *eptVect, StateAp *state )
{
	if ( eptVect != 0 ) {
		/* Vect is there, walk it looking for state. */
		for ( int i = 0; i < eptVect->length(); i++ ) {
			if ( eptVect->data[i].targ == state )
				return true;
		}
	}
	return false;
}

/* Fill epsilon vectors in a root state from a given starting point. Epmploys
 * a depth first search through the graph of epsilon transitions. */
void FsmAp::epsilonFillEptVectFrom( StateAp *root, StateAp *from, bool parentLeaving )
{
	/* Walk the epsilon transitions out of the state. */
	for ( EpsilonTrans::Iter ep = from->epsilonTrans; ep.lte(); ep++ ) {
		/* Find the entry point, if the it does not resove, ignore it. */
		EntryMapEl *enLow, *enHigh;
		if ( entryPoints.findMulti( *ep, enLow, enHigh ) ) {
			/* Loop the targets. */
			for ( EntryMapEl *en = enLow; en <= enHigh; en++ ) {
				/* Do not add the root or states already in eptVect. */
				StateAp *targ = en->value;
				if ( targ != from && !inEptVect(root->eptVect, targ) ) {
					/* Maybe need to create the eptVect. */
					if ( root->eptVect == 0 )
						root->eptVect = new EptVect();

					/* If moving to a different graph or if any parent is
					 * leaving then we are leaving. */
					bool leaving = parentLeaving ||
							root->owningGraph != targ->owningGraph;

					/* All ok, add the target epsilon and recurse. */
					root->eptVect->append( EptVectEl(targ, leaving) );
					epsilonFillEptVectFrom( root, targ, leaving );
				}
			}
		}
	}
}

void FsmAp::shadowReadWriteStates( MergeData &md )
{
	/* Init isolatedShadow algorithm data. */
	for ( StateList::Iter st = stateList; st.lte(); st++ )
		st->isolatedShadow = 0;

	/* Any states that may be both read from and written to must
	 * be shadowed. */
	for ( StateList::Iter st = stateList; st.lte(); st++ ) {
		/* Find such states by looping through stateVect lists, which give us
		 * the states that will be read from. May cause us to visit the states
		 * that we are interested in more than once. */
		if ( st->eptVect != 0 ) {
			/* For all states that will be read from. */
			for ( EptVect::Iter ept = *st->eptVect; ept.lte(); ept++ ) {
				/* Check for read and write to the same state. */
				StateAp *targ = ept->targ;
				if ( targ->eptVect != 0 ) {
					/* State is to be written to, if the shadow is not already
					 * there, create it. */
					if ( targ->isolatedShadow == 0 ) {
						StateAp *shadow = addState();
						mergeStates( md, shadow, targ );
						targ->isolatedShadow = shadow;
					}

					/* Write shadow into the state vector so that it is the
					 * state that the epsilon transition will read from. */
					ept->targ = targ->isolatedShadow;
				}
			}
		}
	}
}

void FsmAp::resolveEpsilonTrans( MergeData &md )
{
	/* Walk the state list and invoke recursive worker on each state. */
	for ( StateList::Iter st = stateList; st.lte(); st++ )
		epsilonFillEptVectFrom( st, st, false );

	/* Prevent reading from and writing to of the same state. */
	shadowReadWriteStates( md );

	/* For all states that have epsilon transitions out, draw the transitions,
	 * clear the epsilon transitions. */
	for ( StateList::Iter st = stateList; st.lte(); st++ ) {
		/* If there is a state vector, then create the pre-merge state. */
		if ( st->eptVect != 0 ) {
			/* Merge all the epsilon targets into the state. */
			for ( EptVect::Iter ept = *st->eptVect; ept.lte(); ept++ ) {
				if ( ept->leaving )
					mergeStatesLeaving( md, st, ept->targ );
				else
					mergeStates( md, st, ept->targ );
			}

			/* Clean up the target list. */
			delete st->eptVect;
			st->eptVect = 0;
		}

		/* Clear the epsilon transitions vector. */
		st->epsilonTrans.empty();
	}
}

void FsmAp::epsilonOp()
{
	/* For merging process. */
	MergeData md;

	setMisfitAccounting( true );

	for ( StateList::Iter st = stateList; st.lte(); st++ )
		st->owningGraph = 0;

	/* Perform merges. */
	resolveEpsilonTrans( md );

	/* Epsilons can caused merges which leave behind unreachable states. */
	fillInStates( md );

	/* Remove the misfits and turn off misfit accounting. */
	removeMisfits();
	setMisfitAccounting( false );
}

/* Make a new maching by joining together a bunch of machines without making
 * any transitions between them. A negative finalId results in there being no
 * final id. */
void FsmAp::joinOp( int startId, int finalId, FsmAp **others, int numOthers )
{
	/* For the merging process. */
	MergeData md;

	/* Set the owning machines. Start at one. Zero is reserved for the start
	 * and final states. */
	for ( StateList::Iter st = stateList; st.lte(); st++ )
		st->owningGraph = 1;
	for ( int m = 0; m < numOthers; m++ ) {
		for ( StateList::Iter st = others[m]->stateList; st.lte(); st++ )
			st->owningGraph = 2+m;
	}

	/* All machines loose start state status. */
	unsetStartState();
	for ( int m = 0; m < numOthers; m++ )
		others[m]->unsetStartState();

	/* Bring the other machines into this. */
	for ( int m = 0; m < numOthers; m++ ) {
		/* Bring in the rest of other's entry points. */
		copyInEntryPoints( others[m] );
		others[m]->entryPoints.empty();

		/* Merge the lists. This will move all the states from other into
		 * this. No states will be deleted. */
		stateList.append( others[m]->stateList );
		assert( others[m]->misfitList.length() == 0 );

		/* Move the final set data from other into this. */
		finStateSet.insert( others[m]->finStateSet );
		others[m]->finStateSet.empty();

		/* Since other's list is empty, we can delete the fsm without
		 * affecting any states. */
		delete others[m];
	}

	/* Look up the start entry point. */
	EntryMapEl *enLow = 0, *enHigh = 0;
	bool findRes = entryPoints.findMulti( startId, enLow, enHigh );
	if ( ! findRes ) {
		/* No start state. Set a default one and proceed with the join. Note
		 * that the result of the join will be a very uninteresting machine. */
		setStartState( addState() );
	}
	else {
		/* There is at least one start state, create a state that will become
		 * the new start state. */
		StateAp *newStart = addState();
		setStartState( newStart );

		/* The start state is in an owning machine class all it's own. */
		newStart->owningGraph = 0;

		/* Create the set of states to merge from. */
		StateSet stateSet;
		for ( EntryMapEl *en = enLow; en <= enHigh; en++ )
			stateSet.insert( en->value );

		/* Merge in the set of start states into the new start state. */
		mergeStates( md, newStart, stateSet.data, stateSet.length() );
	}

	/* Take a copy of the final state set, before unsetting them all. This
	 * will allow us to call clearOutData on the states that don't get
	 * final state status back back. */
	StateSet finStateSetCopy = finStateSet;

	/* Now all final states are unset. */
	unsetAllFinStates();

	if ( finalId >= 0 ) {
		/* Create the implicit final state. */
		StateAp *finState = addState();
		setFinState( finState );

		/* Assign an entry into the final state on the final state entry id. Note
		 * that there may already be an entry on this id. That's ok. Also set the
		 * final state owning machine id. It's in a class all it's own. */
		setEntry( finalId, finState );
		finState->owningGraph = 0;
	}

	/* Hand over to workers for resolving epsilon trans. This will merge states
	 * with the targets of their epsilon transitions. */
	resolveEpsilonTrans( md );

	/* Invoke the relinquish final callback on any states that did not get
	 * final state status back. */
	for ( StateSet::Iter st = finStateSetCopy; st.lte(); st++ ) {
		if ( !((*st)->stateBits & STB_ISFINAL) )
			clearOutData( *st );
	}

	/* Fill in any new states made from merging. */
	fillInStates( md );

	/* Joining can be messy. Instead of having misfit accounting on (which is
	 * tricky here) do a full cleaning. */
	removeUnreachableStates();
}

void FsmAp::globOp( FsmAp **others, int numOthers )
{
	/* All other machines loose start states status. */
	for ( int m = 0; m < numOthers; m++ )
		others[m]->unsetStartState();

	/* Bring the other machines into this. */
	for ( int m = 0; m < numOthers; m++ ) {
		/* Bring in the rest of other's entry points. */
		copyInEntryPoints( others[m] );
		others[m]->entryPoints.empty();

		/* Merge the lists. This will move all the states from other into
		 * this. No states will be deleted. */
		stateList.append( others[m]->stateList );
		assert( others[m]->misfitList.length() == 0 );

		/* Move the final set data from other into this. */
		finStateSet.insert( others[m]->finStateSet );
		others[m]->finStateSet.empty();

		/* Since other's list is empty, we can delete the fsm without
		 * affecting any states. */
		delete others[m];
	}
}

void FsmAp::deterministicEntry()
{
	/* For the merging process. */
	MergeData md;

	/* States may loose their entry points, turn on misfit accounting. */
	setMisfitAccounting( true );

	/* Get a copy of the entry map then clear all the entry points. As we
	 * iterate the old entry map finding duplicates we will add the entry
	 * points for the new states that we create. */
	EntryMap prevEntry = entryPoints;
	unsetAllEntryPoints();

	for ( int enId = 0; enId < prevEntry.length(); ) {
		/* Count the number of states on this entry key. */
		int highId = enId;
		while ( highId < prevEntry.length() && prevEntry[enId].key == prevEntry[highId].key )
			highId += 1;

		int numIds = highId - enId;
		if ( numIds == 1 ) {
			/* Only a single entry point, just set the entry. */
			setEntry( prevEntry[enId].key, prevEntry[enId].value );
		}
		else {
			/* Multiple entry points, need to create a new state and merge in
			 * all the targets of entry points. */
			StateAp *newEntry = addState();
			for ( int en = enId; en < highId; en++ )
				mergeStates( md, newEntry, prevEntry[en].value );

			/* Add the new state as the single entry point. */
			setEntry( prevEntry[enId].key, newEntry );
		}

		enId += numIds;
	}

	/* The old start state may be unreachable. Remove the misfits and turn off
	 * misfit accounting. */
	removeMisfits();
	setMisfitAccounting( false );
}

/* Unset any final states that are no longer to be final due to final bits. */
void FsmAp::unsetKilledFinals()
{
	/* Duplicate the final state set before we begin modifying it. */
	StateSet fin( finStateSet );

	for ( int s = 0; s < fin.length(); s++ ) {
		/* Check for killing bit. */
		StateAp *state = fin.data[s];
		if ( state->stateBits & STB_GRAPH1 ) {
			/* One final state is a killer, set to non-final. */
			unsetFinState( state );
		}

		/* Clear all killing bits. Non final states should never have had those
		 * state bits set in the first place. */
		state->stateBits &= ~STB_GRAPH1;
	}
}

/* Unset any final states that are no longer to be final due to final bits. */
void FsmAp::unsetIncompleteFinals()
{
	/* Duplicate the final state set before we begin modifying it. */
	StateSet fin( finStateSet );

	for ( int s = 0; s < fin.length(); s++ ) {
		/* Check for one set but not the other. */
		StateAp *state = fin.data[s];
		if ( state->stateBits & STB_BOTH &&
				(state->stateBits & STB_BOTH) != STB_BOTH )
		{
			/* One state wants the other but it is not there. */
			unsetFinState( state );
		}

		/* Clear wanting bits. Non final states should never have had those
		 * state bits set in the first place. */
		state->stateBits &= ~STB_BOTH;
	}
}

/* Ensure that the start state is free of entry points (aside from the fact
 * that it is the start state). If the start state has entry points then Make a
 * new start state by merging with the old one. Useful before modifying start
 * transitions. If the existing start state has any entry points other than the
 * start state entry then modifying its transitions changes more than the start
 * transitions. So isolate the start state by separating it out such that it
 * only has start stateness as it's entry point. */
void FsmAp::isolateStartState( )
{
	/* For the merging process. */
	MergeData md;

	/* Bail out if the start state is already isolated. */
	if ( isStartStateIsolated() )
		return;

	/* Turn on misfit accounting to possibly catch the old start state. */
	setMisfitAccounting( true );

	/* This will be the new start state. The existing start
	 * state is merged with it. */
	StateAp *prevStartState = startState;
	unsetStartState();
	setStartState( addState() );

	/* Merge the new start state with the old one to isolate it. */
	mergeStates( md, startState, prevStartState );

	/* Stfil and stateDict will be empty because the merging of the old start
	 * state into the new one will not have any conflicting transitions. */
	assert( md.stateDict.treeSize == 0 );
	assert( md.stfillHead == 0 );

	/* The old start state may be unreachable. Remove the misfits and turn off
	 * misfit accounting. */
	removeMisfits();
	setMisfitAccounting( false );
}

#ifdef LOG_CONDS
void logCondSpace( CondSpace *condSpace )
{
	if ( condSpace == 0 )
		cerr << "<empty>";
	else {
		for ( CondSet::Iter csi = condSpace->condSet.last(); csi.gtb(); csi-- ) {
			if ( ! csi.last() )
				cerr << ',';
			(*csi)->actionName( cerr );
		}
	}
}

void logNewExpansion( Expansion *exp )
{
	cerr << "created expansion:" << endl;
	cerr << "  range: " << exp->lowKey.getVal() << " .. " <<
			exp->highKey.getVal() << endl;

	cerr << "  fromCondSpace: ";
	logCondSpace( exp->fromCondSpace );
	cerr << endl;
	cerr << "  fromVals: " << exp->fromVals << endl;

	cerr << "  toCondSpace: ";
	logCondSpace( exp->toCondSpace );
	cerr << endl;
	cerr << "  toValsList: ";
	for ( LongVect::Iter to = exp->toValsList; to.lte(); to++ )
		cerr << " " << *to;
	cerr << endl;
}
#endif


void FsmAp::findTransExpansions( ExpansionList &expansionList,
		StateAp *destState, StateAp *srcState )
{
	PairIter<TransAp, StateCond> transCond( destState->outList.head,
			srcState->stateCondList.head );
	for ( ; !transCond.end(); transCond++ ) {
		if ( transCond.userState == RangeOverlap ) {
			Expansion *expansion = new Expansion( transCond.s1Tel.lowKey,
					transCond.s1Tel.highKey );
			expansion->fromTrans = new TransAp(*transCond.s1Tel.trans);
			expansion->fromTrans->fromState = 0;
			expansion->fromTrans->toState = transCond.s1Tel.trans->toState;
			expansion->fromCondSpace = 0;
			expansion->fromVals = 0;
			CondSpace *srcCS = transCond.s2Tel.trans->condSpace;
			expansion->toCondSpace = srcCS;

			long numTargVals = (1 << srcCS->condSet.length());
			for ( long targVals = 0; targVals < numTargVals; targVals++ )
				expansion->toValsList.append( targVals );

			#ifdef LOG_CONDS
			logNewExpansion( expansion );
			#endif
			expansionList.append( expansion );
		}
	}
}

void FsmAp::findCondExpInTrans( ExpansionList &expansionList, StateAp *state,
		Key lowKey, Key highKey, CondSpace *fromCondSpace, CondSpace *toCondSpace,
		long fromVals, LongVect &toValsList )
{
	/* Make condition-space low and high keys for searching. */
	TransAp searchTrans;
	searchTrans.lowKey = fromCondSpace->baseKey + fromVals * keyOps->alphSize() +
			(lowKey - keyOps->minKey);
	searchTrans.highKey = fromCondSpace->baseKey + fromVals * keyOps->alphSize() +
			(highKey - keyOps->minKey);
	searchTrans.prev = searchTrans.next = 0;

	PairIter<TransAp> pairIter( state->outList.head, &searchTrans );
	for ( ; !pairIter.end(); pairIter++ ) {
		if ( pairIter.userState == RangeOverlap ) {
			/* Need to make character-space low and high keys from the range
			 * overlap for the expansion object. */
			Key expLowKey = pairIter.s1Tel.lowKey - fromCondSpace->baseKey - fromVals *
					keyOps->alphSize() + keyOps->minKey;
			Key expHighKey = pairIter.s1Tel.highKey - fromCondSpace->baseKey - fromVals *
					keyOps->alphSize() + keyOps->minKey;

			Expansion *expansion = new Expansion( expLowKey, expHighKey );
			expansion->fromTrans = new TransAp(*pairIter.s1Tel.trans);
			expansion->fromTrans->fromState = 0;
			expansion->fromTrans->toState = pairIter.s1Tel.trans->toState;
			expansion->fromCondSpace = fromCondSpace;
			expansion->fromVals = fromVals;
			expansion->toCondSpace = toCondSpace;
			expansion->toValsList = toValsList;

			expansionList.append( expansion );
			#ifdef LOG_CONDS
			logNewExpansion( expansion );
			#endif
		}
	}
}

void FsmAp::findCondExpansions( ExpansionList &expansionList,
		StateAp *destState, StateAp *srcState )
{
	PairIter<StateCond, StateCond> condCond( destState->stateCondList.head,
			srcState->stateCondList.head );
	for ( ; !condCond.end(); condCond++ ) {
		if ( condCond.userState == RangeOverlap ) {
			/* Loop over all existing condVals . */
			CondSet &destCS = condCond.s1Tel.trans->condSpace->condSet;
			long destLen = destCS.length();

			/* Find the items in src cond set that are not in dest
			 * cond set. These are the items that we must expand. */
			CondSet srcOnlyCS = condCond.s2Tel.trans->condSpace->condSet;
			for ( CondSet::Iter dcsi = destCS; dcsi.lte(); dcsi++ )
				srcOnlyCS.remove( *dcsi );
			long srcOnlyLen = srcOnlyCS.length();

			if ( srcOnlyCS.length() > 0 ) {
				#ifdef LOG_CONDS
				cerr << "there are " << srcOnlyCS.length() << " item(s) that are "
							"only in the srcCS" << endl;
				#endif

				CondSet mergedCS = destCS;
				mergedCS.insert( condCond.s2Tel.trans->condSpace->condSet );

				CondSpace *fromCondSpace = addCondSpace( destCS );
				CondSpace *toCondSpace = addCondSpace( mergedCS );

				/* Loop all values in the dest space. */
				for ( long destVals = 0; destVals < (1 << destLen); destVals++ ) {
					long basicVals = 0;
					for ( CondSet::Iter csi = destCS; csi.lte(); csi++ ) {
						if ( destVals & (1 << csi.pos()) ) {
							Action **cim = mergedCS.find( *csi );
							long bitPos = (cim - mergedCS.data);
							basicVals |= 1 << bitPos;
						}
					}

					/* Loop all new values. */
					LongVect expandToVals;
					for ( long soVals = 0; soVals < (1 << srcOnlyLen); soVals++ ) {
						long targVals = basicVals;
						for ( CondSet::Iter csi = srcOnlyCS; csi.lte(); csi++ ) {
							if ( soVals & (1 << csi.pos()) ) {
								Action **cim = mergedCS.find( *csi );
								long bitPos = (cim - mergedCS.data);
								targVals |= 1 << bitPos;
							}
						}
						expandToVals.append( targVals );
					}

					findCondExpInTrans( expansionList, destState,
							condCond.s1Tel.lowKey, condCond.s1Tel.highKey,
							fromCondSpace, toCondSpace, destVals, expandToVals );
				}
			}
		}
	}
}

void FsmAp::doExpand( MergeData &md, StateAp *destState, ExpansionList &expList1 )
{
	for ( ExpansionList::Iter exp = expList1; exp.lte(); exp++ ) {
		for ( LongVect::Iter to = exp->toValsList; to.lte(); to++ ) {
			long targVals = *to;

			/* We will use the copy of the transition that was made when the
			 * expansion was created. It will get used multiple times. Each
			 * time we must set up the keys, everything else is constant and
			 * and already prepared. */
			TransAp *srcTrans = exp->fromTrans;

			srcTrans->lowKey = exp->toCondSpace->baseKey +
					targVals * keyOps->alphSize() + (exp->lowKey - keyOps->minKey);
			srcTrans->highKey = exp->toCondSpace->baseKey +
					targVals * keyOps->alphSize() + (exp->highKey - keyOps->minKey);

			TransList srcList;
			srcList.append( srcTrans );
			outTransCopy( md, destState, srcList.head );
			srcList.abandon();
		}
	}
}


void FsmAp::doRemove( MergeData &md, StateAp *destState, ExpansionList &expList1 )
{
	for ( ExpansionList::Iter exp = expList1; exp.lte(); exp++ ) {
		Removal removal;
		if ( exp->fromCondSpace == 0 ) {
			removal.lowKey = exp->lowKey;
			removal.highKey = exp->highKey;
		}
		else {
			removal.lowKey = exp->fromCondSpace->baseKey +
				exp->fromVals * keyOps->alphSize() + (exp->lowKey - keyOps->minKey);
			removal.highKey = exp->fromCondSpace->baseKey +
				exp->fromVals * keyOps->alphSize() + (exp->highKey - keyOps->minKey);
		}
		removal.next = 0;

		TransList destList;
		PairIter<TransAp, Removal> pairIter( destState->outList.head, &removal );
		for ( ; !pairIter.end(); pairIter++ ) {
			switch ( pairIter.userState ) {
			case RangeInS1: {
				TransAp *destTrans = pairIter.s1Tel.trans;
				destTrans->lowKey = pairIter.s1Tel.lowKey;
				destTrans->highKey = pairIter.s1Tel.highKey;
				destList.append( destTrans );
				break;
			}
			case RangeInS2:
				break;
			case RangeOverlap: {
				TransAp *trans = pairIter.s1Tel.trans;
				detachTrans( trans->fromState, trans->toState, trans );
				delete trans;
				break;
			}
			case BreakS1: {
				pairIter.s1Tel.trans = dupTrans( destState,
						pairIter.s1Tel.trans );
				break;
			}
			case BreakS2:
				break;
			}
		}
		destState->outList.transfer( destList );
	}
}

void FsmAp::mergeStateConds( StateAp *destState, StateAp *srcState )
{
	StateCondList destList;
	PairIter<StateCond> pairIter( destState->stateCondList.head,
			srcState->stateCondList.head );
	for ( ; !pairIter.end(); pairIter++ ) {
		switch ( pairIter.userState ) {
		case RangeInS1: {
			StateCond *destCond = pairIter.s1Tel.trans;
			destCond->lowKey = pairIter.s1Tel.lowKey;
			destCond->highKey = pairIter.s1Tel.highKey;
			destList.append( destCond );
			break;
		}
		case RangeInS2: {
			StateCond *newCond = new StateCond( *pairIter.s2Tel.trans );
			newCond->lowKey = pairIter.s2Tel.lowKey;
			newCond->highKey = pairIter.s2Tel.highKey;
			destList.append( newCond );
			break;
		}
		case RangeOverlap: {
			StateCond *destCond = pairIter.s1Tel.trans;
			StateCond *srcCond = pairIter.s2Tel.trans;
			CondSet mergedCondSet;
			mergedCondSet.insert( destCond->condSpace->condSet );
			mergedCondSet.insert( srcCond->condSpace->condSet );
			destCond->condSpace = addCondSpace( mergedCondSet );

			destCond->lowKey = pairIter.s1Tel.lowKey;
			destCond->highKey = pairIter.s1Tel.highKey;
			destList.append( destCond );
			break;
		}
		case BreakS1:
			pairIter.s1Tel.trans = new StateCond( *pairIter.s1Tel.trans );
			break;

		case BreakS2:
			break;
		}
	}
	destState->stateCondList.transfer( destList );
}

/* A state merge which represents the drawing in of leaving transitions.  If
 * there is any out data then we duplicate the source state, transfer the out
 * data, then merge in the state. The new state will be reaped because it will
 * not be given any in transitions. */
void FsmAp::mergeStatesLeaving( MergeData &md, StateAp *destState, StateAp *srcState )
{
	if ( !hasOutData( destState ) )
		mergeStates( md, destState, srcState );
	else {
		StateAp *ssMutable = addState();
		mergeStates( md, ssMutable, srcState );
		transferOutData( ssMutable, destState );

		for ( OutCondSet::Iter cond = destState->outCondSet; cond.lte(); cond++ )
			embedCondition( md, ssMutable, cond->action, cond->sense );

		mergeStates( md, destState, ssMutable );
	}
}

void FsmAp::mergeStates( MergeData &md, StateAp *destState,
		StateAp **srcStates, int numSrc )
{
	for ( int s = 0; s < numSrc; s++ )
		mergeStates( md, destState, srcStates[s] );
}

void FsmAp::mergeStates( MergeData &md, StateAp *destState, StateAp *srcState )
{
	ExpansionList expList1;
	ExpansionList expList2;

	findTransExpansions( expList1, destState, srcState );
	findCondExpansions( expList1, destState, srcState );
	findTransExpansions( expList2, srcState, destState );
	findCondExpansions( expList2, srcState, destState );

	mergeStateConds( destState, srcState );

	outTransCopy( md, destState, srcState->outList.head );

	doExpand( md, destState, expList1 );
	doExpand( md, destState, expList2 );

	doRemove( md, destState, expList1 );
	doRemove( md, destState, expList2 );

	expList1.empty();
	expList2.empty();

	/* Get its bits and final state status. */
	destState->stateBits |= ( srcState->stateBits & ~STB_ISFINAL );
	if ( srcState->isFinState() )
		setFinState( destState );

	/* Draw in any properties of srcState into destState. */
	if ( srcState == destState ) {
		/* Duplicate the list to protect against write to source. The
		 * priorities sets are not copied in because that would have no
		 * effect. */
		destState->epsilonTrans.append( EpsilonTrans( srcState->epsilonTrans ) );

		/* Get all actions, duplicating to protect against write to source. */
		destState->toStateActionTable.setActions(
				ActionTable( srcState->toStateActionTable ) );
		destState->fromStateActionTable.setActions(
				ActionTable( srcState->fromStateActionTable ) );
		destState->outActionTable.setActions( ActionTable( srcState->outActionTable ) );
		destState->outCondSet.insert( OutCondSet( srcState->outCondSet ) );
		destState->errActionTable.setActions( ErrActionTable( srcState->errActionTable ) );
		destState->eofActionTable.setActions( ActionTable( srcState->eofActionTable ) );
	}
	else {
		/* Get the epsilons, out priorities. */
		destState->epsilonTrans.append( srcState->epsilonTrans );
		destState->outPriorTable.setPriors( srcState->outPriorTable );

		/* Get all actions. */
		destState->toStateActionTable.setActions( srcState->toStateActionTable );
		destState->fromStateActionTable.setActions( srcState->fromStateActionTable );
		destState->outActionTable.setActions( srcState->outActionTable );
		destState->outCondSet.insert( srcState->outCondSet );
		destState->errActionTable.setActions( srcState->errActionTable );
		destState->eofActionTable.setActions( srcState->eofActionTable );
	}
}

void FsmAp::fillInStates( MergeData &md )
{
	/* Merge any states that are awaiting merging. This will likey cause
	 * other states to be added to the stfil list. */
	StateAp *state = md.stfillHead;
	while ( state != 0 ) {
		StateSet *stateSet = &state->stateDictEl->stateSet;
		mergeStates( md, state, stateSet->data, stateSet->length() );
		state = state->alg.next;
	}

	/* Delete the state sets of all states that are on the fill list. */
	state = md.stfillHead;
	while ( state != 0 ) {
		/* Delete and reset the state set. */
		delete state->stateDictEl;
		state->stateDictEl = 0;

		/* Next state in the stfill list. */
		state = state->alg.next;
	}

	/* StateDict will still have its ptrs/size set but all of it's element
	 * will be deleted so we don't need to clean it up. */
}

void FsmAp::findEmbedExpansions( ExpansionList &expansionList,
		StateAp *destState, Action *condAction, bool sense )
{
	StateCondList destList;
	PairIter<TransAp, StateCond> transCond( destState->outList.head,
			destState->stateCondList.head );
	for ( ; !transCond.end(); transCond++ ) {
		switch ( transCond.userState ) {
			case RangeInS1: {
				if ( transCond.s1Tel.lowKey <= keyOps->maxKey ) {
					assert( transCond.s1Tel.highKey <= keyOps->maxKey );

					/* Make a new state cond. */
					StateCond *newStateCond = new StateCond( transCond.s1Tel.lowKey,
							transCond.s1Tel.highKey );
					newStateCond->condSpace = addCondSpace( CondSet( condAction ) );
					destList.append( newStateCond );

					/* Create the expansion. */
					Expansion *expansion = new Expansion( transCond.s1Tel.lowKey,
							transCond.s1Tel.highKey );
					expansion->fromTrans = new TransAp(*transCond.s1Tel.trans);
					expansion->fromTrans->fromState = 0;
					expansion->fromTrans->toState = transCond.s1Tel.trans->toState;
					expansion->fromCondSpace = 0;
					expansion->fromVals = 0;
					expansion->toCondSpace = newStateCond->condSpace;
					expansion->toValsList.append( sense?1:0 );
					#ifdef LOG_CONDS
					logNewExpansion( expansion );
					#endif
					expansionList.append( expansion );
				}
				break;
			}
			case RangeInS2: {
				/* Enhance state cond and find the expansion. */
				StateCond *stateCond = transCond.s2Tel.trans;
				stateCond->lowKey = transCond.s2Tel.lowKey;
				stateCond->highKey = transCond.s2Tel.highKey;

				CondSet &destCS = stateCond->condSpace->condSet;
				long destLen = destCS.length();
				CondSpace *fromCondSpace = stateCond->condSpace;

				CondSet mergedCS = destCS;
				mergedCS.insert( condAction );
				CondSpace *toCondSpace = addCondSpace( mergedCS );
				stateCond->condSpace = toCondSpace;
				destList.append( stateCond );

				/* Loop all values in the dest space. */
				for ( long destVals = 0; destVals < (1 << destLen); destVals++ ) {
					long basicVals = 0;
					for ( CondSet::Iter csi = destCS; csi.lte(); csi++ ) {
						if ( destVals & (1 << csi.pos()) ) {
							Action **cim = mergedCS.find( *csi );
							long bitPos = (cim - mergedCS.data);
							basicVals |= 1 << bitPos;
						}
					}

					long targVals = basicVals;
					Action **cim = mergedCS.find( condAction );
					long bitPos = (cim - mergedCS.data);
					targVals |= (sense?1:0) << bitPos;

					LongVect expandToVals( targVals );
					findCondExpInTrans( expansionList, destState,
						transCond.s2Tel.lowKey, transCond.s2Tel.highKey,
						fromCondSpace, toCondSpace, destVals, expandToVals );
				}
				break;
			}


			case RangeOverlap:
			case BreakS1:
			case BreakS2:
				assert( false );
				break;
		}
	}

	destState->stateCondList.transfer( destList );
}

void FsmAp::embedCondition( StateAp *state, Action *condAction, bool sense )
{
	MergeData md;
	ExpansionList expList;

	/* Turn on misfit accounting to possibly catch the old start state. */
	setMisfitAccounting( true );

	/* Worker. */
	embedCondition( md, state, condAction, sense );

	/* Fill in any states that were newed up as combinations of others. */
	fillInStates( md );

	/* Remove the misfits and turn off misfit accounting. */
	removeMisfits();
	setMisfitAccounting( false );
}

void FsmAp::embedCondition( MergeData &md, StateAp *state, Action *condAction, bool sense )
{
	ExpansionList expList;

	findEmbedExpansions( expList, state, condAction, sense );
	doExpand( md, state, expList );
	doRemove( md, state, expList );
	expList.empty();
}

/* Check if a machine defines a single character. This is useful in validating
 * ranges and machines to export. */
bool FsmAp::checkSingleCharMachine()
{
	/* Must have two states. */
	if ( stateList.length() != 2 )
		return false;
	/* The start state cannot be final. */
	if ( startState->isFinState() )
		return false;
	/* There should be only one final state. */
	if ( finStateSet.length() != 1 )
		return false;
	/* The final state cannot have any transitions out. */
	if ( finStateSet[0]->outList.length() != 0 )
		return false;
	/* The start state should have only one transition out. */
	if ( startState->outList.length() != 1 )
		return false;
	/* The singe transition out of the start state should not be a range. */
	TransAp *startTrans = startState->outList.head;
	if ( startTrans->lowKey != startTrans->highKey )
		return false;
	return true;
}