rlgen-cd/ipgotocodegen.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 "ipgotocodegen.h"
  26 #include "redfsm.h"
  27 #include "gendata.h"
  28 #include "bstmap.h"
  29
  30 bool IpGotoCodeGen::useAgainLabel()
  31 {
  32         return redFsm->anyRegActionRets() ||
  33                         redFsm->anyRegActionByValControl() ||
  34                         redFsm->anyRegNextStmt();
  35 }
  36
  37 void IpGotoCodeGen::GOTO( ostream &ret, int gotoDest, bool inFinish )
  38 {
  39         ret << "{" << CTRL_FLOW() << "goto st" << gotoDest << ";}";
  40 }
  41
  42 void IpGotoCodeGen::CALL( ostream &ret, int callDest, int targState, bool inFinish )
  43 {
  44         ret << "{" << STACK() << "[" << TOP() << "++] = " << targState <<
  45                         "; " << CTRL_FLOW() << "goto st" << callDest << ";}";
  46 }
  47
  48 void IpGotoCodeGen::RET( ostream &ret, bool inFinish )
  49 {
  50         ret << "{" << CS() << " = " << STACK() << "[--" << TOP() << "]; " <<
  51                         CTRL_FLOW() << "goto _again;}";
  52 }
  53
  54 void IpGotoCodeGen::GOTO_EXPR( ostream &ret, InlineItem *ilItem, bool inFinish )
  55 {
  56         ret << "{" << CS() << " = (";
  57         INLINE_LIST( ret, ilItem->children, 0, inFinish );
  58         ret << "); " << CTRL_FLOW() << "goto _again;}";
  59 }
  60
  61 void IpGotoCodeGen::CALL_EXPR( ostream &ret, InlineItem *ilItem, int targState, bool inFinish )
  62 {
  63         ret << "{" << STACK() << "[" << TOP() << "++] = " << targState << "; " << CS() << " = (";
  64         INLINE_LIST( ret, ilItem->children, 0, inFinish );
  65         ret << "); " << CTRL_FLOW() << "goto _again;}";
  66 }
  67
  68 void IpGotoCodeGen::NEXT( ostream &ret, int nextDest, bool inFinish )
  69 {
  70         ret << CS() << " = " << nextDest << ";";
  71 }
  72
  73 void IpGotoCodeGen::NEXT_EXPR( ostream &ret, InlineItem *ilItem, bool inFinish )
  74 {
  75         ret << CS() << " = (";
  76         INLINE_LIST( ret, ilItem->children, 0, inFinish );
  77         ret << ");";
  78 }
  79
  80 void IpGotoCodeGen::CURS( ostream &ret, bool inFinish )
  81 {
  82         ret << "(_ps)";
  83 }
  84
  85 void IpGotoCodeGen::TARGS( ostream &ret, bool inFinish, int targState )
  86 {
  87         ret << targState;
  88 }
  89
  90 void IpGotoCodeGen::BREAK( ostream &ret, int targState )
  91 {
  92         ret << CTRL_FLOW() << "goto _out" << targState << ";";
  93 }
  94
  95 bool IpGotoCodeGen::IN_TRANS_ACTIONS( RedStateAp *state )
  96 {
  97         bool anyWritten = false;
  98
  99         /* Emit any transitions that have actions and that go to this state. */
 100         for ( int it = 0; it < state->numInTrans; it++ ) {
 101                 RedTransAp *trans = state->inTrans[it];
 102                 if ( trans->action != 0 && trans->labelNeeded ) {
 103                         /* Remember that we wrote an action so we know to write the
 104                          * line directive for going back to the output. */
 105                         anyWritten = true;
 106
 107                         /* Write the label for the transition so it can be jumped to. */
 108                         out << "tr" << trans->id << ":\n";
 109
 110                         /* If the action contains a next, then we must preload the current
 111                          * state since the action may or may not set it. */
 112                         if ( trans->action->anyNextStmt() )
 113                                 out << "        " << CS() << " = " << trans->targ->id << ";\n";
 114
 115                         /* Write each action in the list. */
 116                         for ( ActionTable::Iter item = trans->action->key; item.lte(); item++ )
 117                                 ACTION( out, item->value, trans->targ->id, false );
 118
 119                         /* If the action contains a next then we need to reload, otherwise
 120                          * jump directly to the target state. */
 121                         if ( trans->action->anyNextStmt() )
 122                                 out << "\tgoto _again;\n";
 123                         else
 124                                 out << "\tgoto st" << trans->targ->id << ";\n";
 125                 }
 126         }
 127
 128         return anyWritten;
 129 }
 130
 131 /* Called from GotoCodeGen::STATE_GOTOS just before writing the gotos for each
 132  * state. */
 133 void IpGotoCodeGen::GOTO_HEADER( RedStateAp *state )
 134 {
 135         bool anyWritten = IN_TRANS_ACTIONS( state );
 136
 137         if ( state->labelNeeded )
 138                 out << "st" << state->id << ":\n";
 139
 140         if ( state->toStateAction != 0 ) {
 141                 /* Remember that we wrote an action. Write every action in the list. */
 142                 anyWritten = true;
 143                 for ( ActionTable::Iter item = state->toStateAction->key; item.lte(); item++ )
 144                         ACTION( out, item->value, state->id, false );
 145         }
 146
 147         /* Advance and test buffer pos. */
 148         if ( state->labelNeeded ) {
 149                 if ( hasEnd ) {
 150                         out <<
 151                                 "       if ( ++" << P() << " == " << PE() << " )\n"
 152                                 "               goto _out" << state->id << ";\n";
 153                 }
 154                 else {
 155                         out <<
 156                                 "       " << P() << " += 1;\n";
 157                 }
 158         }
 159
 160         /* Give the state a switch case. */
 161         out << "case " << state->id << ":\n";
 162
 163         if ( state->fromStateAction != 0 ) {
 164                 /* Remember that we wrote an action. Write every action in the list. */
 165                 anyWritten = true;
 166                 for ( ActionTable::Iter item = state->fromStateAction->key; item.lte(); item++ )
 167                         ACTION( out, item->value, state->id, false );
 168         }
 169
 170         if ( anyWritten )
 171                 genLineDirective( out );
 172
 173         /* Record the prev state if necessary. */
 174         if ( state->anyRegCurStateRef() )
 175                 out << "        _ps = " << state->id << ";\n";
 176 }
 177
 178 void IpGotoCodeGen::STATE_GOTO_ERROR()
 179 {
 180         /* In the error state we need to emit some stuff that usually goes into
 181          * the header. */
 182         RedStateAp *state = redFsm->errState;
 183         bool anyWritten = IN_TRANS_ACTIONS( state );
 184
 185         /* No case label needed since we don't switch on the error state. */
 186         if ( anyWritten )
 187                 genLineDirective( out );
 188
 189         if ( state->labelNeeded )
 190                 out << "st" << state->id << ":\n";
 191
 192         /* Break out here. */
 193         out << "        goto _out" << state->id << ";\n";
 194 }
 195
 196
 197 /* Emit the goto to take for a given transition. */
 198 std::ostream &IpGotoCodeGen::TRANS_GOTO( RedTransAp *trans, int level )
 199 {
 200         if ( trans->action != 0 ) {
 201                 /* Go to the transition which will go to the state. */
 202                 out << TABS(level) << "goto tr" << trans->id << ";";
 203         }
 204         else {
 205                 /* Go directly to the target state. */
 206                 out << TABS(level) << "goto st" << trans->targ->id << ";";
 207         }
 208         return out;
 209 }
 210
 211 std::ostream &IpGotoCodeGen::EXIT_STATES()
 212 {
 213         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 214                 if ( st->outNeeded ) {
 215                         outLabelUsed = true;
 216                         out << "        _out" << st->id << ": " << CS() << " = " <<
 217                                         st->id << "; goto _out; \n";
 218                 }
 219         }
 220         return out;
 221 }
 222
 223 std::ostream &IpGotoCodeGen::AGAIN_CASES()
 224 {
 225         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 226                 out <<
 227                         "               case " << st->id << ": goto st" << st->id << ";\n";
 228         }
 229         return out;
 230 }
 231
 232 std::ostream &IpGotoCodeGen::FINISH_CASES()
 233 {
 234         bool anyWritten = false;
 235
 236         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 237                 if ( st->eofAction != 0 ) {
 238                         if ( st->eofAction->eofRefs == 0 )
 239                                 st->eofAction->eofRefs = new IntSet;
 240                         st->eofAction->eofRefs->insert( st->id );
 241                 }
 242         }
 243
 244         for ( ActionTableMap::Iter act = redFsm->actionMap; act.lte(); act++ ) {
 245                 if ( act->eofRefs != 0 ) {
 246                         for ( IntSet::Iter pst = *act->eofRefs; pst.lte(); pst++ )
 247                                 out << "        case " << *pst << ": \n";
 248
 249                         /* Remember that we wrote a trans so we know to write the
 250                          * line directive for going back to the output. */
 251                         anyWritten = true;
 252
 253                         /* Write each action in the eof action list. */
 254                         for ( ActionTable::Iter item = act->key; item.lte(); item++ )
 255                                 ACTION( out, item->value, STATE_ERR_STATE, true );
 256                         out << "\tbreak;\n";
 257                 }
 258         }
 259
 260         if ( anyWritten )
 261                 genLineDirective( out );
 262         return out;
 263 }
 264
 265 void IpGotoCodeGen::setLabelsNeeded( InlineList *inlineList )
 266 {
 267         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
 268                 switch ( item->type ) {
 269                 case InlineItem::Goto: case InlineItem::Call: {
 270                         /* Mark the target as needing a label. */
 271                         item->targState->labelNeeded = true;
 272                         break;
 273                 }
 274                 default: break;
 275                 }
 276
 277                 if ( item->children != 0 )
 278                         setLabelsNeeded( item->children );
 279         }
 280 }
 281
 282 /* Set up labelNeeded flag for each state. */
 283 void IpGotoCodeGen::setLabelsNeeded()
 284 {
 285         /* If we use the _again label, then we the _again switch, which uses all
 286          * labels. */
 287         if ( useAgainLabel() ) {
 288                 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 289                         st->labelNeeded = true;
 290         }
 291         else {
 292                 /* Do not use all labels by default, init all labelNeeded vars to false. */
 293                 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 294                         st->labelNeeded = false;
 295
 296                 if ( redFsm->errState != 0 && redFsm->anyLmSwitchError() )
 297                         redFsm->errState->labelNeeded = true;
 298
 299                 /* Walk all transitions and set only those that have targs. */
 300                 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) {
 301                         /* If there is no action with a next statement, then the label will be
 302                          * needed. */
 303                         if ( trans->action == 0 || !trans->action->anyNextStmt() )
 304                                 trans->targ->labelNeeded = true;
 305
 306                         /* Need labels for states that have goto or calls in action code
 307                          * invoked on characters (ie, not from out action code). */
 308                         if ( trans->action != 0 ) {
 309                                 /* Loop the actions. */
 310                                 for ( ActionTable::Iter act = trans->action->key; act.lte(); act++ ) {
 311                                         /* Get the action and walk it's tree. */
 312                                         setLabelsNeeded( act->value->inlineList );
 313                                 }
 314                         }
 315                 }
 316         }
 317
 318         if ( hasEnd ) {
 319                 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
 320                         st->outNeeded = st->labelNeeded;
 321         }
 322         else {
 323                 if ( redFsm->errState != 0 )
 324                         redFsm->errState->outNeeded = true;
 325
 326                 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) {
 327                         /* Any state with a transition in that has a break will need an
 328                          * out label. */
 329                         if ( trans->action != 0 && trans->action->anyBreakStmt() )
 330                                 trans->targ->outNeeded = true;
 331                 }
 332         }
 333 }
 334
 335 void IpGotoCodeGen::writeOutData()
 336 {
 337         out <<
 338                 "static const int " << START() << " = " << START_STATE_ID() << ";\n"
 339                 "\n";
 340
 341         if ( writeFirstFinal ) {
 342                 out <<
 343                         "static const int " << FIRST_FINAL() << " = " << FIRST_FINAL_STATE() << ";\n"
 344                         "\n";
 345         }
 346
 347         if ( writeErr ) {
 348                 out <<
 349                         "static const int " << ERROR() << " = " << ERROR_STATE() << ";\n"
 350                         "\n";
 351         }
 352 }
 353
 354 void IpGotoCodeGen::writeOutExec()
 355 {
 356         /* Must set labels immediately before writing because we may depend on the
 357          * noend write option. */
 358         setLabelsNeeded();
 359         outLabelUsed = false;
 360
 361         out << "        {\n";
 362
 363         if ( redFsm->anyRegCurStateRef() )
 364                 out << "        int _ps = 0;\n";
 365
 366         if ( redFsm->anyConditions() )
 367                 out << "        " << WIDE_ALPH_TYPE() << " _widec;\n";
 368
 369         if ( hasEnd ) {
 370                 outLabelUsed = true;
 371                 out <<
 372                         "       if ( " << P() << " == " << PE() << " )\n"
 373                         "               goto _out;\n";
 374         }
 375
 376         if ( useAgainLabel() ) {
 377                 out <<
 378                         "       goto _resume;\n"
 379                         "\n"
 380                         "_again:\n"
 381                         "       switch ( " << CS() << " ) {\n";
 382                         AGAIN_CASES() <<
 383                         "       default: break;\n"
 384                         "       }\n"
 385                         "\n";
 386
 387                 if ( hasEnd ) {
 388                         outLabelUsed = true;
 389                         out <<
 390                                 "       if ( ++" << P() << " == " << PE() << " )\n"
 391                                 "               goto _out;\n";
 392                 }
 393                 else {
 394                         out <<
 395                                 "       " << P() << " += 1;\n";
 396                 }
 397
 398                 out << "_resume:\n";
 399         }
 400
 401         out <<
 402                 "       switch ( " << CS() << " )\n     {\n";
 403                 STATE_GOTOS();
 404                 SWITCH_DEFAULT() <<
 405                 "       }\n";
 406                 EXIT_STATES() <<
 407                 "\n";
 408
 409         if ( outLabelUsed )
 410                 out << "        _out: {}\n";
 411
 412         out <<
 413                 "       }\n";
 414 }
 415
 416 void IpGotoCodeGen::writeOutEOF()
 417 {
 418         if ( redFsm->anyEofActions() ) {
 419                 out <<
 420                         "       {\n"
 421                         "       switch ( " << CS() << " ) {\n";
 422                         FINISH_CASES();
 423                         SWITCH_DEFAULT() <<
 424                         "       }\n"
 425                         "       }\n"
 426                         "\n";
 427         }
 428 }