/*
* Copyright 2002 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
*/
#include <string.h>
#include <assert.h>
#include "fsmgraph.h"
#include <iostream>
using namespace std;
/* Construct a mark index for a specified number of states. Must new up
* an array that is states^2 in size. */
MarkIndex::MarkIndex( int states ) : numStates(states)
{
/* Total pairs is states^2. Actually only use half of these, but we allocate
* them all to make indexing into the array easier. */
int total = states * states;
/* New up chars so that individual DListEl constructors are
* not called. Zero out the mem manually. */
array = new bool[total];
memset( array, 0, sizeof(bool) * total );
}
/* Free the array used to store state pairs. */
MarkIndex::~MarkIndex()
{
delete[] array;
}
/* Mark a pair of states. States are specified by their number. The
* marked states are moved from the unmarked list to the marked list. */
void MarkIndex::markPair(int state1, int state2)
{
int pos = ( state1 >= state2 ) ?
( state1 * numStates ) + state2 :
( state2 * numStates ) + state1;
array[pos] = true;
}
/* Returns true if the pair of states are marked. Returns false otherwise.
* Ordering of states given does not matter. */
bool MarkIndex::isPairMarked(int state1, int state2)
{
int pos = ( state1 >= state2 ) ?
( state1 * numStates ) + state2 :
( state2 * numStates ) + state1;
return array[pos];
}
/* Create a new fsm state. State has not out transitions or in transitions, not
* out out transition data and not number. */
StateAp::StateAp()
:
/* No out or in transitions. */
outList(),
inList(),
/* No EOF target. */
eofTarget(0),
/* No entry points, or epsilon trans. */
entryIds(),
epsilonTrans(),
/* Conditions. */
stateCondList(),
/* No transitions in from other states. */
foreignInTrans(0),
/* Only used during merging. Normally null. */
stateDictEl(0),
eptVect(0),
/* No state identification bits. */
stateBits(0),
/* No Priority data. */
outPriorTable(),
/* No Action data. */
toStateActionTable(),
fromStateActionTable(),
outActionTable(),
outCondSet(),
errActionTable(),
eofActionTable()
{
}
/* Copy everything except actual the transitions. That is left up to the
* FsmAp copy constructor. */
StateAp::StateAp(const StateAp &other)
:
/* All lists are cleared. They will be filled in when the
* individual transitions are duplicated and attached. */
outList(),
inList(),
/* Set this using the original state's eofTarget. It will get mapped back
* to the new machine in the Fsm copy constructor. */
eofTarget(other.eofTarget),
/* Duplicate the entry id set and epsilon transitions. These
* are sets of integers and as such need no fixing. */
entryIds(other.entryIds),
epsilonTrans(other.epsilonTrans),
/* Copy in the elements of the conditions. */
stateCondList( other.stateCondList ),
/* No transitions in from other states. */
foreignInTrans(0),
/* This is only used during merging. Normally null. */
stateDictEl(0),
eptVect(0),
/* Fsm state data. */
stateBits(other.stateBits),
/* Copy in priority data. */
outPriorTable(other.outPriorTable),
/* Copy in action data. */
toStateActionTable(other.toStateActionTable),
fromStateActionTable(other.fromStateActionTable),
outActionTable(other.outActionTable),
outCondSet(other.outCondSet),
errActionTable(other.errActionTable),
eofActionTable(other.eofActionTable)
{
/* Duplicate all the transitions. */
for ( TransList::Iter trans = other.outList; trans.lte(); trans++ ) {
/* Dupicate and store the orginal target in the transition. This will
* be corrected once all the states have been created. */
TransAp *newTrans = new TransAp(*trans);
assert( trans->lmActionTable.length() == 0 );
newTrans->toState = trans->toState;
outList.append( newTrans );
}
}
/* If there is a state dict element, then delete it. Everything else is left
* up to the FsmGraph destructor. */
StateAp::~StateAp()
{
if ( stateDictEl != 0 )
delete stateDictEl;
}
/* Compare two states using pointers to the states. With the approximate
* compare, the idea is that if the compare finds them the same, they can
* immediately be merged. */
int ApproxCompare::compare( const StateAp *state1, const StateAp *state2 )
{
int compareRes;
/* Test final state status. */
if ( (state1->stateBits & STB_ISFINAL) && !(state2->stateBits & STB_ISFINAL) )
return -1;
else if ( !(state1->stateBits & STB_ISFINAL) && (state2->stateBits & STB_ISFINAL) )
return 1;
/* Test epsilon transition sets. */
compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans,
state2->epsilonTrans );
if ( compareRes != 0 )
return compareRes;
/* Compare the out transitions. */
compareRes = FsmAp::compareStateData( state1, state2 );
if ( compareRes != 0 )
return compareRes;
/* Use a pair iterator to get the transition pairs. */
PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
for ( ; !outPair.end(); outPair++ ) {
switch ( outPair.userState ) {
case RangeInS1:
compareRes = FsmAp::compareFullPtr( outPair.s1Tel.trans, 0 );
if ( compareRes != 0 )
return compareRes;
break;
case RangeInS2:
compareRes = FsmAp::compareFullPtr( 0, outPair.s2Tel.trans );
if ( compareRes != 0 )
return compareRes;
break;
case RangeOverlap:
compareRes = FsmAp::compareFullPtr(
outPair.s1Tel.trans, outPair.s2Tel.trans );
if ( compareRes != 0 )
return compareRes;
break;
case BreakS1:
case BreakS2:
break;
}
}
/* Check EOF targets. */
if ( state1->eofTarget < state2->eofTarget )
return -1;
else if ( state1->eofTarget > state2->eofTarget )
return 1;
/* Got through the entire state comparison, deem them equal. */
return 0;
}
/* Compare class used in the initial partition. */
int InitPartitionCompare::compare( const StateAp *state1 , const StateAp *state2 )
{
int compareRes;
/* Test final state status. */
if ( (state1->stateBits & STB_ISFINAL) && !(state2->stateBits & STB_ISFINAL) )
return -1;
else if ( !(state1->stateBits & STB_ISFINAL) && (state2->stateBits & STB_ISFINAL) )
return 1;
/* Test epsilon transition sets. */
compareRes = CmpEpsilonTrans::compare( state1->epsilonTrans,
state2->epsilonTrans );
if ( compareRes != 0 )
return compareRes;
/* Compare the out transitions. */
compareRes = FsmAp::compareStateData( state1, state2 );
if ( compareRes != 0 )
return compareRes;
/* Use a pair iterator to test the condition pairs. */
PairIter<StateCond> condPair( state1->stateCondList.head, state2->stateCondList.head );
for ( ; !condPair.end(); condPair++ ) {
switch ( condPair.userState ) {
case RangeInS1:
return 1;
case RangeInS2:
return -1;
case RangeOverlap: {
CondSpace *condSpace1 = condPair.s1Tel.trans->condSpace;
CondSpace *condSpace2 = condPair.s2Tel.trans->condSpace;
if ( condSpace1 < condSpace2 )
return -1;
else if ( condSpace1 > condSpace2 )
return 1;
break;
}
case BreakS1:
case BreakS2:
break;
}
}
/* Use a pair iterator to test the transition pairs. */
PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
for ( ; !outPair.end(); outPair++ ) {
switch ( outPair.userState ) {
case RangeInS1:
compareRes = FsmAp::compareDataPtr( outPair.s1Tel.trans, 0 );
if ( compareRes != 0 )
return compareRes;
break;
case RangeInS2:
compareRes = FsmAp::compareDataPtr( 0, outPair.s2Tel.trans );
if ( compareRes != 0 )
return compareRes;
break;
case RangeOverlap:
compareRes = FsmAp::compareDataPtr(
outPair.s1Tel.trans, outPair.s2Tel.trans );
if ( compareRes != 0 )
return compareRes;
break;
case BreakS1:
case BreakS2:
break;
}
}
return 0;
}
/* Compare class for the sort that does the partitioning. */
int PartitionCompare::compare( const StateAp *state1, const StateAp *state2 )
{
int compareRes;
/* Use a pair iterator to get the transition pairs. */
PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
for ( ; !outPair.end(); outPair++ ) {
switch ( outPair.userState ) {
case RangeInS1:
compareRes = FsmAp::comparePartPtr( outPair.s1Tel.trans, 0 );
if ( compareRes != 0 )
return compareRes;
break;
case RangeInS2:
compareRes = FsmAp::comparePartPtr( 0, outPair.s2Tel.trans );
if ( compareRes != 0 )
return compareRes;
break;
case RangeOverlap:
compareRes = FsmAp::comparePartPtr(
outPair.s1Tel.trans, outPair.s2Tel.trans );
if ( compareRes != 0 )
return compareRes;
break;
case BreakS1:
case BreakS2:
break;
}
}
/* Test eof targets. */
if ( state1->eofTarget == 0 && state2->eofTarget != 0 )
return -1;
else if ( state1->eofTarget != 0 && state2->eofTarget == 0 )
return 1;
else if ( state1->eofTarget != 0 ) {
/* Both eof targets are set. */
compareRes = CmpOrd< MinPartition* >::compare(
state1->eofTarget->alg.partition, state2->eofTarget->alg.partition );
if ( compareRes != 0 )
return compareRes;
}
return 0;
}
/* Compare class for the sort that does the partitioning. */
bool MarkCompare::shouldMark( MarkIndex &markIndex, const StateAp *state1,
const StateAp *state2 )
{
/* Use a pair iterator to get the transition pairs. */
PairIter<TransAp> outPair( state1->outList.head, state2->outList.head );
for ( ; !outPair.end(); outPair++ ) {
switch ( outPair.userState ) {
case RangeInS1:
if ( FsmAp::shouldMarkPtr( markIndex, outPair.s1Tel.trans, 0 ) )
return true;
break;
case RangeInS2:
if ( FsmAp::shouldMarkPtr( markIndex, 0, outPair.s2Tel.trans ) )
return true;
break;
case RangeOverlap:
if ( FsmAp::shouldMarkPtr( markIndex,
outPair.s1Tel.trans, outPair.s2Tel.trans ) )
return true;
break;
case BreakS1:
case BreakS2:
break;
}
}
return false;
}
/*
* Transition Comparison.
*/
/* Compare target partitions. Either pointer may be null. */
int FsmAp::comparePartPtr( TransAp *trans1, TransAp *trans2 )
{
if ( trans1 != 0 ) {
/* If trans1 is set then so should trans2. The initial partitioning
* guarantees this for us. */
if ( trans1->toState == 0 && trans2->toState != 0 )
return -1;
else if ( trans1->toState != 0 && trans2->toState == 0 )
return 1;
else if ( trans1->toState != 0 ) {
/* Both of targets are set. */
return CmpOrd< MinPartition* >::compare(
trans1->toState->alg.partition, trans2->toState->alg.partition );
}
}
return 0;
}
/* Compares two transition pointers according to priority and functions.
* Either pointer may be null. Does not consider to state or from state. */
int FsmAp::compareDataPtr( TransAp *trans1, TransAp *trans2 )
{
if ( trans1 == 0 && trans2 != 0 )
return -1;
else if ( trans1 != 0 && trans2 == 0 )
return 1;
else if ( trans1 != 0 ) {
/* Both of the transition pointers are set. */
int compareRes = compareTransData( trans1, trans2 );
if ( compareRes != 0 )
return compareRes;
}
return 0;
}
/* Compares two transitions according to target state, priority and functions.
* Does not consider from state. Either of the pointers may be null. */
int FsmAp::compareFullPtr( TransAp *trans1, TransAp *trans2 )
{
if ( (trans1 != 0) ^ (trans2 != 0) ) {
/* Exactly one of the transitions is set. */
if ( trans1 != 0 )
return -1;
else
return 1;
}
else if ( trans1 != 0 ) {
/* Both of the transition pointers are set. Test target state,
* priority and funcs. */
if ( trans1->toState < trans2->toState )
return -1;
else if ( trans1->toState > trans2->toState )
return 1;
else if ( trans1->toState != 0 ) {
/* Test transition data. */
int compareRes = compareTransData( trans1, trans2 );
if ( compareRes != 0 )
return compareRes;
}
}
return 0;
}
bool FsmAp::shouldMarkPtr( MarkIndex &markIndex, TransAp *trans1,
TransAp *trans2 )
{
if ( (trans1 != 0) ^ (trans2 != 0) ) {
/* Exactly one of the transitions is set. The initial mark round
* should rule out this case. */
assert( false );
}
else if ( trans1 != 0 ) {
/* Both of the transitions are set. If the target pair is marked, then
* the pair we are considering gets marked. */
return markIndex.isPairMarked( trans1->toState->alg.stateNum,
trans2->toState->alg.stateNum );
}
/* Neither of the transitiosn are set. */
return false;
}
