ragel/fsmbase.cpp

   1 /*
   2  *  Copyright 2001 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
  50         /* Misfit accounting is a switch, turned on only at specific times. It
  51          * controls what happens when states have no way in from the outside
  52          * world.. */
  53         misfitAccounting(false)
  54 {
  55 }
  56
  57 /* Copy all graph data including transitions. */
  58 FsmAp::FsmAp( const FsmAp &graph )
  59 :
  60         /* Lists start empty. Will be filled by copy. */
  61         stateList(),
  62         misfitList(),
  63
  64         /* Copy in the entry points,
  65          * pointers will be resolved later. */
  66         entryPoints(graph.entryPoints),
  67         startState(graph.startState),
  68
  69         /* Will be filled by copy. */
  70         finStateSet(),
  71
  72         /* Misfit accounting is only on during merging. */
  73         misfitAccounting(false)
  74 {
  75         /* Create the states and record their map in the original state. */
  76         StateList::Iter origState = graph.stateList;
  77         for ( ; origState.lte(); origState++ ) {
  78                 /* Make the new state. */
  79                 StateAp *newState = new StateAp( *origState );
  80
  81                 /* Add the state to the list.  */
  82                 stateList.append( newState );
  83
  84                 /* Set the mapsTo item of the old state. */
  85                 origState->alg.stateMap = newState;
  86         }
  87
  88         /* Derefernce all the state maps. */
  89         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
  90                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
  91                         /* The points to the original in the src machine. The taget's duplicate
  92                          * is in the statemap. */
  93                         StateAp *toState = trans->toState != 0 ? trans->toState->alg.stateMap : 0;
  94
  95                         /* Attach The transition to the duplicate. */
  96                         trans->toState = 0;
  97                         attachTrans( state, toState, trans );
  98                 }
  99         }
 100
 101         /* Fix the state pointers in the entry points array. */
 102         EntryMapEl *eel = entryPoints.data;
 103         for ( int e = 0; e < entryPoints.length(); e++, eel++ ) {
 104                 /* Get the duplicate of the state. */
 105                 eel->value = eel->value->alg.stateMap;
 106
 107                 /* Foreign in transitions must be built up when duping machines so
 108                  * increment it here. */
 109                 eel->value->foreignInTrans += 1;
 110         }
 111
 112         /* Fix the start state pointer and the new start state's count of in
 113          * transiions. */
 114         startState = startState->alg.stateMap;
 115         startState->foreignInTrans += 1;
 116
 117         /* Build the final state set. */
 118         StateSet::Iter st = graph.finStateSet;
 119         for ( ; st.lte(); st++ )
 120                 finStateSet.insert((*st)->alg.stateMap);
 121 }
 122
 123 /* Deletes all transition data then deletes each state. */
 124 FsmAp::~FsmAp()
 125 {
 126         /* Delete all the transitions. */
 127         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 128                 /* Iterate the out transitions, deleting them. */
 129                 state->outList.empty();
 130         }
 131
 132         /* Delete all the states. */
 133         stateList.empty();
 134 }
 135
 136 /* Set a state final. The state has its isFinState set to true and the state
 137  * is added to the finStateSet. */
 138 void FsmAp::setFinState( StateAp *state )
 139 {
 140         /* Is it already a fin state. */
 141         if ( state->stateBits & SB_ISFINAL )
 142                 return;
 143
 144         state->stateBits |= SB_ISFINAL;
 145         finStateSet.insert( state );
 146 }
 147
 148 /* Set a state non-final. The has its isFinState flag set false and the state
 149  * is removed from the final state set. */
 150 void FsmAp::unsetFinState( StateAp *state )
 151 {
 152         /* Is it already a non-final state? */
 153         if ( ! (state->stateBits & SB_ISFINAL) )
 154                 return;
 155
 156         /* When a state looses its final state status it must relinquish all the
 157          * properties that are allowed only for final states. */
 158         clearOutData( state );
 159
 160         state->stateBits &= ~ SB_ISFINAL;
 161         finStateSet.remove( state );
 162 }
 163
 164 /* Set and unset a state as the start state. */
 165 void FsmAp::setStartState( StateAp *state )
 166 {
 167         /* Sould change from unset to set. */
 168         assert( startState == 0 );
 169         startState = state;
 170
 171         if ( misfitAccounting ) {
 172                 /* If the number of foreign in transitions is about to go up to 1 then
 173                  * take it off the misfit list and put it on the head list. */
 174                 if ( state->foreignInTrans == 0 )
 175                         stateList.append( misfitList.detach( state ) );
 176         }
 177
 178         /* Up the foreign in transitions to the state. */
 179         state->foreignInTrans += 1;
 180 }
 181
 182 void FsmAp::unsetStartState()
 183 {
 184         /* Should change from set to unset. */
 185         assert( startState != 0 );
 186
 187         /* Decrement the entry's count of foreign entries. */
 188         startState->foreignInTrans -= 1;
 189
 190         if ( misfitAccounting ) {
 191                 /* If the number of foreign in transitions just went down to 0 then take
 192                  * it off the main list and put it on the misfit list. */
 193                 if ( startState->foreignInTrans == 0 )
 194                         misfitList.append( stateList.detach( startState ) );
 195         }
 196
 197         startState = 0;
 198 }
 199
 200 /* Associate an id with a state. Makes the state a named entry point. Has no
 201  * effect if the entry point is already mapped to the state. */
 202 void FsmAp::setEntry( int id, StateAp *state )
 203 {
 204         /* Insert the id into the state. If the state is already labelled with id,
 205          * nothing to do. */
 206         if ( state->entryIds.insert( id ) ) {
 207                 /* Insert the entry and assert that it succeeds. */
 208                 entryPoints.insertMulti( id, state );
 209
 210                 if ( misfitAccounting ) {
 211                         /* If the number of foreign in transitions is about to go up to 1 then
 212                          * take it off the misfit list and put it on the head list. */
 213                         if ( state->foreignInTrans == 0 )
 214                                 stateList.append( misfitList.detach( state ) );
 215                 }
 216
 217                 /* Up the foreign in transitions to the state. */
 218                 state->foreignInTrans += 1;
 219         }
 220 }
 221
 222 /* Remove the association of an id with a state. The state looses it's entry
 223  * point status. Assumes that the id is indeed mapped to state. */
 224 void FsmAp::unsetEntry( int id, StateAp *state )
 225 {
 226         /* Find the entry point in on id. */
 227         EntryMapEl *enLow = 0, *enHigh = 0;
 228         entryPoints.findMulti( id, enLow, enHigh );
 229         while ( enLow->value != state )
 230                 enLow += 1;
 231
 232         /* Remove the record from the map. */
 233         entryPoints.remove( enLow );
 234
 235         /* Remove the state's sense of the link. */
 236         state->entryIds.remove( id );
 237         state->foreignInTrans -= 1;
 238         if ( misfitAccounting ) {
 239                 /* If the number of foreign in transitions just went down to 0 then take
 240                  * it off the main list and put it on the misfit list. */
 241                 if ( state->foreignInTrans == 0 )
 242                         misfitList.append( stateList.detach( state ) );
 243         }
 244 }
 245
 246 /* Remove all association of an id with states. Assumes that the id is indeed
 247  * mapped to a state. */
 248 void FsmAp::unsetEntry( int id )
 249 {
 250         /* Find the entry point in on id. */
 251         EntryMapEl *enLow = 0, *enHigh = 0;
 252         entryPoints.findMulti( id, enLow, enHigh );
 253         for ( EntryMapEl *mel = enLow; mel <= enHigh; mel++ ) {
 254                 /* Remove the state's sense of the link. */
 255                 mel->value->entryIds.remove( id );
 256                 mel->value->foreignInTrans -= 1;
 257                 if ( misfitAccounting ) {
 258                         /* If the number of foreign in transitions just went down to 0
 259                          * then take it off the main list and put it on the misfit list. */
 260                         if ( mel->value->foreignInTrans == 0 )
 261                                 misfitList.append( stateList.detach( mel->value ) );
 262                 }
 263         }
 264
 265         /* Remove the records from the entry points map. */
 266         entryPoints.removeMulti( enLow, enHigh );
 267 }
 268
 269
 270 void FsmAp::changeEntry( int id, StateAp *to, StateAp *from )
 271 {
 272         /* Find the entry in the entry map. */
 273         EntryMapEl *enLow = 0, *enHigh = 0;
 274         entryPoints.findMulti( id, enLow, enHigh );
 275         while ( enLow->value != from )
 276                 enLow += 1;
 277
 278         /* Change it to the new target. */
 279         enLow->value = to;
 280
 281         /* Remove from's sense of the link. */
 282         from->entryIds.remove( id );
 283         from->foreignInTrans -= 1;
 284         if ( misfitAccounting ) {
 285                 /* If the number of foreign in transitions just went down to 0 then take
 286                  * it off the main list and put it on the misfit list. */
 287                 if ( from->foreignInTrans == 0 )
 288                         misfitList.append( stateList.detach( from ) );
 289         }
 290
 291         /* Add to's sense of the link. */
 292         if ( to->entryIds.insert( id ) != 0 ) {
 293                 if ( misfitAccounting ) {
 294                         /* If the number of foreign in transitions is about to go up to 1 then
 295                          * take it off the misfit list and put it on the head list. */
 296                         if ( to->foreignInTrans == 0 )
 297                                 stateList.append( misfitList.detach( to ) );
 298                 }
 299
 300                 /* Up the foreign in transitions to the state. */
 301                 to->foreignInTrans += 1;
 302         }
 303 }
 304
 305
 306 /* Clear all entry points from a machine. */
 307 void FsmAp::unsetAllEntryPoints()
 308 {
 309         for ( EntryMap::Iter en = entryPoints; en.lte(); en++ ) {
 310                 /* Kill all the state's entry points at once. */
 311                 if ( en->value->entryIds.length() > 0 ) {
 312                         en->value->foreignInTrans -= en->value->entryIds.length();
 313
 314                         if ( misfitAccounting ) {
 315                                 /* If the number of foreign in transitions just went down to 0
 316                                  * then take it off the main list and put it on the misfit
 317                                  * list. */
 318                                 if ( en->value->foreignInTrans == 0 )
 319                                         misfitList.append( stateList.detach( en->value ) );
 320                         }
 321
 322                         /* Clear the set of ids out all at once. */
 323                         en->value->entryIds.empty();
 324                 }
 325         }
 326
 327         /* Now clear out the entry map all at once. */
 328         entryPoints.empty();
 329 }
 330
 331 /* Assigning an epsilon transition into final states. */
 332 void FsmAp::epsilonTrans( int id )
 333 {
 334         for ( StateSet::Iter fs = finStateSet; fs.lte(); fs++ )
 335                 (*fs)->epsilonTrans.append( id );
 336 }
 337
 338 /* Mark all states reachable from state. Traverses transitions forward. Used
 339  * for removing states that have no path into them. */
 340 void FsmAp::markReachableFromHere( StateAp *state )
 341 {
 342         /* Base case: return; */
 343         if ( state->stateBits & SB_ISMARKED )
 344                 return;
 345
 346         /* Set this state as processed. We are going to visit all states that this
 347          * state has a transition to. */
 348         state->stateBits |= SB_ISMARKED;
 349
 350         /* Recurse on all out transitions. */
 351         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 352                 if ( trans->toState != 0 )
 353                         markReachableFromHere( trans->toState );
 354         }
 355 }
 356
 357 void FsmAp::markReachableFromHereStopFinal( StateAp *state )
 358 {
 359         /* Base case: return; */
 360         if ( state->stateBits & SB_ISMARKED )
 361                 return;
 362
 363         /* Set this state as processed. We are going to visit all states that this
 364          * state has a transition to. */
 365         state->stateBits |= SB_ISMARKED;
 366
 367         /* Recurse on all out transitions. */
 368         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 369                 StateAp *toState = trans->toState;
 370                 if ( toState != 0 && !toState->isFinState() )
 371                         markReachableFromHereStopFinal( toState );
 372         }
 373 }
 374
 375 /* Mark all states reachable from state. Traverse transitions backwards. Used
 376  * for removing dead end paths in graphs. */
 377 void FsmAp::markReachableFromHereReverse( StateAp *state )
 378 {
 379         /* Base case: return; */
 380         if ( state->stateBits & SB_ISMARKED )
 381                 return;
 382
 383         /* Set this state as processed. We are going to visit all states with
 384          * transitions into this state. */
 385         state->stateBits |= SB_ISMARKED;
 386
 387         /* Recurse on all items in transitions. */
 388         for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ )
 389                 markReachableFromHereReverse( trans->fromState );
 390 }
 391
 392 /* Determine if there are any entry points into a start state other than the
 393  * start state. Setting starting transitions requires that the start state be
 394  * isolated. In most cases a start state will already be isolated. */
 395 bool FsmAp::isStartStateIsolated()
 396 {
 397         /* If there are any in transitions then the state is not isolated. */
 398         if ( startState->inList.head != 0 )
 399                 return false;
 400
 401         /* If there are any entry points then isolated. */
 402         if ( startState->entryIds.length() > 0 )
 403                 return false;
 404
 405         return true;
 406 }
 407
 408 /* Bring in other's entry points. Assumes others states are going to be
 409  * copied into this machine. */
 410 void FsmAp::copyInEntryPoints( FsmAp *other )
 411 {
 412         /* Use insert multi because names are not unique. */
 413         for ( EntryMap::Iter en = other->entryPoints; en.lte(); en++ )
 414                 entryPoints.insertMulti( en->key, en->value );
 415 }
 416
 417 void FsmAp::setStateNumbers()
 418 {
 419         int curNum = 0;
 420         StateList::Iter state = stateList;
 421         for ( ; state.lte(); state++ )
 422                 state->alg.stateNum = curNum++;
 423 }
 424
 425
 426 void FsmAp::unsetAllFinStates()
 427 {
 428         for ( StateSet::Iter st = finStateSet; st.lte(); st++ )
 429                 (*st)->stateBits &= ~ SB_ISFINAL;
 430         finStateSet.empty();
 431 }
 432
 433 void FsmAp::setFinBits( int finStateBits )
 434 {
 435         for ( int s = 0; s < finStateSet.length(); s++ )
 436                 finStateSet.data[s]->stateBits |= finStateBits;
 437 }
 438
 439
 440 /* Tests the integrity of the transition lists and the fromStates. */
 441 void FsmAp::verifyIntegrity()
 442 {
 443         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 444                 /* Walk the out transitions and assert fromState is correct. */
 445                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ )
 446                         assert( trans->fromState == state );
 447
 448                 /* Walk the inlist and assert toState is correct. */
 449                 for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ )
 450                         assert( trans->toState == state );
 451         }
 452 }
 453
 454 void FsmAp::verifyReachability()
 455 {
 456         /* Mark all the states that can be reached
 457          * through the set of entry points. */
 458         markReachableFromHere( startState );
 459         for ( EntryMap::Iter en = entryPoints; en.lte(); en++ )
 460                 markReachableFromHere( en->value );
 461
 462         /* Check that everything got marked. */
 463         for ( StateList::Iter st = stateList; st.lte(); st++ ) {
 464                 /* Assert it got marked and then clear the mark. */
 465                 assert( st->stateBits & SB_ISMARKED );
 466                 st->stateBits &= ~ SB_ISMARKED;
 467         }
 468 }
 469
 470 void FsmAp::verifyNoDeadEndStates()
 471 {
 472         /* Mark all states that have paths to the final states. */
 473         for ( StateSet::Iter pst = finStateSet; pst.lte(); pst++ )
 474                 markReachableFromHereReverse( *pst );
 475
 476         /* Start state gets honorary marking. Must be done AFTER recursive call. */
 477         startState->stateBits |= SB_ISMARKED;
 478
 479         /* Make sure everything got marked. */
 480         for ( StateList::Iter st = stateList; st.lte(); st++ ) {
 481                 /* Assert the state got marked and unmark it. */
 482                 assert( st->stateBits & SB_ISMARKED );
 483                 st->stateBits &= ~ SB_ISMARKED;
 484         }
 485 }