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