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 "mltable.h"
26 #include "redfsm.h"
27 #include "gendata.h"
28
29 /* Determine if we should use indicies or not. */
calcIndexSize()30 void OCamlTabCodeGen::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->maxActionLoc) * 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->maxActionLoc) * 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 &OCamlTabCodeGen::TO_STATE_ACTION( RedStateAp *state )
58 {
59 int act = 0;
60 if ( state->toStateAction != 0 )
61 act = state->toStateAction->location+1;
62 out << act;
63 return out;
64 }
65
FROM_STATE_ACTION(RedStateAp * state)66 std::ostream &OCamlTabCodeGen::FROM_STATE_ACTION( RedStateAp *state )
67 {
68 int act = 0;
69 if ( state->fromStateAction != 0 )
70 act = state->fromStateAction->location+1;
71 out << act;
72 return out;
73 }
74
EOF_ACTION(RedStateAp * state)75 std::ostream &OCamlTabCodeGen::EOF_ACTION( RedStateAp *state )
76 {
77 int act = 0;
78 if ( state->eofAction != 0 )
79 act = state->eofAction->location+1;
80 out << act;
81 return out;
82 }
83
84
TRANS_ACTION(RedTransAp * trans)85 std::ostream &OCamlTabCodeGen::TRANS_ACTION( RedTransAp *trans )
86 {
87 /* If there are actions, emit them. Otherwise emit zero. */
88 int act = 0;
89 if ( trans->action != 0 )
90 act = trans->action->location+1;
91 out << act;
92 return out;
93 }
94
TO_STATE_ACTION_SWITCH()95 std::ostream &OCamlTabCodeGen::TO_STATE_ACTION_SWITCH()
96 {
97 /* Walk the list of functions, printing the cases. */
98 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
99 /* Write out referenced actions. */
100 if ( act->numToStateRefs > 0 ) {
101 /* Write the case label, the action and the case break. */
102 out << "\t| " << act->actionId << " ->\n";
103 ACTION( out, act, 0, false );
104 }
105 }
106
107 genLineDirective( out );
108 return out;
109 }
110
FROM_STATE_ACTION_SWITCH()111 std::ostream &OCamlTabCodeGen::FROM_STATE_ACTION_SWITCH()
112 {
113 /* Walk the list of functions, printing the cases. */
114 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
115 /* Write out referenced actions. */
116 if ( act->numFromStateRefs > 0 ) {
117 /* Write the case label, the action and the case break. */
118 out << "\t| " << act->actionId << " ->\n";
119 ACTION( out, act, 0, false );
120 }
121 }
122
123 genLineDirective( out );
124 return out;
125 }
126
EOF_ACTION_SWITCH()127 std::ostream &OCamlTabCodeGen::EOF_ACTION_SWITCH()
128 {
129 /* Walk the list of functions, printing the cases. */
130 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
131 /* Write out referenced actions. */
132 if ( act->numEofRefs > 0 ) {
133 /* Write the case label, the action and the case break. */
134 out << "\t| " << act->actionId << " ->\n";
135 ACTION( out, act, 0, true );
136 }
137 }
138
139 genLineDirective( out );
140 return out;
141 }
142
143
ACTION_SWITCH()144 std::ostream &OCamlTabCodeGen::ACTION_SWITCH()
145 {
146 /* Walk the list of functions, printing the cases. */
147 for ( GenActionList::Iter act = actionList; act.lte(); act++ ) {
148 /* Write out referenced actions. */
149 if ( act->numTransRefs > 0 ) {
150 /* Write the case label, the action and the case break. */
151 out << "\t| " << act->actionId << " -> \n";
152 ACTION( out, act, 0, false );
153 }
154 }
155
156 genLineDirective( out );
157 return out;
158 }
159
COND_OFFSETS()160 std::ostream &OCamlTabCodeGen::COND_OFFSETS()
161 {
162 out << "\t";
163 int totalStateNum = 0, curKeyOffset = 0;
164 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
165 /* Write the key offset. */
166 out << curKeyOffset;
167 if ( !st.last() ) {
168 out << ARR_SEP();
169 if ( ++totalStateNum % IALL == 0 )
170 out << "\n\t";
171 }
172
173 /* Move the key offset ahead. */
174 curKeyOffset += st->stateCondList.length();
175 }
176 out << "\n";
177 return out;
178 }
179
KEY_OFFSETS()180 std::ostream &OCamlTabCodeGen::KEY_OFFSETS()
181 {
182 out << "\t";
183 int totalStateNum = 0, curKeyOffset = 0;
184 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
185 /* Write the key offset. */
186 out << curKeyOffset;
187 if ( !st.last() ) {
188 out << ARR_SEP();
189 if ( ++totalStateNum % IALL == 0 )
190 out << "\n\t";
191 }
192
193 /* Move the key offset ahead. */
194 curKeyOffset += st->outSingle.length() + st->outRange.length()*2;
195 }
196 out << "\n";
197 return out;
198 }
199
200
INDEX_OFFSETS()201 std::ostream &OCamlTabCodeGen::INDEX_OFFSETS()
202 {
203 out << "\t";
204 int totalStateNum = 0, curIndOffset = 0;
205 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
206 /* Write the index offset. */
207 out << curIndOffset;
208 if ( !st.last() ) {
209 out << ARR_SEP();
210 if ( ++totalStateNum % IALL == 0 )
211 out << "\n\t";
212 }
213
214 /* Move the index offset ahead. */
215 curIndOffset += st->outSingle.length() + st->outRange.length();
216 if ( st->defTrans != 0 )
217 curIndOffset += 1;
218 }
219 out << "\n";
220 return out;
221 }
222
COND_LENS()223 std::ostream &OCamlTabCodeGen::COND_LENS()
224 {
225 out << "\t";
226 int totalStateNum = 0;
227 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
228 /* Write singles length. */
229 out << st->stateCondList.length();
230 if ( !st.last() ) {
231 out << ARR_SEP();
232 if ( ++totalStateNum % IALL == 0 )
233 out << "\n\t";
234 }
235 }
236 out << "\n";
237 return out;
238 }
239
240
SINGLE_LENS()241 std::ostream &OCamlTabCodeGen::SINGLE_LENS()
242 {
243 out << "\t";
244 int totalStateNum = 0;
245 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
246 /* Write singles length. */
247 out << st->outSingle.length();
248 if ( !st.last() ) {
249 out << ARR_SEP();
250 if ( ++totalStateNum % IALL == 0 )
251 out << "\n\t";
252 }
253 }
254 out << "\n";
255 return out;
256 }
257
RANGE_LENS()258 std::ostream &OCamlTabCodeGen::RANGE_LENS()
259 {
260 out << "\t";
261 int totalStateNum = 0;
262 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
263 /* Emit length of range index. */
264 out << st->outRange.length();
265 if ( !st.last() ) {
266 out << ARR_SEP();
267 if ( ++totalStateNum % IALL == 0 )
268 out << "\n\t";
269 }
270 }
271 out << "\n";
272 return out;
273 }
274
TO_STATE_ACTIONS()275 std::ostream &OCamlTabCodeGen::TO_STATE_ACTIONS()
276 {
277 out << "\t";
278 int totalStateNum = 0;
279 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
280 /* Write any eof action. */
281 TO_STATE_ACTION(st);
282 if ( !st.last() ) {
283 out << ARR_SEP();
284 if ( ++totalStateNum % IALL == 0 )
285 out << "\n\t";
286 }
287 }
288 out << "\n";
289 return out;
290 }
291
FROM_STATE_ACTIONS()292 std::ostream &OCamlTabCodeGen::FROM_STATE_ACTIONS()
293 {
294 out << "\t";
295 int totalStateNum = 0;
296 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
297 /* Write any eof action. */
298 FROM_STATE_ACTION(st);
299 if ( !st.last() ) {
300 out << ARR_SEP();
301 if ( ++totalStateNum % IALL == 0 )
302 out << "\n\t";
303 }
304 }
305 out << "\n";
306 return out;
307 }
308
EOF_ACTIONS()309 std::ostream &OCamlTabCodeGen::EOF_ACTIONS()
310 {
311 out << "\t";
312 int totalStateNum = 0;
313 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
314 /* Write any eof action. */
315 EOF_ACTION(st);
316 if ( !st.last() ) {
317 out << ARR_SEP();
318 if ( ++totalStateNum % IALL == 0 )
319 out << "\n\t";
320 }
321 }
322 out << "\n";
323 return out;
324 }
325
EOF_TRANS()326 std::ostream &OCamlTabCodeGen::EOF_TRANS()
327 {
328 out << "\t";
329 int totalStateNum = 0;
330 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
331 /* Write any eof action. */
332 long trans = 0;
333 if ( st->eofTrans != 0 ) {
334 assert( st->eofTrans->pos >= 0 );
335 trans = st->eofTrans->pos+1;
336 }
337 out << trans;
338
339 if ( !st.last() ) {
340 out << ARR_SEP();
341 if ( ++totalStateNum % IALL == 0 )
342 out << "\n\t";
343 }
344 }
345 out << "\n";
346 return out;
347 }
348
349
COND_KEYS()350 std::ostream &OCamlTabCodeGen::COND_KEYS()
351 {
352 out << '\t';
353 int totalTrans = 0;
354 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
355 /* Loop the state's transitions. */
356 for ( GenStateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
357 /* Lower key. */
358 out << ALPHA_KEY( sc->lowKey ) << ARR_SEP();
359 if ( ++totalTrans % IALL == 0 )
360 out << "\n\t";
361
362 /* Upper key. */
363 out << ALPHA_KEY( sc->highKey ) << ARR_SEP();
364 if ( ++totalTrans % IALL == 0 )
365 out << "\n\t";
366 }
367 }
368
369 /* Output one last number so we don't have to figure out when the last
370 * entry is and avoid writing a comma. */
371 out << 0 << "\n";
372 return out;
373 }
374
COND_SPACES()375 std::ostream &OCamlTabCodeGen::COND_SPACES()
376 {
377 out << '\t';
378 int totalTrans = 0;
379 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
380 /* Loop the state's transitions. */
381 for ( GenStateCondList::Iter sc = st->stateCondList; sc.lte(); sc++ ) {
382 /* Cond Space id. */
383 out << sc->condSpace->condSpaceId << ARR_SEP();
384 if ( ++totalTrans % IALL == 0 )
385 out << "\n\t";
386 }
387 }
388
389 /* Output one last number so we don't have to figure out when the last
390 * entry is and avoid writing a comma. */
391 out << 0 << "\n";
392 return out;
393 }
394
KEYS()395 std::ostream &OCamlTabCodeGen::KEYS()
396 {
397 out << '\t';
398 int totalTrans = 0;
399 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
400 /* Loop the singles. */
401 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
402 out << ALPHA_KEY( stel->lowKey ) << ARR_SEP();
403 if ( ++totalTrans % IALL == 0 )
404 out << "\n\t";
405 }
406
407 /* Loop the state's transitions. */
408 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
409 /* Lower key. */
410 out << ALPHA_KEY( rtel->lowKey ) << ARR_SEP();
411 if ( ++totalTrans % IALL == 0 )
412 out << "\n\t";
413
414 /* Upper key. */
415 out << ALPHA_KEY( rtel->highKey ) << ARR_SEP();
416 if ( ++totalTrans % IALL == 0 )
417 out << "\n\t";
418 }
419 }
420
421 /* Output one last number so we don't have to figure out when the last
422 * entry is and avoid writing a comma. */
423 out << 0 << "\n";
424 return out;
425 }
426
INDICIES()427 std::ostream &OCamlTabCodeGen::INDICIES()
428 {
429 int totalTrans = 0;
430 out << '\t';
431 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
432 /* Walk the singles. */
433 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
434 out << stel->value->id << ARR_SEP();
435 if ( ++totalTrans % IALL == 0 )
436 out << "\n\t";
437 }
438
439 /* Walk the ranges. */
440 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
441 out << rtel->value->id << ARR_SEP();
442 if ( ++totalTrans % IALL == 0 )
443 out << "\n\t";
444 }
445
446 /* The state's default index goes next. */
447 if ( st->defTrans != 0 ) {
448 out << st->defTrans->id << ARR_SEP();
449 if ( ++totalTrans % IALL == 0 )
450 out << "\n\t";
451 }
452 }
453
454 /* Output one last number so we don't have to figure out when the last
455 * entry is and avoid writing a comma. */
456 out << 0 << "\n";
457 return out;
458 }
459
TRANS_TARGS()460 std::ostream &OCamlTabCodeGen::TRANS_TARGS()
461 {
462 int totalTrans = 0;
463 out << '\t';
464 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
465 /* Walk the singles. */
466 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
467 RedTransAp *trans = stel->value;
468 out << trans->targ->id << ARR_SEP();
469 if ( ++totalTrans % IALL == 0 )
470 out << "\n\t";
471 }
472
473 /* Walk the ranges. */
474 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
475 RedTransAp *trans = rtel->value;
476 out << trans->targ->id << ARR_SEP();
477 if ( ++totalTrans % IALL == 0 )
478 out << "\n\t";
479 }
480
481 /* The state's default target state. */
482 if ( st->defTrans != 0 ) {
483 RedTransAp *trans = st->defTrans;
484 out << trans->targ->id << ARR_SEP();
485 if ( ++totalTrans % IALL == 0 )
486 out << "\n\t";
487 }
488 }
489
490 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
491 if ( st->eofTrans != 0 ) {
492 RedTransAp *trans = st->eofTrans;
493 trans->pos = totalTrans;
494 out << trans->targ->id << ARR_SEP();
495 if ( ++totalTrans % IALL == 0 )
496 out << "\n\t";
497 }
498 }
499
500
501 /* Output one last number so we don't have to figure out when the last
502 * entry is and avoid writing a comma. */
503 out << 0 << "\n";
504 return out;
505 }
506
507
TRANS_ACTIONS()508 std::ostream &OCamlTabCodeGen::TRANS_ACTIONS()
509 {
510 int totalTrans = 0;
511 out << '\t';
512 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
513 /* Walk the singles. */
514 for ( RedTransList::Iter stel = st->outSingle; stel.lte(); stel++ ) {
515 RedTransAp *trans = stel->value;
516 TRANS_ACTION( trans ) << ARR_SEP();
517 if ( ++totalTrans % IALL == 0 )
518 out << "\n\t";
519 }
520
521 /* Walk the ranges. */
522 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
523 RedTransAp *trans = rtel->value;
524 TRANS_ACTION( trans ) << ARR_SEP();
525 if ( ++totalTrans % IALL == 0 )
526 out << "\n\t";
527 }
528
529 /* The state's default index goes next. */
530 if ( st->defTrans != 0 ) {
531 RedTransAp *trans = st->defTrans;
532 TRANS_ACTION( trans ) << ARR_SEP();
533 if ( ++totalTrans % IALL == 0 )
534 out << "\n\t";
535 }
536 }
537
538 for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
539 if ( st->eofTrans != 0 ) {
540 RedTransAp *trans = st->eofTrans;
541 TRANS_ACTION( trans ) << ARR_SEP();
542 if ( ++totalTrans % IALL == 0 )
543 out << "\n\t";
544 }
545 }
546
547 /* Output one last number so we don't have to figure out when the last
548 * entry is and avoid writing a comma. */
549 out << 0 << "\n";
550 return out;
551 }
552
TRANS_TARGS_WI()553 std::ostream &OCamlTabCodeGen::TRANS_TARGS_WI()
554 {
555 /* Transitions must be written ordered by their id. */
556 RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
557 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
558 transPtrs[trans->id] = trans;
559
560 /* Keep a count of the num of items in the array written. */
561 out << '\t';
562 int totalStates = 0;
563 for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
564 /* Record the position, need this for eofTrans. */
565 RedTransAp *trans = transPtrs[t];
566 trans->pos = t;
567
568 /* Write out the target state. */
569 out << trans->targ->id;
570 if ( t < redFsm->transSet.length()-1 ) {
571 out << ARR_SEP();
572 if ( ++totalStates % IALL == 0 )
573 out << "\n\t";
574 }
575 }
576 out << "\n";
577 delete[] transPtrs;
578 return out;
579 }
580
581
TRANS_ACTIONS_WI()582 std::ostream &OCamlTabCodeGen::TRANS_ACTIONS_WI()
583 {
584 /* Transitions must be written ordered by their id. */
585 RedTransAp **transPtrs = new RedTransAp*[redFsm->transSet.length()];
586 for ( TransApSet::Iter trans = redFsm->transSet; trans.lte(); trans++ )
587 transPtrs[trans->id] = trans;
588
589 /* Keep a count of the num of items in the array written. */
590 out << '\t';
591 int totalAct = 0;
592 for ( int t = 0; t < redFsm->transSet.length(); t++ ) {
593 /* Write the function for the transition. */
594 RedTransAp *trans = transPtrs[t];
595 TRANS_ACTION( trans );
596 if ( t < redFsm->transSet.length()-1 ) {
597 out << ARR_SEP();
598 if ( ++totalAct % IALL == 0 )
599 out << "\n\t";
600 }
601 }
602 out << "\n";
603 delete[] transPtrs;
604 return out;
605 }
606
GOTO(ostream & ret,int gotoDest,bool inFinish)607 void OCamlTabCodeGen::GOTO( ostream &ret, int gotoDest, bool inFinish )
608 {
609 ret << "begin " << vCS() << " <- " << gotoDest << "; " <<
610 CTRL_FLOW() << "raise Goto_again end";
611 }
612
GOTO_EXPR(ostream & ret,GenInlineItem * ilItem,bool inFinish)613 void OCamlTabCodeGen::GOTO_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish )
614 {
615 ret << "begin " << vCS() << " <- (";
616 INLINE_LIST( ret, ilItem->children, 0, inFinish );
617 ret << "); " << CTRL_FLOW() << "raise Goto_again end";
618 }
619
CURS(ostream & ret,bool inFinish)620 void OCamlTabCodeGen::CURS( ostream &ret, bool inFinish )
621 {
622 ret << "(_ps)";
623 }
624
TARGS(ostream & ret,bool inFinish,int targState)625 void OCamlTabCodeGen::TARGS( ostream &ret, bool inFinish, int targState )
626 {
627 ret << "(" << vCS() << ")";
628 }
629
NEXT(ostream & ret,int nextDest,bool inFinish)630 void OCamlTabCodeGen::NEXT( ostream &ret, int nextDest, bool inFinish )
631 {
632 ret << vCS() << " <- " << nextDest << ";";
633 }
634
NEXT_EXPR(ostream & ret,GenInlineItem * ilItem,bool inFinish)635 void OCamlTabCodeGen::NEXT_EXPR( ostream &ret, GenInlineItem *ilItem, bool inFinish )
636 {
637 ret << vCS() << " <- (";
638 INLINE_LIST( ret, ilItem->children, 0, inFinish );
639 ret << ");";
640 }
641
CALL(ostream & ret,int callDest,int targState,bool inFinish)642 void OCamlTabCodeGen::CALL( ostream &ret, int callDest, int targState, bool inFinish )
643 {
644 if ( prePushExpr != 0 ) {
645 ret << "begin ";
646 INLINE_LIST( ret, prePushExpr, 0, false );
647 }
648
649 ret << "begin " << AT( STACK(), POST_INCR(TOP()) ) << " <- " << vCS() << "; ";
650 ret << vCS() << " <- " << callDest << "; " << CTRL_FLOW() << "raise Goto_again end ";
651
652 if ( prePushExpr != 0 )
653 ret << "end";
654 }
655
CALL_EXPR(ostream & ret,GenInlineItem * ilItem,int targState,bool inFinish)656 void OCamlTabCodeGen::CALL_EXPR( ostream &ret, GenInlineItem *ilItem, int targState, bool inFinish )
657 {
658 if ( prePushExpr != 0 ) {
659 ret << "begin ";
660 INLINE_LIST( ret, prePushExpr, 0, false );
661 }
662
663 ret << "begin " << AT(STACK(), POST_INCR(TOP()) ) << " <- " << vCS() << "; " << vCS() << " <- (";
664 INLINE_LIST( ret, ilItem->children, targState, inFinish );
665 ret << "); " << CTRL_FLOW() << "raise Goto_again end ";
666
667 if ( prePushExpr != 0 )
668 ret << "end";
669 }
670
RET(ostream & ret,bool inFinish)671 void OCamlTabCodeGen::RET( ostream &ret, bool inFinish )
672 {
673 ret << "begin " << vCS() << " <- " << AT(STACK(), PRE_DECR(TOP()) ) << "; ";
674
675 if ( postPopExpr != 0 ) {
676 ret << "begin ";
677 INLINE_LIST( ret, postPopExpr, 0, false );
678 ret << "end ";
679 }
680
681 ret << CTRL_FLOW() << "raise Goto_again end";
682 }
683
BREAK(ostream & ret,int targState)684 void OCamlTabCodeGen::BREAK( ostream &ret, int targState )
685 {
686 outLabelUsed = true;
687 ret << "begin " << P() << " <- " << P() << " + 1; " << CTRL_FLOW() << "raise Goto_out end";
688 }
689
writeData()690 void OCamlTabCodeGen::writeData()
691 {
692 /* If there are any transtion functions then output the array. If there
693 * are none, don't bother emitting an empty array that won't be used. */
694 if ( redFsm->anyActions() ) {
695 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActArrItem), A() );
696 ACTIONS_ARRAY();
697 CLOSE_ARRAY() <<
698 "\n";
699 }
700
701 if ( redFsm->anyConditions() ) {
702 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondOffset), CO() );
703 COND_OFFSETS();
704 CLOSE_ARRAY() <<
705 "\n";
706
707 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondLen), CL() );
708 COND_LENS();
709 CLOSE_ARRAY() <<
710 "\n";
711
712 OPEN_ARRAY( WIDE_ALPH_TYPE(), CK() );
713 COND_KEYS();
714 CLOSE_ARRAY() <<
715 "\n";
716
717 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxCondSpaceId), C() );
718 COND_SPACES();
719 CLOSE_ARRAY() <<
720 "\n";
721 }
722
723 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxKeyOffset), KO() );
724 KEY_OFFSETS();
725 CLOSE_ARRAY() <<
726 "\n";
727
728 OPEN_ARRAY( WIDE_ALPH_TYPE(), K() );
729 KEYS();
730 CLOSE_ARRAY() <<
731 "\n";
732
733 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxSingleLen), SL() );
734 SINGLE_LENS();
735 CLOSE_ARRAY() <<
736 "\n";
737
738 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxRangeLen), RL() );
739 RANGE_LENS();
740 CLOSE_ARRAY() <<
741 "\n";
742
743 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset), IO() );
744 INDEX_OFFSETS();
745 CLOSE_ARRAY() <<
746 "\n";
747
748 if ( useIndicies ) {
749 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndex), I() );
750 INDICIES();
751 CLOSE_ARRAY() <<
752 "\n";
753
754 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
755 TRANS_TARGS_WI();
756 CLOSE_ARRAY() <<
757 "\n";
758
759 if ( redFsm->anyActions() ) {
760 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
761 TRANS_ACTIONS_WI();
762 CLOSE_ARRAY() <<
763 "\n";
764 }
765 }
766 else {
767 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxState), TT() );
768 TRANS_TARGS();
769 CLOSE_ARRAY() <<
770 "\n";
771
772 if ( redFsm->anyActions() ) {
773 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TA() );
774 TRANS_ACTIONS();
775 CLOSE_ARRAY() <<
776 "\n";
777 }
778 }
779
780 if ( redFsm->anyToStateActions() ) {
781 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), TSA() );
782 TO_STATE_ACTIONS();
783 CLOSE_ARRAY() <<
784 "\n";
785 }
786
787 if ( redFsm->anyFromStateActions() ) {
788 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), FSA() );
789 FROM_STATE_ACTIONS();
790 CLOSE_ARRAY() <<
791 "\n";
792 }
793
794 if ( redFsm->anyEofActions() ) {
795 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxActionLoc), EA() );
796 EOF_ACTIONS();
797 CLOSE_ARRAY() <<
798 "\n";
799 }
800
801 if ( redFsm->anyEofTrans() ) {
802 OPEN_ARRAY( ARRAY_TYPE(redFsm->maxIndexOffset+1), ET() );
803 EOF_TRANS();
804 CLOSE_ARRAY() <<
805 "\n";
806 }
807
808 STATE_IDS();
809
810 out << "type " << TYPE_STATE() << " = { mutable keys : int; mutable trans : int; mutable acts : int; mutable nacts : int; }"
811 << TOP_SEP();
812
813 out << "exception Goto_match" << TOP_SEP();
814 out << "exception Goto_again" << TOP_SEP();
815 out << "exception Goto_eof_trans" << TOP_SEP();
816 }
817
LOCATE_TRANS()818 void OCamlTabCodeGen::LOCATE_TRANS()
819 {
820 out <<
821 " state.keys <- " << AT( KO(), vCS() ) << ";\n"
822 " state.trans <- " << CAST(transType) << AT( IO(), vCS() ) << ";\n"
823 "\n"
824 " let klen = " << AT( SL(), vCS() ) << " in\n"
825 " if klen > 0 then begin\n"
826 " let lower : " << signedKeysType << " ref = ref state.keys in\n"
827 " let upper : " << signedKeysType << " ref = ref " << CAST(signedKeysType) <<
828 "(state.keys + klen - 1) in\n"
829 " while !upper >= !lower do\n"
830 " let mid = " << CAST(signedKeysType) << " (!lower + ((!upper - !lower) / 2)) in\n"
831 " if " << GET_WIDE_KEY() << " < " << AT( K(), "mid" ) << " then\n"
832 " upper := " << CAST(signedKeysType) << " (mid - 1)\n"
833 " else if " << GET_WIDE_KEY() << " > " << AT( K(), "mid" ) << " then\n"
834 " lower := " << CAST(signedKeysType) << " (mid + 1)\n"
835 " else begin\n"
836 " state.trans <- state.trans + " << CAST(transType) << " (mid - state.keys);\n"
837 " raise Goto_match;\n"
838 " end\n"
839 " done;\n"
840 " state.keys <- state.keys + " << CAST(keysType) << " klen;\n"
841 " state.trans <- state.trans + " << CAST(transType) << " klen;\n"
842 " end;\n"
843 "\n"
844 " let klen = " << AT( RL(), vCS() ) << " in\n"
845 " if klen > 0 then begin\n"
846 " let lower : " << signedKeysType << " ref = ref state.keys in\n"
847 " let upper : " << signedKeysType << " ref = ref " << CAST(signedKeysType) <<
848 "(state.keys + (klen * 2) - 2) in\n"
849 " while !upper >= !lower do\n"
850 " let mid = " << CAST(signedKeysType) << " (!lower + (((!upper - !lower) / 2) land (lnot 1))) in\n"
851 " if " << GET_WIDE_KEY() << " < " << AT( K() , "mid" ) << " then\n"
852 " upper := " << CAST(signedKeysType) << " (mid - 2)\n"
853 " else if " << GET_WIDE_KEY() << " > " << AT( K(), "mid+1" ) << " then\n"
854 " lower := " << CAST(signedKeysType) << " (mid + 2)\n"
855 " else begin\n"
856 " state.trans <- state.trans + " << CAST(transType) << "((mid - state.keys) / 2);\n"
857 " raise Goto_match;\n"
858 " end\n"
859 " done;\n"
860 " state.trans <- state.trans + " << CAST(transType) << " klen;\n"
861 " end;\n"
862 "\n";
863 }
864
COND_TRANSLATE()865 void OCamlTabCodeGen::COND_TRANSLATE()
866 {
867 out <<
868 " _widec = " << GET_KEY() << ";\n"
869 " _klen = " << CL() << "[" << vCS() << "];\n"
870 " _keys = " << CAST(keysType) << " ("<< CO() << "[" << vCS() << "]*2);\n"
871 " if ( _klen > 0 ) {\n"
872 " " << signedKeysType << " _lower = _keys;\n"
873 " " << signedKeysType << " _mid;\n"
874 " " << signedKeysType << " _upper = " << CAST(signedKeysType) <<
875 " (_keys + (_klen<<1) - 2);\n"
876 " while (true) {\n"
877 " if ( _upper < _lower )\n"
878 " break;\n"
879 "\n"
880 " _mid = " << CAST(signedKeysType) <<
881 " (_lower + (((_upper-_lower) >> 1) & ~1));\n"
882 " if ( " << GET_WIDE_KEY() << " < " << CK() << "[_mid] )\n"
883 " _upper = " << CAST(signedKeysType) << " (_mid - 2);\n"
884 " else if ( " << GET_WIDE_KEY() << " > " << CK() << "[_mid+1] )\n"
885 " _lower = " << CAST(signedKeysType) << " (_mid + 2);\n"
886 " else {\n"
887 " switch ( " << C() << "[" << CO() << "[" << vCS() << "]"
888 " + ((_mid - _keys)>>1)] ) {\n";
889
890 for ( CondSpaceList::Iter csi = condSpaceList; csi.lte(); csi++ ) {
891 GenCondSpace *condSpace = csi;
892 out << " case " << condSpace->condSpaceId << ": {\n";
893 out << TABS(2) << "_widec = " << CAST(WIDE_ALPH_TYPE()) << "(" <<
894 KEY(condSpace->baseKey) << " + (" << GET_KEY() <<
895 " - " << KEY(keyOps->minKey) << "));\n";
896
897 for ( GenCondSet::Iter csi = condSpace->condSet; csi.lte(); csi++ ) {
898 out << TABS(2) << "if ( ";
899 CONDITION( out, *csi );
900 Size condValOffset = ((1 << csi.pos()) * keyOps->alphSize());
901 out << " ) _widec += " << condValOffset << ";\n";
902 }
903
904 out <<
905 " break;\n"
906 " }\n";
907 }
908
909 SWITCH_DEFAULT();
910
911 out <<
912 " }\n"
913 " break;\n"
914 " }\n"
915 " }\n"
916 " }\n"
917 "\n";
918 }
919
writeExec()920 void OCamlTabCodeGen::writeExec()
921 {
922 testEofUsed = false;
923 outLabelUsed = false;
924 initVarTypes();
925
926 out <<
927 " begin\n";
928 // " " << klenType << " _klen";
929
930 // if ( redFsm->anyRegCurStateRef() )
931 // out << ", _ps";
932
933 /*
934 out << " " << transType << " _trans;\n";
935
936 if ( redFsm->anyConditions() )
937 out << " " << WIDE_ALPH_TYPE() << " _widec;\n";
938
939 if ( redFsm->anyToStateActions() || redFsm->anyRegActions()
940 || redFsm->anyFromStateActions() )
941 {
942 out <<
943 " int _acts;\n"
944 " int _nacts;\n";
945 }
946
947 out <<
948 " " << keysType << " _keys;\n"
949 "\n";
950 // " " << PTR_CONST() << WIDE_ALPH_TYPE() << POINTER() << "_keys;\n"
951 */
952
953 out <<
954 " let state = { keys = 0; trans = 0; acts = 0; nacts = 0; } in\n"
955 " let rec do_start () =\n";
956 if ( !noEnd ) {
957 testEofUsed = true;
958 out <<
959 " if " << P() << " = " << PE() << " then\n"
960 " do_test_eof ()\n"
961 "\telse\n";
962 }
963
964 if ( redFsm->errState != 0 ) {
965 outLabelUsed = true;
966 out <<
967 " if " << vCS() << " = " << redFsm->errState->id << " then\n"
968 " do_out ()\n"
969 "\telse\n";
970 }
971 out << "\tdo_resume ()\n";
972
973 out << "and do_resume () =\n";
974
975 if ( redFsm->anyFromStateActions() ) {
976 out <<
977 " state.acts <- " << AT( FSA(), vCS() ) << ";\n"
978 " state.nacts <- " << AT( A(), POST_INCR("state.acts") ) << ";\n"
979 " while " << POST_DECR("state.nacts") << " > 0 do\n"
980 " begin match " << AT( A(), POST_INCR("state.acts") ) << " with\n";
981 FROM_STATE_ACTION_SWITCH();
982 SWITCH_DEFAULT() <<
983 " end\n"
984 " done;\n"
985 "\n";
986 }
987
988 if ( redFsm->anyConditions() )
989 COND_TRANSLATE();
990
991 out << "\tbegin try\n";
992 LOCATE_TRANS();
993 out << "\twith Goto_match -> () end;\n";
994
995 out <<
996 "\tdo_match ()\n";
997
998 out << "and do_match () =\n";
999
1000 if ( useIndicies )
1001 out << " state.trans <- " << CAST(transType) << AT( I(), "state.trans" ) << ";\n";
1002
1003 out << "\tdo_eof_trans ()\n";
1004
1005 // if ( redFsm->anyEofTrans() )
1006 out << "and do_eof_trans () =\n";
1007
1008 if ( redFsm->anyRegCurStateRef() )
1009 out << " let ps = " << vCS() << " in\n";
1010
1011 out <<
1012 " " << vCS() << " <- " << AT( TT() ,"state.trans" ) << ";\n"
1013 "\n";
1014
1015 if ( redFsm->anyRegActions() ) {
1016 out <<
1017 "\tbegin try\n"
1018 " match " << AT( TA(), "state.trans" ) << " with\n"
1019 "\t| 0 -> raise Goto_again\n"
1020 "\t| _ ->\n"
1021 " state.acts <- " << AT( TA(), "state.trans" ) << ";\n"
1022 " state.nacts <- " << AT( A(), POST_INCR("state.acts") ) << ";\n"
1023 " while " << POST_DECR("state.nacts") << " > 0 do\n"
1024 " begin match " << AT( A(), POST_INCR("state.acts") ) << " with\n";
1025 ACTION_SWITCH();
1026 SWITCH_DEFAULT() <<
1027 " end;\n"
1028 " done\n"
1029 "\twith Goto_again -> () end;\n";
1030 }
1031 out << "\tdo_again ()\n";
1032
1033 // if ( redFsm->anyRegActions() || redFsm->anyActionGotos() ||
1034 // redFsm->anyActionCalls() || redFsm->anyActionRets() )
1035 out << "\tand do_again () =\n";
1036
1037 if ( redFsm->anyToStateActions() ) {
1038 out <<
1039 " state.acts <- " << AT( TSA(), vCS() ) << ";\n"
1040 " state.nacts <- " << AT( A(), POST_INCR("state.acts") ) << ";\n"
1041 " while " << POST_DECR("state.nacts") << " > 0 do\n"
1042 " begin match " << AT( A(), POST_INCR("state.acts") ) << " with\n";
1043 TO_STATE_ACTION_SWITCH();
1044 SWITCH_DEFAULT() <<
1045 " end\n"
1046 " done;\n"
1047 "\n";
1048 }
1049
1050 if ( redFsm->errState != 0 ) {
1051 outLabelUsed = true;
1052 out <<
1053 " match " << vCS() << " with\n"
1054 "\t| " << redFsm->errState->id << " -> do_out ()\n"
1055 "\t| _ ->\n";
1056 }
1057
1058 out << "\t" << P() << " <- " << P() << " + 1;\n";
1059
1060 if ( !noEnd ) {
1061 out <<
1062 " if " << P() << " <> " << PE() << " then\n"
1063 " do_resume ()\n"
1064 "\telse do_test_eof ()\n";
1065 }
1066 else {
1067 out <<
1068 " do_resume ()\n";
1069 }
1070
1071 // if ( testEofUsed )
1072 out << "and do_test_eof () =\n";
1073
1074 if ( redFsm->anyEofTrans() || redFsm->anyEofActions() ) {
1075 out <<
1076 " if " << P() << " = " << vEOF() << " then\n"
1077 " begin try\n";
1078
1079 if ( redFsm->anyEofTrans() ) {
1080 out <<
1081 " if " << AT( ET(), vCS() ) << " > 0 then\n"
1082 " begin\n"
1083 " state.trans <- " << CAST(transType) << "(" << AT( ET(), vCS() ) << " - 1);\n"
1084 " raise Goto_eof_trans;\n"
1085 " end;\n";
1086 }
1087
1088 if ( redFsm->anyEofActions() ) {
1089 out <<
1090 " let __acts = ref " << AT( EA(), vCS() ) << " in\n"
1091 " let __nacts = ref " << AT( A(), "!__acts" ) << " in\n"
1092 " incr __acts;\n"
1093 " while !__nacts > 0 do\n"
1094 " decr __nacts;\n"
1095 " begin match " << AT( A(), POST_INCR("__acts.contents") ) << " with\n";
1096 EOF_ACTION_SWITCH();
1097 SWITCH_DEFAULT() <<
1098 " end;\n"
1099 " done\n";
1100 }
1101
1102 out <<
1103 " with Goto_again -> do_again ()\n"
1104 " | Goto_eof_trans -> do_eof_trans () end\n"
1105 "\n";
1106 }
1107 else
1108 {
1109 out << "\t()\n";
1110 }
1111
1112 if ( outLabelUsed )
1113 out << " and do_out () = ()\n";
1114
1115 out << "\tin do_start ()\n";
1116 out << " end;\n";
1117 }
1118
initVarTypes()1119 void OCamlTabCodeGen::initVarTypes()
1120 {
1121 int klenMax = MAX(MAX(redFsm->maxCondLen, redFsm->maxRangeLen),
1122 redFsm->maxSingleLen);
1123 int keysMax = MAX(MAX(redFsm->maxKeyOffset, klenMax),
1124 redFsm->maxCondOffset);
1125 int transMax = MAX(MAX(redFsm->maxIndex+1, redFsm->maxIndexOffset), keysMax);
1126 transMax = MAX(transMax, klenMax);
1127 transType = ARRAY_TYPE(transMax);
1128 klenType = ARRAY_TYPE(klenMax);
1129 keysType = ARRAY_TYPE(keysMax);
1130 signedKeysType = ARRAY_TYPE(keysMax, true);
1131 }
1132