/* * Copyright 2001-2007 Adrian Thurston */ /* 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 #include #include "fsmgraph.h" /* Simple singly linked list append routine for the fill list. The new state * goes to the end of the list. */ void MergeData::fillListAppend( StateAp *state ) { state->alg.next = 0; if ( stfillHead == 0 ) { /* List is empty, state becomes head and tail. */ stfillHead = state; stfillTail = state; } else { /* List is not empty, state goes after last element. */ stfillTail->alg.next = state; stfillTail = state; } } /* Graph constructor. */ FsmAp::FsmAp() : /* No start state. */ startState(0), errState(0), /* Misfit accounting is a switch, turned on only at specific times. It * controls what happens when states have no way in from the outside * world.. */ misfitAccounting(false) { } /* Copy all graph data including transitions. */ FsmAp::FsmAp( const FsmAp &graph ) : /* Lists start empty. Will be filled by copy. */ stateList(), misfitList(), /* Copy in the entry points, * pointers will be resolved later. */ entryPoints(graph.entryPoints), startState(graph.startState), errState(0), /* Will be filled by copy. */ finStateSet(), /* Misfit accounting is only on during merging. */ misfitAccounting(false) { /* Create the states and record their map in the original state. */ StateList::Iter origState = graph.stateList; for ( ; origState.lte(); origState++ ) { /* Make the new state. */ StateAp *newState = new StateAp( *origState ); /* Add the state to the list. */ stateList.append( newState ); /* Set the mapsTo item of the old state. */ origState->alg.stateMap = newState; } /* Derefernce all the state maps. */ for ( StateList::Iter state = stateList; state.lte(); state++ ) { for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { /* The points to the original in the src machine. The taget's duplicate * is in the statemap. */ StateAp *toState = trans->toState != 0 ? trans->toState->alg.stateMap : 0; /* Attach The transition to the duplicate. */ trans->toState = 0; attachTrans( state, toState, trans ); } /* Fix the eofTarg, if set. */ if ( state->eofTarget != 0 ) state->eofTarget = state->eofTarget->alg.stateMap; } /* Fix the state pointers in the entry points array. */ EntryMapEl *eel = entryPoints.data; for ( int e = 0; e < entryPoints.length(); e++, eel++ ) { /* Get the duplicate of the state. */ eel->value = eel->value->alg.stateMap; /* Foreign in transitions must be built up when duping machines so * increment it here. */ eel->value->foreignInTrans += 1; } /* Fix the start state pointer and the new start state's count of in * transiions. */ startState = startState->alg.stateMap; startState->foreignInTrans += 1; /* Build the final state set. */ StateSet::Iter st = graph.finStateSet; for ( ; st.lte(); st++ ) finStateSet.insert((*st)->alg.stateMap); } /* Deletes all transition data then deletes each state. */ FsmAp::~FsmAp() { /* Delete all the transitions. */ for ( StateList::Iter state = stateList; state.lte(); state++ ) { /* Iterate the out transitions, deleting them. */ state->outList.empty(); } /* Delete all the states. */ stateList.empty(); } /* Set a state final. The state has its isFinState set to true and the state * is added to the finStateSet. */ void FsmAp::setFinState( StateAp *state ) { /* Is it already a fin state. */ if ( state->stateBits & STB_ISFINAL ) return; state->stateBits |= STB_ISFINAL; finStateSet.insert( state ); } /* Set a state non-final. The has its isFinState flag set false and the state * is removed from the final state set. */ void FsmAp::unsetFinState( StateAp *state ) { /* Is it already a non-final state? */ if ( ! (state->stateBits & STB_ISFINAL) ) return; /* When a state looses its final state status it must relinquish all the * properties that are allowed only for final states. */ clearOutData( state ); state->stateBits &= ~ STB_ISFINAL; finStateSet.remove( state ); } /* Set and unset a state as the start state. */ void FsmAp::setStartState( StateAp *state ) { /* Sould change from unset to set. */ assert( startState == 0 ); startState = state; if ( misfitAccounting ) { /* If the number of foreign in transitions is about to go up to 1 then * take it off the misfit list and put it on the head list. */ if ( state->foreignInTrans == 0 ) stateList.append( misfitList.detach( state ) ); } /* Up the foreign in transitions to the state. */ state->foreignInTrans += 1; } void FsmAp::unsetStartState() { /* Should change from set to unset. */ assert( startState != 0 ); /* Decrement the entry's count of foreign entries. */ startState->foreignInTrans -= 1; if ( misfitAccounting ) { /* If the number of foreign in transitions just went down to 0 then take * it off the main list and put it on the misfit list. */ if ( startState->foreignInTrans == 0 ) misfitList.append( stateList.detach( startState ) ); } startState = 0; } /* Associate an id with a state. Makes the state a named entry point. Has no * effect if the entry point is already mapped to the state. */ void FsmAp::setEntry( int id, StateAp *state ) { /* Insert the id into the state. If the state is already labelled with id, * nothing to do. */ if ( state->entryIds.insert( id ) ) { /* Insert the entry and assert that it succeeds. */ entryPoints.insertMulti( id, state ); if ( misfitAccounting ) { /* If the number of foreign in transitions is about to go up to 1 then * take it off the misfit list and put it on the head list. */ if ( state->foreignInTrans == 0 ) stateList.append( misfitList.detach( state ) ); } /* Up the foreign in transitions to the state. */ state->foreignInTrans += 1; } } /* Remove the association of an id with a state. The state looses it's entry * point status. Assumes that the id is indeed mapped to state. */ void FsmAp::unsetEntry( int id, StateAp *state ) { /* Find the entry point in on id. */ EntryMapEl *enLow = 0, *enHigh = 0; entryPoints.findMulti( id, enLow, enHigh ); while ( enLow->value != state ) enLow += 1; /* Remove the record from the map. */ entryPoints.remove( enLow ); /* Remove the state's sense of the link. */ state->entryIds.remove( id ); state->foreignInTrans -= 1; if ( misfitAccounting ) { /* If the number of foreign in transitions just went down to 0 then take * it off the main list and put it on the misfit list. */ if ( state->foreignInTrans == 0 ) misfitList.append( stateList.detach( state ) ); } } /* Remove all association of an id with states. Assumes that the id is indeed * mapped to a state. */ void FsmAp::unsetEntry( int id ) { /* Find the entry point in on id. */ EntryMapEl *enLow = 0, *enHigh = 0; entryPoints.findMulti( id, enLow, enHigh ); for ( EntryMapEl *mel = enLow; mel <= enHigh; mel++ ) { /* Remove the state's sense of the link. */ mel->value->entryIds.remove( id ); mel->value->foreignInTrans -= 1; if ( misfitAccounting ) { /* If the number of foreign in transitions just went down to 0 * then take it off the main list and put it on the misfit list. */ if ( mel->value->foreignInTrans == 0 ) misfitList.append( stateList.detach( mel->value ) ); } } /* Remove the records from the entry points map. */ entryPoints.removeMulti( enLow, enHigh ); } void FsmAp::changeEntry( int id, StateAp *to, StateAp *from ) { /* Find the entry in the entry map. */ EntryMapEl *enLow = 0, *enHigh = 0; entryPoints.findMulti( id, enLow, enHigh ); while ( enLow->value != from ) enLow += 1; /* Change it to the new target. */ enLow->value = to; /* Remove from's sense of the link. */ from->entryIds.remove( id ); from->foreignInTrans -= 1; if ( misfitAccounting ) { /* If the number of foreign in transitions just went down to 0 then take * it off the main list and put it on the misfit list. */ if ( from->foreignInTrans == 0 ) misfitList.append( stateList.detach( from ) ); } /* Add to's sense of the link. */ if ( to->entryIds.insert( id ) != 0 ) { if ( misfitAccounting ) { /* If the number of foreign in transitions is about to go up to 1 then * take it off the misfit list and put it on the head list. */ if ( to->foreignInTrans == 0 ) stateList.append( misfitList.detach( to ) ); } /* Up the foreign in transitions to the state. */ to->foreignInTrans += 1; } } /* Clear all entry points from a machine. */ void FsmAp::unsetAllEntryPoints() { for ( EntryMap::Iter en = entryPoints; en.lte(); en++ ) { /* Kill all the state's entry points at once. */ if ( en->value->entryIds.length() > 0 ) { en->value->foreignInTrans -= en->value->entryIds.length(); if ( misfitAccounting ) { /* If the number of foreign in transitions just went down to 0 * then take it off the main list and put it on the misfit * list. */ if ( en->value->foreignInTrans == 0 ) misfitList.append( stateList.detach( en->value ) ); } /* Clear the set of ids out all at once. */ en->value->entryIds.empty(); } } /* Now clear out the entry map all at once. */ entryPoints.empty(); } /* Assigning an epsilon transition into final states. */ void FsmAp::epsilonTrans( int id ) { for ( StateSet::Iter fs = finStateSet; fs.lte(); fs++ ) (*fs)->epsilonTrans.append( id ); } /* Mark all states reachable from state. Traverses transitions forward. Used * for removing states that have no path into them. */ void FsmAp::markReachableFromHere( StateAp *state ) { /* Base case: return; */ if ( state->stateBits & STB_ISMARKED ) return; /* Set this state as processed. We are going to visit all states that this * state has a transition to. */ state->stateBits |= STB_ISMARKED; /* Recurse on all out transitions. */ for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { if ( trans->toState != 0 ) markReachableFromHere( trans->toState ); } } void FsmAp::markReachableFromHereStopFinal( StateAp *state ) { /* Base case: return; */ if ( state->stateBits & STB_ISMARKED ) return; /* Set this state as processed. We are going to visit all states that this * state has a transition to. */ state->stateBits |= STB_ISMARKED; /* Recurse on all out transitions. */ for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { StateAp *toState = trans->toState; if ( toState != 0 && !toState->isFinState() ) markReachableFromHereStopFinal( toState ); } } /* Mark all states reachable from state. Traverse transitions backwards. Used * for removing dead end paths in graphs. */ void FsmAp::markReachableFromHereReverse( StateAp *state ) { /* Base case: return; */ if ( state->stateBits & STB_ISMARKED ) return; /* Set this state as processed. We are going to visit all states with * transitions into this state. */ state->stateBits |= STB_ISMARKED; /* Recurse on all items in transitions. */ for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ ) markReachableFromHereReverse( trans->fromState ); } /* Determine if there are any entry points into a start state other than the * start state. Setting starting transitions requires that the start state be * isolated. In most cases a start state will already be isolated. */ bool FsmAp::isStartStateIsolated() { /* If there are any in transitions then the state is not isolated. */ if ( startState->inList.head != 0 ) return false; /* If there are any entry points then isolated. */ if ( startState->entryIds.length() > 0 ) return false; return true; } /* Bring in other's entry points. Assumes others states are going to be * copied into this machine. */ void FsmAp::copyInEntryPoints( FsmAp *other ) { /* Use insert multi because names are not unique. */ for ( EntryMap::Iter en = other->entryPoints; en.lte(); en++ ) entryPoints.insertMulti( en->key, en->value ); } void FsmAp::unsetAllFinStates() { for ( StateSet::Iter st = finStateSet; st.lte(); st++ ) (*st)->stateBits &= ~ STB_ISFINAL; finStateSet.empty(); } void FsmAp::setFinBits( int finStateBits ) { for ( int s = 0; s < finStateSet.length(); s++ ) finStateSet.data[s]->stateBits |= finStateBits; } /* Tests the integrity of the transition lists and the fromStates. */ void FsmAp::verifyIntegrity() { for ( StateList::Iter state = stateList; state.lte(); state++ ) { /* Walk the out transitions and assert fromState is correct. */ for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) assert( trans->fromState == state ); /* Walk the inlist and assert toState is correct. */ for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ ) assert( trans->toState == state ); } } void FsmAp::verifyReachability() { /* Mark all the states that can be reached * through the set of entry points. */ markReachableFromHere( startState ); for ( EntryMap::Iter en = entryPoints; en.lte(); en++ ) markReachableFromHere( en->value ); /* Check that everything got marked. */ for ( StateList::Iter st = stateList; st.lte(); st++ ) { /* Assert it got marked and then clear the mark. */ assert( st->stateBits & STB_ISMARKED ); st->stateBits &= ~ STB_ISMARKED; } } void FsmAp::verifyNoDeadEndStates() { /* Mark all states that have paths to the final states. */ for ( StateSet::Iter pst = finStateSet; pst.lte(); pst++ ) markReachableFromHereReverse( *pst ); /* Start state gets honorary marking. Must be done AFTER recursive call. */ startState->stateBits |= STB_ISMARKED; /* Make sure everything got marked. */ for ( StateList::Iter st = stateList; st.lte(); st++ ) { /* Assert the state got marked and unmark it. */ assert( st->stateBits & STB_ISMARKED ); st->stateBits &= ~ STB_ISMARKED; } } void FsmAp::depthFirstOrdering( StateAp *state ) { /* Nothing to do if the state is already on the list. */ if ( state->stateBits & STB_ONLIST ) return; /* Doing depth first, put state on the list. */ state->stateBits |= STB_ONLIST; stateList.append( state ); /* Recurse on everything ranges. */ for ( TransList::Iter tel = state->outList; tel.lte(); tel++ ) { if ( tel->toState != 0 ) depthFirstOrdering( tel->toState ); } } /* Ordering states by transition connections. */ void FsmAp::depthFirstOrdering() { /* Init on state list flags. */ for ( StateList::Iter st = stateList; st.lte(); st++ ) st->stateBits &= ~STB_ONLIST; /* Clear out the state list, we will rebuild it. */ int stateListLen = stateList.length(); stateList.abandon(); /* Add back to the state list from the start state and all other entry * points. */ if ( errState != 0 ) depthFirstOrdering( errState ); depthFirstOrdering( startState ); for ( EntryMap::Iter en = entryPoints; en.lte(); en++ ) depthFirstOrdering( en->value ); /* Make sure we put everything back on. */ assert( stateListLen == stateList.length() ); } /* Stable sort the states by final state status. */ void FsmAp::sortStatesByFinal() { /* Move forward through the list and throw final states onto the end. */ StateAp *state = 0; StateAp *next = stateList.head; StateAp *last = stateList.tail; while ( state != last ) { /* Move forward and load up the next. */ state = next; next = state->next; /* Throw to the end? */ if ( state->isFinState() ) { stateList.detach( state ); stateList.append( state ); } } } void FsmAp::setStateNumbers( int base ) { for ( StateList::Iter state = stateList; state.lte(); state++ ) state->alg.stateNum = base++; } bool FsmAp::checkErrTrans( StateAp *state, TransAp *trans ) { /* Might go directly to error state. */ if ( trans->toState == 0 ) return true; if ( trans->prev == 0 ) { /* If this is the first transition. */ if ( keyOps->minKey < trans->lowKey ) return true; } else { /* Not the first transition. Compare against the prev. */ TransAp *prev = trans->prev; Key nextKey = prev->highKey; nextKey.increment(); if ( nextKey < trans->lowKey ) return true; } return false; } bool FsmAp::checkErrTransFinish( StateAp *state ) { /* Check if there are any ranges already. */ if ( state->outList.length() == 0 ) return true; else { /* Get the last and check for a gap on the end. */ TransAp *last = state->outList.tail; if ( last->highKey < keyOps->maxKey ) return true; } return 0; } bool FsmAp::hasErrorTrans() { bool result; for ( StateList::Iter st = stateList; st.lte(); st++ ) { for ( TransList::Iter tr = st->outList; tr.lte(); tr++ ) { result = checkErrTrans( st, tr ); if ( result ) return true; } result = checkErrTransFinish( st ); if ( result ) return true; } return false; }