Logo Search packages:      
Sourcecode: ragel version File versions

fsmattach.cpp

/*
 *  Copyright 2001 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 <string.h>
#include <assert.h>
#include "fsmgraph.h"

#include <iostream>
using namespace std;

/* Insert a transition into an inlist. The head must be supplied. Also sets
 * fromState and toState. */
void FsmAp::attachToInList( StateAp *from, StateAp *to, 
            TransAp *&head, TransAp *trans )
{
      trans->ilnext = head;
      trans->ilprev = 0;

      /* If in trans list is not empty, set the head->prev to trans. */
      if ( head != 0 )
            head->ilprev = trans;

      /* Now insert ourselves at the front of the list. */
      head = trans;

      /* Keep track of foreign transitions for from and to. */
      if ( from != to ) {
            if ( misfitAccounting ) {
                  /* If the number of foreign in transitions is about to go up to 1 then
                   * move it from the misfit list to the main list. */
                  if ( to->foreignInTrans == 0 )
                        stateList.append( misfitList.detach( to ) );
            }
            
            to->foreignInTrans += 1;
      }
};

/* Detach a transition from an inlist. The head of the inlist must be supplied.
 * Also reset the transitions's fromState and toState pointers. */
void FsmAp::detachFromInList( StateAp *from, StateAp *to, 
            TransAp *&head, TransAp *trans )
{
      /* Detach in the inTransList. */
      if ( trans->ilprev == 0 ) 
            head = trans->ilnext; 
      else
            trans->ilprev->ilnext = trans->ilnext; 

      if ( trans->ilnext != 0 )
            trans->ilnext->ilprev = trans->ilprev; 
      
      /* Keep track of foreign transitions for from and to. */
      if ( from != to ) {
            to->foreignInTrans -= 1;
            
            if ( misfitAccounting ) {
                  /* If the number of foreign in transitions goes down to 0 then move it
                   * from the main list to the misfit list. */
                  if ( to->foreignInTrans == 0 )
                        misfitList.append( stateList.detach( to ) );
            }
      }
}

/* Attach states on the default transition, range list or on out/in list key.
 * Type of attaching and is controlled by keyType. First makes a new
 * transition. If there is already a transition out from fromState on the
 * default, then will assertion fail. */
TransAp *FsmAp::attachNewTrans( StateAp *from, StateAp *to, 
            FsmKeyType keyType, long lowKey, long highKey )
{
      /* Make the new transition. */
      TransAp *retVal = new TransAp();

      /* The transition is now attached. Remember the parties involved. */
      retVal->fromState = from;
      retVal->toState = to;

      switch ( keyType ) {
      case KeyTypeRange: {
            /* Make the entry in the out list for the transitions. */
            from->outList.append( retVal );

            /* Set the the keys of the new trans. */
            retVal->lowKey = lowKey;
            retVal->highKey = highKey;

            /* Attach using inRange as the head pointer. */
            if ( to != 0 )
                  attachToInList( from, to, to->inRange.head, retVal );
            break;
      }
      case KeyTypeDefault: {
            /* If there is already a default, then assertion fail. */
            assert( from->outDefault == 0 );

            /* Attach using the new transition and defInTrans as the head. */
            from->outDefault = retVal;

            /* Keys are not used for the default transition. Init it for
             * consistency. */
            retVal->lowKey = 0;
            retVal->highKey = 0;

            /* Attach using inDef as the head pointer. */
            if ( to != 0 )
                  attachToInList( from, to, to->inDefault.head, retVal );
            break;
      }}

      return retVal;
}

/* Attach for out/in lists, range lists or for default transition. Type of
 * attaching is controlled by the keyType parameter. This attach should be
 * used when a transition already is allocated and it must be attached. Does
 * not handle adding the transition into the out list. */
void FsmAp::attachTrans( StateAp *from, StateAp *to, TransAp *trans, 
            FsmKeyType keyType )
{
      assert( trans->fromState == 0 && trans->toState == 0 );
      trans->fromState = from;
      trans->toState = to;

      if ( to != 0 ) { 
            switch ( keyType ) {
            case KeyTypeRange: {
                  /* Attach using the inRange pointer as the head pointer. */
                  attachToInList( from, to, to->inRange.head, trans );
                  break;
            }
            case KeyTypeDefault: {
                  /* Attach using inDef as the head pointer. */
                  attachToInList( from, to, to->inDefault.head, trans );
                  break;
            }}
      }
}

