diff options
Diffstat (limited to 'src/libfsm/binary.cc')
| -rw-r--r-- | src/libfsm/binary.cc | 819 |
1 files changed, 819 insertions, 0 deletions
diff --git a/src/libfsm/binary.cc b/src/libfsm/binary.cc new file mode 100644 index 00000000..39b58a47 --- /dev/null +++ b/src/libfsm/binary.cc @@ -0,0 +1,819 @@ +/* + * Copyright 2001-2018 Adrian Thurston <thurston@colm.net> + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in all + * copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + * SOFTWARE. + */ + +#include "ragel.h" +#include "binary.h" +#include "redfsm.h" +#include "gendata.h" + +#include <assert.h> + +void Binary::genAnalysis() +{ + redFsm->sortByStateId(); + + /* Choose default transitions and the single transition. */ + redFsm->chooseDefaultSpan(); + + /* Choose the singles. */ + redFsm->moveSelectTransToSingle(); + + if ( redFsm->errState != 0 ) + redFsm->getErrorCond(); + + /* If any errors have occured in the input file then don't write anything. */ + if ( red->id->errorCount > 0 ) + return; + + /* Anlayze Machine will find the final action reference counts, among other + * things. We will use these in reporting the usage of fsm directives in + * action code. */ + red->analyzeMachine(); + + setKeyType(); + + /* Run the analysis pass over the table data. */ + setTableState( TableArray::AnalyzePass ); + tableDataPass(); + + /* Switch the tables over to the code gen mode. */ + setTableState( TableArray::GeneratePass ); +} + + +void Binary::tableDataPass() +{ + if ( type == Loop ) + taActions(); + + taKeyOffsets(); + taSingleLens(); + taRangeLens(); + taIndexOffsets(); + taIndices(); + + taTransCondSpacesWi(); + taTransOffsetsWi(); + taTransLengthsWi(); + + taTransCondSpaces(); + taTransOffsets(); + taTransLengths(); + + taCondTargs(); + taCondActions(); + + taToStateActions(); + taFromStateActions(); + taEofActions(); + taEofConds(); + taEofTrans(); + + taKeys(); + taCondKeys(); + + taNfaTargs(); + taNfaOffsets(); + taNfaPushActions(); + taNfaPopTrans(); +} + +void Binary::writeData() +{ + if ( type == Loop ) { + /* If there are any transtion functions then output the array. If there + * are none, don't bother emitting an empty array that won't be used. */ + if ( redFsm->anyActions() ) + taActions(); + } + + taKeyOffsets(); + taKeys(); + taSingleLens(); + taRangeLens(); + taIndexOffsets(); + + taTransCondSpaces(); + taTransOffsets(); + taTransLengths(); + + taCondKeys(); + taCondTargs(); + taCondActions(); + + if ( redFsm->anyToStateActions() ) + taToStateActions(); + + if ( redFsm->anyFromStateActions() ) + taFromStateActions(); + + if ( redFsm->anyEofActions() ) + taEofActions(); + + taEofConds(); + + if ( redFsm->anyEofTrans() ) + taEofTrans(); + + taNfaTargs(); + taNfaOffsets(); + taNfaPushActions(); + taNfaPopTrans(); + + STATE_IDS(); +} + + +void Binary::setKeyType() +{ + transKeys.setType( ALPH_TYPE(), alphType->size, alphType->isChar ); + transKeys.isSigned = keyOps->isSigned; +} + +void Binary::setTableState( TableArray::State state ) +{ + for ( ArrayVector::Iter i = arrayVector; i.lte(); i++ ) { + TableArray *tableArray = *i; + tableArray->setState( state ); + } +} + +void Binary::taKeyOffsets() +{ + keyOffsets.start(); + + int curKeyOffset = 0; + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + keyOffsets.value( curKeyOffset ); + curKeyOffset += st->outSingle.length() + st->outRange.length()*2; + } + + keyOffsets.finish(); +} + + +void Binary::taSingleLens() +{ + singleLens.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) + singleLens.value( st->outSingle.length() ); + + singleLens.finish(); +} + + +void Binary::taRangeLens() +{ + rangeLens.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) + rangeLens.value( st->outRange.length() ); + + rangeLens.finish(); +} + +void Binary::taIndexOffsets() +{ + indexOffsets.start(); + + int curIndOffset = 0; + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + /* Write the index offset. */ + indexOffsets.value( curIndOffset ); + + /* Move the index offset ahead. */ + curIndOffset += st->outSingle.length() + st->outRange.length(); + if ( st->defTrans != 0 ) + curIndOffset += 1; + } + + indexOffsets.finish(); +} + +void Binary::taToStateActions() +{ + toStateActions.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) + TO_STATE_ACTION(st); + + toStateActions.finish(); +} + +void Binary::taFromStateActions() +{ + fromStateActions.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) + FROM_STATE_ACTION(st); + + fromStateActions.finish(); +} + +void Binary::taEofActions() +{ + eofActions.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) + EOF_ACTION( st ); + + eofActions.finish(); +} + +void Binary::taEofConds() +{ + /* + * EOF Cond Spaces + */ + eofCondSpaces.start(); + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->outCondSpace != 0 ) + eofCondSpaces.value( st->outCondSpace->condSpaceId ); + else + eofCondSpaces.value( -1 ); + } + eofCondSpaces.finish(); + + /* + * EOF Cond Key Indixes + */ + eofCondKeyOffs.start(); + + int curOffset = 0; + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + long off = 0; + if ( st->outCondSpace != 0 ) { + off = curOffset; + curOffset += st->outCondKeys.length(); + } + eofCondKeyOffs.value( off ); + } + + eofCondKeyOffs.finish(); + + /* + * EOF Cond Key Lengths. + */ + eofCondKeyLens.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + long len = 0; + if ( st->outCondSpace != 0 ) + len = st->outCondKeys.length(); + eofCondKeyLens.value( len ); + } + + eofCondKeyLens.finish(); + + /* + * EOF Cond Keys + */ + eofCondKeys.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->outCondSpace != 0 ) { + for ( int c = 0; c < st->outCondKeys.length(); c++ ) { + CondKey key = st->outCondKeys[c]; + eofCondKeys.value( key.getVal() ); + } + } + } + + eofCondKeys.finish(); +} + +void Binary::taEofTrans() +{ + eofTrans.start(); + + /* Need to compute transition positions. */ + int totalTrans = 0; + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + totalTrans += st->outSingle.length(); + totalTrans += st->outRange.length(); + if ( st->defTrans != 0 ) + totalTrans += 1; + } + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + long trans = 0; + if ( st->eofTrans != 0 ) { + trans = totalTrans + 1; + totalTrans += 1; + } + + eofTrans.value( trans ); + } + + eofTrans.finish(); +} + +void Binary::taKeys() +{ + transKeys.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + /* Loop the singles. */ + for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) { + transKeys.value( stel->lowKey.getVal() ); + } + + /* Loop the state's transitions. */ + for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) { + /* Lower key. */ + transKeys.value( rtel->lowKey.getVal() ); + + /* Upper key. */ + transKeys.value( rtel->highKey.getVal() ); + } + } + + transKeys.finish(); +} + +void Binary::taIndices() +{ + indices.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + /* Walk the singles. */ + for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) + indices.value( stel->value->id ); + + /* Walk the ranges. */ + for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) + indices.value( rtel->value->id ); + + /* The state's default index goes next. */ + if ( st->defTrans != 0 ) + indices.value( st->defTrans->id ); + } + + indices.finish(); +} + +void Binary::taTransCondSpaces() +{ + transCondSpaces.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + /* Walk the singles. */ + for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) { + RedTransAp *trans = stel->value; + if ( trans->condSpace != 0 ) + transCondSpaces.value( trans->condSpace->condSpaceId ); + else + transCondSpaces.value( -1 ); + } + + /* Walk the ranges. */ + for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) { + RedTransAp *trans = rtel->value; + if ( trans->condSpace != 0 ) + transCondSpaces.value( trans->condSpace->condSpaceId ); + else + transCondSpaces.value( -1 ); + } + + /* The state's default index goes next. */ + if ( st->defTrans != 0 ) { + RedTransAp *trans = st->defTrans; + if ( trans->condSpace != 0 ) + transCondSpaces.value( trans->condSpace->condSpaceId ); + else + transCondSpaces.value( -1 ); + } + } + + /* Add any eof transitions that have not yet been written out above. */ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->eofTrans != 0 ) { + RedTransAp *trans = st->eofTrans; + if ( trans->condSpace != 0 ) + transCondSpaces.value( trans->condSpace->condSpaceId ); + else + transCondSpaces.value( -1 ); + } + } + + transCondSpaces.finish(); +} + +void Binary::taTransOffsets() +{ + transOffsets.start(); + + int curOffset = 0; + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + /* Walk the singles. */ + for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) { + RedTransAp *trans = stel->value; + transOffsets.value( curOffset ); + curOffset += trans->numConds(); + } + + /* Walk the ranges. */ + for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) { + RedTransAp *trans = rtel->value; + transOffsets.value( curOffset ); + curOffset += trans->numConds(); + } + + /* The state's default index goes next. */ + if ( st->defTrans != 0 ) { + RedTransAp *trans = st->defTrans; + transOffsets.value( curOffset ); + curOffset += trans->numConds(); + } + } + + /* Add any eof transitions that have not yet been written out above. */ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->eofTrans != 0 ) { + RedTransAp *trans = st->eofTrans; + transOffsets.value( curOffset ); + curOffset += trans->numConds(); + } + } + + errCondOffset = curOffset; + + transOffsets.finish(); +} + +void Binary::taTransLengths() +{ + transLengths.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + /* Walk the singles. */ + for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) { + RedTransAp *trans = stel->value; + transLengths.value( trans->numConds() ); + } + + /* Walk the ranges. */ + for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) { + RedTransAp *trans = rtel->value; + transLengths.value( trans->numConds() ); + } + + /* The state's default index goes next. */ + if ( st->defTrans != 0 ) { + RedTransAp *trans = st->defTrans; + transLengths.value( trans->numConds() ); + } + } + + /* Add any eof transitions that have not yet been written out above. */ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->eofTrans != 0 ) { + RedTransAp *trans = st->eofTrans; + transLengths.value( trans->numConds() ); + } + } + + transLengths.finish(); +} + +void Binary::taTransCondSpacesWi() +{ + transCondSpacesWi.start(); + + for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) { + /* Cond Space id. */ + if ( trans->condSpace != 0 ) + transCondSpacesWi.value( trans->condSpace->condSpaceId ); + else + transCondSpacesWi.value( -1 ); + } + + transCondSpacesWi.finish(); +} + +void Binary::taTransOffsetsWi() +{ + transOffsetsWi.start(); + + int curOffset = 0; + for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) { + transOffsetsWi.value( curOffset ); + + TransApSet::Iter next = trans; + next.increment(); + + curOffset += trans->numConds(); + } + + transOffsetsWi.finish(); +} + +void Binary::taTransLengthsWi() +{ + transLengthsWi.start(); + + for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) { + transLengthsWi.value( trans->numConds() ); + + TransApSet::Iter next = trans; + next.increment(); + } + + transLengthsWi.finish(); +} + +void Binary::taCondKeys() +{ + condKeys.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + /* Walk the singles. */ + for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) { + RedTransAp *trans = stel->value; + for ( int c = 0; c < trans->numConds(); c++ ) { + CondKey key = trans->outCondKey( c ); + condKeys.value( key.getVal() ); + } + } + + /* Walk the ranges. */ + for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) { + RedTransAp *trans = rtel->value; + for ( int c = 0; c < trans->numConds(); c++ ) { + CondKey key = trans->outCondKey( c ); + condKeys.value( key.getVal() ); + } + } + + /* The state's default index goes next. */ + if ( st->defTrans != 0 ) { + RedTransAp *trans = st->defTrans; + for ( int c = 0; c < trans->numConds(); c++ ) { + CondKey key = trans->outCondKey( c ); + condKeys.value( key.getVal() ); + } + } + } + + /* Add any eof transitions that have not yet been written out above. */ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->eofTrans != 0 ) { + RedTransAp *trans = st->eofTrans; + for ( int c = 0; c < trans->numConds(); c++ ) { + CondKey key = trans->outCondKey( c ); + condKeys.value( key.getVal() ); + } + } + } + + condKeys.finish(); +} + +void Binary::taCondTargs() +{ + condTargs.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + /* Walk the singles. */ + for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) { + RedTransAp *trans = stel->value; + for ( int c = 0; c < trans->numConds(); c++ ) { + RedCondPair *cond = trans->outCond( c ); + condTargs.value( cond->targ->id ); + } + } + + /* Walk the ranges. */ + for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) { + RedTransAp *trans = rtel->value; + for ( int c = 0; c < trans->numConds(); c++ ) { + RedCondPair *cond = trans->outCond( c ); + condTargs.value( cond->targ->id ); + } + } + + /* The state's default index goes next. */ + if ( st->defTrans != 0 ) { + RedTransAp *trans = st->defTrans; + for ( int c = 0; c < trans->numConds(); c++ ) { + RedCondPair *cond = trans->outCond( c ); + condTargs.value( cond->targ->id ); + } + } + } + + /* Add any eof transitions that have not yet been written out above. */ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->eofTrans != 0 ) { + RedTransAp *trans = st->eofTrans; + for ( int c = 0; c < trans->numConds(); c++ ) { + RedCondPair *cond = trans->outCond( c ); + condTargs.value( cond->targ->id ); + } + } + } + + if ( redFsm->errCond != 0 ) { + RedCondPair *cond = &redFsm->errCond->p; + condTargs.value( cond->targ->id ); + } + + condTargs.finish(); +} + +void Binary::taCondActions() +{ + condActions.start(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + /* Walk the singles. */ + for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) { + RedTransAp *trans = stel->value; + for ( int c = 0; c < trans->numConds(); c++ ) { + RedCondPair *cond = trans->outCond( c ); + COND_ACTION( cond ); + } + } + + /* Walk the ranges. */ + for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) { + RedTransAp *trans = rtel->value; + for ( int c = 0; c < trans->numConds(); c++ ) { + RedCondPair *cond = trans->outCond( c ); + COND_ACTION( cond ); + } + } + + /* The state's default index goes next. */ + if ( st->defTrans != 0 ) { + RedTransAp *trans = st->defTrans; + for ( int c = 0; c < trans->numConds(); c++ ) { + RedCondPair *cond = trans->outCond(c); + COND_ACTION( cond ); + } + } + } + + /* Add any eof transitions that have not yet been written out above. */ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->eofTrans != 0 ) { + RedTransAp *trans = st->eofTrans; + for ( int c = 0; c < trans->numConds(); c++ ) { + RedCondPair *cond = trans->outCond(c); + COND_ACTION( cond ); + } + } + } + + if ( redFsm->errCond != 0 ) { + RedCondPair *cond = &redFsm->errCond->p; + COND_ACTION( cond ); + } + + condActions.finish(); +} + +void Binary::taNfaTargs() +{ + nfaTargs.start(); + + /* Offset of zero means no NFA targs, put a filler there. */ + nfaTargs.value( 0 ); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->nfaTargs != 0 ) { + nfaTargs.value( st->nfaTargs->length() ); + for ( RedNfaTargs::Iter targ = *st->nfaTargs; targ.lte(); targ++ ) + nfaTargs.value( targ->state->id ); + } + } + + nfaTargs.finish(); +} + +/* These need to mirror nfa targs. */ +void Binary::taNfaPushActions() +{ + nfaPushActions.start(); + + nfaPushActions.value( 0 ); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->nfaTargs != 0 ) { + nfaPushActions.value( 0 ); + for ( RedNfaTargs::Iter targ = *st->nfaTargs; targ.lte(); targ++ ) + NFA_PUSH_ACTION( targ ); + } + } + + nfaPushActions.finish(); +} + +void Binary::taNfaPopTrans() +{ + nfaPopTrans.start(); + + nfaPopTrans.value( 0 ); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->nfaTargs != 0 ) { + + nfaPopTrans.value( 0 ); + + for ( RedNfaTargs::Iter targ = *st->nfaTargs; targ.lte(); targ++ ) + NFA_POP_TEST( targ ); + } + } + + nfaPopTrans.finish(); +} + +void Binary::taNfaOffsets() +{ + nfaOffsets.start(); + + /* Offset of zero means no NFA targs, real targs start at 1. */ + long offset = 1; + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->nfaTargs == 0 ) { + nfaOffsets.value( 0 ); + } + else { + nfaOffsets.value( offset ); + offset += 1 + st->nfaTargs->length(); + } + } + + nfaOffsets.finish(); +} + + +/* Write out the array of actions. */ +std::ostream &Binary::ACTIONS_ARRAY() +{ + out << "\t0, "; + int totalActions = 1; + for ( GenActionTableMap::Iter act = redFsm->actionMap; act.lte(); act++ ) { + /* Write out the length, which will never be the last character. */ + out << act->key.length() << ", "; + /* Put in a line break every 8 */ + if ( totalActions++ % 8 == 7 ) + out << "\n\t"; + + for ( GenActionTable::Iter item = act->key; item.lte(); item++ ) { + out << item->value->actionId; + if ( ! (act.last() && item.last()) ) + out << ", "; + + /* Put in a line break every 8 */ + if ( totalActions++ % 8 == 7 ) + out << "\n\t"; + } + } + out << "\n"; + return out; +} + +void Binary::taActions() +{ + actions.start(); + + /* Put "no-action" at the beginning. */ + actions.value( 0 ); + + for ( GenActionTableMap::Iter act = redFsm->actionMap; act.lte(); act++ ) { + /* Write out the length, which will never be the last character. */ + actions.value( act->key.length() ); + + for ( GenActionTable::Iter item = act->key; item.lte(); item++ ) + actions.value( item->value->actionId ); + } + + actions.finish(); +} + + + + |