Logo Search packages:      
Sourcecode: ragel version File versions

fsmap.cpp

/*
 *  Copyright 2002-2004 Adrian Thurston <adriant@ragel.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"

/* Insert a function into a function table. */
void ActionTable::setAction( int ordering, int actionId )
{
      /* Multi-insert in case specific instances of an action appear in a
       * transition more than once. */
      insertMulti( ordering, actionId );
}

/* Set all the functions from a funcTable in this table. */
void ActionTable::setActions( const ActionTable &other )
{
      for ( ActionTable::Iter action = other; action.lte(); action++ )
            insertMulti( action->key, action->value );
}

void ErrActionTable::setAction( int ordering, int actionId, int transferPoint )
{
      insertMulti( ErrActionTableEl( actionId, ordering, transferPoint ) );
}

void ErrActionTable::setActions( const ErrActionTable &other )
{
      for ( ErrActionTable::Iter act = other; act.lte(); act++ )
            insertMulti( ErrActionTableEl( act->actionId, 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 );
}

/* If there is a state dict element, then delete it. Everything else is left
 * up to the FsmGraph destructor. */
StateAp::~StateAp()
{
      if ( stateDictEl != 0 )
            delete stateDictEl;
}

/* 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();

      /* Walk all transitions out of the start state. */
      OutIter outIt( startState );
      for ( ; ! outIt.end(); outIt++ ) {
            if ( outIt.trans->toState != 0 )
                  outIt.trans->priorTable.setPrior( ordering, prior );
      }

      /* If the new start state is final then set the out priority. This follows
       * the same convention as setting start funcs in the out funcs of a final
       * start state. */
      if ( startState->stateBits & SB_ISFINAL )
            startState->outPriorTable.setPrior( ordering, prior );
}

/* 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. */
            OutIter outIt( state );
            for ( ; ! outIt.end() ; outIt++ ) {
                  if ( outIt.trans->toState != 0 )
                        outIt.trans->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. */
            InIter inIt( *state );
            for ( ; ! inIt.end(); inIt++ )
                  inIt.trans->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, int actionId )
{
      /* Make sure the start state has no other entry points. */
      isolateStartState();

      /* Walk the start state's transitions, setting functions. */
      OutIter outIt( startState );
      for ( ; ! outIt.end(); outIt++ ) {
            if ( outIt.trans->toState != 0 )
                  outIt.trans->actionTable.setAction( ordering, actionId );
      }

      /* If start state is final then insert on the out func. This means that you
       * can have start and leaving funcs on a machine that recognizes the null
       * word. */
      if ( startState->stateBits & SB_ISFINAL )
            startState->outActionTable.setAction( ordering, actionId );
}

/* Set functions to execute on all transitions. Walks the out lists of all
 * states. */
void FsmAp::allTransAction( int ordering, int actionId )
{
      /* Walk all states. */
      for ( StateList::Iter state = stateList; state.lte(); state++ ) {
            /* Walk the out list of the state. */
            OutIter outIt( state );
            for ( ; ! outIt.end(); outIt++ ) {
                  if ( outIt.trans->toState != 0 )
                        outIt.trans->actionTable.setAction( ordering, actionId );
            }
      }
}

/* 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, int actionId )
{
      /* Walk all final states. */
      for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) {
            /* Walk the final state's in list. */
            InIter inIt( *state );
            for ( ; ! inIt.end(); inIt++ )
                  inIt.trans->actionTable.setAction( ordering, actionId );
      }
}

/* Add functions to any future out transitions that may be made going out of
 * this state machine. */
void FsmAp::leaveFsmAction( int ordering, int actionId )
{
      /* Insert the action in the outActionTable of all final states. */
      for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
            (*state)->outActionTable.setAction( ordering, actionId );
}

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::setErrorAction( StateAp *state, int ordering, int actionId )
{
      /* Set error transitions in the states that go to error. */
      for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
            if ( trans->toState == 0 )
                  trans->actionTable.setAction( ordering, actionId );
      }

      /* If the outlist does not cover the alphabet then an error trans
       * needs to go into the default transition. */
      if ( !outListCovers( state ) ) {
            if ( state->outDefault == 0 ) {
                  /* There is no default transition, make one and set the
                   * error action. */
                  TransAp *newTrans = attachNewTrans( state, 0, KeyTypeDefault, 0, 0 );
                  newTrans->actionTable.setAction( ordering, actionId );
            }
            else if ( state->outDefault->toState == 0 ) {
                  /* There is a default that goes to the error state, add 
                   * to the action table. */
                  state->outDefault->actionTable.setAction( ordering, actionId );
            }
      }
}

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 ) {
                  setErrorAction( state, act->ordering, act->actionId );
                  if ( ! state->isFinState() )
                        state->eofActionTable.setAction( act->ordering, act->actionId );

                  state->errActionTable.BaseTable::remove( i );
            }
            else {
                  i += 1;
            }
      }
}

/* Set error actions in the start state. */
void FsmAp::startErrorAction( int ordering, int actionId, int transferPoint )
{
      /* Make sure the start state has no other entry points. */
      isolateStartState();

      /* Add the actions. */
      startState->errActionTable.setAction( ordering, actionId, transferPoint );
}

/* Set error actions in all states where there is a transition out. */
void FsmAp::allErrorAction( int ordering, int actionId, int transferPoint )
{
      /* Insert actions in the error action table of all states. */
      for ( StateList::Iter state = stateList; state.lte(); state++ )
            state->errActionTable.setAction( ordering, actionId, transferPoint );
}

/* Set error actions in the states that have transitions into a final state. */
void FsmAp::finishErrorAction( int ordering, int actionId, 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, actionId, transferPoint );
      }
}