/* Detach for out/in lists or for default transition. The type of detaching is
 * controlled by the keyType parameter. */
void FsmAp::detachTrans( StateAp *from, StateAp *to, TransAp *trans, 
            FsmKeyType keyType )
{
      assert( trans->fromState == from && trans->toState == to );
      trans->fromState = 0;
      trans->toState = 0;

      if ( to != 0 ) {
            switch ( keyType ) {
            case KeyTypeRange: {
                  /* Detach using to's inRange pointer as the head. */
                  detachFromInList( from, to, to->inRange.head, trans );
                  break;
            }
            case KeyTypeDefault: {
                  /* Detach using the to's inDefHead as the head pointer. */
                  detachFromInList( from, to, to->inDefault.head, trans );
                  break;
            }}
      }
}


/* Detach a state from the graph. Detaches and deletes transitions in and out
 * of the state. Empties inList and outList. Removes the state from the final
 * state set. A detached state becomes useless and should be deleted. */
void FsmAp::detachState( StateAp *state )
{
      /* Detach the in transitions from the inRange list of transitions. */
      while ( state->inRange.head != 0 ) {
            /* Get pointers to the trans and the state. */
            TransAp *trans = state->inRange.head;
            StateAp *fromState = trans->fromState;

            /* Detach the transitions from the source state. */
            detachTrans( fromState, state, trans, KeyTypeRange );

            /* If from has a default transition we cannot delete range from
             * because that effectively adds the keys to the set of keys following
             * the default trans.  Instead null out the transition. */
            if ( fromState->outDefault != 0 ) {
                  /* From has a default transition, we must null out the target. */
                  trans->actionTable.empty();
                  trans->priorTable.empty();

                  /* Attach to the error state. */
                  attachTrans( fromState, 0, trans, KeyTypeRange );
            }
            else {
                  /* No default, Ok to delete the transition. */
                  fromState->outList.detach( trans );
                  delete trans;
            }
      }

      /* Detach default in transitions. */
      while ( state->inDefault.head != 0 ) {
            /* Get pointers to the trans and the state. */
            TransAp *trans = state->inDefault.head;
            StateAp *fromState = trans->fromState;

            /* Detach. */
            detachTrans( fromState, state, trans, KeyTypeDefault );

            /* From state no longer has a default trans, null it out, delete the
             * trans. */
            fromState->outDefault = 0;
            delete trans;
      }

      /* Remove the entry points in on the machine. */
      while ( state->entryIds.length() > 0 )
            unsetEntry( state->entryIds[0], state );

      /* Detach out range transitions. */
      for ( TransList::Iter trans = state->outList; trans.lte(); ) {
            TransList::Iter next = trans.next();
            detachTrans( state, trans->toState, trans, KeyTypeRange );
            delete trans;
            trans = next;
      }

      /* Delete all of the out range pointers. */
      state->outList.abandon();

      /* Detach the default out transition. */
      if ( state->outDefault != 0 ) {
            detachTrans( state, state->outDefault->toState, state->outDefault, 
                        KeyTypeDefault );
            delete state->outDefault;
      }

      /* Unset final stateness before detaching from graph. */
      if ( state->stateBits & SB_ISFINAL )
            finStateSet.remove( state );
}


/* Duplicate a transition. Makes a new transition that is attached to the same
 * dest as srcTrans. The new transition has functions and priority taken from
 * srcTrans. If leavingFsm is set, then outPrior and outFuncs are taken from
 * the from state. Used for merging a transition in to a free spot. The trans
 * can just be dropped in. It does not conflict with an existing trans and need
 * not be crossed. Returns the new transition. */
TransAp *FsmAp::dupTrans( StateAp *from, FsmKeyType keyType, 
            TransAp *srcTrans, bool leavingFsm )
{
      /* Make a new transition. */
      TransAp *newTrans = new TransAp();

      /* We can attach the transition, one does not exist. */
      attachTrans( from, srcTrans->toState, newTrans, keyType );
            
      /* Call the user callback to add in the original source transition. */
      addInTrans( newTrans, srcTrans );

      /* If the transition being duplicated is not an error transition and we
       * are leaving, then add in the from state's out data. This will pickup
       * any out functions or and/or set the priority from the out prior. This
       * must happen after the adding in of the trans, so that out priority
       * overrides the priority from the source trans. */
      if ( newTrans->toState != 0 && leavingFsm )
            leavingFromState( newTrans, from );

      return newTrans;
}

