ragel/fsmgraph.h

   1 /*
   2  *  Copyright 2001-2007 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 #ifndef _FSMGRAPH_H
  23 #define _FSMGRAPH_H
  24
  25 #include "config.h"
  26 #include <assert.h>
  27 #include <iostream>
  28 #include <string>
  29 #include "common.h"
  30 #include "vector.h"
  31 #include "bstset.h"
  32 #include "compare.h"
  33 #include "avltree.h"
  34 #include "dlist.h"
  35 #include "bstmap.h"
  36 #include "sbstmap.h"
  37 #include "sbstset.h"
  38 #include "sbsttable.h"
  39 #include "avlset.h"
  40 #include "avlmap.h"
  41 #include "ragel.h"
  42
  43 //#define LOG_CONDS
  44
  45 /* Flags that control merging. */
  46 #define SB_GRAPH1     0x01
  47 #define SB_GRAPH2     0x02
  48 #define SB_BOTH       0x03
  49 #define SB_ISFINAL    0x04
  50 #define SB_ISMARKED   0x08
  51 #define SB_ONLIST     0x10
  52
  53 using std::ostream;
  54
  55 struct TransAp;
  56 struct StateAp;
  57 struct FsmAp;
  58 struct Action;
  59 struct LongestMatchPart;
  60
  61 /* State list element for unambiguous access to list element. */
  62 struct FsmListEl
  63 {
  64         StateAp *prev, *next;
  65 };
  66
  67 /* This is the marked index for a state pair. Used in minimization. It keeps
  68  * track of whether or not the state pair is marked. */
  69 struct MarkIndex
  70 {
  71         MarkIndex(int states);
  72         ~MarkIndex();
  73
  74         void markPair(int state1, int state2);
  75         bool isPairMarked(int state1, int state2);
  76
  77 private:
  78         int numStates;
  79         bool *array;
  80 };
  81
  82 extern KeyOps *keyOps;
  83
  84 /* Transistion Action Element. */
  85 typedef SBstMapEl< int, Action* > ActionTableEl;
  86
  87 /* Nodes in the tree that use this action. */
  88 struct NameInst;
  89 struct InlineList;
  90 typedef Vector<NameInst*> ActionRefs;
  91
  92 /* Element in list of actions. Contains the string for the code to exectute. */
  93 struct Action
  94 :
  95         public DListEl<Action>,
  96         public AvlTreeEl<Action>
  97 {
  98 public:
  99
 100         Action( const InputLoc &loc, char *name, InlineList *inlineList, int condId )
 101         :
 102                 loc(loc),
 103                 name(name),
 104                 inlineList(inlineList),
 105                 actionId(-1),
 106                 numTransRefs(0),
 107                 numToStateRefs(0),
 108                 numFromStateRefs(0),
 109                 numEofRefs(0),
 110                 numCondRefs(0),
 111                 anyCall(false),
 112                 isLmAction(false),
 113                 condId(condId)
 114         {
 115         }
 116
 117         /* Key for action dictionary. */
 118         char *getKey() const { return name; }
 119
 120         /* Data collected during parse. */
 121         InputLoc loc;
 122         char *name;
 123         InlineList *inlineList;
 124         int actionId;
 125
 126         void actionName( ostream &out )
 127         {
 128                 if ( name != 0 )
 129                         out << name;
 130                 else
 131                         out << loc.line << ":" << loc.col;
 132         }
 133
 134         /* Places in the input text that reference the action. */
 135         ActionRefs actionRefs;
 136
 137         /* Number of references in the final machine. */
 138         int numRefs()
 139                 { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; }
 140         int numTransRefs;
 141         int numToStateRefs;
 142         int numFromStateRefs;
 143         int numEofRefs;
 144         int numCondRefs;
 145         bool anyCall;
 146
 147         bool isLmAction;
 148         int condId;
 149 };
 150
 151 struct CmpCondId
 152 {
 153         static inline int compare( const Action *cond1, const Action *cond2 )
 154         {
 155                 if ( cond1->condId < cond2->condId )
 156                         return -1;
 157                 else if ( cond1->condId > cond2->condId )
 158                         return 1;
 159                 return 0;
 160         }
 161 };
 162
 163 /* A list of actions. */
 164 typedef DList<Action> ActionList;
 165 typedef AvlTree<Action, char *, CmpStr> ActionDict;
 166
 167 /* Structure for reverse action mapping. */
 168 struct RevActionMapEl
 169 {
 170         char *name;
 171         InputLoc location;
 172 };
 173
 174
 175 /* Transition Action Table.  */
 176 struct ActionTable
 177         : public SBstMap< int, Action*, CmpOrd<int> >
 178 {
 179         void setAction( int ordering, Action *action );
 180         void setActions( int *orderings, Action **actions, int nActs );
 181         void setActions( const ActionTable &other );
 182
 183         bool hasAction( Action *action );
 184 };
 185
 186 typedef SBstSet< Action*, CmpOrd<Action*> > ActionSet;
 187 typedef CmpSTable< Action*, CmpOrd<Action*> > CmpActionSet;
 188
 189 /* Transistion Action Element. */
 190 typedef SBstMapEl< int, LongestMatchPart* > LmActionTableEl;
 191
 192 /* Transition Action Table.  */
 193 struct LmActionTable
 194         : public SBstMap< int, LongestMatchPart*, CmpOrd<int> >
 195 {
 196         void setAction( int ordering, LongestMatchPart *action );
 197         void setActions( const LmActionTable &other );
 198 };
 199
 200 /* Compare of a whole action table element (key & value). */
 201 struct CmpActionTableEl
 202 {
 203         static int compare( const ActionTableEl &action1,
 204                         const ActionTableEl &action2 )
 205         {
 206                 if ( action1.key < action2.key )
 207                         return -1;
 208                 else if ( action1.key > action2.key )
 209                         return 1;
 210                 else if ( action1.value < action2.value )
 211                         return -1;
 212                 else if ( action1.value > action2.value )
 213                         return 1;
 214                 return 0;
 215         }
 216 };
 217
 218 /* Compare for ActionTable. */
 219 typedef CmpSTable< ActionTableEl, CmpActionTableEl > CmpActionTable;
 220
 221 /* Compare of a whole lm action table element (key & value). */
 222 struct CmpLmActionTableEl
 223 {
 224         static int compare( const LmActionTableEl &lmAction1,
 225                         const LmActionTableEl &lmAction2 )
 226         {
 227                 if ( lmAction1.key < lmAction2.key )
 228                         return -1;
 229                 else if ( lmAction1.key > lmAction2.key )
 230                         return 1;
 231                 else if ( lmAction1.value < lmAction2.value )
 232                         return -1;
 233                 else if ( lmAction1.value > lmAction2.value )
 234                         return 1;
 235                 return 0;
 236         }
 237 };
 238
 239 /* Compare for ActionTable. */
 240 typedef CmpSTable< LmActionTableEl, CmpLmActionTableEl > CmpLmActionTable;
 241
 242 /* Action table element for error action tables. Adds the encoding of transfer
 243  * point. */
 244 struct ErrActionTableEl
 245 {
 246         ErrActionTableEl( Action *action, int ordering, int transferPoint )
 247                 : ordering(ordering), action(action), transferPoint(transferPoint) { }
 248
 249         /* Ordering and id of the action embedding. */
 250         int ordering;
 251         Action *action;
 252
 253         /* Id of point of transfere from Error action table to transtions and
 254          * eofActionTable. */
 255         int transferPoint;
 256
 257         int getKey() const { return ordering; }
 258 };
 259
 260 struct ErrActionTable
 261         : public SBstTable< ErrActionTableEl, int, CmpOrd<int> >
 262 {
 263         void setAction( int ordering, Action *action, int transferPoint );
 264         void setActions( const ErrActionTable &other );
 265 };
 266
 267 /* Compare of an error action table element (key & value). */
 268 struct CmpErrActionTableEl
 269 {
 270         static int compare( const ErrActionTableEl &action1,
 271                         const ErrActionTableEl &action2 )
 272         {
 273                 if ( action1.ordering < action2.ordering )
 274                         return -1;
 275                 else if ( action1.ordering > action2.ordering )
 276                         return 1;
 277                 else if ( action1.action < action2.action )
 278                         return -1;
 279                 else if ( action1.action > action2.action )
 280                         return 1;
 281                 else if ( action1.transferPoint < action2.transferPoint )
 282                         return -1;
 283                 else if ( action1.transferPoint > action2.transferPoint )
 284                         return 1;
 285                 return 0;
 286         }
 287 };
 288
 289 /* Compare for ErrActionTable. */
 290 typedef CmpSTable< ErrActionTableEl, CmpErrActionTableEl > CmpErrActionTable;
 291
 292
 293 /* Descibe a priority, shared among PriorEls.
 294  * Has key and whether or not used. */
 295 struct PriorDesc
 296 {
 297         int key;
 298         int priority;
 299 };
 300
 301 /* Element in the arrays of priorities for transitions and arrays. Ordering is
 302  * unique among instantiations of machines, desc is shared. */
 303 struct PriorEl
 304 {
 305         PriorEl( int ordering, PriorDesc *desc )
 306                 : ordering(ordering), desc(desc) { }
 307
 308         int ordering;
 309         PriorDesc *desc;
 310 };
 311
 312 /* Compare priority elements, which are ordered by the priority descriptor
 313  * key. */
 314 struct PriorElCmp
 315 {
 316         static inline int compare( const PriorEl &pel1, const PriorEl &pel2 )
 317         {
 318                 if ( pel1.desc->key < pel2.desc->key )
 319                         return -1;
 320                 else if ( pel1.desc->key > pel2.desc->key )
 321                         return 1;
 322                 else
 323                         return 0;
 324         }
 325 };
 326
 327
 328 /* Priority Table. */
 329 struct PriorTable
 330         : public SBstSet< PriorEl, PriorElCmp >
 331 {
 332         void setPrior( int ordering, PriorDesc *desc );
 333         void setPriors( const PriorTable &other );
 334 };
 335
 336 /* Compare of prior table elements for distinguising state data. */
 337 struct CmpPriorEl
 338 {
 339         static inline int compare( const PriorEl &pel1, const PriorEl &pel2 )
 340         {
 341                 if ( pel1.desc < pel2.desc )
 342                         return -1;
 343                 else if ( pel1.desc > pel2.desc )
 344                         return 1;
 345                 else if ( pel1.ordering < pel2.ordering )
 346                         return -1;
 347                 else if ( pel1.ordering > pel2.ordering )
 348                         return 1;
 349                 return 0;
 350         }
 351 };
 352
 353 /* Compare of PriorTable distinguising state data. Using a compare of the
 354  * pointers is a little more strict than it needs be. It requires that
 355  * prioritiy tables have the exact same set of priority assignment operators
 356  * (from the input lang) to be considered equal.
 357  *
 358  * Really only key-value pairs need be tested and ordering be merged. However
 359  * this would require that in the fuseing of states, priority descriptors be
 360  * chosen for the new fused state based on priority. Since the out transition
 361  * lists and ranges aren't necessarily going to line up, this is more work for
 362  * little gain. Final compression resets all priorities first, so this would
 363  * only be useful for compression at every operator, which is only an
 364  * undocumented test feature.
 365  */
 366 typedef CmpSTable<PriorEl, CmpPriorEl> CmpPriorTable;
 367
 368 /* Plain action list that imposes no ordering. */
 369 typedef Vector<int> TransFuncList;
 370
 371 /* Comparison for TransFuncList. */
 372 typedef CmpTable< int, CmpOrd<int> > TransFuncListCompare;
 373
 374 /* Transition class that implements actions and priorities. */
 375 struct TransAp
 376 {
 377         TransAp() : fromState(0), toState(0) {}
 378         TransAp( const TransAp &other ) :
 379                 lowKey(other.lowKey),
 380                 highKey(other.highKey),
 381                 fromState(0), toState(0),
 382                 actionTable(other.actionTable),
 383                 priorTable(other.priorTable)
 384         {
 385                 assert( lmActionTable.length() == 0 && other.lmActionTable.length() == 0 );
 386         }
 387
 388         Key lowKey, highKey;
 389         StateAp *fromState;
 390         StateAp *toState;
 391
 392         /* Pointers for outlist. */
 393         TransAp *prev, *next;
 394
 395         /* Pointers for in-list. */
 396         TransAp *ilprev, *ilnext;
 397
 398         /* The function table and priority for the transition. */
 399         ActionTable actionTable;
 400         PriorTable priorTable;
 401
 402         LmActionTable lmActionTable;
 403 };
 404
 405 /* In transition list. Like DList except only has head pointers, which is all
 406  * that is required. Insertion and deletion is handled by the graph. This
 407  * class provides the iterator of a single list. */
 408 struct TransInList
 409 {
 410         TransInList() : head(0) { }
 411
 412         TransAp *head;
 413
 414         struct Iter
 415         {
 416                 /* Default construct. */
 417                 Iter() : ptr(0) { }
 418
 419                 /* Construct, assign from a list. */
 420                 Iter( const TransInList &il )  : ptr(il.head) { }
 421                 Iter &operator=( const TransInList &dl ) { ptr = dl.head; return *this; }
 422
 423                 /* At the end */
 424                 bool lte() const    { return ptr != 0; }
 425                 bool end() const    { return ptr == 0; }
 426
 427                 /* At the first, last element. */
 428                 bool first() const { return ptr && ptr->ilprev == 0; }
 429                 bool last() const  { return ptr && ptr->ilnext == 0; }
 430
 431                 /* Cast, dereference, arrow ops. */
 432                 operator TransAp*() const   { return ptr; }
 433                 TransAp &operator *() const { return *ptr; }
 434                 TransAp *operator->() const { return ptr; }
 435
 436                 /* Increment, decrement. */
 437                 inline void operator++(int)   { ptr = ptr->ilnext; }
 438                 inline void operator--(int)   { ptr = ptr->ilprev; }
 439
 440                 /* The iterator is simply a pointer. */
 441                 TransAp *ptr;
 442         };
 443 };
 444
 445 typedef DList<TransAp> TransList;
 446
 447 /* Set of states, list of states. */
 448 typedef BstSet<StateAp*> StateSet;
 449 typedef DList<StateAp> StateList;
 450
 451 /* A element in a state dict. */
 452 struct StateDictEl
 453 :
 454         public AvlTreeEl<StateDictEl>
 455 {
 456         StateDictEl(const StateSet &stateSet)
 457                 : stateSet(stateSet) { }
 458
 459         const StateSet &getKey() { return stateSet; }
 460         StateSet stateSet;
 461         StateAp *targState;
 462 };
 463
 464 /* Dictionary mapping a set of states to a target state. */
 465 typedef AvlTree< StateDictEl, StateSet, CmpTable<StateAp*> > StateDict;
 466
 467 /* Data needed for a merge operation. */
 468 struct MergeData
 469 {
 470         MergeData()
 471                 : stfillHead(0), stfillTail(0) { }
 472
 473         StateDict stateDict;
 474
 475         StateAp *stfillHead;
 476         StateAp *stfillTail;
 477
 478         void fillListAppend( StateAp *state );
 479 };
 480
 481 struct TransEl
 482 {
 483         /* Constructors. */
 484         TransEl() { }
 485         TransEl( Key lowKey, Key highKey )
 486                 : lowKey(lowKey), highKey(highKey) { }
 487         TransEl( Key lowKey, Key highKey, TransAp *value )
 488                 : lowKey(lowKey), highKey(highKey), value(value) { }
 489
 490         Key lowKey, highKey;
 491         TransAp *value;
 492 };
 493
 494 struct CmpKey
 495 {
 496         static int compare( const Key key1, const Key key2 )
 497         {
 498                 if ( key1 < key2 )
 499                         return -1;
 500                 else if ( key1 > key2 )
 501                         return 1;
 502                 else
 503                         return 0;
 504         }
 505 };
 506
 507 /* Vector based set of key items. */
 508 typedef BstSet<Key, CmpKey> KeySet;
 509
 510 struct MinPartition
 511 {
 512         MinPartition() : active(false) { }
 513
 514         StateList list;
 515         bool active;
 516
 517         MinPartition *prev, *next;
 518 };
 519
 520 /* Epsilon transition stored in a state. Specifies the target */
 521 typedef Vector<int> EpsilonTrans;
 522
 523 /* List of states that are to be drawn into this. */
 524 struct EptVectEl
 525 {
 526         EptVectEl( StateAp *targ, bool leaving )
 527                 : targ(targ), leaving(leaving) { }
 528
 529         StateAp *targ;
 530         bool leaving;
 531 };
 532 typedef Vector<EptVectEl> EptVect;
 533
 534 /* Set of entry ids that go into this state. */
 535 typedef BstSet<int> EntryIdSet;
 536
 537 /* Set of longest match items that may be active in a given state. */
 538 typedef BstSet<LongestMatchPart*> LmItemSet;
 539
 540 /* A Conditions which is to be
 541  * transfered on pending out transitions. */
 542 struct OutCond
 543 {
 544         OutCond( Action *action, bool sense )
 545                 : action(action), sense(sense) {}
 546
 547         Action *action;
 548         bool sense;
 549 };
 550
 551 struct CmpOutCond
 552 {
 553         static int compare( const OutCond &outCond1, const OutCond &outCond2 )
 554         {
 555                 if ( outCond1.action < outCond2.action )
 556                         return -1;
 557                 else if ( outCond1.action > outCond2.action )
 558                         return 1;
 559                 else if ( outCond1.sense < outCond2.sense )
 560                         return -1;
 561                 else if ( outCond1.sense > outCond2.sense )
 562                         return 1;
 563                 return 0;
 564         }
 565 };
 566
 567 /* Set of conditions to be transfered to on pending out transitions. */
 568 typedef SBstSet< OutCond, CmpOutCond > OutCondSet;
 569 typedef CmpSTable< OutCond, CmpOutCond > CmpOutCondSet;
 570
 571 /* Conditions. */
 572 typedef BstSet< Action*, CmpCondId > CondSet;
 573 typedef CmpTable< Action*, CmpCondId > CmpCondSet;
 574
 575 struct CondSpace
 576         : public AvlTreeEl<CondSpace>
 577 {
 578         CondSpace( const CondSet &condSet )
 579                 : condSet(condSet) {}
 580
 581         const CondSet &getKey() { return condSet; }
 582
 583         CondSet condSet;
 584         Key baseKey;
 585         long condSpaceId;
 586 };
 587
 588 typedef Vector<CondSpace*> CondSpaceVect;
 589
 590 typedef AvlTree<CondSpace, CondSet, CmpCondSet> CondSpaceMap;
 591
 592 struct StateCond
 593 {
 594         StateCond( Key lowKey, Key highKey ) :
 595                 lowKey(lowKey), highKey(highKey) {}
 596
 597         Key lowKey;
 598         Key highKey;
 599         CondSpace *condSpace;
 600
 601         StateCond *prev, *next;
 602 };
 603
 604 typedef DList<StateCond> StateCondList;
 605 typedef Vector<long> LongVect;
 606
 607 struct Expansion
 608 {
 609         Expansion( Key lowKey, Key highKey ) :
 610                 lowKey(lowKey), highKey(highKey),
 611                 fromTrans(0), fromCondSpace(0),
 612                 toCondSpace(0) {}
 613
 614         ~Expansion()
 615         {
 616                 if ( fromTrans != 0 )
 617                         delete fromTrans;
 618         }
 619
 620         Key lowKey;
 621         Key highKey;
 622
 623         TransAp *fromTrans;
 624         CondSpace *fromCondSpace;
 625         long fromVals;
 626
 627         CondSpace *toCondSpace;
 628         LongVect toValsList;
 629
 630         Expansion *prev, *next;
 631 };
 632
 633 typedef DList<Expansion> ExpansionList;
 634
 635 struct Removal
 636 {
 637         Key lowKey;
 638         Key highKey;
 639
 640         Removal *next;
 641 };
 642
 643 struct CondData
 644 {
 645         CondData() : lastCondKey(0) {}
 646
 647         /* Condition info. */
 648         Key lastCondKey;
 649
 650         CondSpaceMap condSpaceMap;
 651 };
 652
 653 extern CondData *condData;
 654
 655 struct FsmConstructFail
 656 {
 657         enum Reason
 658         {
 659                 CondNoKeySpace
 660         };
 661
 662         FsmConstructFail( Reason reason )
 663                 : reason(reason) {}
 664         Reason reason;
 665 };
 666
 667 /* State class that implements actions and priorities. */
 668 struct StateAp
 669 {
 670         StateAp();
 671         StateAp(const StateAp &other);
 672         ~StateAp();
 673
 674         /* Is the state final? */
 675         bool isFinState() { return stateBits & SB_ISFINAL; }
 676
 677         /* Out transition list and the pointer for the default out trans. */
 678         TransList outList;
 679
 680         /* In transition Lists. */
 681         TransInList inList;
 682
 683         /* Entry points into the state. */
 684         EntryIdSet entryIds;
 685
 686         /* Epsilon transitions. */
 687         EpsilonTrans epsilonTrans;
 688
 689         /* Condition info. */
 690         StateCondList stateCondList;
 691
 692         /* Number of in transitions from states other than ourselves. */
 693         int foreignInTrans;
 694
 695         /* Temporary data for various algorithms. */
 696         union {
 697                 /* When duplicating the fsm we need to map each
 698                  * state to the new state representing it. */
 699                 StateAp *stateMap;
 700
 701                 /* When minimizing machines by partitioning, this maps to the group
 702                  * the state is in. */
 703                 MinPartition *partition;
 704
 705                 /* When merging states (state machine operations) this next pointer is
 706                  * used for the list of states that need to be filled in. */
 707                 StateAp *next;
 708
 709                 /* Identification for printing and stable minimization. */
 710                 int stateNum;
 711
 712         } alg;
 713
 714         /* Data used in epsilon operation, maybe fit into alg? */
 715         StateAp *isolatedShadow;
 716         int owningGraph;
 717
 718         /* A pointer to a dict element that contains the set of states this state
 719          * represents. This cannot go into alg, because alg.next is used during
 720          * the merging process. */
 721         StateDictEl *stateDictEl;
 722
 723         /* When drawing epsilon transitions, holds the list of states to merge
 724          * with. */
 725         EptVect *eptVect;
 726
 727         /* Bits controlling the behaviour of the state during collapsing to dfa. */
 728         int stateBits;
 729
 730         /* State list elements. */
 731         StateAp *next, *prev;
 732
 733         /*
 734          * Priority and Action data.
 735          */
 736
 737         /* Out priorities transfered to out transitions. */
 738         PriorTable outPriorTable;
 739
 740         /* The following two action tables are distinguished by the fact that when
 741          * toState actions are executed immediatly after transition actions of
 742          * incoming transitions and the current character will be the same as the
 743          * one available then. The fromState actions are executed immediately
 744          * before the transition actions of outgoing transitions and the current
 745          * character is same as the one available then. */
 746
 747         /* Actions to execute upon entering into a state. */
 748         ActionTable toStateActionTable;
 749
 750         /* Actions to execute when going from the state to the transition. */
 751         ActionTable fromStateActionTable;
 752
 753         /* Actions to add to any future transitions that leave via this state. */
 754         ActionTable outActionTable;
 755
 756         /* Conditions to add to any future transiions that leave via this sttate. */
 757         OutCondSet outCondSet;
 758
 759         /* Error action tables. */
 760         ErrActionTable errActionTable;
 761
 762         /* Actions to execute on eof. */
 763         ActionTable eofActionTable;
 764
 765         /* Set of longest match items that may be active in this state. */
 766         LmItemSet lmItemSet;
 767 };
 768
 769 template <class ListItem> struct NextTrans
 770 {
 771         Key lowKey, highKey;
 772         ListItem *trans;
 773         ListItem *next;
 774
 775         void load() {
 776                 if ( trans == 0 )
 777                         next = 0;
 778                 else {
 779                         next = trans->next;
 780                         lowKey = trans->lowKey;
 781                         highKey = trans->highKey;
 782                 }
 783         }
 784
 785         void set( ListItem *t ) {
 786                 trans = t;
 787                 load();
 788         }
 789
 790         void increment() {
 791                 trans = next;
 792                 load();
 793         }
 794 };
 795
 796
 797 /* Encodes the different states that are meaningful to the of the iterator. */
 798 enum PairIterUserState
 799 {
 800         RangeInS1, RangeInS2,
 801         RangeOverlap,
 802         BreakS1, BreakS2
 803 };
 804
 805 template <class ListItem1, class ListItem2 = ListItem1> struct PairIter
 806 {
 807         /* Encodes the different states that an fsm iterator can be in. */
 808         enum IterState {
 809                 Begin,
 810                 ConsumeS1Range, ConsumeS2Range,
 811                 OnlyInS1Range,  OnlyInS2Range,
 812                 S1SticksOut,    S1SticksOutBreak,
 813                 S2SticksOut,    S2SticksOutBreak,
 814                 S1DragsBehind,  S1DragsBehindBreak,
 815                 S2DragsBehind,  S2DragsBehindBreak,
 816                 ExactOverlap,   End
 817         };
 818
 819         PairIter( ListItem1 *list1, ListItem2 *list2 );
 820
 821         /* Query iterator. */
 822         bool lte() { return itState != End; }
 823         bool end() { return itState == End; }
 824         void operator++(int) { findNext(); }
 825         void operator++()    { findNext(); }
 826
 827         /* Iterator state. */
 828         ListItem1 *list1;
 829         ListItem2 *list2;
 830         IterState itState;
 831         PairIterUserState userState;
 832
 833         NextTrans<ListItem1> s1Tel;
 834         NextTrans<ListItem2> s2Tel;
 835         Key bottomLow, bottomHigh;
 836         ListItem1 *bottomTrans1;
 837         ListItem2 *bottomTrans2;
 838
 839 private:
 840         void findNext();
 841 };
 842
 843 /* Init the iterator by advancing to the first item. */
 844 template <class ListItem1, class ListItem2> PairIter<ListItem1, ListItem2>::PairIter(
 845                 ListItem1 *list1, ListItem2 *list2 )
 846 :
 847         list1(list1),
 848         list2(list2),
 849         itState(Begin)
 850 {
 851         findNext();
 852 }
 853
 854 /* Return and re-entry for the co-routine iterators. This should ALWAYS be
 855  * used inside of a block. */
 856 #define CO_RETURN(label) \
 857         itState = label; \
 858         return; \
 859         entry##label: backIn = true
 860
 861 /* Return and re-entry for the co-routine iterators. This should ALWAYS be
 862  * used inside of a block. */
 863 #define CO_RETURN2(label, uState) \
 864         itState = label; \
 865         userState = uState; \
 866         return; \
 867         entry##label: backIn = true
 868
 869 /* Advance to the next transition. When returns, trans points to the next
 870  * transition, unless there are no more, in which case end() returns true. */
 871 template <class ListItem1, class ListItem2> void PairIter<ListItem1, ListItem2>::findNext()
 872 {
 873         /* This variable is used in dummy statements that follow the entry
 874          * goto labels. The compiler needs some statement to follow the label. */
 875         bool backIn;
 876
 877         /* Jump into the iterator routine base on the iterator state. */
 878         switch ( itState ) {
 879                 case Begin:              goto entryBegin;
 880                 case ConsumeS1Range:     goto entryConsumeS1Range;
 881                 case ConsumeS2Range:     goto entryConsumeS2Range;
 882                 case OnlyInS1Range:      goto entryOnlyInS1Range;
 883                 case OnlyInS2Range:      goto entryOnlyInS2Range;
 884                 case S1SticksOut:        goto entryS1SticksOut;
 885                 case S1SticksOutBreak:   goto entryS1SticksOutBreak;
 886                 case S2SticksOut:        goto entryS2SticksOut;
 887                 case S2SticksOutBreak:   goto entryS2SticksOutBreak;
 888                 case S1DragsBehind:      goto entryS1DragsBehind;
 889                 case S1DragsBehindBreak: goto entryS1DragsBehindBreak;
 890                 case S2DragsBehind:      goto entryS2DragsBehind;
 891                 case S2DragsBehindBreak: goto entryS2DragsBehindBreak;
 892                 case ExactOverlap:       goto entryExactOverlap;
 893                 case End:                goto entryEnd;
 894         }
 895
 896 entryBegin:
 897         /* Set up the next structs at the head of the transition lists. */
 898         s1Tel.set( list1 );
 899         s2Tel.set( list2 );
 900
 901         /* Concurrently scan both out ranges. */
 902         while ( true ) {
 903                 if ( s1Tel.trans == 0 ) {
 904                         /* We are at the end of state1's ranges. Process the rest of
 905                          * state2's ranges. */
 906                         while ( s2Tel.trans != 0 ) {
 907                                 /* Range is only in s2. */
 908                                 CO_RETURN2( ConsumeS2Range, RangeInS2 );
 909                                 s2Tel.increment();
 910                         }
 911                         break;
 912                 }
 913                 else if ( s2Tel.trans == 0 ) {
 914                         /* We are at the end of state2's ranges. Process the rest of
 915                          * state1's ranges. */
 916                         while ( s1Tel.trans != 0 ) {
 917                                 /* Range is only in s1. */
 918                                 CO_RETURN2( ConsumeS1Range, RangeInS1 );
 919                                 s1Tel.increment();
 920                         }
 921                         break;
 922                 }
 923                 /* Both state1's and state2's transition elements are good.
 924                  * The signiture of no overlap is a back key being in front of a
 925                  * front key. */
 926                 else if ( s1Tel.highKey < s2Tel.lowKey ) {
 927                         /* A range exists in state1 that does not overlap with state2. */
 928                         CO_RETURN2( OnlyInS1Range, RangeInS1 );
 929                         s1Tel.increment();
 930                 }
 931                 else if ( s2Tel.highKey < s1Tel.lowKey ) {
 932                         /* A range exists in state2 that does not overlap with state1. */
 933                         CO_RETURN2( OnlyInS2Range, RangeInS2 );
 934                         s2Tel.increment();
 935                 }
 936                 /* There is overlap, must mix the ranges in some way. */
 937                 else if ( s1Tel.lowKey < s2Tel.lowKey ) {
 938                         /* Range from state1 sticks out front. Must break it into
 939                          * non-overlaping and overlaping segments. */
 940                         bottomLow = s2Tel.lowKey;
 941                         bottomHigh = s1Tel.highKey;
 942                         s1Tel.highKey = s2Tel.lowKey;
 943                         s1Tel.highKey.decrement();
 944                         bottomTrans1 = s1Tel.trans;
 945
 946                         /* Notify the caller that we are breaking s1. This gives them a
 947                          * chance to duplicate s1Tel[0,1].value. */
 948                         CO_RETURN2( S1SticksOutBreak, BreakS1 );
 949
 950                         /* Broken off range is only in s1. */
 951                         CO_RETURN2( S1SticksOut, RangeInS1 );
 952
 953                         /* Advance over the part sticking out front. */
 954                         s1Tel.lowKey = bottomLow;
 955                         s1Tel.highKey = bottomHigh;
 956                         s1Tel.trans = bottomTrans1;
 957                 }
 958                 else if ( s2Tel.lowKey < s1Tel.lowKey ) {
 959                         /* Range from state2 sticks out front. Must break it into
 960                          * non-overlaping and overlaping segments. */
 961                         bottomLow = s1Tel.lowKey;
 962                         bottomHigh = s2Tel.highKey;
 963                         s2Tel.highKey = s1Tel.lowKey;
 964                         s2Tel.highKey.decrement();
 965                         bottomTrans2 = s2Tel.trans;
 966
 967                         /* Notify the caller that we are breaking s2. This gives them a
 968                          * chance to duplicate s2Tel[0,1].value. */
 969                         CO_RETURN2( S2SticksOutBreak, BreakS2 );
 970
 971                         /* Broken off range is only in s2. */
 972                         CO_RETURN2( S2SticksOut, RangeInS2 );
 973
 974                         /* Advance over the part sticking out front. */
 975                         s2Tel.lowKey = bottomLow;
 976                         s2Tel.highKey = bottomHigh;
 977                         s2Tel.trans = bottomTrans2;
 978                 }
 979                 /* Low ends are even. Are the high ends even? */
 980                 else if ( s1Tel.highKey < s2Tel.highKey ) {
 981                         /* Range from state2 goes longer than the range from state1. We
 982                          * must break the range from state2 into an evenly overlaping
 983                          * segment. */
 984                         bottomLow = s1Tel.highKey;
 985                         bottomLow.increment();
 986                         bottomHigh = s2Tel.highKey;
 987                         s2Tel.highKey = s1Tel.highKey;
 988                         bottomTrans2 = s2Tel.trans;
 989
 990                         /* Notify the caller that we are breaking s2. This gives them a
 991                          * chance to duplicate s2Tel[0,1].value. */
 992                         CO_RETURN2( S2DragsBehindBreak, BreakS2 );
 993
 994                         /* Breaking s2 produces exact overlap. */
 995                         CO_RETURN2( S2DragsBehind, RangeOverlap );
 996
 997                         /* Advance over the front we just broke off of range 2. */
 998                         s2Tel.lowKey = bottomLow;
 999                         s2Tel.highKey = bottomHigh;
1000                         s2Tel.trans = bottomTrans2;
1001
1002                         /* Advance over the entire s1Tel. We have consumed it. */
1003                         s1Tel.increment();
1004                 }
1005                 else if ( s2Tel.highKey < s1Tel.highKey ) {
1006                         /* Range from state1 goes longer than the range from state2. We
1007                          * must break the range from state1 into an evenly overlaping
1008                          * segment. */
1009                         bottomLow = s2Tel.highKey;
1010                         bottomLow.increment();
1011                         bottomHigh = s1Tel.highKey;
1012                         s1Tel.highKey = s2Tel.highKey;
1013                         bottomTrans1 = s1Tel.trans;
1014
1015                         /* Notify the caller that we are breaking s1. This gives them a
1016                          * chance to duplicate s2Tel[0,1].value. */
1017                         CO_RETURN2( S1DragsBehindBreak, BreakS1 );
1018
1019                         /* Breaking s1 produces exact overlap. */
1020                         CO_RETURN2( S1DragsBehind, RangeOverlap );
1021
1022                         /* Advance over the front we just broke off of range 1. */
1023                         s1Tel.lowKey = bottomLow;
1024                         s1Tel.highKey = bottomHigh;
1025                         s1Tel.trans = bottomTrans1;
1026
1027                         /* Advance over the entire s2Tel. We have consumed it. */
1028                         s2Tel.increment();
1029                 }
1030                 else {
1031                         /* There is an exact overlap. */
1032                         CO_RETURN2( ExactOverlap, RangeOverlap );
1033
1034                         s1Tel.increment();
1035                         s2Tel.increment();
1036                 }
1037         }
1038
1039         /* Done, go into end state. */
1040         CO_RETURN( End );
1041 }
1042
1043
1044 /* Compare lists of epsilon transitions. Entries are name ids of targets. */
1045 typedef CmpTable< int, CmpOrd<int> > CmpEpsilonTrans;
1046
1047 /* Compare class for the Approximate minimization. */
1048 class ApproxCompare
1049 {
1050 public:
1051         ApproxCompare() { }
1052         int compare( const StateAp *pState1, const StateAp *pState2 );
1053 };
1054
1055 /* Compare class for the initial partitioning of a partition minimization. */
1056 class InitPartitionCompare
1057 {
1058 public:
1059         InitPartitionCompare() { }
1060         int compare( const StateAp *pState1, const StateAp *pState2 );
1061 };
1062
1063 /* Compare class for the regular partitioning of a partition minimization. */
1064 class PartitionCompare
1065 {
1066 public:
1067         PartitionCompare() { }
1068         int compare( const StateAp *pState1, const StateAp *pState2 );
1069 };
1070
1071 /* Compare class for a minimization that marks pairs. Provides the shouldMark
1072  * routine. */
1073 class MarkCompare
1074 {
1075 public:
1076         MarkCompare() { }
1077         bool shouldMark( MarkIndex &markIndex, const StateAp *pState1,
1078                         const StateAp *pState2 );
1079 };
1080
1081 /* List of partitions. */
1082 typedef DList< MinPartition > PartitionList;
1083
1084 /* List of transtions out of a state. */
1085 typedef Vector<TransEl> TransListVect;
1086
1087 /* Entry point map used for keeping track of entry points in a machine. */
1088 typedef BstSet< int > EntryIdSet;
1089 typedef BstMapEl< int, StateAp* > EntryMapEl;
1090 typedef BstMap< int, StateAp* > EntryMap;
1091 typedef Vector<EntryMapEl> EntryMapBase;
1092
1093 /* Graph class that implements actions and priorities. */
1094 struct FsmAp
1095 {
1096         /* Constructors/Destructors. */
1097         FsmAp( );
1098         FsmAp( const FsmAp &graph );
1099         ~FsmAp();
1100
1101         /* The list of states. */
1102         StateList stateList;
1103         StateList misfitList;
1104
1105         /* The map of entry points. */
1106         EntryMap entryPoints;
1107
1108         /* The start state. */
1109         StateAp *startState;
1110
1111         /* Error state, possibly created only when the final machine has been
1112          * created and the XML machine is about to be written. No transitions
1113          * point to this state. */
1114         StateAp *errState;
1115
1116         /* The set of final states. */
1117         StateSet finStateSet;
1118
1119         /* Misfit Accounting. Are misfits put on a separate list. */
1120         bool misfitAccounting;
1121
1122         /*
1123          * Transition actions and priorities.
1124          */
1125
1126         /* Set priorities on transtions. */
1127         void startFsmPrior( int ordering, PriorDesc *prior );
1128         void allTransPrior( int ordering, PriorDesc *prior );
1129         void finishFsmPrior( int ordering, PriorDesc *prior );
1130         void leaveFsmPrior( int ordering, PriorDesc *prior );
1131
1132         /* Action setting support. */
1133         void transferErrorActions( StateAp *state, int transferPoint );
1134         void setErrorAction( StateAp *state, int ordering, Action *action );
1135
1136         /* Fill all spaces in a transition list with an error transition. */
1137         void fillGaps( StateAp *state );
1138
1139         /* Similar to setErrorAction, instead gives a state to go to on error. */
1140         void setErrorTarget( StateAp *state, StateAp *target, int *orderings,
1141                         Action **actions, int nActs );
1142
1143         /* Set actions to execute. */
1144         void startFsmAction( int ordering, Action *action );
1145         void allTransAction( int ordering, Action *action );
1146         void finishFsmAction( int ordering, Action *action );
1147         void leaveFsmAction( int ordering, Action *action );
1148         void longMatchAction( int ordering, LongestMatchPart *lmPart );
1149
1150         /* Set conditions. */
1151         CondSpace *addCondSpace( const CondSet &condSet );
1152
1153         void findEmbedExpansions( ExpansionList &expansionList,
1154                 StateAp *destState, Action *condAction, bool sense );
1155         void embedCondition( MergeData &md, StateAp *state, Action *condAction, bool sense );
1156         void embedCondition( StateAp *state, Action *condAction, bool sense );
1157
1158         void startFsmCondition( Action *condAction, bool sense );
1159         void allTransCondition( Action *condAction, bool sense );
1160         void leaveFsmCondition( Action *condAction, bool sense );
1161
1162         /* Set error actions to execute. */
1163         void startErrorAction( int ordering, Action *action, int transferPoint );
1164         void allErrorAction( int ordering, Action *action, int transferPoint );
1165         void finalErrorAction( int ordering, Action *action, int transferPoint );
1166         void notStartErrorAction( int ordering, Action *action, int transferPoint );
1167         void notFinalErrorAction( int ordering, Action *action, int transferPoint );
1168         void middleErrorAction( int ordering, Action *action, int transferPoint );
1169
1170         /* Set EOF actions. */
1171         void startEOFAction( int ordering, Action *action );
1172         void allEOFAction( int ordering, Action *action );
1173         void finalEOFAction( int ordering, Action *action );
1174         void notStartEOFAction( int ordering, Action *action );
1175         void notFinalEOFAction( int ordering, Action *action );
1176         void middleEOFAction( int ordering, Action *action );
1177
1178         /* Set To State actions. */
1179         void startToStateAction( int ordering, Action *action );
1180         void allToStateAction( int ordering, Action *action );
1181         void finalToStateAction( int ordering, Action *action );
1182         void notStartToStateAction( int ordering, Action *action );
1183         void notFinalToStateAction( int ordering, Action *action );
1184         void middleToStateAction( int ordering, Action *action );
1185
1186         /* Set From State actions. */
1187         void startFromStateAction( int ordering, Action *action );
1188         void allFromStateAction( int ordering, Action *action );
1189         void finalFromStateAction( int ordering, Action *action );
1190         void notStartFromStateAction( int ordering, Action *action );
1191         void notFinalFromStateAction( int ordering, Action *action );
1192         void middleFromStateAction( int ordering, Action *action );
1193
1194         /* Shift the action ordering of the start transitions to start at
1195          * fromOrder and increase in units of 1. Useful before kleene star
1196          * operation.  */
1197         int shiftStartActionOrder( int fromOrder );
1198
1199         /* Clear all priorities from the fsm to so they won't affcet minimization
1200          * of the final fsm. */
1201         void clearAllPriorities();
1202
1203         /* Zero out all the function keys. */
1204         void nullActionKeys();
1205
1206         /* Walk the list of states and verify state properties. */
1207         void verifyStates();
1208
1209         /* Misfit Accounting. Are misfits put on a separate list. */
1210         void setMisfitAccounting( bool val )
1211                 { misfitAccounting = val; }
1212
1213         /* Set and Unset a state as final. */
1214         void setFinState( StateAp *state );
1215         void unsetFinState( StateAp *state );
1216
1217         void setStartState( StateAp *state );
1218         void unsetStartState( );
1219
1220         /* Set and unset a state as an entry point. */
1221         void setEntry( int id, StateAp *state );
1222         void changeEntry( int id, StateAp *to, StateAp *from );
1223         void unsetEntry( int id, StateAp *state );
1224         void unsetEntry( int id );
1225         void unsetAllEntryPoints();
1226
1227         /* Epsilon transitions. */
1228         void epsilonTrans( int id );
1229         void shadowReadWriteStates( MergeData &md );
1230
1231         /*
1232          * Basic attaching and detaching.
1233          */
1234
1235         /* Common to attaching/detaching list and default. */
1236         void attachToInList( StateAp *from, StateAp *to, TransAp *&head, TransAp *trans );
1237         void detachFromInList( StateAp *from, StateAp *to, TransAp *&head, TransAp *trans );
1238
1239         /* Attach with a new transition. */
1240         TransAp *attachNewTrans( StateAp *from, StateAp *to,
1241                         Key onChar1, Key onChar2 );
1242
1243         /* Attach with an existing transition that already in an out list. */
1244         void attachTrans( StateAp *from, StateAp *to, TransAp *trans );
1245
1246         /* Redirect a transition away from error and towards some state. */
1247         void redirectErrorTrans( StateAp *from, StateAp *to, TransAp *trans );
1248
1249         /* Detach a transition from a target state. */
1250         void detachTrans( StateAp *from, StateAp *to, TransAp *trans );
1251
1252         /* Detach a state from the graph. */
1253         void detachState( StateAp *state );
1254
1255         /*
1256          * NFA to DFA conversion routines.
1257          */
1258
1259         /* Duplicate a transition that will dropin to a free spot. */
1260         TransAp *dupTrans( StateAp *from, TransAp *srcTrans );
1261
1262         /* In crossing, two transitions both go to real states. */
1263         TransAp *fsmAttachStates( MergeData &md, StateAp *from,
1264                         TransAp *destTrans, TransAp *srcTrans );
1265
1266         /* Two transitions are to be crossed, handle the possibility of either
1267          * going to the error state. */
1268         TransAp *mergeTrans( MergeData &md, StateAp *from,
1269                         TransAp *destTrans, TransAp *srcTrans );
1270
1271         /* Compare deterimne relative priorities of two transition tables. */
1272         int comparePrior( const PriorTable &priorTable1, const PriorTable &priorTable2 );
1273
1274         /* Cross a src transition with one that is already occupying a spot. */
1275         TransAp *crossTransitions( MergeData &md, StateAp *from,
1276                         TransAp *destTrans, TransAp *srcTrans );
1277
1278         void outTransCopy( MergeData &md, StateAp *dest, TransAp *srcList );
1279
1280         void doRemove( MergeData &md, StateAp *destState, ExpansionList &expList1 );
1281         void doExpand( MergeData &md, StateAp *destState, ExpansionList &expList1 );
1282         void findCondExpInTrans( ExpansionList &expansionList, StateAp *state,
1283                         Key lowKey, Key highKey, CondSpace *fromCondSpace, CondSpace *toCondSpace,
1284                         long destVals, LongVect &toValsList );
1285         void findTransExpansions( ExpansionList &expansionList,
1286                         StateAp *destState, StateAp *srcState );
1287         void findCondExpansions( ExpansionList &expansionList,
1288                         StateAp *destState, StateAp *srcState );
1289         void mergeStateConds( StateAp *destState, StateAp *srcState );
1290
1291         /* Merge a set of states into newState. */
1292         void mergeStates( MergeData &md, StateAp *destState,
1293                         StateAp **srcStates, int numSrc );
1294         void mergeStatesLeaving( MergeData &md, StateAp *destState, StateAp *srcState );
1295         void mergeStates( MergeData &md, StateAp *destState, StateAp *srcState );
1296
1297         /* Make all states that are combinations of other states and that
1298          * have not yet had their out transitions filled in. This will
1299          * empty out stateDict and stFil. */
1300         void fillInStates( MergeData &md );
1301
1302         /*
1303          * Transition Comparison.
1304          */
1305
1306         /* Compare transition data. Either of the pointers may be null. */
1307         static inline int compareDataPtr( TransAp *trans1, TransAp *trans2 );
1308
1309         /* Compare target state and transition data. Either pointer may be null. */
1310         static inline int compareFullPtr( TransAp *trans1, TransAp *trans2 );
1311
1312         /* Compare target partitions. Either pointer may be null. */
1313         static inline int comparePartPtr( TransAp *trans1, TransAp *trans2 );
1314
1315         /* Check marked status of target states. Either pointer may be null. */
1316         static inline bool shouldMarkPtr( MarkIndex &markIndex,
1317                         TransAp *trans1, TransAp *trans2 );
1318
1319         /*
1320          * Callbacks.
1321          */
1322
1323         /* Compare priority and function table of transitions. */
1324         static int compareTransData( TransAp *trans1, TransAp *trans2 );
1325
1326         /* Add in the properties of srcTrans into this. */
1327         void addInTrans( TransAp *destTrans, TransAp *srcTrans );
1328
1329         /* Compare states on data stored in the states. */
1330         static int compareStateData( const StateAp *state1, const StateAp *state2 );
1331
1332         /* Out transition data. */
1333         void clearOutData( StateAp *state );
1334         bool hasOutData( StateAp *state );
1335         void transferOutData( StateAp *destState, StateAp *srcState );
1336
1337         /*
1338          * Allocation.
1339          */
1340
1341         /* New up a state and add it to the graph. */
1342         StateAp *addState();
1343
1344         /*
1345          * Building basic machines
1346          */
1347
1348         void concatFsm( Key c );
1349         void concatFsm( Key *str, int len );
1350         void concatFsmCI( Key *str, int len );
1351         void orFsm( Key *set, int len );
1352         void rangeFsm( Key low, Key high );
1353         void rangeStarFsm( Key low, Key high );
1354         void emptyFsm( );
1355         void lambdaFsm( );
1356
1357         /*
1358          * Fsm operators.
1359          */
1360
1361         void starOp( );
1362         void repeatOp( int times );
1363         void optionalRepeatOp( int times );
1364         void concatOp( FsmAp *other );
1365         void unionOp( FsmAp *other );
1366         void intersectOp( FsmAp *other );
1367         void subtractOp( FsmAp *other );
1368         void epsilonOp();
1369         void joinOp( int startId, int finalId, FsmAp **others, int numOthers );
1370         void globOp( FsmAp **others, int numOthers );
1371         void deterministicEntry();
1372
1373         /*
1374          * Operator workers
1375          */
1376
1377         /* Determine if there are any entry points into a start state other than
1378          * the start state. */
1379         bool isStartStateIsolated();
1380
1381         /* Make a new start state that has no entry points. Will not change the
1382          * identity of the fsm. */
1383         void isolateStartState();
1384
1385         /* Workers for resolving epsilon transitions. */
1386         bool inEptVect( EptVect *eptVect, StateAp *targ );
1387         void epsilonFillEptVectFrom( StateAp *root, StateAp *from, bool parentLeaving );
1388         void resolveEpsilonTrans( MergeData &md );
1389
1390         /* Workers for concatenation and union. */
1391         void doConcat( FsmAp *other, StateSet *fromStates, bool optional );
1392         void doOr( FsmAp *other );
1393
1394         /*
1395          * Final states
1396          */
1397
1398         /* Unset any final states that are no longer to be final
1399          * due to final bits. */
1400         void unsetIncompleteFinals();
1401         void unsetKilledFinals();
1402
1403         /* Bring in other's entry points. Assumes others states are going to be
1404          * copied into this machine. */
1405         void copyInEntryPoints( FsmAp *other );
1406
1407         /* Ordering states. */
1408         void depthFirstOrdering( StateAp *state );
1409         void depthFirstOrdering();
1410         void sortStatesByFinal();
1411
1412         /* Set sqequential state numbers starting at 0. */
1413         void setStateNumbers( int base );
1414
1415         /* Unset all final states. */
1416         void unsetAllFinStates();
1417
1418         /* Set the bits of final states and clear the bits of non final states. */
1419         void setFinBits( int finStateBits );
1420
1421         /*
1422          * Self-consistency checks.
1423          */
1424
1425         /* Run a sanity check on the machine. */
1426         void verifyIntegrity();
1427
1428         /* Verify that there are no unreachable states, or dead end states. */
1429         void verifyReachability();
1430         void verifyNoDeadEndStates();
1431
1432         /*
1433          * Path pruning
1434          */
1435
1436         /* Mark all states reachable from state. */
1437         void markReachableFromHereReverse( StateAp *state );
1438
1439         /* Mark all states reachable from state. */
1440         void markReachableFromHere( StateAp *state );
1441         void markReachableFromHereStopFinal( StateAp *state );
1442
1443         /* Removes states that cannot be reached by any path in the fsm and are
1444          * thus wasted silicon. */
1445         void removeDeadEndStates();
1446
1447         /* Removes states that cannot be reached by any path in the fsm and are
1448          * thus wasted silicon. */
1449         void removeUnreachableStates();
1450
1451         /* Remove error actions from states on which the error transition will
1452          * never be taken. */
1453         bool outListCovers( StateAp *state );
1454         bool anyErrorRange( StateAp *state );
1455
1456         /* Remove states that are on the misfit list. */
1457         void removeMisfits();
1458
1459         /*
1460          * FSM Minimization
1461          */
1462
1463         /* Minimization by partitioning. */
1464         void minimizePartition1();
1465         void minimizePartition2();
1466
1467         /* Minimize the final state Machine. The result is the minimal fsm. Slow
1468          * but stable, correct minimization. Uses n^2 space (lookout) and average
1469          * n^2 time. Worst case n^3 time, but a that is a very rare case. */
1470         void minimizeStable();
1471
1472         /* Minimize the final state machine. Does not find the minimal fsm, but a
1473          * pretty good approximation. Does not use any extra space. Average n^2
1474          * time. Worst case n^3 time, but a that is a very rare case. */
1475         void minimizeApproximate();
1476
1477         /* This is the worker for the minimize approximate solution. It merges
1478          * states that have identical out transitions. */
1479         bool minimizeRound( );
1480
1481         /* Given an intial partioning of states, split partitions that have out trans
1482          * to differing partitions. */
1483         int partitionRound( StateAp **statePtrs, MinPartition *parts, int numParts );
1484
1485         /* Split partitions that have a transition to a previously split partition, until
1486          * there are no more partitions to split. */
1487         int splitCandidates( StateAp **statePtrs, MinPartition *parts, int numParts );
1488
1489         /* Fuse together states in the same partition. */
1490         void fusePartitions( MinPartition *parts, int numParts );
1491
1492         /* Mark pairs where out final stateness differs, out trans data differs,
1493          * trans pairs go to a marked pair or trans data differs. Should get
1494          * alot of pairs. */
1495         void initialMarkRound( MarkIndex &markIndex );
1496
1497         /* One marking round on all state pairs. Considers if trans pairs go
1498          * to a marked state only. Returns whether or not a pair was marked. */
1499         bool markRound( MarkIndex &markIndex );
1500
1501         /* Move the in trans into src into dest. */
1502         void inTransMove(StateAp *dest, StateAp *src);
1503
1504         /* Make state src and dest the same state. */
1505         void fuseEquivStates(StateAp *dest, StateAp *src);
1506
1507         /* Find any states that didn't get marked by the marking algorithm and
1508          * merge them into the primary states of their equivalence class. */
1509         void fuseUnmarkedPairs( MarkIndex &markIndex );
1510
1511         /* Merge neighboring transitions go to the same state and have the same
1512          * transitions data. */
1513         void compressTransitions();
1514
1515         /* Returns true if there is a transtion (either explicit or by a gap) to
1516          * the error state. */
1517         bool checkErrTrans( StateAp *state, TransAp *trans );
1518         bool checkErrTransFinish( StateAp *state );
1519         bool hasErrorTrans();
1520
1521         /* Check if a machine defines a single character. This is useful in
1522          * validating ranges and machines to export. */
1523         bool checkSingleCharMachine( );
1524 };
1525
1526
1527 #endif /* _FSMGRAPH_H */