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