rlcodegen/fsmcodegen.cpp

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