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