Notes on version 6.3.

[ragel.git] / ragel / fsmmin.cpp

/*
 *  Copyright 2002 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 "fsmgraph.h"
#include "mergesort.h"

int FsmAp::partitionRound( StateAp **statePtrs, MinPartition *parts, int numParts )
{
        /* Need a mergesort object and a single partition compare. */
        MergeSort<StateAp*, PartitionCompare> mergeSort;
        PartitionCompare partCompare;

        /* For each partition. */
        for ( int p = 0; p < numParts; p++ ) {
                /* Fill the pointer array with the states in the partition. */
                StateList::Iter state = parts[p].list;
                for ( int s = 0; state.lte(); state++, s++ )
                        statePtrs[s] = state;

                /* Sort the states using the partitioning compare. */
                int numStates = parts[p].list.length();
                mergeSort.sort( statePtrs, numStates );

                /* Assign the states into partitions based on the results of the sort. */
                int destPart = p, firstNewPart = numParts;
                for ( int s = 1; s < numStates; s++ ) {
                        /* If this state differs from the last then move to the next partition. */
                        if ( partCompare.compare( statePtrs[s-1], statePtrs[s] ) < 0 ) {
                                /* The new partition is the next avail spot. */
                                destPart = numParts;
                                numParts += 1;
                        }

                        /* If the state is not staying in the first partition, then
                         * transfer it to its destination partition. */
                        if ( destPart != p ) {
                                StateAp *state = parts[p].list.detach( statePtrs[s] );
                                parts[destPart].list.append( state );
                        }
                }

                /* Fix the partition pointer for all the states that got moved to a new
                 * partition. This must be done after the states are transfered so the
                 * result of the sort is not altered. */
                for ( int newPart = firstNewPart; newPart < numParts; newPart++ ) {
                        StateList::Iter state = parts[newPart].list;
                        for ( ; state.lte(); state++ )
                                state->alg.partition = &parts[newPart];
                }
        }

        return numParts;
}

/**
 * \brief Minimize by partitioning version 1.
 *
 * Repeatedly tries to split partitions until all partitions are unsplittable.
 * Produces the most minimal FSM possible.
 */
void FsmAp::minimizePartition1()
{
        /* Need one mergesort object and partition compares. */
        MergeSort<StateAp*, InitPartitionCompare> mergeSort;
        InitPartitionCompare initPartCompare;

        /* Nothing to do if there are no states. */
        if ( stateList.length() == 0 )
                return;

        /* 
         * First thing is to partition the states by final state status and
         * transition functions. This gives us an initial partitioning to work
         * with.
         */

        /* Make a array of pointers to states. */
        int numStates = stateList.length();
        StateAp** statePtrs = new StateAp*[numStates];

        /* Fill up an array of pointers to the states for easy sorting. */
        StateList::Iter state = stateList;
        for ( int s = 0; state.lte(); state++, s++ )
                statePtrs[s] = state;
                
        /* Sort the states using the array of states. */
        mergeSort.sort( statePtrs, numStates );

        /* An array of lists of states is used to partition the states. */
        MinPartition *parts = new MinPartition[numStates];

        /* Assign the states into partitions. */
        int destPart = 0;
        for ( int s = 0; s < numStates; s++ ) {
                /* If this state differs from the last then move to the next partition. */
                if ( s > 0 && initPartCompare.compare( statePtrs[s-1], statePtrs[s] ) < 0 ) {
                        /* Move to the next partition. */
                        destPart += 1;
                }

                /* Put the state into its partition. */
                statePtrs[s]->alg.partition = &parts[destPart];
                parts[destPart].list.append( statePtrs[s] );
        }

        /* We just moved all the states from the main list into partitions without
         * taking them off the main list. So clean up the main list now. */
        stateList.abandon();

        /* Split partitions. */
        int numParts = destPart + 1;
        while ( true ) {
                /* Test all partitions for splitting. */
                int newNum = partitionRound( statePtrs, parts, numParts );

                /* When no partitions can be split, stop. */
                if ( newNum == numParts )
                        break;

                numParts = newNum;
        }

        /* Fuse states in the same partition. The states will end up back on the
         * main list. */
        fusePartitions( parts, numParts );

        /* Cleanup. */
        delete[] statePtrs;
        delete[] parts;
}

/* Split partitions that need splittting, decide which partitions might need
 * to be split as a result, continue until there are no more that might need
 * to be split. */
