1 files changed, 533 insertions, 0 deletions
diff --git a/src/pdagraph.cc b/src/pdagraph.cc
new file mode 100644
index 0000000..8f17b7a
--- /dev/null
+++ b/src/pdagraph.cc
@@ -0,0 +1,533 @@
+/*
+ *  Copyright 2006-2012 Adrian Thurston <thurston@complang.org>
+ */
+
+/*  This file is part of Colm.
+ *
+ *  Colm 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.
+ * 
+ *  Colm 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 Colm; if not, write to the Free Software
+ *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
+ */
+
+#include <string.h>
+#include <iostream>
+#include <string.h>
+#include <assert.h>
+#include "global.h"
+#include "pdagraph.h"
+#include "mergesort.h"
+
+using std::cerr;
+using std::endl;
+
+/* Create a new fsm state. State has not out transitions or in transitions, not
+ * out out transition data and not number. */
+PdaState::PdaState()
+:
+	/* No in transitions. */
+	inRange(),
+
+	/* No entry points, or epsilon trans. */
+	pendingCommits(),
+
+	stateSet(0),
+
+	/* Only used during merging. Normally null. */
+	stateDictEl(0),
+
+	/* No state identification bits. */
+	stateBits(0),
+
+	onClosureQueue(false),
+	inClosedMap(false),
+	followMarked(false),
+
+	advanceReductions(false)
+{
+}
+
+/* Copy everything except the action transitions. That is left up to the
+ * PdaGraph copy constructor. */
+PdaState::PdaState(const PdaState &other)
+:
+	inRange(),
+
+	/* Duplicate the entry id set, epsilon transitions and context sets. These
+	 * are sets of integers and as such need no fixing. */
+	pendingCommits(other.pendingCommits),
+
+	stateSet(0),
+
+	/* This is only used during merging. Normally null. */
+	stateDictEl(0),
+
+	/* Fsm state data. */
+	stateBits(other.stateBits),
+
+	dotSet(other.dotSet),
+	onClosureQueue(false),
+	inClosedMap(false),
+	followMarked(false),
+
+	transMap()
+{
+	/* Duplicate all the transitions. */
+	for ( TransMap::Iter trans = other.transMap; trans.lte(); trans++ ) {
+		/* Dupicate and store the orginal target in the transition. This will
+		 * be corrected once all the states have been created. */
+		PdaTrans *newTrans = new PdaTrans(*trans->value);
+		newTrans->toState = trans->value->toState;
+		transMap.append( TransMapEl( newTrans->lowKey, newTrans ) );
+	}
+}
+
+/* If there is a state dict element, then delete it. Everything else is left
+ * up to the FsmGraph destructor. */
+PdaState::~PdaState()
+{
+	if ( stateDictEl != 0 )
+		delete stateDictEl;
+}
+
+/* Graph constructor. */
+PdaGraph::PdaGraph()
+:
+	/* No start state. */
+	startState(0)
+{
+}
+
+/* Copy all graph data including transitions. */
+PdaGraph::PdaGraph( const PdaGraph &graph )
+:
+	/* Lists start empty. Will be filled by copy. */
+	stateList(),
+	misfitList(),
+
+	/* Copy in the entry points, 
+	 * pointers will be resolved later. */
+	startState(graph.startState),
+
+	/* Will be filled by copy. */
+	finStateSet()
+{
+	/* Create the states and record their map in the original state. */
+	PdaStateList::Iter origState = graph.stateList;
+	for ( ; origState.lte(); origState++ ) {
+		/* Make the new state. */
+		PdaState *newState = new PdaState( *origState );
+
+		/* Add the state to the list.  */
+		stateList.append( newState );
+
+		/* Set the mapsTo item of the old state. */
+		origState->stateMap = newState;
+	}
+	
+	/* Derefernce all the state maps. */
+	for ( PdaStateList::Iter state = stateList; state.lte(); state++ ) {
+		for ( TransMap::Iter trans = state->transMap; trans.lte(); trans++ ) {
+			/* The points to the original in the src machine. The taget's duplicate
+			 * is in the statemap. */
+			PdaState *toState = trans->value->toState != 0 ? 
+					trans->value->toState->stateMap : 0;
+
+			/* Attach The transition to the duplicate. */
+			trans->value->toState = 0;
+			attachTrans( state, toState, trans->value );
+		}
+	}
+
+	/* Fix the start state pointer and the new start state's count of in
+	 * transiions. */
+	startState = startState->stateMap;
+
+	/* Build the final state set. */
+	PdaStateSet::Iter st = graph.finStateSet; 
+	for ( ; st.lte(); st++ ) 
+		finStateSet.insert((*st)->stateMap);
+}
+
+/* Deletes all transition data then deletes each state. */
+PdaGraph::~PdaGraph()
+{
+	/* Delete all the transitions. */
+	PdaStateList::Iter state = stateList;
+	for ( ; state.lte(); state++ ) {
+		for ( TransMap::Iter trans = state->transMap; trans.lte(); trans++ )
+			delete trans->value;
+	}
+
+	/* Delete all the states. */
+	stateList.empty();
+}
+
+/* Set a state final. The state has its isFinState set to true and the state
+ * is added to the finStateSet. */
+void PdaGraph::setFinState( PdaState *state )
+{
+	/* Is it already a fin state. */
+	if ( state->stateBits & SB_ISFINAL )
+		return;
+	
+	state->stateBits |= SB_ISFINAL;
+	finStateSet.insert( state );
+}
+
+void PdaGraph::unsetAllFinStates( )
+{
+	for ( PdaStateSet::Iter st = finStateSet; st.lte(); st++ ) {
+		PdaState *state = *st;
+		state->stateBits &= ~ SB_ISFINAL;
+	}
+	finStateSet.empty();
+}
+
+/* Set and unset a state as the start state. */
+void PdaGraph::setStartState( PdaState *state )
+{
+	/* Sould change from unset to set. */
+	assert( startState == 0 );
+	startState = state;
+}
+
+/* Mark all states reachable from state. Traverses transitions forward. Used
+ * for removing states that have no path into them. */
+void PdaGraph::markReachableFromHere( PdaState *state )
+{
+	/* Base case: return; */
+	if ( state->stateBits & SB_ISMARKED )
+		return;
+	
+	/* Set this state as processed. We are going to visit all states that this
+	 * state has a transition to. */
+	state->stateBits |= SB_ISMARKED;
+
+	/* Recurse on all out transitions. */
+	for ( TransMap::Iter trans = state->transMap; trans.lte(); trans++ ) {
+		if ( trans->value->toState != 0 )
+			markReachableFromHere( trans->value->toState );
+	}
+}
+
+void PdaGraph::setStateNumbers()
+{
+	int curNum = 0;
+	PdaStateList::Iter state = stateList;
+	for ( ; state.lte(); state++ )
+		state->stateNum = curNum++;
+}
+
+/* Insert a transition into an inlist. The head must be supplied. */
+void PdaGraph::attachToInList( PdaState *from, PdaState *to, 
+		PdaTrans *&head, PdaTrans *trans )
+{
+	trans->ilnext = head;
+	trans->ilprev = 0;
+
+	/* If in trans list is not empty, set the head->prev to trans. */
+	if ( head != 0 )
+		head->ilprev = trans;
+
+	/* Now insert ourselves at the front of the list. */
+	head = trans;
+};
+
+/* Detach a transition from an inlist. The head of the inlist must be supplied. */
+void PdaGraph::detachFromInList( PdaState *from, PdaState *to, 
+		PdaTrans *&head, PdaTrans *trans )
+{
+	/* Detach in the inTransList. */
+	if ( trans->ilprev == 0 ) 
+		head = trans->ilnext; 
+	else
+		trans->ilprev->ilnext = trans->ilnext; 
+
+	if ( trans->ilnext != 0 )
+		trans->ilnext->ilprev = trans->ilprev; 
+}
+
+/* Attach states on the default transition, range list or on out/in list key.
+ * Type of attaching and is controlled by keyType. First makes a new
+ * transition. If there is already a transition out from fromState on the
+ * default, then will assertion fail. */
+PdaTrans *PdaGraph::appendNewTrans( PdaState *from, PdaState *to, long lowKey, long )
+{
+	/* Make the new transition. */
+	PdaTrans *retVal = new PdaTrans();
+
+	/* The transition is now attached. Remember the parties involved. */
+	retVal->fromState = from;
+	retVal->toState = to;
+
+	/* Make the entry in the out list for the transitions. */
+	from->transMap.append( TransMapEl( lowKey, retVal ) );
+
+	/* Set the the keys of the new trans. */
+	retVal->lowKey = lowKey;
+
+	/* Attach using inRange as the head pointer. */
+	attachToInList( from, to, to->inRange.head, retVal );
+
+	return retVal;
+}
+
+PdaTrans *PdaGraph::insertNewTrans( PdaState *from, PdaState *to, long lowKey, long )
+{
+	/* Make the new transition. */
+	PdaTrans *retVal = new PdaTrans();
+
+	/* The transition is now attached. Remember the parties involved. */
+	retVal->fromState = from;
+	retVal->toState = to;
+
+	/* Make the entry in the out list for the transitions. */
+	from->transMap.insert( lowKey, retVal );
+
+	/* Set the the keys of the new trans. */
+	retVal->lowKey = lowKey;
+
+	/* Attach using inRange as the head pointer. */
+	attachToInList( from, to, to->inRange.head, retVal );
+
+	return retVal;
+}
+
+/* Attach for range lists or for the default transition. Type of attaching is
+ * controlled by the keyType parameter. This attach should be used when a
+ * transition already is allocated and must be attached to a target state.
+ * Does not handle adding the transition into the out list. */
+void PdaGraph::attachTrans( PdaState *from, PdaState *to, PdaTrans *trans )
+{
+	assert( trans->fromState == 0 && trans->toState == 0 );
+	trans->fromState = from;
+	trans->toState = to;
+
+	/* Attach using the inRange pointer as the head pointer. */
+	attachToInList( from, to, to->inRange.head, trans );
+}
+
+/* Detach for out/in lists or for default transition. The type of detaching is
+ * controlled by the keyType parameter. */
+void PdaGraph::detachTrans( PdaState *from, PdaState *to, PdaTrans *trans )
+{
+	assert( trans->fromState == from && trans->toState == to );
+	trans->fromState = 0;
+	trans->toState = 0;
+
+	/* Detach using to's inRange pointer as the head. */
+	detachFromInList( from, to, to->inRange.head, trans );
+}
+
+
+/* Detach a state from the graph. Detaches and deletes transitions in and out
+ * of the state. Empties inList and outList. Removes the state from the final
+ * state set. A detached state becomes useless and should be deleted. */
+void PdaGraph::detachState( PdaState *state )
+{
+	/* Detach the in transitions from the inRange list of transitions. */
+	while ( state->inRange.head != 0 ) {
+		/* Get pointers to the trans and the state. */
+		PdaTrans *trans = state->inRange.head;
+		PdaState *fromState = trans->fromState;
+
+		/* Detach the transitions from the source state. */
+		detachTrans( fromState, state, trans );
+
+		/* Ok to delete the transition. */
+		fromState->transMap.remove( trans->lowKey );
+		delete trans;
+	}
+
+	/* Detach out range transitions. */
+	for ( TransMap::Iter trans = state->transMap; trans.lte(); trans++ ) {
+		detachTrans( state, trans->value->toState, trans->value );
+		delete trans->value;
+	}
+
+	/* Delete all of the out range pointers. */
+	state->transMap.empty();
+
+	/* Unset final stateness before detaching from graph. */
+	if ( state->stateBits & SB_ISFINAL )
+		finStateSet.remove( state );
+}
+
+/* Move all the transitions that go into src so that they go into dest.  */
+void PdaGraph::inTransMove( PdaState *dest, PdaState *src )
+{
+	/* Do not try to move in trans to and from the same state. */
+	assert( dest != src );
+
+	/* If src is the start state, dest becomes the start state. */
+	assert( src != startState );
+
+	/* Move the transitions in inRange. */
+	while ( src->inRange.head != 0 ) {
+		/* Get trans and from state. */
+		PdaTrans *trans = src->inRange.head;
+		PdaState *fromState = trans->fromState;
+
+		/* Detach from src, reattach to dest. */
+		detachTrans( fromState, src, trans );
+		attachTrans( fromState, dest, trans );
+	}
+}
+
+void PdaGraph::addInReduction( PdaTrans *dest, long prodId, long prior )
+{
+	/* Look for the reduction. If not there insert it, otherwise take
+	 * the max of the priorities. */
+	ReductionMapEl *redMapEl = dest->reductions.find( prodId );
+	if ( redMapEl == 0 )
+		dest->reductions.insert( prodId, prior );
+	else if ( prior > redMapEl->value )
+		redMapEl->value = prior;
+}
+
+/* Callback invoked when another trans (or possibly this) is added into this
+ * transition during the merging process.  Draw in any properties of srcTrans
+ * into this transition. AddInTrans is called when a new transitions is made
+ * that will be a duplicate of another transition or a combination of several
+ * other transitions. AddInTrans will be called for each transition that the
+ * new transition is to represent. */
+void PdaGraph::addInTrans( PdaTrans *destTrans, PdaTrans *srcTrans )
+{
+	/* Protect against adding in from ourselves. */
+	if ( srcTrans != destTrans ) {
+
+		/* Add in the shift priority. */
+		if ( destTrans->isShift && srcTrans->isShift ) {
+			/* Both shifts are set. We want the max of the two. */
+			if ( srcTrans->shiftPrior > destTrans->shiftPrior )
+				destTrans->shiftPrior = srcTrans->shiftPrior;
+		}
+		else if ( srcTrans->isShift ) {
+			/* Just the source is set, copy the source prior over. */
+			destTrans->shiftPrior = srcTrans->shiftPrior;
+		}
+
+		/* If either is a shift, dest is a shift. */
+		destTrans->isShift = destTrans->isShift || srcTrans->isShift;
+
+		/* Add in the reductions. */
+		for ( ReductionMap::Iter red = srcTrans->reductions; red.lte(); red++ )
+			addInReduction( destTrans, red->key, red->value );
+
+		/* Add in the commit points. */
+		destTrans->commits.insert( srcTrans->commits );
+
+		if ( srcTrans->toState->advanceReductions )
+			destTrans->toState->advanceReductions = true;
+
+		if ( srcTrans->noPreIgnore )
+			destTrans->noPreIgnore = true;
+		if ( srcTrans->noPostIgnore )
+			destTrans->noPostIgnore = true;
+	}
+}
+
+/* NO LONGER USED. */
+void PdaGraph::addInState( PdaState *destState, PdaState *srcState )
+{
+	/* Draw in any properties of srcState into destState. */
+	if ( srcState != destState ) {
+		/* Get the epsilons, context, out priorities. */
+		destState->pendingCommits.insert( srcState->pendingCommits );
+		if ( srcState->pendingCommits.length() > 0 )
+			cerr << "THERE ARE PENDING COMMITS DRAWN IN" << endl;
+
+		/* Parser generation data. */
+		destState->dotSet.insert( srcState->dotSet );
+
+		if ( srcState->onClosureQueue && !destState->onClosureQueue ) {
+			stateClosureQueue.append( destState );
+			destState->onClosureQueue = true;
+		}
+	}
+}
+
+/* Make a new state. The new state will be put on the graph's
+ * list of state. The new state can be created final or non final. */
+PdaState *PdaGraph::addState()
+{
+	/* Make the new state to return. */
+	PdaState *state = new PdaState();
+
+	/* Create the new state. */
+	stateList.append( state );
+
+	return state;
+}
+
+
+/* Follow from to the final state of srcFsm. */
+PdaState *PdaGraph::followFsm( PdaState *from, PdaGraph *srcFsm )
+{
+	PdaState *followSrc = srcFsm->startState;
+
+	while ( ! followSrc->isFinState() ) {
+		assert( followSrc->transMap.length() == 1 );
+		PdaTrans *followTrans = followSrc->transMap[0].value;
+
+		PdaTrans *inTrans = from->findTrans( followTrans->lowKey );
+		assert( inTrans != 0 );
+
+		from = inTrans->toState;
+		followSrc = followTrans->toState;
+	}
+
+	return from;
+}
+
+int PdaGraph::fsmLength( )
+{
+	int length = 0;
+	PdaState *state = startState;
+	while ( ! state->isFinState() ) {
+		length += 1;
+		state = state->transMap[0].value->toState;
+	}
+	return length;
+}
+
+/* Remove states that have no path to them from the start state. Recursively
+ * traverses the graph marking states that have paths into them. Then removes
+ * all states that did not get marked. */
+void PdaGraph::removeUnreachableStates()
+{
+	/* Mark all the states that can be reached 
+	 * through the existing set of entry points. */
+	if ( startState != 0 )
+		markReachableFromHere( startState );
+
+	for ( PdaStateSet::Iter si = entryStateSet; si.lte(); si++ )
+		markReachableFromHere( *si );
+
+	/* Delete all states that are not marked
+	 * and unmark the ones that are marked. */
+	PdaState *state = stateList.head;
+	while ( state ) {
+		PdaState *next = state->next;
+
+		if ( state->stateBits & SB_ISMARKED )
+			state->stateBits &= ~ SB_ISMARKED;
+		else {
+			detachState( state );
+			stateList.detach( state );
+			delete state;
+		}
+
+		state = next;
+	}
+}