2 * Copyright 2007 Victor Hugo Borja <vic@rubyforge.org>
3 * 2006-2007 Adrian Thurston <thurston@complang.org>
6 /* This file is part of Ragel.
8 * Ragel is free software; you can redistribute it and/or modify
9 * it under the terms of the GNU General Public License as published by
10 * the Free Software Foundation; either version 2 of the License, or
11 * (at your option) any later version.
13 * Ragel is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 * GNU General Public License for more details.
18 * You should have received a copy of the GNU General Public License
19 * along with Ragel; if not, write to the Free Software
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
35 inline string label(string a, int i)
40 ostream &RbxGotoCodeGen::rbxLabel(ostream &out, string label)
42 out << "Rubinius.asm { @labels[:_" << FSM_NAME() << "_" << label << "].set! }\n";
46 ostream &RbxGotoCodeGen::rbxGoto(ostream &out, string label)
48 out << "Rubinius.asm { goto @labels[:_" << FSM_NAME() << "_" << label << "] }\n";
52 /* Emit the goto to take for a given transition. */
53 std::ostream &RbxGotoCodeGen::TRANS_GOTO( RedTransAp *trans, int level )
56 return rbxGoto(out, label("tr",trans->id));
59 std::ostream &RbxGotoCodeGen::TO_STATE_ACTION_SWITCH()
61 /* Walk the list of functions, printing the cases. */
62 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
63 /* Write out referenced actions. */
64 if ( act->numToStateRefs > 0 ) {
65 /* Write the case label, the action and the case break. */
66 out << "\twhen " << act->actionId << " then\n";
67 ACTION( out, act, 0, false );
71 genLineDirective( out );
75 std::ostream &RbxGotoCodeGen::FROM_STATE_ACTION_SWITCH()
77 /* Walk the list of functions, printing the cases. */
78 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
79 /* Write out referenced actions. */
80 if ( act->numFromStateRefs > 0 ) {
81 /* Write the case label, the action and the case break. */
82 out << "\twhen " << act->actionId << " then\n";
83 ACTION( out, act, 0, false );
87 genLineDirective( out );
91 std::ostream &RbxGotoCodeGen::EOF_ACTION_SWITCH()
93 /* Walk the list of functions, printing the cases. */
94 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
95 /* Write out referenced actions. */
96 if ( act->numEofRefs > 0 ) {
97 /* Write the case label, the action and the case break. */
98 out << "\twhen " << act->actionId << " then\n";
99 ACTION( out, act, 0, true );
103 genLineDirective( out );
107 std::ostream &RbxGotoCodeGen::ACTION_SWITCH()
109 /* Walk the list of functions, printing the cases. */
110 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
111 /* Write out referenced actions. */
112 if ( act->numTransRefs > 0 ) {
113 /* Write the case label, the action and the case break. */
114 out << "\twhen " << act->actionId << " then\n";
115 ACTION( out, act, 0, false );
119 genLineDirective( out );
123 void RbxGotoCodeGen::GOTO_HEADER( RedStateAp *state )
125 /* Label the state. */
126 out << "when " << state->id << " then\n";
130 void RbxGotoCodeGen::emitSingleSwitch( RedStateAp *state )
132 /* Load up the singles. */
133 int numSingles = state->outSingle.length();
134 RedTransEl *data = state->outSingle.data;
136 if ( numSingles == 1 ) {
137 /* If there is a single single key then write it out as an if. */
138 out << "\tif " << GET_WIDE_KEY(state) << " == " <<
139 KEY(data[0].lowKey) << " \n\t\t";
141 /* Virtual function for writing the target of the transition. */
142 TRANS_GOTO(data[0].value, 0) << "\n";
146 else if ( numSingles > 1 ) {
147 /* Write out single keys in a switch if there is more than one. */
148 out << "\tcase " << GET_WIDE_KEY(state) << "\n";
150 /* Write out the single indicies. */
151 for ( int j = 0; j < numSingles; j++ ) {
152 out << "\t\twhen " << KEY(data[j].lowKey) << " then\n";
153 TRANS_GOTO(data[j].value, 0) << "\n";
156 /* Close off the transition switch. */
161 void RbxGotoCodeGen::emitRangeBSearch( RedStateAp *state, int level, int low, int high )
163 /* Get the mid position, staying on the lower end of the range. */
164 int mid = (low + high) >> 1;
165 RedTransEl *data = state->outRange.data;
167 /* Determine if we need to look higher or lower. */
168 bool anyLower = mid > low;
169 bool anyHigher = mid < high;
171 /* Determine if the keys at mid are the limits of the alphabet. */
172 bool limitLow = data[mid].lowKey == keyOps->minKey;
173 bool limitHigh = data[mid].highKey == keyOps->maxKey;
175 if ( anyLower && anyHigher ) {
176 /* Can go lower and higher than mid. */
177 out << TABS(level) << "if " << GET_WIDE_KEY(state) << " < " <<
178 KEY(data[mid].lowKey) << " \n";
179 emitRangeBSearch( state, level+1, low, mid-1 );
180 out << TABS(level) << "elsif " << GET_WIDE_KEY(state) << " > " <<
181 KEY(data[mid].highKey) << " \n";
182 emitRangeBSearch( state, level+1, mid+1, high );
183 out << TABS(level) << "else\n";
184 TRANS_GOTO(data[mid].value, level+1) << "\n";
185 out << TABS(level) << "end\n";
187 else if ( anyLower && !anyHigher ) {
188 /* Can go lower than mid but not higher. */
189 out << TABS(level) << "if " << GET_WIDE_KEY(state) << " < " <<
190 KEY(data[mid].lowKey) << " then\n";
191 emitRangeBSearch( state, level+1, low, mid-1 );
193 /* if the higher is the highest 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) << "elsif" << GET_WIDE_KEY(state) << " <= " <<
201 KEY(data[mid].highKey) << " )\n";
202 TRANS_GOTO(data[mid].value, level+1) << "\n";
204 out << TABS(level) << "end\n";
206 else if ( !anyLower && anyHigher ) {
207 /* Can go higher than mid but not lower. */
208 out << TABS(level) << "if " << GET_WIDE_KEY(state) << " > " <<
209 KEY(data[mid].highKey) << " \n";
210 emitRangeBSearch( state, level+1, mid+1, high );
212 /* If the lower end is the lowest in the alphabet then there is no
213 * sense testing it. */
215 out << TABS(level) << "else\n";
216 TRANS_GOTO(data[mid].value, level+1) << "\n";
219 out << TABS(level) << "elsif " << GET_WIDE_KEY(state) << " >= " <<
220 KEY(data[mid].lowKey) << " then\n";
221 TRANS_GOTO(data[mid].value, level+1) << "\n";
223 out << TABS(level) << "end\n";
226 /* Cannot go higher or lower than mid. It's mid or bust. What
227 * tests to do depends on limits of alphabet. */
228 if ( !limitLow && !limitHigh ) {
229 out << TABS(level) << "if " << KEY(data[mid].lowKey) << " <= " <<
230 GET_WIDE_KEY(state) << " && " << GET_WIDE_KEY(state) << " <= " <<
231 KEY(data[mid].highKey) << " \n";
232 TRANS_GOTO(data[mid].value, level+1) << "\n";
233 out << TABS(level) << "end\n";
235 else if ( limitLow && !limitHigh ) {
236 out << TABS(level) << "if " << GET_WIDE_KEY(state) << " <= " <<
237 KEY(data[mid].highKey) << " \n";
238 TRANS_GOTO(data[mid].value, level+1) << "\n";
239 out << TABS(level) << "end\n";
241 else if ( !limitLow && limitHigh ) {
242 out << TABS(level) << "if " << KEY(data[mid].lowKey) << " <= " <<
243 GET_WIDE_KEY(state) << " \n";
244 TRANS_GOTO(data[mid].value, level+1) << "\n";
245 out << TABS(level) << "end\n";
248 /* Both high and low are at the limit. No tests to do. */
249 TRANS_GOTO(data[mid].value, level+1) << "\n";
254 void RbxGotoCodeGen::STATE_GOTO_ERROR()
256 /* Label the state and bail immediately. */
258 RedStateAp *state = redFsm->errState;
259 out << "when " << state->id << " then\n";
260 rbxGoto(out << " ", "_out") << "\n";
263 void RbxGotoCodeGen::COND_TRANSLATE( GenStateCond *stateCond, int level )
265 GenCondSpace *condSpace = stateCond->condSpace;
266 out << TABS(level) << "_widec = " <<
267 KEY(condSpace->baseKey) << " + (" << GET_KEY() <<
268 " - " << KEY(keyOps->minKey) << ");\n";
270 for ( GenCondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
271 out << TABS(level) << "if ";
272 CONDITION( out, *csi );
273 Size condValOffset = ((1 << csi.pos()) * keyOps->alphSize());
274 out << "\n _widec += " << condValOffset << ";\n end";
278 void RbxGotoCodeGen::emitCondBSearch( RedStateAp *state, int level, int low, int high )
280 /* Get the mid position, staying on the lower end of the range. */
281 int mid = (low + high) >> 1;
282 GenStateCond **data = state->stateCondVect.data;
284 /* Determine if we need to look higher or lower. */
285 bool anyLower = mid > low;
286 bool anyHigher = mid < high;
288 /* Determine if the keys at mid are the limits of the alphabet. */
289 bool limitLow = data[mid]->lowKey == keyOps->minKey;
290 bool limitHigh = data[mid]->highKey == keyOps->maxKey;
292 if ( anyLower && anyHigher ) {
293 /* Can go lower and higher than mid. */
294 out << TABS(level) << "if " << GET_KEY() << " < " <<
295 KEY(data[mid]->lowKey) << " \n";
296 emitCondBSearch( state, level+1, low, mid-1 );
297 out << TABS(level) << "elsif " << GET_KEY() << " > " <<
298 KEY(data[mid]->highKey) << " \n";
299 emitCondBSearch( state, level+1, mid+1, high );
300 out << TABS(level) << "else\n";
301 COND_TRANSLATE(data[mid], level+1);
302 out << TABS(level) << "end\n";
304 else if ( anyLower && !anyHigher ) {
305 /* Can go lower than mid but not higher. */
306 out << TABS(level) << "if " << GET_KEY() << " < " <<
307 KEY(data[mid]->lowKey) << " \n";
308 emitCondBSearch( state, level+1, low, mid-1 );
310 /* if the higher is the highest in the alphabet then there is no
311 * sense testing it. */
313 out << TABS(level) << "else\n";
314 COND_TRANSLATE(data[mid], level+1);
317 out << TABS(level) << "elsif " << GET_KEY() << " <= " <<
318 KEY(data[mid]->highKey) << " then\n";
319 COND_TRANSLATE(data[mid], level+1);
321 out << TABS(level) << "end\n";
324 else if ( !anyLower && anyHigher ) {
325 /* Can go higher than mid but not lower. */
326 out << TABS(level) << "if " << GET_KEY() << " > " <<
327 KEY(data[mid]->highKey) << " \n";
328 emitCondBSearch( state, level+1, mid+1, high );
330 /* If the lower end is the lowest in the alphabet then there is no
331 * sense testing it. */
333 out << TABS(level) << "else\n";
334 COND_TRANSLATE(data[mid], level+1);
337 out << TABS(level) << "elsif " << GET_KEY() << " >= " <<
338 KEY(data[mid]->lowKey) << " then\n";
339 COND_TRANSLATE(data[mid], level+1);
341 out << TABS(level) << "end\n";
344 /* Cannot go higher or lower than mid. It's mid or bust. What
345 * tests to do depends on limits of alphabet. */
346 if ( !limitLow && !limitHigh ) {
347 out << TABS(level) << "if " << KEY(data[mid]->lowKey) << " <= " <<
348 GET_KEY() << " && " << GET_KEY() << " <= " <<
349 KEY(data[mid]->highKey) << " then\n";
350 COND_TRANSLATE(data[mid], level+1);
351 out << TABS(level) << "end\n";
353 else if ( limitLow && !limitHigh ) {
354 out << TABS(level) << "if " << GET_KEY() << " <= " <<
355 KEY(data[mid]->highKey) << " then\n";
356 COND_TRANSLATE(data[mid], level+1);
357 out << TABS(level) << "end\n";
359 else if ( !limitLow && limitHigh ) {
360 out << TABS(level) << "if " << KEY(data[mid]->lowKey) << " <= " <<
361 GET_KEY() << " then\n";
362 COND_TRANSLATE(data[mid], level+1);
363 out << TABS(level) << "end\n";
366 /* Both high and low are at the limit. No tests to do. */
367 COND_TRANSLATE(data[mid], level);
372 std::ostream &RbxGotoCodeGen::STATE_GOTOS()
374 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
375 if ( st == redFsm->errState )
378 /* Writing code above state gotos. */
381 if ( st->stateCondVect.length() > 0 ) {
382 out << " _widec = " << GET_KEY() << ";\n";
383 emitCondBSearch( st, 1, 0, st->stateCondVect.length() - 1 );
387 if ( st->outSingle.length() > 0 )
388 emitSingleSwitch( st );
390 /* Default case is to binary search for the ranges, if that fails then */
391 if ( st->outRange.length() > 0 )
392 emitRangeBSearch( st, 1, 0, st->outRange.length() - 1 );
394 /* Write the default transition. */
395 TRANS_GOTO( st->defTrans, 1 ) << "\n";
401 std::ostream &RbxGotoCodeGen::TRANSITIONS()
403 /* Emit any transitions that have functions and that go to
405 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) {
406 /* Write the label for the transition so it can be jumped to. */
407 rbxLabel(out << " ", label("tr", trans->id)) << "\n";
409 /* Destination state. */
410 if ( trans->action != 0 && trans->action->anyCurStateRef() )
411 out << "_ps = " << CS() << "'n";
412 out << CS() << " = " << trans->targ->id << "\n";
414 if ( trans->action != 0 ) {
415 /* Write out the transition func. */
416 rbxGoto(out, label("f", trans->action->actListId)) << "\n";
419 /* No code to execute, just loop around. */
420 rbxGoto(out, "_again") << "\n";
426 std::ostream &RbxGotoCodeGen::EXEC_FUNCS()
428 /* Make labels that set acts and jump to execFuncs. Loop func indicies. */
429 for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
430 if ( redAct->numTransRefs > 0 ) {
431 rbxLabel(out, label("f", redAct->actListId)) << "\n" <<
432 "_acts = " << itoa( redAct->location+1 ) << "\n";
433 rbxGoto(out, "execFuncs") << "\n";
437 rbxLabel(out, "execFuncs") <<
439 " _nacts = " << A() << "[_acts]\n"
441 " while ( _nacts > 0 ) \n"
444 " case ( "<< A() << "[_acts-1] ) \n";
449 rbxGoto(out, "_again");
453 int RbxGotoCodeGen::TO_STATE_ACTION( RedStateAp *state )
456 if ( state->toStateAction != 0 )
457 act = state->toStateAction->location+1;
461 int RbxGotoCodeGen::FROM_STATE_ACTION( RedStateAp *state )
464 if ( state->fromStateAction != 0 )
465 act = state->fromStateAction->location+1;
469 int RbxGotoCodeGen::EOF_ACTION( RedStateAp *state )
472 if ( state->eofAction != 0 )
473 act = state->eofAction->location+1;
477 std::ostream &RbxGotoCodeGen::TO_STATE_ACTIONS()
479 /* Take one off for the psuedo start state. */
480 int numStates = redFsm->stateList.length();
481 unsigned int *vals = new unsigned int[numStates];
482 memset( vals, 0, sizeof(unsigned int)*numStates );
484 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
485 vals[st->id] = TO_STATE_ACTION(st);
488 for ( int st = 0; st < redFsm->nextStateId; st++ ) {
489 /* Write any eof action. */
491 if ( st < numStates-1 ) {
493 if ( (st+1) % IALL == 0 )
502 std::ostream &RbxGotoCodeGen::FROM_STATE_ACTIONS()
504 /* Take one off for the psuedo start state. */
505 int numStates = redFsm->stateList.length();
506 unsigned int *vals = new unsigned int[numStates];
507 memset( vals, 0, sizeof(unsigned int)*numStates );
509 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
510 vals[st->id] = FROM_STATE_ACTION(st);
513 for ( int st = 0; st < redFsm->nextStateId; st++ ) {
514 /* Write any eof action. */
516 if ( st < numStates-1 ) {
518 if ( (st+1) % IALL == 0 )
527 std::ostream &RbxGotoCodeGen::EOF_ACTIONS()
529 /* Take one off for the psuedo start state. */
530 int numStates = redFsm->stateList.length();
531 unsigned int *vals = new unsigned int[numStates];
532 memset( vals, 0, sizeof(unsigned int)*numStates );
534 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
535 vals[st->id] = EOF_ACTION(st);
538 for ( int st = 0; st < redFsm->nextStateId; st++ ) {
539 /* Write any eof action. */
541 if ( st < numStates-1 ) {
543 if ( (st+1) % IALL == 0 )
552 std::ostream &RbxGotoCodeGen::FINISH_CASES()
554 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
555 /* States that are final and have an out action need a case. */
556 if ( st->eofAction != 0 ) {
557 /* Write the case label. */
558 out << "\t\twhen " << st->id << " then\n";
560 /* Write the goto func. */
561 rbxGoto(out, label("f", st->eofAction->actListId)) << "\n";
568 void RbxGotoCodeGen::GOTO( ostream &ret, int gotoDest, bool inFinish )
570 ret << "begin\n" << CS() << " = " << gotoDest << " ";
571 rbxGoto(ret, "_again") <<
575 void RbxGotoCodeGen::GOTO_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish )
577 ret << "begin\n" << CS() << " = (";
578 INLINE_LIST( ret, ilItem->children, 0, inFinish );
580 rbxGoto(ret, "_again") <<
584 void RbxGotoCodeGen::CURS( ostream &ret, bool inFinish )
589 void RbxGotoCodeGen::TARGS( ostream &ret, bool inFinish, int targState )
591 ret << "(" << CS() << ")";
594 void RbxGotoCodeGen::NEXT( ostream &ret, int nextDest, bool inFinish )
596 ret << CS() << " = " << nextDest << ";";
599 void RbxGotoCodeGen::NEXT_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish )
601 ret << CS() << " = (";
602 INLINE_LIST( ret, ilItem->children, 0, inFinish );
606 void RbxGotoCodeGen::CALL( ostream &ret, int callDest, int targState, bool inFinish )
608 if ( prePushExpr != 0 ) {
610 INLINE_LIST( ret, prePushExpr, 0, false );
614 << STACK() << "[" << TOP() << "++] = " << CS() << "; " << CS() << " = " <<
616 rbxGoto(ret, "_again") <<
619 if ( prePushExpr != 0 )
623 void RbxGotoCodeGen::CALL_EXPR( ostream &ret, GenInlineItem *ilItem, int targState, bool inFinish )
625 if ( prePushExpr != 0 ) {
627 INLINE_LIST( ret, prePushExpr, 0, false );
630 ret << "begin\n" << STACK() << "[" << TOP() << "++] = " << CS() << "; " << CS() << " = (";
631 INLINE_LIST( ret, ilItem->children, targState, inFinish );
633 rbxGoto(ret, "_again") <<
636 if ( prePushExpr != 0 )
640 void RbxGotoCodeGen::RET( ostream &ret, bool inFinish )
642 ret << "begin\n" << CS() << " = " << STACK() << "[--" << TOP() << "]; " ;
644 if ( postPopExpr != 0 ) {
646 INLINE_LIST( ret, postPopExpr, 0, false );
650 rbxGoto(ret, "_again") <<
654 void RbxGotoCodeGen::BREAK( ostream &ret, int targState )
660 " " << P() << " += 1\n"
661 " " << rbxGoto(ret, "_out") << "\n"
665 void RbxGotoCodeGen::writeData()
667 if ( redFsm->anyActions() ) {
668 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActArrItem), A() );
674 if ( redFsm->anyToStateActions() ) {
675 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
681 if ( redFsm->anyFromStateActions() ) {
682 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
683 FROM_STATE_ACTIONS();
688 if ( redFsm->anyEofActions() ) {
689 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), EA() );
698 void RbxGotoCodeGen::writeExec()
700 outLabelUsed = false;
704 out << " Rubinius.asm { @labels = Hash.new { |h,k| h[k] = new_label } }\n";
706 if ( redFsm->anyRegCurStateRef() )
707 out << " _ps = 0;\n";
709 if ( redFsm->anyToStateActions() || redFsm->anyRegActions()
710 || redFsm->anyFromStateActions() )
712 out << " _acts, _nacts = nil\n";
715 if ( redFsm->anyConditions() )
716 out << " _widec = nil\n";
723 " if ( " << P() << " == " << PE() << " )\n";
724 rbxGoto(out << " ", "_out") << "\n" <<
728 if ( redFsm->errState != 0 ) {
731 " if ( " << CS() << " == " << redFsm->errState->id << " )\n";
732 rbxGoto(out << " ", "_out") << "\n" <<
736 rbxLabel(out, "_resume") << "\n";
738 if ( redFsm->anyFromStateActions() ) {
741 " _acts = " << ARR_OFF( A(), FSA() + "[" + CS() + "]" ) << ";\n"
742 " _nacts = " << " *_acts++;\n"
743 " while ( _nacts-- > 0 ) {\n"
744 " switch ( *_acts++ ) {\n";
745 FROM_STATE_ACTION_SWITCH();
753 " case ( " << CS() << " )\n";
761 if ( redFsm->anyRegActions() )
762 EXEC_FUNCS() << "\n";
765 rbxLabel(out, "_again") << "\n";
767 if ( redFsm->anyToStateActions() ) {
769 " _acts = " << ARR_OFF( A(), TSA() + "[" + CS() + "]" ) << ";\n"
770 " _nacts = " << " *_acts++;\n"
771 " while ( _nacts-- > 0 ) {\n"
772 " switch ( *_acts++ ) {\n";
773 TO_STATE_ACTION_SWITCH();
780 if ( redFsm->errState != 0 ) {
783 " if ( " << CS() << " == " << redFsm->errState->id << " )\n";
784 rbxGoto(out << " ", "_out") << "\n" <<
789 out << " " << P() << " += 1\n"
790 " if ( " << P() << " != " << PE() << " )\n";
791 rbxGoto(out << " ", "_resume") << "\n" <<
796 " " << P() << " += 1;\n";
797 rbxGoto(out << " ", "_resume") << "\n";
801 rbxLabel(out, "_out") << "\n";
806 void RbxGotoCodeGen::writeEOF()
808 if ( redFsm->anyEofActions() ) {
812 ARR_OFF( A(), EA() + "[" + CS() + "]" ) << ";\n"
813 " " << " _nacts = " << " *_acts++;\n"
814 " while ( _nacts-- > 0 ) {\n"
815 " switch ( *_acts++ ) {\n";
828 * indent-tabs-mode: 1
829 * c-file-style: "bsd"