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), pos(-1), labelNeeded(true) { }
 221
 222         RedStateAp *targ;
 223         RedAction *action;
 224         int id;
 225         int pos;
 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                 eofTrans(0),
 343                 id(0),
 344                 bAnyRegCurStateRef(false),
 345                 partitionBoundary(false),
 346                 inTrans(0),
 347                 numInTrans(0)
 348         { }
 349
 350         /* Transitions out. */
 351         RedTransList outSingle;
 352         RedTransList outRange;
 353         RedTransAp *defTrans;
 354
 355         /* For flat conditions. */
 356         Key condLowKey, condHighKey;
 357         CondSpace **condList;
 358
 359         /* For flat keys. */
 360         Key lowKey, highKey;
 361         RedTransAp **transList;
 362
 363         /* The list of states that transitions from this state go to. */
 364         RedStateVect targStates;
 365
 366         bool isFinal;
 367         bool labelNeeded;
 368         bool outNeeded;
 369         bool onStateList;
 370         RedAction *toStateAction;
 371         RedAction *fromStateAction;
 372         RedAction *eofAction;
 373         RedTransAp *eofTrans;
 374         int id;
 375         StateCondList stateCondList;
 376         StateCondVect stateCondVect;
 377
 378         /* Pointers for the list of states. */
 379         RedStateAp *prev, *next;
 380
 381         bool anyRegCurStateRef() { return bAnyRegCurStateRef; }
 382         bool bAnyRegCurStateRef;
 383
 384         int partition;
 385         bool partitionBoundary;
 386
 387         RedTransAp **inTrans;
 388         int numInTrans;
 389 };
 390
 391 /* List of states. */
 392 typedef DList<RedStateAp> RedStateList;
 393
 394 /* Set of reduced transitons. Comparison is by pointer. */
 395 typedef BstSet< RedTransAp*, CmpOrd<RedTransAp*> > RedTransSet;
 396
 397 /* Next version of the fsm machine. */
 398 struct RedFsmAp
 399 {
 400         RedFsmAp();
 401
 402         bool forcedErrorState;
 403
 404         int nextActionId;
 405         int nextTransId;
 406
 407         /* Next State Id doubles as the total number of state ids. */
 408         int nextStateId;
 409
 410         TransApSet transSet;
 411         ActionTableMap actionMap;
 412         RedStateList stateList;
 413         RedStateSet entryPoints;
 414         RedStateAp *startState;
 415         RedStateAp *errState;
 416         RedTransAp *errTrans;
 417         RedTransAp *errActionTrans;
 418         RedStateAp *firstFinState;
 419         int numFinStates;
 420         int nParts;
 421
 422         bool bAnyToStateActions;
 423         bool bAnyFromStateActions;
 424         bool bAnyRegActions;
 425         bool bAnyEofActions;
 426         bool bAnyEofTrans;
 427         bool bAnyActionGotos;
 428         bool bAnyActionCalls;
 429         bool bAnyActionRets;
 430         bool bAnyRegActionRets;
 431         bool bAnyRegActionByValControl;
 432         bool bAnyRegNextStmt;
 433         bool bAnyRegCurStateRef;
 434         bool bAnyRegBreak;
 435         bool bAnyConditions;
 436
 437         int maxState;
 438         int maxSingleLen;
 439         int maxRangeLen;
 440         int maxKeyOffset;
 441         int maxIndexOffset;
 442         int maxIndex;
 443         int maxActListId;
 444         int maxActionLoc;
 445         int maxActArrItem;
 446         unsigned long long maxSpan;
 447         unsigned long long maxCondSpan;
 448         int maxFlatIndexOffset;
 449         Key maxKey;
 450         int maxCondOffset;
 451         int maxCondLen;
 452         int maxCondSpaceId;
 453         int maxCondIndexOffset;
 454         int maxCond;
 455
 456         bool anyActions();
 457         bool anyToStateActions()        { return bAnyToStateActions; }
 458         bool anyFromStateActions()      { return bAnyFromStateActions; }
 459         bool anyRegActions()            { return bAnyRegActions; }
 460         bool anyEofActions()            { return bAnyEofActions; }
 461         bool anyEofTrans()              { return bAnyEofTrans; }
 462         bool anyActionGotos()           { return bAnyActionGotos; }
 463         bool anyActionCalls()           { return bAnyActionCalls; }
 464         bool anyActionRets()            { return bAnyActionRets; }
 465         bool anyRegActionRets()         { return bAnyRegActionRets; }
 466         bool anyRegActionByValControl() { return bAnyRegActionByValControl; }
 467         bool anyRegNextStmt()           { return bAnyRegNextStmt; }
 468         bool anyRegCurStateRef()        { return bAnyRegCurStateRef; }
 469         bool anyRegBreak()              { return bAnyRegBreak; }
 470         bool anyConditions()            { return bAnyConditions; }
 471
 472
 473         /* Is is it possible to extend a range by bumping ranges that span only
 474          * one character to the singles array. */
 475         bool canExtend( const RedTransList &list, int pos );
 476
 477         /* Pick single transitions from the ranges. */
 478         void moveTransToSingle( RedStateAp *state );
 479         void chooseSingle();
 480
 481         void makeFlat();
 482
 483         /* Move a selected transition from ranges to default. */
 484         void moveToDefault( RedTransAp *defTrans, RedStateAp *state );
 485
 486         /* Pick a default transition by largest span. */
 487         RedTransAp *chooseDefaultSpan( RedStateAp *state );
 488         void chooseDefaultSpan();
 489
 490         /* Pick a default transition by most number of ranges. */
 491         RedTransAp *chooseDefaultNumRanges( RedStateAp *state );
 492         void chooseDefaultNumRanges();
 493
 494         /* Pick a default transition tailored towards goto driven machine. */
 495         RedTransAp *chooseDefaultGoto( RedStateAp *state );
 496         void chooseDefaultGoto();
 497
 498         /* Ordering states by transition connections. */
 499         void optimizeStateOrdering( RedStateAp *state );
 500         void optimizeStateOrdering();
 501
 502         /* Ordering states by transition connections. */
 503         void depthFirstOrdering( RedStateAp *state );
 504         void depthFirstOrdering();
 505
 506         /* Set state ids. */
 507         void sequentialStateIds();
 508         void sortStateIdsByFinal();
 509
 510         /* Arrange states in by final id. This is a stable sort. */
 511         void sortStatesByFinal();
 512
 513         /* Sorting states by id. */
 514         void sortByStateId();
 515
 516         /* Locating the first final state. This is the final state with the lowest
 517          * id. */
 518         void findFirstFinState();
 519
 520         void assignActionLocs();
 521
 522         RedTransAp *getErrorTrans();
 523         RedStateAp *getErrorState();
 524
 525         /* Is every char in the alphabet covered? */
 526         bool alphabetCovered( RedTransList &outRange );
 527
 528         RedTransAp *allocateTrans( RedStateAp *targState, RedAction *actionTable );
 529
 530         void partitionFsm( int nParts );
 531
 532         void setInTrans();
 533 };
 534
 535
 536 #endif /* _REDFSM_H */