2 * Copyright 2001-2007 Adrian Thurston <thurston@cs.queensu.ca>
5 /* This file is part of Ragel.
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.
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.
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
36 #include "sbsttable.h"
43 /* Flags that control merging. */
44 #define SB_GRAPH1 0x01
45 #define SB_GRAPH2 0x02
47 #define SB_ISFINAL 0x04
48 #define SB_ISMARKED 0x08
49 #define SB_ONLIST 0x10
57 struct LongestMatchPart;
59 /* State list element for unambiguous access to list element. */
65 /* This is the marked index for a state pair. Used in minimization. It keeps
66 * track of whether or not the state pair is marked. */
69 MarkIndex(int states);
72 void markPair(int state1, int state2);
73 bool isPairMarked(int state1, int state2);
80 extern KeyOps *keyOps;
82 /* Transistion Action Element. */
83 typedef SBstMapEl< int, Action* > ActionTableEl;
85 /* Nodes in the tree that use this action. */
88 typedef Vector<NameInst*> ActionRefs;
90 /* Element in list of actions. Contains the string for the code to exectute. */
93 public DListEl<Action>,
94 public AvlTreeEl<Action>
98 Action( const InputLoc &loc, char *name, InlineList *inlineList, int condId )
102 inlineList(inlineList),
115 /* Key for action dictionary. */
116 char *getKey() const { return name; }
118 /* Data collected during parse. */
121 InlineList *inlineList;
124 void actionName( ostream &out )
129 out << loc.line << ":" << loc.col;
132 /* Places in the input text that reference the action. */
133 ActionRefs actionRefs;
135 /* Number of references in the final machine. */
137 { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; }
140 int numFromStateRefs;
151 static inline int compare( const Action *cond1, const Action *cond2 )
153 if ( cond1->condId < cond2->condId )
155 else if ( cond1->condId > cond2->condId )
161 /* A list of actions. */
162 typedef DList<Action> ActionList;
163 typedef AvlTree<Action, char *, CmpStr> ActionDict;
165 /* Structure for reverse action mapping. */
166 struct RevActionMapEl
173 /* Transition Action Table. */
175 : public SBstMap< int, Action*, CmpOrd<int> >
177 void setAction( int ordering, Action *action );
178 void setActions( int *orderings, Action **actions, int nActs );
179 void setActions( const ActionTable &other );
181 bool hasAction( Action *action );
184 typedef SBstSet< Action*, CmpOrd<Action*> > ActionSet;
185 typedef CmpSTable< Action*, CmpOrd<Action*> > CmpActionSet;
187 /* Transistion Action Element. */
188 typedef SBstMapEl< int, LongestMatchPart* > LmActionTableEl;
190 /* Transition Action Table. */
192 : public SBstMap< int, LongestMatchPart*, CmpOrd<int> >
194 void setAction( int ordering, LongestMatchPart *action );
195 void setActions( const LmActionTable &other );
198 /* Compare of a whole action table element (key & value). */
199 struct CmpActionTableEl
201 static int compare( const ActionTableEl &action1,
202 const ActionTableEl &action2 )
204 if ( action1.key < action2.key )
206 else if ( action1.key > action2.key )
208 else if ( action1.value < action2.value )
210 else if ( action1.value > action2.value )
216 /* Compare for ActionTable. */
217 typedef CmpSTable< ActionTableEl, CmpActionTableEl > CmpActionTable;
219 /* Compare of a whole lm action table element (key & value). */
220 struct CmpLmActionTableEl
222 static int compare( const LmActionTableEl &lmAction1,
223 const LmActionTableEl &lmAction2 )
225 if ( lmAction1.key < lmAction2.key )
227 else if ( lmAction1.key > lmAction2.key )
229 else if ( lmAction1.value < lmAction2.value )
231 else if ( lmAction1.value > lmAction2.value )
237 /* Compare for ActionTable. */
238 typedef CmpSTable< LmActionTableEl, CmpLmActionTableEl > CmpLmActionTable;
240 /* Action table element for error action tables. Adds the encoding of transfer
242 struct ErrActionTableEl
244 ErrActionTableEl( Action *action, int ordering, int transferPoint )
245 : ordering(ordering), action(action), transferPoint(transferPoint) { }
247 /* Ordering and id of the action embedding. */
251 /* Id of point of transfere from Error action table to transtions and
255 int getKey() const { return ordering; }
258 struct ErrActionTable
259 : public SBstTable< ErrActionTableEl, int, CmpOrd<int> >
261 void setAction( int ordering, Action *action, int transferPoint );
262 void setActions( const ErrActionTable &other );
265 /* Compare of an error action table element (key & value). */
266 struct CmpErrActionTableEl
268 static int compare( const ErrActionTableEl &action1,
269 const ErrActionTableEl &action2 )
271 if ( action1.ordering < action2.ordering )
273 else if ( action1.ordering > action2.ordering )
275 else if ( action1.action < action2.action )
277 else if ( action1.action > action2.action )
279 else if ( action1.transferPoint < action2.transferPoint )
281 else if ( action1.transferPoint > action2.transferPoint )
287 /* Compare for ErrActionTable. */
288 typedef CmpSTable< ErrActionTableEl, CmpErrActionTableEl > CmpErrActionTable;
291 /* Descibe a priority, shared among PriorEls.
292 * Has key and whether or not used. */
299 /* Element in the arrays of priorities for transitions and arrays. Ordering is
300 * unique among instantiations of machines, desc is shared. */
303 PriorEl( int ordering, PriorDesc *desc )
304 : ordering(ordering), desc(desc) { }
310 /* Compare priority elements, which are ordered by the priority descriptor
314 static inline int compare( const PriorEl &pel1, const PriorEl &pel2 )
316 if ( pel1.desc->key < pel2.desc->key )
318 else if ( pel1.desc->key > pel2.desc->key )
326 /* Priority Table. */
328 : public SBstSet< PriorEl, PriorElCmp >
330 void setPrior( int ordering, PriorDesc *desc );
331 void setPriors( const PriorTable &other );
334 /* Compare of prior table elements for distinguising state data. */
337 static inline int compare( const PriorEl &pel1, const PriorEl &pel2 )
339 if ( pel1.desc < pel2.desc )
341 else if ( pel1.desc > pel2.desc )
343 else if ( pel1.ordering < pel2.ordering )
345 else if ( pel1.ordering > pel2.ordering )
351 /* Compare of PriorTable distinguising state data. Using a compare of the
352 * pointers is a little more strict than it needs be. It requires that
353 * prioritiy tables have the exact same set of priority assignment operators
354 * (from the input lang) to be considered equal.
356 * Really only key-value pairs need be tested and ordering be merged. However
357 * this would require that in the fuseing of states, priority descriptors be
358 * chosen for the new fused state based on priority. Since the out transition
359 * lists and ranges aren't necessarily going to line up, this is more work for
360 * little gain. Final compression resets all priorities first, so this would
361 * only be useful for compression at every operator, which is only an
362 * undocumented test feature.
364 typedef CmpSTable<PriorEl, CmpPriorEl> CmpPriorTable;
366 /* Plain action list that imposes no ordering. */
367 typedef Vector<int> TransFuncList;
369 /* Comparison for TransFuncList. */
370 typedef CmpTable< int, CmpOrd<int> > TransFuncListCompare;
372 /* Transition class that implements actions and priorities. */
375 TransAp() : fromState(0), toState(0) {}
376 TransAp( const TransAp &other ) :
377 lowKey(other.lowKey),
378 highKey(other.highKey),
379 fromState(0), toState(0),
380 actionTable(other.actionTable),
381 priorTable(other.priorTable)
383 assert( lmActionTable.length() == 0 && other.lmActionTable.length() == 0 );
390 /* Pointers for outlist. */
391 TransAp *prev, *next;
393 /* Pointers for in-list. */
394 TransAp *ilprev, *ilnext;
396 /* The function table and priority for the transition. */
397 ActionTable actionTable;
398 PriorTable priorTable;
400 LmActionTable lmActionTable;
403 /* In transition list. Like DList except only has head pointers, which is all
404 * that is required. Insertion and deletion is handled by the graph. This
405 * class provides the iterator of a single list. */
408 TransInList() : head(0) { }
414 /* Default construct. */
417 /* Construct, assign from a list. */
418 Iter( const TransInList &il ) : ptr(il.head) { }
419 Iter &operator=( const TransInList &dl ) { ptr = dl.head; return *this; }
422 bool lte() const { return ptr != 0; }
423 bool end() const { return ptr == 0; }
425 /* At the first, last element. */
426 bool first() const { return ptr && ptr->ilprev == 0; }
427 bool last() const { return ptr && ptr->ilnext == 0; }
429 /* Cast, dereference, arrow ops. */
430 operator TransAp*() const { return ptr; }
431 TransAp &operator *() const { return *ptr; }
432 TransAp *operator->() const { return ptr; }
434 /* Increment, decrement. */
435 inline void operator++(int) { ptr = ptr->ilnext; }
436 inline void operator--(int) { ptr = ptr->ilprev; }
438 /* The iterator is simply a pointer. */
443 typedef DList<TransAp> TransList;
445 /* Set of states, list of states. */
446 typedef BstSet<StateAp*> StateSet;
447 typedef DList<StateAp> StateList;
449 /* A element in a state dict. */
452 public AvlTreeEl<StateDictEl>
454 StateDictEl(const StateSet &stateSet)
455 : stateSet(stateSet) { }
457 const StateSet &getKey() { return stateSet; }
462 /* Dictionary mapping a set of states to a target state. */
463 typedef AvlTree< StateDictEl, StateSet, CmpTable<StateAp*> > StateDict;
465 /* Data needed for a merge operation. */
469 : stfillHead(0), stfillTail(0) { }
476 void fillListAppend( StateAp *state );
483 TransEl( Key lowKey, Key highKey )
484 : lowKey(lowKey), highKey(highKey) { }
485 TransEl( Key lowKey, Key highKey, TransAp *value )
486 : lowKey(lowKey), highKey(highKey), value(value) { }
494 static int compare( const Key key1, const Key key2 )
498 else if ( key1 > key2 )
505 /* Vector based set of key items. */
506 typedef BstSet<Key, CmpKey> KeySet;
510 MinPartition() : active(false) { }
515 MinPartition *prev, *next;
518 /* Epsilon transition stored in a state. Specifies the target */
519 typedef Vector<int> EpsilonTrans;
521 /* List of states that are to be drawn into this. */
524 EptVectEl( StateAp *targ, bool leaving )
525 : targ(targ), leaving(leaving) { }
530 typedef Vector<EptVectEl> EptVect;
532 /* Set of entry ids that go into this state. */
533 typedef BstSet<int> EntryIdSet;
535 /* Set of longest match items that may be active in a given state. */
536 typedef BstSet<LongestMatchPart*> LmItemSet;
539 typedef BstSet< Action*, CmpCondId > CondSet;
540 typedef CmpTable< Action*, CmpCondId > CmpCondSet;
543 : public AvlTreeEl<CondSpace>
545 CondSpace( const CondSet &condSet )
546 : condSet(condSet) {}
548 const CondSet &getKey() { return condSet; }
555 typedef Vector<CondSpace*> CondSpaceVect;
557 typedef AvlTree<CondSpace, CondSet, CmpCondSet> CondSpaceMap;
561 StateCond( Key lowKey, Key highKey ) :
562 lowKey(lowKey), highKey(highKey) {}
566 CondSpace *condSpace;
568 StateCond *prev, *next;
571 typedef DList<StateCond> StateCondList;
572 typedef Vector<long> LongVect;
576 Expansion( Key lowKey, Key highKey ) :
577 lowKey(lowKey), highKey(highKey),
578 fromTrans(0), fromCondSpace(0),
583 if ( fromTrans != 0 )
591 CondSpace *fromCondSpace;
594 CondSpace *toCondSpace;
597 Expansion *prev, *next;
600 typedef DList<Expansion> ExpansionList;
612 CondData() : nextCondKey(0) {}
614 /* Condition info. */
617 CondSpaceMap condSpaceMap;
620 extern CondData *condData;
622 /* State class that implements actions and priorities. */
626 StateAp(const StateAp &other);
629 /* Is the state final? */
630 bool isFinState() { return stateBits & SB_ISFINAL; }
632 /* Out transition list and the pointer for the default out trans. */
635 /* In transition Lists. */
638 /* Entry points into the state. */
641 /* Epsilon transitions. */
642 EpsilonTrans epsilonTrans;
644 /* Condition info. */
645 StateCondList stateCondList;
647 /* Number of in transitions from states other than ourselves. */
650 /* Temporary data for various algorithms. */
652 /* When duplicating the fsm we need to map each
653 * state to the new state representing it. */
656 /* When minimizing machines by partitioning, this maps to the group
657 * the state is in. */
658 MinPartition *partition;
660 /* When merging states (state machine operations) this next pointer is
661 * used for the list of states that need to be filled in. */
664 /* Identification for printing and stable minimization. */
669 /* Data used in epsilon operation, maybe fit into alg? */
670 StateAp *isolatedShadow;
673 /* A pointer to a dict element that contains the set of states this state
674 * represents. This cannot go into alg, because alg.next is used during
675 * the merging process. */
676 StateDictEl *stateDictEl;
678 /* When drawing epsilon transitions, holds the list of states to merge
682 /* Bits controlling the behaviour of the state during collapsing to dfa. */
685 /* State list elements. */
686 StateAp *next, *prev;
689 * Priority and Action data.
692 /* Out priorities transfered to out transitions. */
693 PriorTable outPriorTable;
695 /* The following two action tables are distinguished by the fact that when
696 * toState actions are executed immediatly after transition actions of
697 * incoming transitions and the current character will be the same as the
698 * one available then. The fromState actions are executed immediately
699 * before the transition actions of outgoing transitions and the current
700 * character is same as the one available then. */
702 /* Actions to execute upon entering into a state. */
703 ActionTable toStateActionTable;
705 /* Actions to execute when going from the state to the transition. */
706 ActionTable fromStateActionTable;
708 /* Actions to add to any future transitions that leave via this state. */
709 ActionTable outActionTable;
711 /* Conditions to add to any future transiions that leave via this sttate. */
712 ActionSet outCondSet;
714 /* Error action tables. */
715 ErrActionTable errActionTable;
717 /* Actions to execute on eof. */
718 ActionTable eofActionTable;
720 /* Set of longest match items that may be active in this state. */
724 template <class ListItem> struct NextTrans
735 lowKey = trans->lowKey;
736 highKey = trans->highKey;
740 void set( ListItem *t ) {
752 /* Encodes the different states that are meaningful to the of the iterator. */
753 enum PairIterUserState
755 RangeInS1, RangeInS2,
760 template <class ListItem1, class ListItem2 = ListItem1> struct PairIter
762 /* Encodes the different states that an fsm iterator can be in. */
765 ConsumeS1Range, ConsumeS2Range,
766 OnlyInS1Range, OnlyInS2Range,
767 S1SticksOut, S1SticksOutBreak,
768 S2SticksOut, S2SticksOutBreak,
769 S1DragsBehind, S1DragsBehindBreak,
770 S2DragsBehind, S2DragsBehindBreak,
774 PairIter( ListItem1 *list1, ListItem2 *list2 );
776 /* Query iterator. */
777 bool lte() { return itState != End; }
778 bool end() { return itState == End; }
779 void operator++(int) { findNext(); }
780 void operator++() { findNext(); }
782 /* Iterator state. */
786 PairIterUserState userState;
788 NextTrans<ListItem1> s1Tel;
789 NextTrans<ListItem2> s2Tel;
790 Key bottomLow, bottomHigh;
791 ListItem1 *bottomTrans1;
792 ListItem2 *bottomTrans2;
798 /* Init the iterator by advancing to the first item. */
799 template <class ListItem1, class ListItem2> PairIter<ListItem1, ListItem2>::PairIter(
800 ListItem1 *list1, ListItem2 *list2 )
809 /* Return and re-entry for the co-routine iterators. This should ALWAYS be
810 * used inside of a block. */
811 #define CO_RETURN(label) \
814 entry##label: backIn = true
816 /* Return and re-entry for the co-routine iterators. This should ALWAYS be
817 * used inside of a block. */
818 #define CO_RETURN2(label, uState) \
820 userState = uState; \
822 entry##label: backIn = true
824 /* Advance to the next transition. When returns, trans points to the next
825 * transition, unless there are no more, in which case end() returns true. */
826 template <class ListItem1, class ListItem2> void PairIter<ListItem1, ListItem2>::findNext()
828 /* This variable is used in dummy statements that follow the entry
829 * goto labels. The compiler needs some statement to follow the label. */
832 /* Jump into the iterator routine base on the iterator state. */
834 case Begin: goto entryBegin;
835 case ConsumeS1Range: goto entryConsumeS1Range;
836 case ConsumeS2Range: goto entryConsumeS2Range;
837 case OnlyInS1Range: goto entryOnlyInS1Range;
838 case OnlyInS2Range: goto entryOnlyInS2Range;
839 case S1SticksOut: goto entryS1SticksOut;
840 case S1SticksOutBreak: goto entryS1SticksOutBreak;
841 case S2SticksOut: goto entryS2SticksOut;
842 case S2SticksOutBreak: goto entryS2SticksOutBreak;
843 case S1DragsBehind: goto entryS1DragsBehind;
844 case S1DragsBehindBreak: goto entryS1DragsBehindBreak;
845 case S2DragsBehind: goto entryS2DragsBehind;
846 case S2DragsBehindBreak: goto entryS2DragsBehindBreak;
847 case ExactOverlap: goto entryExactOverlap;
848 case End: goto entryEnd;
852 /* Set up the next structs at the head of the transition lists. */
856 /* Concurrently scan both out ranges. */
858 if ( s1Tel.trans == 0 ) {
859 /* We are at the end of state1's ranges. Process the rest of
860 * state2's ranges. */
861 while ( s2Tel.trans != 0 ) {
862 /* Range is only in s2. */
863 CO_RETURN2( ConsumeS2Range, RangeInS2 );
868 else if ( s2Tel.trans == 0 ) {
869 /* We are at the end of state2's ranges. Process the rest of
870 * state1's ranges. */
871 while ( s1Tel.trans != 0 ) {
872 /* Range is only in s1. */
873 CO_RETURN2( ConsumeS1Range, RangeInS1 );
878 /* Both state1's and state2's transition elements are good.
879 * The signiture of no overlap is a back key being in front of a
881 else if ( s1Tel.highKey < s2Tel.lowKey ) {
882 /* A range exists in state1 that does not overlap with state2. */
883 CO_RETURN2( OnlyInS1Range, RangeInS1 );
886 else if ( s2Tel.highKey < s1Tel.lowKey ) {
887 /* A range exists in state2 that does not overlap with state1. */
888 CO_RETURN2( OnlyInS2Range, RangeInS2 );
891 /* There is overlap, must mix the ranges in some way. */
892 else if ( s1Tel.lowKey < s2Tel.lowKey ) {
893 /* Range from state1 sticks out front. Must break it into
894 * non-overlaping and overlaping segments. */
895 bottomLow = s2Tel.lowKey;
896 bottomHigh = s1Tel.highKey;
897 s1Tel.highKey = s2Tel.lowKey;
898 s1Tel.highKey.decrement();
899 bottomTrans1 = s1Tel.trans;
901 /* Notify the caller that we are breaking s1. This gives them a
902 * chance to duplicate s1Tel[0,1].value. */
903 CO_RETURN2( S1SticksOutBreak, BreakS1 );
905 /* Broken off range is only in s1. */
906 CO_RETURN2( S1SticksOut, RangeInS1 );
908 /* Advance over the part sticking out front. */
909 s1Tel.lowKey = bottomLow;
910 s1Tel.highKey = bottomHigh;
911 s1Tel.trans = bottomTrans1;
913 else if ( s2Tel.lowKey < s1Tel.lowKey ) {
914 /* Range from state2 sticks out front. Must break it into
915 * non-overlaping and overlaping segments. */
916 bottomLow = s1Tel.lowKey;
917 bottomHigh = s2Tel.highKey;
918 s2Tel.highKey = s1Tel.lowKey;
919 s2Tel.highKey.decrement();
920 bottomTrans2 = s2Tel.trans;
922 /* Notify the caller that we are breaking s2. This gives them a
923 * chance to duplicate s2Tel[0,1].value. */
924 CO_RETURN2( S2SticksOutBreak, BreakS2 );
926 /* Broken off range is only in s2. */
927 CO_RETURN2( S2SticksOut, RangeInS2 );
929 /* Advance over the part sticking out front. */
930 s2Tel.lowKey = bottomLow;
931 s2Tel.highKey = bottomHigh;
932 s2Tel.trans = bottomTrans2;
934 /* Low ends are even. Are the high ends even? */
935 else if ( s1Tel.highKey < s2Tel.highKey ) {
936 /* Range from state2 goes longer than the range from state1. We
937 * must break the range from state2 into an evenly overlaping
939 bottomLow = s1Tel.highKey;
940 bottomLow.increment();
941 bottomHigh = s2Tel.highKey;
942 s2Tel.highKey = s1Tel.highKey;
943 bottomTrans2 = s2Tel.trans;
945 /* Notify the caller that we are breaking s2. This gives them a
946 * chance to duplicate s2Tel[0,1].value. */
947 CO_RETURN2( S2DragsBehindBreak, BreakS2 );
949 /* Breaking s2 produces exact overlap. */
950 CO_RETURN2( S2DragsBehind, RangeOverlap );
952 /* Advance over the front we just broke off of range 2. */
953 s2Tel.lowKey = bottomLow;
954 s2Tel.highKey = bottomHigh;
955 s2Tel.trans = bottomTrans2;
957 /* Advance over the entire s1Tel. We have consumed it. */
960 else if ( s2Tel.highKey < s1Tel.highKey ) {
961 /* Range from state1 goes longer than the range from state2. We
962 * must break the range from state1 into an evenly overlaping
964 bottomLow = s2Tel.highKey;
965 bottomLow.increment();
966 bottomHigh = s1Tel.highKey;
967 s1Tel.highKey = s2Tel.highKey;
968 bottomTrans1 = s1Tel.trans;
970 /* Notify the caller that we are breaking s1. This gives them a
971 * chance to duplicate s2Tel[0,1].value. */
972 CO_RETURN2( S1DragsBehindBreak, BreakS1 );
974 /* Breaking s1 produces exact overlap. */
975 CO_RETURN2( S1DragsBehind, RangeOverlap );
977 /* Advance over the front we just broke off of range 1. */
978 s1Tel.lowKey = bottomLow;
979 s1Tel.highKey = bottomHigh;
980 s1Tel.trans = bottomTrans1;
982 /* Advance over the entire s2Tel. We have consumed it. */
986 /* There is an exact overlap. */
987 CO_RETURN2( ExactOverlap, RangeOverlap );
994 /* Done, go into end state. */
999 /* Compare lists of epsilon transitions. Entries are name ids of targets. */
1000 typedef CmpTable< int, CmpOrd<int> > CmpEpsilonTrans;
1002 /* Compare class for the Approximate minimization. */
1007 int compare( const StateAp *pState1, const StateAp *pState2 );
1010 /* Compare class for the initial partitioning of a partition minimization. */
1011 class InitPartitionCompare
1014 InitPartitionCompare() { }
1015 int compare( const StateAp *pState1, const StateAp *pState2 );
1018 /* Compare class for the regular partitioning of a partition minimization. */
1019 class PartitionCompare
1022 PartitionCompare() { }
1023 int compare( const StateAp *pState1, const StateAp *pState2 );
1026 /* Compare class for a minimization that marks pairs. Provides the shouldMark
1032 bool shouldMark( MarkIndex &markIndex, const StateAp *pState1,
1033 const StateAp *pState2 );
1036 /* List of partitions. */
1037 typedef DList< MinPartition > PartitionList;
1039 /* List of transtions out of a state. */
1040 typedef Vector<TransEl> TransListVect;
1042 /* Entry point map used for keeping track of entry points in a machine. */
1043 typedef BstSet< int > EntryIdSet;
1044 typedef BstMapEl< int, StateAp* > EntryMapEl;
1045 typedef BstMap< int, StateAp* > EntryMap;
1046 typedef Vector<EntryMapEl> EntryMapBase;
1048 /* Graph class that implements actions and priorities. */
1051 /* Constructors/Destructors. */
1053 FsmAp( const FsmAp &graph );
1056 /* The list of states. */
1057 StateList stateList;
1058 StateList misfitList;
1060 /* The map of entry points. */
1061 EntryMap entryPoints;
1063 /* The start state. */
1064 StateAp *startState;
1066 /* Error state, possibly created only when the final machine has been
1067 * created and the XML machine is about to be written. No transitions
1068 * point to this state. */
1071 /* The set of final states. */
1072 StateSet finStateSet;
1074 /* Misfit Accounting. Are misfits put on a separate list. */
1075 bool misfitAccounting;
1078 * Transition actions and priorities.
1081 /* Set priorities on transtions. */
1082 void startFsmPrior( int ordering, PriorDesc *prior );
1083 void allTransPrior( int ordering, PriorDesc *prior );
1084 void finishFsmPrior( int ordering, PriorDesc *prior );
1085 void leaveFsmPrior( int ordering, PriorDesc *prior );
1087 /* Action setting support. */
1088 void transferErrorActions( StateAp *state, int transferPoint );
1089 void setErrorAction( StateAp *state, int ordering, Action *action );
1091 /* Fill all spaces in a transition list with an error transition. */
1092 void fillGaps( StateAp *state );
1094 /* Similar to setErrorAction, instead gives a state to go to on error. */
1095 void setErrorTarget( StateAp *state, StateAp *target, int *orderings,
1096 Action **actions, int nActs );
1098 /* Set actions to execute. */
1099 void startFsmAction( int ordering, Action *action );
1100 void allTransAction( int ordering, Action *action );
1101 void finishFsmAction( int ordering, Action *action );
1102 void leaveFsmAction( int ordering, Action *action );
1103 void longMatchAction( int ordering, LongestMatchPart *lmPart );
1105 /* Set conditions. */
1106 CondSpace *addCondSpace( const CondSet &condSet );
1108 void findEmbedExpansions( ExpansionList &expansionList,
1109 StateAp *destState, Action *condAction );
1110 void embedCondition( MergeData &md, StateAp *state, Action *condAction );
1111 void embedCondition( StateAp *state, Action *condAction );
1113 void startFsmCondition( Action *condAction );
1114 void allTransCondition( Action *condAction );
1115 void leaveFsmCondition( Action *condAction );
1117 /* Set error actions to execute. */
1118 void startErrorAction( int ordering, Action *action, int transferPoint );
1119 void allErrorAction( int ordering, Action *action, int transferPoint );
1120 void finalErrorAction( int ordering, Action *action, int transferPoint );
1121 void notStartErrorAction( int ordering, Action *action, int transferPoint );
1122 void notFinalErrorAction( int ordering, Action *action, int transferPoint );
1123 void middleErrorAction( int ordering, Action *action, int transferPoint );
1125 /* Set EOF actions. */
1126 void startEOFAction( int ordering, Action *action );
1127 void allEOFAction( int ordering, Action *action );
1128 void finalEOFAction( int ordering, Action *action );
1129 void notStartEOFAction( int ordering, Action *action );
1130 void notFinalEOFAction( int ordering, Action *action );
1131 void middleEOFAction( int ordering, Action *action );
1133 /* Set To State actions. */
1134 void startToStateAction( int ordering, Action *action );
1135 void allToStateAction( int ordering, Action *action );
1136 void finalToStateAction( int ordering, Action *action );
1137 void notStartToStateAction( int ordering, Action *action );
1138 void notFinalToStateAction( int ordering, Action *action );
1139 void middleToStateAction( int ordering, Action *action );
1141 /* Set From State actions. */
1142 void startFromStateAction( int ordering, Action *action );
1143 void allFromStateAction( int ordering, Action *action );
1144 void finalFromStateAction( int ordering, Action *action );
1145 void notStartFromStateAction( int ordering, Action *action );
1146 void notFinalFromStateAction( int ordering, Action *action );
1147 void middleFromStateAction( int ordering, Action *action );
1149 /* Shift the action ordering of the start transitions to start at
1150 * fromOrder and increase in units of 1. Useful before kleene star
1152 int shiftStartActionOrder( int fromOrder );
1154 /* Clear all priorities from the fsm to so they won't affcet minimization
1155 * of the final fsm. */
1156 void clearAllPriorities();
1158 /* Zero out all the function keys. */
1159 void nullActionKeys();
1161 /* Walk the list of states and verify state properties. */
1162 void verifyStates();
1164 /* Misfit Accounting. Are misfits put on a separate list. */
1165 void setMisfitAccounting( bool val )
1166 { misfitAccounting = val; }
1168 /* Set and Unset a state as final. */
1169 void setFinState( StateAp *state );
1170 void unsetFinState( StateAp *state );
1172 void setStartState( StateAp *state );
1173 void unsetStartState( );
1175 /* Set and unset a state as an entry point. */
1176 void setEntry( int id, StateAp *state );
1177 void changeEntry( int id, StateAp *to, StateAp *from );
1178 void unsetEntry( int id, StateAp *state );
1179 void unsetEntry( int id );
1180 void unsetAllEntryPoints();
1182 /* Epsilon transitions. */
1183 void epsilonTrans( int id );
1184 void shadowReadWriteStates( MergeData &md );
1187 * Basic attaching and detaching.
1190 /* Common to attaching/detaching list and default. */
1191 void attachToInList( StateAp *from, StateAp *to, TransAp *&head, TransAp *trans );
1192 void detachFromInList( StateAp *from, StateAp *to, TransAp *&head, TransAp *trans );
1194 /* Attach with a new transition. */
1195 TransAp *attachNewTrans( StateAp *from, StateAp *to,
1196 Key onChar1, Key onChar2 );
1198 /* Attach with an existing transition that already in an out list. */
1199 void attachTrans( StateAp *from, StateAp *to, TransAp *trans );
1201 /* Redirect a transition away from error and towards some state. */
1202 void redirectErrorTrans( StateAp *from, StateAp *to, TransAp *trans );
1204 /* Detach a transition from a target state. */
1205 void detachTrans( StateAp *from, StateAp *to, TransAp *trans );
1207 /* Detach a state from the graph. */
1208 void detachState( StateAp *state );
1211 * NFA to DFA conversion routines.
1214 /* Duplicate a transition that will dropin to a free spot. */
1215 TransAp *dupTrans( StateAp *from, TransAp *srcTrans );
1217 /* In crossing, two transitions both go to real states. */
1218 TransAp *fsmAttachStates( MergeData &md, StateAp *from,
1219 TransAp *destTrans, TransAp *srcTrans );
1221 /* Two transitions are to be crossed, handle the possibility of either
1222 * going to the error state. */
1223 TransAp *mergeTrans( MergeData &md, StateAp *from,
1224 TransAp *destTrans, TransAp *srcTrans );
1226 /* Compare deterimne relative priorities of two transition tables. */
1227 int comparePrior( const PriorTable &priorTable1, const PriorTable &priorTable2 );
1229 /* Cross a src transition with one that is already occupying a spot. */
1230 TransAp *crossTransitions( MergeData &md, StateAp *from,
1231 TransAp *destTrans, TransAp *srcTrans );
1233 void outTransCopy( MergeData &md, StateAp *dest, TransAp *srcList );
1235 void doRemove( MergeData &md, StateAp *destState, ExpansionList &expList1 );
1236 void doExpand( MergeData &md, StateAp *destState, ExpansionList &expList1 );
1237 void findCondExpInTrans( ExpansionList &expansionList, StateAp *state,
1238 Key lowKey, Key highKey, CondSpace *fromCondSpace, CondSpace *toCondSpace,
1239 long destVals, LongVect &toValsList );
1240 void findTransExpansions( ExpansionList &expansionList,
1241 StateAp *destState, StateAp *srcState );
1242 void findCondExpansions( ExpansionList &expansionList,
1243 StateAp *destState, StateAp *srcState );
1244 void mergeStateConds( StateAp *destState, StateAp *srcState );
1246 /* Merge a set of states into newState. */
1247 void mergeStates( MergeData &md, StateAp *destState,
1248 StateAp **srcStates, int numSrc );
1249 void mergeStatesLeaving( MergeData &md, StateAp *destState, StateAp *srcState );
1250 void mergeStates( MergeData &md, StateAp *destState, StateAp *srcState );
1252 /* Make all states that are combinations of other states and that
1253 * have not yet had their out transitions filled in. This will
1254 * empty out stateDict and stFil. */
1255 void fillInStates( MergeData &md );
1258 * Transition Comparison.
1261 /* Compare transition data. Either of the pointers may be null. */
1262 static inline int compareDataPtr( TransAp *trans1, TransAp *trans2 );
1264 /* Compare target state and transition data. Either pointer may be null. */
1265 static inline int compareFullPtr( TransAp *trans1, TransAp *trans2 );
1267 /* Compare target partitions. Either pointer may be null. */
1268 static inline int comparePartPtr( TransAp *trans1, TransAp *trans2 );
1270 /* Check marked status of target states. Either pointer may be null. */
1271 static inline bool shouldMarkPtr( MarkIndex &markIndex,
1272 TransAp *trans1, TransAp *trans2 );
1278 /* Compare priority and function table of transitions. */
1279 static int compareTransData( TransAp *trans1, TransAp *trans2 );
1281 /* Add in the properties of srcTrans into this. */
1282 void addInTrans( TransAp *destTrans, TransAp *srcTrans );
1284 /* Compare states on data stored in the states. */
1285 static int compareStateData( const StateAp *state1, const StateAp *state2 );
1287 /* Out transition data. */
1288 void clearOutData( StateAp *state );
1289 bool hasOutData( StateAp *state );
1290 void transferOutData( StateAp *destState, StateAp *srcState );
1296 /* New up a state and add it to the graph. */
1297 StateAp *addState();
1300 * Building basic machines
1303 void concatFsm( Key c );
1304 void concatFsm( Key *str, int len );
1305 void concatFsmCI( Key *str, int len );
1306 void orFsm( Key *set, int len );
1307 void rangeFsm( Key low, Key high );
1308 void rangeStarFsm( Key low, Key high );
1317 void repeatOp( int times );
1318 void optionalRepeatOp( int times );
1319 void concatOp( FsmAp *other );
1320 void unionOp( FsmAp *other );
1321 void intersectOp( FsmAp *other );
1322 void subtractOp( FsmAp *other );
1324 void joinOp( int startId, int finalId, FsmAp **others, int numOthers );
1325 void globOp( FsmAp **others, int numOthers );
1326 void deterministicEntry();
1332 /* Determine if there are any entry points into a start state other than
1333 * the start state. */
1334 bool isStartStateIsolated();
1336 /* Make a new start state that has no entry points. Will not change the
1337 * identity of the fsm. */
1338 void isolateStartState();
1340 /* Workers for resolving epsilon transitions. */
1341 bool inEptVect( EptVect *eptVect, StateAp *targ );
1342 void epsilonFillEptVectFrom( StateAp *root, StateAp *from, bool parentLeaving );
1343 void resolveEpsilonTrans( MergeData &md );
1345 /* Workers for concatenation and union. */
1346 void doConcat( FsmAp *other, StateSet *fromStates, bool optional );
1347 void doOr( FsmAp *other );
1353 /* Unset any final states that are no longer to be final
1354 * due to final bits. */
1355 void unsetIncompleteFinals();
1356 void unsetKilledFinals();
1358 /* Bring in other's entry points. Assumes others states are going to be
1359 * copied into this machine. */
1360 void copyInEntryPoints( FsmAp *other );
1362 /* Ordering states. */
1363 void depthFirstOrdering( StateAp *state );
1364 void depthFirstOrdering();
1365 void sortStatesByFinal();
1367 /* Set sqequential state numbers starting at 0. */
1368 void setStateNumbers( int base );
1370 /* Unset all final states. */
1371 void unsetAllFinStates();
1373 /* Set the bits of final states and clear the bits of non final states. */
1374 void setFinBits( int finStateBits );
1377 * Self-consistency checks.
1380 /* Run a sanity check on the machine. */
1381 void verifyIntegrity();
1383 /* Verify that there are no unreachable states, or dead end states. */
1384 void verifyReachability();
1385 void verifyNoDeadEndStates();
1391 /* Mark all states reachable from state. */
1392 void markReachableFromHereReverse( StateAp *state );
1394 /* Mark all states reachable from state. */
1395 void markReachableFromHere( StateAp *state );
1396 void markReachableFromHereStopFinal( StateAp *state );
1398 /* Removes states that cannot be reached by any path in the fsm and are
1399 * thus wasted silicon. */
1400 void removeDeadEndStates();
1402 /* Removes states that cannot be reached by any path in the fsm and are
1403 * thus wasted silicon. */
1404 void removeUnreachableStates();
1406 /* Remove error actions from states on which the error transition will
1407 * never be taken. */
1408 bool outListCovers( StateAp *state );
1409 bool anyErrorRange( StateAp *state );
1411 /* Remove states that are on the misfit list. */
1412 void removeMisfits();
1418 /* Minimization by partitioning. */
1419 void minimizePartition1();
1420 void minimizePartition2();
1422 /* Minimize the final state Machine. The result is the minimal fsm. Slow
1423 * but stable, correct minimization. Uses n^2 space (lookout) and average
1424 * n^2 time. Worst case n^3 time, but a that is a very rare case. */
1425 void minimizeStable();
1427 /* Minimize the final state machine. Does not find the minimal fsm, but a
1428 * pretty good approximation. Does not use any extra space. Average n^2
1429 * time. Worst case n^3 time, but a that is a very rare case. */
1430 void minimizeApproximate();
1432 /* This is the worker for the minimize approximate solution. It merges
1433 * states that have identical out transitions. */
1434 bool minimizeRound( );
1436 /* Given an intial partioning of states, split partitions that have out trans
1437 * to differing partitions. */
1438 int partitionRound( StateAp **statePtrs, MinPartition *parts, int numParts );
1440 /* Split partitions that have a transition to a previously split partition, until
1441 * there are no more partitions to split. */
1442 int splitCandidates( StateAp **statePtrs, MinPartition *parts, int numParts );
1444 /* Fuse together states in the same partition. */
1445 void fusePartitions( MinPartition *parts, int numParts );
1447 /* Mark pairs where out final stateness differs, out trans data differs,
1448 * trans pairs go to a marked pair or trans data differs. Should get
1450 void initialMarkRound( MarkIndex &markIndex );
1452 /* One marking round on all state pairs. Considers if trans pairs go
1453 * to a marked state only. Returns whether or not a pair was marked. */
1454 bool markRound( MarkIndex &markIndex );
1456 /* Move the in trans into src into dest. */
1457 void inTransMove(StateAp *dest, StateAp *src);
1459 /* Make state src and dest the same state. */
1460 void fuseEquivStates(StateAp *dest, StateAp *src);
1462 /* Find any states that didn't get marked by the marking algorithm and
1463 * merge them into the primary states of their equivalence class. */
1464 void fuseUnmarkedPairs( MarkIndex &markIndex );
1466 /* Merge neighboring transitions go to the same state and have the same
1467 * transitions data. */
1468 void compressTransitions();
1470 /* Returns true if there is a transtion (either explicit or by a gap) to
1471 * the error state. */
1472 bool checkErrTrans( StateAp *state, TransAp *trans );
1473 bool checkErrTransFinish( StateAp *state );
1474 bool hasErrorTrans();
1476 /* Check if a machine defines a single character. This is useful in
1477 * validating ranges and machines to export. */
1478 bool checkSingleCharMachine( );
1482 #endif /* _FSMGRAPH_H */