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 "common.h"
  29 #include "vector.h"
  30 #include "dlist.h"
  31 #include "compare.h"
  32 #include "bstmap.h"
  33 #include "bstset.h"
  34 #include "avlmap.h"
  35 #include "avltree.h"
  36 #include "avlbasic.h"
  37 #include "mergesort.h"
  38 #include "sbstmap.h"
  39 #include "sbstset.h"
  40 #include "sbsttable.h"
  41
  42 #define TRANS_ERR_TRANS   0
  43 #define STATE_ERR_STATE   0
  44 #define FUNC_NO_FUNC      0
  45
  46 using std::string;
  47
  48 struct RedStateAp;
  49 struct InlineList;
  50 struct Action;
  51
  52 /* Location in an input file. */
  53 struct InputLoc
  54 {
  55         int line;
  56         int col;
  57 };
  58
  59 /*
  60  * Inline code tree
  61  */
  62 struct InlineItem
  63 {
  64         enum Type
  65         {
  66                 Text, Goto, Call, Next, GotoExpr, CallExpr, NextExpr, Ret,
  67                 PChar, Char, Hold, Exec, HoldTE, ExecTE, Curs, Targs, Entry,
  68                 LmSwitch, LmSetActId, LmSetTokEnd, LmGetTokEnd, LmInitTokStart,
  69                 LmInitAct, LmSetTokStart, SubAction, Break
  70         };
  71
  72         InlineItem( const InputLoc &loc, Type type ) :
  73                 loc(loc), data(0), targId(0), targState(0),
  74                 lmId(0), children(0), offset(0),
  75                 handlesError(false), type(type) { }
  76
  77         InputLoc loc;
  78         char *data;
  79         int targId;
  80         RedStateAp *targState;
  81         int lmId;
  82         InlineList *children;
  83         int offset;
  84         bool handlesError;
  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         bool 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                 id(0),
 342                 bAnyRegCurStateRef(false),
 343                 partitionBoundary(false),
 344                 inTrans(0),
 345                 numInTrans(0)
 346         { }
 347
 348         /* Transitions out. */
 349         RedTransList outSingle;
 350         RedTransList outRange;
 351         RedTransAp *defTrans;
 352
 353         /* For flat conditions. */
 354         Key condLowKey, condHighKey;
 355         CondSpace **condList;
 356
 357         /* For flat keys. */
 358         Key lowKey, highKey;
 359         RedTransAp **transList;
 360
 361         /* The list of states that transitions from this state go to. */
 362         RedStateVect targStates;
 363
 364         bool isFinal;
 365         bool labelNeeded;
 366         bool outNeeded;
 367         bool onStateList;
 368         RedAction *toStateAction;
 369         RedAction *fromStateAction;
 370         RedAction *eofAction;
 371         int id;
 372         StateCondList stateCondList;
 373         StateCondVect stateCondVect;
 374
 375         /* Pointers for the list of states. */
 376         RedStateAp *prev, *next;
 377
 378         bool anyRegCurStateRef() { return bAnyRegCurStateRef; }
 379         bool bAnyRegCurStateRef;
 380
 381         int partition;
 382         bool partitionBoundary;
 383
 384         RedTransAp **inTrans;
 385         int numInTrans;
 386 };
 387
 388 /* List of states. */
 389 typedef DList<RedStateAp> RedStateList;
 390
 391 /* Set of reduced transitons. Comparison is by pointer. */
 392 typedef BstSet< RedTransAp*, CmpOrd<RedTransAp*> > RedTransSet;
 393
 394 /* Next version of the fsm machine. */
 395 struct RedFsmAp
 396 {
 397         RedFsmAp();
 398
 399         bool wantComplete;
 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         /* Locating the first final state. This is the final state with the lowest
 512          * id. */
 513         void findFirstFinState();
 514
 515         void assignActionLocs();
 516
 517         RedTransAp *getErrorTrans();
 518         RedStateAp *getErrorState();
 519
 520         /* Is every char in the alphabet covered? */
 521         bool alphabetCovered( RedTransList &outRange );
 522
 523         RedTransAp *allocateTrans( RedStateAp *targState, RedAction *actionTable );
 524
 525         void partitionFsm( int nParts );
 526
 527         void setInTrans();
 528 };
 529
 530
 531 #endif /* _REDFSM_H */