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