ragel/redfsm.h

   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 bAnyRegActionRets;
 425         bool bAnyRegActionByValControl;
 426         bool bAnyRegNextStmt;
 427         bool bAnyRegCurStateRef;
 428         bool bAnyRegBreak;
 429         bool bAnyConditions;
 430
 431         int maxState;
 432         int maxSingleLen;
 433         int maxRangeLen;
 434         int maxKeyOffset;
 435         int maxIndexOffset;
 436         int maxIndex;
 437         int maxActListId;
 438         int maxActionLoc;
 439         int maxActArrItem;
 440         unsigned long long maxSpan;
 441         unsigned long long maxCondSpan;
 442         int maxFlatIndexOffset;
 443         Key maxKey;
 444         int maxCondOffset;
 445         int maxCondLen;
 446         int maxCondSpaceId;
 447         int maxCondIndexOffset;
 448         int maxCond;
 449
 450         bool anyActions();
 451         bool anyToStateActions()        { return bAnyToStateActions; }
 452         bool anyFromStateActions()      { return bAnyFromStateActions; }
 453         bool anyRegActions()            { return bAnyRegActions; }
 454         bool anyEofActions()            { return bAnyEofActions; }
 455         bool anyEofTrans()              { return bAnyEofTrans; }
 456         bool anyActionGotos()           { return bAnyActionGotos; }
 457         bool anyActionCalls()           { return bAnyActionCalls; }
 458         bool anyActionRets()            { return bAnyActionRets; }
 459         bool anyRegActionRets()         { return bAnyRegActionRets; }
 460         bool anyRegActionByValControl() { return bAnyRegActionByValControl; }
 461         bool anyRegNextStmt()           { return bAnyRegNextStmt; }
 462         bool anyRegCurStateRef()        { return bAnyRegCurStateRef; }
 463         bool anyRegBreak()              { return bAnyRegBreak; }
 464         bool anyConditions()            { return bAnyConditions; }
 465
 466
 467         /* Is is it possible to extend a range by bumping ranges that span only
 468          * one character to the singles array. */
 469         bool canExtend( const RedTransList &list, int pos );
 470
 471         /* Pick single transitions from the ranges. */
 472         void moveTransToSingle( RedStateAp *state );
 473         void chooseSingle();
 474
 475         void makeFlat();
 476
 477         /* Move a selected transition from ranges to default. */
 478         void moveToDefault( RedTransAp *defTrans, RedStateAp *state );
 479
 480         /* Pick a default transition by largest span. */
 481         RedTransAp *chooseDefaultSpan( RedStateAp *state );
 482         void chooseDefaultSpan();
 483
 484         /* Pick a default transition by most number of ranges. */
 485         RedTransAp *chooseDefaultNumRanges( RedStateAp *state );
 486         void chooseDefaultNumRanges();
 487
 488         /* Pick a default transition tailored towards goto driven machine. */
 489         RedTransAp *chooseDefaultGoto( RedStateAp *state );
 490         void chooseDefaultGoto();
 491
 492         /* Ordering states by transition connections. */
 493         void optimizeStateOrdering( RedStateAp *state );
 494         void optimizeStateOrdering();
 495
 496         /* Ordering states by transition connections. */
 497         void depthFirstOrdering( RedStateAp *state );
 498         void depthFirstOrdering();
 499
 500         /* Set state ids. */
 501         void sequentialStateIds();
 502         void sortStateIdsByFinal();
 503
 504         /* Arrange states in by final id. This is a stable sort. */
 505         void sortStatesByFinal();
 506
 507         /* Sorting states by id. */
 508         void sortByStateId();
 509
 510         /* Locating the first final state. This is the final state with the lowest
 511          * id. */
 512         void findFirstFinState();
 513
 514         void assignActionLocs();
 515
 516         RedTransAp *getErrorTrans();
 517         RedStateAp *getErrorState();
 518
 519         /* Is every char in the alphabet covered? */
 520         bool alphabetCovered( RedTransList &outRange );
 521
 522         RedTransAp *allocateTrans( RedStateAp *targState, RedAction *actionTable );
 523
 524         void partitionFsm( int nParts );
 525
 526         void setInTrans();
 527 };
 528
 529
 530 #endif