Logo Search packages:      
Sourcecode: ragel version File versions

fsmgraph.h

/*
 *  Copyright 2001-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 
 */

#ifndef _FSMGRAPH_H
#define _FSMGRAPH_H

#include <assert.h>
#include "vector.h"
#include "bstset.h"
#include "compare.h"
#include "avltree.h"
#include "dlist.h"
#include "bstmap.h"
#include "sbstmap.h"
#include "sbstset.h"
#include "sbsttable.h"
#include "avlset.h"

/* Flags that control merging. */
#define SB_GRAPH1     0x01
#define SB_GRAPH2     0x02
#define SB_BOTH       0x03
#define SB_ISFINAL    0x04
#define SB_ISMARKED   0x08

struct TransAp;
struct StateAp;
struct FsmAp;

/* Differnt types of keys that transitions can be attached on. */
enum FsmKeyType
{
      KeyTypeRange,
      KeyTypeDefault
};

/* State list element for unambiguous access to list element. */
struct FsmListEl 
{
      StateAp *prev, *next;
};

/* This is the marked index for a state pair. Used in minimization. It keeps
 * track of whether or not the state pair is marked. */
struct MarkIndex
{
      MarkIndex(int states);
      ~MarkIndex();

      void markPair(int state1, int state2);
      bool isPairMarked(int state1, int state2);

private:
      int numStates;
      bool *array;
};

/* An abstraction of the key operators to enforce the possibility that the key
 * may be signed or unsigned. */
struct KeyOps
{
      /* Default to signed alphabet. */
      KeyOps() 
            :isAlphSigned(true) {}

      /* Default to signed alphabet. */
      KeyOps( bool isSigned ) 
            :isAlphSigned(isSigned) {}

      /* Less than. */
      bool lt( long key1, long key2 ) {
            return isAlphSigned ?  key1 < key2 : 
                  (unsigned long)key1 < (unsigned long)key2;
      }

      /* Greater than. */
      bool gt( long key1, long key2 ) {
            return isAlphSigned ? key1 > key2 : 
                  (unsigned long)key1 > (unsigned long)key2;
      }

      /* Equality. */
      bool eq( long key1, long key2 ) {
            return key1 == key2;
      }

      /* Decrement. Needed only for ranges. */
      void dec( long &key ) {
            key = isAlphSigned ? key - 1 : ((unsigned long)key)-1;
      }

      /* Increment. Needed only for ranges. */
      void inc( long &key ) {
            key = isAlphSigned ? key+1 : ((unsigned long)key)+1;
      }

      /* Compute the distance between two keys. */
      unsigned long long span( long key1, long key2 ) {
            return isAlphSigned ? 
                  (long long)key2 - (long long)key1 + 1: 
                  (unsigned long long)((unsigned long)key2) - 
                        (unsigned long long)((unsigned long)key1) + 1;
      }

      bool isAlphSigned;
      long lowKey, highKey;
};

/* Transistion Action Element. */
typedef SBstMapEl< int, int > ActionTableEl;

/* Transition Action Table.  */
struct ActionTable 
      : public SBstMap< int, int, CmpOrd<int> >
{
      void setAction( int ordering, int actionId );
      void setActions( const ActionTable &other );
};

/* Compare of a whole action table element (key & value). */
struct CmpActionTableEl
{
      static int compare( const ActionTableEl &action1, 
                  const ActionTableEl &action2 )
      {
            if ( action1.key < action2.key )
                  return -1;
            else if ( action1.key > action2.key )
                  return 1;
            else if ( action1.value < action2.value )
                  return -1;
            else if ( action1.value > action2.value )
                  return 1;
            return 0;
      }
};

/* Compare for ActionTable. */
typedef CmpSTable< ActionTableEl, CmpActionTableEl > CmpActionTable;

/* Action table element for error action tables. Adds the encoding of transfer
 * point. */
struct ErrActionTableEl
{
      ErrActionTableEl( int actionId, int ordering, int transferPoint )
            : ordering(ordering), actionId(actionId), transferPoint(transferPoint) { }