int FsmAp::splitCandidates( StateAp **statePtrs, MinPartition *parts, int numParts )
{
        /* Need a mergesort and a partition compare. */
        MergeSort<StateAp*, PartitionCompare> mergeSort;
        PartitionCompare partCompare;

        /* The lists of unsplitable (partList) and splitable partitions. 
         * Only partitions in the splitable list are check for needing splitting. */
        PartitionList partList, splittable;

        /* Initially, all partitions are born from a split (the initial
         * partitioning) and can cause other partitions to be split. So any
         * partition with a state with a transition out to another partition is a
         * candidate for splitting. This will make every partition except possibly
         * partitions of final states split candidates. */
        for ( int p = 0; p < numParts; p++ ) {
                /* Assume not active. */
                parts[p].active = false;

                /* Look for a trans out of any state in the partition. */
                for ( StateList::Iter state = parts[p].list; state.lte(); state++ ) {
                        /* If there is at least one transition out to another state then 
                         * the partition becomes splittable. */
                        if ( state->outList.length() > 0 ) {
                                parts[p].active = true;
                                break;
                        }
                }

                /* If it was found active then it goes on the splittable list. */
                if ( parts[p].active )
                        splittable.append( &parts[p] );
                else
                        partList.append( &parts[p] );
        }

        /* While there are partitions that are splittable, pull one off and try
         * to split it. If it splits, determine which partitions may now be split
         * as a result of the newly split partition. */
        while ( splittable.length() > 0 ) {
                MinPartition *partition = splittable.detachFirst();

                /* Fill the pointer array with the states in the partition. */
                StateList::Iter state = partition->list;
                for ( int s = 0; state.lte(); state++, s++ )
                        statePtrs[s] = state;

                /* Sort the states using the partitioning compare. */
                int numStates = partition->list.length();
                mergeSort.sort( statePtrs, numStates );

                /* Assign the states into partitions based on the results of the sort. */
                MinPartition *destPart = partition;
                int firstNewPart = numParts;
                for ( int s = 1; s < numStates; s++ ) {
                        /* If this state differs from the last then move to the next partition. */
                        if ( partCompare.compare( statePtrs[s-1], statePtrs[s] ) < 0 ) {
                                /* The new partition is the next avail spot. */
                                destPart = &parts[numParts];
                                numParts += 1;
                        }

                        /* If the state is not staying in the first partition, then
                         * transfer it to its destination partition. */
                        if ( destPart != partition ) {
                                StateAp *state = partition->list.detach( statePtrs[s] );
                                destPart->list.append( state );
                        }
                }

                /* Fix the partition pointer for all the states that got moved to a new
                 * partition. This must be done after the states are transfered so the
                 * result of the sort is not altered. */
                int newPart;
                for ( newPart = firstNewPart; newPart < numParts; newPart++ ) {
                        StateList::Iter state = parts[newPart].list;
                        for ( ; state.lte(); state++ )
                                state->alg.partition = &parts[newPart];
                }

                /* Put the partition we just split and any new partitions that came out
                 * of the split onto the inactive list. */
                partition->active = false;
                partList.append( partition );
                for ( newPart = firstNewPart; newPart < numParts; newPart++ ) {
                        parts[newPart].active = false;
                        partList.append( &parts[newPart] );
                }

                if ( destPart == partition )
                        continue;

                /* Now determine which partitions are splittable as a result of
                 * splitting partition by walking the in lists of the states in
                 * partitions that got split. Partition is the faked first item in the
                 * loop. */
                MinPartition *causalPart = partition;
                newPart = firstNewPart - 1;
                while ( newPart < numParts ) {
                        /* Loop all states in the causal partition. */
                        StateList::Iter state = causalPart->list;
                        for ( ; state.lte(); state++ ) {
                                /* Walk all transition into the state and put the partition
                                 * that the from state is in onto the splittable list. */
                                for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ ) {
                                        MinPartition *fromPart = trans->fromState->alg.partition;
                                        if ( ! fromPart->active ) {
                                                fromPart->active = true;
                                                partList.detach( fromPart );
                                                splittable.append( fromPart );
                                        }
                                }
                        }

                        newPart += 1;
                        causalPart = &parts[newPart];
                }
        }
        return numParts;
}


/**
 * \brief Minimize by partitioning version 2 (best alg).
 *
 * Repeatedly tries to split partitions that may splittable until there are no
 * more partitions that might possibly need splitting. Runs faster than
 * version 1. Produces the most minimal fsm possible.
 */
