rlcodegen/gendata.cpp

   1 /*
   2  *  Copyright 2005-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 #include "gendata.h"
  23
  24 /* Code Generators. */
  25 #include "gvdotgen.h"
  26 #include "tabcodegen.h"
  27 #include "ftabcodegen.h"
  28 #include "flatcodegen.h"
  29 #include "fflatcodegen.h"
  30 #include "gotocodegen.h"
  31 #include "fgotocodegen.h"
  32 #include "ipgotocodegen.h"
  33 #include "splitcodegen.h"
  34 #include "javacodegen.h"
  35
  36 #include <iostream>
  37
  38 using std::cerr;
  39 using std::endl;
  40
  41 CodeGenData *cgd = 0;
  42
  43 void CodeGenData::createMachine()
  44 {
  45         redFsm = new RedFsmAp();
  46 }
  47
  48 void CodeGenData::initActionList( unsigned long length )
  49 {
  50         allActions = new Action[length];
  51         for ( unsigned long a = 0; a < length; a++ )
  52                 actionList.append( allActions+a );
  53 }
  54
  55 void CodeGenData::newAction( int anum, char *name, int line,
  56                 int col, InlineList *inlineList )
  57 {
  58         allActions[anum].actionId = anum;
  59         allActions[anum].name = name;
  60         allActions[anum].loc.line = line;
  61         allActions[anum].loc.col = col;
  62         allActions[anum].inlineList = inlineList;
  63 }
  64
  65 void CodeGenData::initActionTableList( unsigned long length )
  66 {
  67         allActionTables = new RedAction[length];
  68 }
  69
  70 void CodeGenData::initStateList( unsigned long length )
  71 {
  72         allStates = new RedStateAp[length];
  73         for ( unsigned long s = 0; s < length; s++ )
  74                 redFsm->stateList.append( allStates+s );
  75 }
  76
  77 void CodeGenData::setStartState( unsigned long startState )
  78 {
  79         this->startState = startState;
  80 }
  81
  82 void CodeGenData::addEntryPoint( char *name, unsigned long entryState )
  83 {
  84         entryPointIds.append( entryState );
  85         entryPointNames.append( name );
  86 }
  87
  88 void CodeGenData::initTransList( int snum, unsigned long length )
  89 {
  90         /* Could preallocate the out range to save time growing it. For now do
  91          * nothing. */
  92 }
  93
  94 void CodeGenData::newTrans( int snum, int tnum, Key lowKey,
  95                 Key highKey, long targ, long action )
  96 {
  97         /* Get the current state and range. */
  98         RedStateAp *curState = allStates + snum;
  99         RedTransList &destRange = curState->outRange;
 100
 101         /* Make the new transitions. */
 102         RedStateAp *targState = targ >= 0 ? (allStates + targ) :
 103                         wantComplete ? redFsm->getErrorState() : 0;
 104         RedAction *actionTable = action >= 0 ? (allActionTables + action) : 0;
 105         RedTransAp *trans = redFsm->allocateTrans( targState, actionTable );
 106         RedTransEl transEl( lowKey, highKey, trans );
 107
 108         if ( wantComplete ) {
 109                 /* If the machine is to be complete then we need to fill any gaps with
 110                  * the error transitions. */
 111                 if ( destRange.length() == 0 ) {
 112                         /* Range is currently empty. */
 113                         if ( keyOps->minKey < lowKey ) {
 114                                 /* The first range doesn't start at the low end. */
 115                                 Key fillHighKey = lowKey;
 116                                 fillHighKey.decrement();
 117
 118                                 /* Create the filler with the state's error transition. */
 119                                 RedTransEl newTel( keyOps->minKey, fillHighKey, redFsm->getErrorTrans() );
 120                                 destRange.append( newTel );
 121                         }
 122                 }
 123                 else {
 124                         /* The range list is not empty, get the the last range. */
 125                         RedTransEl *last = &destRange[destRange.length()-1];
 126                         Key nextKey = last->highKey;
 127                         nextKey.increment();
 128                         if ( nextKey < lowKey ) {
 129                                 /* There is a gap to fill. Make the high key. */
 130                                 Key fillHighKey = lowKey;
 131                                 fillHighKey.decrement();
 132
 133                                 /* Create the filler with the state's error transtion. */
 134                                 RedTransEl newTel( nextKey, fillHighKey, redFsm->getErrorTrans() );
 135                                 destRange.append( newTel );
 136                         }
 137                 }
 138         }
 139
 140         /* Filler taken care of. Append the range. */
 141         destRange.append( RedTransEl( lowKey, highKey, trans ) );
 142 }
 143
 144 void CodeGenData::finishTransList( int snum )
 145 {
 146         /* Get the current state and range. */
 147         RedStateAp *curState = allStates + snum;
 148         RedTransList &destRange = curState->outRange;
 149
 150         /* If building a complete machine we may need filler on the end. */
 151         if ( wantComplete ) {
 152                 /* Check if there are any ranges already. */
 153                 if ( destRange.length() == 0 ) {
 154                         /* Fill with the whole alphabet. */
 155                         /* Add the range on the lower and upper bound. */
 156                         RedTransEl newTel( keyOps->minKey, keyOps->maxKey, redFsm->getErrorTrans() );
 157                         destRange.append( newTel );
 158                 }
 159                 else {
 160                         /* Get the last and check for a gap on the end. */
 161                         RedTransEl *last = &destRange[destRange.length()-1];
 162                         if ( last->highKey < keyOps->maxKey ) {
 163                                 /* Make the high key. */
 164                                 Key fillLowKey = last->highKey;
 165                                 fillLowKey.increment();
 166
 167                                 /* Create the new range with the error trans and append it. */
 168                                 RedTransEl newTel( fillLowKey, keyOps->maxKey, redFsm->getErrorTrans() );
 169                                 destRange.append( newTel );
 170                         }
 171                 }
 172         }
 173 }
 174
 175 void CodeGenData::setFinal( int snum )
 176 {
 177         RedStateAp *curState = allStates + snum;
 178         curState->isFinal = true;
 179 }
 180
 181
 182 void CodeGenData::setStateActions( int snum, long toStateAction,
 183                         long fromStateAction, long eofAction )
 184 {
 185         RedStateAp *curState = allStates + snum;
 186         if ( toStateAction >= 0 )
 187                 curState->toStateAction = allActionTables + toStateAction;
 188         if ( fromStateAction >= 0 )
 189                 curState->fromStateAction = allActionTables + fromStateAction;
 190         if ( eofAction >= 0 )
 191                 curState->eofAction = allActionTables + eofAction;
 192 }
 193
 194 void CodeGenData::resolveTargetStates( InlineList *inlineList )
 195 {
 196         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
 197                 switch ( item->type ) {
 198                 case InlineItem::Goto: case InlineItem::Call:
 199                 case InlineItem::Next: case InlineItem::Entry:
 200                         item->targState = allStates + item->targId;
 201                         break;
 202                 default:
 203                         break;
 204                 }
 205
 206                 if ( item->children != 0 )
 207                         resolveTargetStates( item->children );
 208         }
 209 }
 210
 211
 212 void CodeGenData::finishMachine()
 213 {
 214         if ( redFsm->forcedErrorState )
 215                 redFsm->getErrorState();
 216
 217         /* We get the start state as an offset, set the pointer now. */
 218         redFsm->startState = allStates + startState;
 219         for ( EntryIdVect::Iter en = entryPointIds; en.lte(); en++ )
 220                 redFsm->entryPoints.insert( allStates + *en );
 221
 222         for ( ActionList::Iter a = actionList; a.lte(); a++ )
 223                 resolveTargetStates( a->inlineList );
 224
 225         /* Note that even if we want a complete graph we do not give the error
 226          * state a default transition. All machines break out of the processing
 227          * loop when in the error state. */
 228
 229         if ( codeStyle == GenGoto || codeStyle == GenFGoto || codeStyle == GenIpGoto ) {
 230                 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 231                         for ( StateCondList::Iter sci = st->stateCondList; sci.lte(); sci++ )
 232                                 st->stateCondVect.append( sci );
 233                 }
 234         }
 235 }
 236
 237
 238 bool CodeGenData::setAlphType( char *data )
 239 {
 240         /* FIXME: This should validate the alphabet type selection. */
 241         HostType *alphType = hostLang->hostTypes + atoi(data);
 242         thisKeyOps.setAlphType( alphType );
 243         return true;
 244 }
 245
 246 void CodeGenData::initCondSpaceList( ulong length )
 247 {
 248         allCondSpaces = new CondSpace[length];
 249         for ( ulong c = 0; c < length; c++ )
 250                 condSpaceList.append( allCondSpaces + c );
 251 }
 252
 253 void CodeGenData::newCondSpace( int cnum, int condSpaceId, Key baseKey )
 254 {
 255         CondSpace *cond = allCondSpaces + cnum;
 256         cond->condSpaceId = condSpaceId;
 257         cond->baseKey = baseKey;
 258 }
 259
 260 void CodeGenData::condSpaceItem( int cnum, long condActionId )
 261 {
 262         CondSpace *cond = allCondSpaces + cnum;
 263         cond->condSet.append( allActions + condActionId );
 264 }
 265
 266 void CodeGenData::initStateCondList( int snum, ulong length )
 267 {
 268         /* Could preallocate these, as we could with transitions. */
 269 }
 270
 271 void CodeGenData::addStateCond( int snum, Key lowKey, Key highKey, long condNum )
 272 {
 273         RedStateAp *curState = allStates + snum;
 274
 275         /* Create the new state condition. */
 276         StateCond *stateCond = new StateCond;
 277         stateCond->lowKey = lowKey;
 278         stateCond->highKey = highKey;
 279
 280         /* Assign it a cond space. */
 281         CondSpace *condSpace = allCondSpaces + condNum;
 282         stateCond->condSpace = condSpace;
 283
 284         curState->stateCondList.append( stateCond );
 285 }
 286
 287
 288 /* Generate the codegen depending on the command line options given. */
 289 void CodeGenData::makeCodeGen()
 290 {
 291         switch ( hostLangType ) {
 292         case CCode:
 293                 switch ( codeStyle ) {
 294                 case GenTables:
 295                         codeGen = new CTabCodeGen(out);
 296                         break;
 297                 case GenFTables:
 298                         codeGen = new CFTabCodeGen(out);
 299                         break;
 300                 case GenFlat:
 301                         codeGen = new CFlatCodeGen(out);
 302                         break;
 303                 case GenFFlat:
 304                         codeGen = new CFFlatCodeGen(out);
 305                         break;
 306                 case GenGoto:
 307                         codeGen = new CGotoCodeGen(out);
 308                         break;
 309                 case GenFGoto:
 310                         codeGen = new CFGotoCodeGen(out);
 311                         break;
 312                 case GenIpGoto:
 313                         codeGen = new CIpGotoCodeGen(out);
 314                         break;
 315                 case GenSplit:
 316                         codeGen = new CSplitCodeGen(out);
 317                         break;
 318                 }
 319                 break;
 320
 321         case DCode:
 322                 switch ( codeStyle ) {
 323                 case GenTables:
 324                         codeGen = new DTabCodeGen(out);
 325                         break;
 326                 case GenFTables:
 327                         codeGen = new DFTabCodeGen(out);
 328                         break;
 329                 case GenFlat:
 330                         codeGen = new DFlatCodeGen(out);
 331                         break;
 332                 case GenFFlat:
 333                         codeGen = new DFFlatCodeGen(out);
 334                         break;
 335                 case GenGoto:
 336                         codeGen = new DGotoCodeGen(out);
 337                         break;
 338                 case GenFGoto:
 339                         codeGen = new DFGotoCodeGen(out);
 340                         break;
 341                 case GenIpGoto:
 342                         codeGen = new DIpGotoCodeGen(out);
 343                         break;
 344                 case GenSplit:
 345                         codeGen = new DSplitCodeGen(out);
 346                         break;
 347                 }
 348                 break;
 349
 350         case JavaCode:
 351                 switch ( codeStyle ) {
 352                 case GenTables:
 353                         codeGen = new JavaTabCodeGen(out);
 354                         break;
 355                 default:
 356                         assert(false);
 357                         break;
 358                 }
 359                 break;
 360         }
 361
 362         codeGen->cgd = this;
 363 }
 364
 365 CondSpace *CodeGenData::findCondSpace( Key lowKey, Key highKey )
 366 {
 367         for ( CondSpaceList::Iter cs = condSpaceList; cs.lte(); cs++ ) {
 368                 Key csHighKey = cs->baseKey;
 369                 csHighKey += keyOps->alphSize() * (1 << cs->condSet.length());
 370
 371                 if ( lowKey >= cs->baseKey && highKey <= csHighKey )
 372                         return cs;
 373         }
 374         return 0;
 375 }
 376
 377 Condition *CodeGenData::findCondition( Key key )
 378 {
 379         for ( ConditionList::Iter cond = conditionList; cond.lte(); cond++ ) {
 380                 Key upperKey = cond->baseKey + (1 << cond->condSet.length());
 381                 if ( cond->baseKey <= key && key <= upperKey )
 382                         return cond;
 383         }
 384         return 0;
 385 }
 386
 387 Key CodeGenData::findMaxKey()
 388 {
 389         Key maxKey = keyOps->maxKey;
 390         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 391                 assert( st->outSingle.length() == 0 );
 392                 assert( st->defTrans == 0 );
 393
 394                 long rangeLen = st->outRange.length();
 395                 if ( rangeLen > 0 ) {
 396                         Key highKey = st->outRange[rangeLen-1].highKey;
 397                         if ( highKey > maxKey )
 398                                 maxKey = highKey;
 399                 }
 400         }
 401         return maxKey;
 402 }
 403
 404 void CodeGenData::findFinalActionRefs()
 405 {
 406         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 407                 /* Rerence count out of single transitions. */
 408                 for ( RedTransList::Iter rtel = st->outSingle; rtel.lte(); rtel++ ) {
 409                         if ( rtel->value->action != 0 ) {
 410                                 rtel->value->action->numTransRefs += 1;
 411                                 for ( ActionTable::Iter item = rtel->value->action->key; item.lte(); item++ )
 412                                         item->value->numTransRefs += 1;
 413                         }
 414                 }
 415
 416                 /* Reference count out of range transitions. */
 417                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 418                         if ( rtel->value->action != 0 ) {
 419                                 rtel->value->action->numTransRefs += 1;
 420                                 for ( ActionTable::Iter item = rtel->value->action->key; item.lte(); item++ )
 421                                         item->value->numTransRefs += 1;
 422                         }
 423                 }
 424
 425                 /* Reference count default transition. */
 426                 if ( st->defTrans != 0 && st->defTrans->action != 0 ) {
 427                         st->defTrans->action->numTransRefs += 1;
 428                         for ( ActionTable::Iter item = st->defTrans->action->key; item.lte(); item++ )
 429                                 item->value->numTransRefs += 1;
 430                 }
 431
 432                 /* Reference count to state actions. */
 433                 if ( st->toStateAction != 0 ) {
 434                         st->toStateAction->numToStateRefs += 1;
 435                         for ( ActionTable::Iter item = st->toStateAction->key; item.lte(); item++ )
 436                                 item->value->numToStateRefs += 1;
 437                 }
 438
 439                 /* Reference count from state actions. */
 440                 if ( st->fromStateAction != 0 ) {
 441                         st->fromStateAction->numFromStateRefs += 1;
 442                         for ( ActionTable::Iter item = st->fromStateAction->key; item.lte(); item++ )
 443                                 item->value->numFromStateRefs += 1;
 444                 }
 445
 446                 /* Reference count EOF actions. */
 447                 if ( st->eofAction != 0 ) {
 448                         st->eofAction->numEofRefs += 1;
 449                         for ( ActionTable::Iter item = st->eofAction->key; item.lte(); item++ )
 450                                 item->value->numEofRefs += 1;
 451                 }
 452         }
 453 }
 454
 455 void CodeGenData::analyzeAction( Action *act, InlineList *inlineList )
 456 {
 457         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
 458                 /* Only consider actions that are referenced. */
 459                 if ( act->numRefs() > 0 ) {
 460                         if ( item->type == InlineItem::Goto || item->type == InlineItem::GotoExpr )
 461                                 codeGen->bAnyActionGotos = true;
 462                         else if ( item->type == InlineItem::Call || item->type == InlineItem::CallExpr )
 463                                 codeGen->bAnyActionCalls = true;
 464                         else if ( item->type == InlineItem::Ret )
 465                                 codeGen->bAnyActionRets = true;
 466                 }
 467
 468                 /* Check for various things in regular actions. */
 469                 if ( act->numTransRefs > 0 || act->numToStateRefs > 0 || act->numFromStateRefs > 0 ) {
 470                         /* Any returns in regular actions? */
 471                         if ( item->type == InlineItem::Ret )
 472                                 codeGen->bAnyRegActionRets = true;
 473
 474                         /* Any next statements in the regular actions? */
 475                         if ( item->type == InlineItem::Next || item->type == InlineItem::NextExpr )
 476                                 codeGen->bAnyRegNextStmt = true;
 477
 478                         /* Any by value control in regular actions? */
 479                         if ( item->type == InlineItem::CallExpr || item->type == InlineItem::GotoExpr )
 480                                 codeGen->bAnyRegActionByValControl = true;
 481
 482                         /* Any references to the current state in regular actions? */
 483                         if ( item->type == InlineItem::Curs )
 484                                 codeGen->bAnyRegCurStateRef = true;
 485
 486                         if ( item->type == InlineItem::Break )
 487                                 codeGen->bAnyRegBreak = true;
 488
 489                         if ( item->type == InlineItem::LmSwitch && item->handlesError )
 490                                 codeGen->bAnyLmSwitchError = true;
 491                 }
 492
 493                 if ( item->children != 0 )
 494                         analyzeAction( act, item->children );
 495         }
 496 }
 497
 498 void CodeGenData::analyzeActionList( RedAction *redAct, InlineList *inlineList )
 499 {
 500         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
 501                 /* Any next statements in the action table? */
 502                 if ( item->type == InlineItem::Next || item->type == InlineItem::NextExpr )
 503                         redAct->bAnyNextStmt = true;
 504
 505                 /* Any references to the current state. */
 506                 if ( item->type == InlineItem::Curs )
 507                         redAct->bAnyCurStateRef = true;
 508
 509                 if ( item->type == InlineItem::Break )
 510                         redAct->bAnyBreakStmt = true;
 511
 512                 if ( item->children != 0 )
 513                         analyzeActionList( redAct, item->children );
 514         }
 515 }
 516
 517 /* Assign ids to referenced actions. */
 518 void CodeGenData::assignActionIds()
 519 {
 520         int nextActionId = 0;
 521         for ( ActionList::Iter act = cgd->actionList; act.lte(); act++ ) {
 522                 /* Only ever interested in referenced actions. */
 523                 if ( act->numRefs() > 0 )
 524                         act->actionId = nextActionId++;
 525         }
 526 }
 527
 528 void CodeGenData::setValueLimits()
 529 {
 530         codeGen->maxSingleLen = 0;
 531         codeGen->maxRangeLen = 0;
 532         codeGen->maxKeyOffset = 0;
 533         codeGen->maxIndexOffset = 0;
 534         codeGen->maxActListId = 0;
 535         codeGen->maxActionLoc = 0;
 536         codeGen->maxActArrItem = 0;
 537         codeGen->maxSpan = 0;
 538         codeGen->maxCondSpan = 0;
 539         codeGen->maxFlatIndexOffset = 0;
 540         codeGen->maxCondOffset = 0;
 541         codeGen->maxCondLen = 0;
 542         codeGen->maxCondSpaceId = 0;
 543         codeGen->maxCondIndexOffset = 0;
 544
 545         /* In both of these cases the 0 index is reserved for no value, so the max
 546          * is one more than it would be if they started at 0. */
 547         codeGen->maxIndex = redFsm->transSet.length();
 548         codeGen->maxCond = cgd->condSpaceList.length();
 549
 550         /* The nextStateId - 1 is the last state id assigned. */
 551         codeGen->maxState = redFsm->nextStateId - 1;
 552
 553         for ( CondSpaceList::Iter csi = cgd->condSpaceList; csi.lte(); csi++ ) {
 554                 if ( csi->condSpaceId > codeGen->maxCondSpaceId )
 555                         codeGen->maxCondSpaceId = csi->condSpaceId;
 556         }
 557
 558         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 559                 /* Maximum cond length. */
 560                 if ( st->stateCondList.length() > codeGen->maxCondLen )
 561                         codeGen->maxCondLen = st->stateCondList.length();
 562
 563                 /* Maximum single length. */
 564                 if ( st->outSingle.length() > codeGen->maxSingleLen )
 565                         codeGen->maxSingleLen = st->outSingle.length();
 566
 567                 /* Maximum range length. */
 568                 if ( st->outRange.length() > codeGen->maxRangeLen )
 569                         codeGen->maxRangeLen = st->outRange.length();
 570
 571                 /* The key offset index offset for the state after last is not used, skip it.. */
 572                 if ( ! st.last() ) {
 573                         codeGen->maxCondOffset += st->stateCondList.length();
 574                         codeGen->maxKeyOffset += st->outSingle.length() + st->outRange.length()*2;
 575                         codeGen->maxIndexOffset += st->outSingle.length() + st->outRange.length() + 1;
 576                 }
 577
 578                 /* Max cond span. */
 579                 if ( st->condList != 0 ) {
 580                         unsigned long long span = keyOps->span( st->condLowKey, st->condHighKey );
 581                         if ( span > codeGen->maxCondSpan )
 582                                 codeGen->maxCondSpan = span;
 583                 }
 584
 585                 /* Max key span. */
 586                 if ( st->transList != 0 ) {
 587                         unsigned long long span = keyOps->span( st->lowKey, st->highKey );
 588                         if ( span > codeGen->maxSpan )
 589                                 codeGen->maxSpan = span;
 590                 }
 591
 592                 /* Max cond index offset. */
 593                 if ( ! st.last() ) {
 594                         if ( st->condList != 0 )
 595                                 codeGen->maxCondIndexOffset += keyOps->span( st->condLowKey, st->condHighKey );
 596                 }
 597
 598                 /* Max flat index offset. */
 599                 if ( ! st.last() ) {
 600                         if ( st->transList != 0 )
 601                                 codeGen->maxFlatIndexOffset += keyOps->span( st->lowKey, st->highKey );
 602                         codeGen->maxFlatIndexOffset += 1;
 603                 }
 604         }
 605
 606         for ( ActionTableMap::Iter at = redFsm->actionMap; at.lte(); at++ ) {
 607                 /* Maximum id of action lists. */
 608                 if ( at->actListId+1 > codeGen->maxActListId )
 609                         codeGen->maxActListId = at->actListId+1;
 610
 611                 /* Maximum location of items in action array. */
 612                 if ( at->location+1 > codeGen->maxActionLoc )
 613                         codeGen->maxActionLoc = at->location+1;
 614
 615                 /* Maximum values going into the action array. */
 616                 if ( at->key.length() > codeGen->maxActArrItem )
 617                         codeGen->maxActArrItem = at->key.length();
 618                 for ( ActionTable::Iter item = at->key; item.lte(); item++ ) {
 619                         if ( item->value->actionId > codeGen->maxActArrItem )
 620                                 codeGen->maxActArrItem = item->value->actionId;
 621                 }
 622         }
 623 }
 624
 625
 626
 627 /* Gather various info on the machine. */
 628 void CodeGenData::analyzeMachine()
 629 {
 630         /* Find the true count of action references.  */
 631         findFinalActionRefs();
 632
 633         /* Check if there are any calls in action code. */
 634         for ( ActionList::Iter act = cgd->actionList; act.lte(); act++ ) {
 635                 /* Record the occurrence of various kinds of actions. */
 636                 if ( act->numToStateRefs > 0 )
 637                         codeGen->bAnyToStateActions = true;
 638                 if ( act->numFromStateRefs > 0 )
 639                         codeGen->bAnyFromStateActions = true;
 640                 if ( act->numEofRefs > 0 )
 641                         codeGen->bAnyEofActions = true;
 642                 if ( act->numTransRefs > 0 )
 643                         codeGen->bAnyRegActions = true;
 644
 645                 /* Recurse through the action's parse tree looking for various things. */
 646                 analyzeAction( act, act->inlineList );
 647         }
 648
 649         /* Analyze reduced action lists. */
 650         for ( ActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
 651                 for ( ActionTable::Iter act = redAct->key; act.lte(); act++ )
 652                         analyzeActionList( redAct, act->value->inlineList );
 653         }
 654
 655         /* Find states that have transitions with actions that have next
 656          * statements. */
 657         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 658                 /* Check any actions out of outSinge. */
 659                 for ( RedTransList::Iter rtel = st->outSingle; rtel.lte(); rtel++ ) {
 660                         if ( rtel->value->action != 0 && rtel->value->action->anyCurStateRef() )
 661                                 st->bAnyRegCurStateRef = true;
 662                 }
 663
 664                 /* Check any actions out of outRange. */
 665                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 666                         if ( rtel->value->action != 0 && rtel->value->action->anyCurStateRef() )
 667                                 st->bAnyRegCurStateRef = true;
 668                 }
 669
 670                 /* Check any action out of default. */
 671                 if ( st->defTrans != 0 && st->defTrans->action != 0 &&
 672                                 st->defTrans->action->anyCurStateRef() )
 673                         st->bAnyRegCurStateRef = true;
 674
 675                 if ( st->stateCondList.length() > 0 )
 676                         codeGen->bAnyConditions = true;
 677         }
 678
 679         /* Assign ids to actions that are referenced. */
 680         assignActionIds();
 681
 682         /* Set the maximums of various values used for deciding types. */
 683         setValueLimits();
 684
 685         /* Determine if we should use indicies. */
 686         codeGen->calcIndexSize();
 687 }
 688
 689 /* Generate the code for an fsm. Assumes parseData is set up properly. Called
 690  * by parser code. */
 691 void CodeGenData::prepareMachine()
 692 {
 693         if ( hasBeenPrepared )
 694                 return;
 695         hasBeenPrepared = true;
 696
 697         /* Do this before distributing transitions out to singles and defaults
 698          * makes life easier. */
 699         Key maxKey = findMaxKey();
 700
 701         redFsm->assignActionLocs();
 702
 703         /* Order the states. */
 704         redFsm->depthFirstOrdering();
 705
 706         if ( codeStyle == GenGoto || codeStyle == GenFGoto ||
 707                         codeStyle == GenIpGoto || codeStyle == GenSplit )
 708         {
 709                 /* For goto driven machines we can keep the original depth
 710                  * first ordering because it's ok if the state ids are not
 711                  * sequential. Split the the ids by final state status. */
 712                 redFsm->sortStateIdsByFinal();
 713         }
 714         else {
 715                 /* For table driven machines the location of the state is used to
 716                  * identify it so the states must be sorted by their final ids.
 717                  * Though having a deterministic ordering is important,
 718                  * specifically preserving the depth first ordering is not because
 719                  * states are stored in tables. */
 720                 redFsm->sortStatesByFinal();
 721                 redFsm->sequentialStateIds();
 722         }
 723
 724         /* Find the first final state. This is the final state with the lowest
 725          * id.  */
 726         redFsm->findFirstFinState();
 727
 728         /* Choose default transitions and the single transition. */
 729         redFsm->chooseDefaultSpan();
 730
 731         /* Maybe do flat expand, otherwise choose single. */
 732         if ( codeStyle == GenFlat || codeStyle == GenFFlat )
 733                 redFsm->makeFlat();
 734         else
 735                 redFsm->chooseSingle();
 736
 737         /* If any errors have occured in the input file then don't write anything. */
 738         if ( gblErrorCount > 0 )
 739                 return;
 740
 741         if ( codeStyle == GenSplit )
 742                 redFsm->partitionFsm( numSplitPartitions );
 743
 744         if ( codeStyle == GenIpGoto || codeStyle == GenSplit )
 745                 redFsm->setInTrans();
 746
 747         /* Make a code generator that will output the header/code. */
 748         if ( codeGen == 0 )
 749                 makeCodeGen();
 750         codeGen->redFsm = redFsm;
 751
 752         /* Anlayze Machine will find the final action reference counts, among
 753          * other things. We will use these in reporting the usage
 754          * of fsm directives in action code. */
 755         analyzeMachine();
 756         codeGen->maxKey = maxKey;
 757 }
 758
 759 void CodeGenData::generateGraphviz()
 760 {
 761         /* Do ordering and choose state ids. */
 762         redFsm->depthFirstOrdering();
 763         redFsm->sequentialStateIds();
 764
 765         /* For dot file generation we want to pick default transitions. */
 766         redFsm->chooseDefaultSpan();
 767
 768         /* Make the generator. */
 769         GraphvizDotGen dotGen( fsmName, this, redFsm, out );
 770
 771         /* Write out with it. */
 772         dotGen.writeDotFile();
 773 }
 774
 775 void CodeGenData::generateCode()
 776 {
 777         if ( writeOps & WO_NOEND )
 778                 hasEnd = false;
 779
 780         if ( writeOps & WO_NOERROR )
 781                 writeErr = false;
 782
 783         if ( writeOps & WO_NOPREFIX )
 784                 dataPrefix = false;
 785
 786         if ( writeOps & WO_NOFF )
 787                 writeFirstFinal = false;
 788
 789         if ( writeData || writeInit || writeExec || writeEOF ) {
 790                 prepareMachine();
 791
 792                 /* Force a newline. */
 793                 out << "\n";
 794                 genLineDirective( out );
 795         }
 796
 797
 798         if ( writeExec ) {
 799                 /* Must set labels immediately before writing because we may depend
 800                  * on the noend write option. */
 801                 codeGen->setLabelsNeeded();
 802         }
 803
 804         if ( writeData )
 805                 codeGen->writeOutData();
 806
 807         if ( writeInit )
 808                 codeGen->writeOutInit();
 809
 810         if ( writeExec )
 811                 codeGen->writeOutExec();
 812
 813         if ( writeEOF )
 814                 codeGen->writeOutEOF();
 815 }
 816
 817 void CodeGenData::generate()
 818 {
 819         if ( redFsm != 0 ) {
 820                 if ( outputFormat == OutCode )
 821                         generateCode();
 822                 else if ( outputFormat == OutGraphvizDot && !graphvizDone ) {
 823                         graphvizDone = true;
 824                         generateGraphviz();
 825                 }
 826         }
 827 }
 828
 829 void lineDirective( ostream &out, char *fileName, int line )
 830 {
 831         if ( hostLangType != JavaCode ) {
 832                 /* Write the preprocessor line info for to the input file. */
 833                 out << "#line " << line  << " \"";
 834                 for ( char *pc = fileName; *pc != 0; pc++ ) {
 835                         if ( *pc == '\\' )
 836                                 out << "\\\\";
 837                         else
 838                                 out << *pc;
 839                 }
 840                 out << "\"\n";
 841         }
 842 }
 843
 844 void genLineDirective( ostream &out )
 845 {
 846         assert( outputFormat == OutCode );
 847         std::streambuf *sbuf = out.rdbuf();
 848         output_filter *filter = static_cast<output_filter*>(sbuf);
 849         lineDirective( out, filter->fileName, filter->line + 1 );
 850 }