ragel-6.9ragel-6.9

1 files changed, 530 insertions, 0 deletions

diff --git a/ragel/redfsm.h b/ragel/redfsm.h
new file mode 100644
index 0000000..2e7ad7c
--- /dev/null
+++ b/ragel/redfsm.h
@@ -0,0 +1,530 @@
+/*
+ *  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 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 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