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 & STB_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 & STB_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::setErrorActions( StateAp *state, const ActionTable &other )
 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.setActions( other );
 314         }
 315 }
 316
 317 void FsmAp::setErrorAction( StateAp *state, int ordering, Action *action )
 318 {
 319         /* Fill any gaps in the out list with an error transition. */
 320         fillGaps( state );
 321
 322         /* Set error transitions in the transitions that go to error. */
 323         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 324                 if ( trans->toState == 0 )
 325                         trans->actionTable.setAction( ordering, action );
 326         }
 327 }
 328
 329
 330 /* Give a target state for error transitions. */
 331 void FsmAp::setErrorTarget( StateAp *state, StateAp *target, int *orderings,
 332                         Action **actions, int nActs )
 333 {
 334         /* Fill any gaps in the out list with an error transition. */
 335         fillGaps( state );
 336
 337         /* Set error target in the transitions that go to error. */
 338         for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 339                 if ( trans->toState == 0 ) {
 340                         /* The trans goes to error, redirect it. */
 341                         redirectErrorTrans( trans->fromState, target, trans );
 342                         trans->actionTable.setActions( orderings, actions, nActs );
 343                 }
 344         }
 345 }
 346
 347 void FsmAp::transferOutActions( StateAp *state )
 348 {
 349         for ( ActionTable::Iter act = state->outActionTable; act.lte(); act++ )
 350                 state->eofActionTable.setAction( act->key, act->value );
 351         state->outActionTable.empty();
 352 }
 353
 354 void FsmAp::transferErrorActions( StateAp *state, int transferPoint )
 355 {
 356         for ( int i = 0; i < state->errActionTable.length(); ) {
 357                 ErrActionTableEl *act = state->errActionTable.data + i;
 358                 if ( act->transferPoint == transferPoint ) {
 359                         /* Transfer the error action and remove it. */
 360                         setErrorAction( state, act->ordering, act->action );
 361                         if ( ! state->isFinState() )
 362                                 state->eofActionTable.setAction( act->ordering, act->action );
 363                         state->errActionTable.vremove( i );
 364                 }
 365                 else {
 366                         /* Not transfering and deleting, skip over the item. */
 367                         i += 1;
 368                 }
 369         }
 370 }
 371
 372 /* Set error actions in the start state. */
 373 void FsmAp::startErrorAction( int ordering, Action *action, int transferPoint )
 374 {
 375         /* Make sure the start state has no other entry points. */
 376         isolateStartState();
 377
 378         /* Add the actions. */
 379         startState->errActionTable.setAction( ordering, action, transferPoint );
 380 }
 381
 382 /* Set error actions in all states where there is a transition out. */
 383 void FsmAp::allErrorAction( int ordering, Action *action, int transferPoint )
 384 {
 385         /* Insert actions in the error action table of all states. */
 386         for ( StateList::Iter state = stateList; state.lte(); state++ )
 387                 state->errActionTable.setAction( ordering, action, transferPoint );
 388 }
 389
 390 /* Set error actions in final states. */
 391 void FsmAp::finalErrorAction( int ordering, Action *action, int transferPoint )
 392 {
 393         /* Add the action to the error table of final states. */
 394         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 395                 (*state)->errActionTable.setAction( ordering, action, transferPoint );
 396 }
 397
 398 void FsmAp::notStartErrorAction( int ordering, Action *action, int transferPoint )
 399 {
 400         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 401                 if ( state != startState )
 402                         state->errActionTable.setAction( ordering, action, transferPoint );
 403         }
 404 }
 405
 406 void FsmAp::notFinalErrorAction( int ordering, Action *action, int transferPoint )
 407 {
 408         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 409                 if ( ! state->isFinState() )
 410                         state->errActionTable.setAction( ordering, action, transferPoint );
 411         }
 412 }
 413
 414 /* Set error actions in the states that have transitions into a final state. */
 415 void FsmAp::middleErrorAction( int ordering, Action *action, int transferPoint )
 416 {
 417         /* Isolate the start state in case it is reachable from in inside the
 418          * machine, in which case we don't want it set. */
 419         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 420                 if ( state != startState && ! state->isFinState() )
 421                         state->errActionTable.setAction( ordering, action, transferPoint );
 422         }
 423 }
 424
 425 /* Set EOF actions in the start state. */
 426 void FsmAp::startEOFAction( int ordering, Action *action )
 427 {
 428         /* Make sure the start state has no other entry points. */
 429         isolateStartState();
 430
 431         /* Add the actions. */
 432         startState->eofActionTable.setAction( ordering, action );
 433 }
 434
 435 /* Set EOF actions in all states where there is a transition out. */
 436 void FsmAp::allEOFAction( int ordering, Action *action )
 437 {
 438         /* Insert actions in the EOF action table of all states. */
 439         for ( StateList::Iter state = stateList; state.lte(); state++ )
 440                 state->eofActionTable.setAction( ordering, action );
 441 }
 442
 443 /* Set EOF actions in final states. */
 444 void FsmAp::finalEOFAction( int ordering, Action *action )
 445 {
 446         /* Add the action to the error table of final states. */
 447         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 448                 (*state)->eofActionTable.setAction( ordering, action );
 449 }
 450
 451 void FsmAp::notStartEOFAction( int ordering, Action *action )
 452 {
 453         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 454                 if ( state != startState )
 455                         state->eofActionTable.setAction( ordering, action );
 456         }
 457 }
 458
 459 void FsmAp::notFinalEOFAction( int ordering, Action *action )
 460 {
 461         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 462                 if ( ! state->isFinState() )
 463                         state->eofActionTable.setAction( ordering, action );
 464         }
 465 }
 466
 467 /* Set EOF actions in the states that have transitions into a final state. */
 468 void FsmAp::middleEOFAction( int ordering, Action *action )
 469 {
 470         /* Set the actions in all states that are not the start state and not final. */
 471         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 472                 if ( state != startState && ! state->isFinState() )
 473                         state->eofActionTable.setAction( ordering, action );
 474         }
 475 }
 476
 477 /*
 478  * Set To State Actions.
 479  */
 480
 481 /* Set to state actions in the start state. */
 482 void FsmAp::startToStateAction( int ordering, Action *action )
 483 {
 484         /* Make sure the start state has no other entry points. */
 485         isolateStartState();
 486         startState->toStateActionTable.setAction( ordering, action );
 487 }
 488
 489 /* Set to state actions in all states. */
 490 void FsmAp::allToStateAction( int ordering, Action *action )
 491 {
 492         /* Insert the action on all states. */
 493         for ( StateList::Iter state = stateList; state.lte(); state++ )
 494                 state->toStateActionTable.setAction( ordering, action );
 495 }
 496
 497 /* Set to state actions in final states. */
 498 void FsmAp::finalToStateAction( int ordering, Action *action )
 499 {
 500         /* Add the action to the error table of final states. */
 501         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 502                 (*state)->toStateActionTable.setAction( ordering, action );
 503 }
 504
 505 void FsmAp::notStartToStateAction( int ordering, Action *action )
 506 {
 507         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 508                 if ( state != startState )
 509                         state->toStateActionTable.setAction( ordering, action );
 510         }
 511 }
 512
 513 void FsmAp::notFinalToStateAction( int ordering, Action *action )
 514 {
 515         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 516                 if ( ! state->isFinState() )
 517                         state->toStateActionTable.setAction( ordering, action );
 518         }
 519 }
 520
 521 /* Set to state actions in states that are not final and not the start state. */
 522 void FsmAp::middleToStateAction( int ordering, Action *action )
 523 {
 524         /* Set the action in all states that are not the start state and not final. */
 525         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 526                 if ( state != startState && ! state->isFinState() )
 527                         state->toStateActionTable.setAction( ordering, action );
 528         }
 529 }
 530
 531 /*
 532  * Set From State Actions.
 533  */
 534
 535 void FsmAp::startFromStateAction( int ordering, Action *action )
 536 {
 537         /* Make sure the start state has no other entry points. */
 538         isolateStartState();
 539         startState->fromStateActionTable.setAction( ordering, action );
 540 }
 541
 542 void FsmAp::allFromStateAction( int ordering, Action *action )
 543 {
 544         /* Insert the action on all states. */
 545         for ( StateList::Iter state = stateList; state.lte(); state++ )
 546                 state->fromStateActionTable.setAction( ordering, action );
 547 }
 548
 549 void FsmAp::finalFromStateAction( int ordering, Action *action )
 550 {
 551         /* Add the action to the error table of final states. */
 552         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 553                 (*state)->fromStateActionTable.setAction( ordering, action );
 554 }
 555
 556 void FsmAp::notStartFromStateAction( int ordering, Action *action )
 557 {
 558         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 559                 if ( state != startState )
 560                         state->fromStateActionTable.setAction( ordering, action );
 561         }
 562 }
 563
 564 void FsmAp::notFinalFromStateAction( int ordering, Action *action )
 565 {
 566         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 567                 if ( ! state->isFinState() )
 568                         state->fromStateActionTable.setAction( ordering, action );
 569         }
 570 }
 571
 572 void FsmAp::middleFromStateAction( int ordering, Action *action )
 573 {
 574         /* Set the action in all states that are not the start state and not final. */
 575         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 576                 if ( state != startState && ! state->isFinState() )
 577                         state->fromStateActionTable.setAction( ordering, action );
 578         }
 579 }
 580
 581 /* Shift the function ordering of the start transitions to start
 582  * at fromOrder and increase in units of 1. Useful before staring.
 583  * Returns the maximum number of order numbers used. */
 584 int FsmAp::shiftStartActionOrder( int fromOrder )
 585 {
 586         int maxUsed = 0;
 587
 588         /* Walk the start state's transitions, shifting function ordering. */
 589         for ( TransList::Iter trans = startState->outList; trans.lte(); trans++ ) {
 590                 /* Walk the function data for the transition and set the keys to
 591                  * increasing values starting at fromOrder. */
 592                 int curFromOrder = fromOrder;
 593                 ActionTable::Iter action = trans->actionTable;
 594                 for ( ; action.lte(); action++ )
 595                         action->key = curFromOrder++;
 596
 597                 /* Keep track of the max number of orders used. */
 598                 if ( curFromOrder - fromOrder > maxUsed )
 599                         maxUsed = curFromOrder - fromOrder;
 600         }
 601
 602         return maxUsed;
 603 }
 604
 605 /* Remove all priorities. */
 606 void FsmAp::clearAllPriorities()
 607 {
 608         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 609                 /* Clear out priority data. */
 610                 state->outPriorTable.empty();
 611
 612                 /* Clear transition data from the out transitions. */
 613                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ )
 614                         trans->priorTable.empty();
 615         }
 616 }
 617
 618 /* Zeros out the function ordering keys. This may be called before minimization
 619  * when it is known that no more fsm operations are going to be done.  This
 620  * will achieve greater reduction as states will not be separated on the basis
 621  * of function ordering. */
 622 void FsmAp::nullActionKeys( )
 623 {
 624         /* For each state... */
 625         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 626                 /* Walk the transitions for the state. */
 627                 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
 628                         /* Walk the action table for the transition. */
 629                         for ( ActionTable::Iter action = trans->actionTable;
 630                                         action.lte(); action++ )
 631                                 action->key = 0;
 632
 633                         /* Walk the action table for the transition. */
 634                         for ( LmActionTable::Iter action = trans->lmActionTable;
 635                                         action.lte(); action++ )
 636                                 action->key = 0;
 637                 }
 638
 639                 /* Null the action keys of the to state action table. */
 640                 for ( ActionTable::Iter action = state->toStateActionTable;
 641                                 action.lte(); action++ )
 642                         action->key = 0;
 643
 644                 /* Null the action keys of the from state action table. */
 645                 for ( ActionTable::Iter action = state->fromStateActionTable;
 646                                 action.lte(); action++ )
 647                         action->key = 0;
 648
 649                 /* Null the action keys of the out transtions. */
 650                 for ( ActionTable::Iter action = state->outActionTable;
 651                                 action.lte(); action++ )
 652                         action->key = 0;
 653
 654                 /* Null the action keys of the error action table. */
 655                 for ( ErrActionTable::Iter action = state->errActionTable;
 656                                 action.lte(); action++ )
 657                         action->ordering = 0;
 658
 659                 /* Null the action keys eof action table. */
 660                 for ( ActionTable::Iter action = state->eofActionTable;
 661                                 action.lte(); action++ )
 662                         action->key = 0;
 663         }
 664 }
 665
 666 /* Walk the list of states and verify that non final states do not have out
 667  * data, that all stateBits are cleared, and that there are no states with
 668  * zero foreign in transitions. */
 669 void FsmAp::verifyStates()
 670 {
 671         for ( StateList::Iter state = stateList; state.lte(); state++ ) {
 672                 /* Non final states should not have leaving data. */
 673                 if ( ! (state->stateBits & STB_ISFINAL) ) {
 674                         assert( state->outActionTable.length() == 0 );
 675                         assert( state->outCondSet.length() == 0 );
 676                         assert( state->outPriorTable.length() == 0 );
 677                 }
 678
 679                 /* Data used in algorithms should be cleared. */
 680                 assert( (state->stateBits & STB_BOTH) == 0 );
 681                 assert( state->foreignInTrans > 0 );
 682         }
 683 }
 684
 685 /* Compare two transitions according to their relative priority. Since the
 686  * base transition has no priority associated with it, the default is to
 687  * return equal. */
 688 int FsmAp::comparePrior( const PriorTable &priorTable1, const PriorTable &priorTable2 )
 689 {
 690         /* Looking for differing priorities on same keys. Need to concurrently
 691          * scan the priority lists. */
 692         PriorTable::Iter pd1 = priorTable1;
 693         PriorTable::Iter pd2 = priorTable2;
 694         while ( pd1.lte() && pd2.lte() ) {
 695                 /* Check keys. */
 696                 if ( pd1->desc->key < pd2->desc->key )
 697                         pd1.increment();
 698                 else if ( pd1->desc->key > pd2->desc->key )
 699                         pd2.increment();
 700                 /* Keys are the same, check priorities. */
 701                 else if ( pd1->desc->priority < pd2->desc->priority )
 702                         return -1;
 703                 else if ( pd1->desc->priority > pd2->desc->priority )
 704                         return 1;
 705                 else {
 706                         /* Keys and priorities are equal, advance both. */
 707                         pd1.increment();
 708                         pd2.increment();
 709                 }
 710         }
 711
 712         /* No differing priorities on the same key. */
 713         return 0;
 714 }
 715
 716 /* Compares two transitions according to priority and functions. Pointers
 717  * should not be null. Does not consider to state or from state.  Compare two
 718  * transitions according to the data contained in the transitions.  Data means
 719  * any properties added to user transitions that may differentiate them. Since
 720  * the base transition has no data, the default is to return equal. */
 721 int FsmAp::compareTransData( TransAp *trans1, TransAp *trans2 )
 722 {
 723         /* Compare the prior table. */
 724         int cmpRes = CmpPriorTable::compare( trans1->priorTable,
 725                         trans2->priorTable );
 726         if ( cmpRes != 0 )
 727                 return cmpRes;
 728
 729         /* Compare longest match action tables. */
 730         cmpRes = CmpLmActionTable::compare(trans1->lmActionTable,
 731                         trans2->lmActionTable);
 732         if ( cmpRes != 0 )
 733                 return cmpRes;
 734
 735         /* Compare action tables. */
 736         return CmpActionTable::compare(trans1->actionTable,
 737                         trans2->actionTable);
 738 }
 739
 740 /* Callback invoked when another trans (or possibly this) is added into this
 741  * transition during the merging process.  Draw in any properties of srcTrans
 742  * into this transition. AddInTrans is called when a new transitions is made
 743  * that will be a duplicate of another transition or a combination of several
 744  * other transitions. AddInTrans will be called for each transition that the
 745  * new transition is to represent. */
 746 void FsmAp::addInTrans( TransAp *destTrans, TransAp *srcTrans )
 747 {
 748         /* Protect against adding in from ourselves. */
 749         if ( srcTrans == destTrans ) {
 750                 /* Adding in ourselves, need to make a copy of the source transitions.
 751                  * The priorities are not copied in as that would have no effect. */
 752                 destTrans->lmActionTable.setActions( LmActionTable(srcTrans->lmActionTable) );
 753                 destTrans->actionTable.setActions( ActionTable(srcTrans->actionTable) );
 754         }
 755         else {
 756                 /* Not a copy of ourself, get the functions and priorities. */
 757                 destTrans->lmActionTable.setActions( srcTrans->lmActionTable );
 758                 destTrans->actionTable.setActions( srcTrans->actionTable );
 759                 destTrans->priorTable.setPriors( srcTrans->priorTable );
 760         }
 761 }
 762
 763 /* Compare the properties of states that are embedded by users. Compares out
 764  * priorities, out transitions, to, from, out, error and eof action tables. */
 765 int FsmAp::compareStateData( const StateAp *state1, const StateAp *state2 )
 766 {
 767         /* Compare the out priority table. */
 768         int cmpRes = CmpPriorTable::
 769                         compare( state1->outPriorTable, state2->outPriorTable );
 770         if ( cmpRes != 0 )
 771                 return cmpRes;
 772
 773         /* Test to state action tables. */
 774         cmpRes = CmpActionTable::compare( state1->toStateActionTable,
 775                         state2->toStateActionTable );
 776         if ( cmpRes != 0 )
 777                 return cmpRes;
 778
 779         /* Test from state action tables. */
 780         cmpRes = CmpActionTable::compare( state1->fromStateActionTable,
 781                         state2->fromStateActionTable );
 782         if ( cmpRes != 0 )
 783                 return cmpRes;
 784
 785         /* Test out action tables. */
 786         cmpRes = CmpActionTable::compare( state1->outActionTable,
 787                         state2->outActionTable );
 788         if ( cmpRes != 0 )
 789                 return cmpRes;
 790
 791         /* Test out condition sets. */
 792         cmpRes = CmpOutCondSet::compare( state1->outCondSet,
 793                         state2->outCondSet );
 794         if ( cmpRes != 0 )
 795                 return cmpRes;
 796
 797         /* Test out error action tables. */
 798         cmpRes = CmpErrActionTable::compare( state1->errActionTable,
 799                         state2->errActionTable );
 800         if ( cmpRes != 0 )
 801                 return cmpRes;
 802
 803         /* Test eof action tables. */
 804         return CmpActionTable::compare( state1->eofActionTable,
 805                         state2->eofActionTable );
 806 }
 807
 808
 809 /* Invoked when a state looses its final state status and the leaving
 810  * transition embedding data should be deleted. */
 811 void FsmAp::clearOutData( StateAp *state )
 812 {
 813         /* Kill the out actions and priorities. */
 814         state->outActionTable.empty();
 815         state->outCondSet.empty();
 816         state->outPriorTable.empty();
 817 }
 818
 819 bool FsmAp::hasOutData( StateAp *state )
 820 {
 821         return ( state->outActionTable.length() > 0 ||
 822                         state->outCondSet.length() > 0 ||
 823                         state->outPriorTable.length() > 0 );
 824 }
 825
 826 /*
 827  * Setting Conditions.
 828  */
 829
 830
 831 void logNewExpansion( Expansion *exp );
 832 void logCondSpace( CondSpace *condSpace );
 833
 834 CondSpace *FsmAp::addCondSpace( const CondSet &condSet )
 835 {
 836         CondSpace *condSpace = condData->condSpaceMap.find( condSet );
 837         if ( condSpace == 0 ) {
 838                 /* Do we have enough keyspace left? */
 839                 Size availableSpace = condData->lastCondKey.availableSpace();
 840                 Size neededSpace = (1 << condSet.length() ) * keyOps->alphSize();
 841                 if ( neededSpace > availableSpace )
 842                         throw FsmConstructFail( FsmConstructFail::CondNoKeySpace );
 843
 844                 Key baseKey = condData->lastCondKey;
 845                 baseKey.increment();
 846                 condData->lastCondKey += (1 << condSet.length() ) * keyOps->alphSize();
 847
 848                 condSpace = new CondSpace( condSet );
 849                 condSpace->baseKey = baseKey;
 850                 condData->condSpaceMap.insert( condSpace );
 851
 852                 #ifdef LOG_CONDS
 853                 cerr << "adding new condition space" << endl;
 854                 cerr << "  condition set: ";
 855                 logCondSpace( condSpace );
 856                 cerr << endl;
 857                 cerr << "  baseKey: " << baseKey.getVal() << endl;
 858                 #endif
 859         }
 860         return condSpace;
 861 }
 862
 863 void FsmAp::startFsmCondition( Action *condAction, bool sense )
 864 {
 865         /* Make sure the start state has no other entry points. */
 866         isolateStartState();
 867         embedCondition( startState, condAction, sense );
 868 }
 869
 870 void FsmAp::allTransCondition( Action *condAction, bool sense )
 871 {
 872         for ( StateList::Iter state = stateList; state.lte(); state++ )
 873                 embedCondition( state, condAction, sense );
 874 }
 875
 876 void FsmAp::leaveFsmCondition( Action *condAction, bool sense )
 877 {
 878         for ( StateSet::Iter state = finStateSet; state.lte(); state++ )
 879                 (*state)->outCondSet.insert( OutCond( condAction, sense ) );
 880 }