void FsmAp::minimizePartition2()
{
        /* Need a mergesort and an initial partition compare. */
        MergeSort<StateAp*, InitPartitionCompare> mergeSort;
        InitPartitionCompare initPartCompare;

        /* Nothing to do if there are no states. */
        if ( stateList.length() == 0 )
                return;

        /* 
         * First thing is to partition the states by final state status and
         * transition functions. This gives us an initial partitioning to work
         * with.
         */

        /* Make a array of pointers to states. */
        int numStates = stateList.length();
        StateAp** statePtrs = new StateAp*[numStates];

        /* Fill up an array of pointers to the states for easy sorting. */
        StateList::Iter state = stateList;
        for ( int s = 0; state.lte(); state++, s++ )
                statePtrs[s] = state;
                
        /* Sort the states using the array of states. */
        mergeSort.sort( statePtrs, numStates );

        /* An array of lists of states is used to partition the states. */
        MinPartition *parts = new MinPartition[numStates];

        /* Assign the states into partitions. */
        int destPart = 0;
        for ( int s = 0; s < numStates; s++ ) {
                /* If this state differs from the last then move to the next partition. */
                if ( s > 0 && initPartCompare.compare( statePtrs[s-1], statePtrs[s] ) < 0 ) {
                        /* Move to the next partition. */
                        destPart += 1;
                }

                /* Put the state into its partition. */
                statePtrs[s]->alg.partition = &parts[destPart];
                parts[destPart].list.append( statePtrs[s] );
        }

        /* We just moved all the states from the main list into partitions without
         * taking them off the main list. So clean up the main list now. */
        stateList.abandon();

        /* Split partitions. */
        int numParts = splitCandidates( statePtrs, parts, destPart+1 );

        /* Fuse states in the same partition. The states will end up back on the
         * main list. */
        fusePartitions( parts, numParts );

        /* Cleanup. */
        delete[] statePtrs;
        delete[] parts;
}

void FsmAp::initialMarkRound( MarkIndex &markIndex )
{
        /* P and q for walking pairs. */
        StateAp *p = stateList.head, *q;

        /* Need an initial partition compare. */
        InitPartitionCompare initPartCompare;

        /* Walk all unordered pairs of (p, q) where p != q.
         * The second depth of the walk stops before reaching p. This
         * gives us all unordered pairs of states (p, q) where p != q. */
        while ( p != 0 ) {
                q = stateList.head;
                while ( q != p ) {
                        /* If the states differ on final state status, out transitions or
                         * any transition data then they should be separated on the initial
                         * round. */
                        if ( initPartCompare.compare( p, q ) != 0 )
                                markIndex.markPair( p->alg.stateNum, q->alg.stateNum );

                        q = q->next;
                }
                p = p->next;
        }
}

bool FsmAp::markRound( MarkIndex &markIndex )
{
        /* P an q for walking pairs. Take note if any pair gets marked. */
        StateAp *p = stateList.head, *q;
        bool pairWasMarked = false;

        /* Need a mark comparison. */
        MarkCompare markCompare;

        /* Walk all unordered pairs of (p, q) where p != q.
         * The second depth of the walk stops before reaching p. This
         * gives us all unordered pairs of states (p, q) where p != q. */
        while ( p != 0 ) {
                q = stateList.head;
                while ( q != p ) {
                        /* Should we mark the pair? */
                        if ( !markIndex.isPairMarked( p->alg.stateNum, q->alg.stateNum ) ) {
                                if ( markCompare.shouldMark( markIndex, p, q ) ) {
                                        markIndex.markPair( p->alg.stateNum, q->alg.stateNum );
                                        pairWasMarked = true;
                                }
                        }
                        q = q->next;
                }
                p = p->next;
        }

        return pairWasMarked;
}


/**
 * \brief Minimize by pair marking.
 *
 * Decides if each pair of states is distinct or not. Uses O(n^2) memory and
 * should only be used on small graphs. Produces the most minmimal FSM
 * possible.
 */
void FsmAp::minimizeStable()
{
        /* Set the state numbers. */
        setStateNumbers( 0 );

        /* This keeps track of which pairs have been marked. */
        MarkIndex markIndex( stateList.length() );

        /* Mark pairs where final stateness, out trans, or trans data differ. */
        initialMarkRound( markIndex );

        /* While the last round of marking succeeded in marking a state
         * continue to do another round. */
        int modified = markRound( markIndex );
        while (modified)
                modified = markRound( markIndex );

        /* Merge pairs that are unmarked. */
        fuseUnmarkedPairs( markIndex );
}

