"Fossies" - the Fresh Open Source Software Archive

Member "ragel-6.10/ragel/redfsm.h" (24 Mar 2017, 12541 Bytes) of package /linux/misc/ragel-6.10.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "redfsm.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 6.9_vs_6.10.

    1 /*
    2  *  Copyright 2001-2006 Adrian Thurston <thurston@complang.org>
    3  */
    4 
    5 /*  This file is part of Ragel.
    6  *
    7  *  Ragel is free software; you can redistribute it and/or modify
    8  *  it under the terms of the GNU General Public License as published by
    9  *  the Free Software Foundation; either version 2 of the License, or
   10  *  (at your option) any later version.
   11  * 
   12  *  Ragel is distributed in the hope that it will be useful,
   13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   15  *  GNU General Public License for more details.
   16  * 
   17  *  You should have received a copy of the GNU General Public License
   18  *  along with Ragel; if not, write to the Free Software
   19  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
   20  */
   21 
   22 #ifndef _REDFSM_H
   23 #define _REDFSM_H
   24 
   25 #include <assert.h>
   26 #include <string.h>
   27 #include <string>
   28 #include "config.h"
   29 #include "common.h"
   30 #include "vector.h"
   31 #include "dlist.h"
   32 #include "compare.h"
   33 #include "bstmap.h"
   34 #include "bstset.h"
   35 #include "avlmap.h"
   36 #include "avltree.h"
   37 #include "avlbasic.h"
   38 #include "mergesort.h"
   39 #include "sbstmap.h"
   40 #include "sbstset.h"
   41 #include "sbsttable.h"
   42 
   43 
   44 #define TRANS_ERR_TRANS   0
   45 #define STATE_ERR_STATE   0
   46 #define FUNC_NO_FUNC      0
   47 
   48 using std::string;
   49 
   50 struct RedStateAp;
   51 struct GenInlineList;
   52 struct GenAction;
   53 
   54 /*
   55  * Inline code tree
   56  */
   57 struct GenInlineItem
   58 {
   59     enum Type 
   60     {
   61         Text, Goto, Call, Next, GotoExpr, CallExpr, NextExpr, Ret, 
   62         PChar, Char, Hold, Exec, Curs, Targs, Entry,
   63         LmSwitch, LmSetActId, LmSetTokEnd, LmGetTokEnd, LmInitTokStart,
   64         LmInitAct, LmSetTokStart, SubAction, Break
   65     };
   66 
   67     GenInlineItem( const InputLoc &loc, Type type ) : 
   68         loc(loc), data(0), targId(0), targState(0), 
   69         lmId(0), children(0), offset(0),
   70         type(type) { }
   71     
   72     InputLoc loc;
   73     char *data;
   74     int targId;
   75     RedStateAp *targState;
   76     int lmId;
   77     GenInlineList *children;
   78     int offset;
   79     Type type;
   80 
   81     GenInlineItem *prev, *next;
   82 };
   83 
   84 /* Normally this would be atypedef, but that would entail including DList from
   85  * ptreetypes, which should be just typedef forwards. */
   86 struct GenInlineList : public DList<GenInlineItem> { };
   87 
   88 /* Element in list of actions. Contains the string for the code to exectute. */
   89 struct GenAction 
   90 :
   91     public DListEl<GenAction>
   92 {
   93     GenAction( )
   94     :
   95         name(0),
   96         inlineList(0), 
   97         actionId(0),
   98         numTransRefs(0),
   99         numToStateRefs(0),
  100         numFromStateRefs(0),
  101         numEofRefs(0)
  102     {
  103     }
  104 
  105     /* Data collected during parse. */
  106     InputLoc loc;
  107     const char *name;
  108     GenInlineList *inlineList;
  109     int actionId;
  110 
  111     string nameOrLoc();
  112 
  113     /* Number of references in the final machine. */
  114     int numRefs() 
  115         { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; }
  116     int numTransRefs;
  117     int numToStateRefs;
  118     int numFromStateRefs;
  119     int numEofRefs;
  120 };
  121 
  122 
  123 /* Forwards. */
  124 struct RedStateAp;
  125 struct StateAp;
  126 
  127 /* Transistion GenAction Element. */
  128 typedef SBstMapEl< int, GenAction* > GenActionTableEl;
  129 
  130 /* Transition GenAction Table.  */
  131 struct GenActionTable 
  132     : public SBstMap< int, GenAction*, CmpOrd<int> >
  133 {
  134     void setAction( int ordering, GenAction *action );
  135     void setActions( int *orderings, GenAction **actions, int nActs );
  136     void setActions( const GenActionTable &other );
  137 };
  138 
  139 /* Compare of a whole action table element (key & value). */
  140 struct CmpGenActionTableEl
  141 {
  142     static int compare( const GenActionTableEl &action1, 
  143             const GenActionTableEl &action2 )
  144     {
  145         if ( action1.key < action2.key )
  146             return -1;
  147         else if ( action1.key > action2.key )
  148             return 1;
  149         else if ( action1.value < action2.value )
  150             return -1;
  151         else if ( action1.value > action2.value )
  152             return 1;
  153         return 0;
  154     }
  155 };
  156 
  157 /* Compare for GenActionTable. */
  158 typedef CmpSTable< GenActionTableEl, CmpGenActionTableEl > CmpGenActionTable;
  159 
  160 /* Set of states. */
  161 typedef BstSet<RedStateAp*> RedStateSet;
  162 typedef BstSet<int> IntSet;
  163 
  164 /* Reduced action. */
  165 struct RedAction
  166 :
  167     public AvlTreeEl<RedAction>
  168 {
  169     RedAction( )
  170     :   
  171         key(), 
  172         eofRefs(0),
  173         numTransRefs(0),
  174         numToStateRefs(0),
  175         numFromStateRefs(0),
  176         numEofRefs(0),
  177         bAnyNextStmt(false), 
  178         bAnyCurStateRef(false),
  179         bAnyBreakStmt(false)
  180     { }
  181     
  182     const GenActionTable &getKey() 
  183         { return key; }
  184 
  185     GenActionTable key;
  186     int actListId;
  187     int location;
  188     IntSet *eofRefs;
  189 
  190     /* Number of references in the final machine. */
  191     int numRefs() 
  192         { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; }
  193     int numTransRefs;
  194     int numToStateRefs;
  195     int numFromStateRefs;
  196     int numEofRefs;
  197 
  198     bool anyNextStmt() { return bAnyNextStmt; }
  199     bool anyCurStateRef() { return bAnyCurStateRef; }
  200     bool anyBreakStmt() { return bAnyBreakStmt; }
  201 
  202     bool bAnyNextStmt;
  203     bool bAnyCurStateRef;
  204     bool bAnyBreakStmt;
  205 };
  206 typedef AvlTree<RedAction, GenActionTable, CmpGenActionTable> GenActionTableMap;
  207 
  208 /* Reduced transition. */
  209 struct RedTransAp
  210 :
  211     public AvlTreeEl<RedTransAp>
  212 {
  213     RedTransAp( RedStateAp *targ, RedAction *action, int id )
  214         : targ(targ), action(action), id(id), pos(-1), labelNeeded(true) { }
  215 
  216     RedStateAp *targ;
  217     RedAction *action;
  218     int id;
  219     int pos;
  220     bool partitionBoundary;
  221     bool labelNeeded;
  222 };
  223 
  224 /* Compare of transitions for the final reduction of transitions. Comparison
  225  * is on target and the pointer to the shared action table. It is assumed that
  226  * when this is used the action tables have been reduced. */
  227 struct CmpRedTransAp
  228 {
  229     static int compare( const RedTransAp &t1, const RedTransAp &t2 )
  230     {
  231         if ( t1.targ < t2.targ )
  232             return -1;
  233         else if ( t1.targ > t2.targ )
  234             return 1;
  235         else if ( t1.action < t2.action )
  236             return -1;
  237         else if ( t1.action > t2.action )
  238             return 1;
  239         else
  240             return 0;
  241     }
  242 };
  243 
  244 typedef AvlBasic<RedTransAp, CmpRedTransAp> TransApSet;
  245 
  246 /* Element in out range. */
  247 struct RedTransEl
  248 {
  249     /* Constructors. */
  250     RedTransEl( Key lowKey, Key highKey, RedTransAp *value ) 
  251         : lowKey(lowKey), highKey(highKey), value(value) { }
  252 
  253     Key lowKey, highKey;
  254     RedTransAp *value;
  255 };
  256 
  257 typedef Vector<RedTransEl> RedTransList;
  258 typedef Vector<RedStateAp*> RedStateVect;
  259 
  260 typedef BstMapEl<RedStateAp*, unsigned long long> RedSpanMapEl;
  261 typedef BstMap<RedStateAp*, unsigned long long> RedSpanMap;
  262 
  263 /* Compare used by span map sort. Reverse sorts by the span. */
  264 struct CmpRedSpanMapEl
  265 {
  266     static int compare( const RedSpanMapEl &smel1, const RedSpanMapEl &smel2 )
  267     {
  268         if ( smel1.value > smel2.value )
  269             return -1;
  270         else if ( smel1.value < smel2.value )
  271             return 1;
  272         else
  273             return 0;
  274     }
  275 };
  276 
  277 /* Sorting state-span map entries by span. */
  278 typedef MergeSort<RedSpanMapEl, CmpRedSpanMapEl> RedSpanMapSort;
  279 
  280 /* Set of entry ids that go into this state. */
  281 typedef Vector<int> EntryIdVect;
  282 typedef Vector<char*> EntryNameVect;
  283 
  284 typedef Vector< GenAction* > GenCondSet;
  285 
  286 struct Condition
  287 {
  288     Condition( )
  289         : key(0), baseKey(0) {}
  290 
  291     Key key;
  292     Key baseKey;
  293     GenCondSet condSet;
  294 
  295     Condition *next, *prev;
  296 };
  297 typedef DList<Condition> ConditionList;
  298 
  299 struct GenCondSpace
  300 {
  301     Key baseKey;
  302     GenCondSet condSet;
  303     int condSpaceId;
  304 
  305     GenCondSpace *next, *prev;
  306 };
  307 typedef DList<GenCondSpace> CondSpaceList;
  308 
  309 struct GenStateCond
  310 {
  311     Key lowKey;
  312     Key highKey;
  313 
  314     GenCondSpace *condSpace;
  315 
  316     GenStateCond *prev, *next;
  317 };
  318 typedef DList<GenStateCond> GenStateCondList;
  319 typedef Vector<GenStateCond*> StateCondVect;
  320 
  321 /* Reduced state. */
  322 struct RedStateAp
  323 {
  324     RedStateAp()
  325     : 
  326         defTrans(0), 
  327         condList(0),
  328         transList(0), 
  329         isFinal(false), 
  330         labelNeeded(false), 
  331         outNeeded(false), 
  332         onStateList(false), 
  333         toStateAction(0), 
  334         fromStateAction(0), 
  335         eofAction(0), 
  336         eofTrans(0), 
  337         id(0), 
  338         bAnyRegCurStateRef(false),
  339         partitionBoundary(false),
  340         inTrans(0),
  341         numInTrans(0)
  342     { }
  343 
  344     /* Transitions out. */
  345     RedTransList outSingle;
  346     RedTransList outRange;
  347     RedTransAp *defTrans;
  348 
  349     /* For flat conditions. */
  350     Key condLowKey, condHighKey;
  351     GenCondSpace **condList;
  352 
  353     /* For flat keys. */
  354     Key lowKey, highKey;
  355     RedTransAp **transList;
  356 
  357     /* The list of states that transitions from this state go to. */
  358     RedStateVect targStates;
  359 
  360     bool isFinal;
  361     bool labelNeeded;
  362     bool outNeeded;
  363     bool onStateList;
  364     RedAction *toStateAction;
  365     RedAction *fromStateAction;
  366     RedAction *eofAction;
  367     RedTransAp *eofTrans;
  368     int id;
  369     GenStateCondList stateCondList;
  370     StateCondVect stateCondVect;
  371 
  372     /* Pointers for the list of states. */
  373     RedStateAp *prev, *next;
  374 
  375     bool anyRegCurStateRef() { return bAnyRegCurStateRef; }
  376     bool bAnyRegCurStateRef;
  377 
  378     int partition;
  379     bool partitionBoundary;
  380 
  381     RedTransAp **inTrans;
  382     int numInTrans;
  383 };
  384 
  385 /* List of states. */
  386 typedef DList<RedStateAp> RedStateList;
  387 
  388 /* Set of reduced transitons. Comparison is by pointer. */
  389 typedef BstSet< RedTransAp*, CmpOrd<RedTransAp*> > RedTransSet;
  390 
  391 /* Next version of the fsm machine. */
  392 struct RedFsmAp
  393 {
  394     RedFsmAp();
  395 
  396     bool forcedErrorState;
  397 
  398     int nextActionId;
  399     int nextTransId;
  400 
  401     /* Next State Id doubles as the total number of state ids. */
  402     int nextStateId;
  403 
  404     TransApSet transSet;
  405     GenActionTableMap actionMap;
  406     RedStateList stateList;
  407     RedStateSet entryPoints;
  408     RedStateAp *startState;
  409     RedStateAp *errState;
  410     RedTransAp *errTrans;
  411     RedTransAp *errActionTrans;
  412     RedStateAp *firstFinState;
  413     int numFinStates;
  414     int nParts;
  415 
  416     bool bAnyToStateActions;
  417     bool bAnyFromStateActions;
  418     bool bAnyRegActions;
  419     bool bAnyEofActions;
  420     bool bAnyEofTrans;
  421     bool bAnyActionGotos;
  422     bool bAnyActionCalls;
  423     bool bAnyActionRets;
  424     bool bAnyActionByValControl;
  425     bool bAnyRegActionRets;
  426     bool bAnyRegActionByValControl;
  427     bool bAnyRegNextStmt;
  428     bool bAnyRegCurStateRef;
  429     bool bAnyRegBreak;
  430     bool bAnyConditions;
  431 
  432     int maxState;
  433     int maxSingleLen;
  434     int maxRangeLen;
  435     int maxKeyOffset;
  436     int maxIndexOffset;
  437     int maxIndex;
  438     int maxActListId;
  439     int maxActionLoc;
  440     int maxActArrItem;
  441     unsigned long long maxSpan;
  442     unsigned long long maxCondSpan;
  443     int maxFlatIndexOffset;
  444     Key maxKey;
  445     int maxCondOffset;
  446     int maxCondLen;
  447     int maxCondSpaceId;
  448     int maxCondIndexOffset;
  449     int maxCond;
  450 
  451     bool anyActions();
  452     bool anyToStateActions()        { return bAnyToStateActions; }
  453     bool anyFromStateActions()      { return bAnyFromStateActions; }
  454     bool anyRegActions()            { return bAnyRegActions; }
  455     bool anyEofActions()            { return bAnyEofActions; }
  456     bool anyEofTrans()              { return bAnyEofTrans; }
  457     bool anyActionGotos()           { return bAnyActionGotos; }
  458     bool anyActionCalls()           { return bAnyActionCalls; }
  459     bool anyActionRets()            { return bAnyActionRets; }
  460     bool anyActionByValControl()    { return bAnyActionByValControl; }
  461     bool anyRegActionRets()         { return bAnyRegActionRets; }
  462     bool anyRegActionByValControl() { return bAnyRegActionByValControl; }
  463     bool anyRegNextStmt()           { return bAnyRegNextStmt; }
  464     bool anyRegCurStateRef()        { return bAnyRegCurStateRef; }
  465     bool anyRegBreak()              { return bAnyRegBreak; }
  466     bool anyConditions()            { return bAnyConditions; }
  467 
  468 
  469     /* Is is it possible to extend a range by bumping ranges that span only
  470      * one character to the singles array. */
  471     bool canExtend( const RedTransList &list, int pos );
  472 
  473     /* Pick single transitions from the ranges. */
  474     void moveTransToSingle( RedStateAp *state );
  475     void chooseSingle();
  476 
  477     void makeFlat();
  478 
  479     /* Move a selected transition from ranges to default. */
  480     void moveToDefault( RedTransAp *defTrans, RedStateAp *state );
  481 
  482     /* Pick a default transition by largest span. */
  483     RedTransAp *chooseDefaultSpan( RedStateAp *state );
  484     void chooseDefaultSpan();
  485 
  486     /* Pick a default transition by most number of ranges. */
  487     RedTransAp *chooseDefaultNumRanges( RedStateAp *state );
  488     void chooseDefaultNumRanges();
  489 
  490     /* Pick a default transition tailored towards goto driven machine. */
  491     RedTransAp *chooseDefaultGoto( RedStateAp *state );
  492     void chooseDefaultGoto();
  493 
  494     /* Ordering states by transition connections. */
  495     void optimizeStateOrdering( RedStateAp *state );
  496     void optimizeStateOrdering();
  497 
  498     /* Ordering states by transition connections. */
  499     void depthFirstOrdering( RedStateAp *state );
  500     void depthFirstOrdering();
  501 
  502     /* Set state ids. */
  503     void sequentialStateIds();
  504     void sortStateIdsByFinal();
  505 
  506     /* Arrange states in by final id. This is a stable sort. */
  507     void sortStatesByFinal();
  508 
  509     /* Sorting states by id. */
  510     void sortByStateId();
  511 
  512     /* Locating the first final state. This is the final state with the lowest
  513      * id. */
  514     void findFirstFinState();
  515 
  516     void assignActionLocs();
  517 
  518     RedTransAp *getErrorTrans();
  519     RedStateAp *getErrorState();
  520 
  521     /* Is every char in the alphabet covered? */
  522     bool alphabetCovered( RedTransList &outRange );
  523 
  524     RedTransAp *allocateTrans( RedStateAp *targState, RedAction *actionTable );
  525 
  526     void partitionFsm( int nParts );
  527 
  528     void setInTrans();
  529 };
  530 
  531 
  532 #endif