1 /*
2 * Copyright 2001-2006 Adrian Thurston <thurston@complang.org>
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 "redfsm.h"
23 #include "avlmap.h"
24 #include "mergesort.h"
25 #include <iostream>
26 #include <sstream>
27
28 using std::ostringstream;
29
nameOrLoc()30 string GenAction::nameOrLoc()
31 {
32 if ( name != 0 )
33 return string(name);
34 else {
35 ostringstream ret;
36 ret << loc.line << ":" << loc.col;
37 return ret.str();
38 }
39 }
40
RedFsmAp()41 RedFsmAp::RedFsmAp()
42 :
43 forcedErrorState(false),
44 nextActionId(0),
45 nextTransId(0),
46 startState(0),
47 errState(0),
48 errTrans(0),
49 firstFinState(0),
50 numFinStates(0),
51 bAnyToStateActions(false),
52 bAnyFromStateActions(false),
53 bAnyRegActions(false),
54 bAnyEofActions(false),
55 bAnyEofTrans(false),
56 bAnyActionGotos(false),
57 bAnyActionCalls(false),
58 bAnyActionRets(false),
59 bAnyActionByValControl(false),
60 bAnyRegActionRets(false),
61 bAnyRegActionByValControl(false),
62 bAnyRegNextStmt(false),
63 bAnyRegCurStateRef(false),
64 bAnyRegBreak(false),
65 bAnyConditions(false)
66 {
67 }
68
69 /* Does the machine have any actions. */
anyActions()70 bool RedFsmAp::anyActions()
71 {
72 return actionMap.length() > 0;
73 }
74
depthFirstOrdering(RedStateAp * state)75 void RedFsmAp::depthFirstOrdering( RedStateAp *state )
76 {
77 /* Nothing to do if the state is already on the list. */
78 if ( state->onStateList )
79 return;
80
81 /* Doing depth first, put state on the list. */
82 state->onStateList = true;
83 stateList.append( state );
84
85 /* At this point transitions should only be in ranges. */
86 assert( state->outSingle.length() == 0 );
87 assert( state->defTrans == 0 );
88
89 /* Recurse on everything ranges. */
90 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
91 if ( rtel->value->targ != 0 )
92 depthFirstOrdering( rtel->value->targ );
93 }
94 }
95
96 /* Ordering states by transition connections. */
depthFirstOrdering()97 void RedFsmAp::depthFirstOrdering()
98 {
99 /* Init on state list flags. */
100 for ( RedStateList::Iter st = stateList; st.lte(); st++ )
101 st->onStateList = false;
102
103 /* Clear out the state list, we will rebuild it. */
104 int stateListLen = stateList.length();
105 stateList.abandon();
106
107 /* Add back to the state list from the start state and all other entry
108 * points. */
109 if ( startState != 0 )
110 depthFirstOrdering( startState );
111 for ( RedStateSet::Iter en = entryPoints; en.lte(); en++ )
112 depthFirstOrdering( *en );
113 if ( forcedErrorState )
114 depthFirstOrdering( errState );
115
116 /* Make sure we put everything back on. */
117 assert( stateListLen == stateList.length() );
118 }
119
120 /* Assign state ids by appearance in the state list. */
sequentialStateIds()121 void RedFsmAp::sequentialStateIds()
122 {
123 /* Table based machines depend on the state numbers starting at zero. */
124 nextStateId = 0;
125 for ( RedStateList::Iter st = stateList; st.lte(); st++ )
126 st->id = nextStateId++;
127 }
128
129 /* Stable sort the states by final state status. */
sortStatesByFinal()130 void RedFsmAp::sortStatesByFinal()
131 {
132 /* Move forward through the list and throw final states onto the end. */
133 RedStateAp *state = 0;
134 RedStateAp *next = stateList.head;
135 RedStateAp *last = stateList.tail;
136 while ( state != last ) {
137 /* Move forward and load up the next. */
138 state = next;
139 next = state->next;
140
141 /* Throw to the end? */
142 if ( state->isFinal ) {
143 stateList.detach( state );
144 stateList.append( state );
145 }
146 }
147 }
148
149 /* Assign state ids by final state state status. */
sortStateIdsByFinal()150 void RedFsmAp::sortStateIdsByFinal()
151 {
152 /* Table based machines depend on this starting at zero. */
153 nextStateId = 0;
154
155 /* First pass to assign non final ids. */
156 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
157 if ( ! st->isFinal )
158 st->id = nextStateId++;
159 }
160
161 /* Second pass to assign final ids. */
162 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
163 if ( st->isFinal )
164 st->id = nextStateId++;
165 }
166 }
167
168 struct CmpStateById
169 {
compareCmpStateById170 static int compare( RedStateAp *st1, RedStateAp *st2 )
171 {
172 if ( st1->id < st2->id )
173 return -1;
174 else if ( st1->id > st2->id )
175 return 1;
176 else
177 return 0;
178 }
179 };
180
sortByStateId()181 void RedFsmAp::sortByStateId()
182 {
183 /* Make the array. */
184 int pos = 0;
185 RedStateAp **ptrList = new RedStateAp*[stateList.length()];
186 for ( RedStateList::Iter st = stateList; st.lte(); st++, pos++ )
187 ptrList[pos] = st;
188
189 MergeSort<RedStateAp*, CmpStateById> mergeSort;
190 mergeSort.sort( ptrList, stateList.length() );
191
192 stateList.abandon();
193 for ( int st = 0; st < pos; st++ )
194 stateList.append( ptrList[st] );
195
196 delete[] ptrList;
197 }
198
199 /* Find the final state with the lowest id. */
findFirstFinState()200 void RedFsmAp::findFirstFinState()
201 {
202 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
203 if ( st->isFinal && (firstFinState == 0 || st->id < firstFinState->id) )
204 firstFinState = st;
205 }
206 }
207
assignActionLocs()208 void RedFsmAp::assignActionLocs()
209 {
210 int nextLocation = 0;
211 for ( GenActionTableMap::Iter act = actionMap; act.lte(); act++ ) {
212 /* Store the loc, skip over the array and a null terminator. */
213 act->location = nextLocation;
214 nextLocation += act->key.length() + 1;
215 }
216 }
217
218 /* Check if we can extend the current range by displacing any ranges
219 * ahead to the singles. */
canExtend(const RedTransList & list,int pos)220 bool RedFsmAp::canExtend( const RedTransList &list, int pos )
221 {
222 /* Get the transition that we want to extend. */
223 RedTransAp *extendTrans = list[pos].value;
224
225 /* Look ahead in the transition list. */
226 for ( int next = pos + 1; next < list.length(); pos++, next++ ) {
227 /* If they are not continuous then cannot extend. */
228 Key nextKey = list[next].lowKey;
229 nextKey.decrement();
230 if ( list[pos].highKey != nextKey )
231 break;
232
233 /* Check for the extenstion property. */
234 if ( extendTrans == list[next].value )
235 return true;
236
237 /* If the span of the next element is more than one, then don't keep
238 * checking, it won't be moved to single. */
239 unsigned long long nextSpan = keyOps->span( list[next].lowKey, list[next].highKey );
240 if ( nextSpan > 1 )
241 break;
242 }
243 return false;
244 }
245
246 /* Move ranges to the singles list. */
moveTransToSingle(RedStateAp * state)247 void RedFsmAp::moveTransToSingle( RedStateAp *state )
248 {
249 RedTransList &range = state->outRange;
250 RedTransList &single = state->outSingle;
251 for ( int rpos = 0; rpos < range.length(); ) {
252 /* Check if this is a range we can extend. */
253 if ( canExtend( range, rpos ) ) {
254 /* Transfer singles over. */
255 while ( range[rpos].value != range[rpos+1].value ) {
256 /* Transfer the range to single. */
257 single.append( range[rpos+1] );
258 range.remove( rpos+1 );
259 }
260
261 /* Extend. */
262 range[rpos].highKey = range[rpos+1].highKey;
263 range.remove( rpos+1 );
264 }
265 /* Maybe move it to the singles. */
266 else if ( keyOps->span( range[rpos].lowKey, range[rpos].highKey ) == 1 ) {
267 single.append( range[rpos] );
268 range.remove( rpos );
269 }
270 else {
271 /* Keeping it in the ranges. */
272 rpos += 1;
273 }
274 }
275 }
276
277 /* Look through ranges and choose suitable single character transitions. */
chooseSingle()278 void RedFsmAp::chooseSingle()
279 {
280 /* Loop the states. */
281 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
282 /* Rewrite the transition list taking out the suitable single
283 * transtions. */
284 moveTransToSingle( st );
285 }
286 }
287
makeFlat()288 void RedFsmAp::makeFlat()
289 {
290 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
291 if ( st->stateCondList.length() == 0 ) {
292 st->condLowKey = 0;
293 st->condHighKey = 0;
294 }
295 else {
296 st->condLowKey = st->stateCondList.head->lowKey;
297 st->condHighKey = st->stateCondList.tail->highKey;
298
299 unsigned long long span = keyOps->span( st->condLowKey, st->condHighKey );
300 st->condList = new GenCondSpace*[ span ];
301 memset( st->condList, 0, sizeof(GenCondSpace*)*span );
302
303 for ( GenStateCondList::Iter sci = st->stateCondList; sci.lte(); sci++ ) {
304 unsigned long long base, trSpan;
305 base = keyOps->span( st->condLowKey, sci->lowKey )-1;
306 trSpan = keyOps->span( sci->lowKey, sci->highKey );
307 for ( unsigned long long pos = 0; pos < trSpan; pos++ )
308 st->condList[base+pos] = sci->condSpace;
309 }
310 }
311
312 if ( st->outRange.length() == 0 ) {
313 st->lowKey = st->highKey = 0;
314 st->transList = 0;
315 }
316 else {
317 st->lowKey = st->outRange[0].lowKey;
318 st->highKey = st->outRange[st->outRange.length()-1].highKey;
319 unsigned long long span = keyOps->span( st->lowKey, st->highKey );
320 st->transList = new RedTransAp*[ span ];
321 memset( st->transList, 0, sizeof(RedTransAp*)*span );
322
323 for ( RedTransList::Iter trans = st->outRange; trans.lte(); trans++ ) {
324 unsigned long long base, trSpan;
325 base = keyOps->span( st->lowKey, trans->lowKey )-1;
326 trSpan = keyOps->span( trans->lowKey, trans->highKey );
327 for ( unsigned long long pos = 0; pos < trSpan; pos++ )
328 st->transList[base+pos] = trans->value;
329 }
330
331 /* Fill in the gaps with the default transition. */
332 for ( unsigned long long pos = 0; pos < span; pos++ ) {
333 if ( st->transList[pos] == 0 )
334 st->transList[pos] = st->defTrans;
335 }
336 }
337 }
338 }
339
340
341 /* A default transition has been picked, move it from the outRange to the
342 * default pointer. */
moveToDefault(RedTransAp * defTrans,RedStateAp * state)343 void RedFsmAp::moveToDefault( RedTransAp *defTrans, RedStateAp *state )
344 {
345 /* Rewrite the outRange, omitting any ranges that use
346 * the picked default. */
347 RedTransList outRange;
348 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
349 /* If it does not take the default, copy it over. */
350 if ( rtel->value != defTrans )
351 outRange.append( *rtel );
352 }
353
354 /* Save off the range we just created into the state's range. */
355 state->outRange.transfer( outRange );
356
357 /* Store the default. */
358 state->defTrans = defTrans;
359 }
360
alphabetCovered(RedTransList & outRange)361 bool RedFsmAp::alphabetCovered( RedTransList &outRange )
362 {
363 /* Cannot cover without any out ranges. */
364 if ( outRange.length() == 0 )
365 return false;
366
367 /* If the first range doesn't start at the the lower bound then the
368 * alphabet is not covered. */
369 RedTransList::Iter rtel = outRange;
370 if ( keyOps->minKey < rtel->lowKey )
371 return false;
372
373 /* Check that every range is next to the previous one. */
374 rtel.increment();
375 for ( ; rtel.lte(); rtel++ ) {
376 Key highKey = rtel[-1].highKey;
377 highKey.increment();
378 if ( highKey != rtel->lowKey )
379 return false;
380 }
381
382 /* The last must extend to the upper bound. */
383 RedTransEl *last = &outRange[outRange.length()-1];
384 if ( last->highKey < keyOps->maxKey )
385 return false;
386
387 return true;
388 }
389
chooseDefaultSpan(RedStateAp * state)390 RedTransAp *RedFsmAp::chooseDefaultSpan( RedStateAp *state )
391 {
392 /* Make a set of transitions from the outRange. */
393 RedTransSet stateTransSet;
394 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ )
395 stateTransSet.insert( rtel->value );
396
397 /* For each transition in the find how many alphabet characters the
398 * transition spans. */
399 unsigned long long *span = new unsigned long long[stateTransSet.length()];
400 memset( span, 0, sizeof(unsigned long long) * stateTransSet.length() );
401 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
402 /* Lookup the transition in the set. */
403 RedTransAp **inSet = stateTransSet.find( rtel->value );
404 int pos = inSet - stateTransSet.data;
405 span[pos] += keyOps->span( rtel->lowKey, rtel->highKey );
406 }
407
408 /* Find the max span, choose it for making the default. */
409 RedTransAp *maxTrans = 0;
410 unsigned long long maxSpan = 0;
411 for ( RedTransSet::Iter rtel = stateTransSet; rtel.lte(); rtel++ ) {
412 if ( span[rtel.pos()] > maxSpan ) {
413 maxSpan = span[rtel.pos()];
414 maxTrans = *rtel;
415 }
416 }
417
418 delete[] span;
419 return maxTrans;
420 }
421
422 /* Pick default transitions from ranges for the states. */
chooseDefaultSpan()423 void RedFsmAp::chooseDefaultSpan()
424 {
425 /* Loop the states. */
426 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
427 /* Only pick a default transition if the alphabet is covered. This
428 * avoids any transitions in the out range that go to error and avoids
429 * the need for an ERR state. */
430 if ( alphabetCovered( st->outRange ) ) {
431 /* Pick a default transition by largest span. */
432 RedTransAp *defTrans = chooseDefaultSpan( st );
433
434 /* Rewrite the transition list taking out the transition we picked
435 * as the default and store the default. */
436 moveToDefault( defTrans, st );
437 }
438 }
439 }
440
chooseDefaultGoto(RedStateAp * state)441 RedTransAp *RedFsmAp::chooseDefaultGoto( RedStateAp *state )
442 {
443 /* Make a set of transitions from the outRange. */
444 RedTransSet stateTransSet;
445 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
446 if ( rtel->value->targ == state->next )
447 return rtel->value;
448 }
449 return 0;
450 }
451
chooseDefaultGoto()452 void RedFsmAp::chooseDefaultGoto()
453 {
454 /* Loop the states. */
455 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
456 /* Pick a default transition. */
457 RedTransAp *defTrans = chooseDefaultGoto( st );
458 if ( defTrans == 0 )
459 defTrans = chooseDefaultSpan( st );
460
461 /* Rewrite the transition list taking out the transition we picked
462 * as the default and store the default. */
463 moveToDefault( defTrans, st );
464 }
465 }
466
chooseDefaultNumRanges(RedStateAp * state)467 RedTransAp *RedFsmAp::chooseDefaultNumRanges( RedStateAp *state )
468 {
469 /* Make a set of transitions from the outRange. */
470 RedTransSet stateTransSet;
471 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ )
472 stateTransSet.insert( rtel->value );
473
474 /* For each transition in the find how many ranges use the transition. */
475 int *numRanges = new int[stateTransSet.length()];
476 memset( numRanges, 0, sizeof(int) * stateTransSet.length() );
477 for ( RedTransList::Iter rtel = state->outRange; rtel.lte(); rtel++ ) {
478 /* Lookup the transition in the set. */
479 RedTransAp **inSet = stateTransSet.find( rtel->value );
480 numRanges[inSet - stateTransSet.data] += 1;
481 }
482
483 /* Find the max number of ranges. */
484 RedTransAp *maxTrans = 0;
485 int maxNumRanges = 0;
486 for ( RedTransSet::Iter rtel = stateTransSet; rtel.lte(); rtel++ ) {
487 if ( numRanges[rtel.pos()] > maxNumRanges ) {
488 maxNumRanges = numRanges[rtel.pos()];
489 maxTrans = *rtel;
490 }
491 }
492
493 delete[] numRanges;
494 return maxTrans;
495 }
496
chooseDefaultNumRanges()497 void RedFsmAp::chooseDefaultNumRanges()
498 {
499 /* Loop the states. */
500 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
501 /* Pick a default transition. */
502 RedTransAp *defTrans = chooseDefaultNumRanges( st );
503
504 /* Rewrite the transition list taking out the transition we picked
505 * as the default and store the default. */
506 moveToDefault( defTrans, st );
507 }
508 }
509
getErrorTrans()510 RedTransAp *RedFsmAp::getErrorTrans( )
511 {
512 /* If the error trans has not been made aready, make it. */
513 if ( errTrans == 0 ) {
514 /* This insert should always succeed since no transition created by
515 * the user can point to the error state. */
516 errTrans = new RedTransAp( getErrorState(), 0, nextTransId++ );
517 RedTransAp *inRes = transSet.insert( errTrans );
518 assert( inRes != 0 );
519 }
520 return errTrans;
521 }
522
getErrorState()523 RedStateAp *RedFsmAp::getErrorState()
524 {
525 /* Something went wrong. An error state is needed but one was not supplied
526 * by the frontend. */
527 assert( errState != 0 );
528 return errState;
529 }
530
531
allocateTrans(RedStateAp * targ,RedAction * action)532 RedTransAp *RedFsmAp::allocateTrans( RedStateAp *targ, RedAction *action )
533 {
534 /* Create a reduced trans and look for it in the transiton set. */
535 RedTransAp redTrans( targ, action, 0 );
536 RedTransAp *inDict = transSet.find( &redTrans );
537 if ( inDict == 0 ) {
538 inDict = new RedTransAp( targ, action, nextTransId++ );
539 transSet.insert( inDict );
540 }
541 return inDict;
542 }
543
partitionFsm(int nparts)544 void RedFsmAp::partitionFsm( int nparts )
545 {
546 /* At this point the states are ordered by a depth-first traversal. We
547 * will allocate to partitions based on this ordering. */
548 this->nParts = nparts;
549 int partSize = stateList.length() / nparts;
550 int remainder = stateList.length() % nparts;
551 int numInPart = partSize;
552 int partition = 0;
553 if ( remainder-- > 0 )
554 numInPart += 1;
555 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
556 st->partition = partition;
557
558 numInPart -= 1;
559 if ( numInPart == 0 ) {
560 partition += 1;
561 numInPart = partSize;
562 if ( remainder-- > 0 )
563 numInPart += 1;
564 }
565 }
566 }
567
setInTrans()568 void RedFsmAp::setInTrans()
569 {
570 /* First pass counts the number of transitions. */
571 for ( TransApSet::Iter trans = transSet; trans.lte(); trans++ )
572 trans->targ->numInTrans += 1;
573
574 /* Pass over states to allocate the needed memory. Reset the counts so we
575 * can use them as the current size. */
576 for ( RedStateList::Iter st = stateList; st.lte(); st++ ) {
577 st->inTrans = new RedTransAp*[st->numInTrans];
578 st->numInTrans = 0;
579 }
580
581 /* Second pass over transitions copies pointers into the in trans list. */
582 for ( TransApSet::Iter trans = transSet; trans.lte(); trans++ )
583 trans->targ->inTrans[trans->targ->numInTrans++] = trans;
584 }
585