1 /*
2 * Copyright 2001-2007 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 <string.h>
23 #include <assert.h>
24 #include "fsmgraph.h"
25
26 /* Simple singly linked list append routine for the fill list. The new state
27 * goes to the end of the list. */
fillListAppend(StateAp * state)28 void MergeData::fillListAppend( StateAp *state )
29 {
30 state->alg.next = 0;
31
32 if ( stfillHead == 0 ) {
33 /* List is empty, state becomes head and tail. */
34 stfillHead = state;
35 stfillTail = state;
36 }
37 else {
38 /* List is not empty, state goes after last element. */
39 stfillTail->alg.next = state;
40 stfillTail = state;
41 }
42 }
43
44 /* Graph constructor. */
FsmAp()45 FsmAp::FsmAp()
46 :
47 /* No start state. */
48 startState(0),
49 errState(0),
50
51 /* Misfit accounting is a switch, turned on only at specific times. It
52 * controls what happens when states have no way in from the outside
53 * world.. */
54 misfitAccounting(false)
55 {
56 }
57
58 /* Copy all graph data including transitions. */
FsmAp(const FsmAp & graph)59 FsmAp::FsmAp( const FsmAp &graph )
60 :
61 /* Lists start empty. Will be filled by copy. */
62 stateList(),
63 misfitList(),
64
65 /* Copy in the entry points,
66 * pointers will be resolved later. */
67 entryPoints(graph.entryPoints),
68 startState(graph.startState),
69 errState(0),
70
71 /* Will be filled by copy. */
72 finStateSet(),
73
74 /* Misfit accounting is only on during merging. */
75 misfitAccounting(false)
76 {
77 /* Create the states and record their map in the original state. */
78 StateList::Iter origState = graph.stateList;
79 for ( ; origState.lte(); origState++ ) {
80 /* Make the new state. */
81 StateAp *newState = new StateAp( *origState );
82
83 /* Add the state to the list. */
84 stateList.append( newState );
85
86 /* Set the mapsTo item of the old state. */
87 origState->alg.stateMap = newState;
88 }
89
90 /* Derefernce all the state maps. */
91 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
92 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
93 /* The points to the original in the src machine. The taget's duplicate
94 * is in the statemap. */
95 StateAp *toState = trans->toState != 0 ? trans->toState->alg.stateMap : 0;
96
97 /* Attach The transition to the duplicate. */
98 trans->toState = 0;
99 attachTrans( state, toState, trans );
100 }
101
102 /* Fix the eofTarg, if set. */
103 if ( state->eofTarget != 0 )
104 state->eofTarget = state->eofTarget->alg.stateMap;
105 }
106
107 /* Fix the state pointers in the entry points array. */
108 EntryMapEl *eel = entryPoints.data;
109 for ( int e = 0; e < entryPoints.length(); e++, eel++ ) {
110 /* Get the duplicate of the state. */
111 eel->value = eel->value->alg.stateMap;
112
113 /* Foreign in transitions must be built up when duping machines so
114 * increment it here. */
115 eel->value->foreignInTrans += 1;
116 }
117
118 /* Fix the start state pointer and the new start state's count of in
119 * transiions. */
120 startState = startState->alg.stateMap;
121 startState->foreignInTrans += 1;
122
123 /* Build the final state set. */
124 StateSet::Iter st = graph.finStateSet;
125 for ( ; st.lte(); st++ )
126 finStateSet.insert((*st)->alg.stateMap);
127 }
128
129 /* Deletes all transition data then deletes each state. */
~FsmAp()130 FsmAp::~FsmAp()
131 {
132 /* Delete all the transitions. */
133 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
134 /* Iterate the out transitions, deleting them. */
135 state->outList.empty();
136 }
137
138 /* Delete all the states. */
139 stateList.empty();
140 }
141
142 /* Set a state final. The state has its isFinState set to true and the state
143 * is added to the finStateSet. */
setFinState(StateAp * state)144 void FsmAp::setFinState( StateAp *state )
145 {
146 /* Is it already a fin state. */
147 if ( state->stateBits & STB_ISFINAL )
148 return;
149
150 state->stateBits |= STB_ISFINAL;
151 finStateSet.insert( state );
152 }
153
154 /* Set a state non-final. The has its isFinState flag set false and the state
155 * is removed from the final state set. */
unsetFinState(StateAp * state)156 void FsmAp::unsetFinState( StateAp *state )
157 {
158 /* Is it already a non-final state? */
159 if ( ! (state->stateBits & STB_ISFINAL) )
160 return;
161
162 /* When a state looses its final state status it must relinquish all the
163 * properties that are allowed only for final states. */
164 clearOutData( state );
165
166 state->stateBits &= ~ STB_ISFINAL;
167 finStateSet.remove( state );
168 }
169
170 /* Set and unset a state as the start state. */
setStartState(StateAp * state)171 void FsmAp::setStartState( StateAp *state )
172 {
173 /* Sould change from unset to set. */
174 assert( startState == 0 );
175 startState = state;
176
177 if ( misfitAccounting ) {
178 /* If the number of foreign in transitions is about to go up to 1 then
179 * take it off the misfit list and put it on the head list. */
180 if ( state->foreignInTrans == 0 )
181 stateList.append( misfitList.detach( state ) );
182 }
183
184 /* Up the foreign in transitions to the state. */
185 state->foreignInTrans += 1;
186 }
187
unsetStartState()188 void FsmAp::unsetStartState()
189 {
190 /* Should change from set to unset. */
191 assert( startState != 0 );
192
193 /* Decrement the entry's count of foreign entries. */
194 startState->foreignInTrans -= 1;
195
196 if ( misfitAccounting ) {
197 /* If the number of foreign in transitions just went down to 0 then take
198 * it off the main list and put it on the misfit list. */
199 if ( startState->foreignInTrans == 0 )
200 misfitList.append( stateList.detach( startState ) );
201 }
202
203 startState = 0;
204 }
205
206 /* Associate an id with a state. Makes the state a named entry point. Has no
207 * effect if the entry point is already mapped to the state. */
setEntry(int id,StateAp * state)208 void FsmAp::setEntry( int id, StateAp *state )
209 {
210 /* Insert the id into the state. If the state is already labelled with id,
211 * nothing to do. */
212 if ( state->entryIds.insert( id ) ) {
213 /* Insert the entry and assert that it succeeds. */
214 entryPoints.insertMulti( id, state );
215
216 if ( misfitAccounting ) {
217 /* If the number of foreign in transitions is about to go up to 1 then
218 * take it off the misfit list and put it on the head list. */
219 if ( state->foreignInTrans == 0 )
220 stateList.append( misfitList.detach( state ) );
221 }
222
223 /* Up the foreign in transitions to the state. */
224 state->foreignInTrans += 1;
225 }
226 }
227
228 /* Remove the association of an id with a state. The state looses it's entry
229 * point status. Assumes that the id is indeed mapped to state. */
unsetEntry(int id,StateAp * state)230 void FsmAp::unsetEntry( int id, StateAp *state )
231 {
232 /* Find the entry point in on id. */
233 EntryMapEl *enLow = 0, *enHigh = 0;
234 entryPoints.findMulti( id, enLow, enHigh );
235 while ( enLow->value != state )
236 enLow += 1;
237
238 /* Remove the record from the map. */
239 entryPoints.remove( enLow );
240
241 /* Remove the state's sense of the link. */
242 state->entryIds.remove( id );
243 state->foreignInTrans -= 1;
244 if ( misfitAccounting ) {
245 /* If the number of foreign in transitions just went down to 0 then take
246 * it off the main list and put it on the misfit list. */
247 if ( state->foreignInTrans == 0 )
248 misfitList.append( stateList.detach( state ) );
249 }
250 }
251
252 /* Remove all association of an id with states. Assumes that the id is indeed
253 * mapped to a state. */
unsetEntry(int id)254 void FsmAp::unsetEntry( int id )
255 {
256 /* Find the entry point in on id. */
257 EntryMapEl *enLow = 0, *enHigh = 0;
258 entryPoints.findMulti( id, enLow, enHigh );
259 for ( EntryMapEl *mel = enLow; mel <= enHigh; mel++ ) {
260 /* Remove the state's sense of the link. */
261 mel->value->entryIds.remove( id );
262 mel->value->foreignInTrans -= 1;
263 if ( misfitAccounting ) {
264 /* If the number of foreign in transitions just went down to 0
265 * then take it off the main list and put it on the misfit list. */
266 if ( mel->value->foreignInTrans == 0 )
267 misfitList.append( stateList.detach( mel->value ) );
268 }
269 }
270
271 /* Remove the records from the entry points map. */
272 entryPoints.removeMulti( enLow, enHigh );
273 }
274
275
changeEntry(int id,StateAp * to,StateAp * from)276 void FsmAp::changeEntry( int id, StateAp *to, StateAp *from )
277 {
278 /* Find the entry in the entry map. */
279 EntryMapEl *enLow = 0, *enHigh = 0;
280 entryPoints.findMulti( id, enLow, enHigh );
281 while ( enLow->value != from )
282 enLow += 1;
283
284 /* Change it to the new target. */
285 enLow->value = to;
286
287 /* Remove from's sense of the link. */
288 from->entryIds.remove( id );
289 from->foreignInTrans -= 1;
290 if ( misfitAccounting ) {
291 /* If the number of foreign in transitions just went down to 0 then take
292 * it off the main list and put it on the misfit list. */
293 if ( from->foreignInTrans == 0 )
294 misfitList.append( stateList.detach( from ) );
295 }
296
297 /* Add to's sense of the link. */
298 if ( to->entryIds.insert( id ) != 0 ) {
299 if ( misfitAccounting ) {
300 /* If the number of foreign in transitions is about to go up to 1 then
301 * take it off the misfit list and put it on the head list. */
302 if ( to->foreignInTrans == 0 )
303 stateList.append( misfitList.detach( to ) );
304 }
305
306 /* Up the foreign in transitions to the state. */
307 to->foreignInTrans += 1;
308 }
309 }
310
311
312 /* Clear all entry points from a machine. */
unsetAllEntryPoints()313 void FsmAp::unsetAllEntryPoints()
314 {
315 for ( EntryMap::Iter en = entryPoints; en.lte(); en++ ) {
316 /* Kill all the state's entry points at once. */
317 if ( en->value->entryIds.length() > 0 ) {
318 en->value->foreignInTrans -= en->value->entryIds.length();
319
320 if ( misfitAccounting ) {
321 /* If the number of foreign in transitions just went down to 0
322 * then take it off the main list and put it on the misfit
323 * list. */
324 if ( en->value->foreignInTrans == 0 )
325 misfitList.append( stateList.detach( en->value ) );
326 }
327
328 /* Clear the set of ids out all at once. */
329 en->value->entryIds.empty();
330 }
331 }
332
333 /* Now clear out the entry map all at once. */
334 entryPoints.empty();
335 }
336
337 /* Assigning an epsilon transition into final states. */
epsilonTrans(int id)338 void FsmAp::epsilonTrans( int id )
339 {
340 for ( StateSet::Iter fs = finStateSet; fs.lte(); fs++ )
341 (*fs)->epsilonTrans.append( id );
342 }
343
344 /* Mark all states reachable from state. Traverses transitions forward. Used
345 * for removing states that have no path into them. */
markReachableFromHere(StateAp * state)346 void FsmAp::markReachableFromHere( StateAp *state )
347 {
348 /* Base case: return; */
349 if ( state->stateBits & STB_ISMARKED )
350 return;
351
352 /* Set this state as processed. We are going to visit all states that this
353 * state has a transition to. */
354 state->stateBits |= STB_ISMARKED;
355
356 /* Recurse on all out transitions. */
357 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
358 if ( trans->toState != 0 )
359 markReachableFromHere( trans->toState );
360 }
361 }
362
markReachableFromHereStopFinal(StateAp * state)363 void FsmAp::markReachableFromHereStopFinal( StateAp *state )
364 {
365 /* Base case: return; */
366 if ( state->stateBits & STB_ISMARKED )
367 return;
368
369 /* Set this state as processed. We are going to visit all states that this
370 * state has a transition to. */
371 state->stateBits |= STB_ISMARKED;
372
373 /* Recurse on all out transitions. */
374 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ ) {
375 StateAp *toState = trans->toState;
376 if ( toState != 0 && !toState->isFinState() )
377 markReachableFromHereStopFinal( toState );
378 }
379 }
380
381 /* Mark all states reachable from state. Traverse transitions backwards. Used
382 * for removing dead end paths in graphs. */
markReachableFromHereReverse(StateAp * state)383 void FsmAp::markReachableFromHereReverse( StateAp *state )
384 {
385 /* Base case: return; */
386 if ( state->stateBits & STB_ISMARKED )
387 return;
388
389 /* Set this state as processed. We are going to visit all states with
390 * transitions into this state. */
391 state->stateBits |= STB_ISMARKED;
392
393 /* Recurse on all items in transitions. */
394 for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ )
395 markReachableFromHereReverse( trans->fromState );
396 }
397
398 /* Determine if there are any entry points into a start state other than the
399 * start state. Setting starting transitions requires that the start state be
400 * isolated. In most cases a start state will already be isolated. */
isStartStateIsolated()401 bool FsmAp::isStartStateIsolated()
402 {
403 /* If there are any in transitions then the state is not isolated. */
404 if ( startState->inList.head != 0 )
405 return false;
406
407 /* If there are any entry points then isolated. */
408 if ( startState->entryIds.length() > 0 )
409 return false;
410
411 return true;
412 }
413
414 /* Bring in other's entry points. Assumes others states are going to be
415 * copied into this machine. */
copyInEntryPoints(FsmAp * other)416 void FsmAp::copyInEntryPoints( FsmAp *other )
417 {
418 /* Use insert multi because names are not unique. */
419 for ( EntryMap::Iter en = other->entryPoints; en.lte(); en++ )
420 entryPoints.insertMulti( en->key, en->value );
421 }
422
423
unsetAllFinStates()424 void FsmAp::unsetAllFinStates()
425 {
426 for ( StateSet::Iter st = finStateSet; st.lte(); st++ )
427 (*st)->stateBits &= ~ STB_ISFINAL;
428 finStateSet.empty();
429 }
430
setFinBits(int finStateBits)431 void FsmAp::setFinBits( int finStateBits )
432 {
433 for ( int s = 0; s < finStateSet.length(); s++ )
434 finStateSet.data[s]->stateBits |= finStateBits;
435 }
436
437
438 /* Tests the integrity of the transition lists and the fromStates. */
verifyIntegrity()439 void FsmAp::verifyIntegrity()
440 {
441 for ( StateList::Iter state = stateList; state.lte(); state++ ) {
442 /* Walk the out transitions and assert fromState is correct. */
443 for ( TransList::Iter trans = state->outList; trans.lte(); trans++ )
444 assert( trans->fromState == state );
445
446 /* Walk the inlist and assert toState is correct. */
447 for ( TransInList::Iter trans = state->inList; trans.lte(); trans++ )
448 assert( trans->toState == state );
449 }
450 }
451
verifyReachability()452 void FsmAp::verifyReachability()
453 {
454 /* Mark all the states that can be reached
455 * through the set of entry points. */
456 markReachableFromHere( startState );
457 for ( EntryMap::Iter en = entryPoints; en.lte(); en++ )
458 markReachableFromHere( en->value );
459
460 /* Check that everything got marked. */
461 for ( StateList::Iter st = stateList; st.lte(); st++ ) {
462 /* Assert it got marked and then clear the mark. */
463 assert( st->stateBits & STB_ISMARKED );
464 st->stateBits &= ~ STB_ISMARKED;
465 }
466 }
467
verifyNoDeadEndStates()468 void FsmAp::verifyNoDeadEndStates()
469 {
470 /* Mark all states that have paths to the final states. */
471 for ( StateSet::Iter pst = finStateSet; pst.lte(); pst++ )
472 markReachableFromHereReverse( *pst );
473
474 /* Start state gets honorary marking. Must be done AFTER recursive call. */
475 startState->stateBits |= STB_ISMARKED;
476
477 /* Make sure everything got marked. */
478 for ( StateList::Iter st = stateList; st.lte(); st++ ) {
479 /* Assert the state got marked and unmark it. */
480 assert( st->stateBits & STB_ISMARKED );
481 st->stateBits &= ~ STB_ISMARKED;
482 }
483 }
484
depthFirstOrdering(StateAp * state)485 void FsmAp::depthFirstOrdering( StateAp *state )
486 {
487 /* Nothing to do if the state is already on the list. */
488 if ( state->stateBits & STB_ONLIST )
489 return;
490
491 /* Doing depth first, put state on the list. */
492 state->stateBits |= STB_ONLIST;
493 stateList.append( state );
494
495 /* Recurse on everything ranges. */
496 for ( TransList::Iter tel = state->outList; tel.lte(); tel++ ) {
497 if ( tel->toState != 0 )
498 depthFirstOrdering( tel->toState );
499 }
500 }
501
502 /* Ordering states by transition connections. */
depthFirstOrdering()503 void FsmAp::depthFirstOrdering()
504 {
505 /* Init on state list flags. */
506 for ( StateList::Iter st = stateList; st.lte(); st++ )
507 st->stateBits &= ~STB_ONLIST;
508
509 /* Clear out the state list, we will rebuild it. */
510 int stateListLen = stateList.length();
511 stateList.abandon();
512
513 /* Add back to the state list from the start state and all other entry
514 * points. */
515 if ( errState != 0 )
516 depthFirstOrdering( errState );
517 depthFirstOrdering( startState );
518 for ( EntryMap::Iter en = entryPoints; en.lte(); en++ )
519 depthFirstOrdering( en->value );
520
521 /* Make sure we put everything back on. */
522 assert( stateListLen == stateList.length() );
523 }
524
525 /* Stable sort the states by final state status. */
sortStatesByFinal()526 void FsmAp::sortStatesByFinal()
527 {
528 /* Move forward through the list and throw final states onto the end. */
529 StateAp *state = 0;
530 StateAp *next = stateList.head;
531 StateAp *last = stateList.tail;
532 while ( state != last ) {
533 /* Move forward and load up the next. */
534 state = next;
535 next = state->next;
536
537 /* Throw to the end? */
538 if ( state->isFinState() ) {
539 stateList.detach( state );
540 stateList.append( state );
541 }
542 }
543 }
544
setStateNumbers(int base)545 void FsmAp::setStateNumbers( int base )
546 {
547 for ( StateList::Iter state = stateList; state.lte(); state++ )
548 state->alg.stateNum = base++;
549 }
550
551
checkErrTrans(StateAp * state,TransAp * trans)552 bool FsmAp::checkErrTrans( StateAp *state, TransAp *trans )
553 {
554 /* Might go directly to error state. */
555 if ( trans->toState == 0 )
556 return true;
557
558 if ( trans->prev == 0 ) {
559 /* If this is the first transition. */
560 if ( keyOps->minKey < trans->lowKey )
561 return true;
562 }
563 else {
564 /* Not the first transition. Compare against the prev. */
565 TransAp *prev = trans->prev;
566 Key nextKey = prev->highKey;
567 nextKey.increment();
568 if ( nextKey < trans->lowKey )
569 return true;
570 }
571 return false;
572 }
573
checkErrTransFinish(StateAp * state)574 bool FsmAp::checkErrTransFinish( StateAp *state )
575 {
576 /* Check if there are any ranges already. */
577 if ( state->outList.length() == 0 )
578 return true;
579 else {
580 /* Get the last and check for a gap on the end. */
581 TransAp *last = state->outList.tail;
582 if ( last->highKey < keyOps->maxKey )
583 return true;
584 }
585 return 0;
586 }
587
hasErrorTrans()588 bool FsmAp::hasErrorTrans()
589 {
590 bool result;
591 for ( StateList::Iter st = stateList; st.lte(); st++ ) {
592 for ( TransList::Iter tr = st->outList; tr.lte(); tr++ ) {
593 result = checkErrTrans( st, tr );
594 if ( result )
595 return true;
596 }
597 result = checkErrTransFinish( st );
598 if ( result )
599 return true;
600 }
601 return false;
602 }
603