Logo Search packages:      
Sourcecode: ragel version File versions

redfsm.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 _REDFSM_H
#define _REDFSM_H

#include <assert.h>
#include "vector.h"
#include "compare.h"
#include "bstmap.h"
#include "bstset.h"
#include "avlmap.h"
#include "avltree.h"
#include "avlbasic.h"
#include "fsmgraph.h"
#include "mergesort.h"

#define TRANS_ERR_TRANS   0
#define STATE_ERR_STATE   0
#define FUNC_NO_FUNC      0

/* Forwards. */
struct RedStateAp;
struct TransAp;
struct StateAp;
struct FsmAp;

/* Reduced action. */
struct RedAction
:
      public AvlTreeEl<RedAction>
{
      RedAction( const ActionTable &key )
            : key(key), bAnyNextStmt(false), 
            bAnyCurStateRef(false) { }
      
      const ActionTable &getKey() 
            { return key; }

      ActionTable key;
      int actListId;
      int location;

      bool anyNextStmt() { return bAnyNextStmt; }
      bool anyCurStateRef() { return bAnyCurStateRef; }

      bool bAnyNextStmt;
      bool bAnyCurStateRef;
};
typedef AvlTree<RedAction, ActionTable, CmpActionTable> ActionTableMap;

/* Reduced transition. */
struct RedTransAp
:
      public AvlTreeEl<RedTransAp>
{
      RedTransAp( RedStateAp *targ, RedAction *action, int id )
            : targ(targ), action(action), id(id) { }

      RedStateAp *targ;
      RedAction *action;
      int id;
};

/* Compare of transitions for the final reduction of transitions. Comparison
 * is on target and the pointer to the shared action table. It is assumed that
 * when this is used the action tables have been reduced. */
struct CmpRedTransAp
{
      static int compare( const RedTransAp &t1, const RedTransAp &t2 )
      {
            if ( t1.targ < t2.targ )
                  return -1;
            else if ( t1.targ > t2.targ )
                  return 1;
            else if ( t1.action < t2.action )
                  return -1;
            else if ( t1.action > t2.action )
                  return 1;
            else
                  return 0;
      }
};

typedef AvlBasic<RedTransAp, CmpRedTransAp> TransApSet;

/* Element in out range. */
struct RedTransEl
{
      /* Constructors. */
      RedTransEl( long lowKey, long highKey, RedTransAp *value ) 
            : lowKey(lowKey), highKey(highKey), value(value) { }

      long lowKey, highKey;
      RedTransAp *value;
};

typedef Vector<RedTransEl> RedTransList;
typedef Vector<RedStateAp*> RedStateVect;

typedef BstMapEl<RedStateAp*, unsigned long long> RedSpanMapEl;
typedef BstMap<RedStateAp*, unsigned long long> RedSpanMap;

/* Compare used by span map sort. Reverse sorts by the span. */
struct CmpRedSpanMapEl
{
      static int compare( const RedSpanMapEl &smel1, const RedSpanMapEl &smel2 )
      {
            if ( smel1.value > smel2.value )
                  return -1;
            else if ( smel1.value < smel2.value )
                  return 1;
            else
                  return 0;
      }
};

/* Sorting state-span map entries by span. */
typedef MergeSort<RedSpanMapEl, CmpRedSpanMapEl> RedSpanMapSort;


/* Reduced state. */
struct RedStateAp
{
      RedStateAp( bool isFinal, RedAction *eofAction ) : 
            defTrans(0), transList(0), isFinal(isFinal), 
            labelNeeded(false), onStateList(false), 
            eofAction(eofAction), id(0), 
            bAnyRegCurStateRef(false) { }

      /* Transitions out. */
      RedTransList outSingle;
      RedTransList outRange;
      RedTransAp *defTrans;

      /* For flat keys. */
      long lowKey, highKey;
      RedTransAp **transList;

      /* The list of states that transitions from this state go to. */
      RedStateVect targStates;

      bool isFinal;
      bool labelNeeded;
      bool onStateList;
      RedAction *eofAction;
      int id;
      ContextSet contextSet;