/* In crossing, src trans and dest trans both go to existing states. Make one
 * state from the sets of states that src and dest trans go to. */
TransAp *FsmAp::fsmAttachStates( MergeData &md, StateAp *from, FsmKeyType keyType, 
                  TransAp *destTrans, TransAp *srcTrans, bool leavingFsm )
{
      /* The priorities are equal. We must merge the transitions. Does the
       * existing trans go to the state we are to attach to? ie, are we to
       * simply double up the transition? */
      StateAp *toState = srcTrans->toState;
      StateAp *existingState = destTrans->toState;

      if ( existingState == toState ) {
            /* The transition is a double up to the same state.  Copy the src
             * trans into itself. We don't need to merge in the from out trans
             * data, that was done already. */
            addInTrans( destTrans, srcTrans );
      }
      else {
            /* The trans is not a double up. Dest trans cannot be the same as src
             * trans. Set up the state set. */
            StateSet stateSet;

            /* We go to all the states the existing trans goes to, plus... */
            if ( existingState->stateDictEl == 0 )
                  stateSet.insert( existingState );
            else
                  stateSet.insert( existingState->stateDictEl->stateSet );

            /* ... all the states that we have been told to go to. */
            if ( toState->stateDictEl == 0 )
                  stateSet.insert( toState );
            else
                  stateSet.insert( toState->stateDictEl->stateSet );

            /* Look for the state. If it is not there already, make it. */
            StateDictEl *lastFound;
            if ( md.stateDict.insert( stateSet, &lastFound ) ) {
                  /* Make a new state representing the combination of states in
                   * stateSet. It gets added to the fill list.  This means that we
                   * need to fill in it's transitions sometime in the future.  We
                   * don't do that now (ie, do not recurse). */
                  StateAp *combinState = addState();

                  /* Link up the dict element and the state. */
                  lastFound->targState = combinState;
                  combinState->stateDictEl = lastFound;

                  /* Add to the fill list. */
                  md.fillListAppend( combinState );
            }

            /* Get the state insertted/deleted. */
            StateAp *targ = lastFound->targState;

            /* Detach the state from existing state. */
            detachTrans( from, existingState, destTrans, keyType );

            /* Re-attach to the new target. */
            attachTrans( from, targ, destTrans, keyType );

            /* Add in src trans to the existing transition that we redirected to
             * the new state. We don't need to merge in the from out trans data,
             * that was done already. */
            addInTrans( destTrans, srcTrans );
      }

      return destTrans;
}

/* Two transitions are to be crossed, handle the possibility of either going
 * to the error state. */
TransAp *FsmAp::mergeTrans( MergeData &md, StateAp *from, FsmKeyType keyType, 
                  TransAp *destTrans, TransAp *srcTrans, bool leavingFsm )
{
      TransAp *retTrans = 0;
      if ( destTrans->toState == 0 && srcTrans->toState == 0 ) {
            /* Error added into error. */
            addInTrans( destTrans, srcTrans );
            retTrans = destTrans;
      }
      else if ( destTrans->toState == 0 && srcTrans->toState != 0 ) {
            /* Non error added into error we need to detach and reattach, */
            detachTrans( from, destTrans->toState, destTrans, keyType );
            attachTrans( from, srcTrans->toState, destTrans, keyType );
            addInTrans( destTrans, srcTrans );
            retTrans = destTrans;

            if ( leavingFsm )
                  leavingFromState( retTrans, from );
      }
      else if ( srcTrans->toState == 0 ) {
            /* Dest goes somewhere but src doesn't, just add it it in. */
            addInTrans( destTrans, srcTrans );
            retTrans = destTrans;
      }
      else {
            /* Both go somewhere, run the actual cross. */
            retTrans = fsmAttachStates( md, from, keyType, destTrans, 
                        srcTrans, leavingFsm );

            if ( leavingFsm )
                  leavingFromState( retTrans, from );
      }


      return retTrans;
}

/* Find the trans with the higher priority. If src is lower priority then dest then
 * src is ignored. If src is higher priority than dest, then src overwrites dest. If
 * the priorities are equal, then they are merged. */