      /* Ordering and id of the action embedding. */
      int ordering;
      int actionId;

      /* Id of point of transfere from Error action table to transtions and
       * eofActionTable. */
      int transferPoint;

      int getKey() const { return ordering; }
};

struct ErrActionTable
      : public SBstTable< ErrActionTableEl, int, CmpOrd<int> >
{
      typedef SVector< ErrActionTableEl > BaseTable;

      void setAction( int ordering, int actionId, int transferPoint );
      void setActions( const ErrActionTable &other );
};

/* Compare of an error action table element (key & value). */
struct CmpErrActionTableEl
{
      static int compare( const ErrActionTableEl &action1, 
                  const ErrActionTableEl &action2 )
      {
            if ( action1.ordering < action2.ordering )
                  return -1;
            else if ( action1.ordering > action2.ordering )
                  return 1;
            else if ( action1.actionId < action2.actionId )
                  return -1;
            else if ( action1.actionId > action2.actionId )
                  return 1;
            else if ( action1.transferPoint < action2.transferPoint )
                  return -1;
            else if ( action1.transferPoint > action2.transferPoint )
                  return 1;
            return 0;
      }
};

/* Compare for ErrActionTable. */
typedef CmpSTable< ErrActionTableEl, CmpErrActionTableEl > CmpErrActionTable;


/* Descibe a priority, shared among PriorEls. 
 * Has key and whether or not used. */
struct PriorDesc
{
      int key;
      int priority;
      bool used;
};

/* Element in the arrays of priorities for transitions and arrays. Ordering is
 * unique among instantiations of machines, desc is shared. */
struct PriorEl
{
      PriorEl( int ordering, PriorDesc *desc ) 
            : ordering(ordering), desc(desc) { }

      int ordering;
      PriorDesc *desc;
};

/* Compare priority elements, which are ordered by the priority descriptor
 * key. */
struct PriorElCmp
{
      static inline int compare( const PriorEl &pel1, const PriorEl &pel2 ) 
      {
            if ( pel1.desc->key < pel2.desc->key )
                  return -1;
            else if ( pel1.desc->key > pel2.desc->key )
                  return 1;
            else
                  return 0;
      }
};


/* Priority Table. */
struct PriorTable 
      : public SBstSet< PriorEl, PriorElCmp >
{
      void setPrior( int ordering, PriorDesc *desc );
      void setPriors( const PriorTable &other );
};

/* Compare of prior table elements for distinguising state data. */
struct CmpPriorEl
{
      static inline int compare( const PriorEl &pel1, const PriorEl &pel2 )
      {
            if ( pel1.desc < pel2.desc )
                  return -1;
            else if ( pel1.desc > pel2.desc )
                  return 1;
            else if ( pel1.ordering < pel2.ordering )
                  return -1;
            else if ( pel1.ordering > pel2.ordering )
                  return 1;
            return 0;
      }
};

/* Compare of PriorTable distinguising state data. Using a compare of the
 * pointers is a little more strict than it needs be. It requires that
 * prioritiy tables have the exact same set of priority assignment operators
 * (from the input lang) to be considered equal. 
 *
 * Really only key-value pairs need be tested and ordering be merged. However
 * this would require that in the fuseing of states, priority descriptors be
 * chosen for the new fused state based on priority. Since the out transition
 * lists and ranges aren't necessarily going to line up, this is more work for
 * little gain. Final compression resets all priorities first, so this would
 * only be useful for compression at every operator, which is only an
 * undocumented test feature.
 */
typedef CmpSTable<PriorEl, CmpPriorEl> CmpPriorTable;

/* Plain action list that imposes no ordering. */
typedef Vector<int> TransFuncList;

/* Comparison for TransFuncList. */
typedef CmpTable< int, CmpOrd<int> > TransFuncListCompare;

/* Transition class that implements actions and priorities. */
struct TransAp 
{
      TransAp() : fromState(0), toState(0) {}
      TransAp( const TransAp &other ) :
            lowKey(other.lowKey),
            highKey(other.highKey),
            fromState(0), toState(0),
            actionTable(other.actionTable),
            priorTable(other.priorTable) {}

