ragel/fsmgraph.h

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