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