ragel-6.10.tar.gz: ragel-6.10/ragel/fsmgraph.h

"Fossies" - the Fresh Open Source Software Archive

Member "ragel-6.10/ragel/fsmgraph.h" (24 Mar 2017, 42492 Bytes) of package /linux/misc/ragel-6.10.tar.gz:

As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "fsmgraph.h" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report:

6.9_vs_6.10.

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: {} 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: {} 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 /* Jump into the iterator routine base on the iterator state. */ 877 switch ( itState ) { 878 case Begin: goto entryBegin; 879 case ConsumeS1Range: goto entryConsumeS1Range; 880 case ConsumeS2Range: goto entryConsumeS2Range; 881 case OnlyInS1Range: goto entryOnlyInS1Range; 882 case OnlyInS2Range: goto entryOnlyInS2Range; 883 case S1SticksOut: goto entryS1SticksOut; 884 case S1SticksOutBreak: goto entryS1SticksOutBreak; 885 case S2SticksOut: goto entryS2SticksOut; 886 case S2SticksOutBreak: goto entryS2SticksOutBreak; 887 case S1DragsBehind: goto entryS1DragsBehind; 888 case S1DragsBehindBreak: goto entryS1DragsBehindBreak; 889 case S2DragsBehind: goto entryS2DragsBehind; 890 case S2DragsBehindBreak: goto entryS2DragsBehindBreak; 891 case ExactOverlap: goto entryExactOverlap; 892 case End: goto entryEnd; 893 } 894 895 entryBegin: 896 /* Set up the next structs at the head of the transition lists. */ 897 s1Tel.set( list1 ); 898 s2Tel.set( list2 ); 899 900 /* Concurrently scan both out ranges. */ 901 while ( true ) { 902 if ( s1Tel.trans == 0 ) { 903 /* We are at the end of state1's ranges. Process the rest of 904 * state2's ranges. */ 905 while ( s2Tel.trans != 0 ) { 906 /* Range is only in s2. */ 907 CO_RETURN2( ConsumeS2Range, RangeInS2 ); 908 s2Tel.increment(); 909 } 910 break; 911 } 912 else if ( s2Tel.trans == 0 ) { 913 /* We are at the end of state2's ranges. Process the rest of 914 * state1's ranges. */ 915 while ( s1Tel.trans != 0 ) { 916 /* Range is only in s1. */ 917 CO_RETURN2( ConsumeS1Range, RangeInS1 ); 918 s1Tel.increment(); 919 } 920 break; 921 } 922 /* Both state1's and state2's transition elements are good. 923 * The signiture of no overlap is a back key being in front of a 924 * front key. */ 925 else if ( s1Tel.highKey < s2Tel.lowKey ) { 926 /* A range exists in state1 that does not overlap with state2. */ 927 CO_RETURN2( OnlyInS1Range, RangeInS1 ); 928 s1Tel.increment(); 929 } 930 else if ( s2Tel.highKey < s1Tel.lowKey ) { 931 /* A range exists in state2 that does not overlap with state1. */ 932 CO_RETURN2( OnlyInS2Range, RangeInS2 ); 933 s2Tel.increment(); 934 } 935 /* There is overlap, must mix the ranges in some way. */ 936 else if ( s1Tel.lowKey < s2Tel.lowKey ) { 937 /* Range from state1 sticks out front. Must break it into 938 * non-overlaping and overlaping segments. */ 939 bottomLow = s2Tel.lowKey; 940 bottomHigh = s1Tel.highKey; 941 s1Tel.highKey = s2Tel.lowKey; 942 s1Tel.highKey.decrement(); 943 bottomTrans1 = s1Tel.trans; 944 945 /* Notify the caller that we are breaking s1. This gives them a 946 * chance to duplicate s1Tel[0,1].value. */ 947 CO_RETURN2( S1SticksOutBreak, BreakS1 ); 948 949 /* Broken off range is only in s1. */ 950 CO_RETURN2( S1SticksOut, RangeInS1 ); 951 952 /* Advance over the part sticking out front. */ 953 s1Tel.lowKey = bottomLow; 954 s1Tel.highKey = bottomHigh; 955 s1Tel.trans = bottomTrans1; 956 } 957 else if ( s2Tel.lowKey < s1Tel.lowKey ) { 958 /* Range from state2 sticks out front. Must break it into 959 * non-overlaping and overlaping segments. */ 960 bottomLow = s1Tel.lowKey; 961 bottomHigh = s2Tel.highKey; 962 s2Tel.highKey = s1Tel.lowKey; 963 s2Tel.highKey.decrement(); 964 bottomTrans2 = s2Tel.trans; 965 966 /* Notify the caller that we are breaking s2. This gives them a 967 * chance to duplicate s2Tel[0,1].value. */ 968 CO_RETURN2( S2SticksOutBreak, BreakS2 ); 969 970 /* Broken off range is only in s2. */ 971 CO_RETURN2( S2SticksOut, RangeInS2 ); 972 973 /* Advance over the part sticking out front. */ 974 s2Tel.lowKey = bottomLow; 975 s2Tel.highKey = bottomHigh; 976 s2Tel.trans = bottomTrans2; 977 } 978 /* Low ends are even. Are the high ends even? */ 979 else if ( s1Tel.highKey < s2Tel.highKey ) { 980 /* Range from state2 goes longer than the range from state1. We 981 * must break the range from state2 into an evenly overlaping 982 * segment. */ 983 bottomLow = s1Tel.highKey; 984 bottomLow.increment(); 985 bottomHigh = s2Tel.highKey; 986 s2Tel.highKey = s1Tel.highKey; 987 bottomTrans2 = s2Tel.trans; 988 989 /* Notify the caller that we are breaking s2. This gives them a 990 * chance to duplicate s2Tel[0,1].value. */ 991 CO_RETURN2( S2DragsBehindBreak, BreakS2 ); 992 993 /* Breaking s2 produces exact overlap. */ 994 CO_RETURN2( S2DragsBehind, RangeOverlap ); 995 996 /* Advance over the front we just broke off of range 2. */ 997 s2Tel.lowKey = bottomLow; 998 s2Tel.highKey = bottomHigh; 999 s2Tel.trans = bottomTrans2; 1000 1001 /* Advance over the entire s1Tel. We have consumed it. */ 1002 s1Tel.increment(); 1003 } 1004 else if ( s2Tel.highKey < s1Tel.highKey ) { 1005 /* Range from state1 goes longer than the range from state2. We 1006 * must break the range from state1 into an evenly overlaping 1007 * segment. */ 1008 bottomLow = s2Tel.highKey; 1009 bottomLow.increment(); 1010 bottomHigh = s1Tel.highKey; 1011 s1Tel.highKey = s2Tel.highKey; 1012 bottomTrans1 = s1Tel.trans; 1013 1014 /* Notify the caller that we are breaking s1. This gives them a 1015 * chance to duplicate s2Tel[0,1].value. */ 1016 CO_RETURN2( S1DragsBehindBreak, BreakS1 ); 1017 1018 /* Breaking s1 produces exact overlap. */ 1019 CO_RETURN2( S1DragsBehind, RangeOverlap ); 1020 1021 /* Advance over the front we just broke off of range 1. */ 1022 s1Tel.lowKey = bottomLow; 1023 s1Tel.highKey = bottomHigh; 1024 s1Tel.trans = bottomTrans1; 1025 1026 /* Advance over the entire s2Tel. We have consumed it. */ 1027 s2Tel.increment(); 1028 } 1029 else { 1030 /* There is an exact overlap. */ 1031 CO_RETURN2( ExactOverlap, RangeOverlap ); 1032 1033 s1Tel.increment(); 1034 s2Tel.increment(); 1035 } 1036 } 1037 1038 /* Done, go into end state. */ 1039 CO_RETURN( End ); 1040 } 1041 1042 1043 /* Compare lists of epsilon transitions. Entries are name ids of targets. */ 1044 typedef CmpTable< int, CmpOrd<int> > CmpEpsilonTrans; 1045 1046 /* Compare class for the Approximate minimization. */ 1047 class ApproxCompare 1048 { 1049 public: 1050 ApproxCompare() { } 1051 int compare( const StateAp *pState1, const StateAp *pState2 ); 1052 }; 1053 1054 /* Compare class for the initial partitioning of a partition minimization. */ 1055 class InitPartitionCompare 1056 { 1057 public: 1058 InitPartitionCompare() { } 1059 int compare( const StateAp *pState1, const StateAp *pState2 ); 1060 }; 1061 1062 /* Compare class for the regular partitioning of a partition minimization. */ 1063 class PartitionCompare 1064 { 1065 public: 1066 PartitionCompare() { } 1067 int compare( const StateAp *pState1, const StateAp *pState2 ); 1068 }; 1069 1070 /* Compare class for a minimization that marks pairs. Provides the shouldMark 1071 * routine. */ 1072 class MarkCompare 1073 { 1074 public: 1075 MarkCompare() { } 1076 bool shouldMark( MarkIndex &markIndex, const StateAp *pState1, 1077 const StateAp *pState2 ); 1078 }; 1079 1080 /* List of partitions. */ 1081 typedef DList< MinPartition > PartitionList; 1082 1083 /* List of transtions out of a state. */ 1084 typedef Vector<TransEl> TransListVect; 1085 1086 /* Entry point map used for keeping track of entry points in a machine. */ 1087 typedef BstSet< int > EntryIdSet; 1088 typedef BstMapEl< int, StateAp* > EntryMapEl; 1089 typedef BstMap< int, StateAp* > EntryMap; 1090 typedef Vector<EntryMapEl> EntryMapBase; 1091 1092 /* Graph class that implements actions and priorities. */ 1093 struct FsmAp 1094 { 1095 /* Constructors/Destructors. */ 1096 FsmAp( ); 1097 FsmAp( const FsmAp &graph ); 1098 ~FsmAp(); 1099 1100 /* The list of states. */ 1101 StateList stateList; 1102 StateList misfitList; 1103 1104 /* The map of entry points. */ 1105 EntryMap entryPoints; 1106 1107 /* The start state. */ 1108 StateAp *startState; 1109 1110 /* Error state, possibly created only when the final machine has been 1111 * created and the XML machine is about to be written. No transitions 1112 * point to this state. */ 1113 StateAp *errState; 1114 1115 /* The set of final states. */ 1116 StateSet finStateSet; 1117 1118 /* Misfit Accounting. Are misfits put on a separate list. */ 1119 bool misfitAccounting; 1120 1121 /* 1122 * Transition actions and priorities. 1123 */ 1124 1125 /* Set priorities on transtions. */ 1126 void startFsmPrior( int ordering, PriorDesc *prior ); 1127 void allTransPrior( int ordering, PriorDesc *prior ); 1128 void finishFsmPrior( int ordering, PriorDesc *prior ); 1129 void leaveFsmPrior( int ordering, PriorDesc *prior ); 1130 1131 /* Action setting support. */ 1132 void transferOutActions( StateAp *state ); 1133 void transferErrorActions( StateAp *state, int transferPoint ); 1134 void setErrorActions( StateAp *state, const ActionTable &other ); 1135 void setErrorAction( StateAp *state, int ordering, Action *action ); 1136 1137 /* Fill all spaces in a transition list with an error transition. */ 1138 void fillGaps( StateAp *state ); 1139 1140 /* Similar to setErrorAction, instead gives a state to go to on error. */ 1141 void setErrorTarget( StateAp *state, StateAp *target, int *orderings, 1142 Action **actions, int nActs ); 1143 1144 /* Set actions to execute. */ 1145 void startFsmAction( int ordering, Action *action ); 1146 void allTransAction( int ordering, Action *action ); 1147 void finishFsmAction( int ordering, Action *action ); 1148 void leaveFsmAction( int ordering, Action *action ); 1149 void longMatchAction( int ordering, LongestMatchPart *lmPart ); 1150 1151 /* Set conditions. */ 1152 CondSpace *addCondSpace( const CondSet &condSet ); 1153 1154 void findEmbedExpansions( ExpansionList &expansionList, 1155 StateAp *destState, Action *condAction, bool sense ); 1156 void embedCondition( MergeData &md, StateAp *state, Action *condAction, bool sense ); 1157 void embedCondition( StateAp *state, Action *condAction, bool sense ); 1158 1159 void startFsmCondition( Action *condAction, bool sense ); 1160 void allTransCondition( Action *condAction, bool sense ); 1161 void leaveFsmCondition( Action *condAction, bool sense ); 1162 1163 /* Set error actions to execute. */ 1164 void startErrorAction( int ordering, Action *action, int transferPoint ); 1165 void allErrorAction( int ordering, Action *action, int transferPoint ); 1166 void finalErrorAction( int ordering, Action *action, int transferPoint ); 1167 void notStartErrorAction( int ordering, Action *action, int transferPoint ); 1168 void notFinalErrorAction( int ordering, Action *action, int transferPoint ); 1169 void middleErrorAction( int ordering, Action *action, int transferPoint ); 1170 1171 /* Set EOF actions. */ 1172 void startEOFAction( int ordering, Action *action ); 1173 void allEOFAction( int ordering, Action *action ); 1174 void finalEOFAction( int ordering, Action *action ); 1175 void notStartEOFAction( int ordering, Action *action ); 1176 void notFinalEOFAction( int ordering, Action *action ); 1177 void middleEOFAction( int ordering, Action *action ); 1178 1179 /* Set To State actions. */ 1180 void startToStateAction( int ordering, Action *action ); 1181 void allToStateAction( int ordering, Action *action ); 1182 void finalToStateAction( int ordering, Action *action ); 1183 void notStartToStateAction( int ordering, Action *action ); 1184 void notFinalToStateAction( int ordering, Action *action ); 1185 void middleToStateAction( int ordering, Action *action ); 1186 1187 /* Set From State actions. */ 1188 void startFromStateAction( int ordering, Action *action ); 1189 void allFromStateAction( int ordering, Action *action ); 1190 void finalFromStateAction( int ordering, Action *action ); 1191 void notStartFromStateAction( int ordering, Action *action ); 1192 void notFinalFromStateAction( int ordering, Action *action ); 1193 void middleFromStateAction( int ordering, Action *action ); 1194 1195 /* Shift the action ordering of the start transitions to start at 1196 * fromOrder and increase in units of 1. Useful before kleene star 1197 * operation. */ 1198 int shiftStartActionOrder( int fromOrder ); 1199 1200 /* Clear all priorities from the fsm to so they won't affcet minimization 1201 * of the final fsm. */ 1202 void clearAllPriorities(); 1203 1204 /* Zero out all the function keys. */ 1205 void nullActionKeys(); 1206 1207 /* Walk the list of states and verify state properties. */ 1208 void verifyStates(); 1209 1210 /* Misfit Accounting. Are misfits put on a separate list. */ 1211 void setMisfitAccounting( bool val ) 1212 { misfitAccounting = val; } 1213 1214 /* Set and Unset a state as final. */ 1215 void setFinState( StateAp *state ); 1216 void unsetFinState( StateAp *state ); 1217 1218 void setStartState( StateAp *state ); 1219 void unsetStartState( ); 1220 1221 /* Set and unset a state as an entry point. */ 1222 void setEntry( int id, StateAp *state ); 1223 void changeEntry( int id, StateAp *to, StateAp *from ); 1224 void unsetEntry( int id, StateAp *state ); 1225 void unsetEntry( int id ); 1226 void unsetAllEntryPoints(); 1227 1228 /* Epsilon transitions. */ 1229 void epsilonTrans( int id ); 1230 void shadowReadWriteStates( MergeData &md ); 1231 1232 /* 1233 * Basic attaching and detaching. 1234 */ 1235 1236 /* Common to attaching/detaching list and default. */ 1237 void attachToInList( StateAp *from, StateAp *to, TransAp *&head, TransAp *trans ); 1238 void detachFromInList( StateAp *from, StateAp *to, TransAp *&head, TransAp *trans ); 1239 1240 /* Attach with a new transition. */ 1241 TransAp *attachNewTrans( StateAp *from, StateAp *to, 1242 Key onChar1, Key onChar2 ); 1243 1244 /* Attach with an existing transition that already in an out list. */ 1245 void attachTrans( StateAp *from, StateAp *to, TransAp *trans ); 1246 1247 /* Redirect a transition away from error and towards some state. */ 1248 void redirectErrorTrans( StateAp *from, StateAp *to, TransAp *trans ); 1249 1250 /* Detach a transition from a target state. */ 1251 void detachTrans( StateAp *from, StateAp *to, TransAp *trans ); 1252 1253 /* Detach a state from the graph. */ 1254 void detachState( StateAp *state ); 1255 1256 /* 1257 * NFA to DFA conversion routines. 1258 */ 1259 1260 /* Duplicate a transition that will dropin to a free spot. */ 1261 TransAp *dupTrans( StateAp *from, TransAp *srcTrans ); 1262 1263 /* In crossing, two transitions both go to real states. */ 1264 TransAp *fsmAttachStates( MergeData &md, StateAp *from, 1265 TransAp *destTrans, TransAp *srcTrans ); 1266 1267 /* Two transitions are to be crossed, handle the possibility of either 1268 * going to the error state. */ 1269 TransAp *mergeTrans( MergeData &md, StateAp *from, 1270 TransAp *destTrans, TransAp *srcTrans ); 1271 1272 /* Compare deterimne relative priorities of two transition tables. */ 1273 int comparePrior( const PriorTable &priorTable1, const PriorTable &priorTable2 ); 1274 1275 /* Cross a src transition with one that is already occupying a spot. */ 1276 TransAp *crossTransitions( MergeData &md, StateAp *from, 1277 TransAp *destTrans, TransAp *srcTrans ); 1278 1279 void outTransCopy( MergeData &md, StateAp *dest, TransAp *srcList ); 1280 1281 void doRemove( MergeData &md, StateAp *destState, ExpansionList &expList1 ); 1282 void doExpand( MergeData &md, StateAp *destState, ExpansionList &expList1 ); 1283 void findCondExpInTrans( ExpansionList &expansionList, StateAp *state, 1284 Key lowKey, Key highKey, CondSpace *fromCondSpace, CondSpace *toCondSpace, 1285 long destVals, LongVect &toValsList ); 1286 void findTransExpansions( ExpansionList &expansionList, 1287 StateAp *destState, StateAp *srcState ); 1288 void findCondExpansions( ExpansionList &expansionList, 1289 StateAp *destState, StateAp *srcState ); 1290 void mergeStateConds( StateAp *destState, StateAp *srcState ); 1291 1292 /* Merge a set of states into newState. */ 1293 void mergeStates( MergeData &md, StateAp *destState, 1294 StateAp **srcStates, int numSrc ); 1295 void mergeStatesLeaving( MergeData &md, StateAp *destState, StateAp *srcState ); 1296 void mergeStates( MergeData &md, StateAp *destState, StateAp *srcState ); 1297 1298 /* Make all states that are combinations of other states and that 1299 * have not yet had their out transitions filled in. This will 1300 * empty out stateDict and stFil. */ 1301 void fillInStates( MergeData &md ); 1302 1303 /* 1304 * Transition Comparison. 1305 */ 1306 1307 /* Compare transition data. Either of the pointers may be null. */ 1308 static inline int compareDataPtr( TransAp *trans1, TransAp *trans2 ); 1309 1310 /* Compare target state and transition data. Either pointer may be null. */ 1311 static inline int compareFullPtr( TransAp *trans1, TransAp *trans2 ); 1312 1313 /* Compare target partitions. Either pointer may be null. */ 1314 static inline int comparePartPtr( TransAp *trans1, TransAp *trans2 ); 1315 1316 /* Check marked status of target states. Either pointer may be null. */ 1317 static inline bool shouldMarkPtr( MarkIndex &markIndex, 1318 TransAp *trans1, TransAp *trans2 ); 1319 1320 /* 1321 * Callbacks. 1322 */ 1323 1324 /* Compare priority and function table of transitions. */ 1325 static int compareTransData( TransAp *trans1, TransAp *trans2 ); 1326 1327 /* Add in the properties of srcTrans into this. */ 1328 void addInTrans( TransAp *destTrans, TransAp *srcTrans ); 1329 1330 /* Compare states on data stored in the states. */ 1331 static int compareStateData( const StateAp *state1, const StateAp *state2 ); 1332 1333 /* Out transition data. */ 1334 void clearOutData( StateAp *state ); 1335 bool hasOutData( StateAp *state ); 1336 void transferOutData( StateAp *destState, StateAp *srcState ); 1337 1338 /* 1339 * Allocation. 1340 */ 1341 1342 /* New up a state and add it to the graph. */ 1343 StateAp *addState(); 1344 1345 /* 1346 * Building basic machines 1347 */ 1348 1349 void concatFsm( Key c ); 1350 void concatFsm( Key *str, int len ); 1351 void concatFsmCI( Key *str, int len ); 1352 void orFsm( Key *set, int len ); 1353 void rangeFsm( Key low, Key high ); 1354 void rangeStarFsm( Key low, Key high ); 1355 void emptyFsm( ); 1356 void lambdaFsm( ); 1357 1358 /* 1359 * Fsm operators. 1360 */ 1361 1362 void starOp( ); 1363 void repeatOp( int times ); 1364 void optionalRepeatOp( int times ); 1365 void concatOp( FsmAp *other ); 1366 void unionOp( FsmAp *other ); 1367 void intersectOp( FsmAp *other ); 1368 void subtractOp( FsmAp *other ); 1369 void epsilonOp(); 1370 void joinOp( int startId, int finalId, FsmAp **others, int numOthers ); 1371 void globOp( FsmAp **others, int numOthers ); 1372 void deterministicEntry(); 1373 1374 /* 1375 * Operator workers 1376 */ 1377 1378 /* Determine if there are any entry points into a start state other than 1379 * the start state. */ 1380 bool isStartStateIsolated(); 1381 1382 /* Make a new start state that has no entry points. Will not change the 1383 * identity of the fsm. */ 1384 void isolateStartState(); 1385 1386 /* Workers for resolving epsilon transitions. */ 1387 bool inEptVect( EptVect *eptVect, StateAp *targ ); 1388 void epsilonFillEptVectFrom( StateAp *root, StateAp *from, bool parentLeaving ); 1389 void resolveEpsilonTrans( MergeData &md ); 1390 1391 /* Workers for concatenation and union. */ 1392 void doConcat( FsmAp *other, StateSet *fromStates, bool optional ); 1393 void doOr( FsmAp *other ); 1394 1395 /* 1396 * Final states 1397 */ 1398 1399 /* Unset any final states that are no longer to be final 1400 * due to final bits. */ 1401 void unsetIncompleteFinals(); 1402 void unsetKilledFinals(); 1403 1404 /* Bring in other's entry points. Assumes others states are going to be 1405 * copied into this machine. */ 1406 void copyInEntryPoints( FsmAp *other ); 1407 1408 /* Ordering states. */ 1409 void depthFirstOrdering( StateAp *state ); 1410 void depthFirstOrdering(); 1411 void sortStatesByFinal(); 1412 1413 /* Set sqequential state numbers starting at 0. */ 1414 void setStateNumbers( int base ); 1415 1416 /* Unset all final states. */ 1417 void unsetAllFinStates(); 1418 1419 /* Set the bits of final states and clear the bits of non final states. */ 1420 void setFinBits( int finStateBits ); 1421 1422 /* 1423 * Self-consistency checks. 1424 */ 1425 1426 /* Run a sanity check on the machine. */ 1427 void verifyIntegrity(); 1428 1429 /* Verify that there are no unreachable states, or dead end states. */ 1430 void verifyReachability(); 1431 void verifyNoDeadEndStates(); 1432 1433 /* 1434 * Path pruning 1435 */ 1436 1437 /* Mark all states reachable from state. */ 1438 void markReachableFromHereReverse( StateAp *state ); 1439 1440 /* Mark all states reachable from state. */ 1441 void markReachableFromHere( StateAp *state ); 1442 void markReachableFromHereStopFinal( StateAp *state ); 1443 1444 /* Removes states that cannot be reached by any path in the fsm and are 1445 * thus wasted silicon. */ 1446 void removeDeadEndStates(); 1447 1448 /* Removes states that cannot be reached by any path in the fsm and are 1449 * thus wasted silicon. */ 1450 void removeUnreachableStates(); 1451 1452 /* Remove error actions from states on which the error transition will 1453 * never be taken. */ 1454 bool outListCovers( StateAp *state ); 1455 bool anyErrorRange( StateAp *state ); 1456 1457 /* Remove states that are on the misfit list. */ 1458 void removeMisfits(); 1459 1460 /* 1461 * FSM Minimization 1462 */ 1463 1464 /* Minimization by partitioning. */ 1465 void minimizePartition1(); 1466 void minimizePartition2(); 1467 1468 /* Minimize the final state Machine. The result is the minimal fsm. Slow 1469 * but stable, correct minimization. Uses n^2 space (lookout) and average 1470 * n^2 time. Worst case n^3 time, but a that is a very rare case. */ 1471 void minimizeStable(); 1472 1473 /* Minimize the final state machine. Does not find the minimal fsm, but a 1474 * pretty good approximation. Does not use any extra space. Average n^2 1475 * time. Worst case n^3 time, but a that is a very rare case. */ 1476 void minimizeApproximate(); 1477 1478 /* This is the worker for the minimize approximate solution. It merges 1479 * states that have identical out transitions. */ 1480 bool minimizeRound( ); 1481 1482 /* Given an intial partioning of states, split partitions that have out trans 1483 * to differing partitions. */ 1484 int partitionRound( StateAp **statePtrs, MinPartition *parts, int numParts ); 1485 1486 /* Split partitions that have a transition to a previously split partition, until 1487 * there are no more partitions to split. */ 1488 int splitCandidates( StateAp **statePtrs, MinPartition *parts, int numParts ); 1489 1490 /* Fuse together states in the same partition. */ 1491 void fusePartitions( MinPartition *parts, int numParts ); 1492 1493 /* Mark pairs where out final stateness differs, out trans data differs, 1494 * trans pairs go to a marked pair or trans data differs. Should get 1495 * alot of pairs. */ 1496 void initialMarkRound( MarkIndex &markIndex ); 1497 1498 /* One marking round on all state pairs. Considers if trans pairs go 1499 * to a marked state only. Returns whether or not a pair was marked. */ 1500 bool markRound( MarkIndex &markIndex ); 1501 1502 /* Move the in trans into src into dest. */ 1503 void inTransMove(StateAp *dest, StateAp *src); 1504 1505 /* Make state src and dest the same state. */ 1506 void fuseEquivStates(StateAp *dest, StateAp *src); 1507 1508 /* Find any states that didn't get marked by the marking algorithm and 1509 * merge them into the primary states of their equivalence class. */ 1510 void fuseUnmarkedPairs( MarkIndex &markIndex ); 1511 1512 /* Merge neighboring transitions go to the same state and have the same 1513 * transitions data. */ 1514 void compressTransitions(); 1515 1516 /* Returns true if there is a transtion (either explicit or by a gap) to 1517 * the error state. */ 1518 bool checkErrTrans( StateAp *state, TransAp *trans ); 1519 bool checkErrTransFinish( StateAp *state ); 1520 bool hasErrorTrans(); 1521 1522 /* Check if a machine defines a single character. This is useful in 1523 * validating ranges and machines to export. */ 1524 bool checkSingleCharMachine( ); 1525 }; 1526 1527 #endif