/*
 *  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 
 */
#include "redfsm.h"
#include "avlmap.h"
#include "mergesort.h"
#include <iostream>
#include <sstream>
using std::ostringstream;
using std::string;
string GenAction::nameOrLoc()
{
        if ( name != 0 )
                return string(name);
        else {
                ostringstream ret;
                ret << loc.line << ":" << loc.col;
                return ret.str();
        }
}
RedFsmAp::RedFsmAp()
:
        forcedErrorState(false),
        nextActionId(0),
        nextTransId(0),
        startState(0),
        errState(0),
        errTrans(0),
        firstFinState(0),
        numFinStates(0),
        bAnyToStateActions(false),
        bAnyFromStateActions(false),
        bAnyRegActions(false),
        bAnyEofActions(false),
        bAnyEofTrans(false),
        bAnyActionGotos(false),
        bAnyActionCalls(false),
        bAnyActionRets(false),
        bAnyActionByValControl(false),
        bAnyRegActionRets(false),
        bAnyRegActionByValControl(false),
        bAnyRegNextStmt(false),
        bAnyRegCurStateRef(false),
        bAnyRegBreak(false),
        bAnyConditions(false)
{
}
/* Does the machine have any actions. */
bool RedFsmAp::anyActions()
{
        return actionMap.length() > 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. */
        if ( startState != 0 )
                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++;
        }
}
struct CmpStateById
{
        static int compare( RedStateAp *st1, RedStateAp *st2 )
        {
                if ( st1->id < st2->id )
                        return -1;
                else if ( st1->id > st2->id )
                        return 1;
                else
                        return 0;
        }
};
void RedFsmAp::sortByStateId()
{
        /* Make the array. */
        int pos = 0;
        RedStateAp **ptrList = new RedStateAp*[stateList.length()];
        for ( RedStateList::Iter st = stateList; st.lte(); st++, pos++ )
                ptrList[pos] = st;
         
        MergeSort<RedStateAp*, CmpStateById> mergeSort;
        mergeSort.sort( ptrList, stateList.length() );
        stateList.abandon();
        for ( int st = 0; st < pos; st++ )
                stateList.append( ptrList[st] );
        delete[] ptrList;
}
/* 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 ( GenActionTableMap::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 GenCondSpace*[ span ];
                        memset( st->condList, 0, sizeof(GenCondSpace*)*span );
                        for ( GenStateCondList::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.transfer( outRange );
        /* 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()
{
        /* Something went wrong. An error state is needed but one was not supplied
         * by the frontend. */
        assert( errState != 0 );
        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;
}