TransAp *FsmAp::crossTransitions( MergeData &md, StateAp *from, FsmKeyType keyType, 
            TransAp *destTrans, TransAp *srcTrans, bool leavingFsm )
{
      TransAp *retTrans;

      /* Compute the priority table of the source transition. */
      PriorTable srcPrior = srcTrans->priorTable;
      if ( leavingFsm )
            srcPrior.setPriors( from->outPriorTable );

      /* Compare the priority of the dest and src transitions. */
      int compareRes = comparePrior( destTrans->priorTable, srcPrior );
      if ( compareRes < 0 ) {
            /* Src trans has a higher priority than dest, src overwrites dest.
             * Detach dest and return a copy of src. */
            detachTrans( from, destTrans->toState, destTrans, keyType );
            retTrans = dupTrans( from, keyType, srcTrans, leavingFsm );
      }
      else if ( compareRes > 0 ) {
            /* The dest trans has a higher priority, use dest. */
            retTrans = destTrans;
      }
      else {
            /* Src trans and dest trans have the same priority, they must be merged. */
            retTrans = mergeTrans( md, from, keyType, destTrans, 
                        srcTrans, leavingFsm );
      }

      /* Return the transition that resulted from the cross. */
      return retTrans;
}

/* When copying out transitions, a transition exists only in the dest out list.
 * Since the key is not in src, we must consider a default transition.  Dest
 * may get crossed with it. */
TransAp *FsmAp::keyInDestEl( MergeData &md, StateAp *dest, StateAp *src, 
             NextTrans *destTel, bool leavingFsm )
{
      TransAp *retTrans = 0;

      /* Is there a default transition? */
      if ( src->outDefault != 0 ) {
            /* Cross dest trans with the default from src. */
            retTrans = crossTransitions( md, dest, KeyTypeRange, destTel->trans, 
                        src->outDefault, leavingFsm );
      }
      else {
            /* No default transition from src. Just use what was in dest already. */
            retTrans = destTel->trans;
      }
      return retTrans;
}

/* When copying out transitions, a transition exists only in the src out list.
 * Since the key is not in dest, we must consider a default transition. Src may
 * get crossed with one of those. */
TransAp *FsmAp::keyInSrcEl( MergeData &md, StateAp *dest, StateAp *src, 
            NextTrans *srcTel, bool leavingFsm )
{
      TransAp *retTrans = 0;

      if ( dest->outDefault != 0 ) {
            /* Cross src trans with the default. Since crossing writes to the
             * dest, we first need a copy of the default. */
            TransAp *newTrans = dupTrans( dest, KeyTypeRange, dest->outDefault, false );
            retTrans = crossTransitions( md, dest, KeyTypeRange, newTrans, 
                        srcTel->trans, leavingFsm );
      }
      else {
            /* Dup src's trans into the new transition element. */
            retTrans = dupTrans( dest, KeyTypeRange, srcTel->trans, leavingFsm );
      }

      return retTrans;
}

/* Copying the default transition. */
void FsmAp::copyDefTrans( MergeData &md, StateAp *dest, StateAp *src, bool leavingFsm )
{
      if ( dest->outDefault != 0 && src->outDefault != 0 ) {
            /* Must cross the default out transitions. */
            dest->outDefault = crossTransitions( md, dest, KeyTypeDefault,
                              dest->outDefault, src->outDefault, leavingFsm );
      }
      else if ( src->outDefault != 0 ) {
            /* A default trans only in src, copy it to dest. */
            dest->outDefault = dupTrans( dest, KeyTypeDefault,
                        src->outDefault, leavingFsm );
      }
      else {
            /* Leave dest->outDefault as is. */
      }
}

void FsmAp::changeRangeLowerKey( TransAp *trans, long oldKey, 
            long newKey )
{
      /* Be certain that the the we are changing from the correct old key and
       * set the new key. */
      assert( keyOps->eq( trans->lowKey, oldKey ) );
      trans->lowKey = newKey;
}

/* Append a transition to a destination list. If any gaps are found then
 * reports that by setting covers = false. */
void FsmAp::appendTrans( TransList &destList, TransAp *trans, bool &covers )
{
      if ( destList.length() == 0 ) {
            if ( keyOps->lt( keyOps->lowKey, trans->lowKey ) )
                  covers = false;
      }
      else {
            long lastHigh = destList.tail->highKey;
            keyOps->inc( lastHigh );
            if ( keyOps->lt( lastHigh, trans->lowKey ) )
                  covers = false;
      }
      destList.append( trans );
}

/* Copy the transitions in srcList to the outlist of dest. If srcList comes from
 * a final state and out transitions should be copied in then leavingFsm can be
 * set true. SrcList should not be the outList of dest, otherwise you would
 * be copying the contents of srcList into itself as it's iterated: bad news. */
