"Fossies" - the Fresh Open Source Software Archive

Member "ragel-6.10/ragel/redfsm.cpp" (24 Mar 2017, 16725 Bytes) of package /linux/misc/ragel-6.10.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "redfsm.cpp" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: 6.9_vs_6.10.

    1 /*
    2  *  Copyright 2001-2006 Adrian Thurston <thurston@complang.org>
    3  */
    4 
    5 /*  This file is part of Ragel.
    6  *
    7  *  Ragel is free software; you can redistribute it and/or modify
    8  *  it under the terms of the GNU General Public License as published by
    9  *  the Free Software Foundation; either version 2 of the License, or
   10  *  (at your option) any later version.
   11  * 
   12  *  Ragel is distributed in the hope that it will be useful,
   13  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   14  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   15  *  GNU General Public License for more details.
   16  * 
   17  *  You should have received a copy of the GNU General Public License
   18  *  along with Ragel; if not, write to the Free Software
   19  *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA 
   20  */
   21 
   22 #include "redfsm.h"
   23 #include "avlmap.h"
   24 #include "mergesort.h"
   25 #include <iostream>
   26 #include <sstream>
   27 
   28 using std::ostringstream;
   29 
   30 string GenAction::nameOrLoc()
   31 {
   32     if ( name != 0 )
   33         return string(name);
   34     else {
   35         ostringstream ret;
   36         ret << loc.line << ":" << loc.col;
   37         return ret.str();
   38     }
   39 }
   40 
   41 RedFsmAp::RedFsmAp()
   42 :
   43     forcedErrorState(false),
   44     nextActionId(0),
   45     nextTransId(0),
   46     startState(0),
   47     errState(0),
   48     errTrans(0),
   49     firstFinState(0),
   50     numFinStates(0),
   51     bAnyToStateActions(false),
   52     bAnyFromStateActions(false),
   53     bAnyRegActions(false),
   54     bAnyEofActions(false),
   55     bAnyEofTrans(false),
   56     bAnyActionGotos(false),
   57     bAnyActionCalls(false),
   58     bAnyActionRets(false),
   59     bAnyActionByValControl(false),
   60     bAnyRegActionRets(false),
   61     bAnyRegActionByValControl(false),
   62     bAnyRegNextStmt(false),
   63     bAnyRegCurStateRef(false),
   64     bAnyRegBreak(false),
   65     bAnyConditions(false)
   66 {
   67 }
   68 
   69 /* Does the machine have any actions. */
   70 bool RedFsmAp::anyActions()
   71 {
   72     return actionMap.length() > 0;
   73 }
   74 
   75 void RedFsmAp::depthFirstOrdering( RedStateAp *state )
   76 {
   77     /* Nothing to do if the state is already on the list. */
   78     if ( state->onStateList )
   79         return;
   80 
   81     /* Doing depth first, put state on the list. */
   82     state->onStateList = true;
   83     stateList.append( state );
   84     
   85     /* At this point transitions should only be in ranges. */
   86     assert( state->outSingle.length() == 0 );
   87     assert( state->defTrans == 0 );
   88 
   89     /* Recurse on everything ranges. */
   90     for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
   91         if ( rtel->value->targ != 0 )
   92             depthFirstOrdering( rtel->value->targ );
   93     }
   94 }
   95 
   96 /* Ordering states by transition connections. */
   97 void RedFsmAp::depthFirstOrdering()
   98 {
   99     /* Init on state list flags. */
  100     for ( RedStateList::Iter st = stateList; st.lte(); st++ )
  101         st->onStateList = false;
  102     
  103     /* Clear out the state list, we will rebuild it. */
  104     int stateListLen = stateList.length();
  105     stateList.abandon();
  106 
  107     /* Add back to the state list from the start state and all other entry
  108      * points. */
  109     if ( startState != 0 )
  110         depthFirstOrdering( startState );
  111     for ( RedStateSet::Iter en = entryPoints; en.lte(); en++ )
  112         depthFirstOrdering( *en );
  113     if ( forcedErrorState )
  114         depthFirstOrdering( errState );
  115     
  116     /* Make sure we put everything back on. */
  117     assert( stateListLen == stateList.length() );
  118 }
  119 
  120 /* Assign state ids by appearance in the state list. */
  121 void RedFsmAp::sequentialStateIds()
  122 {
  123     /* Table based machines depend on the state numbers starting at zero. */
  124     nextStateId = 0;
  125     for ( RedStateList::Iter st = stateList; st.lte(); st++ )
  126         st->id = nextStateId++;
  127 }
  128 
  129 /* Stable sort the states by final state status. */
  130 void RedFsmAp::sortStatesByFinal()
  131 {
  132     /* Move forward through the list and throw final states onto the end. */
  133     RedStateAp *state = 0;
  134     RedStateAp *next = stateList.head;
  135     RedStateAp *last = stateList.tail;
  136     while ( state != last ) {
  137         /* Move forward and load up the next. */
  138         state = next;
  139         next = state->next;
  140 
  141         /* Throw to the end? */
  142         if ( state->isFinal ) {
  143             stateList.detach( state );
  144             stateList.append( state );
  145         }
  146     }
  147 }
  148 
  149 /* Assign state ids by final state state status. */
  150 void RedFsmAp::sortStateIdsByFinal()
  151 {
  152     /* Table based machines depend on this starting at zero. */
  153     nextStateId = 0;
  154 
  155     /* First pass to assign non final ids. */
  156     for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
  157         if ( ! st->isFinal ) 
  158             st->id = nextStateId++;
  159     }
  160 
  161     /* Second pass to assign final ids. */
  162     for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
  163         if ( st->isFinal ) 
  164             st->id = nextStateId++;
  165     }
  166 }
  167 
  168 struct CmpStateById
  169 {
  170     static int compare( RedStateAp *st1, RedStateAp *st2 )
  171     {
  172         if ( st1->id < st2->id )
  173             return -1;
  174         else if ( st1->id > st2->id )
  175             return 1;
  176         else
  177             return 0;
  178     }
  179 };
  180 
  181 void RedFsmAp::sortByStateId()
  182 {
  183     /* Make the array. */
  184     int pos = 0;
  185     RedStateAp **ptrList = new RedStateAp*[stateList.length()];
  186     for ( RedStateList::Iter st = stateList; st.lte(); st++, pos++ )
  187         ptrList[pos] = st;
  188     
  189     MergeSort<RedStateAp*, CmpStateById> mergeSort;
  190     mergeSort.sort( ptrList, stateList.length() );
  191 
  192     stateList.abandon();
  193     for ( int st = 0; st < pos; st++ )
  194         stateList.append( ptrList[st] );
  195 
  196     delete[] ptrList;
  197 }
  198 
  199 /* Find the final state with the lowest id. */
  200 void RedFsmAp::findFirstFinState()
  201 {
  202     for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
  203         if ( st->isFinal && (firstFinState == 0 || st->id < firstFinState->id) )
  204             firstFinState = st;
  205     }
  206 }
  207 
  208 void RedFsmAp::assignActionLocs()
  209 {
  210     int nextLocation = 0;
  211     for ( GenActionTableMap::Iter act = actionMap; act.lte(); act++ ) {
  212         /* Store the loc, skip over the array and a null terminator. */
  213         act->location = nextLocation;
  214         nextLocation += act->key.length() + 1;      
  215     }
  216 }
  217 
  218 /* Check if we can extend the current range by displacing any ranges
  219  * ahead to the singles. */
  220 bool RedFsmAp::canExtend( const RedTransList &list, int pos )
  221 {
  222     /* Get the transition that we want to extend. */
  223     RedTransAp *extendTrans = list[pos].value;
  224 
  225     /* Look ahead in the transition list. */
  226     for ( int next = pos + 1; next < list.length(); pos++, next++ ) {
  227         /* If they are not continuous then cannot extend. */
  228         Key nextKey = list[next].lowKey;
  229         nextKey.decrement();
  230         if ( list[pos].highKey != nextKey )
  231             break;
  232 
  233         /* Check for the extenstion property. */
  234         if ( extendTrans == list[next].value )
  235             return true;
  236 
  237         /* If the span of the next element is more than one, then don't keep
  238          * checking, it won't be moved to single. */
  239         unsigned long long nextSpan = keyOps->span( list[next].lowKey, list[next].highKey );
  240         if ( nextSpan > 1 )
  241             break;
  242     }
  243     return false;
  244 }
  245 
  246 /* Move ranges to the singles list. */
  247 void RedFsmAp::moveTransToSingle( RedStateAp *state )
  248 {
  249     RedTransList &range = state->outRange;
  250     RedTransList &single = state->outSingle;
  251     for ( int rpos = 0; rpos < range.length(); ) {
  252         /* Check if this is a range we can extend. */
  253         if ( canExtend( range, rpos ) ) {
  254             /* Transfer singles over. */
  255             while ( range[rpos].value != range[rpos+1].value ) {
  256                 /* Transfer the range to single. */
  257                 single.append( range[rpos+1] );
  258                 range.remove( rpos+1 );
  259             }
  260             
  261             /* Extend. */
  262             range[rpos].highKey = range[rpos+1].highKey;
  263             range.remove( rpos+1 );
  264         }
  265         /* Maybe move it to the singles. */
  266         else if ( keyOps->span( range[rpos].lowKey, range[rpos].highKey ) == 1 ) {
  267             single.append( range[rpos] );
  268             range.remove( rpos );
  269         }
  270         else {
  271             /* Keeping it in the ranges. */
  272             rpos += 1;
  273         }
  274     }
  275 }
  276 
  277 /* Look through ranges and choose suitable single character transitions. */
  278 void RedFsmAp::chooseSingle()
  279 {
  280     /* Loop the states. */
  281     for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
  282         /* Rewrite the transition list taking out the suitable single
  283          * transtions. */
  284         moveTransToSingle( st );
  285     }
  286 }
  287 
  288 void RedFsmAp::makeFlat()
  289 {
  290     for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
  291         if ( st->stateCondList.length() == 0 ) {
  292             st->condLowKey = 0;
  293             st->condHighKey = 0;
  294         }
  295         else {
  296             st->condLowKey = st->stateCondList.head->lowKey;
  297             st->condHighKey = st->stateCondList.tail->highKey;
  298 
  299             unsigned long long span = keyOps->span( st->condLowKey, st->condHighKey );
  300             st->condList = new GenCondSpace*[ span ];
  301             memset( st->condList, 0, sizeof(GenCondSpace*)*span );
  302 
  303             for ( GenStateCondList::Iter sci = st->stateCondList; sci.lte(); sci++ ) {
  304                 unsigned long long base, trSpan;
  305                 base = keyOps->span( st->condLowKey, sci->lowKey )-1;
  306                 trSpan = keyOps->span( sci->lowKey, sci->highKey );
  307                 for ( unsigned long long pos = 0; pos < trSpan; pos++ )
  308                     st->condList[base+pos] = sci->condSpace;
  309             }
  310         }
  311 
  312         if ( st->outRange.length() == 0 ) {
  313             st->lowKey = st->highKey = 0;
  314             st->transList = 0;
  315         }
  316         else {
  317             st->lowKey = st->outRange[0].lowKey;
  318             st->highKey = st->outRange[st->outRange.length()-1].highKey;
  319             unsigned long long span = keyOps->span( st->lowKey, st->highKey );
  320             st->transList = new RedTransAp*[ span ];
  321             memset( st->transList, 0, sizeof(RedTransAp*)*span );
  322             
  323             for ( RedTransList::Iter trans = st->outRange; trans.lte(); trans++ ) {
  324                 unsigned long long base, trSpan;
  325                 base = keyOps->span( st->lowKey, trans->lowKey )-1;
  326                 trSpan = keyOps->span( trans->lowKey, trans->highKey );
  327                 for ( unsigned long long pos = 0; pos < trSpan; pos++ )
  328                     st->transList[base+pos] = trans->value;
  329             }
  330 
  331             /* Fill in the gaps with the default transition. */
  332             for ( unsigned long long pos = 0; pos < span; pos++ ) {
  333                 if ( st->transList[pos] == 0 )
  334                     st->transList[pos] = st->defTrans;
  335             }
  336         }
  337     }
  338 }
  339 
  340 
  341 /* A default transition has been picked, move it from the outRange to the
  342  * default pointer. */
  343 void RedFsmAp::moveToDefault( RedTransAp *defTrans, RedStateAp *state )
  344 {
  345     /* Rewrite the outRange, omitting any ranges that use 
  346      * the picked default. */
  347     RedTransList outRange;
  348     for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
  349         /* If it does not take the default, copy it over. */
  350         if ( rtel->value != defTrans )
  351             outRange.append( *rtel );
  352     }
  353 
  354     /* Save off the range we just created into the state's range. */
  355     state->outRange.transfer( outRange );
  356 
  357     /* Store the default. */
  358     state->defTrans = defTrans;
  359 }
  360 
  361 bool RedFsmAp::alphabetCovered( RedTransList &outRange )
  362 {
  363     /* Cannot cover without any out ranges. */
  364     if ( outRange.length() == 0 )
  365         return false;
  366 
  367     /* If the first range doesn't start at the the lower bound then the
  368      * alphabet is not covered. */
  369     RedTransList::Iter rtel = outRange;
  370     if ( keyOps->minKey < rtel->lowKey )
  371         return false;
  372 
  373     /* Check that every range is next to the previous one. */
  374     rtel.increment();
  375     for ( ; rtel.lte(); rtel++ ) {
  376         Key highKey = rtel[-1].highKey;
  377         highKey.increment();
  378         if ( highKey != rtel->lowKey )
  379             return false;
  380     }
  381 
  382     /* The last must extend to the upper bound. */
  383     RedTransEl *last = &outRange[outRange.length()-1];
  384     if ( last->highKey < keyOps->maxKey )
  385         return false;
  386 
  387     return true;
  388 }
  389 
  390 RedTransAp *RedFsmAp::chooseDefaultSpan( RedStateAp *state )
  391 {
  392     /* Make a set of transitions from the outRange. */
  393     RedTransSet stateTransSet;
  394     for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ )
  395         stateTransSet.insert( rtel->value );
  396     
  397     /* For each transition in the find how many alphabet characters the
  398      * transition spans. */
  399     unsigned long long *span = new unsigned long long[stateTransSet.length()];
  400     memset( span, 0, sizeof(unsigned long long) * stateTransSet.length() );
  401     for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
  402         /* Lookup the transition in the set. */
  403         RedTransAp **inSet = stateTransSet.find( rtel->value );
  404         int pos = inSet - stateTransSet.data;
  405         span[pos] += keyOps->span( rtel->lowKey, rtel->highKey );
  406     }
  407 
  408     /* Find the max span, choose it for making the default. */
  409     RedTransAp *maxTrans = 0;
  410     unsigned long long maxSpan = 0;
  411     for ( RedTransSet::Iter rtel = stateTransSet; rtel.lte(); rtel++ ) {
  412         if ( span[rtel.pos()] > maxSpan ) {
  413             maxSpan = span[rtel.pos()];
  414             maxTrans = *rtel;
  415         }
  416     }
  417 
  418     delete[] span;
  419     return maxTrans;
  420 }
  421 
  422 /* Pick default transitions from ranges for the states. */
  423 void RedFsmAp::chooseDefaultSpan()
  424 {
  425     /* Loop the states. */
  426     for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
  427         /* Only pick a default transition if the alphabet is covered. This
  428          * avoids any transitions in the out range that go to error and avoids
  429          * the need for an ERR state. */
  430         if ( alphabetCovered( st->outRange ) ) {
  431             /* Pick a default transition by largest span. */
  432             RedTransAp *defTrans = chooseDefaultSpan( st );
  433 
  434             /* Rewrite the transition list taking out the transition we picked
  435              * as the default and store the default. */
  436             moveToDefault( defTrans, st );
  437         }
  438     }
  439 }
  440 
  441 RedTransAp *RedFsmAp::chooseDefaultGoto( RedStateAp *state )
  442 {
  443     /* Make a set of transitions from the outRange. */
  444     RedTransSet stateTransSet;
  445     for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
  446         if ( rtel->value->targ == state->next )
  447             return rtel->value;
  448     }
  449     return 0;
  450 }
  451 
  452 void RedFsmAp::chooseDefaultGoto()
  453 {
  454     /* Loop the states. */
  455     for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
  456         /* Pick a default transition. */
  457         RedTransAp *defTrans = chooseDefaultGoto( st );
  458         if ( defTrans == 0 )
  459             defTrans = chooseDefaultSpan( st );
  460 
  461         /* Rewrite the transition list taking out the transition we picked
  462          * as the default and store the default. */
  463         moveToDefault( defTrans, st );
  464     }
  465 }
  466 
  467 RedTransAp *RedFsmAp::chooseDefaultNumRanges( RedStateAp *state )
  468 {
  469     /* Make a set of transitions from the outRange. */
  470     RedTransSet stateTransSet;
  471     for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ )
  472         stateTransSet.insert( rtel->value );
  473     
  474     /* For each transition in the find how many ranges use the transition. */
  475     int *numRanges = new int[stateTransSet.length()];
  476     memset( numRanges, 0, sizeof(int) * stateTransSet.length() );
  477     for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
  478         /* Lookup the transition in the set. */
  479         RedTransAp **inSet = stateTransSet.find( rtel->value );
  480         numRanges[inSet - stateTransSet.data] += 1;
  481     }
  482 
  483     /* Find the max number of ranges. */
  484     RedTransAp *maxTrans = 0;
  485     int maxNumRanges = 0;
  486     for ( RedTransSet::Iter rtel = stateTransSet; rtel.lte(); rtel++ ) {
  487         if ( numRanges[rtel.pos()] > maxNumRanges ) {
  488             maxNumRanges = numRanges[rtel.pos()];
  489             maxTrans = *rtel;
  490         }
  491     }
  492 
  493     delete[] numRanges;
  494     return maxTrans;
  495 }
  496 
  497 void RedFsmAp::chooseDefaultNumRanges()
  498 {
  499     /* Loop the states. */
  500     for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
  501         /* Pick a default transition. */
  502         RedTransAp *defTrans = chooseDefaultNumRanges( st );
  503 
  504         /* Rewrite the transition list taking out the transition we picked
  505          * as the default and store the default. */
  506         moveToDefault( defTrans, st );
  507     }
  508 }
  509 
  510 RedTransAp *RedFsmAp::getErrorTrans( )
  511 {
  512     /* If the error trans has not been made aready, make it. */
  513     if ( errTrans == 0 ) {
  514         /* This insert should always succeed since no transition created by
  515          * the user can point to the error state. */
  516         errTrans = new RedTransAp( getErrorState(), 0, nextTransId++ );
  517         RedTransAp *inRes = transSet.insert( errTrans );
  518         assert( inRes != 0 );
  519     }
  520     return errTrans;
  521 }
  522 
  523 RedStateAp *RedFsmAp::getErrorState()
  524 {
  525     /* Something went wrong. An error state is needed but one was not supplied
  526      * by the frontend. */
  527     assert( errState != 0 );
  528     return errState;
  529 }
  530 
  531 
  532 RedTransAp *RedFsmAp::allocateTrans( RedStateAp *targ, RedAction *action )
  533 {
  534     /* Create a reduced trans and look for it in the transiton set. */
  535     RedTransAp redTrans( targ, action, 0 );
  536     RedTransAp *inDict = transSet.find( &redTrans );
  537     if ( inDict == 0 ) {
  538         inDict = new RedTransAp( targ, action, nextTransId++ );
  539         transSet.insert( inDict );
  540     }
  541     return inDict;
  542 }
  543 
  544 void RedFsmAp::partitionFsm( int nparts )
  545 {
  546     /* At this point the states are ordered by a depth-first traversal. We
  547      * will allocate to partitions based on this ordering. */
  548     this->nParts = nparts;
  549     int partSize = stateList.length() / nparts;
  550     int remainder = stateList.length() % nparts;
  551     int numInPart = partSize;
  552     int partition = 0;
  553     if ( remainder-- > 0 )
  554         numInPart += 1;
  555     for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
  556         st->partition = partition;
  557 
  558         numInPart -= 1;
  559         if ( numInPart == 0 ) {
  560             partition += 1;
  561             numInPart = partSize;
  562             if ( remainder-- > 0 )
  563                 numInPart += 1;
  564         }
  565     }
  566 }
  567 
  568 void RedFsmAp::setInTrans()
  569 {
  570     /* First pass counts the number of transitions. */
  571     for ( TransApSet::Iter trans = transSet; trans.lte(); trans++ )
  572         trans->targ->numInTrans += 1;
  573 
  574     /* Pass over states to allocate the needed memory. Reset the counts so we
  575      * can use them as the current size. */
  576     for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
  577         st->inTrans = new RedTransAp*[st->numInTrans];
  578         st->numInTrans = 0;
  579     }
  580 
  581     /* Second pass over transitions copies pointers into the in trans list. */
  582     for ( TransApSet::Iter trans = transSet; trans.lte(); trans++ )
  583         trans->targ->inTrans[trans->targ->numInTrans++] = trans;
  584 }