Split the XML parsing, reduced fsm, and the code generation data structures out
[external/ragel.git] / redfsm / gendata.cpp
1 /*
2  *  Copyright 2005-2006 Adrian Thurston <thurston@cs.queensu.ca>
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 #include "gendata.h"
23 #include <iostream>
24
25 using std::cerr;
26 using std::endl;
27
28 CodeGenData::CodeGenData( ostream &out )
29 :
30         sourceFileName(0),
31         fsmName(0), 
32         out(out),
33         redFsm(0), 
34         allActions(0),
35         allActionTables(0),
36         allConditions(0),
37         allCondSpaces(0),
38         allStates(0),
39         nameIndex(0),
40         startState(0),
41         getKeyExpr(0),
42         accessExpr(0),
43         curStateExpr(0),
44         wantComplete(0),
45         hasLongestMatch(false),
46         hasEnd(true),
47         dataPrefix(true),
48         writeFirstFinal(true),
49         writeErr(true),
50         hasBeenPrepared(false)
51 {}
52
53
54 void CodeGenData::createMachine()
55 {
56         redFsm = new RedFsmAp();
57 }
58
59 void CodeGenData::initActionList( unsigned long length )
60
61         allActions = new Action[length];
62         for ( unsigned long a = 0; a < length; a++ )
63                 actionList.append( allActions+a );
64 }
65
66 void CodeGenData::newAction( int anum, char *name, int line, 
67                 int col, InlineList *inlineList )
68 {
69         allActions[anum].actionId = anum;
70         allActions[anum].name = name;
71         allActions[anum].loc.line = line;
72         allActions[anum].loc.col = col;
73         allActions[anum].inlineList = inlineList;
74 }
75
76 void CodeGenData::initActionTableList( unsigned long length )
77
78         allActionTables = new RedAction[length];
79 }
80
81 void CodeGenData::initStateList( unsigned long length )
82 {
83         allStates = new RedStateAp[length];
84         for ( unsigned long s = 0; s < length; s++ )
85                 redFsm->stateList.append( allStates+s );
86 }
87
88 void CodeGenData::setStartState( unsigned long startState )
89 {
90         this->startState = startState;
91 }
92
93 void CodeGenData::addEntryPoint( char *name, unsigned long entryState )
94 {
95         entryPointIds.append( entryState );
96         entryPointNames.append( name );
97 }
98
99 void CodeGenData::initTransList( int snum, unsigned long length )
100 {
101         /* Could preallocate the out range to save time growing it. For now do
102          * nothing. */
103 }
104
105 void CodeGenData::newTrans( int snum, int tnum, Key lowKey, 
106                 Key highKey, long targ, long action )
107 {
108         /* Get the current state and range. */
109         RedStateAp *curState = allStates + snum;
110         RedTransList &destRange = curState->outRange;
111
112         /* Make the new transitions. */
113         RedStateAp *targState = targ >= 0 ? (allStates + targ) : 
114                         wantComplete ? redFsm->getErrorState() : 0;
115         RedAction *actionTable = action >= 0 ? (allActionTables + action) : 0;
116         RedTransAp *trans = redFsm->allocateTrans( targState, actionTable );
117         RedTransEl transEl( lowKey, highKey, trans );
118
119         if ( wantComplete ) {
120                 /* If the machine is to be complete then we need to fill any gaps with
121                  * the error transitions. */
122                 if ( destRange.length() == 0 ) {
123                         /* Range is currently empty. */
124                         if ( keyOps->minKey < lowKey ) {
125                                 /* The first range doesn't start at the low end. */
126                                 Key fillHighKey = lowKey;
127                                 fillHighKey.decrement();
128
129                                 /* Create the filler with the state's error transition. */
130                                 RedTransEl newTel( keyOps->minKey, fillHighKey, redFsm->getErrorTrans() );
131                                 destRange.append( newTel );
132                         }
133                 }
134                 else {
135                         /* The range list is not empty, get the the last range. */
136                         RedTransEl *last = &destRange[destRange.length()-1];
137                         Key nextKey = last->highKey;
138                         nextKey.increment();
139                         if ( nextKey < lowKey ) {
140                                 /* There is a gap to fill. Make the high key. */
141                                 Key fillHighKey = lowKey;
142                                 fillHighKey.decrement();
143
144                                 /* Create the filler with the state's error transtion. */
145                                 RedTransEl newTel( nextKey, fillHighKey, redFsm->getErrorTrans() );
146                                 destRange.append( newTel );
147                         }
148                 }
149         }
150
151         /* Filler taken care of. Append the range. */
152         destRange.append( RedTransEl( lowKey, highKey, trans ) );
153 }
154
155 void CodeGenData::finishTransList( int snum )
156 {
157         /* Get the current state and range. */
158         RedStateAp *curState = allStates + snum;
159         RedTransList &destRange = curState->outRange;
160
161         /* If building a complete machine we may need filler on the end. */
162         if ( wantComplete ) {
163                 /* Check if there are any ranges already. */
164                 if ( destRange.length() == 0 ) {
165                         /* Fill with the whole alphabet. */
166                         /* Add the range on the lower and upper bound. */
167                         RedTransEl newTel( keyOps->minKey, keyOps->maxKey, redFsm->getErrorTrans() );
168                         destRange.append( newTel );
169                 }
170                 else {
171                         /* Get the last and check for a gap on the end. */
172                         RedTransEl *last = &destRange[destRange.length()-1];
173                         if ( last->highKey < keyOps->maxKey ) {
174                                 /* Make the high key. */
175                                 Key fillLowKey = last->highKey;
176                                 fillLowKey.increment();
177
178                                 /* Create the new range with the error trans and append it. */
179                                 RedTransEl newTel( fillLowKey, keyOps->maxKey, redFsm->getErrorTrans() );
180                                 destRange.append( newTel );
181                         }
182                 }
183         }
184 }
185
186 void CodeGenData::setFinal( int snum )
187 {
188         RedStateAp *curState = allStates + snum;
189         curState->isFinal = true;
190 }
191
192
193 void CodeGenData::setStateActions( int snum, long toStateAction, 
194                         long fromStateAction, long eofAction )
195 {
196         RedStateAp *curState = allStates + snum;
197         if ( toStateAction >= 0 )
198                 curState->toStateAction = allActionTables + toStateAction;
199         if ( fromStateAction >= 0 )
200                 curState->fromStateAction = allActionTables + fromStateAction;
201         if ( eofAction >= 0 )
202                 curState->eofAction = allActionTables + eofAction;
203 }
204
205 void CodeGenData::resolveTargetStates( InlineList *inlineList )
206 {
207         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
208                 switch ( item->type ) {
209                 case InlineItem::Goto: case InlineItem::Call:
210                 case InlineItem::Next: case InlineItem::Entry:
211                         item->targState = allStates + item->targId;
212                         break;
213                 default:
214                         break;
215                 }
216
217                 if ( item->children != 0 )
218                         resolveTargetStates( item->children );
219         }
220 }
221
222 void CodeGenData::closeMachine()
223 {
224         if ( redFsm->forcedErrorState )
225                 redFsm->getErrorState();
226
227         /* We get the start state as an offset, set the pointer now. */
228         redFsm->startState = allStates + startState;
229         for ( EntryIdVect::Iter en = entryPointIds; en.lte(); en++ )
230                 redFsm->entryPoints.insert( allStates + *en );
231
232         for ( ActionList::Iter a = actionList; a.lte(); a++ )
233                 resolveTargetStates( a->inlineList );
234
235         /* Note that even if we want a complete graph we do not give the error
236          * state a default transition. All machines break out of the processing
237          * loop when in the error state. */
238
239         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
240                 for ( StateCondList::Iter sci = st->stateCondList; sci.lte(); sci++ )
241                         st->stateCondVect.append( sci );
242         }
243 }
244
245
246 bool CodeGenData::setAlphType( char *data )
247 {
248         /* FIXME: This should validate the alphabet type selection. */
249         HostType *alphType = hostLang->hostTypes + atoi(data);
250         thisKeyOps.setAlphType( alphType );
251         return true;
252 }
253
254 void CodeGenData::initCondSpaceList( ulong length )
255 {
256         allCondSpaces = new CondSpace[length];
257         for ( ulong c = 0; c < length; c++ )
258                 condSpaceList.append( allCondSpaces + c );
259 }
260
261 void CodeGenData::newCondSpace( int cnum, int condSpaceId, Key baseKey )
262 {
263         CondSpace *cond = allCondSpaces + cnum;
264         cond->condSpaceId = condSpaceId;
265         cond->baseKey = baseKey;
266 }
267
268 void CodeGenData::condSpaceItem( int cnum, long condActionId )
269 {
270         CondSpace *cond = allCondSpaces + cnum;
271         cond->condSet.append( allActions + condActionId );
272 }
273
274 void CodeGenData::initStateCondList( int snum, ulong length )
275 {
276         /* Could preallocate these, as we could with transitions. */
277 }
278
279 void CodeGenData::addStateCond( int snum, Key lowKey, Key highKey, long condNum )
280 {
281         RedStateAp *curState = allStates + snum;
282
283         /* Create the new state condition. */
284         StateCond *stateCond = new StateCond;
285         stateCond->lowKey = lowKey;
286         stateCond->highKey = highKey;
287
288         /* Assign it a cond space. */
289         CondSpace *condSpace = allCondSpaces + condNum;
290         stateCond->condSpace = condSpace;
291
292         curState->stateCondList.append( stateCond );
293 }
294
295
296 CondSpace *CodeGenData::findCondSpace( Key lowKey, Key highKey )
297 {
298         for ( CondSpaceList::Iter cs = condSpaceList; cs.lte(); cs++ ) {
299                 Key csHighKey = cs->baseKey;
300                 csHighKey += keyOps->alphSize() * (1 << cs->condSet.length());
301
302                 if ( lowKey >= cs->baseKey && highKey <= csHighKey )
303                         return cs;
304         }
305         return 0;
306 }
307
308 Condition *CodeGenData::findCondition( Key key )
309 {
310         for ( ConditionList::Iter cond = conditionList; cond.lte(); cond++ ) {
311                 Key upperKey = cond->baseKey + (1 << cond->condSet.length());
312                 if ( cond->baseKey <= key && key <= upperKey )
313                         return cond;
314         }
315         return 0;
316 }
317
318 Key CodeGenData::findMaxKey()
319 {
320         Key maxKey = keyOps->maxKey;
321         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
322                 assert( st->outSingle.length() == 0 );
323                 assert( st->defTrans == 0 );
324
325                 long rangeLen = st->outRange.length();
326                 if ( rangeLen > 0 ) {
327                         Key highKey = st->outRange[rangeLen-1].highKey;
328                         if ( highKey > maxKey )
329                                 maxKey = highKey;
330                 }
331         }
332         return maxKey;
333 }
334
335 void CodeGenData::findFinalActionRefs()
336 {
337         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
338                 /* Rerence count out of single transitions. */
339                 for ( RedTransList::Iter rtel = st->outSingle; rtel.lte(); rtel++ ) {
340                         if ( rtel->value->action != 0 ) {
341                                 rtel->value->action->numTransRefs += 1;
342                                 for ( ActionTable::Iter item = rtel->value->action->key; item.lte(); item++ )
343                                         item->value->numTransRefs += 1;
344                         }
345                 }
346
347                 /* Reference count out of range transitions. */
348                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
349                         if ( rtel->value->action != 0 ) {
350                                 rtel->value->action->numTransRefs += 1;
351                                 for ( ActionTable::Iter item = rtel->value->action->key; item.lte(); item++ )
352                                         item->value->numTransRefs += 1;
353                         }
354                 }
355
356                 /* Reference count default transition. */
357                 if ( st->defTrans != 0 && st->defTrans->action != 0 ) {
358                         st->defTrans->action->numTransRefs += 1;
359                         for ( ActionTable::Iter item = st->defTrans->action->key; item.lte(); item++ )
360                                 item->value->numTransRefs += 1;
361                 }
362
363                 /* Reference count to state actions. */
364                 if ( st->toStateAction != 0 ) {
365                         st->toStateAction->numToStateRefs += 1;
366                         for ( ActionTable::Iter item = st->toStateAction->key; item.lte(); item++ )
367                                 item->value->numToStateRefs += 1;
368                 }
369
370                 /* Reference count from state actions. */
371                 if ( st->fromStateAction != 0 ) {
372                         st->fromStateAction->numFromStateRefs += 1;
373                         for ( ActionTable::Iter item = st->fromStateAction->key; item.lte(); item++ )
374                                 item->value->numFromStateRefs += 1;
375                 }
376
377                 /* Reference count EOF actions. */
378                 if ( st->eofAction != 0 ) {
379                         st->eofAction->numEofRefs += 1;
380                         for ( ActionTable::Iter item = st->eofAction->key; item.lte(); item++ )
381                                 item->value->numEofRefs += 1;
382                 }
383         }
384 }
385
386 void CodeGenData::analyzeAction( Action *act, InlineList *inlineList )
387 {
388         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
389                 /* Only consider actions that are referenced. */
390                 if ( act->numRefs() > 0 ) {
391                         if ( item->type == InlineItem::Goto || item->type == InlineItem::GotoExpr )
392                                 redFsm->bAnyActionGotos = true;
393                         else if ( item->type == InlineItem::Call || item->type == InlineItem::CallExpr )
394                                 redFsm->bAnyActionCalls = true;
395                         else if ( item->type == InlineItem::Ret )
396                                 redFsm->bAnyActionRets = true;
397                 }
398
399                 /* Check for various things in regular actions. */
400                 if ( act->numTransRefs > 0 || act->numToStateRefs > 0 || act->numFromStateRefs > 0 ) {
401                         /* Any returns in regular actions? */
402                         if ( item->type == InlineItem::Ret )
403                                 redFsm->bAnyRegActionRets = true;
404
405                         /* Any next statements in the regular actions? */
406                         if ( item->type == InlineItem::Next || item->type == InlineItem::NextExpr )
407                                 redFsm->bAnyRegNextStmt = true;
408
409                         /* Any by value control in regular actions? */
410                         if ( item->type == InlineItem::CallExpr || item->type == InlineItem::GotoExpr )
411                                 redFsm->bAnyRegActionByValControl = true;
412
413                         /* Any references to the current state in regular actions? */
414                         if ( item->type == InlineItem::Curs )
415                                 redFsm->bAnyRegCurStateRef = true;
416
417                         if ( item->type == InlineItem::Break )
418                                 redFsm->bAnyRegBreak = true;
419
420                         if ( item->type == InlineItem::LmSwitch && item->handlesError )
421                                 redFsm->bAnyLmSwitchError = true;
422                 }
423
424                 if ( item->children != 0 )
425                         analyzeAction( act, item->children );
426         }
427 }
428
429 void CodeGenData::analyzeActionList( RedAction *redAct, InlineList *inlineList )
430 {
431         for ( InlineList::Iter item = *inlineList; item.lte(); item++ ) {
432                 /* Any next statements in the action table? */
433                 if ( item->type == InlineItem::Next || item->type == InlineItem::NextExpr )
434                         redAct->bAnyNextStmt = true;
435
436                 /* Any references to the current state. */
437                 if ( item->type == InlineItem::Curs )
438                         redAct->bAnyCurStateRef = true;
439
440                 if ( item->type == InlineItem::Break )
441                         redAct->bAnyBreakStmt = true;
442
443                 if ( item->children != 0 )
444                         analyzeActionList( redAct, item->children );
445         }
446 }
447
448 /* Assign ids to referenced actions. */
449 void CodeGenData::assignActionIds()
450 {
451         int nextActionId = 0;
452         for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
453                 /* Only ever interested in referenced actions. */
454                 if ( act->numRefs() > 0 )
455                         act->actionId = nextActionId++;
456         }
457 }
458
459 void CodeGenData::setValueLimits()
460 {
461         redFsm->maxSingleLen = 0;
462         redFsm->maxRangeLen = 0;
463         redFsm->maxKeyOffset = 0;
464         redFsm->maxIndexOffset = 0;
465         redFsm->maxActListId = 0;
466         redFsm->maxActionLoc = 0;
467         redFsm->maxActArrItem = 0;
468         redFsm->maxSpan = 0;
469         redFsm->maxCondSpan = 0;
470         redFsm->maxFlatIndexOffset = 0;
471         redFsm->maxCondOffset = 0;
472         redFsm->maxCondLen = 0;
473         redFsm->maxCondSpaceId = 0;
474         redFsm->maxCondIndexOffset = 0;
475
476         /* In both of these cases the 0 index is reserved for no value, so the max
477          * is one more than it would be if they started at 0. */
478         redFsm->maxIndex = redFsm->transSet.length();
479         redFsm->maxCond = condSpaceList.length(); 
480
481         /* The nextStateId - 1 is the last state id assigned. */
482         redFsm->maxState = redFsm->nextStateId - 1;
483
484         for ( CondSpaceList::Iter csi = condSpaceList; csi.lte(); csi++ ) {
485                 if ( csi->condSpaceId > redFsm->maxCondSpaceId )
486                         redFsm->maxCondSpaceId = csi->condSpaceId;
487         }
488
489         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
490                 /* Maximum cond length. */
491                 if ( st->stateCondList.length() > redFsm->maxCondLen )
492                         redFsm->maxCondLen = st->stateCondList.length();
493
494                 /* Maximum single length. */
495                 if ( st->outSingle.length() > redFsm->maxSingleLen )
496                         redFsm->maxSingleLen = st->outSingle.length();
497
498                 /* Maximum range length. */
499                 if ( st->outRange.length() > redFsm->maxRangeLen )
500                         redFsm->maxRangeLen = st->outRange.length();
501
502                 /* The key offset index offset for the state after last is not used, skip it.. */
503                 if ( ! st.last() ) {
504                         redFsm->maxCondOffset += st->stateCondList.length();
505                         redFsm->maxKeyOffset += st->outSingle.length() + st->outRange.length()*2;
506                         redFsm->maxIndexOffset += st->outSingle.length() + st->outRange.length() + 1;
507                 }
508
509                 /* Max cond span. */
510                 if ( st->condList != 0 ) {
511                         unsigned long long span = keyOps->span( st->condLowKey, st->condHighKey );
512                         if ( span > redFsm->maxCondSpan )
513                                 redFsm->maxCondSpan = span;
514                 }
515
516                 /* Max key span. */
517                 if ( st->transList != 0 ) {
518                         unsigned long long span = keyOps->span( st->lowKey, st->highKey );
519                         if ( span > redFsm->maxSpan )
520                                 redFsm->maxSpan = span;
521                 }
522
523                 /* Max cond index offset. */
524                 if ( ! st.last() ) {
525                         if ( st->condList != 0 )
526                                 redFsm->maxCondIndexOffset += keyOps->span( st->condLowKey, st->condHighKey );
527                 }
528
529                 /* Max flat index offset. */
530                 if ( ! st.last() ) {
531                         if ( st->transList != 0 )
532                                 redFsm->maxFlatIndexOffset += keyOps->span( st->lowKey, st->highKey );
533                         redFsm->maxFlatIndexOffset += 1;
534                 }
535         }
536
537         for ( ActionTableMap::Iter at = redFsm->actionMap; at.lte(); at++ ) {
538                 /* Maximum id of action lists. */
539                 if ( at->actListId+1 > redFsm->maxActListId )
540                         redFsm->maxActListId = at->actListId+1;
541
542                 /* Maximum location of items in action array. */
543                 if ( at->location+1 > redFsm->maxActionLoc )
544                         redFsm->maxActionLoc = at->location+1;
545
546                 /* Maximum values going into the action array. */
547                 if ( at->key.length() > redFsm->maxActArrItem )
548                         redFsm->maxActArrItem = at->key.length();
549                 for ( ActionTable::Iter item = at->key; item.lte(); item++ ) {
550                         if ( item->value->actionId > redFsm->maxActArrItem )
551                                 redFsm->maxActArrItem = item->value->actionId;
552                 }
553         }
554 }
555
556
557
558 /* Gather various info on the machine. */
559 void CodeGenData::analyzeMachine()
560 {
561         /* Find the true count of action references.  */
562         findFinalActionRefs();
563
564         /* Check if there are any calls in action code. */
565         for ( ActionList::Iter act = actionList; act.lte(); act++ ) {
566                 /* Record the occurrence of various kinds of actions. */
567                 if ( act->numToStateRefs > 0 )
568                         redFsm->bAnyToStateActions = true;
569                 if ( act->numFromStateRefs > 0 )
570                         redFsm->bAnyFromStateActions = true;
571                 if ( act->numEofRefs > 0 )
572                         redFsm->bAnyEofActions = true;
573                 if ( act->numTransRefs > 0 )
574                         redFsm->bAnyRegActions = true;
575
576                 /* Recurse through the action's parse tree looking for various things. */
577                 analyzeAction( act, act->inlineList );
578         }
579
580         /* Analyze reduced action lists. */
581         for ( ActionTableMap::Iter redAct = redFsm->actionMap; redAct.lte(); redAct++ ) {
582                 for ( ActionTable::Iter act = redAct->key; act.lte(); act++ )
583                         analyzeActionList( redAct, act->value->inlineList );
584         }
585
586         /* Find states that have transitions with actions that have next
587          * statements. */
588         for ( RedStateList::Iter st = redFsm->stateList; st.lte(); st++ ) {
589                 /* Check any actions out of outSinge. */
590                 for ( RedTransList::Iter rtel = st->outSingle; rtel.lte(); rtel++ ) {
591                         if ( rtel->value->action != 0 && rtel->value->action->anyCurStateRef() )
592                                 st->bAnyRegCurStateRef = true;
593                 }
594
595                 /* Check any actions out of outRange. */
596                 for ( RedTransList::Iter rtel = st->outRange; rtel.lte(); rtel++ ) {
597                         if ( rtel->value->action != 0 && rtel->value->action->anyCurStateRef() )
598                                 st->bAnyRegCurStateRef = true;
599                 }
600
601                 /* Check any action out of default. */
602                 if ( st->defTrans != 0 && st->defTrans->action != 0 && 
603                                 st->defTrans->action->anyCurStateRef() )
604                         st->bAnyRegCurStateRef = true;
605                 
606                 if ( st->stateCondList.length() > 0 )
607                         redFsm->bAnyConditions = true;
608         }
609
610         /* Assign ids to actions that are referenced. */
611         assignActionIds();
612
613         /* Set the maximums of various values used for deciding types. */
614         setValueLimits();
615 }
616
617
618
619 void lineDirective( ostream &out, char *fileName, int line )
620 {
621         if ( hostLangType != JavaCode ) {
622                 /* Write the preprocessor line info for to the input file. */
623                 out << "#line " << line  << " \"";
624                 for ( char *pc = fileName; *pc != 0; pc++ ) {
625                         if ( *pc == '\\' )
626                                 out << "\\\\";
627                         else
628                                 out << *pc;
629                 }
630                 out << "\"\n";
631         }
632 }
633