void FsmAp::outTransCopy( MergeData &md, StateAp *dest, StateAp *src, bool leavingFsm )
{
      /* For making destination lists. */
      TransEl newTel;
      bool covers = true;

      /* The destination list. */
      TransList destList;

      /* Set up an iterator to stop at breaks. */
      PairIter outPair( dest, src, keyOps, true );
      while ( ! outPair.end() ) {
            switch ( outPair.userState ) {
            case PairIter::RangeInS1: {
                  /* Dest range may get crossed with src's default transition. */
                  TransAp *newTrans = keyInDestEl( md, dest, src, &outPair.s1Tel, leavingFsm );

                  /* Set up the transition's keys and append to the dest list. */
                  newTrans->lowKey = outPair.s1Tel.lowKey;
                  newTrans->highKey = outPair.s1Tel.highKey;
                  appendTrans( destList, newTrans, covers );
                  break;
            }
            case PairIter::RangeInS2: {
                  /* Src range may get crossed with dest's default transition. */
                  TransAp *newTrans = keyInSrcEl( md, dest, src, &outPair.s2Tel, leavingFsm );

                  /* Set up the transition's keys and append to the dest list. */
                  newTrans->lowKey = outPair.s2Tel.lowKey;
                  newTrans->highKey = outPair.s2Tel.highKey;
                  appendTrans( destList, newTrans, covers );
                  break;
            }
            case PairIter::RangeOverlap: {
                  /* Exact overlap, cross them. */
                  TransAp *newTrans = crossTransitions( md, dest, KeyTypeRange,
                        outPair.s1Tel.trans, outPair.s2Tel.trans, leavingFsm );

                  /* Set up the transition's keys and append to the dest list. */
                  newTrans->lowKey = outPair.s1Tel.lowKey;
                  newTrans->highKey = outPair.s1Tel.highKey;
                  appendTrans( destList, newTrans, covers );
                  break;
            }
            case PairIter::BreakS1: {
                  /* Since we are always writing to the dest trans, the dest needs
                   * to be coppied when it is broken. The copy goes into the first
                   * half of the break because that is the value we have access to.
                   * */
                  outPair.s1Tel.trans = dupTrans( dest, KeyTypeRange, 
                              outPair.s1Tel.trans, false );
                  break;
            }
            case PairIter::BreakS2:
                  break;
            }

            outPair++;
      }

      if ( destList.length() == 0 || !covers || keyOps->lt( 
                  destList.tail->highKey, keyOps->highKey ) )
      {
            /* Dest List does not cover the alphabet, handle 
             * default transitions. */
            copyDefTrans( md, dest, src, leavingFsm );
      }
      else if ( dest->outDefault != 0 ) {
            /* Dest list covers the alphabet, default transition will never be
             * taken. */
            detachTrans( dest, dest->outDefault->toState, 
                        dest->outDefault, KeyTypeDefault );
            delete dest->outDefault;
            dest->outDefault = 0;
      }

      /* Transfer destList into dest->outList. */
      dest->outList.shallowCopy( destList );
      destList.abandon();
}


/* Move all the transitions that go into src so that they go into dest.  */
void FsmAp::inTransMove( StateAp *dest, StateAp *src )
{
      /* Do not try to move in trans to and from the same state. */
      assert( dest != src );

      /* If src is the start state, dest becomes the start state. */
      if ( src == startState ) {
            unsetStartState();
            setStartState( dest );
      }

      /* For each entry point into, create an entry point into dest, when the
       * state is detached, the entry points to src will be removed. */
      for ( EntryIdSet::Iter enId = src->entryIds; enId.lte(); enId++ )
            changeEntry( *enId, dest, src );

      /* Move the transitions in inRange. */
      while ( src->inRange.head != 0 ) {
            /* Get trans and from state. */
            TransAp *trans = src->inRange.head;
            StateAp *fromState = trans->fromState;

            /* Detach from src, reattach to dest. */
            detachTrans( fromState, src, trans, KeyTypeRange );
            attachTrans( fromState, dest, trans, KeyTypeRange );
      }

      /* Move the default transitions. */
      while ( src->inDefault.head != 0 ) {
            /* Get trans and from state. */
            TransAp *trans = src->inDefault.head;
            StateAp *fromState = trans->fromState;

            /* Detach from src, reattach to dest. */
            detachTrans( fromState, src, trans, KeyTypeDefault );
            attachTrans( fromState, dest, trans, KeyTypeDefault );
      }
}

Generated by  Doxygen 1.6.0   Back to index