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