path: root/ragel/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 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