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                 assert( trans->lmActionTable.length() == 0 );
 160                 newTrans->toState = trans->toState;
 161                 outList.append( newTrans );
 162         }
 163 }
 164
 165 /* If there is a state dict element, then delete it. Everything else is left
 166  * up to the FsmGraph destructor. */
 167 StateAp::~StateAp()
 168 {
 169         if ( stateDictEl != 0 )
 170                 delete stateDictEl;
 171 }
 172
 173 /* Compare two states using pointers to the states. With the approximate
 174  * compare, the idea is that if the compare finds them the same, they can
 175  * immediately be merged. */
 176 int ApproxCompare::compare( const StateAp *state1, const StateAp *state2 )
 177 {
 178         int compareRes;
 179
 180         /* Test final state status. */
 181         if ( (state1->stateBits & STB_ISFINAL) && !(state2->stateBits & STB_ISFINAL) )
 182                 return -1;
 183         else if ( !(state1->stateBits & STB_ISFINAL) && (state2->stateBits & STB_ISFINAL) )
 184                 return 1;
 185
 186         /* Test epsilon transition sets. */
 187         compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans,
 188                         state2->epsilonTrans );
 189         if ( compareRes != 0 )
 190                 return compareRes;
 191
 192         /* Compare the out transitions. */
 193         compareRes = FsmAp::compareStateData( state1, state2 );
 194         if ( compareRes != 0 )
 195                 return compareRes;
 196
 197         /* Use a pair iterator to get the transition pairs. */
 198         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 199         for ( ; !outPair.end(); outPair++ ) {
 200                 switch ( outPair.userState ) {
 201
 202                 case RangeInS1:
 203                         compareRes = FsmAp::compareFullPtr( outPair.s1Tel.trans, 0 );
 204                         if ( compareRes != 0 )
 205                                 return compareRes;
 206                         break;
 207
 208                 case RangeInS2:
 209                         compareRes = FsmAp::compareFullPtr( 0, outPair.s2Tel.trans );
 210                         if ( compareRes != 0 )
 211                                 return compareRes;
 212                         break;
 213
 214                 case RangeOverlap:
 215                         compareRes = FsmAp::compareFullPtr(
 216                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
 217                         if ( compareRes != 0 )
 218                                 return compareRes;
 219                         break;
 220
 221                 case BreakS1:
 222                 case BreakS2:
 223                         break;
 224                 }
 225         }
 226
 227         /* Check EOF targets. */
 228         if ( state1->eofTarget < state2->eofTarget )
 229                 return -1;
 230         else if ( state1->eofTarget > state2->eofTarget )
 231                 return 1;
 232
 233         /* Got through the entire state comparison, deem them equal. */
 234         return 0;
 235 }
 236
 237 /* Compare class used in the initial partition. */
 238 int InitPartitionCompare::compare( const StateAp *state1 , const StateAp *state2 )
 239 {
 240         int compareRes;
 241
 242         /* Test final state status. */
 243         if ( (state1->stateBits & STB_ISFINAL) && !(state2->stateBits & STB_ISFINAL) )
 244                 return -1;
 245         else if ( !(state1->stateBits & STB_ISFINAL) && (state2->stateBits & STB_ISFINAL) )
 246                 return 1;
 247
 248         /* Test epsilon transition sets. */
 249         compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans,
 250                         state2->epsilonTrans );
 251         if ( compareRes != 0 )
 252                 return compareRes;
 253
 254         /* Compare the out transitions. */
 255         compareRes = FsmAp::compareStateData( state1, state2 );
 256         if ( compareRes != 0 )
 257                 return compareRes;
 258
 259         /* Use a pair iterator to test the condition pairs. */
 260         PairIter<StateCond> condPair( state1->stateCondList.head, state2->stateCondList.head );
 261         for ( ; !condPair.end(); condPair++ ) {
 262                 switch ( condPair.userState ) {
 263                 case RangeInS1:
 264                         return 1;
 265                 case RangeInS2:
 266                         return -1;
 267
 268                 case RangeOverlap: {
 269                         CondSpace *condSpace1 = condPair.s1Tel.trans->condSpace;
 270                         CondSpace *condSpace2 = condPair.s2Tel.trans->condSpace;
 271                         if ( condSpace1 < condSpace2 )
 272                                 return -1;
 273                         else if ( condSpace1 > condSpace2 )
 274                                 return 1;
 275                         break;
 276                 }
 277                 case BreakS1:
 278                 case BreakS2:
 279                         break;
 280                 }
 281         }
 282
 283         /* Use a pair iterator to test the transition pairs. */
 284         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 285         for ( ; !outPair.end(); outPair++ ) {
 286                 switch ( outPair.userState ) {
 287
 288                 case RangeInS1:
 289                         compareRes = FsmAp::compareDataPtr( outPair.s1Tel.trans, 0 );
 290                         if ( compareRes != 0 )
 291                                 return compareRes;
 292                         break;
 293
 294                 case RangeInS2:
 295                         compareRes = FsmAp::compareDataPtr( 0, outPair.s2Tel.trans );
 296                         if ( compareRes != 0 )
 297                                 return compareRes;
 298                         break;
 299
 300                 case RangeOverlap:
 301                         compareRes = FsmAp::compareDataPtr(
 302                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
 303                         if ( compareRes != 0 )
 304                                 return compareRes;
 305                         break;
 306
 307                 case BreakS1:
 308                 case BreakS2:
 309                         break;
 310                 }
 311         }
 312
 313         return 0;
 314 }
 315
 316 /* Compare class for the sort that does the partitioning. */
 317 int PartitionCompare::compare( const StateAp *state1, const StateAp *state2 )
 318 {
 319         int compareRes;
 320
 321         /* Use a pair iterator to get the transition pairs. */
 322         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 323         for ( ; !outPair.end(); outPair++ ) {
 324                 switch ( outPair.userState ) {
 325
 326                 case RangeInS1:
 327                         compareRes = FsmAp::comparePartPtr( outPair.s1Tel.trans, 0 );
 328                         if ( compareRes != 0 )
 329                                 return compareRes;
 330                         break;
 331
 332                 case RangeInS2:
 333                         compareRes = FsmAp::comparePartPtr( 0, outPair.s2Tel.trans );
 334                         if ( compareRes != 0 )
 335                                 return compareRes;
 336                         break;
 337
 338                 case RangeOverlap:
 339                         compareRes = FsmAp::comparePartPtr(
 340                                         outPair.s1Tel.trans, outPair.s2Tel.trans );
 341                         if ( compareRes != 0 )
 342                                 return compareRes;
 343                         break;
 344
 345                 case BreakS1:
 346                 case BreakS2:
 347                         break;
 348                 }
 349         }
 350
 351         /* Test eof targets. */
 352         if ( state1->eofTarget == 0 && state2->eofTarget != 0 )
 353                 return -1;
 354         else if ( state1->eofTarget != 0 && state2->eofTarget == 0 )
 355                 return 1;
 356         else if ( state1->eofTarget != 0 ) {
 357                 /* Both eof targets are set. */
 358                 compareRes = CmpOrd< MinPartition* >::compare(
 359                         state1->eofTarget->alg.partition, state2->eofTarget->alg.partition );
 360                 if ( compareRes != 0 )
 361                         return compareRes;
 362         }
 363
 364         return 0;
 365 }
 366
 367 /* Compare class for the sort that does the partitioning. */
 368 bool MarkCompare::shouldMark( MarkIndex &markIndex, const StateAp *state1,
 369                         const StateAp *state2 )
 370 {
 371         /* Use a pair iterator to get the transition pairs. */
 372         PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
 373         for ( ; !outPair.end(); outPair++ ) {
 374                 switch ( outPair.userState ) {
 375
 376                 case RangeInS1:
 377                         if ( FsmAp::shouldMarkPtr( markIndex, outPair.s1Tel.trans, 0 ) )
 378                                 return true;
 379                         break;
 380
 381                 case RangeInS2:
 382                         if ( FsmAp::shouldMarkPtr( markIndex, 0, outPair.s2Tel.trans ) )
 383                                 return true;
 384                         break;
 385
 386                 case RangeOverlap:
 387                         if ( FsmAp::shouldMarkPtr( markIndex,
 388                                         outPair.s1Tel.trans, outPair.s2Tel.trans ) )
 389                                 return true;
 390                         break;
 391
 392                 case BreakS1:
 393                 case BreakS2:
 394                         break;
 395                 }
 396         }
 397
 398         return false;
 399 }
 400
 401 /*
 402  * Transition Comparison.
 403  */
 404
 405 /* Compare target partitions. Either pointer may be null. */
 406 int FsmAp::comparePartPtr( TransAp *trans1, TransAp *trans2 )
 407 {
 408         if ( trans1 != 0 ) {
 409                 /* If trans1 is set then so should trans2. The initial partitioning
 410                  * guarantees this for us. */
 411                 if ( trans1->toState == 0 && trans2->toState != 0 )
 412                         return -1;
 413                 else if ( trans1->toState != 0 && trans2->toState == 0 )
 414                         return 1;
 415                 else if ( trans1->toState != 0 ) {
 416                         /* Both of targets are set. */
 417                         return CmpOrd< MinPartition* >::compare(
 418                                 trans1->toState->alg.partition, trans2->toState->alg.partition );
 419                 }
 420         }
 421         return 0;
 422 }
 423
 424
 425 /* Compares two transition pointers according to priority and functions.
 426  * Either pointer may be null. Does not consider to state or from state. */
 427 int FsmAp::compareDataPtr( TransAp *trans1, TransAp *trans2 )
 428 {
 429         if ( trans1 == 0 && trans2 != 0 )
 430                 return -1;
 431         else if ( trans1 != 0 && trans2 == 0 )
 432                 return 1;
 433         else if ( trans1 != 0 ) {
 434                 /* Both of the transition pointers are set. */
 435                 int compareRes = compareTransData( trans1, trans2 );
 436                 if ( compareRes != 0 )
 437                         return compareRes;
 438         }
 439         return 0;
 440 }
 441
 442 /* Compares two transitions according to target state, priority and functions.
 443  * Does not consider from state. Either of the pointers may be null. */
 444 int FsmAp::compareFullPtr( TransAp *trans1, TransAp *trans2 )
 445 {
 446         if ( (trans1 != 0) ^ (trans2 != 0) ) {
 447                 /* Exactly one of the transitions is set. */
 448                 if ( trans1 != 0 )
 449                         return -1;
 450                 else
 451                         return 1;
 452         }
 453         else if ( trans1 != 0 ) {
 454                 /* Both of the transition pointers are set. Test target state,
 455                  * priority and funcs. */
 456                 if ( trans1->toState < trans2->toState )
 457                         return -1;
 458                 else if ( trans1->toState > trans2->toState )
 459                         return 1;
 460                 else if ( trans1->toState != 0 ) {
 461                         /* Test transition data. */
 462                         int compareRes = compareTransData( trans1, trans2 );
 463                         if ( compareRes != 0 )
 464                                 return compareRes;
 465                 }
 466         }
 467         return 0;
 468 }
 469
 470
 471 bool FsmAp::shouldMarkPtr( MarkIndex &markIndex, TransAp *trans1,
 472                                 TransAp *trans2 )
 473 {
 474         if ( (trans1 != 0) ^ (trans2 != 0) ) {
 475                 /* Exactly one of the transitions is set. The initial mark round
 476                  * should rule out this case. */
 477                 assert( false );
 478         }
 479         else if ( trans1 != 0 ) {
 480                 /* Both of the transitions are set. If the target pair is marked, then
 481                  * the pair we are considering gets marked. */
 482                 return markIndex.isPairMarked( trans1->toState->alg.stateNum,
 483                                 trans2->toState->alg.stateNum );
 484         }
 485
 486         /* Neither of the transitiosn are set. */
 487         return false;
 488 }
 489
 490