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