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