javagen/tabcodegen.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 "javagen.h"
  25 #include "tabcodegen.h"
  26 #include "redfsm.h"
  27 #include "gendata.h"
  28
  29 /* Determine if we should use indicies or not. */
  30 void TabCodeGen::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->maxActionLoc) * 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->maxActionLoc) * totalIndex;
  51         }
  52
  53         /* If using indicies reduces the size, use them. */
  54         useIndicies = sizeWithInds < sizeWithoutInds;
  55 }
  56
  57 int TabCodeGen::TO_STATE_ACTION( RedStateAp *state )
  58 {
  59         int act = 0;
  60         if ( state->toStateAction != 0 )
  61                 act = state->toStateAction->location+1;
  62         return act;
  63 }
  64
  65 int TabCodeGen::FROM_STATE_ACTION( RedStateAp *state )
  66 {
  67         int act = 0;
  68         if ( state->fromStateAction != 0 )
  69                 act = state->fromStateAction->location+1;
  70         return act;
  71 }
  72
  73 int TabCodeGen::EOF_ACTION( RedStateAp *state )
  74 {
  75         int act = 0;
  76         if ( state->eofAction != 0 )
  77                 act = state->eofAction->location+1;
  78         return act;
  79 }
  80
  81
  82 int TabCodeGen::TRANS_ACTION( RedTransAp *trans )
  83 {
  84         /* If there are actions, emit them. Otherwise emit zero. */
  85         int act = 0;
  86         if ( trans->action != 0 )
  87                 act = trans->action->location+1;
  88         return act;
  89 }
  90
  91 std::ostream &TabCodeGen::TO_STATE_ACTION_SWITCH()
  92 {
  93         /* Walk the list of functions, printing the cases. */
  94         for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
  95                 /* Write out referenced actions. */
  96                 if ( act->numToStateRefs > 0 ) {
  97                         /* Write the case label, the action and the case break. */
  98                         out << "\tcase " << act->actionId << ":\n";
  99                         ACTION( out, act, 0, false );
 100                         out << "\tbreak;\n";
 101                 }
 102         }
 103
 104         genLineDirective( out );
 105         return out;
 106 }
 107
 108 std::ostream &TabCodeGen::FROM_STATE_ACTION_SWITCH()
 109 {
 110         /* Walk the list of functions, printing the cases. */
 111         for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
 112                 /* Write out referenced actions. */
 113                 if ( act->numFromStateRefs > 0 ) {
 114                         /* Write the case label, the action and the case break. */
 115                         out << "\tcase " << act->actionId << ":\n";
 116                         ACTION( out, act, 0, false );
 117                         out << "\tbreak;\n";
 118                 }
 119         }
 120
 121         genLineDirective( out );
 122         return out;
 123 }
 124
 125 std::ostream &TabCodeGen::EOF_ACTION_SWITCH()
 126 {
 127         /* Walk the list of functions, printing the cases. */
 128         for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
 129                 /* Write out referenced actions. */
 130                 if ( act->numEofRefs > 0 ) {
 131                         /* Write the case label, the action and the case break. */
 132                         out << "\tcase " << act->actionId << ":\n";
 133                         ACTION( out, act, 0, true );
 134                         out << "\tbreak;\n";
 135                 }
 136         }
 137
 138         genLineDirective( out );
 139         return out;
 140 }
 141
 142
 143 std::ostream &TabCodeGen::ACTION_SWITCH()
 144 {
 145         /* Walk the list of functions, printing the cases. */
 146         for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
 147                 /* Write out referenced actions. */
 148                 if ( act->numTransRefs > 0 ) {
 149                         /* Write the case label, the action and the case break. */
 150                         out << "\tcase " << act->actionId << ":\n";
 151                         ACTION( out, act, 0, false );
 152                         out << "\tbreak;\n";
 153                 }
 154         }
 155
 156         genLineDirective( out );
 157         return out;
 158 }
 159
 160 std::ostream &TabCodeGen::COND_OFFSETS()
 161 {
 162         START_ARRAY_LINE();
 163         int totalStateNum = 0, curKeyOffset = 0;
 164         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 165                 /* Write the key offset. */
 166                 ARRAY_ITEM( curKeyOffset, ++totalStateNum, st.last() );
 167
 168                 /* Move the key offset ahead. */
 169                 curKeyOffset += st->stateCondList.length();
 170         }
 171         END_ARRAY_LINE();
 172         return out;
 173 }
 174
 175 std::ostream &TabCodeGen::KEY_OFFSETS()
 176 {
 177         START_ARRAY_LINE();
 178         int totalStateNum = 0, curKeyOffset = 0;
 179         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 180                 /* Write the key offset. */
 181                 ARRAY_ITEM( curKeyOffset, ++totalStateNum, st.last() );
 182
 183                 /* Move the key offset ahead. */
 184                 curKeyOffset += st->outSingle.length() + st->outRange.length()*2;
 185         }
 186         END_ARRAY_LINE();
 187         return out;
 188 }
 189
 190
 191 std::ostream &TabCodeGen::INDEX_OFFSETS()
 192 {
 193         START_ARRAY_LINE();
 194         int totalStateNum = 0, curIndOffset = 0;
 195         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 196                 /* Write the index offset. */
 197                 ARRAY_ITEM( curIndOffset, ++totalStateNum, st.last() );
 198
 199                 /* Move the index offset ahead. */
 200                 curIndOffset += st->outSingle.length() + st->outRange.length();
 201                 if ( st->defTrans != 0 )
 202                         curIndOffset += 1;
 203         }
 204         END_ARRAY_LINE();
 205         return out;
 206 }
 207
 208 std::ostream &TabCodeGen::COND_LENS()
 209 {
 210         START_ARRAY_LINE();
 211         int totalStateNum = 0;
 212         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 213                 /* Write singles length. */
 214                 ARRAY_ITEM( st->stateCondList.length(), ++totalStateNum, st.last() );
 215         }
 216         END_ARRAY_LINE();
 217         return out;
 218 }
 219
 220
 221 std::ostream &TabCodeGen::SINGLE_LENS()
 222 {
 223         START_ARRAY_LINE();
 224         int totalStateNum = 0;
 225         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 226                 /* Write singles length. */
 227                 ARRAY_ITEM( st->outSingle.length(), ++totalStateNum, st.last() );
 228         }
 229         END_ARRAY_LINE();
 230         return out;
 231 }
 232
 233 std::ostream &TabCodeGen::RANGE_LENS()
 234 {
 235         START_ARRAY_LINE();
 236         int totalStateNum = 0;
 237         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 238                 /* Emit length of range index. */
 239                 ARRAY_ITEM( st->outRange.length(), ++totalStateNum, st.last() );
 240         }
 241         END_ARRAY_LINE();
 242         return out;
 243 }
 244
 245 std::ostream &TabCodeGen::TO_STATE_ACTIONS()
 246 {
 247         START_ARRAY_LINE();
 248         int totalStateNum = 0;
 249         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 250                 /* Write any eof action. */
 251                 ARRAY_ITEM( TO_STATE_ACTION(st), ++totalStateNum, st.last() );
 252         }
 253         END_ARRAY_LINE();
 254         return out;
 255 }
 256
 257 std::ostream &TabCodeGen::FROM_STATE_ACTIONS()
 258 {
 259         START_ARRAY_LINE();
 260         int totalStateNum = 0;
 261         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 262                 /* Write any eof action. */
 263                 ARRAY_ITEM( FROM_STATE_ACTION(st), ++totalStateNum, st.last() );
 264         }
 265         END_ARRAY_LINE();
 266         return out;
 267 }
 268
 269 std::ostream &TabCodeGen::EOF_ACTIONS()
 270 {
 271         START_ARRAY_LINE();
 272         int totalStateNum = 0;
 273         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 274                 /* Write any eof action. */
 275                 ARRAY_ITEM( EOF_ACTION(st), ++totalStateNum, st.last() );
 276         }
 277         END_ARRAY_LINE();
 278         return out;
 279 }
 280
 281 std::ostream &TabCodeGen::COND_KEYS()
 282 {
 283         START_ARRAY_LINE();
 284         int totalTrans = 0;
 285         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 286                 /* Loop the state's transitions. */
 287                 for ( StateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
 288                         /* Lower key. */
 289                         ARRAY_ITEM( KEY( sc->lowKey ), ++totalTrans, false );
 290                         ARRAY_ITEM( KEY( sc->highKey ), ++totalTrans, false );
 291                 }
 292         }
 293
 294         /* Output one last number so we don't have to figure out when the last
 295          * entry is and avoid writing a comma. */
 296         ARRAY_ITEM( 0, ++totalTrans, true );
 297         END_ARRAY_LINE();
 298         return out;
 299 }
 300
 301 std::ostream &TabCodeGen::COND_SPACES()
 302 {
 303         START_ARRAY_LINE();
 304         int totalTrans = 0;
 305         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 306                 /* Loop the state's transitions. */
 307                 for ( StateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
 308                         /* Cond Space id. */
 309                         ARRAY_ITEM( KEY( sc->condSpace->condSpaceId ), ++totalTrans, false );
 310                 }
 311         }
 312
 313         /* Output one last number so we don't have to figure out when the last
 314          * entry is and avoid writing a comma. */
 315         ARRAY_ITEM( 0, ++totalTrans, true );
 316         END_ARRAY_LINE();
 317         return out;
 318 }
 319
 320 std::ostream &TabCodeGen::KEYS()
 321 {
 322         START_ARRAY_LINE();
 323         int totalTrans = 0;
 324         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 325                 /* Loop the singles. */
 326                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 327                         ARRAY_ITEM( KEY( stel->lowKey ), ++totalTrans, false );
 328                 }
 329
 330                 /* Loop the state's transitions. */
 331                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 332                         /* Lower key. */
 333                         ARRAY_ITEM( KEY( rtel->lowKey ), ++totalTrans, false );
 334
 335                         /* Upper key. */
 336                         ARRAY_ITEM( KEY( rtel->highKey ), ++totalTrans, false );
 337                 }
 338         }
 339
 340         /* Output one last number so we don't have to figure out when the last
 341          * entry is and avoid writing a comma. */
 342         ARRAY_ITEM( 0, ++totalTrans, true );
 343         END_ARRAY_LINE();
 344         return out;
 345 }
 346
 347 std::ostream &TabCodeGen::INDICIES()
 348 {
 349         int totalTrans = 0;
 350         START_ARRAY_LINE();
 351         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 352                 /* Walk the singles. */
 353                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 354                         ARRAY_ITEM( KEY( stel->value->id ), ++totalTrans, false );
 355                 }
 356
 357                 /* Walk the ranges. */
 358                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 359                         ARRAY_ITEM( KEY( rtel->value->id ), ++totalTrans, false );
 360                 }
 361
 362                 /* The state's default index goes next. */
 363                 if ( st->defTrans != 0 ) {
 364                         ARRAY_ITEM( KEY( st->defTrans->id ), ++totalTrans, false );
 365                 }
 366         }
 367
 368         /* Output one last number so we don't have to figure out when the last
 369          * entry is and avoid writing a comma. */
 370         ARRAY_ITEM( 0, ++totalTrans, true );
 371         END_ARRAY_LINE();
 372         return out;
 373 }
 374
 375 std::ostream &TabCodeGen::TRANS_TARGS()
 376 {
 377         int totalTrans = 0;
 378         START_ARRAY_LINE();
 379         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 380                 /* Walk the singles. */
 381                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 382                         RedTransAp *trans = stel->value;
 383                         ARRAY_ITEM( KEY( trans->targ->id ), ++totalTrans, false );
 384                 }
 385
 386                 /* Walk the ranges. */
 387                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 388                         RedTransAp *trans = rtel->value;
 389                         ARRAY_ITEM( KEY( trans->targ->id ), ++totalTrans, false );
 390                 }
 391
 392                 /* The state's default target state. */
 393                 if ( st->defTrans != 0 ) {
 394                         RedTransAp *trans = st->defTrans;
 395                         ARRAY_ITEM( KEY( trans->targ->id ), ++totalTrans, false );
 396                 }
 397         }
 398
 399         /* Output one last number so we don't have to figure out when the last
 400          * entry is and avoid writing a comma. */
 401         ARRAY_ITEM( 0, ++totalTrans, true );
 402         END_ARRAY_LINE();
 403         return out;
 404 }
 405
 406
 407 std::ostream &TabCodeGen::TRANS_ACTIONS()
 408 {
 409         int totalTrans = 0;
 410         START_ARRAY_LINE();
 411         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 412                 /* Walk the singles. */
 413                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 414                         RedTransAp *trans = stel->value;
 415                         ARRAY_ITEM( TRANS_ACTION( trans ), ++totalTrans, false );
 416                 }
 417
 418                 /* Walk the ranges. */
 419                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 420                         RedTransAp *trans = rtel->value;
 421                         ARRAY_ITEM( TRANS_ACTION( trans ), ++totalTrans, false );
 422                 }
 423
 424                 /* The state's default index goes next. */
 425                 if ( st->defTrans != 0 ) {
 426                         RedTransAp *trans = st->defTrans;
 427                         ARRAY_ITEM( TRANS_ACTION( trans ), ++totalTrans, false );
 428                 }
 429         }
 430
 431         /* Output one last number so we don't have to figure out when the last
 432          * entry is and avoid writing a comma. */
 433         ARRAY_ITEM( 0, ++totalTrans, true );
 434         END_ARRAY_LINE();
 435         return out;
 436 }
 437
 438 std::ostream &TabCodeGen::TRANS_TARGS_WI()
 439 {
 440         /* Transitions must be written ordered by their id. */
 441         RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
 442         for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
 443                 transPtrs[trans->id] = trans;
 444
 445         /* Keep a count of the num of items in the array written. */
 446         START_ARRAY_LINE();
 447         int totalStates = 0;
 448         for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
 449                 /* Write out the target state. */
 450                 RedTransAp *trans = transPtrs[t];
 451                 ARRAY_ITEM( trans->targ->id, ++totalStates, ( t >= redFsm->transSet.length()-1 ) );
 452         }
 453         END_ARRAY_LINE();
 454         delete[] transPtrs;
 455         return out;
 456 }
 457
 458
 459 std::ostream &TabCodeGen::TRANS_ACTIONS_WI()
 460 {
 461         /* Transitions must be written ordered by their id. */
 462         RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
 463         for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
 464                 transPtrs[trans->id] = trans;
 465
 466         /* Keep a count of the num of items in the array written. */
 467         START_ARRAY_LINE();
 468         int totalAct = 0;
 469         for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
 470                 /* Write the function for the transition. */
 471                 RedTransAp *trans = transPtrs[t];
 472                 ARRAY_ITEM( TRANS_ACTION( trans ), ++totalAct, ( t >= redFsm->transSet.length()-1 ) );
 473         }
 474         END_ARRAY_LINE();
 475         delete[] transPtrs;
 476         return out;
 477 }
 478
 479 void TabCodeGen::LOCATE_TRANS()
 480 {
 481         out <<
 482                 "       _keys = " << ARR_OFF( K(), KO() + "[" + CS() + "]" ) << ";\n"
 483                 "       _trans = " << IO() << "[" << CS() << "];\n"
 484                 "\n"
 485                 "       _klen = " << SL() << "[" << CS() << "];\n"
 486                 "       if ( _klen > 0 ) {\n"
 487                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_lower = _keys;\n"
 488                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_mid;\n"
 489                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_upper = _keys + _klen - 1;\n"
 490                 "               while (1) {\n"
 491                 "                       if ( _upper < _lower )\n"
 492                 "                               break;\n"
 493                 "\n"
 494                 "                       _mid = _lower + ((_upper-_lower) >> 1);\n"
 495                 "                       if ( " << GET_WIDE_KEY() << " < *_mid )\n"
 496                 "                               _upper = _mid - 1;\n"
 497                 "                       else if ( " << GET_WIDE_KEY() << " > *_mid )\n"
 498                 "                               _lower = _mid + 1;\n"
 499                 "                       else {\n"
 500                 "                               _trans += (_mid - _keys);\n"
 501                 "                               goto _match;\n"
 502                 "                       }\n"
 503                 "               }\n"
 504                 "               _keys += _klen;\n"
 505                 "               _trans += _klen;\n"
 506                 "       }\n"
 507                 "\n"
 508                 "       _klen = " << RL() << "[" << CS() << "];\n"
 509                 "       if ( _klen > 0 ) {\n"
 510                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_lower = _keys;\n"
 511                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_mid;\n"
 512                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_upper = _keys + (_klen<<1) - 2;\n"
 513                 "               while (1) {\n"
 514                 "                       if ( _upper < _lower )\n"
 515                 "                               break;\n"
 516                 "\n"
 517                 "                       _mid = _lower + (((_upper-_lower) >> 1) & ~1);\n"
 518                 "                       if ( " << GET_WIDE_KEY() << " < _mid[0] )\n"
 519                 "                               _upper = _mid - 2;\n"
 520                 "                       else if ( " << GET_WIDE_KEY() << " > _mid[1] )\n"
 521                 "                               _lower = _mid + 2;\n"
 522                 "                       else {\n"
 523                 "                               _trans += ((_mid - _keys)>>1);\n"
 524                 "                               goto _match;\n"
 525                 "                       }\n"
 526                 "               }\n"
 527                 "               _trans += _klen;\n"
 528                 "       }\n"
 529                 "\n";
 530 }
 531
 532 void TabCodeGen::GOTO( ostream &ret, int gotoDest, bool inFinish )
 533 {
 534         ret << "{" << CS() << " = " << gotoDest << "; " <<
 535                         CTRL_FLOW() << "goto _again;}";
 536 }
 537
 538 void TabCodeGen::GOTO_EXPR( ostream &ret, InlineItem *ilItem, bool inFinish )
 539 {
 540         ret << "{" << CS() << " = (";
 541         INLINE_LIST( ret, ilItem->children, 0, inFinish );
 542         ret << "); " << CTRL_FLOW() << "goto _again;}";
 543 }
 544
 545 void TabCodeGen::CURS( ostream &ret, bool inFinish )
 546 {
 547         ret << "(_ps)";
 548 }
 549
 550 void TabCodeGen::TARGS( ostream &ret, bool inFinish, int targState )
 551 {
 552         ret << "(" << CS() << ")";
 553 }
 554
 555 void TabCodeGen::NEXT( ostream &ret, int nextDest, bool inFinish )
 556 {
 557         ret << CS() << " = " << nextDest << ";";
 558 }
 559
 560 void TabCodeGen::NEXT_EXPR( ostream &ret, InlineItem *ilItem, bool inFinish )
 561 {
 562         ret << CS() << " = (";
 563         INLINE_LIST( ret, ilItem->children, 0, inFinish );
 564         ret << ");";
 565 }
 566
 567 void TabCodeGen::CALL( ostream &ret, int callDest, int targState, bool inFinish )
 568 {
 569         ret << "{" << STACK() << "[" << TOP() << "++] = " << CS() << "; " << CS() << " = " <<
 570                         callDest << "; " << CTRL_FLOW() << "goto _again;}";
 571 }
 572
 573 void TabCodeGen::CALL_EXPR( ostream &ret, InlineItem *ilItem, int targState, bool inFinish )
 574 {
 575         ret << "{" << STACK() << "[" << TOP() << "++] = " << CS() << "; " << CS() << " = (";
 576         INLINE_LIST( ret, ilItem->children, targState, inFinish );
 577         ret << "); " << CTRL_FLOW() << "goto _again;}";
 578 }
 579
 580 void TabCodeGen::RET( ostream &ret, bool inFinish )
 581 {
 582         ret << "{" << CS() << " = " << STACK() << "[--" <<
 583                         TOP() << "]; " << CTRL_FLOW() <<  "goto _again;}";
 584 }
 585
 586 void TabCodeGen::BREAK( ostream &ret, int targState )
 587 {
 588         outLabelUsed = true;
 589         ret << CTRL_FLOW() << "goto _out;";
 590 }
 591
 592 void TabCodeGen::writeOutData()
 593 {
 594         /* If there are any transtion functions then output the array. If there
 595          * are none, don't bother emitting an empty array that won't be used. */
 596         if ( redFsm->anyActions() ) {
 597                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActArrItem), A() );
 598                 ACTIONS_ARRAY();
 599                 CLOSE_ARRAY() <<
 600                 "\n";
 601         }
 602
 603         if ( redFsm->anyConditions() ) {
 604                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondOffset), CO() );
 605                 COND_OFFSETS();
 606                 CLOSE_ARRAY() <<
 607                 "\n";
 608
 609                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondLen), CL() );
 610                 COND_LENS();
 611                 CLOSE_ARRAY() <<
 612                 "\n";
 613
 614                 OPEN_ARRAY( WIDE_ALPH_TYPE(), CK() );
 615                 COND_KEYS();
 616                 CLOSE_ARRAY() <<
 617                 "\n";
 618
 619                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondSpaceId), C() );
 620                 COND_SPACES();
 621                 CLOSE_ARRAY() <<
 622                 "\n";
 623         }
 624
 625         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxKeyOffset), KO() );
 626         KEY_OFFSETS();
 627         CLOSE_ARRAY() <<
 628         "\n";
 629
 630         OPEN_ARRAY( WIDE_ALPH_TYPE(), K() );
 631         KEYS();
 632         CLOSE_ARRAY() <<
 633         "\n";
 634
 635         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxSingleLen), SL() );
 636         SINGLE_LENS();
 637         CLOSE_ARRAY() <<
 638         "\n";
 639
 640         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxRangeLen), RL() );
 641         RANGE_LENS();
 642         CLOSE_ARRAY() <<
 643         "\n";
 644
 645         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset), IO() );
 646         INDEX_OFFSETS();
 647         CLOSE_ARRAY() <<
 648         "\n";
 649
 650         if ( useIndicies ) {
 651                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex), I() );
 652                 INDICIES();
 653                 CLOSE_ARRAY() <<
 654                 "\n";
 655
 656                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 657                 TRANS_TARGS_WI();
 658                 CLOSE_ARRAY() <<
 659                 "\n";
 660
 661                 if ( redFsm->anyActions() ) {
 662                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
 663                         TRANS_ACTIONS_WI();
 664                         CLOSE_ARRAY() <<
 665                         "\n";
 666                 }
 667         }
 668         else {
 669                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 670                 TRANS_TARGS();
 671                 CLOSE_ARRAY() <<
 672                 "\n";
 673
 674                 if ( redFsm->anyActions() ) {
 675                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
 676                         TRANS_ACTIONS();
 677                         CLOSE_ARRAY() <<
 678                         "\n";
 679                 }
 680         }
 681
 682         if ( redFsm->anyToStateActions() ) {
 683                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
 684                 TO_STATE_ACTIONS();
 685                 CLOSE_ARRAY() <<
 686                 "\n";
 687         }
 688
 689         if ( redFsm->anyFromStateActions() ) {
 690                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
 691                 FROM_STATE_ACTIONS();
 692                 CLOSE_ARRAY() <<
 693                 "\n";
 694         }
 695
 696         if ( redFsm->anyEofActions() ) {
 697                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), EA() );
 698                 EOF_ACTIONS();
 699                 CLOSE_ARRAY() <<
 700                 "\n";
 701         }
 702
 703         STATIC_VAR( "int", START() ) << " = " << START_STATE_ID() << ";\n"
 704         "\n";
 705
 706         if ( writeFirstFinal ) {
 707                 STATIC_VAR( "int" , FIRST_FINAL() ) << " = " << FIRST_FINAL_STATE() << ";\n"
 708                 "\n";
 709         }
 710
 711         if ( writeErr ) {
 712                 STATIC_VAR( "int", ERROR() ) << " = " << ERROR_STATE() << ";\n"
 713                 "\n";
 714         }
 715 }
 716
 717 void TabCodeGen::COND_TRANSLATE()
 718 {
 719         out <<
 720                 "       _widec = " << GET_KEY() << ";\n"
 721                 "       _klen = " << CL() << "[" << CS() << "];\n"
 722                 "       _keys = " << ARR_OFF( CK(), "(" + CO() + "[" + CS() + "]*2)" ) << ";\n"
 723                 "       if ( _klen > 0 ) {\n"
 724                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_lower = _keys;\n"
 725                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_mid;\n"
 726                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_upper = _keys + (_klen<<1) - 2;\n"
 727                 "               while (1) {\n"
 728                 "                       if ( _upper < _lower )\n"
 729                 "                               break;\n"
 730                 "\n"
 731                 "                       _mid = _lower + (((_upper-_lower) >> 1) & ~1);\n"
 732                 "                       if ( " << GET_WIDE_KEY() << " < _mid[0] )\n"
 733                 "                               _upper = _mid - 2;\n"
 734                 "                       else if ( " << GET_WIDE_KEY() << " > _mid[1] )\n"
 735                 "                               _lower = _mid + 2;\n"
 736                 "                       else {\n"
 737                 "                               switch ( " << C() << "[" << CO() << "[" << CS() << "]"
 738                                                         " + ((_mid - _keys)>>1)] ) {\n";
 739
 740         for ( CondSpaceList::Iter csi = condSpaceList; csi.lte(); csi++ ) {
 741                 CondSpace *condSpace = csi;
 742                 out << "        case " << condSpace->condSpaceId << ": {\n";
 743                 out << TABS(2) << "_widec = " << CAST(WIDE_ALPH_TYPE()) << "(" <<
 744                                 KEY(condSpace->baseKey) << " + (" << GET_KEY() <<
 745                                 " - " << KEY(keyOps->minKey) << "));\n";
 746
 747                 for ( CondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
 748                         out << TABS(2) << "if ( ";
 749                         CONDITION( out, *csi );
 750                         Size condValOffset = ((1 << csi.pos()) * keyOps->alphSize());
 751                         out << " ) _widec += " << condValOffset << ";\n";
 752                 }
 753
 754                 out <<
 755                         "               break;\n"
 756                         "       }\n";
 757         }
 758
 759         SWITCH_DEFAULT();
 760
 761         out <<
 762                 "                               }\n"
 763                 "                               break;\n"
 764                 "                       }\n"
 765                 "               }\n"
 766                 "       }\n"
 767                 "\n";
 768 }
 769
 770 void TabCodeGen::writeOutExec()
 771 {
 772         outLabelUsed = false;
 773
 774         out <<
 775                 "       {\n"
 776                 "       int _klen";
 777
 778         if ( redFsm->anyRegCurStateRef() )
 779                 out << ", _ps";
 780
 781         out <<
 782                 ";\n"
 783                 "       " << UINT() << " _trans;\n";
 784
 785         if ( redFsm->anyConditions() )
 786                 out << "        " << WIDE_ALPH_TYPE() << " _widec;\n";
 787
 788         if ( redFsm->anyToStateActions() || redFsm->anyRegActions()
 789                         || redFsm->anyFromStateActions() )
 790         {
 791                 out <<
 792                         "       " << PTR_CONST() << ARRAY_TYPE(redFsm->maxActArrItem) << POINTER() << "_acts;\n"
 793                         "       " << UINT() << " _nacts;\n";
 794         }
 795
 796         out <<
 797                 "       " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_keys;\n"
 798                 "\n";
 799
 800         if ( hasEnd ) {
 801                 outLabelUsed = true;
 802                 out <<
 803                         "       if ( " << P() << " == " << PE() << " )\n"
 804                         "               goto _out;\n";
 805         }
 806
 807         out << "_resume:\n";
 808
 809         if ( redFsm->errState != 0 ) {
 810                 outLabelUsed = true;
 811                 out <<
 812                         "       if ( " << CS() << " == " << redFsm->errState->id << " )\n"
 813                         "               goto _out;\n";
 814         }
 815
 816         if ( redFsm->anyFromStateActions() ) {
 817                 out <<
 818                         "       _acts = " << ARR_OFF( A(),  FSA() + "[" + CS() + "]" ) << ";\n"
 819                         "       _nacts = " << CAST(UINT()) << " *_acts++;\n"
 820                         "       while ( _nacts-- > 0 ) {\n"
 821                         "               switch ( *_acts++ ) {\n";
 822                         FROM_STATE_ACTION_SWITCH();
 823                         SWITCH_DEFAULT() <<
 824                         "               }\n"
 825                         "       }\n"
 826                         "\n";
 827         }
 828
 829         if ( redFsm->anyConditions() )
 830                 COND_TRANSLATE();
 831
 832         LOCATE_TRANS();
 833
 834         out << "_match:\n";
 835
 836         if ( redFsm->anyRegCurStateRef() )
 837                 out << "        _ps = " << CS() << ";\n";
 838
 839         if ( useIndicies )
 840                 out << "        _trans = " << I() << "[_trans];\n";
 841
 842         out <<
 843                 "       " << CS() << " = " << TT() << "[_trans];\n"
 844                 "\n";
 845
 846         if ( redFsm->anyRegActions() ) {
 847                 out <<
 848                         "       if ( " << TA() << "[_trans] == 0 )\n"
 849                         "               goto _again;\n"
 850                         "\n"
 851                         "       _acts = " << ARR_OFF( A(), TA() + "[_trans]" ) << ";\n"
 852                         "       _nacts = " << CAST(UINT()) << " *_acts++;\n"
 853                         "       while ( _nacts-- > 0 )\n        {\n"
 854                         "               switch ( *_acts++ )\n           {\n";
 855                         ACTION_SWITCH();
 856                         SWITCH_DEFAULT() <<
 857                         "               }\n"
 858                         "       }\n"
 859                         "\n";
 860         }
 861
 862         if ( redFsm->anyRegActions() || redFsm->anyActionGotos() ||
 863                         redFsm->anyActionCalls() || redFsm->anyActionRets() )
 864                 out << "_again:\n";
 865
 866         if ( redFsm->anyToStateActions() ) {
 867                 out <<
 868                         "       _acts = " << ARR_OFF( A(), TSA() + "[" + CS() + "]" ) << ";\n"
 869                         "       _nacts = " << CAST(UINT()) << " *_acts++;\n"
 870                         "       while ( _nacts-- > 0 ) {\n"
 871                         "               switch ( *_acts++ ) {\n";
 872                         TO_STATE_ACTION_SWITCH();
 873                         SWITCH_DEFAULT() <<
 874                         "               }\n"
 875                         "       }\n"
 876                         "\n";
 877         }
 878
 879         if ( hasEnd ) {
 880                 out <<
 881                         "       if ( ++" << P() << " != " << PE() << " )\n"
 882                         "               goto _resume;\n";
 883         }
 884         else {
 885                 out <<
 886                         "       " << P() << " += 1;\n"
 887                         "       goto _resume;\n";
 888         }
 889
 890         if ( outLabelUsed )
 891                 out << "        _out: {}\n";
 892
 893         out << "        }\n";
 894 }
 895
 896
 897 void TabCodeGen::writeOutEOF()
 898 {
 899         if ( redFsm->anyEofActions() ) {
 900                 out <<
 901                         "       {\n"
 902                         "       " << PTR_CONST() << ARRAY_TYPE(redFsm->maxActArrItem) << POINTER() << "_acts = " <<
 903                                         ARR_OFF( A(), EA() + "[" + CS() + "]" ) << ";\n"
 904                         "       " << UINT() << " _nacts = " << CAST(UINT()) << " *_acts++;\n"
 905                         "       while ( _nacts-- > 0 ) {\n"
 906                         "               switch ( *_acts++ ) {\n";
 907                         EOF_ACTION_SWITCH();
 908                         SWITCH_DEFAULT() <<
 909                         "               }\n"
 910                         "       }\n"
 911                         "       }\n"
 912                         "\n";
 913         }
 914 }