      long lowKey, highKey;
      StateAp *fromState;
      StateAp *toState;

      /* Pointers for outlist. */
      TransAp *prev, *next;

      /* Pointers for in-list. */
      TransAp *ilprev, *ilnext;

      /* The function table and priority for the transition. */
      ActionTable actionTable;
      PriorTable priorTable;
};

/* In transition list. Like DList except only has head pointers, which is all
 * that is required. Insertion and deletion is handled by the graph. This
 * class provides the iterator of a single list. */
struct TransInList
{
      TransInList() : head(0) { }

      TransAp *head;

      struct Iter
      {
            /* Default construct. */
            Iter() : ptr(0) { }

            /* Construct, assign from a list. */
            Iter( const TransInList &il )  : ptr(il.head) { }
            Iter &operator=( const TransInList &dl ) { ptr = dl.head; return *this; }

            /* At the end */
            bool lte() const    { return ptr != 0; }
            bool end() const    { return ptr == 0; }

            /* At the first, last element. */
            bool first() const { return ptr && ptr->ilprev == 0; }
            bool last() const  { return ptr && ptr->ilnext == 0; }

            /* Cast, dereference, arrow ops. */
            operator TransAp*() const   { return ptr; }
            TransAp &operator *() const { return *ptr; }
            TransAp *operator->() const { return ptr; }

            /* Increment, decrement. */
            inline void operator++(int)   { ptr = ptr->ilnext; }
            inline void operator--(int)   { ptr = ptr->ilprev; }

            /* The iterator is simply a pointer. */
            TransAp *ptr;
      };
};

typedef DList<TransAp> TransList;

/* Set of states, list of states. */
typedef BstSet<StateAp*> StateSet;
typedef DList<StateAp> StateList;

/* A element in a state dict. */
struct StateDictEl 
:
      public AvlTreeEl<StateDictEl>
{
      StateDictEl(const StateSet &stateSet) 
            : stateSet(stateSet) { }

      const StateSet &getKey() { return stateSet; }
      StateSet stateSet;
      StateAp *targState;
};

/* Dictionary mapping a set of states to a target state. */
typedef AvlTree< StateDictEl, StateSet, CmpTable<StateAp*> > StateDict;

/* Data needed for a merge operation. */
struct MergeData
{
      MergeData() 
            : stfillHead(0), stfillTail(0) { }

      StateDict stateDict;

      StateAp *stfillHead;
      StateAp *stfillTail;

      void fillListAppend( StateAp *state );
};

struct TransEl
{
      /* Constructors. */
      TransEl() { }
      TransEl( long lowKey, long highKey ) 
            : lowKey(lowKey), highKey(highKey) { }
      TransEl( long lowKey, long highKey, TransAp *value ) 
            : lowKey(lowKey), highKey(highKey), value(value) { }

      long lowKey, highKey;
      TransAp *value;
};

/* Vector based set of key items. */
struct KeySet
:
      public Vector<long>
{
      /* Return a pointer to the item in the set on success. */
      long *insert( long key, KeyOps *keyOps );
};

struct MinPartition 
{
      MinPartition() : active(false) { }

      StateList list;
      bool active;

      MinPartition *prev, *next;
};

/* Epsilon transition stored in a state. Specifies the target */
typedef Vector<int> EpsilonTrans;

/* List of states that are to be drawn into this. */
struct EptVectEl
{
      EptVectEl( StateAp *targ, bool leaving ) 
            : targ(targ), leaving(leaving) { }

      StateAp *targ;
      bool leaving;
};
typedef Vector<EptVectEl> EptVect;

/* Set of entry ids that go into this state. */
typedef BstSet<int> EntryIdSet;

/* Set of context ids. */
typedef BstSet<int> ContextSet;

/* State class that implements actions and priorities. */
struct StateAp 
{
      StateAp();
      StateAp(const StateAp &other);
      ~StateAp();

      /* Is the state final? */
      bool isFinState() { return stateBits & SB_ISFINAL; }

