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