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;
 296                         break;
 297                 case GenFTables:
 298                         codeGen = new CFTabCodeGen;
 299                         break;
 300                 case GenFlat:
 301                         codeGen = new CFlatCodeGen;
 302                         break;
 303                 case GenFFlat:
 304                         codeGen = new CFFlatCodeGen;
 305                         break;
 306                 case GenGoto:
 307                         codeGen = new CGotoCodeGen;
 308                         break;
 309                 case GenFGoto:
 310                         codeGen = new CFGotoCodeGen;
 311                         break;
 312                 case GenIpGoto:
 313                         codeGen = new CIpGotoCodeGen;
 314                         break;
 315                 case GenSplit:
 316                         codeGen = new CSplitCodeGen;
 317                         break;
 318                 }
 319                 break;
 320
 321         case DCode:
 322                 switch ( codeStyle ) {
 323                 case GenTables:
 324                         codeGen = new DTabCodeGen;
 325                         break;
 326                 case GenFTables:
 327                         codeGen = new DFTabCodeGen;
 328                         break;
 329                 case GenFlat:
 330                         codeGen = new DFlatCodeGen;
 331                         break;
 332                 case GenFFlat:
 333                         codeGen = new DFFlatCodeGen;
 334                         break;
 335                 case GenGoto:
 336                         codeGen = new DGotoCodeGen;
 337                         break;
 338                 case GenFGoto:
 339                         codeGen = new DFGotoCodeGen;
 340                         break;
 341                 case GenIpGoto:
 342                         codeGen = new DIpGotoCodeGen;
 343                         break;
 344                 case GenSplit:
 345                         codeGen = new DSplitCodeGen;
 346                         break;
 347                 }
 348                 break;
 349
 350         case JavaCode:
 351                 switch ( codeStyle ) {
 352                 case GenTables:
 353                         codeGen = new JavaTabCodeGen;
 354                         break;
 355                 default:
 356                         assert(false);
 357                         break;
 358                 }
 359                 break;
 360         }
 361
 362         codeGen->fsmName = fsmName;
 363         codeGen->cgd = this;
 364 }
 365
 366 CondSpace *CodeGenData::findCondSpace( Key lowKey, Key highKey )
 367 {
 368         for ( CondSpaceList::Iter cs = condSpaceList; cs.lte(); cs++ ) {
 369                 Key csHighKey = cs->baseKey;
 370                 csHighKey += keyOps->alphSize() * (1 << cs->condSet.length());
 371
 372                 if ( lowKey >= cs->baseKey && highKey <= csHighKey )
 373                         return cs;
 374         }
 375         return 0;
 376 }
 377
 378 Condition *CodeGenData::findCondition( Key key )
 379 {
 380         for ( ConditionList::Iter cond = conditionList; cond.lte(); cond++ ) {
 381                 Key upperKey = cond->baseKey + (1 << cond->condSet.length());
 382                 if ( cond->baseKey <= key && key <= upperKey )
 383                         return cond;
 384         }
 385         return 0;
 386 }
 387
 388 Key CodeGenData::findMaxKey()
 389 {
 390         Key maxKey = keyOps->maxKey;
 391         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 392                 assert( st->outSingle.length() == 0 );
 393                 assert( st->defTrans == 0 );
 394
 395                 long rangeLen = st->outRange.length();
 396                 if ( rangeLen > 0 ) {
 397                         Key highKey = st->outRange[rangeLen-1].highKey;
 398                         if ( highKey > maxKey )
 399                                 maxKey = highKey;
 400                 }
 401         }
 402         return maxKey;
 403 }
 404
 405 /* Generate the code for an fsm. Assumes parseData is set up properly. Called
 406  * by parser code. */
 407 void CodeGenData::prepareMachine()
 408 {
 409         if ( hasBeenPrepared )
 410                 return;
 411         hasBeenPrepared = true;
 412
 413         /* Do this before distributing transitions out to singles and defaults
 414          * makes life easier. */
 415         Key maxKey = findMaxKey();
 416
 417         redFsm->assignActionLocs();
 418
 419         /* Order the states. */
 420         redFsm->depthFirstOrdering();
 421
 422         if ( codeStyle == GenGoto || codeStyle == GenFGoto ||
 423                         codeStyle == GenIpGoto || codeStyle == GenSplit )
 424         {
 425                 /* For goto driven machines we can keep the original depth
 426                  * first ordering because it's ok if the state ids are not
 427                  * sequential. Split the the ids by final state status. */
 428                 redFsm->sortStateIdsByFinal();
 429         }
 430         else {
 431                 /* For table driven machines the location of the state is used to
 432                  * identify it so the states must be sorted by their final ids.
 433                  * Though having a deterministic ordering is important,
 434                  * specifically preserving the depth first ordering is not because
 435                  * states are stored in tables. */
 436                 redFsm->sortStatesByFinal();
 437                 redFsm->sequentialStateIds();
 438         }
 439
 440         /* Find the first final state. This is the final state with the lowest
 441          * id.  */
 442         redFsm->findFirstFinState();
 443
 444         /* Choose default transitions and the single transition. */
 445         redFsm->chooseDefaultSpan();
 446
 447         /* Maybe do flat expand, otherwise choose single. */
 448         if ( codeStyle == GenFlat || codeStyle == GenFFlat )
 449                 redFsm->makeFlat();
 450         else
 451                 redFsm->chooseSingle();
 452
 453         /* If any errors have occured in the input file then don't write anything. */
 454         if ( gblErrorCount > 0 )
 455                 return;
 456
 457         if ( codeStyle == GenSplit )
 458                 redFsm->partitionFsm( numSplitPartitions );
 459
 460         if ( codeStyle == GenIpGoto || codeStyle == GenSplit )
 461                 redFsm->setInTrans();
 462
 463         /* Make a code generator that will output the header/code. */
 464         if ( codeGen == 0 )
 465                 makeCodeGen();
 466         codeGen->redFsm = redFsm;
 467
 468         /* Anlayze Machine will find the final action reference counts, among
 469          * other things. We will use these in reporting the usage
 470          * of fsm directives in action code. */
 471         codeGen->analyzeMachine();
 472         codeGen->maxKey = maxKey;
 473 }
 474
 475 void CodeGenData::generateGraphviz()
 476 {
 477         /* Do ordering and choose state ids. */
 478         redFsm->depthFirstOrdering();
 479         redFsm->sequentialStateIds();
 480
 481         /* For dot file generation we want to pick default transitions. */
 482         redFsm->chooseDefaultSpan();
 483
 484         /* Make the generator. */
 485         GraphvizDotGen dotGen( fsmName, this, redFsm, *outStream );
 486
 487         /* Write out with it. */
 488         dotGen.writeDotFile();
 489 }
 490
 491 void CodeGenData::generateCode()
 492 {
 493         if ( writeOps & WO_NOEND )
 494                 hasEnd = false;
 495
 496         if ( writeOps & WO_NOERROR )
 497                 writeErr = false;
 498
 499         if ( writeOps & WO_NOPREFIX )
 500                 dataPrefix = false;
 501
 502         if ( writeOps & WO_NOFF )
 503                 writeFirstFinal = false;
 504
 505         if ( writeData || writeInit || writeExec || writeEOF ) {
 506                 prepareMachine();
 507
 508                 /* Force a newline. */
 509                 *outStream << "\n";
 510                 genLineDirective( *outStream );
 511         }
 512
 513
 514         if ( writeExec ) {
 515                 /* Must set labels immediately before writing because we may depend
 516                  * on the noend write option. */
 517                 codeGen->setLabelsNeeded();
 518         }
 519
 520         if ( writeData )
 521                 codeGen->writeOutData();
 522
 523         if ( writeInit )
 524                 codeGen->writeOutInit();
 525
 526         if ( writeExec )
 527                 codeGen->writeOutExec();
 528
 529         if ( writeEOF )
 530                 codeGen->writeOutEOF();
 531 }
 532
 533 void CodeGenData::generate()
 534 {
 535         if ( redFsm != 0 ) {
 536                 if ( outputFormat == OutCode )
 537                         generateCode();
 538                 else if ( outputFormat == OutGraphvizDot && !graphvizDone ) {
 539                         graphvizDone = true;
 540                         generateGraphviz();
 541                 }
 542         }
 543 }
 544
 545 void lineDirective( ostream &out, char *fileName, int line )
 546 {
 547         if ( hostLangType != JavaCode ) {
 548                 /* Write the preprocessor line info for to the input file. */
 549                 out << "#line " << line  << " \"";
 550                 for ( char *pc = fileName; *pc != 0; pc++ ) {
 551                         if ( *pc == '\\' )
 552                                 out << "\\\\";
 553                         else
 554                                 out << *pc;
 555                 }
 556                 out << "\"\n";
 557         }
 558 }
 559
 560 void genLineDirective( ostream &out )
 561 {
 562         lineDirective( out, outputFileName, outFilter->line + 1 );
 563 }