path: root/contrib/tools/ragel6/redfsm.h

/* 
 *  Copyright 2001-2006 Adrian Thurston <thurston@complang.org> 
 */ 
 
/*  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 <assert.h> 
#include <string.h> 
#include <string> 
#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<GenInlineItem> { }; 
 
/* Element in list of actions. Contains the string for the code to exectute. */ 
struct GenAction  
: 
	public DListEl<GenAction> 
{ 
	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<int> > 
{ 
	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<RedStateAp*> RedStateSet; 
typedef BstSet<int> IntSet; 
 
/* Reduced action. */ 
struct RedAction 
: 
	public AvlTreeEl<RedAction> 
{ 
	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<RedAction, GenActionTable, CmpGenActionTable> GenActionTableMap; 
 
/* Reduced transition. */ 
struct RedTransAp 
: 
	public AvlTreeEl<RedTransAp> 
{ 
	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<RedTransAp, CmpRedTransAp> 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<RedTransEl> RedTransList; 
typedef Vector<RedStateAp*> RedStateVect; 
 
typedef BstMapEl<RedStateAp*, unsigned long long> RedSpanMapEl; 
typedef BstMap<RedStateAp*, unsigned long long> 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<RedSpanMapEl, CmpRedSpanMapEl> RedSpanMapSort; 
 
/* Set of entry ids that go into this state. */ 
typedef Vector<int> EntryIdVect; 
typedef Vector<char*> EntryNameVect; 
 
typedef Vector< GenAction* > GenCondSet; 
 
struct Condition 
{ 
	Condition( ) 
		: key(0), baseKey(0) {} 
 
	Key key; 
	Key baseKey; 
	GenCondSet condSet; 
 
	Condition *next, *prev; 
}; 
typedef DList<Condition> ConditionList; 
 
struct GenCondSpace 
{ 
	Key baseKey; 
	GenCondSet condSet; 
	int condSpaceId; 
 
	GenCondSpace *next, *prev; 
}; 
typedef DList<GenCondSpace> CondSpaceList; 
 
struct GenStateCond 
{ 
	Key lowKey; 
	Key highKey; 
 
	GenCondSpace *condSpace; 
 
	GenStateCond *prev, *next; 
}; 
typedef DList<GenStateCond> GenStateCondList; 
typedef Vector<GenStateCond*> 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<RedStateAp> RedStateList; 
 
/* Set of reduced transitons. Comparison is by pointer. */ 
typedef BstSet< RedTransAp*, CmpOrd<RedTransAp*> > 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