      /* Out transition list and the pointer for the default out trans. */
      TransList outList;
      TransAp *outDefault;

      /* In transition Lists. */
      TransInList inRange, inDefault;

      /* Entry points into the state. */
      EntryIdSet entryIds;

      /* Epsilon transitions. */
      EpsilonTrans epsilonTrans;

      /* Context set in the state. */
      ContextSet contextSet;

      /* Number of in transitions from states other than ourselves. */
      int foreignInTrans;

      /* Temporary data for various algorithms. */
      union {
            /* When duplicating the fsm we need to map each 
             * state to the new state representing it. */
            StateAp *stateMap;

            /* When minimizing machines by partitioning, this maps to the group
             * the state is in. */
            MinPartition *partition;

            /* When merging states (state machine operations) this next pointer is
             * used for the list of states that need to be filled in. */
            StateAp *next;

            /* Identification for printing and stable minimization. */
            int stateNum;

      } alg;

      /* Data used in epsilon operation, maybe fit into alg? */
      StateAp *isolatedShadow;
      int owningGraph;

      /* A pointer to a dict element that contains the set of states this state
       * represents. This cannot go into alg, because alg.next is used during
       * the merging process. */
      StateDictEl *stateDictEl;

      /* When drawing epsilon transitions, holds the list of states to merge
       * with. */
      EptVect *eptVect;

      /* Bits controlling the behaviour of the state during collapsing to dfa. */
      int stateBits;

      /* State list elements. */
      StateAp *next, *prev;

      /* 
       * Action and priority data.
       */

      /* Actions to add to any transitions leaving an the via this state. */
      ActionTable outActionTable;

      /* Out priorities transfered to out transitions. */
      PriorTable outPriorTable;

      /* Error action tables. */
      ErrActionTable errActionTable;

      /* Actions to execute on eof. */
      ActionTable eofActionTable;
};

/* Iterator for a state's out transitions.  Objects being iterated over come
 * from 3 sources: out transitions, out ranges and the default transitions.
 * Skips over unset transition elements. */
struct OutIter
{
      /* Encodes the different states that an fsm iterator can be in. */
      enum IterState {
            Begin,
            Range,
            Default,
            End
      };

      OutIter( StateAp *state );

      /* Query iterator. */
      bool lte() { return itState != End; }
      bool end() { return itState == End; }
      TransAp *operator++(int);
      TransAp *operator++();

      /* Iterator state data. */
      TransAp *trans;
      StateAp *state;
      IterState itState;

private:
      void findNext();
};

/* Iterator for a state's in transitions. This iterator does not adhere to
 * Ragel's standard iterator interface due to the exceptional requirements.
 * Objects being iterated over come from 3 sources: in transitions, in
 * ranges and the default transitions. These points are lists of transitions. */
struct InIter
{
      /* Encodes the different states that an fsm iterator can be in. */
      enum IterState {
            Begin,
            Range,
            Default,
            End
      };

      InIter( StateAp *state );

      /* Query iterator. */
      bool lte() { return itState != End; }
      bool end() { return itState == End; }
      TransAp *operator++(int);
      TransAp *operator++();

      /* The trans pointer available outside this class. */
      TransAp *trans;

      /* Iterator state. */
      StateAp *state;
      IterState itState;

private:
      void findNext();
};

struct NextTrans
{
      long lowKey, highKey;
      TransAp *trans;
      TransAp *next;

      void load() {
            if ( trans != 0 ) {
                  next = trans->next;
                  lowKey = trans->lowKey;
                  highKey = trans->highKey;
            }
      }

      void set( TransAp *t ) {
            trans = t;
            load();
      }

      void increment() {
            trans = next;
            load();
      }
};

struct PairIter
{
      /* Encodes the different states that an fsm iterator can be in. */
      enum IterState {
            Begin,
            ConsumeS1Range, ConsumeS2Range,
            OnlyInS1Range,  OnlyInS2Range,
            S1SticksOut,    S1SticksOutBreak,
            S2SticksOut,    S2SticksOutBreak,
            S1DragsBehind,  S1DragsBehindBreak,
            S2DragsBehind,  S2DragsBehindBreak,
            ExactOverlap,   End
      };

