path: root/rlcodegen/redfsm.cpp

/*
 *  Copyright 2001-2006 Adrian Thurston <thurston@cs.queensu.ca>
 */

/*  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 
 */

#include "redfsm.h"
#include "avlmap.h"
#include <iostream>
#include <sstream>

using std::ostringstream;

KeyOps *keyOps = 0;

string Action::nameOrLoc()
{
	if ( name != 0 )
		return string(name);
	else {
		ostringstream ret;
		ret << loc.line << ":" << loc.col;
		return ret.str();
	}
}

RedFsmAp::RedFsmAp()
:
	wantComplete(false),
	forcedErrorState(false),
	nextActionId(0),
	nextTransId(0),
	errState(0),
	errTrans(0),
	firstFinState(0),
	numFinStates(0)
{
}

void RedFsmAp::depthFirstOrdering( RedStateAp *state )
{
	/* Nothing to do if the state is already on the list. */
	if ( state->onStateList )
		return;

	/* Doing depth first, put state on the list. */
	state->onStateList = true;
	stateList.append( state );
	
	/* At this point transitions should only be in ranges. */
	assert( state->outSingle.length() == 0 );
	assert( state->defTrans == 0 );

	/* Recurse on everything ranges. */
	for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
		if ( rtel->value->targ != 0 )
			depthFirstOrdering( rtel->value->targ );
	}
}

/* Ordering states by transition connections. */
void RedFsmAp::depthFirstOrdering()
{
	/* Init on state list flags. */
	for ( RedStateList::Iter st = stateList; st.lte(); st++ )
		st->onStateList = false;
	
	/* Clear out the state list, we will rebuild it. */
	int stateListLen = stateList.length();
	stateList.abandon();

	/* Add back to the state list from the start state and all other entry
	 * points. */
	depthFirstOrdering( startState );
	for ( RedStateSet::Iter en = entryPoints; en.lte(); en++ )
		depthFirstOrdering( *en );
	if ( forcedErrorState )
		depthFirstOrdering( errState );
	
	/* Make sure we put everything back on. */
	assert( stateListLen == stateList.length() );
}

/* Assign state ids by appearance in the state list. */
void RedFsmAp::sequentialStateIds()
{
	/* Table based machines depend on the state numbers starting at zero. */
	nextStateId = 0;
	for ( RedStateList::Iter st = stateList; st.lte(); st++ )
		st->id = nextStateId++;
}

/* Stable sort the states by final state status. */
void RedFsmAp::sortStatesByFinal()
{
	/* Move forward through the list and throw final states onto the end. */
	RedStateAp *state = 0;
	RedStateAp *next = stateList.head;
	RedStateAp *last = stateList.tail;
	while ( state != last ) {
		/* Move forward and load up the next. */
		state = next;
		next = state->next;

		/* Throw to the end? */
		if ( state->isFinal ) {
			stateList.detach( state );
			stateList.append( state );
		}
	}
}

/* Assign state ids by final state state status. */
void RedFsmAp::sortStateIdsByFinal()
{
	/* Table based machines depend on this starting at zero. */
	nextStateId = 0;

	/* First pass to assign non final ids. */
	for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
		if ( ! st->isFinal ) 
			st->id = nextStateId++;
	}

	/* Second pass to assign final ids. */
	for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
		if ( st->isFinal ) 
			st->id = nextStateId++;
	}
}

/* Find the final state with the lowest id. */
void RedFsmAp::findFirstFinState()
{
	for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
		if ( st->isFinal && (firstFinState == 0 || st->id < firstFinState->id) )
			firstFinState = st;
	}
}

void RedFsmAp::assignActionLocs()
{
	int nextLocation = 0;
	for ( ActionTableMap::Iter act = actionMap; act.lte(); act++ ) {
		/* Store the loc, skip over the array and a null terminator. */
		act->location = nextLocation;
		nextLocation += act->key.length() + 1;		
	}
}

/* Check if we can extend the current range by displacing any ranges
 * ahead to the singles. */
