2 * Copyright 2005-2006 Adrian Thurston <thurston@cs.queensu.ca>
5 /* This file is part of Ragel.
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.
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.
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
28 CodeGenData::CodeGenData( ostream &out )
45 hasLongestMatch(false),
48 writeFirstFinal(true),
50 hasBeenPrepared(false)
54 void CodeGenData::createMachine()
56 redFsm = new RedFsmAp();
59 void CodeGenData::initActionList( unsigned long length )
61 allActions = new Action[length];
62 for ( unsigned long a = 0; a < length; a++ )
63 actionList.append( allActions+a );
66 void CodeGenData::newAction( int anum, char *name, int line,
67 int col, InlineList *inlineList )
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;
76 void CodeGenData::initActionTableList( unsigned long length )
78 allActionTables = new RedAction[length];
81 void CodeGenData::initStateList( unsigned long length )
83 allStates = new RedStateAp[length];
84 for ( unsigned long s = 0; s < length; s++ )
85 redFsm->stateList.append( allStates+s );
88 void CodeGenData::setStartState( unsigned long startState )
90 this->startState = startState;
93 void CodeGenData::addEntryPoint( char *name, unsigned long entryState )
95 entryPointIds.append( entryState );
96 entryPointNames.append( name );
99 void CodeGenData::initTransList( int snum, unsigned long length )
101 /* Could preallocate the out range to save time growing it. For now do
105 void CodeGenData::newTrans( int snum, int tnum, Key lowKey,
106 Key highKey, long targ, long action )
108 /* Get the current state and range. */
109 RedStateAp *curState = allStates + snum;
110 RedTransList &destRange = curState->outRange;
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 );
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();
129 /* Create the filler with the state's error transition. */
130 RedTransEl newTel( keyOps->minKey, fillHighKey, redFsm->getErrorTrans() );
131 destRange.append( newTel );
135 /* The range list is not empty, get the the last range. */
136 RedTransEl *last = &destRange[destRange.length()-1];
137 Key nextKey = last->highKey;
139 if ( nextKey < lowKey ) {
140 /* There is a gap to fill. Make the high key. */
141 Key fillHighKey = lowKey;
142 fillHighKey.decrement();
144 /* Create the filler with the state's error transtion. */
145 RedTransEl newTel( nextKey, fillHighKey, redFsm->getErrorTrans() );
146 destRange.append( newTel );
151 /* Filler taken care of. Append the range. */
152 destRange.append( RedTransEl( lowKey, highKey, trans ) );
155 void CodeGenData::finishTransList( int snum )
157 /* Get the current state and range. */
158 RedStateAp *curState = allStates + snum;
159 RedTransList &destRange = curState->outRange;
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 );
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();
178 /* Create the new range with the error trans and append it. */
179 RedTransEl newTel( fillLowKey, keyOps->maxKey, redFsm->getErrorTrans() );
180 destRange.append( newTel );
186 void CodeGenData::setFinal( int snum )
188 RedStateAp *curState = allStates + snum;
189 curState->isFinal = true;
193 void CodeGenData::setStateActions( int snum, long toStateAction,
194 long fromStateAction, long eofAction )
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;
205 void CodeGenData::resolveTargetStates( InlineList *inlineList )
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;
217 if ( item->children != 0 )
218 resolveTargetStates( item->children );
222 void CodeGenData::closeMachine()
224 if ( redFsm->forcedErrorState )
225 redFsm->getErrorState();
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 );
232 for ( ActionList::Iter a = actionList; a.lte(); a++ )
233 resolveTargetStates( a->inlineList );
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. */
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 );
246 bool CodeGenData::setAlphType( char *data )
248 /* FIXME: This should validate the alphabet type selection. */
249 HostType *alphType = hostLang->hostTypes + atoi(data);
250 thisKeyOps.setAlphType( alphType );
254 void CodeGenData::initCondSpaceList( ulong length )
256 allCondSpaces = new CondSpace[length];
257 for ( ulong c = 0; c < length; c++ )
258 condSpaceList.append( allCondSpaces + c );
261 void CodeGenData::newCondSpace( int cnum, int condSpaceId, Key baseKey )
263 CondSpace *cond = allCondSpaces + cnum;
264 cond->condSpaceId = condSpaceId;
265 cond->baseKey = baseKey;
268 void CodeGenData::condSpaceItem( int cnum, long condActionId )
270 CondSpace *cond = allCondSpaces + cnum;
271 cond->condSet.append( allActions + condActionId );
274 void CodeGenData::initStateCondList( int snum, ulong length )
276 /* Could preallocate these, as we could with transitions. */
279 void CodeGenData::addStateCond( int snum, Key lowKey, Key highKey, long condNum )
281 RedStateAp *curState = allStates + snum;
283 /* Create the new state condition. */
284 StateCond *stateCond = new StateCond;
285 stateCond->lowKey = lowKey;
286 stateCond->highKey = highKey;
288 /* Assign it a cond space. */
289 CondSpace *condSpace = allCondSpaces + condNum;
290 stateCond->condSpace = condSpace;
292 curState->stateCondList.append( stateCond );
296 CondSpace *CodeGenData::findCondSpace( Key lowKey, Key highKey )
298 for ( CondSpaceList::Iter cs = condSpaceList; cs.lte(); cs++ ) {
299 Key csHighKey = cs->baseKey;
300 csHighKey += keyOps->alphSize() * (1 << cs->condSet.length());
302 if ( lowKey >= cs->baseKey && highKey <= csHighKey )
308 Condition *CodeGenData::findCondition( Key key )
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 )
318 Key CodeGenData::findMaxKey()
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 );
325 long rangeLen = st->outRange.length();
326 if ( rangeLen > 0 ) {
327 Key highKey = st->outRange[rangeLen-1].highKey;
328 if ( highKey > maxKey )
335 void CodeGenData::findFinalActionRefs()
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;
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;
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;
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;
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;
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;
386 void CodeGenData::analyzeAction( Action *act, InlineList *inlineList )
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;
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;
405 /* Any next statements in the regular actions? */
406 if ( item->type == InlineItem::Next || item->type == InlineItem::NextExpr )
407 redFsm->bAnyRegNextStmt = true;
409 /* Any by value control in regular actions? */
410 if ( item->type == InlineItem::CallExpr || item->type == InlineItem::GotoExpr )
411 redFsm->bAnyRegActionByValControl = true;
413 /* Any references to the current state in regular actions? */
414 if ( item->type == InlineItem::Curs )
415 redFsm->bAnyRegCurStateRef = true;
417 if ( item->type == InlineItem::Break )
418 redFsm->bAnyRegBreak = true;
420 if ( item->type == InlineItem::LmSwitch && item->handlesError )
421 redFsm->bAnyLmSwitchError = true;
424 if ( item->children != 0 )
425 analyzeAction( act, item->children );
429 void CodeGenData::analyzeActionList( RedAction *redAct, InlineList *inlineList )
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;
436 /* Any references to the current state. */
437 if ( item->type == InlineItem::Curs )
438 redAct->bAnyCurStateRef = true;
440 if ( item->type == InlineItem::Break )
441 redAct->bAnyBreakStmt = true;
443 if ( item->children != 0 )
444 analyzeActionList( redAct, item->children );
448 /* Assign ids to referenced actions. */
449 void CodeGenData::assignActionIds()
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++;
459 void CodeGenData::setValueLimits()
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;
469 redFsm->maxCondSpan = 0;
470 redFsm->maxFlatIndexOffset = 0;
471 redFsm->maxCondOffset = 0;
472 redFsm->maxCondLen = 0;
473 redFsm->maxCondSpaceId = 0;
474 redFsm->maxCondIndexOffset = 0;
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();
481 /* The nextStateId - 1 is the last state id assigned. */
482 redFsm->maxState = redFsm->nextStateId - 1;
484 for ( CondSpaceList::Iter csi = condSpaceList; csi.lte(); csi++ ) {
485 if ( csi->condSpaceId > redFsm->maxCondSpaceId )
486 redFsm->maxCondSpaceId = csi->condSpaceId;
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();
494 /* Maximum single length. */
495 if ( st->outSingle.length() > redFsm->maxSingleLen )
496 redFsm->maxSingleLen = st->outSingle.length();
498 /* Maximum range length. */
499 if ( st->outRange.length() > redFsm->maxRangeLen )
500 redFsm->maxRangeLen = st->outRange.length();
502 /* The key offset index offset for the state after last is not used, skip it.. */
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;
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;
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;
523 /* Max cond index offset. */
525 if ( st->condList != 0 )
526 redFsm->maxCondIndexOffset += keyOps->span( st->condLowKey, st->condHighKey );
529 /* Max flat index offset. */
531 if ( st->transList != 0 )
532 redFsm->maxFlatIndexOffset += keyOps->span( st->lowKey, st->highKey );
533 redFsm->maxFlatIndexOffset += 1;
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;
542 /* Maximum location of items in action array. */
543 if ( at->location+1 > redFsm->maxActionLoc )
544 redFsm->maxActionLoc = at->location+1;
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;
558 /* Gather various info on the machine. */
559 void CodeGenData::analyzeMachine()
561 /* Find the true count of action references. */
562 findFinalActionRefs();
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;
576 /* Recurse through the action's parse tree looking for various things. */
577 analyzeAction( act, act->inlineList );
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 );
586 /* Find states that have transitions with actions that have next
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;
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;
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;
606 if ( st->stateCondList.length() > 0 )
607 redFsm->bAnyConditions = true;
610 /* Assign ids to actions that are referenced. */
613 /* Set the maximums of various values used for deciding types. */
619 void lineDirective( ostream &out, char *fileName, int line )
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++ ) {