ragel/redfsm.cpp

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