2 * Copyright 2001-2006 Adrian Thurston <thurston@complang.org>
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 "gotocodegen.h"
30 /* Emit the goto to take for a given transition. */
31 std::ostream &GotoCodeGen::TRANS_GOTO( RedTransAp *trans, int level )
33 out << TABS(level) << "goto tr" << trans->id << ";";
37 std::ostream &GotoCodeGen::TO_STATE_ACTION_SWITCH()
39 /* Walk the list of functions, printing the cases. */
40 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
41 /* Write out referenced actions. */
42 if ( act->numToStateRefs > 0 ) {
43 /* Write the case label, the action and the case break. */
44 out << "\tcase " << act->actionId << ":\n";
45 ACTION( out, act, 0, false, false );
50 genLineDirective( out );
54 std::ostream &GotoCodeGen::FROM_STATE_ACTION_SWITCH()
56 /* Walk the list of functions, printing the cases. */
57 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
58 /* Write out referenced actions. */
59 if ( act->numFromStateRefs > 0 ) {
60 /* Write the case label, the action and the case break. */
61 out << "\tcase " << act->actionId << ":\n";
62 ACTION( out, act, 0, false, false );
67 genLineDirective( out );
71 std::ostream &GotoCodeGen::EOF_ACTION_SWITCH()
73 /* Walk the list of functions, printing the cases. */
74 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
75 /* Write out referenced actions. */
76 if ( act->numEofRefs > 0 ) {
77 /* Write the case label, the action and the case break. */
78 out << "\tcase " << act->actionId << ":\n";
79 ACTION( out, act, 0, true, false );
84 genLineDirective( out );
88 std::ostream &GotoCodeGen::ACTION_SWITCH()
90 /* Walk the list of functions, printing the cases. */
91 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
92 /* Write out referenced actions. */
93 if ( act->numTransRefs > 0 ) {
94 /* Write the case label, the action and the case break. */
95 out << "\tcase " << act->actionId << ":\n";
96 ACTION( out, act, 0, false, false );
101 genLineDirective( out );
105 void GotoCodeGen::GOTO_HEADER( RedStateAp *state )
107 /* Label the state. */
108 out << "case " << state->id << ":\n";
112 void GotoCodeGen::emitSingleSwitch( RedStateAp *state )
114 /* Load up the singles. */
115 int numSingles = state->outSingle.length();
116 RedTransEl *data = state->outSingle.data;
118 if ( numSingles == 1 ) {
119 /* If there is a single single key then write it out as an if. */
120 out << "\tif ( " << GET_WIDE_KEY(state) << " == " <<
121 KEY(data[0].lowKey) << " )\n\t\t";
123 /* Virtual function for writing the target of the transition. */
124 TRANS_GOTO(data[0].value, 0) << "\n";
126 else if ( numSingles > 1 ) {
127 /* Write out single keys in a switch if there is more than one. */
128 out << "\tswitch( " << GET_WIDE_KEY(state) << " ) {\n";
130 /* Write out the single indicies. */
131 for ( int j = 0; j < numSingles; j++ ) {
132 out << "\t\tcase " << KEY(data[j].lowKey) << ": ";
133 TRANS_GOTO(data[j].value, 0) << "\n";
136 /* Emits a default case for D code. */
139 /* Close off the transition switch. */
144 void GotoCodeGen::emitRangeBSearch( RedStateAp *state, int level, int low, int high )
146 /* Get the mid position, staying on the lower end of the range. */
147 int mid = (low + high) >> 1;
148 RedTransEl *data = state->outRange.data;
150 /* Determine if we need to look higher or lower. */
151 bool anyLower = mid > low;
152 bool anyHigher = mid < high;
154 /* Determine if the keys at mid are the limits of the alphabet. */
155 bool limitLow = data[mid].lowKey == keyOps->minKey;
156 bool limitHigh = data[mid].highKey == keyOps->maxKey;
158 if ( anyLower && anyHigher ) {
159 /* Can go lower and higher than mid. */
160 out << TABS(level) << "if ( " << GET_WIDE_KEY(state) << " < " <<
161 KEY(data[mid].lowKey) << " ) {\n";
162 emitRangeBSearch( state, level+1, low, mid-1 );
163 out << TABS(level) << "} else if ( " << GET_WIDE_KEY(state) << " > " <<
164 KEY(data[mid].highKey) << " ) {\n";
165 emitRangeBSearch( state, level+1, mid+1, high );
166 out << TABS(level) << "} else\n";
167 TRANS_GOTO(data[mid].value, level+1) << "\n";
169 else if ( anyLower && !anyHigher ) {
170 /* Can go lower than mid but not higher. */
171 out << TABS(level) << "if ( " << GET_WIDE_KEY(state) << " < " <<
172 KEY(data[mid].lowKey) << " ) {\n";
173 emitRangeBSearch( state, level+1, low, mid-1 );
175 /* if the higher is the highest in the alphabet then there is no
176 * sense testing it. */
178 out << TABS(level) << "} else\n";
179 TRANS_GOTO(data[mid].value, level+1) << "\n";
182 out << TABS(level) << "} else if ( " << GET_WIDE_KEY(state) << " <= " <<
183 KEY(data[mid].highKey) << " )\n";
184 TRANS_GOTO(data[mid].value, level+1) << "\n";
187 else if ( !anyLower && anyHigher ) {
188 /* Can go higher than mid but not lower. */
189 out << TABS(level) << "if ( " << GET_WIDE_KEY(state) << " > " <<
190 KEY(data[mid].highKey) << " ) {\n";
191 emitRangeBSearch( state, level+1, mid+1, high );
193 /* If the lower end is the lowest in the alphabet then there is no
194 * sense testing it. */
196 out << TABS(level) << "} else\n";
197 TRANS_GOTO(data[mid].value, level+1) << "\n";
200 out << TABS(level) << "} else if ( " << GET_WIDE_KEY(state) << " >= " <<
201 KEY(data[mid].lowKey) << " )\n";
202 TRANS_GOTO(data[mid].value, level+1) << "\n";
206 /* Cannot go higher or lower than mid. It's mid or bust. What
207 * tests to do depends on limits of alphabet. */
208 if ( !limitLow && !limitHigh ) {
209 out << TABS(level) << "if ( " << KEY(data[mid].lowKey) << " <= " <<
210 GET_WIDE_KEY(state) << " && " << GET_WIDE_KEY(state) << " <= " <<
211 KEY(data[mid].highKey) << " )\n";
212 TRANS_GOTO(data[mid].value, level+1) << "\n";
214 else if ( limitLow && !limitHigh ) {
215 out << TABS(level) << "if ( " << GET_WIDE_KEY(state) << " <= " <<
216 KEY(data[mid].highKey) << " )\n";
217 TRANS_GOTO(data[mid].value, level+1) << "\n";
219 else if ( !limitLow && limitHigh ) {
220 out << TABS(level) << "if ( " << KEY(data[mid].lowKey) << " <= " <<
221 GET_WIDE_KEY(state) << " )\n";
222 TRANS_GOTO(data[mid].value, level+1) << "\n";
225 /* Both high and low are at the limit. No tests to do. */
226 TRANS_GOTO(data[mid].value, level+1) << "\n";
231 void GotoCodeGen::STATE_GOTO_ERROR()
233 /* Label the state and bail immediately. */
235 RedStateAp *state = redFsm->errState;
236 out << "case " << state->id << ":\n";
237 out << " goto _out;\n";
240 void GotoCodeGen::COND_TRANSLATE( GenStateCond *stateCond, int level )
242 GenCondSpace *condSpace = stateCond->condSpace;
243 out << TABS(level) << "_widec = " << CAST(WIDE_ALPH_TYPE()) << "(" <<
244 KEY(condSpace->baseKey) << " + (" << GET_KEY() <<
245 " - " << KEY(keyOps->minKey) << "));\n";
247 for ( GenCondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
248 out << TABS(level) << "if ( ";
249 CONDITION( out, *csi );
250 Size condValOffset = ((1 << csi.pos()) * keyOps->alphSize());
251 out << " ) _widec += " << condValOffset << ";\n";
255 void GotoCodeGen::emitCondBSearch( RedStateAp *state, int level, int low, int high )
257 /* Get the mid position, staying on the lower end of the range. */
258 int mid = (low + high) >> 1;
259 GenStateCond **data = state->stateCondVect.data;
261 /* Determine if we need to look higher or lower. */
262 bool anyLower = mid > low;
263 bool anyHigher = mid < high;
265 /* Determine if the keys at mid are the limits of the alphabet. */
266 bool limitLow = data[mid]->lowKey == keyOps->minKey;
267 bool limitHigh = data[mid]->highKey == keyOps->maxKey;
269 if ( anyLower && anyHigher ) {
270 /* Can go lower and higher than mid. */
271 out << TABS(level) << "if ( " << GET_KEY() << " < " <<
272 KEY(data[mid]->lowKey) << " ) {\n";
273 emitCondBSearch( state, level+1, low, mid-1 );
274 out << TABS(level) << "} else if ( " << GET_KEY() << " > " <<
275 KEY(data[mid]->highKey) << " ) {\n";
276 emitCondBSearch( state, level+1, mid+1, high );
277 out << TABS(level) << "} else {\n";
278 COND_TRANSLATE(data[mid], level+1);
279 out << TABS(level) << "}\n";
281 else if ( anyLower && !anyHigher ) {
282 /* Can go lower than mid but not higher. */
283 out << TABS(level) << "if ( " << GET_KEY() << " < " <<
284 KEY(data[mid]->lowKey) << " ) {\n";
285 emitCondBSearch( state, level+1, low, mid-1 );
287 /* if the higher is the highest in the alphabet then there is no
288 * sense testing it. */
290 out << TABS(level) << "} else {\n";
291 COND_TRANSLATE(data[mid], level+1);
292 out << TABS(level) << "}\n";
295 out << TABS(level) << "} else if ( " << GET_KEY() << " <= " <<
296 KEY(data[mid]->highKey) << " ) {\n";
297 COND_TRANSLATE(data[mid], level+1);
298 out << TABS(level) << "}\n";
301 else if ( !anyLower && anyHigher ) {
302 /* Can go higher than mid but not lower. */
303 out << TABS(level) << "if ( " << GET_KEY() << " > " <<
304 KEY(data[mid]->highKey) << " ) {\n";
305 emitCondBSearch( state, level+1, mid+1, high );
307 /* If the lower end is the lowest in the alphabet then there is no
308 * sense testing it. */
310 out << TABS(level) << "} else {\n";
311 COND_TRANSLATE(data[mid], level+1);
312 out << TABS(level) << "}\n";
315 out << TABS(level) << "} else if ( " << GET_KEY() << " >= " <<
316 KEY(data[mid]->lowKey) << " ) {\n";
317 COND_TRANSLATE(data[mid], level+1);
318 out << TABS(level) << "}\n";
322 /* Cannot go higher or lower than mid. It's mid or bust. What
323 * tests to do depends on limits of alphabet. */
324 if ( !limitLow && !limitHigh ) {
325 out << TABS(level) << "if ( " << KEY(data[mid]->lowKey) << " <= " <<
326 GET_KEY() << " && " << GET_KEY() << " <= " <<
327 KEY(data[mid]->highKey) << " ) {\n";
328 COND_TRANSLATE(data[mid], level+1);
329 out << TABS(level) << "}\n";
331 else if ( limitLow && !limitHigh ) {
332 out << TABS(level) << "if ( " << GET_KEY() << " <= " <<
333 KEY(data[mid]->highKey) << " ) {\n";
334 COND_TRANSLATE(data[mid], level+1);
335 out << TABS(level) << "}\n";
337 else if ( !limitLow && limitHigh ) {
338 out << TABS(level) << "if ( " << KEY(data[mid]->lowKey) << " <= " <<
339 GET_KEY() << " )\n {";
340 COND_TRANSLATE(data[mid], level+1);
341 out << TABS(level) << "}\n";
344 /* Both high and low are at the limit. No tests to do. */
345 COND_TRANSLATE(data[mid], level);
350 std::ostream &GotoCodeGen::STATE_GOTOS()
352 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
353 if ( st == redFsm->errState )
356 /* Writing code above state gotos. */
359 if ( st->stateCondVect.length() > 0 ) {
360 out << " _widec = " << GET_KEY() << ";\n";
361 emitCondBSearch( st, 1, 0, st->stateCondVect.length() - 1 );
365 if ( st->outSingle.length() > 0 )
366 emitSingleSwitch( st );
368 /* Default case is to binary search for the ranges, if that fails then */
369 if ( st->outRange.length() > 0 )
370 emitRangeBSearch( st, 1, 0, st->outRange.length() - 1 );
372 /* Write the default transition. */
373 TRANS_GOTO( st->defTrans, 1 ) << "\n";
379 std::ostream &GotoCodeGen::TRANSITIONS()
381 /* Emit any transitions that have functions and that go to
383 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) {
384 /* Write the label for the transition so it can be jumped to. */
385 out << " tr" << trans->id << ": ";
387 /* Destination state. */
388 if ( trans->action != 0 && trans->action->anyCurStateRef() )
389 out << "_ps = " << CS() << ";";
390 out << CS() << " = " << trans->targ->id << "; ";
392 if ( trans->action != 0 ) {
393 /* Write out the transition func. */
394 out << "goto f" << trans->action->actListId << ";\n";
397 /* No code to execute, just loop around. */
398 out << "goto _again;\n";
404 std::ostream &GotoCodeGen::EXEC_FUNCS()
406 /* Make labels that set acts and jump to execFuncs. Loop func indicies. */
407 for ( ActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
408 if ( redAct->numTransRefs > 0 ) {
409 out << " f" << redAct->actListId << ": " <<
410 "_acts = " << ARR_OFF(A(), itoa( redAct->location+1 ) ) << ";"
411 " goto execFuncs;\n";
418 " _nacts = *_acts++;\n"
419 " while ( _nacts-- > 0 ) {\n"
420 " switch ( *_acts++ ) {\n";
429 unsigned int GotoCodeGen::TO_STATE_ACTION( RedStateAp *state )
432 if ( state->toStateAction != 0 )
433 act = state->toStateAction->location+1;
437 unsigned int GotoCodeGen::FROM_STATE_ACTION( RedStateAp *state )
440 if ( state->fromStateAction != 0 )
441 act = state->fromStateAction->location+1;
445 unsigned int GotoCodeGen::EOF_ACTION( RedStateAp *state )
448 if ( state->eofAction != 0 )
449 act = state->eofAction->location+1;
453 std::ostream &GotoCodeGen::TO_STATE_ACTIONS()
455 /* Take one off for the psuedo start state. */
456 int numStates = redFsm->stateList.length();
457 unsigned int *vals = new unsigned int[numStates];
458 memset( vals, 0, sizeof(unsigned int)*numStates );
460 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
461 vals[st->id] = TO_STATE_ACTION(st);
464 for ( int st = 0; st < redFsm->nextStateId; st++ ) {
465 /* Write any eof action. */
467 if ( st < numStates-1 ) {
469 if ( (st+1) % IALL == 0 )
478 std::ostream &GotoCodeGen::FROM_STATE_ACTIONS()
480 /* Take one off for the psuedo start state. */
481 int numStates = redFsm->stateList.length();
482 unsigned int *vals = new unsigned int[numStates];
483 memset( vals, 0, sizeof(unsigned int)*numStates );
485 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
486 vals[st->id] = FROM_STATE_ACTION(st);
489 for ( int st = 0; st < redFsm->nextStateId; st++ ) {
490 /* Write any eof action. */
492 if ( st < numStates-1 ) {
494 if ( (st+1) % IALL == 0 )
503 std::ostream &GotoCodeGen::EOF_ACTIONS()
505 /* Take one off for the psuedo start state. */
506 int numStates = redFsm->stateList.length();
507 unsigned int *vals = new unsigned int[numStates];
508 memset( vals, 0, sizeof(unsigned int)*numStates );
510 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
511 vals[st->id] = EOF_ACTION(st);
514 for ( int st = 0; st < redFsm->nextStateId; st++ ) {
515 /* Write any eof action. */
517 if ( st < numStates-1 ) {
519 if ( (st+1) % IALL == 0 )
528 std::ostream &GotoCodeGen::FINISH_CASES()
530 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
531 /* States that are final and have an out action need a case. */
532 if ( st->eofAction != 0 ) {
533 /* Write the case label. */
534 out << "\t\tcase " << st->id << ": ";
536 /* Write the goto func. */
537 out << "goto f" << st->eofAction->actListId << ";\n";
544 void GotoCodeGen::GOTO( ostream &ret, int gotoDest, bool inFinish )
546 ret << "{" << CS() << " = " << gotoDest << "; " <<
547 CTRL_FLOW() << "goto _again;}";
550 void GotoCodeGen::GOTO_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish )
552 ret << "{" << CS() << " = (";
553 INLINE_LIST( ret, ilItem->children, 0, inFinish, false );
554 ret << "); " << CTRL_FLOW() << "goto _again;}";
557 void GotoCodeGen::CURS( ostream &ret, bool inFinish )
562 void GotoCodeGen::TARGS( ostream &ret, bool inFinish, int targState )
564 ret << "(" << CS() << ")";
567 void GotoCodeGen::NEXT( ostream &ret, int nextDest, bool inFinish )
569 ret << CS() << " = " << nextDest << ";";
572 void GotoCodeGen::NEXT_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish )
574 ret << CS() << " = (";
575 INLINE_LIST( ret, ilItem->children, 0, inFinish, false );
579 void GotoCodeGen::CALL( ostream &ret, int callDest, int targState, bool inFinish )
581 if ( prePushExpr != 0 ) {
583 INLINE_LIST( ret, prePushExpr, 0, false, false );
586 ret << "{" << STACK() << "[" << TOP() << "++] = " << CS() << "; " << CS() << " = " <<
587 callDest << "; " << CTRL_FLOW() << "goto _again;}";
589 if ( prePushExpr != 0 )
593 void GotoCodeGen::CALL_EXPR( ostream &ret, GenInlineItem *ilItem, int targState, bool inFinish )
595 if ( prePushExpr != 0 ) {
597 INLINE_LIST( ret, prePushExpr, 0, false, false );
600 ret << "{" << STACK() << "[" << TOP() << "++] = " << CS() << "; " << CS() << " = (";
601 INLINE_LIST( ret, ilItem->children, targState, inFinish, false );
602 ret << "); " << CTRL_FLOW() << "goto _again;}";
604 if ( prePushExpr != 0 )
608 void GotoCodeGen::RET( ostream &ret, bool inFinish )
610 ret << "{" << CS() << " = " << STACK() << "[--" << TOP() << "];";
612 if ( postPopExpr != 0 ) {
614 INLINE_LIST( ret, postPopExpr, 0, false, false );
618 ret << CTRL_FLOW() << "goto _again;}";
621 void GotoCodeGen::BREAK( ostream &ret, int targState, bool csForced )
624 ret << "{" << P() << "++; " << CTRL_FLOW() << "goto _out; }";
627 void GotoCodeGen::writeData()
629 if ( redFsm->anyActions() ) {
630 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActArrItem), A() );
636 if ( redFsm->anyToStateActions() ) {
637 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
643 if ( redFsm->anyFromStateActions() ) {
644 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
645 FROM_STATE_ACTIONS();
650 if ( redFsm->anyEofActions() ) {
651 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), EA() );
660 void GotoCodeGen::writeExec()
663 outLabelUsed = false;
667 if ( redFsm->anyRegCurStateRef() )
668 out << " int _ps = 0;\n";
670 if ( redFsm->anyToStateActions() || redFsm->anyRegActions()
671 || redFsm->anyFromStateActions() )
674 " " << PTR_CONST() << ARRAY_TYPE(redFsm->maxActArrItem) << POINTER() << "_acts;\n"
675 " " << UINT() << " _nacts;\n";
678 if ( redFsm->anyConditions() )
679 out << " " << WIDE_ALPH_TYPE() << " _widec;\n";
686 " if ( " << P() << " == " << PE() << " )\n"
687 " goto _test_eof;\n";
690 if ( redFsm->errState != 0 ) {
693 " if ( " << CS() << " == " << redFsm->errState->id << " )\n"
699 if ( redFsm->anyFromStateActions() ) {
701 " _acts = " << ARR_OFF( A(), FSA() + "[" + CS() + "]" ) << ";\n"
702 " _nacts = " << CAST(UINT()) << " *_acts++;\n"
703 " while ( _nacts-- > 0 ) {\n"
704 " switch ( *_acts++ ) {\n";
705 FROM_STATE_ACTION_SWITCH();
713 " switch ( " << CS() << " ) {\n";
721 if ( redFsm->anyRegActions() )
722 EXEC_FUNCS() << "\n";
726 if ( redFsm->anyToStateActions() ) {
728 " _acts = " << ARR_OFF( A(), TSA() + "[" + CS() + "]" ) << ";\n"
729 " _nacts = " << CAST(UINT()) << " *_acts++;\n"
730 " while ( _nacts-- > 0 ) {\n"
731 " switch ( *_acts++ ) {\n";
732 TO_STATE_ACTION_SWITCH();
739 if ( redFsm->errState != 0 ) {
742 " if ( " << CS() << " == " << redFsm->errState->id << " )\n"
748 " if ( ++" << P() << " != " << PE() << " )\n"
753 " " << P() << " += 1;\n"
758 out << " _test_eof: {}\n";
760 if ( redFsm->anyEofTrans() || redFsm->anyEofActions() ) {
762 " if ( " << P() << " == " << EOFV() << " )\n"
765 if ( redFsm->anyEofTrans() ) {
767 " switch ( " << CS() << " ) {\n";
769 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
770 if ( st->eofTrans != 0 )
771 out << " case " << st->id << ": goto tr" << st->eofTrans->id << ";\n";
778 if ( redFsm->anyEofActions() ) {
780 " " << PTR_CONST() << ARRAY_TYPE(redFsm->maxActArrItem) <<
781 POINTER() << "__acts = " <<
782 ARR_OFF( A(), EA() + "[" + CS() + "]" ) << ";\n"
783 " " << UINT() << " __nacts = " << CAST(UINT()) << " *__acts++;\n"
784 " while ( __nacts-- > 0 ) {\n"
785 " switch ( *__acts++ ) {\n";
798 out << " _out: {}\n";