      /* Pointers for the list of states. */
      RedStateAp *prev, *next;

      bool anyRegCurStateRef() { return bAnyRegCurStateRef; }
      bool bAnyRegCurStateRef;
};

/* List of states. */
typedef DList<RedStateAp> RedStateList;

/* Entry points. */
struct RedEntryListEl
{
      RedEntryListEl( int key, RedStateAp *value )
            : key(key), value(value) { }

      int key;
      RedStateAp *value;
};
typedef Vector<RedEntryListEl> RedEntryList;
typedef BstMapEl<int, RedStateAp*> RedEntryMapEl;
typedef BstMap<int, RedStateAp*> RedEntryMap;

/* Set of reduced transitons. Comparison is by pointer. */
typedef BstSet< RedTransAp*, CmpOrd<RedTransAp*> > RedTransSet;

struct NextRedTrans
{
      long lowKey, highKey;
      TransAp *trans;
      RedTransAp *redTrans;
      TransAp *next;

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

      NextRedTrans( TransAp *t ) {
            trans = t;
            load();
      }

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

/* Next version of the fsm machine. */
struct RedFsmAp
{
      RedFsmAp( FsmAp *graph, bool complete );

      FsmAp *graph;
      bool complete;
      KeyOps *keyOps;

      int nextActionId;
      int nextTransId;
      int nextStateId;

      TransApSet transSet;
      ActionTableMap actionMap;
      RedStateList stateList;
      RedEntryList entryList;
      RedEntryMap entryMap;
      RedStateAp *startState;
      RedStateAp *errState;
      RedTransAp *errTrans;
      RedTransAp *errActionTrans;
      RedStateAp *firstFinState;
      int numFinStates;

      /* Is is it possible to extend a range by bumping ranges that span only
       * one character to the singles array. */
      bool canExtend( const RedTransList &list, int pos );

      /* Pick single transitions from the ranges. */
      void moveTransToSingle( RedStateAp *state );
      void chooseSingle();

      void makeFlat();

      /* Move a selected transition from ranges to default. */
      void moveToDefault( RedTransAp *defTrans, RedStateAp *state );

      /* Pick a default transition by largest span. */
      RedTransAp *chooseDefaultSpan( RedStateAp *state );
      void chooseDefaultSpan();

      /* Pick a default transition by most number of ranges. */
      RedTransAp *chooseDefaultNumRanges( RedStateAp *state );
      void chooseDefaultNumRanges();

      /* Pick a default transition tailored towards goto driven machine. */
      RedTransAp *chooseDefaultGoto( RedStateAp *state );
      void chooseDefaultGoto();

      /* Ordering states by transition connections. */
      void optimizeStateOrdering( RedStateAp *state );
      void optimizeStateOrdering();

      /* Ordering states by transition connections. */
      void depthFirstOrdering( RedStateAp *state );
      void depthFirstOrdering();

      /* Set state ids. */
      void sequentialStateIds();
      void sortStateIdsByFinal();

      /* Arrange states in by final id. This is a stable sort. */
      void sortStatesByFinal();

      /* Locating the first final state. This is the final state with the lowest
       * id. */
      void findFirstFinState();

      /*
       * Building the initial machine.
       */
      
      void assignActionLocs();

      /* Move default transitions to ranges and remove transition elements with
       * null targets. */
      bool doesExtend( RedTransList &destRange, const RedTransEl &redTel );

      RedTransAp *getErrorTrans();
      RedStateAp *getErrorState();

      void appendToRange( RedTransList &destRange, const RedTransEl &redTel, StateAp *state );
      void finishRange( RedTransList &destRange, StateAp *state );
      void defaultToRange( RedTransList &destRange, StateAp *state );

      /* Is every char in the alphabet covered? */
      bool alphabetCovered( RedTransList &outRange );

      /* Reduce transitions. Collects them all in. */
      RedTransAp *reduceTrans( TransAp *trans );
      void reduceMachine(); 
};


#endif /* _REDFSM_H */

Generated by  Doxygen 1.6.0   Back to index