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