rlcodegen/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 "rlcodegen.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 /*
  54  * Inline code tree
  55  */
  56 struct InlineItem
  57 {
  58         enum Type
  59         {
  60                 Text, Goto, Call, Next, GotoExpr, CallExpr, NextExpr, Ret,
  61                 PChar, Char, Hold, Exec, HoldTE, ExecTE, Curs, Targs, Entry,
  62                 LmSwitch, LmSetActId, LmSetTokEnd, LmGetTokEnd, LmInitTokStart,
  63                 LmInitAct, LmSetTokStart, SubAction, Break
  64         };
  65
  66         InlineItem( const InputLoc &loc, Type type ) :
  67                 loc(loc), data(0), targId(0), targState(0),
  68                 lmId(0), children(0), offset(0),
  69                 handlesError(false), type(type) { }
  70
  71         InputLoc loc;
  72         char *data;
  73         int targId;
  74         RedStateAp *targState;
  75         int lmId;
  76         InlineList *children;
  77         int offset;
  78         bool handlesError;
  79         Type type;
  80
  81         InlineItem *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 InlineList : public DList<InlineItem> { };
  87
  88 /* Element in list of actions. Contains the string for the code to exectute. */
  89 struct Action
  90 :
  91         public DListEl<Action>
  92 {
  93         Action( )
  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         char *name;
 108         InlineList *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 Action Element. */
 128 typedef SBstMapEl< int, Action* > ActionTableEl;
 129
 130 /* Transition Action Table.  */
 131 struct ActionTable
 132         : public SBstMap< int, Action*, CmpOrd<int> >
 133 {
 134         void setAction( int ordering, Action *action );
 135         void setActions( int *orderings, Action **actions, int nActs );
 136         void setActions( const ActionTable &other );
 137 };
 138
 139 /* Compare of a whole action table element (key & value). */
 140 struct CmpActionTableEl
 141 {
 142         static int compare( const ActionTableEl &action1,
 143                         const ActionTableEl &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 ActionTable. */
 158 typedef CmpSTable< ActionTableEl, CmpActionTableEl > CmpActionTable;
 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 ActionTable &getKey()
 183                 { return key; }
 184
 185         ActionTable key;
 186         int actListId;
 187         int location;
 188         IntSet *eofRefs;
 189
 190         /* Number of references in the final machine. */
 191         bool 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, ActionTable, CmpActionTable> ActionTableMap;
 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), labelNeeded(true) { }
 215
 216         RedStateAp *targ;
 217         RedAction *action;
 218         int id;
 219         bool partitionBoundary;
 220         bool labelNeeded;
 221 };
 222
 223 /* Compare of transitions for the final reduction of transitions. Comparison
 224  * is on target and the pointer to the shared action table. It is assumed that
 225  * when this is used the action tables have been reduced. */
 226 struct CmpRedTransAp
 227 {
 228         static int compare( const RedTransAp &t1, const RedTransAp &t2 )
 229         {
 230                 if ( t1.targ < t2.targ )
 231                         return -1;
 232                 else if ( t1.targ > t2.targ )
 233                         return 1;
 234                 else if ( t1.action < t2.action )
 235                         return -1;
 236                 else if ( t1.action > t2.action )
 237                         return 1;
 238                 else
 239                         return 0;
 240         }
 241 };
 242
 243 typedef AvlBasic<RedTransAp, CmpRedTransAp> TransApSet;
 244
 245 /* Element in out range. */
 246 struct RedTransEl
 247 {
 248         /* Constructors. */
 249         RedTransEl( Key lowKey, Key highKey, RedTransAp *value )
 250                 : lowKey(lowKey), highKey(highKey), value(value) { }
 251
 252         Key lowKey, highKey;
 253         RedTransAp *value;
 254 };
 255
 256 typedef Vector<RedTransEl> RedTransList;
 257 typedef Vector<RedStateAp*> RedStateVect;
 258
 259 typedef BstMapEl<RedStateAp*, unsigned long long> RedSpanMapEl;
 260 typedef BstMap<RedStateAp*, unsigned long long> RedSpanMap;
 261
 262 /* Compare used by span map sort. Reverse sorts by the span. */
 263 struct CmpRedSpanMapEl
 264 {
 265         static int compare( const RedSpanMapEl &smel1, const RedSpanMapEl &smel2 )
 266         {
 267                 if ( smel1.value > smel2.value )
 268                         return -1;
 269                 else if ( smel1.value < smel2.value )
 270                         return 1;
 271                 else
 272                         return 0;
 273         }
 274 };
 275
 276 /* Sorting state-span map entries by span. */
 277 typedef MergeSort<RedSpanMapEl, CmpRedSpanMapEl> RedSpanMapSort;
 278
 279 /* Set of entry ids that go into this state. */
 280 typedef Vector<int> EntryIdVect;
 281 typedef Vector<char*> EntryNameVect;
 282
 283 typedef Vector< Action* > CondSet;
 284
 285 struct Condition
 286 {
 287         Condition( )
 288                 : key(0), baseKey(0) {}
 289
 290         Key key;
 291         Key baseKey;
 292         CondSet condSet;
 293
 294         Condition *next, *prev;
 295 };
 296 typedef DList<Condition> ConditionList;
 297
 298 struct CondSpace
 299 {
 300         Key baseKey;
 301         CondSet condSet;
 302         int condSpaceId;
 303
 304         CondSpace *next, *prev;
 305 };
 306 typedef DList<CondSpace> CondSpaceList;
 307
 308 struct StateCond
 309 {
 310         Key lowKey;
 311         Key highKey;
 312
 313         CondSpace *condSpace;
 314
 315         StateCond *prev, *next;
 316 };
 317 typedef DList<StateCond> StateCondList;
 318 typedef Vector<StateCond*> StateCondVect;
 319
 320 /* Reduced state. */
 321 struct RedStateAp
 322 {
 323         RedStateAp()
 324         :
 325                 defTrans(0),
 326                 condList(0),
 327                 transList(0),
 328                 isFinal(false),
 329                 labelNeeded(false),
 330                 outNeeded(false),
 331                 onStateList(false),
 332                 toStateAction(0),
 333                 fromStateAction(0),
 334                 eofAction(0),
 335                 id(0),
 336                 bAnyRegCurStateRef(false),
 337                 partitionBoundary(false),
 338                 inTrans(0),
 339                 numInTrans(0)
 340         { }
 341
 342         /* Transitions out. */
 343         RedTransList outSingle;
 344         RedTransList outRange;
 345         RedTransAp *defTrans;
 346
 347         /* For flat conditions. */
 348         Key condLowKey, condHighKey;
 349         CondSpace **condList;
 350
 351         /* For flat keys. */
 352         Key lowKey, highKey;
 353         RedTransAp **transList;
 354
 355         /* The list of states that transitions from this state go to. */
 356         RedStateVect targStates;
 357
 358         bool isFinal;
 359         bool labelNeeded;
 360         bool outNeeded;
 361         bool onStateList;
 362         RedAction *toStateAction;
 363         RedAction *fromStateAction;
 364         RedAction *eofAction;
 365         int id;
 366         StateCondList stateCondList;
 367         StateCondVect stateCondVect;
 368
 369         /* Pointers for the list of states. */
 370         RedStateAp *prev, *next;
 371
 372         bool anyRegCurStateRef() { return bAnyRegCurStateRef; }
 373         bool bAnyRegCurStateRef;
 374
 375         int partition;
 376         bool partitionBoundary;
 377
 378         RedTransAp **inTrans;
 379         int numInTrans;
 380 };
 381
 382 /* List of states. */
 383 typedef DList<RedStateAp> RedStateList;
 384
 385 /* Set of reduced transitons. Comparison is by pointer. */
 386 typedef BstSet< RedTransAp*, CmpOrd<RedTransAp*> > RedTransSet;
 387
 388 /* Next version of the fsm machine. */
 389 struct RedFsmAp
 390 {
 391         RedFsmAp();
 392
 393         bool wantComplete;
 394         bool forcedErrorState;
 395
 396         int nextActionId;
 397         int nextTransId;
 398
 399         /* Next State Id doubles as the total number of state ids. */
 400         int nextStateId;
 401
 402         TransApSet transSet;
 403         ActionTableMap actionMap;
 404         RedStateList stateList;
 405         RedStateSet entryPoints;
 406         RedStateAp *startState;
 407         RedStateAp *errState;
 408         RedTransAp *errTrans;
 409         RedTransAp *errActionTrans;
 410         RedStateAp *firstFinState;
 411         int numFinStates;
 412         int nParts;
 413
 414         /* Is is it possible to extend a range by bumping ranges that span only
 415          * one character to the singles array. */
 416         bool canExtend( const RedTransList &list, int pos );
 417
 418         /* Pick single transitions from the ranges. */
 419         void moveTransToSingle( RedStateAp *state );
 420         void chooseSingle();
 421
 422         void makeFlat();
 423
 424         /* Move a selected transition from ranges to default. */
 425         void moveToDefault( RedTransAp *defTrans, RedStateAp *state );
 426
 427         /* Pick a default transition by largest span. */
 428         RedTransAp *chooseDefaultSpan( RedStateAp *state );
 429         void chooseDefaultSpan();
 430
 431         /* Pick a default transition by most number of ranges. */
 432         RedTransAp *chooseDefaultNumRanges( RedStateAp *state );
 433         void chooseDefaultNumRanges();
 434
 435         /* Pick a default transition tailored towards goto driven machine. */
 436         RedTransAp *chooseDefaultGoto( RedStateAp *state );
 437         void chooseDefaultGoto();
 438
 439         /* Ordering states by transition connections. */
 440         void optimizeStateOrdering( RedStateAp *state );
 441         void optimizeStateOrdering();
 442
 443         /* Ordering states by transition connections. */
 444         void depthFirstOrdering( RedStateAp *state );
 445         void depthFirstOrdering();
 446
 447         /* Set state ids. */
 448         void sequentialStateIds();
 449         void sortStateIdsByFinal();
 450
 451         /* Arrange states in by final id. This is a stable sort. */
 452         void sortStatesByFinal();
 453
 454         /* Locating the first final state. This is the final state with the lowest
 455          * id. */
 456         void findFirstFinState();
 457
 458         void assignActionLocs();
 459
 460         RedTransAp *getErrorTrans();
 461         RedStateAp *getErrorState();
 462
 463         /* Is every char in the alphabet covered? */
 464         bool alphabetCovered( RedTransList &outRange );
 465
 466         RedTransAp *allocateTrans( RedStateAp *targState, RedAction *actionTable );
 467
 468         void partitionFsm( int nParts );
 469
 470         void setInTrans();
 471 };
 472
 473
 474 #endif /* _REDFSM_H */