rlgen-cd/fsmcodegen.cpp

   1 /*
   2  *  Copyright 2001-2006 Adrian Thurston <thurston@cs.queensu.ca>
   3  *            2004 Erich Ocean <eric.ocean@ampede.com>
   4  *            2005 Alan West <alan@alanz.com>
   5  */
   6
   7 /*  This file is part of Ragel.
   8  *
   9  *  Ragel is free software; you can redistribute it and/or modify
  10  *  it under the terms of the GNU General Public License as published by
  11  *  the Free Software Foundation; either version 2 of the License, or
  12  *  (at your option) any later version.
  13  *
  14  *  Ragel is distributed in the hope that it will be useful,
  15  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *  GNU General Public License for more details.
  18  *
  19  *  You should have received a copy of the GNU General Public License
  20  *  along with Ragel; if not, write to the Free Software
  21  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  22  */
  23
  24 #include "rlgen-cd.h"
  25 #include "fsmcodegen.h"
  26 #include "redfsm.h"
  27 #include "gendata.h"
  28 #include <sstream>
  29 #include <string>
  30 #include <assert.h>
  31
  32
  33 using std::ostream;
  34 using std::ostringstream;
  35 using std::string;
  36 using std::cerr;
  37 using std::endl;
  38
  39 void lineDirective( ostream &out, char *fileName, int line )
  40 {
  41         if ( noLineDirectives )
  42                 out << "/* ";
  43
  44         /* Write the preprocessor line info for to the input file. */
  45         out << "#line " << line  << " \"";
  46         for ( char *pc = fileName; *pc != 0; pc++ ) {
  47                 if ( *pc == '\\' )
  48                         out << "\\\\";
  49                 else
  50                         out << *pc;
  51         }
  52         out << '"';
  53
  54         if ( noLineDirectives )
  55                 out << " */";
  56
  57         out << '\n';
  58 }
  59
  60 void genLineDirective( ostream &out )
  61 {
  62         std::streambuf *sbuf = out.rdbuf();
  63         output_filter *filter = static_cast<output_filter*>(sbuf);
  64         lineDirective( out, filter->fileName, filter->line + 1 );
  65 }
  66
  67
  68 /* Init code gen with in parameters. */
  69 FsmCodeGen::FsmCodeGen( ostream &out )
  70 :
  71         CodeGenData(out)
  72 {
  73 }
  74
  75 unsigned int FsmCodeGen::arrayTypeSize( unsigned long maxVal )
  76 {
  77         long long maxValLL = (long long) maxVal;
  78         HostType *arrayType = keyOps->typeSubsumes( maxValLL );
  79         assert( arrayType != 0 );
  80         return arrayType->size;
  81 }
  82
  83 string FsmCodeGen::ARRAY_TYPE( unsigned long maxVal )
  84 {
  85         long long maxValLL = (long long) maxVal;
  86         HostType *arrayType = keyOps->typeSubsumes( maxValLL );
  87         assert( arrayType != 0 );
  88
  89         string ret = arrayType->data1;
  90         if ( arrayType->data2 != 0 ) {
  91                 ret += " ";
  92                 ret += arrayType->data2;
  93         }
  94         return ret;
  95 }
  96
  97
  98 /* Write out the fsm name. */
  99 string FsmCodeGen::FSM_NAME()
 100 {
 101         return fsmName;
 102 }
 103
 104 /* Emit the offset of the start state as a decimal integer. */
 105 string FsmCodeGen::START_STATE_ID()
 106 {
 107         ostringstream ret;
 108         ret << redFsm->startState->id;
 109         return ret.str();
 110 };
 111
 112 /* Write out the array of actions. */
 113 std::ostream &FsmCodeGen::ACTIONS_ARRAY()
 114 {
 115         out << "\t0, ";
 116         int totalActions = 1;
 117         for ( ActionTableMap::Iter act = redFsm->actionMap; act.lte(); act++ ) {
 118                 /* Write out the length, which will never be the last character. */
 119                 out << act->key.length() << ", ";
 120                 /* Put in a line break every 8 */
 121                 if ( totalActions++ % 8 == 7 )
 122                         out << "\n\t";
 123
 124                 for ( ActionTable::Iter item = act->key; item.lte(); item++ ) {
 125                         out << item->value->actionId;
 126                         if ( ! (act.last() && item.last()) )
 127                                 out << ", ";
 128
 129                         /* Put in a line break every 8 */
 130                         if ( totalActions++ % 8 == 7 )
 131                                 out << "\n\t";
 132                 }
 133         }
 134         out << "\n";
 135         return out;
 136 }
 137
 138
 139 string FsmCodeGen::CS()
 140 {
 141         ostringstream ret;
 142         if ( curStateExpr != 0 ) {
 143                 /* Emit the user supplied method of retrieving the key. */
 144                 ret << "(";
 145                 INLINE_LIST( ret, curStateExpr, 0, false );
 146                 ret << ")";
 147         }
 148         else {
 149                 /* Expression for retrieving the key, use simple dereference. */
 150                 ret << ACCESS() << "cs";
 151         }
 152         return ret.str();
 153 }
 154
 155 string FsmCodeGen::ACCESS()
 156 {
 157         ostringstream ret;
 158         if ( accessExpr != 0 )
 159                 INLINE_LIST( ret, accessExpr, 0, false );
 160         return ret.str();
 161 }
 162
 163 string FsmCodeGen::GET_WIDE_KEY()
 164 {
 165         if ( redFsm->anyConditions() )
 166                 return "_widec";
 167         else
 168                 return GET_KEY();
 169 }
 170
 171 string FsmCodeGen::GET_WIDE_KEY( RedStateAp *state )
 172 {
 173         if ( state->stateCondList.length() > 0 )
 174                 return "_widec";
 175         else
 176                 return GET_KEY();
 177 }
 178
 179 string FsmCodeGen::GET_KEY()
 180 {
 181         ostringstream ret;
 182         if ( getKeyExpr != 0 ) {
 183                 /* Emit the user supplied method of retrieving the key. */
 184                 ret << "(";
 185                 INLINE_LIST( ret, getKeyExpr, 0, false );
 186                 ret << ")";
 187         }
 188         else {
 189                 /* Expression for retrieving the key, use simple dereference. */
 190                 ret << "(*" << P() << ")";
 191         }
 192         return ret.str();
 193 }
 194
 195 /* Write out level number of tabs. Makes the nested binary search nice
 196  * looking. */
 197 string FsmCodeGen::TABS( int level )
 198 {
 199         string result;
 200         while ( level-- > 0 )
 201                 result += "\t";
 202         return result;
 203 }
 204
 205 /* Write out a key from the fsm code gen. Depends on wether or not the key is
 206  * signed. */
 207 string FsmCodeGen::KEY( Key key )
 208 {
 209         ostringstream ret;
 210         if ( keyOps->isSigned || !hostLang->explicitUnsigned )
 211                 ret << key.getVal();
 212         else
 213                 ret << (unsigned long) key.getVal() << 'u';
 214         return ret.str();
 215 }
 216
 217 void FsmCodeGen::EXEC( ostream &ret, InlineItem *item, int targState, int inFinish )
 218 {
 219         /* The parser gives fexec two children. The double brackets are for D
 220          * code. If the inline list is a single word it will get interpreted as a
 221          * C-style cast by the D compiler. */
 222         ret << "{" << P() << " = ((";
 223         INLINE_LIST( ret, item->children, targState, inFinish );
 224         ret << "))-1;}";
 225 }
 226
 227 void FsmCodeGen::EXECTE( ostream &ret, InlineItem *item, int targState, int inFinish )
 228 {
 229         /* Tokend version of exec. */
 230
 231         /* The parser gives fexec two children. The double brackets are for D
 232          * code. If the inline list is a single word it will get interpreted as a
 233          * C-style cast by the D compiler. */
 234         ret << "{" << TOKEND() << " = ((";
 235         INLINE_LIST( ret, item->children, targState, inFinish );
 236         ret << "));}";
 237 }
 238
 239
 240 void FsmCodeGen::LM_SWITCH( ostream &ret, InlineItem *item,
 241                 int targState, int inFinish )
 242 {
 243         ret <<
 244                 "       switch( " << ACT() << " ) {\n";
 245
 246         /* If the switch handles error then we also forced the error state. It
 247          * will exist. */
 248         if ( item->handlesError ) {
 249                 ret << "        case 0: " << TOKEND() << " = " << TOKSTART() << "; ";
 250                 GOTO( ret, redFsm->errState->id, inFinish );
 251                 ret << "\n";
 252         }
 253
 254         for ( InlineList::Iter lma = *item->children; lma.lte(); lma++ ) {
 255                 /* Write the case label, the action and the case break. */
 256                 ret << "        case " << lma->lmId << ":\n";
 257
 258                 /* Write the block and close it off. */
 259                 ret << "        {";
 260                 INLINE_LIST( ret, lma->children, targState, inFinish );
 261                 ret << "}\n";
 262
 263                 ret << "        break;\n";
 264         }
 265         /* Default required for D code. */
 266         ret <<
 267                 "       default: break;\n"
 268                 "       }\n"
 269                 "\t";
 270 }
 271
 272 void FsmCodeGen::SET_ACT( ostream &ret, InlineItem *item )
 273 {
 274         ret << ACT() << " = " << item->lmId << ";";
 275 }
 276
 277 void FsmCodeGen::SET_TOKEND( ostream &ret, InlineItem *item )
 278 {
 279         /* The tokend action sets tokend. */
 280         ret << TOKEND() << " = " << P();
 281         if ( item->offset != 0 )
 282                 out << "+" << item->offset;
 283         out << ";";
 284 }
 285
 286 void FsmCodeGen::GET_TOKEND( ostream &ret, InlineItem *item )
 287 {
 288         ret << TOKEND();
 289 }
 290
 291 void FsmCodeGen::INIT_TOKSTART( ostream &ret, InlineItem *item )
 292 {
 293         ret << TOKSTART() << " = " << NULL_ITEM() << ";";
 294 }
 295
 296 void FsmCodeGen::INIT_ACT( ostream &ret, InlineItem *item )
 297 {
 298         ret << ACT() << " = 0;";
 299 }
 300
 301 void FsmCodeGen::SET_TOKSTART( ostream &ret, InlineItem *item )
 302 {
 303         ret << TOKSTART() << " = " << P() << ";";
 304 }
 305
 306 void FsmCodeGen::SUB_ACTION( ostream &ret, InlineItem *item,
 307                 int targState, bool inFinish )
 308 {
 309         if ( item->children->length() > 0 ) {
 310                 /* Write the block and close it off. */
 311                 ret << "{";
 312                 INLINE_LIST( ret, item->children, targState, inFinish );
 313                 ret << "}";
 314         }
 315 }
 316
 317
 318 /* Write out an inline tree structure. Walks the list and possibly calls out
 319  * to virtual functions than handle language specific items in the tree. */
 320 void FsmCodeGen::INLINE_LIST( ostream &ret, InlineList *inlineList,
 321                 int targState, bool inFinish )
 322 {
 323         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
 324                 switch ( item->type ) {
 325                 case InlineItem::Text:
 326                         ret << item->data;
 327                         break;
 328                 case InlineItem::Goto:
 329                         GOTO( ret, item->targState->id, inFinish );
 330                         break;
 331                 case InlineItem::Call:
 332                         CALL( ret, item->targState->id, targState, inFinish );
 333                         break;
 334                 case InlineItem::Next:
 335                         NEXT( ret, item->targState->id, inFinish );
 336                         break;
 337                 case InlineItem::Ret:
 338                         RET( ret, inFinish );
 339                         break;
 340                 case InlineItem::PChar:
 341                         ret << P();
 342                         break;
 343                 case InlineItem::Char:
 344                         ret << GET_KEY();
 345                         break;
 346                 case InlineItem::Hold:
 347                         ret << P() << "--;";
 348                         break;
 349                 case InlineItem::Exec:
 350                         EXEC( ret, item, targState, inFinish );
 351                         break;
 352                 case InlineItem::HoldTE:
 353                         ret << TOKEND() << "--;";
 354                         break;
 355                 case InlineItem::ExecTE:
 356                         EXECTE( ret, item, targState, inFinish );
 357                         break;
 358                 case InlineItem::Curs:
 359                         CURS( ret, inFinish );
 360                         break;
 361                 case InlineItem::Targs:
 362                         TARGS( ret, inFinish, targState );
 363                         break;
 364                 case InlineItem::Entry:
 365                         ret << item->targState->id;
 366                         break;
 367                 case InlineItem::GotoExpr:
 368                         GOTO_EXPR( ret, item, inFinish );
 369                         break;
 370                 case InlineItem::CallExpr:
 371                         CALL_EXPR( ret, item, targState, inFinish );
 372                         break;
 373                 case InlineItem::NextExpr:
 374                         NEXT_EXPR( ret, item, inFinish );
 375                         break;
 376                 case InlineItem::LmSwitch:
 377                         LM_SWITCH( ret, item, targState, inFinish );
 378                         break;
 379                 case InlineItem::LmSetActId:
 380                         SET_ACT( ret, item );
 381                         break;
 382                 case InlineItem::LmSetTokEnd:
 383                         SET_TOKEND( ret, item );
 384                         break;
 385                 case InlineItem::LmGetTokEnd:
 386                         GET_TOKEND( ret, item );
 387                         break;
 388                 case InlineItem::LmInitTokStart:
 389                         INIT_TOKSTART( ret, item );
 390                         break;
 391                 case InlineItem::LmInitAct:
 392                         INIT_ACT( ret, item );
 393                         break;
 394                 case InlineItem::LmSetTokStart:
 395                         SET_TOKSTART( ret, item );
 396                         break;
 397                 case InlineItem::SubAction:
 398                         SUB_ACTION( ret, item, targState, inFinish );
 399                         break;
 400                 case InlineItem::Break:
 401                         BREAK( ret, targState );
 402                         break;
 403                 }
 404         }
 405 }
 406 /* Write out paths in line directives. Escapes any special characters. */
 407 string FsmCodeGen::LDIR_PATH( char *path )
 408 {
 409         ostringstream ret;
 410         for ( char *pc = path; *pc != 0; pc++ ) {
 411                 if ( *pc == '\\' )
 412                         ret << "\\\\";
 413                 else
 414                         ret << *pc;
 415         }
 416         return ret.str();
 417 }
 418
 419 void FsmCodeGen::ACTION( ostream &ret, Action *action, int targState, bool inFinish )
 420 {
 421         /* Write the preprocessor line info for going into the source file. */
 422         lineDirective( ret, sourceFileName, action->loc.line );
 423
 424         /* Write the block and close it off. */
 425         ret << "\t{";
 426         INLINE_LIST( ret, action->inlineList, targState, inFinish );
 427         ret << "}\n";
 428 }
 429
 430 void FsmCodeGen::CONDITION( ostream &ret, Action *condition )
 431 {
 432         ret << "\n";
 433         lineDirective( ret, sourceFileName, condition->loc.line );
 434         INLINE_LIST( ret, condition->inlineList, 0, false );
 435 }
 436
 437 string FsmCodeGen::ERROR_STATE()
 438 {
 439         ostringstream ret;
 440         if ( redFsm->errState != 0 )
 441                 ret << redFsm->errState->id;
 442         else
 443                 ret << "-1";
 444         return ret.str();
 445 }
 446
 447 string FsmCodeGen::FIRST_FINAL_STATE()
 448 {
 449         ostringstream ret;
 450         if ( redFsm->firstFinState != 0 )
 451                 ret << redFsm->firstFinState->id;
 452         else
 453                 ret << redFsm->nextStateId;
 454         return ret.str();
 455 }
 456
 457 void FsmCodeGen::writeInit()
 458 {
 459         out << "        {\n";
 460
 461         if ( redFsm->startState != 0 )
 462                 out << "\t" << CS() << " = " << START() << ";\n";
 463
 464         /* If there are any calls, then the stack top needs initialization. */
 465         if ( redFsm->anyActionCalls() || redFsm->anyActionRets() )
 466                 out << "\t" << TOP() << " = 0;\n";
 467
 468         if ( hasLongestMatch ) {
 469                 out <<
 470                         "       " << TOKSTART() << " = " << NULL_ITEM() << ";\n"
 471                         "       " << TOKEND() << " = " << NULL_ITEM() << ";\n"
 472                         "       " << ACT() << " = 0;\n";
 473         }
 474         out << "        }\n";
 475 }
 476
 477 string FsmCodeGen::DATA_PREFIX()
 478 {
 479         if ( dataPrefix )
 480                 return FSM_NAME() + "_";
 481         return "";
 482 }
 483
 484 /* Emit the alphabet data type. */
 485 string FsmCodeGen::ALPH_TYPE()
 486 {
 487         string ret = keyOps->alphType->data1;
 488         if ( keyOps->alphType->data2 != 0 ) {
 489                 ret += " ";
 490                 ret += + keyOps->alphType->data2;
 491         }
 492         return ret;
 493 }
 494
 495 /* Emit the alphabet data type. */
 496 string FsmCodeGen::WIDE_ALPH_TYPE()
 497 {
 498         string ret;
 499         if ( redFsm->maxKey <= keyOps->maxKey )
 500                 ret = ALPH_TYPE();
 501         else {
 502                 long long maxKeyVal = redFsm->maxKey.getLongLong();
 503                 HostType *wideType = keyOps->typeSubsumes( keyOps->isSigned, maxKeyVal );
 504                 assert( wideType != 0 );
 505
 506                 ret = wideType->data1;
 507                 if ( wideType->data2 != 0 ) {
 508                         ret += " ";
 509                         ret += wideType->data2;
 510                 }
 511         }
 512         return ret;
 513 }
 514
 515 void FsmCodeGen::STATE_IDS()
 516 {
 517         if ( redFsm->startState != 0 )
 518                 STATIC_VAR( "int", START() ) << " = " << START_STATE_ID() << ";\n";
 519
 520         if ( writeFirstFinal )
 521                 STATIC_VAR( "int" , FIRST_FINAL() ) << " = " << FIRST_FINAL_STATE() << ";\n";
 522
 523         if ( writeErr )
 524                 STATIC_VAR( "int", ERROR() ) << " = " << ERROR_STATE() << ";\n";
 525
 526         out << "\n";
 527
 528         if ( entryPointNames.length() > 0 ) {
 529                 for ( EntryNameVect::Iter en = entryPointNames; en.lte(); en++ ) {
 530                         STATIC_VAR( "int", DATA_PREFIX() + "en_" + *en ) <<
 531                                         " = " << entryPointIds[en.pos()] << ";\n";
 532                 }
 533                 out << "\n";
 534         }
 535 }
 536
 537 void FsmCodeGen::writeExports()
 538 {
 539         if ( exportList.length() > 0 ) {
 540                 for ( ExportList::Iter ex = exportList; ex.lte(); ex++ ) {
 541                         out << "#define " << DATA_PREFIX() << "ex_" << ex->name << " " <<
 542                                         KEY(ex->key) << "\n";
 543                 }
 544                 out << "\n";
 545         }
 546 }
 547
 548
 549 /*
 550  * Language specific, but style independent code generators functions.
 551  */
 552
 553 string CCodeGen::PTR_CONST()
 554 {
 555         return "const ";
 556 }
 557
 558 std::ostream &CCodeGen::OPEN_ARRAY( string type, string name )
 559 {
 560         out << "static const " << type << " " << name << "[] = {\n";
 561         return out;
 562 }
 563
 564 std::ostream &CCodeGen::CLOSE_ARRAY()
 565 {
 566         return out << "};\n";
 567 }
 568
 569 std::ostream &CCodeGen::STATIC_VAR( string type, string name )
 570 {
 571         out << "static const " << type << " " << name;
 572         return out;
 573 }
 574
 575 string CCodeGen::UINT( )
 576 {
 577         return "unsigned int";
 578 }
 579
 580 string CCodeGen::ARR_OFF( string ptr, string offset )
 581 {
 582         return ptr + " + " + offset;
 583 }
 584
 585 string CCodeGen::CAST( string type )
 586 {
 587         return "(" + type + ")";
 588 }
 589
 590 string CCodeGen::NULL_ITEM()
 591 {
 592         return "0";
 593 }
 594
 595 string CCodeGen::POINTER()
 596 {
 597         return " *";
 598 }
 599
 600 std::ostream &CCodeGen::SWITCH_DEFAULT()
 601 {
 602         return out;
 603 }
 604
 605 string CCodeGen::CTRL_FLOW()
 606 {
 607         return "";
 608 }
 609
 610 /*
 611  * D Specific
 612  */
 613
 614 string DCodeGen::NULL_ITEM()
 615 {
 616         return "null";
 617 }
 618
 619 string DCodeGen::POINTER()
 620 {
 621         // multiple items seperated by commas can also be pointer types.
 622         return "* ";
 623 }
 624
 625 string DCodeGen::PTR_CONST()
 626 {
 627         return "";
 628 }
 629
 630 std::ostream &DCodeGen::OPEN_ARRAY( string type, string name )
 631 {
 632         out << "static const " << type << "[] " << name << " = [\n";
 633         return out;
 634 }
 635
 636 std::ostream &DCodeGen::CLOSE_ARRAY()
 637 {
 638         return out << "];\n";
 639 }
 640
 641 std::ostream &DCodeGen::STATIC_VAR( string type, string name )
 642 {
 643         out << "static const " << type << " " << name;
 644         return out;
 645 }
 646
 647 string DCodeGen::ARR_OFF( string ptr, string offset )
 648 {
 649         return "&" + ptr + "[" + offset + "]";
 650 }
 651
 652 string DCodeGen::CAST( string type )
 653 {
 654         return "cast(" + type + ")";
 655 }
 656
 657 string DCodeGen::UINT( )
 658 {
 659         return "uint";
 660 }
 661
 662 std::ostream &DCodeGen::SWITCH_DEFAULT()
 663 {
 664         out << "                default: break;\n";
 665         return out;
 666 }
 667
 668 string DCodeGen::CTRL_FLOW()
 669 {
 670         return "if (true) ";
 671 }
 672
 673 void FsmCodeGen::finishRagelDef()
 674 {
 675         if ( codeStyle == GenGoto || codeStyle == GenFGoto ||
 676                         codeStyle == GenIpGoto || codeStyle == GenSplit )
 677         {
 678                 /* For directly executable machines there is no required state
 679                  * ordering. Choose a depth-first ordering to increase the
 680                  * potential for fall-throughs. */
 681                 redFsm->depthFirstOrdering();
 682         }
 683         else {
 684                 /* The frontend will do this for us, but it may be a good idea to
 685                  * force it if the intermediate file is edited. */
 686                 redFsm->sortByStateId();
 687         }
 688
 689         /* Choose default transitions and the single transition. */
 690         redFsm->chooseDefaultSpan();
 691
 692         /* Maybe do flat expand, otherwise choose single. */
 693         if ( codeStyle == GenFlat || codeStyle == GenFFlat )
 694                 redFsm->makeFlat();
 695         else
 696                 redFsm->chooseSingle();
 697
 698         /* If any errors have occured in the input file then don't write anything. */
 699         if ( gblErrorCount > 0 )
 700                 return;
 701
 702         if ( codeStyle == GenSplit )
 703                 redFsm->partitionFsm( numSplitPartitions );
 704
 705         if ( codeStyle == GenIpGoto || codeStyle == GenSplit )
 706                 redFsm->setInTrans();
 707
 708         /* Anlayze Machine will find the final action reference counts, among
 709          * other things. We will use these in reporting the usage
 710          * of fsm directives in action code. */
 711         analyzeMachine();
 712
 713         /* Determine if we should use indicies. */
 714         calcIndexSize();
 715 }
 716
 717 ostream &FsmCodeGen::source_warning( const InputLoc &loc )
 718 {
 719         cerr << sourceFileName << ":" << loc.line << ":" << loc.col << ": warning: ";
 720         return cerr;
 721 }
 722
 723 ostream &FsmCodeGen::source_error( const InputLoc &loc )
 724 {
 725         gblErrorCount += 1;
 726         assert( sourceFileName != 0 );
 727         cerr << sourceFileName << ":" << loc.line << ":" << loc.col << ": ";
 728         return cerr;
 729 }
 730