      /* Encodes the different states that are meaningful to the of the
       * iterator. */
      enum UserState {
            RangeInS1, RangeInS2,
            RangeOverlap,
            BreakS1, BreakS2
      };

      PairIter( const StateAp *state1, const StateAp *state2, 
                  KeyOps *keyOps, bool wantBreaks );
      
      /* Query iterator. */
      bool lte() { return itState != End; }
      bool end() { return itState == End; }
      void operator++(int) { findNext(); }
      void operator++()    { findNext(); }

      /* Iterator state. */
      const StateAp *state1;
      const StateAp *state2;
      IterState itState;
      UserState userState;

      NextTrans s1Tel, s2Tel;
      long bottomLow, bottomHigh;
      TransAp *bottomTrans;

      KeyOps *keyOps;
      bool wantBreaks;

private:
      void findNext();
};

/* Compare lists of epsilon transitions. Entries are name ids of targets. */
typedef CmpTable< int, CmpOrd<int> > CmpEpsilonTrans;

/* Compare sets of context values. */
typedef CmpTable< int, CmpOrd<int> > CmpContextSets;


/* Compare class for the Approximate minimization. */
class ApproxCompare
{
public:
      ApproxCompare() : keyOps(0) { }
      int compare( const StateAp *pState1, const StateAp *pState2 );

      /* Signed alphabet, used in comparison of out transitions. */
      KeyOps *keyOps;
};

/* Compare class for the initial partitioning of a partition minimization. */
class InitPartitionCompare
{
public:
      InitPartitionCompare() : keyOps(0) { }
      int compare( const StateAp *pState1, const StateAp *pState2 );

      /* Signed alphabet, used in comparison of out transitions. */
      KeyOps *keyOps;
};

/* Compare class for the regular partitioning of a partition minimization. */
class PartitionCompare
{
public:
      PartitionCompare() : keyOps(0) { }
      int compare( const StateAp *pState1, const StateAp *pState2 );

      /* Signed alphabet, used in comparison of out transitions. */
      KeyOps *keyOps;
};

/* Compare class for a minimization that marks pairs. Provides the shouldMark
 * routine. */
class MarkCompare
{
public:
      MarkCompare() : keyOps(0) { }
      bool shouldMark( MarkIndex &markIndex, const StateAp *pState1, 
                  const StateAp *pState2 );

      /* Signed alphabet, used in comparison of out transitions. */
      KeyOps *keyOps;
};

/* List of partitions. */
typedef DList< MinPartition > PartitionList;

/* List of transtions out of a state. */
typedef Vector<TransEl> TransListVect;

/* Entry point map used for keeping track of entry points in a machine. */
typedef BstSet< int > EntryIdSet;
typedef BstMapEl< int, StateAp* > EntryMapEl;
typedef BstMap< int, StateAp* > EntryMap;
typedef Vector<EntryMapEl> EntryMapBase;

/* Graph class that implements actions and priorities. */
struct FsmAp 
{
      /* Constructors/Destructors. */
      FsmAp( KeyOps *keyOps );
      FsmAp( const FsmAp &graph );
      ~FsmAp();

      /* The list of states. */
      StateList stateList;
      StateList misfitList;

      /* The map of entry points. */
      EntryMap entryPoints;

      /* The start state. */
      StateAp *startState;

      /* The set of final states. */
      StateSet finStateSet;

      /* Misfit Accounting. Are misfits put on a separate list. */
      bool misfitAccounting;

      /* Pointer to description of key type. */
      KeyOps *keyOps;

      /*
       * Transition actions and priorities.
       */

      /* Set priorities on transtions. */
      void startFsmPrior( int ordering, PriorDesc *prior );
      void allTransPrior( int ordering, PriorDesc *prior );
      void finishFsmPrior( int ordering, PriorDesc *prior );
      void leaveFsmPrior( int ordering, PriorDesc *prior );

