ragel/csftable.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 "csftable.h"
  26 #include "redfsm.h"
  27 #include "gendata.h"
  28
  29 /* Determine if we should use indicies or not. */
  30 void CSharpFTabCodeGen::calcIndexSize()
  31 {
  32         int sizeWithInds = 0, sizeWithoutInds = 0;
  33
  34         /* Calculate cost of using with indicies. */
  35         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  36                 int totalIndex = st->outSingle.length() + st->outRange.length() +
  37                                 (st->defTrans == 0 ? 0 : 1);
  38                 sizeWithInds += arrayTypeSize(redFsm->maxIndex) * totalIndex;
  39         }
  40         sizeWithInds += arrayTypeSize(redFsm->maxState) * redFsm->transSet.length();
  41         if ( redFsm->anyActions() )
  42                 sizeWithInds += arrayTypeSize(redFsm->maxActListId) * redFsm->transSet.length();
  43
  44         /* Calculate the cost of not using indicies. */
  45         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  46                 int totalIndex = st->outSingle.length() + st->outRange.length() +
  47                                 (st->defTrans == 0 ? 0 : 1);
  48                 sizeWithoutInds += arrayTypeSize(redFsm->maxState) * totalIndex;
  49                 if ( redFsm->anyActions() )
  50                         sizeWithoutInds += arrayTypeSize(redFsm->maxActListId) * totalIndex;
  51         }
  52
  53         /* If using indicies reduces the size, use them. */
  54         useIndicies = sizeWithInds < sizeWithoutInds;
  55 }
  56
  57 std::ostream &CSharpFTabCodeGen::TO_STATE_ACTION( RedStateAp *state )
  58 {
  59         int act = 0;
  60         if ( state->toStateAction != 0 )
  61                 act = state->toStateAction->actListId+1;
  62         out << act;
  63         return out;
  64 }
  65
  66 std::ostream &CSharpFTabCodeGen::FROM_STATE_ACTION( RedStateAp *state )
  67 {
  68         int act = 0;
  69         if ( state->fromStateAction != 0 )
  70                 act = state->fromStateAction->actListId+1;
  71         out << act;
  72         return out;
  73 }
  74
  75 std::ostream &CSharpFTabCodeGen::EOF_ACTION( RedStateAp *state )
  76 {
  77         int act = 0;
  78         if ( state->eofAction != 0 )
  79                 act = state->eofAction->actListId+1;
  80         out << act;
  81         return out;
  82 }
  83
  84
  85 /* Write out the function for a transition. */
  86 std::ostream &CSharpFTabCodeGen::TRANS_ACTION( RedTransAp *trans )
  87 {
  88         int action = 0;
  89         if ( trans->action != 0 )
  90                 action = trans->action->actListId+1;
  91         out << action;
  92         return out;
  93 }
  94
  95 /* Write out the function switch. This switch is keyed on the values
  96  * of the func index. */
  97 std::ostream &CSharpFTabCodeGen::TO_STATE_ACTION_SWITCH()
  98 {
  99         /* Loop the actions. */
 100         for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
 101                 if ( redAct->numToStateRefs > 0 ) {
 102                         /* Write the entry label. */
 103                         out << "\tcase " << redAct->actListId+1 << ":\n";
 104
 105                         /* Write each action in the list of action items. */
 106                         for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
 107                                 ACTION( out, item->value, 0, false );
 108
 109                         out << "\tbreak;\n";
 110                 }
 111         }
 112
 113         genLineDirective( out );
 114         return out;
 115 }
 116
 117 /* Write out the function switch. This switch is keyed on the values
 118  * of the func index. */
 119 std::ostream &CSharpFTabCodeGen::FROM_STATE_ACTION_SWITCH()
 120 {
 121         /* Loop the actions. */
 122         for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
 123                 if ( redAct->numFromStateRefs > 0 ) {
 124                         /* Write the entry label. */
 125                         out << "\tcase " << redAct->actListId+1 << ":\n";
 126
 127                         /* Write each action in the list of action items. */
 128                         for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
 129                                 ACTION( out, item->value, 0, false );
 130
 131                         out << "\tbreak;\n";
 132                 }
 133         }
 134
 135         genLineDirective( out );
 136         return out;
 137 }
 138
 139 std::ostream &CSharpFTabCodeGen::EOF_ACTION_SWITCH()
 140 {
 141         /* Loop the actions. */
 142         for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
 143                 if ( redAct->numEofRefs > 0 ) {
 144                         /* Write the entry label. */
 145                         out << "\tcase " << redAct->actListId+1 << ":\n";
 146
 147                         /* Write each action in the list of action items. */
 148                         for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
 149                                 ACTION( out, item->value, 0, true );
 150
 151                         out << "\tbreak;\n";
 152                 }
 153         }
 154
 155         genLineDirective( out );
 156         return out;
 157 }
 158
 159 /* Write out the function switch. This switch is keyed on the values
 160  * of the func index. */
 161 std::ostream &CSharpFTabCodeGen::ACTION_SWITCH()
 162 {
 163         /* Loop the actions. */
 164         for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
 165                 if ( redAct->numTransRefs > 0 ) {
 166                         /* Write the entry label. */
 167                         out << "\tcase " << redAct->actListId+1 << ":\n";
 168
 169                         /* Write each action in the list of action items. */
 170                         for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
 171                                 ACTION( out, item->value, 0, false );
 172
 173                         out << "\tbreak;\n";
 174                 }
 175         }
 176
 177         genLineDirective( out );
 178         return out;
 179 }
 180
 181 void CSharpFTabCodeGen::writeData()
 182 {
 183         if ( redFsm->anyConditions() ) {
 184                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondOffset), CO() );
 185                 COND_OFFSETS();
 186                 CLOSE_ARRAY() <<
 187                 "\n";
 188
 189                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondLen), CL() );
 190                 COND_LENS();
 191                 CLOSE_ARRAY() <<
 192                 "\n";
 193
 194                 OPEN_ARRAY( WIDE_ALPH_TYPE(), CK() );
 195                 COND_KEYS();
 196                 CLOSE_ARRAY() <<
 197                 "\n";
 198
 199                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondSpaceId), C() );
 200                 COND_SPACES();
 201                 CLOSE_ARRAY() <<
 202                 "\n";
 203         }
 204
 205         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxKeyOffset), KO() );
 206         KEY_OFFSETS();
 207         CLOSE_ARRAY() <<
 208         "\n";
 209
 210         OPEN_ARRAY( WIDE_ALPH_TYPE(), K() );
 211         KEYS();
 212         CLOSE_ARRAY() <<
 213         "\n";
 214
 215         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxSingleLen), SL() );
 216         SINGLE_LENS();
 217         CLOSE_ARRAY() <<
 218         "\n";
 219
 220         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxRangeLen), RL() );
 221         RANGE_LENS();
 222         CLOSE_ARRAY() <<
 223         "\n";
 224
 225         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset), IO() );
 226         INDEX_OFFSETS();
 227         CLOSE_ARRAY() <<
 228         "\n";
 229
 230         if ( useIndicies ) {
 231                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex), I() );
 232                 INDICIES();
 233                 CLOSE_ARRAY() <<
 234                 "\n";
 235
 236                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 237                 TRANS_TARGS_WI();
 238                 CLOSE_ARRAY() <<
 239                 "\n";
 240
 241                 if ( redFsm->anyActions() ) {
 242                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActListId), TA() );
 243                         TRANS_ACTIONS_WI();
 244                         CLOSE_ARRAY() <<
 245                         "\n";
 246                 }
 247         }
 248         else {
 249                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 250                 TRANS_TARGS();
 251                 CLOSE_ARRAY() <<
 252                 "\n";
 253
 254                 if ( redFsm->anyActions() ) {
 255                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActListId), TA() );
 256                         TRANS_ACTIONS();
 257                         CLOSE_ARRAY() <<
 258                         "\n";
 259                 }
 260         }
 261
 262         if ( redFsm->anyToStateActions() ) {
 263                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
 264                 TO_STATE_ACTIONS();
 265                 CLOSE_ARRAY() <<
 266                 "\n";
 267         }
 268
 269         if ( redFsm->anyFromStateActions() ) {
 270                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
 271                 FROM_STATE_ACTIONS();
 272                 CLOSE_ARRAY() <<
 273                 "\n";
 274         }
 275
 276         if ( redFsm->anyEofActions() ) {
 277                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActListId), EA() );
 278                 EOF_ACTIONS();
 279                 CLOSE_ARRAY() <<
 280                 "\n";
 281         }
 282
 283         if ( redFsm->anyEofTrans() ) {
 284                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset+1), ET() );
 285                 EOF_TRANS();
 286                 CLOSE_ARRAY() <<
 287                 "\n";
 288         }
 289
 290         STATE_IDS();
 291 }
 292
 293 void CSharpFTabCodeGen::writeExec()
 294 {
 295         testEofUsed = false;
 296         outLabelUsed = false;
 297         initVarTypes();
 298
 299         out <<
 300                 "       {\n"
 301                 "       " << klenType << " _klen";
 302
 303         if ( redFsm->anyRegCurStateRef() )
 304                 out << ", _ps";
 305
 306         out <<
 307                 ";\n"
 308                 "       " << keysType << " _keys;\n"
 309                 "       " << transType << " _trans;\n";
 310
 311         if ( redFsm->anyConditions() )
 312                 out << "        " << WIDE_ALPH_TYPE() << " _widec;\n";
 313
 314         out << "\n";
 315
 316         if ( !noEnd ) {
 317                 testEofUsed = true;
 318                 out <<
 319                         "       if ( " << P() << " == " << PE() << " )\n"
 320                         "               goto _test_eof;\n";
 321         }
 322
 323         if ( redFsm->errState != 0 ) {
 324                 outLabelUsed = true;
 325                 out <<
 326                         "       if ( " << vCS() << " == " << redFsm->errState->id << " )\n"
 327                         "               goto _out;\n";
 328         }
 329
 330         out << "_resume:\n";
 331
 332         if ( redFsm->anyFromStateActions() ) {
 333                 out <<
 334                         "       switch ( " << FSA() << "[" << vCS() << "] ) {\n";
 335                         FROM_STATE_ACTION_SWITCH();
 336                         SWITCH_DEFAULT() <<
 337                         "       }\n"
 338                         "\n";
 339         }
 340
 341         if ( redFsm->anyConditions() )
 342                 COND_TRANSLATE();
 343
 344         LOCATE_TRANS();
 345
 346         out << "_match:\n";
 347
 348         if ( useIndicies )
 349                 out << "        _trans = " << CAST(transType) << I() << "[_trans];\n";
 350
 351         if ( redFsm->anyEofTrans() )
 352                 out << "_eof_trans:\n";
 353
 354         if ( redFsm->anyRegCurStateRef() )
 355                 out << "        _ps = " << vCS() << ";\n";
 356
 357         out <<
 358                 "       " << vCS() << " = " << TT() << "[_trans];\n"
 359                 "\n";
 360
 361         if ( redFsm->anyRegActions() ) {
 362                 out <<
 363                         "       if ( " << TA() << "[_trans] == 0 )\n"
 364                         "               goto _again;\n"
 365                         "\n"
 366                         "       switch ( " << TA() << "[_trans] ) {\n";
 367                         ACTION_SWITCH();
 368                         SWITCH_DEFAULT() <<
 369                         "       }\n"
 370                         "\n";
 371         }
 372
 373         if ( redFsm->anyRegActions() || redFsm->anyActionGotos() ||
 374                         redFsm->anyActionCalls() || redFsm->anyActionRets() )
 375                 out << "_again:\n";
 376
 377         if ( redFsm->anyToStateActions() ) {
 378                 out <<
 379                         "       switch ( " << TSA() << "[" << vCS() << "] ) {\n";
 380                         TO_STATE_ACTION_SWITCH();
 381                         SWITCH_DEFAULT() <<
 382                         "       }\n"
 383                         "\n";
 384         }
 385
 386         if ( redFsm->errState != 0 ) {
 387                 outLabelUsed = true;
 388                 out <<
 389                         "       if ( " << vCS() << " == " << redFsm->errState->id << " )\n"
 390                         "               goto _out;\n";
 391         }
 392
 393         if ( !noEnd ) {
 394                 out <<
 395                         "       if ( ++" << P() << " != " << PE() << " )\n"
 396                         "               goto _resume;\n";
 397         }
 398         else {
 399                 out <<
 400                         "       " << P() << " += 1;\n"
 401                         "       goto _resume;\n";
 402         }
 403
 404         if ( testEofUsed )
 405                 out << "        _test_eof: {}\n";
 406
 407         if ( redFsm->anyEofTrans() || redFsm->anyEofActions() ) {
 408                 out <<
 409                         "       if ( " << P() << " == " << vEOF() << " )\n"
 410                         "       {\n";
 411
 412                 if ( redFsm->anyEofTrans() ) {
 413                         out <<
 414                                 "       if ( " << ET() << "[" << vCS() << "] > 0 ) {\n"
 415                                 "               _trans = " << CAST(transType) << " (" << ET() <<
 416                                         "[" << vCS() << "] - 1);\n"
 417                                 "               goto _eof_trans;\n"
 418                                 "       }\n";
 419                 }
 420
 421                 if ( redFsm->anyEofActions() ) {
 422                         out <<
 423                                 "       switch ( " << EA() << "[" << vCS() << "] ) {\n";
 424                                 EOF_ACTION_SWITCH();
 425                                 SWITCH_DEFAULT() <<
 426                                 "       }\n";
 427                 }
 428
 429                 out <<
 430                         "       }\n"
 431                         "\n";
 432         }
 433
 434         if ( outLabelUsed )
 435                 out << "        _out: {}\n";
 436
 437         out << "        }\n";
 438 }