redfsm/redfsm.cpp

   1 /*
   2  *  Copyright 2001-2006 Adrian Thurston <thurston@cs.queensu.ca>
   3  */
   4
   5 /*  This file is part of Ragel.
   6  *
   7  *  Ragel is free software; you can redistribute it and/or modify
   8  *  it under the terms of the GNU General Public License as published by
   9  *  the Free Software Foundation; either version 2 of the License, or
  10  *  (at your option) any later version.
  11  *
  12  *  Ragel is distributed in the hope that it will be useful,
  13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *  GNU General Public License for more details.
  16  *
  17  *  You should have received a copy of the GNU General Public License
  18  *  along with Ragel; if not, write to the Free Software
  19  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  */
  21
  22 #include "redfsm.h"
  23 #include "avlmap.h"
  24 #include "mergesort.h"
  25 #include <iostream>
  26 #include <sstream>
  27
  28 using std::ostringstream;
  29
  30 KeyOps *keyOps = 0;
  31
  32 string Action::nameOrLoc()
  33 {
  34         if ( name != 0 )
  35                 return string(name);
  36         else {
  37                 ostringstream ret;
  38                 ret << loc.line << ":" << loc.col;
  39                 return ret.str();
  40         }
  41 }
  42
  43 RedFsmAp::RedFsmAp()
  44 :
  45         wantComplete(false),
  46         forcedErrorState(false),
  47         nextActionId(0),
  48         nextTransId(0),
  49         startState(0),
  50         errState(0),
  51         errTrans(0),
  52         firstFinState(0),
  53         numFinStates(0),
  54         bAnyToStateActions(false),
  55         bAnyFromStateActions(false),
  56         bAnyRegActions(false),
  57         bAnyEofActions(false),
  58         bAnyActionGotos(false),
  59         bAnyActionCalls(false),
  60         bAnyActionRets(false),
  61         bAnyRegActionRets(false),
  62         bAnyRegActionByValControl(false),
  63         bAnyRegNextStmt(false),
  64         bAnyRegCurStateRef(false),
  65         bAnyRegBreak(false),
  66         bAnyLmSwitchError(false),
  67         bAnyConditions(false)
  68 {
  69 }
  70
  71 /* Does the machine have any actions. */
  72 bool RedFsmAp::anyActions()
  73 {
  74         return actionMap.length() > 0;
  75 }
  76
  77 void RedFsmAp::depthFirstOrdering( RedStateAp *state )
  78 {
  79         /* Nothing to do if the state is already on the list. */
  80         if ( state->onStateList )
  81                 return;
  82
  83         /* Doing depth first, put state on the list. */
  84         state->onStateList = true;
  85         stateList.append( state );
  86
  87         /* At this point transitions should only be in ranges. */
  88         assert( state->outSingle.length() == 0 );
  89         assert( state->defTrans == 0 );
  90
  91         /* Recurse on everything ranges. */
  92         for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
  93                 if ( rtel->value->targ != 0 )
  94                         depthFirstOrdering( rtel->value->targ );
  95         }
  96 }
  97
  98 /* Ordering states by transition connections. */
  99 void RedFsmAp::depthFirstOrdering()
 100 {
 101         /* Init on state list flags. */
 102         for ( RedStateList::Iter st = stateList; st.lte(); st++ )
 103                 st->onStateList = false;
 104
 105         /* Clear out the state list, we will rebuild it. */
 106         int stateListLen = stateList.length();
 107         stateList.abandon();
 108
 109         /* Add back to the state list from the start state and all other entry
 110          * points. */
 111         if ( startState != 0 )
 112                 depthFirstOrdering( startState );
 113         for ( RedStateSet::Iter en = entryPoints; en.lte(); en++ )
 114                 depthFirstOrdering( *en );
 115         if ( forcedErrorState )
 116                 depthFirstOrdering( errState );
 117
 118         /* Make sure we put everything back on. */
 119         assert( stateListLen == stateList.length() );
 120 }
 121
 122 /* Assign state ids by appearance in the state list. */
 123 void RedFsmAp::sequentialStateIds()
 124 {
 125         /* Table based machines depend on the state numbers starting at zero. */
 126         nextStateId = 0;
 127         for ( RedStateList::Iter st = stateList; st.lte(); st++ )
 128                 st->id = nextStateId++;
 129 }
 130
 131 /* Stable sort the states by final state status. */
 132 void RedFsmAp::sortStatesByFinal()
 133 {
 134         /* Move forward through the list and throw final states onto the end. */
 135         RedStateAp *state = 0;
 136         RedStateAp *next = stateList.head;
 137         RedStateAp *last = stateList.tail;
 138         while ( state != last ) {
 139                 /* Move forward and load up the next. */
 140                 state = next;
 141                 next = state->next;
 142
 143                 /* Throw to the end? */
 144                 if ( state->isFinal ) {
 145                         stateList.detach( state );
 146                         stateList.append( state );
 147                 }
 148         }
 149 }
 150
 151 /* Assign state ids by final state state status. */
 152 void RedFsmAp::sortStateIdsByFinal()
 153 {
 154         /* Table based machines depend on this starting at zero. */
 155         nextStateId = 0;
 156
 157         /* First pass to assign non final ids. */
 158         for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
 159                 if ( ! st->isFinal )
 160                         st->id = nextStateId++;
 161         }
 162
 163         /* Second pass to assign final ids. */
 164         for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
 165                 if ( st->isFinal )
 166                         st->id = nextStateId++;
 167         }
 168 }
 169
 170 struct CmpStateById
 171 {
 172         static int compare( RedStateAp *st1, RedStateAp *st2 )
 173         {
 174                 if ( st1->id < st2->id )
 175                         return -1;
 176                 else if ( st1->id > st2->id )
 177                         return 1;
 178                 else
 179                         return 0;
 180         }
 181 };
 182
 183 void RedFsmAp::sortByStateId()
 184 {
 185         /* Make the array. */
 186         int pos = 0;
 187         RedStateAp **ptrList = new RedStateAp*[stateList.length()];
 188         for ( RedStateList::Iter st = stateList; st.lte(); st++, pos++ )
 189                 ptrList[pos] = st;
 190
 191         MergeSort<RedStateAp*, CmpStateById> mergeSort;
 192         mergeSort.sort( ptrList, stateList.length() );
 193
 194         stateList.abandon();
 195         for ( int st = 0; st < pos; st++ )
 196                 stateList.append( ptrList[st] );
 197
 198         delete[] ptrList;
 199 }
 200
 201 /* Find the final state with the lowest id. */
 202 void RedFsmAp::findFirstFinState()
 203 {
 204         for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
 205                 if ( st->isFinal && (firstFinState == 0 || st->id < firstFinState->id) )
 206                         firstFinState = st;
 207         }
 208 }
 209
 210 void RedFsmAp::assignActionLocs()
 211 {
 212         int nextLocation = 0;
 213         for ( ActionTableMap::Iter act = actionMap; act.lte(); act++ ) {
 214                 /* Store the loc, skip over the array and a null terminator. */
 215                 act->location = nextLocation;
 216                 nextLocation += act->key.length() + 1;
 217         }
 218 }
 219
 220 /* Check if we can extend the current range by displacing any ranges
 221  * ahead to the singles. */
 222 bool RedFsmAp::canExtend( const RedTransList &list, int pos )
 223 {
 224         /* Get the transition that we want to extend. */
 225         RedTransAp *extendTrans = list[pos].value;
 226
 227         /* Look ahead in the transition list. */
 228         for ( int next = pos + 1; next < list.length(); pos++, next++ ) {
 229                 /* If they are not continuous then cannot extend. */
 230                 Key nextKey = list[next].lowKey;
 231                 nextKey.decrement();
 232                 if ( list[pos].highKey != nextKey )
 233                         break;
 234
 235                 /* Check for the extenstion property. */
 236                 if ( extendTrans == list[next].value )
 237                         return true;
 238
 239                 /* If the span of the next element is more than one, then don't keep
 240                  * checking, it won't be moved to single. */
 241                 unsigned long long nextSpan = keyOps->span( list[next].lowKey, list[next].highKey );
 242                 if ( nextSpan > 1 )
 243                         break;
 244         }
 245         return false;
 246 }
 247
 248 /* Move ranges to the singles list. */
 249 void RedFsmAp::moveTransToSingle( RedStateAp *state )
 250 {
 251         RedTransList &range = state->outRange;
 252         RedTransList &single = state->outSingle;
 253         for ( int rpos = 0; rpos < range.length(); ) {
 254                 /* Check if this is a range we can extend. */
 255                 if ( canExtend( range, rpos ) ) {
 256                         /* Transfer singles over. */
 257                         while ( range[rpos].value != range[rpos+1].value ) {
 258                                 /* Transfer the range to single. */
 259                                 single.append( range[rpos+1] );
 260                                 range.remove( rpos+1 );
 261                         }
 262
 263                         /* Extend. */
 264                         range[rpos].highKey = range[rpos+1].highKey;
 265                         range.remove( rpos+1 );
 266                 }
 267                 /* Maybe move it to the singles. */
 268                 else if ( keyOps->span( range[rpos].lowKey, range[rpos].highKey ) == 1 ) {
 269                         single.append( range[rpos] );
 270                         range.remove( rpos );
 271                 }
 272                 else {
 273                         /* Keeping it in the ranges. */
 274                         rpos += 1;
 275                 }
 276         }
 277 }
 278
 279 /* Look through ranges and choose suitable single character transitions. */
 280 void RedFsmAp::chooseSingle()
 281 {
 282         /* Loop the states. */
 283         for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
 284                 /* Rewrite the transition list taking out the suitable single
 285                  * transtions. */
 286                 moveTransToSingle( st );
 287         }
 288 }
 289
 290 void RedFsmAp::makeFlat()
 291 {
 292         for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
 293                 if ( st->stateCondList.length() == 0 ) {
 294                         st->condLowKey = 0;
 295                         st->condHighKey = 0;
 296                 }
 297                 else {
 298                         st->condLowKey = st->stateCondList.head->lowKey;
 299                         st->condHighKey = st->stateCondList.tail->highKey;
 300
 301                         unsigned long long span = keyOps->span( st->condLowKey, st->condHighKey );
 302                         st->condList = new CondSpace*[ span ];
 303                         memset( st->condList, 0, sizeof(CondSpace*)*span );
 304
 305                         for ( StateCondList::Iter sci = st->stateCondList; sci.lte(); sci++ ) {
 306                                 unsigned long long base, trSpan;
 307                                 base = keyOps->span( st->condLowKey, sci->lowKey )-1;
 308                                 trSpan = keyOps->span( sci->lowKey, sci->highKey );
 309                                 for ( unsigned long long pos = 0; pos < trSpan; pos++ )
 310                                         st->condList[base+pos] = sci->condSpace;
 311                         }
 312                 }
 313
 314                 if ( st->outRange.length() == 0 ) {
 315                         st->lowKey = st->highKey = 0;
 316                         st->transList = 0;
 317                 }
 318                 else {
 319                         st->lowKey = st->outRange[0].lowKey;
 320                         st->highKey = st->outRange[st->outRange.length()-1].highKey;
 321                         unsigned long long span = keyOps->span( st->lowKey, st->highKey );
 322                         st->transList = new RedTransAp*[ span ];
 323                         memset( st->transList, 0, sizeof(RedTransAp*)*span );
 324
 325                         for ( RedTransList::Iter trans = st->outRange; trans.lte(); trans++ ) {
 326                                 unsigned long long base, trSpan;
 327                                 base = keyOps->span( st->lowKey, trans->lowKey )-1;
 328                                 trSpan = keyOps->span( trans->lowKey, trans->highKey );
 329                                 for ( unsigned long long pos = 0; pos < trSpan; pos++ )
 330                                         st->transList[base+pos] = trans->value;
 331                         }
 332
 333                         /* Fill in the gaps with the default transition. */
 334                         for ( unsigned long long pos = 0; pos < span; pos++ ) {
 335                                 if ( st->transList[pos] == 0 )
 336                                         st->transList[pos] = st->defTrans;
 337                         }
 338                 }
 339         }
 340 }
 341
 342
 343 /* A default transition has been picked, move it from the outRange to the
 344  * default pointer. */
 345 void RedFsmAp::moveToDefault( RedTransAp *defTrans, RedStateAp *state )
 346 {
 347         /* Rewrite the outRange, omitting any ranges that use
 348          * the picked default. */
 349         RedTransList outRange;
 350         for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
 351                 /* If it does not take the default, copy it over. */
 352                 if ( rtel->value != defTrans )
 353                         outRange.append( *rtel );
 354         }
 355
 356         /* Save off the range we just created into the state's range. */
 357         state->outRange.transfer( outRange );
 358
 359         /* Store the default. */
 360         state->defTrans = defTrans;
 361 }
 362
 363 bool RedFsmAp::alphabetCovered( RedTransList &outRange )
 364 {
 365         /* Cannot cover without any out ranges. */
 366         if ( outRange.length() == 0 )
 367                 return false;
 368
 369         /* If the first range doesn't start at the the lower bound then the
 370          * alphabet is not covered. */
 371         RedTransList::Iter rtel = outRange;
 372         if ( keyOps->minKey < rtel->lowKey )
 373                 return false;
 374
 375         /* Check that every range is next to the previous one. */
 376         rtel.increment();
 377         for ( ; rtel.lte(); rtel++ ) {
 378                 Key highKey = rtel[-1].highKey;
 379                 highKey.increment();
 380                 if ( highKey != rtel->lowKey )
 381                         return false;
 382         }
 383
 384         /* The last must extend to the upper bound. */
 385         RedTransEl *last = &outRange[outRange.length()-1];
 386         if ( last->highKey < keyOps->maxKey )
 387                 return false;
 388
 389         return true;
 390 }
 391
 392 RedTransAp *RedFsmAp::chooseDefaultSpan( RedStateAp *state )
 393 {
 394         /* Make a set of transitions from the outRange. */
 395         RedTransSet stateTransSet;
 396         for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ )
 397                 stateTransSet.insert( rtel->value );
 398
 399         /* For each transition in the find how many alphabet characters the
 400          * transition spans. */
 401         unsigned long long *span = new unsigned long long[stateTransSet.length()];
 402         memset( span, 0, sizeof(unsigned long long) * stateTransSet.length() );
 403         for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
 404                 /* Lookup the transition in the set. */
 405                 RedTransAp **inSet = stateTransSet.find( rtel->value );
 406                 int pos = inSet - stateTransSet.data;
 407                 span[pos] += keyOps->span( rtel->lowKey, rtel->highKey );
 408         }
 409
 410         /* Find the max span, choose it for making the default. */
 411         RedTransAp *maxTrans = 0;
 412         unsigned long long maxSpan = 0;
 413         for ( RedTransSet::Iter rtel = stateTransSet; rtel.lte(); rtel++ ) {
 414                 if ( span[rtel.pos()] > maxSpan ) {
 415                         maxSpan = span[rtel.pos()];
 416                         maxTrans = *rtel;
 417                 }
 418         }
 419
 420         delete[] span;
 421         return maxTrans;
 422 }
 423
 424 /* Pick default transitions from ranges for the states. */
 425 void RedFsmAp::chooseDefaultSpan()
 426 {
 427         /* Loop the states. */
 428         for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
 429                 /* Only pick a default transition if the alphabet is covered. This
 430                  * avoids any transitions in the out range that go to error and avoids
 431                  * the need for an ERR state. */
 432                 if ( alphabetCovered( st->outRange ) ) {
 433                         /* Pick a default transition by largest span. */
 434                         RedTransAp *defTrans = chooseDefaultSpan( st );
 435
 436                         /* Rewrite the transition list taking out the transition we picked
 437                          * as the default and store the default. */
 438                         moveToDefault( defTrans, st );
 439                 }
 440         }
 441 }
 442
 443 RedTransAp *RedFsmAp::chooseDefaultGoto( RedStateAp *state )
 444 {
 445         /* Make a set of transitions from the outRange. */
 446         RedTransSet stateTransSet;
 447         for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
 448                 if ( rtel->value->targ == state->next )
 449                         return rtel->value;
 450         }
 451         return 0;
 452 }
 453
 454 void RedFsmAp::chooseDefaultGoto()
 455 {
 456         /* Loop the states. */
 457         for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
 458                 /* Pick a default transition. */
 459                 RedTransAp *defTrans = chooseDefaultGoto( st );
 460                 if ( defTrans == 0 )
 461                         defTrans = chooseDefaultSpan( st );
 462
 463                 /* Rewrite the transition list taking out the transition we picked
 464                  * as the default and store the default. */
 465                 moveToDefault( defTrans, st );
 466         }
 467 }
 468
 469 RedTransAp *RedFsmAp::chooseDefaultNumRanges( RedStateAp *state )
 470 {
 471         /* Make a set of transitions from the outRange. */
 472         RedTransSet stateTransSet;
 473         for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ )
 474                 stateTransSet.insert( rtel->value );
 475
 476         /* For each transition in the find how many ranges use the transition. */
 477         int *numRanges = new int[stateTransSet.length()];
 478         memset( numRanges, 0, sizeof(int) * stateTransSet.length() );
 479         for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
 480                 /* Lookup the transition in the set. */
 481                 RedTransAp **inSet = stateTransSet.find( rtel->value );
 482                 numRanges[inSet - stateTransSet.data] += 1;
 483         }
 484
 485         /* Find the max number of ranges. */
 486         RedTransAp *maxTrans = 0;
 487         int maxNumRanges = 0;
 488         for ( RedTransSet::Iter rtel = stateTransSet; rtel.lte(); rtel++ ) {
 489                 if ( numRanges[rtel.pos()] > maxNumRanges ) {
 490                         maxNumRanges = numRanges[rtel.pos()];
 491                         maxTrans = *rtel;
 492                 }
 493         }
 494
 495         delete[] numRanges;
 496         return maxTrans;
 497 }
 498
 499 void RedFsmAp::chooseDefaultNumRanges()
 500 {
 501         /* Loop the states. */
 502         for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
 503                 /* Pick a default transition. */
 504                 RedTransAp *defTrans = chooseDefaultNumRanges( st );
 505
 506                 /* Rewrite the transition list taking out the transition we picked
 507                  * as the default and store the default. */
 508                 moveToDefault( defTrans, st );
 509         }
 510 }
 511
 512 RedTransAp *RedFsmAp::getErrorTrans( )
 513 {
 514         /* If the error trans has not been made aready, make it. */
 515         if ( errTrans == 0 ) {
 516                 /* This insert should always succeed since no transition created by
 517                  * the user can point to the error state. */
 518                 errTrans = new RedTransAp( getErrorState(), 0, nextTransId++ );
 519                 RedTransAp *inRes = transSet.insert( errTrans );
 520                 assert( inRes != 0 );
 521         }
 522         return errTrans;
 523 }
 524
 525 RedStateAp *RedFsmAp::getErrorState()
 526 {
 527         /* Something went wrong. An error state is needed but one was not supplied
 528          * by the frontend. */
 529         assert( errState != 0 );
 530         return errState;
 531 }
 532
 533
 534 RedTransAp *RedFsmAp::allocateTrans( RedStateAp *targ, RedAction *action )
 535 {
 536         /* Create a reduced trans and look for it in the transiton set. */
 537         RedTransAp redTrans( targ, action, 0 );
 538         RedTransAp *inDict = transSet.find( &redTrans );
 539         if ( inDict == 0 ) {
 540                 inDict = new RedTransAp( targ, action, nextTransId++ );
 541                 transSet.insert( inDict );
 542         }
 543         return inDict;
 544 }
 545
 546 void RedFsmAp::partitionFsm( int nparts )
 547 {
 548         /* At this point the states are ordered by a depth-first traversal. We
 549          * will allocate to partitions based on this ordering. */
 550         this->nParts = nparts;
 551         int partSize = stateList.length() / nparts;
 552         int remainder = stateList.length() % nparts;
 553         int numInPart = partSize;
 554         int partition = 0;
 555         if ( remainder-- > 0 )
 556                 numInPart += 1;
 557         for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
 558                 st->partition = partition;
 559
 560                 numInPart -= 1;
 561                 if ( numInPart == 0 ) {
 562                         partition += 1;
 563                         numInPart = partSize;
 564                         if ( remainder-- > 0 )
 565                                 numInPart += 1;
 566                 }
 567         }
 568 }
 569
 570 void RedFsmAp::setInTrans()
 571 {
 572         /* First pass counts the number of transitions. */
 573         for ( TransApSet::Iter trans = transSet; trans.lte(); trans++ )
 574                 trans->targ->numInTrans += 1;
 575
 576         /* Pass over states to allocate the needed memory. Reset the counts so we
 577          * can use them as the current size. */
 578         for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
 579                 st->inTrans = new RedTransAp*[st->numInTrans];
 580                 st->numInTrans = 0;
 581         }
 582
 583         /* Second pass over transitions copies pointers into the in trans list. */
 584         for ( TransApSet::Iter trans = transSet; trans.lte(); trans++ )
 585                 trans->targ->inTrans[trans->targ->numInTrans++] = trans;
 586 }