ragel/gotable.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 <sstream>
  25 #include "ragel.h"
  26 #include "gotable.h"
  27 #include "redfsm.h"
  28 #include "gendata.h"
  29
  30 using std::endl;
  31
  32 /* Determine if we should use indicies or not. */
  33 void GoTabCodeGen::calcIndexSize()
  34 {
  35         int sizeWithInds = 0, sizeWithoutInds = 0;
  36
  37         /* Calculate cost of using with indicies. */
  38         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  39                 int totalIndex = st->outSingle.length() + st->outRange.length() +
  40                                 (st->defTrans == 0 ? 0 : 1);
  41                 sizeWithInds += arrayTypeSize(redFsm->maxIndex) * totalIndex;
  42         }
  43         sizeWithInds += arrayTypeSize(redFsm->maxState) * redFsm->transSet.length();
  44         if ( redFsm->anyActions() )
  45                 sizeWithInds += arrayTypeSize(redFsm->maxActionLoc) * redFsm->transSet.length();
  46
  47         /* Calculate the cost of not using indicies. */
  48         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
  49                 int totalIndex = st->outSingle.length() + st->outRange.length() +
  50                                 (st->defTrans == 0 ? 0 : 1);
  51                 sizeWithoutInds += arrayTypeSize(redFsm->maxState) * totalIndex;
  52                 if ( redFsm->anyActions() )
  53                         sizeWithoutInds += arrayTypeSize(redFsm->maxActionLoc) * totalIndex;
  54         }
  55
  56         /* If using indicies reduces the size, use them. */
  57         useIndicies = sizeWithInds < sizeWithoutInds;
  58 }
  59
  60 std::ostream &GoTabCodeGen::TO_STATE_ACTION( RedStateAp *state )
  61 {
  62         int act = 0;
  63         if ( state->toStateAction != 0 )
  64                 act = state->toStateAction->location+1;
  65         out << act;
  66         return out;
  67 }
  68
  69 std::ostream &GoTabCodeGen::FROM_STATE_ACTION( RedStateAp *state )
  70 {
  71         int act = 0;
  72         if ( state->fromStateAction != 0 )
  73                 act = state->fromStateAction->location+1;
  74         out << act;
  75         return out;
  76 }
  77
  78 std::ostream &GoTabCodeGen::EOF_ACTION( RedStateAp *state )
  79 {
  80         int act = 0;
  81         if ( state->eofAction != 0 )
  82                 act = state->eofAction->location+1;
  83         out << act;
  84         return out;
  85 }
  86
  87
  88 std::ostream &GoTabCodeGen::TRANS_ACTION( RedTransAp *trans )
  89 {
  90         /* If there are actions, emit them. Otherwise emit zero. */
  91         int act = 0;
  92         if ( trans->action != 0 )
  93                 act = trans->action->location+1;
  94         out << act;
  95         return out;
  96 }
  97
  98 std::ostream &GoTabCodeGen::TO_STATE_ACTION_SWITCH( int level )
  99 {
 100         /* Walk the list of functions, printing the cases. */
 101         for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
 102                 /* Write out referenced actions. */
 103                 if ( act->numToStateRefs > 0 ) {
 104                         /* Write the case label, the action and the case break. */
 105                         out << TABS(level) << "case " << act->actionId << ":" << endl;
 106                         ACTION( out, act, 0, false, false );
 107                 }
 108         }
 109
 110         genLineDirective( out );
 111         return out;
 112 }
 113
 114 std::ostream &GoTabCodeGen::FROM_STATE_ACTION_SWITCH( int level )
 115 {
 116         /* Walk the list of functions, printing the cases. */
 117         for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
 118                 /* Write out referenced actions. */
 119                 if ( act->numFromStateRefs > 0 ) {
 120                         /* Write the case label, the action and the case break. */
 121                         out << TABS(level) << "case " << act->actionId << ":" << endl;
 122                         ACTION( out, act, 0, false, false );
 123                 }
 124         }
 125
 126         genLineDirective( out );
 127         return out;
 128 }
 129
 130 std::ostream &GoTabCodeGen::EOF_ACTION_SWITCH( int level )
 131 {
 132         /* Walk the list of functions, printing the cases. */
 133         for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
 134                 /* Write out referenced actions. */
 135                 if ( act->numEofRefs > 0 ) {
 136                         /* Write the case label, the action and the case break. */
 137                         out << TABS(level) << "case " << act->actionId << ":" << endl;
 138                         ACTION( out, act, 0, true, false );
 139                 }
 140         }
 141
 142         genLineDirective(out);
 143         return out;
 144 }
 145
 146
 147 std::ostream &GoTabCodeGen::ACTION_SWITCH( int level )
 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 << TABS(level) << "case " << act->actionId << ":" << endl;
 155                         ACTION( out, act, 0, false, false );
 156                 }
 157         }
 158
 159         genLineDirective(out);
 160         return out;
 161 }
 162
 163 std::ostream &GoTabCodeGen::COND_OFFSETS()
 164 {
 165         out << "        ";
 166         int totalStateNum = 0, curKeyOffset = 0;
 167         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 168                 /* Write the key offset. */
 169                 out << curKeyOffset;
 170                 out << ", ";
 171                 if ( !st.last() ) {
 172                         if ( ++totalStateNum % IALL == 0 )
 173                                 out << endl << "        ";
 174                 }
 175
 176                 /* Move the key offset ahead. */
 177                 curKeyOffset += st->stateCondList.length();
 178         }
 179         out << endl;
 180         return out;
 181 }
 182
 183 std::ostream &GoTabCodeGen::KEY_OFFSETS()
 184 {
 185         out << "        ";
 186         int totalStateNum = 0, curKeyOffset = 0;
 187         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 188                 /* Write the key offset. */
 189                 out << curKeyOffset;
 190                 out << ", ";
 191                 if ( !st.last() ) {
 192                         if ( ++totalStateNum % IALL == 0 )
 193                                 out << endl << "        ";
 194                 }
 195
 196                 /* Move the key offset ahead. */
 197                 curKeyOffset += st->outSingle.length() + st->outRange.length()*2;
 198         }
 199         out << endl;
 200         return out;
 201 }
 202
 203
 204 std::ostream &GoTabCodeGen::INDEX_OFFSETS()
 205 {
 206         out << "        ";
 207         int totalStateNum = 0, curIndOffset = 0;
 208         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 209                 /* Write the index offset. */
 210                 out << curIndOffset;
 211                 out << ", ";
 212                 if ( !st.last() ) {
 213                         if ( ++totalStateNum % IALL == 0 )
 214                                 out << endl << "        ";
 215                 }
 216
 217                 /* Move the index offset ahead. */
 218                 curIndOffset += st->outSingle.length() + st->outRange.length();
 219                 if ( st->defTrans != 0 )
 220                         curIndOffset += 1;
 221         }
 222         out << endl;
 223         return out;
 224 }
 225
 226 std::ostream &GoTabCodeGen::COND_LENS()
 227 {
 228         out << "        ";
 229         int totalStateNum = 0;
 230         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 231                 /* Write singles length. */
 232                 out << st->stateCondList.length();
 233                 out << ", ";
 234                 if ( !st.last() ) {
 235                         if ( ++totalStateNum % IALL == 0 )
 236                                 out << endl << "        ";
 237                 }
 238         }
 239         out << endl;
 240         return out;
 241 }
 242
 243
 244 std::ostream &GoTabCodeGen::SINGLE_LENS()
 245 {
 246         out << "        ";
 247         int totalStateNum = 0;
 248         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 249                 /* Write singles length. */
 250                 out << st->outSingle.length();
 251                 out << ", ";
 252                 if ( !st.last() ) {
 253                         if ( ++totalStateNum % IALL == 0 )
 254                                 out << endl << "        ";
 255                 }
 256         }
 257         out << endl;
 258         return out;
 259 }
 260
 261 std::ostream &GoTabCodeGen::RANGE_LENS()
 262 {
 263         out << "        ";
 264         int totalStateNum = 0;
 265         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 266                 /* Emit length of range index. */
 267                 out << st->outRange.length();
 268                 out << ", ";
 269                 if ( !st.last() ) {
 270                         if ( ++totalStateNum % IALL == 0 )
 271                                 out << endl << "        ";
 272                 }
 273         }
 274         out << endl;
 275         return out;
 276 }
 277
 278 std::ostream &GoTabCodeGen::TO_STATE_ACTIONS()
 279 {
 280         out << "        ";
 281         int totalStateNum = 0;
 282         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 283                 /* Write any eof action. */
 284                 TO_STATE_ACTION(st);
 285                 out << ", ";
 286                 if ( !st.last() ) {
 287                         if ( ++totalStateNum % IALL == 0 )
 288                                 out << endl << "        ";
 289                 }
 290         }
 291         out << endl;
 292         return out;
 293 }
 294
 295 std::ostream &GoTabCodeGen::FROM_STATE_ACTIONS()
 296 {
 297         out << "        ";
 298         int totalStateNum = 0;
 299         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 300                 /* Write any eof action. */
 301                 FROM_STATE_ACTION(st);
 302                 out << ", ";
 303                 if ( !st.last() ) {
 304                         if ( ++totalStateNum % IALL == 0 )
 305                                 out << endl << "        ";
 306                 }
 307         }
 308         out << endl;
 309         return out;
 310 }
 311
 312 std::ostream &GoTabCodeGen::EOF_ACTIONS()
 313 {
 314         out << "        ";
 315         int totalStateNum = 0;
 316         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 317                 /* Write any eof action. */
 318                 EOF_ACTION(st);
 319                 out << ", ";
 320                 if ( !st.last() ) {
 321                         if ( ++totalStateNum % IALL == 0 )
 322                                 out << endl << "        ";
 323                 }
 324         }
 325         out << endl;
 326         return out;
 327 }
 328
 329 std::ostream &GoTabCodeGen::EOF_TRANS()
 330 {
 331         out << "        ";
 332         int totalStateNum = 0;
 333         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 334                 /* Write any eof action. */
 335                 long trans = 0;
 336                 if ( st->eofTrans != 0 ) {
 337                         assert( st->eofTrans->pos >= 0 );
 338                         trans = st->eofTrans->pos+1;
 339                 }
 340                 out << trans;
 341
 342                 out << ", ";
 343                 if ( !st.last() ) {
 344                         if ( ++totalStateNum % IALL == 0 )
 345                                 out << endl << "        ";
 346                 }
 347         }
 348         out << endl;
 349         return out;
 350 }
 351
 352
 353 std::ostream &GoTabCodeGen::COND_KEYS()
 354 {
 355         out << "        ";
 356         int totalTrans = 0;
 357         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 358                 /* Loop the state's transitions. */
 359                 for ( GenStateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
 360                         /* Lower key. */
 361                         out << KEY( sc->lowKey ) << ", ";
 362                         if ( ++totalTrans % IALL == 0 )
 363                                 out << endl << "        ";
 364
 365                         /* Upper key. */
 366                         out << KEY( sc->highKey ) << ", ";
 367                         if ( ++totalTrans % IALL == 0 )
 368                                 out << endl << "        ";
 369                 }
 370         }
 371
 372         out << endl;
 373         return out;
 374 }
 375
 376 std::ostream &GoTabCodeGen::COND_SPACES()
 377 {
 378         out << "        ";
 379         int totalTrans = 0;
 380         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 381                 /* Loop the state's transitions. */
 382                 for ( GenStateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
 383                         /* Cond Space id. */
 384                         out << sc->condSpace->condSpaceId << ", ";
 385                         if ( ++totalTrans % IALL == 0 )
 386                                 out << endl << "        ";
 387                 }
 388         }
 389
 390         out << endl;
 391         return out;
 392 }
 393
 394 std::ostream &GoTabCodeGen::KEYS()
 395 {
 396         out << "        ";
 397         int totalTrans = 0;
 398         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 399                 /* Loop the singles. */
 400                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 401                         out << KEY( stel->lowKey ) << ", ";
 402                         if ( ++totalTrans % IALL == 0 )
 403                                 out << endl << "        ";
 404                 }
 405
 406                 /* Loop the state's transitions. */
 407                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 408                         /* Lower key. */
 409                         out << KEY( rtel->lowKey ) << ", ";
 410                         if ( ++totalTrans % IALL == 0 )
 411                                 out << endl << "        ";
 412
 413                         /* Upper key. */
 414                         out << KEY( rtel->highKey ) << ", ";
 415                         if ( ++totalTrans % IALL == 0 )
 416                                 out << endl << "        ";
 417                 }
 418         }
 419
 420         out << endl;
 421         return out;
 422 }
 423
 424 std::ostream &GoTabCodeGen::INDICIES()
 425 {
 426         out << "        ";
 427         int totalTrans = 0;
 428         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 429                 /* Walk the singles. */
 430                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 431                         out << stel->value->id << ", ";
 432                         if ( ++totalTrans % IALL == 0 )
 433                                 out << endl << "        ";
 434                 }
 435
 436                 /* Walk the ranges. */
 437                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 438                         out << rtel->value->id << ", ";
 439                         if ( ++totalTrans % IALL == 0 )
 440                                 out << endl << "        ";
 441                 }
 442
 443                 /* The state's default index goes next. */
 444                 if ( st->defTrans != 0 ) {
 445                         out << st->defTrans->id << ", ";
 446                         if ( ++totalTrans % IALL == 0 )
 447                                 out << endl << "        ";
 448                 }
 449         }
 450
 451         out << endl;
 452         return out;
 453 }
 454
 455 std::ostream &GoTabCodeGen::TRANS_TARGS()
 456 {
 457         out << "        ";
 458         int totalTrans = 0;
 459         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 460                 /* Walk the singles. */
 461                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 462                         RedTransAp *trans = stel->value;
 463                         out << trans->targ->id << ", ";
 464                         if ( ++totalTrans % IALL == 0 )
 465                                 out << endl << "        ";
 466                 }
 467
 468                 /* Walk the ranges. */
 469                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 470                         RedTransAp *trans = rtel->value;
 471                         out << trans->targ->id << ", ";
 472                         if ( ++totalTrans % IALL == 0 )
 473                                 out << endl << "        ";
 474                 }
 475
 476                 /* The state's default target state. */
 477                 if ( st->defTrans != 0 ) {
 478                         RedTransAp *trans = st->defTrans;
 479                         out << trans->targ->id << ", ";
 480                         if ( ++totalTrans % IALL == 0 )
 481                                 out << endl << "        ";
 482                 }
 483         }
 484
 485         /* Add any eof transitions that have not yet been written out above. */
 486         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 487                 if ( st->eofTrans != 0 ) {
 488                         RedTransAp *trans = st->eofTrans;
 489                         trans->pos = totalTrans;
 490                         out << trans->targ->id << ", ";
 491                         if ( ++totalTrans % IALL == 0 )
 492                                 out << endl << "        ";
 493                 }
 494         }
 495
 496
 497         out << endl;
 498         return out;
 499 }
 500
 501
 502 std::ostream &GoTabCodeGen::TRANS_ACTIONS()
 503 {
 504         out << "        ";
 505         int totalTrans = 0;
 506         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 507                 /* Walk the singles. */
 508                 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
 509                         RedTransAp *trans = stel->value;
 510                         TRANS_ACTION( trans ) << ", ";
 511                         if ( ++totalTrans % IALL == 0 )
 512                                 out << endl << "        ";
 513                 }
 514
 515                 /* Walk the ranges. */
 516                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
 517                         RedTransAp *trans = rtel->value;
 518                         TRANS_ACTION( trans ) << ", ";
 519                         if ( ++totalTrans % IALL == 0 )
 520                                 out << endl << "        ";
 521                 }
 522
 523                 /* The state's default index goes next. */
 524                 if ( st->defTrans != 0 ) {
 525                         RedTransAp *trans = st->defTrans;
 526                         TRANS_ACTION( trans ) << ", ";
 527                         if ( ++totalTrans % IALL == 0 )
 528                                 out << endl << "        ";
 529                 }
 530         }
 531
 532         /* Add any eof transitions that have not yet been written out above. */
 533         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
 534                 if ( st->eofTrans != 0 ) {
 535                         RedTransAp *trans = st->eofTrans;
 536                         TRANS_ACTION( trans ) << ", ";
 537                         if ( ++totalTrans % IALL == 0 )
 538                                 out << endl << "        ";
 539                 }
 540         }
 541
 542         out << endl;
 543         return out;
 544 }
 545
 546 std::ostream &GoTabCodeGen::TRANS_TARGS_WI()
 547 {
 548         /* Transitions must be written ordered by their id. */
 549         RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
 550         for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
 551                 transPtrs[trans->id] = trans;
 552
 553         /* Keep a count of the num of items in the array written. */
 554         out << "        ";
 555         int totalStates = 0;
 556         for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
 557                 /* Record the position, need this for eofTrans. */
 558                 RedTransAp *trans = transPtrs[t];
 559                 trans->pos = t;
 560
 561                 /* Write out the target state. */
 562                 out << trans->targ->id << ", ";
 563                 if ( t < redFsm->transSet.length()-1 ) {
 564                         if ( ++totalStates % IALL == 0 )
 565                                 out << endl << "        ";
 566                 }
 567         }
 568         out << endl;
 569         delete[] transPtrs;
 570         return out;
 571 }
 572
 573
 574 std::ostream &GoTabCodeGen::TRANS_ACTIONS_WI()
 575 {
 576         /* Transitions must be written ordered by their id. */
 577         RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
 578         for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
 579                 transPtrs[trans->id] = trans;
 580
 581         /* Keep a count of the num of items in the array written. */
 582         out << "        ";
 583         int totalAct = 0;
 584         for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
 585                 /* Write the function for the transition. */
 586                 RedTransAp *trans = transPtrs[t];
 587                 TRANS_ACTION( trans );
 588                 out << ", ";
 589                 if ( t < redFsm->transSet.length()-1 ) {
 590                         if ( ++totalAct % IALL == 0 )
 591                                 out << endl << "        ";
 592                 }
 593         }
 594         out << endl;
 595         delete[] transPtrs;
 596         return out;
 597 }
 598
 599 void GoTabCodeGen::writeData()
 600 {
 601         /* If there are any transtion functions then output the array. If there
 602          * are none, don't bother emitting an empty array that won't be used. */
 603         if ( redFsm->anyActions() ) {
 604                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActArrItem), A() );
 605                 ACTIONS_ARRAY();
 606                 CLOSE_ARRAY() << endl;
 607         }
 608
 609         if ( redFsm->anyConditions() ) {
 610                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondOffset), CO() );
 611                 COND_OFFSETS();
 612                 CLOSE_ARRAY() << endl;
 613
 614                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondLen), CL() );
 615                 COND_LENS();
 616                 CLOSE_ARRAY() << endl;
 617
 618                 OPEN_ARRAY( WIDE_ALPH_TYPE(), CK() );
 619                 COND_KEYS();
 620                 CLOSE_ARRAY() << endl;
 621
 622                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondSpaceId), C() );
 623                 COND_SPACES();
 624                 CLOSE_ARRAY() << endl;
 625         }
 626
 627         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxKeyOffset), KO() );
 628         KEY_OFFSETS();
 629         CLOSE_ARRAY() << endl;
 630
 631         OPEN_ARRAY( WIDE_ALPH_TYPE(), K() );
 632         KEYS();
 633         CLOSE_ARRAY() << endl;
 634
 635         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxSingleLen), SL() );
 636         SINGLE_LENS();
 637         CLOSE_ARRAY() << endl;
 638
 639         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxRangeLen), RL() );
 640         RANGE_LENS();
 641         CLOSE_ARRAY() << endl;
 642
 643         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset), IO() );
 644         INDEX_OFFSETS();
 645         CLOSE_ARRAY() << endl;
 646
 647         if ( useIndicies ) {
 648                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex), I() );
 649                 INDICIES();
 650                 CLOSE_ARRAY() << endl;
 651
 652                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 653                 TRANS_TARGS_WI();
 654                 CLOSE_ARRAY() << endl;
 655
 656                 if ( redFsm->anyActions() ) {
 657                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
 658                         TRANS_ACTIONS_WI();
 659                         CLOSE_ARRAY() << endl;
 660                 }
 661         }
 662         else {
 663                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
 664                 TRANS_TARGS();
 665                 CLOSE_ARRAY() << endl;
 666
 667                 if ( redFsm->anyActions() ) {
 668                         OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
 669                         TRANS_ACTIONS();
 670                         CLOSE_ARRAY() << endl;
 671                 }
 672         }
 673
 674         if ( redFsm->anyToStateActions() ) {
 675                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
 676                 TO_STATE_ACTIONS();
 677                 CLOSE_ARRAY() << endl;
 678         }
 679
 680         if ( redFsm->anyFromStateActions() ) {
 681                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
 682                 FROM_STATE_ACTIONS();
 683                 CLOSE_ARRAY() << endl;
 684         }
 685
 686         if ( redFsm->anyEofActions() ) {
 687                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), EA() );
 688                 EOF_ACTIONS();
 689                 CLOSE_ARRAY() << endl;
 690         }
 691
 692         if ( redFsm->anyEofTrans() ) {
 693                 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset+1), ET() );
 694                 EOF_TRANS();
 695                 CLOSE_ARRAY() << endl;
 696         }
 697
 698         STATE_IDS();
 699 }
 700
 701 void GoTabCodeGen::LOCATE_TRANS()
 702 {
 703         out <<
 704                 "       _keys = " << CAST(INT(), KO() + "[" + vCS() + "]") << endl <<
 705                 "       _trans = " << CAST(INT(), IO() + "[" + vCS() + "]") << endl <<
 706                 endl <<
 707                 "       _klen = " << CAST(INT(), SL() + "[" + vCS() + "]") << endl <<
 708                 "       if _klen > 0 {" << endl <<
 709                 "               _lower := " << CAST(INT(), "_keys") << endl <<
 710                 "               var _mid " << INT() << endl <<
 711                 "               _upper := " << CAST(INT(), "_keys + _klen - 1") << endl <<
 712                 "               for {" << endl <<
 713                 "                       if _upper < _lower {" << endl <<
 714                 "                               break" << endl <<
 715                 "                       }" << endl <<
 716                 endl <<
 717                 "                       _mid = _lower + ((_upper - _lower) >> 1)" << endl <<
 718                 "                       switch {" << endl <<
 719                 "                       case " << GET_WIDE_KEY() << " < " << K() << "[_mid]" << ":" << endl <<
 720                 "                               _upper = _mid - 1" << endl <<
 721                 "                       case " << GET_WIDE_KEY() << " > " << K() << "[_mid]" << ":" << endl <<
 722                 "                               _lower = _mid + 1" << endl <<
 723                 "                       default:" << endl <<
 724                 "                               _trans += " << CAST(INT(), "_mid - " + CAST(INT(), "_keys")) << endl <<
 725                 "                               goto _match" << endl <<
 726                 "                       }" << endl <<
 727                 "               }" << endl <<
 728                 "               _keys += _klen" << endl <<
 729                 "               _trans += _klen" << endl <<
 730                 "       }" << endl <<
 731                 endl <<
 732                 "       _klen = " << CAST(INT(), RL() + "[" + vCS() + "]") << endl <<
 733                 "       if _klen > 0 {" << endl <<
 734                 "               _lower := " << CAST(INT(), "_keys") << endl <<
 735                 "               var _mid " << INT() << endl <<
 736                 "               _upper := " << CAST(INT(), "_keys + (_klen << 1) - 2") << endl <<
 737                 "               for {" << endl <<
 738                 "                       if _upper < _lower {" << endl <<
 739                 "                               break" << endl <<
 740                 "                       }" << endl <<
 741                 endl <<
 742                 "                       _mid = _lower + (((_upper - _lower) >> 1) & ^1)" << endl <<
 743                 "                       switch {" << endl <<
 744                 "                       case " << GET_WIDE_KEY() << " < " << K() << "[_mid]" << ":" << endl <<
 745                 "                               _upper = _mid - 2" << endl <<
 746                 "                       case " << GET_WIDE_KEY() << " > " << K() << "[_mid + 1]" << ":" << endl <<
 747                 "                               _lower = _mid + 2" << endl <<
 748                 "                       default:" << endl <<
 749                 "                               _trans += " << CAST(INT(), "(_mid - " + CAST(INT(), "_keys") + ") >> 1") << endl <<
 750                 "                               goto _match" << endl <<
 751                 "                       }" << endl <<
 752                 "               }" << endl <<
 753                 "               _trans += _klen" << endl <<
 754                 "       }" << endl <<
 755                 endl;
 756 }
 757
 758 void GoTabCodeGen::COND_TRANSLATE()
 759 {
 760         out <<
 761                 "       _widec = " << CAST(WIDE_ALPH_TYPE(), GET_KEY()) << endl <<
 762                 "       _klen = " << CAST(INT(), CL() + "[" + vCS() + "]") << endl <<
 763                 "       _keys = " << CAST(INT(), CO() + "[" + vCS() + "] * 2") << endl <<
 764                 "       if _klen > 0 {" << endl <<
 765                 "               _lower := " << CAST(INT(), "_keys") << endl <<
 766                 "               var _mid " << INT() << endl <<
 767                 "               _upper := " << CAST(INT(), "_keys + (_klen << 1) - 2") << endl <<
 768                 "       COND_LOOP:" << endl <<
 769                 "               for {" << endl <<
 770                 "                       if _upper < _lower {" << endl <<
 771                 "                               break" << endl <<
 772                 "                       }" << endl <<
 773                 endl <<
 774                 "                       _mid = _lower + (((_upper - _lower) >> 1) & ^1)" << endl <<
 775                 "                       switch {" << endl <<
 776                 "                       case " << GET_WIDE_KEY() << " < " << CAST(WIDE_ALPH_TYPE(), CK() + "[_mid]") << ":" << endl <<
 777                 "                               _upper = _mid - 2" << endl <<
 778                 "                       case " << GET_WIDE_KEY() << " > " << CAST(WIDE_ALPH_TYPE(), CK() + "[_mid + 1]") << ":" << endl <<
 779                 "                               _lower = _mid + 2" << endl <<
 780                 "                       default:" << endl <<
 781                 "                               switch " << C() << "[" << CAST(INT(), CO() + "[" + vCS() + "]") <<
 782                                                         " + ((_mid - _keys)>>1)] {" << endl;
 783
 784         for ( CondSpaceList::Iter csi = condSpaceList; csi.lte(); csi++ ) {
 785                 GenCondSpace *condSpace = csi;
 786                 out << TABS(4) << "case " << condSpace->condSpaceId << ":" << endl;
 787                 out << TABS(5) << "_widec = " << KEY(condSpace->baseKey) << " + (" << CAST(WIDE_ALPH_TYPE(), GET_KEY()) <<
 788                                         " - " << KEY(keyOps->minKey) << ")" << endl;
 789
 790                 for ( GenCondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
 791                         out << TABS(5) << "if ";
 792                         CONDITION( out, *csi );
 793                         Size condValOffset = ((1 << csi.pos()) * keyOps->alphSize());
 794                         out << " {" << endl << TABS(6) << "_widec += " << condValOffset << endl << TABS(5) << "}" << endl;
 795                 }
 796         }
 797
 798         out <<
 799                 "                               }" << endl <<
 800                 "                               break COND_LOOP" << endl <<
 801                 "                       }" << endl <<
 802                 "               }" << endl <<
 803                 "       }" << endl <<
 804                 endl;
 805 }
 806
 807 void GoTabCodeGen::writeExec()
 808 {
 809         testEofUsed = false;
 810         outLabelUsed = false;
 811
 812         out <<
 813                 "       {" << endl <<
 814                 "       var _klen " << INT() << endl;
 815
 816         if ( redFsm->anyRegCurStateRef() )
 817                 out << "        var _ps " << INT() << endl;
 818
 819         out <<
 820                 "       var _trans " << INT() << endl;
 821
 822         if ( redFsm->anyConditions() )
 823                 out << "        var _widec " << WIDE_ALPH_TYPE() << endl;
 824
 825         if ( redFsm->anyToStateActions() || redFsm->anyRegActions()
 826                         || redFsm->anyFromStateActions() )
 827         {
 828                 out <<
 829                         "       var _acts " << INT() << endl <<
 830                         "       var _nacts " << UINT() << endl;
 831         }
 832
 833         out <<
 834                 "       var _keys " << INT() << endl;
 835
 836         if ( !noEnd ) {
 837                 testEofUsed = true;
 838                 out <<
 839                         "       if " << P() << " == " << PE() << " {" << endl <<
 840                         "               goto _test_eof" << endl <<
 841                         "       }" << endl;
 842         }
 843
 844         if ( redFsm->errState != 0 ) {
 845                 outLabelUsed = true;
 846                 out <<
 847                         "       if " << vCS() << " == " << redFsm->errState->id << " {" << endl <<
 848                         "               goto _out" << endl <<
 849                         "       }" << endl;
 850         }
 851
 852         out << "_resume:" << endl;
 853
 854         if ( redFsm->anyFromStateActions() ) {
 855                 out <<
 856                         "       _acts = " << CAST(INT(), FSA() + "[" + vCS() + "]") << endl <<
 857                         "       _nacts = " << CAST(UINT(), A() + "[_acts]") << "; _acts++" << endl <<
 858                         "       for ; _nacts > 0; _nacts-- {" << endl <<
 859                         "                _acts++" << endl <<
 860                         "               switch " << A() << "[_acts - 1]" << " {" << endl;
 861                         FROM_STATE_ACTION_SWITCH(2);
 862                         out <<
 863                         "               }" << endl <<
 864                         "       }" << endl << endl;
 865         }
 866
 867         if ( redFsm->anyConditions() )
 868                 COND_TRANSLATE();
 869
 870         LOCATE_TRANS();
 871
 872         out << "_match:" << endl;
 873
 874         if ( useIndicies )
 875                 out << "        _trans = " << CAST(INT(), I() + "[_trans]") << endl;
 876
 877         if ( redFsm->anyEofTrans() )
 878                 out << "_eof_trans:" << endl;
 879
 880         if ( redFsm->anyRegCurStateRef() )
 881                 out << "        _ps = " << vCS() << endl;
 882
 883         out <<
 884                 "       " << vCS() << " = " << CAST(INT(), TT() + "[_trans]") << endl << endl;
 885
 886         if ( redFsm->anyRegActions() ) {
 887                 out <<
 888                         "       if " << TA() << "[_trans] == 0 {" <<  endl <<
 889                         "               goto _again" << endl <<
 890                         "       }" << endl <<
 891                         endl <<
 892                         "       _acts = " << CAST(INT(), TA() + "[_trans]") << endl <<
 893                         "       _nacts = " << CAST(UINT(), A() + "[_acts]") << "; _acts++" << endl <<
 894                         "       for ; _nacts > 0; _nacts-- {" << endl <<
 895                         "               _acts++" << endl <<
 896                         "               switch " << A() << "[_acts-1]" << " {" << endl;
 897                         ACTION_SWITCH(2);
 898                         out <<
 899                         "               }" << endl <<
 900                         "       }" << endl << endl;
 901         }
 902
 903         if ( redFsm->anyRegActions() || redFsm->anyActionGotos() ||
 904                         redFsm->anyActionCalls() || redFsm->anyActionRets() )
 905                 out << "_again:" << endl;
 906
 907         if ( redFsm->anyToStateActions() ) {
 908                 out <<
 909                         "       _acts = " << CAST(INT(), TSA() + "[" + vCS() + "]") << endl <<
 910                         "       _nacts = " << CAST(UINT(), A() + "[_acts]") << "; _acts++" << endl <<
 911                         "       for ; _nacts > 0; _nacts-- {" << endl <<
 912                         "               _acts++" << endl <<
 913                         "               switch " << A() << "[_acts-1] {" << endl;
 914                         TO_STATE_ACTION_SWITCH(2);
 915                         out <<
 916                         "               }" << endl <<
 917                         "       }" << endl << endl;
 918         }
 919
 920         if ( redFsm->errState != 0 ) {
 921                 outLabelUsed = true;
 922                 out <<
 923                         "       if " << vCS() << " == " << redFsm->errState->id << " {" << endl <<
 924                         "               goto _out" << endl <<
 925                         "       }" << endl;
 926         }
 927
 928         if ( !noEnd ) {
 929                 out <<
 930                         "       " << P() << "++" << endl <<
 931                         "       if " << P() << " != " << PE() << " {" << endl <<
 932                         "               goto _resume" << endl <<
 933                         "       }" << endl;
 934         }
 935         else {
 936                 out <<
 937                         "       " << P() << "++" << endl <<
 938                         "       goto _resume" << endl;
 939         }
 940
 941         if ( testEofUsed )
 942                 out << "        _test_eof: {}" << endl;
 943
 944         if ( redFsm->anyEofTrans() || redFsm->anyEofActions() ) {
 945                 out <<
 946                         "       if " << P() << " == " << vEOF() << " {" << endl;
 947
 948                 if ( redFsm->anyEofTrans() ) {
 949                         out <<
 950                                 "               if " << ET() << "[" << vCS() << "] > 0 {" << endl <<
 951                                 "                       _trans = " << CAST(INT(), ET() + "[" + vCS() + "] - 1") << endl <<
 952                                 "                       goto _eof_trans" << endl <<
 953                                 "               }" << endl;
 954                 }
 955
 956                 if ( redFsm->anyEofActions() ) {
 957                         out <<
 958                                 "               __acts := " << EA() << "[" << vCS() << "]" << endl <<
 959                                 "               __nacts := " << CAST(UINT(), A() + "[__acts]") << "; __acts++" << endl <<
 960                                 "               for ; __nacts > 0; __nacts-- {" << endl <<
 961                                 "                       __acts++" << endl <<
 962                                 "                       switch " << A() << "[__acts-1] {" << endl;
 963                                 EOF_ACTION_SWITCH(3);
 964                                 out <<
 965                                 "                       }" << endl <<
 966                                 "               }" << endl;
 967                 }
 968
 969                 out <<
 970                         "       }" << endl << endl;
 971         }
 972
 973         if ( outLabelUsed )
 974                 out << "        _out: {}" << endl;
 975
 976         out << "        }" << endl;
 977 }