bool FsmAp::minimizeRound()
{
        /* Nothing to do if there are no states. */
        if ( stateList.length() == 0 )
                return false;

        /* Need a mergesort on approx compare and an approx compare. */
        MergeSort<StateAp*, ApproxCompare> mergeSort;
        ApproxCompare approxCompare;

        /* Fill up an array of pointers to the states. */
        StateAp **statePtrs = new StateAp*[stateList.length()];
        StateList::Iter state = stateList;
        for ( int s = 0; state.lte(); state++, s++ )
                statePtrs[s] = state;

        bool modified = false;

        /* Sort The list. */
        mergeSort.sort( statePtrs, stateList.length() );

        /* Walk the list looking for duplicates next to each other, 
         * merge in any duplicates. */
        StateAp **pLast = statePtrs;
        StateAp **pState = statePtrs + 1;
        for ( int i = 1; i < stateList.length(); i++, pState++ ) {
                if ( approxCompare.compare( *pLast, *pState ) == 0 ) {
                        /* Last and pState are the same, so fuse together. Move forward
                         * with pState but not with pLast. If any more are identical, we
                         * must */
                        fuseEquivStates( *pLast, *pState );
                        modified = true;
                }
                else {
                        /* Last and this are different, do not set to merge them. Move
                         * pLast to the current (it may be way behind from merging many
                         * states) and pState forward one to consider the next pair. */
                        pLast = pState;
                }
        }
        delete[] statePtrs;
        return modified;
}

/**
 * \brief Minmimize by an approximation.
 *
 * Repeatedly tries to find states with transitions out to the same set of
 * states on the same set of keys until no more identical states can be found.
 * Does not produce the most minimial FSM possible.
 */
void FsmAp::minimizeApproximate()
{
        /* While the last minimization round succeeded in compacting states,
         * continue to try to compact states. */
        while ( true ) {
                bool modified = minimizeRound();
                if ( ! modified )
                        break;
        }
}


/* Remove states that have no path to them from the start state. Recursively
 * traverses the graph marking states that have paths into them. Then removes
 * all states that did not get marked. */
void FsmAp::removeUnreachableStates()
{
        /* Misfit accounting should be off and there should be no states on the
         * misfit list. */
        assert( !misfitAccounting && misfitList.length() == 0 );

        /* Mark all the states that can be reached 
         * through the existing set of entry points. */
        markReachableFromHere( startState );
        for ( EntryMap::Iter en = entryPoints; en.lte(); en++ )
                markReachableFromHere( en->value );

        /* Delete all states that are not marked
         * and unmark the ones that are marked. */
        StateAp *state = stateList.head;
        while ( state ) {
                StateAp *next = state->next;

                if ( state->stateBits & STB_ISMARKED )
                        state->stateBits &= ~ STB_ISMARKED;
                else {
                        detachState( state );
                        stateList.detach( state );
                        delete state;
                }

                state = next;
        }
}

bool FsmAp::outListCovers( StateAp *state )
{
        /* Must be at least one range to cover. */
        if ( state->outList.length() == 0 )
                return false;
        
        /* The first must start at the lower bound. */
        TransList::Iter trans = state->outList.first();
        if ( keyOps->minKey < trans->lowKey )
                return false;

        /* Loop starts at second el. */
        trans.increment();

        /* Loop checks lower against prev upper. */
        for ( ; trans.lte(); trans++ ) {
                /* Lower end of the trans must be one greater than the
                 * previous' high end. */
                Key lowKey = trans->lowKey;
                lowKey.decrement();
                if ( trans->prev->highKey < lowKey )
                        return false;
        }

        /* Require that the last range extends to the upper bound. */
        trans = state->outList.last();
        if ( trans->highKey < keyOps->maxKey )
                return false;

        return true;
}

/* Remove states that that do not lead to a final states. Works recursivly traversing
 * the graph in reverse (starting from all final states) and marking seen states. Then
 * removes states that did not get marked. */
void FsmAp::removeDeadEndStates()
{
        /* Misfit accounting should be off and there should be no states on the
         * misfit list. */
        assert( !misfitAccounting && misfitList.length() == 0 );

        /* Mark all states that have paths to the final states. */
        StateAp **st = finStateSet.data;
        int nst = finStateSet.length();
        for ( int i = 0; i < nst; i++, st++ )
                markReachableFromHereReverse( *st );

        /* Start state gets honorary marking. If the machine accepts nothing we
         * still want the start state to hang around. This must be done after the
         * recursive call on all the final states so that it does not cause the
         * start state in transitions to be skipped when the start state is
         * visited by the traversal. */
        startState->stateBits |= STB_ISMARKED;

        /* Delete all states that are not marked
         * and unmark the ones that are marked. */
        StateAp *state = stateList.head;
        while ( state != 0 ) {
                StateAp *next = state->next;

                if ( state->stateBits & STB_ISMARKED  )
                        state->stateBits &= ~ STB_ISMARKED;
                else {
                        detachState( state );
                        stateList.detach( state );
                        delete state;
                }
                
                state = next;
        }
}