      /* Action setting support. */
      void transferOutActions( StateAp *state );
      void transferErrorActions( StateAp *state, int transferPoint );
      void setErrorAction( StateAp *state, int ordering, int actionId );

      /* Set actions to execute. */
      void startFsmAction( int ordering, int actionId );
      void allTransAction( int ordering, int actionId );
      void finishFsmAction( int ordering, int actionId );
      void leaveFsmAction( int ordering, int actionId );

      /* Set error actions to execute. */
      void startErrorAction( int ordering, int actionId, int transferPoint );
      void allErrorAction( int ordering, int actionId, int transferPoint );
      void finishErrorAction( int ordering, int actionId, int transferPoint );
      void leaveErrorAction( int ordering, int actionId, int transferPoint );

      /* Set Context. */
      void startContext( int contextId );
      void allContext( int contextId );
      void finishContext( int contextId );
      void leaveContext( int contextId );

      /* Shift the action ordering of the start transitions to start at
       * fromOrder and increase in units of 1. Useful before kleene star
       * operation.  */
      int shiftStartActionOrder( int fromOrder );

      /* Clear all priorities from the fsm to so they won't affcet minimization
       * of the final fsm. */
      void clearAllPriorities();

      /* Zero out all the function keys. */
      void nullActionKeys();

      /* Walk the list of states and verify state properties. */
      void verifyStates();

      /* Misfit Accounting. Are misfits put on a separate list. */
      void setMisfitAccounting( bool val ) 
            { misfitAccounting = val; }

      /* Set and Unset a state as final. */
      void setFinState( StateAp *state );
      void unsetFinState( StateAp *state );

      void setStartState( StateAp *state );
      void unsetStartState( );
      
      /* Set and unset a state as an entry point. */
      void setEntry( int id, StateAp *state );
      void changeEntry( int id, StateAp *to, StateAp *from );
      void unsetEntry( int id, StateAp *state );
      void unsetEntry( int id );
      void unsetAllEntryPoints();

      /* Epsilon transitions. */
      void epsilonTrans( int id );
      void shadowReadWriteStates( MergeData &md );

      /*
       * Basic attaching and detaching.
       */

      /* Common to attaching/detaching list and default. */
      void attachToInList( StateAp *from, StateAp *to, TransAp *&head, TransAp *trans );
      void detachFromInList( StateAp *from, StateAp *to, TransAp *&head, TransAp *trans );

      /* Attach with a new transition. */
      TransAp *attachNewTrans( StateAp *from, StateAp *to, FsmKeyType keyType, 
                  long onChar1, long onChar2 );

      /* Attach with an existing transition that already in an out list. */
      void attachTrans( StateAp *from, StateAp *to, TransAp *trans, 
                  FsmKeyType keyType );

      /* Detach a transition from a target state. */
      void detachTrans( StateAp *from, StateAp *to, TransAp *trans, 
                  FsmKeyType keyType );

      /* When a range is split the lower key changes, this fixes it. */
      void changeRangeLowerKey( TransAp *trans, long oldKey, long newKey );

      /* Detach a state from the graph. */
      void detachState( StateAp *state );

      /*
       * NFA to DFA conversion routines.
       */

      /* Duplicate a transition that will dropin to a free spot. */
      TransAp *dupTrans( StateAp *from, FsmKeyType keyType,
                  TransAp *srcTrans, bool leavingFsm );

      /* In crossing, src trans overwrites the existing one because it has a
       * higher priority. */
      TransAp *overwriteTrans( MergeData &md, StateAp *from, FsmKeyType keyType, 
                  TransAp *destTrans, TransAp *srcTrans, bool leavingFsm );

      /* In crossing, two transitions both go to real states. */
      TransAp *fsmAttachStates( MergeData &md, StateAp *from, FsmKeyType keyType,
                  TransAp *destTrans, TransAp *srcTrans, bool leavingFsm );

      /* Two transitions are to be crossed, handle the possibility of either
       * going to the error state. */
      TransAp *mergeTrans( MergeData &md, StateAp *from, FsmKeyType keyType,
                  TransAp *destTrans, TransAp *srcTrans, bool leavingFsm );

