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