ragel/fsmgraph.h

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