redfsm/redfsm.h

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