/* Remove states on the misfit list. To work properly misfit accounting should
 * be on when this is called. The detaching of a state will likely cause
 * another misfit to be collected and it can then be removed. */
void FsmAp::removeMisfits()
{
        while ( misfitList.length() > 0 ) {
                /* Get the first state. */
                StateAp *state = misfitList.head;

                /* Detach and delete. */
                detachState( state );

                /* The state was previously on the misfit list and detaching can only
                 * remove in transitions so the state must still be on the misfit
                 * list. */
                misfitList.detach( state );
                delete state;
        }
}

/* Fuse src into dest because they have been deemed equivalent states.
 * Involves moving transitions into src to go into dest and invoking
 * callbacks. Src is deleted detached from the graph and deleted. */
void FsmAp::fuseEquivStates( StateAp *dest, StateAp *src )
{
        /* This would get ugly. */
        assert( dest != src );

        /* Cur is a duplicate. We can merge it with trail. */
        inTransMove( dest, src );

        detachState( src );
        stateList.detach( src );
        delete src;
}

void FsmAp::fuseUnmarkedPairs( MarkIndex &markIndex )
{
        StateAp *p = stateList.head, *nextP, *q;

        /* Definition: The primary state of an equivalence class is the first state
         * encounterd that belongs to the equivalence class. All equivalence
         * classes have primary state including equivalence classes with one state
         * in it. */

        /* For each unmarked pair merge p into q and delete p. q is always the
         * primary state of it's equivalence class. We wouldn't have landed on it
         * here if it were not, because it would have been deleted.
         *
         * Proof that q is the primaray state of it's equivalence class: Assume q
         * is not the primary state of it's equivalence class, then it would be
         * merged into some state that came before it and thus p would be
         * equivalent to that state. But q is the first state that p is equivalent
         * to so we have a contradiction. */

        /* Walk all unordered pairs of (p, q) where p != q.
         * The second depth of the walk stops before reaching p. This
         * gives us all unordered pairs of states (p, q) where p != q. */
        while ( p != 0 ) {
                nextP = p->next;

                q = stateList.head;
                while ( q != p ) {
                        /* If one of p or q is a final state then mark. */
                        if ( ! markIndex.isPairMarked( p->alg.stateNum, q->alg.stateNum ) ) {
                                fuseEquivStates( q, p );
                                break;
                        }
                        q = q->next;
                }
                p = nextP;
        }
}

void FsmAp::fusePartitions( MinPartition *parts, int numParts )
{
        /* For each partition, fuse state 2, 3, ... into state 1. */
        for ( int p = 0; p < numParts; p++ ) {
                /* Assume that there will always be at least one state. */
                StateAp *first = parts[p].list.head, *toFuse = first->next;

                /* Put the first state back onto the main state list. Don't bother
                 * removing it from the partition list first. */
                stateList.append( first );

                /* Fuse the rest of the state into the first. */
                while ( toFuse != 0 ) {
                        /* Save the next. We will trash it before it is needed. */
                        StateAp *next = toFuse->next;

                        /* Put the state to be fused in to the first back onto the main
                         * list before it is fuse.  the graph. The state needs to be on
                         * the main list for the detach from the graph to work.  Don't
                         * bother removing the state from the partition list first. We
                         * need not maintain it. */
                        stateList.append( toFuse );

                        /* Now fuse to the first. */
                        fuseEquivStates( first, toFuse );

                        /* Go to the next that we saved before trashing the next pointer. */
                        toFuse = next;
                }

                /* We transfered the states from the partition list into the main list without
                 * removing the states from the partition list first. Clean it up. */
                parts[p].list.abandon();
        }
}


/* Merge neighboring transitions go to the same state and have the same
 * transitions data. */
void FsmAp::compressTransitions()
{
        for ( StateList::Iter st = stateList; st.lte(); st++ ) {
                if ( st->outList.length() > 1 ) {
                        for ( TransList::Iter trans = st->outList, next = trans.next(); next.lte();  ) {
                                Key nextLow = next->lowKey;
                                nextLow.decrement();
                                if ( trans->highKey == nextLow && trans->toState == next->toState &&
                                        CmpActionTable::compare( trans->actionTable, next->actionTable ) == 0 )
                                {
                                        trans->highKey = next->highKey;
                                        st->outList.detach( next );
                                        detachTrans( next->fromState, next->toState, next );
                                        delete next;
                                        next = trans.next();
                                }
                                else {
                                        trans.increment();
                                        next.increment();
                                }
                        }
                }
        }
}