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         /* Not yet supporting minimization of states with EOF targets. */
 227         assert( state1->eofTarget == 0 && state2->eofTarget == 0 );
 228
 229         /* Got through the entire state comparison, deem them equal. */
 230         return 0;
 231 }
 232
 233 /* Compare class for the sort that does the intial partition of compaction. */
 234 int InitPartitionCompare::compare( const StateAp *state1 , const StateAp *state2 )
 235 {
 236         int compareRes;
 237
 238         /* Test final state status. */
 239         if ( (state1->stateBits & SB_ISFINAL) && !(state2->stateBits & SB_ISFINAL) )
 240                 return -1;
 241         else if ( !(state1->stateBits & SB_ISFINAL) && (state2->stateBits & SB_ISFINAL) )
 242                 return 1;
 243
 244         /* Test epsilon transition sets. */
 245         compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans,
 246                         state2->epsilonTrans );
 247         if ( compareRes != 0 )
 248                 return compareRes;
 249
 250         /* Compare the out transitions. */
 251         compareRes = FsmAp::compareStateData( state1, state2 );
 252         if ( compareRes != 0 )
 253                 return compareRes;
 254
 255         /* Use a pair iterator to test the condition pairs. */
 256         PairIter<StateCond> condPair( state1->stateCondList.head, state2->stateCondList.head );
 257         for ( ; !condPair.end(); condPair++ ) {
 258                 switch ( condPair.userState ) {
 259                 case RangeInS1:
 260                         return 1;
 261                 case RangeInS2:
 262                         return -1;
 263
 264                 case RangeOverlap: {
 265                         CondSpace *condSpace1 = condPair.s1Tel.trans->condSpace;
 266                         CondSpace *condSpace2 = condPair.s2Tel.trans->condSpace;
 267                         if ( condSpace1 < condSpace2 )
 268                                 return -1;
 269                         else if ( condSpace1 > condSpace2 )
 270                                 return 1;
 271                         break;
 272                 }
 273                 case BreakS1:
 274                 case BreakS2:
 275                         break;
 276                 }
 277         }
 278
 279         /* Use a pair iterator to test the transition pairs. */
 280         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 281         for ( ; !outPair.end(); outPair++ ) {
 282                 switch ( outPair.userState ) {
 283
 284                 case RangeInS1:
 285                         compareRes = FsmAp::compareDataPtr( outPair.s1Tel.trans, 0 );
 286                         if ( compareRes != 0 )
 287                                 return compareRes;
 288                         break;
 289
 290                 case RangeInS2:
 291                         compareRes = FsmAp::compareDataPtr( 0, outPair.s2Tel.trans );
 292                         if ( compareRes != 0 )
 293                                 return compareRes;
 294                         break;
 295
 296                 case RangeOverlap:
 297                         compareRes = FsmAp::compareDataPtr(
 298                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
 299                         if ( compareRes != 0 )
 300                                 return compareRes;
 301                         break;
 302
 303                 case BreakS1:
 304                 case BreakS2:
 305                         break;
 306                 }
 307         }
 308
 309         /* Not yet supporting minimization of states with EOF targets. */
 310         assert( state1->eofTarget == 0 && state2->eofTarget == 0 );
 311
 312         return 0;
 313 }
 314
 315 /* Compare class for the sort that does the partitioning. */
 316 int PartitionCompare::compare( const StateAp *state1, const StateAp *state2 )
 317 {
 318         int compareRes;
 319
 320         /* Use a pair iterator to get the transition pairs. */
 321         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 322         for ( ; !outPair.end(); outPair++ ) {
 323                 switch ( outPair.userState ) {
 324
 325                 case RangeInS1:
 326                         compareRes = FsmAp::comparePartPtr( outPair.s1Tel.trans, 0 );
 327                         if ( compareRes != 0 )
 328                                 return compareRes;
 329                         break;
 330
 331                 case RangeInS2:
 332                         compareRes = FsmAp::comparePartPtr( 0, outPair.s2Tel.trans );
 333                         if ( compareRes != 0 )
 334                                 return compareRes;
 335                         break;
 336
 337                 case RangeOverlap:
 338                         compareRes = FsmAp::comparePartPtr(
 339                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
 340                         if ( compareRes != 0 )
 341                                 return compareRes;
 342                         break;
 343
 344                 case BreakS1:
 345                 case BreakS2:
 346                         break;
 347                 }
 348         }
 349
 350         /* Not yet supporting minimization of states with EOF targets. */
 351         assert( state1->eofTarget == 0 && state2->eofTarget == 0 );
 352
 353         return 0;
 354 }
 355
 356 /* Compare class for the sort that does the partitioning. */
 357 bool MarkCompare::shouldMark( MarkIndex &markIndex, const StateAp *state1,
 358                         const StateAp *state2 )
 359 {
 360         /* Use a pair iterator to get the transition pairs. */
 361         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 362         for ( ; !outPair.end(); outPair++ ) {
 363                 switch ( outPair.userState ) {
 364
 365                 case RangeInS1:
 366                         if ( FsmAp::shouldMarkPtr( markIndex, outPair.s1Tel.trans, 0 ) )
 367                                 return true;
 368                         break;
 369
 370                 case RangeInS2:
 371                         if ( FsmAp::shouldMarkPtr( markIndex, 0, outPair.s2Tel.trans ) )
 372                                 return true;
 373                         break;
 374
 375                 case RangeOverlap:
 376                         if ( FsmAp::shouldMarkPtr( markIndex,
 377                                         outPair.s1Tel.trans, outPair.s2Tel.trans ) )
 378                                 return true;
 379                         break;
 380
 381                 case BreakS1:
 382                 case BreakS2:
 383                         break;
 384                 }
 385         }
 386
 387         return false;
 388 }
 389
 390 /*
 391  * Transition Comparison.
 392  */
 393
 394 /* Compare target partitions. Either pointer may be null. */
 395 int FsmAp::comparePartPtr( TransAp *trans1, TransAp *trans2 )
 396 {
 397         if ( trans1 != 0 ) {
 398                 /* If trans1 is set then so should trans2. The initial partitioning
 399                  * guarantees this for us. */
 400                 if ( trans1->toState == 0 && trans2->toState != 0 )
 401                         return -1;
 402                 else if ( trans1->toState != 0 && trans2->toState == 0 )
 403                         return 1;
 404                 else if ( trans1->toState != 0 ) {
 405                         /* Both of targets are set. */
 406                         return CmpOrd< MinPartition* >::compare(
 407                                 trans1->toState->alg.partition, trans2->toState->alg.partition );
 408                 }
 409         }
 410         return 0;
 411 }
 412
 413
 414 /* Compares two transition pointers according to priority and functions.
 415  * Either pointer may be null. Does not consider to state or from state. */
 416 int FsmAp::compareDataPtr( TransAp *trans1, TransAp *trans2 )
 417 {
 418         if ( trans1 == 0 && trans2 != 0 )
 419                 return -1;
 420         else if ( trans1 != 0 && trans2 == 0 )
 421                 return 1;
 422         else if ( trans1 != 0 ) {
 423                 /* Both of the transition pointers are set. */
 424                 int compareRes = compareTransData( trans1, trans2 );
 425                 if ( compareRes != 0 )
 426                         return compareRes;
 427         }
 428         return 0;
 429 }
 430
 431 /* Compares two transitions according to target state, priority and functions.
 432  * Does not consider from state. Either of the pointers may be null. */
 433 int FsmAp::compareFullPtr( TransAp *trans1, TransAp *trans2 )
 434 {
 435         if ( (trans1 != 0) ^ (trans2 != 0) ) {
 436                 /* Exactly one of the transitions is set. */
 437                 if ( trans1 != 0 )
 438                         return -1;
 439                 else
 440                         return 1;
 441         }
 442         else if ( trans1 != 0 ) {
 443                 /* Both of the transition pointers are set. Test target state,
 444                  * priority and funcs. */
 445                 if ( trans1->toState < trans2->toState )
 446                         return -1;
 447                 else if ( trans1->toState > trans2->toState )
 448                         return 1;
 449                 else if ( trans1->toState != 0 ) {
 450                         /* Test transition data. */
 451                         int compareRes = compareTransData( trans1, trans2 );
 452                         if ( compareRes != 0 )
 453                                 return compareRes;
 454                 }
 455         }
 456         return 0;
 457 }
 458
 459
 460 bool FsmAp::shouldMarkPtr( MarkIndex &markIndex, TransAp *trans1,
 461                                 TransAp *trans2 )
 462 {
 463         if ( (trans1 != 0) ^ (trans2 != 0) ) {
 464                 /* Exactly one of the transitions is set. The initial mark round
 465                  * should rule out this case. */
 466                 assert( false );
 467         }
 468         else if ( trans1 != 0 ) {
 469                 /* Both of the transitions are set. If the target pair is marked, then
 470                  * the pair we are considering gets marked. */
 471                 return markIndex.isPairMarked( trans1->toState->alg.stateNum,
 472                                 trans2->toState->alg.stateNum );
 473         }
 474
 475         /* Neither of the transitiosn are set. */
 476         return false;
 477 }
 478
 479