ragel/fsmap.cpp

   1 /*
   2  *  Copyright 2002-2004 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 "fsmgraph.h"
  23 #include <iostream>
  24 using std::cerr;
  25 using std::endl;
  26
  27 CondData *condData = 0;
  28 KeyOps *keyOps = 0;
  29
  30 /* Insert an action into an action table. */
  31 void ActionTable::setAction( int ordering, Action *action )
  32 {
  33         /* Multi-insert in case specific instances of an action appear in a
  34          * transition more than once. */
  35         insertMulti( ordering, action );
  36 }
  37
  38 /* Set all the action from another action table in this table. */
  39 void ActionTable::setActions( const ActionTable &other )
  40 {
  41         for ( ActionTable::Iter action = other; action.lte(); action++ )
  42                 insertMulti( action->key, action->value );
  43 }
  44
  45 void ActionTable::setActions( int *orderings, Action **actions, int nActs )
  46 {
  47         for ( int a = 0; a < nActs; a++ )
  48                 insertMulti( orderings[a], actions[a] );
  49 }
  50
  51 bool ActionTable::hasAction( Action *action )
  52 {
  53         for ( int a = 0; a < length(); a++ ) {
  54                 if ( data[a].value == action )
  55                         return true;
  56         }
  57         return false;
  58 }
  59
  60 /* Insert an action into an action table. */
  61 void LmActionTable::setAction( int ordering, LongestMatchPart *action )
  62 {
  63         /* Multi-insert in case specific instances of an action appear in a
  64          * transition more than once. */
  65         insertMulti( ordering, action );
  66 }
  67
  68 /* Set all the action from another action table in this table. */
  69 void LmActionTable::setActions( const LmActionTable &other )
  70 {
  71         for ( LmActionTable::Iter action = other; action.lte(); action++ )
  72                 insertMulti( action->key, action->value );
  73 }
  74
  75 void ErrActionTable::setAction( int ordering, Action *action, int transferPoint )
  76 {
  77         insertMulti( ErrActionTableEl( action, ordering, transferPoint ) );
  78 }
  79
  80 void ErrActionTable::setActions( const ErrActionTable &other )
  81 {
  82         for ( ErrActionTable::Iter act = other; act.lte(); act++ )
  83                 insertMulti( ErrActionTableEl( act->action, act->ordering, act->transferPoint ) );
  84 }
  85
  86 /* Insert a priority into this priority table. Looks out for priorities on
  87  * duplicate keys. */
  88 void PriorTable::setPrior( int ordering, PriorDesc *desc )
  89 {
  90         PriorEl *lastHit = 0;
  91         PriorEl *insed = insert( PriorEl(ordering, desc), &lastHit );
  92         if ( insed == 0 ) {
  93                 /* This already has a priority on the same key as desc. Overwrite the
  94                  * priority if the ordering is larger (later in time). */
  95                 if ( ordering >= lastHit->ordering )
  96                         *lastHit = PriorEl( ordering, desc );
  97         }
  98 }
  99
 100 /* Set all the priorities from a priorTable in this table. */
 101 void PriorTable::setPriors( const PriorTable &other )
 102 {
 103         /* Loop src priorities once to overwrite duplicates. */
 104         PriorTable::Iter priorIt = other;
 105         for ( ; priorIt.lte(); priorIt++ )
 106                 setPrior( priorIt->ordering, priorIt->desc );
 107 }
 108
 109 /* Set the priority of starting transitions. Isolates the start state so it has
 110  * no other entry points, then sets the priorities of all the transitions out
 111  * of the start state. If the start state is final, then the outPrior of the
 112  * start state is also set. The idea is that a machine that accepts the null
 113  * string can still specify the starting trans prior for when it accepts the
 114  * null word. */
 115 void FsmAp::startFsmPrior( int ordering, PriorDesc *prior )
 116 {
 117         /* Make sure the start state has no other entry points. */
 118         isolateStartState();
 119
 120         /* Walk all transitions out of the start state. */
 121         for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) {
 122                 if ( trans->toState != 0 )
 123                         trans->priorTable.setPrior( ordering, prior );
 124         }
 125
 126         /* If the new start state is final then set the out priority. This follows
 127          * the same convention as setting start action in the out action table of
 128          * a final start state. */
 129         if ( startState->stateBits & SB_ISFINAL )
 130                 startState->outPriorTable.setPrior( ordering, prior );
 131 }
 132
 133 /* Set the priority of all transitions in a graph. Walks all transition lists
 134  * and all def transitions. */
 135 void FsmAp::allTransPrior( int ordering, PriorDesc *prior )
 136 {
 137         /* Walk the list of all states. */
 138         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 139                 /* Walk the out list of the state. */
 140                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 141                         if ( trans->toState != 0 )
 142                                 trans->priorTable.setPrior( ordering, prior );
 143                 }
 144         }
 145 }
 146
 147 /* Set the priority of all transitions that go into a final state. Note that if
 148  * any entry states are final, we will not be setting the priority of any
 149  * transitions that may go into those states in the future. The graph does not
 150  * support pending in transitions in the same way pending out transitions are
 151  * supported. */
 152 void FsmAp::finishFsmPrior( int ordering, PriorDesc *prior )
 153 {
 154         /* Walk all final states. */
 155         for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) {
 156                 /* Walk all in transitions of the final state. */
 157                 for ( TransInList::Iter trans = (*state)->inList; trans.lte(); trans++ )
 158                         trans->priorTable.setPrior( ordering, prior );
 159         }
 160 }
 161
 162 /* Set the priority of any future out transitions that may be made going out of
 163  * this state machine. */
 164 void FsmAp::leaveFsmPrior( int ordering, PriorDesc *prior )
 165 {
 166         /* Set priority in all final states. */
 167         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 168                 (*state)->outPriorTable.setPrior( ordering, prior );
 169 }
 170
 171
 172 /* Set actions to execute on starting transitions. Isolates the start state
 173  * so it has no other entry points, then adds to the transition functions
 174  * of all the transitions out of the start state. If the start state is final,
 175  * then the func is also added to the start state's out func list. The idea is
 176  * that a machine that accepts the null string can execute a start func when it
 177  * matches the null word, which can only be done when leaving the start/final
 178  * state. */
 179 void FsmAp::startFsmAction( int ordering, Action *action )
 180 {
 181         /* Make sure the start state has no other entry points. */
 182         isolateStartState();
 183
 184         /* Walk the start state's transitions, setting functions. */
 185         for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) {
 186                 if ( trans->toState != 0 )
 187                         trans->actionTable.setAction( ordering, action );
 188         }
 189
 190         /* If start state is final then add the action to the out action table.
 191          * This means that when the null string is accepted the start action will
 192          * not be bypassed. */
 193         if ( startState->stateBits & SB_ISFINAL )
 194                 startState->outActionTable.setAction( ordering, action );
 195 }
 196
 197 /* Set functions to execute on all transitions. Walks the out lists of all
 198  * states. */
 199 void FsmAp::allTransAction( int ordering, Action *action )
 200 {
 201         /* Walk all states. */
 202         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 203                 /* Walk the out list of the state. */
 204                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 205                         if ( trans->toState != 0 )
 206                                 trans->actionTable.setAction( ordering, action );
 207                 }
 208         }
 209 }
 210
 211 /* Specify functions to execute upon entering final states. If the start state
 212  * is final we can't really specify a function to execute upon entering that
 213  * final state the first time. So function really means whenever entering a
 214  * final state from within the same fsm. */
 215 void FsmAp::finishFsmAction( int ordering, Action *action )
 216 {
 217         /* Walk all final states. */
 218         for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) {
 219                 /* Walk the final state's in list. */
 220                 for ( TransInList::Iter trans = (*state)->inList; trans.lte(); trans++ )
 221                         trans->actionTable.setAction( ordering, action );
 222         }
 223 }
 224
 225 /* Add functions to any future out transitions that may be made going out of
 226  * this state machine. */
 227 void FsmAp::leaveFsmAction( int ordering, Action *action )
 228 {
 229         /* Insert the action in the outActionTable of all final states. */
 230         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 231                 (*state)->outActionTable.setAction( ordering, action );
 232 }
 233
 234 /* Add functions to the longest match action table for constructing scanners. */
 235 void FsmAp::longMatchAction( int ordering, LongestMatchPart *lmPart )
 236 {
 237         /* Walk all final states. */
 238         for ( StateSet::Iter state = finStateSet; state.lte(); state++ ) {
 239                 /* Walk the final state's in list. */
 240                 for ( TransInList::Iter trans = (*state)->inList; trans.lte(); trans++ )
 241                         trans->lmActionTable.setAction( ordering, lmPart );
 242         }
 243 }
 244
 245 void FsmAp::fillGaps( StateAp *state )
 246 {
 247         if ( state->outList.length() == 0 ) {
 248                 /* Add the range on the lower and upper bound. */
 249                 attachNewTrans( state, 0, keyOps->minKey, keyOps->maxKey );
 250         }
 251         else {
 252                 TransList srcList;
 253                 srcList.transfer( state->outList );
 254
 255                 /* Check for a gap at the beginning. */
 256                 TransList::Iter trans = srcList, next;
 257                 if ( keyOps->minKey < trans->lowKey ) {
 258                         /* Make the high key and append. */
 259                         Key highKey = trans->lowKey;
 260                         highKey.decrement();
 261
 262                         attachNewTrans( state, 0, keyOps->minKey, highKey );
 263                 }
 264
 265                 /* Write the transition. */
 266                 next = trans.next();
 267                 state->outList.append( trans );
 268
 269                 /* Keep the last high end. */
 270                 Key lastHigh = trans->highKey;
 271
 272                 /* Loop each source range. */
 273                 for ( trans = next; trans.lte(); trans = next ) {
 274                         /* Make the next key following the last range. */
 275                         Key nextKey = lastHigh;
 276                         nextKey.increment();
 277
 278                         /* Check for a gap from last up to here. */
 279                         if ( nextKey < trans->lowKey ) {
 280                                 /* Make the high end of the range that fills the gap. */
 281                                 Key highKey = trans->lowKey;
 282                                 highKey.decrement();
 283
 284                                 attachNewTrans( state, 0, nextKey, highKey );
 285                         }
 286
 287                         /* Reduce the transition. If it reduced to anything then add it. */
 288                         next = trans.next();
 289                         state->outList.append( trans );
 290
 291                         /* Keep the last high end. */
 292                         lastHigh = trans->highKey;
 293                 }
 294
 295                 /* Now check for a gap on the end to fill. */
 296                 if ( lastHigh < keyOps->maxKey ) {
 297                         /* Get a copy of the default. */
 298                         lastHigh.increment();
 299
 300                         attachNewTrans( state, 0, lastHigh, keyOps->maxKey );
 301                 }
 302         }
 303 }
 304
 305 void FsmAp::setErrorAction( StateAp *state, int ordering, Action *action )
 306 {
 307         /* Fill any gaps in the out list with an error transition. */
 308         fillGaps( state );
 309
 310         /* Set error transitions in the transitions that go to error. */
 311         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 312                 if ( trans->toState == 0 )
 313                         trans->actionTable.setAction( ordering, action );
 314         }
 315 }
 316
 317
 318 /* Give a target state for error transitions. */
 319 void FsmAp::setErrorTarget( StateAp *state, StateAp *target, int *orderings,
 320                         Action **actions, int nActs )
 321 {
 322         /* Fill any gaps in the out list with an error transition. */
 323         fillGaps( state );
 324
 325         /* Set error target in the transitions that go to error. */
 326         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 327                 if ( trans->toState == 0 ) {
 328                         /* The trans goes to error, redirect it. */
 329                         redirectErrorTrans( trans->fromState, target, trans );
 330                         trans->actionTable.setActions( orderings, actions, nActs );
 331                 }
 332         }
 333 }
 334
 335 void FsmAp::transferOutActions( StateAp *state )
 336 {
 337         for ( ActionTable::Iter act = state->outActionTable; act.lte(); act++ )
 338                 state->eofActionTable.setAction( act->key, act->value );
 339         state->outActionTable.empty();
 340 }
 341
 342 void FsmAp::transferErrorActions( StateAp *state, int transferPoint )
 343 {
 344         for ( int i = 0; i < state->errActionTable.length(); ) {
 345                 ErrActionTableEl *act = state->errActionTable.data + i;
 346                 if ( act->transferPoint == transferPoint ) {
 347                         /* Transfer the error action and remove it. */
 348                         setErrorAction( state, act->ordering, act->action );
 349                         if ( ! state->isFinState() )
 350                                 state->eofActionTable.setAction( act->ordering, act->action );
 351                         state->errActionTable.vremove( i );
 352                 }
 353                 else {
 354                         /* Not transfering and deleting, skip over the item. */
 355                         i += 1;
 356                 }
 357         }
 358 }
 359
 360 /* Set error actions in the start state. */
 361 void FsmAp::startErrorAction( int ordering, Action *action, int transferPoint )
 362 {
 363         /* Make sure the start state has no other entry points. */
 364         isolateStartState();
 365
 366         /* Add the actions. */
 367         startState->errActionTable.setAction( ordering, action, transferPoint );
 368 }
 369
 370 /* Set error actions in all states where there is a transition out. */
 371 void FsmAp::allErrorAction( int ordering, Action *action, int transferPoint )
 372 {
 373         /* Insert actions in the error action table of all states. */
 374         for ( StateList::Iter state = stateList; state.lte(); state++ )
 375                 state->errActionTable.setAction( ordering, action, transferPoint );
 376 }
 377
 378 /* Set error actions in final states. */
 379 void FsmAp::finalErrorAction( int ordering, Action *action, int transferPoint )
 380 {
 381         /* Add the action to the error table of final states. */
 382         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 383                 (*state)->errActionTable.setAction( ordering, action, transferPoint );
 384 }
 385
 386 void FsmAp::notStartErrorAction( int ordering, Action *action, int transferPoint )
 387 {
 388         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 389                 if ( state != startState )
 390                         state->errActionTable.setAction( ordering, action, transferPoint );
 391         }
 392 }
 393
 394 void FsmAp::notFinalErrorAction( int ordering, Action *action, int transferPoint )
 395 {
 396         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 397                 if ( ! state->isFinState() )
 398                         state->errActionTable.setAction( ordering, action, transferPoint );
 399         }
 400 }
 401
 402 /* Set error actions in the states that have transitions into a final state. */
 403 void FsmAp::middleErrorAction( int ordering, Action *action, int transferPoint )
 404 {
 405         /* Isolate the start state in case it is reachable from in inside the
 406          * machine, in which case we don't want it set. */
 407         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 408                 if ( state != startState && ! state->isFinState() )
 409                         state->errActionTable.setAction( ordering, action, transferPoint );
 410         }
 411 }
 412
 413 /* Set EOF actions in the start state. */
 414 void FsmAp::startEOFAction( int ordering, Action *action )
 415 {
 416         /* Make sure the start state has no other entry points. */
 417         isolateStartState();
 418
 419         /* Add the actions. */
 420         startState->eofActionTable.setAction( ordering, action );
 421 }
 422
 423 /* Set EOF actions in all states where there is a transition out. */
 424 void FsmAp::allEOFAction( int ordering, Action *action )
 425 {
 426         /* Insert actions in the EOF action table of all states. */
 427         for ( StateList::Iter state = stateList; state.lte(); state++ )
 428                 state->eofActionTable.setAction( ordering, action );
 429 }
 430
 431 /* Set EOF actions in final states. */
 432 void FsmAp::finalEOFAction( int ordering, Action *action )
 433 {
 434         /* Add the action to the error table of final states. */
 435         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 436                 (*state)->eofActionTable.setAction( ordering, action );
 437 }
 438
 439 void FsmAp::notStartEOFAction( int ordering, Action *action )
 440 {
 441         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 442                 if ( state != startState )
 443                         state->eofActionTable.setAction( ordering, action );
 444         }
 445 }
 446
 447 void FsmAp::notFinalEOFAction( int ordering, Action *action )
 448 {
 449         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 450                 if ( ! state->isFinState() )
 451                         state->eofActionTable.setAction( ordering, action );
 452         }
 453 }
 454
 455 /* Set EOF actions in the states that have transitions into a final state. */
 456 void FsmAp::middleEOFAction( int ordering, Action *action )
 457 {
 458         /* Set the actions in all states that are not the start state and not final. */
 459         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 460                 if ( state != startState && ! state->isFinState() )
 461                         state->eofActionTable.setAction( ordering, action );
 462         }
 463 }
 464
 465 /*
 466  * Set To State Actions.
 467  */
 468
 469 /* Set to state actions in the start state. */
 470 void FsmAp::startToStateAction( int ordering, Action *action )
 471 {
 472         /* Make sure the start state has no other entry points. */
 473         isolateStartState();
 474         startState->toStateActionTable.setAction( ordering, action );
 475 }
 476
 477 /* Set to state actions in all states. */
 478 void FsmAp::allToStateAction( int ordering, Action *action )
 479 {
 480         /* Insert the action on all states. */
 481         for ( StateList::Iter state = stateList; state.lte(); state++ )
 482                 state->toStateActionTable.setAction( ordering, action );
 483 }
 484
 485 /* Set to state actions in final states. */
 486 void FsmAp::finalToStateAction( int ordering, Action *action )
 487 {
 488         /* Add the action to the error table of final states. */
 489         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 490                 (*state)->toStateActionTable.setAction( ordering, action );
 491 }
 492
 493 void FsmAp::notStartToStateAction( int ordering, Action *action )
 494 {
 495         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 496                 if ( state != startState )
 497                         state->toStateActionTable.setAction( ordering, action );
 498         }
 499 }
 500
 501 void FsmAp::notFinalToStateAction( int ordering, Action *action )
 502 {
 503         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 504                 if ( ! state->isFinState() )
 505                         state->toStateActionTable.setAction( ordering, action );
 506         }
 507 }
 508
 509 /* Set to state actions in states that are not final and not the start state. */
 510 void FsmAp::middleToStateAction( int ordering, Action *action )
 511 {
 512         /* Set the action in all states that are not the start state and not final. */
 513         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 514                 if ( state != startState && ! state->isFinState() )
 515                         state->toStateActionTable.setAction( ordering, action );
 516         }
 517 }
 518
 519 /*
 520  * Set From State Actions.
 521  */
 522
 523 void FsmAp::startFromStateAction( int ordering, Action *action )
 524 {
 525         /* Make sure the start state has no other entry points. */
 526         isolateStartState();
 527         startState->fromStateActionTable.setAction( ordering, action );
 528 }
 529
 530 void FsmAp::allFromStateAction( int ordering, Action *action )
 531 {
 532         /* Insert the action on all states. */
 533         for ( StateList::Iter state = stateList; state.lte(); state++ )
 534                 state->fromStateActionTable.setAction( ordering, action );
 535 }
 536
 537 void FsmAp::finalFromStateAction( int ordering, Action *action )
 538 {
 539         /* Add the action to the error table of final states. */
 540         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 541                 (*state)->fromStateActionTable.setAction( ordering, action );
 542 }
 543
 544 void FsmAp::notStartFromStateAction( int ordering, Action *action )
 545 {
 546         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 547                 if ( state != startState )
 548                         state->fromStateActionTable.setAction( ordering, action );
 549         }
 550 }
 551
 552 void FsmAp::notFinalFromStateAction( int ordering, Action *action )
 553 {
 554         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 555                 if ( ! state->isFinState() )
 556                         state->fromStateActionTable.setAction( ordering, action );
 557         }
 558 }
 559
 560 void FsmAp::middleFromStateAction( int ordering, Action *action )
 561 {
 562         /* Set the action in all states that are not the start state and not final. */
 563         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 564                 if ( state != startState && ! state->isFinState() )
 565                         state->fromStateActionTable.setAction( ordering, action );
 566         }
 567 }
 568
 569 /* Shift the function ordering of the start transitions to start
 570  * at fromOrder and increase in units of 1. Useful before staring.
 571  * Returns the maximum number of order numbers used. */
 572 int FsmAp::shiftStartActionOrder( int fromOrder )
 573 {
 574         int maxUsed = 0;
 575
 576         /* Walk the start state's transitions, shifting function ordering. */
 577         for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) {
 578                 /* Walk the function data for the transition and set the keys to
 579                  * increasing values starting at fromOrder. */
 580                 int curFromOrder = fromOrder;
 581                 ActionTable::Iter action = trans->actionTable;
 582                 for ( ; action.lte(); action++ )
 583                         action->key = curFromOrder++;
 584
 585                 /* Keep track of the max number of orders used. */
 586                 if ( curFromOrder - fromOrder > maxUsed )
 587                         maxUsed = curFromOrder - fromOrder;
 588         }
 589
 590         return maxUsed;
 591 }
 592
 593 /* Remove all priorities. */
 594 void FsmAp::clearAllPriorities()
 595 {
 596         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 597                 /* Clear out priority data. */
 598                 state->outPriorTable.empty();
 599
 600                 /* Clear transition data from the out transitions. */
 601                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ )
 602                         trans->priorTable.empty();
 603         }
 604 }
 605
 606 /* Zeros out the function ordering keys. This may be called before minimization
 607  * when it is known that no more fsm operations are going to be done.  This
 608  * will achieve greater reduction as states will not be separated on the basis
 609  * of function ordering. */
 610 void FsmAp::nullActionKeys( )
 611 {
 612         /* For each state... */
 613         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 614                 /* Walk the transitions for the state. */
 615                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 616                         /* Walk the action table for the transition. */
 617                         for ( ActionTable::Iter action = trans->actionTable;
 618                                         action.lte(); action++ )
 619                                 action->key = 0;
 620
 621                         /* Walk the action table for the transition. */
 622                         for ( LmActionTable::Iter action = trans->lmActionTable;
 623                                         action.lte(); action++ )
 624                                 action->key = 0;
 625                 }
 626
 627                 /* Null the action keys of the to state action table. */
 628                 for ( ActionTable::Iter action = state->toStateActionTable;
 629                                 action.lte(); action++ )
 630                         action->key = 0;
 631
 632                 /* Null the action keys of the from state action table. */
 633                 for ( ActionTable::Iter action = state->fromStateActionTable;
 634                                 action.lte(); action++ )
 635                         action->key = 0;
 636
 637                 /* Null the action keys of the out transtions. */
 638                 for ( ActionTable::Iter action = state->outActionTable;
 639                                 action.lte(); action++ )
 640                         action->key = 0;
 641
 642                 /* Null the action keys of the error action table. */
 643                 for ( ErrActionTable::Iter action = state->errActionTable;
 644                                 action.lte(); action++ )
 645                         action->ordering = 0;
 646
 647                 /* Null the action keys eof action table. */
 648                 for ( ActionTable::Iter action = state->eofActionTable;
 649                                 action.lte(); action++ )
 650                         action->key = 0;
 651         }
 652 }
 653
 654 /* Walk the list of states and verify that non final states do not have out
 655  * data, that all stateBits are cleared, and that there are no states with
 656  * zero foreign in transitions. */
 657 void FsmAp::verifyStates()
 658 {
 659         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 660                 /* Non final states should not have leaving data. */
 661                 if ( ! (state->stateBits & SB_ISFINAL) ) {
 662                         assert( state->outActionTable.length() == 0 );
 663                         assert( state->outCondSet.length() == 0 );
 664                         assert( state->outPriorTable.length() == 0 );
 665                 }
 666
 667                 /* Data used in algorithms should be cleared. */
 668                 assert( (state->stateBits & SB_BOTH) == 0 );
 669                 assert( state->foreignInTrans > 0 );
 670         }
 671 }
 672
 673 /* Compare two transitions according to their relative priority. Since the
 674  * base transition has no priority associated with it, the default is to
 675  * return equal. */
 676 int FsmAp::comparePrior( const PriorTable &priorTable1, const PriorTable &priorTable2 )
 677 {
 678         /* Looking for differing priorities on same keys. Need to concurrently
 679          * scan the priority lists. */
 680         PriorTable::Iter pd1 = priorTable1;
 681         PriorTable::Iter pd2 = priorTable2;
 682         while ( pd1.lte() && pd2.lte() ) {
 683                 /* Check keys. */
 684                 if ( pd1->desc->key < pd2->desc->key )
 685                         pd1.increment();
 686                 else if ( pd1->desc->key > pd2->desc->key )
 687                         pd2.increment();
 688                 /* Keys are the same, check priorities. */
 689                 else if ( pd1->desc->priority < pd2->desc->priority )
 690                         return -1;
 691                 else if ( pd1->desc->priority > pd2->desc->priority )
 692                         return 1;
 693                 else {
 694                         /* Keys and priorities are equal, advance both. */
 695                         pd1.increment();
 696                         pd2.increment();
 697                 }
 698         }
 699
 700         /* No differing priorities on the same key. */
 701         return 0;
 702 }
 703
 704 /* Compares two transitions according to priority and functions. Pointers
 705  * should not be null. Does not consider to state or from state.  Compare two
 706  * transitions according to the data contained in the transitions.  Data means
 707  * any properties added to user transitions that may differentiate them. Since
 708  * the base transition has no data, the default is to return equal. */
 709 int FsmAp::compareTransData( TransAp *trans1, TransAp *trans2 )
 710 {
 711         /* Compare the prior table. */
 712         int cmpRes = CmpPriorTable::compare( trans1->priorTable,
 713                         trans2->priorTable );
 714         if ( cmpRes != 0 )
 715                 return cmpRes;
 716
 717         /* Compare longest match action tables. */
 718         cmpRes = CmpLmActionTable::compare(trans1->lmActionTable,
 719                         trans2->lmActionTable);
 720         if ( cmpRes != 0 )
 721                 return cmpRes;
 722
 723         /* Compare action tables. */
 724         return CmpActionTable::compare(trans1->actionTable,
 725                         trans2->actionTable);
 726 }
 727
 728 /* Callback invoked when another trans (or possibly this) is added into this
 729  * transition during the merging process.  Draw in any properties of srcTrans
 730  * into this transition. AddInTrans is called when a new transitions is made
 731  * that will be a duplicate of another transition or a combination of several
 732  * other transitions. AddInTrans will be called for each transition that the
 733  * new transition is to represent. */
 734 void FsmAp::addInTrans( TransAp *destTrans, TransAp *srcTrans )
 735 {
 736         /* Protect against adding in from ourselves. */
 737         if ( srcTrans == destTrans ) {
 738                 /* Adding in ourselves, need to make a copy of the source transitions.
 739                  * The priorities are not copied in as that would have no effect. */
 740                 destTrans->lmActionTable.setActions( LmActionTable(srcTrans->lmActionTable) );
 741                 destTrans->actionTable.setActions( ActionTable(srcTrans->actionTable) );
 742         }
 743         else {
 744                 /* Not a copy of ourself, get the functions and priorities. */
 745                 destTrans->lmActionTable.setActions( srcTrans->lmActionTable );
 746                 destTrans->actionTable.setActions( srcTrans->actionTable );
 747                 destTrans->priorTable.setPriors( srcTrans->priorTable );
 748         }
 749 }
 750
 751 /* Compare the properties of states that are embedded by users. Compares out
 752  * priorities, out transitions, to, from, out, error and eof action tables. */
 753 int FsmAp::compareStateData( const StateAp *state1, const StateAp *state2 )
 754 {
 755         /* Compare the out priority table. */
 756         int cmpRes = CmpPriorTable::
 757                         compare( state1->outPriorTable, state2->outPriorTable );
 758         if ( cmpRes != 0 )
 759                 return cmpRes;
 760
 761         /* Test to state action tables. */
 762         cmpRes = CmpActionTable::compare( state1->toStateActionTable,
 763                         state2->toStateActionTable );
 764         if ( cmpRes != 0 )
 765                 return cmpRes;
 766
 767         /* Test from state action tables. */
 768         cmpRes = CmpActionTable::compare( state1->fromStateActionTable,
 769                         state2->fromStateActionTable );
 770         if ( cmpRes != 0 )
 771                 return cmpRes;
 772
 773         /* Test out action tables. */
 774         cmpRes = CmpActionTable::compare( state1->outActionTable,
 775                         state2->outActionTable );
 776         if ( cmpRes != 0 )
 777                 return cmpRes;
 778
 779         /* Test out condition sets. */
 780         cmpRes = CmpOutCondSet::compare( state1->outCondSet,
 781                         state2->outCondSet );
 782         if ( cmpRes != 0 )
 783                 return cmpRes;
 784
 785         /* Test out error action tables. */
 786         cmpRes = CmpErrActionTable::compare( state1->errActionTable,
 787                         state2->errActionTable );
 788         if ( cmpRes != 0 )
 789                 return cmpRes;
 790
 791         /* Test eof action tables. */
 792         return CmpActionTable::compare( state1->eofActionTable,
 793                         state2->eofActionTable );
 794 }
 795
 796
 797 /* Invoked when a state looses its final state status and the leaving
 798  * transition embedding data should be deleted. */
 799 void FsmAp::clearOutData( StateAp *state )
 800 {
 801         /* Kill the out actions and priorities. */
 802         state->outActionTable.empty();
 803         state->outCondSet.empty();
 804         state->outPriorTable.empty();
 805 }
 806
 807 bool FsmAp::hasOutData( StateAp *state )
 808 {
 809         return ( state->outActionTable.length() > 0 ||
 810                         state->outCondSet.length() > 0 ||
 811                         state->outPriorTable.length() > 0 );
 812 }
 813
 814 /*
 815  * Setting Conditions.
 816  */
 817
 818
 819 void logNewExpansion( Expansion *exp );
 820 void logCondSpace( CondSpace *condSpace );
 821
 822 CondSpace *FsmAp::addCondSpace( const CondSet &condSet )
 823 {
 824         CondSpace *condSpace = condData->condSpaceMap.find( condSet );
 825         if ( condSpace == 0 ) {
 826                 /* Do we have enough keyspace left? */
 827                 Size availableSpace = condData->lastCondKey.availableSpace();
 828                 Size neededSpace = (1 << condSet.length() ) * keyOps->alphSize();
 829                 if ( neededSpace > availableSpace )
 830                         throw FsmConstructFail( FsmConstructFail::CondNoKeySpace );
 831
 832                 Key baseKey = condData->lastCondKey;
 833                 baseKey.increment();
 834                 condData->lastCondKey += (1 << condSet.length() ) * keyOps->alphSize();
 835
 836                 condSpace = new CondSpace( condSet );
 837                 condSpace->baseKey = baseKey;
 838                 condData->condSpaceMap.insert( condSpace );
 839
 840                 #ifdef LOG_CONDS
 841                 cerr << "adding new condition space" << endl;
 842                 cerr << "  condition set: ";
 843                 logCondSpace( condSpace );
 844                 cerr << endl;
 845                 cerr << "  baseKey: " << baseKey.getVal() << endl;
 846                 #endif
 847         }
 848         return condSpace;
 849 }
 850
 851 void FsmAp::startFsmCondition( Action *condAction, bool sense )
 852 {
 853         /* Make sure the start state has no other entry points. */
 854         isolateStartState();
 855         embedCondition( startState, condAction, sense );
 856 }
 857
 858 void FsmAp::allTransCondition( Action *condAction, bool sense )
 859 {
 860         for ( StateList::Iter state = stateList; state.lte(); state++ )
 861                 embedCondition( state, condAction, sense );
 862 }
 863
 864 void FsmAp::leaveFsmCondition( Action *condAction, bool sense )
 865 {
 866         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 867                 (*state)->outCondSet.insert( OutCond( condAction, sense ) );
 868 }