/* * Copyright 2001-2006 Adrian Thurston */ /* This file is part of Ragel. * * Ragel is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * Ragel is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with Ragel; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */ #ifndef _REDFSM_H #define _REDFSM_H #include #include #include #include "config.h" #include "common.h" #include "vector.h" #include "dlist.h" #include "compare.h" #include "bstmap.h" #include "bstset.h" #include "avlmap.h" #include "avltree.h" #include "avlbasic.h" #include "mergesort.h" #include "sbstmap.h" #include "sbstset.h" #include "sbsttable.h" #define TRANS_ERR_TRANS 0 #define STATE_ERR_STATE 0 #define FUNC_NO_FUNC 0 using std::string; struct RedStateAp; struct GenInlineList; struct GenAction; /* * Inline code tree */ struct GenInlineItem { enum Type { Text, Goto, Call, Next, GotoExpr, CallExpr, NextExpr, Ret, PChar, Char, Hold, Exec, Curs, Targs, Entry, LmSwitch, LmSetActId, LmSetTokEnd, LmGetTokEnd, LmInitTokStart, LmInitAct, LmSetTokStart, SubAction, Break }; GenInlineItem( const InputLoc &loc, Type type ) : loc(loc), data(0), targId(0), targState(0), lmId(0), children(0), offset(0), type(type) { } InputLoc loc; char *data; int targId; RedStateAp *targState; int lmId; GenInlineList *children; int offset; Type type; GenInlineItem *prev, *next; }; /* Normally this would be atypedef, but that would entail including DList from * ptreetypes, which should be just typedef forwards. */ struct GenInlineList : public DList { }; /* Element in list of actions. Contains the string for the code to exectute. */ struct GenAction : public DListEl { GenAction( ) : name(0), inlineList(0), actionId(0), numTransRefs(0), numToStateRefs(0), numFromStateRefs(0), numEofRefs(0) { } /* Data collected during parse. */ InputLoc loc; const char *name; GenInlineList *inlineList; int actionId; string nameOrLoc(); /* Number of references in the final machine. */ int numRefs() { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; } int numTransRefs; int numToStateRefs; int numFromStateRefs; int numEofRefs; }; /* Forwards. */ struct RedStateAp; struct StateAp; /* Transistion GenAction Element. */ typedef SBstMapEl< int, GenAction* > GenActionTableEl; /* Transition GenAction Table. */ struct GenActionTable : public SBstMap< int, GenAction*, CmpOrd > { void setAction( int ordering, GenAction *action ); void setActions( int *orderings, GenAction **actions, int nActs ); void setActions( const GenActionTable &other ); }; /* Compare of a whole action table element (key & value). */ struct CmpGenActionTableEl { static int compare( const GenActionTableEl &action1, const GenActionTableEl &action2 ) { if ( action1.key < action2.key ) return -1; else if ( action1.key > action2.key ) return 1; else if ( action1.value < action2.value ) return -1; else if ( action1.value > action2.value ) return 1; return 0; } }; /* Compare for GenActionTable. */ typedef CmpSTable< GenActionTableEl, CmpGenActionTableEl > CmpGenActionTable; /* Set of states. */ typedef BstSet RedStateSet; typedef BstSet IntSet; /* Reduced action. */ struct RedAction : public AvlTreeEl { RedAction( ) : key(), eofRefs(0), numTransRefs(0), numToStateRefs(0), numFromStateRefs(0), numEofRefs(0), bAnyNextStmt(false), bAnyCurStateRef(false), bAnyBreakStmt(false) { } const GenActionTable &getKey() { return key; } GenActionTable key; int actListId; int location; IntSet *eofRefs; /* Number of references in the final machine. */ int numRefs() { return numTransRefs + numToStateRefs + numFromStateRefs + numEofRefs; } int numTransRefs; int numToStateRefs; int numFromStateRefs; int numEofRefs; bool anyNextStmt() { return bAnyNextStmt; } bool anyCurStateRef() { return bAnyCurStateRef; } bool anyBreakStmt() { return bAnyBreakStmt; } bool bAnyNextStmt; bool bAnyCurStateRef; bool bAnyBreakStmt; }; typedef AvlTree GenActionTableMap; /* Reduced transition. */ struct RedTransAp : public AvlTreeEl { RedTransAp( RedStateAp *targ, RedAction *action, int id ) : targ(targ), action(action), id(id), pos(-1), labelNeeded(true) { } RedStateAp *targ; RedAction *action; int id; int pos; bool partitionBoundary; bool labelNeeded; }; /* Compare of transitions for the final reduction of transitions. Comparison * is on target and the pointer to the shared action table. It is assumed that * when this is used the action tables have been reduced. */ struct CmpRedTransAp { static int compare( const RedTransAp &t1, const RedTransAp &t2 ) { if ( t1.targ < t2.targ ) return -1; else if ( t1.targ > t2.targ ) return 1; else if ( t1.action < t2.action ) return -1; else if ( t1.action > t2.action ) return 1; else return 0; } }; typedef AvlBasic TransApSet; /* Element in out range. */ struct RedTransEl { /* Constructors. */ RedTransEl( Key lowKey, Key highKey, RedTransAp *value ) : lowKey(lowKey), highKey(highKey), value(value) { } Key lowKey, highKey; RedTransAp *value; }; typedef Vector RedTransList; typedef Vector RedStateVect; typedef BstMapEl RedSpanMapEl; typedef BstMap RedSpanMap; /* Compare used by span map sort. Reverse sorts by the span. */ struct CmpRedSpanMapEl { static int compare( const RedSpanMapEl &smel1, const RedSpanMapEl &smel2 ) { if ( smel1.value > smel2.value ) return -1; else if ( smel1.value < smel2.value ) return 1; else return 0; } }; /* Sorting state-span map entries by span. */ typedef MergeSort RedSpanMapSort; /* Set of entry ids that go into this state. */ typedef Vector EntryIdVect; typedef Vector EntryNameVect; typedef Vector< GenAction* > GenCondSet; struct Condition { Condition( ) : key(0), baseKey(0) {} Key key; Key baseKey; GenCondSet condSet; Condition *next, *prev; }; typedef DList ConditionList; struct GenCondSpace { Key baseKey; GenCondSet condSet; int condSpaceId; GenCondSpace *next, *prev; }; typedef DList CondSpaceList; struct GenStateCond { Key lowKey; Key highKey; GenCondSpace *condSpace; GenStateCond *prev, *next; }; typedef DList GenStateCondList; typedef Vector StateCondVect; /* Reduced state. */ struct RedStateAp { RedStateAp() : defTrans(0), condList(0), transList(0), isFinal(false), labelNeeded(false), outNeeded(false), onStateList(false), toStateAction(0), fromStateAction(0), eofAction(0), eofTrans(0), id(0), bAnyRegCurStateRef(false), partitionBoundary(false), inTrans(0), numInTrans(0) { } /* Transitions out. */ RedTransList outSingle; RedTransList outRange; RedTransAp *defTrans; /* For flat conditions. */ Key condLowKey, condHighKey; GenCondSpace **condList; /* For flat keys. */ Key lowKey, highKey; RedTransAp **transList; /* The list of states that transitions from this state go to. */ RedStateVect targStates; bool isFinal; bool labelNeeded; bool outNeeded; bool onStateList; RedAction *toStateAction; RedAction *fromStateAction; RedAction *eofAction; RedTransAp *eofTrans; int id; GenStateCondList stateCondList; StateCondVect stateCondVect; /* Pointers for the list of states. */ RedStateAp *prev, *next; bool anyRegCurStateRef() { return bAnyRegCurStateRef; } bool bAnyRegCurStateRef; int partition; bool partitionBoundary; RedTransAp **inTrans; int numInTrans; }; /* List of states. */ typedef DList RedStateList; /* Set of reduced transitons. Comparison is by pointer. */ typedef BstSet< RedTransAp*, CmpOrd > RedTransSet; /* Next version of the fsm machine. */ struct RedFsmAp { RedFsmAp(); bool forcedErrorState; int nextActionId; int nextTransId; /* Next State Id doubles as the total number of state ids. */ int nextStateId; TransApSet transSet; GenActionTableMap actionMap; RedStateList stateList; RedStateSet entryPoints; RedStateAp *startState; RedStateAp *errState; RedTransAp *errTrans; RedTransAp *errActionTrans; RedStateAp *firstFinState; int numFinStates; int nParts; bool bAnyToStateActions; bool bAnyFromStateActions; bool bAnyRegActions; bool bAnyEofActions; bool bAnyEofTrans; bool bAnyActionGotos; bool bAnyActionCalls; bool bAnyActionRets; bool bAnyActionByValControl; bool bAnyRegActionRets; bool bAnyRegActionByValControl; bool bAnyRegNextStmt; bool bAnyRegCurStateRef; bool bAnyRegBreak; bool bAnyConditions; int maxState; int maxSingleLen; int maxRangeLen; int maxKeyOffset; int maxIndexOffset; int maxIndex; int maxActListId; int maxActionLoc; int maxActArrItem; unsigned long long maxSpan; unsigned long long maxCondSpan; int maxFlatIndexOffset; Key maxKey; int maxCondOffset; int maxCondLen; int maxCondSpaceId; int maxCondIndexOffset; int maxCond; bool anyActions(); bool anyToStateActions() { return bAnyToStateActions; } bool anyFromStateActions() { return bAnyFromStateActions; } bool anyRegActions() { return bAnyRegActions; } bool anyEofActions() { return bAnyEofActions; } bool anyEofTrans() { return bAnyEofTrans; } bool anyActionGotos() { return bAnyActionGotos; } bool anyActionCalls() { return bAnyActionCalls; } bool anyActionRets() { return bAnyActionRets; } bool anyActionByValControl() { return bAnyActionByValControl; } bool anyRegActionRets() { return bAnyRegActionRets; } bool anyRegActionByValControl() { return bAnyRegActionByValControl; } bool anyRegNextStmt() { return bAnyRegNextStmt; } bool anyRegCurStateRef() { return bAnyRegCurStateRef; } bool anyRegBreak() { return bAnyRegBreak; } bool anyConditions() { return bAnyConditions; } /* Is is it possible to extend a range by bumping ranges that span only * one character to the singles array. */ bool canExtend( const RedTransList &list, int pos ); /* Pick single transitions from the ranges. */ void moveTransToSingle( RedStateAp *state ); void chooseSingle(); void makeFlat(); /* Move a selected transition from ranges to default. */ void moveToDefault( RedTransAp *defTrans, RedStateAp *state ); /* Pick a default transition by largest span. */ RedTransAp *chooseDefaultSpan( RedStateAp *state ); void chooseDefaultSpan(); /* Pick a default transition by most number of ranges. */ RedTransAp *chooseDefaultNumRanges( RedStateAp *state ); void chooseDefaultNumRanges(); /* Pick a default transition tailored towards goto driven machine. */ RedTransAp *chooseDefaultGoto( RedStateAp *state ); void chooseDefaultGoto(); /* Ordering states by transition connections. */ void optimizeStateOrdering( RedStateAp *state ); void optimizeStateOrdering(); /* Ordering states by transition connections. */ void depthFirstOrdering( RedStateAp *state ); void depthFirstOrdering(); /* Set state ids. */ void sequentialStateIds(); void sortStateIdsByFinal(); /* Arrange states in by final id. This is a stable sort. */ void sortStatesByFinal(); /* Sorting states by id. */ void sortByStateId(); /* Locating the first final state. This is the final state with the lowest * id. */ void findFirstFinState(); void assignActionLocs(); RedTransAp *getErrorTrans(); RedStateAp *getErrorState(); /* Is every char in the alphabet covered? */ bool alphabetCovered( RedTransList &outRange ); RedTransAp *allocateTrans( RedStateAp *targState, RedAction *actionTable ); void partitionFsm( int nParts ); void setInTrans(); }; #endif