ragel/rubyftable.cpp

   1 /*
   2  *  2007 Victor Hugo Borja <vic@rubyforge.org>
   3  *  Copyright 2001-2007 Adrian Thurston <thurston@complang.org>
   4  */
   5
   6 /*  This file is part of Ragel.
   7  *
   8  *  Ragel is free software; you can redistribute it and/or modify
   9  *  it under the terms of the GNU General Public License as published by
  10  *  the Free Software Foundation; either version 2 of the License, or
  11  *  (at your option) any later version.
  12  *
  13  *  Ragel is distributed in the hope that it will be useful,
  14  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *  GNU General Public License for more details.
  17  *
  18  *  You should have received a copy of the GNU General Public License
  19  *  along with Ragel; if not, write to the Free Software
  20  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  21  */
  22
  23 #include <iomanip>
  24 #include <sstream>
  25 #include "redfsm.h"
  26 #include "gendata.h"
  27 #include "ragel.h"
  28 #include "rubyftable.h"
  29
  30 using std::ostream;
  31 using std::ostringstream;
  32 using std::string;
  33 using std::cerr;
  34 using std::endl;
  35
  36 void RubyFTabCodeGen::GOTO( ostream &out, int gotoDest, bool inFinish )
  37 {
  38         out <<
  39                 "       begin\n"
  40                 "               " << vCS() << " = " << gotoDest << "\n"
  41                 "               _goto_level = _again\n"
  42                 "               next\n"
  43                 "       end\n";
  44 }
  45
  46 void RubyFTabCodeGen::GOTO_EXPR( ostream &out, GenInlineItem *ilItem, bool inFinish )
  47 {
  48         out <<
  49                 "       begin\n"
  50                 "               " << vCS() << " = (";
  51         INLINE_LIST( out, ilItem->children, 0, inFinish );
  52         out << ")\n";
  53         out <<
  54                 "               _goto_level = _again\n"
  55                 "               next\n"
  56                 "       end\n";
  57 }
  58
  59 void RubyFTabCodeGen::CALL( ostream &out, int callDest, int targState, bool inFinish )
  60 {
  61         if ( prePushExpr != 0 ) {
  62                 out << "begin\n";
  63                 INLINE_LIST( out, prePushExpr, 0, false );
  64         }
  65
  66         out <<
  67                 "       begin\n"
  68                 "               " << STACK() << "[" << TOP() << "] = " << vCS() << "\n"
  69                 "               " << TOP() << "+= 1\n"
  70                 "               " << vCS() << " = " << callDest << "\n"
  71                 "               _goto_level = _again\n"
  72                 "               next\n"
  73                 "       end\n";
  74
  75         if ( prePushExpr != 0 )
  76                 out << "end\n";
  77 }
  78
  79 void RubyFTabCodeGen::CALL_EXPR(ostream &out, GenInlineItem *ilItem,
  80                 int targState, bool inFinish )
  81 {
  82         if ( prePushExpr != 0 ) {
  83                 out << "begin\n";
  84                 INLINE_LIST( out, prePushExpr, 0, false );
  85         }
  86
  87         out <<
  88                 "       begin\n"
  89                 "               " << STACK() << "[" << TOP() << "] = " << vCS() << "\n"
  90                 "               " << TOP() << " += 1\n"
  91                 "               " << vCS() << " = (";
  92         INLINE_LIST( out, ilItem->children, targState, inFinish );
  93         out << ")\n";
  94
  95         out <<
  96                 "               _goto_level = _again\n"
  97                 "               next\n"
  98                 "       end\n";
  99
 100         if ( prePushExpr != 0 )
 101                 out << "end\n";
 102 }
 103
 104 void RubyFTabCodeGen::RET( ostream &out, bool inFinish )
 105 {
 106         out <<
 107                 "       begin\n"
 108                 "               " << TOP() << " -= 1\n"
 109                 "               " << vCS() << " = " << STACK() << "[" << TOP() << "]\n";
 110
 111         if ( postPopExpr != 0 ) {
 112                 out << "begin\n";
 113                 INLINE_LIST( out, postPopExpr, 0, false );
 114                 out << "end\n";
 115         }
 116
 117         out <<
 118                 "               _goto_level = _again\n"
 119                 "               next\n"
 120                 "       end\n";
 121 }
 122
 123 void RubyFTabCodeGen::BREAK( ostream &out, int targState )
 124 {
 125         out <<
 126                 "       begin\n"
 127                 "               " << P() << " += 1\n"
 128                 "               _goto_level = _out\n"
 129                 "               next\n"
 130                 "       end\n";
 131 }
 132
 133
 134 std::ostream &RubyFTabCodeGen::TO_STATE_ACTION_SWITCH()
 135 {
 136         /* Loop the actions. */
 137         for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
 138                 if ( redAct->numToStateRefs > 0 ) {
 139                         /* Write the entry label. */
 140                         out << "\twhen " << redAct->actListId+1 << " then\n";
 141
 142                         /* Write each action in the list of action items. */
 143                         for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
 144                                 ACTION( out, item->value, 0, false );
 145
 146                 }
 147         }
 148
 149         genLineDirective( out );
 150         return out;
 151 }
 152
 153 /* Write out the function switch. This switch is keyed on the values
 154  * of the func index. */
 155 std::ostream &RubyFTabCodeGen::FROM_STATE_ACTION_SWITCH()
 156 {
 157         /* Loop the actions. */
 158         for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
 159                 if ( redAct->numFromStateRefs > 0 ) {
 160                         /* Write the entry label. */
 161                         out << "\twhen " << redAct->actListId+1 << " then\n";
 162
 163                         /* Write each action in the list of action items. */
 164                         for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
 165                                 ACTION( out, item->value, 0, false );
 166
 167                 }
 168         }
 169
 170         genLineDirective( out );
 171         return out;
 172 }
 173
 174 std::ostream &RubyFTabCodeGen::EOF_ACTION_SWITCH()
 175 {
 176         /* Loop the actions. */
 177         for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
 178                 if ( redAct->numEofRefs > 0 ) {
 179                         /* Write the entry label. */
 180                         out << "\twhen " << redAct->actListId+1 << " then\n";
 181
 182                         /* Write each action in the list of action items. */
 183                         for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
 184                                 ACTION( out, item->value, 0, true );
 185
 186                 }
 187         }
 188
 189         genLineDirective( out );
 190         return out;
 191 }
 192
 193 /* Write out the function switch. This switch is keyed on the values
 194  * of the func index. */
 195 std::ostream &RubyFTabCodeGen::ACTION_SWITCH()
 196 {
 197         /* Loop the actions. */
 198         for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
 199                 if ( redAct->numTransRefs > 0 ) {
 200                         /* Write the entry label. */
 201                         out << "\twhen " << redAct->actListId+1 << " then\n";
 202
 203                         /* Write each action in the list of action items. */
 204                         for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
 205                                 ACTION( out, item->value, 0, false );
 206
 207                 }
 208         }
 209
 210         genLineDirective( out );
 211         return out;
 212 }
 213
 214
 215 int RubyFTabCodeGen::TO_STATE_ACTION( RedStateAp *state )
 216 {
 217         int act = 0;
 218         if ( state->toStateAction != 0 )
 219                 act = state->toStateAction->actListId+1;
 220         return act;
 221 }
 222
 223 int RubyFTabCodeGen::FROM_STATE_ACTION( RedStateAp *state )
 224 {
 225         int act = 0;
 226         if ( state->fromStateAction != 0 )
 227                 act = state->fromStateAction->actListId+1;
 228         return act;
 229 }
 230
 231 int RubyFTabCodeGen::EOF_ACTION( RedStateAp *state )
 232 {
 233         int act = 0;
 234         if ( state->eofAction != 0 )
 235                 act = state->eofAction->actListId+1;
 236         return act;
 237 }
 238
 239
 240 /* Write out the function for a transition. */
 241 int RubyFTabCodeGen::TRANS_ACTION( RedTransAp *trans )
 242 {
 243         int action = 0;
 244         if ( trans->action != 0 )
 245                 action = trans->action->actListId+1;
 246         return action;
 247 }
 248
 249 void RubyFTabCodeGen::writeData()
 250 {
 251
 252         if ( redFsm->anyConditions() ) {
 253                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondOffset), CO() );
 254                 COND_OFFSETS();
 255                 CLOSE_ARRAY() <<
 256                 "\n";
 257
 258                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondLen), CL() );
 259                 COND_LENS();
 260                 CLOSE_ARRAY() <<
 261                 "\n";
 262
 263                 OPEN_ARRAY( WIDE_ALPH_TYPE(), CK() );
 264                 COND_KEYS();
 265                 CLOSE_ARRAY() <<
 266                 "\n";
 267
 268                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondSpaceId), C() );
 269                 COND_SPACES();
 270                 CLOSE_ARRAY() <<
 271                 "\n";
 272         }
 273
 274         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxKeyOffset), KO() );
 275         KEY_OFFSETS();
 276         CLOSE_ARRAY() <<
 277         "\n";
 278
 279         OPEN_ARRAY( WIDE_ALPH_TYPE(), K() );
 280         KEYS();
 281         CLOSE_ARRAY() <<
 282         "\n";
 283
 284         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxSingleLen), SL() );
 285         SINGLE_LENS();
 286         CLOSE_ARRAY() <<
 287         "\n";
 288
 289         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxRangeLen), RL() );
 290         RANGE_LENS();
 291         CLOSE_ARRAY() <<
 292         "\n";
 293
 294         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset), IO() );
 295         INDEX_OFFSETS();
 296         CLOSE_ARRAY() <<
 297         "\n";
 298
 299         if ( useIndicies ) {
 300                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex), I() );
 301                 INDICIES();
 302                 CLOSE_ARRAY() <<
 303                 "\n";
 304
 305                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 306                 TRANS_TARGS_WI();
 307                 CLOSE_ARRAY() <<
 308                 "\n";
 309
 310                 if ( redFsm->anyActions() ) {
 311                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActListId), TA() );
 312                         TRANS_ACTIONS_WI();
 313                         CLOSE_ARRAY() <<
 314                         "\n";
 315                 }
 316         }
 317         else {
 318                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 319                 TRANS_TARGS();
 320                 CLOSE_ARRAY() <<
 321                 "\n";
 322
 323                 if ( redFsm->anyActions() ) {
 324                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActListId), TA() );
 325                         TRANS_ACTIONS();
 326                         CLOSE_ARRAY() <<
 327                         "\n";
 328                 }
 329         }
 330
 331         if ( redFsm->anyToStateActions() ) {
 332                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
 333                 TO_STATE_ACTIONS();
 334                 CLOSE_ARRAY() <<
 335                 "\n";
 336         }
 337
 338         if ( redFsm->anyFromStateActions() ) {
 339                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
 340                 FROM_STATE_ACTIONS();
 341                 CLOSE_ARRAY() <<
 342                 "\n";
 343         }
 344
 345         if ( redFsm->anyEofActions() ) {
 346                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActListId), EA() );
 347                 EOF_ACTIONS();
 348                 CLOSE_ARRAY() <<
 349                 "\n";
 350         }
 351
 352         if ( redFsm->anyEofTrans() ) {
 353                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset+1), ET() );
 354                 EOF_TRANS();
 355                 CLOSE_ARRAY() <<
 356                 "\n";
 357         }
 358
 359         STATE_IDS();
 360 }
 361
 362 void RubyFTabCodeGen::writeExec()
 363 {
 364         out <<
 365                 "begin\n"
 366                 "       testEof = false\n"
 367                 "       _klen, _trans, _keys";
 368
 369         if ( redFsm->anyRegCurStateRef() )
 370                 out << ", _ps";
 371
 372         if ( redFsm->anyConditions() )
 373                 out << ", _widec";
 374
 375         out << " = nil\n";
 376
 377         out <<
 378                 "       _goto_level = 0\n"
 379                 "       _resume = 10\n"
 380                 "       _eof_trans = 15\n"
 381                 "       _again = 20\n"
 382                 "       _test_eof = 30\n"
 383                 "       _out = 40\n";
 384
 385         out <<
 386                 "       while true\n"
 387                 "       if _goto_level <= 0\n";
 388
 389         if ( !noEnd ) {
 390                 out <<
 391                         "       if " << P() << " == " << PE() << "\n"
 392                         "               _goto_level = _test_eof\n"
 393                         "               next\n"
 394                         "       end\n";
 395         }
 396
 397         if ( redFsm->errState != 0 ) {
 398                 out <<
 399                         "       if " << vCS() << " == " << redFsm->errState->id << "\n"
 400                         "               _goto_level = _out\n"
 401                         "               next\n"
 402                         "       end\n";
 403         }
 404
 405         /* The resume label. */
 406         out <<
 407                 "       end\n"
 408                 "       if _goto_level <= _resume\n";
 409
 410         if ( redFsm->anyFromStateActions() ) {
 411                 out <<
 412                         "       case " << FSA() << "[" << vCS() << "] \n";
 413                         FROM_STATE_ACTION_SWITCH() <<
 414                         "       end # from state action switch \n"
 415                         "\n";
 416         }
 417
 418         if ( redFsm->anyConditions() )
 419                 COND_TRANSLATE();
 420
 421         LOCATE_TRANS();
 422
 423         if ( useIndicies )
 424                 out << "        _trans = " << I() << "[_trans];\n";
 425
 426         if ( redFsm->anyEofTrans() ) {
 427                 out <<
 428                         "       end\n"
 429                         "       if _goto_level <= _eof_trans\n";
 430         }
 431
 432         if ( redFsm->anyRegCurStateRef() )
 433                 out << "        _ps = " << vCS() << ";\n";
 434
 435         out <<
 436                 "       " << vCS() << " = " << TT() << "[_trans];\n"
 437                 "\n";
 438
 439         if ( redFsm->anyRegActions() ) {
 440                 out <<
 441                         "       if " << TA() << "[_trans] != 0\n"
 442                         "\n"
 443                         "               case " << TA() << "[_trans] \n";
 444                         ACTION_SWITCH() <<
 445                         "               end # action switch \n"
 446                         "       end\n"
 447                         "\n";
 448         }
 449
 450         /* The again label. */
 451         out <<
 452                 "       end\n"
 453                 "       if _goto_level <= _again\n";
 454
 455         if ( redFsm->anyToStateActions() ) {
 456                 out <<
 457                         "       case " << TSA() << "[" << vCS() << "] \n";
 458                         TO_STATE_ACTION_SWITCH() <<
 459                         "       end\n"
 460                         "\n";
 461         }
 462
 463         if ( redFsm->errState != 0 ) {
 464                 out <<
 465                         "       if " << vCS() << " == " << redFsm->errState->id << "\n"
 466                         "               _goto_level = _out\n"
 467                         "               next\n"
 468                         "       end\n";
 469         }
 470
 471         out << "        " << P() << " += 1\n";
 472
 473         if ( !noEnd ) {
 474                 out <<
 475                         "       if " << P() << " != " << PE() << "\n"
 476                         "               _goto_level = _resume\n"
 477                         "               next\n"
 478                         "       end\n";
 479         }
 480         else {
 481                 out <<
 482                         "       _goto_level = _resume\n"
 483                         "       next\n";
 484         }
 485
 486         /* The test eof label. */
 487         out <<
 488                 "       end\n"
 489                 "       if _goto_level <= _test_eof\n";
 490
 491         if ( redFsm->anyEofTrans() || redFsm->anyEofActions() ) {
 492                 out <<
 493                         "       if " << P() << " == " << vEOF() << "\n";
 494
 495                 if ( redFsm->anyEofTrans() ) {
 496                         out <<
 497                                 "       if " << ET() << "[" << vCS() << "] > 0\n"
 498                                 "               _trans = " << ET() << "[" << vCS() << "] - 1;\n"
 499                                 "               _goto_level = _eof_trans\n"
 500                                 "               next;\n"
 501                                 "       end\n";
 502                 }
 503
 504                 if ( redFsm->anyEofActions() ) {
 505                         out <<
 506                                 "       begin\n"
 507                                 "               case ( " << EA() << "[" << vCS() << "] )\n";
 508                                 EOF_ACTION_SWITCH() <<
 509                                 "               end\n"
 510                                 "       end\n";
 511                 }
 512
 513                 out <<
 514                         "       end\n"
 515                         "\n";
 516         }
 517
 518         out <<
 519                 "       end\n"
 520                 "       if _goto_level <= _out\n"
 521                 "               break\n"
 522                 "       end\n"
 523                 "end\n";
 524
 525         /* Wrapping the execute block. */
 526         out << "        end\n";
 527 }
 528
 529
 530 void RubyFTabCodeGen::calcIndexSize()
 531 {
 532         int sizeWithInds = 0, sizeWithoutInds = 0;
 533
 534         /* Calculate cost of using with indicies. */
 535         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 536                 int totalIndex = st->outSingle.length() + st->outRange.length() +
 537                                 (st->defTrans == 0 ? 0 : 1);
 538                 sizeWithInds += arrayTypeSize(redFsm->maxIndex) * totalIndex;
 539         }
 540         sizeWithInds += arrayTypeSize(redFsm->maxState) * redFsm->transSet.length();
 541         if ( redFsm->anyActions() )
 542                 sizeWithInds += arrayTypeSize(redFsm->maxActListId) * redFsm->transSet.length();
 543
 544         /* Calculate the cost of not using indicies. */
 545         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 546                 int totalIndex = st->outSingle.length() + st->outRange.length() +
 547                                 (st->defTrans == 0 ? 0 : 1);
 548                 sizeWithoutInds += arrayTypeSize(redFsm->maxState) * totalIndex;
 549                 if ( redFsm->anyActions() )
 550                         sizeWithoutInds += arrayTypeSize(redFsm->maxActListId) * totalIndex;
 551         }
 552
 553         /* If using indicies reduces the size, use them. */
 554         useIndicies = sizeWithInds < sizeWithoutInds;
 555 }
 556
 557 /*
 558  * Local Variables:
 559  * mode: c++
 560  * indent-tabs-mode: 1
 561  * c-file-style: "bsd"
 562  * End:
 563  */