diff options
Diffstat (limited to 'src/libfsm/fsmap.cc')
| -rw-r--r-- | src/libfsm/fsmap.cc | 1200 |
1 files changed, 1200 insertions, 0 deletions
diff --git a/src/libfsm/fsmap.cc b/src/libfsm/fsmap.cc new file mode 100644 index 00000000..98863f52 --- /dev/null +++ b/src/libfsm/fsmap.cc @@ -0,0 +1,1200 @@ +/* + * Copyright 2002-2018 Adrian Thurston <thurston@colm.net> + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include "fsmgraph.h" +#include <iostream> +using std::endl; + +/* Insert an action into an action table. */ +void ActionTable::setAction( int ordering, Action *action ) +{ + /* Multi-insert in case specific instances of an action appear in a + * transition more than once. */ + insertMulti( ordering, action ); +} + +/* Set all the action from another action table in this table. */ +void ActionTable::setActions( const ActionTable &other ) +{ + for ( ActionTable::Iter action = other; action.lte(); action++ ) + insertMulti( action->key, action->value ); +} + +void ActionTable::setActions( int *orderings, Action **actions, int nActs ) +{ + for ( int a = 0; a < nActs; a++ ) + insertMulti( orderings[a], actions[a] ); +} + +bool ActionTable::hasAction( Action *action ) +{ + for ( int a = 0; a < length(); a++ ) { + if ( data[a].value == action ) + return true; + } + return false; +} + +/* Insert an action into an action table. */ +void LmActionTable::setAction( int ordering, FsmLongestMatchPart *action ) +{ + /* Multi-insert in case specific instances of an action appear in a + * transition more than once. */ + insertMulti( ordering, action ); +} + +/* Set all the action from another action table in this table. */ +void LmActionTable::setActions( const LmActionTable &other ) +{ + for ( LmActionTable::Iter action = other; action.lte(); action++ ) + insertMulti( action->key, action->value ); +} + +void ErrActionTable::setAction( int ordering, Action *action, int transferPoint ) +{ + insertMulti( ErrActionTableEl( action, ordering, transferPoint ) ); +} + +void ErrActionTable::setActions( const ErrActionTable &other ) +{ + for ( ErrActionTable::Iter act = other; act.lte(); act++ ) + insertMulti( ErrActionTableEl( act->action, act->ordering, act->transferPoint ) ); +} + +/* Insert a priority into this priority table. Looks out for priorities on + * duplicate keys. */ +void PriorTable::setPrior( int ordering, PriorDesc *desc ) +{ + PriorEl *lastHit = 0; + PriorEl *insed = insert( PriorEl(ordering, desc), &lastHit ); + if ( insed == 0 ) { + /* This already has a priority on the same key as desc. Overwrite the + * priority if the ordering is larger (later in time). */ + if ( ordering >= lastHit->ordering ) + *lastHit = PriorEl( ordering, desc ); + } +} + +/* Set all the priorities from a priorTable in this table. */ +void PriorTable::setPriors( const PriorTable &other ) +{ + /* Loop src priorities once to overwrite duplicates. */ + PriorTable::Iter priorIt = other; + for ( ; priorIt.lte(); priorIt++ ) + setPrior( priorIt->ordering, priorIt->desc ); +} + +/* Set the priority of starting transitions. Isolates the start state so it has + * no other entry points, then sets the priorities of all the transitions out + * of the start state. If the start state is final, then the outPrior of the + * start state is also set. The idea is that a machine that accepts the null + * string can still specify the starting trans prior for when it accepts the + * null word. */ +void FsmAp::startFsmPrior( int ordering, PriorDesc *prior ) +{ + /* Make sure the start state has no other entry points. */ + isolateStartState( this ); + + /* Walk all transitions out of the start state. */ + for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) { + if ( trans->tdap()->toState != 0 ) + trans->tdap()->priorTable.setPrior( ordering, prior ); + } + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) { + if ( cond->toState != 0 ) + cond->priorTable.setPrior( ordering, prior ); + } + } + } + + if ( startState->nfaOut != 0 ) { + for ( NfaTransList::Iter na = *startState->nfaOut; na.lte(); na++ ) + na->priorTable.setPrior( ordering, prior ); + } + + /* If the new start state is final then set the out priority. This follows + * the same convention as setting start action in the out action table of + * a final start state. */ + if ( startState->stateBits & STB_ISFINAL ) + startState->outPriorTable.setPrior( ordering, prior ); + + /* Start fsm priorities are a special case that may require + * minimization afterwards. */ + afterOpMinimize( true ); +} + +/* Set the priority of all transitions in a graph. Walks all transition lists + * and all def transitions. */ +void FsmAp::allTransPrior( int ordering, PriorDesc *prior ) +{ + /* Walk the list of all states. */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + /* Walk the out list of the state. */ + for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) { + if ( trans->tdap()->toState != 0 ) + trans->tdap()->priorTable.setPrior( ordering, prior ); + } + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) { + if ( cond->toState != 0 ) + cond->priorTable.setPrior( ordering, prior ); + } + } + } + + if ( state->nfaOut != 0 ) { + for ( NfaTransList::Iter na = *state->nfaOut; na.lte(); na++ ) + na->priorTable.setPrior( ordering, prior ); + } + } +} + +/* Set the priority of all transitions that go into a final state. Note that if + * any entry states are final, we will not be setting the priority of any + * transitions that may go into those states in the future. The graph does not + * support pending in transitions in the same way pending out transitions are + * supported. */ +void FsmAp::finishFsmPrior( int ordering, PriorDesc *prior ) +{ + /* Walk all final states. */ + for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) { + /* Walk all in transitions of the final state. */ + for ( TransInList::Iter t = (*state)->inTrans; t.lte(); t++ ) + t->priorTable.setPrior( ordering, prior ); + for ( CondInList::Iter t = (*state)->inCond; t.lte(); t++ ) + t->priorTable.setPrior( ordering, prior ); + + if ( (*state)->nfaIn != 0 ) { + for ( NfaInList::Iter na = *(*state)->nfaIn; na.lte(); na++ ) + na->priorTable.setPrior( ordering, prior ); + } + } +} + +/* Set the priority of any future out transitions that may be made going out of + * this state machine. */ +void FsmAp::leaveFsmPrior( int ordering, PriorDesc *prior ) +{ + /* Set priority in all final states. */ + for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) + (*state)->outPriorTable.setPrior( ordering, prior ); +} + + +/* Set actions to execute on starting transitions. Isolates the start state + * so it has no other entry points, then adds to the transition functions + * of all the transitions out of the start state. If the start state is final, + * then the func is also added to the start state's out func list. The idea is + * that a machine that accepts the null string can execute a start func when it + * matches the null word, which can only be done when leaving the start/final + * state. */ +void FsmAp::startFsmAction( int ordering, Action *action ) +{ + /* Make sure the start state has no other entry points. */ + isolateStartState( this ); + + /* Walk the start state's transitions, setting functions. */ + for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) { + if ( trans->tdap()->toState != 0 ) + trans->tdap()->actionTable.setAction( ordering, action ); + } + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) { + if ( cond->toState != 0 ) + cond->actionTable.setAction( ordering, action ); + } + } + } + + /* If start state is final then add the action to the out action table. + * This means that when the null string is accepted the start action will + * not be bypassed. */ + if ( startState->stateBits & STB_ISFINAL ) + startState->outActionTable.setAction( ordering, action ); + + if ( startState->nfaOut != 0 ) { + for ( NfaTransList::Iter na = *startState->nfaOut; na.lte(); na++ ) { + + StateAp *state = na->toState; + + /* Walk the start state's transitions, setting functions. */ + for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) { + if ( trans->tdap()->toState != 0 ) + trans->tdap()->actionTable.setAction( ordering, action ); + } + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) { + if ( cond->toState != 0 ) + cond->actionTable.setAction( ordering, action ); + } + } + } + + /* If start state is final then add the action to the out action table. + * This means that when the null string is accepted the start action will + * not be bypassed. */ + if ( state->stateBits & STB_ISFINAL ) + state->outActionTable.setAction( ordering, action ); + + } + } + + afterOpMinimize( true ); +} + +/* Set functions to execute on all transitions. Walks the out lists of all + * states. */ +void FsmAp::allTransAction( int ordering, Action *action ) +{ + /* Walk all states. */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + /* Walk the out list of the state. */ + for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) { + if ( trans->tdap()->toState != 0 ) + trans->tdap()->actionTable.setAction( ordering, action ); + } + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) { + if ( cond->toState != 0 ) + cond->actionTable.setAction( ordering, action ); + } + } + } + } +} + +/* Specify functions to execute upon entering final states. If the start state + * is final we can't really specify a function to execute upon entering that + * final state the first time. So function really means whenever entering a + * final state from within the same fsm. */ +void FsmAp::finishFsmAction( int ordering, Action *action ) +{ + /* Walk all final states. */ + for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) { + /* Walk the final state's in list. */ + for ( TransInList::Iter t = (*state)->inTrans; t.lte(); t++ ) + t->actionTable.setAction( ordering, action ); + for ( CondInList::Iter t = (*state)->inCond; t.lte(); t++ ) + t->actionTable.setAction( ordering, action ); + } +} + +/* Add functions to any future out transitions that may be made going out of + * this state machine. */ +void FsmAp::leaveFsmAction( int ordering, Action *action ) +{ + /* Insert the action in the outActionTable of all final states. */ + for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) + (*state)->outActionTable.setAction( ordering, action ); +} + +/* Add functions to the longest match action table for constructing scanners. */ +void FsmAp::longMatchAction( int ordering, FsmLongestMatchPart *lmPart ) +{ + /* Walk all final states. */ + for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) { + /* Walk the final state's in list. */ + for ( TransInList::Iter t = (*state)->inTrans; t.lte(); t++ ) + t->lmActionTable.setAction( ordering, lmPart ); + for ( CondInList::Iter t = (*state)->inCond; t.lte(); t++ ) + t->lmActionTable.setAction( ordering, lmPart ); + } +} + +void FsmAp::fillGaps( StateAp *state ) +{ + /* + * First pass fills in the the caps between transitions. + */ + if ( state->outList.length() == 0 ) { + /* Add the range on the lower and upper bound. */ + attachNewTrans( state, 0, ctx->keyOps->minKey, ctx->keyOps->maxKey ); + } + else { + TransList srcList; + srcList.transfer( state->outList ); + + /* Check for a gap at the beginning. */ + TransList::Iter trans = srcList, next; + if ( ctx->keyOps->lt( ctx->keyOps->minKey, trans->lowKey ) ) { + /* Make the high key and append. */ + Key highKey = trans->lowKey; + ctx->keyOps->decrement( highKey ); + + attachNewTrans( state, 0, ctx->keyOps->minKey, highKey ); + } + + /* Write the transition. */ + next = trans.next(); + state->outList.append( trans ); + + /* Keep the last high end. */ + Key lastHigh = trans->highKey; + + /* Loop each source range. */ + for ( trans = next; trans.lte(); trans = next ) { + /* Make the next key following the last range. */ + Key nextKey = lastHigh; + ctx->keyOps->increment( nextKey ); + + /* Check for a gap from last up to here. */ + if ( ctx->keyOps->lt( nextKey, trans->lowKey ) ) { + /* Make the high end of the range that fills the gap. */ + Key highKey = trans->lowKey; + ctx->keyOps->decrement( highKey ); + + attachNewTrans( state, 0, nextKey, highKey ); + } + + /* Reduce the transition. If it reduced to anything then add it. */ + next = trans.next(); + state->outList.append( trans ); + + /* Keep the last high end. */ + lastHigh = trans->highKey; + } + + /* Now check for a gap on the end to fill. */ + if ( ctx->keyOps->lt( lastHigh, ctx->keyOps->maxKey ) ) { + /* Get a copy of the default. */ + ctx->keyOps->increment( lastHigh ); + + attachNewTrans( state, 0, lastHigh, ctx->keyOps->maxKey ); + } + } + + /* + * Second pass fills in gaps in condition lists. + */ + for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) + continue; + + CondList srcList; + srcList.transfer( trans->tcap()->condList ); + + CondList::Iter cond = srcList, next; + + /* Check for gap at the beginning. */ + if ( cond->key > 0 ) { + for ( CondKey key = 0; key < cond->key; key.increment() ) + attachNewCond( trans, state, 0, key ); + } + + next = cond.next(); + trans->tcap()->condList.append( cond ); + + CondKey lastKey = cond->key; + + for ( cond = next; cond.lte(); cond = next ) { + /* Make the next key following the last range. */ + CondKey nextKey = lastKey; + nextKey.increment(); + + /* Check for a gap from last up to here. */ + if ( nextKey < cond->key ) { + for ( CondKey key = nextKey; key < cond->key; key.increment() ) + attachNewCond( trans, state, 0, key ); + } + + next = cond.next(); + trans->tcap()->condList.append( cond ); + + lastKey = cond->key; + } + + CondKey high = (trans->condSpace == 0) ? + 0 : (1 << trans->condSpace->condSet.length()); + + /* Now check for a gap on the end to fill. */ + if ( lastKey < high ) { + /* Get a copy of the default. */ + lastKey.increment(); + + for ( CondKey key = lastKey; key < high; key.increment() ) + attachNewCond( trans, state, 0, key ); + } + } +} + +void FsmAp::setErrorActions( StateAp *state, const ActionTable &other ) +{ + /* Fill any gaps in the out list with an error transition. */ + fillGaps( state ); + + /* Set error transitions in the transitions that go to error. */ + for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) { + if ( trans->tdap()->toState == 0 ) + trans->tdap()->actionTable.setActions( other ); + } + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) { + if ( cond->toState == 0 ) + cond->actionTable.setActions( other ); + } + } + } +} + +void FsmAp::setErrorAction( StateAp *state, int ordering, Action *action ) +{ + /* Fill any gaps in the out list with an error transition. */ + fillGaps( state ); + + /* Set error transitions in the transitions that go to error. */ + for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) { + if ( trans->tdap()->toState == 0 ) + trans->tdap()->actionTable.setAction( ordering, action ); + } + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) { + if ( cond->toState == 0 ) + cond->actionTable.setAction( ordering, action ); + } + } + } +} + + +/* Give a target state for error transitions. */ +void FsmAp::setErrorTarget( StateAp *state, StateAp *target, int *orderings, + Action **actions, int nActs ) +{ + /* Fill any gaps in the out list with an error transition. */ + fillGaps( state ); + + /* Set error target in the transitions that go to error. */ + for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) { + if ( trans->tdap()->toState == 0 ) { + /* The trans goes to error, redirect it. */ + redirectErrorTrans( trans->tdap()->fromState, target, trans->tdap() ); + trans->tdap()->actionTable.setActions( orderings, actions, nActs ); + } + } + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) { + if ( cond->toState == 0 ) { + /* The trans goes to error, redirect it. */ + redirectErrorTrans( cond->fromState, target, cond ); + cond->actionTable.setActions( orderings, actions, nActs ); + } + } + } + } +} + +void FsmAp::transferOutActions( StateAp *state ) +{ + for ( ActionTable::Iter act = state->outActionTable; act.lte(); act++ ) + state->eofActionTable.setAction( act->key, act->value ); + state->outActionTable.empty(); +} + +void FsmAp::transferErrorActions( StateAp *state, int transferPoint ) +{ + for ( int i = 0; i < state->errActionTable.length(); ) { + ErrActionTableEl *act = state->errActionTable.data + i; + if ( act->transferPoint == transferPoint ) { + /* Transfer the error action and remove it. */ + setErrorAction( state, act->ordering, act->action ); + if ( ! state->isFinState() ) + state->eofActionTable.setAction( act->ordering, act->action ); + state->errActionTable.vremove( i ); + } + else { + /* Not transfering and deleting, skip over the item. */ + i += 1; + } + } +} + +/* Set error actions in the start state. */ +void FsmAp::startErrorAction( int ordering, Action *action, int transferPoint ) +{ + /* Make sure the start state has no other entry points. */ + isolateStartState( this ); + + /* Add the actions. */ + startState->errActionTable.setAction( ordering, action, transferPoint ); + + afterOpMinimize( true ); +} + +/* Set error actions in all states where there is a transition out. */ +void FsmAp::allErrorAction( int ordering, Action *action, int transferPoint ) +{ + /* Insert actions in the error action table of all states. */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) + state->errActionTable.setAction( ordering, action, transferPoint ); +} + +/* Set error actions in final states. */ +void FsmAp::finalErrorAction( int ordering, Action *action, int transferPoint ) +{ + /* Add the action to the error table of final states. */ + for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) + (*state)->errActionTable.setAction( ordering, action, transferPoint ); +} + +void FsmAp::notStartErrorAction( int ordering, Action *action, int transferPoint ) +{ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( state != startState ) + state->errActionTable.setAction( ordering, action, transferPoint ); + } +} + +void FsmAp::notFinalErrorAction( int ordering, Action *action, int transferPoint ) +{ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( ! state->isFinState() ) + state->errActionTable.setAction( ordering, action, transferPoint ); + } +} + +/* Set error actions in the states that have transitions into a final state. */ +void FsmAp::middleErrorAction( int ordering, Action *action, int transferPoint ) +{ + /* Isolate the start state in case it is reachable from in inside the + * machine, in which case we don't want it set. */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( state != startState && ! state->isFinState() ) + state->errActionTable.setAction( ordering, action, transferPoint ); + } +} + +/* Set EOF actions in the start state. */ +void FsmAp::startEOFAction( int ordering, Action *action ) +{ + /* Make sure the start state has no other entry points. */ + isolateStartState( this ); + + /* Add the actions. */ + startState->eofActionTable.setAction( ordering, action ); + + afterOpMinimize( true ); +} + +/* Set EOF actions in all states where there is a transition out. */ +void FsmAp::allEOFAction( int ordering, Action *action ) +{ + /* Insert actions in the EOF action table of all states. */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) + state->eofActionTable.setAction( ordering, action ); +} + +/* Set EOF actions in final states. */ +void FsmAp::finalEOFAction( int ordering, Action *action ) +{ + /* Add the action to the error table of final states. */ + for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) + (*state)->eofActionTable.setAction( ordering, action ); +} + +void FsmAp::notStartEOFAction( int ordering, Action *action ) +{ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( state != startState ) + state->eofActionTable.setAction( ordering, action ); + } +} + +void FsmAp::notFinalEOFAction( int ordering, Action *action ) +{ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( ! state->isFinState() ) + state->eofActionTable.setAction( ordering, action ); + } +} + +/* Set EOF actions in the states that have transitions into a final state. */ +void FsmAp::middleEOFAction( int ordering, Action *action ) +{ + /* Set the actions in all states that are not the start state and not final. */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( state != startState && ! state->isFinState() ) + state->eofActionTable.setAction( ordering, action ); + } +} + +/* + * Set To State Actions. + */ + +/* Set to state actions in the start state. */ +void FsmAp::startToStateAction( int ordering, Action *action ) +{ + /* Make sure the start state has no other entry points. */ + isolateStartState( this ); + + startState->toStateActionTable.setAction( ordering, action ); + + afterOpMinimize( true ); +} + +/* Set to state actions in all states. */ +void FsmAp::allToStateAction( int ordering, Action *action ) +{ + /* Insert the action on all states. */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) + state->toStateActionTable.setAction( ordering, action ); +} + +/* Set to state actions in final states. */ +void FsmAp::finalToStateAction( int ordering, Action *action ) +{ + /* Add the action to the error table of final states. */ + for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) + (*state)->toStateActionTable.setAction( ordering, action ); +} + +void FsmAp::notStartToStateAction( int ordering, Action *action ) +{ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( state != startState ) + state->toStateActionTable.setAction( ordering, action ); + } +} + +void FsmAp::notFinalToStateAction( int ordering, Action *action ) +{ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( ! state->isFinState() ) + state->toStateActionTable.setAction( ordering, action ); + } +} + +/* Set to state actions in states that are not final and not the start state. */ +void FsmAp::middleToStateAction( int ordering, Action *action ) +{ + /* Set the action in all states that are not the start state and not final. */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( state != startState && ! state->isFinState() ) + state->toStateActionTable.setAction( ordering, action ); + } +} + +/* + * Set From State Actions. + */ + +void FsmAp::startFromStateAction( int ordering, Action *action ) +{ + /* Make sure the start state has no other entry points. */ + isolateStartState( this ); + + startState->fromStateActionTable.setAction( ordering, action ); + + afterOpMinimize( true ); +} + +void FsmAp::allFromStateAction( int ordering, Action *action ) +{ + /* Insert the action on all states. */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) + state->fromStateActionTable.setAction( ordering, action ); +} + +void FsmAp::finalFromStateAction( int ordering, Action *action ) +{ + /* Add the action to the error table of final states. */ + for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) + (*state)->fromStateActionTable.setAction( ordering, action ); +} + +void FsmAp::notStartFromStateAction( int ordering, Action *action ) +{ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( state != startState ) + state->fromStateActionTable.setAction( ordering, action ); + } +} + +void FsmAp::notFinalFromStateAction( int ordering, Action *action ) +{ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( ! state->isFinState() ) + state->fromStateActionTable.setAction( ordering, action ); + } +} + +void FsmAp::middleFromStateAction( int ordering, Action *action ) +{ + /* Set the action in all states that are not the start state and not final. */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + if ( state != startState && ! state->isFinState() ) + state->fromStateActionTable.setAction( ordering, action ); + } +} + +/* Shift the function ordering of the start transitions to start + * at fromOrder and increase in units of 1. Useful before staring. + * Returns the maximum number of order numbers used. */ +int FsmAp::shiftStartActionOrder( int fromOrder ) +{ + int maxUsed = 0; + + /* Walk the start state's transitions, shifting function ordering. */ + for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) { + int curFromOrder = fromOrder; + ActionTable::Iter action = trans->tdap()->actionTable; + for ( ; action.lte(); action++ ) + action->key = curFromOrder++; + + /* Keep track of the max number of orders used. */ + if ( curFromOrder - fromOrder > maxUsed ) + maxUsed = curFromOrder - fromOrder; + } + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) { + /* Walk the function data for the transition and set the keys to + * increasing values starting at fromOrder. */ + int curFromOrder = fromOrder; + ActionTable::Iter action = cond->actionTable; + for ( ; action.lte(); action++ ) + action->key = curFromOrder++; + + /* Keep track of the max number of orders used. */ + if ( curFromOrder - fromOrder > maxUsed ) + maxUsed = curFromOrder - fromOrder; + } + } + } + + return maxUsed; +} + +/* Remove all priorities. */ +void FsmAp::clearAllPriorities() +{ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + /* Clear out priority data. */ + state->outPriorTable.empty(); + + /* Clear transition data from the out transitions. */ + for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) + trans->tdap()->priorTable.empty(); + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) + cond->priorTable.empty(); + } + } + + if ( state->nfaIn != 0 ) { + for ( NfaInList::Iter na = *state->nfaIn; na.lte(); na++ ) + na->priorTable.empty(); + } + } +} + +/* Zeros out the function ordering keys. This may be called before minimization + * when it is known that no more fsm operations are going to be done. This + * will achieve greater reduction as states will not be separated on the basis + * of function ordering. */ +void FsmAp::nullActionKeys( ) +{ + /* For each state... */ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + /* Walk the transitions for the state. */ + for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) { + if ( trans->plain() ) { + /* Walk the action table for the transition. */ + for ( ActionTable::Iter action = trans->tdap()->actionTable; + action.lte(); action++ ) + action->key = 0; + + /* Walk the action table for the transition. */ + for ( LmActionTable::Iter action = trans->tdap()->lmActionTable; + action.lte(); action++ ) + action->key = 0; + } + else { + for ( CondList::Iter cond = trans->tcap()->condList; cond.lte(); cond++ ) { + /* Walk the action table for the transition. */ + for ( ActionTable::Iter action = cond->actionTable; + action.lte(); action++ ) + action->key = 0; + + /* Walk the action table for the transition. */ + for ( LmActionTable::Iter action = cond->lmActionTable; + action.lte(); action++ ) + action->key = 0; + } + } + } + + /* Null the action keys of the to state action table. */ + for ( ActionTable::Iter action = state->toStateActionTable; + action.lte(); action++ ) + action->key = 0; + + /* Null the action keys of the from state action table. */ + for ( ActionTable::Iter action = state->fromStateActionTable; + action.lte(); action++ ) + action->key = 0; + + /* Null the action keys of the out transtions. */ + for ( ActionTable::Iter action = state->outActionTable; + action.lte(); action++ ) + action->key = 0; + + /* Null the action keys of the error action table. */ + for ( ErrActionTable::Iter action = state->errActionTable; + action.lte(); action++ ) + action->ordering = 0; + + /* Null the action keys eof action table. */ + for ( ActionTable::Iter action = state->eofActionTable; + action.lte(); action++ ) + action->key = 0; + } +} + +/* Walk the list of states and verify that non final states do not have out + * data, that all stateBits are cleared, and that there are no states with + * zero foreign in transitions. */ +void FsmAp::verifyStates() +{ + for ( StateList::Iter state = stateList; state.lte(); state++ ) { + /* Non final states should not have leaving data. */ + if ( ! (state->stateBits & STB_ISFINAL) ) { + assert( state->outActionTable.length() == 0 ); + assert( state->outCondSpace == 0 ); + assert( state->outCondKeys.length() == 0 ); + assert( state->outPriorTable.length() == 0 ); + } + + /* Data used in algorithms should be cleared. */ + assert( (state->stateBits & STB_BOTH) == 0 ); + assert( state->foreignInTrans > 0 ); + } +} + +/* Compare two transitions according to their relative priority. Since the + * base transition has no priority associated with it, the default is to + * return equal. */ +int FsmAp::comparePrior( const PriorTable &priorTable1, const PriorTable &priorTable2 ) +{ + /* Looking for differing priorities on same keys. Need to concurrently + * scan the priority lists. */ + PriorTable::Iter pd1 = priorTable1; + PriorTable::Iter pd2 = priorTable2; + while ( pd1.lte() && pd2.lte() ) { + /* Check keys. */ + if ( pd1->desc->key < pd2->desc->key ) + pd1.increment(); + else if ( pd1->desc->key > pd2->desc->key ) + pd2.increment(); + /* Keys are the same, check priorities. */ + else if ( pd1->desc->priority < pd2->desc->priority ) { + if ( ctx->checkPriorInteraction && pd1->desc->guarded ) { + if ( ! priorInteraction ) { + priorInteraction = true; + guardId = pd1->desc->guardId; + } + } + return -1; + } + else if ( pd1->desc->priority > pd2->desc->priority ) { + if ( ctx->checkPriorInteraction && pd1->desc->guarded ) { + if ( ! priorInteraction ) { + priorInteraction = true; + guardId = pd1->desc->guardId; + } + } + return 1; + } + else { + /* Keys and priorities are equal, advance both. */ + pd1.increment(); + pd2.increment(); + } + } + + /* No differing priorities on the same key. */ + return 0; +} + +int FsmAp::compareCondListBitElim( const CondList &condList1, const CondList &condList2 ) +{ + typedef ValPairIter< PiList<CondAp> > ValPairIterPiListCondAp; + ValPairIterPiListCondAp outPair( condList1, condList2 ); + for ( ; !outPair.end(); outPair++ ) { + switch ( outPair.userState ) { + case ValPairIterPiListCondAp::RangeInS1: { + int compareRes = FsmAp::compareCondBitElimPtr<CondAp>( outPair.s1Tel.trans, 0 ); + if ( compareRes != 0 ) + return compareRes; + break; + } + case ValPairIterPiListCondAp::RangeInS2: { + int compareRes = FsmAp::compareCondBitElimPtr<CondAp>( 0, outPair.s2Tel.trans ); + if ( compareRes != 0 ) + return compareRes; + break; + } + case ValPairIterPiListCondAp::RangeOverlap: { + int compareRes = FsmAp::compareCondBitElimPtr<CondAp>( + outPair.s1Tel.trans, outPair.s2Tel.trans ); + if ( compareRes != 0 ) + return compareRes; + break; + }} + } + return 0; +} + +/* Compares two transitions according to priority and functions. Pointers + * should not be null. Does not consider to state or from state. Compare two + * transitions according to the data contained in the transitions. Data means + * any properties added to user transitions that may differentiate them. Since + * the base transition has no data, the default is to return equal. */ +int FsmAp::compareTransData( TransAp *trans1, TransAp *trans2 ) +{ + if ( trans1->condSpace < trans2->condSpace ) + return -1; + else if ( trans2->condSpace < trans1->condSpace ) + return 1; + + if ( trans1->plain() ) { + int compareRes = FsmAp::compareCondDataPtr( trans1->tdap(), trans2->tdap() ); + if ( compareRes != 0 ) + return compareRes; + } + else { + typedef ValPairIter< PiList<CondAp> > ValPairIterPiListCondAp; + ValPairIterPiListCondAp outPair( trans1->tcap()->condList, + trans2->tcap()->condList ); + for ( ; !outPair.end(); outPair++ ) { + switch ( outPair.userState ) { + case ValPairIterPiListCondAp::RangeInS1: { + int compareRes = FsmAp::compareCondDataPtr<CondAp>( outPair.s1Tel.trans, 0 ); + if ( compareRes != 0 ) + return compareRes; + break; + } + case ValPairIterPiListCondAp::RangeInS2: { + int compareRes = FsmAp::compareCondDataPtr<CondAp>( 0, outPair.s2Tel.trans ); + if ( compareRes != 0 ) + return compareRes; + break; + } + case ValPairIterPiListCondAp::RangeOverlap: { + int compareRes = FsmAp::compareCondDataPtr<CondAp>( + outPair.s1Tel.trans, outPair.s2Tel.trans ); + if ( compareRes != 0 ) + return compareRes; + break; + }} + } + } + return 0; +} + +/* Compares two transitions according to priority and functions. Pointers + * should not be null. Does not consider to state or from state. Compare two + * transitions according to the data contained in the transitions. Data means + * any properties added to user transitions that may differentiate them. Since + * the base transition has no data, the default is to return equal. */ +template< class Trans > int FsmAp::compareCondData( Trans *trans1, Trans *trans2 ) +{ + /* Compare the prior table. */ + int cmpRes = CmpPriorTable::compare( trans1->priorTable, + trans2->priorTable ); + if ( cmpRes != 0 ) + return cmpRes; + + /* Compare longest match action tables. */ + cmpRes = CmpLmActionTable::compare(trans1->lmActionTable, + trans2->lmActionTable); + if ( cmpRes != 0 ) + return cmpRes; + + /* Compare action tables. */ + return CmpActionTable::compare(trans1->actionTable, + trans2->actionTable); +} + +/* Compares two transitions according to priority and functions. Pointers + * should not be null. Does not consider to state or from state. Compare two + * transitions according to the data contained in the transitions. Data means + * any properties added to user transitions that may differentiate them. Since + * the base transition has no data, the default is to return equal. */ +template< class Trans > int FsmAp::compareCondBitElim( Trans *trans1, Trans *trans2 ) +{ + if ( trans1->toState < trans2->toState ) + return -1; + else if ( trans1->toState > trans2->toState ) + return 1; + + /* Compare the prior table. */ + int cmpRes = CmpPriorTable::compare( trans1->priorTable, + trans2->priorTable ); + if ( cmpRes != 0 ) + return cmpRes; + + /* Compare longest match action tables. */ + cmpRes = CmpLmActionTable::compare(trans1->lmActionTable, + trans2->lmActionTable); + if ( cmpRes != 0 ) + return cmpRes; + + /* Compare action tables. */ + return CmpActionTable::compare(trans1->actionTable, + trans2->actionTable); +} + +/* Compare the properties of states that are embedded by users. Compares out + * priorities, out transitions, to, from, out, error and eof action tables. */ +int FsmAp::compareStateData( const StateAp *state1, const StateAp *state2 ) +{ + /* Compare the out priority table. */ + int cmpRes = CmpPriorTable:: + compare( state1->outPriorTable, state2->outPriorTable ); + if ( cmpRes != 0 ) + return cmpRes; + + /* Test to state action tables. */ + cmpRes = CmpActionTable::compare( state1->toStateActionTable, + state2->toStateActionTable ); + if ( cmpRes != 0 ) + return cmpRes; + + /* Test from state action tables. */ + cmpRes = CmpActionTable::compare( state1->fromStateActionTable, + state2->fromStateActionTable ); + if ( cmpRes != 0 ) + return cmpRes; + + /* Test out action tables. */ + cmpRes = CmpActionTable::compare( state1->outActionTable, + state2->outActionTable ); + if ( cmpRes != 0 ) + return cmpRes; + + /* Out condition space and set of vals. */ + if ( state1->outCondSpace < state2->outCondSpace ) + return -1; + else if ( state1->outCondSpace > state2->outCondSpace ) + return 1; + + cmpRes = CmpTable<int>::compare( state1->outCondKeys, + state2->outCondKeys ); + if ( cmpRes != 0 ) + return cmpRes; + + /* Test out error action tables. */ + cmpRes = CmpErrActionTable::compare( state1->errActionTable, + state2->errActionTable ); + if ( cmpRes != 0 ) + return cmpRes; + + /* Test eof action tables. */ + cmpRes = CmpActionTable::compare( state1->eofActionTable, + state2->eofActionTable ); + if ( cmpRes != 0 ) + return cmpRes; + + return CmpTable<FsmLongestMatchPart*>::compare( + state1->lmNfaParts, state2->lmNfaParts ); +} + + +/* Invoked when a state looses its final state status and the leaving + * transition embedding data should be deleted. */ +void FsmAp::clearOutData( StateAp *state ) +{ + /* Kill the out actions and priorities. */ + state->outCondSpace = 0; + state->outCondKeys.empty(); + state->outActionTable.empty(); + state->outPriorTable.empty(); +} + +bool FsmAp::hasOutData( StateAp *state ) +{ + return ( state->outActionTable.length() > 0 || + state->outCondSpace != 0 || + state->outCondKeys.length() > 0 || + state->outPriorTable.length() > 0 || + state->outCondSpace != 0 ); +} + +/* + * Setting Conditions. + */ + +FsmRes FsmAp::startFsmCondition( Action *condAction, bool sense ) +{ + CondSet set; + CondKeySet vals; + set.insert( condAction ); + vals.append( sense ? 1 : 0 ); + + /* Make sure the start state has no other entry points. */ + isolateStartState( this ); + + FsmRes res = embedCondition( this, startState, set, vals ); + if ( !res.success() ) + return res; + + if ( startState->nfaOut != 0 ) { + /* Only one level. */ + for ( NfaTransList::Iter na = *startState->nfaOut; na.lte(); na++ ) { + res = embedCondition( this, startState, set, vals ); + if ( !res.success() ) + return res; + } + } + + afterOpMinimize( true ); + + return FsmRes( FsmRes::Fsm(), this ); +} + +void FsmAp::allTransCondition( Action *condAction, bool sense ) +{ + CondSet set; + CondKeySet vals; + set.insert( condAction ); + vals.append( sense ? 1 : 0 ); + + for ( StateList::Iter state = stateList; state.lte(); state++ ) + embedCondition( this, state, set, vals ); +} + +void FsmAp::leaveFsmCondition( Action *condAction, bool sense ) +{ + for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) + addOutCondition( *state, condAction, sense ); +} |