A fix to the documentation makefile from John D. Mitchell.

[ragel.git] / ragel / fsmgraph.cpp

/*
 *  Copyright 2001, 2002, 2006 Adrian Thurston <thurston@cs.queensu.ca>
 */

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