ragel/fsmgraph.h

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