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