      /* Compare deterimne relative priorities of two transition tables. */
      int comparePrior( const PriorTable &priorTable1, const PriorTable &priorTable2 );

      /* Cross a src transition with one that is already occupying a spot. */
      TransAp *crossTransitions( MergeData &md, StateAp *from, FsmKeyType keyType, 
                  TransAp *destTrans, TransAp *srcTrans, bool leavingFsm );

      /* Common to copying transition lists and ranges. */
      TransAp *keyInDestEl( MergeData &md, StateAp *dest, StateAp *src, 
                  NextTrans *destTel, bool leavingFsm );
      TransAp *keyInSrcEl( MergeData &md, StateAp *dest, StateAp *src, 
                  NextTrans *srcTel, bool leavingFsm );

      /* Copy the default transition. */
      void copyDefTrans( MergeData &md, StateAp *dest, StateAp *src, bool leavingFsm );

      void appendTrans( TransList &destList, TransAp *trans, bool &covers );
      void outTransCopy( MergeData &md, StateAp *dest, StateAp *src, bool leavingFsm );

      /* Merging states into a destination state. */
      void mergeStates( MergeData &md, StateAp *destState, 
                  StateAp *srcState, bool leavingFsm );

      /* Merge a set of states into newState. */
      void mergeStates( MergeData &md, StateAp *destState, 
                  StateAp **srcStates, int numSrc );

      /* Make all states that are combinations of other states and that
       * have not yet had their out transitions filled in. This will 
       * empty out stateDict and stFil. */
      void fillInStates( MergeData &md );

      /*
       * Transition Comparison.
       */

      /* Compare transition data. Either of the pointers may be null. */
      static inline int compareDataPtr( TransAp *trans1, TransAp *trans2 );

      /* Compare target state and transition data. Either pointer may be null. */
      static inline int compareFullPtr( TransAp *trans1, TransAp *trans2 );

      /* Compare target partitions. Either pointer may be null. */
      static inline int comparePartPtr( TransAp *trans1, TransAp *trans2 );

      /* Check marked status of target states. Either pointer may be null. */
      static inline bool shouldMarkPtr( MarkIndex &markIndex, 
                  TransAp *trans1, TransAp *trans2 );

      /*
       * Callbacks.
       */

      /* Compare priority and function table of transitions. */
      static int compareTransData( TransAp *trans1, TransAp *trans2 );

      /* Add in the properties of srcTrans into this. */
      void addInTrans( TransAp *destTrans, TransAp *srcTrans );

      /* Compare states on data stored in the states. */
      static int compareStateData( const StateAp *state1, const StateAp *state2 );

      /* This trans is going to be made a leaving-graph-trans from srcState. */
      void leavingFromState( TransAp *destTrans, StateAp *srcState );
      
      /* Invoked when a state looses its final state status. */
      void relinquishFinal( StateAp *state );

      /*
       * Allocation.
       */

      /* New up a state and add it to the graph. */
      StateAp *addState();

      /*
       * Building basic machines
       */

      void concatFsm( long c );
      void concatFsm( long *str, int len );
      void orFsm( long *set, int len );
      void dotFsm( );
      void dotStarFsm( );
      void rangeFsm( long low, long high );
      void nullFsm( );
      void emptyFsm( );

      /*
       * Fsm operators.
       */

      void starOp( );
      void repeatOp( int times );
      void optionalRepeatOp( int times );
      void concatOp( FsmAp *other );
      void unionOp( FsmAp *other );
      void intersectOp( FsmAp *other );
      void subtractOp( FsmAp *other );
      void epsilonOp();
      void joinOp( int startId, int finalId, FsmAp **others, int numOthers );
      void globOp( FsmAp **others, int numOthers );
      void deterministicEntry();

      /*
       * Operator workers
       */

      /* Determine if there are any entry points into a start state other than
       * the start state. */
      bool isStartStateIsolated();

      /* Make a new start state that has no entry points. Will not change the
       * identity of the fsm. */
      void isolateStartState();

