ragel/fsmstate.cpp

   1 /*
   2  *  Copyright 2002 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 #include <iostream>
  27 using namespace std;
  28
  29 /* Construct a mark index for a specified number of states. Must new up
  30  * an array that is states^2 in size. */
  31 MarkIndex::MarkIndex( int states ) : numStates(states)
  32 {
  33         /* Total pairs is states^2. Actually only use half of these, but we allocate
  34          * them all to make indexing into the array easier. */
  35         int total = states * states;
  36
  37         /* New up chars so that individual DListEl constructors are
  38          * not called. Zero out the mem manually. */
  39         array = new bool[total];
  40         memset( array, 0, sizeof(bool) * total );
  41 }
  42
  43 /* Free the array used to store state pairs. */
  44 MarkIndex::~MarkIndex()
  45 {
  46         delete[] array;
  47 }
  48
  49 /* Mark a pair of states. States are specified by their number. The
  50  * marked states are moved from the unmarked list to the marked list. */
  51 void MarkIndex::markPair(int state1, int state2)
  52 {
  53         int pos = ( state1 >= state2 ) ?
  54                 ( state1 * numStates ) + state2 :
  55                 ( state2 * numStates ) + state1;
  56
  57         array[pos] = true;
  58 }
  59
  60 /* Returns true if the pair of states are marked. Returns false otherwise.
  61  * Ordering of states given does not matter. */
  62 bool MarkIndex::isPairMarked(int state1, int state2)
  63 {
  64         int pos = ( state1 >= state2 ) ?
  65                 ( state1 * numStates ) + state2 :
  66                 ( state2 * numStates ) + state1;
  67
  68         return array[pos];
  69 }
  70
  71 /* Create a new fsm state. State has not out transitions or in transitions, not
  72  * out out transition data and not number. */
  73 StateAp::StateAp()
  74 :
  75         /* No out or in transitions. */
  76         outList(),
  77         inList(),
  78
  79         /* No EOF target. */
  80         eofTarget(0),
  81
  82         /* No entry points, or epsilon trans. */
  83         entryIds(),
  84         epsilonTrans(),
  85
  86         /* Conditions. */
  87         stateCondList(),
  88
  89         /* No transitions in from other states. */
  90         foreignInTrans(0),
  91
  92         /* Only used during merging. Normally null. */
  93         stateDictEl(0),
  94         eptVect(0),
  95
  96         /* No state identification bits. */
  97         stateBits(0),
  98
  99         /* No Priority data. */
 100         outPriorTable(),
 101
 102         /* No Action data. */
 103         toStateActionTable(),
 104         fromStateActionTable(),
 105         outActionTable(),
 106         outCondSet(),
 107         errActionTable(),
 108         eofActionTable()
 109 {
 110 }
 111
 112 /* Copy everything except actual the transitions. That is left up to the
 113  * FsmAp copy constructor. */
 114 StateAp::StateAp(const StateAp &other)
 115 :
 116         /* All lists are cleared. They will be filled in when the
 117          * individual transitions are duplicated and attached. */
 118         outList(),
 119         inList(),
 120
 121         /* Set this using the original state's eofTarget. It will get mapped back
 122          * to the new machine in the Fsm copy constructor. */
 123         eofTarget(other.eofTarget),
 124
 125         /* Duplicate the entry id set and epsilon transitions. These
 126          * are sets of integers and as such need no fixing. */
 127         entryIds(other.entryIds),
 128         epsilonTrans(other.epsilonTrans),
 129
 130         /* Copy in the elements of the conditions. */
 131         stateCondList( other.stateCondList ),
 132
 133         /* No transitions in from other states. */
 134         foreignInTrans(0),
 135
 136         /* This is only used during merging. Normally null. */
 137         stateDictEl(0),
 138         eptVect(0),
 139
 140         /* Fsm state data. */
 141         stateBits(other.stateBits),
 142
 143         /* Copy in priority data. */
 144         outPriorTable(other.outPriorTable),
 145
 146         /* Copy in action data. */
 147         toStateActionTable(other.toStateActionTable),
 148         fromStateActionTable(other.fromStateActionTable),
 149         outActionTable(other.outActionTable),
 150         outCondSet(other.outCondSet),
 151         errActionTable(other.errActionTable),
 152         eofActionTable(other.eofActionTable)
 153 {
 154         /* Duplicate all the transitions. */
 155         for ( TransList::Iter trans = other.outList; trans.lte(); trans++ ) {
 156                 /* Dupicate and store the orginal target in the transition. This will
 157                  * be corrected once all the states have been created. */
 158                 TransAp *newTrans = new TransAp(*trans);
 159                 newTrans->toState = trans->toState;
 160                 outList.append( newTrans );
 161         }
 162 }
 163
 164 /* If there is a state dict element, then delete it. Everything else is left
 165  * up to the FsmGraph destructor. */
 166 StateAp::~StateAp()
 167 {
 168         if ( stateDictEl != 0 )
 169                 delete stateDictEl;
 170 }
 171
 172 /* Compare two states using pointers to the states. With the approximate
 173  * compare the idea is that if the compare finds them the same, they can
 174  * immediately be merged. */
 175 int ApproxCompare::compare( const StateAp *state1 , const StateAp *state2 )
 176 {
 177         int compareRes;
 178
 179         /* Test final state status. */
 180         if ( (state1->stateBits & SB_ISFINAL) && !(state2->stateBits & SB_ISFINAL) )
 181                 return -1;
 182         else if ( !(state1->stateBits & SB_ISFINAL) && (state2->stateBits & SB_ISFINAL) )
 183                 return 1;
 184
 185         /* Test epsilon transition sets. */
 186         compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans,
 187                         state2->epsilonTrans );
 188         if ( compareRes != 0 )
 189                 return compareRes;
 190
 191         /* Compare the out transitions. */
 192         compareRes = FsmAp::compareStateData( state1, state2 );
 193         if ( compareRes != 0 )
 194                 return compareRes;
 195
 196         /* Use a pair iterator to get the transition pairs. */
 197         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 198         for ( ; !outPair.end(); outPair++ ) {
 199                 switch ( outPair.userState ) {
 200
 201                 case RangeInS1:
 202                         compareRes = FsmAp::compareFullPtr( outPair.s1Tel.trans, 0 );
 203                         if ( compareRes != 0 )
 204                                 return compareRes;
 205                         break;
 206
 207                 case RangeInS2:
 208                         compareRes = FsmAp::compareFullPtr( 0, outPair.s2Tel.trans );
 209                         if ( compareRes != 0 )
 210                                 return compareRes;
 211                         break;
 212
 213                 case RangeOverlap:
 214                         compareRes = FsmAp::compareFullPtr(
 215                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
 216                         if ( compareRes != 0 )
 217                                 return compareRes;
 218                         break;
 219
 220                 case BreakS1:
 221                 case BreakS2:
 222                         break;
 223                 }
 224         }
 225
 226         /* Got through the entire state comparison, deem them equal. */
 227         return 0;
 228 }
 229
 230 /* Compare class for the sort that does the intial partition of compaction. */
 231 int InitPartitionCompare::compare( const StateAp *state1 , const StateAp *state2 )
 232 {
 233         int compareRes;
 234
 235         /* Test final state status. */
 236         if ( (state1->stateBits & SB_ISFINAL) && !(state2->stateBits & SB_ISFINAL) )
 237                 return -1;
 238         else if ( !(state1->stateBits & SB_ISFINAL) && (state2->stateBits & SB_ISFINAL) )
 239                 return 1;
 240
 241         /* Test epsilon transition sets. */
 242         compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans,
 243                         state2->epsilonTrans );
 244         if ( compareRes != 0 )
 245                 return compareRes;
 246
 247         /* Compare the out transitions. */
 248         compareRes = FsmAp::compareStateData( state1, state2 );
 249         if ( compareRes != 0 )
 250                 return compareRes;
 251
 252         /* Use a pair iterator to test the condition pairs. */
 253         PairIter<StateCond> condPair( state1->stateCondList.head, state2->stateCondList.head );
 254         for ( ; !condPair.end(); condPair++ ) {
 255                 switch ( condPair.userState ) {
 256                 case RangeInS1:
 257                         return 1;
 258                 case RangeInS2:
 259                         return -1;
 260
 261                 case RangeOverlap: {
 262                         CondSpace *condSpace1 = condPair.s1Tel.trans->condSpace;
 263                         CondSpace *condSpace2 = condPair.s2Tel.trans->condSpace;
 264                         if ( condSpace1 < condSpace2 )
 265                                 return -1;
 266                         else if ( condSpace1 > condSpace2 )
 267                                 return 1;
 268                         break;
 269                 }
 270                 case BreakS1:
 271                 case BreakS2:
 272                         break;
 273                 }
 274         }
 275
 276         /* Use a pair iterator to test the transition pairs. */
 277         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 278         for ( ; !outPair.end(); outPair++ ) {
 279                 switch ( outPair.userState ) {
 280
 281                 case RangeInS1:
 282                         compareRes = FsmAp::compareDataPtr( outPair.s1Tel.trans, 0 );
 283                         if ( compareRes != 0 )
 284                                 return compareRes;
 285                         break;
 286
 287                 case RangeInS2:
 288                         compareRes = FsmAp::compareDataPtr( 0, outPair.s2Tel.trans );
 289                         if ( compareRes != 0 )
 290                                 return compareRes;
 291                         break;
 292
 293                 case RangeOverlap:
 294                         compareRes = FsmAp::compareDataPtr(
 295                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
 296                         if ( compareRes != 0 )
 297                                 return compareRes;
 298                         break;
 299
 300                 case BreakS1:
 301                 case BreakS2:
 302                         break;
 303                 }
 304         }
 305
 306         return 0;
 307 }
 308
 309 /* Compare class for the sort that does the partitioning. */
 310 int PartitionCompare::compare( const StateAp *state1, const StateAp *state2 )
 311 {
 312         int compareRes;
 313
 314         /* Use a pair iterator to get the transition pairs. */
 315         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 316         for ( ; !outPair.end(); outPair++ ) {
 317                 switch ( outPair.userState ) {
 318
 319                 case RangeInS1:
 320                         compareRes = FsmAp::comparePartPtr( outPair.s1Tel.trans, 0 );
 321                         if ( compareRes != 0 )
 322                                 return compareRes;
 323                         break;
 324
 325                 case RangeInS2:
 326                         compareRes = FsmAp::comparePartPtr( 0, outPair.s2Tel.trans );
 327                         if ( compareRes != 0 )
 328                                 return compareRes;
 329                         break;
 330
 331                 case RangeOverlap:
 332                         compareRes = FsmAp::comparePartPtr(
 333                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
 334                         if ( compareRes != 0 )
 335                                 return compareRes;
 336                         break;
 337
 338                 case BreakS1:
 339                 case BreakS2:
 340                         break;
 341                 }
 342         }
 343
 344         return 0;
 345 }
 346
 347 /* Compare class for the sort that does the partitioning. */
 348 bool MarkCompare::shouldMark( MarkIndex &markIndex, const StateAp *state1,
 349                         const StateAp *state2 )
 350 {
 351         /* Use a pair iterator to get the transition pairs. */
 352         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 353         for ( ; !outPair.end(); outPair++ ) {
 354                 switch ( outPair.userState ) {
 355
 356                 case RangeInS1:
 357                         if ( FsmAp::shouldMarkPtr( markIndex, outPair.s1Tel.trans, 0 ) )
 358                                 return true;
 359                         break;
 360
 361                 case RangeInS2:
 362                         if ( FsmAp::shouldMarkPtr( markIndex, 0, outPair.s2Tel.trans ) )
 363                                 return true;
 364                         break;
 365
 366                 case RangeOverlap:
 367                         if ( FsmAp::shouldMarkPtr( markIndex,
 368                                         outPair.s1Tel.trans, outPair.s2Tel.trans ) )
 369                                 return true;
 370                         break;
 371
 372                 case BreakS1:
 373                 case BreakS2:
 374                         break;
 375                 }
 376         }
 377
 378         return false;
 379 }
 380
 381 /*
 382  * Transition Comparison.
 383  */
 384
 385 /* Compare target partitions. Either pointer may be null. */
 386 int FsmAp::comparePartPtr( TransAp *trans1, TransAp *trans2 )
 387 {
 388         if ( trans1 != 0 ) {
 389                 /* If trans1 is set then so should trans2. The initial partitioning
 390                  * guarantees this for us. */
 391                 if ( trans1->toState == 0 && trans2->toState != 0 )
 392                         return -1;
 393                 else if ( trans1->toState != 0 && trans2->toState == 0 )
 394                         return 1;
 395                 else if ( trans1->toState != 0 ) {
 396                         /* Both of targets are set. */
 397                         return CmpOrd< MinPartition* >::compare(
 398                                 trans1->toState->alg.partition, trans2->toState->alg.partition );
 399                 }
 400         }
 401         return 0;
 402 }
 403
 404
 405 /* Compares two transition pointers according to priority and functions.
 406  * Either pointer may be null. Does not consider to state or from state. */
 407 int FsmAp::compareDataPtr( TransAp *trans1, TransAp *trans2 )
 408 {
 409         if ( trans1 == 0 && trans2 != 0 )
 410                 return -1;
 411         else if ( trans1 != 0 && trans2 == 0 )
 412                 return 1;
 413         else if ( trans1 != 0 ) {
 414                 /* Both of the transition pointers are set. */
 415                 int compareRes = compareTransData( trans1, trans2 );
 416                 if ( compareRes != 0 )
 417                         return compareRes;
 418         }
 419         return 0;
 420 }
 421
 422 /* Compares two transitions according to target state, priority and functions.
 423  * Does not consider from state. Either of the pointers may be null. */
 424 int FsmAp::compareFullPtr( TransAp *trans1, TransAp *trans2 )
 425 {
 426         if ( (trans1 != 0) ^ (trans2 != 0) ) {
 427                 /* Exactly one of the transitions is set. */
 428                 if ( trans1 != 0 )
 429                         return -1;
 430                 else
 431                         return 1;
 432         }
 433         else if ( trans1 != 0 ) {
 434                 /* Both of the transition pointers are set. Test target state,
 435                  * priority and funcs. */
 436                 if ( trans1->toState < trans2->toState )
 437                         return -1;
 438                 else if ( trans1->toState > trans2->toState )
 439                         return 1;
 440                 else if ( trans1->toState != 0 ) {
 441                         /* Test transition data. */
 442                         int compareRes = compareTransData( trans1, trans2 );
 443                         if ( compareRes != 0 )
 444                                 return compareRes;
 445                 }
 446         }
 447         return 0;
 448 }
 449
 450
 451 bool FsmAp::shouldMarkPtr( MarkIndex &markIndex, TransAp *trans1,
 452                                 TransAp *trans2 )
 453 {
 454         if ( (trans1 != 0) ^ (trans2 != 0) ) {
 455                 /* Exactly one of the transitions is set. The initial mark round
 456                  * should rule out this case. */
 457                 assert( false );
 458         }
 459         else if ( trans1 != 0 ) {
 460                 /* Both of the transitions are set. If the target pair is marked, then
 461                  * the pair we are considering gets marked. */
 462                 return markIndex.isPairMarked( trans1->toState->alg.stateNum,
 463                                 trans2->toState->alg.stateNum );
 464         }
 465
 466         /* Neither of the transitiosn are set. */
 467         return false;
 468 }
 469
 470