ragel/cdtable.cpp

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