ragel/goipgoto.cpp

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