"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