diff options
Diffstat (limited to 'src/libfsm/ipgoto.cc')
| -rw-r--r-- | src/libfsm/ipgoto.cc | 764 |
1 files changed, 764 insertions, 0 deletions
diff --git a/src/libfsm/ipgoto.cc b/src/libfsm/ipgoto.cc new file mode 100644 index 00000000..3718ea91 --- /dev/null +++ b/src/libfsm/ipgoto.cc @@ -0,0 +1,764 @@ +/* + * 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 "ipgoto.h" +#include "redfsm.h" +#include "gendata.h" +#include "bstmap.h" +#include "parsedata.h" + +#include <sstream> + +using std::ostringstream; + +void IpGoto::tableDataPass() +{ + taNfaTargs(); + taNfaOffsets(); + taNfaPushActions(); + taNfaPopTrans(); +} + +void IpGoto::genAnalysis() +{ + /* For directly executable machines there is no required state + * ordering. Choose a depth-first ordering to increase the + * potential for fall-throughs. */ + redFsm->depthFirstOrdering(); + + /* Choose default transitions and the single transition. */ + redFsm->chooseDefaultSpan(); + + /* Choose single. */ + redFsm->moveSelectTransToSingle(); + + /* If any errors have occured in the input file then don't write anything. */ + if ( red->id->errorCount > 0 ) + return; + + redFsm->setInTrans(); + + /* 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(); + + /* Run the analysis pass over the table data. */ + setTableState( TableArray::AnalyzePass ); + tableDataPass(); + + /* Switch the tables over to the code gen mode. */ + setTableState( TableArray::GeneratePass ); +} + +bool IpGoto::useAgainLabel() +{ + return redFsm->anyActionRets() || + redFsm->anyActionByValControl() || + redFsm->anyRegNextStmt(); +} + +void IpGoto::GOTO( ostream &ret, int gotoDest, bool inFinish ) +{ + ret << OPEN_GEN_BLOCK(); + + ret << "goto " << stLabel[gotoDest].reference() << ";"; + + ret << CLOSE_GEN_BLOCK(); +} + +void IpGoto::GOTO_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish ) +{ + ret << OPEN_GEN_BLOCK() << vCS() << " = " << OPEN_HOST_EXPR(); + INLINE_LIST( ret, ilItem->children, 0, inFinish, false ); + ret << CLOSE_HOST_EXPR() << ";"; + + ret << " goto " << _again << ";"; + + ret << CLOSE_GEN_BLOCK(); +} + +void IpGoto::CALL( ostream &ret, int callDest, int targState, bool inFinish ) +{ + ret << OPEN_GEN_BLOCK(); + + if ( red->prePushExpr != 0 ) { + ret << OPEN_HOST_BLOCK( red->prePushExpr ); + INLINE_LIST( ret, red->prePushExpr->inlineList, 0, false, false ); + ret << CLOSE_HOST_BLOCK(); + } + + ret << STACK() << "[" << TOP() << "] = " << targState << + "; " << TOP() << "+= 1; "; + + ret << "goto " << stLabel[callDest].reference() << ";"; + + ret << CLOSE_GEN_BLOCK(); +} + +void IpGoto::NCALL( ostream &ret, int callDest, int targState, bool inFinish ) +{ + ret << OPEN_GEN_BLOCK(); + + if ( red->prePushExpr != 0 ) { + ret << OPEN_HOST_BLOCK( red->prePushExpr ); + INLINE_LIST( ret, red->prePushExpr->inlineList, 0, false, false ); + ret << CLOSE_HOST_BLOCK(); + } + + ret << STACK() << "[" << TOP() << "] = " << targState << + "; " << TOP() << "+= 1; " << vCS() << " = " << callDest << "; " << + CLOSE_GEN_BLOCK(); +} + +void IpGoto::CALL_EXPR( ostream &ret, GenInlineItem *ilItem, int targState, bool inFinish ) +{ + ret << OPEN_GEN_BLOCK(); + + if ( red->prePushExpr != 0 ) { + ret << OPEN_HOST_BLOCK( red->prePushExpr ); + INLINE_LIST( ret, red->prePushExpr->inlineList, 0, false, false ); + ret << CLOSE_HOST_BLOCK(); + } + + ret << STACK() << "[" << TOP() << "] = " << targState << "; " << TOP() << "+= 1;" << + vCS() << " = " << OPEN_HOST_EXPR(); + INLINE_LIST( ret, ilItem->children, 0, inFinish, false ); + ret << CLOSE_HOST_EXPR() << ";"; + + ret << " goto " << _again << ";"; + + ret << CLOSE_GEN_BLOCK(); +} + +void IpGoto::NCALL_EXPR( ostream &ret, GenInlineItem *ilItem, int targState, bool inFinish ) +{ + ret << OPEN_GEN_BLOCK(); + + if ( red->prePushExpr != 0 ) { + ret << OPEN_HOST_BLOCK( red->prePushExpr ); + INLINE_LIST( ret, red->prePushExpr->inlineList, 0, false, false ); + ret << CLOSE_HOST_BLOCK(); + } + + ret << STACK() << "[" << TOP() << "] = " << targState << "; " << TOP() << "+= 1;" << + vCS() << " = " << OPEN_HOST_EXPR(); + INLINE_LIST( ret, ilItem->children, 0, inFinish, false ); + ret << CLOSE_HOST_EXPR() << "; " << CLOSE_GEN_BLOCK(); +} + +void IpGoto::RET( ostream &ret, bool inFinish ) +{ + ret << OPEN_GEN_BLOCK() << TOP() << " -= 1;" << vCS() << " = " + << STACK() << "[" << TOP() << "];"; + + if ( red->postPopExpr != 0 ) { + ret << OPEN_HOST_BLOCK( red->postPopExpr ); + INLINE_LIST( ret, red->postPopExpr->inlineList, 0, false, false ); + ret << CLOSE_HOST_BLOCK(); + } + + ret << "goto " << _again << ";" << CLOSE_GEN_BLOCK(); +} + +void IpGoto::NRET( ostream &ret, bool inFinish ) +{ + ret << OPEN_GEN_BLOCK() << TOP() << " -= 1;" << vCS() << " = " + << STACK() << "[" << TOP() << "];"; + + if ( red->postPopExpr != 0 ) { + ret << OPEN_HOST_BLOCK( red->postPopExpr ); + INLINE_LIST( ret, red->postPopExpr->inlineList, 0, false, false ); + ret << CLOSE_HOST_BLOCK(); + } + + ret << CLOSE_GEN_BLOCK(); +} + +void IpGoto::NEXT( ostream &ret, int nextDest, bool inFinish ) +{ + ret << vCS() << " = " << nextDest << ";"; +} + +void IpGoto::NEXT_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish ) +{ + ret << vCS() << " = ("; + INLINE_LIST( ret, ilItem->children, 0, inFinish, false ); + ret << ");"; +} + +void IpGoto::CURS( ostream &ret, bool inFinish ) +{ + ret << "(" << ps << ")"; +} + +void IpGoto::TARGS( ostream &ret, bool inFinish, int targState ) +{ + ret << targState; +} + +void IpGoto::BREAK( ostream &ret, int targState, bool csForced ) +{ + ret << OPEN_GEN_BLOCK() << P() << "+= 1; "; + if ( !csForced ) + ret << vCS() << " = " << targState << "; "; + ret << "goto " << _out << ";" << CLOSE_GEN_BLOCK(); +} + +void IpGoto::NBREAK( ostream &ret, int targState, bool csForced ) +{ + ret << OPEN_GEN_BLOCK() << P() << "+= 1; "; + if ( !csForced ) + ret << vCS() << " = " << targState << "; "; + ret << nbreak << " = 1;" << CLOSE_GEN_BLOCK(); +} + +void IpGoto::NFA_PUSH_ACTION( RedNfaTarg *targ ) +{ + int act = 0; + if ( targ->push != 0 ) + act = targ->push->actListId+1; + nfaPushActions.value( act ); +} + +void IpGoto::NFA_POP_TEST( RedNfaTarg *targ ) +{ + int act = 0; + if ( targ->popTest != 0 ) + act = targ->popTest->actListId+1; + nfaPopTrans.value( act ); +} + + +bool IpGoto::IN_TRANS_ACTIONS( RedStateAp *state ) +{ + bool anyWritten = false; + + /* Emit any transitions that have actions and that go to this state. */ + for ( int it = 0; it < state->numInConds; it++ ) { + RedCondPair *trans = state->inConds[it]; + if ( trans->action != 0 ) { + /* Remember that we wrote an action so we know to write the + * line directive for going back to the output. */ + anyWritten = true; + + /* Write the label for the transition so it can be jumped to. */ + if ( ctrLabel[trans->id].isReferenced ) + out << "_ctr" << trans->id << ":\n"; + + /* If the action contains a next, then we must preload the current + * state since the action may or may not set it. */ + if ( trans->action->anyNextStmt() ) + out << " " << vCS() << " = " << trans->targ->id << ";\n"; + + if ( redFsm->anyRegNbreak() ) + out << nbreak << " = 0;\n"; + + /* Write each action in the list. */ + for ( GenActionTable::Iter item = trans->action->key; item.lte(); item++ ) { + ACTION( out, item->value, IlOpts( trans->targ->id, false, + trans->action->anyNextStmt() ) ); + out << "\n"; + } + + if ( redFsm->anyRegNbreak() ) { + out << + "if ( " << nbreak << " == 1 )\n" + " goto " << _out << ";\n"; + } + + + /* If the action contains a next then we need to reload, otherwise + * jump directly to the target state. */ + if ( trans->action->anyNextStmt() ) + out << "goto " << _again << ";\n"; + else + out << "goto " << stLabel[trans->targ->id].reference() << ";\n"; + } + } + + + return anyWritten; +} + +void IpGoto::GOTO_HEADER( RedStateAp *state ) +{ +} + +void IpGoto::STATE_GOTO_ERROR() +{ +} + + +/* Emit the goto to take for a given transition. */ +std::ostream &IpGoto::TRANS_GOTO( RedTransAp *trans ) +{ + if ( trans->condSpace == 0 || trans->condSpace->condSet.length() == 0 ) { + /* Existing. */ + assert( trans->numConds() == 1 ); + RedCondPair *cond = trans->outCond( 0 ); + if ( cond->action != 0 ) { + /* Go to the transition which will go to the state. */ + out << "goto " << ctrLabel[trans->p.id].reference() << ";"; + } + else { + /* Go directly to the target state. */ + out << "goto " << stLabel[cond->targ->id].reference() << ";"; + } + } + else { + out << ck << " = 0;\n"; + for ( GenCondSet::Iter csi = trans->condSpace->condSet; csi.lte(); csi++ ) { + out << "if ( "; + CONDITION( out, *csi ); + Size condValOffset = (1 << csi.pos()); + out << " )\n" << ck << " += " << condValOffset << ";\n"; + } + CondKey lower = 0; + CondKey upper = trans->condFullSize() - 1; + COND_B_SEARCH( trans, lower, upper, 0, trans->numConds() - 1 ); + + if ( trans->errCond() != 0 ) { + COND_GOTO( trans->errCond() ) << "\n"; + } + } + + return out; +} + +/* Emit the goto to take for a given transition. */ +std::ostream &IpGoto::COND_GOTO( RedCondPair *cond ) +{ + /* Existing. */ + if ( cond->action != 0 ) { + /* Go to the transition which will go to the state. */ + out << "goto " << ctrLabel[cond->id].reference() << ";"; + } + else { + /* Go directly to the target state. */ + out << "goto " << stLabel[cond->targ->id].reference() << ";"; + } + + return out; +} + +std::ostream &IpGoto::EXIT_STATES() +{ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( outLabel[st->id].isReferenced ) { + out << outLabel[st->id].define() << ": " << vCS() << " = " << + st->id << "; goto " << _out << "; \n"; + } + if ( popLabel[st->id].isReferenced ) { + out << popLabel[st->id].define() << ": " << vCS() << " = " << + st->id << "; goto " << _pop << "; \n"; + } + } + return out; +} + +std::ostream &IpGoto::AGAIN_CASES() +{ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + out << + "case " << st->id << ": goto " << stLabel[st->id].reference() << ";\n"; + } + return out; +} + +std::ostream &IpGoto::STATE_GOTO_CASES() +{ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + out << "case " << st->id << ":\n"; + out << "goto st_case_" << st->id << ";\n"; + } + return out; +} + +void IpGoto::NFA_PUSH_ST( RedStateAp *state ) +{ + std::stringstream ss; + ss << state->id; + std::string _state = ss.str(); + + if ( redFsm->anyNfaStates() ) { + + if ( state->nfaTargs != 0 ) { + out << + "if ( " << ARR_REF( nfaOffsets ) << "[" << _state << "] != 0 ) {\n"; + + if ( red->nfaPrePushExpr != 0 ) { + out << + new_recs << " = " << state->nfaTargs->length() << ";\n"; + } + + if ( red->nfaPrePushExpr != 0 ) { + out << OPEN_HOST_BLOCK( red->nfaPrePushExpr ); + INLINE_LIST( out, red->nfaPrePushExpr->inlineList, 0, false, false ); + out << CLOSE_HOST_BLOCK(); + } + + int alt = 0; + for ( RedNfaTargs::Iter nt = *state->nfaTargs; nt.lte(); nt++ ) { + out << + " nfa_bp[nfa_len].state = " << nt->state->id << ";\n" + " nfa_bp[nfa_len].p = " << P() << ";\n"; + + if ( nt->popTest != 0 ) { + out << + " nfa_bp[nfa_len].popTrans = " << (nt->popTest->actListId+1) << ";\n"; + } + else if ( redFsm->bAnyNfaPops ) { + out << + " nfa_bp[nfa_len].popTrans = 0;\n"; + } + + if ( nt->push != 0 ) { + for ( GenActionTable::Iter item = nt->push->key; item.lte(); item++ ) + ACTION( out, item->value, IlOpts( 0, false, false ) ); + } + + out << + " nfa_len += 1;\n"; + + alt += 1; + } + + out << + "}\n"; + } + } +} + +std::ostream &IpGoto::STATE_GOTOS() +{ + bool eof = redFsm->anyEofActivity() || redFsm->anyNfaStates(); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + IN_TRANS_ACTIONS( st ); + + if ( stLabel[st->id].isReferenced ) + out << "_st" << st->id << ":\n"; + + /* Need to do this if the transition is an eof transition, or if + * the action contains fexec. Otherwise, no need. */ + if ( eof ) { + out << + "if ( " << P() << " == " << vEOF() << " )\n"; + + if ( st->isFinal || !redFsm->anyNfaStates() ) + out << "goto " << outLabel[st->id].reference() << ";\n"; + else + out << "goto " << popLabel[st->id].reference() << ";\n"; + } + + if ( st->toStateAction != 0 ) { + /* Write every action in the list. */ + for ( GenActionTable::Iter item = st->toStateAction->key; item.lte(); item++ ) { + ACTION( out, item->value, IlOpts( st->id, false, + st->toStateAction->anyNextStmt() ) ); + out << "\n"; + } + } + + if ( st == redFsm->errState ) { + out << "st_case_" << st->id << ":\n"; + + /* Break out here. */ + if ( !redFsm->anyNfaStates() ) + out << "goto " << outLabel[st->id].reference() << ";\n"; + else + out << "goto " << popLabel[st->id].reference() << ";\n"; + } + else { + + /* Advance and test buffer pos. */ + if ( st->labelNeeded ) { + out << + P() << "+= 1;\n"; + } + + /* Give the st a switch case. */ + out << "st_case_" << st->id << ":\n"; + + if ( !noEnd ) { + if ( eof ) { + out << + "if ( " << P() << " == " << PE() << " && " << P() << " != " << vEOF() << " )\n" + " goto " << outLabel[st->id].reference() << ";\n"; + } + else { + out << + "if ( " << P() << " == " << PE() << " )\n" + " goto " << outLabel[st->id].reference() << ";\n"; + } + } + + + NFA_PUSH_ST( st ); + + if ( st->fromStateAction != 0 ) { + /* Write every action in the list. */ + for ( GenActionTable::Iter item = st->fromStateAction->key; item.lte(); item++ ) { + ACTION( out, item->value, IlOpts( st->id, false, + st->fromStateAction->anyNextStmt() ) ); + out << "\n"; + } + } + + if ( !noEnd && eof ) { + out << + "if ( " << P() << " == " << vEOF() << " ) {\n"; + + if ( st->eofTrans != 0 ) + TRANS_GOTO( st->eofTrans ); + else { + if ( st->isFinal || !redFsm->anyNfaStates() ) + out << "goto " << outLabel[st->id].reference() << ";\n"; + else + out << "goto " << popLabel[st->id].reference() << ";\n"; + } + + out << + "}\n" + "else {\n"; + } + + /* Record the prev st if necessary. */ + if ( st->anyRegCurStateRef() ) + out << ps << " = " << st->id << ";\n"; + + /* Try singles. */ + if ( st->outSingle.length() > 0 ) + SINGLE_SWITCH( st ); + + /* Default case is to binary search for the ranges, if that fails then */ + if ( st->outRange.length() > 0 ) { + RANGE_B_SEARCH( st, keyOps->minKey, keyOps->maxKey, + 0, st->outRange.length() - 1 ); + } + + /* Write the default transition. */ + TRANS_GOTO( st->defTrans ) << "\n"; + + if ( !noEnd && eof ) { + out << + "}\n"; + } + } + } + return out; +} + +std::ostream &IpGoto::FINISH_CASES() +{ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->eofTrans != 0 ) { + out << + "case " << st->id << ":\n"; + + TRANS_GOTO( st->eofTrans ); + } + } + + return out; +} + +void IpGoto::setLabelsNeeded( GenInlineList *inlineList ) +{ + for ( GenInlineList::Iter item = *inlineList; item.lte(); item++ ) { + switch ( item->type ) { + case GenInlineItem::Goto: + case GenInlineItem::Call: + case GenInlineItem::Ncall: { + /* Mark the target as needing a label. */ + item->targState->labelNeeded = true; + break; + } + default: break; + } + + if ( item->children != 0 ) + setLabelsNeeded( item->children ); + } +} + +void IpGoto::setLabelsNeeded( RedCondPair *pair ) +{ + /* If there is no action with a next statement, then the label will be + * needed. */ + if ( pair->action == 0 || !pair->action->anyNextStmt() ) + pair->targ->labelNeeded = true; + + /* Need labels for states that have goto or calls in action code + * invoked on characters (ie, not from out action code). */ + if ( pair->action != 0 ) { + /* Loop the actions. */ + for ( GenActionTable::Iter act = pair->action->key; act.lte(); act++ ) { + /* Get the action and walk it's tree. */ + setLabelsNeeded( act->value->inlineList ); + } + } +} + +/* Set up labelNeeded flag for each state. */ +void IpGoto::setLabelsNeeded() +{ + /* If we use the _again label, then we generate the _again switch, which + * uses all labels. */ + if ( useAgainLabel() ) { + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) + st->labelNeeded = true; + } + else { + /* Do not use all labels by default, init all labelNeeded vars to false. */ + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) + st->labelNeeded = false; + + for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) { + if ( trans->condSpace == 0 ) + setLabelsNeeded( &trans->p ); + } + + for ( CondApSet::Iter cond = redFsm->condSet; cond.lte(); cond++ ) + setLabelsNeeded( &cond->p ); + + for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) { + if ( st->eofAction != 0 ) { + for ( GenActionTable::Iter item = st->eofAction->key; item.lte(); item++ ) + setLabelsNeeded( item->value->inlineList ); + } + } + } +} + +void IpGoto::writeData() +{ + STATE_IDS(); + + taNfaTargs(); + taNfaOffsets(); + taNfaPushActions(); + taNfaPopTrans(); +} + +void IpGoto::NFA_FROM_STATE_ACTION_EXEC() +{ +// if ( redFsm->anyFromStateActions() ) { +// /* Unimplemented feature. Don't have the from state actions array in +// * this mode. Need to add it, or to alter the NFA pop codegen to be +// * consistent with the mode. */ +// assert( false ); +// } +} + +void IpGoto::writeExec() +{ + int maxCtrId = redFsm->nextCondId > redFsm->nextTransId ? redFsm->nextCondId : redFsm->nextTransId; + + stLabel = allocateLabels( stLabel, IpLabel::St, redFsm->nextStateId ); + ctrLabel = allocateLabels( ctrLabel, IpLabel::Ctr, maxCtrId ); + outLabel = allocateLabels( outLabel, IpLabel::Out, redFsm->nextStateId ); + popLabel = allocateLabels( popLabel, IpLabel::Pop, redFsm->nextStateId ); + + /* Must set labels immediately before writing because we may depend on the + * noend write option. */ + setLabelsNeeded(); + + out << "{\n"; + + DECLARE( INT(), cpc ); + DECLARE( INT(), ck ); + DECLARE( INT(), pop_test ); + DECLARE( INT(), nbreak ); + DECLARE( INT(), ps ); + DECLARE( INT(), new_recs ); + DECLARE( INT(), alt ); + + if ( _again.isReferenced ) { + out << + " goto " << _resume << ";\n" + "\n"; + + out << EMIT_LABEL( _again ); + + out << + " switch ( " << vCS() << " ) {\n"; + AGAIN_CASES() << + " }\n" + "\n"; + + } + + out << EMIT_LABEL( _resume ); + + out << "switch ( " << vCS() << " ) {\n"; + + STATE_GOTO_CASES(); + + out << "}\n"; + + STATE_GOTOS(); + + EXIT_STATES(); + + out << EMIT_LABEL( _pop ); + + if ( redFsm->anyNfaStates() ) { + out << + "if ( nfa_len == 0 )\n" + " goto " << _out << ";\n" + "\n"; + + out << + "nfa_count += 1;\n" + "nfa_len -= 1;\n" << + P() << " = nfa_bp[nfa_len].p;\n"; + + if ( redFsm->bAnyNfaPops ) { + NFA_FROM_STATE_ACTION_EXEC(); + + NFA_POP_TEST_EXEC(); + + out << + "if ( " << pop_test << " )\n" + " " << vCS() << " = nfa_bp[nfa_len].state;\n" + "else\n" + " " << vCS() << " = " << ERROR_STATE() << ";\n"; + } + else { + out << + vCS() << " = nfa_bp[nfa_len].state;\n"; + + } + + NFA_POST_POP(); + + out << "goto " << _resume << ";\n"; + } + + out << EMIT_LABEL( _out ); + + out << + "}\n"; +} |