1 /*
2 * Copyright 2001-2006 Adrian Thurston <thurston@complang.org>
3 * 2004 Erich Ocean <eric.ocean@ampede.com>
4 * 2005 Alan West <alan@alanz.com>
5 */
6
7 /* This file is part of Ragel.
8 *
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.
13 *
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.
18 *
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
22 */
23
24 #include "ragel.h"
25 #include "mlftable.h"
26 #include "redfsm.h"
27 #include "gendata.h"
28
29 /* Determine if we should use indicies or not. */
calcIndexSize()30 void OCamlFTabCodeGen::calcIndexSize()
31 {
32 int sizeWithInds = 0, sizeWithoutInds = 0;
33
34 /* Calculate cost of using with indicies. */
35 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
36 int totalIndex = st->outSingle.length() + st->outRange.length() +
37 (st->defTrans == 0 ? 0 : 1);
38 sizeWithInds += arrayTypeSize(redFsm->maxIndex) * totalIndex;
39 }
40 sizeWithInds += arrayTypeSize(redFsm->maxState) * redFsm->transSet.length();
41 if ( redFsm->anyActions() )
42 sizeWithInds += arrayTypeSize(redFsm->maxActListId) * redFsm->transSet.length();
43
44 /* Calculate the cost of not using indicies. */
45 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
46 int totalIndex = st->outSingle.length() + st->outRange.length() +
47 (st->defTrans == 0 ? 0 : 1);
48 sizeWithoutInds += arrayTypeSize(redFsm->maxState) * totalIndex;
49 if ( redFsm->anyActions() )
50 sizeWithoutInds += arrayTypeSize(redFsm->maxActListId) * totalIndex;
51 }
52
53 /* If using indicies reduces the size, use them. */
54 useIndicies = sizeWithInds < sizeWithoutInds;
55 }
56
TO_STATE_ACTION(RedStateAp * state)57 std::ostream &OCamlFTabCodeGen::TO_STATE_ACTION( RedStateAp *state )
58 {
59 int act = 0;
60 if ( state->toStateAction != 0 )
61 act = state->toStateAction->actListId+1;
62 out << act;
63 return out;
64 }
65
FROM_STATE_ACTION(RedStateAp * state)66 std::ostream &OCamlFTabCodeGen::FROM_STATE_ACTION( RedStateAp *state )
67 {
68 int act = 0;
69 if ( state->fromStateAction != 0 )
70 act = state->fromStateAction->actListId+1;
71 out << act;
72 return out;
73 }
74
EOF_ACTION(RedStateAp * state)75 std::ostream &OCamlFTabCodeGen::EOF_ACTION( RedStateAp *state )
76 {
77 int act = 0;
78 if ( state->eofAction != 0 )
79 act = state->eofAction->actListId+1;
80 out << act;
81 return out;
82 }
83
84
85 /* Write out the function for a transition. */
TRANS_ACTION(RedTransAp * trans)86 std::ostream &OCamlFTabCodeGen::TRANS_ACTION( RedTransAp *trans )
87 {
88 int action = 0;
89 if ( trans->action != 0 )
90 action = trans->action->actListId+1;
91 out << action;
92 return out;
93 }
94
95 /* Write out the function switch. This switch is keyed on the values
96 * of the func index. */
TO_STATE_ACTION_SWITCH()97 std::ostream &OCamlFTabCodeGen::TO_STATE_ACTION_SWITCH()
98 {
99 /* Loop the actions. */
100 for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
101 if ( redAct->numToStateRefs > 0 ) {
102 /* Write the entry label. */
103 out << "\t| " << redAct->actListId+1 << " ->\n";
104
105 /* Write each action in the list of action items. */
106 for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
107 ACTION( out, item->value, 0, false );
108
109 out << "\t()\n";
110 }
111 }
112
113 genLineDirective( out );
114 return out;
115 }
116
117 /* Write out the function switch. This switch is keyed on the values
118 * of the func index. */
FROM_STATE_ACTION_SWITCH()119 std::ostream &OCamlFTabCodeGen::FROM_STATE_ACTION_SWITCH()
120 {
121 /* Loop the actions. */
122 for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
123 if ( redAct->numFromStateRefs > 0 ) {
124 /* Write the entry label. */
125 out << "\t| " << redAct->actListId+1 << " ->\n";
126
127 /* Write each action in the list of action items. */
128 for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
129 ACTION( out, item->value, 0, false );
130
131 out << "\t()\n";
132 }
133 }
134
135 genLineDirective( out );
136 return out;
137 }
138
EOF_ACTION_SWITCH()139 std::ostream &OCamlFTabCodeGen::EOF_ACTION_SWITCH()
140 {
141 /* Loop the actions. */
142 for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
143 if ( redAct->numEofRefs > 0 ) {
144 /* Write the entry label. */
145 out << "\t| " << redAct->actListId+1 << " ->\n";
146
147 /* Write each action in the list of action items. */
148 for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
149 ACTION( out, item->value, 0, true );
150
151 out << "\t()\n";
152 }
153 }
154
155 genLineDirective( out );
156 return out;
157 }
158
159 /* Write out the function switch. This switch is keyed on the values
160 * of the func index. */
ACTION_SWITCH()161 std::ostream &OCamlFTabCodeGen::ACTION_SWITCH()
162 {
163 /* Loop the actions. */
164 for ( GenActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
165 if ( redAct->numTransRefs > 0 ) {
166 /* Write the entry label. */
167 out << "\t| " << redAct->actListId+1 << " ->\n";
168
169 /* Write each action in the list of action items. */
170 for ( GenActionTable::Iter item = redAct->key; item.lte(); item++ )
171 ACTION( out, item->value, 0, false );
172
173 out << "\t()\n";
174 }
175 }
176
177 genLineDirective( out );
178 return out;
179 }
180
writeData()181 void OCamlFTabCodeGen::writeData()
182 {
183 if ( redFsm->anyConditions() ) {
184 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondOffset), CO() );
185 COND_OFFSETS();
186 CLOSE_ARRAY() <<
187 "\n";
188
189 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondLen), CL() );
190 COND_LENS();
191 CLOSE_ARRAY() <<
192 "\n";
193
194 OPEN_ARRAY( WIDE_ALPH_TYPE(), CK() );
195 COND_KEYS();
196 CLOSE_ARRAY() <<
197 "\n";
198
199 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondSpaceId), C() );
200 COND_SPACES();
201 CLOSE_ARRAY() <<
202 "\n";
203 }
204
205 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxKeyOffset), KO() );
206 KEY_OFFSETS();
207 CLOSE_ARRAY() <<
208 "\n";
209
210 OPEN_ARRAY( WIDE_ALPH_TYPE(), K() );
211 KEYS();
212 CLOSE_ARRAY() <<
213 "\n";
214
215 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxSingleLen), SL() );
216 SINGLE_LENS();
217 CLOSE_ARRAY() <<
218 "\n";
219
220 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxRangeLen), RL() );
221 RANGE_LENS();
222 CLOSE_ARRAY() <<
223 "\n";
224
225 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset), IO() );
226 INDEX_OFFSETS();
227 CLOSE_ARRAY() <<
228 "\n";
229
230 if ( useIndicies ) {
231 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex), I() );
232 INDICIES();
233 CLOSE_ARRAY() <<
234 "\n";
235
236 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
237 TRANS_TARGS_WI();
238 CLOSE_ARRAY() <<
239 "\n";
240
241 if ( redFsm->anyActions() ) {
242 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActListId), TA() );
243 TRANS_ACTIONS_WI();
244 CLOSE_ARRAY() <<
245 "\n";
246 }
247 }
248 else {
249 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
250 TRANS_TARGS();
251 CLOSE_ARRAY() <<
252 "\n";
253
254 if ( redFsm->anyActions() ) {
255 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActListId), TA() );
256 TRANS_ACTIONS();
257 CLOSE_ARRAY() <<
258 "\n";
259 }
260 }
261
262 if ( redFsm->anyToStateActions() ) {
263 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
264 TO_STATE_ACTIONS();
265 CLOSE_ARRAY() <<
266 "\n";
267 }
268
269 if ( redFsm->anyFromStateActions() ) {
270 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
271 FROM_STATE_ACTIONS();
272 CLOSE_ARRAY() <<
273 "\n";
274 }
275
276 if ( redFsm->anyEofActions() ) {
277 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActListId), EA() );
278 EOF_ACTIONS();
279 CLOSE_ARRAY() <<
280 "\n";
281 }
282
283 if ( redFsm->anyEofTrans() ) {
284 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset+1), ET() );
285 EOF_TRANS();
286 CLOSE_ARRAY() <<
287 "\n";
288 }
289
290 STATE_IDS();
291
292 out << "type " << TYPE_STATE() << " = { mutable keys : int; mutable trans : int; }"
293 << TOP_SEP();
294
295 out << "exception Goto_match" << TOP_SEP();
296 out << "exception Goto_again" << TOP_SEP();
297 out << "exception Goto_eof_trans" << TOP_SEP();
298 }
299
writeExec()300 void OCamlFTabCodeGen::writeExec()
301 {
302 testEofUsed = false;
303 outLabelUsed = false;
304 initVarTypes();
305
306 out <<
307 " begin\n";
308
309 // if ( redFsm->anyRegCurStateRef() )
310 // out << klenType ", _ps";
311
312 out <<
313 " let state = { keys = 0; trans = 0; } in\n"
314 " let rec do_start () =\n";
315
316 // if ( redFsm->anyConditions() )
317 // out << " " << WIDE_ALPH_TYPE() << " _widec;\n";
318
319 if ( !noEnd ) {
320 testEofUsed = true;
321 out <<
322 " if " << P() << " = " << PE() << " then\n"
323 " do_test_eof ()\n"
324 "\telse\n";
325 }
326
327 if ( redFsm->errState != 0 ) {
328 outLabelUsed = true;
329 out <<
330 " if " << vCS() << " = " << redFsm->errState->id << " then\n"
331 " do_out ()\n"
332 "\telse\n";
333 }
334 out << "\tdo_resume ()\n";
335
336 out << "and do_resume () =\n";
337
338 if ( redFsm->anyFromStateActions() ) {
339 out <<
340 " begin match " << AT( FSA(), vCS() ) << " with\n";
341 FROM_STATE_ACTION_SWITCH();
342 SWITCH_DEFAULT() <<
343 " end;\n"
344 "\n";
345 }
346
347 if ( redFsm->anyConditions() )
348 COND_TRANSLATE();
349
350 out << "\tbegin try\n";
351 LOCATE_TRANS();
352 out << "\twith Goto_match -> () end;\n";
353
354 out <<
355 "\tdo_match ()\n";
356
357 out << "and do_match () =\n";
358
359 if ( useIndicies )
360 out << " state.trans <- " << CAST(transType) << AT( I(), "state.trans" ) << ";\n";
361
362 out << "\tdo_eof_trans ()\n";
363
364 // if ( redFsm->anyEofTrans() )
365 out << "and do_eof_trans () =\n";
366
367 if ( redFsm->anyRegCurStateRef() )
368 out << " let ps = " << vCS() << " in\n";
369
370 out <<
371 " " << vCS() << " <- " << AT( TT() ,"state.trans" ) << ";\n"
372 "\n";
373
374 if ( redFsm->anyRegActions() ) {
375 out <<
376 " begin try if " << AT( TA() , "state.trans" ) << " = 0 then\n"
377 " raise Goto_again;\n"
378 "\n"
379 " match " << AT( TA(), "state.trans" ) << " with\n";
380 ACTION_SWITCH();
381 SWITCH_DEFAULT() <<
382 " with Goto_again -> () end;\n"
383 "\n";
384 }
385 out << "\tdo_again ()\n";
386
387 // if ( redFsm->anyRegActions() || redFsm->anyActionGotos() ||
388 // redFsm->anyActionCalls() || redFsm->anyActionRets() )
389 out << "\tand do_again () =\n";
390
391 if ( redFsm->anyToStateActions() ) {
392 out <<
393 " begin match " << AT( TSA(), vCS() ) << " with\n";
394 TO_STATE_ACTION_SWITCH();
395 SWITCH_DEFAULT() <<
396 " end;\n"
397 "\n";
398 }
399
400 if ( redFsm->errState != 0 ) {
401 outLabelUsed = true;
402 out <<
403 " match " << vCS() << " with\n"
404 "\t| " << redFsm->errState->id << " -> do_out ()\n"
405 "\t| _ ->\n";
406 }
407
408 out << "\t" << P() << " <- " << P() << " + 1;\n";
409
410 if ( !noEnd ) {
411 out <<
412 " if " << P() << " <> " << PE() << " then\n"
413 " do_resume ()\n"
414 "\telse do_test_eof ()\n";
415 }
416 else {
417 out <<
418 " do_resume ()\n";
419 }
420
421 // if ( testEofUsed )
422 out << "and do_test_eof () =\n";
423
424 if ( redFsm->anyEofTrans() || redFsm->anyEofActions() ) {
425 out <<
426 " if " << P() << " = " << vEOF() << " then\n"
427 " begin try\n";
428
429 if ( redFsm->anyEofTrans() ) {
430 out <<
431 " if " << AT( ET(), vCS() ) << " > 0 then\n"
432 " begin\n"
433 " state.trans <- " << CAST(transType) << "(" << AT( ET(), vCS() ) << " - 1);\n"
434 " raise Goto_eof_trans;\n"
435 " end;\n";
436 }
437
438 if ( redFsm->anyEofActions() ) {
439 out <<
440 " begin match " << AT( EA(), vCS() ) << " with\n";
441 EOF_ACTION_SWITCH();
442 SWITCH_DEFAULT() <<
443 " end\n";
444 }
445
446 out <<
447 " with Goto_again -> do_again ()\n"
448 " | Goto_eof_trans -> do_eof_trans () end\n"
449 "\n";
450 }
451 else
452 {
453 out << "\t()\n";
454 }
455
456 if ( outLabelUsed )
457 out << " and do_out () = ()\n";
458
459 out << "\tin do_start ()\n";
460 out << " end;\n";
461 }
462
463