ragel/fsmattach.cpp

   1 /*
   2  *  Copyright 2001 Adrian Thurston <thurston@complang.org>
   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 #include <iostream>
  27 using namespace std;
  28
  29 /* Insert a transition into an inlist. The head must be supplied. */
  30 void FsmAp::attachToInList( StateAp *from, StateAp *to,
  31                 TransAp *&head, TransAp *trans )
  32 {
  33         trans->ilnext = head;
  34         trans->ilprev = 0;
  35
  36         /* If in trans list is not empty, set the head->prev to trans. */
  37         if ( head != 0 )
  38                 head->ilprev = trans;
  39
  40         /* Now insert ourselves at the front of the list. */
  41         head = trans;
  42
  43         /* Keep track of foreign transitions for from and to. */
  44         if ( from != to ) {
  45                 if ( misfitAccounting ) {
  46                         /* If the number of foreign in transitions is about to go up to 1 then
  47                          * move it from the misfit list to the main list. */
  48                         if ( to->foreignInTrans == 0 )
  49                                 stateList.append( misfitList.detach( to ) );
  50                 }
  51
  52                 to->foreignInTrans += 1;
  53         }
  54 };
  55
  56 /* Detach a transition from an inlist. The head of the inlist must be supplied. */
  57 void FsmAp::detachFromInList( StateAp *from, StateAp *to,
  58                 TransAp *&head, TransAp *trans )
  59 {
  60         /* Detach in the inTransList. */
  61         if ( trans->ilprev == 0 )
  62                 head = trans->ilnext;
  63         else
  64                 trans->ilprev->ilnext = trans->ilnext;
  65
  66         if ( trans->ilnext != 0 )
  67                 trans->ilnext->ilprev = trans->ilprev;
  68
  69         /* Keep track of foreign transitions for from and to. */
  70         if ( from != to ) {
  71                 to->foreignInTrans -= 1;
  72
  73                 if ( misfitAccounting ) {
  74                         /* If the number of foreign in transitions goes down to 0 then move it
  75                          * from the main list to the misfit list. */
  76                         if ( to->foreignInTrans == 0 )
  77                                 misfitList.append( stateList.detach( to ) );
  78                 }
  79         }
  80 }
  81
  82 /* Attach states on the default transition, range list or on out/in list key.
  83  * First makes a new transition. If there is already a transition out from
  84  * fromState on the default, then will assertion fail. */
  85 TransAp *FsmAp::attachNewTrans( StateAp *from, StateAp *to, Key lowKey, Key highKey )
  86 {
  87         /* Make the new transition. */
  88         TransAp *retVal = new TransAp();
  89
  90         /* The transition is now attached. Remember the parties involved. */
  91         retVal->fromState = from;
  92         retVal->toState = to;
  93
  94         /* Make the entry in the out list for the transitions. */
  95         from->outList.append( retVal );
  96
  97         /* Set the the keys of the new trans. */
  98         retVal->lowKey = lowKey;
  99         retVal->highKey = highKey;
 100
 101         /* Attach using inList as the head pointer. */
 102         if ( to != 0 )
 103                 attachToInList( from, to, to->inList.head, retVal );
 104
 105         return retVal;
 106 }
 107
 108 /* Attach for range lists or for the default transition.  This attach should
 109  * be used when a transition already is allocated and must be attached to a
 110  * target state.  Does not handle adding the transition into the out list. */
 111 void FsmAp::attachTrans( StateAp *from, StateAp *to, TransAp *trans )
 112 {
 113         assert( trans->fromState == 0 && trans->toState == 0 );
 114         trans->fromState = from;
 115         trans->toState = to;
 116
 117         if ( to != 0 ) {
 118                 /* Attach using the inList pointer as the head pointer. */
 119                 attachToInList( from, to, to->inList.head, trans );
 120         }
 121 }
 122
 123 /* Redirect a transition away from error and towards some state. This is just
 124  * like attachTrans except it requires fromState to be set and does not touch
 125  * it. */
 126 void FsmAp::redirectErrorTrans( StateAp *from, StateAp *to, TransAp *trans )
 127 {
 128         assert( trans->fromState != 0 && trans->toState == 0 );
 129         trans->toState = to;
 130
 131         if ( to != 0 ) {
 132                 /* Attach using the inList pointer as the head pointer. */
 133                 attachToInList( from, to, to->inList.head, trans );
 134         }
 135 }
 136
 137 /* Detach for out/in lists or for default transition. */
 138 void FsmAp::detachTrans( StateAp *from, StateAp *to, TransAp *trans )
 139 {
 140         assert( trans->fromState == from && trans->toState == to );
 141         trans->fromState = 0;
 142         trans->toState = 0;
 143
 144         if ( to != 0 ) {
 145                 /* Detach using to's inList pointer as the head. */
 146                 detachFromInList( from, to, to->inList.head, trans );
 147         }
 148 }
 149
 150
 151 /* Detach a state from the graph. Detaches and deletes transitions in and out
 152  * of the state. Empties inList and outList. Removes the state from the final
 153  * state set. A detached state becomes useless and should be deleted. */
 154 void FsmAp::detachState( StateAp *state )
 155 {
 156         /* Detach the in transitions from the inList list of transitions. */
 157         while ( state->inList.head != 0 ) {
 158                 /* Get pointers to the trans and the state. */
 159                 TransAp *trans = state->inList.head;
 160                 StateAp *fromState = trans->fromState;
 161
 162                 /* Detach the transitions from the source state. */
 163                 detachTrans( fromState, state, trans );
 164
 165                 /* Ok to delete the transition. */
 166                 fromState->outList.detach( trans );
 167                 delete trans;
 168         }
 169
 170         /* Remove the entry points in on the machine. */
 171         while ( state->entryIds.length() > 0 )
 172                 unsetEntry( state->entryIds[0], state );
 173
 174         /* Detach out range transitions. */
 175         for ( TransList::Iter trans = state->outList; trans.lte(); ) {
 176                 TransList::Iter next = trans.next();
 177                 detachTrans( state, trans->toState, trans );
 178                 delete trans;
 179                 trans = next;
 180         }
 181
 182         /* Delete all of the out range pointers. */
 183         state->outList.abandon();
 184
 185         /* Unset final stateness before detaching from graph. */
 186         if ( state->stateBits & STB_ISFINAL )
 187                 finStateSet.remove( state );
 188 }
 189
 190
 191 /* Duplicate a transition. Makes a new transition that is attached to the same
 192  * dest as srcTrans. The new transition has functions and priority taken from
 193  * srcTrans. Used for merging a transition in to a free spot. The trans can
 194  * just be dropped in. It does not conflict with an existing trans and need
 195  * not be crossed. Returns the new transition. */
 196 TransAp *FsmAp::dupTrans( StateAp *from, TransAp *srcTrans )
 197 {
 198         /* Make a new transition. */
 199         TransAp *newTrans = new TransAp();
 200
 201         /* We can attach the transition, one does not exist. */
 202         attachTrans( from, srcTrans->toState, newTrans );
 203
 204         /* Call the user callback to add in the original source transition. */
 205         addInTrans( newTrans, srcTrans );
 206
 207         return newTrans;
 208 }
 209
 210 /* In crossing, src trans and dest trans both go to existing states. Make one
 211  * state from the sets of states that src and dest trans go to. */
 212 TransAp *FsmAp::fsmAttachStates( MergeData &md, StateAp *from,
 213                         TransAp *destTrans, TransAp *srcTrans )
 214 {
 215         /* The priorities are equal. We must merge the transitions. Does the
 216          * existing trans go to the state we are to attach to? ie, are we to
 217          * simply double up the transition? */
 218         StateAp *toState = srcTrans->toState;
 219         StateAp *existingState = destTrans->toState;
 220
 221         if ( existingState == toState ) {
 222                 /* The transition is a double up to the same state.  Copy the src
 223                  * trans into itself. We don't need to merge in the from out trans
 224                  * data, that was done already. */
 225                 addInTrans( destTrans, srcTrans );
 226         }
 227         else {
 228                 /* The trans is not a double up. Dest trans cannot be the same as src
 229                  * trans. Set up the state set. */
 230                 StateSet stateSet;
 231
 232                 /* We go to all the states the existing trans goes to, plus... */
 233                 if ( existingState->stateDictEl == 0 )
 234                         stateSet.insert( existingState );
 235                 else
 236                         stateSet.insert( existingState->stateDictEl->stateSet );
 237
 238                 /* ... all the states that we have been told to go to. */
 239                 if ( toState->stateDictEl == 0 )
 240                         stateSet.insert( toState );
 241                 else
 242                         stateSet.insert( toState->stateDictEl->stateSet );
 243
 244                 /* Look for the state. If it is not there already, make it. */
 245                 StateDictEl *lastFound;
 246                 if ( md.stateDict.insert( stateSet, &lastFound ) ) {
 247                         /* Make a new state representing the combination of states in
 248                          * stateSet. It gets added to the fill list.  This means that we
 249                          * need to fill in it's transitions sometime in the future.  We
 250                          * don't do that now (ie, do not recurse). */
 251                         StateAp *combinState = addState();
 252
 253                         /* Link up the dict element and the state. */
 254                         lastFound->targState = combinState;
 255                         combinState->stateDictEl = lastFound;
 256
 257                         /* Add to the fill list. */
 258                         md.fillListAppend( combinState );
 259                 }
 260
 261                 /* Get the state insertted/deleted. */
 262                 StateAp *targ = lastFound->targState;
 263
 264                 /* Detach the state from existing state. */
 265                 detachTrans( from, existingState, destTrans );
 266
 267                 /* Re-attach to the new target. */
 268                 attachTrans( from, targ, destTrans );
 269
 270                 /* Add in src trans to the existing transition that we redirected to
 271                  * the new state. We don't need to merge in the from out trans data,
 272                  * that was done already. */
 273                 addInTrans( destTrans, srcTrans );
 274         }
 275
 276         return destTrans;
 277 }
 278
 279 /* Two transitions are to be crossed, handle the possibility of either going
 280  * to the error state. */
 281 TransAp *FsmAp::mergeTrans( MergeData &md, StateAp *from,
 282                         TransAp *destTrans, TransAp *srcTrans )
 283 {
 284         TransAp *retTrans = 0;
 285         if ( destTrans->toState == 0 && srcTrans->toState == 0 ) {
 286                 /* Error added into error. */
 287                 addInTrans( destTrans, srcTrans );
 288                 retTrans = destTrans;
 289         }
 290         else if ( destTrans->toState == 0 && srcTrans->toState != 0 ) {
 291                 /* Non error added into error we need to detach and reattach, */
 292                 detachTrans( from, destTrans->toState, destTrans );
 293                 attachTrans( from, srcTrans->toState, destTrans );
 294                 addInTrans( destTrans, srcTrans );
 295                 retTrans = destTrans;
 296         }
 297         else if ( srcTrans->toState == 0 ) {
 298                 /* Dest goes somewhere but src doesn't, just add it it in. */
 299                 addInTrans( destTrans, srcTrans );
 300                 retTrans = destTrans;
 301         }
 302         else {
 303                 /* Both go somewhere, run the actual cross. */
 304                 retTrans = fsmAttachStates( md, from, destTrans, srcTrans );
 305         }
 306
 307         return retTrans;
 308 }
 309
 310 /* Find the trans with the higher priority. If src is lower priority then dest then
 311  * src is ignored. If src is higher priority than dest, then src overwrites dest. If
 312  * the priorities are equal, then they are merged. */
 313 TransAp *FsmAp::crossTransitions( MergeData &md, StateAp *from,
 314                 TransAp *destTrans, TransAp *srcTrans )
 315 {
 316         TransAp *retTrans;
 317
 318         /* Compare the priority of the dest and src transitions. */
 319         int compareRes = comparePrior( destTrans->priorTable, srcTrans->priorTable );
 320         if ( compareRes < 0 ) {
 321                 /* Src trans has a higher priority than dest, src overwrites dest.
 322                  * Detach dest and return a copy of src. */
 323                 detachTrans( from, destTrans->toState, destTrans );
 324                 retTrans = dupTrans( from, srcTrans );
 325         }
 326         else if ( compareRes > 0 ) {
 327                 /* The dest trans has a higher priority, use dest. */
 328                 retTrans = destTrans;
 329         }
 330         else {
 331                 /* Src trans and dest trans have the same priority, they must be merged. */
 332                 retTrans = mergeTrans( md, from, destTrans, srcTrans );
 333         }
 334
 335         /* Return the transition that resulted from the cross. */
 336         return retTrans;
 337 }
 338
 339 /* Copy the transitions in srcList to the outlist of dest. The srcList should
 340  * not be the outList of dest, otherwise you would be copying the contents of
 341  * srcList into itself as it's iterated: bad news. */
 342 void FsmAp::outTransCopy( MergeData &md, StateAp *dest, TransAp *srcList )
 343 {
 344         /* The destination list. */
 345         TransList destList;
 346
 347         /* Set up an iterator to stop at breaks. */
 348         PairIter<TransAp> outPair( dest->outList.head, srcList );
 349         for ( ; !outPair.end(); outPair++ ) {
 350                 switch ( outPair.userState ) {
 351                 case RangeInS1: {
 352                         /* The pair iter is the authority on the keys. It may have needed
 353                          * to break the dest range. */
 354                         TransAp *destTrans = outPair.s1Tel.trans;
 355                         destTrans->lowKey = outPair.s1Tel.lowKey;
 356                         destTrans->highKey = outPair.s1Tel.highKey;
 357                         destList.append( destTrans );
 358                         break;
 359                 }
 360                 case RangeInS2: {
 361                         /* Src range may get crossed with dest's default transition. */
 362                         TransAp *newTrans = dupTrans( dest, outPair.s2Tel.trans );
 363
 364                         /* Set up the transition's keys and append to the dest list. */
 365                         newTrans->lowKey = outPair.s2Tel.lowKey;
 366                         newTrans->highKey = outPair.s2Tel.highKey;
 367                         destList.append( newTrans );
 368                         break;
 369                 }
 370                 case RangeOverlap: {
 371                         /* Exact overlap, cross them. */
 372                         TransAp *newTrans = crossTransitions( md, dest,
 373                                 outPair.s1Tel.trans, outPair.s2Tel.trans );
 374
 375                         /* Set up the transition's keys and append to the dest list. */
 376                         newTrans->lowKey = outPair.s1Tel.lowKey;
 377                         newTrans->highKey = outPair.s1Tel.highKey;
 378                         destList.append( newTrans );
 379                         break;
 380                 }
 381                 case BreakS1: {
 382                         /* Since we are always writing to the dest trans, the dest needs
 383                          * to be copied when it is broken. The copy goes into the first
 384                          * half of the break to "break it off". */
 385                         outPair.s1Tel.trans = dupTrans( dest, outPair.s1Tel.trans );
 386                         break;
 387                 }
 388                 case BreakS2:
 389                         break;
 390                 }
 391         }
 392
 393         /* Abandon the old outList and transfer destList into it. */
 394         dest->outList.transfer( destList );
 395 }
 396
 397
 398 /* Move all the transitions that go into src so that they go into dest.  */
 399 void FsmAp::inTransMove( StateAp *dest, StateAp *src )
 400 {
 401         /* Do not try to move in trans to and from the same state. */
 402         assert( dest != src );
 403
 404         /* If src is the start state, dest becomes the start state. */
 405         if ( src == startState ) {
 406                 unsetStartState();
 407                 setStartState( dest );
 408         }
 409
 410         /* For each entry point into, create an entry point into dest, when the
 411          * state is detached, the entry points to src will be removed. */
 412         for ( EntryIdSet::Iter enId = src->entryIds; enId.lte(); enId++ )
 413                 changeEntry( *enId, dest, src );
 414
 415         /* Move the transitions in inList. */
 416         while ( src->inList.head != 0 ) {
 417                 /* Get trans and from state. */
 418                 TransAp *trans = src->inList.head;
 419                 StateAp *fromState = trans->fromState;
 420
 421                 /* Detach from src, reattach to dest. */
 422                 detachTrans( fromState, src, trans );
 423                 attachTrans( fromState, dest, trans );
 424         }
 425 }