rlgen-cd/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 "rlgen-cd.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 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 = 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 = 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 = 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 = 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::EOF_TRANS()
 331 {
 332         out << "\t";
 333         int totalStateNum = 0;
 334         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 335                 /* Write any eof action. */
 336                 long trans = 0;
 337                 if ( st->eofTrans != 0 )
 338                         trans = st->eofTrans->id+1;
 339                 out << trans;
 340
 341                 if ( !st.last() ) {
 342                         out << ", ";
 343                         if ( ++totalStateNum % IALL == 0 )
 344                                 out << "\n\t";
 345                 }
 346         }
 347         out << "\n";
 348         return out;
 349 }
 350
 351
 352 std::ostream &TabCodeGen::COND_KEYS()
 353 {
 354         out << '\t';
 355         int totalTrans = 0;
 356         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 357                 /* Loop the state's transitions. */
 358                 for ( StateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
 359                         /* Lower key. */
 360                         out << KEY( sc->lowKey ) << ", ";
 361                         if ( ++totalTrans % IALL == 0 )
 362                                 out << "\n\t";
 363
 364                         /* Upper key. */
 365                         out << KEY( sc->highKey ) << ", ";
 366                         if ( ++totalTrans % IALL == 0 )
 367                                 out << "\n\t";
 368                 }
 369         }
 370
 371         /* Output one last number so we don't have to figure out when the last
 372          * entry is and avoid writing a comma. */
 373         out << 0 << "\n";
 374         return out;
 375 }
 376
 377 std::ostream &TabCodeGen::COND_SPACES()
 378 {
 379         out << '\t';
 380         int totalTrans = 0;
 381         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 382                 /* Loop the state's transitions. */
 383                 for ( StateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
 384                         /* Cond Space id. */
 385                         out << sc->condSpace->condSpaceId << ", ";
 386                         if ( ++totalTrans % IALL == 0 )
 387                                 out << "\n\t";
 388                 }
 389         }
 390
 391         /* Output one last number so we don't have to figure out when the last
 392          * entry is and avoid writing a comma. */
 393         out << 0 << "\n";
 394         return out;
 395 }
 396
 397 std::ostream &TabCodeGen::KEYS()
 398 {
 399         out << '\t';
 400         int totalTrans = 0;
 401         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 402                 /* Loop the singles. */
 403                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 404                         out << KEY( stel->lowKey ) << ", ";
 405                         if ( ++totalTrans % IALL == 0 )
 406                                 out << "\n\t";
 407                 }
 408
 409                 /* Loop the state's transitions. */
 410                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 411                         /* Lower key. */
 412                         out << KEY( rtel->lowKey ) << ", ";
 413                         if ( ++totalTrans % IALL == 0 )
 414                                 out << "\n\t";
 415
 416                         /* Upper key. */
 417                         out << KEY( rtel->highKey ) << ", ";
 418                         if ( ++totalTrans % IALL == 0 )
 419                                 out << "\n\t";
 420                 }
 421         }
 422
 423         /* Output one last number so we don't have to figure out when the last
 424          * entry is and avoid writing a comma. */
 425         out << 0 << "\n";
 426         return out;
 427 }
 428
 429 std::ostream &TabCodeGen::INDICIES()
 430 {
 431         int totalTrans = 0;
 432         out << '\t';
 433         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 434                 /* Walk the singles. */
 435                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 436                         out << stel->value->id << ", ";
 437                         if ( ++totalTrans % IALL == 0 )
 438                                 out << "\n\t";
 439                 }
 440
 441                 /* Walk the ranges. */
 442                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 443                         out << rtel->value->id << ", ";
 444                         if ( ++totalTrans % IALL == 0 )
 445                                 out << "\n\t";
 446                 }
 447
 448                 /* The state's default index goes next. */
 449                 if ( st->defTrans != 0 ) {
 450                         out << st->defTrans->id << ", ";
 451                         if ( ++totalTrans % IALL == 0 )
 452                                 out << "\n\t";
 453                 }
 454         }
 455
 456         /* Output one last number so we don't have to figure out when the last
 457          * entry is and avoid writing a comma. */
 458         out << 0 << "\n";
 459         return out;
 460 }
 461
 462 std::ostream &TabCodeGen::TRANS_TARGS()
 463 {
 464         int totalTrans = 0;
 465         out << '\t';
 466         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 467                 /* Walk the singles. */
 468                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 469                         RedTransAp *trans = stel->value;
 470                         out << trans->targ->id << ", ";
 471                         if ( ++totalTrans % IALL == 0 )
 472                                 out << "\n\t";
 473                 }
 474
 475                 /* Walk the ranges. */
 476                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 477                         RedTransAp *trans = rtel->value;
 478                         out << trans->targ->id << ", ";
 479                         if ( ++totalTrans % IALL == 0 )
 480                                 out << "\n\t";
 481                 }
 482
 483                 /* The state's default target state. */
 484                 if ( st->defTrans != 0 ) {
 485                         RedTransAp *trans = st->defTrans;
 486                         out << trans->targ->id << ", ";
 487                         if ( ++totalTrans % IALL == 0 )
 488                                 out << "\n\t";
 489                 }
 490         }
 491
 492         /* Output one last number so we don't have to figure out when the last
 493          * entry is and avoid writing a comma. */
 494         out << 0 << "\n";
 495         return out;
 496 }
 497
 498
 499 std::ostream &TabCodeGen::TRANS_ACTIONS()
 500 {
 501         int totalTrans = 0;
 502         out << '\t';
 503         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 504                 /* Walk the singles. */
 505                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 506                         RedTransAp *trans = stel->value;
 507                         TRANS_ACTION( trans ) << ", ";
 508                         if ( ++totalTrans % IALL == 0 )
 509                                 out << "\n\t";
 510                 }
 511
 512                 /* Walk the ranges. */
 513                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 514                         RedTransAp *trans = rtel->value;
 515                         TRANS_ACTION( trans ) << ", ";
 516                         if ( ++totalTrans % IALL == 0 )
 517                                 out << "\n\t";
 518                 }
 519
 520                 /* The state's default index goes next. */
 521                 if ( st->defTrans != 0 ) {
 522                         RedTransAp *trans = st->defTrans;
 523                         TRANS_ACTION( trans ) << ", ";
 524                         if ( ++totalTrans % IALL == 0 )
 525                                 out << "\n\t";
 526                 }
 527         }
 528
 529         /* Output one last number so we don't have to figure out when the last
 530          * entry is and avoid writing a comma. */
 531         out << 0 << "\n";
 532         return out;
 533 }
 534
 535 std::ostream &TabCodeGen::TRANS_TARGS_WI()
 536 {
 537         /* Transitions must be written ordered by their id. */
 538         RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
 539         for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
 540                 transPtrs[trans->id] = trans;
 541
 542         /* Keep a count of the num of items in the array written. */
 543         out << '\t';
 544         int totalStates = 0;
 545         for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
 546                 /* Write out the target state. */
 547                 RedTransAp *trans = transPtrs[t];
 548                 out << trans->targ->id;
 549                 if ( t < redFsm->transSet.length()-1 ) {
 550                         out << ", ";
 551                         if ( ++totalStates % IALL == 0 )
 552                                 out << "\n\t";
 553                 }
 554         }
 555         out << "\n";
 556         delete[] transPtrs;
 557         return out;
 558 }
 559
 560
 561 std::ostream &TabCodeGen::TRANS_ACTIONS_WI()
 562 {
 563         /* Transitions must be written ordered by their id. */
 564         RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
 565         for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
 566                 transPtrs[trans->id] = trans;
 567
 568         /* Keep a count of the num of items in the array written. */
 569         out << '\t';
 570         int totalAct = 0;
 571         for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
 572                 /* Write the function for the transition. */
 573                 RedTransAp *trans = transPtrs[t];
 574                 TRANS_ACTION( trans );
 575                 if ( t < redFsm->transSet.length()-1 ) {
 576                         out << ", ";
 577                         if ( ++totalAct % IALL == 0 )
 578                                 out << "\n\t";
 579                 }
 580         }
 581         out << "\n";
 582         delete[] transPtrs;
 583         return out;
 584 }
 585
 586 void TabCodeGen::LOCATE_TRANS()
 587 {
 588         out <<
 589                 "       _keys = " << ARR_OFF( K(), KO() + "[" + CS() + "]" ) << ";\n"
 590                 "       _trans = " << IO() << "[" << CS() << "];\n"
 591                 "\n"
 592                 "       _klen = " << SL() << "[" << CS() << "];\n"
 593                 "       if ( _klen > 0 ) {\n"
 594                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_lower = _keys;\n"
 595                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_mid;\n"
 596                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_upper = _keys + _klen - 1;\n"
 597                 "               while (1) {\n"
 598                 "                       if ( _upper < _lower )\n"
 599                 "                               break;\n"
 600                 "\n"
 601                 "                       _mid = _lower + ((_upper-_lower) >> 1);\n"
 602                 "                       if ( " << GET_WIDE_KEY() << " < *_mid )\n"
 603                 "                               _upper = _mid - 1;\n"
 604                 "                       else if ( " << GET_WIDE_KEY() << " > *_mid )\n"
 605                 "                               _lower = _mid + 1;\n"
 606                 "                       else {\n"
 607                 "                               _trans += (_mid - _keys);\n"
 608                 "                               goto _match;\n"
 609                 "                       }\n"
 610                 "               }\n"
 611                 "               _keys += _klen;\n"
 612                 "               _trans += _klen;\n"
 613                 "       }\n"
 614                 "\n"
 615                 "       _klen = " << RL() << "[" << CS() << "];\n"
 616                 "       if ( _klen > 0 ) {\n"
 617                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_lower = _keys;\n"
 618                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_mid;\n"
 619                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_upper = _keys + (_klen<<1) - 2;\n"
 620                 "               while (1) {\n"
 621                 "                       if ( _upper < _lower )\n"
 622                 "                               break;\n"
 623                 "\n"
 624                 "                       _mid = _lower + (((_upper-_lower) >> 1) & ~1);\n"
 625                 "                       if ( " << GET_WIDE_KEY() << " < _mid[0] )\n"
 626                 "                               _upper = _mid - 2;\n"
 627                 "                       else if ( " << GET_WIDE_KEY() << " > _mid[1] )\n"
 628                 "                               _lower = _mid + 2;\n"
 629                 "                       else {\n"
 630                 "                               _trans += ((_mid - _keys)>>1);\n"
 631                 "                               goto _match;\n"
 632                 "                       }\n"
 633                 "               }\n"
 634                 "               _trans += _klen;\n"
 635                 "       }\n"
 636                 "\n";
 637 }
 638
 639 void TabCodeGen::GOTO( ostream &ret, int gotoDest, bool inFinish )
 640 {
 641         ret << "{" << CS() << " = " << gotoDest << "; " <<
 642                         CTRL_FLOW() << "goto _again;}";
 643 }
 644
 645 void TabCodeGen::GOTO_EXPR( ostream &ret, InlineItem *ilItem, bool inFinish )
 646 {
 647         ret << "{" << CS() << " = (";
 648         INLINE_LIST( ret, ilItem->children, 0, inFinish );
 649         ret << "); " << CTRL_FLOW() << "goto _again;}";
 650 }
 651
 652 void TabCodeGen::CURS( ostream &ret, bool inFinish )
 653 {
 654         ret << "(_ps)";
 655 }
 656
 657 void TabCodeGen::TARGS( ostream &ret, bool inFinish, int targState )
 658 {
 659         ret << "(" << CS() << ")";
 660 }
 661
 662 void TabCodeGen::NEXT( ostream &ret, int nextDest, bool inFinish )
 663 {
 664         ret << CS() << " = " << nextDest << ";";
 665 }
 666
 667 void TabCodeGen::NEXT_EXPR( ostream &ret, InlineItem *ilItem, bool inFinish )
 668 {
 669         ret << CS() << " = (";
 670         INLINE_LIST( ret, ilItem->children, 0, inFinish );
 671         ret << ");";
 672 }
 673
 674 void TabCodeGen::CALL( ostream &ret, int callDest, int targState, bool inFinish )
 675 {
 676         if ( prePushExpr != 0 ) {
 677                 ret << "{";
 678                 INLINE_LIST( ret, prePushExpr, 0, false );
 679         }
 680
 681         ret << "{" << STACK() << "[" << TOP() << "++] = " << CS() << "; " << CS() << " = " <<
 682                         callDest << "; " << CTRL_FLOW() << "goto _again;}";
 683
 684         if ( prePushExpr != 0 )
 685                 ret << "}";
 686 }
 687
 688 void TabCodeGen::CALL_EXPR( ostream &ret, InlineItem *ilItem, int targState, bool inFinish )
 689 {
 690         if ( prePushExpr != 0 ) {
 691                 ret << "{";
 692                 INLINE_LIST( ret, prePushExpr, 0, false );
 693         }
 694
 695         ret << "{" << STACK() << "[" << TOP() << "++] = " << CS() << "; " << CS() << " = (";
 696         INLINE_LIST( ret, ilItem->children, targState, inFinish );
 697         ret << "); " << CTRL_FLOW() << "goto _again;}";
 698
 699         if ( prePushExpr != 0 )
 700                 ret << "}";
 701 }
 702
 703 void TabCodeGen::RET( ostream &ret, bool inFinish )
 704 {
 705         ret << "{" << CS() << " = " << STACK() << "[--" <<
 706                         TOP() << "]; ";
 707
 708         if ( postPopExpr != 0 ) {
 709                 ret << "{";
 710                 INLINE_LIST( ret, postPopExpr, 0, false );
 711                 ret << "}";
 712         }
 713
 714         ret << CTRL_FLOW() <<  "goto _again;}";
 715 }
 716
 717 void TabCodeGen::BREAK( ostream &ret, int targState )
 718 {
 719         outLabelUsed = true;
 720         ret << CTRL_FLOW() << "goto _out;";
 721 }
 722
 723 void TabCodeGen::writeData()
 724 {
 725         /* If there are any transtion functions then output the array. If there
 726          * are none, don't bother emitting an empty array that won't be used. */
 727         if ( redFsm->anyActions() ) {
 728                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActArrItem), A() );
 729                 ACTIONS_ARRAY();
 730                 CLOSE_ARRAY() <<
 731                 "\n";
 732         }
 733
 734         if ( redFsm->anyConditions() ) {
 735                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondOffset), CO() );
 736                 COND_OFFSETS();
 737                 CLOSE_ARRAY() <<
 738                 "\n";
 739
 740                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondLen), CL() );
 741                 COND_LENS();
 742                 CLOSE_ARRAY() <<
 743                 "\n";
 744
 745                 OPEN_ARRAY( WIDE_ALPH_TYPE(), CK() );
 746                 COND_KEYS();
 747                 CLOSE_ARRAY() <<
 748                 "\n";
 749
 750                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondSpaceId), C() );
 751                 COND_SPACES();
 752                 CLOSE_ARRAY() <<
 753                 "\n";
 754         }
 755
 756         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxKeyOffset), KO() );
 757         KEY_OFFSETS();
 758         CLOSE_ARRAY() <<
 759         "\n";
 760
 761         OPEN_ARRAY( WIDE_ALPH_TYPE(), K() );
 762         KEYS();
 763         CLOSE_ARRAY() <<
 764         "\n";
 765
 766         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxSingleLen), SL() );
 767         SINGLE_LENS();
 768         CLOSE_ARRAY() <<
 769         "\n";
 770
 771         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxRangeLen), RL() );
 772         RANGE_LENS();
 773         CLOSE_ARRAY() <<
 774         "\n";
 775
 776         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset), IO() );
 777         INDEX_OFFSETS();
 778         CLOSE_ARRAY() <<
 779         "\n";
 780
 781         if ( useIndicies ) {
 782                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex), I() );
 783                 INDICIES();
 784                 CLOSE_ARRAY() <<
 785                 "\n";
 786
 787                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 788                 TRANS_TARGS_WI();
 789                 CLOSE_ARRAY() <<
 790                 "\n";
 791
 792                 if ( redFsm->anyActions() ) {
 793                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
 794                         TRANS_ACTIONS_WI();
 795                         CLOSE_ARRAY() <<
 796                         "\n";
 797                 }
 798         }
 799         else {
 800                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 801                 TRANS_TARGS();
 802                 CLOSE_ARRAY() <<
 803                 "\n";
 804
 805                 if ( redFsm->anyActions() ) {
 806                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
 807                         TRANS_ACTIONS();
 808                         CLOSE_ARRAY() <<
 809                         "\n";
 810                 }
 811         }
 812
 813         if ( redFsm->anyToStateActions() ) {
 814                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
 815                 TO_STATE_ACTIONS();
 816                 CLOSE_ARRAY() <<
 817                 "\n";
 818         }
 819
 820         if ( redFsm->anyFromStateActions() ) {
 821                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
 822                 FROM_STATE_ACTIONS();
 823                 CLOSE_ARRAY() <<
 824                 "\n";
 825         }
 826
 827         if ( redFsm->anyEofActions() ) {
 828                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), EA() );
 829                 EOF_ACTIONS();
 830                 CLOSE_ARRAY() <<
 831                 "\n";
 832         }
 833
 834         if ( redFsm->anyEofTrans() ) {
 835                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex+1), ET() );
 836                 EOF_TRANS();
 837                 CLOSE_ARRAY() <<
 838                 "\n";
 839         }
 840
 841         STATE_IDS();
 842 }
 843
 844 void TabCodeGen::COND_TRANSLATE()
 845 {
 846         out <<
 847                 "       _widec = " << GET_KEY() << ";\n"
 848                 "       _klen = " << CL() << "[" << CS() << "];\n"
 849                 "       _keys = " << ARR_OFF( CK(), "(" + CO() + "[" + CS() + "]*2)" ) << ";\n"
 850                 "       if ( _klen > 0 ) {\n"
 851                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_lower = _keys;\n"
 852                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_mid;\n"
 853                 "               " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_upper = _keys + (_klen<<1) - 2;\n"
 854                 "               while (1) {\n"
 855                 "                       if ( _upper < _lower )\n"
 856                 "                               break;\n"
 857                 "\n"
 858                 "                       _mid = _lower + (((_upper-_lower) >> 1) & ~1);\n"
 859                 "                       if ( " << GET_WIDE_KEY() << " < _mid[0] )\n"
 860                 "                               _upper = _mid - 2;\n"
 861                 "                       else if ( " << GET_WIDE_KEY() << " > _mid[1] )\n"
 862                 "                               _lower = _mid + 2;\n"
 863                 "                       else {\n"
 864                 "                               switch ( " << C() << "[" << CO() << "[" << CS() << "]"
 865                                                         " + ((_mid - _keys)>>1)] ) {\n";
 866
 867         for ( CondSpaceList::Iter csi = condSpaceList; csi.lte(); csi++ ) {
 868                 CondSpace *condSpace = csi;
 869                 out << "        case " << condSpace->condSpaceId << ": {\n";
 870                 out << TABS(2) << "_widec = " << CAST(WIDE_ALPH_TYPE()) << "(" <<
 871                                 KEY(condSpace->baseKey) << " + (" << GET_KEY() <<
 872                                 " - " << KEY(keyOps->minKey) << "));\n";
 873
 874                 for ( CondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
 875                         out << TABS(2) << "if ( ";
 876                         CONDITION( out, *csi );
 877                         Size condValOffset = ((1 << csi.pos()) * keyOps->alphSize());
 878                         out << " ) _widec += " << condValOffset << ";\n";
 879                 }
 880
 881                 out <<
 882                         "               break;\n"
 883                         "       }\n";
 884         }
 885
 886         SWITCH_DEFAULT();
 887
 888         out <<
 889                 "                               }\n"
 890                 "                               break;\n"
 891                 "                       }\n"
 892                 "               }\n"
 893                 "       }\n"
 894                 "\n";
 895 }
 896
 897 void TabCodeGen::writeExec()
 898 {
 899         testEofUsed = false;
 900         outLabelUsed = false;
 901
 902         out <<
 903                 "       {\n"
 904                 "       int _klen";
 905
 906         if ( redFsm->anyRegCurStateRef() )
 907                 out << ", _ps";
 908
 909         out <<
 910                 ";\n"
 911                 "       " << UINT() << " _trans;\n";
 912
 913         if ( redFsm->anyConditions() )
 914                 out << "        " << WIDE_ALPH_TYPE() << " _widec;\n";
 915
 916         if ( redFsm->anyToStateActions() || redFsm->anyRegActions()
 917                         || redFsm->anyFromStateActions() )
 918         {
 919                 out <<
 920                         "       " << PTR_CONST() << ARRAY_TYPE(redFsm->maxActArrItem) <<
 921                                         POINTER() << "_acts;\n"
 922                         "       " << UINT() << " _nacts;\n";
 923         }
 924
 925         out <<
 926                 "       " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_keys;\n"
 927                 "\n";
 928
 929         if ( hasEnd ) {
 930                 testEofUsed = true;
 931                 out <<
 932                         "       if ( " << P() << " == " << PE() << " )\n"
 933                         "               goto _test_eof;\n";
 934         }
 935
 936         if ( redFsm->errState != 0 ) {
 937                 outLabelUsed = true;
 938                 out <<
 939                         "       if ( " << CS() << " == " << redFsm->errState->id << " )\n"
 940                         "               goto _out;\n";
 941         }
 942
 943         out << "_resume:\n";
 944
 945         if ( redFsm->anyFromStateActions() ) {
 946                 out <<
 947                         "       _acts = " << ARR_OFF( A(),  FSA() + "[" + CS() + "]" ) << ";\n"
 948                         "       _nacts = " << CAST(UINT()) << " *_acts++;\n"
 949                         "       while ( _nacts-- > 0 ) {\n"
 950                         "               switch ( *_acts++ ) {\n";
 951                         FROM_STATE_ACTION_SWITCH();
 952                         SWITCH_DEFAULT() <<
 953                         "               }\n"
 954                         "       }\n"
 955                         "\n";
 956         }
 957
 958         if ( redFsm->anyConditions() )
 959                 COND_TRANSLATE();
 960
 961         LOCATE_TRANS();
 962
 963         out << "_match:\n";
 964
 965         if ( useIndicies )
 966                 out << "        _trans = " << I() << "[_trans];\n";
 967
 968         if ( redFsm->anyEofTrans() )
 969                 out << "_eof_trans:\n";
 970
 971         if ( redFsm->anyRegCurStateRef() )
 972                 out << "        _ps = " << CS() << ";\n";
 973
 974         out <<
 975                 "       " << CS() << " = " << TT() << "[_trans];\n"
 976                 "\n";
 977
 978         if ( redFsm->anyRegActions() ) {
 979                 out <<
 980                         "       if ( " << TA() << "[_trans] == 0 )\n"
 981                         "               goto _again;\n"
 982                         "\n"
 983                         "       _acts = " << ARR_OFF( A(), TA() + "[_trans]" ) << ";\n"
 984                         "       _nacts = " << CAST(UINT()) << " *_acts++;\n"
 985                         "       while ( _nacts-- > 0 )\n        {\n"
 986                         "               switch ( *_acts++ )\n           {\n";
 987                         ACTION_SWITCH();
 988                         SWITCH_DEFAULT() <<
 989                         "               }\n"
 990                         "       }\n"
 991                         "\n";
 992         }
 993
 994         if ( redFsm->anyRegActions() || redFsm->anyActionGotos() ||
 995                         redFsm->anyActionCalls() || redFsm->anyActionRets() )
 996                 out << "_again:\n";
 997
 998         if ( redFsm->anyToStateActions() ) {
 999                 out <<
1000                         "       _acts = " << ARR_OFF( A(), TSA() + "[" + CS() + "]" ) << ";\n"
1001                         "       _nacts = " << CAST(UINT()) << " *_acts++;\n"
1002                         "       while ( _nacts-- > 0 ) {\n"
1003                         "               switch ( *_acts++ ) {\n";
1004                         TO_STATE_ACTION_SWITCH();
1005                         SWITCH_DEFAULT() <<
1006                         "               }\n"
1007                         "       }\n"
1008                         "\n";
1009         }
1010
1011         if ( redFsm->errState != 0 ) {
1012                 outLabelUsed = true;
1013                 out <<
1014                         "       if ( " << CS() << " == " << redFsm->errState->id << " )\n"
1015                         "               goto _out;\n";
1016         }
1017
1018         if ( hasEnd ) {
1019                 out <<
1020                         "       if ( ++" << P() << " != " << PE() << " )\n"
1021                         "               goto _resume;\n";
1022         }
1023         else {
1024                 out <<
1025                         "       " << P() << " += 1;\n"
1026                         "       goto _resume;\n";
1027         }
1028
1029         if ( testEofUsed )
1030                 out << "        _test_eof: {}\n";
1031
1032         if ( redFsm->anyEofTrans() || redFsm->anyEofActions() ) {
1033                 out <<
1034                         "       if ( " << P() << " == " << EOFV() << " )\n"
1035                         "       {\n";
1036
1037                 if ( redFsm->anyEofTrans() ) {
1038                         out <<
1039                                 "       if ( " << ET() << "[" << CS() << "] > 0 ) {\n"
1040                                 "               _trans = " << ET() << "[" << CS() << "] - 1;\n"
1041                                 "               goto _eof_trans;\n"
1042                                 "       }\n";
1043                 }
1044
1045                 if ( redFsm->anyEofActions() ) {
1046                         out <<
1047                                 "       " << PTR_CONST() << ARRAY_TYPE(redFsm->maxActArrItem) <<
1048                                                 POINTER() << "__acts = " <<
1049                                                 ARR_OFF( A(), EA() + "[" + CS() + "]" ) << ";\n"
1050                                 "       " << UINT() << " __nacts = " << CAST(UINT()) << " *__acts++;\n"
1051                                 "       while ( __nacts-- > 0 ) {\n"
1052                                 "               switch ( *__acts++ ) {\n";
1053                                 EOF_ACTION_SWITCH();
1054                                 SWITCH_DEFAULT() <<
1055                                 "               }\n"
1056                                 "       }\n";
1057                 }
1058
1059                 out <<
1060                         "       }\n"
1061                         "\n";
1062         }
1063
1064         if ( outLabelUsed )
1065                 out << "        _out: {}\n";
1066
1067         out << "        }\n";
1068 }