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
38 #include "sbsttable.h"
45 /* Flags that control merging. */
46 #define SB_GRAPH1 0x01
47 #define SB_GRAPH2 0x02
49 #define SB_ISFINAL 0x04
50 #define SB_ISMARKED 0x08
51 #define SB_ONLIST 0x10
59 struct LongestMatchPart;
61 /* State list element for unambiguous access to list element. */
67 /* This is the marked index for a state pair. Used in minimization. It keeps
68 * track of whether or not the state pair is marked. */
71 MarkIndex(int states);
74 void markPair(int state1, int state2);
75 bool isPairMarked(int state1, int state2);
82 extern KeyOps *keyOps;
84 /* Transistion Action Element. */
85 typedef SBstMapEl< int, Action* > ActionTableEl;
87 /* Nodes in the tree that use this action. */
90 typedef Vector<NameInst*> ActionRefs;
92 /* Element in list of actions. Contains the string for the code to exectute. */
95 public DListEl<Action>,
96 public AvlTreeEl<Action>
100 Action( const InputLoc &loc, char *name, InlineList *inlineList, int condId )
104 inlineList(inlineList),
117 /* Key for action dictionary. */
118 char *getKey() const { return name; }
120 /* Data collected during parse. */
123 InlineList *inlineList;
126 void actionName( ostream &out )
131 out << loc.line << ":" << loc.col;
134 /* Places in the input text that reference the action. */
135 ActionRefs actionRefs;
137 /* Number of references in the final machine. */
139 { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; }
142 int numFromStateRefs;
153 static inline int compare( const Action *cond1, const Action *cond2 )
155 if ( cond1->condId < cond2->condId )
157 else if ( cond1->condId > cond2->condId )
163 /* A list of actions. */
164 typedef DList<Action> ActionList;
165 typedef AvlTree<Action, char *, CmpStr> ActionDict;
167 /* Structure for reverse action mapping. */
168 struct RevActionMapEl
175 /* Transition Action Table. */
177 : public SBstMap< int, Action*, CmpOrd<int> >
179 void setAction( int ordering, Action *action );
180 void setActions( int *orderings, Action **actions, int nActs );
181 void setActions( const ActionTable &other );
183 bool hasAction( Action *action );
186 typedef SBstSet< Action*, CmpOrd<Action*> > ActionSet;
187 typedef CmpSTable< Action*, CmpOrd<Action*> > CmpActionSet;
189 /* Transistion Action Element. */
190 typedef SBstMapEl< int, LongestMatchPart* > LmActionTableEl;
192 /* Transition Action Table. */
194 : public SBstMap< int, LongestMatchPart*, CmpOrd<int> >
196 void setAction( int ordering, LongestMatchPart *action );
197 void setActions( const LmActionTable &other );
200 /* Compare of a whole action table element (key & value). */
201 struct CmpActionTableEl
203 static int compare( const ActionTableEl &action1,
204 const ActionTableEl &action2 )
206 if ( action1.key < action2.key )
208 else if ( action1.key > action2.key )
210 else if ( action1.value < action2.value )
212 else if ( action1.value > action2.value )
218 /* Compare for ActionTable. */
219 typedef CmpSTable< ActionTableEl, CmpActionTableEl > CmpActionTable;
221 /* Compare of a whole lm action table element (key & value). */
222 struct CmpLmActionTableEl
224 static int compare( const LmActionTableEl &lmAction1,
225 const LmActionTableEl &lmAction2 )
227 if ( lmAction1.key < lmAction2.key )
229 else if ( lmAction1.key > lmAction2.key )
231 else if ( lmAction1.value < lmAction2.value )
233 else if ( lmAction1.value > lmAction2.value )
239 /* Compare for ActionTable. */
240 typedef CmpSTable< LmActionTableEl, CmpLmActionTableEl > CmpLmActionTable;
242 /* Action table element for error action tables. Adds the encoding of transfer
244 struct ErrActionTableEl
246 ErrActionTableEl( Action *action, int ordering, int transferPoint )
247 : ordering(ordering), action(action), transferPoint(transferPoint) { }
249 /* Ordering and id of the action embedding. */
253 /* Id of point of transfere from Error action table to transtions and
257 int getKey() const { return ordering; }
260 struct ErrActionTable
261 : public SBstTable< ErrActionTableEl, int, CmpOrd<int> >
263 void setAction( int ordering, Action *action, int transferPoint );
264 void setActions( const ErrActionTable &other );
267 /* Compare of an error action table element (key & value). */
268 struct CmpErrActionTableEl
270 static int compare( const ErrActionTableEl &action1,
271 const ErrActionTableEl &action2 )
273 if ( action1.ordering < action2.ordering )
275 else if ( action1.ordering > action2.ordering )
277 else if ( action1.action < action2.action )
279 else if ( action1.action > action2.action )
281 else if ( action1.transferPoint < action2.transferPoint )
283 else if ( action1.transferPoint > action2.transferPoint )
289 /* Compare for ErrActionTable. */
290 typedef CmpSTable< ErrActionTableEl, CmpErrActionTableEl > CmpErrActionTable;
293 /* Descibe a priority, shared among PriorEls.
294 * Has key and whether or not used. */
301 /* Element in the arrays of priorities for transitions and arrays. Ordering is
302 * unique among instantiations of machines, desc is shared. */
305 PriorEl( int ordering, PriorDesc *desc )
306 : ordering(ordering), desc(desc) { }
312 /* Compare priority elements, which are ordered by the priority descriptor
316 static inline int compare( const PriorEl &pel1, const PriorEl &pel2 )
318 if ( pel1.desc->key < pel2.desc->key )
320 else if ( pel1.desc->key > pel2.desc->key )
328 /* Priority Table. */
330 : public SBstSet< PriorEl, PriorElCmp >
332 void setPrior( int ordering, PriorDesc *desc );
333 void setPriors( const PriorTable &other );
336 /* Compare of prior table elements for distinguising state data. */
339 static inline int compare( const PriorEl &pel1, const PriorEl &pel2 )
341 if ( pel1.desc < pel2.desc )
343 else if ( pel1.desc > pel2.desc )
345 else if ( pel1.ordering < pel2.ordering )
347 else if ( pel1.ordering > pel2.ordering )
353 /* Compare of PriorTable distinguising state data. Using a compare of the
354 * pointers is a little more strict than it needs be. It requires that
355 * prioritiy tables have the exact same set of priority assignment operators
356 * (from the input lang) to be considered equal.
358 * Really only key-value pairs need be tested and ordering be merged. However
359 * this would require that in the fuseing of states, priority descriptors be
360 * chosen for the new fused state based on priority. Since the out transition
361 * lists and ranges aren't necessarily going to line up, this is more work for
362 * little gain. Final compression resets all priorities first, so this would
363 * only be useful for compression at every operator, which is only an
364 * undocumented test feature.
366 typedef CmpSTable<PriorEl, CmpPriorEl> CmpPriorTable;
368 /* Plain action list that imposes no ordering. */
369 typedef Vector<int> TransFuncList;
371 /* Comparison for TransFuncList. */
372 typedef CmpTable< int, CmpOrd<int> > TransFuncListCompare;
374 /* Transition class that implements actions and priorities. */
377 TransAp() : fromState(0), toState(0) {}
378 TransAp( const TransAp &other ) :
379 lowKey(other.lowKey),
380 highKey(other.highKey),
381 fromState(0), toState(0),
382 actionTable(other.actionTable),
383 priorTable(other.priorTable)
385 assert( lmActionTable.length() == 0 && other.lmActionTable.length() == 0 );
392 /* Pointers for outlist. */
393 TransAp *prev, *next;
395 /* Pointers for in-list. */
396 TransAp *ilprev, *ilnext;
398 /* The function table and priority for the transition. */
399 ActionTable actionTable;
400 PriorTable priorTable;
402 LmActionTable lmActionTable;
405 /* In transition list. Like DList except only has head pointers, which is all
406 * that is required. Insertion and deletion is handled by the graph. This
407 * class provides the iterator of a single list. */
410 TransInList() : head(0) { }
416 /* Default construct. */
419 /* Construct, assign from a list. */
420 Iter( const TransInList &il ) : ptr(il.head) { }
421 Iter &operator=( const TransInList &dl ) { ptr = dl.head; return *this; }
424 bool lte() const { return ptr != 0; }
425 bool end() const { return ptr == 0; }
427 /* At the first, last element. */
428 bool first() const { return ptr && ptr->ilprev == 0; }
429 bool last() const { return ptr && ptr->ilnext == 0; }
431 /* Cast, dereference, arrow ops. */
432 operator TransAp*() const { return ptr; }
433 TransAp &operator *() const { return *ptr; }
434 TransAp *operator->() const { return ptr; }
436 /* Increment, decrement. */
437 inline void operator++(int) { ptr = ptr->ilnext; }
438 inline void operator--(int) { ptr = ptr->ilprev; }
440 /* The iterator is simply a pointer. */
445 typedef DList<TransAp> TransList;
447 /* Set of states, list of states. */
448 typedef BstSet<StateAp*> StateSet;
449 typedef DList<StateAp> StateList;
451 /* A element in a state dict. */
454 public AvlTreeEl<StateDictEl>
456 StateDictEl(const StateSet &stateSet)
457 : stateSet(stateSet) { }
459 const StateSet &getKey() { return stateSet; }
464 /* Dictionary mapping a set of states to a target state. */
465 typedef AvlTree< StateDictEl, StateSet, CmpTable<StateAp*> > StateDict;
467 /* Data needed for a merge operation. */
471 : stfillHead(0), stfillTail(0) { }
478 void fillListAppend( StateAp *state );
485 TransEl( Key lowKey, Key highKey )
486 : lowKey(lowKey), highKey(highKey) { }
487 TransEl( Key lowKey, Key highKey, TransAp *value )
488 : lowKey(lowKey), highKey(highKey), value(value) { }
496 static int compare( const Key key1, const Key key2 )
500 else if ( key1 > key2 )
507 /* Vector based set of key items. */
508 typedef BstSet<Key, CmpKey> KeySet;
512 MinPartition() : active(false) { }
517 MinPartition *prev, *next;
520 /* Epsilon transition stored in a state. Specifies the target */
521 typedef Vector<int> EpsilonTrans;
523 /* List of states that are to be drawn into this. */
526 EptVectEl( StateAp *targ, bool leaving )
527 : targ(targ), leaving(leaving) { }
532 typedef Vector<EptVectEl> EptVect;
534 /* Set of entry ids that go into this state. */
535 typedef BstSet<int> EntryIdSet;
537 /* Set of longest match items that may be active in a given state. */
538 typedef BstSet<LongestMatchPart*> LmItemSet;
540 /* A Conditions which is to be
541 * transfered on pending out transitions. */
544 OutCond( Action *action, bool sense )
545 : action(action), sense(sense) {}
553 static int compare( const OutCond &outCond1, const OutCond &outCond2 )
555 if ( outCond1.action < outCond2.action )
557 else if ( outCond1.action > outCond2.action )
559 else if ( outCond1.sense < outCond2.sense )
561 else if ( outCond1.sense > outCond2.sense )
567 /* Set of conditions to be transfered to on pending out transitions. */
568 typedef SBstSet< OutCond, CmpOutCond > OutCondSet;
569 typedef CmpSTable< OutCond, CmpOutCond > CmpOutCondSet;
572 typedef BstSet< Action*, CmpCondId > CondSet;
573 typedef CmpTable< Action*, CmpCondId > CmpCondSet;
576 : public AvlTreeEl<CondSpace>
578 CondSpace( const CondSet &condSet )
579 : condSet(condSet) {}
581 const CondSet &getKey() { return condSet; }
588 typedef Vector<CondSpace*> CondSpaceVect;
590 typedef AvlTree<CondSpace, CondSet, CmpCondSet> CondSpaceMap;
594 StateCond( Key lowKey, Key highKey ) :
595 lowKey(lowKey), highKey(highKey) {}
599 CondSpace *condSpace;
601 StateCond *prev, *next;
604 typedef DList<StateCond> StateCondList;
605 typedef Vector<long> LongVect;
609 Expansion( Key lowKey, Key highKey ) :
610 lowKey(lowKey), highKey(highKey),
611 fromTrans(0), fromCondSpace(0),
616 if ( fromTrans != 0 )
624 CondSpace *fromCondSpace;
627 CondSpace *toCondSpace;
630 Expansion *prev, *next;
633 typedef DList<Expansion> ExpansionList;
645 CondData() : lastCondKey(0) {}
647 /* Condition info. */
650 CondSpaceMap condSpaceMap;
653 extern CondData *condData;
655 struct FsmConstructFail
662 FsmConstructFail( Reason reason )
667 /* State class that implements actions and priorities. */
671 StateAp(const StateAp &other);
674 /* Is the state final? */
675 bool isFinState() { return stateBits & SB_ISFINAL; }
677 /* Out transition list and the pointer for the default out trans. */
680 /* In transition Lists. */
683 /* Entry points into the state. */
686 /* Epsilon transitions. */
687 EpsilonTrans epsilonTrans;
689 /* Condition info. */
690 StateCondList stateCondList;
692 /* Number of in transitions from states other than ourselves. */
695 /* Temporary data for various algorithms. */
697 /* When duplicating the fsm we need to map each
698 * state to the new state representing it. */
701 /* When minimizing machines by partitioning, this maps to the group
702 * the state is in. */
703 MinPartition *partition;
705 /* When merging states (state machine operations) this next pointer is
706 * used for the list of states that need to be filled in. */
709 /* Identification for printing and stable minimization. */
714 /* Data used in epsilon operation, maybe fit into alg? */
715 StateAp *isolatedShadow;
718 /* A pointer to a dict element that contains the set of states this state
719 * represents. This cannot go into alg, because alg.next is used during
720 * the merging process. */
721 StateDictEl *stateDictEl;
723 /* When drawing epsilon transitions, holds the list of states to merge
727 /* Bits controlling the behaviour of the state during collapsing to dfa. */
730 /* State list elements. */
731 StateAp *next, *prev;
734 * Priority and Action data.
737 /* Out priorities transfered to out transitions. */
738 PriorTable outPriorTable;
740 /* The following two action tables are distinguished by the fact that when
741 * toState actions are executed immediatly after transition actions of
742 * incoming transitions and the current character will be the same as the
743 * one available then. The fromState actions are executed immediately
744 * before the transition actions of outgoing transitions and the current
745 * character is same as the one available then. */
747 /* Actions to execute upon entering into a state. */
748 ActionTable toStateActionTable;
750 /* Actions to execute when going from the state to the transition. */
751 ActionTable fromStateActionTable;
753 /* Actions to add to any future transitions that leave via this state. */
754 ActionTable outActionTable;
756 /* Conditions to add to any future transiions that leave via this sttate. */
757 OutCondSet outCondSet;
759 /* Error action tables. */
760 ErrActionTable errActionTable;
762 /* Actions to execute on eof. */
763 ActionTable eofActionTable;
765 /* Set of longest match items that may be active in this state. */
769 template <class ListItem> struct NextTrans
780 lowKey = trans->lowKey;
781 highKey = trans->highKey;
785 void set( ListItem *t ) {
797 /* Encodes the different states that are meaningful to the of the iterator. */
798 enum PairIterUserState
800 RangeInS1, RangeInS2,
805 template <class ListItem1, class ListItem2 = ListItem1> struct PairIter
807 /* Encodes the different states that an fsm iterator can be in. */
810 ConsumeS1Range, ConsumeS2Range,
811 OnlyInS1Range, OnlyInS2Range,
812 S1SticksOut, S1SticksOutBreak,
813 S2SticksOut, S2SticksOutBreak,
814 S1DragsBehind, S1DragsBehindBreak,
815 S2DragsBehind, S2DragsBehindBreak,
819 PairIter( ListItem1 *list1, ListItem2 *list2 );
821 /* Query iterator. */
822 bool lte() { return itState != End; }
823 bool end() { return itState == End; }
824 void operator++(int) { findNext(); }
825 void operator++() { findNext(); }
827 /* Iterator state. */
831 PairIterUserState userState;
833 NextTrans<ListItem1> s1Tel;
834 NextTrans<ListItem2> s2Tel;
835 Key bottomLow, bottomHigh;
836 ListItem1 *bottomTrans1;
837 ListItem2 *bottomTrans2;
843 /* Init the iterator by advancing to the first item. */
844 template <class ListItem1, class ListItem2> PairIter<ListItem1, ListItem2>::PairIter(
845 ListItem1 *list1, ListItem2 *list2 )
854 /* Return and re-entry for the co-routine iterators. This should ALWAYS be
855 * used inside of a block. */
856 #define CO_RETURN(label) \
859 entry##label: backIn = true
861 /* Return and re-entry for the co-routine iterators. This should ALWAYS be
862 * used inside of a block. */
863 #define CO_RETURN2(label, uState) \
865 userState = uState; \
867 entry##label: backIn = true
869 /* Advance to the next transition. When returns, trans points to the next
870 * transition, unless there are no more, in which case end() returns true. */
871 template <class ListItem1, class ListItem2> void PairIter<ListItem1, ListItem2>::findNext()
873 /* This variable is used in dummy statements that follow the entry
874 * goto labels. The compiler needs some statement to follow the label. */
877 /* Jump into the iterator routine base on the iterator state. */
879 case Begin: goto entryBegin;
880 case ConsumeS1Range: goto entryConsumeS1Range;
881 case ConsumeS2Range: goto entryConsumeS2Range;
882 case OnlyInS1Range: goto entryOnlyInS1Range;
883 case OnlyInS2Range: goto entryOnlyInS2Range;
884 case S1SticksOut: goto entryS1SticksOut;
885 case S1SticksOutBreak: goto entryS1SticksOutBreak;
886 case S2SticksOut: goto entryS2SticksOut;
887 case S2SticksOutBreak: goto entryS2SticksOutBreak;
888 case S1DragsBehind: goto entryS1DragsBehind;
889 case S1DragsBehindBreak: goto entryS1DragsBehindBreak;
890 case S2DragsBehind: goto entryS2DragsBehind;
891 case S2DragsBehindBreak: goto entryS2DragsBehindBreak;
892 case ExactOverlap: goto entryExactOverlap;
893 case End: goto entryEnd;
897 /* Set up the next structs at the head of the transition lists. */
901 /* Concurrently scan both out ranges. */
903 if ( s1Tel.trans == 0 ) {
904 /* We are at the end of state1's ranges. Process the rest of
905 * state2's ranges. */
906 while ( s2Tel.trans != 0 ) {
907 /* Range is only in s2. */
908 CO_RETURN2( ConsumeS2Range, RangeInS2 );
913 else if ( s2Tel.trans == 0 ) {
914 /* We are at the end of state2's ranges. Process the rest of
915 * state1's ranges. */
916 while ( s1Tel.trans != 0 ) {
917 /* Range is only in s1. */
918 CO_RETURN2( ConsumeS1Range, RangeInS1 );
923 /* Both state1's and state2's transition elements are good.
924 * The signiture of no overlap is a back key being in front of a
926 else if ( s1Tel.highKey < s2Tel.lowKey ) {
927 /* A range exists in state1 that does not overlap with state2. */
928 CO_RETURN2( OnlyInS1Range, RangeInS1 );
931 else if ( s2Tel.highKey < s1Tel.lowKey ) {
932 /* A range exists in state2 that does not overlap with state1. */
933 CO_RETURN2( OnlyInS2Range, RangeInS2 );
936 /* There is overlap, must mix the ranges in some way. */
937 else if ( s1Tel.lowKey < s2Tel.lowKey ) {
938 /* Range from state1 sticks out front. Must break it into
939 * non-overlaping and overlaping segments. */
940 bottomLow = s2Tel.lowKey;
941 bottomHigh = s1Tel.highKey;
942 s1Tel.highKey = s2Tel.lowKey;
943 s1Tel.highKey.decrement();
944 bottomTrans1 = s1Tel.trans;
946 /* Notify the caller that we are breaking s1. This gives them a
947 * chance to duplicate s1Tel[0,1].value. */
948 CO_RETURN2( S1SticksOutBreak, BreakS1 );
950 /* Broken off range is only in s1. */
951 CO_RETURN2( S1SticksOut, RangeInS1 );
953 /* Advance over the part sticking out front. */
954 s1Tel.lowKey = bottomLow;
955 s1Tel.highKey = bottomHigh;
956 s1Tel.trans = bottomTrans1;
958 else if ( s2Tel.lowKey < s1Tel.lowKey ) {
959 /* Range from state2 sticks out front. Must break it into
960 * non-overlaping and overlaping segments. */
961 bottomLow = s1Tel.lowKey;
962 bottomHigh = s2Tel.highKey;
963 s2Tel.highKey = s1Tel.lowKey;
964 s2Tel.highKey.decrement();
965 bottomTrans2 = s2Tel.trans;
967 /* Notify the caller that we are breaking s2. This gives them a
968 * chance to duplicate s2Tel[0,1].value. */
969 CO_RETURN2( S2SticksOutBreak, BreakS2 );
971 /* Broken off range is only in s2. */
972 CO_RETURN2( S2SticksOut, RangeInS2 );
974 /* Advance over the part sticking out front. */
975 s2Tel.lowKey = bottomLow;
976 s2Tel.highKey = bottomHigh;
977 s2Tel.trans = bottomTrans2;
979 /* Low ends are even. Are the high ends even? */
980 else if ( s1Tel.highKey < s2Tel.highKey ) {
981 /* Range from state2 goes longer than the range from state1. We
982 * must break the range from state2 into an evenly overlaping
984 bottomLow = s1Tel.highKey;
985 bottomLow.increment();
986 bottomHigh = s2Tel.highKey;
987 s2Tel.highKey = s1Tel.highKey;
988 bottomTrans2 = s2Tel.trans;
990 /* Notify the caller that we are breaking s2. This gives them a
991 * chance to duplicate s2Tel[0,1].value. */
992 CO_RETURN2( S2DragsBehindBreak, BreakS2 );
994 /* Breaking s2 produces exact overlap. */
995 CO_RETURN2( S2DragsBehind, RangeOverlap );
997 /* Advance over the front we just broke off of range 2. */
998 s2Tel.lowKey = bottomLow;
999 s2Tel.highKey = bottomHigh;
1000 s2Tel.trans = bottomTrans2;
1002 /* Advance over the entire s1Tel. We have consumed it. */
1005 else if ( s2Tel.highKey < s1Tel.highKey ) {
1006 /* Range from state1 goes longer than the range from state2. We
1007 * must break the range from state1 into an evenly overlaping
1009 bottomLow = s2Tel.highKey;
1010 bottomLow.increment();
1011 bottomHigh = s1Tel.highKey;
1012 s1Tel.highKey = s2Tel.highKey;
1013 bottomTrans1 = s1Tel.trans;
1015 /* Notify the caller that we are breaking s1. This gives them a
1016 * chance to duplicate s2Tel[0,1].value. */
1017 CO_RETURN2( S1DragsBehindBreak, BreakS1 );
1019 /* Breaking s1 produces exact overlap. */
1020 CO_RETURN2( S1DragsBehind, RangeOverlap );
1022 /* Advance over the front we just broke off of range 1. */
1023 s1Tel.lowKey = bottomLow;
1024 s1Tel.highKey = bottomHigh;
1025 s1Tel.trans = bottomTrans1;
1027 /* Advance over the entire s2Tel. We have consumed it. */
1031 /* There is an exact overlap. */
1032 CO_RETURN2( ExactOverlap, RangeOverlap );
1039 /* Done, go into end state. */
1044 /* Compare lists of epsilon transitions. Entries are name ids of targets. */
1045 typedef CmpTable< int, CmpOrd<int> > CmpEpsilonTrans;
1047 /* Compare class for the Approximate minimization. */
1052 int compare( const StateAp *pState1, const StateAp *pState2 );
1055 /* Compare class for the initial partitioning of a partition minimization. */
1056 class InitPartitionCompare
1059 InitPartitionCompare() { }
1060 int compare( const StateAp *pState1, const StateAp *pState2 );
1063 /* Compare class for the regular partitioning of a partition minimization. */
1064 class PartitionCompare
1067 PartitionCompare() { }
1068 int compare( const StateAp *pState1, const StateAp *pState2 );
1071 /* Compare class for a minimization that marks pairs. Provides the shouldMark
1077 bool shouldMark( MarkIndex &markIndex, const StateAp *pState1,
1078 const StateAp *pState2 );
1081 /* List of partitions. */
1082 typedef DList< MinPartition > PartitionList;
1084 /* List of transtions out of a state. */
1085 typedef Vector<TransEl> TransListVect;
1087 /* Entry point map used for keeping track of entry points in a machine. */
1088 typedef BstSet< int > EntryIdSet;
1089 typedef BstMapEl< int, StateAp* > EntryMapEl;
1090 typedef BstMap< int, StateAp* > EntryMap;
1091 typedef Vector<EntryMapEl> EntryMapBase;
1093 /* Graph class that implements actions and priorities. */
1096 /* Constructors/Destructors. */
1098 FsmAp( const FsmAp &graph );
1101 /* The list of states. */
1102 StateList stateList;
1103 StateList misfitList;
1105 /* The map of entry points. */
1106 EntryMap entryPoints;
1108 /* The start state. */
1109 StateAp *startState;
1111 /* Error state, possibly created only when the final machine has been
1112 * created and the XML machine is about to be written. No transitions
1113 * point to this state. */
1116 /* The set of final states. */
1117 StateSet finStateSet;
1119 /* Misfit Accounting. Are misfits put on a separate list. */
1120 bool misfitAccounting;
1123 * Transition actions and priorities.
1126 /* Set priorities on transtions. */
1127 void startFsmPrior( int ordering, PriorDesc *prior );
1128 void allTransPrior( int ordering, PriorDesc *prior );
1129 void finishFsmPrior( int ordering, PriorDesc *prior );
1130 void leaveFsmPrior( int ordering, PriorDesc *prior );
1132 /* Action setting support. */
1133 void transferErrorActions( StateAp *state, int transferPoint );
1134 void setErrorAction( StateAp *state, int ordering, Action *action );
1136 /* Fill all spaces in a transition list with an error transition. */
1137 void fillGaps( StateAp *state );
1139 /* Similar to setErrorAction, instead gives a state to go to on error. */
1140 void setErrorTarget( StateAp *state, StateAp *target, int *orderings,
1141 Action **actions, int nActs );
1143 /* Set actions to execute. */
1144 void startFsmAction( int ordering, Action *action );
1145 void allTransAction( int ordering, Action *action );
1146 void finishFsmAction( int ordering, Action *action );
1147 void leaveFsmAction( int ordering, Action *action );
1148 void longMatchAction( int ordering, LongestMatchPart *lmPart );
1150 /* Set conditions. */
1151 CondSpace *addCondSpace( const CondSet &condSet );
1153 void findEmbedExpansions( ExpansionList &expansionList,
1154 StateAp *destState, Action *condAction, bool sense );
1155 void embedCondition( MergeData &md, StateAp *state, Action *condAction, bool sense );
1156 void embedCondition( StateAp *state, Action *condAction, bool sense );
1158 void startFsmCondition( Action *condAction, bool sense );
1159 void allTransCondition( Action *condAction, bool sense );
1160 void leaveFsmCondition( Action *condAction, bool sense );
1162 /* Set error actions to execute. */
1163 void startErrorAction( int ordering, Action *action, int transferPoint );
1164 void allErrorAction( int ordering, Action *action, int transferPoint );
1165 void finalErrorAction( int ordering, Action *action, int transferPoint );
1166 void notStartErrorAction( int ordering, Action *action, int transferPoint );
1167 void notFinalErrorAction( int ordering, Action *action, int transferPoint );
1168 void middleErrorAction( int ordering, Action *action, int transferPoint );
1170 /* Set EOF actions. */
1171 void startEOFAction( int ordering, Action *action );
1172 void allEOFAction( int ordering, Action *action );
1173 void finalEOFAction( int ordering, Action *action );
1174 void notStartEOFAction( int ordering, Action *action );
1175 void notFinalEOFAction( int ordering, Action *action );
1176 void middleEOFAction( int ordering, Action *action );
1178 /* Set To State actions. */
1179 void startToStateAction( int ordering, Action *action );
1180 void allToStateAction( int ordering, Action *action );
1181 void finalToStateAction( int ordering, Action *action );
1182 void notStartToStateAction( int ordering, Action *action );
1183 void notFinalToStateAction( int ordering, Action *action );
1184 void middleToStateAction( int ordering, Action *action );
1186 /* Set From State actions. */
1187 void startFromStateAction( int ordering, Action *action );
1188 void allFromStateAction( int ordering, Action *action );
1189 void finalFromStateAction( int ordering, Action *action );
1190 void notStartFromStateAction( int ordering, Action *action );
1191 void notFinalFromStateAction( int ordering, Action *action );
1192 void middleFromStateAction( int ordering, Action *action );
1194 /* Shift the action ordering of the start transitions to start at
1195 * fromOrder and increase in units of 1. Useful before kleene star
1197 int shiftStartActionOrder( int fromOrder );
1199 /* Clear all priorities from the fsm to so they won't affcet minimization
1200 * of the final fsm. */
1201 void clearAllPriorities();
1203 /* Zero out all the function keys. */
1204 void nullActionKeys();
1206 /* Walk the list of states and verify state properties. */
1207 void verifyStates();
1209 /* Misfit Accounting. Are misfits put on a separate list. */
1210 void setMisfitAccounting( bool val )
1211 { misfitAccounting = val; }
1213 /* Set and Unset a state as final. */
1214 void setFinState( StateAp *state );
1215 void unsetFinState( StateAp *state );
1217 void setStartState( StateAp *state );
1218 void unsetStartState( );
1220 /* Set and unset a state as an entry point. */
1221 void setEntry( int id, StateAp *state );
1222 void changeEntry( int id, StateAp *to, StateAp *from );
1223 void unsetEntry( int id, StateAp *state );
1224 void unsetEntry( int id );
1225 void unsetAllEntryPoints();
1227 /* Epsilon transitions. */
1228 void epsilonTrans( int id );
1229 void shadowReadWriteStates( MergeData &md );
1232 * Basic attaching and detaching.
1235 /* Common to attaching/detaching list and default. */
1236 void attachToInList( StateAp *from, StateAp *to, TransAp *&head, TransAp *trans );
1237 void detachFromInList( StateAp *from, StateAp *to, TransAp *&head, TransAp *trans );
1239 /* Attach with a new transition. */
1240 TransAp *attachNewTrans( StateAp *from, StateAp *to,
1241 Key onChar1, Key onChar2 );
1243 /* Attach with an existing transition that already in an out list. */
1244 void attachTrans( StateAp *from, StateAp *to, TransAp *trans );
1246 /* Redirect a transition away from error and towards some state. */
1247 void redirectErrorTrans( StateAp *from, StateAp *to, TransAp *trans );
1249 /* Detach a transition from a target state. */
1250 void detachTrans( StateAp *from, StateAp *to, TransAp *trans );
1252 /* Detach a state from the graph. */
1253 void detachState( StateAp *state );
1256 * NFA to DFA conversion routines.
1259 /* Duplicate a transition that will dropin to a free spot. */
1260 TransAp *dupTrans( StateAp *from, TransAp *srcTrans );
1262 /* In crossing, two transitions both go to real states. */
1263 TransAp *fsmAttachStates( MergeData &md, StateAp *from,
1264 TransAp *destTrans, TransAp *srcTrans );
1266 /* Two transitions are to be crossed, handle the possibility of either
1267 * going to the error state. */
1268 TransAp *mergeTrans( MergeData &md, StateAp *from,
1269 TransAp *destTrans, TransAp *srcTrans );
1271 /* Compare deterimne relative priorities of two transition tables. */
1272 int comparePrior( const PriorTable &priorTable1, const PriorTable &priorTable2 );
1274 /* Cross a src transition with one that is already occupying a spot. */
1275 TransAp *crossTransitions( MergeData &md, StateAp *from,
1276 TransAp *destTrans, TransAp *srcTrans );
1278 void outTransCopy( MergeData &md, StateAp *dest, TransAp *srcList );
1280 void doRemove( MergeData &md, StateAp *destState, ExpansionList &expList1 );
1281 void doExpand( MergeData &md, StateAp *destState, ExpansionList &expList1 );
1282 void findCondExpInTrans( ExpansionList &expansionList, StateAp *state,
1283 Key lowKey, Key highKey, CondSpace *fromCondSpace, CondSpace *toCondSpace,
1284 long destVals, LongVect &toValsList );
1285 void findTransExpansions( ExpansionList &expansionList,
1286 StateAp *destState, StateAp *srcState );
1287 void findCondExpansions( ExpansionList &expansionList,
1288 StateAp *destState, StateAp *srcState );
1289 void mergeStateConds( StateAp *destState, StateAp *srcState );
1291 /* Merge a set of states into newState. */
1292 void mergeStates( MergeData &md, StateAp *destState,
1293 StateAp **srcStates, int numSrc );
1294 void mergeStatesLeaving( MergeData &md, StateAp *destState, StateAp *srcState );
1295 void mergeStates( MergeData &md, StateAp *destState, StateAp *srcState );
1297 /* Make all states that are combinations of other states and that
1298 * have not yet had their out transitions filled in. This will
1299 * empty out stateDict and stFil. */
1300 void fillInStates( MergeData &md );
1303 * Transition Comparison.
1306 /* Compare transition data. Either of the pointers may be null. */
1307 static inline int compareDataPtr( TransAp *trans1, TransAp *trans2 );
1309 /* Compare target state and transition data. Either pointer may be null. */
1310 static inline int compareFullPtr( TransAp *trans1, TransAp *trans2 );
1312 /* Compare target partitions. Either pointer may be null. */
1313 static inline int comparePartPtr( TransAp *trans1, TransAp *trans2 );
1315 /* Check marked status of target states. Either pointer may be null. */
1316 static inline bool shouldMarkPtr( MarkIndex &markIndex,
1317 TransAp *trans1, TransAp *trans2 );
1323 /* Compare priority and function table of transitions. */
1324 static int compareTransData( TransAp *trans1, TransAp *trans2 );
1326 /* Add in the properties of srcTrans into this. */
1327 void addInTrans( TransAp *destTrans, TransAp *srcTrans );
1329 /* Compare states on data stored in the states. */
1330 static int compareStateData( const StateAp *state1, const StateAp *state2 );
1332 /* Out transition data. */
1333 void clearOutData( StateAp *state );
1334 bool hasOutData( StateAp *state );
1335 void transferOutData( StateAp *destState, StateAp *srcState );
1341 /* New up a state and add it to the graph. */
1342 StateAp *addState();
1345 * Building basic machines
1348 void concatFsm( Key c );
1349 void concatFsm( Key *str, int len );
1350 void concatFsmCI( Key *str, int len );
1351 void orFsm( Key *set, int len );
1352 void rangeFsm( Key low, Key high );
1353 void rangeStarFsm( Key low, Key high );
1362 void repeatOp( int times );
1363 void optionalRepeatOp( int times );
1364 void concatOp( FsmAp *other );
1365 void unionOp( FsmAp *other );
1366 void intersectOp( FsmAp *other );
1367 void subtractOp( FsmAp *other );
1369 void joinOp( int startId, int finalId, FsmAp **others, int numOthers );
1370 void globOp( FsmAp **others, int numOthers );
1371 void deterministicEntry();
1377 /* Determine if there are any entry points into a start state other than
1378 * the start state. */
1379 bool isStartStateIsolated();
1381 /* Make a new start state that has no entry points. Will not change the
1382 * identity of the fsm. */
1383 void isolateStartState();
1385 /* Workers for resolving epsilon transitions. */
1386 bool inEptVect( EptVect *eptVect, StateAp *targ );
1387 void epsilonFillEptVectFrom( StateAp *root, StateAp *from, bool parentLeaving );
1388 void resolveEpsilonTrans( MergeData &md );
1390 /* Workers for concatenation and union. */
1391 void doConcat( FsmAp *other, StateSet *fromStates, bool optional );
1392 void doOr( FsmAp *other );
1398 /* Unset any final states that are no longer to be final
1399 * due to final bits. */
1400 void unsetIncompleteFinals();
1401 void unsetKilledFinals();
1403 /* Bring in other's entry points. Assumes others states are going to be
1404 * copied into this machine. */
1405 void copyInEntryPoints( FsmAp *other );
1407 /* Ordering states. */
1408 void depthFirstOrdering( StateAp *state );
1409 void depthFirstOrdering();
1410 void sortStatesByFinal();
1412 /* Set sqequential state numbers starting at 0. */
1413 void setStateNumbers( int base );
1415 /* Unset all final states. */
1416 void unsetAllFinStates();
1418 /* Set the bits of final states and clear the bits of non final states. */
1419 void setFinBits( int finStateBits );
1422 * Self-consistency checks.
1425 /* Run a sanity check on the machine. */
1426 void verifyIntegrity();
1428 /* Verify that there are no unreachable states, or dead end states. */
1429 void verifyReachability();
1430 void verifyNoDeadEndStates();
1436 /* Mark all states reachable from state. */
1437 void markReachableFromHereReverse( StateAp *state );
1439 /* Mark all states reachable from state. */
1440 void markReachableFromHere( StateAp *state );
1441 void markReachableFromHereStopFinal( StateAp *state );
1443 /* Removes states that cannot be reached by any path in the fsm and are
1444 * thus wasted silicon. */
1445 void removeDeadEndStates();
1447 /* Removes states that cannot be reached by any path in the fsm and are
1448 * thus wasted silicon. */
1449 void removeUnreachableStates();
1451 /* Remove error actions from states on which the error transition will
1452 * never be taken. */
1453 bool outListCovers( StateAp *state );
1454 bool anyErrorRange( StateAp *state );
1456 /* Remove states that are on the misfit list. */
1457 void removeMisfits();
1463 /* Minimization by partitioning. */
1464 void minimizePartition1();
1465 void minimizePartition2();
1467 /* Minimize the final state Machine. The result is the minimal fsm. Slow
1468 * but stable, correct minimization. Uses n^2 space (lookout) and average
1469 * n^2 time. Worst case n^3 time, but a that is a very rare case. */
1470 void minimizeStable();
1472 /* Minimize the final state machine. Does not find the minimal fsm, but a
1473 * pretty good approximation. Does not use any extra space. Average n^2
1474 * time. Worst case n^3 time, but a that is a very rare case. */
1475 void minimizeApproximate();
1477 /* This is the worker for the minimize approximate solution. It merges
1478 * states that have identical out transitions. */
1479 bool minimizeRound( );
1481 /* Given an intial partioning of states, split partitions that have out trans
1482 * to differing partitions. */
1483 int partitionRound( StateAp **statePtrs, MinPartition *parts, int numParts );
1485 /* Split partitions that have a transition to a previously split partition, until
1486 * there are no more partitions to split. */
1487 int splitCandidates( StateAp **statePtrs, MinPartition *parts, int numParts );
1489 /* Fuse together states in the same partition. */
1490 void fusePartitions( MinPartition *parts, int numParts );
1492 /* Mark pairs where out final stateness differs, out trans data differs,
1493 * trans pairs go to a marked pair or trans data differs. Should get
1495 void initialMarkRound( MarkIndex &markIndex );
1497 /* One marking round on all state pairs. Considers if trans pairs go
1498 * to a marked state only. Returns whether or not a pair was marked. */
1499 bool markRound( MarkIndex &markIndex );
1501 /* Move the in trans into src into dest. */
1502 void inTransMove(StateAp *dest, StateAp *src);
1504 /* Make state src and dest the same state. */
1505 void fuseEquivStates(StateAp *dest, StateAp *src);
1507 /* Find any states that didn't get marked by the marking algorithm and
1508 * merge them into the primary states of their equivalence class. */
1509 void fuseUnmarkedPairs( MarkIndex &markIndex );
1511 /* Merge neighboring transitions go to the same state and have the same
1512 * transitions data. */
1513 void compressTransitions();
1515 /* Returns true if there is a transtion (either explicit or by a gap) to
1516 * the error state. */
1517 bool checkErrTrans( StateAp *state, TransAp *trans );
1518 bool checkErrTransFinish( StateAp *state );
1519 bool hasErrorTrans();
1521 /* Check if a machine defines a single character. This is useful in
1522 * validating ranges and machines to export. */
1523 bool checkSingleCharMachine( );
1527 #endif /* _FSMGRAPH_H */