ragel/fsmbase.cpp

   1 /*
   2  *  Copyright 2001-2007 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 <string.h>
  23 #include <assert.h>
  24 #include "fsmgraph.h"
  25
  26 /* Simple singly linked list append routine for the fill list. The new state
  27  * goes to the end of the list. */
  28 void MergeData::fillListAppend( StateAp *state )
  29 {
  30         state->alg.next = 0;
  31
  32         if ( stfillHead == 0 ) {
  33                 /* List is empty, state becomes head and tail. */
  34                 stfillHead = state;
  35                 stfillTail = state;
  36         }
  37         else {
  38                 /* List is not empty, state goes after last element. */
  39                 stfillTail->alg.next = state;
  40                 stfillTail = state;
  41         }
  42 }
  43
  44 /* Graph constructor. */
  45 FsmAp::FsmAp()
  46 :
  47         /* No start state. */
  48         startState(0),
  49         errState(0),
  50
  51         /* Misfit accounting is a switch, turned on only at specific times. It
  52          * controls what happens when states have no way in from the outside
  53          * world.. */
  54         misfitAccounting(false)
  55 {
  56 }
  57
  58 /* Copy all graph data including transitions. */
  59 FsmAp::FsmAp( const FsmAp &graph )
  60 :
  61         /* Lists start empty. Will be filled by copy. */
  62         stateList(),
  63         misfitList(),
  64
  65         /* Copy in the entry points,
  66          * pointers will be resolved later. */
  67         entryPoints(graph.entryPoints),
  68         startState(graph.startState),
  69         errState(0),
  70
  71         /* Will be filled by copy. */
  72         finStateSet(),
  73
  74         /* Misfit accounting is only on during merging. */
  75         misfitAccounting(false)
  76 {
  77         /* Create the states and record their map in the original state. */
  78         StateList::Iter origState = graph.stateList;
  79         for ( ; origState.lte(); origState++ ) {
  80                 /* Make the new state. */
  81                 StateAp *newState = new StateAp( *origState );
  82
  83                 /* Add the state to the list.  */
  84                 stateList.append( newState );
  85
  86                 /* Set the mapsTo item of the old state. */
  87                 origState->alg.stateMap = newState;
  88         }
  89
  90         /* Derefernce all the state maps. */
  91         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
  92                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
  93                         /* The points to the original in the src machine. The taget's duplicate
  94                          * is in the statemap. */
  95                         StateAp *toState = trans->toState != 0 ? trans->toState->alg.stateMap : 0;
  96
  97                         /* Attach The transition to the duplicate. */
  98                         trans->toState = 0;
  99                         attachTrans( state, toState, trans );
 100                 }
 101
 102                 /* Fix the eofTarg, if set. */
 103                 if ( state->eofTarget != 0 )
 104                         state->eofTarget = state->eofTarget->alg.stateMap;
 105         }
 106
 107         /* Fix the state pointers in the entry points array. */
 108         EntryMapEl *eel = entryPoints.data;
 109         for ( int e = 0; e < entryPoints.length(); e++, eel++ ) {
 110                 /* Get the duplicate of the state. */
 111                 eel->value = eel->value->alg.stateMap;
 112
 113                 /* Foreign in transitions must be built up when duping machines so
 114                  * increment it here. */
 115                 eel->value->foreignInTrans += 1;
 116         }
 117
 118         /* Fix the start state pointer and the new start state's count of in
 119          * transiions. */
 120         startState = startState->alg.stateMap;
 121         startState->foreignInTrans += 1;
 122
 123         /* Build the final state set. */
 124         StateSet::Iter st = graph.finStateSet;
 125         for ( ; st.lte(); st++ )
 126                 finStateSet.insert((*st)->alg.stateMap);
 127 }
 128
 129 /* Deletes all transition data then deletes each state. */
 130 FsmAp::~FsmAp()
 131 {
 132         /* Delete all the transitions. */
 133         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 134                 /* Iterate the out transitions, deleting them. */
 135                 state->outList.empty();
 136         }
 137
 138         /* Delete all the states. */
 139         stateList.empty();
 140 }
 141
 142 /* Set a state final. The state has its isFinState set to true and the state
 143  * is added to the finStateSet. */
 144 void FsmAp::setFinState( StateAp *state )
 145 {
 146         /* Is it already a fin state. */
 147         if ( state->stateBits & SB_ISFINAL )
 148                 return;
 149
 150         state->stateBits |= SB_ISFINAL;
 151         finStateSet.insert( state );
 152 }
 153
 154 /* Set a state non-final. The has its isFinState flag set false and the state
 155  * is removed from the final state set. */
 156 void FsmAp::unsetFinState( StateAp *state )
 157 {
 158         /* Is it already a non-final state? */
 159         if ( ! (state->stateBits & SB_ISFINAL) )
 160                 return;
 161
 162         /* When a state looses its final state status it must relinquish all the
 163          * properties that are allowed only for final states. */
 164         clearOutData( state );
 165
 166         state->stateBits &= ~ SB_ISFINAL;
 167         finStateSet.remove( state );
 168 }
 169
 170 /* Set and unset a state as the start state. */
 171 void FsmAp::setStartState( StateAp *state )
 172 {
 173         /* Sould change from unset to set. */
 174         assert( startState == 0 );
 175         startState = state;
 176
 177         if ( misfitAccounting ) {
 178                 /* If the number of foreign in transitions is about to go up to 1 then
 179                  * take it off the misfit list and put it on the head list. */
 180                 if ( state->foreignInTrans == 0 )
 181                         stateList.append( misfitList.detach( state ) );
 182         }
 183
 184         /* Up the foreign in transitions to the state. */
 185         state->foreignInTrans += 1;
 186 }
 187
 188 void FsmAp::unsetStartState()
 189 {
 190         /* Should change from set to unset. */
 191         assert( startState != 0 );
 192
 193         /* Decrement the entry's count of foreign entries. */
 194         startState->foreignInTrans -= 1;
 195
 196         if ( misfitAccounting ) {
 197                 /* If the number of foreign in transitions just went down to 0 then take
 198                  * it off the main list and put it on the misfit list. */
 199                 if ( startState->foreignInTrans == 0 )
 200                         misfitList.append( stateList.detach( startState ) );
 201         }
 202
 203         startState = 0;
 204 }
 205
 206 /* Associate an id with a state. Makes the state a named entry point. Has no
 207  * effect if the entry point is already mapped to the state. */
 208 void FsmAp::setEntry( int id, StateAp *state )
 209 {
 210         /* Insert the id into the state. If the state is already labelled with id,
 211          * nothing to do. */
 212         if ( state->entryIds.insert( id ) ) {
 213                 /* Insert the entry and assert that it succeeds. */
 214                 entryPoints.insertMulti( id, state );
 215
 216                 if ( misfitAccounting ) {
 217                         /* If the number of foreign in transitions is about to go up to 1 then
 218                          * take it off the misfit list and put it on the head list. */
 219                         if ( state->foreignInTrans == 0 )
 220                                 stateList.append( misfitList.detach( state ) );
 221                 }
 222
 223                 /* Up the foreign in transitions to the state. */
 224                 state->foreignInTrans += 1;
 225         }
 226 }
 227
 228 /* Remove the association of an id with a state. The state looses it's entry
 229  * point status. Assumes that the id is indeed mapped to state. */
 230 void FsmAp::unsetEntry( int id, StateAp *state )
 231 {
 232         /* Find the entry point in on id. */
 233         EntryMapEl *enLow = 0, *enHigh = 0;
 234         entryPoints.findMulti( id, enLow, enHigh );
 235         while ( enLow->value != state )
 236                 enLow += 1;
 237
 238         /* Remove the record from the map. */
 239         entryPoints.remove( enLow );
 240
 241         /* Remove the state's sense of the link. */
 242         state->entryIds.remove( id );
 243         state->foreignInTrans -= 1;
 244         if ( misfitAccounting ) {
 245                 /* If the number of foreign in transitions just went down to 0 then take
 246                  * it off the main list and put it on the misfit list. */
 247                 if ( state->foreignInTrans == 0 )
 248                         misfitList.append( stateList.detach( state ) );
 249         }
 250 }
 251
 252 /* Remove all association of an id with states. Assumes that the id is indeed
 253  * mapped to a state. */
 254 void FsmAp::unsetEntry( int id )
 255 {
 256         /* Find the entry point in on id. */
 257         EntryMapEl *enLow = 0, *enHigh = 0;
 258         entryPoints.findMulti( id, enLow, enHigh );
 259         for ( EntryMapEl *mel = enLow; mel <= enHigh; mel++ ) {
 260                 /* Remove the state's sense of the link. */
 261                 mel->value->entryIds.remove( id );
 262                 mel->value->foreignInTrans -= 1;
 263                 if ( misfitAccounting ) {
 264                         /* If the number of foreign in transitions just went down to 0
 265                          * then take it off the main list and put it on the misfit list. */
 266                         if ( mel->value->foreignInTrans == 0 )
 267                                 misfitList.append( stateList.detach( mel->value ) );
 268                 }
 269         }
 270
 271         /* Remove the records from the entry points map. */
 272         entryPoints.removeMulti( enLow, enHigh );
 273 }
 274
 275
 276 void FsmAp::changeEntry( int id, StateAp *to, StateAp *from )
 277 {
 278         /* Find the entry in the entry map. */
 279         EntryMapEl *enLow = 0, *enHigh = 0;
 280         entryPoints.findMulti( id, enLow, enHigh );
 281         while ( enLow->value != from )
 282                 enLow += 1;
 283
 284         /* Change it to the new target. */
 285         enLow->value = to;
 286
 287         /* Remove from's sense of the link. */
 288         from->entryIds.remove( id );
 289         from->foreignInTrans -= 1;
 290         if ( misfitAccounting ) {
 291                 /* If the number of foreign in transitions just went down to 0 then take
 292                  * it off the main list and put it on the misfit list. */
 293                 if ( from->foreignInTrans == 0 )
 294                         misfitList.append( stateList.detach( from ) );
 295         }
 296
 297         /* Add to's sense of the link. */
 298         if ( to->entryIds.insert( id ) != 0 ) {
 299                 if ( misfitAccounting ) {
 300                         /* If the number of foreign in transitions is about to go up to 1 then
 301                          * take it off the misfit list and put it on the head list. */
 302                         if ( to->foreignInTrans == 0 )
 303                                 stateList.append( misfitList.detach( to ) );
 304                 }
 305
 306                 /* Up the foreign in transitions to the state. */
 307                 to->foreignInTrans += 1;
 308         }
 309 }
 310
 311
 312 /* Clear all entry points from a machine. */
 313 void FsmAp::unsetAllEntryPoints()
 314 {
 315         for ( EntryMap::Iter en = entryPoints; en.lte(); en++ ) {
 316                 /* Kill all the state's entry points at once. */
 317                 if ( en->value->entryIds.length() > 0 ) {
 318                         en->value->foreignInTrans -= en->value->entryIds.length();
 319
 320                         if ( misfitAccounting ) {
 321                                 /* If the number of foreign in transitions just went down to 0
 322                                  * then take it off the main list and put it on the misfit
 323                                  * list. */
 324                                 if ( en->value->foreignInTrans == 0 )
 325                                         misfitList.append( stateList.detach( en->value ) );
 326                         }
 327
 328                         /* Clear the set of ids out all at once. */
 329                         en->value->entryIds.empty();
 330                 }
 331         }
 332
 333         /* Now clear out the entry map all at once. */
 334         entryPoints.empty();
 335 }
 336
 337 /* Assigning an epsilon transition into final states. */
 338 void FsmAp::epsilonTrans( int id )
 339 {
 340         for ( StateSet::Iter fs = finStateSet; fs.lte(); fs++ )
 341                 (*fs)->epsilonTrans.append( id );
 342 }
 343
 344 /* Mark all states reachable from state. Traverses transitions forward. Used
 345  * for removing states that have no path into them. */
 346 void FsmAp::markReachableFromHere( StateAp *state )
 347 {
 348         /* Base case: return; */
 349         if ( state->stateBits & SB_ISMARKED )
 350                 return;
 351
 352         /* Set this state as processed. We are going to visit all states that this
 353          * state has a transition to. */
 354         state->stateBits |= SB_ISMARKED;
 355
 356         /* Recurse on all out transitions. */
 357         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 358                 if ( trans->toState != 0 )
 359                         markReachableFromHere( trans->toState );
 360         }
 361 }
 362
 363 void FsmAp::markReachableFromHereStopFinal( StateAp *state )
 364 {
 365         /* Base case: return; */
 366         if ( state->stateBits & SB_ISMARKED )
 367                 return;
 368
 369         /* Set this state as processed. We are going to visit all states that this
 370          * state has a transition to. */
 371         state->stateBits |= SB_ISMARKED;
 372
 373         /* Recurse on all out transitions. */
 374         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 375                 StateAp *toState = trans->toState;
 376                 if ( toState != 0 && !toState->isFinState() )
 377                         markReachableFromHereStopFinal( toState );
 378         }
 379 }
 380
 381 /* Mark all states reachable from state. Traverse transitions backwards. Used
 382  * for removing dead end paths in graphs. */
 383 void FsmAp::markReachableFromHereReverse( StateAp *state )
 384 {
 385         /* Base case: return; */
 386         if ( state->stateBits & SB_ISMARKED )
 387                 return;
 388
 389         /* Set this state as processed. We are going to visit all states with
 390          * transitions into this state. */
 391         state->stateBits |= SB_ISMARKED;
 392
 393         /* Recurse on all items in transitions. */
 394         for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ )
 395                 markReachableFromHereReverse( trans->fromState );
 396 }
 397
 398 /* Determine if there are any entry points into a start state other than the
 399  * start state. Setting starting transitions requires that the start state be
 400  * isolated. In most cases a start state will already be isolated. */
 401 bool FsmAp::isStartStateIsolated()
 402 {
 403         /* If there are any in transitions then the state is not isolated. */
 404         if ( startState->inList.head != 0 )
 405                 return false;
 406
 407         /* If there are any entry points then isolated. */
 408         if ( startState->entryIds.length() > 0 )
 409                 return false;
 410
 411         return true;
 412 }
 413
 414 /* Bring in other's entry points. Assumes others states are going to be
 415  * copied into this machine. */
 416 void FsmAp::copyInEntryPoints( FsmAp *other )
 417 {
 418         /* Use insert multi because names are not unique. */
 419         for ( EntryMap::Iter en = other->entryPoints; en.lte(); en++ )
 420                 entryPoints.insertMulti( en->key, en->value );
 421 }
 422
 423
 424 void FsmAp::unsetAllFinStates()
 425 {
 426         for ( StateSet::Iter st = finStateSet; st.lte(); st++ )
 427                 (*st)->stateBits &= ~ SB_ISFINAL;
 428         finStateSet.empty();
 429 }
 430
 431 void FsmAp::setFinBits( int finStateBits )
 432 {
 433         for ( int s = 0; s < finStateSet.length(); s++ )
 434                 finStateSet.data[s]->stateBits |= finStateBits;
 435 }
 436
 437
 438 /* Tests the integrity of the transition lists and the fromStates. */
 439 void FsmAp::verifyIntegrity()
 440 {
 441         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 442                 /* Walk the out transitions and assert fromState is correct. */
 443                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ )
 444                         assert( trans->fromState == state );
 445
 446                 /* Walk the inlist and assert toState is correct. */
 447                 for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ )
 448                         assert( trans->toState == state );
 449         }
 450 }
 451
 452 void FsmAp::verifyReachability()
 453 {
 454         /* Mark all the states that can be reached
 455          * through the set of entry points. */
 456         markReachableFromHere( startState );
 457         for ( EntryMap::Iter en = entryPoints; en.lte(); en++ )
 458                 markReachableFromHere( en->value );
 459
 460         /* Check that everything got marked. */
 461         for ( StateList::Iter st = stateList; st.lte(); st++ ) {
 462                 /* Assert it got marked and then clear the mark. */
 463                 assert( st->stateBits & SB_ISMARKED );
 464                 st->stateBits &= ~ SB_ISMARKED;
 465         }
 466 }
 467
 468 void FsmAp::verifyNoDeadEndStates()
 469 {
 470         /* Mark all states that have paths to the final states. */
 471         for ( StateSet::Iter pst = finStateSet; pst.lte(); pst++ )
 472                 markReachableFromHereReverse( *pst );
 473
 474         /* Start state gets honorary marking. Must be done AFTER recursive call. */
 475         startState->stateBits |= SB_ISMARKED;
 476
 477         /* Make sure everything got marked. */
 478         for ( StateList::Iter st = stateList; st.lte(); st++ ) {
 479                 /* Assert the state got marked and unmark it. */
 480                 assert( st->stateBits & SB_ISMARKED );
 481                 st->stateBits &= ~ SB_ISMARKED;
 482         }
 483 }
 484
 485 void FsmAp::depthFirstOrdering( StateAp *state )
 486 {
 487         /* Nothing to do if the state is already on the list. */
 488         if ( state->stateBits & SB_ONLIST )
 489                 return;
 490
 491         /* Doing depth first, put state on the list. */
 492         state->stateBits |= SB_ONLIST;
 493         stateList.append( state );
 494
 495         /* Recurse on everything ranges. */
 496         for ( TransList::Iter tel = state->outList; tel.lte(); tel++ ) {
 497                 if ( tel->toState != 0 )
 498                         depthFirstOrdering( tel->toState );
 499         }
 500 }
 501
 502 /* Ordering states by transition connections. */
 503 void FsmAp::depthFirstOrdering()
 504 {
 505         /* Init on state list flags. */
 506         for ( StateList::Iter st = stateList; st.lte(); st++ )
 507                 st->stateBits &= ~SB_ONLIST;
 508
 509         /* Clear out the state list, we will rebuild it. */
 510         int stateListLen = stateList.length();
 511         stateList.abandon();
 512
 513         /* Add back to the state list from the start state and all other entry
 514          * points. */
 515         if ( errState != 0 )
 516                 depthFirstOrdering( errState );
 517         depthFirstOrdering( startState );
 518         for ( EntryMap::Iter en = entryPoints; en.lte(); en++ )
 519                 depthFirstOrdering( en->value );
 520
 521         /* Make sure we put everything back on. */
 522         assert( stateListLen == stateList.length() );
 523 }
 524
 525 /* Stable sort the states by final state status. */
 526 void FsmAp::sortStatesByFinal()
 527 {
 528         /* Move forward through the list and throw final states onto the end. */
 529         StateAp *state = 0;
 530         StateAp *next = stateList.head;
 531         StateAp *last = stateList.tail;
 532         while ( state != last ) {
 533                 /* Move forward and load up the next. */
 534                 state = next;
 535                 next = state->next;
 536
 537                 /* Throw to the end? */
 538                 if ( state->isFinState() ) {
 539                         stateList.detach( state );
 540                         stateList.append( state );
 541                 }
 542         }
 543 }
 544
 545 void FsmAp::setStateNumbers( int base )
 546 {
 547         for ( StateList::Iter state = stateList; state.lte(); state++ )
 548                 state->alg.stateNum = base++;
 549 }
 550
 551
 552 bool FsmAp::checkErrTrans( StateAp *state, TransAp *trans )
 553 {
 554         /* Might go directly to error state. */
 555         if ( trans->toState == 0 )
 556                 return true;
 557
 558         if ( trans->prev == 0 ) {
 559                 /* If this is the first transition. */
 560                 if ( keyOps->minKey < trans->lowKey )
 561                         return true;
 562         }
 563         else {
 564                 /* Not the first transition. Compare against the prev. */
 565                 TransAp *prev = trans->prev;
 566                 Key nextKey = prev->highKey;
 567                 nextKey.increment();
 568                 if ( nextKey < trans->lowKey )
 569                         return true;
 570         }
 571         return false;
 572 }
 573
 574 bool FsmAp::checkErrTransFinish( StateAp *state )
 575 {
 576         /* Check if there are any ranges already. */
 577         if ( state->outList.length() == 0 )
 578                 return true;
 579         else {
 580                 /* Get the last and check for a gap on the end. */
 581                 TransAp *last = state->outList.tail;
 582                 if ( last->highKey < keyOps->maxKey )
 583                         return true;
 584         }
 585         return 0;
 586 }
 587
 588 bool FsmAp::hasErrorTrans()
 589 {
 590         bool result;
 591         for ( StateList::Iter st = stateList; st.lte(); st++ ) {
 592                 for ( TransList::Iter tr = st->outList; tr.lte(); tr++ ) {
 593                         result = checkErrTrans( st, tr );
 594                         if ( result )
 595                                 return true;
 596                 }
 597                 result = checkErrTransFinish( st );
 598                 if ( result )
 599                         return true;
 600         }
 601         return false;
 602 }