/* Set error actions in final states. */
void FsmAp::leaveErrorAction( int ordering, int actionId, int transferPoint )
{
      /* Add the action to the error table of final states. */
      for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
            (*state)->errActionTable.setAction( ordering, actionId, transferPoint );
}

void FsmAp::startContext( int contextId )
{
      /* Make sure the start state has no other entry points. */
      isolateStartState();

      /* Add the actions. */
      startState->contextSet.insert( contextId );
}

void FsmAp::allContext( int contextId )
{
      /* Insert actions in the error action table of all states. */
      for ( StateList::Iter state = stateList; state.lte(); state++ )
            state->contextSet.insert( contextId );
}

void FsmAp::finishContext( int contextId )
{
      /* 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->contextSet.insert( contextId );
      }
}

void FsmAp::leaveContext( int contextId )
{
      /* Add the action to the error table of final states. */
      for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
            (*state)->contextSet.insert( contextId );
}

/* 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. */
      OutIter outIt( startState );
      for ( ; ! outIt.end(); outIt++ ) {
            TransAp *trans = outIt.trans;

            /* Walk the function data for the transition and set the keys to
             * increasing values starting at fromOrder. */
            int curFromOrder = fromOrder;
            ActionTable::Iter action = trans->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. */
            OutIter outIt( state );
            for ( ; ! outIt.end(); outIt++ )
                  outIt.trans->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. */
            OutIter outIt( state );
            for ( ; ! outIt.end(); outIt ++ ) {
                  /* Walk the action table for the transition. */
                  for ( ActionTable::Iter action = outIt.trans->actionTable;
                              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 out transtions. */
            for ( ErrActionTable::Iter action = state->errActionTable;
                        action.lte(); action++ )
                  action->ordering = 0;

            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 priorities or transitions. */
            if ( ! (state->stateBits & SB_ISFINAL) ) {
                  assert( state->outActionTable.length() == 0 );
                  assert( state->outPriorTable.length() == 0 );
            }

            /* Data used in algorithms should be cleared. */
            assert( (state->stateBits & SB_BOTH) == 0 );
            assert( state->foreignInTrans > 0 );
      }
}

/* Compare two transitions according to their relative priority.  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 )
                  return -1;
            else if ( pd1->desc->priority > pd2->desc->priority )
                  return 1;
            else {
                  /* Keys and priorities are equal, advance both. */
                  pd1.increment();
                  pd2.increment();
            }
      }

      /* No differing priorities on the same key. */
      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 )
{
      /* Compare the prior table. */
      int cmpRes = CmpPriorTable::
				compare( trans1->priorTable, trans2->priorTable );
      if ( cmpRes != 0 )
            return cmpRes;
      
      /* Priority tables the same. Compare function tables. */
      return CmpActionTable::
			compare(trans1->actionTable, trans2->actionTable);
}

/* Callback invoked when another trans (or possibly this) is added into this
 * transition during the merging process.  Draw in any properties of srcTrans
 * into this transition. AddInTrans is called when a new transitions is made
 * that will be a duplicate of another transition or a combination of several
 * other transitions. AddInTrans will be called for each transition that the
 * new transition is to represent. */
void FsmAp::addInTrans( TransAp *destTrans, TransAp *srcTrans )
{
      /* Protect against adding in from ourselves. */
      if ( srcTrans == destTrans ) {
            /* Adding in ourselves, need to make a copy of the source transitions.
             * The priorities are not copied in as that would have no effect. */
            destTrans->actionTable.setActions( ActionTable(srcTrans->actionTable) );
      }
      else {
            /* Not a copy of ourself, get the functions and priorities. */
            destTrans->actionTable.setActions( srcTrans->actionTable );
            destTrans->priorTable.setPriors( srcTrans->priorTable );
      }
}

/* Compare the out transition data of two states. Compares out priorities and
 * out transitions.  Compare two states accroding to the data contained in the
 * states.  Data means any properties added to user states that may
 * differentiate them.  Since the base states has no data, the default is to
 * return equal. */
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 out actions. */
      cmpRes = CmpActionTable::compare( state1->outActionTable, 
                  state2->outActionTable );
      if ( cmpRes != 0 )
            return cmpRes;

      /* Test out error actions. */
      cmpRes = CmpErrActionTable::compare( state1->errActionTable, 
                  state2->errActionTable );
      if ( cmpRes != 0 )
            return cmpRes;

      return CmpActionTable::compare( state1->eofActionTable, 
                  state2->eofActionTable );
}

/* Callback invoked when destTrans is made into a transition leaving srcState.
 * Draw in the out transition properties of srcState into this transition.
 * LeavingFromState is called when concatOp or starOp is called with
 * leavingFsm = true and a transition is made that represents leaving machine
 * one and going to machine two in the case of concatOp and leaving a machine
 * to go back into itself in the case of the star operator. */
void FsmAp::leavingFromState( TransAp *destTrans, StateAp *srcState )
{
      /* Get the actions data from the outActionTable. */
      destTrans->actionTable.setActions( srcState->outActionTable );

      /* Get the priorities from the outPriorTable. */
      destTrans->priorTable.setPriors( srcState->outPriorTable );
}


/* Callback invoked when a state looses its final state status. This is where
 * properties of final states get unset. At the point of invocation, it is
 * unspecified whether or not isFinState is set.  Callback invoked when a
 * state looses its final state status. This is where properties of final
 * states get unset. At the point of invocation, it is unspecified whether or
 * not isFinState is set. */
void FsmAp::relinquishFinal( StateAp *state )
{
      /* Kill the out actions and priorities. */
      state->outActionTable.empty();
      state->outPriorTable.empty();
}

Generated by  Doxygen 1.6.0   Back to index