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