ragel/cssplit.cpp

   1 /*
   2  *  Copyright 2006 Adrian Thurston <thurston@complang.org>
   3  */
   4
   5 /*  This file is part of Ragel.
   6  *
   7  *  Ragel is free software; you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License as published by
   9  *  the Free Software Foundation; either version 2 of the License, or
  10  *  (at your option) any later version.
  11  *
  12  *  Ragel is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License
  18  *  along with Ragel; if not, write to the Free Software
  19  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  */
  21
  22
  23 #include "ragel.h"
  24 #include "cssplit.h"
  25 #include "gendata.h"
  26 #include <assert.h>
  27
  28 using std::ostream;
  29 using std::ios;
  30 using std::endl;
  31
  32 /* Emit the goto to take for a given transition. */
  33 std::ostream &CSharpSplitCodeGen::TRANS_GOTO( RedTransAp *trans, int level )
  34 {
  35         if ( trans->targ->partition == currentPartition ) {
  36                 if ( trans->action != 0 ) {
  37                         /* Go to the transition which will go to the state. */
  38                         out << TABS(level) << "goto tr" << trans->id << ";";
  39                 }
  40                 else {
  41                         /* Go directly to the target state. */
  42                         out << TABS(level) << "goto st" << trans->targ->id << ";";
  43                 }
  44         }
  45         else {
  46                 if ( trans->action != 0 ) {
  47                         /* Go to the transition which will go to the state. */
  48                         out << TABS(level) << "goto ptr" << trans->id << ";";
  49                         trans->partitionBoundary = true;
  50                 }
  51                 else {
  52                         /* Go directly to the target state. */
  53                         out << TABS(level) << "goto pst" << trans->targ->id << ";";
  54                         trans->targ->partitionBoundary = true;
  55                 }
  56         }
  57         return out;
  58 }
  59
  60 /* Called from before writing the gotos for each state. */
  61 void CSharpSplitCodeGen::GOTO_HEADER( RedStateAp *state, bool stateInPartition )
  62 {
  63         bool anyWritten = IN_TRANS_ACTIONS( state );
  64
  65         if ( state->labelNeeded )
  66                 out << "st" << state->id << ":\n";
  67
  68         if ( state->toStateAction != 0 ) {
  69                 /* Remember that we wrote an action. Write every action in the list. */
  70                 anyWritten = true;
  71                 for ( GenActionTable::Iter item = state->toStateAction->key; item.lte(); item++ )
  72                         ACTION( out, item->value, state->id, false );
  73         }
  74
  75         /* Advance and test buffer pos. */
  76         if ( state->labelNeeded ) {
  77                 if ( !noEnd ) {
  78                         out <<
  79                                 "       if ( ++" << P() << " == " << PE() << " )\n"
  80                                 "               goto _out" << state->id << ";\n";
  81                 }
  82                 else {
  83                         out <<
  84                                 "       " << P() << " += 1;\n";
  85                 }
  86         }
  87
  88         /* Give the state a switch case. */
  89         out << "case " << state->id << ":\n";
  90
  91         if ( state->fromStateAction != 0 ) {
  92                 /* Remember that we wrote an action. Write every action in the list. */
  93                 anyWritten = true;
  94                 for ( GenActionTable::Iter item = state->fromStateAction->key; item.lte(); item++ )
  95                         ACTION( out, item->value, state->id, false );
  96         }
  97
  98         if ( anyWritten )
  99                 genLineDirective( out );
 100
 101         /* Record the prev state if necessary. */
 102         if ( state->anyRegCurStateRef() )
 103                 out << "        _ps = " << state->id << ";\n";
 104 }
 105
 106 std::ostream &CSharpSplitCodeGen::STATE_GOTOS( int partition )
 107 {
 108         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 109                 if ( st->partition == partition ) {
 110                         if ( st == redFsm->errState )
 111                                 STATE_GOTO_ERROR();
 112                         else {
 113                                 /* We call into the base of the goto which calls back into us
 114                                  * using virtual functions. Set the current partition rather
 115                                  * than coding parameter passing throughout. */
 116                                 currentPartition = partition;
 117
 118                                 /* Writing code above state gotos. */
 119                                 GOTO_HEADER( st, st->partition == partition );
 120
 121                                 if ( st->stateCondVect.length() > 0 ) {
 122                                         out << "        _widec = " << GET_KEY() << ";\n";
 123                                         emitCondBSearch( st, 1, 0, st->stateCondVect.length() - 1 );
 124                                 }
 125
 126                                 /* Try singles. */
 127                                 if ( st->outSingle.length() > 0 )
 128                                         emitSingleSwitch( st );
 129
 130                                 /* Default case is to binary search for the ranges, if that fails then */
 131                                 if ( st->outRange.length() > 0 )
 132                                         emitRangeBSearch( st, 1, 0, st->outRange.length() - 1 );
 133
 134                                 /* Write the default transition. */
 135                                 TRANS_GOTO( st->defTrans, 1 ) << "\n";
 136                         }
 137                 }
 138         }
 139         return out;
 140 }
 141
 142
 143 std::ostream &CSharpSplitCodeGen::PART_TRANS( int partition )
 144 {
 145         for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) {
 146                 if ( trans->partitionBoundary ) {
 147                         out <<
 148                                 "ptr" << trans->id << ":\n";
 149
 150                         if ( trans->action != 0 ) {
 151                                 /* If the action contains a next, then we must preload the current
 152                                  * state since the action may or may not set it. */
 153                                 if ( trans->action->anyNextStmt() )
 154                                         out << "        " << vCS() << " = " << trans->targ->id << ";\n";
 155
 156                                 /* Write each action in the list. */
 157                                 for ( GenActionTable::Iter item = trans->action->key; item.lte(); item++ )
 158                                         ACTION( out, item->value, trans->targ->id, false );
 159                         }
 160
 161                         out <<
 162                                 "       goto pst" << trans->targ->id << ";\n";
 163                         trans->targ->partitionBoundary = true;
 164                 }
 165         }
 166
 167         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 168                 if ( st->partitionBoundary ) {
 169                         out <<
 170                                 "       pst" << st->id << ":\n"
 171                                 "       " << vCS() << " = " << st->id << ";\n";
 172
 173                         if ( st->toStateAction != 0 ) {
 174                                 /* Remember that we wrote an action. Write every action in the list. */
 175                                 for ( GenActionTable::Iter item = st->toStateAction->key; item.lte(); item++ )
 176                                         ACTION( out, item->value, st->id, false );
 177                                 genLineDirective( out );
 178                         }
 179
 180                         ptOutLabelUsed = true;
 181                         out << "        goto _pt_out; \n";
 182                 }
 183         }
 184         return out;
 185 }
 186
 187 std::ostream &CSharpSplitCodeGen::EXIT_STATES( int partition )
 188 {
 189         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 190                 if ( st->partition == partition && st->outNeeded ) {
 191                         outLabelUsed = true;
 192                         out << "        _out" << st->id << ": " << vCS() << " = " <<
 193                                         st->id << "; goto _out; \n";
 194                 }
 195         }
 196         return out;
 197 }
 198
 199
 200 std::ostream &CSharpSplitCodeGen::PARTITION( int partition )
 201 {
 202         outLabelUsed = false;
 203         ptOutLabelUsed = false;
 204
 205         /* Initialize the partition boundaries, which get set during the writing
 206          * of states. After the state writing we will */
 207         for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
 208                 trans->partitionBoundary = false;
 209         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 210                 st->partitionBoundary = false;
 211
 212         out << "        " << ALPH_TYPE() << " *p = *_pp, *pe = *_ppe;\n";
 213
 214         if ( redFsm->anyRegCurStateRef() )
 215                 out << "        int _ps = 0;\n";
 216
 217         if ( redFsm->anyConditions() )
 218                 out << "        " << WIDE_ALPH_TYPE() << " _widec;\n";
 219
 220         if ( useAgainLabel() ) {
 221                 out <<
 222                         "       goto _resume;\n"
 223                         "\n"
 224                         "_again:\n"
 225                         "       switch ( " << vCS() << " ) {\n";
 226                         AGAIN_CASES() <<
 227                         "       default: break;\n"
 228                         "       }\n"
 229                         "\n";
 230
 231
 232                 if ( !noEnd ) {
 233                         outLabelUsed = true;
 234                         out <<
 235                                 "       if ( ++" << P() << " == " << PE() << " )\n"
 236                                 "               goto _out;\n";
 237
 238                 }
 239                 else {
 240                         out <<
 241                                 "       " << P() << " += 1;\n";
 242                 }
 243
 244                 out <<
 245                         "_resume:\n";
 246         }
 247
 248         out <<
 249                 "       switch ( " << vCS() << " )\n    {\n";
 250                 STATE_GOTOS( partition );
 251                 SWITCH_DEFAULT() <<
 252                 "       }\n";
 253                 PART_TRANS( partition );
 254                 EXIT_STATES( partition );
 255
 256         if ( outLabelUsed ) {
 257                 out <<
 258                         "\n"
 259                         "       _out:\n"
 260                         "       *_pp = p;\n"
 261                         "       *_ppe = pe;\n"
 262                         "       return 0;\n";
 263         }
 264
 265         if ( ptOutLabelUsed ) {
 266                 out <<
 267                         "\n"
 268                         "       _pt_out:\n"
 269                         "       *_pp = p;\n"
 270                         "       *_ppe = pe;\n"
 271                         "       return 1;\n";
 272         }
 273
 274         return out;
 275 }
 276
 277 std::ostream &CSharpSplitCodeGen::PART_MAP()
 278 {
 279         int *partMap = new int[redFsm->stateList.length()];
 280         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 281                 partMap[st->id] = st->partition;
 282
 283         out << "\t";
 284         int totalItem = 0;
 285         for ( int i = 0; i < redFsm->stateList.length(); i++ ) {
 286                 out << partMap[i];
 287                 if ( i != redFsm->stateList.length() - 1 ) {
 288                         out << ", ";
 289                         if ( ++totalItem % IALL == 0 )
 290                                 out << "\n\t";
 291                 }
 292         }
 293
 294         delete[] partMap;
 295         return out;
 296 }
 297
 298 void CSharpSplitCodeGen::writeData()
 299 {
 300         out <<
 301                 "const int " << START() << " = " << START_STATE_ID() << ";\n"
 302                 "\n";
 303
 304         if ( !noFinal ) {
 305                 out <<
 306                         "const int " << FIRST_FINAL() << " = " << FIRST_FINAL_STATE() << ";\n"
 307                         "\n";
 308         }
 309
 310         if ( !noError ) {
 311                 out <<
 312                         "const int " << ERROR() << " = " << ERROR_STATE() << ";\n"
 313                         "\n";
 314         }
 315
 316
 317         OPEN_ARRAY( ARRAY_TYPE(numSplitPartitions), PM() );
 318         PART_MAP();
 319         CLOSE_ARRAY() <<
 320         "\n";
 321
 322         for ( int p = 0; p < redFsm->nParts; p++ ) {
 323                 out << "int partition" << p << "( " << ALPH_TYPE() << " **_pp, " << ALPH_TYPE() <<
 324                         " **_ppe, struct " << FSM_NAME() << " *fsm );\n";
 325         }
 326         out << "\n";
 327 }
 328
 329 std::ostream &CSharpSplitCodeGen::ALL_PARTITIONS()
 330 {
 331         /* compute the format string. */
 332         int width = 0, high = redFsm->nParts - 1;
 333         while ( high > 0 ) {
 334                 width++;
 335                 high /= 10;
 336         }
 337         assert( width <= 8 );
 338         char suffFormat[] = "_%6.6d.c";
 339         suffFormat[2] = suffFormat[4] = ( '0' + width );
 340
 341         for ( int p = 0; p < redFsm->nParts; p++ ) {
 342                 char suffix[10];
 343                 sprintf( suffix, suffFormat, p );
 344                 const char *fn = fileNameFromStem( sourceFileName, suffix );
 345                 const char *include = fileNameFromStem( sourceFileName, ".h" );
 346
 347                 /* Create the filter on the output and open it. */
 348                 output_filter *partFilter = new output_filter( fn );
 349                 partFilter->open( fn, ios::out|ios::trunc );
 350                 if ( !partFilter->is_open() ) {
 351                         error() << "error opening " << fn << " for writing" << endl;
 352                         exit(1);
 353                 }
 354
 355                 /* Attach the new file to the output stream. */
 356                 std::streambuf *prev_rdbuf = out.rdbuf( partFilter );
 357
 358                 out <<
 359                         "#include \"" << include << "\"\n"
 360                         "int partition" << p << "( " << ALPH_TYPE() << " **_pp, " << ALPH_TYPE() <<
 361                                         " **_ppe, struct " << FSM_NAME() << " *fsm )\n"
 362                         "{\n";
 363                         PARTITION( p ) <<
 364                         "}\n\n";
 365                 out.flush();
 366
 367                 /* Fix the output stream. */
 368                 out.rdbuf( prev_rdbuf );
 369         }
 370         return out;
 371 }
 372
 373
 374 void CSharpSplitCodeGen::writeExec()
 375 {
 376         /* Must set labels immediately before writing because we may depend on the
 377          * noend write option. */
 378         setLabelsNeeded();
 379         out <<
 380                 "       {\n"
 381                 "       int _stat = 0;\n";
 382
 383         if ( !noEnd ) {
 384                 out <<
 385                         "       if ( " << P() << " == " << PE() << " )\n"
 386                         "               goto _out;\n";
 387         }
 388
 389         out << "        goto _resume;\n";
 390
 391         /* In this reentry, to-state actions have already been executed on the
 392          * partition-switch exit from the last partition. */
 393         out << "_reenter:\n";
 394
 395         if ( !noEnd ) {
 396                 out <<
 397                         "       if ( ++" << P() << " == " << PE() << " )\n"
 398                         "               goto _out;\n";
 399         }
 400         else {
 401                 out <<
 402                         "       " << P() << " += 1;\n";
 403         }
 404
 405         out << "_resume:\n";
 406
 407         out <<
 408                 "       switch ( " << PM() << "[" << vCS() << "] ) {\n";
 409         for ( int p = 0; p < redFsm->nParts; p++ ) {
 410                 out <<
 411                         "       case " << p << ":\n"
 412                         "               _stat = partition" << p << "( &p, &pe, fsm );\n"
 413                         "               break;\n";
 414         }
 415         out <<
 416                 "       }\n"
 417                 "       if ( _stat )\n"
 418                 "               goto _reenter;\n";
 419
 420         if ( !noEnd )
 421                 out << "        _out: {}\n";
 422
 423         out <<
 424                 "       }\n";
 425
 426         ALL_PARTITIONS();
 427 }
 428
 429 void CSharpSplitCodeGen::setLabelsNeeded( RedStateAp *fromState, GenInlineList *inlineList )
 430 {
 431         for ( GenInlineList::Iter item = *inlineList; item.lte(); item++ ) {
 432                 switch ( item->type ) {
 433                 case GenInlineItem::Goto: case GenInlineItem::Call: {
 434                         /* In split code gen we only need labels for transitions across
 435                          * partitions. */
 436                         if ( fromState->partition == item->targState->partition ){
 437                                 /* Mark the target as needing a label. */
 438                                 item->targState->labelNeeded = true;
 439                         }
 440                         break;
 441                 }
 442                 default: break;
 443                 }
 444
 445                 if ( item->children != 0 )
 446                         setLabelsNeeded( fromState, item->children );
 447         }
 448 }
 449
 450 void CSharpSplitCodeGen::setLabelsNeeded( RedStateAp *fromState, RedTransAp *trans )
 451 {
 452         /* In the split code gen we don't need labels for transitions across
 453          * partitions. */
 454         if ( fromState->partition == trans->targ->partition ) {
 455                 /* If there is no action with a next statement, then the label will be
 456                  * needed. */
 457                 trans->labelNeeded = true;
 458                 if ( trans->action == 0 || !trans->action->anyNextStmt() )
 459                         trans->targ->labelNeeded = true;
 460         }
 461
 462         /* Need labels for states that have goto or calls in action code
 463          * invoked on characters (ie, not from out action code). */
 464         if ( trans->action != 0 ) {
 465                 /* Loop the actions. */
 466                 for ( GenActionTable::Iter act = trans->action->key; act.lte(); act++ ) {
 467                         /* Get the action and walk it's tree. */
 468                         setLabelsNeeded( fromState, act->value->inlineList );
 469                 }
 470         }
 471 }
 472
 473 /* Set up labelNeeded flag for each state. */
 474 void CSharpSplitCodeGen::setLabelsNeeded()
 475 {
 476         /* If we use the _again label, then we the _again switch, which uses all
 477          * labels. */
 478         if ( useAgainLabel() ) {
 479                 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 480                         st->labelNeeded = true;
 481         }
 482         else {
 483                 /* Do not use all labels by default, init all labelNeeded vars to false. */
 484                 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 485                         st->labelNeeded = false;
 486                 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
 487                         trans->labelNeeded = false;
 488
 489                 /* Walk all transitions and set only those that have targs. */
 490                 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 491                         for ( RedTransList::Iter tel = st->outRange; tel.lte(); tel++ )
 492                                 setLabelsNeeded( st, tel->value );
 493
 494                         for ( RedTransList::Iter tel = st->outSingle; tel.lte(); tel++ )
 495                                 setLabelsNeeded( st, tel->value );
 496
 497                         if ( st->defTrans != 0 )
 498                                 setLabelsNeeded( st, st->defTrans );
 499                 }
 500         }
 501
 502         if ( !noEnd ) {
 503                 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 504                         st->outNeeded = st->labelNeeded;
 505         }
 506         else {
 507                 if ( redFsm->errState != 0 )
 508                         redFsm->errState->outNeeded = true;
 509
 510                 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) {
 511                         /* Any state with a transition in that has a break will need an
 512                          * out label. */
 513                         if ( trans->action != 0 && trans->action->anyBreakStmt() )
 514                                 trans->targ->outNeeded = true;
 515                 }
 516         }
 517 }
 518