bool RedFsmAp::canExtend( const RedTransList &list, int pos )
{
	/* Get the transition that we want to extend. */
	RedTransAp *extendTrans = list[pos].value;

	/* Look ahead in the transition list. */
	for ( int next = pos + 1; next < list.length(); pos++, next++ ) {
		/* If they are not continuous then cannot extend. */
		Key nextKey = list[next].lowKey;
		nextKey.decrement();
		if ( list[pos].highKey != nextKey )
			break;

		/* Check for the extenstion property. */
		if ( extendTrans == list[next].value )
			return true;

		/* If the span of the next element is more than one, then don't keep
		 * checking, it won't be moved to single. */
		unsigned long long nextSpan = keyOps->span( list[next].lowKey, list[next].highKey );
		if ( nextSpan > 1 )
			break;
	}
	return false;
}

/* Move ranges to the singles list. */
void RedFsmAp::moveTransToSingle( RedStateAp *state )
{
	RedTransList &range = state->outRange;
	RedTransList &single = state->outSingle;
	for ( int rpos = 0; rpos < range.length(); ) {
		/* Check if this is a range we can extend. */
		if ( canExtend( range, rpos ) ) {
			/* Transfer singles over. */
			while ( range[rpos].value != range[rpos+1].value ) {
				/* Transfer the range to single. */
				single.append( range[rpos+1] );
				range.remove( rpos+1 );
			}
			
			/* Extend. */
			range[rpos].highKey = range[rpos+1].highKey;
			range.remove( rpos+1 );
		}
		/* Maybe move it to the singles. */
		else if ( keyOps->span( range[rpos].lowKey, range[rpos].highKey ) == 1 ) {
			single.append( range[rpos] );
			range.remove( rpos );
		}
		else {
			/* Keeping it in the ranges. */
			rpos += 1;
		}
	}
}

/* Look through ranges and choose suitable single character transitions. */
void RedFsmAp::chooseSingle()
{
	/* Loop the states. */
	for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
		/* Rewrite the transition list taking out the suitable single
		 * transtions. */
		moveTransToSingle( st );
	}
}

void RedFsmAp::makeFlat()
{
	for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
		if ( st->stateCondList.length() == 0 ) {
			st->condLowKey = 0;
			st->condHighKey = 0;
		}
		else {
			st->condLowKey = st->stateCondList.head->lowKey;
			st->condHighKey = st->stateCondList.tail->highKey;

			unsigned long long span = keyOps->span( st->condLowKey, st->condHighKey );
			st->condList = new CondSpace*[ span ];
			memset( st->condList, 0, sizeof(CondSpace*)*span );

			for ( StateCondList::Iter sci = st->stateCondList; sci.lte(); sci++ ) {
				unsigned long long base, trSpan;
				base = keyOps->span( st->condLowKey, sci->lowKey )-1;
				trSpan = keyOps->span( sci->lowKey, sci->highKey );
				for ( unsigned long long pos = 0; pos < trSpan; pos++ )
					st->condList[base+pos] = sci->condSpace;
			}
		}

		if ( st->outRange.length() == 0 ) {
			st->lowKey = st->highKey = 0;
			st->transList = 0;
		}
		else {
			st->lowKey = st->outRange[0].lowKey;
			st->highKey = st->outRange[st->outRange.length()-1].highKey;
			unsigned long long span = keyOps->span( st->lowKey, st->highKey );
			st->transList = new RedTransAp*[ span ];
			memset( st->transList, 0, sizeof(RedTransAp*)*span );
			
			for ( RedTransList::Iter trans = st->outRange; trans.lte(); trans++ ) {
				unsigned long long base, trSpan;
				base = keyOps->span( st->lowKey, trans->lowKey )-1;
				trSpan = keyOps->span( trans->lowKey, trans->highKey );
				for ( unsigned long long pos = 0; pos < trSpan; pos++ )
					st->transList[base+pos] = trans->value;
			}

			/* Fill in the gaps with the default transition. */
			for ( unsigned long long pos = 0; pos < span; pos++ ) {
				if ( st->transList[pos] == 0 )
					st->transList[pos] = st->defTrans;
			}
		}
	}
}


