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