Added an override for the eof variable.
[external/ragel.git] / rlgen-cd / fsmcodegen.cpp
1 /*
2  *  Copyright 2001-2006 Adrian Thurston <thurston@cs.queensu.ca>
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 "rlgen-cd.h"
25 #include "fsmcodegen.h"
26 #include "redfsm.h"
27 #include "gendata.h"
28 #include <sstream>
29 #include <string>
30 #include <assert.h>
31
32
33 using std::ostream;
34 using std::ostringstream;
35 using std::string;
36 using std::cerr;
37 using std::endl;
38
39 void lineDirective( ostream &out, char *fileName, int line )
40 {
41         if ( noLineDirectives )
42                 out << "/* ";
43
44         /* Write the preprocessor line info for to the input file. */
45         out << "#line " << line  << " \"";
46         for ( char *pc = fileName; *pc != 0; pc++ ) {
47                 if ( *pc == '\\' )
48                         out << "\\\\";
49                 else
50                         out << *pc;
51         }
52         out << '"';
53
54         if ( noLineDirectives )
55                 out << " */";
56
57         out << '\n';
58 }
59
60 void genLineDirective( ostream &out )
61 {
62         std::streambuf *sbuf = out.rdbuf();
63         output_filter *filter = static_cast<output_filter*>(sbuf);
64         lineDirective( out, filter->fileName, filter->line + 1 );
65 }
66
67
68 /* Init code gen with in parameters. */
69 FsmCodeGen::FsmCodeGen( ostream &out )
70 :
71         CodeGenData(out)
72 {
73 }
74
75 unsigned int FsmCodeGen::arrayTypeSize( unsigned long maxVal )
76 {
77         long long maxValLL = (long long) maxVal;
78         HostType *arrayType = keyOps->typeSubsumes( maxValLL );
79         assert( arrayType != 0 );
80         return arrayType->size;
81 }
82
83 string FsmCodeGen::ARRAY_TYPE( unsigned long maxVal )
84 {
85         long long maxValLL = (long long) maxVal;
86         HostType *arrayType = keyOps->typeSubsumes( maxValLL );
87         assert( arrayType != 0 );
88
89         string ret = arrayType->data1;
90         if ( arrayType->data2 != 0 ) {
91                 ret += " ";
92                 ret += arrayType->data2;
93         }
94         return ret;
95 }
96
97
98 /* Write out the fsm name. */
99 string FsmCodeGen::FSM_NAME()
100 {
101         return fsmName;
102 }
103
104 /* Emit the offset of the start state as a decimal integer. */
105 string FsmCodeGen::START_STATE_ID()
106 {
107         ostringstream ret;
108         ret << redFsm->startState->id;
109         return ret.str();
110 };
111
112 /* Write out the array of actions. */
113 std::ostream &FsmCodeGen::ACTIONS_ARRAY()
114 {
115         out << "\t0, ";
116         int totalActions = 1;
117         for ( ActionTableMap::Iter act = redFsm->actionMap; act.lte(); act++ ) {
118                 /* Write out the length, which will never be the last character. */
119                 out << act->key.length() << ", ";
120                 /* Put in a line break every 8 */
121                 if ( totalActions++ % 8 == 7 )
122                         out << "\n\t";
123
124                 for ( ActionTable::Iter item = act->key; item.lte(); item++ ) {
125                         out << item->value->actionId;
126                         if ( ! (act.last() && item.last()) )
127                                 out << ", ";
128
129                         /* Put in a line break every 8 */
130                         if ( totalActions++ % 8 == 7 )
131                                 out << "\n\t";
132                 }
133         }
134         out << "\n";
135         return out;
136 }
137
138
139 string FsmCodeGen::ACCESS()
140 {
141         ostringstream ret;
142         if ( accessExpr != 0 )
143                 INLINE_LIST( ret, accessExpr, 0, false );
144         return ret.str();
145 }
146
147
148 string FsmCodeGen::P()
149
150         ostringstream ret;
151         if ( pExpr == 0 )
152                 ret << "p";
153         else {
154                 ret << "(";
155                 INLINE_LIST( ret, pExpr, 0, false );
156                 ret << ")";
157         }
158         return ret.str();
159 }
160
161 string FsmCodeGen::PE()
162 {
163         ostringstream ret;
164         if ( peExpr == 0 )
165                 ret << "pe";
166         else {
167                 ret << "(";
168                 INLINE_LIST( ret, peExpr, 0, false );
169                 ret << ")";
170         }
171         return ret.str();
172 }
173
174 string FsmCodeGen::EOFV()
175 {
176         ostringstream ret;
177         if ( eofExpr == 0 )
178                 ret << "eof";
179         else {
180                 ret << "(";
181                 INLINE_LIST( ret, eofExpr, 0, false );
182                 ret << ")";
183         }
184         return ret.str();
185 }
186
187 string FsmCodeGen::CS()
188 {
189         ostringstream ret;
190         if ( csExpr == 0 )
191                 ret << ACCESS() << "cs";
192         else {
193                 /* Emit the user supplied method of retrieving the key. */
194                 ret << "(";
195                 INLINE_LIST( ret, csExpr, 0, false );
196                 ret << ")";
197         }
198         return ret.str();
199 }
200
201 string FsmCodeGen::TOP()
202 {
203         ostringstream ret;
204         if ( topExpr == 0 )
205                 ret << ACCESS() + "top";
206         else {
207                 ret << "(";
208                 INLINE_LIST( ret, topExpr, 0, false );
209                 ret << ")";
210         }
211         return ret.str();
212 }
213
214 string FsmCodeGen::STACK()
215 {
216         ostringstream ret;
217         if ( stackExpr == 0 )
218                 ret << ACCESS() + "stack";
219         else {
220                 ret << "(";
221                 INLINE_LIST( ret, stackExpr, 0, false );
222                 ret << ")";
223         }
224         return ret.str();
225 }
226
227 string FsmCodeGen::ACT()
228 {
229         ostringstream ret;
230         if ( actExpr == 0 )
231                 ret << ACCESS() + "act";
232         else {
233                 ret << "(";
234                 INLINE_LIST( ret, actExpr, 0, false );
235                 ret << ")";
236         }
237         return ret.str();
238 }
239
240 string FsmCodeGen::TOKSTART()
241 {
242         ostringstream ret;
243         if ( tokstartExpr == 0 )
244                 ret << ACCESS() + "tokstart";
245         else {
246                 ret << "(";
247                 INLINE_LIST( ret, tokstartExpr, 0, false );
248                 ret << ")";
249         }
250         return ret.str();
251 }
252
253 string FsmCodeGen::TOKEND()
254 {
255         ostringstream ret;
256         if ( tokendExpr == 0 )
257                 ret << ACCESS() + "tokend";
258         else {
259                 ret << "(";
260                 INLINE_LIST( ret, tokendExpr, 0, false );
261                 ret << ")";
262         }
263         return ret.str();
264 }
265
266 string FsmCodeGen::GET_WIDE_KEY()
267 {
268         if ( redFsm->anyConditions() ) 
269                 return "_widec";
270         else
271                 return GET_KEY();
272 }
273
274 string FsmCodeGen::GET_WIDE_KEY( RedStateAp *state )
275 {
276         if ( state->stateCondList.length() > 0 )
277                 return "_widec";
278         else
279                 return GET_KEY();
280 }
281
282 string FsmCodeGen::GET_KEY()
283 {
284         ostringstream ret;
285         if ( getKeyExpr != 0 ) { 
286                 /* Emit the user supplied method of retrieving the key. */
287                 ret << "(";
288                 INLINE_LIST( ret, getKeyExpr, 0, false );
289                 ret << ")";
290         }
291         else {
292                 /* Expression for retrieving the key, use simple dereference. */
293                 ret << "(*" << P() << ")";
294         }
295         return ret.str();
296 }
297
298 /* Write out level number of tabs. Makes the nested binary search nice
299  * looking. */
300 string FsmCodeGen::TABS( int level )
301 {
302         string result;
303         while ( level-- > 0 )
304                 result += "\t";
305         return result;
306 }
307
308 /* Write out a key from the fsm code gen. Depends on wether or not the key is
309  * signed. */
310 string FsmCodeGen::KEY( Key key )
311 {
312         ostringstream ret;
313         if ( keyOps->isSigned || !hostLang->explicitUnsigned )
314                 ret << key.getVal();
315         else
316                 ret << (unsigned long) key.getVal() << 'u';
317         return ret.str();
318 }
319
320 void FsmCodeGen::EXEC( ostream &ret, InlineItem *item, int targState, int inFinish )
321 {
322         /* The parser gives fexec two children. The double brackets are for D
323          * code. If the inline list is a single word it will get interpreted as a
324          * C-style cast by the D compiler. */
325         ret << "{" << P() << " = ((";
326         INLINE_LIST( ret, item->children, targState, inFinish );
327         ret << "))-1;}";
328 }
329
330 void FsmCodeGen::LM_SWITCH( ostream &ret, InlineItem *item, 
331                 int targState, int inFinish )
332 {
333         ret << 
334                 "       switch( " << ACT() << " ) {\n";
335
336         for ( InlineList::Iter lma = *item->children; lma.lte(); lma++ ) {
337                 /* Write the case label, the action and the case break. */
338                 ret << "        case " << lma->lmId << ":\n";
339
340                 /* Write the block and close it off. */
341                 ret << "        {";
342                 INLINE_LIST( ret, lma->children, targState, inFinish );
343                 ret << "}\n";
344
345                 ret << "        break;\n";
346         }
347         /* Default required for D code. */
348         ret << 
349                 "       default: break;\n"
350                 "       }\n"
351                 "\t";
352 }
353
354 void FsmCodeGen::SET_ACT( ostream &ret, InlineItem *item )
355 {
356         ret << ACT() << " = " << item->lmId << ";";
357 }
358
359 void FsmCodeGen::SET_TOKEND( ostream &ret, InlineItem *item )
360 {
361         /* The tokend action sets tokend. */
362         ret << TOKEND() << " = " << P();
363         if ( item->offset != 0 ) 
364                 out << "+" << item->offset;
365         out << ";";
366 }
367
368 void FsmCodeGen::GET_TOKEND( ostream &ret, InlineItem *item )
369 {
370         ret << TOKEND();
371 }
372
373 void FsmCodeGen::INIT_TOKSTART( ostream &ret, InlineItem *item )
374 {
375         ret << TOKSTART() << " = " << NULL_ITEM() << ";";
376 }
377
378 void FsmCodeGen::INIT_ACT( ostream &ret, InlineItem *item )
379 {
380         ret << ACT() << " = 0;";
381 }
382
383 void FsmCodeGen::SET_TOKSTART( ostream &ret, InlineItem *item )
384 {
385         ret << TOKSTART() << " = " << P() << ";";
386 }
387
388 void FsmCodeGen::SUB_ACTION( ostream &ret, InlineItem *item, 
389                 int targState, bool inFinish )
390 {
391         if ( item->children->length() > 0 ) {
392                 /* Write the block and close it off. */
393                 ret << "{";
394                 INLINE_LIST( ret, item->children, targState, inFinish );
395                 ret << "}";
396         }
397 }
398
399
400 /* Write out an inline tree structure. Walks the list and possibly calls out
401  * to virtual functions than handle language specific items in the tree. */
402 void FsmCodeGen::INLINE_LIST( ostream &ret, InlineList *inlineList, 
403                 int targState, bool inFinish )
404 {
405         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
406                 switch ( item->type ) {
407                 case InlineItem::Text:
408                         ret << item->data;
409                         break;
410                 case InlineItem::Goto:
411                         GOTO( ret, item->targState->id, inFinish );
412                         break;
413                 case InlineItem::Call:
414                         CALL( ret, item->targState->id, targState, inFinish );
415                         break;
416                 case InlineItem::Next:
417                         NEXT( ret, item->targState->id, inFinish );
418                         break;
419                 case InlineItem::Ret:
420                         RET( ret, inFinish );
421                         break;
422                 case InlineItem::PChar:
423                         ret << P();
424                         break;
425                 case InlineItem::Char:
426                         ret << GET_KEY();
427                         break;
428                 case InlineItem::Hold:
429                         ret << P() << "--;";
430                         break;
431                 case InlineItem::Exec:
432                         EXEC( ret, item, targState, inFinish );
433                         break;
434                 case InlineItem::Curs:
435                         CURS( ret, inFinish );
436                         break;
437                 case InlineItem::Targs:
438                         TARGS( ret, inFinish, targState );
439                         break;
440                 case InlineItem::Entry:
441                         ret << item->targState->id;
442                         break;
443                 case InlineItem::GotoExpr:
444                         GOTO_EXPR( ret, item, inFinish );
445                         break;
446                 case InlineItem::CallExpr:
447                         CALL_EXPR( ret, item, targState, inFinish );
448                         break;
449                 case InlineItem::NextExpr:
450                         NEXT_EXPR( ret, item, inFinish );
451                         break;
452                 case InlineItem::LmSwitch:
453                         LM_SWITCH( ret, item, targState, inFinish );
454                         break;
455                 case InlineItem::LmSetActId:
456                         SET_ACT( ret, item );
457                         break;
458                 case InlineItem::LmSetTokEnd:
459                         SET_TOKEND( ret, item );
460                         break;
461                 case InlineItem::LmGetTokEnd:
462                         GET_TOKEND( ret, item );
463                         break;
464                 case InlineItem::LmInitTokStart:
465                         INIT_TOKSTART( ret, item );
466                         break;
467                 case InlineItem::LmInitAct:
468                         INIT_ACT( ret, item );
469                         break;
470                 case InlineItem::LmSetTokStart:
471                         SET_TOKSTART( ret, item );
472                         break;
473                 case InlineItem::SubAction:
474                         SUB_ACTION( ret, item, targState, inFinish );
475                         break;
476                 case InlineItem::Break:
477                         BREAK( ret, targState );
478                         break;
479                 }
480         }
481 }
482 /* Write out paths in line directives. Escapes any special characters. */
483 string FsmCodeGen::LDIR_PATH( char *path )
484 {
485         ostringstream ret;
486         for ( char *pc = path; *pc != 0; pc++ ) {
487                 if ( *pc == '\\' )
488                         ret << "\\\\";
489                 else
490                         ret << *pc;
491         }
492         return ret.str();
493 }
494
495 void FsmCodeGen::ACTION( ostream &ret, Action *action, int targState, bool inFinish )
496 {
497         /* Write the preprocessor line info for going into the source file. */
498         lineDirective( ret, sourceFileName, action->loc.line );
499
500         /* Write the block and close it off. */
501         ret << "\t{";
502         INLINE_LIST( ret, action->inlineList, targState, inFinish );
503         ret << "}\n";
504 }
505
506 void FsmCodeGen::CONDITION( ostream &ret, Action *condition )
507 {
508         ret << "\n";
509         lineDirective( ret, sourceFileName, condition->loc.line );
510         INLINE_LIST( ret, condition->inlineList, 0, false );
511 }
512
513 string FsmCodeGen::ERROR_STATE()
514 {
515         ostringstream ret;
516         if ( redFsm->errState != 0 )
517                 ret << redFsm->errState->id;
518         else
519                 ret << "-1";
520         return ret.str();
521 }
522
523 string FsmCodeGen::FIRST_FINAL_STATE()
524 {
525         ostringstream ret;
526         if ( redFsm->firstFinState != 0 )
527                 ret << redFsm->firstFinState->id;
528         else
529                 ret << redFsm->nextStateId;
530         return ret.str();
531 }
532
533 void FsmCodeGen::writeInit()
534 {
535         out << "        {\n";
536
537         if ( writeCS )
538                 out << "\t" << CS() << " = " << START() << ";\n";
539         
540         /* If there are any calls, then the stack top needs initialization. */
541         if ( redFsm->anyActionCalls() || redFsm->anyActionRets() )
542                 out << "\t" << TOP() << " = 0;\n";
543
544         if ( hasLongestMatch ) {
545                 out << 
546                         "       " << TOKSTART() << " = " << NULL_ITEM() << ";\n"
547                         "       " << TOKEND() << " = " << NULL_ITEM() << ";\n"
548                         "       " << ACT() << " = 0;\n";
549         }
550         out << "        }\n";
551 }
552
553 string FsmCodeGen::DATA_PREFIX()
554 {
555         if ( dataPrefix )
556                 return FSM_NAME() + "_";
557         return "";
558 }
559
560 /* Emit the alphabet data type. */
561 string FsmCodeGen::ALPH_TYPE()
562 {
563         string ret = keyOps->alphType->data1;
564         if ( keyOps->alphType->data2 != 0 ) {
565                 ret += " ";
566                 ret += + keyOps->alphType->data2;
567         }
568         return ret;
569 }
570
571 /* Emit the alphabet data type. */
572 string FsmCodeGen::WIDE_ALPH_TYPE()
573 {
574         string ret;
575         if ( redFsm->maxKey <= keyOps->maxKey )
576                 ret = ALPH_TYPE();
577         else {
578                 long long maxKeyVal = redFsm->maxKey.getLongLong();
579                 HostType *wideType = keyOps->typeSubsumes( keyOps->isSigned, maxKeyVal );
580                 assert( wideType != 0 );
581
582                 ret = wideType->data1;
583                 if ( wideType->data2 != 0 ) {
584                         ret += " ";
585                         ret += wideType->data2;
586                 }
587         }
588         return ret;
589 }
590
591 void FsmCodeGen::STATE_IDS()
592 {
593         if ( redFsm->startState != 0 )
594                 STATIC_VAR( "int", START() ) << " = " << START_STATE_ID() << ";\n";
595
596         if ( writeFirstFinal )
597                 STATIC_VAR( "int" , FIRST_FINAL() ) << " = " << FIRST_FINAL_STATE() << ";\n";
598
599         if ( writeErr )
600                 STATIC_VAR( "int", ERROR() ) << " = " << ERROR_STATE() << ";\n";
601
602         out << "\n";
603
604         if ( entryPointNames.length() > 0 ) {
605                 for ( EntryNameVect::Iter en = entryPointNames; en.lte(); en++ ) {
606                         STATIC_VAR( "int", DATA_PREFIX() + "en_" + *en ) << 
607                                         " = " << entryPointIds[en.pos()] << ";\n";
608                 }
609                 out << "\n";
610         }
611 }
612
613
614 /*
615  * Language specific, but style independent code generators functions.
616  */
617
618 string CCodeGen::PTR_CONST()
619 {
620         return "const ";
621 }
622
623 std::ostream &CCodeGen::OPEN_ARRAY( string type, string name )
624 {
625         out << "static const " << type << " " << name << "[] = {\n";
626         return out;
627 }
628
629 std::ostream &CCodeGen::CLOSE_ARRAY()
630 {
631         return out << "};\n";
632 }
633
634 std::ostream &CCodeGen::STATIC_VAR( string type, string name )
635 {
636         out << "static const " << type << " " << name;
637         return out;
638 }
639
640 string CCodeGen::UINT( )
641 {
642         return "unsigned int";
643 }
644
645 string CCodeGen::ARR_OFF( string ptr, string offset )
646 {
647         return ptr + " + " + offset;
648 }
649
650 string CCodeGen::CAST( string type )
651 {
652         return "(" + type + ")";
653 }
654
655 string CCodeGen::NULL_ITEM()
656 {
657         return "0";
658 }
659
660 string CCodeGen::POINTER()
661 {
662         return " *";
663 }
664
665 std::ostream &CCodeGen::SWITCH_DEFAULT()
666 {
667         return out;
668 }
669
670 string CCodeGen::CTRL_FLOW()
671 {
672         return "";
673 }
674
675 void CCodeGen::writeExports()
676 {
677         if ( exportList.length() > 0 ) {
678                 for ( ExportList::Iter ex = exportList; ex.lte(); ex++ ) {
679                         out << "#define " << DATA_PREFIX() << "ex_" << ex->name << " " << 
680                                         KEY(ex->key) << "\n";
681                 }
682                 out << "\n";
683         }
684 }
685
686 /*
687  * D Specific
688  */
689
690 string DCodeGen::NULL_ITEM()
691 {
692         return "null";
693 }
694
695 string DCodeGen::POINTER()
696 {
697         // multiple items seperated by commas can also be pointer types.
698         return "* ";
699 }
700
701 string DCodeGen::PTR_CONST()
702 {
703         return "";
704 }
705
706 std::ostream &DCodeGen::OPEN_ARRAY( string type, string name )
707 {
708         out << "static const " << type << "[] " << name << " = [\n";
709         return out;
710 }
711
712 std::ostream &DCodeGen::CLOSE_ARRAY()
713 {
714         return out << "];\n";
715 }
716
717 std::ostream &DCodeGen::STATIC_VAR( string type, string name )
718 {
719         out << "static const " << type << " " << name;
720         return out;
721 }
722
723 string DCodeGen::ARR_OFF( string ptr, string offset )
724 {
725         return "&" + ptr + "[" + offset + "]";
726 }
727
728 string DCodeGen::CAST( string type )
729 {
730         return "cast(" + type + ")";
731 }
732
733 string DCodeGen::UINT( )
734 {
735         return "uint";
736 }
737
738 std::ostream &DCodeGen::SWITCH_DEFAULT()
739 {
740         out << "                default: break;\n";
741         return out;
742 }
743
744 string DCodeGen::CTRL_FLOW()
745 {
746         return "if (true) ";
747 }
748
749 void DCodeGen::writeExports()
750 {
751         if ( exportList.length() > 0 ) {
752                 for ( ExportList::Iter ex = exportList; ex.lte(); ex++ ) {
753                         out << "static const " << ALPH_TYPE() << " " << DATA_PREFIX() << 
754                                         "ex_" << ex->name << " = " << KEY(ex->key) << ";\n";
755                 }
756                 out << "\n";
757         }
758 }
759
760 /*
761  * End D-specific code.
762  */
763
764 void FsmCodeGen::finishRagelDef()
765 {
766         if ( codeStyle == GenGoto || codeStyle == GenFGoto || 
767                         codeStyle == GenIpGoto || codeStyle == GenSplit )
768         {
769                 /* For directly executable machines there is no required state
770                  * ordering. Choose a depth-first ordering to increase the
771                  * potential for fall-throughs. */
772                 redFsm->depthFirstOrdering();
773         }
774         else {
775                 /* The frontend will do this for us, but it may be a good idea to
776                  * force it if the intermediate file is edited. */
777                 redFsm->sortByStateId();
778         }
779
780         /* Choose default transitions and the single transition. */
781         redFsm->chooseDefaultSpan();
782                 
783         /* Maybe do flat expand, otherwise choose single. */
784         if ( codeStyle == GenFlat || codeStyle == GenFFlat )
785                 redFsm->makeFlat();
786         else
787                 redFsm->chooseSingle();
788
789         /* If any errors have occured in the input file then don't write anything. */
790         if ( gblErrorCount > 0 )
791                 return;
792         
793         if ( codeStyle == GenSplit )
794                 redFsm->partitionFsm( numSplitPartitions );
795
796         if ( codeStyle == GenIpGoto || codeStyle == GenSplit )
797                 redFsm->setInTrans();
798
799         /* Anlayze Machine will find the final action reference counts, among
800          * other things. We will use these in reporting the usage
801          * of fsm directives in action code. */
802         analyzeMachine();
803
804         /* Determine if we should use indicies. */
805         calcIndexSize();
806 }
807
808 ostream &FsmCodeGen::source_warning( const InputLoc &loc )
809 {
810         cerr << sourceFileName << ":" << loc.line << ":" << loc.col << ": warning: ";
811         return cerr;
812 }
813
814 ostream &FsmCodeGen::source_error( const InputLoc &loc )
815 {
816         gblErrorCount += 1;
817         assert( sourceFileName != 0 );
818         cerr << sourceFileName << ":" << loc.line << ":" << loc.col << ": ";
819         return cerr;
820 }
821