      /* Workers for resolving epsilon transitions. */
      bool inEptVect( EptVect *eptVect, StateAp *targ );
      void epsilonFillEptVectFrom( StateAp *root, StateAp *from, bool parentLeaving );
      void resolveEpsilonTrans( MergeData &md );

      /* Workers for concatenation and union. */
      void doConcat( FsmAp *other, StateSet *fromStates, bool optional );
      void doOr( FsmAp *other );

      /*
       * Final states
       */

      /* Unset any final states that are no longer to be final 
       * due to final bits. */
      void unsetIncompleteFinals();
      void unsetKilledFinals();

      /* Bring in other's entry points. Assumes others states are going to be
       * copied into this machine. */
      void copyInEntryPoints( FsmAp *other );

      /* Set State numbers starting at 0. */
      void setStateNumbers();

      /* Unset all final states. */
      void unsetAllFinStates();

      /* Set the bits of final states and clear the bits of non final states. */
      void setFinBits( int finStateBits );

      /*
       * Self-consistency checks.
       */

      /* Run a sanity check on the machine. */
      void verifyIntegrity();

      /* Verify that there are no unreachable states, or dead end states. */
      void verifyReachability();
      void verifyNoDeadEndStates();

      /*
       * Path pruning
       */

      /* Mark all states reachable from state. */
      void markReachableFromHereReverse( StateAp *state );

      /* Mark all states reachable from state. */
      void markReachableFromHere( StateAp *state );


      /* Removes states that cannot be reached by any path in the fsm and are
       * thus wasted silicon. */
      void removeDeadEndStates();

      /* Removes states that cannot be reached by any path in the fsm and are
       * thus wasted silicon. */
      void removeUnreachableStates();

      /* Remove error actions from states on which the error transition will
       * never be taken. */
      bool outListCovers( StateAp *state );
      bool anyErrorRange( StateAp *state );

      /* Remove states that are on the misfit list. */
      void removeMisfits();

      /*
       * FSM Minimization
       */

      /* Minimization by partitioning. */
      void minimizePartition1();
      void minimizePartition2();

      /* Minimize the final state Machine. The result is the minimal fsm. Slow
       * but stable, correct minimization. Uses n^2 space (lookout) and average
       * n^2 time. Worst case n^3 time, but a that is a very rare case. */
      void minimizeStable();

      /* Minimize the final state machine. Does not find the minimal fsm, but a
       * pretty good approximation. Does not use any extra space. Average n^2
       * time. Worst case n^3 time, but a that is a very rare case. */
      void minimizeApproximate();

      /* This is the worker for the minimize approximate solution. It merges
       * states that have identical out transitions. */
      bool minimizeRound( );

      /* Given an intial partioning of states, split partitions that have out trans
       * to differing partitions. */
      int partitionRound( StateAp **statePtrs, MinPartition *parts, int numParts );

      /* Split partitions that have a transition to a previously split partition, until
       * there are no more partitions to split. */
      int splitCandidates( StateAp **statePtrs, MinPartition *parts, int numParts );

      /* Fuse together states in the same partition. */
      void fusePartitions( MinPartition *parts, int numParts );

      /* Mark pairs where out final stateness differs, out trans data differs,
       * trans pairs go to a marked pair or trans data differs. Should get 
       * alot of pairs. */
      void initialMarkRound( MarkIndex &markIndex );

      /* One marking round on all state pairs. Considers if trans pairs go
       * to a marked state only. Returns whether or not a pair was marked. */
      bool markRound( MarkIndex &markIndex );

      /* Move the in trans into src into dest. */
      void inTransMove(StateAp *dest, StateAp *src);
      
      /* Make state src and dest the same state. */
      void fuseEquivStates(StateAp *dest, StateAp *src);

      /* Find any states that didn't get marked by the marking algorithm and
       * merge them into the primary states of their equivalence class. */
      void fuseUnmarkedPairs( MarkIndex &markIndex );
};


#endif /* _FSMGRAPH_H */

Generated by  Doxygen 1.6.0   Back to index