/* A default transition has been picked, move it from the outRange to the
 * default pointer. */
void RedFsmAp::moveToDefault( RedTransAp *defTrans, RedStateAp *state )
{
	/* Rewrite the outRange, omitting any ranges that use 
	 * the picked default. */
	RedTransList outRange;
	for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
		/* If it does not take the default, copy it over. */
		if ( rtel->value != defTrans )
			outRange.append( *rtel );
	}

	/* Save off the range we just created into the state's range. */
	state->outRange.shallowCopy( outRange );
	outRange.abandon();

	/* Store the default. */
	state->defTrans = defTrans;
}

bool RedFsmAp::alphabetCovered( RedTransList &outRange )
{
	/* Cannot cover without any out ranges. */
	if ( outRange.length() == 0 )
		return false;

	/* If the first range doesn't start at the the lower bound then the
	 * alphabet is not covered. */
	RedTransList::Iter rtel = outRange;
	if ( keyOps->minKey < rtel->lowKey )
		return false;

	/* Check that every range is next to the previous one. */
	rtel.increment();
	for ( ; rtel.lte(); rtel++ ) {
		Key highKey = rtel[-1].highKey;
		highKey.increment();
		if ( highKey != rtel->lowKey )
			return false;
	}

	/* The last must extend to the upper bound. */
	RedTransEl *last = &outRange[outRange.length()-1];
	if ( last->highKey < keyOps->maxKey )
		return false;

	return true;
}

RedTransAp *RedFsmAp::chooseDefaultSpan( RedStateAp *state )
{
	/* Make a set of transitions from the outRange. */
	RedTransSet stateTransSet;
	for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ )
		stateTransSet.insert( rtel->value );
	
	/* For each transition in the find how many alphabet characters the
	 * transition spans. */
	unsigned long long *span = new unsigned long long[stateTransSet.length()];
	memset( span, 0, sizeof(unsigned long long) * stateTransSet.length() );
	for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
		/* Lookup the transition in the set. */
		RedTransAp **inSet = stateTransSet.find( rtel->value );
		int pos = inSet - stateTransSet.data;
		span[pos] += keyOps->span( rtel->lowKey, rtel->highKey );
	}

	/* Find the max span, choose it for making the default. */
	RedTransAp *maxTrans = 0;
	unsigned long long maxSpan = 0;
	for ( RedTransSet::Iter rtel = stateTransSet; rtel.lte(); rtel++ ) {
		if ( span[rtel.pos()] > maxSpan ) {
			maxSpan = span[rtel.pos()];
			maxTrans = *rtel;
		}
	}

	delete[] span;
	return maxTrans;
}

/* Pick default transitions from ranges for the states. */
void RedFsmAp::chooseDefaultSpan()
{
	/* Loop the states. */
	for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
		/* Only pick a default transition if the alphabet is covered. This
		 * avoids any transitions in the out range that go to error and avoids
		 * the need for an ERR state. */
		if ( alphabetCovered( st->outRange ) ) {
			/* Pick a default transition by largest span. */
			RedTransAp *defTrans = chooseDefaultSpan( st );

			/* Rewrite the transition list taking out the transition we picked
			 * as the default and store the default. */
			moveToDefault( defTrans, st );
		}
	}
}

RedTransAp *RedFsmAp::chooseDefaultGoto( RedStateAp *state )
{
	/* Make a set of transitions from the outRange. */
	RedTransSet stateTransSet;
	for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
		if ( rtel->value->targ == state->next )
			return rtel->value;
	}
	return 0;
}

void RedFsmAp::chooseDefaultGoto()
{
	/* Loop the states. */
	for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
		/* Pick a default transition. */
		RedTransAp *defTrans = chooseDefaultGoto( st );
		if ( defTrans == 0 )
			defTrans = chooseDefaultSpan( st );

		/* Rewrite the transition list taking out the transition we picked
		 * as the default and store the default. */
		moveToDefault( defTrans, st );
	}
}

