/*
- * Copyright 2001 Adrian Thurston <thurston@cs.queensu.ca>
+ * Copyright 2001-2007 Adrian Thurston <thurston@cs.queensu.ca>
*/
/* This file is part of Ragel.
:
/* 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
* pointers will be resolved later. */
entryPoints(graph.entryPoints),
startState(graph.startState),
+ errState(0),
/* Will be filled by copy. */
finStateSet(),
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. */
void FsmAp::setFinState( StateAp *state )
{
/* Is it already a fin state. */
- if ( state->stateBits & SB_ISFINAL )
+ if ( state->stateBits & STB_ISFINAL )
return;
- state->stateBits |= SB_ISFINAL;
+ state->stateBits |= STB_ISFINAL;
finStateSet.insert( state );
}
void FsmAp::unsetFinState( StateAp *state )
{
/* Is it already a non-final state? */
- if ( ! (state->stateBits & SB_ISFINAL) )
+ 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 &= ~ SB_ISFINAL;
+ state->stateBits &= ~ STB_ISFINAL;
finStateSet.remove( state );
}
void FsmAp::markReachableFromHere( StateAp *state )
{
/* Base case: return; */
- if ( state->stateBits & SB_ISMARKED )
+ 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 |= SB_ISMARKED;
+ state->stateBits |= STB_ISMARKED;
/* Recurse on all out transitions. */
for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
void FsmAp::markReachableFromHereStopFinal( StateAp *state )
{
/* Base case: return; */
- if ( state->stateBits & SB_ISMARKED )
+ 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 |= SB_ISMARKED;
+ state->stateBits |= STB_ISMARKED;
/* Recurse on all out transitions. */
for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
void FsmAp::markReachableFromHereReverse( StateAp *state )
{
/* Base case: return; */
- if ( state->stateBits & SB_ISMARKED )
+ 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 |= SB_ISMARKED;
+ state->stateBits |= STB_ISMARKED;
/* Recurse on all items in transitions. */
for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ )
entryPoints.insertMulti( en->key, en->value );
}
-void FsmAp::setStateNumbers()
-{
- int curNum = 0;
- StateList::Iter state = stateList;
- for ( ; state.lte(); state++ )
- state->alg.stateNum = curNum++;
-}
-
void FsmAp::unsetAllFinStates()
{
for ( StateSet::Iter st = finStateSet; st.lte(); st++ )
- (*st)->stateBits &= ~ SB_ISFINAL;
+ (*st)->stateBits &= ~ STB_ISFINAL;
finStateSet.empty();
}
/* 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 & SB_ISMARKED );
- st->stateBits &= ~ SB_ISMARKED;
+ assert( st->stateBits & STB_ISMARKED );
+ st->stateBits &= ~ STB_ISMARKED;
}
}
markReachableFromHereReverse( *pst );
/* Start state gets honorary marking. Must be done AFTER recursive call. */
- startState->stateBits |= SB_ISMARKED;
+ 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 & SB_ISMARKED );
- st->stateBits &= ~ SB_ISMARKED;
+ 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;
}
projects / external / ragel.git / blobdiff