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