ragel/cstable.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 "cstable.h"
  26 #include "redfsm.h"
  27 #include "gendata.h"
  28
  29 /* Determine if we should use indicies or not. */
  30 void CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 );
 104                         out << "\tbreak;\n";
 105                 }
 106         }
 107
 108         genLineDirective( out );
 109         return out;
 110 }
 111
 112 std::ostream &CSharpTabCodeGen::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 );
 121                         out << "\tbreak;\n";
 122                 }
 123         }
 124
 125         genLineDirective( out );
 126         return out;
 127 }
 128
 129 std::ostream &CSharpTabCodeGen::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 );
 138                         out << "\tbreak;\n";
 139                 }
 140         }
 141
 142         genLineDirective( out );
 143         return out;
 144 }
 145
 146
 147 std::ostream &CSharpTabCodeGen::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 );
 156                         out << "\tbreak;\n";
 157                 }
 158         }
 159
 160         genLineDirective( out );
 161         return out;
 162 }
 163
 164 std::ostream &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 << ALPHA_KEY( sc->lowKey ) << ", ";
 363                         if ( ++totalTrans % IALL == 0 )
 364                                 out << "\n\t";
 365
 366                         /* Upper key. */
 367                         out << ALPHA_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 &CSharpTabCodeGen::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 &CSharpTabCodeGen::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 << ALPHA_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 << ALPHA_KEY( rtel->lowKey ) << ", ";
 415                         if ( ++totalTrans % IALL == 0 )
 416                                 out << "\n\t";
 417
 418                         /* Upper key. */
 419                         out << ALPHA_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 << "(char) " << 0 << "\n";
 428         return out;
 429 }
 430
 431 std::ostream &CSharpTabCodeGen::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 &CSharpTabCodeGen::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         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 495                 if ( st->eofTrans != 0 ) {
 496                         RedTransAp *trans = st->eofTrans;
 497                         trans->pos = totalTrans;
 498                         out << trans->targ->id << ", ";
 499                         if ( ++totalTrans % IALL == 0 )
 500                                 out << "\n\t";
 501                 }
 502         }
 503
 504
 505         /* Output one last number so we don't have to figure out when the last
 506          * entry is and avoid writing a comma. */
 507         out << 0 << "\n";
 508         return out;
 509 }
 510
 511
 512 std::ostream &CSharpTabCodeGen::TRANS_ACTIONS()
 513 {
 514         int totalTrans = 0;
 515         out << '\t';
 516         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 517                 /* Walk the singles. */
 518                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 519                         RedTransAp *trans = stel->value;
 520                         TRANS_ACTION( trans ) << ", ";
 521                         if ( ++totalTrans % IALL == 0 )
 522                                 out << "\n\t";
 523                 }
 524
 525                 /* Walk the ranges. */
 526                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 527                         RedTransAp *trans = rtel->value;
 528                         TRANS_ACTION( trans ) << ", ";
 529                         if ( ++totalTrans % IALL == 0 )
 530                                 out << "\n\t";
 531                 }
 532
 533                 /* The state's default index goes next. */
 534                 if ( st->defTrans != 0 ) {
 535                         RedTransAp *trans = st->defTrans;
 536                         TRANS_ACTION( trans ) << ", ";
 537                         if ( ++totalTrans % IALL == 0 )
 538                                 out << "\n\t";
 539                 }
 540         }
 541
 542         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 543                 if ( st->eofTrans != 0 ) {
 544                         RedTransAp *trans = st->eofTrans;
 545                         TRANS_ACTION( trans ) << ", ";
 546                         if ( ++totalTrans % IALL == 0 )
 547                                 out << "\n\t";
 548                 }
 549         }
 550
 551         /* Output one last number so we don't have to figure out when the last
 552          * entry is and avoid writing a comma. */
 553         out << 0 << "\n";
 554         return out;
 555 }
 556
 557 std::ostream &CSharpTabCodeGen::TRANS_TARGS_WI()
 558 {
 559         /* Transitions must be written ordered by their id. */
 560         RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
 561         for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
 562                 transPtrs[trans->id] = trans;
 563
 564         /* Keep a count of the num of items in the array written. */
 565         out << '\t';
 566         int totalStates = 0;
 567         for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
 568                 /* Record the position, need this for eofTrans. */
 569                 RedTransAp *trans = transPtrs[t];
 570                 trans->pos = t;
 571
 572                 /* Write out the target state. */
 573                 out << trans->targ->id;
 574                 if ( t < redFsm->transSet.length()-1 ) {
 575                         out << ", ";
 576                         if ( ++totalStates % IALL == 0 )
 577                                 out << "\n\t";
 578                 }
 579         }
 580         out << "\n";
 581         delete[] transPtrs;
 582         return out;
 583 }
 584
 585
 586 std::ostream &CSharpTabCodeGen::TRANS_ACTIONS_WI()
 587 {
 588         /* Transitions must be written ordered by their id. */
 589         RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
 590         for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
 591                 transPtrs[trans->id] = trans;
 592
 593         /* Keep a count of the num of items in the array written. */
 594         out << '\t';
 595         int totalAct = 0;
 596         for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
 597                 /* Write the function for the transition. */
 598                 RedTransAp *trans = transPtrs[t];
 599                 TRANS_ACTION( trans );
 600                 if ( t < redFsm->transSet.length()-1 ) {
 601                         out << ", ";
 602                         if ( ++totalAct % IALL == 0 )
 603                                 out << "\n\t";
 604                 }
 605         }
 606         out << "\n";
 607         delete[] transPtrs;
 608         return out;
 609 }
 610
 611 void CSharpTabCodeGen::GOTO( ostream &ret, int gotoDest, bool inFinish )
 612 {
 613         ret << "{" << vCS() << " = " << gotoDest << "; " <<
 614                         CTRL_FLOW() << "goto _again;}";
 615 }
 616
 617 void CSharpTabCodeGen::GOTO_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish )
 618 {
 619         ret << "{" << vCS() << " = (";
 620         INLINE_LIST( ret, ilItem->children, 0, inFinish );
 621         ret << "); " << CTRL_FLOW() << "goto _again;}";
 622 }
 623
 624 void CSharpTabCodeGen::CURS( ostream &ret, bool inFinish )
 625 {
 626         ret << "(_ps)";
 627 }
 628
 629 void CSharpTabCodeGen::TARGS( ostream &ret, bool inFinish, int targState )
 630 {
 631         ret << "(" << vCS() << ")";
 632 }
 633
 634 void CSharpTabCodeGen::NEXT( ostream &ret, int nextDest, bool inFinish )
 635 {
 636         ret << vCS() << " = " << nextDest << ";";
 637 }
 638
 639 void CSharpTabCodeGen::NEXT_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish )
 640 {
 641         ret << vCS() << " = (";
 642         INLINE_LIST( ret, ilItem->children, 0, inFinish );
 643         ret << ");";
 644 }
 645
 646 void CSharpTabCodeGen::CALL( ostream &ret, int callDest, int targState, bool inFinish )
 647 {
 648         if ( prePushExpr != 0 ) {
 649                 ret << "{";
 650                 INLINE_LIST( ret, prePushExpr, 0, false );
 651         }
 652
 653         ret << "{" << STACK() << "[" << TOP() << "++] = " << vCS() << "; " << vCS() << " = " <<
 654                         callDest << "; " << CTRL_FLOW() << "goto _again;}";
 655
 656         if ( prePushExpr != 0 )
 657                 ret << "}";
 658 }
 659
 660 void CSharpTabCodeGen::CALL_EXPR( ostream &ret, GenInlineItem *ilItem, int targState, bool inFinish )
 661 {
 662         if ( prePushExpr != 0 ) {
 663                 ret << "{";
 664                 INLINE_LIST( ret, prePushExpr, 0, false );
 665         }
 666
 667         ret << "{" << STACK() << "[" << TOP() << "++] = " << vCS() << "; " << vCS() << " = (";
 668         INLINE_LIST( ret, ilItem->children, targState, inFinish );
 669         ret << "); " << CTRL_FLOW() << "goto _again;}";
 670
 671         if ( prePushExpr != 0 )
 672                 ret << "}";
 673 }
 674
 675 void CSharpTabCodeGen::RET( ostream &ret, bool inFinish )
 676 {
 677         ret << "{" << vCS() << " = " << STACK() << "[--" <<
 678                         TOP() << "]; ";
 679
 680         if ( postPopExpr != 0 ) {
 681                 ret << "{";
 682                 INLINE_LIST( ret, postPopExpr, 0, false );
 683                 ret << "}";
 684         }
 685
 686         ret << CTRL_FLOW() <<  "goto _again;}";
 687 }
 688
 689 void CSharpTabCodeGen::BREAK( ostream &ret, int targState )
 690 {
 691         outLabelUsed = true;
 692         ret << "{" << P() << "++; " << CTRL_FLOW() << "goto _out; }";
 693 }
 694
 695 void CSharpTabCodeGen::writeData()
 696 {
 697         /* If there are any transtion functions then output the array. If there
 698          * are none, don't bother emitting an empty array that won't be used. */
 699         if ( redFsm->anyActions() ) {
 700                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActArrItem), A() );
 701                 ACTIONS_ARRAY();
 702                 CLOSE_ARRAY() <<
 703                 "\n";
 704         }
 705
 706         if ( redFsm->anyConditions() ) {
 707                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondOffset), CO() );
 708                 COND_OFFSETS();
 709                 CLOSE_ARRAY() <<
 710                 "\n";
 711
 712                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondLen), CL() );
 713                 COND_LENS();
 714                 CLOSE_ARRAY() <<
 715                 "\n";
 716
 717                 OPEN_ARRAY( WIDE_ALPH_TYPE(), CK() );
 718                 COND_KEYS();
 719                 CLOSE_ARRAY() <<
 720                 "\n";
 721
 722                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondSpaceId), C() );
 723                 COND_SPACES();
 724                 CLOSE_ARRAY() <<
 725                 "\n";
 726         }
 727
 728         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxKeyOffset), KO() );
 729         KEY_OFFSETS();
 730         CLOSE_ARRAY() <<
 731         "\n";
 732
 733         OPEN_ARRAY( WIDE_ALPH_TYPE(), K() );
 734         KEYS();
 735         CLOSE_ARRAY() <<
 736         "\n";
 737
 738         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxSingleLen), SL() );
 739         SINGLE_LENS();
 740         CLOSE_ARRAY() <<
 741         "\n";
 742
 743         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxRangeLen), RL() );
 744         RANGE_LENS();
 745         CLOSE_ARRAY() <<
 746         "\n";
 747
 748         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset), IO() );
 749         INDEX_OFFSETS();
 750         CLOSE_ARRAY() <<
 751         "\n";
 752
 753         if ( useIndicies ) {
 754                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex), I() );
 755                 INDICIES();
 756                 CLOSE_ARRAY() <<
 757                 "\n";
 758
 759                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 760                 TRANS_TARGS_WI();
 761                 CLOSE_ARRAY() <<
 762                 "\n";
 763
 764                 if ( redFsm->anyActions() ) {
 765                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
 766                         TRANS_ACTIONS_WI();
 767                         CLOSE_ARRAY() <<
 768                         "\n";
 769                 }
 770         }
 771         else {
 772                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 773                 TRANS_TARGS();
 774                 CLOSE_ARRAY() <<
 775                 "\n";
 776
 777                 if ( redFsm->anyActions() ) {
 778                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
 779                         TRANS_ACTIONS();
 780                         CLOSE_ARRAY() <<
 781                         "\n";
 782                 }
 783         }
 784
 785         if ( redFsm->anyToStateActions() ) {
 786                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
 787                 TO_STATE_ACTIONS();
 788                 CLOSE_ARRAY() <<
 789                 "\n";
 790         }
 791
 792         if ( redFsm->anyFromStateActions() ) {
 793                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
 794                 FROM_STATE_ACTIONS();
 795                 CLOSE_ARRAY() <<
 796                 "\n";
 797         }
 798
 799         if ( redFsm->anyEofActions() ) {
 800                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), EA() );
 801                 EOF_ACTIONS();
 802                 CLOSE_ARRAY() <<
 803                 "\n";
 804         }
 805
 806         if ( redFsm->anyEofTrans() ) {
 807                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset+1), ET() );
 808                 EOF_TRANS();
 809                 CLOSE_ARRAY() <<
 810                 "\n";
 811         }
 812
 813         STATE_IDS();
 814 }
 815
 816 void CSharpTabCodeGen::LOCATE_TRANS()
 817 {
 818         out <<
 819                 "       _keys = " << KO() + "[" + vCS() + "]" << ";\n"
 820                 "       _trans = " << CAST(transType) << IO() << "[" << vCS() << "];\n"
 821                 "\n"
 822                 "       _klen = " << SL() << "[" << vCS() << "];\n"
 823                 "       if ( _klen > 0 ) {\n"
 824                 "               " << signedKeysType << " _lower = _keys;\n"
 825                 "               " << signedKeysType << " _mid;\n"
 826                 "               " << signedKeysType << " _upper = " << CAST(signedKeysType) <<
 827                         " (_keys + _klen - 1);\n"
 828                 "               while (true) {\n"
 829                 "                       if ( _upper < _lower )\n"
 830                 "                               break;\n"
 831                 "\n"
 832                 "                       _mid = " << CAST(signedKeysType) <<
 833                         " (_lower + ((_upper-_lower) >> 1));\n"
 834                 "                       if ( " << GET_WIDE_KEY() << " < " << K() << "[_mid] )\n"
 835                 "                               _upper = " << CAST(signedKeysType) << " (_mid - 1);\n"
 836                 "                       else if ( " << GET_WIDE_KEY() << " > " << K() << "[_mid] )\n"
 837                 "                               _lower = " << CAST(signedKeysType) << " (_mid + 1);\n"
 838                 "                       else {\n"
 839                 "                               _trans += " << CAST(transType) << " (_mid - _keys);\n"
 840                 "                               goto _match;\n"
 841                 "                       }\n"
 842                 "               }\n"
 843                 "               _keys += " << CAST(keysType) << " _klen;\n"
 844                 "               _trans += " << CAST(transType) << " _klen;\n"
 845                 "       }\n"
 846                 "\n"
 847                 "       _klen = " << RL() << "[" << vCS() << "];\n"
 848                 "       if ( _klen > 0 ) {\n"
 849                 "               " << signedKeysType << " _lower = _keys;\n"
 850                 "               " << signedKeysType << " _mid;\n"
 851                 "               " << signedKeysType << " _upper = " << CAST(signedKeysType) <<
 852                         " (_keys + (_klen<<1) - 2);\n"
 853                 "               while (true) {\n"
 854                 "                       if ( _upper < _lower )\n"
 855                 "                               break;\n"
 856                 "\n"
 857                 "                       _mid = " << CAST(signedKeysType) <<
 858                         " (_lower + (((_upper-_lower) >> 1) & ~1));\n"
 859                 "                       if ( " << GET_WIDE_KEY() << " < " << K() << "[_mid] )\n"
 860                 "                               _upper = " << CAST(signedKeysType) << " (_mid - 2);\n"
 861                 "                       else if ( " << GET_WIDE_KEY() << " > " << K() << "[_mid+1] )\n"
 862                 "                               _lower = " << CAST(signedKeysType) << " (_mid + 2);\n"
 863                 "                       else {\n"
 864                 "                               _trans += " << CAST(transType) << "((_mid - _keys)>>1);\n"
 865                 "                               goto _match;\n"
 866                 "                       }\n"
 867                 "               }\n"
 868                 "               _trans += " << CAST(transType) << " _klen;\n"
 869                 "       }\n"
 870                 "\n";
 871 }
 872
 873 void CSharpTabCodeGen::COND_TRANSLATE()
 874 {
 875         out <<
 876                 "       _widec = " << GET_KEY() << ";\n"
 877                 "       _klen = " << CL() << "[" << vCS() << "];\n"
 878                 "       _keys = " << CAST(keysType) << " ("<< CO() << "[" << vCS() << "]*2);\n"
 879                 "       if ( _klen > 0 ) {\n"
 880                 "               " << signedKeysType << " _lower = _keys;\n"
 881                 "               " << signedKeysType << " _mid;\n"
 882                 "               " << signedKeysType << " _upper = " << CAST(signedKeysType) <<
 883                         " (_keys + (_klen<<1) - 2);\n"
 884                 "               while (true) {\n"
 885                 "                       if ( _upper < _lower )\n"
 886                 "                               break;\n"
 887                 "\n"
 888                 "                       _mid = " << CAST(signedKeysType) <<
 889                         " (_lower + (((_upper-_lower) >> 1) & ~1));\n"
 890                 "                       if ( " << GET_WIDE_KEY() << " < " << CK() << "[_mid] )\n"
 891                 "                               _upper = " << CAST(signedKeysType) << " (_mid - 2);\n"
 892                 "                       else if ( " << GET_WIDE_KEY() << " > " << CK() << "[_mid+1] )\n"
 893                 "                               _lower = " << CAST(signedKeysType) << " (_mid + 2);\n"
 894                 "                       else {\n"
 895                 "                               switch ( " << C() << "[" << CO() << "[" << vCS() << "]"
 896                                                         " + ((_mid - _keys)>>1)] ) {\n";
 897
 898         for ( CondSpaceList::Iter csi = condSpaceList; csi.lte(); csi++ ) {
 899                 GenCondSpace *condSpace = csi;
 900                 out << "        case " << condSpace->condSpaceId << ": {\n";
 901                 out << TABS(2) << "_widec = " << CAST(WIDE_ALPH_TYPE()) << "(" <<
 902                                 KEY(condSpace->baseKey) << " + (" << GET_KEY() <<
 903                                 " - " << KEY(keyOps->minKey) << "));\n";
 904
 905                 for ( GenCondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
 906                         out << TABS(2) << "if ( ";
 907                         CONDITION( out, *csi );
 908                         Size condValOffset = ((1 << csi.pos()) * keyOps->alphSize());
 909                         out << " ) _widec += " << condValOffset << ";\n";
 910                 }
 911
 912                 out <<
 913                         "               break;\n"
 914                         "       }\n";
 915         }
 916
 917         SWITCH_DEFAULT();
 918
 919         out <<
 920                 "                               }\n"
 921                 "                               break;\n"
 922                 "                       }\n"
 923                 "               }\n"
 924                 "       }\n"
 925                 "\n";
 926 }
 927
 928 void CSharpTabCodeGen::writeExec()
 929 {
 930         testEofUsed = false;
 931         outLabelUsed = false;
 932         initVarTypes();
 933
 934         out <<
 935                 "       {\n"
 936                 "       " << klenType << " _klen";
 937
 938         if ( redFsm->anyRegCurStateRef() )
 939                 out << ", _ps";
 940
 941         out <<
 942                 ";\n"
 943                 "       " << transType << " _trans;\n";
 944
 945         if ( redFsm->anyConditions() )
 946                 out << "        " << WIDE_ALPH_TYPE() << " _widec;\n";
 947
 948         if ( redFsm->anyToStateActions() || redFsm->anyRegActions()
 949                         || redFsm->anyFromStateActions() )
 950         {
 951                 out <<
 952                         "       " << actsType << " _acts;\n"
 953                         "       " << nactsType << " _nacts;\n";
 954         }
 955
 956         out <<
 957                 "       " << keysType << " _keys;\n"
 958                 "\n";
 959 //              "       " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_keys;\n"
 960
 961         if ( !noEnd ) {
 962                 testEofUsed = true;
 963                 out <<
 964                         "       if ( " << P() << " == " << PE() << " )\n"
 965                         "               goto _test_eof;\n";
 966         }
 967
 968         if ( redFsm->errState != 0 ) {
 969                 outLabelUsed = true;
 970                 out <<
 971                         "       if ( " << vCS() << " == " << redFsm->errState->id << " )\n"
 972                         "               goto _out;\n";
 973         }
 974
 975         out << "_resume:\n";
 976
 977         if ( redFsm->anyFromStateActions() ) {
 978                 out <<
 979                         "       _acts = " << FSA() << "[" + vCS() + "]" << ";\n"
 980                         "       _nacts = " << A() << "[_acts++];\n"
 981                         "       while ( _nacts-- > 0 ) {\n"
 982                         "               switch ( " << A() << "[_acts++] ) {\n";
 983                         FROM_STATE_ACTION_SWITCH();
 984                         SWITCH_DEFAULT() <<
 985                         "               }\n"
 986                         "       }\n"
 987                         "\n";
 988         }
 989
 990         if ( redFsm->anyConditions() )
 991                 COND_TRANSLATE();
 992
 993         LOCATE_TRANS();
 994
 995         out << "_match:\n";
 996
 997         if ( useIndicies )
 998                 out << "        _trans = " << CAST(transType) << I() << "[_trans];\n";
 999
1000         if ( redFsm->anyEofTrans() )
1001                 out << "_eof_trans:\n";
1002
1003         if ( redFsm->anyRegCurStateRef() )
1004                 out << "        _ps = " << vCS() << ";\n";
1005
1006         out <<
1007                 "       " << vCS() << " = " << TT() << "[_trans];\n"
1008                 "\n";
1009
1010         if ( redFsm->anyRegActions() ) {
1011                 out <<
1012                         "       if ( " << TA() << "[_trans] == 0 )\n"
1013                         "               goto _again;\n"
1014                         "\n"
1015                         "       _acts = " << TA() << "[_trans]" << ";\n"
1016                         "       _nacts = " << A() << "[_acts++];\n"
1017                         "       while ( _nacts-- > 0 )\n        {\n"
1018                         "               switch ( " << A() << "[_acts++] )\n             {\n";
1019                         ACTION_SWITCH();
1020                         SWITCH_DEFAULT() <<
1021                         "               }\n"
1022                         "       }\n"
1023                         "\n";
1024         }
1025
1026         if ( redFsm->anyRegActions() || redFsm->anyActionGotos() ||
1027                         redFsm->anyActionCalls() || redFsm->anyActionRets() )
1028                 out << "_again:\n";
1029
1030         if ( redFsm->anyToStateActions() ) {
1031                 out <<
1032                         "       _acts = " << TSA() << "[" << vCS() << "]" << ";\n"
1033                         "       _nacts = " << A() << "[_acts++];\n"
1034                         "       while ( _nacts-- > 0 ) {\n"
1035                         "               switch ( " << A() << "[_acts++] ) {\n";
1036                         TO_STATE_ACTION_SWITCH();
1037                         SWITCH_DEFAULT() <<
1038                         "               }\n"
1039                         "       }\n"
1040                         "\n";
1041         }
1042
1043         if ( redFsm->errState != 0 ) {
1044                 outLabelUsed = true;
1045                 out <<
1046                         "       if ( " << vCS() << " == " << redFsm->errState->id << " )\n"
1047                         "               goto _out;\n";
1048         }
1049
1050         if ( !noEnd ) {
1051                 out <<
1052                         "       if ( ++" << P() << " != " << PE() << " )\n"
1053                         "               goto _resume;\n";
1054         }
1055         else {
1056                 out <<
1057                         "       " << P() << " += 1;\n"
1058                         "       goto _resume;\n";
1059         }
1060
1061         if ( testEofUsed )
1062                 out << "        _test_eof: {}\n";
1063
1064         if ( redFsm->anyEofTrans() || redFsm->anyEofActions() ) {
1065                 out <<
1066                         "       if ( " << P() << " == " << vEOF() << " )\n"
1067                         "       {\n";
1068
1069                 if ( redFsm->anyEofTrans() ) {
1070                         out <<
1071                                 "       if ( " << ET() << "[" << vCS() << "] > 0 ) {\n"
1072                                 "               _trans = " << CAST(transType) << " (" << ET() <<
1073                                         "[" << vCS() << "] - 1);\n"
1074                                 "               goto _eof_trans;\n"
1075                                 "       }\n";
1076                 }
1077
1078                 if ( redFsm->anyEofActions() ) {
1079                         out <<
1080                                 "       " << actsType << " __acts = " <<
1081                                                 EA() << "[" << vCS() << "]" << ";\n"
1082                                 "       " << nactsType << " __nacts = " <<
1083                                 A() << "[__acts++];\n"
1084                                 "       while ( __nacts-- > 0 ) {\n"
1085                                 "               switch ( " << A() << "[__acts++] ) {\n";
1086                                 EOF_ACTION_SWITCH();
1087                                 SWITCH_DEFAULT() <<
1088                                 "               }\n"
1089                                 "       }\n";
1090                 }
1091
1092                 out <<
1093                         "       }\n"
1094                         "\n";
1095         }
1096
1097         if ( outLabelUsed )
1098                 out << "        _out: {}\n";
1099
1100         out << "        }\n";
1101 }
1102
1103 void CSharpTabCodeGen::initVarTypes()
1104 {
1105         int klenMax = MAX(MAX(redFsm->maxCondLen, redFsm->maxRangeLen),
1106                                 redFsm->maxSingleLen);
1107         int keysMax = MAX(MAX(redFsm->maxKeyOffset, klenMax),
1108                                 redFsm->maxCondOffset);
1109         int transMax = MAX(MAX(redFsm->maxIndex+1, redFsm->maxIndexOffset), keysMax);
1110         transMax = MAX(transMax, klenMax);
1111         transType = ARRAY_TYPE(transMax);
1112         klenType = ARRAY_TYPE(klenMax);
1113         keysType = ARRAY_TYPE(keysMax);
1114         signedKeysType = ARRAY_TYPE(keysMax, true);
1115         actsType = ARRAY_TYPE(redFsm->maxActionLoc);
1116         nactsType = ARRAY_TYPE(redFsm->maxActArrItem);
1117 }