RedTransAp *RedFsmAp::chooseDefaultNumRanges( RedStateAp *state )
{
	/* Make a set of transitions from the outRange. */
	RedTransSet stateTransSet;
	for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ )
		stateTransSet.insert( rtel->value );
	
	/* For each transition in the find how many ranges use the transition. */
	int *numRanges = new int[stateTransSet.length()];
	memset( numRanges, 0, sizeof(int) * stateTransSet.length() );
	for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
		/* Lookup the transition in the set. */
		RedTransAp **inSet = stateTransSet.find( rtel->value );
		numRanges[inSet - stateTransSet.data] += 1;
	}

	/* Find the max number of ranges. */
	RedTransAp *maxTrans = 0;
	int maxNumRanges = 0;
	for ( RedTransSet::Iter rtel = stateTransSet; rtel.lte(); rtel++ ) {
		if ( numRanges[rtel.pos()] > maxNumRanges ) {
			maxNumRanges = numRanges[rtel.pos()];
			maxTrans = *rtel;
		}
	}

	delete[] numRanges;
	return maxTrans;
}

void RedFsmAp::chooseDefaultNumRanges()
{
	/* Loop the states. */
	for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
		/* Pick a default transition. */
		RedTransAp *defTrans = chooseDefaultNumRanges( st );

		/* Rewrite the transition list taking out the transition we picked
		 * as the default and store the default. */
		moveToDefault( defTrans, st );
	}
}

RedTransAp *RedFsmAp::getErrorTrans( )
{
	/* If the error trans has not been made aready, make it. */
	if ( errTrans == 0 ) {
		/* This insert should always succeed since no transition created by
		 * the user can point to the error state. */
		errTrans = new RedTransAp( getErrorState(), 0, nextTransId++ );
		RedTransAp *inRes = transSet.insert( errTrans );
		assert( inRes != 0 );
	}
	return errTrans;
}

RedStateAp *RedFsmAp::getErrorState()
{
	/* Check if we need to init the error trans. */
	if ( errState == 0 ) {
		errState = new RedStateAp();
		stateList.append( errState );
	}
	return errState;
}


RedTransAp *RedFsmAp::allocateTrans( RedStateAp *targ, RedAction *action )
{
	/* Create a reduced trans and look for it in the transiton set. */
	RedTransAp redTrans( targ, action, 0 );
	RedTransAp *inDict = transSet.find( &redTrans );
	if ( inDict == 0 ) {
		inDict = new RedTransAp( targ, action, nextTransId++ );
		transSet.insert( inDict );
	}
	return inDict;
}

void RedFsmAp::partitionFsm( int nparts )
{
	/* At this point the states are ordered by a depth-first traversal. We
	 * will allocate to partitions based on this ordering. */
	this->nParts = nparts;
	int partSize = stateList.length() / nparts;
	int remainder = stateList.length() % nparts;
	int numInPart = partSize;
	int partition = 0;
	if ( remainder-- > 0 )
		numInPart += 1;
	for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
		st->partition = partition;

		numInPart -= 1;
		if ( numInPart == 0 ) {
			partition += 1;
			numInPart = partSize;
			if ( remainder-- > 0 )
				numInPart += 1;
		}
	}
}

void RedFsmAp::setInTrans()
{
	/* First pass counts the number of transitions. */
	for ( TransApSet::Iter trans = transSet; trans.lte(); trans++ )
		trans->targ->numInTrans += 1;

	/* Pass over states to allocate the needed memory. Reset the counts so we
	 * can use them as the current size. */
	for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
		st->inTrans = new RedTransAp*[st->numInTrans];
		st->numInTrans = 0;
	}

	/* Second pass over transitions copies pointers into the in trans list. */
	for ( TransApSet::Iter trans = transSet; trans.lte(); trans++ )
		trans->targ->inTrans[trans->targ->numInTrans++] = trans;
}