1 /*
2 * Copyright 2006 Adrian Thurston <thurston@complang.org>
3 */
4
5 /* This file is part of Ragel.
6 *
7 * Ragel is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 *
12 * Ragel is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with Ragel; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21
22
23 #include "ragel.h"
24 #include "cdsplit.h"
25 #include "gendata.h"
26 #include <assert.h>
27
28 using std::ostream;
29 using std::ios;
30 using std::endl;
31
32 /* Emit the goto to take for a given transition. */
TRANS_GOTO(RedTransAp * trans,int level)33 std::ostream &SplitCodeGen::TRANS_GOTO( RedTransAp *trans, int level )
34 {
35 if ( trans->targ->partition == currentPartition ) {
36 if ( trans->action != 0 ) {
37 /* Go to the transition which will go to the state. */
38 out << TABS(level) << "goto tr" << trans->id << ";";
39 }
40 else {
41 /* Go directly to the target state. */
42 out << TABS(level) << "goto st" << trans->targ->id << ";";
43 }
44 }
45 else {
46 if ( trans->action != 0 ) {
47 /* Go to the transition which will go to the state. */
48 out << TABS(level) << "goto ptr" << trans->id << ";";
49 trans->partitionBoundary = true;
50 }
51 else {
52 /* Go directly to the target state. */
53 out << TABS(level) << "goto pst" << trans->targ->id << ";";
54 trans->targ->partitionBoundary = true;
55 }
56 }
57 return out;
58 }
59
60 /* Called from before writing the gotos for each state. */
GOTO_HEADER(RedStateAp * state,bool stateInPartition)61 void SplitCodeGen::GOTO_HEADER( RedStateAp *state, bool stateInPartition )
62 {
63 bool anyWritten = IN_TRANS_ACTIONS( state );
64
65 if ( state->labelNeeded )
66 out << "st" << state->id << ":\n";
67
68 if ( state->toStateAction != 0 ) {
69 /* Remember that we wrote an action. Write every action in the list. */
70 anyWritten = true;
71 for ( GenActionTable::Iter item = state->toStateAction->key; item.lte(); item++ ) {
72 ACTION( out, item->value, state->id, false,
73 state->toStateAction->anyNextStmt() );
74 }
75 }
76
77 /* Advance and test buffer pos. */
78 if ( state->labelNeeded ) {
79 if ( !noEnd ) {
80 out <<
81 " if ( ++" << P() << " == " << PE() << " )\n"
82 " goto _out" << state->id << ";\n";
83 }
84 else {
85 out <<
86 " " << P() << " += 1;\n";
87 }
88 }
89
90 /* Give the state a switch case. */
91 out << "case " << state->id << ":\n";
92
93 if ( state->fromStateAction != 0 ) {
94 /* Remember that we wrote an action. Write every action in the list. */
95 anyWritten = true;
96 for ( GenActionTable::Iter item = state->fromStateAction->key; item.lte(); item++ ) {
97 ACTION( out, item->value, state->id, false,
98 state->fromStateAction->anyNextStmt() );
99 }
100 }
101
102 if ( anyWritten )
103 genLineDirective( out );
104
105 /* Record the prev state if necessary. */
106 if ( state->anyRegCurStateRef() )
107 out << " _ps = " << state->id << ";\n";
108 }
109
STATE_GOTOS(int partition)110 std::ostream &SplitCodeGen::STATE_GOTOS( int partition )
111 {
112 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
113 if ( st->partition == partition ) {
114 if ( st == redFsm->errState )
115 STATE_GOTO_ERROR();
116 else {
117 /* We call into the base of the goto which calls back into us
118 * using virtual functions. Set the current partition rather
119 * than coding parameter passing throughout. */
120 currentPartition = partition;
121
122 /* Writing code above state gotos. */
123 GOTO_HEADER( st, st->partition == partition );
124
125 if ( st->stateCondVect.length() > 0 ) {
126 out << " _widec = " << GET_KEY() << ";\n";
127 emitCondBSearch( st, 1, 0, st->stateCondVect.length() - 1 );
128 }
129
130 /* Try singles. */
131 if ( st->outSingle.length() > 0 )
132 emitSingleSwitch( st );
133
134 /* Default case is to binary search for the ranges, if that fails then */
135 if ( st->outRange.length() > 0 )
136 emitRangeBSearch( st, 1, 0, st->outRange.length() - 1 );
137
138 /* Write the default transition. */
139 TRANS_GOTO( st->defTrans, 1 ) << "\n";
140 }
141 }
142 }
143 return out;
144 }
145
146
PART_TRANS(int partition)147 std::ostream &SplitCodeGen::PART_TRANS( int partition )
148 {
149 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) {
150 if ( trans->partitionBoundary ) {
151 out <<
152 "ptr" << trans->id << ":\n";
153
154 if ( trans->action != 0 ) {
155 /* If the action contains a next, then we must preload the current
156 * state since the action may or may not set it. */
157 if ( trans->action->anyNextStmt() )
158 out << " " << vCS() << " = " << trans->targ->id << ";\n";
159
160 /* Write each action in the list. */
161 for ( GenActionTable::Iter item = trans->action->key; item.lte(); item++ ) {
162 ACTION( out, item->value, trans->targ->id, false,
163 trans->action->anyNextStmt() );
164 }
165 }
166
167 out <<
168 " goto pst" << trans->targ->id << ";\n";
169 trans->targ->partitionBoundary = true;
170 }
171 }
172
173 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
174 if ( st->partitionBoundary ) {
175 out <<
176 " pst" << st->id << ":\n"
177 " " << vCS() << " = " << st->id << ";\n";
178
179 if ( st->toStateAction != 0 ) {
180 /* Remember that we wrote an action. Write every action in the list. */
181 for ( GenActionTable::Iter item = st->toStateAction->key; item.lte(); item++ ) {
182 ACTION( out, item->value, st->id, false,
183 st->toStateAction->anyNextStmt() );
184 }
185 genLineDirective( out );
186 }
187
188 ptOutLabelUsed = true;
189 out << " goto _pt_out; \n";
190 }
191 }
192 return out;
193 }
194
EXIT_STATES(int partition)195 std::ostream &SplitCodeGen::EXIT_STATES( int partition )
196 {
197 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
198 if ( st->partition == partition && st->outNeeded ) {
199 outLabelUsed = true;
200 out << " _out" << st->id << ": " << vCS() << " = " <<
201 st->id << "; goto _out; \n";
202 }
203 }
204 return out;
205 }
206
207
PARTITION(int partition)208 std::ostream &SplitCodeGen::PARTITION( int partition )
209 {
210 outLabelUsed = false;
211 ptOutLabelUsed = false;
212
213 /* Initialize the partition boundaries, which get set during the writing
214 * of states. After the state writing we will */
215 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
216 trans->partitionBoundary = false;
217 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
218 st->partitionBoundary = false;
219
220 out << " " << ALPH_TYPE() << " *p = *_pp, *pe = *_ppe;\n";
221
222 if ( redFsm->anyRegCurStateRef() )
223 out << " int _ps = 0;\n";
224
225 if ( redFsm->anyConditions() )
226 out << " " << WIDE_ALPH_TYPE() << " _widec;\n";
227
228 if ( useAgainLabel() ) {
229 out <<
230 " goto _resume;\n"
231 "\n"
232 "_again:\n"
233 " switch ( " << vCS() << " ) {\n";
234 AGAIN_CASES() <<
235 " default: break;\n"
236 " }\n"
237 "\n";
238
239
240 if ( !noEnd ) {
241 outLabelUsed = true;
242 out <<
243 " if ( ++" << P() << " == " << PE() << " )\n"
244 " goto _out;\n";
245
246 }
247 else {
248 out <<
249 " " << P() << " += 1;\n";
250 }
251
252 out <<
253 "_resume:\n";
254 }
255
256 out <<
257 " switch ( " << vCS() << " )\n {\n";
258 STATE_GOTOS( partition );
259 SWITCH_DEFAULT() <<
260 " }\n";
261 PART_TRANS( partition );
262 EXIT_STATES( partition );
263
264 if ( outLabelUsed ) {
265 out <<
266 "\n"
267 " _out:\n"
268 " *_pp = p;\n"
269 " *_ppe = pe;\n"
270 " return 0;\n";
271 }
272
273 if ( ptOutLabelUsed ) {
274 out <<
275 "\n"
276 " _pt_out:\n"
277 " *_pp = p;\n"
278 " *_ppe = pe;\n"
279 " return 1;\n";
280 }
281
282 return out;
283 }
284
PART_MAP()285 std::ostream &SplitCodeGen::PART_MAP()
286 {
287 int *partMap = new int[redFsm->stateList.length()];
288 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
289 partMap[st->id] = st->partition;
290
291 out << "\t";
292 int totalItem = 0;
293 for ( int i = 0; i < redFsm->stateList.length(); i++ ) {
294 out << partMap[i];
295 if ( i != redFsm->stateList.length() - 1 ) {
296 out << ", ";
297 if ( ++totalItem % IALL == 0 )
298 out << "\n\t";
299 }
300 }
301
302 delete[] partMap;
303 return out;
304 }
305
writeData()306 void SplitCodeGen::writeData()
307 {
308 out <<
309 "static const int " << START() << " = " << START_STATE_ID() << ";\n"
310 "\n";
311
312 if ( !noFinal ) {
313 out <<
314 "static const int " << FIRST_FINAL() << " = " << FIRST_FINAL_STATE() << ";\n"
315 "\n";
316 }
317
318 if ( !noError ) {
319 out <<
320 "static const int " << ERROR() << " = " << ERROR_STATE() << ";\n"
321 "\n";
322 }
323
324
325 OPEN_ARRAY( ARRAY_TYPE(numSplitPartitions), PM() );
326 PART_MAP();
327 CLOSE_ARRAY() <<
328 "\n";
329
330 for ( int p = 0; p < redFsm->nParts; p++ ) {
331 out << "int partition" << p << "( " << ALPH_TYPE() << " **_pp, " << ALPH_TYPE() <<
332 " **_ppe, struct " << FSM_NAME() << " *fsm );\n";
333 }
334 out << "\n";
335 }
336
ALL_PARTITIONS()337 std::ostream &SplitCodeGen::ALL_PARTITIONS()
338 {
339 /* compute the format string. */
340 int width = 0, high = redFsm->nParts - 1;
341 while ( high > 0 ) {
342 width++;
343 high /= 10;
344 }
345 assert( width <= 8 );
346 char suffFormat[] = "_%6.6d.c";
347 suffFormat[2] = suffFormat[4] = ( '0' + width );
348
349 for ( int p = 0; p < redFsm->nParts; p++ ) {
350 char suffix[10];
351 sprintf( suffix, suffFormat, p );
352 const char *fn = fileNameFromStem( sourceFileName, suffix );
353 const char *include = fileNameFromStem( sourceFileName, ".h" );
354
355 /* Create the filter on the output and open it. */
356 output_filter *partFilter = new output_filter( fn );
357 partFilter->open( fn, ios::out|ios::trunc );
358 if ( !partFilter->is_open() ) {
359 error() << "error opening " << fn << " for writing" << endl;
360 exit(1);
361 }
362
363 /* Attach the new file to the output stream. */
364 std::streambuf *prev_rdbuf = out.rdbuf( partFilter );
365
366 out <<
367 "#include \"" << include << "\"\n"
368 "int partition" << p << "( " << ALPH_TYPE() << " **_pp, " << ALPH_TYPE() <<
369 " **_ppe, struct " << FSM_NAME() << " *fsm )\n"
370 "{\n";
371 PARTITION( p ) <<
372 "}\n\n";
373 out.flush();
374
375 /* Fix the output stream. */
376 out.rdbuf( prev_rdbuf );
377 }
378 return out;
379 }
380
381
writeExec()382 void SplitCodeGen::writeExec()
383 {
384 /* Must set labels immediately before writing because we may depend on the
385 * noend write option. */
386 setLabelsNeeded();
387 out <<
388 " {\n"
389 " int _stat = 0;\n";
390
391 if ( !noEnd ) {
392 out <<
393 " if ( " << P() << " == " << PE() << " )\n"
394 " goto _out;\n";
395 }
396
397 out << " goto _resume;\n";
398
399 /* In this reentry, to-state actions have already been executed on the
400 * partition-switch exit from the last partition. */
401 out << "_reenter:\n";
402
403 if ( !noEnd ) {
404 out <<
405 " if ( ++" << P() << " == " << PE() << " )\n"
406 " goto _out;\n";
407 }
408 else {
409 out <<
410 " " << P() << " += 1;\n";
411 }
412
413 out << "_resume:\n";
414
415 out <<
416 " switch ( " << PM() << "[" << vCS() << "] ) {\n";
417 for ( int p = 0; p < redFsm->nParts; p++ ) {
418 out <<
419 " case " << p << ":\n"
420 " _stat = partition" << p << "( &p, &pe, fsm );\n"
421 " break;\n";
422 }
423 out <<
424 " }\n"
425 " if ( _stat )\n"
426 " goto _reenter;\n";
427
428 if ( !noEnd )
429 out << " _out: {}\n";
430
431 out <<
432 " }\n";
433
434 ALL_PARTITIONS();
435 }
436
setLabelsNeeded(RedStateAp * fromState,GenInlineList * inlineList)437 void SplitCodeGen::setLabelsNeeded( RedStateAp *fromState, GenInlineList *inlineList )
438 {
439 for ( GenInlineList::Iter item = *inlineList; item.lte(); item++ ) {
440 switch ( item->type ) {
441 case GenInlineItem::Goto: case GenInlineItem::Call: {
442 /* In split code gen we only need labels for transitions across
443 * partitions. */
444 if ( fromState->partition == item->targState->partition ){
445 /* Mark the target as needing a label. */
446 item->targState->labelNeeded = true;
447 }
448 break;
449 }
450 default: break;
451 }
452
453 if ( item->children != 0 )
454 setLabelsNeeded( fromState, item->children );
455 }
456 }
457
setLabelsNeeded(RedStateAp * fromState,RedTransAp * trans)458 void SplitCodeGen::setLabelsNeeded( RedStateAp *fromState, RedTransAp *trans )
459 {
460 /* In the split code gen we don't need labels for transitions across
461 * partitions. */
462 if ( fromState->partition == trans->targ->partition ) {
463 /* If there is no action with a next statement, then the label will be
464 * needed. */
465 trans->labelNeeded = true;
466 if ( trans->action == 0 || !trans->action->anyNextStmt() )
467 trans->targ->labelNeeded = true;
468 }
469
470 /* Need labels for states that have goto or calls in action code
471 * invoked on characters (ie, not from out action code). */
472 if ( trans->action != 0 ) {
473 /* Loop the actions. */
474 for ( GenActionTable::Iter act = trans->action->key; act.lte(); act++ ) {
475 /* Get the action and walk it's tree. */
476 setLabelsNeeded( fromState, act->value->inlineList );
477 }
478 }
479 }
480
481 /* Set up labelNeeded flag for each state. */
setLabelsNeeded()482 void SplitCodeGen::setLabelsNeeded()
483 {
484 /* If we use the _again label, then we the _again switch, which uses all
485 * labels. */
486 if ( useAgainLabel() ) {
487 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
488 st->labelNeeded = true;
489 }
490 else {
491 /* Do not use all labels by default, init all labelNeeded vars to false. */
492 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
493 st->labelNeeded = false;
494 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
495 trans->labelNeeded = false;
496
497 /* Walk all transitions and set only those that have targs. */
498 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
499 for ( RedTransList::Iter tel = st->outRange; tel.lte(); tel++ )
500 setLabelsNeeded( st, tel->value );
501
502 for ( RedTransList::Iter tel = st->outSingle; tel.lte(); tel++ )
503 setLabelsNeeded( st, tel->value );
504
505 if ( st->defTrans != 0 )
506 setLabelsNeeded( st, st->defTrans );
507 }
508 }
509
510 if ( !noEnd ) {
511 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ )
512 st->outNeeded = st->labelNeeded;
513 }
514 else {
515 if ( redFsm->errState != 0 )
516 redFsm->errState->outNeeded = true;
517
518 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ ) {
519 /* Any state with a transition in that has a break will need an
520 * out label. */
521 if ( trans->action != 0 && trans->action->anyBreakStmt() )
522 trans->targ->outNeeded = true;
523 }
524 }
525 }
526
527