2 * Copyright 2004-2006 Adrian Thurston <thurston@cs.queensu.ca>
3 * 2004 Erich Ocean <eric.ocean@ampede.com>
4 * 2005 Alan West <alan@alanz.com>
7 /* This file is part of Ragel.
9 * Ragel is free software; you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation; either version 2 of the License, or
12 * (at your option) any later version.
14 * Ragel is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
19 * You should have received a copy of the GNU General Public License
20 * along with Ragel; if not, write to the Free Software
21 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25 #include "flatcodegen.h"
29 std::ostream &FlatCodeGen::TO_STATE_ACTION( RedStateAp *state )
32 if ( state->toStateAction != 0 )
33 act = state->toStateAction->location+1;
38 std::ostream &FlatCodeGen::FROM_STATE_ACTION( RedStateAp *state )
41 if ( state->fromStateAction != 0 )
42 act = state->fromStateAction->location+1;
47 std::ostream &FlatCodeGen::EOF_ACTION( RedStateAp *state )
50 if ( state->eofAction != 0 )
51 act = state->eofAction->location+1;
56 std::ostream &FlatCodeGen::TRANS_ACTION( RedTransAp *trans )
58 /* If there are actions, emit them. Otherwise emit zero. */
60 if ( trans->action != 0 )
61 act = trans->action->location+1;
66 std::ostream &FlatCodeGen::TO_STATE_ACTION_SWITCH()
68 /* Walk the list of functions, printing the cases. */
69 for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
70 /* Write out referenced actions. */
71 if ( act->numToStateRefs > 0 ) {
72 /* Write the case label, the action and the case break */
73 out << "\tcase " << act->actionId << ":\n";
74 ACTION( out, act, 0, false );
79 genLineDirective( out );
83 std::ostream &FlatCodeGen::FROM_STATE_ACTION_SWITCH()
85 /* Walk the list of functions, printing the cases. */
86 for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
87 /* Write out referenced actions. */
88 if ( act->numFromStateRefs > 0 ) {
89 /* Write the case label, the action and the case break */
90 out << "\tcase " << act->actionId << ":\n";
91 ACTION( out, act, 0, false );
96 genLineDirective( out );
100 std::ostream &FlatCodeGen::EOF_ACTION_SWITCH()
102 /* Walk the list of functions, printing the cases. */
103 for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
104 /* Write out referenced actions. */
105 if ( act->numEofRefs > 0 ) {
106 /* Write the case label, the action and the case break */
107 out << "\tcase " << act->actionId << ":\n";
108 ACTION( out, act, 0, true );
113 genLineDirective( out );
118 std::ostream &FlatCodeGen::ACTION_SWITCH()
120 /* Walk the list of functions, printing the cases. */
121 for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
122 /* Write out referenced actions. */
123 if ( act->numTransRefs > 0 ) {
124 /* Write the case label, the action and the case break */
125 out << "\tcase " << act->actionId << ":\n";
126 ACTION( out, act, 0, false );
131 genLineDirective( out );
136 std::ostream &FlatCodeGen::FLAT_INDEX_OFFSET()
139 int totalStateNum = 0, curIndOffset = 0;
140 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
141 /* Write the index offset. */
145 if ( ++totalStateNum % IALL == 0 )
149 /* Move the index offset ahead. */
150 if ( st->transList != 0 )
151 curIndOffset += keyOps->span( st->lowKey, st->highKey );
153 if ( st->defTrans != 0 )
160 std::ostream &FlatCodeGen::KEY_SPANS()
163 int totalStateNum = 0;
164 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
165 /* Write singles length. */
166 unsigned long long span = 0;
167 if ( st->transList != 0 )
168 span = keyOps->span( st->lowKey, st->highKey );
172 if ( ++totalStateNum % IALL == 0 )
180 std::ostream &FlatCodeGen::TO_STATE_ACTIONS()
183 int totalStateNum = 0;
184 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
185 /* Write any eof action. */
189 if ( ++totalStateNum % IALL == 0 )
197 std::ostream &FlatCodeGen::FROM_STATE_ACTIONS()
200 int totalStateNum = 0;
201 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
202 /* Write any eof action. */
203 FROM_STATE_ACTION(st);
206 if ( ++totalStateNum % IALL == 0 )
214 std::ostream &FlatCodeGen::EOF_ACTIONS()
217 int totalStateNum = 0;
218 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
219 /* Write any eof action. */
223 if ( ++totalStateNum % IALL == 0 )
231 std::ostream &FlatCodeGen::COND_KEYS()
235 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
236 /* Emit just cond low key and cond high key. */
237 out << KEY( st->condLowKey ) << ", ";
238 out << KEY( st->condHighKey ) << ", ";
239 if ( ++totalTrans % IALL == 0 )
243 /* Output one last number so we don't have to figure out when the last
244 * entry is and avoid writing a comma. */
249 std::ostream &FlatCodeGen::COND_KEY_SPANS()
252 int totalStateNum = 0;
253 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
254 /* Write singles length. */
255 unsigned long long span = 0;
256 if ( st->condList != 0 )
257 span = keyOps->span( st->condLowKey, st->condHighKey );
261 if ( ++totalStateNum % IALL == 0 )
269 std::ostream &FlatCodeGen::CONDS()
273 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
274 if ( st->condList != 0 ) {
275 /* Walk the singles. */
276 unsigned long long span = keyOps->span( st->condLowKey, st->condHighKey );
277 for ( unsigned long long pos = 0; pos < span; pos++ ) {
278 if ( st->condList[pos] != 0 )
279 out << st->condList[pos]->condSpaceId + 1 << ", ";
282 if ( ++totalTrans % IALL == 0 )
288 /* Output one last number so we don't have to figure out when the last
289 * entry is and avoid writing a comma. */
294 std::ostream &FlatCodeGen::COND_INDEX_OFFSET()
297 int totalStateNum = 0, curIndOffset = 0;
298 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
299 /* Write the index offset. */
303 if ( ++totalStateNum % IALL == 0 )
307 /* Move the index offset ahead. */
308 if ( st->condList != 0 )
309 curIndOffset += keyOps->span( st->condLowKey, st->condHighKey );
316 std::ostream &FlatCodeGen::KEYS()
320 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
321 /* Emit just low key and high key. */
322 out << KEY( st->lowKey ) << ", ";
323 out << KEY( st->highKey ) << ", ";
324 if ( ++totalTrans % IALL == 0 )
328 /* Output one last number so we don't have to figure out when the last
329 * entry is and avoid writing a comma. */
334 std::ostream &FlatCodeGen::INDICIES()
338 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
339 if ( st->transList != 0 ) {
340 /* Walk the singles. */
341 unsigned long long span = keyOps->span( st->lowKey, st->highKey );
342 for ( unsigned long long pos = 0; pos < span; pos++ ) {
343 out << st->transList[pos]->id << ", ";
344 if ( ++totalTrans % IALL == 0 )
349 /* The state's default index goes next. */
350 if ( st->defTrans != 0 )
351 out << st->defTrans->id << ", ";
353 if ( ++totalTrans % IALL == 0 )
357 /* Output one last number so we don't have to figure out when the last
358 * entry is and avoid writing a comma. */
363 std::ostream &FlatCodeGen::TRANS_TARGS()
365 /* Transitions must be written ordered by their id. */
366 RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
367 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
368 transPtrs[trans->id] = trans;
370 /* Keep a count of the num of items in the array written. */
373 for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
374 /* Write out the target state. */
375 RedTransAp *trans = transPtrs[t];
376 out << trans->targ->id;
377 if ( t < redFsm->transSet.length()-1 ) {
379 if ( ++totalStates % IALL == 0 )
389 std::ostream &FlatCodeGen::TRANS_ACTIONS()
391 /* Transitions must be written ordered by their id. */
392 RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
393 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
394 transPtrs[trans->id] = trans;
396 /* Keep a count of the num of items in the array written. */
399 for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
400 /* Write the function for the transition. */
401 RedTransAp *trans = transPtrs[t];
402 TRANS_ACTION( trans );
403 if ( t < redFsm->transSet.length()-1 ) {
405 if ( ++totalAct % IALL == 0 )
414 void FlatCodeGen::LOCATE_TRANS()
417 " _keys = " << ARR_OFF( K(), "(" + CS() + "<<1)" ) << ";\n"
418 " _inds = " << ARR_OFF( I(), IO() + "[" + CS() + "]" ) << ";\n"
420 " _slen = " << SP() << "[" << CS() << "];\n"
421 " _trans = _inds[ _slen > 0 && _keys[0] <=" << GET_WIDE_KEY() << " &&\n"
422 " " << GET_WIDE_KEY() << " <= _keys[1] ?\n"
423 " " << GET_WIDE_KEY() << " - _keys[0] : _slen ];\n"
427 void FlatCodeGen::GOTO( ostream &ret, int gotoDest, bool inFinish )
429 ret << "{" << CS() << " = " << gotoDest << "; " <<
430 CTRL_FLOW() << "goto _again;}";
433 void FlatCodeGen::GOTO_EXPR( ostream &ret, InlineItem *ilItem, bool inFinish )
435 ret << "{" << CS() << " = (";
436 INLINE_LIST( ret, ilItem->children, 0, inFinish );
437 ret << "); " << CTRL_FLOW() << "goto _again;}";
440 void FlatCodeGen::CURS( ostream &ret, bool inFinish )
445 void FlatCodeGen::TARGS( ostream &ret, bool inFinish, int targState )
447 ret << "(" << CS() << ")";
450 void FlatCodeGen::NEXT( ostream &ret, int nextDest, bool inFinish )
452 ret << CS() << " = " << nextDest << ";";
455 void FlatCodeGen::NEXT_EXPR( ostream &ret, InlineItem *ilItem, bool inFinish )
457 ret << CS() << " = (";
458 INLINE_LIST( ret, ilItem->children, 0, inFinish );
462 void FlatCodeGen::CALL( ostream &ret, int callDest, int targState, bool inFinish )
464 ret << "{" << STACK() << "[" << TOP() << "++] = " << CS() << "; " << CS() << " = " <<
465 callDest << "; " << CTRL_FLOW() << "goto _again;}";
469 void FlatCodeGen::CALL_EXPR( ostream &ret, InlineItem *ilItem, int targState, bool inFinish )
471 ret << "{" << STACK() << "[" << TOP() << "++] = " << CS() << "; " << CS() << " = (";
472 INLINE_LIST( ret, ilItem->children, targState, inFinish );
473 ret << "); " << CTRL_FLOW() << "goto _again;}";
477 void FlatCodeGen::RET( ostream &ret, bool inFinish )
479 ret << "{" << CS() << " = " << STACK() << "[--" << TOP() << "]; " <<
480 CTRL_FLOW() << "goto _again;}";
483 void FlatCodeGen::BREAK( ostream &ret, int targState )
486 ret << CTRL_FLOW() << "goto _out;";
489 void FlatCodeGen::writeData()
491 /* If there are any transtion functions then output the array. If there
492 * are none, don't bother emitting an empty array that won't be used. */
493 if ( redFsm->anyActions() ) {
494 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActArrItem), A() );
500 if ( redFsm->anyConditions() ) {
501 OPEN_ARRAY( WIDE_ALPH_TYPE(), CK() );
506 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondSpan), CSP() );
511 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCond), C() );
516 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondIndexOffset), CO() );
522 OPEN_ARRAY( WIDE_ALPH_TYPE(), K() );
527 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxSpan), SP() );
532 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxFlatIndexOffset), IO() );
537 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex), I() );
542 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
547 if ( redFsm->anyActions() ) {
548 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
554 if ( redFsm->anyToStateActions() ) {
555 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
561 if ( redFsm->anyFromStateActions() ) {
562 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
563 FROM_STATE_ACTIONS();
568 if ( redFsm->anyEofActions() ) {
569 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), EA() );
578 void FlatCodeGen::COND_TRANSLATE()
581 " _widec = " << GET_KEY() << ";\n";
584 " _keys = " << ARR_OFF( CK(), "(" + CS() + "<<1)" ) << ";\n"
585 " _conds = " << ARR_OFF( C(), CO() + "[" + CS() + "]" ) << ";\n"
587 " _slen = " << CSP() << "[" << CS() << "];\n"
588 " _cond = _slen > 0 && _keys[0] <=" << GET_WIDE_KEY() << " &&\n"
589 " " << GET_WIDE_KEY() << " <= _keys[1] ?\n"
590 " _conds[" << GET_WIDE_KEY() << " - _keys[0]] : 0;\n"
594 " switch ( _cond ) {\n";
595 for ( CondSpaceList::Iter csi = condSpaceList; csi.lte(); csi++ ) {
596 CondSpace *condSpace = csi;
597 out << " case " << condSpace->condSpaceId + 1 << ": {\n";
598 out << TABS(2) << "_widec = " << CAST(WIDE_ALPH_TYPE()) << "(" <<
599 KEY(condSpace->baseKey) << " + (" << GET_KEY() <<
600 " - " << KEY(keyOps->minKey) << "));\n";
602 for ( CondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
603 out << TABS(2) << "if ( ";
604 CONDITION( out, *csi );
605 Size condValOffset = ((1 << csi.pos()) * keyOps->alphSize());
606 out << " ) _widec += " << condValOffset << ";\n";
619 void FlatCodeGen::writeExec()
621 outLabelUsed = false;
627 if ( redFsm->anyRegCurStateRef() )
634 if ( redFsm->anyConditions() )
638 if ( redFsm->anyToStateActions() ||
639 redFsm->anyRegActions() || redFsm->anyFromStateActions() )
642 " " << PTR_CONST() << ARRAY_TYPE(redFsm->maxActArrItem) << POINTER() << "_acts;\n"
643 " " << UINT() << " _nacts;\n";
647 " " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_keys;\n"
648 " " << PTR_CONST() << ARRAY_TYPE(redFsm->maxIndex) << POINTER() << "_inds;\n";
650 if ( redFsm->anyConditions() ) {
652 " " << PTR_CONST() << ARRAY_TYPE(redFsm->maxCond) << POINTER() << "_conds;\n"
653 " " << WIDE_ALPH_TYPE() << " _widec;\n";
661 " if ( " << P() << " == " << PE() << " )\n"
665 if ( redFsm->errState != 0 ) {
668 " if ( " << CS() << " == " << redFsm->errState->id << " )\n"
674 if ( redFsm->anyFromStateActions() ) {
676 " _acts = " << ARR_OFF( A(), FSA() + "[" + CS() + "]" ) << ";\n"
677 " _nacts = " << CAST(UINT()) << " *_acts++;\n"
678 " while ( _nacts-- > 0 ) {\n"
679 " switch ( *_acts++ ) {\n";
680 FROM_STATE_ACTION_SWITCH();
687 if ( redFsm->anyConditions() )
692 if ( redFsm->anyRegCurStateRef() )
693 out << " _ps = " << CS() << ";\n";
696 " " << CS() << " = " << TT() << "[_trans];\n"
699 if ( redFsm->anyRegActions() ) {
701 " if ( " << TA() << "[_trans] == 0 )\n"
704 " _acts = " << ARR_OFF( A(), TA() + "[_trans]" ) << ";\n"
705 " _nacts = " << CAST(UINT()) << " *_acts++;\n"
706 " while ( _nacts-- > 0 ) {\n"
707 " switch ( *(_acts++) )\n {\n";
715 if ( redFsm->anyRegActions() || redFsm->anyActionGotos() ||
716 redFsm->anyActionCalls() || redFsm->anyActionRets() )
719 if ( redFsm->anyToStateActions() ) {
721 " _acts = " << ARR_OFF( A(), TSA() + "[" + CS() + "]" ) << ";\n"
722 " _nacts = " << CAST(UINT()) << " *_acts++;\n"
723 " while ( _nacts-- > 0 ) {\n"
724 " switch ( *_acts++ ) {\n";
725 TO_STATE_ACTION_SWITCH();
732 if ( redFsm->errState != 0 ) {
735 " if ( " << CS() << " == " << redFsm->errState->id << " )\n"
741 " if ( ++" << P() << " != " << PE() << " )\n"
746 " " << P() << " += 1;\n"
751 out << " _out: {}\n";
756 void FlatCodeGen::writeEOF()
758 if ( redFsm->anyEofActions() ) {
761 " " << PTR_CONST() << ARRAY_TYPE(redFsm->maxActArrItem) << POINTER() << "_acts = " <<
762 ARR_OFF( A(), EA() + "[" + CS() + "]" ) << ";\n"
763 " " << UINT() << " _nacts = " << CAST(UINT()) << " *_acts++;\n"
764 " while ( _nacts-- > 0 ) {\n"
765 " switch ( *_acts++ ) {\n";