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